acceptodds
Under review as a conference paper at ICLR 2027

Certified Retain Degradation Control for Counterfactual Guided Machine Unlearning

Abstract

Machine unlearning can introduce new prediction errors on retained data, and searching over update configurations can amplify this risk through selection bias. Reliable deployment therefore requires a degradation guarantee that remains valid after configuration selection. We propose conformal machine unlearning configuration evaluation (CMUCE), a unified framework for certification and selection that combines deletion-efficacy screening with finite-sample control of positive prediction regret relative to a fixed reference model. For each realized deletion request, we establish a guarantee that every accepted configuration has retained-population risk below a prescribed tolerance, even when candidates share calibration data and the final configuration is chosen from the accepted set. The construction combines Hoeffding–Bentkus bounds with family-wise testing and accommodates any calibration-independent candidate generator. We further characterize when counterfactual guidance improves the certificate: under explicit anchor-quality, gradient-alignment, and local score-transfer conditions, a paired one-step comparison yields a certificate-ordering bound whose calibration and anchor-yield error terms decay exponentially with their respective sample budgets. Under a Hellinger shift budget , an additional risk margin of extends certification to the deployment distribution. Experiments on vision, text, and tabular benchmarks show that guided candidates can attain lower retain regret and tighter certificates, while joint selection identifies configurations meeting both deletion and retain-risk requirements.

Primary area:
learning theory
Keywords:
machine unlearning, unlearning bias, certified bias, conformal risk control

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_nTG4OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

Machine unlearning updates a trained model after deletion requests but can introduce new errors on retained data, and searching over update configurations can select ones whose observed retain scores understate true population risk. The paper proposes CMUCE (Conformal Machine Unlearning Configuration Evaluation): a bounded positive prediction regret score s_ret ∈ [0,1] measuring how often an update flips a previously-correct retained prediction to an error relative to a fixed reference model; a Hoeffding–Bentkus lower-tail inversion for a fixed-candidate retain-risk upper bound (Prop. 4.1); Bonferroni/Holm family-wise error control over a candidate grid to preserve the retain guarantee after selection from shared calibration data (Prop. 4.2); and intersection with a separately-specified deletion-efficacy set. Theorem 5.1 states conditions (anchor quality, gradient alignment, local score transfer) under which counterfactual-guided candidates tighten the certificate; Theorem 6.1 adds a √(2ρ) margin under a Hellinger shift budget H(D,Q) ≤ ρ. Validation spans CIFAR-100 and CUB-200 (ResNet-18, with ViT/DeiT transfer), AG News (DistilBERT), and Adult/German, comparing CF-guided + CMUCE against seven unlearning baselines on a 20-class deletion task (Table 1), plus budget/noise/backbone and runtime studies.

Critical strengths
  1. The selection-valid retain guarantee is the right primitive, correctly executed. The paper identifies a real failure mode — configuration search inflating apparent retain performance — and controls it with a finite-sample, distribution-free family-wise construction (Prop. 4.2) that requires no independence among candidate scores and correctly observes that intersecting with the deletion-effective set can only shrink the accepted set. This is consequential because it is the paper's genuine, defensible deliverable and holds up under scrutiny.
  2. Honest exposure of the certificate–reality gap. Figure 2 and Table 1 report the HB upper bound and the independent-test retain regret side by side, and the text states plainly that the UCB stays above the test proxy (≈ 2×) and that the CUB certificate ties a baseline rather than beating it. This candor is consequential because it keeps the core "certified" claim defensible exactly where the empirical edge is thin, and lets a reader locate the real contribution without reverse-engineering it.
Critical weaknesses
  1. The word "certified" in the title and abstract claims more than the theorems deliver, at the two points that distinguish the paper. The abstract's "under a Hellinger shift budget ρ, a margin of √(2ρ) extends certification to the deployment distribution" is, in Thm 6.1, a bound that holds only if H(D,Q) ≤ ρ — and the paper provides no procedure to certify ρ, conceding that estimating the radius needs external evidence. The deployment "certificate" is therefore an assumption-conditional bound, not a guarantee the method can issue on real data. Likewise "certified improvement" (Thm 5.1) is a sufficient-condition result resting on M_ν>0, c_s>0, gradient alignment, and a local score-transfer condition, none of which is shown to hold for the configurations CMUCE actually selects in Table 1. Since "certified," applied to deployment and to the counterfactual-guidance benefit, is the paper's headline differentiator, the gap between the word and the theorems is material.
  2. The empirical superiority rests on a single run with no variance, and the flagship advantage is a tie or within plausible noise. Table 1 reports one number per cell at a fixed seed (42) with no std or confidence interval. The claimed advantages are small: the CIFAR UCB edge is .042 vs. .045/.048, and on CUB the UCB (.096) ties ℓ₁-Sparse; retain-regret differences of .002–.007 over a 10% test split with no reported n or event count are not shown to exceed sampling noise, and the deletion-audit FA (5.6/7.3) is not best (ℓ₁-Sparse 5.2/6.7; Retrain 0.0) but merely under the threshold. A central contribution billed as empirical improvement is thus demonstrated only for one seed, leaving the comparative claims unestablished.
Questions for authors
  1. Please report Table 1's R and UCB columns as mean ± std over multiple seeds / calibration splits, with the test-split n and event count behind each R. The claimed edges (.002–.007) are smaller than plausible single-seed noise; without variance the "lowest retain risk" and "tightest CIFAR UCB" claims cannot be told apart from chance.
  2. For the configurations CMUCE actually selects in Table 1, do the Thm 5.1 conditions (M_ν>0, c_s>0, gradient alignment, the Eq. 13 score-transfer condition) hold? Please show a diagnostic in at least the controlled settings where they can be measured. If they are not verified, "certified improvement" should be restated as a sufficient-condition theorem that is not demonstrated on the runs.
  3. How would a practitioner obtain or bound ρ = H(D,Q) for a real deployment distribution? If ρ cannot be estimated from available data, the abstract/title phrase "extends certification to the deployment distribution" overstates Thm 6.1 — will you qualify it to "conditional on an assumed Hellinger budget," or supply a procedure that certifies ρ?
  4. CF-guided uses N_cf=50 counterfactual generations (an extra ~8.4 s and an extra optimization signal) that the baselines do not receive. Is the Table 1 comparison matched on total compute and on the information available to each method? Please add a compute-matched or signal-matched baseline; otherwise the retain-risk edge cannot be attributed to the method rather than to extra tuning.
11 comments

Thank you for your careful review. We have revised the manuscript to address your questions and make the evidence for each conclusion easier to assess.

1.Table 1 of the revised manuscript reports mean ± sample SD over three seeds. The R and nominal HB results are reproduced below, with δ=0.10\delta=0.10 for each fixed candidate. Appendix E.9 gives exact calibration and test counts in Tables 6–7 for the key CF-guided versus ℓ₁-Sparse comparisons on both datasets, together with CIFAR-100 retraining. Table 8 reports the corresponding summaries.

MethodCIFAR-100 RCIFAR-100 HBCUB-200 RCUB-200 HB
Retrain0.008 ± 0.0010.026 ± 0.0020.015 ± 0.0040.069 ± 0.007
FT-Unlearn0.033 ± 0.0050.054 ± 0.0030.051 ± 0.0070.103 ± 0.003
SCRUB0.041 ± 0.0020.060 ± 0.0030.051 ± 0.0030.107 ± 0.004
UNSIR0.034 ± 0.0050.057 ± 0.0040.049 ± 0.0060.105 ± 0.005
SalUn0.027 ± 0.0030.043 ± 0.0050.042 ± 0.0040.104 ± 0.005
MinNorm-OG0.027 ± 0.0030.048 ± 0.0020.044 ± 0.0020.100 ± 0.003
SEMU0.030 ± 0.0020.054 ± 0.0020.045 ± 0.0030.102 ± 0.004
ℓ₁-Sparse0.027 ± 0.0010.046 ± 0.0030.043 ± 0.0020.094 ± 0.002
CF-guided + CMUCE0.022 ± 0.0010.040 ± 0.0020.040 ± 0.0010.093 ± 0.003

Each reported CIFAR-100 run uses 4,800 retained calibration examples and 4,800 retained test examples. Each reported CUB-200 run uses 1,060 examples in each split. Here kk counts examples that the reference predicts correctly and the updated model predicts incorrectly. The denominator nn includes the entire retained split, so test regret is ktest/ntestk_{\mathrm{test}}/n_{\mathrm{test}}. We compute nominal HB from kcalk_{\mathrm{cal}} and ncaln_{\mathrm{cal}} using Proposition 4.1 at δ=0.10\delta=0.10. The integer count enters the binomial tail directly.

CIFAR-100:

MethodSeedCalibration k/nTest k/nTest RNominal HB (δ=0.1)RA / FA (%)
Retrain42112 / 480038 / 48000.0079170.02759378.2 / 0.0
Retrain4394 / 480036 / 48000.0075000.02352678.1 / 0.0
Retrain44103 / 480041 / 48000.0085420.02556479.6 / 0.0
ℓ₁-Sparse42204 / 4800130 / 48000.0270830.04805776.3 / 5.2
ℓ₁-Sparse43181 / 4800125 / 48000.0260420.04297875.5 / 5.2
ℓ₁-Sparse44194 / 4800135 / 48000.0281250.04585176.2 / 5.6
CF-guided + CMUCE42178 / 4800106 / 48000.0220830.04231476.8 / 5.6
CF-guided + CMUCE43156 / 4800101 / 48000.0210420.03743476.4 / 5.4
CF-guided + CMUCE44165 / 4800110 / 48000.0229170.03943376.7 / 5.8

CUB-200:

MethodSeedCalibration k/nTest k/nTest RNominal HB (δ=0.1)RA / FA (%)
ℓ₁-Sparse4284 / 106046 / 10600.0433960.09558479.4 / 6.7
ℓ₁-Sparse4380 / 106044 / 10600.0415090.09149379.1 / 6.6
ℓ₁-Sparse4484 / 106048 / 10600.0452830.09558479.2 / 7.1
CF-guided + CMUCE4284 / 106043 / 10600.0405660.09558479.9 / 7.3
CF-guided + CMUCE4379 / 106041 / 10600.0386790.09046979.4 / 7.0
CF-guided + CMUCE4482 / 106044 / 10600.0415090.09354079.9 / 7.4

2.In Section 5 of the revised manuscript, we have titled Theorem 5.1 “Sufficient conditions for one-step certificate ordering.” The theorem describes a particular comparison between two updates from the same starting parameter. Both update directions are evaluated at that starting point. The resulting certificates use the same calibration observations and confidence level.

The guarantee applies under the stated assumptions on anchor quality, gradient alignment, smoothness and score transfer. These assumptions yield a probability bound for aCF≤astda_{\mathrm{CF}} \le a_{\mathrm{std}}. For its application to the Table 1 models, the required uniform population bounds remain explicit assumptions. In particular, establishing Mν>0M_\nu > 0 and cs>0c_s > 0 requires bounds that hold across the relevant population.

The empirical role of the diagnostics is to characterize the observed relationship between the optimization loss and the retain score. Appendix E.10, Table 9, reports the expanded results below. Each vision or text grid contributes 156 paired standard/CF updates, and each tabular grid contributes 52 pairs. These counts refer to paired diagnostic observations.

Dataset / taskBackboneValid-anchor fractionGradient cosineSurrogate gapSame-sign rateFitted slope
CIFAR-100 classResNet-180.72 ± 0.030.27 ± 0.040.068 ± 0.00979.5%0.18
CIFAR-100 classViT-Tiny0.69 ± 0.040.23 ± 0.040.059 ± 0.01076.3%0.17
CIFAR-100 classDeiT-Tiny0.70 ± 0.030.25 ± 0.040.063 ± 0.00977.6%0.17
CUB-200 classResNet-180.66 ± 0.040.23 ± 0.050.074 ± 0.01176.3%0.15
CUB-200 classViT-Tiny0.63 ± 0.040.20 ± 0.050.065 ± 0.01273.7%0.14
CUB-200 classDeiT-Tiny0.64 ± 0.040.21 ± 0.040.069 ± 0.01175.0%0.15
AG NewsDistilBERT0.75 ± 0.030.29 ± 0.040.048 ± 0.00781.4%0.19
Adult3-layer DNN0.78 ± 0.030.31 ± 0.040.055 ± 0.00882.7%0.21
German3-layer DNN0.71 ± 0.040.24 ± 0.050.052 ± 0.00976.9%0.17

Yield, cosine and surrogate-gap entries report diagnostic means ± SD. Sign agreement is 73.7%–82.7%, and the fitted slopes are positive across all nine settings. These measurements provide empirical support for an association between surrogate and score changes. The fitted slope summarizes that observed association. The theorem's csc_s specifies a uniform population lower bound. The average cosine similarly describes the observed alignment, while the theorem requires its stated alignment and margin conditions.

The roles of the two evaluations are also explicit in the revised manuscript. Table 1 compares fixed configurations and gives their nominal δ=0.1\delta=0.1 bounds. The 52-candidate selection analysis applies the deletion screen and the family-wise retain-risk tests to decide which candidates qualify for deployment.

The central certification result is established by Propositions 4.1–4.2. It controls retain risk after selection under the conditional-i.i.d. and calibration-separation assumptions. Candidate-wise tests may share data and may be dependent. This guarantee holds independently of the additional conditions used to explain one-step certificate ordering.

3.The revised Abstract describes the shift extension in plain language. Section 6 specifies the Hellinger budget as an input that requires external justification for the intended deployment. Theorem 6.1 gives a sensitivity bound conditional on this assumed budget for the full evaluation-unit distribution.

Under the normalized convention used in the manuscript, the additional risk margin is 2\sqrt{2} times ρ\rho. For the fixed bounded retain score and Z=(X,Y)Z=(X,Y), $ \left|R_Q(\lambda)-R_D(\lambda)\right| \le \operatorname{TV}(D_Z,Q_Z) \le \sqrt{2}H(D_Z,Q_Z) \le \sqrt{2}\rho.$ The distance inequality is recorded in Gibbs and Su, Section 3, Eq. (8), now cited in Section 6 and Appendix D.1 of the revised manuscript. Their Section 2 uses the unnormalized distance dH=2Hd_H=\sqrt{2}H. Let δcal\delta_{\mathrm{cal}} be the family-wise source-calibration error budget. The simultaneous source-certification event has probability at least 1−δcal1-\delta_{\mathrm{cal}}. On this event, the inequality gives the following bound for every candidate in the declared family: $ H(D_Z,Q_Z)\le\rho \Longrightarrow R_Q(\lambda)\le\min\{1,a^{\mathrm{sim}}_{\lambda,D}+\sqrt{2}\rho\}. $ This makes the effect of a chosen budget explicit. When asim<r0a^{\mathrm{sim}} < r_0, the headroom (r0−asim)/2(r_0-a^{\mathrm{sim}})/\sqrt{2} gives the admissible-radius boundary. The sufficient rule accepts a justified budget strictly below that boundary.

An external procedure could supply a valid upper bound on the radius with error probability η\eta. Combining this with the source-calibration error budget gives confidence at least 1−δcal−η1-\delta_{\mathrm{cal}}-\eta. Bonferroni source calibration allocates δcal/N\delta_{\mathrm{cal}}/N to each candidate. Another practical option is direct recalibration on an independent i.i.d. labeled sample from QQ. The candidate family is frozen before that calibration, with the same fixed bounded score and appropriate family-wise control.

We retain "Certified" in the title because it refers to the retain-degradation control of Propositions 4.1–4.2, which holds after selection under the stated calibration assumptions; the shift and counterfactual-guidance results are now presented as conditional and sufficient-condition results, respectively.

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

This paper introduces a new perspective for evaluating the unlearned model's performance on retaining data and proposes a framework for evaluating and selecting unlearning configs. The authors introduce positive prediction regret to measure newly introduced prediction errors relative to a fixed reference model. Experiments on vision, text, and tabular datasets demonstrate reduced retain degradation and tighter risk bounds compared with existing unlearning baselines.

Critical strengths
  1. The proposed positive prediction regret captures newly introduced errors that may be hidden by aggregate retained accuracy. This provides a useful perspective for evaluating the side effects of machine unlearning.

  2. By combining finite-sample risk bounds with family-wise testing, the proposed CMUCE provides retain-side guarantees that remain valid when selecting among multiple unlearning configurations. The framework is modular and can accommodate different unlearning methods and candidate generators.

Critical weaknesses
  1. Although the experiments demonstrate lower retained degradation and tighter certificates for counterfactual guided candidates, they do not directly establish the practical advantage of selection valid certification over simpler configuration selection strategies.

  2. The main experiments appear to rely on a single random seed, without reporting variability across independent training runs. Several improvements over existing unlearning baselines are relatively small, yet no standard deviations or confidence intervals across runs are provided.

Questions for authors
  1. Could the authors compare CMUCE with standard validation-based configuration selection on the same candidate grid, particularly in terms of the frequency of selecting configurations whose retained-population risk exceeds the specified tolerance?

  2. Could the authors report results across multiple independent training seeds, including the mean and standard deviation of retain regret, deletion efficacy, and certificate values?

4 comments

Thank you for your helpful suggestions. We have added a direct comparison of selection rules and results across three seeds to the revised manuscript.

1.CMUCE allows a model to be chosen from its accepted set while retaining the stated risk guarantee. This holds under the calibration assumptions in Proposition 4.2. We have added a direct comparison in Section 7.3 and Figure 4(a) of the revised manuscript. Appendix E.8 gives the final selected-model results in Table 4 and the accepted-set diagnostics in Table 5.

All rules use the same 52-candidate grid and the same set of candidates that pass the deletion audit. For each setting, we evaluate 200 random partitions of the held-out pools with r0=0.05r_0=0.05 and δ=0.10\delta=0.10. Each rule ranks eligible candidates by highest calibration retained accuracy. Ties are resolved by lowest calibration regret count, then lowest candidate index. The five rules differ in how they screen for retain risk:

  • Validation RA selects directly from the deletion-effective set.
  • Empirical regret first requires calibration regret below 0.05.
  • Nominal HB first requires the candidate-wise p-value to be at most 0.10.
  • CMUCE–Bonferroni requires the p-value to be at most 0.10/52.
  • CMUCE–Holm applies the sequentially rejective family-wise procedure at 0.10.

An empty eligible set leads to abstention. For CIFAR class and sample deletion, the calibration/test sizes are 2,400/4,800. For CUB class deletion, they are 1,060/1,060. Both the output rate and the selected-model test-exceedance rate use all 200 partitions as the denominator. A partition counts as an exceedance when the rule returns a model whose independent-test regret is at or above 0.05. An abstention contributes zero to this rate. The test-regret and test-RA columns report mean ± SD over partitions that return a model.

SettingSelection ruleOutput (%)Selected test exceedance (%)Test R, given outputTest RA (%), given output
CIFAR classValidation RA100.038.50.048 ± 0.00677.0 ± 0.3
CIFAR classEmpirical regret100.026.50.045 ± 0.00576.9 ± 0.3
CIFAR classNominal HB100.012.50.041 ± 0.00476.9 ± 0.2
CIFAR classCMUCE–Bonferroni100.01.50.031 ± 0.00376.6 ± 0.2
CIFAR classCMUCE–Holm100.02.00.031 ± 0.00376.6 ± 0.2
CIFAR sampleValidation RA100.046.00.051 ± 0.00776.6 ± 0.3
CIFAR sampleEmpirical regret100.031.00.047 ± 0.00676.5 ± 0.3
CIFAR sampleNominal HB99.514.50.043 ± 0.00576.5 ± 0.3
CIFAR sampleCMUCE–Bonferroni98.01.50.037 ± 0.00376.4 ± 0.2
CIFAR sampleCMUCE–Holm98.52.00.037 ± 0.00376.4 ± 0.2
CUB classValidation RA100.042.00.049 ± 0.00780.1 ± 0.3
CUB classEmpirical regret100.028.50.046 ± 0.00680.0 ± 0.3
CUB classNominal HB98.013.00.042 ± 0.00579.9 ± 0.3
CUB classCMUCE–Bonferroni95.02.00.036 ± 0.00379.7 ± 0.2
CUB classCMUCE–Holm95.52.50.036 ± 0.00379.7 ± 0.2

With this common ranking rule, CMUCE–Bonferroni returns a model in 95.0%–100.0% of partitions. Its selected-model test-exceedance frequency is 1.5%–2.0%, compared with 38.5%–46.0% for validation-RA selection. Among partitions with an output, its mean test RA is 0.2–0.4 percentage points below the validation-RA baseline. These measurements show the observed risk and accuracy trade-off for the returned models.

The 200 partitions measure resampling behavior within the available held-out pools. Independent-test regret provides an empirical proxy for population risk. Proposition 4.2 gives the population-risk guarantee under its stated assumptions.

The following table reports how often at least one accepted candidate has independent-test regret at or above 0.05. Each percentage uses all 200 partitions.

Setting / calibration budgetAcceptance ruleSet-level test exceedance
CIFAR class, 0.5×Empirical-regret screen42.5%
CIFAR class, 0.5×Nominal HB19.5%
CIFAR class, 0.5×CMUCE–Holm4.5%
CIFAR class, 0.5×CMUCE–Bonferroni3.5%
CIFAR sample, 0.5×Empirical-regret screen51.0%
CIFAR sample, 0.5×Nominal HB23.0%
CIFAR sample, 0.5×CMUCE–Holm4.0%
CIFAR sample, 0.5×CMUCE–Bonferroni3.0%
CUB class, 1.0×Empirical-regret screen46.0%
CUB class, 1.0×Nominal HB21.0%
CUB class, 1.0×CMUCE–Holm4.5%
CUB class, 1.0×CMUCE–Bonferroni4.0%

Empirical screening yields set-level test exceedances of 42.5%–51.0%, and nominal HB yields 19.5%–23.0%. The corresponding CMUCE values are 3.0%–4.5%. This complements the selected-model comparison by examining the entire accepted set.

If a selected model exceeds the test threshold, its accepted set necessarily contains a model that does. Thus, on these same partitions, the set-level frequency also bounds the all-attempt test-exceedance frequency of any alternative ranking rule that selects from that set. Abstention contributes zero to the all-attempt frequency.

For the population guarantee, let F\mathcal{F} denote the non-calibration information that fixes the candidate family, reference and risks. Under the stated calibration assumptions, each candidate with risk at least r0r_0 passes its Bonferroni test with probability at most δ/52\delta/52, conditional on F\mathcal{F}. A union bound gives

&\Pr\\!\left(\exists\lambda\in\widehat{\Lambda}_{\mathrm{deploy}}: R_{\mathrm{ret}}(\lambda)\ge r_0\mid\mathcal{F}\right)\\\\ &\quad\le \sum_{\substack{\lambda\in\Lambda:\\\R_{\mathrm{ret}}(\lambda)\ge r_0}} \Pr(p_\lambda\le\delta/52\mid\mathcal{F})\\\\ &\quad\le\delta. \end{aligned}$$ Averaging over $\mathcal{F}$ gives the same bound across candidate-construction randomness. Applying the deletion audit further reduces the accepted set and preserves the guarantee. Any subsequent choice within that set inherits it. This is the argument in Proposition 4.2. Its general Learn-then-Test basis is stated in [Angelopoulos et al., Section 2.1, Theorem 1, and Section 2.3, Proposition 2 (arXiv v5)](https://arxiv.org/pdf/2110.01052v5). An independent select-then-certify split provides another valid route when a separate certification sample is available.

2.Table 1 of the revised manuscript reports the fixed-configuration comparisons for seeds 42, 43, and 44 as mean ± sample SD. The results are reproduced below, with nominal HB bounds at δ=0.10\delta=0.10. Appendix E.9 supplies exact per-run counts for the key comparisons.

CIFAR-100:

MethodRA (%)FA (%)Test regret RNominal HB UCB
Retrain78.6 ± 0.80.0 ± 0.00.008 ± 0.0010.026 ± 0.002
FT-Unlearn75.7 ± 1.17.0 ± 0.70.033 ± 0.0050.054 ± 0.003
SCRUB74.6 ± 0.56.6 ± 0.30.041 ± 0.0020.060 ± 0.003
UNSIR75.8 ± 0.66.3 ± 0.40.034 ± 0.0050.057 ± 0.004
SalUn76.0 ± 0.35.9 ± 0.20.027 ± 0.0030.043 ± 0.005
MinNorm-OG76.1 ± 0.45.8 ± 0.30.027 ± 0.0030.048 ± 0.002
SEMU76.4 ± 0.35.2 ± 0.50.030 ± 0.0020.054 ± 0.002
ℓ₁-Sparse76.0 ± 0.45.3 ± 0.20.027 ± 0.0010.046 ± 0.003
CF-guided + CMUCE76.6 ± 0.25.6 ± 0.20.022 ± 0.0010.040 ± 0.002

CUB-200:

MethodRA (%)FA (%)Test regret RNominal HB UCB
Retrain82.6 ± 1.20.0 ± 0.00.015 ± 0.0040.069 ± 0.007
FT-Unlearn78.4 ± 0.88.9 ± 0.40.051 ± 0.0070.103 ± 0.003
SCRUB78.4 ± 0.48.0 ± 0.30.051 ± 0.0030.107 ± 0.004
UNSIR78.6 ± 0.58.2 ± 0.40.049 ± 0.0060.105 ± 0.005
SalUn79.5 ± 0.37.3 ± 0.20.042 ± 0.0040.104 ± 0.005
MinNorm-OG79.0 ± 0.36.8 ± 0.40.044 ± 0.0020.100 ± 0.003
SEMU79.3 ± 0.37.1 ± 0.20.045 ± 0.0030.102 ± 0.004
ℓ₁-Sparse79.2 ± 0.26.8 ± 0.20.043 ± 0.0020.094 ± 0.002
CF-guided + CMUCE79.7 ± 0.37.2 ± 0.20.040 ± 0.0010.093 ± 0.003

Among the reported approximate unlearning methods, CF-guided + CMUCE has the lowest mean test regret on both datasets. It also has the lowest mean nominal HB bound on CIFAR-100. On CUB-200, its mean HB bound is 0.093, compared with 0.094 for ℓ₁-Sparse. Its mean regret is 0.040, compared with 0.043 for ℓ₁-Sparse. Both observed differences are small. We interpret these three-run comparisons as descriptive evidence of performance and variability, including the small CUB-200 regret gap. Retraining supplies a reference for the forget–retain trade-off.

The seed study measures variation across trained models. The partition study measures how selection rules behave when the held-out pools are repartitioned. Nominal HB bounds characterize fixed configurations. Selection across the full grid uses the family-wise tests in Proposition 4.2.

Thank you for helping us make the selection comparison and its variability easier to assess.

Dear Reviewer Reviewer 55Cy,

Thank you again for your helpful review. As the discussion period draws to a close, we would be very grateful if you could review our point-by-point responses and additional results, in particular the comparison with validation-based selection and the three-seed results that you requested. If our responses have addressed your concerns, we hope you will take them into account in your final assessment. We understand that this is a particularly busy time and sincerely appreciate your consideration. If any concerns remain, we would welcome the opportunity to provide further clarification.

Best regards,
The Authors

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

This paper focuses on the problem that existing unlearning evaluations overlook the fact that retained accuracy describes aggregate utility but can hide a redistribution of errors: improved predictions on some examples can offset newly incorrect predictions on others. The authors instead focus on the positive increase in per-example loss relative to a reference model. With the original model as the reference, this score directly quantifies how often an update turns a previously correct retained prediction into an error. The authors introduce conformal machine unlearning configuration evaluation (CMUCE). CMUCE turns retain-side degradation into an explicit, selection-valid deployment constraint for machine unlearning. Combining this constraint with a deletion audit yields a joint set from which practitioners can choose according to utility or cost. The local analysis connects useful counterfactual guidance to tighter certificates, while the shift extension expresses deployment uncertainty through a transparent risk budget.

Critical strengths
  • The authors conduct empirical validation on five datasets across image, text, and tabular modalities, using multiple network architectures, such as ResNet, ViT, DNN, and BERT.
  • The authors focus on measuring the positive increase in per-example loss relative to a reference model to quantify how often an update turns a previously correct retained prediction into an error.
Critical weaknesses
  • The evaluation protocol in Section 7 reports only a single seed, 42. Results across multiple seeds would help assess the stability of the findings.
  • Some writing issues: The authors should briefly explain “counterfactual budgets” and “counterfactual and other candidate generators” when they first appear in the Introduction to improve readability.
  • The assumption in Eq. (13) needs further explanation and empirical justification. Extending the validation of this assumption to more of the evaluated datasets and model architectures would strengthen the analysis.
  • Although the experiments cover image, text, and tabular modalities, all evaluated tasks are classification tasks. Could the authors discuss the framework’s applicability to LLM unlearning, including any necessary changes to the scoring and calibration procedures?
  • Robustness against relearning attacks is an important aspect of unlearning. Could the authors discuss how their evaluation framework relates to this aspect and whether its evaluation results provide any insights into such robustness?
Questions for authors

Please see the Weaknesses.

6 comments

Thank you for your careful reading and constructive suggestions. We have clarified the explanations and added further evaluations in the revised manuscript.

1.Table 1 of the revised manuscript now reports fixed-configuration results for seeds 42, 43, and 44. Each entry gives the mean ± sample SD across these runs. The HB columns use nominal δ=0.10\delta=0.10. Appendix E.9 provides exact per-run counts for the key comparisons in Tables 6–7 and the corresponding summaries in Table 8.

The R and HB results are summarized below. CF-guided + CMUCE also achieves forget accuracies of 5.6 ± 0.2% on CIFAR-100 and 7.2 ± 0.2% on CUB-200. Both meet the class-deletion audit threshold of 10%.

MethodCIFAR-100 RCIFAR-100 HBCUB-200 RCUB-200 HB
Retrain0.008 ± 0.0010.026 ± 0.0020.015 ± 0.0040.069 ± 0.007
FT-Unlearn0.033 ± 0.0050.054 ± 0.0030.051 ± 0.0070.103 ± 0.003
SCRUB0.041 ± 0.0020.060 ± 0.0030.051 ± 0.0030.107 ± 0.004
UNSIR0.034 ± 0.0050.057 ± 0.0040.049 ± 0.0060.105 ± 0.005
SalUn0.027 ± 0.0030.043 ± 0.0050.042 ± 0.0040.104 ± 0.005
MinNorm-OG0.027 ± 0.0030.048 ± 0.0020.044 ± 0.0020.100 ± 0.003
SEMU0.030 ± 0.0020.054 ± 0.0020.045 ± 0.0030.102 ± 0.004
ℓ₁-Sparse0.027 ± 0.0010.046 ± 0.0030.043 ± 0.0020.094 ± 0.002
CF-guided + CMUCE0.022 ± 0.0010.040 ± 0.0020.040 ± 0.0010.093 ± 0.003

2.We have defined these terms at first use in the Introduction of the revised manuscript. A counterfactual budget counts attempted anchors per deleted input. Every attempt contributes to this budget. Feasibility and quality checks then determine which anchors are valid. An anchor generator constructs alternative inputs that guide the update around deleted examples. A candidate generator is the unlearning procedure that produces an updated model for each configuration. CMUCE evaluates the resulting models with the same decision rule. We also spell out counterfactual (CF) before using the abbreviation.

3.Section 5 of the revised manuscript now explains how Eq. (13) connects the optimization loss to the score that CMUCE certifies. For the default 0–1 score, consider examples that the reference model predicts correctly. When the standard update makes an error and the CF update corrects it, retain risk decreases. When the standard update is correct and the CF update introduces an error, retain risk increases. Under the stated alignment and valid-anchor event, Eq. (13) requires the fraction helped by CF to exceed the fraction harmed by at least csMν>0c_s M_\nu > 0. Both fractions are measured over the full retained population.

We have also expanded the diagnostics in Appendix E.10, Table 9. Each vision or text setting uses 156 paired standard/CF updates, and each tabular setting uses 52 pairs. These counts refer to paired diagnostic observations.

Dataset / taskBackboneValid-anchor fractionGradient cosineSurrogate gapSame-sign rateFitted slope
CIFAR-100 classResNet-180.72 ± 0.030.27 ± 0.040.068 ± 0.00979.5%0.18
CIFAR-100 classViT-Tiny0.69 ± 0.040.23 ± 0.040.059 ± 0.01076.3%0.17
CIFAR-100 classDeiT-Tiny0.70 ± 0.030.25 ± 0.040.063 ± 0.00977.6%0.17
CUB-200 classResNet-180.66 ± 0.040.23 ± 0.050.074 ± 0.01176.3%0.15
CUB-200 classViT-Tiny0.63 ± 0.040.20 ± 0.050.065 ± 0.01273.7%0.14
CUB-200 classDeiT-Tiny0.64 ± 0.040.21 ± 0.040.069 ± 0.01175.0%0.15
AG NewsDistilBERT0.75 ± 0.030.29 ± 0.040.048 ± 0.00781.4%0.19
Adult3-layer DNN0.78 ± 0.030.31 ± 0.040.055 ± 0.00882.7%0.21
German3-layer DNN0.71 ± 0.040.24 ± 0.050.052 ± 0.00976.9%0.17

Yield, cosine and surrogate-gap entries report diagnostic means ± SD. The same-sign rate records how often the observed surrogate and score changes agree in direction. Across the nine settings, this rate is 73.7%–82.7%, and the fitted slopes are positive. These results describe the observed relationship between the two changes. A fitted slope summarizes the sampled observations. Applying Theorem 5.1 to a specific Table 1 model additionally requires valid uniform population bounds, including csc_s in Eq. (13), together with the other stated conditions.

In Section 5, we have restated Theorem 5.1 as “Sufficient conditions for one-step certificate ordering.” The comparison starts both updates from the same parameter and evaluates both directions there. The two certificates use the same calibration observations and confidence level. Under the stated anchor, alignment, smoothness and score-transfer assumptions, the theorem gives a probability bound for aCF≤astda_{\mathrm{CF}} \le a_{\mathrm{std}}. Propositions 4.1–4.2 provide retain-risk control under the calibration assumptions independently of these additional mechanism conditions.

4.Appendix E.12 of the revised manuscript now explains the proposed extension through score design and calibration. For generation, the score should describe the retained capability to preserve. A fixed evaluation rule can assign each answer a utility in [0,1][0,1]. Its positive decrease from the reference model measures deterioration. For example, a decrease from 0.9 to 0.7 contributes 0.2, while an improvement contributes zero. An alternative measures the positive increase in length-normalized sequence negative log-likelihood. A scale fixed before calibration normalizes this increase, which is then clipped at one. The resulting certificate concerns the expected normalized, clipped score. Larger increases receive the same maximum score.

Calibration would use one bounded score per independently sampled unit. This can be a prompt–answer pair or a pre-specified aggregate for a cluster of related prompts. The units must satisfy the conditional i.i.d. assumption, and cluster aggregation defines a cluster-level risk. Stochastic generation or judging would use independent evaluation randomness under a fixed protocol. The candidate family, reference model, normalization, decoding and judging rules would be fixed before calibration. Calibration observations must be held apart from pretraining, candidate construction and tuning. A separate deletion audit would evaluate forgetting. Our current text experiments evaluate classification, and this formulation provides a concrete protocol for future generative evaluation. Thank you for suggesting this broader evaluation perspective.

5.Relearning asks whether further training can recover the information targeted by deletion. For example, a declared attack could fine-tune the unlearned model on a specified amount of deleted or related data. Our current results characterize deletion efficacy and retained degradation immediately after the evaluated unlearning update. They provide the starting point for the proposed evaluation in Appendix E.12. That evaluation would measure both quantities again after further training, since recovery of deleted information and changes in retained utility answer different questions.

We would pre-specify attack training data, optimization budgets and evaluation checkpoints, then freeze the complete family of attacked models. A fresh retained calibration set, excluded from pretraining, unlearning, attack training and protocol tuning, would evaluate their updated retain scores relative to the fixed reference. For NN candidates and KK declared attack settings, including all evaluated budgets and checkpoints, Bonferroni can allocate δ/(NK)\delta/(NK) to each pair. Under the conditional i.i.d. assumption, this provides simultaneous retain-risk control for that family. A calibration-independent post-attack deletion audit would then identify models meeting both requirements at the declared checkpoints. A further adaptively designed attack would require a new evaluation with independent calibration.

A related use keeps the original unlearned models as deployment candidates and filters them using a calibration-independent relearning audit. Their original retain guarantee is preserved because filtering only shrinks the eligible set. The fresh calibration above is used when the target is the attacked models themselves. Appendix E.12 now explains these two uses separately and specifies what each evaluation would establish. We appreciate your suggestion to evaluate these aspects separately.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.