# FAME: Formal Abstract Minimal Explanation for Neural Networks

arXiv: https://arxiv.org/abs/2603.10661 · HTML: https://mlsanity.com/paper/2603.10661/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 34 of its 50 references that are in the map.
- First posted on arXiv 11 Mar 2026.

## Builds on (most cited first, 30 of 34)

- [Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks](https://mlsanity.com/paper/1702.01135/) (2017)
- [Efficient Neural Network Robustness Certification with General Activation Functions](https://mlsanity.com/paper/1811.00866/) (2018)
- [Beta-CROWN: Efficient Bound Propagation with Per-neuron Split Constraints for Complete and Incomplete Neural Network Robustness Verification](https://mlsanity.com/paper/2103.06624/) (2021)
- [Evaluating and Aggregating Feature-based Model Explanations](https://mlsanity.com/paper/2005.00631/) (2020)
- [Abduction-Based Explanations for Machine Learning Models](https://mlsanity.com/paper/1811.10656/) (2018)
- [A Symbolic Approach to Explaining Bayesian Network Classifiers](https://mlsanity.com/paper/1805.03364/) (2018)
- [Marabou 2.0: A Versatile Formal Analyzer of Neural Networks](https://mlsanity.com/paper/2401.14461/) (2024)
- [Explaining Naive Bayes and Other Linear Classifiers with Polynomial Time and Delay](https://mlsanity.com/paper/2008.05803/) (2020)
- [On Explaining Random Forests with SAT](https://mlsanity.com/paper/2105.10278/) (2021)
- [On Guaranteed Optimal Robust Explanations for NLP Models](https://mlsanity.com/paper/2105.03640/) (2021)
- [On Explaining Decision Trees](https://mlsanity.com/paper/2010.11034/) (2020)
- [Logic-Based Explainability in Machine Learning](https://mlsanity.com/paper/2211.00541/) (2022)
- [Towards Formal XAI: Formally Approximate Minimal Explanations of Neural Networks](https://mlsanity.com/paper/2210.13915/) (2022)
- [SAT-Based Rigorous Explanations for Decision Lists](https://mlsanity.com/paper/2105.06782/) (2021)
- [Explanations for Monotonic Classifiers](https://mlsanity.com/paper/2106.00154/) (2021)
- [Don't Lie to Me! Robust and Efficient Explainability with Verified Perturbation Analysis](https://mlsanity.com/paper/2202.07728/) (2022)
- [The Fourth International Verification of Neural Networks Competition (VNN-COMP 2023): Summary and Results](https://mlsanity.com/paper/2312.16760/) (2023)
- [On Efficiently Explaining Graph-Based Classifiers](https://mlsanity.com/paper/2106.01350/) (2021)
- [A Review of Formal Methods applied to Machine Learning](https://mlsanity.com/paper/2104.02466/) (2021)
- [Trading Complexity for Sparsity in Random Forest Explanations](https://mlsanity.com/paper/2108.05276/) (2021)
- [VeriX: Towards Verified Explainability of Deep Neural Networks](https://mlsanity.com/paper/2212.01051/) (2022)
- [Achieving robustness in classification using optimal transport with hinge regularization](https://mlsanity.com/paper/2006.06520/) (2020)
- [ASTERYX : A model-Agnostic SaT-basEd appRoach for sYmbolic and score-based eXplanations](https://mlsanity.com/paper/2206.11900/) (2022)
- [Xplique: A Deep Learning Explainability Toolbox](https://mlsanity.com/paper/2206.04394/) (2022)
- [Formally Explaining Neural Networks within Reactive Systems](https://mlsanity.com/paper/2308.00143/) (2023)
- [On the Computation of Necessary and Sufficient Explanations](https://mlsanity.com/paper/2203.10451/) (2022)
- [Distance-Restricted Explanations: Theoretical Underpinnings & Efficient Implementation](https://mlsanity.com/paper/2405.08297/) (2024)
- [From Robustness to Explainability and Back Again](https://mlsanity.com/paper/2306.03048/) (2023)
- [Explaining, Fast and Slow: Abstraction and Refinement of Provable Explanations](https://mlsanity.com/paper/2506.08505/) (2025)
- [Disproving XAI Myths with Formal Methods -- Initial Results](https://mlsanity.com/paper/2306.01744/) (2023)

## Built on by (most cited first, 3 of 3)

- [Incremental Neural Network Verification via Learned Conflicts](https://mlsanity.com/paper/2603.12232/) (2026)
- [Beyond Explaining Predictions: Logic-Based Explanations for Confidence in Machine Learning Models](https://mlsanity.com/paper/2606.10347/) (2026)
- [Beyond L2: Generalizing Abductive Latent Explanations to Diverse Prototype-Based Architectures](https://mlsanity.com/paper/2608.16773/) (2026)

## Abstract (arXiv)

We propose FAME (Formal Abstract Minimal Explanations), a new class of abductive explanations grounded in abstract interpretation. FAME is the first method to scale to large neural networks while reducing explanation size. Our main contribution is the design of dedicated perturbation domains that eliminate the need for traversal order. FAME progressively shrinks these domains and leverages LiRPA-based bounds to discard irrelevant features, ultimately converging to a formal abstract minimal explanation. To assess explanation quality, we introduce a procedure that measures the worst-case distance between an abstract minimal explanation and a true minimal explanation. This procedure combines adversarial attacks with an optional VERIX+ refinement step. We benchmark FAME against VERIX+ and demonstrate consistent gains in both explanation size and runtime on medium- to large-scale neural networks.