# Sample Complexities of Estimating Gumbel--Max Watermark Proportions with and without Reduction to Pivotal Statistics

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 41 references that are in the map.
- First posted on arXiv 30 Jun 2026.

## Builds on (most cited first, 20 of 20)

- [Categorical Reparameterization with Gumbel-Softmax](https://mlsanity.com/paper/1611.01144/) (2016)
- [A Watermark for Large Language Models](https://mlsanity.com/paper/2301.10226/) (2023)
- [Robust Distortion-free Watermarks for Language Models](https://mlsanity.com/paper/2307.15593/) (2023)
- [Undetectable Watermarks for Language Models](https://mlsanity.com/paper/2306.09194/) (2023)
- [A* Sampling](https://mlsanity.com/paper/1411.0030/) (2014)
- [Mean estimation and regression under heavy-tailed distributions--a survey](https://mlsanity.com/paper/1906.04280/) (2019)
- [Unbiased Watermark for Large Language Models](https://mlsanity.com/paper/2310.10669/) (2023)
- [A Statistical Framework of Watermarks for Large Language Models: Pivot, Detection Efficiency and Optimal Rules](https://mlsanity.com/paper/2404.01245/) (2024)
- [Robust Detection of Watermarks for Large Language Models Under Human Edits](https://mlsanity.com/paper/2411.13868/) (2024)
- [Optimal estimation of high-dimensional location Gaussian mixtures](https://mlsanity.com/paper/2002.05818/) (2020)
- [Data Amplification: Instance-Optimal Property Estimation](https://mlsanity.com/paper/1903.01432/) (2019)
- [Optimal Estimation of Watermark Proportions in Hybrid AI-Human Texts](https://mlsanity.com/paper/2506.22343/) (2025)
- [On the Empirical Power of Goodness-of-Fit Tests in Watermark Detection](https://mlsanity.com/paper/2510.03944/) (2025)
- [Local moment matching: A unified methodology for symmetric functional estimation and distribution estimation under Wasserstein distance](https://mlsanity.com/paper/1802.08405/) (2018)
- [On the best approximation by finite Gaussian mixtures](https://mlsanity.com/paper/2404.08913/) (2024)
- [Optimal Detection for Language Watermarks with Pseudorandom Collision](https://mlsanity.com/paper/2510.22007/) (2025)
- [Optimal Estimation of Simultaneous Signals Using Absolute Inner Product with Applications to Integrative Genomics](https://mlsanity.com/paper/1801.08120/) (2018)
- [Refined Detection for Gumbel Watermarking](https://mlsanity.com/paper/2603.30017/) (2026)
- [Sharp Inequalities between Total Variation and Hellinger Distances for Gaussian Mixtures](https://mlsanity.com/paper/2602.03202/) (2026)
- [Adaptive Confidence Intervals in Efron's Gaussian Two-Groups Model](https://mlsanity.com/paper/2604.26992/) (2026)

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

- [Watermark Forensics for Generative Models: An Information-Theoretic Perspective](https://mlsanity.com/paper/2607.13003/) (2026)

## Abstract (arXiv)

Watermarking promises statistical traceability of large language model (LLM) uses, but real documents rarely arrive as purely human-written or purely LLM-generated. This motivates a quantitative question beyond detection: what proportion of a document is generated from a pre-specified watermarked LLM? We study this watermark proportion estimation problem under the Gumbel--max watermarking mechanism, treating the next-token prediction distributions as unknown and arbitrary nuisance parameters subject to a non-degeneracy condition. We compare two observation regimes: in the full observation regime, the estimator observes the pseudorandom vector and the selected token at each position; in the more prevalent setting of pivotal reduction, it observes only a scalar pivot, which follows a one-dimensional Uniform--Beta mixture distribution. Under pivotal reduction, we develop a Laguerre-polynomial estimator and establish a matching information-theoretic lower bound for the sample complexity. For full observation, we introduce an event-counting estimator and show a matching lower bound, yielding a substantially smaller sample complexity. As our results imply, although reducing to pivotal statistics is an elegant and prevalent choice, it is not always sample-efficient for estimating the proportion of watermarks.