🤖 AI

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

This paper introduces a novel binomial multibit LLM watermarking scheme that encodes every bit of a payload at every token position using a stateful encoder to dynamically prioritize underencoded bits, achieving superior accuracy and robustness over existing baselines while proposing a more practical per-bit confidence scoring metric for evaluation.

Original authors: Thibaud Gloaguen, Robin Staab, Mark Vero, Martin Vechev

Published 2026-05-13

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Thibaud Gloaguen, Robin Staab, Mark Vero, Martin Vechev

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Problem: Hiding a Secret Message in a Book

Imagine you are an author (an AI) writing a book. You want to prove that you wrote a specific page, or perhaps you want to hide a secret note inside the text, like a user's ID or a timestamp.

For a long time, researchers tried to do this by hiding a single bit of information (a "yes" or "no") in every sentence. This is like stamping a tiny "X" on every page to say, "This page is real." It works for detection, but it can't carry complex messages like "User #1234 wrote this."

To hide a longer message (like a 32-bit or 64-bit code), previous methods tried a strategy called "Position Allocation."

The Old Way: Imagine you have a 32-bit secret code. The old method says: "For the first word, I'll hide the first bit of the code. For the second word, I'll hide the second bit. For the third word, the third bit."
The Flaw: This is like trying to carry a heavy suitcase by only using one finger at a time. If you miss a word, you lose that specific piece of the puzzle. Also, sometimes the "finger" gets tired, and the message gets garbled. It's inefficient and fragile.

The New Solution: The "Binomial" Approach

The authors propose a fundamentally new way to hide the message. Instead of hiding one piece of the puzzle at a time, they hide the entire puzzle in every single word.

The Analogy: The Choir and the Conductor

Imagine a choir (the AI) singing a song.

The Secret: The conductor has a secret 32-note melody (the message) they want the choir to sing.
The Old Method: The conductor points to the first singer and says, "Sing note 1." Then points to the second singer: "Sing note 2." If the second singer forgets, note 2 is lost forever.
The New Method (Binomial Encoding): The conductor tells every single singer to listen to the entire 32-note melody.
- For every word they sing, the choir members subtly adjust their pitch based on all 32 notes at once.
- It's like every singer is holding a tiny, invisible map of the whole melody.
- If you listen to just one word, you get a faint hint of the whole melody. If you listen to the whole song, you can reconstruct the melody perfectly by taking a "majority vote" of all the hints.

Why is this better?
Because the information is everywhere. Even if you delete a few words (or if the AI makes a mistake), the rest of the text still holds the full secret. You don't need to find the "right" word to find the "right" bit; every word has a piece of the whole picture.

The "Stateful" Upgrade: The Smart Coach

The authors added a second layer of smarts called a Stateful Encoder.

The Problem: Sometimes, the AI is really good at hiding the first few bits of the secret, but it's struggling with the last few.
The Solution: The "Coach" (the encoder) watches the song as it's being written. It realizes, "Hey, we've got the first 20 notes locked in, but the last 12 are shaky."
The Action: The Coach then whispers to the AI, "Stop worrying about the first 20 notes. Focus all your energy on making the last 12 notes perfect."
Result: This dynamic shifting of focus ensures that the entire message comes out clear, rather than letting the weak parts drag the whole thing down.

A New Way to Measure Success

The paper also argues that we are measuring these watermarks wrong.

Old Metric: "If we know this text is watermarked, how well can we read the secret?"
- Analogy: "If I tell you this is a secret code, can you crack it?" This ignores the fact that in the real world, most text isn't a secret code.
New Metric (Per-Bit Confidence): "If we look at random text, can we tell if a secret is there? And if so, how sure are we about each specific bit?"
- Analogy: Instead of just guessing, the system gives you a "confidence score" for every single bit. It says, "I'm 99% sure the first bit is a 1, but I'm only 50% sure about the last one." This prevents false alarms.

The Results

The authors tested their method against 8 other top methods using messages of 16, 32, and 64 bits.

Better Accuracy: Their method decoded the secret messages much more accurately than the others, especially for longer messages.
More Robust: Even when the text was slightly changed (like deleting words or swapping synonyms), their method held up better than the competition.
Quality: The text still sounded natural and didn't lose much quality (it didn't sound like a robot trying too hard).

Summary

This paper introduces a new way to watermark AI text. Instead of hiding one tiny secret piece in each word, it hides the entire secret message inside every single word. It uses a "smart coach" to focus on the weak spots during generation and introduces a new way to measure success that accounts for real-world noise. The result is a system that is stronger, more accurate, and better at hiding long, complex secrets in plain sight.

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

Problem Statement

Large Language Model (LLM) watermarking has transitioned from theoretical research to commercial deployment, primarily focusing on zero-bit watermarks that answer a binary question: "Was this text generated by a specific model?" However, emerging practical applications require multibit watermarks capable of encoding complex payloads (e.g., user IDs, timestamps, licensing metadata) directly into the generated text.

Existing multibit schemes predominantly rely on position allocation (e.g., MPAC, MirrorMark), where each generation step encodes only a single bit from the payload at a specific position. This approach suffers from two main limitations:

Sub-optimality: Encoding only one bit per token is inefficient, and allocated positions can be unevenly distributed.
Scalability: Alternative approaches that avoid position allocation (e.g., Cycle-Shift, ArcMark) are computationally limited to short payloads because decoding time increases exponentially with message length.

The central challenge addressed by this work is designing a multibit watermarking scheme that can effectively encode long bitstrings without relying on position allocation, while maintaining high message accuracy and robustness.

Methodology

The authors propose a fundamentally new approach based on binomial encoding, which encodes the entire message bitstring at every token position.

1. Binomial Encoding and Decoding

Unlike prior works that select a single bit to encode per token, this method encodes every bit of the $m$ -bit payload at every generation step.

Encoding: At each token position $t$ , the system samples $m$ independent Bernoulli(0.5) score vectors ( $G^1_t, \dots, G^m_t$ ) using a pseudorandom number generator (PRNG) seeded by the context and a private key. For each bit $M_i$ in the payload, the corresponding score vector is flipped (complemented) if $M_i = 1$ . The final score vector $\tilde{G}_t$ is the sum of these $m$ modified vectors. The token distribution is then biased toward tokens with higher $\tilde{G}_t$ scores.
Decoding: To decode, the system recomputes the Bernoulli scores for each token in the text. The decoded bit for position $i$ is determined by a majority vote across all tokens. Crucially, the method provides per-bit confidence scoring using two-sided binomial tests, allowing the system to assess the statistical significance of each decoded bit without assuming the text is watermarked.

2. Stateful Encoder

To improve bit accuracy, the authors introduce a stateful encoder that dynamically redirects encoding pressure during generation.

The encoder tracks the current decoding statistic for each bit based on the partially generated sequence.
It calculates the expected worst-case bit accuracy for each bit if the remaining tokens are generated without watermarking.
The scoring function is adjusted to prioritize bits that are currently under-encoded (i.e., those with decoding statistics close to the decision boundary), thereby maximizing the expected overall bit accuracy.

3. Evaluation Metrics

The paper challenges existing evaluation metrics (e.g., raw message accuracy) which assume the input text is already known to be watermarked. The authors argue that in real-world deployment, one must first detect if a message exists. They introduce Bit Accuracy at $\alpha\%$ False Positive Rate (BA@ $\alpha\%$ FPR) as a more practical metric. This metric measures the probability of correctly decoding a bit while ensuring that non-watermarked text is not falsely flagged as containing a message more than $\alpha\%$ of the time.

Key Contributions

First Position-Allocation-Free Multibit Watermark: The authors introduce the first scheme that encodes the full message bitstring at every token position via binomial encoding, avoiding the scalability and efficiency limits of position allocation.
Stateful Encoder: A novel mechanism that dynamically prioritizes underperforming bits during generation, significantly improving bit accuracy without altering the decoding strategy.
New Evaluation Framework: The paper critiques prior metrics for lacking practical insight into false positives and proposes per-bit confidence scoring (BA@ $\alpha\%$ FPR) as a standard for evaluating multibit watermarks in realistic scenarios.
Comprehensive Evaluation: Extensive experiments against 8 baselines across 16, 32, and 64-bit payloads demonstrate superior performance in bit accuracy, message accuracy, and robustness, particularly in low-distortion regimes and with larger payloads.

Results

The evaluation was conducted using LLAMA3.1-8B and MINISTRAL-3-14B with payloads of 16, 32, and 64 bits.

Message Accuracy: The proposed scheme (specifically the stateful version, "Ours+") outperforms all 8 baselines (including MPAC, MirrorMark, ArcMark, and StealthInk) in message accuracy, with the performance gap widening for longer payloads (32 and 64 bits) and low-distortion settings.
Confidence-Based Accuracy (BA@1%FPR): The stateless version of the proposed method achieves significantly higher BA@1%FPR than baselines, indicating superior ability to distinguish watermarked bits from random noise while controlling false positives.
Robustness: While robustness remains a challenge for all multibit watermarks (accuracy drops sharply with >10% word deletion or paraphrasing), the proposed method consistently outperforms baselines across various text modifications.
Scaling: The scheme scales more favorably with the number of tokens compared to baselines; at 500 tokens, the proposed method achieves >90% bit accuracy, whereas the best baseline reaches ~80%.

Significance and Claims

The paper claims to open a new direction for multibit watermarking research by demonstrating that binomial encoding is a more powerful paradigm than position allocation. The authors assert that their approach effectively encodes large payloads without the computational intractability of previous non-allocation methods (like Cycle-Shift).

Furthermore, the work highlights a critical gap in the field: the lack of practical evaluation metrics for multibit watermarks. By introducing per-bit confidence scoring, the authors argue that future research and deployment must account for the probability of false positives when decoding messages from arbitrary text, not just watermarked text.

The authors remain modest regarding limitations, acknowledging that robustness against text modifications (e.g., paraphrasing) is still an open problem and that while their empirical results show superiority over position allocation, theoretical proofs of strict optimality for non-position allocation methods are not provided. They also note that the stateful encoder, while improving message accuracy, may slightly reduce confidence-based metrics because it optimizes for expected accuracy rather than statistical significance per bit.