TL;DR
Current machine unlearning methods promise to scrub sensitive data from trained models without the immense cost of retraining from scratch, but how do we know they truly forgot? This paper proposes computational unlearning—a cryptographic indistinguishability framework testing whether an adversary can tell an unlearned model apart from a "mirror" model retrained from scratch. The authors show that popular unlearning techniques fail this test dramatically, and theoretically prove that achieving true computational unlearning via differential privacy requires collapsing model utility entirely.
What Problem Does This Paper Address?
Under data privacy regulations like the GDPR's "Right to be Forgotten" and copyright takedown regimes, model owners often need to remove specific data points (the forget set) from trained models. Retraining from scratch is computationally expensive, giving rise to heuristic and certified machine unlearning methods.
However, evaluating unlearning has historically relied on optimizing proxy metrics, such as membership inference attack (MIA) scores. This leads to two critical failure modes:
- Underforgetting: The model retains residual traces of the deleted data (e.g., failing to purge planted backdoor triggers).
- Overforgetting: The model damages retain-set performance or artificially suppresses MIA scores so aggressively that its behavior no longer resembles a clean model trained without that data.
The field lacked a rigorous, formal standard to determine whether an unlearned model behaves identically to a retrained control model.
Methods
The paper introduces Computational Unlearning, formalized as a cryptographic security game:
- The Security Game: An adversary $\mathcal{A}$ selects a dataset $\mathcal{D}$ and receives the trained model $M_o$. $\mathcal{A}$ then specifies a forget set $\mathcal{D}_f$. The challenger produces two models: an unlearned model $M_u \leftarrow \text{unlearn}(M_o, \mathcal{D}_f)$ and a retrained "mirror" model $M_c \leftarrow \text{learn}(\text{init}(1^\lambda), \mathcal{D} \setminus \mathcal{D}_f)$. The challenger provides both models in random order, and $\mathcal{A}$ must guess which is which. Unlearning holds if $\mathcal{A}$ has only a negligible advantage over random guessing ($1/2 + \text{negl}(\lambda)$). The authors define both white-box (full weights) and black-box (query oracle) settings.
- Empirical Distinguishers:
MIAScore: Leveraging standard membership inference attacks. Because heuristic methods over-minimize MIA scores to near-zero, their scores are out of distribution compared to a model that genuinely never saw the data.KLDScore: A novel distinguisher measuring the Kullback-Leibler divergence between the original model and candidate models when evaluated on Gaussian-perturbed inputs around the forget set: $$\text{KLDScore}(M_o, M, \mathcal{D}, \mathcal{D}_f) = \sum_{x_i \in \mathcal{D}_f} D_{\text{KL}}\left(M(x_i + \mathcal{N}(0, 0.1)) \parallel M_o(x_i + \mathcal{N}(0, 0.1))\right)$$
The authors evaluate four prominent unlearning methods against these distinguishers: Bad Teacher, Amnesiac Unlearning, Selective Synaptic Dampening (SSD), and Certified Deep Unlearning (CDU).
Datasets
- CIFAR-10: Evaluated on a ResNet-18 architecture with varying forget set sizes (from small subsets up to full class deletion of 5,000 images).
- Poisoned CIFAR-10: Used with the BadNets backdoor attack (10% poison rate) to test whether metric closeness to the retrained model prevents backdoor retention.
- New benchmarks: No new data benchmarks were introduced; the primary contribution is the cryptographic evaluation framework.
Key Insights and Ideas
- The "Over-Optimization" Trap: A model that never encountered a data point does not have a 0% membership score; it has a baseline distribution of predictions. Because heuristic methods aggressively force forget-set loss to resemble random guesses or zero out gradients, their outputs stand out clearly against a retrained control.
- Deterministic Unlearning Cannot Exist for Entropic Learners: For randomized training algorithms (such as SGD, which has non-zero Shannon entropy), any deterministic unlearning algorithm is trivially distinguishable because the adversary can simply execute the deterministic unlearning procedure offline and match outputs.
- Differential Privacy Destroys Utility: To satisfy black-box computational unlearning using differentially private inference, the privacy budget must scale with security parameter $\lambda$ ($\epsilon \le \ln(1 + \text{negl}(\lambda))$ and $\delta \le \text{negl}(\lambda)$). This tight bound forces the output distribution of $M_o$ and $M_u$ to match a model trained on an empty dataset, collapsing utility to that of a randomly initialized network.
- Closer to the Mirror Means Safer: Closeness to the mirror model in
KLDScorestrongly correlates with actual backdoor removal (ordinary least-squares trendline $t$-value of $9.864$, $p < 0.05$).
Key Results
- Distinguishability: The adversary achieved $>60\%$ distinguishing accuracy across all evaluated forget set sizes, scaling to 100% accuracy on larger forget sets and complete class removal (5,000 images).
- Certified Deep Unlearning Breakdown: Across noise scale parameters $\sigma \in [10^{-5}, 10^{-1}]$, an adversary using
KLDScoreachieved 100% distinguishing accuracy, as unlearned model divergence scales directly with $\sigma$ while the retrained control is unaffected. - Backdoor Removal Failure: Heuristic methods that deviated heavily from the control model's
KLDScoreroutinely retained high poison sample accuracy (up to ~90%), proving that failing indistinguishability correlates directly with underforgetting.
Limitations and Future Work
- Strong Threat Model: The adversarial game assumes the adversary controls the initial training data and selects the exact forget set. Real-world adversaries are typically weaker, though any method secure under this game remains secure against weaker adversaries.
- Scope of Models: Experiments were restricted to ResNet-18 image classification on CIFAR-10.
- Open Practical Challenge: The paper proves what cannot work (deterministic unlearning on SGD, DP-based inference masking), leaving the design of practical, computationally indistinguishable unlearning algorithms for future work.
- Future Directions: Expanding the formal framework to generative and foundation models, as well as exploring relaxed game variants (e.g., allowing the defender to prune additional non-requested data).
Summary updated