Towards Anytime-Valid Statistical Watermarking

Baihe Huang; Eric Xu; Kannan Ramchandran; Jiantao Jiao; Michael I. Jordan

cs.LGFeb 19, 2026

Towards Anytime-Valid Statistical Watermarking

Authors: Baihe Huang, Eric Xu, Kannan Ramchandran, Jiantao Jiao, Michael I. Jordan

Organizations: University of California, Berkeley.

Abstract

The proliferation of Large Language Models (LLMs) necessitates efficient mechanisms to distinguish machine-generated content from human text. While statistical watermarking has emerged as a promising solution, existing methods suffer from two critical limitations: the lack of a principled approach for selecting sampling distributions and the reliance on fixed-horizon hypothesis testing, which precludes valid early stopping. In this paper, we bridge this gap by developing the first e-value-based watermarking framework, Anchored E-Watermarking, that unifies optimal sampling with anytime-valid inference. Unlike traditional approaches where optional stopping invalidates Type-I error guarantees, our framework enables valid, anytime-inference by constructing a test supermartingale for the detection process. By leveraging an anchor distribution to approximate the target model, we characterize the optimal e-value with respect to the worst-case log-growth rate and derive the optimal expected stopping time. Our theoretical claims are substantiated by simulations and evaluations on established benchmarks, showing that our framework can significantly enhance sample efficiency, reducing the average token budget required for detection by 13-15% relative to state-of-the-art baselines.

Figures & tables

Panel of Figure 1 — Figure 1: Simulation of the two-token case for the log growth problem in Eq. ( 2 ). Three separate anchor distributions are used each with parameter $\delta=0.01$ . We solve the simplified maxmin problem using the CLARABEL interior point method solver which is run for $30$ steps. The theoretical optimum is computed as in Eq. ( 5 ).

Panel of Figure 2 — Figure 2: Simulation of the two-token case for the stopping time problem $\text{SC}(e^{*})$ . We simulate for three different anchor distributions $p_{0}=\begin{bmatrix}p&1-p\end{bmatrix}$ with $\delta=0.1$ and estimate average stopping times $\mathbb{E}[\tau_{\alpha}]$ for $\alpha$ values ranging from $10^{-2}$ to $10^{-120}$ . Each $\mathbb{E}[\tau_{\alpha}]$ is estimated by simulating $10000$ stopping times $\tau_{\alpha}$ . The plots above display graphs of $\frac{\mathbb{E}[\tau_{\alpha}]}{\log(1/\alpha)}$ with red dashed lines equal to $1/J^{*}$ where $J^{*}$ is as in Eq. ( 5 ). We observe that convergence to the theoretical optimum is obtained for sufficiently small $\alpha$ .

Scheme	Quality ( $\uparrow$ )	Size ( $\downarrow$ )
Exponential	0.907	$\infty$
Inverse Transform	0.917	734.0
Binary	0.919	$\infty$
Distribution Shift	0.912	145.0
SEAL	0.901	84.5
Theorem 4.1	0.919	72.0

Table 1: Comparison of our e-value-based watermarking scheme in Theorem 4.1 with baselines across quality and size. We report the median over different private keys and perturbation methods. The best result in each category is highlighted in bold.

\infty

size suggests over half of the watermarked generations fail to be detected after perturbation. E-value-based watermarking demonstrates higher efficiency comparing with all baselines.

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Temp.	Exponential	Inverse Transform	Binary	Distribution Shift	SEAL	Theorem 4.1
0.3	0.906	0.910	0.905	0.900	0.905	0.909
0.7	0.907	0.917	0.919	0.912	0.901	0.919
1.0	0.898	0.917	0.905	0.907	0.871	0.902

Appendix

Table 2: Quality (

\uparrow

) across different temperature settings. Best (per temperature) is highlighted in bold.

Temp.	Exponential	Inverse Transform	Binary	Distribution Shift	SEAL	Theorem 4.1
0.3	$\infty$	$\infty$	$\infty$	112.5	106.0	97.0
0.7	$\infty$	734.0	$\infty$	145.0	84.5	72.0
1.0	240.5	163.5	$\infty$	317.0	133.0	97.5

Appendix

Table 3: Size (

\downarrow

) across different temperature settings. Best (per temperature) is highlighted in bold.

LLM Watermarking

Large language model watermarking embeds or detects signals in text and models to trace provenance, ownership, and unauthorized use.

See all 111 papers

Efficient Online LLM Watermark Detection via Rao-Blackwellized E-Processes
Jul 24, 2026Lu Luo, Dandan Mo, Chengdong Xu +4LLM Watermarking Sequential Hypothesis Testing
Yunnan Key Laboratory of Statistical Modeling and Data Analysis, Yunnan University, Kunming, China · School of Statistics and Management, Shanghai University of Finance and Economics, Shanghai, China
A Unified Attack Framework against Statistical Generative Watermarks for Large Language Models
Oct 20, 2026Romina Omidi, Nima Naderloui, Yuan Hong +1LLM Watermarking Robustness of Machine-Generated Text Detection
Illinois Institute of Technology · University of Connecticut
Flip, Don't Shuffle: Watermarking LLMs at the Speed of Inference
Sep 3, 2026Simone Ceppi, Ignacio SanchezLLM Watermarking
European Commission Joint Research Centre Ispra, Italy

Jul 24, 2026J/K move · Enter open · S save

Efficient Online LLM Watermark Detection via Rao-Blackwellized E-Processes

Lu Luo, Dandan Mo, Chengdong Xu, Ting Li+3

Yunnan Key Laboratory of Statistical Modeling and Data Analysis, Yunnan University, Kunming, China · School of Statistics and Management, Shanghai University of Finance and Economics, Shanghai, China

LLM Watermarking Sequential Hypothesis Testing

Open paper AskPDF arXiv

As large language models (LLMs) are increasingly deployed, reliable and efficient mechanisms for distinguishing AI-generated text from human-written content have become essential. Statistical watermarking has emerged as a promising solution, yet most existing methods are typically fixed-horizon procedures, precluding valid early stopping in streaming generation. In this paper, we develop an efficient online watermark detection framework with anytime-valid inference based on Rao-Blackwellized e-processes, enabling recursive token-level evidence updates without storing the full history. In particular, we instantiate the framework for the Gumbel-max watermark and reduce the original token-level dependence testing problem to a pivot-induced sequential testing problem with an explicit null distribution. Theoretically, we prove anytime-valid Type I error control under arbitrary optional stopping and establish positive asymptotic log-growth under watermarking, implying consistency of the proposed stopping rules. Simulations and experiments on real LLM-generated text demonstrate efficient online detection with rigorous anytime-valid guarantees.

Abstract

LLM Watermarking

Explore similar work

Efficient Online LLM Watermark Detection via Rao-Blackwellized E-Processes

A Unified Attack Framework against Statistical Generative Watermarks for Large Language Models

Flip, Don't Shuffle: Watermarking LLMs at the Speed of Inference