# A Query-Optimal Algorithm for Finding Counterfactuals

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 54 references that are in the map.
- First posted on arXiv 14 Jul 2022.

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

- [A Unified Approach to Interpreting Model Predictions](https://mlsanity.com/paper/1705.07874/) (2017)
- ["Why Should I Trust You?": Explaining the Predictions of Any Classifier](https://mlsanity.com/paper/1602.04938/) (2016)
- [Deep Inside Convolutional Networks: Visualising Image Classification Models and Saliency Maps](https://mlsanity.com/paper/1312.6034/) (2013)
- [Understanding Black-box Predictions via Influence Functions](https://mlsanity.com/paper/1703.04730/) (2017)
- [Counterfactual Explanations without Opening the Black Box: Automated Decisions and the GDPR](https://mlsanity.com/paper/1711.00399/) (2017)
- [Explaining Machine Learning Classifiers through Diverse Counterfactual Explanations](https://mlsanity.com/paper/1905.07697/) (2019)
- [Actionable Recourse in Linear Classification](https://mlsanity.com/paper/1809.06514/) (2018)
- [Model-Agnostic Counterfactual Explanations for Consequential Decisions](https://mlsanity.com/paper/1905.11190/) (2019)
- [Efficient Search for Diverse Coherent Explanations](https://mlsanity.com/paper/1901.04909/) (2019)
- [Robust and Stable Black Box Explanations](https://mlsanity.com/paper/2011.06169/) (2020)
- [Interpretability via Model Extraction](https://mlsanity.com/paper/1706.09773/) (2017)
- [Born-Again Tree Ensembles](https://mlsanity.com/paper/2003.11132/) (2020)
- [Provably efficient, succinct, and precise explanations](https://mlsanity.com/paper/2111.01576/) (2021)
- [Interpreting Models via Single Tree Approximation](https://mlsanity.com/paper/1610.09036/) (2016)
- [Estimating Learnability in the Sublinear Data Regime](https://mlsanity.com/paper/1805.01626/) (2018)
- [Active Tolerant Testing](https://mlsanity.com/paper/1711.00388/) (2017)
- [Sublinear Optimal Policy Value Estimation in Contextual Bandits](https://mlsanity.com/paper/1912.06111/) (2019)
- [The Query Complexity of Certification](https://mlsanity.com/paper/2201.07736/) (2022)
- [Active Local Learning](https://mlsanity.com/paper/2008.13374/) (2020)

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

- [Logic-Based Explainability in Machine Learning](https://mlsanity.com/paper/2211.00541/) (2022)
- [Robust Explanation Constraints for Neural Networks](https://mlsanity.com/paper/2212.08507/) (2022)
- [Local vs. Global Interpretability: A Computational Complexity Perspective](https://mlsanity.com/paper/2406.02981/) (2024)
- [Formal Mechanistic Interpretability: Automated Circuit Discovery with Provable Guarantees](https://mlsanity.com/paper/2602.16823/) (2026)
- [Additive Models Explained: A Computational Complexity Approach](https://mlsanity.com/paper/2510.21292/) (2025)
- [Unifying Formal Explanations: A Complexity-Theoretic Perspective](https://mlsanity.com/paper/2602.18160/) (2026)
- [Provably Explaining Neural Additive Models](https://mlsanity.com/paper/2602.17530/) (2026)

## Abstract (arXiv)

We design an algorithm for finding counterfactuals with strong theoretical guarantees on its performance. For any monotone model f : Xd → 0,1 and instance x^star, our algorithm makes [ S(f)O(Deltaf(x^star))· log d] queries to f and returns an sl optimal counterfactual for x^star: a nearest instance x' to x^star for which f(x')ne f(x^star). Here S(f) is the sensitivity of f, a discrete analogue of the Lipschitz constant, and Deltaf(x^star) is the distance from x^star to its nearest counterfactuals. The previous best known query complexity was d,O(Deltaf(x^star)), achievable by brute-force local search. We further prove a lower bound of S(f)Omega(Deltaf(x^star)) + Omega(log d) on the query complexity of any algorithm, thereby showing that the guarantees of our algorithm are essentially optimal.