# Optimized Couplings for Watermarking Large Language Models

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

## Key facts

- Cited by 9 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 26 of its 47 references that are in the map.
- First posted on arXiv 13 May 2025.

## 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, 26 of 26)

- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [Constitutional AI: Harmlessness from AI Feedback](https://mlsanity.com/paper/2212.08073/) (2022)
- [TruthfulQA: Measuring How Models Mimic Human Falsehoods](https://mlsanity.com/paper/2109.07958/) (2021)
- [Transformer Feed-Forward Layers Are Key-Value Memories](https://mlsanity.com/paper/2012.14913/) (2020)
- [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)
- [TrustLLM: Trustworthiness in Large Language Models](https://mlsanity.com/paper/2401.05561/) (2024)
- [Undetectable Watermarks for Language Models](https://mlsanity.com/paper/2306.09194/) (2023)
- [Rethinking Lossy Compression: The Rate-Distortion-Perception Tradeoff](https://mlsanity.com/paper/1901.07821/) (2019)
- [On the Reliability of Watermarks for Large Language Models](https://mlsanity.com/paper/2306.04634/) (2023)
- [A Survey of Text Watermarking in the Era of Large Language Models](https://mlsanity.com/paper/2312.07913/) (2023)
- [Unbiased Watermark for Large Language Models](https://mlsanity.com/paper/2310.10669/) (2023)
- [MarkLLM: An Open-Source Toolkit for LLM Watermarking](https://mlsanity.com/paper/2405.10051/) (2024)
- [Three Bricks to Consolidate Watermarks for Large Language Models](https://mlsanity.com/paper/2308.00113/) (2023)
- [Watermarking Text Generated by Black-Box Language Models](https://mlsanity.com/paper/2305.08883/) (2023)
- [Mark My Words: Analyzing and Evaluating Language Model Watermarks](https://mlsanity.com/paper/2312.00273/) (2023)
- [Adaptive Text Watermark for Large Language Models](https://mlsanity.com/paper/2401.13927/) (2024)
- [A Statistical Framework of Watermarks for Large Language Models: Pivot, Detection Efficiency and Optimal Rules](https://mlsanity.com/paper/2404.01245/) (2024)
- [SoK: Watermarking for AI-Generated Content](https://mlsanity.com/paper/2411.18479/) (2024)
- [WaterBench: Towards Holistic Evaluation of Watermarks for Large Language Models](https://mlsanity.com/paper/2311.07138/) (2023)
- [A coding theorem for the rate-distortion-perception function](https://mlsanity.com/paper/2104.13662/) (2021)
- [Towards Optimal Statistical Watermarking](https://mlsanity.com/paper/2312.07930/) (2023)
- [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)
- [Watermarking Language Models with Error Correcting Codes](https://mlsanity.com/paper/2406.10281/) (2024)

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

- [PMark: Towards Robust and Distortion-free Semantic-level Watermarking with Channel Constraints](https://mlsanity.com/paper/2509.21057/) (2025)
- [A Unified Framework for LLM Watermarks](https://mlsanity.com/paper/2602.06754/) (2026)
- [ArcMark: Distortion-Free Multi-Byte LLM Watermark via Optimal Transport](https://mlsanity.com/paper/2602.07235/) (2026)
- [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)
- [Optimal Multi-bit Generative Watermarking Schemes Under Worst-Case False-Alarm Constraints](https://mlsanity.com/paper/2604.08759/) (2026)
- [Watermarkable Multi-Draft Speculative Sampling via Poisson Processes](https://mlsanity.com/paper/2609.21858/) (2026)
- [On the Information-Theoretic Limits of Latent-Space Watermarking Through Pretrained Generators](https://mlsanity.com/paper/2609.24377/) (2026)

## Abstract (arXiv)

Large-language models (LLMs) are now able to produce text that is, in many cases, seemingly indistinguishable from human-generated content. This has fueled the development of watermarks that imprint a ``signal'' in LLM-generated text with minimal perturbation of an LLM's output. This paper provides an analysis of text watermarking in a one-shot setting. Through the lens of hypothesis testing with side information, we formulate and analyze the fundamental trade-off between watermark detection power and distortion in generated textual quality. We argue that a key component in watermark design is generating a coupling between the side information shared with the watermark detector and a random partition of the LLM vocabulary. Our analysis identifies the optimal coupling and randomization strategy under the worst-case LLM next-token distribution that satisfies a min-entropy constraint. We provide a closed-form expression of the resulting detection rate under the proposed scheme and quantify the cost in a max-min sense. Finally, we provide an array of numerical results, comparing the proposed scheme with the theoretical optimum and existing schemes, in both synthetic data and LLM watermarking. Our code is available at https://github.com/Carol-Long/CC_Watermark