# WOODELF-HD: Efficient Background SHAP for High-Depth Decision Trees

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 36 references that are in the map.
- First posted on arXiv 12 Apr 2026.

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

- [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)
- [Tunability: Importance of Hyperparameters of Machine Learning Algorithms](https://mlsanity.com/paper/1802.09596/) (2018)
- [On the Tractability of SHAP Explanations](https://mlsanity.com/paper/2009.08634/) (2020)
- [CatBoost: unbiased boosting with categorical features](https://mlsanity.com/paper/1706.09516/) (2017)
- [Fast TreeSHAP: Accelerating SHAP Value Computation for Trees](https://mlsanity.com/paper/2109.09847/) (2021)
- [The Shapley Value of Tuples in Query Answering](https://mlsanity.com/paper/1904.08679/) (2019)
- [GPUTreeShap: Massively Parallel Exact Calculation of SHAP Scores for Tree Ensembles](https://mlsanity.com/paper/2010.13972/) (2020)
- [TreeGrad-Ranker: Feature Ranking via O(L)-Time Gradients for Decision Trees](https://mlsanity.com/paper/2602.11623/) (2026)

## Abstract (arXiv)

Decision-tree ensembles are a cornerstone of predictive modeling, and SHAP is a standard framework for interpreting their predictions. Among its variants, Background SHAP offers high accuracy by modeling missing features using a background dataset. Historically, this approach did not scale well, as the time complexity for explaining n instances using m background samples included an O(mn) component. Recent methods such as Woodelf and PLTreeSHAP reduce this to O(m+n), but introduce a preprocessing bottleneck that grows as 3^D with tree depth D, making them impractical for deep trees. We address this limitation with WoodelfHD, a Woodelf extension that reduces the 3^D factor to 2^D. The key idea is a Strassen-like multiplication scheme that exploits the structure of Woodelf matrices, reducing matrix-vector multiplication from O(k^2) to O(k*log(k)) via a fully vectorized, non-recursive implementation. In addition, we merge path nodes with identical features, reducing cache size and memory usage. When running on standard environments, WoodelfHD enables exact Background SHAP computation for trees with depths up to 21, where previous methods fail due to excessive memory usage. For ensembles of depths 12 and 15, it achieves speedups of 33x and 162x, respectively, over the state-of-the-art.