Search papers, labs, and topics across Lattice.
This paper introduces Stateless Bernoulli Watermarking (SBW), a novel statistical watermarking technique for Large Language Models that utilizes independent per-token Bernoulli trials to determine green list membership, achieving a membership complexity of \(O(1)\). SBW significantly enhances efficiency by enabling single-kernel execution without intermediate allocations, while maintaining detection guarantees comparable to existing methods. Experimental results demonstrate that SBW incurs less than 1% overhead in end-to-end generation benchmarks, marking a substantial improvement in watermarking speed and effectiveness.
SBW achieves over 6000x faster watermarking than previous methods while maintaining robust detection guarantees and minimal overhead.
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 $\mathcal{N}(0,1)$ under the null. The stateless architecture enables capabilities unavailable to existing methods: full-vocabulary self-salt watermarking (over 6000$\times$ faster than KGW's self-salt and 2$\times$ 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$\times$ while producing more diverse text. Experiments across two seeding schemes and eight $(\gamma, \delta)$ configurations confirm statistical equivalence with ROC-AUC differences below 0.01.
