How Short Can a Publicly Verifiable Watermark Be?

A watermark on AI-generated text is a hidden statistical pattern planted during generation so that someone can later check where the text came from. Most schemes are symmetric: the same secret key plants and checks the mark, so anyone who is given the checker can also forge it. Publicly verifiable watermarks separate the two roles, either with a digital signature or with a detector network that is hard to invert. Today they pay a steep price in length. The signature scheme of Publicly-Detectable Watermarking for Language Models needs about 1,000 tokens. The neural scheme UPV loses accuracy sharply near its decision threshold of $z \approx 3$. This note argues that the length problem is the same problem rare-event physicists face when they set sensitivity limits, and that the physics gives a precise answer.

The argument turns on one observation. If anyone can run the detector, a forger can generate many paraphrases of the content they want to spoof and keep the first one that passes. This is a look-elsewhere search run by the adversary. It is the same trials penalty that cut the Telescope Array hotspot from $5.1\sigma$ before correcting for the number of places searched to $3.4\sigma$ after (Telescope Array anisotropy). A public detector with false-positive rate $\alpha$ therefore offers roughly $\log_2(1/\alpha)$ bits of security against spoofing, whatever its internals. Real security requires $\alpha$ near $2^{-128}$. Stein's lemma then fixes the minimum text length at which that is statistically possible. We propose to derive this limit, test existing public schemes against it, and build a signature embedding that approaches it by borrowing the physicists' habit of unbinned, per-event likelihood fitting instead of hard all-or-nothing decoding.

Core Claim

The first claim concerns security. Suppose a forger can sample freely from a language model of similar entropy. Against a public detector with false-positive rate $\alpha$, $q$ queries give spoof success of roughly $1-(1-\alpha)^q \approx q\alpha$. Any detector that allows token-by-token hill climbing does worse still.

The second claim concerns length. Stein's lemma says that at fixed detection power the false-positive rate falls as $\alpha \approx e^{-nD}$, where $n$ is the number of tokens and $D$ is the per-token Kullback–Leibler divergence between the detector's statistic on watermarked and on human text. A target of $\lambda$ bits of security (forging costs about $2^{\lambda}$ tries) therefore needs

$$n^{*} \approx \frac{\lambda \ln 2}{\bar D}, \qquad \bar D \le \bar H,$$

where $\bar H$ is the average per-token entropy of the generator. The bound $\bar D \le \bar H$ holds because a sampler that does not distort the output distribution cannot carry more information per token than that token's randomness.

Put together, the length a public watermark needs is set mainly by security bits divided by usable entropy per token. Better detection power alone cannot buy security. PDWS's 1,000 tokens should then be explainable as $\lambda$, plus error-correction overhead, plus bits wasted on low-entropy tokens. The last two terms are what we try to remove.

Research Program

Theory. We will state and prove the sample-and-test spoofing bound and the Stein-type length bound. Both will be written for detectors that return a p-value, with $\bar D$ estimated per entropy stratum.

Audit of existing schemes. We treat each public scheme as a physics analysis and ask where it sits relative to $n^{*}$. For UPV, we compute the security implied by its operating threshold. At $z \approx 3$ to $4$, $\alpha$ is roughly $10^{-3}$ to $10^{-4}$, which is only about 10 to 14 bits. We then run two spoofers. One is the generic sample-and-filter spoofer. The other is a detector-guided decoder that uses the public LSTM score as a beam-search objective. UPV reports that "reverse training," meaning learning the generator back from the detector, rarely succeeds. That test does not cover guided search, which never needs to recover the generator.

Construction. PDWS already signs a hash of the first block, encodes the signature with an error-correcting code, and plants the bits by rejection sampling. We change two things.

First, planting becomes entropy-aware. Bits are placed only at positions the verifier can identify as high-entropy using a public reference model. The generator and verifier agree on those positions, so no bits are lost at deterministic tokens. This addresses the low-entropy failure noted for Bileve and PDWS.

Second, verification uses soft-decision decoding. Each recovered bit is weighted by the reference model's estimate of how much choice the generator had at that position. This carries over the finding in A Likelihood Based Approach for Watermark Detection that low-probability tokens carry more watermark information. It also mirrors how the CLEO $\tau\to\mu\gamma$ search recovered sensitivity with an unbinned per-event likelihood fit rather than coarse counting. A signature still either verifies or fails, so security remains cryptographic. The gain is in how few tokens are needed to recover it reliably.

That likelihood paper supplies the weighting method but is purely symmetric. It needs the secret key sequence at detection, so its optimality result says nothing about public verification.

Baselines

Unmodified PDWS. This is the naive reference point for signature-based public watermarks and the scheme our construction modifies. We run it on the same C4 news-like prompts, the same generator, and the same signature primitive, and we sweep text length. The file's only reported figure is that it "requires approximately 1,000 tokens" at about 0.01s verification (PDWS). Beating it means verifying at the same $\lambda$, with at most equal perplexity, in substantially fewer tokens. We commit to reporting the measured ratio rather than a target.

UPV. This is the strongest short-text public detector. It reports F1 "nearly 99%" on long C4 texts, with a sharp drop near $z\approx 3$ (UPV). We retrain it with its released design, using its roughly 43,000-parameter watermark network, on the same generator. We compare at matched false-positive rates rather than matched F1. The comparison that matters is forging cost. If guided search spoofs UPV in far fewer than $1/\alpha$ queries, UPV's short-text power does not correspond to security.

Bileve. This is the strongest hybrid, reporting F1 1.000 on unedited OPT-1.3B text (Bileve). We run its signature tier on OpenGen and LFQA with OPT-1.3B, as in its paper, and record tokens-to-verify alongside ours.

Symmetric ceilings. Symmetric detectors are not competitors, since they cannot be made public. They show how much short-text sensitivity public verification gives up:

Ablations. Two ablations isolate the key ingredient. One uses entropy-aware placement with hard decoding. The other uses soft decoding with uniform placement. We also include a shorter-signature variant of plain PDWS, explained below.

All schemes use the same generators (OPT-1.3B, LLaMA-7B), prompts, and tuning budget. Spoofers get equal query budgets.

Why not just…?

Why not just use a shorter signature in PDWS? This is a real threat. Much of a length reduction might come from the signature primitive alone. We will therefore run plain PDWS with the shortest signature we deploy and credit only the remaining gap to entropy-aware placement and soft decoding. The Stein bound predicts both effects are separable: $\lambda$ sets the numerator and wasted entropy lowers $\bar D$.

Why not just lower UPV's threshold or add a likelihood-ratio test on its outputs? A better test raises power but, by the sample-and-test bound, cannot raise security above $\log_2(1/\alpha)$ bits. The UPV audit measures this directly. If guided search does not beat $q\alpha$, then UPV is simply well tuned at its own security level, and we will report that.

Why not just use randomized key pools? Randomized key selection cut forgery on AdvBench from 68% to 16%, but its detector needs the secret keys. An informed attacker with a DistilBERT classifier also pushed forgery back to 65%. It does not answer the public-verification question.

Why not goodness-of-fit tests in low-entropy text? The goodness-of-fit study gets its low-temperature gains partly from repetition and is symmetric. We evaluate it only as an extra symmetric reference in the $T=0.3$ stratum.

Proposed Experiments and Decisive Checks

We generate from OPT-1.3B and LLaMA-7B on C4 news-like, OpenGen, and LFQA prompts. Lengths are 25 to 1,000 tokens. Prompts are grouped into strata by measured entropy, with $T=0.3$ and $T=1.0$ sampling to create low- and high-entropy regimes. Targeted spoofing uses AdvBench and HarmfulQ harmful contents.

The metrics are:

  • tokens needed for signature recovery with 95% probability at a fixed $\lambda$;
  • spoof success as a function of query count;
  • perplexity;
  • robustness to the substitution rates used in the likelihood paper.

Three results decide the proposal.

  1. Does the forging bound hold? Measured spoof success on UPV and on a z-score public detector should follow $q\alpha$ under sample-and-filter. The key question is whether guided decoding beats that line.
  2. Does the length bound predict reality? Tokens-to-verify, across entropy strata and schemes, should scale with $\lambda \ln 2/\bar D$ using per-token $\bar D$ estimated from held-out data. If the prediction fails badly, the physics analogy is wrong.
  3. Does the construction close the gap? Our construction should verify in clearly fewer tokens than both plain PDWS and its shorter-signature variant at matched $\lambda$ and matched perplexity, with the gain concentrated in low-entropy strata.