# CONFEX: Uncertainty-Aware Counterfactual Explanations with Conformal Guarantees

arXiv: https://arxiv.org/abs/2510.19754 · HTML: https://mlsanity.com/paper/2510.19754/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 21 of its 34 references that are in the map.
- First posted on arXiv 22 Oct 2025.

## Builds on (most cited first, 21 of 21)

- [Counterfactual Explanations without Opening the Black Box: Automated Decisions and the GDPR](https://mlsanity.com/paper/1711.00399/) (2017)
- [Conformal Prediction Under Covariate Shift](https://mlsanity.com/paper/1904.06019/) (2019)
- [FACE: Feasible and Actionable Counterfactual Explanations](https://mlsanity.com/paper/1909.09369/) (2019)
- [Multi-Objective Counterfactual Explanations](https://mlsanity.com/paper/2004.11165/) (2020)
- [Conformal Prediction With Conditional Guarantees](https://mlsanity.com/paper/2305.12616/) (2023)
- [A survey of algorithmic recourse: definitions, formulations, solutions, and prospects](https://mlsanity.com/paper/2010.04050/) (2020)
- [Localized Conformal Prediction: A Generalized Inference Framework for Conformal Prediction](https://mlsanity.com/paper/2106.08460/) (2021)
- [Class-Conditional Conformal Prediction with Many Classes](https://mlsanity.com/paper/2306.09335/) (2023)
- [Getting a CLUE: A Method for Explaining Uncertainty Estimates](https://mlsanity.com/paper/2006.06848/) (2020)
- ['It's Reducing a Human Being to a Percentage'; Perceptions of Justice in Algorithmic Decisions](https://mlsanity.com/paper/1801.10408/) (2018)
- [CARLA: A Python Library to Benchmark Algorithmic Recourse and Counterfactual Explanation Algorithms](https://mlsanity.com/paper/2108.00783/) (2021)
- [Interpretable Predictions of Tree-based Ensembles via Actionable Feature Tweaking](https://mlsanity.com/paper/1706.06691/) (2017)
- [Batch Multivalid Conformal Prediction](https://mlsanity.com/paper/2209.15145/) (2022)
- [Robust Counterfactual Explanations for Tree-Based Ensembles](https://mlsanity.com/paper/2207.02739/) (2022)
- [Conformal prediction with local weights: randomization enables local guarantees](https://mlsanity.com/paper/2310.07850/) (2023)
- [FOCUS: Flexible Optimizable Counterfactual Explanations for Tree Ensembles](https://mlsanity.com/paper/1911.12199/) (2019)
- [Generating Interpretable Counterfactual Explanations By Implicit Minimisation of Epistemic and Aleatoric Uncertainties](https://mlsanity.com/paper/2103.08951/) (2021)
- [Regression Trees for Fast and Adaptive Prediction Intervals](https://mlsanity.com/paper/2402.07357/) (2024)
- [Faithful Model Explanations through Energy-Constrained Conformal Counterfactuals](https://mlsanity.com/paper/2312.10648/) (2023)
- [The k-d tree data structure and a proof for neighborhood computation in expected logarithmic time](https://mlsanity.com/paper/1903.04936/) (2019)
- [Individualised Counterfactual Examples Using Conformal Prediction Intervals](https://mlsanity.com/paper/2505.22326/) (2025)

## Abstract (arXiv)

Counterfactual explanations (CFXs) provide human-understandable justifications for model predictions, enabling actionable recourse and enhancing interpretability. To be reliable, CFXs must avoid regions of high predictive uncertainty, where explanations may be misleading or inapplicable. However, existing methods often neglect uncertainty or lack principled mechanisms for incorporating it with formal guarantees. We propose CONFEX, a novel method for generating uncertainty-aware counterfactual explanations using Conformal Prediction (CP) and Mixed-Integer Linear Programming (MILP). CONFEX explanations are designed to provide local coverage guarantees, addressing the issue that CFX generation violates exchangeability. To do so, we develop a novel localised CP procedure that enjoys an efficient MILP encoding by leveraging an offline tree-based partitioning of the input space. This way, CONFEX generates CFXs with rigorous guarantees on both predictive uncertainty and optimality. We evaluate CONFEX against state-of-the-art methods across diverse benchmarks and metrics, demonstrating that our uncertainty-aware approach yields robust and plausible explanations.