REVIEW 3 major objections 4 minor 1 cited by
Estimating near-verbatim extraction risk in language models with decoding-constrained beam search
T0 review · 3 major / 4 minor · reviewed 2026-08-03 · deepseek-v4-flash
Pith's one-line read A decoding-constrained beam search yields deterministic lower bounds on near-verbatim extraction risk at about 20 Monte-Carlo samples' cost.
desk verdict A genuinely useful lower-bound estimator with a clean proof; treat the cross-model comparisons as provisional until tightness is validated. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central object is top-k constrained beam search (k-CBS): standard beam search modified so that candidate expansion and probability scoring respect the top-k decoding distribution, and the final across-beam prune is omitted so all B·k complete candidates are returned with their exact conditional probabilities. The lower bound is then the sum of probabilities of returned candidates lying in the ε-ball of the target suffix, LB_{ε,dist} = Σ_{(ẑ,logp)∈F^(≤ε)} exp(logp), which is provably no larger than p^dist_{z,ε}. An ε-viability-pruned variant additionally prunes partial paths that can no longer finish within distance ε, using a monotone Hamming counter or a streamed, Ukkonen-banded Wagner-
What would settle it
Construct a small-vocabulary model and a known memorized suffix whose near-verbatim mass is deliberately spread across many low-probability paths, each below the 1/(B+1) survival threshold at some depth, so that the exact near-verbatim probability can be computed by enumeration. If exact p^dist_{z,ε} ≥ τ_min but k-CBS with B=20 returns a lower bound of zero, the concentration premise that makes the estimates useful is violated.
Extended reading notes
Core claim
The paper's central claim is that near-verbatim extraction risk can be lower-bounded cheaply and deterministically. For a target suffix z(suf) and distance budget ε, the near-verbatim extraction probability p^dist_{z,ε} is the total probability mass of all continuations within distance ε of z(suf). The paper constructs a beam search that expands only the top-k tokens at each step, records exact top-k renormalized probabilities, and returns all B·k terminal candidates without a final prune. Filtering these candidates by distance and summing their probabilities gives LB_{ε,dist} ≤ p^dist_{z,ε} (Equation 5). Because beam search concentrates on high-probability continuations, and memorized suffi
Load-bearing premise
The practical usefulness of the lower bound rests on the empirical premise that, for memorized sequences, most near-verbatim probability mass stays within the beam's top-B at every depth; only paths with cumulative probability above roughly 1/(B+1) are formally guaranteed to survive the prunes.
Editorial extensions
If this is right
- Near-verbatim extraction rates are markedly higher than verbatim rates; for example, one 32B model goes from 1.42% verbatim-extractable sequences to 2.57% at Levenshtein distance 5.
- Per-sequence risk can jump from zero verbatim probability to over 0.85 near-verbatim probability, so verbatim-only audits can miss the most leak-prone sequences.
- The gap between greedy and probabilistic near-verbatim measures grows with model size, meaning greedy methods undercount extraction more for larger models.
- Negative controls on held-out data stay near zero, supporting that the near-verbatim detections reflect training-data memorization rather than generic text similarity.
- The method's cost—comparable to about 20 Monte-Carlo samples per sequence—makes near-verbatim extraction measurement feasible at the scale of whole corpora.
Reading between the lines
- If the lower bound is typically tight on memorized text, k-CBS can serve as a cheap screening tool for copyright and privacy risk: auditors can rank sequences by near-verbatim mass without running 100,000 samples per sequence.
- The same decoding-constrained search idea could be adapted to other decoding schemes (nucleus sampling, temperature scaling) and other distance metrics, potentially extending the audit surface beyond token-level edit distances.
- A zero lower bound is not evidence of absence of risk; it only says the beam missed viable continuations. A responsible audit protocol would pair k-CBS with targeted Monte Carlo for high-prior-risk sequences that return zero.
- Because the lower bound is deterministic and reproducible for a fixed model and hyperparameters, it could be used as a per-model audit artifact that is stable across evaluations, unlike stochastic sampling estimates.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper introduces decoding-constrained beam search (k-CBS), a modification of beam search that scores candidates under top-k decoding and returns up to B·k complete continuations with their exact top-k probabilities. Filtering the returned continuations to those within Levenshtein or Hamming distance ε of a target suffix and summing their probabilities yields a deterministic lower bound on the near-verbatim extraction probability p^dist_{z,ε} (Eq. 5). The authors prove the validity of this lower bound (Theorem 12, Corollary 13) and demonstrate on OLMo2/Wikipedia and Llama2/Gatsby that k-CBS reports higher extraction rates, larger per-sequence risk, and model-size trends than verbatim probabilistic extraction, at a token-evaluation cost comparable to roughly 20 Monte Carlo samples. Held-out Wikipedia sequences serve as negative controls and remain flat.
Significance. If the empirical tightness of the lower bound holds across models and text types, this is a valuable efficiency result for memorization auditing: practitioners can get provably downward-biased estimates of near-verbatim extraction risk at far lower cost than MC sampling. The formal lower-bound proof, the deterministic output, the use of open models and public corpora, and the negative controls are concrete strengths. The central concern is that the paper's headline empirical comparisons — extraction rates, mass-gain CCDFs, verbatim-share distributions — are all comparisons of lower bounds, and the tightness of those lower bounds is calibrated on a single sequence. Because the paper itself concedes in Appendix C.2.3 that no distribution-free survival guarantee exists for typical τ_min-scale sequences, the scale-up patterns in Sections 5.1–5.2 are not yet established as properties of true extraction risk.
major comments (3)
- [§5.1, Figure 3] The verbatim probabilistic rate is computed with k-CBS at ε=0, i.e., a lower bound, even though Section 2 and Appendix A.2.3 state that verbatim p_z can be computed exactly with one teacher-forced forward pass. The headline comparison “2.57% vs 1.42%” therefore compares two lower bounds of different tightness, and the ε=0 baseline is unnecessarily loose. Please report the exact teacher-forced verbatim extraction rate and reframe the “increased extraction rate” claim against that exact number. If the exact rate is higher than 1.42%, the near-verbatim gain is smaller than stated.
- [§4.2, Eq. (5); Appendix C.2.3] The lower bound is provably valid, but its usefulness as a measure of extraction risk depends on the fraction of the ε-ball mass that k-CBS captures. Lemma 4 guarantees survival only for paths whose cumulative probability exceeds 1/(B+1)≈0.048 at every depth; for typical extractable sequences with p^dist≈τ_min=0.001, the paper explicitly states that no comparable guarantee exists without distributional assumptions. The single-sequence calibration in Figure 2 does not establish that the capture fraction is stable across model size, text type, or ε. Held-out controls rule out false positives but not downward bias. Please provide a multi-sequence calibration, e.g., comparing LB against high-sample MC or exact computation on a stratified sample across models and corpora, and report the distribution of LB/MC ratios.
- [§5.2, Figures 5–6] The claims that “risk increases scale with model size” and that verbatim share varies by model/text compare lower-bound-derived quantities. Since the tightness of LB is not shown to be invariant across model sizes, the CCDF shifts in Figure 5 and the verbatim-share patterns in Figure 6 could reflect estimator-bias variation rather than changes in true extraction risk. For the reported mass-gain statistics, please report capture-fraction diagnostics or, where feasible, upper-bound-based intervals (e.g., using the banked-mass upper bounds in Appendix E) so that the reader can judge whether the scale-up pattern is robust to the downward bias.
minor comments (4)
- [Algorithm 1, line 12] The early-termination condition is typeset in a garbled way: “if τmin and max( , logp)∈L t exp(logp)<τ min/(B·k)”. Please rewrite the predicate clearly, e.g., “if τ_min is provided and max_{(ẑ,logp)∈L_t} exp(logp) < τ_min/(B·k)”.
- [Figure 2 caption] The caption says “k-CBS cost 20 samples”; this should say “cost equivalent to 20 MC samples in token evaluations” and should emphasize that the 89.4% capture figure is for a single sequence.
- [Abstract / §1] The numbers “2.57% vs 1.42%” are described without the qualifier that they are lower-bound-based rates. Please state explicitly in the abstract and introduction that these are lower bounds, not exact rates.
- [Appendix E.2.2] The introduction of the Ukkonen band is clear, but the notation D[i,j] is used with both row and column indices in a way that occasionally conflicts with the beam depth variable t; please standardize the indexing to avoid confusion.
Circularity Check
No significant circularity: Eq. 5 is an explicitly labeled lower bound whose validity follows by subset monotonicity, and the practical tightness concern is an unproven assumption, not a circular derivation.
full rationale
The paper's central formal claim—Equation 5, LB_{ε,dist} = Σ_{(ẑ,logp)∈F^(≤ε)} exp(logp) ≤ p^dist_{z,ε}—is a subset-sum bound. Because k-CBS returns only continuations that are actually in the ε-ball under the top-k decoding distribution, the sum is a subset of the full ε-ball mass. This is a valid lower bound by construction, and the paper consistently labels it as a lower bound, not as an unbiased estimate or as equal to p^dist_{z,ε}. That is not circular in the harmful sense: the bound does not presuppose the extraction-risk conclusions it supports. The paper's experimental interpretation—that the returned LB values measure near-verbatim extraction risk across models—depends on an empirical tightness assumption: high-mass ε-viable continuations survive beam pruning. The paper itself concedes that Lemma 4 only guarantees survival for paths with cumulative probability > 1/(B+1) ≈ 0.048 at every depth, and that for typical extractable sequences with mass near τmin=0.001, 'we cannot provide a comparable guarantee... without distributional assumptions' (Appendix C.2.3). This is an acknowledged limitation of the method's utility, not a circularity in the derivation. Likewise, the rank-budget counting argument in Section 4 and Appendix C.2.3 gives necessary conditions for high-mass paths, not an assumption of the conclusion. The threshold τmin=0.001 and top-k k=40 settings are inherited from prior work by overlapping authors (Hayes et al., 2025b; Cooper et al., 2025). This is a self-citation, but it is not load-bearing for the validity of the lower-bound theorem; it affects the threshold used to declare extraction success in the experiments. The negative held-out controls and the single-sequence MC comparison in Figure 2 provide some independent empirical grounding, though they do not establish uniform tightness. Overall, the conceptual concern about estimator bias is a real robustness/correctness risk, but it does not reduce the derivation to its inputs by definition. Score 1 reflects the minor self-citation of experimental settings and the acknowledged tightness gap, not a circular central claim.
Assumptions & free parameters
free parameters (4)
- Beam width B =
20
- Edit tolerance ε =
5
- Extraction threshold τmin =
0.001
- Top-k size k =
40
assumptions (5)
- domain assumption Memorized suffixes carry unusually high conditional probability under θ, so beam search's high-mass region contains the near-verbatim ε-ball mass.
- domain assumption Lower-bound tightness is roughly constant across model sizes and text types.
- standard math Top-k renormalized chain conserves mass (frontier mass identity).
- standard math Pigeonhole/simplex rank bounds: a token of rank R has probability ≤ 1/R.
- standard math Wagner-Fischer recurrence and Ukkonen banding correctly compute Levenshtein distances.
Cite this review
Pith. "Pith review of Estimating near-verbatim extraction risk in language models with decoding-constrained beam search." pith.science (2026). https://pith.science/paper/FISNAD56
@misc{pith2026260324917,
author = {Pith},
title = {Pith review of: Estimating near-verbatim extraction risk in language models with decoding-constrained beam search},
year = {2026},
howpublished = {\url{https://pith.science/paper/FISNAD56}},
note = {Machine review of arXiv:2603.24917}
}
read the original abstract
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.
Figures
Figures from the paper (25 more)
Forward citations
Cited by 1 Pith paper
-
Probabilistic "Copies" in Generative AI Models
An LLM is an infringing copy of a work only when the work can be extracted from it with relatively little effort, so some models are copies of some works and no model is a copy of everything it trained on.
Reference graph
Works this paper leans on
-
[1]
Greedy-decoded extraction is a special case of probabilistic extraction: under ϕ=greedy , the per-step distribution is a point mass on the arg max token, so pz = 1 if and only if the generated continuation equals the target suffix (otherwise pz = 0), recovering Equation 10
-
[2]
For stochastic ϕ, a single-run, one-shot equality indicator1 [generateθ,ϕ (z1:a, T) = za+1:a+T ]is a Bernoulli random variable with meanp z
-
[3]
Computing pz without sampling (teacher-forced scoring).To evaluate pz for verbatim extraction, we do not need to generate any tokens
In practice, it is unnecessary to actually generate any continuations to estimate pz; teacher-forced scoring (described below) computes pz directly from the logits y in a single forward pass (Cooper et al., 2025). Computing pz without sampling (teacher-forced scoring).To evaluate pz for verbatim extraction, we do not need to generate any tokens. Instead, ...
2025
-
[4]
, T− 1}; existence)If T≥ 3and |V| ≥T, then there exists b∈V T such that for everyεwith2≤ε<T, BHam ε (b)⊊B Lev ε (b)
(Strictness for ε∈ {2, . . ., T− 1}; existence)If T≥ 3and |V| ≥T, then there exists b∈V T such that for everyεwith2≤ε<T, BHam ε (b)⊊B Lev ε (b)
-
[5]
(Saturation)For every b∈V T, every ε≥T , and dist∈ {Hamming, Levenshtein}, Bdist ε (b) = VT. Proof. First, note that if b and c differ at r=Hamming(b , c) positions, then performing those r position-wise substitutions is a valid edit script from b to c of cost r (Equation 15). By the definition of the Levenshtein distance (Equation 16), Levenshtein(b, c)≤...
-
[6]
And so c∈B Lev ε (b)—i.e., every member of BHam ε (b) must also be a member of BLev ε (b)
(Inclusion)By Equation 22, if c∈B Ham ε (b), then Levenshtein(b, c)≤Hamming(b , c)≤ε . And so c∈B Lev ε (b)—i.e., every member of BHam ε (b) must also be a member of BLev ε (b). 2.(Equality forε∈ {0, 1})Forε=0 bothε-balls are{b}. For ε= 1, this corresponds to Levenshtein(b, c)≤ 1 with b, c∈V T. In this case, the single edit cannot be an insertion or delet...
-
[7]
(Strictness for ε∈ { 2, . . ., T− 1}; existence)The reason BHam ε (b) can be strictly contained in BLev ε (b) is that Levenshtein distance allows an insertion-deletion pair to “shift” tokens and realign two sequences. For example, if T≥ 3 and the vocabulary V is large enough to choose pairwise distinct tokensv 1, . . . ,vT, consider b := (v1,v 2, . . . ,v...
-
[8]
And so, by Equation 22, Levenshtein(b, c)≤Hamming(b , c)≤T
(Saturation)For any c∈V T, by definition, Hamming(b, c)≤T , since there are at most T mismatched positions. And so, by Equation 22, Levenshtein(b, c)≤Hamming(b , c)≤T . Therefore, once ε≥T , every c is included; the ε-ball stabilizes to be every sequence inVT. C An intuition for more efficient near-verbatim probabilistic extraction Even though the set of ...
Show all 36 references
-
[9]
samples independently either hits or misses the ε-ball
There is no guarantee MC will sample from a high-probability ε-ball.Each of the M i.i.d. samples independently either hits or misses the ε-ball. The probability ofneverhitting it inMsamples is Pr missB dist ε (z(suf)) = (1−p dist z,ε )M. (24) 23 Preprint. To guarantee a miss p...
-
[10]
no extraction
Even when MC hits the ε-ball, the estimate ˆpdist z,ε can be unreliable.Each term in Equation 23 is a Bernoulli random variable with success probability pdist z,ε . Because ˆpdist z,ε is the mean ofMsuch i.i.d. variables, its variance and standard error are Var[ ˆpdist z,ε ] =...
1976
-
[11]
For each partial history ˆzin the beam ( z(pre)∥ˆz(cont) <t , the prefix concatenated with the generated continuation so far), the model produces next-token probabilities Prθ( ˆz|ˆz) over ˆz∈V
-
[12]
25 Preprint
Each beam element is expanded by each of these tokens, yielding candidate children ˆz′ =ˆz∥ ˆzwith updated scores logp(ˆz′) =logp(ˆz) +log Pr θ ( ˆz|ˆz). 25 Preprint
-
[13]
This is done for efficiency, i.e., to prevent explosive blow-up of the number of sequences under consideration
For the next iteration (t+ 1), beam search performs an across-beam prune to keep only the B unique highest-scoring partial sequences and discards the rest. This is done for efficiency, i.e., to prevent explosive blow-up of the number of sequences under consideration. After T s...
-
[14]
For each partial history ˆzin the beam, the model θ and top- k decoding ϕ produce next-token probabilities Prθ,ϕ ( ˆz|ˆz)over only the top-k-token set, ˆz∈S t(ˆz)
-
[15]
Each beam element is expanded by each of these k tokens, yielding B·k candidate children ˆz′ =ˆz∥ ˆzwith updated scores logp(ˆz′) =logp(ˆz) +log Pr θ,ϕ ( ˆz|ˆz)
-
[16]
After T steps, the algorithm returns all B·k complete continuations (i.e., without performing a final across-beam prune)
For the next iteration (t+ 1), beam search performs an across-beam prune to keep only theBunique highest-scoring partial sequences and discards the rest. After T steps, the algorithm returns all B·k complete continuations (i.e., without performing a final across-beam prune). S...
2016
-
[17]
Token rank.At most steps t, the true suffix token zt lies in the model’s top-k set, and deviations are rare enough that the full continuation remains withinB dist ε (z(suf))
-
[18]
Beam dominance.The verbatim path and/or its near-verbatim variants maintain cumu- lative log-probabilities that stay within the beam’s top-B at each depth, so they survive all across-beam prunes. We formalize these conditions quantitatively in Appendix C.2.3 below and show tha...
2022
-
[19]
Select the top-B candidates from the top-k tokens →L 1 (no additional forward pass needed)
Prefill.Process the a prefix tokens (L0, a single element) in one forward pass, producing logits for the first suffix position. Select the top-B candidates from the top-k tokens →L 1 (no additional forward pass needed). Cost:atoken evaluations
-
[20]
up to B·k
Decode steps t= 1, . . ., T− 1.Compute logits for each element of Lt (|Lt| token evaluations), expand each by the top-k tokens (B·k candidates), and prune to the top- B→L t+1. At the final step ( t=T− 1), return all B·k candidates without pruning (Appendix D). Cost: ∑T−1 t=1 |...
2025
-
[21]
Pruning.Pool all children from the current beam and (aside from the same EOS policy ask-CBS) retain them according to one of the following rules: • Variable-width beam (full nucleus expansion).Keepallchildren S ˆz∈beamCt(ˆz; p); in variable-width mode (B=∞), the step-tbeam car...
2025
-
[22]
Descendant of a banked node: its mass is bounded bybank, since the total mass of all depth-Tdescendants of a banked ancestor equals that ancestor’s mass (Lemma 9)
-
[23]
Descendant of a Hamming-pruned node: non-ε-viable by Hamming monotonicity, so it cannot contribute top Ham z,ε
-
[24]
looks bad
Descendant of an EOS-terminated node: cannot produce a T-length continuation and thus cannot contribute top Ham z,ε . Since only categories (a) and (b) can contribute to pHam z,ε , we have pHam z,ε ≤LB ε,Ham +bank= UBε,Ham. As with baseline k-CBS (Appendix D.2), the optional τ...
1985
-
[25]
, jmax(t+1) (left to right) using Equation 48, treating any out-of-band predecessor as +∞
Fill D[t+ 1, j] for j=j min(t+1), . . ., jmax(t+1) (left to right) using Equation 48, treating any out-of-band predecessor as +∞. This keeps the recurrence exactly consistent with Wagner-Fischer. - For instance, when j=jmin(t+ 1)=0, the → insert predecessor D[t+ 1, −1] and the...
-
[26]
Prunethis partial path immediately if minj∈[jmin(t+1),jmax(t+1)]D[t+ 1, j]>ε (Lemma 17); otherwise, carry its banded row forward as the new state. This keeps a beam item’s per-child update cost and memory both O(ε)—the same order of bookkeeping overhead as the Hamming-pruned v...
1999
-
[29]
Provincial Board✓ ✓ ✓ ✓ ✓ ✓
-
[30]
98th Academy Awards✓ ✓ ✓ ✓ ✓
-
[31]
Maguindanao del Sur Provincial Board.This page was created in 2025 (i.e., makes sense it would be pulled in during curation of held-out data), but the extracted text is a boilerplate template describing Philippine provincial board elections. From manual investigation using the...
2025
-
[32]
List of submissions to the Nth Academy Awards
98th Academy Awards – Best International Feature Film submissions.This page was created January 31, 2026—well after training cutoff. However, the extracted text is identical or near-identical to boilerplate shared across all “List of submissions to the Nth Academy Awards” page...
2026
-
[33]
The template structure and stock phrases (track descriptions, race numbering) are widely duplicated
2015 WinStar World Casino & Resort 350.This NASCAR Truck Series race page was created January 10, 2024 (after the cutoff), but the extracted text follows the same tem- plate used across hundreds of NASCAR race articles, many of which predate the train- ing cutoff (e.g., the 20...
2015
-
[34]
b z(suf):rought the Batman to the forefront of public consciousness
Batman in popular culture.This page was created in December 2025, but the extracted text exists on multiple fan wikis dating to 2019, and thus plausibly was included in Common Crawl (and therefore the training data). It also contains aGuardianquote about Batman that existed ve...
2025
-
[35]
unlocked
Finnmark (Storting constituency).This page was created September 29, 2024. The extracted text is boilerplate shared across all 19 Norwegian Storting constituency pages (that we found through manual Wikipedia API search). The earliest of these (Oslo) was created August 2021, wi...
2024
-
[749]
For the baseline runs, we also manually examine outputs that surpassτmin but are not within Levε= 5 of the target suffix
In general, tighter pruning frees beam slots for more viable candidates at that specific distance, revealing (relatively)∼1–2% more extraction. For the baseline runs, we also manually examine outputs that surpassτmin but are not within Levε= 5 of the target suffix. The results...
2022
-
[1974]
running mismatch counter ≤ε
(with Ukkonen’s criterion (Ukkonen, 1985)) requires O(ε) time and O(ε) memory per partial path per step, totaling O(B k Tε) time and O(B kε) peak memory across the beam (reduced to O(Bε) after each across-beam prune). This is purely bookkeeping—no extra forward passes through ...
1985
-
[2024]
We thenreservoir sampled11 100,000 pages that fit these conditions from the whole range of Wikipedia pages in this time frame, de-duplicating by page ID
For each batch of 500 creation events, we checked the page lengths via prop=info and kept pages with ≥8,000 bytes of wikitext. We thenreservoir sampled11 100,000 pages that fit these conditions from the whole range of Wikipedia pages in this time frame, de-duplicating by page ...
2024
Reviewed August 3, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.