Watermarking › Watermarking Schemes

The field has converged on two main families of watermarking schemes: token-level schemes that operate on the sampling distribution at each decoding step, and distortion-free schemes that modify how sampling randomness is used without changing the marginal output distribution. Token-level schemes have dominated research because they offer strong statistical guarantees and integrate cleanly into the decoding pipeline. Both families share the requirement that the watermark key must be kept private for the scheme to remain secure.

Before diving into the mechanics, it helps to think about what a watermarking scheme must accomplish simultaneously:

• Detectability: The signal must be strong enough that a detector can reliably confirm its presence in a reasonable amount of text.
• Imperceptibility: The text must still read like natural language. A watermark that causes the model to produce awkward or ungrammatical sentences would be both obvious and counterproductive.
• Security: An attacker who does not know the key should not be able to remove the watermark without degrading text quality significantly, nor should they be able to forge a watermark to falsely attribute text.

These three requirements exist in tension, and much of the research in this area examines the tradeoffs between them.

The key insight in token-level watermarking is that language model decoding involves choosing tokens from a probability distribution at each step. If you can systematically bias those choices, even slightly, you introduce a pattern that accumulates over many tokens and becomes statistically detectable.

The most influential scheme was introduced by Kirchenbauer et al. (2023), often called the KGW watermark. It works by partitioning the vocabulary into two sets at each token position: a "green" set and a "red" set. The partition depends on the previous token, using a hash function keyed to a secret key. During generation, the logits for green-list tokens are increased by a fixed additive amount $\delta$, making the model more likely to select them. Tokens from the red list are not penalized but compete against boosted green tokens.

To understand why this works, consider what happens to the softmax distribution when you add $\delta$ to a subset of logits. If token $i$ has logit $l_i$, then adding $\delta$ to green tokens changes the selection probability. For green token $g$ versus red token $r$:

$$\frac{P(\text{green token } g)}{P(\text{red token } r)} = \frac{e^{l_g + \delta}}{e^{l_r}} = e^{l_g - l_r + \delta}$$

Even when the red token has a higher base logit ($l_r > l_g$), if $\delta$ is large enough, the green token wins. This is the boost mechanism: you are not forcing specific tokens but tilting the odds.

More precisely, before sampling token $t$, the scheme:

1. Hashes the previous token $t-1$ (or a window of previous tokens) together with the secret key to obtain a pseudo-random partition
2. Marks a fraction $\gamma$ of the vocabulary as green
3. Adds $\delta$ to the logit of every green-list token
4. Samples normally from the modified distribution

The detection procedure counts how many green tokens appear in the candidate text, computes a z-score under the null hypothesis that the text was generated without watermarking, and rejects the null if the score exceeds a threshold.

The partition changes at every step because it depends on the current context. This means you cannot predict future green lists from past ones without the key, which prevents attackers from simply avoiding green tokens. If you change token $t-1$ to avoid a red-token situation at position $t$, you simultaneously change the partition at position $t+1$. The dependency chain makes targeted removal difficult.

The statistical heart of the KGW scheme is a hypothesis test. Let $T$ be the number of tokens in the candidate text, and let $|s|_G$ denote the count of green tokens, where "green" is determined by the same hash function and key used during generation.

Under the null hypothesis $H_0$ (text was not watermarked), each token is independently green with probability $\gamma$. Why? Because without the logit boost, the token choice is determined solely by the model's learned distribution, which has no reason to match any particular hash-derived split. The expected number of green tokens is $\gamma T$, and by the central limit theorem, the count is approximately normally distributed with mean $\gamma T$ and variance $T \cdot \gamma(1 - \gamma)$.

The z-score is computed as:

$$z = \frac{|s|_G - \gamma T}{\sqrt{T \cdot \gamma(1 - \gamma)}}$$

where:

• $|s|_G$: the number of tokens in the text that fall in the green list under the key-derived partition
• $T$: total number of tokens in the text
• $\gamma$: the fraction of the vocabulary assigned to the green list (typically 0.5)
• $T \cdot \gamma(1 - \gamma)$: the variance of a binomial distribution with $T$ trials and success probability $\gamma$

This is a standard z-test for a proportion. The numerator measures how far the observed green count is from what you would expect by chance. The denominator normalizes by the standard deviation, putting the statistic on a scale where values above roughly 2 are unlikely under the null.

If the text was watermarked, green tokens appear at a rate higher than $\gamma$ because their logits were boosted by $\delta$ during generation. A large positive $z$ score indicates the presence of the watermark. The detector rejects $H_0$ and concludes the text is watermarked when $z$ exceeds a threshold $z_\alpha$, where $\alpha$ is the desired false positive rate.

For a one-sided test at significance level $\alpha = 0.01$, the threshold is $z_\alpha \approx 2.33$. For $\alpha = 0.001$, the threshold rises to $z_\alpha \approx 3.09$. These correspond to the upper tail of the standard normal distribution: a z-score of 2.33 means the observed green count is in the top 1% of what you would expect from unwatermarked text.

The intuition for why the signal accumulates is essentially the same as why large samples give more precise estimates. Each token is a single Bernoulli trial: was it green? With only 20 tokens, random fluctuations dominate. With 200 tokens, the law of large numbers ensures that the observed green rate converges to its true mean, and the true mean under the watermarked distribution is higher than $\gamma$ by an amount that depends on $\delta$.

The KGW scheme has two variants that differ in how they handle high-entropy versus low-entropy positions.

Hard watermarking strictly forbids red tokens by setting their logits to $-\infty$. This maximizes detection power because every generated token is guaranteed to be green. The z-score grows at the maximum rate, and detection is reliable even with fewer tokens. The problem is quality degradation. When the model would naturally continue with a word like "not" or "however" but these happen to be on the red list for the current context, the model is forced to produce something awkward. At low-entropy positions, where one or two tokens strongly dominate the distribution, the forced exclusion of red tokens can produce grammatically incorrect or semantically inconsistent text.

Soft watermarking adds $\delta$ to green-list logits without zeroing out red tokens. Quality loss is much smaller because the model can still choose red tokens if they dominate the distribution strongly enough. Consider a position where the model assigns logit 8.0 to "not" (a red token) and logit 4.0 to its best green alternative. With $\delta = 2.0$, the best green token now has logit 6.0, but "not" still wins at 8.0. The sentence continues naturally. Detection power is lower than hard watermarking because not every generated token is green, but it degrades gracefully and remains reliable at moderate text lengths.

The tradeoff between quality and detection power is fundamental and cannot be fully eliminated. Higher $\delta$ makes the watermark easier to detect but also more perceptible as unnatural text because the model is more strongly biased away from its most natural continuations. Kirchenbauer et al. showed that soft watermarking with $\delta \approx 2.0$ and $\gamma = 0.5$ achieves a useful balance: text quality remains close to the unwatermarked baseline as measured by perplexity and human evaluation, while detection succeeds reliably with $T \geq 200$ tokens at meaningful significance levels.

The choice between hard and soft watermarking is not merely technical. Hard watermarking might be appropriate for internal auditing where text quality is not consumer-facing. Soft watermarking is necessary for any deployment where the watermarked model interacts directly with users who would notice quality degradation.

The context-dependent partitioning of the KGW scheme has both strengths and weaknesses. The strength is that the partition is unpredictable without the key. An attacker observing the generated text cannot infer which tokens are green for future positions because the partition changes with each new token. The weakness is that the hash of consecutive tokens creates correlations between adjacent decisions, complicating the statistical analysis and making it harder to reason about detection power theoretically.

A simpler alternative is the unigram watermark, which uses a single fixed partition of the vocabulary that does not change across positions. The same green list applies at every token position throughout a document. Detection is still a z-test on the green token count, but the partition is fixed rather than context-dependent. This simplification has two consequences: the statistical analysis is cleaner because token choices are more nearly independent, and the scheme is more vulnerable to attack because an attacker who discovers which words are on the green list can avoid them entirely. Since the partition does not change, discovering even part of the green list gives the attacker useful information for targeted removal.

A more sophisticated approach, proposed by Christ et al. (2023), generates a pseudo-random binary signal $r_t \in \{0, 1\}$ for each position $t$ using a pseudo-random function keyed to the secret key and the current position index. The bits determine which tokens to prefer without partitioning the full vocabulary. This scheme offers provably optimal detection under certain assumptions because it achieves the maximum possible information content per token while remaining undetectable to a party without the key. The theoretical guarantees come at the cost of more complex detection algorithms, but the framework has influenced subsequent work.

A significant limitation of logit-bias schemes is that they always distort the output distribution. The generated text is not drawn from the true model distribution. This matters for several reasons. First, calibration: watermarked models are slightly less faithful to the input prompt because they systematically prefer certain tokens even when those tokens are not the most natural continuation. Second, detectability: the distortion is in principle measurable by anyone who knows enough about the model's natural distribution, even without knowing the watermark key. Third, downstream use: if a watermarked model's outputs are used as training data for another model, the biased distribution introduces systematic errors.

Kuditipudi et al. (2023) introduced a family of distortion-free watermarks that preserve the original sampling distribution in expectation. The key idea is to use a pseudo-random coupling between the model's probability distribution and a secret signal, rather than modifying the logits. Because the signal is embedded through the randomness of the sampling process rather than through biased logits, the marginal distribution over outputs is unchanged.

To understand the mechanism, recall how token sampling normally works. The model produces a probability distribution $P$ over the vocabulary. You sample a token by drawing a uniform random variable $u \sim \text{Uniform}(0, 1)$ and applying the inverse CDF of $P$: you find the token $t$ such that $\sum_{t' < t} P(t') \leq u < \sum_{t' \leq t} P(t')$. Different values of $u$ produce different tokens according to their probabilities.

The distortion-free watermark replaces the uniformly random $u$ with a value derived from the secret key: $u_t = F(k, t)$ where $F$ is a pseudo-random function. The output distribution is still $P$ because a pseudo-random $u_t$ is statistically indistinguishable from a truly uniform one if $F$ is a good pseudo-random function. But now the specific token chosen at each position is determined by the key in a way that a detector can verify.

Detection works by testing whether the observed tokens are consistent with having been chosen using the key-derived randomness. Concretely, for each token $t$ in the candidate text, the detector computes the rank of $t$ under the probability distribution $P$ given the preceding context. Under the watermark, each token should have a specific expected rank determined by $u_t$. Under the null hypothesis, ranks are uniformly distributed. A rank-based test statistic exploits this asymmetry to identify watermarked text.

The tradeoff is detection efficiency. Because distortion-free schemes do not boost any signals above the natural distribution, each token provides less evidence about the watermark's presence than it would under a logit-bias scheme. Empirically, distortion-free schemes typically require more tokens to achieve the same detection confidence. The theoretical guarantee of zero distribution shift is useful, but practical performance at short text lengths is lower than logit-bias approaches. For long documents, the difference diminishes.