{"ID":5552854,"CreatedAt":"2026-07-02T01:54:51.863792489Z","UpdatedAt":"2026-07-03T21:54:35.419828569Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.00224","arxiv_id":"2607.00224","title":"Sample Complexities of Estimating Gumbel--Max Watermark Proportions with and without Reduction to Pivotal Statistics","abstract":"Watermarking promises a statistical trace of large language model (LLM) use, but real documents, after editing or paraphrasing, rarely arrive as purely human-written or purely machine-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 (NTP) 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; under the more popular 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 widely used procedure, it is not always sample-efficient for estimating the proportion of watermarks.","short_abstract":"Watermarking promises a statistical trace of large language model (LLM) use, but real documents, after editing or paraphrasing, rarely arrive as purely human-written or purely machine-generated. This motivates a quantitative question beyond detection: what proportion of a document is generated from a pre-specified wate...","url_abs":"https://arxiv.org/abs/2607.00224","url_pdf":"https://arxiv.org/pdf/2607.00224v1","authors":"[\"Shuwen Chai\",\"Qiaosen Wang\"]","published":"2026-06-30T22:04:35Z","proceeding":"math.ST","tasks":"[\"math.ST\",\"cs.IT\",\"cs.LG\",\"stat.ML\"]","methods":"[\"Large Language Model\",\"Language Model\",\"Generative Adversarial Network\"]","has_code":false}