HeavyWater and SimplexWater: Distortion-free LLM Watermarks for Low-Entropy Distributions

Large language model (LLM) watermarks enable authentication of text provenance, curb misuse of machine-generated text, and promote trust in AI systems. Current watermarks operate by changing the next-token predictions output by an LLM. The updated (i.e., watermarked) predictions depend on random side information produced, for example, by hashing previously generated tokens. LLM watermarking is particularly challenging when next-token predictions are near-deterministic. In fact, over 90% of next-token distributions are low-entropy, with more than half of the probability mass on a single token. In this paper, we propose an optimization framework for watermark design for this regime. Our goal is to understand how to most effectively use random side information to optimize the detection-quality trade-off. Our analysis informs the design of two new watermarks: HeavyWater and SimplexWater. Both watermarks are tunable, gracefully trading-off between detection accuracy and text distortion. They can also be applied to any LLM and are agnostic to side information generation. We evaluate the performance of HeavyWater and SimplexWater across several benchmarks, demonstrating that they achieve superior detection with minimal degradation in downstream quality across generation tasks. Our theoretical analysis also reveals surprising new connections between LLM watermarking and coding theory.