Undetectable Watermarks for Language Models

Introduction

With the rise in the use of artificial models that churn out human-like text, there’s also an increase in the potential for misuse. Imagine a student employing a language model to effortlessly write her “Machine Learning 101” homework or conjuring up tear-jerking emails to beg professors for easier exams. That’s when the need arises to distinguish between texts penned by a language model and those crafted by human hands. The go-to method of employing a heuristic test to determine if a text was AI-generated, however, grows increasingly fragile as large language models (LLMs) advance. Even the cutting-edge detectors, like GPTZero [Tia23], can be outsmarted with cleverly crafted prompts.

Ultimately, as LLM outputs move closer to becoming identical to human-generated text, this approach becomes hopeless. It is already very hard to tell, for instance, that the previous paragraph was written by such a model. To overcome this problem, it is reasonable to consider intentionally modifying the model to embed watermarks into the text. Recent work of [KGW+23] introduced such watermarks in the context of LLMs. However, existing watermarking schemes come with a cost: To plant a useful watermark, the distribution of texts the model generates has to be noticeably changed. In fact, for existing schemes it is possible for the user to distinguish between outputs of the original model and of the watermarked one, and it is hence possible that the quality of text degrades.

We show how to plant watermarks with the following properties, stated informally, in any LLM.

(Undetectability) It is computationally infeasible to distinguish between the original and the watermarked models, even when the user is allowed to make many adaptive queries. In particular, the quality of generated text remains identical.

(Completeness) There is a secret key that enables efficient detection of responses from the watermarked model, as long as “enough randmoness” was used to generate the response. The detection works even when presented with only a contiguous sub-string from the response, and it doesn’t require any other information.

(Soundness) Any text generated independently from the secret key has a negligible chance of being detected as watermarked.

We note that the existence of a secret key is necessary, as otherwise Properties (1) and (2) would directly contradict each other. However, in practice the secret key can be published if one wishes; Property (1) still ensures that the quality of the text is imperceptibly changed for all uses not involving the secret key.

An important aspect of our construction is that Properties (1) and (3) will always hold, for any LLM with any choice of parameters, and without making any assumptions on the text. Our scheme is the first to have these properties, and we argue that they are completely crucial. First, the creator of a state-of-the-art LLM is unlikely to intentionally degrade the quality of their model, making Property (1) necessary for any practical watermarking scheme. As the quality and versatility of LLMs has reached such high levels, any noticeable change due to the watermark is liable to have adverse side-effects in some situations. Second, falsely accusing humans of using LLMs to generate their texts should be completely unacceptable. When heuristics are used for detection, this will always be a possibility — indeed, instances of such false accusations against students have already made news headlines [Fow23, Jim23], and concerningly, false accusations are more common for non-native English writers [LYM+23]. Property (3) in our construction rigorously guarantees that natural text will not be detected as watermarked.

Of course, a watermark is only useful if it can be detected with the secret key. If the model has a deterministic response to some prompt, then we should not be able to embed the watermark in that response (as any change to the output would necessarily be detectable). For Property (2), we therefore need to assume that enough “randomness” was used in the generation of the specific text we are considering. We introduce a formal notion that we call empirical entropy, and show that this condition is necessary. Our detection algorithm works when it is given text containing any consecutive sub-string with enough empirical entropy from an output of the model.

Primary contributions of this work include the formal definition and construction of undetectable watermarks, and the notion of empirical entropy that quantifies the randomness used in the generation of a specific output. These definitions and our results appear in Section 2.

Approaches for detecting AI-generated text largely fall into two categories. Watermarking schemes alter the output of a language model in a way that a corresponding detection algorithm can identify. Post-hoc detectors leave the output of the model unchanged and instead identify AI-generated text using existing differences between natural language and the model’s output.

The simplest post-hoc detectors use natural heuristics to distinguish between human- and AI-generated text. These heuristics include relative entropy scoring [LUY08], perplexity [Ber16], and other statistical methods [GSR19]; see [Ber16] for a survey of such methods. Other post-hoc detectors (e.g., [ZHR+19, MLK+23, Tia23, KAAL23]) are themselves models, specifically trained for this binary classification task. Unfortunately, these heuristic and model-based methods lack formal guarantees, and it’s possible to train a model to transform AI-generated text in a way that evades them; see, e.g., [KSK+23, SKB+23]. For example, [KSK+23] trains a model to paraphrase text output by language models, fooling common post-hoc detectors such as GPTZero [Tia23], DetectGPT [MLK+23], and the detector developed by OpenAI [KAAL23]. Furthermore, simple tricks such as instructing the model in the prompt to write a response that evades a detector, or varying the model’s parameters (e.g., increasing the temperature and frequency/presence penalties for GPT-4), fool [Tia23]. [CBZ+23] prove that as AI-generated text more closely resembles natural text, post-hoc detectors will need longer text samples.

See [JAML20] for more comprehensive background on post-hoc detection of AI-generated text and attacks.

Language watermarking schemes.

Several schemes (e.g., [AF21, QZL+23, YAJK23, MZ23]) involve using an ML model in the watermarking algorithm itself. [AF21, MZ23] work by taking a passage of text and using a model to produce a semantically similar altered passage. By nature of using machine learning, these constructions have no formal guarantees and rely on heuristic arguments for undetectability, soundness, and correctness.

In a recent work, [KGW+23] presented the first watermarking scheme for LLMs with any formal guarantees. They showed that a watermark can be planted in outputs with large enough entropy (with a definition different than ours, yet morally similar). However, their watermarking scheme crucially changes the distribution of generated texts and uses this change to detect the watermark. They bound the difference between the original distribution and the distribution of their watermarked model, using a quantity called perplexity. In contrast, in our work the original and watermarked output distributions are completely indistinguishable.

The authors of this paper are also aware of an ongoing watermarking project of [Aar22], which he mentions in his blog. It appears that in this project, the guarantee is that the two distributions will be indistinguishable, but only as long as no two output texts are seen that share a common substring of a certain length. In contrast, our construction guarantees undetectability without any assumption on the texts or the model. In particular we allow the distinguisher to make adaptive queries with arbitrary prompts, so it may force the model to return outputs that share long parts with each other.

Our scheme, as well as those of [KGW+23] and [Aar22] are vulnerable to simple attacks such as the “emoji attack”https://twitter.com/goodside/status/1610682909647671306 discussed in [KGW+23]. We discuss attacks on watermarking schemes further in Section 6.1.

Steganography.

Steganography is the study of encoding a hidden message into a given channel (e.g., natural language or an image) such that a recipient possessing a key can read the message but an eavesdropping adversary cannot determine whether a message is present. [HvAL09] defines security of a steganography scheme against a chosen hiddentext attack (CHA) as the requirement that an adversary cannot determine whether a given oracle is for the original distribution or the distribution embedded with a hiddentext. Porting this definition over to the watermark setting, one would obtain undetectability. However, the corresponding steganography schemes we are aware of would not obtain undetectability without making assumptions about the entropy of the channel. Crucially, in our setting where prompts for the language model are adversarially chosen, we want to retain undetectability even if the adversary submits a prompt with a deterministic response.

Part of the reason for this difference stems from the access that the watermark and encoding algorithms have to the channel (or the distribution of the language model’s output). In steganography, the encoding algorithm has only oracle access to the channel. In our language model setting, the watermark algorithm receives from the model a full description of the probability distribution $p_{i}$ for each token. Because of this limited access, steganography schemes largely either rely on assumptions about the entropy of the channel (e.g., [HvAL09]) or lose security when the channel has low entropy (e.g., [DIRR09]). Our watermark is undetectable regardless of the entropy of the text. We achieve this guarantee exactly by using the watermark algorithm’s access to the distributions $p_{i}$. Using this knowledge, the algorithm is able to compute the empirical entropy of its output thus far. Once the empirical entropy is sufficiently high, it uses the output as a random seed for a PRF used to embed the watermark in subsequent tokens. Importantly, our algorithm alters the output distribution only once it has collected enough entropy; in the steganography schemes, the encoding algorithm with only oracle access does not know when this has happened.

This complete knowledge of each token distribution $p_{i}$ separates the problem of watermarking language models from watermarking more generally. One prior steganography scheme for language models, [KJGR21], operates in our regime where the encoding algorithm has access to each $p_{i}$. However, it assumes that the decoding algorithm has access to each $p_{i}$ as well. This is unrealistic for watermarking, as the probability distributions $p_{i}$ for the output of the model on some prompt depend on that prompt. A watermark detection algorithm, which receives only the output and not the prompt, does not know the distributions $p_{i}$. In practice, it would be unrealistic to assume that a detector trying to determine whether an essay was generated by a language model would also be given the prompt used to generate it.

Watermarking.

The field of digital watermarking focuses on the problem of covertly planting a signal in a medium (e.g., an image or text) such that it can be detected by an algorithm. [ARC+01, ARH+03] present some of the first watermarking schemes for NLP-generated text, though their schemes rely on a syntactic tree structure that was present in NLP models at that time but no longer used today. [HMW07] formally defines watermarking and desired properties, though these definitions are not tailored to language models.

Other related work.

Recently, [GKVZ22] used a cryptographic construction to embed undetectable backdoors into neural networks. In both their work and ours, cryptographic notions of indistinguishability are used in the context of machine-learning, rather than empirical notions.

2 Organization of the Paper

In Section 2 we formally define our model, introduce the notions of empirical entropy and undetectable watermarks, and outline our results. In Section 3 we sketch a simple watermarking scheme that achieves undetectability, but falls short of our main scheme in other respects. In Section 4 we construct our undetectable watermarks with strong completeness and soundness guarantees. We include an overview of these constructions in Section 4.2. In Section 5 we discuss the necessity of the assumptions we make. In Section 6 we discuss possible methods of removing watermarks from texts. In particular, we prove that it is impossible to create undetectable watermarks that are completely unremovable, under certain assumptions. In Section 7 we summarize and discuss open problems.

Modeling the Problem

Let $\secpar$ denote the security parameter. A function $f$ of $\secpar$ is negligible if $f(\secpar)\in O(\frac{1}{\poly(\secpar)})$ for every polynomial $\poly(\cdot)$. We denote $f(\secpar)\leq\negl$ to mean that $f$ is negligible. For a vector or sequence of tokens $s=(s_{1},\ldots,s_{\absolutevalue{s}})$ and positive integers $b\geq a$, let $s[a:b]$ denote $(s_{a},\ldots,s_{b})$. We use $\log(x)$ to denote the logarithm base 2 of $x$, and $\ln(x)$ to denote the natural logarithm of $x$. For integer $n>0$, we define $[n]:=\{1,\dots,n\}$. For integers $n\geq k>0$, we define $[k,n]:=\{k,\dots,n\}$.

Pseudorandom function (PRF).

2 Language Models

We loosely follow [KGW+23] in our definition of a language model. We will often refer to language models simply as models.

A language model $\mathsf{Model}$ over token set $\cal{T}$ is a deterministic algorithm that takes as input a prompt prompt and tokens previously output by the model $x=(x_{1},\ldots,x_{i-1})$, and outputs a probability distribution $p_{i}=\mathsf{Model}(\textsc{prompt},x)$ over $\cal{T}$.

A language model $\mathsf{Model}$ is used to generate text as a response to a prompt by iteratively sampling from the returned distribution until a special terminating token $\texttt{done}\in\cal{T}$ is drawn.

A language model’s response to a prompt prompt is a random variable $\overline{\mathsf{Model}}(\textsc{prompt})\in\mathcal{T}^{\star}$ that is defined algorithmically as follows. We begin with an empty list of tokens $x=()$. As long as the last token in $x$ is not done, we draw a token $x_{i}$ from the distribution $\mathsf{Model}(\textsc{prompt},x)$ and append it to $x$. Finally, we set $\overline{\mathsf{Model}}(\textsc{prompt})=x$.

Throughout the text we will make use of a security parameter $\lambda$. We will assume that our model never outputs text of length super-polynomial in $\lambda$. (For OpenAI’s language models, there is actually a fixed limit to the length of generated text.)

3 Entropy and Empirical Entropy

Let $\log(x)$ denote the logarithm base 2 of $x$. For a probability distribution $D$ over elements of a finite set $X$, we define the Shannon entropy of $D$ as

where $D(x)$ is the probability of $x$ in the distribution $D$. The empirical entropy of $x$ in $D$ is simply $-\log D(x)$. The expected empirical entropy of $x\sim D$ is exactly $H(D)$. Intuitively, the empirical entropy of $x$ (with respect to $D$) is the number of random bits that were required to draw $x$ out of the distribution $D$. The entropy $H(D)$ is thus the expected number of random bits needed to draw an element out of the distribution $D$.

We thus define the empirical entropy of a model’s response as follows.

For a language model $\mathsf{Model}$, a prompt prompt, and a possible response $x\in\mathcal{T}^{\star}$, we define the empirical entropy of $\overline{\mathsf{Model}}$ responding with $x$ to prompt as

We next generalize the definition of empirical entropy from whole outputs to substrings out of a model’s output. Intuitively, we want to measure how much entropy was involved in the generation of a particular contiguous substring of the output.

For a language model $\mathsf{Model}$, a prompt prompt, a possible response $x\in\mathcal{T}^{\star}$, and indices $i,j\in[\absolutevalue{x}]$ with $i\leq j$ we define the empirical entropy on substring $[i,j]$ of $\overline{\mathsf{Model}}$ responding with $x$ to prompt as

We sometimes write $H_{e}^{i}:=H_{e}^{[i,i]}$ to denote the empirical entropy of a single token $i$. We remark that in expectation, Definition 3 simply captures the entropy in the response generation. That is, we have

where $x\sim\overline{\mathsf{Model}}\left(\textsc{prompt}\right)$.

4 Watermarks

We formally define a watermarking scheme as follows.

A watermarking scheme for a model $\mathsf{Model}$ over $\cal{T}$ is a tuple of algorithms $\mathcal{W}=(\mathsf{Setup},\mathsf{Wat},\mathsf{Detect})$ where:

$\mathsf{Setup}(1^{\secpar})\to\sk$ outputs a secret key, with respect to a security parameter $\secpar$.

$\mathsf{Wat}_{\sk}(\textsc{prompt})$ is a randomized algorithm that takes as input a prompt prompt and generates a response in $\cal{T}^{\star}$.

$\mathsf{Detect}_{\sk}(x)\to\{\true,\false\}$ is an algorithm that takes as input a sequence $x\in\cal{T}^{\star}$ outputs $\true$ or $\false$.

Ideally, $\mathsf{Detect}_{\sk}(x)$ should output $\true$ if $x$ is generated by $\mathsf{Wat}_{\sk}(\textsc{prompt})$, and should output $\false$ if $x$ is generated independently of $\sk$. The former property is called completeness and the latter soundness.

A watermarking scheme $\mathcal{W}$ is sound if for every security parameter $\secpar$ and token sequence $x\in\mathcal{T}^{\star}$ of length $\absolutevalue{x}\leq\poly(\lambda)$,

A scheme is sound if any text that is generated independently from $\sk$ has negligible probability of being detected as watermarked by $\mathsf{Detect}_{\sk}$. Essentially, this means we will never see a false-positive detection.

Defining completeness requires care: It is not reasonable to require $\mathsf{Detect}_{\sk}$ to detect any sequence $x$ generated by $\mathsf{Wat}_{\sk}(\textsc{prompt})$ for some prompt, as it is possible that $x$ is very short, or that $\overline{\mathsf{Model}}(\textsc{prompt})$ is deterministic or has very low entropy. Instead, we require $\mathsf{Detect}_{\sk}$ to detect watermarks only in responses for which the entropy in the generation process is high enough.

A watermarking scheme $\mathcal{W}$ is $b(L)$-complete if for every security parameter $\lambda$ and prompt prompt of length $\absolutevalue{\textsc{prompt}}\leq\poly(\lambda)$,

Definition 7 guarantees that any output generated by $\mathsf{Wat}_{\sk}$ with empirical entropy at least $b(L)$, where $L$ is the length of the output, will be detected as watermarked with high probability. Essentially, this means we will never see a false-negative detection on any output of high enough empirical entropy. In Section 5 we show that it is necessary to consider the empirical entropy of the specific output rather than the standard entropy of the entire model.

We also generalize Definition 7 to capture contiguous substrings of outputs. That is, we should be able to detect a watermarked output of $\mathsf{Wat}_{\sk}$ even if $\mathsf{Detect}_{\sk}$ is only given a long enough contiguous substring from it.

A watermarking scheme $\mathcal{W}$ is $b(L)$-substring-complete if for every prompt prompt and security parameter $\lambda$,

This means that every contiguous part of an output of the watermarking procedure, that has high enough empirical entropy, is detected as watermarked with high probability. We stress that the empirical entropies in Definitions 7 and 8 are defined with respect to the original model $\mathsf{Model}$, without reference to the watermarking procedure $\mathsf{Wat}_{\sk}$. We also note that the empirical entropy $H_{e}(\mathsf{Model},\textsc{prompt},x)$ is only used as part of the definition, and is not necessarily known to $\mathsf{Detect}_{\sk}$. It is in general not possible to compute $H_{e}(\mathsf{Model},\textsc{prompt},x)$ without knowledge of prompt.

5 Undetectable Watermarks

Finally, we define the notion of computationally undetectable watermarking schemes. Intuitively, a scheme is undetectable if it is infeasible to distinguish between the distributions of $\overline{\mathsf{Model}}$ and $\mathsf{Wat}_{\sk}$, even when those can be queried adaptively with arbitrary prompts.

A watermarking scheme $\mathcal{W}=(\mathsf{Setup},\mathsf{Wat},\mathsf{Detect})$ is undetectable if for every security parameter $\secpar$ and all polynomial-time distinguishers $D$,

where the notation $D^{\mathcal{O}_{1},\mathcal{O}_{2}}$ means that $D$ is allowed to adaptively query both $\mathcal{O}_{1}$ and $\mathcal{O}_{2}$ with arbitrary prompts.

Note that in the above definition, we allow the distinguisher access to $\mathsf{Model}$ itself as well as $\overline{\mathsf{Model}}$ or $\mathsf{Wat}_{\sk}$. The only thing that is kept secret from the distinguisher is the secret key.

It is important to remark that in any undetectable watermarking scheme, the quality of outputs must be identical between $\overline{\mathsf{Model}}$ and $\mathsf{Wat}_{\sk}$, as otherwise it would be possible to distinguish between them. In particular, embedding the watermark does not degrade the quality of the generated text at all.

We finally note that a watermarking scheme can be made public by publishing the secret key $\sk$. Then, everyone can run the detection algorithm $\mathsf{Detect}_{\sk}$. In particular, the scheme is no longer undetectable as $\mathsf{Detect}_{\sk}$ can be used to distinguish between $\overline{\mathsf{Model}}$ and $\mathsf{Wat}_{\sk}$. Nevertheless, we still maintain the property that there is no degradation in the quality of watermarked outputs, as long as the definition of “quality” does not depend on the secret key $\sk$.

6 Statement of our Theorems

We are now ready to formally state the guarantees of the watermarking schemes that we present. To warm up, in Section 3 we give a simple construction of an $O\left(\lambda\right)$-complete scheme, but it only achieves a much weaker notion of soundness, and the watermarking algorithm runs in expected $\poly(\lambda)$ time rather than strict $\poly(\lambda)$ time. In Section 4.3, we prove the following theorem by introducing an efficient watermarking scheme with Algorithms 3 and 4.

For any model $\mathsf{Model}$ we construct a watermarking scheme $\mathcal{W}$ that is undetectable, sound, and $O(\lambda\sqrt{L})$-complete.

This means that our watermarking scheme is always undetectable and sound, and is also complete as long as there is enough empirical entropy in the model’s response.

In Section 5 we show that it is necessary for the completeness parameter $b(L)$ to be reasonably large, with respect to $\lambda$. In fact, we show that it is inherent that low empirical entropy outputs are not watermarked in any undetectable watermarking scheme for any model.

To strengthen Theorem 1, we also present a modified scheme (Algorithms 5 and 6) in Section 4.4 which obtains substring completeness, with similar parameters.

For any model $\mathsf{Model}$ we construct a watermarking scheme $\mathcal{W}$ that is undetectable, sound, and $O(\lambda\sqrt{L})$-substring-complete.

In Section 6 we discuss known attacks on methods of detecting AI-generated text. We also prove that any undetectable watermarking scheme is removable, if the model enables a fairly strong form of query access and if one is willing to expend a number of queries that grows linearly with the size of generated text. Finally, in Section 7 we pose some open problems related to this work.

Simplified Construction

In this section we describe a simple construction of an undetectable watermarking scheme that achieves $\Theta\left(\lambda\right)$-completeness. However, this scheme falls short of our main constructions in Section 4 in two important ways. First, it has a false-positive rate of $\varepsilon=1/\poly(\lambda)$ instead of $\negl$. We call such a scheme $\varepsilon$-weakly-sound. Second, the watermarking procedure $\mathsf{Wat}_{\sk}$ is not very efficient: Its expected run-time is polynomial in the length of the output and in $\frac{1}{\varepsilon}$, but the worst-case running time of $\mathsf{Wat}_{\sk}$ is unbounded.

Later, in Section 4 we present our main construction which is undetectable, sound, complete (in fact, it is even substring-complete) and efficient, yet achieves suboptimal completeness. Bridging this gap is an interesting open problem discussed in Section 7.

We begin by adding another strong assumption, that the min-entropy of the response to any prompt is at least $5\secpar$. Equivalently, let prompt be a prompt and assume that for every $x$, we have $H_{e}(\mathsf{Model},\textsc{prompt},x)\geq 5\lambda$. We define the watermarking scheme as follows. The distribution of $\mathsf{Wat}^{\mathcal{O}}(\textsc{prompt})$ is defined as the distribution of $x\sim\overline{\mathsf{Model}}(\textsc{prompt})$ conditioned on $\mathcal{O}(x)=0^{b}$. Equivalently, $\mathsf{Wat}^{\mathcal{O}}(\textsc{prompt})$ repeatedly draws outputs from $\overline{\mathsf{Model}}(\textsc{prompt})$ until the first time it gets a response $x$ for which $\mathcal{O}(x)=0^{b}$, and then it returns $x$. Note that this requires $2^{b}$ calls to $\overline{\mathsf{Model}}(\textsc{prompt})$ in expectation. To detect whether a string $x$ is watermarked, $\mathsf{Detect}^{\mathcal{O}}$ simply checks whether $\mathcal{O}(x)=0^{b}$. We assume that $b\leq\lambda$ and sketch a proof for the above scheme being weakly sound, complete and undetectable.

For any string $x$, the value of $\mathcal{O}(x)$ is truly random by the assumption. Thus, it is detected as watermarked with probability $2^{-b}$.

Complete:

By definition, $\mathsf{Wat}^{\mathcal{O}}(\textsc{prompt})$ only produces outputs $x$ such that $\mathcal{O}(x)=0^{b}$, which are detected as watermarked by $\mathsf{Detect}^{\mathcal{O}}$.

Undetectable:

Let $D$ be a distinguisher that can query $\mathsf{Wat}^{\mathcal{O}}(\textsc{prompt})$ at most $2^{\lambda}$ times. In expectation, the total number of times $\mathsf{Wat}^{\mathcal{O}}(\textsc{prompt})$ queries $\overline{\mathsf{Model}}(\textsc{prompt})$ to answer all queries is at most $2^{\lambda}\cdot 2^{b}\leq 2^{2\lambda}$ (since $b\leq\secpar$ by assumption). As the probability of each output $x$ to be output by $\overline{\mathsf{Model}}(\textsc{prompt})$ is at most $2^{-5\lambda}$, and as $2^{2\lambda}\ll\sqrt{2^{5\lambda}}$, with high probability $\mathcal{O}$ is never queried twice on the same input. If $\mathcal{O}$ is never queried on the same input twice, then it simply outputs an independent random value for each query. In particular, the process of repeatedly sampling $x\sim\overline{\mathsf{Model}}(\textsc{prompt})$ until $\mathcal{O}(x)=0^{b}$ is equivalent to repeatedly sampling $x\sim\overline{\mathsf{Model}}(\textsc{prompt})$ until an independent, fresh random string is $0^{b}$ — which is identical to simply sampling $x\sim\overline{\mathsf{Model}}(\textsc{prompt})$.

2 Removing the high min-entropy assumption

We next define a scheme that no longer requires the assumption about the min-entropy of the model. We do so by only watermarking outputs with empirical entropy higher than $6\lambda$, corresponding to the definition of $(6\lambda)$-complete schemes.

Let prompt be any prompt and consider the probability

Denote by $M_{\leq}$ the distribution $x\sim\overline{\mathsf{Model}}(\textsc{prompt})$ conditioned on $H_{e}\left(\mathsf{Model},\textsc{prompt},x\right)\leq 6\lambda$. Similarly, denote by $M_{>}$ the distribution $x\sim\overline{\mathsf{Model}}(\textsc{prompt})$ conditioned on $H_{e}\left(\mathsf{Model},\textsc{prompt},x\right)>6\lambda$. Drawing $x\sim\overline{\mathsf{Model}}(\textsc{prompt})$ is equivalent to the following process: with probability $p$, we draw a string out of the distribution $M_{>}$, otherwise, we draw a string out of $M_{\leq}$.

Therefore, we consider the following natural algorithm for $\mathsf{Wat}^{\mathcal{O}}$. We first flip a biased coin $c\sim\text{Bernoulli}(p)$. If $c=0$ then we draw an output from the distribution $M_{\leq}$. If $c=1$, then we apply the algorithm of Section 3.1 — that is, we draw an output from the distribution $x\sim M_{>}$ conditioned on $\mathcal{O}(x)=0^{b}$.

This scheme is again weakly sound, and it is complete for every output $x$ with empirical entropy at least $6\lambda$ because these outputs will always satisfy $\mathcal{O}(x)=0^{b}$. If $p\leq 2^{-\lambda}$, then undetectability is straightforward: with all but negligible probability, the distinguisher will only see outputs from $M_{\leq}$, which we did not change. Otherwise, $p>2^{-\lambda}$ and thus the distribution $M_{>}$ is of min-entropy at least $6\lambda-\lambda=5\lambda$. In particular, the construction of Section 3.1 applied to $M_{>}$ is guaranteed to be undetectable.

We finally note that it is intractable to compute the value of $p$ or the conditional distributions $M_{\leq},M_{>}$. We avoid their explicit computation as follows. To implement $\mathsf{Wat}^{\mathcal{O}}$, we first draw a string $x\sim\overline{\mathsf{Model}}(\textsc{prompt})$. Computing the empirical entropy $H_{e}(\mathsf{Model},\textsc{prompt},x)$ given $\mathsf{Model},\textsc{prompt},x$ is straightforward. The probability that $H_{e}(\mathsf{Model},\textsc{prompt},x)>6\lambda$ is of course exactly $p$. Thus, we can check if $H_{e}(\mathsf{Model},\textsc{prompt},x)\leq 6\lambda$. If so, we simply output $x$. Otherwise, we need to sample a response from $M_{>}$ conditioned on its output under $\mathcal{O}$ being $0^{b}$. We can do so by repeatedly sampling $x\sim\overline{\mathsf{Model}}(\textsc{prompt})$ until both $H_{e}(\mathsf{Model},\textsc{prompt},x)>6\lambda$ and $\mathcal{O}(x)=0^{b}$. Note that the probability of success is now $p\cdot 2^{-b}$, and thus in expectation $\frac{1}{p}2^{b}$ tries are needed, which may be very large if $p$ is small. On the other hand, we only reach this loop with probability $p$; hence, the expected number of queries from $\overline{\mathsf{Model}}(\textsc{prompt})$ our algorithm makes is $1+p\cdot\frac{1}{p}2^{b}=1+2^{b}$.

3 Removing the random oracle assumption

The construction presented so far uses a random oracle $\mathcal{O}$, which is impossible to implement.Note that we cannot sample the values of $\mathcal{O}$ on-the-fly, because $\mathsf{Wat}$ and $\mathsf{Detect}$ need to agree on all of the used values. Often, as we also do later in Section 4, a random oracle can be replaced with a cryptographic pseudorandom function (PRF, defined in Section 2.1). However, the inefficiency of $\mathsf{Wat}^{\mathcal{O}}$ requires being careful about this switch.

A PRF with a security parameter $\lambda$ requires memory and runtime $\poly(\lambda)$ and is guaranteed to be indistinguishable from a random oracle only to distinguishers that run in time $\poly(\lambda)$ as well. As $\mathsf{Wat}^{\mathcal{O}}$ runs in (expected) time $2^{b}$, we must choose $b=O(\log\lambda)$ for the PRF to behave as a random oracle. This implies that the soundness is no longer $\negl$, but is at least $\frac{1}{\poly(\lambda)}$.

Pseudo-code for this simplified scheme is presented in Algorithms 1 and 2. We state the properties of this scheme in Theorem 3 without proof; the proofs of these properties were sketched in the preceding two sections.

For any $\lambda,\mathsf{Model}$ and $b\leq O(\log\lambda)$, Algorithms 1 and 2 are a watermarking scheme $\mathcal{W}$ that is undetectable, $(6\lambda)$-complete, and $2^{-b}$-weakly-sound. On expectation, $\mathsf{Wat}_{\sk}$ makes $1+2^{b}$ calls to $\overline{\mathsf{Model}}$ to generate each response.

This construction already demonstrates the importance of our completeness definition (Definition 7): Only trying to watermark outputs of high empirical entropy was crucial for this simple construction’s undetectability. As we will see in Section 5, only watermarking high empirical entropy outputs is in fact inherent to undetectable watermarking schemes.

Constructing Undetectable Watermarks

For ease of presentation and analysis, we describe our watermarking scheme as operating on text encoded as a binary string. That is, we assume that the token set is $\mathcal{T}=\{0,1\}$.

Note that this assumption is without loss of generality: We can easily convert a model $M$ with an arbitrary token set $\mathcal{T}$ into a model $M^{\prime}$ with a binary token set. First, we encode each token in $\mathcal{T}$ as a distinct string in $\{0,1\}^{\log|\mathcal{T}|}$; note that every codeword has length at most $\log|\mathcal{T}|$. For GPT-4, the number of tokens is $\absolutevalue{\mathcal{T}}=100,277$, and thus $\log|\mathcal{T}|\approx 17$ [Ope23]. Let $E$ denote this encoding function, and let $p_{i}$ be a distribution over $\mathcal{T}$ output by $M$. We convert $p_{i}$ into a series of distributions $p^{\prime}_{i,j}$ for $M^{\prime}$, where $p^{\prime}_{i,1}$ is the distribution of the first bit of the codeword corresponding to a token sampled from $p_{i}$. That is, $p^{\prime}_{i,1}(0)=\Pr_{t\leftarrow p_{i}}[E(t)_{1}]$, where $E(t)_{1}$ denotes the first bit of $E(t)$. Let $b_{i,1}$ denote the bit sampled by $M^{\prime}$ from $p^{\prime}_{i,1}$. Each subsequent $p^{\prime}_{i,j}$ is then sampled according to the distribution of the $j^{\text{th}}$ bit of the codeword corresponding to a token sampled from $p_{i}$, conditioned on the previous bits being equal to $b_{i,1},b_{i,2},\ldots,b_{i,j-1}$. After $M^{\prime}$ samples the last bit of the current token from $p^{\prime}_{i,|\mathcal{T}|}$, it calls $M$ to obtain the distribution $p_{i+1}$ for the next token.

Therefore, a watermarking scheme for binary alphabets can be used on models with token alphabets of arbitrary size using the above reduction. We note that the expected length of the encoding can be reduced by using a Huffman encoding of the token set instead of an arbitrary encoding.

2 Overview of the Construction

In Section 3, we saw a simple scheme that plants a watermark by sampling only texts for which an easily checkable predicate holds. In order to make this scheme more efficient, a natural idea is to sample tokens one at a time. If we don’t require undetectability, an easy way to do this is to use a $\{0,1\}$-valued hash function $h$ and sample tokens $x_{j}$ with preference for those satisfying $h(x_{j})=1$. Given some text, we can determine whether a watermark is present by computing the hash of each token. In watermarked text, more tokens should hash to 1 than to 0; in un-watermarked text, there should be no bias. This is a classic idea in steganography, discussed in [HvAL09]. It is essentially the idea used in [KGW+23].

Unfortunately, this strategy significantly alters the output distribution, making it easily detectable: It prefers half of the words in the token set. As long as a biasing strategy yields a significant expected gap between the incidence of some predicate in watermarked text versus natural text, the resulting scheme should yield an observable watermark. Our objective is to plant a signal without noticeably changing the distribution of each token.

We first discuss a watermarking scheme that can only be used to generate a single output text of a predetermined maximum length $L$, for an arbitrary prompt. The secret key shared by the watermarked model and the detection algorithm will be a sequence $\vec{u}=u_{1},\dots,u_{L}$ of uniformly chosen real numbers in the range $$. Even though this state is independent of the prompt the model will receive, we show that this shared state is enough to plant a watermark in any single response. From the perspective of a user who doesn’t know the secret key$\vec{u}$, the distribution of outputs is not changed at all.

When generating a response, the watermarked model will use the secret key to decide on each output token. Consider the generation of the $j$-th token in the response, after the previous tokens are already decided. Let $p_{j}(1)$ denote the probability, according to the real model, of this token being $1$. The watermarked model outputs $x_{j}=1$ if $u_{j}\leq p_{j}(1)$ and $x_{j}=0$ otherwise. As $u_{j}$ was drawn uniformly from $$, the probability that the watermarked model output$x_{j}=1$is exactly$p_{j}(1)$. Therefore, the distribution of generated text (in a single response) does not change at all. Nevertheless, we next show that the detection algorithm can compare the generated text to the shared sequence$\vec{u}$, and deduce that the generated output was drawn from the watermarked model.

For each text bit $x_{j}$, the detection algorithm can compute a score

Given a string $x=(x_{1},\ldots,x_{L})$, the detection algorithm sums the score of all text bits

Crucially, the detection algorithm does not need to know the distributions with which the model produces output bits. Since the detection algorithm does not have access to the prompt, it would not be able to compute those distributions.

We observe that the expected score is higher in watermarked text, as $u_{j}$ is correlated with the output bit $x_{j}$. In non-watermarked text, the value of $u_{j}$ is independent of the value of $x_{j}$. Therefore, $s(x_{j},u_{j})$ is simply an exponential random variable with mean $1$:

For watermarked outputs, on the other hand,

We’ve shown that there’s a substantial gap between the expected scores of watermarked and natural text, as long as the text generation has high entropy. This should give us hope that this biasing strategy yields a reliable detector, but there are a few obstacles left on the way.

First, the expectation argument turns out to not be very useful because the variance of the score could be large. In Section 5 we discuss why this implies that we must consider empirical entropy instead of the entropy of the entire model. In Sections 4.3 and 4.4 we use empirical entropy to build effective distinguishers.

Second, the scheme described above is only indistinguishable for a single response, and that response must be shorter than the secret key. A natural idea is to use a psuedorandom function (refer to Section 2.1 for a definition) to determine the values $u_{j}$, instead of drawing them all in advance. For example, by setting $u_{j}=F_{\sk}(j)$ the length of any single response no longer has to be bounded. As $F_{\sk}$ is queried on each input $j$ at most once, the values of $u_{j}$ are pseudorandom and the distribution of a single watermarked output is computationally indistinguishable from the original distribution. The question becomes: Can we deal with multiple responses? One of our main contributions, and the most substantial difference from all prior work, is to answer this question in the affirmative.

Let $r^{(i)}$ be a unique identifier assigned to each response. This might be a global counter or a random string (usually referred to as a nonce). To sample the $j$-th token of the $i$-th response we can use $u_{j}^{(i)}=F_{\sk}(r^{(i)},j)$. If all pairs $(r^{(i)},j)$ are unique, then the values of $u^{(i)}_{j}$ are pseudorandom. However, the detection algorithm needs to know $r^{(i)}$ to compute the detection score. If $r^{(i)}$ is a counter, then we would need to keep a global state to maintain it. Moreover, to use the detection algorithm we would need to enumerate over all possible counter values. If $r^{(i)}$ is a long random string, no global state is needed, but the detection algorithm still needs to know $r^{(i)}$. While $r^{(i)}$ must be recoverable by the detection algorithm, it cannot simply be written in the output text, as we might as well just append “WATERMARK!” to it instead (which would obviously change the distribution of outputs). Our solution is to use real randomness to generate the first few tokens of each output, keeping track of how much entropy we used in the process. Once this entropy passes some specified threshold, we use the high-entropy prefix as $r^{(i)}$. Since these prefixes have high enough entropy, all choices of $r^{(i)}$ will be unique with all but negligible probability. The detection algorithm will test whether any prefix in the text, if used as $r^{(i)}$, will yield an unusually high score for the remainder of the text. The details of this construction are presented in Section 4.3.

In the above sketch the detector needs the entire output from the model to detect the watermark. We describe a modification of this scheme in Section 4.4 which is able to detect the watermark, even when it is given only an contiguous substring of the output with sufficiently high entropy. Essentially, this modification works the same except it “resets” the choice of $r^{(i)}$ whenever enough new entropy is observed.

3 Constructing Undetectable Watermarks

Let $\poly_{1}(\cdot),\poly_{2}(\cdot)$ be polynomials. Let $F_{\sk}:\{0,1\}^{\poly_{1}(\secpar)}\to\{0,1\}^{\poly_{2}(\secpar)}$ be a PRF, where $\sk\in\{0,1\}^{\secpar}$. We wish to interpret the output of $F_{\sk}$ as a real number in $$. We do so by letting$z$be the integer representation of the output and taking$\frac{z}{2^{\poly_{2}(\secpar)}}$. We consider$\poly_{2}$to be a large polynomial and ignore floating point errors. In the below algorithms, we allow$F_{\sk}$to take strings of varying length as input; we assume that$\poly_{1}(\cdot)$is chosen such that these strings are never too long, and if they are too short we pad them. In this section we assume that the token alphabet is binary as discussed in Section 4.1. We let done denote the binary encoding of the “done" token, and we write$\texttt{done}\in(x_{1},\ldots,x_{k})$if and only if the decoding of$(x_{1},\ldots,x_{k})$ in the original token alphabet includes done.

In this section we let $\mathcal{W}=(\mathsf{Setup},\mathsf{Wat},\mathsf{Detect})$ denote the watermarking scheme where $\mathsf{Wat}$ is Algorithm 3, $\mathsf{Detect}$ is Algorithm 4, and $\mathsf{Setup}(1^{\secpar})$ samples $\sk\leftarrow\{0,1\}^{\secpar}$. This scheme is outlined above in Section 4.2.

Let $\mathsf{Wat}^{\mathcal{O}}$ and $\mathsf{Detect}^{\mathcal{O}}$ be the same algorithms as $\mathsf{Wat}_{\sk}$ and $\mathsf{Detect}_{\sk}$, except that they use a random oracle $\mathcal{O}$ instead of $F_{\sk}$. Since both algorithms only make black-box use of $F_{\sk}$, these are well-defined. Denote this random oracle scheme by $\mathcal{W}^{\mathcal{O}}$ (which does not need a $\mathsf{Setup}$ algorithm). Undetectability, $b(L)$-(substring-)completeness, and soundness are defined identically for $\mathcal{W}^{\mathcal{O}}$, except we replace the probabilities over $\sk\leftarrow\mathsf{Setup}(1^{\secpar})$ with probabilities over $\mathcal{O}\leftarrow\{f:\{0,1\}^{\poly_{1}(\secpar)}\to\{0,1\}^{\poly_{2}(\secpar)}\}$. Note that in the definition of undetectability for $\mathcal{W}^{\mathcal{O}}$, the distinguisher will not be given access to the random oracle $\mathcal{O}$ (since the distinguisher for $\mathcal{W}$ is not given access to $F_{\sk}$).

The watermarking scheme $\mathcal{W}$ is undetectable/$b(L)$-(substring-)complete/sound if and only if $\mathcal{W}^{\mathcal{O}}$ is undetectable/$b(L)$-(substring-)complete/sound, assuming the security of the PRF used in $\mathcal{W}$.

The security of the PRF says that black-box access to $F_{\sk}$ (for random $\sk$) is indistinguishable from black-box access to a random $\mathcal{O}$, for any polynomial-time distinguisher. Observe that Algorithms 3 and 4 both only make black-box use of $F_{\sk}$. Therefore it is possible to efficiently test, using only black-box access to $F_{\sk}$, whether a given text/prompt/distinguisher violates soundness/$b(L)$-(substring-)completeness/undetectability. The security of the PRF then implies that the advantage of any given text/prompt/distinguisher is at most $\negl$ different between $\mathcal{W}$ and $\mathcal{W}^{\mathcal{O}}$. ∎

Let $E_{1},\dots,E_{n}$ be i.i.d. exponential random variables with rate 1, and let $\overline{E}:=\sum_{i=1}^{n}E_{i}$ be their sum. Then for any $\tau>0$,

$\Pr[\overline{E}\geq n+\sqrt{\tau n}]\leq\left(\frac{4}{5}\right)^{\sqrt{\tau}}$, and

$\Pr[\overline{E}\leq n-\sqrt{\tau n}]\leq e^{-\tau/2}$.

We start with part (a). By [Jan18, Theorem 5.1(i)],

If $\tau\geq n$, then since $1+z\leq 2^{z}$ for $z\geq 1$ we have

If $\tau\leq n$, then using $e^{z}\geq 1+z+z^{2}/2$ for $z\geq 0$ we have

where we have also used the fact that $(1+\frac{z}{n})^{n}$ is monotonically increasing in $n$.

We now turn to part (b). By [Jan18, Theorem 5.1(iii)],

If $\tau\geq n$, the probability becomes 0. If $\tau<n$, then taking the natural logarithm the above becomes

where for $0<z<1$ we have used the facts that $\frac{\ln(1-z)}{z}\leq\frac{-2}{2-z}$ and $\frac{2}{2-z}\geq 1+\frac{z}{2}$. ∎

$\mathcal{W}$ is a sound watermarking scheme.

Recall the definition of soundness in Definition 6. By Lemma 1 it suffices to show that for any text $x=x_{1},\dots,x_{L}$,

For $i,j\in[L]$, define $r^{(i)}$, $v_{j}^{(i)}$ as in Algorithm 4 and let $u_{j}^{(i)}:=\mathcal{O}(r^{(i)},j)$. Recall that $v_{j}^{(i)}=x_{j}\cdot u_{j}^{(i)}+(1-x_{j})\cdot(1-u_{j}^{(i)})$.

Since $u_{j}^{(i)}$ is independent from $x_{j}$, we have $v_{j}^{(i)}\sim U()$. Therefore, $E_{j}^{(i)}:=\ln(1/v_{j}^{(i)})$ are independent exponential random variables with rate parameter 1. By Lemma 2,

By a union bound over all $L$ possible values of $i$, the probability of Algorithm 4 returning $\true$ is at most $L\cdot(4/5)^{\lambda}=\negl$, completing the proof. ∎

$\mathcal{W}$ is a $\left(\frac{4}{\ln 2}\lambda\sqrt{L}\right)$-complete watermarking scheme.

Recall the definition of completeness in Definition 7. By Lemma 1 it suffices to show that for every prompt,

where $b(L)=\frac{4}{\ln 2}\lambda\sqrt{L}$. In fact, we will prove something stronger: For every fixed $x\in\mathcal{T}^{\star}$ and prompt such that $H_{e}(\mathsf{Model},\textsc{prompt},x)\geq\frac{4}{\ln 2}\lambda\sqrt{\absolutevalue{x}}$, if each bit $x_{i}$ of $x$ has empirical entropy $H_{e}^{i}(\mathsf{Model},\textsc{prompt},x)\leq\lambda$,

Inequality 2 says that for any possible fixed output $x$ that has high empirical entropy (which isn’t too concentrated on any particular bit), conditioning on $\mathsf{Wat}^{\mathcal{O}}$ outputting it, it is likely to be detected as watermarked. Note that the probability here is over the choice of outputs of $\mathcal{O}$ and not over $x$, which is fixed.

Observe that Inequality 2 is not falsifiable, so we cannot do the PRF switch (Lemma 1) with it. However, since each bit has at most a $2^{-\lambda}$ chance of having empirical entropy more than $\lambda$, Inequality 2 implies Inequality 1 via the law of total probability.

Denote by $s_{j}$ the random variable $\ln\frac{1}{v_{j}}$, conditioned on $\mathsf{Wat}^{\mathcal{O}}(\textsc{prompt})=x$, or equivalently, on the value of $x_{j}$. Recall that the variable $E=\ln\frac{1}{u}$ for $u\sim U()$ is exponentially distributed with rate $1$. In particular, if $x_{j}=1$ the variable $s_{j}$ is distributed the same as $E$ conditioned on $u\leq p_{j}(1)$, or equivalently on $E\geq\ln\frac{1}{p_{j}(1)}$. By the memorylessness property of exponential distributions, hence, $s_{j}$ is distributed as $\ln\frac{1}{p_{j}(1)}+E_{j}$, where $E_{j}$ is an exponentially distributed random variable with rate $1$. Symmetrically, if $x_{j}=0$ the variable $s_{j}$ is distributed as $\ln\frac{1}{p_{j}(0)}+E_{j}$. We conclude that

$\mathcal{W}$ is an undetectable watermarking scheme.

Recall Definition 9, which says that a watermark is undetectable if no efficient adversary can distinguish between query access to the watermarked model and the original one. Consider any fixed history of responses $x^{(1)},\dots,x^{(t-1)}$, and suppose that the adversary submits prompt as the next query. We will show that

Since the adversary can only make $\poly(\lambda)$ queries, it follows that the entire interaction with $\mathsf{Wat}^{\mathcal{O}}$ is statistically indistinguishable from interaction with $\overline{\mathsf{Model}}$. Finally, we will obtain the theorem by invoking Lemma 1.

For $k\in[t-1]$ and $i\in[L^{(k)}]$, we define

Note that $q^{(k)}_{i}(z)$ is the probability that $x^{(t)}_{i}=z$, given that $x^{(t)}_{j}=x^{(k)}_{j}$ for $j\in[i-1]$. We compute

4 Constructing Substring-Complete Watermarks

The detector presented in Section 4.3 receieves as an input the entire text output by $\mathsf{Wat}_{\sk}$. In this section we generalize the scheme into a substring-complete one, which is able to detect watermarks in any contiguous sequence of text with sufficiently high empirical entropy.

We use the same notation as in Section 4.3, except that now $\mathcal{W}$ refers to the scheme defined in Algorithms 5 and 6.

$\mathcal{W}$ is a sound watermarking scheme.

$\mathcal{W}$ is a $\left(\frac{8}{\ln 2}\lambda\sqrt{L}\right)$-substring-complete watermarking scheme.

We argue that any substring with empirical entropy at least $\frac{8}{\ln 2}\lambda\sqrt{L}$ must include the entirety of a pair of consecutive blocks $r^{(a)},r^{(a+1)}$. We then refer to the proof of Theorem 5 to argue that the bias planted in $r^{(a+1)}$ with the seed $r^{(a)}$ can be detected with overwhelming probability.

Recall the definition of completeness in Definition 7. By Lemma 1 it suffices to show that for every prompt,

where $b(L)=\frac{8}{\ln 2}\lambda\sqrt{L}$. We’ll show that for every fixed $x\in\mathcal{T}^{\star}$, $i,L\in[|x|]$, and prompt such that $H_{e}^{[i:i+L]}(\mathsf{Model},\textsc{prompt},x)\geq\frac{8}{\ln 2}\lambda\sqrt{L}$, if each bit $x_{j}$ of $x[i:i+L]$ has empirical entropy $H_{e}^{j}(\mathsf{Model},\textsc{prompt},x)\leq\lambda$,

Therefore, after $r^{(a)}$ has been fixed, there is sufficient entropy in the remainder of our substring $x[d+1:i+L]$ so that $r^{(a+1)}$ will be contained entirely within it. Since $r^{(a+1)}$ has empirical entropy at least $\frac{2}{\ln 2}\lambda\sqrt{k-d}$, we can now follow the analysis in the proof of Theorem 5 to conclude that this choice of $c,d,k$ in the detection algorithm results in an output of $\true$. ∎

$\mathcal{W}$ is an undetectable watermarking scheme.

Recall Definition 9, which says that a watermark is undetectable if no efficient adversary can distinguish between query access to the watermarked model and the original one. Let $\mathcal{R}_{W}$ and $\mathcal{R}_{M}$ be the distributions over the next block $r^{(t)}$ under $\mathsf{Wat}^{\mathcal{O}}$ and $\overline{\mathsf{Model}}$, respectively.

For any fixed history of blocks $r^{(1)},\dots,r^{(t-1)}$, if

then $\mathcal{R}_{W}=\mathcal{R}_{M}$ and

Inductively, any $\poly(\lambda)$-many blocks output by $\mathsf{Wat}^{\mathcal{O}}$ are at most $\negl$-far in statistical distance from outputs of $\overline{\mathsf{Model}}$. Since only $\poly(\lambda)$ blocks can appear in the experiment, the entire interaction with $\mathsf{Wat}^{\mathcal{O}}$ is statistically indistinguishable from interaction with $\overline{\mathsf{Model}}$. Finally, we will obtain the theorem by invoking Lemma 1.

Depending on whether $t$ is the first block in the response, we reason that $\mathcal{R}_{W}=\mathcal{R}_{M}$ differently:

If $r^{(t)}$ is the first block in the response, then $\mathcal{R}_{W}=\mathcal{R}_{M}$ because $\mathsf{Wat}^{\mathcal{O}}$ and $\overline{\mathsf{Model}}$ behave identically until after the first block is sampled.

If $r^{(t)}$ is not the first block in the response (i.e., $r^{(t-1)}$ is a part of the same response as $r^{(t)}$), then $\mathcal{R}_{W}=\mathcal{R}_{M}$ because $r^{(t-1)}\not\in\{r^{(1)},\dots,r^{(t-2)}\}$ and therefore $\mathsf{Wat}^{\mathcal{O}}$ uses fresh randomness to generate $r^{(t)}$. (Note that $r^{(t-1)}\neq\bot$, since the subsequent block $r^{(t)}$ is a part of the same response.)

In either case, once we know that $\mathcal{R}_{W}=\mathcal{R}_{M}$, Inequality 5 follows from the exact same argument as in the proof of Theorem 6. ∎

Necessity of Assumptions

In this section we show that the assumptions we use for our construction are necessary. Informally, the two main statements we prove in this section are:

Undetectability is possible only against a computationally bounded adversary. That is, using a polynomial number of queries and exponential running time we can detect any nontrivial watermarking scheme. This is proven in Lemma 4.

Undetectability is impossible if outputs of low empirical entropy are watermarked: For any $t$, if a non-negligible fraction of outputs with empirical entropy $\leq t$ are watermarked then we can detect the watermark using $\exp(t)$ queries and time. This is proven in Theorem 10.

To warm up, we first observe that there exist models that generate text with arbitrarily high entropy, and nevertheless in any undetectable watermark only a negligible fraction of outputs can be watermarked. Hence, the natural attempt to only consider the model’s entropy is insufficient.

For every $\lambda,b,\varepsilon>0$ there exists a prompt-independent model $\mathsf{Model}$ such that $H(\overline{\mathsf{Model}}(\emptyset))\geq b$, the maximum length of an output of $\overline{\mathsf{Model}}$ is $\frac{1}{\varepsilon}b$, and the following holds. If $\mathcal{W}$ is any undetectable and sound watermarking scheme for $\mathsf{Model}$, then

We define the output distribution of $\overline{\mathsf{Model}}$ as follows. With probability $1-\varepsilon$, $\overline{\mathsf{Model}}$ outputs done. Otherwise, it outputs a uniformly random binary string of length $\frac{1}{\varepsilon}b$. The entropy of $\overline{\mathsf{Model}}$ is larger than $\varepsilon\cdot\frac{1}{\varepsilon}b>b$.