# When is the Computation of a Feature Attribution Method Tractable?

arXiv: https://arxiv.org/abs/2501.02356 · HTML: https://mlsanity.com/paper/2501.02356/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 21 references that are in the map.
- First posted on arXiv 4 Jan 2025.

## Builds on (most cited first, 12 of 12)

- [A Unified Approach to Interpreting Model Predictions](https://mlsanity.com/paper/1705.07874/) (2017)
- ["Why Should I Trust You?": Explaining the Predictions of Any Classifier](https://mlsanity.com/paper/1602.04938/) (2016)
- [Towards A Rigorous Science of Interpretable Machine Learning](https://mlsanity.com/paper/1702.08608/) (2017)
- [The Mythos of Model Interpretability](https://mlsanity.com/paper/1606.03490/) (2016)
- [The many Shapley values for model explanation](https://mlsanity.com/paper/1908.08474/) (2019)
- [The Shapley Taylor Interaction Index](https://mlsanity.com/paper/1902.05622/) (2019)
- [Data Banzhaf: A Robust Data Valuation Framework for Machine Learning](https://mlsanity.com/paper/2205.15466/) (2022)
- [On the Tractability of SHAP Explanations](https://mlsanity.com/paper/2009.08634/) (2020)
- [On the Complexity of SHAP-Score-Based Explanations: Tractability via Knowledge Compilation and Non-Approximability Results](https://mlsanity.com/paper/2104.08015/) (2021)
- [Logic for Explainable AI](https://mlsanity.com/paper/2305.05172/) (2023)
- [What to Expect of Classifiers? Reasoning about Logistic Regression with Missing Features](https://mlsanity.com/paper/1903.01620/) (2019)
- [Handling Missing Data in Decision Trees: A Probabilistic Approach](https://mlsanity.com/paper/2006.16341/) (2020)

## Built on by (most cited first, 2 of 2)

- [SHAP Meets Tensor Networks: Provably Tractable Explanations with Parallelism](https://mlsanity.com/paper/2510.21599/) (2025)
- [Verified SHAP: Provable Bounds for Exact Shapley Values of Neural Networks](https://mlsanity.com/paper/2605.24084/) (2026)

## Abstract (arXiv)

Feature attribution methods have become essential for explaining machine learning models. Many popular approaches, such as SHAP and Banzhaf values, are grounded in power indices from cooperative game theory, which measure the contribution of features to model predictions. This work studies the computational complexity of power indices beyond SHAP, addressing the conditions under which they can be computed efficiently. We identify a simple condition on power indices that ensures that computation is polynomially equivalent to evaluating expected values, extending known results for SHAP. We also introduce Bernoulli power indices, showing that their computation can be simplified to a constant number of expected value evaluations. Furthermore, we explore interaction power indices that quantify the importance of feature subsets, proving that their computation complexity mirrors that of individual features.