What makes unlearning hard and what to do about it

1 Introduction

• Deep networks are nonconvex, making it difficult to trace how a subset of training data affects model weights and thus to remove its influence after training.This difficulty raises concerns about harmful or outdated information and user privacy in systems that reuse trained models.Source: §1 · p. 1
• Understanding which requests are difficult may help select an unlearning method or indicate when retraining from scratch is preferable to approximate unlearning.The paper also identifies better evaluation protocols as a potential benefit of understanding factors that affect difficulty.Source: §1 · p. 2
• Unlearning becomes harder as retain and forget sets are more entangled and as forget-set examples are more memorized.The investigation also finds that algorithms suffer differently as difficulty increases, revealing behaviors and failure modes not seen with random forget sets.Source: §1 · p. 2
• RUM refines the forget set into homogeneous subsets and uses existing algorithms to unlearn each subset before composing the result.The paper reports that RUM boosts several state-of-the-art algorithms and addresses issues uncovered by its difficulty analysis.Source: §1 · p. 2

2.1 Unlearning problem formulation

• The forget set is the selected training-data subset to remove, and its complement is the retain set.The unlearning algorithm uses the original model, forget set, and retain set to produce an unlearned model.Source: §2.1 · p. 2
• An ideal unlearning algorithm produces a model-weight distribution matching retraining on the training data with the forget set excluded, while being more computationally efficient to be practical.Exact unlearning sets ε = δ = 0; for neural networks, the known exact approaches involve retraining and can be inefficient, whereas approximate methods are generally more efficient but lack known tight bounds.Source: §2.1 · p. 2
• Empirical evaluation considers forgetting quality, utility, and efficiency, using forget-set accuracy or membership-inference attacks as forgetting proxies.Utility can be measured by retain- and test-set accuracy, and efficiency by time; the paper uses both forgetting proxies in its experiments.Source: §2.1 · pp. 2–3

2.2 Memorization

• An example's memorization score measures how its prediction probability differs between models trained with and without that example.Prior work identifies atypical or outlier examples as more highly memorized; noisy or incorrect labels may require memorization for correct prediction.Source: §2.2 · p. 3

3 Related Work

• Post-training methods include fine-tuning on retained data, gradient ascent on the forget set, combined retain-loss minimization and forget-loss maximization, and influence-based weight estimation.SCRUB uses a student-teacher objective, while L1-sparse adds an L1 penalty during retain-set fine-tuning.Source: §3 · p. 3
• Relabelling-based methods train on new labels for forget-set features, and SalUn optimizes that relabelled data using salient model parameters.The described approach treats model weights as salient or intact with respect to the forget set.Source: §3 · pp. 3–4
• Unlike adversarial benchmark work that constructs worst-case forget sets through bilevel optimization, this paper studies interpretable factors to understand algorithm behavior and improve pipelines.The factors are retain–forget entanglement and memorization.Source: §3 · p. 4
• Prior work links noisy labels to more forgetting events during training and finds that differentially private models have difficulty predicting atypical examples; this paper studies after-the-fact unlearning instead.The paper connects this line of work to memorization, which it describes as closely related to data-distribution atypicality.Source: §3 · p. 4

4 What Makes Unlearning Hard?

• ToW scores an unlearned model by how closely its accuracies on the forget, retain, and test sets match retraining from scratch; higher scores indicate better unlearning.The score uses the product of the three accuracy-match terms.Source: §4 · p. 4

4.1 The more entangled the forget and retain sets are, the harder unlearning becomes

• Higher embedding-space entanglement makes unlearning harder for all tested algorithms, with relabelling methods performing especially poorly at high entanglement.The authors hypothesize that relabelling a forgotten example can also harm nearby retained examples.Source: Figure 1 · p. 5, §4.1 · p. 5

4.2 The more memorized the forget examples are, the harder unlearning becomes

• For most algorithms, lower memorization makes unlearning easier, but SalUn and Random-label show the inverse trend.Relabelling methods can overforget: they lower forget-set accuracy more than retraining does, which helps on high-mem sets but hurts on low-mem sets.Source: Figure 1 · p. 5, §4.2 · p. 6

4.1 The more entangled the forget and retain sets are, the harder unlearning becomes

• The Entanglement Score measures retain–forget entanglement using their embedding-space variance relative to the separation between their means.Embeddings come from the original model before unlearning begins.Source: §4.1 · pp. 4–5
• To create entanglement strata, the authors sort examples by distance to the full-data embedding centroid and select contiguous ranges, producing low-, medium-, and high-score partitions.They evaluate four dataset/architecture settings with forget sets of 3,000 examples.Source: §4.1 · p. 5

4.2 The more memorized the forget examples are, the harder unlearning becomes

• Memorization strata are formed by selecting the 3,000 lowest-score, highest-score, or near-0.5 examples, then comparing unlearning performance on CIFAR-10 and CIFAR-100.The resulting sets are called low-mem, high-mem, and medium-mem, respectively.Source: §4.2 · p. 6
• Algorithm rankings vary by memorization level: Finetune leads on medium-mem, SalUn on high-mem, and several methods, including no unlearning, on low-mem.Relabelling methods notably fail on low-mem sets, where other algorithms—and even no unlearning—can perform well.Source: §4.2 · p. 6

5 Refined-Unlearning Meta-algorithm (RUM) for Improved Unlearning

• RUM partitions a forget set into homogeneous subsets, then uses existing unlearning algorithms to unlearn the subsets.The framework targets forget sets that may mix examples from different data modes, including rare or highly memorized and common, unmemorized examples.Source: §5 · p. 7
• The refinement function partitions the forget set so each example appears in exactly one subset, aiming for homogeneity on factors that affect difficulty or algorithm behavior.Source: §5 · p. 7
• The sequential meta-algorithm selects an unlearning algorithm for each subset and an execution order, then returns the model from the final step.It selects from a pool of existing algorithms and leaves other meta-algorithm designs for future work.Source: §5 · p. 7
• RUM is presented as an analysis framework that surfaces open problems and pathways for future algorithms, alongside specific top-performing instantiations.Source: §5 · p. 7

Experimental setup

• The experiments use three equal-sized forget-set subsets of low-, medium-, and high-memorization examples and evaluate ToW and MIA-based measures.The CIFAR-10 and CIFAR-100 forget sets each contain 3,000 examples; the study also compares low-to-high and high-to-low processing orders.Source: §6 · pp. 7–8

Refinement and per-subset algorithm selection

• RUMF significantly outperforms vanilla and shuffle across four algorithms and two datasets, while full RUM yields the overall best results.Source: Figure 3 · p. 8, §6 · pp. 8–9

Refinement alone

• In most cases, random-shuffle processing performs worse than vanilla, indicating that a poor refinement strategy may increase unlearning difficulty.Source: §6 · p. 8

Per-subset algorithm selection

• On CIFAR-10, full RUM uses do nothing → Fine-tune → SalUn and gives the best ToW and MIA; on CIFAR-100, it corresponds to NegGrad+ RUMF.Source: Figure 3 · p. 8, §6 · p. 9

C-proxy refinement

• C-proxy refinement preserves the observed difficulty trend and gives significant performance gains comparable to refinement with memorization scores.The experiments also report this pattern on Tiny-ImageNet with ResNet-18 and VGG-16.Source: §6 · p. 9, Figure 4 · p. 9

Sequence dynamics

• Different subset orderings yield similar ToW but can vary in MIA; SalUn's later sequence steps reverse its initial overforgetting of low-memorization examples.Source: §6 · p. 9, Figure 5 · p. 10

7 Discussion and conclusion

• Sequential unlearning on homogenized forget-set subsets improves all considered state-of-the-art algorithms, and choosing the best algorithm per subset can further boost performance.The discussion also reports that relabeling-based methods suffer disproportionately as embedding-space entanglement rises and show a reverse trend from other methods across memorization levels.Source: §7 · p. 10
• Unlearning gets harder as retain–forget embedding-space entanglement or forget-set memorization increases, and the algorithms respond differently as difficulty rises.Relabeling-based methods suffer disproportionately with greater entanglement and show a reverse trend from other methods across memorization levels.Source: §7 · p. 10
• Sequential RUM's efficiency depends on the algorithm: repeated Fine-tune passes cost more, while some algorithms add little overall cost.Doing nothing on a subset can improve efficiency, especially because most examples are low-memorization; C-proxy can improve performance with minimal computational cost without computing memorization scores.Source: §7 · p. 10
• All memorization buckets had relatively high embedding-space entanglement, so separating data-space outliers did not lower entanglement between forget and retain sets.The interaction between data-space outliers and embedding-space entanglement is left for future work.Source: §7 · p. 10
• Future work should examine other refinement strategies, sequential RUM's privacy implications, and adapting the framework to LLM unlearning.The discussion specifically raises the privacy onion effect and notes contemporaneous LLM work focused on highest-memorized examples, using a different definition of memorization.Source: §7 · p. 10

A.1 Broader impact

• Unlearning can support user-requested data deletion and model safety or accuracy by removing harmful or outdated information.The paper frames these as potential broader impacts of unlearning research.Source: §A.1 · p. 14
• The authors characterize their work as exploratory, identifying interpretable factors that affect difficulty and can drive improvements to unlearning pipelines.Source: §A.1 · p. 14
• The authors do not foresee a direct harmful impact from this work.Source: §A.1 · p. 14

A.2 Implementation details

• Evaluation covers CIFAR-10, CIFAR-100, and Tiny-ImageNet using ResNet-18, ResNet-50, and VGG-16.ResNet-18 is used for CIFAR-10; ResNet-50 for CIFAR-100; and ResNet-18 and VGG-16 for Tiny-ImageNet.Source: §A.2 · p. 14
• Original models were trained with SGD, weight decay 0.0005, momentum 0.9, and batch size 256, with epochs and learning-rate schedules varying by dataset and architecture.CIFAR-10 ResNet-18 used 30 epochs; CIFAR-100 ResNet-50 used 150; Tiny-ImageNet ResNet-18 used 80 and VGG-16 used 100.Source: §A.2 · p. 14
• Unlearning methods used method-specific hyperparameter searches, while retrain-from-scratch repeated the original training procedure using only the retain set.The passage gives separate epoch, learning-rate, and method-specific parameter ranges for Fine-tune, L1-sparse, NegGrad, NegGrad+, Influence, SalUn, and Random-label.Source: §A.2 · p. 14
• Partition experiments report averages with 95% confidence intervals over three runs, except relabeling methods, which used six runs; RUM tuned each step to match retraining accuracy.RUM results are averages over three runs with 95% confidence intervals.Source: §A.2 · p. 14

A.3 Procedure for creating retain / forget partitions with varying ES

• The distance procedure uses embeddings extracted from the original model trained on the full training dataset and the mean embedding as the global centroid.Source: §A.3 · p. 15
• Examples are ranked by their l2-distance from the training-set embedding centroid, with 3,000 highest-distance examples forming the low-ES bucket and subsequent groups forming medium- and high-ES buckets.Each forget set has 3,000 examples; high distances are treated as less entangled with the retain set.Source: §A.3 · p. 15
• For CIFAR-10/ResNet-18 and CIFAR-100/ResNet-50, low (high) ES corresponds to high (low) MMD, supporting consistency between the ES and MMD measures.The reported ES values increase from low to high partitions for both datasets.Source: §A.3 · p. 15
• Figure 6 shows forget and retain representations becoming increasingly entangled from low- to high-ES partitions, consistent with the computed ES values.The authors interpret greater entanglement as greater complexity in distinguishing the two sets.Source: §A.3 · p. 15

• A confidence-based binary MIA is trained on equal-sized retain and test samples, then applied to the forget set; its score is the fraction predicted as non-training.The desired outcome is for forget examples to be classified as non-training.Source: §A.4 · p. 15
• The ideal MIA score matches retraining from scratch, while MIA gap measures the absolute score difference from retraining, with zero ideal.Some forget examples can still be classified as training data after retraining because they resemble the retain set.Source: §A.4 · p. 16
• ToW-MIA combines the forget-set MIA difference and retain/test accuracy differences from retraining; it ranges from 0 to 1, with higher values better.Figure 7 shows the same trends with ToW-MIA as with ToW.Source: §A.4 · pp. 16–17, Figure 7 · p. 17

A.5 Data-space vs embedding-space outliers

• Memorization scores span 0–1 within each ES category, while all memorization buckets have relatively high ES, indicating distinct factors.Mean memorization scores rise from low to high ES categories, but each category still contains a range of memorization levels.Source: §A.5 · p. 17, Table 3 · p. 17, Figure 8 · p. 18

A.6 Confidence-based proxy for memorization

• C-proxy averages ground-truth-label softmax probabilities across training epochs and is negatively correlated with memorization while reducing computational overhead.The evaluation compares its fidelity and additional computational cost with memorization-score computation and retraining from scratch.Source: §A.6 · p. 18, Table 4 · p. 18
• Lower C-proxy corresponds to harder unlearning, while C-proxy-refined RUMF retains significant gains comparable to memorization-based refinement.The reported pattern spans datasets and model architectures.Source: §A.6 · pp. 18–19, Figure 9 · p. 19, Figure 10 · p. 19

A.7 Per-example differences between the unlearned and retrained models

• ca. [7%, 15%] disagreement for highly memorized data versus ca. [3%, 5%] for low-memorized data, with disagreement remaining modest.These per-example trends align with ToW trends across memorization levels and are also observed across ES levels.Source: §A.7 · p. 19, Table 5 · p. 20

A.8 Detailed results

• Low-to-high and high-to-low memorization orderings yield similar ToW but different accuracy dynamics during sequential unlearning.The plots track overall forget-set, subset, retain-set, and test-set accuracy after each step.Source: §A.8 · p. 21, Figure 13 · p. 22, Table 16 · p. 33
• ToW decreases from low to high ES across algorithms and with increasing memorization for most algorithms, indicating greater unlearning difficulty.The detailed results include multiple datasets and architectures; averages use 3 runs, or 6 for relabelling-based algorithms.Source: §A.8 · p. 20, Figure 11 · p. 21, Figure 12 · p. 22
• RUMF improves each selected algorithm, while full RUM, which chooses the best algorithm for each subset, achieves the overall best results.The comparison includes one-go, shuffled subsets, and refinement-based subsets.Source: §A.8 · p. 21, Table 16 · p. 33