mlsanityData to 7 Oct 2026

Fast TreeSHAP: Accelerating SHAP Value Computation for Trees

arXiv 2109.09847 ↗First posted 20 Sep 2021cs.LG stat.MLcited by 28

Not on the map. Why?

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.

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

Builds on

14 of 33 references.

References · 14

  1. 2017A Unified Approach to Interpreting Model Predictionscited by 6,488
  2. 2016XGBoost: A Scalable Tree Boosting Systemcited by 5,120
  3. 2016"Why Should I Trust You?": Explaining the Predictions of Any Classifiercited by 5,040
  4. 2017Axiomatic Attribution for Deep Networkscited by 3,350
  5. 2019The many Shapley values for model explanationcited by 341
  6. 2019Interpretable machine learning: definitions, methods, and applicationscited by 303
  7. 2018Consistent Individualized Feature Attribution for Tree Ensemblescited by 279
  8. 2019Explaining individual predictions when features are dependent: More accurate approximations to Shapley valuescited by 205
  9. 2020Problems with Shapley-value-based explanations as feature importance measurescited by 198
  10. 2019Feature relevance quantification in explainable AI: A causal problemcited by 164
  11. 2020True to the Model or True to the Data?cited by 123
  12. 2020Shapley explainability on the data manifoldcited by 88
2 more
  1. 2019Explainable AI for Trees: From Local Explanations to Global Understandingcited by 64
  2. 2020Generating Interpretable Poverty Maps using Object Detection in Satellite Imagescited by 27

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 2; 2023: 6; 2024: 9; 2025: 2; 2026: 9.

28 papers.

Sort:

  1. 2022Algorithms to estimate Shapley value feature attributionscited by 114
  2. 2024Beyond TreeSHAP: Efficient Computation of Any-Order Shapley Interactions for Tree Ensemblescited by 30
  3. 2023Efficient XAI Techniques: A Taxonomic Surveycited by 14
  4. 2022Linear TreeShapcited by 12
  5. 2024On the Tractability of SHAP Explanations under Markovian Distributionscited by 10
  6. 2024SHAP values via sparse Fourier representationcited by 8
  7. 2025SHAP Meets Tensor Networks: Provably Tractable Explanations with Parallelismcited by 8
  8. 2023EMBERSim: A Large-Scale Databank for Boosting Similarity Search in Malware Analysiscited by 6
  9. 2024Improving the Weighting Strategy in KernelSHAPcited by 5
  10. 2023The Thousand Faces of Explainable AI Along the Machine Learning Life Cycle: Industrial Reality and Current State of Researchcited by 4
  11. 2024Fast Estimation of Partial Dependence Functions using Treescited by 4
  12. 2026TreeGrad-Ranker: Feature Ranking via O(L)-Time Gradients for Decision Treescited by 4
16 more
  1. 2023On marginal feature attributions of tree-based modelscited by 3
  2. 2024Fast Calculation of Feature Contributions in Boosting Treescited by 3
  3. 2025From Decision Trees to Boolean Logic: A Fast and Unified SHAP Algorithmcited by 3
  4. 2023An Efficient Shapley Value Computation for the Naive Bayes Classifiercited by 2
  5. 2024A Comprehensive Study of Shapley Value in Data Analyticscited by 2
  6. 2024Applications of Explainable artificial intelligence in Earth system sciencecited by 1
  7. 2026Quadrature-TreeSHAP: Depth-Independent TreeSHAP and Shapley Interactionscited by 1
  8. 2023Unlocking Sales Growth: Account Prioritization Engine with Explainable AIcited by 0
  9. 2024XAI and Android Malware Modelscited by 0
  10. 2026WOODELF-HD: Efficient Background SHAP for High-Depth Decision Treescited by 0
  11. 2026Rethinking XAI Evaluation: A Human-Centered Audit of Shapley Benchmarks in High-Stakes Settingscited by 0
  12. 2026Budget-Efficient Automatic Algorithm Design via Code Graphcited by 0
  13. 2026Verified SHAP: Provable Bounds for Exact Shapley Values of Neural Networkscited by 0
  14. 2026Enhancing AI Interpretability with Localised Architecturescited by 0
  15. 2026What Makes a Peer? Valuation-Anchored Similarity in Private Marketscited by 0
  16. 2026qshap: Fast Shapley Decomposition of R2 for Gradient-Boosted Treescited by 0