The Computational Complexity of Formal Minimal Explanations

18 concepts16 papers1 proposal

When we ask why a complex machine learning model made a specific prediction, popular post-hoc tools like LIME or SHAP offer a "best guess" by assigning heuristic importance scores to input features. However, as Min Wu et al. observe in their work on VeriX: Towards Verified Explainability of Deep Neural Networks, these heuristics provide no formal guarantees. In safety-critical domains like aviation or medicine, a guess is not enough. We need formal explanations—mathematically rigorous proofs that a specific set of features is entirely responsible for a model's decision.

This requirement has led to the study of sufficient reasons (or abductive explanations), pioneered by researchers like Alexey Ignatiev et al. in Abduction-Based Explanations for Machine Learning Models. A sufficient reason is a subset of input features whose current values are enough to completely lock in the model's prediction. No matter how you change the remaining, unchosen features, the output remains invariant.

To be useful to humans, these explanations must be as brief as possible. We want minimal explanations—either subset-minimal (no single feature can be removed without losing the guarantee) or cardinality-minimal (the absolute smallest set of features that works). But finding these minimal sets introduces a massive computational bottleneck.

The Combinatorial Explosion of Sufficiency

Why is finding a minimal explanation so hard? The difficulty stems from a nested mathematical challenge: to prove that a subset of features is a "sufficient reason," you must verify that the model's output is invariant across all possible assignments of the remaining features.

As Keyon Vafa et al. explain in Rationales for Sequential Predictions, this creates a daunting combinatorial optimization problem. For a model with $d$ features, searching through all possible feature combinations to find the absolute smallest subset is fundamentally NP-hard.

In fact, the problem often sits even higher on the polynomial hierarchy. Finding a cardinality-minimal explanation is frequently $\Sigma_2^p$-complete. This complexity arises because the task combines two competing quantifiers:

  1. Existential ($\exists$): Does there exist a small subset of features of size $k$?
  2. Universal ($\forall$): Such that for all possible counterfactual values of the excluded features, the prediction remains unchanged?

This $\Sigma_2^p$ complexity means that standard post-hoc search methods are prone to timing out or producing bloated, redundant results instead of truly minimal justifications, as detailed by Shahaf Bassan et al. in Explain Yourself, Briefly! Self-Explaining Neural Networks with Concise Sufficient Reasons. Even in models traditionally celebrated for their interpretability, such as decision trees, Alexander Kozachinskiy et al. proved in On Computing Probabilistic Explanations for Decision Trees that finding minimum-size probabilistic explanations is both NP-hard and highly resistant to approximation.

Post-Hoc Search Space (Exponential Explosion)
  ├── Subset 1: [Feature A] ─── Verify all variations of [B, C, D...] ❌ (Fails)
  ├── Subset 2: [Feature B, C] ─── Verify all variations of [A, D...]  ✅ (Sufficient)
  └── ... (Must evaluate up to 2^d combinations)

To make formal explainability practical, researchers have developed three main strategies: constraining the model's structure, over-approximating the search space via mathematical abstractions, or forcing the model to explain itself natively.

Taming Complexity via Model Structure

If computing minimal explanations for arbitrary black-box models is intractable, one solution is to restrict the mathematical structure of the classifier to collapse the verification space.

A prime example is the class of monotonic classifiers, where increasing an input feature can only move the output in a single direction. In Explanations for Monotonic Classifiers, João Marques-Silva 0001 et al. demonstrated that monotonicity allows the computation of formal explanations in polynomial time.

Monotonicity removes the need to check every combination of counterfactual values. Because the function's direction is predictable, the worst-case counterfactual is always located at the extreme boundary of the feature space. If the prediction holds at that single extreme boundary, it is mathematically guaranteed to hold everywhere else.

Monotonic Function Property:
  If f(x) is monotonic, the worst-case counterfactual is at the extreme boundary (x_max or x_min).
  Instead of checking the entire space, check the boundary:
  [Sufficient Feature Values] + [Extreme Boundary Values] ──> Prediction Holds? 
  If Yes ──> Proven for the entire continuous space in Polynomial Time.

Building on this insight, Bernardo Cuenca Grau et al. showed in Cardinality-Minimal Explanations for Monotonic Neural Networks that when neural networks are constrained to be monotonic and utilize continuous activation functions like ReLU, a fast greedy algorithm can find the absolute smallest (cardinality-minimal) explanations in polynomial time. Similar structural advantages have been uncovered for decision graphs by Xuanxiang Huang et al. in On Efficiently Explaining Graph-Based Classifiers, and for neural additive models by Shahaf Bassan et al. in Provably Explaining Neural Additive Models.

Algorithmic Accelerations: Abstraction and Bundling

When we cannot alter the underlying model architecture, we must change how we navigate and verify the feature space. Instead of evaluating features one by one, modern frameworks use over-approximation to rule out large swathes of features simultaneously.

In FAME: Formal Abstract Minimal Explanation for Neural Networks, Ryma Boumazouza et al. introduce abstract interpretation to formal explainability. Instead of checking individual, concrete feature vectors, the authors group feature values into intervals (abstract domains) and propagate these intervals through the network using GPU acceleration. If the resulting output interval does not cross the model's decision boundary, the entire region of space is proven safe in a single pass, allowing the algorithm to prune irrelevant features in large batches.

Concrete Traversal (Slow):
  Vector 1 ──> [Network] ──> Check Boundary
  Vector 2 ──> [Network] ──> Check Boundary

Abstract Interpretation (Fast):
  [Interval Range] ──> [Network] ──> [Output Range] ──> Does not cross boundary? 
                                                         (Prunes millions of vectors at once)

Similarly, in Towards Formal XAI: Formally Approximate Minimal Explanations of Neural Networks, Shahaf Bassan et al. group features into "bundles" and deploy parallel processing threads to simultaneously compute upper and lower bounds on the explanation size. By relaxing the search from individual features to structured groups, they achieve massive speedups. From a different perspective, Guy Blanc et al. prove in Provably efficient, succinct, and precise explanations that by framing the search for feature certificates as an "implicit decision tree learning" problem, one can adaptively query a black-box model to isolate small, highly accurate sets of features without triggering a computational explosion.

Relaxing the Definition of a Guarantee

Another way to bypass the $\Sigma_2^p$ complexity barrier is to relax what we accept as a "guarantee." Must an explanation satisfy every single mathematical corner case, or is a strong majority or high-probability threshold sufficient?

For ensemble models like Random Forests, finding a feature set that guarantees a prediction across every single tree is notoriously difficult. To resolve this, Gilles Audemard et al. introduced the concept of "majoritary reasons" in Trading Complexity for Sparsity in Random Forest Explanations. Instead of forcing a subset of features to satisfy the entire forest simultaneously, they search for features that satisfy a majority of the individual trees. This slight relaxation of logical rigor drops the computational complexity into a sweet spot that yields shorter, more readable explanations in a fraction of the time.

Shifting the Burden to the Architecture

Instead of treating explanation generation as an expensive post-hoc search problem over a fixed model, a final paradigm shifts this computational burden directly into the model's training phase.

To circumvent the inherent NP-hardness of post-hoc verification solvers, Shahaf Bassan et al. designed self-explaining neural networks in Explain Yourself, Briefly! Self-Explaining Neural Networks with Concise Sufficient Reasons. By embedding minimality constraints directly into the network's architecture and loss function, the model learns to natively output its own concise sufficient reasons during the standard forward pass.

Ultimately, whether through structural constraints, abstract mathematical shortcuts, or native architectural design, the field of formal XAI is systematically mapping out how to extract provably correct, human-comprehensible justifications from complex models without succumbing to combinatorial explosion.

Key Foundational Work

Abduction-Based Explanations for Machine Learning Models (2019) — contributed 2 concept elements to this direction.
Provably efficient, succinct, and precise explanations (2021) — contributed 1 concept elements to this direction.
Rationales for Sequential Predictions (2021) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_computational_complexity_of_minimal_expl_0c2a3574,
  title = {computational complexity of minimal explanations},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/computational-complexity-of-minimal-explanations/rdr_0c2a357486f143e6a1320328b4cd8864},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_computational_complexity_of_minimal_expl_0c2a3574_v1,
  title = {computational complexity of minimal explanations},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/computational-complexity-of-minimal-explanations/rdr_0c2a357486f143e6a1320328b4cd8864/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake