On the Hardness of Computing Counterfactual and Semi-factual Explanations in XAI

André Artelt, Martin Olsen, Kevin Tierney

TL;DR

This paper dives into the computational complexity of generating counterfactual and semi-factual explanations in Explainable AI (XAI). It reveals that for many common machine learning models, these explanations are computationally "hard" to produce, and even harder to approximate. This has significant implications for the practical deployment of XAI and the regulation of AI systems.

What Problem Does This Paper Address?

As machine learning models become more prevalent in critical applications, the need for clear explanations of their decisions is paramount. Counterfactual and semi-factual explanations are two popular methods for achieving this, offering insights into how input changes affect model outputs. However, the computational cost of generating these explanations has been largely unexplored. This paper aims to bridge this gap by providing a comprehensive overview of existing complexity results and introducing new findings on the difficulty of approximating these explanations, highlighting a potential bottleneck for widespread XAI adoption.

Methods

The authors provide a survey of existing literature on the computational complexity of counterfactual and semi-factual explanations for various machine learning models, including perceptrons, ReLU networks, and tree-based models. They categorize these explanations based on their formalizations (e.g., classic, robust, plausible) and the underlying models. A significant contribution is the introduction of new inapproximability results. These results demonstrate that for certain models (ReLU networks, additive tree models, kNN models), it's not just hard to find the optimal explanation, but also computationally infeasible to find a good enough approximation within polynomial time, assuming P ≠ NP. This is achieved through reductions from the 3-SAT problem, a standard technique in computational complexity theory.

Datasets

Not discussed in the paper. The paper focuses on theoretical complexity analysis rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Explanations are often computationally expensive: The paper consolidates existing research to show that generating counterfactual and semi-factual explanations is frequently NP-hard or NP-complete for many common ML models.
  • Approximation is also hard: The authors introduce novel inapproximability results, showing that even finding approximate explanations is computationally intractable for certain models, posing a significant challenge for practical XAI.
  • Implications for regulation: The computational hardness of explanations has direct consequences for regulatory efforts like the EU AI Act, which mandates explanations. If explanations are too hard to compute, it raises questions about the feasibility of such regulations.
  • Model choice matters: The complexity of generating explanations varies significantly depending on the ML model used. Simpler models like monotonic classifiers or decision trees tend to be more computationally tractable for explanations.
  • The "best" explanation might be unattainable: The findings suggest that for many real-world scenarios, aiming for the absolute "best" or "optimal" counterfactual/semi-factual explanation might be an unrealistic goal.

Key Results

The paper presents a comprehensive overview of computational complexity results for counterfactual and semi-factual explanations, summarized in Tables 1 and 2. Key findings include:

  • Counterfactuals: For ensembles of ReLU networks, robust counterfactuals are NP-hard, and plausible counterfactuals are NP-complete. For single models, many are NP-hard or NP-complete, with exceptions for monotonic classifiers and decision trees.
  • Semi-factuals: Similar to counterfactuals, semi-factual explanations are computationally hard for most models, with exceptions for linear models and decision trees.
  • Inapproximability: The paper proves that for ReLU networks, additive tree models, and kNN models, there is no polynomial-time algorithm that can guarantee a 2p(n)-approximation for the WACHTER-CFE problem (a general form of counterfactual explanation) for any polynomial p(n), assuming P ≠ NP.

Limitations and Future Work

  • Continuous Features: The current analysis primarily focuses on discrete or binary input features. The complexity of explanations for models with continuous features remains largely unexplored and is a significant area for future work.
  • Causal Explanations: The paper's analysis is limited to non-causal explanations. The computational complexity of causal counterfactual explanations, which are crucial for real-world actionability, is also an open area.
  • Heuristic and Approximation Methods: While exact explanations might be infeasible, the paper acknowledges the practical use of heuristic and approximation methods. Future work should investigate the quality and formal guarantees of these methods, especially for continuous features.
  • Average-Case Analysis: The current complexity analysis is worst-case. Exploring average-case performance and less strict formulations of explanations could bridge the gap between theoretical findings and practical scenarios.
  • Semi-factual Explanations: The research on semi-factual explanations, both in terms of formalization and complexity, is less developed compared to counterfactuals and warrants more attention.

Summary updated

Abstract

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.
BibTeX
@article{artelt2025hardness,
  author = {André Artelt and Martin Olsen and Kevin Tierney},
  title = {{On the Hardness of Computing Counterfactual and Semi-factual Explanations in XAI}},
  journal = {Accepted by TMLR},
  year = {2025},
  url = {https://openreview.net/forum?id=aELzBw0q1O},
}
Figure