Towards Codable Watermarking for Injecting Multi-Bits Information to LLMs
Authors: Lean Wang
Wenkai Yang
Deli Chen
Hao Zhou
Yankai Lin
Fandong Meng
Jie Zhou
Xu Sun
Venue: ICLR 2024 poster (2024)
Keywords: text watermarking
large language model
codable
systematic study
Primary area: societal considerations including fairness, safety, privacy
TL;DR: This paper conducts a systematic study on the topic of Codable Text Watermarking for LLMs (CTWL) and propose a novel method Balance-Marking for CTWL.

Abstract: As large language models (LLMs) generate texts with increasing fluency and realism, there is a growing need to identify the source of texts to prevent the abuse of LLMs. Text watermarking techniques have proven reliable in distinguishing whether a text is generated by LLMs by injecting hidden patterns. However, we argue that existing LLM watermarking methods are encoding-inefficient and cannot flexibly meet the diverse information encoding needs (such as encoding model version, generation time, user id, etc.). In this work, we conduct the first systematic study on the topic of **Codable Text Watermarking for LLMs** (CTWL) that allows text watermarks to carry multi-bit customizable information. First of all, we study the taxonomy of LLM watermarking technologies and give a mathematical formulation for CTWL. Additionally, we provide a comprehensive evaluation system for CTWL: (1) watermarking success rate, (2) robustness against various corruptions, (3) coding rate of payload information, (4) encoding and decoding efficiency, (5) impacts on the quality of the generated text. To meet the requirements of these non-Pareto-improving metrics, we follow the most prominent vocabulary partition-based watermarking direction, and devise an advanced CTWL method named **Balance-Marking**. The core idea of our method is to use a proxy language model to split the vocabulary into probability-balanced parts, thereby effectively maintaining the quality of the watermarked text. Our code is available at https://github.com/lancopku/codable-watermarking-for-llm.

Published as a conference paper at ICLR 2024
TOWARDS CODABLE WATERMARKING FOR INJECTING MULTI-BITS INFORMATION TO LLMs
Lean Wang* 1:8, Wenkai Yang* Deli Chen
Hao Zhou Yankai Lin', Fandong ,eng", .Jie Zhou Xu Sun "National Key Laboratory for Multimedia Information Processing,
School of Computer Science, Peking University
*Gaoling School of Artificial Intelligence, Renmin University of China Patterrn Recognition Center, WeChat AI, Tencent Inc., China DeepSeek AI
[lean, xusun @pku. edu. cn, victorchen@deepseek. (wenkaiyang, yarkailinnJeruc.c on (tuxzhou, fandongmeng, withtommhouu com
ABSTRACT
As large language models (LLMs) generate texts with increasing fluency and real- ism, there is a growing need to identify the source of texts to prevent the abuse of LLMs. Text watermarking techniques have proven reliable in distinguish- ing whether a text is generated by LLMs by injecting hidden patterns. How- ever, we argue that existing LLM watermarking methods are incoding-ineffccien and cannot flexibly meet the diverse information encoding needs (such as en- coding model version, generation time, user id, etc.). In this work, duet the first systematic study on the topic of Codable Text Watermarking for LLMs (CTWL.) that allows text watermarks formation. First of all, we study the taxonomy of LiM watermarking technolo- gies and give mathematical formulation for CTWL. Additionally, we provide a comprehensive evaluation system for CTWL: (1) watermarking success rate, (2) robustness against various corruptions, (3) coding rate of payload informa- tion, (4) encoding and decoding efficiency, (5) impacts on the quality of the gen- erated text. To meet requirements of these Porooartto-imiooiingg metries, we follow the most prominent vocabulary partition-based watermarking direc- tion, and devise an advanced CTWL method named Balking-Marking. The core idea of our method is to proxy language model to split the vocabulary into probability- ballnced parts, thereby effectively maintaining the quality of the wa- termarked text. Extensive experimental results show that method outperforms the baseline under comprehensive evaluation. Our code is available at https: //github. cow wwwpw////w..///////ooooo/opcpwpa codable watermarking riggniiin---go for- 11m
carry multi-bit customizable in-
INTRODUCTION
Recently, with the explosive development of Large Language Models (LLMs) OOpenAl 2022 Tou-
vron et al. 2023). there has been growing concern in the community about the potential negative effects of the Al-gerrrteed content (AIGC). For instance, LLMs could exploited to produce fake news, encyclopedia entries, academic papers. Hence, there is an urgent need to reliably distin- guish between numan-writted and Al-generated texts.
Text watermarking (Jalil & Mirza 2009, /enugopal et al. 2011) aims to inject hidden patterns into the generated text, and detect the specific patterns to determine the source text. The most representative line of LLM watermarking methods (Kirchen. al. 2023a Lee et al. 2023 Zhao et al. 2023) injects the watermark by controlling the available part of the vocabulary during LLM's decoding process and detect whether text contains watermark with high accuracy and low false positive rate. However, we argue that these existing LLM watermarking methods encode too
Equal contribution.

---

Published as a conference paper at ICLR 2024
Table 1: Taxonomy of LLM watermarking technologies, with representative work of each direc- tion attached. It can be found that existing LLM watermarking methods either do not make full use of the generation ability of LLMs, or lack customized watermarking information. Our work simul- taneously addresses both of these issues, filling the gap in this line of academic research.
Watermark
Watermark Injection Timing
Information
Post-preesss after I.I. Generation
Integrate with L.I. Generation
One-Bit
Black-Box Watermarking (Yang al. 2023b
LLM Watermarking (Kirhhen. et [023a]
Multi-Bits
Natual Language Watermarking (Yon et al.
2023a
Codable Text Watermarking for LLMS (This Work)
limited information (only I bit of information whether the text is generated by one specific model or not), and can not satisfy the increasing demand for customizing information in the application of LLMs (for example, embedding model and version information in the watermark can effectively trace the source of a text among multiple LLMs, etc.).
Present Work. We conducted the first systematic study the topic of Codable Text Watermarking for LLMs (CTWL), which allows the watermark injected into L.MM-generatd text to carry more customizable information. First and foremost, given the fact that the boundary and definition of CTWL remain unclear, we start with a taxonomy study on watermarking technologies (Section 2 and then give a mathematical formalization of the CTWL problem (Section B). Then, we propose comprehensive evaluation system for CTWL (Appendix C.. which consists of the following 5 crite- ria: (1) Success Rate: the LLM watermarking method should have high success rates of recovering message from watermarked texts and distinguishing between human- written and watermarked ones. (2) Robustness: the watermarking method should remain high success rate when facing different challenging attacks (such as copy-paste attack, substitution attack, etc.). (3) Coding Rate: the ratio of text token number to information bit number should be high. (4) Computational Complexity: the computation cost of watermark writing and decoding should meet the practical hardware and latency requirements. (5) Text Quality: the impact of adding complex watermark patterns on the quality of generated texts should be minimal.
Therefore, devising a practically applicable CTWL method is a challenging task, since it is difficult to make Pareto improvements in these conflicting metries. In this work. we first extend the random vocabulary splitting idea from Kirchen. et al.) 2023a), and devise the Vanilla-Marking method to encode multi-bit message in watermark. However, this naive baseline perform poorly in maintain- ing generated text quality, since multi-bit watermark is more complex than one-bit watermark, thus injecting multi-bit watermark causes a greater impact on the text quality.
To overcome this challenge, and inspired by the idea that a probability-balance vocabulary partition can more effectively ensure the quality of the watermarked text, we devise an advanced CTWL method named Balance-Marking. Specifically, we leverage proxy language model (proxy-LM) to guide the vocabulary partitioning instead of random splitting, ensuring that the probabilities of the available/unavilable parts are close to 50-50. This balance partition avoids the excessive impact of watermark on text quality caused by random vocabulary splitting(e.g. most nigh-prrobbbiltyy tokens are in the unavailable part). Also, this mechanism implicitly helps the watermark algorithm to skip low-entropy segments of text, which further ensures the text quality. Moreover, we can achieve a flexible and customizable watermarking algorithm deployment for different LLM application scenes by switching the proxy-LM. For example, we can take a small language model as the proxy-LM to ensure higher inference efficiency; we can take public language model the proxy-LM and achieve an open watermarking protocol among different L.LM providers without the leakage of the I.LMs. Extensive experimental results demonstrate that the Salance-Markinn method surpasses the method across different sizes of LLMs (OPT-1.3B (Zhang et al. 2022), LLaMA- 7B and LLaMA-13B (Touvron et al. 2023)). Additional experiments are performed to assess the influence of crucial modules within our approach. Furthermore, we analyze the application scenarios of CTWL and potential avenues for future research.
A more detailed discussion on the application scenarios of codable text watermark and the selection of proxy language models is presented in the Appendix D
2

---

Published as a conference paper at ICLR 2024
2
RELATED WORK
The current studies on identifying LLM-generated texts can be mainly divided into two categories: detecting-basee (introduced in Appendix A) and watermarking- based methods. The watermarking- based method has proven more effective and reliable [Sadasivan et al. (2023) and we focus on the watermarking-base method. Text watermarking technology marks text by injecting human- invisible hidden patterns into the text, and then determines the text source by detecting whether the
text contains watermark (Jalil & Mirza 2009, Venugopal et al., 2011]] Abdelnabi & Fritz 2021] Yang et al. 2022). We analyze the taxonomy of LLM watermarking methods in Table [ LLM watermarking techniques can be categorized into two types according to the point of watermark insertion: (1) Integrated into the model generation process Kirchen. et al., 2023a), and (2) Post- processing after text generation (Yoo et al. 2023a Yang al. (023b). Post-processing methods are independent of LLMs and they usually utilize masked language models (MLMs) (e.g. BERT (De- vlin al., 2019). RoBERTa (Liu al. (2019) to replace tokens with synonyms. Both one-bit Yang et al. (2023b) or multi-bits Yoo et [ (2023)) information can be injected in this manner. However, we argue that post-processing methods are not as effective as integrating methods for generating high-quality watermarked texts, since they do not take advantage of the generative power of LLMs. Moreover, replacement-bast based methods can only operate individual tokens and cannot adaptively change the subsequent generation sequence like integrating methods.
The most representative integrating watermarking technique for LLMs is proposed by Kirchen. al. (223a), which watermarks the L.L--eeeerteed text by manipulating the available part of the vocab- ulary. Following Kirchen. et al. (2023a), several studies explore effective text watermarking in various scenarios. Kirchen. et al. (2023b) later improves this method by exploring diverse choices of random seed generators for splitting the vocabulary. [ee et al. (2023) takes a step further to actively select high entropy tokens to watermark instead of all tokens, which is shown be more effective in the code detection task. Zhao et al. (2023) simplify the watermark method of Kirchen, jet al. (2023a) by making the vocabulary splitting independent of the previously generated tokens and only dependent on a global key. However, all these methods generate watermarks that only con- tain I bit of information, which cannot meet the need inject watermarks with diverse customized information. There are some very concurrent works YYoo et al.] [023b] Fernandez et al.) (023) that focus on this problem. These methods still follow the random vocabulary partition (Kirchen. et al.) 2023a), posing an unignorable threat to the quality of generated text caused by the multi-bits wa- termark. contrast, our MMrrking method can effectively maintain the text quality after injecting complex messages by balancing the probability distribution of the vocabulary partitions.
3 MATHEMATICAL FORMULATION OF CODABLE LLM WATERMARKING
3.1 NOTATIONS AND PRELIMINARIES
Here, we first introduce the necessary notations used in this paper. Assume there is a large lan- guage model LLM that takes prompt sequence xprompt as the input and sequentially outputs the corresponding tokens to form natural sentences as the response. At 1-th step (1 = 1, ...,..... L), the entire input for LLM is the combination of the original prompt xrrompt and the sequence of tokens t.(t-)) = (fo.... ... .4-1} that is already predicted by LLM in previous steps Then, LLM produces a probability distribution over the entire vocabulary V as PLLM (xLLM(XXroop)))) (xprompt t(( (..., Pt.LAs (w) reroopp t.((-))). ..... ), in which PLLM (v) (pxrrompt t:((-1)) is the predicted probabil- ity of a specific token e by LLM. The next token & is sampled based on PLLM (xprompt t.((-1))
according to specific sampling rules, such multinomial sampling or greedy sampling.
3.2 FORMULATION OF CODABLE TEXT WATERMARKING
In this paper, we propose the concept of codable text watermarking for LLMs (CTWL) that can encode rich and necessary information into the text watermarks, in order to satisfy the multiple demands on the realistic application of LLMss. Formally, CTWL can be formulated as a message
In the first step, there is no previously generated token, thus define none.
3

---

Published as a conference paper at ICLR 2024
encoding stage with message decodiin/extraacingg stage:
Encoding:
P x M MT Enc(xprompt m) b,
Decoding:
M- Dec(t)= m,
where P, T and M represents the prompt space, text space, and message space separately, m E M the message that needs to be encoded. Thus, one-bit watermarking methods can be considered as a simplified case of CTWL, where the message space only contains {0, 1}. Following the definition Eq. I... the target on decoding messages from can be written as
m arg max Pan (mm111t)))
m'EM
where we need to design a specific probability function Pa, referred to as message function (refer to Section 4.2) measure how likely is that the watermarked message is m' given t.
Therefore, according to Bayes Formula, in the message encoding phase, it is equivalent to achieve
max (t/(t//)) m' fm
max Pa (t)mm))))
I
(3)
max
log Pw (tilm, b((-1))))))
max 7
Σ
log Pue (lilmm, (aa-1)))-
1=1
That is, we aim to enlarge the gap between the probability that the text t is generated under message m and the probability that it is generated under other m' However, as we can see, the above equation only considers the target of effectively hiding message m into t, but does not take the quality of the generated text into consideration. Thus, we take the original text generated without embedded watermarks tar baseline for comparison, and reformulate the encoding phase as:
max Σ log Pa t.(-))) max m fm
log Puo (o t-(--))))
(4)
s.t. PPl(()xPromp)) (P (xpompp) +
Here, we utilize the perplexity (PPL) metric to measure the quality of the generated text, with the aim of ensuring the watermarked text maintains similar quality the text without watermarks.
4 BALANCE-MARKING, A SIMPLE YET EFFECTIVE CTWL METHOD
In this section, we first present an approximation algorithm to solve Eq. in Section 4.1 which serves as a general encoding algorithm for any predefined Pw- Then, we introduce two designs of P.. in Section 4.2 as unified guidelines to encode and decode messages. Finally, given the pre-defined encoding a algorithm and Pw. the message extracting can be performed as presented in Section
4.1 A GENERAL FRAMEWORK FOR CODABLE WATERMARK ENCODING
In order to solve the constrained optimization problem in Eq. ( the method of Lagrange Multipliers by introducing dual variable and turn it into an uncon- strained optimization problem. Furthermore, assume that the PPL scores in Eq. (4) are caleu- lated based on the same LLM used to generate t given the prompt xrromp and LLM, the term PPLLLM (tat (fori[xpronn can be regarded constant. Therefore, the target can be rephrased as:
motivated apply
flog PL..M( Prompp " + 5(log Pa (41mm, taa-)) - log Pu (u (1)--)))
max
1=1
(5)
where we use pt( = [ PLLMM (llppoop
prompt txq-1))) and set
L and vn.
argmax, nr fm Σ log P(tilm' 11)-
'The detailed derivations be found in Appendix B
"We take the form of division in Eq. in order to successfully derive the optimization target to Eq. 5
Thii assumption practical as the I.M. is powerful enough to accurately measure the perplexity of text.
4

---

Published as a conference paper at ICLR 2024
Algorithm 1: A General Message Encoding Framework for A Settled P.
Input: Language model LLM, prompt xPrompt message m, watermarking weight
for ( I..... , do
1. Calculate log PLLAS (e|xtrompt, ()))))))) for each v in the vocabulary using I.LM;
2. Calculate log Pa (v)m, t:(t-)) based on the settled Pw;
3. Select 1y = arg max flog PLLM (1/MMu//xroo (ulxprompt t,((-1)) + ō(log Pa (c/m,, t:(1-1))
Σ log Pul(olm', 1 M'EM
M
end
Output: watermarked text (21,6,,... ... .t,) ,tt)
Eq. ( motivates us that in order to encode m into t, we can manipulate the output logits dur- ing each token's generation by adding term 6(log (t (m, t.q--)) - -log (t mn, t:(+)))) to the original log logits. However, in practice, solving mn is infeasible because the true in can only be solved after the whole output & is determined, while need to calculate 5(log Pa (4 t((-1)) - log Pw (falm,, L((t-1)) in each generation step according to Eq. (5) Therefore, we replace log Pw (t m, 1)( with calculable [M| Em'r log (tilmm,, t.q--)) as an alternative, and finally get the message encoding object function in each generation step as:
L(m, x prompt t.((11)) max{log PLLM (c)mprompp (a(11)))
model logit
(6)
+ 5(log Pw (ulum,tttun
log (u
M
M!EM
message logit
where we denote the first term in the right as the model logit, which determined by the LLM only; we denote the second additional term the message logit, which is the key component for encoding message m into f.
As can see, long the function P is well-defined, the encoding process be completed by adding the message logits to the model logits and sampling the token based on the new logits. We put the general message encoding procedure in Algorithm 1 and will discuss how properly design Pw in detail in the next section.
4.2 THE DESIGN OF MESSAGE FUNCTION Pw
In the above section, we present a general encoding algorithm for an arbitrary P.. In the following. we will introduce two designs of Pt, as our preliminary attempts toward CTWL.
4.2.1 VANILLA Pe FOR RANDOM VOCABULARY PARTITION
According to Eq. (6), a high value of L(m, Prompt t-(--1)) relies on the existence of with high message logit. In other words, there should be a u for which log Pa. (v) m, t.(1-1)) greatly surpasses the mean. To achieve this, one natural idea to ensure that the distribution (m,,,, t:(-1)) = (Pan(1 Jm, t))= Pw (12/m, t.q-1)),". (u |m, t)) varies greatly across distinct messages. In this way, for message m, there would at least exist e whose log (w t.(1-1)) deviates far from the mean [M Emrem log (ulmmm, t:(111),, thereby resulting a high message logit. To ensure such differences in P (m, ty( with different m, we can assign random values for P (m, t((1-))) based on the random seeds directly decided by their own m:
[1, h(C, m. t)) 1,
log (ulm, t-0-))) = 10. bee, m. t(()n)) 0.
TToough employ greedy search as the text generation algorithm in Algorithm for example, framework is also compatible with other generation rules such heam search.
5

---

Published as a conference paper at ICLR 2024
Algorithm 2: Algorithm of Choosing Subset Vm,taa-1 (Practical Version in Red)
Input: Message m, text prefix t,(-1)), language model LLM, proxy-LM LMMrrozy Ma = {I,... A), hash functions and h.
1. Calculate seed = h(m, (.(1-1)). or = h(h(m), t.(1-1)) where h maps m to
h(m) MA:
2. Shuffle the vocab list (U1, , )pd) to (o1,--. F/yl) with the seed s;
3. Select the first & tokens in the shuffled list so that k is the minimal value to make
fo/,.... .ve, satisfy Eq, (9 or Eq
Output: Vm,tu-n {uy k
Pur tq(--))
log Pu (ulm, b.((11)) = log Σ Puolulm t((-11))
(8)
In the above, h denotes a hash function that maps the input (v. m. (.(-1)) to either 0 or 1. This can be considered vanilla extension from the soft watermarking method in Kirchen. al. (2023a)
by further taking m into consideration, thus we denote it as Vanilla-Marking.
4.2.2 AMprozy-AIDED Pw FOR BALANCE VOCABULARY PARTITION
The message function Pe proposed in Section 4.2.1 has a problem that it does not guarantee that the same v can also have high model logit the same time. This could potentially result in small sum of the model logit and the message logit. Therefore, we argue that a more advanced Pa: should produce with both a high model logit and message logit.
To accomplish this, we are motivated to utilize the model logit distribution PLEM Prooopt t.q-1) as prior knowledge, and pre-select subset of tokens that is likely to contain some tokens with high model logits in advance. Then, we assign high message logits to the tokens in the above subset, ensuring the existence of token with both high model logit and message logit. Formally, we propose Algorithm t randomly choose the subset Vm,t.a- that satisfies the following condition:
PLLM (uleroom tt(1-1))
BEV (1-1))
where a is a controllable threshold. W set 0.5 in the following paper unless otherwise stated, be- cause we believe that balancing the probability accumulations of tokens within and out of Vm,t, 1 can achieve the maximal diversity of V Vm,t,a- w.r.t. different The reason why design Al- gorithm 2 in such way is, the case when all {PLLM Proxprompt, t-(-n)) Vm,, } values tend to be small, yet still sum to a, is very unlikely to occur. Thus, there should always be some PLLAS (v prompt ti) that is relatively large to make the summation exceed the threshold. Ad- ditionally, introducing randomness in the selection process of Vm,ta-n) can enlarge the difference in V Vm,t.a-. among different messages m, which plays the same role as that in Vanilla-Marking
After getting Vm,taa-ay we assign the message logits by following Eq. 8 but modifying Eq. (7) as
E Vm.aa- log (ululm, = 1,, v & Vmntaa-
1,
(10)
Also, we make some specific improvements to make our method more practical in various scenarios. We summarize these strategies briefly here, and put the detailed illustrations Appendix F (1) We omit prompt and truncate t,(1-1) to fixed-length Eq-1--Emess))(0-)) for consistency during
both encoding and decoding. (2) To make our method applicable in various scenarios discussed
in Appendix D we broaden the LLM used in PLEM (ulta--1-a -ip----ppaaaale ((01))))0111))) into general proxy model denoted as LMprexy and modify the condition in Eq. (9) to:
Σ
PIM
2
(11)

---

Published as a conference paper at ICLR 2024
(3) For efficient encoding and decoding the entire message space, opt to first map the entire message space into smaller space as h(m) E MA = (1, " A by using another hash function h, and then compute the seed s as s = h(h((m)
The practical version of the above LMprezy-aidee aided watermarking method is specially highlighted in red Algorithm 2 Given that employs probability-bllanee vocabulary partition, we refer as Balance-Marking.
Here, we briefly discuss about the two advantages that Balance-Marking has compared to Vanilla- Marking. (1) First, Balance-Marking is more effective in maintaining text quality. That is because the way pre-choosing the subset Vm.t.-_.) ensures that Balance-Marking can find tokens with both high model logits and message logits, thus making the next generated word more mean- ingful and reliable. However, Vanilla- Munilla-Marking, which just randomly selects the available tokens, might end up with an unreasonable next token. (2) Secondly and interestingly. Balance-Marking also has the ability to automatically bypass low-entropy sections of the text, which a property that Lee et al. (2023) explicitly aims to achieve. For example, if there is only candidate whose predicted probability by proxy-LM is almost 1.0, then for all messages, this token would be selected into the available part. In other words, this position in the sequence is implicitly "skipped" during watermark encoding and decoding, and the decoding process is actually carried out by comparing the values of Pw under different on those high-entropy sections of the text.
reasonable token
4.3 MESSAGE DECODING
For settled Pa the decoding process is conducted by finding a solution to Eq. (2) As per Bayes' Theorem, this can be rewritten as:
m arg max Par (t)(mmm = arg max log Pw (t t.(-1)))-
(12)
m'EM
E.EM
Eq. 12 can be computed directly using either Eq. and Eq. for Vanilla- and Eq. (8) for Balance-Marking. Furthermore, when we need to encode multiple messages into
Eq. (T))
text, we can sequentially encode each message into segment of the text (e.g., every 100 tokens
of the text). Then, message decoding can be conducted independently within each segment.
5 EXPERIMENT
5.1 EXPERIMENTAL SETTINGS
Following the experimental settings used by Kirchen. et al. (2023a), we utilize OPT-1.3B (Zhang ct al. 2022) for the generation texts in main experiments. We also conduct experiments on LLaMA- (Touvron et al. 2023) models. Our prompt inputs are derived from the news-like subset of the C4 dataset (Raffel et al. 2019). In each experiment, we extract 500 prompt inputs and truncate them to uniform length of 300 tokens. The language model is then requested generate 200 tokens via a 4-way beam search. To mitigate repetition in the generated text, we implement repetition penalty of 1.5. We evaluate the quality of the text by perplexity. For OPT-1.3B, we use OPT-2.3B to calculate perplexity. As for LLaMA-7/13B, we use LLaMA-33B to calculate perplexity. The evaluation protocol for CTWL is introduced in Appendix C Besides, a case study provided in Appendix K
As for the LMprozy in Dolance-Markingg we opt to use GPT2 [Radford publicly available, and comparatively smaller language model, which comprises 124M parame- ters. Additional hyper-parameters used in Balance- Balance-Marking are set to the following: A = 100, T.prefir = 10, 20-bit information. The hash scheme is the same as Kirchen. et al. (2023a). A detailed discussion is presented in G Besides, conduct some approximation for acceleration, which is detailed in Appendix
2019 a well-known,
0.5 and M {0, 1,.., 200 1). Here, a message m E M corresponds to
For detailed discussion about the choice of A, refer to Appendix G.2
7

---

Published as a conference paper at ICLR 2024
Coding Rate: 10 tokens/
Coding tokens bid
(c) Capy-Paate Attackss
Substitution Atlacks
0.90
0.00
3.0
Perplexity
Perplexity
Perplexity
Perplexity
Balance-Marking
Vanilla-Marking
No watermark
Figure 1: Balance- Marking outperforms marklng under both different coding rates (subfig- ure a, b) and different attack scenarios (subfigure c, d).
5.2 THE RESULTS OF WATERMARK QUALITY
We experiment with Vanilla-Marking and Balance-Marking by adjusting the parameter ô in Algo- rithm 1 This parameter helps strike a balance between text quality and watermark success rate. Higher& 8 values lead
stronger watermark but at the expense of text quality. We run tests using range of 5 values (i.e., (0.5, 0.8, 0.9, 1.0, 1.1, 1.3, 1.4, 1.5, 1.8, 2.0, 2.5, 3.0, 4.0}) and coding rates of 10 or 5 tokens per bit to observe the corresponding effects.
Figure Ta and 1b depict the trade-off between text quality, assessed by perplexity, and the success rate of recovering the embedded watermark. Enhancing the watermark's success rate tends to ad- versely affect text quality, and embedding watermarks with high coding rate of 5 tokens per bit is particularly challenging. In both cases, Balance-Marking outperforms Vanilla- MaarkigMarr,ng, offering superior trade-off between text quality and watermark success rate.
5.3 THE RESULTS OF ROBUSTNESS TO REAL-WORLD ATTACKS
In real-world applications, the embedded watermark in text can be weakened by different types of attacks. For example, watermarks can be difficult to detect when hidden in Homan--riiten texts, a situation known Copy-Paste Attacks (Kirchen. al. (023b). Moreover, the watermark can be eroded by actions like word substitution, referred to as Substitution Attacks. In our study, we apply these attacks to the watermark under a coding rate of 10 tokens per bit
Robustness to Copy-paste Attacks. A possible way use LLM-generated text is integrate into human-written documents. We refer to this as a "Copy-Paste Attack" (Kirchen. et al. 2023b). This presents challenge in watermark detection the location of the watermarked text becomes unpredictable. To simulate this, we insert 200-token watermarked text into a 1000-token piece of written text, taken from the C4 dataset. The detection process involves using slid- ing window technique (Kirchen. et al. 2023b) and computing (m (aaliding..iidoo incorrectly labeling human-writtee written texts as watermarked texts, we set a threshold of - 10-5 Any Xsliding. window with max, P(m x) below this threshold will make be classified human- written. Our tests reveal that this threshold successfully prevents mislabeling buman--ritte texts as watermarked. Figure [C demonstrates the robustness of both Salance-Marking and Kanilla-Marking methods against copy- -paste attacks, with Balance- maintaining superior performance.
)
0 To avoid
Robustness to Substitution Attacks. In the practical application of model-generated texts, to- kens may be replaced for editing purposes to prevent watermark detection. To replicate this, we employ the RoBERTa-Large (Liu et al. 2019) model to carry out word substitution (see details in
omit the case of coding rate tokens per hit since makes both watermarks ineffective under attacks. Applyyigg Bayes' Theorem, we know that P., xx) is proportional to P., (x mm), which can be computed explained Section 4.3 By normalizing Pw (x]mm, obtain (m/x).
8

---

Published as a conference paper at ICLR 2024
Trcafie Time
1.00
Reologahiing
7H
15.0
Reae
10M4
0.55
Tine bxcands
8.00
8.80
7,5
531
0,38
8.00
2.8
0.86
616
35
35 Perphecity
3,5
30
Necteen
Line
Perplesily
Perpledit
Vellace-Marking
Vanilla
No wrtermmack
Figure 2: (a) Trade-off between efficiency and watermark success rate. Specifically, Vanilla- Marking can be viewed as Balance-Marking with L.Mrrozy = O (denoted as "null"). (b) Balance- Marking outperforms Vanilla-Marking in distinguishing between message-embedded and human- written texts. (c, d) Balance-Marking is still superior to Vanilla-Marking when using LLaMA-7/13B.
Appendix H). Figure Id illustrates the impact of Substitution Attacks (substitution ratio=5%) on Manilla-Marking and Balance-Marking. Balance-Marking outperforms Vanilla-Marking as under Copy-Paste Attacks. Experiments with a substitution ratio of 10% are reported in Appendix [
5.4 FURTHER ANALYSIS
Distinguishing between message-embedded and human-written texts. In practice, it's very im- portant to ensure that human-written texts are not wrongly identified as watermarked. To prevent extracting pseudo messages from human-written texts, tion 5.3 While this threshold guarantees to prevent all human-written texts from being incorrectly identified, may also misidentify some watermarked texts human-written. Figure 2bb demon- strates this by showing both the success rate of correctly distinguishing message- embedded texts from human Still, Balknce-Marking outperforms Vanilla-Marking.
the same threshold 1 1 10- in Sec-
message-embedded numan-written written ones, and the corresponding text quality (the coding rate is 10 tokens per bit).
Trade-off' between Efficiency and Watermark Quality. The LMprosy introduced in Balance- Marking brings better watermark quality but also along with extra computational cost. In Figure 2a we verify this trade-off between the efficiency and watermark quality when larger L.Mprozy' are introduced. Specifically, we can view Vanilla-Marking as special kind of Balance-Marken with Liprroay = also discussed the LMprrzy LLM case in Appendix G.I
Scaling to larger LLMs. To verify that our watermark algorithm also works for larger LLMs, we conduct experiments with LLaMA-7/13B (under a coding rate 10, and smaller set (0.8, 1.0, 1.2, 1.5, 2.0. to save computational costs), as shown in Figure 2d Appendix also lists the results with coding rate 5. Balance-Marking stably outperforms Vanilla-Marking when scaling to larger LLMs.
6 CONCLUSION
In this work, we provide the first systematic study on the topic of Codable Text Watermarking for Large Language Models (CTWL), filling the research gap of integrating multi-bit information wa- termarks into the generation process of L.Ms.. We first conduct taxonomic analysis of CTWL. and provide a rigorous mathematical formalization for CTWL. We then design CTWL method Balance-Marking, which effectively ensures the balance of the probabilities of available and un- available vocabularies with the help of proxy language model, thereby ensuring the high quality and diversity of the generated text. Extensive experiments have shown that our method significantly outperforms the direct baseline method in the comprehensive evaluation of five dimensions, reach- ing a practical level of usability. We hope that our work can help the community better understand the CT'LL issue and inspire more outstanding research in the future.

---

Published as a conference paper at ICLR 2024
ETHICAL STATEMENT
Our paper aims to provide an effective way to reduce the ethical problems brought by the LLMs. Our method can inject watermark that carries rich information into the text generated by the LLMs, thus helping the public to identify whether the specific text is machine-generated under some necessary circumstances. For example, of the name of the source LLM can be easily traced from the source once it is used for harmful purposes, such as creating fake news or cheating on academic writings. Therefore, our work does not have any negative ethical concerns.
seschine-generater text with watermarks that carry the information
REPRODUCIBILITY STATEMENT
We have provided the necessary explanations for all the assumptions we made after they are pro- posed in the main paper. We provide detailed mathematical derivations for the complicated formu- las such deriving Eq. (4) to Eq. (5) in Appendix B We present the detailed illustrations of the approximations we made during mathematical derivations in Appendix [ We give the necessary illustration of the experiment settings in Section [5.] and Section [..1 the main paper. The detailed explanations and explorations of training hyper-parameters are in Appendix G The descriptions of the implementations of substitution attacks in Appendix H
ACKNOWLEDGEMENTS
We sincerely thank all the anonymous reviewers for their helpful suggestions improving manuscript. This work is supported in part by Tencent Research Grant and the National Natural Science Foundation of China (No. 62176002). Yankai Lin and Xu Sun are the corresponding authors of this paper.
REFERENCES
Sahar Abdelnabi and Mario Fritz. Adversarial Watermarking Transformer: Towards Tracing Text Provenance with Data Hiding. In 2021 IEEE Symposium on Security and Privacy (SP), pp. 121- 140. IEEE, 2021.
Anton Bakhtin, Sam Gross, Myle Ott, Yuntian Deng, Marc' Aurelio Ranzato, and Arthur Szlam. Real or Fake? Learning to Discriminate Machine from Human-GGnnrated Text. arXiv preprint arXiv:19066 03351, 2019.
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training Deep Bidirectional Transformers for Language Understanding, In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Lan- guage Technologies, NAACL-ILT 2019, Minneapolis, MN, USA, June 2-7, 2019, Volume I (Long and Short Papers). pp. 4171-4186, 2019.
Pierre Fernandez, Antoine Chaffin, Karim Tit, Vivien Chappelier, and Teddy Furon. Three Bricks to Consolidate Watermarks for Large Language Models. CoRR, abs/2308.0011.. 2023.
Zunera Jalil and Anwar M Mirza. Review of Digital Watermarking Techniques for Text Doeu- ments. In 2009 International Conference on Information and Multimedia Technology, pp. 230- 234. IEEE, 2009.
Ganesh Jawahar, Muhammad Abdul-Mageed, and Laks VS Lakshmanan. Automatic Detection of Bichinne-Genrrteed Text: A Critical Survey, arXiv preprint arXiv:2011.01314, 2020.
John Kirchen., Jonas Geiping, Yuxin Wen, Jonathan Katz, Ian Miers, and Tom Goldstein. Water- mark for Large Language Models. arXiv preprint arXiv:2301. 10226, 2023a.
John Kirchen.. Jonas Geiping, Yuxin Wen, Manli Shu, Khalid Saifullah, Kezhi Kong, Kasun Fer- nando, Aniruddha Saha. Micah Goldblum, and Tom Goldstein. On the Reliability of Watermarks for Large Language Models. arXiv preprint Xiv::236600663. 2023b.
10

---

Published as a conference paper at ICLR 2024
Ryuto Koike, Masahiro Kaneko, and Naoaki Okazaki. OUTFOX: LLM- -eneraatd Essay Detection through In-context Learning with Adversarially Generated Examples. CoRR, abs/2307.11729, 2023.
Taehyun Lee, Seokhee Hong. Jaewoo Ahn, Ilgee Hong, Hwaran Lee, Sangdoo Yun, Jamin Shin, and Gunhee Kim. Who Wrote this Code? Watermarking for Code Generation. arXiv preprini arXiv:2305. 15060, 2023.
Yinhan Liu, Myle Ou, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. Roberta: A Robustly Optimized Bert Pretraining Approach. arXiv preprint arXiv:1907. 11692, 2019.
Eric Mitchell, Yoonho Lee, Alexander Khazatsky, Christopher D Manning, and Chelsea Finn. Detectgpt: Zero-Shot
Text Detection using Probability Curvature. arXiv
preprint arXiv:2301. 11300, 2023.
Sandra Mitrović, Davide Andreoletti, and Omran Ayoub. Chatgpt or Human? Detect and Explain. Explaining Decisions of Machine Learning Model for Detecting Short Chatgpt-Generann Text. arXiv preprint arXiv:2301. 2023.
OpenAl. GPT-2: 1.5 Release. November 2019. URL http:tts///ooeaai.co//eeeeaeae
--t-2-1-5b-re relassee
OpenAl. ChatGPT: Optimizing Language Models for Dialogue. November 2022. URL https:
bl //ogenaa..com/lllgg//cagggggg
OpenAl. New AI Classifier for Indicating Al-Written Text, 2023. URL https::////o/ com/
Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. Language Models are Unsupervised Multitask Learners. OpenAl blog, 1(8):9, 2019.
Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu. Exploring the Limits of Transfer Learning with a Unified Text-to- Text Transformer. arXiv e-prints, 2019.
Vinu Sankar Sadasivan, Aounon Kumar, Sriram Balasubramanian. Wenxiao Wang, and Soheil Feizi. Can Al-Generated Text be Reliably Detected? arXiv preprint urXiv:2203.11/55 2023.
Victor Sanh, Lysandre Debut, Julien Chaumond, and Thomas Wolf. DistilBERT, a Distilled Version of BERT: Smaller, Faster, Cheaper and Lighter. arXiv preprint arXiv:1910.011 2019.
Irene Solaiman, Miles Brundage, Jack Clark, Amanda Askell, Ariel Herbert-Voss, Jeff Wu, Alec Radford, Gretchen Krueger, Jong Wook Kim, Sarah Kreps, al. Release Strategies and the Social Impacts of Language Models. arXiv preprint arXiv: 09203, 2019.
Edward Tian. GPTZero. 2023. URL http:htts:////ttm http::://gppttrrooooom
Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al. Llama: Open and efficient foundation language models. arXiv preprint arXiv:2302. 13971, 2023.
Ashish Venugopal, Jakob Uszkoreit, David Talbot, Franz Josef Och, and Juri Ganitkevitch. Water- marking the Outputs of Structured Prediction with an Application in Statistical Machine Trans- lation. In Proceedings of the 2011 Conference on Empirical Methods in Natural Language Pro- cessing, pp.
2011.
Kangxi Wu, Liang Pang, Huawei Shen, Xueqi Cheng, and Tat-Seng Chua. LLMDet: Large Language Models Detection Tool, arXiv preprint arXiv:2305. 200.:2300550.0.... /5004, 2023.
Lingyi Yang, Feng Jiang, and Haizhou Li. Is ChatGPT Involved in Texts? Measure the Polish Ratio to Detect Cheerat-GGenrrated Text. CoRR, abs/2307.1 1380, 2023a.

---

Published as a conference paper at ICLR 2024
Xi Yang, Jie Zhang, Kejiang Chen, Weiming Zhang, Zehua Ma, Feng Wang, and Nenghai Yu. Tracing Text Provenance via Context-Aware Lexical Substitution. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 11613-11621, 2022.
Xi Yang, Kejiang Chen, Weiming Zhang, Chang Liu, Yuang Qi, Jie Zhang, Han Fang, and Nenghai Yu. Watermarking Text Generated by Black-Box Language Models. arXiv preprint arXiv:2305.08883 2023b.
Kioo Yoo, Wonhyuk Ahn, Jiho Jang, and Nojun Kwak. Robust Multi-bit Natural Language Watermarking through Invariant Features. In Proceedings of the 61st Anmual Meeting of the Association for Computational Linguistics (Volume 1: Long Pupers), pp. 2092-2115, 2023a.
KiYoon Yoo, Wonhyuk Ahn, and Nojun Kwak. Advancing beyond identification: Multi-bit water- mark for large language models. CoRR, abs/2308. 00221, 2023b.
Susan Zhang, Stephen Roller, Naman Goyal, Mikel Artetxe, Moya Chen, Shuohui Chen. Christo- pher Dewan, Mona Diab, Xian Li, Xi Victoria Lin, Todor Mihaylov, Myle Ott, Sam Shleifer, Kurt Shuster, Daniel Simig, Punit Singh Koura, Anjali Sridhar, Tianlu Wang, and Luke Zettlemoyer. OPT: Open Pre-trained Transformer Language Models. ArXiv, abs/2205.01066 2022.
Xuandong Zhao, Prabhanjan Vijendra Ananth, Lei Li, and Yu-Xiang Wang. Provable Robust Wa- termarking for Al-Generated Text. 2023.
12

---

Published as a conference paper at ICLR 2024
A SUPPLEMENT TO RELATED WORK
Detecting-based Methods. This kind of method aims to detect whether a text is generated by language model by formulating the task as binary classification problem (Bakhtin et al., 2019 Jawahar et al., 2020 OpenAA] 2019). (1) One way to achieve this goal is to first collect outputs from specific LLM along with human-writter texts, and then use them to train binary classi- fier Mitrović et al. (2023). For example. O (2019) fine-tune a RoBERTa classification model
detect whether text is generated by GPT-2 model or not. Later, MMirrović et al. (2023) collect
data produced by ChatGPT
(2022) and fine-tune a DistilBERT model (Sanh et al. 2019)
to distinguish texts written by humans and that generated by ChatGPT. OpenAl (2023) create
more advanced classifier that can detect texts generated by variety of diverse LLMs. (2) Besides
explicitly training deep classifiers, some other methods achieve detection by exploring the statisti- cal differences between
texts and ouman-written texts (Solaiman et al.) 2019) Wu
jet al.] 2023). GPTZero (Tian) 2023) popular tool identify machine-gent -eeherntgeeerttedd texts by cal- culating the perplexity and burstiness scores of texts and comparing them with specific thresholds. DetectGPT (Mitchell et al. 2023) claims that when a machine-generale
text is perturbed, its log probability will always show decreasing pattern, which is not the same for human-written texts. Based on this finding, it defines a log probability-basee metric to help detect texts generated by LLMs. Recently, there have been the detection of machine-generated text in specific domains. However, all these detection methods face the risk of becoming increasingly ineffective in the future, the LLMs will be consistently im-
works (Koike et al., 2023 Yang et al.) 2023a exploring
proved to behave more and more like humans, which finally makes detection impractical (Sadasivan al. 2023).
B DETAILED MATHEMATICAL DERIVATIONS OMITTED IN THE MAIN PAPER
Here, we provide detailed mathematical derivations about the formulas that are simplified in the main paper.
Eq.
max (t/mm/
max (t)(t)mm)) m'
max i Pu (tilm'm (attil'',tuu))))) t.(-1)))3 max i (tal m, t))/ mn 7m
(13)
max
log Pw (tilmm, (t(mm,ttaa)))
max 7f
log Pu (ut( Σ
From Eq.
4 to Eq. 5
As (PL
= = P(ty (xprompt +:((--1))) Eq. 4 equi--
alent to
max
log Pu ((t(),,t.(-)))
max mn p
log Pu (tilmm, 11)- Σ
Iml
(14)
log P(tx t((-1))) < (t prompt + e).
s.t.
1=1
By applying the method of Lagrange Multipliers, we can re-define the target as:
log Pu (u (tllmm, t.(1-1)) log Pu (telm, t((-1))) - max Σ Fm
max
1=1
(15)
log P(t t.(t log (PP (xpoppom +)]]
For simplicity but without loss of generality, let's assume that the PPL scores are calculated based on the same LLM used to generate [0 In this case, given the prompt prompt and LLM, the term
This assumption is practical as the L.M is powerful enough to accurately measure the perplexity of text.
13

---

Published as a conference paper at ICLR 2024
PPLLLM (t
(erompt) (xpropt))) can be regarded constant. Therefore, Eq. 15) can be rephrased
max
log (1 (.(-))))
log (u ,.a(-))))
i=1
(16)
log PLLM (t/x(t//prrmpp prompt t((--1)))-
Let = I and vi- = argmax Σ
log P(4]m', 1:(1-1)); the objective function can be restructured as
x
m' #m
Eq. 5
C THE EVALUATION SYSTEM OF CODABLE LLM WATERMARKING
The prosperity of LLM technology has brought more diverse and differentiated application scenarios than traditional NLP models. Therefore, the evaluation of the practicability of LLM-ggnnrated text watermarking technology is expected to keep pace with this trend. However, existing studies lack a unified convincing evaluation system for LLM- -eM----erttted text watermarking technology. In this section, start with analyzing the uniqueness of LLM applications and establish comprehensive evaluation system for LLM-generated text watermarking from 5 different aspects.
C.I WATERMARKING SUCCESS RATE
define two indicators to measure how successful the watermark is injected into LLM- LLM-generated texts as expected: (1) Success rate of recognizing the model-generated texts from human written texts, and (2) Success rate of recovering the injected watermark message. Both of these two metrics need to be considered for CTWL; while for normal LLM watermarking (Kirchen. al. (023a), only the first metric need to be evaluated.
C.2 ROBUSTNESS AGAINST ATTACKS
Texts generated by LLMs are usually modified before they are actually used for the purpose of pol- ishing detection escaping. Thus, the watermarking algorithms need to ensure robustness in the face of various corruptions and attacks. We summarize the two most representative attacks threat- ening the success of LLM watermarking: (1) Copy-Paste Attack (Kirchen. al. 2023b). where wumttewritten LLM-generated text fragments are mixed with human written text fragments; (2) Substitution At- tack, where individual or sequential tokens synonymously replaced based human knowledge or masked language models like BERT (Devlin et al. 2019) or RoBERTa (Liu et al. 2019).
C.3 PAYLOAD INFORMATION CODING RATE
For non-codable watermarking methods, the encoded information always one-bit. For CTWL, we divide the number of bits carried by the watermark by the length of the covered tokens the indica- tor for measuring the coding rate the watermarking algorithm. Obviously, good watermarking technique should encode as many bits of information possible without sacrificing the performance on other metrics.
C.4 ENCODING AND DECODING EFFICIENCY
Injecting watermarks during LLM's generation will inevitably increase the computational cost. Moreover, restoring multiple bits of information from the text also takes higher computational com- plexity than decoding 1-bit information. We argue that it is necessary to consider the additional computational complexity brought by the encoding and decoding of the large model watermarking algorithm. Besides, the parallelism of the watermarking algorithm is also vital for the actual time consumption.
14

---

Published as a conference paper at ICLR 2024
C.5 IMPACT ON THE QUALITY OF GENERATED TEXT
Codable watermarks contain more complex information and have larger impact the quality of text generated by LLMs than non-codable watermarks. Therefore, it is necessary to ensure that the impact of the watermark the quality of LLM-generater text is within acceptable range for the deployment of watermarking algorithms. the current work, we adopt the text perplexity (PPL) as an automated metric to measure the quality of LLM- --geeerrttedd texts. In future work, will include more metrics such as semantic similarity or human evaluation for comprehensive evaluation text quality.
D POTENTIAL APPLICATION SCENES OF CODABLE LLM WATERMARKING
In this section, we analyze some potential application scenarios of codable LLM watermarking, and examine how our method adjusts the proxy-LM to adapt to the varying demands for watermarking techniques in different application scenarios.
D.1 CORPORATE INTELLECTUAL PROPERTY PROTECTION
For service providers based on LLMs, generating texts with watermarks containing information related the model, service, request, or user can effectively ensure that the generated texts can be traced and identified, thereby preventing the model from being used unreasonably or without authorization. Service providers can flexibly choose and combine the information to be included in the watermark to better protect their intellectual property. In this scenario, as the owner of LLMs, the service provider can choose to use the large model itself as a proxy-LM to minimize the impact of adding watermarks on the quality of the text, or prepare small model similar to the large one to accelerate inference through methods like distillation, quantization, or pruning.
D.2 USER-LEVEL COPYRIGHT PROTECTION
The discussion on the copyright of text generated by LLMss is also interesting topic, users may believe that their intellectual input when writing prompts gives them (at least part of) the copyright of the generated text. In such situation, users can choose reach an agreement with the LLMs service provider on a customized watermark algorithm for the user self (through customizing the proxy-LM or hash function). the encoding stage, the service provider will generate text containing a specific watermark according to the user's 's exclusive watermark encoding algorithm. When the user wants to prove that piece of text comes from him- herself, the user can request the service provider to use his or her exclusive decoding algorithm to confirm whether it contains personal watermark. To make this more credible, an independent third-party organization similar to the patent office can take the responsibility to manage and certify these customized watermark algorithms.
D.3 OPEN WATERMARKING PROTOCOL
For the public, it is desirable to have a very convenient way to identify whether a text comes from a model and which model it comes from. We propose idea based to reduce the identification problems caused by scattered and differentiated watermarking methods adopted by different service providers. First, the protocol selects open-source language model (such as GPT-2) as a proxy-LM, and then determines a unified and scalable message coding system establish publicly available watermark encoding and decoding algorithm. Any service provider that joins this protocol can use the watermark encoding algorithm to inject watermarks into the texts generated by their private models by extending the message coding system. this way, the public can efficiently identify all models that join the protocol using a single decoding algorithm. The technical support for this idea to work is that our Balance-Marking leverages both the LLMs and the proxy-LM during the encoding stage, while in the decoding stage, only the proxy-LM is needed to restore the watermark information. This makes it possible to have multiple closed-source LLMs encoding and single public model decoding. If as many service providers possible join this protocol, identifying the source of the text will become an increasingly easy task, which can effectively alleviate the impact of L.M--generteed texts human community order and security.
open watermark protocol
15

---

Published as a conference paper at ICLR 2024
D.4 RELAY WATERMARKING AMONG MODELS
Model-generated text that is actually applied is usually not generated in one step, but may go through multiple users multiple models for processing, such as expansion, polishing, translation, para- phrasing, and so on. we want to track the complete production process the information of the last model processing, it is feasible ensure that the watermark incremen- tally written in a relay form among different models. As discussed in the previous subsection, this requires an open watermark protocol and a scalable information encoding system. This also requires adding a processing step to our method: first extract the watermark message from the text input to the model, mix it with the message of the new model itself, and then add the new message to the watermark of the newly generated text. In this way, we can track the complete life cycle of machine- generated text. Of course, as discussed in the previous subsection, this also requires as many LLM service providers possible to join the open watermark protocol.
text, not just obtain
E APPROXIMATION DURING CALCULATION P.
In calculating Pw. of Vanilla-Marking and Balance-Marking, we perform the following two approx- imations.
Excluding Term [M EmveM log (ulummm, t.(1-1)) from Encoding When implementing Al- gorithm there is need to compute TM Em'em log Pao (ulm', kaa-1)), which can be time- consuming task. However, due the inherent randomness of Pw, hypothesize that this mean value almost remains constant under the Law of Large Numbers. This hypothesis is corroborated by our empirical studies (see Appendix E. that indicate that this value remains close to -11 with a relatively insignificant standard deviation (less than 0.05) across v. Hence, we can exclude this calculation from Algorithm during encoding for efficiency.
Substituting log (ulmm, t.(1-1)) with log Pu(ulm, 1)) during Decoding Similarly, we substitute log Pe (v/m, ((((1))) with log (ulmm, t.(1-1)) in Eq. (12). The difference between the two expressions equals log Σ Pu (elm, t:(1-1)), which we assume to be almost constant. Our empir-
ical findings (see Appendix [E.2) support this claim. In the Kanill--Marking approach, the standard deviation is as low as 0.002, with an average value of 11.4. Despite Balance-Marking having slightly higher deviation (0.23) and a mean of 11.4, still allows for the exclusion of this calcula- tion to help speed up the computation process.
E. EXCLUDING TERM [M EmEm log (ul(rmm t,(1-1)) FROM ENCODING
The randomness present within the design of the message function P. allows us to interpret ex- pressions of log P. (#lm', tg-s))s in 21 Σmem log (u t()( independent and iden- tically distributed (i.id.) random variables. Consequently, via the law of large numbers, the term [M Em'cm log P., (v (v/m,, mmm, t:(1-1)) remains approximately constant.
1
As practical test of our hypothesis, we randomly selected 100 sequences of t.(1-1) from human- written texts (specifically, the news-like subset of the C4 dataset (Raffel et al., (0199) as well as watermarked texts. Afterward, for each t.(r-1), randomly picked 100 tokens v from the vocab-
ulary to calculate the standard deviation of M
Σ log Pw (ylm', t((-1)) across v We report
EM
the standard deviation and mean across v (averaged over 100 instances of t.()-1))) in Table 2 Given
the small standard deviation across the vocabulary, it's appropriate to exclude it in Algorithm
Since the solution t depends on the model logit and message logit of u under given (. 1); it's enough concentrate on the variations across
16

---

Published as a conference paper at ICLR 2024
Table MM
Σ
log Pu(umm' 1)( on human-written texts and watermarked texts. The num-
m'EM bers are the mean + and the standard deviation across v.
Human-Written Texts
Watermarked Texts
Marking
-10.95 0.0005
-10.95 + 0.0005
Malance-Marking
-10.93 + 0.0461
-10.93 +: 0.0457
E.2
SUBSTITUTING log t(a-)) WITH log (o taa-1) DURING DECODING
Consider that
log Pa (v/m, t((--))) ((())) = log Pu (u/m,, t-(-1)) log Σ Pa (olm,,ttaaa))
(17)
in a manner akin to Appendix E.1 we hypothesize that log Σ (ulm,, t.(111)) may remain nearly
constant. If so, the magnitude of Pw. t.((-1)) can be represented by the term (ulm,, t((-1)))-
Appendix F.1 the term log (ulmm, t,(1-1)) can be interpreted as i.i.d. random variables, hence by invoking the law of large numbers, for any 6, we establish:
Σ (clm, ta-m)) (
lim 1V--000
28 0,
(18)
M
with V representing the vocabulary and μ is the mean.
According to the mean value theorem, a c exists between Σ (u/m,, t.(-11)) and nV\1 such that
log Σ Pullumm, log(11)))
(19)
Σ Pu (ulm,
ta(-))) (v 14V1
Through empirical experimentation
observed that log Σ Pe m,, ta-1)) exceeds 10.5.
Given that the size vocabulary [V] is 50257, it implies e 20.55 > 1/. leading to
Pu t.(11)) - u4/.
log Σ (alm, log 1|ll
Σ
(20)
V
Merging Eq. 18 and Eq. 20 confirms that, with high certainty, log Σ (ulm, t, approxi- mates constant.
To validate our hypothesis, we randomly select 100 t.(--1) as above, and randomly pick 100 m from M. The standard deviation and mean of log Σ Pu (u/m,, t.((-1)) are presented in Table 3 The
deviation of log Σ Pu (r/mm, ((((1)) is higher in Balance-Marking than in Vanilla-Marking, due
the likelihood that log Pu. (u/m, 1)) may not precisely i.i.d for Balance-Marking. Neverthe- less, this modest variation still allows exclude log Σ P. (v|m, t.(--)) for the sake of swifter computation.
We the same experimental settings the experiments shown in Table
17

---

Published as a conference paper at ICLR 2024
Table 3: log (w ty) on human- the average + the standard deviation across (f.(--)):m).
human-written written texts and watermarked texts. The numbers are
Human- Human-Written Texts
Watermarked Texts
Vanilla-Markinn
11.45 = 0.0019
11.45 + 0.0022
Balance-Markingg
11.42 = 0. 1.97
11.41 + 0.2266
F DETAILED ILLUSTRATIONS ABOUT THE PRACTICAL IMPROVEMENTS ON BALANCE-MARKING
The method introduced the beginning of Section 4.2.2 may encounter several obstacles in realistic applications. Thus, we make the following improvements to make it more practical when facing various realistic circumstances:
(1) Omit xrrompt and truncate 1) into fixed length. Considering that the x is usu- ally unavailable and the text receiver might only obtains a segment of the watermarked text during the message decoding phase, it will cause inconsistency between the encoding and decoding phases on calculating the token probabilities for creating Vm,ta-ry- To address this problem, we employ PLLM (v ((=11-ppraaaa)(((11))) to approximate PLEM (1lm(ulxprommp t.(t-1)). That is, we omit xprompt and truncate (.(111) fixed-length ((1-1-bpra/s)(0-11) for consistency during both encoding and decoding.
(2) Use a proxy language model (proxy-LM) LMprary in Eq. Moreover, consid- ering several usage scenarios discussed in Appendix D we broaden the LLM used in PL (1 (e-1-brr (11- into general proxy model denoted as L.ror This model can either be LLM itself when the model company wants the watermarked text only to be decoded by itself, or be another smaller and public language model (c.g.. GPT-2 (Radford et al. (019)) PLLM that allows for quicker computation of P. and enables anyone to decode the embedded message without knowing the specific LLM used in text generation.
(3) Pre-map message space into smaller space for efficient computing. Since computing Vmtta-n for each m during encoding can be much time-consuming when the message space pretty large, we opt first map the entire message space into smaller space as h(m) E MA {1,..., A} by using another hash function h, and then compute the seed s as = = By this way, we only need to run Algorithm mere A times for each t((-1)-
G HYPERPARAMETERS AND HASH SCHEME
In Section 5.1 we opt to use LM Array GPT2 (Rafford et al. 2019 A 100, Tire = 10.
= 0.5 and M {0, 1, I..., 200 - 1} for Balance- Balance-Marking. The reason to set a = 0.5 is to achieve the maximal diversity of V Vm,t.--1 w.r.t. different m. The choice of LMprozz. A, I Lpreffnr fireffi- M aims
to balance efficiency and performance, which is further discussed in Appendix G. to G.4 The hash scheme is detailed in Appendix G.5
G.1 THE IMPACT THE PROXY LANGUAGE MODEL LM A.Mpraay
In our Balance-Marking method, we employ LMprory to generate estimation for PLLMM(V) (v).ttn)) It can be reasonably hypothesized that an enhanced LMprosy could offer a more accurate estimation of Prr.o(v(t.(u1))). thereby leading to superior performance. Experiments de- tailed in Figure support this hypothesis!! [3 However, GPT2-Large illustrates better performance in comparison GPT2-XL, suggesting that the improvement might have certain ceiling.
Here, experiments with 8 (1.0, 1.2, 1.5, 2.0, 3.0). Appendix G.2
G.4 also the ds.
18

---

Published as a conference paper at ICLR 2024
1.00
0.95
Success Rate
0.90
GPT2
X
GPT2-Medium
0.80
GPT2-Large
GPTT2-L.
watermark
3.5 Perplexity
3.0
Figure 3: Illustration of LMprozy' 's impact on watermarking. Larger LMprozy tends to exhibit
improved performance.
Table 4: Growing LMprozy size amplifies the computational cost during both encoding and decod- ing processes.
GPT2
GPT2-Medium
GPT2-Large
GPT2-XL (1.5B)
LM Lppowy
(124M)
(355M)
(774M)
Encoding Time (s)
9.50
11.69
14.08
16.38
Decoding Time (s)
2.97
3.09
3.43
3.53
Unfortunately, as the size of LMprozy increases, there follows a consequential surge in computa- tional cost, clearly demonstrated in Table For practical applications, becomes necessary to establish balance between time expenditure and the quality of the watermark.
Special Case:
LMprony = LLM Table 5 and Table show the efficiency and quality of different LM pronys and the LM Looor LLM case. L.prony LLM has the best quality, but is slower than LM preay = GPT2.
LMpreay
G.2 THE IMPACT OF THE PRE-MAPPING SPACE SIZE A
The purpose of introducing ppper-errrmeter A in Balance- Galance-Marking is to reduce the number of Vm,t. to be computed. A lower value of A results in lower computational expenses during decoding, as shown in Table On the other hand, the cost of encoding remains relatively constant because only single message requires the computation of Vm,t.p-. during encoding.
To explore the impact of A on watermarking quality, we conducted additional experiments as demonstrated in Figure Although a larger A generally leads enhanced performance, there exist notable exceptions, such as when A = 150, where the performance is lower than when A = 100.
To strike balance between performance and computational efficiency, elected A 100
for our main experiments in Section 5.2
G.3 THE IMPACT OF THE TRUNCATION LENGTH Lprefir
The parameter Lprefize which is part of Eq. impacts the quality of the watermark in two significant ways. (1) A longer Eq-11- PLM (u (01-)-1-))m))))0)))))))))))))))) can poten-
19

---

Published as a conference paper at ICLR 2024
Table 5: Efficiency of different proayss and the LMprory LLM case.
GPT2
GPT2-Medium
GPT2-Large
GPT2-XI
LLM self
LMprowy
(124M)
(355M)
(774M)
(1.5B)
(OPT-1.3B)
Encoding Time (s)
9.50
11.69
14.08
16.38
11.05
Decoding Time (s)
2.97
3.09
3.43
3.53
4.07
I.M prozyS and the LM LMpor The watermark success rate of different LM different PPLs.
Table 6:
LLM case under
PPL
3.2
3.35
3.5
GPT2 (I24M)
83.1
91.3
95.3
GPT2-Medium (355M)
84.9
93.2
95.1
GPT2-Large (774M)
88.6
93.8
96.7
GPT2-XL (1-5B)
86.4
93.4
96.0
LLM self (OPT-1.3B)
91.7
94.8
96.9
tially provide superior approximation of PLLM (ul (p|xprompt, f.((-11)-- However, (2) increased tu (p--1-ppeofs):((1-- length will reduce the number of effective tokens in available for encoding and decoding. This reduction occurs because t:L.refie lacks sufficient preceding words form 1:01 which consequently results in their exclusion from encoding and decoding. Jillustrtts the influence of Lirefix- Generally speaking, relatively low Lprefiz value can degrade the watermark quality, while a moderate Lprefin like 10 achieves similar performance to larger values such as or 20.
The time cost for encoding and decoding remains relatively consistent across varying Tireffir val- ues, as demonstrated in Table Interestingly, a larger Lprefiz might lead to a decrease in time cost, aligning with the aforementioned explanation that more extended Lyrefia results in a shorter effective t utilized in the encoding and decoding stages.
G.4 THE IMPACT OF THE MESSAGE SPACE SIZE |M
Increasing the size of IM| under fixed payload information coding rate results in larger number of tokens available for embedding a single message. In text watermarking scenarios, certain parts of the text often exhibit low entropy, thereby challenging the watermark encoding process (Kirchen. let al. 2023ap. However, an increase in the number of tokens mitigates this problem, as it improves the likelihood of having high-entropy sections where the message can be effectively embedded. Moreover, let's consider an example where [M] is relatively small. In such a case, piece of information of 20 bits might need to be divided into four separate chunks of bits each to be encoded. If encoding fails for any of these 5-bit information segments, the encoding of the entire 20-bit information fails. This phenomenon potentially results a significant accumulation of errors.
Figure 6 validates the analysis above by demonstrating a strong correlation between larger |M] and better watermark quality. Here, the experiment utilizes the LLM to generate 210 tokens for encoding and decoding, since when [M| = 27 and the coding rate is 10 tokens per bit, one message corresponds to 70 tokens.
Table shows the time costs of the encoding and decoding processes when [M] increases. The time expenditure for encoding remains relatively stable, since there is only one message for which the calculation of P.. is necessary. Contrastingly, the decoding process experiences noticeable increase in time cost when [M] rises up to 220 Thus, while an increase in [M] steadily improves watermark quality, the size of M can not be increased unlimitedly
Forr instance, if LM equals 240 it becomes exceedingly difficult calculate Pa (t/m') in Eq. 12 for all messages m' M during the decoding process.
20

---

Published as a conference paper at ICLR 2024
Table 7: Investigation into the impact of on watermark efficiency, A larger A value generally results in longer decoding time.
A
25
50
100
150
250
Encoding Time (s)
9.39
9.48
9.50
9.22
9.37
Decoding Time (s)
1.89
2.27
2.97
4.49
6.24
1.00
x
0.95
Success Rate
0.90
A 25 +
A 50
0.80
A 150
A 250
watermark
3.5 Perplexity
3.0
Figure 4: Illustration of A's impact on watermarking quality. A higher tends to have better watermark quality.
G.5 HASH SCHEME
Following the hash implementation in Kirchen. et al. (2023a), in the case both the Vanilla- Marking and Balance-Marking methods, make of the last token in t.(t-1 calculate Mu,, m. 1((11)) in Eq. ( and h(m, t.(1-1)) in Algorithm 2 i.e. l(v, m, t.q-1)) = l(v,, m, 4-1) and h(m, t)(-1)) = humm, 4-1)).
H IMPLEMENTATION OF SUBSTITUTION ATTACKS
For chosen text to be tested on, we arbitrarily pick an unaltered token each time. This token is then masked and the model is asked predict In the event that token's predicted logit surpasses the predicted logit of the original token minus 1.0, we replace the original token with the new one. With a designated substitution ratio a and sentence consisting of tokens, we continue this process until the substituted tokens reach the value of al or after L attempts are made. From empirical analysis, we establish that such replacements result a marginal increase PPL by around 0.1.
SUBSTITUTION ATTACKS WITH A SUBSTITUTION RATIO OF 10%
Figure 7 compares the results under a substitution ratio 5% and 10%. higher substitution results in lower success rate, and the performance of Balance-Marking and Vanilla-Marking becomes closer from to Figure 76 indicating that Substitution Attacks may more hurt to Balance- Marking than Vankiia-Marking. This be attributed to the fact that P., of Balance-Marking relies on t I 1) (see Eq. III while P., of Vanilla-Marking only depends on tu- 1), since we Lire/tz only use the last token of t((1-1) to calculate h (m, t.(t1)) 11) (see Section 5.1 So, Balance-Marken will be affected more when more tokens are substituted.
21

---

Published as a conference paper at ICLR 2024
1.00
0.95
Success Rate
0.90
Lyreta = 5
X
Lyrefa
Lyrefs-
0.80
Langa
Lorgli = 20
watermark
3.5 Perplexity
3.0
Illustration of fire 's impact on watermark quality. A too-low Lprefiz value can de- grade the watermark quality.
Figure 5:
Table 8:
Investigation into the impact of Lirefir on watermark efficiency. Lprefiz has a modest
impact watermark efficiency.
f
5
10
15
20
Encoding Time (s)
9.52
9.03
9.50
9.29
9.10
Decoding Time (s)
3.01
3.05
2.97
2.91
2.86
J RESULTS OF LLAMA- 7B AND LLAMA- 13B AT A CODING RATE OF 5
Besides experiments with a coding rate of 10 in Section 5.4 we also tested the coding rate of 5. The
results shown in Figure g andd 9 Balance-Marking outperforms Vanilla-Marking in all cases.
K ILLUSTRATIVE EXAMPLES OF WATERMARKED TEXTS
In this section, present some examples generated using watermarking approach (Table 10). These examples serve as case study to demonstrate the quality of our watermarking technique. All the generated sentences truncated 200 tokens.
22

---

Published as a conference paper at ICLR 2024
Table Investigation into the impact of [M] on watermark efficiency. The size of M has modest impact watermark efficiency.
M
25
27
2
2
Encoding Time (s)
9.89
10.02
9.83
10.05
Decoding Time (s)
2.37
2.34
2.36
3.13
1.00
0.95
Success Rate
0.90
0.80
+
IM] 2
X 2
IM] 2
IMi= 2
0.50
No watermark
3.5 Perplexity
3.0
Figure 6: Illustration of [M['s impact on watermark quality. A larger M results in better watermark quality.
1.00
1.00
0.95
0.95
X+
Success Rtte
0.90
X
Succes Rale
0.90
0.80
0.80
0.50
0.50
Sdaan-Markkng Vantts-Maarkngg
Bdann-Markiny
Vantia-Markite
vaternark
vateruark
0.00
0.00
3.0
3.5
Perplexity
Perplexity
(a) Substitution Attacks (substitution ratio 5%).
(b) Substitution Attacks (substitution ratio 10%).
Figure 7: The relationship between the success rate after Copy-Paste Attacks Substitution Attacks and the PPL., Balance- Balance-Marking outperforms Vanilla-Marking under both attacks.
23

---

Published as a conference paper at ICLR 2024
1.00
Balance-Markinng Marklng
0.95
No watermark
0.90
Success Rate
0.80
+
x
0.50
0.00
3.5
3.0
Perplexity
Figure 8: Balance-Marking outperforms Vanilla-Marking under LLaMA-7B and coding rate of
tokens per bit).
1.00
Balance-Marking
X
Marklln
0.95
No watermark
0.90
Success Rate
0.80
0.50
0.00
3.5
3.0
Perplexity
Figure 9: Balance-Markinn Marking outperforms Vanilla- Marking under LLaMA-13B and coding rate of
tokens per bit).
24

---

Published as a conference paper at ICLR 2024
Table 10: Examples of generated texts.
Case Study
Text
An EgyptAir jet sent series of signals indicating that smoke had been detected on board before it crashed into the Mediterranean on Thurs- day, France's ' air accident investigation agency said on Saturday. A spokesman for the BEA agency said the signals did not indicate what caused the smoke or fire on board the plane, which plunged into the sea with 66 people on board as it was heading from Paris to Cairo. But they offered the first clues to what unfolded in the moments before the crash. One aviation source said that a fire on board would likely have generated multiple warning signals. while sudden explosion may not have generated any. The army spokesman published pictures on Saturday on official Facebook page of the recovered items, which in- cluded blue debris with EgyptAir markings, seat fabric with designs in the airline's ' colours, and a yellow lifejacket. It was the third blow since October to Egypt's 's travel industry, still reeling from political unrest fol- lowing the 2011 uprising that ousted Hosni Mubarak. lamic State bombing brought down a Russian airliner after it took off from Sharm el-Sheikh airport in late October, killing all 224 people on board, and EgyptAir plane hijacked in March by a ing a fake suicide belt. "These messages do not allow in any way to say what may have caused smoke fire on board the aireraft," said a spokesman for the French BEA agency, which is assisting an official Egyptian
Prompt
suspected Is-
wear-
inquiry into the crash. "We will continue our work until we are able to give you more information." " he added. Egyptian authorities have so far given few details about the crash, saying only that it happened shortly after take-off at 4:18 p.m. (1318 GMT) on Thursday. The flight data recorder and cockpit voice recorder were recovered from the ocean floor on Friday. The black box recorders are expected to handed over to in- vestigators later this month. BEA spokesman Jean-Francois Delfraissy told a news conference on Saturday that the black boxes contained "a great deal of information". He declined to comment were any indications of mechanical failure. He also said the BEA had received reports of any distress calls from the plane before it disap- peared from radar screens. French President Francois Hollande said on Saturday that his thoughts were with the families of those who died in the crash.
No-watermark (OPT-1.3B)
whether there
probe. "We will continue our work until we can be certain about the cause." Egyptian officials said earlier on Saturday that they had found no evidence of foul play the crash. They also said there were no signs of mechanical failure on the Airbus A320, which feet (9,800 meters) when disappeared from radar screens shortly af- ter take-off from Oran, near the Libyan border, at 2:24 p.m. local time (0824 GMT). The wreckage was found some 20 kilometres (12.5 miles) off the Libyan coast Saturday afternoon. It is unclear how long it has been in the water or how deep is. The search is being conducted by a naval patrol vessel, two ships from the Italian navy, one from the United Arab Emirates, one from Greece and a helicopter from the French Navy. The aircraft was carrying 149 passengers and nine crew members, cluding 82 Egyptians, 12 Italians,
flying 31,000
Vanilla-Markinn (OPT-1.3B)
(watermark success rate = 93%)
25

---

Published as a conference paper at ICLR 2024
Table 10 (Continued); Examples of generated texts.
Case Study
Text
inquiry into the crash. "They are just indications that there could have been some kind of activity on the part of the aircraft," he added. He declined to comment further. French President Francois Hollande, who visited the crash site in the southern city of Ismailia with Prime Minister Manuel Valls on Saturday, has called for an international investigation into the crash. Egypt's 's civil aviation authority said in statement Saturday that an initial examination of the black box flight data recorder showed that "there were signs of mechanical problem with the aircraft." It added: "The preliminary findings of the investigation sug- gest that there was technical fault that led to the loss of communica- tion between the aircraft and the ground control centre." CAUGHT BY SURVIVORS Survivors described hearing loud noise and then seeing flames coming out of the rear of the Airbus A320, one of the world's 's most modern planes
Balance-Marking (OPT-1.3B)
(watermark success rate = 95%)
aring a fake suicide belt who demanded to be flown to Cyprus. Egyptian President Abdel Fattah al-Sisi declared three days of national mourn- ing and ordered flags to fly at half-mast until Tuesday. "We will spare no effort to find out the reasons behind this disaster," Prime Minister Sherif Ismail told reporters in Cairo. France's 's foreign minister Jean- Mare Ayrault said he had spoken to his Egyptian counterpart Sameh Shoukry and expressed France's ' "solidarity" with the families of the victims. French President Francois Hollande is due to speak to Sisi later Saturday, according to the Elysee presidential palace. German Chancellor Angela Merkel said she was "deeply shaken" by the news of the crash, adding: "Our thoughts
No-watermark (LLaMA-7B)
with the families
aring fake suicide belt who forced it to land in Cyprus, Egyptian offi- cials say there is no evidence so far of a terrorist attack but investigators are treating the incident as a "criminal act". France's foreign minister Jean-Marc Ayrault, speaking on BFM TV, said he could not rule out terrorist attack. "I can't 't exclude anything at this stage We must re- main very vigilant," he said, adding that French experts were taking part in the investigation. Egyptian security officials told Reuters on Friday that a technical glitch was being investigated as the possible cause of the crash. Another senior Egyptian security official, speaking on con- dition of anonymity, said investigators had found no trace of explosives or traces of chemicals used to make explosive devices on the remains of the Airbus A320. Investigators also found
Vanilla-Marking (LLaMA-7B)
(watermark success rate 96.8%)
aring a fake suicide belt who demanded to be flown to Cyprus. He was overpowered and the plane landed safely in Cyprus. British Foreign Secretary Philip Hammond said he had spoken to Egyptian President Abdel Fattah al-Sisi about the incident. expressed our condolences the families of the victims." he told reporters in Brussels. Hammond de- clined comment when asked whether Britain would review security arrangements at British airports, including London's 's Heathrow, which has direct flights to Egypt's main tourist destinations. The United Na- tions Security Council condemned the "outrageous and cowardly ter- rorist attack" but made no mention of possible retaliatory action against militants in Sinai. The council also urged all states to cooperate with the Egyptian authorities in their efforts to bring perpetrators to justice.
Balance-Marking (LLaMA-77B
(watermark success rate 96.2%)
26

---

looking into all Published as a conference paper at ICLR 2024
Table 10 (Continued);
Examples of generated texts.
Case Study
Text
aring fake suicide belt. Egyptian Prime Minister Sherif Ismail told reporters at the crash site: "There is no indication so far of any terror- ist or sabotage act." He added that investigators possible causes including mechanical failure, human eπrоr and weather conditions. "We are working very hard find the black box," he said, referring to the cockpit voice recorder and flight data recorder that could help explain why the Airbus A320 plummeted from 37,000 feet (1 (11,280 metres) into the sea. French President Francois Hollande, whose coun- try lost 54 citizens the disaster, has ordered an inquiry to carried jointly with Egyptian authorities. The BEA will lead the French side of the probe. The BEA spokesman said the search for the wreckage
No-watermark (LLaMA-13B)
aring suicide belt who forced it to divert to Cyprus. Egyptian Prime Minister Sherif Ismail told reporters on Saturday that investigations were focusing on the possibility of a "terrorist attack" but stressed this could not yet be confirmed. "There no clear indication this time," " he said, adding that Egypt out the cause of the crash. Investigators are combing through the wreck- age of the Airbus (AIR.PA) A320 found 295 km north of the coastal city of Alexandria, searching for the black box flight recorders that will pro- vide crucial clues the cause of the crash. France's 's Bureau d' d'Enquetes et d' Analyses pour la Securite du Trafic Aérien (BEA), which is leading the probe into the crash, said
Vanilla-Marking (LLaMA-13B)
cooperating with other countries to find
(watermark success rate 98%)
aring a fake suicide belt who forced it to divert to Cyprus. He surren- dered and was arrested after giving himself up. The cause of Thursday's 's crash remains unknown, but the focus has turned to the possibility of a technical failure, terrorism given their high level of training. The Airbus A320 is a workhorse of worldwide aviation. It has good safety record, with only two fatal ac- cidents in the past 15 years one of them the Germanwings disaster in the French Alps last year, when co-pilot appears to have intentionally crashed the plane, killing all 150 people on board. The other was an A320 operated by Indonesian budget carrier Adam Air that crashed into the sea off the coast of Sulawesi in 2007,
deliberate act by the pilot co-pilot,
Balance-Marking (LLaMA-13B)
(watermark success rate 97%)
27


Reviews:
[{"review_id": "1nTWN7EGA6", "reviewer": "Reviewer_pLxG", "summary": "In this paper, the authors propose a novel approach to inject multi-bit message information into large language models (LLMs). To inject the watermark, their approach enlarges the gap between the probability that the text is generated under the specific message and other messages. They also propose the balance-marking algorithm to maintain the text quality while injecting the watermark. Experiment results show that CTWL outperforms other baseline approaches in different dimensions.", "questions": "1. How about the text quality of CTWL compared to the previous work, which focuses on injecting information by postprocessing?\n2. Can the authors show some cases to explain how Balance-Marking works but Vanilla-Marking fails?\n3. What is the computation cost of previous studies compared to CTWL?", "limitations": "", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. It is the first work to inject the multi-bit information during the generation process of LLM instead of the postprocessing. The authors propose a novel approach, CTWL, to effectively encode the information while maintaining the text quality. CTWL proposes a Balance-Marking algorithm to consider that some generated tokens should have high model logits and message logits at the same time. Therefore, CTWL can inject the watermark into the generated text with only a slight reduction in the text quality.\n2. Experiment results show that CTWL is robust against the copy-paste attacks and substitution attacks.\n3. CTWL can also work for larger LLM (LLaMA-7/13B).", "weaknesses": "1. It is essential to compare the watermarked text with other approaches to evaluate the effectiveness of the proposed method. In the last paragraph of the related work section, the authors stated, “There are some very concurrent works ... the vocabulary partitions....” Still, there are not any experiments that compare the text quality between CTWL and other approaches. The authors are suggested to compare the BLEU, ROUGE, or other metrics with the previous studies, such as Kirchenbauer et al. (2023a), to show the text quality of CTWL is better than previous work. These experiments can make the results more convincing.\n\n2. It would be better if the author could show some examples of watermarked texts to compare Balance-Marking and Vanilla-Marking. The case study can help the readers know which cases Balance-Marking works but Vanilla-Marking fails. The authors can also compare the encoding time of CTWL with previous studies to show that the encoding time of CTWL is reasonable and practical.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "wE7TgcDGM9", "reviewer": "Reviewer_iBFF", "summary": "This work fill in the blank of watermark injection on LLM generated text on multi-bits information encoding during LLM generation. Prior work use Vanilla-marking to encode multi-bit information, yet they decrease generation quality. This work proposes a balance marking algorithm, the goal is to improve the generation quality, which can be achieved by making the LLM lose close to the original one. This work guides the vocabulary partitioning with a proxy-LM. Results are demonstrated on OPT, LLaMA-7B, 13B.", "questions": "I am new to the field, and I I am still confused after reading twice. Can the author explain this in plain language? \n\nThe goal is to find the prompt that separate watermarked input and non-watermarked input the most right? Not separating machine-generated vs human-generated. As I see Eq 3 is separating both machine-generated text. There is no human written one.\n\nHow does the method encode multibit information? Is the information to be encoded is m? Eq 12 decodes M, yet this formulation is very similar to adversarial attack, why does the method can decode the unique m instead of some adversarial string? Like Zou et al. Universal and Transferable Adversarial Attacks on Aligned Language Models.\n\nDoes Model logit used for guard generation quality?\n\nDoes message logit used to add watermark?\n\nDoes a larger L give better watermark and higher quality?\n\nI understand you want a v which create a large Pw differece for detection, does eq 7,9 simply find the words in a predefined dictionary?\n\nWhat does sigma mean? In plain language, I do not intuitively understand.\n\nHow does Eq 10 encode the quality, Eq 9 inside?\n\nI don't get why you need Eq 11.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. Interesting work on multi-bit injection to LLM while considering the text quality.", "weaknesses": "1. Writing needs improving. There is a lot of math and equation, and less intuition. \n\n2. I do not understand the paper after a few passes, while I am not in the watermarking field, the content should be written so that it can be understood by the general ML audience.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "GhzUUFjd9a", "reviewer": "Reviewer_CxJT", "summary": "This paper first theoretically analyses two main limitations of the Codable Text Watermarking for LLMs (CTWL) field: (1) encode limited information (only 1 bit) ;(2) ignore the quality of generated watermarking texts. Then, authors propose a advanced CTWL method named Balance-Marking. The core idea of our method is to use a proxy language model to split the vocabulary into probability-balanced parts, thereby effectively maintaining the quality of the watermarked text. Extensive experimental results show that our method outperforms the baseline under comprehensive evaluation.", "questions": "(1)\tFrom Eq. (16) in Appendix, I cannot get the same formulation as Eq. (5). As we know, the Lagrange multipliers are commonly added to the constraint item.\n(2)\tAuthors use Proxy-LM to approximate the condition defined by Eq. (9), which inevitably decreases the watermarking text quality. The main performance difference between Proxy-LM and the original LLM in Eq. (5) should be comprehensively discussed, including text quality, success rate, robustness, etc. \n(3)\tAuthors just analyze the trade-off between efficiency and watermark success rate in different proxy-LMs, which makes me question that authors subjectively miss the trade-off between text quality and coding rate of payload information in different proxy-LMs. Moreover, the caption of Figure (2)(a) is inconsistent with the corresponding descriptions.\n(4)\tAuthors do not evaluate the robustness of the proposed method to machine paraphrasing attacks which have been considered in some previous works (“Kirchen. et al., 2023a” and “Kirchen. et al., 2023b”).\n(5)\tIt is analyzed that what are the different experimental results when using different sampling strategies? such as greedy sampling, top-p sampling, etc.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper gives a general mathematical presentation for the watermarked text for LLM.\n2. The proposed method comprehensively consider the trade-off between watermarked text quality and embedded capacity.", "weaknesses": "1. The details of the formulation presentation have some mistakes.\n2. The robustness experiments are not enough.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "bqt3hp6uR7", "reviewer": "Reviewer_qLTC", "summary": "This work proposes a watermarking scheme for encoding multiple bits of information into LLM’s generated text. The scheme is built on a recent LLM watermarking work that encodes only one bit of information [Kirchenbauer, 2023a]. The main contribution of this work is showing a simple way to create balanced “green/red lists” using a public proxy LLM. The scheme performs better than the baseline used in Kirchenbauer [2023a] but suffers a large computation overhead.\n\n---\n\n### Update after rebuttal\n\nI decided to raise my rating from 3 to 6 but decreased my confidence from 4 to 3. I'm also raising the soundness score from 2 to 3. My detailed response can be found at [this comment](https://openreview.net/forum?id=JYu5Flqm9D&noteId=xrgL53bRP8).", "questions": "- Page 4: When I read the last paragraph about using the *mean* of the log probability instead of the *max* overall messages $m' \\in \\mathcal{M}$, I was a little confused. More precisely, I didn’t see why it addresses the mentioned problem about “…solving $\\hat m$ is infeasible because the true $\\hat m$ can only be solved after the whole output t is determined…”; both options still rely on computing $\\log P_w(t_l|m',\\mathbf t_{:(t-1)})$ for all $m'$. What am I missing here?\n- Is there any result on different hash lengths (i.e., how many of the previous tokens are used to compute hash)? This seems like an important experiment since it can affect both the robustness and the text quality (likelihood of repetition).\n- I wonder how the proposed watermark performs if the proxy LLM is the LLM we want to watermark. Perhaps, the watermark’s efficiency can be improved significantly if this is the case, but it does limit a lot of use cases of the watermark as the authors have pointed out.\n- I find it very interesting that larger models achieve a higher success rate (i.e., LLaMA-13B > LLaMA-7B > OPT-1.3B). This seems counterintuitive because larger and better models usually have lower perplexity/entropy so it should be more difficult to watermark them. I wonder if this is a pleasant side effect of the balance marking, but it seems like the success rate under the vanilla marking also improves. I wonder if the authors have any comment on this observation.\n- What does “coding rate” exactly refer to? I assume that it means the number of watermarked tokens divided by the message length in bits, but it is mentioned that the text length is fixed to 200 and 20 bits for the message. So I could be misunderstanding this.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "### Originality\n\nThe formulation leading up to Eq. (5) and (6) is neat in my opinion. It gives a nice interpretation of the “bias” in the logits as a Lagrangian multiplier from the constraint in Eq. (4). I have my doubts (mentioned later) about relying on perplexity as a metric in practice, but this does not take away the theoretical formulation here.\n\nThe idea of using a proxy LLM to help partition the green/red lists (”Balance-Marking”) is a nice idea and is the main contribution of this work. It seems to improve over the default random partition (”Vanilla-Marking”) empirically in all cases.\n\n### Clarity\n\nThe main idea of the scheme and the experimental setup as well as the results are all conveyed clearly and effectively. I had no trouble (as far as I’m aware) following the paper.", "weaknesses": "Despite the aforementioned strengths, the paper has some weaknesses; I will try to list the ones that, I think, are more minor and easier to fix first.\n\n### Perplexity as a proxy for text quality\n\nIt is well-known that repetitive texts can achieve very low perplexity, especially on older and weaker models [1,2]. I think there are better alternatives. First, I would prefer to see the perplexity computed by larger and better models than OPT-2.7B. I understand that Kirchenbauer [2023a] also uses perplexity as their main metric (also by OPT-2.7B) as well, but they take another alternative to show the text quality which is to simply include a good number of samples in the paper for the readers to judge. To be even more convincing, I like the approach taken by Fernandez et al. [2023] which is to use multiple text generation benchmarks that do not rely on perplexity. Other alternatives include using human evaluation or an oracle model (like GPT-3.5/4) for judging the similarity of watermarked vs non-watermarked texts.\n\n### Theoretical bound on the watermarking efficacy\n\nKirchenbauer [2023a] provides a nice theorem (Theorem 4.2) that allows one to theoretically estimate the $p$-value of the watermark as a function of the spiked entropy (as well as other parameters). I believe that the same type of theorem can be derived for the proposed scheme in the multi-bit watermark as well. I believe that this component will significantly strengthen the paper.\n\n### Metrics\n\nIt is mentioned that “success rate” combines both message recovery and watermark detection. First, I would like to confirm that a successful sample only counts if all 20 bits are correctly recovered and the watermark is correctly detected.\n\nMore importantly, I think there are two missing metrics: empirical $p$-value and the notion of FPR or AUC. Since watermarking is a sensitive application and a false positive can be extremely costly, these two metrics are particularly important. The paper briefly mentions a score threshold on $P_w(m|x)$, but it is simply fixed at 1e-5, and I could not find an explanation on how it is computed. This seems to give a “confidence score” on a particular message $m$ but does not look like an appropriate statistic for determining whether text $x$ is watermarked.\n\n### Comparison to steganography\n\nThe paper briefly mentions steganography and some older watermarking works, but the experiments do not compare the proposed scheme to any. I believe that steganography and watermarking share a very similar concept; steganography is also used to convey multiple bits of information which makes it very relevant to this work. I would suggest that the authors try to compare the proposed scheme to steganography on natural language such as [3] and [4] as well as Yoo et al. [2023].\n\n### Computation cost\n\nBalance vocab partitioning comes with a great computation cost for decoding or verifying the watermark. The authors are aware of the limitation and have devised some mechanisms to reduce the overheads (using the second hash function and using a small proxy LLM). However, there are still two concerns:\n\n1. Balance-marking with GPT-2 is twice as expensive as the baseline which I assume is already quite higher than the non-watermarked generation (it will be good to see this number too). This is a huge practical limitation.\n2. More importantly, the fact that the linearly increased cost only yields diminishing improvement in the success rate is concerning (Figure 2a). The success rate seems still too low for practical use even with the heavy overheads.\n\n**Minors/Typos**\n\n- In Eq. (9), it seems like $v$ is missing. So it should be $P_{LLM}(v|...)$  instead of $P_{LLM}(...)$ .\n- I believe that the variant of the copy-paste attack used in the experiment is fairly weak. A real attacker would interleave multiple parts of the non-watermarked text. This further reduces the effective number of watermarked tokens.\n- Paraphrase attack is a common attack in the watermarking literature at this point. This attack is stronger than both the copy-paste and the synonym substitution used in the experiments. It is also easy to carry out in practice so I think it might be a good idea to include it.\n- Section 5.5: in the first paragraph of this section, “$1 - 10^{-5}$” should be “$1 \\times 10^{-5}$” instead.\n\n**References**\n\n- Kirchenbauer [2023a]: https://arxiv.org/abs/2301.10226\n- Fernandez et al. [2023]: https://arxiv.org/abs/2308.00113\n- Yoo et al. [2023]: https://aclanthology.org/2023.acl-long.117/\n- [1] https://arxiv.org/abs/1904.09751\n- [2] https://openreview.net/forum?id=SJeYe0NtvH\n- [3] https://arxiv.org/abs/1909.01496\n- [4] https://arxiv.org/abs/2210.14889", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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:

Decision: Accept (poster)