Catch-22: On the Fundamental Tradeoff Between Detectability and Robustness in LLM Watermarking

Large language models generate text by sampling tokens at random, a process now widely used for inference-time watermarking that verifies AIgenerated content. We present an informationtheoretic framework that captures the trade-off between robustness to text edits and detectability by observers who lack the watermark key or a keyless detector. The bounds we derive hold regardless of computational power, and what a keyless detector can actually achieve depends on what it can observe about the model and its outputs. At the heart of the analysis is an additive, Kullback-Leibler (KL) information measure that quantifies how well a hypothesis test can distinguish watermarked from unwatermarked text while the watermark remains stealthy. The measure remains zero for distribution-preserving schemes and increases with text length for token-level and sentencelevel probability-modifying schemes. When edits are modeled as noise, the KL measure shrinks quadratically with the edit rate for token-level schemes and with an induced semantic flip rate for sentence-level schemes. This shrinkage exposes an unavoidable trilemma among robustness, stealth, and reliable verification. Guided by these limits, we propose a hybrid watermarking strategy that selects the Pareto-optimal scheme among distribution-preserving, semantic-level, and tokenlevel methods based on the expected editing regime at deployment. Experiments on Llama-2-7B and Mistral-7B under paraphrasing attacks corroborate these theoretical predictions and confirm that the hybrid strategy lies near the Pareto frontier across the edit regimes we evaluate.