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

Junlin Zhu; Baizhou Huang; Xiaojun Wan

cs.CLApr 15, 2026

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

Authors: Junlin Zhu, Baizhou Huang, Xiaojun Wan

Organizations: Wangxuan Institute of Computer Technology, Peking University

Abstract

As large language models become standard backends for content generation, practical provenance increasingly requires multi-bit watermarking. In provider-internal deployments, a key requirement is message symmetry: the message itself should not systematically affect either text quality or verification outcomes. Vocabulary-partition watermarks can break message symmetry in low-entropy decoding: some messages are assigned most of the probability mass, while others are forced to use tail tokens. This makes embedding quality and message decoding accuracy message-dependent. We propose QuantileMark, a white-box multi-bit watermark that embeds messages within the continuous cumulative probability interval $[0, 1)$ . At each step, QuantileMark partitions this interval into $M$ equal-mass bins and samples strictly from the bin assigned to the target symbol, ensuring a fixed $1/M$ probability budget regardless of context entropy. For detection, the verifier reconstructs the same partition under teacher forcing, computes posteriors over latent bins, and aggregates evidence for verification. We prove message-unbiasedness, a property ensuring that the base distribution is recovered when averaging over messages. This provides a theoretical foundation for generation-side symmetry, while the equal-mass design additionally promotes uniform evidence strength across messages on the detection side. Empirical results on C4 continuation and LFQA show improved multi-bit recovery and detection robustness over strong baselines, with negligible impact on generation quality. Our code is available at GitHub (https://github.com/zzzjunlin/QuantileMark).

Figures & tables

Panel of Figure 1 — Figure 1: Impact of probability mass partitioning strategies on message symmetry under a low-entropy distribution. (a) Vocabulary Partition allocates uneven probability budgets to messages that should ideally be weighted equally. (b) Equal-Mass Partition assigns a fixed probability budget to each message.

Panel of Figure 2 — Figure 2: Overview of QuantileMark, where $m=2$ , $H=4$ . (a) Embedding: The key-derived logic (green) maps symbol to target bin $B_{r^{\star}}$ (blue frame). A random value $u$ (red dashed line) is sampled uniformly within this bin, forcing the selection of the token is whose interval covers $u$ . (b) Detection: Posteriors (blue bars) form the evidence $\mathrm{LPO}$ at this step. These scores are aggregated across steps assigned to position $i_{t}=2$ (right, blue columns) to decode $\hat{s}_{2}$ .

	C4					LFQA
Method	Bit Acc $\uparrow$	AUC $\uparrow$	TPR@ 1%FPR $\uparrow$	PPL $\downarrow$	Time (s) $\downarrow$	Bit Acc $\uparrow$	AUC $\uparrow$	TPR@ 1%FPR $\uparrow$	PPL $\downarrow$	Time (s) $\downarrow$
No watermark	–	–	–	7.684	–	–	–	–	2.647	–
MPAC	0.9702	0.9887	0.9800	10.351	0.103	0.8770	0.9756	0.8056	3.793	0.111
StealthInk	0.9003	0.9869	0.7920	8.235	0.645	0.7447	0.8301	0.2425	2.636	1.013
QuantileMark (ours)	0.9893	0.9995	0.9840	7.404	0.343	0.9500	0.9997	1.0	2.759	0.348

Table 1: Generation and detection performance on C4 and LFQA with 24 bits embedded in 300 tokens. Time (s) denotes average detection time per sample.

Panel of Figure 3 — Figure 3: Varying detection length $T$ on Llama-3.1-8B-Instruct for LFQA.

	No attack		Copy-paste ( $\epsilon=0.2$ )		Synonym ( $\epsilon=0.2$ )		Deletion ( $\epsilon=0.1$ )		Paraphrase (Dipper)
Method	Bit Acc $\uparrow$	AUC $\uparrow$	Bit Acc $\uparrow$	AUC $\uparrow$	Bit Acc $\uparrow$	AUC $\uparrow$	Bit Acc $\uparrow$	AUC $\uparrow$	Bit Acc $\uparrow$	AUC $\uparrow$
MPAC	0.9702	0.9887	0.9438	0.9849	0.9476	0.9876	0.8811	0.9750	0.7201	0.7936
StealthInk	0.9003	0.9869	0.8497	0.9550	0.8608	0.9701	0.7839	0.8854	0.6829	0.6536
QuantileMark	0.9893	0.9995	0.9730	0.9972	0.9712	0.9963	0.8712	0.9426	0.7640	0.7609

Table 2: Robustness on C4 with 24 bits embedded in 300 tokens. The attack intensities

\epsilon

denote the fraction of tokens modified.

Panel of Figure 4 — Figure 4: LFQA ablation of $m$ for QuantileMark with 24 bits embedded. We vary the bits per symbol $m$ ( $M=2^{m}$ quantile bins).

Panel of Figure 5 — Figure 5: Detector-generator mismatch analysis on Llama-3.1-8B-Instruct.

	Machine translation			Summarization
Method	BLEU $\uparrow$	R-1 $\uparrow$	BERT $\uparrow$	R-1 $\uparrow$	BERT $\uparrow$	PPL $\downarrow$
No watermark	17.55	49.13	35.82	37.42	21.40	5.18
MPAC	16.89	47.98	34.89	36.81	20.57	5.81
StealthInk	17.42	48.97	35.75	37.08	20.83	5.72
QuantileMark	17.41	48.99	35.99	37.44	21.37	5.21

Table 3: Downstream generation quality under top-

k{=}128

sampling. For machine translation, we report BLEU, ROUGE-1 (R-1), and BERTScore (BERT). For summarization, we report ROUGE-1, BERTScore, and perplexity (PPL).

Appendix figures & tables6 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 6 — Figure 6: Performance comparison on LFQA with varying bits per symbol ( $m$ ) using LLR as the token-level evidence. This serves as a complement to Figure 4 , which uses LPO.

Evidence	Bit Acc $\uparrow$	Detection AUC $\uparrow$	Score on wm ( $\mu\pm\sigma$ )	Score on no wm ( $\mu\pm\sigma$ )
C4
LPO	0.9868	0.9989	2.215 $\pm$ 1.134	-2.791 $\pm$ 0.531
LLR	0.9879	0.9751	-0.9069 $\pm$ 0.414	-3.336 $\pm$ 0.659
LFQA
LPO	0.9500	0.9997	-0.046 $\pm$ 0.949	-3.152 $\pm$ 0.410
LLR	0.9470	0.9980	-0.899 $\pm$ 0.359	-4.291 $\pm$ 0.554

Appendix

Table 4: Comparison of LPO and LLR evidence within QuantileMark (

m=2,H=12

) on C4 and LFQA. Score entries report mean

\pm

standard deviation.

	C4		LFQA
Method	AUC $\uparrow$	TPR@ 1%FPR $\uparrow$	AUC $\uparrow$	TPR@ 1%FPR $\uparrow$
MPAC	0.9993	0.986	0.9744	0.8337
StealthInk	0.9851	0.6960	0.8081	0.1824
QuantileMark	0.9998	0.9900	0.9985	0.9499

Appendix

Table 5: Detection performance on C4 and LFQA with 24 bits embedded in 300 tokens. Negatives are non-watermarked text generated by model.

Method	GPT-4o $\uparrow$
No watermark	4.115
MPAC	3.921
StealthInk	4.047
QuantileMark	4.109

Appendix

Table 6: LFQA answer quality judged by GPT-4o. Scores are on a 1–5 scale; higher is better. We randomly sample 500 prompts from LFQA and generate answers with a maximum length of

T{=}300

new tokens. During evaluation, we exclude outputs shorter than 50 tokens to mitigate potential length-related bias.

Message length (bits)	Bit Acc $\uparrow$	AUC $\uparrow$
24	0.9500	0.9997
32	0.9196	0.9997
40	0.9025	0.9997
48	0.8801	0.9994
56	0.8690	0.9995

Appendix

Table 7: Effect of increasing message length on LFQA (

T{=}300

m{=}2

). Detection AUC remains near-perfect, while bit accuracy degrades gracefully as each symbol receives fewer supporting tokens.

Method	Bit Acc $\uparrow$	AUC $\uparrow$	PPL $\downarrow$
QuantileMark	0.9500	0.9997	2.759
+ skip repeated seed	0.9438	0.9996	2.644

Appendix

Table 8: Effect of skipping repeated seeds on LFQA. Skipping slightly reduces PPL and mitigates sentence-level bias, while maintaining detection performance.

Explore similar work

CertMark: Distortion-Free Multi-Bit Watermarking with Certified Decoding
Sep 27, 2026Paweł Batorski, Przemysław Spurek, Paul SwobodaLLM Watermarking Robust Watermarking
Heinrich Heine University Düsseldorf · Jagiellonian University · IDEAS Research Institute
XMark: Reliable Multi-Bit Watermarking for LLM-Generated Texts
Apr 6, 2026Jiahao Xu, Rui Hu, Olivera Kotevska +1Text Watermarking LLM Watermarking
University of Nevada, Reno · Oak Ridge National Laboratory
Every Bit, Everywhere, All at Once: A Binomial Multibit LLM Watermark
May 12, 2026Thibaud Gloaguen, Robin Staab, Mark Vero +1Text Watermarking LLM Watermarking
ETH Zurich

Sep 27, 2026J/K move · Enter open · S save

CertMark: Distortion-Free Multi-Bit Watermarking with Certified Decoding

Paweł Batorski, Przemysław Spurek, Paul Swoboda

Heinrich Heine University Düsseldorf · Jagiellonian University · IDEAS Research Institute

LLM Watermarking Robust Watermarking

Open paper AskPDF arXiv

Leading multi-bit watermarking methods for language models encode messages by biasing the model's next-token probabilities, creating a trade-off between message recovery and text quality. Their decoders typically return the highest-scoring candidate from accumulated token-level evidence, without a certified abstention rule that bounds the probability of outputting an incorrect message. We introduce CertMark, a distribution-preserving multi-bit watermark with certified decoding. Rather than modifying probabilities, CertMark uses the embedded message to seed an exact Gumbel-max sampler, thereby preserving the model's original sampling distribution. We propose two scalable decoders: a model-agnostic, text-only decoder and a model-aware variant that leverages the original next-token distributions for stronger recovery. Both support certified abstention with mathematical bounds on the probability of returning an incorrect message. Across text completion, summarization, and story generation, CertMark matches the perplexity of unwatermarked text while reliably recovering multi-bit messages. The model-aware decoder further achieves higher bit accuracy than probability-biasing baselines. Our code is publicly available at https://github.com/Batorskq/CertMark.

Abstract

Explore similar work

CertMark: Distortion-Free Multi-Bit Watermarking with Certified Decoding

XMark: Reliable Multi-Bit Watermarking for LLM-Generated Texts

Every Bit, Everywhere, All at Once: A Binomial Multibit LLM Watermark