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

Abstract

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 form

Categories

@misc{ceppi2026flip,
  title = {{Flip, Don't Shuffle: Watermarking LLMs at the Speed of Inference}},
  author = {Simone Ceppi and Ignacio Sanchez},
  year = {2026},
  month = sep,
  eprint = {2609.03844},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.03844}
}