LMCleaner: Efficient and Certified Online Unlearning via Influence Propagation Truncation

Abstract

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.