Watermark Forensics for Generative Models: An Information-Theoretic Perspective
arXiv:2607.13003v1 introduces a unified information-theoretic framework that quantifies sample complexity costs across the forensic ladder—detection, attribution, payload extraction, and localization—for watermarks in generative model outputs: attribution to one of $N$ users requires $\Theta(\log N/h)$ tokens under statistically distortion-free schemes, where $h$ is the per-token average conditional mutual information lower bound, while detection depends solely on distributional distance—not information.
Core Result: The Forensic Ladder and Its Information-Theoretic Costs
This paper establishes an information-theoretic model that organizes four canonical watermark forensic capabilities—detection, attribution, payload extraction, and localization—into a hierarchical "forensic ladder", and rigorously characterizes the minimal output length $n$ (i.e., number of tokens) required for each level.
- Detection depends only on existence: its cost is governed by statistical distance (e.g., KL divergence or total variation) between the marked and unmarked distributions—not by information content;
- Attribution and payload extraction depend on total information: the mutual information $I(S; X_{1:n})$ between the secret $S$ (e.g., user ID or embedded payload) and the full sequence $X_{1:n}$;
- Localization further depends on temporal information structure: captured by the information profile $\nu(t) = I(S; X_t \mid X_{<t})$, i.e., how much the $t$-th token reveals about $S$ given prior tokens.
Key Modeling: The Information Profile $\nu(t)$ Unifies Two Watermark Paradigms
The function $\nu(t)$ quantifies the incremental information about secret $S$ carried by token $t$. Its:
- Total mass, $\sum_t \nu(t) = I(S; X_{1:n})$, determines feasibility of attribution and extraction;
- Temporal spread (e.g., concentrated vs. uniform) governs robustness of localization;
- Detection capability is fully decoupled from $\nu(t)$ and instead determined by $f$-divergence (e.g., $\chi^2$ or KL) between marked and unmarked distributions.
Thus, the two dominant watermark design paradigms in literature—"fine-grained subtle watermarking" (small $\nu(t)$ per token) and "coarse-grained loud watermarking" (large $\nu(t)$ on few tokens)—are shown to be two incomparable ways of capping $\nu(t)$, with no universal superiority.
Main Theorem: Entropy-Rate Scaling Law for Attribution
Under statistically distortion-free watermarking schemes, the paper’s main theorem establishes that attributing a text to one of $N$ users requires $\Theta(\log N / h)$ tokens, where $h$ is a lower bound on the per-token average conditional mutual information $\mathbb{E}[\nu(t)] \geq h$. This result provides the first tight information-theoretic sample complexity characterization for attribution, revealing it as fundamentally constrained by Shannon entropy rate and channel capacity jointly.