- 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
-
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.
-
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
- 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.
- 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
- 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.
- 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.
- 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.
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,…,fa, applying Eq. 11 at every edge whose split feature is in S 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 p and the variables pe and pe↑ to q, qe and qe↑. This makes more sense, as they store the qiv values defined in Eq. 2, and it avoids a clash with p, 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⌉).
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, which can be compared directly with float32 unit roundoff (5.96×10−8); it stays near 10−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.