Watermark Forensics: An Information-Theoretic Ladder Beyond Detection

Paper: 2607.13003 Authors: Xiaoyu Li, Zheng Gao, Xiaoyan Feng, Jiaojiao Jiang, Yulei Sui, Jiankun Hu Categories: cs.CR, cs.IT, cs.LG

The Gap

Existing watermark research largely stops at detection—is this text AI-generated? The next logical steps, attributing which user generated it or embedding a hidden payload, were treated as separate engineering problems without a unified theoretical foundation. Prior attribution methods often relied on ad-hoc collision counting or brute-force matching, which lacked provable efficiency and couldn’t precisely quantify the fundamental cost. Furthermore, the interplay between these tasks and the underlying language model’s entropy was not formally characterized, leaving key trade-offs (like watermark footprint vs. resolution) as informal guidelines.

+-----------------------+    +-------------------------------+    +---------------------+
| Prior State:          |    | This Paper's Path:            |    | Outcome:            |
| Detection-only focus  | -> | Define unified "forensic      | -> | Tight, provable     |
| Ad-hoc attribution    |    | ladder" using information     |    | entropy-rate laws   |
| No cost quantification|    | profile v(t) = I(S;Xt|X<t)   |    | for each task       |
+-----------------------+    +-------------------------------+    +---------------------+

The Increment

One sentence: Before this paper, watermark forensics was a collection of isolated tasks with heuristic solutions; after, it is a unified information-theoretic framework where the cost of each forensic operation (attribution, extraction, localization) is precisely quantified by how secret information is distributed across tokens.

Core Mechanism

The paper introduces a central object: the information profile, ν(t) = I(S; Xₜ | X_{<t}). This measures, for each token position *t, the mutual information between the secret payload S (e.g., a user ID) and the token Xₜ, given all previous tokens. Think of ν(t) as the “information yield” of the t-th token about the secret. The total sum of ν(t) over the sequence is the total secret information embedded, which pays for the forensic tasks.

The framework reveals a fundamental division. Attribution and payload extraction are “information-paid” tasks—their cost scales with the total information mass (Σ ν(t)). Detection, however, is “presence-paid”—it depends on the statistical distance between the marked and unmarked distributions, not on information content. Localization depends on the *spread of the information profile. Two watermarking philosophies emerge as special cases: a “subtle” mark with small, uniform ν(t) (good for quality, poor for localization) and a “loud” mark with a few large ν(t) values (good for localization, riskier for quality).

+------------------+        +--------------------------------------+
| Secret Payload S |        | Information Profile v(t)             |
| (e.g., user ID)  |------->| Measures I(S; Xt | X<t) per token. |
+------------------+        +--------------------------------------+
                                    |                |                |
                                    v                v                v
                            +-----------+    +---------------+    +--------------+
                            | Total Mass|    | Spread/Shape  |    | Presence     |
                            | (Sum v(t))|    | (Localization)|    | (Detection)  |
                            +-----------+    +---------------+    +--------------+
                                    |                |
                                    v                v
                            +-----------+    +---------------+
                            | Attribution/|    | Localization  |
                            | Extraction  |    | of Edits      |
                            +-----------+    +---------------+

Here’s a structural metaphor: imagine a postal system for secrets. The secret *S is a letter you want to smuggle. The generated text is a train of mail cars (tokens). The watermarking scheme is your smuggling method.

• Information Profile ν(t): This is how many pages of the secret letter you hide in each mail car. Hiding a little in every car (subtle mark) is stealthy but means a customs agent (detector) needs to inspect a long train to be sure something’s amiss. Hiding the whole letter in one car (loud mark) is risky but makes the train shorter for attribution.
• Total Information Mass (Σ ν(t)): This is the total number of secret letter pages. To attribute the letter to one of *N possible senders (users), you need enough total pages to uniquely identify the sender. The paper proves this requires Θ(log N / h) mail cars, where h is the entropy rate (the “diversity” of the cargo in each car).
• Localization: This is asking which specific mail cars were tampered with. If you spread the secret letter thinly across all cars, it’s hard to localize edits (changing a few cars doesn’t destroy the letter). If you put all pages in a few cars, localizing edits is easy (but losing those cars loses the whole secret).
• Detection: This is simply asking “is this train carrying contraband at all?” which depends on the overall statistical smell of the train, not on how the secret pages are distributed.

Key Concepts

• Information Profile ν(t): Forget the math for a second. Think of a secret message *S (e.g., the number 42) being encoded into a sequence of coin flips. The “information profile” is just a list of how much each individual flip tells you about the secret, given what you’ve already seen from the previous flips. If the scheme is to make the first flip be “heads” if S=42 and “tails” otherwise, then ν(1) is huge (that one flip tells you everything about S if it’s heads). All subsequent flips have ν(t)≈0, because the secret is already fully known. This paper uses this concept to bookkeep how the “forensic value” is distributed across the output.

• Entropy-Rate Bound for Attribution: This is the paper’s main technical result. It states that to reliably attribute a text to one of *N users, the text must be at least Θ(log N / h) tokens long, where h is the source’s entropy rate. The intuition: you need log N bits of information to distinguish N possibilities. The entropy rate h tells you how many bits of “information capacity” each token provides on average. So the minimum length is (bits needed) / (bits per token). The “tightness” means no scheme can do asymptotically better, and the paper constructs a scheme that achieves this bound.

• Footprint-Resolution Uncertainty Principle: You cannot have both a tiny watermark footprint (subtle, low-distortion mark) and high localization resolution (pinpointing exactly where edits occurred) simultaneously. These are trade-offs, like Heisenberg’s uncertainty. A mark that is very subtle spreads its information thinly across many tokens, making it hard to tell which tokens were edited. A mark that precisely localizes edits must concentrate its signal in fewer tokens, making those tokens more conspicuous.

Framework Shift

Before (mainstream approach):        After (this paper):
+---------------------------+        +-------------------------------------+
| Detection:                |        | Unified Framework:                  |
| Hypothesis test           |        | Forensic Tasks as Information Costs |
| (Is it AI-generated?)     |        |   - Detection (Presence-paid)       |
+---------------------------+        |   - Attribution/Extraction          |
| Attribution/Extraction:   |        |       (Information-paid, by mass)   |
| Separate ad-hoc methods   |  --->  |   - Localization                    |
| (Collision counts, etc.)  |        |       (Information-paid, by spread) |
+---------------------------+        +-------------------------------------+
| No unified theory;        |        | Core Object: Information Profile    |
| costs not quantified      |        | v(t) = I(S; Xt|X<t)                |
+---------------------------+        | Governs all costs precisely.        |
                                     +-------------------------------------+

From task-specific heuristics to an information-theoretic cost structure, the core shift is treating watermark forensics as an information flow problem where the secret’s distribution across tokens dictates all possible operations and their fundamental limits.

Expert Assessment

Problem choice: Excellent. This is a real, foundational gap. Watermarking is moving from binary detection to richer forensics, and the field lacked a principled framework. The paper positions itself at the intersection of information theory and practical AI security, which is a sweet spot for impact.

Method maturity: High. The use of mutual information profiles is a natural but powerful lens. The main theorem (Θ(log N / h)) is a clean, insightful result. The identification of the “decoder thresholding by realized surprisal” as optimal is a clever insight that moves beyond naive collision counting. It’s more insight than brute force.

Experimental integrity: Solid. They validate on GPT-2, Pythia, and Qwen2.5, recovering predicted constants. The baselines are appropriate (comparing against the non-optimal collision-counting method). The experiments confirm the theory rather than being the paper’s core strength, which is typical for a theory paper. No red flags.

Writing quality: Very good for a theory paper, but dense. The “forensic ladder” framing is brilliant for clarity. The weakest section might be the deeper parts of the converse proof in the appendix—more intuition there would help. The main text, however, does a commendable job of balancing rigor and intuition.

Verdict: Strong accept. This paper provides the missing theoretical foundation for a rapidly evolving practical area. It’s likely to become a standard reference for anyone working on LLM watermarking beyond detection.

Takeaways

1. Frame your problem with an information profile. When designing any system that embeds a secret into a sequence (watermarks, steganography, coding), explicitly analyze and design the *distribution of secret information across the sequence, not just the total amount. This reveals fundamental trade-offs (e.g., subtlety vs. localizability).
2. Distinguish between “information-paid” and “presence-paid” tasks. In security, some attacks require stealing information (paid by information capacity), while others just require detecting an anomaly (paid by statistical divergence). The optimal defense for each is fundamentally different.
3. Use “realized surprisal” thresholds for attribution. Instead of generic statistical tests, calibrate your detection/attribute thresholds to the specific, token-level surprise of the candidate watermark. This is more efficient and achieves provable bounds.