{"id":"a9823d0f-1cb4-46b3-9d76-ec200ee5833d","arxiv_id":"2506.06073","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"The paper introduces system-aware unlearning and gives the first exact unlearning algorithm for linear classification that stores a sublinear-size core set instead of the entire dataset.","lead":"This paper proposes a weaker definition of machine unlearning where the attacker only sees what the system stores, not the whole training set, and shows that under this definition a linear classifier can be unlearned exactly while storing far less than the full data. If this threat model is accepted, it turns an impossible memory problem into a practical one for large systems.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Proof of Theorem 4.2 uses A_t^{-1} in place of A_{t-1}^{-1}; the monotonicity argument is incomplete as written, though the claim appears repairable.","rationale":"The reader's weakest assumption concerns the threat model: whether an attacker can realistically be prevented from recovering S\\U. That is a legitimate modeling question, but it is not an internal inconsistency, and the paper explicitly frames its contribution relative to this model. A more concrete and immediately testable issue is the monotonicity proof for the central exactness claim. Theorem 4.1 depends on Theorem 4.2, and the published proof of Theorem 4.2 uses the wrong covariance matrix in a key inequality. The error is localized and the theorem appears fixable by comparing with A_{t-1} instead of A_t, so I do not recommend changing the reader's conditional verdict. I disagree with the reader's choice of weakest assumption because the proof gap is the most load-bearing technical risk for the paper's headline linear-classification result; if the corrected monotonicity argument fails, the exact-unlearning claim would be unproven, whereas the threat-model concern is a definitional choice the paper explicitly defends.","tokens_in":34636,"tokens_out":38582,"duration_ms":369408,"concrete_test":"Re-derive Theorem 4.2 using A_{t-1} in place of A_t: verify x_t^T (A_{t-1} - x_j x_j^T)^{-1} x_t >= x_t^T A_{t-1}^{-1} x_t > T^{-kappa} for every queried point x_t and deleted queried point x_j. Also run a numerical check on random linear datasets: execute BBQSAMPLER on S, delete one queried point x_j, execute BBQSAMPLER on Q\\{x_j}, and confirm the returned queried set equals Q\\{x_j} for all deletions.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The exactness of Algorithm 1 (Theorem 4.1) rests entirely on Theorem 4.2, whose proof as written contains a false inequality. It states that for a point queried at time t, x_t^T A_t^{-1} x_t > T^{-kappa}; Algorithm 1's query condition is actually x_t^T A_{t-1}^{-1} x_t > T^{-kappa} (Algorithm 1, line 4). Since A_t = A_{t-1} + x_t x_t^T, the post-update leverage is q/(1+q), which can drop below T^{-kappa} even when q > T^{-kappa}; for example, q = 1.1 T^{-kappa} with T^{-kappa} = 0.1 gives q/(1+q) ≈ 0.099 < 0.1. The subsequent Sherman-Morrison comparison is performed with A_t, so the displayed argument does not establish that re-running on C(S)\\U queries every remaining point. The theorem is likely repairable: deleting x_j before time t replaces A_{t-1} by A_{t-1} - x_j x_j^T, whose inverse is larger, giving x_t^T A_{t-1\\setminus x_j}^{-1} x_t >= x_t^T A_{t-1}^{-1} x_t > T^{-kappa}. But as published, the central exactness proof has a gap. No other load-bearing flaw was identified in the linear-classification claim under the paper's stated threat model.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a new notion of machine unlearning, called system-aware unlearning, in which the guarantee is stated with respect to a subset S' of the original sample S that the learning algorithm actually relies on; the attacker is assumed to observe only the state-of-system after unlearning, not the full remaining dataset S\\U. The authors argue that this generalizes traditional certified unlearning (which corresponds to S'=S) and that core-set and sample-compression algorithms are natural instantiations. The main algorithmic contribution is an exact system-aware unlearning algorithm for linear classification (Algorithm 1), built on the BBQSAMPLER selective-sampling procedure, with claimed memory O(d T^kappa log T), sublinear in the sample size for kappa<1, together with a deletion-capacity bound and an expected-deletion-time analysis. A second algorithm (Algorithm 2) extends the scheme to general function classes via a pool-based active-learning query rule. The paper also reports experiments on two datasets comparing Algorithm 1 with SISA and exact retraining.","tokens_in":34944,"tokens_out":20416,"duration_ms":208543,"significance":"The definitional proposal is a substantive and debatable contribution: it makes explicit that the strength of an unlearning guarantee depends on what an attacker can observe, and it provides a framework in which algorithms that rely on few stored points can achieve exact unlearning at low memory cost. If the technical results are correct, the linear-classification algorithm is notable because it evades the lower bound of Cherapanamjeri et al. (2025) by changing the threat model rather than by contradicting it. The paper is also honest that the guarantee is relative to the new definition and that a traditional attacker who can recover S\\U would not be protected. The exactness argument is by construction rather than circular, and the selective-sampling connection is a useful conceptual bridge. However, several load-bearing proof steps in the current manuscript are incorrect or incomplete, so the advertised results are not yet established as written.","major_comments":[{"comment":"The proof of Theorem 4.2 contains a false inequality that is load-bearing for the exactness claim. Algorithm 1 queries at time t when x_t^T A_{t-1}^{-1} x_t > T^{-kappa}, but the proof states that a queried point satisfies x_t^T A_t^{-1} x_t > T^{-kappa}. These are not equivalent: by Sherman-Morrison, x_t^T A_t^{-1} x_t = q/(1+q) with q = x_t^T A_{t-1}^{-1} x_t, and q/(1+q) can be below T^{-kappa} even when q > T^{-kappa}. The displayed Sherman-Morrison comparison is then performed with A_t, so the argument does not establish that rerunning on C(S)\\U queries every remaining point. Since Theorem 4.1 relies directly on Theorem 4.2, the central exactness proof has a gap. The gap appears repairable, e.g. by working with A_{t-1} and using that deleting x_j before time t replaces A_{t-1} by the smaller matrix A_{t-1} - x_j x_j^T, whose inverse is larger, but the manuscript as written is not correct.","section":"Section 4, Theorem 4.2 and its proof"},{"comment":"The same pre-update/post-update confusion appears in the query-complexity argument that supports the sublinear-memory claim. In the proof of Theorem D.8, r_t is defined as x_t^T A_t^{-1} x_t, and the query count is written as NT = sum over {r_t > T^{-kappa}} 1. But Algorithm 1 queries when x_t^T A_{t-1}^{-1} x_t > T^{-kappa}; for points with leverage just above threshold, the post-update value q/(1+q) is below T^{-kappa}, so the displayed sum undercounts the true number of queries. A correct bound would use the pre-update leverage or threshold the post-update leverage at T^{-kappa}/(1+T^{-kappa}). In addition, Lemma D.4 and Corollary D.5 are stated for arbitrary x with no precondition, but the asserted bound x^T A_{T\\U}^{-1} x <= e T^{-kappa} fails for directions that have not been observed (the quadratic form can be as large as 1/lambda). The induction proof has no valid base case. These issues affect the memory bound of Theorem 4.3 and the stability estimates used for deletion capacity, although they also appear to be repairable.","section":"Appendix D, Theorem D.8 and Lemma D.4 / Corollary D.5"},{"comment":"The exactness of Algorithm 2 for general function classes rests on Theorem 5.2, but the proof as written does not establish the claimed monotonicity of the GENERALBBQSAMPLER. The key step asserts that the argmax of D^2 over the remaining pool is unchanged after deleting a previously queried point. Coordinate-wise monotonicity of D^2 under deletion does not imply this: removing a point from the denominator can increase D^2(x; .) by different factors for different x, so the greedy maximizer can change, and a point that was queried in the original run may never be selected in the rerun. The displayed expression D^2(x, Q'_l* \\ {x_j}) is also not the quantity that the algorithm uses, since x_j is not in the rerun's queried set. Because Theorem 5.1 depends on Theorem 5.2, the general-function-class exact-unlearning claim is not established as written. The authors should either prove the property under additional assumptions on the query criterion, modify Algorithm 2 so that the unlearning update actually reruns the sampler on C(S)\\U and store the resulting queried set, or substantially qualify the general-class contribution.","section":"Section 5, Theorem 5.2 and its proof"}],"minor_comments":[{"comment":"The proof and surrounding text refer to 'the traditional definition of unlearning (Definition 2.3)', but Definition 2.3 is system-aware unlearning; the traditional definition is Definition 2.1.","section":"Section 3, Theorem 3.1"},{"comment":"The text says 'the deletion capacity bound in Theorem 4.1 only applies to core set deletions', but the capacity bound is Theorem 4.3; Theorem 4.1 is the exactness statement.","section":"Section 4.1, first paragraph"},{"comment":"Algorithm 1 states 0 <= kappa <= 1, but Theorem D.8 and its proof use quantities such as 1/kappa and assume kappa in (0,1); the endpoint case kappa=0 should be clarified or excluded.","section":"Algorithm 1 and Theorem D.8"},{"comment":"Lemma D.4 should state the condition under which the initial bound x^T A_T^{-1} x <= T^{-kappa} holds (e.g. for points that were unqueried at their arrival time), since the claim as written is false without this restriction.","section":"Appendix D, Lemma D.4"},{"comment":"The function returns only sign(w^T x), while the state-of-system definition in Theorem 4.1 includes (A(S,U), C(S)\\U); the return statement should make explicit that the remaining core set and the updated matrices are part of the returned state.","section":"Algorithm 1, lines 17-20"}],"recommendation":"major_revision","confidential_remarks":"The paper's central idea is timely and the linear-case framework is promising, but the current manuscript contains load-bearing proof errors: the exactness proof of Theorem 4.2 uses the post-update leverage instead of the pre-update leverage, the query-complexity proof in Theorem D.8 repeats a related mistake, and the general-class monotonicity proof in Theorem 5.2 is not valid. My sense is that the linear-classification results are repairable with modest changes, and the general-class extension may require either a genuinely different argument or a modified algorithm. I would encourage the editor to send the paper back for a revision rather than reject, provided the authors can supply correct proofs for these points."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The thing to know: this is a solid, genuinely new contribution, not a repackaging. The system-aware unlearning definition (Def. 2.3, with S' a subset of S that is fixed before U is known) is a real modeling contribution, and the observation that a label-independent monotone query condition makes the queried set deletion-stable is the right algorithmic lever. For linear classification under that threat model, the exact unlearning algorithm with memory O(dT^kappa log T) is an honest bypass of the Cherapanamjeri et al. storage lower bound. The linear-case story holds up: Theorem 4.1 and the excess risk/deletion capacity bounds are plausible, and the use of the BBQ sampler is a good fit. I would trust the main claim after minor fixes.\n\nWhere it is soft. First, the proof of Theorem 4.2 as written uses x_t^T A_t^{-1} x_t > T^{-kappa}, but the query condition in Algorithm 1 is x_t^T A_{t-1}^{-1} x_t > T^{-kappa} (line 4). Since A_t = A_{t-1} + x_t x_t^T, the post-update leverage is q/(1+q), which can dip below threshold even when q exceeds it. This is a genuine gap in the displayed proof, but it is clearly repairable: a deletion before time t only decreases the covariance, so x_t^T A_{t-1\\setminus x_j}^{-1} x_t >= x_t^T A_{t-1}^{-1} x_t > T^{-kappa}. The theorem survives with that fix. Second, the general-function extension (Theorem 5.2) has a more substantive gap: the proof asserts that after deleting a queried point, the stage-wise greedy selection will query the same set, but it does not justify that the pool composition after each stage is identical between the two executions. That may also be repairable, but it needs more than a line. The experiments are illustrative, not probative — no error bars, no hyperparameter reporting — but they are not load-bearing for the main claim.\n\nOn the threat model itself: if an attacker can recover S\\U, Definition 2.3 with S'=C(S) gives nothing. The authors argue this is unrealistic, and that is a legitimate position, not a sleight of hand. The mutual-information argument (Theorem 2.4) supports the direction of the claim.\n\nWho it is for: anyone working on unlearning theory, especially on sample-compression and selective-sampling connections, and anyone building practical unlearning for linear probing. The paper deserves a serious referee and, with the indexing fix and a tightened Section 5 proof, it could be a good ICML-level paper. I would engage with it in review rather than desk-reject.","headline":"The paper's system-aware unlearning definition and the exact sublinear-memory linear algorithm are real, but the proof of the key monotonicity theorem (4.2) has a repairable indexing gap and the general-function extension is shakier.","tokens_in":35475,"tokens_out":1661,"would_cite":true,"duration_ms":17995,"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":"Traditional unlearning assumes an attacker who knows the full remaining dataset; the paper replaces that with a system-aware definition under which a selective-sampling linear classifier can unlearn exactly while storing only a sublinear…","keywords":["machine unlearning","system-aware unlearning","selective sampling","sample compression","core sets","linear classification","deletion capacity","data privacy"],"falsifier":"To test the core claim, search for the smallest dataset $S$ and deletion set $U$ for which running the selective sampler on $C(S)\\setminus U$ fails to query all of $C(S)\\setminus U$. Theorem 4.2 asserts this never happens; a counterexample would break the equality $C(C(S)\\setminus U)=C(S)\\setminus U$ and with it the exactness guarantee, since the unlearned state would no longer coincide with a fresh run on the core set.","tokens_in":34435,"feed_emoji":"🗑️","tokens_out":12436,"duration_ms":104246,"temperature":0.7,"pith_summary":"Machine unlearning traditionally demands that after a deletion request the model be indistinguishable from one retrained on the full remaining dataset, a bar that forces exact unlearning algorithms to store the entire sample. The paper argues this is the wrong threat model: a realistic attacker can only see what the system actually stored, not every point it ever encountered. It introduces system-aware unlearning, where the post-deletion state of the system must be indistinguishable from the state produced by running the same algorithm on $S' \\setminus U$ for a fixed subset $S'$ of the training set, and shows that algorithms which learn from a small core set can meet this definition exactly. The concrete payoff is an exact system-aware unlearning algorithm for linear classification whose memory is $O(dT^\\kappa \\log T)$, sublinear in the sample size, with corresponding bounds on deletion capacity, excess risk, and deletion time.","feed_headline":"Store less, forget faster: exact unlearning in sublinear memory","feed_subtitle":"Redefining the attacker's view lets a selective sampler erase deletions without retraining on the full dataset.","key_machinery":"The load-bearing object is the state-of-system mapping $I_A(S,U)$ together with the fixed subset $S' \\subseteq S$ that the definition lets the algorithm choose; the paper sets $S' = C(S)$, where $C(S)$ is the core set of points a selective sampler queried. Core-set algorithms satisfy $A(S) = A(C(S))$, so the system only ever stores $C(S)$. The property that carries the argument is monotonicity: the BBQSAMPLER's query condition is label-independent, so deleting points strengthens the query statistic, giving $C(C(S)\\setminus U)=C(S)\\setminus U$ for every deletion set. This means no re-sampling is needed at unlearning time; the update is just an ERM re-solve on $C(S)\\setminus U$, and in the general case the same role is played by a generalized sampler whose query complexity is controlled by an eluder-dimension-like quantity of the function class.","core_discovery":"The central discovery is that exact unlearning becomes easy once the guarantee is tied to what the system stores rather than to the whole dataset. The paper's Algorithm 1 learns a linear classifier with a selective sampler and takes $S' = C(S)$, the set of queried points. Because the sampler's query condition $x^\\top A^{-1} x > T^{-\\kappa}$ depends only on inputs, not labels, deleting a point can only raise the query statistic for every remaining point; hence running the sampler on $C(S) \\setminus U$ re-queries exactly $C(S) \\setminus U$. The unlearned state $I_A(S,U) = (A(S,U), C(S)\\setminus U)$ is then identical to the state produced by direct learning on $C(S)\\setminus U$, so Algorithm 1 is exact system-aware unlearning, with $\\varepsilon=\\delta=0$, and the same monotonicity gives an extension to general function classes through a generalized sampler.","pith_inferences":["Accepting system-aware unlearning changes what \"deleted\" means legally and practically: the guarantee is indistinguishability from a system that only ever stored the core set, not from one trained on all $S\\setminus U$, so an auditor who can reconstruct $S\\setminus U$ would not be satisfied.","The monotonic query-condition trick suggests a general design recipe for unlearning-friendly learners: make each algorithm's data usage monotone under deletion so unlearning is an exact reversal of learning; other online or streaming algorithms with label-independent updates may inherit the same property.","A complementary route the paper leaves open is approximate system-aware unlearning: perturbing the core-set ERM with differential privacy (as in the paper's interpolation example) could cut memory or computation further, or handle non-monotonic samplers, at the cost of $(\\varepsilon,\\delta)$-indistinguishability.","The strongest practical test would be on linear probing layers of large pretrained models, where the core set is the small set of influential probe examples; measuring deletion time, memory, and membership-inference resistance there would show whether sublinear-memory exact unlearning survives real representation spaces."],"forward_implications":["Exact unlearning for linear classification is achieved with $O(dT^\\kappa \\log T)$ memory, sublinear in the sample size, a regime the paper states is impossible under the traditional unlearning definition.","Deletion requests outside the core set are processed for free, so the practical deletion capacity is governed by how often deleted points fall in $C(S)$; under a uniform deletion distribution the system can tolerate $\\Theta(K T / (d T^\\kappa \\log T))$ total deletions with high probability.","The expected deletion time under uniform deletions is at most $O(d^3 T^\\kappa \\log T / T)$, which for large $T$ beats the per-deletion cost of exact retraining-based unlearning.","The approach extends to general function classes: exact system-aware unlearning holds for any class where a monotonic selective sampler exists, with memory bounded by the class's eluder-dimension-like quantity, and with uniform stability of the regression oracle controlling the deletion capacity."],"supporting_citations":[{"why":"It supplies BBQSAMPLER, the selective sampling procedure whose label-independent query rule gives unlearning its monotonicity.","marker":"(Cesa-Bianchi et al., 2009)"},{"why":"It proves that exact unlearning for linear classification under the traditional definition must store the entire dataset, the lower bound that the sublinear-memory algorithm bypasses.","marker":"(Cherapanamjeri et al., 2025)"},{"why":"It formulates the traditional $(\\varepsilon,\\delta)$-unlearning definition and deletion capacity that system-aware unlearning generalizes and is compared against.","marker":"(Sekhari et al., 2021)"},{"why":"It provides the regret and query-complexity analysis used to bound the core-set size and the excess risk of the final predictor.","marker":"(Dekel et al., 2012)"},{"why":"It supplies the generalized monotonic sampler and the eluder-dimension-like complexity measure used in the general-function-class extension.","marker":"(Gentile et al., 2022)"},{"why":"It supplies the sample-compression generalization bounds that convert post-unlearning empirical error into excess-risk guarantees.","marker":"(Kakade & Tewari, 2008)"},{"why":"It defines uniform stability, the condition on the regression oracle that controls how many core-set deletions the general algorithm can tolerate.","marker":"(Bousquet & Elisseeff, 2002)"}],"fun_headline_variants":["Store less, forget faster: exact unlearning without full dataset","System-aware unlearning: sublinear memory, exact deletion","Exact unlearning by storing less: a system-aware approach","Forget faster with less stored data: exact system-aware unlearning","A realistic attacker enables exact unlearning with less memory"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole guarantee rests on the threat model in Definition 2.3: an attacker can see only the system's stored state after unlearning and cannot reconstruct the full remaining dataset $S \\setminus U$; if a realistic attacker can get $S\\setminus U$, the exactness of Algorithm 1 does not imply privacy against a retraining comparison.","fun_headline_variants_meta":{"raw":{"variants":["Store less, forget faster: exact unlearning without full dataset","System-aware unlearning: sublinear memory, exact deletion","Exact unlearning by storing less: a system-aware approach","Forget faster with less stored data: exact system-aware unlearning","A realistic attacker enables exact unlearning with less memory"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000457,"raw_usage":{"total_tokens":2317,"prompt_tokens":991,"completion_tokens":1326,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":607,"completion_tokens_details":{"reasoning_tokens":1242}},"tokens_in":607,"tokens_out":1326,"duration_ms":11983,"temperature":1.0,"reasoning_tokens":1242,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T06:01:27.507317+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"To test the core claim, search for the smallest dataset $S$ and deletion set $U$ for which running the selective sampler on $C(S)\\setminus U$ fails to query all of $C(S)\\setminus U$. Theorem 4.2 asserts this never happens; a counterexample would break the equality $C(C(S)\\setminus U)=C(S)\\setminus U$ and with it the exactness guarantee, since the unlearned state would no longer coincide with a fresh run on the core set.","supporting_citations":[{"cited_title":"Robust bounds for classification via selective sampling","cited_arxiv_id":null,"evidence_quote":"It supplies BBQSAMPLER, the selective sampling procedure whose label-independent query rule gives unlearning its monotonicity."},{"cited_title":"The space complexity of learning-unlearning algorithms, 2025","cited_arxiv_id":null,"evidence_quote":"It proves that exact unlearning for linear classification under the traditional definition must store the entire dataset, the lower bound that the sublinear-memory algorithm bypasses."},{"cited_title":"Selective sampling and active learning from single and multiple teachers","cited_arxiv_id":null,"evidence_quote":"It provides the regret and query-complexity analysis used to bound the core-set size and the excess risk of the final predictor."},{"cited_title":"Fast Rates in Pool-Based Batch Active Learning","cited_arxiv_id":"2202.05448","evidence_quote":"It supplies the generalized monotonic sampler and the eluder-dimension-like complexity measure used in the general-function-class extension."},{"cited_title":"and Tewari, A","cited_arxiv_id":null,"evidence_quote":"It supplies the sample-compression generalization bounds that convert post-unlearning empirical error into excess-risk guarantees."},{"cited_title":"and Elisseeff, A","cited_arxiv_id":null,"evidence_quote":"It defines uniform stability, the condition on the regression oracle that controls how many core-set deletions the general algorithm can tolerate."}],"review_version":1}