# Linear TreeShap

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 2 of its 22 references that are in the map.
- First posted on arXiv 16 Sep 2022.

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

- ["Why Should I Trust You?": Explaining the Predictions of Any Classifier](https://mlsanity.com/paper/1602.04938/) (2016)
- [Fast TreeSHAP: Accelerating SHAP Value Computation for Trees](https://mlsanity.com/paper/2109.09847/) (2021)

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

- [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)
- [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)
- [TreeGrad-Ranker: Feature Ranking via O(L)-Time Gradients for Decision Trees](https://mlsanity.com/paper/2602.11623/) (2026)
- [Fast Calculation of Feature Contributions in Boosting Trees](https://mlsanity.com/paper/2407.03515/) (2024)
- [Quadrature-TreeSHAP: Depth-Independent TreeSHAP and Shapley Interactions](https://mlsanity.com/paper/2605.04497/) (2026)
- [Adalina: Adaptive Linear Approximation for the Shapley Value and Beyond](https://mlsanity.com/paper/2604.08438/) (2026)
- [ConfoundingSHAP: Quantifying confounding strength in causal inference](https://mlsanity.com/paper/2605.10533/) (2026)
- [Verified SHAP: Provable Bounds for Exact Shapley Values of Neural Networks](https://mlsanity.com/paper/2605.24084/) (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)
- [qshap: Fast Shapley Decomposition of R2 for Gradient-Boosted Trees](https://mlsanity.com/paper/2608.24104/) (2026)
- [Explaining Heterogeneous Treatment Effects with Causal Forests and the Hoeffding Functional Decomposition](https://mlsanity.com/paper/2610.16447/) (2026)

## Abstract (arXiv)

Decision trees are well-known due to their ease of interpretability. To improve accuracy, we need to grow deep trees or ensembles of trees. These are hard to interpret, offsetting their original benefits. Shapley values have recently become a popular way to explain the predictions of tree-based machine learning models. It provides a linear weighting to features independent of the tree structure. The rise in popularity is mainly due to TreeShap, which solves a general exponential complexity problem in polynomial time. Following extensive adoption in the industry, more efficient algorithms are required. This paper presents a more efficient and straightforward algorithm: Linear TreeShap. Like TreeShap, Linear TreeShap is exact and requires the same amount of memory.