- Rating
- 3
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper proposes WOODELF-HD. Building upon the original WOODELF framework and leveraging the block identities of the M-matrix M1=0 and M4=M2+M3, it reduces the matrix-vector multiplications per leaf from four blocks to two via recursion, and observes that the final computation depends only on the off-diagonal blocks of the matrix, thereby reducing memory consumption from O(3^D) to O(2^D). Meanwhile, the authors introduce the Unique Feature Decision Pattern (UFDP) to merge same-feature splits along paths, and compare the runtime and memory performance of WOODELF-HD against SHAP, PLTREESHAP, and WOODELF on four datasets including IEEE-CIS.
Critical strengths
-
The observation of algebraic structures in this paper is quite profound. In particular, the insight that "the recursive property of M-matrices ultimately reduces to a single anti-diagonal" not only yields implementation-level acceleration but also unifies linear contribution functions such as SHAP, Banzhaf, and interaction indices under the same acceleration framework. Compared to mere engineering optimizations, this represents a universally applicable algorithmic insight.
-
The experiments cover a broad range, including not only IEEE-CIS but also HIGGS, KDD-99, and California Housing, spanning diverse scenarios such as large-scale, high-dimensional, and few-feature settings. The hyperparameter tuning experiments in the appendix further demonstrate that deep trees are common in practice, strengthening the problem motivation. The results show that the proposed method has significant practical value in medium-to-high depth scenarios of Background SHAP. Notably, depths 18 and 21 can achieve exact computation within a 50GB environment, demonstrating clear advantages over existing methods.
Critical weaknesses
- As shown in Table 3, at depth 12, WOODELF is the fastest baseline, taking 104 seconds, which is approximately 33× faster than 58 minutes; at depth 15, PLTREESHAP is the fastest baseline, taking 285 seconds, which is approximately 162× faster than 12.8 hours. In other words, the "state of the art" points to different algorithms at depths 12 and 15. This can easily mislead readers into thinking that it is always relative to the same strongest baseline.
- The single-tree extrapolation assumes a strictly linear relationship between runtime and the number of trees, but in practice, factors such as cache, scheduling, and memory pressure can violate this assumption. For comparative experiments claiming to be "state of the art", it is recommended to report the true full runtime at least in small-scale, completable settings, and to conduct a sensitivity analysis of the extrapolation error.
- The core contribution of this paper is precisely making depth 18/21 computable, yet it does not provide correctness comparisons with SHAP, brute-force computation, or other independent implementations at these high depths. Since existing methods are unavailable at high depths, the authors could at least construct verifiable scenarios on artificial models with a low number of features but high tree depths, because SHAP or brute-force computation remains feasible in such cases. Otherwise, the correctness at high depths relies mainly on theoretical soundness rather than experimental evidence.
- The main text and Tables 1–2 express complexity using tree depth D instead of the D_u that really works.
Some typoes:
- Change "50GM RAM" to "50GB RAM" throughout the text.
- Unify the spelling of "PLTreeSHAP" and "PLTREESHAP". It is recommended to standardize on one form and maintain consistency throughout the text.
Questions for authors
- Please report the speedup relative to each baseline separately and explain the selection criteria for the "state of the art" at each depth. At the same time, please explain the specific error ranges for the extrapolation of * and SHAP in Table 3, and it would be best to supplement with actual runs rather than extrapolated results.
- Please provide correctness evidence at high depth. For example, construct an artificial decision tree with a low number of features and high tree depth, so that SHAP or brute-force computation can still run, and report the maximum error between WOODELF-HD and the reference results.
- Please explicitly use D_u to express complexity in the main text and the complexity table, or annotate its actual meaning next to D.
2 comments
Official Comment by Reviewer UYdu
Thank you for clarifying the baseline comparisons and complexity bounds, and for adding correctness checks at high tree depths. These revisions address most of my concerns, and I stand by my positive assessment. Good luck!
Additional Benchmarks, Empirical Correctness Checks, and Complexity Refinements
Thanks for the review!
Raised Weaknesses:
In the revision, we changed the phrasing to “For Background SHAP on CPU, WoodelfHD significantly outperforms the fastest baseline at every depth from 9 onward, achieving a 33x speedup over Woodelf at depth 12 and a 162x speedup over PLTREESHAP at depth 15.”
We added Appendix E.1, which evaluates every Background SHAP setting in Tables 3 and 6 on a single tree: the first tree from each 100-tree model. Results are in Table 8. No runtimes are extrapolated across trees. Only the shap runtimes are still estimated: we use 10 background rows and extrapolate. On California Housing, shap uses the entire training set as the background dataset, so no estimation is needed there. On a single tree, WoodelfHD remains the fastest CPU method in all but one setting. On IEEE-CIS, for example, WoodelfHD is 52x faster than the fastest baseline at depth 12 (vs Woodelf) and 233x faster at depth 15 (vs PLTREESHAP). On 100 trees, the corresponding speedups in Table 3 are 33x and 162x. The only exception is at depth 6 on HIGGS, where Woodelf is 1.2–1.3× faster, as in Table 6. On California Housing, where the shap package runs on the full background dataset, WoodelfHD is 96x–460x faster.
Thanks for the suggestion! The shap package supports computation at any depth (it's just slower than WoodelfHD), so there is no reason not to repeat the depth-9 LightGBM empirical verification at higher depths. In the revised paper, this is exactly what we did. In Appendix E.5, path-dependent SHAP and background SHAP were validated at depths 6, 9, 12, 15, 18, and 21, and path-dependent SHAP IV was validated at depths 6, 9, 12, 15, and 18. We did not test depth-21 interactions because WoodelfHD needs over 50 GB of memory in this case. For background interactions, which shap does not support, we kept the existing depth-6 XGBoost tests. All tests pass with a tolerance of 10−5.
WoodelfHD's time and space complexities in Tables 1 and 2 of the main paper now use Du instead of D. We also updated Appendix D, which analyzes WoodelfHD's complexity for a generic contribution function v, to use Du instead of D. Thanks for the suggestion, these complexity bounds are tighter than before.
We fixed the typos. We are sticking with “PLTREESHAP”.
Questions