Abstract
Counterfactual explanations (CFXs) provide human-understandablejustifications for model predictions, enabling actionable recourse andenhancing interpretability. To be reliable, CFXs must avoid regions of highpredictive uncertainty, where explanations may be misleading or inapplicable.However, existing methods often neglect uncertainty or lack principledmechanisms for incorporating it with formal guarantees. We propose CONFEX, anovel method for generating uncertainty-aware counterfactual explanations usingConformal Prediction (CP) and Mixed-Integer Linear Programming (MILP). CONFEXexplanations are designed to provide local coverage guarantees, addressing theissue that CFX generation violates exchangeability. To do so, we develop anovel localised CP procedure that enjoys an efficient MILP encoding byleveraging an offline tree-based partitioning of the input space. This way,CONFEX generates CFXs with rigorous guarantees on both predictive uncertaintyand optimality. We evaluate CONFEX against state-of-the-art methods acrossdiverse benchmarks and metrics, demonstrating that our uncertainty-awareapproach yields robust and plausible explanations.