Additive Models Explained: A Computational Complexity Approach
Not on the map. Why?
Abstract (arXiv)
Generalized Additive Models (GAMs) are commonly considered *interpretable* within the ML community, as their structure makes the relationship between inputs and outputs relatively understandable. Therefore, it may seem natural to hypothesize that obtaining meaningful explanations for GAMs could be performed efficiently and would not be computationally infeasible. In this work, we challenge this hypothesis by analyzing the *computational complexity* of generating different explanations for various forms of GAMs across multiple contexts. Our analysis reveals a surprisingly diverse landscape of both positive and negative complexity outcomes. Particularly, under standard complexity assumptions such as P!=NP, we establish several key findings: (1) in stark contrast to many other common ML models, the complexity of generating explanations for GAMs is heavily influenced by the structure of the input space; (2) the complexity of explaining GAMs varies significantly with the types of component models used - but interestingly, these differences only emerge under specific input domain settings; (3) significant complexity distinctions appear for obtaining explanations in regression tasks versus classification tasks in GAMs; and (4) expressing complex models like neural networks additively (e.g., as neural additive models) can make them easier to explain, though interestingly, this benefit appears only for certain explanation methods and input domains. Collectively, these results shed light on the feasibility of computing diverse explanations for GAMs, offering a rigorous theoretical picture of the conditions under which such computations are possible or provably hard.
Key facts. Cited by 3 papers in the map (data through 14 Oct 2026). Builds on 80 of its 114 references that are in the map. First posted on arXiv 24 Oct 2025.
Builds on
80 of 114 references.
References · 80
- 2017A Unified Approach to Interpreting Model Predictionscited by 6,555
- 2016"Why Should I Trust You?": Explaining the Predictions of Any Classifiercited by 5,070
- 2017Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networkscited by 744
- 2019Explaining Machine Learning Classifiers through Diverse Counterfactual Explanationscited by 614
- 2018Towards Robust Interpretability with Self-Explaining Neural Networkscited by 505
- 2019The many Shapley values for model explanationcited by 344
- 2020Neural Additive Models: Interpretable Machine Learning with Neural Netscited by 319
- 2019On the (In)fidelity and Sensitivity for Explanationscited by 310
- 2018Explanations based on the Missing: Towards Contrastive Explanations with Pertinent Negativescited by 262
- 2021Beta-CROWN: Efficient Bound Propagation with Per-neuron Split Constraints for Complete and Incomplete Neural Network Robustness Verificationcited by 228
- 2018Abduction-Based Explanations for Machine Learning Modelscited by 160
- 2022Bridging the Gap Between Learning in Discrete and Continuous Environments for Vision-and-Language Navigationcited by 132
38 more
- 2018A Symbolic Approach to Explaining Bayesian Network Classifierscited by 131
- 2020On The Reasons Behind Decisionscited by 100
- 2020On the Tractability of SHAP Explanationscited by 92
- 2021NODE-GAM: Neural Generalized Additive Model for Interpretable Deep Learningcited by 88
- 2024Marabou 2.0: A Versatile Formal Analyzer of Neural Networkscited by 81
- 2020Model Interpretability through the Lens of Computational Complexitycited by 75
- 2022From Shapley Values to Generalized Additive Models and backcited by 60
- 2020Explaining Naive Bayes and Other Linear Classifiers with Polynomial Time and Delaycited by 57
- 2021On Explaining Random Forests with SATcited by 57
- 2022Neural Basis Models for Interpretabilitycited by 56
- 2021On Guaranteed Optimal Robust Explanations for NLP Modelscited by 54
- 2020How Interpretable and Trustworthy are GAMs?cited by 44
- 2022Towards Formal XAI: Formally Approximate Minimal Explanations of Neural Networkscited by 42
- 2021On the Computational Intelligibility of Boolean Classifierscited by 40
- 2021On Efficiently Explaining Graph-Based Classifierscited by 37
- 2022On Computing Probabilistic Explanations for Decision Treescited by 35
- 2021Continuous vs. Discrete Optimization of Deep Neural Networkscited by 34
- 2019Robustness Verification of Tree-based Modelscited by 33
- 2021On the Complexity of SHAP-Score-Based Explanations: Tractability via Knowledge Compilation and Non-Approximability Resultscited by 32
- 2021Provably efficient, succinct, and precise explanationscited by 32
- 2018What made you do this? Understanding black-box decisions with sufficient input subsetscited by 31
- 2022VeriX: Towards Verified Explainability of Deep Neural Networkscited by 30
- 2023Exploring and Interacting with the Set of Good Sparse Generalized Additive Modelscited by 30
- 2022Sparse Interaction Additive Networks via Feature Interaction Detection and Sparse Selectioncited by 28
- 2021Reachability Is NP-Complete Even for the Simplest Neural Networkscited by 27
- 2021Foundations of Symbolic Languages for Model Interpretabilitycited by 26
- 2022Sparse Neural Additive Model: Interpretable Deep Learning with Feature Selection via Group Sparsitycited by 25
- 2021Probabilistic Sufficient Explanationscited by 24
- 2021Accuracy, Interpretability, and Differential Privacy via Explainable Boostingcited by 24
- 2023Formally Explaining Neural Networks within Reactive Systemscited by 24
- 2022Computing Abductive Explanations for Boosted Treescited by 23
- 2022Feature Necessity & Relevancy in ML Classifier Explanationscited by 23
- 2024Local vs. Global Interpretability: A Computational Complexity Perspectivecited by 23
- 2024Distance-Restricted Explanations: Theoretical Underpinnings & Efficient Implementationcited by 21
- 2024The Interpretable and Effective Graph Neural Additive Networkscited by 20
- 2022Fast Sparse Classification for Generalized Linear and Additive Modelscited by 19
- 2022On Computing Probabilistic Abductive Explanationscited by 18
- 2023Neural Additive Models for Location Scale and Shape: A Framework for Interpretable Neural Regression Beyond the Meancited by 18
50 most cited of 80 All 80 (JSON)
Built on by
Citing papers per year: 2026: 3.
3 papers.