Randomized Antipodal Search Done Right for Data Pareto Improvement of LLM Unlearning
For practitioners deploying LLMs who need to remove undesirable knowledge post-deployment, this work provides a principled and scalable data-centric unlearning method that improves the trade-off between forgetting and retention.
The paper tackles the problem of retrieving relevant data for LLM unlearning when only an undesired generation is observed. It introduces RASLIK, a randomized retrieval algorithm that achieves sublinear complexity and consistently outperforms deterministic baselines and oracle sampling across multiple models and datasets.
Large language models (LLMs) sometimes memorize undesirable knowledge, which must be removed after deployment. Prior work on machine unlearning has focused largely on optimization methods that adjust parameters to enforce forgetting while preserving retention. However, these approaches assume that the forget and retain sets are readily available, which rarely holds in practice. Unlearning is typically triggered by an undesired generation at inference time, making the retrieval of relevant data the central challenge. We introduce the notion of data Pareto improvement for LLM unlearning, which formalizes how retrieval can expand the achievable trade-off frontier between forgetting and retention. To realize this principle, we propose Randomized Antipodal Search on Linearized Influence Kernel (RASLIK), a retrieval algorithm that combines permutation-projection hashing with randomized antipodal search. RASLIK reduces selection variance, achieves sublinear complexity, and yields a double gain in both quality and efficiency. Across multiple models, datasets, and unlearning algorithms, RASLIK consistently outperforms deterministic baselines and even oracle sampling, establishing randomized search as a principled and scalable solution for data-centric unlearning.