Measuring memorization in language models via probabilistic extraction (2025)

Abstract: Large language models (LLMs) are susceptible to memorizing training data, raising concerns about the potential extraction of sensitive information at generation time. Discoverable extraction is the most common method for measuring this issue: split a training example into a prefix and suffix, then prompt the LLM with the prefix, and deem the example extractable if the LLM generates the matching suffix using greedy sampling. This definition yields a yes-or-no determination of whether extraction was successful with respect to a single query. Though efficient to compute, we show that this definition is unreliable because it does not account for non-determinism present in more realistic (non-greedy) sampling schemes, for which LLMs produce a range of outputs for the same prompt. We introduce probabilistic discoverable extraction, which, without additional cost, relaxes discoverable extraction by considering multiple queries to quantify the probability of extracting a target sequence. We evaluate our probabilistic measure across different models, sampling schemes, and training-data repetitions, and find that this measure provides more nuanced information about extraction risk compared to traditional discoverable extraction.

## introduction large language models (llms) are susceptible to memorizing pieces of their training data, raising concerns about the potential extraction of sensitive information in the training dataset at generation time @xcite @xcite @xcite @xcite @xcite @xcite . 1 this issue has attracted significant attention, leading researchers to routinely report training-data extraction rates in technical reports introducing new llms @xcite @xcite @xcite . there are numerous ways to measure these rates, but one of the most common is to quantify discoverable extraction: split an llm's training example into a prefix and suffix, prompt the llm with the prefix, and deem the example extractable if the llm generates the sequence that matches the suffix @xcite @xcite (section 2). discoverable extraction is simple and efficient to compute; however, it has drawbacks that may make it an unreliable estimate for a model's true extraction rate. notably, the definition for discoverable extraction does not account for the non-deterministic nature of llms. it yields a yes-or-no determination of whether extraction was successful with respect to a single user query, most typically executed with deterministic greedy sampling. but, of course, in realistic production settings, users may query the model multiple times and with non-deterministic sampling schemes, where multiple queries with the same prompt can result in a range of different generations. so, by only generating a single sequence to check for a match with the target, discoverable extraction may miss cases where a match could have been found if more than one sequence had been generated. further, extracting sensitive training data even once out of multiple queries could be problematic, as an adversary (e.g., a hacker checking credit card numbers) may have external means of verifying the sensitive information's validity. it is therefore reasonable to quantify the number of sequences that need to be generated before a particular target example becomes extractable. following from this motivation, we introduce probabilistic discoverable extraction: a relaxation of discoverable extraction that considers multiple queries in order to quantify the probability of extracting a particular target sequence. that is, our new definition for (n, p)-discoverable extraction quantifies the number of attempts n an adversary would need to make to extract a target sequence at least once with probability p under a given sampling scheme (section 3). we benchmark (n, p)discoverable extraction rates for different sampling schemes, settings of n and p, model families and sizes, and repetitions of target data (section 4). in summary, (n, p)-discoverable extraction • provides more meaningful measurements of extraction rates than greedy-sampled discoverable extraction, which, by comparison, underestimates extraction rates even for modest values of n and p (sections 3.1 & 4.1). the gap between the two rates increases for larger models and more repetitions of the target (section 4.2). ## preliminaries and related work we begin with prior work on discoverable extraction (section 2.1) and relevant background on different sampling schemes (section 2.2). ## probabilistic discoverable extraction the more realistic setting of non-deterministic sampling and multiple queries motivates measuring ex-traction from a probabilistic perspective. rather than taking a one-shot approach, it is reasonable to quantify the number of sequences that need to be generated before a target example becomes likely to be extracted under a chosen sampling scheme. following from this motivation, we introduce (n, p)-discoverable extraction, which captures the capabilities of a regular user that can query the model n times to extract verbatim a target sequence with probability p (section 3.1). under non-deterministic sampling schemes, many extractable targets are unlikely to be guaranteed to be generated (i.e., @xmath0, but many targets may be generated at least once given enough attempts (@xmath1. thus, our definition captures a continuous notion of the risk of extracting the target example; it provides a more meaningful estimate of extraction risk than can be gleaned from one-shot, yes-or-no tests (section 2.1). we then discuss how n and p are directly related through a simple equation such that, in practice, it is possible to measure a high-fidelity approximation of (n, p)-discoverable extraction with just one query-with no overhead compared to traditional discoverable extraction (section 3.2). we then briefly describe a variant of (n, p)-discoverable extraction that measures the non-verbatim extraction of target sequences (section 3.3), and draw connections between our contributions and other work (section 3.4). ## experiments we now demonstrate the utility of taking a probabilistic perspective on measuring extraction through experiments involving different model families. we show how (n, p)-discoverable extraction rates change as a function of n and p (section 4.1), and evaluate how these rates increase for larger model sizes and training-data repetitions (section 4.2). we also verify that our analysis reflects valid estimates of training-data extraction. to do so, we compare the (n, p)-discoverable extraction rate to the corresponding rate of generating test-data examples (section 4.3). altogether, our analysis illustrates that (n, p)-discoverable extraction provides more reliable measurements of extraction rates than greedy-sampled discoverable extraction, and also reveals a more nuanced picture of extraction risk in llms. ## conclusion in this paper, we take a probabilistic perspective on measuring training-data extraction in language models. this represents a significant departure from prior work and model-release reports, which tend to measure discoverable extraction: one-shot, yes-or-no determinations of extraction using deterministic greedy sampling. instead, our measure for (n, p)-discoverable extraction captures a continuous notion of the risk of extracting a target example: we recast discoverable extraction in terms of the number of queries n one would need to make to extract a target at least once with probability p under a chosen sampling scheme. to conclude, we revisit three benefits of our probabilistic approach. reliable quantification of extraction. through extensive experimentation, we show that (n, p)discoverable extraction provides more reliable measurement of extraction rates and facilitates more valid comparisons of extraction rates across models. greedy-sampled discoverable extractionthe common approach in prior work-often significantly underestimates the overall rate of possible extraction (sections 3.1 & 4.1), with the degree of underestimation increasing for larger models (section 4.2). however, for low query budgets n (and even for relatively low p), the (n, p)-discoverable extraction rate is often lower than the greedy rate. this suggests that prior reported greedy rates may also overestimate the amount of extraction experienced by end users in practice (section 4.1).