The Finite-Sample Cost of Adaptivity in Watermark Detection

A watermarked language model leaves a faint statistical fingerprint on every token it writes. Human edits and paraphrasing replace many of those tokens with unmarked ones, so the detector must find a small, weak excess of evidence buried in noise. Statisticians have a mature theory for exactly this "needle in a haystack" problem. Its central promise is that adaptive tests can detect the signal as well as a test that already knew how sparse and how strong it was. The promise is proved only as the number of observations goes to infinity. Real watermark checks run on 20 to 400 tokens, which is the regime where the empirical robustness benchmark of Watermark under Fire finds detection breaking down on 20–40 token snippets.

We propose to measure what adaptivity actually costs at these lengths. For each combination of model, temperature, edit type, edit rate and text length, we compare two detectors at a fixed 1% false positive rate. The first is an "oracle" that is handed the single best test statistic for that condition. The second is a fully adaptive detector that must choose blindly. We then ask two things. Does the gap between them shrink with length the way the theory implies? Do the theory's predictions about which statistics fail, and where, hold on real watermarked text? The practical output is a detector that is exactly calibrated at every length, with a measured power loss relative to the oracle. The scientific output is the first quantitative check of the asymptotic theory of rare, weak signal detection on a real deployment problem.

Core Claim

Adaptive detection theory says that ignorance of signal sparsity and strength is asymptotically free. Higher criticism for detecting sparse heterogeneous mixtures shows that Higher Criticism (HC) reaches the optimal detection boundary without knowing either quantity. HC is a test that scans the sorted p-values for an excess of small ones, standardized at each threshold. Optimal Detection of Sparse Mixtures Against a Given Null Distribution and the exact Berk-Jones analysis of On the exact Berk-Jones statistics prove similar results for related statistics. Watermark detection inherits this framing directly. Robust Detection of Watermarks for Large Language Models Under Human Edits recasts edited-text detection as a sparse mixture problem and proves its truncated goodness-of-fit test, Tr-GoF, is adaptive and asymptotically optimal.

Two empirical results make the asymptotic picture questionable. On the Empirical Power of Goodness-of-Fit Tests in Watermark Detection finds that the winning statistic changes with regime. LORD-GoF reports that Chi-squared dominates at low entropy and Anderson-Darling at medium entropy. If adaptivity were free in practice, the choice of statistic would not matter this much.

Our claim is twofold. First, the finite-sample cost of adaptivity is measurable, depends on regime, and is the right quantity to report. Second, it can be made small by a simple, exactly calibrated combination of a theory-chosen family of statistics. We define the cost at length $n$ and condition $c$ as

$$\Delta(n, c) = \max_{k} \mathrm{Power}_k(n, c) - \mathrm{Power}_{\mathrm{adapt}}(n, c).$$

Here $k$ ranges over a fixed set of candidate statistics, and each $\mathrm{Power}_k$ is the true positive rate at an exact 1% false positive rate. $\mathrm{Power}_{\mathrm{adapt}}$ is the true positive rate of the blind detector at the same false positive rate. Asymptotic theory predicts that $\Delta \to 0$ within the sparse-mixture model. Nobody has measured how fast it shrinks, or whether it shrinks at all once the departures from that model in real text are taken into account.

Research Program

The construction rests on one property of unbiased watermarks such as Gumbel-max. Given the secret key, each token yields a "pivotal" p-value, meaning one whose distribution under the null is known exactly regardless of the language model: uniform on [0,1] for human-written text. Any statistic computed from these p-values can therefore be calibrated by simulating uniform draws at the exact observed length. No asymptotic approximation is needed. This also removes the finite-sample instability of HC's $\sqrt{t(1-t)}$ denominator that Moscovich et al. warn about, because the critical value is simulated rather than approximated.

Repeated contexts break exact uniformity, since a repeated n-gram context reproduces the same pivot. The low-temperature repetition effect reported by the empirical-power paper sits exactly on this fault line. We therefore run every calibration twice. One version deduplicates repeated contexts. The other keeps duplicates and calibrates against real human C4 text scored with the same key. A detector counts only if its false positive rate on held-out human text stays at the 1% target.

The candidate family is chosen to cover the failure modes the theory identifies:

The adaptive detector takes the minimum of the members' calibrated p-values. Its own null distribution is again simulated at length $n$, so the combined test is exact. This is deliberately the simplest adaptive scheme. Section 4 of the research file suggests entropy-based switching between statistics. We include that as a competitor rather than as our method.

To connect real conditions to the theory, we place each condition in the two-parameter sparsity–strength plane. Sparsity comes from the measured fraction of surviving watermarked tokens, written as $\epsilon = n^{-\beta}$ to define $\beta$. Strength comes from the per-token signal under the alternative, which we compute from the model's own next-token distributions. This lets us overlay the Donoho–Kipnis impossibility curve on the empirical results and test whether HC fails where the curve says it should.

Proposed Experiments

We follow the protocol of the empirical-power study so that our numbers are directly comparable to it:

  • Text: C4 and ELI5 prompts.
  • Models: OPT-1.3B, OPT-13B and Llama 3.1-8B.
  • Watermarks: Gumbel-max, inverse-transform and SynthID.
  • Temperatures: 0.1 to 1.0.
  • Lengths: 20, 50, 100, 200 and 400 tokens. The empirical-power study does not cover the shortest of these, so the short-text regime is new.
  • Edits:
  • WordNet substitution, random insertion and deletion at controlled rates, following Li et al.
  • Information-rich removal of the strongest signals, following the empirical-power study.
  • The WATERPARK paraphrase and stacked attacks from Watermark under Fire.

We add a semi-synthetic arm in which pivots are drawn from real model next-token distributions with an exactly dialed edit fraction. This gives clean coordinates in the sparsity–strength plane while keeping realistic entropy profiles. Metrics are true positive rate at an exact 1% false positive rate, the cost $\Delta(n,c)$ with bootstrap intervals, and wall-clock time per document.

Baselines

The naive reference point is the sum-based detector for each scheme: Aaronson's score for Gumbel-max, and the corresponding summed scores for inverse-transform and SynthID. Li et al. show this detector collapses under edits because noise tokens add up linearly. It is run on identical texts with an exact simulated threshold, so it is not handicapped by its calibration. Beating it is necessary but not interesting.

The strongest existing competitor is the Chi-squared goodness-of-fit test, which is the strongest test in the empirical-power study. That paper reports a false negative rate of 2.9% for Chi-squared, against 15.1% for the best baseline, at temperature 0.3 with 400 Gumbel-max tokens. It also reports an error of 0.9% for Chi-squared versus 94.5% for the baseline under 50% information-rich removal on SynthID. We reproduce these two cells first as a sanity check. The adaptive detector must then match Chi-squared within bootstrap error in its winning regimes, and strictly beat it in at least one regime family, such as medium entropy, short texts, or paraphrase.

Tr-GoF is the strongest theoretically motivated adaptive competitor. We found no reported numeric result on Lacuna for Tr-GoF under the protocol above, so we rerun it with its published truncation, giving it the same exact calibration. Maximal $L_2$ thresholding has never been run on watermark text; no reported result was found on Lacuna for it in this setting. It receives the same threshold grid size as the other scanning statistics.

The oracle is reported both on test data and on a held-out selection split. The test-data version is an upper bound. The held-out version is the honest "tuned single statistic" competitor.

Three ablations isolate the proposal's ingredients:

  • Calibration ablation: asymptotic critical values versus exact simulated ones, which isolates how much short-text failure is a calibration artifact.
  • Membership ablation: removing the moderate-signal and global members, which tests whether theory-chosen coverage matters.
  • Selection ablation: replacing min-p combination with entropy-based switching, using entropy estimated from the scoring model.

Why not just…?

Why not just use the sum-based score? It is cheap and well understood. However, the 94.5% error reported by the empirical-power study under information-rich removal, and Li et al.'s dilution argument, show that it fails under edits. Our results report it in every cell, so the size of its loss at short lengths will be visible directly.

Why not just use Chi-squared everywhere? This is the real threat. It already wins the headline cells. LORD-GoF also reports Anderson-Darling ahead at medium entropy, but if Chi-squared's deficit there is negligible, then the adaptive detector buys nothing. Our results settle this cell by cell. If $\Delta$ for Chi-squared alone is within error of $\Delta$ for the combination across all conditions, we will report that as the finding: the theory's adaptivity is unnecessary in practice and one fixed test suffices.

Why not just switch statistics by estimated entropy? This is the natural reading of Gap 3, and it is included as an ablation. Entropy is estimated with error. Edit rate, which also determines the best test, is not observable from entropy at all. The selection ablation measures whether switching loses power relative to min-p combination on mixed-edit conditions.

Why not train a neural detector? WATERPARK finds neural detectors more brittle and more prone to false positives under paraphrase than statistical scoring. Such detectors also offer no exact false positive guarantee at a given length. We therefore exclude them from the main comparison and cite this evidence rather than rerun it.

Decisive Checks

Four results decide the outcome:

  • Calibration: the false positive rate on held-out human C4 text stays at or below 1% at every length for every detector, both with and without deduplication. Any detector failing this is discarded.
  • Rate of shrinkage: $\Delta(n,c)$ shrinks with $n$, and its fitted decay is reported per regime. If $\Delta$ stays flat or grows between 50 and 400 tokens, the asymptotic adaptivity claim does not transfer to this domain.
  • Impossibility curve: in the semi-synthetic arm, HC's power collapses below the plotted Donoho–Kipnis curve, while sum of squares or $L_2$ thresholding retain power there. This is a direct finite-sample test of the impossibility theory.
  • Practical gain: on the 20–50 token WATERPARK snippets and stacked attacks, the exactly calibrated adaptive detector improves true positive rate over Chi-squared and Tr-GoF at 1% false positive rate. If it does not, we report that no gain exists in the regime where practitioners most need one.