Every Bit, Everywhere, All at Once: A Binomial Multibit LLM Watermark
Thibaud Gloaguen, Robin Staab, Mark Vero, Martin Vechev · 2026
Read Every Bit, Everywhere, All at Once: A Binomial Multibit LLM Watermark by Thibaud Gloaguen, Robin Staab, Mark Vero, Martin Vechev (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-11653.txt.
Introduction
Gloaguen, Staab, Vero and Vechev propose a binomial multi-bit LLM mark putting every bit everywhere. Commercial marking needs multi-bit payloads like user IDs in made text. Their method uses binomial coding to put every bit at every token, plus a coder shifting pressure to undercoded bits. Against 8 baselines on 64-bit payloads, the scheme beats rivals on accuracy, with gaps widening for large payloads. They challenge prior scoring methods and introduce per-bit confidence scores.
Catalog record
| CREATOR | Thibaud Gloaguen, Robin Staab, Mark Vero, Martin Vechev |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 78344 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.11653
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Every Bit, Everywhere, All at Once: A Binomial Multibit LLM Watermark Thibaud Gloaguen, Robin Staab, Mark Vero, Martin Vechev Abstract With LLM watermarking already being deployed commercially, practical applications increasingly require multibit watermarks that encode more complex payloads, such as user IDs or timestamps, into the generated text. In this work, we propose a fundamentally new approach for multibit watermarking: introducing binomial encoding to directly encode every bit of the payload at every token position. We complement our approach with a stateful encoder that during generation dynamically redirects encoding pressure toward underencoded bits. Our evaluation against 8 baselines on up to 64-bit payloads shows that our scheme achieves superior message accuracy and robustness, with the gap to baseline methods widening in more relevant settings (i.e., large payloads and low-distortion regimes). At the same time, we challenge prior works’ evaluation metrics, highlighting their lack of practical insights, and introduce per-bit confidence scoring as a practically relevant metric for evaluating multibit LLM watermarks. 1 Introduction LLM watermarking has emerged as a leading approach for detecting AI-generated content, with major companies and regulators moving toward deployment [ 1 ] . Initial watermarking research focused on zero-bit watermarks, which answer a single binary question: was this text generated using a given watermark? While technically sufficient for detection, emerging practical applications demand richer watermarking signals that, e.g., allow model providers to embed individual user IDs, encode timestamps, or include licensing metadata. These use cases require multibit watermarks that encode an m -bit payload into the model output and are able to reliably decode it from watermarked text. Multibit Watermarking To enable the inclusion of such multibit information, existing schemes overwhelmingly rely on position allocation [ 2 , 3 , 4 ] : at each generation step, the watermark selects a single bit position from the payload and encodes only that bit using a chosen zero-bit scheme. The full message is then recovered by aggregating per-token evidence across many tokens. Yet, allocated positions can be uneven [ 4 ] , and encoding only one bit per token has been found to be sub-optimal [ 5 ] , limiting the effectiveness of such schemes in practice (see Section 5 ). At the same time, alternative, more powerful, approaches that avoid position allocation, e.g., Cycle-Shift [ 6 ] and ArcMark [ 5 ] , are computationally limited to short payloads. Hence, the question remains whether we can design a more powerful multibit watermarking scheme that effectively encodes longer bitstrings without having to assign individual bits to individual generation steps? This Work: Multibit Watermarking via Binomial Encoding We answer this question affirmatively with a powerful multibit watermarking scheme that encodes large payloads without position allocation (illustrated in Figure 1 ). Our key insight is to replace fully encoding individual bits in specific locations with partly encoding every bit across every location via binomial encoding . Given an m -bit message, at each generation step, we sample m independent Bernoulli score vectors and flip each according to the corresponding bit value, yielding a binomial score that aggregates alignment across all m bits ( Figure 1 , blue shade). The watermarked distribution then favors tokens whose scores align with the full message ( Figure 1 , middle). Decoding reduces to a majority vote per bit, with statistical significance provided by two-sided binomial tests ( Figure 1 , right). We further introduce a stateful encoder that, during generation, tracks which bits are already well-encoded and redirects encoding pressure toward bits that are not yet correctly recovered. Our evaluation ( Section 5 ) shows that our approach outperforms prior works in most practical scenarios. Beyond the method itself, we also revisit how multibit watermarks should be evaluated under practical deployment conditions. Prior works [ 2 , 3 , 4 ] typically report bit accuracy and message accuracy assuming the input text is already known to be watermarked; that is, they answer “given a watermarked text, how much of the encoded message can we decode?” They do not address the broader deployment question: given an arbitrary text, can we first detect whether it is watermarked and, if so, reliably decode the embedded message? Since most texts encountered in practice are not watermarked, ignoring false positives in message recovery falls short of real-world deployment constraints. Notably, we find in Section 4 that while existing approaches can be post-hoc adapted with error-detection codes , this comes at the cost of reduced capacity. In contrast, binomial watermarks directly support per-bit confidence scoring , enabling even statistically sound recovery of sub-messages. Key Contributions. Our main contributions are: • We introduce the first multibit LLM watermark that encodes the full message bitstring at every token position via binomial encoding , avoiding existing shortcomings ( Section 3.1 ). • We propose a stateful encoder that dynamically prioritizes underperforming bits during generation, significantly improving bit accuracy without affecting decoding ( Section 3.2 ). • We challenge prior multibit evaluation metrics, highlighting their limited interpretability, and propose per-bit confidence scoring as an alternative metric ( Section 4 ). • We provide a comprehensive evaluation against 8 baselines across 3 bitstring lengths (16, 32, 64 bits), showing that our scheme achieves superior bit accuracy, message accuracy, and robustness, with the gap widening at longer payloads and in low-distortion regimes ( Section 5 ). 2 Background and Related Work Figure 1 : Overview of Our Multibit Watermark Algorithm Encoder and Decoder: Given an m -bit bitstring (here 010 ), at each step of the generation process, we use the context to seed a pseudorandom number generator (PRNG) that samples m Bernoulli variables ( G ) for each token in the vocabulary. We encode our bitstring with an XNOR operation and sum the encoded Bernoulli variables to obtain binomial token scores ( \tilde{G} ). We then modify the next-token logit distribution with \tilde{G} to obtain our watermarked distribution. For decoding the bitstring from a text, we use the same PRNG to retrieve the m Bernoulli variables for every token in the text. We then decode the bitstring by taking the majority bit at each bit position, using m binomial tests to obtain per-bit confidence. In this section, we introduce relevant related work in (multibit) LLM watermarking. LLM Watermarks The goal of (zero-bit) LLM watermarks is to insert a detectable signal into text generated by an LLM. At each step of the generation process, the previously generated context and a private key seed a pseudorandom number generator, which assigns a score to each token in the vocabulary. Then, the next-token distribution produced by the LLM is biased to favor tokens with higher scores. For detection, given a sequence of tokens (text), we aggregate the individual token scores. We call this aggregation the detection statistic . For instance, with Red-Green watermarks [ 7 ] , this statistic is the number of green tokens. If the text was generated without knowledge of the scores, the statistic is random. However, when using the watermark, the statistic is biased toward higher values. Importantly, for deploying detection at internet-scale, the statistic should be model-free, i.e., it should not require access to the LLM. Popular approaches commonly build on Kirchenbauer et al. 2023 , which biases the logits of the next-token distribution