# Efficient Explanations for Knowledge Compilation Languages

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 62 references that are in the map.
- First posted on arXiv 4 Jul 2021.

## Builds on (most cited first, 18 of 18)

- [A Unified Approach to Interpreting Model Predictions](https://mlsanity.com/paper/1705.07874/) (2017)
- ["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)
- [A Survey Of Methods For Explaining Black Box Models](https://mlsanity.com/paper/1802.01933/) (2018)
- [The Mythos of Model Interpretability](https://mlsanity.com/paper/1606.03490/) (2016)
- [OpenML: networked science in machine learning](https://mlsanity.com/paper/1407.7722/) (2014)
- [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)
- [Explaining Explanations in AI](https://mlsanity.com/paper/1811.01439/) (2018)
- [A Symbolic Approach to Explaining Bayesian Network Classifiers](https://mlsanity.com/paper/1805.03364/) (2018)
- [Towards Explainable Artificial Intelligence](https://mlsanity.com/paper/1909.12072/) (2019)
- [On The Reasons Behind Decisions](https://mlsanity.com/paper/2002.09284/) (2020)
- [Model Interpretability through the Lens of Computational Complexity](https://mlsanity.com/paper/2010.12265/) (2020)
- [Explanation in Human-AI Systems: A Literature Meta-Review, Synopsis of Key Ideas and Publications, and Bibliography for Explainable AI](https://mlsanity.com/paper/1902.01876/) (2019)
- [On Guaranteed Optimal Robust Explanations for NLP Models](https://mlsanity.com/paper/2105.03640/) (2021)
- [The Challenge of Crafting Intelligible Intelligence](https://mlsanity.com/paper/1803.04263/) (2018)
- [On the Computational Intelligibility of Boolean Classifiers](https://mlsanity.com/paper/2104.06172/) (2021)
- [SDDs are Exponentially More Succinct than OBDDs](https://mlsanity.com/paper/1601.00501/) (2016)

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

- [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)
- [On the Computation of Necessary and Sufficient Explanations](https://mlsanity.com/paper/2203.10451/) (2022)
- [Logic for Explainable AI](https://mlsanity.com/paper/2305.05172/) (2023)
- [Tractable Boolean and Arithmetic Circuits](https://mlsanity.com/paper/2202.02942/) (2022)
- [A New Class of Explanations for Classifiers with Non-Binary Features](https://mlsanity.com/paper/2304.14760/) (2023)
- [On Deciding Feature Membership in Explanations of SDD & Related Classifiers](https://mlsanity.com/paper/2202.07553/) (2022)
- [Feature Relevancy, Necessity and Usefulness: Complexity and Algorithms](https://mlsanity.com/paper/2505.09640/) (2025)
- [Leveraging Association Rules for Better Predictions and Better Explanations](https://mlsanity.com/paper/2510.18628/) (2025)
- [Beyond Trained Models: Compiling GNNs for a Sound Explainer Benchmark](https://mlsanity.com/paper/2610.03526/) (2026)

## Abstract (arXiv)

Knowledge compilation (KC) languages find a growing number of practical uses, including in Constraint Programming (CP) and in Machine Learning (ML). In most applications, one natural question is how to explain the decisions made by models represented by a KC language. This paper shows that for many of the best known KC languages, well-known classes of explanations can be computed in polynomial time. These classes include deterministic decomposable negation normal form (d-DNNF), and so any KC language that is strictly less succinct than d-DNNF. Furthermore, the paper also investigates the conditions under which polynomial time computation of explanations can be extended to KC languages more succinct than d-DNNF.