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

MC$^2$Mark: Distortion-Free Multi-Bit Watermarking for Long Messages

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 MC²Mark, a distortion-free multi-bit text watermark that colors vocabulary partitions by message bits, stacks reweighting layers, and decodes via evidence-accumulation hit rates, improving long-message (up to 512-bit) detection accuracy over MPAC and BiMark.

Problem

Multi-bit watermarks for LLM text struggle to keep distortion-free generation while reliably embedding and recovering long messages, since detectability degrades quickly as message length grows.

Approach

Extends multi-channel watermarking to multi-bit messages by assigning each vocabulary subset a green/red color from message bits, computing distortion-free scaling factors over permutations of the message (with a closed-form heuristic), applying this sequentially over m layers with XOR-masked message segments, and decoding bits by comparing mask-normalized hit rates across time and layers.

Key results

• At 256-bit messages with 512 tokens, MC²Mark reaches 91.34%-97.76% detection accuracy across datasets, while MPAC and BiMark stay around 53-70%.
• At 512-bit messages, MC²Mark achieves 87.21%-92.69% accuracy versus at most about 64% for MPAC and 41% for BiMark.
• Robustness: at 50% random token replacement with 16-bit messages MC²Mark keeps 90.44% accuracy; on Dipper paraphrasing at 256 bits it scores 54.90% vs 53.92% for the best baseline.

Surprising findings

• BiMark accuracy drops below chance-like levels (about 38% at 512 bits) with longer messages, and in the 128-bit Dipper setting BiMark falls below MPAC.

Limitations

• Dipper paraphrasing accuracy at long messages remains low (about 55% at 256 bits and 54% at 512 bits), near chance.
• Detection accuracy at 512 bits and 50% token replacement falls to roughly 57-85%, showing robustness drops with length.
• Experiments use only 512-token texts and 3B-scale instruct models; the linear-programming optimum is replaced by a heuristic without a proof of optimality.

Experimental setup

Datasets: book_report (MMW) mmw_story (MMW) fake_news (MMW) dolly_cw longform_qa (WaterBench) finance_qa (WaterBench) c4_subset (C4)

Benchmarks: book_report mmw_story fake_news dolly_cw longform_qa finance_qa c4_subset WMT/MBart translation (BLEU, BERTScore) BART summarization (ROUGE-1, BERTScore, perplexity)

Metrics: detection accuracy BERTScore BLEU ROUGE-1 perplexity

Baselines: MPAC BiMark

Builds on: MCmark BiMark MPAC Kirchenbauer et al. green-red watermark

Closest papers by meaning

• ArcMark: Distortion-Free Multi-Byte LLM Watermark via Optimal Transport (NeurIPS 2026 · similarity 0.91)
• BiMark: Unbiased Multilayer Watermarking for Large Language Models (ICML 2025 · similarity 0.90)
• Majority Bit-Aware Watermarking for Large Language Models (NeurIPS 2026 · similarity 0.90)
• Robust Multi-bit Text Watermark with LLM-based Paraphrasers (ICML 2025 · similarity 0.89)
• StealthInk: A Multi-bit and Stealthy Watermark for Large Language Models (ICML 2025 · similarity 0.87)
• Revealing Weaknesses in Text Watermarking Through Self-Information Rewrite Attacks (ICML 2025 · similarity 0.87)