Refined Detection for Gumbel Watermarking

Tor Lattimore

cs.LGMar 31, 2026

Refined Detection for Gumbel Watermarking

Authors: Tor Lattimore

Organizations: Google DeepMind

Abstract

We propose a simple detection mechanism for the Gumbel watermarking scheme proposed by Aaronson (2022). The new mechanism is proven to be near-optimal in a problem-dependent sense among all model-agnostic watermarking schemes under the assumption that the next-token distribution is sampled i.i.d.

Figures & tables

Panel of Figure 1 — Algorithm 1: The watermarking algorithm accepts a secret key and a model and autoregressively samples a sequence of tokens until the token is sampled. The function uses its input to compute a pseudorandom vector $U_{t}$ uniformly distributed on $[0,1]^{\Sigma}$ .

Panel of Figure 2 — Algorithm 2: The detection algorithm accepts the secret key, the confidence level $\delta\in(0,1)$ that controls the false positive rate and the sequence of tokens to be evaluated. The is a well-chosen statistical test that the $(V_{t})_{t=1}^{n}$ are independent and uniformly distributed on $[0,1]$ at confidence level $\delta$ . Various options are available as we discuss in Section 2 and Section 3 .

Panel of Figure 3 — Algorithm 3: The power law detection algorithm accepts the secret key, the confidence level $\delta\in(0,1)$ that controls the false positive rate and the sequence of tokens to be evaluated.

Watermark Removal Detection

See all 11 papers

textGrain watermarking is harder to detect: can sum-tests still do it optimally?
Oct 13, 2026Swapnaneel Bhattacharyya, Soham BonnerjeeWatermark Removal Detection LLM Watermarking
University of Pennsylvania
Optimal Multi-bit Generative Watermarking Schemes Under Worst-Case False-Alarm Constraints
Apr 9, 2026Yu-Shin Huang, Chao Tian, Krishna NarayananMulti-Bit Watermarking Text Watermarking
AutoMark: Enabling Autoresearch to Discover Better LLM Watermarks
Sep 29, 2026Thibaud Gloaguen, Robin Staab, Martin VechevText Watermarking LLM Watermarking
ETH Zurich

Oct 13, 2026J/K move · Enter open · S save

textGrain watermarking is harder to detect: can sum-tests still do it optimally?

Swapnaneel Bhattacharyya, Soham Bonnerjee

University of Pennsylvania

Watermark Removal Detection LLM Watermarking Robust Watermarking

Open paper AskPDF arXiv

Watermarking embeds an imperceptible signal in text from large language models that is statistically detectable with a secret key. The recent textGrain watermark (Li et. al. (2026b)) calibrates this signal against the model's sampling entropy through an explicit entropy budget, combining the stochasticity of Red-Green and the unbiasedness of Gumbel-max watermarks, and its accompanying report proposes a detector that sums pivotal statistics. We study when, and how efficiently, textGrain can be detected after human edits, modeled as a sparse mixture in which a fraction

\varepsilon_n\asymp n^{-p}

of positions retain the watermark and token uncertainty decays as

n^{-q}

. First, entropy calibration comes at a cost: the minimax detection boundary of textGrain is

p+q=1/2

, so its detectable region is strictly smaller than that of Gumbel-max and maximal-coupling watermarks, whose boundary is

2p+q=1

. This cost stems from textGrain's construction rather than from entropy calibration itself: an unbiased scheme with the same entropy loss remains detectable where textGrain is not. Second, perhaps surprisingly, this loss makes the sum detector optimal at the boundary when the number of transport columns is fixed, unlike for Gumbel-max. When the number of columns grows and the entropy budget does not vanish, the detectable region expands while that of the sum detector does not. Third, for a fixed edit fraction, we characterize the optimal exponential rate of type II error decay and show that the sum detector falls strictly short of it at every fixed alternative. Finally, we propose a weighted multiscale binomial scan, valid in finite samples and needing no knowledge of the next-token distributions, entropy budget, or edit fraction; it attains every detection boundary above and the optimal exponent.

Abstract

Watermark Removal Detection

Explore similar work

textGrain watermarking is harder to detect: can sum-tests still do it optimally?

Optimal Multi-bit Generative Watermarking Schemes Under Worst-Case False-Alarm Constraints

AutoMark: Enabling Autoresearch to Discover Better LLM Watermarks