Abstract
Misuse of LLM-generated text can be curbed by watermarking techniques that embed implicit signals into the output. We propose a watermark that partitions the vocabulary at each decoding step into three sets (Green/Yellow/Red) with fixed ratios and restricts sampling to the Green and Yellow sets. At detection time, we replay the same partitions, compute Green-enrichment and Red-depletion statistics, convert them to one-sided z-scores, and aggregate their p-values via Fisher's method to decide whether a passage is watermarked. We implement generation, detection, and testing on Llama 2 7B, and evaluate true-positive rate, false-positive rate, and text quality. Results show that the triple-partition scheme achieves high detection accuracy at fixed FPR while preserving readability.
Introduction
As Large Language Models (LLMs) become ubiquitous, the risk of their misuse for generating misinformation, academic dishonesty, or automated social engineering has skyrocketed. To trace AI-generated text, researchers use "watermarking"—embedding hidden statistical patterns into the text during generation.
The current standard for generation-based watermarking (like the popular KGW method) splits the vocabulary into two lists: a "Green" list (favored) and a "Red" list (penalized). However, these dual-list methods face a harsh trade-off: they often suffer from low detection success rates and are vulnerable to simple edits, or they degrade the naturalness of the generated text too much. HATS (High-Accuracy Triple-Set) bridges this gap, aiming for high detection accuracy and low false positives without ruining the semantic quality of the output.
Methodology
HATS introduces a novel triple-set watermarking technique that modifies both the generation and detection phases of LLM watermarking.
Generation: Triple-Partitioning
Instead of two lists, HATS pseudo-randomly partitions the vocabulary into three disjoint subsets: Green, Yellow, and Red. This partition is determined by a hash of the previous context tokens.
- Green tokens receive a positive probability bias to encourage their selection.
- Yellow tokens receive a slight negative bias to discourage them while maintaining semantic diversity.
- Red tokens are strictly prohibited, with their probability set to zero.
Detection: Poisson-Binomial & Fisher's Method
The detector recreates the token partitions using the same hash function and looks for two distinct signals: an unusually high number of Green tokens (Green enrichment) and an unusually low number of Red tokens (Red depletion).
Instead of assuming a simple binomial distribution, HATS uses a Poisson-binomial distribution. This better models the reality that token probabilities change at every step due to context shifts and sampling truncations. The detector calculates one-sided $p$-values for both signals and combines them using Fisher's method to make a final "Watermarked or Clean" decision.
Experimental Setup
The authors evaluated HATS on LLaMA-2-7B using two primary datasets:
- Alpaca Dataset: 600 instruction-response pairs used to evaluate watermark embedding and True Positive Rate (TPR).
- Mixed Human-Written Corpus: 600 samples from WikiText, IMDB, AG News, and Yelp to evaluate the False Positive Rate (FPR).
Results and Discussion
HATS was compared against several baselines, including KGW, KGW2, OpenAI, and Marylandz.
Detection Performance
HATS significantly outperformed all baselines in detection accuracy. It achieved a 61.67% TPR, nearly doubling the performance of the original KGW method (38.83%).
Furthermore, HATS achieved the lowest False Positive Rate at just 0.50% (3/600 false alarms on human text), compared to KGW's 2.00%.
Text Quality
While HATS introduces a strict prohibition of Red tokens, it maintains high readability. In perplexity evaluations, it ranked second overall, trailing only the original KGW method. This suggests that the triple-partition scheme successfully balances the strength of the watermark signal with the naturalness of the generated text.
Conclusion
The HATS framework demonstrates that dual-evidence detection—combining Green enrichment and Red depletion—is far more robust than single-signal methods. By utilizing a Poisson-binomial distribution and Fisher's method, HATS provides a more realistic and powerful statistical foundation for LLM watermarking. Future work will focus on refining the algorithm to further improve contextual coherence and testing robustness against adversarial attacks like paraphrasing.
Summary updated