Formal Guarantees for Machine Learning Explanations

57 concepts47 papers1 proposal

Most popular methods for explaining machine learning models—such as LIME, SHAP, or various saliency maps—operate on intuition and statistical sampling. While these tools provide visually appealing heatmaps or feature importance scores, they often lack a rigorous mathematical link to the model’s actual decision logic. As Waeldchen et al. point out, these heuristic methods can be manipulated or provide a false sense of security, failing to offer a provable lower bound on the information content of an explanation.

To address this "reliability gap," a growing body of research focuses on formal explanations: justifications for model predictions that are backed by mathematical proofs of sufficiency, necessity, and robustness.

The Limits of Heuristic Explanations

The fundamental problem with heuristic XAI is the lack of "ground truth." When a saliency map highlights a cluster of pixels, there is no guarantee that those pixels are actually responsible for the prediction. In fact, Marques-Silva 0001 et al. demonstrate that heuristic explainers can sometimes produce results with zero overlap with the true set of influential features.

This lack of rigor is particularly dangerous in safety-critical domains like healthcare or autonomous aviation. As Bassan et al. argue, if an explanation cannot provably guarantee that a subset of features is sufficient to maintain a prediction, it remains a "best guess" that could mask dangerous biases or catastrophic failure modes.

Defining Rigor through Logic

Formal XAI treats machine learning models as logical functions. By mapping a model's behavior to symbolic logic, researchers can define explanations using two primary concepts:

  1. Abductive Explanations (AXp): A minimal subset of input features that guarantees the model's prediction, regardless of the values of the remaining features.
  2. Contrastive Explanations (CXp): A minimal set of features that, if changed, would guarantee the prediction flips to a different class (answering "Why not class B?").

Ignatiev et al. established a theoretical bridge between these explanations and adversarial machine learning, showing that these two fields are duals of one another. Similarly, Watson et al. unified these concepts under the philosophical framework of necessity and sufficiency, providing a formal logic that can encompass disparate methods like rule lists and counterfactuals.

Overcoming the Complexity Barrier

The primary reason heuristic methods are preferred in practice is speed. Computing a provably minimal explanation is typically NP-hard. However, recent work has identified several pathways to make formal guarantees computationally feasible:

  • Tractable Model Classes: For certain models, such as monotonic neural networks, Cuenca Grau et al. show that cardinality-minimal explanations can be found in polynomial time. Similarly, Huang et al. demonstrate that if a classifier is represented as a tractable Boolean circuit (like a d-DNNF), rigorous explanations can be computed efficiently.
  • Abstraction-Refinement: To handle large neural networks, Bassan et al. propose finding explanations on simplified, smaller versions of a network first, then refining those explanations for the full model.
  • SAT and SMT Solvers: By encoding models into Satisfiability (SAT) or Satisfiability Modulo Theories (SMT) problems, researchers can leverage powerful automated reasoning tools. Izza et al. used this approach to generate exact explanations for Random Forests, outperforming heuristic tools in both accuracy and reliability.

Robustness and Algorithmic Recourse

A formal explanation should not only be correct for the current model but also stable across time. A common issue in XAI is that an explanation might become invalid if the model is slightly retrained.

Jiang et al. and Lan et al. have introduced frameworks to guarantee $\Delta$-robustness. These methods ensure that a counterfactual explanation (a recommendation for how a user can change their input to get a different result) remains valid even if the model's parameters shift within a certain bound. This moves the field toward "verified explainability," where the justification for a decision is as robust as the decision itself Wu et al..

Toward a Mathematical Foundation for Trust

The shift from heuristic to formal explanations represents a transition from "explaining away" black-box behavior to "verifying" it. Whether through axiomatic approaches like Integrated Gradients Sundararajan et al. or logic-based feature attribution Ignatiev et al., the goal is to ensure that when a system provides a reason for its actions, that reason is mathematically sound, logically necessary, and provably sufficient.

Key Foundational Work

Axiomatic Attribution for Deep Networks (2017) — contributed 1 concept elements to this direction.
On Relating Explanations and Adversarial Examples (2019) — 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_formal_explanation_guarantees_855e80df,
  title = {formal explanation guarantees},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/formal-explanation-guarantees/rdr_855e80df84104ef787d2ec218e864a15},
  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_formal_explanation_guarantees_855e80df_v1,
  title = {formal explanation guarantees},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/formal-explanation-guarantees/rdr_855e80df84104ef787d2ec218e864a15/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