Stateless Bernoulli Watermarking Drops Green-List Membership to O(1) and Adds Under 1% Generation Overhead

arXiv 2609.03844·medium signalXBlueskyLinkedInCopy link

SBW determines green-list membership through independent per-token Bernoulli trials rather than KGW's vocabulary permutation or SynthID's multi-layer tournament, requiring a single comparison per token against a counter-based RNG, which reduces membership complexity to O(1) and enables single-kernel execution with zero intermediate allocations. The authors prove the z-score test remains N(0,1) under the null, preserving fixed-size green-list detection guarantees, and the stateless design unlocks full-vocabulary self-salt watermarking over 6000x faster than KGW's self-salt and 2x faster than SynthID while biasing the entire vocabulary, plus architectural compatibility with distributed inference. End-to-end it adds under 1% overhead at all batch sizes, and they identify hash design as a new quality axis, with a GPU-native Jenkins hash improving null calibration 1.8x.