# Foundations of Symbolic Languages for Model Interpretability arXiv: https://arxiv.org/abs/2110.02376 ยท HTML: https://mlsanity.com/paper/2110.02376/ ## Key facts - Cited by 26 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 5 Oct 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) - [A Survey on Bias and Fairness in Machine Learning](https://mlsanity.com/paper/1908.09635/) (2019) - [Towards A Rigorous Science of Interpretable Machine Learning](https://mlsanity.com/paper/1702.08608/) (2017) - [OpenML: networked science in machine learning](https://mlsanity.com/paper/1407.7722/) (2014) - [Explaining Explanations: An Overview of Interpretability of Machine Learning](https://mlsanity.com/paper/1806.00069/) (2018) - [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) - [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) - [Explaining Naive Bayes and Other Linear Classifiers with Polynomial Time and Delay](https://mlsanity.com/paper/2008.05803/) (2020) - [On Explaining Decision Trees](https://mlsanity.com/paper/2010.11034/) (2020) - [Stop Explaining Black Box Machine Learning Models for High Stakes Decisions and Use Interpretable Models Instead](https://mlsanity.com/paper/1811.10154/) (2018) - [On Symbolically Encoding the Behavior of Random Forests](https://mlsanity.com/paper/2007.01493/) (2020) - [On the Relative Expressiveness of Bayesian and Neural Networks](https://mlsanity.com/paper/1812.08957/) (2018) - [Better Trees: An empirical study on hyperparameter tuning of classification decision tree induction algorithms](https://mlsanity.com/paper/1812.02207/) (2018) - [Descriptive Complexity for Counting Complexity Classes](https://mlsanity.com/paper/1805.02724/) (2018) ## Built on by (most cited first, 26 of 26) - [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 Computing Probabilistic Explanations for Decision Trees](https://mlsanity.com/paper/2207.12213/) (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) - [Local vs. Global Interpretability: A Computational Complexity Perspective](https://mlsanity.com/paper/2406.02981/) (2024) - [Disproving XAI Myths with Formal Methods -- Initial Results](https://mlsanity.com/paper/2306.01744/) (2023) - [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) - [Formal Mechanistic Interpretability: Automated Circuit Discovery with Provable Guarantees](https://mlsanity.com/paper/2602.16823/) (2026) - [Neurosymbolic AI and its Taxonomy: a survey](https://mlsanity.com/paper/2305.08876/) (2023) - [A Uniform Language to Explain Decision Trees](https://mlsanity.com/paper/2310.11636/) (2023) - [Even-if Explanations: Formal Foundations, Priorities and Complexity](https://mlsanity.com/paper/2401.10938/) (2024) - [On the Complexity of Global Necessary Reasons to Explain Classification](https://mlsanity.com/paper/2501.06766/) (2025) - [Additive Models Explained: A Computational Complexity Approach](https://mlsanity.com/paper/2510.21292/) (2025) - [Query languages for neural networks](https://mlsanity.com/paper/2408.10362/) (2024) - [SQL4NN: Validation and expressive querying of models as data](https://mlsanity.com/paper/2502.14745/) (2025) - [Recursive querying of neural networks via weighted structures](https://mlsanity.com/paper/2601.03201/) (2026) - [Unifying Formal Explanations: A Complexity-Theoretic Perspective](https://mlsanity.com/paper/2602.18160/) (2026) - [COMET: Neural Cost Model Explanation Framework](https://mlsanity.com/paper/2302.06836/) (2023) - [Logic Explanation of AI Classifiers by Categorical Explaining Functors](https://mlsanity.com/paper/2503.16203/) (2025) - [Extracting Robust Register Automata from Neural Networks over Data Sequences](https://mlsanity.com/paper/2511.19100/) (2025) - [On Logic-Based Explainability with Partially Specified Inputs](https://mlsanity.com/paper/2306.15803/) (2023) - [Seeing Through Risk: A Symbolic Approximation of Prospect Theory](https://mlsanity.com/paper/2504.14448/) (2025) - [Synthesis and Verification of Transformer Programs (Technical Report)](https://mlsanity.com/paper/2602.16473/) (2026) - [ExplAIner: A Declarative Query Language for Explaining Classification Models](https://mlsanity.com/paper/2607.06407/) (2026) ## Abstract (arXiv) Several queries and scores have recently been proposed to explain individual predictions over ML models. Given the need for flexible, reliable, and easy-to-apply interpretability methods for ML models, we foresee the need for developing declarative languages to naturally specify different explainability queries. We do this in a principled way by rooting such a language in a logic, called FOIL, that allows for expressing many simple but important explainability queries, and might serve as a core for more expressive interpretability languages. We study the computational complexity of FOIL queries over two classes of ML models often deemed to be easily interpretable: decision trees and OBDDs. Since the number of possible inputs for an ML model is exponential in its dimension, the tractability of the FOIL evaluation problem is delicate but can be achieved by either restricting the structure of the models or the fragment of FOIL being evaluated. We also present a prototype implementation of FOIL wrapped in a high-level declarative language and perform experiments showing that such a language can be used in practice.