mlsanityData to 7 Oct 2026

On the Hardness of Computing Counterfactual and Semifactual Explanations in XAI

arXiv 2601.09455 ↗First posted 14 Jan 2026cs.LG cs.AIcited by 0

Not on the map. Why?

Abstract (arXiv)

Providing clear explanations to the choices of machine learning models is essential for these models to be deployed in crucial applications. Counterfactual and semi-factual explanations have emerged as two mechanisms for providing users with insights into the outputs of their models. We provide an overview of the computational complexity results in the literature for generating these explanations, finding that in many cases, generating explanations is computationally hard. We strengthen the argument for this considerably by further contributing our own inapproximability results showing that not only are explanations often hard to generate, but under certain assumptions, they are also hard to approximate. We discuss the implications of these complexity results for the XAI community and for policymakers seeking to regulate explanations in AI.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 28 of its 47 references that are in the map. First posted on arXiv 14 Jan 2026.

Builds on

28 of 47 references.

References · 28

  1. 2017Counterfactual Explanations without Opening the Black Box: Automated Decisions and the GDPRcited by 1,086
  2. 2019Explaining Machine Learning Classifiers through Diverse Counterfactual Explanationscited by 612
  3. 2018Towards Fast Computation of Certified Robustness for ReLU Networkscited by 254
  4. 2019FACE: Feasible and Actionable Counterfactual Explanationscited by 232
  5. 2019Model-Agnostic Counterfactual Explanations for Consequential Decisionscited by 204
  6. 2020Multi-Objective Counterfactual Explanationscited by 157
  7. 2020Model Interpretability through the Lens of Computational Complexitycited by 75
  8. 2020On the Fairness of Causal Algorithmic Recoursecited by 69
  9. 2020On Generating Plausible Counterfactual and Semi-Factual Explanations for Deep Learningcited by 60
  10. 2021On Explaining Random Forests with SATcited by 57
  11. 2020Explaining Naive Bayes and Other Linear Classifiers with Polynomial Time and Delaycited by 56
  12. 2020On Explaining Decision Treescited by 49
16 more
  1. 2020Decisions, Counterfactual Explanations and Strategic Behaviorcited by 44
  2. 2021Evaluating Robustness of Counterfactual Explanationscited by 41
  3. 2021SAT-Based Rigorous Explanations for Decision Listscited by 40
  4. 2021On Efficiently Explaining Graph-Based Classifierscited by 37
  5. 2020Convex Density Constraints for Computing Plausible Counterfactual Explanationscited by 32
  6. 2023Even if Explanations: Prior Work, Desiderata & Benchmarks for Semi-Factual XAIcited by 20
  7. 2021A Few Good Counterfactuals: Generating Interpretable, Plausible and Diverse Counterfactual Explanationscited by 19
  8. 2020FaiR-N: Fair and Robust Neural Networks for Structured Datacited by 15
  9. 2022"Even if ..." -- Diverse Semifactual Explanations of Rejectcited by 11
  10. 2024Hard to Explain: On the Computational Hardness of In-Distribution Model Interpretationcited by 11
  11. 2025Explaining k-Nearest Neighbors: Abductive and Counterfactual Explanationscited by 10
  12. 2022"Explain it in the Same Way!" -- Model-Agnostic Group Fairness of Counterfactual Explanationscited by 9
  13. 2023The Utility of "Even if..." Semifactual Explanation to Optimise Positive Outcomescited by 8
  14. 2024Rigorous Probabilistic Guarantees for Robust Counterfactual Explanationscited by 6
  15. 2024Even-Ifs From If-Onlys: Are the Best Semi-Factual Explanations Found Using Counterfactuals As Guides?cited by 5
  16. 2024Even-if Explanations: Formal Foundations, Priorities and Complexitycited by 4

Built on by

Not cited yet.