mlsanityData to 7 Oct 2026

A Query-Optimal Algorithm for Finding Counterfactuals

arXiv 2207.07072 ↗First posted 14 Jul 2022cs.DS cs.LGcited by 7

Not on the map. Why?

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.

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

Builds on

19 of 54 references.

References · 19

  1. 2017A Unified Approach to Interpreting Model Predictionscited by 6,488
  2. 2016"Why Should I Trust You?": Explaining the Predictions of Any Classifiercited by 5,040
  3. 2013Deep Inside Convolutional Networks: Visualising Image Classification Models and Saliency Mapscited by 2,348
  4. 2017Understanding Black-box Predictions via Influence Functionscited by 1,714
  5. 2017Counterfactual Explanations without Opening the Black Box: Automated Decisions and the GDPRcited by 1,086
  6. 2019Explaining Machine Learning Classifiers through Diverse Counterfactual Explanationscited by 612
  7. 2018Actionable Recourse in Linear Classificationcited by 327
  8. 2019Model-Agnostic Counterfactual Explanations for Consequential Decisionscited by 204
  9. 2019Efficient Search for Diverse Coherent Explanationscited by 111
  10. 2020Robust and Stable Black Box Explanationscited by 47
  11. 2017Interpretability via Model Extractioncited by 40
  12. 2020Born-Again Tree Ensemblescited by 38
7 more
  1. 2021Provably efficient, succinct, and precise explanationscited by 32
  2. 2016Interpreting Models via Single Tree Approximationcited by 17
  3. 2018Estimating Learnability in the Sublinear Data Regimecited by 10
  4. 2017Active Tolerant Testingcited by 4
  5. 2019Sublinear Optimal Policy Value Estimation in Contextual Banditscited by 4
  6. 2022The Query Complexity of Certificationcited by 3
  7. 2020Active Local Learningcited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 2; 2023: 0; 2024: 1; 2025: 1; 2026: 3.

7 papers.

  1. 2022Logic-Based Explainability in Machine Learningcited by 47
  2. 2022Robust Explanation Constraints for Neural Networkscited by 23
  3. 2024Local vs. Global Interpretability: A Computational Complexity Perspectivecited by 23
  4. 2026Formal Mechanistic Interpretability: Automated Circuit Discovery with Provable Guaranteescited by 10
  5. 2025Additive Models Explained: A Computational Complexity Approachcited by 3
  6. 2026Provably Explaining Neural Additive Modelscited by 1
  7. 2026Unifying Formal Explanations: A Complexity-Theoretic Perspectivecited by 1