SynthID: A Tournament Without the Matches
6 min read
Watermarking helps us identify AI-generated writing. Ironically, the models have such a distinctive voice that I often feel I can spot it already. Nonetheless, there is some cool math behind doing this statistically.
The goal of distortion-free watermarking is to draw from the model’s actual distribution while making the draw correlated with a hidden random variable. If you see only the draw, it has the model’s distribution because it really came from that distribution. But if you also know the hidden randomness, you can test for the correlation.
We’ll analyze SynthID-Text, which Google uses in Gemini. Anthropic recently adopted a version of the method for Claude. Its sampling rule is a tournament: tokens compete using secret random scores, and the winner becomes the next token.
The Tournament View
Fix the text generated so far, and let \(p_0(x)\) be the model’s distribution over the next token \(x\) in a vocabulary \(V\). Start by drawing \(2^m\) candidate tokens independently from \(p_0\). We will run an \(m\)-round tournament, pairing off the remaining candidates at each round until one winner remains.
Here is where the hidden randomness enters. In round \(\ell\), assign every token \(x\in V\) an independent fair bit \(g_\ell(x)\in\{0,1\}\). A token with score one beats a token with score zero; a fair coin settles ties. The assignment is shared across all matches in that round, so two copies of the same token receive the same score. Each new round gets a fresh assignment.
Averaging over the new bits and the tie-breaking coin, either contestant in a match has probability \(1/2\) of advancing, whatever the two tokens are. Thus a randomly selected winner has the same distribution as a randomly selected contestant. Repeating this argument through the rounds, the final winner still has distribution \(p_0\).
For a particular assignment, though, score-one tokens are favored. The graphic follows this change in distribution through two rounds; clicking a score changes the assignment.
To detect the watermark later, we need to reconstruct those assignments. SynthID generates them from a secret key, the recent text, the candidate token, and the round. Someone with the key can recover the scores of the emitted tokens and check whether they are unusually high.
The computational problem is that playing the tournament takes \(2^m\) candidates for a single output token. Thirty rounds would require more than a billion candidates. Instead, we can calculate the winner’s distribution directly.
The Tournament in Closed Form
Fix all the score assignments, and let \(p_{\ell-1}\) be the distribution of a token entering round \(\ell\). Write \(\mu_\ell=\sum_{y\in V}p_{\ell-1}(y)g_\ell(y)\) for the probability that an opponent has score one.
Claim: The distribution after one round is
\[\begin{align*} p_\ell(x)=p_{\ell-1}(x)\bigl(1+g_\ell(x)-\mu_\ell\bigr). \end{align*}\]
Proof
Against an opponent \(y\), the probability that \(x\) wins is
\[\begin{align*} \frac{1+g_\ell(x)-g_\ell(y)}{2}. \end{align*}\]
This is one when the scores are \((1,0)\), zero when they are \((0,1)\), and \(1/2\) when they agree. Average over the opponent to obtain
\[\begin{align*} \Pr(\text{first slot wins}\mid\text{first token is }x) &=\sum_{y\in V}p_{\ell-1}(y)\frac{1+g_\ell(x)-g_\ell(y)}{2}\\ &=\frac{1+g_\ell(x)-\mu_\ell}{2}. \end{align*}\]
The winning \(x\) can come from either slot. Each slot contains \(x\) with probability \(p_{\ell-1}(x)\), so
\[\begin{align*} p_\ell(x) &=2p_{\ell-1}(x)\frac{1+g_\ell(x)-\mu_\ell}{2}\\ &=p_{\ell-1}(x)\bigl(1+g_\ell(x)-\mu_\ell\bigr). \end{align*}\]
Even if both contestants are \(x\), exactly one slot wins, so these events are disjoint. Conditional on the score assignments, separate matches depend on independent initial draws and tie-breaking coins. Their winners are therefore independent draws from \(p_\ell\), which justifies applying the same calculation in the next round.
To sample the final winner, start with \(p_0\), apply this update \(m\) times, and draw once from \(p_m\). Each update costs \(O(|V|)\), for a total of \(O(m|V|)\) instead of an exponential tournament. There is no normalization step: summing the update gives \(1+\mu_\ell-\mu_\ell=1\).
We can now check distortion-freedom algebraically. Conditional on all earlier assignments, \(p_{\ell-1}\) is fixed and the new bits are independent and fair, so
\[\begin{align*} \mathbb E[g_\ell(x)]&=\tfrac12, &\mathbb E[\mu_\ell]&=\sum_y p_{\ell-1}(y)\tfrac12=\tfrac12. \end{align*}\]
Taking expectation over this round’s bits gives
\[\begin{align*} \mathbb E_{g_\ell}[p_\ell(x)\mid g_1,\ldots,g_{\ell-1}] =p_{\ell-1}(x)\bigl(1+\tfrac12-\tfrac12\bigr) =p_{\ell-1}(x). \end{align*}\]
Iterating expectations yields \(\mathbb E[p_m(x)]=p_0(x)\), as promised.
A Likelihood-Ratio Detector
With the winner’s distribution in hand, we can test whether an observed token is more likely under the secret tournament or the original model. For an observed token \(x\), the likelihood ratio is the probability under the tournament divided by the original probability:
\[\begin{align*} \frac{p_m(x)}{p_0(x)} =\prod_{\ell=1}^m\bigl(1+g_\ell(x)-\mu_\ell\bigr). \end{align*}\]
This is defined on tokens with \(p_0(x)>0\). A large ratio means the token is more likely with this particular secret assignment than it would be without watermarking.
For a text \(x_1,\ldots,x_T\), recompute the distributions and scores at each position using the preceding text. Adding a position index \(t\) to these quantities, the log-likelihood ratio becomes
\[\begin{align*} L &=\sum_{t=1}^T\log\frac{p_{m,t}(x_t)}{p_{0,t}(x_t)}\\ &=\sum_{t=1}^T\sum_{\ell=1}^m \log\bigl(1+g_{\ell,t}(x_t)-\mu_{\ell,t}\bigr). \end{align*}\]
Declare a detection when \(L\) exceeds a threshold chosen to control false positives under the unwatermarked model.
Computing this exact likelihood ratio requires access to the model distribution to calculate each \(\mu_{\ell,t}\). Without it, you can still reconstruct the scores using the tokenizer, secret key, and watermark configuration, then:
- Average the scores. Watermarking favors score-one tokens, so look for an average above the unwatermarked baseline of \(1/2\). This requires no trained classifier; you can choose a detection threshold using known unwatermarked examples.
- Use an analytical threshold. If the \(N\) retained scores are independent fair bits under unwatermarked generation, their sum follows \(\operatorname{Binomial}(N,1/2)\). Use its upper tail to decide how many ones would be sufficiently unusual. This calculation requires independence, so repeated contexts cannot simply be counted as fresh evidence.
- Train a Bayesian detector. Learn a small probability model for the reconstructed scores from watermarked and unwatermarked examples. The detector compares score likelihoods and applies Bayes’ rule to estimate the probability of a watermark. Calibrate its detection threshold on held-out unwatermarked examples.
Hashing the Meaning
Reconstructing the secret assignments becomes harder when someone edits the text. If we hash the preceding tokens, changing even one word can change the hash and hence the scores assigned to subsequent tokens. The detector then reconstructs different scores from those used during generation, even when the edit preserves the meaning. This makes token-based hashing brittle to paraphrasing.
In joint work on SimKey, we use the semantic meaning of the preceding text to generate the keys. We embed the context as a vector and apply locality-sensitive hashing, so contexts with similar meanings are more likely to produce the same key even when their wording differs. These keys can drive the same SynthID tournament, making the watermark more robust to paraphrasing.