Source-linked AI summary
Measuring memorization in language models via probabilistic extraction
Jamie Hayes, Marika Swanberg, Harsh Chaudhari, Itay Yona, Ilia Shumailov, Milad Nasr, Christopher A. Choquette-Choo, Katherine Lee, A. Feder Cooper
TL;DR
LLM memorization creates a risk that sensitive training data can be extracted, but common one-shot greedy measurements do not capture repeated queries and non-deterministic outputs. The paper introduces probabilistic discoverable extraction, which quantifies target-extraction probability across attempts without additional computational cost. It finds that this measure gives more reliable and nuanced extraction-rate measurements than greedy extraction, while its scope is limited to a relatively benign API-only adversary and does not distinguish target sensitivity.
Problem
Common discoverable-extraction measurements reduce extraction to a single greedy-sampled yes-or-no query, despite realistic non-deterministic sampling and repeated queries.
Method
The paper defines (n, p)-discoverable extraction as the number of attempts needed to extract a target sequence at least once with probability p under a specified sampling scheme.
Results
Probabilistic discoverable extraction provides more reliable measurements and enables more valid model comparisons, while greedy extraction often underestimates possible extraction and can overestimate extraction at low query budgets.
Takeaways & Limitations
The measure provides more nuanced information about extraction risk without additional cost because it can be computed with one query.
Takeaways & Limitations
The study focuses on a relatively benign adversary with API access and limited side information, and it does not distinguish extraction rates for different target types such as PII.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper argues that one-shot greedy extraction gives an incomplete view of training-data extraction because realistic sampling is non-deterministic and users may query models repeatedly. It introduces probabilistic discoverable extraction to quantify target-extraction probability, while preserving low computational cost and supporting non-verbatim matches.
- Probabilistic discoverable extraction quantifies how many attempts n are needed to extract a target sequence at least once with probability p under a sampling scheme.
- Greedy-sampled discoverable extraction often underestimates possible extraction, with the gap increasing for larger models and more target repetitions.
- The measure captures extraction risk under a specified non-deterministic sampling scheme rather than returning only a single-query yes-or-no outcome.
- Probabilistic discoverable extraction can be approximated with one query, avoiding overhead compared with traditional discoverable extraction.
- The measure also extends naturally to non-verbatim matches against a target sequence.
2 Preliminaries and related work
Discoverable extraction tests whether an LLM reproduces a training example’s suffix from its prefix, but the result depends on the sampling scheme and is especially limited by one-shot evaluation. This section formalizes the setup and motivates considering more realistic non-greedy sampling.
- 2 Preliminaries and related work: The extraction process composes an autoregressive language model with a sampling scheme that repeatedly samples tokens and appends them to the prompt.The model maps token sequences to vocabulary distributions, while the sampling scheme selects the next token; repeated application generates the query output.
- 2 Preliminaries and related work: Discoverable extraction splits a training example into a prefix and suffix, then counts exact suffix reproduction from the prefix as successful extraction.The standard definition treats extraction as a binary outcome for one query.
- 2 Preliminaries and related work: Prior evaluations vary prefix lengths and the minimum generated suffix length used to qualify an example as extracted.For example, Carlini et al. (2022) use prefixes from 50 to 500 tokens and test generation of the next 50 tokens.
- 2 Preliminaries and related work: Greedy sampling selects the highest-probability token at each step, making one-shot extraction deterministic, whereas other schemes introduce randomness and output diversity.Temperature sampling increases diversity as temperature rises and converges to greedy sampling as T →0; top-k sampling restricts sampling to the k highest-probability tokens.
- 2 Preliminaries and related work: Greedy sampling provides an incomplete picture because many deployed models use non-greedy schemes and users may choose among sampling strategies.Non-greedy methods can increase output diversity, while greedy decoding may fail to select the globally most likely sequence.
3 Probabilistic discoverable extraction
Probabilistic discoverable extraction extends one-shot greedy testing to quantify the chance that repeated queries extract a target sequence. The paper shows that non-deterministic sampling can reveal targets greedy sampling misses, while one-query probabilities provide an efficient approximation.
- 3.2 How should one set on n and p?: Equation (2) relates n and p through a single-query target probability, enabling efficient approximation without the overhead of directly sampling n sequences.The paper uses this procedure for its verbatim-extraction experiments and verifies its agreement with empirical n-query estimates in Figure 2.
- 3.1 Defining (n, p)-discoverable extraction: (n, p)-discoverable extraction measures whether n independent queries generate a target sequence at least once with probability at least p.It captures extraction risk continuously under a specified model and sampling scheme rather than as a one-shot yes-or-no outcome.
- 3.1 Defining (n, p)-discoverable extraction: Non-deterministic sampling can extract targets that greedy sampling misses, because a lower-ranked target token may lead to the overall-more-likely suffix.In the Figure 1 example, greedy diverges when the target token is rank 2, whereas top-k sampling selects it and then extracts the target with probability 16.2%.
- 3.1 Defining (n, p)-discoverable extraction: Repeated queries matter because a target occurring with probability 16.2% would be generated after about 6 queries in expectation, potentially exposing sensitive information verifiable externally.The authors connect this setting to production users who may query models multiple times.
- 3.2 How should one set on n and p?: The framework does not prescribe universal n and p values because acceptable extraction risk depends on the information being extracted, such as generic text versus PII.This flexibility supports context-specific decisions about extraction-risk tolerance.
4 Experiments
Experiments show that probabilistic extraction rates vary with query budget, target probability, model size, repetitions, and model family, while distinguishing memorization from chance generation.
- Overall model extraction risk: 9.04% is the maximum extraction rate for Pythia 2.8B with top-k sampling, versus 1.3% under greedy sampling on Enron.The maximum rate is nearly 7× the greedy rate.
- Overall model extraction risk: For low p, probabilistic extraction exceeds greedy extraction even at small n, while for high p and small n it can remain lower.For Pythia 2.8B, the rate approaches greedy extraction only after n > 169 at p = 0.999 and n > 17 at p = 0.5.
- Extraction risk across models: Probabilistic extraction reverses the model-risk comparison suggested by greedy sampling: GPT-Neo 1.3B exceeds Pythia 1B at every n and p despite a lower greedy rate.Greedy sampling would therefore rank Pythia 1B as riskier, whereas the probabilistic measure implies the opposite.
- Model size: Extraction rates increase with model size and training-example repetitions, and the probabilistic rate separates increasingly from the greedy rate as repetitions grow.Greedy rates for Pythia 1B, 2.8B, and 12B are 0.76%, 1.3%, and 3.07%, respectively.
- Model size: Pythia 12B has higher (n, p)-discoverable extraction than Pythia 2.8B at every n and p, with a larger gap from greedy extraction.The maximum-versus-greedy gap is 13% for Pythia 12B versus 7.74% for Pythia 2.8B.
- Validating (n, p)-discoverable extraction: Training-data extraction substantially exceeds generation of unseen test data, supporting memorization rather than happenstance as the source of observed matches.Even at p = 0.1 and very large n, test-data generation remains below 1% versus over 5% for training-data extraction.
5 Conclusion
The paper replaces one-shot greedy extraction with a probabilistic measure based on the queries needed to reach a target extraction probability. This yields more reliable, cost-free risk estimates and supports sensitivity-aware analysis.
- (n, p)-discoverable extraction measures how many queries are needed to extract a target at least once with probability p under a chosen sampling scheme.
- The measure provides more reliable extraction rates and model comparisons than greedy sampling, which can underestimate overall extraction and overestimate risk at low query budgets.
- The probabilistic measure can be computed with one query, adding no computational cost while providing more nuanced extraction-risk information.
- Practitioners can tune n and p to reflect different sensitivity thresholds, including contexts where rare PII leakages are problematic.
6 Limitations
The study measures extraction with a relatively benign API-only adversary and does not distinguish target sensitivity, leaving stronger attacks and sensitive-target-specific rates for future work.
- The analysis assumes an adversary with API access only and limited side information, while more powerful adversaries remain outside its scope.
- PII extraction is examined only cursorily through phone numbers, so extraction rates for other PII and sensitive targets require separate study.
A More examples of how greedy sampling can miss extraction
Examples show that greedy sampling can miss target extraction even when generated text is highly similar, whereas top-k sampling sometimes generates the target suffix.
- 9.74% target-suffix probability appears despite a greedy output differing from the target by only one directional word.
- 14.93% target-suffix probability is reported for the Greece example under top-k sampling.
- 9.09% target-suffix probability under top-k sampling accompanies a greedy output differing from the target in the Olympic year.
- 7.5% target-suffix probability under top-k sampling accompanies a greedy suffix with only 12% token edit distance from the target.
- Figure 8 compares greedy and top-k generations token-by-token, so shifted matching characters can still count as mismatches.
B Comparison to other extraction, reconstruction, and memorization definitions
The paper positions probabilistic extraction against alternative memorization measures, emphasizing practical estimation without retraining many models and highlighting distributional problems with rank perplexity.
- The approach targets production practicality, typical-user capabilities, and extraction risk without retraining multiple models.
- 1000-generation perplexity distributions vary across training examples and fit skewed Gaussians poorly, undermining rank-perplexity estimation here.
- Information-theoretic and counterfactual definitions can require many models, including hundreds for counterfactual memorization estimates.
- Prompt-optimization attacks search over multiple prompts per target and are more computationally expensive than this approach.
- Related work studies probabilistic extraction, PII leakage, reconstruction, canary memorization, and legal interpretations, but with different scopes or analyses.
C.2 Datasets
Experiments use multiple model families and datasets, primarily evaluating Pythia on Enron while extending tests to other subsets, proxies, and a held-out validation dataset.
- Pythia and GPT-Neo tests use Enron, Wikipedia, and GitHub subsets from The Pile, while Llama and OPT use Common Crawl proxies.
- The validation experiment compares (n, p)-discoverable extraction with generated Trek 2007 Spam classification test data.
- One query computes sequence probabilities and supports testing different prefix and suffix lengths without additional model queries.
- The framework can also extend verbatim extraction to non-verbatim matches using a user-chosen distance function and threshold.
D.1 An example instantiation with the Hamming distance
The paper instantiates non-verbatim probabilistic extraction with Hamming distance, treating suffixes within ε token substitutions of the target as successful extractions. Because enumerating all such suffixes is expensive, it estimates extraction probabilities from sampled outputs.
- Definition: Hamming distance defines successful extraction as generating a suffix within ε token substitutions of the verbatim target.The possible suffixes form S_ε, and the accepted generated texts append one member of S_ε to the target prefix.
- Computational cost: Direct computation is expensive because it requires enumerating every candidate suffix in S_ε and evaluating its probability.The number of candidates grows with suffix length, vocabulary size, and the allowed number of substitutions.
- Approximation: The empirical approximation generates n suffixes, estimates the target probability from the fraction matching the target, and converts that estimate into extraction probability.For non-verbatim extraction, each sampled suffix is checked by its Hamming distance to the target rather than exact equality.
- Approximation: Small n may provide incomplete coverage of S_ε, so drawing m > n samples can improve the estimate before computing the n-trial probability.The paper cautions that the combined approximation may be a poor stand-in for the full probability mass when n is small.
- Distance choices: Other distance functions, including Levenshtein distance, Jaccard distance, and transformed BLEU similarity, can replace Hamming distance.These alternatives change how insertions, deletions, substitutions, or sequence similarity are treated.
E Experiments with more Pythia model sizes on Enron
Additional Pythia sizes on Enron show that extraction rates generally scale upward with model size, with approximately doubled rates when parameter counts double. The appendix also compares maximum and greedy rates, highlighting a widening gap for larger models.
- Scaling with model size: Extraction rates approximately double across most n and p settings when the number of model parameters doubles.This result extends the Pythia analysis on 10,000 Enron examples.
- Experimental setup: The figure compares (n, p)-discoverable extraction rates across Pythia models using top-k sampling with k = 40 and T = 1 on Enron.It expands the earlier Figure 3 results.
F Extraction rates under different sampling schemes for Pythia 2.8B on Enron
For Pythia 2.8B on Enron, extraction rates depend strongly on sampling hyperparameters, n, and p, and the relationship is not strictly ordered across schemes. The appendix also connects suffix perplexity to sampling probability and shows that top-k and top-q can make many targets impossible to generate.
- Sampling schemes: Larger k, q, or temperature generally increases extraction rates as n grows, but the effect depends on p and no strict ordering is guaranteed.Token probabilities can rise or fall as sampling hyperparameters change, so rate comparisons across settings may reverse.
- Top-k sampling: At n = 1 and p = 0.1, k = 2 reaches approximately 1.5%, exceeding the below-1.3% rates for k = 40 and k = 80; larger-k rates later overtake it.For larger n, higher-k settings consistently produce higher extraction rates in the reported comparison.
- Top-q and temperature sampling: Top-q sampling shows the same broad pattern: larger q produces larger extraction rates as n increases, with gaps widening more slowly at larger p.Temperature sampling exhibits similar trends, with more consistent gaps at larger n.
- Practical comparison: Rates computed under one sampling scheme remain useful because top-k, top-q, and temperature rates can be cheaply recomputed across hyperparameters.These schemes are post-processing functions applied to the model’s token-logit distribution.
- Sampling support: Top-k and top-q distributions contain fewer than 10,000 examples because roughly 9,000 target suffixes have zero sampling probability, unlike random sampling.Under random sampling with T = 1, every token remains possible, whereas truncated schemes can exclude target tokens.
- Perplexity and probability: For top-k, low-perplexity suffixes are often almost surely sampled within 100 trials, while random sampling makes approximately 250 targets almost surely sampled.The analysis compares suffix perplexity distributions with probabilities of sampling each target within n = 100 trials.
H Experimental results over more datasets and model classes
Experiments beyond the main Pythia-on-Enron setting test the findings across additional datasets and model families. The appendix reports comparable analyses for Pythia on Wikipedia and GitHub, Llama on Common Crawl, and OPT on Common Crawl.
- Scope: The appendix broadens evaluation beyond Pythia models on Enron to additional datasets and model classes.It includes Pythia, Llama, and OPT experiments across the listed data subsets.
- Pythia: Figures 14 and 15 compare greedy and (n, p)-discoverable extraction for Pythia models on Wikipedia and GitHub.They cover 1B, 2.8B, 6.9B, and 12B models under top-k, top-q, and random sampling.
- Llama: Figure 16 compares greedy and (n, p)-discoverable extraction for 7B and 13B Llama models on Common Crawl.The comparison spans top-k, top-q, and random sampling schemes.
- OPT: Figure 17 compares greedy and (n, p)-discoverable extraction for 350M–6.7B OPT models on Common Crawl.The models are evaluated under top-k, top-q, and random sampling schemes.