Optimal Detection for Language Watermarks with Pseudorandom Collision

• URL: http://arxiv.org/abs/2510.22007v1
• Date: Fri, 24 Oct 2025 20:21:52 GMT
• Title: Optimal Detection for Language Watermarks with Pseudorandom Collision
• Authors: T. Tony Cai, Xiang Li, Qi Long, Weijie J. Su, Garrett G. Wen,
• Abstract summary: We introduce a statistical framework that captures structure through a hierarchical two-layer partition.<n>At its core is the concept of minimal units -- the smallest groups treatable as independent across units while permitting dependence within.<n>Applying to Gumbel-max and inverse-transform watermarks, our framework produces closed-form optimal rules.
• Score: 28.84134119819056
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Text watermarking plays a crucial role in ensuring the traceability and accountability of large language model (LLM) outputs and mitigating misuse. While promising, most existing methods assume perfect pseudorandomness. In practice, repetition in generated text induces collisions that create structured dependence, compromising Type I error control and invalidating standard analyses. We introduce a statistical framework that captures this structure through a hierarchical two-layer partition. At its core is the concept of minimal units -- the smallest groups treatable as independent across units while permitting dependence within. Using minimal units, we define a non-asymptotic efficiency measure and cast watermark detection as a minimax hypothesis testing problem. Applied to Gumbel-max and inverse-transform watermarks, our framework produces closed-form optimal rules. It explains why discarding repeated statistics often improves performance and shows that within-unit dependence must be addressed unless degenerate. Both theory and experiments confirm improved detection power with rigorous Type I error control. These results provide the first principled foundation for watermark detection under imperfect pseudorandomness, offering both theoretical insight and practical guidance for reliable tracing of model outputs.

Related papers

• 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)
• Beyond Raw Detection Scores: Markov-Informed Calibration for Boosting Machine-Generated Text Detection [105.14032334647932]
  Machine-generated texts (MGTs) pose risks such as disinformation and phishing, highlighting the need for reliable detection.<n> Metric-based methods, which extract statistically distinguishable features of MGTs, are often more practical than complex model-based methods that are prone to overfitting.<n>We propose a Markov-informed score calibration strategy that models two relationships of context detection scores that may aid calibration.
  arXiv  Detail & Related papers  (2026-02-08T16:06:12Z)
• Improve the Trade-off Between Watermark Strength and Speculative Sampling Efficiency for Language Models [18.988823703120865]
  Speculative sampling accelerates inference, with efficiency improving as the acceptance rate increases.<n>Recent work reveals a fundamental trade-off: higher watermark strength reduces acceptance, preventing their simultaneous achievement.<n>We introduce a measure of watermark strength that governs statistical detectability and is maximized when tokens are deterministic functions of pseudorandom numbers.
  arXiv  Detail & Related papers  (2026-02-01T20:30:59Z)
• Scalable, Explainable and Provably Robust Anomaly Detection with One-Step Flow Matching [14.503330877000758]
  Time-Conditioned Contraction Matching is a novel method for semi-supervised anomaly detection in tabular data.<n>It is inspired by flow matching, a recent generative modeling framework that learns velocity fields between probability distributions.<n>Extensive experiments on the ADBench benchmark show that TCCM strikes a favorable balance between detection accuracy and inference cost.
  arXiv  Detail & Related papers  (2025-10-21T06:26:38Z)
• 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)
• PMark: Towards Robust and Distortion-free Semantic-level Watermarking with Channel Constraints [49.2373408329323]
  We introduce a new theoretical framework on watermark-leveling (SWM) for large language models (LLMs)<n>We propose PMark, a simple yet powerful SWM method that estimates the median next sentence dynamically through sampling channels.<n> Experimental results show that PMark consistently outperforms existing SWM baselines in both text quality and paraphrasing.
  arXiv  Detail & Related papers  (2025-09-25T12:08:31Z)
• 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)
• Towards Optimal Statistical Watermarking [95.46650092476372]
  We study statistical watermarking by formulating it as a hypothesis testing problem. Key to our formulation is a coupling of the output tokens and the rejection region. We characterize the Uniformly Most Powerful (UMP) watermark in the general hypothesis testing setting.
  arXiv  Detail & Related papers  (2023-12-13T06:57:00Z)
• Prototype-based Aleatoric Uncertainty Quantification for Cross-modal Retrieval [139.21955930418815]
  Cross-modal Retrieval methods build similarity relations between vision and language modalities by jointly learning a common representation space. However, the predictions are often unreliable due to the Aleatoric uncertainty, which is induced by low-quality data, e.g., corrupt images, fast-paced videos, and non-detailed texts. We propose a novel Prototype-based Aleatoric Uncertainty Quantification (PAU) framework to provide trustworthy predictions by quantifying the uncertainty arisen from the inherent data ambiguity.
  arXiv  Detail & Related papers  (2023-09-29T09:41:19Z)

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.