Watermarking is a way to mark the output of a language model so it can be identified later: a signal embedded in the text itself, invisible to a casual reader, detectable by anyone with the right key. It matters for content integrity: knowing whether a piece of text was generated by an AI.

The most widely studied class of watermarks works at generation time. At each step, the model’s vocabulary is split into two halves: a “green list” and a “red list”. Tokens from the green list are upweighted, so they get picked more frequently. A text is later detected as watermarked by measuring whether green tokens appear more often than chance. Simple, principled, and it works .

The standard way to assign tokens to lists was a random shuffle of the vocabulary, followed by a split at the midpoint. This guarantees a perfectly balanced partition: exactly half the tokens are green, half are red. Correct, and well understood. But also inherently sequential and memory-intensive.

The crucial insight in this work is both simple and effective. A perfectly balanced partition is not actually necessary. What the detection test needs is not that the split is exact, but that it is exact in expectation: each token should have an equal probability of landing on either side. If that holds, token after token the statistical behaviour converges to exactly what you would get with a perfect split.

So the question becomes: how do you assign each token to a list independently, with equal probability, cheaply, and in parallel? Coin flips. One Bernoulli trial per token, no communication between tokens, no intermediate allocations, trivially parallelisable and distributable without communication on multiple GPUs as modern LLM deployment often requires. Membership assignment reduces to a single comparison per token against a counter-based RNG: O(1), stateless, and embarrassingly parallel.

We prove analytically that the detection statistic’s null distribution is unchanged, and verify empirically that detection power and text quality are unaffected. The cost drops dramatically.

The method, Stateless Bernoulli Watermarking (SBW), is faster than anything comparable: over 6000x faster than KGW ’s self-salt scheme and 2x faster than SynthID at full-vocabulary watermarking, with less than 1% end-to-end generation overhead at all batch sizes. Along the way, we found something unexpected: the choice of hash function, a detail everyone had treated as an implementation footnote, turns out to be a meaningful axis for watermark quality. A GPU-native Jenkins hash improves null calibration by 1.8x and produces more diverse text.

This work was accepted at EMNLP 2026 (main conference), co-authored with Ignacio Sanchez.

Paper: Flip, Don’t Shuffle: Watermarking LLMs at the Speed of Inference (Ceppi and Sanchez, 2026)
Code and data: github.com/si-mon-jinn/flip-dont-shuffle
Tools: sbw · waterpipe