Future Deletions from Past Retraining: Exact Machine Unlearning via Sparse Retraining Archive

Exact machine unlearning seeks to reproduce retraining outcomes after designated data are removed, but repeated retraining becomes impractical as the number of possible deletion combinations grows exponentially. In this paper, we study the recovery of all deletion targets from sparse retraining archives containing models retrained for only a small fraction of deletion requests, without further data access or retraining. For ridge regression, we show that all deletion responses lie in a low-dimensional space and satisfy a shared affine matrix equation when the curvature contributed by deletable data is low rank. This structure yields a convex decoder that recovers unseen retraining targets from archived models. Under independently and uniformly sampled deletion requests, we establish upper and lower bounds showing that, at fixed rank and confidence, the archive size required for exact recovery grows only linearly with the number of deletable groups despite the exponential catalog size. We further derive uniform recovery bounds for noisy archives, characterizing rank-dependent error amplification, and extend the analysis to approximately low-rank deleted curvature through an explicit spectral-tail term. Controlled experiments recover all 4,096 deletion targets from 96 archived models and support the predicted acquisition and error-amplification mechanisms. Further experiments assess noisy recovery in the convex special case and spectral-tail effects.