Watermarking LLM Output

Deutsche Version hier

The EU AI Act requires providers of certain AI systems to mark generated output with a watermark to the extent that this is technically feasible. The technologies behind this are fascinating and differ fundamentally between text and images. An image watermark must be extremely robust against operations such as blurring, noise, and scaling. Text offers far fewer ways to make such automatic alterations, so watermarks can work much more directly with the specific choice and order of words. This naturally raises the question of how much they affect text quality. Although we do not know which technologies LLM providers actually use, it may be surprising that, at least in theory, watermarks can be completely invisible—that is, free of statistical anomalies—in many scenarios.

First, a brief explanation of the basics: an LLM does not itself output individual tokens. Instead, it assigns numbers called logits to every token in its vocabulary, with larger numbers expressing a kind of preference. An algorithm then turns these logits into probabilities, taking additional parameters such as temperature into account. We can therefore treat the LLM together with its sampling algorithm as a generator of probabilities, referred to below as the model or model probability. Suppose the model has already generated The cat is sitting on and, for simplicity, we treat each word as one token. It might assign the a probability of $60\%$ and a a probability of $40\%$ as the next word. If we repeat the same generation many times, we get The cat is sitting on the in six cases and The cat is sitting on a in four. In reality, of course, model probabilities depend on the entire context window, which typically contains far more than this one sentence.

This is exactly where watermarks come in: broadly speaking, whenever probabilities are involved, there is room to embed information invisibly. A typical method computes a secret hash from a fixed number $n$ of preceding tokens. A hash is essentially a deterministic function whose output—a large number or string—is difficult to predict. All kinds of other objects can be derived from it. In the simplest case, every token in the vocabulary is assigned a bit, either 0 or 1. For $n=4$, for example, the last four tokens The cat is sitting might produce an assignment such as { "on": 0, "down": 1, ... }. The watermarking method then tries to favor positively marked tokens while ensuring that, averaged over all possible bit assignments, the original probabilities remain exactly unchanged. In this example, we would observe a bias toward down. After a different prefix, the assignment would also be different and might favor on instead. But if we rolled the hash at random rather than computing it, the resulting distribution would always be exactly the one intended by the model.

At first glance, this may sound as though it should produce a detectable change in the statistical patterns of the text. That is only partly true. Consider a board game played with a magical die whose outcome depends on the current board position. The die follows no visible pattern and, averaged over every possible position, still produces all six faces with equal probability. In a single game, there would be no statistical anomaly unless a position repeated. Someone who knew the die’s rules, however, could inspect the game record and determine with high confidence whether it had been used, even if it was used only during parts of the game.

Similarly, the only way to detect irregularities in a watermarked text without generating it repeatedly is for the same sequence of $n$ tokens to recur. After a fragment such as in other words,, for example, a new clause might begin with the more often than with this because the hash favors the, even though the model itself has no strong preference. But even this is not straightforward: after generating one clause beginning with the, the model could strongly favor beginning the next one with this.

Importantly, the model probabilities are no longer required to verify the watermark, although they would certainly be useful. In naturally generated text, an average of half the tokens should receive a positive mark from the hashing algorithm. Verification simply measures how far the watermark signal deviates from this $50\%$ baseline. Taking the text length into account, we can calculate the probability that an unmarked text would produce an equally strong signal—the same probability that a sequence of fair coin flips would produce a similar result. If this probability is very small, the text was probably generated, at least in part, by an model using the watermark.

The mathematically interesting question is how much signal can be hidden in each token without disturbing the overall probability distribution. The simplest case is a uniform distribution. Suppose the model assigns equal probability to four tokens at some position. We compute their hash markings and, as long as at least one token is marked 1, choose uniformly among the positively marked tokens. Only when all four tokens are marked 0, which happens in one out of 16 cases, do we choose uniformly among all four. In this example, 15 out of 16 generated tokens receive a positive mark.

With an unequal weighting such as $75\%$ to $25\%$, however, the maximum achievable signal is only $75\%$. Weighting therefore matters greatly. Source code, in which syntax predetermines many tokens, may carry a weaker signal than prose, although it still contains sources of entropy such as comments and variable names. If the model is simply asked to output the numbers from one to ten or the alphabet, there is no opportunity to hide a watermark signal in its answer.

The following demo makes the two-token case concrete. The slider changes the model probability assigned to tokens A and B. The four rows represent the four equally likely hash states 00, 01, 10, and 11: the first bit marks A and the second marks B. Each row’s bar shows how often the algorithm selects A or B in that state. Averaged across all four states, the probability set with the slider is always preserved. This is also visible in the combined length of the dark sections across all four bars.

The watermark signal is the proportion of selected tokens that carry a positive mark. The farther the model probability moves away from a uniform distribution, the less freedom the algorithm has and the weaker the signal becomes. Between $25\%$ and $75\%$, the signal reaches its maximum of $75\%$.

Signal strength can be summarized in several ways. As one illustration, the demo uses the expected p-value after ten tokens.¹ This particular statistic is not essential to the main argument: the higher the density of positive markings, the more clearly a marked text can be distinguished from an unmarked one.

It would be even better to extract more than a single bit of information from the hash. With single-bit markings, a token generated without knowledge of the watermark has a $50\%$ chance of receiving a positive mark. Even a perfectly marked individual token therefore provides only a modest statistical signal, because an unmarked token would look equally good in $50\%$ of cases.

This is the approach taken by the authors of Scalable watermarking for identifying large language model outputs. Instead of assigning only one bit to each token, they give every token a marking of $m$ independent bits. A tournament is then held. At the start, $2^m$ tokens are sampled according to the model probabilities and divided into pairs. The two tokens in each pair compete using the first bit of their respective markings. If exactly one has a 1, it wins; otherwise, a fair coin is flipped. Averaged over all hashes, the winning tokens still follow model probabilities.² This leaves $2^{m-1}$ tokens for the next round, which uses the second marking bit.

Changing bits between rounds is necessary. Suppose there are only two candidate tokens with probabilities of $99\%$ and $1\%$. In $25\%$ of possible markings, the second token would be favored. With $m=8$, we begin with $2^8=256$ samples, so there is still a high probability of drawing the second token at least once. If the same bit were used throughout, that rare token would then win every round and reach the top, increasing its overall probability dramatically—from $1\%$ to around $25\%$.

Verification looks slightly different in this system because the hash now produces $m$ bits for every token, but the basic idea is the same. For an unmarked source, the individual bits should look like fair coin flips. For a marked source, positive bits should predominate.

Tournament sampling is an efficient way to use these additional bits during selection. The exact mathematics matters less than the basic insight that a watermarking algorithm works better when it extracts more ranking-relevant information from the hash. A single bit divides the entire vocabulary into only two large groups. If two candidate tokens receive the same bit, choosing between them cannot strengthen the signal: from the watermark’s perspective, they are equivalent at that moment.

Multiple independent bits distinguish tokens much more finely. They do not create a complete ordering, and ties remain possible, but indistinguishable cases occur much less often than when tokens are divided into only two groups. The algorithm therefore gets significantly more opportunities to make a choice that favors the watermark. This makes it possible to strengthen the watermark signal further without changing the original model probabilities on average. In particular, the plateau between $25\%$ and $75\%$ in the interactive example would disappear, and probabilities near $50\%$ could yield an even stronger signal.