Saved in:
| Main Authors: | , , , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2603.24917 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908914328535040 |
|---|---|
| author | Cooper, A. Feder Lemley, Mark A. De Sa, Christopher Duesterwald, Lea Casasola, Allison Hayes, Jamie Lee, Katherine Ho, Daniel E. Liang, Percy |
| author_facet | Cooper, A. Feder Lemley, Mark A. De Sa, Christopher Duesterwald, Lea Casasola, Allison Hayes, Jamie Lee, Katherine Ho, Daniel E. Liang, Percy |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_24917 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Estimating near-verbatim extraction risk in language models with decoding-constrained beam search Cooper, A. Feder Lemley, Mark A. De Sa, Christopher Duesterwald, Lea Casasola, Allison Hayes, Jamie Lee, Katherine Ho, Daniel E. Liang, Percy Computation and Language Machine Learning 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. |
| title | Estimating near-verbatim extraction risk in language models with decoding-constrained beam search |
| topic | Computation and Language Machine Learning |
| url | https://arxiv.org/abs/2603.24917 |