💬 NLP

QuantileMark: A Message-Symmetric Multi-bit Watermark for LLMs

QuantileMark is a white-box multi-bit watermarking method for large language models that ensures message symmetry and robust detection by embedding messages within equal-mass probability bins in the continuous cumulative distribution, thereby maintaining generation quality while achieving uniform evidence strength across all messages.

Original authors: Junlin Zhu, Baizhou Huang, Xiaojun Wan

Published 2026-04-16

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Junlin Zhu, Baizhou Huang, Xiaojun Wan

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 own a bakery that sells thousands of delicious, custom cakes every day. You want to know which baker made which cake, just in case someone tries to sell a fake one or if a cake turns out to be bad. So, you decide to bake a tiny, invisible "secret ingredient" into every cake.

The problem with previous methods was like this: Imagine you have a bag of 100 different colored sprinkles. To hide your secret, you tell the baker, "If you are making Cake #1, use only Red sprinkles. If you are making Cake #2, use only Blue sprinkles."

But here's the catch: Some cakes naturally need a lot of Red sprinkles to taste good, while others need Blue.

The Old Way (Vocabulary Partition): If you force a "Blue-only" cake to use Red sprinkles because that's the code for Cake #1, the cake tastes weird (bad quality). If you force a "Red-only" cake to use Blue sprinkles, it also tastes weird. Worse, if the baker happens to want Red sprinkles anyway, the secret is easy to spot. But if they wanted Blue, the secret is hard to find. The "secret" changes the taste of the cake depending on which secret you are hiding.

Enter QuantileMark: The "Equal-Slice" Cake.

The researchers at Peking University came up with a smarter way called QuantileMark. Instead of assigning specific colors to specific cakes, they changed the rules of the kitchen entirely.

The Analogy: The Probability Pie

Imagine the baker's decision-making process as a giant pie representing 100% of the possible flavors they could choose for the next bite of the cake.

The biggest slice of the pie is the flavor the baker really wants to use (e.g., "Chocolate").
The tiny slivers are the weird flavors they rarely pick (e.g., "Pickles").

How QuantileMark Works:

The Equal Slices: Instead of giving "Red" to one cake and "Blue" to another, the baker cuts the entire pie into 4 equal slices (since they are hiding 2 bits of information, which equals 4 possibilities).
- Slice 1: 0% to 25% of the pie.
- Slice 2: 25% to 50%.
- Slice 3: 50% to 75%.
- Slice 4: 75% to 100%.
The Secret Code: Every time the baker needs to pick a flavor, they look at their secret code (the message). Let's say the code says "Slice 3."
- The baker must pick a flavor that falls inside that 50%–75% slice of the pie.
- If the baker's favorite flavor (Chocolate) is in that slice, they pick Chocolate. Easy!
- If their favorite is in Slice 1, they have to pick the best flavor available in Slice 3. Maybe it's "Strawberry."

Why is this a game-changer?

Fairness (Message Symmetry): It doesn't matter if the secret code is "Slice 1" or "Slice 4." Every slice is exactly the same size (25%). The baker never has to pick a "weird" flavor just because of the code. The cake always tastes just as good, no matter which secret is hidden inside.
Detectability: Because the baker is forced to pick from a specific slice, a detective (the verifier) can look at the cake and say, "Ah, this flavor is in the 50-75% range. That matches the code for 'Slice 3'!" Even if the baker had to compromise slightly, the detective can still see the pattern clearly because the slices are perfectly equal.

The "White-Box" Detective

In the old days, the detective had to guess based on the outside of the cake (Black-Box). They couldn't see the recipe.
With QuantileMark, the bakery allows the detective to peek inside the kitchen (White-Box). The detective knows the recipe, knows how the pie was sliced, and can mathematically prove, "Yes, this cake was baked using the 'Slice 3' rule."

The Real-World Result

The paper tested this on AI models (the bakers) writing text (the cakes).

Quality: The text written with QuantileMark sounded just as natural and high-quality as text without any secret code. The "taste" wasn't ruined.
Recovery: The detective could read the secret message (like a User ID or a timestamp) almost perfectly, even if the text was short.
Robustness: Even if someone tried to edit the text (like changing a few words or deleting a sentence), the secret was still much harder to destroy compared to the old "Red vs. Blue sprinkle" methods.

Summary

QuantileMark is like a new way of baking secrets into AI text. Instead of forcing the AI to use specific words that might ruin the sentence (like forcing a "Red sprinkle" on a "Blue cake"), it divides the AI's choices into equal, fair chunks. This ensures the text stays delicious (high quality) while making the secret code easy to find and impossible to mess up, no matter what the AI was originally planning to say.

1. Problem Statement

As Large Language Models (LLMs) become ubiquitous, there is an urgent need for provenance tracking to attribute content to specific users, models, or timestamps. While zero-bit watermarks (detecting if text is AI-generated) are established, practical deployments increasingly require multi-bit watermarks to encode metadata (e.g., User IDs).

The paper identifies a critical flaw in existing multi-bit watermarking schemes, particularly vocabulary-partition methods (e.g., MPAC), regarding Message Symmetry:

The Issue: In low-entropy decoding scenarios (where the model is highly confident), vocabulary partitioning assigns uneven probability budgets to different message symbols.
- Example: If a model assigns 80% probability to Token A, and Token A falls into the partition for Message "00", embedding "00" is "free" (high quality, high detection confidence). However, embedding "01" might force the model to select a low-probability tail token, degrading text quality and weakening detection evidence.
Consequence: This creates a systematic bias where the quality of the generated text and the reliability of the watermark detection depend on the specific message being embedded. This violates operational fairness and theoretical guarantees of distribution preservation.

Existing distribution-preserving methods (e.g., StealthInk) attempt to fix this but often prioritize stealth (minimal distortion) over detection strength, resulting in weak evidence for robust multi-bit recovery, especially in provider-internal settings where white-box access is available.

2. Methodology: QuantileMark

The authors propose QuantileMark, a white-box multi-bit watermarking framework that operates on the continuous cumulative probability interval $[0, 1)$ rather than discrete vocabulary spaces.

Core Mechanism

Quantile Partitioning:
- Instead of partitioning the vocabulary, QuantileMark partitions the cumulative probability interval $[0, 1)$ into $M$ bins of equal mass (where $M = 2^m$ and $m$ is bits per symbol).
- Each bin $B_r = [r/M, (r+1)/M)$ represents exactly $1/M$ of the probability mass, regardless of the underlying token distribution or context entropy.
Embedding (Generation):
- For a target symbol $s_t$ , a keyed permutation $\phi_t$ maps it to a specific target bin $B_{r^*}$ .
- The sampler draws a random value $u$ uniformly from $B_{r^*}$ .
- The output token is the one whose cumulative probability interval covers $u$ .
- Result: Every symbol receives a fixed probability budget of $1/M$ . This structurally enforces message symmetry.
Detection (Verification):
- The verifier (with white-box access) reconstructs the base distribution $p_0$ and the same quantile geometry using teacher forcing.
- For an observed token $x_t$ , the detector calculates the posterior probability that it originated from a specific bin $r$ :
  $P(R_t = r | x_t, h_t) = \frac{\text{Overlap Mass}(x_t, B_r)}{p_0(x_t | h_t)}$
- Evidence is aggregated using Log Posterior Odds (LPO) across steps assigned to the same message symbol.
- The message is decoded by maximizing the cumulative LPO for each symbol position.

Theoretical Guarantees

Message-Unbiasedness: The authors prove that if the message is uniform, the expected watermarked distribution equals the base distribution ( $E[p_{wm}] = p_0$ ). This ensures that, on average, the watermark introduces no distortion regardless of the message content.
Cipher-Unbiasedness: Even if the message is fixed but the key is randomized, the distribution remains preserved.

3. Key Contributions

QuantileMark Framework: A novel white-box watermarking scheme that defines the embedding channel on the continuous CDF interval, ensuring equal-mass partitioning for all message symbols.
Theoretical Foundation: Formalization and proof of message-unbiasedness, providing a rigorous guarantee that generation quality and detection outcomes are independent of the specific message content.
Superior Empirical Performance: Demonstrated significant improvements in multi-bit recovery and detection robustness compared to state-of-the-art baselines (MPAC, StealthInk) while maintaining negligible impact on generation quality (Perplexity).

4. Experimental Results

The authors evaluated QuantileMark on C4 (open-ended continuation) and LFQA (long-form QA) using Llama-2 and Llama-3 models.

Recovery Accuracy: QuantileMark achieved 98.93% bit accuracy on C4 and 95.00% on LFQA (24-bit message, 300 tokens), outperforming MPAC (97.02% / 87.70%) and StealthInk (90.03% / 74.47%).
Detection Robustness: It achieved near-perfect AUC (0.9995 on C4, 0.9997 on LFQA) and TPR@1%FPR, significantly outperforming baselines, especially in low-entropy regimes where vocabulary partitioning fails.
Generation Quality: The Perplexity (PPL) of QuantileMark remained nearly identical to the unwatermarked baseline (e.g., 7.404 vs 7.684 on C4), confirming the theoretical unbiasedness. In contrast, MPAC showed a noticeable PPL increase due to distortionary biases.
Robustness: The method showed strong resistance to copy-paste and synonym attacks. While paraphrasing and deletion attacks remain challenging (as with all multi-bit schemes), QuantileMark maintained higher resilience than baselines.
Downstream Utility: In text summarization and machine translation tasks, QuantileMark preserved utility scores (BLEU, ROUGE) comparable to the no-watermark baseline.

5. Significance and Impact

Solving the Symmetry Problem: QuantileMark addresses a fundamental limitation of current multi-bit watermarks. By ensuring that no single message is "harder" to embed than another, it guarantees fair service quality and reliable attribution for all users.
Provider-Internal Optimization: The method leverages white-box access to maximize detection signal strength without compromising stealth, making it ideal for internal provider verification (e.g., tracing toxic content or copyright violations).
Theoretical to Practical Bridge: It provides a mathematically rigorous approach (equal-mass quantile partitioning) that translates directly into robust, high-performance empirical results, setting a new standard for multi-bit provenance in LLMs.

In conclusion, QuantileMark offers a practically viable solution for multi-bit attribution that balances message symmetry, detection robustness, and generation quality, overcoming the structural asymmetries inherent in vocabulary-partition approaches.