# Exact Unlearning

Removing a record's influence so completely that the result is indistinguishable from having never trained on it.

**Rests on:** Utility Preservation

**Leads to:** Unlearning Verification

*Machine Learning · Machine Unlearning*


## Why learn this

Exact unlearning is the standard for true privacy in machine learning. Learning it gives you a clear benchmark: if a model can be proven to have no memory of specific data, that is the highest level of trust you can offer. It underpins methods like approximate unlearning and supports legal demands such as the 'Right to Be Forgotten'. Concretely, you will learn how to build systems that can completely erase a user's data contribution—a capability that is becoming a legal requirement in many places and essential for maintaining public trust. For example, if a company must delete one customer's file from a dataset of 10,000 files, exact unlearning ensures that customer's information is gone entirely, not just hidden.


## The intuition

Imagine a teacher who has taught a class for a year. On the last day, a student asks to be removed from the attendance record. The teacher has two choices: (a) go back and re-teach the entire year as if that student had never existed—which is very slow but gives a perfect result—or (b) just cross the student's name off the attendance sheet, which is fast but leaves traces: other students remember them, the seating chart has an empty space, and the teacher's memory of the class is slightly different. Exact unlearning is like option (a) for machine learning models: it removes the data's influence so completely that the model behaves exactly as if the data had never been in the training set. The catch is that retraining from scratch is expensive. So the real skill is to structure your training from the start so that when a deletion request comes, you only need to retrain a tiny part, not the whole model. For instance, if you split 10,000 training images into ten groups of 1,000, and one user's 100 images belong to group three, you only need to retrain the model for group three, saving 90% of the work.


## An analogy

Think of a library that loans out books. Every day, the librarian reads a new book and writes a summary in a master notebook. The notebook is filled with summaries, each influenced by the books read so far. One day, a patron returns a book that was never actually checked out—the system says it was, but the patron denies it. The librarian must ensure the notebook no longer reflects that book's content. The only way to be truly exact is to rewrite the notebook from scratch, without using that book—but that means re-reading every other book, which is slow. A better approach is to use a separate notebook for each subject. When a book on 'gardening' is called into question, the librarian only rewrites the gardening notebook, using the books in that subject, and leaves the cooking and astronomy notebooks untouched. This is exactly what splitting data into independent training sets does: it isolates the data so that deleting one record requires updating only one small part of the system, not the whole model. The analogy holds because both the library and the model can achieve exact removal by limiting the scope of the retraining. Where it breaks down: in the library, the notebooks are independent summaries; in a neural network, the layers and weights are not independent—the model's behavior is a complex function of all the data, so separating the influence is harder. But the principle of partitioning to bound the cost is the same.


## Definition

Exact unlearning is the process of removing a specific training record's influence from a model so completely that the resulting model is identical to one trained without that record, leaving no detectable trace of its presence.


## How it connects

You have studied approximate unlearning, which reduces a record's influence by adjusting weights but cannot give absolute guarantees. Exact unlearning is the gold standard—it gives you a guarantee, but it usually relies on splitting data into independent groups to be affordable. This concept connects directly to the Right to Be Forgotten: deletion obligations, as your notes say, extend to trained model weights, not just databases. Exact unlearning is the technical answer to that legal requirement. It also contrasts with methods where data never leaves the client, where it is much harder to isolate which update caused which influence.


## The mathematics

This concept rests on the branch of mathematics called set theory and probability, but the core operation is simple arithmetic—counting and comparing. The key idea is that we need to compute what the model would have learned if a particular data point had never been seen. To do that, we first define a training dataset as a collection of examples. For exact unlearning, we need to compare two models: one trained on the full dataset, and one trained on the dataset minus one example. The guarantee is that these two models are identical in their outputs for every possible input—not just for the deleted example, but for all inputs. In practice, we achieve this by partitioning the dataset into disjoint subsets (shards), training a separate model on each shard, and then combining their predictions. When we delete a record from one shard, we retrain that shard's model from scratch (using its remaining records). The overall model's behavior is then the same as if the full dataset (without the deleted record) had been used from the start—because the shard model is trained independently and exactly. The mathematics is about ensuring the combination of sharded models is equivalent to the unsharded model for all inputs—a property that holds by construction if each record is in exactly one shard and the combination rule (e.g., averaging) is fixed and independent of the data.

Let the training set be D, split into S shards D_1, D_2, ..., D_S. The model is an aggregation function F of the per-shard models M_i = train(D_i). For a deletion request for records in D_j, the new model is F(M_1, ..., M_j', ..., M_S) where M_j' = train(D_j \ {r}). Exact unlearning holds iff for all inputs x, F(M_1, ..., M_j', ...)(x) = train(D \ {r})(x). For the simple average model, F is the weighted mean: F(M_1,...) = sum_i |D_i| * M_i / sum_i |D_i|.


## A worked example

```
Suppose we have a tiny dataset of 6 records, each with a single feature x and a label y. We want to train a model that predicts y from x. We'll use a simple model: the average of y for each x (like a lookup table). The records are: (x=1, y=2), (x=2, y=4), (x=3, y=6), (x=4, y=8), (x=5, y=10), (x=6, y=12). We want to delete the record (x=3, y=6).

Step 1: Full dataset: y values = [2,4,6,8,10,12], average = (2+4+6+8+10+12)/6 = 42/6 = 7   # This is the model trained on all six records—it predicts y=7 for any input (since it's just the average).
Step 2: Dataset without the record: y values = [2,4,8,10,12], count = 5, sum = 36, average = 36/5 = 7.2   # This is the model trained on the dataset with the record (x=3,y=6) removed.
Step 3: Exact unlearning requires that the model after deletion gives the same predictions as the model trained from scratch without that record, for all inputs.   # Here, the average changes from 7 to 7.2, so the model must output 7.2 for any input, not 7.
Step 4: Now use sharding: split the dataset into two shards. Shard A gets records (x=1,y=2), (x=2,y=4), (x=3,y=6); Shard B gets (x=4,y=8), (x=5,y=10), (x=6,y=12). Train a separate average on each shard: A_avg = (2+4+6)/3 = 4, B_avg = (8+10+12)/3 = 10.   # The overall model is the average of the two shard models: (4+10)/2 = 7, matching the full dataset average.
Step 5: Delete the record (x=3,y=6) from shard A. Retrain shard A on its remaining records: (x=1,y=2), (x=2,y=4). New A_avg = (2+4)/2 = 3. Shard B remains unchanged: B_avg = 10.   # The overall model becomes (3+10)/2 = 6.5, which is different from the required 7.2. So this simple averaging combination is NOT exact—because the combination rule is sensitive to the number of records in each shard.
Step 6: To achieve exactness, we must adjust the combination rule: instead of plain averaging, we use a weighted average where each shard's contribution is proportional to the number of records it has. Before deletion: A has 3 records, B has 3. Weighted average = (3*4 + 3*10)/6 = (12+30)/6 = 7. After deletion: A has 2 records, B has 3. Weighted average = (2*3 + 3*10)/5 = (6+30)/5 = 36/5 = 7.2. This matches the retrained model.   # By using weights based on shard sizes, the combination rule adapts to the deletion, making the overall model identical to a model trained on the full dataset minus the record.

Result: Exact unlearning is achieved when the combination rule (like weighted averaging) is chosen so that deleting a record and retraining the affected shard yields the same overall model as retraining the entire dataset without the record. In this example, the weighted average gives 7.2, matching the retrained model. This illustrates the principle: sharding works only if the aggregation rule compensates for the changed shard sizes.
```


## From scratch, in Python

```python
# No frameworks, just plain Python.
# We're building a tiny dataset and a model that predicts the average of y for any x.

# Step 1: Define the training data as a list of (x, y) pairs.
# A list is an ordered, changeable collection. Here each element is a tuple (x, y).
data = [(1, 2), (2, 4), (3, 6), (4, 8), (5, 10), (6, 12)]

# Step 2: Define a function that trains a model on a list of records.
# A function is a block of reusable code. This one takes a list of records and returns the average y.
def train_average(records):
    # Sum all the y values using a loop.
    total = 0  # Start with zero.
    count = 0  # Count how many records we have.
    for x, y in records:  # For each record, unpack the tuple into x and y.
        total = total + y
        count = count + 1
    return total / count  # The average.

# Step 3: Define the aggregation function that combines per-shard models.
def combine(shard_models, shard_sizes):
    # Weighted average: each model's contribution is proportional to its shard's size.
    total_weighted = 0
    total_size = 0
    for model, size in zip(shard_models, shard_sizes):
        total_weighted = total_weighted + model * size
        total_size = total_size + size
    return total_weighted / total_size

# Step 4: Split data into two shards (using list slicing).
shard_A = data[:3]  # First three records: [(1,2), (2,4), (3,6)]
shard_B = data[3:]  # Last three records: [(4,8), (5,10), (6,12)]

# Step 5: Train models on each shard.
model_A = train_average(shard_A)
model_B = train_average(shard_B)
print('Before deletion: A_avg =', model_A, ' B_avg =', model_B)
print('Combined (weighted) =', combine([model_A, model_B], [len(shard_A), len(shard_B)]))
# Should print 7 (the overall average).

# Step 6: Delete the record (3, 6) from shard_A.
# We'll remove it by building a new list that excludes that particular record.
shard_A_remaining = [record for record in shard_A if record != (3, 6)]

# Step 7: Retrain shard A.
model_A_new = train_average(shard_A_remaining)
# Shard B stays the same.

# Step 8: Combine again with updated shard sizes.
shard_sizes = [len(shard_A_remaining), len(shard_B)]
combined_new = combine([model_A_new, model_B], shard_sizes)
print('After deletion: A_avg_new =', model_A_new, ' B_avg =', model_B)
print('Combined (weighted) =', combined_new)
# Should print 7.2, same as training on all data minus the record.

```


## The same thing, with a framework

```python
In practice, you would use a library like PyTorch or scikit-learn. Here's the same idea with a simple neural network (using PyTorch) and a manual per-shard retraining. Note: the framework doesn't provide a ready-made 'exact unlearning' function—you have to implement the sharding and aggregation logic yourself.
```


## What the code does

The code starts by defining a list of tuples, where each tuple is a training record (x, y). We define two functions: `train_average` computes the average of y for a list of records using a loop over the list; `combine` takes a list of models (each a single number, the average) and their shard sizes, and computes a weighted average. We split the data into two shards using list slicing: `data[:3]` gives the first three records, `data[3:]` the last three. We train each shard's model and combine them, getting 7. To delete a record, we use a list comprehension to create a new list excluding the record `(3,6)`. We retrain shard A on this new list, keep shard B unchanged, and recompute the weighted average with updated sizes. The result matches the expected 7.2. The key point is that the combination function must use the shard sizes as weights; otherwise the combined model would not match the retrained full model.


## Common misconceptions

**Exact unlearning means the model forgets the data point completely.** — If I delete a record, the model should have no memory of it at all—like it never saw it.

The model's behavior is a function of all training data, so even after 'forgetting', the model may still produce outputs that correlate with the deleted point (e.g., if another similar record exists). Exact unlearning means the model's predictions are the same as if the point was never in the dataset—not that the model has no information that could be used to guess it. In fact: Exact unlearning guarantees indistinguishability from a model trained without the record, not absolute ignorance. The model may accidentally 'remember' through correlations with other data.

**Exact unlearning is always the best choice.** — If exact unlearning is possible, why would anyone use approximate methods?

Exact unlearning often requires expensive retraining or a special architecture (like sharding) that may hurt model accuracy. Approximate methods are faster and can be good enough in practice, especially when the deleted records are low-risk. In fact: Exact unlearning offers a guarantee but at a cost. Approximate methods trade some guarantee for efficiency, and are often preferred when resources are limited or the data sensitivity is low.

**Sharding always gives exact unlearning for free.** — If I split the data into shards and train separate models, deleting a record only requires retraining that shard, so I get exact unlearning automatically.

As shown in the numerical example, the aggregation rule must be chosen carefully. If you use a simple average without weighting by shard size, the combined model after deletion will not match the full retrained model. Also, the model type must be such that the aggregation rule preserves the exact function. In fact: Sharding only gives exact unlearning if the aggregation rule compensates for changed shard sizes and the per-shard models are trained independently and exactly. This is the SISA approach.


## In short

Exact unlearning means removing a record's influence so completely that the model is indistinguishable from one trained without it. The key to making it affordable is structuring training in advance—via SISA-style sharding—so each record only affects a small part of the model. Then a deletion request only requires retraining that shard. The challenge is ensuring the aggregation of shard models exactly matches the full model's behavior. This is the gold standard against which all approximate methods are measured, and it is essential for legal compliance and user trust.


## Where this is used

Exact unlearning is used in any application where a deletion request must be provably honoured, not just approximately. In large language models, removing a user's identity from training data is nearly impossible after training, but if the training were structured with sharding from the start, one could retrain only the shard that contained the record. This is not common in practice for LLMs due to the enormous scale, but it is the benchmark against which approximate methods are judged. In small models running on devices (e.g., on-device keyword spotters), sharding is feasible because the data volume is smaller. For retrieval-augmented generation, exact unlearning applies to the embedding model: if a document is deleted, you must remove its influence from the index and, ideally, from the embedding model's weights—but the latter is hard. Agentic systems that plan and call tools often rely on models trained on user-specific data; a deletion request would require retraining the agent's policy network, but sharding across users makes this tractable: each user's data goes into a separate shard, and deleting a user only retrains that shard. In everyday applied machine learning—recommendation systems, fraud detection, forecasting—exact unlearning is used to comply with regulations like GDPR. A developer would implement it by partitioning data into shards, training a model per shard (e.g., a separate model for each month's data), and using a model-agnostic aggregation (e.g., weighted averaging for regression, majority voting for classification). When a deletion request arrives, they retrain only the shard(s) containing the record, and re-aggregate. The main practical challenge is that the aggregation rule must be chosen so that the overall model's performance is preserved—for many models (like deep nets) this is non-trivial, so exact unlearning often forces a simpler model or a more structured design.


---

Read this on the web: https://basavapurushottam.com/learn-ai/exact-unlearning
