# Estimating near-verbatim extraction risk in language models with decoding-constrained beam search

arXiv: https://arxiv.org/abs/2603.24917 · HTML: https://mlsanity.com/paper/2603.24917/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 50 references that are in the map.
- First posted on arXiv 26 Mar 2026.

## Builds on (most cited first, 21 of 21)

- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [LLaMA: Open and Efficient Foundation Language Models](https://mlsanity.com/paper/2302.13971/) (2023)
- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [Neural Machine Translation by Jointly Learning to Align and Translate](https://mlsanity.com/paper/1409.0473/) (2014)
- [Gemini 1.5: Unlocking multimodal understanding across millions of tokens of context](https://mlsanity.com/paper/2403.05530/) (2024)
- [Sequence to Sequence Learning with Neural Networks](https://mlsanity.com/paper/1409.3215/) (2014)
- [The Curious Case of Neural Text Degeneration](https://mlsanity.com/paper/1904.09751/) (2019)
- [The Pile: An 800GB Dataset of Diverse Text for Language Modeling](https://mlsanity.com/paper/2101.00027/) (2020)
- [Gemma 2: Improving Open Language Models at a Practical Size](https://mlsanity.com/paper/2408.00118/) (2024)
- [Dolma: an Open Corpus of Three Trillion Tokens for Language Model Pretraining Research](https://mlsanity.com/paper/2402.00159/) (2024)
- [Scalable Extraction of Training Data from (Production) Language Models](https://mlsanity.com/paper/2311.17035/) (2023)
- [2 OLMo 2 Furious](https://mlsanity.com/paper/2501.00656/) (2024)
- [Diverse Beam Search: Decoding Diverse Solutions from Neural Sequence Models](https://mlsanity.com/paper/1610.02424/) (2016)
- [Talkin' 'Bout AI Generation: Copyright and the Generative-AI Supply Chain](https://mlsanity.com/paper/2309.08133/) (2023)
- [Extracting memorized pieces of (copyrighted) books from open-weight language models](https://mlsanity.com/paper/2505.12546/) (2025)
- [Exploring the limits of strong membership inference attacks on large language models](https://mlsanity.com/paper/2505.18773/) (2025)
- [The Files are in the Computer: On Copyright, Memorization, and Generative AI](https://mlsanity.com/paper/2404.12590/) (2024)
- [Extracting books from production language models](https://mlsanity.com/paper/2601.02671/) (2026)
- [Machine Unlearning Doesn't Do What You Think: Lessons for Generative AI Policy and Research](https://mlsanity.com/paper/2412.06966/) (2024)
- [Report of the 1st Workshop on Generative AI and Law](https://mlsanity.com/paper/2311.06477/) (2023)
- [Machine Learners Should Acknowledge the Legal Implications of Large Language Models as Personal Data](https://mlsanity.com/paper/2503.01630/) (2025)

## Built on by (most cited first, 1 of 1)

- [Extractable Memorization From First Principles](https://mlsanity.com/paper/2607.12649/) (2026)

## Abstract (arXiv)

Recent work shows that standard greedy-decoding extraction methods for quantifying memorization in LLMs miss how extraction risk varies across sequences. Probabilistic extraction -- computing the probability of generating a target suffix given a prefix under a decoding scheme -- addresses this, but is tractable only for verbatim memorization, missing near-verbatim instances that pose similar privacy and copyright risks. Quantifying near-verbatim extraction risk is expensive: the set of near-verbatim suffixes is combinatorially large, and reliable Monte Carlo (MC) estimation can require ~100,000 samples per sequence. To mitigate this cost, we introduce decoding-constrained beam search, which yields deterministic lower bounds on near-verbatim extraction risk at a cost comparable to ~20 MC samples per sequence. Across experiments, our approach surfaces information invisible to verbatim methods: many more extractable sequences, substantially larger per-sequence extraction mass, and patterns in how near-verbatim extraction risk manifests across model sizes and types of text.