# Watermarks in the Sand: Impossibility of Strong Watermarking for Generative Models

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

## Key facts

- Cited by 87 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 52 of its 78 references that are in the map.
- First posted on arXiv 7 Nov 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, 30 of 52)

- [Learning Transferable Visual Models From Natural Language Supervision](https://mlsanity.com/paper/2103.00020/) (2021)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [High-Resolution Image Synthesis with Latent Diffusion Models](https://mlsanity.com/paper/2112.10752/) (2021)
- [Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer](https://mlsanity.com/paper/1910.10683/) (2019)
- [RoBERTa: A Robustly Optimized BERT Pretraining Approach](https://mlsanity.com/paper/1907.11692/) (2019)
- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [Judging LLM-as-a-Judge with MT-Bench and Chatbot Arena](https://mlsanity.com/paper/2306.05685/) (2023)
- [Flamingo: a Visual Language Model for Few-Shot Learning](https://mlsanity.com/paper/2204.14198/) (2022)
- [Improved Techniques for Training GANs](https://mlsanity.com/paper/1606.03498/) (2016)
- [CLIPScore: A Reference-free Evaluation Metric for Image Captioning](https://mlsanity.com/paper/2104.08718/) (2021)
- [ImageReward: Learning and Evaluating Human Preferences for Text-to-Image Generation](https://mlsanity.com/paper/2304.05977/) (2023)
- [Human Preference Score v2: A Solid Benchmark for Evaluating Human Preferences of Text-to-Image Synthesis](https://mlsanity.com/paper/2306.09341/) (2023)
- [Show Your Work: Scratchpads for Intermediate Computation with Language Models](https://mlsanity.com/paper/2112.00114/) (2021)
- [A Generalist Agent](https://mlsanity.com/paper/2205.06175/) (2022)
- [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)
- [OpenAssistant Conversations -- Democratizing Large Language Model Alignment](https://mlsanity.com/paper/2304.07327/) (2023)
- [ELI5: Long Form Question Answering](https://mlsanity.com/paper/1907.09190/) (2019)
- [Defending Against Neural Fake News](https://mlsanity.com/paper/1905.12616/) (2019)
- [GLTR: Statistical Detection and Visualization of Generated Text](https://mlsanity.com/paper/1906.04043/) (2019)
- [Paraphrasing evades detectors of AI-generated text, but retrieval is an effective defense](https://mlsanity.com/paper/2303.13408/) (2023)
- [HiDDeN: Hiding Data With Deep Networks](https://mlsanity.com/paper/1807.09937/) (2018)
- [Can AI-Generated Text be Reliably Detected?](https://mlsanity.com/paper/2303.11156/) (2023)
- [The Curse of Recursion: Training on Generated Data Makes Models Forget](https://mlsanity.com/paper/2305.17493/) (2023)
- [Robust Distortion-free Watermarks for Language Models](https://mlsanity.com/paper/2307.15593/) (2023)
- [The Stable Signature: Rooting Watermarks in Latent Diffusion Models](https://mlsanity.com/paper/2303.15435/) (2023)
- [Provable Robust Watermarking for AI-Generated Text](https://mlsanity.com/paper/2306.17439/) (2023)
- [All That's 'Human' Is Not Gold: Evaluating Human Evaluation of Generated Text](https://mlsanity.com/paper/2107.00061/) (2021)
- [StegaStamp: Invisible Hyperlinks in Physical Photographs](https://mlsanity.com/paper/1904.05343/) (2019)
- [Embedding Watermarks into Deep Neural Networks](https://mlsanity.com/paper/1701.04082/) (2017)

## Built on by (most cited first, 30 of 87)

- [On the Learnability of Watermarks for Language Models](https://mlsanity.com/paper/2312.04469/) (2023)
- [Visibility into AI Agents](https://mlsanity.com/paper/2401.13138/) (2024)
- [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)
- [SoK: Watermarking for AI-Generated Content](https://mlsanity.com/paper/2411.18479/) (2024)
- [No Free Lunch in LLM Watermarking: Trade-offs in Watermarking Design Choices](https://mlsanity.com/paper/2402.16187/) (2024)
- [Pseudorandom Error-Correcting Codes](https://mlsanity.com/paper/2402.09370/) (2024)
- [Securing Large Language Models: Threats, Vulnerabilities and Responsible Practices](https://mlsanity.com/paper/2403.12503/) (2024)
- [AI-Generated Video Detection via Perceptual Straightening](https://mlsanity.com/paper/2507.00583/) (2025)
- [SynthID-Image: Image watermarking at internet scale](https://mlsanity.com/paper/2510.09263/) (2025)
- [Bypassing LLM Watermarks with Color-Aware Substitutions](https://mlsanity.com/paper/2403.14719/) (2024)
- [Towards Optimal Statistical Watermarking](https://mlsanity.com/paper/2312.07930/) (2023)
- [Optimizing watermarks for large language models](https://mlsanity.com/paper/2312.17295/) (2023)
- [Detecting AI-Generated Text: Factors Influencing Detectability with Current Methods](https://mlsanity.com/paper/2406.15583/) (2024)
- [Theoretically Grounded Framework for LLM Watermarking: A Distribution-Adaptive Approach](https://mlsanity.com/paper/2410.02890/) (2024)
- [Hidden in the Noise: Two-Stage Robust Watermarking for Images](https://mlsanity.com/paper/2412.04653/) (2024)
- [IDs for AI Systems](https://mlsanity.com/paper/2406.12137/) (2024)
- [Debiasing Watermarks for Large Language Models via Maximal Coupling](https://mlsanity.com/paper/2411.11203/) (2024)
- [Watermarking Language Models for Many Adaptive Users](https://mlsanity.com/paper/2405.11109/) (2024)
- [Revealing Weaknesses in Text Watermarking Through Self-Information Rewrite Attacks](https://mlsanity.com/paper/2505.05190/) (2025)
- [AI Risk Management Should Incorporate Both Safety and Security](https://mlsanity.com/paper/2405.19524/) (2024)
- [Adversarial Paraphrasing: A Universal Attack for Humanizing AI-Generated Text](https://mlsanity.com/paper/2506.07001/) (2025)
- [A Watermark for Black-Box Language Models](https://mlsanity.com/paper/2410.02099/) (2024)
- [Optimizing Adaptive Attacks against Watermarks for Language Models](https://mlsanity.com/paper/2410.02440/) (2024)
- [Data Authenticity, Consent, & Provenance for AI are all broken: what will it take to fix them?](https://mlsanity.com/paper/2404.12691/) (2024)
- [Decoding the AI Pen: Techniques and Challenges in Detecting AI-Generated Text](https://mlsanity.com/paper/2403.05750/) (2024)
- [Large Language Model Watermark Stealing With Mixed Integer Programming](https://mlsanity.com/paper/2405.19677/) (2024)
- [SoK: On the Role and Future of AIGC Watermarking in the Era of Gen-AI](https://mlsanity.com/paper/2411.11478/) (2024)
- [Excuse me, sir? Your language model is leaking (information)](https://mlsanity.com/paper/2401.10360/) (2024)
- [Edit Distance Robust Watermarks via Indexing Pseudorandom Codes](https://mlsanity.com/paper/2406.02633/) (2024)

## Abstract (arXiv)

Watermarking generative models consists of planting a statistical signal (watermark) in a model's output so that it can be later verified that the output was generated by the given model. A strong watermarking scheme satisfies the property that a computationally bounded attacker cannot erase the watermark without causing significant quality degradation. In this paper, we study the (im)possibility of strong watermarking schemes. We prove that, under well-specified and natural assumptions, strong watermarking is impossible to achieve. This holds even in the private detection algorithm setting, where the watermark insertion and detection algorithms share a secret key, unknown to the attacker. To prove this result, we introduce a generic efficient watermark attack; the attacker is not required to know the private key of the scheme or even which scheme is used. Our attack is based on two assumptions: (1) The attacker has access to a "quality oracle" that can evaluate whether a candidate output is a high-quality response to a prompt, and (2) The attacker has access to a "perturbation oracle" which can modify an output with a nontrivial probability of maintaining quality, and which induces an efficiently mixing random walk on high-quality outputs. We argue that both assumptions can be satisfied in practice by an attacker with weaker computational capabilities than the watermarked model itself, to which the attacker has only black-box access. Furthermore, our assumptions will likely only be easier to satisfy over time as models grow in capabilities and modalities. We demonstrate the feasibility of our attack by instantiating it to attack three existing watermarking schemes for large language models: Kirchenbauer et al. (2023), Kuditipudi et al. (2023), and Zhao et al. (2023). The same attack successfully removes the watermarks planted by all three schemes, with only minor quality degradation.