Language model watermarks embed a hidden statistical signal into generated text so that its origin can later be detected. A useful watermark should not affect the distribution of chosen tokens and should remain detectable even after the text has been edited.
The majority of LLM watermarkers have two components: (1) a sampler which chooses how to sample tokens from the underlying language model distribution to embed a statistical signal; and (2) a detector which, given possibly watermarked and edited text, computes a score for how likely the text was generated by a watermarker using the sampler.
Cyclic Tournament Sampling is a combination of the Tournament Sampler from Google DeepMind's SynthID-Text1 with the detector from Kuditipudi et al.2 DeepMind's SynthID-Text allows for more control and stronger signal than existing sampling methods while Kuditipudi et al. provides a detector that is strongly robust to text edits and insertions. By combining the two this project hopes to create a text watermarker that provides strong, tunable, statistical signal even under text deletions and insertions.
Code for this project can be found here
.The sampling approach for the Cyclic Tournament watermarker is very similar to that used by SynthID-text. At a high level, SynthID-text's tournament sampling works in the following way. First, we instantiate $m$ random functions $g_1, \ldots, g_m$; each of these is an independent pseudorandom function which is keyed by a random seed $r$ and returns a score for any token $x$ in the LLM vocabulary. After this, we sample $M = 2^m$ tokens (with replacement) from the underling LM distribution. We pair up the $M$ tokens uniformly and randomly; for each pair $x, x'$, we let $\mathop{argmax}_{y\in \{x, x'\}}g_1(y, r)$ proceed to the next round (ties broken arbitrarily). The next round repeats this process with $g_2$ instead of $g_1$. At the end we are left with a single sampled token.
The key change to sampling that this project makes to this approach is to alter how the random seed $r$ is picked. SynthID-text picks $r$ as a hash of a small context window of previous tokens. Kuditipudi et al. observe that such a choice makes sampling highly dependent on context and makes detection challenging under small text manipulations. We use Kuditipudi et al.'s alternative instead. In particular, we instantiate a vector $\xi\in \mathbb{R}^\ell$ of random keys which is stored and fixed by the watermarker once in advance. When generating token $x_t$ in a sequence, we use $\xi_{t \% \ell}$ as the key to feed into the $g_i$.
We use the detection approach of Kuditipudi et al. with a modified distance function to calculate scores for watermarked text. At a high level, Kuditipudi et al. checks how likely text $y$ is to be watermarked by looking at a scanning window of $\xi$ against $y$ and checking statistical signal at each window location; the advent of using $\xi$ as a random seed instead of a hash of recent context means that, even after insertions or rearrangements, some "patches" of text should still retain their statistical signal.
The main alteration of Kuditipudi et al. that this project makes is the modification of the distance function $d(\xi^{(i)}, y^{(j)})$ in their paper, where $\xi^{(i)}\in \mathbb{R}^{k}$ and $y^{(j)} \in \mathbb{R}^{k}$ are both contiguous blocks of random keys and text respectively. We use the scoring function from SynthID-text for the distance function; namely, $d(\xi^{(i)}, y^{(j)}) = \sum_{h = 1}^{k}\sum_{\tau = 1}^m g_\tau(y^{(j)}_h, \xi^{(i)}_h)$.
One note here on efficiency; if we naively compute the distance function for all subsequences $\xi^{(i)}, y^{(j)}$, we will end up with $O(|y|\ell k m)$. However, by precomputing the $\sum_{\tau = 1}^m g_\tau(y^{(j)}_h, \xi^{(i)}_h)$, we can reduce this to $O(|y|\ell k + y\ell m)$.
In our experiments, we find that tournament sampling is strong but still not as effective as the exponential sampling (Gumbel sampling) that Kuditipudi et al. use in their paper. To evaluate both watermarkers, we used Gemma-2-9b as the underlying watermarker; we used prompt lengths of 50 tokens and evaluation was done on the first 100 tokens of generated text (discarding generations which finished before this).
Aligned with Kuditipudi et al., we use reference distribution sizes of 5000 example prompts from the c4/realnewslike dataset. Evaluation was done on 1000 examples also from c4/realnewslike dataset. We use $m = 40$ tournament rounds.
Over the 1000 evaluation rounds, exponential sampling achieved 86.3% detection power at a 5% false-positive rate, while tournament sampling achieved 71.5%. The p-value distributions are summarized below.
Reference distributions took around 8 hours per model to gather and evaluation takes around 1 hour per model on Nvidia A100 GPUs. Compute costs for this project were offset by a BlueDot impact rapid grant.