# Scaling Guarantees for Nearest Counterfactual Explanations

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

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Oct 2020.

## Built on by (most cited first, 22 of 22)

- [Robust Counterfactual Explanations in Machine Learning: A Survey](https://mlsanity.com/paper/2402.01928/) (2024)
- [Formalising the Robustness of Counterfactual Explanations for Neural Networks](https://mlsanity.com/paper/2208.14878/) (2022)
- [Robust Explanation Constraints for Neural Networks](https://mlsanity.com/paper/2212.08507/) (2022)
- [Provably Robust and Plausible Counterfactual Explanations for Neural Networks via Robust Optimisation](https://mlsanity.com/paper/2309.12545/) (2023)
- [Counterfactual Explanations as Interventions in Latent Space](https://mlsanity.com/paper/2106.07754/) (2021)
- [Promoting Counterfactual Robustness through Diversity](https://mlsanity.com/paper/2312.06564/) (2023)
- [Efficient XAI Techniques: A Taxonomic Survey](https://mlsanity.com/paper/2302.03225/) (2023)
- [Achieving Diversity in Counterfactual Explanations: a Review and Discussion](https://mlsanity.com/paper/2305.05840/) (2023)
- [GAM Coach: Towards Interactive and User-centered Algorithmic Recourse](https://mlsanity.com/paper/2302.14165/) (2023)
- [Generating collective counterfactual explanations in score-based classification via mathematical optimization](https://mlsanity.com/paper/2310.12822/) (2023)
- [Interval Abstractions for Robust Counterfactual Explanations](https://mlsanity.com/paper/2404.13736/) (2024)
- [Generating Likely Counterfactuals Using Sum-Product Networks](https://mlsanity.com/paper/2401.14086/) (2024)
- [RobustX: Robust Counterfactual Explanations Made Easy](https://mlsanity.com/paper/2502.13751/) (2025)
- [FETA: Fairness Enforced Verifying, Training, and Predicting Algorithms for Neural Networks](https://mlsanity.com/paper/2206.00553/) (2022)
- [ElliCE: Efficient and Provably Robust Algorithmic Recourse via the Rashomon Sets](https://mlsanity.com/paper/2602.07674/) (2026)
- [Principled Diverse Counterfactuals in Multilinear Models](https://mlsanity.com/paper/2201.06467/) (2022)
- [Understanding User Preferences in Explainable Artificial Intelligence: A Survey and a Mapping Function Proposal](https://mlsanity.com/paper/2302.03180/) (2023)
- [Finding Optimal Diverse Feature Sets with Alternative Feature Selection](https://mlsanity.com/paper/2307.11607/) (2023)
- [Using Constraints to Discover Sparse and Alternative Subgroup Descriptions](https://mlsanity.com/paper/2406.01411/) (2024)
- [Out-of-Distribution Detection using Counterfactual Distance](https://mlsanity.com/paper/2508.10148/) (2025)
- [Synthesising Counterfactual Explanations via Label-Conditional Gaussian Mixture Variational Autoencoders](https://mlsanity.com/paper/2510.04855/) (2025)
- [Evaluating Counterfactual Explanation Methods on Incomplete Inputs](https://mlsanity.com/paper/2604.08004/) (2026)

## Abstract (arXiv)

Counterfactual explanations (CFE) are being widely used to explain algorithmic decisions, especially in consequential decision-making contexts (e.g., loan approval or pretrial bail). In this context, CFEs aim to provide individuals affected by an algorithmic decision with the most similar individual (i.e., nearest individual) with a different outcome. However, while an increasing number of works propose algorithms to compute CFEs, such approaches either lack in optimality of distance (i.e., they do not return the nearest individual) and perfect coverage (i.e., they do not provide a CFE for all individuals); or they cannot handle complex models, such as neural networks. In this work, we provide a framework based on Mixed-Integer Programming (MIP) to compute nearest counterfactual explanations with provable guarantees and with runtimes comparable to gradient-based approaches. Our experiments on the Adult, COMPAS, and Credit datasets show that, in contrast with previous methods, our approach allows for efficiently computing diverse CFEs with both distance guarantees and perfect coverage.