Watermark Forensics for Generative Models: An Information-Theoretic Perspective

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; X_t | 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.