🔢 mathematics

Covert Multi-bit LLM Watermarking: An Information Theory and Coding Approach

This paper proposes a novel block-autoregressive framework for multi-bit LLM watermarking that leverages information-theoretic principles, including Gelfand-Pinsker and channel synthesis coding, to achieve high-capacity, low-distortion covert embedding with an explicit polar code-based algorithm.

Original authors: Sidong Guo, Tyler Kann, Teodora Baluta, Matthieu R. Bloch

Published 2026-05-19

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Sidong Guo, Tyler Kann, Teodora Baluta, Matthieu R. Bloch

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 have a very smart robot that writes stories, emails, or code. This robot is so good at mimicking human writing that it's hard to tell if a piece of text was written by a person or the robot. The authors of this paper want to solve a specific problem: How can we secretly mark the robot's writing to prove it came from the robot, without the writing sounding weird or losing its quality?

They call this "watermarking." Think of it like a hidden watermark in a banknote that you can't see with the naked eye, but a special scanner can detect.

Here is a simple breakdown of their approach, using everyday analogies:

1. The Problem: The Robot is Too Strict

Usually, when a robot writes, it picks words one by one, strictly based on the word it just wrote. It's like a train on a single track: once it leaves the station, it can't look ahead to see what the next station looks like.

The authors realized that if the robot could look ahead—even just a tiny bit—it could hide secret messages much better. They propose a new way for the robot to work: Block-Autoregressive.

The Analogy: Instead of picking one word at a time, imagine the robot picks a small "block" of 8 words at once. Before it locks in those 8 words, it looks at all the possible combinations of those 8 words. This gives it a "non-causal" view (a peek into the immediate future) of what the text could look like.

2. The Solution: The "Secret Menu"

The core idea is to use this "peek" to hide a secret message (like a digital ID tag) inside the text.

The Setup: Imagine the robot has a "base menu" of how it usually picks words.
The Trick: The authors introduce a "secret menu" (the watermark). When the robot is about to pick a block of words, it checks its secret menu.
- If the secret message says "0," it picks a word combination that is slightly more likely to be chosen from a specific group.
- If the secret message says "1," it picks from a different group.
The Magic: The robot does this so subtly that the overall "flavor" of the text (its statistical pattern) remains almost identical to the unwatermarked text. To a human reader, the story sounds perfect. To a special decoder with the secret key, the pattern of choices reveals the hidden message.

3. The Math: The "Perfect Balance"

The paper uses heavy math (Information Theory) to prove how much secret data they can hide without breaking the text.

The Gelfand-Pinsker Analogy: Imagine you are trying to send a message through a noisy radio channel, but you know exactly what the noise will sound like before you speak. You can adjust your voice to cancel out the noise perfectly. The authors treat the robot's natural word choices as "noise" and the secret message as the signal. Because the robot knows its own "noise" (the probability of word choices) in advance, it can hide the message more efficiently.
The Result: They calculated the theoretical maximum speed at which they can hide data. They found that by using this "peek-ahead" method, they can hide about 0.375 bits of data for every word generated. That's like hiding a tiny secret note inside every single word without the reader noticing.

4. The Algorithm: The "Smart Traffic Controller"

To make this work in real life, they didn't just guess; they built a smart system using two main tools:

CMDP (Constrained Markov Decision Process): Think of this as a traffic controller for the robot. The controller has to decide which words to pick to hide the message. But it has a rule: "Don't make the text sound weird." The controller constantly checks: "If I pick this word to hide a '1', will the next 7 words still sound natural?" It balances the need to hide data with the need to keep the text high-quality.
Polar Codes: This is a specific type of error-correction code (like a safety net). Even if the text gets slightly altered later (or if the decoder is a bit unsure), this code ensures the hidden message can still be recovered correctly.

5. The Results: It Works!

The authors tested their system using a real language model (LLaMA).

Stealth: The watermarked text was almost indistinguishable from normal text. The "perplexity" (a measure of how confusing or unnatural the text sounds) barely changed.
Reliability: They successfully hid messages with a very low error rate (less than 10% of the hidden bits were lost).
The Catch: The system works best with short blocks of text (like 8 words at a time). If they tried to look too far ahead (longer blocks), the math gets too heavy for computers to handle quickly.

Summary

The paper proposes a way to secretly stamp Large Language Models' output by letting the model "peek" at a small group of future words before deciding what to write. By using this peek to slightly nudge its word choices, it can embed a hidden ID message. The math proves this is possible without ruining the quality of the writing, and their computer algorithm successfully demonstrated it in practice.

What the paper does NOT claim:

It does not claim this works for any length of text instantly (it struggles with very long blocks).
It does not claim this is a perfect defense against all AI misuse, only a method for tracing and timestamping.
It does not discuss medical or clinical uses; it is purely about text generation and information theory.

Technical Summary: Covert Multi-bit LLM Watermarking: An Information Theory and Coding Approach

Problem Statement
The paper addresses the challenge of multi-bit watermarking for Large Language Models (LLMs). While zero-rate (binary) watermarking has been extensively studied to detect AI-generated text, embedding richer messages (e.g., for source tracing or timestamping) requires higher embedding rates without compromising text quality or detectability. Existing algorithmic approaches often lack a precise information-theoretic characterization of achievable rates, leading to suboptimal performance. Furthermore, standard LLMs operate under strictly autoregressive constraints, which prevent encoders from accessing future token distributions, limiting the application of classical non-causal information-theoretic frameworks like Gelfand-Pinsker (GP) coding.

Methodology and System Model
The authors propose a block-autoregressive model inspired by multi-token prediction architectures (e.g., self-speculative decoding). In this model, the encoder is granted limited non-causal access to token distributions within a block of length $n$ before sampling, provided that verification occurs prior to final token selection. This abstraction bridges the gap between practical LLMs and information-theoretic models.

The core technical approach involves three main components:

Information-Theoretic Formulation: The problem is modeled as a channel with state (the base token distribution $S$ ) known non-causally at the encoder but not at the decoder. The authors combine Gelfand-Pinsker (GP) coding (for message embedding) with channel resolvability coding (to ensure the watermarked distribution remains statistically close to the base distribution, ensuring covertness).
Capacity Characterization: The paper derives an exact characterization of the covert multi-bit watermarking capacity. The capacity is defined as the maximum rate $R$ such that the total variation (TV) distance between the watermarked distribution and the base distribution vanishes asymptotically, while the probability of decoding error approaches zero.
Algorithmic Implementation:
- Constrained Markov Decision Process (CMDP): To handle finite block lengths and the memory effects of LLMs, the optimization of joint distributions across blocks is formulated as a CMDP. This allows the system to balance immediate embedding rates against the impact on future state evolution.
- Polar Coding: An explicit construction based on polar codes is developed. The encoder utilizes the learned joint distribution to select index sets for message bits ( $H_{enc} \cap L_{dec}$ ) and employs a modified successive cancellation rule to handle sequence-level dependencies (non-i.i.d. states).
- Secret Key Usage: A secret key is used to one-time pad (OTP) specific message bits, providing the necessary randomness for soft-covering to satisfy the covertness constraint.

Key Contributions

Model Proposal: Introduction of a block-autoregressive model that enables non-causal access to token distributions within blocks, facilitating the adaptation of GP and channel resolvability schemes for LLMs.
Capacity Analysis: Derivation of the exact information-theoretic capacity for covert multi-bit watermarking under non-causal state access, expressed as $\max_{p(u|s), W(x|u,s)} [I(U; X) - I(U; S)]$ subject to distribution matching constraints.
Algorithm Design: Development of a practical watermarking algorithm that integrates CMDP for optimizing encoding distributions over multiple blocks and polar codes for explicit, capacity-achieving construction.

Results
Numerical experiments were conducted using LLaMA3.2 1B with a block length of $L=8$ and $B=2$ blocks.

Performance: The proposed algorithm achieves a bit-error rate (BER) below 10% at an embedding rate of 0.375 bits/token over short token lengths.
Quality: The method maintains negligible degradation in perplexity (PPL) and text quality, as measured by the base model's scoring mechanism.
Covertness: The study demonstrates that increasing the number of secret keys reduces the average Total Variation (TV) distance, aligning with theoretical predictions. However, for finite block lengths ( $L=8$ ), polarization is insufficient to fully realize the theoretical TV constraints at higher rates, leading to a trade-off where exceeding certain key rate thresholds can degrade covertness effectiveness.

Significance and Claims
The paper claims to provide the first exact information-theoretic characterization of multi-bit LLM watermarking capacity under a model that accounts for the practical constraints of LLMs (specifically, the relaxation of strict autoregression via multi-token prediction). By unifying GP coding and channel resolvability, the work establishes a theoretical upper bound on achievable rates while ensuring statistical covertness.

The authors emphasize that their approach offers a principled framework for embedding messages that balances robustness, distortion, and covertness. They acknowledge that the current implementation is limited by the computational complexity of optimizing encoding distributions and computing Bhattacharyya parameters for longer block lengths, identifying the design of scalable approximations (e.g., mismatched decoding or neural alternatives) as a primary direction for future work. The work is positioned as a foundational step toward rigorous, high-capacity watermarking for next-generation LLM architectures.