Refined Detection for Gumbel Watermarking

1. Problem Statement

The paper addresses the challenge of detecting watermarked text generated by Large Language Models (LLMs) without access to the model itself (model-agnostic detection).

• Context: Watermarking schemes embed a secret signal into the token selection process to distinguish AI-generated text from human text.
• Specific Focus: The authors focus on the Gumbel watermarking scheme proposed by Aaronson (2022). This scheme is "non-distortionary," meaning it samples tokens according to the model's original probability distribution $P_t$ while embedding a watermark via a secret key and pseudorandom noise.
• The Gap: While Aaronson's original detection method works, it relies on a statistic based on exponential distributions. The authors argue this is not statistically optimal, particularly in scenarios where the model's entropy varies or is low. The goal is to design a detection mechanism that is near-optimal in a problem-dependent sense, minimizing the number of tokens ($n$) required to detect the watermark with a given confidence level ($\delta$).

2. Methodology

A. The Gumbel Watermarking Mechanism (Recap)

The generation process (Algorithm 1) works as follows:

1. Given a secret key and previous tokens, a hash function generates a pseudorandom vector $U_t \in [0, 1]^\Sigma$.
2. The next token $A_t$ is selected via the Gumbel trick:
   $$A_t = \arg\max_{a \in \Sigma} \frac{P_t(a)}{-\log(U_{t,a})}$$
3. The detector reconstructs the noise variables $U_t$ using the key and the observed text. It then extracts $V_t = U_{t, A_t}$.
   • Null Hypothesis ($H_0$): If the text is not watermarked, $V_t$ are i.i.d. uniform on $[0, 1]$.
   • Alternative Hypothesis ($H_1$): If watermarked, $V_t$ follows a specific non-uniform distribution dependent on $P_t$.

B. The Proposed Detection Mechanism: Power Law Detection

The core contribution is replacing Aaronson's exponential statistic with a truncated power law statistic (Algorithm 3).

• The Statistic: Instead of using $S_t = \log(1/(1-V_t))$ (which leads to exponential tails), the authors define:
  $$S(u) = \min\left(\frac{1}{\sqrt{\epsilon}}, \frac{1}{\sqrt{1-u}}\right) - \mu$$
  where $\mu$ is a centering constant ensuring $\mathbb{E}[S(U)] = 0$ under $H_0$, and $\epsilon$ is a truncation parameter.
• Intuition: The term $\frac{1}{\sqrt{1-u}}$ creates a "heavy-tailed" distribution. Under the alternative hypothesis (watermarked), the values of $V_t$ tend to be smaller (closer to 0) for high-probability tokens, causing $1/\sqrt{1-V_t}$ to be large. The heavy tail amplifies these deviations more effectively than exponential statistics.
• Truncation: The $\min(\cdot, 1/\sqrt{\epsilon})$ term is crucial to control the variance under the null hypothesis, ensuring the false positive rate remains bounded.

C. Theoretical Framework

The authors define a new entropy-like quantity to characterize the difficulty of detection:
$$G_\epsilon(p) = \frac{G_1(p_\epsilon)}{\sqrt{\epsilon}} + G_{1/2}(p^c_\epsilon)$$
where $p_\epsilon$ and $p^c_\epsilon$ are the parts of the distribution below and above threshold $\epsilon$, respectively. This quantity captures the "detectability" of the distribution $p$.

3. Key Contributions

1. New Detection Statistic: Introduction of a truncated power law statistic that is theoretically more efficient than the previous exponential statistic for Gumbel watermarking.
2. Problem-Dependent Upper Bounds: The authors prove that detection occurs with high probability when the number of tokens $n$ satisfies:
   $$\sum_{t=1}^n G_\epsilon(P_t) = \Omega\left(\sqrt{n \log n \log(1/\delta)}\right)$$
   This bound depends on the specific entropy profile of the generated text, rather than just the average entropy.
3. Information-Theoretic Lower Bounds: The paper establishes a lower bound for any model-agnostic watermarking scheme in a symmetric setting. The lower bound matches the upper bound of the proposed scheme up to logarithmic factors, proving the scheme is nearly optimal.
4. Analysis of Subexponential Statistics: The authors demonstrate that statistics with subexponential tails (like the original exponential or Gaussian-based detectors) are inherently suboptimal for this problem. They require $n = \tilde{\Omega}(1/\bar{H}^2)$ tokens, whereas the proposed power law detector achieves $n = \tilde{\Omega}(1/\bar{H})$ in low-entropy regimes.

4. Key Results

• Theorem 2 (Upper Bound): If the sum of the $G_\epsilon$ quantities of the token distributions exceeds a threshold proportional to $\sqrt{n \log n}$, the detector returns "watermarked" with probability $\ge 1 - 2\delta$.
• Theorem 20 (Lower Bound): For any valid selection kernel and symmetric distribution of models, detection is impossible if $n$ is smaller than a bound determined by $\mathbb{E}[G_1(P_\epsilon)]$ and $\mathbb{E}[G_{1/2}(P^c_\epsilon)]^2$.
• Comparison with Aaronson (2022):
  • High Entropy: Both methods perform similarly.
  • Low Entropy (e.g., deterministic tokens): The new method is significantly faster. For a distribution with a small probability $\beta$ of being non-deterministic, the new method requires $n \approx O(1/\beta)$ tokens, while the old method requires $n \approx O(1/\beta^2)$.
• Examples:
  • Example 8 (Constant Low Entropy): Detection time scales with $1/(\beta(1-\beta))$.
  • Example 9 (Rare High Entropy): Detection time scales with $1/\beta^2$ for the old method vs. $1/\beta$ for the new method.

5. Significance and Discussion

• Theoretical Optimality: This work provides the first rigorous proof that a specific detector for Gumbel watermarking is nearly optimal among all model-agnostic schemes. It closes the gap between what is theoretically possible and what is achievable.
• Heavy-Tailed Statistics: The paper highlights a fundamental insight in statistical watermarking: heavy-tailed statistics are necessary for optimal detection when the signal (entropy) is sparse or variable. Standard subexponential statistics fail to capture the "rare but strong" signals present in low-entropy text.
• Practical Implications:
  • The method allows for faster detection of watermarked text, reducing the amount of data needed to confidently identify AI generation.
  • The authors note that while the theory is superior, empirical tests on real language data showed mixed results (slightly worse performance than the exponential detector), likely due to constant factors and the logarithmic gap. They suggest combining both detectors as a practical heuristic.
• Limitations: The detection relies on the assumption that the noise variables are independent and uniform under the null hypothesis. The paper acknowledges that pseudorandomness in practice introduces minor distortions, though empirical evidence suggests this does not significantly impact downstream tasks.

In summary, Lattimore refines the detection of Gumbel watermarks by introducing a heavy-tailed power law statistic, proving it is nearly optimal for detecting watermarks in text with varying entropy levels, and establishing fundamental limits on what any model-agnostic detector can achieve.