acceptodds
Under review as a conference paper at ICLR 2027

Sparse Forest: Efficient Online Learning and Unlearning Framework for Tree Ensembles

Abstract

Evolving data and limited computational resources pose two coupled challenges for deploying machine learning system in reality. Online learning and unlearning enable models to incorporate new observations and remove obsolete records, while the computational efficiency of tree ensembles makes them attractive for resource-constrained deployment. However, inexpensive training and inference do not imply inexpensive maintenance: a single sample insertion or deletion can trigger costly whole tree reconstruction. We introduce *Sparse Forest* that addresses this bottleneck through three complementary forms of sparsity. *Structural sparsity* limits the complexity of the maintained trees, reducing the fundamental cost of node statistics updates. *Reconstruction sparsity* prunes the reconstruction through in-place subtree repair, reusing existing descendants and propagating changes in sample membership. *Split-change sparsity* reduces the frequency of structural changes by retaining satisfactory splits under a controlled suboptimality tolerance. Together, these principles control how much structure must be maintained, how much work each repair requires, and how often repairs necessiates. By formalizing -suboptimality for tree ensembles, Sparse Forest makes exactness an explicit, configurable property rather than a fixed design choice. At , Sparse Forest maintains a model that is *bit-identical* to retraining from scratch on the updated dataset. To our knowledge, this is the first such guarantee for online learning and unlearning in tree ensembles, going beyong equality in distribution. Relaxing this condition () trades retraining equivalence for substantially fewer structural changes at negligible accuracy cost. Experiments demonstrate orders-of-magnitude speedups over the state-of-the-art online learning and unlearning baseline, establishing Sparse Forest as a practical alternative for real-world deployment.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
Online Learning, Machine Unlearning, Random Forest, Sparsity, Exactness

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_6oXUOpenReview ↗
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
  1. The paper addresses a practical and important problem in maintaining tree ensembles under frequent data updates.

  2. The three sparsity mechanisms are complementary, and the paper provides a formal exactness guarantee.

  3. The experiments cover multiple datasets and update settings, showing substantial efficiency improvements.

Critical weaknesses
  1. Some runtime comparisons rely on estimated baseline results, and the main stream timings exclude final deferred repair.

  2. The paper lacks a controlled end-to-end runtime ablation isolating the contributions of all three sparsity mechanisms.

  3. The improved amortized update bound relies on additional conditions that are not guaranteed in general.

Questions for authors
  1. How do the reported speedups change when only completed baseline runs are considered, without estimated results?

  2. Can the authors provide an end-to-end runtime ablation to show how much each sparsity mechanism contributes to the overall speedup?

  3. 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?

  4. How often do reevaluations retain suboptimal splits without restoring sufficient slack, and how does this affect runtime?

4 comments
AuthorsOpenReview ↗

[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., DaRE on CreditCard and Higgs): 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., HedgeCut on 4 datasets): Crashes during initial build or exceeds 512 GB RAM, so runtime cannot be estimated.

Extrapolating in s1 and s2 simply 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%0.92\% of total runtime on average:

DatasetAdultBankCreditCardDiabetesHeartHiggsNoShowPurchaseVaccineOverall
Stream time (%)99.9599.9699.9999.8299.9592.2399.8699.9999.9699.08
Drain time (%)0.050.040.010.180.057.770.140.010.040.92

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, or ST 0.1 for 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 (including SF/ST stream + drain time):

Workload (Ref.)BaselineIncomplete dataset(s)Speedup (w/ est.)Speedup (w/o est.)Speedup (w/ drain)
Insert & Delete (SF 0.1)DynFrsNone25.68×25.68×25.48×
DyGBAll (s1)194,160.96×No completed runs189,991.87×
Insert-only (ST 0.1)VFDTNone10.43×10.43×10.41×
EFDTNone24.35×24.35×24.31×
Delete-only (SF 0.1)DaRECreditCard, Higgs (s2)25,223.97×277.45×25,111.56×
HedgeCutAdult, CreditCard, Higgs, Vaccine (s3)N/A (s3)10.19×10.14×*
FUTUREAll (s1)87,631.39×No completed runs86,405.47×

*Computed over the 5 completed datasets only, as failed builds cannot be estimated.

Note that HedgeCut's 10.19×10.19\times gap reflects survival bias toward smaller datasets: on the largest dataset it completes (Diabetes), it is 33.25×33.25\times slower than SF 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:

MetricSF 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.)
Stream-processing time24.30s154.7s25.62s292.1s278.6s1853s1228s281.0s
Relative time (×)1.000×7.132×1.062×7.488×1.000×6.186×2.133×1.252×

The three mechanisms play complementary roles depending on the exactness regime: In SF 0.1 ((0.1,0.5)(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. In SF 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)O(1) gap certificate still provides a 1.25×1.25\times speedup. The complete result is available at Appendix C.7 Table 8.

AuthorsOpenReview ↗

[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 O(ps)\mathcal O(ps), O(p+psεn1−φ)\mathcal O(p + \frac{ps}{\varepsilon n^{1-\varphi}}), or O(p)\mathcal O(p)?

Let KK be the number of local updates (gap) at a node between two consecutive reevaluations. It is proven that reevaluation costs O(Kp+ps)\mathcal{O}(Kp + ps), or O(p+ps/K)\mathcal{O}(p + ps/K) amortized per update, and improves over conventional O(ps)\mathcal{O}(ps) update whenever K>1K > 1 and reaching O(p)\mathcal{O}(p) once K=Ω(s)K = \Omega(s). Thus, the improved O(p+psεn1−φ)\mathcal O(p + \frac{ps}{\varepsilon n^{1-\varphi}}) bound holds whenever K=Ω(εn1−φ)K = \Omega(\varepsilon n^{1-\varphi}), which reaches O(p)\mathcal{O}(p) once εn1−φ=Ω(s)\varepsilon n^{1-\varphi} = \Omega(s) which is common for large nodes (for typical s∈{5,20,40}s \in \{5, 20, 40\} and ε∈[0.1,2]\varepsilon \in [0.1, 2]):

  • n≥s/εn \ge s/\varepsilon for φ=0\varphi = 0.
  • n≥(s/ε)2n \ge (s/\varepsilon)^2 for the default φ=0.5\varphi = 0.5.
  • whereas φ=1\varphi = 1 yields a constant-factor gain K=Ω(ε)K = \Omega(\varepsilon).

Whether K=Ω(εn01−φ)K = \Omega(\varepsilon n_0^{1-\varphi}) is guaranteed depends on the residual suboptimality gap g0∈[0,εn0−φ]g_0 \in [0, \varepsilon n_0^{-\varphi}] left after reevaluation. As evaluated in Appendix D.2:

  • Default (normal) rule (not satisfied): Retains the installed split whenever g0≤εn0−φg_0 \le \varepsilon n_0^{-\varphi}. Because g0g_0 can lie arbitrarily close to εn0−φ\varepsilon n_0^{-\varphi} (near-zero slack), the next reevaluation can trigger after K=O(1)K = \mathcal{O}(1) updates in the worst case; thus, default SF does NOT unconditionally guarantee K=Ω(εn01−φ)K = \Omega(\varepsilon n_0^{1-\varphi}).
  • Slack-restoring rules (unconditionally satisfied): The O(p+psεn01−φ)\mathcal O(p + \frac{ps}{\varepsilon n_0^{1-\varphi}}) bound can be strictly guaranteed simply by enforcing slack restoration at reevaluation via
    • always-repair: always installing the optimal split during reevaluation so g0=0g_0 = 0.
    • fractional-slack: retains the current split iff g0≤12εn0−φg_0 \le \frac12 \varepsilon n_0^{-\varphi}, guaranteeing at least 12εn0−φ\frac12 \varepsilon n_0^{-\varphi} slack and hence K=Ω(εn01−φ)K = \Omega(\varepsilon n_0^{1-\varphi}).

Trade off between frequency of reevaluation and frequency of repairing

Crucially, the O(p+ps/K)\mathcal{O}(p + ps/K) cost only measures local updates, whereas changing an installed split triggers in-place subtree repair over descendants, which is sufficiently expensive: O(n+mp+ps)\mathcal O(n + mp + ps). To quantify this trade-off, we instrumented SF 0.1 on Higgs comparing default normal against always-repair:

MetricVariantd=0d=0d=1d=1d=2d=2d=3d=3d=4d=4d=5d=5-99d=10d=10-1919d=20d=20-2929d=30d=30-3939Overall
Avg. gap KKnormal129.0794.0262.3339.9427.658.642.411.431.244.04
always-repair164.83246.49296.77299.69285.66179.4352.969.532.4074.66
# of reevaluationsnormal38,817.453,365.280,592.2126,019.4182,583.03,019,004.222,829,026.012,990,207.0703,665.840,023,280
always-repair30,437.442,715.060,696.287,996.2124,346.21,985,276.417,198,113.67,055,018.6256,782.826,841,382
# of repairsnormal0.00.00.00.00.2328.4130,855.6199,531.012,894.0343,609
always-repair84.6240.6506.01,174.82,523.0138,483.21,990,342.4599,112.211,470.22,743,937
Avg. repair sizenormal0.00.00.00.060.0056.8335.0030.0528.0031.88
always-repair1,232,154584,897300,184141,94974,388.48,692.09836.01217.25124.791,366.85
Stream-processing timenormal61.39s
always-repair801.11s

This experiment reveals a clear and important findings:

  • Compared to always-repair, normal performs 49.1%49.1\% more reevaluations, yet triggers 87.5%87.5\% fewer repairs and shrinks average repair size by 97.7%97.7\%. Consequently, normal reduces total stream-processing time by 92.3%92.3\%, resulting in a 13×13\times speedup.
  • In normal, 99.14%99.14\% reevaluations retain the split without repairing, while 89.78%89.78\% reevaluation necessitates a repair.
  • The overall average gap of normal is K=4.04K=4.04 (still improve the O(ps)\mathcal O(ps) update by 4×4\times), whereas always-repair achieves K=74.66>s=40K=74.66>s=40, entering the O(p)\mathcal{O}(p) local regime.

In short, while Sparse Forest can guarantee the O(p+psεn1−φ)\mathcal O(p + \frac{ps}{\varepsilon n^{1-\varphi}}) bound via slack restoration, our default retention rule intentionally sacrifices worst-case local spacing KK 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:

  1. Guaranteeing the improved amortized bound slows total runtime by 13×: Strictly enforcing the O(p+psεn1−φ)\mathcal{O}(p + \frac{ps}{\varepsilon n^{1-\varphi}}) local bound (always-repair) triggers a 12×12\times higher subtree-repair rate per reevaluation (8×8\times more total repairs) and slows Sparse Forest by 13×13\times (801.1 s vs. 61.4 s).

Because subtree repair scales with node size nn (O(np+ps)\mathcal{O}(np + ps) per layer plus descendant updates) and is far more expensive than the O(ps)\mathcal{O}(ps) or O(p+ps/εn1−φ)\mathcal O(p + ps/\varepsilon n^{1-\varphi}) local node update, optimizing local amortized complexity increases overall end-to-end complexity. Meanwhile, our default rule avoids 99.199.1\\% of repairs while still achieving a 4×4\times 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.

  1. 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

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

Sparse Forest (SF) tackles online learning of additive tree models, where the stream not only contains insertions (i.e., new data points) and queries (i.e., predictions), but also deletions (i.e., removal of previously seen data points from the model). The authors introduce three mechanisms for SF: (1) structural sparsity: uniform threshold grids per candidate attribute with histogram + prefix-sum statistics and tree subsampling; (2) reconstruction sparsity: in-place subtree repair that migrates only the samples switching sides under a new split, with optional child swap so at most n/2 samples move; (3) split-change sparsity: the installed split is retained while its gap to the current optimum stays within (epsilon, phi)-suboptimality (gap <= eps * n^-phi). The idea is that at eps = 0, SF retains a bit-identical model to retraining. On nine binary datasets the authors show that SF is ~17.5x faster than DynFrs with comparable AUC.

Critical strengths
  1. Real, novel formalization: (eps, phi)-suboptimality largely unifies the tolerance regimes of VFDT/EFDT and fully-dynamic DTs, and makes exactness a configurable knob with bit-identity to retrain models at eps = 0. For unlearning, this is much more than the usual equality-in-distribution.
  2. The paper contains proofs for most of the arguments. Most proofs are well-presented and easy to follow. There are some minor inconsistencies in writing, but the math generally supports the algorithm and findings of the authors. The formalization is sound and seems helpful for future work.
Critical weaknesses

Weaknesses

  1. The experimental setup is the weak point. Baselines are cheap additive ensembles, and the comparison is explicitly not "capacity-matched"(C.1: runtime differences "should not be attributed to one sparsity mechanism alone"). I don't see ablation studies for hyperparameters. The exactness verification is mostly on a reduced-scale (256/2,048 records) and the full-data Higgs cells are missing (allocation failure). Multiclass/regression generalization only uses toy datasets (Iris 150, Wine 178, Auto MPG 392). Given the theoretical focus of the paper, I don't weigh this too heavily, but given that running experiments with additive tree ensembles is somewhat cheap, I hoped for a better evaluation.
  2. The O(1/q^2) workload claim (25x from q = 0.2) is a loose heuristic: it holds only when per-tree work is linear in tree size. Under the paper's own O(1) per-node amortized updates, per-request savings are ~q * log(qN)/log(N), not q^2.

There are issues with the presentation that I give here so that authors can improve the paper. I don't view them as critical weaknesses, though:

  • Many typos: "necessiates" (abstract), "depolyment/depoly", "natrual", "interpertability", "indentifiable", "capabile" (p.8), "qunatities", "esemble", "allievate", "substree", "recusively", "mirros", "similary", "retraing"; missing \alpha on p.5 ("fixed attribute alpha").
  • Number inconsistency: 17.5x (abstract/intro) vs 16.9x (conclusion).
  • Label confusion: "SF 0.1" in Figs. 4/5 is the native gamma = 0.05 config (normalized eps = 0.1/sqrt(n)), not the pure eps*n^-phi rule of Fig. 6. This is acknowledged but confusing.
  • Grid thresholds can be arbitrarily suboptimal when a grid is used vs data-adaptive splits that are theoretically better but often worse/not as good in practice. I feel like this is not sufficiently acknowledged. In particular, it is never quantified on the binary benchmarks how much the grid hurts performance.
  • The appendix contains a lot of the "important meat" of the paper. I understand that in a conference submission, space is very limited. Nevertheless, I think a better paper structure could have made it easier to follow the paper and actually understand the main points without the need to consult the appendix all the time.
Questions for authors

Please explain some of your arguments a bit more in detail. In particular, please explain if it is O(1/q2)O(1/q^2) or something closer to q⋅log(qN)/log(N)q \cdot log(qN)/log(N)?

I am rating weak accept for now, but I am willing to bump it up.

2 comments
AuthorsOpenReview ↗

[1/2] Response to Reviewer ejAT

We sincerely thank the reviewer for the thoughtful review, encouraging assessment of our theoretical formulation, and constructive suggestions. Your feedback directly guided a major overhaul of our experiments and presentation, which we summarize below.

[W1] Experiments needs to be better

Over the rebuttal period, we substantially expanded and standardized our empirical evaluation along five fronts:

Unified protocols and organized results

Previously, different experiments used slightly different evaluation and aggregation rules. We have unified all timing, memory accounting, seed sets (identical 5 random seeds per dataset), and evaluation criteria, and re-ran all experiments from scratch. Complete per-dataset, per-model raw numbers are now reported in Appendix C.4–C.8 (Tables 1–9), covering:

  1. streaming (un)learning runtime,
  2. batch (un)learning runtime & accuracy,
  3. initial training time & memory,
  4. streaming predictive performance,
  5. train–test predictive performance,
  6. predictive KL divergence vs. retraining,
  7. (ε,φ)(\varepsilon, \varphi) ablations,
  8. ablations of the three sparsity mechanisms,
  9. ablations of different qq, & study of even grid v.s. random threshold,
  10. multi-class classification and regression.

Therefore, every figure and claim in the main text is directly verifiable.

New baseline

Alongside DyGB, we added the model-agnostic unlearning baseline FUTURE (implemented with XGBoost, also suggested by Reviewer Yt4X) to go beyond simple bagging ensembles. Under our unified protocol, FUTURE is faster than DyGB with strong predictive accuracy, but remains orders of magnitude slower than our Sparse Forest in streaming updates.

Capacity-matched experiments

In the paper, we use a predictive performance-matched protocol so no baseline sacrifices accuracy for speed. For each forest method, their parameter T∈100,150,250T \in \\{100, 150, 250\\}, dmax⁡∈10,15,20,25,30,40d_{\max} \in \\{10, 15, 20, 25, 30, 40\\}, and s∈5,15,20,30,40s \in \\{5, 15, 20, 30, 40\\} are selected via 5-fold cross-validated grid search on the training set, and aims for the best predictive performance. On Higgs, where full grid search for DynFrs and DaRE would exceed 540 hours, we use their official setting T=100T = 100, whereas Sparse Forest uses T=250T = 250, and gains +0.10+0.10pp in accuracy and +0.19+0.19pp in AUC. Thus, Sparse Forest achieves its 48.67×48.67\times speedup over DynFrs despite maintaining 2.5×2.5\times more trees, and would show an even larger margin (146.01×146.01\times speedup) under equal tree counts:

ModelAdultBankCreditCardDiabetesHeartHiggsNoShowPurchaseVaccineOverall
SF 0.11.01.01.01.01.01.01.01.01.01.00×
SF 03.693.081.866.174.5818.386.112.712.945.50×
DynFrs18.6220.5120.4145.0826.11146.0122.7620.7618.3037.62×

Under the capacity-matched setting, SF 0.1 improve the average speedup against DynFrs from 25.68×25.68\times (predicitive performance-matched) to 37.62×37.62\times.

More ablation studies

We now ablate every Sparse Forest-specific component and hyperparameter:

  1. An end-to-end runtime ablation disabling each of the three sparsity mechanisms one at a time (Table 8, also requested by Reviewer 6oXU).
  2. Suboptimality parameters (ε,φ)(\varepsilon, \varphi) (Fig. 5, Table 7)
  3. Tree subsampling density q∈0.1,0.2,0.33,0.5,1.0q \in \\{0.1, 0.2, 0.33, 0.5, 1.0\\} (result in [W2] below).
  4. even-grid vs. random split thresholds (detailed under [W3] below) as you suggested.

Larger multi-class classifition and regression

We replaced the "toy datasets" with two larger multi-class classification datasets (Letter Recognition with 20,000 samples and Shuttle with 58,000 samples) and two larger regression datasets (Superconductivity with 21,263 samples and BikeSharing with 17,379 samples) The detailed results are in Appendix C.8 (Table 9).

AuthorsOpenReview ↗

[2/2] Response to Reviewer ejAT

[W2] On speedup of tree subsampling

Your findings are correct and thank you for catching this. The speedup from subsampling at rate qq depends on which update regime occurs:

  • Updates without subtree repair (dominant case about 99.14%99.14\% of reevaluations): An update only traverses root-to-leaf paths in the qTqT trees containing the sample. When tree height scales as O(log⁡qN)\mathcal O(\log qN) vs. O(log⁡N)\mathcal O(\log N), per-request work scales by qlog⁡(qN)log⁡Nq \frac{\log(qN)}{\log N}, giving a speedup of O(log⁡Nqlog⁡(qN))\mathcal O(\frac{\log N}{q \log(qN)}), exactly as you derived. When tree depth saturates the maximum depth dmax⁡d_{\max}, path length is O(dmax⁡)\mathcal O(d_{\max}) and the speedup simplifies to O(1/q)\mathcal{O}(1/q).
  • Updates with subtree repair (very rare): Because subsampling reduces both the fraction of affected trees by qq and the expected sample size per tree from NN to qNqN, operations whose cost is linear in tree/subtree size (e.g., naive retraining O(Nps)\mathcal O(Nps) or large shallow repairs O(n+mp+ps)\mathcal O(n + mp + ps)) shrink by q2q^2, yielding O(1/q2)\mathcal{O}(1/q^2). The O(1/q2)\mathcal O(1/q^2) in the initial manuscript comes from comparing the tree subsampling with a naïve Random Forest retraining method, but we should clarify it.

We have revised the manuscript to state both regimes accurately rather than claiming O(1/q2)\mathcal{O}(1/q^2) unconditionally. We spotted an O(1/q)\mathcal O(1/q) scaling behavior in stream charged time in our empirical ablations across q∈0.1,0.2,0.33,0.5,1.0q \in \\{0.1, 0.2, 0.33, 0.5, 1.0\\}:

Relative charged timeq = 0.1q = 0.2q = 0.33q = 0.5q = 1.0
Relative charged time1.00×2.15×3.41×5.25×10.99×

[W3] Improvments on the manuscript

Many typos

Thank you for listing these carefully. We fixed every typo and missing symbol and conducted a thorough proofreading pass across the entire paper.

Number inconsistency

The earlier discrepancy (17.5×17.5\times vs. 16.9×16.9\times) stemmed from inconsistent aggregation across unaligned seed counts (geometric vs. arithmetic mean). Under our unified 5-seed protocol using the standard arithmetic mean over relative runtime across datasets, all numbers in the abstract, main text, and conclusion are now fully consistent (SF 0.1 achieves a 25.68×25.68\times mean speedup over DynFrs; details in Table 1).

Label Confusion

γ\gamma was a leftover parameter from an earlier draft (2γ=ε2\gamma = \varepsilon). We apologize for the confusion and have removed γ\gamma everywhere in favor of (ε,φ)(\varepsilon, \varphi)-suboptimality.

Cost of using even-grid threshold

Following your suggestion, we evaluated SF 0.1 with even-grid candidate thresholds against standard randomly drawn thresholds (random) across all 9 binary datasets (5 seeds each, same settings as Fig. 4):

Metriceven-grid (Default)randomDifference (random vs. even-grid)
Relative stream time1.000×1.074×+7.4% slower
Mean accuracy82.1288%82.1227%−0.0061 pp
Mean ROC-AUC85.3152%85.3476%+0.0324 pp

Across the 9 benchmarks, even-grid achieves virtually identical predictive performance (+0.0061+0.0061pp in accuracy, −0.0324-0.0324pp in ROC-AUC) while running 7.47.4\\% faster on average thanks to shared prefix-sum/histogram indexing. We have added this discussion to the main text and Appendix C.7.

Merging appendix into the main text

We have moved some of the exactness related notation into the main text, and moved more experimental results into the main text while keepingt the larger, detailed tables containing the raw data in the appendix. We also connects the main text more with the discussion in Appendix D.2, and we will be merging more content from the Appendix to the main text.

Thank you once again for your detailed, constructive review that strengthened our paper a lot.

With gratitude,

Author(s) of Submission 3225

Reviewer_Yt4XOpenReview ↗
Rating
3(+1)
Confidence
4
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

goal: online learning and unlearning for tree ensembles.

Critical strengths

tree ensembles are widely applicable to many problems but there is limited work in terms unlearning, especially online unlearning with tree ensembles.

Critical weaknesses

missing baseline: Flexible Unlearning for Tree Ensemble, https://arxiv.org/abs/2508.21181 the submission shares some of the datasets and baselines with the above paper too!

We call a model accurate if \hat{y}_q is close to the true label y_q, under a task-specific criterion, with high probability. "close" and "with high probability"

this is unconventional definition of accuracy.

Definition 1: Distributional Exactness

this definition is mis-specified. In a continuous model space, every individual model may have probability zero, Pr[M_t = M] = Pr[M_re = M] = 0, even though the distributions are different.

Definition 2: Total Exactness

this is not well-defined: suppose retraining randomly returns trees T_0 or T_1, both valid, each with prob of 0.5. The unlearning algorithm has exactly the same output distribution. Then depending on the coupling, the two model may or may not match. If authors mean there exists some coupling under which the outputs are identical, then it is not stricter than distributional exactness. Any two identically distributed outputs can be coupled to be equal almost surely. "Same specification" and "shared randomness" are vague.

It's unclear whether retraining means retraining the entire pipeline from raw data or retraining the proposed sparse forest learner.

typos---didn't check thoroughly:

going beyong

an model

Questions for authors

see above.

4 comments
AuthorsOpenReview ↗

[1/2] Response to Reviewer Yt4X

We are grateful to the reviewers for their careful reading and valuable suggestions, which have significantly contributed to refining our research. Here are the responses to your points raised in the weakness sections.

[W1] Missing baseline FUTURE:

We appreciate the reviewer bringing the FUTURE baseline to our attention. As we could not find an official public implementation of FUTURE, we reached out to the original authors for clarification and carefully use an AI agent re-implemented FUTURE following their paper and guidance.

Because FUTURE is model-agnostic and performs approximate unlearning, we paired it with XGBoost as its base learner, which achieved stronger predictive performance than other tree-based models. This places FUTURE alongside DyGB, as both operate on gradient-boosted trees. We have incorporated the full experimental results for FUTURE into the revised manuscript, and summarize the key findings below:

  • For streaming, FUTURE is estimated to be 8.76×1048.76\times10^4 times slower than Sparse Forest (ε=0.1\varepsilon = 0.1) (SF 0.1 for short), and for reference DyGB is 1.94×1051.94\times10^5 times slower.
  • On our largest dataset Higgs, unlearning a batch of 10510^5 samples takes 165.5 s165.5\text{ s} for FUTURE (820.7 s820.7\text{ s} for DyGB), compared to just 27.21 s27.21\text{ s} for SF 0.1.
  • FUTURE achieves the highest average test accuracy at 82.3882.38\\%, closely followed by DyGB at 82.2482.24\\% and SF 0.1 at 82.2182.21\\% (making SF 0.1 the best non-gradient-boosting model)

In summary, FUTURE is a strong state-of-the-art baseline for approximate batch unlearning on gradient-boosted models. Meanwhile, Sparse Forest remains about 5.5×5.5\times faster in batch unlearning, orders of magnitude faster in streaming updates, and capable of exact unlearning.

[W2] Weakness on definitions:

Thank you very much for carefully examining our definitions and pointing out these subtle mathematical details. Your comments helped us make our problem formulation much clearer and more rigorous.

Definition of Accuracy

We intended to refer to conventional evaluation metrics, and we agree that our original phrasing was vague. We have now removed that and made predictive performance explicit in the Background section so that it aligns with standard definitions.

Definition of Distributional Exactness

We really appreciate you pointing out that our previous definition of distributional exactness only worked for discrete model spaces and was ill-suited for continuous model spaces (which Random Forests with continuous thresholds/statistics fall into). Prompted by your feedback, we rebuilt our formulation from the basis with rigorous definitions of the training algorithm, distributional exactness, and total exactness.

In our revised Background section, we explicitly define a measurable model space (M,Σ)(\mathcal{M}, \Sigma) and parameterize a training algorithm Aψ,ω\mathcal{A}^{\psi, \omega} and online (un)learning algorithm A±ψ,ω\mathcal A_{\pm}^{\psi, \omega} by:

  • Training specification ψ\psi: specifies the learner class, hyperparameters, feature encoding, domain bounds, and deterministic tie-breaking rules of the training algorithm.
  • Random seed ω\omega: drawn from a probability space (Ω,F,PΩ)(\Omega, \mathcal{F}, P_\Omega) governing all internal randomness (such that ω↦Aψ,ω(D)\omega \mapsto \mathcal{A}^{\psi, \omega}(D) is (F,Σ)(\mathcal{F}, \Sigma)-measurable for every finite dataset D∈DD \in \mathcal{D}).

We treat ψ\psi as fixed prior to deployment and shared between training and online updates, so we suppress ψ\psi and write Aω(D)\mathcal{A}^\omega(D) whenever clear from context. When ω∼PΩ\omega \sim P_\Omega is left implicit, M=A(D)\mathsf{M} = \mathcal{A}(D) denotes the resulting M\mathcal{M}-valued random variable, and when ω\omega is specified, Aω\mathcal{A}^\omega is treated as a deterministic algorithm.

With this setup, our revised definition of distributional exactness handles continuous model spaces properly via equality of probability measures:

Distributional Exactness

An online (un)learning algorithm A±\mathcal A_\pm is distributionally exact with respect to A\mathcal A (under shared specification ψ\psi) if, for every initial dataset D0∈DD_0 \in \mathcal D and every valid request stream (rt)t≥1(\mathbf r_t)_{t \ge 1}, the maintained model Mt=A±(Mt−1,rt)\mathsf M_t = \mathcal A_\pm(\mathsf M_{t-1}, \mathbf r_t) (with M0=A(D0)\mathsf M_0 = \mathcal{A}(D_0)) and the freshly retrained model Mre=A(Dt)\mathsf M_{\mathrm{re}} = \mathcal A(D_t) induce identical probability measures on (M,Σ)(\mathcal M, \Sigma): ∀t≥1,∀S∈Σ:Pr⁡[Mt∈S]=Pr⁡[Mre∈S].\forall t \ge 1, \forall S \in \Sigma : \quad \Pr[\mathsf M_t \in S] = \Pr[\mathsf M_{\mathrm{re}} \in S].

AuthorsOpenReview ↗

[2/2] Response to Reviewer Yt4X

Definition of Total Exactness

Following your constructive suggestions, we refine the definition of total exactness rigorous by tying all randomness to the single random seed ω\omega shared between the maintained model and the retrained model, and requiring deterministic equivalence for every seed (so that satisfying distributional exactness no longer implies total exactness):

Total Exactness

An online (un)learning algorithm A±ω\mathcal{A}_\pm^\omega is totally exact with respect to Aω\mathcal{A}^\omega (under shared specification ψ\psi) if, for every seed ω∈Ω\omega \in \Omega, every initial dataset D0∈DD_0 \in \mathcal{D}, and every valid request stream (rt)t≥1(\mathbf{r}_t)_{t \ge 1}, the maintained model Mtω=A±ω(Mt−1ω,rt)\mathsf{M}_t^\omega = \mathcal{A}_\pm^\omega(\mathsf{M}_{t-1}^\omega, \mathbf{r}_t) (with M0ω=Aω(D0)\mathsf{M}_0^\omega = \mathcal{A}^\omega(D_0)) and the retrained model Mreω=Aω(Dt)\mathsf{M}_{\mathrm{re}}^\omega = \mathcal{A}^\omega(D_t) are bit-identical in canonical logical state (Appendix B.2): ∀t≥1,∀ω∈Ω:Mtω=Mreω.\forall t \ge 1, \forall \omega \in \Omega : \quad \mathsf{M}_t^\omega = \mathsf{M}_{\mathrm{re}}^\omega.

Additionally, if A±ω\mathcal{A}_\pm^\omega is totally exact with respect to Aω\mathcal{A}^\omega, it automatically implies distributional exactness. Even when the maintained pipeline (Aω1,A±ω1)(\mathcal{A}^{\omega_1}, \mathcal{A}_\pm^{\omega_1}) and an independent retraining run Aω2\mathcal{A}^{\omega_2} use different random seeds ω1\omega_1 and ω2\omega_2 drawn independently from the same probability space (Ω,F,PΩ)(\Omega, \mathcal{F}, P_\Omega), distributional exactness still holds: by total exactness, Mtω1=A±ω1(Mt−1,rt)=Aω1(Dt)\mathsf{M}_t^{\omega_1} = \mathcal{A}^{\omega_1}_\pm(\mathsf M_{t-1}, \mathbf r_t) = \mathcal A^{\omega_1}(D_t) for every ω1∈Ω\omega_1 \in \Omega; since ω1\omega_1 and ω2\omega_2 have the same distribution PΩP_\Omega and ω↦Aω(Dt)\omega \mapsto \mathcal{A}^\omega(D_t) is measurable, we have for every S∈ΣS \in \Sigma: Pr⁡ω1∼PΩ[Mtω1∈S]=Pr⁡ω1∼PΩ[Aω1(Dt)∈S]=Pr⁡ω2∼PΩ[Aω2(Dt)∈S]=Pr⁡ω2∼PΩ[Mreω2∈S].\Pr_{\omega_1 \sim P_\Omega}[\mathsf{M}_t^{\omega_1} \in S] = \Pr_{\omega_1 \sim P_\Omega}[\mathcal{A}^{\omega_1}(D_t) \in S] = \Pr_{\omega_2 \sim P_\Omega}[\mathcal{A}^{\omega_2}(D_t) \in S] = \Pr_{\omega_2 \sim P_\Omega}[\mathsf{M}_{\mathrm{re}}^{\omega_2} \in S].

This seed-deterministic formulation of total exactness resolves the T0T_0 / T1T_1 coupling issue you mentioned. The revised total exactness is not "there exists some post-hoc coupling under which Mt\mathsf{M}_t and Mre\mathsf{M}_{\mathrm{re}} match". Instead, the A±ω\mathcal{A}_\pm^\omega is strictly deterministic given the initial seed ω\omega sampled at t=0t = 0 and draws no fresh randomness during updates. In the example, retraining that returns TωT_\omega and maintenance that returns T1−ωT_{1-\omega} have identical output distributions (distributional exact) but fail total exactness condition for both seeds.

Clarifications

We have stated explicitly in both definitions that A±\mathcal{A}_\pm and A\mathcal{A} share the fixed specification ψ\psi, and this resolves the ambiguity regarding what "retraining" means in the manuscript: when evaluating Sparse Forest's online (un)learning algorithm A±ψ,ω\mathcal A^{\psi, \omega}_\pm, retraining means building a new forest with Sparse Forest learning algorithm Aψ,ω\mathcal A^{\psi, \omega} on DtD_t under the same fixed feature encoding, domain bounds, and hyperparameters defined in ψ\psi.

For total exactness, we agree that from a statistical data-removal standpoint, it is not "stronger" than distributional exactness in terms of what is unlearned or learned: it does NOT require the model to "forget" more, make the model safer from a privacy perspective, or yield higher predictive gains from online learning. But we would like to clarify why total exactness matters in streaming online (un)learning. Existing randomized methods (e.g., DynFrs) resample subtrees across sequential updates, making it difficult to verify both theoretically (proof only consider unlearning for once) and empirically whether distributional exactness strictly holds over long request streams.

That is why we used predictive KL divergence as an empirical proxy to measure divergence between maintained model and retrained models. By contrast, when a model satisfies total exactness, empirical verification is straightforward and exact: after processing the entire stream, we simply retrain on DtD_t (with the same specification ψ\psi and seed ω\omega), and verify directly that the two models (and their predictions) are bit-identical. In our work, Sparse Forest (ε=0\varepsilon = 0) (SF 0) guarantees total exactness both theoretically (proved in Appendix B.2) and empirically (achieving 0 state mismatch and Predictive KL = 0 in all experiments).

[W3] Typos in manuscript:

We thank the reviewer for reading our paper very carefully and spotted such typos. We have already fixed all typos in the revised manuscript.

With gratitude,

Author(s) of Submission 3225

I thank authors for the additional experiments and reworking their math details. Could you please upload a revised version of the paper with these changes applied for review?

Dear Reviewer Yt4X

Thank you for your timely follow-up. We have attached the revised manuscript. Definitions 1 and 2 (p. 3) now distinguish equality in distribution over all measurable sets of models from equality of the maintained and retrained models for every shared seed. Appendix B.2 gives the proof for Sparse Forest. Figure 4, 6 (pp. 8-9) summarizes the FUTURE comparison, and Tables 1 and 2 (pp. 26–27) report the streaming and batch results.

We appreciate your careful reading and the opportunity for refining and clarifying.

Sincerely yours,

Author(s) of Submission 3225

Comments on the paper

1 comment
AuthorsOpenReview ↗

Rebuttal and Revision Summary

Dear Area Chair and Reviewers,

We sincerely thank the Area Chair for the work and Reviewers (Yt4X, ejAT, 6oXU) for their constructive feedback.

Brief Context: Sparse Forest (SF) maintains tree ensembles under interleaved streams of sample insertions, deletions, and queries via three mechanisms: structural sparsity (uniform-grid histograms + tree subsampling), reconstruction sparsity (in-place subtree repair via sample migration), and split-change sparsity ((ε,φ)(\varepsilon,\varphi)-suboptimal split retention with O(1)\mathcal{O}(1) gap certificates). At ε=0\varepsilon=0, SF guarantees total exactness (bit-identical to retraining from scratch, 5.69×5.69\times faster than DynFrs, the fastest baseline); at (ε,φ)=(0.1,1/2)(\varepsilon,\varphi)=(0.1, 1/2), SF achieves a 25.68×25.68\times average speedup over DynFrs with slightly better accuracy/AUC.

  • Mathematical rigor of exactness definitions [Reviewer Yt4X]. To address ambiguities regarding continuous model spaces, random-seed coupling, and retraining specifications, we reformulated Distributional Exactness over measurable model spaces and defined Total Exactness as deterministic seed-wise bit-identity under a fixed algorithm specification. We formally proved Total Exactness for SF (ε=0\varepsilon=0) and verified bit-for-bit identity with scratch retraining across all 2,700 checkpoints (Section 2, Appendix B.2, Table 6); Reviewer Yt4X thanked us for reworking the math and requested the revised PDF, which is now uploaded.

  • New baseline (FUTURE) and expanded benchmarks [Reviewers Yt4X, ejAT]. Addressing requests for missing baselines, capacity-matched controls, and broader task coverage, we added comparisons against FUTURE (CIKM 2025), showing that SF substantially reducing post-deletion retraining divergence and running 5.5×5.5\times faster on large-batch deletions, and orders of magnitude faster in online (un)learning stream. We also added equal-tree capacity controls (raising SF's mean speedup over DynFrs from 25.7×25.7\times to 37.6×37.6\times) and four larger multiclass and regression benchmarks.

  • Component ablations, split grids, and complexity analysis [Reviewers ejAT, 6oXU]. To address requests for isolating SF's design components and refining our subsampling complexity claims, we added controlled ablations confirming that structural sparsity, split-change sparsity, and in-place repair each provide critical, complementary speedups across exact and relaxed regimes, while uniform split grids match random thresholds in accuracy/AUC at faster speeds (Tables 7–9, Figure 5). We also refined our subsampling analysis to distinguish path traversals (O(1/q)\mathcal{O}(1/q) at capped depth, matching empirical scaling) from full subtree rebuilds, and moved key definitions and ablations into the main text (Sections 3.1 & 4).

  • Local amortized bound vs. end-to-end efficiency [Reviewer 6oXU]. Reviewer 6oXU noted that default split retention does not enforce our worst-case amortized local node-scan bound and asked how enforcing it impacts runtime. We proved that enforcing slack restoration at reevaluation strictly guarantees the local bound, and empirically showed that while this variant reduces local node reevaluations as predicted, it triggers frequent, costly subtree repairs that slow end-to-end stream processing by 13×13\times—validating default SF's split retention as a deliberate design choice for overall efficiency (Section 3.3, Appendices B.3 & D.2, Figure 8).

Detailed point-by-point responses are provided in our reviewer-specific replies and Appendices B–D.

Best regards,

Author(s) of Submission 3225

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.