On the Tractability of SHAP Explanations

SHAP explanations may be computationally impractical for real-world use: The paper demonstrates that computing SHAP explanations—a widely-used tool for explaining AI decisions—is mathematically intractable (computationally infeasible) for common machine learning models like logistic regression, even under simplified assumptions about data distribution.

Popular simplifications don't solve the core problem: Organizations often use "fully-factorized" assumptions to make SHAP computation easier, but this paper shows these shortcuts don't actually resolve the fundamental computational difficulty, meaning the problem remains hard even with these workarounds.

The problem is harder than previously understood: Computing SHAP explanations is shown to be #P-hard across multiple settings, including even trivial classifiers with simple data distributions, suggesting the computational challenge is more fundamental and widespread than practitioners may realize.

Implications for AI accountability: Since SHAP is a popular method for making AI decisions interpretable and accountable, these tractability results raise questions about whether organizations can actually compute reliable explanations for their models in practice, potentially undermining efforts to provide meaningful transparency to stakeholders and regulators.