Covert Multi-bit LLM Watermarking: An Information Theory and Coding Approach
Abstract
We study the problem of multi-bit watermarking for non-autoregressive large language models (LLMs). We introduce an information-theoretic model inspired by diffusion language models (DLM), in which the encoder has limited non-causal access to token distributions within each token block. This formulation enables an information-theoretic characterization of the non-causal watermarking capacity, in which knowledge of LLM cover statistics is leveraged to enable a multi-bit covert embedding. We study the information-theoretic limits of the model by combining Gelfand--Pinsker and channel synthesis coding techniques and obtain an exact characterization of the capacity. The embedding strategy is further optimized across blocks using a constrained Markov decision process (CMDP) and we develop an explicit algorithm based on polar codes following the information-theoretic principles. We simulate the error performance on LLaDA, and provide empirical total variation (TV) analysis as a function of key randomness.
Related
- Feedback Coding Enables Inference-Time Covert Agentic Communication
- On the Information-Theoretic Limits of Latent-Space Watermarking Through Pretrained Generators
- Communication with Adversarial Users: Byzantine Models in Multi-User Information Theory
- SimpleMark: Fast Multi-Bit Text Watermarking under f -Divergence Constraints
- Distributed Cross-Layer Optimization for Covert Multi-Hop, Multi-Modal Networks: Exponentially Fast Convergence and Robust Tracking
BibTeX
@misc{guo2026covert,
title = {{Covert Multi-bit LLM Watermarking: An Information Theory and Coding Approach}},
author = {Sidong Guo and Tyler Kann and Teodora Baluta and Matthieu R. Bloch},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2605.16709},
eprint = {2605.16709},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2605.16709},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Covert Multi-bit LLM Watermarking: An Information Theory and Coding Approach
AU - Sidong Guo
AU - Tyler Kann
AU - Teodora Baluta
AU - Matthieu R. Bloch
PY - 2026
DA - 2026/09/02
PB - arXiv
DO - 10.48550/arxiv.2605.16709
UR - https://arxiv.org/abs/2605.16709
AB - We study the problem of multi-bit watermarking for non-autoregressive large language models (LLMs). We introduce an information-theoretic model inspired by diffusion language models (DLM), in which the encoder has limited non-causal access to token distributions within each token block. This formulation enables an information-theoretic characterization of the non-causal watermarking capacity, in which knowledge of LLM cover statistics is leveraged to enable a multi-bit covert embedding. We study the information-theoretic limits of the model by combining Gelfand--Pinsker and channel synthesis coding techniques and obtain an exact characterization of the capacity. The embedding strategy is further optimized across blocks using a constrained Markov decision process (CMDP) and we develop an explicit algorithm based on polar codes following the information-theoretic principles. We simulate the error performance on LLaDA, and provide empirical total variation (TV) analysis as a function of key randomness.
ER -