PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Simone Ceppi, Ignacio Sanchez

arXiv:2609.03844v1cs.CRcs.CLcs.LG

TL;DR

LLM watermarking needs production deployment without a substantial inference “watermark tax.” SBW uses independent Bernoulli trials and counter-based random generation to make watermarking stateless, while preserving fixed-size green-list detection guarantees and substantially reducing latency. The paper reports full-vocabulary self-salt support, strong speedups over existing methods, and statistical equivalence across evaluated settings, with broader model-family and distributed-deployment validation left for future work.

  • Problem

    Production LLM watermarking must distinguish machine-generated text while avoiding the computational and temporal overhead associated with applying watermarks during inference.

  • Method

    SBW determines green-list membership through independent per-token Bernoulli trials using a counter-based random number generator instead of vocabulary permutation or sequential tournament operations.

  • Results

    SBW achieves 2× lower latency than SynthID and over 6000× lower latency than KGW while preserving the detection z-score and matching KGW empirically in tested distributions.

  • Takeaways & Limitations

    The stateless formulation enables full-vocabulary self-salt, single-kernel O(1) watermarking, and compatibility with distributed inference.

  • Takeaways & Limitations

    Evaluation primarily uses one GPU and one model, and distributed compatibility has not been empirically validated in tensor-parallel or pipeline-parallel deployment.

Abstract

from arXiv · show

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 $(γ, δ)$ configurations confirm statistical equivalence with ROC-AUC differences below 0.01.

1 Introduction and State of the Art

SBW addresses the need for production-ready LLM watermarking without substantial inference overhead by replacing sequential or global watermarking operations with a stateless statistical design.

  • Motivation: Production deployment matters because regulations increasingly require providers to mark AI-generated output while watermarking can impose computational and temporal overhead.The paper frames this overhead as the “watermark tax.”
  • Related work: The paper situates SBW among adversarial, distilled, post-hoc, and sampling-process statistical watermarking approaches.The supplied related-work passage lists these method families but is truncated before completing the statistical-watermarking discussion.
  • Contributions: SBW replaces KGW’s vocabulary permutation and SynthID’s tournament passes with independent per-token Bernoulli trials.The paper presents this as a local, stateless watermarking decision.
  • Contributions: 2× lower latency than SynthID and over 6000× lower than KGW are reported for SBW benchmarks.The contribution statement also identifies full-vocabulary self-salt support at production scale.
  • Implementation: A production-ready implementation includes a vLLM logits processor, while the implementation and evaluation code are released publicly.The contribution and code passages identify the vLLM integration and associated repositories.

2 Stateless Bernoulli Watermarking

SBW turns green-list construction into independent local tests driven by a counter-based random number generator, eliminating global vocabulary operations and intermediate allocations.

  • Bernoulli Green List Construction: SBW replaces vocabulary-wide partitioning with independent Bernoulli candidate tests derived from a context seed and token-specific threshold.The seed is derived from preceding context through a pseudorandom function.
  • Bernoulli Green List Construction: A counter-based random number generator computes each token’s random value in O(1), making green-list membership independently testable and parallelizable.The implementation uses Philox 4x32-10 for GPU-native counter-based generation.
  • Computational benefits: Single fused-kernel generation reduces the stated per-token complexity from O(V log V) for KGW or O(k · m) for SynthID to O(V).The method is described as avoiding intermediate tensor allocation during watermarking.
  • Self-salt schemes: Full-vocabulary self-salt becomes tractable, whereas KGW requires a separate randperm per candidate and SynthID does not support self-salt.The comparison concerns self-salt schemes rather than ordinary context-only watermarking.
  • Detection: Detection membership tests fall to O(1) per token because the full green list need not be computed.The passage contrasts this with O(V log V) for KGW and O(m) for SynthID.
  • Statistical trade-off: The green-list size becomes random with expected size γ|V| rather than exactly γ|V|, but the paper states this does not reduce detection power.Theoretical and empirical equivalence are referenced as support for this trade-off.
  • Hash design: Replacing a permutation-table lookup with the Bob Jenkins integer hash uses pure ALU instructions and avoids scattered memory accesses that can thrash GPU caches.The paper separately analyzes the larger hash output range as a watermark-quality factor.

3 Theoretical Analysis of Equivalence

Theoretical analysis shows that independent Bernoulli green-list membership preserves the fixed-size watermark’s null moments and z-score detection behavior while enabling O(1) membership testing.

  • Equivalence result: Replacing KGW’s fixed-size green list with stochastic Bernoulli membership preserves the detection z-score exactly.The resulting formulation also supports an O(1) per-token membership test.
  • Moment equivalence: Under H0, the per-token green indicator has mean γ and variance γ(1−γ), identical to the fixed-size case.The stochastic green-list proportion has expected value γ.
  • Proof strategy: The proof derives the matching variance by combining conditional variance with the law of total variance.The proof sketch explains why the variance terms associated with random green-list proportions cancel.
  • Null distribution: Mutual independence makes the green-token count binomial with parameters (T, γ), so the standard KGW z-score applies unchanged.This connects the Bernoulli construction directly to the null test statistic.
  • Empirical validation: The supplied experiments compare KGW and SBW on z-score distributions, detection accuracy, and text quality.The cited table caption identifies separate statistical-equivalence and performance-benchmark groups, but does not provide cell values.

4 Numerical Experiments

Experiments show that SBW matches KGW in detection-related statistics and ROC-AUC while exposing hash-dependent quality trade-offs under self-salt.

  • Without Self-Salt: KS statistics for non-watermarked text are comparable between schemes, while two-sample tests show negligible effect sizes and maximum CDF differences below 5 percentage points.Both schemes deviate from ideal N(0, 1) on real LLM generations because token distributions correlate with hash-based assignments.
  • Without Self-Salt: Seven of eight watermarked configurations fail to reject identical z-score distributions, and the distributions overlap almost completely with clear separation from zero.The single rejection is also flagged by the t-test and is described as consistent with chance across eight tests.
  • With Self-Salt: With self-salt, SBW-ss is 1.74× and 1.60× closer to N(0, 1) at γ = 0.25 and γ = 0.50, respectively, although its watermarked z-scores are slightly higher.The reported differences are attributed to the Jenkins hash rather than the Bernoulli construction.
  • Detection Accuracy: AUC differences remain below 1%, with both schemes reaching AUC ≥0.999 at higher δ values and no systematic implementation bias.The ROC curves are visually indistinguishable, supporting equivalent detection accuracy.
  • Text Quality: Non-self-salt perplexity profiles are nearly identical, whereas SBW-ss has higher degradation at δ ≥5 but is statistically indistinguishable at practical settings δ ≤2.At aggressive settings, the higher perplexity is accompanied by higher text diversity.

5 Capabilities Enabled by Stateless Formulation

SBW’s stateless threshold formulation enables fused, allocation-free watermarking, practical full-vocabulary self-salt, and compatibility with distributed inference while retaining the underlying statistical framework’s guarantees and limitations.

  • 5 Capabilities Enabled by Stateless Formulation: The stateless formulation is implemented in a production-ready vLLM codebase and supports hardware-level optimizations for latency-sensitive inference.The cited implementation context connects the formulation to deployment-oriented execution rather than only asymptotic analysis.
  • 5.1 Fused Kernel Architecture: KGW cannot be fused because permutation, index materialization, mask construction, and bias application require separate GPU operations.SynthID can be fused, but its fused computation still performs O(k · m) work per token.
  • 5.1 Fused Kernel Architecture: A single fused CUDA kernel performs in-place logit mutation with one counter-based RNG evaluation per token, zero intermediate allocation, and no CPU synchronization.These properties make the watermark fully GPU-resident and expressible as one pointwise tensor operation.
  • 5.2 Full-Vocabulary Self-Salt Watermarking: Self-salt improves robustness to editing attacks, but SynthID avoids candidate-dependent seeding and KGW restricts it to top-k = 40 candidates.KGW therefore leaves the remaining vocabulary unbiased, weakening the signal in high-entropy contexts.
  • 5.2 Full-Vocabulary Self-Salt Watermarking: O(1) per-candidate cost makes true full-vocabulary self-salt feasible at O(B × V), versus KGW’s O(B × 40 × V log V) cost for 40 candidates.The approach biases the entire vocabulary while retaining candidate-dependent seeding.
  • 5.3 Inherited Security and Robustness: SBW inherits the statistical framework’s security and robustness strengths as well as its fundamental limitations.The underlying analyses rely on each token receiving green-list membership probability γ conditioned on the seeding context.

6 Performance Evaluation

SBW has low end-to-end generation overhead and substantially lower isolated watermarking latency than the compared methods, including while processing the full vocabulary with self-salt seeding.

  • Evaluation Setup: The benchmark compares logits processors in the same generation loop, using Qwen2-7B, 128 generated tokens, batch sizes 16–256, 50 iterations, and 10 warmup runs.Transformers was used because the official SynthID implementation lacked a vLLM-compatible processor.
  • End-to-End Overhead: At batch 64, SBW adds 21 ms versus SynthID’s 136 ms, a 6.5× reduction; at batch 256, overheads converge at 76 ms and 80 ms.The relative overhead remains approximately constant for SBW while SynthID’s decreases with batch size.
  • Scaling Behavior: SBW’s full-vocabulary computation saturates GPU compute around batch sizes 32–64, after which kernel and generation times grow proportionally.This explains the approximately constant percentage overhead across larger batches.
  • End-to-End Overhead: SBW remains below 1% overhead at all batch sizes, whereas SynthID ranges from 0.6% to 4.4% and KGW reaches 57% at batch size 1.Figure 4 reports end-to-end overhead on Qwen2-7B with 128 output tokens; KGW is omitted from the plot because it is out of scale.
  • Production Deployment: In production vLLM deployments, SBW achieves approximately 1% overhead at production concurrency and can partially overlap with memory-bound model operations.KGW and SynthID cannot benefit from the same pipelining according to the cited passage.
  • Isolated Watermarking Latency: 2–3× lower latency than SynthID and over 6000× lower than KGW were measured for the isolated watermarking processor despite SBW’s full-vocabulary candidate-dependent seeding.SBW also uses zero additional memory through in-place logit mutation.

7 Conclusion

SBW matches KGW’s detection guarantees through independent Bernoulli trials rather than sequential vocabulary operations, enabling efficient execution and full-vocabulary self-salt while also highlighting hash design as a quality factor.

  • Conclusion: SBW achieves KGW-equivalent detection guarantees through independent per-token Bernoulli trials instead of sequential vocabulary operations.This mechanism underlies the paper’s efficiency and capability claims.
  • Conclusion: Single-kernel O(1) watermarking, zero allocation, full-vocabulary self-salt, and distributed-inference compatibility follow from the stateless formulation.The conclusion presents these as capabilities enabled by the alternative mechanism.
  • Conclusion: SBW achieves 2× lower latency than SynthID and over 6000× lower latency than KGW.These comparisons are stated as overall conclusion-level performance results.
  • Conclusion: Hash function design is identified as a meaningful factor in watermark quality.The conclusion presents this as a second contribution beyond the stateless formulation.

8 Ethical Considerations

The paper advocates transparent watermark disclosure and cautions that reliable false-positive control depends on conservative thresholds and sufficiently long text.

  • Transparency: Users should be informed when a watermark is present, with deployment paired with clear user-facing documentation.The method is described as agnostic to disclosure policy.
  • False Accusations: False-positive rates become negligible only at sufficiently conservative thresholds and with texts of adequate length.The paper cautions that very short texts have limited statistical power.

9 Limitations

The paper reports strong performance and broad implementation support, but evaluation remains limited in model, hardware, security, and distributed-inference coverage.

  • Evaluation scope: Broader evaluation across model families remains future work because the main experiments use one GPU and model.The authors validate one additional model and setup, but not a broad range of model families.
  • Security scope: Adaptive watermark-removal and spoofing attacks were not evaluated, leaving dedicated security analysis for future work.
  • Implementation scope: Hand-tuned CUDA kernels could further reduce SBW latency, especially at small batch sizes where kernel-launch overhead dominates.
  • Deployment scope: Distributed and multi-device compatibility is architectural only because tensor-parallel and pipeline-parallel deployments were not empirically validated.

F Generalization Experiments

Additional experiments varying model, vocabulary, prompts, sampling, and hardware find no detectable difference between KGW and SBW z-score distributions.

  • Experimental design: The generalization experiment simultaneously varies five factors to test whether SBW’s equivalence extends beyond the main setup.
  • Generalization results: All tests fail to reject equivalence between KGW and SBW z-score distributions across varied models, vocabularies, prompts, sampling strategies, and hardware.The experiment uses 200 samples per scheme at δ = 2 and γ = 0.50.

G Robustness to Attacks

Across 19 attack configurations, SBW generally matches KGW’s robustness and retains more watermark signal whenever their distributions differ.

  • Overall robustness: In 11 of 19 attack configurations, SBW and KGW have statistically equivalent z-score distributions.The evaluation covers character-level, structural, word-level, and semantic attacks.
  • Overall robustness: In all 8 non-equivalent cases, SBW retains more watermark signal than KGW, never less.
  • Interpretation: SBW’s stronger retention is consistent with Jenkins hashing producing less autocorrelated green-list assignments under sequence-disrupting attacks.
  • Statistical basis: Under the null, the Bernoulli construction has marginal token indicators distributed as Bernoulli(γ), matching fixed-size KGW green lists.
  • Statistical basis: The z-score calibration argument additionally requires independent token indicators, supported by independent seeds and the null assumption that token choices ignore green lists.
Loading 2609.03844v1…