Problem-dependent optimality of Li et al. (2025) detector

Determine whether the model-agnostic detector proposed by Li, Ruan, Wang, Long, and Su (2025), which is optimal in an asymptotic minimax framework under the assumption that max_{a ∈ Σ} P_t(a) ≤ 1 − Δ for some fixed Δ ∈ (0,1), achieves near-optimal problem-dependent detection efficiency comparable to the power-law detector for Gumbel watermarking described in this paper.

Background

Li et al. (2025) analyze detection for watermarking and propose a model-agnostic detector that attains asymptotic optimality in a minimax sense, assuming a uniform bound Δ on the maximum next-token probability. Their guarantees target worst-case distributions within that constraint class.

This paper introduces a power-law based detection statistic for the Gumbel watermarking scheme and proves near-optimal detection times in a problem-dependent sense under i.i.d. next-token assumptions. Because minimax and problem-dependent optimality notions can yield different sample-complexity characterizations, it remains unresolved whether Li et al.’s detector can match the problem-dependent efficiency demonstrated here.

References

Like us, also examine the problem of refining the detection of Gumbel watermarking (and the scheme by ). They propose a model-agnostic detector that is optimal in an asymptotic minimax framework where P_t is assumed to satisfy \max_{a \in \Sigma} P_t(a) \leq 1 - \Delta for some user-provided constant \Delta \in (0,1). On the one hand, they are able to establish a kind of exact optimality. On the other hand, thanks to the minimax nature of their optimality definition, it is unclear if their method achieves the same kind of near-optimal problem-dependent detection efficiency as our proposal.

— Refined Detection for Gumbel Watermarking  (2603.30017 - Lattimore, 31 Mar 2026) in Related work