Watermark Forensics for Generative Models An Information-Theoretic Perspective Xiaoyu Li1
Zheng Gao1
Xiaoyan Feng2
Jiaojiao Jiang1
Yulei Sui1
Jiankun Hu1
1
University of New South Wales
2
Griffith University
{xiaoyu.li2, zheng.gao1, jiaojiao.jiang, yulei.sui}@unsw.edu.au [email protected]
July 15, 2026
arXiv:2607.13003v1 [cs.CR] 14 Jul 2026
Abstract. A watermark in a generative model’s output is normally asked only whether a text is machine-made. The
same mark can do more: attribute it to the user who produced it, extract a hidden payload, or localize the part that survives editing. These form a forensic ladder, and we ask what each rung costs in the sample length n. A single object organizes the answers. Let S be the secret the mark carries (a user’s identity, a payload), and let the information profile ν(t) = I(S; Xt | X<t ) measure how much the t-th token reveals about S given the earlier ones. Its total pays for attribution and extraction; how it is spread across the text pays for localization; and detection alone is paid for not by information but by presence, the distance from the marked to the unmarked distribution. The two quality models in the literature, a mark subtle on every token and one that stamps a few tokens loudly, are then incomparable ways of capping this one profile. Our main theorem settles the ladder’s entropy column. For schemes that leave the model’s output distribution statistically intact, attributing a text to one of N users costs Θ(log N/h) tokens over every stationary-ergodic source of entropy rate h, sharp to a (1 + o(1)) factor; to our knowledge the first tight entropy-rate law for multi-user attribution (via exact alignment; the edit-robust case is open). A warning: the natural collision-counting argument overcharges without bound, and only a decoder that scores each candidate by its own realized surprisal, not against the others, attains the rate while almost never implicating an innocent user. A matching converse makes the law two-sided, and the same accounting prices extraction of an ℓ-bit payload at Θ(ℓ/h). Two gaps are real rather than modeling artifacts: a window Θ(log N ) tokens wide in which a text is provably machine-made yet unattributable, and an uncertainty principle trading a mark’s footprint against its localization resolution. Since emerging regulation presumes an extractable mark, these are limits it inherits rather than escapes. Across three language models (GPT-2, Pythia-410M, Qwen2.5) under deployed watermarks, the predicted constants appear: the collision analysis overcharges by about 1.6×, and detection saturates its Θ(log N ) window before attribution begins. cost n Detection ̸= Attribution ℓ Θ( ∆ )
m w=Ω(n)
Localize
one measure ν(t) = I(S; Xt | X<t ) biasing B(∆) subtle on every token, full support ∆: an L∞ cap
N Θ( log ∆ )
Extract
Attribute embedding E(m) a short, loud stamp
Θ(1/∆)
Detect is it marked?
which of N users?
what payload?
where?
1
2
3
0 mechanism-blind
(a) the forensic ladder
footprint m: an L0 cap same shaded mass ∥ν∥1 = I(S; X) ≥ log N , two shapes
(b) one profile ν(t), two caps
Figure 1: The forensic ladder, and the one measure beneath it. (a) The four forensic questions form a sample-complexity ladder. Detection is cheap and mechanism-blind; but attribution is not free (naming one of N users costs Θ(log N/∆) or Θ(log N/h) in the appropriate per-token currency, the jump from detection to attribution), and extraction and crop-robust localization sit higher still. (b) The rungs above detection are read off a single object, the information profile ν(t) = I(S; Xt | X<t ). The literature’s two quality models are two incomparable caps on the same ν: a biasing mark spends the mass thinly under an L∞ height cap ∆ (subtle on every token, full support), an embedding mark concentrates it under an L0 width cap m (a short, loud stamp). Same shaded mass ∥ν∥1 = I(S; X), two shapes.
Contents 1 Introduction
3
2 Model: the forensic ladder
5
2.1 The information profile . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
2.2
9
Useful tools . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3 Results
10
3.1 The forensic-recovery budget . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
3.2
Detection is not attribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
3.3 Two quality models, and the localization map . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
3.4
Closing the entropy column . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
3.5
Level 3, and a shared budget . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16
3.6
Numerical illustration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
3.7
Confirmation on deployed language models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
19
4 The framework applied: a taxonomy of deployed watermarks
20
5 Related work
22
6 Discussion
25
7 Conclusion
27
A Notation
33
B Information-theoretic background
33
C Deferred proofs
34
C.1 Prior results we import, and their terminology . . . . . . . . . . . . . . . . . . . . . . . . . . . .
34
C.2 The forensic-recovery budget . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
35
C.3 Attribution converse and the forensic gap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
36
C.4 Two quality models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
37
C.5 Level 3: footprint–resolution and the rate region
. . . . . . . . . . . . . . . . . . . . . . . . . . .
39
C.6 Proof of Theorem 3.6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
40
C.7 The overlap identity and the candidate list . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
42
C.8 Two definitional witnesses: why the per-secret recut is necessary . . . . . . . . . . . . . . . . . . .
42
D How deployed watermarks fit the framework D.1 Language-model watermarks
43
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
43
D.2 Image and audio watermarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
44
E Additional related work
45
F What is a watermark? A philosophical and historical discussion
47
2
Watermark Forensics for Generative Models
1
Introduction
Consider two deployed watermarks for generative models. Tree-Ring (Wen et al., 2023) embeds a ring pattern into the Fourier spectrum of a diffusion model’s initial noise; to test an image one inverts the generation and matches the ring. The green-list of Kirchenbauer et al. (2023) colours half the vocabulary green at each decoding step and tilts the next token toward it; to test a passage one counts green tokens. Tuned to the same detection ROC, the two are interchangeable for the question is this AI-generated. Now ask a second question. Given the marked image, can one point to where the mark lives? Yes: invert to the noise and read off the ring. Given the marked text, can one point to which tokens are the mark? Not in any strict sense; every token is plausible under the natural distribution, and the mark exists only in the statistical aggregate of the whole passage. In the second case the watermark is a property of the carrier, not an object inside it, and asking which tokens are the mark is a category error, much as one cannot ask which molecules of a warm gas carry its temperature. The distinction has direct consequences for attribution, extraction, and regulation, and the literature treats it only case by case. This paper makes that informal gap quantitative. We treat the forensic uses of a watermark as a ladder of four statistical problems on a length-n carrier: Level 0 detection (machine-generated or not), Level 1 attribution (which of N users produced it), Level 2 extraction (recover an ℓ-bit payload), and Level 3 localization (which sub-region carries the mark). We ask for the sample complexity of each. The detection rung is by now well understood: under a per-token distortion budget ∆ (each marked conditional within KL ∆ of the natural one), detection costs Θ(1/∆) tokens, with sharp constants (Cai et al., 2024; Huang et al., 2023; Li et al., 2025b). We import this rung and never reprove it. Our question is what happens above it, and whether the embedding-versus-biasing distinction that separates our two examples is a real boundary or a matter of taste. One object. It is a real boundary, and one measure draws it. Every forensic question asks how much of the secret S a decoder can recover from the carrier X; by data processing this is at most the mutual information I(S; X), the number of nats that observing X reveals about S (for attribution and distortion-free extraction, conditioned on the decoder’s public key registry; Section 2, and a primer on the information-theoretic notions P is in Section B). The chain rule resolves it position by position, I(S; X) = t I(S; Xt | X<t ), each summand the information about S that the t-th token adds given its past. This is the information profile of the scheme’s forensic payload S, ν(t) := I(S; Xt | X<t ), t = 1, . . . , n. Attribution and extraction are recovery questions, how much of S, so each is governed by the total mass ∥ν∥1 = I(S; X); localization asks not how much but where, so it reads the shape supp ν, the footprint of Definition 2.4. Detection is the exception: the imported baseline asks only whether the mark is present, priced by how far the marked law sits from natural and not by the mass — a scheme can make S recoverable yet be undetectable without the key. Our two opening examples are the extremal profiles (Figure 1): the green-list spreads its mass ∆-thin over every position, while Tree-Ring concentrates it on a vanishing set of transform coordinates. The profile is written once, at generation time: by data processing, no reading of the carrier can recover more about S than the sampler put in, so what any decoder can ever learn is fixed by the ν the scheme writes. This is the paper’s one idea: the forensic power of a watermark is set by the information it makes recoverable, position by position — the profile — and not by the mechanics of how the mark is embedded. The literature asks four questions of a watermark and treats them as four problems; detection is the mechanism-blind baseline, and the three rungs above it are readings of ν. Everything below is a statement about functionals of it. The profile earns its keep as the object that unifies the ladder above detection — attribution, extraction, and localization, together with the two quality models, become functionals of one measure — more than as a proof device: the scalar mass ∥ν∥1 already separates attribution and extraction, while the per-position shape does load-bearing work only in the mechanism dichotomy (Theorem 3.3) and in localization (Theorem 3.12). We are explicit throughout about which is which. Contributions. The contribution is the object; each result below is a way of reading it. • One measure, two norms (Proposition 2.6). The chain rule gives the exact identity ∥ν∥1 = I(S; X) = Φ(n), the quantity the forensic-recovery budget caps. The two quality models of the literature are then norm caps on ν: the distributional model B(∆) caps it in L∞ (ν(t) ≤ ∆ at every position, via the golden formula), and the footprint model E(m) caps it in L0 (ν supported on at most m positions, by conditional 3
Watermark Forensics for Generative Models
screening). We organize what were two incomparable quality models and a separately stated footprint axis as one object read two ways; the incomparability becomes definitional, two norms on one measure. Only the mass is invariant to the choice of dictionary and ordering; the caps, like sparsity, are relative to a fixed basis. Crop-robustness is the one property not of ν alone: it additionally needs an edit coupling on the carrier footprint. • The entropy column closes (Theorem 3.6). For statistically distortion-free schemes with i.i.d. per-user keys (the decoder knows pnat and the deployed key set), attribution among N users costs log N log N , and natt = (1 + o(1)) natt = Θ h h as the per-innocent false-positive level δ → 0 with log(1/δ) = o(log N ) (the log(1/δ) term is then lower order), for every stationary-ergodic source of entropy rate h > 0; the Shannon–McMillan–Breiman theorem is the only source hypothesis. To our knowledge this is the first tight h-rate for multi-user attribution. Achievability is a surprisal-threshold decoder, and its threshold is forced, not tuned: an innocent key matches the observed text only with probability pnat (X) = e−ı(X) , where ı(X) = − log pnat (X) is the realized surprisal, so to implicate no innocent above δ/N the decoder must answer only when ı(X) > τ = log(N/δ) (then pnat (X) < δ/N ); completeness only asks that the true text, being pnat -typical, clear that same bar, which it does once n ≥ τ /h. The obvious decoder instead reports any consistent key; bounding its error means counting the innocents consistent by chance, (N − 1)e−nr2 , and waiting for that list to clear at log N/r2 , the Rényi-2 collision rate. But the forensic question is not list size; it is naming one user with a guarantee, governed by the Shannon rate h. Since r2 ≤ h, and can be far smaller, the consistency count overcharges by the unbounded factor h/r2 (Proposition 3.9). That guarantee is exact and non-asymptotic, and for the deterministic witness scheme pointwise, which is the form a forensic guarantee has to take: no innocent user is implicated except with probability δ/N — at every length, for every source, for every realized set of innocent keys. The matching converse is Fano plus a mixture-entropy bound on the i.i.d. key draw. Extraction is the same theorem at N = 2ℓ , giving Θ(ℓ/h) (Corollary 3.7). The entropy column of the ladder, previously a converse-only ledger, is thereby two-sided. • The rest of the ladder, as readings of ν (Theorems 3.1 to 3.3 and 3.12 and Proposition 3.13). The mass and the shape of one measure, read five more ways. The forensic-recovery budget Φ(n) = ∥ν∥1 ≤ n∆, (n) respectively ≤ n hn (hn := H(pnat )/n ↓ h, the entropy rate). The co-located window: a length at which a biasing watermark is detectable with error → 0 yet every attribution rule errs with probability → 1, within a single scheme. The dichotomy at the extremal profiles: B(∆) couples, natt = Ω(log N/∆) (tight for regular mixing sources), while E(m) decouples, natt = Θ(log N/ log q), ∆-free; a localization map enables the cheaper model but does not decide it (Corollary 3.4). The footprint–resolution uncertainty m · w = Ω(n): fine-resolution crop-robustness forces full support. And the rate region: attribution and extraction split one mass, Ratt + Rext ≤ (1 + o(1)) n∆, order-tight. What is imported and what is ours. The Level-0 detection rate and the fidelity–detectability frontier are imported (Cai et al., 2024; Huang et al., 2023; Li et al., 2025b), as is the distortion-free detection rate (Christ et al., 2024). The attribution converse in the B(∆) column is the single-user Fano specialization of the distortion-constrained fingerprinting converse of Moulin (2008); Somekh-Baruch and Merhav (2005); we claim no novelty for it. The false-positive mechanism behind Theorem 3.6 is the folklore likelihood-ratio Markov bound (a one-line change of measure); we claim its use here, not the inequality. Ours are: the profile as the organizing object and the norm-cap reading of the quality models; the closed entropy column, that is, the decoder, its exact false-positive side, and tightness at full stationary-ergodic generality; the co-located window; the footprint– resolution uncertainty; the rate region; and the taxonomy. We flag plainly that the entropy-column witness decodes by exact alignment and is not edit-robust; edit-robust ∆-free attribution remains open. The closest prior work proves complementary things: Cohen et al. (2025) construct multi-user watermarks where detection is cheap and tracing is expensive, with a cryptographic counting argument but no tight information-theoretic rate in h; Jiang et al. (2024) argue empirically that detection and attribution coincide under a strict threshold; the SoK of Zhao et al. (2025a) taxonomizes schemes on a security axis, with no sample-complexity content; concurrent work (He et al., 2025a) studies the scalar I(S; X) without the positional decomposition on which our questions turn. We position against each in Section 5. 4
Watermark Forensics for Generative Models
Why these questions. Watermarking is becoming provenance infrastructure: the mechanism by which a world filling with synthetic content is supposed to answer who made this. The four rungs of the ladder are the operational content of that hope, and they are not one capability but four, with four prices. What theory can contribute is the price list: which questions are priced by the population (attribution: a log N toll in the appropriate currency), which are not (detection), and which are structurally unavailable (fine crop-robust localization for any small-footprint mark, Theorem 3.12). Regulation makes the list concrete. Watermark statutes tacitly assume the embedding ontology, asking for marks “in a machine-readable format” and the like: language that presumes an extractable object. Our dichotomy prices that presumption: a biasing watermark cannot meet an attribution or localization mandate at any fidelity without a sample cost that diverges as the mark is made stealthier, and the closed entropy column gives an attribution mandate its price when the mark is distortion-free, Θ((log N + log(1/δ))/h) tokens with a per-innocent false-positive guarantee of δ/N . A statute can mandate a capability; it cannot repeal an inequality. We return to this in Section 6. Organization. Section 2 sets the model, the quality assumptions, and the information profile (Proposition 2.6). Section 3 states the results: the forensic-recovery budget, the closed entropy column (Theorem 3.6), the co-located window, the dichotomy, the uncertainty bound, and the rate region, with a numerical illustration and, on three watermarked language models (GPT-2, Pythia, Qwen2.5), a measurement of the operative constants (Section 3.7). Section 4 reads twenty deployed schemes through the profile. Section 5 positions the paper against prior and concurrent work, Section 6 draws consequences and states the open problems, and Section 7 concludes. Proofs are in Section C, which also contains the imported-results glossary (Section C.1), the scheme-by-scheme fit of the deployed watermarks (Section D), and a broader survey of adjacent work (Section E).
2
Model: the forensic ladder
The model has three ingredients: a carrier, the laws that generate it, and a keyed family that secretly selects among those laws; every forensic task is a question about the selection. Carrier, model, keys. Tokens are drawn from an alphabet Σ of size q := |Σ|; a carrier is a sequence X ∈ X := Σn . An unmarked model induces the natural law pnat on X . A keyed watermarking scheme draws (K) (K) a secret key K ∼ µ from a key space K and generates X ∼ pwm ; write p̄ := EK pwm for the key-averaged output law. The secret S (a user identity in [N ], an ℓ-bit payload, or both) determines the key, K = K(S), so S → K → X is a Markov chain. The primary object throughout is the family of per-secret kernels pwm (· | s, x<t ) (the conditional next-token law under secret s given the prefix x<t ) from which key-averaged quantities are derived, never the reverse. Decoders are informed: an attribution decoder knows pnat and the key registry κ := {k1 , . . . , kN }, and false-positive statements are averaged over the i.i.d. draw of those keys. Recoverable information is measured against this side information: throughout, the per-secret quantities — the kernels ¯ and the budget Φ — are read conditionally pwm (· | S, x<t ), the information profile ν, the distortion profile d, ¯ on the registry κ, written I(S; X), d(t), and so on for brevity. Given κ the secret determines its key, K = kS , so each per-secret object is the realized per-key one and every average over S ranges over the enrolled keys. This conditioning is vacuous for a fixed registry (a single enrolled key, detection, or deterministic extraction). It matters for any randomized registry with exchangeable keys — bounded schemes included, since marginally over the key draw the carrier is independent of the secret — and is sharpest for the distortion-free witness of Theorem 3.6, whose output is exactly pnat : there the unconditional I(S; X) = 0 while the registry-conditional budget is positive, and it is that conditional quantity the converse bounds by nhn . All logarithms are natural unless a base is shown; KL(· ∥ ·) is relative entropy and I(·; ·) mutual information, both in nats. Quality as a budget. Fidelity to the base model is what makes a watermark usable, and it is what constrains forensic power. We consider the two quality models that occur in practice, both stated on the per-secret kernels. ¯ := EX ES KL(pwm (· | S, X<t ) ∥ pnat (· | X<t )) for the per-secret distortion profile (expectations Write d(t) <t Pn ¯ under the joint marked law), so by the chain rule t=1 d(t) = ES KL(pwm (· | S) ∥ pnat ), and T := {t : pwm (· | s, x<t ) ̸= pnat (· | x<t ) for some s, x<t } for the per-secret footprint, the set of marked positions. A natural alternative is the key-averaged marginal profile δmarg (t) := EX<t KL(ES pwm (· | S, X<t ) ∥ pnat (· | X<t )); joint ¯ convexity of relative entropy gives the bridge δmarg (t) ≤ d(t), and the inequality is strict in general (Section C.8). We retire the marginal profile because it cannot see information hidden in correlations across positions: the 5
Watermark Forensics for Generative Models
two-token parity scheme (Section C.8) has zero marginal distortion at every position, yet a decoder reads one full bit from it (ν(2) = log 2 below). Every cap below is therefore stated on the per-secret kernels. Assumption 2.1 (Bounded-distortion quality; the class B(∆)). There is a per-token budget ∆ ≥ 0, imposed in one of two forms. Sup-form: KL(pwm (· | s, x<t ) ∥ pnat (· | x<t )) ≤ ∆ for every secret s, prefix x<t , and ¯ ≤ ∆. The sup-form implies the avg-form, and we tag each claim with the position t. Avg-form: maxt d(t) form it needs: every converse below needs only the avg-form, while the exponential-tilting achievability (k) witness satisfies the sup-form. By the chain rule the global divergence inherits the cap: KL pwm ∥ pnat ≤ n∆ P ¯ for every key k under the sup-form, and ES KL(pwm (· | S) ∥ pnat ) = d(t) ≤ n∆ under the avg-form. Each token stays ∆-close to natural on average; the mark is delocalized.
t
Assumption 2.2 (Distortion-free quality). The mixture is undetectable without the key, at one of two levels. Sequence level: p̄ = pnat (statistically) or p̄ ≈ pnat up to a negligible distinguishing advantage (computationally) — the operational statement: no key-less observer detects the mark. Kernel level: EK pwm (· | K, x<t ) = pnat (· | x<t ) for every prefix x<t — the structural statement, satisfied by the exact-sampler family (inverse-CDF / exponential-minimum sampling; Kuditipudi et al., 2023; Section 4), and implying the sequence level wheneverthe key coordinates consumed at distinct positions are position-independent. (k) The per-key divergence KL pwm ∥ pnat is unconstrained; the binding resource is the generation entropy (n)
(n)
hn := H(pnat )/n, where pnat is the length-n law; for stationary sources hn decreases to the entropy rate h := limn hn , and finite-n statements use hn , asymptotic ones h. We state for each result which level it uses. Assumption 2.1 is the regime of green-list and tilting schemes (Kirchenbauer et al., 2023); Assumption 2.2 is the regime of distortion-free and undetectable schemes (Christ and Gunn, 2024; Christ et al., 2024; Dathathri et al., 2024; Kuditipudi et al., 2023). For the localization results (Section 3, Level 3) we use one structural hypothesis, satisfied by the deployed schemes. Assumption 2.3 (r-local / edit-based). There is a set R ⊆ [n] (the carrier footprint), a constant r, and a coupling of the marked carrier X with an unmarked carrier X ′ ∼ pnat such that X and X ′ agree on every coordinate outside the dilated footprint R+ := {i : dist(i, R) ≤ r}; for a scheme in the footprint-capped class E(m) of Definition 2.4 one may take R = T when the natural law factorizes across positions (off-T kernels then depend on no marked prefix; a perfectly correlated source admits no such coupling). Equivalently, the watermark is a local edit confined to a neighbourhood of R and does not propagate elsewhere. This is the post-hoc regime in which Level-3 localization is actually studied: image, audio, and patch watermarks edit only the marked region and leave the rest of the carrier as generated (a biasing scheme such as green-list instead has R = [n], so R+ = [n] and the assumption is vacuous). The consequence we use is immediate: any contiguous window disjoint from R+ has xW = x′W , distributed exactly as pnat . The two mechanisms. The distinction the introduction drew between an object inside the carrier and a property of its law has a clean operational form, which we take from the ontology of generative watermarking (after the steganography trichotomy of Fridrich, 2009) and state informally, since no result below invokes it directly; the operative cut is Definition 2.4. An embedding watermark is a triple (Gen, Embed, Ext) with a carrier-level object space W, maps Embed : X × K × W → X and Ext : X × K → W ∪ {⊥} with Ext(Embed(x, k, w), k) = w for almost all (k, w), and a localization map Lk : X → 2[n] through which alone Ext reads x: the watermark isan object on (k)
(k)
Lk (x). A biasing watermark is a pair (Genwm , Det), where Genwm induces pwm with KL pwm ∥ pnat > 0 (or = 0, indistinguishable only against a bounded distinguisher) and Det : X × K → {0, 1} is a hypothesis test realising a (k) Type-I/Type-II trade-off: the watermark is a property of the law pwm . The two mechanisms come equipped with different native operations (Ext recovers an object at Level 2, Det runs a test at Level 0), which is the seed of the ladder below. What this object-versus-property distinction says about what a watermark is we take up, as a closing reflection, in Section F. 6
Watermark Forensics for Generative Models
The operative refinement: footprint. For the sample-complexity analysis, the object-level reading leaves one thing under-determined: its localization map constrains where the secret is read from, but not the size of Lk (x). A green-list secret is readable from a long enough window, so the read-from criterion alone would miscount it as embedding. The “object inside” intuition needs the region to be small. We therefore read the distinction through the per-secret footprint T . Definition 2.4 (Footprint; embedding vs. biasing). A scheme is embedding if |T | = o(n), so the per-secret kernels are marked on a vanishing fraction of coordinates, and Lk := T is then a localization map (off T the next-token law is exactly natural given the past, for every secret); it is biasing if |T | = Ω(n): a constant fraction of coordinates carry distortion for some secret, so no o(n) region contains the mark and it lives only in the aggregate. The footprint-capped class is E(m) := {|T | ≤ m}; together with B(∆) of Assumption 2.1 it is read in a fixed dictionary and coordinate ordering (see the remarks after Proposition 2.6). Remark 2.5 (Model change: per-secret, not key-averaged). Both classes are cut on the per-secret kernels, not on the key-averaged kernel ES pwm (· | S, x<t ): by the convexity bridge they are strict subclasses of their marginal counterparts, and the marginal cut misclassifies — every kernel-level distortion-free scheme (Assumption 2.2) has key-averaged kernels exactly natural, so the key-averaged support would place all of them in E(0) while they carry Φ(n) > 0. The two cuts separate in both directions (Section C.8): writing ν for the information profile of Proposition 2.6 below, the two-token parity scheme has ν(2) = log 2 while δmarg ≡ 0, and the key-independent kernel-bend has δmarg > 0 while ν ≡ 0. This refinement does real work, and it splits the embedding ontology’s localization map into two orthogonal axes. The footprint T governs whether forensic cost decouples from the distortion budget (Theorem 3.3); the readout resolution of Ext, namely whether the secret is decoded globally or per-region, governs localization (Theorem 3.12), and is independent of the footprint. The two come apart on real schemes: green-list (Kirchenbauer et al., 2023) is biasing (T = [n]) although its secret is recoverable from a window; and SEAL or Gaussian Shading, which an object-level reading would file as embedding, are full-support hence biasing, localizing (when they do) by fine readout rather than by a small footprint (Section 4). The distortion-free family (Kuditipudi, Christ–Gunn) is likewise full-support biasing, living in the entropy regime of Assumption 2.2 rather than the ∆ regime.
2.1
The information profile
The per-secret kernels carry one further object, and it organizes everything that follows: the information profile of a scheme, the measure on positions X ν(t) := I(S; Xt | X<t ), ν(A) := ν(t), ∥ν∥1 := ν([n]). t∈A
Proposition 2.6 (Information profile). For every keyed scheme: (i) (Mass identity.) ∥ν∥1 = I(S; X) = Φ(n). ¯ for every t; hence under Assumption 2.1, in either form, maxt ν(t) ≤ ∆. (ii) (B(∆) is an L∞ cap.) ν(t) ≤ d(t) (iii) (E(m) is an L0 cap.) If the scheme lies in E(m) (Definition 2.4: per-secret kernels unmarked off T , |T | ≤ m, in the fixed dictionary and ordering), then ν(t) = 0 for t ∈ / T ; hence supp(ν) ⊆ T and P Φ(n) = t∈T ν(t) ≤ m log q. Proof. (i) is the chain rule for mutual information. (ii): condition on X<t = x<t and apply the golden formula (Fact 2.11) with reference pnat (· | x<t ), giving I(S; Xt | X<t = x<t ) ≤ ES KL(pwm (· | S, x<t ) ∥ pnat (· | x<t )); ¯ averaging over x<t gives ν(t) ≤ d(t). (iii): for t ∈ / T the kernel pwm (· | s, x<t ) = pnat (· | x<t ) does not depend on s, so Xt ⊥ S | X<t (given the past, the kernel at t is the natural law for every secret, so Xt carries no secret-information there; whatever earlier marked positions did to shape X<t was already counted at those positions) and ν(t) = 0; each surviving term obeys ν(t) ≤ H(Xt | X<t ) ≤ log q. 7
Watermark Forensics for Generative Models
ν(t) = I(S; Xt | X<t ) height ≤ ∆ an L∞ cap (biasing)
shape supp ν width ≤ m: an L0 cap read by localization (Level 3) position t = 1, . . . , n
P
mass ∥ν∥1 = ν(t) = I(S; X) = Φ(n) t read by detection, attribution, extraction (Levels 0–2)
Figure 2: One profile, read two ways (Proposition 2.6). The information profile ν(t) = I(S; Xt | X<t ) is a measure on
positions, and a measure has a total and a support. The forensic tasks above detection are exactly these two functionals: attribution and extraction read the mass ∥ν∥1 = I(S; X) = Φ(n), which the forensic-recovery budget caps (Theorem 3.1); localization reads the shape supp ν; detection is the mechanism-blind baseline, priced by presence. The two quality models of the literature are then two caps on the same ν: a height cap ν(t) ≤ ∆ (L∞ , Proposition 2.6(ii), biasing) and a support cap | supp ν| ≤ m (L0 , Proposition 2.6(iii), embedding).
Remark 2.7 (Two caps, one object). Proposition 2.6 reads the two quality models as norm caps on the same measure: B(∆) caps ∥ν∥∞ and E(m) caps ∥ν∥0 , the support size; their incomparability is now definitional (different norms on one object) rather than a contingency of two ontologies (Figure 2). How the forensic tasks read ν (mass for Levels 1–2, shape plus the edit coupling for Level 3; detection, Level 0, reads neither) is spelled out under Mass, shape, robustness below. Remark 2.8 (Basis and ordering relativity). ν is computed in a coordinate system: a dictionary in which X is written and an order in which its coordinates are revealed. Only the mass ∥ν∥1 = I(S; X) is invariant; the L∞ and L0 caps (and with them the embedding/biasing cut of Definition 2.4) are stated relative to a fixed dictionary and ordering, declared once per scheme (for Tree-Ring, the latent-Fourier dictionary; Section 4). This is the same relativity as sparsity, and we treat it the same way: a property of the representation, fixed in advance. Mass, shape, robustness. Attribution and extraction read the mass ∥ν∥1 (Definition 2.10); localization reads the shape supp(ν), together with the edit coupling of Assumption 2.3 (Theorem 3.12); detection, the mechanism-blind baseline, reads neither — a key-blind test is priced by the mixture divergence KL(p̄ ∥ pnat ), which a scheme can drive to zero while keeping ∥ν∥1 > 0 (the parity witness), and a keyed test by the per-key divergence or soundness (Θ(1/∆), Θ(λ/h)). Mass and shape are properties of the per-secret kernels alone. Crop-robustness is not: it lives on the coupling footprint R of Assumption 2.3, not on supp(ν). The two witnesses of Section C.8 separate the notions in both directions: the kernel-bend has ν ≡ 0 (nothing recoverable anywhere) yet a window covering the bent coordinate is visibly non-natural; the parity scheme has ν(2) = log 2 yet every window marginal is exactly natural. Theorem 3.12 is accordingly stated on R: mass and shape are read from ν, robustness from the edit coupling. The forensic levels. The forensic uses of a watermark form a ladder of statistical problems. Definition 2.9 (Forensic tasks). Given a length-n sample (and, for keyed detectors, the key), the forensic tasks are: • Level 0 (Detection). Test H0 : X ∼ pnat against H1 : X ∼ pwm , with Type-I/Type-II errors (α, β). (k )
• Level 1 (Attribution). With N users, keys k1 , . . . , kN , U ∼ Unif[N ] and X ∼ pwmU , output Û (X) ∈ [N ], with error Pe := Pr[Û ̸= U ].
8
Watermark Forensics for Generative Models
• Level 2 (Extraction). A payload W ∼ Unif{0, 1}ℓ is fixed at generation; recover Ŵ (X), with error Pr[Ŵ ̸= W ]. • Level 3 (Localization). Identify the marked window, robustly to cropping to any window of size ≥ w (Section 3). We write ndet , natt , next for the least n achieving a fixed target error. The forensic-recovery budget. The single quantity that drives every lower bound is the information a scheme makes recoverable about its secret. Definition 2.10 (Forensic-recovery budget). The forensic-recovery budget of a scheme is Φ(n) := I(S; X) = ∥ν∥1 (Proposition 2.6(i); the mutual information is registry-conditional, per the convention above): the total mass of the information profile. By data processing, any informed extractor Ŝ = g(X, κ) satisfies I(S; Ŝ | κ) ≤ Φ(n), so Φ(n) upper-bounds the recoverable information of every Level-1 / Level-2 procedure simultaneously. We use Unif for the uniform distribution and write a = Θ(b) in the usual two-sided sense, hiding universal constants. The standing convention is that the detection rung of Definition 2.9 is the imported baseline ndet = Θ(1/∆) (Cai et al., 2024; Huang et al., 2023; Li et al., 2025b) (Fact C.1); all of our results concern the rungs above it. Throughout, λ denotes the soundness (security) parameter of distortion-free detection: the keyed detector’s false-positive probability is at most 2−λ ; it is distinct from the per-innocent attribution level δ of Theorem 3.6, which parametrizes a different task.
2.2
Useful tools
The whole paper rests on three textbook facts, which we use as machinery and record once. Fact 2.11 (Data processing and the golden formula; Cover and Thomas, 2006). If S → K → X is a Markov chain then I(S; X) ≤ I(K; X). Moreover, for a key K with X ∼ PX|K and marginal PX , I(K; X) = minQ EK KL PX|K ∥ Q , with the minimum attained at Q = PX ; hence I(K; X) ≤ EK KL PX|K ∥ Q for every reference Q. Fact 2.12 (Fano’s inequality; Cover and Thomas, 2006). For U on a set of size N and any estimator Û = g(X) with error Pe = Pr[Û = ̸ U ], H(U | X) ≤ Hb (Pe ) + Pe log(N − 1), where Hb is binary entropy. Consequently, if U ∼ Unif[N ], Pe ≥ 1 − (I(U ; X) + log 2)/ log N . Fact 2.13 (Stein’s lemma and its ergodic extension; Barron, 1985; Cover and Thomas, 2006). (i) For testing P against Q from n i.i.d. samples at fixed Type-I level α ∈ (0, 1), the smallest Type-II error βn obeys − n1 log βn → KL(P ∥ Q) (Cover and Thomas, 2006). (ii) More generally, if P, Q are the length-n marginals of stationary ergodic laws with positive KL-rate D̄ := limn n1 KL(P ∥ Q) > 0 and an L1 -domination condition on the log-density, then the generalized (relative-entropy) Shannon–McMillan–Breiman theorem (Barron, dP 1985) gives n1 log dQ → D̄ almost surely under P , so the optimal test of P against Q on a single length-n sample has error → 0. A merely diverging total KL on non-i.i.d. laws does not suffice: it is the per-symbol rate D̄, under that domination condition, that must be bounded below. Three further results that we import rather than use as machinery (the Level-0 detection rate, the distortionconstrained fingerprinting converse, and the general-channel coding theorem) are stated, with the non-standard terminology they involve, in Section C.1.
9
Watermark Forensics for Generative Models
Prop 2.6 the information profile ν
Thm 3.1 forensic-recovery budget ∥ν∥1 ≤ n∆
Thm 3.2 detection ̸= attribution
Thm 3.3
Thm 3.6
Prop 3.13
Thm 3.12
two quality models
log N entropy column Θ( h )
rate region
footprint–resolution
mass
Cor 3.4
Cor 3.7
Prop 3.9
footprint ⇒ localization
extraction Θ(ℓ/h)
the collision trap h/r2
shape
Figure 3: The results at a glance. Every result is a reading of the information profile ν. The forensic-recovery
budget (Theorem 3.1) caps its mass ∥ν∥1 = I(S; X); the four results left of the divider concern that mass budget (the detect/attribute separation; the two quality models; the closed entropy column; the shared rate region), while Theorem 3.12 reads its shape. Solid arrows mark a direct dependence, dashed arrows a secondary use (Theorem 3.2 supplies the dichotomy’s lower bound; Theorem 3.3(a) supplies the rate region’s achievability). Corollaries and the collision-trap proposition hang under their parents; the imported and textbook facts each proof draws on are catalogued in Section C.1.
3
Results
One object organizes the results: the information profile ν(t) := I(S; Xt | X<t ) of Proposition 2.6 (Section 2). Attribution and extraction read its mass ∥ν∥1 = I(S; X) = Φ(n); localization reads its shape supp(ν) together with the edit coupling; detection is the mechanism-blind baseline, priced by presence rather than the mass. Everything below is a statement about ν: its mass funds attribution and extraction and sets them against the detection baseline (Theorems 3.1 to 3.3 and 3.6); its shape governs localization (Theorem 3.12); and the levels draw on one shared budget (Proposition 3.13). Full proofs are in Section C, and we are explicit throughout about which step is imported and which is ours.
3.1
The forensic-recovery budget
Each forensic procedure is funded from a single account, the mass ∥ν∥1 = I(S; X) of the profile, and the quality models cap that account in three different norms. The theorem reads off all three. Theorem 3.1 (Forensic-recovery budget). Let a keyed scheme generate X ∈ Σn from a secret S via a key K = K(S), and set Φ(n) := I(S; X) = supg I(S; g(X, κ) | κ) (informed decoders, registry-conditional per the convention of Section 2). Then (a) under Assumption 2.1, Φ(n) ≤ n∆; (b) under Assumption 2.2 with statistical undetectability, Φ(n) ≤ nhn (hn ↓ h for stationary sources; asymptotic statements may use h); and P (c) under the footprint cap E(m) of Section 2, with marked set T (|T | ≤ m), Φ(n) = t∈T ν(t) ≤ m log q (Proposition 2.6(iii)). In particular every Level-1 and Level-2 procedure recovers at most Φ(n) nats about the secret, irrespective of N or ℓ. (K) Proof sketch. S → K → X is Markov, so I(S; X) ≤ I(K; X) ≤ EK KL pwm ∥ Q for every reference Q (golden formula). Take Q = pnat with Assumption 2.1 for (a); for (b), when p̄ = pnat there is no divergence left to spend, so no reference beats the source itself and I(K; X) ≤ H(X) = nhn . For (c), Proposition 2.6(iii) gives ν(t) = 0 off T , and each remaining term is at most H(Xt | X<t ) ≤ log q. This is a pure data-processing bound: it uses only the quality budget, never the embedding/biasing distinction, so it holds for every scheme. In the profile reading, (a), (b), (c) are three faces of one quantity: the L∞ cap, the
10
Watermark Forensics for Generative Models
the secret reaches the carrier only through the key X ∼ pK wm
K = K(S)
S
K
X
secret
key
carrier (n tokens)
Φ(n) = I(S; X)
≤
I(K; X)
data proc.
≤ golden formula
recoverable Φ(n) = I(S; X)
distortion budget n∆
EK KL pK wm ∥ pnat
≤
n∆
quality budget
slack
(one ledger funds attribution and extraction)
Figure 4: The forensic-recovery budget (Theorem 3.1). The secret reaches the carrier only through the key, so
S → K → X is a Markov chain, and three forced steps (data processing, then the golden formula, then the quality budget) bound the recoverable information Φ(n) = I(S; X) by the distortion actually spent, n∆. Nothing about embedding versus biasing enters: it is one ledger, and every nat it holds is shared between attribution and extraction (Proposition 3.13).
P P (K) P entropy ceiling, and the L0 cap on the mass ∥ν∥1 . The chain-rule reading Φ(n) = t ν(t) ≤ EK i di = i di (K) ¯ (here di := EK di = d(i), the key-averaged per-token distortion) is the same budget once more: the recoverable secret cannot exceed the total per-token distortion spent, and a single ledger funds attribution and extraction alike (Figure 4).
3.2
Detection is not attribution
Detection asks whether a mark is present; attribution asks which of N keys placed it. The distinction is not rhetorical—the two tasks spend the mass ∥ν∥1 at different rates—and the theorem below makes the separation quantitative. Theorem 3.2 (Attribution converse and the forensic gap). Under Assumption 2.1, for N ≥ 2 and any attribution rule, n∆ + log 2 Pe ≥ 1 − , (3.1) log N so natt = Ω(log N/∆). Moreover, suppose the scheme is mixture-detectable: the key-unknown test of p̄ against pnat reaches vanishing error by some length nmix det (in the stationary-token model a positive per-token mixture divergence n1 KL(p̄ ∥ pnat ) ≥ c > 0 suffices). Then for all sufficiently large N , on the window nmix det ≤ n < (1 − η) log N/∆ the watermark is detectable with error → 0 while every attribution rule has Pe ≥ η − o(1). Proof sketch. Theorem 3.1(a) gives I(U ; X) ≤ n∆; Fano, H(U | X) ≤ log 2 + Pe log N , with H(U | X) = log N − I(U ; X), gives (3.1). On the window n ≥ nmix det the scheme is mixture-detectable (key-unknown detection error → 0; in the stationary-token model a positive per-token mixture divergence n1 KL(p̄ ∥ pnat ) ≥ c > 0 suffices, by the relative-entropy ergodic theorem), while n∆ < (1 − η) log N forces Pe ≥ η − o(1). In one sentence: detection is a fixed two-point test, p̄ against pnat , whose cost does not grow with N ; attribution must extract log N nats of identity, and the budget funding it accrues only at rate ∆ per token, so it cannot begin until n∆ ≳ log N . The window between is where the watermark is loud but anonymous. We are careful about credit. The converse (3.1) is an elementary single-user Fano bound on I(U ; X) under the budget (derived from scratch in Section C); it is the collusion-free special case of the distortion-constrained fingerprinting converse of Moulin (2008) and Somekh-Baruch and Merhav (2005), whose hard content (the worst-case collusion channel) we do not use. We claim no novelty for it. Note also that the converse consumes ¯ ≤ ∆, not the sup-form; the sup-form is only the avg-form cap of Section 2 (Fano on ∥ν∥1 needs maxt d(t) 11
Watermark Forensics for Generative Models
what the achievability constructions certify). What we add is the explicit co-located regime: a single biasing scheme, at a single length, detectable yet information-theoretically unattributable. The mixture-detectability hypothesis is genuine, not free: the parity scheme on {0, 1}2 (under key k0 , (x1 , x2 ) is uniform on {00, 11}; under k1 , uniform on {01, 10}; each has KL = log 2 within budget, yet the mixture is uniform on {0, 1}2 = pnat exactly) is detectable only with the key, which itself is informative; for distortion-free schemes “detect but not attribute” is automatic, not a separation. The clean takeaway survives at every N : attribution costs Θ(log N ) more tokens than detection (Section 3.6). The razor-thin endpoint, Pe → 1 at near-perfect detection, is the asymptotic-in-N sharpening of that same gap, not a separate phenomenon.
3.3
Two quality models, and the localization map
The separation above caps every bounded-distortion scheme, embedding included; it does not by itself separate the mechanisms. The mechanism enters through which quality model a scheme can use: the two norm caps of Section 2 on the same profile ν. Two orthogonal axes are in play (Figure 14 in Section 4): the footprint, which this subsection moves along (does the cost decouple from ∆?), and the readout resolution of Theorem 3.12 (can the mark be named in place?). The distributional cap B(∆) (the sup-form per-secret cap: every kernel within ∆ of natural at every prefix, hence ν(t) ≤ ∆ everywhere, an L∞ cap) keeps the mark subtle on every token; the footprint cap E(m) (per-secret kernels unmarked off a set T with |T | ≤ m, hence ν = 0 off T , an L0 cap) confines it to ≤ m coordinates, with no per-token bound. The two are definitionally incomparable: different norms on one object. Attribution succeeds once the cumulative profile reaches ν([n]) ≥ (1 − o(1)) log N (Fano on the mass), so natt is a first-passage time of ν. The two caps force two extremal shapes, and the dichotomy is nothing but their two first-passage lengths: a thin-and-wide ν ≡ ∆ reaches log N only at n ∼ log N/∆, while a tall-and-narrow ν = (log q) 1T reaches it already at n ∼ log N/ log q, with no ∆ in sight. The theorem makes this precise. Theorem 3.3 (Two quality models). For attribution among N users and ℓ-bit extraction: (a) (Distributional cap couples.) Every scheme in B(∆) has natt = Ω(log N/∆) and next = Ω(ℓ/∆). These are achieved, with natt = Θ(log N/∆) and next = Θ(ℓ/∆), when pnat is memoryless, or regular (pnat (· | past) ≥ p0 > 0) and strongly mixing; for general q-ary pnat the matching upper bound is conjectural. (b) (Footprint cap decouples.) There is a scheme in E(m) achieving natt = Θ(log N/ log q), next = Θ(ℓ/ log q) at m = Θ(log N/ log q), with no dependence on any per-token cap. In a carrier of length P ¯ n ≫ natt the footprint fraction m/n → 0 (and the aggregate distortion n−1 t d(t) → 0 when pnat is regular, pnat (· | past) ≥ p0 > 0): imperceptibility comes from the vanishing footprint, not a per-token bound. The localization map makes E(m) available: a scheme in E(m) has localization map T (Corollary 3.4), and a biasing scheme (no localization map) cannot lie in E(m) for m = o(n), so under a quality constraint it is confined to B(∆) and pays the coupled cost (a). (k) Proof sketch. (a) Lower bound: B(∆) ⇒ KL pwm ∥ pnat ≤ n∆, so Theorem 3.2 applies (unconditionally). Upper bound by a conditional tilting code: tilt the natural conditional pnat (· | X<i ) by ∆ when cu [i] = 1; the KL chain rule makes the total distortion exactly (#ones)∆ ≤ n∆ for any autoregressive pnat (the construction controls KL). Fidelity is spent in KL, but the bits a decoder reads back are measured by the symmetric Jensen–Shannon information E JSD = Θ(∆), the capacity of the per-position channel (C ≈ ∆/4 in the binary witness); under the regularity/mixing hypothesis the per-position information stays ≥ c(p0 )∆ uniformly and the information density concentrates (Verdú–Han), giving reliable decoding at n = Θ(log N/∆) above a finite-blocklength floor n = Ω(1/∆). (b) The stamp: write the user’s base-q digits into the first m = ⌈log N/ log q⌉ tokens, T = {1, . . . , m}; readback is exact, the region is Θ(log N/ log q), and footprint m/n → 0 gives the fidelity. Three clarifications keep the statement honest. First, the asymmetry is not definitional: (a)’s lower bound rides on the forensic-recovery budget (Theorem 3.1), not on “no localization map.” Second, this is not an iff
12
Watermark Forensics for Generative Models
pays the B(∆) cost
pays the E(m) cost
∆-coupled, Ω(log N/∆)
∆-free, Θ(log N/ log q)
small footprint |T | = o(n)
possible
the stamp ✓
a small mark that still obeys B(∆)
footprint decouples the cost
(has a map)
pays Ω(log N/∆) (Corollary 3.4)
Θ(log N/ log q), ∆-free
full support |T | = Ω(n)
biasing, forced
impossible
no footprint ⇒ confined to B(∆)
no small footprint
pays Ω(log N/∆)
⇒ no E(m) to use
(no map)
Figure 5: The bridge is one-directional (Theorem 3.3, Corollary 3.4). Crossing “footprint” with “quality model used”
leaves exactly one cheap, ∆-free cell, the stamp, and it needs both a small footprint and actually using the footprint model E(m). A small footprint (a localization map) enables the cheap model but does not decide the cost: a small mark that still obeys the per-token cap B(∆) stays ∆-coupled (top-left). A full-support biasing scheme has no small footprint, so it is confined to B(∆) (bottom-left); the ∆-free corner is simply unreachable for it (bottom-right). This is a one-way bridge, not an “embedding ⇔ ∆-free” equivalence.
phase boundary. A scheme admitting a localization map that also obeys B(∆) still needs m ≥ log N/∆ readable coordinates and remains ∆-coupled; ∆-freeness comes from the footprint model, which the localization map enables but does not force. Third, the witness in (b) is a deliberately trivial cleartext digit-stamp: it is not robust to a single edit and is imperceptible only through the m/n → 0 footprint, nothing like the semantic, edit-robust localization of deployed embedding watermarks (Arabi et al., 2025; Zhang et al., 2024). A ∆-free achievability for any operational (edit-robust, imperceptible) watermark remains open; (b) establishes only that the information-theoretic obstruction is absent. The honest statement is a one-directional bridge (Figure 5): Corollary 3.4 (Footprint forces localization). Let the scheme lie in E(m) with marked set T , |T | ≤ m. Then ν = 0 off T , so I(S; X) = ν(T ); the likelihood’s dependence on s factors through the pairs ((x<t , xt ))t∈T , so X≤max T is a sufficient statistic for S; and when T is a prefix (as for the stamp) this is the exact Markov chain S → XT → X. Thus Lk := T localizes the mark. The converse fails: a scheme in E(m) that also ¯ ≤ ∆ (which suffices, since ν(t) ≤ d(t); ¯ obeys the avg-form cap maxt d(t) the sup-form implies it) still needs m ≥ (1 − o(1)) log N/∆ marked coordinates — localization does not buy ∆-freeness.
3.4
Closing the entropy column
In the distortion-free regime (Assumption 2.2) the binding resource is the entropy rate h, and Theorem 3.1(b) gives the Fano converse natt = Ω(log N/h). Whether the rate is attainable (whether a p̄ = pnat scheme can actually attribute at n = O(log N/h)) is the achievability question left open by that converse-only ledger. It closes, at full stationary-ergodic generality, by a decoder that thresholds the realized surprisal (Figure 6), giving, to our knowledge, the first tight h-rate for multi-user attribution. Definition 3.5 (Witness scheme; threshold decoder). Give the N users i.i.d. keys, each an i.i.d. Unif[0, 1] sequence, and mark by inverse-CDF sampling, Xt = Fp−1 (ku (t)), so that X ∼ pnat exactly (kernel-level nat (·|X<t ) distortion-free, Assumption 2.2; exponential-minimum sampling after Kuditipudi et al., 2023). The decoder knows pnat and the realized key set {k1 , . . . , kN }. With τ := log(N/δ) and ı(X) := − log pnat (X), the realized surprisal, the threshold decoder returns a key consistent with X when ı(X) > τ (any one, if several are consistent) and declares failure when ı(X) ≤ τ . The theorem states the rate, then gives in three parts the exact per-innocent guarantee, the completeness threshold, and the matching converse that together make it two-sided.
13
Watermark Forensics for Generative Models
Theorem 3.6 (Distortion-free attribution is Θ(log N/h)). Let pnat be stationary ergodic with entropy rate h > 0 (no mixing hypothesis), marked and decoded as in Definition 3.5. Fix a per-innocent false-positive level δ ∈ (0, 12 ) and let N → ∞ (optionally δ → 0 with log(1/δ) = o(log N ) for the (1 + o(1)) form). Then attribution among N users costs natt = Θ(log N/h) (achievability alone holding for all δ ∈ (0, 1)), sharpening to (1 + o(1)) log N/h, and: (i) (False positives; exact, non-asymptotic.) For every n and arbitrary pnat (no ergodicity used): for the deterministic sampler of Definition 3.5, a fixed innocent v is the key returned only with probability Pr[Û = v] ≤ e−τ = δ/N , pointwise in the realized innocent keys (the probability is over the true text X ∼ pnat ); for randomized distortion-free kernels the same bound holds averaged over the key draw. (ii) (Completeness.) Pr[ı(X) > τ ] → 1 whenever n ≥ (1+α)τ /h for any fixed α > 0 (Shannon–McMillan– Breiman; here h is the entropy rate). (iii) (The rate, two-sided.) Achievability: the average error is ≤ δ + o(1) once n ≥ (1 + α)(log N + log(1/δ))/h, for every fixed α > 0 (N large). Converse: for i.i.d. keys, every attribution rule with error (n) ≤ 2δ needs n ≥ (1 − 2δ) log N/hn − O(1/h), with hn := H(pnat )/n (= (1 + o(1))h) — conditional Fano discharged by a mixture-entropy step (Section C.6). Thus natt = Θ(log N/h) for fixed δ ∈ (0, 21 ), log N natt = (1 + o(1)) as δ → 0, log(1/δ) = o(log N ). h For a fixed deployed key set the converse instead holds under a mixture-entropy hypothesis on the realized keys (as N → ∞; automatic when pnat is the maximum-entropy law), detailed in Section C.6. Corollary 3.7 (Payload extraction). Index N = 2ℓ keys by the payload W ∼ Unif{0, 1}ℓ . Under the hypotheses of Theorem 3.6, next = Θ(ℓ/h) for fixed δ, and next = (1 + o(1)) ℓ log 2/h as δ → 0 with log(1/δ) = o(ℓ). Proof sketch. (i) is a two-line computation, the deterministic case first (matching the proof order in the appendix): fix the realized key set; on {ı(X) > τ } the single string an innocent key determines has pnat mass < e−τ , so Pr[Û = v] ≤ e−τ pointwise. For randomized distortion-free kernels, average over the key Q draw: given X, an independent wrong key is consistent with probability t pnat (Xt | X<t ) = e−ı(X) , so P Pr[Û = v] ≤ E[e−ı 1{ı > τ }] = X: pnat (X)<e−τ pnat (X)2 ≤ e−τ . (ii) is Shannon–McMillan–Breiman: ı(X)/n → h a.s. and τ /n ≤ h/(1 + α) < h. (iii) combines the two with a union bound over the N − 1 innocents; the converse is conditional Fano plus the Jensen step Eκ [H(p̂κ )] ≤ H(Eκ [p̂κ ]) = nhn , where κ = {k1 , . . . , kN } is the realized P (k ) key set and p̂κ := N1 v pwmv the induced key mixture. Full proof in Section C.6. Remark 3.8 (Tightness and necessity of the hypotheses). Both structural hypotheses are necessary, not technical. Ergodicity: take the stationary non-ergodic mixture that emits, with probability 12 each, the all-zero stream or i.i.d. fair bits. Its process entropy rate is 12 log 2 > 0, yet on the constant component the realized surprisal never exceeds log 2 < τ , so every attribution rule (informed or not) errs with probability ≥ 12 − o(1) at every length: the rate log N/h fails when h is read as the process rate. What survives for stationary sources is the componentwise statement: part (i) holds verbatim, completeness holds within each ergodic component, and as δ → 0 the rate becomes (1 + o(1)) log N/h∗ with h∗ the essential infimum of the components’ entropy rates (elementary for finite mixtures; for fixed δ the constant improves to a δ-quantile of the component rates, whose sharp form we leave open). Ergodicity is exactly the condition collapsing h∗ , the quantile, and the process rate to one number. The key registry: without the indexed assignment v 7→ kv the users are exchangeable given X, indeed X is independent of U , so every rule succeeds with probability exactly 1/N ; attribution without the registry is attribution without the identities. The converse, by contrast, already bounds the informed decoder.
14
Watermark Forensics for Generative Models
An innocent key kv generates one fixed string X(kv ). It frames v only if X(kv ) = X and ı(X) > τ :
ı(X)/n → h
τ /n = log(N/δ)/n ı(X) > τ
Pr[Û =v] = pnat X(kv )
h
= e
−ı
< e
−τ
=
δ . N
δ/N = e−τ innocent’s mass e−ı (a sliver)
n⋆ = τ /h
n
pointwise, exact, every n, every source
(ii) completeness (rate = h)
(i) soundness (FP = δ/N ) Figure 6: The surprisal threshold does both jobs (Theorem 3.6). The decoder accepts a consistent key only when the
realized surprisal ı(X) = − log pnat (X) exceeds τ = log(N/δ), and that single threshold is forced, not tuned. (ii) The marked text is itself pnat -typical, so ı(X)/n → h (Shannon–McMillan–Breiman) and clears τ once n ≥ τ /h: this is why the rate is the entropy h. (i) An innocent key produces one fixed string, which coincides with X only with pnat -mass e−ı < e−τ = δ/N : the per-innocent guarantee is exact and pointwise. To frame no innocent above δ/N one must reject every candidate below τ , and completeness then only asks that the true text clear the same bar.
Proposition 3.9 (The collision trap). Consider the witness scheme and threshold decoder of Definition 3.5 on an i.i.d. source, and say a key is consistent with X if it generates X token for token. Then: P (i) the expected number of falsely consistent keys is exactly (N − 1)e−nr2 , where r2 := − log x pnat (x)2 is the Rényi-2 rate, so the expected list clears (falls below one) only at n ≥ log(N − 1)/r2 ; (ii) yet the surprisal-threshold decoder keeps per-innocent false positives ≤ δ/N at every length, and its average error is ≤ δ + o(1) once n ≥ (1 + α) log(N/δ)/h, for any fixed α > 0; (iii) r2 ≤ h always, with equality iff pnat is uniform on its support, so the consistency count prescribes h/r2 times more tokens than the decision requires, a factor unbounded as the source skews. Proof. (i) is the collision identity of Lemma C.4 specialized to the deterministic witness and an i.i.d. source (Section C.7); (ii) is Theorem 3.6(i)–(iii); (iii) is monotonicity of Rényi entropy in its order, with equality exactly on support-uniform sources (Section B); for pnat = Ber(p), h/r2 → ∞ as p → 0. The trap, in words. Consistency (alignment) is the rule deployed detectors actually use: answer with any key consistent with the text. Its natural analysis drives the expected list (N − 1)e−nr2 below a constant and so predicts the rate log N/r2 — the wrong rate. Collision entropy prices the candidate list; Shannon entropy prices the decision: in the window log N/h ≤ n ≪ log N/r2 the list is exponentially large, yet the surprisal threshold has already separated the true key within it (Figure 7). Only the second rate is a sample complexity. The seeded numerics certify the trap: at the operating point the consistency-only decoder’s false-positive rate overshoots the δ/N target by orders of magnitude (Section 3.6). A tie-abstaining variant of the consistency rule has zero false positives in the closed-world model U ∈ [N ] but loses the guarantee on out-of-set text (Section C.7); it is not used by the headline. Whether a genuine r2 cost reappears for edit-robust decoders is taken up in Section 6. Example 3.10 (A skewed coin makes the gap concrete). Take pnat = Ber(0.1) i.i.d. (the source of Section 3.6). Its entropy rate is h = Hb (0.1) = 0.325 nats, while its Rényi-2 rate is r2 = − log(0.12 + 0.92 ) = 0.198 nats, so h/r2 ≈ 1.64. To attribute among N = 232 users, the surprisal threshold succeeds at n ≈ log N/h ≈ 68 tokens (the log(1/δ) term, about 9 tokens here, is lower-order in N ), while the consistency list clears only at n ≈ log N/r2 ≈ 112; their ratio is exactly h/r2 ≈ 1.64. The gap grows without bound as the coin skews (h/r2 → ∞ as p → 0): the trap is not a constant-factor nuisance. Credit, again. The false-positive mechanism in (i) is the folklore likelihood-ratio Markov bound, for which we claim no novelty (Section C.6). What is new is the closed column: the matching achievability at full stationaryergodic generality (SMB only), with an exact non-asymptotic false-positive side, and its forensic reading — the entropy mass of Theorem 3.1(b) is operational, not merely a ceiling. The distortion-free sub-column of Table 1,
15
Watermark Forensics for Generative Models
# consistent keys (log scale)
attribution already succeeds
the naive count “waits” for here
(N −1) e−nr2 keys still “consistent”
collision entropy r2 prices the candidate list;
≈ e n(h−r2 ) consistent
list size = 1
the trap sample length n log N log N h r2 Shannon entropy h prices the decision (and r2 < h, gap h/r2 unbounded)
Figure 7: The collision trap (Proposition 3.9). The obvious decoder answers with any key consistent with the text; its
list of falsely consistent innocents, (N − 1)e−nr2 , clears only at n = log N/r2 . So a count-based analysis predicts that rate. But the surprisal threshold decides already at n = log N/h, deep inside the window where the list is still exponentially large (≈ e n(h−r2 ) ): it singles out the true key within the list rather than waiting for the list to shrink. The Rényi-2 rate r2 prices the candidate list; the Shannon rate h prices the decision, and r2 < h makes the gap h/r2 unbounded.
a one-sided converse ledger in the first version of this paper, is now two-sided at Levels 1 and 2. The closest cryptographic tracing of many adaptive users gives no tight information-theoretic h-rate (Cohen et al., 2025); Christ–Gunn-style undetectable schemes are computational and governed by seed entropy (scope note after Theorem 3.1 in Section C). The witness decoder is exact-alignment, hence not edit-robust; a ∆-free, edit-robust attribution rate remains open (Section 6). Remark 3.11 (Where the columns meet). The two extremal columns of Table 1 touch at exactly one source. On a full-alphabet-uniform i.i.d. source, h = log q, so the closed entropy column gives (1 + o(1)) log N/ log q: the invisible distortion-free witness then costs no more than the cleartext digit-stamp of Theorem 3.3(b), and only there, since log N/h ≥ log N/ log q always, with equality iff pnat = Unif(Σ); the witness moreover saturates Theorem 3.1(b) with equality (I(K; X) = H(X) = nhn for the deterministic sampler), which is why the column closes. Separately, the collision trap vanishes exactly on support-uniform sources (r2 = h iff pnat is uniform on its support, Proposition 3.9(iii)): the overcharge h/r2 is a price of skew. The two degeneracies are distinct: a source uniform on a strict sub-alphabet kills the trap but not the gap between the columns.
3.5
Level 3, and a shared budget
The top rung, localization, is where the framework does work the budget alone does not predict. A watermark is localizing if it can name which sub-region carries the mark, and the demanding version asks this to survive cropping. Model a crop adversary that deletes all but a contiguous window W of length w; a scheme is w-crop-robust if the detector succeeds on xW for every offset. We assume the scheme is r-local / edit-based (Assumption 2.3): the marked carrier agrees with an unmarked one outside an r-neighbourhood R+ of the carrier footprint R (the support of the edit coupling; for a scheme in E(m) over a factorizing source one may take R = T ), the post-hoc regime of image, audio, and patch watermarks, where Level-3 localization is actually studied. Robustness is the one property that is not a functional of ν alone: mass and shape live in ν; crop-robustness additionally needs the edit coupling on R, which is why Assumption 2.3 is stated on the carrier.
16
Watermark Forensics for Generative Models
Table 1: The forensic ladder. Symbols: ∆ per-token KL budget; h per-token entropy rate; λ detection soundness (FP ≤ 2−λ );
q = |Σ| alphabet size; m footprint; w crop window; N users; ℓ payload bits. In the distributional column the lower bounds (Ω) are unconditional; the matching upper bounds (Θ, shown in brackets) hold for regular, strongly-mixing pnat (Theorem 3.3) and are conjectural for general q-ary pnat . The embedding column is two-sided (Θ, exact construction); the distortion-free (h) sub-column is now two-sided at Levels 1–2 (Theorem 3.6: stationary-ergodic source, i.i.d. keys, decoder knowing pnat and the key set). The bounded Level-0 rate Θ(1/∆) is the imported baseline (Cai et al., 2024; Huang et al., 2023; Li et al., 2025b); the distortion-free Level-0 rate Θ(λ/h) (with λ the entropy needed for 2−λ false-positive security) is from Christ et al. (2024); the bounded-regime attribution converse is the single-user Fano specialization of Moulin (2008); Somekh-Baruch and Merhav (2005). Level 3 (crop-robust localization to resolution w, Theorem 3.12) turns on a different axis, readout resolution: it forces full support, so the small-footprint embedding column cannot reach it. Level
Task
Distributional B(∆) (h: distortion-free)
Footprint E(m) (embedding)
0 1 2 3
Detection Attribution (N ) Extraction (ℓ) Localization (res. w)
Θ(1/∆) / Θ(λ/h) Ω(log N/∆) [Θ if mixing] / Θ(log N/h) Ω(ℓ/∆) [Θ if mixing] / Θ(ℓ/h) needs full support, w∆ ≥ log(n/w)
same (baseline) Θ(log N/ log q), ∆-free Θ(ℓ/ log q), ∆-free coarse w = ω(1) only
Theorem 3.12 (Footprint–resolution uncertainty). Under Assumption 2.3, any w-crop-robust scheme has dilated support R+ meeting every length-w window; since |R+ | ≤ (2r + 1)|R|, its carrier footprint |R| obeys |R| w ≥
n−w+1 , 2r + 1
i.e.
|R| w = Ω(n) (r = O(1)),
the Ω(n) reading trivial for w > n/2 (a nonempty R already gives |R| w > n/2). For a scheme in E(m) whose natural law factorizes across positions (in particular i.i.d.; the post-hoc regime of Assumption 2.3) one may take R = T , so |R| ≤ m and the bound reads m w = Ω(n). Consequently (i) a small-footprint embedding scheme (m = o(n), hence |R| = o(n)) is crop-robust only at coarse resolution w = ω(1), and (ii) constant-resolution crop-robustness forces |R| = Ω(n), i.e. full support, that is, biasing. Moreover (iii) under Assumption 2.1, for a natural law that factorizes across the length-w blocks (in particular i.i.d., and the whitened regime of the post-hoc schemes Assumption 2.3 targets), w-crop-robust localization (naming the window among the Θ(n/w) blocks from xW alone) requires w∆ ≥ (1 − o(1)) log(n/w). Proof sketch. If a length-w window W misses R+ , then by the coupling of Assumption 2.3 xW = x′W ∼ pnat , so a detector seeing only xW tests pnat against pnat and cannot beat chance, a contradiction. Hence R+ meets every length-w window; there are n − w + 1 such windows and one element pierces at most w of them, so |R+ | ≥ (n − w + 1)/w; with |R+ | ≤ (2r + 1)|R| this gives |R| w = Ω(n), and |R| ≤ m for E(m). For (iii), partition [n] into Nw = ⌊n/w⌋ disjoint length-w blocks; naming the surviving block is attribution among the blocks (Theorem 3.2 with the Nw blocks as users), so by Fano I(J; xWJ ) ≥ (1−o(1)) log Nw for J ∼ Unif[Nw ]. When pnat P P factorizes across the blocks, the golden formula bounds I(J; xWJ ) ≤ EJ i∈WJ di = N1w i di ≤ n∆/Nw = w∆, P using only the global budget i di ≤ n∆ (no per-token cap); hence w∆ ≥ (1 − o(1)) log(n/w). For correlated pnat the cropped block marginalizes its prefix and this accounting can fail; the relation persists in our numerical search, but a tight general proof is left open. So Level 3 turns on a different axis than the footprint (Figure 8): a small-footprint embedding scheme cannot be crop-robust at fine resolution at all (a single splice removes its mark), whereas crop-robust fine localization forces full support |R| = Ω(n/w). A scheme localizes when it reads a full-support mark at fine per-region resolution and self-locates at window budget w ≥ log(n/w)/∆. This is the structural form of the empirical split (fine-readout schemes localize; global-readout schemes do not), made precise in Section 4. Finally, the levels are not independent obligations but draws on one account. Proposition 3.13 (Forensic rate region). Under Assumption 2.1 and in the regime n∆ → ∞, with Ratt = log N and Rext = ℓ log 2:
17
Watermark Forensics for Generative Models
marked R (dilated R+ , width 2r+1) [1, . . . , n]
carrier a crop window of length w falls in a gap: xW = x′W ∼ pnat (unmarked) ⇒ detector at chance ×
So every length-w window must meet R+ ⇒ consecutive marks lie ≤ w apart ⇒ |R+ | ≥
hence |R| w = Ω(n)
n , w+1
few marks ⇒ only coarse resolution; fine resolution ⇒ full support (biasing).
Figure 8: Why a small footprint cannot localize at fine resolution (Theorem 3.12). Under the edit coupling (Assumption 2.3), a crop window that misses the dilated footprint R+ sees text distributed exactly as pnat , so a detector reading only that window tests pnat against pnat and cannot beat chance. Every length-w window must therefore meet R+ , which forces the marks no more than w apart: |R| w = Ω(n). Few marks buy only coarse resolution; fine resolution forces full support, that is, biasing.
(a) (Converse.) vanishing-error attribution and extraction force Ratt + Rext ≤ (1 + o(1)) n∆; (b) (Achievability.) for regular, strongly-mixing pnat (general q-ary conjectural, inheriting Theorem 3.3(a)), every pair with Ratt + Rext ≤ (1 − o(1)) nC is achieved by one multiplexed conditional tilting code, where C = Θ(∆) is the per-token channel capacity. Thus the achievable region is a slope-−1 simplex whose boundary is order-tight, Θ(n∆): it lies between nC and n∆, which agree up to the capacity constant (C ≈ ∆/4 in the binary witness of Section 3.6). The corners carry no extra loss. Proof sketch. With S = (U, W ), the chain rule gives I(U, W ; X) = I(U ; X) + I(W ; X | U ) ≤ n∆ (Theorem 3.1); Fano on U and conditional Fano on W | U make the two terms ≥ (1 − o(1))Ratt and ≥ (1 − o(1))Rext , giving (a). For (b), concatenate the two messages into one codeword and apply Theorem 3.3(a) at rate nC. So it is not just that attribution and extraction are each Ω(·/∆), but that a biasing watermark cannot be cheap at both at once: every nat spent naming the user is a nat denied to the payload (Figure 9). The embedding analogue is the ∆-free simplex Ratt + Rext ≤ m log q, now a theorem (Theorem 3.1(c), the L0 face of the mass cap), and there, uniquely, the bound is constant-exact (the zero-error stamp readback meets it).
3.6
Numerical illustration
We instantiate the tilting code over a binary alphabet (p+ = Ber( 12 + s), pnat = Ber( 12 )) and measure detection power and attribution accuracy by seeded Monte Carlo (Figure 10). Three findings confirm the theory. (i) The converse (3.1) is never violated. (ii) The attribution threshold scales as log N/C, where C = I(b; X) = Θ(∆) is the channel capacity (empirically C ≈ ∆/4 at s = 0.08, so the operative constant is the capacity, not ∆ itself), and grows by exactly the factor log 4096/ log 64 = 2 as N goes from 64 to 4096, while the detection threshold is flat in N , so the ratio is Θ(log N ) (Figure 10b). (iii) At N = 4096, detection power is already 0.99 while attribution accuracy is still 0.28 at a common length (n = 1400; Figure 10a), and detection saturates to 1.00 several hundred tokens before attribution leaves chance (it reaches 0.55 only at n = 2200): the finite-N form of the gap. The embedding stamp, by contrast, attributes among all 4096 users from n = 12 tokens, where the biasing scheme is at chance. The first two findings quantify Theorem 3.2; the third quantifies Theorem 3.3. Two further seeded experiments exercise Theorem 3.6 directly. The first runs the threshold decoder on an i.i.d. binary source (h ≈ 0.325, r2 ≈ 0.198) at δ = 0.05 and N up to 232 : the per-innocent false-positive rate satisfies FP · N/δ ≤ 0.11 at every tested length, including the boundary n = τ /h, while the consistency-only decoder (no surprisal threshold) overshoots the δ/N target by one to four orders of magnitude — the collision trap of Proposition 3.9, priced by e−nr2 , not by the decision rate. A companion run tracks the consistency decoder’s threshold drift (seeded) and supports the abstain-on-tie completeness observation of Proposition 3.9. The second
18
Watermark Forensics for Generative Models
Rext
Rext
=
n∆
m lo g
nC
q
the stamp zero error Ratt
Ratt
(a) biasing B(∆)
(b) embedding E(m)
soft frontier, order-tight Θ(n∆)
sharp frontier, constant-exact
one mass split two ways: every nat naming the user is a nat denied the payload Figure 9: Two rate regions, one shape (Proposition 3.13). Attribution and extraction draw on the single budget of Theorem 3.1, so their rates trade off along a slope-(−1) frontier. (a) Under the per-token cap B(∆) the frontier is soft, order-tight Θ(n∆), lying between the achievable nC and the converse n∆ (C ≈ ∆/4 in the binary witness of Section 3.6). (b) Under the footprint cap E(m) it is sharp and constant-exact, Ratt + Rext = m log q, met with equality and zero error by the stamp. The same simplex, with a soft boundary on one side and a hard one on the other.
checks the Jensen step, Eκ [H(p̂κ )] ≤ nhn , at all tested (n, N ) pairs, including N > enh (all pass). All runs are seeded and reproducible.
3.7
Confirmation on deployed language models
The theory makes a falsifiable numerical prediction: the consistency rule’s overcharge is the entropy ratio h/r2 , a quantity fixed by the source and by nothing about the watermark. On natural language it should be a stable constant near 1.6. The binary source of Section 3.6 isolates the mechanism on a distribution we control; we now close the loop, measuring h/r2 and the detection/attribution thresholds where they are meant to bite: on real autoregressive language models, and on the watermarks practitioners deploy. These are illustrations of the theory’s operational content, not new theory — the lower bounds remain the theorems, unfalsifiable by simulation, and what follows measures their inputs (the rates h, r2 and the detection/attribution thresholds) on real systems; the exact false-positive guarantee δ/N itself was exercised in the seeded numerics of Section 3.6. All experiments are seeded and reproducible. The collision trap on a shipped distortion-free scheme. Theorem 3.6 and its trap (Proposition 3.9) live in the distortion-free regime, whose deployable instance is the exponential-minimum-sampling (Gumbelmax) watermark of Aaronson (2022) and Kuditipudi et al. (2023): a key-seeded Gumbel perturbs the logits, (κ) xt = arg maxi log pnat (i | x<t ) + gt,i , so marginally xt ∼ pnat . We run it on GPT-2 (Radford et al., 2019). Two properties make the entropy column apply, and we verify rather than assume both. (i) Distortion-free: the marked text has the same Shannon and Rényi-2 rates as unmarked sampling (h = 3.81 vs. 3.76, r2 = 2.36 vs. 2.33 nats/token), so the mark spends no distortion. (ii) The collision is real: at a fixed context, 8000 independent keys reproduce pnat (its 20 most likely tokens to within 0.006), so an innocent key emits token v with probability exactly pnat (v) — so the per-token collision law of Proposition 3.9 is a property of the construction at a fixed context, not a modelling assumption (r2 here is the empirical Rényi-2 rate, and the (N − 1)e−nr2 count is its per-token extrapolation). The guarantee lengths then separate as predicted (Figure 11): implicating no innocent above δ/N costs log(N/δ)/r2 tokens under the consistency rule but only log(N/δ)/h under surprisal thresholding, a ratio h/r2 = 1.61 on GPT-2. This is the trap on a scheme one can ship, and the deterministic witness of Section 3.6 recovers the very same constant.
19
Watermark Forensics for Generative Models
(a) The forensic gap (N = 4096)
(b) Attribution (logN), detection flat
1.0
30 threshold n
success rate
0.8 0.6 0.4 detection power attribution accuracy chance 1/N can detect, cannot attribute
0.2 0.0
attribution natt detection ndet theory C logN
0
5
10 15 20 25 sequence budget n
30
25 20 15 10
35
4
5
6 logN
7
8
Figure 10: Seeded Monte-Carlo confirmation of the separation (binary tilting code, s = 0.08, so the per-token budget is ∆ = KL(pwm ∥ pnat ) /n and the channel capacity C = I(b; X) ≈ ∆/4). (a) At N = 4096, detection power saturates to 1 while attribution accuracy is still near chance over a wide window (shaded): one can detect long before one can attribute. (b) The attribution threshold grows linearly in log N (slope matching ∆/C, dashed), while the detection threshold is flat in N ; their ratio is Θ(log N ).
Detection is not attribution, on the deployed green-list. The green-list of Kirchenbauer et al. (2023) is the extremal biasing profile (the B(∆) column of Theorem 3.3): a context-keyed split greens a fraction γ = 14 of the vocabulary and adds a fixed logit bias (here 2.0). On GPT-2 the realized green fraction is 0.62 under the true key against 0.25 under any innocent key. Figure 12 exhibits Theorem 3.2 in finite-N form: detection power saturates by n ≈ 28 tokens independently of N , whereas the attribution length (here the 50%-accuracy crossing) grows linearly in log N (+2.3 tokens per doubling, from 16 to 61 tokens as N runs 28 to 228 ). Between the two lies a window in which the passage is detectable yet unattributable. Unlike the EMS scheme above, the green-list shifts the entropy: the two quality models of Definition 2.4, the same separation read off either column. The overcharge is a property of language, not of one model. The constant h/r2 is the only modeldependent quantity in the trap, so we measure it across families. On GPT-2, Pythia-410M (Biderman et al., 2023), and Qwen2.5-0.5B (Qwen Team, 2024) — three pretraining corpora and tokenizers, vocabularies from 50k to 152k — the absolute rates fall as the models sharpen (h from 3.80 to 2.34 nats/token), but the overcharge is stable: h/r2 = 1.61, 1.60, 1.57 (Figure 13). The collision trap reflects the gap between the Shannon and Rényi-2 rates of natural language, not an artifact of any one model.
4
The framework applied: a taxonomy of deployed watermarks
The classification of Definition 2.4 is decided by one measurable quantity: the per-secret footprint T (the reading set: the positions on which the per-secret kernels are marked, Corollary 3.4), read in the basis the extractor works in. The per-secret reading is not optional: the key-averaged support would misclassify every distortion-free scheme as E(0), since averaging over the key can erase a mark present under every individual key (parity witness, Section C.8). Table 2 evaluates the criterion on twenty-one representative schemes (the twenty deployed watermarks and the theoretical digit-stamp witness), holding it fixed (so a scheme is embedding only if its per-secret kernels truly mark o(n) coordinates, not merely if its secret is readable from a sub-carrier); Section D works through each scheme individually. Two axes turn out to matter, and they are orthogonal: the footprint T , which governs the embedding/biasing split and the ∆-free decoupling of Theorem 3.3; and the readout resolution, whether the mark is decoded globally or per-region, which governs Level 3. Three patterns follow. 1. Almost every deployed watermark is biasing, and the ∆-free class is nearly empty. Applied consistently, the footprint criterion puts not only the LLM schemes but also the neural image and audio
20
Watermark Forensics for Generative Models
the trap on EMS: overcharge 1.61 ×
EMS distortion-free: marked rates = unmarked
rate (nats / token)
3 2 1 0
EMS Shannon h EMS Renyi-2 r2
0
20
40 60 tokens n
plain h (unmarked) plain r2 (unmarked)
80
tokens to guarantee error
10
4
8 6 4 2
100
consistency nA logN/r2 surprisal nB logN/h
10
15 20 25 log2 N (number of users)
30
Figure 11: The collision trap on the deployed EMS (Gumbel-max) distortion-free watermark, GPT-2. (a) The marked text’s Shannon (h) and Rényi-2 (r2 ) rates coincide with unmarked sampling (dotted): the watermark is distortion-free, so the entropy column of Theorem 3.6 applies. (b) To implicate no innocent user above δ/N , the consistency-list rule needs log(N/δ)/r2 tokens (amber) while surprisal thresholding needs log(N/δ)/h (blue); the shaded overcharge is the factor h/r2 = 1.61, widening as Θ(log N ).
watermarks on the biasing side: green-list and its descendants tilt every token; the distortion-free family keeps p̄ = pnat but spreads its signal over the whole sequence; and SEAL, EditGuard, AudioSeal, and Stable Signature perturb the entire latent, image, or waveform. For the distortion-free rows the per-secret reading shows this is forced, not incidental: the per-secret kernels of an exact sampler are near-deterministic in the key (each conditional collapses onto the token the key selects), so every position is marked (full support), and the per-token conditional divergence exceeds any finite cap, placing these schemes outside B(∆) for every finite ∆. They are governed by the entropy column, and by Theorem 3.6 that column is now closed: attribution among N users at n = (1 + o(1)) log N/h is tight for the exact-sampler schemes with i.i.d. keys that the theorem covers (the computationally undetectable constructions, governed by seed entropy, sit outside its hypotheses). The only genuine o(n)-footprint schemes in Table 2 are Tree-Ring (a ring on a few Fourier shells) and the theoretical digit-stamp. Even RingID (Ci et al., 2024), the Tree-Ring successor engineered for multi-key identification, does not join them: its key capacity comes from a key-specific noise pattern occupying an entire latent channel alongside the discretized rings, so its per-secret footprint is a constant fraction of the latent (Section D) — attribution capacity was bought by leaving the small-footprint class. The ∆-free decoupling of Theorem 3.3(b) is therefore realized by essentially no deployed scheme, which is precisely why deployable, edit-robust ∆-free attribution is open (Section 6), not a solved case we are merely cataloguing. 2. Localization is a second, orthogonal axis (readout resolution), and the framework predicts its cost. Whether a scheme reaches Level 3 is decided not by its footprint but by whether its (full-support) mark is decoded per-region: SEAL reads a per-patch hash, EditGuard a per-region mask, AudioSeal a per-sample residual, while green-list reads one whole-passage count. This is not in tension with Theorem 3.12; it is its content. Crop-robust localization at resolution w requires a carrier footprint of size Ω(n/w), so a scheme that localizes finely and survives cropping must be full-support. The deployed localizers are indeed observed to be full-support (Table 2), consistent with this. The framework thus predicts both halves of the empirical benchmark on which fine-readout embedding-style schemes localize at high AUC while global-readout latent schemes (Gaussian Shading, Tree-Ring in pixels) score near zero (Arabi et al., 2025). 3. The classification is basis-relative. Tree-Ring is the one deployed embedding scheme, and only in the right basis: in the latent-noise spatial basis the inverse-DFT of the ring spreads over all noise coordinates (and the noise-to-image map is the full diffusion sampler, not a transform), so there it is biasing; in the Fourier basis of the initial noise the mark is a small object on a few frequency shells, and the detector reads it there by inverting
21
Watermark Forensics for Generative Models
coupling: +2.3 tokens per doubling of N
Detection saturates; attribution lags
1.0
tokens to attribute / detect
60
success
0.8 detectable yet unattributable
0.6 0.4 0.2 0.0
detection power (Level 0) attribution acc, N = 1048576 (Level 1)
0
20
40 60 tokens n
80
100
attribution n * logN detection n * (flat in N)
50 40 30 20 7.5 10.0 12.5 15.0 17.5 20.0 22.5 25.0 27.5 log2 N (number of users)
Figure 12: Detection is not attribution on the deployed green-list watermark, GPT-2. (a) Detection power
saturates by n ≈ 28 tokens while attribution accuracy (shown for N = 220 ) lags; in the shaded window the text is detectable yet unattributable. (b) The attribution length (the 50%-accuracy crossing) grows linearly in log N (+2.3 tokens per doubling of N ); the detection threshold is flat in N . The finite-N form of the Θ(log N ) gap of Theorem 3.2.
the generation.1 The localization map can be a change of basis; the framework asks in which representation the mark becomes an o(n) object, and answers that for almost all of today’s schemes there is none. SemStamp (Hou et al., 2024) makes the relativity concrete a second time, in the opposite direction: its extractor reads a sentence-embedding dictionary, where the carrier’s coordinates are sentences rather than tokens, and the basis change re-grains the footprint without shrinking it: every sentence is steered into a keyed LSH region, so the scheme is full-support at either granularity. A change of basis can relocate the mark (Tree-Ring) or merely change the units in which it is read (SemStamp); only the former creates an o(n) object. Consistency with the definition. A green-list key is recoverable from a long window and a SEAL patch-hash is readable from a crop, yet both schemes mark a constant fraction of coordinates under every key, so both are biasing under the per-secret footprint (Definition 2.4); they differ in readout resolution, not in footprint. Keying the embedding/biasing line on “readable from a sub-carrier” would split them; keying it on the footprint does not, and Table 2 is the consistent application.
5
Related work
Detection statistics (Level 0), imported. A line of recent work pins down the sample complexity of watermark detection. Huang et al. (2023) give uniformly most powerful tests and matching minimax Type-II bounds; Li et al. (2025b) derive closed-form detection efficiency and the pivotal statistic; Cai et al. (2024) √ establish the per-step KL detectability floor 1 − 1 − e−DKL and the fidelity–detectability frontier (sharpened by He et al., 2025c to a tight f -divergence bound). These fix our Level-0 rung at ndet = Θ(1/∆); we treat the rate and the ∆ ↔ (α, β) knob as given and build the ladder above them. Multi-user watermarking and fingerprinting (Level 1). Cohen et al. (2025) construct language-model watermarks for many adaptive users with a detect-short / trace-long gap, built from Tardos and Boneh–Shaw fingerprinting codes (Boneh and Shaw, 1998; Tardos, 2008). This is the closest prior art, and it proves the direction complementary to ours: achievability of cheap detection with expensive tracing in a cryptographic model. Their sole optimality remark is a counting argument (“log n bits are needed to identify a user”); there is no statistical converse on length, no distortion budget, and no biasing side. The matching converse we use is not new: the distortion-constrained fingerprinting converse of Moulin (2008) and Somekh-Baruch and Merhav (2005) 1 Like sparsity, the footprint is relative to a fixed dictionary and a fixed coordinate ordering: for Tree-Ring the dictionary is
the latent-Fourier one and the ordering is its radial indexing of shells. Only the mass ∥ν∥1 is invariant under a change of either (Proposition 2.6).
22
Watermark Forensics for Generative Models
The collision trap is not model-specific: r2 < h on every model
gpt2
h/r2 = 1.61 ×
pythia-410m
h/r2 = 1.60 ×
Qwen2.5-0.5B
h/r2 = 1.57 ×
0
1
2 3 rate (nats / token)
r2 (consistency rate) h (surprisal rate)
4
Figure 13: The overcharge h/r2 across model families. On GPT-2, Pythia-410M, and Qwen2.5-0.5B the absolute
rates differ, but r2 < h with a stable ratio ≈ 1.6: the consistency-list rule costs ∼ 60% more tokens than surprisal thresholding on every model. The collision trap is a property of natural-language entropy.
already proves that fingerprinting capacity under a fidelity constraint → 0 as the constraint tightens, exactly the “couples to the budget” phenomenon (with L2 -distortion in place of KL). We import it and instantiate it for the per-token KL channel rather than claim it. Classical fingerprinting (Tardos, 2008) supplies the Θ(c2 log N ) scaling under the combinatorial marking assumption (the same code machinery drives tight lower bounds well beyond watermarking, e.g. in differential privacy, Bun et al., 2014), but with no detection task and hence no separation. Our addition over this line is the contrast with the footprint model (Theorem 3.3), not the converse. Jiang et al. (2024) study detection versus attribution empirically at fixed length and argue, under a strict threshold, that the two essentially coincide. This is the opposite phenomenology to our impossibility regime, which their model (embedding bitstrings, no biasing, no length law) cannot express. Concurrent work of Song and Shahabi (2025) studies attribution faithfulness without a sample-complexity ladder. On the deployed-attribution axis, Sander et al. (2024) recover a membership/identity signal from watermarked text (“radioactivity”); this is a Level-1-flavored capability in practice, but it asks whether a model was trained on marked text rather than which of N users emitted a fixed sample, and it carries no length law. Multi-bit payload capacity (Level 2) is studied by Guo et al. (2026) via Gelfand–Pinsker coding and by Gilani et al. (2026); Yoo et al. (2023); our embedding-side payload term is consistent with these, and the log N attribution surcharge is the axis they lack. The embedding/biasing taxonomy (Level 3 and the dichotomy). The recent SoK (Zhao et al., 2025a) taxonomizes “statistical” (token-probability) versus “embedding” (content-feature) schemes and argues detection and attribution should be separate functions, but on the robustness-versus-unforgeability security axis, with no sample-complexity content; the statistical/embedding split there is an engineering taxonomy, never a theorem or a phase boundary. Empirical localization results confirm the mechanism without explaining it: SEAL (Arabi et al., 2025) localizes at 98.2% AUC where distributional schemes score 0% on the same task, and EditGuard (Zhang et al., 2024) gives tamper localization for image watermarks. Our Theorem 3.3 is, to our knowledge, the first theorem stating the existence of a localization map as the boundary between ∆-coupled and ∆-free forensic cost. Concurrent information-theoretic frameworks. Distributional Information Embedding (He et al., 2025a) is the closest concurrent framework: it analyzes the watermarking trade-off at the level of the scalar I(S; X). Our profile ν(t) is the positional refinement of that scalar (its mass recovers it), and the forensic ladder is the use the refinement is put to: tasks become functionals of ν that a single number cannot separate. The unified-optimization framework of Gloaguen et al. (2026b) treats scheme design as constrained optimization, the design axis, orthogonal to sample complexity. Proportion estimation (Li et al., 2025d) targets a different Level-3-adjacent estimand: what fraction of a text is marked, not which positions; WISER (Bonnerjee et al.,
23
fine / per-region
forbidden small footprint cannot localize at fine resolution m w = Ω(n) (Theorem 3.12)
SEAL EditGuard AudioSeal
global readout
readout resolution
(localization, Theorem 3.12)
Watermark Forensics for Generative Models
SynthID
Tree-Ring
Gaussian Shading
digit-stamp
green-list
full support Ω(n)
small o(n)
footprint |T |
(∆-free ←→ ∆-coupled, Theorem 3.3)
Figure 14: The two orthogonal axes of the taxonomy. The footprint |T | (horizontal; small gold dots = embedding,
full-support blue dots = biasing) governs the ∆-free decoupling of Theorem 3.3; the readout resolution (vertical) governs localization (Theorem 3.12). Being independent, the two axes let deployed schemes spread across three quadrants, and the localizers (SEAL, EditGuard, AudioSeal) reach Level 3 by fine readout, not a small footprint. The fourth quadrant, small footprint with fine resolution, is empty for a reason: Theorem 3.12 forbids it, m w = Ω(n).
2025) localizes multi-segment watermarks via change-point methods, an empirical/finite-sample method with no information-theoretic lower bound. Steganography. The information-theoretic model of steganography (Cachin, 2004; Fridrich, 2009) and the square-root law of steganographic capacity (Ker et al., 2008) concern the bounded-total-KL regime, where keeping √ the total divergence constant forces an embeddable payload of order n. Our regime is the linear-total-KL one: a per-token budget ∆ gives total budget n∆ and a payload linear in n. The two should not be conflated; the forensic-recovery budget (Theorem 3.1) is the linear-regime analogue of the stego capacity bound, now resolved by forensic level and by mechanism. The structurally closest predecessor of a per-position information quantity is Filler and Fridrich (2009): under mutually independent embedding, a per-element Fisher information, summed across the cover, determines the capacity of ε-secure steganography — the engine of the square-root law. The profile ν differs on three axes: it is a mutual-information quantity, not a second-order (Fisher) one; it feeds per-task functionals (mass and shape), not a single aggregate capacity; and it is defined on autoregressive conditionals, not i.i.d. cover models. Covert communication and perfect steganography. The square-root law of covert capacity (Bash et al., √ 2012; Bloch, 2016; Ker, 2007) lives in the budget regime KL ≤ ε: a fixed total divergence forces an O( n) payload. The statistically distortion-free column of Table 1 is the KL = 0 keyed regime (Cachin-style perfect steganography (Cachin, 2004)) where the binding resource is not a divergence budget but the generation entropy h. Theorem 3.6 is the multi-user attribution rate for that regime; to our knowledge no prior work gives a tight h-rate for N -user attribution. The closest, Cohen et al. (2025), is cryptographic (security-parameter counting, with adaptive robustness as the focus), complementary, not rate-tight. Identification via channels. Steinberg and Merhav (2001) cast watermark identification as identification via channels in the sense of Ahlswede and Dueck (1989): the blocklength is held fixed and the number of verifiable signatures grows doubly exponentially in it. This is the dual of our question, which fixes the user population N and asks for the sample cost n(N ). Their split between verification (“is it signature s?”) and decoding (“which signature?”) has, to our knowledge, no sample-complexity counterpart; we pose it as an open question in Section 6. Impossibility and robustness. A separate thread shows strong watermarks can be removed under mild assumptions (Francati et al., 2026; Zhang et al., 2023), the latter giving a sharp coding-theoretic ceiling on tamper
24
Watermark Forensics for Generative Models
Table 2: Where deployed watermarks fall, with the footprint criterion applied uniformly. “Basis” is the representation the
extractor reads; “Footprint” is the per-secret footprint T (Corollary 3.4), full (Ω(n)) or small (o(n)) (footprint read on per-secret kernels; Section C.8); “Model” is the operative quality model; “Readout” is global (whole-carrier statistic) or fine (per-region); “Levels” lists the forensic rungs the base construction reaches, with parenthesized rungs reached only by descendant or extension variants (multi-bit, many-user, or message-channel versions), not the base scheme. Almost every deployed scheme is full-support (biasing); the genuine o(n)-footprint cases are Tree-Ring (a ring in the Fourier basis) and the theoretical digit-stamp. Level-3 localizers are full-support with fine readout, exactly as Theorem 3.12 requires. Scheme
Basis
Footprint
Model
Readout
Levels
Class
Language models (token carrier): all biasing Green-list (Kirchenbauer et al., 2023) Unigram (Zhao et al., 2024) SynthID-Text (Dathathri et al., 2024) Reweighting (Hu et al., 2024; Wu et al., 2024) Multi-bit (Gilani et al., 2026; Yoo et al., 2023) BiMark (Feng et al., 2025) Many-user (Cohen et al., 2025) Distortion-free (Kuditipudi et al., 2023) Undetectable (Christ et al., 2024) PRC (Christ and Gunn, 2024) SemStamp (Hou et al., 2024)
tokens tokens tokens tokens tokens tokens tokens tokens tokens tokens sentence-emb.
full full full full full full full full full full full
B(∆) B(∆) d-free d-free B(∆)/d-free d-free d-free d-free d-free d-free B(∆)
global global global global bucketed bucketed global global global global global
0,(1,2) biasing 0 biasing 0 biasing (d-free) 0 biasing (d-free) 0,2 biasing 0,2 biasing (d-free) 0–2 biasing (d-free) 0 biasing (d-free) 0 biasing (d-free) 0 biasing (d-free) 0 biasing
Images / audio Tree-Ring (Wen et al., 2023) RingID (Ci et al., 2024) Gaussian Shading (Yang et al., 2024) ROBIN (Huang et al., 2024) HiDDeN (Zhu et al., 2018) Stable Signature (Fernandez et al., 2023b) SEAL (Arabi et al., 2025) EditGuard (Zhang et al., 2024) AudioSeal (San Roman et al., 2024)
Fourier Fourier latent Fourier (interm.) pixels feature latent pixels samples
small full full full full full full full full
d-free d-free (part.) d-free B(∆) B(∆) B(∆) d-free B(∆) B(∆)
global global global global global global fine fine fine
0,(1) 0,1 0,2 0 0,2 0,2 0–3 0,(2),3 0,(2),3
embedding biasing biasing (d-free) biasing biasing biasing biasing (d-free) biasing biasing
(Digit-stamp, Theorem 3.3(b))
tokens
small
E(m)
global
0–2
embedding
robustness, and that reusing a detector across keys inflates false positives (Fu and Russell, 2025); on the attack side, Abdalla and Vershynin (2025) exhibit statistical-to-computational gaps for removal. The false-detection result is a ∆-dependent upper bound on one parasitic detector, not a floor over all detectors on natural content; we discuss the corresponding open question (a false-positive floor) in Section 6. Recent design, detection, attack, and localization work adjacent to the framework is surveyed further in Section E.
6
Discussion
What the dichotomy says for regulation. Current statutes ask for marks “in a machine-readable format” (EU AI Act, Art. 50), “noticeable labels” (China’s Deep Synthesis provisions), or “latent disclosure” (California SB 942). Read operationally, each presumes an extractable object: the embedding side of Definition 2.4. Theorem 3.3 makes the cost of that presumption precise: a biasing watermark can satisfy a Level-1 (attribution) or Level-2 (extraction) mandate only at a sample cost Ω(log N/∆) that diverges as the mark is made stealthier (∆ → 0), whereas an embedding watermark pays a fixed Θ(log N/ log q) independent of fidelity. A regulator who wants attribution is, whether or not the text says so, mandating the embedding ontology. We state this as an informed structural consequence, not a legal interpretation. Which rate is a sample complexity. The closed column also settles a question the naive analysis gets wrong: the Rényi-2 rate r2 governs the size of the falsely-consistent list, but the Shannon rate h governs the decision, and only the decision is what a forensic guarantee names (Proposition 3.9). Whether an edit-robust decoder, which can no longer check consistency token-for-token, is forced back onto the larger r2 rate is the open question we turn to next.
25
Watermark Forensics for Generative Models
Localization (Level 3) and the witness gap. Theorem 3.12 makes the redundancy–resolution tradeoff quantitative: crop-robust localization at resolution w forces m w = Ω(n) (precisely |R+ | ≥ (n − w + 1)/w for the dilated support and |R| ≥ |R+ |/(2r + 1), with |R| ≤ m in the factorizing regime). This explains the empirical split (Section 4) and exposes the honest limit of our decoupling witness. The digit-stamp of Theorem 3.3(b) has footprint m = Θ(log N/ log q) = o(n), so by Theorem 3.12(ii) it cannot be crop-robust at any fine resolution: a single splice destroys it. The deployed schemes that do localize (SEAL at 98.2% AUC, EditGuard, AudioSeal) are, by Theorem 3.12, forced to be full-support; they are biasing and localize only because they read their delocalized mark at fine per-region resolution. So the clean ∆-free decoupling and operational edit-robust localization pull in opposite directions, and the question our witness leaves open (is there a deployable (imperceptible, edit-robust) scheme whose attribution cost is ∆-free?) is, by Theorem 3.12, exactly the question of whether one can be ∆-free on the payload while paying the m w = Ω(n) tax only on the locating layer. We conjecture this is achievable with a layered PRC-style construction but do not prove it. The same gap is now the live one on the distortion-free side: Theorem 3.6 closes the attribution rate there, but its witness decoder is exact-alignment (consistency is checked token-for-token against the key) and a single edit destroys it. Under a soft (edit-robust) notion of consistency the true key is no longer deterministically consistent, the tie-abstention device behind Proposition 3.9 loses its zero-false-positive guarantee, and a genuine r2 -type cost may resurface. Whether edit-robust distortion-free attribution still costs log N/h, or genuinely pays the larger log N/r2 , is the sharpest open problem the framework raises. Verification versus search (open). Our attribution task is a search: which of N users emitted X? The verification variant (is it user u?) is a composite binary test, and the identification-via-channels literature (Ahlswede and Dueck, 1989; Steinberg and Merhav, 2001), with a covert (distortion-free) analogue in Zhang and Tan (2021), suggests the two scale very differently: at fixed blocklength the number of verifiable signatures is doubly exponential while the decodable ones are merely exponential. The sample-complexity dual would make verification N -free, an exponential separation from search’s Θ(log N/∆); the proof obstacle is testing the composite null (the N − 1 other keys) uniformly. The sample-complexity version of the verification-vs-decoding split is open; we have not pursued it here. A false-positive floor (open). The seed of this work conjectured an information-theoretic false-positive floor for biasing watermarks on natural content: that no detector can drive the false-positive rate to zero at fixed power when pwm and pnat overlap. Against a computationally unbounded distinguisher this is delicate, since undetectable constructions (Christ et al., 2024) make the marginal gap vanish, so any floor must be stated in the key-known or information-theoretic-adversary regime. Fu and Russell (2025) give a related upper bound (false positives inflate when a detector is reused across keys), but a genuine floor over all detectors on a natural-content null remains open. We leave it as a conjecture rather than fold a weaker statement into the main results. Tightness and generality of the achievability (open). Three gaps remain between our converses and the constructions that meet them. The B(∆) achievability of Theorem 3.3(a) matches its converse only up to the per-position capacity constant, and only for memoryless or regular strongly-mixing sources; the exact q-ary tilting constant, and a general-ergodic achievability that removes the mixing hypothesis the conditional tilting code needs, are both open. On the distortion-free side the entropy column assumes i.i.d. per-user keys; correlated or coded assignments (Tardos-style, Tardos, 2008) might trade candidate-list size against length, a different point on the same rate curve. None of these changes a rate order; each sharpens a constant or widens a hypothesis. Existence, identity, and the ledger. Beneath the rates, the ladder separates two kinds of question. Detection asks whether a mark exists: a two-point hypothesis test, whose cost is set by a fixed divergence and is indifferent to the size of the user population. Attribution asks who: an estimation among N alternatives, which cannot conclude before log N nats of identity have arrived. Existence is cheap; identity is priced; and the window of Theorem 3.2 is what lies between, a text that can raise suspicion but cannot yet support a name. The form of a forensic guarantee matters as much as its rate: Theorem 3.6(i) prices false accusation per innocent rather than on average (no innocent is implicated except with probability δ/N , exactly and non-asymptotically), which is the quantitative shape of a presumption of innocence. And the account every level draws on is settled before any question is asked: by data processing (Theorem 3.1), reading the carrier can only spend information that generation deposited, never mint more. What can ever be detected, attributed, or extracted from a scheme’s output is fixed, token by token, by the profile ν it writes, and where it can be localized is fixed by the shape 26
Watermark Forensics for Generative Models
of ν together with the edit coupling on the carrier; the quality models are covenants on the deposits (∆ at a time, or only what the source’s entropy affords); attribution and extraction are withdrawals against one balance (Proposition 3.13). Design is the choice of a deposit schedule, and a forensic mandate is, in the end, a constraint on ν. Limitations. (i) Our bounds are information-theoretic: Φ(n) = I(S; X) caps every computationally unbounded extractor, so the lower bounds are unconditional, but the distortion-free budget (Assumption 2.2) uses statistical undetectability, with a negligible slack under merely computational undetectability. (ii) The Level-0 detection rate we import assumes the standard independent/stationary-token model (Huang et al., 2023; Li et al., 2025b); our colocated gap needs only that the key-unknown detection error vanishes on the window, which in that model follows from a positive per-token mixture divergence via the relative-entropy ergodic theorem (a large total KL alone would not suffice for a single joint sample). (iii) The within-scheme impossibility (Theorem 3.2, “detectable yet unattributable at one length”) is an asymptotic statement: it lives on the window ω(1/∆) ≤ n < (1 − η) log N/∆, which is wide as N → ∞ but narrow at moderate N , so our simulations (Section 3.6) accordingly exhibit the robust form of the separation (attribution threshold Θ(log N ) above the detection threshold) rather than the razor-thin point. (iv) The embedding “stamp” of Theorem 3.3 is the simplest witness of decoupling, not a deployable scheme; robust embedding watermarks (commitment- or code-based; SEAL, EditGuard empirically) realize the same decoupling with imperceptibility and robustness, which we cite rather than reprove. (v) The distortion-free achievability of Theorem 3.6 and Corollary 3.7 is information-theoretic in its decoder as well: the witness extractor searches the key set, so it runs in time Θ(N ) = Θ(2ℓ ) in the payload; an efficient Θ(ℓ/h)-sample extractor is a separate requirement, which the “machine-readable mark” reading of a regulatory mandate implicitly wants and which we leave open. Summary. A watermark is an object in its carrier or a property of its law, and the footprint of Definition 2.4 is where that informal distinction becomes measurable. Detection is the cheapest question one can ask of either kind, and the only one whose cost is mechanism-blind. Every question above it (who, what, where) is metered by a single distortion budget for schemes confined to the distributional quality model, and bought at a ∆-free price by schemes that can use a bounded footprint; the localization map is the structural feature that admits the cheaper model, and it enables without deciding. The three questions above detection are readings of one measure, two of its mass and one of its shape with the edit coupling on the carrier, and their prices differ because the readings do.
7
Conclusion
A watermark decides, token by token as it generates, how much of its secret the world will ever recover; the information profile ν(t) = I(S; Xt | X<t ) is the record of that decision, and the forensic questions above detection are readings of it. The prices follow. The mass ∥ν∥1 funds attribution and extraction in one of two currencies, ∆ per token against a fidelity budget or h per token against the entropy the source affords; the shape of ν, with the edit coupling on the carrier, governs localization under the uncertainty m w = Ω(n); detection is the mechanism-blind baseline beneath them. The question that would have led our list of open problems, a distortion-free achievability to match the entropy converse, is closed by Theorem 3.6: attribution costs (1 + o(1))(log N + log(1/δ))/h at full stationary-ergodic generality, with an exact per-innocent false-positive guarantee, and extraction follows at Θ(ℓ/h) (Corollary 3.7). With this the ladder’s currencies are identified at every rung: ∆, h, and the geometry of the footprint. What the framework leaves open — and the sharpest of it is a matter of robustness, not of information — we set out in Section 6. Nothing in the profile is special to watermarking. ν(t) = I(S; Xt | X<t ) prices what any secret threaded through a sequential generator makes recoverable, and its mass-versus-shape reading should apply wherever information is embedded position by position — steganography, fingerprinting, covert communication. We have used it to say one thing about one domain: the forensic power of a watermark is fixed by the information it makes recoverable, not by the mechanics of how the mark is embedded.
27
Watermark Forensics for Generative Models
References Scott Aaronson. My AI safety lecture for UT effective altruism. Blog post, https://scottaaronson.blog/?p= 6823, 2022. Pedro Abdalla and Roman Vershynin. LLM watermarking using mixtures and statistical-to-computational gaps. arXiv preprint arXiv:2505.01484, 2025. Rudolf Ahlswede and Gunter Dueck. Identification via channels. IEEE Transactions on Information Theory, 35 (1):15–29, 1989. doi: 10.1109/18.42172. Zhenxin Ai and Haiyun He. PASA: A principled embedding-space watermarking approach for LLM-generated text under semantic-invariant attacks. arXiv preprint arXiv:2605.10977, 2026. Kasra Arabi, R. Teal Witter, Chinmay Hegde, and Niv Cohen. SEAL: Semantic aware image watermarking. arXiv preprint arXiv:2503.12172, 2025. Aristotle. Categories and De Interpretatione. Clarendon Press, Oxford, 1963. Rui Bao, Zheng Gao, Xiaoyu Li, Xiaoyan Feng, Yang Song, and Jiaojiao Jiang. SHIFT: Stochastic hiddentrajectory deflection for removing diffusion-based watermark. arXiv preprint arXiv:2603.29742, 2026. Andrew R. Barron. The strong ergodic theorem for densities: Generalized Shannon–McMillan–Breiman theorem. The Annals of Probability, 13(4):1292–1303, 1985. doi: 10.1214/aop/1176992813. Boulat A. Bash, Dennis Goeckel, and Don Towsley. Square root law for communication with low probability of detection on AWGN channels. In Proc. IEEE International Symposium on Information Theory (ISIT), pages 448–452, 2012. doi: 10.1109/ISIT.2012.6284228. Stella Biderman, Hailey Schoelkopf, Quentin Anthony, Herbie Bradley, Kyle O’Brien, Eric Hallahan, Mohammad Aflah Khan, Shivanshu Purohit, USVSN Sai Prashanth, Edward Raff, Aviya Skowron, Lintang Sutawika, and Oskar van der Wal. Pythia: A suite for analyzing large language models across training and scaling. In International Conference on Machine Learning (ICML), 2023. Matthieu R. Bloch. Covert communication over noisy channels: A resolvability perspective. IEEE Transactions on Information Theory, 62(5):2334–2354, 2016. doi: 10.1109/TIT.2016.2530089. Dan Boneh and James Shaw. Collusion-secure fingerprinting for digital data. IEEE Transactions on Information Theory, 44(5):1897–1905, 1998. Soham Bonnerjee, Sayar Karmakar, and Subhrajyoty Roy. WISER: Segmenting watermarked region — an epidemic change-point perspective. arXiv preprint arXiv:2509.21160, 2025. Mark Bun, Jonathan Ullman, and Salil Vadhan. Fingerprinting codes and the price of approximate differential privacy. In STOC, 2014. Christian Cachin. An information-theoretic model for steganography. Information and Computation, 192(1): 41–56, 2004. Zhongze Cai, Shang Liu, Hanzhao Wang, Huaiyang Zhong, and Xiaocheng Li. Towards better statistical understanding of watermarking LLMs. arXiv preprint arXiv:2403.13027, 2024. Shuwen Chai and Qiaosen Wang. Sample complexities of estimating Gumbel–max watermark proportions with and without reduction to pivotal statistics. arXiv preprint arXiv:2607.00224, 2026. Pengzhen Chen, Yanwei Liu, Xiaoyan Gu, Antonios Argyriou, Wu Liu, and Weiping Wang. Rotation-invariant spherical watermarking via third-order SO(3) representation coupling. arXiv preprint arXiv:2605.26702, 2026. Miranda Christ and Sam Gunn. Pseudorandom error-correcting codes. arXiv preprint arXiv:2402.09370, 2024.
28
Watermark Forensics for Generative Models
Miranda Christ, Sam Gunn, and Or Zamir. Undetectable watermarks for language models. In Conference on Learning Theory (COLT), 2024. Hai Ci, Pei Yang, Yiren Song, and Mike Zheng Shou. RingID: Rethinking tree-ring watermarking for enhanced multi-key identification. In ECCV, 2024. Aloni Cohen, Alexander Hoover, and Gabe Schoenbach. Watermarking language models for many adaptive users. In IEEE Symposium on Security and Privacy (S&P), 2025. Thomas M. Cover and Joy A. Thomas. Elements of Information Theory. Wiley-Interscience, 2nd edition, 2006. Sumanth Dathathri, Abigail See, Sumedh Ghaisas, Po-Sen Huang, Rob McAdam, Johannes Welbl, et al. Scalable watermarking for identifying large language model outputs. Nature, 634(8035):818–823, 2024. Jacques Derrida. Limited Inc. Northwestern University Press, Evanston, IL, 1988. John Duns Scotus. Six questions on individuation (Ordinatio II, d. 3, part 1). In Paul Vincent Spade, editor, Five Texts on the Mediaeval Problem of Universals, pages 57–113. Hackett, Indianapolis, 1994. Xiaoyan Feng, He Zhang, Yanjun Zhang, Leo Yu Zhang, and Shirui Pan. BiMark: Unbiased multilayer watermarking for large language models. In Proceedings of the 42nd International Conference on Machine Learning (ICML), volume 267 of Proceedings of Machine Learning Research, 2025. Pierre Fernandez, Antoine Chaffin, Karim Tit, Vivien Chappelier, and Teddy Furon. Three bricks to consolidate watermarks for large language models. In IEEE International Workshop on Information Forensics and Security (WIFS), 2023a. Pierre Fernandez, Guillaume Couairon, Hervé Jégou, Matthijs Douze, and Teddy Furon. The stable signature: Rooting watermarks in latent diffusion models. arXiv preprint arXiv:2303.15435, 2023b. Tomáš Filler and Jessica Fridrich. Fisher information determines capacity of ε-secure steganography. In Information Hiding (IH 2009), volume 5806 of Lecture Notes in Computer Science, pages 31–47. Springer, 2009. Danilo Francati, Yevin Nikhel Goonatilake, Shubham Pawar, Daniele Venturi, and Giuseppe Ateniese. The coding limits of robust watermarking for generative models. In IEEE European Symposium on Security and Privacy (EuroS&P), 2026. Jessica Fridrich. Steganography in Digital Media: Principles, Algorithms, and Applications. Cambridge University Press, 2009. Zihao Fu and Chris Russell. Multi-use LLM watermarking and the false detection problem. arXiv preprint arXiv:2506.15975, 2025. Zheng Gao, Xiaoyu Li, Zhicheng Bao, Xiaoyan Feng, and Jiaojiao Jiang. Breaking semantic-aware watermarks via LLM-guided coherence-preserving semantic injection. In Proceedings of the ACM Web Conference, pages 8569–8572, 2026a. doi: 10.1145/3774904.3792912. Zheng Gao, Xiaoyu Li, Xiaoyan Feng, Jiaojiao Jiang, Yang Song, Yulei Sui, Zhenchang Xing, and Liming Zhu. TRACE: A two-channel robust attribution watermark via complementary embeddings for LLM-agent trajectories. arXiv preprint arXiv:2607.08400, 2026b. Zheng Gao, Yifan Yang, Xiaoyu Li, Xiaoyan Feng, Haoran Fan, Yang Song, and Jiaojiao Jiang. SLICE: Semantic latent injection via compartmentalized embedding for image watermarking. arXiv preprint arXiv:2603.12749, 2026c. Atefeh Gilani, Sajani Vithana, Carol Xuan Long, Oliver Kosut, Lalitha Sankar, and Flavio P. Calmon. ArcMark: Distortion-free multi-byte LLM watermark via optimal transport. arXiv preprint arXiv:2602.07235, 2026.
29
Watermark Forensics for Generative Models
Thibaud Gloaguen, Robin Staab, Nikola Jovanović, and Martin Vechev. Watermarking diffusion language models. In International Conference on Learning Representations (ICLR), 2026a. Thibaud Gloaguen, Robin Staab, Nikola Jovanović, and Martin Vechev. A unified framework for LLM watermarks. arXiv preprint arXiv:2602.06754, 2026b. Noah Golowich and Ankur Moitra. Edit distance robust watermarks for language models. In Advances in Neural Information Processing Systems (NeurIPS), 2024. Sidong Guo, Tyler Kann, Teodora Baluta, and Matthieu R. Bloch. Covert multi-bit LLM watermarking: An information theory and coding approach. arXiv preprint arXiv:2605.16709, 2026. Haiyun He, Yepeng Liu, Ziqiao Wang, Yongyi Mao, and Yuheng Bu. Distributional information embedding: A framework for multi-bit watermarking. arXiv preprint arXiv:2501.16558, 2025a. Haiyun He, Yepeng Liu, Ziqiao Wang, Yongyi Mao, and Yuheng Bu. Theoretically grounded framework for LLM watermarking: A distribution-adaptive approach. In Advances in Neural Information Processing Systems (NeurIPS), 2025b. Haiyun He, Yepeng Liu, Zhuoer Shen, Ziqiao Wang, Yongyi Mao, and Yuheng Bu. Fundamental trade-offs in multi-bit watermarking of stochastic processes. arXiv preprint arXiv:2605.08826, 2026. Hengzhi He, Shirong Xu, Alexander Nemecek, Jiping Li, Erman Ayday, and Guang Cheng. Optimal watermark generation under type I and type II errors. arXiv preprint arXiv:2512.05333, 2025c. Herodotus. The Histories. Oxford University Press, Oxford, 1998. Abe Bohan Hou, Jingyu Zhang, Tianxing He, Yichen Wang, Yung-Sung Chuang, Hongwei Wang, Lingfeng Shen, Benjamin Van Durme, Daniel Khashabi, and Yulia Tsvetkov. SemStamp: A semantic watermark with paraphrastic robustness for text generation. In NAACL, 2024. Zhengmian Hu, Lichang Chen, Xidong Wu, Yihan Wu, Hongyang Zhang, and Heng Huang. Unbiased watermark for large language models. In International Conference on Learning Representations (ICLR), 2024. Baihe Huang, Hanlin Zhu, Banghua Zhu, Kannan Ramchandran, Michael I. Jordan, Jason D. Lee, and Jiantao Jiao. Towards optimal statistical watermarking. arXiv preprint arXiv:2312.07930, 2023. Huayang Huang, Yu Wu, and Qian Wang. ROBIN: Robust and invisible watermarks for diffusion models with adversarial optimization. In NeurIPS, 2024. Dard Hunter. Papermaking: The History and Technique of an Ancient Craft. Alfred A. Knopf, New York, 2nd edition, 1947. Zhengyuan Jiang, Moyang Guo, Yuepeng Hu, Yupu Wang, and Neil Zhenqiang Gong. Watermark-based detection and attribution of AI-generated content. arXiv preprint arXiv:2404.04254, 2024. David Kahn. The Codebreakers: The Story of Secret Writing. Macmillan, New York, 1967. Andrew D. Ker. A capacity result for batch steganography. IEEE Signal Processing Letters, 14(8):525–528, 2007. Andrew D. Ker, Tomáš Pevný, Jan Kodovský, and Jessica Fridrich. The square root law of steganographic capacity. In ACM Workshop on Multimedia and Security, 2008. John Kirchenbauer, Jonas Geiping, Yuxin Wen, Jonathan Katz, Ian Miers, and Tom Goldstein. A watermark for large language models. In ICML, 2023. Saul A. Kripke. Naming and Necessity. Harvard University Press, Cambridge, MA, 1980. Rohith Kuditipudi, John Thickstun, Tatsunori Hashimoto, and Percy Liang. Robust distortion-free watermarks for language models. arXiv preprint arXiv:2307.15593, 2023. 30
Watermark Forensics for Generative Models
Gottfried Wilhelm Leibniz. Philosophical Essays. Hackett, Indianapolis, 1989. Wenda Li, Huijie Zhang, and Qing Qu. Shallow diffuse: Robust and invisible watermarking through lowdimensional subspaces in diffusion models. In Advances in Neural Information Processing Systems (NeurIPS), 2025a. Xiang Li, Feng Ruan, Huiyuan Wang, Qi Long, and Weijie J. Su. A statistical framework of watermarks for large language models: Pivot, detection efficiency and optimal rules. The Annals of Statistics, 53(1):322–351, 2025b. arXiv:2404.01245. Xiang Li, Feng Ruan, Huiyuan Wang, Qi Long, and Weijie J. Su. Robust detection of watermarks for large language models under human edits. Journal of the Royal Statistical Society Series B: Statistical Methodology, 2025c. doi: 10.1093/jrsssb/qkaf056. Xiang Li, Garrett Wen, Weiqing He, Jiayuan Wu, Qi Long, and Weijie J. Su. Optimal estimation of watermark proportions in hybrid AI-human texts. arXiv preprint arXiv:2506.22343, 2025d. Bing Liu, Shunping Wang, Yufan Zhu, Xinyi Yu, Jing Huang, Linkang Du, Hongbin Pei, and Wei Luo. Implicit identity technologies for LLMs: Fingerprinting and watermarking across datasets, models, and generated content. arXiv preprint arXiv:2605.29245, 2026a. Yepeng Liu, Xuandong Zhao, Christopher Kruegel, Dawn Song, and Yuheng Bu. In-context watermarks for large language models. In International Conference on Learning Representations (ICLR), 2026b. Jiacheng Lu, Yiming Li, Tao Song, Weijian Wang, Wenjie Qu, Haibing Guan, and Jiaheng Zhang. Echoes within the reasoning: Stealthy and effective watermarking via chain of thought. arXiv preprint arXiv:2605.28890, 2026. Georgios Milis, Yubin Qin, Yihan Wu, and Heng Huang. Hidden in plain tokens: Simply robust, gradient-free watermark for synthetic audio. arXiv preprint arXiv:2605.25967, 2026. Pierre Moulin. Universal fingerprinting: Capacity and random-coding exponents. arXiv preprint arXiv:0801.3837, 2008. Yunyi Ni, Ziyu Yang, Ze Niu, Emily Davis, and Finn Carter. On the information-theoretic fragility of robust watermarking under diffusion editing. arXiv preprint arXiv:2511.10933, 2025. Charles Sanders Peirce. Collected Papers of Charles Sanders Peirce. Harvard University Press, Cambridge, MA, 1931. Haotian Qin, Dongliang Chang, Yueying Gao, Yuexuan Tan, Lei Chen, and Zhanyu Ma. IncreFA: Breaking the static wall of generative model attribution. arXiv preprint arXiv:2604.17736, 2026. Qwen Team. Qwen2.5 technical report. arXiv preprint arXiv:2412.15115, 2024. Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. Language models are unsupervised multitask learners. Technical report, OpenAI, 2019. Gilbert Ryle. The Concept of Mind. Hutchinson, London, 1949. Robin San Roman, Pierre Fernandez, Alexandre Défossez, Teddy Furon, Tuan Tran, and Hady Elsahar. Proactive detection of voice cloning with localized watermarking. In ICML, 2024. Tom Sander, Pierre Fernandez, Alain Durmus, Matthijs Douze, and Teddy Furon. Watermarking makes language models radioactive. arXiv preprint arXiv:2402.14904, 2024. Claude E. Shannon. A mathematical theory of communication. The Bell System Technical Journal, 27(3): 379–423, 1948. doi: 10.1002/j.1538-7305.1948.tb01338.x.
31
Watermark Forensics for Generative Models
Anelia Somekh-Baruch and Neri Merhav. On the capacity game of private fingerprinting systems under collusion attacks. IEEE Transactions on Information Theory, 51(3):884–899, 2005. Min Jae Song and Kameron Shahabi. Ideal attribution and faithful watermarks for language models. arXiv preprint arXiv:2512.07038, 2025. Yossef Steinberg and Neri Merhav. Identification in the presence of side information with application to watermarking. IEEE Transactions on Information Theory, 47(4):1410–1422, 2001. Gábor Tardos. Optimal probabilistic fingerprint codes. Journal of the ACM, 55(2):1–24, 2008. Dor Tsur, Carol Xuan Long, Claudio Mayrink Verdun, Hsiang Hsu, Chen-Fu Chen, Haim Permuter, Sajani Vithana, and Flavio P. Calmon. HeavyWater and SimplexWater: Distortion-free LLM watermarks for lowentropy distributions. In Advances in Neural Information Processing Systems (NeurIPS), 2025. Sergio Verdú and Te Sun Han. A general formula for channel capacity. IEEE Transactions on Information Theory, 40(4):1147–1157, 1994. Yuxin Wen, John Kirchenbauer, Jonas Geiping, and Tom Goldstein. Tree-ring watermarks: Fingerprints for diffusion images that are invisible and robust. arXiv preprint arXiv:2305.20030, 2023. Yihan Wu, Zhengmian Hu, Junfeng Guo, Hongyang Zhang, and Heng Huang. A resilient and accessible distribution-preserving watermark for large language models. In ICML, 2024. Zijin Yang, Kai Zeng, Kejiang Chen, Han Fang, Weiming Zhang, and Nenghai Yu. Gaussian shading: Provable performance-lossless image watermarking for diffusion models. In CVPR, 2024. KiYoon Yoo, Wonhyuk Ahn, and Nojun Kwak. Advancing beyond identification: Multi-bit watermark for large language models. arXiv preprint arXiv:2308.00221, 2023. Bokang Zeng, Zheng Gao, Xiaoyu Li, Xiaoyan Feng, and Jiaojiao Jiang. LAVA: Layered audio-visual antitampering watermarking for robust deepfake detection and localization. In Proceedings of the ACM International Conference on Multimedia (ACM MM), 2026. arXiv:2604.23957. Hanlin Zhang, Benjamin L. Edelman, Danilo Francati, Daniele Venturi, Giuseppe Ateniese, and Boaz Barak. Watermarks in the sand: Impossibility of strong watermarking for generative models. arXiv preprint arXiv:2311.04378, 2023. Qiaosheng Zhang and Vincent Y. F. Tan. Covert identification over binary-input discrete memoryless channels. IEEE Transactions on Information Theory, 2021. Xuanyu Zhang, Runyi Li, Jiwen Yu, Youmin Xu, Weiqi Li, and Jian Zhang. EditGuard: Versatile image watermarking for tamper localization and copyright protection. In CVPR, 2024. Xuandong Zhao, Prabhanjan Ananth, Lei Li, and Yu-Xiang Wang. Provable robust watermarking for AI-generated text. In International Conference on Learning Representations (ICLR), 2024. Xuandong Zhao, Sam Gunn, Miranda Christ, Jaiden Fairoze, Andres Fabrega, Nicholas Carlini, et al. SoK: Watermarking for AI-generated content. In IEEE Symposium on Security and Privacy (S&P), 2025a. Xuandong Zhao, Lei Li, and Yu-Xiang Wang. Permute-and-flip: An optimally stable and watermarkable decoder for LLMs. In International Conference on Learning Representations (ICLR), 2025b. Jiren Zhu, Russell Kaplan, Justin Johnson, and Li Fei-Fei. HiDDeN: Hiding data with deep networks. In ECCV, 2018.
32
Watermark Forensics for Generative Models
A
Notation
Table 3 collects the symbols used throughout. The dependency structure of the results is mapped in Figure 3 (Section 3); the imported and textbook facts each proof draws on are catalogued in Section C.1 and cited inline at each use. All logarithms and information quantities are in nats unless a base is shown; per the convention of Section 2, the profile ν and the budget Φ are read conditional on the registry κ (written I(S; X) for brevity). Table 3: Notation used throughout the paper.
Symbol
Meaning
Defined in
Model and keys n Σ, q = |Σ| X ∈ Σn pnat (k) pwm (K) p̄ = EK pwm K∈K κ = {k1 , . . . , kN } P (kv ) p p̂κ = N1 v wm S N, ℓ
carrier length (number of tokens) token alphabet and its size the carrier (the generated text/sample) natural (unmarked) law on Σn marked law under key k key-averaged (mixture) law secret key; key space key registry (enrolled keys; the informed decoder’s side information) realized key mixture given the registry κ secret: user U ∈ [N ], payload W ∈ {0, 1}ℓ , or both number of users; payload length (bits)
Section 2 Section 2 Section 2 Section 2 Section 2 Section 2 Section 2 Section 2 Section C.6 Section 2 Definition 2.9
The information profile ν(t) = I(S; Xt | X<t ) ∥ν∥1 = I(S; X) = Φ(n) supp ν T ¯ d(t)
information profile (secret information added by token t) its mass = the forensic-recovery budget its shape (support) per-secret footprint (the marked positions) per-secret distortion profile
Proposition 2.6 Definition 2.10 Proposition 2.6 Definition 2.4 Section 2
Quality models ∆ B(∆) E(m), m Lk R, R+ w
per-token distortion (KL) budget bounded-distortion / biasing class; L∞ cap ν(t) ≤ ∆ footprint / embedding class; L0 cap | supp ν| ≤ m localization map carrier footprint and its r-dilation (Level 3) crop resolution (window length)
Assumption 2.1 Assumption 2.1 Definition 2.4 Definition 2.4 Assumption 2.3 Definition 2.9
Forensic tasks and rates ndet , natt , next Pe δ λ
sample complexity of detection / attribution / extraction attribution error probability per-innocent false-positive level (attribution) detection soundness parameter (FP ≤ 2−λ )
Definition 2.9 Definition 2.9 Theorem 3.6 Section 2
Information-theoretic quantities h, hn P r2 = − log x pnat (x)2 ı(X) = − log pnat (X) τ = log(N/δ) I(·; ·), H(·), KL(· ∥ ·) JSD, Unif
B
(n)
entropy rate; finite-n entropy H(pnat )/n Rényi-2 rate realized surprisal surprisal threshold mutual information, entropy, relative entropy (nats) Jensen–Shannon divergence; uniform distribution
Assumption 2.2 Proposition 3.9 Definition 3.5 Definition 3.5 Section B Section B
Information-theoretic background
This section is a self-contained primer on the information-theoretic notions the paper uses; readers fluent in information theory can skip it. All quantities are in nats (natural logarithms), and pnat , pwm are laws on the length-n carrier Σn . 33
Watermark Forensics for Generative Models
Surprisal and entropy. The surprisal of an outcome x under a law p is ıp (x) = − log p(x): a rare outcome is P surprising. Its average is the entropy H(p) = Ex∼p ıp (x) = − x p(x) log p(x), the mean uncertainty in a draw (n) from p. For a sequence the per-symbol entropy hn = H(pnat )/n measures how much fresh randomness each token carries; for a stationary source it decreases to the entropy rate h = limn hn . Mutual information and the chain rule. The mutual information I(S; X) = H(S) − H(S | X) is how much observing X lowers the uncertainty about S. It is the right currency for a forensic decoder: by data processing (below), no function of X recovers more than I(S; X) nats about S. The chain rule resolves it position by P position, I(S; X) = t I(S; Xt | X<t ), and the summand ν(t) = I(S; Xt | X<t ) is the information profile that organizes the paper. Relative entropy, the golden formula, and data processing. The relative entropy (or Kullback–Leibler P divergence) KL(p ∥ q) = x p(x) log p(x) q(x) ≥ 0 measures how distinguishable p is from q; it is the exponent at which a likelihood-ratio test separates them. It is our fidelity currency: a mark that moves a token law by KL ∆ spends ∆ of distortion there. The golden formula (Fact 2.11) writes a mutual information as a divergence against any reference Q, I(K; X) = minQ EK KL PX|K ∥ Q , so I(K; X) ≤ EK KL PX|K ∥ Q for every Q; taking Q = pnat turns the bound into the distortion budget. The data-processing inequality, that a Markov chain S → K → X forces I(S; X) ≤ I(K; X), says post-processing cannot manufacture information. Together they are the forensic-recovery budget (Theorem 3.1). Fano’s inequality. To convert an information bound into an error bound we use Fano’s inequality (Fact 2.12): 2 naming one of N equiprobable users with error Pe needs I(U ; X) ≥ (1−Pe ) log N −log 2, i.e. Pe ≥ 1− I(U ;X)+log . log N Recovering log N nats of identity therefore demands a budget of ≈ log N nats; this is the engine of every lower bound here. Typicality and Stein’s lemma. The asymptotic equipartition property says the surprisal of a long sample concentrates: ıpnat (X)/n → h almost surely (the Shannon–McMillan–Breiman theorem), so a typical sample has probability ≈ e−nh . This is exactly why the surprisal threshold of Theorem 3.6 works: the true (typical) text clears any sub-h bar τ once n ≳ τ /h. The dual statement for testing is Stein’s lemma and its ergodic extension (Fact 2.13): the optimal test of p̄ against pnat has error decaying at the KL-rate, so a positive per-symbol divergence makes the two laws asymptotically separable. P Rényi-2 entropy and collisions. The Rényi-2 entropy rate r2 = − log x pnat (x)2 governs collisions: two P independent draws from pnat coincide with probability x pnat (x)2 = e−r2 per symbol. Rényi entropy is nonincreasing in its order, so r2 ≤ h, with equality only for a source uniform on its support; the gap h/r2 is precisely the factor by which the naive consistency analysis overcharges (Proposition 3.9). Jensen–Shannon divergence. The Jensen–Shannon divergence JSD(p, q) = 12 KL(p ∥ m) + 12 KL(q ∥ m), with m = 12 (p + q), is a symmetric, bounded divergence; it equals the mutual information between a fair coin choosing p or q and the resulting sample. It is the yield of the tilting code (Theorem 3.3): fidelity is spent in KL, but the bits a decoder reads back per token are measured by the JSD between the two tilted kernels.
C
Deferred proofs
The starred macros reprint each statement with its original number, so the appendix copy cannot drift from the body. The three textbook tools the proofs use as machinery are in Section 2.2; the prior results we import, together with the non-standard terminology they involve, are restated next.
C.1
Prior results we import, and their terminology
The proofs lean on three results from prior work that are not ours, and on a few information-theoretic terms that may be unfamiliar; we explain both informally here before invoking them. Fingerprinting capacity and collusion. A fingerprinting code gives each of N users a distinct codeword and asks, from one observed copy, which user it came from. A collusion attack lets several users pool their copies and average them into a forgery that no single codeword matches; the fingerprinting capacity is the largest number of 34
Watermark Forensics for Generative Models
identifiable bits per output symbol that survives such attacks, under a fidelity (distortion) budget on how far the marked copy may sit from the original. The result we use (Moulin, 2008; Somekh-Baruch and Merhav, 2005) is that this capacity tends to 0 as the budget tightens, which is exactly the “couples to the budget” phenomenon. We invoke only its degenerate, collusion-free (c = 1) case, where the worst-case collusion channel disappears and the bound is the plain Fano inequality (Fact 2.12) applied to I(U ; X) under the budget. Channels with memory, information density, and mixing. A channel “with memory” is one whose output at position i may depend on the entire past, not just the current input (as an autoregressive language model p(x,y) does). The information density i(x; y) = log p(x) p(y) is the log-likelihood ratio whose expectation is the mutual P information; a channel is information-stable when the normalised density n1 i i(Xi ; Yi | past) concentrates around a constant (a law of large numbers for information), and a sufficient condition is that the source is strongly mixing, i.e. its correlations decay with distance. For information-stable channels the Shannon coding theorem still holds: roughly nC message bits decode reliably at blocklength n, where C is the capacity (Verdú and Han, 1994). Exponential tilt and Jensen–Shannon divergence. An exponential tilt of a distribution p is a oneparameter reweighting p+ (x) ∝ p(x) eθ ϕ(x) that shifts p in a chosen direction ϕ while letting us dial its KL distance to p continuously from 0 up to the target ∆ we need. The Jensen–Shannon divergence JSD(p, q) = 1 1 1 2 KL(p ∥ m)+ 2 KL(q ∥ m) with m = 2 (p+q) is a symmetric, bounded divergence; it equals the mutual information between a fair coin choosing p or q and the resulting sample, and so is the per-token information rate of our tilting code. (For Assumption 2.2, “distortion-free” or “undetectable” means the key-averaged law equals the natural one, p̄ = pnat , so no key-blind test beats chance; the recoverable signal is then limited by the generation entropy rather than by a distortion budget.) Fact C.1 (Level-0 detection rate; Cai et al., 2024; Huang et al., 2023; Li et al., 2025b). Under the standard independent/stationary-token detection model with per-token budget ∆, the √ optimal detector achieves target error δ at ndet = Θ(log(1/δ)/∆), and the single-step detectability floor is 1 − 1 − e−D at per-step divergence D (Cai et al., 2024, Prop. 3.1). We use only the monotone consequence that detection error → 0 as n∆ → ∞. Fact C.2 (Distortion-constrained fingerprinting converse; Moulin, 2008; Somekh-Baruch and Merhav, 2005). The capacity of a fingerprinting/watermarking channel under a fidelity constraint tends to 0 as the constraint tightens; equivalently, identifying one of N users from a length-n output costs Ω(log N / (per-symbol fidelity budget)). The single-user, collusion-free case is Fact 2.12 applied to I(U ; X) under the budget, which is the only case we invoke. Fact C.3 (General channel capacity; Verdú and Han, 1994). For an information-stable channel with memory, the capacity equals limn n1 supPX n I(X n ; Y n ), and reliable decoding of M messages is possible at blocklength P n once log M ≤ (1 − o(1))nC; the information density n1 i i(Xi ; Yi | past) concentrates under stationarity and mixing.
C.2
The forensic-recovery budget
Theorem 3.1 (Forensic-recovery budget). Let a keyed scheme generate X ∈ Σn from a secret S via a key K = K(S), and set Φ(n) := I(S; X) = supg I(S; g(X, κ) | κ) (informed decoders, registry-conditional per the convention of Section 2). Then (a) under Assumption 2.1, Φ(n) ≤ n∆; (b) under Assumption 2.2 with statistical undetectability, Φ(n) ≤ nhn (hn ↓ h for stationary sources; asymptotic statements may use h); and P (c) under the footprint cap E(m) of Section 2, with marked set T (|T | ≤ m), Φ(n) = t∈T ν(t) ≤ m log q (Proposition 2.6(iii)). In particular every Level-1 and Level-2 procedure recovers at most Φ(n) nats about the secret, irrespective of N or ℓ.
35
Watermark Forensics for Generative Models
Proof. Idea. Everything the carrier reveals about the secret passes through the key, and the golden formula prices that information against any reference law; choosing the natural law turns the price into the distortion budget, while choosing the source itself turns it into the entropy ceiling. Since X depends on the secret S only through the key K = K(S), the chain S → K → X is Markov. All quantities are read conditionally on the registry κ (Section 2); given κ the secret determines its enrolled key, so d¯ below is the realized per-key distortion and the sums over S range over the N enrolled keys (the realized key-mixture is p̂κ ; p̄ = Eκ p̂κ stays the unconditional marginal). The data-processing inequality (Fact 2.11) gives Φ(n) = I(S; X) ≤ I(K; X) (mutual informations conditional on κ throughout). For any distribution Q on Σn , X X EK KL PX|K ∥ Q = EK PX|K (x) log PX|K (x) − p̂κ (x) log Q(x), x
x
since EK PX|K (x) = p̂κ (x). The second term is the cross-entropy H(p̂κ , Q), minimized over Q at Q = p̂κ (Gibbs’ inequality), and the minimum value makes the right-hand side equal to I(K; X); this is the golden formula of Fact 2.11, and in particular, for every fixed Q, I(K; X) ≤ EK KL PX|K ∥ Q . (C.1) (a) Put Q = pnat in (C.1): under Assumption 2.1, pushing the key average through to the secret and applying the chain rule for relative entropy, n X ¯ I(K; X) ≤ EK KL p(K) = ES KL(pwm (· | S) ∥ pnat ) = d(t) ≤ n∆, wm ∥ pnat t=1
¯ ≤ ∆ (indeed only P d(t) ¯ ≤ n∆); with the data-processing step which uses only the avg-form cap maxt d(t) t Φ(n) ≤ n∆. (b) Working conditionally on κ, mutual information never exceeds a conditional entropy, and conditioning on κ only reduces entropy; under Assumption 2.2 p̄ = pnat , so Φ(n) = I(S; X | κ) ≤ I(K; X | κ) ≤ H(X | κ) ≤ H(X) = H(p̄) = H(pnat ) = nhn , the step H(X | κ) ≤ H(X) being the Jensen (concavity-of-entropy) bound Eκ H(p̂κ ) ≤ H(Eκ p̂κ ) = H(pnat ) on P (k ) (n) the realized key-mixture p̂κ := N1 v pwmv (Section C.6), and hn := H(pnat )/n is the finite-n entropy (hn ↓ h for stationary sources, so asymptotic statements may use the rate h). (c) Under E(m) the per-secret kernels equal the natural ones off T , so Xt ⊥ S | X<t for every t ∈ / T and ν(t) = I(S; Xt | X<t ) = 0 there (Proposition 2.6(iii); conditioning on the full past screens autoregressive propagation). P The chain rule then gives Φ(n) = t ν(t) = ν(T ), and each remaining term is at most H(Xt | X<t ) ≤ log q, whence Φ(n) ≤ |T | log q ≤ m log q. Scope of (b). The entropy bound Φ ≤ H(X) needs no undetectability assumption, but the evaluation H(X) = nhn uses statistical undetectability p̄ = pnat . Computational undetectability gives no two-sided entropy bound: for pnat = Unif({0, 1}n ), a pseudorandom generator with seed length s = polylog(n) has output ≈c pnat yet entropy ≤ s ≪ nh. Computationally undetectable schemes (Christ–Gunn, PRC) are therefore governed by seed entropy, not nhn .
C.3
Attribution converse and the forensic gap
Theorem 3.2 (Attribution converse and the forensic gap). Under Assumption 2.1, for N ≥ 2 and any attribution rule, n∆ + log 2 , (3.1) Pe ≥ 1 − log N so natt = Ω(log N/∆). Moreover, suppose the scheme is mixture-detectable: the key-unknown test of p̄ against pnat reaches vanishing error by some length nmix det (in the stationary-token model a positive per-token mixture divergence n1 KL(p̄ ∥ pnat ) ≥ c > 0 suffices). Then for all sufficiently large N , on the window
36
Watermark Forensics for Generative Models
nmix det ≤ n < (1 − η) log N/∆ the watermark is detectable with error → 0 while every attribution rule has Pe ≥ η − o(1). (k ) Proof. Converse. Apply Theorem 3.1(a) with S = U ∼ Unif[N ]: each KL pwmu ∥ pnat ≤ n∆, so I(U ; X) ≤ n∆. Fano’s inequality (Fact 2.12), together with H(U | X) = H(U ) − I(U ; X) = log N − I(U ; X) ≥ log N − n∆, gives log N − n∆ ≤ H(U | X) ≤ log 2 + Pe log N, which rearranges to the converse Pe ≥ 1 −
n∆ + log 2 . log N
The bound is non-trivial once n∆ < log N − log 2, giving natt = Ω(log N/∆). This is the single-user case of the distortion-constrained fingerprinting converse of Moulin (2008); Somekh-Baruch and Merhav (2005) (Fact C.2), specialized to the per-token KL channel. Forensic gap. Call the scheme mixture-detectable if the key-unknown likelihood-ratio test of p̄ against pnat has error → 0 as n → ∞, and write nmix det for the length at which it does. In the stationary-token model this is implied, when p̄ is ergodic, by a positive per-token mixture divergence n1 KL(p̄ ∥ pnat ) ≥ c > 0: by the relative-entropy (Shannon–McMillan–Breiman) theorem (Fact 2.13(ii)) the normalised log-likelihood ratio 1 n log(p̄/pnat ) concentrates at a positive rate under p̄ and a negative rate under pnat , so the likelihood-ratio test separates the hypotheses with vanishing error. (For a non-ergodic key-mixture p̄ one needs the divergence rate positive on every ergodic component; a component that coincides with pnat would leave a constant miss probability.) (We do not use the i.i.d. Chernoff–Stein lemma applied to a single length-n sample, for which a diverging KL alone would not force the error to 0.) On the window nmix det ≤ n < (1 − η) log N/∆, log N +log 2 detection error → 0 while n∆ < (1 − η) log N , so the converse gives Pe ≥ 1 − (1−η) log = η − o(1). N mix ⋆ mix The window is non-empty when log N = ω(∆ ndet ). At n = ⌈log log N/∆⌉ (assumed ≥ ndet , so detection still succeeds), I(U ; X) ≤ n⋆ ∆ ≤ log log N + ∆ = log log N + O(1) (∆ a fixed per-scheme constant), whence Pe ≥ 1 − log loglogNN+O(1) → 1. Necessity of mixture-detectability. The hypothesis c > 0 is not free. The parity scheme on Σn = {0, 1}2 with (0)
(1)
(b)
two keys, pwm = Unif{x : x1 ⊕ x2 = 0} and pwm = Unif{x : x1 ⊕ x2 = 1}, has KL pwm ∥ pnat = log 2 (within (0)
(1)
budget) yet p̄ = 12 (pwm + pwm ) = Unif({0, 1}2 ) = pnat exactly, so the key-unknown detector is blind. For such (distortion-free) schemes “detectable but not attributable” is automatic, not a separation.
C.4
Two quality models
Theorem 3.3 (Two quality models). For attribution among N users and ℓ-bit extraction: (a) (Distributional cap couples.) Every scheme in B(∆) has natt = Ω(log N/∆) and next = Ω(ℓ/∆). These are achieved, with natt = Θ(log N/∆) and next = Θ(ℓ/∆), when pnat is memoryless, or regular (pnat (· | past) ≥ p0 > 0) and strongly mixing; for general q-ary pnat the matching upper bound is conjectural. (b) (Footprint cap decouples.) There is a scheme in E(m) achieving natt = Θ(log N/ log q), next = Θ(ℓ/ log q) at m = Θ(log N/ log q), with no dependence on any per-token cap. In a carrier of length P ¯ n ≫ natt the footprint fraction m/n → 0 (and the aggregate distortion n−1 t d(t) → 0 when pnat is regular, pnat (· | past) ≥ p0 > 0): imperceptibility comes from the vanishing footprint, not a per-token bound. The localization map makes E(m) available: a scheme in E(m) has localization map T (Corollary 3.4), and a biasing scheme (no localization map) cannot lie in E(m) for m = o(n), so under a quality constraint it is confined to B(∆) and pays the coupled cost (a).
37
Watermark Forensics for Generative Models
Proof. Idea. The lower bound is the budget once more: B(∆) caps the mass at n∆, so attribution needs n ≳ log N/∆. The two upper bounds spend that mass in the two extremal shapes, thin-and-wide (a tilting code on every token) and tall-and-narrow (the digit stamp on a few). P (k) (k) (k) Write di for the per-key conditional distortions, so i di = KL pwm ∥ pnat by the chain rule for relative entropy. (a) Lower bound. A scheme every per-secret conditional within ∆ at every prefix) has in B(∆)(sup-form: P (k) (k) (k) di ≤ ∆ for every i, k, so KL pwm ∥ pnat = i di ≤ n∆ and Theorem 3.2 applies (the converse needs only this avg-form consequence), giving natt = Ω(log N/∆); the ℓ-bit version replaces U ∼ Unif[N ] with W ∼ Unif{0, 1}ℓ in Fano, giving next = Ω(ℓ/∆). (i) (a) Upper bound (conditional tilting code). Fora fixed ∆, let p+ (· | x<i ) be the order-preserving exponential tilt (i)
(i)
of the natural conditional pnat (· | x<i ) with KL p+ ∥ pnat = ∆. Assign user u an i.i.d. codeword cu ∈ {0, 1}n ; (i)
generate Xi ∼ p+ (· | X<i ) when cu [i] = 1 and Xi ∼ pnat (· | X<i ) otherwise. By the KL chain rule the total distortion is exactly (#{i : cu [i] = 1}) ∆ ≤ n∆ for any autoregressive pnat , so the scheme lies in B(∆) (each token within ∆). The induced per-position channel cu [i] 7→ Xi (conditioned on the past) has mutual (i) (i) information E JSD(p+ , pnat ) = Θ(∆); under a mild mixing assumption on pnat the conditional information P 1 density n i i(cu [i]; Xi | X<i ) concentrates, and the general channel-with-memory coding theorem (Verdú–Han, Fact C.3) gives reliable maximum-likelihood decoding of N codewords once n = Θ(log N/∆). The same code carries ℓ message bits, giving next = Θ(ℓ/∆). (b) Footprint upper bound (the stamp). Let m = ⌈log N/ log q⌉ and Lk (x) = {1, . . . , m}. Encode u ∈ [N ] by its m base-q digits and set X1 , . . . , Xm to those digits; generate Xm+1 , . . . , Xn ∼ pnat . Then the per-secret kernels for i > m are exactly natural, so the scheme is in E(m) with marked set T = {1, . . . , m}, and the extractor reading X1:m recovers u with zero error, so Φ = log N and the region has size m = Θ(log N/ log q), independent of any per-token cap. Fidelity holds by the footprint m/n → 0; if a KL reading is wanted, assuming pnat (digiti | past) ≥ p0 > 0 gives total distortion ≤ m log(1/p0 ), an n-independent constant, so the average per-token distortion → 0. The ℓ-bit version forces ⌈ℓ/ log q⌉ positions. Corollary 3.4 (Footprint forces localization). Let the scheme lie in E(m) with marked set T , |T | ≤ m. Then ν = 0 off T , so I(S; X) = ν(T ); the likelihood’s dependence on s factors through the pairs ((x<t , xt ))t∈T , so X≤max T is a sufficient statistic for S; and when T is a prefix (as for the stamp) this is the exact Markov chain S → XT → X. Thus Lk := T localizes the mark. The converse fails: a scheme in E(m) that also ¯ ≤ ∆ (which suffices, since ν(t) ≤ d(t); ¯ obeys the avg-form cap maxt d(t) the sup-form implies it) still needs m ≥ (1 − o(1)) log N/∆ marked coordinates — localization does not buy ∆-freeness. Proof. In E(m) the per-secret kernels off T are natural, so the likelihood factorizes as Y Y pwm (x | s) = pwm (xt | s, x<t ) · pnat (xt | x<t ), t∈T
t∈T /
and the ratio pwm (x | s)/pnat (x) = t∈T pwm (xt | s, x<t )/pnat (xt | x<t ) depends on s only through the pairs ((x<t , xt ))t∈T . By the factorization criterion, X≤max T is a sufficient statistic for S; and ν = 0 off T (Proposition 2.6(iii)) gives I(S; X) = ν(T ). When T is a prefix {1, . . . , m} (the stamp), sufficiency is exactly the Markov chain S → XT → X. (For general T the chain S → XT → X can fail: the readout needs the conditioning prefixes, i.e. X≤max T , not XT alone.) In all cases Lk := T localizes the mark: the s-dependence of the likelihood lives on T , read conditionally on the (natural) prefix. ¯ ≤ ∆ (which the sup-form implies). Converse leg. Suppose the scheme also satisfies the avg-form cap maxt d(t) ¯ ≤ ∆ at every t (ν(t) ≤ d(t) ¯ by the golden formula; cf. Proposition 2.6(ii)), so vanishing-error Then ν(t) ≤ d(t) attribution forces, by Fano, (1 − o(1)) log N ≤ I(U ; X) = ν(T ) ≤ m∆, i.e. m ≥ (1 − o(1)) log N/∆: localization does not buy ∆-freeness — dropping the per-token cap does. Q
38
Watermark Forensics for Generative Models
C.5
Level 3: footprint–resolution and the rate region
Theorem 3.12 (Footprint–resolution uncertainty). Under Assumption 2.3, any w-crop-robust scheme has dilated support R+ meeting every length-w window; since |R+ | ≤ (2r + 1)|R|, its carrier footprint |R| obeys |R| w ≥
n−w+1 , 2r + 1
i.e.
|R| w = Ω(n) (r = O(1)),
the Ω(n) reading trivial for w > n/2 (a nonempty R already gives |R| w > n/2). For a scheme in E(m) whose natural law factorizes across positions (in particular i.i.d.; the post-hoc regime of Assumption 2.3) one may take R = T , so |R| ≤ m and the bound reads m w = Ω(n). Consequently (i) a small-footprint embedding scheme (m = o(n), hence |R| = o(n)) is crop-robust only at coarse resolution w = ω(1), and (ii) constant-resolution crop-robustness forces |R| = Ω(n), i.e. full support, that is, biasing. Moreover (iii) under Assumption 2.1, for a natural law that factorizes across the length-w blocks (in particular i.i.d., and the whitened regime of the post-hoc schemes Assumption 2.3 targets), w-crop-robust localization (naming the window among the Θ(n/w) blocks from xW alone) requires w∆ ≥ (1 − o(1)) log(n/w). Proof. Idea. A crop window disjoint from the dilated footprint sees only unmarked text and cannot detect, so the footprint must meet every length-w window; a set meeting every window cannot be too sparse, which lower-bounds its size. (a)/(b). Let R+ = {i : dist(i, R) ≤ r} be the dilated support, |R+ | ≤ (2r + 1)|R|. Suppose a length-w window W is disjoint from R+ . By the coupling of Assumption 2.3, the marked carrier agrees on W with an unmarked carrier X ′ ∼ pnat , so xW = x′W has law exactly pnat ; a detector observing only xW then tests pnat against pnat and cannot exceed chance, contradicting w-crop-robust detection. Hence every length-w window meets R+ . There are n − w + 1 such windows, and a single element i lies in at most w of them (those starting in [i − w + 1, i]), so |R+ | ≥ (n − w + 1)/w, tight for R+ = {w, 2w, . . . }. Combining with |R+ | ≤ (2r + 1)|R| gives |R| w ≥ (n−w+1)/(2r+1), i.e. |R| w = Ω(n) for r = O(1) (for w > n/2 a nonempty R gives |R| w > n/2 directly); for a scheme in E(m) whose natural law factorizes across positions, the off-T kernels are prefix-independent, an exact r = 0 coupling with R = T exists, and the bound reads m w = Ω(n) (for correlated sources an R = T coupling can fail to exist: a scheme stamping one symbol of a perfectly correlated source is w-crop-robust for every w with |T | = 1, and is excluded exactly because its carrier footprint under any valid coupling is Ω(n), not |T |). (i) and (ii) are the regimes |R| = o(n) (in particular m = o(n) under E(m)) and w = O(1). (c). Here we take pnat to factorize across the length-w blocks (the i.i.d. / whitened regime; the general correlated case is discussed below). Partition [n] into Nw = ⌊n/w⌋ disjoint length-w blocks W1 , . . . , WNw ; crop to a uniformly random block J ∼ Unif[Nw ]. Crop-robust localization must output J from xWJ alone, so by Fano (Fact 2.12) I(J; xWJ ) ≥ (1 − o(1)) log Nw . For the upper bound, (Fact 2.11) with the common the golden formula W natural block law pW nat as reference gives I(J; xWJ ) ≤ EJ KL PxWJ |J ∥ pnat . Because pnat is block-independent, its within-block conditionals coincide with the full-prefix conditionals, soby the chain rule over the block and joint P convexity of relative entropy each block term obeys KL PxWJ |J ∥ pW nat ≤ i∈WJ di (the marked within-block
(K) ¯ of the natural conditional conditional, with its pre-block prefix marginalized, stays within di := EK di = d(i) by convexity). Hence X 1 X n∆ I(J; xWJ ) ≤ EJ di = di ≤ = w∆, Nw Nw i∈WJ
i∈[n]
using only the global budget i di ≤ n∆ of Assumption 2.1 (avg-form), not a per-token cap. Combining, log Nw ≤ (1 + o(1)) w∆, i.e. w∆ ≥ (1 − o(1)) log(n/w). The block-independence hypothesis is load-bearing. For a correlated pnat the cropped block xWJ marginalizes P W out its pre-block prefix, and KL PxWJ |J ∥ pnat need not be bounded by i∈WJ di : the divergence of the cropped block against the stationary block law can exceed the prefix-conditioned per-token budget actually spent there (a binary first-order Markov source already exhibits this). The conclusion I(J; xWJ ) ≤ w∆ nonetheless held throughout a numerical search over correlated stationary sources and localizing schemes (the ratio I/(w∆) P
39
Watermark Forensics for Generative Models
peaking at 1, attained at the i.i.d. point), so we expect the relation to be general; a tight proof for correlated pnat is left open. Proposition 3.13 (Forensic rate region). Under Assumption 2.1 and in the regime n∆ → ∞, with Ratt = log N and Rext = ℓ log 2: (a) (Converse.) vanishing-error attribution and extraction force Ratt + Rext ≤ (1 + o(1)) n∆; (b) (Achievability.) for regular, strongly-mixing pnat (general q-ary conjectural, inheriting Theorem 3.3(a)), every pair with Ratt + Rext ≤ (1 − o(1)) nC is achieved by one multiplexed conditional tilting code, where C = Θ(∆) is the per-token channel capacity. Thus the achievable region is a slope-−1 simplex whose boundary is order-tight, Θ(n∆): it lies between nC and n∆, which agree up to the capacity constant (C ≈ ∆/4 in the binary witness of Section 3.6). The corners carry no extra loss. Proof. Converse. With S = (U, W ) and U ⊥ W , the chain rule and Theorem 3.1(a) give I(U ; X) + I(W ; X | U ) = I(U, W ; X) ≤ n∆. Vanishing-error attribution forces I(U ; X) ≥ (1 − o(1)) log N by Fano (Fact 2.12), and vanishing-error extraction forces I(W ; X | U ) ≥ (1 − o(1))ℓ log 2 (Fano applied to W ∈ {0, 1}ℓ conditioned on each value of U and averaged); adding, Ratt + Rext ≤ (1 + o(1)) n∆. Achievability. Concatenate the user identity and the payload into a single message of Ratt + Rext nats and transmit it with the conditional tilting code of Theorem 3.3(a), whose per-token capacity is C = Θ(∆). Under the regularity/mixing hypothesis the information density concentrates, so reliable decoding holds once nC ≥ (1 + o(1))(Ratt + Rext ); the decoder splits the recovered message into (Û , Ŵ ).
C.6
Proof of Theorem 3.6
Theorem 3.6 (Distortion-free attribution is Θ(log N/h)). Let pnat be stationary ergodic with entropy rate h > 0 (no mixing hypothesis), marked and decoded as in Definition 3.5. Fix a per-innocent false-positive level δ ∈ (0, 12 ) and let N → ∞ (optionally δ → 0 with log(1/δ) = o(log N ) for the (1 + o(1)) form). Then attribution among N users costs natt = Θ(log N/h) (achievability alone holding for all δ ∈ (0, 1)), sharpening to (1 + o(1)) log N/h, and: (i) (False positives; exact, non-asymptotic.) For every n and arbitrary pnat (no ergodicity used): for the deterministic sampler of Definition 3.5, a fixed innocent v is the key returned only with probability Pr[Û = v] ≤ e−τ = δ/N , pointwise in the realized innocent keys (the probability is over the true text X ∼ pnat ); for randomized distortion-free kernels the same bound holds averaged over the key draw. (ii) (Completeness.) Pr[ı(X) > τ ] → 1 whenever n ≥ (1+α)τ /h for any fixed α > 0 (Shannon–McMillan– Breiman; here h is the entropy rate). (iii) (The rate, two-sided.) Achievability: the average error is ≤ δ + o(1) once n ≥ (1 + α)(log N + log(1/δ))/h, for every fixed α > 0 (N large). Converse: for i.i.d. keys, every attribution rule with error (n) ≤ 2δ needs n ≥ (1 − 2δ) log N/hn − O(1/h), with hn := H(pnat )/n (= (1 + o(1))h) — conditional Fano discharged by a mixture-entropy step (Section C.6). Thus natt = Θ(log N/h) for fixed δ ∈ (0, 21 ), log N natt = (1 + o(1)) as δ → 0, log(1/δ) = o(log N ). h For a fixed deployed key set the converse instead holds under a mixture-entropy hypothesis on the realized keys (as N → ∞; automatic when pnat is the maximum-entropy law), detailed in Section C.6.
40
Watermark Forensics for Generative Models
Proof. Idea. The true text is pnat -typical, so its surprisal clears any sub-h threshold (completeness, by SMB); an innocent key’s string is itself pnat -distributed, so it coincides with the typical text only with pnat -mass ≤ e−τ (soundness, a change of measure). The threshold τ = log(N/δ) is what balances the two sides. Throughout, the true user’s key makes the text law exactly pnat (the inverse-CDF sampler is distortion-free: marginally over the key, X ∼ pnat ). Consistency of a key kv with a text X means that kv (t) lands in the realized token’s quantile cell of pnat (· | X<t ) at every t; for the deterministic sampler this says exactly X(kv ) = X, where X(kv ) is the single string key kv generates. (i) False positives, pointwise version (deterministic sampler). Fix the realized innocent keys. Each innocent kv determines one string X(kv ), and Û = v requires X = X(kv ) and ı(X) > τ . The only randomness left is the true text X ∼ pnat , so Pr[Û = v] = pnat X(kv ) 1{ı(X(kv )) > τ } ≤ e−τ = δ/N, since on {ı > τ } we have pnat = e−ı < e−τ pointwise. This holds for every realized key set (no averaging over the key draw) and for arbitrary pnat (no ergodicity), at every n. (i′ ) Averaged version (randomized distortion-free kernels). Given X, an independent wrong key kv is consistent Q with probability t pnat (Xt | X<t ) = pnat (X) = e−ı(X) (each kv (t) must land in the realized token’s quantile cell, and kv (t) ∼ Unif[0, 1] independently). Hence X X pnat (X)2 ≤ e−τ pnat (X) = e−τ . Pr[Û = v] ≤ EX∼pnat e−ı(X) 1{ı(X) > τ } = X: pnat (X)<e−τ
X
This is the watermark-forensics instance of the folklore likelihood-ratio Markov bound Prpnat [log(P kv /pnat ) > τ ] ≤ e−τ (Barron-style change of measure): for any randomized distortion-free kernel only the key-averaged bound survives, which is how the “any scheme” reading must be scoped. (ii) Completeness. The true key is always consistent, so the decoder finds U iff ı(X) > τ . By the Shannon– McMillan–Breiman theorem (Cover and Thomas, 2006), ı(X)/n → h almost surely for stationary ergodic pnat ; at n ≥ (1 + α)τ /h we have τ /n ≤ h/(1 + α) < h, so Pr[ı(X) > τ ] = Pr[ı(X)/n > τ /n] → 1. Quantifier order. Completeness needs τ /n bounded away from h: with δ fixed and N → ∞ this holds along n = (1 + α)τ /h with the o(1) uniform; for jointly δ → 0 one needs log(1/δ) = O(log N ), keeping τ = Θ(log N ) — this is the asymptotic regime stated in the theorem. P (iii) Rate. Combining, the average error is at most Pr[ı ≤ τ ] + v̸=U Pr[Û = v] ≤ o(1) + N · δ/N = δ + o(1) at n = (1 + α)(log N + log(1/δ))/h, any fixed α > 0. P (k) (iii) Converse. Write P k := pwm for the marked law under key k, and p̂κ := N1 v P kv for the realized N -key mixture given the key set κ = {k1 , . . . , kN }; each P kv is a random measure with E[P kv ] = pnat (the sequence-level condition p̄ = pnat ; for the witness this follows from the kernel-level form because its keys are i.i.d. across positions, so inverse-CDF sampling is distortion-free at the sequence level, cf. Assumption 2.2), and since the keys are i.i.d., Eκ [p̂κ ] = p̄ = pnat . Condition on the realized key set κ: U ∼ Unif[N ] and X ∼ P kU ; since U ⊥ κ and U ∼ Unif[N ], the κ-conditional marginal of X is p̂κ , so H(X | κ) = H(p̂κ ) and I(U ; X | κ) ≤ H(X | κ) = H(p̂κ ). Fano (Fact 2.12) at each κ gives Pe (κ) ≥ 1 − (I(U ; X | κ) + log 2)/ log N ; averaging over the i.i.d. key draw (by concavity of entropy and Jensen, Eκ H(p̂κ ) ≤ H(Eκ p̂κ ) = H(pnat ) = nhn ; the inequality is textbook and we claim only its use) Pe = Eκ Pe (κ) ≥ 1 −
nhn + log 2 Eκ I(U ; X | κ) + log 2 ≥ 1− . log N log N
Any rule with error ≤ 2δ (the threshold decoder achieves ≤ δ+o(1)) therefore needs n ≥ (1−2δ) log N/hn −O(1/h). Two symbols do the bookkeeping here: completeness (ii) uses the entropy rate h via Shannon–McMillan–Breiman, (n) while the converse uses the finite-n quantity hn = H(pnat )/n exactly; for stationary sources hn ↓ h, so nhn = (1 + o(1))nh and the two sides meet asymptotically. Since α > 0 is arbitrary, natt = Θ(log N/h) for every fixed δ ∈ (0, 21 ) (achievability alone holds for all δ ∈ (0, 1); the converse coefficient 1 − 2δ needs δ < 12 ); letting δ → 0 with log(1/δ) = o(log N ) squeezes the two sides together, natt = (1 + o(1)) log N/h, closing the column. Fixed-key variant. For a fixed deployed key set κ the averaging step is unavailable; I(U ; X) ≤ H(p̂κ ) still holds, and under the carried hypothesis H(p̂κ ) ≤ nhn + o(log N ) (the slack o(log N ) as N → ∞) the same Fano computation gives Pe ≥ 1 − (nhn + o(log N ) + log 2)/ log N , hence natt = Ω(log N/h) and, with W ∼ Unif{0, 1}ℓ in place of U , next = Ω(ℓ/h). (When pnat is the maximum-entropy law the hypothesis is automatic.) 41
Watermark Forensics for Generative Models
Corollary 3.7 (Payload extraction). Index N = 2ℓ keys by the payload W ∼ Unif{0, 1}ℓ . Under the hypotheses of Theorem 3.6, next = Θ(ℓ/h) for fixed δ, and next = (1 + o(1)) ℓ log 2/h as δ → 0 with log(1/δ) = o(ℓ). Proof. Identify the payload W ∼ Unif{0, 1}ℓ with U ∼ Unif[N ] for N = 2ℓ , so log N = ℓ log 2 nats. Theorem 3.6 gives next = Θ(ℓ/h) for fixed δ, and next = (1 + o(1)) ℓ log 2/h as δ → 0 with log(1/δ) = o(ℓ).
C.7
The overlap identity and the candidate list
Lemma C.4 (Scheme-independent collision identity). For any statistically distortion-free scheme satisfying the kernel-level condition Ek∼µ p(x | k, x<t ) = pnat (x | x<t ) for every prefix x<t and every x (randomized kernels included), and independent keys k, k ′ ∼ µ, hX i X Ek,k′ p(x | k, x<t ) p(x | k ′ , x<t ) = pnat (x | x<t )2 . x
x
The expected pairwise per-token overlap is therefore invariant across all distortion-free schemes. Proof. For independent k, k ′ , E[AB] = E[A] E[B] termwise in x; then apply the kernel-level distortion-free condition twice. For the inverse-CDF witness of Theorem 3.6 the kernels are point masses given the prefix, and the identity P P ′ is also a direct sequence-level computation: Ek,k′ X P k (X)P k (X) = X pnat (X)2 . With an i.i.d. source, P P 2 −nr2 where r2 := − log x∈Σ pnat (x)2 is the Rényi-2 rate, so the expected number M of falsely X pnat (X) = e consistent keys is X E[M ] = (N − 1) EX∼pnat [pnat (X)] = (N − 1) pnat (X)2 = (N − 1) e−nr2 , X
which is the exponentially large candidate list of Proposition 3.9 in the window log N/h ≤ n ≪ log N/r2 . Abstain-on-tie has zero false positives (closed world). The rule outputs v only when v is the unique consistent key. A false positive requires a wrong v to be uniquely consistent; but the true key is always consistent with the text it generated — contradiction. Hence FP = 0 exactly, at every n and every source, within the closed-world model U ∈ [N ]; on out-of-set text (no true key present) the argument vanishes. Its completeness EX [(1 − pnat (X))N −1 ] → 1 at the threshold (1 + o(1)) log N/h is supported numerically and is not claimed as a theorem; Theorem 3.6 does not use it.
C.8
Two definitional witnesses: why the per-secret recut is necessary
The v2 definitions of Section 2 state the quality caps on the per-secret kernels pwm (· | s, x<t ), not on the keyaveraged marginal distortion profile. Two two-token examples show that the marginal profile and the information profile disagree in both directions, so the recut is forced, not cosmetic. Parity (marginal δ ≡ 0, yet ν(2) = log 2). On Σ = {0, 1}, n = 2, pnat = Unif({0, 1}2 ), secret S ∼ Unif{0, 1} (s) with pwm = Unif{x : x1 ⊕ x2 = s}. The key-averaged law is p̄ = Unif({0, 1}2 ) = pnat exactly, so the marginal pertoken distortion vanishes at both positions, and a key-averaged footprint reading would place the scheme in E(0) — absurd, since Φ = I(S; X) = log 2: given X1 , the token X2 determines the parity, so ν(2) = I(S; X2 | X1 ) = log 2. Per-secret, the kernel at t = 2 is a point mass ̸= Unif, so t = 2 is marked, as it must be. Kernel bend (marginal δ2 > 0, yet ν ≡ 0). Same Σ, n = 2, pnat = Unif; every secret generates X1 ∼ Unif{0, 1} and then X2 ∼ Ber(3/4), regardless of S. Then δ2 = KL(Ber(3/4) ∥ Ber(1/2)) > 0 while X ⊥ S, so ν ≡ 0: position 2 carries distortion but no secret. Distortion support does not certify information. Together: the marginal profile both under-counts (parity) and over-counts (bend) the secret-bearing positions, ¯ by the golden formula and δ marg (t) ≤ d(t) ¯ by while the per-secret profile d¯ dominates both (ν(t) ≤ d(t)
42
Watermark Forensics for Generative Models
joint convexity of KL), which is what makes the v2 caps sound and the screening property supp(ν) ⊆ T (Proposition 2.6(iii)) a theorem rather than a convention.
D
How deployed watermarks fit the framework
We now place each scheme of Table 2 inside the model of Section 2: we identify its per-secret footprint T (hence its side of Definition 2.4), the quality model it obeys (Assumption 2.1 or Assumption 2.2, or the footprint cap E(m)), its readout resolution, and the forensic levels it reaches. The recurring lesson is that almost every deployed scheme is biasing: full-support, and localizing (when it does) by fine readout rather than by a small footprint.
D.1
Language-model watermarks
Green-list (Kirchenbauer et al., 2023). At each step the key hashes the previous token to split the vocabulary into a green/red list and adds a fixed logit bias toward green; detection counts green tokens. Every token’s conditional is tilted under every key, so the per-secret footprint is T = [n] and the scheme is biasing (Definition 2.4) under the bounded-distortion model B(∆), with ∆ the per-token green-bias divergence. Readout is global (one green-fraction statistic), so it reaches Level 0 and, in its multi-bit and many-user descendants, Levels 1–2, but not crop-robust Level 3. Its secret is recoverable from a long window, which is why the support, not a read-from criterion, is the right cut (Section 2). Unigram-Watermark (Zhao et al., 2024). The context-width-1 ablation of green-list: a single keydetermined global green list (no context hashing), a fixed logit bias toward it, and a one-proportion z-test on the green count. Every token’s conditional is tilted under every key, so T = [n]: biasing under B(∆), global readout, Level 0. Its contribution is a provable edit- and paraphrase-robustness guarantee, and the fixed list buys it by making the mark maximally delocalized: robustness here is redundancy of a full-support mark, not a small footprint. SynthID-Text (Dathathri et al., 2024). Tournament sampling reweights the next-token distribution through keyed elimination rounds; in its non-distortionary mode the key-averaged law is the model’s own, p̄ = pnat . It is therefore biasing in the distortion-free regime (Assumption 2.2): full support, global readout, Level-0 (zero-bit) detection. Distribution-preserving reweighting (Hu et al., 2024; Wu et al., 2024). DiPmark and the unbiasedwatermark family reweight the next-token distribution by a key-conditioned function whose key-average is the identity: EK pwm (· | K, x<t ) = pnat (· | x<t ) at every prefix — the kernel-level form of Assumption 2.2, not merely the sequence-level one. Under each key the reweighting touches every step, so T = [n]: biasing (d-free), global readout (a keyed score summed over the sequence), Level 0. Multi-bit watermarks (Gilani et al., 2026; Yoo et al., 2023). These carry an ℓ-bit payload by positiondependent green-lists (MPAC, bounded-distortion B(∆)) or an optimal-transport coupling (ArcMark, distortionfree, Assumption 2.2); either way the mark perturbs every token’s per-secret conditional, so T = [n] and the scheme is biasing, with bucketed (per-position-class) rather than fine readout. The family realises Levels 0 and 2, at the Θ(ℓ/∆) payload cost of Table 1. BiMark (Feng et al., 2025). An unbiased multilayer multi-bit scheme: a bit-flip reweighting whose keyaverage is the identity (EK pwm (· | K, x<t ) = pnat (· | x<t ), the kernel-level form of Assumption 2.2), stacked across several layers to raise detectability while preserving quality (lower perplexity). Every step is reweighted, so T = [n]: full support, biasing in the distortion-free regime. Multi-bit messages are carried by an XOR-enhanced position-allocation code, read back bit by bit from a voting matrix without the message space, so the readout is bucketed (per-position-class) rather than fine; the scheme reaches Levels 0 and 2. Being distortion-free, its payload cost is governed by the entropy column rather than a distortion budget: Corollary 3.7 caps message-agnostic ℓ-bit extraction at Θ(ℓ/h) tokens.
43
Watermark Forensics for Generative Models
Many adaptive users (Cohen et al., 2025). This construction is built generically from a distortion-free zero-bit scheme plus an erasure-robust (Boneh–Kiayias–Montgomery) fingerprinting code, inheriting full support and p̄ = pnat : biasing in the entropy regime (Assumption 2.2). It embeds a message and traces among many users, reaching Levels 0–2; its detect-short / trace-long guarantee is the achievability companion to our Level-0/Level-1 converse (Theorem 3.2). Distortion-free watermarks (Kuditipudi et al., 2023). An exponential-minimum-sampling rule (after Aaronson’s exponential-sampling proposal for GPT, Aaronson, 2022) aligns the output with a key-dependent random sequence while keeping p̄ = pnat ; the alignment signal is spread over the whole sequence. Full support, biasing (Assumption 2.2), global readout, Level 0. Its robustness to cropping is redundancy of a delocalised mark, not a small footprint. Undetectable watermarks (Christ et al., 2024). A pseudorandom signal is embedded in the high-entropy steps of generation so that, without the key, the output is computationally indistinguishable from pnat . Full support, distortion-free biasing (Assumption 2.2); the governing resource is the generation entropy (the paper certifies completeness through the empirical entropy of the realized output), and the scheme reaches Level 0. Pseudorandom error-correcting codes (Christ and Gunn, 2024). A PRC encodes a pseudorandom codeword spread across the output, decodable with the key even after bounded corruption. Full support, distortion-free biasing (Assumption 2.2); the error-correction buys robustness, not a small footprint. The language-model watermark it instantiates is zero-bit, so it reaches Level 0; multi-bit message embedding is a separate steganographic application of the same code. SemStamp (Hou et al., 2024). Sentence-level rejection sampling: a keyed locality-sensitive hash partitions a sentence-embedding space into regions, and each candidate sentence is resampled until it lands in a watermarked region; detection counts in-region sentences. The extractor’s basis is the sentence-embedding space, so the footprint is read at sentence granularity — and there every sentence’s per-secret conditional is the natural law conditioned on the keyed region, hence marked: full support, biasing under B(∆) (the per-sentence divergence is log(1/γ) for region mass γ under pnat ), global readout, Level 0. The basis change swaps tokens for sentences without shrinking the footprint’s fraction: basis-relativity (Section 4, pattern 3) in the opposite direction from Tree-Ring, for which the change of basis is what creates the o(n) object.
D.2
Image and audio watermarks
Tree-Ring (Wen et al., 2023). A ring is written into a few concentric frequency shells of the diffusion model’s initial-noise Fourier spectrum; detection inverts the generation and matches the ring. In the latent-noise spatial basis the inverse-DFT of the ring is delocalized over all noise coordinates (and the noise-to-image map is the full diffusion sampler, not a transform), so there it is full support, biasing; but in the Fourier basis of the latent the mark is an o(n) object on a handful of shells: it is embedding there, the one deployed scheme with a genuine small footprint. Its localization map is the ring’s support and its readout is global (a matched filter), so it reaches Level 0 and, with key-distinct rings, Level 1, but not spatial Level 3. This is the basis-dependence of Definition 2.4 made concrete. RingID (Ci et al., 2024). The Tree-Ring successor built for multi-key identification — Level 1 in practice, instantiated in the same latent-Fourier dictionary, the regime of Theorem 3.3(b)’s attribution question. Two verified design changes decide its classification. The ring values are discretized (each ring carries ±α rather than a draw from the Gaussian Fourier prior), so the key-averaged law on the shells is no longer natural (RingID itself documents the distribution shift this family incurs), and the d-free reading survives only partially. And to make many keys discriminable it adds a heterogeneous second component: a key-specific Gaussian noise pattern occupying an entire latent channel, read jointly with the rings by a nearest-key ℓ1 match after DDIM inversion. That channel is a constant fraction of the latent coordinates, so the per-secret footprint is Ω(n): biasing, global readout, Levels 0–1. The instructive part is the trade: the ring component alone is the deployed object closest to the small-footprint attribution of Theorem 3.3(b), and RingID buys reliable multi-key capacity precisely by leaving the embedding class.
44
Watermark Forensics for Generative Models
Gaussian Shading (Yang et al., 2024). The latent prior is replaced by a key-determined sample that is still marginally Gaussian, so the output is performance-lossless (p̄ = pnat ) while carrying a message. Full support in the latent, distortion-free biasing (Assumption 2.2), global readout; Levels 0 and 2. ROBIN (Huang et al., 2024). An explicit watermark is planted in the Fourier spectrum of an intermediate diffusion latent (around steps 200–300 of 1000), and an adversarially optimized hiding prompt-guidance signal steers the remaining generation to conceal it; verification DDIM-inverts to the embedding step and thresholds an ℓ1 distance to the planted pattern. The optimized pattern spans concentric rings covering roughly 70% of the frequency plane, so even in its own Fourier basis the footprint is Ω(n): full support, biasing under B(∆) (the optimization explicitly budgets retention against an unwatermarked anchor image, and the steered law is not pnat ), global readout, Level 0 (zero-bit). HiDDeN (Zhu et al., 2018). The classic learned image watermark and the ancestor of Stable Signature: an encoder network maps a cover image and an ℓ-bit message to a visually indistinguishable encoded image, and a jointly trained decoder recovers the message through differentiable noise layers (blur, crop, dropout, JPEG). The learned residual spans the whole image, so T is full: biasing under B(∆), global readout of one bitstring; Levels 0 and 2. Stable Signature (Fernandez et al., 2023b). The latent decoder is fine-tuned so every image it produces carries a fixed bitstring, recovered by a trained extractor. The signature perturbs the whole image’s features (full support); it is biasing under B(∆) with global readout of one bitstring, reaching Levels 0 and 2 but, lacking per-region decoding, not Level 3. SEAL (Arabi et al., 2025). A semantic locality-sensitive hash of the image is bound into the watermark and read per patch, which lets it localize tampering at high AUC where latent schemes score zero. The mark covers the whole carrier (full support, distortion-free biasing, Assumption 2.2); what reaches Level 3 is its fine readout resolution, not a small footprint, exactly as Theorem 3.12 requires of any crop-robust localizer. Levels 0–3. EditGuard (Zhang et al., 2024). A dual localization-plus-copyright watermark embeds a fragile, spatiallyindexed mark across all pixels and recovers a tamper mask from reconstruction error. Full support, biasing under B(∆), but with fine per-region readout, so it reaches Levels 0 and 3 (and carries a copyright bitstring, a Level-2 channel). AudioSeal (San Roman et al., 2024). A detector network reads a per-sample localization signal embedded throughout the waveform, flagging AI-generated segments at sample resolution. Full support, biasing under B(∆), fine readout; Levels 0 and 3 (a 16-bit message variant adds Level 2). The digit-stamp (ours). For contrast, the decoupling witness of Theorem 3.3(b) writes the secret into the first m = Θ(log N/ log q) tokens and leaves the rest natural: T = [m] with |T | = o(n), so it is genuinely embedding in token space and attributes at a ∆-free cost. It is also the only such construction here, and it is not robust to a single edit, which is precisely the gap between the information-theoretic decoupling and a deployable scheme (Section 6).
E
Additional related work
Section 5 positioned the paper against the work its theorems build on or answer. This appendix broadens the lens to recent watermarking research adjacent to the framework, read, where the connection is real, through the profile ν and the ladder. Independent and concurrent, Liu et al. (2026a) survey a related landscape under the name implicit identity, organizing fingerprinting and watermarking across datasets, models, and generated content into a lifecycle taxonomy; our contribution is orthogonal in kind, not degree: rather than taxonomize the space of mechanisms, we isolate one generation-time mark and derive exact sample-complexity rates for each forensic capability it supports. Design and detection theory for language-model watermarks. A fast-moving line treats scheme design as an optimization problem. He et al. (2025b) jointly optimize the watermarking scheme and its detector under a worst-case false-positive constraint and distortion control, with closed-form distribution-adaptive solutions,
45
Watermark Forensics for Generative Models
and Ai and He (2026) watermark over semantic clusters in embedding space with provable robustness to semantic-invariant (paraphrase) attacks; Tsur et al. (2025) cast distortion-free design for low-entropy generation (code, structured output) as optimal transport, the regime where the entropy column prices attribution most dearly (h small makes log N/h large); Zhao et al. (2025b) design a decoder (Permute-and-Flip) with a provably better quality–stability trade-off and a Gumbel-analogous watermark tailored to it; and Gloaguen et al. (2026a) give the first watermark for diffusion language models, whose arbitrary-order generation is a carrier process our autoregressive profile does not directly cover (re-cutting ν for order-agnostic generation is a natural extension). Liu et al. (2026b) move the marking capability from the sampler to the prompt itself; in our terms the deposit schedule is then chosen without kernel access, a constrained class the framework does not yet price. On the detection side, Fernandez et al. (2023a) consolidate deployed tests with non-asymptotic false-positive guarantees, the Level-0 discipline whose attribution-side analogue is the per-innocent δ/N form of Theorem 3.6(i); Li et al. (2025c) prove a truncated goodness-of-fit test adaptively optimal for detecting the Gumbel-max watermark under human edits, robust Level-0 where our open problem asks for robust Level 1. Closest in spirit to our currencies, He et al. (2026) derive information-theoretic trade-offs (false alarm, detection error, distortion, information rate) for multi-bit watermarking of stationary processes; like the concurrent He et al. (2025a), the analysis lives at the level of aggregate rates, and the positional decomposition ν(t), on which our shape and localization results turn, is again the difference. A further question in the same currency is answered by Chai and Wang (2026): estimating what fraction of a document is watermarked under the Gumbel-max mechanism, with matching information-theoretic lower bounds for both a full-observation and a pivotal-statistic estimator—a mixed-authorship reading of the mass ∥ν∥1 our framework has not itself posed. Finally, Golowich and Moitra (2024) construct watermarks that are simultaneously undetectable and robust to a constant fraction of adversarial edits via indexing pseudorandom codes: the strongest known step toward the regime of our sharpest open problem, since it achieves edit-robust Level 0, and whether an indexing-style construction supports N -user attribution at the h-rate is exactly the question Section 7 poses. Qin et al. (2026) attack a different notion of attribution entirely: attributing an image to its generating model from learned artifacts alone, with no embedded key and an open, ever-growing set of candidate generators (their IncreFA casts this as incremental learning against 28 models spanning 2022–2025). Theorem 3.6 instead prices attribution among a fixed, enrolled key set; the two notions bound complementary settings, passive generator identification versus keyed user attribution, and neither theorem transfers to the other’s regime. Attribution in agent-trajectory carriers. Moving beyond token streams, Gao et al. (2026b) watermark the trajectories of LLM agents—their logs of tool calls and actions—for robust ownership attribution, splitting the mark across two complementary channels: a selection channel keyed on local content and a tally channel keyed on log structure that stays invariant under rewriting. Read through the ladder this is Level-1 attribution in a non-text carrier, and the design speaks directly to our sharpest open problem: the structural tally channel is a deposit schedule whose support is engineered to survive step deletion and paraphrase, empirical evidence that the edit-robust attribution Section 7 calls for becomes attainable once the carrier admits a rewriting-invariant coordinate. In a related but distinct carrier, Lu et al. (2026) watermark a model’s own chain-of-thought: an ownership signal is aligned with high-saliency structural anchors in the internal geometry of the reasoning trace, and a model-free registration test verifies it, robust to fine-tuning, quantization, model perturbation, and output-level attack. Where Gao et al. (2026b) split the mark across an agent’s external action log, here the carrier is the reasoning process a single model produces on its own, a second illustration that attribution generalizes past the plain generated token sequence our profile ν is defined over. Image and multimodal schemes, and localization. Li et al. (2025a) embed diffusion-image watermarks in a low-dimensional subspace approximately orthogonal to the generation manifold; in the taxonomy’s terms this is a latent-basis choice, and the basis relativity of Definition 2.4 (only the mass ∥ν∥1 is invariant) is the right lens for such subspace designs. Gao et al. (2026c) bind distinct semantic factors of an image to designated regions of the initial noise, obtaining false-accept guarantees together with tamper localization, per-factor readout on the axis Theorem 3.12 prices. Zeng et al. (2026) layer audio-visual anti-tampering marks with cross-modal alignment for deepfake detection and localization, Level-3 readout in a multimodal carrier, company to EditGuard and AudioSeal in Table 2’s fine-readout rows. Two further constructions narrow to a single carrier each: Milis et al. (2026) watermark synthetic speech alone, exploiting token-vocabulary redundancy for a gradient-free scheme robust to audio-domain edits, and Chen et al. (2026) watermark panoramic imagery alone, coupling third-order 46
Watermark Forensics for Generative Models
SO(3) representations so the mark survives arbitrary 3-D rotation of the sphere. Both are carrier-specific instances of the same footprint-versus-basis question Section 4 poses in general. Attacks and removal. Removal is the adversarial complement of our lower bounds: the rates price the decoder’s task when the mark survives, and attacks decide whether it survives (the impossibility line of Francati et al., 2026; Zhang et al., 2023). Bao et al. (2026) give a training-free removal attack on diffusion watermarks that deflects the latent trajectory by stochastic resampling, succeeding against nine schemes at once because they share a reliance on trajectory reconstruction; Gao et al. (2026a) defeat semantic-aware image watermarks by LLM-guided, coherence-preserving semantic injection, attacking in the semantic basis the scheme reads, a reminder that the footprint, like sparsity, is basis-relative (Section 4). Ni et al. (2025) track how the mutual information a robust mark carries decays under iterated diffusion editing — an information-theoretic reading of removal on the same quantity ν whose deposit our converses price.
F
What is a watermark? A philosophical and historical discussion
The question in this section’s title is older than the technology that prompts it, and its oldest answer is an image. In the paper mills of Fabriano, around 1282, a figure of twisted wire was sewn onto the mould on which the pulp was couched; where the wire lay the sheet formed thinner, and the design (a crown, a hand, a unicorn) appeared not on the page but through it, when the leaf was lifted to the light (Hunter, 1947). The mark was in the very substance of the paper and yet nowhere on its surface; it named the maker, the mill, the year, and it did so to guard against forgery, so that the sheet could vouch for its own origin. Nearly everything essential to the objects of this paper is already present in that gesture: a mark laid into a carrier at the moment of its making, imperceptible to ordinary reading, and legible only from a particular standpoint — held, as it were, against the light. Two ancient impulses meet in it. The first is to authenticate: the seal in wax, the potter’s mark, the assayer’s hallmark struck on silver, the signature, each a way of binding a made thing to the one who made it, of letting an object carry its own provenance. The second is to conceal. The art of hidden writing is at least as old as Herodotus (1998, 5.35, 7.239), who tells that Histiaeus pricked a message into the shaved scalp of a slave and waited for the hair to regrow before sending him, and that Demaratus scraped the wax from a tablet, wrote on the wood beneath, and sealed the words again under fresh wax. Antiquity had no name for the practice; it was Trithemius, at the close of the fifteenth century, who supplied one (steganographia, covered writing) and bequeathed the modern art its name (Kahn, 1967). A generative watermark is the union of these two impulses, and a strange union it is, for it authenticates by concealing: the distortion-free mark of Theorem 3.6 is a seal that leaves the wax unbroken, a signature in an ink that, to every eye but one, is the paper itself. What kind of thing, then, is such a mark? Here the historical question turns metaphysical, and the standing temptation is to seek an object where there is none. Shown a marked passage and asked to point to the watermark, one hunts for a token, a phrase, a buried signature, and, for the schemes that matter, finds nothing. The error is one of category. It is the error Ryle (1949) diagnosed in the visitor who, shown the colleges, the library, and the halls, asks to be shown the University in addition: the University is not a further building beside the others but the manner in which they are ordered, and to look for it among them is to mistake its logical type. In an older vocabulary one seeks a substance and is offered an accident, a way that a substance is (Aristotle, 1963, Categories, chs. 2, 5). A biasing watermark is exactly this: not an object in the carrier but a property of the law that generated it, a disposition of the text to answer a certain test, present at every position and locatable at none. To ask which token is the mark is to ask which molecule of a warm gas carries its heat. That a property with no place can nonetheless be measured, named, and priced is the bequest of Shannon (1948): once information is reconceived as distinguishability rather than as stuff, a mark need not be a thing in order to be real, and the profile ν becomes the exact record, position by position, of how far the generating law has been bent to carry the secret, whether that bending is gathered into an object or dissolved into a property. If the watermark is not an object, what relation does it bear to its origin? The precise answer was furnished, in another connection, by Peirce (1931), who divided the ways a sign can stand for its object into three. An icon signifies by resemblance, a portrait, a map; a symbol by convention, a word, a flag; but an index signifies “by virtue of being really affected by that Object” (CP 2.248): smoke by fire, a weathercock by the wind, a footprint by the foot that pressed it. A watermark is neither icon nor symbol. It does not resemble its origin, and it refers 47
Watermark Forensics for Generative Models
to it by no agreement; it is an index. The correlations a decoder reads were physically laid down by the key at the instant of generation, and to detect or to attribute is to read backward along that causal thread to the act that deposited it. This is why forensics is possible at all (forensics is the reading of indices), and it is why the forensic-recovery budget of Theorem 3.1 has the form it has. An index can carry only the causal information that flowed into it; no reading, however ingenious, recovers a trace the cause did not leave. Data processing is nothing but this ancient fact set in the language of information: a trace cannot be manufactured downstream of the event that makes it. An index that points to a person becomes a name. The passage from the trace to the name was made by Kripke (1980), for whom a name is fastened to its bearer by an initial baptism and thereafter transmitted along a causal–historical chain, referring not through any description its user holds but through the unbroken line back to the baptismal act. The key, drawn at generation time, is such a baptism; the marked text carries the chain folded into its statistics; and to attribute is to trace the chain to the name that fixed it. Detection and attribution are thus two questions of unequal depth put to a single index. Detection asks only whether a mark exists — a question of being, indifferent to whose it is. Attribution asks whose, and this is the harder question, for it demands not existence but individuation: what makes this text the work of this origin and no other. The schoolmen had a word for the metaphysical ground of such thisness: the haecceity of Duns Scotus (1994), the ultimate difference by which a thing is this one and not another of its kind. Existence is cheap; haecceity is dear, and Theorem 3.6 prices it exactly, at log N nats in the appropriate currency, for to single one origin out of N is to pay log N nats of thisness. There remains a paradox at the core of every mark of authenticity, and it is the deepest lesson the theory holds. A mark can authenticate only if it can be checked, and to be checked it must in some measure be reproducible — the verifier must be able to regenerate or to recognize it. But a mark that is reproducible is, in the same measure, forgeable. Derrida (1988) found this tension in the signature, the very emblem of a singular and present author: a signature works as the sign of that singularity only because it has “a repeatable, iterable, imitable form,” and the iterability that lets it function at all is the same that makes it forgeable. A watermark inherits the paradox in its sharpest form and answers it with the key. The mark is made iterable for exactly one party, the holder of the key, and the security of the scheme is nothing but the size of the gap between the iterability granted to the verifier and the iterability withheld from the forger. The distortion-free construction is, in this light, a resolution of the signature’s paradox by information: the mark is wholly public in its effect (the text circulates freely, indistinguishable from unmarked text) and wholly private in its ground (only the key can read it), and the entire force of Theorem 3.6 lives in that difference. Here, too, Leibniz (1989) returns. His principle that no two things are indiscernible (that to be numerically distinct is to differ in some property) appears, in the distortion-free regime, to fail: two users’ outputs are, as laws, statistically identical, told apart by no test whatever. The principle is not broken but relativized. Indiscernibility is always indiscernibility to a standpoint; the texts no test can separate are separated at once by the holder of the registry, and the watermark is precisely the information that lives in the difference between what one standpoint can tell apart and what another cannot. This is the whole content of the registry-conditioning of Section 2: against the world the mark’s mass is zero, against the key it is positive, and the scheme is nothing but that difference. We may now answer the question of the title. A watermark is not a mark in a text but a structure in the relation among three terms: a text, the origin that generated it, and a standpoint from which that origin can be read. It is a trace, in Peirce’s exact sense, made legible by a key; a name, in Kripke’s, deposited at the text’s birth and recoverable along a causal thread; a commitment, in the end, by which the words are made to answer for where they came from. The text is unchanged; what the mark alters is not what the words say but what they owe — how much of their origin they can be compelled to confess, and from where. The profile ν is the ledger of that debt, entered once at generation and never after, and the four forensic questions of this paper are the four questions one has always been able to put to a trace: that it is (detection), whose it is (attribution), what it says (extraction), and where it lies (localization). Their prices, which the foregoing has computed, are the prices of reading a mark that was made, like the figure in the Fabriano sheet, to be found only by one who knows how to hold it to the light.
48