CS Paper Radar

Counterfactual Certification for Sequential Unlearning with Long-Run Performance Guarantees

Hanna Benarroch, Jamal Atif, Olivier Cappé

cs.LG stat.ML ·submitted 2026-10-13 08:56 UTC · v1

Abstract

Certified machine unlearning ensures the proximity between the unlearned model and a model retrained without the data to be forgotten. Extending this framework to sequential deletion requests, typically arriving as groups of variable size (e.g., all records of one user or of coordinated users), is challenging. For unlearning methods based on fine-tuning on the retain sets, this leads to either degrading performance or increasing computation as the number of unlearning requests grows. For independent successive requests, we instead certify each model release against a counterfactual unlearning trajectory in which the group being deleted never took part. With a fixed fine-tuning budget per deletion, we show that, for smooth strongly convex objectives, this approach keeps the performance loss bounded, uniformly in the number of requests. Experiments with multiclass logistic regression on FEMNIST show that the resulting algorithm needs fewer corrective steps than existing sequential methods and outperforms training-time differential privacy, particularly when group sizes are heterogeneous.

Closest papers

Nearest neighbours by meaning across the whole index.

Error Accumulation in Second-Order Sequential Machine Unlearning

cs.LG stat.ML ·2026-11-02 ·Chen Shang, Haolin Zou, Binghe Zhu, Arian Maleki
code/data similarity 0.71
Abstract

Machine unlearning seeks to remove the influence of deleted training data without full retraining. In the sequential setting, deletion requests arrive over time, and repeated updates can accumulate approximation errors. In this paper, we study error accumulation in high dimensions, where parameter count $p$ is proportional to sample size $n$, for second-order unlearning methods under two privacy settings: (i) \emph{partial unlearning}, which allows unpublished internal states to be retained while certified versions of the model are released; and (ii) \emph{perfect unlearning}, which retains only published models and no hidden states. We also distinguish pointwise and pathwise certification, depending on whether the certification guarantee applies to each released model or the whole released sequence. We analyze conjugate gradient (CG) as an efficient solver for the inverse Hessian-vector product (IHVP) in Newton iterations. Our theory shows that a maximum of 1/2/2/3 Newton--CG updates suffice for successful certification and vanishing population-risk degradation of the published model, for pointwise partial, pathwise partial, pointwise perfect and pathwise perfect certification, respectively. Numerical experiments demonstrate accurate sequential tracking and substantial computational gains of Newton-based methods combined with conjugate gradient, over gradient-based updates, especially for ill-conditioned problems.

0.29

Minimax Gaussian Mechanisms for Continual Machine Unlearning

cs.LG stat.ML ·2026-10-08 ·Qi Kuang, Yin Xia
similarity 0.71
Abstract

Machine unlearning updates a trained model after records are deleted, aiming to match exact retraining without repeating the full training procedure. We develop Gaussian mechanisms for Newton updates under sequential deletion requests. Using Gaussian differential privacy (GDP) and its adaptive composition rule, we show that the full sequence of released models is statistically difficult to distinguish from matched exact retraining. To calibrate these mechanisms for empirical risk minimization, we derive upper bounds on the error of the Newton approximation relative to exact retraining and on how this error changes after each deletion batch. Independent Gaussian noise is calibrated using bounds on the full residual at each release, whereas Gaussian random walk noise uses smaller bounds on residual increments. These bounds yield allocations minimizing the worst-case maximum noise variance across releases under the resulting GDP certification constraints. With count-based bounds, the random walk asymptotically matches the worst-case variance of a single release at deletion cap $M$, while independent noise incurs an additional factor of order $M$. Set-based bounds can reduce the noise variances by using gradients and Hessians of the deleted records. For singleton deletion, we further show that count-based independent noise, count-based random walk noise, and set-based independent noise are minimax among fixed Gaussian covariances under their respective residual or increment bounds. With set-based bounds, allowing variances to adapt to deleted records can improve on every fixed covariance by a factor of order $(\log M)^2$ on some data sequences. The residual and noise bounds also yield parameter and predictive consistency relative to exact retraining, uniformly over deletion policies. Simulations and a credit default data analysis evaluate bounds, noise variances, and estimation errors.

0.30

Forget the Data, Keep the Capability: Switchable Unlearning for Retrieval

cs.CV ·2026-10-27 ·Jingong Chen, Kyle Gao, Guangyuan Li, Chulwoo Pack, Sijia Liu +1 more
theorycode/data similarity 0.70
Abstract

Privacy compliance requires re-identification models to selectively forget individuals while preserving their ability to recognize others. For this, we present MoME, a switchable framework that can adapt pre-trained backbones for privacy compliance, allowing the same model to switch between Full mode for standard inference and Core mode for unlearned inference. MoME splits one backbone into core parameters that preserve retrieval and zero-initialized parasitic parameters that carry the full-data knowledge, and training them under gradient isolation so the core never receives a forget-set gradient. Disabling the branch yields Core, which satisfies a request to delete a person's training data, and enabling it yields Full, which retains what the deleted data taught, so honoring the request is a flag flip rather than a retraining run. We prove Core independent of the forget set up to an audited set of coupling channels and introduce the rank-based Forgetting-Rank statistic to audit that independence in a trained model. On Market-1501, VeRi-776 and RegDB, Core reads at a retrained reference under three membership attacks while retrieving above it, and the retrieval advantage carries to ResNet and CLIP backbones. Code and weights are available at https://github.com/Jingong-Chen/MoME.

0.22

Auditable Unlearning for LLMs

cs.AI ·2026-11-04 ·Piyush Tiwary, Anushka Srivastava, Prathosh A. P
hot direction similarity 0.69
Abstract

Machine unlearning aims to remove a user's data from a trained model after a deletion request. Existing methods are majorly evaluated on three axes - how well they forget, how much capability they retain, and how robust they are to membership inference attacks, but not on whether the provider can offer the user any evidence that the deletion occurred. To fill this gap, we introduce auditability as a fourth axis, defined as the separation between requested (forget set) and retained (retain set) data under a statistic the provider computes. We show that across eleven unlearning methods on TOFU, MUSE and RWKU no method satisfies all four axes, with different methods falling short on different axes. To address this, we propose a two stage method that can be used on top of any unlearning method, in the the first stage we propose ${GapWiden}$ which uses a hinge loss to increase the difference between audit statistics of forget set and retain set. In the second stage we propose ${GapVeil}$, an inference time rejection-sampler which uses the base model as the drafter and re-samples based on the audit statistics of the drafted response. We observe that using our method, auditability and leakage reach oracle parity for every unlearning method, and forget performance converges to the oracle; retain performance improves for nine of eleven methods but remains short of parity. Our results show that evidence of deletion or auditability can be constructed by design, and that treating it as an explicit requirement changes the viability of existing unlearning methods.

0.26

Why Forget-Only Unlearning Needs Memorization

cs.LG cs.ITstat.ML ·2026-10-07 ·Luka Radić, Vikrant Singhal, Amartya Sanyal
similarity 0.69
Abstract

Machine unlearning asks for a deletion algorithm whose output is close to retraining from scratch without the selected forget examples. In this work, we study forget-only unlearning, where the deletion algorithm receives only the trained model and the examples to forget, with no retained data or extra training information. We ask whether forget-only unlearning is always possible. We first show that this depends on the learning method: different datasets can produce the same trained model but require very different outputs after the same examples are removed. Using this observation, we derive lower bounds on how accurately unlearning can match retraining and instantiate them for several standard learning algorithms. We then ask what must be true when forget-only unlearning succeeds. To this end, we derive lower bounds on what an algorithm must memorize about the training data to handle arbitrary deletion requests. For simple threshold learners, the required information can be as large as the entire dataset, even though ordinary training keeps only one boundary point. Overall, our results show that information discarded during ordinary learning may be needed later for deletion, so models designed for forget-only unlearning may need to retain more information than standard training does.

0.18

IDSISA: Influence-Distilled Sharded Training for Efficient Machine Unlearning

cs.LG cs.AI ·2026-11-04 ·Deeraj SK, Sadhana Devarajan, Tanmoy Hazra, Anupam Shukla
theory similarity 0.68
Abstract · This work has been submitted to the IEEE for possible publication. Copyright may be transferred without notice, after which this version may…

Machine unlearning removes the influence of specific training examples to comply with privacy regulations. Full retraining gives strong guarantees but is computationally prohibitive at scale; approximate methods are efficient but lack formal guarantees. SISA (Sharded, Isolated, Sliced, and Aggregated training) achieves certified deletion through data sharding and independent retraining, but random partitioning scatters forget requests across most shards, and isolated retraining degrades utility. We introduce IDSISA (Influence-Distilled SISA), which uses influence functions to concentrate forget-prone samples into few shards and distillation from unaffected shards to recover utility lost to isolation. The deletion guarantee inherited from SISA's retraining step remains exact and requires no probabilistic qualification; the distillation-based utility recovery is a separately quantified, empirically bounded approximation ($ε_{\text{cert}} \leq 0.015$ in expectation). We further formalize certification under sequences of repeated deletion requests, where cross-shard distillation can create dependencies between shards; we prove that a closure-based cascading retraining procedure restores the deletion guarantee to the full aggregated model under any deletion sequence. Experiments on ResNet-18/CIFAR-10, ResNet-18/CIFAR-100, BiLSTM/IMDB, TCN/IMDB, and a fully connected network on Fashion-MNIST show $14-91\%$ better selective forgetting, up to $50\%$ better utility retention in relative terms (with consistent percentage-point gains on the other architectures, where a relative baseline is undefined), and unlearning-time changes ranging from $-6.7\%$ to $+6.4\%$ depending on architecture, relative to SISA.

0.22

Exact Unlearning After Data Curation

cs.LG cs.AI ·2026-10-24 ·Priyank Jayraj, Devanshu sahoo, Uday Mittal
similarity 0.68
Abstract

Training pipelines often remove similar examples before fitting a model. Deleting a raw record can change that selection and admit an example that was excluded before. What must a service retain to reproduce training after such requests? We answer this question for a fixed rule in which earlier similar records block later ones. A limit on the total number of future deletions identifies exactly which records can still enter training. We use this boundary to build a summary of training statistics that can be repaired exactly after repeated deletions. The repaired summary is the same as rebuilding it on the surviving data with the remaining budget. We also construct finite-precision features for ridge regression, a linear learner with a penalty on coefficient size. With exact rational outputs, allowing one more deletion changes the required private information. It rises from zero to every private feature sign in the excluded candidates. An encoding attains this conditional private-information minimum on the constructed family throughout a sequence of requests. On 1,001 AskUbuntu development records, deleting an initially excluded record admits another record at 13 of 51 fixed similarity cutoffs. Exact membership repair passes 13,056 deletion-step checks. Two model-based semantic calibrations fail their fixed criteria, so the downstream task study is not run. The central result is a retention contract: the future deletions a service promises to support determine which excluded data can still be needed.

0.10

Confess What You Know: Forget-Set Misalignment with Model Knowledge in LLM Unlearning

cs.LG cs.AIcs.CL ·2026-09-01 ·Miso Kim, Georu Lee, Seungwon Jeong, Woojin Lee
top venue similarity 0.67
Abstract · Accepted to EMNLP 2026 (Main Conference). 22 pages, 3 figures

Machine unlearning for large language models (LLMs) often assumes that a pre-defined forget set matches what the model has memorized, but this frequently breaks in realistic privacy settings where the original training data is inaccessible. We term this gap forget-set misalignment and identify two cases. In Under Unlearning, the forget set omits memorized information and leakage persists. In Out-of-Knowledge Unlearning, the algorithm is driven to "forget" knowledge the model never learned, perturbing parameters and degrading utility. Using gradient-level analysis, we show these behaviors arise from misaligned unlearning targets rather than specific optimization choices. We then propose CONfession-to-Forget-Set (CONFS), a data-blind framework that constructs model-aligned forget sets by eliciting and formalizing the model's memorized knowledge. Across synthetic, multimodal, and real-world benchmarks, CONFS approaches Gold-standard performance on several metrics and achieves a competitive forgetting-utility balance, while preserving utility better than other data-blind forget-set constructions.

0.62