Most popular methods for explaining machine learning models, such as LIME or SHAP, rely on "heuristics"—statistical approximations that offer a best guess as to why a model made a decision. While intuitive, these methods lack mathematical rigor. They cannot guarantee that the features they highlight are actually sufficient to trigger the prediction, nor can they prove that the explanation will remain valid if the model is slightly retrained.
A growing body of research, led by figures like Alexey Ignatiev, João Marques-Silva, and Nina Narodytska, seeks to replace these "vibes-based" explanations with formal explanations grounded in mathematical logic. By treating a machine learning model as a set of logical constraints, these researchers can provide provable guarantees of sufficiency and necessity.
From Heuristics to Prime Implicants
The core intuition of this field is to view a model’s prediction not as a probability, but as a logical consequence of its inputs. In Abduction-Based Explanations for Machine Learning Models, the authors introduce the concept of Abductive Explanations (AXp).
An AXp is a "prime implicant": a minimal subset of input features such that, as long as these features remain fixed, the model’s prediction is mathematically guaranteed to stay the same, regardless of what happens to any other features.
Unlike a saliency map that might highlight a pixel because it "seems important," an abductive explanation provides a sufficiency guarantee. If a loan application is rejected because of "Income" and "Credit Score," a formal AXp proves that no matter how much you change the applicant's "Age" or "Zip Code," the model must still reject the application.
The Duality of Why and Why Not
Formal explainability reveals a deep mathematical symmetry between two types of questions:
- Why? (Abductive): What is the smallest set of features that forces this prediction?
- Why Not? (Contrastive): What is the smallest change I could make to flip this prediction?
In On Relating 'Why?' and 'Why Not?' Explanations, Ignatiev and colleagues prove that these two forms are minimal hitting sets of one another. This means that if you find all the ways to flip a prediction (contrastive), you can mathematically derive the reasons for the current prediction (abductive), and vice versa. This duality allows researchers to use high-performance solvers—like MaxSAT or SMT solvers—to efficiently navigate the space of possible explanations, as seen in Using MaxSAT for Efficient Explanations of Tree Ensembles.
Verified Robustness in High-Stakes Domains
The primary motivation for this rigor is safety. In domains like autonomous aviation or medicine, a "heuristic" guess isn't enough. Gitta Kutyniok argues in Zuverlässige Künstliche Intelligenz that the "reliability gap" in AI can only be closed by grounding explainability in theoretical foundations.
One major breakthrough in this area is $\Delta$-robustness. As Junqi Jiang and Francesca Toni explain in Formalising the Robustness of Counterfactual Explanations for Neural Networks, standard explanations are fragile; if you retrain a model on slightly different data, the "reason" for a decision might vanish. Formal methods allow for the generation of explanations that are guaranteed to remain valid even if the model's internal weights shift within a defined range.
Scaling Proofs to Deep Learning
While formal reasoning is computationally expensive (often NP-hard), recent work has focused on making it practical for complex models:
- Monotonicity: Bernardo Cuenca Grau and Ian Horrocks showed in Cardinality-Minimal Explanations for Monotonic Neural Networks that if a model is constrained to be monotonic, we can find the absolute smallest explanations in polynomial time.
- Abstraction-Refinement: The VeriX framework, developed by Haoze Wu and Clark Barrett, uses automated reasoning to produce "optimal robust explanations." Newer iterations like VeriX+ use binary search and bound propagation to scale these proofs to large Transformer models.
- Symbolic Compilation: Tools like PyXAI and Silas compile ensemble models (like Random Forests) into Boolean formulas, allowing users to "rectify" models—mathematically forcing them to align with domain knowledge or safety constraints.
By moving from statistical summaries to logical proofs, this research direction ensures that when an AI provides a reason for its actions, that reason is not just a plausible story, but a mathematical certainty.