Skip to main content
Back

WoodelfHD Delivers 162x Speedup Making XGBoost Explanations Actually Usable

A Strassen-inspired trick shrinks SHAP's exponential cost from 3^D to 2^D, making exact feature attributions practical for deep tree ensembles.

Pro

  • WoodelfHD reduces Background SHAP's exponential preprocessing cost from 3^D to 2^D via a Strassen-like scheme.
  • Achieves 33x speedup at depth 12 and 162x at depth 15 on IEEE-CIS fraud detection.
  • Enables exact Background SHAP computation up to depth 21 where prior methods run out of memory.
  • Key trick: exploit M matrix structure to store only the secondary diagonal, cutting memory dramatically.
  • Vectorized non-recursive implementation uses O(D) NumPy operations instead of 2^D recursive calls.
  • Available now in the Woodelf Python package as the default implementation.

Explaining predictions from tree ensembles like XGBoost and LightGBM usually means running SHAP, and the most accurate flavor, Background SHAP, has always come with a nasty scaling problem. A new algorithm called WoodelfHD tackles the worst part of that problem, delivering a 162x speedup at tree depth 15 and pushing exact computation into territory that previous methods could not reach.

The exponential wall in tree explanations

SHAP treats a model's prediction as a cooperative game and hands out credit to each feature using Shapley values. 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. The background variant is more faithful, but historically it scaled badly.

The naive implementation in the popular shap package has an O(mn) term, where m is the size of the background dataset and n is the number of instances you want to explain. The PLTreeSHAP algorithm reduces this to O(m+n) by preprocessing the decision tree and the background dataset. A more recent algorithm, Woodelf, matches that O(m+n) scaling and adds numerical stability plus GPU support.

Both PLTreeSHAP and Woodelf hit a different wall: their preprocessing cost grows as 3^D with tree depth D. In practice, this makes the algorithms difficult to use once the maximum depth exceeds about 12, as runtimes climb sharply and memory requirements typically become prohibitive. Although limiting tree depth is a common way to control overfitting, deep trees are still frequently used in practice. LightGBM, for example, employs a leaf-wise (depth-first) growth strategy by default and imposes no explicit depth limit.