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

Fabrice Harel-Canada*, Boran Erol*, Connor Choi, Jason Liu, Gary Jiarui Song, Nanyun Peng, Amit Sahai · 2025

Read Sandcastles in the Storm: Revisiting the (Im)possibility of Strong Watermarking by Fabrice Harel-Canada*, Boran Erol*, Connor Choi, Jason Liu, Gary Jiarui Song, Nanyun Peng, Amit Sahai (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-06827.txt.

Introduction

Fabrice Harel-Canada and six co-authors stress test claims that AI text watermarks can always be erased in this 2025 paper. Recent theory argued that random walk attacks, which keep editing a text while a quality checker guards its sense, can dissolve any watermark.

The team ran large experiments and found the theory's assumptions shaky. Mixing is slow: after hundreds of edits, every perturbed text still carried traces of its origin. The quality checkers also faltered, judging edits with only seventy-seven percent accuracy, so errors piled up during attacks. Automated walks removed watermarks just twenty-six percent of the time, and only ten percent under human quality review. The authors conclude that watermarking is sturdier in practice than the models suggest.

Catalog record

CREATORFabrice Harel-Canada*, Boran Erol*, Connor Choi, Jason Liu, Gary Jiarui Song, Nanyun Peng, Amit Sahai
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE96 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-06827

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Sandcastles in the Storm: Revisiting the (Im)possibility of Strong Watermarking Fabrice Harel-Canada*, Boran Erol*, Connor Choi, Jason Liu, Gary Jiarui Song, Nanyun Peng, Amit Sahai Abstract 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. † † * Equal contribution. 1 Introduction The rapid proliferation of generative AI has created an urgent need for mechanisms to authenticate machine-generated content. Watermarking – embedding statistical signals into AI outputs to verify provenance – serves as a vital safeguard against misinformation, IP theft, and academic fraud. While traditional methods employ visual patterns (e.g., pixel-level changes in images), statistical watermarking for text encodes imperceptible signals at lexical or semantic levels through specially selected patterns of tokens Liu et al. (2024b) . However, recent work by Zhang et al. (2024) (“Watermarks in the Sand,” WITS) challenges the viability of watermarking, asserting that any such scheme can be defeated without degrading output quality through a simple random walk attack (see also, e.g., Kirchenbauer et al. (2024) ; Kuditipudi et al. (2024) ; Krishna et al. (2023) ). This impossibility result threatens to undermine the accountability and security of generative AI, leaving no viable path to enforce ethical standards or trace misuse. The text-based WITS attack employs two primary components: (1) a perturbation oracle \mathbf{P} that iteratively modifies text, and (2) a quality oracle \mathbf{Q} to ensure that the edits are reasonable. These induce a random walk on a (potentially enormous) graph \mathbf{G} , where nodes represent possible texts y and edges denote size-bounded perturbations (e.g., single-word swaps or paraphrases). Under certain assumptions, the random walk converges to a stationary distribution – a stable equilibrium over nodes that remains unchanged under further perturbations. Crucially, this stationary distribution is a function of \mathbf{P} and therefore independent of any particular watermarking scheme. As the random walk approaches this equilibrium, the likelihood of encountering a \mathbf{Q} -approved unwatermarked text increases. Notably, the WITS attack prioritizes quality equivalence over semantic equivalence: it seeks unwatermarked texts that score similarly under \mathbf{Q} , even if their meaning diverges significantly from the original. While elegant in theory, the WITS argument relies on two key assumptions (KA) that warrant further scrutiny. Specifically, WITS assumes that: KA1. The transition probabilities assigned to quality-preserving perturbations are high enough to ensure rapid mixing. Formally, this means that the second-largest eigenvalue (in absolute value) of the transition matrix is sufficiently close to zero to ensure rapid mixing ( Zhang et al. (2024) , Theorem 5). KA2. The quality oracle \mathbf{Q} can reliably preserve output quality throughout the attack. But if \mathbf{Q} is unreliable – either by admitting low-quality outputs or by blocking valid edits – the attack either fails to escape the watermark or produces low-quality outputs that are no longer competitive with the original. Taken together, KA1 is concerned with attack efficiency and KA2 further requires that the results remain meaningfully close to the initial text quality. To investigate whether these assumptions hold in practice, we designed analyses carefully tailored to study each assumption. For KA1 , acquiring the eigenvalues of the transition matrix is infeasible due to its intractable size. Instead, we approximate mixing behavior by testing whether random walks retain memory of their starting states. If the random walk efficiently mixes, perturbed texts should lose memory of their starting points, making them indistinguishable from those originating elsewhere in the graph. Conversely, if stationary mixing is slow, initial states should remain identifiable even after many perturbations. For KA2 , we crafted a dataset of perturbations annotated with human quality judgments and benchmarked a variety of automated oracles to determine their reliability. We then used the best oracle to guide the random-walk attacks and cross-checked the quality of the final perturbed texts to fairly estimate the robustness of several representative watermarking schemes – KGW Kirchenbauer et al. (2023) , SIR Liu et al. (2024a) , and Adaptive Liu and Bu (2024) . Our approach therefore addresses three primary research questions: RQ1. Can stationary distributions for watermarking be reached under practical constraints? Even after hundreds of perturbations, starting states remain 100% distinguishable, strongly suggesting that stationary distributions are not within efficient reach. RQ2. Are LLM-based quality oracles sophisticated enough to guide a random-walk attack? The top-performing oracle attained an F1-score of 77.4%, leaving significant room for errors to accumulate during the attack. This suggests that current generative oracles do not conform to the widely held belief that “verification is easier than generation.” RQ3. How effective are random-walk attacks in breaking watermarks when controlling for quality? Our improved random-walk attacks – whether operating on a word, span, sentence, or document level – succeeded in erasing the watermarks only 26.1% of the time on average. After humans reviewed the perturbed texts to determine if quality was truly preserved, success dropped to an average 10.5%. Overall, our findings demonstrate a disconnect between theoretical assumptions and practical realities. These findings highlight the trade-offs adversaries face: preserving quality necessitates minimal edits, but escaping detection requires riskier perturbations that compromise output quality. By bridging theoretical critique with empirical validation, this work challenges the inevitability of strong watermarking’s failure and offers a path forward for developing robust watermarking techniques grounded in real-world constraints. 2 Background In this section, we outline the main objects and assumptions that underpin our analysis, following Zhang et al. (2024) . For formal definitions and more details, refer to Appendix A . Let \mathbf{M} be a generative model mapping prompts x\in\mathcal{X} to outputs y\in\mathcal{Y} according to a probability distribution. Let \mathbf{Q}:\mathcal{X}\times\mathcal{Y}\to[0,1] be a function that returns a quality score for y as a response to prompt x . We assume that the adversary has oracle access to \mathbf{Q} . Notice that the watermarked model can be used as the quality oracle since we are not editing y using \mathbf{Q} , whether or not this is sufficient to approximate \mathbf{Q} is the content of KA2 . Let \mathbf{P}:\mathcal{X}\times\mathcal{Y}\to\mathcal{Y} be a randomized perturbation oracle that generates an alternative response y^{\prime} from an original response y for the same prompt x . For the attack to succeed, \mathbf{P} must preserve the quality of y with constant nonzero probability \epsilon_{\text{pert}}\in(0,1] (Definition A.1 ). Starting from a watermarked response y_{0} , we iteratively apply \mathbf{P} to generate mutations by setting y_{i}=\mathbf{P}(x,y_{i-1}) . To maintain high quality,

Read the complete text