Watermarking Low-entropy Generation for Large Language Models: An Unbiased and Low-risk Method

Minjia Mao, Dongjun Wei, Zeyu Chen, Xiao Fang, Michael Chau

TL;DR

The researchers propose STA-1 (Sampling One Then Accepting), a novel watermarking method for LLMs that is mathematically unbiased and significantly safer for "low-entropy" tasks like code generation. Unlike previous methods that can degrade text quality by forcing unlikely word choices, STA-1 preserves the original model's distribution while enabling fast, black-box detection with strong statistical guarantees.

What Problem Does This Paper Address?

As LLMs become ubiquitous, the ability to distinguish between human-written and AI-generated text is critical for safety and accountability. Watermarking—the process of subtly altering the model's token selection to embed a hidden signal—is a leading solution.

However, existing watermarking techniques face a major hurdle: low-entropy scenarios. In tasks like writing Python code or stating mathematical facts, there are often very few "correct" next tokens. If a watermarking algorithm forces the model to pick a "green-listed" token that has a low probability, the code might break or the facts might become garbled.

Current "unbiased" watermarks (which maintain the model's original probability distribution on average) can still be "high-risk" because they increase the variance of the output. This means that while they look fine across a million samples, any single generation might be a "hallucinated" mess.

Methods

The authors introduce two primary algorithms:

  1. STA-1 (Sampling One Then Accepting): This is the core "unbiased" method. At each step:
  2. The model samples a candidate token from its original distribution.
  3. If that token is in the "green list" (determined by a secret hash of the previous token), it is accepted.
  4. If it is in the "red list," the model denies it and samples a second token from the original distribution, which it always accepts.
  5. Why it works: This "two-strike" rule is mathematically proven to be unbiased. Because it only allows at most one resample, it minimizes the "risk" of deviating too far from the model's best guess.
  6. STA-M: An extension designed for better robustness. It uses a heuristic entropy threshold. If the model is very certain (low entropy), it uses STA-1 to protect quality. If the model is uncertain (high entropy), it allows up to $M$ resamples to "force" a green token, making the watermark much harder to remove through attacks.

Detection: The method uses a standard $z$-test to count green tokens. It is "black-box," meaning the detector doesn't need the original prompt or the model itself—just the secret key used to generate the green/red lists.

Datasets

The authors evaluated their methods on two distinct types of data:

  • C4 (Subset): A high-entropy dataset consisting of news-like natural language text.
  • HumanEval: A low-entropy dataset consisting of 164 Python coding problems used to test if the watermark breaks functional code.

Key Insights and Ideas

  • Unbiased $\neq$ Low-Risk: This is the paper's "aha moment." Previous researchers argued that if a watermark is unbiased, it won't hurt quality. The authors prove that variance matters. A high-variance unbiased watermark might technically be "correct" on average but will frequently produce "unsatisfactory" individual outputs in sensitive tasks like coding.
  • The Gini Connection: The authors use the Gini Index to provide statistical guarantees for their detection. They show that a higher Gini Index (lower uncertainty) in the model's output actually makes the watermark easier to detect with high confidence.
  • Efficiency is King: Some competing unbiased methods (like RDW) require complex permutations that make detection incredibly slow. STA-1's simplicity allows for near-instant detection.

Key Results

  • Code Integrity: On the HumanEval (code) dataset, STA-1 achieved the highest pass@k scores among unbiased methods, meaning it was the least likely to "break" the code it was watermarking.
  • Risk Reduction: STA-1 demonstrated significantly lower variance in perplexity compared to competitors like Dipmark and RDW, confirming it is "lower risk" for low-entropy generation.
  • Detection Speed: STA-1 detected watermarks in 500 sequences in roughly 46 seconds, whereas the RDW method took nearly 4 hours for the same task.
  • Robustness: The STA-M variant proved highly robust against "copy-paste" attacks and paraphrasing attacks (using tools like GPT-3.5 or DIPPER), outperforming the standard biased KGW watermark in several attack scenarios.

Limitations and Future Work

  • The Low-Entropy Ceiling: While STA-1 is better than its predecessors, watermarking extremely low-entropy text (where only one token is ever valid) remains an open challenge. If there's only one possible word, you can't change it without changing the meaning.
  • Sequence-Level Context: The current method operates at the token level. The authors suggest that future work could incorporate "context code history" to make the watermark even more resilient to heavy editing.
  • Attack Sophistication: While robust against current paraphrasers, the "arms race" between watermarking and AI-driven watermark removal continues.

Summary updated

Abstract

Recent advancements in large language models (LLMs) have highlighted the risk of misusing them, raising the need for accurate detection of LLM-generated content. In response, a viable solution is to inject imperceptible identifiers into LLMs, known as watermarks. Our research extends the existing watermarking methods by proposing the novel Sampling One Then Accepting (STA-1) method. STA-1 is an unbiased watermark that preserves the original token distribution in expectation and has a lower risk of producing unsatisfactory outputs in low-entropy scenarios compared to existing unbiased watermarks. In watermark detection, STA-1 does not require prompts or a white-box LLM, provides statistical guarantees, demonstrates high efficiency in detection time, and remains robust against various watermarking attacks. Experimental results on low-entropy and high-entropy datasets demonstrate that STA-1 achieves the above properties simultaneously, making it a desirable solution for watermarking LLMs. Implementation codes for this study are available online.
BibTeX
@misc{mao2024watermarking,
  author = {Minjia Mao and Dongjun Wei and Zeyu Chen and Xiao Fang and Michael Chau},
  title = {{Watermarking Low-entropy Generation for Large Language Models: An Unbiased and Low-risk Method}},
  year = {2024},
  eprint = {2405.14604},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2405.14604},
}
Figure