Minimal Sufficient Explanations

145 concepts100 papers1 proposal

Imagine a medical AI diagnoses a patient with a rare disease. Popular explanation methods like LIME or SHAP might provide a heatmap highlighting various symptoms that influenced the decision. But do these symptoms guarantee the diagnosis? If you change other unrelated symptoms, will the model flip its decision?

Traditional heuristic attribution methods can highlight features that are influential but do not guarantee that the highlighted features are actually sufficient to justify a model's decision, as noted by Carter et al.. To bridge this gap, a rigorous branch of Explainable AI (XAI) focuses on minimal sufficient explanations—also known as abductive explanations or prime implicants. Instead of asking "how much did each feature contribute?", this paradigm asks: What is the smallest set of features that completely locks in the prediction?

The Core Intuition: The "Lock-In" Condition

To understand why minimal sufficient explanations work, it helps to shift from thinking about statistical correlations to thinking about logical guarantees.

An abductive explanation identifies a subset-minimal collection of feature values that logically entails a specific classification, ensuring the prediction remains constant regardless of how other input variables change (Ignatiev et al.).

[ Full Input Features ] ---> Model Prediction: "Class A"
          |
  (Isolate Minimal Subset)
          |
          v
[ Fixed Core Features ] + [ Any Random Perturbations ] ---> Guaranteed Prediction: "Class A"

If a model uses a minimal sufficient subset, you can completely randomize, mask, or perturb all other features outside of this subset, and the model's output is mathematically guaranteed to stay the same. This approach filters out redundant or irrelevant background noise to produce a compact, logical rule that explains the model's decision-making process for a given instance.

This concept spans both empirical and formal methodologies. In natural language processing, the principle of sufficiency was leveraged by Lei et al. to extract short, coherent text snippets ("rationales") that allow a model to maintain high predictive accuracy when presented in isolation. In symbolic logic, a decision's explanation can be formally defined as a "complete reason," which Marquis et al. describe as the weakest logical formula that triggers the same outcome.

From Empirical Subsets to Formal Proofs

How do we actually find these minimal subsets? The research direction splits into two main flavors: empirical optimization and formal verification.

Empirical Optimization

In complex, deep black-box models, researchers often find these subsets by treating the problem as a combinatorial search. For instance, Carter et al. systematically reduce the input until only the most critical statistical signals remain, identifying the smallest possible subset of input features that allows a model to maintain a specific prediction threshold.

Formal XAI

For high-stakes applications where statistical approximations are not enough, Formal XAI leverages automated reasoners (like SAT solvers) to provide mathematically sound proofs of sufficiency (Marques-Silva et al.).

As shown in the context of constraint-based explanations, a simple greedy iterative removal process can be used to find a subset-minimal explanation (Ignatiev). The algorithm starts with the full set of features and systematically drops them one by one:

  1. Drop a feature from the current explanation set.
  2. Check via a solver if the prediction remains invariant for all possible values of the remaining unconstrained features.
  3. If the prediction is guaranteed to stay the same, the dropped feature was redundant, and it is permanently removed.
  4. If the prediction can change, the feature is vital and must be kept.

The resulting set is a prime implicant, meaning no further features can be removed without potentially changing the model's output.

Taming the Computational Complexity

Finding these exact minimal sets is incredibly difficult. Waeldchen et al. investigated the computational complexity of this task and proved that finding the smallest subset of input features that guarantees a classifier's decision is $\text{NP}^{\text{PP}}$-complete. Even approximating the size of this explanation is NP-hard.

To bypass this theoretical bottleneck, researchers employ two main strategies:

1. Tractable Logical Circuits

Instead of reasoning over a raw neural network directly, researchers compile or transform classifiers into specialized symbolic representations. By encoding models as Binary Decision Diagrams (BDDs) (Zhang et al.), Ordered Decision Diagrams (ODDs) (Shih et al.), or d-DNNFs (Huang et al.), the internal structure becomes transparent. For example, Huang et al. demonstrated that for classifiers represented as d-DNNFs, subset-minimal explanations can be derived through a greedy drop-one algorithm in polynomial time.

2. Exploiting Model Monotonicity

When a classifier exhibits monotonic behavior—meaning additional positive features consistently increase the likelihood of a positive outcome—the search space collapses dramatically. As shown by Shih et al., in monotone classifiers, the smallest set of active features responsible for a decision is equivalent to the shortest set of features that locks in that decision. This mathematical alignment allows model-agnostic, polynomial-time algorithms to compute formal explanations without exponential complexity (Marques-Silva et al.).

Quantifying Importance via Formal Feature Attribution

A single classification decision often stems from multiple independent sets of sufficient features rather than a single unique cause (Huang et al.). If a model can output "Class A" based on either feature set $\{X, Y\}$ or feature set $\{Y, Z\}$, how do we communicate this to a user?

This challenge led to the development of Formal Feature Attribution (FFA). Introduced by Ignatiev et al., FFA quantifies feature importance by calculating the frequency with which a specific feature appears across all minimal sets of features sufficient to guarantee a model's prediction.

To make this practical, Yu et al. introduced anytime approximation algorithms that intelligently switch between explanation strategies to compute these frequencies quickly. This provides a mathematically rigorous ranking grounded in formal logic rather than statistical sampling, ensuring that features are scored based on their logical necessity to the underlying decision boundary.

Contrastive Extensions

Focusing on minimal sufficiency naturally opens the door to contrastive explanations. By understanding what is minimally sufficient to keep a prediction, we can also understand what is required to change it.

For example, the Contrastive Explanations Method (CEM) developed by Dhurandhar et al. splits an explanation into two parts:

  • Pertinent Positives: The minimal sufficient set of features that must be present to maintain the model's original classification.
  • Pertinent Negatives: The minimal set of features that must be necessarily absent to prevent the prediction from flipping to a close alternative.

By framing interpretability around the strict conditions required to lock in or alter a decision, minimal sufficient explanations provide a mathematically sound alternative to heuristic visualizations, giving users verifiable guarantees of why a model behaves the way it does.

Key Foundational Work

Rationalizing Neural Predictions (2016) — contributed 2 concept elements to this direction.
Rationalizing Neural Predictions (2016) — contributed 2 concept elements to this direction.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 102 papers
  2. Version 1 · 2026-10-04 · 59 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_prime_implicant_explanation_5bb46dfe,
  title = {prime implicant explanation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/prime-implicant-explanation/rdr_5bb46dfe9a354eb6862423e3f1f065da},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 2, frozen text):

@misc{lacuna_prime_implicant_explanation_5bb46dfe_v2,
  title = {prime implicant explanation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/prime-implicant-explanation/rdr_5bb46dfe9a354eb6862423e3f1f065da/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake