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

Majority Bit-Aware Watermarking for Large Language Models

NeurIPS 2026 · Large language models › Language, safety and interpretability · approach: Text watermarking

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 majority bit-aware encoding for multi-bit LLM watermarking, where the green list is the union of message-bit shards matching the majority bit (so gamma >= 0.5), with MajorMark (clustering decoder) and MajorMark+ (block-wise, deterministic decoder) improving the quality-accuracy trade-off over MPAC and RSBH.

Problem

Multi-bit LLM watermarking faces a trade-off: a small green list ratio preserves decoding accuracy but degrades text quality, while a large green list weakens the frequency-based watermark signal.

Approach

Encode the message into which vocabulary shards are boosted: partition the vocabulary into b shards, one per bit, and boost the union of shards matching the majority bit. This guarantees a green list ratio of at least 0.5 and decodes by inferring which shards were boosted, with block-wise encoding for long messages to raise the expected green ratio.

Key results

• At b=64, delta=4, MajorMark+ reaches 97.81% bit accuracy vs. RSBH 90.39% and MPAC 93.59%, with lower PPL (6.21 vs 6.41 for RSBH).
• Averaged over delta in {2,4,6} at b=64 on C4, MajorMark+ attains 94.82% BA and PPL 6.29, versus MPAC 90.52% BA and PPL 9.86 and RSBH 89.74% BA and PPL 6.85.
• With 100 users on LLaMA-3.1-8B, MajorMark+ achieves 99.81% BA with PPL 6.51, while StealthInk gets PPL 4.83 but BA 83.84%.

Surprising findings

• StealthInk achieves the lowest PPL in the 100-user study but has much lower bit accuracy (49.31% on Qwen3-8B), showing the quality-accuracy trade-off persists.

Limitations

• Paraphrase attacks still substantially degrade bit accuracy for all methods.
• Extreme all-zero or all-one messages give gamma=1.0 and must be excluded.
• Clustering-based MajorMark decoding is sensitive to weak bias and long messages, motivating MajorMark+.

Experimental setup

Datasets: C4 news Essays OpenGen WritingPrompts CNN/DailyMail

Benchmarks: C4 news Essays OpenGen WritingPrompts CNN/DailyMail

Metrics: bit accuracy perplexity top-5 hit rate BERTScore ROUGE runtime

Baselines: DepthW CycleShift MPAC RSBH StealthInk BiMark

Builds on: KGW RSBH MPAC CycleShift DepthW

Closest papers by meaning

• ArcMark: Distortion-Free Multi-Byte LLM Watermark via Optimal Transport (NeurIPS 2026 · similarity 0.90)
• BiMark: Unbiased Multilayer Watermarking for Large Language Models (ICML 2025 · similarity 0.90)
• MC$^2$Mark: Distortion-Free Multi-Bit Watermarking for Long Messages (NeurIPS 2026 · similarity 0.90)
• Black-Box Detection of Language Model Watermarks (ICLR 2025 · similarity 0.89)
• PRO: Enabling Precise and Robust Text Watermark for Open-Source LLMs (NeurIPS 2026 · similarity 0.89)
• StealthInk: A Multi-bit and Stealthy Watermark for Large Language Models (ICML 2025 · similarity 0.88)