Why Forget-Only Unlearning Needs Memorization

Machine unlearning asks for a deletion procedure whose output is close to retraining from scratch on the retained data. We study the strict forget-only setting, where the unlearner receives only the trained model $M=A(S)$ and forget set $U$, with no retained data or auxiliary training state. We show that forget-only unlearning is not uniformly possible: if two datasets yield the same trained model but a common deletion sends their retraining targets far apart, no forget-only unlearner can satisfy Rényi unlearning while preserving nontrivial utility. Conversely, we prove mutual-information lower bounds showing that supporting many deletion requests requires the trained model to memorize enough dataset information to recover the corresponding retraining targets. We instantiate these results on standard learners, including thresholds, medians, SVMs, PCA, sparse regression, and factorized matrix completion. Overall, strict forget-only unlearning can require retaining far more information than ordinary learning: deletion requests may expose information the learner would otherwise discard.