BiMark: Unbiased Multilayer Watermarking for Large Language Models
Authors: Xiaoyan Feng
He Zhang
Yanjun Zhang
Leo Yu Zhang
Shirui Pan
Venue: ICML 2025 poster (2025)
Keywords: Language Model Watermarking
Text Generation
Model Security
AI Security
Large Language Model
Primary area: social_aspects->security

Abstract: Recent advances in Large Language Models (LLMs) have raised urgent concerns about LLM-generated text authenticity, prompting regulatory demands for reliable identification mechanisms. 
Although watermarking offers a promising solution, existing approaches struggle to simultaneously achieve three critical requirements: text quality preservation, model-agnostic detection, and message embedding capacity, which are crucial for practical implementation.
To achieve these goals, the key challenge lies in balancing the trade-off between text quality preservation and message embedding capacity.
To address this challenge, we propose BiMark, a novel watermarking framework that achieves these requirements through three key innovations:
(1) a bit-flip unbiased reweighting mechanism enabling model-agnostic detection, (2) a multilayer architecture enhancing detectability without compromising generation quality, and (3) an information encoding approach supporting multi-bit watermarking. 
Through theoretical analysis and extensive experiments, we validate that, 
compared to state-of-the-art  multi-bit watermarking methods, BiMark achieves up to 30% higher extraction rates for short texts while maintaining text quality indicated by lower perplexity, and performs comparably to non-watermarked text on downstream tasks such as summarization and translation.

BiMark: Unbiased Multilayer Watermarking for Large Language Models
Xiaoyan Feng" 1
He Zhang 2
Yanjun Zhang
Leo Yu Zhang' Shirui Pan'
Abstract
human-created text. However, pressing security challenges (Zhang et al., 2023b; Wei et al., 2025; Gong et al., 2025; Luo et al., 2024; Zhang et al., 2025a;b; 2023a; 2024b; Pan et al., 2025) have been raised with the rapid progression of Al technologies (Zheng et al., 2024b; Zhang et al., 2024a; Zheng et al., 2024a; 2023; 2025; Guan et al., 2023), such as the misuse of LLMs (Tang et al., 2024) and synthetic data pollution (Shumailov et al., 2024). Therefore, recent legislation, such as the Al Act of the European Union (Eu- ropean Commission, 2023) and the executive order of the U.S. Department of Commerce (The White House, 2023), mandates the implementation of technical measures to mark and detect --g--eeerrteed content. Thus, it appeals to LLM watermarking (Zhang et al., 2024e; Tang et al., 2024), a promising method to address these challenges, offering a proactive approach embedding identifiable patterns in LLM-generated text (Liu et al., 2024).
Recent advances in Large Language Models (LLMs) have raised urgent concerns about LLM- generated text authenticity, prompting regulatory demands for reliable identification mechanisms. Although watermarking offers a promising solu- tion, existing approaches struggle to simultane- ously achieve three critical requirements: text quality preservation model-agnostic detection, and message embedding capacity, which are cru- cial for practical implementation. To achieve these goals, the key challenge lies in balancing the trade-off between text quality preservation and message embedding capacity. To address this challenge, we propose BiMark, a novel water- marking framework that achieves these require- ments through three key innovations: (1) a bit- flip unbiased reweighting mechanism enabling model-agnostic detection, (2) multilayer archi- tecture enhancing detectability without compro- mising generation quality, and (3) an informa- tion encoding approach supporting multi-bit wa- termarking. Through thcoretical analysis and ex- tensive experiments, we validate that, compared to state-of-the-ard multi-bit watermarking meth- ods, BiMark achieves up to 30% higher extraction rates for short texts while maintaining text quality indicated by lower perplexity, and performs com- parably to non-watermarked text on downstream tasks such as summarization and translation.
Depending on whether it is integrated with the language model, watermarking can be categorized into inference- time watermarking and post-hoc watermarking (Tang et al., 2024). Compared to post-hoc methods that require an ad- ditional auxiliary module (Abdelnabi & Fritz, 2021; Yang et al., 2022; Yoo et al., 2023a), inference-time watermark- ing (Dathathri et al., 2024; Aaronson, 2023; Kirchenbauer et al., 2023) can embed detectable patterns linked to secret key by modifying the LLM token sampling process in a plug- and-play manner, thereby efficiently achieving a crypto- graphically guaranteed detectable secret watermark (Aaron- son, 2023; Kirchenbauer al., 2023).
In general, implementing language model watermarking necessitates three key requirements: 1) Text quality preser- vation: The integration of watermarking mechanisms must maintain the fundamental utility and performance of lan- guage models (Hu et al., 2023; Kuditipudi et al., 2023). 2) Model-agnostic detection: The watermark verification process should function independently of the generating model's architecture, parameters, access rights (Kirchen- bauer al., 2023; Kuditipudi et al., 2023). 3) Message embedding capacity: The watermarking scheme should ac- commodate sufficient capacity to encode crucial metadata such as model identity, generation timestamp, and content provenance (Bob & Dan, 2024; Pang et al., 2024).
1. Introduction
Large Language Models (LLMs) (OpenAI, 2022; Team, 2024b) have recently emerged in advancing cutting-edge technologies, and their rapid evolution has made LLM- generated content increasingly indistinguishable from
'Equal contribution Grrfffthh University, Brisbane "RMIT Uni- versity, Melbourne UUniversity of Technology Sydney, Sydney. Correspondence to: Leo Yu Zhang @leo.zhang@griffitu griffith.ccuu.uuz Shirui Pan <s. maan@griffith.com griffith.cduauu>.
Proceedings of the 4nnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
Note that it not trivial satisfy the above three require-

---

BiMark: Unbiased Multilayer Watermarking for Large Language Models
Table Comparison between BiMark (our method) and related studies.
Techniques
Requirements
Methods
Vocahulary
Text Quality
Model-Agnostic
Message Embedding
Timing
Partition
Preservation
Detection
Capacity
Yang et al. (2022), REMARK-LLM (Zhang et al., 2024c)
O
Post-Hoc
AWT (Abdelnabi & Fritz, 2021), Yoo al. (2023a)
He (2022a), CATER (He al., 2022h)
Aaronson (2023)
Kuditipudi al. (2023), Zhao et al. (2024)
Fernandez al. (2023)
Cumulative
7-reweight (Hu ot al., 2023)
Inference-
Probability
DiPmark (Wu et al., 2023)
Time
GINSEW (Zhao al., 2023)
Red List (Kirehenbauer al., 2023)
Token
SynthID (Dathathri et al., 2024)
Counting
MPAC (Yoo et al.. 2023b), Qu et al. (2024)
BiMark (Ours)
Inference-ting watermarking achieved by modifying the sampling strategy the model, such as adjusting the probubility distribution tokens, Post-hoc watermarking achieved hy editing existing text, such as synonym replacement and paraphrasing. this table, O indicates "Not Considered", ① indicates "Partially Considered", and indicates "Considered", multi-bit capacity, O indicates methods require the prior knowledge of embeuded messages, and indicutes methods can work without such knowledge.
ments, as there is trade-off between text quality preserva- tion and message embedding capacity (Yoo et al., 2023b; Qu et al., 2024; Kirchenbauer et al., 2023). Some existing works (Yoo et al.. 2023b; Qu et al., 2024) achieve efficient multi-bit watermarking by embedding one message bit per token through hashing. However, they rely on text quality- compromising zero-bit watermarking (Kirchenbauer al., 2023) as foundation, leading their enhancement of mes- sage embedding capacity inevitably come the cost of text quality preservation. Note that, although other methods (Fernandez et al., 2023; Fairoze et al., 2023; Wang et al., 2023) can mitigate this issue to some extent by associat- ing messages with secret keys or hash functions, they lack detection efficiency due to using messages non-invertibly.
2. Related Work
LLM watermarking aims to address the urgent need to dif- ferentiate gener-geeerated text from luman-written content. Text watermarking (Fang et al., 2017; Ziegler al., 2019; He et al., 2022b; Fairoze et al., 2023; Fridrich al., 2004; Christ et al., 2024; Zhao et al., 2024) has evolved signifi- cantly since its early application in content protection. Here we review related work on inference-time watermarking around the three key capacities in LLM watermarking.
Text quality preservation. Early watermarking methods such Soft Red List (Kirchenbauer et al., 2023) signifi- cantly influenced the field but faced challenges with text quality preservation due to their biased nature. Recent work has addressed this challenge through two main approaches: unbiased reweighting (Hu et al., 2023; Wu et al., 2023) and distortion free sampling (Kuditipudi et al., 2023; Zhao et al., 2024: Dathathri al., 2024). Unbiased reweighting methods, such as 7-reweight (Hu al., 2023) and DiP- mark (Wu et al., 2023), modify the probability distributions of generated text to inject watermarks while ensuring that the expected probability distribution remains unchanged. Distortion sampling methods, such as Gumbel sam- pling (Aaronson, 2023; Kuditipudi et al., 2023) and Syn- thID (Dathathri al., 2024), employ secret keys to guide the sampling process rather than modifying the probability distribution. Many of them enable model-agnostic detection, but lack multi-bit functionality.
To this end, propose an integrated pipeline called BiMark to embed and extract multi-bit messages via watermarking while preserving text quality. BiMark requires neither train- ing for embedding nor access to language models for detec- tion. This approach simultaneously achieves the three key requirements. Our three-fold contributions are as follows:
1. For filling the gap between text quality preservation through unbiased reweighting and model-agnostic de- tection, we propose a token counting based reweighting approach that enables model-agnostic detection.
2. For handling the trade-off between message embed- ding capacity and text quality preservation, present multilayer reweighting mechanism that enhances de- tectability without sacrificing text quality.
Model- -adel--ggootic detection. The ability to detect water- marks without accessing the original or an auxiliary model is crucial for practical deployment. Existing watermarking methods developed from unbiased reweighting (Hu et al., 2023; Wu al., 2023) utilize cumulative probability
3. For implementing multi-bit watermarking, we intro- duce an XOR-enhanced information encoding ap- proach that enables messages carrying and message- agnostic extraction while preserving text quality.

---

BiMark: Unbiased Multilayer Watermarking for Large Language Models
partition the vocabulary, which makes them unsuitable for model-agnostic detection. In the scenario of multi-bit water- marking, similar concept critical for practical deployment is message-agnostii detection. That is, the ability to extract messages without access to the message space. Among existing multi-bit watermarking methods, only the works of Yoo et al. (2023b) and (Qu et al., 2024) satisfy this prop- erty through extracting messages from voting matrix bit by bit. However, they are developed based on Soft Red List and thus without guaranteeing text quality.
Early works (Kirchenbauer et al., 2023; Kuditipudi et al., 2023; Hu et al., 2023) only focus on addressing the binary question of whether a text contains watermarks, referred to zero-bit watermarking. For more reliable text authenticity, watermarking methods that can carry informative messages are proposed, referred to as multi-bit watermarking (Yoo et al., 2023b; Fairoze et al., 2023; Cohen et al., 2025).
A zero-bit watermarking scheme has two key components: 1) distribution reweighting function Rşç By - Av through which the key k modifies the original probability distribution to inject signals, where Ay is the set of all possi- ble probability distributions over the vocabulary set V: and 2) a detector: D V > {True, False} which determines whether a token sequence contains the watermarks, where V denotes all possible token sequences over vocabulary V.
Message embedding capacity. Message embedding capac- ity enables information to be embedded in and extracted from watermarked text, which is essential for tracing text provenance (Cohen et al., 2025; Pang et al., 2024). Recent studies develop multi-bit watermarking for message embed- ding capacity by associating each message with unique secret key (Fernandez et al., 2023), or incorporating mes- sages into hash functions as inputs (Fairoze et al., 2023; Wang et al., 2023). These methods require access to mes- sage space for extraction, as the messages themselves are entangled with hash functions in a non-invertible manner.
A multi-bit watermarking scheme has two components: 1) distribution reweighting function Ra.m Av - Ay that works similarly to the zero-bit scheme but additionally in- corporates a message m E {0, 1). for watermarking, where is the message length. 2) a detector: D V + 1)", which is also similar to a zero-bit watermark detector but can extract embedded messages from watermarked text.
Yoo al. (2023b) proposed position allocation technique incorporating Soft Red List (Kirchenbauer et al., 2023), which can solve this problem. They allocate each token to a subunit of message for watermark embedding, and ex- tract the message bit by bit, which is in a message-agnostic way. Qu et al. (2024) further incorporates error correction codes to enhance multi-bit watermarking resilience. How- ever, these methods were designed using List-List, leading to lack of unbiasedness. As shown in the Tab. 1, com- prehensive comparison between BiMark and related studies is presented, highlighting our contributions in this field.
3.2. Soft Red List Watermarking
Soft Red List (Kirchenbauer et al., 2023) is a pioneering inference-time watermarking method, introducing the in- genious concept of green list and red list for LLM water- marking. We examine this method because its green list and red list approach inspired our bit-fip unbiased reweighting technique, which determines green lists through a coin flip.
Green-Red partition for watermarking. Soft Red List embedding watermarks by employing uniquely devised vocabulary bipartition framework guided by a pseudoran- dom function prf,- This function, initialized with secret key k. takes a sliding window of previous tokens as input and generates a binary mask for vocabulary partitioning, The
3. Preliminary
3.1. Watermarking for LLMs
Text generation of LLMs. A Large Language Model (LLM) produces text sequentially. Let V denote a vocab- ulary set of all tokens. A LLM generates a single token E V from a probability distribution PM E Ay over all possible next tokens conditioned on preceding tokens, and continue this process autoregressively. Denoting a se- quence of tokens (41,022 ... ,In) as Bimm the joint gen- eration probability of a token sequence can be written as: PM (mm+in+m (im)) IT (M
and key-dependent nature of prf, en- sures both efficiency and tamper resistance of the watermark. Given a proportion 7 the method splits vocabulary into a green list and red list using prfg such that the size of green lists is >/V). When generating text, the method constructs probability distribution PMr, to facilitate watermarking by adjusting PM - enhancing probabilities for tokens on green lists while decreasing those on red lists.
Z-test for watermark detection. Soft Red List water- marks can be detected by comparing the proportion of green tokens in the text with the expected proportion % because the watermarked LLM is influenced to generate more to- kens from green lists created by secret key. Specifically, given text segment with T tokens, let G denote the count of tokens on green lists. Since green list membership is
Watermarking LLM- text. To reliably distin- guish between J.MM-eeerrtedd and human-written text, wa- termarking methods actively inject detectable signals using secret keys (Kirchenbauer et al., 2023; Aaronson, 2023) into -egeererettedd text. During detection, through mea- suring the similarity between extracted signals and injected signals with the same keys, the watermark can be verified.

---

BiMark: Unbiased Multilayer Watermarking for Large Language Models
BiMark has three key components: 1) bit- lip unbiased reweighting Function that preserves text quality while facilitating efficient modslagnossic watermark detection, 2)
multi-loyer reweiphting mechanism that enhances watemark detectability, and 3) an XOR- enhunced position
allocation technique that
Ali previous tokens
LLM
Original probabltty distribution
Sample next token from
Previous tokens
One message Index
Multi-layer bit-flip reweighting
Reweighted probability distribution
the reweighted diatribution
F
Update the voting matrix baced on token's subsot Indox
Message
message
Pasudorandom
0001
19
lunction pr
XOR
21 5
Extract massage based on the majoniy votes
Extracted massage
One-time pad mask
Fair coin flips
4 180
text generation
Message embedding
Message extraction
Figure 1. Pipeline of BiMark. The I.Im outputs probability distribution over all tokens (grey lines). b) The message embedding process (red lines) modifies this distribution using pseudorandom function that selects message bits and generates one-time pad masks. After XOR operations create fair coin flips, multilayer unbiased reweighting guides token sampling. c) Message extraction (green lines) reconstructed the message by observing token subset memberships across multilayers and using majority voting to recover message bits.
randomly determined for each token, a not-watermarked text will have a green token proportion close to y following the law of large numbers. To statistically test for deviations, one-proportion z-test can be applied:
unbiased reweighting function for a single token generation:
Definition 3.2. (Unbiased reweighting function (Hu et al., 2023)). Given random variable and reweighting func- tion R. Av + Dv, we say that Re is an unbiased reweighting function and only if for all probability distri- butions P E Av, E. [P]]
G/
V-(1-7)/7
If the z-score surpasses predefined threshold, it suggests that the text is watermarked, since the proportion of green to- kens deviates significantly from the expected value y. When using the z-score for watermark detection, the correspond- ing p-value reflects the false positive rate (Type-I error), whereas the false negative rate (Type-II error) is influenced by the inherent entropy characteristics of the LLM (Kirchen- bauer et al., 2023; Kuditipudi et al., 2023).
To achieve n-shot undetectability, they introduced a context tracking mechanism that only generates watermarked tokens when encountering new context tokens and generates non- watermarked tokens otherwise. This mechanism prevents the reuse of previously consumed context tokens as seeds for watermarking, thereby ensuring the independence of random variables used in the reweighting function.
3.4. Multi-bit Watermarking via Position Allocation
3.3. Watermarking via Unbiased Reweighting
Many prior works (Fernandez et al., 2023; Fairoze et al., 2023; Wang et al., 2023; Yoo et al., 2023b; Qu et al.,
While Soft Red List effectively embeds detectable water- marks, it potentially degrades text quality by introducing biases in the generation process. To address this limita- tion, Hu et al. (2023) proposed unbiased watermarking, which aims to maintain the original distribution of gener- ated text while enabling watermark detectability. Assume that a service provider creates watermarks using a secret key k randomly chosen from a key space K. following a prior distribution P& (k)). A desirable watermarking property is that the probability distributions of watermarked text and non- waneeatermrrke text are identical. This can be formally defined as follows:
2024) have explored multi-bit watermarking that extends beyond zero-bit detection. Among them, Yoo et al. (2023b) proposed Multi-bit Watermarking via Position Allocation (MPAC). which enables message embedding without addi- tional latency compared to Soft Red List and allows message extraction in a message-agnostic manner. We examine this technique, as it inspired BiMark, which integrates it with XOR operations to achieve unbiased watermarking.
Message embedding. MPAC inherits the framework of Soft Red List and encodes messages into watermarks by selecting different vocabulary subsets as green lists. Assuming the message is a binary string m E {0, 1) for each token generation: A pseudorandom function prf, takes previous tokens in a sliding window 1) partition the vocabulary V into two balanced subsets' Vo and V1, 2) select one position p 21,2, ... e} which determines which message bit will be encoded. The method then designates the vocabulary subset Vmipp as the green list, and the subsequent process
Definition 3.1 (n-shot undetectable (Hu et al., 2023)). For a fixed input sequence a E V", we say that watermarked LLM and key prior pair (PM, Pk) is unddetlundeteccablee compared to original LLM Par if for any n number of strings x' E V*:
T2 PM (2 (a; k)
II PM (a'(aa))=
Σ (k( II
REK
1=1
IIn the original paper, the number of partitions can be over 2. For ease discussion, we take bipartition here.
To achieve 1-shot undetectability, Hu al. (2023) proposed

---

BiMark: Unbiased Multilayer Watermarking for Large Language Models
(C e 6,2
(1 + 4x31-
preserve text quality in watermarking, existing methods (Hu et al., 2023; Wu al. 2023) based on cumulative probability distributions require access to model probabilities, making them unsuitable for model-agnostic detection.
(Pa)
Cloudy
Raimy
Windy
Stormy
Foggy
(1 f)
PM
Sunny
Cloudy
Raimy
Windy
Stormy
Fogey
We propose a bit-flip reweighting function that relies on token counting-based bipartitions, enabling both unbiased reweighting and model-agnostic detection. The core mech- anism of which is straightforward: we use a fair coin flip to determine the direction of probability redistribution be- tween two vocabulary bipartitions Vo and V/. When the coin shows heads, we increase the probabilities of tokens in V1 while proportionally decreasing the probabilities in Vo, and vice versa for tails. This symmetric adjustment and the fairness of the coin flip ensure the expected token distribution remains unchanged while creating a detectable pattern in text generated by watermarked LLMs.
6,)C1
(P))
Sunny
Cloudy
Rainy
Windy
Stormy
Fossy
Figure 2. Bit-flip unbiased reweighting, Given a vocabulary bipar- tition Vo (shown in yellow) and V (shown in blue), a probability distribution Pa over the vocabulary V is adjusted based on a fair coin flip e. When 5 and probabilities of Vi is decreased by 6, %. When e = 1, probabilitics of Vi is increased by 51 % and probabilities of Vo is decreased by 60 This symmetric adjustment preserves original probabilities in expectation when the coin flip are fair.
O. probabilities of Vo is increased by
of increasing probabilities following as Soft Red List.
Formally, let a random variable represent fair coin flip, where e = 1 indicates heads and e = 0 indicates tails. Given a vocabulary bipartition (V,, Vi), the bit- bit-flip reweighting function Fig. 2 adjusts an original probability as follows:
Message extraction. MPAC extracts embedded messages from text using a green-list voting matrix M E RRxx2 in a message-agossicc manner. Given a text, for each token x, the method pseudorandomly reconstructs the correspond- ing vocabulary partition V1 and Vo, along with the mes- sage position p. Next, it checks the subset membership of token x: if E Vo, then [p]0 is incremented by 1: if I E V1, then [p][[]] is incremented by 1. After processing all tokens, based on the assumption that wa- termarked text contains more green tokens than red to- kens, each bit of the extracted message can be obtained as arg max [M [p]lt) for E (1,..., ,f). The sum of the ma- jority votes Ex max ( (p][t) serves as the total green to- kens for determining whether the text contains watermarks.
(1 + (x)()
if 1 V1,
(1 (0)
ife = 1 E Vo,
Re.e(PM)(s))
(1 (M))
if 0A E V1, if 0A E Vo-
(1 + (x)
(1)
Here, 6g and 8, are scaling factors for Vo and V1. respec- tively, and = (6p, 51, Vo. Vi) denotes reweighting func- tion configuration. Fig. 2 illustrates an example of the bit- flip unbiased reweighting. The scaling factors óg and d1 must maintain valid probability distribution. Subject to the constraint that the probability distribution sums to unity, valid ón can be derived by a valid o as Lemma 4.1.
4. The Proposed BiMark
Lemma 4.1 (Scaling factor constraint). Let T Exer PM((T) be the total probability of partition V1 in the distribution PM. For T < 1, the scaling factor of Vo must satisfy:
BiMark is an unbiased multi-bit watermarking framework designed to achieve text quality preservation, message em- bedding capacity, and model-agnostic and message-agnostic detection simultancously. It operates in two phases: wa- termark embedding and watermark detection. In the em- bedding phase, we introduce novel bit-flip reweighting function that preserves text quality while facilitating model- agnostic detection. To enhance watermark detectability, a multilayer reweighting mechanism is employed. For car- rying messages, we propose multi-bit watermarking via XOR-enhanced position allocation based on a one-time pad mechanism. In the detection phase, a voting matrix is con- structed based on the text for message extraction. Fig. illustrates the overall architecture of BiMark.
6 . 7/ (11 -)--
Proof. Let A be the absolute change in probability between
partitions Vo and V1. When A > 0, for the probability distribution to remain valid:
A= == 60 - -T),
It is clear to see that 60 81 7/ - -)
Due to the constraint in Eq. (2), when dn ensures valid probability distribution, ôp also satisfies the corresponding bound. Although the unbiased reweighting function is es- tablished, implementing watermarking faces a challenge of determining appropriate scaling factors do, on that maintain
4.1. Bit-Flip Unbiased Reweighting
An unbiased reweighting function is the core component of unbiased watermarking. While unbiased reweighting helps

---

BiMark: Unbiased Multilayer Watermarking for Large Language Models
valid probability distribution while achieving effective watermarking. This requires carefully handling edge cases and constraints that arise in real-world scenarios.
17.64
23,52
11:77
14.71
20.59
11.77 (%) layer
Sunny
Clouy
Rainy
Windy
Stormy
FoBBY
21.17
28.23
14.13
11.40
25.95
9.12
For practical implementation, we introduce a base scaling factor 8 E [o. 1] and derive 81 adaptively based on r from Eq. (3). However, two scenarios require special attention: (1) If r = 0, we set 61 = 0 since all tokens in V have zero probability and any non-zero 81 would have no effect on the probability distribution and will break the symmetry of our reweighting scheme when
Sunny
Cloudy
Rainy
Windy
Starmy
FoggY
28.23
9.12
15.95
11.40
14.13
21.17
layer 2
Cloudy
FogBy
Stormy
Windy
Rainy
Sunny
22.59
7.29
12.76
14.00
17.34
26,01
Cloudy
Tous
Starmy
Windy
Rainy
Sunny
1. (2) If (1 (1+5)r > 1, we set 51 = (1-T)/T which which makes the probability of V become 1 and the probability of Vo become 0. ensuring the reweighted distribution remains a valid probability distribution over two partitions. Consequently, the scaling factor ò1 becomes:
14.00
7.29
12.76
26.01
17.34
22.59
layer
Windy
Foggy Stormy
Sunny
Ralny
Cloudy
16.80
15.32
23.32
15.55
20.25
Windy
TosBy
Stormy
Sunny
Rairy
Cloudy
001
011
011
100
100
110
(6=0.2)
0
if = 0,
x 12 6 1/2
6 V.
x V.
61
(1 - T/T 8
if (1 + 18 > 1,
(3)
Figure 3. Multilayer bit-slip reweighting. Given multiple bipar- titions, each reweighting layer adjusts the probability from the previous reweighting layer based on the bipartition and the fair coin flip result of this layer. In layer 1, "Sunay" belongs Vi and e = 1. making "Sunny" become green and gain probability. In layer 2. "Sunny" belongs Vo and 0, making "Sunny" become green and gain probability. In layer 3, "Sunny" belongs to V1 and 1, making "SSunyy" become red and lose probability.
otherwise.
It is easy to check this piecewise definition of 61 ensures a valid probability distribution for all possible cases.
Theorem 4.2 (Bit-Flip unbiased reweighting). For any prob- ability distribution over a vocabulary V and a reweighting function Ro. defined above, we have F.e (e. = P.
This property follows naturally from our design: we use fair coin flips to determine which partition's ' probabilities to increase or decrease, and ensure the probability changes are equal in magnitude. The symmetry of these adjustments guarantees unbiasedness while enabling watermark detec- tion through token count analysis-a key advantage over pre- vious cumulative probability- -assed approaches. The proof of Theorem 4.2 can be found in App. 1. Note that both Vo and V11 have equal probabilities of being the green list due to fair coin flips. To obtain a consistent proportion for the z- test, both sets should have equal size: [Vol = Mil = 12/2.
independent bipartitions and fair coin flips to iteratively adjust probability distributions, as shown in Fig. 3.
Formally, given a sequence of independent vocabulary bi- partitions [(V): D)) ... , (V% D) and a sequence of inde- pendent fair coin flips e = [e e² .... ee). i.e. el follows Bernouli(O.5),, the multilayer reweighting is defined as:
PM = Rog o Rgs e o o Rgy,e' (PM)),
where o denotes function composition (applied from right to left), and Rø is bit-flip reweighting function configured with the i-th bipartition, the i-th fair coin flip, and a base scaling factor ē used to obtain valid dn and valid on for unbiased reweighting as described in Section 4.1.
4.2. Multilayer Unbiased Reweighting
In Soft Red List (Kirchenbauer et al., 2023), watermark detectability can be enhanced by combining a smaller green list proportion 7 with a larger logit adjustment value 5. Since Soft Red List imposes no constraints on the unbiased prop- erty, 5 can be arbitrarily large-in in the extreme case, restrict- ing generation to only green list tokens (Kirchenbauer et al., 2023). In contrast, the bit-flip reweighting is constrained by unbiased probability adjustment-with only single layer reweighting (one bipartition), the watermark may be weak and difficult to detect due to an imbalanced probability dis- tribution. To address this limitation, we propose a multilayer reweighting mechanism that preserves the unbiased property while enhancing watermark detectability through multiple
When vocabulary bipartitions (Vo', 5 , 1/2" and fair coin flips e; are independent across layers, the multilayer reweighting is still unbiased, i.e., [e PM. A discussion and proof of this property can be found in App. A.3.
4.3. XOR-enhanced Position Allocation
Integrating with the multilayer unbiased reweighting mech- anism, we propose unbiased multi-bit watermarking method via XOR-enhanced position allocation technique, which can embed messages into text while maintaining text quality and can extract the message from the text.
For ease of presentation, we assume (1 (1+)1)73 (1+56) -7) and focus on the edge outlier caused by expanding Vı.
Message embedding. To embed a message m E {0, 1] into generated text, we pseudorandomly encode it into a

---

BiMark: Unbiased Multilayer Watermarking for Large Language Models
sequence of balanced bits as fair coin flips that guides our multilayer reweighting. This encoding process is achieved through a one-time pad with XOR operations. For single token generation, fair coin flips are constructed as follows:
{1 if Vo:
i
This estimation leverages the statistical bias introduced dur- ing generation tokens were more likely from partitions corresponding to the respective coin flip results.
1) Message bit selection: A message index E {1,... 2) is pseudorandomly selected using previous tokens in a sliding window as seed. Then, ma[p] is one bit of the message that will be embedded in the generated token.
The message bit m|p] is estimated by é' @ 6', which is a reversal of the XOR operation, and is taken as a vote of the message bit. This vote accumulated by incrementing M [p][et e b*] by 1. The multilayer design provides d inde- pendent votes per token, enhancing extraction reliability.
2) Random mask generation: A sequence of balanced bits b = [b², .1,..... ,b=] is pseudorandomly sampled from Bernoull((0.5) using previous tokens in a sliding window as a seed. These bits serve as a one-time tieetime pad mask.
3) Extracting message bits through majority voting: After all tokens are processed, the message is extracted through the majority vote bit by bit as follows:
3) Fair coin flip computation: To encode the message bit, for each layer, a fair coin flip is calculated by e¹ m [p] @ b², where @ is the XOR operation and i f1,2, dd. These fair coin flips are used in the multilayer bit-flip reweighting.
m [p] arg max M (p::)) for p E (1, ...
This process ensures two crucial properties. First, the mes- sage is recoverable because the XOR operation is reversible - -given 6' and ex for each token, the corresponding message bit m(p) can be recovered. Second, and equally impor- tant, the unbiased property is guaranteed. This is because XORing any fixed bit (in our case, mp(p)) with random bit sampled from Bernoulli(0.5) produces a result bit that also follows (00 (see App. A.4 for proof)- property that ensures fair coin flips for unbiased reweight- ing regardless of the message content. See App. C for the complete watermarked text generation algorithm.
The extraction process reliably recovers the embedded mes- sage by leveraging both the deterministic nature of the pseu- dorandom function and the statistical patterns created by our multilayer reweighting scheme. See App. C for the complete watermark detection algorithm.
In summary, BiMark achieves unbiased multi-bit water- marking through a carefully orchestrated pipeline. During generation, the multilayer unbiased reweighting mechanism applies iterative probability adjustments guided by fair coin flips where message bits are encoded, which creates de- tectable statistical patterns while preserving the original generation distribution. During detection, these patterns are verified by analyzing token distribution across bipartitions of multiple layers and aggregating evidence in a voting ma- trix, enabling message extraction. The framework maintains text quality while enabling message embedding capacity with model-agnostic and message-agnostic detection.
Note that in this encoding process, message bits and one- time pad masks are contructed pscudorandomly for each token during text generation. The vocabulary partitions used in unbiased reweighting are constructed pseudorandomly before the entire text generation process. Compared to existing methods which construct vocabulary partitions or permutation for each token (Kirchenbauer et al., 2023; Hu et al., 2023; Wu al., 2023), this approach more efficient.
5. Experimental Analyses
Message extraction. The embedded message m is ex- tracted from the watermarked text by analyzing the statisti- cal patterns created by the multilayer reweighting process. The approach is extended from the voting matrix method introduced in Section 3.4 adapting the multilayer reweight- ing and the XOR operations. Given a text segment, votes of message bits are gathered from each token x as follows:
We conduct comprehensive experiments to evaluate Bi- Mark's effectiveness across three key dimensions: mes- sage embedding capacity, text quality preservation, and an ablation study of the multilayer mechanism. For compar- isons, we focus on inference-time methods that are pub- licly available and support model-agnostic and message- agnostic detection. The code is available at: https: / //gtttbbbbb.///////// com wwt/////////////e/ BirarrM.r..... git.
1) Recovering variables used by encoding: The message index p and the one-time pad mask b- = [b', .b?..... ... 54) used in the generation phase are reconstructed pseudorandomly using the same key. Note the message mipl is unknown but can be reconstructed if the et, i 21, d) is known.
5.1. Message Embedding Capacity
Experimental setup. For experiments of message embed- ding capacity, the I.lama--BB model (AI @ Meta, 2024) is used for text generation with temperature 1.0 and top-50 sampling. C4-RealNewslike (Raffel et al., 2020) dataset is used as prompts. For pscudorandom operations of wa- termarking methods, a 2-token sliding context window is
2) Gathering voles of message büt: To reconstruct the mes- sage bit. for each layer i, the fair coin flip e' is estimated through tokens' subset membership follows:

---

BiMark: Unbiased Multilayer Watermarking for Large Language Models
1.00
3.00
Table 2. Message extraction rate.
Pagg Pigg 33%
Text Length (Tokens)
Bits
Method
50
100
20X1
3100
Rate
PPL.
Kote
PPL.
Rite
PPL.
Rate
PPL.
BiMakk
95.26
8,5
97.62
7.38
96.15
5.78
18.88
4.57
Sydtin
Systhi Scft Rud
8
MPAC (1)
49.49
9.44
79.72
8.64
89.51
8.08
93.48
7.85
Soft Redilkt
2.22
MPAC
78.81
9.76
89.75
9.13
96.4
8:63
98.57
8.39
Perplesit
BiMuk
85.55
8,60
93.31
7.35
95,54
5.83
95.54
4.71
MPAC (1)
$7.04
9.36
8.63
79.31
8.17
87,50
7.89
MPAC (1.5)
66.06
9.69
78.21
8.87
89.04
8:45
93.83
8.45
BiMark
66.35
8,63
82.69
7.48
89.68
5.89
90.22
4.75
75
125
175
225
125
175
275
32
MPAC (1)
45.06
9.16
56.79
8.34
67.96
7.92
74.32
7.67
kumber tokeres
Number of tokama
MPAC (1.5)
51.03
9.77
65.35
8.96
78.15
8.49
84.70
8,35
(3) llamaa-Bp 88
(b) Cwon2.5522 38
"Rate"(11 denotes message extraction rale which the ratio of correctly extracted bits, and "PPL" (1) denoies perplexity. "MPAC (1)" and "MPAC (1.5y" indicate that value added to green tokens' logit are and
Figure Zero-bit Watermark Detection.
respectively.
formance improvement is more evident with both shorter texts and longer messages, which typically present greater challenges in watermarking.
Table 3. 8-Bit message extraction rate from damaged text.
Length
Ratio
Method
25
50
1000
1.50
200
250
300
BiMark
70.25
82.4
91.02
93.74
94.94
95.23
95.24
MPAC
54.5
67.08
73.41
76.34
80.15
82.1
We further evaluate resilience against synonym substitution attacks (Jovanović et al., 2023; Zhang et al., 2024d; Hou et al., 2023; Ren et al., 2023) using BERT (Devlin et al., 2018) and WordNet (Miller, 1995). Tab. demonstrates Bi-
MPAC (1.5)
56.42
66.8
76.85
82.64
86.55
89,33
91.62
RiMark
60.61
71.6
81.71
86.29
88.62
89.39
90.01
MPAC
52.83
64.29
67.31
70.03
72.19
MPAC (1.5)
50.04
58.04
67.36
73.1
76.37
78.99
80.85
BiMark
53.37
62.52
70.37
74.22
76.23
77.3
78.23
MPAC
43.18
48.71
56.3
58.29
59.78
60.57
Mark's superior performance-for 100-token texts, BiMark maintains 18.44%, 21.30% and 26.24% higher extraction rates than those of MPAC under 0.1, 0.2, and 0.3 text sub- stitution ratios, respectively. This enhanced resilience is attributed to the fact that the multilayer mechanism pro- vides abundant watermark evidences, leading the statistical patterns of detection to be more distinguishable between watermarked and non -atermarred text.
MPAC (1.5)
45.59
51.16
58. 11
62.24
64.73
67.07
68.31
used for seeding. For evaluating the generation quality of language models with watermarks, perplexity of gener- ated text calculated using Gemma-9B (Team, 2024a) as an oracle model which has more parameters than Llama3- 8B. The baseline methods include MPAC (Yoo et al., 2023b), Soft Red List (Kirchenbauer et al., 2023), and Syn- thID (Dathathri et al., 2024). For MPAC and Soft Red List, the proportion y of green lists is 0.5 for a balance between detectability and text quality, and also fair comparison with BiMark's vocabulary bipartitonn setting. For SynthID, the number of tournaments is 30, as recommended in the default setting. For BiMark, the base scaling factor ó is 1.0, and the number of layers d is 10, which provides a balance between detectability and computational efficiency.
Ziro-bit watermarking scenario. performance on zero-bit watermarking by embedding 1- bit messages through our framework and compare it with two state-of-the-art model-agnostic zero-bit watermarking methods: Soft Red List (Kirchenbauer et al., 2023) and SynthID (Dathathri et al., 2024), which are biased and unbi- ased methods, respectively. True positive rate (TPR) 1% false positive rate (FPR) is used as the evaluation metric of this task. The results in Fig, 4 show that BiMark achieves significantly improved performance and comparable detec- tion performance compared to Soft Red List and SynthID, respectively, while maintaining lower perplexity on both Llama3-8B and Qwen2.5 (Team, 2024b).
We access BiMark's
Multi-bit watermarking scenario.
In this experiment, we compare BiMark with MPAC (Yoo et al., 2023b), a state-of-the--at multi-bit watermarking method that is model-agnostic and message-agnostic de- tectable. We test with varying message lengths (8, 16, and 32 bits) and text lengths (50, 100, 200, and 300 tokens), using message extraction rate, i.e. the bit accuracy between embedded messages and extracted messages, as the eval- uation metrie. As shown in Tab. 2, MPAC significantly sacrifices text quality when the value ö added to logit scores of green tokens grows from 1 to 1.5, even though it im- proves the message extraction. In contrast, BiMark consis- tently achieves higher extraction rates with lower perplexity. For 50-token texts, BiMark improves message extraction rates by 20.87%, 29.50%. and 30.02% for 8-bit, 16-bit and 32-bit messages respectively, compared to MPAC. The per-
5.2. Text Quality Preservation
Watermarks' impact on generated text quality is assessed in two downstream tasks of language models: text sum- marization and machine translation. For text summariza- tion, BaRT- (Lewis al., 2019) is employed on the CNN/DailyMail dataset (See et al., 2017), where the per- formance is evaluated using BERTScore-FI (Zhang* et al., 2020) and ROUGE-1 (Lin, 2004). For machine translation, MBart (Lewis et al., 2019) is employed on the WMT' 16 En-Ro subset (Bojar et al., 2016), where the performance is evaluated using BLEU (Papineni et al., 2002).

---

BiMark: Unbiased Multilayer Watermarking for Large Language Models
1,00
1.0
Table 4. I.M downstream tasks performance.
0.05
Text Summarization
Machine Translation
Method
BERTScore
ROUGE-1
BERTSoore
BLEU
0.90
0.6
No Watermark
32.45: o
38.321 0s
$6.21_ m
21.93g.1
0.4
0.85
Soft Red List (1.0)
m
37.97
15.74_.1
21.362.16
Soft Rod List (1.5)
31 31
37
55, 55.06-.15
20.67
0.80
Soft Red List (2.0)
36.99.10 D5
54.17
19
0.0
Gumbel Sampling
32. m m
38. m0 m
22. 14
25
Number of toleess
125
175
225
Number of toklnss
100
150
200
7- --eeeight
32.25+
38.09+.00 88
55.67=05
21.49+.14
laye
DiPmark
32
38.21
56.11
21.87:2.0
layer 2
Sppar
layrr
SymthID
32.45
38.32:.04
56.17
22.11
(a) Layer number analysis
(b) Individual layer contribution
BiMark (Ours)
32.48 m
38.32 os
56.14_.
1.015
"Soft Red Lisu indicates that the value added to green tokens' logit scores are 1. The same applies to "Soft Red 1is" and "Soft Rod List(2.0))
0.8
TPR
0.6
6.0
90.4
Baseline methods include Soft Red List, Gumbel Sam- pling (Kuditipudi et al., 2023), 7-Reweight (Hu et al., 2023), DiPmark (Wu et al., 2023), and SynthID (Dathathri et al., 2024). Soft Red List, SynthII), and BiMark use the same settings as previous experiments, while other methods take default or recommended settings in the original works. In Tab. 4, Soft Red List shows obvious quality degrada- tion, where performance drops significantly as watermark strength increases (indicated by 5). Among unbiased meth- ods, BiMark achieves comparable performance while addi- tionally supporting embedding and extracting useful mes- sages. The consistent performance across both summariza- tion and translation tasks demonstrates that our unbiased multilayer watermarking successfully preserves language models' essential abilities for downstream tasks.
0.2
50
100
150
200
30
100
150
200
tokens
2-03
2-35
3-37
5:100
6-1
6-5
d-10
6-20
(c) Scaling factor analysis
(d) Resilience analysis
Figure 5. Ablation experiments of multilayer reweighting.
with increased layers, slightly decreases after reaching a peak, but remains superior to single-layer approaches.
As shown in App. A.2, watermark detectability depends the base scaling factor 8 and probability balance be- tween bipartitions. Observation (2) occurs because multi- layer reweighting is iterative, with shallow layers having a dominant impact on the final probability distribution. Since shallow layers typically have more evenly distributed prob- abilities over tokens, their reweighting effects are more substantial and cannot be reversed by subsequent layers. Observation (1) occurs because while adding layers initially strengthens the watermark signal and improves detectability, excessive layers diminish performance since deeper lay- ers contribute minimally to detection while adding noise. Observation (3) occurs because appropriate base scaling factors enable gradual probability reweighting across layers, allowing deeper layers to contribute to detection. Obser- vation (4) occurs because multilayer reweighting creates multiple independent watermark evidence, which enhances the distinguishability between watermarked and clean text.
5.3. Ablation Study
Computational cost analysis. While multilayer reweight- ing introduces additional computational overhead during token generation, in our experiments, generating single token using BiMark with batch size of 1 and 50 takes 0.036s and 0.047s on average, respectively, showing that our BiMark is efficient in parallelized inference.
Impact of the multilayer mechanism. An ablation study is conducted across the following four scenarios:
1) Layer number analysis: Fig. 5 (a) evaluates watermark detection across varying layer numbers d 1,5, 10, 20 with fixed 8 = 1.0. Results show that detectability initially improves with increasing layers until reaching peak, then decreases as the number of layers becomes excessive. 2) In- dividual layer contribution: Fig. 5 (b) analyzes each layer's contribution to detection with 8 = 1.0 and = 10. Results show that all layers contribute to detection, with shallow lay- ers providing particularly strong signals. 3) Scaling factor analysis: Fig. 5 (c) evaluates detection performance with a base scaling factor å ranging from 0.1 to 1.0 and fixed d = 50. Performance follows the same pattern as layer anal- ysis. 4) Resilience analysis: Fig. 5 (d) assesses resilience against 10% word substitution across different layer num- bers. Results indicate that watermark resilience improves
6. Conclusion
This work presents BiMark, novel watermarking frame- work for LLMs that simultaneously achieves three critical capabilities: text quality preservation, message embedding capacity, and model- detection. These properties are essential for practical deployment and are validated through both theoretical and empirical analysis. BiMark's superior message embedding capacity stems from subtle patterns generated by multilayer mechanism, which reveals new possibilities for exploring more secure watermarking via fine-grained probability distribution reweighting.

---

BiMark: Unbiased Multilayer Watermarking for Large Language Models
Acknowledgement
2025 JEEE Symposium on Security and Privacy (SP), pp.
2583-2601, Los Alamitos, CA, USA, May 2025. IEEE Computer Society, doi: 10.1099/P61115.2222..0000 URL https: http://t....eeecoootttoooooooooe 00084.
This research was partly funded by the Australian Research Council (ARC) under grants FT210100097, DP240101547, DP250102634, and the CSIRO-National Science Founda- tion (US) AI Research Collaboration Program.
0rg/10.1109/SP6111
Dathathri, S., See, A., Ghaisas, S., Huang, P.-.., McAdam, R., Welbl, J., Bachani, V., Kaskasoli, A., Stanforth, R., Matejovicova, T., et al. Scalable watermarking for identi- fying large language model outputs. Nature, 634(8035): 818-823, 2024.
Impact Statement
This paper presents BiMark, a novel watermarking frame- work addressing critical challenges in Al-generated content authentication, contributing to responsible LLM deploy- ment. By providing a model-agnostic solution that provides message embedding and text quality preservation, BiMark supports responsible Al governance, contributing to a more transparent and trustworthy Al ecosystem.
Devlin, J., Chang, M., Lee, K., and Toutanova, K. BERT: pre-training of deep bidirectional transformers for lan- guage understanding, CoRR, abs/ 2018, URL http:/ htt///rxivv.rr abs / B1 O. 04805.
European Commission. Regulation (eu) 2024/168 of the european parliament and of the council of 13 june 2024. Technical report, European Commission, 2023.
References
Aaronson, S. Watermarking of large language models, 2023. URL httpt:ttt////.
berke 1 ey edu/tall descott-aaronee cate--uttatttt aut-austin- --s-aiiootonpaii-i-- 3-08-17.
Fairoze, J., Garg, S., Jha, S., Mahloujifar. S., Mahmoody, M., and Wang, M. Publicly detectable watermarking for language models. arXiv preprint arXiv:2310.18491 2023.
Abdelnabi, S. and Fritz, M. Adversarial watermarking trans- former: Towards tracing text provenance with data hiding. In 202/ IEFE Symposium on Security and Privacy (SP), pp. 121-140. IEEE, 2021.
Fang, T., Jaggi. M., and Argyraki, K. Generating stegano- graphic text with Istms. arXiv preprint arKiv: /705. 10742, 2017.
A Meta. Llama 3 model card. Technical report, Meta, 2024. URL httpt://////tttt /ttphhtttttttttgg// com/ com/meta http/metaallllan /1lama3/blob/ wtt.:/ainnnnaae Sariiin//ODDLLCCe
Fernandez, P., Chaffin, A., Tit, K., Chappelier, V., and Furon, T. Three bricks to consolidate watermarks for large lan- guage models. In 2023 IEEE International Workshop on Information Forensics and Security (WIFS), pp. 1 1-6. IEEE, 2023.
md.
Bob, G. and Dan, G. Digital watermarks are not ready for large language models. Lawfare, February 2024. URL https: www. www.aaawwddeeeaaco wwt//rrticll.oo......ooo... not poot-ready-- for -large- langge-lagguagemmmmell..
Fridrich, J., Goljan, M., and Soukal, D. Searching for the stego-key. In Security, Steganography, and Watermark- ing of Multimedia Contents VI, volume 5306, pp- 70-82. SPIE, 2004.
ddiigtta-watteraatt are-not
are
Bojar, O. r. Chatterjee, R., Federmann, C., Graham, Y.,
Haddow, B., Huck, M., Jimeno Yepes, A., Koehn, P., Lo-
gacheva, V., Monz, C., Negri, M., Neveol, A., Neves, M., Popel, M., Post, M., Rubino, R., Scarton, C., Specia, L., Turchi, M., Verspoor, K., and Zampieri, M. Findings of the 2016 conference on machine translation. In Proceed- ings of the First Conference on Machine Translation, pp- 131-198, Berlin, Germany, August 2016. Association for Computational Linguisties. URI. http: www. aclw eb. .t.g anthologyh/////oo/oooooa /W/W1///// /116 6 7-16-2301.
Gong, Z., Zhang, Y., Zhang, L. Y., Zhang, Z., Xiang, Y., and Pan, S. Not all edges are equally robust: Evaluating the robustness of ranking-based federated learning. arXiv preprint ar arXiv:2503.088: 08976, 2025.
Guan, T., Peng. J., and Liang. J. Spatial- graph multi-gate mixture-of-expee model for traffic prediction. 2023 IEEE 26th International Conference on Intelli- gent Transportation Systems (ITSC), pp. 36 41. IEEE, 2023.
Christ, M., Gunn, S., and Zamir, O. Undetectable water- marks for language models. In The Thirty Seventh Annual Conference on Learning Theory, pp. 1125-1139. PMLR, 2024.
He, X., Xu, Q. Lyu, L.,, Wu, F., and Wang, C. Protecting intellectual property of language generation apis with lex- ical watermark. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 107766 2022a.
Cohen, A., Hoover, A., and Schoenbach, G. Watermark- ing Language Models for Many Adaptive Users In

---

BiMark: Unbiased Multilayer Watermarking for Large Language Models
He, X., Xu, Q. Zeng, Y., Lyu, L., Wu, F., Li, J., and Jia, R. Cater: Intellectual property protection text generation apis via conditional watermarks. Advances in Neural Information Processing Systems, 15:5431-5445, 2022b.
Pan, J., Liu, Y., Zheng, X., Zheng, Y., Liew, A. W.-C,, Li, F,, and Pan, S. A label-free heterophily-guidee approach for unsupervised graph fraud detection. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 39, pp. 12443-12451, 12451, 2025.
Hou, A. B., Zhang, J., He, T., Wang, Y., Chuang, Y.-S., Wang, H., Shen, L.., Van Durme, B., Khashabi, D., and Tsvetkov, Y. Semstamp: A semantic watermark with paraphrastic robustness for text generation. arXiv preprint arXiv:2310.03991, 2023.
Pang, Q. Hu, S., Zheng, W., and Smith, V. No free lunch in LLM watermarking. Trade-offs in watermarking design choices. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024. URL ht tps: / optpreveereveeeeeeeeeee http::/eee//toorreeeeeeeee (tt.://EooounddxI11100000 bskv.
Hu, Z., Chen, L., Wu, X., Wu, Y., Zhang, H., and Huang, H. Unbiased watermark for large language models. arXiv preprint arXiv:2310.10665 2023.
Papineni, K., Roukos, S., Ward, T., and Zhu, W.-J. Bleu: a method for automatic evaluation of machine transla- tion. In Proceedings of the 40th annual meeting of the Association for Computational Linguistics, pp. 311-318, 2002.
Jovanović, N., Staab, R., and Vechev, M. Watermark steal- ing in large language models. In ICLR 2024 Workshop on Reliable and Responsible Foundation Models, 2023.
Kirchenbauer, J., Geiping, J., Wen, Y., Katz, J., Miers, I., and Goldstein, T. A watermark for large language models. In International Conference on Machine Learning, pp. 17061-17084, PMLR, 2023.
Qu, W. Yin, D., He, Z., Zou, W., Tao, T., Jia, J., and Zhang, J. Provably robust multi-bit watermarking for ai ti-generated text via error correction code. arXiv preprint arXiv:2401.1682 2024.
Krishna, K., Song, Y., Karpinska, M., Wieting, J., and lyyer, M. Paraphrasing evades detectors of ai- ai-generated text, but retrieval is effective defense. Advances in Neural Information Processing Systems, 36:27469-27500 2023.
Raffel, C., Shazeer, N., Roberts, A., Lee. K., Narang, S., Matena, M., Zhou, Y., Li, W., and Liu, J. Exploring the limits of transfer learning with unified text-to-text transformer. Journal of machine learning research, 21 (I (140))1677, 2020.
Kuditipudi, R., Thickstun, J., Hashimoto, T., and Liang, Robust distortion-free watermarks for language models. arXiv preprint arXiv:2307. 2023.
Ren, J., Xu, H., Liu, Y., Cui, Y., Wang, S., Yin, D., and Tang. J. A robust semantics- based watermark for large language model against paraphrasing. arXiv preprint MrXiv:2311.0872 2023.
Lewis, M., Liu, Y., Goyal, N., Ghazvininejad, M., Mo- hamed, A., Levy, O., Stoyanov, V., and Zettlemoyer, L. pre-training for natural language generation, translation, and comprehen- sion. CoRR, 1eN/1990.13461, 2019.
BART: denoising requence-to-sequene
See, A., Liu, P. J., and Manning, C. D. Get to the point: Summarization with pointer-generane networks. In Pro- ceedings the the 55th Annual Meeting of the Association for Computational Linguistics (Volume Long Papers), pp. 1073 1083, Vancouver, Canada, July 2017. Associa- tion for Computational Linguisties. doi: 10.18653/v 1/P1 7- 1099. URL https: http//wwwwccoommmoo www.wb..wbbb.................... org antho logy /P1 P17 1099.
Lin, C.-Y. Rouge: A package for automatic evaluation of summaries. In Text summarization branches out, pp. 74-81, 2004.
Liu, A., Pan, L., Lu, Li, J., Hu, X., Zhang, X., Wen, L., King, I., Xiong, H., and Yu, P. A survey of text watermarking in the era of large language models. ACM Computing Surveys, 57(2):1-36, 2024.
Shumailov, I,, Shumaylov, 7., Zhao, Y., Papernot, N., Ander- son, R., and Gal, Y. Ai models collapse when trained on recursively generated data. Nature, (81(2222)75557753 2024.
Luo, C., Wang, Y., Zhang, Y., and Zhang, L. Y. Distributed differentially private matrix factorization for implicit data via secure aggregation. IEEE Transactions on Computers, 2024.
Tang, R., Chuang, Y.-N., and Hu, X. The science of detect- ing I1m llmegeeertted text. Communications of the ACM, 67 (4):50-50 59, 2024.
Miller, G. A. Wordnet: lexical database for english. Com- mun. ACM, 38(1 11, November 1995.
Team, G. Gemma. Technical report, Gemma Team, 2024a. URL https:tt///// /www. kaggle e com m// m/3301.
OpenAl. Introducing ChatGPT. Technical report, OpenAl, 2022. URL https:://// openai, wwt/blog/c/aicccooooooooo chat gpt.
Team, Q. Qwen2.5: A party of foundation models, Septem- ber 2024b. URL https: / qwenlm. git 1o/b log / qwen2.5/

---

BiMark: Unbiased Multilayer Watermarking for Large Language Models
The White House. Executive order on the safe, secure, and trustworthy development and use of artificial intelligence. Technical report, The White House, USA, 2023.
Zhang T.,, Kishore*, V., Wu*, E,, Weinberger, K. Q., and
Artzi, Y. Bertscore: Evaluating text generation with bert. In International Conference on Learning Representations, 2020.
Wang. L., Yang, W., Chen, D., Zhou, H., Lin, Y., Meng, F., Zhou, J., and Sun, X. Towards codable text wa- termarking for large language models. arXiv preprint TDVV:2377.19992 2023.
Zhang, X., Zhang, Z., Zhong, Q. Zheng, X., Zhang, Y., Hu, S., and Zhang, L. Y. Masked language model based textual adversarial example detection. In Proceedings of the 2023 ACM Asia Conference on Computer and Communications Security, pp. 925- 935, 2023b.
Wei, J., Zhang, Y., Zhang, L. Y., Chen, C., Pan, S., Ong, K.-L., Zhang, J., and Xiang, Y. Extracting private training data in federated learning from clients. IEEE Transac- tions on Information Forensics and Security, 2025.
Zhang, X., Zhang, Z., Zhang, Y., Zheng, X., Zhang, L. Y., Hu, S., and Pan, S. Exploring gradient- guided masked lan- guage model to detect textual adversarial attacks. arXiv 2025b.
Wu, Y., Hu, Z., Zhang, H., and Huang, H. Dipmark: A stealthy, efficient and resilient watermark for large lan- guage models. arXiv preprint arXiv:2310.07710, 2023.
preprint arXiv:2504.08
Zhang, Z.,, Zhang, X., Zhang. Y., Zhang, L. Y., Chen, C.,, Hu, S., Gill, A., and Pan, S. Large language model watermark stealing with mixed integer programming. arXiv preprint arXiv:2405. 19677, 2024d.
Yang, X., Zhang. J., Chen, K., Zhang, W. Ma. Z., Wang, F., and Yu, N. Tracing text provenance via context-aware lex- ical substitution. In Proceedings of the AAAI Conference on Artificial Intelligence, pp. 11613-11621 2022.
Zhang, Z., Zhang, X., Zhang, Y., Zhang, L. Y., Chen, C., Hu, S., Gill, A., and Pan, S. Stealing watermarks of large language models via mixed integer programming. In 2024 Annual Computer Security Applications Conference (ACSAC), pp. 46 60. IEEE, 2024e.
Yoo, K., Ahn, W., Jang, J., and Kwak, N. Robust multi-bit natural language watermarking through invariant features. arXiv preprint wwXXiv:3005009000 2023a.
Zhao, X., Wang, Y.-X., and Li, L. Prrteccting language generation models via invisible watermarking. In Inter- national Conference on Machine Learning, pp. 42187- 42199. PMLR, 2023.
Yoo, K., Ahn, W., and Kwak, N. Advancing beyond identi- fication: Multi-bit watermark for language models. arXiv preprint TtV:2230..00211, 2023b.
Zhang, H., Wu, B., Wang, S., Yang, X., Xue, M., Pan, S., and Yuan, x. Demystifying uneven vulnerability of link stealing attacks against graph neural networks. In International Conference Machine Learning, pp- 41737-41752. PMLR, 2023a.
Zhao, X., Li, L., and Wang, Y.-X. Cermute-andffii An optimally robust and watermarkable decoder for llms. arXiv preprint mxXiv2242..08800 2024.
Zheng, X., Zhang, M., Chen, C., Molaei, S., Zhou, C., and Pan, S. Gnnevaluator: Evaluating gun performance on unseen graphs without labels. Advances in Neural Information Processing Systems, 36:33606-3366 2023.
Zhang, H., Wu, B., Yuan, X., Pan. S., Tong, H., and Pei, J. Trustworthy graph neural networks: Aspects, methods, and trends. Proceedings of the IEEE, 2024a.
Zheng, X., Song, D., Wen, Q., Du, B., and Pan, S. Online gnn evaluation under test-time graph distribution shifts. In The Twelfth International Conference on Learning Representations, 2024a.
Zhang, H., Yuan, X., and Pan, S. Unraveling privacy risks of individual fairesss in graph neural networks. In 2024 IEEE 40th International Conference on Data Engineering (ICDE), pp. 1712-1725. 1725. IEEE, 2024b.
Zheng, Y., Koh, H. Y., Yang. M., Li, L., May, L. T., Webb, G. I., Pan, S., and Church, G. Large language models in drug discovery and development: From disease mecha- nisms to clinical trials. arXiv preprint arXiv:2409. 04481, 2024b.
Zhang, H., Wu, B., Yang, X., Yuan, X., Liu, X., and Yi, X. Dynamic graph unlearning: A general and efficient post-processing method via gradient transformation. In Proceedings of the ACM on Web Conference 2025, pp. 931-944, 2025a.
Zheng, Y., Koh, H. Y., Ju, J., Nguyen, A. T., May. L. T. Webb, G. I., and Pan, S. Large language models for scien- tific discovery in molecular property prediction. Nature Machine Intelligence, pp. 1-11, 2025.
Zhang, R., Hussain, S. S., Neekhara, P., and Koushanfar, F. [REMARK-LLM) A robust and efficient watermarking framework for generative large language models. In 33rd USENIX Security Symposium ( (USENIX Security 24). pp- 1813-1830, 2024c.
Ziegler, Z. M., Deng, Y., and Rush, A. M. Neural linguistic steganography. arXiv preprint 1909iv9909.000 01 0196,, 2019.

---

BiMark: Unbiased Multilayer Watermarking for Large Language Models
A. Proof & Analyses
A.1. Proof of Theorem 4.2
Proof. For any a V. we consider Ee (R.,e((M))(()) by examining two cases:
Case 1: If E V1,
T.(Re.o(PM)(22 1 (1 (((-)))))))) 6x,))M()))
PM
Case 2: If E Vo.
1 Be (Pa)) 1 7/11 5o PM))
+ +
(*))
Re (PM)) = PM- Note that this result holds regardless of the specific value of 51 (and consequently 5o), long they maintain valid probability distribution.
Since this holds for all x E V. we have Ee
A.2. Type-II Error Analysis of Single-Layer Unbiased Reweighting
To understand the multilayer watermarking scheme, we first analyze the Type- error rate (false negative rate) of watermark detection in single-layer reweighting. While the multilayer reweighting involves complex interactions between layers, this single-layer analysis provides crucial insights into the fundamental behavior of the multilayer approach.
Statistical properties of a single-layer reweighting, Given a text sequence of length T,, let G denote the count of tokens belonging to green lists during detection. Under the null hypothesis Ho (i.e., the token sequence contains no watermark), the expected proportion of green tokens is 0.5 due to balanced vocabulary bipartitions. Under the alternative hypothesis 1/1 (i.c., the token sequence watermarked), this proportion deviates from 0.5 due to the single-layer reweighting scheme. For a single token 2, at position t, let G, be a random variable indicating whether z; belongs to the corresponding green list.
Corollary A.1. Under single-layer unbiased reweighting, the expectation and the variance of G, follow:
0.5 + Ö7, if T S 1 F.G.]
148
1.5 - if 1 < <T <,
148
(0.25 82
if S 7. S 147
Var[Gr]
-0.75 2T
- -?
if
n 1
148
where ò is the base scaling factor for unbiased reweighting.
Proof. Given a vocabulary bipartition Vo and V1. and a fair coin flip e, in a bit-flip unbiased reweighting, green tokens are defined based on two conditions: when e = 0, tokens x E Vo are green, and when e = 1, tokens x E V are green. Since the value and the vocabulary bipartition are independent, an indicator G, follows:
=
if (c OA Vo) (e IA) otherwise.
G.
(4)
Let Pt and PM denote the original and reweighted probability distribution at time step i, respectively. Note t Evev, (x),,, according to the definition of bit-flip unbiased reweighting (see Eq. (1)), we have:
(x E v1) = (1+))PM(()) ife
(1 (1-8)) ife =
(5)
(1 - PM
ife
(M, E Vo)
(1 PM (x)
if =

---

BiMark: Unbiased Multilayer Watermarking for Large Language Models
The expectation of Ge can be derived follows:
E|G,]
Σ #EV
an Vi) + P (2/ Vo)GG,
Σ P M (2/ E v1,== 1) = + P W V1, - ==)
+ (xlo E Vo,e = P) 1) + PM (2 Vo, e 0)P(e O]]
Σ (a| Vi,== P) = 1) + P M (1/2 Vo. e = P(e = 0)]
(: Eq. (4))
WEV
= 0.5
Σ ( v 1) + (x/3 E ==
(:'e ~ (er5ouli((0.5))
NEV
8t
= 0.5
Σ (1 + (1++)) PM
Vi) + (1+
(M E voll
(: Eq. (5))
1 1
NEV
= 0.5((1 + 6) + (1 + 8T.
(1 [1-)
1-Tr Tr
0.5 + 8Tt.
Given that is determined by both and Ft in Eq. (3). E(G)) can be expressed as a piecewise function:
0.5 + 87.
if0 E Ti 148
E|G.]
(6)
1.5 T₁
if 2 146
To derive Var[G.]. since G, takes values of either or 0, we have G G., and consequently E|G E[G.]. Using the variance formula and this property, we have:
Var[G,] E[G E[G,]² E[G,] (E[G,))²
This leads to the following piecewise expression:
[.25 - 2
if T. < 173'
Var[G:]
(7)
-0.75 + 2T.
T2 if 2 148'
Type-II error analysis. The Type-Il II error rate 3 is the probability of failing to detect watermark when one is present. For the z-test with significance level ot
B = P(: < 21 (H))
where 21-a is the critical value and is test statistic, since the proportion of green lists is 0.5:
-.5
(8)
00.25/T
Under H1, the total count G approximately follows a normal distribution by the Central Limit Theorem:
G~ N(T EGG,), T Var(
(9)
Using Eq. (8) and Eq. (9), the expectation and variance under H₃ can be derived, and under H1, follows:
N(((E -.5)) Var[G,])
Consequently, the Tlpe-II error rate is:
3 Φ 21-a 2(E 0.5) 0.5) VT
2 Var(Gi]

---

BiMark: Unbiased Multilayer Watermarking for Large Language Models
Key insights. The Type-II ertor rate decreases when [ increases Var[G:] decreases. When ô = 1, E|G]] reaches its maximum when r = 0.5, implying that our watermarking scheme is most effective for high-entropy text, which aligns with previous findings from (Kirchenbauer et al., 2023) and (Kuditipudi et al., 2023). Note that E[G[] reaches its maximum 1 when r = 1+3" This actually corresponds to the case when T is amplified to occupy the entire probability space. In this case, probabilities in Vo will be shrunk to O. As multilayer reweighting is iterative, this process will concentrate probabilities among few tokens. This property indicates that shallow layers of reweighting have more impact on the ultimate reweighted probability distribution. Once tokens are shrunk to near-zero probabilities in early layers, even if they are allocated to green lists deeper layers, their probabilities cannot be effectively recovered.
A.3. Multilayer Reweighting
We analyze the expectation of reweighted probability distribution layer by layer. Let Pi denote the distribution after applying layers of reweighting. For any layer i, we know from Theorem 4.2 that Ee (eg[Rsse (Prr = PM This property holds true each layer regardless of the outcomes of previous layers due the fact:
1. Vocabulary bipartitions (V, Vi) is independent of (Vo+), vi+));
2. Fair coin flip el is independent of et+1;
3. Bipartitions and fair coin flips are independent of each other.
Therefore, by analyzing from the innermost layer outward, we conclude that the entire composition maintains the unbiased property:
Ee [PM,wl = PM-
A.4. Property of XOR operaion
We first define our variables. Let z E {0, be our original bit. Let d E {0, 1} be random bit sampled from (0.3) Let = x @ b be the result of the XOR operation.
We need to prove that P(e = 1) = 1/2 and P(e = 0) 1/2, regardless of the value of æ.
when 2 0, e
If b then e
0. If 0, then Because P(b 1) P(b 0) 1/2, we have
P(c 0/r 0) 1/2 and P(e 1/2 0) 1/2.
When 1. 1 @ b. If 1, then 0. If = 0, then 1. Because P(b 1) P(b = 0) 1/2, we have
P(e = 0/z 1) = 1/2 and p(e 1|r = 1) = 1/2.
Since the statement holds true for both possible values of x, we can conclude that follows a Bernouli(005)) distribution regardless of the original value x.

---

BiMark: Unbiased Multilayer Watermarking for Large Language Models
B. More Experiments
To further assess watermark resilience, watermark detection performance against paraphrasing attacks is evaluated. These attacks are performed using DIPPER (Krishna et al., 2023), fine-tuned language model for watermark evasion with controllable lexical and order diversity parameters.
Table 5. Watermark detection against paraphrasing attacks.
Length (Token)
Method
50
100]
200
300
(20.0)
(0,20)
(20,20)
(20.0)
(0.20)
(20,20)
(20,0)
(0.20)
(20.20)
/
(20.0)
(0,20)
(20,20)
Soft Red List
68.88
15.43
35,27
13.08
92.33
32.39
69.94
27.4
98.11
56.25
90.84
49.4
99.78
71.16
96.9
66.32
SynthID
97.25
54.82
87.03
98.04
83,14
96.52
76.13
99.48
97.83
99.55
94.75
100
97.78
100
97.21
DiPmark
24.4
10.25
23.71
34.03
89 99.94
41.62
62.63
0.236
94,76
65.39
89.57
BiMark
97.87
67.4
89.17
59.94
98.42
78.37
95.71
70.9
99.81
91.62
99.2
87.28
100
98.93
100
98.35
"(20, "10,20". "(20,20"" follows notation (loxical diversity, order diversily).
C. Algorithms
Alg. summarizes the watermarked text generation process for message embedding discussed in Sec. 4.2. Alg. 2 summarizes the watermark detection process for message extraction discussed in Sec. 4.2. The overall process is visualized in Fig. 6.
Given: sequence vocabulary bipartitions pulti-layer unbiased reweighting (V) v)).. (%
multi-bit message m, example 000010
position allocation for one message
Fair coin for unbiased multilayer reweighting
Sample an index Pt from (1.2.... ... pscudorandomll
Obtain balanced bits ei ef........ ef that carry the message for unbiased reweighting. where ef: m/p.] @
Message content Indexes
PsPaPaPe..-PPe Pc...
On
3 59204023322450441124333333
Multiayeer fair coin flips
PM
Obtain a message m[p;]
posiiion
010010100001
layer
Message content bits
mi p. hmppm/pp.....
pp]...
111000100000
0000 1 0000001 noo 10000000000000000000000000000000 0000:000011000000000000000000000
Pyt
B. Random balanced as a one-time pad mask Pseudorandomly obtain multiple balanced bits bj... where bf- bf-Bernollii (1/2)
Extracting messages from text sequence of tokens xq........... Initialize g voting matrix for from 0.1.
Extracted
message
0
generated tokons x
for from to d:
12:
3
0
Multilayer random balanced bits
position
& 1f x Vi else #t
5"
0
Previous
Layer
65
010110100011
update Mfpx][[oc]] +
let loch b4 ④
M
114
10:
for p from 1:
b9
111100100010
mip] max(M[p|10)
15:
0
prf,
return
--- Message embedding via text generation
Message extraction
Figure 6. The complete process of BiMark. The right part shows original LLM text generation. The watermark embedding process begins when the LLM outputs an original probability distribution Pas- Step A pscudorandomly selects message hit m ip). Step B samples one-time pad mask. Step C aapppiiss XOR operations between b
independent balanced bits b = [6' 12 .... 6t from Bernoulli(O.5) and m[p] to obtain fair coin flips e = ee,,ee,... ,e",, then conducts multilayer unbiased reweighting. The next token is sampled from the reweighted distribution, and the process continues iteratively. Step D processes token sequences extract messages. For each token, the message index p and one-time pad mask are pseudorandomly reconstructed. Based on token subset membership. estimations of fair coin flips è are obtained. Using by + é votes for message bits are collected. The final message is extracted via majority voting.

---

BiMark: Unbiased Multilayer Watermarking for Large Language Models
Algorithm 1 Embedding multi-bit message
Algorithm 2 Extracting multi-bit message from text
Input: a language model LM
Input: sequence of balanced vocabulary bipartitions
a sequence of tokens as a prompt
[VV. Vf), (V Vi)..., (V VD]
a sequence of balanced vocabulary bipartitions
message length é, window size h pseudorandom functions prfp- prfp
(0% V2), (V%, VP, .... (V%, V
a message m E {0, 1]" window size h
1. Initialize 2 voting matrix M
a base scaling factor 5 bit-flip unbiased reweighting function R
for 1, do
pseudorandom functions prfp- prf,
2. If the current previous tokens a-h: in a sliding window h have been used as a seed, then skip the current token and continue; else record current previous tokens h: and apply it to prf, and prf, to get seedp and seed,,
for f. = 1,2, do
1. Apply LM to all prior tokens to get probability distribution PM over the vocabulary.
2. If the current previous tokens æ-k: in the sliding window have been used as seed, then sample a next token 2; from PM": 4
Sample an index p E (1, ... ,{) using seed,. Sample b² ,,6, bd Bern(0.5) using seed,
else record the current previous tokens x w- and apply prfp p and prf, to it get seed, and seeds-
for i 1,2, ...d. d do
4. éj if Fa E V/8
else é = 0.
3. Sample an index Pt E (1, .... .) using seed,. Sample b,, by. ... , ~ (0.5(..5) using seed,,
5.
loct = bj $ &..
6. update M [pc] += 1.
end for end for
for = 1,2, ................................ d do
4. Let 0; = (Vi. V 8). and calculate
for p from to do
ef = m b4.
7. m max (M [p] [p][t)
end for
5. Obtain the i-layer reweighted distribution
8. Return the extracted message m
PM Ro 1)
end for
6. Sample the next token Ie from PM. P...
end for

---

BiMark: Unbiased Multilayer Watermarking for Large Language Models
D. Examples of Watermarked Text
Text
Detection
food processor opens up world possibilities such hot soups jy cold concoctions. It may he a hit bulky, but processons can he used to make now desserts,
banina ice cream and pie crusts. For more savory options, processors are great for
Prompt
N/A
quickly ricing shredding vogetables. Get your own loss than $30 Amazon. 2. Wooden spoons are going to he your new hest friends. Metal tools scratch many pots und pans. but wood won't cause them any harm.
Try making hunana ice cream with only an immersion blender instead traditional ice cream maker and food processor. It's fast and no-mess way make lusty treat, Try this Cinnamon & Honey Banana Nice Cream Recipe: 3 ripe frozen bananas thop. cinnamen cup almond
immersion mixer until smooth. Blend in large food processor blender with with honey. sliced almonds, your lavorise toppings and enjoy! 3. A good blender will work wonders for smoothics and soup parees and won't cause you to break your wallet. If you are ingrodient combo junkie, ecunomical option thun processor. You can blend logether
blender may he variety of foods in your blender to make mw vegan desserts like cashew or macadamia nut based creams. If you think you can forego ice cream, think again! You make loe cream alsernatives that are healthy for your waistline but still taste great. Try this recipe forn Raw Cocomut Ice Cream: 4 thep almond milk 14 thop vanilla extract cup unsweetened shredded cocomnt Blend in your food processor and pour over chopped bananas a plate. Freeze for 15-20 minutes. Enjoy! 5, Spagheti squash must have for any raw vegan. Not only is spaghetti squash delicious, but they can be very filling can caten
7-score: 0.9758
No Watermark
p-value: 0.1645
require no pasta machine. Spaghetti squash are also very versatile variety of ways. A dehydratoo is another great raw food tool. Try making raw vegan jorky, dchydrating fruit and veggies to make crispy chips or making desserts like cookies brownies. 7. You can make your own veggie chips. You can even make your veggie chips. They aren't I bad, stop buying them! Use your dehydrator and some non-stick parchment sheets to make your own at home in three simple steps. Thinly slice vegetables (thinness depends on crispiness), dehydrate for 12 hours and enjoy! 9. You add a little spice any recipe with small containing chili fakees. They come in handy for many dishes. From savory salads made with treshingredients to simple avocado toast, they make any dish little more interesting, Another great way to add some flavor to your cuisine through the use of spices. Spices can be fun and easy way to boost flaver. A good salt-free blend
N/A
They 'e also much easier to cleun: Just wash it with soup and water, and leave out in the open sir to dry. You should also invest
silicone spoon. They'r great scraping bowls, stirring sauces or blending sauces into a puree. 3. Use mesh steve struin your sauce or pasta water. You don't need to buy one- simply purchase vogetable steamer cheesecloth from your local supernarket. strainer, and pour the sauce thnough it Alternatvelyy, try tying up the steamer or cloth around a wooden spoon and straining that way. 4. you's working with a tiny kitchen and limited counter space, consider investing collapsible silicone spatula. Like all high quality tools, it's heat resistant and dishwasher safe. Silicone spatulas are great for stirring and mixing. because the soft rubber won't 't scratch any cookware. They also have flat edges, which make them perfect for scraping those last bits of batter bowls, S. Don't buy trngs or fork for flipping food. A spatula makes the whole
need
the steamer cloth in heat-safe
z-score: 17,5733
p-value: 1.97E-69
extraction message:
"11110101 10000000110000000110000000001101 10001111
business much eusier. Spatulas are incredibly udapiable- they wark on ailed and
voting matris M=
BiMark
greased surfaces, and they're ideal for tossing or turning the salad. The handle flat. which means the spatula is safe to put on chopping board. Unlike fork or slotted
[124, 961. [65, 79]. [44, 841,130, 58).
[73, (78, [79, 113).
spoon, the spatula is gentle on frugile fish and doesn't I disturh the delicate bits salad less
[33, 78). [24, 56). [30, 74). [57, 39).
you can buy bamboo cutting board. Be board made of untreated bamboo, and purchase one with groove running down the center for easy food disposal. Since the hamboo's naturally water resistant, there's no need soak the board water bleach: you can just wash with hot water and seap. Be careful, though: Weoden cutting boards can crack if they too hot, so keep it off the stove. 7. Don't 't throw out your coffee grinder. It's an ideal gadget for transforming spices into powdery blends. Keep eye on the grind: If gets too line, the grinder may release static clectricity, which will make it hard for spices exit the chamber. they keep petting stuck, mix the spice around with spoon, For even more flavor, try placing grinder an electric heater, If you're 'e using whole spices, directly. This will help open up
leaves,
select
198, 46.. 165. 391, [49, 15,,
[48, 87), (1), [44. [2].[67. 109].
[30, 42], [13, 3]. [63, 17). [38, 34).
[36, 681. 1126, 1621. 190, 381,
[81. 39), [46, 90). [15, 491, [32,
message extraction rale:
heat up

---

BiMark: Unbiased Multilayer Watermarking for Large Language Models
Text
Derection
Hefore SAP Labs designed its new digs Palo Alto, company exccutives asked eriployees how make it welcoming place to woek. After all, that's where they spend most of their day. The unswer? Windows. Lots of windows letting in lots of light. The German based business software company complied even going far
Prompt
N/A
executives away from windows give workers access to daylight. As the country embeaces "green" building design be it in the workplace or home daylight has become premium.
"Light has so many things to contribute to our smiiftctiin and productivity levels." said Mark de la Vergne, president realize that." Daylight not only prometes healthier lives and work environments, but can be an oconomic incentive for businesses honcowaers
International Commission Illumination, "We're just coming to
a for the real cstate market. boost productivity. stimulate better decision making and reduce energy and operating costs- all reasons green buildders encoumgiing more natural light than past years. "Daylight is commoditt that we' ve neglected for so long as Americans." said David Johnston, president of Pacific Green Building and an expert designing green buildings. "I think see real awakening." " Green design is trend that has swept over the Western U.S. in the last decade. As more people
starting to
efficient, earth-friendly homes, they demand natural light. especially for indoor acrivities. "The value of natural light is huge." said Tim Eddy, senior principal for archiitccture and design company ZGF, "With the amount of time we spead indoors, it's the way for all of us to remain healthfully connected to natural cycle"" People naturally respond to direct sunlight, It's boen part of our environment forever. affocts us from the inside out the way we foel. how well sleep. how much energy have, and how we think. "There nir, and you can just get a spark from it." Eddy said, Natural light is human response to nature. de la Vergne said. It's also ecosooicc response green huilding has taken its place alongside the more pructical - and often more costly- considerations huilding design and concrnatioon It's considered "must" item for office buildings and residentia builders throughout the country. The U.S. Green Building Council, which estublished rating standard for green huikding, now provdes certificarion for rens thousands of buikdings - residkntiall and commercial - accoss the country. There aren't statisties on how many homes have "natural light" their wish list. But "green" homes incressingly popular. The Lendership in Energy and Enviroumental Design cortification program popular for homes, particularly the West, requirement for green buildings owned by the federal governientt - cortifies residential buildings based on criteria such as energy elliciency watcrr efficiency. location. material selection and sustainable design. "Any homebuyer who plans to stay in home longer than five years is better
0ss00r:0.98999
No Watermerk
p-talac:.1611
energy in the
NIA
growing building trend. In the last decade,
federal government raised standards for indoor lighting, calling for buildings to let more natural light through windows. That goal dovetnils nicely with energy efficiency goals set recent years. "Daylight free, and time when energy super expensive, emissions," said Michael Howard, the new directer of lighting research at the Pacific Northwest National Laboratory in Richland. Howard the new research, including the first-ever test bed to be constructed to measure natural light, could lead to big energy savings in the future. in commercial buildings nasoowwde
new energy and environmental requirements summer, it
can save money and reduce car
2-900rc:00.7
Lighting represencs the largest share of electricity more than the air conditioners and furnaces in buildings combined. And lightng accounts for 27 percent the power consumed by homes. The energy and environmental requirements being considered by Congress would lend to hig improvements in energy efficiency nationwide. At the same at the imgact of natural light on worker productivity and joh sutisfaction. This all has become important the age of energy efficiency. "Gireen huilding "Groen building is the buzz now." How much sunlight do we need? One of the questions the research, including the test bed constructed next year, what the right amount of light to set the stage for productive work environment. Howard says most fodkral buildings aim
p-value: 188e
extracted message:
"101000001 1001 1010001 100000010100"
coalition olexperts the Pacific Nothwest National Laboratory looking
voting matris M-
buzz now," Howard said,
I126, 78), [23, 171, 123, 57J, 1105, 55),
BiMark
[63, 41J, [108, 68). [115, 53), [134, 74).
152, 1081, [18, 541, 1117, 43J, 153, 19).
for lighting would equal the equivalent full moon. But lighting that would equal the equivalent of full moon is actually too much light. In fact, he says it could cause problens with
[35, 931, [51, 851, [31, [57, 871.
184, 521, [67, 211, [58, 46). 124, 56).
worker productivity. "Some studies showing that you need less light. about two to three times less, to he more producrive," he suid. The new test bed to be conseracted next year is 25. 25.000-square foot office building at Richland's Hanford site. It will study everything from window placements to the impact of natural light on worker prochctivity. The for ways hetter design natural light to maximize worker productivity.
[53. 911, [67, 531, [67, 1116, 60L.
[62, 34), (77.6, 66.4). (S7. 15), [25, 47).
[65, 31J, [62, 146), [137, 63). 192, 44]]
state-
message extraction rate: 1.0
new test bed will
"We think that it'll be very helpful in understunding if we're really getting the benefits." he said. The new test hed he constructed next year a state-of-theart 25,00 1000--quare-foon office bailding
Richland's Hanford site. It will study everything from window placements to the impact of natural light on worker productivity. The new test bed will look for ways better design natural light to maximize worker


Reviews:
[{"review_id": "FI8YmLqDCq", "reviewer": "Reviewer_FxLk", "summary": "This paper introduces BiMark, a comprehensive framework for watermarking large language models that achieves three critical objectives: text quality preservation, model-agnostic detection, and message embedding capacity. The core innovation is a novel probability distribution reweighting method with a multilayer architecture. The approach iteratively adjusts probability distributions across random vocabulary partitions using pseudorandom bits, keeping the modified probability consistent with the original probability in expectation to maintain text quality. The authors further develop methods for encoding and extracting messages within these patterns. Through theoretical analysis and experiments, the paper demonstrates BiMark’s ability to embed multi-bit information without degrading text quality, along with enhanced robustness to existing methods.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1**: Computational cost of multi-layer reweighting\n\n**R1**: Please refer to our response to Reviewer jksy in *R1*.\n\n**Q2**: Robustness experiments\n\n**R2**: We conducted advanced paraphrasing attacks to our watermarked text. \nThe detectability of BiMark under paraphrasing shows desirable robustness.\nAnalysis reveals multi-layer watermarking provides fine-grained watermark evidence to keep the green ratio of watermarked text steadily deviating from 1/2 after paraphrasing. \nFor more details, please refer to our response to Reviewer kPVR in *R3*.\n\n**Q3**: Terminology consistency\n\n**R3**: Thank you for pointing out the inconsistencies in our terminology. We will correct these issues and thoroughly revise the paper to avoid other potential issues.\n\n**Q4**: Scaling factor selection\n\n**R4**: For selecting scaling factors, we recommend adjusting based on the application scenario: \n- For better text quality: use smaller scaling factors with more layers.\n- For computational efficiency: use larger scaling factors with fewer layers.\n\nThe underline insight behind these selection lies in entropy reduction effect of multi-layer reweighting. For details, please refer to our response to Reviewer jksy in *R2*.", "claims_and_evidence": "The claims made in the submission are well-supported by convincing evidence through both theoretical analysis and experimental results. Lemma 4.1, Theorem 4.2, and Appendices A.1 and A.2 provide theoretical guarantees for the unbiasedness of reweighting and the detectability of the watermark. Sections 4.3 and 4.4 describe the information embedding methods, and Figure 6 and Algorithm 1-2 in Appendix C detail the complete algorithmic process.  The experiments in Section 5 demonstrate the method's ability to carry multi-bit information and the impact of watermarks on text quality, and include ablation experiments to show the impact of multi-layer mechanisms on the detectability and robustness of watermarks.", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria are appropriate for the watermarking problem addressed. The experiments comprehensively evaluate key aspects: message embedding capacity, text quality preservation, and watermark detectability.", "theoretical_claims": "The theoretical is convincing.", "experimental_designs_or_analyses": "The paper’s experimental design is sound, though the attack scenarios in robustness experiments could be more diverse.", "relation_to_broader_scientific_literature": "The paper properly situates its contributions within the existing literature:\n\n1.\t [1] introduced using pseudorandom number generators with previous tokens as seeds for vocabulary bipartition during inference, adjusting token probabilities to inject watermarks, with detection via z-test of green token proportions.\n\n2.\t [2] introduced unbiased probability distribution reweighting for preserving text quality, using cumulative probability thresholds for vocabulary partitioning, but requiring model access for detection.\n\n3.\t [3] extended [2] with more refined probability reweighting but didn’t address message embedding.\n\n4.\t [4] extended [1] to enable message embedding through encoding vocabulary partition.\n\nBiMark naturally combines the red-green list partitioning from [1] with a novel unbiased reweighting method with a multilayer mechanism to achieve message-carrying, model-agnostic detection while preserving text quality.\n\n[1] Kirchenbauer, John, et al. \"A watermark for large language models.\" International Conference on Machine Learning. PMLR, 2023.\n\n[2] Hu, Zhengmian, et al. \"Unbiased Watermark for Large Language Models.\" The Twelfth International Conference on Learning Representations.\n\n[3] Wu, Yihan, et al. \"A Resilient and Accessible Distribution-Preserving Watermark for Large Language Models.\" International Conference on Machine Learning. PMLR, 2024.\n\n[4] Yoo, KiYoon, Wonhyuk Ahn, and Nojun Kwak. \"Advancing Beyond Identification: Multi-bit Watermark for Large Language Models.\" Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers). 2024.", "essential_references_not_discussed": "None.", "other_strengths_and_weaknesses": "**Strengths**:\n\n1.\t   Introduces a novel vocabulary-based unbiased reweighting method using a coin-flip-like random variable to control probability redistribution direction, maintaining expected probabilities while creating detectable watermark patterns.\n\n2.\t   Proposes an innovative multilayer mechanism where multiple independent vocabulary partitions and unbiased reweighting allow each token to be influenced by multiple green lists, providing more observable evidence for watermark detection.\n\n3.\t   Creatively employs one-time-pad cryptography to encode messages into the watermarking control sequence, maintaining the unbiased property while carrying hidden information.\n\n4.\t    Provides both theoretical and experimental analysis of the unbiasedness and the detectability of the watermark.\n\n**Weaknesses**:\n\n1.\t    Limited discussion of computational resources required for the multilayer unbiased reweighting method, particularly as layers increase.\n\n2.\t    Robustness experiments lack sufficient diversity of attack scenarios.", "other_comments_or_suggestions": "The paper contains several typographical inconsistencies:\n\n1) In Figure 3, the authors use the term “level” in the diagram but use “layer” throughout the rest of the paper. \n\n2) In Figure 4 legends, the method name “KGW” appears, but “Soft Red List” is used in the paper.", "questions_for_authors": "1.\tWhat is the computational impact of the multilayer architecture, particularly as the number of layers increases? \n2.\tHow should scaling factors for unbiased reweighting be selected, and what factors does this selection depend on?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "UGbvY43ZgP", "reviewer": "Reviewer_kPVR", "summary": "In this paper, the authors introduces BiMark, a watermarking framework for LLMs designed to address the challenges of text quality preservation and model-agnostic detection. BiMark utilizes a bit-flip unbiased reweighting mechanism, a multi-layer architecture, and an advanced information encoding strategy to embed watermarks without degrading text quality. Through theoretical and experimental validation, BiMark maintains comparable performance on downstream tasks such as summarization and translation.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1**:*Perplexity*\n\n**R1**:\nWe reported perplexity in our experiments because it is one of the most commonly used metrics for evaluating the quality of generated text. We will revise the relevant statement in the final paper.\n\n**Q2**:*Challenge of unbiased watermark and model-agnostic detection* \n\n**R2**: \nWe agree with you that prior work such as DipMark and SynthID has addressed the model-agnostic requirement. However, our work uniquely aims to integrate three critical properties—text quality preservation, model-agnostic detection, and message embedding capacity—into a single cohesive framework, a task that remains challenging in the current research landscape. We will revise our statement accordingly to prevent confusion.\n\n\n**Q3**:*Baseline methods and evaluation criteria*\n\n**R3**:\nAdditional comparative evaluations with \\[1\\] are conducted, as presented in the following table. Note that \\[2\\] is not suitable as a baseline due to its significant inefficiency. Previous studies have confirmed its high computational cost—for example, embedding a 32-bit message requires approximately 29,000 seconds \\[1\\].\n\nThe table below reports the bit match rates of multi-bit watermark detection experiments on 8-bit, 16-bit and 32-bit message embedding and extraction, where Length indicates the number of tokens in the watermarked text being detected.\n|Length|50|50|50|100|100|100|200|200|200|300|300|300|\n|-------------------------|:-----:|:------:|:------:|:-----:|:------:|:------:|:-----:|:------:|:------:|:-----:|:------:|:------:|\n|Method|8-bit|16-bit|32-bit|8-bit|16-bit|32-bit|8-bit|16-bit|32-bit|8-bit|16-bit|32-bit|\n|MPAC\\[3\\]|78.81|66.06|51.03|89.75|78.21|65.35|96.4|89.04|78.15|98.57|93.83|84.7|\n|BCH\\[1\\]|96.54|71.94|49.08|98.74|84.4|64.67|99.16|95.25|85.46|100|96.21|90.46|\n|BiMark|95.26|85.55|66.35|97.62|93.31|82.69|98.15|95.54|89.68|97.88|95.86|90.22|\n\nCompared with \\[1\\], BiMark is an unbiased watermarking method, and the Error Correction Code component of \\[1\\] has the potential to integrate with BiMark to further improve multi-bit watermark performance. \n\nAdditional comparative evaluations with DiPmark \\[4\\] are conducted.\nWe exclude comparison with Gamma-Reweight \\[5\\] as it is not model-agnostic detectable, thus beyond the scope of the application scenario of our study. \nAdditional evaluations on robustness are conducted through the advanced paraphraser model Dipper \\[6\\].\nThe table below reports TPR@1%FPR of watermark detection on watermarked text with and without paraphrasing, where (20,0) indicates parameters lex_diversity and order_diversity of Dipper are 20 and 0.\n|Length|50|50|50|50|100|100|100|100|200|200|200|200|300|300|300|300|\n|---------------------------------------------|:---------:|:-------:|:-------:|:--------:|:---------:|:-------:|:-------:|:--------:|:---------:|:-------:|:-------:|:--------:|:---------:|:-------:|:-------:|:--------:|\n|Method|-|(20,0)|(0,20)|(20,20)|-|(20,0)|(0,20)|(20,20)|-|(20,0)|(0,20)|(20,20)|- |(20,0)|(0,20)|(20,20)|\n|Soft-Red-List\\[7\\]|68.88|15.43|35.27|13.08|92.53|32.39|69.94|27.4|98.11|56.25|90.84|49.4|99.78|71.16|96.9|66.52|\n|SynthID\\[8\\]|97.25|54.82|87.03|50|98.04|83.14|96.52|76.13|99.48|97.83|99.55|94.75|100|97.78|100|97.21|\n|DiPmark\\[4\\]|59.57|10.86|24.4|10.25|76.07|23.71|34.03|15.56|89.94|41.62|62.63|0.236|94.76|65.39|89.57|42.81|\n|BiMark|97.87|67.4|89.17|59.94|98.42|78.37|95.71|70.9|99.81|91.62|99.2|87.28|100|98.93|100|98.35|\n\n\\[1\\] Provably Robust Multibit Watermarking for AI-generated Text via Error Correction Code.\n\n\\[2\\] Three bricks to consolidate watermarks for large language models. \n\n\\[3\\] Advancing Beyond Identification: Multi-bit Watermark for Large Language Models.\n\n\\[4\\] A Resilient and Accessible Distribution-Preserving Watermark for Large Language Models.\n\n\\[5\\] Unbiased Watermark for Large Language Models.\n\n\\[6\\] Paraphrasing evades detectors of ai-generated text, but retrieval is an effective defence.\n\n\\[7\\] A Watermark for Large Language Models.\n\n\\[8\\] Scalable watermarking for identifying large language model outputs.\n\n**Q4**: Robustness analysis and evaluation\n\n**R4**: A primary robustness evaluation has been provided in Section 5.1 Table 3 in our paper. **Additional evaluations are conducted to test BiMark's resilience against paraphrasing attacks, as outlined in R3**. \n\n\n**Q5**:Comparison with DiPmark and Gamma-Reweight\n\n**R5**: \n\n|Feature / Method| DiPmark | Gamma-Reweight | BiMark |\n|------------------------------------------------------------------------------|---------|----------------|--------|\nMulti-layer mechanism for enhanced detectability and robustness|X|X|✔️|\n|Supports embedding/extracting multi-bit messages|X| X|✔️|\n|Model-agnostic detectability|✔️|X|✔️|", "claims_and_evidence": "In abstract, the authors claimed that \"through theoretical analysis and extensive experiments, we validate that, compared to state-of-the-art methods, BiMark reducing perplexity by up to 11%.\" However, the unbiased property only ensures that the distribution of watermarked LMs is equal to the original LM distribution. Reducing the PPL should not be expected in an unbiased watermark. Thus, this experimental observation contradicted with the unbiased property introduced in this paper.\n\nIn introduction, the authors claimed that \"adapting existing unbiased reweighting methods for reliable model-agnostic detection is challenging.\" However, this challenge has been addressed by the prior work e.g. dipmark and SynthID-Text [1]. Thus, the model-agnostic detection is generally not a challenge in LLM watermarking research.\n\n[1] Scalable watermarking for identifying large language model outputs. Nature, 2024.", "methods_and_evaluation_criteria": "This work missing several important baseline watermarking methods. In multi-bit watermark detection experiments,  Qu et al., 2024 [1] and Fernandez et al., 2023 [2] should be included as baseline. In zero-bit distortion free watermark detection experiments, unbiased watermark and dipmark should also be included.\n\nBesides, the robustness of the proposed watermark is not measured in the experiments.\n\n[1] Provably Robust Multibit Watermarking for AI-generated Text via Error Correction Code.\n\n[2] Three bricks to consolidate watermarks for large language models.", "theoretical_claims": "The theoretical claims look correct to me", "experimental_designs_or_analyses": "In prior work, the watermark algorithms are usually evaluated from three perspective: detectability, quality, and robustness. This paper only consider the detectability and the quality, a comprehensive evaluation of the robustness of the proposed method is missing.", "relation_to_broader_scientific_literature": "The reweight algorithm proposed in this paper is similar to the gamma-reweight and the dipmark. The authors should compare their method with the prior work and discuss why the proposed method is better than the prior work.", "essential_references_not_discussed": "Gamma-reweight and dipmark are cited in the work, but the authors fail to discuss those two methods, given the similarity between the bit-flip reweight and the prior work.", "other_strengths_and_weaknesses": "See above comments", "other_comments_or_suggestions": "No", "questions_for_authors": "No", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "JifTJs6gYY", "reviewer": "Reviewer_oDDU", "summary": "The paper presents BiMark, a watermarking technique for large language models (LLMs) that ensures text quality preservation, model-agnostic detection, and message embedding capacity—three key properties often challenging to balance in existing watermarking methods. BiMark introduces a bit-flip unbiased reweighting mechanism that enables detection without model access, a multilayer reweighting approach to enhance detectability, and an information encoding scheme supporting multi-bit watermarks. Through theoretical analysis and empirical validation, BiMark achieves higher extraction rates for short texts while maintaining low perplexity and comparable performance to non-watermarked text in downstream tasks. The framework provides a robust, practical, and efficient watermarking solution for AI-generated content detection.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1**: Sophisticated adversarial attacks\n\n**R1**: We conducted advanced paraphrasing attacks and reported experimental results in our response to Reviewer kPVR in *R3*. \n\n**Q2**: Inference-time benchmarks\n\n**R2**: We analyzed the computational cost and give experimental time cost of BiMark. Please refer to our response to Reviewer jksy in *R1*.\n\n**Q3**: Non-monotonic performance as the number of layers increases\n\n**R3**: The non-monotonic relationship between layer count and detection performance can be explained through our analytical framework:\n\n- Initial enhancement: Adding layers initially strengthens detection by creating more statistical patterns across independent vocabulary partitions.\n- Entropy reduction effect: As shown in our theoretical analysis (*R2* of Our response to Reviewer jksy), each layer of unbiased reweighting reduces the expected entropy of the probability distribution.\n- Diminishing benefits mechanism: When too many layers are applied, the probability distribution becomes increasingly concentrated, causing later layers to operate on highly skewed distributions. This creates a situation where green lists in later layers may have extremely low probability, making generated tokens unlikely to fall into these green lists and adding noise to the detection process.\n\nWe observed this phenomenon more prominently with larger scaling factors, as they cause more dramatic probability redistribution at each layer, accelerating both the initial enhancement and subsequent diminishing benefits.\n\n**Q4**: Meaning of symbols\n\n**R4**: $M$ stores absolute counts for detection.\nDuring detecting watermark, a ratio of green counts is calculated based on the absolute counts in $M$. \nThough there is noise caused by randomness of text generation, for certain length of watermarked text, the green ratio of watermarked text will significantly exceed 1/2 and that of non-watermarked text will be around 1/2.", "claims_and_evidence": "BiMark is evaluated for text quality preservation, model-agnostic detection, multi-bit embedding, and robustness against text modifications. Empirical results indicate that unbiased reweighting minimizes impact on text fluency and perplexity, with watermark detection verified on Llama3-8B and Qwen2.5-3B. Message embedding is tested through extraction rate comparisons (Table 2), showing up to 30% higher recovery for short texts. Robustness is assessed using synonym substitution experiments (Table 3), though further evaluation against paraphrasing and other adversarial attacks could enhance understanding of the method’s resilience. These results contribute to evaluating BiMark’s effectiveness across different aspects of LLM watermarking.", "methods_and_evaluation_criteria": "(1) Effectiveness and Robustness: BiMark is evaluated on multiple models (Llama3-8B, Qwen2.5-3B) and NLP tasks (summarization, translation). Text quality preservation and model-agnostic detection are assessed using perplexity and performance metrics, while message embedding capacity is examined through extraction rate comparisons. \n\n(2) Practicality and Efficiency: The selected datasets align with watermarking evaluation needs. The paper does not explicitly analyze the computational efficiency of multilayer reweighting or discuss detailed strategies for large-scale deployment, which could provide further clarity on real-world applicability.", "theoretical_claims": "The proof for unbiased reweighting (Theorem 4.2) demonstrates that probability distributions remain unchanged, ensuring unbiasedness across multiple layers through statistical independence. The reasoning follows standard probability principles, with no major errors identified. The type-II error analysis applies the Central Limit Theorem and z-tests, though additional empirical validation under different entropy conditions could improve reliability.", "experimental_designs_or_analyses": "The paper evaluates message embedding capacity by comparing BiMark’s extraction rates with state-of-the-art methods (MPAC). Results (Table 2) indicate higher extraction rates and lower perplexity. Robustness is tested using synonym substitution, but further evaluation against paraphrasing or adversarial rewriting is needed. Text quality preservation is assessed with summarization and translation tasks (CNN/DailyMail, WMT’16), using BERTScore, ROUGE, and BLEU (Table 4).", "relation_to_broader_scientific_literature": "BiMark builds on prior LLM watermarking techniques like Soft Red-List (Kirchenbauer et al., 2023) and MPAC (Yoo et al., 2023b) but improves text quality preservation, model-agnostic detection, and multi-bit embedding. It extends unbiased reweighting (Hu et al., 2023) with a multilayer approach, enhancing watermark robustness while maintaining detection reliability without model access.", "essential_references_not_discussed": "The references are sufficient to the best of the reviewer’s knowledge, covering key works on LLM watermarking, unbiased reweighting, and robustness.", "other_strengths_and_weaknesses": "Strong points\n\nThe paper presents an approach to LLM watermarking using unbiased reweighting and multilayer detection, aiming to balance text quality, model-agnostic detection, and message embedding. While prior methods often degrade text fluency for watermark robustness, BiMark seeks a trade-off to maintain detectability without significant quality loss. Theoretical foundations, including unbiased reweighting proofs and type-II error analysis, support its claims. Empirical validation on Llama3-8B and Qwen2.5-3B in summarization and translation tasks demonstrates its effectiveness. Its model-agnostic design removes dependence on internal parameters, suggesting scalability for AI-generated content authentication, though real-world feasibility remains an open question.\n\nWeak points\n\n(1)While the paper tests robustness against synonym substitution, it does not evaluate more sophisticated adversarial attacks, such as paraphrasing-based obfuscation, GAN-based perturbations, or adaptive attacks designed to break watermark detection. The authors are encouraged to evaluate the proposed method against other attacks or discuss the limitations of the watermarking approach.\n\n(2)The paper does not provide explicit inference-time benchmarks for the multilayer reweighting method, making it unclear how computational overhead scales with increasing layers or longer text sequences. The authors are suggested to report the runtime or discuss the computational complexity of the proposed method.\n\n(3)The multilayer watermarking approach shows non-monotonic performance as the number of layers increases. However, the paper does not explore adaptive selection strategies that could optimize performance for different text lengths or generation settings. The authors are encouraged to provide explanations for this observation.\n\n(4)Vague symbol and statements. The notation M[i][v] is used in the multi-bit watermark extraction process. However, it is not immediately clear whether M stores absolute counts or normalized probabilities, making it difficult to assess how well the voting mechanism works under noisy conditions. Moreover, it says that “However, the detection performance does not improve monotonically with the number of layers” While the paper mentions this non-monotonic behavior, it does not clearly explain why it occurs or whether it is due to statistical noise, overfitting, or implementation constraints.", "other_comments_or_suggestions": "Refer to the comments", "questions_for_authors": "Refer to the comments", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "q5ecKJ3f1S", "reviewer": "Reviewer_jksy", "summary": "In this work, the authors introduce BiMark, which encodes and extracts multi-bit messages via watermarking while preserving text quality. Meanwhile, BiMark enables model-agnostic detection via a bit-flip unbiased reweighting and enhances detectability via a multi-layer architecture.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1**:*Computational cost*\n\n**R1**: \nFor a single-layer reweighting, the method requires first calculating the probability of a vocabulary subset, then obtaining scaling factors based on these original probabilities, and finally adjusting the probability of candidate tokens. The complexity of this operation is $O(|\\mathcal{V}|)$.\n\nFor multi-layer setting, the operation is iterative, making the computation cost grow linearly with the increase in the number of layers, leading to a total complexity of $O(|d\\mathcal{V}|)$. \n\nThe table below shows the runtime for BiMark during a single inference pass in our experiments:\n\n|Method|Batch_size=1|Batch_size=50|\n|---------------------|-----------|--------|\n|BiMark|0.036 s|0.047 s|\n\nThe experimental result shows BiMark can benefit significantly from large batch size.\n\n**Q2**: *Type-II error of unbiased multi-layer reweighting.*\n\n**R2**: Although it is challenging to provide a close-form expression of type-II error rate of multi-layer watermarking at present since the current layer's probability depends on the reweighted distribution of the previous layer, the analytical idea is the same as single-layer reweighting.\nSpecifically, the detectability of multi-layer watermarking gradually decreases as unbiased reweighting reduces distribution entropy across layers.\n\nIntuitively, our method iteratively adjusts probability on tokens through unbiased reweighting based on our red-green vocabulary partitions. In a simplified case with two probabilities $p$ and $1-p$, each layer of reweighting transfers some probability $\\Delta$ between these groups with fair chance, creating a detectable pattern.\n\nAccording to type-II error rate analysis of our single-layer unbiased reweighting, higher entropy distributions allow higher expected green ratio in watermarked text, improving detectability. \nHowever, this process also inherently reduces entropy because entropy $(-\\sum_x p(x)\\log p(x))$ is concave, and our reweighting creates a more \"peaked\" distribution in expectation.\n\nAs a result, with each successive reweighting layer, the entropy of the reweighted distribution decreases in expectation, leading to diminishing marginal contributions to detectability. \n\nThis analysis explains our empirical observation that detection performance does not increase monotonically with the number of layers. Deeper layers operate on increasingly low-entropy distributions, offering proportionally smaller gains in overall watermark strength.\n\n**Q3**: *Experimental comparison.*\n\n**R3**: We would like to clarify our experimental choices:\n\nFor zero-bit case, BiMark was compared with Soft-Red-List (it only supports zero-bit watermarking). The labelling of Soft-Red-List as \"KGW\" in the figures will be corrected for consistency in the revised version.\n\nFor multi-bit case, BiMark was compared with MPAC. MPAC is not available for the zero-bit scenario since it is specifically designed for multi-bit watermarking tasks and is built upon Soft-Red-List.\n\nGINSEW \\[1\\] is not available as it is intended for a different purpose—specifically, protecting text-generation models from theft through distillation rather than detecting watermarks in individual text segments.\n\n\\[1\\] Protecting language generation models via invisible watermarking.\n\n\n**Q4**: *Ablation study*\n\n**R4**: In Fig.5(c\\), we set the number of reweighting layers to $d=50$. We apologize that the legend does not clearly reflect this setting.\nWe chose this large value to more clearly demonstrate how scaling factor affects watermark detectability when the number of layers is fixed.\nWhile the relationship between scaling factor and detectability holds for any value of $d$, the effects are more obvious with larger $d$ values, making the trends easier to visualize. \n\n**Q5**: *Potential vulnerability to attack*\n\n**R5**: \nWe have additionally evaluated the vulnerability of our method under paraphrasing attack, as shown in R3 to Reviewer kPVR.\nOur current work focuses primarily on the watermarking mechanism itself. We acknowledge the importance of  attack resistance, and we will investigate broader attack scenarios and conduct vulnerability analysis as part of our future work. \n\n**Q6**: *Code release*\n\n**R6**: Thank you for suggestions. We plan to release the code implementation at the time of the final decision announcement.\n\n**Q7**:*Concerns about representation*\n\n**R7**: Thank you for your suggestions. We will enhance our paper by: (1) providing more detailed experimental analysis (2) redesigning Figs. 1 and 6 to better illustrate BiMark's mechanisms; and (3) improving overall presentation with consistent terminology and clearer explanations throughout the paper.", "claims_and_evidence": "The claims are clear and reasonable, yet lack the explicit correspondence of evidence.", "methods_and_evaluation_criteria": "BiMark enables model-agnostic detection by a vocabulary size-based reweighting approach and enhances detectability via multi-layer reweighting mechanism. However, the main idea of preserving text quality is borrowed from unbiased reweighting.", "theoretical_claims": "Firstly, it needs to provide computation complexity of BiMark.\nSecondly, the authors provide Type-II error of single-layer unbiased reweighting, while failing to extend to multilayers.", "experimental_designs_or_analyses": "Firstly, the experiments are not fairly compared. The authors evaluate the model-agnostic detection of BiMark by comparing SynthID and KGW (the author mentioned only shot red list in analysis), while other representative works are missing, e.g., soft red-list, MPAC, and GINSEW. \n\nSecondly, the ablation studies are not clear in presentation or analyses. It is hard to identify the legend correspondence, and it is confusing to take d=50 for studying the detectability, yet d=50 is not studied in the effect of multilayer. \n\nThe analyses are not organized in a readable way, making it doubtful to use generative language models directly.", "relation_to_broader_scientific_literature": "BiMark's contributions are situated within the broader scientific literature on watermarking techniques for Large Language Models (LLMs). Specifically, BiMark integrates multilayer architecture enhancing detectability without compromising generation quality, and an information encoding approach supporting multi-bit watermarking.\nBiMark advances the field of digital watermarking, offering a robust solution for content authentication and intellectual property protection in AI-generated text.​", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Strenghts\n1 The authors provide a clear and comprehensive category of related watermarking work.\n2 The motivation is interesting and worth exploring.\n3 BiMarker is a model-agnostic approach that is compatible with existing generative models. \n\n\n\nweakness:\n1 Both Fig.1 and Fig.6 need more illustration. It is hard to follow by the current version.\n2 The presentation is hard to follow and needs to be polished better.\n3 The computation burden requires deeper analysis and potential solutions.\n4 BiMark is vulnerable to attacks, which needs deeper exploration.", "other_comments_or_suggestions": "1 The experimental analysis should enhance \n2 The figure could be illustrated more clearly.\n3 The project should release the code for better contribution.", "questions_for_authors": "See Above", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: All three reviewers recommended to accept this paper in their reviews. After discussion, it was eventually agreed that this paper meets the ICML acceptance bar.
The authors are encouraged to address the comments of the reviewers to improve this work.
The author’s rebuttal has been carefully read and discussed. The author’s message has been carefully read and considered.
Decision: Accept (poster)