{"id":"eea69455-6d1c-497f-8c33-55b99326c151","arxiv_id":"2505.08138","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"A formal indistinguishability definition of machine unlearning is introduced, current methods are shown to fail it empirically, and impossibility and utility-collapse results are claimed.","lead":"This paper proposes a new test for machine unlearning: after a model deletes some training data, an adversary should not be able to tell its behavior apart from a model that never saw that data. The authors show that several popular unlearning methods fail this test, and that achieving it with deterministic methods or differential privacy is provably hard without losing usefulness.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The theoretical results in §5.1 rest on a min-entropy assumption that Definition 14 does not make; Theorem 19 is false as stated, so the paper's theoretical conclusions are not established.","rationale":"The paper's empirical contribution is plausible and the definitional framework is worth considering, but the theoretical section is what supports the stronger \"fundamentally falls short\" conclusion. The reader's weakest-assumption correctly identifies the min-entropy/Shannon-entropy gap in Theorem 18. The same proof style invalidates Theorem 19, which is in fact false because a deterministic learner with a randomized unlearn that is perfect except with negligible probability satisfies the game but not Definition 16. This does not overturn the empirical findings or the value of the framework, but it means the headline theoretical claims need either correction or additional assumptions. A repaired proof might add a min-entropy condition to Definition 14 or derive a p_max bound from p.p.t.-samplability, and Theorem 19's conclusion would need to be weakened. Since these are fixable but not present in the manuscript, the CONDITIONAL verdict remains appropriate.","tokens_in":15977,"tokens_out":20436,"duration_ms":217867,"concrete_test":"Analytically verify the counterexample to Theorem 19: take learn to be exact k-NN, which is deterministic, and define unlearn(M_o, D_f) to return the k-NN model storing D \\ D_f with probability 1 − 2^{-λ} and a fixed model not equal to the control with probability 2^{-λ}. Compute the adversary's success probability in Definition 7 exactly. If it is at most 1/2 + 2^{-λ}, then Theorem 19 as stated is refuted, because this scheme is not perfect under Definition 16 yet satisfies white-box computational unlearning.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing weakness is in §5.1. Definition 14 defines an entropic learning scheme by Shannon entropy at least 1 bit, but the proof of Theorem 18 switches to \"minimum entropy greater than 1 bit\" and uses the conclusion p_max < 1/2. Shannon entropy ≥ 1 does not imply any such min-entropy bound: for example, a distribution over 2^{poly(λ)} outcomes with p(h0) = 1 − 1/λ and a long tail can have entropy ≥ 1 while p_max is close to 1, not 1/2. The proof's contradiction (\"p_max does not asymptotically approach 1/2\") is therefore not derived from the stated definition. More seriously, Theorem 19 is false as stated. A deterministic learner (e.g., the paper's own exact k-NN learning scheme) paired with a randomized unlearn that outputs the control model with probability 1 − 2^{-λ} and a distinct model otherwise satisfies Definitions 7 and 8 with negligible adversary advantage, but it is not a perfect unlearning algorithm under Definition 16. The paper's conclusion that non-perfect computational unlearning requires both randomized learning and randomized unlearning is hence unsupported, and the impossibility narrative loses its theoretical anchor.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a new formal notion of machine unlearning called computational unlearning, defined through a cryptographic indistinguishability game in which an adversary must tell apart a model produced by an unlearning method from a control model produced by retraining without the forget set. The game is given in white-box and black-box variants (Definitions 7 and 8). The authors construct two distinguishing scores, MIAScore and KLDScore, and report experiments on ResNet-18/CIFAR-10 with four unlearning methods, finding that an adversary distinguishes the unlearned model from the control with success rates above 60% at all tested forget-set sizes. The theoretical section claims (i) that no deterministic unlearning method can achieve computational unlearning for entropic learning schemes (Theorem 18), (ii) that any deterministic learning scheme satisfying computational unlearning must perfectly unlearn (Theorem 19), and (iii) that differentially private constructions collapse utility (Theorem 26 and Corollary 27).","tokens_in":16095,"tokens_out":6840,"duration_ms":74055,"significance":"The paper makes a useful conceptual contribution by moving the unlearning evaluation goal from score-based measures to a formal indistinguishability game, and the empirical study is a clear negative result for several representative heuristic and approximate unlearning methods. The use of KLDScore as a distinguisher is a nice complement to membership-inference-based scores. If the theoretical results were made correct, the framework would be a valuable step toward rigorous unlearning definitions. However, the current proofs of the central theorems contain load-bearing gaps and one false statement, so the theoretical conclusions are not established as written.","major_comments":[{"comment":"Definition 14 defines an entropic learning scheme by Shannon entropy at least 1 bit, but the proof of Theorem 18 switches to \"minimum entropy greater than 1 bit\" and then uses p_max < 1/2. Shannon entropy at least 1 bit does not imply any such min-entropy bound: for example, a distribution with p(h0) = 1 - 1/λ and the remaining mass spread over 2^λ outcomes has Shannon entropy exceeding 1 bit while p_max tends to 1, not 1/2. Therefore the contradiction in the proof does not follow from the stated definition. The theorem may be repairable by changing the definition to a min-entropy condition, but as written the impossibility result for deterministic unlearning is not proven.","section":"Definition 14 and Theorem 18"},{"comment":"Theorem 19 is false as stated. Let the learning scheme be deterministic and let unlearn be randomized, outputting the control model M_c with probability 1 - 2^{-λ} and some other model with probability 2^{-λ}. The adversary can compute M_c itself and compare the two challenge models to it; its advantage is 2^{-λ-1}, which is negligible, so Definitions 7 and 8 are satisfied. Yet unlearn is not perfect under Definition 16, since it does not always output the retrained model. This counterexample refutes the theorem and also invalidates Remark 20's dichotomy that a computational unlearning scheme must either be perfect or have both randomized learning and randomized unlearning.","section":"Theorem 19"},{"comment":"The proof of Theorem 26 is not a rigorous proof of an 'if and only if' statement. The two directions are asserted with informal statements about an adversary 'obtaining a query result with non-negligible privacy loss' after a polynomial number of queries, without bounding the adversary's advantage or relating the privacy-loss events to the distinguishing game. Additionally, the construction in which unlearn simply outputs the original model is not a forgetting operation in any intuitive sense, and the claim that it satisfies black-box computational unlearning needs a formal argument that the adversary's access to M_o in Definition 8 does not already trivially break indistinguishability. Furthermore, Corollary 27 uses the case D_f = D, while Definitions 7 and 8 require the adversary to select a proper subset D_f ⊂ D; if equality is excluded, the utility-collapse argument does not go through.","section":"Theorem 26 and Corollary 27"},{"comment":"Lemma 25 and its proof are too loose to support Theorem 26. The proof shows D_KL(P||Q) ≤ max_x L(x), but differential privacy only bounds the privacy loss with probability at least 1 - δ, not for every element, and the role of δ is absent from the derivation. A correct argument must account for the δ failure probability and then relate the resulting statistical divergence to the distinguishing advantage in the black-box game. As written, the lemma does not establish the 'negligible relative entropy' claim used in Theorem 26.","section":"Lemma 25"}],"minor_comments":[{"comment":"The winning condition is written P(b'=b) < 1/2 + negl(λ); since the adversary can always succeed with probability at least 1/2, the inequality should be ≤ 1/2 + negl(λ) unless strictness is intentional and explained.","section":"Definitions 7 and 8"},{"comment":"The displayed cost condition says cost(learn(D\\D_f)) < cost(unlearn(M_o,D_f)), which is the opposite of the intended requirement that unlearning be cheaper than retraining. This should be cost(unlearn(M_o,D_f)) < cost(learn(D\\D_f)) (or with ≤), otherwise the remark does not prevent the trivial init-based solution it is meant to exclude.","section":"Remark 10"},{"comment":"There is a typo in the text 'known as the as the forget set' that should be corrected to 'known as the forget set.'","section":"Section 2"},{"comment":"References [21] and [22] are the same He et al. paper and should be merged or differentiated.","section":"References"},{"comment":"The notation D_f ⊂ D in Definitions 7 and 8 should be clarified as proper or non-strict subset; the proof of Corollary 27 uses D_f = D, which is only valid if non-strict subset is allowed.","section":"Notation D_f ⊂ D"},{"comment":"The phrase 'Beta distribution with the Jeffries prior' should be 'Jeffreys prior,' and it would help to state the actual interval construction used for the 95% confidence intervals.","section":"Section 4.2"}],"recommendation":"major_revision","confidential_remarks":"The empirical contribution and the proposed security-game framework are solid, but the theoretical section as currently written cannot support the paper's headline claims. Theorem 19 is false, Theorem 18 relies on an unstated min-entropy assumption, and the DP utility-collapse results need a rigorous proof. These issues are substantive but appear fixable with a careful reworking of Section 5, so I recommend major revision rather than rejection. The authors should also re-examine whether the definition of entropic learning should be based on min-entropy and whether the cost condition in Remark 10 is correct."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague —\n\nThe paper has one genuinely useful idea and one serious flaw. The genuinely useful idea is the security-game formulation of machine unlearning: an unlearning method is judged by whether a p.p.t. adversary can tell its output apart from a retrained control model. The empirical section is clean and convincing: on CIFAR-10/ResNet-18, four published methods (bad teacher, amnesiac, SSD, certified deep unlearning) are distinguishable with high success rates using either MIA scores or a KL-divergence score. The authors ran 128 trials per setting, report confidence intervals, and vary forget-set size and the CDU sigma; the results are plausible and reproducible in principle even without released code.\n\nThe flaw is in Section 5.1. Theorem 18's proof switches from Shannon entropy to \"minimum entropy greater than 1 bit,\" but Definition 14 only requires Shannon entropy >= 1. Those are not equivalent: a distribution over a large set with one outcome of probability 1 - 1/λ and a long tail can have Shannon entropy > 1 while p_max is arbitrarily close to 1. So the contradiction the proof derives does not follow from the stated definition. Theorem 19 is false as stated: a deterministic learning scheme paired with a randomized unlearn that outputs the control model with probability 1 - negl(λ) satisfies computational unlearning (Definitions 7/8) but is not perfect under Definition 16, which requires exact equality always. The paper's conclusion that deterministic learning schemes must be perfect is therefore unsupported; at most they need to match the control with overwhelming probability. The DP utility-collapse results (Theorem 26/Corollary 27) are also sketched and depend on an odd corner case where D_f = D, which should be either justified or removed.\n\nThe stress-test note is correct: the theoretical anchor of the paper's narrative is not established. That does not sink the empirical contribution or the definition itself, but it means the paper needs major revision before it can be accepted. The authors should fix the entropy definition/proof mismatch, restate Theorem 19 with the right conclusion, and either supply code or precise decision rules for the distinguishers. I would send this to peer review, because the framework is likely to be influential and the empirical finding deserves a public venue. It is a conditional accept, not a reject.","headline":"The security-game definition and the empirical demonstration are worth taking seriously, but the impossibility theorems as stated do not survive contact with the proof details.","tokens_in":16736,"tokens_out":3571,"would_cite":true,"duration_ms":35342,"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":"Machine unlearning methods fail to erase an adversary's ability to tell them apart from a retrained control model.","keywords":["machine unlearning","computational unlearning","indistinguishability","membership inference","differential privacy","certified removal","utility collapse","security game"],"falsifier":"Exhibit a learning scheme whose output distribution has Shannon entropy at least 1 bit but places probability $1-2^{-\\lambda}$ on one particular model, pair it with a deterministic unlearner that outputs that likely model, and show an adversary cannot distinguish the result from the control model with non-negligible advantage; that would refute Theorem 18 as stated.","tokens_in":15665,"feed_emoji":"🕵️","tokens_out":4544,"duration_ms":42581,"temperature":0.7,"pith_summary":"The paper proposes a new standard for machine unlearning, called computational unlearning: an unlearning method succeeds only if no efficient adversary can distinguish its output from a control model retrained without the data to be forgotten. It reports experiments on ResNet-18 models trained on CIFAR-10 showing that four published unlearning methods fail this test under both a membership-inference-based score and a KL-divergence-based score. The paper also proves theoretical consequences: deterministic unlearning cannot achieve computational unlearning for entropic learning schemes, deterministic schemes that do achieve it must unlearn perfectly, and differential-privacy-based unlearning works only with negligible privacy parameters, which collapses utility to that of a randomly initialized model.","feed_headline":"Machine unlearning fails its mirror test","feed_subtitle":"A new security game shows published unlearning methods remain distinguishable from retrained control models.","key_machinery":"The machinery is the security game itself, borrowed from cryptographic indistinguishability: two candidate models, one random bit, and an adversary who guesses the bit. The load-bearing objects are two distinguishers: MIAScore, which applies membership inference scores, and KLDScore, which measures KL divergence between the original model's outputs and the candidate model's outputs on perturbed forget-set inputs. The impossibility argument rests on the adversary being able to run the deterministic unlearning algorithm on the original model, while the entropic learning scheme rarely reproduces the same model twice.","core_discovery":"The central claim is that unlearning should be defined as computational indistinguishability in a two-party game: a challenger hands the adversary an unlearned model and a mirror model (retrained on the retained data) in random order, and the adversary guesses which is which. A method achieves computational unlearning only if no probabilistic polynomial-time adversary can guess correctly except with negligible advantage. Empirically, all tested representative methods — bad teacher, amnesiac, selective synaptic dampening, and certified deep unlearning — are distinguishable in both white-box and black-box settings. Theoretically, the framework implies that entropic learning schemes require randomized unlearning, that deterministic schemes satisfying the definition must perform perfect unlearning, and that building unlearning from differential privacy forces utility down to that of a randomly initialized model.","pith_inferences":["Beyond the paper: the same game could be adapted to generative models by treating inference as sampling and measuring distinguishability on output distributions, though per-token scores would likely behave differently from the classification scores used here.","Beyond the paper: an adaptive adversary who queries the oracle repeatedly before choosing the forget set could shift the measured distinguishability; the current experiments use a fixed random forget set, so adaptive attacks are an untested extension.","Beyond the paper: the reported KLDScore intersection between σ = 0.001 and σ = 0.01 for certified deep unlearning suggests a parameter regime where the unlearned model may become harder to distinguish, and the paper leaves this regime open for future work.","Beyond the paper: the framework's strength depends heavily on the adversary knowing the original model; if that knowledge is withheld, certified removal with a sufficiently tight bound may remain a viable weaker standard, as the paper itself notes."],"forward_implications":["Deterministic heuristic unlearning methods such as selective synaptic dampening and amnesiac unlearning can never satisfy the computational unlearning definition for entropic learning schemes.","Any deterministic learning scheme that satisfies the definition must implement perfect unlearning, meaning it outputs exactly the retrained model.","Differentially private unlearning constructions satisfy black-box computational unlearning only when the privacy parameters are negligible, at which point the unlearned model's utility equals that of a randomly initialized model.","Because black-box infeasibility implies white-box infeasibility, differential-privacy-based constructions cannot support the stronger white-box notion either.","The k-nearest neighbors algorithm admits a white-box computational unlearning algorithm simply by deleting the forgotten points, because the unlearned model is then identical to the control model."],"supporting_citations":[{"why":"Provides bad teacher unlearning, one of the tested heuristic methods that the paper's distinguishers successfully separate from the control.","marker":"[10]"},{"why":"Provides selective synaptic dampening (SSD), a deterministic heuristic unlearning method shown to be distinguishable.","marker":"[15]"},{"why":"Provides amnesiac unlearning, a deterministic heuristic method shown to be distinguishable.","marker":"[18]"},{"why":"Provides certified deep unlearning, the approximate method whose σ parameter is varied in the KLDScore experiments.","marker":"[49]"},{"why":"Supplies the membership inference attack approach used to build the MIAScore distinguisher.","marker":"[38]"},{"why":"Supplies the differential privacy definitions and properties used in the utility-collapse theorem.","marker":"[13]"},{"why":"Supplies the certified removal framework whose bounds the paper contrasts with computational unlearning.","marker":"[19]"},{"why":"Provides the CIFAR-10 benchmark used in every distinguishing experiment.","marker":"[27]"}],"fun_headline_variants":["Mirror test exposes unlearning failures","Unlearning methods fail new mirror game","Computational unlearning: a tough bar","Adversary can spot unlearned models","True unlearning demands indistinguishability"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The impossibility proof for deterministic unlearning assumes the learning algorithm never outputs any single model with probability above 1/2, while the paper's written definition only requires Shannon entropy of at least 1 bit; these two conditions are not the same.","fun_headline_variants_meta":{"raw":{"variants":["Mirror test exposes unlearning failures","Unlearning methods fail new mirror game","Computational unlearning: a tough bar","Adversary can spot unlearned models","True unlearning demands indistinguishability"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000708,"raw_usage":{"total_tokens":3198,"prompt_tokens":964,"completion_tokens":2234,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":580,"completion_tokens_details":{"reasoning_tokens":2170}},"tokens_in":580,"tokens_out":2234,"duration_ms":18849,"temperature":1.0,"reasoning_tokens":2170,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T22:04:11.813054+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Exhibit a learning scheme whose output distribution has Shannon entropy at least 1 bit but places probability $1-2^{-\\lambda}$ on one particular model, pair it with a deterministic unlearner that outputs that likely model, and show an adversary cannot distinguish the result from the control model with non-negligible advantage; that would refute Theorem 18 as stated.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the membership inference attack approach used to build the MIAScore distinguisher."},{"cited_title":"Learning Multiple Layers of Features from Tiny Images","cited_arxiv_id":null,"evidence_quote":"Provides the CIFAR-10 benchmark used in every distinguishing experiment."}],"review_version":1}