Technical Summary: WaterSearch

Problem Statement

Large Language Models (LLMs) require robust watermarking mechanisms to ensure accountability and identify machine-generated content. Existing methods, such as the KGW framework, typically rely on perturbing token-level probability distributions during generation. While effective for detection, these perturbations introduce a well-known trade-off: increasing watermark strength often degrades text quality, particularly in challenging scenarios like short-text generation, reasoning tasks, and low-entropy generation (e.g., code completion). Current attempts to mitigate this via entropy-aware heuristics or unbiased adjustments still rely on modifying token distributions under a fixed generation pipeline, which can deviate from the model's original behavior and fail to balance detectability with fidelity.

Methodology: WaterSearch

The authors propose WaterSearch, a search-based framework that shifts the perspective from token-level perturbations to seed-level control. The core insight is that watermark behavior varies significantly across different random seeds, leading to diverse trade-offs between detection strength and generation quality.

1. Seed Pooling and Parallel Generation

Instead of generating a single text sequence with a fixed seed, WaterSearch maintains a seed pool of global seeds at each generation step.

• Seed Pool Construction: A set of predefined seeds is permuted using a secret key ($\pi_{key}$) to ensure reproducibility for detection while introducing controlled variation.
• Parallel Candidates: For each chunk of text, the framework generates $k$ candidates in parallel: one standard unwatermarked sequence and $k-1$ watermarked sequences, each instantiated with a different seed from the pool.
• Efficiency: To manage computational cost, the system employs parallel generation with Key-Value (KV) cache reuse, reducing memory complexity from $O(k(L+T))$ to $O(k(L+m))$, where $m$ is the chunk size.

2. Candidate Selection

WaterSearch treats watermarking as a candidate selection problem. It evaluates the $k$ generated chunks using a weighted objective function $q(y, \tilde{y})$:
$$q(y, \tilde{y}) = \alpha q_{sim}(y, \tilde{y}) + (1 - \alpha) \frac{|\tilde{y}|_G}{|\tilde{y}|}$$
Where:

• $q_{sim}$ measures the similarity (lexical or semantic) between the candidate and the unwatermarked reference (fidelity).
• $\frac{|\tilde{y}|_G}{|\tilde{y}|}$ represents the proportion of "green list" tokens (detectability).
• $\alpha$ is a tunable hyperparameter balancing quality and detectability.
  The chunk with the highest score is selected and appended to the context for the next iteration.

3. Detection Strategy

Since the specific seed used for the selected chunk is not explicitly known to the detector, WaterSearch employs a max-statistic based hypothesis testing strategy:

• Chunk-Level Testing: For a given text chunk, the detector reconstructs the seed pool and evaluates the watermark statistic (number of green tokens) for all candidate seeds.
• Max-Statistic: It selects the maximum statistic observed across the seed pool. Under the null hypothesis ($H_0$, no watermark), the distribution of this maximum statistic is derived from the maximum of independent binomial variables.
• Aggregation: Chunk-level p-values are aggregated using Fisher's method to compute a document-level significance score. This approach is robust to token-level perturbations and paraphrasing because it accumulates evidence across multiple chunks.

Key Contributions

1. Seed-Level Perspective: The paper identifies that random seeds significantly influence watermark behavior and introduces seed pooling as a new mechanism to explore the quality–detectability trade-off space.
2. WaterSearch Framework: A practical, modular framework that generates and selects candidates under different seeds, compatible with existing token-level watermarking methods (e.g., KGW, GPT Watermark).
3. Robust Detection: A detection method based on seed-level statistical variation that does not require explicit seed identification, offering robustness against attacks.

Experimental Results

Experiments were conducted on WaterBench (spanning 10 tasks including short/long text, QA, and code) and RepoBench-P across three models (Qwen2.5-7B, Llama2-7B, InternLM-7B) and four watermark baselines.

• Overall Performance: WaterSearch consistently outperformed baseline methods across all settings, achieving an average absolute gain of approximately 5.5 points in the geometric mean (GM) of quality and detection metrics.
• Challenging Scenarios:
  • Short-text Generation: Significant improvements in detection success rates (e.g., +26.9 points in Copen, +3.7 in HotpotQA) where token budgets are limited.
  • Low-Entropy Generation: Notable gains in code completion tasks (LCC, RepoBench-P), with an average gain of 4.7 points, maintaining high text quality while improving detectability.
• Robustness: The method demonstrated superior resilience against insertion attacks, synonym substitution, and paraphrasing attacks (Pegasus, Parrot) compared to baselines.
• Ablation Studies:
  • Increasing the parallel beam size ($K$) improved both quality and detection, with even $K=2$ showing gains over baselines.
  • The trade-off factor $\alpha$ allows for flexible control, with WaterSearch achieving a better Pareto frontier than baselines.

Significance and Claims

The paper claims that treating randomness (random seeds) as a controllable variable offers a principled way to improve watermarking without fundamentally altering the token-level generation logic. By leveraging seed diversity, WaterSearch effectively navigates the quality–detectability trade-off, particularly in scenarios where traditional perturbation methods struggle. The authors emphasize that their approach is modular and compatible with existing watermarking schemes, providing a practical solution for deploying robust watermarks in real-world LLM applications.

The work acknowledges limitations, noting that it inherits the constraints of the underlying watermarking methods (e.g., KGW's potential impact on quality) and incurs additional computational overhead, though this is mitigated by KV-cache reuse. Future work is suggested to focus on improving sampling efficiency and reducing costs.