acceptodds
Under review as a conference paper at ICLR 2027

Quadrature-TreeSHAP: Fast and Stable Shapley Values and Interactions at Any Depth

14 views

Abstract

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 . Shapley values and any-order interaction values are then recovered by integrating these polynomials over from 0 to 1. We evaluate these integrals using Gauss–Legendre quadrature, and show that, in practice, only fixed quadrature points are sufficient to reach machine precision. In fact, Quadrature-TreeSHAP with 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 to faster than TreeSHAP on CPU and to faster than GPUTreeSHAP on GPU. Shapley pairwise interactions are to faster on CPU, with higher-order interactions achieving speedups of up to compared to TreeSHAP-IQ.

Primary area:
interpretability and explainable AI
Keywords:
SHAP, Shapley, TreeSHAP, explainability, decision trees, Gauss Legendre

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_Ze6BOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper introduces Quadrature-TreeSHAP, a method for computing path-dependent Shapley values and higher-order feature interactions in tree ensembles. It expresses weighted Banzhaf interactions as polynomials in the feature participation probability and integrates them using Gauss–Legendre quadrature to recover Shapley interactions. The algorithm evaluates these polynomials during a depth-first traversal, with updates that handle repeated features along a path. Its first-order computation is algebraically equivalent to TreeGrad-Shap, while the proposed formulation extends to arbitrary interaction orders.

The authors derive a condition on the number of quadrature points needed for exact integration, but use a fixed eight-point rule in practice to reduce computation and support efficient parallel execution. They provide CPU and GPU implementations for first- and second-order interactions and a Python implementation for higher orders. Experiments cover 12 XGBoost ensembles across four datasets, with runtime comparisons against TreeSHAP, GPUTreeSHAP, and TreeSHAP-IQ. The reported results show substantial speedups, particularly for interaction values, while numerical experiments on deep Fashion-MNIST models show small attribution errors with eight quadrature points. These accuracy results are empirical rather than a general guarantee for the fixed eight-point rule.

Critical strengths
  1. A useful formulation for higher-order interactions. The weighted-Banzhaf formulation gives a common approach to computing individual Shapley values and higher-order interactions. Theorem 2 makes the dependence of the required quadrature count on the interaction order and the number of distinct path features explicit. This is useful because it provides a way to accelerate interaction computations, rather than improving only first-order attributions.

  2. Substantial practical runtime improvements. The paper goes beyond a mathematical reformulation and evaluates CPU and GPU implementations. Tables 2 and 3 report both absolute runtimes and speedups, with CPU improvements of 1.06–10.59× for first-order values and 3.80–58.11× for pairwise interactions on the benchmarks with available baselines. These results suggest a useful reduction in explanation costs, particularly for interaction values.

Critical weaknesses
  1. The evidence for the fixed eight-point rule is promising but concentrated on a narrow set of models.

The paper does evaluate numerical accuracy on deeper trees: Figure 1 and Appendices A.2–A.3 report results on Fashion-MNIST models with depths up to 50. However, Table 1 shows that 10 of the 12 benchmark models have maximum distinct-feature depth (d <=16), for which eight-point Gauss–Legendre quadrature is already exact for first-order values by Theorem 2. Thus, most runtime benchmarks do not test the accuracy of the fixed rule beyond its exactness regime, while the deeper-tree accuracy evidence comes primarily from one dataset and model family. Evaluating the eight-point rule on additional datasets or tree structures with (d>16), and reporting errors relative to an appropriate attribution or prediction scale, would better support the claim that eight points are sufficient in practice.

  1. The new algorithmic contribution needs clearer explanation and stronger validation.

The paper acknowledges that its first-order algorithm is algebraically equivalent to TreeGrad-Shap, so the higher-order extension is particularly important to the contribution. However, Section 5 does not explain clearly enough how the leaf-level expression in Eq. (10) becomes the recursive update in Eq. (11) and Algorithm 1. For repeated split features, the reader is given factor replacement, state restoration, and contribution updates, but little guidance on how these operations fit together. A worked example following a small tree through to a pairwise interaction value would make this substantially easier to understand.

Both figures report experimental outcomes; neither illustrates the computation. This is not a request for a particular figure format. The problem is that the reader has to reconstruct the connection between the mathematical expression and the implementation. A clear update invariant or a worked derivation is especially important for checking that repeated features are handled correctly.

The experimental evidence does not fully resolve this concern. The higher-order experiments mainly report runtimes on a single explained row, whereas the numerical accuracy analysis focuses on first-order attributions. A comparison with directly enumerated Shapley interaction indices on small trees would provide a more direct check of the higher-order recursion. A lower polynomial degree alone does not validate the recursive implementation or establish its floating-point accuracy.

The first-order comparison in Appendix A.1 also uses different quadrature counts for the two implementations. It therefore does not isolate the effect of fixing the quadrature count from other implementation differences. A comparison using the same quadrature count and numerical precision would help establish what accounts for the reported advantage over the closest method.

The runtime improvements and higher-order formulation are promising. However, the current evidence does not adequately establish when the fixed eight-point approximation is reliable, and the higher-order algorithm needs a clearer explanation and more direct correctness checks. The comparison with the closest first-order method also leaves the source of the speedup uncertain. I therefore lean toward rejection in its current form. Clarifying the accuracy conditions, validating the repeated-feature updates, and providing a matched comparison could change my assessment.

Questions for authors
  1. Accuracy of the eight-point rule

What evidence or criterion supports using eight quadrature points for a given model and input? Does the implementation include an accuracy check or a fallback to a model-dependent number of points? Please distinguish the exactness guarantee from the empirical results for eight points, and clarify how attribution scale is accounted for when comparing absolute errors with float32 unit roundoff.

  1. Higher-order updates and repeated features

Could you provide an invariant or derivation connecting Eq. (11) and Algorithm 1 to the leaf-level formula in Eq. (10), particularly when a feature appears repeatedly along a path? A small worked tree example and a comparison against directly enumerated second- and third-order interaction indices on small trees would help verify the implementation.

  1. Comparison with TreeGrad-Shap

Could you report a comparison using the same number of quadrature points and numerical precision for both implementations? Please clarify whether the nodes are also matched, and separate the effects of quadrature budget from implementation choices such as vectorization and traversal overhead.

1 comment
AuthorsOpenReview ↗

Proof of Eq. 11, Accuracy with Eight Points, and Controlled Runtime Comparisons

Thanks for the detailed review and suggestions.

Empirical accuracy on high dimensional data given 8 quadrature points: We have expanded the adult dataset with one-hot encoding (14 features expanded to 124), which brings it up to d=25-27 (depending on seed). The deep-tree experiment of Figure 1, up to max depth 50, now shows all 4 datasets, with achieved unique features d=8, 19-20, 25-27, 40-42. Error is now reported on a relative scale. In practice it is difficult to generate trees with high numbers of distinct features because the learner prefers to repeatedly split on small groups of informative features.

Proof of the telescoping update in Eq. 11 and of Alg. 1: Thank you for pointing out this gap. We have added Appendix D, where we formally derive Eq. 11 from Theorem 1 and Eq. 10. We show that for any interaction set S=f1,…,faS = \\{f_1, \dots, f_a\\}, applying Eq. 11 at every edge whose split feature is in SS as we traverse down the tree, including repeated splits on the same feature, telescopes to exactly the leaf-level term of Eq. 10. Summing over the leaves, the traversal therefore gives the same result as applying Eq. 10 to every leaf directly (Theorem 10).

Then, in the same appendix, we explain how Alg. 1 uses Eq. 11 to compute the Shapley values and interactions. To better connect the algorithm's notation to our math, we rename the array pp and the variables pep_e and pe↑p_{e^\uparrow} to qq, qeq_e and qe↑q_{e^\uparrow}. This makes more sense, as they store the qivq_i^v values defined in Eq. 2, and it avoids a clash with pp, the participation probability in Theorem 1. We hope this makes the connection between the formulation and the algorithm clearer.

Questions

Q1: Accuracy and implementation of the eight-point rule.

  • Implementation: Our XGBoost implementation always uses 8 points and always works in float32. Fixing the number of points at 8 enables a fast SIMD implementation (see Sec. 5.2): the C++ compiler needs to know the number of points at compile time to turn the loops into SIMD operations, which is why we do not accept the number of points as an input. There are ways around this, such as compiling several versions of the function for different numbers of points and choosing which one to call at runtime, but we decided to keep it simple for now. Our Python implementation supports any number of quadrature points (Appendix A.2 uses 8, 16 and ⌈d/2⌉\lceil d/2 \rceil).

  • Empirical accuracy: See the "Practical analysis" paragraph in Sec. 5.1 and Fig. 1. We also invite you to read Appendices A.2 and A.3, where we report our errors in float64 under several error metrics and show the accuracy with 16 quadrature points in addition to 8. To account for attribution scale, Fig. 1 now reports the relative error ∥Φ−Φref∥F/∥Φref∥F\lVert\Phi-\Phi^{\mathrm{ref}}\rVert_F/\lVert\Phi^{\mathrm{ref}}\rVert_F, which can be compared directly with float32 unit roundoff (5.96×10−85.96\times10^{-8}); it stays near 10−710^{-7} on all four datasets.

  • Theoretical bounds: These are discussed in Appendix B. We bound the error of a single leaf, discuss the rare cases where the error can get close to this bound, and provide a bound that depends only on the number of points and not on the depth.

Q2: A formal proof of Eq. 11 is provided in Appendix D. This proof also covers repeated features. Appendix G presents a running example of Alg. 1 to illustrate its steps and flow. In the main paper, we refer readers to this example after presenting the pseudo code for Alg. 1.

Q3: We have revised Appendix A.1 to compare variable-point and fixed-eight implementations using the same compiled traversal, precision, and compiler settings. Fixed-eight specialization gives 1.86–2.41× speedups on sparse models and 1.47–1.53× on large models for Adult, CovType, and Fashion-MNIST. The large and sparse California Housing models are 8–9% slower, and all small models are 18–22% slower, because the variable rule already requires only four and three points, respectively; fixing the count at eight increases the quadrature work.

Reviewer_iSZ9OpenReview ↗
Rating
4
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper proposes Quadrature-TreeSHAP, a quadrature-based approach to compuing Path-Dependent Shapley values and higher-order Shapley interactions for tree ensembles. The method expresses Shapley interactions through weighted Banzhaf polynomials and evaluates the resulting integrals using Gauss–Legendre quadrature in low order. The paper provides theoretical exactness conditions, an algorithm for arbitrary-order interactions, and CPU/GPU implementations. Experiments on 12 XGBoost benchmarks demonstrate substantial runtime improvements and promising numerical stability in practice.

Critical strengths
  1. The paper provides a clean formulation connecting weighted Banzhaf interaction polynomials with Path-Dependent TreeSHAP. The extension to arbitrary-order interactions is natural and theoretically justified.
  2. The method shows substantial computational improvements over existing methods, particularly for higher-order interactions. The CPU/GPU implementations and integration into XGBoost further strengthen its practical significance.
  3. The empirical finding that only 8 Gauss–Legendre quadrature points can achieve high numerical accuracy even for very deep trees is particularly interesting.
Critical weaknesses
  1. Although the paper provides additional theoretical error bounds, the fixed-eight-point approximation is not guaranteed to achieve machine precision for arbitrary trees. A discussion of potential corner cases where the approximation may fail to achieve high accuracy would be helpful.
  2. The runtime comparisons would be more convincing with repeated experiments and measures of variability. Given the relatively low computational cost of explaining, this should be straightforward, particularly when the reported speedup is as small as 1.06× in Table 2.
Questions for authors

Are there any numerical accuracy comparisons against TreeSHAP-IQ, in addition to the current first-order TreeSHAP comparison?

2 comments
AuthorsOpenReview ↗

Expanded Error Analysis and Comparisons with TreeSHAP-IQ

Thanks for your kind review and suggestions.

We have added repeats and standard deviations to all reported speedups.

Rare corner cases of numerical instability

We added Appendix B. 3 in which we discuss the rare cases where the error can come close to the bound we proved in Appendix B and shown in Table 9. These cases are:

  1. Large covers, and xx falsifies every split: a deep leaf that most training rows reach, and a row xx that falsifies every split on its path. Such an xx is an extreme outlier: most of the training set satisfies all these splits, while xx falsifies every one of them.
  2. Most covers are small, and xx satisfies every split: This is also rare as during training at least one training row must reach each leaf. For example, with 5050 path features and 1010 million training rows, even a leaf that only a single row reaches has covers with a geometric mean of 0.720.72. For 1717 path features, the depth when 8 qaudrature points stop being exact, the geometric mean is 0.390.39.

We explain how these cases translate to weighted Banzhaf polynomials with an area under the curve that is hard for Gauss–Legendre to approximate (see Figure 3).

QuadratureTreeSHAP vs TreeSHAP-IQ numerically stability

QuadratureTreeSHAP is substantially more numerically stable than TreeSHAP-IQ. TreeSHAP-IQ is an extension of Linear TreeSHAP, which is less numerically stable than TreeSHAP.

A related development: the maintainers of shapiq, the package that implements TreeSHAP-IQ, have recently adopted QuadratureTreeSHAP as their default path-dependent algorithm. The table below reports the maximum efficiency error ∣∑iϕi+ϕ0−f(x)∣\left|\sum_{i} \phi_i + \phi_0 - f(x)\right| of first-order Shapley values on Fashion-MNIST (leaf-wise XGBoost, 100 trees, 100 test rows × 10 classes). It compares our float64 implementation with shapiq 1.6.0, the last release before the switch to QuadratureTreeSHAP, and with the current release, shapiq 1.8.0.

Methodmax_depth 10max_depth 20max_depth 30max_depth 40max_depth 50
QuadratureTreeSHAP1.3e-152.2e-111.2e-89.4e-89.4e-8
shapiq 1.6.03.1e-82.0e-70.122.1e46.2e8
shapiq latest version3.1e-82.2e-82.2e-82.2e-82.2e-8

Thank you for your response. I have no further questions.

Reviewer_Ld1NOpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This work generalizes TreeGrad-Shap of Li et al. (ICLR'26) to any order interactions, and computes the resulting integral using a fixed-point Gauss-Legendre quadrature rule (with 8-point practically sufficient for most applications). Both CPU and GPU implementations have been incorporated into the XGBoost library. Numerical tests show the proposed implementation significantly improves previous baselines.

Critical strengths
  • a practically useful extension of the first-order observation of TreeGrad-Shap

  • carefully implemented and integrated to the existing XGBoost library

Critical weaknesses
  • If I had to name one, the theoretical contributions of this work feel slightly incremental. However, I do not consider this a big deal because the practical advantage is clear.
Questions for authors

Theorem 2 shows that the number of nodes required for exact computation decreases with the interaction size s, while Contribution item 2 and experiment Table 2 indicate that with a larger interaction size, runtime increases. It might be a good idea to add a comment on the total runtime right after Theorem 2, to clear things up.

This work seems to complement QuadraShap (Mohammadi et al., 2026). In particular, how does Corollary 6 in the appendix compare with Proposition 3 of QuadraShap? Could the authors offer some empirical comparisons between the two (on first order SHAP values)?

Minor comment:

Perhaps it'd be prudent to change "any depth" in the title to "practical depth"?

2 comments
AuthorsOpenReview ↗

Tighter Error Bounds and Clarified Higher-Order Complexity

Thanks for the review!

We added a paragraph right after Theorem 2 on the any-order complexity of Quadrature-TreeSHAP. In short, while the work per value can decrease, as fewer quadrature points are required, the number of values to compute grows with the order and thus the total complexity also increases.

Minor comment: We decided to delete the “at Any Depth” part of our title. Thanks for the suggestion, it's better and clearer this way.

QuadraSHAP bound vs ours bound

QuadraSHAP's bound builds on the classical Bernstein-ellipse error bound for Gauss–Legendre quadrature (Trefethen, 2013, Thm. 19.3). It aims for generality: one bound covers any product game. There is also an advantage in analyzing specific games, as their structure might be used to derive a tighter bound. Our bound uses the tree polynomial structure and derives the bound directly. This structure allows us to provide 20–750x smaller bounds than QuadraSHAP's: the table below demonstrates this by empirically comparing these two bounds at 4, 8, and 16 quadrature points and tree depths of 20, 30, 50 and 100. Additionally we just extended appendix B.3 that shows that our bound is tight (leaves can come arbitrarily close to it) and wrote appendix B.4 which bounds the error at any depth d. For example, the error of a single unit leaf can not exceed 4.17518×10−34.17518\times10^{-3} using 8 quadrature points, no matter the depth. This max error is reached at d=168. QuadraSHAP bound approaches infinity as d increases.

Worst case per unit leaf, Proposition 3 / Corollary 6:

ddn=4n=4n=8n=8n=16n=16
200.11 / 5.5e-32.2e-5 / 4.7e-88.0e-17 / 0 (exact)
300.37 / 1.2e-27.2e-4 / 1.5e-51.0e-12 / 0 (exact)
501.15 / 1.5e-21.9e-2 / 4.7e-41.6e-8 / 2.1e-11
1003.42 / 1.5e-20.34 / 3.0e-31.3e-4 / 1.8e-6
Reviewer_Ld1NOpenReview ↗

ack to the response

Thanks for the response and clarifying the bound against QuadraShap's. No more questions.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.