Provable Robust Watermarking for AI-Generated Text
Authors: Xuandong Zhao
Prabhanjan Vijendra Ananth
Lei Li
Yu-Xiang Wang
Venue: ICLR 2024 poster (2024)
Keywords: text generation
watermark
secure ai
Primary area: societal considerations including fairness, safety, privacy

Abstract: We study the problem of watermarking large language models (LLMs) generated text — one of the most promising approaches for addressing the safety challenges of LLM usage. In this paper, we propose a rigorous theoretical framework to quantify the effectiveness and robustness of LLM watermarks. We propose a robust and high-quality watermark method, Unigram-Watermark, by extending an existing approach with a simplified fixed grouping strategy. We prove that our watermark method enjoys guaranteed generation quality, correctness in watermark detection, and is robust against text editing and paraphrasing. Experiments on three varying LLMs and two datasets verify that our Unigram-Watermark achieves superior detection accuracy and comparable generation quality in perplexity, thus promoting the responsible use of LLMs.

Published as a conference paper at ICLR 2024
PROVABLE ROBUST GENERATED TEXT
WATERMARKING
FOR AI-
Xuandong Zhao UC Santa Barbura
Prabhanjan Ananth
Lei Li
Yu-Xiang Wang
[xuandongzhao,, pwwphhhaaa..raaaajjaaaaaa leili, yuxi angw) êcs ucsb.
ABSTRACT
We study the problem of watermarking large language models (LLMS)) generated text one of the most promising approaches for addressing the safety challenges of LLM usage. In this paper, we propose a rigorous theoretical framework to quantify the effectiveness and robustness LLM watermarks. We propose robust and high-quality watermark method, UNIGRAM- WATERMARK, by extending an existing approach with a simplified fixed grouping strategy. We prove that our watermark method enjoys guaranteed generation quality, correctness in watermark detection, and robust against text editing and paraphrasing. Experiments on three varying LLMs and two datasets verify that our UNIGRAM- WATERMARK achieves superior detection accuracy and comparable generation quality in perplexity, thus promoting the responsible use of LLMs. Code is available at ht.ps:: / gituub. com/ htt//uuunnnngaoao....o Uni gram- Wa e rmark rk.
INTRODUCTION
Generative Artificial Intelligence (AI) (Brown et al., 2020; Ramesh et al., 2022; Saharia et al., 2022: OpenAI, 2023a) has achieved significant progress in recent years, spanning from computer vision (CV) to natural language processing (NLP). Large language models (LLMs) such as ChatGPT (OpenAI, 2022) can generate coherent and contextually relevant long-form text in response user- specified prompts. However, the ease of using LLMs has raised concerns about their potential misuse (Zellers et al., 2019; Weidinger et al., 2021; Stokel-Wall Walker, 2022). For example, LLMs could be used to generate fake news, contaminate web content, assist in academic dishonesty. Additionally, the proliferation of synthetic data from LLMS poses challenges for training new models, as synthetic data needs to be detected and excluded before model training (Radford al., 2022; Carlini et al., 2023).
There are two main camps of existing attempts to address these challenges. One camp, inspired by Turing (1950), aims generically distinguishing machine-gemerated text from that of the humans (Gehrmann et al., 2019; Mitchell et al., 2023; Hovy, 2016; Zellers et al., 2019; OpenAl, 2023b). These works primarily leverage hand-crafted learned "statistical patterns" of generated text, thus their performance is not robust to distribution changes (c.g.. by prompting conditioning), prone to biases (Liang al., 2023), and vulnerable adversarial attacks.
The other camp advocates active intervention by injecting carefully-designed watermarks to machine- generated text (Kirchenbauer al., 2023; Zhao et al., 2023). The watermarking approach does not search for statistical patterns (which could be hit-or-miss), but rather deliberately plant subtle but distinctive patterns within the content enable downstream detection. Compared detection approaches, the watermarking methods aim at determining whether the text is coming from a specific language model rather than solving the Turing test generically. As a result, watermarking approaches are robust to distribution-shi and essentially prove rather than predict the origin of the suspect text.
the passive
The most notable challenge for the watermarking approach is that the planted patterns could be post-processed away. As an example, Kirchenbauer et al. (2023)'s soft watermarking method divides the vocabulary into "green list" and "red list" based on the prefix token, and subtly increases the probability of choosing from the green list. If the watermarked sentence edited by changing every other token into its synonym, then it is no longer possible determine the green/red lists for each

---

Published as a conference paper at ICLR 2024
candidate token, thus ruining the detector. One could also simply paraphrase the sentence whole using another off shellf LLM.
In this paper, we take a first stab at formally defining robustness in the context of watermarking LLMs. Our contributions are fourfold.
1.
We devise rigorous theoretical framework for quantifying the performance drop, the correctness of detection, and the security property against post-processing.
We propose to simplify the scheme Kirchenbauer et al. (2023) by using a fixed Green-Red split consistently and show that the new watermark, named UNIGRAM- WAAAAA-A-AERRRK is twice as robust to edits as the baseline, provably.
We prove that the watermarked LLM is close the original LLM (in all Renyi divergences) and show that the Type 1/Type II errors of the detection algorithm decay exponentially as the suspect text length gets longer and more diverse.
We conduct experiments utilizing various large language models on diverse datasets. The results indicate that our method achieves superior detection accuracy and improved robustness against different attacks, thus promoting the responsible use of LLMs.
To the best of our knowledge, we are the first to obtain provably robust guarantees for watermarks for LLMs against arbitrary edits.
Related work. We build upon the work of Kirchenbauer et al. (2023) in which the family of K K-gram (statistical) watermark was proposed'. The main method we consider chooses = 1, thus its name UNIGRAM- WATRRMRR.. Our work provides formal theoretical guarantees to this family of K -gram watermark. For the sake of clean presentation, we focus on the case when K = and discuss the applicability of our results for K > 1 in the discussion section. Our work is independent of the concurrent work of cryptographic watermarks (Aaronson, 2023; Christ et al., 2023). In particular, Aaronson (2023)'s proprietary work can also be viewed as an alternative K -gram watermark, but uses a cryptographic approach for measuring utility drop, which results in different kind of tradeoff. We defer detailed discussion an extended discussion of the related work in Appendix A. Technically, the main theoretical tool we used for analyzing dependent random variables and their concentration tightly due Albert (2019), the instantiation to our problem is new and nontrivial.
PROBLEM SETUP AND METHOD
We start with an overview of the language model watermarking problem. The definitions and notations introduced in this section will be used throughout the paper.
Language models. A language model (LM) M is statistical model that describes the probability of a sequence of words occurring in sentence. Common neural language models (e.g., GPT-2/3 (Radford al., 2019; Brown al., 2020)) are designed for next-wort word prediction which typically uses a transformer neural network (Vaswani et al., 2017). The LM has a "vocabulary" V with N == V| 50, 000 tokens or more (Radford et al., 2019; Liu et al., 2019). Let be an input prompt. : [y,, ....... U..] are tokens generated by M. During inference, MM receives the input prompt as the prefix of generation. It iteratively computes logit scores &, for every next token. The logits
exp(e</o]) transform into probability distribution via soft-(arg)max function Pe[u] = E [ieVex((2 for all E
V. The LM then samples the next token from this distribution: y/: Pt-
2.1 DEFINITION OF LANGUAGE MODEL WATERMARKING
In the language model watermarking problem, the objective for the model owner is to embed a secret message known "watermark" within the generated sequence y for a given prompt There two desired requirements for watermarking. First, the quality of the watermarked model should be comparable to the quality of the original, in-watermarked model. Second, adversary needs to modify sufficiently many Al-generated text in order to evade detection.
Note the changed name. Kirchenbauer et al. (2023) referred to its (unnamed) watermaak that determines the green/red list using prefix of length (K- 1). We think K K-gram watermark is the most concise and informative name for this family.
2

---

Published as a conference paper at ICLR 2024
Definition 2.1 (Edit distance). The edit distance, denoted as (y x), quantifies the number of basic operations required to transform a sequence y into another sequence z. These operations include "insertion", "deletion", and "replacement" of tokens.
Definition 2.2 (Language model watermarking). A language model watermarking scheme consists of two probabilistic polynomial algorithms (Watermark, Detect):
Watermark(MD (M): Let .M be a language model and let P. == PP (y) 12 1 be the condi- tional probability distribution of /-th token on V generated by M. This algorithm produces a new model M with a new conditional distribution p: == I (((w)) Wi 1W1.-11 on V. Additionally, outputs a detection key associated with M. The watermark could contain certain randomness.
Detect(k, y): This algorithm takes input detection key and sequence y. then outputs 1 (indicating it was generated by M) or 0 (indicating it was not generated by MM.
We require the following three correctness properties hold:
w-Quality of watermarked output, for E I: Assume the original language model M generates probability vector Pt for the token position The watermarked model M predicts the token at position t using the modified probability vector p.. It is required that the distance between the two probability distributions satisfies: D (p: llp.) S w for any fixed prompts and prefixes.
an Type error ("No false positives"): for any fixed y (i.e., independent to k). it holds that P Detect(k, y) = 1; (M, k) Watermark(MM) < Cy-
(( Type II error ("No false negatives"): P Detect(k, y) 0; (M.k))-ateemrrk(aM)) S BleeMM) y-
We also require the following security property (parameterized by 2 and n k, c)):
For any adversary A that postprocesses y with auxiliary information aux and any prompt V
v.k. (M.k)--aaarmrk((M)
Detect(k, v ED(y, VAA) 2 17,k, y Detect(k.))=1 ya~A(gaaux
M-x((a)
Remark 2.3 (Discussion on Definition 2.2). Informally, our definition allows us to formally quantify
the essential properties of language model watermarking scheme including its generation quality relative to the input LM, the accuracy of detection in terms of both false positives and false negatives, as well as the robustness to attacks.
The security property, in particular, states the following: suppose a malicious adversary intends to evade the detection algorithm, then the adversarial answer, to some input prompt æz, should far away (in edit distance) from any Al-generated answer. In other words, the optimal strategy to evade the detection algorithm would necessitate exccuting a minimum number of insert/éelete/replaeeeen operations, captured by the function 17()) in Definition 2.2. This conceptually suggests that the adversary must exert considerable effort to successfully elude detection.
Admittedly, there other attacks where edit distance does not capture either the effort the utility loss. For example, if one prompts an unwatermarked LLM to paraphrase then the number of edits be large but the semantic meaning is retained. However, edit distance is natural metric that smoothly interpolates the gray zone between the world where Y = y in which it should clearly be caught and the other world where A is independently created without using M in which it would be a false positive Detect returns 1.
2.2 THREAT MODELS
Adversary's objective. The primary objective of the adversary is render the watermark detection algorithm ineffective. Specifically. the adversary aims to produce a y such that Detect(k, y = while the same time, V. is minor modification of an Al-generated text y.
Adversary's capabilities. We consider an adversary with black-box input-output access to the language model. This adversary has the capacity modify the sequence within bounded edit
3

---

Published as a conference paper at ICLR 2024
distance. Given imput prompt æ, the watermarked language model generates text output <- (Mx). The adversary. equipped with arbitrary side-information and computational resources, can then produce a modified output y. such that the edit distance between the original and modified output, ED(,, y. vA) is bounded, i.e. (D MA)
2.3 METHOD
Algorithm 1 UNIGRAM- WATERMARK: Watermark
1: Input: random number generator F; green list size E (0, 1), watermark strength d.
2: Randomly generate a watermark key k using F.
3: Use watermark key to partition the vocabulary of M into "green list" G C V of size 7/V, and a "red list" R G
4: Define new language model M where for t. and any prefix (x, V1:tt: the resulting logits satisfy
L == L.[u] + +1(( E G);
(I)
where 1(-) is the indicator function and the logit vector e, E RIV is obtained by the passing the same prefix to M.
5: Output: watermark key k, watermarked language model M.
Algorithm 2 UNIGRAM- WATERMARK: Detect
1: Input: suspect text y. watermark detection key k, threshold T.
2: Output: or (whether the text is watermarked)..
3: Use the watermark detection key k to find the "green list" G.
4: Calculate the number of green list tokens y = Ei= 1 E G) (y,, ,,,,..,,ud)
5:
Compute the z-statistic:
By (1yle - ym) Vn -).
6: if Zy > T then return 1, i.e. "The suspect text watermarked."
7: else return 0, i..." "The suspect text is not watermarked.""
Now let instantiate Definition 2.2 with concrete algorithms. We will focus UNIGRAM- WATERMARK a variant of the K K-gram watermark proposed by Kirchenbauer et al. (2023) but with choice of K = 1. Pseudocodes of our approach Watermark and Detect provided in Algorithm 1 and 2. In Algorithm 1, we randomly partition the vocabulary into two distinct sets: the green list with N tokens and the red list with the remaining tokens. In M, the logits of the language model for the green list tokens are increased by d while the logits for tokens in the red list remain unchanged. Then at detection time (Algorithm 2), we count the number of green tokens in the suspect text, normalize the test-statistic, then make calibrated decision on whether we think the suspect text is generated from M or not. We show the examples of real prompts and watermarked outputs Table 1.
The watermarking procedure is parameterized by two watermark sirength parameters 8. deter- mines the fraction of the vocabulary included in the green list. We typically set ạ to be constant, e.g., 1/3 0.5. å specifies the increase in the logits associated with the green list tokens. The larger is, the lower the quality of the watermarked LM, but the easier it is to detect.
Our UNIGRAM- WATERMARK enjoys all good properties of the general K K-gram watermark from Kirchenbauer et al. (2023). rums in linear time and does not require access to the language model or the prompt used for generation. It is also intuitively robust to cropping and minor edits.
Overall, the proposed watermarking scheme requires almost no overhead in its implementation, is extremely simple, and is easy to maintain. The big question is: How well does this wate rmark scheme work?
The remainder of this paper provides answers this question with provable guarantees (Section 3) on the properties from Definition 2.2 and extensive experiments (Section 4).
Before that, let us address two burning questions that knowledgeable reader may have.
4

---

Published as a conference paper at ICLR 2024
Prompt
Is it possible fail several times and succeed once?
LJaMA-I3B
Of course it is, and that how we improve.lnSayinn AnSaying "I can't do that" never a good thing InSometimes we think we've tried all we can and that "isn't enough". That the time when we ask for help The root of all evils to be secret. Honesty and self-criticism nec- essary for improvement. The measure of intelligence the ability change. [continues...]
(un-watermarked)
PPL: 12.19
7-score: -2,425
I.L.MA-13B
When most people are confronted with failure, they cannot imagine such a thing happening. When one faces business reverses and bankruptey, it seems impossible. When we are rejected it looks as we are going to be rejected forever. However, it does not need to be this way. The human spirit simply will not give up. When we face failure and it looks like we [continues..]
(watermarked)
PPL:: 12.47
2-score: 11.085
Table 1: Comparison of un- watermarked and watermarked text using the ALaMA-13B model. Green and red tokens are color-coded respectively. UNIGR A WATERMARK produces watermarked text of similar quality without noticeable degradation, yet with significant differences in z-scores for watermark detection.
Why choosing K = 1? Recall that the general K K-gram watermark works in the same way as ours, but randomly generates different Green list for each prefix of length K - 1. In contrast, choosing K means we have a consistent green list for every new token the language model generates. The main advantage of choosing K 1 is that it is the most robust choice within this family and we believe robustness is the single most important feature of a watermarking scheme in practice.
Robustness to other attacks. Besides the robustness to edits, which we will prove in Section 3 and compare to that of K 2 2. UNIGRAM- WATERMARK is also resilient to many other kinds of generation time attacks that people can apply such as reversing, shuffling, as well the "Emoji insertion attack" that will completely break the watermark for K 2 2 but not for K = 1. We provide a detailed discussion of this in Appendix E.I.
The price for robustness? Kirchenbauer et al. (2023) did not consider the choice of K = 1 for an obvious reason. The watermark is now so simple that an attacker who observes the generated text may learn to guess the consistent green list. This is an issue for K 2 2 too but certainly more so for K 1. There is robustness- learnabiity tradeoff as we adjust K which deserves more rigorous treatment in future work. That said, we are ready to argue for biasing towards robustness. Why? We argue that in practice, could be surprisingly difficult for an attacker to construct meaningful attack when they do not have access to the original LMM We provide a more detailed experimental study with a faithful practical attack in Appendix B.4. Moreover, there are alternative ways to get around this issue by refreshing the green list once in while.
3 MAIN THEORETICAL RESULTS
In this section, we present the quality, correctness, and security properties of UNIGRAM-WATERMARE as described in Definition 2.2.
3.1 QUALITY GUARANTEE OF UNIGRAM- WATERMARK
We first show that the distance between the original probability vector Ps and the watermarked probability vector P. are very close to each other in any Renyi-divergence.
Theorem 3.1. Consider h as the input to the language model at step i, denoted as h = [xx, 11. Fix green list G. Let 8 represent the watermark strength. For any h, the a-th order Renyi-divergence between the watermarked probability distribution P. = -p((Ih) at time step t and the original probubility distribution p.
(h(- satisfies:
Wh, max (Da (Dillp:), D. (p:llp)) < min(ō, /888)..
The proof, deferred to the appendix, leverages a surprising connection to modern techniques in the differential privacy literature (Dwork et al., 2006; Dong et al., 2020).
Remark 3.2 (KL-divergence and other probability distance metrics). Renyi-divergence is very gen- and chi-square divergence
eral. Leaeeck--ebbee-ddveeeee divergence bound of min 6, ad² ad²/8} by choosing a = and a = 2 respectively and swap p and p. Hellinger distance can be obtained by choosing a 0.5. By Pinsker's inequality, we get a Total
directly implied by the a-Renyi
5

---

Published as a conference paper at ICLR 2024
Variation distance bound of min / 0/2 8/4). Moreover, by choosing a co, obtain upper bound of for a very strong multiplicative guarantee known as max max-divergence. The resulting two distributions p and p are referred to by cryptographers as (6, inddistinnguusssabee, which says that for any measurable event S, the log-odds ratio satisfies S log P=(v+E8(A)
(((ne))h) S 6.
To summarize, our result shows that Algorithm produces M that satisfies w-quality of watermarked output with w (as a function of d) for almost all commonly used probability distance D.
3.2 TYPE I ERROR OF UNIGRAM- WATERMARK
Theorem 3.3 (No false positives (short version of Theorem C.4)). Consider y Fim as any fixed
text. Define Cmax ( = max4e[N] E3=1 i = i) and V(y) == 1 1 = 1))²
With probability a (over only the randomness of
64V (og(9/a) 16C (y) log(9/a)
Zy S
1-7
Vn - 7)
The theorem says that the z-score for any sufficiently diverse text is Ó(1) and it is applicable to any text not generated by the watermarked LM M.
Remark 3.4 (Controlling false positive rate). The theorem implies that if we choose 16C (9g(9/a) then the false-positive rate is smaller than a. Note that and
V 1-7
64V (9g(9/a)
/ny(1-a)
Cmax can be computed directly from y. allowing to choose an input-dependent T as function of
V, Cmax that achieves a a-Tyye error guarantee with a fixed a for all inputs. particular, the Type I error decreases exponentially as we increase the threshold т.
3.3 TYPE II ERROR OF UNIGRAM- WATERMARK
To bound the Type II error, i.e., false negative rates, we need to make certain assumptions about of the language model and the prompt æ. These assumptions include "on-average high entropy" assumption and a "homophily" condition. We will provide a detailed definition and discussion of these assumptions in Appendix C.4.1 and Appendix C.4.2.
The "on-average high entropy" assumption requires the probability of the roll-out text to be "suffi ciently diverse" on average. is related but different from the "spike entropy" assumption used by Kirchenbauer et al. (2023). The "homophily" assumption is new to this paper. It is an assumption about the distribution induced by the trans-transssions of the language model M, which says that increasing the probability of green-list token at time does not decrease the probability of seeing that token in the future. This may seem counter-intuitive, but we will give concrete examples in Appendix C.4.2 to show why this is fundamental for any statistical watermark to work effectively.
Theorem 3.5 (Only true positive (informal version of Theorem C.13)). Assume "average-high entropy" and "homophilly" to be valid with appropriate parameters, and in addition n 2 (1)og(1133/88 then with probability 1 - 8
2y 22
Remark 3.6. The bounds Type I/II error together say that 2n 8/n if y is from M while žy x 0(1) otherwise, i.e., there is a large margin between them so we can choose т in between. Also, the and / parameters decay exponentially the gets larger.
3.4 SECURITY PROPERTY OF WAARRM-WATTRMARKK
We demonstrate the robustness of our watermarking scheme against editing attempts through Theorem
3.7. As a baseline of comparison, we also obtain new robustness guarantees for the soft watermarking method proposed in Kirchenbauer et al. (2023). The detailed proof is deferred to the Appendix C.
Theorem 3.7 (Robustness to editing). Let y fy..... ynl represent the watermarked sequence. Suppose the adversary A follows Definition 2.2 and outputs modified text u [w1, [M,,.... -.... Um].

---

Published as a conference paper at ICLR 2024
Gelasel-model
Humen
KGW-23 watermark
OpenGen-GPT
Un watermaric
OpenCie-OPP
ap
LFOA-GPT2
25core
LFQA-LLaMA
Text Perplexity
60
40
5
Human (a) 2-Scores of watermarked and un-watermarked nachine-generated text, along with s-score of human human-generated text. The watermarked text 2-
Watermarked Un-watemarked
GPT2
OFT
LLaMA
(b) Text perplexity comparison (evaluated by GPT-
3) between human- -unan-generated text and text gener- ated by various models on the OpenGen dataset.
score surpasess the empirical threshold of 2 = 6.0.
Figure I: z-score comparison and text perplexity comparison.
Following Equation 2. we calculate z-score By and Zu. Assume edit distance between y and (denoted as 1)) satisfies < n. Then we have
(1 + 7/2)n (1-7/2)n
Zu 2 Zy max
Vn Tj
In particular, when 1) (1+7/2)2 we can drop the second term in the max.
This theorem bounds the changes to our test z-score when r edits are performed. As we established for a high-entropy sequence, By typically grows in O((e* Vn), which means that when ó is constant, with an appropriate choice of r, the watermark is robust up to O(n) arbitrary edits! Finally, compared Kirchenbauer et al. (2023)'s watermark, ours is twice as robust (see Appendix D).
EXPERIMENT
In this section, we aim conduct experiments evaluate watermark detection performance, water- marked text quality, and robustness against attacks compared to the baseline. Additional experiment results including different parameters, white-box attacks, scaled language models, etc. are deferred to Appendix B.
4.1 EXPERIMENT SETTING
Datasets and prompts. We utilize two long-form text datasets: OpenGen and LFQA. OpenGen, collected by Krishna et al. (2023), consists of 3K two-sentence chunks sampled from the validation split of WikiText-100 (Merity et al., 2017). The subsequent 300 tokens serve as the human-written continuation. LFQA is a long-form question-answertt
dataset created by Krishna al. (2023) by scraping questions from Reddit, posted between July and December 2021, across six domains. Krishna et al. (2023) randomly select 500 questions from each domain and pair them with their corresponding longest numan--witten answers, resulting in 3K QA pairs. In our experiments, we use questions as prompts and the corresponding answers as numan-written text.
Language models. We conduct experiments using three satte-of-the-art public language models of varying sizes from different model families: GPT2-XI. with 1.5B parameters (Radford al., 2019), OPT-1.3B (Zhang et al., 2022), and LLaMA-7B (Touvron et al., 2023). Nucleus Sampling (Holtzman et al., 2020) employed as the default decoding algorithm to introduce randomness while maintaining human-like text output. The models are loaded from the Huggingface library (Wolf et al., 2019), and the generate API function is used to adjust the logits distribution of the language model.
Evaluation methods. Maintaining a low false positive rate is crucial to prevent misclassifying un-watermarked text watermarked. To ensure this, set the false positive rates at 1 and 10% for
7

---

Published as a conference paper at ICLR 2024
OpenGen
LFQA
Setting
Method
1% FPR
10% FPR
1% FPR
10% FPR
TPR
F1
TPR
F1
TPR
F1
TPR
F1
No atlack
KGW+23
1.000
0.995
1.000
0.952
1.000
0.995
1,000
0.952
UNIGRAM- WATERMARK
1.000
0.995
1.000
0.952
1.000
0.995
1,000
0.952
KGW+23
0.565
0.704
0.853
0.747
0.327
0.453
0.673
0.490
CharGPT
UNIGRAM- WATERMARK
0.866
0.910
0.961
0.818
0.442
0.568
0.865
0.584
KGW+23
0.386
0,546
0.738
0.720
0.372
0.534
0.740
0.767
DIPPER-1
UNIGRAM- WATERMARK
0.729
0.830
0.922
0.837
0.639
0.770
0.909
0.865
KGW+23
0.490
0.646
0.810
0.769
0.432
0.595
0.845
0.839
DIPPER-2
UNIGRAM- WATERMARK
0.777
0.862
0.941
0.852
0.693
0.810
0.948
0.894
KGW+23
0.342
0,505
0.667
0.759
0.457
0.617
0.783
0.836
BART
UNIGRAM- WATERMARK
0.590
0.730
0.861
0.857
0.656
0.784
0.885
0.897
Table 2: Performance comparison of our method (UNIGRAM- WATERMARK) and the soft watermark- ing method proposed in Kirchenbauer et al. (2023) (denoted KGW+23). Both methods employ LLaMA-7B with nucleus sampling, utilizing 8 = 2.0 and 7 = 0.5. We use ChatGPT, DIPPER, and BART for paraphrasing the watermarked text as paraphrasing attacks. True positive rate and F1 score are presented for fixing the false positive rates at 1% and 10%. When there is no attack, both methods exhibit perfect watermark detection. Nevertheless, when subjected paraphrasing attacks, UNIGRAM-WATERMARE consistently outperforms KGW+23.
all detection algorithms and adjust the detection threshold accordingly. We report true positive rate (TPR), Fl score, and ROC curves. GPT3 etex wwaiiddiviiiiiaeeeeeee (Ouyang et al., 2022), is used as the oracle model for perplexity evaluation. The experiments are conducted on Nvidia A100 GPUs.
4.2 WATERMARKING RESULTS
We use a watermark strength of = 2.0 and green list ratio of y = 0.5. We also use different watermark keys for different models. Stronger watermarks can be achieved for shorter sequences for a smaller and a larger d. From the two datasets, we generate 500 watermarked sentences and 500 un-watermarked sentences using three different models (GPT2-XL, OPT-1.3B, and LLaMA-7B). We label them as "watermarked" and tun-waaermarked" respectively. We also have corresponding written text for each prompt, referred to as "human". All sentences are cropped to length of 200 tokens. 2-scores are calculated for hypothesis testing as shown in Algorithm 2 between different sentence groups The results (Figure la) indicate a clear distinction between watermarked and non-watermarked text. A default threshold of z-score = 6.0 can be used to determine if a text is watermarked. For a fair comparison with Kirchenbauer et al. (2023), we also set 8 = 2.0 and y = 0.5 for their method.
Figure lb demonstrates the text perplexity of human, un-watermarked machine- generated, and two watermarking-generte The perplexity of human text is significantly lower, likely due to the expertise contributed in the Wikipedia-based dataset used to train GPT3. We observe that the perplexity of the watermarked text is comparable to that of genarrte text, especially with the of the largest model LLaMA-7B, This finding further supports the effective- ness of our method in preserving linguistic characteristics and coherence, ensuring seamless integration of watermarks with- out compromising overall text quality. One example of the prompt questions and machine-generatee answers can be found in Table 1. We also conduct human evaluations to assess text quality. We enlist crowd workers from Amazon Mechanical Turk (AMT) to evaluate the quality of both watermarked and unwatermarked texts. From the LLaMA-7B model on the OpenGen dataset, we select 100 watermarked and 100 unwatermarked texts, anonymize the sentences, and ask workers to rate the quality scale of 1 (poor) to (excellent). Each sentence undergoes two evaluations. The average score and standard deviation are computed and presented in Table 3.
texts, evaluated on the OpenGen dataset.
Avg Score STD
Un-watermarked 3.660 0.655
Watermarked
3.665
0.619
Table 3: Human evaluation result.
8

---

Published as a conference paper at ICLR 2024
(a) UNIGRAM- WATERMARK against paraphrasing at- (b) UNIGRAM WATERMARK against editing attacks on tacks on OpenGen dataset with LLaMA-7B.
LFQA dataset with LLaMA-7B.
Figure 2: ROC curves with corresponding AUC values for watermark detection against various attack methods. Complete results can be found in the Appendix B.
4.3 ROBUSTNESS RESULTS
Paraphrasing attack. To demonstrate the superior robustness of our method, supported by our theorem, we devise experiments to compare its performance against Kirchenbauer et al. (2023). We employ different paraphrase attack techniques targeting the removal of the watermark. Firstly, we utilized two versions of the DIPPER model (Krishna et al., 2023), we denote them as "DIPPER-1" and "DIPPER-2" DIPPER-2 2 has greater diversity than DIPPER-1. Additionally, we leverage the ChatGPT API, generating paraphrased text by providing prompts such as "Rewrite the following paragraph:". Furthermore, we employ BART (Lewis et al., 2019) (bart-large sized model fine-tuned on the CNN Daily Mail dataset (Hermann et al., 2015)) for text summarization another type of paraphrasing attack. The results of our experiments are shown in Figure 2 and Table 2. The results illustrate the substantial improvement in robustness achieved by our method compared to Kirchenbauer al. (2023). Notably, method achieves an accuracy rate of over 85% with a false positive rate of 10%.
large-
Editing attack. To further evaluate the robustness of UNIGRAM- WATERMARK against edit attacks, we examine its performance when subjected to synonym replacement, random deletion, and random swapping. These edit attack scenarios represent common techniques used to manipulate text and potentially remove watermarks. We conduct these attacks for the watermarked text of UNIGRAM- WATERMARK and KGW+23. The results are shown in Figure 2. In each scenario, our method consistently outperforms Kirchenbauer et al. (2023) watermarking scheme, showcasing its enhanced resilience and effectiveness in protecting the integrity of the embedded watermarks.
4.4 DISTINGUISHING HUMAN- WRITTEN TEXT
An interesting observation emphasized by Liang et al. (2023) the misclassification of non-native English writ- ing samples as A Al-generated by existing AI content de- tectors. Our method can effectively establish text origin and maintain robustness to distribution shifts. We eval- uate UNIGRAN AM- WATERMARK written text on dataset of hrrttewwitten TOFFL essays collected by Liang et al. (2023). Our method demon- strates remarkable ability accurately classify human- written text, as evidenced by significantly lower 2-scores compared to the empirical threshold of 6.0. This outcome underscores the effectiveness of our watermark in discerning text generated by human authors, further enhancing its practical utility and reliability.
Misclassitedd rate
43%
50%
distinguishing human-
6tth Crigin Aingli
bul
Saping
Openki
TiTaee
Craaptin
Zerulrtt
Figure 3: Distinguishing human-written text on TOFFL dataset.
5 CONCLUSION
In this paper, we have addressed the concerns surrounding the potential misuse of large language models and proposed an effective watermarking approach, UNIGRAM- WATERMARK, for detecting machine-generated text from a specific language model. Our contributions include the development of a rigorous theoretical framework, designing a provable effective, and robust watermarking scheme under this framework, as well as conducting extensive experiments demonstrate the effectiveness and robustness of our method in practice. We anticipate that our work will inspire future research to develop more resilient watermarking methods capable of withstanding broader range of attacks.

---

Published as a conference paper at ICLR 2024
6 IMPACT STATEMENTS
Applicability to general K K-Gram watermark. While we focused on UNIGRAM- WATERMARK, most of results apply K-Grrm watermarks with K > 2 too. These include the Type I error bound, security properties (Robustness to edits), as well as the "Unique" alternative detector which we presented in Appendix E. While our Type Il error bound does not directly work for K some of our intermediate steps can be applied.
Limitations. While watermarking method, UNIGRAM- WATERMARK, demonstrates improved robustness against edits, its reliance on fixed Green-Red split may not be universally optimal. The performance and robustness of watermarking methods can vary depending on the specific characteristics of the LLM and the generated text. Additionally, although our method enhances detection capabilities, it is not immune all possible attacks.
Future work. Future work includes constructing unlearnable watermarks, understanding the robustness- leausbeessl tradeoff as well unifying cryptographical and statistical watermarks.
REFERENCES
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 33:1877-1901, 2020. 2020.
Aditya Ramesh, Prafulla Dhariwal, Alex Nichol, Casey Chu, and Mark Chen. Hierarchical text- conditional image generation with clip latents. ArXiv, abs/2204.06125, 2022.
Chitwan Saharia, William Chan, Saurabh Saxena, Lala Li, Jay Whang. Emily Denton, Kamyar Ghasemipour, Raphael Gontijo Lopes, Burcu Karagol Ayan, Tim Salimans, et al. Photorealistic text-to-image diffusion models with deep language understanding. Advances in Neural Information Processing Systems, 35:36479-366 -34494, 2022.
OpenAl. Gpt-4 technical report. ArXiv, abs/2303.08774, 2023a.
OpenAl. Chatgpt: Optimizing language models for dialogue. OpenAl blog, 2022. URL https:
oopenai www/blog.//oo./ httptgggccattp......
Rowan Zellers, Ari Holtzman, Hannah Rashkin, Yonatan Bisk, Ali Farhadi, Franziska Roesner, and Yejin Choi. Defending against neural fake news. Advances in neural information processing systems, 32, 2019.
Laura Weidinger, John J. Mellor, Maribeth Rauh, Conor Griffin, Jonathan Uesato, Po-Sen Huang, Myra Cheng, Mia Glaese, Borja Balle, Atoosa Kasirzadeh, Zachary Kenton, Sande Minnich Brown, William T. Hawkins, Tom Stepleton, Courtney Biles, Abeba Birhane, Julia Haas, Laura Rimell, Lisa Anne Hendricks, William S. Isaac, Sean Legassick, Geoffrey Irving, and lason Gabriel. Ethical and social risks of harm from language models. ArXiv, abs/21 12.04359, 2021.
Chris Walker. Ai bot chatgpt writes smart essays should professors worry? Nature, 2022.
Alec Radford, Jong Wook Kim, Tao Xu, Greg Brockman, Christine McLeavey, and Ilya Sutskever. Robust speech recognition via large-scale weak supervision. ArXiv, abs/2212.04356 2022.
Nicholas Carlini, Matthew Jagielski, Christopher A. Choquette- CCho, Daniel Paleka, Will Pearce, H. Anderson, A. Terzis, Kurt Thomas, and Florian Tramèr. Poisoning web-scale training datasets practical, ArXiv, abs/2302. 10149, 2023.
Alan M Turing. Computing machinery and intelligence. 1950.
Sebastian Gehrmann, Hendrik Strobelt, and Alexander M. Rush. Gltr: Statistical detection and visualization of generated text. In Annual Meeting of the Association for Computational Linguistics, 2019.
Eric Mitchell, Yoonho Lee, Alexander Khazatsky, Christopher D. Manning, and Chelsea Finn. Detectgpt: Zero-shot machine -eaiertee text detection using probability curvature. ArXiv, abs/2301. 1305, 2023.
10

---

Published as a conference paper at ICLR 2024
Dirk Hovy. The enemy in your camp: How well can detect ceaistically-geeeratee fake reviews- an adversarial study. In Annual Meeting of the Association for Computational Linguistics, 2016.
OpenAI. nAI blog, 2023b.
New ai classifier for indicating ai-written
text.
Ope-
URL
https:
http//pppaaaaaaae/ee//ee/...a..a com/ blgg//lo////
Weixin Liang, Mert Yuksekgonul, Yining Mao, Eric Wu, and James Zou. Gpt detectors are biased against non-native english writers. ArXiv, abs/2304.02819, 2023.
John Kirchenbauer, Jonas Geiping, Yuxin Wen, Jonathan Katz, Ian Miers, and Tom Goldstein. A watermark for large language models. International Conference on Machine Learning, 2023.
Xuandong Zhao, Yu xiang Wang, and Lei Li. Protecting language generation models via invisible watermarking. ArXiv, abs/2302.03162,, 2023.
Scott Aaronson.
watermarking of large lan- URL https: / simonss berkeley edu/talks/ scott-aaronson- www.ssoooutuuutti----e austinstinn 1orsstii-ppnaa-2223-0000
Simons
institute
talk
guage models. 2023.
Miranda Christ, Sam Gunn, and Or Zamir. Undetectable watermarks for language models. arXiv
preprint arXiv:2306.09194 2023.
Mélisande Albert. Concentration inequalities for randomly permuted sums. In High Dimensional Probability VIII: The Oaxaca Volume, pages 341-383. Springer, 2019.
Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. Language models unsupervised multitask learners. OpenAl blog, 2019.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones. Aidan Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017.
Yinhan Liu, Myle Out, 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, abs/1907. 1692, 2019.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryplography, pages 265-284. Springer, 2006.
Jinshuo Dong, David Durfee, and Ryan Rogers. Optimal differential privacy composition for exponential mechanisms. In International Conference on Machine Learning, pages 2597-2606. PMLR, 2020.
Kalpesh Krishna, Yixiao Song, Marzena Karpinska, John Wieting, and Mohit lyyer. Paraphrasing evades detectors of ai-generated text, but retrieval is effective defense. ArXiv, 13408 2023.
Stephen Merity, Caiming Xiong, James Bradbury, and Richard Socher. Pointer sentinel mixture models. In International Conference Learning Representations, 2017.
Susan Zhang, Stephen Roller, Naman Goyal, Mikel Artetxe, Moya Chen, Shuohui Chen, Christopher 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.01068, 2022.
Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Erie Hambro, Faisal Azhar, aurellen Rodriguez, Armand Joulin, Edouard Grave, and Guillaume Lample. Llama: Open and efficient foundation language models. ArXiv, abs/2302.13971. 2023.
Ari Holtzman, Jan Buys, Maxwell Forbes, and Yejin Choi. The curious case of neural text degenera- tion. In International Conference on Learning Representations, 2020.
11

---

Published as a conference paper at ICLR 2024
Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, and Jamie Brew. Huggingface' s transformers: ofate-of-the-an art natural language processing. ArXiv, abs/1910.03371, 2019.
Long Ouyang, Jeff Wu, Xu Jiang, Diogo Almeida, Carroll L. Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray. John Schulman, Jacob Hilton, Fraser Kelton, Luke E. Miller, Maddie Simens, Amanda Askell, Peter Welinder, Paul Francis Christiano, Jan Leike, and Ryan J. Lowe. Training language models to follow instructions with human feedback. ArXiv, abs/2203.02155. 2022.
Mike Lewis, Yinhan Liu, Naman Goyal, Marjan Ghazvininejad, Abdel rahman Mohamed, Omer Levy, Veselin Stoyanov, and Luke Zettlemoyer. Bart: Denoising natural language generation, translation, and comprehension. In Annual Meeting of the Association for Compulational Linguistics, 2019.
pre- pre-training for
Karl Moritz Hermann, Tomas Kocisky, Edward Grefenstette, Lasse Espeholt, Will Kay, Mustafa Suleyman, and Phil Blunsom. Teaching machines to read and comprehend. Advances in neural information processing systems, 28, 2015.
Katzenbeisser Stefan, AP Fabien, et al. Information hiding techniques for steganography and digital watermarking, 2000.
Umut Topkara, Mercan Topkara, and Mikhail J. Atallah. The hiding virtues of ambiguity: quantifiably resilient watermarking of natural language text through synonym substitutions. In Workshop Multimedia & Security, 2006.
Mikhail J. Atallah, Victor Raskin, Michael Crogan, Christian F. Hempelmann, Florian Kerschbaum, Dina Mohamed, and Sanket Naik. Natural language watermarking: Design, analysis, and proof-of-concept implementation. In Information Hiding, 2001.
Mikhail J. Atallah, Victor Raskin, Christian F, Hempelmann, Mercan Topkara, Radu Sion, Umut Topkara, and Katrina F. Triezenberg. Natural language watermarking and tamperproofing. In Information Hiding, 2002.
Xi Yang, Jie Zhang, Kejiang Chen, Weiming Zhang, Zehua Ma, Feng Wang, and Nenghai Yu. Tracing text provenance via context-aware lexical substitution. Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 11613-11621 2022.
Honai Ucoka, Yugo Murawaki, and Sadao Kurohashi. Frustratingly easy edit- linguistic steganography with a masked language model. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, 2021.
Margherita Gambini, Tiziano Fagni, F. Falchi, and Maurizio Tesconi. On pushing deepfake tweet detection capabilities the limits. Proceedings of the 14th ACM Web Science Conference 2022, 2022.
Max Wolff. Attacking neural text detectors. ArXiv, abs/a202.. 17668, 2020.
Vinu Sankar Sadasivan, Aounon Kumar, S. Balasubramaniaan Wenxiao Wang, and Soheil Feizi. Can ai-generated text be reliably detected? ArXiv, abs/2303.111566 1156, 2023.
Souradip Chakraborty, Amrit Singh Bedi, Sicheng Zhu, Bang An, Dinesh Manocha, and Furong Huang. On the possibilities of ai-generated text detection. arXiv preprint urXiv:2304.04736, 2023.
Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. The Journal of Machine Learning Research, 21(1):5485-5511, 2020.
Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. In Symposium Foundations of Computer Science (F)CS'07), pages 14- IEEE, 2007.
Mark Cesar and Ryan Rogers. Bounding, concentrating, and truncating: Unifying privacy loss composition for data analytics. In Algorithmic Learning Theory, pages 421-457, PMLR, 2021.
12

---

Published as a conference paper at ICLR 2024
CONTENTS
Introduction
2 Problem setup and method
2.1
Definition of language model watermarking
2.2
Threat models
2.3
Method
3
Main theoretical results
3.1
Quality guarantee of UNIGRAM- WATERMARK
3.2 Type error of UNIGRAM- WATERMARK.
6
3.3 Type II error of UNIGRAM-WATERMAN WATERMARK
3.4
Security property of UNIGRAM- WATERMARK
4
Experiment
4.1
Experiment setting
4.2
Watermarking results
4.3
Robustness results
4.4
Distinguishing human-written text
5
Conclusion
Impact statements
10
More on related work
15
Additional experiment results
16
B.1 Empirical error rates
16
B.2 Different watermark parameters
16
B.3 Additional robustness results
17
B.4
White-box attack
17
B.4.1
Estimating the Green List tokens
17
B.4.2 Evasion attack (white-box and estimated)
19
B.5 Testing on scaled language models
19
B.6 Results for deduplicated detection
19
Main theoretical results with proofs
20
C.1 Quality guarantees
20
C.2 Robustness Security guarantees
21
C33 No false positive (Type I error guarantees)
22
C.4 Only true detection (Type II error guarantees)
23
13

---

Published as a conference paper at ICLR 2024
C.4.1 On-average high entropy assumption
23
C.4.2 A "homophily" assumption.
24
C.5
Theorem statement on "Only true detection"
25
C.6 Proof of Theorem C.13
26
C.6.1 Many green list tokens with high probability
27
C.6.2 Many green list tokens in expectation
29
C.7 Security property
30
Analysis of Kirchenbauer et al. (2023)
D.1 Soft watermarking scheme of Kirchenbauer et al. (2023)
31
D.2 Sccurity property of Kirchenbauer et al. (2023)
E Alternative detector "Unique" and its desirable properties
32
E.1 Alternative detection "Unique" is robust to Emoji attack and other tricky attacks
33
Technical lemmas
34
14

---

Published as a conference paper at ICLR 2024
A MORE ON RELATED WORK
Watermarking natural languages. The concept of watermarking, which involves hiding identifying information within data, has long history. However, watermarking digital text has been challenging due to its discrete nature (Stefan et al., 2000). Early approaches relied on techniques such as synonym substitution (Topkara et al., 2006), syntactic structure restructuring (Atallah al., 2001), or paraphrasing (Atallah et al., 2002). Later, advancements in modern neural language models led to improved methods that move away from rule-based approaches. Different approaches have been proposed, such as encoding messages by context- aware lexical substitution (Yang et al.. 2022) or using mask-infilling models for editing text (Ueoka et al., 2021). Recent studies (Zhao al., 2023; Kirchenbauer et al., 2023) explore modifying the logits of language models during token generation and embedding invisible watermarks in the decoding process. Our objective is to develop a robust watermarking technique for natural language models that maintain high text quality while effectively concealing identifying information.
Post-hoc detection. Rather than watermarking, alternative approach involves developing detection models for post-hoc analysis of machine generated text. Some detection methods use statistical outlier detection techniques without requiring additional training. For example, GLTR (Gehrmann et al., 2019) assesses the expected probability of individual tokens and applics thresholding to identify Al-generated content. DetectGPT (Mitchell et al., 2023) suggests that Al-generated passages tend to reside in the negative curvature of the log probability of texts. Another set of methods relies on classifiers that are fine-tuned to distinguish between human-written and muchine-generated text. Initial efforts in this domain focus on detecting fake reviews (Hovy, 2016) and fake news (Zellers et al., 2019). More recently, OpenAI releases a web interface that uses a finetuned GPT model for this discrimination task (OpenAI, 2023b). However, as language models improve, Al- --generateed text is becoming increasingly similar to -umanngeneraaed text, making more challenging to detect. Gambini et al. (2022) find that existing detection strategies designed for GPT-2 struggle with GPT-3. Moreover, known detectors are found to fragile adversarial attacks (Wolff, 2020) and biased towards non-native English writers (Liang et al., 2023).
machine-generated
Impossibility results? Sadasivan et al. (2023) poses the question of whether detecting machine- generated text is possible and argue that as the human distribution and LLM distribution of texts get closer, any classifier will have to either have a large Type I error or a large Type II error. The authors also argue that (in Corollary 2) if the watermarking scheme can be learned then paraphrasing attacks either evade the detector or also classify humans with a similar distribution as false positives. This does not invalidate our results that in Theorem 3.1 that the watermarked LM M and original LM M statistically close - in fact, indistinguishable in the "differential privacy" sense. But the indistinguisaability is for each token. As the number of tokens gets larger, they will eventually become distinguishable, that why our Theorem C.4 and Theorem C.13 are not contradicting Theorem 3.1. This argument was initially pointed out by Chakraborty et al. (2023), showing that detection is possible.
made no theoretical claim about paraphrasing. We do claim
Language model watermarks with provable guarantees. Concurrent to our work, Christ et al. (2023) consider the problem of formally defining watermarking language models and propose a construction with provable guarantees. The main differences between their work and ours are:
In Christ et al. (2023), the watermarked distribution is computationally indistinguishable (i.e., indistinguishable against probabilistic polynomial-time algorithms) from the un-watermarked distribution whereas in our case, we insist that the watermarked distribution is statistically close to the un- watermarked distribution (of each token). The Type-I/Type-I error guarantees and the security properties are qualitatively different in both works.
We both use different approaches to achieve our definitions. The advantage of our construction is that it satisfies robustness to edits property whereas they have no such guarantees. On the other hand, our construction uses very different set of assumptions (e.g., high entropy) on the language model and prompt that appears to be incompatible with theirs.
Finally, we implement our construction and conduct a thorough empirical evaluation to demonstrate its practicality while they don't provide any implementation of their construction.
Statistical vs Cryptographic Watermarks. Christ et al. (2023) and Aaronson (2023) are examples of cryptographic watermarks, while Kirchenbauer et al. (2023) and this paper study statistical
15

---

Published as a conference paper at ICLR 2024
watermarks. There several prominent differences that make it a bit challenging to compare the two kinds, but we will try. To start, we argue that both Christ et al. (2023) and Aaronson (2023) similar definition of language model watermarks Definition 2.2 and considered similar set of properties. Specifically, the "soundness", "completeness" from Christ et al. (2023) directly map to our "Type error" and "Type II error" requirements. As understand from the materials in Aaronson (2023)'s talk, their "indistinguishabiltt"" is form of performance guarantee for M. The difference to ours is that they require (in our notation)
P Next token] = E
PP
Next token|k]
=
P
Next token]
M(proopp)
Mpproppp)
M(prompt)
where the random key is marginalized out. while our results require that for every k the next token
Next token[k] m8
Next token]
M(prompt)
M(prompt)
to be statistically close (in the same sense of 8-differential privacy). By our metric, however, Aaronson (2023)'s watermark does not appear to satisfy any nontrivial 6 guarantce, since it only requires unbiasedness. For that reason, the detection guarantee and its tradeoff with quality that discussed in Remark C. 15 is not applicable to the cryptographic watermarks.
B ADDITIONAL EXPERIMENT RESULTS
B.1 EMPIRICAL ERROR RATES
We perform experiments on two datasets (OpenGen and LFQA) using three different models (GPT2- XL, OPT-1.3B, and LLaMA-7B). Table presents the error rates, showcasing the sensitivity of the resulting hypothesis test based on observed 2-scores. The results demonstrate that there are no Type-I (false positive) eтrors for all models, with true positive rates exceeding 0.94 for a threshold of 2 = 6.0.
2
6.0
7.0
Dataset
Model
FPR
TNR
TPR
FNR
FPR
TNR
TPR
FNR
GPT2-XI.
1.0
0.943
0.057
0.0
1.0
0.832
0.168
OpenGen
OPT-1.3B
0.0
1.0
0.998
0.002
0.0
1.0
0.996
0.004
LLaMA-7B
0.0
1.0
0.974
0.026
0.0
1.0
0.911
0.089
GPT2-XL
0.0
1.0
0.948
0.052
0.0
1.0
0.889
0.111
LFQA
OPT-1.3B
0.0
1.0
1.000
0.000
0.0
1.0
0.997
0.003
LLaMA-7B
0.0
1.0
0.976
0.024
0.0
1.0
0.942
0.058
Table 4: Empirical error rates for watermark detection using different models on two datasets. All models employ nucleus sampling with 5 2.0 and 7 0.5. No Type-I (false positive) errors observed across all models.
B.2 DIFFERENT WATERMARK PARAMETERS
We conduct an analysis understand the impact of changing watermark strength (8), green list size (7), and sampling methods on two datasets. The results are summarized in Table 5. When using nucleus sampling with a fixed 7 = 0.5, increasing the watermark strength resulted in higher true positive rates (TPR), but it also led to an increase in perplexity (lower quality). Furthermore, for the same watermark strength ó, varying the green list ratio from 0.25 to 0.5 and 0.75 showed improved detection results with smaller 7. Additionally, we explore different decoding methods, transitioning from nucleus sampling to multinomial sampling and beam search. Remarkably, watermark detection performed effectively with all decoding methods. It is worth noting that the perplexity score for beam search significantly lower than that nucleus sampling. However, beam search tends to generate shorter sequences with repeated words.
16

---

Published as a conference paper at ICLR 2024
6.0
7.0
Dataset decoding
8
PPT.
FPR
TNR
TPR
FNR
FPR
TNR
TPR
FNR
nucleus
1.0
0.5
18.37a. 45
0.0
1.0
0.576
0.424
0.0
1.0
0.310
0.690
nucleus
2.0
0.5
19.42s.78
0.0
1.0
0.998
0.002
0.0
1.0
0.996
0.004
nucleus
5.0
0.5
19.
19.441n.02
0.0
1.0
1.000
0.000
0.0
1.0
1.000
0.000
nucleus
10.0
0.5
19.2 19.2018.01
0.0
1.0
1.000
0.000
0.0
1.0
1.000
0.000
OpenGin
nucleus
2.0
0.25
57.9
0.0
1.000
0.000
0.0
1,0
1,000
0.000
nucleus
2.0
0.75
20.037.67
0.0
0.820
0,180
1.0
0,485
0.515
2.0
0.5
1.750.50
0.0
0.951
0.049
0.0
1.0
0,924 0.076
4-beums
2.0
0.5
1.830.97
0.0
1.0
0.992
0.008
0.0
1.0
0,982
0,018
6-beums
2.0
0.5
1.891.10
0.0
1.0
0.984
0.016
0.0
1.0
0,982
0.018
8-beams
2.0
1.96, 23
0.0
0.986
0.014
0.0
0.984 1.0
0.016
nucleus
1.0
0.5
18.65 18.633.19
0.0
1.0
0.455
0.545
0.0
1.0
0.199
0.801
nucleus
2.0
0.5
19.14
0.0
1.000
0.000
0.0
1.0
0.997
0.003
nucleus
5.0
0.5
15.37
0.0
1.000
1.000
0.000
nucleus
10.0
0.5
16.07 14.25
0.0
1.0
0.998
0.002
0.0
1.0
0.998
0.002
LFQA
nucleus
2.0
0.25
15.27
0.0
1.0
1.000
0.000
0.0
1.0
1.000
0,000
nucleus
2.0
0.75
19.44s.20
0.0
1.0
0.893
0.107
0.0
1.0
0.582
0.418
m-nom.
2.0
0.5
3.172.39
0.0
0.934
0.066
0.0
1.0
0.914
0.086
4-beams
3.242.85
0.0
0.014
6-beams
2.0
0.5
3.202.52
0.0
0.994
0.006
0.0
1,0
0,994 0.006
8-beams
2.0
0.5
3.132.37
0.0
1.0
0.994
0.006
0.0
1,0
0,992
0.008
Table 5: Comparison of empirical error rates for watermark detection using nucleus sampling, multinomial decoding, and beam search. Each row represents the average of 500 sequences. While sequences generated with beam search exhibit lower perplexity, they tend favor shorter outputs, potentially resulting in less diverse text.
B.3 ADDITIONAL ROBUSTNESS RESULTS
In addition to the previously discussed robustness evaluations, provide further analysis of method's resilience against paraphrasing attacks and editing attacks. The results are presented in Figure 4. Notably, our proposed method -ATRRAAAAR consistently outperforms the baseline approach (KGW+23) across various datasets and attack scenarios. This demonstrates the superior robustness of our method in accurately detecting watermarked text.
B.4 WIITEE-OOX ATTACK
potential attack for UNIGRAM- WWM-M-AAARRKK is estimate the fixed green and red list. Then the adversary may attempt to bypass detection using these estimated lists. We conduct experiments on white-box attacks and we find that is difficult accurately estimate the green list. Even if the green list is known, our watermark is still somewhat effective thanks to our added robustness.
B.4.1 ESTIMATING THE GREEN LIST TOKENS
The question arises: how can the adversary estimate the green list? We simulate an adversary attempting to learn the green list tokens by querying the model multiple times. The adversary collects token distributions from watermarked text and compares them to natural human distributions.
In our experiment, we query the LLaMA-133 13B watermarked model with watermark strength 5 2.0. watermark ratio 7 0.5 (same setting in the paper) 2500 times, collecting 0.7 million tokens of watermarked text generated from the prompts in LFQA and OpenGen dataset.
Then we simulate three human data distributions:
1. The human response from the same prompt (LFQA and OpenGen dataset). The corresponding human output is 0.4 million tokens. We denote as the "LFQA & OpenGen dataset"
2. Most times, human responses not known. So collect 2000 samples from the C4 (Raffel et al., 2020) dataset to form an approximate human dataset with million tokens. We denote it as the "C4 dataset".
17

---

Published as a conference paper at ICLR 2024
1.0
0.3
0.0
Thus: Roo/DA Rite:
0.6
0.5
0.4
0-
1.4
30MER KOW 23 AUC: 0.002
0.2
0.2
Chatget Dur
0.343
20PPE Dus AUCI 6.964
0.0
0.0
0.0
(a) UNIGRAM- WATERMARK against paraphrasing attacks LFQA dataset with LLaMA-
7B.
1.0
1.0
7.0
0.8
0.81
0.8
0.6
0.6
2.6
0.
1aptoce-21 K0B
Reploce-.11 0pm
AUC 0.323
0.4
Desto01 SGM
20 Dus
43. 052
A-C: 1.)
2.4
Swepp: Cuts AUC
Siup KSW
Repboce-3.3 K2
2.04
Soap KGWW AUC
0.2
Reploce-255 62
AU7:9.783
02
05005 GGW-23
0.2
KGW0422 AUC: 0.031
Reploce-25 0um
AUC 0.86)
01005 Ous
AUC 6954
Svap 0.5 Curs
AUC
0.0
9.0
0.5
0.6 Pabi Bace
Fable Per Race
Pes
(b) UNIGRAM- WATERMARK against editing attacks OpenGen dataset with LLaMA-7B.
We vary the rates of synonym replacement, random deletion, and random swapping (0.1,
0.3, 0.5) to demonstrate different attack scenarios.
Figure 4: ROC curves with corresponding AUC values for watermark detection against various attack methods.
To simulate the distribution from non-native speakers. We also collect non-nan non-native speaker (TOEFL essay) dataset from Liang et al. (2023) with 12k tokens. We denote it as the "Non-native dataset".
We calculate token frequencies for the three "human" datasets and the watermarked dataset. We use the following decision rule (Algorithm to decide whether a token green red.
Algorithm 3 Estimating the Green List tokens
1:
for every token in the vocabulary V do
2: A(t) f Frequency(e in watermarked text) Frequency(y human text)
3: if (()) 2 0 then
4:
v is in the Green List.
5:
else
6:
v is in the Red List.
7:
end if
8:
end for
The estimation results for the green list tokens are shown in the table below.
Dataset
TPR
FPR
FNR
F1
LFQA & OpenGen dataset
0.692
0.830
0.170
0.755
C4 dataset
0.591
0.806
0.194
0.609
Non-native dataset
0.323
0.923
0.077
0.463
The results suggest that while it is possible make non- trivial inferences about which token is green, is hard to say for sure. Notice that we are using a rather big watermark strength. For smaller and more esoteric contexts (prompt, e.g., Non-native TOEFL dataset), such determination is harder.
18

---

Published as a conference paper at ICLR 2024
B.4.2 EVASION ATTACK (WHITE- BOX AND ESTIMATED)
In situations where the adversary has either an estimated version or full knowledge of the green and red lists, they can formulate evasion strategy. We simulate this by assuming the adversary employs WordNet from NLTK to identify token synonyms. Tokens identified as in the green list are replaced with red list synonyms, noting that some tokens may not have synonyms may only have green synonyms.
Green List
Detect AUC
Avg PPL (eval by GPT-3)
No attack
1.000
45.413
Know all green tokens
0.8413
193.410
Estimated from IFQQA & OpenGen dataset
0.9397
189.423
Estimated from C4 dataset
0.9291
189.070
Estimated from Non-native dataset
0.9998
125.380
Table 6: Evasion attack results: analysis of detection AUC and perplexity.
The results in Table show it is difficult to evade detection even with known green list tokens. The detection AUC for the watermarked text is still somewhat high. In addition, the honest attempt to evade the attack by automatic synonym replacement has led to significant drop in the text quality.
B.5 TESTING ON SCALED LANGUAGE MODELS
OpenGen
LFQA
LLaMA-13B
No attack
1.000
1.000
ChatGPT attack
0.783
0.854
LLaMA-65B
No attack
1.000 0.831
1.000
ChatGPT attack
0.697
Table Detection results (TPR at I % FPR) for scaled models LLaMA-13B and LLaMA-65B.
We conduct supplementary experiments on the scaled models LLaMA-13B and LLaMA -65B, Using the same experimental settings as in the main paper. preliminary results show that method maintains effectiveness on these larger models. For LLaMA-13B. we are able to use the same test set size in the original paper. For LLaMA-65B, due to computational constraints, test sample of 100 sentences. The results (TPR at 1% FPR) are shown in Table
B.6 RESULTS FOR DEDUPLICATED DETECTION
OpenGen
LFQA
LLaMA-13B
No attack Unique Detector
1.000
1.000
ChatGPT attack Unique Detector
0.679
0.773
LLaMA-65B
No attack Unique Detector
1.000 0.783
1.000
ChatGPT attack Unique Detector
0.682
Table 8: Detection results (TPR at 1% FPR) with "Unique" detector.
An alternative detector, named "Unique" demonstrates improved robustness in detection and offers advantages in controlling false positives with ease (Section E). We conduct experiments to evaluate deduplicated detection performance, with the outcomes presented in Table 8.
19

---

Published as a conference paper at ICLR 2024
C MAIN THEORETICAL RESULTS WITH PROOFS
In this section, we state and prove the guarantees for UNIGRAM- WATERMARK which certifies the required quality, correctness, and security properties of language model watermarking scheme from Definition 2.2.
Symbols and mathematical notations. We use P(., El.] P[---] and E[-1-] denote the probability, expectation operator, conditional probability and conditional expectation respectively. Whenever there is ambiguity on which distribution the random variables are drawn from, we explicitly state them, g. P(x,)))=((X < 3/Y² v). or equivalently P[X < 3 = y: (X ~ Dj. To avoid clutter, we do not distinguish between random variables and constants as the distinctions are clear sequence of tokens y. 1-12..11 || lloe denotes the standard &g and loo -norms vector. addition, [n] is shorthand for {1, 2, ... n). Other symbols and their meanings will be defined as encounter them.
from the context. Boldface symbols denote vector, e.g., a probability mass function
C.I. QUALITY GUARANTEES
We start by providing a strong utility analysis of the watermarked language model than the "perplexity" bound from (Kirchenbauer et al., 2023). Our results work for the entire family of Rényi-divergence and imply guarantees in Kullback-Leibles (KL) divergence and Total Variation-distance.
The Renyi-divergence of distributions P, Q is defined
dP dQ
(Pll)) a
log
E z~Q
where aQ
dP is the Radon-Nikodym derivative. When + 1, the Renyi divergence converges to the KL-divergence. Additionally, when a = 0.5, it serves as an upper bound for the TV-distance.
On the technical level, we leverage a surprising connection to modern machinery developed in the differential privacy literature known as "bounded range" analysis (Dong et al., 2020) of the classical exponential mechanism (McSherry and Talwar, 2007).
Theorem C.1 (Restatement of Theorem 3.1). Consider h as the input to the language model at step t, denoted as h [xx 11: Fix green list G. Let represent the watermark strength. For any h. the a-th order Renyi-divergence between the watermarked probability distribution P. pe(-)h) at time step and the original probability distribution P: (c)- satisfies:
Yh, max (pillp)), Da (p.llp.) & min a.
(622/1 /8}.
Proof. We define 8, when v E R and 8, when G. Using this definition, have:
exp(eo + 5p) I exp(o) cxp(Ee) =ea 25 p(ulh)
p(c(h) En exp(ew dw) exp(-6) En exp(ew)
Similarly, p(e 2 e 26 20p(v)))
Consequently, p and p are 28-close in terms of max-divergence, which can be interpreted as (c, 8)- indistinguishable similar to the concept of Differential Privacy (Dwork et al., 2006) with 5 = 0 and = 28.
Additionally, ((u(h) and hh) satisfy S-BoundedRange (Proposition Dong et al. (2020)) with parameter 5, since the changes to l, is monotonic. Lemma 3.2 in Cesar and Rogers (2021) shows that /8-cconcentratedd differential privacy, which says that D. (pll)) s 8a 6-Bounded Range implies Sopplieso//-conneeeeee
for all > 1 (where Da represents Rényi Divergence of order a). Specifically, when 1, the KL-divergence satisfies (kl(p)))) < 8²
Furthermore, S-BoundedRange implies 5-DP (or rather (6. i0--idiistinguushablltyy since we are dealing with just two distributions rather than a family of neighbor distributions). follows from the that
DKL. (pll)) S D2o s
20

---

Published as a conference paper at ICLR 2024
Corollary C.2. For any prompt x, the KL-divergence between the probability distribution of the watermarked sequence and the original sequence satisfies:
Yx, max DKL (P( (=ml)))pp(((())
1.m (1).)=))) DKL (p(y (x) ( (z)) & miminnd, no² n8/
Proof. The proof follows from the adaptive composition theorem for Renyi-divergence, and max- divergence (from the DP literature) for the autoregressive decomposition of p (x) and p and then invoke Theorem 3.1 for each factor.
C.2 ROBUSTNESS/ SECURITY GUARANTEES
In this section, we provide the proof for Theorems 3.7, D.I, and 3.1 to ensure completeness and precision. We begin by restating the theorems and providing the corresponding proofs with necessary modifications.
Theorem C.3 (Robustness to editing (Restatement of Theorem 3.7)). Let y .y Yn represent the watermarked sequence. Suppose the adversary A follows Definition 2.2 and outputs modified text u [u1,.... |. Following Equation we calculate 2-score By and Zu. Assume edit distance between y and (denoted as 1) satisfies n. Then we have
(1 + 7/2mm
(1 1-7/2 }.
Zu 2 Ey max
VT.
Vn Tj
In particular, when S
2ty [147/2]7 we can drop the second term in the max.
Proof. Define bivariate function [(x y)
By Taylor's theorem
ko. fx, +)+ @zf(1 -Koy kw)) 0yf(1 (x kzy ky)
kz kiy
Vu (V kin
his
yky
f(x,8)
2 Kyy
where ky is between O and kn and ky is between and ki. We also know that | S &: and Ikyl ki.
lower bound of the above can be obtained by finding an upper bound to
7ky R 2 Ky
by 2/ ky
ky
First observe that we can always choose lig = k. Next we discuss two possibilities of ky. If ky is negative, then choosing ky k and maximizes the bound, which gives (1+4/2/4
If ky is positive, then should always choose ky ky to maximize the expression, which gives us an upper bound of
ky y ky
A + (2 - kyy 3y
34 Vy ly
7V y - ky
Vy ky
2
We will discuss cases again, the first case is when k 22y/2 /2 < 0. In this case, the function
g(u) = a/u + bu with a < 0 has derivative of -a/u² + 2 0, thus is monotonically increasing. Thus we should choose ky = O. The second case is when 72/2 > this case the 0 in the above gu)) and g(u) is convex, thus maNuminnSSu.... s(u) max (g(MNaxx) (umin)) Thus we should just compare the two cases when ky and ky k, i.c., max (1-7/2)k 3.
Ve' VV-k
Collect everything together, we get an upper bound o (1 + 7/2)k
k
(1 - 7-2/2)k
(1 (1+r/2)/
(1 - (1-//2)/
max
max
V
V
Vy
V
Vy- -
i...,
(1 + (1+7/2)K 7/2)k
(1 7/2)k
fa k:z 1 - kw) 1550-Saa (x.
max
V
Vy -
21

---

Published as a conference paper at ICLR 2024
Now notice that our 2-score has the same form the fzz function. We take y and I = G. Instantiate & be the maximum number edits 17. Observe that given that the adversary has bounded edit distance, each operation of "insertion", "deletion", or "edit" can, at most, alter one token from the green list to the red list. They also can only alter the length by the numher of edits. The above result translates into
(1 + 7/2)m (1 (1-7/2)0
Zu 2 by max
vn
vn
where 7) denotes the edit distance between y and u.
The robustness theorem above implies the security guarantees as we discussed in Corollary C.23.
C.3 No FALSE POSITIVE (TYPE I ERROR GUARANTEES)
Theorem C.4 (No false positives) ). Consider y Vinn as any fixed suspect text. Let N =: |] and G C [V] satisfying [G] = yN. G selected through Algorithm 1, using a uniform random
choice, Let yla denote the number of tokens in G and Zy = wla-mm as in Algorithm 2. Then the following statements hold true:
Vny(1-7)
1. Assume n 2 L, then
Eluylalul yn and Bizyly [y] = 0.
Define Cmax (y) = maxie[N] Eラ= 1 i) and (z) == 1. Ei (E)= 1 = i))?, then
with probability (over only the randomness of G).
P Iull 2 yn + (644nV1og(9///) + 16C (og(9/))) Sa
or equivalently (when n 2 1)
64V log(9/a)
16C log(9/a)
by
y
Sa.
(n
Proof. To prove the first statement, observe that any fixed token has probability y be included in the green list, thus by the linearity of the expectation and the independence of y in G.
Elyllly = Σ B E G)lb) = Σ ===m m.
Next, we will prove the second statement by applying Lemma F.1 to obtain the result stated in the third statement. Let d:j 1(j I yN) Ei= 1(ye = i). By our assumption 0 aij Cmax for all j.j. Observe that Σ I, (1) is identically distributed with lylc-
1/16 /1//////// /a), we get that with probability 1 a. By Lemma F.1 with = 16 (00
16 log(9/a)
lllle 7m| 2
NynV + 16C log(9/a)
N
where we used that 1/16 < 9 and the fact that only yN columns of the oi,j matrix di,j is nonzero, and for each non-zero column L2-norm of the column is bounded by VnV by definition of V. The result for the z-score follows trivially.
Remark C.5 (Wide applicability). Note that the theorem does not impose assumptions on how is generated. covers any procedure (including human generation) that produces y in a manner independently of the secret partition G. In cases where is generated by language model, it could be the output of greedy search from pyy x. y V1--1)) 1), nucleus sampling, beam search, or any other decoding methods.
22

---

Published as a conference paper at ICLR 2024
Remark C.6 (Diversity parameters). The V and Cmax parameters in Theorem C.4 measure the diversity of the suspect text y and are necessary for the high-probability bound. As an exam- ple, if the prompt says "Repeat "Goal" for hundred thousand t times like soccer commentator. Then the resulting generated sequence will be "Goal goal goal and has either green tokens 0 green tokens. No meaningful Type error bound can be obtained.
Remark C.7 (Controlling false positive rate). The theorem implies that if we choose
64V log(9/a) 16Cmax (9/()/ then the false- dalle-positive rate is smaller than a. Note that V and function of V. maxx that achieves a a-Tyye error guarantee with a fixed a for all inputs. In particular, the Type
1-7 Cmax can be computed directly from y. allowing to choose input-dependent
/xy(1->)
I error decreases exponentially as we increase the threshold
C.4 ONLY TRUE DETECTION (TYPE II ERROR GUARANTEES)
For bounding the Type II error, i..., false negative rates, we will work with our proposed method that generates y from the language model, i.e., sampling from the watermarked distribution P recursively one token at time.
Let's first recall few notations. h is the input to the language model step i.e. h [ac V1.--1l Let represent the watermark strength from Equation 1. The green list G C [N] is a random index set of the vocabulary of size >V.. The watermarked probability distribution p. P.( h) time step L. The process of generating the sentence , , Y/ involves recursively sampling from p.. which we refer to as a "roll-out" procedure.
:
We need to make few assumptions about the language model's probability distribution p and the prompt æ. We will first state them and then explain why these are natural and arguably needed for the Type II error to be small.
C.4.1 ON-AVERAGE HIGH ENTROPY ASSUMPTION
The first such assumption requires the probability of the roll-out to be "sufficiently diverse" on average. We will introduce the notation |pl|a E/
Assumption C.8 (On-average-hipg high-entropp). We say a language model's probability distribution p with prompt æ satisfies Ç aaaaaagrrgehhhhhhee high-entropy if
| S
1=1 2p(1))
This assumption requires the distribution of the roll-out to be sufficiently diffuse on average (either in expectation or with high probability).
The purpose of these assumptions is to rule out the cases when Vin is almost deterministic under and perturbing the logits by does not change the distribution much at all.
For example, if the prompt writes
"Generate the English alphabet in capital letters for 200 times please."
Then the language model would generate
"ABC... XYZ, ABC XY2,
Despite that the generated sequence is very long, i.c., n is as large as 5, 200, the added watermark does not change the distribution very much at all. To this, if p(ys "C"læ. h) > 1 for a tiny c, and then by our quality guarantee, P(ys- = "C" [z, h)
cc
Quantitatively, for nearly uniform Pt. & O1INN, if p. concentrates when a football commentator exclaims "Goal goal goal goal .", then we cannot obtain better bound than the trivial & < 1. In the alphabet example above & < 1/26.
single token for all e.g..
23

---

Published as a conference paper at ICLR 2024
Why is it called entropy? Assumption C.8 is related the "high-entropy" assumption in Kirchen- bauer et al. (2023) but for a slightly different kind of entropy. In a more formal sense, the quantity ||P:| 1 is connected to the Tsallis entropy of order 2, defined as (2(pr) ks |p,ll") where kB is known as the Boltzmann constant. Our assumption requires the expected Tsallis entropy of the conditional distribution pa over the roll-out of p to be larger than k {) average among
t t= T..
For high-probability result, we also need stronger version. Assumption C.9 On-average-high-enttrn
(high probability)). We say that language model's probability distribution p with a prompt æ satisfies (E, jj-oo-aaverrg--hhhh-entttoyy with probability at least 1 - 3 over the generated sequence Vi:
1
max
Σ 1=1
Pt
Pell
Σ
P
P 12 SE.
1=1
t=1
The behavior is similar to that of the expectation version of the assumption. When Pt is nearly uniform, p. = O(1/N), then 5 = O(1/VN). When p: supported only on one token, then Ç - 1. In practice, & is small constant. As we will present in the main theorem, as long as & = 8, the number of green list tokens is guaranteed to grow faster "yn as n gets larger.
One may also ask whether it is necessary to make entropy assumptions on the conditional probabilities instead of the marginal probabilitics induced by p or p. but this is unfortunately not sufficient as illustrated in the following example.
Example C.10 (Marginal high entropy is insufficient). Let the prompt æ be
"Generate the first token uniformly at random, then repeat the token you generated for the remaining n- tckens",
In this case, a good language model that follows the instruction will have IP = =)= 1/N for all and all I,.., n marginally, which implies that the entropy is the maximum and for any green list G, Pp E G) 7, On the other hand, with probability 7, lyle = n and with probability There isn't 't any concentration around yn possible. Moreover, check that if we apply 7e
1-7, lyla
watermark, then (yt G) +1--3] for all t and all G. This changes the probability of seeing |yla = n slightly but the two world remains indistinguishable.
C.4.2 A "HOMOPIILLY" ASSUMPTION
The second assumption that need to make is called "homophily", which says that increasing the probability of a group of tokens by adding the watermarks will not decrease the probability of generating the same group of tokens in the future as the language model rolls out.
Assumption C.11 ("Homophily"), We say language model's probability distribution p and prompt x satisfy "homophily" if for any G, the corresponding watermarked p satisfies that
(y G)
P
(y (UE
h<p(-|a) L
h-pp (ae) Lu-p(-1h.a))
where h denotes the generated sequence before y..
This assumption says that by increasing the probability of tokens in G, the induced distribution of the prefix h cannot counter-intuitively reduce the probability of tokens G in the future on average.
The assumption is not unreasonable, because we expect language model to be more likely to refer to text it has generated the prefix than those that did not appear in the prefix.
This "homophily" assumption is needed to rule out the unnatural situation where increasing the green list tokens initially ends up reducing the number of green list tokens the long run. To illustrate this consider the following example utilizing the prompt:
æ = "Randomly select a color, state what it is. Then write a short poem about it without naming this color at all."
24

---

Published as a conference paper at ICLR 2024
The generated text from commercial language model is
"Color choice: green. Emerald whispers in the meadow's sway, Life's s verdant rhythm in ceaseless play. It cradles the world in a leafy embrace, silent serenade to nature's grace."
Notice that the token "green" E G, it increases the probability of the language model generating "green" at the beginning. However, regardless of the text's length, the subsequent portion of the generated will contain the word "green", instructed by the prompt. This decreases the expected number of times the token "green" appears.
To hammer it home, consider the following more quantitative construction of that works no matter which random green list G realizes.
"Choose the first k token by random sampling without replacement: Then sample from all but the token you choose
uniformly for n-k rounds."
It's easy calculate that the expected number of times any token appears in language model that perfectly follows the instruction will be n/N. However, the watermarked language model, let's say we use a very large d such that the first & tokens are from the green list, then the expected number k + >N-k (n-k)(n which is bounded by k = Y N-k
of times a green-list token appears NN
7NV
instead of growing linearly in n as in the original language model.
To obtain concentration bound, also need stronger version of the homophily assumption as follows.
Assumption C.12 (High probability on-average homophily). There exists coupling joint distribution of i and i.m where marginally Vı.z p(-/2), Vim p(+|x)) such that for any G, with probability 1 - 3 over the joint distribution,
Po 11
The reason for defining the existence of a coupling is for technical reasons, but the purpose of the assumption is identical to that of the in-expectation version.
C.5 THEBRRMM STATEMENT ON "ONLY TRUE DETECTION"
Now we are ready to state the main theorem.
Theorem C.13 (Only true detection). For a fixed language model M and prompt a. The sentence y tm generated from M(x) where M is an output of our watermarking scheme Watermarks, (M)) with parameter 8,7 Then the following statements are true.
1. Assume homophily (Assumption C.11), then
E Elylel
2 1 (c 1h 711 ye
||pa||2.
Ma (p(((a))
In particular, if Assumption C.8 condition is true with parameter { (1- parameter 1, then
(1+((60 11sje for
e
Elyaa 2 ny (1 (E5 1)(1 ( 1 (e (6- 1)7
- n/1 -1n -
or equivalently B[zy] 1 (e 1)7
Assume high probabbtbyy version of homophily (Assumption C.12). There exists a parameter C that depends only 8, y such that with probability least B for any 3 > 0 (over both G and
25

---

Published as a conference paper at ICLR 2024
y ~~ y~p(11,, G)
nye"
|1 2 1+ (e - 117
2n log (6/3)
- -C,,y log 27(n+
R Σ |p: +
n
11
Pall
Σ
Pr
ac
+
P 11
B
1=1
1=1
1=1
In particular, for a parameter 0 < <n<1,
8 8log(6) (6/ 7 7
T
=0(1//3)
(3)
(1-x) x1-x))--(11- -)) -113
and Assumption C.9 condition is true with parameter (E,3/3) where
(1 - (1 - -7) - -1)
5
Ō()),
(4)
8C (1 - + e log²
(7(m=-1)
3
then
P Ilvlla < (7(1 + (c ( 1)(1 7) + veb
k(e 1) ny
=
PP By <
1 1 (e 1)7
S..
Remark C.14 (Exponentially small Type I and Type II error guarantees). Recall that according to Theorem C.4, in order to have false positive rate controlled at level a, we need set the threshold T 2 Vlog(1/a) for sufficiently high-entropy sequences. Theorem C.13 says that we want the false negative rate to be smaller than 3, we only need the threshold X λōn under similar (slightly different) high-entropy sequences for ri Z / Observe that there a wide range of valid choices of for us to have detection algorithm that does not make Type I or Type II error with high probability. These observations together suggest that we can afford to choose 8 x 1/v/ if the sequence is sufficiently high-entropy.
Remark C.15 information-theoreticc optimality). The sample complexity of n > 1/8² is information- theoretically optimal (up to logarithmic factor) in 8 because, our accuracy guarantee (together with the composition theorem) indicates that the Kl--divergence between a sequence of length n generated from and that generated from P is no² indistinguishable, i.e., n > 1/82 for any classifier even the uniform most-powe poot--l Neyman-Pearee information, c.g., o and which we do not have) to make no mistakes with constant probability.
likelihood-ratio test (which requires additional
C.6 PROOF OF THEOREM C.13
In the false negative cases, y is drawn from the watermarked language model M. To be explicit, let us write y = [...... In] D i.n. Now let's also define a hypothetical (possibly coupled) sequence Vim which is drawn from the original (un-watermarked) language model M.
For convenience, we define the following shorthand p(G) = Py-ply E G}. for a probability mass function p defined the vocabulary V. Specificallyy, (G))): means Pp 1) [y E G),
parameterized by a fixed green list G. Similarly, (G y irr-1) denotes Py-pe 3) 1 G).
The proof of Theorem C.13 considers the following decomposition
lylG =ly la
Σ Ep. (G
(5)
+ Σ ( - Σ (C
(6)
+ Ep(G)
steps to prove a lower bound to each of the three terms. We will start with the high probability bound (the second statement in Theorem C3) then deal with the expectation.
26

---

Published as a conference paper at ICLR 2024
C.6.1 MANY GREEN LIST TOKENS WITH HIGH PROBABILITY
To obtain a high-probability lower bound, requires us to obtain concentration for each of the three terms. Specifically,
1. To bound Term (5), randomness in y to show ly is close to E, Pi (G
Lemma C.16 which invokes Martingale concentration over the
2. We will show Term (6) is non-negative with high probability by using the homophily assumption (Assumption C.12). This allows to study the roll-out V1.t-1 under MMæx) (or p) by studying hypothetical alternative roll-out V1:1-1 sampled under M(x) (or p).
3. Then we control Term (7) by first Taylor expanding it into quantities involving Pr (G instead of (Gl then apply concentration inequalities for each expanded terms over the randomness of G' (while fixing V1tt-1 to obtain a high probability lower bound. Proposition C.19 gives the results.
We start by tackling (5) via Martingale concentration.
Lemma C.16. For any green list and prompt x.
E
yll
Σ
W E EG]
= 0.
wap p (a
Moreover, with probability least
B over the roll-out
n
yy G
(t E v 1og(333)
Proof. We fix G and construct a martingale sequence X1, X2, . Xn where Xy = 0 and:
X; X 1(ye G)
P yo-p(-1la.vaa
[ye E G/.
Check that E[X X, The underlying filtration is the sigma-field generated by y1.r-
The claim about the expectation follows from that Xo = 0 and an inductive argument following the tower property of conditional probabilities.
By the fact that XX, X < 1 we can apply Azuma-Hoef inequality and get
IP []X,, - E[X,]] 2 u) 2e 2e
Check that by an inductive argument E[X,] = O. So we get that with probability at least 1 - 5
"
X,,
Σ 1 G)
Σ
P
[ E G]
S V 2n log(2/8).
t=1 ---((
To handle (6), we apply Assumption C.12 with parameter 3/3, which says that with probability 1 8/3 (6)2 O. This converts a roll-out from & ~ P to a roll-out from the original p.
Before deal with (7), let write lemma that rewrites p. (G into more convenient form.
Lemma C.17. For any t, h. Fix G. Denote short hands P(G) = PperplCCe..h E G] and PGG) := Py..pi((m..t)ll E GT.
(1
(6 - -)(11(1-(G))
P(G) = 1+ ( 1)p(G)
I+ - (+p()) p()).
27

---

Published as a conference paper at ICLR 2024
Proof. By definition,
Eyeg eluto
P(G) Eyea E Eygoreh
e'p(G)
+1 -Pp(GG) 1+ 1)p()) P(G)
P(G)
=11
(e -1)(1-p((())
1t (e - 1)p(G) P(G).
The lemma implics that P(G) 2 GG) and that if p(G) is bounded away from 1, P(G) 2 (1 (GG)..
Lemma C.18. For any I, h. Fix G.
y P(G) 2 1+ (e - 1)7
e
(D(G) -3) -e((()) 7)2
(1 (e5 (1
Proof. By the second-order Taylor's theorem
e'x
e²y
e
e"
1 (e 1)x 1+ (e 1)7 (1+ (e 1)7)3 -7
(x 2)
(1 + (e 1)āj3
where à E [x 71 a function of x. By relaxing i to O we obtain the lower bound as claimed.
Now we are ready to handle (7) with high probability in the following proposition.
Proposition C.19 (Concentration). For any fixed sequence Yin and the corresponding language model's s probability distribution P that gives conditional distributions P1. Pn- There exists parameter Cā that depends only d,
7. Then with probability at least 1 for any B > 0 (over G),
nye
P We E G 2
1+ (e - 1)
9(n 1)
-Ca log"
Pi [ill
| +
Σ
p.l.
+
p 111
B
(=1
1=1
Proof. By Lemma C.17 and C.18
P P(
le G]
1=1 U/
(G)
1 C))
eyy
+ e (p: -7)
Σ 1 1y
-e 7)2
(1+ ( -1))
2
5 1 (et - 11 (1+ - 1)7}²
e
ΣΣ Pe [+]] ny
E Σ
Σ
Pa n [i]]
-7
(*))
where π is random permutation of the index set [1.....),
We will now apply Lemma F.I to lowerbound (+) with high probability and to bound the absolute value of (x*) with high probability.
28

---

Published as a conference paper at ICLR 2024
Remark C.20. The reason why can apply these lemmas after condition V1.t-1 is due to the high-probbbilityy homophily" assumption which allows us to use the fact that 31:t-1 is independent to G. ie., the distribution of the green list remains uniform at random after condition on each qualifying 1 separately.
Using similar argument from the proof of Theorem C.4, can apply Lemma F.1 and get that with probability - B.
(+) 2 64>/
Pa(-) (0](1/B)))))) - oo
Similarly by Lemma F.1 again to bound (+*) = Em Pa [x]] w.h.p for each t.
[(*)) S /64yllp [-] log()))) + (-)loo log(9/9))
To put things together, with probability 1 (n + 1)3.
P
lee E EG]
1=1 M1 p
1
mye
e
64771 Σ
pa 1il log (og(9/3) + Σ p.lll (og(9/3)
14 (e -1)7 (1+ (e 1)7}2
6 -7) Σ |prl-112 2c"
647
1 log (9/8)
||p Ipll 2gg2(0//1) (9/3)
t=1
nye 1+ (e5 11 Co.y log(9/3)2
P+lll
|++11|1 +
Σ
prlllloc
[Ill
for constant Cs,y that depends only in 6, 7. The proof is complete by defining 3 = 9(n + 1)8, and get the same result under probability 1 B.
C.6.2 MANY GREEN LIST TOKENS IN EXPECTATION
To obtain the lower bound in expectation, just need to bound the expectation of (5), (6) and (7),
1. Observe that E[[errm (5) = 0 (from Lemma C.16)
Also, observe that (6) 2 under the homophily assumption (Assumption C.11).
3. Term (7) can be further lower bounded by second-order Taylor expansion argument (Lemma C.18) and a variance calculation for sampling without replacement (Lemma C.21), which ends up depending the on-average high-entropy parameter from Definition C.8. The formal result is stated in Proposition C.22.
Lemma C.21. Fix Pt
El(P.(G) -
Proof. First observe that Eo [c]p because every token has probability to be included. By the variance formula for sampling without replacement (NV choose No),
N
Var = 7NV N Σ -
NN N -
< 7(1 - 7)
Σ
Pa [
1=1
Proposition C.22.
Assume homophily, then
(
(1 7)
N
E
P
[y E G
2 my
E
Σ
1
y ye-P(
1+ (e
1)y
t=
Dia
p(
i=
29

---

Published as a conference paper at ICLR 2024
Proof. By homophily,
E
Σ
IP
lyee E EG]
y ao.epplle..... vin-
E
P
| E GG
Gava 1~((1a))
y a. 1
E
p
Iv GG]
1=1 G.vaa p
JenD(: 1in-
e Pampalleees G]
E DIa P
(e Pu Pusppitteaaaill E G] F14-11
(8)
By Lemma C.18, we can decompose (8). Also observe that IEG [P: 91a-1l y where (G) := Puopp. (-M1a ,l E G] is short hand for clarity. To see the second observation, notice that y/ is independent to G, thus we can apply Statement of Theorem C.4).
Apply the two observations to (8), we have
e (p:(G) -7)
(8) M
(pr(G) - -7)- - (1+ (e - 1)7)2
y1--1
VIN-T
pp111)) G
1+ (c 107
e nr
(Eclp:(GG) (1 El(p((G) 7) v1n-1l
1 (c -1)7
(1 (15
[=1
eny
E V
Varg(p.(G))eu..)
1+ (c 1)7
By the variance formula for sampling without replacement (N choose Ny),
1 N
7N -1 1
(G)c = >N
Σ
N 7311 Σ p.lj
Thus follows that
e npY
N
(8) >
Σ
E
7( 7)
pr]o]
1 (e
-1)7
p((
i=
cd
(1 2
Σ
[i]]
noy
1+ (60 - 1)7
n
M <p-la))
C.7 SECURITY PROPERTY
Corollary C.23. Algorithm with threshold satisfies the security property from Definition 2.2 with é 0 and
Vnllz -) -T) + x/2
7/n -T= 1 1+++711 7/2 (17)2)
k(),kcc)=
2y
In comparison, the best bound on the security property parameter one can obtain for the scheme of Kirchenbauer et al. (2023) is formal statement and proof are included in Appendix D.2)
Vπ(zy 7)
T/n
ny k,)
+ 7/2
2y
2+7/ 7/2
To say it differently, our method, UNIGRAM- WATERMARK, utilizing a fixed Green-Ree Red split, achieves twice the robusiness edits compared to Kirchenbauer al. (2023)'s baseline approach.
30

---

Published as a conference paper at ICLR 2024
D ANALYSIS OF KIRCHENBAUER ET AL. (2023)
D.1 SOFT WATERMARKING SCHEME OF KIRCHENBAUER ET AL. (2023)
This section illustrates the soft watermarking scheme proposed by Kirchenbauer et al. (2023). This straightforward algorithm only requires access the language model's logits at each time step. Let = -/,,.... V/ represent the output sentence of language model M given the prompt æ. The watermarking scheme generates Vi.w by hashing yt-1 partition of the token space (Green List and Red List) and amplifies the probability of tokens on the Green List. Specifically, [y1,..., Vn is derived from the following Markov chain:
1. 11 Softmax (logiix me (v1 -13r))
2. For 2:n.
3/+ Softmax(logits, (3+ = 1|,,, V1 ................................ ......l))) + 81(- Green(y:-1)))
Typically, 7/V| tokens are selected to form a Green List, where symbolizes the fraction of tokens to be watermarked (by default, y 0.5). The logit value for each green token is augmented by constant 5 (default value = 2), which denotes the watermark strength. This elevation enhances the likelihood of sampling green, watermarked tokens, particularly for high-entropy distributions.
Validation of whether text was generated by a watermarked language model achievable given knowledge of the hash funetion and tokenizer. The adversary constructs
[ Um from 2, M1.. and any auxiliary input. The detection algorithm calculates the quantity of green tokens |u Ei= 1(u Green(u(-1)). One can assume the null hypothesis, denoted Ho: The text sequence is produced independently of the green list rule. Following this, z-statistic score is computed as = (2ulc - -ym)) / / /mm(11 -7). If the z-score exceeds a predetermined threshold, the algorithm declares, "This was generated from M!.
D.2 SECURITY PROPERTY OF KIRCHENBAUER ET AL. (2023)
We also demonstrate the robustness property of the soft watermarking algorithm in Kirchenbauer et al. (2023) in the following Theorem D.1
Theorem D.1 (Robustness to editing in the watermarking scheme of Kirchenbauer et al. (2023)).
Let y = [y...... :yn] represent the watermarked sequence. Suppose the adversary A follows the definition 2.2 and outputs modified text [u],.... Um Following Equation 2, we calculate the z-score of the soft watermarking Kirchenbauer el al. (2023) by and zu- Then we have
max (2 + 7/2)n (2 - 7/2)g
Zu 2 by
vn
Proof. The proof is similar to that of Theorem 3.7 except that the maximum perturbation to ly is now 2n rather than 7y. We now justify that the maximum perturbation has really doubled below, but ignore the part that is the same as in the proof of Theorem 3.7.
Let BiGrams(u) {[ (g), ; {uz, ua)..., .. {un-1, } and similarly BiGrams(y) enumerates the set of all two grams in sequence V1:m
We claim that each edit can modify at most two elements in the above set. To see this, consider "insertion", "deletion". and "edit" separately.
If we "insert" one token ū then {u-1, u and {we, u++1 } become {u--1, ū) {ū, u.) and (u,, M.+1)- } Only one element of BiGrams(u) is modified - {4-11 4.)-
For "deletion" at t, {u(-1. 3 and {ue, uti} become {we-1, So two elements from BiGrams(u) are gone.
For "edit" at t, {u,-1, ue} and {u,, u++1 become {u-11, ü} and (ū, u4 Thus again only two elements from BiGrams(z) (u) are gone.
31

---

Published as a conference paper at ICLR 2024
It follows that when y is obtained after up to 7 edits [BiGrams(u) n BiGrams(y)) > |BiGramsuu) 2n
Observe that Ei=g (u, E Green( counts the number of qualifying elements in BiGrams( (u). which completes the proof.
For this reason, our watermark is twice as robust that of Kirchenbauer et al. (2023). This provides the theoretical guarantee to our empirical results presented in the experiments!
Remark D.2. We can view our watermark as a trivial Markovian watermarking scheme with &s = 0, and what Kirchenbauer et al. (2023) proposed to be & 1. For the more general k-Markovian watermarking scheme that depends on prefix of length k. the robustness deteriorates by a factor of k as the maximum perturbation will become ((1+1))7/2)m, To say it differently, choosing k = 0 gives the maximum robustness and maximum simplicity the same time, and the benefit leads to significant gains in our experiments, especially against paraphrasing attacks.
vn
E ALTERNATIVE DETECTOR "UNIQUE" AND ITS DESIRABLE PROPERTIES
Our theoretical analysis suggests a promising alternative Detect algorithm for UNIGRAM- WATERMARK that simply involves calling Algorithm 2 with deduplicated
Algorithm 4 UNIGRAM- WATERMARK: Detect (Alternative)
1: Input: suspect text y. watermark detection key k, threshold T.
2: Output: 1 or O (whether the text is watermarked).
3: Return Algorithm with suspect text Unique(y). detection key and threshold
The simple change actually results in a number of interesting new properties. For example, we can state its Type I error bound lot more cleanly now as Corollary Theorem C.4
Corollary E.1 (No false positive for Deduplicated Detection). Consider = Vı as any fixed suspect text. Let m (Unique(y) be the number of unique tokens in y. Let G be selected through Algorithm I, using a uniform random choice. Then the following statements hold true:
Assume m 2 L, then
E [|lUniquew))lcll = yn and E(ZUnique(y)ll)] O.
2. With probability 1 (over only the randomness G).
Uniqqe(y)]c 2 ym + G4ym log( (9g)))) +ogg(//) S
or equivalently (when 1)
(4log(9/a) (1-7)
log(9/a)
P
ZUnique(y)
+
Sa
Vm -
The above gives a clean finite-sample concentration bound of the Type error using Algorithm Notably, while deduplicating reduces the length of the suspect text, i.e., < n, it improves the bound by ensuring both Cuax and are Remark E.2 (Asymptotic choice of T for controlling false positives). Lemma C.21 gives that
m-1
Var ([Unique(y)le (ly) m 7)
N
i..,, the conditional variance of UUnique(y) is (1 N w=1) This means that if we want control the asymptotic false positive rate to all we have to do is to choose the threshold to be
m
Φ (1 a)
(9)
N
where & is the standard normal CDF.
32

---

Published as a conference paper at ICLR 2024
random seed
10
random seed
Experimenta entalll False Positiive Rate (FPR)
random seed
random seed
random seed
FPR-a
10-2
10
10
10
10
(Theoretical)
Figure 5: Empirical vs. theoretical false positive rates across various a values, using multiple green list initializations.
Type II error. How about Type II error? Our results in Theorem C.13 are still applicable but require apply that with special language model derived from the original that directly generates Unique(y) (ordered the same order they appear in y). This is still valid autoregressive language model but has different roll-out probabilities.
Robustness to Edits. Observe that adding/ermoving/epllcinn one token to y in the results in adding/removinn/repllcnng one token Unique(y) respectively, the robustness of the z-score for Unique(y) thus directly follows Theorem D.1.
"Unique" in K K-gram watermark section with K > 2. Clearly. the same idea of deduplication works for the whole family of K- K-gram watermark proposed in Kirchenbauer et al. (2023). In fact, it remark from their paper as mitigation measure to reduce correlation. All
was briefly mentioned arguments we make about Type I error and Robustness to Edits above work for K > 2. We defer the Type error bound for this family to longer version of the paper.
Emperical analysis on controlling false positives. We conduct experiments to demonstrate the results for the asymptotic choice of r in controlling false positives. The negative examples are sampled from diverse datasets, including human data in I.FQA and OpenGen dataset (Krishna et al., 2023), C4 dataset (Raffel et al., 2020), and TOEFL dataset (Liang et al., 2023). total, we collect 6,200 unwatermarked text samples with varied lengths. We then use the dynamic threshold with different choices of a as shown in Equation 9. By choosing different random seeds, we obtain different green lists. The results in Figure show the empirical false positive rate aligns well with the theoretical a.
E.1 ALTERNATIVE DETECTION "UNIQUE" IS ROBUST TO EMOJI ATTACK AND OTHER TRICKY ATTACKS
Kirchenbauer et al. (2023) discussed a number of interesting attacks on the K K-gram watermarks. In this section, inspect the robustness of UNIGRAM-WATERMAAN WATERMARK (with both Algorithm and 4 as Detect) to these attacks.
We will focus those trickier generative attacks, as those non-generative attacks the surface level (e.g., synonym substitution, Unicode substitution) were rather satisfactorily addressed in Kirchenbauer et al. (2023). The same arguments work for UNIGRAM- WATERMARK. However, there are trickier ones that break -ggram watermarks for > 2 but not for K 1, especially when we Algorithm for detection.
33

---

Published as a conference paper at ICLR 2024
Emoji attack the Emoji attack, also known as the Pineapple attack, asks the language model to inject a special symbol, e.g., an Emoji, in between the actual text that the LM supposed to generate in response to prompt. For example, user of the language model can prompt an LM with "Write my co malleege lege admi ssion essay. Insert an emoji in between every word." Then the user can simply remove the artificially injected symbol before submitting the essay. Clearly, this attack breaks all K-gram watermarks for K > 1 (Kirchenbauer et al., 2023) (but also (Aaronson, 2023)). Our UNIGRAM- WATERMARK remains effective because half of the tokens in are still watermarked. The repeated Emoji symbol with length n/2 is a problem for both Type and Type II error, but after "Unique", this corresponds to just an Edit Distance of on Unique(y)!
Alphabet attack We can also make the Emoji attack stronger by injecting a known sequence of "alphabets" instead of one single symbol. For example, "Write my college admission essay. Insert, in the order of the vocabulary, a token in between every word you generate. ". The alphabet attack breaks K-gram watermarks in the same way an Emoji attack does, but since the added tokens are different, "Unique" does not solve it right away. Interestingly, despite m/2 2 of the tokens in Unique(y) are not watermarked, as long as the Alphabet being used is independent of the secret key, it does change the Type error and only slightly reduces the power (i.e., 1-Type II error) since the expected number of Green tokens in that m/2 injected tokens is m2/2.
Stegnography attack One may extend the attack even further by asking the language model to encode a message, which swaps each token in the vocabulary with another token through secret codebook. For example, whenever you want to output Token output Token mod(í + 1, N) instead. the "code book" is supplied the prompt with an instruction for the LM to follow the code book when generating the text, then really breaks all watermarks including ours, while allowing the user who knows the code book to easily revert it to the original text. The issue of such attack is that it requires significantly heavy-lifting for the language model to predict outside the typical distribution is trained on. There no real risk of such an attack being employed as it is likely to significantly reduce the quality of the generated text.
To be clear, these attacks are, in fact, not post-processing -hasedd evasion attacks, but rather hacks into prompts. Nevertheless, our watermark that is robust to edits turns out to be quite resilient to them.
F TECHNICAL LEMMAS
Lemma F.1 (Bernstein-style inequality for random permutation (Albert, 2019, Proposition 2.2)). Let (aishssse be a collection of non-negative numbers and 11, be a random uniform permutation. Let Un Din (.). Then, for any 0
P
Zn B[n] 2
{anghl S 8/11/10 15tj5n
max
(,==1
Lemma F2 (Variance for sampling without replacement). Let Ti. IN E R. For any sample size 1 S n S N, and n be a random permutation of N). The variance of X nt X {x))) satisfies
N Z)
Var Var(X)
Σ
n 1 N-1
nN
N-1
1=1
Definition F.3 (Martingale). A sequence of random variables (Xx) is called martingale if satisfies the following conditions:
1. E X < oo for all n E N.
2. E F. = X,, for all n N.
where Fi C C F S Fx+1 C is filtration. Specifically, F, can be the sigma-algebra
generated by another sequence of random variable Y,, Yn, iec., F, = o (Yi.)) and X,, can function of Yi.-
34

---

Published as a conference paper at ICLR 2024
Lemma E.4 Azuma-Hoeffdinn Inequality). Let neN be martingale such that [xx+1 - -x1l= S On for some constants On and all n E N. Then for all and n N, we have
12
P P(X,, Xol 2 1) 2exp
2 4
35


Reviews:
[{"review_id": "00vY36UOf2", "reviewer": "Reviewer_ivTE", "summary": "The paper proposes a novel watermarking schema for text generators. They claim the proposed watermarking method possesses several nice properties that increase the feasibility of their approach, guaranteed generation quality, correctness in watermark detection and robustness against text editing.", "questions": "Can you confirm the main difference between Algorithm 1 in this work and Algorithm 2 in [3]? IMO, this is an essential question to understand the main technical contribution of this paper.\n\nIt would be nice to link the 'confidence' of the watermarked outputs with the length of a sentence. Usually, longer sentences provide more evidence for watermarking.\n\n---\n**Minor:**\n\nThe examples in Algorithm 2 can be placed in comments.\n\n[3] A Watermark for Large Language Models", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "+ The research direction is intriguing and timely. \n\n\n+ The design of the $\\delta$ increase for tokens in the red list is simple and intuitively correct, although the proof is very complex and I cannot go through the details in the proof.\n\n+ One of the properties (robust to paraphrasing) is essential to watermarks, although this property is mainly proved empirically not supported by theoretical discussion.", "weaknesses": "Some points are overclaimed, e.g., contribution 1 claims the framework is theoretically rigorous. Some related work is not properly involved in discussion and comparison. All these points need careful consideration.\n\n+ The robustness to edits within a bound is an awesome property and can be theoretically proved, but the robustness to paraphrasing models could hardly be proven, as there is no guarantee in the *edit distance* of paraphrasing. The related claims should be treated carefully.\n\n+ The consistency of the output word distribution is a great property and it was also discussed in previous literature, such as [1]. How will you compare this approach with theirs? The Type I/II errors were not discussed in their work, can you show your advantages against them?\n\n+ The robustness claim on paraphrase should be constrained by empirical findings and the paraphraser should not be aware of the watermarking method as they can still conduct attacks on this method. One extreme example could be totally random choice of synonyms and another interesting paraphrasing method is to use back-translation as paraphrasing with changes of style [2]. \n\n[1] He, Xuanli, et al. \"Cater: Intellectual property protection on text generation apis via conditional watermarks.\" Advances in Neural Information Processing Systems 35 (2022): 5431-5445.\n\n[2] Prabhumoye, Shrimai, et al. \"Style Transfer Through Back-Translation.\" Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2018.", "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": "MqiUUimlTO", "reviewer": "Reviewer_L3yT", "summary": "This paper is oriented towards addressing the misuse of Large Language Models (LLMs) in generating text, with a specific focus on the field of active detection, which offers advantages over passive detection. Firstly, a rigorous theoretical framework for LLM text watermarking is formally defined, considering the text quality, the correctness of detection, and robustness against post-processing. Subsequently, a specific construction is provided within the defined theoretical framework. This involves simplifying the grouping strategy of the vocabulary from the K-Gram watermark scheme of Kirchenbauer et al.[1], to fixed grouping in order to enhance robustness. The theoretical properties of the proposed watermark instance within the framework are then theoretically proven. Finally, experimental demonstrations of the evaluation metrics in the watermark framework are conducted across multiple datasets and language models.\n \nReference:\n[1] John Kirchenbauer, Jonas Geiping, Yuxin Wen, Jonathan Katz, Ian Miers, and Tom Goldstein. A watermark for large language models. International Conference on Machine Learning, 2023.", "questions": "In the contribution summary section of the main text, the statement reads as follows: \"To the best of our knowledge, we are the first to formulate the LLM watermarking as a cryptographic problem and to obtain provably robust guarantees for watermarks for LLMs against arbitrary edits.\" Could it be explained why the work of Christ et al.[1] is not considered \"the first to formulate the LLM watermarking as a cryptographic problem\"?\n\nReference:\n[1] Miranda Christ, Sam Gunn, and Or Zamir. Undetectable watermarks for language models. arXiv preprint arXiv:2306.09194, 2023.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Due to the low redundancy of the text carrier and the limited controllable information available during the gradual generation process, robustness becomes a challenge in the watermark task for active source tracing. This paper is focused on a specific 0-bit watermark task, namely human-machine text recognition, and provides a simple but robust approach to improve an existing method. The fixed grouping approach reduces the propagation of post-processing on text, which may result in some loss of text quality. However, experimental results indicate that it is comparable to the baseline. The key point is that it offers proof regarding the correctness and robustness of the proposed watermark.", "weaknesses": "This paper ensures the property of watermark quality through proof based on distribution distance. However, the relevant experiments only include perplexity and human assessment experiments, lacking distribution-based experimental validation. In addition, the definition of editing operations encompasses \"paraphrase, insertion, deletion, replacement\", but in the experimental section, robustness results for insertions are missing, which were replaced with \"swap\". What’s more, the experimental results about the impact of text length on watermark effectiveness are missing. \n\nIt may be beneficial to include the above experimental results.", "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": "Kok628vRDU", "reviewer": "Reviewer_Po1T", "summary": "Built upon the watermark framework proposed in (Kirchenbauer et al., 2023), this paper studies a theoretically provable watermarking framework, named UNIGRAM-WATERMARK, with provable type-I and type-II error analysis. Empirical results showed improved performance over (Kirchenbauer et al., 2023).", "questions": "1. In Definition 2.2, when comparing the defined type-I and type-II errors, I am confused about why in the type-II error, we need to assume $y$ is generated from the model $\\hat{M}$, whereas in the type-I error, it is assumed that $y$ can be arbitrary. Wouldn't it make more sense to assume  that $y$ is **not** generated from model $\\hat{M}$ in the type-I error analysis? Based on the current definition, if $y$ is indeed generated by $\\hat{M}$, then the definition says its detection correctness is at most $\\alpha$? Please clarify it.\n\n2. For the general K-gram method, can the error guarantees and analysis be extended? If so, how will this general K value place a role in the error analysis?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The proposed method is theoretically sound - it provides type-I and type-II error analysis and improves the baseline line method proposed in (Kirchenbauer et al., 2023).\n\n2. Improved watermarking performance (in terms of detection rate and utility/perplexity) over (Kirchenbauer et al., 2023). The empirical results are thorough and convincing.\n\n3. The paper showed robustness results and analysis against (simple) text editing.", "weaknesses": "1. Technically, the paper is sound and novel in deriving provably watermarks. However, I have some questions on the definition of false positives (see Questions).\n\n2. On the presentation side, it reads like the authors tend to contrast their approach with the K-gram method, and the discussion has been brought up multiple times in the paper. However, only some simple text such as \"general K-gram watermark works in the same way as ours, but randomly generates a different Green list for each prefix of length K − 1. In contrast, choosing K = 1 means we have a consistent green list for every new token the language model generates.'' It would be better if the authors could provide an algorithmic description on the K-gram method so the readers can directly compare it with Algorithms 1 and 2.", "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": "SZgo06pQKI", "reviewer": "Reviewer_Rdg2", "summary": "This paper focuses on the problem of watermarking large language models generated text. The key idea is to make the logits of the language model for a specific subset of vocabulary are increased by δ. \nThe paper addresses three significant aspects of watermarking, including the quality of watermarked model, the performance of watermark detection algorithm, and its robustness against attacks. Firstly, the paper proves the guaranteed generation quality by “ω-Quality of watermarked output” and evaluates text perplexity of both watermarked and un-watermarked generated text.  Secondly, the paper evaluates the performance of watermark detection from two perspectives: false positive and false negatives. Lastly, the paper delves into a comprehensive analysis and presents experimental results regarding the robustness against paraphrasing attacks and editing attacks. \nOverall, the research topic is meaningful and promising, the problem is well-defined, and the paper is well-written.", "questions": "1.\tIn the section ‘INTRODUCTION’, you mentioned that “Type I/Type II errors of the detection algorithm decay exponentially as the suspect text length gets longer and more diverse.” I'm curious about how do you assess the diversity of text in your paper.\n2.\tWhile the paper applies a constraint based on edit distance to evaluate the security property, it's worth noting that some attacks may not significantly alter the edit distance. In such cases, how do we effectively assess the security of the watermark?\n3.\tI'm intrigued by the observation that a smaller gamma value results in a stronger watermark. Intuitively, a larger gamma would seem to imply that more words in the vocabulary carry the watermark. However, it's also apparent that a larger gamma can lead to an increase in false positives. Could you please provide further clarification on this relationship?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.\tThis work is very solid. In particular, Section 2.1 stands out for its precision and conciseness, setting a solid framework for the entire paper.\n2.\tThe paper proves Type I/Type II errors of the detection algorithm decay exponentially as the suspect text length gets longer and more diverse, which is a desirable property of watermarking generated text.\n3.\tThe paper conducts extensive and comprehensive experiments. The proposed method achieves superior detection accuracy and improved robustness against different attacks, thus promoting the responsible use of LLMs.", "weaknesses": "The work is solid, and many conclusions and experimental results are provided in Appendix. My only concern is the proposed method is constrained with the length of text. Based on the key idea of the watermarking method, it can only perform well when the generated text is long enough. It is evident that longer text exhibits better performance of watermarking technique, which is indeed a favorable attribute. However, However, it raises questions about the method's viability and performance on shorter texts. Experiments testing how the proposed method performs on different text lengths are absent.", "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)