# Beyond TreeSHAP: Efficient Computation of Any-Order Shapley Interactions for Tree Ensembles

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

## Key facts

- Cited by 31 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 50 references that are in the map.
- First posted on arXiv 22 Jan 2024.

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

- [A Unified Approach to Interpreting Model Predictions](https://mlsanity.com/paper/1705.07874/) (2017)
- [XGBoost: A Scalable Tree Boosting System](https://mlsanity.com/paper/1603.02754/) (2016)
- [Fooling LIME and SHAP: Adversarial Attacks on Post hoc Explanation Methods](https://mlsanity.com/paper/1911.02508/) (2019)
- [The many Shapley values for model explanation](https://mlsanity.com/paper/1908.08474/) (2019)
- [Problems with Shapley-value-based explanations as feature importance measures](https://mlsanity.com/paper/2002.11097/) (2020)
- [Improving KernelSHAP: Practical Shapley Value Estimation via Linear Regression](https://mlsanity.com/paper/2012.01536/) (2020)
- [The Shapley Taylor Interaction Index](https://mlsanity.com/paper/1902.05622/) (2019)
- [True to the Model or True to the Data?](https://mlsanity.com/paper/2006.16234/) (2020)
- [FastSHAP: Real-Time Shapley Value Estimation](https://mlsanity.com/paper/2107.07436/) (2021)
- [Algorithms to estimate Shapley value feature attributions](https://mlsanity.com/paper/2207.07605/) (2022)
- [How does this interaction affect me? Interpretable attribution for feature interactions](https://mlsanity.com/paper/2006.10965/) (2020)
- [Faith-Shap: The Faithful Shapley Interaction Index](https://mlsanity.com/paper/2203.00870/) (2022)
- [OpenML-Python: an extensible Python API for OpenML](https://mlsanity.com/paper/1911.02490/) (2019)
- [From Shapley Values to Generalized Additive Models and back](https://mlsanity.com/paper/2209.04012/) (2022)
- [Visualizing the Feature Importance for Black Box Models](https://mlsanity.com/paper/1804.06620/) (2018)
- [SHAP-IQ: Unified Approximation of any-order Shapley Interactions](https://mlsanity.com/paper/2303.01179/) (2023)
- [Purifying Interaction Effects with the Functional ANOVA: An Efficient Algorithm for Recovering Identifiable Additive Models](https://mlsanity.com/paper/1911.04974/) (2019)
- [Fast TreeSHAP: Accelerating SHAP Value Computation for Trees](https://mlsanity.com/paper/2109.09847/) (2021)
- [High Dimensional Model Explanations: an Axiomatic Approach](https://mlsanity.com/paper/2006.08969/) (2020)

## Built on by (most cited first, 30 of 31)

- [shapiq: Shapley Interactions for Machine Learning](https://mlsanity.com/paper/2410.01649/) (2024)
- [KernelSHAP-IQ: Weighted Least-Square Optimization for Shapley Interactions](https://mlsanity.com/paper/2405.10852/) (2024)
- [Exact Computation of Any-Order Shapley Interactions for Graph Neural Networks](https://mlsanity.com/paper/2501.16944/) (2025)
- [Unifying Feature-Based Explanations with Functional ANOVA and Cooperative Game Theory](https://mlsanity.com/paper/2412.17152/) (2024)
- [SHAP Meets Tensor Networks: Provably Tractable Explanations with Parallelism](https://mlsanity.com/paper/2510.21599/) (2025)
- [Tree Ensemble Explainability through the Hoeffding Functional Decomposition and TreeHFD Algorithm](https://mlsanity.com/paper/2510.24815/) (2025)
- [An Odd Estimator for Shapley Values](https://mlsanity.com/paper/2602.01399/) (2026)
- [Efficient and Accurate Explanation Estimation with Distribution Compression](https://mlsanity.com/paper/2406.18334/) (2024)
- [Fast Estimation of Partial Dependence Functions using Trees](https://mlsanity.com/paper/2410.13448/) (2024)
- [Disentangling Interactions and Dependencies in Feature Attribution](https://mlsanity.com/paper/2410.23772/) (2024)
- [HyperSHAP: Shapley Values and Interactions for Explaining Hyperparameter Optimization](https://mlsanity.com/paper/2502.01276/) (2025)
- [UbiQTree: Uncertainty Quantification in XAI with Tree Ensembles](https://mlsanity.com/paper/2508.09639/) (2025)
- [TreeGrad-Ranker: Feature Ranking via O(L)-Time Gradients for Decision Trees](https://mlsanity.com/paper/2602.11623/) (2026)
- [Exactly Computing do-Shapley Values](https://mlsanity.com/paper/2602.07203/) (2026)
- [A Comprehensive Study of Shapley Value in Data Analytics](https://mlsanity.com/paper/2412.01460/) (2024)
- [Adaptive Prompting: Ad-hoc Prompt Composition for Social Bias Detection](https://mlsanity.com/paper/2502.06487/) (2025)
- [Quadrature-TreeSHAP: Depth-Independent TreeSHAP and Shapley Interactions](https://mlsanity.com/paper/2605.04497/) (2026)
- [Energy-Based Model for Accurate Estimation of Shapley Values in Feature Attribution](https://mlsanity.com/paper/2404.01078/) (2024)
- [Surrogate Interpretable Graph for Random Decision Forests](https://mlsanity.com/paper/2506.01988/) (2025)
- [Adalina: Adaptive Linear Approximation for the Shapley Value and Beyond](https://mlsanity.com/paper/2604.08438/) (2026)
- [Generalized Functional ANOVA: A Complete Theoretical Framework](https://mlsanity.com/paper/2605.18422/) (2026)
- [A novel gradient-based method for decision trees optimizing arbitrary differential loss functions](https://mlsanity.com/paper/2503.17855/) (2025)
- [CUBE: Contrastive Understanding by Balanced Experiments](https://mlsanity.com/paper/2509.10825/) (2025)
- [SX-GeoTree: Self-eXplaining Geospatial Regression Tree Incorporating the Spatial Similarity of Feature Attributions](https://mlsanity.com/paper/2511.19845/) (2025)
- [Provable Recovery of Locally Important Signed Features and Interactions from Random Forest](https://mlsanity.com/paper/2512.11081/) (2025)
- [Rethinking XAI Evaluation: A Human-Centered Audit of Shapley Benchmarks in High-Stakes Settings](https://mlsanity.com/paper/2604.22662/) (2026)
- [ConfoundingSHAP: Quantifying confounding strength in causal inference](https://mlsanity.com/paper/2605.10533/) (2026)
- [TN-SHAP-G: Graph-Structured Tensor Network Surrogates for Shapley Values and Interactions](https://mlsanity.com/paper/2606.01540/) (2026)
- [OperatorSHAP: Fast and Accurate Shapley Value Estimation for Neural Operators](https://mlsanity.com/paper/2606.28065/) (2026)
- [Nonlinear Axiomatic Attribution for Cooperative Games](https://mlsanity.com/paper/2607.09869/) (2026)

## Abstract (arXiv)

While shallow decision trees may be interpretable, larger ensemble models like gradient-boosted trees, which often set the state of the art in machine learning problems involving tabular data, still remain black box models. As a remedy, the Shapley value (SV) is a well-known concept in explainable artificial intelligence (XAI) research for quantifying additive feature attributions of predictions. The model-specific TreeSHAP methodology solves the exponential complexity for retrieving exact SVs from tree-based models. Expanding beyond individual feature attribution, Shapley interactions reveal the impact of intricate feature interactions of any order. In this work, we present TreeSHAP-IQ, an efficient method to compute any-order additive Shapley interactions for predictions of tree-based models. TreeSHAP-IQ is supported by a mathematical framework that exploits polynomial arithmetic to compute the interaction scores in a single recursive traversal of the tree, akin to Linear TreeSHAP. We apply TreeSHAP-IQ on state-of-the-art tree ensembles and explore interactions on well-established benchmark datasets.