TL;DR
Researchers have developed a new "binomial" watermarking scheme for Large Language Models (LLMs) that encodes complex, multi-bit payloads (like user IDs or timestamps) by spreading every bit of information across every single token generated. By using a stateful encoder that dynamically prioritizes "under-encoded" bits during text generation, this method achieves significantly higher accuracy and robustness for large payloads (up to 64 bits) compared to existing techniques.
What Problem Does This Paper Address?
As LLMs move from research labs to commercial deployment, we need more than just a "yes/no" answer to whether a text was AI-generated. We need multibit watermarks—digital signatures that can carry metadata like a specific user ID, a license key, or a creation timestamp.
The current state-of-the-art usually relies on position allocation. Imagine trying to hide a 32-bit message in a paragraph; existing methods might pick token #5 to represent bit #1, token #12 for bit #2, and so on. This is inefficient: if a specific token is "forced" to represent a bit that doesn't fit the natural flow of language, text quality suffers. Furthermore, if an attacker deletes the specific tokens where bits were hidden, the message is lost.
The authors identify a major gap: existing methods either don't scale to long messages or become incredibly fragile when the text is edited.
Methods
The authors propose a fundamentally different approach called Binomial Multibit Watermarking. Instead of assigning one bit to one token, they encode the entire message into every token.
- Binomial Encoding: For an $m$-bit message, the system generates $m$ independent random "score vectors" for the entire vocabulary. If the $i$-th bit of the message is a 1, they use the score; if it's a 0, they use the inverse. They then sum these up to create a "binomial score" for every possible next token. Tokens that align with more bits in the message get higher scores and are more likely to be sampled.
- Stateful Encoding: This is the "secret sauce." During generation, the encoder keeps track of which bits are already "winning" (likely to be decoded correctly) and which are "losing." It then dynamically shifts the encoding pressure to favor the bits that are currently under-represented.
- Decoding: To read the watermark, the decoder performs a majority vote for each bit position across all tokens and uses a two-sided binomial test to determine statistical confidence.
Datasets
The researchers evaluated their method using:
- ELI5 (Explain Like I'm Five): Used as the primary prompt dataset for generating long-form text.
- C4 (Realnewslike subset): Used to estimate token frequencies and calibrate "null hypothesis" (human-generated) text.
- Quality Benchmarks: To ensure the watermark didn't make the LLM "dumber," they tested on GSM8k (math), HumanEval (coding), and MBPP (python programming).
- Models: Primary testing was done on Llama 3.1-8B, with additional validation on Ministral-3-14B.
Key Insights and Ideas
- "Every Bit, Everywhere": By spreading the message across the entire text, the watermark becomes much harder to "excise." You can't just delete the "ID tokens" because every token carries a piece of the ID.
- The Confidence Metric: The authors argue that "bit accuracy" is a misleading metric because it doesn't account for false positives. They introduce BA@1%FPR (Bit Accuracy at a 1% False Positive Rate), which measures how accurately you can decode a bit while ensuring you almost never "hallucinate" a watermark in human-written text.
- Redirection of Pressure: The stateful encoder acts like a coach during a game, noticing which players (bits) are struggling and giving them more playtime (encoding weight) to ensure the whole team succeeds.
Key Results
- Superior Scaling: On 64-bit payloads, the binomial scheme significantly outperformed 8 baselines. While baselines struggled to maintain message accuracy as the payload grew, the binomial approach remained robust.
- Efficiency in Length: At a length of 500 tokens, the proposed scheme exceeded 90% bit accuracy, while the best baseline hovered around 80%.
- Robustness: In tests involving word deletion and synonym substitution, the binomial watermark (specifically the "Ours+" stateful version) consistently maintained higher accuracy than prior works like MPAC or MirrorMark.
- Low Distortion: The method excels in "low-distortion" regimes, meaning it can hide a message effectively while barely touching the original perplexity (naturalness) of the LLM's output.
Limitations and Future Work
Despite the improvements, the authors admit that robustness is still an uphill battle. If an attacker heavily paraphrases the text (e.g., using another LLM to rewrite it), the bit accuracy drops toward random chance (0.5).
Future work will likely focus on making these binomial scores more resistant to semantic changes rather than just token-level edits. Additionally, while the empirical results are strong, the authors note a lack of theoretical proof that non-positional encoding is always strictly better than positional allocation—a challenge for the math-inclined in the field.
Summary updated