# Fast TreeSHAP: Accelerating SHAP Value Computation for Trees

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

## Key facts

- Cited by 29 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 33 references that are in the map.
- First posted on arXiv 20 Sep 2021.

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

- [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)
- ["Why Should I Trust You?": Explaining the Predictions of Any Classifier](https://mlsanity.com/paper/1602.04938/) (2016)
- [Axiomatic Attribution for Deep Networks](https://mlsanity.com/paper/1703.01365/) (2017)
- [The many Shapley values for model explanation](https://mlsanity.com/paper/1908.08474/) (2019)
- [Interpretable machine learning: definitions, methods, and applications](https://mlsanity.com/paper/1901.04592/) (2019)
- [Consistent Individualized Feature Attribution for Tree Ensembles](https://mlsanity.com/paper/1802.03888/) (2018)
- [Explaining individual predictions when features are dependent: More accurate approximations to Shapley values](https://mlsanity.com/paper/1903.10464/) (2019)
- [Problems with Shapley-value-based explanations as feature importance measures](https://mlsanity.com/paper/2002.11097/) (2020)
- [Feature relevance quantification in explainable AI: A causal problem](https://mlsanity.com/paper/1910.13413/) (2019)
- [True to the Model or True to the Data?](https://mlsanity.com/paper/2006.16234/) (2020)
- [Shapley explainability on the data manifold](https://mlsanity.com/paper/2006.01272/) (2020)
- [Explainable AI for Trees: From Local Explanations to Global Understanding](https://mlsanity.com/paper/1905.04610/) (2019)
- [Generating Interpretable Poverty Maps using Object Detection in Satellite Images](https://mlsanity.com/paper/2002.01612/) (2020)

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

- [Algorithms to estimate Shapley value feature attributions](https://mlsanity.com/paper/2207.07605/) (2022)
- [Beyond TreeSHAP: Efficient Computation of Any-Order Shapley Interactions for Tree Ensembles](https://mlsanity.com/paper/2401.12069/) (2024)
- [Efficient XAI Techniques: A Taxonomic Survey](https://mlsanity.com/paper/2302.03225/) (2023)
- [Linear TreeShap](https://mlsanity.com/paper/2209.08192/) (2022)
- [On the Tractability of SHAP Explanations under Markovian Distributions](https://mlsanity.com/paper/2405.02936/) (2024)
- [SHAP values via sparse Fourier representation](https://mlsanity.com/paper/2410.06300/) (2024)
- [SHAP Meets Tensor Networks: Provably Tractable Explanations with Parallelism](https://mlsanity.com/paper/2510.21599/) (2025)
- [EMBERSim: A Large-Scale Databank for Boosting Similarity Search in Malware Analysis](https://mlsanity.com/paper/2310.01835/) (2023)
- [Improving the Weighting Strategy in KernelSHAP](https://mlsanity.com/paper/2410.04883/) (2024)
- [The Thousand Faces of Explainable AI Along the Machine Learning Life Cycle: Industrial Reality and Current State of Research](https://mlsanity.com/paper/2310.07882/) (2023)
- [Fast Estimation of Partial Dependence Functions using Trees](https://mlsanity.com/paper/2410.13448/) (2024)
- [TreeGrad-Ranker: Feature Ranking via O(L)-Time Gradients for Decision Trees](https://mlsanity.com/paper/2602.11623/) (2026)
- [On marginal feature attributions of tree-based models](https://mlsanity.com/paper/2302.08434/) (2023)
- [Fast Calculation of Feature Contributions in Boosting Trees](https://mlsanity.com/paper/2407.03515/) (2024)
- [From Decision Trees to Boolean Logic: A Fast and Unified SHAP Algorithm](https://mlsanity.com/paper/2511.09376/) (2025)
- [An Efficient Shapley Value Computation for the Naive Bayes Classifier](https://mlsanity.com/paper/2307.16718/) (2023)
- [A Comprehensive Study of Shapley Value in Data Analytics](https://mlsanity.com/paper/2412.01460/) (2024)
- [Quadrature-TreeSHAP: Depth-Independent TreeSHAP and Shapley Interactions](https://mlsanity.com/paper/2605.04497/) (2026)
- [Applications of Explainable artificial intelligence in Earth system science](https://mlsanity.com/paper/2406.11882/) (2024)
- [Unlocking Sales Growth: Account Prioritization Engine with Explainable AI](https://mlsanity.com/paper/2306.07464/) (2023)
- [XAI and Android Malware Models](https://mlsanity.com/paper/2411.16817/) (2024)
- [WOODELF-HD: Efficient Background SHAP for High-Depth Decision Trees](https://mlsanity.com/paper/2604.10569/) (2026)
- [Rethinking XAI Evaluation: A Human-Centered Audit of Shapley Benchmarks in High-Stakes Settings](https://mlsanity.com/paper/2604.22662/) (2026)
- [QuadraSHAP: ε-Exact Shapley Values for Product Games in Logarithmic Parallel Time](https://mlsanity.com/paper/2605.05870/) (2026)
- [Budget-Efficient Automatic Algorithm Design via Code Graph](https://mlsanity.com/paper/2605.10598/) (2026)
- [Verified SHAP: Provable Bounds for Exact Shapley Values of Neural Networks](https://mlsanity.com/paper/2605.24084/) (2026)
- [Enhancing AI Interpretability with Localised Architectures](https://mlsanity.com/paper/2606.07998/) (2026)
- [What Makes a Peer? Valuation-Anchored Similarity in Private Markets](https://mlsanity.com/paper/2608.12594/) (2026)
- [qshap: Fast Shapley Decomposition of R2 for Gradient-Boosted Trees](https://mlsanity.com/paper/2608.24104/) (2026)

## Abstract (arXiv)

SHAP (SHapley Additive exPlanation) values are one of the leading tools for interpreting machine learning models, with strong theoretical guarantees (consistency, local accuracy) and a wide availability of implementations and use cases. Even though computing SHAP values takes exponential time in general, TreeSHAP takes polynomial time on tree-based models. While the speedup is significant, TreeSHAP can still dominate the computation time of industry-level machine learning solutions on datasets with millions or more entries, causing delays in post-hoc model diagnosis and interpretation service. In this paper we present two new algorithms, Fast TreeSHAP v1 and v2, designed to improve the computational efficiency of TreeSHAP for large datasets. We empirically find that Fast TreeSHAP v1 is 1.5x faster than TreeSHAP while keeping the memory cost unchanged. Similarly, Fast TreeSHAP v2 is 2.5x faster than TreeSHAP, at the cost of a slightly higher memory usage, thanks to the pre-computation of expensive TreeSHAP steps. We also show that Fast TreeSHAP v2 is well-suited for multi-time model interpretations, resulting in as high as 3x faster explanation of newly incoming samples.