Majority Bit-Aware Watermarking For Large Language Models

Jiahao Xu; Rui Hu; Olivera Kotevska; Zikai Zhang

cs.CLAug 5, 2025

Majority Bit-Aware Watermarking For Large Language Models

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

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

Abstract

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.

Figures & tables

Method	Encoding	Decoding
Method	$\mathbb{E}_{\mathbf{m}}[\gamma]$	$\times\|\mathbf{x}\|$	Eff.?
CTWL ctwl †	$-$	$2^{b}$	✗
CycleShift cycleshift	$=0.25$	$2^{b}$	✗
DepthW depthw	$=0.50$	$2^{b}$	✗
RSBH rsbh ‡	$=0.50$	$2^{d}$	✓
MPAC mpac	$=0.25$	$1$	✓

Table 1: Comparison of representative multi-bit LLM watermarking methods.

\mathbb{E}_{\mathbf{m}}[\gamma]

denotes the expected green list ratio over all possible messages.

\times|\mathbf{x}|

indicates that the decoding process requires how many enumerations over all tokens in the input text

\mathbf{x}

. “Eff.?” reflects whether the decoding procedure is computationally efficient.

Figure 1: Impact of green list ratio

\gamma

on the utility of watermarked text (right) and the decoding accuracy (left).

Panel of Figure 2 — Figure 2: An overview of the majority bit-aware encoding process of MajorMark and MajorMark + .

Figure 3: Occurrence distributions for candidate $\lambda$ (0 or 1). Distribution produced by the correct $\lambda$ exhibits significant skewness.

Method	$\delta=2$			$\delta=4$			$\delta=6$			Avg. BA $\uparrow$	Avg. PPL $\downarrow$
Method	BA $\uparrow$	PPL $\downarrow$	Top- $\mathbf{5}$ $\uparrow$	BA $\uparrow$	PPL $\downarrow$	Top- $\mathbf{5}$ $\uparrow$	BA $\uparrow$	PPL $\downarrow$	Top- $\mathbf{5}$ $\uparrow$	Avg. BA $\uparrow$	Avg. PPL $\downarrow$
Message length $b=8$
CycleShift	$\mathbf{100.00}$	$5.09$	$90.72$	$\mathbf{100.00}$	$8.64$	$81.43$	$\mathbf{100.00}$	$15.44$	$75.65$	$\mathbf{100.00}$	$9.72$
DepthW	$95.62$	$4.53$	$91.65$	$\mathbf{100.00}$	$8.24$	$79.53$	$\mathbf{100.00}$	$25.49$	$61.13$	$98.54$	$12.75$
MPAC	$99.38$	$5.03$	$90.41$	$\mathbf{100.00}$	$8.74$	$81.44$	$\mathbf{100.00}$	$16.06$	$74.52$	$99.79$	$9.94$
RSBH	$\mathbf{100.00}$	$4.80$	$91.19$	$\mathbf{100.00}$	$6.36$	$89.30$	$\mathbf{100.00}$	$8.66$	$86.87$	$\mathbf{100.00}$	$6.61$

Table 2: Comparison of methods across various message lengths and watermarking biases. The PPL of non-watermarked text is

3.81

, serving as a lower bound for the PPL of all watermarked texts.

Figure 4: BA of different methods under varying numbers of observed tokens

T

with

b=64

Figure 5: BA and PPL of methods with increasing message length

b\in\{32,40,48,56,64\}

with

\delta=4

Method	LLaMA- $3.1$ - $8$ B		Qwen $3$ - $8$ B
Method	PPL $\downarrow$	BA $\uparrow$	PPL $\downarrow$	BA $\uparrow$
MPAC	$8.34$	$97.72$	$5.65$	$92.66$
StealthInk	$\mathbf{4.83}$	$83.84$	$\mathbf{3.50}$	$49.31$
BiMark	$8.39$	$99.47$	$5.05$	$96.66$
MajorMark	$6.79$	$98.41$	$4.91$	$96.91$
MajorMark +	$6.51$	$\mathbf{99.81}$	$4.75$	$\mathbf{98.50}$

Table 3: Evaluation on recent public LLMs with

100

users.

Figure 6: BA of different methods under Copy-Paste and Paraphrase attacks.

Method	PPL $\downarrow$	BA $\uparrow$
Method	PPL $\downarrow$	CharP	SenS
MPAC	$6.36$	$81.88$	$95.31$
RSBH	$5.47$	$78.28$	$93.25$
MajorMark	$5.31$	$\mathbf{82.84}$	$94.97$
MajorMark +	$\mathbf{5.19}$	$81.56$	$\mathbf{96.72}$

Table 4: Robustness evaluation under character-level perturbation (CharP) and sentence shuffling (SenS).

Method	Enc. (s)	Dec. (s)	BA $\uparrow$
DepthW	$37.87$	$\approx 8.89\times 10^{8}$ (Est.)	-
MPAC	$36.13$	$0.13$	$89.22$
RSBH	$36.06$	$25.56$	$89.38$
MajorMark	$36.58$	$2.18$	$96.74$
MajorMark +	$36.85$	$12.70$	$97.81$

Table 5: Comparison of runtime (in seconds) and BA. The decoding time for DepthW is estimated.

Method	$\delta=2$		$\delta=4$		Avg. BA $\uparrow$	Avg. PPL $\downarrow$
Method	BA $\uparrow$	PPL $\downarrow$	BA $\uparrow$	PPL $\downarrow$
$\mathtt{KMeans}$	$96.74$	$4.43$	$99.06$	$6.32$	$97.90$	$5.38$
$\mathtt{AC}$	$94.06$	$4.43$	$99.84$	$6.32$	$96.95$	$5.38$
$\mathtt{GMM}$	$92.81$	$4.43$	$99.84$	$6.32$	$96.33$	$5.38$
$r=1$	$95.94$	$4.74$	$100.00$	$6.55$	$97.97$	$5.65$
$r=2$	$97.81$	$4.49$	$100.00$	$6.05$	$98.91$	$5.27$

Table 6: Ablation study of MajorMark (first three rows) and MajorMark + (last four rows), evaluating clustering methods and block sizes, respectively.

Appendix figures & tables11 assets

Supplementary material from the paper’s appendix.

Appendix

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

Appendix

Table 7: Notation table.

Model	Method	$\delta=2$			$\delta=4$			Avg. BA $\uparrow$	Avg. PPL $\downarrow$	Avg. Top- $\mathbf{5}$ $\uparrow$
Model	Method	BA $\uparrow$	PPL $\downarrow$	Top- $\mathbf{5}$ $\uparrow$	BA $\uparrow$	PPL $\downarrow$	Top- $\mathbf{5}$ $\uparrow$	Avg. BA $\uparrow$	Avg. PPL $\downarrow$	Avg. Top- $\mathbf{5}$ $\uparrow$
Message length $b=32$
Qwen $2.5$ - $7$ B	MajorMark	$96.25$	$6.69$	$86.99$	$99.22$	$8.49$	$85.29$	$97.74$	$7.59$	$86.14$
Qwen $2.5$ - $7$ B	MajorMark +	$98.75$	$6.31$	$88.39$	$100.00$	$8.85$	$84.77$	$\mathbf{99.38}$	$\mathbf{7.58}$	$\mathbf{86.58}$
Gemma- $2$ B	MajorMark	$96.41$	$7.02$	$87.16$	$99.06$	$9.80$	$83.38$	$97.74$	$8.41$	$\mathbf{85.27}$
Gemma- $2$ B	MajorMark +	$99.38$	$6.95$	$86.02$	$100.00$	$9.69$	$84.36$	$\mathbf{99.69}$	$\mathbf{8.32}$	$85.19$

Appendix

Table 8: Performance of MajorMark and MajorMark + on Qwen

2.5

7

B, Gemma-

2

B, and LLaMA-

3.1

8

B with

b\in\{32,64\}

and

\delta\in\{2,4\}

. The PPL for non-watermarked texts generated by Qwen

2.5

7

B, Gemma-

2

B, and LLaMA-

3.1

8

B are

4.97

5.71

, and

4.27

, respectively.

Method	$\delta=2$			$\delta=4$			$\delta=6$			Avg. BA $\uparrow$	Avg. PPL $\downarrow$	Avg. Top- $\mathbf{5}$ $\uparrow$
Method	BA $\uparrow$	PPL $\downarrow$	Top- $\mathbf{5}$ $\uparrow$	BA $\uparrow$	PPL $\downarrow$	Top- $\mathbf{5}$ $\uparrow$	BA $\uparrow$	PPL $\downarrow$	Top- $\mathbf{5}$ $\uparrow$	Avg. BA $\uparrow$	Avg. PPL $\downarrow$	Avg. Top- $\mathbf{5}$ $\uparrow$
Message length $b=32$
MPAC	$86.56$	$4.77$	$91.26$	$97.34$	$9.23$	$81.86$	$99.38$	$15.08$	$76.41$	$94.43$	$9.69$	$83.18$
RSBH	$84.53$	$4.68$	$92.47$	$96.56$	$6.43$	$89.98$	$97.66$	$8.64$	$88.47$	$92.92$	$6.58$	$90.31$
MajorMark	$90.94$	$4.35$	$92.83$	$97.81$	$6.02$	$90.01$	$99.38$	$8.51$	$87.95$	$96.04$	$6.29$	$90.26$
MajorMark +	$\mathbf{92.03}$	$\mathbf{4.09}$	$\mathbf{93.85}$	$\mathbf{99.38}$	$\mathbf{5.63}$	$\mathbf{91.16}$	$\mathbf{100.00}$	$\mathbf{7.96}$	$\mathbf{88.90}$	$\mathbf{97.14}$	$\mathbf{5.89}$	$\mathbf{91.30}$

Appendix

Table 9: Performance comparison of watermarking methods (MPAC, RSBH, MajorMark, and MajorMark + ) on the OpenGen dataset with message lengths

b\in\{32,64\}

and watermarking biases

\delta\in\{2,4,6\}

Method	$\delta=2$			$\delta=4$			$\delta=6$			Avg. BA $\uparrow$	Avg. PPL $\downarrow$	Avg. Top- $\mathbf{5}$ $\uparrow$
Method	BA $\uparrow$	PPL $\downarrow$	Top- $\mathbf{5}$ $\uparrow$	BA $\uparrow$	PPL $\downarrow$	Top- $\mathbf{5}$ $\uparrow$	BA $\uparrow$	PPL $\downarrow$	Top- $\mathbf{5}$ $\uparrow$	Avg. BA $\uparrow$	Avg. PPL $\downarrow$	Avg. Top- $\mathbf{5}$ $\uparrow$
Message length $b=32$
MPAC	$88.44$	$4.29$	$92.18$	$98.75$	$9.28$	$80.54$	$99.69$	$14.91$	$75.30$	$95.63$	$9.49$	$82.67$
RSBH	$89.22$	$4.23$	$93.31$	$97.66$	$6.33$	$88.98$	$97.66$	$7.78$	$87.78$	$94.85$	$6.11$	$90.02$
MajorMark	$91.41$	$\mathbf{4.12}$	$93.24$	$98.28$	$5.98$	$89.60$	$99.53$	$7.71$	$87.70$	$96.41$	$5.94$	$90.18$
MajorMark +	$\mathbf{96.72}$	$4.21$	$\mathbf{93.37}$	$\mathbf{100.00}$	$\mathbf{5.83}$	$\mathbf{90.44}$	$\mathbf{100.00}$	$\mathbf{7.40}$	$\mathbf{88.92}$	$\mathbf{98.91}$	$\mathbf{5.81}$	$\mathbf{90.91}$

Appendix

Table 10: Performance comparison of watermarking methods (MPAC, RSBH, MajorMark, and MajorMark + ) on the Essays dataset with message lengths

b\in\{32,64\}

and watermarking biases

\delta\in\{2,4,6\}

Method	$\delta=4$			$\delta=6$			Avg. BA $\uparrow$	Avg. PPL $\downarrow$	Avg. Top- $\mathbf{5}$ $\uparrow$
Method	BA $\uparrow$	PPL $\downarrow$	Top- $\mathbf{5}$ $\uparrow$	BA $\uparrow$	PPL $\downarrow$	Top- $\mathbf{5}$ $\uparrow$	Avg. BA $\uparrow$	Avg. PPL $\downarrow$	Avg. Top- $\mathbf{5}$ $\uparrow$
Message length $b=32$
MPAC	$84.69$	$4.69$	$96.09$	$98.28$	$13.65$	$85.41$	$91.49$	$9.17$	$90.75$
RSBH	$83.28$	$4.17$	$98.17$	$96.41$	$6.20$	$96.81$	$89.85$	$5.19$	$97.49$
MajorMark	$89.38$	$4.09$	$98.70$	$96.41$	$6.19$	$97.12$	$92.90$	$5.14$	$97.91$
MajorMark +	$\mathbf{91.88}$	$\mathbf{3.91}$	$\mathbf{98.72}$	$\mathbf{98.44}$	$\mathbf{5.52}$	$\mathbf{97.51}$	$\mathbf{95.16}$	$\mathbf{4.72}$	$\mathbf{98.12}$

Appendix

Table 11: Performance comparison of watermarking methods on the WritingPrompts dataset for the story generation task with message lengths

b\in\{32,64\}

and watermarking biases

\delta\in\{4,6\}

Method	$\delta=4$			$\delta=6$			Avg. BA $\uparrow$	Avg. PPL $\downarrow$	Avg. Top- $\mathbf{5}$ $\uparrow$
Method	BA $\uparrow$	PPL $\downarrow$	Top- $\mathbf{5}$ $\uparrow$	BA $\uparrow$	PPL $\downarrow$	Top- $\mathbf{5}$ $\uparrow$	Avg. BA $\uparrow$	Avg. PPL $\downarrow$	Avg. Top- $\mathbf{5}$ $\uparrow$
Message length $b=32$
MPAC	$83.12$	$6.36$	$96.68$	$96.41$	$12.25$	$90.48$	$89.77$	$9.31$	$93.58$
RSBH	$85.00$	$5.81$	$98.83$	$\mathbf{97.34}$	$8.07$	$97.24$	$91.17$	$6.94$	$98.04$
MajorMark	$88.12$	$5.72$	$99.02$	$95.78$	$7.70$	$98.00$	$91.95$	$6.71$	$98.51$
MajorMark +	$\mathbf{89.53}$	$\mathbf{5.72}$	$\mathbf{99.10}$	$95.16$	$\mathbf{7.13}$	$\mathbf{98.52}$	$\mathbf{92.35}$	$\mathbf{6.43}$	$\mathbf{98.81}$

Appendix

Table 12: Performance comparison of watermarking methods on the CNN/DailyMail dataset for the text summarization task with message lengths

b\in\{32,64\}

and watermarking biases

\delta\in\{4,6\}

Metric	MajorMark +	BiMark	$W$ Statistic	$p$ -value
PPL	$4.75\pm 0.95$	$5.05\pm 1.23$	$1633.0$	$0.00108$
BA	$98.50\pm 4.41$	$96.66\pm 4.66$	$1094.0$	$0.00002$

Appendix

Table 13: Statistical significance test over

100

users on Qwen

3

8

B. We report the mean and standard deviation of each metric across users.

Method	$\boldsymbol{\delta=2}$	$\boldsymbol{\delta=4}$	$\boldsymbol{\delta=6}$
MPAC	$\;0.8376/0.33/0.29\;$	$\;0.8210/0.28/0.25\;$	$\;0.8105/0.26/0.22\;$
RSBH	$\;0.8384/0.35/0.31\;$	$\;0.8316/0.33/0.29\;$	$\;0.8234/0.30/0.26\;$
MajorMark	$\;0.8415/0.37/0.33\;$	$\;0.8305/0.33/0.28\;$	$\;0.8269/0.31/0.28\;$
MajorMark +	$\;0.8449/0.36/0.32\;$	$\;0.8381/0.34/0.29\;$	$\;0.8311/0.33/0.29\;$

Appendix

Table 14: Semantic and lexical fidelity (BERTScore

\uparrow

/ ROUGE-1

\uparrow

/ ROUGE-Lsum

\uparrow

) for different bias values

\delta

with

b=32

Method	TPR@1%FPR $\uparrow$	TPR@5%FPR $\uparrow$
MajorMark	$98.00$	$99.00$
MajorMark +	$97.00$	$100.00$

Appendix

Table 15: Detection performance under low-FPR settings with message length

b=32

Figure 7: Pareto comparison under different

(r,\delta)

combinations.

$\delta$	$h_{\lambda}/b=71.88\%$	$h_{\lambda}/b=81.25\%$
$2$	$(4.06,85.62)$	$(4.09,80.16)$
$4$	$(4.89,97.66)$	$(4.39,96.88)$
$6$	$(5.90,100.00)$	$(4.91,100.00)$
$8$	$(6.71,100.00)$	$(5.54,99.69)$

Appendix

Table 16: Impact of watermarking bias

\delta

under different message imbalance rates.

Explore similar work

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
Selective Disclosure Watermarking for Large Language Models
Jul 6, 2026Xuyang Chen, Xiang Li, Yangxinyu Xie +1Text Watermarking Privacy-Preserving Language Models
University of Pennsylvania
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

Apr 6, 2026J/K move · Enter open · S save

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

Jiahao Xu, Rui Hu, Olivera Kotevska, Zikai Zhang

University of Nevada, Reno · Oak Ridge National Laboratory

Text Watermarking LLM Watermarking Robust Watermarking

Open paper AskPDF arXiv

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.

Abstract

Explore similar work

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

Selective Disclosure Watermarking for Large Language Models

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