# Logic-Based Explainability in Machine Learning

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

## Key facts

- Cited by 48 papers in the map (data through 14 Oct 2026).
- Builds on 105 of its 351 references that are in the map.
- First posted on arXiv 24 Oct 2022.

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

- [A Unified Approach to Interpreting Model Predictions](https://mlsanity.com/paper/1705.07874/) (2017)
- [Generative Adversarial Networks](https://mlsanity.com/paper/2203.00667/) (2022)
- ["Why Should I Trust You?": Explaining the Predictions of Any Classifier](https://mlsanity.com/paper/1602.04938/) (2016)
- [Deep Inside Convolutional Networks: Visualising Image Classification Models and Saliency Maps](https://mlsanity.com/paper/1312.6034/) (2013)
- [Explanation in Artificial Intelligence: Insights from the Social Sciences](https://mlsanity.com/paper/1706.07269/) (2017)
- [Sanity Checks for Saliency Maps](https://mlsanity.com/paper/1810.03292/) (2018)
- [A Survey Of Methods For Explaining Black Box Models](https://mlsanity.com/paper/1802.01933/) (2018)
- [Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks](https://mlsanity.com/paper/1702.01135/) (2017)
- [Fooling LIME and SHAP: Adversarial Attacks on Post hoc Explanation Methods](https://mlsanity.com/paper/1911.02508/) (2019)
- [A Survey on Explainable Artificial Intelligence (XAI): Towards Medical XAI](https://mlsanity.com/paper/1907.07374/) (2019)
- [Interpretable Machine Learning: Fundamental Principles and 10 Grand Challenges](https://mlsanity.com/paper/2103.11251/) (2021)
- [Methods for Interpreting and Understanding Deep Neural Networks](https://mlsanity.com/paper/1706.07979/) (2017)
- [European Union regulations on algorithmic decision-making and a "right to explanation"](https://mlsanity.com/paper/1606.08813/) (2016)
- [The (Un)reliability of saliency methods](https://mlsanity.com/paper/1711.00867/) (2017)
- [Actionable Recourse in Linear Classification](https://mlsanity.com/paper/1809.06514/) (2018)
- [Algorithmic Recourse: from Counterfactual Explanations to Interventions](https://mlsanity.com/paper/2002.06278/) (2020)
- [Distilling a Neural Network Into a Soft Decision Tree](https://mlsanity.com/paper/1711.09784/) (2017)
- [Algorithms for Verifying Deep Neural Networks](https://mlsanity.com/paper/1903.06758/) (2019)
- [Abduction-Based Explanations for Machine Learning Models](https://mlsanity.com/paper/1811.10656/) (2018)
- [The Disagreement Problem in Explainable Machine Learning: A Practitioner's Perspective](https://mlsanity.com/paper/2202.01602/) (2022)
- [A Symbolic Approach to Explaining Bayesian Network Classifiers](https://mlsanity.com/paper/1805.03364/) (2018)
- [Explainable Deep Learning: A Field Guide for the Uninitiated](https://mlsanity.com/paper/2004.14545/) (2020)
- [A survey of algorithmic recourse: definitions, formulations, solutions, and prospects](https://mlsanity.com/paper/2010.04050/) (2020)
- ["How do I fool you?": Manipulating User Trust via Misleading Black Box Explanations](https://mlsanity.com/paper/1911.06473/) (2019)
- [Optimal Sparse Decision Trees](https://mlsanity.com/paper/1904.12847/) (2019)
- [On The Reasons Behind Decisions](https://mlsanity.com/paper/2002.09284/) (2020)
- [Generalized and Scalable Optimal Sparse Decision Trees](https://mlsanity.com/paper/2006.08690/) (2020)
- [Preventing Repeated Real World AI Failures by Cataloging Incidents: The AI Incident Database](https://mlsanity.com/paper/2011.08512/) (2020)
- [When Explanations Lie: Why Many Modified BP Attributions Fail](https://mlsanity.com/paper/1912.09818/) (2019)
- [On the Tractability of SHAP Explanations](https://mlsanity.com/paper/2009.08634/) (2020)

## Built on by (most cited first, 30 of 48)

- [The Inadequacy of Shapley Values for Explainability](https://mlsanity.com/paper/2302.08160/) (2023)
- [Explainability is NOT a Game](https://mlsanity.com/paper/2307.07514/) (2023)
- [Local vs. Global Interpretability: A Computational Complexity Perspective](https://mlsanity.com/paper/2406.02981/) (2024)
- [Distance-Restricted Explanations: Theoretical Underpinnings & Efficient Implementation](https://mlsanity.com/paper/2405.08297/) (2024)
- [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)
- [Explain Yourself, Briefly! Self-Explaining Neural Networks with Concise Sufficient Reasons](https://mlsanity.com/paper/2502.03391/) (2025)
- [On Formal Feature Attribution and Its Approximation](https://mlsanity.com/paper/2307.03380/) (2023)
- [Explainable AI (XAI) in Image Segmentation in Medicine, Industry, and Beyond: A Survey](https://mlsanity.com/paper/2405.01636/) (2024)
- [Beyond Topological Self-Explainable GNNs: A Formal Explainability Perspective](https://mlsanity.com/paper/2502.02719/) (2025)
- [From SHAP Scores to Feature Importance Scores](https://mlsanity.com/paper/2405.11766/) (2024)
- [SHAP Meets Tensor Networks: Provably Tractable Explanations with Parallelism](https://mlsanity.com/paper/2510.21599/) (2025)
- [Space Explanations of Neural Network Classification](https://mlsanity.com/paper/2511.22498/) (2025)
- [A Refutation of Shapley Values for Explainability](https://mlsanity.com/paper/2309.03041/) (2023)
- [Refutation of Shapley Values for XAI -- Additional Evidence](https://mlsanity.com/paper/2310.00416/) (2023)
- [A Uniform Language to Explain Decision Trees](https://mlsanity.com/paper/2310.11636/) (2023)
- [Faster Verified Explanations for Neural Networks](https://mlsanity.com/paper/2512.00164/) (2025)
- [Explaining Decisions in ML Models: a Parameterized Complexity Analysis](https://mlsanity.com/paper/2407.15780/) (2024)
- [Abductive and Contrastive Explanations for Scoring Rules in Voting](https://mlsanity.com/paper/2408.12927/) (2024)
- [On the Complexity of Global Necessary Reasons to Explain Classification](https://mlsanity.com/paper/2501.06766/) (2025)
- [Why this and not that? A Logic-based Framework for Contrastive Explanations](https://mlsanity.com/paper/2507.08454/) (2025)
- [FAME: Formal Abstract Minimal Explanation for Neural Networks](https://mlsanity.com/paper/2603.10661/) (2026)
- [Attribution-Scores and Causal Counterfactuals as Explanations in Artificial Intelligence](https://mlsanity.com/paper/2303.02829/) (2023)
- [Logic-Based Explainability: Past, Present & Future](https://mlsanity.com/paper/2406.11873/) (2024)
- [Query languages for neural networks](https://mlsanity.com/paper/2408.10362/) (2024)
- [Robust Explanations Through Uncertainty Decomposition: A Path to Trustworthier AI](https://mlsanity.com/paper/2507.12913/) (2025)
- [Explaining Tournament Solutions with Minimal Supports](https://mlsanity.com/paper/2509.09312/) (2025)
- [Recursive querying of neural networks via weighted structures](https://mlsanity.com/paper/2601.03201/) (2026)
- [COMET: Neural Cost Model Explanation Framework](https://mlsanity.com/paper/2302.06836/) (2023)
- [Explainable Answer-set Programming](https://mlsanity.com/paper/2308.15901/) (2023)

## Abstract (arXiv)

The last decade witnessed an ever-increasing stream of successes in Machine Learning (ML). These successes offer clear evidence that ML is bound to become pervasive in a wide range of practical uses, including many that directly affect humans. Unfortunately, the operation of the most successful ML models is incomprehensible for human decision makers. As a result, the use of ML models, especially in high-risk and safety-critical settings is not without concern. In recent years, there have been efforts on devising approaches for explaining ML models. Most of these efforts have focused on so-called model-agnostic approaches. However, all model-agnostic and related approaches offer no guarantees of rigor, hence being referred to as non-formal. For example, such non-formal explanations can be consistent with different predictions, which renders them useless in practice. This paper overviews the ongoing research efforts on computing rigorous model-based explanations of ML models; these being referred to as formal explanations. These efforts encompass a variety of topics, that include the actual definitions of explanations, the characterization of the complexity of computing explanations, the currently best logical encodings for reasoning about different ML models, and also how to make explanations interpretable for human decision makers, among others.