Paperlane

no. 16 · Tuesday 17 November 2026

Fundamental Limits of Statistical Watermarking for LLMs with Fixed and Optimizable Common Randomness

Haiyun He, Yepeng Liu, Zhuoer Shen, Ziqiao Wang, Yongyi Mao and Yuheng Bu

math.IT

Abstract

Watermarking has emerged as an important technique for distinguishing AI-generated text from human-written text. However, most existing work is primarily empirical, relies on ad hoc watermarking designs, and lacks a fundamental understanding of the performance limits. In this paper, we propose a unified theoretical framework for statistical watermarking of large language models (LLMs), casting the problem as an independence test between generated text and common randomness and jointly designing the watermarking embedder and the detector. Our objective is to maximize detection power while controlling the worst-case false positive rate (FPR) and limiting distortion to text quality. A central focus of our framework is the design of the common randomness, which plays a critical role in both watermark embedding and detection. We characterize the fundamental limits of statistical watermarking under both fixed and optimizable common randomness. Our results show that optimizing the common randomness does not improve the fundamental limits: the best achievable performance is the same as that with fixed common randomness. Nevertheless, common randomness design remains highly important because it can substantially simplify detector design. In particular, with optimizable common randomness, a fixed, deterministic, and model-agnostic detector can achieve optimal performance. We further study a practical setting with fixed uniform common randomness and a fixed deterministic detector, and characterize its performance gap relative to the optimizable case, thereby demonstrating the practical value of optimizable common randomness.

fields
Information Theory
pdf ↗ page arXiv:2611.19305 ↗