Research map / Large language models / Language, safety and interpretability

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

NeurIPS 2026 · Large language models › Language, safety and interpretability · approach: Text watermarking · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes a binomial multibit LLM watermark that encodes every bit at every token via per-bit Bernoulli score vectors, plus a stateful encoder and a per-bit confidence (BA@1%FPR) evaluation metric.

Problem

Multibit LLM watermarks typically allocate one bit position per token, which limits payload recovery for longer messages; prior evaluations also ignore false positives when decoding arbitrary text.

Approach

Encode the full m-bit message at every token by sampling m independent Bernoulli score vectors, XNOR-aligning each with its message bit, and summing them into binomial token scores; decoding is per-bit majority vote with binomial p-values. A stateful encoder reweights bits by their expected decoding accuracy given the partial sequence.

Key results

• On 32-bit payloads with Llama3.1-8B, Ours+ reaches 0.707 bit accuracy under 10% word deletion vs 0.664 for the best baseline (BiMark/MC2Mark), and is best across all robustness settings in the table.
• At 500 tokens in the low-distortion regime with 32-bit payloads, bit accuracy of Ours exceeds 90% while the best baseline reaches about 80%.
• For 8-bit payloads at perplexity budget 4, Ours reaches 98.9% BA@1%FPR vs 88.8% for MPAC and 84.7% for Cycle-Shift.

Surprising findings

• Many prior multibit watermarks produce decoded messages on arbitrary unwatermarked text, so message/bit accuracy metrics on watermarked text alone overstate practical performance.
• Some prior zero-bit detectors (MPAC, StealthInk) have miscalibrated p-values with empirical FPR above the theoretical FPR under the null.

Limitations

• Robustness to text modifications remains limited for all schemes, with bit accuracy dropping sharply beyond 10% word edits and near 0.5 under paraphrasing.
• Only proven that encoding every bit at every position never loses power versus position allocation, not a strict advantage.
• Advantage shrinks for short payloads (8 bits).

Experimental setup

Datasets: ELI5 Zhihu-KOL C4 realnewslike GSM8K HumanEval MBPP MATH500

Benchmarks: ELI5 GSM8K HumanEval MBPP MATH500 Zhihu-KOL

Metrics: message accuracy bit accuracy BA@1%FPR perplexity TPR@1%FPR word deletion/synonym/paraphrase robustness

Baselines: MPAC Cycle-Shift ArcMark BiMark MC2Mark MirrorMark RSBH StealthInk

Builds on: Red-Green watermark SynthID-text Soft PPL watermark MPAC Cycle-Shift

Closest papers by meaning

• ArcMark: Distortion-Free Multi-Byte LLM Watermark via Optimal Transport (NeurIPS 2026 · similarity 0.91)
• Majority Bit-Aware Watermarking for Large Language Models (NeurIPS 2026 · similarity 0.88)
• MC$^2$Mark: Distortion-Free Multi-Bit Watermarking for Long Messages (NeurIPS 2026 · similarity 0.87)
• Robust Multi-bit Text Watermark with LLM-based Paraphrasers (ICML 2025 · similarity 0.87)
• PRO: Enabling Precise and Robust Text Watermark for Open-Source LLMs (NeurIPS 2026 · similarity 0.85)
• No Free Lunch in LLM Watermarking: Trade-offs in Watermarking Design Choices (NeurIPS 2024 · similarity 0.85)