WOODELF-HD: Efficient Background SHAP for High-Depth Decision Trees
Ron Wettenstein, Alexander Nadel, Udi Boker, [0.5em] Reichman University, Herzliya, Israel · 2026
Read WOODELF-HD: Efficient Background SHAP for High-Depth Decision Trees by Ron Wettenstein, Alexander Nadel, Udi Boker, [0.5em] Reichman University, Herzliya, Israel (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-10569.txt.
Introduction
Wettenstein, Nadel, and Boker speed up Background SHAP for deep decision-tree ensembles. SHAP rates each feature's contribution by comparing against background data. Earlier fast methods hit a preprocessing wall that grows as 3 to the power of depth. Their WoodelfHD extension cuts that factor to 2 to the power of depth with a Strassen-like scheme and merged path nodes. It handles trees up to depth 21. It runs 33 times faster than the rival at depth 12 and 162 times faster at depth 15.
Catalog record
| CREATOR | Ron Wettenstein, Alexander Nadel, Udi Boker, [0.5em] Reichman University, Herzliya, Israel |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 46649 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.10569
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
WOODELF-HD: Efficient Background SHAP for High-Depth Decision Trees Ron Wettenstein, Alexander Nadel, Udi Boker, [0.5em] Reichman University, Herzliya, Israel Abstract 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 n instances using m m background samples included an O ( m n ) O(mn) component. Recent methods such as Woodelf and PLTreeSHAP reduce this to O ( m + n ) O(m+n) , but introduce a preprocessing bottleneck that grows as 3 D 3^{D} with tree depth D D , making them impractical for deep trees. We address this limitation with WoodelfHD , a Woodelf extension that reduces the 3 D 3^{D} factor to 2 D 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 ) O(k^{2}) to O ( k log k ) 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 21 , where previous methods fail due to excessive memory usage. For ensembles of depths 12 12 and 15 15 , it achieves speedups of 33 × 33\times and 162 × 162\times , respectively, over the state-of-the-art. Links The Woodelf and WoodelfHD Python Package – https://github.com/ron-wettenstein/woodelf Experimental Results Interactive Report — https://ron-wettenstein.github.io/TreeBranchMarks/ benchmarks/reports/WoodelfhdMainExperiment.html Experiment Notebooks — https://github.com/ron-wettenstein/WoodelfExperiments Task shap Package PLTreeSHAP Original Woodelf WoodelfHD BG SHAP O(nmTLD) O(mTL\!+\!nT3^{D}D) O(mTL\!+\!nTLD\!+\!TL3^{D}D) O(mTL\!+\!nTLD\!+\!TL2^{D}D^{2}) BG SHAP IV O(nmTLDf) O(mTL\!+\!nT3^{D}D^{2}) O(mTL\!+\!nTLD^{2}\!+\!TL3^{D}D^{2}) O(mTL\!+\!nTLD^{2}\!+\!TL2^{D}D^{3}) Table 1: Time complexities for Background SHAP (BG SHAP) and Background SHAP interaction values (BG SHAP IV). The table presents the complexities of the shap Python package, PLTreeSHAP , original Woodelf (as presented in [ 26 ] ) and WoodelfHD (as presented in this paper). For notation, see fig. 1 . The shap complexity depends on O(nm) , which becomes impractical for large background datasets. Among the methods with O(n+m) dependence, WoodelfHD achieves the best asymptotic complexity, depending on 2^{D} rather than 3^{D} . 1 Introduction Decision tree ensembles such as XGBoost [ 8 ] , Random Forest [ 5 ] , and CatBoost [ 13 ] are widely used predictive models for classification and regression. With their increasing adoption, substantial attention has been devoted to explaining their predictions. One common perspective frames explanation as the fair distribution of predictive credit among input features. This viewpoint is formalized by SHAP [ 22 ] , which models prediction explanation as a cooperative game and assigns feature attributions using Shapley values [ 28 ] . Beyond individual attributions, SHAP also extends to Shapley interaction values, which capture pairwise feature interactions [ 14 ] . Computing Shapley values is #P-hard for certain games [ 24 ] and for common model classes such as neural networks and logistic regression [ 31 , 16 ] . Fortunately, exact and efficient computation is possible for decision tree ensembles [ 23 ] as well as in other settings, including certain classes of Boolean circuits [ 1 ] and tuples in query answering [ 21 ] . SHAP has two commonly used variants. Background SHAP uses a background dataset to accurately capture the model prediction when some features are missing, while Path-Dependent SHAP estimates this behavior based on node-coverage statistics. While our proposed solution applies to both variants, we focus primarily on Background SHAP, the more accurate approach, where we improve the state-of-the-art complexity. The most widely used implementation of SHAP is the shap Python package, which supports both CPU [ 23 ] and GPU [ 25 ] computation. shap ’s key drawback is its quadratic complexity for Background SHAP: The complexity of explaining the predictions of n instances with a background dataset of size m includes an O(mn) component. The PLTreeSHAP algorithm [ 35 ] reduces this to O(m+n) by preprocessing the decision tree and the background dataset. For Path-Dependent SHAP, FastTreeSHAP [ 33 ] was the first algorithm to outperform the original shap implementation. More recent advances include Linear TreeSHAP [ 34 ] , which improves the theoretical complexity but suffers from numerical instability (see [ 20 ] , Section 5), and TreeGrad-SHAP [ 20 ] , which builds on this line of work and significantly reduces these stability issues. Finally, recent work introduced Woodelf , a unified and efficient algorithm for computing Shapley values on decision tree ensembles [ 26 ] . Woodelf computes both Path-Dependent and Background SHAP in a numerically stable manner and, like PLTreeSHAP , computes Background SHAP with complexity that scales as O(m+n) . It is significantly faster than shap , PLTreeSHAP , and FastTreeSHAP , especially on large datasets. Woodelf is GPU-friendly and available as a Python package. In this paper, we extend Woodelf to efficiently support high-depth trees. 1.1 Our Contributions Task Original Woodelf WoodelfHD PD SHAP O(\boldsymbol{L3^{D}D}\,+ n(f+L)) O(\boldsymbol{2^{D}D}\,+ n(f+D)) BG SHAP O(\boldsymbol{L3^{D}D}\,+ n(f+L)+\,mL) O(\boldsymbol{2^{D}D}\,+ n(f+D)+\,mD) PD SHAP IV O(\boldsymbol{L3^{D}D^{2}}\,+ n(f^{2}+L)) O(\boldsymbol{2^{D}D^{2}}\,+ n(f^{2}+D)) BG SHAP IV O(\boldsymbol{L3^{D}D^{2}}\,+ n(f^{2}+L)+\,mL) O(\boldsymbol{2^{D}D^{2}}\,+ n(f^{2}+D)+\,mD) Table 2: Space complexities of the original Woodelf [ 26 ] and WoodelfHD , considering both the Path-Dependent (PD) and Background (BG) variants for Shapley values (SHAP) and Shapley interaction values (SHAP IV). For notation, see fig. 1 . A key limitation of both Woodelf and PLTreeSHAP is their poor scalability to deep trees. Their time and space complexities have a (3^{D}D) component, where D is the tree depth. In practice, this makes the algorithms difficult to use once the maximum depth exceeds about 12, as runtimes increase sharply and memory requirements typically become prohibitive. Although limiting tree depth is a common way to control overfitting [ 4 ] , deep trees are still frequently used in practice. For example, LightGBM [ 19 ] employs a leaf-wise (depth-first) growth strategy by default and does not impose an explicit depth limit. This strategy expands splits along a single path before broadening the tree, often producing trees with a large maximum depth. \boldsymbol{f} : no. of features; \boldsymbol{n} : no. of consumer data rows; \boldsymbol{m} : no. of background data rows; \boldsymbol{T} : no. of trees; \boldsymbol{D} : max depth; \boldsymbol{L} : max leaves per tree. Figure 1: Notation. We introduce WoodelfHD ( Woodelf for High Depth), an improved algorithm that enhances the state-of-the-art complexity for Background SHAP by replacing the 3^{D}D component with 2^{D}D^{2} in both time and space. tables 1 and 2 summarize the resulting complexity reductions. Notation is given in fig. 1 . These improvements also extend to Path-Dependent SHAP. While the theoretical state-of-the-art remains O(nTLD) as established by Linear TreeSHAP , our approach often outperforms both TreeGrad-SHAP and shap in practical applications involving large-scale datasets. These gains are driven by WoodelfHD vectorized implementations and efficient preprocessing. WoodelfHD significantly outperforms the state-of-the-art in computing Background SHAP on deep trees and extends the range of depths that can be handled in practice. On a 50GB RAM machine, WoodelfHD runs efficiently up to depth 21,