Most popular methods for explaining machine learning models, such as SHAP or LIME, rely on local approximations or statistical averages. While these "heuristic" methods produce intuitive heatmaps, they often lack mathematical guarantees. A heatmap might highlight a feature that is correlated with a prediction, but it cannot tell you if that feature is sufficient to trigger the prediction on its own.
A growing body of research, often termed Formal XAI, shifts the focus from feature importance scores to logical sufficiency. Instead of asking "How much did this pixel contribute?", these methods ask: "What is the smallest set of features that, if held constant, guarantees the model will make the same decision?"
The Intuition of Sufficiency
The core idea is to treat a machine learning model as a formal logical function. In this view, an explanation is a Sufficient Input Subset (SIS)—a minimal "rationale" that justifies a decision. Jonas Mueller and Brandon Carter 0001 define these as the smallest possible subsets of features that trigger a model's prediction above a certain threshold, even if all other features are removed or randomized.
This approach addresses a major flaw in traditional attribution: a feature can be "important" in a statistical sense but logically irrelevant to a specific instance. For example, Xuanxiang Huang and João Marques-Silva 0001 have demonstrated that in complex classifiers, game-theoretic methods like SHAP can assign high importance to features that have zero logical impact on the actual decision, a phenomenon they use to refute the reliability of Shapley values for high-stakes explainability.
Abductive Reasoning and Prime Implicants
To find these sufficient subsets rigorously, researchers use abductive reasoning. In logic, an abductive explanation is a "prime implicant"—a minimal set of conditions that logically entails a conclusion.
Alexey Ignatiev, Nina Narodytska, and João Marques-Silva 0001 introduced a framework that uses automated reasoners (like SAT solvers) to compute these prime implicants for ML models. If a subset of features is an abductive explanation, it serves as a "certificate" of the prediction: as long as those features remain unchanged, the model's output is mathematically guaranteed to stay the same, regardless of any noise or changes in the "irrelevant" features.
This creates a clear distinction between:
- Necessity: Must this feature be part of every possible explanation?
- Relevancy: Could this feature be part of at least one explanation?
By answering these questions, as explored in Feature Necessity & Relevancy in ML Classifier Explanations, we gain a much deeper understanding of the model's internal "logic" than a simple saliency map could provide.
Bridging the Gap to Human Interpretability
While formal explanations are rigorous, they can be difficult for humans to digest if there are many possible sufficient subsets. Recent work attempts to bridge this gap by aggregating these logical proofs back into feature scores.
For instance, Formal Feature Attribution (FFA) defines a feature's importance as the proportion of all minimal sufficient sets that include it. Similarly, Gagan Biradar and Yacine Izza propose axiomatic aggregations of abductive explanations to create robust importance scores that are grounded in logic rather than statistical sampling.
Scaling to Complex Models
The primary challenge of Formal XAI is computational complexity; finding the absolute smallest sufficient subset is often NP-hard. However, researchers are finding ways to scale these ideas:
- Model-Specific Solvers: Tools like PyXAI leverage the internal structure of decision trees and random forests to compute exact explanations efficiently.
- Abstraction-Refinement: Shahaf Bassan and Guy Katz use an abstraction-refinement framework to find explanations on simplified versions of neural networks before refining them, significantly speeding up the process.
- Differentiable Masking: In computer vision, methods like Vision DiffMask use differentiable patch masking to approximate the minimal subset of an image required for a Vision Transformer to maintain its prediction.
By moving toward logical sufficiency, the field is transitioning from "plausible" explanations—which look good to humans but might be unfaithful to the model—to "provable" explanations that offer the rigorous guarantees required for trustworthy AI.