Leak@$k$: Unlearning Does Not Make LLMs Forget Under Probabilistic Decoding

Unlearning in large language models (LLMs) is critical for regulatory compliance and for building ethical generative AI systems that avoid producing private, toxic, illegal, or copyrighted content. Despite rapid progress, in this work, we show that \textit{almost all} existing unlearning methods fail to achieve true forgetting in practice. Specifically, while evaluations of these `unlearned' models under deterministic (greedy) decoding often suggest successful knowledge removal using standard benchmarks, we show that sensitive information reliably resurfaces when models are sampled with standard probabilistic decoding. To rigorously capture this vulnerability, we introduce \texttt{leak@$k$}, a new meta-evaluation metric that quantifies the likelihood of forgotten knowledge reappearing when generating $k$ samples from the model under realistic decoding strategies. Using three widely adopted benchmarks, TOFU, MUSE, and WMDP, we conduct the first large-scale, systematic study of unlearning reliability using \texttt{leak@$k$} metric. Our findings demonstrate that knowledge leakage persists across methods and tasks, underscoring that current state-of-the-art (SOTA) unlearning techniques provide only limited forgetting. We propose an algorithm, termed Robust Unlearning under LEak@$k$ metric (\texttt{RULE}) to address this concern. We demonstrate that \texttt{RULE} provides an unlearned model for TOFU benchmark with no information leakage for a large number of generation samples. On the MUSE benchmark, \texttt{RULE} outperforms SOTA unlearning methods under the \texttt{leak@$k$} metric across most sampling budgets $k$. Codes are available at \url{https://github.com/OptimAI-Lab/Leak-k}.

Large language models memorize private, toxic, or copyrighted content. Unlearning is a promising approach to remove this unwanted knowledge, but current evaluations use deterministic decoding (models always pick the most likely word), making unlearning appear successful. Real deployments use probabilistic decoding (models randomly sample alternatives), which causes supposedly sensitive information to resurface reliably. When prompted multiple times with probabilistic sampling, unlearned models consistently regenerate sensitive information, even when greedy testing suggested they had forgotten it. To quantify this, we introduce leak@k, a new evaluation method that checks whether sensitive information appears in any of several generated answers. We test various unlearning methods on several standard benchmarks and find that leakage often increases as more answers are sampled. We also propose RULE, a robust unlearning method under leak@k metric, that repeatedly generates leaking responses and uses them during training to make forgetting more robust. Our results show that evaluating only one deterministic answer can give a false sense of safety, and that future unlearning systems should be tested under repeated, realistic model use.