Robust Distortion-free Watermarks for Language Models

Introduction

The ability of language models to mass produce human-like text creates an acute, renewed emphasis on the importance of provenance of generated content. For example, the website StackOverflow has banned users from posting answers using OpenAI’s ChatGPT model to mitigate the spread of misinformation on the platform . A reliable forensic tool for attributing text to a particular language model would empower individuals—such as platform moderators and teachers—to enact and enforce policies on language model usage; it would also better enable model providers to track the (mis)use of their models, e.g., to scrub synthetic text from the training data of future language models.

To achieve provenance, a watermark is a signal embedded within some generated content—in our case, text from a language model—that encodes the source of the content. We consider a setting where a (untrusted) third party user queries a language model (LM) by sending prompts to a trusted provider (Figure 1): the LM provider generates text from their language model with a watermark so that a detector may later identify the source of the text if the user publishes it. The ideal watermark should satisfy at least the following three desiderata:

distortion-free—the watermark should preserve the original text distribution;

agnostic—it should be detectable without the language model and/or prompt;

robust—it should withstand perturbations of the watermarked text.

Existing watermarks either distort the model’s sampling distribution, thus altering the API functionality , or are not robust to editing or cropping the text . Meanwhile, classical steganographic techniques for covertly encoding messages within samples of text from a language model are neither agnostic nor robust . We develop the first watermarks for attributing text to a language model that achieve all three desiderata.

Our methodology consists of two components, which the LM provider and detector respectively use to execute the two steps of the protocol in Figure 1 under their control: a $\mathtt{generate}$ method that deterministically maps a sequence $\xi$ of random numbers encoded by a (secret) watermark key Whether the watermark key is secret or not (e.g., if the LM provider publishes the key to allow anyone to detect watermarked text) is an implementation choice that does not affect the main parts of our analysis. —which we call the watermark key sequence—to a sample from the language model, and a $\mathtt{detect}$ method that aligns a putative watermarked text with the watermark key sequence using the shared key. Informally, our watermarks are distortion-free in the sense that—marginalizing over the watermark key sequence—each call to $\mathtt{generate}$ is equal in distribution to a sample from the original language model, i.e., $P(\textbf{text})=\int_{\xi}\mathbf{1}\!\left\{\textbf{text}=\mathtt{generate}(\xi,\textbf{prompt})\right\}d\nu(\xi)$ is equal to the original language model’s sampling distribution.

The challenge of detecting watermarked text is that the detector cannot simply recompute $\mathtt{generate}$ and compare its output against the text since they do not necessarily know the prompt which produced the text: in practice, users often crop the prompt when publishing text from a language model. Our watermarks are agnostic in the sense that they are easily detectable with a suitable model-agnostic and prompt-agnostic test statistic $\phi$ such that $\phi(\mathtt{generate}(\xi,\textbf{prompt}),\xi)\ll\phi(\textbf{text},\xi)$ for any text that is independent of the watermark key sequence. The idea here is that the detector may use $\phi$ within $\mathtt{detect}$ to compute a $p$-value with respect to the null hypothesis that the text is independent of the watermark key sequence, i.e., that the text is not watermarked.

To ensure $\mathtt{detect}$ is robust to edits of the watermarked text, the core idea underpinning the design of each test statistic $\phi$ is to leverage techniques for robust sequence alignment to align a putative watermarked text with the watermark key sequence; we quantify the quality of the alignment using an “alignment cost” specific to each watermark. The sequence alignment procedure ensures the watermark is detectable from even a small, corrupted block of watermarked text planted within some other larger text. Of course, a sufficiently motivated and/or sophisticated user can still evade detection by simply rewriting the text from scratch themselves (or, using another language model to generate the text); the point of a robust watermark is simply that the amount of effort and/or resources a user requires to produce text that evades watermark detection should be commensurate to what they would have expended had they not had access to the watermarked language model in the first place.

Whereas $\mathtt{generate}$ is a deterministic function, if our watermark produced the same text every time for each prompt it would not be very useful. We resolve this limitation by designing a wrapper around $\mathtt{generate}$ that calls $\mathtt{generate}$ using a randomly chosen subsequence of $\xi$ instead of generating tokens from the same starting point each time. For the same reasons that $\mathtt{detect}$ is robust to editing and cropping watermarked text, calling $\mathtt{generate}$ in this fashion does not affect watermark detectability. In practice, the statistical power of our watermarks improves exponentially with respect to the length of the putative watermarked text and diminishes only linearly with the length of the random number sequence; thus, by increasing the length of the random number sequence, we can reduce the probability of reusing the same random subsequence while still ensuring our watermark has good statistical power (i.e., that it yields low $p$-values for watermarked text).

To remark briefly on the work most closely related to ours, we contrast the distortion-free property of our watermarks with the hashing-based watermarks of Kirchenbauer et al. and Aaronson that bias the distribution of watermarked text towards certain $k$-grams by hashing a sliding window of the previous $k-1$ tokens to determine the next token pseudorandomly. We give examples of prompts (e.g., “Give me a list of 20 movies.”) for which the bias due to hashing is clearly noticeable in our experiments. Christ et al. propose a variation of hashing in which the window size changes based on the entropy of the generated tokens to avoid hash collisions with high probability. Their motivation is similar to ours in that they focus on preserving the original text distribution; however, like Kirchenbauer et al. and Aaronson , using larger window sizes hurts robustness as an adversary can break the watermark by replacing a single token in each window. Our watermark is not only distortion-free but also robust to substantial corruption of the text, which is crucial in practice. We defer a more thorough discussion of related work to the next section (Section 1.1).

We describe the details of our methodology in Section 2, wherein we give two instantiations of watermarks—using inverse transform sampling and exponential minimum sampling—and provide analyses of their statistical power. We experimentally validate the power and robustness of our watermarks using the OPT-1.3B, LLaMA-7B and Alpaca-7B language models in Section 3. Across all models, we find the second instantiation using exponential minimum sampling to be the most powerful. For both the OPT-1.3B and LLaMA-7B models, using this watermark we can reliably detect watermarked text ($p\leq 0.01$) from $35$ tokens even after corrupting between $40$-$50$% of the tokens via random edits (i.e., substitutions, insertions or deletions); the watermark also remains detectable from $50$ tokens even after paraphrasing the text by translating to French/Russian and back. For the Alpaca-7B model, we conduct a case study on the feasibility of watermarking responses to typical user instructions. Due to the lower entropy of the responses, detection is more difficult: around $25\%$ of the responses—whose median length is around $100$ tokens—are detectable with $p\leq 0.01$, and the watermark is also less robust to paraphrasing. We release code for implementing the watermark and reproducing the experiments in this paper, as well as additional supplementary material including an in-browser demo of the watermark detectorFor assets and supplemental material, see: https://github.com/jthickstun/watermark..

Text watermarking is a special case of linguistic steganography, in that the goal is to convey a hidden message—the watermark—within a passage of text. Existing approaches to linguistic steganography fall under two broad categories: edit-based methods that modify a pre-existing text, and generative methods that construct a distribution over cover text . Crucially, in contrast to steganography, the literature on digital watermarking has historically foregrounded robustness to corruption as a key attribute of a good watermark . In this light, a text watermark should be able to withstand some perturbations of the text, thus precluding the direct application of many existing techniques for linguistic steganography .

Older work on text watermarking considers editing a pre-existing text to include a watermark ; for a survey of edit-based watermarks, see Kamaruddin et al. . In contrast, we are interested in generating watermarked text while preserving the distribution over the text from a language model. Work on generative watermarking is nascent, underwritten by recent advances in open-ended text generation . Pioneering work by Venugopal et al. proposed a generative watermark for the output of a machine translation system, biasing the system towards translations with particular features that can later be detected using a hypothesis test.

Also concurrent to our work, Christ et al. propose watermarking blocks of text from a language model by hashing each block to seed a sampler for the next block. Christ et al. vary their block sizes—which are analogous to the hyperparameter $k$ of Kirchenbauer et al. and Aaronson —as a function of the empirical entropy of the constituent tokens to avoid using the same seed twice with high probability. Their work is similar to ours in that they preserve the original text distribution; however, the resulting watermark is not robust since in order to mitigate the distortion induced by hashing the block sizes must be sufficiently large to avoid hash collisions with high probability over all blocks and—similar to Kirchenbauer et al. and Aaronson —replacing any token in the previous block breaks the watermark in the next block. Whereas Christ et al. —who do not run experiments—choose their block sizes to be sufficiently large to minimize distortion, Kirchenbauer et al. and Aaronson recommend choosing $k$ to be a small constant in practice, which ensures a moderate amount of robustness by introducing some distortion.

An alternative approach for detecting synthetic text is to learn a classifier between synthetic and human text . A key advantage of such methods over watermarking is that they do not require coordination with the original producer of the text (i.e., the LM provider); however, their effectiveness is distribution dependent and they do not provide a priori (distribution-free) guarantees on the significance level of detection (i.e., Type I errors).

Finally, we note that our setting is different from the literature on planting watermarks in the training data of machine learning models, e.g., to infer the model’s training set or otherwise influence the model’s output . Such watermarks are not distortion-free by design, since the point is to plant some learnable signal in the training data that influences the behavior of models which train on the watermarked data.

Methodology and theoretical analysis

Let $\mathcal{V}$ be a discrete set, i.e., the vocabulary, and let $p\in\mathcal{V}^{*}\to\Delta(\mathcal{V})$ be an autoregressive language model which maps a string of arbitrary length to a distribution over the vocabulary, with $p(\cdot\mid x)$ denoting the distribution of the next token given the prefix $x\in\mathcal{V}^{*}$. Let $\Xi$ denote the space in which lie the elements of the watermark key sequence. Recall the main protocol (Figure 1) which defines our problem setting:

The LM provider shares a random watermark key sequence $\xi\in\Xi^{*}$ with the detector;

The user sends a prompt $x\in\mathcal{V}^{*}$ to the LM provider;

The LM provider generates text $Y\in\mathcal{V}^{*}$ by $Y=\mathtt{generate}(x,\xi)$;

The user publishes text $\widetilde{Y}\in\mathcal{V}^{*}$, which may be either (i) (an edited version of) the generated text $Y$ or (ii) text independent of $Y$ (e.g., text that they wrote themselves);

The detector determines if $\widetilde{Y}$ is watermarked—i.e., if $\widetilde{Y}$ depends on the watermark key sequence—by computing a $p$-value $\widehat{p}=\mathtt{detect}(\widetilde{Y},\xi)$ with respect to the null hypothesis that $\widetilde{Y}$ is independent of $\xi$ (i.e., not watermarked).

We relate Definition 1 to our informal definition of distortion-free text in the introduction through the following simple lemma. Assuming the conditions of the lemma are met, the only material difference between an LM provider using $\mathtt{generate}$ versus sampling directly from the language model is that the sequence $\xi$ is an input to the method rather than resampled i.i.d. within the method for each call. We treat the language model $p$, the decoder $\Gamma$, and generation length $m$ as internal parameters of the $\mathtt{generate}$ method.

As $n\geq m$, we have $\{\xi_{i}\}_{i=1}^{m}\overset{\text{i.i.d.}}{\sim}\nu$. The claim then follows immediately from applying Definition 1 to Line 1 of $\mathtt{generate}$ for $i\in[m]$. ∎

This alignment-based detection strategy makes the watermark robust, since even if the user crops or otherwise corrupts $Y$, a single block of preserved watermarked text within some larger body of unwatermarked text will suffice to trigger a low $p$-value from $\mathtt{detect}$. The actual form of the alignment cost will be specific to each watermark—in particular, it will depend on the nature of the decoder $\Gamma$ in $\mathtt{generate}$. Our most robust watermarks incorporate a soft notion of edit distance (i.e., Levenshtein distance) into the computation of the alignment cost via dynamic programming, with runtime scaling quadratically in the block size. Thus, letting $m$ be the length of the input text $y$, $n$ be the length of the watermark key sequence $\xi$, and $k$ be the block size, the cost of computing the test statistic is $O(mnk^{2})$.

To illustrate how the decoder and the alignment cost fit together, we give a simple example for the toy setting of a binary vocabulary.

Example 1 (): Consider a binary vocabulary $\mathcal{V}=\{0,1\}$. To generate $Y\in\{0,1\}^{*}$ from the model, the LM provider shares $\{\xi_{i}\}_{i=1}^{n}\overset{\text{i.i.d.}}{\sim}\textup{Unif}()$ with the detector and let $Y_{i}=0$ if $\xi_{i}\leq p(0\mid Y_{:i-1})$ and $Y_{i}=1$ otherwise. In particular, defining the decoder $\Gamma$ by

In the above example, the LM provider generates the same text each time from the watermark key sequence, which is not ideal in practice. One solution for avoiding reusing elements of the watermark key sequence across queries is to make $\mathtt{generate}$ stateful, thus enabling the LM provider to generate a total of $\lfloor n/m\rfloor$ independent watermarked text samples of $m$ tokens each from the language model. Instead, to avoid persisting state, we provide a randomized wrapper $\mathtt{shift\textup{-}generate}$ (Algorithm 4) around $\mathtt{generate}$ and modify the watermarking protocol from the start of the section to allow the LM provider to call the $\mathtt{shift\textup{-}generate}$ instead of $\mathtt{generate}$ in the second step of the protocol. The wrapper $\mathtt{shift\textup{-}generate}$ randomly shifts the watermark key sequence before passing the shifted sequence to $\mathtt{generate}$. Shifting the watermark key sequence does not affect the value of the test statistic in $\mathtt{detect}$, since to compute the test statistic the detector anyways searches over all subsequences of the watermark key sequence to find the best match for each block of text. There are $n$ possible shifts, each of which may produce a distinct text; while in principle these $n$ texts will correlate with each other due to sharing elements of the watermark key sequence, in practice we find the effects of these correlations are not noticeable. The so-called birthday paradox implies the LM provider can typically expect to call $\mathtt{shift\textup{-}generate}$ on the order of ${n}^{1/2}$ times, each time generating a different text, before reusing the same offset twice.

2 Terminology: watermark strategies and watermark potential

Henceforth, we use the term watermarking strategy to refer to a concrete instantiation of the $\mathtt{shift\textup{-}generate}$, $\mathtt{generate}$ and $\mathtt{detect}$ methods by specifying the internal parameters of both algorithms (i.e., the decoder $\Gamma$, the test statistic $\phi$ and the watermark key sequence distribution $\nu$). We give concrete watermarking strategies in the following sections (Sections 2.3 and 2.4). For each watermarking strategy, we show two main results: we prove the decoder is distortion-free and also obtain high probability upper bounds on the $p$-values of watermarked text—as a function of the length of the text and the watermark key sequence. We emphasize that only the former result (i.e., that the decoder is distortion-free) is critical to the validity of our main claims; we intend the latter collection of results to provide intuition for when we would expect the detector to have sufficient power and to anticipate the forthcoming experimental results in Section 3. The strength of the $p$-value upper bounds will depend on the observed token probabilities of (watermarked) text, through a quantity which we evocatively term the watermark potential.

Observe the watermark potential of text from a deterministic language model is always zero, whereas for a high-entropy model it will approach one. The degree to which it is possible for the detector to reliably distinguish watermarked text from unwatermarked text necessarily depends on the watermark potential of the LM provider’s language model. For example, if the language model is deterministic, then any distortion-free watermark will necessarily have zero statistical power. We formalize this intuition by establishing the following general lower bound on the detection accuracy of any watermarking strategy as a function of the watermark potential of the original language model. In particular, we lower bound the error of any classifier $h:\mathcal{V}^{*}\times\Xi^{*}\to\{-1,+1\}$ that tries to distinguish watermarked (positive label) versus nonwatermarked text (negative label) given some watermark key $\xi$ (we make no assumption on the distribution of $\xi$ except that it is independent of unwatermarked text by definition). We defer the proof of Lemma 2.2 to Appendix A.

Let $Y_{i}^{\prime}\sim p(\cdot\mid Y_{:i-1}^{\prime})$ for $i\in[m]$. Let $Y\stackrel{{\scriptstyle d}}{{=}}Y^{\prime}$ and let $\xi\in\Xi^{*}$ be a random variable that is independent of $Y^{\prime}$. Let $h:\mathcal{V}^{*}\times\Xi^{*}\to\{-1,+1\}$ be a classifier. Let $c>0$ and define the set $\mathcal{V}_{c}\subset\mathcal{V}^{m}$ by

Lemma 2.2 implies it is impossible to test between any watermarked and non-watermarked text (i.e., between $Y$ versus $Y^{\prime}$) that are equal in distribution (i.e., distortion-free) if the text typically has low watermark potential, irrespective of the design of the watermark key; in particular, the sum of the Type I and II error rates of $h$ will be close to one if the watermark potential is close to zero. The theorem is not tight: depending on the language model, its result may be vacuous for small values of $c$ (e.g., the constants which appear in our upper bounds) since only texts whose token likelihoods all exceed $\exp(-c/2)$ contribute to the lower bound. Also our upper bounds scale inverse exponentially with the square of the watermark potential, which will always be smaller than the watermark potential itself since the watermark potential is bounded between zero and one.

The point of the forthcoming $p$-value upper bounds for the watermarking strategies in Sections 2.3 and 2.4 is to establish the existence of test statistics for each watermark such that the statistical power of the watermark improves exponentially with the length of the text and decays at most linearly with the length of the watermark key sequence. The test statistics we use to prove these upper bounds differ slightly from those we employ in our experiments: in the former case, we prioritize the simplicity of stating the bounds in terms of watermark potential, whereas in the latter case, we prioritize empirical performance.

3 Watermarking via inverse transform sampling

Inverse transform sampling is a general technique for sampling from a univariate distribution by taking the pushforward of a uniform random variable through its inverse cumulative distribution function (CDF). Crucially, the technique is valid irrespective of the ordering of the CDF, a property which we presently leverage to construct a watermarking strategy in which $\mathtt{generate}$ is distortion-free and also $\mathtt{detect}$ is agnostic. In particular, we implement $\mathtt{generate}$ with a decoder that maps a sequence of uniform random variables and permutations to tokens using inverse transform sampling. To detect watermarked text, the detector correlates the sequence of permuted indices of the tokens in the text with the sequence of uniform random variables to detect watermarked text. Meanwhile, for any nonwatermarked text, the sequence of permuted token indices will be i.i.d. uniform irrespective of the text itself and thus not correlate with the sequence of uniform random variables.

Formally, with $\Pi$ as the space of permutations over the vocabulary $[N]$, for $\xi=(u,\pi)\in\times\Pi=:\Xi$ and any distribution $\mu\in\Delta([N])$, define the decoder by

i.e., $\Gamma(\xi,\mu)$ is the token with the smallest index in the permutation $\pi$ such that CDF of $\mu$ with respect to $\pi$ is at least $u$. Generalizing the intuition from Example 3, we show this decoder is distortion-free in the following theorem.

Define $\Gamma$ by equation (1). Let $\pi\in\Pi$ be arbitrary and let $U\sim\textup{Unif}()$, with $\xi:=(U,\pi)$. Then $\Gamma$ is distortion-free with respect to $\xi$.

As the width of this interval is exactly $\mu(y)$, the result follows immediately. ∎

i.e., the negative covariance (each $U_{i}$ and $\eta(\pi_{i}(Y_{i}))$ both have expectation $1/2$).

We exactly characterize in Lemma 2.3 the difference in the expected value of our alignment cost on some text assuming the text is watermarked (i.e., generated using the same key as the detector) versus not watermarked in terms of the watermark potential of the text (Definition 2). To state the result, we define the constant $C_{0}:=\textup{Var}(\eta(\textup{Unif}([N])))$, where we abuse notation slightly to temporarily treat $\eta$ as a pushforward map over distributions. Note that $C_{0}=\textup{Var}(\textup{Unif}())+o_{N}(1)=1/12+o_{N}(1)$. We defer the proof of Lemma 2.3 to Appendix B.

Summing the result of Lemma 2.3 over $i\in[m]$ implies for any $j\in[n]$ that

Thus, we can upper bound the $p$-value output by $\mathtt{detect}$ in Lemma 2.4 using a standard concentration argument and taking a union bound over $j\in[n]$. We defer the proof of Lemma 2.4 to Appendix B. In fact, we actually prove a more general result for $k\leq m$ wherein we allow $\widetilde{Y}$ to be a subsequence of $Y$ which the user may choose adaptively. We defer this more general result to Appendix B as it is more cumbersome to state.

Lemma 2.4 implies that with high probability the value of the test statistic on watermarked text with the correct key will be lower than with a resampled key. In particular, ignoring discretization errors due to the finite number of resamples $T$ in $\mathtt{detect}$, the lemma implies watermarked samples with watermark potential bounded away from zero (i.e., if the language model is not effectively deterministic) will have exponentially small expected $p$-values with respect to the length $m$ of the text. The bound grows only linearly with the length $n$ of the random number sequence, implying for moderately large $m$ (e.g., $m=50$) an LM provider can generate plenty of distortion-free watermarked text (i.e., $n=2^{\Omega(m)}$ total tokens) while still enabling detection of the watermark from snippets of $m$ tokens (e.g., $50$ tokens typically amount to a couple sentences of text). Of course, recall the computational complexity of detection scales linearly with $n$, which in practice may be a more relevant limitation than the statistical power of the watermark. Note that both $\mathtt{detect}$ and the test statistic (Algorithm 3) are easily parallizeable.

We show in Lemma 2.5 an analogous result to Lemma 2.4 holds even if an adversary corrupts the original watermarked text by substituting tokens. To state the lemma, we introduce a quantity $\widetilde{\alpha}$ which depends on both the corrupted and original watermarked text and accounts for the decrease in the expected value of the test statistic (which recall for the original text is equal up to a numerical constant to the watermark potential of the text) due to token substitutions. We defer the proof of Lemma 2.5 to Appendix B.

Lemma 2.5 implies that even if an adversary replaces the vast majority of tokens in a watermarked text, detection with low $p$-values will still be possible so long as the remaining tokens have watermark potential bounded away from zero. In particular, the permuted indices of the original tokens will still positively correlate with the corresponding uniform random variables from the watermark key sequence, while those of the substituted tokens will exhibit a small negative correlation scaling as $O(1/N)$.

To handle insertions and deletions, we can robustify our test statistic by incorporating a soft notion of edit distance into our original alignment cost. The parameter $\gamma$ in Definition 3 assigns a cost to each insertion and deletion operation when aligning the tokens $y$ with the sequence $\xi$, while the base alignment cost $d_{0}$ defines the quality of the alignment via a cost function over substitutions. In practice, we drop the minimizations over $y^{\prime}\in\mathcal{V}$ and $\xi^{\prime}\in\Xi$ in the second and third cases respectively of the definition; we include them here to make our subsequent theoretical analysis cleaner.

with $d_{\gamma}(y,(u,\pi)):=\gamma\cdot\mathtt{len}(y)$ if $\xi$ is empty and vice versa (as base cases). For $y\in\mathcal{V}^{*}$ (resp., $\xi\in\Xi^{*}$), we let $y_{\mathtt{len}(y)+1:}$ (resp., $\xi_{\mathtt{len}(\xi)+1}$) denote the empty string/sequence.

Redefining the test statistic $\phi$ using $d_{\gamma}$ as the alignment cost—using $d_{0}$ from equation (2)—ensures $\mathtt{detect}$ is robust not only to substituting tokens, but also inserting and deleting tokens from watermarked text, as we show in Lemma 2.6. We defer the proof of Lemma 2.6 to Appendix B. To state the lemma, we first recursively define a notion of edit distance between two strings. The definition is equivalent to the minimum number of insertion and/or deletion operations needed to transform one string into the other (see Lemma B.2).

(edit distance) For $y,\widetilde{y}\in\mathcal{V}^{*}$, define the edit distance by

with $d_{\textup{edit}}(y,\widetilde{y})=\mathtt{len}(y)$ if $\widetilde{y}$ is empty and vice versa.

We prove the result by showing there must exist a length $k$ substring of the corrupted text $\widetilde{Y}$ within edit distance $k\varepsilon$ of a substring of $Y$ that the detector will be able to distinguish as watermarked. For fixed $k$, the set of strings within edit distance $\varepsilon k$ of an original block watermarked text blows up combinatorially with $\varepsilon$. To ensure we can detect the watermark, the result implies we must set $\gamma=\Omega(1/\varepsilon)$, which means our bound on the expected $p$-value is vacuous as soon as $\varepsilon=\Omega(1/\log k)$. Admittedly, our analysis is not tight; for example, as a preview of the experimental results to come, in practice we find smaller values of $\gamma$ (i.e., $\gamma<1$) to perform significantly better. However, one takeaway from the result is that using a block size $k<m$, where here $m$ is the length of the input text, for detection can be an effective strategy when the user has substantially corrupted the text. The assumption that $k$ divides evenly into $m$ is an artifact of our analysis and not important in practice.

3.2 What we run in practice

In practice, to reduce overhead in both $\mathtt{generate}$ and $\mathtt{detect}$, we use a single random permutation In principle, with a single random permutation the permuted token indices of both watermarked and nonwatermarked text are no longer conditionally independent of each other, and so the results of Lemmas 2.4, 2.5 and 2.6 no longer apply. However, in practice we observe no degradation in statistical power. Also, irrespective of the lemmas, the $p$-values from $\mathtt{detect}$ are still valid by construction. instead of a full sequence, i.e., we let $\pi_{i}=\pi$ for all $i\in[n]$ for $\pi\sim\textup{Unif}(\pi)$. Recall Theorem 1 makes no assumption about the distribution of the permutations; thus, the watermark is still distortion-free. Also, for the test statistic, we find using

as the alignment cost performs better empirically than the alignment cost in equation (2). To reiterate, the output of $\mathtt{detect}$ is a valid $p$-value irrespective of the test statistic we use.

Henceforth, we refer to this version of the watermarking strategy as $\mathtt{ITS}$, and we refer to the corresponding Levenshtein version as $\mathtt{ITS}$-$\mathtt{edit}$, wherein we define the base alignment cost $d_{0}$ by equation (3) and use the following simplified notion of Levenshtein cost:

with $d_{\gamma}(y,(u,\pi)):=\gamma\cdot\mathtt{len}(y)$ if $\xi$ is empty and vice versa (as base cases). For $y\in\mathcal{V}^{*}$ (resp., $\xi\in\Xi^{*}$), we let $y_{\mathtt{len}(y)+1:}$ (resp., $\xi_{\mathtt{len}(\xi)+1}$) denote the empty string/sequence.

In summary, for $\mathtt{ITS}$ we use the decoder from equation (1), the test statistic from Algorithm 3 with the alignment cost from equation (3), and the watermark key distribution as the uniform distribution over $^{n}\times\Pi$, where recall $n$ is the length of the watermark key sequence. Meanwhile, $\mathtt{ITS}$-$\mathtt{edit}$ differs from $\mathtt{ITS}$ only in that we define the test statistic using the Levenshtein cost from Definition 5 with the base cost again from equation (3).

4 Watermarking via exponential minimum sampling

Aaronson proposes mapping variables in $^{N}$ to tokens in the vocabulary $[N]$ using exponential minimum sampling to generate watermarked text. Whereas Aaronson proposes the use of distortion-inducing hashes much like Kirchenbauer et al. , we use exponential minimum sampling to implement the decoder in $\mathtt{generate}$, which (after defining a suitable corresponding test statistic) enables an alternative distortion-free and robust watermarking strategy to inverse transform sampling. In particular, for $\xi\in^{N}=:\Xi$ and $\mu\in\Delta([N])$, define the decoder by

We show this decoder is distortion-free in Theorem 2, whose proof we defer to Appendix C.

Define the decoder $\Gamma$ by equation (4) and let $\xi\sim\textup{Unif}(^{N})$. Then $\Gamma$ is distortion-free with respect to $\xi$.

For the sake of analysis, we define the alignment cost as a slight variation of the proposal of Aaronson (see Section 2.4.2) by

again defining the test statistic $\phi$ by Algorithm 3. Similar to Lemma 2.3 for ITS, we exactly characterize the difference in the expected values of the alignment cost on watermarked versus non-watermarked text in terms of the watermark potential of the text. We defer the proof of Lemma 2.7 to Appendix C.

Summing the result of Lemma 2.7 over $i\in[m]$ implies for any $j\in[n]$ that

Thus, defining the test statistic $\phi$ by Algorithm 3 with respect to the alignment cost $d$ from Eqn (5), we can again upper bound the $p$-value output by $\mathtt{detect}$ in Lemma 2.8 using a standard concentration argument and taking a union bound over $j\in[n]$. We defer the proof of Lemma 2.8 to Appendix C. Once again, we actually prove a more general result that allows $\widetilde{Y}$ to be any length $k$ subsequence of $Y$.

Showing high probability $p$-value upper bounds for corruptions of watermarked text that hold almost surely given the corrupted text—i.e., analogues of Lemmas 2.5 and 2.6—is more difficult, primarily due to the fact that the summands in the alignment metric from equation (5) are no longer bounded and thus bounding the influence of each substitution and/or insertion operation on the test statistic requires more careful analysis. Of course, we could in principle tweak the alignment metric by truncating the summands in order to prove the analogous results; however, as the main intuitions would carry over from Lemmas 2.5 and 2.6 and the results are not critical to the main thrust of the paper, we do not carry this plan out.

4.2 What we run in practice

As in the case of ITS, in practice we find using a slight variation of the alignment cost in equation (5) performs better. Namely, following the prescription of Aaronson , we modify the previous alignment cost to instead be

Henceforth, we refer to this version of the watermarking strategy as $\mathtt{EXP}$, and we refer to the corresponding Levenshtein version wherein we define the base alignment cost $d_{0}$ by equation (6) as $\mathtt{EXP}$-$\mathtt{edit}$.

In summary, for $\mathtt{EXP}$ we use the decoder from equation (4), the test statistic from Algorithm 3 with the alignment cost from equation (6), and the watermark key distribution as the uniform distribution over $\Xi^{n}$, where recall $n$ is the length of the watermark key sequence and $\Xi=^{N}$. Meanwhile, $\mathtt{EXP}$-$\mathtt{edit}$ differs from $\mathtt{EXP}$ only in that we define the test statistic using the Levenshtein cost from Definition 5 with the base cost again from equation (6).

Experimental results

We empirically validate the statistical power of our watermarking strategies (i.e., $\mathtt{ITS}$, $\mathtt{ITS}$-$\mathtt{edit}$, $\mathtt{EXP}$, and $\mathtt{EXP}$-$\mathtt{edit}$) via experiments with the OPT-1.3B and LLaMA-7B models. We will also at times collectively refer to $\mathtt{ITS}$ and $\mathtt{ITS}$-$\mathtt{edit}$ as the ITS watermarks and/or strategies and $\mathtt{EXP}$ and $\mathtt{EXP}$-$\mathtt{edit}$ as the EXP watermarks and/or strategies. We run experiments using $\mathtt{generate}$ rather than $\mathtt{shift\textup{-}generate}$, mainly for the sake of reproducibility; recall however that this choice has no impact on the $p$-values we report. We test for all watermarks using a block size $k$ (in Algorithm 3) equal to the length $m$ of the text. Following the methodology of Kirchenbauer et al. , we generate watermarked text continuations of prompts sampled from the news-like subset of the C4 dataset . We vary the generation length $m$ (Experiment 1) and the random number sequence length $n$ (Experiment 2), and we report median $p$-values of watermarked text over $500$ samples. The median $p$-value corresponds to the significance level (i.e., Type I error rate) at which the power of our watermark detector is at least $0.5$.

We also evaluate robustness to four kinds of paraphrasing attacks: randomly substituting a fraction of the generated tokens with tokens chosen uniformly at random from the vocabulary (Experiment 3); randomly inserting a fraction of tokens among the generated tokens (Experiment 4); randomly deleting a fraction of the generated tokens (Experiment 5); using another language model to translate the text from English to French and back (Experiment 6). The first three attacks allow us to systematically vary the level of corruption, while the last attack is an example of an attack we might encounter in the wild. We defer the details of the translation procedures to Appendix D.2.

Finally, using the Alpaca-7B model and evaluation dataset , we conduct a case-study on the feasibility of watermarking the responses of a performant instruction-tuned language model to user queries. We also show for certain kinds of instructions that hashing-based watermarks produce noticeably worse responses than our distortion-free watermarks, thus underlining the importance of the distortion-free property in practice.

In all our experiments—except for Experiment 2, where the control variable $n$ is a hyperparameter that is unique to our watermarks—we also replicate the watermark of Kirchenbauer et al. as a baseline, setting the greenlist fraction $\gamma=0.25$ and varying the logit bias $\delta\in\{1.0,2.0\}$. We respectively refer to these versions of their watermark as $\mathtt{KGW}$-$\mathtt{1.0}$ and $\mathtt{KGW}$-$\mathtt{2.0}$ after the first three authors’ last names. We emphasize their watermark is not directly comparable to our watermarks as it is not distortion-free (e.g., Kirchenbauer et al. report that even the weakest version we employ with $\delta=1.0$ and $\gamma=0.25$ typically increases perplexity by 5–10%).

In their work, Kirchenbauer et al. report approximate $p$-values, which they obtain from computing the $z$-score of a certain test statistic. To ensure a fair comparison, we use $\mathtt{detect}$ (with $T=5000$) to report $p$-values for all watermarks; This setting of $T$ means we never report $p$-values less than $1/5000$ (i.e., $0.0002$) in any of our experiments. in the case of $\mathtt{KGW}$-$\mathtt{1.0}$ and $\mathtt{KGW}$-$\mathtt{2.0}$, we run $\mathtt{detect}$ using the original inexact $p$-values they report as the test statistic. We report error bars for the median $p$-value based on a bootstrapped estimate of the standard deviation using $1000$ resamples.

Instead of recomputing the test statistic $T$ times for each prompt—as we originally prescribe in $\mathtt{detect}$—to save computation we simply sample $T$ prompts and compute the test statistic once for each ground-truth length $m$ completion; we then use the empirical distribution of these test statistics as the reference distribution within $\mathtt{detect}$, which gives a proper $p$-value with respect to the null hypothesis that the text is an original completion from the dataset. For reference, we include the full pseudocode for this modified version of $\mathtt{detect}$ in Appendix D.3, and we also plot the full distributions of $p$-values for nonwatermarked generations (i.e., regular samples from the language models) to verify they are indeed roughly uniform over the interval $$.

We defer further details regarding our experimental protocol to Appendix D.

We vary the length $m$ of watermarked text in Figure 2, fixing the watermark key length $n=256$ for each of our watermarks and setting $\gamma=0.4$ for $\mathtt{ITS}$-$\mathtt{edit}$ and $\gamma=0.0$ for $\mathtt{EXP}$-$\mathtt{edit}$ (see Appendix D.4 for the details of tuning $\gamma$). Our ITS watermarks slightly outperform $\mathtt{KGW}$-$\mathtt{1.0}$ while our EXP watermarks slightly outperform $\mathtt{KGW}$-$\mathtt{2.0}$, despite the fact that $\mathtt{KGW}$-$\mathtt{1.0}$ and $\mathtt{KGW}$-$\mathtt{2.0}$ both distort the text distribution. The EXP watermarks are notably more powerful than the ITS watermarks, requiring roughly two to three times fewer tokens to achieve a comparably low median $p$-value. One conceivable advantage of the ITS watermarks over the EXP watermarks is that they have comparatively less overhead: the watermark key for $\mathtt{EXP}$ and $\mathtt{EXP}$-$\mathtt{edit}$ is a sequence of $n$ vectors in $^{N}$, where recall $N$ is the size of the vocabulary, while for $\mathtt{ITS}$ and $\mathtt{ITS}$-$\mathtt{edit}$ it is simply a sequence of $n$ numbers in $$. All watermarking strategies perform worse on LLaMA-7B than OPT-1.3B, due to the fact that LLaMA-7B typically produces lower entropy text than OPT-1.3B. Due to the discrete nature of the test statistic of Kirchenbauer et al. , i.e., the number of tokens in the text belonging to a “greenlist” versus a “redlist”, the median$p$-values for the$\mathtt{KGW}$-$\mathtt{1.0}$and$\mathtt{KGW}$-$\mathtt{2.0}$watermarks are occasionally unstable, particularly for small values of$m$.

We vary the length $n$ of the watermark key sequence $\xi$ in Figures 3 and 4 for different lengths $m$ of watermarked text from the ITS and EXP watermarks respectively. Recall $n$ corresponds to the total number of tokens we can generate while maintaining our distortion-free guarantee. As our theory predicts, the $p$-values of watermarked text grow linearly with $n$. The rate of growth is fairly mild and decreases rapidly with $m$; even for $n=4096$, which is larger than the maximum generation length of both the OPT-1.3B and LLaMA-7B models, slightly increasing the number of tokens (by 4–8 tokens in the case of EXP, and 10–20 tokens in the case of ITS) suffices to distinguish watermarked text with roughly the same statistical power as $n=64$.

2 Robustness to corruption and paraphrasing

We now proceed to evaluate the robustness of our watermark strategies to various forms of corruption and paraphrasing. We focus on comparing our strongest watermarks ($\mathtt{EXP}$ and $\mathtt{EXP}$-$\mathtt{edit}$) against $\mathtt{KGW}$-$\mathtt{2.0}$, deferring results for all other watermarks to Appendix D.5. As larger $n$ increases the computational overhead of computing our test statistics and the effect of larger $n$ on statistical power is mild (as shown in Figure 4), we run all experiments with $n=256$, which in any case is sufficiently large to ensure the watermarked text across all experiments is distortion-free. Decreasing the insertion/deletion penalty $\gamma$ improves robustness (at least up to a point) but hurts the statistical power of the $\mathtt{ITS}$-$\mathtt{edit}$ and $\mathtt{EXP}$-$\mathtt{edit}$ watermarks for larger $n$, since reducing the penalizer for edits effectively increases the number of candidate alignments under consideration. We run $\mathtt{ITS}$-$\mathtt{edit}$ and $\mathtt{EXP}$-$\mathtt{edit}$ with the same choices of $\gamma$ as in the previous section. We defer the details of tuning $\gamma$ to Appendix D.4.

We vary the fraction of substituted tokens in Figure 5, and we vary the fraction of inserted and deleted tokens in Figures 6 and 7 respectively. For the insertion experiment, we pass only the first $m$ tokens to the detector; similarly, for the deletion experiment, we initially generate more than $m$ watermarked tokens so that even after deleting a fraction thereof, there are at least $m$ tokens remaining. The $\mathtt{EXP}$ and $\mathtt{EXP}$-$\mathtt{edit}$ watermarks are comparably robust to substitution errors, but the latter is far more robust to insertion and deletion errors.

We compare our watermarks against the most robust version of $\mathtt{KGW}$-$\mathtt{2.0}$, in the sense that we hash only the previous token to determine the next token distribution and thus bias the distribution towards some subset of bigrams. If instead we hash the previous $k$ tokens for $k>1$, then substituting any one of the previous $k$ tokens will break the watermark signal in a particular token, and thus the statistical power of their watermark will be worse than what we report in our experiments.

Finally, in Figures 9 and 10 we implement a “roundtrip translation” attack, wherein we attempt to paraphrase watermarked texts of varying lengths by translating the (English) texts into another language (i.e., French and Russian respectively) and back again using a machine translation model (details in Appendix D.2). We include a representative example of the original and (re-)translated texts in Figure 8. Using Russian is a noticeably more effective attack than French: none of the watermarks aside from $\mathtt{EXP}$-$\mathtt{edit}$ are able to reliably detect watermarked text with $p<0.05$ irrespective of $m$.

In many cases, both using French and Russian, the roundtrip translation still preserves large chunks of the original text, which suffices for watermark detection even using $\mathtt{EXP}$, which is substantially less robust to insertion and deletion errors than $\mathtt{EXP}$-$\mathtt{edit}$. Aside from inspecting a few examples, we did not verify that the roundtrip translations preserve the basic semantics of the original text; thus, it is possible our results provide an overly pessimistic view of the robustness of our watermarks to these attacks, since in practice users would presumably not publish such examples. It is also possible that using different machine translation models—or more generally, different forms of automated paraphrasing—might be far more effective in evading watermark detection than those we employed. We publish the full set of watermarked generations for each watermarking strategy, along with their (roundtrip) translations, as part of our code release.

3 Case study: instruction following

In the wild, most users interact with language models by prompting the model with instructions (e.g., “give me code for…”), and the most widely-used language models (e.g., ChatGPT) are specifically fine-tuned to follow such instructions. Thus, using the instruction fine-tuned Alpaca-7B model, we presently conduct a case study on the effectiveness of watermarking a performant instruction following model. In particular, we sample $200$ instructions from the Alpaca-7B evaluation dataset and generate watermarked responses of at most $200$ tokens for each. We then compute conditionally valid $p$-values for each response using the original version of $\mathtt{detect}$ with $T=500$. We also replicate the roundtrip translation attack from Experiment 6. We publish the full set of watermarked generations for each method, along with their (roundtrip) translations, and the instruction prompts as part of our code release.

We plot the distribution of $p$-values for the $\mathtt{EXP}$-$\mathtt{edit}$ and $\mathtt{KGW}$-$\mathtt{2.0}$ watermarks in Figure 11, as well as the $p$-values versus the watermark potential of the watermarked text in Figure 12. In general, the Alpaca-7B responses have considerably lower per-token watermark potential than both the OPT-1.3B and LLaMA-7B models, and thus the statistical power of our watermark is worse despite the responses typically being longer than in the previous experiments (i.e., Experiments 1 and 6). In particular, based on the same random sample of $200$ prompts (from the Alpaca evaluation set in the case of Alpaca-7B, and from the news-like subset of the C4 dataset in the cases of LLaMA-7B and OPT-1.3B), the average per-token watermark potential of text from Alpaca-7B is $0.28$, compared to $0.59$ for LLaMA-7B and $0.67$ for OPT-1.3B. Unlike the previous experiments, $\mathtt{KGW}$-$\mathtt{2.0}$ noticeably outperforms the $\mathtt{EXP}$-$\mathtt{edit}$ watermark. Figure 12 indicates this difference in performance is largely due to the fact $\mathtt{KGW}$-$\mathtt{2.0}$ distorts the distribution of the text and produces responses with noticeably larger watermark potential than regular responses from the model. For responses whose unnormalized watermark potential (i.e., watermark potential multiplied by the number of tokens in the response, to account for the varying lengths of the responses) exceeds roughly $60$, both watermarks tend to yield $p$-values close to zero. Paraphrasing the responses via roundtrip translation attacks into both French and Russian degrades the statistical power of both watermarks, as we show in Figures 13 and 14.

Finally, recall the main distinguishing feature of our watermark compared to Kirchenbauer et al. and Aaronson is that we do not hash previous tokens to determine the distribution of the next token. To demonstrate the pitfalls of hashing, we implement a version of the watermark Aaronson proposes by modifying the $\mathtt{generate}$ method of $\mathtt{EXP}$ to obtain the vector $\xi_{i}\in^{N}$ from seeding a random number generator using the previous $k$ tokens instead of using the watermark key; we call this version $\mathtt{EXP}$-$\mathtt{hash}$. We then prompt Alpaca-7B with requests for various kinds of lists. Because Alpaca-7B tends to separate items in lists by the same recurring token, e.g., a comma or a newline character, and because this recurring token determines the next token, for $k=1$ the lists degenerate into repetition (Figure 15). The authors would like to pat themselves on the back by drawing the reader’s attention to the fact that the title of this paper is not among those suggested by Alpaca-7B.

From inspection, hashing with $k>1$ substantially improves the quality of samples; however, even using $k=4$ can sometimes produce noticeably repetitive text. We reiterate that while increasing $k$ may improve sample quality by making the distortions of watermarked text less noticeable, doing so harms the robustness of the watermark (e.g., replacing just $20\%$ of the tokens would suffice to evade detection for $k=4$). Moreover, using a more robust hash function does not avoid this trade-off between robustness and distortion-freeness, as there is a direct trade-off between the likelihood of a hash collision and the robustness of the hash. In addition to Figure 15, we include more examples (for both $k=1$ and $k=4$) and different prompts in Appendix D.5.5 and our code release.

Discussion

In this paper, we give the first distortion-free watermarking strategies for language models that are robust to editing and/or cropping. The key idea underpinning our approach is to leverage methods for robust sequence alignment to align a putative watermarked text to a watermark key sequence which the LM provider uses to generate watermarked text. The statistical power of our watermarks improves exponentially with respect to the length of the text and diminishes only linearly with respect to the length of the watermark key sequence.

The computational complexity of our watermark detection algorithms grows linearly with the length of the watermark key sequence, which is also the total number of distortion-free watermarked tokens the LM provider may generate. In contrast, the complexities of the watermark detection algorithms of both Christ et al. and also Aaronson and Kirchenbauer et al. depend only on the length of the input text; however, the former watermark is not robust to corruption and the latter two watermarks are not distortion-free. Whether this apparent trade-off between computational complexity, robustness and distortion-freeness is a fundamental trade-off is an interesting open question.

The underlying assumption behind all of the above watermarking strategies including ours is that the LM provider and the watermark detector coordinate by sharing information in advance, e.g., a watermark key. Indeed, the main inherent limitation of watermarking is that the detector must trust the LM provider to faithfully apply the watermark when generating text. A second limitation, which is not inherent but does presently apply to all known watermarks, is that the LM provider cannot release the model weights, since then users could simply query the model directly instead of through the LM provider. Planting robust watermarks directly into the weights of a language model without degrading the quality of the model is an important direction for future work.

Recently, several major language model providers (among others: OpenAI, Anthropic, Google and Meta) have pledged to watermark the text from their models . Thus, we conclude with some salient recommendations for practitioners. First, we recommend practitioners use our $\mathtt{EXP}$-$\mathtt{edit}$ watermark, as it is by far the most robust watermark of those we tested. Second, though in principle the length of the watermark key sequence $n$—which recall imposes a cap on the total number of distortion-free watermarked tokens the LM provider can generate—can grow (nearly) exponentially in the block size $k$ of the test statistic while still enabling watermark detection from as few as $k$ tokens, in practice we find that using a fairly small watermark key sequence (e.g., $n=256$) does not noticeably affect the quality of watermarked text (i.e., even when generating more than $n$ tokens total). Our watermark detection procedures (i.e., both $\mathtt{detect}$ and the test statistic therein from Algorithm 3) are easily parallizeable, so we expect even with a very large watermark key sequence (e.g., $n=100000$) the computational demands of watermark detection will not be a significant bottleneck—though we caveat this speculation by noting that we did not ever run such large $n$ with our implementation.

Acknowledgement

We thank Saminul Haque, Gary Cheng and Padma Kuditipudi for pointing out errors in preliminary drafts of this work and for their helpful feedback in general. This work is supported by an Open Philanthropy Project Award (OpenPhil) and an NSF Frontier Award (NSF Grant no. 1805310).

References

Appendix A Proof of Lemma 2.2

To show the claim, we first lower bound the probability that $Y=Y^{\prime}$. In particular,

where ($\star$) follows from $\exp(-cx)\leq 1-x$ for $0\leq x\leq 1-\exp(-c/2)$. It then follows immediately that

The desired result thus follows from letting $A$ be the event that $h$ predicts $-1$. ∎

Appendix B Analysis of inverse transform sampling

To prove the main theorems, we introduce the following supporting lemma. Recall $C_{0}=\textup{Var}(\eta(\textup{Unif}([N])))$.

Let $\mu\in\Delta([N])$. Let $(U,\pi)\sim\textup{Unif}()\times\textup{Unif}(\Pi)$ and $Y=\Gamma((U,\pi),\mu)$. Then $\frac{1}{C_{0}}\textup{Cov}(U,\eta(\pi(Y))\mid Y)=1-\mu(Y)$ almost surely.

We first characterize the conditional distribution of $\pi$ given $Y$ and the conditional distribution of $U$ given both $\pi$ and $Y$, where recall $\pi$ and $Y$ are discrete. Applying Bayes’ formula and Theorem 1, we have

where ($a$) follows from Bayes’ formula and the independence of $U$ and $\pi$; ($b$) follows from the definition (1) of the decoder $\Gamma$; and ($c$) follows from $I(Y,\pi)\subset$ having width equal to $\mu(Y)$. The displays (7) and (8) respectively imply $\pi\mid Y\sim\textup{Unif}(\Pi)$ and $U\mid\pi,Y\sim\textup{Unif}(I(Y,\pi))$, from which it follows that

from which the desired result follows immediately from recalling $\pi(Y)\mid Y\sim\textup{Unif}([N])$ and the definition of the constant $C_{0}$. ∎

B.2 Proof of Lemma 2.4

We prove the following more general result, from which Lemma 2.4 follows as a corollary.

Lemma 2.3 and the conditional independence of $\tau$ and $\xi$ given $Y$ imply for any $j\in[n]$ that

Each summand in equation (9) lies between $-1/4$ and $1/4$, and also $(U_{i},\pi_{i})$ is conditionally independent of $U_{-i}$ and $\pi_{-i}$ given $Y$. Thus, Hoeffding’s inequality [27, Proposition 2.5] implies for $j\in[n]$ that

Recalling the definition of the test statistic $\phi$ via Algorithm 3, the main claim then follows from taking a union bound over all $j\in[n]$. ∎

B.3 Proof of Lemma 2.5

We begin with the following observation for a single token.

Let $P\in\Delta([N])$. Let $(U,\pi)\sim\textup{Unif}()\times\textup{Unif}(\Pi)$ and $Y=\Gamma((U,\pi),P)$. Let $\widetilde{Y}\in[N]$ be conditionally independent of $(U,\pi)$ given $Y$. If $\widetilde{Y}\neq Y$, then almost surely

Observe the conditional distribution of $\pi(\widetilde{Y})$ given $Y$ is uniform over $[N]\setminus\{\pi(Y)\}$. Let $X$ be a random variable that is equal to $\eta(\pi(Y))$ with probability $1/N$ and otherwise equal to $\eta(\pi(\widetilde{Y}))$. Observe $X$ is independent of $Y$ and thus also $U$ by assumption—in particular, $(N-1)X+1\mid Y\sim\textup{Unif}([N])$ irrespective of the value of $Y$. The claim thus follows from rearranging terms in the equality

Lemma 2.3 and Observation B.1 together imply for any $j\in[n]$ that

i.e., by adding the two results together using Observation B.1 to account for the influence of each substituted token on the expectation. Using the same concentration argument as in the proof of Theorem 2.4, we then have

Recalling the definition of the test statistic $\phi$ via Algorithm 3, the main claim then follows from taking a union bound over all $j\in[n]$ and recalling $k=m$ by assumption. ∎

B.4 Proof of Lemma 2.6

We begin with the following useful facts about edit distance. Throughout, let $\mathcal{S}(y)$ denote the set of substrings of a string $y\in\mathcal{V}^{*}$, including the empty string.

Let $y,\widetilde{y}\in\mathcal{V}^{*}$. Then $d_{\textup{edit}}(y,\widetilde{y})$ is the length of the smallest sequence of insertion and/or deletion operations to obtain $\widetilde{y}$ from $y$.

We proceed via induction on the sum $\mathtt{len}(y)+\mathtt{len}(\widetilde{y})$. The base case where $y$ and $\widetilde{y}$ are both empty is trivial. Now suppose the claim holds all strings whose lengths sum to at most $\mathtt{len}(y)+\mathtt{len}(\widetilde{y})-1$. Recalling the definition of $d_{\textup{edit}}$ (Definition 4), there are three cases.

First, suppose $d_{\textup{edit}}(y,\widetilde{y})=d_{\textup{edit}}(y_{2:},\widetilde{y}_{2:})$. Then by induction there exists a sequence of $d_{\textup{edit}}(y,\widetilde{y})$ insertion and/or deletion operations to obtain $\widetilde{y}_{2:}$ from $y_{2:}$. Because $y_{1}=\widetilde{y}_{1}$, the same sequence suffices to obtain $\widetilde{y}$ from $y$ and thus the claim follows.

Second, suppose $d_{\textup{edit}}(y,\widetilde{y})=1+d_{\textup{edit}}(y_{2:},\widetilde{y})$. Again by induction, there exists a sequence of $d_{\textup{edit}}(y,\widetilde{y})-1$ insertion and/or deletion operations to obtain $\widetilde{y}$ from $y_{2:}$. It follows immediately (i.e., by first deleting $y_{1}$) there exists a sequence of $d_{\textup{edit}}(y,\widetilde{y})$ such operations to obtain $\widetilde{y}$ from $y$, and so the claim holds.

The third case follows by symmetry with the second case. ∎

Let $y,\widetilde{y}\in\mathcal{V}^{*}$. Then for any $\tau<\mathtt{len}(y)$, we have

Observation B.2 implies there exists a sequence of $d_{\textup{edit}}(y,\widetilde{y})$ insertion and/or deletion operations to obtain $\widetilde{y}$ from $y$. We may partition this sequence of operations into sequences based respectively on whether they occur on $y_{:\tau}$ or $y_{\tau+1:}$. Let $\widetilde{y}_{\textup{pre}}$ be the result of performing the first sequence of operations on $y_{:\tau}$ and let $\widetilde{y}_{\textup{suf}}$ be the result of performing the second sequence of operations on $y_{\tau+1:}$. Then $\widetilde{y}$ is the concatenation of $\widetilde{y}_{\textup{pre}}$ and $\widetilde{y}_{\textup{suf}}$, and so the claim follows from the fact that

Let $y,\widetilde{y}\in\mathcal{V}^{*}$ and $\xi\in\Xi^{*}$. Then $d_{\gamma}(y,\xi)\leq\gamma d_{\textup{edit}}(y,\widetilde{y})+d_{\gamma}(\widetilde{y},\xi)$.

We claim $d_{\gamma}(y_{i:},\xi_{j:})\leq d_{\gamma}(\widetilde{y}_{i:},\xi_{j:})+\gamma$. If $y_{i+1:}=\widetilde{y}_{i:}$, then the claim obtains as

with $(\star)$ following from the fact that $d_{0}(y_{i},\xi^{\prime})=0$ for $\xi^{\prime}=(1/2,\pi)$ irrespective of $y_{i}$ and $\pi$.

Otherwise, if $y_{i:}=\widetilde{y}_{i+1:}$, then from unrolling the recursive definition of $d_{\gamma}(\widetilde{y}_{i:},\xi_{j:})$ there must exist some index $j^{\prime}\geq j$ such that either

In the first case, we have $\gamma+\min_{\xi^{\prime}\in\Xi}d_{0}(\widetilde{y}_{i},\xi^{\prime})>0$ since $\gamma>1/2$ by assumption, and so the claim follows as

In the second case, we have $d_{0}(\widetilde{y}_{j})$ the claim follows as

Thus, assuming $d_{\textup{edit}}(y,\widetilde{y})\leq 1$, we have shown $d_{\gamma}(y_{i:},\xi_{j:})\leq d_{\gamma}(\widetilde{y}_{i:},\xi_{j:})+\gamma$, from which it follows that $d_{\gamma}(y,\xi)\leq d_{\gamma}(\widetilde{y},\xi)+\gamma$. The general result follows immediately by applying Observation B.2 and summing the bound for a single edit over the (smallest) sequence of edits to obtain $\widetilde{y}$ from $y$. ∎

Proceeding with the main proof, define for convenience the quantity

while Observation B.3 together with our assumption that $d_{\textup{edit}}(Y,\widetilde{Y})\leq\varepsilon m$ implies

The displays (10) and (11) together imply there exists an index $\tau$ and $Y^{\prime}\in\mathcal{S}(\widetilde{Y})$ such that $\widehat{\alpha}_{\tau}-\frac{1}{k}\min_{Y^{\prime}\in\mathcal{S}(\widetilde{Y})}d_{\textup{edit}}(Y_{\tau+1:\tau+k},Y^{\prime})\geq\alpha(Y)-\varepsilon$. Reusing the same concentration argument as in the proof of Theorem 2.4, for $t\geq 0$ we have

and thus from Observation B.4 it follows that

Letting $t=(C_{0}\alpha-\gamma\varepsilon)/2$ and recalling the definition of the test statistic, we have

All that remains to bound the probability of $\phi(\widetilde{Y},\xi^{\prime})$ exceeding the threshold from the above display. To this end, define the set-valued map $\mathcal{N}_{\beta}(y):=\{y^{\prime}\ :\ d_{\textup{edit}}(y,y^{\prime})\leq\beta/(4\gamma-1)\}$. Then we make the following observation.

For any $y\in\mathcal{V}^{*}$ and $\xi\in\Xi^{*}$, there exists $y^{\prime}\in\mathcal{N}_{\mathtt{len}(\xi)}(y)$ such that

We proceed via induction. The base case where $y$ and $\xi$ both have length $1$ follows trivially by taking $y^{\prime}=y$; in particular, $\gamma>1/2$ implies $d(y,\xi)\leq\gamma+\min_{y^{\prime}}d(y^{\prime},\xi)$ and likewise $d(y,\xi)\leq\gamma+\min_{\xi^{\prime}}d(y,\xi^{\prime})$. Now suppose the result holds so long as $\mathtt{len}(y)+\mathtt{len}(\xi)\leq n-1$. We claim that the result must then also hold if the lengths sum to at most $n$.

We prove this inductive claim by considering three exhaustive cases. First, suppose that $d_{\gamma}(y,\xi)=d_{\gamma}(y_{2:},\xi_{2:})+d(y_{1},\xi_{1})$. By our induction hypothesis, there exists $\hat{y}\in\mathcal{N}_{\mathtt{len}(\xi)-1}(y_{2:})$ such that $d_{\gamma}(y_{2:},\xi_{2:})=\gamma\cdot d_{\textup{edit}}(y_{2:},\hat{y})+d(\hat{y},\xi_{2:})$. The desired result then obtains with $y^{\prime}$ as the concatenation of $y_{1}$ and $\hat{y}$. Second, suppose $d_{\gamma}(y,\xi)=d_{\gamma}(y,\xi_{2:})+\min_{\xi^{\prime}\in\Xi}d(y_{1},\xi^{\prime})+\gamma$. By our induction hypothesis, there exists $\hat{y}\in\mathcal{N}_{\mathtt{len}(\xi)=1}(y)$ such that $d_{\gamma}(y_{2:},\xi)=\gamma\cdot d_{\textup{edit}}(y_{2:},\hat{y})+d(\hat{y},\xi_{2:})$. The result obtains with $y^{\prime}=\hat{y}$. Finally, suppose $d_{\gamma}(y,\xi)=d_{\gamma}(y_{2:},\xi)+d(y^{\prime\prime},\xi_{1})+\gamma$ for some $y^{\prime\prime}\in\mathcal{V}$. By our induction hypothesis, there exists $\hat{y}\in\mathcal{N}_{\mathtt{len}(\xi)-1}(y)$ such that $d_{\gamma}(y_{2:},\xi)=\gamma\cdot d_{\textup{edit}}(y_{2:},\hat{y})+d(\hat{y},\xi)$. The result then obtains by concatenating $y^{\prime\prime}$ with $\widehat{y}$. ∎

Let $\mathcal{I}_{j}:=\{(j+i)\%n\}_{i=1}^{k}$. For any $0\leq i\leq\mathtt{len}(\widetilde{Y})-k$ and $j\in[n]$, Observations B.4 and B.5 together imply that

where ($\star$) follows from the fact that $d_{\textup{edit}}(\widetilde{Y}_{i+1:i+k},y)>k/4(\gamma-1)$ implies

and therefore the minimizer in equation (13) must be an element of $\mathcal{N}_{k/4(\gamma-1)}(\widetilde{Y}_{i+1:i+k})$.

By construction, $\mathcal{N}_{\beta}(y)$ consists of the set of strings obtainable from $y$ by a sequence of at most $\beta$ insertion and/or deletion operations. Now define another set-valued map $\mathcal{N}_{\beta,-}(y)$ as the restriction of $\mathcal{N}_{\beta}(y)$ such that we may only insert a particular token into $y$ (which token is immaterial). As the specific identity of each token we insert into $y$ can only influence the value of $d_{\gamma}$ by $\pm 1/2$, for any $\beta$ it follows that

and so, letting $\beta=k/4(\gamma-1)$, from equation (14) we have

Combining the displays (12) and (15) via another union bound gives the desired result. ∎

Appendix C Analysis of exponential minimum sampling

To prove the main theorems, we introduce the following supporting lemma. The result is well known and we restate it here only for completeness.

Let $\mu\in\Delta([N])$ and $\xi\sim\textup{Unif}(^{N})$. Then for any $y\in[N]$ we have

Suppose $\mu(y)>0$ as otherwise the claim is trivial. Recalling $\xi_{i}\overset{\text{i.i.d.}}{\sim}\textup{Unif}()$, for any $\lambda>0$ we have $-\lambda\log\xi_{i}\overset{\text{i.i.d.}}{\sim}\textup{Exp}(\lambda)$, i.e.,

where in ($\star$) we use the fact that the density of $-\log(\xi_{y})/\mu(y)$ at $u$ is $\mu(y)\exp(-\mu(y)u)$. ∎

The result follows immediately from integrating the result of Lemma C.1 over $t\geq 0$. ∎

C.2 Proof of Lemma 2.7

C.3 Proof of Lemma 2.8

We prove the following general result, from which Lemma 2.8 follows as a corollary.

Lemma 2.7 and the conditional independence of $\tau$ and $\xi$ given $Y$ imply for any $j\in[n]$ that

From Lemma C.1, we have $-\log\xi_{\tau+i,\widetilde{Y}_{i}}\mid\widetilde{Y},Y\sim\textup{Exp}(\gamma_{i})$ for some $\gamma_{i}\leq 1$ for all $i\in[m]$. Also, from the independence of $\widetilde{Y}$ and $\xi^{\prime}$, we have $-\log\xi_{j,\widetilde{Y}_{i}}^{\prime}\mid\widetilde{Y},Y\sim\textup{Exp}(1)$ for all $i\in[m]$ and $j\in[n]$. The following observation thus implies $-\log\xi_{i,\widetilde{Y}_{i}}\mid\widetilde{Y},Y$ and $-\log\xi_{j,\widetilde{Y}_{i}}^{\prime}\mid\widetilde{Y},Y$ are both $(2,2)$-subexponential random variables.

Let $X\sim\textup{Exp}(1)$. Then $X$ is a $(2,2)$ subexponential random variable.