Every Bit, Everywhere, All at Once: A Binomial Multibit LLM Watermark
Authors: Thibaud Gloaguen, Robin Staab, Mark Vero et al.
Summary
The authors introduce a new multibit watermarking scheme for LLMs that encodes every bit of the payload at every token position using binomial encoding, paired with a stateful encoder that dynamically shifts encoding pressure toward underencoded bits during generation. Evaluated against 8 baselines on payloads up to 64 bits, the scheme achieves superior message accuracy and robustness, with the gap widening in large-payload and low-distortion settings. The paper also critiques prior evaluation metrics and proposes per-bit confidence scoring as a practically relevant alternative.
Main takeaways:
- Encodes every bit of the payload (e.g., user ID, timestamp) at every token, rather than spreading bits across the sequence
- Uses a stateful encoder that tracks which bits are underrepresented and redirects encoding effort on the fly
- Outperforms 8 baselines in message accuracy and robustness, especially for large payloads (up to 64 bits) and low-distortion regimes
- Challenges existing evaluation metrics as lacking practical insight; introduces per-bit confidence scoring
- Already deployed commercially, so practical multibit watermarks are a real-world concern
Relevance
Tangentially related to my marker-implantation work: both involve injecting a signal (watermark bits vs. persona markers) into model output and testing robustness/localization. The stateful-encoder idea of dynamically shifting "pressure" toward underencoded bits mirrors my question of whether marker uptake can be amplified by training manipulations.
Threat model
Potential threat/caveat for clean result "Fine-tuning one persona on a two-marker chunk and another on the start marker plants the end marker at every donor answer's end, not chained to the start (LOW confidence)": this item discusses robustness, evaluation.
Abstract
arXiv:2605.11653v1 Announce Type: new 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.