How Many Documents in a Pile Actually Came From a Watermarked LLM? New Math for the Hardest Version of That Question.

Derives sharp statistical bounds on the fraction of edited-watermarked text in a corpus, with honest fragility analysis. The first paper to treat watermark prevalence estimation as a partial identification problem under adversarial editing.

Imagine you're a health inspector checking a city's water supply, but you can't test every tap — you sample. Worse, some pipes have been secretly rerouted (edited), diluting the signal. You can still bound how much contamination exists, but only if you're honest about what the rerouting can do to your detector. That's the mechanism here: not detecting watermarks in individual documents, but bounding the share of an entire corpus that was watermarked, after unknown edits have degraded the signal. The committed claim: for Gumbel-max and green-list (KGW) watermarks, this paper derives a power envelope — a theoretical ceiling on how well any detector can perform — indexed by three editing budgets (retention floor, entropy budget, in-place substitutions). The envelope yields an identified set that is sharp for the alternatives it dominates. At a watermarked share of 0.2, the exact-null bound lands at roughly [0.14, 0.38] with 2,000 documents. That's wide, but it's honest — and it's the first time anyone has produced finite-sample prevalence bounds under adversarial editing for these watermark families. The architecture is classical statistical inference, not ML. The core tool is a sequential coupling argument combined with a known least-favourable next-token distribution. This places the work in the family of partial-identification methods from econometrics (Manski-style bounds) transplanted into the watermark detection setting. The compute requirement is negligible — the hard part is the math, not the GPU hours. The paper distinguishes between an exact null (assuming the null distribution is known perfectly) and a calibrated null (estimated from an independent human reference sample), and the gap between these two regimes is where the fragility lives. Integrity is strong for a theory paper with this much simulation support. The authors test on OPT-1.3B and Qwen3-1.7B outputs, use 12,000 fresh human documents scored under three keys, and run resampling trials with random edits, substitutions, and paraphrases. All bounds covered in these trials. But the paper is admirably honest about two fragilities: LLM-paraphrased KGW pools fall below the envelope (meaning the envelope is conservative for that attack), and a null calibration error of just 0.01 — comparable to the largest deviation observed — is harmless at 2,000 documents but breaks exact-null coverage at 100,000. Code and results are public on GitHub. The ladder position is unusual because there isn't a direct competitor doing exactly this. Prior watermark work focuses on per-document detection (Kirchenbauer et al.'s KGW, Aaronson's Gumbel-max). Prevalence estimation under editing is a new question. The closest relatives are Manski's partial identification bounds in econometrics and recent work on distribution-free hypothesis testing. The paper doesn't claim to beat a SOTA — it defines the problem and provides the first rigorous answer. The milestone to watch is corpus scale. At 2,000 documents, the bounds cover even under adversarial conditions and null calibration error. At 100,000 documents, the exact null breaks and you need a calibrated null with a large reference sample. The practical threshold for regulatory auditors — "can I audit a platform's entire output?" — requires bounds that hold at millions of documents. Getting there means either tighter null calibration or watermarks with stronger post-edit signal, and the paper's framework gives you the exact numbers to track that gap. The obvious experiment not run: real-world adversarial paraphrasing at scale, using frontier models (GPT-4, Claude) as the paraphraser rather than the same-family models used here. The paper acknowledges that LLM paraphrases already push below the envelope for KGW. Testing against the strongest commercially available paraphrasers would either validate the bounds' robustness or reveal where they crack. The honest read: this is a compute and access limitation, not a strategic omission — the authors clearly know this is the next step and have built the framework to accommodate it.