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

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$, rendering them impractical for deep trees. We address this limitation with WoodelfHD, an extension of WoodelfHD 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)$ through a fully vectorized, non-recursive implementation. In addition, we merge path nodes with identical features, further reducing cache size and memory usage. When run in standard environments, WoodelfHD enables exact Background SHAP computation for tree models with depths up to $21$, whereas previous methods fail due to excessive memory usage. For ensembles with depths of $12$ and $15$, it achieves speedups of $33\times$ and $162\times$, respectively, over the state of the art.