# Sandcastles in the Storm: Revisiting the (Im)possibility of Strong Watermarking

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 44 references that are in the map.
- First posted on arXiv 11 May 2025.

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

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [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)
- [TruthfulQA: Measuring How Models Mimic Human Falsehoods](https://mlsanity.com/paper/2109.07958/) (2021)
- [Learning to summarize from human feedback](https://mlsanity.com/paper/2009.01325/) (2020)
- [Chatbot Arena: An Open Platform for Evaluating LLMs by Human Preference](https://mlsanity.com/paper/2403.04132/) (2024)
- [A Watermark for Large Language Models](https://mlsanity.com/paper/2301.10226/) (2023)
- [Prometheus 2: An Open Source Language Model Specialized in Evaluating Other Language Models](https://mlsanity.com/paper/2405.01535/) (2024)
- [Paraphrasing evades detectors of AI-generated text, but retrieval is an effective defense](https://mlsanity.com/paper/2303.13408/) (2023)
- [Interpretable Preferences via Multi-Objective Reward Modeling and Mixture-of-Experts](https://mlsanity.com/paper/2406.12845/) (2024)
- [Skywork-Reward: Bag of Tricks for Reward Modeling in LLMs](https://mlsanity.com/paper/2410.18451/) (2024)
- [Robust Distortion-free Watermarks for Language Models](https://mlsanity.com/paper/2307.15593/) (2023)
- [MarkLLM: An Open-Source Toolkit for LLM Watermarking](https://mlsanity.com/paper/2405.10051/) (2024)
- [Watermarks in the Sand: Impossibility of Strong Watermarking for Generative Models](https://mlsanity.com/paper/2311.04378/) (2023)
- [A Robust Semantics-based Watermark for Large Language Model against Paraphrasing](https://mlsanity.com/paper/2311.08721/) (2023)
- [Quantile Regression for Distributional Reward Models in RLHF](https://mlsanity.com/paper/2409.10164/) (2024)
- [No Free Lunch in LLM Watermarking: Trade-offs in Watermarking Design Choices](https://mlsanity.com/paper/2402.16187/) (2024)
- [Revisiting the Robustness of Watermarking to Paraphrasing Attacks](https://mlsanity.com/paper/2411.05277/) (2024)
- [Optimizing Adaptive Attacks against Watermarks for Language Models](https://mlsanity.com/paper/2410.02440/) (2024)

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

- [SLAM: Structural Linguistic Activation Marking for Language Models](https://mlsanity.com/paper/2605.05443/) (2026)
- [Robust LLM Watermarking with Minimal Semantic Distortion for IP Protection](https://mlsanity.com/paper/2605.23175/) (2026)
- [Beyond AI-Generated Labels: Watermarking, Co-Creation, and Conflation of AI-Generation with Disinformation](https://mlsanity.com/paper/2607.13082/) (2026)
- [Pin It on Anyone: Certified Targeted Displacement of Multi-Bit LLM Watermarks Without the Key](https://mlsanity.com/paper/2610.18359/) (2026)

## Abstract (arXiv)

Watermarking AI-generated text is critical for combating misuse. Yet recent theoretical work argues that any watermark can be erased via random walk attacks that perturb text while preserving quality. However, such attacks rely on two key assumptions: (1) rapid mixing (watermarks dissolve quickly under perturbations) and (2) reliable quality preservation (automated quality oracles perfectly guide edits). Through large-scale experiments and human-validated assessments, we find mixing is slow: 100% of perturbed texts retain traces of their origin after hundreds of edits, defying rapid mixing. Oracles falter, as state-of-the-art quality detectors misjudge edits (77% accuracy), compounding errors during attacks. Ultimately, attacks underperform: automated walks remove watermarks just 26% of the time -- dropping to 10% under human quality review. These findings challenge the inevitability of watermark removal. Instead, practical barriers -- slow mixing and imperfect quality control -- reveal watermarking to be far more robust than theoretical models suggest. The gap between idealized attacks and real-world feasibility underscores the need for stronger watermarking methods and more realistic attack models.