Watermark Forensics for Generative Models: An Information-Theoretic Perspective

Technical Summary: Watermark Forensics for Generative Models: An Information-Theoretic Perspective

Problem Statement
The paper addresses the forensic capabilities of watermarks in generative models, moving beyond the binary question of "is this content machine-made?" (detection) to a hierarchy of more complex tasks: attribution (identifying which of $N$ users generated the content), extraction (recovering a hidden payload), and localization (identifying the specific region of the content carrying the mark). The authors argue that existing literature treats these as disparate problems with ad-hoc solutions, often conflating the mechanism of embedding (e.g., "embedding" a pattern vs. "biasing" a distribution) with the fundamental information-theoretic limits of what can be recovered. The central question is: what is the sample complexity (length $n$) required for each forensic task, and how do these costs relate to the watermark's quality constraints (fidelity, distortion budget, or entropy)?

Methodology and Framework
The authors introduce a unified framework organized around a single object: the information profile $\nu(t)$.

• Definition: $\nu(t) := I(S; X_t | X_{<t})$, where $S$ is the secret (user identity or payload), $X$ is the generated carrier (sequence of tokens), and $X_{<t}$ represents the preceding tokens. This measures the information about $S$ revealed by the $t$-th token, conditioned on the past.
• The Forensic Ladder: The paper models forensic tasks as a ladder of statistical problems:
  • Level 0 (Detection): Is the mark present? (Mechanism-blind baseline).
  • Level 1 (Attribution): Which of $N$ users?
  • Level 2 (Extraction): What is the $\ell$-bit payload?
  • Level 3 (Localization): Where is the mark? (Robust to cropping).
• Quality Models: The framework unifies two distinct quality models found in literature as "norm caps" on the same profile $\nu$:
  1. Bounded-Distortion (Biasing) $B(\Delta)$: The mark is subtle on every token, imposing an $L_\infty$ cap ($\nu(t) \le \Delta$). Examples include Green-list watermarks.
  2. Footprint (Embedding) $E(m)$: The mark is concentrated on a small set of positions (footprint $T$ with $|T| \le m$), imposing an $L_0$ cap ($\nu(t) = 0$ for $t \notin T$). Examples include Tree-Ring.
• The Forensic-Recovery Budget: By the data processing inequality, the total recoverable information is bounded by the mass of the profile: $\Phi(n) = \|\nu\|_1 = I(S; X)$. This budget funds both attribution and extraction.

Key Contributions and Results

1. Closing the Entropy Column (Attribution in Distortion-Free Regimes):

   • The paper establishes the first tight sample complexity law for multi-user attribution in statistically distortion-free schemes (where the key-averaged output is indistinguishable from the natural distribution).
   • Result: For a stationary-ergodic source with entropy rate $h$, attributing a text to one of $N$ users costs $n_{att} = \Theta(\log N / h)$ tokens.
   • Mechanism: The authors propose a surprisal-threshold decoder. Unlike naive "consistency" decoders that count matching keys (which suffer from the "collision trap" and require $n \approx \log N / r_2$, where $r_2$ is the Rényi-2 rate), the surprisal decoder accepts a key only if the realized surprisal $-\log p_{nat}(X)$ exceeds a threshold $\tau = \log(N/\delta)$. This achieves the Shannon rate $h$ with an exact, non-asymptotic per-innocent false-positive guarantee ($\delta/N$).
   • Significance: This resolves the gap between the converse (Fano bound) and achievability, showing that the Shannon entropy rate, not the collision rate, governs the decision complexity.

2. The Forensic Gap (Detection vs. Attribution):

   • The paper proves that detection and attribution are fundamentally different costs. Detection is a fixed two-point test costing $\Theta(1/\Delta)$ (or $\Theta(\lambda/h)$ for distortion-free), independent of $N$. Attribution requires extracting $\log N$ nats of identity.
   • Result: There exists a "forensic gap" window where a text is detectable (error $\to 0$) but unattributable (error $\to 1$). Specifically, for biasing schemes, attribution requires $n \approx \log N / \Delta$, while detection saturates much earlier.
   • Implication: A text can be proven machine-made without being attributable to a specific user.

3. Decoupling via Footprint (The Two Quality Models):

   • The paper formalizes the distinction between "biasing" (full support) and "embedding" (small footprint) schemes.
   • Result:
     • Biasing ($B(\Delta)$): Attribution costs $\Theta(\log N / \Delta)$. The cost is coupled to the distortion budget; making the mark stealthier ($\Delta \to 0$) makes attribution infinitely expensive.
     • Embedding ($E(m)$): Attribution costs $\Theta(\log N / \log q)$, independent of any per-token distortion cap. Imperceptibility is achieved by a vanishing footprint ($m/n \to 0$), not by subtle per-token distortion.
   • Limitation: The paper notes that while the information-theoretic decoupling exists, the only known witness (a "digit stamp") is not robust to editing. Deployable schemes that localize (e.g., SEAL, EditGuard) are found to be full-support (biasing) but achieve localization via fine-grained readout, not small footprints.

4. Localization and the Uncertainty Principle:

   • The paper derives a footprint-resolution uncertainty principle for crop-robust localization.
   • Result: To localize a mark to a window of size $w$ robustly against cropping, the carrier footprint must satisfy $|R| \cdot w = \Omega(n)$.
   • Implication: A small-footprint embedding scheme ($m = o(n)$) cannot be crop-robust at fine resolution. Fine-resolution localization forces the mark to have full support (biasing), effectively ruling out small-footprint schemes for robust localization tasks.

5. Empirical Validation:

   • The authors validate the "collision trap" on real language models (GPT-2, Pythia-410M, Qwen2.5). They measure the ratio $h/r_2 \approx 1.6$ across models, confirming that naive consistency-based decoders overcharge by this factor compared to the optimal surprisal-threshold decoder.
   • Experiments on the Green-list watermark confirm the forensic gap: detection saturates at $\approx 28$ tokens, while attribution accuracy lags significantly, growing linearly with $\log N$.

Significance and Claims
The paper claims to provide the first tight, two-sided information-theoretic laws for the sample complexity of attribution and extraction in generative models.

• Unification: It unifies disparate forensic tasks (detection, attribution, extraction, localization) and quality models (biasing vs. embedding) under a single measure: the information profile $\nu(t)$.
• Regulatory Impact: The authors argue that current regulations (e.g., EU AI Act) often presume an "extractable object" (embedding ontology). The paper's results show that for biasing watermarks (the dominant class in practice), such mandates come with a diverging sample cost ($\Theta(\log N / \Delta)$) as the mark becomes stealthier, whereas embedding schemes offer a fixed cost but are currently limited by robustness constraints.
• Open Problems: The paper explicitly identifies the lack of a distortion-free, edit-robust attribution scheme as the sharpest open problem. While the theoretical rate $\Theta(\log N / h)$ is closed, the existing witness (exact alignment) is not robust to edits. It remains open whether an edit-robust decoder can achieve this rate or if it is forced back to the higher Rényi-2 cost.

In summary, the paper posits that the forensic power of a watermark is not determined by the mechanics of its embedding, but by the information it makes recoverable (the profile $\nu$) and the geometry of its footprint. The "prices" of forensic tasks are strictly governed by these information-theoretic quantities.