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

• URL: http://arxiv.org/abs/2607.00224v2
• Date: Thu, 02 Jul 2026 02:56:41 GMT
• Title: Sample Complexities of Estimating Gumbel--Max Watermark Proportions with and without Reduction to Pivotal Statistics
• Abstract summary: Watermarking promises statistical traceability of large language model (LLM) uses, but real documents rarely arrive as purely human-written or purely LLM-generated.<n>We study this watermark proportion estimation problem under the Gumbel--max watermarking mechanism.<n>We develop a Laguerre-polynomial estimator and establish a matching information-theoretic lower bound for the sample complexity.
• Score: 4.346179456029564
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Minimax bounds for watermarked and masked recursive discrete distribution estimation [15.724207170366846]
  In the absence of a distinguishing mechanism, it has been shown that adding synthetic samples significantly reduces the marginal efficacy of new real samples.<n>We show that it is impossible to improve performance by adding watermarks unless the false negative rate of detection also vanishes.<n>We propose masking, a randomization procedure that narrows the gap in the remaining regimes to a Jensen gap.
  arXiv  Detail & Related papers  (2026-08-31T17:00:09Z)
• Hacking Generative Perplexity: Why Unconditional Text Evaluation Needs Distributional Metrics [49.443264461057645]
  Diffusion and continuous flow-based language models have emerged as the leading non-autoregressive alternatives to language modeling.<n>Progress in both paradigms is overwhelmingly tracked by generative perplexity (gen-PPL): the per-token negative log-likelihood of samples under a frozen autoregressive (AR) scorer.<n>We argue that this metric is unsound. By construction, gen-PPL measures only predictability under the scoring AR, not grammaticality or semantic coherence.
  arXiv  Detail & Related papers  (2026-06-07T02:35:56Z)
• Mind the Unseen Mass: Unmasking LLM Hallucinations via Soft-Hybrid Alphabet Estimation [1.1230191950153754]
  This paper studies uncertainty quantification for large language models under black-box access.<n> estimating the effective semantic alphabet size--that is, the number of distinct meanings expressed in the sampled responses--provides a useful proxy for downstream risk.<n>We propose SHADE, a simple and interpretable estimator that combines Good-Turing coverage with a heat- kernel trace of the normalized Laplacian.
  arXiv  Detail & Related papers  (2026-04-21T07:16:05Z)
• CLT and Edgeworth Expansion for m-out-of-n Bootstrap Estimators of The Studentized Median [5.267184810624153]
  The m-out-of-n bootstrap approximates the distribution of a statistic by repeatedly drawing m subsamples without replacement from an original sample of size n.<n>Despite its broad applicability across econometrics, biostatistics, and machine learning, rigorous parameter-free guarantees for the soundness of the bootstrap have remained elusive.<n>This paper establishes such guarantees by analyzing the estimator of sample quantiles obtained from m-out-of-n resampling of a dataset of size n.
  arXiv  Detail & Related papers  (2025-05-16T22:14:49Z)
• Nearly Optimal Sample Complexity for Learning with Label Proportions [54.67830198790247]
  We investigate Learning from Label Proportions (LLP), a partial information setting where examples in a training set are grouped into bags.<n>Despite the partial observability, the goal is still to achieve small regret at the level of individual examples.<n>We give results on the sample complexity of LLP under square loss, showing that our sample complexity is essentially optimal.
  arXiv  Detail & Related papers  (2025-05-08T15:45:23Z)
• Adaptive Sampled Softmax with Inverted Multi-Index: Methods, Theory and Applications [79.53938312089308]
  The MIDX-Sampler is a novel adaptive sampling strategy based on an inverted multi-index approach.<n>Our method is backed by rigorous theoretical analysis, addressing key concerns such as sampling bias, gradient bias, convergence rates, and generalization error bounds.
  arXiv  Detail & Related papers  (2025-01-15T04:09:21Z)
• Statistically Optimal Generative Modeling with Maximum Deviation from the Empirical Distribution [2.1146241717926664]
  We show that the Wasserstein GAN, constrained to left-invertible push-forward maps, generates distributions that avoid replication and significantly deviate from the empirical distribution. Our most important contribution provides a finite-sample lower bound on the Wasserstein-1 distance between the generative distribution and the empirical one. We also establish a finite-sample upper bound on the distance between the generative distribution and the true data-generating one.
  arXiv  Detail & Related papers  (2023-07-31T06:11:57Z)
• Detecting Adversarial Data by Probing Multiple Perturbations Using Expected Perturbation Score [62.54911162109439]
  Adversarial detection aims to determine whether a given sample is an adversarial one based on the discrepancy between natural and adversarial distributions. We propose a new statistic called expected perturbation score (EPS), which is essentially the expected score of a sample after various perturbations. We develop EPS-based maximum mean discrepancy (MMD) as a metric to measure the discrepancy between the test sample and natural samples.
  arXiv  Detail & Related papers  (2023-05-25T13:14:58Z)
• Statistical Efficiency of Score Matching: The View from Isoperimetry [96.65637602827942]
  We show a tight connection between statistical efficiency of score matching and the isoperimetric properties of the distribution being estimated. We formalize these results both in the sample regime and in the finite regime.
  arXiv  Detail & Related papers  (2022-10-03T06:09:01Z)
• Rethinking Collaborative Metric Learning: Toward an Efficient Alternative without Negative Sampling [156.7248383178991]
  Collaborative Metric Learning (CML) paradigm has aroused wide interest in the area of recommendation systems (RS) We find that negative sampling would lead to a biased estimation of the generalization error. Motivated by this, we propose an efficient alternative without negative sampling for CML named textitSampling-Free Collaborative Metric Learning (SFCML)
  arXiv  Detail & Related papers  (2022-06-23T08:50:22Z)
• On Variance Estimation of Random Forests [0.0]
  This paper develops an unbiased variance estimator based on incomplete U-statistics. We show that our estimators enjoy lower bias and more accurate confidence interval coverage without additional computational costs.
  arXiv  Detail & Related papers  (2022-02-18T03:35:47Z)
• Unrolling Particles: Unsupervised Learning of Sampling Distributions [102.72972137287728]
  Particle filtering is used to compute good nonlinear estimates of complex systems. We show in simulations that the resulting particle filter yields good estimates in a wide range of scenarios.
  arXiv  Detail & Related papers  (2021-10-06T16:58:34Z)
• Estimating Gradients for Discrete Random Variables by Sampling without Replacement [93.09326095997336]
  We derive an unbiased estimator for expectations over discrete random variables based on sampling without replacement. We show that our estimator can be derived as the Rao-Blackwellization of three different estimators.
  arXiv  Detail & Related papers  (2020-02-14T14:15:18Z)

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.