🤖 machine learning

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

MC $^2$ Mark is a distortion-free multi-bit watermarking framework that utilizes Multi-Channel Colored Reweighting and Multi-Layer Sequential Reweighting to embed and decode long messages in large language model outputs with significantly improved robustness and accuracy while preserving text quality.

Original authors: Xuehao Cui, Ruibo Chen, Yihan Wu, Heng Huang

Published 2026-02-17

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Xuehao Cui, Ruibo Chen, Yihan Wu, Heng Huang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a famous chef (a Large Language Model) who can cook up delicious, perfect meals (text) that taste exactly like something a human would make. The problem is, because the food is so good, no one can tell if it was cooked by a human or a robot. This makes it hard to know who is responsible for the meal if something goes wrong, or to prove it was actually made by you.

To solve this, people have tried to add a "secret ingredient" (a watermark) to the recipe. But here's the catch:

Old methods were like adding too much salt. It made the food taste weird (lowered the quality) just to prove it was yours.
Newer methods were like adding a tiny, invisible speck of dye. It didn't change the taste, but if you tried to hide a long message (like a whole ID card) inside the dish, the dye would fade away or get lost in the sauce.

Enter MC2MARK: The "Invisible, Indestructible Sticker"

The researchers behind this paper created a new system called MC2MARK. Think of it as a magical way to stamp a long, complex message onto a meal without changing a single gram of its flavor.

Here is how it works, using some everyday analogies:

1. The "Color-Coded" Menu (Multi-Channel Colored Reweighting)

Imagine the chef has a menu with thousands of ingredients (words).

The Old Way: To send a secret message, the chef would just pick "Green" ingredients more often and "Red" ingredients less often. But if the chef is forced to pick too many Greens, the dish might taste unbalanced.
The MC2MARK Way: The chef divides the menu into many small groups. For every bit of the secret message (0 or 1), they assign a specific "color" to a group of ingredients.
- If the message bit is 1, that group gets a "Green Light" (slightly boosted).
- If the message bit is 0, that group gets a "Red Light" (slightly dimmed).
- The Magic Trick: The chef is so skilled that they balance the boost and the dimming perfectly across the whole menu. If they boost one group, they subtly adjust others so that, on average, the final dish tastes exactly the same as if no secret message existed. It's like a tightrope walker who shifts their weight perfectly so they never fall, keeping the balance (the text quality) intact.

2. The "Layered Cake" Strategy (Multi-Layer Sequential Reweighting)

Sending a long message (like a 256-bit ID) is hard because the signal gets weak.

The Analogy: Imagine trying to hear a whisper in a noisy room. If you whisper once, no one hears you. But if you whisper the same message, then whisper it again, and again, layer by layer, the sound builds up.
MC2MARK does this by applying the "Green/Red" trick not just once, but multiple times (like layers of a cake) as the text is being written. Each layer reinforces the secret message. Even if someone tries to erase part of the text later, the message is still hidden in the remaining layers, making it incredibly hard to destroy.

3. The "Detective's Evidence Board" (Evidence Accumulation)

When a detective (the detector) looks at the finished text to find the secret message, they don't just look for one clue.

The Analogy: Imagine a detective trying to solve a case by looking at a single fingerprint. It's risky. But if they collect hundreds of tiny clues—a shoe print here, a hair there, a partial fingerprint over there—and put them all on an evidence board, the picture becomes crystal clear.
MC2MARK uses a "Hit Rate" system. As the detective reads the text, they check every word against the secret key. If a word matches the "Green" pattern, they get a point. If it matches "Red," they get a point for the opposite. By the end of the text, they count up all the points. Even if the text is long and the message is huge, the math proves exactly what the secret message was, with near-perfect accuracy.

Why is this a Big Deal?

No Taste Change: The text sounds natural, flows well, and doesn't feel "robotic."
Huge Capacity: You can hide a massive amount of information (like a full ID card or a complex code) inside a short story or a long article.
Unbreakable: Even if someone tries to rewrite the text, cut out sentences, or swap words around (like a "paraphrasing" attack), the secret message survives because it's woven into the very fabric of the text generation, layer by layer.

In short: MC2MARK is like a master forger who can stamp a secret, unerasable ID onto a masterpiece painting without leaving a single scratch on the canvas. It allows us to trace where AI text comes from, ensuring accountability without ruining the art.

1. Problem Statement

The rapid advancement of Large Language Models (LLMs) has made machine-generated text indistinguishable from human writing, creating an urgent need for reliable provenance tracing. While statistical watermarking methods exist to detect AI-generated text, they face significant limitations:

Zero-Bit Limitation: Most existing methods only output a binary decision (watermarked vs. not), failing to embed specific identifiers (e.g., user ID, model ID) required for detailed provenance.
Distortion vs. Capacity Trade-off: Existing multi-bit watermarking techniques struggle to embed long messages without degrading text quality (distortion) or losing detectability. As message length increases, the accuracy of current state-of-the-art methods (like BiMark) drops precipitously.
Robustness: Many methods fail under adversarial attacks (e.g., paraphrasing or token replacement) or require access to the message space during detection, limiting practical deployment.

The core challenge addressed is achieving distortion-free (unbiased) multi-bit watermarking that maintains high detection accuracy and robustness even for long messages (e.g., 256+ bits).

2. Methodology: MC2MARK

The authors propose MC2MARK, a framework designed to embed and decode long messages without altering the expected token distribution of the LLM. The framework consists of three core components:

A. Multi-Channel Colored Reweighting (MCCR)

This is the core embedding mechanism.

Concept: The vocabulary $V$ is partitioned into $n$ disjoint subsets (channels), where $n$ corresponds to the message length.
Coloring: The message bits are interpreted as "colors" assigned to these subsets. A bit 1 designates a subset as Green (amplified probability), and 0 designates it as Red (attenuated probability).
Distortion-Free Guarantee: To ensure the text quality remains unchanged (unbiased), the method employs a symmetry-based optimization. It calculates scaling factors for the token probabilities such that, when averaged over all possible key permutations, the expected probability of any token remains identical to the original model distribution.
Heuristic Solution: Since finding the exact optimal scaling is computationally expensive, the authors propose a heuristic that:
1. Attempts to uniformly amplify green subsets to a target scale.
2. Handles "overflow" probability (when amplification exceeds normalization constraints) by redistributing the remaining mass proportionally based on overflow probabilities.
Segmentation: To reduce computational complexity from $O(2^n)$ to a manageable level, the long message is segmented, and a pseudo-random masking strategy is applied to whiten the bit distribution.

B. Multi-Layer Sequential Reweighting (MLSR)

To strengthen the watermark signal without introducing bias:

The generation process applies the MCCR reweighting sequentially across multiple layers ( $m$ layers).
At each generation step, $m$ distinct watermark keys are used to iteratively reweight the token distribution.
Because each layer is distortion-free and keys are sampled independently, the composite multi-layer process remains distortion-free while significantly boosting the statistical signal strength, making the watermark more robust against noise and attacks.

C. Evidence Accumulation Detector

For message recovery, the detector does not rely on a single token but aggregates statistical evidence:

Reconstruction: The detector deterministically reconstructs the watermark keys, segment indices, and masking vectors used during generation based on the input text.
Hit Counting: For every token generated, the detector checks if it belongs to a "Green" subset. If so, it increments a "hit counter" for the corresponding message bit hypothesis.
Normalization: To correct for biases introduced by different masking configurations, the detector tracks "total opportunity" counters (how many times a bit could have been observed).
Decision Rule: The final bit value is determined by comparing the normalized hit rates ( $HitRate_1$ vs. $HitRate_0$ ) for each bit position.

3. Key Contributions

Novel Framework: Introduction of MC2MARK, the first distortion-free multi-bit watermarking framework capable of reliably embedding and detecting long messages (up to 512 bits) with high accuracy.
Technical Innovations:
- MCCR: A method to encode bits via structured token reweighting while mathematically guaranteeing an unbiased distribution.
- MLSR: A technique to amplify watermark signals through iterative, multi-layer reweighting without compromising distortion-free properties.
- Evidence Accumulation: A robust detection scheme that marginalizes over randomness to recover messages accurately.
Performance Benchmark: The work sets a new standard for long-message watermarking, demonstrating that high capacity and high quality are not mutually exclusive.

4. Experimental Results

The authors evaluated MC2MARK against baselines like MPAC and BiMark across seven diverse datasets (e.g., book reports, fake news, finance QA) using Qwen2.5-3B models.

Detectability (Accuracy):
- Short Messages: Achieved near-perfect accuracy (100% on most datasets for 16-32 bits).
- Long Messages: For 256-bit messages, MC2MARK achieved >91% accuracy, outperforming the second-best method (BiMark) by nearly 30%.
- Scalability: While BiMark's accuracy dropped below 60% for 256-bit messages, MC2MARK maintained >90% accuracy even at 512 bits.
Robustness:
- Token Replacement: MC2MARK maintained 100% accuracy with 10-30% random token replacement for short messages and remained significantly higher than baselines for long messages even at 50% replacement.
- Paraphrasing: Under Dipper paraphrasing attacks, MC2MARK consistently outperformed all baselines across all message lengths.
Distortion-Free (Quality):
- Evaluated on text summarization and machine translation tasks.
- Metrics (BERTScore, ROUGE, BLEU, Perplexity) for MC2MARK were virtually identical to the "No Watermark" baseline, proving that the method does not degrade text fluency or semantic quality.
Ablation Studies:
- Removing the masking bit significantly reduced performance for long messages.
- Increasing the number of layers ( $m$ ) improved accuracy, with optimal performance observed around $m=20$ for long messages.

5. Significance

MC2MARK addresses a critical bottleneck in AI safety and regulation: the ability to trace the origin of AI-generated content without compromising the utility of the text.

Practical Deployment: By supporting long messages, it enables the embedding of complex metadata (user IDs, timestamps, model versions) directly into the text, facilitating granular provenance tracking.
Regulatory Impact: It provides a technical foundation for regulating LLM usage, helping to identify malicious actors or unauthorized model usage while ensuring that the generated content remains high-quality and indistinguishable from human writing in terms of style and coherence.
Theoretical Advancement: It demonstrates that the trade-off between message capacity and distortion can be effectively managed through multi-channel, multi-layer reweighting strategies.