2611.07888

Total: 1

#1 CountScan: Simultaneous Lower Bounds on Historical Watermark Matches over All Text Intervals [PDF] [Copy] [Kimi] [REL]

Author: Guanyu Chen

A provider holding a watermark key may audit an external document and choose passages after reading it. A bound computed for a fixed passage is not valid for a passage chosen after seeing the evidence. One remedy splits the evidence between selection and validation. We take the other route and make the statement hold for every interval at once. CountScan gives finite-sample lower bounds on the number of retained historical watermark matches, simultaneously over all text intervals and count thresholds. Its validity rests on one condition: given the auditor's information, the pivots of positions that are not history matches are conditionally super-uniform. This condition holds when generation uses the key only through the Gumbel-max rule and editors have no access to the key, so the guarantee covers edits that depend on the generated text when the calibrators are nonincreasing. Simultaneity raises the threshold by the logarithm of the document length; for a long interval this costs about that logarithm divided by the critical evidence value, in certified tokens. We give a finite-length expansion of the certified proportion, finite-sample rates for two-level rules with lower bounds of the same order within a pivot-only class, and an upper bound over a calibrator class. On pre-registered holdouts with OPT and Qwen base models at temperature one, CountScan certifies substantial counts; under heavy random edits it remains valid but loses most of its power.

Subject: Methodology

Publish: 2026-11-05 12:07:42 UTC