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

May 14, 2026

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

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.

Ron Wettenstein, Alexander Nadel, Udi Boker

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

Feature Interaction Modeling

Ask PDF

May 6, 2026

Quadrature-TreeSHAP: Depth-Independent TreeSHAP and Shapley Interactions

Shapley values are a standard tool for explaining predictions of tree ensembles, with Path-Dependent SHAP being the most widely used variant. Despite substantial progress, existing methods still exhibit trade-offs between depth-dependent runtime, numerical stability, and support for higher-order interactions. To address these challenges, we introduce Quadrature-TreeSHAP, a quadrature-based reformulation of Path-Dependent TreeSHAP that is numerically stable, naturally extends to any-order Shapley interaction values and is practically insensitive to tree depth. Our implementation supports both CPU and GPU and is integrated into XGBoost. Our method is based on a weighted-Banzhaf interaction polynomial, which expresses Banzhaf interaction values as expectations under a feature participation probability

p

. Shapley values and any-order interaction values are then recovered by integrating these polynomials over

p

from 0 to 1. We evaluate these integrals using Gauss-Legendre quadrature, and show that, in practice, only 8 fixed quadrature points are sufficient to reach machine precision. In fact, Quadrature-TreeSHAP with 8 fixed points achieves greater numerical stability than TreeSHAP. This fixed-point formulation removes depth dependence from the inner computation and enables efficient SIMD execution. We confirm these advantages empirically. On 12 XGBoost benchmarks, Quadrature-TreeSHAP computes Shapley values 1.06x-10.59x faster than TreeSHAP on CPU and 1.84x-6.95x faster than GPUTreeSHAP on GPU. Shapley pairwise interactions are 3.80x-58.11x faster on CPU, with higher-order interactions achieving speedups of up to 1200x compared to TreeSHAP-IQ.

Ron Wettenstein, Rory Mitchell, Peng Yu

Reichman University, Herzliya, Israel · Nvidia Corporation · Shopify

Numerical Integration SHAP Feature Attribution Shapley Value Attribution

Ask PDF

Aug 25, 2026

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

Numerous methods have been developed to quantify feature attributions in individual predictions for tree ensembles. However, many applications require global measures of feature contributions to overall model performance. Although local attribution scores can be aggregated to characterize feature importance, such summaries do not directly decompose measures of predictive performance, such as

R^2

. This article introduces qshap, available in both R and Python, which provides Shapley decomposition of

R^2

values for gradient-boosted decision trees (GBDTs) to quantify feature-specific contributions to model performance. By decomposing the quadratic loss of individual observations, qshap provides flexible tools to explore the importance of individual features and observations. qshap currently supports widely used GBDT implementations, including xgboost, lightgbm, and catboost, through a unified tree representation and efficient C++ backends. Its modular design can accommodate other GBDT implementations built from binary decision trees. In addition, we introduce a specialized backend for oblivious trees that exploits their symmetric structure to substantially accelerate computation.

Zhongli Jiang, Min Zhang, Dabao Zhang

University of California, Irvine

Feature Attribution Shapley Value Attribution

Ask PDF

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