An Unforgeable Publicly Verifiable Watermark for Large Language Models
Authors: Aiwei Liu
Leyi Pan
Xuming Hu
Shuang Li
Lijie Wen
Irwin King
Philip S. Yu
Venue: ICLR 2024 poster (2024)
Keywords: Watermark
Large Language Models
Model Security
Primary area: societal considerations including fairness, safety, privacy
TL;DR: We propose the first unforgeable publicly verifiable watermark text watermarking algorithm for LLMs using separate networks for generation and detection, achieving high accuracy and security.

Abstract: Recently, text watermarking algorithms for large language models (LLMs) have been proposed to mitigate the potential harms of text generated by LLMs, including fake news and copyright issues. However, current watermark detection algorithms require the secret key used in the watermark generation process, making them susceptible to security breaches and counterfeiting during public detection.
To address this limitation, we propose an unforgeable publicly verifiable watermark algorithm named UPV that uses two different neural networks for watermark generation and detection, instead of using the same key at both stages. Meanwhile, the token embedding parameters are shared between the generation and detection networks, which makes the detection network achieve a high accuracy very efficiently.
Experiments demonstrate that our algorithm attains high detection accuracy and computational efficiency through neural networks. Subsequent analysis confirms the high complexity involved in forging the watermark from the detection network. Our code is available at https://github.com/THU-BPM/unforgeable_watermark

Published as a conference paper at ICLR 2024
AN UNFORGEABLE PUBLICLY VERIFIABLE WATER- MARK FOR LARGE LANGUAGE MODELS
Aiwei Liu', Leyi Pan', Xuming Hu?, Shu'an ang Li',
Lijie Wen' ;
Irwin King", Philip S. Yu²
'Tsinghua University "The Chinese University of Hong Kong
The Hong Kong University of Science and Technology (Guangzhou)
Universityy of Illinois Chicago
1 uaw20@ma 11s 8. s tsinngua edu. cn, wen1 int.sinnhaaeddu.ooo king@cse.culi mrokk.edu hk
ABSTRACT
Recently, text watermarking algorithmss for large language models (LLMs) have been proposed to mitigate the potential harms of text generated by LLMs, including fake news and copyright issues. However, current watermark detection algorithms require the secret key used in the watermark gencration process, making them susceptible to security breaches and counterfeiting during public detection. To address this limitation, we propose an unforgeable publicly verifiable watermark algorithm named UPV that uses two different neural networks for watermark gen- eration and detection, instead of using the same key at both stages. Meanwhile, the token embedding parameters are shared between the generation and detection net- works, which makes the detection network achieve a high accuracy very efficiently. Experiments demonstrate that our algorithm attains high detection accuracy and computational efficiency through neural networks. Subsequent analysis confirms the high complexity involved in forging the watermark from the detection network. Our code is available at https://gituub.com/ http://coonnouuuu//uu/reeeeellee watermark
INTRODUCTION
With the development of current large language models (LLMs), many LLMs, like GPT-4 (OpenAI 2023) and Claude, could rapidly generate human-like texts. This has led to numerous risks, such as the generation of vast amount of false information on the Internet (Pan et al., 2023), and the infringement of copyrights of creative works (Chen et al., 2023). Therefore, texts generated by LLMs need to be detected and tagged.
At present, some watermarking algorithms for LLM have proved successful making machine- generated texts detectable by adding implicit features during the text generation process that difficult for humans to discover but easily detected by the specially designed method (Christ et al. 2023 Kirchenbauer al. 2023). The current watermark algorithms for large models utilize shared key during the generation and detection of watermarks. They work well when the detection access is restricted to the watermark owner only. However, in many situations, when third-party watermark detection is required, the exposure of the shared key would enable others to forge the watermark. Therefore, preventing the watermark forge in the public detection setting, of great importance.
In this work, we propose UPV, the first unforgeable publicly verifiable watermarking algorithm for LLMs. Our approach adopts the commonly used watermark schema, which embeds small watermark signals into LLM's logits during generation Kirchenbauer et al.) (2023); Zhao et al. (2023). The main difference is that our algorithms could detect the watermark without the generation key. To conceal the details of the watermark in the detection process, we propose using two separate neural networks for watermark generation and detection, rather than relying on the same secret key for both stages. The unforgeability of our algorithm stems from computational asymmetry: constructing watermark generation network from a watermark detection network is notably more complex than To enhance the accuracy of the detection network while alleviating
the reverse process (Section 4.5
Corresponning author

---

Published as a conference paper at ICLR 2024
Watermarked L.L
Watermark Generator
Watermark Detector
Y
Top K Legits
Watcrarked
rea Red telonte
Watermarked
Watermarked
Watermorl
LSTM Network
Language Model
Embedding
Caudidate Token
Tokens local windony
Logits
telees In debected
Figure I: The left segment outlines the token logits generation process of the watermarked language model. Initially, the origin model generates token logits; these are then refined by the watermark generator to increase the probability of watermarked tokens (denoted in green). Operating within a predefined token window, this generator network (center) determines the final token's 's watermark label. The watermark detector (right) evaluates the entire text ascertain watermark presence.
the complexity of the training process, we have shared the token embedding parameters between the detector and the generator. This provides some prior information to the detector while maintaining unforgeable. Specifically, our watermark generator takes a window of w tokens as input and predicts the watermark signals of the last token. The text detector directly takes all tokens from the text as input and outputs whether the complete text contains the watermark.
In experiments, the watermark detection algorithm exhibits detection performance of nearly 99% F1 score, almost identical to the key-based watermark algorithm, which is our theoretical upper bound. Notably, the computational burden of watermark generation and detection network is minimal, especially when compared to large language models, due to its significantly lower parameter count. Furthermore, we have demonstrated the difficulty of cracking the watermarking rules to forge watermark through detailed experiments. We find that both attacking strategies, employing detector construct training data for the generator training and using word frequency analysis, yield exceedingly low rates of successful decryption in scenarios with not exceptionally small window size.
The main contributions of this work can be summarized follows:
Introduction of a novel unforgeable publicly verifiable algorithm named UPV that employs separate neural networks for watermark generation and detection.
Utilization of shared token embedding between the watermark generation and detection networks, thereby improving the efficiency of training the detector.
Through empirical analysis. we have demonstrated that our watermarking algorithm is highly resistant to attacks trying forge the watermark.
RELATED WORK
LLMs have been successfully applied to many tasks (Liu et al. 2023a Hu et al. 2023b). However, the potential for misuse of LLMs still remains. To miligate these misuses, strategies such red teaming (Liu et al. 2022) and safety alignment (Ji et al. 2023 can be employed. Nonetheless, not all forms of misuse can be addressed through these methods, making it imperative detect and track text generated by L.Mss. Currently, there are two primary methods for identifying I...-produced text: text watermarking and classifier- based detection.
Classifier-based approaches typically fine-tune LLMs like GPT-2 (Radford et al. 2019). BART Lewis ct al. 2019), and RoBERTa (Liu et al. 1907) for binary text classification (Zhan et al. 2023 Mireshghallah et al. 2023). Some methods incorporate language model features (Su et al. 2023 or adversarial training (Hu et al. 2023a). However, the fundamental detectability of machine generated text remains open question. Some argue that with sufficient data collection, tigh-performing detectors are achievable (Chakraborty et al.) 2023). Sadasivan et al. (2023) contend that as LLMs become advanced, the performance gap between detectors and random classifiers may diminish.
2

---

Published as a conference paper at ICLR 2024
Compared to the classifier- baasdffie-bbedd methods, text watermarking (Liu et al. 2023c) is more explainable. There are typically two categories of text watermarking methods. The first is to add a watermark to the existing text. For example, Abdelnabi & Fritz (202I) designed data- mata-hiding network to embed watermark information in the text, and utilized a data-revealing network to recover the embedded information. Yoo et al. (023) injected the watermark by substituting some words in the text. However, adding a watermark to the existing text struggles to keep the semantics of the text unchanged which limits its use in real-world scenarios. Another line of methods is injecting the watermark during the text decoding process. Christ et al. (2023) used a pre-peeeeeeeeee rreeselected value sequence to sample the tokens and subsequently detected the watermark by observing the correlation between the preset pseudorandom numbers and the generated tokens. The work of KKuditipudi et al. (2023) introduced Levenshtein distance to measure the distance between generated text and random number sequences, improving the robustness of watermarks. KKirhhnbbaeer et al. (2023) divided the vocabulary into red and green lists and preferred to generate tokens from the green list. Zhao et al. (2023) enhanced the robustness of this approach by using global fixed red-green vocabulary. [iu et al. (2023b) achieve a balance between robustness and security through semantic invariant hashing. Lee et al. (2023) designed watermarking method for low-entropy code generation scenarios. However, the above methods require the key from the watermark generation phase during the detection, which exposes the watermark's key when made accessible for public detection. In this work, we propose the first unforgeable publicly verifiable watermark to alleviate these issues.
PROBLEM DEFINITION
Language Model: A language model, denoted by M, is fundamentally a function for predicting the next token in sequence. M takes an input sequence probability distribution Ps, over a vocabulary set V. Formally, we have Pn = M(zon-1)). The next token selected from the distribution, either via sampling or other methods.
[ro, ........ In- 1] and produces the
Watermarking Algorithm comprises watermark generation and watermark detection. Watermark Generation: This can be seen as subtle modification to a language model's probability dis- tribution. If M denotes a watermarked language model, the token prediction probability ex- pressed as: Pn == (( Wate rma rk Detecti on: This algorithm takes text sequence [To, ................................ [m] and determines the presence of watermark. There's 's one-to-one correspondence between the watermark detection model, denoted as D, and the watermarked language model M.
Unforgeable Publicly Verifiable Watermark: If a watermarking algorithm is publicly verifiable, it implies that the watermark detector is accessible to the public or third parties, allowing everyone to acquire details of the watermark detection algorithm. When a publicly verifiable watermark algorithm also satisfies the characteristic of being unforgeable, it signifies that even if the public gains access to the watermark detector, it remains challenging to get the watermark generation method (the watermark key), thereby hindering the ability to forge the watermark.
For potential attackers, there are two primary attack scenarios. The first involves attempts to modify watermarked text, employing techniques such as text rewriting or synonym substitution to eliminate the watermark. This attack assumes that the attacker does not have access to the detector or similar models, as such access would facilitate easy removal through multiple trials. If user can consistently remove the watermark (over 90%) using a rewriting algorithm, then the watermark considered broken. The second scenario arises when the attacker has access to the detector and attempts to decipher the watermark's 's generation rule for forgery purposes. In this situation, the attacker can access the detector and make unlimited queries. Defenders can only ensure security by designing unforgeable watermark algorithms to prevent forgery. If attacker gains enough understanding of the watermark generation rule (over a threshold) to easily forge watermarked text, the watermark is considered "broken". In the context of watermarking, two texts different meaning they are labeled differently (watermarked or not) or convey different meanings.
Threat Model:
PROPOSED METHOD
This section provides a detailed description of our unforgeable publicly verifiable watermark algo- rithm. The watermarked LLM decoding step is first explained (Section 4.T). We then detail the
3

---

Published as a conference paper at ICLR 2024
watermark generation network (Section 4.2) and principles of watermark detection (Section 4.3 and Section 4.4) Finally, we analyze the unforeability of the algorithm (Section 4.5)
4.1 WATERMARKED LARGE LANGUAGE MODEL
Algorithm Srrithhmmesseee describes how to generate watermarked text with a target language model M. Given an input sequence [rp..... In-1l, .M produces logit scores Pv. for the next token. Afterwards, the candidate tokens will be processed by the watermark generation network W produce the watermarked token set G. Logit scores for tokens in G are incremented by 8, while others remain unchanged, forming the logits of the modified model M. As is shown in Equation |
Not all tokens in the logits are labeled during each generation step. In the case of top-K sampling, only the highest-ranking K tokens are tagged. During beam search with a beam size of B, tokens are labeled only their scores surpass the Bth highest score Sg by a margin of 6, formally defined as {2, EV
(()) SB - 67. A more detailed analysis is provided in the appendix H
Algorithm Watermark Generation Step
1:
Input: Watermark generation network: W. Fixed integer: K. Watermark strength: 5. Language model: M. Previously generated text sequence: 2 = [Z....., In-1]. Local window size: w.
2: Compute logits Pa of token I, given 20:n-1: Pn M ((xaam11).
3: Extract the top-K tokens from logits, denoting them as x top)(Px).
4: Initialize sequence matrix S where each corresponds to the sequence [In 1............................... 2611 for every xn E xx
5: Calculate the watermark result W(S), where each entry v; is O (t) is not watermarked) (wn is watermarked).
6: Generate the watermarked token set G containing items with value in G {ax rr = 1).
7: Construct augmented language model M such that for input sequence [ ........ ................................ I the adjusted logits are:
M( ((0 = M(( + 81 (i G),
where 1(-) an indicator function: it returns if E G and 0 otherwise.
8: Output: Modified language model M
4.2 WATERMARK GENERATION NETWORK
The watermark generation network's architecture is depicted in the middle part of Figure I The shared embedding network, denoted as E, first generates the embedding for each input token. Subsequently, embeddings from a local window w are concatenated and processed by the fully connected classification network to ascertain if the last token in the watermarked token set. We use FFN to denote the fully connected network and the process could be represented as follows:
W(2n- Im) = FFN(E(Zn-o++1) + E(In- @ O E(Ix)).
(2)
The embedding network accepts the binary representation of token IDs as input. The required number of encoding bits is contingent upon the vocabulary size. For instance, GPT2 Radford et al. (2019) has a vocabulary size [V] of 50,257, requiring 16 bits for its binary representation.
For effective watermark detection, it's imperative that the proportion of watermarked tokens generated by the generation network remains invariant. Specifically, for any local window [xn-w+1,-.. x,), the probability that x, belongs to the watermarked token set should consistently be
v[mn-w+1.... In .),
2n-1, = 1) = 7
(3)
where the y has the same meaning as the green list ratio in the previous key-based watermark algorithms Kirchenbauer al. (2023) Zhao al. (2023).
Due to the inherent complexity of neural networks, maintaining a static ratio via predefined parameters
is non-trivial. We address this challenge by curating training dataset maintaining the precise
4

---

Published as a conference paper at ICLR 2024
proportion y. This approach guarantees expected watermarked token ratio y with standard deviation o. Section 4.3 shows the minimal influence of a on the detection. More training details of the watermark generation network could be seen in the appendi C
4.3 WATERMARK DETECTION
In this section, we introduce how to detect a given watermark using the z-value test. Given vocabulary partitioned into watermarked and non-watermarked tokens based fixed ratio, 7, the expected number of tokens from the watermarked set in a standard text of length T' is >T, with variance of y(1 - 7).' Using the z-value test method as proposed by Kirchenbauer et al. (2023), we reject the null hypothesis and detect the watermark in text if the 7-score below surpasses threshold:
z (Isla - /T)/ VT>(1-1)))))
However, as discussed previously, our watermark generation network does not ensure constant ratio y,. Instead, ratio y is achieved with an expected value y and standard deviation a. This necessitates modification of the earlier formula. While the expected count of the green tokens remains yT, the variance must be adjusted. The updated variance can be expressed as:
Var(yT)> = E[V ar h)) + Var (ar(E(TTh) = 7(1 7)T + o
(5)
and the new z-score could be calculated as follows:
(|s|a 11/
(6)
Since our standard deviation a is very small in practice, the increase in variance, TTT, is also quite minimal. In the process subsequent experiments, we will initially estimate the variance of the generation network and then include the variance during the z-score test calculation.
4.4 WATERMARK DETECTION NETWORK
The z-value test effectively detects watermarks in text but requires knowing the label (watermarked or not) of each token during detection. This allows the watermark to be more easily removed forged. To address this, we propose a watermark detection neural network that accepts only the text sequence as input and outputs whether it contains a watermark.
The detailed structure of our watermark detection network is illustrated in the right part of Figure I The input the entire network is the ID sequence of all tokens in the target sentence, where an output of indicates the presence of watermark in the entire sentence, and 0 signifies its absence.
Specifically, all tokens first pass through shared embedding network. Notably, the parameters of this token embedding are consistent with those of the watermark generation network and remain frozen during subsequent training. The motivation behind this novel approach is the shared embedding could give prior information to the detection networks and substantially reduce the difficulty of training.
The token embeddings are then combined and fed into an LSTM network Hochreiter Schmidhuber (1997) for binary classification of whether the text contains a watermark:
D(x) (STM(E(()) @ E(()) @ ... B(xT)).
The watermark detection network functions as a diseriminator, judging the z-value of input text exceeds a threshold. We construct the training data using equation 6 with a predefined threshold z.
Notably, the input of the detection network need not be meaningful text; any token ID list suffices. Thus, the randomly generated ID sequence as training data theoretically avoids out-of-domain issues.
To impede attackers from inferring watermarking rules, we treat the text as a cyclic document, labeling initial tokens based on trailing ones. This results in random labels for the first few tokens, minimizing their effect on detection given the small window relative to full text length. Examples of the cyclic document and training details of the detection network are shown in the appendix F and C
4.5 ANALYSIS OF THE UNFORGEABILITY
To further demonstrate the unforgeability of our watermarking algorithm, this section provides a detailed analysis of the difficulty cracking the watermark generation method.
5

---

Published as a conference paper at ICLR 2024
Table 1: Empirical detection result for watermark detection using top-K sampling and beam search.
Each row is averaged over ~ 500 generated sequences of length T = 200 + 5. The table compares our proposed network-based watermark detection method and the key-based watermark detection that directly calculates the z-score. The hyperparameters are uniformly set as 5 = 2.0, y = 0.5.
C4
DBPEDIA CLASS
Methods / Dataset
FPR
FNR
F1
FPR
FNR
F1
Key-hased Network-based (UPV)
0.2
0.4
99.7
0.2
0.0
99.9
Top-K Sample
0.2
1.1
99.3
0.6
1.4
99.0
GPT2
Key-based Network-hased (UPV)
0.2
99.8
0.0
Beam Scarch
0.7
99.6
0.1
0.8
99.6
Key-based
0.0
0.4
99.8
0.0
0.6
99.7
Top-K Sample
Network-based
0.2
4.7
97.5
0.8
3.1
98.0
OPT 1.3B
Beam Search
Key-hased Network- (UPV)
0.0
0.0
100.0
0.0
0.0
100.0
0.2
0.6
99.6
0.8
0.4
99.4
Key-based Network- based (UPV)
1.0
99.5
3.0
Top-K Sample
3.2
98.2
3.7
LLaMA 7B
Key-based Network- (UPV)
0.0
0.0
100.0
0.0
0.6
99.7
Beam Scarch
0.1
0.4
99.8
0.5
0.9
99.3
In the process of watermark generation, we use watermark generation networks to produce labels for training watermark detection networks. This process is straightforward. For given text æ, the gold label of the detection network 'D is a simple function (denoted as f) of watermark generation network:
D(x)= = (V(x W(1 W(xT-u:))
(8)
Conversely, utilizing the watermark detection network to produce training labels for the watermark generation network presents substantial challenges. Given the input text x and the detection network D, it is not straightforward to obtain a specific label W(x The inference only possible with respect to the relationships among multiple labels. This necessitates accounting for output interdependencies within the generation network, as shown below with a more complex function g:
W(x:stw) g (xx, D, (W(()s++))b)d)
The uncertainty and complex dependencies between labels make training watermark generation networks from watermark detection networks extremely difficult. Details about the complex nature of this process will be expanded upon in the experiment section. This characteristic adequately satisfies computational asymmetry, which is vital for unforgeability-prese cryptography. The theoretical training difficulty and computational asymmetry inherent in training the generation network from the detection network robustly safeguard the unforgeability.
fields like asymmetric
In addition using the watermark detection network train the generation network, one can infer the watermark rules by analyzing word frequency differences across large amounts of text, i.e. the spoofing attack mentioned by (adasivan al. (2023). The principle that when using watermarking method with a window size w. the frequency of the wth token with fixed previous w - 1 tokens will differ from that in unwatermarked text. However, this approach is largely ineffective when the window size is not particularly small, as will be detailed in the experiments section.
5
EXPERIMENT
5.1 EXPERIMENT SETUP
Language Model and Dataset: We utlize three language models GPT-2(Radfori et al. 2019).
DPT-1.3B et al. 2022), and LLaMA-7B (Too-on et al.) 2023 to generate watermarked text. Consistent with previous works, we employ two decoding methods: Top-K K sampling and Beam search, to produce the watermarked text. We select the C4(Raffel al. 2020) and Dbpedia Class (Raffel et al.) (020) datasets and use the first 30 words of each text as the prompt. For each prompt, the language model would generate the next 200 5 tokens.

---

Published as a conference paper at ICLR 2024
Table 2: The table presents an ablation study the shared layer, contrasting the effects of using shared layer (w. shared layer), not using a shared layer (w.o. shared layer), and with shared layer after fine-tuning (w. ft shared layer).
C4
DBPEDIA CLASS
Methods Datasets
FPR
FNR
F1
FPR
FNR
F1
w. shared-layers
0.2
1.1
99.3
1.4
99.0
GPT2
w/o shared-layers
0.0
99.76
0.5
0.9
68.1
47.5
w ft shared-layers
0.2
16.2
90.9
0.6
13.4
92.5
w. shared-layers
0.2
4.7
97.5
0.8
3.1
98.0
OPT 1.3B
w/o shared-layers
0.0
100.0
0.0
0.0
99.4
1.3
shared-layers
0.0
22.3
87.3
0.2
25.9
84.8
w. shared-layers
0.4
3.2
98.2
1.2
3.7
97.5
LLaMA 7B
w/o shared-layers
1.2
81.0
31.4
42.0
11.4
76.9
w shared-layers
0.2
21.3
87.8
1.0
31.3
79.6
Evaluation: The objective in evaluating watermarking algorithms is to distinguish human-written text from language model-generated text. Specifically, select 500 texts from the dataset as human text and 500 language moder--genertte texts for evaluating binary classification metrics. We thoroughly document the false positive rate, false negative rate and Fl score. About baselines, use key-based method as detecting watermark by calculating the z-score with the generation network, and
detection denote our method.
prper-parameter:: The default hyperparameters are configured as follows: watermark token ratio of 0.5, window size w of 5, five token embedding layers, and = 2 for the generator. The detector comprises two LSTM layers well as the same token embedding layers. For decoding, Top-K employs K = 20 and Beam Search utilizes a beam width of 8. Both networks adopt a learning rate of 0.01, optimized via the Adam optimizer (Kingma & Ba 2014). Due to the varying sensitivity of language models to the watermark, for case of comparison, the detection z-score thresholds for GPT-2, OPT 1.3B, and LLaMA 7B set to 1, and 3, respectively.
5.2
MAIN RESULTS
Table I shows a comparison of detection efficacy between our network- -baed watermarking detection algorithm and current key-based watermarking. The key-based baseline watermarking detection algorithm is the method of KKirhhenbaerr et al. (2023), which directly computes the number of watermarked (green) tokens and then calculates the z-score.
As illustrated in Table I similar to the key-based watermarking detection algorithm, our network- based watermarking detection algorithm also scarcely produces false positive results (0.1% 1% and 0.4% on average), meaning that human text is almost never mistakenly identified as watermarked text. Moreover, in most scenarios, the false negative probability is only marginally higher than the key- based watermarking detection algorithm by average of 1.2%. Considering that the performance of the key-based watermarking detection algorithm represents the strict upper bound of our method, this is indeed an outstanding result. We also find that the performance trends of algorithm across different settings (language models, datasets) are similar to the key-based watermarking detection algorithm. This demonstrates the general applicability of our network-based watermarking detection method without using watermark generation rules. We will analyze the difficulty of inferring watermark generation details from the detector subsequent analyses.
5.3 ANALYSIS OF SHARED EMBEDDING
To demonstrate the necessity of shared embedding layers between the generation network and detection network, we compared the watermark detection performance under three settings in Table 2] without using shared embedding layers, using shared embedding layers but not fine-tuning them during detection network training, and using shared embedding layers while also fine-tuning them during detection network training. All the experiments employ top-K sampling.
7

---

Published as a conference paper at ICLR 2024
Detection Attack Window size
Detection PPL value
1.0
7.50
My lucoll Deteriee
0.9
Dract Crackin
Roreme beinse IN perses))
F1 score
0.8-
6.75
6.50
0.7
6.25
0.6-
0.6
6.00
5.75
FLxcon
0.3
PPL 5.50
Window
(b)
Figure 2: The left figure shows the detection success rate of our unforgeable publicly verifiable watermark and the success rate of two attack algorithms on the watermark under different window sizes. The right figure shows how watermark detection Fl score and generated text quality (measured by text perplexity) change as 5 increases.
Without the shared layer, Fl score decreases dramatically, by 72.0% on average. This renders the detection algorithm nearly useless. Furthermore, fine-tuning the shared embedding layers decreases Fl score by 11.1%. These results demonstrate using the generator's s token embedding layers without further fine-tuning is optimal for the detection network.
5.4 UNFORGEABILITY ANALYSIS
It is crucial that the details of watermark generation remain difficult to infer. Thus, we conducted an analysis of the detection Fl score of potential attack methods aimed at discerning the watermark generation rules. Specifically, we examined two attack methods mentioned in Section 4.5 reverse training of the generation network from the detection network, and direct cracking of the watermark based on token frequency. For the reverse training generation network from the detection network attack method, the retrained generation network also shares parameters in the token embedding layers of the detection network without further fine-tuning. The setting w w_ft. params indicates that the token embedding parameters have been fine-tuned during the training the detection network or and the setting w fixed. params indicates the parameters are the same as the origin generation network.
From Figure 2 a),, our watermark detection algorithm can maintain a relatively stable detection score the window size increases. However, the effectiveness of the attack method based on reverse training decreases gradually as the window size increases until it drops to the minimum value of 0.5 (random guess). This strongly validates our explanation in Section 4.5 that training the generator with the detector is a computational asymmetrical inverse process. At the same time, the cracking method directly based word frequency is completely useless when the window size is particularly small. This experiment demonstrates that our method has good unforgeable properties. More details about the attack algorithms could be seen in the appendix
5.5 HYPER- PARAMETER AND ERROR ANALYSIS
In investigating the efficacy of our unforgeable publicly verifiable watermark algorithm, we focus on the influence the å values on the detection F1 score and the text quality. Text quality assessed by perplexity using the LLaMA 13B (Touvron al.] 2023). Figure 2 (b) demonstrates that d increases, so does the Fl score of the detection network; however, this comes at the cost of an increased perplexity (PPL) value in the generated text. After considering these trade-offs. selected a value of 2 to optimize the detection FI score without severely compromising text quality.
To analyze the eтror cases, present the z-score distributions of human and watermarked texts, as well as the algorithm's 's detection Fl score at different z-score ranges in Figure a). These results are generated by I.LMMA7B the C4 dataset. Figure 3 () reveals that the human and watermarked
8

---

Published as a conference paper at ICLR 2024
( Training Step
0.7
700
0.6
600
Naa hamis leal
Nar
00.8
0.5-
0.8
Nums
-0.6
0.4-
400
0.7
300
-0.4
0.6
0.5
100
0.4
7.5
10.0
150
200
Z-score
(a)
(b)
The left figure is an error analysis, illustrating the detection FI score for data within various ranges of z-scores. The right figure depicts the changes in loss and the mean proportion (#: standard deviation) of watermarked tokens generated by the watermark generator network during training.
Figure 3:
texts exhibit nearly normal distributions around -1 and 9, respectively. The detection F1 score of the our watermark algorithm drops significantly around the z-score threshold but approaches 100% in other ranges. This indicates our algorithm is highly reliable for inputs with definite labels.
5.6 WATERMARK GENERATION NETWORK ANALYSIS
It is critical that the watermark generation network produce a stable watermarked token ratio, as the modified z-score calculation (equation 6) depends on the variance of this ratio. Therefore, in this section, we calculate the actual mean and variance of the watermark labels.
Specifically, we train the watermark generation network using 5000 data items with strictly 0.5 ratio of watermarked tokens. As seen in figure 3 (b), the ratio approaches the target value 0.5 as the training loss decreases, and its standard deviation also diminishes. The standard deviation can be controlled within 0.02, corresponding to variance of less than de 4. According to equation R could be nearly neglected the final z-value calculation.
5.7 TIME COMPLEXITY ANALYSIS
Our watermark generation process requires additional network, potentially introducing putational overhead. However, our watermark generation network contains only 43k parameters, negligible compared the 124M 7B parameters in GPT2, OPT-1.3B, and LLaMA-7B models. Empirically, decoding a token takes 30ms in GPT2 on single Tesla V100 GPU, and our watermark- ing adds only Ims on average, even less for larger models. Thus, our watermark generation algorithm adds minimal computational burden. In prior experiments, we selected relatively small top-K K values. However, given that networks can perform batch computations, even large K values do not affect computation time. A detailed analysis will be provided in the appendix
CONCLUSION
In this paper, we propose the first unforgeable publicly verifiable watermarking algorithm for large language models. Unlike previous detection methods that require the watermark key for detection. our method uses separate detection neural network to detect the watermark. In experiments, we demonstrate the difficulty inferring the watermarking method from the detection network, while our method achieves similar Fl scores to direct z-score computation. In the appendix B we demonstrate that our watermarking algorithm remains robust against a single instance text rewriting. However, its robustness in the face of multiple rewrites This aspect falls beyond the scope of our current work, and future research could focus on enhancing the robustness of the unforgeable publicly verifiable watermarking algorithm.
intense attack scenarios remains unexplored.

---

Published as a conference paper at ICLR 2024
7 ACKNOWLEDGMENTS
This work is supported by the National Nature Science Foundation of China (No. 62021002), Tsinghua BNRist, and the Beijing Key Laboratory of Industrial Bigdata System and Application. Additionally, it receives support from the Beijing Natural Science Foundation under grant number QY23117. Moreover, the work is partially supported by grant from the Research Grants Council of the Hong Kong Special Administrative Region, China (CUHK 14222922, RGC GRF No. 2151185). This work is also supported in part by NSF under grant II1-2106558.
At the same time, we would like to express our gratitude to the anonymous ICLR reviewers PMgN, CjAu, seaW, and kypk, as well as the Area Chair vQPR, for their valuable feedback, which played significant role in improving the quality of our paper. We especially appreciate reviewer CjAu, who helped us clarify the definition of our methods and provided many valuable suggestions for revisions, greatly enhancing the quality of our 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.
Souradip Chakraborty, Amrit Singh Bedi, Sicheng Zhu, Bang An, Dinesh Manocha, and Furong Huang. On the possibilities of ai-generated text detection. arXiv preprint arXiv:2304.04736, 2023.
Chen Chen, Jie Fu, and Lingjunn Lyu. A pathway towards responsible ai generated content. arXiv preprint arXiv:2303.nm 01355, 2023.
Miranda Christ, Sam Gunn, and Or Zamir. Undetectable watermarks for language models. arXiv preprint arXiv:2306.09/94 2023.
Marta R Costa-jussă, James Cross, Onur Çelebi, Maha Elbayad, Kenneth Heafield, Kevin Heffernan, Elahe Kalbassi, Janice Lam, Daniel Licht, Jean Maillard, al. No language left behind: Scaling human-centered machine translation. arXiv preprint arXiv:2207.04672. 2022.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9(8): 1735-1780, 1997.
Xiaomeng Hu, Pin- Yu Chen, and Tsung- Yi Ho. Radar: Robust ai-text detection via adversarial learning. arXiv preprint wiXiv:2307.03855 2023a.
Xuming Hu, Junzhe Chen, Xiaochuan Li, Yufei Guo, Lijie Wen, Philip S Yu, and Zhijiang Guo. Do large language models know about facts? arXiv preprint arXiv:2310.05117. 2023b.
Jiaming Ji, Tianyi Qiu, Boyuan Chen, Borong Zhang, Hantao Lou, Kaile Wang, Yawen Duan, Zhonghao He, Jiayi Zhou, Zhaowei Zhang, et al. Ai alignment: A comprehensive survey, arXiv preprint arXiv:2310. 2.t.::231..1952.22 2023.
Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint 14Xiv:14/2.69980 2014.
John Kirchenbauer, Jonas Geiping, Yuxin Wen, Jonathan Katz, Ian Miers, and Tom Goldstein. A watermark for large language models. arXiv preprint arXiv:2301. 10226, 2023.
Rohith Kuditipudi, John Thickstun, Tatsunori Hashimoto, and Percy Liang. Robust distortion-free watermarks for language models. arXiv preprint wxXiv:2307.1559. 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 preprint arXiv:2305.15066) 2023.
Mike Lewis, Yinhan Liu, Naman Goyal, Marjan Ghazvininejad, Abdelrahman Mohamed, Omer Levy, Ves Stoyanov, and Luke Zettlemoyer. Bart: Denoising sequence-to to--ncee-t--suueneee pre-training for natural language generation, translation, and comprehension. arXiv preprint 11Xiv:1910.13400 2019.
10

---

Published as a conference paper at ICLR 2024
Aiwei Liu, Honghai Yu, Xuming Hu, Shu' ang Li, Li Lin, Fukun Ma, Yawen Yang, and Lijie Wen. Character-level white-box adversarial attacks against transformers via attachable subwords substitution. arXiv preprint arXhv:2210.17000 2022.
Aiwei Liu, Xuming Hu, Lijie Wen, and Philip S Yu. A comprehensive evaluation of chatgpt's zero-shot text-to-sql capability. arXiv e-prints, pp. arXiv-2303, 2023a.
Aiwei Liu, Leyi Pan, Xuming Hu, Shiao Meng, and Lijie Wen. A semantic invariant robust watermark for large language models. arXiv preprint arXiv:2310.06356, 2023b.
Aiwei Liu, Leyi Pan, Yijian Lu, Jingjing Li, Xuming Hu, Lijie Wen, Irwin King, and Philip S Yu. A survey of text watermarking in the era of large language models. arXiv preprint arXiv:23/2.07913, 2023c.
Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. Roberta: a robustly optimized bert pretraining approach (2019). arXiv preprint arXiv:1907, 1692, 364, 1907.
Matouš Macháček and Ondřej Bojar. Results of the wmt14 metrics shared task. In Proceedings of the Ninth Workshop on Statistical Machine Translation, pp. 293-301, 2014.
Fatemehsadat Mireshghallah, Justus Mattern, Sicun Gao, Reza Shokri, and Taylor Berg- Barg-Kirkaatrick. Smaller language models are better black-box machine- machine-generated text detectors. arXiv preprint arXiv:2305.09859, 2023.
OpenAl. Gpt-4 technical report, 2023.
Yikang Pan, Liangming Pan, Wenhu Chen, Preslav Nakov, Min-Yen Kan, and William Yang Wang. On the risk of misinformation pollution with large language models. arXiv preprint arXiv:2305. 13661, 2023.
Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, llya Sutskever, et al. Language models are unsupervised multitask learners. OpenA/ 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. The Journal of Machine Learning Research, 2 21(1):5485-553 2020.
Vinu Sankar Sadasivan, Aounon Kumar, Sriram Balasubramanian, Wenxiao Wang, and Soheil Feizi. Can ai-generated text be reliably detected? arXiv preprint arXiv:2003 2023.
Jinyan Su, Terry Yue Zhuo Di Wang, and Preslav Nakov. Detectllm: Leveraging log rank information for zero-shot detection of machine-generated text. arXiv preprint arXiv:2306.055540 2023.
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. 2023.
KiYoon Yoo, Wonhyuk Ahn, Jiho Jang, and Nojun Kwak. Robust multi-bit natural language watermarking through invariant features. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Pupers), pp. 2092-2115, 2023.
Haolan Zhan, Xuanli He, Qiongkai Xu, Yuxiang Wu, and Pontus Stenetorp. G3detector: General gpt-generated text detector. arXiv preprint 2rX5v:2305./2680 2023.
Susan Zhang, Stephen Roller, Naman Goyal, Mikel Artetxe, Moya Chen, Shuohui Chen, Christopher Dewan, Mona Diab, Xian Li, Xi Victoria Lin, et al. Opt: Open pre-trained transformer language models. arXiv preprint arXiv:2205. 0/068, 2022.
Xuandong Zhao, Prabhanjan Ananth, Lei Li, and Yu-Xiang Wang. Provable robust watermarking for ai- ai-generated text. arXiv preprint 23t.::239..4399 2023.
11

---

Published as a conference paper at ICLR 2024
Table 3: Selected output examples from non-watermarked (NW) and watermarked (W) top-K sampling using 7 = 0.5, = 2.0 and ls = 20.
proeege
scal cccepictos
wattimnaii (NW)
vatcmmarked (W)
(XW)
(W)
[Real]
(NW/
(W)
191.
P95.
191.
DiR monthr Jm
10 moriing of the a Jolls Dovrt-
27 moriing Rep--bil dile-blee and Kors discassed liee seed for a condo saa-
11-12 masiing theudity anncenerd
07
10.5
540
8766
7.19
Ressiali, Diare Kass. Angeies Larn and pio lon chai
opuoon Poiust Revice comtaitee (DER: horrd mumber woud sroni- nooddy
tau, die deedeediipeeee of condis to
to gut ther. Cleiclio spolic about the conlo
in the fraiints devememenn has
adoccss-
appeoved by ciyy We prssile
CosidTo projecs.la the
niteee
innpetter
atforcable
wighhoothods Poarl Street continss
aooado that growing
fooh daey I coneiinuss)
Earls simulanenddy close comrni-
the Buildegs lish trral and will
Cardiza
9.15
derpping of Eve, trils delivieed
hall Plyylff Towemnment
iss Auile Oguaborate's logacs,
fice the Bulldogs in the fiall Tae trns also defsond togles in the firal and will feee lae Buildogs as frud, Boesn Callegeiia The lta- plan vary good game againal (oontiieees
berth in the SCAA Toumanent. The hagiee will mast Nome Dome
nakerppair perine- ausse sgiintt Boston Callegr, picking up a 30ppint win ever
the onior goond paoodd curmet ae-
socatt couch Beth Cuasiggla oc. lis alkomee scame
the Big 12 Toumasorr, or Seyl. 14 Asatin loca in ve win the find cound [. continaan)
mrmnin Netre Uame 123-11 conttieess
Two officers of com- pass dust speries tase
with the hondl Disrin Anoney Momeriha of Mastai- sad
they recelved from the govermmene The indistment, whics was no- Tannbyy
between flomelles and the home-
-1.9
9.94
0.83
7.00
1,05
los The acheme, alleyed be
godice
City
Health Welface snowweeed
wchome anly home-
bat conter by the city He said lis of- has won dekayat in moving non
thoee boick
shift with. teme- less who alled dieck foom his tandlunt mon unid the pe- ficers abiut the schens, which in- valvedt continan)
wake the 2012
less peoyle Eaxduically
Saady Hook Elaseatag School chooiing and the 2011 homthing of the Boston Mastiion. Authariess ezy thai the schems [_omtimaas)
cheate willom checks
and sylnn the money
quickly on the case beaase diff.. calyy .omiinee)
Brodhadee had writton
US Arthssader David Multon! writng desely ir West Bezpi
the concrets made Mutiod, th hiP MP abo called os the CM to meign immodenely and the Ceme
Mi Mulfied's behasione in the me- dia and the Patiseneni the Unice
1.85
12.36
4.25
7:35
8115
soune ketzr of peokol
Manmohan Singh
Chief Mistour Buithatee Bla--
Minicee has disccred Union Soo- retasios of Pulieseest and
lecting Maalord's
uxtuties his saaint
mukec a vusemmntt Singh, MP
conting
Taeing
costioes
lin sm) .ontmans)
pood toj cominsee)
Table 4: This table presents the detection accuracy of our algorithm in text rewriting scenarios. We compared the performance of our network-based watermark detection algorithm with the previous key-based watermarking detection methods under the C4 dataset, both in the absence of attacks and after rewriting using GPT-3.55.
No ATTACK
REWRITE W. GPT3.5
Methods / Settings
FPR
FNR
FI
FPR
FNR
Fl
Key-based
0.0
0.0
100.0
2.4
4.7
96.4
W. window hindow_size size
Network-based
0.6
0.0
99.7
6.4
1.0
96.4
GPT2
Key-bused
0.0
0.0
100.0
4.6
9.3
92.8
W. window_siiz size
Network- based
0.0
1.0
99.5
5.0
2.6
96.2
Key-hased
0.0
100.0
6.8
8.9
92.0
W. window hineow_size
Network-based
0.0
0.0
100.0
17.4
3.4
90.3
OPT 1.3B
Key-based
0.0
100.0
7.8
11.5
90.1
W. window_sizee
Network-based
0.4
99.3
4.6
11.2
91.8
Key-based
0.0
0.0
100.0
8.4
12.5
89.0
window_sie Lize
Network-hasod
0.0
100.0
18.0
89.2
LLaMA
window_size 2
Key-based
0.0
0.0
100.0
11.0
13.7
87.2
Network based
98.6
12.4
92.9
A
CASE STUDY
To better illustrate the text generated by the watermarked LLM, we have listed some text examples from both the watermarked LLM and the non-watermarked LLM in Table We compare the z-scores and PPL scores between these texts. Specifically, when calculating PPL scores, we utilize the LLaMA 13B model (Touvron et al. 2023). The results from table demonstrate that the z-scores for texts generated by the watermarked LLM are significantly higher than those from the non- watermaardr I.M,, while there isn't significant increase in the PPL scores.
12

---

Published as a conference paper at ICLR 2024
B ROBUSTNESS TO REWRITE ATTACK
To further illustrate the robustness of our watermarking method, we compared our approach with a key-based watermark detection algorithm in Table 4 focusing the detection Fl scores after text rewriting using the GPT-3.5 turbo model. Specifically, we employed the 3pt-3.5-turbo-06 version with the prompt "Rewrite the following paragraph:".
Table 4 demonstrates that, despite not being specifically designed for rewrite robustness, our method showed significant resilience against text rewriting. After text rewriting using GPT-3.5, the detection Fl score of our method decreased by only an average of 6.7. Notably, our method outperformed the key-based detection approach in this robustness scenario, with average improvement of 1.5 percentage points. Therefore, our watermarking algorithm not only facilitates our watermark detection but also exhibits strong robustness.
C TRAINING DETAIL OF WATERMARK GENERATION AND DETECTION NETWORK
In this section, we will provide more detailed introduction the training details of the watermark generation network and watermark detection network.
For the watermark generation network, the network details have been introduced in Section 4.2 Specifically, for all tokens within a window size, each token is first passed through an embedding network E obtain its embedding. Then, all embeddings are concatenated and passed through fully connected network, FFN, to produce classification logits:
(10) For the embedding network E, there are five layers, the input dimension is 16, and the output dimension of each intermediate layer, including the output layer, is 64. For the FFN, its input dimension is 64*w, where w is the window size. It is three-layer fully connected network, with the first two layer having an output dimension of 64 and the last layer having an output dimension of 1. After passing through sigmoid function the binary cross entropy is used to calculate the loss, as shown below:
W FFN(E(Zn-w+1) ① E(#n-w+2) @ .... O E(x,)).
N
Lng Σ [yv loolooo ((x + (1 - yi) logg1 - oW (xn 1on )))]-
(11)
N
2m1
In the subsequent training process, as shown in Section 5.6 of data with desired label rate and trained for 500 steps with a batch size of 32 using the Adam optimizer with a learning rate of 0.01.
we used 5000 randomly generated pieces
Similarly, the structure of the watermark detection network has been introduced in Section 4.4 The input to this network is all the texts to be tested. Firstly, every token is processed through an embedding network E, identical in structure and shared in parameters with the embedding network in the watermark generation network. Following the embedding of each token, the sequence is passed through an LSTM network to produce the final classification results for detection. This LSTM comprises five layers, with an input dimension of 64 for each unit, an intermediate output dimension of 128, and a final output dimension of 1 for the output logits, obtained by passing the last unit's output through a linear layer and then through a sigmoid function, utilizing BCE loss to generate the detector's 's loss, expressed as follows:
1 N
La N Σ ly log(o(((z)))) + (1 - -y)) llo((1 (((x)))))
(12)
During training, 10,000 data points were used, generated by the watermark generation network as random ID sequences (token IDs), with equal ratio of watermarked and non- watermarked data. The network was trained using the Adam optimizer, a learning rate of 0.01, for 80 epochs, and a batch size of 32, with batch size set to 64.
It's important to note that although an LSTM was chosen for the watermark detection network architecture, it does not imply that watermark detectors are limited to LSTM. This choice was made due to the simplicity and effectiveness of LSTMs, but other architectures capable of processing sequential inputs, like transformers, could also achieve excellent results.
13

---

Published as a conference paper at ICLR 2024
Amount of data Cracking F1
Cracking result
71-
100
Forged watermark F1 score
70-
vineoww libe
Cracking
67-
50-
Amount
Cracking
(b)
Figure 4: The left figure depicts the relationship between the different amount of data for training and the achievable cracking Fl score under reverse training setting. The right figure demonstrates the effectiveness of watermark forgery at various cracking Fl scores.
D DETAILS OF REVERSE TRAINING
In Sections 4.5 and 5.4 analyzed the challenges of training watermark generation network using training data from watermark detection network, both theoretically and experimentally. Here we elaborate the intricacies of this reverse training process.
key aspect is the definition of loss function for reverse training. Given a sentence's token list [11 ...y ]. the detection network DD assigns label indicating watermarked (1) not (0). We employ new generative network, denoted as W, to simulate the detection of watermarks. Specifically, this involves calculating whether each token contains watermark and then computing the average:
T W(astt)
(13)
T
Utilizing the output of generative networks as labels, the final reverse training loss could be repre- sented as follows:
L(W) -D(x log(p) -1- D(x)) log(1 p)
(14)
For training, we used 10,000 random token lists of length 100-200, labeled by detector D.
To further explore the impact of data amount the reverse training attacks, we demonstrated in Figure the changes in the cracking F1 score as the amount of data increases. It could be observed that, beyond a certain data amount, cracking F1 score only experiences marginal improvements with the increase in data amount.
Moreover, to illustrate how different cracking Fl scores influence the degree of watermark forgery, we generated watermarked texts using watermarking rules with varying cracking Fl scores. These texts were then subjected to standard watermark detectors to calculate the corresponding detection Fl scores, depicted in Figure (b)) We employed watermark strength of a = 2. The above result indicates that a cracking F1 score above 90 is required for successful watermark forgery.
E IMPACT OF WATERMARK ON MACHINE TRANSLATION TASK
To validate the impact of our watermarking method on text quality, we conducted further verification in the context of machine translation tasks.
14

---

Published as a conference paper at ICLR 2024
Table 5: This table demonstrates the efficacy of watermarking algorithm in machine translation tasks. We conducted experiments using four scenarios within the WMT14 dataset: English- French. French-English. German- Engllsh,, and English-German The machine translation model employed was -LLB--00-distiled--6000 We compared the watermark detection F1 score as well as the BLEU values before and after watermark insertion.
Setting Key-based FI
Network-based
Ori. BLEU
Wat. BLEU
EN-FR
98.7
98.1
39.3
38.5
FR-EN
99.2
98.9
37.9
34.0
EN-DE 99.2
99.0
49.6
49.6
DE-EN
99.4
99.1
38.5
37.9
Specifically, utilized four scenarios from the WMT14 dataset Macháček & Bojar (2014): English- French, French-English, German-Engglsh, and English-Gernan The machine translation model employed was NLLB-200-disie (ol-ddiiilled-600MM Costa-jussà al. (2022). We reported the model's BLEU scores without watermarking (Ori. BLEU) and with watermarking.
As indicated in Table introducing watermarks only causes minimal impact on BLEU scores, with an average decrease of only 1.3. In these scenarios, both key-based and our dawork-bbssd watermarking detection methods achieved high detection FI score. This further illustrates that our watermarking algorithm has only negligible effect text quality and model performance.
F EXAMPLE OF CYCLIC DOCUMENT
In Section 4.4 we introduced the approach of treating text as a cyclic document for watermark detection and training data construction. This method helps prevent a vulnerability related to the theft of watermark rules. We provide a more detailed explanation through simple example in this section.
Consider sentence t with tokens ABCDEF. When the window size is 3, the labeling of each token follows: C W(ACC)= = watermarked, D W(BCD) not watermarked, watermarked. However, without using cyclic document, tokens
W(CDE)
watermarked, F W(DEF) and B remain unlabeled, potentially creating system vulnerability. For instance, if a user continuously alters the last token (here, F) and observes the detection confidence D(L = ABCDE?) of the network, a clear score distinction between watermarked and unwatermarked tokens emerges. If the tests four characters and finds D(t ABCDEA) se D(t ABCDEB) > D(t ABCDEC) R D( = ABCDED), it's easy to infer that with DE as a prefix, and B are watermarked tokens, while C and D are not.
To address this vulnerability, we set the entire document as a cyclic document. We label the beginning token A W(EFA) and B as W(F ensuring each token has corresponding label and thereby avoiding the aforementioned vulnerability.
G DETAILS OF DIRECT CRACKING ATTACK
Table 6: Occurrence frequencies of the most common (w-1)-gramp under varying window sizes.
Window Size
Most Common Prefix
Frequency
2
the
0.04
3
0.018
4
åG L
0.004
5
åG L. Ghe Gsaid
0,00008
In this section, we detail another attack method mentioned in section 5.4 the direct cracking attack.
This method, originating from the work of Sadasivan et al. 2023), does not require watermark
15

---

Published as a conference paper at ICLR 2024
Attack F1 vs. Number of Data
Attack F1 Score
0.70
And
0.65
0.50
6000 Number of Data
10000
Figure 5: Variation in attack success rate with increasing data volume for window sizes of and
detector. Instead, it solely analyzes changes in token frequency distributions. Specifically, with window size of w, examines the frequency the wth token appears given a prefix of length w-1 tokens. If a token's frequency significantly increases in the presence of watermark, it is deemed to be part the watermark token set.
As in Sadasivan et al. 2023)* method, examine the 181 most common (w-1)-tokee n-grams. Since even the most common (w-1)-grane become increasingly rare as w grows, predicting watermarked text also becomes increasingly difficult with this approach. As shown in Table as the window size increases, the frequency of the most common prefixes decreases markedly. Analyzing this may require extremely large amount of data, but through our analysis in Figure when the window size grows to certain extent, even increasing the data amount cannot significantly improve the effect.
H EXPANDING THE K IN TOP-K SAMPLING
Table 7: Resource consumption metrics of watermark generation network during 200-Token genera- tion task under various k values and window sizes.
K Value
Window Size
Computation Time (s)
Memory Consumption (MB)
0.62
23
10
0.62
23
0.65
25
200
27
0.67
46
2000
10
0.70
48
1.20
228
20000
1.60
354
In Table we comprehensively examined the impact of varying k-values computation time and GPU memory utilization. All timings were recorded on a single V100 32G GPU. It can observed that even when processing 20,000 tokens simultancously, the computation time is only twice that of processing 20 tokens, while the memory consumption increases tenfold (with a window size of 5). This indicates that algorithm demonstrates exceptionally low computational complexity with respect to increasing k-values.
I DETECTION F1 SCORE ACROSS DIFFERENT DOMAINS
To validate claim in Section 4.4 that watermark detection algorithm is robust to differences in text domain, we compare our network-bar based watermark detector to current key-based watermark detectors across various text domains in the DBPEDIA CLASS dataset (Table g). Our algorithm
16

---

Published as a conference paper at ICLR 2024
Table 8: Comparison of detection accuracy of network-based watermark detector text domains in the DBPEDIA CLASS dataset versus key-based watermark detectors.
Setting
FPR
FNR
F1
Key-based Detector
0.5
0.0
99.8
Domain: Agent
Network-based Detector
0.0
0.7
99.6
Key-based Detector
0.0
0.5
99.7
Domain: Place
Network-based Detector
0.1
2.4
98.9
Key-based Detector
0.0
1.0
99.5
Domain: Species
Network-based Detector
0.0
2.8
98.3
achieves consistently high detection Fl score across domains, primarily because the random token ID lists used during training explore the space of V possible inputs, covering all plausible texts. Thus, our detector can theoretically achieve similar detection F1 score across text domains.
17


Reviews:
[{"review_id": "ZRLrE2qKi2", "reviewer": "Reviewer_PMgN", "summary": "This paper presents a method for LLM watermarking. It can handle the security breaches and counterfeiting problems of existing LLM watermarking methods caused by secret key, through using two different neural networks for watermark generation and detection. Experiments on two datasets verify the effectiveness of the proposed method.", "questions": "Are your methods robust to text edit methods like paraphrase?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. LLM watermarking is a very important problem.\n\n2. The proposed method can handle the security breaches and counterfeiting problems of existing LLM watermarking methods.\n\n3. The proposed method is effective according to the reported results.", "weaknesses": "1. Please correct me if I am wrong. It seems that there is no comparison with baseline methods in terms of both watermarking effectiveness and text generation quality.\n\n2. It is not clear whether text edit methods like paraphrase can make the proposed method invalid.", "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": "I8Xl7ftmeS", "reviewer": "Reviewer_CjAu", "summary": "The authors propose a private watermarking method for large language models that allows the public verification of a watermark by using two verification keys, one of which can be released publicly. The authors propose an algorithm involving an LSTM to generate the watermarked text and show that their watermark is effective and difficult to reverse-engineer.", "questions": "* Please clarify the motivation and definitions of \"privacy\". Why are existing watermarking methods not private? \n\n* How robust is your watermark?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "* The experimentation section is thorough, although it could be explained better\n\n* The authors tackle an important and timely problem of watermarking language models.\n\n* The idea of splitting the generation and verification watermarking key is interesting", "weaknesses": "**Unclear Definition of Private Watermarking** \n\nSome statements are confusing. For example, on p1, the authors write the following. \n> However, current watermarking algorithms are all public, which means the detection of watermarks requires the key from the watermark generation process. \n\nBut then, the authors state that any watermarking method can be made private by limiting who has access to this detection key (also p1).\n\n> Although Kirchenbauer et al. (2023) have suggested that the watermark detection process could be placed\nbehind the web API to achieve the effect of private watermarking, this approach requires substantial\nserver resources and robust designs against hacking (even social engineering). \n\nHence, there is a trivial method to make watermarking algorithms private, meaning that not all watermarking methods are public. I am confused by the author's definition of a private and public watermark. I understand the general idea of separate keys for generating and verifying a watermark, but could the authors please elaborate on their definition of a private watermark? Why is their method not public (as the definition used by Kirchenbauer [A] suggests: A watermark is public if anyone can detect a watermark in text). \n\n**Imprecise Language**\n\n* What does \"cracking the watermarking rules\" mean? Are the authors referring to the integrity of their watermarks? \n* What does it mean to \"implement watermarking in a privacy-preserving manner\"? \n* What are \"definite labels\" (p9)? \n\n**Robustness**\n\nThe authors' focus appears to be on the effectiveness and privacy of their watermark, and they do not study its robustness. An attacker who can verify a watermark in any text sequence should be much more capable of removing the watermark. Why did the authors not evaluate robustness? What good is a watermark that is not robust? Even if the watermark is not robust, I would appreciate it if the authors included these experiments showing their watermark's limitations. \n\n\n**Minor Questions**\n\n* What does FFN stand for in EQ 2?\n\n* How many parameters does the LSTM have?\n\n* In EQ 3, is \"P\" supposed to be the probability? Earlier, it was defined to be the logit score.\n\n* In EQ 8, what is $f$? \n--------\n[A] Kirchenbauer, J., Geiping, J., Wen, Y., Katz, J., Miers, I., & Goldstein, T. (2023). A watermark for large language models. arXiv preprint arXiv:2301.10226.", "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": "NNlcF2i0t2", "reviewer": "Reviewer_seaW", "summary": "This paper presents a new watermarking scheme for LLMs using two separate neural networks. The proposed watermarking method preserves the privacy of the secret key since watermark detection does not require the secret key used in watermark generation. The authors show via empirical results that the watermark detection method achieves a high detection rate.", "questions": "Please address the weaknesses above.", "limitations": "", "rating": 3, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper has the following strengths: \n+ The authors propose a new private watermarking scheme that disentangles watermark generation and watermark detection. This addresses the privacy concern of requiring the secret key in watermark detection. \n+ Empirical results show that it's difficult to reverse watermark generation from watermark detection, and also the proposed detection method achieves high detection rate.", "weaknesses": "The paper has the following weaknesses:\n- The contribution of the private watermarking scheme is not clearly justified. If the designer wants to protect the secret key, he can use a public key encryption scheme to design the watermarking scheme. Particularly, they can use a secret key in watermark generation, and a public key for watermark detection. It's not clear why the designer has to use two neural networks for watermark generation/detection.  \n- There is no clear discussion about how watermark generation and the watermark detection model are trained. There is no explanation about the loss function used either. Alg.1 assumes watermark generation network W as input while it's not clear how W is trained in the first place.  \n- The results shown in Section 5 are not comprehensive. It's not clear whether watermark generation has negative impacts on the main task of the LLM and this is not measured. For existing DL watermarking schemes, there is a fidelity requirement on the watermark embedding which shall be measured as part of performance evaluation. Please consider define the criteria for LLM watermarking and report the results in the paper.", "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": "56nypSpCFR", "reviewer": "Reviewer_kypk", "summary": "With the rapid development of Large Language Models (LLMs), these models are capable of generating human-like text, posing various risks such as the proliferation of false information on the Internet and the infringement of copyrights on creative works. Therefore, texts generated by LLMs need to be detectable and taggable. Existing watermarking algorithms are mostly public, requiring the detector to use the secret key employed in the watermark generation process, which exposes the method to vulnerabilities as attackers can easily remove and forge the text watermarks. To address these shortcomings, the authors propose a novel private watermarking algorithm designed specifically for LLMs. The approach uses two separate neural networks for watermark generation and detection, eliminating the dependency on a single secret key across both stages. The security of this method is enhanced through computational asymmetry, making it significantly more challenging to reverse-engineer the watermark generation algorithm from the detector. To reduce the complexity of training, the authors also introduced a technique to share token embedding parameters between the detector and the generator. Extensive experiments validate the efficacy of the proposed method, demonstrating nearly equivalent performance to public watermark algorithms while proving its resilience against two mentioned attacks.", "questions": "1.& 2. The first two points are as mentioned in the weaknesses section.\n\n3. It would be informative if the authors could elucidate the reasoning behind choosing LSTM networks for the Detection Network, especially when more advanced models are available.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The authors successfully identify the limitations inherent in existing public watermarking methods. They introduce a novel private watermarking approach that employs separate generation and detection models. This design transition from a public key to a private key significantly enhances the security of the watermarking process.\n2. The authors offer a suitable explanation in Section 4.3, \"Watermark Detection,\" to address the limitation of deep learning models in maintaining a static watermarked token ratio γ. The empirical validation of this explanation is provided in Section 5.6, \"Watermark Generation Network Analysis.\"\n3. While the performance of the proposed method under different datasets and models does not exceed that of public watermarking methods, the authors provide a plausible explanation for this discrepancy. Despite this, their method achieves competitive performance.\n4. Regarding the strategy of shared embedding, the authors have validated its effectiveness through comprehensive ablation experiments in Section 5.3, \"Analysis of Shared Embedding.\"", "weaknesses": "1. While the authors have identified the security flaws in public watermark methods, the discussion lacks specific references or examples of existing attack methods. To further bolster the superiority of their proposed approach, the authors might need to include comparative assessments against how public watermark methods fare against the two types of attacks discussed in Section 4.5, \"Analysis of Privacy.\"\n2. The last paragraph in Section 4.4, \"Watermark Detection Network,\" regarding the construction of a cyclic document, is somewhat vague. A more detailed explanation, ideally supplemented with concrete examples, would enhance the clarity of this segment.", "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)