# Flip, Don't Shuffle: Watermarking LLMs at the Speed of Inference

arXiv: https://arxiv.org/abs/2609.03844 · HTML: https://mlsanity.com/paper/2609.03844/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Watermarking generated content and models, one of 12 directions in LLM safety and security.
- Builds on 15 of its 25 references that are in the map.
- First posted on arXiv 3 Sep 2026.

## Placed in

- LLM safety and security / [Watermarking generated content and models](https://mlsanity.com/safety/watermarking-generated-content-and-models/)

## Builds on (most cited first, 15 of 15)

- [Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer](https://mlsanity.com/paper/1910.10683/) (2019)
- [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://mlsanity.com/paper/2309.06180/) (2023)
- [A Watermark for Large Language Models](https://mlsanity.com/paper/2301.10226/) (2023)
- [Contrastive Decoding: Open-ended Text Generation as Optimization](https://mlsanity.com/paper/2210.15097/) (2022)
- [Neural Text Generation with Unlikelihood Training](https://mlsanity.com/paper/1908.04319/) (2019)
- [Robust Distortion-free Watermarks for Language Models](https://mlsanity.com/paper/2307.15593/) (2023)
- [Provable Robust Watermarking for AI-Generated Text](https://mlsanity.com/paper/2306.17439/) (2023)
- [Adversarial Watermarking Transformer: Towards Tracing Text Provenance with Data Hiding](https://mlsanity.com/paper/2009.03015/) (2020)
- [Watermark Stealing in Large Language Models](https://mlsanity.com/paper/2402.19361/) (2024)
- [Watermarks in the Sand: Impossibility of Strong Watermarking for Generative Models](https://mlsanity.com/paper/2311.04378/) (2023)
- [On the Learnability of Watermarks for Language Models](https://mlsanity.com/paper/2312.04469/) (2023)
- [A Statistical Framework of Watermarks for Large Language Models: Pivot, Detection Efficiency and Optimal Rules](https://mlsanity.com/paper/2404.01245/) (2024)
- [Revisiting the Robustness of Watermarking to Paraphrasing Attacks](https://mlsanity.com/paper/2411.05277/) (2024)
- [Towards Better Statistical Understanding of Watermarking LLMs](https://mlsanity.com/paper/2403.13027/) (2024)
- [Watermarking Large Language Models and the Generated Content: Opportunities and Challenges](https://mlsanity.com/paper/2410.19096/) (2024)

## Abstract (arXiv)

We introduce Stateless Bernoulli Watermarking (SBW), a new statistical watermark for Large Language Models that determines green list membership through independent per-token Bernoulli trials. Unlike KGW's vocabulary permutation or SynthID's multi-layer tournament, SBW requires only a single comparison per token against a counter-based random number generator, reducing membership complexity to O(1) and enabling single-kernel execution with zero intermediate allocations. We prove that this formulation preserves the same detection guarantees as fixed-size green lists: the z-score test remains N(0,1) under the null. The stateless architecture enables capabilities unavailable to existing methods: full-vocabulary self-salt watermarking (over 6000× faster than KGW's self-salt and 2× faster than SynthID despite biasing the entire vocabulary with candidate-dependent seeding) and architectural compatibility with distributed inference. In end-to-end generation benchmarks, SBW adds less than 1% overhead at all batch sizes. We additionally identify hash function design as a previously unexplored axis for watermark quality, showing that a GPU-native Jenkins hash improves null calibration by 1.8× while producing more diverse text. Experiments across two seeding schemes and eight (γ, δ) configurations confirm statistical equivalence with ROC-AUC differences below 0.01.