On the Hardness of Computing Counterfactual and Semifactual Explanations in XAI

AI summary

Overview

Research area: Explainable AI (XAI) — specifically the computational complexity of counterfactual and semi-factual explanations — with connections to algorithmic complexity theory and AI regulation.

Technical level: Intermediate. The paper positions itself as a "comprehensive and accessible overview" of existing complexity results, but its new contributions are formal inapproximability theorems requiring familiarity with complexity classes such as P, NP, coNP, D^p and Σ₂^p.

Scope in one sentence: The paper surveys what is known about the computational complexity of generating counterfactual and semi-factual explanations across many model types, adds new proofs that approximate counterfactuals are also hard to compute for ReLU networks, additive tree models and kNN models, and discusses what this means for XAI research and AI regulation.

What This Paper Is About

Machine learning models are increasingly used in critical decisions, and regulators such as the EU AI Act give people subject to algorithmic decisions a right to an explanation. Counterfactual explanations describe how to change an input so the model's output changes, while semi-factual explanations describe changes that leave the output unchanged. The authors ask under what conditions these explanations can actually be computed efficiently, and they show that in many cases they cannot — and that even approximating them is hard.

Key Contributions

1. A comprehensive, accessible overview of the literature analyzing the computational complexity of counterfactual and semi-factual explanations, unifying work that is otherwise split across different research communities with different terminology and formalizations.

2. New inapproximability results for counterfactual explanations, extending limited prior work on approximation: for ReLU neural networks with one hidden layer, additive tree models, and kNN models, no polynomial-time approximation algorithm exists with a factor of 2^p(n) for any polynomial p(n), assuming P ≠ NP.

3. A structured complexity framework organized by classifier type and explanation type — including classic counterfactuals, enumeration of counterfactuals, robust counterfactuals, plausible counterfactuals, and global counterfactuals — as well as two semi-factual modeling approaches (Minimum Sufficient Reasons and Maximum Change Allowed).

4. A critical discussion of the implications of these hardness results for the XAI community, including whether optimal explanations are a reasonable goal and how complexity analysis should inform both method design and policy on regulating explanations.

Main Findings

• Counterfactuals are hard for most classifiers. The overview table shows NP-complete complexity for classic single counterfactuals on ReLU networks and kNN models, NP-complete for ensembles of perceptrons, ReLU networks and FBDDs, and NP-hard for additive trees. Global counterfactuals for arbitrary classifiers are NP-hard.

• A few cases are tractable. Classic counterfactuals are computable in polynomial time (PTIME) for perceptrons, decision trees (DT), FBDDs and monotonic classifiers; enumeration of classic counterfactuals is PTIME for decision trees and NP-complete for monotonic classifiers.

• Plausibility generally makes things harder. Adding a context indicator for plausible counterfactuals yields NP-complete results for perceptrons, ReLU networks and FBDDs, and, via the paper's Corollary 2, for ensembles of ReLU networks. Robustness to model changes is NP-hard for ReLU networks (and, via Corollary 1, for ensembles of ReLU networks).

• Semi-factuals follow a similar pattern. Under the Minimum Sufficient Reason formulation, semi-factuals are PTIME for monotonic classifiers, perceptrons, extended linear models, decision trees and FBDDs under the MCA formulation, but Σ₂^p-complete for ReLU networks and ensembles of perceptrons, ReLU networks and FBDDs, NP-hard for decision lists and kNN, and D^p-complete for random forests.

• Enumeration of semi-factuals is largely unstudied. The paper notes that only Marques-Silva et al. (2021) proves that enumerating all possible Minimum Sufficient Reasons with polynomial-time delay is NP-complete.

• Prior approximation hardness existed only for one case. Weng et al. (2018) showed that unless NP = P, no polynomial-time (1−o(1)) ln n-approximation algorithm exists for the Minimum Change Required problem with θ = ℓ₁ for ReLU networks, where n is the number of neurons.

• New inapproximability results (Theorems 1–3). If P ≠ NP, there is no polynomial-time 2^p(n)-approximation algorithm for the WACHTER-CFE problem for: (1) ReLU neural networks with n nodes and one hidden layer, (2) additive tree models with a total of n nodes (restricted to forests of binary decision trees where the aggregated response is the average of tree outputs), and (3) kNN models of size n.

• The inapproximability holds even for exponential factors. The factor 2^p(n) means approximate counterfactuals cannot be computed within any exponential-in-n factor of optimal in polynomial time, under the stated assumption.

• Scope of the new results. They apply to binary/categorical inputs (𝒳 = {0,1}^d), squared-error loss, and a cost function θ bounded above by a polynomial q(n); the operator ⊕ can be the xor operator, so the problem becomes minimizing the number of bits flipped.

Methodology in Plain English

The authors first build a common vocabulary: they define the classic counterfactual explanation as an optimization problem over a cost function subject to the model output changing, distinguish it from the single-objective "Wachter" formulation, and translate these into decision problems (the Minimum Change Required formulation) and counting/optimization variants. They then survey the existing complexity literature and tabulate the results by classifier type and explanation type, including two corollaries they derive for ensembles. For the new results, they define the WACHTER-CFE problem, restrict inputs to binary vectors, and construct reduction proofs based on 3-SAT — a standard proof strategy for showing a problem is hard — to show that no polynomial-time algorithm can approximate the optimum within a factor of 2^p(n) for the three model families. Full proofs are given in Appendix A.2.

Why This Matters

The paper argues that complexity analysis should be part of how the XAI community evaluates explanation methods, since an explanation type can have appealing properties yet be infeasible to compute. It also connects technical hardness to policy: if explanations are computationally hard in many settings, laws and regulations requiring explainability may have practical feasibility limits.

Real-world applications affected:

• Attrition and business analytics — domains where categorical features dominate and the paper's binary-input hardness results directly apply.

• Credit, hiring or other high-stakes decisions — where counterfactual recourse (how to change an unfavorable outcome) is requested and regulators demand explanations.

• Model selection — choosing classifier types whose explanations are tractable in a given domain, guided by the complexity tables.

• Tooling and heuristics — methods such as gradient-based or evolutionary approaches compute feasible but not necessarily optimal explanations; the results explain why optimality guarantees are often out of reach.

Industry relevance: practitioners using popular state-of-the-art explanation tooling (for example, evolutionary methods such as DiCE) cannot expect optimal, or even "good" approximations of, counterfactuals and semi-factuals in categorical scenarios. Decision makers can use the paper's overview to judge whether counterfactual or semi-factual explanations are appropriate for a given application.

Future Directions

• Average-case performance analysis, rather than worst-case complexity, as a better match to how explanations behave in practice.

• Less strict formulations that explicitly allow non-optimal solutions, aligning theory with the heuristics used today (which often land in local minima but remain useful).

• Continuous features, where the paper says formal statements for general non-convex scenarios remain an open problem, leaving it unclear how optimal gradient-based explanations are.

• Additional explanation properties, such as other plausibility formulations (e.g., causal plausibility), robustness, diversity, fairness and global counterfactuals, whose effect on computational complexity is stated as unknown.

• Enumeration of semi-factual explanations, which the paper notes has not been studied except for the polynomial-delay result for Minimum Sufficient Reasons.

Target Audience

XAI researchers and method designers who need to know which explanation types are feasible for which models; complexity theorists interested in social choice and ML applications; and policymakers and regulators — including those working on the EU AI Act's right to an explanation — who need to understand the practical limits of mandating explainable AI. Practitioners selecting models and explanation methods for categorical, real-world data such as attrition or business analytics will also find the complexity tables directly useful.

Authors’ 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.