Watermark Forensics for Generative Models: An Information-Theoretic Perspective

Image generated by AI

TLDR

• What: An information-theoretic framework showing that all generative model watermarking tasks (detection, attribution, extraction, and localization) are governed by a single mathematical object—the information profile—revealing fundamental limits on user attribution and crop-robust localization.
• Who's at risk: Providers deploying watermarking systems for model provenance, copyright enforcement, or user-tracking (e.g., SynthID-Text, green-list variants, and sequential generation pipelines) who assume watermarks can easily scale to millions of users or pin down edited segments.
• Key number: Naive collision-counting decoders overcharge sample complexity by a factor of up to $1.61\times$on natural language (GPT-2); using a *surprisal-threshold decoder* recovers the optimal$\Theta(\log N / h)$ token cost.

As regulatory pressures mount—such as the EU AI Act (Art. 50) and California's SB 942—the AI industry is looking to implement watermarking systems. Many of these statutes presume that a watermark is a physical, extractable "object" embedded in a text or image. They mandate capabilities like attribution (identifying which specific user generated a piece of text) and localization (identifying exactly which parts of a document have been modified).

However, this paper demonstrates that a fundamental information-theoretic barrier exists between detecting a watermark and attributing it to a user. While detecting whether a text was generated by a model like GPT-2 or Qwen-2.5 requires very few tokens, uniquely identifying one of $N$ users who generated it is dramatically more expensive. This research introduces "The Forensic Ladder" to prove exactly what each forensic query costs in sample length.

Threat Model

Background & Problem Setup

The generative model watermarking literature has been fragmented, treating detection, payload extraction, and localization as distinct engineering problems. Existing techniques generally fall into two incomparable "quality models" or paradigms:

1. Biasing / Distributional Marks ($B(\Delta)$): These schemes (e.g., the green-list approach by Kirchenbauer et al., 2023) subtly alter the probability of every generated token. The watermark is "delocalized" and exists only in the statistical aggregate.
2. Embedding / Footprint Marks ($\mathcal{E}(m)$): These schemes (e.g., Tree-Ring by Wen et al., 2023) stamp a small, highly concentrated mark on a subset of coordinates (e.g., specific Fourier coefficients of initial noise).

The authors unify these paradigms by defining the Information Profile $\nu(t)$, which measures how much information the $t$-th token reveals about the watermark's secret $S$ (such as user ID or payload) given the preceding tokens:

The total mass of this profile, $\|\nu\|_1 = I(S; X) = \Phi(n)$, represents the forensic-recovery budget.

How This Work Compares to Prior Art

Methodology

The authors analyze watermarks across a "forensic ladder" of four statistical tasks:

Level 3: Localize (Where is the mark?)     --> Requires Shape/Footprint
Level 2: Extract (What is the payload?)     --> Requires Mass
Level 1: Attribute (Which of N users?)      --> Requires Mass
Level 0: Detect (Is it AI-generated?)       --> Requires Presence / Divergence

1. The Surprisal-Threshold Decoder

The natural, naive way to attribute a text is to count "collisions"—checking which of the $N$ user keys is consistent with the generated text. However, this count-based approach is highly sensitive to the Rényi-2 collision rate $r_2$, which overcharges the sample complexity.

To reach the true Shannon entropy limit $h$ of the source, the authors propose a Surprisal-Threshold Decoder (Definition 3.5). Instead of comparing keys against each other, this decoder scores each candidate key against its own realized surprisal $\iota(X) = -\log p_{\text{nat}}(X)$.

def surprisal_threshold_decoder(X, keys, p_nat, delta):
    """
    X: Observed token sequence of length n
    keys: Registry of N candidate keys {k_1, ..., k_N}
    p_nat: The natural language model distribution
    delta: Target per-innocent false-positive probability
    """
    # 1. Compute realized surprisal of the sequence
    surprisal = -sum(log(p_nat(X[t] | X[:t])) for t in range(len(X)))
    
    # 2. Set the forced threshold
    N = len(keys)
    threshold = log(N / delta)
    
    if surprisal <= threshold:
        return "Failure: Insufficient sequence length"
        
    # 3. Identify consistent keys
    consistent_keys = []
    for user_id, key in enumerate(keys):
        if is_consistent(X, key):
            consistent_keys.append(user_id)
            
    if len(consistent_keys) == 1:
        return sorted(consistent_keys)[0] # Successful unique attribution
    else:
        return "Failure: Ambiguous or no match"

2. Footprint-Resolution Uncertainty

For Level 3 (Localization), the paper proves a fundamental uncertainty principle. Under an edit-based coupling (Assumption 2.3), any $w$-crop-robust scheme must satisfy:

where $|R|$ is the footprint size and $w$ is the crop window resolution. This means that a small-footprint embedding scheme cannot be crop-robust at fine resolution. To survive cropping, a watermark must have a full-support, biasing footprint.

Key Results

The paper's main theoretical and empirical results settle the sample complexity ($n$) required for each forensic task:

The Forensic Ladder Cost Matrix

The "Collision Trap" Overcharge on Real LLMs

The paper evaluates the gap between the Shannon entropy rate $h$ and the Rényi-2 collision rate $r_2$ on three deployed language models under exponential-minimum-sampling (EMS) watermarks.

Analysis of Figure 10 & 11: On GPT-2, naive collision counting predicts a cost governed by $r_2$, whereas the surprisal threshold decoder achieves the $h$-rate. The shaded "forensic gap" represents the region where a text is statistically detectable as machine-generated but mathematically unattributable to a specific user due to insufficient sample length.

Limitations & Open Questions

1. Lack of Edit-Robustness in the Tight Rate: The mathematical proof of the optimal $\Theta(\log N / h)$ rate for Level 1 attribution relies on an exact-alignment decoder. In practice, edits (insertions, deletions, substitutions) break this alignment. Finding an edit-robust, distortion-free attribution decoder that achieves the $h$-rate remains an open challenge.
2. The "Unattributable" Window: Under biasing watermarks, there is a wide window of sample lengths where a regulator can prove a text is AI-generated (Level 0) but cannot legally attribute it to a specific user (Level 1) without violating the target false-positive rate $\delta$. This means "anonymous" watermarked text is a structural reality.
3. The Footprint-Resolution Tradeoff: If you want to build a system that detects copyright infringement on short, cropped snippets (small $w$), you are forced to use a full-support biasing mark, which inherently degrades the generation quality across the entire document.

What Practitioners Should Do

If you are designing or auditing generative model watermarking pipelines, implement the following steps:

1. Upgrade Your Decoders to Use Surprisal Thresholding

Stop using simple key-matching/collision-counting strategies for user tracing. They are statistically inefficient. Instead, calculate the per-token negative log-likelihood of the natural model:

# Example logic using Hugging Face model outputs
loss = model(input_ids, labels=input_ids).loss
realized_surprisal = loss * len(input_ids)

Only implicate a user key if the realized surprisal clears the threshold $\tau = \log(N/\delta)$.

2. Define Forensic Boundaries in Your SLAs

Do not promise downstream clients that your watermarked LLM outputs can be attributed to individual users on short texts. For a system with $N = 10^6$ users and a target false positive rate of $\delta = 10^{-4}$ on GPT-2:

• Detection is highly confident at $n \approx 30$ tokens.
• Attribution is mathematically impossible below $n \approx \log(10^6/10^{-4}) / 3.81 \approx 23.0 / 3.81 \approx 6$ tokens (assuming a distortion-free scheme). In practice, under biasing watermarks, it will require hundreds of tokens.

3. Pair Watermark Types with Deployed Rungs

• If your goal is tamper detection or copyright localization (Level 3), you must use fine-readout, full-support watermarks (like SEAL or EditGuard).
• If your goal is high-fidelity detection only (Level 0), use distortion-free, global-readout schemes (like Kuditipudi et al.'s EMS or SynthID-Text). Do not attempt to force these schemes to perform localization.

The Takeaway

Watermarking is not a magical silver bullet that can simultaneously hide messages, locate edits, and identify users. This paper establishes that every forensic question is a withdrawal from a single, fixed information budget. If you spend your information mass on detecting a watermark, you have less budget left to name the user. Regulators and developers must accept that under the laws of information theory, a watermark can easily be loud yet entirely anonymous.

Den's Take

I love mathematically rigorous reality checks, and this paper delivers a crucial one to regulators dreaming of painless AI provenance. There is a massive, often ignored gap between simply detecting synthetic text and actually attributing it to one of millions of users.

By unifying watermarking under the "information profile," this work exposes the harsh physical limits of tracing. If you are deploying enterprise LLM tracing to meet compliance mandates, you cannot treat watermarks as magic, un-croppable serial numbers. I am particularly pleased to see the authors ground this in decoder efficiency: pointing out that naive collision-counting decoders waste up to $1.61\times$ more sample complexity on GPT-2 than an optimal surprisal-threshold decoder is the exact kind of practitioner-focused optimization we need.

This has direct implications for system architecture. While verifying model identity can be efficient, scaling down to track $N$ individual users introduces a steep $\Theta(\log N / h)$ token cost. If your security architecture relies on watermarks to catch bad actors in generation pipelines, prepare for a stark trade-off between user-tracking resolution and generation quality.