{"id":"0d4ad827-8808-496f-b2d3-416a9af7f539","arxiv_id":"2502.01634","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"A GBDT can have data added or removed in place, without full retraining, by updating only affected tree nodes and stored split statistics.","lead":"This paper presents a framework that lets a trained gradient boosting (GBDT) model accept new data or delete old data in place, without retraining from scratch. It could make production machine learning systems adapt faster to new information and honor data deletion requests cheaply.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lazy derivative refresh is the load-bearing approximation: leaf scores are updated without retraining, but residuals for later trees are refreshed only on retrained nodes, so the claimed closeness to retrained GBDT is unquantified and Appendix D does not cover it.","rationale":"The reader's conditional verdict is appropriate. Independent support exists: code is released, benchmarks are broad, and the backdoor/MIA checks plus ablations give real empirical evidence. However, the framework's core speed-accuracy tradeoff is carried by lazy derivative updates, not by the split-robustness inequalities. The paper never quantifies the error introduced by not propagating changed leaf scores through later boosting iterations. Appendix D addresses a different mechanism (split stability) and contains a visible sign error in Eq. (11). The proposed A/B/C experiment isolates the effect of the lazy update and would determine whether the concern is material. I agree with the reader that the theory needs relabeling; I place less weight on the robustness-split proofs because the deployed retraining decisions can be validated empirically, and more weight on the untested residual-propagation assumption. Thus the reader's conditional verdict stands; if the A/B/C test shows divergence, the condition should be stated as a hard requirement rather than a style change.","tokens_in":38529,"tokens_out":8908,"duration_ms":93302,"concrete_test":"Using the released code, run incremental updates with |D'|=1% of Dtr, M=100, J=20 on Adult, Covtype, and Letter under three conditions: (a) the published lazy derivative update; (b) a variant that, after each tree update, refreshes residuals and hessians for every training row whose leaf score changed (touching more data but still no full retrain); and (c) full retraining on Dtr ∪ D'. Compare test error and functional similarity φ to (c). If (a) is within seed-level noise of (b), the lazy update is benign; if (a) is measurably worse (for example, φ drops by more than 1 point or test error diverges on any dataset), then the central accuracy claim depends on an unvalidated approximation and the paper should either bound the staleness error or report accuracy with lazy refresh disabled.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is that after an O(|D'|) in-place pass the model closely matches retraining on Dtr ∪ Din \\ Dde. The algorithm's correctness for future boosting iterations depends on the residuals used by trees m+1,...,M-1. Algorithm 3 updates leaf prediction values (line 9) for every leaf reached by D', even when no split changes. A leaf-score change alters the gradient of every training row in that leaf; in standard boosting those changed gradients must be used when fitting all subsequent trees. The Adaptive Lazy Update (Section 3.2) instead refreshes derivatives only when retraining occurs, and Appendix N confirms this: 'when a sub-tree requires retraining, the derivatives are updated,' while unchanged-best-split nodes keep outdated derivatives. Thus the model can accumulate gradient staleness even though its leaf scores have moved. The approximations in Appendix D (Distance Robust, Eq. (8)-(13), and Robustness Split, Eq. (14)-(20)) only bound split-gain movement under a λ-fraction add/removal; they do not bound error from stale residuals, and Eq. (11) contains a sign error in the left-child term that makes the derivation suspect. Empirical tables show the approximation often works, but Table 13's error metric recomputes leaf scores with latest residuals rather than measuring the actual stale-gradient model, so it cannot detect this failure mode. If stale residuals propagate badly on some data distributions, the O(D') speed comes at unquantified accuracy cost.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes an in-place online learning framework for Gradient Boosting Decision Trees (GBDT) that supports both incremental (adding data) and decremental (removing data) learning without changing the number of parameters or trees. The core algorithm (Algorithm 3) traverses existing tree nodes, recomputes the best split using only the online dataset D′ and stored aggregate statistics, keeps splits that remain best, retrains only sub-trees whose best split changed, and updates leaf prediction values. To reduce cost, the authors introduce three optimizations: split-candidate sampling, an adaptive lazy update for derivatives (refreshing residual/hessian values only for retrained sub-trees), and an adaptive split-robustness tolerance. They provide a theoretical analysis (Appendix D) relating the sampling rate α, the online-data fraction λ, and a robustness tolerance σ to the probability of retaining splits, and they report extensive experiments on 10 public datasets plus high-dimensional and time-series data, including backdoor attack and membership-inference tests. The central claim is that adding or deleting a small data fraction can be done in O(|D′|) time rather than O(|Dtr|) retraining, with accuracy close to a full retrain.","tokens_in":38805,"tokens_out":4511,"duration_ms":43789,"significance":"If the central claim holds, the paper addresses a practically important gap: GBDT models are widely deployed, yet standard implementations cannot efficiently add or remove training instances. The proposed framework is one of the first to handle incremental and decremental learning in a unified in-place manner, and the empirical study is unusually broad: it includes large datasets (SUSY, HIGGS, Covtype), high-dimensional datasets (RCV1, News20), continual batch addition/removal, unseen-class expansion, and security-oriented evaluations (backdoor injection/removal and membership inference). The authors also release an open-source implementation, which strengthens reproducibility. The main caveats are that the theoretical justification in Appendix D contains unquantified linear approximations and a sign inconsistency, and that the adaptive lazy update is not covered by that theory; the claimed accuracy-cost trade-off therefore rests primarily on empirical evidence. The results are plausible and potentially useful, but the paper needs revision before the central claims can be considered fully supported.","major_comments":[{"comment":"The adaptive lazy update is the load-bearing approximation for the O(|D′|) claim, but the paper never quantifies how much accuracy is lost by using outdated derivatives. Algorithm 3 line 9 updates leaf prediction values whenever any data from D′ reaches a leaf, even if the node's split is unchanged; in standard boosting, changing a leaf score changes the gradient of every training row in that leaf, and those changed gradients should be used when fitting all subsequent trees. The paper instead refreshes derivatives only when a sub-tree is retrained (Appendix N states: 'when a sub-tree requires retraining, the derivatives are updated'), so rows in unchanged-but-updated leaves keep stale residuals. The theoretical results in Appendix D (Distance Robust, Robustness Split) bound split-gain movement under a λ-fraction add/removal; they do not bound the error introduced by stale residuals in later boosting iterations. Table 13, which reports 'approximation error of leaf scores', recomputes leaf values with the latest residual and hessian for both the online-learned and retrained models, so it measures a hypothetical model with fresh leaf scores, not the actual model produced by Algorithm 2. Consequently, Table 13 cannot detect the failure mode of the lazy derivative update. Either add a theorem that bounds the distance between the online-updated model and the retrained model under the lazy update, or provide an experiment that evaluates the actual deployed model (e.g., test error and functional similarity, as in Tables 6 and 8) in settings where splits are unchanged but leaf values are updated, with a breakdown of how many residuals are stale.","section":"Section 3.2, Appendix N, Table 13"},{"comment":"The proof of Definition 1 (Distance Robust) contains a sign inconsistency. Eq. (10) expands (1 − λ)Gain(s) − Gain(s + NΔ) with a left-child term (1 − NΔ/Nls)(Σg)²/(Σh), but Eq. (11) replaces that factor with (1 + NΔ/Nls) for the left child while keeping (1 − NΔ/Nrs) for the right child. The sign flip is what turns the left-child contribution into a positive term in Eq. (12), and the final inequality in Eq. (13) depends on this flip. The derivation also relies on an unstated linear approximation of the gain under removal (treating removed sums as scaling by λ) and on the assertion E[NΔ] = 1/α without derivation. Since these results are used to justify the split-candidate sampling rate α and the hyper-parameter trade-offs advertised in Section 3.3, the proof must be corrected or the statements demoted to heuristic motivation. Please either fix the algebra and provide the missing assumptions, or explicitly frame the robustness conditions as empirical observations rather than theorems.","section":"Appendix D, Eqs. (8)-(13)"},{"comment":"The adaptive split robustness tolerance σ is motivated by the empirical observation in Figure 2, which shows that the best split often shifts to the second-best split when |D′| increases. However, the paper does not connect σ to the theoretical conditions in Appendix D; the robustness definitions involve λ and α but not σ. The suggestion that σ ≈ 0.1 is therefore a heuristic, and Figure 10 shows that increasing σ can reduce functional similarity considerably (e.g., the Letter dataset drops by about 5% when σ goes from 0 to 0.5). The abstract claims that the paper 'theoretically show[s] the relationship between the hyper-parameters of the proposed optimizations', but the relationship among α, λ, and σ is only partially established. Please either derive a bound that includes σ or revise the claim to state that the trade-off is demonstrated empirically.","section":"Section 3.4 and Figure 2"}],"minor_comments":[{"comment":"The row labeled 'Gain Computing & Split Finding' lists complexity O(αBJσ), which mixes α, B, J, and σ in a way that is not explained in the table footnote. The surrounding text gives the more explicit formula O(J|D′|·Pσ + JαB·(1−Pσ)), and the table should match that expression or define the symbols used.","section":"Appendix F, Table 5"},{"comment":"The captions for Figures 3 and 5 repeat the phrase 'The impact of tuning data size on the number of retrained nodes for each iteration', but the figures actually plot test accuracy as a function of trained data proportion. These captions should be corrected to describe the accuracy curves.","section":"Figure captions"},{"comment":"In Algorithm 3, line 4 computes the 'best gain' with Eq. (5), but line 5 compares this to the current split s using inequality s′ ≠ s. Since Eq. (5) returns a gain value, the comparison should be between the best split index and s; the wording in the text and algorithm is inconsistent. Clarify whether s′ denotes a gain or a split.","section":"Section 2.3, Algorithm 3"},{"comment":"The speedup values in Table 3 are sometimes below 1 (e.g., SUSY decremental learning at |D′|=1% reports a 0.2× speedup against ThunderGBM on GPU, and several HIGGS rows are below 0.5×). The text claims the method is 'substantially faster than other methods', which is accurate for the incremental/decremental baselines but not for the GPU comparison. Please qualify the claim and discuss when GPU retraining can be faster.","section":"Section 4.2, Table 3"},{"comment":"In the Robustness Split proof, the denominator of the second term in Eq. (16) appears to have a missing minus sign: it reads 'Σ_{xi∈rs} hi,k  Σ_{xi∈rs∩D′} hi,k' without a subtraction operator. This is likely a typographical error and should be corrected for readability.","section":"Appendix D, Eq. (16)"}],"recommendation":"major_revision","confidential_remarks":"The paper is a credible empirical study of an important practical problem, and the experimental breadth is a clear strength. However, the theoretical appendix contains a concrete sign error and relies on an unquantified linearization, and the adaptive lazy update—central to the claimed speed advantage—lacks both a theoretical guarantee and an appropriate empirical metric in Table 13. These issues are fixable within the scope of the manuscript: the authors can either tighten the theory or restate the robustness results as heuristics, and they can add an experiment that measures the actual stale-gradient model rather than a recomputed-leaf-score surrogate. I recommend major revision rather than rejection because the core empirical evidence is substantial and the framework is likely to be useful even if the theoretical framing is weakened."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe short version: this is a real systems contribution—unified in-place incremental and decremental learning for GBDT with the same model size—and the empirical work is broad enough that it deserves a serious referee. The theoretical wrapping is thinner than claimed, and one load-bearing approximation, the lazy derivative refresh, is only empirically justified.\n\nWhat's new: prior work handles only one direction, iGBDT for adding, DeltaBoost and the authors' own MUinGBDT for deletion. This paper unifies both in a single framework, stores split statistics to avoid touching the training set, and adds adaptive lazy updates and a split robustness tolerance. The experiments are the strong point: ten public datasets, updates ranging from a single point to 1% of the data, backdoor injection/removal, membership inference, time series, high-dimensional data, and ablations over the main hyper-parameters. CPU speedups for small updates are dramatic, and test accuracy after update tracks retraining in most cases. The code is released.\n\nWhere it gets soft. The theory in Appendix D is heuristic. The Distance Robust and Robustness Split proofs rely on unquantified linear approximations, and Eq. (11) has a sign/denominator typo that the surrounding derivation has to correct. The practical conclusion, that smaller α or λ gives more robust splits, is plausible, but the proof does not establish it rigorously.\n\nThe larger concern is the lazy derivative update. When a leaf prediction changes but the split is kept, gradients for rows in that leaf are not refreshed before fitting later trees. The authors acknowledge this in Appendix N, but Table 13 does not measure the actual stale-gradient model: it recomputes leaf scores with the latest residuals. So the reported approximation error is not the error of the deployed model. The end-to-end accuracy tables look good, but they are empirical and dataset-limited, and there are no error bars or multiple seeds. A distribution where stale residuals matter could be a real failure mode.\n\nMemory is also a practical issue: storing per-bin statistics costs 185 GB on RCV1 with 47k features, which limits scope.\n\nBottom line: the core idea is a sound heuristic and the evaluation is substantial. If the authors relabel the theory as heuristics, add variance reporting, and either bound or better characterize the stale-gradient effect, this would be a solid accept. I'd send it to review with a request for major revision on those points.\n\nRead this if you work on GBDT systems, machine unlearning, or online learning for tabular data.","headline":"A genuinely useful GBDT incremental/decremental learning system with broad, convincing experiments, but the theory is heuristic and the lazy-derivative approximation deserves a caveat and better measurement.","tokens_in":39363,"tokens_out":4153,"would_cite":true,"duration_ms":35062,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"A trained GBDT can accept new rows or forget old ones in place, keeping the same tree count and accuracy close to retraining from scratch.","keywords":["online learning","gradient boosting decision trees","incremental learning","decremental learning","data deletion","split candidate sampling","lazy derivative update","machine unlearning"],"falsifier":"Take a trained GBDT and remove a batch $D_{de}$ of size 0.1% engineered so that at some node two candidate splits have nearly equal gain, then recompute every split's gain from the full remaining data. If the best split changes even though the Distance Robust inequality predicted it would be kept, the linear-perturbation premise is falsified; alternatively, run an add-then-delete cycle and compare leaf scores to a retrain-from-scratch model, where growing divergence of the lazy derivative update would show accumulated drift.","tokens_in":38259,"feed_emoji":"🌳","tokens_out":12451,"duration_ms":102777,"temperature":0.7,"pith_summary":"Gradient-boosted decision trees (GBDTs) are usually batch-only: once trained, they cannot absorb new rows or forget old ones without rebuilding the whole ensemble from scratch, which is slow on large data. This paper claims that a well-trained GBDT can instead be updated in place, adding a new batch $D_{in}$ or removing a subset $D_{de}$ while leaving the number of trees and their parameter count unchanged. The intended target is the model a full retrain on $D_{tr}$ plus $D_{in}$ minus $D_{de}$ would produce, and the framework is designed to get close to that model at a cost that scales with the small changed batch rather than the whole dataset. The paper also identifies three interacting controls—the fraction of data being added or removed, the split-candidate sampling rate, and a split-robustness tolerance—and argues that they trade accuracy against update cost in a predictable way. If correct, this makes frequent small updates and targeted data deletion practical for GBDT deployments.","feed_headline":"Add or delete data from a GBDT in place, up to 974x faster","feed_subtitle":"Small batches update the ensemble without changing tree count; accuracy stays near a full retrain.","key_machinery":"The load-bearing object is the weighted squared-error gain of a candidate split, $Gain(s)$ from Eq. (5): the squared sum of first derivatives divided by the sum of second derivatives for the left child, plus the same for the right child, minus the parent term. Because this expression uses only per-node sums, the framework stores, for every candidate split, the aggregate $S_{rp}$ (sum of residuals) and $S_{pp}$ (sum of second derivatives) during training and refreshes them from the online batch's rows, avoiding a scan of $D_{tr}$. Around this core sit three optimizations: split-candidate sampling (only a fraction $\\alpha$ of the $B$ discretized split points are considered, so the expected gap between the best split and its nearest competitor grows as $1/\\alpha$), the adaptive split robustness tolerance (a split is kept when it stays in the top $\\sigma$ fraction of candidates, with $\\sigma$ around 0.1 recommended), and the lazy derivative update (leaf scores and gradients are recomputed only for leaves reached by changed data). The named robustness conditions—Distance Robust, which bounds the nearest alternative split by a gain-ratio inequality, and Robustness Split, which requires $Gain(s) > Gain(t)/(1-\\lambda)$—are what the proofs use to justify keeping old splits.","core_discovery":"The paper's central claim is that incremental and decremental learning on GBDT can be unified as the same in-place operation: traverse each existing tree from root to leaves, recompute the best split gain using only the added or removed rows, keep the split when it remains optimal or within tolerance, and retrain only the sub-tree rooted at nodes whose best split actually shifts. Deletion is treated as the inverse of addition with the same code path. The argument is carried by the structure of the split gain in Eq. (5), which decomposes into per-node sums of first derivatives (residuals) and second derivatives (hessians); the framework stores those sums for every candidate split during training, so an online update only needs to add or subtract the changed rows' contributions. The paper reports that on public datasets this yields models whose predictions match a retrain-from-scratch model in most cases above roughly 98% functional similarity for small batches, while cutting update time to a small fraction of retraining, with backdoor experiments demonstrating that a trigger learned by incremental learning is erased again by decremental learning.","pith_inferences":["Because the gain function decomposes into per-node sums, the same in-place strategy may transfer to other additive tree ensembles, such as random forests or arbitrary split-gain trees, though the paper does not claim this.","The robustness-tolerance analysis implies a per-dataset calibration procedure: measure how often split rankings permute on a small holdout and set $\\alpha$ and $\\sigma$ accordingly, rather than using fixed defaults.","A stress test the paper does not report is repeated add/delete cycling; the lazy derivative update could accumulate drift over many small perturbations, so comparing leaf scores after many cycles against a retrained model would bound this effect.","The membership-inference experiment positions decremental learning as a privacy operation, but the framework provides no certified-unlearning guarantee, so a formal audit bound would be needed before relying on it for regulated data deletion."],"forward_implications":["Adding or deleting 0.1%–1% of the training data costs $O(|D'|)$ rather than $O(|D_{tr}|)$, so frequent small updates become practical on large datasets.","Tree count and parameter count stay fixed, so online updates do not inflate model size or inference latency.","Continual batch addition and removal (for example 5% → 100% → 5% of the data) tracks retrain-from-scratch accuracy on the reported datasets.","Backdoor triggers inserted by incremental learning are removed by decremental learning, with attack success rate falling back to clean-model levels."],"supporting_citations":[{"why":"Provides the Robust LogitBoost algorithm (Algorithm 1) whose gain formula and derivative sums the online framework reuses.","marker":"(Li, 2010)"},{"why":"iGBDT is the incremental-learning baseline; its lazy-update idea is extended here and its cost is shown to scale poorly with data fraction.","marker":"(Zhang et al., 2019)"},{"why":"The GBDT unlearning framework whose stored statistical information is extended to unified incremental/decremental online learning.","marker":"(Lin et al., 2023a)"},{"why":"DeltaBoost is the decremental-learning baseline; the paper contrasts its disjoint-subdataset degradation with full per-node updates.","marker":"(Wu et al., 2023)"},{"why":"Establishes residual-coupling across boosting trees, the key property that makes in-place updates nontrivial.","marker":"(Friedman et al., 2000)"},{"why":"XGBoost serves as the retrain-from-scratch baseline for training time and online-learning speedups.","marker":"(Chen & Guestrin, 2016)"},{"why":"LightGBM serves as a retrain-from-scratch baseline for training time, memory, and accuracy comparisons.","marker":"(Ke et al., 2017)"},{"why":"OnlineGB is the online boosting baseline compared for incremental learning.","marker":"(Leistner et al., 2009)"}],"fun_headline_variants":["In-place GBDT updates: add or delete rows on the fly","First in-place add/delete for GBDT with near-retrain accuracy","Add or remove GBDT data in place, keep accuracy, cut time","GBDT learns incrementally and decrementally in place","Unified in-place incremental/decremental GBDT learning"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The central load-bearing premise is a linear-perturbation approximation in the Appendix D proofs: adding or removing a small fraction $\\lambda$ of data is treated as shifting split gains approximately linearly, with the nearest alternative split expected to sit at distance $1/\\alpha$; the Distance Robust proof relies on this approximation, and the derivation in Eq. (11) contains a sign inconsistency. If this linearization fails, the framework either keeps a stale split (accuracy loss) or retrains too often (speed loss).","fun_headline_variants_meta":{"raw":{"variants":["In-place GBDT updates: add or delete rows on the fly","First in-place add/delete for GBDT with near-retrain accuracy","Add or remove GBDT data in place, keep accuracy, cut time","GBDT learns incrementally and decrementally in place","Unified in-place incremental/decremental GBDT learning"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00026,"raw_usage":{"total_tokens":1598,"prompt_tokens":964,"completion_tokens":634,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":580,"completion_tokens_details":{"reasoning_tokens":541}},"tokens_in":580,"tokens_out":634,"duration_ms":5800,"temperature":1.0,"reasoning_tokens":541,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T14:45:00.440023+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a trained GBDT and remove a batch $D_{de}$ of size 0.1% engineered so that at some node two candidate splits have nearly equal gain, then recompute every split's gain from the full remaining data. If the best split changes even though the Distance Robust inequality predicted it would be kept, the linear-perturbation premise is falsified; alternatively, run an add-then-delete cycle and compare leaf scores to a retrain-from-scratch model, where growing divergence of the lazy derivative update would show accumulated drift.","supporting_citations":[],"review_version":1}