Provable Robust Watermarking for AI-Generated Text

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 to 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-Walker, 2022). For example, LLMs could be used to generate fake news, contaminate web content, or 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 et 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 at generically distinguishing machine-generated text from that of the humans (Gehrmann et al., 2019; Mitchell et al., 2023; Hovy, 2016; Zellers et al., 2019; OpenAI, 2023b). These works primarily leverage hand-crafted or learned “statistical patterns” of generated text, thus their performance is not robust to distribution changes (e.g., by prompting / conditioning), prone to biases (Liang et al., 2023), and vulnerable to adversarial attacks.

The other camp advocates active intervention by injecting carefully-designed watermarks to machine-generated text (Kirchenbauer et 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 to enable downstream detection. Compared to the passive 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-shift and can essentially prove — rather than predict — the origin of the suspect text.

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 a “green list” and a “red list” based on the prefix token, and subtly increases the probability of choosing from the green list. If the watermarked sentence is edited by changing every other token into its synonym, then it is no longer possible to determine the green/red lists for each candidate token, thus ruining the detector. One could also simply paraphrase the sentence as a whole using another off-the-shelf LLM.

In this paper, we take a first stab at formally defining robustness in the context of watermarking LLMs. Our contributions are fourfold.

We devise a 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 of Kirchenbauer et al. (2023) by using a fixed Green-Red split consistently and show that the new watermark, named Unigram-Watermark, is twice as robust to edits as the baseline, provably.

We prove that the watermarked LLM is close to the original LLM (in all Renyi divergences) and show that the Type I/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$-gram (statistical) watermark was proposedNote the changed name. Kirchenbauer et al. (2023) referred to its (unnamed) soft-watermark that determines the green/red list using a prefix of length $(K-1)$. We think $K$-gram watermark is the most concise and informative name for this family.. The main method we consider chooses $K=1$, thus its name Unigram-Watermark. Our work provides formal theoretical guarantees to this family of $K$-gram watermark. For the sake of a clean presentation, we focus on the case when $K=1$ 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 a different kind of tradeoff. We defer detailed discussion to 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 is due to 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.

In the language model watermarking problem, the objective for the model owner is to embed a secret message known as “watermark” within the generated sequence $\boldsymbol{y}$ for a given prompt $\boldsymbol{x}$. There are two desired requirements for watermarking. First, the quality of the watermarked model should be comparable to the quality of the original, un-watermarked model. Second, an adversary needs to modify sufficiently many AI-generated text in order to evade detection.

The edit distance, denoted as ${\sf ED}(\boldsymbol{y},\boldsymbol{z})$, quantifies the number of basic operations required to transform a sequence $\boldsymbol{y}$ into another sequence $\boldsymbol{z}$. These operations include “insertion”, “deletion”, and “replacement” of tokens.

A language model watermarking scheme consists of two probabilistic polynomial-time algorithms $({\sf Watermark},{\sf Detect})$:

${\sf Detect}({\sf k},\boldsymbol{y})$: This algorithm takes input detection key ${\sf k}$ and sequence $\boldsymbol{y}$, then outputs 1 (indicating it was generated by $\hat{\mathcal{M}}$) or 0 (indicating it was not generated by $\hat{\mathcal{M}}$).

We require the following three correctness properties to hold:

$\alpha_{\boldsymbol{y}}$-Type I error (“No false positives”): for any fixed $\boldsymbol{y}$ (i.e., independent to ${\sf k}$), it holds that

$\beta_{(\boldsymbol{x},{\mathcal{M}})}$-Type II error (“No false negatives”):

We also require the following security property (parameterized by $\epsilon\geq 0$ and $\eta(\boldsymbol{y},{\sf k},\epsilon)$):

For any adversary ${\mathcal{A}}$ that postprocesses $\boldsymbol{y}$ with auxiliary information ${\sf aux}$ and any prompt $\boldsymbol{x}\in{\mathcal{V}}^{*}$

Informally, our definition allows us to formally quantify the essential properties of a 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 $\boldsymbol{x}$, should be far away (in edit distance) from any AI-generated answer. In other words, the optimal strategy to evade the detection algorithm would necessitate executing a minimum number of insert/delete/replacement operations, captured by the function $\eta(\cdot)$ in Definition 2.2. This conceptually suggests that the adversary must exert considerable effort to successfully elude detection.

Admittedly, there are other attacks where edit distance does not capture either the effort or the utility loss. For example, if one prompts an unwatermarked LLM to paraphrase $\boldsymbol{y}$ then the number of edits can be large but the semantic meaning is retained. However, edit distance is a natural metric that smoothly interpolates the gray zone between the world where $\boldsymbol{y}_{\mathcal{A}}=\boldsymbol{y}$ in which it should clearly be caught and the other world where $\boldsymbol{y}_{\mathcal{A}}$ is independently created without using $\hat{\mathcal{M}}$ in which it would be a false positive if ${\sf Detect}$ returns $1$.

2 Threat models

Adversary’s objective. The primary objective of the adversary is to render the watermark detection algorithm ineffective. Specifically, the adversary aims to produce a $\boldsymbol{y}_{\mathcal{A}}$ such that ${\sf Detect}({\sf k},\boldsymbol{y}_{\mathcal{A}})=0$ while at the same time, $\boldsymbol{y}_{\mathcal{A}}$ is a minor modification of an AI-generated text $\boldsymbol{y}$.

Adversary’s capabilities. We consider an adversary with black-box input-output access to the language model. This adversary has the capacity to modify the sequence within a bounded edit distance. Given an input prompt $\boldsymbol{x}$, the watermarked language model generates a text output $\boldsymbol{y}\leftarrow\hat{\mathcal{M}}(\boldsymbol{x})$. The adversary, equipped with arbitrary side-information and computational resources, can then produce a modified output $\boldsymbol{y}_{\mathcal{A}}$ such that the edit distance between the original and modified output, ${\sf ED}(\boldsymbol{y},\boldsymbol{y}_{\mathcal{A}})$, is bounded, i.e. ${\sf ED}(\boldsymbol{y},\boldsymbol{y}_{\mathcal{A}})<\eta$.

3 Method

Now let us instantiate Definition 2.2 with concrete algorithms. We will focus on Unigram-Watermark — a variant of the $K$-gram watermark proposed by Kirchenbauer et al. (2023) but with a choice of $K=1$. Pseudocodes of our approach ${\sf Watermark}$ and ${\sf Detect}$ are provided in Algorithm 1 and 2. In Algorithm 1, we randomly partition the vocabulary into two distinct sets: the green list with $\gamma N$ tokens and the red list with the remaining tokens. In $\hat{\mathcal{M}}$, the logits of the language model for the green list tokens are increased by $\delta$ 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 a calibrated decision on whether we think the suspect text is generated from $\hat{\mathcal{M}}$ or not. We show the examples of real prompts and watermarked outputs in Table 1.

The watermarking procedure is parameterized by two watermark strength parameters $\gamma,\delta$. $\gamma$ determines the fraction of the vocabulary included in the green list. We typically set $\gamma$ to be a constant, e.g., $1/3$ or $0.5$. $\delta$ specifies the increase in the logits associated with the green list tokens. The larger $\delta$ 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$-gram watermark from Kirchenbauer et al. (2023). It runs 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 watermark scheme work?

The remainder of this paper provides answers to 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 a knowledgeable reader may have.

Why choosing $K=1$? Recall that the 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. 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\geq 2$. Unigram-Watermark is also resilient to many other kinds of generation time attacks that people can apply such as reversing, shuffling, as well as the “Emoji insertion attack” that will completely break the watermark for $K\geq 2$ but not for $K=1$. We provide a detailed discussion of this in Appendix E.1.

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\geq 2$ too but certainly more so for $K=1$. There is a robustness-learnability tradeoff as we adjust $K$ which deserves a more rigorous treatment in future work. That said, we are ready to argue for biasing towards robustness. Why? We argue that in practice, it could be surprisingly difficult for an attacker to construct a meaningful attack when they do not have access to the original LM. 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 a while.

Main theoretical results

In this section, we present the quality, correctness, and security properties of Unigram-Watermark as described in Definition 2.2.

We first show that the distance between the original probability vector $\mathbf{p}_{t}$ and the watermarked probability vector $\hat{\mathbf{p}}_{t}$ are very close to each other in any Renyi-divergence.

Consider $\boldsymbol{h}$ as the input to the language model at step $t$, denoted as $\boldsymbol{h}=[\boldsymbol{x},\boldsymbol{y}_{1:t-1}]$. Fix green list $G$. Let $\delta$ represent the watermark strength. For any $\boldsymbol{h}$, the $\alpha$-th order Renyi-divergence between the watermarked probability distribution $\hat{\mathbf{p}}_{t}=\hat{\mathbf{p}}_{t}(\cdot|\boldsymbol{h})$ at time step $t$ and the original probability distribution $\mathbf{p}_{t}=\mathbf{p}_{t}(\cdot|\boldsymbol{h})$ satisfies:

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).

Renyi-divergence is very general. Kullback-Leibler-divergence and chi-square divergence are directly implied by the $\alpha$-Renyi divergence bound of $\min\{\delta,\alpha\delta^{2}/8\}$ by choosing $\alpha=1$ and $\alpha=2$ respectively and swap $\hat{\mathbf{p}}$ and $\mathbf{p}$. Hellinger distance can be obtained by choosing $\alpha=0.5$. By Pinsker’s inequality, we get a Total Variation distance bound of $\min\{\sqrt{\delta/2},\delta/4\}$. Moreover, by choosing $\alpha\rightarrow\infty$, we obtain an upper bound of $\delta$ for a very strong multiplicative guarantee known as max-divergence. The resulting two distributions $\hat{\mathbf{p}}$ and $\mathbf{p}$ are referred to by cryptographers as $(\delta,0)$-indistinguishable, which says that for any measurable event $S$, the log-odds ratio satisfies

To summarize, our result shows that Algorithm 1 produces $\hat{\mathcal{M}}$ that satisfies $\omega$-quality of watermarked output with $\omega$ (as a function of $\delta$) for almost all commonly used probability distance $D$.

2 Type I error of Unigram-Watermark

Consider $\boldsymbol{y}=\boldsymbol{y}_{1:n}$ as any fixed text. Define $C_{\max}(\boldsymbol{y}):=\max_{i\in[N]}\sum_{j=1}^{n}\mathbf{1}(y_{j}=i)$ and $V(\boldsymbol{y}):=\frac{1}{n}\sum_{i=1}^{N}(\sum_{j=1}^{n}\mathbf{1}(y_{j}=i))^{2}$. With probability $1-\alpha$ (over only the randomness of $G$):

The theorem implies that if we choose $\tau>\sqrt{\frac{64V\log(9/\alpha)}{1-\gamma}}+\frac{16C_{\max}\log(9/\alpha)}{\sqrt{n\gamma(1-\gamma)}}$, then the false-positive rate is smaller than $\alpha$. Note that $V$ and $C_{\max}$ can be computed directly from $\boldsymbol{y}$, allowing us to choose an input-dependent $\tau$ as a function of $V,C_{\max}$ that achieves a $\alpha$-Type I error guarantee with a fixed $\alpha$ for all inputs. In particular, the Type I error $\alpha$ decreases exponentially as we increase the threshold $\tau$.

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 $\mathbf{p}$ of the language model and the prompt $\boldsymbol{x}$. These assumptions include a “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 “sufficiently diverse” on average. It 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 state-transitions of the language model $\mathcal{M}$, which says that increasing the probability of a green-list token at time $t$ 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.

The bounds on Type I/II error together say that $z_{\boldsymbol{y}}\asymp\delta\sqrt{n}$ if $\boldsymbol{y}$ is from $\hat{\mathcal{M}}$ while $z_{\boldsymbol{y}}\asymp O(1)$ otherwise, i.e., there is a large margin between them so we can choose $\tau$ in between. Also, the $\alpha$ and $\beta$ parameters decay exponentially as the $n$ gets larger.

4 Security property of Unigram-Watermark

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.

Let $\boldsymbol{y}=\left[y_{1},\ldots,y_{n}\right]$ represent the watermarked sequence. Suppose the adversary $\mathcal{A}$ follows Definition 2.2 and outputs a modified text $\boldsymbol{u}=\left[u_{1},\ldots,u_{m}\right]$. Following Equation 2, we calculate $z$-score $z_{\boldsymbol{y}}$ and $z_{\boldsymbol{u}}$. Assume edit distance between $\boldsymbol{y}$ and $\boldsymbol{u}$ (denoted as $\eta$) satisfies $\eta<n$. Then we have

In particular, when $\eta\leq\frac{2\gamma n}{(1+\gamma/2)^{2}}$, we can drop the second term in the max.

This theorem bounds the changes to our test $z$-score when $\eta$ edits are performed. As we established for a high-entropy sequence, $z_{\boldsymbol{y}}$ typically grows in $O((e^{\delta}-1)\sqrt{n})$, which means that when $\delta$ is a constant, with an appropriate choice of $\tau$, the watermark is robust up to $O(n)$ arbitrary edits!

Finally, compared to Kirchenbauer et al. (2023)’s watermark, ours is twice as robust (see Appendix D).

Experiment

In this section, we aim to conduct experiments to evaluate watermark detection performance, watermarked 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.

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-103 (Merity et al., 2017). The subsequent 300 tokens serve as the human-written continuation. LFQA is a long-form question-answering dataset created by Krishna et 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 human-written answers, resulting in 3K QA pairs. In our experiments, we use the questions as prompts and the corresponding answers as human-written text.

Language models. We conduct experiments using three state-of-the-art public language models of varying sizes from different model families: GPT2-XL with 1.5B parameters (Radford et al., 2019), OPT-1.3B (Zhang et al., 2022), and LLaMA-7B (Touvron et al., 2023). Nucleus Sampling (Holtzman et al., 2020) is 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 as watermarked. To ensure this, we set the false positive rates at 1% and 10% for all detection algorithms and adjust the detection threshold accordingly. We report true positive rate (TPR), F1 score, and ROC curves. GPT3 (text-davinci-003) (Ouyang et al., 2022), is used as the oracle model for perplexity evaluation. The experiments are conducted on Nvidia A100 GPUs.

2 Watermarking results

We use a watermark strength of $\delta=2.0$ and a green list ratio of $\gamma=0.5$. We also use different watermark keys ${\sf k}$ for different models. Stronger watermarks can be achieved for shorter sequences for a smaller $\gamma$ and a larger $\delta$. 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 “un-watermarked” respectively. We also have corresponding human-written text for each prompt, referred to as "human". All sentences are cropped to a length of 200 tokens. $z$-scores are calculated for hypothesis testing as shown in Algorithm 2 between different sentence groups. The results (Figure 1a) 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 $\delta=2.0$ and $\gamma=0.5$ for their method.

Figure 1b demonstrates the text perplexity of human, un-watermarked machine-generated, and two watermarking-generated texts, evaluated on the OpenGen dataset. 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 human-generated text, especially with the use of the largest model LLaMA-7B. This finding further supports the effectiveness of our method in preserving linguistic characteristics and coherence, ensuring seamless integration of watermarks without compromising overall text quality. One example of the prompt questions and machine-generated 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 on a scale of 1 (poor) to 5 (excellent). Each sentence undergoes two evaluations. The average score and standard deviation are computed and presented in Table 3.

3 Robustness results

One of the key advantages of our method is its robustness. To provide comprehensive evidence of its resilience, we conduct experiments to test its resilience against various attacking methods.

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 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-cnn, a large-sized model fine-tuned on the CNN Daily Mail dataset (Hermann et al., 2015)) for text summarization as 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 et al. (2023). Notably, our method achieves an accuracy rate of over 85% with a false positive rate of 10%.

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 Distinguishing human-written text

An interesting observation emphasized by Liang et al. (2023) is the misclassification of non-native English writing samples as AI-generated by existing AI content detectors. Our method can effectively establish text origin and maintain robustness to distribution shifts. We evaluate Unigram-Watermark in distinguishing human-written text on a dataset of human-written TOEFL essays collected by Liang et al. (2023). Our method demonstrates a remarkable ability to accurately classify human-written text, as evidenced by significantly lower $z$-scores compared to the empirical threshold of $z=6.0$. This outcome underscores the effectiveness of our watermark in discerning text generated by human authors, further enhancing its practical utility and reliability.

Conclusion and discussion

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 to 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 a broader range of attacks.

Applicability to general $K$-Gram watermark. While we focused on Unigram-Watermark, most of our results apply to $K$-Gram watermarks with $K\geq 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 II error bound does not directly work for $K\geq 2$, some of our intermediate steps can be applied.

Limitations. While our watermarking method, Unigram-Watermark, demonstrates improved robustness against edits, its reliance on a 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 to all possible attacks.

Future work. Future work includes constructing unlearnable watermarks, understanding the robustness-learnability tradeoff as well as unifying cryptographical and statistical watermarks.

References

Appendix A More on related work

Watermarking natural languages. The concept of watermarking, which involves hiding identifying information within data, has a 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 et 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 et 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, an 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 applies thresholding to identify AI-generated content. DetectGPT [Mitchell et al., 2023] suggests that AI-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 machine-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, AI-generated text is becoming increasingly similar to human-generated text, making it more challenging to detect. Gambini et al. find that existing detection strategies designed for GPT-2 struggle with GPT-3. Moreover, known detectors are found to be fragile to adversarial attacks [Wolff, 2020] and biased towards non-native English writers [Liang et al., 2023].

Impossibility results? Sadasivan et al. 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 as we made no theoretical claim about paraphrasing. We do claim that in Theorem 3.1 that the watermarked LM $\hat{\mathcal{M}}$ and original LM $\mathcal{M}$ is statistically close — in fact, indistinguishable in the “differential privacy” sense. But the indistinguishability is for each token. As the number of tokens gets larger, they will eventually become distinguishable, that is 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. , showing that detection is possible.

Language model watermarks with provable guarantees. Concurrent to our work, Christ et al. 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. , 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-II 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 a 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. and Aaronson are examples of cryptographic watermarks, while Kirchenbauer et al. and this paper study statistical watermarks. There are 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. and Aaronson use a similar definition of language model watermarks as Definition 2.2 and considered a similar set of properties. Specifically, the “soundness”, “completeness” from Christ et al. directly map to our “Type I error” and “Type II error” requirements. As we understand from the materials in Aaronson ’s talk, their “indistinguishability” is a form of performance guarantee for $\hat{\mathcal{M}}$. The difference to ours is that they require (in our notation)

where the random key ${\sf k}$ is marginalized out. while our results require that for every ${\sf k}$ the next token

to be statistically close (in the same sense of $\delta$-differential privacy). By our metric, however, Aaronson ’s watermark does not appear to satisfy any nontrivial $\delta$ guarantee, since it only requires unbiasedness. For that reason, the detection guarantee and its tradeoff with quality that we discussed in Remark C.15 is not applicable to the cryptographic watermarks.

Appendix B Additional experiment results

We perform experiments on two datasets (OpenGen and LFQA) using three different models (GPT2-XL, OPT-1.3B, and LLaMA-7B). Table 4 presents the error rates, showcasing the sensitivity of the resulting hypothesis test based on observed $z$-scores. The results demonstrate that there are no Type-I (false positive) errors for all models, with true positive rates exceeding 0.94 for a threshold of $z=6.0$.

B.2 Different watermark parameters

We conduct an analysis to understand the impact of changing watermark strength ($\delta$), green list size ($\gamma$), and sampling methods on two datasets. The results are summarized in Table 5. When using nucleus sampling with a fixed $\gamma=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 $\delta$, varying the green list ratio from 0.25 to 0.5 and 0.75 showed improved detection results with smaller $\gamma$. 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 is significantly lower than that of nucleus sampling. However, beam search tends to generate shorter sequences with repeated words.

B.3 Additional robustness results

In addition to the previously discussed robustness evaluations, we provide further analysis of our method’s resilience against paraphrasing attacks and editing attacks. The results are presented in Figure 4. Notably, our proposed method (Unigram-Watermark) 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 White-box attack

A potential attack for Unigram-Watermark is to 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 it is difficult to accurately estimate the green list. Even if the green list is known, our watermark is still somewhat effective thanks to our added robustness.

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-13B watermarked model with watermark strength $\delta=2.0$, watermark ratio $\gamma=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:

The human response from the same prompt (LFQA and OpenGen dataset). The corresponding human output is 0.4 million tokens. We denote it as the “LFQA & OpenGen dataset”

Most times, human responses are not known. So we collect 2000 samples from the C4 [Raffel et al., 2020] dataset to form an approximate human dataset with 1 million tokens. We denote it as the “C4 dataset”.

To simulate the distribution from non-native speakers. We also collect a non-native speaker (TOEFL essay) dataset from Liang et al. 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 3) to decide whether a token is green or red.

The estimation results for the green list tokens are shown in the table below.

The results suggest that while it is possible to make non-trivial inferences about which token is green, it 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.

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 an 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 or may only have green synonyms.

The results in Table 6 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 a significant drop in the text quality.

B.5 Testing on scaled language models

We conduct supplementary experiments on the scaled models LLaMA-13B and LLaMA-65B. Using the same experimental settings as in the main paper, our preliminary results show that our method maintains effectiveness on these larger models. For LLaMA-13B, we are able to use the same test set size as in the original paper. For LLaMA-65B, due to computational constraints, we test on a sample of 100 sentences. The results (TPR at 1% FPR) are shown in Table 7.

B.6 Results for deduplicated detection

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.

Appendix 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 a language model watermarking scheme from Definition 2.2.

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-Leibler (KL) divergence and Total Variation-distance.

The Renyi-divergence of two distributions $P$, $Q$ is defined as

where $\frac{dP}{dQ}$ is the Radon–Nikodym derivative. When $\alpha\rightarrow 1$, the Renyi divergence converges to the KL-divergence. Additionally, when $\alpha=0.5$, it serves as an upper bound for the TV-distance.

On the technical level, we leverage a surprising connection to a 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].

Consider $\boldsymbol{h}$ as the input to the language model at step $t$, denoted as $\boldsymbol{h}=[\boldsymbol{x},\boldsymbol{y}_{1:t-1}]$. Fix green list $G$. Let $\delta$ represent the watermark strength. For any $\boldsymbol{h}$, the $\alpha$-th order Renyi-divergence between the watermarked probability distribution $\hat{\mathbf{p}}_{t}=\hat{\mathbf{p}}_{t}(\cdot|\boldsymbol{h})$ at time step $t$ and the original probability distribution $\mathbf{p}_{t}=\mathbf{p}_{t}(\cdot|\boldsymbol{h})$ satisfies:

We define $\delta_{v}=0$ when $v\in R$ and $\delta_{v}=\delta$ when $v\in G$. Using this definition, we have:

Similarly, $\hat{\mathbf{p}}(v|\boldsymbol{h})\geq e^{-2\delta}\mathbf{p}(v|\boldsymbol{h})$.

Furthermore, $\delta$-BoundedRange implies $\delta$-DP (or rather $(\delta,0)$-indistinguishability, since we are dealing with just two distributions rather than a family of neighbor distributions). It follows from the that

For any prompt $\boldsymbol{x}$, the KL-divergence between the probability distribution of the watermarked sequence and the original sequence satisfies:

The proof follows from the adaptive composition theorem for Renyi-divergence, and max-divergence (from the DP literature) for the autoregressive decomposition of $\hat{\mathbf{p}}(\boldsymbol{y}_{1:n}|\boldsymbol{x})$ and $\mathbf{p}(\boldsymbol{y}_{1:n}|\boldsymbol{x})$ 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.1, and 3.1 to ensure completeness and precision. We begin by restating the theorems and providing the corresponding proofs with necessary modifications.

Let $\boldsymbol{y}=\left[y_{1},\ldots,y_{n}\right]$ represent the watermarked sequence. Suppose the adversary $\mathcal{A}$ follows Definition 2.2 and outputs a modified text $\boldsymbol{u}=\left[u_{1},\ldots,u_{m}\right]$. Following Equation 2, we calculate $z$-score $z_{\boldsymbol{y}}$ and $z_{\boldsymbol{u}}$. Assume edit distance between $\boldsymbol{y}$ and $\boldsymbol{u}$ (denoted as $\eta$) satisfies $\eta<n$. Then we have

In particular, when $\eta\leq\frac{2\gamma n}{(1+\gamma/2)^{2}}$, we can drop the second term in the max.

Define bivariate function $f(x,y)=\frac{x-\gamma y}{\sqrt{y}}$. By Taylor’s theorem

A lower bound of the above can be obtained by finding an upper bound to

We will discuss two cases again, the first case is when $k-\gamma y/2\leq 0$. In this case, the function $g(u)=a/u+bu$ with $a\leq 0$ has a derivative of $-a/u^{2}+b\geq 0$, thus $g$ is monotonically increasing. Thus we should choose $k_{y}=0$. The second case is when $k-\gamma y/2>0$, in this case the $a>0$ in the above $g(u)$ and $g(u)$ is convex, thus $\max_{u_{\min}\leq u\leq u_{\max}}g(u)=\max\{g(u_{\max}),g(u_{\min})\}$. Thus we should just compare the two cases when $k_{y}=0$ and $k_{y}=k$, i.e., $\max\{\frac{k}{\sqrt{y}},\frac{(1-\gamma/2)k}{\sqrt{y-k}}\}$.

Collect everything together, we get an upper bound o

Now notice that our $z$-score has the same form as the $f(x,y)$ function. We can take $y=n$ and $x=|\boldsymbol{y}|_{G}$. Instantiate $k$ be the maximum number of edits $\eta$. Observe that given that the adversary has a 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 number of edits. The above result translates into

where $\eta$ 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)

Consider $\boldsymbol{y}=\boldsymbol{y}_{1:n}$ as any fixed suspect text. Let $N=:|\mathcal{V}|$ and $G\subset|\mathcal{V}|$ satisfying $|G|=\gamma N$. $G$ is selected through Algorithm 1, using a uniform random choice. Let $|\boldsymbol{y}|_{G}$ denote the number of tokens in $G$ and $z_{\boldsymbol{y}}:=\frac{|\boldsymbol{y}|_{G}-\gamma n}{\sqrt{n\gamma(1-\gamma)}}$ as in Algorithm 2. Then the following statements hold true:

Define $C_{\max}(\boldsymbol{y}):=\max_{i\in[N]}\sum_{j=1}^{n}\mathbf{1}(y_{j}=i)$ and $V(\boldsymbol{y}):=\frac{1}{n}\sum_{i=1}^{N}(\sum_{j=1}^{n}\mathbf{1}(y_{j}=i))^{2}$, then with probability $1-\alpha$ (over only the randomness of $G$),

To prove the first statement, observe that any fixed token has a probability $\gamma$ to be included in the green list, thus by the linearity of the expectation and the independence of $\boldsymbol{y}$ in $G$.

By Lemma F.1 with $t=16\log(8e^{1/16}/\alpha)$, we get that with probability $1-\alpha$,

where we used that $8e^{1/16}\leq 9$ and the fact that only $\gamma N$ columns of the $a_{i,j}$ matrix $a_{i,j}$ is nonzero, and for each non-zero column L2-norm of the column is bounded by $\sqrt{nV}$ by our definition of $V$. The result for the $z$-score follows trivially. ∎

Note that the theorem does not impose assumptions on how $\boldsymbol{y}$ is generated. It covers any procedure (including human generation) that produces $\boldsymbol{y}$ in a manner independently of the secret partition $G$. In cases where $\boldsymbol{y}$ is generated by a language model, it could be the output of greedy search from $\mathbf{p}(y_{t}|\boldsymbol{x},\boldsymbol{y}_{1:t-1})$, nucleus sampling, beam search, or any other decoding methods.

The $V$ and $C_{\max}$ parameters in Theorem C.4 measure the diversity of the suspect text $\boldsymbol{y}$ and are necessary for the high-probability bound. As an example, if the prompt says “Repeat ‘‘Goal’’ for a hundred thousand times like a soccer commentator.” Then the resulting generated sequence will be “Goal goal goal ...”, and has either $n$ green tokens or green tokens. No meaningful Type I error bound can be obtained.

The theorem implies that if we choose $\tau>\sqrt{\frac{64V\log(9/\alpha)}{1-\gamma}}+\frac{16C_{\max}\log(9/\alpha)}{\sqrt{n\gamma(1-\gamma)}}$, then the false-positive rate is smaller than $\alpha$. Note that $V$ and $C_{\max}$ can be computed directly from $\boldsymbol{y}$, allowing us to choose an input-dependent $\tau$ as a function of $V,C_{\max}$ that achieves a $\alpha$-Type I error guarantee with a fixed $\alpha$ for all inputs. In particular, the Type I error $\alpha$ decreases exponentially as we increase the threshold $\tau$.

C.4 Only true detection (Type II error guarantees)

For bounding the Type II error, i.e., false negative rates, we will work with our proposed method that generates $\boldsymbol{y}$ from the language model, i.e., sampling from the watermarked distribution $\hat{\mathbf{p}}$ recursively one token at a time.

Let’s first recall a few notations. $\boldsymbol{h}$ is the input to the language model at step $t$, i.e., $\boldsymbol{h}=[\boldsymbol{x},\boldsymbol{y}_{1:t-1}]$. Let $\delta$ represent the watermark strength from Equation 1. The green list $G\subset[N]$ is a random index set of the vocabulary of size $\gamma N$. The watermarked probability distribution $\hat{\mathbf{p}}_{t}=\hat{\mathbf{p}}_{t}(\cdot|\boldsymbol{h})$ at time step $t$. The process of generating the sentence $y_{1},y_{2},\ldots,y_{n}$ involves recursively sampling from $\hat{\mathbf{p}}_{t}$, which we refer to as a “roll-out” procedure.

We need to make a few assumptions about the language model’s probability distribution $\mathbf{p}$ and the prompt $\boldsymbol{x}$. We will first state them and then explain why these are natural and arguably needed for the Type II error to be small.

The first such assumption requires the probability of the roll-out to be “sufficiently diverse” on average. We will introduce the notation $\|\mathbf{p}\|_{2}:=\sqrt{\sum_{i=1}^{N}\mathbf{p}[i]^{2}}$.

We say a language model’s probability distribution $\mathbf{p}$ with a prompt $\boldsymbol{x}$ satisfies $\xi$-on-average-high-entropy if

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 $\boldsymbol{y}_{1:n}$ is almost deterministic under $\mathbf{p}$ and perturbing the logits by $\delta$ does not change the distribution much at all.

“Generate the English alphabet in capital letters for 200 times please.”

Despite that the generated sequence is very long, i.e., $n$ is as large as $5,200$, the added watermark does not change the distribution very much at all. To see this, if $\mathbf{p}(y_{3}=\text{``C''}|\boldsymbol{x},\boldsymbol{h})\geq 1-\epsilon$ for a tiny $\epsilon$, and then by our quality guarantee, $\hat{\mathbf{p}}(y_{3}=\text{``C'' }|\boldsymbol{x},\boldsymbol{h})\geq 1-\epsilon e^{\delta}$.

Quantitatively, for nearly uniform $\mathbf{p}_{t}$, $\xi=O(1/N)$, if $\mathbf{p}_{t}$ concentrates on a single token for all $t$, e.g., when a football commentator exclaims “Goal goal goal goal ....”, then we cannot obtain a better bound than the trivial $\xi\leq 1$. In the alphabet example above $\xi\leq 1/26$.

Why is it called entropy? Assumption C.8 is related to the “high-entropy” assumption in Kirchenbauer et al. but for a slightly different kind of entropy. In a more formal sense, the quantity $\|\mathbf{p}_{t}\|^{2}$ is connected to the Tsallis entropy of order 2, defined as $S_{2}(\mathbf{p}_{t})=k_{B}(1-\|\mathbf{p}_{t}\|^{2})$ where $k_{B}$ is known as the Boltzmann constant. Our assumption requires the expected Tsallis entropy of the conditional distribution $\mathbf{p}_{t}$ over the roll-out of $\mathbf{p}$ to be larger than $k_{B}(1-\xi)$ on average among $t=1,...,n$.

For a high-probability result, we also need a stronger version.

We say that a language model’s probability distribution $\mathbf{p}$ with a prompt $\boldsymbol{x}$ satisfies $(\xi,\beta)$-on-average-high-entropy if with probability at least $1-\beta$ over the generated sequence $\boldsymbol{y}_{1:n}$,

The behavior is similar to that of the expectation version of the assumption. When $\mathbf{p}_{t}$ is nearly uniform, $\mathbf{p}_{t}[i]=O(1/N)$, then $\xi=O(1/\sqrt{N})$. When $\mathbf{p}_{t}$ is supported only on one token, then $\xi=1$. In practice, $\xi$ is a small constant. As we will present in the main theorem, as long as $\xi\asymp\delta$, the number of green list tokens is guaranteed to grow faster $\gamma n$ as $n$ gets larger.

One may also ask whether it is necessary to make entropy assumptions on the conditional probabilities instead of the marginal probabilities induced by $\mathbf{p}$ or $\hat{\mathbf{p}}$, but this is unfortunately not sufficient as illustrated in the following example.

“Generate the first token uniformly at random, then repeat the token you generated for the remaining $n-1$ tokens”.

C.4.2 A “homophily” assumption

The second assumption that we 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.

We say a language model’s probability distribution $\mathbf{p}$ and prompt $\boldsymbol{x}$ satisfy “homophily” if for any $G$, the corresponding watermarked $\hat{\mathbf{p}}$ satisfies that

where $\boldsymbol{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 $\boldsymbol{h}$ cannot counter-intuitively reduce the probability of tokens in $G$ in the future on average.

The assumption is not unreasonable, because we expect a language model to be more likely to refer to text it has generated in 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 in the long run. To illustrate this, consider the following example utilizing the prompt:

$\boldsymbol{x}=$ “Randomly select a color, state what it is. Then write a short poem about it without naming this color at all.”

The generated text from a commercial language model is

“Color choice: green. Emerald whispers in the meadow’s sway, Life’s verdant rhythm in ceaseless play. It cradles the world in a leafy embrace, A silent serenade to nature’s grace.”

Notice that if the token “green” $\in 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 text will not contain the word “green”, as 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.

$\boldsymbol{x}=$ “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 to calculate that the expected number of times any token appears in a language model that perfectly follows the instruction will be $n/N$. However, the watermarked language model, let’s say we use a very large $\delta$ such that the first $k$ tokens are from the green list, then the expected number of times a green-list token appears is $\frac{k}{\gamma N}+\frac{\gamma N-k}{\gamma N}\frac{(n-k)(\gamma N-k)}{N-k}$ which is bounded by $1$ if $k=\gamma N$ instead of growing linearly in $n$ as in the original language model.

To obtain a concentration bound, we also need a stronger version of the homophily assumption as follows.

There exists a coupling – a joint distribution of $\boldsymbol{y}_{1:n}$ and $\hat{\boldsymbol{y}}_{1:n}$ where marginally $\boldsymbol{y}_{1:n}\sim\mathbf{p}(\cdot|\boldsymbol{x})$, $\hat{\boldsymbol{y}}_{1:n}\sim\hat{\mathbf{p}}(\cdot|\boldsymbol{x})$ – such that for any $G$, with probability $1-\beta$ over the joint distribution,

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 Theorem statement on “Only true detection”

Now we are ready to state the main theorem.

For a fixed language model $\mathcal{M}$ and a prompt $\boldsymbol{x}$. The sentence $\boldsymbol{y}_{1:n}$ generated from $\hat{\mathcal{M}}(\boldsymbol{x})$ where $\hat{\mathcal{M}}$ is an output of our watermarking scheme ${\sf Watermark}_{\delta,\gamma}(\mathcal{M})$ with parameter $\delta,\gamma$. Then the following statements are true.

In particular, if Assumption C.8 condition is true with parameter $\xi\leq(1-\kappa)\frac{e^{\delta}-1}{(1+(e^{\delta}-1)\gamma)e^{\delta}}$ for a parameter $0<\kappa<1$, then

Assume high-probability version of homophily (Assumption C.12). There exists a parameter $C_{\delta,\gamma}$ that depends only $\delta,\gamma$ such that with probability at least $1-\beta$ for any $\beta>0$ (over both $G$ and $\boldsymbol{y}\sim\hat{\mathbf{p}}(\cdot|\boldsymbol{x},G)$ ),

In particular, if for a parameter $0<\kappa<1$,

and Assumption C.9 condition is true with parameter $(\xi,\beta/3)$ where

Recall that according to Theorem C.4, in order to have a false positive rate controlled at level $\alpha$, we need to set the threshold $\tau\gtrsim\sqrt{\log(1/\alpha)}$ for sufficiently high-entropy sequences. Theorem C.13 says that if we want the false negative rate to be smaller than $\beta$, we only need the threshold $\tau\lesssim\kappa\delta n$ under similar (slightly different) high-entropy sequences for $n\gtrsim\log(1/\beta)/\delta^{2}$. Observe that there is a wide range of valid choices of $\tau$ for us to have a 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 $\delta\asymp 1/\sqrt{n}$ if the sequence is sufficiently high-entropy.

The sample complexity of $n\gtrsim 1/\delta^{2}$ is information-theoretically optimal (up to a logarithmic factor) in $\delta$ because, our accuracy guarantee (together with the composition theorem) indicates that the KL-divergence between a sequence of length $n$ generated from $\mathbf{p}$ and that generated from $\hat{\mathbf{p}}$ is $n\delta^{2}$ indistinguishable, i.e., $n>1/\delta^{2}$ for any classifier — even the uniform most-powerful Neyman-Pearson likelihood-ratio test (which requires additional information, e.g., $\boldsymbol{x}$ and $\mathbf{p}$ which we do not have) — to make no mistakes with a constant probability.

C.6 Proof of Theorem C.13

In the false negative error cases, $\boldsymbol{y}$ is drawn from the watermarked language model $\hat{\mathcal{M}}$. To be explicit, let us write $\boldsymbol{y}=[\hat{y}_{1},...,\hat{y}_{n}]=\hat{\boldsymbol{y}}_{1:n}$. Now let’s also define a hypothetical (possibly coupled) sequence $\boldsymbol{y}_{1:n}$ which is drawn from the original (un-watermarked) language model $\mathcal{M}$.

The proof of Theorem C.13 considers the following decomposition

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 C.13) then deal with the expectation.

To obtain a high-probability lower bound, it requires us to obtain concentration for each of the three terms. Specifically,

To bound Term (5), we use Lemma C.16 which invokes Martingale concentration over the randomness in $\boldsymbol{y}$ to show $|\boldsymbol{y}|_{G}$ is close to $\sum_{t}\hat{\mathbf{p}}_{t}(G|\hat{\boldsymbol{y}}_{1:t-1})$.

We will show Term (6) is non-negative with high probability by using the homophily assumption (Assumption C.12). This allows us to study the roll-out $\hat{\boldsymbol{y}}_{1:t-1}$ under $\hat{\mathcal{M}}(\boldsymbol{x})$ (or $\hat{\mathbf{p}}$) by studying a hypothetical alternative roll-out $\boldsymbol{y}_{1:t-1}$ sampled under $\mathcal{M}(\boldsymbol{x})$ (or $\mathbf{p}$).

Then we control Term (7) by first Taylor expanding it into quantities involving $\mathbf{p}_{t}(G|\boldsymbol{y}_{1:t-1})$ instead of $\hat{\mathbf{p}}(G|\boldsymbol{y}_{1:t-1})$, then apply concentration inequalities for each expanded terms over the randomness of $G$ (while fixing $\boldsymbol{y}_{1:t-1}$) to obtain a high probability lower bound. Proposition C.19 gives the results.

We start by tackling (5) via Martingale concentration.

For any green list $G$ and prompt $\boldsymbol{x}$.

Moreover, with probability at least $1-\beta$ over the roll-out

We fix $G$ and construct a martingale sequence $X_{1},X_{2},...,X_{n}$ where $X_{0}=0$ and:

The claim about the expectation follows from that $X_{0}=0$ and an inductive argument following the tower property of conditional probabilities.

By the fact that $|X_{t}-X_{t-1}|\leq 1$ we can apply Azuma-Hoeffding’s inequality and get

To handle (6), we apply Assumption C.12 with parameter $\beta/3$, which says that with probability $1-\beta/3$ (6)$\geq 0$. This converts a roll-out from $\hat{y}\sim\hat{\mathbf{p}}$ to a roll-out from the original $p$.

Before we deal with (7), let us write a lemma that rewrites $\hat{\mathbf{p}}_{t}(G|\boldsymbol{y}_{1:t-1})$ into a more convenient form.

The lemma implies that $\hat{\mathbf{p}}(G)\geq\mathbf{p}(G)$ and that if $\mathbf{p}(G)$ is bounded away from $1$, $\hat{\mathbf{p}}(G)\geq(1+O(\delta))\mathbf{p}(G)$.

For any $t$, $\boldsymbol{h}_{t}$. Fix $G$.

Now we are ready to handle (7) with high probability in the following proposition.

For any fixed sequence $\boldsymbol{y}_{1:n}$, and the corresponding language model’s probability distribution $\mathbf{p}$ that gives conditional distributions $\mathbf{p}_{1},...,\mathbf{p}_{n}$. There exists a parameter $C_{\delta,\gamma}$ that depends only $\delta,\gamma$. Then with probability at least $1-\beta$ for any $\beta>0$ (over $G$),

where $\pi$ is a random permutation of the index set $\{1,...,N\}$.

We will now apply Lemma F.1 to lowerbound $(*)$ with high probability and to bound the absolute value of $(**)$ with high probability.

The reason why we can apply these lemmas even after we condition on $\boldsymbol{y}_{1:t-1}$ is due to the “high-probability homophily” assumption which allows us to use the fact that $\boldsymbol{y}_{1:t-1}$ is independent to $G$, i.e., the distribution of the green list remains uniform at random after we condition on each qualifying $\boldsymbol{y}_{1:t-1}$ separately.

Using a similar argument from the proof of Theorem C.4, we can apply Lemma F.1 and get that with probability $1-\beta$,

Similarly by Lemma F.1 again to bound $(**)=\sum_{i=1}^{N\gamma}\mathbf{p}_{t}[\pi[i]]-\gamma$ w.h.p for each $t$.

To put things together, with probability $1-(n+1)\beta$,

C.6.2 Many green list tokens in expectation

To obtain the lower bound in expectation, we just need to bound the expectation of (5), (6) and (7).

Also, observe that $\eqref{eq:term2}\geq 0$ under the homophily assumption (Assumption C.11).

Term (7) can be further lower bounded by a second-order Taylor expansion argument (Lemma C.18) and a variance calculation for sampling without replacement (Lemma C.21), which ends up depending on the on-average high-entropy parameter from Definition C.8. The formal result is stated in Proposition C.22.

Apply the two observations to (8), we have

By the variance formula for sampling without replacement ($N$ choose $N\gamma$),

C.7 Security property

Algorithm 2 with threshold $\tau$ satisfies the security property from Definition 2.2 with $\epsilon=0$ and

In comparison, the best bound on the security property parameter one can obtain for the scheme of Kirchenbauer et al. is (a formal statement and proof are included in Appendix D.2)

To say it differently, our method, Unigram-Watermark, utilizing a fixed Green-Red split, achieves twice the robustness to edits compared to Kirchenbauer et al. ’s baseline approach.

Appendix D Analysis of Kirchenbauer et al. [2023]

This section illustrates the soft watermarking scheme proposed by Kirchenbauer et al. . This straightforward algorithm only requires access to the language model’s logits at each time step. Let $\boldsymbol{y}=\left[y_{1},\ldots,y_{n}\right]$ represent the output sentence of language model $\mathcal{M}$ given the prompt $\boldsymbol{x}$. The watermarking scheme generates $\boldsymbol{y}_{1:n}$ by hashing $y_{t-1}$ to a partition of the token space (Green List and Red List) and amplifies the probability of tokens on the Green List. Specifically, $\left[y_{1},\ldots,y_{n}\right]$ is derived from the following Markov chain:

y_{1}\sim\text{Softmax}\big{(}\text{logits}_{\mathcal{M}}\big{(}y_{1}=\cdot|x\big{)}\big{)}

Typically, $\gamma|\mathcal{V}|$ tokens are selected to form a Green List, where $\gamma$ symbolizes the fraction of tokens to be watermarked (by default, $\gamma=0.5$). The logit value for each green token is augmented by a constant $\delta$ (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 a text was generated by a watermarked language model is achievable given knowledge of the hash function and tokenizer. The adversary constructs $\boldsymbol{u}=\left[u_{1},\ldots,u_{m}\right]$ from $\boldsymbol{x},\boldsymbol{y}_{1:n}$ and any auxiliary input. The detection algorithm calculates the quantity of green tokens $|\boldsymbol{u}|_{G}=\sum_{t=2}^{m}\mathbf{1}(u_{t}\in\text{Green}(u_{t-1}))$. One can assume the null hypothesis, denoted as $H_{0}$: The text sequence is produced independently of the green list rule. Following this, a $z$-statistic score is computed as $z=\left(|\boldsymbol{u}|_{G}-\gamma m\right)/\sqrt{m\gamma(1-\gamma)}$. If the $z$-score exceeds a predetermined threshold, the algorithm declares, “This was generated from $\hat{\mathcal{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. in the following Theorem D.1

Let $\boldsymbol{y}=\left[y_{1},\ldots,y_{n}\right]$ represent the watermarked sequence. Suppose the adversary $\mathcal{A}$ follows the definition 2.2 and outputs a modified text $\boldsymbol{u}=\left[u_{1},\ldots,u_{m}\right]$. Following Equation 2, we calculate the $z$-score of the soft watermarking Kirchenbauer et al. $z_{\boldsymbol{y}}$ and $z_{\boldsymbol{u}}$. Then we have

The proof is similar to that of Theorem 3.7 except that the maximum perturbation to $|\mathbf{y}|_{G}$ is now $2\eta$ rather than $\eta$. 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 $\mathsf{BiGrams}(\boldsymbol{u})=\{\{u_{1},u_{2}\},\{u_{2},u_{3}\},...,\{u_{n-1},u_{n}\}\}$ and similarly $\mathsf{BiGrams}(\boldsymbol{y})$ enumerates the set of all two grams in sequence $\boldsymbol{y}_{1: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.

For “deletion” at $t$, $\{u_{t-1},u_{t}\}$ and $\{u_{t},u_{t+1}\}$ become $\{u_{t-1},u_{t+1}\}$. So two elements from $\mathsf{BiGrams}(\boldsymbol{u})$ are gone.

It follows that when $\boldsymbol{y}$ is obtained after up to $\eta$ edits

Observe that $\sum_{t=2}^{n}\mathbf{1}(u_{t}\in\text{Green}(u_{t-1}))$ counts the number of qualifying elements in $\mathsf{BiGrams}(\boldsymbol{u})$, which completes the proof. ∎

For this reason, our watermark is twice as robust as that of Kirchenbauer et al. . This provides the theoretical guarantee to our empirical results presented in the experiments!

We can view our watermark as a trivial Markovian watermarking scheme with $k=0$, and what Kirchenbauer et al. proposed to be $k=1$. For the more general $k$-Markovian watermarking scheme that depends on a prefix of length $k$, the robustness deteriorates by a factor of $k$, as the maximum perturbation will become $\frac{((k+1)+\gamma/2)\eta}{\sqrt{n}}$. To say it differently, choosing $k=0$ gives the maximum robustness and maximum simplicity at the same time, and the benefit leads to significant gains in our experiments, especially against paraphrasing attacks.

Appendix E Alternative detector “Unique” and its desirable properties

Our theoretical analysis suggests a promising alternative ${\sf Detect}{}$ algorithm for Unigram-Watermark that simply involves calling Algorithm 2 with a deduplicated $\boldsymbol{y}$.

The simple change actually results in a number of interesting new properties. For example, we can state its Type I error bound a lot more cleanly now as a Corollary of Theorem C.4

With probability $1-\alpha$ (over only the randomness of $G$),

The above gives a clean finite-sample concentration bound of the Type I error using Algorithm 4. Notably, while deduplicating reduces the length of the suspect text, i.e., $m<n$, it improves the bound by ensuring both $C_{\max}$ and $V$ are $1$.

“Unique” in $K$-gram watermark section with $K\geq 2$. Clearly, the same idea of deduplication works for the whole family of $K$-gram watermark proposed in Kirchenbauer et al. . In fact, it was briefly mentioned in a remark from their paper as a mitigation measure to reduce correlation. All arguments we make about Type I error and Robustness to Edits above work for $K\geq 2$. We defer the Type II error bound for this family to a longer version of the paper.

Emperical analysis on controlling false positives. We conduct experiments to demonstrate the results for the asymptotic choice of $\tau$ in controlling false positives. The negative examples are sampled from diverse datasets, including human data in LFQA and OpenGen dataset [Krishna et al., 2023], C4 dataset [Raffel et al., 2020], and TOEFL dataset [Liang et al., 2023]. In total, we collect 6,200 unwatermarked text samples with varied lengths. We then use the dynamic threshold $\tau$ with different choices of $\alpha$ as shown in Equation 9. By choosing different random seeds, we obtain different green lists. The results in Figure 5 show the empirical false positive rate aligns well with the theoretical $\alpha$.

Kirchenbauer et al. discussed a number of interesting attacks on the $K$-gram watermarks. In this section, we inspect the robustness of Unigram-Watermark (with both Algorithm 2 and 4 as ${\sf Detect}{}$) to these attacks.

We will focus on those trickier generative attacks, as those non-generative attacks on the surface level (e.g., synonym substitution, Unicode substitution) were rather satisfactorily addressed in Kirchenbauer et al. . The same arguments work for Unigram-Watermark. However, there are trickier ones that break $K$-gram watermarks for $K\geq 2$ but not for $K=1$, especially when we use Algorithm 4 for detection.

To be clear, these attacks are, in fact, not post-processing-based evasion attacks, but rather hacks into prompts. Nevertheless, our watermark that is robust to edits turns out to be quite resilient to them.

Appendix F Technical lemmas

Let $\{a_{i,j}\}_{1\leq i,j\leq n}$ be a collection of non-negative numbers and $\Pi_{n}$ be a random uniform permutation. Let $Z_{n}=\sum_{i=1}^{n}a_{i,\Pi_{n}(i)}$. Then, for any $t>0$

where $\mathcal{F}_{1}\subseteq\mathcal{F}_{2}\subseteq...\subseteq\mathcal{F}_{n}\subseteq\mathcal{F}_{n+1}\subseteq...$ is a filtration. Specifically, $\mathcal{F}_{n}$ can be the sigma-algebra generated by another sequence of random variable $Y_{1},...,Y_{n}$, i.e., $\mathcal{F}_{n}=\sigma(Y_{1:n})$ and $X_{n}$ can be a function of $Y_{1:n}$.