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

Jiahao Xu; Rui Hu; Olivera Kotevska; Zikai Zhang

cs.CLApr 6, 2026

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

Authors: Jiahao Xu, Rui Hu, Olivera Kotevska, Zikai Zhang

Organizations: University of Nevada, Reno · Oak Ridge National Laboratory

Abstract

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.

Figures & tables

Figure 1: Illustration of the encoder and decoder for MPAC (top) and LoSo (bottom).

Figure 2: Left: Perplexity vs.

T

for MPAC, LoSo , and clean (unwatermarked) text. Right: Bit accuracy vs.

T

for MPAC and LoSo . Note that we do not report bit accuracy for clean text, since it corresponds to the false-positive case. Results are from the text completion task on LLaMA-

2

7

B Touvron et al. (2023) using C

4

dataset Raffel et al. (2020) , with message length

b=16

under varying output sequence lengths

T

Figure 3: Illustration showing that tokens in

\mathcal{E}

may originate from different shards across multiple permutations.

Method	$T=150$		$T=200$		$T=250$		$T=300$		Avg. BA $\uparrow$	Avg. PPL $\downarrow$
Method	BA $\uparrow$	PPL $\downarrow$	BA $\uparrow$	PPL $\downarrow$	BA $\uparrow$	PPL $\downarrow$	BA $\uparrow$	PPL $\downarrow$	Avg. BA $\uparrow$	Avg. PPL $\downarrow$
Text Completion
CycleShift	$95.25$	$5.17$	$98.00$	$5.02$	$97.00$	$5.07$	$98.25$	$4.96$	$97.13$	$5.06$
DepthW	$79.50$	$4.62$	$89.00$	$4.67$	$90.50$	$4.63$	$95.75$	$4.62$	$88.69$	$4.64$
StealthInk	$85.00$	$4.13$	$89.50$	$4.21$	$92.25$	$4.13$	$92.50$	$4.04$	$89.81$	$4.13$
MPAC	$94.00$	$5.19$	$94.00$	$5.00$	$96.25$	$5.03$	$98.25$	$5.10$	$95.63$	$5.08$

Table 1: Comparison of methods on three downstream tasks with

b=8

under different token budgets

T\in\{150,200,250,300\}

. The average PPL of unwatermarked texts is

3.97

4.59

, and

3.69

for the three tasks, respectively, serving as the lower bounds for the PPLs of watermarked texts.

Figure 4: Impact of message length

b

on BA for MPAC, RSBH, StealthInk, and XMark on the text completion and text summarization tasks.

Figure 5: Impact of bias

\delta

on BA and PPL for MPAC, RSBH, and XMark on the text summarization and story generation tasks. Hollow markers indicate results with

\delta=3

, while solid markers correspond to

\delta=4

Figure 6: Robustness of methods against text editing attacks on the text completion task with

b=16

Method	BA $\uparrow$	PPL $\downarrow$	R.-1 $\uparrow$	R.-Lsum $\uparrow$	BLEU $\uparrow$
RSBH	$58.62$	$7.60$	$0.61$	$0.58$	$38.96$
MPAC	$60.88$	$7.54$	$0.65$	$0.61$	$43.21$
XMark	$64.62$	$7.26$	$0.64$	$0.61$	44.52

Table 2: Results on the machine translation task using WMT14 German-to-English dataset.

Method	BA $\uparrow$	PPL $\downarrow$	R.-1 $\uparrow$	R.-Lsum $\uparrow$	BSc. $\uparrow$
RSBH	$84.47$	$4.46$	$0.36$	$0.33$	$0.8266$
MPAC	$85.81$	$4.71$	$0.35$	$0.32$	$0.8254$
XMark	$93.00$	$4.50$	$0.38$	$0.35$	$0.8304$

Table 3: Performance comparison with long messages (

b=64

) and long generated texts (

T=1000

) on the text completion task.

Method	Encoding	Decoding	BA $\uparrow$
DepthW	$11.51$	$16.16$	$79.50$
MPAC	$10.93$	$0.06$	$94.00$
RSBH	$11.80$	$8.45$	$92.75$
StealthInk	$11.47$	$0.07$	$85.00$
XMark	$11.54$	$0.08$	$98.75$

Table 4: Comparison of runtime (in seconds) and BA under the default setting.

Method	$T=150$		$T=250$		Avg. BA $\uparrow$	Avg. PPL $\downarrow$
Method	BA $\uparrow$	PPL $\downarrow$	BA $\uparrow$	PPL $\downarrow$
LoSo	$74.06$	$4.45$	$81.38$	$4.46$	$77.72$	$4.46$
XMark ( $k{=}2$ )	$82.62$	$4.84$	$88.00$	$4.60$	$85.31$	$4.72$
XMark ( $k{=}3$ )	$82.94$	$5.01$	$89.38$	$4.97$	$86.16$	$4.99$
XMark ( $k{=}4$ )	$84.25$	$5.07$	$92.06$	$5.14$	$88.16$	$5.11$
XMark - ( $k{=}2$ )	$81.31$	$-$	$88.06$	$-$	$84.69$	$-$

Table 5: Ablation study of XMark with different numbers of hash keys (

k

) and different token–shard mapping matrices: cTMM in XMark vs. TMM in XMark - .

Appendix figures & tables5 assets

Supplementary material from the paper’s appendix.

Appendix

Symbol	Description
$\gamma$	The green list ratio
$\mathbf{m}$	The binary multi-bit message
$b$	The length of message $\mathbf{m}$
$f$	The large language model
$\mathbf{x}_{p}$	The input prompt
$\mathbf{x}_{s}$	The suspect text

Appendix

Table 6: Notation table.

Task (Dataset)	Method	$T=150$		$T=200$		$T=250$		$T=300$		Avg. BA $\uparrow$	Avg. PPL $\downarrow$
Task (Dataset)	Method	BA $\uparrow$	PPL $\downarrow$	BA $\uparrow$	PPL $\downarrow$	BA $\uparrow$	PPL $\downarrow$	BA $\uparrow$	PPL $\downarrow$	Avg. BA $\uparrow$	Avg. PPL $\downarrow$
Text Completion (Essays)	StealthInk	$71.62$	$4.12$	$75.00$	$3.90$	$78.88$	$3.75$	$79.25$	$3.66$	$76.19$	$3.86$
	MPAC	$85.88$	$5.37$	$89.12$	$5.09$	$91.75$	$4.93$	$92.88$	$4.78$	$89.91$	$5.04$
	RSBH	$80.12$	$4.97$	$85.00$	$4.80$	$89.75$	$4.66$	$91.00$	$4.53$	$86.47$	$4.74$
	XMark	$92.62$	$4.88$	$95.62$	$4.68$	$97.12$	$4.50$	$97.75$	$4.40$	$95.78$	$4.62$
Text Completion (OpenGen)	StealthInk	$72.75$	$4.11$	$75.75$	$3.98$	$77.88$	$4.04$	$80.12$	$3.85$	$76.63$	$3.99$

Appendix

Table 7: Performance comparison on text completion tasks with message length

b=16

under different numbers of available tokens

T\in\{150,200,250,300\}

on the Essays and OpenGen datasets.

Task (Dataset)	Method	$T=150$		$T=200$		$T=250$		$T=300$		Avg. BA $\uparrow$	Avg. PPL $\downarrow$
Task (Dataset)	Method	BA $\uparrow$	PPL $\downarrow$	BA $\uparrow$	PPL $\downarrow$	BA $\uparrow$	PPL $\downarrow$	BA $\uparrow$	PPL $\downarrow$	Avg. BA $\uparrow$	Avg. PPL $\downarrow$
Text Completion (Essays)	StealthInk	$65.94$	$4.17$	$67.76$	$3.96$	$71.12$	$3.84$	$72.12$	$3.74$	$69.24$	$3.93$
	MPAC	$77.81$	$5.03$	$80.38$	$4.89$	$80.94$	$4.76$	$83.19$	$4.65$	$80.58$	$4.83$
	RSBH	$75.06$	$5.07$	$80.38$	$4.77$	$82.00$	$4.67$	$84.06$	$4.54$	$80.38$	$4.76$
	XMark	$82.38$	$4.89$	$85.38$	$4.65$	$89.31$	$4.44$	$91.25$	$4.32$	$87.08$	$4.58$
Text Completion (OpenGen)	StealthInk	$67.12$	$4.22$	$67.88$	$4.03$	$69.94$	$4.07$	$71.69$	$4.01$	$69.16$	$4.08$

Appendix

Table 8: Performance comparison on text completion tasks with message length

b=32

under different numbers of available tokens

T\in\{150,200,250,300\}

on the Essays and OpenGen datasets.

Method	Detection Mechanism and Threshold	TPR@ $10\%$ FPR $\uparrow$	F1 Score $\uparrow$
CycleShift	$p$ -value ( $p<2\mathrm{e}^{-2}$ )	$80.00$	$0.85$
MPAC	$z$ -score ( $z>4.10$ )	$98.00$	$0.94$
StealthInk	$p$ -value ( $p<8\mathrm{e}^{-4}$ )	$60.00$	$0.70$
XMark	Standard Deviation ( $\sigma>3.30$ )	$94.00$	$0.92$

Appendix

Table 9: False positive detection performance measured by TPR at

10\%

FPR (TPR@

10\%

FPR) and F

1

score.

Message Length	Model	Method	$T=150$		$T=200$		$T=250$		$T=300$		Avg. BA $\uparrow$	Avg. PPL $\downarrow$
Message Length	Model	Method	BA $\uparrow$	PPL $\downarrow$	BA $\uparrow$	PPL $\downarrow$	BA $\uparrow$	PPL $\downarrow$	BA $\uparrow$	PPL $\downarrow$	Avg. BA $\uparrow$	Avg. PPL $\downarrow$
$b=8$	Qwen $2.5$ - $7$ B	MPAC	$96.50$	$8.25$	$98.00$	$7.69$	$98.50$	$7.57$	$98.50$	$7.66$	$97.88$	$7.79$
	Qwen $2.5$ - $7$ B	XMark	$97.75$	$7.66$	$100.00$	$7.19$	$100.00$	$7.07$	$100.00$	$7.00$	$99.44$	$7.23$
	LLaMA- $3.1$ - $8$ B	MPAC	$97.25$	$6.55$	$98.25$	$6.44$	$98.75$	$6.38$	$99.50$	$6.33$	$98.44$	$6.43$
	LLaMA- $3.1$ - $8$ B	XMark	$100.00$	$6.37$	$99.75$	$6.05$	$100.00$	$5.98$	$100.00$	$5.94$	$99.94$	$6.09$
$b=16$	Qwen $2.5$ - $7$ B	MPAC	$91.12$	$7.97$	$91.00$	$7.90$	$94.75$	$7.54$	$95.38$	$7.55$	$93.06$	$7.74$

Appendix

Table 10: Performance comparison of MPAC and XMark on Qwen

2.5

7

B and LLaMA-

3.1

8

B models with message lengths

b\in\{8,16\}

and number of available tokens

T\in\{150,200,250,300\}

Explore similar work

Majority Bit-Aware Watermarking For Large Language Models
Aug 5, 2025Jiahao 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
QuantileMark: A Message-Symmetric Multi-bit Watermark for LLMs
Apr 15, 2026Junlin Zhu, Baizhou Huang, Xiaojun WanText Watermarking LLM Watermarking
Wangxuan Institute of Computer Technology, Peking University

Aug 5, 2025J/K move · Enter open · S save

Majority Bit-Aware Watermarking For Large Language Models

Jiahao Xu, Rui Hu, Olivera Kotevska, Zikai Zhang

University of Nevada, Reno · Oak Ridge National Laboratory

Text Watermarking LLM Watermarking

Open paper AskPDF arXiv

The growing deployment of Large Language Models (LLMs) has raised concerns about their misuse in generating harmful or deceptive content. To address this issue, watermarking methods have been proposed to embed identifiable multi-bit messages into generated text for misuse tracing. However, existing methods often suffer from a fundamental trade-off between text quality and decoding accuracy. In particular, they have to restrict the size of the preferred token set (i.e., green list) during encoding to maintain a detectable watermark signal for decoding, which inevitably degrades generation quality. To improve this trade-off, we propose a novel message encoding paradigm called majority bit-aware encoding, which relaxes the watermark signal strength from the green list size. This strategy allows for a strong watermark signal to be preserved in generated texts even when using a large green list. We introduce two instantiations of this paradigm: MajorMark and MajorMark

^{+}

, where the latter is specifically optimized for long messages. Extensive experiments on state-of-the-art LLMs demonstrate that our methods achieve higher decoding accuracy and superior text quality compared to prior baselines. The code is at https://github.com/JiiahaoXU/MajorMark.

Abstract

Explore similar work

Majority Bit-Aware Watermarking For Large Language Models

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

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