Every Bit, Everywhere, All at Once: A Binomial Multibit LLM Watermark

arXiv:2605.11653 · cs.CR, cs.AI · Submitted 2026-05-12 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Security Radio. Generated commentary on the latest security and cryptography papers.

Nadia: Today's paper: "Every Bit, Everywhere, All at Once".

Elias: Multibit watermarking has emerged as a leading approach for detecting AI-generated content,

Nadia: First, who's behind it and why it matters.

Title and authors: Nadia: So, we're looking at the paper titled "Every Bit, Everywhere, All at Once: A Binomial Multibit LLM Watermark," and it seems like the core idea is tackling the problem of embedding complex information into AI-generated text. Elias, can you give us a simple rundown of what that title actually means in practical terms?

Elias: Well, essentially, it suggests they've moved past just marking tokens or positions; they are trying to put every single bit of a message right into every single token generated by the AI using binomial encoding. It’s about maximum density for watermarking.

Priya: From a privacy standpoint, that level of embedding complexity sounds interesting because it implies the message isn't just a simple flag but something much richer, like user IDs or specific timestamps. What does this mean for how we measure privacy?

Nadia: It means they are aiming to encode payloads that are more substantial than just detecting AI origin; they want to embed actual data into the text itself in a very thorough way. We need to figure out how easy it is for someone else to peel that data out.

Elias: The authors are Thibaud Gloaguen, Robin Staab, Mark Vero, and Martin Vechev from ETH Zurich, and their approach hinges on using binomial encoding combined with a stateful encoder for dynamic pressure redirection. This structure is key to making the encoding process more effective during generation.

Priya: If it's this dense at every position, I wonder if that complexity might introduce subtle statistical artifacts that we need to account for when we try to measure privacy leakage or inference attacks.

Nadia: Exactly, Priya, because if the encoding is so fine-grained across all tokens, the detection signal might be harder to distinguish from natural text variations. We need to see how robust this is against simple edits.

Elias: The authors are showing results against eight different baselines on payloads up to sixty-four bits long, and they claim their scheme widens the gap with other methods in settings that matter most, like those with large payloads and low distortion regimes.

The paper's summary: Nadia: So, diving into the summary of "Every Bit, Everywhere, All at Once: A Binomial Multibit LLM Watermark," it explains their fundamental shift in methodology away from positional allocation. They are directly encoding every bit of a payload at every token position using binomial encoding to create a final score vector.

Elias: That means instead of picking specific spots for bits, they’re treating the whole sequence probabilistically and flipping individual Bernoulli variables based on the message bit value to get a binomial token score that aggregates alignment. It’s a different mathematical foundation than what we usually see in existing work.

Priya: The mechanism described involving sampling "m independent Bernoulli score vectors" and then calculating G˜i using the message bit is quite intricate; can you elaborate on what that actually looks like when you try to measure the resulting data integrity?

Nadia: It’s a process where they take a given m-bit message, and at each generation step, they sample those independent score vectors, then flip them based on whether the message bit is one or zero to get that binomial score. This then feeds into a distribution that biases token sampling toward tokens with higher scores.

Elias: The decoding part also relies on recomputing those same pseudorandom Bernoulli scores for every token position and then using a majority vote across all m bits to reconstruct the original message bit string at each position. It’s a self-contained system for both encoding and decoding.

Priya: I'm interested in the stateful encoder they propose, which seems to adjust this pressure during generation by weighting bits based on expected bit accuracy derived from Lemma three point one, which gives a closed-form expression for that expected accuracy as Phi(d i / √t T − t).

Nadia: That stateful aspect is where they claim they can further enhance the bit accuracy without messing up the decoding process; it dynamically shifts focus to bits that are underencoded. It’s an important mechanism for improving robustness against generation noise.

Elias: They also introduce a new evaluation metric called BA@α percentFPR, which measures the probability that a message exists and can be decoded with a specific confidence level, which they argue is more practical than just measuring raw bit accuracy on already watermarked texts.

The paper's improvements: Nadia: Moving on to the specific improvements outlined in "Every Bit, Everywhere, All at Once: A Binomial Multibit LLM Watermark," the authors are proposing two major enhancements beyond their core concept. First, they introduce a stateful encoder designed to dynamically redirect encoding pressure toward underencoded bits based on expected bit accuracy.

Elias: That stateful encoder is quite clever because it modifies the scores using the standard normal CDF, Phi, to quantify that expected accuracy of each bit given the partially generated sequence through an expression like G˜′ t(u):= Xm i=one one/T X T ∈T Φ(one/√T)(d i t−one + (2G˜i t(u) − one)).

Priya: I’m curious about the practical impact of using that specific mathematical formulation from Lemma three point one; how does knowing that closed-form expression for expected accuracy help us understand what the actual data is showing in terms of bit fidelity during inference?

Nadia: It helps them weight the importance of each bit at time t, essentially telling the AI which bits need more attention because they’re currently underencoded, which should boost the overall message accuracy. They claim this works without affecting how decoding functions.

Elias: And on the evaluation side, they suggest moving away from older metrics by proposing per-bit confidence scoring, which is tied into their new metric BA@α percentFPR. This shifts the focus to a more relevant question about whether a bit string is correctly decoded with a specified level of certainty that it actually exists.

Priya: That move towards per-bit confidence scoring seems like it addresses the limitations we've seen before, where metrics only worked if you already knew the text was watermarked; this new metric attempts to answer if an arbitrary text has a reliable bitstring hidden in it at all.

Conclusion: Nadia: So, wrapping up our discussion on "Every Bit, Everywhere, All at Once: A Binomial Multibit LLM Watermark," the main points are that they introduced a method that encodes every bit of a payload directly into every token position via binomial encoding and added a stateful encoder to dynamically prioritize underencoded bits.

Elias: They also proposed this new per-bit confidence scoring metric, BA@α percentFPR, to give us a way to evaluate the reliability of these embeds when we don't know if the original text is watermarked or not.

Priya: It’s interesting how they tackle the evaluation challenge by focusing on practical metrics like BA@α percentFPR rather than just measuring existing accuracy assumptions.

Nadia: It suggests that for future work, we should focus on how this system handles really large payloads and maintaining high quality scores while embedding this kind of dense information. We should also keep asking about the exploitation side—can someone cheaply extract these bits?

Elias: I agree, because the stateful encoder is a sophisticated mechanism; understanding its parameters and what breaks it is crucial for anyone looking to build systems that can use this technology reliably.

Priya: And from a measurement view, we need to ensure that the statistical soundness of their detection statistics remains robust across various deployment scenarios before we rely on these findings for large-scale applications.

ETH Zurich

cs.CR, cs.AI

Submitted: 2026-05-12

Updated: 2026-09-28

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 67/100

The gist: Multibit watermarking has emerged as a leading approach for detecting AI-generated content, and this work introduces a fundamentally new approach to encoding complex payloads by directly encoding

Key concepts

Binomial Encoding
This technique replaces assigning individual bits to specific locations with a more flexible approach. Instead of fixing where each bit goes, the scheme uses independent Bernoulli scores at each step and flips them based on the message bit value. This aggregates alignment across all positions rather than relying on pre-determined slots.
Expected Bit Accuracy
This concept measures how reliable a specific message bit is to be decoded given the partially generated sequence so far. The stateful encoder uses this metric to dynamically adjust encoding pressure, prioritizing bits that are currently underrepresented or less accurate during the generation process.
Per-bit Confidence Scoring (BA@α%FPR)
This proposed evaluation metric assesses the practical utility of a watermark by determining the probability that a specific bit or string is correctly decoded with a certain confidence level. It shifts focus from simple accuracy to answering whether an arbitrary text can be reliably detected and decoded, regardless of prior knowledge.

Terminology

Summary

Multibit watermarking has emerged as a leading approach for detecting AI-generated content, and this work introduces a fundamentally new approach to encoding complex payloads by directly encoding every bit at every token position using binomial encoding. This scheme is significant because it overcomes the limitations of existing methods that rely on position allocation, allowing for the effective embedding of large bitstrings without requiring individual bits to be assigned to specific generation steps.

How it works

The core innovation is replacing 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, the scheme samples m independent Bernoulli score vectors and flips each according to the corresponding bit value to yield a binomial score that aggregates alignment. Specifically, for a given position t and message bit Mi, the complementary score is calculated as:

G˜i = G i if Mi = 1, 1 − G i otherwise.

This process results in a final score vector G˜t:= Pm i=1 G˜i t ∈ Σ. The watermarked next-token probability distribution is then constructed using this score vector:

q(G˜t, pt) ∝ pt exp(δG˜t).

This distribution biases sampling towards tokens with larger scores, which increases the expected bit accuracy. For decoding, the process involves recomputing the same pseudorandom Bernoulli scores G1 t (ωt) through Gm t (ωt) for each token position. The decoded message at position t is determined by:

Mˆ t = [G1 t(ωt),..., Gm t(ωt)] ∈ 0, 1 m.

The final message Mˆ is obtained by aggregating the per-token evidence using a majority vote, defined as:

Mˆ = round (1/ω X ω t=1 Mˆ t).

Improving the Bit Accuracy with a Stateful Encoder

To further enhance bit accuracy, the paper introduces an optional stateful encoder that dynamically redirects encoding pressure toward underencoded bits. Instead of favoring all bits independently via G˜t, the scheme uses expected bit accuracy to weight the importance of each bit at time t. The watermarking scores are modified to:

G˜′ t(u):= Xm i=1 1/T X T ∈T Φ(1/√T)(d i t−1 + (2G˜i t(u) − 1)).

This modification uses the standard normal CDF (Φ) to quantify the expected accuracy of each bit given the partially generated sequence. This approach is supported by Lemma 3.1, which provides a closed-form expression for this expected accuracy:

P[d i T ≥ 0 d i t] ≈ Φ(d i / √t T − t).

Challenging Prior Evaluation Metrics

The paper critiques prior works that typically report bit accuracy and message accuracy assuming the input text is already known to be watermarked. The authors argue that these metrics fail to 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? Consequently, they propose per-bit confidence scoring as a practically relevant metric. This new metric answers the question: given any text, what is the probability that a given bit (respectively, the full bitstring) is correctly decoded with (1 − α) confidence that the message exists? This leads to the introduction of BA@α%FPR.

The End-to-End Watermark Algorithm

The final algorithm integrates multibit encoding, decoding, and stateful improvement into an end-to-end scheme. At each token position t, the process involves:

  1. Using the LLM context (ω<t) to seed a PRNG and sample m independent Bernoulli score vectors G1 t,..., Gm t ∈ 0, 1 Σ.

  2. Applying binomial encoding via Equation (2) to derive complementary scores G˜i t, allowing for construction of the final score vector G˜t.

  3. Computing the watermarked next-token probability distribution using a scheme like Soft PPL: q(G˜′ t, pt)u = 1/Σ u = arg max v∈Σ G˜'t(v) + λ log(pt)v.

Key Contributions

The main contributions of this work are:

We introduce the first multibit LLM watermark that encodes the full message bitstring at every token position via binomial encoding, avoiding existing shortcomings.

**We propose a stateful encoder that dynamically prioritizes underperforming bits during generation, significantly improving bit accuracy without affecting decoding.

Improvements for AI systems

Based on the scientific paper, here are the specific improvements that can be made to AI systems and what those improved systems will be able to do:

  1. The development of a novel, non-position-allocation based multibit watermarking scheme using binomial encoding directly into every token position.

  2. Implementation of a stateful encoder that dynamically prioritizes underencoded bits during generation by weighting the importance of each bit based on its expected worst-case accuracy (using the closed-form expression from Lemma 3.1).

  3. A new, practically relevant evaluation metric: Bit Accuracy at α% FPR (BA@α%FPR), which measures the probability that a message exists and can be correctly decoded with a specified confidence level, moving beyond prior metrics that only evaluate watermarked texts.

  4. Integration of distortion-free techniques like SynthID-Text and adapted Soft PPL schemes to embed complex payloads into LLM outputs without significantly degrading the generation quality (perplexity).

  5. A robust framework for evaluating and calibrating zero-bit watermarks, including methods to verify the statistical soundness of detection statistics (e.g., adjusting Monte Carlo approaches for better calibration).

The improved AI systems resulting from these improvements can do the following:

  1. They will be able to embed complex, high-entropy payloads (like user IDs or timestamps) directly into their generated text at every token level without relying on pre-determined positions in the output sequence.

  2. They will exhibit superior message accuracy and robustness compared to existing multibit watermarking methods, especially when encoding large bitstrings (32 and 64 bits) and in low-distortion regimes (high quality settings).

  3. They will be capable of providing a more reliable proof or audit trail for AI-generated content by allowing platform operators to statistically determine the presence and correct decoding probability of embedded metadata, even when the original text has been slightly modified (e.g., paraphrased or edited).

  4. They will achieve better trade-offs between detection reliability and generation quality, enabling them to embed richer provenance information while maintaining high perplexity scores (quality) compared to current state-of-the-art methods like ArcMark or Cycle-Shift.

  5. They will be able to provide confidence scores for decoded bits, allowing downstream systems to interpret the reliability of the extracted information, significantly reducing overconfident misinterpretations of weak watermark signals.

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.

Sources

Related papers