A taxonomy of machine unlearning
This file fixes the vocabulary the literature review uses, and the three axes it organises
methods along. It is written before the review so that terms stay consistent across
timeline.md, gaps.md, LITERATURE_REVIEW.md and the Stage 4 method specifications.
Two of the three axes are borrowed with attribution; the third is this project's own. Every definition below is traceable to a section of a paper we have read. Where a paper is silent, this file says so rather than filling the gap.
Scope note. This taxonomy covers image classifiers, which is the project's track. Nothing here is claimed for language models, graphs, federated settings or generative models, and no paper from those areas is in the corpus.
1. Vocabulary
1.1 The three sets, and the oracle
Fix a training set \mathcal{D} and a subset \mathcal{D}_f \subset \mathcal{D} to be forgotten. Write \mathcal{D}_r = \mathcal{D} \setminus \mathcal{D}_f for the retain set. Three models recur throughout:
| Symbol | Name | Definition |
|---|---|---|
| w^o | original | the model trained on all of \mathcal{D} |
| w^u | unlearned | the output of an unlearning procedure applied to w^o |
| w^r | oracle / retrain-from-scratch | a model trained on \mathcal{D}_r alone |
The oracle is the reference point almost every empirical paper measures against, and §1.2 and §6 below are largely about how contested that choice has become.
Two forget-set shapes recur and are not interchangeable. Class unlearning removes every example of one class; selective (or random-subset) unlearning removes a scattered subset, sometimes drawn from within a single class. The distinction is load-bearing for method applicability: Tarun et al. 2024 states that "unlearning random samples, or only a subset of a class, is out of the scope of this paper", which excludes it from both of this project's phases.
1.2 Exact, approximate, certified
These three words are used loosely in the literature and this project uses them narrowly.
Exact unlearning produces a model that is, by construction, one that could have been produced without \mathcal{D}_f. Bourtoule et al. 2021 achieves it architecturally by sharding, slicing and checkpointing so that a deletion request only forces retraining of one slice of one shard.
Approximate unlearning produces a model that is close to what retraining would have given, under some notion of closeness. The notion varies, and the variation matters more than the shared label suggests.
Certified unlearning attaches a formal, differential-privacy-style guarantee. Guo et al. 2020 defines (\varepsilon,\delta)-certified removal by bounding the max-divergence between the mechanism's output distribution and that of retraining, and Sekhari et al. 2021 Definition 2 states an (\varepsilon,\delta)-unlearning condition explicitly "motivated by the definition of differential privacy".
A lineage correction the review must get right
It is common to cite Ginart et al. 2019 as the source of an (\varepsilon,\delta)-approximate definition. It is not. Definition 3.1 requires equality in distribution, A(D_{-i}) =_d R_A(D, A(D), i), and the paper says it is focusing on "exact data deletion"; the approximate relaxation is deferred to an appendix we have not read. Ginart's contribution is to compare distributions over models rather than deterministic outputs — a real advance on Cao et al. 2015, but a different thing from being approximate.
The correct lineage is: Cao et al. 2015 (deterministic output equality) → Ginart et al. 2019 (exact, distributional) → Guo et al. 2020 (genuinely (\varepsilon,\delta)) → Sekhari et al. 2021 and Neel et al. 2021 (DP-style, with deletion capacity and update sequences).
Guo et al. 2020 gives the cleanest one-line placement of the whole certified line: the subject is "the trade-off between utility and removal efficiency, with re-training from scratch and differential privacy at the two ends of the spectrum, and removal in the middle."
1.3 Deletion is not privacy
The sharpest statement of this in the corpus is Ginart et al. 2019's: cryptography and differential privacy "do not lead to efficient data deletion, but rather attempt to make data private or non-identifiable … Even an operation that outputs the entire dataset in the clear could support data deletion, whereas such an operation is certainly not private. In this sense, the challenge of data deletion only arises in the presence of computational limitations."
Two later results complicate the picture in opposite directions. Sekhari et al. 2021 Lemma 1 shows a sufficiently private algorithm unlearns for free — ignore the deletion request entirely — but their Theorem 2 establishes a strict \Theta(d^{1/4}) separation in deletion capacity, so privacy is a sufficient and wasteful route rather than the right one. And Chen et al. 2021 shows the converse hazard: because unlearning produces two models, the discrepancy between them is itself a leak, so deletion performed without regard to privacy can be actively harmful rather than merely unambitious.
2. Axis A — what is unlearned, and where success is measured
Adopted from Thudi et al. 2022a Figure 1, which classifies prior post-hoc approximate unlearning on two sub-axes.
Citation-key warning. Kurmanji et al. 2023 cites this paper as Thudi et al. 2022a and the forging paper Thudi et al. 2022b as 2022b. Same first author, same year, adjacent topics — swapping them would misattribute the forging result.
| Sub-axis | Values |
|---|---|
| What is being unlearned? | logits · weights · distribution of weights |
| How is success measured? | output space: test accuracy, membership inference, logits — weight space: weights, distribution of weights |
The grid is useful because the diagonal is not forced. A method can target weights while being measured in output space, which is exactly what most vision papers do.
Three independent results say the weight-space column is the weaker one, and the review presents them together because no single paper does:
- Not sufficient. Goel et al. 2022 Theorem 1 shows weight proximity to a retrained model does not imply the forget set's influence is gone.
- Not necessary. The same paper observes a randomly initialised network contains no forget-set information yet is far from the retrained model in weight space.
- Not verifiable. Thudi et al. 2022b Theorem 1 and Corollary 2 show that for minibatch SGD, unlearning "is not well-defined over the logs (and thus the models) of finite datasets", because a forging map lets an owner rewrite the training log so the same trajectory is explained by a dataset not containing the forgotten point. Their conclusion: unlearning "cannot be defined on the parameter space", and must be defined and verified at the level of the process, not the artifact.
Xu et al. 2025 pushes the same conclusion into a positive proposal, arguing the anchor-based principle is inauditable because it depends on an unknown retrained anchor in parameter space, and replacing it with a criterion stated purely in output space.
Where this project sits. Our provenance apparatus — config hash, git SHA, split hash, seed and library versions recorded per run — is process-level verification in Thudi et al. 2022b's sense, though it was built for reproducibility rather than for auditing. That connection is worth stating in the review; it was not the design intent.
3. Axis B — algorithm shape: erase, then repair
Adopted from Triantafillou et al. 2024 §5, which observes that most competition submissions decompose into
"an 'erase' phase, aiming to remove the influence of the forget set, followed by a 'repair' phase, aiming to repair any excess damage to the utility of the model that is caused by imperfect erasing."
Erase mechanisms seen across the corpus and the competition submissions:
| Erase mechanism | Instances |
|---|---|
| gradient ascent on the forget set | NegGrad, and the saliency-defining step of Fan et al. 2024 |
| relabelling the forget set and fine-tuning on it | Random Label; Graves et al. 2021's "Unlearning" variant; the base of Fan et al. 2024 |
| pushing forget predictions toward a bad or uniform target | Chundawat et al. 2023's incompetent teacher |
| pushing forget predictions away from the original model | Kurmanji et al. 2023's MAX steps |
| perturbing or dampening selected parameters | Golatkar et al. 2020a's Fisher noise; Foster et al. 2024's dampening |
| a closed-form jump in weight space | Golatkar et al. 2020b's NTK one-shot forgetting |
| corrupting with error-maximising noise | Tarun et al. 2024's IMPAIR step |
Repair is far less varied: essentially all of it is cross-entropy or distillation on the retain set — Kurmanji et al. 2023's MIN steps, Tarun et al. 2024's REPAIR epoch, the retain-set term in Fan et al. 2024 Equation 6, and plain fine-tuning.
The authors' own caveat, which the review must carry. Their footnote 7: "unlearning phases cannot always be neatly categorized as one of the two: for instance, finetuning on the retain set still has an indirect erasing effect on the forget set due to catastrophic forgetting." So this axis describes intent, not a partition of effects. That is precisely why Graves et al. 2021's "Naive Retraining" — continuing training on \mathcal{D}\setminus S and relying on catastrophic interference — is a pure-repair method that nonetheless erases.
4. Axis C — access and cost
This axis is ours. It asks what an unlearning procedure is permitted to touch and what it costs, and it is the axis that actually does work: it is what excludes SISA and the SD loss from Stage 7, and what places the theory papers' bounds outside the class SCRUB belongs to.
Five sub-dimensions:
C1. Forget-set access. Full samples, labels only, or none. Tarun et al. 2024 is explicitly zero-glance: it never looks at the forget samples, only the forget class label plus a small retain subset. Sekhari et al. 2021's unlearner does receive U, and the authors name the paradox — "storing and using information in order to delete it" — in their title.
C2. Retain-set access at unlearning time. Foster et al. 2024 is the notable case: its selection step uses a precomputed Fisher diagonal over the full dataset, so it needs no retain set at unlearning time at all. The paper's prose says \mathcal{D}_r but Equation 4 and Algorithm 1 use \mathcal{D}, and the authors justify the substitution on the grounds that [\;]_{\mathcal{D}_r} "must be recalculated for every new forget request."
C3. Intervention point: post-hoc or training-time. A post-hoc method applies to a frozen, already-trained model. A training-time method changes how the original is trained, and therefore cannot be applied to an existing model. Bourtoule et al. 2021 is training-time by construction; so is Thudi et al. 2022a's SD loss; so is Graves et al. 2021's batch-subtraction variant, which requires per-batch updates to have been logged during training. This distinction is why this project drops all three from Stage 7 — not on quality grounds but on structural ones.
C4. Storage beyond the final model. Sekhari et al. 2021 makes this a first-class constraint: the unlearner may use statistics T(S) but not S, "aiming for memory requirements which are independent of the training data size n", which they note "precludes strategies which involve storing and reusing the entire training set, or aggressive model checkpointing." That sentence excludes SISA and Amnesiac by construction. Regehr et al. 2026 drops this constraint, granting full storage — which is why the two papers' rates are not directly comparable and the review must not present them as though they were.
C5. Behaviour under a sequence of requests. Most vision methods are specified and evaluated for a single deletion request. Neel et al. 2021 treats an ongoing sequence of additions and deletions as the object of study, distinguishing strong from weak unlearning by how cost scales with the number of requests handled. Guo et al. 2020 shows the accumulated gradient-residual bound grows linearly in the number of removals T and quadratically in batch size m (Theorem 4), so their Algorithm 2 carries an explicit fallback: when the budget is exhausted, retrain. Certified removal is therefore a depleting budget, not an unbounded capability — the algorithmic counterpart of Sekhari et al. 2021's deletion capacity. Ginart et al. 2019 Remark 3.1 gives the matching complexity statement: an \Omega(n/m) amortised lower bound for m deletion requests in the online setting.
5. The corpus placed on all three axes
Rows are the methods this project could in principle run. A cell reading not established means the sections we read do not settle it — it is a statement about our reading, not about the paper.
| Method | Axis A: target | Axis B: shape | C1 forget access | C2 retain at unlearn | C3 point |
|---|---|---|---|---|---|
| Retrain oracle | — | — | none | full | post-hoc |
| Finetune on \mathcal{D}_r | weights | repair only | none | full | post-hoc |
| NegGrad+ Kurmanji et al. 2023 Eq. 4 | weights | erase + repair | samples | full | post-hoc |
| CF-k / EU-k Goel et al. 2022 | weights (last block) | repair only | none | full | post-hoc |
| Fisher Golatkar et al. 2020a | distribution of weights | erase | see note | required | post-hoc |
| NTK Golatkar et al. 2020b | weights | erase (closed form) | samples and labels | required | post-hoc |
| SCRUB Kurmanji et al. 2023 | logits | erase + repair, alternating | samples | full | post-hoc |
| Bad-T Chundawat et al. 2023 | logits | erase + repair | samples | subset (see note) | post-hoc |
| SSD Foster et al. 2024 | weights | erase only | samples | none | post-hoc |
| SalUn Fan et al. 2024 | weights (masked) | erase + repair | samples | full | post-hoc |
| \ell_1-sparse Jia et al. 2023 | weights | repair with penalty | depends on L_u | full | post-hoc |
| Amnesiac-relabel Graves et al. 2021 | logits | erase | samples and labels | full | post-hoc |
| UNSIR Tarun et al. 2024 | weights | erase + repair | label only | subset | post-hoc |
| SISA Bourtoule et al. 2021 | — (exact) | — | none | shard data | training-time |
| SD loss Thudi et al. 2022a | weights | — | samples | none | training-time |
The rows above the SISA line are the nine baselines and methods Kurmanji et al. 2023 appendix §9 actually specifies, plus the two Priority 2 additions (Foster et al. 2024, Fan et al. 2024, Jia et al. 2023, Graves et al. 2021) and UNSIR. Note there is no plain "NegGrad" row: SCRUB's baseline set is Original, Retrain, Finetune, NegGrad+, CF-k, EU-k, Fisher, NTK and Bad-T. Gradient ascent alone appears in the literature as a mechanism (Axis B, §3 above) but not as a SCRUB baseline.
Note on the Bad-T row. Chundawat et al. 2023 specifies "a small subset of
\mathcal{D}_r"; Kurmanji et al. 2023 appendix §9 reproduces it with the whole retain
set, having "empirically observed that using only 30% of retain-set for Bad-T yields high
test errors", and at KL temperature 4 rather than the original's 1. Both deviations are
recorded for docs/specs/bad_teacher.md; the reproduction follows SCRUB, because SCRUB is
what is being reproduced.
Note on the Fisher row. Golatkar et al. 2020a's derived scrubbing function involves
both \nabla^2 L_\mathcal{D} and \nabla^2 L_{\mathcal{D}_r}, so the theory requires
both sets. Which dataset the implemented Fisher diagonal is computed over is recorded as
open ambiguity F2 in ambiguities.yaml and is not resolved here. Foster et al. 2024
deliberately differs from Golatkar on exactly this point, which is why the shared Fisher
utility in Stage 7 must take the dataset as an argument rather than hard-coding it.
6. Why the axes are orthogonal, and why that matters
The three axes cross-cut, and the review's method section is organised around the claim that they are independent rather than three views of one ordering.
- Axis A is about what is measured; Axis B about what the algorithm does. SCRUB and Bad-T sit at the same point on A (logits) and at opposite points within B: Bad-T minimises a KL toward a bad target while SCRUB maximises a KL away from the single teacher.
- Axis C is independent of both. SSD and Fisher share a mechanism (diagonal Fisher information) and a position on A, but differ on C2 — SSD needs no retain set at unlearning time, Fisher does.
- The theory papers occupy positions on C that no vision method does. Nothing in the vision literature bounds its storage the way Sekhari et al. 2021 does, and nothing reports behaviour over a request stream the way Neel et al. 2021 analyses.
The sharpest instance is Van Waerebeke et al. 2025. Its unlearners are defined with a signature taking both sets, but the class it minimises over may only sample \mathcal{D}_r — the unlearner runs the learning algorithm's own iterates on the retain set starting from \boldsymbol\theta^\star. Every method in the table above that this project will actually run sits outside that class, because every one of them touches \mathcal{D}_f. The paper is also in a different currency: it bounds computation time to a target excess risk via the unlearning complexity ratio T^U_e/T^S_e, and forget quality — forget error, MIA advantage — has no counterpart in it at all.
That is the taxonomy's payoff, and it feeds §5 of the review directly: the two literatures are not on the same grid. The theory line constrains C1, C4 and C5 and assumes convexity; the vision line ignores C4 and C5 entirely, takes C1 for granted, and works on non-convex networks. A bound proved over a class of unlearners that no vision method belongs to is not a bound about those methods — which is a statement about scope, not about correctness.
7. Prehistory: Ginart's four design principles
Worth recording because Ginart et al. 2019 §3.1 maps most of what followed, from the field's second paper.
| Principle | Their idea | Where it reappears |
|---|---|---|
| Linearity | "linear computation allows for simple post-processing to undo the influence of a single datapoint" | the influence-function line: Guo et al. 2020, Sekhari et al. 2021, Izzo et al. 2021, Golatkar et al. 2020a |
| Laziness | "delay computation until inference time, resulting in trivial deletions", e.g. k-NN | not pursued in the deep-network literature |
| Modularity | restricting computation state to specific partitions of the data | this is SISA, two years early: Bourtoule et al. 2021 |
| Quantization | "small changes to the dataset should result in small changes to the (distribution over the) model … known as stability" | the assumption Golatkar et al. 2020a relies on and Kurmanji et al. 2023 attacks |
The unpursued row is as informative as the others. Laziness has no deep-network descendant in this corpus, which is a fact about what the field chose rather than about what is possible.
8. What this taxonomy deliberately does not do
- It does not rank methods. Nothing has been reproduced. No cell above is a quality
judgement, and the only experimental numbers this project holds are SCRUB Table 7 and Jia
Table 2 (see
VERIFICATION_REPORT.md). - It does not resolve the evaluation question. How to measure unlearning is treated separately, in §7 of the review, because the critiques (Carlini et al. 2022, Hayes et al. 2024, Chen et al. 2021, Thudi et al. 2022b, Triantafillou et al. 2024) attack the measurement rather than the taxonomy.
- It does not include a method-capability matrix. That is deliberately deferred to Stage 7, where it can be generated from the implemented interface rather than asserted here and allowed to drift.
- It does not organise itself around the survey. Nguyen et al. 2025 is in the corpus and offers its own taxonomies, but the axes above were derived from primary sources so that each is traceable to a section this project has read. The survey is cited in the review where it is the appropriate authority, not used as the organising frame.