Anticipating Relearning Resistance before the Attack

Machine unlearning is often fragile. By training on loosely related data, an attacker can bring the forgotten capability back. Today, this is only discovered via attacking the model post-unlearning. We show that we can anticipate a model's resistance to such attackers before the unlearning and attack happen from the frozen representation of the model. For weaker attackers that read the target out of a fixed representation, we provide a deterministic certificate, and show that relearning resistance is possible only when the target is statistically independent of the knowledge the model must retain. For stronger attackers that retrain the weights, we show that no certificate can be read from the local geometry of the unlearned model, and give a weaker, probabilistic guarantee from randomized smoothing instead. Across a vision model and ten language models (124M-7B) and four unlearning methods, the floor predicts relearning resistance in agreement with realized attacks, outperforming off-the-shelf baselines, and is sound on the read-out tests that can fail it (151 of 158). This work aims to contribute to safer and more private deployment of machine learning.