# On Explaining Random Forests with SAT

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

## Key facts

- Cited by 57 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 44 references that are in the map.
- First posted on arXiv 21 May 2021.

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

- [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)
- [Methods for Interpreting and Understanding Deep Neural Networks](https://mlsanity.com/paper/1706.07979/) (2017)
- [Deep Learning for Case-Based Reasoning through Prototypes: A Neural Network that Explains Its Predictions](https://mlsanity.com/paper/1710.04806/) (2017)
- [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)
- [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)
- [SAT-Based Rigorous Explanations for Decision Lists](https://mlsanity.com/paper/2105.06782/) (2021)
- [Verifying Robustness of Gradient Boosted Models](https://mlsanity.com/paper/1906.10991/) (2019)
- [Multi-Label Learning with Deep Forest](https://mlsanity.com/paper/1911.06557/) (2019)
- [AutoEncoder by Forest](https://mlsanity.com/paper/1709.09018/) (2017)
- [Distributed Deep Forest and its Application to Automatic Detection of Cash-out Fraud](https://mlsanity.com/paper/1805.04234/) (2018)
- [LionForests: Local Interpretation of Random Forests](https://mlsanity.com/paper/1911.08780/) (2019)

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

- [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)
- [Explanations for Monotonic Classifiers](https://mlsanity.com/paper/2106.00154/) (2021)
- [On Efficiently Explaining Graph-Based Classifiers](https://mlsanity.com/paper/2106.01350/) (2021)
- [Trading Complexity for Sparsity in Random Forest Explanations](https://mlsanity.com/paper/2108.05276/) (2021)
- [The Inadequacy of Shapley Values for Explainability](https://mlsanity.com/paper/2302.08160/) (2023)
- [VeriX: Towards Verified Explainability of Deep Neural Networks](https://mlsanity.com/paper/2212.01051/) (2022)
- [Eliminating The Impossible, Whatever Remains Must Be True](https://mlsanity.com/paper/2206.09551/) (2022)
- [Computing Abductive Explanations for Boosted Trees](https://mlsanity.com/paper/2209.07740/) (2022)
- [Feature Necessity & Relevancy in ML Classifier Explanations](https://mlsanity.com/paper/2210.15675/) (2022)
- [Logic for Explainable AI](https://mlsanity.com/paper/2305.05172/) (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)
- [On Computing Probabilistic Abductive Explanations](https://mlsanity.com/paper/2212.05990/) (2022)
- [Delivering Inflated Explanations](https://mlsanity.com/paper/2306.15272/) (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)
- [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)
- [Hard to Explain: On the Computational Hardness of In-Distribution Model Interpretation](https://mlsanity.com/paper/2408.03915/) (2024)
- [Explaining Random Forests using Bipolar Argumentation and Markov Networks (Technical Report)](https://mlsanity.com/paper/2211.11699/) (2022)
- [Anytime Approximate Formal Feature Attribution](https://mlsanity.com/paper/2312.06973/) (2023)
- [Provably Precise, Succinct and Efficient Explanations for Decision Trees](https://mlsanity.com/paper/2205.09569/) (2022)
- [Cardinality-Minimal Explanations for Monotonic Neural Networks](https://mlsanity.com/paper/2205.09901/) (2022)
- [A New Class of Explanations for Classifiers with Non-Binary Features](https://mlsanity.com/paper/2304.14760/) (2023)
- [Most General Explanations of Tree Ensembles (Extended Version)](https://mlsanity.com/paper/2505.10991/) (2025)
- [Locally-Minimal Probabilistic Explanations](https://mlsanity.com/paper/2312.11831/) (2023)
- [On Computing Relevant Features for Explaining NBCs](https://mlsanity.com/paper/2207.04748/) (2022)
- [A Uniform Language to Explain Decision Trees](https://mlsanity.com/paper/2310.11636/) (2023)
- [Axiomatic Characterisations of Sample-based Explainers](https://mlsanity.com/paper/2408.04903/) (2024)

## Abstract (arXiv)

Random Forest (RFs) are among the most widely used Machine Learning (ML) classifiers. Even though RFs are not interpretable, there are no dedicated non-heuristic approaches for computing explanations of RFs. Moreover, there is recent work on polynomial algorithms for explaining ML models, including naive Bayes classifiers. Hence, one question is whether finding explanations of RFs can be solved in polynomial time. This paper answers this question negatively, by proving that computing one PI-explanation of an RF is D^P-complete. Furthermore, the paper proposes a propositional encoding for computing explanations of RFs, thus enabling finding PI-explanations with a SAT solver. This contrasts with earlier work on explaining boosted trees (BTs) and neural networks (NNs), which requires encodings based on SMT/MILP. Experimental results, obtained on a wide range of publicly available datasets, demontrate that the proposed SAT-based approach scales to RFs of sizes common in practical applications. Perhaps more importantly, the experimental results demonstrate that, for the vast majority of examples considered, the SAT-based approach proposed in this paper significantly outperforms existing heuristic approaches.