- Rating
- 3
- Confidence
- 2
- Informativeness
- 3
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
This paper proposes Sparse Forest, an efficient framework for online learning and unlearning in tree ensembles. It combines three sparsity mechanisms to reduce update costs: structural sparsity, in-place subtree repair, and suboptimal split retention.The method provides an exactness guarantee at zero tolerance and achieves substantial speedups over existing methods while maintaining comparable predictive performance.
Critical strengths
-
The paper addresses a practical and important problem in maintaining tree ensembles under frequent data updates.
-
The three sparsity mechanisms are complementary, and the paper provides a formal exactness guarantee.
-
The experiments cover multiple datasets and update settings, showing substantial efficiency improvements.
Critical weaknesses
-
Some runtime comparisons rely on estimated baseline results, and the main stream timings exclude final deferred repair.
-
The paper lacks a controlled end-to-end runtime ablation isolating the contributions of all three sparsity mechanisms.
-
The improved amortized update bound relies on additional conditions that are not guaranteed in general.
Questions for authors
-
How do the reported speedups change when only completed baseline runs are considered, without estimated results?
-
Can the authors provide an end-to-end runtime ablation to show how much each sparsity mechanism contributes to the overall speedup?
-
Can the authors clarify whether the improved amortized update bound can be guaranteed by the proposed algorithm, or whether it only holds under additional assumptions?
-
How often do reevaluations retain suboptimal splits without restoring sufficient slack, and how does this affect runtime?
4 comments
[2/2] Response to Reviewer 6oXU
[W3/Q3/Q4] Amortized update bound and reevaluation vs. repair trade-off
Thank you for raising this insightful point, as it gets to the core design trade-off between local reevaluation cost and repairing frequency. We clarify both the theoretical guarantee (W3/Q3) and the empirical behavior (Q4).
When is the update cost , , or ?
Let be the number of local updates (gap) at a node between two consecutive reevaluations. It is proven that reevaluation costs , or amortized per update, and improves over conventional update whenever and reaching once . Thus, the improved bound holds whenever , which reaches once which is common for large nodes (for typical and ):
- for .
- for the default .
- whereas yields a constant-factor gain .
Whether is guaranteed depends on the residual suboptimality gap left after reevaluation. As evaluated in Appendix D.2:
- Default (
normal) rule (not satisfied): Retains the installed split whenever . Because can lie arbitrarily close to (near-zero slack), the next reevaluation can trigger after updates in the worst case; thus, defaultSFdoes NOT unconditionally guarantee . - Slack-restoring rules (unconditionally satisfied): The bound can be strictly guaranteed simply by enforcing slack restoration at reevaluation via
always-repair: always installing the optimal split during reevaluation so .fractional-slack: retains the current split iff , guaranteeing at least slack and hence .
Trade off between frequency of reevaluation and frequency of repairing
Crucially, the cost only measures local updates, whereas changing an installed split triggers in-place subtree repair over descendants, which is sufficiently expensive: . To quantify this trade-off, we instrumented SF 0.1 on Higgs comparing default normal against always-repair:
| Metric | Variant | - | - | - | - | Overall | |||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| Avg. gap | normal | 129.07 | 94.02 | 62.33 | 39.94 | 27.65 | 8.64 | 2.41 | 1.43 | 1.24 | 4.04 |
always-repair | 164.83 | 246.49 | 296.77 | 299.69 | 285.66 | 179.43 | 52.96 | 9.53 | 2.40 | 74.66 | |
| # of reevaluations | normal | 38,817.4 | 53,365.2 | 80,592.2 | 126,019.4 | 182,583.0 | 3,019,004.2 | 22,829,026.0 | 12,990,207.0 | 703,665.8 | 40,023,280 |
always-repair | 30,437.4 | 42,715.0 | 60,696.2 | 87,996.2 | 124,346.2 | 1,985,276.4 | 17,198,113.6 | 7,055,018.6 | 256,782.8 | 26,841,382 | |
| # of repairs | normal | 0.0 | 0.0 | 0.0 | 0.0 | 0.2 | 328.4 | 130,855.6 | 199,531.0 | 12,894.0 | 343,609 |
always-repair | 84.6 | 240.6 | 506.0 | 1,174.8 | 2,523.0 | 138,483.2 | 1,990,342.4 | 599,112.2 | 11,470.2 | 2,743,937 | |
| Avg. repair size | normal | 0.0 | 0.0 | 0.0 | 0.0 | 60.00 | 56.83 | 35.00 | 30.05 | 28.00 | 31.88 |
always-repair | 1,232,154 | 584,897 | 300,184 | 141,949 | 74,388.4 | 8,692.09 | 836.01 | 217.25 | 124.79 | 1,366.85 | |
| Stream-processing time | normal | 61.39s | |||||||||
always-repair | 801.11s |
This experiment reveals a clear and important findings:
- Compared to
always-repair,normalperforms more reevaluations, yet triggers fewer repairs and shrinks average repair size by . Consequently,normalreduces total stream-processing time by , resulting in a speedup. - In
normal, reevaluations retain the split without repairing, while reevaluation necessitates a repair. - The overall average gap of
normalis (still improve the update by ), whereasalways-repairachieves , entering the local regime.
In short, while Sparse Forest can guarantee the bound via slack restoration, our default retention rule intentionally sacrifices worst-case local spacing to avoid expensive frequent repairs, which are the true end-to-end bottleneck. This result will be added to the appendix and discuss in the main text.
Best regards,
Author(s) of Submission 3225
I appreciate the further clarification and additinal experimental results the authors provided. My concerns have been partly addressed.
I still have some concerns left about the improved amortized update bound not guaranteed by the default algorithm, and some of the reported speedups still rely on estimated baseline runtimes.
I believe the paper itself has interesting contributions, but some concerns remain. So i will keep my original rating.
Dear Reviewer 6oXU,
Thank you for your timely response. We would like to make our two key points as clear and concise as possible in hopes of addressing your remaining concerns:
- Guaranteeing the improved amortized bound slows total runtime by 13×: Strictly enforcing the local bound (
always-repair) triggers a higher subtree-repair rate per reevaluation ( more total repairs) and slowsSparse Forestby (801.1 s vs. 61.4 s).
Because subtree repair scales with node size ( per layer plus descendant updates) and is far more expensive than the or local node update, optimizing local amortized complexity increases overall end-to-end complexity. Meanwhile, our default rule avoids of repairs while still achieving a reduction in amortized local candidate scans. An intuitive understanding: ensuring optimized amortized bound make reevaluation (cheap) less frequent but repairing (far me expensive) more often, while the default setting make reevaluation more frequent but repairing less often.
- Short-stream estimation is fair and favors slow baselines: In the streaming settings, we are comparing the average time the model needs to process a single request (per-request latency), which is measured precisely and not estimated.
The term "estimation" in our manuscript is misleading, as all per-request latency is measured as [total time / number of requests]. For fast models (SF, ST, DynFrs, VFDT, EFDT), their per-request latency is averaged over all 200k requests. For timed-out baselines (DyGB, FUTURE, DaRE), a single 200k-request run would require about 59.7 days (DyGB mean) or 54.4 days (DaRE on CreditCard), so we measure per-request latency on shorter streams (e.g., 2,000 requests). Using shorter streams actually benefits these baselines, as they are less likely to encounter rare, expensive shallow-tree reconstructions.
Thank you again for your time and consideration.
Sincerely yours,
Author(s) of Submission 3255
[1/2] Response to Reviewer 6oXU
We sincerely thank the reviewer for constructive feedback and helpful suggestions, which have strengthened our empirical evaluation and ablations.
[W1/Q1]Results without estimation and with full drain time:Cause of incompleted runs
Baseline runs fail to complete the full 200k-request stream under three scenarios:
s1(Batch-oriented baselines, e.g.,DyGB,FUTURE): Designed for batch updates rather than per-sample streaming. We run 10 operations of each supported request type and extrapolate to the full stream.s2(24-hour timeout, e.g.,DaREonCreditCardandHiggs): Exceeds the 24-hour limit on large datasets. We run 1,000 operations of each supported request type and extrapolate to the full stream.s3(Training failure, e.g.,HedgeCuton 4 datasets): Crashes during initial build or exceeds 512 GB RAM, so runtime cannot be estimated.Extrapolating in
s1ands2simply compares average per-request latency. In fact, these short-stream estimates are optimistic (favorable to the baselines), as rare but expensive shallow-layer rebuilds are less likely to trigger within 10 or 1,000 requests than over the full stream.Including deferred-repair (drain) time
Across all datasets, final drain time accounts for only 0.92% of total runtime on average:
We originally excluded drain time because nodes left unrepaired at the end of the stream were never queried, so repairing them is unnecessary for serving the stream (affects no query). However, we agree that reporting total time including full materialization (drain) provides a more complete picture, and we have mentioned this in the revised manuscript.
Speedup comparison across accounting choices
Below we report baseline slowdowns (relative to
SF 0.1, orST 0.1for insertion-only) under three settings: (i) w/ estimation (as reported in the paper, no drain), (ii) w/o estimation (completed datasets only, no drain), and (iii) w/ drain (includingSF/STstream + drain time):SF 0.1)DynFrsDyGBs1)ST 0.1)VFDTEFDTSF 0.1)DaREs2)HedgeCuts3)s3)FUTUREs1)*Computed over the 5 completed datasets only, as failed builds cannot be estimated.
Note that
HedgeCut's 10.19× gap reflects survival bias toward smaller datasets: on the largest dataset it completes (Diabetes), it is 33.25× slower thanSF 0.1, while failing or exceeding 512 GB RAM on the four larger datasets. Overall, including drain time scarcely changes any speedup ratio, and full per-dataset results (both absolute and relative) are available in Appendix C.5 Table 1.[W2/Q2]Ablation of the three sparsity mechanisms:We conducted a controlled end-to-end runtime ablation disabling one sparsity mechanism at a time across all datasets (detailed in Appendix C.7, Table 8). Averaged across datasets, the request-processing times and slowdowns relative to the full model are:
SF 0.1(Full)SF 0.1(No Struct.)SF 0.1(No Recon.)SF 0.1(No Split-chg.)SF 0(Full)SF 0(No Struct.)SF 0(No Recon.)SF 0(No Split-chg.)The three mechanisms play complementary roles depending on the exactness regime: In
SF 0.1((0.1,0.5)-suboptimal): structural- and split-change-sparsity drive the speedup, because split retention already avoids most split replacements, subtree reconstruction rarely triggers. InSF 0(totally exact): structural- and reconstruction-sparsity dominate, since exactness forces frequent split updates where in-place subtree repair saves substantial rebuild work, while the O(1) gap certificate still provides a 1.25× speedup. The complete result is available at Appendix C.7 Table 8.