Measuring Memorization in Language Models via Probabilistic Extraction

1. 01What problem does this paper attempt to solve?

   The authors argue that the one-shot discoverable extraction determination with greedy sampling is unreliable, and propose the probabilistic metric (n, p)-discoverable extraction.

   Core question: how to reliably measure the extraction risk of LLM training data—existing discoverable extraction uses greedy sampling to make a single yes/no determination, which the authors argue ignores the non-determinism in realistic sampling and underestimates the extraction rate.

   • Problem setting: LLMs memorize training data and may have sensitive information extracted during generation; new model technical reports often report training data extraction rates, most commonly discoverable extraction: split a training sample into a prefix and a suffix, prompt the model with the prefix, and judge it extractable if greedy sampling generates a matching suffix.
   • Shortcomings of existing methods: the authors point out that this definition gives a yes/no conclusion for a single query and does not consider that under non-deterministic sampling schemes the same prompt can produce multiple outputs; generating only once may miss cases that would hit with a few more queries, and for an adversary able to externally verify sensitive information (e.g., credit card numbers), succeeding once among multiple attempts already constitutes a problem.
   • Core observation: under non-deterministic sampling, many targets are almost never guaranteed to be generated in a single query (p=1), but after enough attempts (n>1) they may be generated at least once; n and p have a directly convertible relationship, so a single query can approximate the entire (n, p) extraction rate.
   • What the paper proposes: (n, p)-discoverable extraction—quantifying how many queries n an adversary needs under a given sampling scheme to extract the target sequence at least once with probability p; and it provides a high-fidelity single-query approximation, a non-verbatim-matching extension (ϵ, n, p), and benchmark measurements across models, sampling schemes, and data repetition counts.
   • Threat model:
     • Goal: generate the target training sample suffix verbatim (or within ϵ distance) at least once within n queries with probability p.
     • Knowledge: the authors state they study a relatively benign adversary—only API access, limited side information; knows the target prefix (the paper uses the first 50 tokens of the training sample as the prompt).
     • Capability: can query the model multiple times with the same prefix and can choose non-deterministic sampling schemes (e.g., top-k).
     • Victim system: language models with open weights such as Pythia, GPT-Neo, Llama, and OPT.

   Collapse this answer

2. 02What related research exists?

   The paper relates to four categories of work: discoverable extraction metrics, sampling schemes, other definitions of memorization, and parallel work on probabilistic extraction.

   Discoverable extraction and its variants

   • Carlini et al. (2021, 2022), Nasr et al. (2023)—proposed and developed the definition of discoverable extraction; this paper's definition is adapted from theirs; Carlini et al. (2022) tested prefixes of 50–500 tokens, judged extraction by generating the following 50 tokens, and additionally analyzed one-shot extraction under beam search.
   • Biderman et al. (2023)—an instantiation with both prefix and suffix set to 32 tokens.
   • Model technical reports (PaLM 2, Gemini, Gemma, Llama, etc.)—routinely report training data extraction rates based on greedy sampling; the authors point out that these reports rely on the greedy one-shot determination, and the resulting extraction amounts may differ from what end users actually see.

   Sampling schemes

   • Fan et al. (2018) (top-k), Basu et al. (2020) (Mirostat), Vijayakumar et al. (2016) (diverse beam search)—non-greedy sampling schemes used to increase output diversity.
   • Carlini et al. (2022) considered high-randomness sampling schemes to be "at odds" with maximizing discoverable extraction; the authors instead consider such schemes more suitable for identifying extraction in realistic multi-query scenarios.

   Other definitions of memorization and extraction (Appendix B)

   • Carlini et al. (2019)—canary memorization and rank perplexity: rank candidate canaries by perplexity, with the rank corresponding to the number of guesses an adversary needs; the authors point out that its (skewed) Gaussian approximation assumption does not apply to the format-unconstrained training samples in this paper (Figure 9).
   • Brown et al. (2021), Feldman and Zhang (2020), Zhang et al. (2023)—information-theoretic and counterfactual definitions of memorization; the authors point out that estimating these quantities requires training many models (Zhang et al. still require hundreds even with subsampling), which is infeasible in the LLM setting.
   • Schwarzschild et al. (2024) et al.—treat memorization as compression, measured by the shortest prompt length needed to generate the target; the authors consider this definition misaligned with the ordinary-user extraction risk this paper focuses on.
   • Kassem et al. (2024), Wang et al. (2024)—extract training data using prompt engineering (LLM prompt search, soft prompts); the authors point out that such methods require optimizing multiple prompts for each target, with higher computational cost than this paper's method.

   Related work on probabilistic extraction

   • Tiwari and Suh (2025)—published shortly after this paper, also studies extraction probability under different sampling strategies and models (Llama, OPT) and non-verbatim extensions; the authors point out that this paper's distinction is providing the single-query conversion relationship between n and p and verifying that what is measured is true memorization rather than coincidental generation.
   • Kim et al. (2023) (ProPILE), Nakka et al. (2024) (PII-Compass)—probabilistic metrics of PII leakage and multi-query experiments; the authors state that Nakka et al.'s multi-query analysis is similar to theirs but limited in scope.
   • Stock et al. (2022)—defends against reconstruction attacks using Rényi DP, analyzing with expectation rather than probability p.

   Baseline and benchmark: the paper's comparison is the traditional greedy-sampling discoverable extraction (Definition 2.1); measurements are conducted on the Enron, Wikipedia, and GitHub subsets of The Pile and on Common Crawl (a proxy for Llama/OPT), with 10,000 samples each.

   The authors position this paper as: relaxing discoverable extraction from a one-shot yes/no determination to a continuous risk metric, without additional computational overhead.

   Collapse this answer

3. 03How does the paper address this problem?

   Relaxes the extraction determination to "generating the target suffix at least once within n queries with probability p," and converts between n and p using one forward computation.

   Overall approach: relax discoverable extraction from a single greedy determination to a probabilistic metric (n, p)-discoverable extraction, and derive the conversion relationship between n and p so that measurement requires no additional query overhead.

   Problem formalization

   • A training sample z is split into a prefix z1:a of length a and a suffix za+1:a+k of length k; fθ is the model and gϕ is the sampling scheme.
   • Discoverable extraction (Definition 2.1): using the prefix as a prompt, if (g_ϕ ∘ f_θ)^k(z_1:a) = z_1:a+k, i.e., the generated sequence matches the target verbatim, it is judged extractable; this is a yes/no determination for a single query.
   • (n, p)-discoverable extraction (Definition 3.1): if the probability that at least one of n independent queries generates the target suffix is no less than p, then z is (n, p)-discoverably extractable; when n=p=1 it reduces to the traditional definition. The authors note that this can also be viewed as the model and sampling scheme jointly providing an anonymity set of size n for a real training sample.

   Conversion between n and p: single-query approximation

   • Let pz be the probability that a single sample generates the target suffix; then z is (n, p)-discoverably extractable if and only if n ≥ log(1−p)/log(1−p_z); fixing p allows solving for n and vice versa, and in expectation n = ⌈1/pz⌉.
   • Computing pz in a single query: feed z to the model token by token, take the conditional log probability at each position after processing by the sampling scheme gϕ (e.g., top-40 truncation, normalization, reweighting at T=1), and sum them to obtain the log-likelihood of the entire sequence under fθ and gϕ (Appendix C.3).
   • The same process can also arbitrarily change the prefix/suffix lengths within the same query (by changing the summation indices), without re-querying.
   • Validation: for 250 samples from the Pile Wikipedia subset and Pythia 6.9B, the empirical p obtained from n=1000 samples is compared with the theoretical p converted by the formula, and the authors report that the two agree (Figure 2).

   How to choose n and p

   • The authors deliberately do not specify concrete thresholds, believing that reasonable values depend on the type of information to be extracted (e.g., tolerance differs between generic phrases and PII), and regard this flexibility as an advantage.
   • One approach is to set the threshold according to the adversary's computational budget: ensuring n is greater than the budget controls the risk, which in practice can be achieved through rate limiting.

   Non-verbatim extension

   • (ϵ, n, p)-discoverable extraction (Definition 3.2): extraction counts if the generated suffix falls within the set Sϵ of suffixes within ϵ distance of the target suffix; the distance function dist and ϵ are chosen by the user.
   • Appendix D uses Hamming distance as an example: direct enumeration is costly (with ϵ=1, a 50-token suffix, and |V|=32,000, there are 1,600,000 candidate suffixes), and there is no closed-form single-query conversion; it can be approximated by the proportion p̂zϵ of n samples falling within ϵ distance.

   Evaluation method

   • The main experiments use top-k sampling (k=40, T=1), compared against the one-shot extraction rate of greedy sampling; prefix 50 tokens, suffix 50 tokens (following the setup of Carlini et al. 2021).
   • The samples are 10,000 samples from the Enron subset of The Pile; the appendix includes Wikipedia and GitHub subsets and Common Crawl proxy data for Llama/OPT (10,000 each).

   Collapse this answer

4. 04What experiments did the paper conduct?

   The (n,p) extraction rate is measured on Pythia, GPT-Neo, Llama, and OPT: the authors state that the greedy underestimation worsens as the model gets larger, with the maximum rate for 2.8B being 9.04% versus 1.3% for greedy.

   Experimental Setup

   • Models tested: Pythia 1B/2.8B/6.9B/12B, GPT-Neo 1.3B (all trained on The Pile); the appendix additionally covers Llama 7B/13B and OPT 350M/1.3B/2.7B/6.7B (training data not fully public; Common Crawl used as a proxy, and the authors expect extraction rate estimates to be biased low).
   • Data: 10,000 each from the Enron, Wikipedia, and GitHub subsets of The Pile; validation experiments use 10,000 emails from TREC 2007 Spam as unseen test data.
   • Protocol: prefix 50 tokens, suffix 50 tokens; the main experiments use top-k sampling (k=40, T=1); Appendix F additionally tests top-q and temperature sampling.
   • Metrics: (n, p)-discoverable extraction rate (one query plus Equation (2) conversion; except Figure 2), compared against the greedy discoverable extraction rate.
   • Determination method: verbatim matching of the target suffix; no LLM judge.
   • Number of repetitions: the paper does not report the number of experimental repetitions or confidence intervals.

   Main Results

   (n, p) extraction rates versus greedy rates under different n, p (Enron 10,000, top-k k=40, T=1; per Figures 3, 4, 5, 11):

   Swipe horizontally to read the table

   Model	Greedy rate	Max (n,p) rate	Source
   Pythia 1B	0.76%	not reported	Figure 5 (greedy rate in Section 4.2)
   Pythia 2.8B	1.3%	9.04%	Figures 3a, 4
   Pythia 12B	3.07%	16.07%	Figures 3b, 11b
   GPT-Neo 1.3B	lower than Pythia 1B	not reported	Figure 5

   • The authors state that in every experiment there exist n, p settings for which the (n, p) rate exceeds the greedy rate; at p=0.1 the (n, p) rate exceeds the greedy rate even for small n, and the gap grows as n increases.
   • The authors state that at high p and small n, greedy instead overestimates: for Pythia 2.8B at p=0.999, the (n, p) rate approaches the greedy rate only when n>169, and at p=0.5 only when n>17.
   • The authors state that cross-model comparisons can reverse: Pythia 1B has a higher greedy rate than GPT-Neo 1.3B, but at the same p the (n, p) rate is higher for GPT-Neo 1.3B at every n (Figure 5).

   Model Scale and Data Repetition

   • Model scale: greedy rates for Pythia 1B/2.8B/12B are 0.76%, 1.3%, 3.07% respectively (Section 4.2); the gap between the greedy rate and the maximum (n, p) rate is 7.74 percentage points for 2.8B and 13 percentage points for 12B (Figure 11); at p=0.9, the number of queries needed to exceed the greedy rate is n=150 for 1B and n=40 for 12B.
   • Repetition count: on phone numbers repeated in the Pile (Pythia 2.8B, repetition-count buckets 1-5, 6-10, 11-50), the (n, p) rate exceeds the greedy rate and the gap widens with repetition count (Figure 6); the figure labels only the buckets and legend (greedy, n=1/10/100, p=0.1), not specific values.
   • The authors state that these results are consistent with the trend in prior literature that "larger models and more repetition are easier to extract," and that underestimation is more severe for large models and highly repeated data.

   Validity Check: Training Data vs Test Data

   • What was tested: whether large n and small p are too lenient—the model might merely happen to generate the target suffix rather than truly memorize it (Pythia 2.8B, Enron training data vs TREC 2007 Spam test data, Figure 7).
   • Results: at all p, the test-data generation rate is lower than the training-data extraction rate; at p=0.1 the test-data generation rate is effectively 0% until n>50,000 and stays below 1% even for very large n, whereas the training-data extraction rate exceeds 5%; at p=0.9, after 500,000 queries the test-data generation rate is 0.3% and the training-data (n, p) extraction rate is 4.4%.
   • Authors' interpretation: the number of queries needed to generate unseen test data is several orders of magnitude higher than for extracting training data, which the authors take to support that matches in their (n, p) measurement are almost certainly due to memorization.

   Other Ablations and Analyses

   • Sampling schemes (Appendix F, Figure 12): varying k for top-k, q for top-q, and temperature T on Pythia 2.8B, Enron; generally smaller k, q, T correspond to lower extraction rates, but there is no strict ordering, and extraction rates remain above the greedy rate under most hyperparameter settings.
   • More Pythia scales (Appendix E, Figure 10): 1B/2.8B/6.9B/12B on Enron; the authors state that at most n, p, doubling the parameter count roughly doubles the extraction rate.
   • Other datasets (Appendix H): Pythia's extraction rate on Wikipedia (Figure 14) is lower than on Enron, and on GitHub (Figure 15) higher than on Enron; on GitHub, Pythia 6.9B has a lower extraction rate than 2.8B at the given n, p, an exception to the scale trend.
   • Llama/OPT (Appendix H, Figures 16, 17): on Common Crawl proxy data, Llama 13B is higher than 7B, and OPT 6.7B is higher than the similarly sized Llama 7B; both have lower extraction rates than similarly sized Pythia on each subset (note that the proxy data may not be in the training set).
   • Suffix probability distribution (Appendix G, Figure 13): on Pythia 2.8B, Enron, about 9,000 suffixes have probability 0 under top-k and top-q sampling; under T=1 random sampling, about 250 target suffixes are almost certainly sampled within n=100.

   Collapse this answer

5. 05What are some points that can be further explored?

   The authors note that the adversary model is relatively benign and does not distinguish target sensitivity types; experiments focus on Pythia, with proxy data for Llama/OPT.

   Limitations and Future Directions Noted by the Authors

   • Limited adversary capability (Section 6): the authors state that they study a relatively benign adversary—API access only, limited side information—and leave stronger adversaries to other work.
   • Target types not distinguished (Section 6): the paper does not distinguish extraction of target sequences of differing sensitivity, and the authors believe extraction rates for more sensitive targets such as PII should be measured separately.
   • PII only roughly touched on (Section 6): phone numbers are used only when measuring repetition counts; extraction rates for different types of PII and other sensitive targets are left to future work.
   • Not limited to memorization (Section 5): the authors propose that the metric could in the future be used to measure the risk of a model outputting arbitrary target sequences (e.g., harmful content).
   • Metrics evolve with attacks (Section 6): the authors state that extraction itself is difficult to measure, and that metrics will improve as new attacks (e.g., Nasr et al. 2023, 2025; Su et al. 2024) emerge.

   Scope of Experiments

   • The models tested are GPT-Neo 1.3B, Pythia (1B/2.8B/6.9B/12B), Llama 1 (7B/13B), and OPT (350M/1.3B/2.7B/6.7B), 11 in total, all open-weight models (Appendix C.1).
   • Training-data extraction measurements cover the Enron, Wikipedia, and GitHub subsets of The Pile (10,000 each); for Llama and OPT, 10,000 Common Crawl samples are used as a proxy, and the authors note that these samples may not be in their training sets and that extraction rate estimates are expected to be biased low (Appendix C.2).
   • Sampling schemes cover top-k, top-q (nucleus), temperature sampling, and a greedy baseline; the main-text results use top-k (k=40, T=1) (Appendix F).
   • Prefix/suffix lengths are fixed at 50/50 tokens; for non-verbatim extension (ϵ, n, p), only the definition and an approximate algorithm are given, with no experimental results in the paper (Section 3.3, Appendix D).
   • The paper does not report the number of experimental repetitions, confidence intervals, or statistical significance tests; the specific values of the n, p thresholds are deliberately left to the user by the authors (Section 3.2).

   Collapse this answer

6. 06Summarize the main content of the paper

   The authors propose the probabilistic extraction metric (n, p)-discoverable extraction, computable with a single query; the authors state that the greedy one-shot determination underestimates extraction risk.

   A paper on measuring memorization of LLM training data: in response to the convention of using greedy sampling to make a one-shot yes/no determination for discoverable extraction, the authors propose a probabilistic alternative metric.

   • Problem to solve: the greedy one-shot determination does not account for non-deterministic sampling and multiple queries; the authors argue it may both underestimate (cases extractable with a few more queries) and overestimate (with high p and small n) the extraction risk that end users actually encounter.
   • Method highlights: (n, p)-discoverable extraction—judged extractable if the probability of generating the target suffix verbatim at least once in n independent queries is no less than p; using n ≥ log(1−p)/log(1−pz), a single forward computation of the target suffix probability pz suffices to convert to any n, p, with no additional overhead; there is also a non-verbatim extension (ϵ, n, p).
   • Main results:
     • Pythia 2.8B, Enron (top-k k=40, T=1): greedy rate 1.3%, maximum (n, p) rate 9.04% (Figure 3a, 4).
     • Pythia 12B: greedy rate 3.07%, maximum rate 16.07%, with the underestimation gap widening as the model gets larger (Figure 3b, 11b).
     • Cross-model comparison reverses: Pythia 1B has a higher greedy rate than GPT-Neo 1.3B, but the (n, p) rate is the opposite (Figure 5).
     • On repeated data, the gap between the (n, p) rate and the greedy rate widens with the number of repetitions (Figure 6, phone numbers).
     • Validation: the generation rate of Pythia 2.8B on the TREC 2007 Spam test data is far lower than the training data extraction rate (0.3% versus 4.4% after p=0.9, 500,000 queries), which the authors consider supports that what is measured is memorization (Figure 7).
   • Authors' conclusions and implications: the authors state that the metric provides a more detailed characterization of extraction risk without increasing computational cost, and that n and p can be flexibly set according to data sensitivity and adversary budget (e.g., with rate limiting); model release reports relying on the greedy rate may give extraction amounts different from what end users actually experience. The authors also note that they only studied a benign adversary with only API access and did not distinguish target sensitivity types.

   Collapse this answer

Related papers