LLM Watermarking: Green-Red List Algorithms

As text generated by Large Language Models becomes indistinguishable from human writing, identifying AI-generated content is critical for preventing academic dishonesty, copyright disputes, and web syndication spam.

LLM Watermarking is a technique that embeds a hidden signature directly into the generated text during token selection. Unlike post-hoc classifiers, watermarking is built into the decoding step. By dynamically splitting the vocabulary into green and red lists based on hash keys, the algorithm biases the model’s output towards green-list tokens, allowing detectors to verify the text mathematically without requiring access to the model weights.

How LLM Watermarking Works (Kirchenbauer et al.)

The core watermarking method operates during the model’s next-token selection step.

Prior Token (x_{t-1}) ---> Hash Function ---> Green/Red Split (Vocab)
                                                     |
Logits (from LLM) ------------------------> Modify Logits (Add bias δ to Green List)
                                                     |
                                            Softmax & Sample

1. The Seed Hash

Before predicting token $x_t$, the system computes a hash value based on the immediately preceding token $x_{t-1}$ (or a window of size $N$):

$$h = \text{Hash}(x_{t-1})$$

2. Vocabulary Partitioning (Green and Red Lists)

The hash value is used to seed a random number generator that splits the vocabulary $V$ into two groups:

• Green List ($G$): Tokens that are encouraged (typically comprising a fraction $\gamma \approx 0.5$ of the vocabulary).
• Red List ($R$): Tokens that are discouraged.

3. Logits Modification

The raw logits $l_t \in \mathbb{R}^{|V|}$ output by the model are modified by adding a bias parameter $\delta > 0$ to the logits of the green-list tokens:

$$\tilde{l}{t, i} = \begin{cases} l{t, i} + \delta & \text{if } i \in G \ l_{t, i} & \text{if } i \in R \end{cases}$$

4. Sampling

The modified logits are passed through a softmax function, and the next token is sampled normally. Because of the bias $\delta$, the model selects green-list tokens significantly more often than would occur in unwatermarked text.

Detecting the Watermark: The Z-Test

To determine whether a text of length $T$ was generated by the watermarked LLM, we check if the proportion of green-list tokens is statistically anomalous.

For an unwatermarked text, the number of green-list tokens $s$ follows a binomial distribution with probability $\gamma$. The expected value and variance are:

$$\mu_0 = \gamma T, \quad \sigma^2_0 = \gamma(1 - \gamma)T$$

We compute the $z$-score of the text:

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

If the $z$-score exceeds a significance threshold (e.g., $z \ge 3.0$), we reject the null hypothesis and classify the text as AI-generated with high statistical confidence.

The Engineering Trade-offs

• Text Quality: Adding too large a bias $\delta$ restricts the model’s choices, which can lead to repetitive phrasing or grammatical errors. A typical value is $\delta \in [1.0, 2.0]$.
• Robustness: Watermarks are highly robust to minor edits, insertion of synonyms, or punctuation changes. However, they can be degraded by translation or major sentence restructuring.
• Zero-Bit Verification: The verifier only needs the hash function and the vocabulary seed keys to detect the watermark—it does not need to run the full LLM.

Python Concept: Watermarked Token Selection

Below is a Python demonstration of how to apply a green-list bias during token selection.

import numpy as np

def sample_with_watermark(logits, previous_token_id, vocab_size, gamma=0.5, delta=1.5):
    """
    Applies the Green-Red list watermark to logits during decoding.
    """
    # 1. Compute hash seed using previous token
    # Using a simple pseudo-random generator seeded with previous token ID
    rng = np.random.default_rng(seed=int(previous_token_id))
    
    # 2. Randomly partition vocabulary
    # Shuffling vocabulary index array
    indices = np.arange(vocab_size)
    rng.shuffle(indices)
    
    # Slice first portion as Green List
    green_size = int(vocab_size * gamma)
    green_list = set(indices[:green_size])
    
    # 3. Apply bias delta to Green List
    modified_logits = np.copy(logits)
    for idx in range(vocab_size):
        if idx in green_list:
            modified_logits[idx] += delta
            
    # 4. Softmax and Sample
    exp_logits = np.exp(modified_logits - np.max(modified_logits))
    probs = exp_logits / np.sum(exp_logits)
    
    next_token = np.random.choice(vocab_size, p=probs)
    return next_token, green_list