Universally Optimal Watermarking Schemes for LLMs: from Theory to Practice

Haiyun He, Yepeng Liu, Ziqiao Wang, Yongyi Mao, Yuheng BuSubmission to ICLR 2025 · Rejected

TL;DR

This paper introduces a mathematically grounded framework that jointly optimizes both the text watermarking rule and the detector for Large Language Models (LLMs). By formulating detection as an independence hypothesis test, the authors establish the theoretical limit of detection (the universally minimum Type-II error) under worst-case false-alarm and distortion constraints, then implement an efficient, model-agnostic watermarking scheme using a small surrogate language model and the Gumbel-max trick.

What Problem Does This Paper Address?

Watermarking AI-generated text is vital for mitigating risks like plagiarism, automated disinformation, and model misuse. An ideal LLM watermarking scheme must satisfy several competing goals:

  1. Detectability: High detection rate while strictly bounding false positives (Type-I error) across arbitrary human text.
  2. Quality (Distortion-Free): Preserving the natural output distribution of the LLM.
  3. Model-Agnosticism: Allowing detection without access to the generating model's weights, prompts, or proprietary parameters.
  4. Robustness: Resisting text perturbations and semantic-preserving edits.

Prior theoretical work studied detectors for heuristic watermarking schemes or optimized schemes for specific non-model-agnostic detectors, often assuming independence across tokens. This paper provides the first framework that jointly optimizes the watermarking scheme and the model-agnostic detector while providing universal theoretical guarantees.

Methods

  • Joint Independence Testing Formulation: Text generation and detection are formulated as distinguishing between $H_0$ (human text: generated tokens $X_1^T$ and auxiliary watermark random sequence $\zeta_1^T$ are independent) and $H_1$ (watermarked text: $X_1^T$ depends on $\zeta_1^T$).
  • Optimal Detector Characterization: The authors prove that universally optimal detectors must belong to a specific family: $\gamma(X_1^T, \zeta_1^T) = \mathbf{1}\{X_1^T = g(\zeta_1^T)\}$ for a surjective mapping $g$.
  • Redundant Auxiliary Symbols: To control worst-case Type-I error on low-entropy text (where certain tokens appear with probability exceeding the false-alarm constraint $\alpha$), the optimal scheme transfers excess probability mass into a designated "redundant" auxiliary state $\tilde{\zeta}$ that the detector never accepts.
  • Practical Token-Level Algorithm with Surrogate Models: Because the generating model's next-token prediction (NTP) distribution is inaccessible during model-agnostic detection, the authors employ a smaller Surrogate Language Model (SLM) sharing the same tokenizer (e.g., Llama2-7B detecting Llama2-13B). Combined with the Gumbel-max trick, the detector reproduces the pseudo-random sampling choices at each token without knowing the original prompt.
Generation: LLM NTP + Gumbel-Max Key  ──►  Watermarked Text
                                                  │
Detection:  Text  ──►  SLM NTP + Gumbel-Max Key  ──►  Test Statistic ≥ λ

Datasets

The authors evaluate their method on two standard natural language benchmarks:

  • C4 (Realnewslike subset): An open-ended, high-entropy dataset of journalistic text mimicking news articles.
  • ELI5: A relatively low-entropy long-form question-answering dataset where detailed explanations are prompted by user questions.

(No new datasets were created for this paper.)

Key Insights and Ideas

  • Entropy Dictates Detection Limits: The fundamental minimum Type-II error depends strictly on the entropy of the original LLM distribution. Low-entropy distributions are inherently harder to watermark without distortion because capping false alarms requires diverting probability mass away from watermarking toward the redundant state $\tilde{\zeta}$.
  • Distortion Restores Detectability: Allowing a bounded total variation distortion ($\epsilon > 0$) directly counteracts the detection penalty imposed by low-entropy text by redistributing probability mass below the false-alarm threshold.
  • Surrogate Models Circumvent the Black-Box Bottleneck: In theory, optimal detection requires the exact marginal probability distribution. In practice, a lightweight surrogate model (SLM) provides an NTP distribution close enough to preserve near-optimal detection performance.

Key Results

Experiments evaluated on Llama2-13B (with a Llama2-7B surrogate) and Mistral-8×7B (with a Mistral-7B surrogate) against baselines KGW-1, EXP-edit, and Gumbel-Max:

  • Unmodified Watermark Detection: On low-entropy ELI5 text, the proposed method achieved 0.998 ROC-AUC and 0.997 True Positive Rate (TPR) at 1% False Positive Rate (FPR) on Llama-13B (Mistral-8×7B reached 0.999 ROC-AUC / 0.999 TPR@1% FPR), outperforming EXP-edit (0.960 and 0.972 TPR@1% FPR).
  • Token Replacement Robustness: Under an attack where 50% of tokens were randomly masked and replaced via T5-large (~35% actual replaced tokens), the scheme retained 0.989–0.995 ROC-AUC and 0.860–0.991 TPR@1% FPR, whereas Gumbel-Max collapsed to 0.326–0.402 TPR@1% FPR.
  • Empirical False-Alarm Verification: Tested on 8,000 unwatermarked sequences, empirical false positive rates closely tracked theoretical $\alpha$ bounds (e.g., theoretical $9.4 \times 10^{-3}$ yielded an empirical $1.1 \times 10^{-4}$).

Limitations and Future Work

  • Inference Overhead at Detection: Unlike hash-based detectors that compute simple frequency counts, this approach requires running forward passes through an SLM during detection.
  • Full Robustness Implementation: While the paper develops an $f$-robust theoretical framework for semantic-preserving equivalence classes, implementing semantic hashing functions that are both computationally efficient and provably robust against insertion, deletion, and full paraphrasing remains open for future engineering.

Summary updated

Abstract

Large Language Models (LLMs) boosts human efficiency but also poses misuse risks, with watermarking serving as a reliable method to differentiate AI-generated content from human-created text. In this work, we propose a novel theoretical framework for watermarking LLMs. Particularly, we jointly optimize both the watermarking scheme and detector to maximize detection performance, while controlling the worst-case Type-I error and distortion in the watermarked text. Within our framework, we characterize the _universally minimum Type-II error_, showing a fundamental trade-off between detection performance and distortion. More importantly, we identify the optimal type of detectors and watermarking schemes. Building upon our theoretical analysis, we introduce a practical, model-agnostic and computationally efficient token-level watermarking algorithm that invokes a surrogate model and the Gumbel-max trick. Empirical results on Llama-13B and Mistral-8$\times$7B demonstrate the effectiveness of our method. Furthermore, we also explore how robustness can be integrated into our theoretical framework, which provides a foundation for designing future watermarking systems with improved resilience to adversarial attacks.
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},
}

Loading related content...

Figure