Scalable watermarking for identifying large language model outputs

• The original SynthID-Text paper
• Published online: 23 October 2024 in Nature

Disclaimer: These are my personal notes written while preparing a seminar presentation. They exist mainly to help me understand the paper and are not a rigorous paper review. There may be misunderstandings or imprecise statements, and the math derivations are my own re-derived versions. If you spot a mistake, feel free to point it out in the comments. I recommend reading this alongside the original paper.

Introduction

LLMs can already synthesize high-quality text, and sometimes it is hard to tell apart from what humans write. AI slop like this flooding the internet could have a huge impact on the whole information and knowledge ecosystem. It would be great if we could trace where text came from (Provenance), which is why watermarking matters. We want to know what the source of a piece of text actually is, and watermarking is a handy tool for that, for both text and images.

The reason I looked at SynthID Image and SynthID Text is that both are Google papers, and rather than papers they feel more like products backed by academic theory. Anthropic has also announced that text generated by their models now carries a watermark (official announcement). Maybe I can find some ideas here for my master’s thesis, using watermarking as a tool.

What makes SynthID nice is that it does not change the LLM training pipeline at all; it only modifies the sampling step of the LLM. The idea should be similar to KGW’s red/green tokens, but it seems to add some enhancements. To make watermarking deployable at scale, SynthID-Text adopts a strategy compatible with speculative sampling, which is an LLM inference acceleration technique (the idea of predicting the tokens that are about to come out).

The authors found experimentally that SynthID does not even degrade the original LLM’s capabilities. They ran a live experiment analyzing user feedback on nearly 20 million Gemini responses to see whether the watermark preserves text quality (though Gemini’s reputation has not been great lately, so I guess they are running experiments again, haha).

The wording in the introduction here is “identification and attribution of LLM text is critical to ensure safe and responsible use of the technology”, rather than Provenance.

There are currently a few ways to achieve this:

• retrieval-based approach: keep a record of all generated text and compare the text under inspection against it. But there are privacy concerns, because every interaction with the LLM has to be stored.
• post hoc detection: use the statistical features of the text itself, or train an additional classifier. The advantage is that no generation records need to be kept; the downside is potentially high computational cost and unstable performance, with poor results on out-of-domain data (data outside the training distribution) and high false positives.
• text watermarking: insert marks into the generated text that are invisible to the naked eye, which can be further divided into three approaches
  • generative watermarking: add the watermark during generation
  • edit-based watermarking: add the watermark to text after it has been generated
  • data-driven watermarking: modify the LLM’s training data

Edit-based watermarking relies on rule-based text transformations such as synonym substitution or inserting invisible Unicode characters (probably something like ASCII smuggling).

Data-driven watermarking uses a trigger phrase during training; the LLM only outputs watermarked content when it sees this trigger, which feels like planting a watermark backdoor.

So SynthID uses generative watermarking, because one of the requirements is that Google wants fine-grained control over the effect on text even at large scale while keeping computational cost low. The authors also say that no perfectly reliable text detection method exists.

SynthID-Text is actually built on existing watermarking components, but it adopts a new sampling method called Tournament Sampling. SynthID-Text can be configured in two modes:

• non-distortionary: aims to preserve text quality
• distortionary: degrades text quality but makes the watermark easier to detect

Watermarking with SynthID-Text

Here x is an input text sequence containing $t - 1$ tokens from vocabulary $V$

The LLM computes the probability distribution of the next token based on $x_{<t}$

This process is shown in the top half of figure 1.

Such a generative watermark can be broken into three components:

• random seed generator
• sampling algorithm
• scoring function

As shown in the bottom half of figure 1, at each step $t$ the random seed generator produces a random seed $r_t$, which may be derived from the preceding text plus a key. The sampling algorithm then samples the next token based on $r_t$ and $P_{LM}(\cdot | x_{<t})$. The key point is that this sampling algorithm creates correlations between $r_t$ and $x_t$, so the output text carries a statistical signal and becomes watermarked text.

A sliding window is used to take the most recent $H$ tokens and hash them together with the key to get $r_t$. This is shown in the top half of figure 2, and the formula below uses $H=4$. That said, a sliding window is not strictly required. Everything up to this point is the same as KGW; the only difference is the tournament sampling method mentioned earlier, which we will get to shortly.

SynthID-Text’s Tournament sampling approach

A Tournament means letting candidate tokens compete against each other. First we define the number $m$ of watermark functions g to be used. On the right side of the top half of figure 2 there are $m=3$ functions $g_1$ $g_2$ $g_3$, which are independent pseudorandom number functions.

Each function g gives a score, written as $g_{l}(x_t, r_t)$; in the figure 2 example the output is only 0 or 1. In other words, the same token may get different outputs under different watermark functions. From here on I will refer to the score produced by function g as the g-score.

The bottom half of figure 2 shows the tournament process. We first define the number of candidates to sample, $m$, and sample $M=2^m$ tokens from the LLM’s output distribution; the same token may be picked multiple times. In the figure below $m$ is 3, so there are eight candidates, four of which are duplicates. $m=3$ means there will be 3 rounds of competition. In each round the higher score wins, ties are broken randomly, and the final winner becomes $x_t$.

The authors mentioned earlier that this method can be used when you do not have access to the LLM weights. At first I thought, doesn’t this still require access to the probability distribution? Then I remembered that the openai-python package has a parameter n that generates multiple independent completions, but that is not per-token, so… I am not sure how this would work in a fully black-box setting. Wait, I wonder whether this is something I could try, but it would be similar to what A Watermark for Black-Box Language Models describes, with a very large inference cost.

By now it is easy to see that the biggest difference between SynthID-Text and KGW is that SynthID-Text does not need to modify the logits (see the figure below, which I captured from step 4 of algorithm 2 in the original KGW paper). KGW directly treats the LLM output after modifying the logits as the watermarked text; SynthID instead samples more candidates and lets the one with the higher g function value win (and it has to win every round). Modifying logits the way KGW does can easily affect output quality, whereas SynthID is less likely to, which will be covered in a later section.

Watermark detection

Detection is very simple: just compute the g-score of the suspicious text, because the sampling favors tokens with high g-score. The formula is:

Here m is the number of g functions and T is the number of tokens; it is simply the average of the scores of every token in every round. If the Score is abnormally high, the text is very likely SynthID-Text output.

Two factors affect watermark detection performance. One is text length: the longer the text, the more accurate the detection. The other is entropy, meaning how certain the model is about the next token. If the LLM distribution has very low entropy, the model gets almost the same response every time it samples. An intuitive example: if I tell ChatGPT to generate 100 a’s, how could it possibly produce a b? How do you watermark those 100 a’s? Conversely, if you ask it to write a novel, the possibilities are extremely diverse and the text is long. This is exactly the same problem other watermarking methods face.

The authors mention that many factors affect the entropy of the LLM distribution. Larger models are more confident about their outputs, so entropy is lower. RLHF may also reduce entropy, a phenomenon also known as mode collapse (a term often used with GAN models). The prompt, as in my earlier example, matters too, as does temperature, and many other things.

Increasing the number of Tournament layers m lets each token provide more watermark evidence while reducing the variance of the Score formula. But detection ability does not grow indefinitely with more layers (intuitively, later layers have little diversity left to choose from, since earlier layers have already made many selections).

Unless otherwise stated, $m$ is set to $30$ in this paper’s experiments.

Preserving the quality of generative text

A term worth mentioning here is “non-distortionary”. This term has been somewhat confusing in past literature, so the authors define text distortion in several levels from weakest to strongest. The weakest is single-token non-distortionary: when we average over the random seed $r_t$, the distribution sampled by the watermark sampling algorithm must equal the distribution sampled from $P_{LM}(\cdot|x_{<t})$.

I did not quite get it at first, but once I thought carefully about how one would verify this it clicked: you just generate many different $r_t$, run the sampling algorithm with each of these $r_t$, and average the resulting text.

Stronger non-distortionary definitions extend to longer spans of tokens rather than a single token, possibly the whole sequence. That is, going from $P(x_t)$ to requiring that $P(x_1, x_2, ..., x_t)$ all match the LLM’s distribution. (This is actually the distortion-free concept mentioned in A Watermark for Black-Box Language Models.)

As for why SynthID-Text can achieve single-token non-distortion, Supplementary Information Section G.1 proves that when each match in the tournament has exactly two competitors, it has the single-token non-distortionary property. With more than two, it cannot be non-distortionary.

Proof that more than 2 competitors cannot be non-distortionary:

Suppose the LLM samples $N$ times from a vocabulary with only two tokens, $V=\{a,b\}$, where $a$ has probability $p$ and $b$ has probability $1-p$. Among the $N$ samples, the number of times $a$ appears, $i$, follows a binomial distribution $Binomial(N,p)$. What we want to compute is the probability $p_{wm}(a)$ that $a$ is ultimately selected as $x_t$, and after taking the expectation over $r$ we hope it equals $p$.

Consider three cases

• a is picked 0 times, i.e. $(1-p)^N \times 0=0$.
• a is picked N times, i.e. $p^N\times 1=p^N$.
• both a and b are picked, which is the binomial expression that follows; the part after it is the g function value, and in case of a tie it is simply $\frac{i}{N}$ because the winner is picked at random.

Take the expectation over r. Since $p^N$ and the binomial part have nothing to do with r, they can be pulled out, so we are effectively taking the expectation of the last term. Here $C_{f_g}$ is the Collision probability (the probability of a tie). Using indicator functions, the expectation of an indicator function is exactly the probability of that event, which is where $\frac{1-C_{f_g}}{2}$ comes from: subtracting $C_{f_g}$ from 1 leaves the probability $P(g_1(a) > g_1(b))+P(g_1(a) < g_1(b))$, and the hash function is designed to be fair, so we can divide by two directly.

When expanded, this expectation looks like $c_0\cdot p^0 + c_1\cdot p^1 + ...c_N \cdot p^N$, and this thing must be identically equal (Identically Equal, holding for all possible values of the variable) to $p$ (that is, $1\cdot p^1$) to satisfy the non-distortionary requirement. In other words, for this to hold, by the Polynomial Identity Theorem, $c_1$ must be 1 and all other coefficients must be 0. If we can find any other coefficient that is non-zero, we have a contradiction.

Expanding and computing the $p^2$ coefficient: here $N>2$ and $C_{f_g} \neq 1$, so it is non-zero, which is a contradiction.

Proof that a layer with two competing samples is always non-distortionary:

This is the definition of $p_{wm}$ for a single layer ($m=1$). The numerator is “the probability that, among $N$ samples, every sample’s score is less than or equal to that of $x_t$” minus “the probability that, among $N$ samples, every sample’s score is strictly less than that of $x_t$ (meaning the maximum score is lower than $x_t$’s)”. Their difference is the probability that the maximum score is exactly $g_1(x_t, r)$. The denominator is the total probability of all tokens with the same g-value as $x_t$ (including $x_t$ itself).

It can also be thought of as:

Substituting $N=2$, it can be written as follows: the original LLM probability multiplied by “the probability of tokens in the Vocabulary whose score equals that of $x_t$” + “the probability of tokens whose score is greater or smaller”. The reason we can directly write $2p(V^{g_1(x_t,r)})$ is that this factor of 2 comes purely from algebra: $\le$ can be split into $<$ and $=$, so $A+B = (B + p(V^{=})) + B$ yields an extra copy of $p(V^{<g_1(x_t,r)})$. This step has not yet used any property of the hash function. Probabilities can be rewritten as sums of indicator functions, which gives the final expression.

Difference of squares:

Then “$\le$” can be split into “$<$” and “$=$”, $A = B + p\left(V^{= g_1(x_t, r)}\right)$:

Substitute back and cancel:

The probability can then be written as follows, restoring it to a sum of indicator functions:

Then we take the expectation over r, $\mathbb{E}_r[p_{wm}]$, which only requires computing the following. Notice that this is where the hash function property is used, namely splitting $2\mathbb{E}[\mathbb{1}_<]$ into $\mathbb{E}[\mathbb{1}_<] + \mathbb{E}[\mathbb{1}_>]$:

Substitute back, and there it is. (The multi-layer case is proven to give the same result.)

Section G.2 then describes in detail the proof that repeated context masking achieves non-distortion for one or more sequences. The idea is to avoid applying the same watermark bias again when the same context reappears. I will leave that for you to read yourselves; anyway, I believe them, and it is definitely not that I was too lazy to read it.

The Supplementary Information of this paper is basically a textbook, starting from the basics. Well worth a read, but I am a bit tired.

Ensuring computational scalability

Because only the sampling layer is modified, the LLM itself is not re-run, so the added computational cost is negligible. The g-values of the candidate tokens can also be computed in parallel, which is well suited to vectorization.

One thing to note is that production systems are usually not a plain autoregressive loop. For example, production may use speculative sampling, a method that uses a smaller, faster model to predict tokens so the LLM can run faster. The target LLM then verifies these predicted tokens, so it does not have to waste time on a forward pass every single step, and the extra predicted tokens can be processed in parallel.

Below is the speculative sampling algorithm, where q is the target LLM and p is the small model

1. Lines 4 to 6: let the small model draft K candidate tokens
2. Line 7: the large model takes these K tokens as input together, so the logits can be computed in parallel
3. Lines 8 to 15: the verification step. For each drafted token $\tilde{x_t}$, draw a uniform random number $r \sim U[0,1]$. If $r < min(1, \frac{q(\tilde{x_t})}{p(\tilde{x_t})})$, accept the small model q’s token into the final result. Otherwise, immediately stop this round of verification and resample the correct token from the residual distribution as a replacement

The reject case is worth noting: the point is to avoid inflating the probability of the rejected token, which is why this formula subtracts the two probability distributions. As for how they compare, they divide the target model’s probability by the small LLM’s probability; the closer to 1 or even > 1, the more likely it is accepted, so it is essentially comparing how much the large and small models agree on this token. A Uniform distribution is used here because the small model’s probability multiplied by this accept rate is exactly the target LLM’s probability. This way the sampling distribution does not deviate from the target LLM, generation quality is not affected, and it is fair.

The + symbol in the bottom right denotes the “Positive Part Operator / Rectified Unit”, which has the same effect as ReLU + L1 normalization

Nobody had previously discussed how to combine generative watermarking with speculative sampling, which is one of their contributions. The authors propose two generative watermarking schemes with speculative sampling, in Supplementary Information Section I.4:

high-detectability watermarked speculative sampling

The goal is to preserve watermark detectability. It may reduce the efficiency of speculative sampling but does not sacrifice the watermark signal. I will not go into the algorithm (algorithm 5) in detail; it is the same as speculative sampling, except the target LLM’s probability distribution is replaced by the watermark sampling function’s distribution. It does increase cost, though, because the algorithm requires directly computing the $p_{wm}$ and $q_{wm}$ distributions. The main slowdown is the high rejection probability, and after a rejection the watermark distribution over the whole Vocabulary has to be computed.

fast watermarked speculative sampling

This preserves the efficiency of speculative sampling, but detectability may drop. For this approach the authors propose a learned Bayesian scoring function to make the detector more effective.

In the algorithm below, it does not need to compute probabilities like $p_{wm}$ or $q_{wm}$; it only needs to be able to sample. There is also a two-key mechanism: the Draft key $k^D$ is used by the small model, and the Target Key $k^T$ is used by the large model.

1. Lines 4 to 6: again let the small model produce K draft tokens, using $k^D$ while generating them.
2. Then the large model runs in parallel and computes the unwatermarked distributions at these K positions
3. Then verify the draft tokens the same way as before
   1. If it passes, it is accepted, but note that this token keeps the watermark from the small model’s key
   2. If it fails, the large model draws a token from the distribution using $k^T$ to fill in, then ends this round

The reason it can be called fast is that the ratio on line 10 of algorithm 5 is $\frac{q_{wm}(\tilde{x_t})}{p_{wm}(\tilde{x_t})}$, meaning the system has to push tens of thousands of tokens back through the watermark sampling function, whereas line 10 of algorithm 6 only needs $\frac{q(\tilde{x_t})}{p(\tilde{x_t})}$. It is as fast as the original speculative sampling with no watermark at all. The two keys are used for probabilistic independence ($k^D$ and $k^T$ are sampled independently), which raises the probability that the target model accepts the draft model’s tokens, because in theory p and q are very similar, and the two keys effectively remove the interference from the watermark.

Evaluation

The authors ran many experiments; I will only pick the interesting ones.

The baselines fall into two categories, non-distortionary and distortionary. For the former they chose the best method at the time, Gumbel sampling, and for the latter Soft Red List. For a fair (like-for-like) comparison, the authors focus on the sampling algorithm and keep everything else the same (random seed generator, scoring, and so on). For all baselines they use the same sliding window random seed generator and the same repeated context masking.

They want to verify quality (text quality must not be affected) and scalability (cost must not be too high).

SynthID-Text preserves quality including in a large-scale- production system

Back when Gemini was still called Bard, they ran an online test, routing half of user queries to watermarked sampling and half to unwatermarked, and let users rate responses via the 👍 and 👎 in the UI. The result was a thumbs-up rate difference of 0.01 (and a thumbs-down difference of 0.02), over 20 million samples, which means basically no difference, at least none that humans can perceive.

To provide an experiment others can reproduce, the authors used Gemma 7B-IT (IT -> instruction-tuned) to answer 300 ELI5 questions (explain like I’m five, named after the well-known Reddit forum, full of complex, open-ended big questions), then had humans rate them in a side-by-side comparison (probably like LM-SYS) on the following aspects

• grammaticality / coherence
• relevance
• correctness
• helpfulness
• overall quality

The result was no statistically significant difference, see Extended Data Table 1

They also measured perplexity and automated benchmark performance, and the conclusion is that non-distortionary SynthID-Text shows no significant difference from the unwatermarked model.

SynthID-Text provides better detectability than existing watermarks

model:

• Gemma 2B-IT
• Gemma 7B-IT
• Mistral 7B-IT The experiments use the ELI5 dataset, which consists of explanatory multi-sentence answers. I think the purpose is that such prompts make the output entropy high. Figure 3a is the non-distortionary category, where SynthID-Text indeed performs better than Gumbel sampling, and TPR clearly increases with more tokens. Note that the vertical axis is $TPR\ @\ FPR = 1\%$, meaning the model’s TPR under the condition that FPR is at most 1% (think of it as the score threshold).

In scenarios that require a very low FPR, a selective prediction mechanism can be used, which simply refrains from judging samples the scoring function is not confident about (abstention). The system sets two score thresholds

• High threshold $\tau_{positive}$: computed from unwatermarked text; only above this threshold do we dare to declare a watermark present (controls FPR)
• Low threshold $\tau_{negative}$: computed from watermarked text; only below this threshold do we dare to declare no watermark (controls FNR) If $\tau_{positive} < \tau_{negative}$, detection at the current length is very good and the requirement can be met without abstaining at all.

Figure 3b describes the case with the selective prediction mechanism; the vertical axis is the abstention rate, and the more tokens there are, the less the detector abstains.

Figure 3c: the combination of low perplexity and high TPR is in the top left, and the closer to the top left the better. Compared with the Soft Red List method, SynthID-Text has lower perplexity, meaning less sentence quality is sacrificed.

Extended data fig 4 uses a metric called Self-BLUE to measure text diversity; lower values mean higher diversity. SynthID-Text also has higher diversity than Gumbel sampling.

SynthID-Text has minimal computational impact

The authors point out that Tournament sampling may indeed take longer than Gumbel and Soft Red List sampling, but these times are still far smaller than the LLM’s own inference time, so the impact on the overall system is comparatively small.

In one experiment, with Gemma 7B-IT on 4 v5e TPUs, the original generation speed was 15.527 ms / token; with 30-layer tournament sampling it became 15.615 ms / token, a latency increase of only 0.57%. For comparison, Gumbel adds 0.26% latency and Soft Red List adds 0.28%. Basically no difference at all.

Discussion

Contribution

Here are the contributions as I summarized them

• We have introduced SynthID-Text, a method for watermarking LLM text.
• SynthID-Text uses certain elements introduced in previous work, but differs in the use of the sampling algorithm, Tournament sampling, which we find provides superior detectability compared with existing methods. It adopts some elements from prior research but adds a novel sampling method, tournament sampling, whose detectability beats existing methods.
• SynthID-Text comes with rigorous and customizable non-distortion properties that can be configured to guarantee text quality preservation. SynthID-Text has customizable non-distortionary properties (two aspects: one is how many competitors each tournament match has, where exactly two gives single-token non-distortion; the other is the K value of repeated context masking), ensuring text quality is preserved.
• We have also proposed an algorithm to combine generative watermarking with speculative sampling. They propose an algorithm combining generative watermarking with speculative sampling.

Limitations

The advantage of this kind of generative watermark is high cross-language stability, and it beats post hoc detectors (because it does not suffer from unseen data). The more notable limitations:

• It requires the service provider’s cooperation; without it, a post hoc detector may be needed for verification. In other words, SynthID-Text is not a silver bullet.
• Open-source models are usually deployed in a decentralized way, and the official party cannot force everyone to run inference with the watermarking mechanism
• The watermark can still be stolen (stealing: inferring the watermark rules by observing large amounts of watermarked output), spoofed, or scrubbed
• Paraphrasing attacks (LLM paraphrasing): using another LLM to rewrite watermarked text can easily remove the watermark signal.

Oh, I thought of one more. For LLM application developers like us, we do not actually have access to the sampling internals, or rather we cannot manipulate the sampling process as finely as SynthID-Text does. So watermarking for black-box APIs is also a problem worth tackling.

Conclusion

This paper provides evidence that SynthID-Text is viable in the real world. To their knowledge, it is the first generative text watermark deployed at scale. (Though probably only Google can pull this off at this level XD)