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
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.
Figure 2: Overview of QuantileMark, where m=2 , H=4 . (a) Embedding: The key-derived logic (green) maps symbol to target bin Br⋆ (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 LPO at this step. These scores are aggregated across steps assigned to position it=2 (right, blue columns) to decode s^2 .
C4
LFQA
Method
Bit Acc ↑
AUC ↑
TPR@ 1%FPR ↑
PPL ↓
Time (s) ↓
Bit Acc ↑
AUC ↑
TPR@ 1%FPR ↑
PPL ↓
Time (s) ↓
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.
Figure 3: Varying detection length T on Llama-3.1-8B-Instruct for LFQA.
No attack
Copy-paste ( ϵ=0.2 )
Synonym ( ϵ=0.2 )
Deletion ( ϵ=0.1 )
Paraphrase (Dipper)
Method
Bit Acc ↑
AUC ↑
Bit Acc ↑
AUC ↑
Bit Acc ↑
AUC ↑
Bit Acc ↑
AUC ↑
Bit Acc ↑
AUC ↑
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 ϵ denote the fraction of tokens modified.
Figure 4: LFQA ablation of m for QuantileMark with 24 bits embedded. We vary the bits per symbol m ( M=2m quantile bins).
Figure 5: Detector-generator mismatch analysis on Llama-3.1-8B-Instruct.
Machine translation
Summarization
Method
BLEU ↑
R-1 ↑
BERT ↑
R-1 ↑
BERT ↑
PPL ↓
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
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 ↑
Detection AUC ↑
Score on wm ( μ±σ )
Score on no wm ( μ±σ )
C4
LPO
0.9868
0.9989
2.215 ± 1.134
-2.791 ± 0.531
LLR
0.9879
0.9751
-0.9069 ± 0.414
-3.336 ± 0.659
LFQA
LPO
0.9500
0.9997
-0.046 ± 0.949
-3.152 ± 0.410
LLR
0.9470
0.9980
-0.899 ± 0.359
-4.291 ± 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 ± standard deviation.
C4
LFQA
Method
AUC ↑
TPR@ 1%FPR ↑
AUC ↑
TPR@ 1%FPR ↑
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 ↑
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 ↑
AUC ↑
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 ↑
AUC ↑
PPL ↓
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.
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.
Paweł Batorski, Przemysław Spurek, Paul Swoboda
Heinrich Heine University Düsseldorf · Jagiellonian University · IDEAS Research Institute
Multi-bit watermarking has emerged as a promising solution for embedding imperceptible binary messages into Large Language Model (LLM)-generated text, enabling reliable attribution and tracing of malicious usage of LLMs. Despite recent progress, existing methods still face key limitations: some become computationally infeasible for large messages, while others suffer from a poor trade-off between text quality and decoding accuracy. Moreover, the decoding accuracy of existing methods drops significantly when the number of tokens in the generated text is limited, a condition that frequently arises in practical usage. To address these challenges, we propose XMark, a novel method for encoding and decoding binary messages in LLM-generated texts. The unique design of XMark's encoder produces a less distorted logit distribution for watermarked token generation, preserving text quality, and also enables its tailored decoder to reliably recover the encoded message with limited tokens. Extensive experiments across diverse downstream tasks show that XMark significantly improves decoding accuracy while preserving the quality of watermarked text, outperforming prior methods. The code is at https://github.com/JiiahaoXU/XMark.
Jiahao Xu, Rui Hu, Olivera Kotevska +1
University of Nevada, Reno · Oak Ridge National Laboratory
With LLM watermarking already being deployed commercially, practical applications increasingly require multibit watermarks that encode more complex payloads, such as user IDs or timestamps, into the generated text. In this work, we propose a fundamentally new approach for multibit watermarking: introducing binomial encoding to directly encode every bit of the payload at every token position. We complement our approach with a stateful encoder that during generation dynamically redirects encoding pressure toward underencoded bits. Our evaluation against 8 baselines on up to 64-bit payloads shows that our scheme achieves superior message accuracy and robustness, with the gap to baseline methods widening in more relevant settings (i.e., large payloads and low-distortion regimes). At the same time, we challenge prior works' evaluation metrics, highlighting their lack of practical insights, and introduce per-bit confidence scoring as a practically relevant metric for evaluating multibit LLM watermarks.