# On Formal Feature Attribution and Its Approximation

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 36 of its 78 references that are in the map.
- First posted on arXiv 7 Jul 2023.

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

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [A Unified Approach to Interpreting Model Predictions](https://mlsanity.com/paper/1705.07874/) (2017)
- [XGBoost: A Scalable Tree Boosting System](https://mlsanity.com/paper/1603.02754/) (2016)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- ["Why Should I Trust You?": Explaining the Predictions of Any Classifier](https://mlsanity.com/paper/1602.04938/) (2016)
- [Explanation in Artificial Intelligence: Insights from the Social Sciences](https://mlsanity.com/paper/1706.07269/) (2017)
- [The Mythos of Model Interpretability](https://mlsanity.com/paper/1606.03490/) (2016)
- [MedMNIST v2 -- A large-scale lightweight benchmark for 2D and 3D biomedical image classification](https://mlsanity.com/paper/2110.14795/) (2021)
- [Fooling LIME and SHAP: Adversarial Attacks on Post hoc Explanation Methods](https://mlsanity.com/paper/1911.02508/) (2019)
- [Abduction-Based Explanations for Machine Learning Models](https://mlsanity.com/paper/1811.10656/) (2018)
- [PMLB: A Large Benchmark Suite for Machine Learning Evaluation and Comparison](https://mlsanity.com/paper/1703.00512/) (2017)
- [A Symbolic Approach to Explaining Bayesian Network Classifiers](https://mlsanity.com/paper/1805.03364/) (2018)
- [Reliable Post hoc Explanations: Modeling Uncertainty in Explainability](https://mlsanity.com/paper/2008.05030/) (2020)
- ["How do I fool you?": Manipulating User Trust via Misleading Black Box Explanations](https://mlsanity.com/paper/1911.06473/) (2019)
- [On The Reasons Behind Decisions](https://mlsanity.com/paper/2002.09284/) (2020)
- [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)
- [Logic-Based Explainability in Machine Learning](https://mlsanity.com/paper/2211.00541/) (2022)
- [On Tackling Explanation Redundancy in Decision Trees](https://mlsanity.com/paper/2205.09971/) (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)
- [On Computing Probabilistic Explanations for Decision Trees](https://mlsanity.com/paper/2207.12213/) (2022)
- [On the Complexity of SHAP-Score-Based Explanations: Tractability via Knowledge Compilation and Non-Approximability Results](https://mlsanity.com/paper/2104.08015/) (2021)
- [Provably efficient, succinct, and precise explanations](https://mlsanity.com/paper/2111.01576/) (2021)
- [The Inadequacy of Shapley Values for Explainability](https://mlsanity.com/paper/2302.08160/) (2023)
- [Foundations of Symbolic Languages for Model Interpretability](https://mlsanity.com/paper/2110.02376/) (2021)
- [ASTERYX : A model-Agnostic SaT-basEd appRoach for sYmbolic and score-based eXplanations](https://mlsanity.com/paper/2206.11900/) (2022)
- [Eliminating The Impossible, Whatever Remains Must Be True](https://mlsanity.com/paper/2206.09551/) (2022)
- [Feature Necessity & Relevancy in ML Classifier Explanations](https://mlsanity.com/paper/2210.15675/) (2022)

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

- [Beyond Topological Self-Explainable GNNs: A Formal Explainability Perspective](https://mlsanity.com/paper/2502.02719/) (2025)
- [Axiomatic Aggregations of Abductive Explanations](https://mlsanity.com/paper/2310.03131/) (2023)
- [Anytime Approximate Formal Feature Attribution](https://mlsanity.com/paper/2312.06973/) (2023)
- [From SHAP Scores to Feature Importance Scores](https://mlsanity.com/paper/2405.11766/) (2024)
- [Most General Explanations of Tree Ensembles (Extended Version)](https://mlsanity.com/paper/2505.10991/) (2025)
- [Logic-Based Explainability: Past, Present & Future](https://mlsanity.com/paper/2406.11873/) (2024)
- [SHAP scores fail pervasively even when Lipschitz succeeds](https://mlsanity.com/paper/2412.13866/) (2024)
- [Knowing What You Cannot Explain: Learning to Reject Low-Quality Explanations](https://mlsanity.com/paper/2507.12900/) (2025)
- [Efficient Contrastive Explanations on Demand](https://mlsanity.com/paper/2412.18262/) (2024)
- [The Sets of Power](https://mlsanity.com/paper/2410.07867/) (2024)
- [A Formal Framework for the Explanation of Finite Automata Decisions](https://mlsanity.com/paper/2602.13351/) (2026)

## Abstract (arXiv)

Recent years have witnessed the widespread use of artificial intelligence (AI) algorithms and machine learning (ML) models. Despite their tremendous success, a number of vital problems like ML model brittleness, their fairness, and the lack of interpretability warrant the need for the active developments in explainable artificial intelligence (XAI) and formal ML model verification. The two major lines of work in XAI include feature selection methods, e.g. Anchors, and feature attribution techniques, e.g. LIME and SHAP. Despite their promise, most of the existing feature selection and attribution approaches are susceptible to a range of critical issues, including explanation unsoundness and out-of-distribution sampling. A recent formal approach to XAI (FXAI) although serving as an alternative to the above and free of these issues suffers from a few other limitations. For instance and besides the scalability limitation, the formal approach is unable to tackle the feature attribution problem. Additionally, a formal explanation despite being formally sound is typically quite large, which hampers its applicability in practical settings. Motivated by the above, this paper proposes a way to apply the apparatus of formal XAI to the case of feature attribution based on formal explanation enumeration. Formal feature attribution (FFA) is argued to be advantageous over the existing methods, both formal and non-formal. Given the practical complexity of the problem, the paper then proposes an efficient technique for approximating exact FFA. Finally, it offers experimental evidence of the effectiveness of the proposed approximate FFA in comparison to the existing feature attribution algorithms not only in terms of feature importance and but also in terms of their relative order.