# Distortion-free Watermarks are not Truly Distortion-free under Watermark Key Collisions

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

## Key facts

- Cited by 10 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 24 of its 43 references that are in the map.
- First posted on arXiv 2 Jun 2024.

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

- [Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer](https://mlsanity.com/paper/1910.10683/) (2019)
- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [BERTScore: Evaluating Text Generation with BERT](https://mlsanity.com/paper/1904.09675/) (2019)
- [HuggingFace's Transformers: State-of-the-art Natural Language Processing](https://mlsanity.com/paper/1910.03771/) (2019)
- [Teaching Machines to Read and Comprehend](https://mlsanity.com/paper/1506.03340/) (2015)
- [Multilingual Denoising Pre-training for Neural Machine Translation](https://mlsanity.com/paper/2001.08210/) (2020)
- [DetectGPT: Zero-Shot Machine-Generated Text Detection using Probability Curvature](https://mlsanity.com/paper/2301.11305/) (2023)
- [A Watermark for Large Language Models](https://mlsanity.com/paper/2301.10226/) (2023)
- [Defending Against Neural Fake News](https://mlsanity.com/paper/1905.12616/) (2019)
- [Paraphrasing evades detectors of AI-generated text, but retrieval is an effective defense](https://mlsanity.com/paper/2303.13408/) (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)
- [A Semantic Invariant Robust Watermark for Large Language Models](https://mlsanity.com/paper/2310.06356/) (2023)
- [Unbiased Watermark for Large Language Models](https://mlsanity.com/paper/2310.10669/) (2023)
- [On the Possibilities of AI-Generated Text Detection](https://mlsanity.com/paper/2304.04736/) (2023)
- [An Unforgeable Publicly Verifiable Watermark for Large Language Models](https://mlsanity.com/paper/2307.16230/) (2023)
- [A Resilient and Accessible Distribution-Preserving Watermark for Large Language Models](https://mlsanity.com/paper/2310.07710/) (2023)
- [Your Vision-Language Model Itself Is a Strong Filter: Towards High-Quality Instruction Tuning with Data Selection](https://mlsanity.com/paper/2402.12501/) (2024)
- [Adversarial Weight Perturbation Improves Generalization in Graph Neural Networks](https://mlsanity.com/paper/2212.04983/) (2022)
- [Learning to Learn from APIs: Black-Box Data-Free Meta-Learning](https://mlsanity.com/paper/2305.18413/) (2023)
- [Reverse Engineering Configurations of Neural Text Generation Models](https://mlsanity.com/paper/2004.06201/) (2020)
- [RetrievalGuard: Provably Robust 1-Nearest Neighbor Image Retrieval](https://mlsanity.com/paper/2206.11225/) (2022)
- [A Law of Robustness beyond Isoperimetry](https://mlsanity.com/paper/2202.11592/) (2022)

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

- [Theoretically Grounded Framework for LLM Watermarking: A Distribution-Adaptive Approach](https://mlsanity.com/paper/2410.02890/) (2024)
- [Improved Unbiased Watermark for Large Language Models](https://mlsanity.com/paper/2502.11268/) (2025)
- [A Watermark for Order-Agnostic Language Models](https://mlsanity.com/paper/2410.13805/) (2024)
- [De-mark: Watermark Removal in Large Language Models](https://mlsanity.com/paper/2410.13808/) (2024)
- [Can Watermarked LLMs be Identified by Users via Crafted Prompts?](https://mlsanity.com/paper/2410.03168/) (2024)
- [Dataset Protection via Watermarked Canaries in Retrieval-Augmented LLMs](https://mlsanity.com/paper/2502.10673/) (2025)
- [More Haste, Less Speed: Weaker Single-Layer Watermark Improves Distortion-Free Watermark Ensembles](https://mlsanity.com/paper/2602.11793/) (2026)
- [Hidden in Plain Tokens: Simply Robust, Gradient-Free Watermark for Synthetic Audio](https://mlsanity.com/paper/2605.25967/) (2026)
- [Robust Text Watermarking for Large Language Models via Dual Semantic Embeddings](https://mlsanity.com/paper/2606.31602/) (2026)
- [MarkTune: Improving the Quality-Detectability Trade-off in Open-Weight LLM Watermarking](https://mlsanity.com/paper/2512.04044/) (2025)

## Abstract (arXiv)

Language model (LM) watermarking techniques inject a statistical signal into LM-generated content by substituting the random sampling process with pseudo-random sampling, using watermark keys as the random seed. Among these statistical watermarking approaches, distortion-free watermarks are particularly crucial because they embed watermarks into LM-generated content without compromising generation quality. However, one notable limitation of pseudo-random sampling compared to true-random sampling is that, under the same watermark keys (i.e., key collision), the results of pseudo-random sampling exhibit correlations. This limitation could potentially undermine the distortion-free property. Our studies reveal that key collisions are inevitable due to the limited availability of watermark keys, and existing distortion-free watermarks exhibit a significant distribution bias toward the original LM distribution in the presence of key collisions. Moreover, achieving a perfect distortion-free watermark is impossible as no statistical signal can be embedded under key collisions. To reduce the distribution bias caused by key collisions, we introduce a new family of distortion-free watermarks--beta-watermark. Experimental results support that the beta-watermark can effectively reduce the distribution bias under key collisions.