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

Ron Wettenstein; Alexander Nadel; Udi Boker

cs.LGApr 12, 2026

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

Authors: Ron Wettenstein, Alexander Nadel, Udi Boker

Organizations: Reichman University, Herzliya, Israel · Faculty of Data and Decision Sciences, Technion, Haifa, 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 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.

Figures & tables

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}

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 .

Figure 2: A consumer row, baseline row and root-to-leaf path. The figure displays the consumer decision pattern ( Def. 1 ), the baseline decision pattern, and the weighted cube that matches these patterns. The cube is constructed according to the procedure in lines 9 - 11 of Alg. 1 .

Panel of Table 3 — Table 3: The matrix produced by MapPatternsToCube for the root-to-leaf path shown in Fig. 2 . The entry at row index $10$ and column index $01$ is the cube that matches the consumer and baseline rows in Fig. 2 . Applying any function that satisfies linearity, such as the Shapley value of $sugar$ or $age$ , to the cubes in this table yields an $M$ matrix. These kinds of matrices are discussed in Sect. 3 .

Figure 3: The $M$ matrices corresponding to a root-to-leaf path with 6 unique features. The matrix $M[x_{a}]$ matches feature $a$ from the first split, $M[x_{b}]$ matches feature $b$ , and so on. Each cell is colored according to its value: $1$ appears as dark red, $-1$ as dark blue, $0$ as white, and intermediate values are shown with opacity proportional to their magnitude.

Figure 4: Using the matrix properties to perform matrix–vector multiplication with only 2 inner multiplications instead of 4. This Strassen-like formulation reduces the complexity from $O(k^{2})$ to $O(k\cdot\log k)$ , i.e., from $O(4^{D})$ to $O(2^{D}D)$ .

Figure 5: Python implementation of StrassenLikeMult . Here, $M_{\text{diag}}$ is a NumPy array of length $2^{D}$ containing the secondary diagonal of $M$ , $f$ is a NumPy array of length $2^{D}$ , and $D$ is the tree depth. The function computes $M\cdot f$ , see Appendix B for intuition and further details.

Figure 6: Mathematical justification for merging all same‑feature splits into a single constraint.

Task	Algorithm	$d{=}6$	$d{=}9$	$d{=}12$	$d{=}15$	$d{=}18$	$d{=}21$
Background SHAP	shap	33 days	61 days	97 days	134 days	173 days	209 days
	pltreeshap	186 sec	39 min	3.8 hrs	12.8 hrs*	X	X
	Woodelf	12 sec	84 sec	58 min	36 hrs*	X	X
	WoodelfHD	14 sec	47 sec	104 sec	285 sec	24 min	3 hrs
	WoodelfHD GPU	18 sec	44 sec	99 sec	171 sec	4.6 min	12 min
Background SHAP IV on $10\,000$ samples	pltreeshap	63 sec	383 sec	33 min	X	X	X

Table 4: Runtime of Background SHAP and Background SHAP IV as a function of tree depth for different algorithms, evaluated on the IEEE-CIS dataset. Columns

d{=}6

d{=}9

, etc. correspond to trees of depths 6, 9, and so on. “X” indicates runs that failed due to excessive memory usage (>50GB RAM). Background SHAP IV is not implemented in shap and thus omitted. Runtime estimation details: entries marked with * were measured on a single tree and extrapolated. Running times for shap were measured using a background dataset of size 10 and extrapolated.

		add $x_{1}$
		add $x_{2}$		add $x_{2}$
add $\neg x_{1}$	add $\neg x_{2}$	$\emptyset$	$\emptyset$	$\emptyset$	$(\neg x_{1}\wedge\neg x_{2})$
add $\neg x_{1}$		$\emptyset$	$\emptyset$	$(\neg x_{1}\wedge x_{2})$	$(\neg x_{1})$
	add $\neg x_{2}$	$\emptyset$	$(x_{1}\wedge\neg x_{2})$	$\emptyset$	$(\neg x_{2})$
		$(x_{1}\wedge x_{2})$	$(x_{1})$	$(x_{2})$	$()$

Figure 7: Example of the

M_{\text{cubes}}

matrix for

x_{1}

and

x_{2}

			add $x_{1}$
			add $x_{2}$				add $x_{2}$
			add $x_{3}$		add $x_{3}$		add $x_{3}$		add $x_{3}$
add $\neg x_{1}$	add $\neg x_{2}$	add $\neg x_{3}$	$\emptyset$	$\emptyset$	$\emptyset$	$\emptyset$	$\emptyset$	$\emptyset$	$\emptyset$	$(\neg x_{1}\wedge\neg x_{2}\wedge\neg x_{3})$
	add $\neg x_{2}$		$\emptyset$	$\emptyset$	$\emptyset$	$\emptyset$	$\emptyset$	$\emptyset$	$(\neg x_{1}\wedge\neg x_{2}\wedge x_{3})$	$(\neg x_{1}\wedge\neg x_{2})$
		add $\neg x_{3}$	$\emptyset$	$\emptyset$	$\emptyset$	$\emptyset$	$\emptyset$	$(\neg x_{1}\wedge x_{2}\wedge\neg x_{3})$	$\emptyset$	$(\neg x_{1}\wedge\neg x_{3})$
			$\emptyset$	$\emptyset$	$\emptyset$	$\emptyset$	$(\neg x_{1}\wedge x_{2}\wedge x_{3})$	$(\neg x_{1}\wedge x_{2})$	$(\neg x_{1}\wedge x_{3})$	$(\neg x_{1})$

Figure 8: Example of the

M_{\text{cubes}}

matrix for

x_{1},x_{2},x_{3}

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Figure 9: Recursive and vectorized multiplication, as formalized by Alg. 4 and Fig. 5 , applied to a simple example. The figure illustrates how the vectorized approach performs all computations at a given recursion depth using just two steps: one operating on the input vector during the downward pass, and one operating on the resulting vector during the upward propagation.

SHAP Feature Attribution

SHAP (SHapley Additive exPlanations) feature attribution assigns model predictions to input features using Shapley values from cooperative game theory.

See all 36 papers

Woodelf++: A Fast and Unified Partial Dependence Plot Algorithm for Decision Tree Ensembles
May 14, 2026Ron Wettenstein, Alexander Nadel, Udi BokerFeature Interaction Modeling
Reichman University, Herzliya, Israel · Faculty of Data and Decision Sciences, Technion, Haifa, Israel
Quadrature-TreeSHAP: Depth-Independent TreeSHAP and Shapley Interactions
May 6, 2026Ron Wettenstein, Rory Mitchell, Peng YuNumerical Integration SHAP Feature Attribution
Reichman University, Herzliya, Israel · Nvidia Corporation · Shopify
qshap: Fast Shapley Decomposition of $R^2$ for Gradient-Boosted Trees
Aug 25, 2026Zhongli Jiang, Min Zhang, Dabao ZhangFeature Attribution Shapley Value Attribution
University of California, Irvine

May 14, 2026J/K move · Enter open · S save

Woodelf++: A Fast and Unified Partial Dependence Plot Algorithm for Decision Tree Ensembles

Ron Wettenstein, Alexander Nadel, Udi Boker

Reichman University, Herzliya, Israel · Faculty of Data and Decision Sciences, Technion, Haifa, Israel

Feature Interaction Modeling

Open paper AskPDF arXiv

Partial Dependence Plots (PDPs) visualize how changes in a single feature affect the average model prediction. They are widely used in practice to interpret decision tree ensembles and other machine learning models. Joint-PDPs extend this idea to pairs of features, revealing their combined effect. Partial Dependence Interaction Values (PDIVs) measure feature interactions. The Any-Order-PDIVs task computes these interactions for every feature subset across all rows of the dataset. We introduce Woodelf++, a unified and efficient approach for computing all these useful explainability tools on decision tree ensembles, building on Woodelf, an algorithm for efficient SHAP computation. By deriving suitable metrics over pseudo-Boolean functions, Woodelf++ can compute PDPs (exact and approximate), Joint-PDPs, and Any-Order-PDIVs in a unified framework. Our method delivers substantial complexity improvements over the state of the art, including an exponential gain for Any-Order-PDIVs. Additionally, we introduce and efficiently compute Full PDPs, which leverage the model's split thresholds to faithfully capture its behavior across all possible feature values. Woodelf++ is implemented in pure Python and supports GPU acceleration. On a dataset with 400,000 rows, Woodelf++ computes PDP and Joint-PDP up to 6x faster than the state of the art and up to five orders of magnitude faster than scikit-learn. For Any-Order-PDIVs, the gap is even larger: Woodelf++ computes all interaction values in 5 minutes, while the state of the art is estimated to require over 1,000,000 years.

Abstract

SHAP Feature Attribution

Explore similar work

Woodelf++: A Fast and Unified Partial Dependence Plot Algorithm for Decision Tree Ensembles

Quadrature-TreeSHAP: Depth-Independent TreeSHAP and Shapley Interactions

qshap: Fast Shapley Decomposition of R2R^2R2 for Gradient-Boosted Trees

qshap: Fast Shapley Decomposition of $R^2$ for Gradient-Boosted Trees