Research map / Learning theory and algorithms / Prediction and decision losses
Local vs. Global Interpretability: A Computational Complexity Perspective
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 theory to compare local and global formal explanations (sufficient reasons, necessity/redundancy, completion counts) for perceptrons, FBDDs/decision trees, and MLPs, proving a local-global duality and uniqueness of global minimal sufficient reasons.
Problem
Local and global interpretability of ML models are studied informally; there is a lack of mathematical rigor in assessing their inherent interpretability, particularly for global explanations.
Approach
Defines global counterparts of formal explanation queries (sufficient reasons, necessity, redundancy, completion count), proves a duality between local contrastive and global sufficient reasons via hitting sets, and proves uniqueness of the subset-minimal global sufficient reason, which yields complexity separations between local and global computation across model classes.
Key results
- For perceptrons, local CSR and MSR are polynomial-time while global G-CSR and G-MSR are coNP-complete.
- For FBDDs (decision trees), global MSR is polynomial-time (G-MSR in PTIME) while local MSR is NP-complete, due to uniqueness of the subset-minimal global sufficient reason.
- The number of local subset-minimal sufficient reasons can be Theta(2^n/sqrt(n)) in the worst case, whereas a global subset-minimal sufficient reason is unique.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the global rather than local MSR query | FBDDs · FBDDs | computational complexity: NP-C -> PTIME | Helped |
| Use the global rather than local FR query | FBDDs · FBDDs | computational complexity: coNP-C -> PTIME | Helped |
| Use the global rather than local MSR query | MLPs · MLPs | computational complexity: $\Sigma_{2}^{P}$-C -> coNP-C | Helped |
| Use the global rather than local FR query | MLPs · MLPs | computational complexity: $\Pi_{2}^{P}$-C -> coNP-C | Helped |
| Use the global rather than local FN query | MLPs · MLPs | computational complexity: PTIME -> coNP-C | Hurt |
| Use the global rather than local CSR query | Perceptrons · Perceptrons | computational complexity: PTIME -> coNP-C | Hurt |
| Use the global rather than local MSR query | Perceptrons · Perceptrons | computational complexity: PTIME -> coNP-C | Hurt |
| Use the global rather than local FR query | Perceptrons · Perceptrons | computational complexity: coNP-C -> coNP-C | No clear effect |
| Use the global rather than local CC query | FBDDs, MLPs, and Perceptrons · FBDDs, MLPs, and Perceptrons | computational complexity: PTIME -> PTIME; \#P-C -> \#P-C | No clear effect |
| Add hidden layers rather than use a Perceptron | MLP local CSR, MSR, and FR · MLPs versus Perceptrons | computational complexity: CSR: PTIME -> coNP-C; MSR: PTIME -> $\Sigma_{2}^{P}$-C; FR: coNP-C -> $\Pi_{2}^{P}$-C | Hurt |
| Add hidden layers rather than use a Perceptron | MLP global CSR, MSR, and FR · MLPs versus Perceptrons | computational complexity | No clear effect |
Surprising findings
- Global sufficient-reason selection is easier than local for decision trees and MLPs, reversing the intuition that global interpretability is harder.
- Completion counting (CC) has the same complexity locally and globally across all analyzed models, unlike decision-problem queries.
Limitations
- Analysis restricted to boolean inputs and outputs; real-valued case only partly covered in appendix.
- Only a limited set of explanation forms (sufficiency, necessity, redundancy, completion count) is studied.
- Purely theoretical; no empirical evaluation on real models.
Experimental setup
Builds on: abductive explanations c-interpretability prime implicants
Closest papers by meaning
- Additive Models Explained: A Computational Complexity Approach (NeurIPS 2025 · similarity 0.91)
- What makes an Ensemble (Un) Interpretable? (ICML 2025 · similarity 0.90)
- Everything, Everywhere, All at Once: Is Mechanistic Interpretability Identifiable? (ICLR 2025 · similarity 0.88)
- Even-if Explanations: Formal Foundations, Priorities and Complexity (AAAI 2025 · similarity 0.87)
- The Computational Complexity of Circuit Discovery for Inner Interpretability (ICLR 2025 · similarity 0.87)
- The Non-Linear Representation Dilemma: Is Causal Abstraction Enough for Mechanistic Interpretability? (NeurIPS 2025 · similarity 0.87)
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.