LMCleaner: Efficient and Certified Online Unlearning via Influence Propagation Truncation

Existing machine unlearning methods primarily focus on removing data influence after training completes, which is effective for many scenarios, but a complementary capability is needed when removal requests arise during ongoing training. We propose LMCleaner, an efficient and certified online unlearning framework that can process unlearning requests at any training step without waiting for training completion. Our key insight is that influence propagation can be decomposed into a trust region where linear approximation is accurate, and a residual that concentrates in a low-dimensional subspace and can be efficiently masked by calibrated noise. Building on this insight, we design an influence propagation truncation mechanism that treats mini-batch influence as atomic units, computes influence within a truncation window for efficient removal, and injects subspace-aware noise for certified privacy. Our theoretical analysis proves that the truncation residual decays exponentially with window size and that the unlearned model is $(\varepsilon, \delta)$-indistinguishable from retraining. Experiments demonstrate that LMCleaner achieves over $100\times$ computational savings compared to baselines while maintaining model utility and defending against membership inference attacks.