Research map / Learning theory and algorithms / Sample complexity
Watermarks in the Sand: Impossibility of Strong Watermarking for Language Models
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proves that strong watermarking of generative models is impossible under quality-oracle and perturbation-oracle assumptions, and demonstrates a generic random-walk attack that removes LM and image watermarks with minor quality loss.
Problem
Strong watermarks for generative model outputs should resist removal by computationally bounded attackers without quality degradation; it is unclear whether such schemes are achievable.
Approach
Shows a generic quality-preserving random-walk attack: using a quality oracle and a perturbation oracle, rejection-sampled random walks over high-quality outputs reach a non-watermarked output of equal or higher quality, so strong watermarking is impossible even in the secret-key setting.
Key results
- On Llama-2-7B, the attack reduces KGW watermark z-score from 6.236 to 1.628 with GPT-4 judge score -0.0877 (near zero, i.e., similar quality).
- Unigram z-score-equivalent p-value rises from 4.563e-11 to 0.208 after attack, with GPT-4 judge -0.0812.
- On SDXL image watermarks, Stable Signature p-value rises from 5.9404e-6 to 0.0589 with CLIPScore 33.91 to 33.40.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Apply the proposed attack to KGW-watermarked outputs | KGW on Llama2-7B · C4 Real News | z-score: 6.236 →1.628 | Helped |
| Apply the proposed attack to Unigram-watermarked outputs | Unigram on Llama2-7B · C4 Real News | z-score: 8.210 →1.456 | Helped |
| Apply the proposed attack to EXP-watermarked outputs | EXP on Llama2-7B · C4 Real News | z-score: 3.540 → 0.745 | Helped |
| Apply the proposed attack to KGW-watermarked outputs | KGW on Llama2-7B · C4 Real News | GPT-4 Judge: -0.0877 | Hurt |
| Apply the proposed attack to Unigram-watermarked outputs | Unigram on Llama2-7B · C4 Real News | GPT-4 Judge: -0.0812 | Hurt |
| Apply the proposed attack to EXP-watermarked outputs | EXP on Llama2-7B · C4 Real News | GPT-4 Judge: -0.0675 | Hurt |
| Apply the proposed attack to Stable Signature-watermarked images | Stable Signature on sdxl-turbo · Image prompts | p-value: 5.9404e-6 →0.0589 | Helped |
| Apply the proposed attack to Invisible Watermark images | Invisible Watermark on stable-diffusion-xl · Image prompts | p-value: 1.793e-5 →0.206 | Helped |
| Apply the proposed attack to Stable Signature-watermarked images | Stable Signature on sdxl-turbo · Image prompts | CLIP score: 33.91 →33.40 | Hurt |
| Apply the proposed attack to Invisible Watermark images | Invisible Watermark on stable-diffusion-xl · Image prompts | CLIP score: 35.64 →35.51 | Hurt |
Surprising findings
- Watermarked model itself can serve as quality oracle, so attacker need not be stronger than the watermarked model.
Limitations
- Attack is not the most efficient for specific schemes; requires many perturbation steps.
- Quality oracle is imperfect (reward models and GPT-3.5 used), so results depend on proxy quality.
- Image experiments are preliminary, using a small sample of 141 valid examples.
Experimental setup
Datasets: C4 Real News
Benchmarks: C4 Real News completion Stable Diffusion image watermark prompts
Metrics: z-score p-value GPT-4 judge score CLIPScore
Baselines: KGW (Kirchenbauer et al., 2023a) Unigram (Zhao et al., 2023a) EXP (Kuditipudi et al., 2023) Invisible Watermark (Mountain, 2021) Stable Signature (Fernandez et al., 2023)
Builds on: KGW watermark Kuditipudi et al. 2023 EXP watermark Unigram watermark
Closest papers by meaning
- Break the Trade-off Between Watermark Strength and Speculative Sampling Efficiency for Language Models (ICLR 2026 · similarity 0.91)
- Edit Distance Robust Watermarks via Indexing Pseudorandom Codes (NeurIPS 2024 · similarity 0.91)
- Inevitable Trade-off between Watermark Strength and Speculative Sampling Efficiency for Language Models (NeurIPS 2024 · similarity 0.91)
- On the Learnability of Watermarks for Language Models (ICLR 2024 · similarity 0.90)
- Optimizing Adaptive Attacks against Watermarks for Language Models (ICML 2025 · similarity 0.90)
- Black-Box Detection of Language Model Watermarks (ICLR 2025 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.