Research map / Learning theory and algorithms / Prediction and decision losses
What makes an Ensemble (Un) Interpretable?
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Uses computational complexity and parameterized complexity to show that ensembles of decision trees are tractable to explain when the number of trees is fixed, while ensembles of linear models become intractable with only two models, and constant-size base models remain hard.
Problem
Interpretability of ensemble models is poorly understood formally; it is unclear what makes ensembles (un)interpretable with respect to explanation types, base-model type, number, and size of base models.
Approach
Applies computational (and parameterized) complexity theory to classify the hardness of sufficient-reason, contrastive, count-completion, and Shapley explanation queries for majority/weighted voting ensembles of decision trees, linear models, and ReLU networks, and shows complexity gaps versus single base models.
Key results
- Ensembles of decision trees and of linear models are coNP-, NP-, Sigma2P-, #P-complete/hard for CSR, MCR, MSR, CC, SHAP, whereas single trees/linear models are PTIME for several of these queries.
- Ensembles with constant-size base models (parameterized by max base-model size) are para-NP/para-Sigma2P/para-#P hard for all queries.
- Ensembles of two linear models are already para-NP-complete for CSR and MCR; tree ensembles with fixed number of trees are in XP and FPT when leaves per tree are bounded.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| aggregate decision trees into an ensemble | Decision trees · CSR, MCR, MSR, CC, and SHAP | computational complexity | Hurt |
| aggregate linear models into an ensemble | Linear models · CSR, MSR, and MCR | computational complexity | Hurt |
| aggregate neural networks into an ensemble | Neural networks · Explainability queries | computational complexity | No clear effect |
| reduce the maximum base-model size to a constant | Ensembles of decision trees, linear models, or neural networks · CSR, MCR, MSR, CC, and SHAP | computational complexity | No clear effect |
| limit the ensemble to two linear models | Linear-model ensembles · CSR and MCR | computational complexity | Hurt |
| limit the ensemble to five linear models | Linear-model ensembles · MSR | computational complexity | Hurt |
| reduce the number of linear models in the ensemble | Linear-model ensembles · CSR, MCR, MSR, CC, and SHAP | computational complexity | No clear effect |
| reduce the number of decision trees in the ensemble | Decision-tree ensembles · CSR, MCR, CC, and SHAP | computational complexity | Helped |
| fix the number of decision-tree leaves per tree | Decision-tree ensembles · CSR, MCR, CC, and SHAP | computational complexity | Helped |
| use a constant number of decision trees rather than linear models | Decision-tree and linear-model ensembles · CSR, MSR, MCR, CC, and SHAP | computational complexity | Helped |
| replace a majority-voting ensemble with a weighted-voting ensemble | Ensembles · Explainability queries | computational complexity | No clear effect |
Surprising findings
- Tree ensembles become more tractable as the number of trees shrinks, whereas linear-model ensembles become intractable with only two models.
- Neural network ensembles show no complexity gap versus single networks because they are closed under ensemble construction.
Limitations
- Restricted to specific explanation forms (sufficient reasons, contrastive, CC, SHAP) and base-model types.
- Analysis is theoretical with Boolean inputs/outputs; extension to regression and multiclass is partly left open.
Experimental setup
Builds on: c-interpretability formal XAI abductive explanations parameterized complexity
Closest papers by meaning
- Local vs. Global Interpretability: A Computational Complexity Perspective (ICML 2024 · similarity 0.90)
- Multistage Defer Trees for Hybrid Interpretability: If at First You Can't Succeed, Tree Again (NeurIPS 2026 · similarity 0.86)
- Additive Models Explained: A Computational Complexity Approach (NeurIPS 2025 · similarity 0.85)
- Everything, Everywhere, All at Once: Is Mechanistic Interpretability Identifiable? (ICLR 2025 · similarity 0.85)
- A General Theoretical Framework for Learning Smallest Interpretable Models (AAAI 2024 · similarity 0.84)
- Learning Performance Maximizing Ensembles with Explainability Guarantees (AAAI 2024 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.