3.5 Application: Watermark Detection

Large language models generate text one token at a time. Let \(\mathcal {W}\) be the vocabulary and write \(w_{1:t-1}=(w_1,\ldots ,w_{t-1})\) for the tokens already generated. Conditional on this history (and on the prompt), an ordinary language model produces a next-token distribution \[ P_t=(P_{t,w})_{w\in \mathcal {W}}, \qquad \sum _{w\in \mathcal {W}}P_{t,w}=1, \] and samples \(w_t\sim P_t\). The distribution \(P_t\) is allowed to change with \(t\).

A watermark modifies the sampling procedure by introducing a secret key. From the key and the preceding text, the model constructs a pseudorandom variable \[ \zeta _t=A(w_{1:t-1},\mathsf {Key}) \] and generates the next token according to a deterministic decoder \[ w_t=S(P_t,\zeta _t). \] The key is later given to a verifier, who can reconstruct \(\zeta _{1:n}\) from the observed text \(w_{1:n}\). A desirable watermark is unbiased: for every next-token distribution \(P\) and every \(w\in \mathcal {W}\), \[ \mathbb {P}_{\zeta }\{S(P,\zeta )=w\}=P_w. \] Thus, after averaging over the pseudorandomness, watermarking does not change the next-token distribution. Its statistical signal is instead the dependence between \(w_t\) and \(\zeta _t\).

3.5.1 The testing problem

Following [12], watermark detection can be written as \[ \begin {aligned} H_0 &: w_{1:n}\text { is human-written or otherwise unwatermarked},\\ H_1 &: w_{1:n}\text { was generated by the watermarked model}. \end {aligned} \] The data available to the verifier are the pairs \((w_t,\zeta _t)_{t=1}^n\). The statistical distinction between the hypotheses is conditional independence versus coupling. If \(\mathcal {F}_{t-1}=\sigma (w_{1:t-1},\zeta _{1:t-1})\), the idealized model is \[ \begin {array}{ll} H_0: & w_t{\perp\!\!\!\perp} \zeta _t\mid \mathcal {F}_{t-1},\\[2pt] H_1: & w_t=S(P_t,\zeta _t), \end {array} \] where the pseudorandom variables behave as fresh independent draws from a known distribution. The null condition is justified by the secrecy of the key: a human who does not know the key cannot systematically coordinate a token with its corresponding pseudorandom value. Under the alternative, the decoder deliberately creates precisely such a coordination.

There is an important nuisance-parameter problem. The verifier usually does not know the prompt or the model’s next-token probabilities \(P_t\), and these probabilities vary across positions. Consequently, a likelihood-ratio test based on the full pairs \((w_t,\zeta _t)\) is generally unavailable. Moreover, merely detecting unusual word frequencies is not enough: unbiasedness makes the marginal law of \(w_t\) the same as that of ordinary sampling. The test must use the hidden dependence revealed by the key.

Formally, a detector is a test \(\phi (w_{1:n},\zeta _{1:n})\in \{0,1\}\), where \(\phi =1\) means that a watermark is declared. At level \(\alpha \), it should satisfy \[ \sup _{Q\in \mathcal {Q}_0}\mathbb {P}_{0,Q}(\phi =1)\leq \alpha , \] where \(\mathcal {Q}_0\) represents the many possible distributions of unwatermarked text. Subject to this false-positive guarantee, we want high power—equivalently, a small false-negative probability—over plausible sequences of unknown next-token distributions under \(H_1\).

3.5.2 Pivots and robust power

The key statistical idea is to replace \((w_t,\zeta _t)\) by a pivotal statistic \[ Y_t=Y(w_t,\zeta _t) \] whose null distribution is a known distribution \(\mu _0\), regardless of the unknown law of the token. Under the watermark, its conditional distribution \(\mu _{1,P_t}\) may depend on \(P_t\), but should be systematically shifted away from \(\mu _0\). The original problem is thereby reduced to \[ \begin {aligned} H_0 &: Y_t{\overset{\text{i.i.d.}}{\sim}} \mu _0,\\ H_1 &: Y_t\mid \mathcal {F}_{t-1}\sim \mu _{1,P_t}, \qquad P_t\in \mathcal {P}, \end {aligned} \] where \(\mathcal {P}\) is a chosen class of plausible next-token distributions. A score function \(h\) then gives the test statistic and rejection rule \[ T_n(h)=\sum _{t=1}^n h(Y_t), \qquad \phi _h=\mathbf {1}\{T_n(h)\geq c_{n,\alpha }\}, \] with \(c_{n,\alpha }\) equal to the \((1-\alpha )\)-quantile of \(T_n(h)\) under \(\mu _0\). Since this null law is known and contains no \(P_t\), the false-positive rate can be calibrated without access to the language model or its prompt.

The remaining design question is the choice of \(h\). For a distribution class \(\mathcal {P}\), define its worst-case false-negative probability by \[ \beta _n(h;\mathcal {P}) =\sup _{P_1,\ldots ,P_n\in \mathcal {P}} \mathbb {P}_{H_1}\{T_n(h)<c_{n,\alpha }\}. \] Thus the statistical objective is \[ \underset {h}{\operatorname {minimize}}\quad \beta _n(h;\mathcal {P}) \qquad \text {subject to}\qquad \mathbb {P}_{H_0}(\phi _h=1)\leq \alpha . \] For long text, one can equivalently compare how quickly \(\beta _n\) decays with \(n\). The paper formalizes this decay as a class-dependent efficiency and reduces the search for the best score to a minimax problem. The class \(\mathcal {P}\) is essential: if it contains completely deterministic next-token distributions, then the decoder has no sampling randomness through which to leave a watermark, and uniform detection can be impossible.