MC$^2$Mark: Distortion-Free Multi-Bit Watermarking for Long Messages
This addresses the need for reliable provenance tracing in AI-generated text, offering a practical solution for long-message watermarking with incremental improvements.
The paper tackles the problem of embedding long messages into AI-generated text via multi-bit watermarking without distorting quality, achieving near-perfect accuracy for short messages and a 30% improvement over prior methods for long messages.
Large language models now produce text indistinguishable from human writing, which increases the need for reliable provenance tracing. Multi-bit watermarking can embed identifiers into generated text, but existing methods struggle to keep both text quality and watermark strength while carrying long messages. We propose MC$^2$Mark, a distortion-free multi-bit watermarking framework designed for reliable embedding and decoding of long messages. Our key technical idea is Multi-Channel Colored Reweighting, which encodes bits through structured token reweighting while keeping the token distribution unbiased, together with Multi-Layer Sequential Reweighting to strengthen the watermark signal and an evidence-accumulation detector for message recovery. Experiments show that MC$^2$Mark improves detectability and robustness over prior multi-bit watermarking methods while preserving generation quality, achieving near-perfect accuracy for short messages and exceeding the second-best method by nearly 30% for long messages.