# Optimal Detection for Language Watermarks with Pseudorandom Collision

arXiv: https://arxiv.org/abs/2510.22007 · HTML: https://mlsanity.com/paper/2510.22007/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Placed in Watermarking generated content and models, one of 12 directions in LLM safety and security.
- First posted on arXiv 24 Oct 2025.

## Placed in

- LLM safety and security / [Watermarking generated content and models](https://mlsanity.com/safety/watermarking-generated-content-and-models/)

## Built on by (most cited first, 3 of 3)

- [Sample Complexities of Estimating Gumbel--Max Watermark Proportions with and without Reduction to Pivotal Statistics](https://mlsanity.com/paper/2607.00224/) (2026)
- [LLM Watermarking as Big Data Provenance: A Deployment-Oriented Systematization](https://mlsanity.com/paper/2607.10103/) (2026)
- [textGrain watermarking is harder to detect: can sum-tests still do it optimally?](https://mlsanity.com/paper/2610.17655/) (2026)

## Abstract (arXiv)

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.