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.
Figures & tables
Figure 1: An excluded record can still control selection. Arrows show blocking by earlier raw neighbors, including excluded neighbors. There is no a,c edge. Deleting b changes the training set and can change the fitted model.
Figure 2: Identical current models, different retention needs. In this constructed K=2 instance, each candidate has four private sign bits, shown as filled squares. Crossed words cannot affect any permitted continuation. Counts give the conditional minimum private information and exclude public metadata and physical overhead.
Cutoff
Edges
Selected
Excluded
Excluded deletions with admission
.50
500,500
1
1,000
0
.84
245,841
7
994
1
.90
15,678
504
497
50
.96
197
952
49
7
.995
0
1,001
0
0
Table 1: Illustrative points from the full 51-cut grid on 1,001 development records. The last column counts initially excluded records whose singleton deletion admits at least one other record. These are fixed score graphs, not selected or semantically qualified operating thresholds.
Check
Matches / checks
Selected membership after each singleton request
13,056 / 13,056
Sequential versus batched retained state
408 / 408
Sequential versus reverse-order retained state
408 / 408
Retained state versus fresh reconstruction
408 / 408
Table 2: Exact integer repair checks over all 51 cutoffs. Counts come from the same two fixed trajectories, not independent statistical replicates. State equality compares logical coefficient maps and indices at the remaining budget.
Cutoff
Pairs
Weighted joint positive (%)
.90
330
0.01
.95
180
0.31
.98
90
9.66
.99
60
40.00
.995
30
40.00
Table 3: Version 4 semantic selection at representative frozen cutoffs. Pairs are sampled canonical pairs with score strictly above the cutoff. Joint proportions use inclusion weights; the selection requirement is 95%.
Machine unlearning removes the influence of selected data or concepts from trained models while preserving useful behavior and avoiding full retraining.
Machine unlearning aims to remove specific data points from a trained model, often striving to emulate "perfect retraining", i.e., producing the model that would have been obtained had the deleted data never been included. We demonstrate that this approach, and security definitions that enable it, carry significant privacy risks for the remaining (undeleted) data points. We present a reconstruction attack showing that for certain tasks, which can be computed securely without deletions, a mechanism adhering to perfect retraining allows an adversary controlling merely ω(1) data points to reconstruct almost the entire dataset merely by issuing deletion requests. We survey existing definitions for machine unlearning, showing they are either susceptible to such attacks or too restrictive to support basic functionalities like exact summation. To address this problem, we propose a new security definition that specifically safeguards undeleted data against leakage caused by the deletion of other points. We show that our definition permits several essential functionalities, such as bulletin boards, summations, and statistical learning.
Aloni Cohen, Refael Kohen, Kobbi Nissim +1
University of Chicago · Tel Aviv University · Dept. of Computer Science, Georgetown University
Exact unlearning requires a deployed predictor to match one rebuilt without the information named by a deletion request. Existing general-purpose exact methods localize retraining through disjoint shards, but every request still invalidates a model, and smaller shards reduce the data available to each constituent predictor. We introduce Quantized Sufficient Statistics (QSS), which separates a small frozen schema from mutable, sum-decomposable content. The schema learns global structure; the content stores local prediction corrections as additive statistics indexed by quantized regions. Deleting content is therefore exact subtraction rather than optimization. We distinguish two guarantees: QSS-L exactly removes a label while retaining the unlabelled input, whereas QSS-E exactly removes both input and label by learning the schema without deletable examples. A deletion takes the arithmetic fast path with probability 1−ρ and triggers a full rebuild with probability ρ; all reported expected latencies include both events. Across 15 vision, text, and tabular datasets at ρ=0.5%, QSS-L is within 2 percentage points of SISA on 11 tasks and provides 4--483× lower expected deletion latency on the low-class-count tasks where a compact schema is effective. QSS-E quantifies the additional accuracy cost of removing every trace of an input.
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.
Luka Radić, Vikrant Singhal, Amartya Sanyal
Department of Computer Science, University of Copenhagen