🔢 mathematics

Optimal Multi-bit Generative Watermarking Schemes Under Worst-Case False-Alarm Constraints

This paper demonstrates that a previously proposed multi-bit generative watermarking scheme for large language models is suboptimal under worst-case false-alarm constraints and introduces two new encoding-decoding constructions that achieve the theoretical lower bound on miss-detection probability, thereby fully characterizing optimal watermarking performance.

Original authors: Yu-Shin Huang, Chao Tian, Krishna Narayanan

Published 2026-04-13

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Yu-Shin Huang, Chao Tian, Krishna Narayanan

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a master chef (the Large Language Model) who can cook up delicious, realistic meals (text) that look exactly like they were made by a human. But there's a problem: people are worried that bad actors might use your cooking to spread fake news or plagiarize work.

To solve this, you want to put a secret watermark inside every dish you make. This watermark is like a tiny, invisible ingredient that proves, "Yes, I cooked this!" However, the watermark has two strict rules:

It must be invisible: No one should be able to taste it or tell the dish is different.
It must be un-removable: Even if someone tries to guess the secret ingredient, they shouldn't be able to fake it.

The Problem: The "Too Many Messages" Puzzle

Most current watermarks are like a simple light switch: they just say "On" (AI made this) or "Off" (Human made this). But the authors of this paper wanted to do something harder: Multi-bit watermarking.

Think of this like sending a secret code instead of just a light switch. You want to embed a specific message (like "Recipe ID #42" or "Author: Chef Alice") into the text. The challenge is: How do you hide a complex message without ruining the taste of the dish or making it too easy for a forger to fake?

The Failed Attempt: The "Rigid Blueprint"

Previously, another team of researchers (He et al.) tried to solve this. They built a system based on a very strict, rigid blueprint.

The Analogy: Imagine they tried to pack a suitcase by forcing every item into a specific, pre-determined slot, no matter how big or small the item was.
The Flaw: They thought this rigid packing was the most efficient way to fit everything in. But the authors of this paper discovered that this "rigid blueprint" actually leaves empty space in the suitcase. It's suboptimal. It forces the system to make more mistakes (like misidentifying a human text as AI) than it needs to.

The Solution: Two New "Smart Packing" Schemes

The authors of this paper realized the previous method was too stiff. They developed two new, flexible ways to pack the secret message into the text that achieve the absolute theoretical limit of perfection.

Scheme A: The "Decomposition" Method (The Master Organizer)

This approach is like taking a messy pile of clothes (the text probabilities) and breaking them down into three specific layers:

The Core Layer: The essential items that fit perfectly into the "secret slots."
The Step Layer: Items that need to be stacked carefully to fill gaps without spilling over.
The Balance Layer: A final adjustment to make sure the suitcase is perfectly balanced so it doesn't tip over (mathematically, this ensures the "row-sum" stays equal).

The Magic Trick: They use a concept called "T-hot representable vectors."

Imagine: You have a set of keys (secret codes). You need to assign a specific key to a specific dish. This method ensures that every possible combination of keys and dishes is used efficiently, like a perfectly organized library where every book has a unique, logical spot.

Scheme B: The "Pseudo-Token" Method (The Magic Extension)

This approach is conceptually simpler but requires a bigger "key ring."

The Analogy: Imagine you are trying to pack a suitcase, but your clothes are too big to fit. Instead of squishing them, you temporarily add invisible "ghost clothes" (pseudo-tokens) to the suitcase to make the math work out perfectly.
Once the packing is done, you magically remove the ghost clothes and redistribute their "weight" back onto the real clothes.
The Trade-off: This method is easier to understand and build, but it requires a much larger set of secret keys (a bigger key ring) than Scheme A.

Why Does This Matter?

The authors proved that their new methods are optimal.

The Lower Bound: They calculated the absolute best possible performance a watermark can ever have (the "speed limit" of the system).
The Result: Their new schemes hit that speed limit exactly. The old method was driving 5 mph under the limit; these new ones are driving right at the limit.

The "False Alarm" Constraint

A critical part of their work is the "Worst-Case False-Alarm Constraint."

The Analogy: Imagine a metal detector at an airport. You don't want it to beep every time a human walks through (a false alarm). The system must be so good that even if a forger tries to trick it with the worst possible fake text, the detector still won't scream "AI!" unless it's actually AI.
The authors' new schemes guarantee that even in the worst-case scenario, the error rate is as low as mathematically possible.

Summary

The Old Way: Tried to force a square peg into a round hole. It worked, but not perfectly.
The New Way:
1. Scheme A: A highly efficient, complex way of organizing the data to fit perfectly.
2. Scheme B: A simpler way that uses "ghost" helpers to make the math work, at the cost of needing more secret keys.
The Outcome: We now have the perfect recipe for hiding multi-bit messages in AI text. It's the most efficient, secure, and undetectable method possible, solving a problem that stumped researchers for a while.

In short, the authors took a broken, inefficient puzzle, realized the pieces were being forced into the wrong spots, and found the perfect way to assemble the puzzle so that the picture is clear, the pieces fit snugly, and no one can tell it was ever a puzzle at all.

1. Problem Statement

The paper addresses the challenge of multi-bit generative watermarking for Large Language Models (LLMs) under a worst-case false-alarm constraint.

Context: As LLMs generate text indistinguishable from human writing, robust watermarking is needed to detect AI-generated content and embed hidden metadata (multi-bit messages).
Constraints:
- Distortionless: The watermarked text must preserve the original statistical properties of the LLM's token distribution ( $P_X$ ).
- Worst-Case False Alarm: The probability of the decoder incorrectly identifying non-watermarked text as watermarked (false alarm) must not exceed a threshold $\alpha$ , even for the worst-case token distribution $Q_X$ .
- Goal: Minimize the miss-detection probability (the probability of failing to detect a valid watermark message $m \in [1:T]$ ) while satisfying the above constraints.
Gap in Prior Work: A previous study by He et al. [11] proposed a theoretical lower bound on the miss-detection probability and a specific encoding-decoding scheme claimed to achieve it. This paper demonstrates that the scheme in [11] is suboptimal and often invalid due to overly restrictive decoder designs.

2. Methodology

The authors formulate the watermarking design problem as a Linear Program (LP) to characterize the optimal trade-off between false alarms and miss-detection.

A. Theoretical Framework

System Model: Defined by an encoder $f$ , a sampler $g$ , and a decoder $\gamma$ . The encoder maps a message $m$ and token distribution $P_X$ to a joint distribution $P_m(X, Z)$ over tokens and a secret key $Z$ .
Optimization Objective: Minimize $\max_{m} \beta_m$ $max_{m} β_{m}$ (worst-case miss-detection) subject to:
1. $\sup_{Q_X} \beta_0(Q_X \otimes P_Z, \gamma) \leq \alpha$ (Worst-case false alarm constraint).
2. Marginal invariance: $\sum_\zeta P_m(x, \zeta) = P_X(x)$ (Distortionless).
Theoretical Lower Bound: The paper reaffirms the lower bound derived in [11] for the optimal miss-detection probability:
$\beta^*[\alpha, P_X] = 1 - \sum_{x \in X} \min\left(\frac{\alpha}{T}, P_X(x)\right)$
The core contribution is proving achievability of this bound, which the previous work failed to do correctly.

B. Key Structural Insights

To achieve the lower bound, the authors identify two necessary structural conditions for the joint distribution $P_m(x, \zeta)$ :

$\alpha$ -bounded total sum: The sum of probabilities assigned to keys that decode to any message $m$ for a specific token $x$ must be $\leq \alpha$ .
$\alpha/T$ -capped column sum: For a specific message $m$ and token $x$ , the probability mass assigned to pairs $(x, \zeta)$ that decode to $m$ must be at least $\min(\alpha/T, P_X(x))$ .

3. Proposed Solutions (Two Optimal Constructions)

The paper introduces two novel encoding-decoding constructions that satisfy the necessary conditions and achieve the theoretical lower bound.

Construction A: Decomposition Approach

This method decomposes the token distribution $P_X$ into three components: $P_X = P_X^{(1)} + P_X^{(2)} + P_X^{(3)}$ .

$P_X^{(1)}$ (T-hot Representable): A component that can be represented as a weighted sum of "T-hot" vectors (vectors with exactly $T$ non-zero entries). This part is distributed using a structural basis where keys are permutations of a canonical vector.
$P_X^{(2)}$ (Step-Vectors): A non-negative, non-decreasing vector with at most $T-1$ positive entries at the tail. This is allocated using "anchored keys" to satisfy the $\alpha/T$ cap without violating row-sum invariance immediately.
$P_X^{(3)}$ (Residual): The remaining mass ( $P_X(x) - \alpha/T$ if positive). This component is used to correct the row-sum imbalance introduced by the allocation of $P_X^{(2)}$ .

Key Mechanism: The algorithm carefully balances the "row-sum imbalance" (where some keys have higher total probability than others across different messages) using the residual mass $P_X^{(3)}$ and a specific "dummy" key $\mathbf{0}$ .

Construction B: Pseudo-Token Approach

This approach is conceptually simpler but may require a larger key space.

Extended Space: It constructs an extended token distribution $P'_X$ $P_{X}^{'}$ of length $N+n$ $N + n$ (where $n \geq 0$ $n \geq 0$ ) that is strictly T-hot representable.
- If $P_X$ is already T-hot representable, $n=0$ .
- Otherwise, $n$ "pseudo-tokens" are added to the vocabulary to make the distribution T-hot representable.
Mapping: The joint distribution is constructed in this extended space using the T-hot representation method.
Projection: The mass associated with the pseudo-tokens is mapped back to the original token space $X$ proportionally to the residual mass $r(x) = \max(P_X(x) - \alpha/T, 0)$ .

Trade-off: Construction B is more straightforward to implement but may require a significantly larger key set size ( $|Z|$ ) compared to Construction A, depending on the uniformity of $P_X$ .

4. Key Results

Refutation of Prior Work: The authors provide a counter-example (using $N=3, T=2, \alpha=0.9$ ) and a duality argument to prove that the construction in [11] cannot achieve the claimed optimal bound. The failure is attributed to the rigid decoder design in [11] which cannot satisfy the necessary linear constraints simultaneously.
Achievability: Both Construction A and Construction B are proven to achieve the theoretical lower bound:
$\max_{m} \beta_m = 1 - \sum_{x \in X} \min\left(\frac{\alpha}{T}, P_X(x)\right)$
Optimality: The paper completely characterizes the optimal performance for multi-bit generative watermarking under worst-case false-alarm constraints.

5. Significance

Theoretical Closure: This work settles the open problem of optimal multi-bit watermarking performance, correcting a significant error in the existing literature.
Practical Implications: By providing explicit, optimal constructions, the paper offers a blueprint for designing watermarking schemes that maximize information embedding (multi-bit) while strictly controlling false alarms and maintaining text naturalness (distortionless).
Methodological Contribution: The introduction of T-hot representable vectors and the decomposition of probability distributions provide new tools for information-theoretic analysis of generative models.
Robustness: The focus on worst-case false-alarm constraints ensures that the watermarking schemes are robust against adversarial token distributions, a critical requirement for real-world deployment against attempts to evade detection.

In summary, this paper establishes the fundamental limits of multi-bit LLM watermarking and provides two constructive, optimal algorithms to reach these limits, correcting previous misconceptions in the field.