# Towards Optimal Statistical Watermarking

arXiv: https://arxiv.org/abs/2312.07930 · HTML: https://mlsanity.com/paper/2312.07930/

## Key facts

- Cited by 26 papers in the map (data through 14 Oct 2026).
- Placed in Watermarking generated content and models, one of 12 directions in LLM safety and security.
- Builds on 18 of its 32 references that are in the map.
- First posted on arXiv 13 Dec 2023.

## Placed in

- LLM safety and security / [Watermarking generated content and models](https://mlsanity.com/safety/watermarking-generated-content-and-models/)

## Builds on (most cited first, 18 of 18)

- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [A Watermark for Large Language Models](https://mlsanity.com/paper/2301.10226/) (2023)
- [Robust Distortion-free Watermarks for Language Models](https://mlsanity.com/paper/2307.15593/) (2023)
- [Provable Robust Watermarking for AI-Generated Text](https://mlsanity.com/paper/2306.17439/) (2023)
- [Undetectable Watermarks for Language Models](https://mlsanity.com/paper/2306.09194/) (2023)
- [On the Reliability of Watermarks for Large Language Models](https://mlsanity.com/paper/2306.04634/) (2023)
- [Adversarial Watermarking Transformer: Towards Tracing Text Provenance with Data Hiding](https://mlsanity.com/paper/2009.03015/) (2020)
- [The Science of Detecting LLM-Generated Texts](https://mlsanity.com/paper/2303.07205/) (2023)
- [Watermarks in the Sand: Impossibility of Strong Watermarking for Generative Models](https://mlsanity.com/paper/2311.04378/) (2023)
- [Three Bricks to Consolidate Watermarks for Large Language Models](https://mlsanity.com/paper/2308.00113/) (2023)
- [OUTFOX: LLM-Generated Essay Detection Through In-Context Learning with Adversarially Generated Examples](https://mlsanity.com/paper/2307.11729/) (2023)
- [Publicly-Detectable Watermarking for Language Models](https://mlsanity.com/paper/2310.18491/) (2023)
- [Mark My Words: Analyzing and Evaluating Language Model Watermarks](https://mlsanity.com/paper/2312.00273/) (2023)
- [Watermarking Conditional Text Generation for AI Detection: Unveiling Challenges and a Semantic-Aware Watermark Remedy](https://mlsanity.com/paper/2307.13808/) (2023)
- [Tracing Text Provenance via Context-Aware Lexical Substitution](https://mlsanity.com/paper/2112.07873/) (2021)
- [Embarrassingly Simple Text Watermarks](https://mlsanity.com/paper/2310.08920/) (2023)
- [Towards Code Watermarking with Dual-Channel Transformations](https://mlsanity.com/paper/2309.00860/) (2023)

## Built on by (most cited first, 26 of 26)

- [Risk Taxonomy, Mitigation, and Assessment Benchmarks of Large Language Model Systems](https://mlsanity.com/paper/2401.05778/) (2024)
- [SoK: Watermarking for AI-Generated Content](https://mlsanity.com/paper/2411.18479/) (2024)
- [Theoretically Grounded Framework for LLM Watermarking: A Distribution-Adaptive Approach](https://mlsanity.com/paper/2410.02890/) (2024)
- [Debiasing Watermarks for Large Language Models via Maximal Coupling](https://mlsanity.com/paper/2411.11203/) (2024)
- [A Watermark for Black-Box Language Models](https://mlsanity.com/paper/2410.02099/) (2024)
- [PMark: Towards Robust and Distortion-free Semantic-level Watermarking with Channel Constraints](https://mlsanity.com/paper/2509.21057/) (2025)
- [WAPITI: A Watermark for Finetuned Open-Source LLMs](https://mlsanity.com/paper/2410.06467/) (2024)
- [Defending LLM Watermarking Against Spoofing Attacks with Contrastive Representation Learning](https://mlsanity.com/paper/2504.06575/) (2025)
- [Optimized Couplings for Watermarking Large Language Models](https://mlsanity.com/paper/2505.08878/) (2025)
- [PASA: A Principled Embedding-Space Watermarking Approach for LLM-Generated Text under Semantic-Invariant Attacks](https://mlsanity.com/paper/2605.10977/) (2026)
- [On the Empirical Power of Goodness-of-Fit Tests in Watermark Detection](https://mlsanity.com/paper/2510.03944/) (2025)
- [A Unified Framework for LLM Watermarks](https://mlsanity.com/paper/2602.06754/) (2026)
- [Generative AI Security: Challenges and Countermeasures](https://mlsanity.com/paper/2402.12617/) (2024)
- [Segmenting Watermarked Texts From Language Models](https://mlsanity.com/paper/2410.20670/) (2024)
- [Detecting Post-generation Edits to Watermarked LLM Outputs via Combinatorial Watermarking](https://mlsanity.com/paper/2510.01637/) (2025)
- [CATMark: A Context-Aware Thresholding Framework for Robust Cross-Task Watermarking in Large Language Models](https://mlsanity.com/paper/2510.02342/) (2025)
- [Data-Centric AI in the Age of Large Language Models](https://mlsanity.com/paper/2406.14473/) (2024)
- [Refined Detection for Gumbel Watermarking](https://mlsanity.com/paper/2603.30017/) (2026)
- [HeavyWater and SimplexWater: Distortion-Free LLM Watermarks for Low-Entropy Next-Token Predictions](https://mlsanity.com/paper/2506.06409/) (2025)
- [Improving the Trade-off Between Watermark Strength and Speculative Sampling Efficiency for Language Models](https://mlsanity.com/paper/2602.01428/) (2026)
- [Watermark Forensics for Generative Models: An Information-Theoretic Perspective](https://mlsanity.com/paper/2607.13003/) (2026)
- [Watermark Smoothing Attacks against Language Models](https://mlsanity.com/paper/2407.14206/) (2024)
- [Adaptive Testing for Segmenting Watermarked Texts From Language Models](https://mlsanity.com/paper/2511.06645/) (2025)
- [MarkTune: Improving the Quality-Detectability Trade-off in Open-Weight LLM Watermarking](https://mlsanity.com/paper/2512.04044/) (2025)
- [Trustworthy AI: Ensuring Reliability and Accountability from Models to Agents](https://mlsanity.com/paper/2605.08964/) (2026)
- [TTMark: Pairwise Distortion-Free Watermarking Beyond Single-Token Entropy](https://mlsanity.com/paper/2609.36372/) (2026)

## Abstract (arXiv)

We study statistical watermarking by formulating it as a hypothesis testing problem, a general framework which subsumes all previous statistical watermarking methods. Key to our formulation is a coupling of the output tokens and the rejection region, realized by pseudo-random generators in practice, that allows non-trivial trade-offs between the Type I error and Type II error. We characterize the Uniformly Most Powerful (UMP) watermark in the general hypothesis testing setting and the minimax Type II error in the model-agnostic setting. In the common scenario where the output is a sequence of n tokens, we establish nearly matching upper and lower bounds on the number of i.i.d. tokens required to guarantee small Type I and Type II errors. Our rate of Theta(h-1 log (1/h)) with respect to the average entropy per token h highlights potentials for improvement from the rate of h-2 in the previous works. Moreover, we formulate the robust watermarking problem where the user is allowed to perform a class of perturbations on the generated texts, and characterize the optimal Type II error of robust UMP tests via a linear programming problem. To the best of our knowledge, this is the first systematic statistical treatment on the watermarking problem with near-optimal rates in the i.i.d. setting, which might be of interest for future works.