On the Complexity of SHAP-Score-Based Explanations: Tractability via Knowledge Compilation and Non-Approximability Results

Marcelo Arenas, Pablo Barceló, Leopoldo E. Bertossi, Mikaël Monet

Introduction

As machine learning models are increasingly deployed in high-stakes domains, the demand for local explanations—interpreting why a specific decision was made for a specific instance—has become paramount. The SHAP (SHapley Additive exPlanations) score has emerged as the gold standard for this task. Rooted in cooperative game theory, SHAP provides a unique and fair distribution of "credit" among input features. However, the practical utility of SHAP is often hindered by its computational complexity. In general settings, computing SHAP scores is #P-hard, forcing practitioners to rely on heuristic approximations that lack formal guarantees. This paper establishes a definitive map of the computational complexity of SHAP, identifying the "tractability frontier" where exact computation is possible and proving where even reliable approximation is fundamentally impossible.

The Computational Challenge of SHAP

The core difficulty in computing SHAP scores lies in the combinatorial explosion of feature subsets. To calculate a feature's contribution, one must theoretically evaluate the model's output across all possible combinations of features. This is computationally equivalent to counting the number of solutions to a complex logic problem (#P-hardness). While various tools exist to estimate these scores, this research investigates whether specific model structures allow for exact, polynomial-time computation.

Tractability via Knowledge Compilation

The authors utilize the framework of Knowledge Compilation (KC) to identify tractable model classes. KC involves transforming complex models (such as decision trees or neural networks) into structured Boolean circuits that simplify specific queries.

The Role of d-DNNFs

The paper identifies deterministic and decomposable Boolean circuits (d-DNNFs) as the key to tractability. These structures possess two critical properties:

  1. Determinism: Ensures that logical operations do not overlap, preventing double-counting of solutions.
  2. Decomposability: Ensures that different branches of the circuit operate on independent sets of variables.

The researchers developed a bottom-up induction algorithm capable of traversing these circuits to compute exact SHAP scores in polynomial time. This result is significant because it encompasses several widely used models, including binary decision trees, Ordered Binary Decision Diagrams (OBDDs), and Free Binary Decision Diagrams (FBDDs). This tractability holds under the assumption of "product distributions," where input features are treated as independent.

The Hardness of Approximation

One of the paper's most striking contributions is the discovery that SHAP is, in some respects, "harder" than model counting (#SAT). For decades, computer scientists have known that while counting the solutions to a Disjunctive Normal Form (DNF) formula is #P-hard, it can be efficiently approximated using a Fully Polynomial-time Randomized Approximation Scheme (FPRAS).

This paper proves that SHAP does not share this property. The authors demonstrate that for DNF formulas, it is impossible to create an FPRAS for SHAP scores unless NP = RP (an outcome considered highly unlikely). This means that for certain model classes, we cannot even obtain a "close enough" answer in a reasonable timeframe. Furthermore, the paper proves that even the simpler task of ranking features—determining if one feature is more influential than another—is computationally intractable for these classes.

Key Insights and Implications

  • The Necessity of Structure: Determinism and decomposability are not merely helpful; they are essential. Removing either property causes the complexity of SHAP computation to jump immediately to #P-hard.
  • Limits of Heuristics: The non-approximability results for DNF formulas suggest that the common practice of using heuristic approximations for SHAP may be fundamentally flawed when applied to certain model structures, as no general-purpose approximation algorithm can provide reliable guarantees.
  • Theoretical Boundaries: The research confirms that SHAP computation is a significantly more difficult problem than standard model counting, placing it high in the hierarchy of computational complexity.

Limitations and Future Work

While this work provides a rigorous map of discrete SHAP complexity, several avenues for future research remain:

  • Continuous Variables: The current study focuses on binary and discrete features. Extending these proofs to continuous domains, perhaps through the use of probabilistic circuits, is a necessary next step.
  • Empirical Distributions: The proofs assume feature independence (product distributions). In real-world scenarios, features are often highly correlated. The authors note that accounting for these correlations (empirical distributions) likely makes the computation even more difficult.
  • Alternative Approximations: While the paper rules out an FPRAS for DNFs, the question remains whether other specific model classes exist where exact computation is hard but reliable approximation is still possible.

Conclusion

By establishing the tractability frontier for SHAP scores, this paper provides a theoretical foundation for the development of more efficient and reliable explainable AI tools. It highlights the power of Knowledge Compilation in making complex models interpretable while cautioning against the uncritical use of approximations in models where SHAP has been proven to be non-approximable.

Summary updated

BibTeX
@article{arenas2023complexity,
  author = {Marcelo Arenas and Pablo Barceló and Leopoldo E. Bertossi and Mikaël Monet},
  title = {{On the Complexity of SHAP-Score-Based Explanations: Tractability via Knowledge Compilation and Non-Approximability Results}},
  journal = {J. Mach. Learn. Res.},
  year = {2023},
  url = {https://openreview.net/forum?id=HeIASYtsNF7},
}
Figure