The Computational Cost of Explanation Minimality

30 concepts20 papers1 proposal

When an artificial intelligence denies a loan application, diagnoses a patient, or derives a complex logical conclusion, users naturally ask: Why?

Providing a complete trace of a system's internal mechanics is rarely helpful. As Chunxi Ji observes in On the Computation of Necessary and Sufficient Explanations, human users require the shortest possible sets of features to ensure the information remains cognitively manageable. We seek parsimony—the absolute minimum number of reasons required to guarantee an outcome.

However, a profound computational paradox underlies this requirement. Across machine learning, logic programming, and database systems, researchers have uncovered a shared mathematical reality: finding a valid explanation can be relatively straightforward, but proving that an explanation is minimal is exceptionally difficult. Forcing an explanation to be concise introduces a severe computational bottleneck, frequently elevating the problem into much higher complexity classes.

Why Minimality Explodes Complexity

To understand why brevity is so expensive, consider the difference between verification and optimization. If a system proposes an explanation for an event, verifying its validity simply requires checking if the proposed causes entail the effect.

However, verifying minimality requires proving a negative: you must demonstrate that no smaller subset of those causes could produce the same effect.

Valid Explanation Check:
[Cause A + Cause B + Cause C] ===> Does this trigger the effect? (Often Easy)

Minimal Explanation Check:
Does [Cause A + Cause B] trigger it? 
Does [Cause B + Cause C] trigger it? 
Does [Cause A + Cause C] trigger it? ... (Requires checking all subsets)

This subset-minimality check introduces an extra layer of quantification. In database query answering under existential rules, the authors of Query Answer Explanations under Existential Rules show that this requirement causes a sharp complexity jump. While finding a query answer might reside in one complexity class, confirming that a specific subset of facts constitutes a minimal justification requires moving up to a harder class (such as $\text{DP}$), because the algorithm must simultaneously verify entailment and ensure no smaller subset exists.

A similar bottleneck appears in automated planning and model reconciliation. When a robot explains its plan to a human by updating the human's mental model, providing a massive, complete description of the environment is computationally trivial. However, Sarath Sreedharan et al. demonstrate in On the Computational Complexity of Model Reconciliations that finding the smallest set of model updates is $\Sigma^P_2$-complete. The computational hardness is driven entirely by the requirement for minimality; the system must search through the vast space of possible updates while verifying that no shorter alternative plan becomes viable for the observer.

The Wall in Machine Learning Interpretability

This mathematical barrier is highly pronounced in modern explainable AI (XAI), where algorithms attempt to explain black-box neural networks by identifying the smallest subset of input features that preserves a prediction.

If a classifier relies on non-linear interactions, features cannot be evaluated in isolation. To find a globally minimal explanation, an algorithm must navigate an exponential combinatorial explosion of feature subsets. Stephan Waeldchen et al. mapped this boundary in The Computational Complexity of Understanding Binary Classifier Decisions, proving that finding the exact minimal feature set is $\text{NP}^{\text{PP}}$-complete. Crucially, the authors established that even approximating the size of the smallest explanation is NP-hard. This means popular heuristic interpretability tools cannot guarantee that the explanations they output are near-optimal; they may routinely produce explanations that are unnecessarily bloated or redundant.

This tension between speed and conciseness manifests across several XAI frameworks:

  • Formal Verification: In VeriX: Towards Verified Explainability of Deep Neural Networks, Haoze Wu et al. leverage constraint solvers to generate mathematically sound explanations, but note that the search for a globally minimal set of influential features forces the system into solving NP-complete problems.
  • Local Anchors: Sebastian Ordyniak et al. study the task of finding the smallest "anchor"—a concise local explanation that maintains high coverage across similar data points—in The Parameterized Complexity of Finding Concise Local Explanations. They confirm that the mathematical task of identifying the absolute smallest subset of anchoring features is generally NP-hard.
  • Knowledge Compilation: To bypass these run-time costs, Adnan Darwiche suggests in Logic for Explainable AI compiling neural networks into symbolic logical functions. Yet, the underlying challenge remains: without efficient ways to extract minimal prime implicants, explanations remain too complex for human comprehension.

The Deep Roots in Symbolic Reasoning

The computational penalty of minimality is not a new artifact of deep learning; it is a foundational characteristic of symbolic logic and automated reasoning.

In propositional abduction—the process of finding the best logical hypothesis to explain an observation—the search space is notoriously difficult. Gustav Nordh et al. show in Propositional Abduction is Almost Always Hard that while determining whether any explanation exists can sometimes be managed, selecting an optimal explanation based on minimality criteria is almost always intractable. The optimization layer required to enforce subset-minimality is exceptionally difficult to encode efficiently in standard decision procedures, as noted by Andreas Pfandler et al. in Backdoors to Abduction.

When reasoning moves to non-monotonic frameworks—where adding new information can invalidate previous conclusions—the cost of parsimony escalates further. Thomas Eiter et al. demonstrated in Semantics and Complexity of Abduction from Default Theories that enforcing minimality in default logic adds an entire level of computational complexity. This occurs because verifying that no subset of the explanation works requires testing the explanation's validity across multiple potential world states.

This exact bottleneck reappears across diverse symbolic paradigms:

The Interpretability Paradox

The collective evidence across these distinct fields points to a fundamental Interpretability Paradox:

$$\text{Human Readability} \propto \frac{1}{\text{Explanation Size}}$$

$$\text{Algorithmic Complexity} \propto \frac{1}{\text{Explanation Size}}$$

The very characteristic that makes an explanation valuable to a human—its brevity—is precisely what makes it computationally expensive for a machine to discover. As systems become more complex, balancing the cognitive limits of the human user against the mathematical limits of the algorithm remains one of the most significant challenges in explainable AI.

Key Foundational Work

Efficient Diagnosis of Multiple Disorders Based on a Symptom Clustering Approach (1990) — contributed 1 concept elements to this direction.
Computational Complexity of Hypothesis Assembly (1987) — 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_explanation_minimality_complexity_cb3d75e7,
  title = {explanation minimality complexity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/explanation-minimality-complexity/rdr_cb3d75e7213049f9968fd23dcb89f008},
  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_explanation_minimality_complexity_cb3d75e7_v1,
  title = {explanation minimality complexity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/explanation-minimality-complexity/rdr_cb3d75e7213049f9968fd23dcb89f008/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