🤖 machine learning

Quadrature-TreeSHAP: Depth-Independent TreeSHAP and Shapley Interactions

The paper introduces Quadrature-TreeSHAP, a numerically stable, depth-independent method that reformulates Path-Dependent TreeSHAP using Gauss-Legendre quadrature to efficiently compute Shapley values and high-order interactions with significant speedups on both CPU and GPU.

Original authors: Ron Wettenstein, Rory Mitchell, Peng Yu

Published 2026-05-07

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Ron Wettenstein, Rory Mitchell, Peng Yu

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a very smart, but complicated, decision-making machine (like a tree that has grown thousands of branches). You want to know exactly why it made a specific prediction. Did it decide "Yes" because of Feature A? Or was it a team effort between Feature B and Feature C?

To answer this, data scientists use a mathematical tool called SHAP. Think of SHAP as a way to fairly split the "credit" for the prediction among all the features, like dividing a pizza based on who brought the most ingredients.

For a long time, the standard way to do this (called TreeSHAP) had three main problems:

It was slow: The deeper the tree grew, the longer it took to calculate the credits. It was like trying to count every single leaf on a giant oak tree one by one.
It was shaky: As trees got deeper, the math started to get messy and inaccurate, like trying to balance a tower of Jenga blocks that keeps wobbling.
It missed the big picture: It was great at explaining single features, but very slow and clunky when trying to explain how features worked together (interactions).

The authors of this paper introduced a new method called Quadrature-TreeSHAP. Here is how it works, using simple analogies:

1. The "Snapshot" vs. The "Movie"

Old methods tried to calculate the credit by walking through every single path of the tree, step-by-step. If the tree was deep, this took forever.

Quadrature-TreeSHAP changes the game. Instead of walking the whole tree, it treats the calculation like a movie. It realizes that the math behind the tree is actually a smooth, predictable curve (a polynomial).

Instead of watching the whole movie frame-by-frame, this new method takes 8 specific "snapshots" (mathematically called quadrature points) of the curve.

The Magic: The authors proved that for these tree models, taking just 8 snapshots is enough to reconstruct the entire movie with perfect accuracy.
The Result: It doesn't matter if the tree is 10 levels deep or 100 levels deep. The method still only needs those same 8 snapshots. It completely ignores the depth, making it incredibly fast and consistent.

2. The "Stable Bridge"

The old method was like building a bridge out of wobbly, uneven planks. As the bridge got longer (deeper trees), the planks would shift, and the math would collapse (numerical instability).

The new method builds the bridge using smooth, solid concrete. By calculating the answer at those 8 fixed points, it avoids the "wobbly planks" entirely. The result is a calculation that stays perfectly stable, even on the deepest, most complex trees.

3. The "Teamwork" Superpower

The old method struggled to explain how features worked together (e.g., "Feature A and Feature B together caused the result"). It was like trying to count how many people are in a room by asking them to line up in pairs, then groups of three, then groups of four—it got exponentially slower.

Quadrature-TreeSHAP handles this effortlessly. Because it uses the same "8 snapshot" trick for groups of any size, it can calculate complex teamwork interactions (3-way, 4-way, or even 6-way) almost instantly.

The Speed: In their tests, calculating these complex interactions was up to 1,200 times faster than the previous best method.

4. The "Assembly Line" (Hardware Efficiency)

Finally, the authors made this method friendly for modern computer chips (CPUs and GPUs).

The Analogy: Imagine a factory assembly line. The old method was like a worker who had to stop and think about every single item differently. The new method is like a machine that processes 8 items at the exact same time in a perfect rhythm.
The Result: Because the math is so regular, it runs super efficiently on both standard computers and powerful graphics cards (GPUs), leading to speedups of up to 10x on standard computers and 7x on graphics cards.

Summary of Results

The authors tested this on 12 different real-world datasets (like predicting housing prices or identifying objects in photos).

Speed: It is consistently faster than the old methods, sometimes by a factor of 10.
Stability: It doesn't break or get inaccurate, even on very deep trees where the old methods failed.
Adoption: They have already built this into XGBoost, one of the most popular machine learning tools in the world. If you use XGBoost in the future, this new, faster, and more stable way of explaining your models will be built right in.

In short: Quadrature-TreeSHAP is like upgrading from a slow, shaky, manual calculator to a high-speed, super-stable digital computer that can solve complex teamwork puzzles in a blink of an eye.

Technical Summary: Quadrature-TreeSHAP

Problem Statement

Explainability for tree ensemble models (e.g., XGBoost, Random Forests) relies heavily on Shapley values. While Path-Dependent SHAP is the standard approach due to its efficiency, existing methods face significant trade-offs regarding depth-dependent runtime, numerical stability, and support for higher-order interactions.

Current state-of-the-art methods exhibit specific limitations:

TreeSHAP and GPUTreeSHAP operate with a time complexity of $O(MTLD^2)$ (where $M$ is samples, $T$ trees, $L$ leaves, $D$ depth).
FastTreeSHAP v2 and Woodelf reduce complexity to $O(MTLD)$ but introduce preprocessing steps exponential in depth, rendering them impractical for deep trees.
Linear TreeSHAP achieves $O(MTND)$ but suffers from numerical instability due to operations in the monomial basis.
TreeGrad-Shap improves stability via gradient formulations but is limited to first-order attributions.
TreeSHAP-IQ extends to higher-order interactions but has a complexity of $O(MTLD \binom{F-1}{s-1})$ , which scales poorly as the number of features ( $F$ ) and interaction order ( $s$ ) increase.

Methodology

The authors propose Quadrature-TreeSHAP, a reformulation of Path-Dependent TreeSHAP based on Gauss–Legendre quadrature and a weighted-Banzhaf interaction polynomial.

1. Theoretical Foundation

The method leverages the relationship between Shapley values and weighted Banzhaf values.

Weighted Banzhaf Polynomial: For a decision tree leaf $v$ , the Path-Dependent weighted Banzhaf interaction value for a feature subset $S$ at inclusion probability $p$ is expressed as a polynomial $B^{(S)}_{p,v}$ . This polynomial is derived from the leaf's path structure and edge weights.
Integral Recovery: Shapley interaction values are recovered by integrating these Banzhaf polynomials over the participation probability $p \in [0, 1]$ :
$SII^{(S)}(f_v) = \int_0^1 B^{(S)}_p(f_v) \, dp$
Quadrature Approximation: Instead of symbolic integration, the authors evaluate this integral using Gauss–Legendre quadrature. The integral is approximated as a weighted sum of the polynomial evaluated at fixed nodes $t_m$ :
$SII^{(S)}_v \approx \sum_{m=1}^n w_m B^{(S)}_{t_m, v}$

2. Algorithmic Implementation

Fixed-Point Formulation: The algorithm performs a single depth-first traversal (DFS) of the tree. During traversal, it propagates the values of the path polynomial at a fixed set of Gauss–Legendre nodes (typically 8) rather than expanding polynomials symbolically.
Complexity Reduction:
- Theoretically, the degree of the integrand for order- $s$ interactions is at most $d-s$ (where $d$ is the maximum unique features on a path).
- Practically, the authors demonstrate that 8 fixed quadrature points are sufficient to reach machine precision (float32) even for very deep trees.
- This removes the dependence on tree depth $d$ from the inner computation, reducing effective complexity from $O(MTN \lceil d/2 \rceil)$ to $O(MTN)$ for first-order, and from $O(MTN d^s)$ to $O(MTN d^{s-1})$ for order- $s$ interactions.
Hardware Acceleration: Because the computation involves evaluating the same fixed set of points for every path, the arithmetic is regular. This allows for efficient SIMD (Single Instruction, Multiple Data) execution on CPUs and SIMT (Single Instruction, Multiple Threads) on GPUs, eliminating the bin-packing and scheduling overhead required by GPUTreeSHAP.

Key Contributions

Any-Order Interaction Algorithm: The paper presents an algorithm for computing any-order Shapley interaction values that improves the state-of-the-art complexity of TreeSHAP-IQ from $O(MTLD \binom{F-1}{s-1})$ to $O(MTN d^s)$ . This yields substantial gains when the number of features exceeds the tree depth ( $F > D \ge d$ ).
Quadrature-Based Reformulation: The authors provide a theoretical and empirical analysis showing that 8 Gauss–Legendre points are sufficient to reach machine precision for Shapley values and interactions, effectively decoupling runtime from tree depth in practice.
Numerical Stability: By evaluating the summary polynomial at bounded, positive nodes rather than expanding coefficients in a monomial basis, the method avoids catastrophic cancellation. The authors claim Quadrature-TreeSHAP is more numerically stable than TreeSHAP, particularly for deep ensembles.
Hardware-Efficient Implementation: The method is implemented in C++ for CPU and integrated into XGBoost for GPU. It exploits vectorization (4 points on CPU, 32 on GPU) to achieve significant speedups over existing implementations.
Open Source Integration: The implementation is open-sourced and integrated into the XGBoost library (replacing the TreeSHAP backend), accessible via standard API calls (pred_contribs=True and pred_interactions=True).

Experimental Results

The authors evaluated Quadrature-TreeSHAP on 12 XGBoost benchmark ensembles (Adult, CalHousing, CovType, Fashion-MNIST) across small, large, and sparse regimes.

First-Order (Shapley Values):
- CPU: 1.06× to 10.59× faster than TreeSHAP (median 3.84×).
- GPU: 1.84× to 6.95× faster than GPUTreeSHAP.
Second-Order (Pairwise Interactions):
- CPU: 3.80× to 58.11× faster than TreeSHAP (median 12.86×).
- GPU: Up to 6.65× faster than GPUTreeSHAP (though GPUTreeSHAP remained competitive on specific small-depth workloads).
Higher-Order Interactions (Python Benchmarks):
- Compared against TreeSHAP-IQ on third-order interactions, Quadrature-TreeSHAP was 18.73× to 26.49× faster.
- On the CovType-sparse dataset, the speedup over TreeSHAP-IQ increased with interaction order, reaching 1209.37× at order 6.
Numerical Stability:
- On the Fashion-MNIST-sparse benchmark with increasing tree depth, TreeSHAP became unstable beyond depth 32. Quadrature-TreeSHAP remained stable, with 6–8 points achieving high accuracy.

Significance

The paper claims that Quadrature-TreeSHAP offers a numerically stable, hardware-efficient, and interaction-aware reformulation of Path-Dependent SHAP. By shifting from symbolic polynomial arithmetic to fixed-point quadrature, the method resolves the trade-off between depth dependence and numerical stability. It enables the efficient computation of high-order interactions on deep trees, a task previously hindered by the exponential complexity or instability of prior methods. The integration into XGBoost ensures immediate practical utility for users of the library and the broader shap package.