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

• URL: http://arxiv.org/abs/2607.21958v1
• Date: Fri, 24 Jul 2026 04:10:36 GMT
• Title: Efficient Online LLM Watermark Detection via Rao-Blackwellized E-Processes
• Abstract summary: We develop an efficient online watermark detection framework with anytime-valid inference based on Rao-Blackwellized e-processes.<n> Simulations and experiments on real-generated text demonstrate efficient online detection with rigorous anytime-valid guarantees.
• Score: 3.2639022787260266
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• PURA: Provably Unbiased and Robust Multi-Bit Watermarking for AI-Generated Text Attribution [83.66032773976904]
  We present PURA, a provably unbiased and robust multi-bit watermarking method for text attribution.<n>Instead of perturbing token probabilities directly, PURA embeds payloads in the latent sampling space via keyed inverse transform sampling.<n>We show that PURA substantially outperforms existing unbiased baselines in the high-payload regime.
  arXiv  Detail & Related papers  (2026-08-23T04:44:27Z)
• A Locally Tokenized Generative Model for Robust Time-Series Watermarking [12.477366787279747]
  We show that existing detectors, which rely on globally coupled re-encoding, suffer from bidirectional drift of the null distribution under post-editing attacks.<n>We propose L-VQVAE, a generative model in which each discrete token is produced from a short contiguous window, and LVQMark, a watermarking method over this token space.
  arXiv  Detail & Related papers  (2026-08-20T07:25:41Z)
• PromptMark: A Prompt-Guided Iterative-Feedback Framework for Source Code Watermarking [0.5798758080057375]
  We propose PromptMark, a black-box, prompt-guided watermarking framework.<n>It embeds invisible yet statistically detectable signals into generated code via structured input instructions.<n>Experiments show that PromptMark consistently achieves strong watermark detectability while maintaining high code correctness.
  arXiv  Detail & Related papers  (2026-06-18T18:21:38Z)
• Towards Anytime-Valid Statistical Watermarking [63.02116925616554]
  We develop the first e-value-based watermarking framework, Anchored E-Watermarking, that unifies optimal sampling with anytime-valid inference.<n>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.
  arXiv  Detail & Related papers  (2026-02-19T18:32:26Z)
• Online LLM watermark detection via e-processes [3.0870861759929977]
  We develop a unified framework for watermark detection based on e-processes.<n>We propose various methods to construct empirically adaptive e-processes that can enhance the detection power.<n>Some experiments demonstrate that the proposed framework achieves competitive performance compared to existing watermark detection methods.
  arXiv  Detail & Related papers  (2026-02-15T19:37:06Z)
• An Ensemble Framework for Unbiased Language Model Watermarking [60.99969104552168]
  We propose ENS, a novel ensemble framework that enhances the detectability and robustness of unbiased watermarks.<n>ENS sequentially composes multiple independent watermark instances, each governed by a distinct key, to amplify the watermark signal.<n> Empirical evaluations show that ENS substantially reduces the number of tokens needed for reliable detection and increases resistance to smoothing and paraphrasing attacks.
  arXiv  Detail & Related papers  (2025-09-28T19:37:44Z)
• Character-Level Perturbations Disrupt LLM Watermarks [64.60090923837701]
  We formalize the system model for Large Language Model (LLM) watermarking.<n>We characterize two realistic threat models constrained on limited access to the watermark detector.<n>We demonstrate character-level perturbations are significantly more effective for watermark removal under the most restrictive threat model.<n> Experiments confirm the superiority of character-level perturbations and the effectiveness of the Genetic Algorithm (GA) in removing watermarks under realistic constraints.
  arXiv  Detail & Related papers  (2025-09-11T02:50:07Z)
• Entropy-Guided Watermarking for LLMs: A Test-Time Framework for Robust and Traceable Text Generation [58.85645136534301]
  Existing watermarking schemes for sampled text often face trade-offs between maintaining text quality and ensuring robust detection against various attacks.<n>We propose a novel watermarking scheme that improves both detectability and text quality by introducing a cumulative watermark entropy threshold.
  arXiv  Detail & Related papers  (2025-04-16T14:16:38Z)
• GaussMark: A Practical Approach for Structural Watermarking of Language Models [61.84270985214254]
  GaussMark is a simple, efficient, and relatively robust scheme for watermarking large language models.<n>We show that GaussMark is reliable, efficient, and relatively robust to corruptions such as insertions, deletions, substitutions, and roundtrip translations.
  arXiv  Detail & Related papers  (2025-01-17T22:30:08Z)
• Theoretically Grounded Framework for LLM Watermarking: A Distribution-Adaptive Approach [53.32564762183639]
  We introduce a novel, unified theoretical framework for watermarking Large Language Models (LLMs)<n>Our approach aims to maximize detection performance while maintaining control over the worst-case false positive rate (FPR) and distortion on text quality.<n>We propose a distortion-free, distribution-adaptive watermarking algorithm (DAWA) that leverages a surrogate model for model-agnosticism and efficiency.
  arXiv  Detail & Related papers  (2024-10-03T18:28:10Z)
• A Statistical Framework of Watermarks for Large Language Models: Pivot, Detection Efficiency and Optimal Rules [27.382399391266564]
  We introduce a framework for reasoning about the statistical efficiency of watermarks and powerful detection rules.<n>We derive optimal detection rules for watermarks under our framework.
  arXiv  Detail & Related papers  (2024-04-01T17:03:41Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.