betaFeedback

WorksComputer Science

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

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.

Paper details

vlnc:W_fzkfvakj
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…