acceptodds
Under review as a conference paper at ICLR 2027

Auditing of Unlearning Algorithms

Abstract

Evaluating whether an unlearning algorithm has truly removed the influence of its forget set remains an open challenge. We introduce a hypothesis-testing auditor that uses membership-inference attacks to compute high-confidence empirical lower bounds on the zero-concentrated differential privacy (zCDP) parameter of certified unlearning, with a direct audit of the Gaussian differential privacy parameter as well; rejecting a candidate establishes that a claimed certificate cannot hold. Our bounds are computed under a black-box threat model in which the adversary additionally observes the initialization and the per-epoch shuffling order. On CIFAR-100, certified methods such as model clipping and rewind-to-delete yield small lower bounds consistent with their stated guarantees, whereas uncertified methods—including Hessian-based unlearning, interleaved descent–ascent, ascent on the forget set, fine-tuning on the retain set, and class-based forgetting methods such as BadTeacher and DELETE—often yield large lower bounds, revealing substantial residual influence of the forget set. Hessian-based unlearning is certified only for convex losses, and that certification does not transfer to the nonconvex networks we study. We further audit uncertified methods on Shakespeare and scale our evaluation to Llama-3.2-1B on TOFU, a dataset of fictitious authors. Overall, our auditor provides a practical tool for refuting unlearning claims. across model architectures, datasets, and scales.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
Machine unlearning, privacy auditing, membership inference, differential privacy.

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_waN6OpenReview ↗
Rating
2(+1)
Confidence
4
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

This paper proposes a hypothesis-testing framework for auditing machine unlearning algorithms. The method derives empirical lower confidence bounds on the zCDP parameter of certified unlearning, with extensions to Gaussian DP and pure DP. The proposed auditor uses randomized inclusion of candidate forget batches and membership-inference-based predictions to construct overlap statistics. The authors evaluate the framework on CIFAR-100, Shakespeare, TOFU, and small convex optimization problems.

Critical strengths
  1. The paper formulates a concrete hypothesis-testing objective with controlled Type I error. It correctly emphasizes that a non-rejection is not evidence of successful unlearning.

  2. The connection between subset-level certified unlearning and Rényi-DP-based auditing is potentially useful.

Critical weaknesses
  1. Poor presentation and organization. The abstract contains poorly formatted citations and unnecessary implementation-level details. The main text is fragmented: Sections 6–8 mix experimental setup, algorithm descriptions, repeated discussions of results, and a separate convex evaluation. Section 7.3 largely revisits findings from earlier subsections. The overall experimental narrative is difficult to follow.

  2. Insufficient and poorly controlled experiments. The main-text experimental analysis is limited, and essential configurations are scattered across multiple appendices. More importantly, certified and uncertified methods use substantially different auditing configurations ((m=6) versus (m=4500)), making their reported lower bounds difficult to compare. The R2D experiment also uses a base model with only approximately 4% CIFAR-100 accuracy.

  3. The central empirical claim is not convincingly supported. For certified methods, the auditor produces zero or very small lower bounds and does not falsify any valid certificate. Appendix F.1 shows that the auditing configuration itself imposes a severe upper limit on attainable bounds: even perfect predictions cannot produce a meaningful test of large claimed privacy parameters.

  4. Limited theoretical novelty. The main theoretical arguments substantially build on established Rényi-DP inequalities and multi-canary auditing methods. The manuscript does not sufficiently demonstrate what fundamentally new capability is enabled by these adaptations.

Questions for authors
  1. Why are substantially different auditor configurations used for certified and uncertified methods, and how can the resulting bounds be compared fairly?

  2. Can the authors report statistical power and rejection rates for deliberately invalid certificates under a fixed computational budget?

  3. How much of the looseness comes from the common-reference reduction, the hypothesis-testing bound, and the membership predictor, respectively?

5 comments
AuthorsOpenReview ↗

Response to reviewer waN6

We thank the reviewer for their detailed review and provide responses to their questions and weaknesses below.

Critical weakness

We thank the reviewer for pointing out ways to improve the clarity of our manuscript.

1. Presentation and organization

Abstract. We would respectfully note that the abstract contains no implementation details. Apart from the auditing approach and threat model, it only names the unlearning algorithms we audit, together with their citations. One citation (SCRUB) was formatted incorrectly, and we have fixed it. We agree that the abstract could be shorter if it named the classes of methods audited (certified, Hessian-based, gradient-based and distillation-based) rather than each method.

Sections 6–8. We agree that the experimental sections mixed setup, method descriptions and results, and that Section 7.3 restated earlier findings. We have reorganized them so that every description comes before any result and each number is stated only once:

  • Section 6 (Setup) (descriptions only): datasets, algorithms, and a single auditor-configuration paragraph (Section 6.3) giving LL, mm, rr and ζ\zeta for every setting.
  • Section 7 (Results) opens with Table 1, then goes by method group (Sections 7.1–7.3), stating each number once.
  • Section 7.4 replaces the old Section 7.3 and keeps only cross-cutting claims, which refer back to Sections 7.1–7.3 without restating numbers.
  • Section 8 (Convex losses) stays separate because it asks a different question: whether the small certified bounds in Section 7.1 come from auditor slack. Its stronger definition (Sekhari et al., 2021) removes the transitivity step of Lemma 4.1.

2. Experimental control

Base models for the certified methods. We agree that model clipping and R2D reach low accuracy on CIFAR-100. Model clipping was evaluated by Koloskova et al. (2025) on CIFAR-10, and we extended it to CIFAR-100 to keep every audit on the same dataset. The paper omitted the retain/forget/test (R/F/T) accuracies of model clipping on CIFAR-100; Table R2 below gives them, and we have added them to Appendix J.1. They are reasonable under adversarial splitting but close to chance under uniform splitting.

Table R2. Final R/F/T accuracy (%) of model clipping on CIFAR-100. Certified: the last row of the table in Appendix J.1.2 (C2=0.225C_2=0.225, σ=10−3\sigma=10^{-3}, ε=105\varepsilon=10^5). Uncertified: the configuration of Appendix J.1.3 (C2=5C_2=5, σ=10−4\sigma=10^{-4}).

CertifiedUncertifiedCertifiedUncertified
UniformAdversarial
Retain1.051.0523.8 ± 1.916.9 ± 2.7
Forget0.770.760.250.05
Test1.011.0020.9 ± 1.615.1 ± 2.3

We therefore now also audit model clipping on CIFAR-10. The setup mirrors the certified CIFAR-100 audits (Section 6.3 and Appendix J.1): a small CNN trained for 400 epochs (72.0% test accuracy), a forget pool of 4,500 points split into m=6m=6 batches of 750, and L=500L=500 runs. We audit two configurations, both under uniform splitting:

  • Certified (C2=0.225C_2=0.225, σ=10−3\sigma=10^{-3}, as in Appendix J.1.2): the stopping rule of Theorem 4.2 ends the noisy phase at step 2,081, and the final retain/forget/test accuracy is 53.2/53.3/52.6%.
  • Uncertified, for auditing only (C2=5C_2=5, σ=10−4\sigma=10^{-4}, as in Appendix J.1.3): C2/σC_2/\sigma is too large for Theorem 4.2, so we stop the noisy phase after 10 epochs. The final accuracy is 59.6/59.5/58.6%.

We audit the model after each noisy step tt. In the uncertified configuration, the bound is 0.680.68 at step 1, the maximum attainable with m=6m=6 and L=500L=500, and stays there for the first 10 steps. It then decays slowly: 0.600.60 at step 20, 0.230.23 at step 40, 0.090.09 at step 100 and 0.0030.003 at step 300. In the certified configuration, the bound is 0.0060.006 after one step and 00 from step 2 on, long before the certified stopping step. R2D was evaluated by its authors on eICU and Lacuna-100 rather than CIFAR-10 (Mu and Klabjan, 2025), so we did not rerun it there.

AuthorsOpenReview ↗

Response to reviewer waN6 (continued)

3. Certified methods and the attainable bound

Why no valid certificate is refuted. A valid certificate is a theorem, so a sound auditor cannot refute it: if our bound exceeded a correctly proved parameter, either the auditor or the proof would be wrong. The auditor should instead be judged by two things. Does it refute certificates used outside their assumptions? And does it respond when the certificate is removed? It does both.

  • Certificates used outside their assumptions. The certificate of Hessian-based unlearning (Zhang et al., 2024) relies on smoothness constants and conditions that are not verified for the neural networks it is proposed for. On CIFAR-100 under uniform splitting our bound is 66.966.9, and on Shakespeare it is 8.768.76, the largest there (Table 1). These are among the largest bounds in the paper.
  • Certificates removed. If model clipping is run with C2/σC_2/\sigma beyond what Theorem 4.2 of Koloskova et al. (2025) admits, the same auditor reaches the maximum attainable bound and then decays as noisy steps proceed (Section 7.1, and on CIFAR-10 in point 2 above). With the certified parameters the bound is 00.

The configuration limits the bound (Appendix F.1). We agree that the configuration caps the attainable bound, and that our certified audits (m=6m=6, L=500L=500) cannot refute a claimed ρ\rho above about 0.680.68. We will state this in Section 7.1. Three points put this in context.

  • The cap is not what binds for the certified methods. Model clipping gives 00 and R2D about 0.20.2, both below the cap of 0.680.68 that the same configuration reaches for uncertified model clipping. A larger cap would not change these numbers.
  • The cap is set by the configuration and grows linearly in mm. It is 0.350.35 at m=6m=6 and L=10L=10 but 763763 at m=4500m=4500, the setting we use for uncertified methods. We use m=6m=6 for certified methods because their per-batch signal is weak, and with many candidates the auditor cannot beat chance (Appendix F.2).
  • DP audits face the same limit. With NN trainings per hypothesis, even a perfect attack certifies an ε\varepsilon that grows only logarithmically in NN: at most 4.544.54 with 500 trials at 99% confidence (Jagielski et al., 2020) and 5.605.60 with 1,000 trials (Nasr et al., 2021). Nasr et al. (2023) report bounds close to this maximum. One-run audits are likewise capped by the number of guesses (Steinke et al., 2023; Mahloujifar et al., 2025), and Steinke et al. (2023, Figure 2) plot their bound up to perfect guessing.

What a small bound means. A bound below the claimed parameter does not show that a method unlearns. To check how close our bound gets when the truth is known, Section 8 audits convex mechanisms with exact parameters. For output perturbation at claimed ρ=1.05\rho=1.05, the bound is 0.470.47. The new Appendix G shows that, in a Gaussian model, the bound stays within a constant factor of the true parameter as mm grows.

4. Theoretical novelty

We agree that our proofs use established tools: Rényi-DP inequalities and the multi-canary design of one-run DP audits. Our contribution is to bring them to certified unlearning. DP auditing is well studied (Jagielski et al., 2020; Nasr et al., 2021; Nasr et al., 2023; Steinke et al., 2023; Mahloujifar et al., 2025), but existing unlearning audits return per-example completeness scores or verification signals, not a bound on a certificate's parameter (Appendix A). To our knowledge, ours is the first audit to return a high-confidence lower bound on the parameter of an indistinguishability-based unlearning definition, which can be compared directly with a published certificate and can refute it.

The adaptation is not direct, for two reasons.

  • The reference model is unobservable. Certified unlearning compares the unlearned model with a reference algorithm that the auditor cannot run. Lemma 4.1 removes the reference by passing through it via transitivity, so the auditor compares two unlearned models directly.
  • The guarantee is subset-level. The guarantee covers every pair of forget subsets, not neighbouring datasets. Lemma 4.2 turns the overlap of a predicted forget set with the true one into a bound on ρ\rho under this all-pairs constraint.

Applying the one-run ff-DP audit of Mahloujifar et al. (2025) to the train-then-unlearn mechanism also gives a valid bound, but it is typically two to four orders of magnitude smaller than ours (Table R1 in our response to Reviewer t67Y; e.g. 0.0130.013 versus 53.953.9 for Hessian-based unlearning on CIFAR-100). Both audits score all candidates jointly; they differ in the guarantee they test. The ff-DP audit tests the record-level guarantee, which bounds the effect of changing one candidate, whereas ours tests the guarantee for every pair of forget subsets, which constrains how far apart two whole forget sets can be.

AuthorsOpenReview ↗

Response to reviewer waN6

Questions

1. Different auditor configurations for certified and uncertified methods

We agree that the two groups use different configurations, and that the paper should explain this more prominently. Appendix F.4 currently contains the discussion.

Why the configurations differ. Certified methods add Gaussian noise to the model weights. The distributions of the attack score with a batch included and excluded then overlap substantially, so predicting each batch separately is close to chance. The batchwise inclusion/exclusion predictor used for uncertified methods therefore gives near-zero bounds here, even on the uncertified variant of model clipping. After the first unlearning step, it gives 0.0020.002 at B=750B=750 (r=6r=6) and 10−510^{-5} at B=100B=100 (r=40r=40) (Appendix F.4). We therefore use the joint sign-vector predictor for certified methods. It calibrates a separate Gaussian for every candidate sign vector and pools evidence across all forget points before committing to one. Because it needs calibration runs for every sign vector, it is feasible only for a few batches, so we use B=750B=750 (m=6m=6). For uncertified methods the per-batch signal is strong, so the batchwise predictor works at B=1B=1 (m=4500m=4500), where enumerating sign vectors is infeasible.

What the configuration changes. Lemma 4.2 holds for any predictor and any mm, so every reported bound remains a valid high-confidence lower bound on the ρ\rho-zCDP unlearning parameter. We agree, however, that the same algorithm can receive very different bounds under different configurations. On uncertified model clipping, for example, the batchwise predictor gives 0.0020.002 after the first step, whereas the joint sign-vector predictor reaches about 0.680.68. A bound therefore reflects both the algorithm and the auditor configuration, and bounds obtained under different configurations should not be compared directly.

The separation between certified and uncertified methods does not rely on this difference. Under the batchwise predictor used for uncertified methods, model clipping gives near-zero bounds even in its uncertified variant: 0.0020.002 at B=750B=750, 10−510^{-5} at B=100B=100, and lower still at B=1B=1. The same predictor at B=1B=1 gives bounds of up to 89.489.4 on the uncertified methods (Table 1).

Changes. We will highlight this choice and its rationale more clearly in the updated version.

2. Power and rejection rates for invalid certificates under a fixed budget.

Our main uncertified case is Hessian-based unlearning (Zhang et al., 2024), proposed for deep networks. Its certificate depends on smoothness constants that cannot be verified for real networks (the authors set them as hyperparameters), so its certified level cannot be computed; we follow their algorithm and noise level. Model clipping beyond Theorem 4.2 (point 2 above) is a second, deliberately uncertified case. Budgets are fixed: L=10L=10 runs of about one GPU-hour each for deep models, and L=500L=500 for model clipping. A bound ρLB\rho_{\mathrm{LB}} rejects every claim ρ0<ρLB\rho_0<\rho_{\mathrm{LB}} at level 5%. For Hessian-based unlearning, this rejects any claim below 66.966.9 on CIFAR-100 (uniform split) and 8.768.76 on Shakespeare; Table R1 (response to Reviewer t67Y) shows the same with a single run. Estimating rejection rates empirically would cost LL more training runs per repetition, so the new Section 4.3 (proofs in Appendix G) instead computes the power analytically in a Gaussian model with a known true parameter, for any LL and mm and in the limit L→∞L\to\infty (Proposition 4.4).

3. Sources of looseness.

  • Common-reference reduction: we expect essentially no loss. Lemma 4.1 is the group-privacy argument of Bun and Steinke (2016, Proposition 9), which is tight for the Gaussian mechanism; in the Gaussian model of Appendix G the factor 4 is attained exactly (Proposition G.1).
  • Membership predictor: we expect a large share of the gap here. Our auditor observes only model outputs, not the weights or internal representations, which may retain information that outputs miss; extending the attack to them could give larger bounds (Section 9). Even in the Gaussian model, a predictor that keeps one bit per candidate loses a factor 2/π2/\pi (Remark G.6).
  • The certificate itself: We believe that the upper bounds for many certified algorithms that we audit are not tight. Tighter analyses of the certified algorithms would narrow the gap from above (Section 9).

We appreciate your feedback and hope this addresses your concerns. Please let us know if anything needs clarification or if you have further questions.

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

Summary

The paper proposes a randomized algorithm on how to audit machine unlearning algorithms. Having query access to blackbox training (AA) and unlearning (UU) algorithms and a dataset D=R∪FD=R\cup F, it proposes an algorithm MM to audit the pair (A,U)(A,U), by fixing a retain set RR and includes a randomly chosen balanced subset F1F_1 of the forget set FF for training (and sends D1=R∪F1D_1=R\cup F_1 to AA), subsequently requesting their deletion (and sends F1F_1 to UU). Then, a membership inference attack is implemented by maximizing a score on the final unlearned model U(A(D1),F1)U(A(D_1), F_1) to predict F^1⊂F\hat{F}_1 \subset F of which batches were included and later asked to be forgotten. The authors utilize this randomization to analyse the statistic ∣F^1∩F1∣|\hat{F}_1 \cap F_1| (and more precisely its departure from null behavior) and repeat the above process LL times to analyse ∣F^1∩F1∣,⋯ ,∣F^L∩FL∣|\hat{F}_1 \cap F_1|, \cdots, |\hat{F}_L \cap F_L| together to derive finite-sample tail bounds for the average number of correct predictions and invert these bounds to obtain lower confidence bounds on the zCDP unlearning parameter. They also provide pure-DP and direct GDP variants. On the empirical side, the experiments cover CIFAR-100, Shakespeare, and Llama-3.2-1B on TOFU. The guarantee they provide is conditional on public initialization and shuffling order, and one-sided since a large lower bound rejects smaller candidate guarantees, however a small bound does not certify successful unlearning.

Critical strengths

The meta algorithm for auditing and the two instantiations for implementing them

  • Evaluating whether an unlearning algorithm UU (in relation to a training algorithm AA) has truly unlearned the forget set FF remains an interesting challenge. Inspired by the framework of auditing of differential privacy, the paper proposes a meta algorithm (Algorithm 1, Appendix D.1) for an auditor MM who has blackbox query access to AA and UU as well as a dataset D=R∪FD=R\cup F.
  • The meta algorithm randomly selects a subset F1⊂FF_1 \subset F of size approximately half of ∣F∣|F| and sends D1=R∪F1D_1= R\cup F_1 to AA for training as well as F1F_1 to UU afterwards for unlearning. It repeats this process LL times by selecting subsets F1,⋯ ,FLF_1, \cdots, F_L independently.
  • The paper provides two instantiations (Algorithm 2 and 3, Appendix D.2 and D.3) of implementing this meta algorithm to select a subset F^1\hat{F}_1 of FF (and similarly F^2,⋯ ,F^L\hat{F}_2, \cdots, \hat{F}_L) based on maximizing a score (scores are different for algorithms 2 and 3).
  • The hope is that if the unlearning algorithm UU had unlearned F1F_1 (null situation), then F1F_1 and F^1\hat{F}_1 are independent and therefore the size ∣F1∩F^1∣|F_1 \cap \hat{F}_1| would satisfy the statistics of a null distribution determined by the original sampling process of F1⊂FF_1 \subset F and how the maximizer F^1\hat{F}_1 of the score is chosen.
  • However, any departure of ∣F1∩F^1∣|F_1 \cap \hat{F}_1| from its null behavior would point toward failure of unlearning of UU. Since, the conclusions depend on randomization of choosing this subset F1F_1 of FF, the paper repeats this procedure LL times to ensure reasonable finite sample guarantees to our satisfaction.
Critical weaknesses
  1. It is unclear how feasible it is in practice that auditor need to be able train the model AA L times before the auditor makes a decision? This is because in my opinion, frontier model training time is lengthy, and the auditor demanding LL rounds of learning and unlearning algorithms to be implemented for auditing (Algorithm 1, Appendix D.1) seems to require a lot of time. Given my background in theory, I was hoping for a clearer theoretical justification for choosing this particular randomized procedure over other possible auditing procedures.

  2. Its unclear how the guarantees are effected once the structure of the dataset DD varies. Could the authors clarify, for a concrete statistical model of data such as data generated using the generalized linear model and some other model of interests, would the guarantees look like? Although the paper establishes finite-sample validity guarantees, I would also have liked concrete guarantees on the audit’s power under a specified model or data distribution. For example, under what conditions can the proposed attack detect a failure of unlearning, and how does the required number of repetitions depend on the magnitude of that failure? Such results would help explain when the procedure is informative and provide a theoretical basis for comparing alternative auditing algorithms.

Questions for authors
  1. Could the authors clarify aspects of Definition 3.1? First, I summarize how I understand the flowchart of machine unlearning in three steps, and for simplicity drop the subscripts x0,πx_0, \pi for the learning and unlearning algorithms AA and UU, respectively.
  • First, a training algorithm AA receives a data set D=D = {zi:i∈[n]z_i: i\in [n]} and is in search of a trained parameter x=A(D)x=A(D) that will hopefully have (among other things) nice generalization guarantees on a fresh set of data. So, the training algorithm AA starts training with the initial parameter x0x_0 and shuffles the data DD with a permutation π\pi for the purposes of training.

  • Second, when the training is over, AA has the trained parameters at x=A(D)x=A(D), and bunch of data removal requests DrD_r come. So, the task for the unlearning algorithm UU is to begin with the following pieces of information, the trained model weights A(D)A(D), the list of removal requests DrD_r, and potentially given the list of entire training data set (not sure if this is required, but the paper assumes it).

  • Third, the goal is that U(A(D),Dr)U(A(D), D_r) is efficient. Moreover, it should approximately match the generalization error of the retrained-from-scratch model A(D∖Dr)A(D\setminus D_r), and U(A(D),Dr)U(A(D), D_r) should also be approximately equidistributed with A(D∖Dr)A(D\setminus D_r) for privacy reasons.

  • Q1 In Definition 3.1, why is hypothetical reference algorithm Aˉ\bar{A} introduced?

    • My understanding is that, from the perspective of the auditor (or even the honest unlearning algorithm designer), we want the unlearning algorithm UU to match the behaviour of the training algorithm AA, since after all it seems natural that the training algorithm has been chosen wisely so that it has good generalization properties (among other things). Hence, it makes sense to compare U(A(D),Df)U(A(D), D_f) with A(D∖Df)A(D\setminus D_f). The mere existence of a reference algorithm Aˉ(D∖Df)\bar{A}(D\setminus D_f) approximately equidistributed with U(A(D),Df)U(A(D), D_f) does not seem sufficient given the overall three requirements of unlearning (efficient, similar generalization error as that of $ A$, approximately equidistributed with A(D∖Df)A(D\setminus D_f)).
  • Q2 In Definition 3.1, what is the smallest possible ρ\rho for a given unlearning-learning pair U,AU, A?

    • My understanding is that, from the perspective of the auditor, given black-box access to U,AU, A as well as those x0,πx_0, \pi, the smallest possible ρ\rho is given by the following: \hat{\rho}(D, U, A):=\sup_{x_0, \pi} \sup_{D_f \subseteq D\} \sup_{\alpha >1} \frac{\max(D_{\alpha}(U(A(D), D_f)||A(D\setminus D_f)), D_{\alpha}(A(D\setminus D_f)||U(A(D), D_f)))}{\alpha}.
  • Q3 In the above ρ^(D,U,A)\hat{\rho}(D, U, A), do we allow sup over all datasets DD as well? Moreover, it seems too strict to allow all subsets of DD as allowable removal requests, since in my opinion that would be too stringent a condition for practical purposes, as it's unclear how long the running time of an unlearning algorithm UU will be if we remove a significant proportion (constant fraction) of the dataset DD. In that case, we might even consider retraining from scratch.

3 comments
AuthorsOpenReview ↗

Response to reviewer 1mtV

We would like to thank the reviewer for the detailed and careful review. We now respond to their questions in the paper below.

1. Number of runs

We agree that repeated training may be infeasible for frontier models. With L=1L=1 our audit still gives large bounds, and more runs make them sharper. On CIFAR-100, for example, a single run gives 68.168.1 for DELETE and 53.953.9 for Hessian-based unlearning, compared with 89.489.4 and 66.966.9 at L=10L=10 (Table R1, response to Reviewer t67Y). We will add the L=1L=1 results to the final version.

Even with L>1L>1, the cost is in line with current practice. Repeated runs are standard in unlearning evaluation: the NeurIPS 2023 unlearning competition scores each method on 512 unlearned and 512 retrained models (Triantafillou et al., 2024, Appendix A.3), whereas we use L=10L=10. Most of the power comes from the number of candidates mm, not from LL: with perfect prediction the bound is at most ρLBmax⁡=14(log⁡∣Sm∣−log⁡(1/ζ)/L)2,log⁡∣Sm∣≈mlog⁡2,\rho_{\mathrm{LB}}^{\max}=\tfrac14\Bigl(\sqrt{\log|\mathcal S_m|}-\sqrt{\log(1/\zeta)/L}\Bigr)^2,\qquad \log|\mathcal S_m|\approx m\log 2, which at m=4500m=4500 is 731731 for L=1L=1 and 763763 for L=10L=10 (Appendix F). More runs matter mainly when mm must be small, as for the certified methods (m=6m=6).

Why this procedure. The auditor draws the forget set at random and tries to predict it from the unlearned model; predicting better than chance means the model still carries information about the forget set. One-run DP audits use the same design (Steinke et al., 2023; Mahloujifar et al., 2025). Because the auditor chooses the forget set itself, the null distribution of its score is known exactly, so the bound is valid for any algorithm and any predictor (Lemma 4.2). Many candidates make the bound large. With two candidates it never exceeds 14log⁡2\tfrac14\log 2, and a pairwise test gives zero with L=5L=5 runs per hypothesis even under perfect separation (Appendix D.4). With many candidates it stays within a constant factor of the true parameter under the data generating distribution as defined in Section 4.3.

2. Guarantees under a concrete data model

We agree that the paper did not analyze the power of the audit under an explicit data model. In DP auditing too, the gap between the empirical lower bound and the true parameter is mostly assessed empirically, against the known parameter of DP-SGD (Nasr et al., 2021; Nasr et al., 2023), or numerically in idealized settings (Steinke et al., 2023; Mahloujifar et al., 2025). Recent work asks when one-run DP audits can be tight. Under pure DP, Keinan et al. (2025) give a necessary and sufficient condition for asymptotic tightness, which holds for algorithms that process each data point separately but fails for, e.g., a single counting query. For ff-DP mechanisms, Xiang et al. (2025) show that, in their framework, interference between canaries always leaves a gap, but they do not quantify it. Both concern record-level DP, not the subset-level guarantee of certified unlearning.

Following the reviewer's suggestion, the new Appendix G studies a Gaussian mean-estimation model in which the true unlearning parameter ρ⋆\rho^\star can be computed exactly (Prop. G.1), so we can measure how close our lower bound gets to it. The retain points and mm candidates are fixed. Each run fits the mean, unlearns a random half of the candidates while leaving a fraction η\eta of their influence, and adds Gaussian noise.

As the number of runs LL grows, our bound converges to a closed-form limit (Thm. G.4). When the candidates lie in orthogonal directions, as i.i.d. data approximately do in high dimension, this limit stays within a constant factor of ρ⋆\rho^\star as mm grows: it is at least about ρ⋆/(2π)≈0.16 ρ⋆\rho^\star/(2\pi)\approx0.16\,\rho^\star when ρ⋆/m\rho^\star/m is small (Thm. G.7), so the bound grows with mm and does not saturate. With two candidates, by contrast, it never exceeds 14log⁡2≈0.17\tfrac14\log2\approx0.17, however large ρ⋆\rho^\star is (Cor. G.5).

As stated in the paper, a bound below a claimed parameter is not evidence that the claim holds.

AuthorsOpenReview ↗

Response to reviewer 1mtV (continued)

3. Questions on Definition 3.1

We thank the reviewer for the careful summary, which matches our setup. Regarding whether the unlearning algorithm needs the full training set: Definition 3.1 allows U\mathcal U to receive it, which is the most permissive interface and covers methods such as class based unlearning methods and retain finetuning that use the retain set. Methods that do not use it are a special case.

Q1: Why a reference algorithm A‾\overline{\mathcal A}? We follow Koloskova et al. (2025), for two reasons.

  • Retraining with A\mathcal A is often the wrong baseline. Given the initialization and shuffling order, the training algorithm A\mathcal A may be deterministic, while a certified unlearning algorithm adds noise. A noisy output can never be close in Rényi divergence to a deterministic one, so requiring A‾=A\overline{\mathcal A}=\mathcal A would rule out noisy certified methods such as model clipping and R2D. Their guarantees instead compare against a noisy procedure that uses only the retain set.
  • It matches the standard definition. Sekhari et al. (2021, Definition 2) use the baseline U(A(Dr),Dr,∅)\mathcal U(\mathcal A(\mathcal D_r),\mathcal D_r,\emptyset), unlearning an empty set. Both this and our A‾\overline{\mathcal A} can be chosen freely, so either can be set to the other and the baselines coincide. The auditor never needs to know or run A‾\overline{\mathcal A}, since Lemma 4.1 compares two unlearned models directly. A rejection therefore rules out every reference algorithm at once.

Q3: Supremum over datasets, and whether all forget subsets are too strict.

  • Datasets. Certification claims hold for every dataset that satisfies their assumptions, so any such dataset is a valid test instance, and a rejection on it refutes the claim.
  • Forget sets. We agree that a guarantee for every subset of D\mathcal D may be too stringent. The literature uses two conventions. Koloskova et al. (2025, Definition 2.1) state the guarantee for every forget set, but their experiments use a forget set of 10% of the data (Section 5.1). Sekhari et al. (2021, Definition 2) instead build the restriction into the definition, requiring the guarantee only for forget sets up to a fixed size (their deletion capacity). Our definition follows the first convention, but our audits only use small forget sets. Each run forgets half of a candidate pool that is 10% of the training data, so about 5% of the training set on CIFAR-100, Shakespeare and TOFU (Section 6.1 and Appendix I). Our results therefore continue to hold under a definition that restricts the forget-set size to this range.

Summary of changes to the paper

  • New Section 4.3, with full statements and proofs in the new Appendix G: in a Gaussian location model, the exact true parameter, a closed form for our bound for any number of candidates, its limit as L→∞L\to\infty, the two-candidate ceiling, and a theorem showing that with many candidates the bound stays within a constant factor of the true parameter. Section 4.3 also states that the attainable bound grows with mm and depends on LL only through log⁡(1/ζ)/L\sqrt{\log(1/\zeta)/L}.
  • After Definition 3.1: a remark that our audits only forget about 5% of the training data, so the results also hold under definitions that restrict the forget-set size.

We appreciate your feedback and hope this addresses your concerns. Please let us know if anything needs clarification or if you have further questions.

AuthorsOpenReview ↗

References

References

  • Koloskova, A., Allouah, Y., Jha, A., Guerraoui, R., and Koyejo, S. (2025). Certified unlearning for neural networks. ICML 2025. https://proceedings.mlr.press/v267/koloskova25a.html
  • Mahloujifar, S., Melis, L., and Chaudhuri, K. (2025). Auditing f-differential privacy in one run. ICML 2025. https://proceedings.mlr.press/v267/mahloujifar25a.html
  • Nasr, M., Song, S., Thakurta, A., Papernot, N., and Carlini, N. (2021). Adversary instantiation: Lower bounds for differentially private machine learning. IEEE S&P 2021. https://arxiv.org/abs/2101.04535
  • Nasr, M., Hayes, J., Steinke, T., Balle, B., Tramèr, F., Jagielski, M., Carlini, N., and Terzis, A. (2023). Tight auditing of differentially private machine learning. USENIX Security 2023. https://arxiv.org/abs/2302.07956
  • Sekhari, A., Acharya, J., Kamath, G., and Suresh, A. T. (2021). Remember what you want to forget: Algorithms for machine unlearning. NeurIPS 2021. https://arxiv.org/abs/2103.03279
  • Steinke, T., Nasr, M., and Jagielski, M. (2023). Privacy auditing with one (1) training run. NeurIPS 2023. https://arxiv.org/abs/2305.08846
  • Triantafillou, E., Kairouz, P., Pedregosa, F., Hayes, J., Kurmanji, M., Zhao, K., Dumoulin, V., Jacques Junior, J., Mitliagkas, I., Wan, J., Sun Hosoya, L., Escalera, S., Dziugaite, G. K., Triantafillou, P., and Guyon, I. (2024). Are we making progress in unlearning? Findings from the first NeurIPS unlearning competition. arXiv preprint, 2024. https://arxiv.org/abs/2406.09073
  • Xiang, Z., Wang, T., and Wang, D. (2025). Privacy audit as bits transmission: (Im)possibilities for audit by one run. USENIX Security 2025. https://arxiv.org/abs/2501.17750
  • Keinan, A., Shenfeld, M., and Ligett, K. (2025). How well can differential privacy be audited in one run? NeurIPS 2025. https://arxiv.org/abs/2503.07199
Reviewer_t67YOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper discusses an auditing algorithm for unlearning mechanisms that either directly employ a differential privacy characterization of unlearning, or, if one can be constructed for them. Given the connection to the DP, the auditing algorithm presented resembles one-run privacy audits. The audits, thus, take the form of establishing a lower-bound for a zCDP (zero concentrated differential privacy) parameter ρ\rho, which is akin to the DP's privacy parameter ε\varepsilon. Several unlearning mechanisms are tested, and lower bounds are provided.

Critical strengths
  • Topic. Unlearning as a method has exceeded its original inception purpose as a tool to enable post-hoc privacy. Instead, it is being actively used for a host of other purposes, including alignment and removing capabilities. Regardless of the validity of such use cases, once an unlearning method is used, it is important to verify its effectiveness. The paper thus addresses a real and timely problem.

  • Breath. The empirical evaluation is diverse. There are, of course, many unlearning methods, but the methods chosen are representative. Also, an independent lower-bound audit of these methods would be useful to the community.

Critical weaknesses
  • Novelty and Proxy Nature. The idea of the paper is straightforward enough. Use the unlearning connection to DP, and by extension, DP audits to do audits of unlearning. This is not entirely novel. In fact, there are a few works (e.g. Y. Gu, J. He, and K. Chen 2025) that are not featured in the related work and are of relevance to the problem at hand that use the same connection. Furthermore, the connection to DP is at best a proxy measure of approximate unlearning and certainly not a measure of exact unlearning. This fact, together with the inherent approximation error of a privacy lower bound, calls into question the usefulness of using privacy lower bounds for auditing unlearning.

  • Potential baselines from the DP literature. Given the connection to DP auditing, I could see authors include other DP auditing mechanisms. For example, Mahloujifar et al. (2025 is a one-run audit; why not use that as a baseline for the auditing algorithm?

  • Overclaim regarding black-box nature. I think the claim that the auditor has black box access is unjustified. Notably, at the start of the threat model (3.3), the paper reads "We consider a black-box adversary that additionally observes (i) the initial model x0 at the start of training and (ii) the shuffling order π of the training points within each epoch. It does not observe the remaining randomness used during training or unlearning." Privacy research has shown that initialization and the batch shuffling order are among the most important factors that affect the quality of black box audits. By having the attacker observe these, the paper significantly increases the power of the adversary. The black-box access is therefore a stretch.

Questions for authors
  • Overall, the writing is pretty clear, but I was confused about the back and forth between zCDP and Rényi-DP. I do not think it was ever explained why we need two different DP notions, especially since these definitions are convertible. Is it because the composition and group privacy definitions are easier to work with in one vs. the other?

  • Do you think the connection to DP is the only viable means of auditing unlearning?

5 comments
AuthorsOpenReview ↗

Response to reviewer t67Y

We would like to thank the reviewer for the detailed and careful review. We now respond to their questions in the paper below.

1. Novelty and the role of approximate-unlearning audits

Subset-level auditing and its relationship to DP. We agree that the link between privacy and unlearning is established. Our contribution is an audit of a subset-level guarantee: Lemma 4.1 bounds the divergence between unlearned models for every pair of candidate forget subsets, including subsets that differ in many records. Record-level DP audits applied to the train-then-unlearn mechanism also give valid lower bounds, but they audit indistinguishability under the addition or removal of a single record, whereas ours audits indistinguishability between entire forget subsets. Point 2 compares the two empirically: with one run each, our bound is often orders of magnitude tighter (Table R1).

We thank the reviewer for pointing to Gu et al. (2025), which studies an orthogonal aspect of unlearning. Starting from a model trained with DP-SGD, it asks whether approximate unlearning preserves the DP guarantee for the retained records, using a LiRA-style attack to estimate each record's membership risk. We instead audit the certificate of the unlearning algorithm itself: whether, for every forget subset, the unlearned model is as close as claimed to a reference algorithm run on the retain set. The training algorithm need not be private, and our audit returns a high-confidence lower bound on ρ\rho that can reject the claimed certificate. We will discuss this work in the final version.

Scope: approximate unlearning and refuting certificates. We agree that we audit approximate unlearning, not exact unlearning. Exact unlearning, typically achieved by retraining from scratch on the retained data, is often computationally prohibitive for large models. This motivates approximate methods that come with certified guarantees (Guo et al., 2020; Sekhari et al., 2021; Neel et al., 2021; Chien et al., 2024; Zhang et al., 2025), and those certificates are what our auditor tests. Its main use is refutation: when the high-confidence empirical lower bound exceeds the claimed parameter, the certification claim is rejected. Hessian-based unlearning (Zhang et al., 2025) is the cleanest example. Its unlearning guarantee is proved under a convexity assumption, yet it is proposed as an unlearning algorithm for neural networks, which are non-convex. Our audit shows that the guarantee does not carry over: under uniform splitting, the auditor returns a large lower bound. The auditor therefore detects when a method is used outside the assumptions under which it was certified. The test is however one-sided: a bound below the claimed parameter does not show that a method unlearns.

2. Comparison with DP-auditing baselines

We agree that the one-run ff-DP auditor of Mahloujifar et al. (2025) is a relevant baseline, and we now compare against it. The transitivity argument behind Lemma 4.1 does not use the balance of the sign vectors, so the audit mechanism M\mathcal M is also 4ρ4\rho-zCDP under the standard neighboring relation, in which the inclusion of a single candidate changes. The ff-DP audit therefore applies to our setting, and a lower bound ρ′\rho' from it gives the unlearning bound ρ′/4\rho'/4. Its audit guarantee, however, assumes that each candidate is included independently, whereas our audit draws a uniformly random balanced sign vector. We therefore run the ff-DP audit on a separate run in which each candidate is included independently with probability 1/21/2. Both audits use 95% confidence, and each uses a single run.

Table R1. Every entry is a 95%-confidence lower bound ρLB\rho_{\mathrm{LB}} on the same zCDP unlearning parameter; the columns differ only in the audit used to compute it. Ours (L=10L=10): our audit with 10 runs, as in Table 1 of the paper. Ours (L=1L=1): our audit on a single run. ff-DP (L=1L=1): the one-run audit of Mahloujifar et al. (2025) on a single Bernoulli-sampled run, "–": not audited.

(a) Shakespeare and TOFU

MethodOurs (L=10L=10)Ours (L=1L=1)ff-DP (L=1L=1)Ours (L=10L=10)Ours (L=1L=1)ff-DP (L=1L=1)
ShakespeareTOFU
GD3.441.980.0205.594.318×10−48\times10^{-4}
Retain FT5.403.300.04415.0910.840.18
Grad. ascent0000.00908×10−48\times10^{-4}
Hessian8.765.520.066–––
NPO-RT–––8.165.980.013
SimNPO–––15.0910.840.18

[continued in the next box]

AuthorsOpenReview ↗

Response to reviewer t67y (contined)

(b) CIFAR-100

MethodOurs (L=10L=10)Ours (L=1L=1)ff-DP (L=1L=1)Ours (L=10L=10)Ours (L=1L=1)ff-DP (L=1L=1)
UniformAdversarial
GD42.533.300.00842.02.652.3×10−52.3\times10^{-5}
Retain FT37.532.540.007238.631.050.0098
Grad. ascent35.725.740.005838.626.140.0096
Hessian66.953.880.0132.82.130.0014
BadTeacher–––0.50.00263.2×10−43.2\times10^{-4}
DELETE–––89.468.110.015
SCRUB–––10.13.829.6×10−49.6\times10^{-4}
SCRUB+R–––11.413.110.0040

With one run each, our audit often gives orders of magnitude higher value in every row except gradient ascent, where both bounds are at most 10−310^{-3}. The gap is at least a factor of 88 (BadTeacher) and typically two to four orders of magnitude. This matches the expectation in point 1 above: the ff-DP audit tests the record-level guarantee, whereas ours uses the all-pairs constraint directly.

3. Access assumptions and the choice of privacy notions

Black-box terminology. We agree that observing the initialization and shuffling order makes the auditor stronger than output-only black-box access, and we will call our setting "black-box query access with public initialization and shuffling order". A known initialization is also the natural setting when a public base model is fine-tuned and then unlearned: in our TOFU experiments, the initialization is the released Llama-3.2-1B-Instruct checkpoint, which any auditor can obtain. The auditor still sees neither the remaining training and unlearning randomness nor any intermediate models. Because our definition requires the guarantee to hold conditional on this public information, our bounds refute that conditional guarantee, not a weaker one that averages over initialization and shuffling.

Why both zCDP and Rényi DP? We agree that two notions are not needed, and the presentation should have made this clear. The only privacy notion we audit is zCDP. A ρ\rho-zCDP guarantee is the Rényi-DP curve εγ=ργ\varepsilon_\gamma=\rho\gamma holding at every order γ>1\gamma>1, which is why Rényi divergence appears in the analysis. Lemma 4.1 derives Dγ(M(S1) ∥ M(S2))≤4ργD_\gamma(\mathcal M(S_1)\,\|\,\mathcal M(S_2))\le 4\rho\gamma for every γ>1\gamma>1 and every pair S1,S2S_1,S_2, so the induced audit mechanism is itself 4ρ4\rho-zCDP over all pairs of candidate forget sets. Lemma 4.2 was stated for a general Rényi-DP curve, but we never use that generality: every reported bound instantiates it with the zCDP curve εγ=4ργ\varepsilon_\gamma=4\rho\gamma, and the optimization over γ\gamma is part of a single test of the scalar ρ\rho. Composition plays no role in the argument. In the revision, we will state all guarantees, including Lemmas 4.1 and 4.2, directly in terms of zCDP.

Is the connection to DP the only way to audit unlearning?

No. Unlearning is most often evaluated with heuristic metrics. In vision, these include accuracy on the forget, retain and test sets, membership-inference attacks (Kurmanji et al., 2023; Hayes et al., 2025), relearning time (Golatkar et al., 2020) and the ZRF score (Chundawat et al., 2023). In language models, they include forget quality and truth ratio on TOFU (Maini et al., 2024), verbatim and knowledge memorization on MUSE (Shi et al., 2025), and accuracy on hazardous-knowledge questions in WMDP (Li et al., 2024). These metrics are useful diagnostics, but they are not guarantees: a model can score well and still leak the forget set to stronger attacks (Hayes et al., 2025) or recover it after light fine-tuning (Lynch et al., 2024; Hu et al., 2025).

A guarantee requires a definition that holds against every attack. The standard choice compares the unlearned model with a model that never saw the forget set. Ginart et al. (2019) require the two output distributions to be identical, and Guo et al. (2020) and Sekhari et al. (2021) relax this to statistical indistinguishability. This relaxation has the form of differential privacy, and the certified methods we audit (Guo et al., 2020; Sekhari et al., 2021; Neel et al., 2021; Chien et al., 2024; Koloskova et al., 2025; Zhang et al., 2025) state their guarantees this way. A heuristic metric cannot reject such a certificate, because a score, good or bad, implies nothing about the certified parameter. Rejecting it requires a hypothesis test of indistinguishability, which our audit provides. We use DP-auditing tools because the certificate has the form of a DP guarantee, not because unlearning reduces to DP: the direct reduction to record-level DP gives much weaker bounds (Table R1).

We appreciate your feedback and hope this addresses your concerns. Please let us know if anything needs clarification or if you have further questions.

AuthorsOpenReview ↗

References used in rebuttal

References

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of the discussion

Summary of revisions

We thank the AC and the reviewers. The reviewers found the problem real and timely and the evaluation diverse (t67Y). They also noted that the hypothesis test controls Type I error and that the paper correctly treats a non-rejection as no evidence of unlearning (waN6). Below we summarize how the revision addresses the remaining concerns.

1. Novelty and relation to DP auditing (t67Y, waN6, 1mtV). As t67Y notes, an independent lower-bound audit of unlearning methods is useful to the community. What we audit is a subset-level certificate. Lemma 4.1 bounds the divergence between unlearned models for every pair of forget subsets, and it removes the reference model, which the auditor cannot observe. We compared against the one-run ff-DP audit of Mahloujifar et al. (2025) on the same mechanism (Table R1, response to t67Y). With a single run each, our bound is typically two to four orders of magnitude larger, e.g. 53.953.9 versus 0.0130.013 for Hessian-based unlearning on CIFAR-100. The same table addresses 1mtV's concern about the cost of repeated runs: a single run already gives large bounds, e.g. 68.168.1 for DELETE versus 89.489.4 with L=10L=10 runs. We will add this comparison, including the single-run results, to the final version.

2. What the auditor can refute (waN6). A correctly proved certificate is a theorem, so a sound auditor cannot refute it. The useful question is whether the auditor refutes certificates used outside their assumptions, and it does. Hessian-based unlearning (Zhang et al., 2024) is proposed as certified for neural networks, but its certificate relies on convexity assumptions that do not hold for them. Our bound is 66.966.9 on CIFAR-100 and 8.768.76 on Shakespeare, among the largest in the paper. Section 7.1 now also states explicitly the cap that the auditor configuration places on the bound.

3. Power of the audit (1mtV, waN6). The new Section 4.3 (proofs in the new Appendix G) studies a Gaussian model in which the true parameter ρ⋆\rho^\star is known exactly. As the number of candidates mm grows, our bound stays within a constant factor of ρ⋆\rho^\star (at least about 0.16 ρ⋆0.16\,\rho^\star), whereas a two-candidate test is capped at 14log⁡2\tfrac14\log 2.

4. Experimental control (waN6). We added the retain/forget/test accuracies of model clipping on CIFAR-100 to Appendix J.1. We also added a new model-clipping audit on CIFAR-10, where the models reach 53–60% accuracy.

5. Presentation and definitions (waN6, t67Y, 1mtV).

  • Sections 6–8 are reorganized so that every description comes before any result and each number is stated once.
  • The main text audits only zCDP. Rényi divergence enters only as an analysis tool, and the Gaussian-DP and pure-DP variants are confined to the appendix. Lemmas 4.1–4.2 are now stated directly in terms of zCDP.
  • The threat model is now called "black-box query access with public initialization and shuffling order".
  • After Definition 3.1, we added a remark that our audits forget only about 5% of the training data, so the results also hold under definitions that restrict the size of the forget set.
  • In response to t67Y's follow-up question, the text after Equations (1)–(2) now states explicitly how the forget-set size enters the bound through the chance-overlap distribution.

Throughout, the test is one-sided: a bound above a claimed parameter refutes it, but a small bound is not evidence that a method unlearns.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.