Universally Optimal Watermarking Schemes for LLMs: from Theory to Practice

Haiyun He, Yepeng Liu, Ziqiao Wang, Yongyi Mao, Yuheng Bu

Abstract

Watermarking has emerged as a crucial method to distinguish AI-generated text from human-created text. In this paper, we present a novel theoretical framework for watermarking Large Language Models (LLMs) that jointly optimizes both the watermarking scheme and the detection process. Our approach focuses on maximizing detection performance while maintaining control over the worst-case Type-I error and text distortion. We characterize the universally minimum Type-II error, showing a fundamental trade-off between watermark detectability and text distortion. Importantly, we identify that the optimal watermarking schemes are adaptive to the LLM generative distribution. Building on our theoretical insights, we propose an efficient, model-agnostic, distribution-adaptive watermarking algorithm (DAWA), utilizing a surrogate model alongside the Gumbel-max trick. Experiments conducted on Llama2-13B and Mistral-8x7B models confirm the effectiveness of our approach. Additionally, we examine incorporating robustness into our framework, paving a way to future watermarking systems that withstand adversarial attacks more effectively.

Introduction

As Large Language Models (LLMs) become ubiquitous, distinguishing AI-generated text from human-written content is a critical challenge for academic integrity, misinformation control, and content accountability. "In-process" watermarking—where a hidden signal is embedded during the text generation phase—is the preferred solution because it is invisible and has negligible latency.

However, existing watermarking schemes often suffer from three major flaws:

  1. Heuristic Design: Most methods rely on empirical tuning rather than formal optimality guarantees.
  2. Disconnected Optimization: Researchers usually design the watermark embedder and the detector separately, missing out on the performance gains of a jointly optimized system.
  3. The "Low-Entropy" Trap: It is notoriously difficult to watermark text that has very little randomness (e.g., a list of names or a famous quote) without either triggering false positives or ruining the text quality.

Methods: The DAWA Framework

We treat watermarking as a constrained optimization problem: maximize the True Positive Rate (TPR) while strictly controlling the False Positive Rate (FPR) and minimizing "distortion" (changes to the original text distribution).

The resulting Distribution-Adaptive Watermarking Algorithm (DAWA) introduces several key innovations:

  • Joint Optimization: We derive closed-form solutions for a pair of embedders and detectors that are mathematically "universally optimal."
  • Distribution Adaptivity: The best watermarking schemes must adapt to the LLM’s Next-Token Prediction (NTP) distribution. Instead of using a fixed "green-red" list, the signal strength varies based on how much "room" the current token's probability distribution allows.
  • The Surrogate Model Trick: A major hurdle in watermarking is that the detector usually doesn't have access to the original LLM's internal probabilities (logits). DAWA solves this by using a Surrogate Language Model (SLM)—a smaller, off-the-shelf model—to approximate the generative distribution during detection.
  • Gumbel-Max Sampling: We utilize the Gumbel-Max trick to ensure the watermarking process remains "distortion-free," meaning the statistical properties of the generated text are identical to the unwatermarked model.
Overview of the DAWA framework for watermark generation and detection using a surrogate model.

Key Insights

  • Entropy as the Bottleneck: The fundamental limit of watermark detectability is tied to the LLM's generative distribution. Low-entropy text is mathematically harder to watermark; DAWA handles this by being "adaptive," essentially being more cautious when the model is very certain about the next token.
  • Model-Agnostic Detection: The detector doesn't need the exact model used for generation. As long as the Surrogate Language Model (SLM) shares the same tokenizer and a similar "understanding" of language, detection remains highly effective.
  • Redundant Signals: The optimal design includes a "redundant" auxiliary sequence. If the text is too predictable (low entropy), the system maps it to this redundant state, which effectively lowers the false positive rate for human-written text that happens to look like AI output.

Experimental Evaluation

We evaluated DAWA across several benchmarks to test performance in different linguistic contexts, including C4 (RealNews) for high-entropy journalistic content, ELI5 for low-entropy long-form question answering, and Wikipedia for large-scale testing at ultra-low FPRs (down to $10^{-5}$).

Key Results

DAWA significantly outperformed state-of-the-art baselines (like KGW and Gumbel-Max) at ultra-low False Positive Rates. For example, at an FPR of $10^{-5}$, DAWA maintained a much higher TPR than its competitors.

ROC curve comparing DAWA's performance against state-of-the-art watermarking schemes.

Furthermore, because the algorithm is built on a distortion-free sampling framework, the perplexity and BLEU scores of the watermarked text were nearly identical to unwatermarked human-level text. The method also proved resilient to "token replacement attacks." Even when 50% of the tokens were replaced by another model (T5-large), DAWA maintained high ROC-AUC scores, outperforming existing heuristic methods.

Discussion and Future Work

While DAWA represents a significant step forward, some limitations remain. Surrogate Mismatch can occur if there are extreme differences in model "knowledge" between the generator and the detector. Additionally, while robust to token swapping, the current framework primarily focuses on token-level statistics. Future work should extend this to "semantic-invariant" attacks, such as heavy paraphrasing or translation. Finally, while generation latency is negligible, the detector's requirement to run an SLM makes it more computationally expensive than simple hash-based detectors.

Summary updated

Abstract

Watermarking has emerged as a crucial method to distinguish AI-generated text from human-created text. In this paper, we present a novel theoretical framework for watermarking Large Language Models (LLMs) that jointly optimizes both the watermarking scheme and the detection process. Our approach focuses on maximizing detection performance while maintaining control over the worst-case Type-I error and text distortion. We characterize \emph{the universally minimum Type-II error}, showing a fundamental trade-off between watermark detectability and text distortion. Importantly, we identify that the optimal watermarking schemes are adaptive to the LLM generative distribution. Building on our theoretical insights, we propose an efficient, model-agnostic, distribution-adaptive watermarking algorithm, utilizing a surrogate model alongside the Gumbel-max trick. Experiments conducted on Llama2-13B and Mistral-8$\times$7B models confirm the effectiveness of our approach. Additionally, we examine incorporating robustness into our framework, paving a way to future watermarking systems that withstand adversarial attacks more effectively.
BibTeX
@misc{he2024universally,
  author = {Haiyun He and Yepeng Liu and Ziqiao Wang and Yongyi Mao and Yuheng Bu},
  title = {{Universally Optimal Watermarking Schemes for LLMs: from Theory to Practice}},
  year = {2024},
  eprint = {2410.02890},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2410.02890},
}
Figure