Robust Distortion-free Watermarks for Language Models
Authors: Rohith Kuditipudi
John Thickstun
Tatsunori Hashimoto
Percy Liang
Venue: Accepted by TMLR ()

Abstract: We propose a methodology for planting watermarks in text from an autoregressive language model that are robust to perturbations without changing the distribution over text up to a certain maximum generation budget. We generate watermarked text by mapping a sequence of random numbers—which we compute using a randomized watermark key—to a sample from the language model. To detect watermarked text, any party who knows the key can align the text to the random number sequence. We instantiate our watermark methodology with two sampling schemes: inverse transform sampling and exponential minimum sampling. We apply these watermarks to three language models—OPT-1.3B, LLaMA-7B and Alpaca-7B—to experimentally validate their statistical power and robustness to various paraphrasing attacks. Notably, for both the OPT-1.3B and LLaMA-7B models, we find 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). 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 certain automated paraphrasing attacks we implement.

Published in Transactions on Machine Learning Research (05/2024)
Robust Distortion-free Watermarks for Language Models
Rohith Kuditipudi
rohithk-@stanford
Deportment of Computer Science
Stanford University
John Thickstun
jlhicstuun&stannford edu
Department of Computer Science
Stanford University
Tatsunori Hashimoto
thashim lataanin@sttfoood....c edu
Department of Computer Science Stanford University
Percy Liang
plaang@@ee.ssannford.c edu
Department of Computer Science Stanford University
Reviewed on OpenReview: https: // openreview. net/ forum? id= PdPPLLM00
Abstract
We propose a methodology for planting watermarks in text from an autoregressive language model that are robust to perturbations without changing the distribution over text up to certain maximum generation budget. We generate watermarked text by mapping sequence of random numbers which we compute using a randomized watermark key to sample from the language model. To detect watermarked text, any party who knows the key can align the text to the random number sequence. We instantiate our watermark method- ology with two sampling schemes: inverse transform sampling and exponential minimum sampling. We apply these watermarks to three language models OPT-1.3B, LLaMA-7B and Alpaca-7B to experimentally validate their statistical power and robustness to various paraphrasing attacks. Notably, for both the OPT-1.3B and LLaMA-7B models, we find can reliably detect watermarked text (p < 0.01) from 35 tokens even after corrupting between 40-50% of the tokens via random edits (i.e., substitutions, insertions deletions). For the Alpaca-7B model, conduct case study sponses 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 S 0.01, and the watermark is also less robust to certain automated paraphrasing attacks we implement."
the feasibility of watermarking
1 Introduction
The ability 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 OpenAl's ChatGPT model mitigate the spread of misinformation on the platform Vincent (2022). A reliable forensic tool for attributing text particular language model would empower individuals such 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.
We release all code publicly httpp:: http::///gtthb...oomjjiiccttttts

---

Published in Transactions on Machine Learning Research (05/2024)
LM Provider
1
User
Detector
Write essay World War 1,
Word
World War 1 most deadly...
4
World War was the deadly...
Figure 1: We define the following watermarking protocol between three parties: the LM provider, the user, the detector. The LM provider and the detector coordinate via a shared key, while the user is an untrusted third party. The protocol consists of four steps: 1) the user sends a prompt to the LM provider; 2) the LM provider generates watermarked text the user; 3) the user edits the watermarked text (to avoid detection) and publishes the edited text; 4) the detector verifies which of the published text. came from the LM provider.
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 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;
2. 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 Kirchenbauer et al. (2023); Aaronson (2023), or are not robust to editing or cropping the text Christ et al. (2023). Meanwhile, classical steganographic techniques for covertly encoding messages within samples of text from a language model are neither agnostic nor robust Ziegler et al. (2019). We develop the first watermarks for attributing lext lo 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 under their control: a generate method that deterministically maps a sequence & of random numbers encoded by a (secret) watermark k we call the walermark key sequence to a sample from the language model, and a detect method that aligns a putative watermarked text with the watermark key sequence using the shared key. Informally, our watermarks are distortion the sense that marginalizing over the watermark key sequence each call to generate is equal in distribu- tion sample from the original language model, i.e., P(text) Se (text generate(E, prompt)] dv(E) is equal to the original language model's sampling distribution.
The challenge of detecting watermarked text is that the detector cannot simply recompute 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 casily detectable with a suitable model-agnostic and prompt-agnostic test statistic such that d(gnnertte(,, prompt), < ((text, {) for any text that is independent of the watermark key sequence. The idca here is that the detector may use & within detect to compute p-value with respect to the null hypothesis that the text is independent of the walermark key sequence, i.e., that the text is not watermarked.
To ensure detect is robust to odits of the watermarkod text, the core idca underpinning the design cach test statistic & is to leverage techniques for robust sequence aligument align pulative walermarked
Whether the watermark key secret (e.g., if the LM provider publishes the key to allow anyone detect watermarked text) an implementation choice that does not affect the main parts of our analysis.
2

---

Published in Transactions on Machine Learning Research (05/2024)
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 sufficienlly motivated and/or sophisticated user can still evade detection by simply rewriting the text from scratch themselves (or, using another language model to generale 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 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 shift-generate around generate that calls generate using a randomly chosen subsequence of & instead of generating tokens from the same starting point each time. For the same reasons that detect is robust to editing and cropping watermarked text, calling generate in this fashion does not affect watermark dotoctability. 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 mumber 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). So long as we do not reuse an element of the key sequence, successive calls to Shift-generate will be jointly indistinguishable from regular calls to the language model.
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. (2023) and Aaronson (2023) that bias the distribution of watermarked text towards certain k-grams by hashing sliding window of the previous k --1 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. (2023) proposc 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. (2023) and Aaronson (2023), 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-fres 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 statis- tical 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 S 0.01) from 35 tokens even af- ter 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 wa- termarking responses to typical user instructions. Due to the lower entropy of the responses, detection is more difficult: around 25% of the responses wwhose median length is around 100 tokens are delectable with p 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- nr-brrwser demo of the watermark detector.
1.1 Related work
Text watermarking is a special case of linguistic steganography, in that the goal is to convey a hidden message- the watermark wwithn within a passage of text. Existing approaches to linguistic steganography fall under two broad categories: edit-bused methods that modify a pre-existing text, and generative hods that
For assets and supplemental material, see: https://github.cem http:://ggkhho....oonhhhhhhhttte
3

---

Published in Transactions on Machine Learning Research (05/2024)
construct a distribution over cover text (Ucoka et al., 2021). Crucially, in contrast to steganography, the literature on digital watermarking has historically foregrounded robustness to corruption as a key attribute of a good watermark (Katzenbeisser & Petitcolas, 2000; Atallah et al., 2001). 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 (Dai & Cai, 2019; Ziegler el al., 2019; Shen el. al., 2020).
Older work on text watermarking considers editing a pre-existing text to include a watermark (Rizzo et al., 2019; Abdelnabi & Fritz, 2021; Yang et al., 2022); for survey of edit-based watermarks, see Kamaruddin et al. (2018). In contrast, we are interested in generating watermarked text while preserving the distribution over the text from language model. Work on generative watermarking is nascent, underwritten by recent advances in open-ended text generation (Brown et al., 2020). Pioneering work by Venugopal et al. (2011) 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 hypothesis test.
Our work is most closely related to Kirchenbauer el al. (2023), who watermark text from a language model by reweighting the token log- probabbiillsss from the model at inference time function (i.e., hash) of the previous k- 1 tokens, where & E N is a hyperparameter. In ongoing unpublished work concurrent to ours, Aaronson (2023) describes technique for watermarking language models using exponential minimum sampling (a close relative of the Gumbel trick Papandreou & Yuille (2011)) to sample from the model, where I tokens. Neither watermark is
the imputs to the sampling mechanism are also a hash of the previous distortion-free, and in fact we show in our experiments that the distortions manifest noticeably in practice (e.g., excessive repetition of certain tokens). Specifically, both Kirchenbauer et al. (2023) and Aaronson (2023) bias the distribution toward subset of k-grams. Increasing k makes the bias less noticeable but hurts the robustness of both watermarks: adversary can break the signal from a particular token by replacing any one of the previous ks - 1 tokens.
Also concurrent to our work, Christ et al. (2023) propose watermarking blocks of text from a language model by hashing each block to seed a sampler for the next block. Christ et al. (2023) vary their block sizes which are analogous to the hyperparameter of Kirchenbauer et al. (2023) and Aaronson (2023) 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 language model's sampling distribution; however, the resulting watermark is not robust. since in order to miligale 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. (2023) and Aaronson (2023) replacing any token in the previous block breaks the watermark in the next block. Whereas Christ et al. (2023) (2h who do not run experiments -chieensssshhee choose their block sizes to be sufficiently large to minimize distortion, Kirchenbauer et al. (2023) and Aaronson (2023) recommend choosing k to be small constant in practice, which ensures moderate amount of robustness by introducing some distortion. Finally, whereas our definition distortion-freenes implies exact equality in distribution of watermarked text to unwaterarredd text for single query to the language model, Christ et al. (2023) propose definition of "undetoctability" that implics approximate equality in distribution, i.c., approximate distortion-freeness,, over multiple queries. Using shift-generate, we also achieve approximate fistortion-freeness in the multiple query setting, though the runtime of our watermark detection procedure must grow with the number of queries; we discuss these trade-offs in more detail in Section 4.
An alternative approach for detecting synthetic text is to learn a classifier between synthetic and human text (Jawahar et al., 2020; Mitchell et al., 2023). 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-fre) 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 (He et al., 2022a;b; Zhao et al., 2023). 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.
4

---

Published in Transactions on Machine Learning Research (05/2024)
2 Methodology and theoretical analysis
Let V be a discrete set, i.e, the vocabulary, and let p E V + A(V) be an autoregressive language model which maps string of arbitrary length to distribution over the vocabulary, with p(- x) denoting the distribution of the next token given the prefix V* Let denote the space in which the elements of the watermark key sequence lic. Recall the main protocol (Figure 1) which defines our problem setting:
0. The LM provider shares a random watermark key sequence & E E with the detector;
1. The user sends prompt V to the LM provider;
2. The LM provider generates text Y E V by Y generate(r, {);
The user publishes text Y E V", which may be either (i) (an edited version of) the generated text or (ii) lext independent of Y (e.g., lext that they wrote themselvess
4. The detector determines if Y watermarked i.e, Y depends on the watermark key sequence by computing a p-value p = detect((Y, with respect to the null hypothesis that Y is independent, of & (i.e., not watermarked).
2.1 Protocol details
In the protocol, the LM provider calls the generate method (Algorithun 1) to autoregressively generate text from a language model using decoder function r E A(V) - V which maps an element & of the watermark key and a distribution over the next token to a next token prediction. By design, over the randomness of & the prediction should constitute a sample from the distribution, i.c., P(T p)) = ys) = =(x)).
Definition 1. A decoder I' E x A(V) + V is distortion- with respect to (the distribution of) random variable & E if for any AVV and y E V it satisfies P(T = y) m(y).
We relate Definition to our informal definition of distortion-free text in the introduction through the following simple lemma. Essentially, long as the watermark key sequence is long enough that we do not reuse any part of it to generate text, the only material difference between an LM provider using generate versus sampling directly from the language model is that the sequence & is an imput to the method rather than resampled i.i.d. within the method for each call. We treal the language model the decoder T, and generation length m as internal parameters of the generate method.
Lemma 2.1. Let n E N with n 2 m. Let r be distortion free with respect to a distribution v A(E) and s.d.d. let 1 ~ v. Let Y generate({: m, p, 1'). Then Y, ~ p(- Yu-1) for [m].
Proof. As 2 m, we have (m sid. Line 2 of generate for E [m].
~ v. The claim then follows immediately from applying Definition to
7
To simplify the remainder of the presentation, do not pass prompt input to generate. As the language model is arbitrary and detect is model-agnostic, this simplification is without loss of generality since itself may model the distribution of text from some base model given an arbitrary prompt. Also, unless stated otherwise, without loss of generality we let V = [N] throughout the paper, where N E N is the vocabulary size.
The detector calls the detect mothod (Algorithm 2) to computo-vin via a permutation test with T resamples a p-value with respect to a test statistic Φ: V* E* + R for the null hypothesis that Y is not watermarked, i.c., that Y is independent of E. The output f of detect is a proper non-asymptotic p-value: if Y is not watermarked, then each (()) constitutes an independent, identically distributed copy of (Y.E) and therefore by symmetry is uniformly distributed over (1/(T 1),2/(T 1),..., 1} for any (non-atomic)
5

---

Published in Transactions on Machine Learning Research (05/2024)
Algorithm 1: Watermarked text generation (generate)
Input watermark key sequence & E
Params: generation length m, language model decoder F
Output: string y E pm
for E I...., do
V/ <- (( p(: Va--1)
return y
test statistic. returns small p-value (e.g., 0.0001) then the text likely watermarked; the p-value is large (e.g., 0.25), then the text might not be.
Algorithm 2:
Watermarked lext detection (detect)
Input string y E V*, watermark key sequence E Params: test statistic Φ; watermark key sequence distribution v E A(E"); resample size T Output: p-value 5 E [0,
for EEL. tE....., do
{(t) ~V
Φi cly. {(0)
p T+1
[ [+ 1
S o(y.
return p
The goal then is to design the test statistic & (Algorithm 3) such that f will typically be small Y is watermarked. In particular, the goal to identify an aligmment cost d: (V E)* E, which measures the quality of match between subsequence of the input text and subsoquence of the watermark key, and use this to define & the minimum cost alignment between length k subsequences of the text and key.
This alignment based detection strategy makes the watermark robust, since even if the user crops or otherwise corrupts Y, a single block preserved watermarked text within some larger body of unwatermarked text will suffice to trigger a low p-value from detect. The actual form of the alignment cost will be specific to each watermark particular, will depend on the nature of the decoder in generate. Our most robust watermarks incorporate 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 be the length of the input text y, n be the length of the watermark key sequence &, and k be the block size, the cost of computing the test statistic is Ommkk2).
Algorithm 3: Test statistic (Ø)
Input string y E V* watermark key sequence = Params: alignment cost d, block size k
Output: test statistic value d(y.g) {) E IR
for E 1,....,1enp 1en(y) k do
for E jel...... II...,,
3
y² - 1 ş + 10
dej + e')
return min;,; dr.j
*By non-atomic, for any R that P(o(Y,)) c) so that almost surely will not have to break tics (meaning, ((y.E) = de) when computing P. In case ties (l.e. if the statistic is atomic), we either modify detect hreak ties uniformly random, simply report valid but conservative p-values by leaving detect is.

---

Published in Transactions on Machine Learning Research (05/2024)
To illustrate how the decoder and the alignment cost fit together, we give simple example for the toy setting of a binary vocabulary.
Example 1: Consider a binary vocabulary V = {0, 1}. To generate Y E {0, 1}* from the model, the LM
provider shares {6]--1 iid. Uni 1)) with the detector and let Y, 0 if & S p(0 Ya-1) and Y, otherwise. In particular, defining the decoder T by
0 & S (10)
[E =
1 & (()),
let Y generate(f:m.p.. P) for some m I n. Then Y is valid sample from the language model as P(G: S p(0 Y)-1)) p(0 Ya-1), and crucially Y and & are correlated (i.e., if & is sufficiently close to zero then Y; 0, and likewise if & is sufficiently close to one then Y, = 1). Thus, we can define the alignment cost d(y, {) = lly - 1
Assuming for the sake of this example that n n m and the user does not corrupt the watermarked text from the LM provider, i.e., Y y=y, Y, the detector can run detect to verify that Y is watermarked using the test statistic & with alignment cost d and block size k = m. The value of the test statistic will then be most the & norm of Y -g. 0
2.2 Handling multiple queries
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 generate stateful, thus enabling the LM provider to generate a total of [n/m] in- dependent watermarked text samples of m tokens each from the language model. Instead, to avoid persisting state, we provide a randomized wrapper shift-generate (Algorithm 4) around generate and modify the watermarking protocol from the start of the section to allow the LM provider call the shift-generate instcad of generate in the second step of the protocol. The wrapper shift-generate randomly shifts the watermark key sequence before passing the shifted sequence to generate. Shifting the watermark key se- quence does not affect the value of the test statistic in 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 walermark key sequence, practice we find the effects of these correlations are not noticeable. The so-called birthday paradox Elfving et al. (1966) implies the LM provider can typically expect call shift-generate l(vn)) times, each time producing different text, before reusing the same offset twice. In fact, the provider can expect call shift- thift-generate (n/m) times before reusing subsequence, in which case the constituent Ω ((ynm) tokens in these texts will be indistinguishable from regular samples from the language model.
In general, we can bound the distortion (i.e., statistical distance from regular samples) of shift-generate in the multi-query setting by the probability of reusing an element of the watermark key sequence. Specifically, for T' queries and a maximum generation length of m tokens per query, we will achieve negligible, i.e., w(mT²). Thus, similar to Christ et al. (2023) we can achieve approximate
o11) distortion, so long distorsion-freeness in the multi-query setting. However, unlike Christ et al. (2023), to achieve approximate distortion-freenese in this setting the computational cost of our watermark detection procedure must grow with the larget nunber of queries. In principle, this trade-off between the degree of distortion and the runtime of watermark detection means at least in an asymptotic sense that the latter effectively upper bounds the number of queries to the LM provider an attacker would require to learn information about the watermark key sequence. In practice, we expect the cost per token of queries to the LM provider will be significant enough to make such attacks expensive to implement.
7

---

Published in Transactions on Machine Learning Research (05/2024)
Algorithm 4: Randomized watermarked text generation (shift-generate)
Input watermark key sequence & E
Params: generation length m, language model p, decoder P
Output: string y E ym
T Unif([n)),, E' + (6(++)) 1
return generate( m.
2.3 Terminology: watermark strategies and watermark potential
Henceforth, we use the term watermarking strategy to refer to a concrete instantiation of the shift-generate generate and detect methods by specifying the internal parameters of both algorithms (i.e., the decoder r, the test statistic ó and the watermark key sequence distribution v). We give concrete watermarking strategies in the following sections (Sections 2.4 and 2.5). For each watermarking strategy, we show two main results: we prove the dccoder is distortion-free and also obtain high probability upper bounds on the p-values of watermarked text as 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.
Definition 2. (watermark potential) Define a : V + IR by
len(y)
a(y) = len(y) yy)
Σ
plus Ma-1)).
The watermark potential of text from a deterministic language model will always be 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 : V" x E > +1] that tries to distinguish watermarked (positive label) versus nonwatermarked text (nogative label) given some watermark key (we make no assumption on the distribution of & except that it is independent of unwatermarked text by definition). We defer the proof of Lemma 2.2 to Appendix A.
Lemma 2.2. Let Y p(- Y for [m]. Let Y - Y' and let g E" be a random variable that is independent of Y'. Let h: V E" +11 be a classifier. Let c and define the set V. vm by
V. = fy : p(u v=-1) 2 exp(-c/2) for all i e [m]].
Then
P(N(Y,E) = -1) P(h(r',)))))) = 1) E (exp((eemmm))))) V.H..
Lemma 2.2 implies it is impossible to test between any watermarked and non non-watermarked text (i.e., between Y versus Y') that are equal in distribution (i.c., distortion-frec) 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 (resp., false Dositive/negativg
error rates of h will be close to one the watermark potential is close to zero. The theorem 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
8

---

Published in Transactions on Machine Learning Research (05/2024)
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.4 and 2.5 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 prove these upper bounds differ slightly from those employ in experiments: in the former case, prioritize the simplicity of stating the bounds in terms of watermark potential, whereas in the latter case, prioritize empirical performance.
2.4 Watermarking via inverse transform sampling
Inverse transform sampling a general technique for sampling from a univariate distribution by taking the pushforward of uniform random variable through its inverse cumulative distribution function (CDF). Crucially, the technique valid irrespective of the ordering of the CDF, property which we presently leverage to construct watermarking strategy in which generate is distortion and also detect is agnostic. In particular, we implement generate with a decoder that maps 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 ii.d. uniform irrespective of the text itself and thus not correlate with the sequence of uniform random variables.
Formally, with II as the space of permutations over the vocabulary [N], for & = (u, E [0, x II =; E and any distribution A[[N]), define the decoder by
T(g, =
-1 (min (m(() m(ii +()) S (())) u)),
(1)
i.e., I'E, ui) is the token with the smallest index in the permutation क such that CDF of μu with respect to π is at least u. Generalizing the intuition from Example 1, we show this decoder is distortion-free in the following theorem.
Theorem 1. Define by equation (1). Let x E II be arbitrory and let U Unif((0, 1]), with = (U, m). Then I is distortion-free with respect E.
Proof. Recalling Definition 1, the result follows from showing for any A(NN) and y E [N] that (H, = y) = p(v). To this end, by equation (1), we have I'u, {) = if and only if U lies in the interval
[u(t T(y') < a()))) xx() S +()))))
As the width of this interval is exactly p(y), the result follows immediately.
Having shown that the decoder is distortion-free, we now proceed to analyze the detoctability of the water- mark. For convenience, define the normalization 7) [N] + 10 by ni() = (i - 1)/(N - -)). Analogous to the toy example, the sequences (v))) and U are correlated. Thus, for the sake of analysis, we define alignment cost d: (V x E)* + IR by
len(y)
d(y. (u, T)) == Σ
(u- 1u4-1/27 1/2) (1((7 1/2).
i.e., the negative covariance (each U, and nT(T;({))) both have expectation 1/2).
We exactly characterize in Lemma 2.3 the difference 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
9

---

Published in Transactions on Machine Learning Research (05/2024)
Co := (aa((((nnf(([]])) where we abuse notation slightly to temporarily treat r as pushforward map over distributions. 5 We defer the proof of Lemma 2.3 to A Appendix B.
Lemma 2.3. Let m, n E N with n 2 m, where m is the generation length and n is the watermark key length. Define the decoder I by equation (1) and the alignoment cost d by equation (2). Let E,5' 1i.. Unil(E") with Y generate(f; m. P.I. Then almost surely for all i E [m]] and j E [n]] we have
Bid(Y,. d(Y;,s)) |M = Co . (1 - pPG Yx-1)) = 1o)((Y-
Summing the result of Lemma 2.3 over E [m] implies for any j E [n] that
F(d(Y. ((+1+++))n))) (i.m) Y] = Coma(Y).
Thus, we can upper bound the p-value output by detect in Lemma 2.4 using a standard concentration argument and taking a union bound over E [n]. We defer the proof of Lemma 2.4 to Appendix B. In fact, we actually prove a more general result for S m wherein we allow 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. Let m, N with n 2 m, where m is the generation length and n is the watermark key length. Define the decoder I by equation (1), aligument cost d by equation (2), and & by Algorithm with block size k k= m.
=. Let E ~ Uni with Y generate(E:n.p.)) and Y =Y Then almost surely
P(O(Y ( < (( (8) < 2n 2nexp( (xxp(-<CCa(Y)12))
Lemma 2.4 implies that with high probability the value of the lest statistic on watermarked texl 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 detect, the lemma implics 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-fret watermarkod text (i.c., n = 20(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, rocall the computational complexity of detection scales lincarly with n, which practice may be a more relevant limitation than the statistical power of the watermark. 6
2.4.1 Robustness to substitutions, insertions and deletions
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 ā 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 numerical constant to the watermark potential of the text) due to token substitations. We defer the proof of Lemma 2.5 to Appendix B.
Lemma 2.5. Let m. E N with n 2 m, where m is the generation length and n is the watermark key length. Define the decoder I by equation (1), alignment cost d by equation (2), and & by Algorithm 3 with k = m. Let E std. Unif(E") with Y = generate(E; m, m,,, P,I)) and let Y E vm be conditionally independent of & and g' given Y. Define
len(y)
a(y.9)= len(y)
1 T. (1 p(ys (x-1)) 189 + 7
N
Then almost surely
P(O E') s (( Y, X, < 2n expexp( 2nxxp(-kCfa(y) 1/22))
Note that Co Var(Unif([O, IJ)) + (1) oy()+ Note that both detect and the test. statistic (Algorithm 3) are easily parallelizesble.
10

---

Published in Transactions on Machine Learning Research (05/2024)
Lemma 2.5 implics 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 lokens will exhibit a small negalive 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 y in Definition 3 assigns a cost to each insertion and deletion operation when aligning the tokens y with the sequence &, while the base alignment cost do defines the quality of the alignment via a cost function over substitutions. In practice, we drop the minimizations over y' E V and s' & E in the second and third cases respectively of the definition; we include them here to make our subsequent theoretical analysis cleaner.
Definition 3. (Levenshtein cost) Let y E R and do V x E + R. For y E V and & E", define the Levenshtein cost d, V x E - R by
(v2: E2.) do E1)
(v) == min
(v. E2.) + mingev (v', E1) +
dy222 E) + mingrez (o {¹) + 7
with dy. (u, y y -en(y) & is empty and vice versa (as base cases). .
Redefining the test statistic á using d, as the alignment cost do from equation (2) ensures detect is robust not only to substituting tokens, but also inscrting and delcting tokens from watermarked text, as we show in Lemma 2.6. We defer the proof of Lemina 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 the minimum number of insertion and/or deletion operations needed to transform one string into the other (scc Lemma B.2).
Definition 4. (odit distance) For y. V", define the edit distance by
V1 deau (3. 17) 1 min/dedit (12. D) deaut (y, D2.)) 31 # D1.
dedia (B2: T2:)
with deait (y, 9) = =yn(yy) if y is empty and vice versa.
Lemma 2.6. Let n. E N with n 2 m, where m is the generation length and is the watermark key length. Define the decoder I by equation (1), alignment cost d = dy with do from equation (2) and r > 1/2, and & by Algorillmm 3 using block size k S m that dávides evenly into m. Let E, i.i.d Unif(E")) with Y = generate(E;m. m,p, p,1"). Let Y E ym be conditionally independent of & and e' given Y, with dedi (Y,Y) em. Then almost surely
P((((, S ((.5)((88)))) (1,0),,7 (on22)))) - 72))/12)
We prove the result by showing there must exist a length k substring of the corrupted text Y within edit distance ke 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 sk of an original blook watermarked text blows up combinatorially with E. To ensure we can detect the watermark, the result implies we must set 7 = R(1/s), which means Admittedly, our analysis is not
our bound the expected p-value is vacuous as soon as 221 tight; for example, as preview of the experimental results to come, in practice we find smaller values of y (i.e., 7 1) to perform significantly better. However, one takeaway from the result is that using block size & < 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 & divides evenly into m is an artifact of our analysis and not important practice.
For y E V (resp., & E E*), we let M1el(y)+1 (resp., (1en(E)+1) denote the empty string/sequence.
11

---

Published in Transactions on Machine Learning Research (05/2024)
2.4.2 What we in practice
In practice, to reduce overhead both generate and detect, we use a single random permutation" instead of a full sequence, i.e, we let म; = a for all E [n] for a ~ Unif(T). Recall Theorem 1 makes no assurnttion about the distribution of the permutations; thus, the watermark is still distortion-free. Also, for the test statistic, find using
len(y)
d(y, (u, m)) = Σ 14s - (T=;
(3)
as the aligument cost performs better empirically than the aligument cost in equation (2). To reiterate, the output of detect is a valid p-value irrespective the test statistic we use.
Hencoforth, we refer to this version of the watermarking strategy as ITS, and we refer the corresponding Levenshtein version as ITS-edit, wherein we define the base alignment cost da by equation (3) and use the following simplified notion of Levenshtein cost:
Definition 5. (simple Levenshtein cost) Let E R and do V x + R. For y E V and & E", define the alignment cost function d, V x E + by
(12, E2.) + do do(
(v. = min (v. E2. +9
(12., {) +,,-
with (v, (u, y 7 -len(y) if & is empty and vice versa (as base cases). 9
In summary, for 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 [0, x II, where recall n is the length of the watermark key sequence. Mcanwhile, ITS-edit differs from ITS only in that we define the test statistic using the Levenshtein cost from Definition with the base cost again from equation (3).
2.5 Watermarking via exponential minimum sampling
Aaronson (2023) proposes mapping variables [0, 1J to tokens in the vocabulary [N] using exponential minimum sampling to generate watermarked text. Whereas Aaronson (2023) proposes the use of distortion- exponential minimum sampling to implement inducing hashes much like Kirchenbauer et al. (2023), corresponding test statistic) enables an alternative the decoder in generate, which (after defining suitable distortion-fie free and robust watermarking strategy to inverse transform sampling. In particular, for & E [0, 1] =: E and E A([N), define the decoder by
I(( == arg min - log(Ei)/m(i). sE[N]
(4)
We show this decoder distortion-fres free in Theorem 2, whose proof we defer Appendix C.
Theorem 2. Define the decoder r by equation (4) and let & Unif([0,, 1] Then I is distortion-free with respect to g.
For the sake of analysis, we define the alignment cost as a slight variation of the proposal of Aaronson (2023) (see Section 2.5.2) by
len(y)
d(y. = Σ
log Eayyer
9Iu principle, with single random permutation the permuted token indices of both watermarked and nonwatermarked text longer conditionally independent of each other, and the results of Lemmas 2.4, 2.5 and 2.6 longer apply. However, in practice we obscrve degradation in statistical power. Also, irrespective of the lemmas, the p-values from detect still valid by construction.
Far y E V (resp., & E*), we let 11e((y)+1: (resp., (1sn(()+1) denote the empty string/sequence.
12

---

Published in Transactions on Machine Learning Research (05/2024)
again defining the test statistic 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.
Lemma 2.7. Lel n E N. Define I by equation (4) and d by equation (5). Let E, 444 Unil(=") with
Y generate n, p, D). Then almost surely for all i E [n] we have
CI)(Y;: d(Y.,s)) Y = -1 11p Ys-1) = aYY
Summing the result of Lemma 2.7 over E [m]] implies for any j E [m] that
E(d(Y,
d(:m)imm) Y ma((Y)
Thus, defining the test statistic by Algorithm 3 with respect the alignment cost from Eqn (5), we can again upper bound the p-value output by detect in Lemma 2.8 using standard concentration argument and taking a union bound over j E [n]. We defer the proof of Lemma 2.8 to Appendix C. Once again, we actually prove more general result that allows Y to be any length k subsequence Y.
Lemma 2.8. Let m, n E N with n 2 m. Define I by equation (4), by equation (5), and & by Algorithm with k m. Let E f.ddd Unif(E") with Y generate({;n. n. and Y =Y. Then almost surely
P(o(Y, E¹) S ( ( F)= S 2nexp (aoxp-mmm(fiinn (-min(maaY)9//8 (8)
2.5.1 Robustness to corruptions
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 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, 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.
2.5.2 What we in practice
As in the case of ITS, in practice we find using a slight variation of the alignment cost equation (5) performs better. Namely, following the prescription of Aaronson (2023), we modify the previous alignment cost to instead be
d(y. () = Σ log(1 - -.i
(6)
Henceforth, we refer to this version of the watermarking stratogy as EXP, and we refer to the corresponding Levenshtein version wherein we define the base alignment cost dy by equation (6) as EXP-edit.
In summary, for 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 E", where recall n is the length of the watermark key sequence and [0, 1] Mcanwhile, EXP-edit differs from EXP only in that we define the test statistic using the Levenshtein cost from Definition with the base cost again from equation (6).
3 Experimental results
We empirically validate the statistical power of our watermarking strategies (i.e., ITS, ITS-edit, EXP, and EXP-edit) via experiments with the OPT-1.3B (Zhang al., 2022) and I.AMMA7BB (Touvron et al., 2023)
13

---

Published in Transactions on Machine Learning Research (05/2024)
models. 10 We run experiments using generate rather than shift-generate, mainly for the sake of re- producibility; recall however that this choice has no impact on the p-values we report. We test for all watermarks using block size & (in Algorithm 3) equal to the length m of the text. Following the method- ology of Kirchenbauer et al. (2023), we generate watermarked text contimuttoos of prompts sampled from the news-like subset of the C4 dataset (Raffel et al., 2020). 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." 11
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 Taori et al. (2023), 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- property in practice.
In all our experiments exceptt for Experiment 2, where the control variable is hyperparameter that is unique to our watermarks we also replicate the watermark of Kirchenbauer et al. (2023) a baseline, setting the greenlist fraction 7 0.25 and varying the logit bias 6 E {1.0, 2.0}. We respectively refer to these versions of their watermark as KGW-1.0 and KGW-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. (2023) report that even the weakest version we employ with ā = 1.0 and y = 0.25 typically increases perplexity by 5-1%)..
In their work, Kirchenbauer et al. (2023) report approximate p-values which they obtaín from computing the 2-score of certain test statistic. To ensure fair comparison, use detect (with T 5000) to report p-values for all watermarks:12 in the case of KGW-1.0 and KGW-2.0, we run 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 times for each prompt-as as we originally prescribe in 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 detect, which gives a proper p-value with respect to the null hypothesis that the text is an original completion from the datasct. For reference, we include the full pscudocode for this modified version of 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 [0, 1].
We defer further details regarding our experimental protocol to Appendix D.
3.1 Varying text and watermark key length
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 7 = 0.4 for ITS-edit and y = 0.0 for EXP-edit (see Appendix D.4 for the details of tuning 7). Our ITS watermarks slightly outperform KGW-1.0 while our EXP watermarks slightly
We will also at times collectively refer to ITS and ITS-edit as the ITS watermarks and/or strategies and EXP and EXP-edit as the EXP watermarks and/or stratogics. The median p-value correspouds the significance level (i..,, Type error rate) at which the power of our watermark detector least. 0.5.
1hss setting of T means we never report p-values less than 1/5000 (L.e., 0.0002) in any of our experiments.
14

---

Published in Transactions on Machine Learning Research (05/2024)
EXP EXP-adit
EXP EXP-edit
ITS edit
ITS edit
KOW-1.0
KGW-10
KOW-22.0
KOW-2
Medien pedien powelue
Medien powelue
0.6
0.6
0.2
0.2
longth
longth
(a) OPT-1.3B
(b) ILaMA-7B
Figure 2: Median p-value of watermarked text relative to varying the text length m, for OPT-1.3B and LLaMA-7B models. Our watermark strategies are competitive with those Kirchenbauer et al. (2023), despite the fact that they distort the text distribution generate watermarked text whereas we do not.
outperform KGW-2.0, despite the fact that KGW-1.0 and KGW-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 comparably low modian p-value. One conceivable advantage of the ITS watermarks over the EXP watermarks is that they have comparatively less overhead: the watermark key for EXP and EXP-edit t is sequence of vectors in [0, 1) where recall N is the size of the vocabulary, while for ITS and ITS-edit it is simply a sequence of n numbers in [0, 1]. All watermarking strategies perform worse on LLaMA-7B than OPT-1.3B, due to the fact that -LB typically produces lower entropy text than OPT-1.3B. Due to the discrete nature of the Lest statistic of Kirchenbauer et al. (2023), i.e., the number of tokens in the text belonging to a "greenlist" versus a "redlist", the median p-values for the KGW-1.0 and KGW-2.0 watermarks are occasionally unstable, particularly for small values of m.
We vary the length n of the watermark key sequence & in Figure 3 for different lengths m of watermarked text from the ITS and EXP watermarks respectively. Recall corresponds to the total number of tokens 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.
3.2 Robustness to corruption and paraphrasing
We now proceed to evaluate the robustness of our watermark strategies various forms of corruption and paraphrasing. We focus on comparing our strongest watermarks (EXP and EXP-edit) against KGW-2.0, deferring results for all other watermarks to Appendix D.5. As larger increases the computational overhead of computing test statistics and the effect of larger n statistical power is mild (as shown in Figure 3), we run all experiments with 256, which in any case is sufficiently large to ensure the watermarked text across all experiments is distortion-free. Decreasing the insertion /deeeeiiooooo penalty 7 improves robustness (at least up to a point) but hurts the statistical power of the ITS-edit and EXP-edit watermarks for larger n, since reducing the penalizer for edits effectively increases the number of candidate alignments under consideration. We run ITS-edit and EXP-edit with the same choices of y as in the previous section. We defer the details of tuning 7 to Appendix D.4.
15

---

3500 Published in Transactions on Machine Learning Research (05/2024)
0.035
30
m 40
0.150
0.025
0.125
0.020
0.100
Median
0.015
0.075
0.20
0.050
0.005
0.025
0.000
0.000
Watermark key length (n)
Watermark key length (n)
(a) OPT-1.3B: ITS (solid) and ITS-edit (dashed)
(b) LLaMA-7B: ITS (solid) and ITS-edit (dashed)
0.200
10
12
18
0.06
valuee
0.100
0.04
0.075
0.050
0.025
0.00
0.000
500
1000
1500
2000
2500
3000
3500
4000
500
1000
1500
2000
2500
3000
4000
Watermark key length (n)
Watermark key length In)
OPT-1.3B EXP (solid) and EXP-edit (dashed)
(d) LLaMA-7B: EXP (solid) and EXP-edit (dashed)
Figure 3: Median p-value of watermarked text for varying the watermark key length Across all watermarks for both the OPT-1.3B and LLaMA-7B models, the median p-values grow lincarly with but decay rapidly with increasing text length m.
16

---

Published in Transactions on Machine Learning Research (05/2024)
EXP
0.5
EXP-edit
EXP-edit
Medien Weddien--reloe prwelue
Medien povelue
0.2
0.1
0.0
0.0
substittiions
(a) OPT-1.3B
(b) ILaMA-7B
Figure 4: Median p-value of watermarked text relative to the fraction of substitution errors, for OPT-1.3B and LLaMA-7B models with m 35. Both versions the EXP watermark significantly outperform KGW-2.0, again despite KGW-2.0 distorting the text distribution.
We vary the fraction of substituted tokens in Figure 4, and vary the fraction of inserted and deleted tokens in Figures 5 and 6 respectively. For the insertion experiment, 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 EXP and EXP-edit watermarks are comparably robust to substitution errors, but the latter is far more robust to insertion and deletion errors.
We compare watermarks against the most robust version of KGW-2.0, in the sense that 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 substiluting any one of the previous & tokens will break the watermark signal in particular token, and thus the statistical power of their watermark will be worse than what we report in our experiments.
Finally, Figures and we implement a "roundtrip translation" attack, wherein we atlempt 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 machine translation model (dctails in Appendix D.2). We include representative example of the original and (re-)translated texts in Figure 7. Using Russian is a noticeably more effective attack than French: none of the watermarks aside from EXP-edit are able to reliably detect watermarked text with < 0.05 irrespective of m. In fact, for Russian the power of both EXP and KGW-2.0 stagnates (or even diminishes) with increasing text length, perhaps due to the inherent ambiguity translating longer texts.
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 EXP, which is substantially less robust to insertion and deletion errors than EXP-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 allacks, since in practice users would presumably not publish such examples. more generally, different forms of automated paraphrasing- detection than those we employed. We publish the full set of watermarked generations for each watermarking strategy, along with their (roundtrip) translations, part of our code release.
also possible that using different machine translation models or
be far more effective evading watermark
17

---

Published in Transactions on Machine Learning Research (05/2024)
0.35
EXP edit
FXP edit KBW
KSW
0.25
Medien poalue
0.15
0.1
0.09
0.1
0.
0.3
0.4
0.5
0.6
0.7
0.1
0.
0.3
0.4
0.5
0.6
0,7
Fraction
Fraction
(a) OPT-1.3B
(b) LLaMA-7B
Figure 5: Modian valuu of watermarked text relative the fraction of insertion errors, for OPT-1.3B and LLaMA-7B models with 35. EXP-edit is far the most robust.
EXP cdit
EXP cdit
KGW-2.0
KGW-2.0
0.10
Modian
0.05
0.1
0.2
0.3
0.4
0.5
0.6
0.1
0.2
0.3
0.4
0.5
0.6
Fraction deletions
Fraction
(a) OPT-1.3B
(b) LLaMA-7B
Figure 6: Median p-value of watermarked text relative the fraction of deletion errors, for OPT-1.3B and LLaMA-7B models with 35. EXP-edit is again the most robust.
18

---

Published in Transactions on Machine Learning Research (05/2024)
dependent on the private sector. That helps them preserve the advantages their industry has govemment healthcare contracting, decreasing
extinction govermmen's abilit regulate the private sector's cost-driving practices. Hence, his proposal was not was not designed to prevent socialized medicine. It's designed to make harder and more expersive than ever dependency and the social good. you want to prevent socialized medicine, go for the Republicans' heads, not bureaucrats' feet. the meantime, though, the Republican plan redefine "govem
original text
socialized medicine. That will help keep democrats out
making them soft
dépendant
industrie gouvemement, tout en diminuant jusqu'à la quasi-exinciio la capacité du gouvemement à réglementer les pratiques de condulte des couts du secteur privé. Il est congu pour rendre plus difficile et plus cher jamais d'obtenir médecine socialisée Cela aidera garder les démocrates hors pouvoir en faisant paraltre doux sur dépendance blen social. Si vous voulez empêcher la médecine socialisée, optez las têtes des républicains, les pieds des bureaucrates attendant, cependant, plan républicain redéfinir gouvemement
side préserver avantages
contrats
santé
French translation
helps them preserve the benefits their industry governmett health care contracts, while reducing the govemment's ability to regulate private sector cost-maragemert practices to near extinction. It's designed make it harder and more expensive than to get socialized medicine help keep addiction and social good. If you want provent socialized medicine, opt for the heads of Republicans, not the feet of bureaucrats meantime, however, Republican plan redefine "the govemment.
roundtrip translation
out power by making look gentle
Figure 7: An illustrative example of roundtrip translation attack via French. Given the first 50 tokens of the roundtrip translation (highlighted in green, in addition to the closest matching snippets to these tokens from the original text), detect returns p s 0.0002.
EXP
EXP-edit
EXP-edit
KUW-2.0
0.4
KDWW22
0.15
Median preabue
0.3
0.05
0.1
30
15
20
25
30
80
30
10
20
25
30
40
45
30
length
length (m))
(a) OPT-1.3B
(b) LLaMA-7B
Figure Median p-value of watermarked text relative to the text length, after roundtrip translation via French, for OPT-1.3B and LLaMA-7B models with 35. EXP performs comparably to EXP-edit, indi- cating that the roundtrip translation attack tends to preserve at least some snippets of the original text.
19

---

Published in Transactions on Machine Learning Research (05/2024)
EXP
EXP
EXP-adit
0.35
EXP-edit
0.30
0.25
P-vauue
0.20
0.20
0.15
0.15
0.10
0.05
3.00
0.00
longth
longth (m)
(a) OPT-1.3B
(b) I.aMA-7B
Figure 9: Median p-value of watermarked text relative to the text length, after roundtrip translation via Russian, for OPT-1.3B and LLaMA-7B models with m 35. In contrast to French, EXP-edit noticeably outperforms EXP. Overall, the attack is noticeably more effective than using French.
3.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 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 EXP-edit and KGW-2.0 watermarks in Figure 10, as well as the p-values versus the watermark potential of the watermarked text in Figure 11. 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 stat istical power of our walermark is worse despite the responses typically being longer than in the previous experiments (i.e., Experiments 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-133B. Unlike the previous experiments, KGW-2.0 noticeably outperforms the EXP-edit watermark. Figure 11 indicates this difference in performance is largely due to the fact KGW-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.c., watermark potential multiplied by the number of tokens the response, account for the varying lengths of the responses) exceeds roughly 60, both watermarks tend to yield valuues 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 12 and 13.
Finally, recall the main distinguishing feature of our watermark compared to Kirchenbauer et al. (2023) and Aaronson (2023) 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 (2023) proposes by modifying the generate method of EXP obtain the vector & E [0, 1]. from sceding a random number generator using the previous l tokens instead of using the watermark key; we call this version EXP-hash. We
20

---

Published in Transactions on Machine Learning Research (05/2024)
140
60
120
30
60
20
40
10
0.4
(a) EXP-edit
(b) KGW-2.0
Figure 10: Histogram p-values of watermarked text from Alpaca-7B. KGW-2.0 noticeably better than EXP-edit, though again the results are strictly comparable KGW-2.0 is not distortion-free.
EXP-edit
EXP-edit
Matomaan patemtal (umnormalzod b04))
80
30
Count
20
20
0.6
2.0
Watermark (unnormaized)
(a) Scatterplot of vavuuuss.
(b) Histogram watermark potential.
Figure Watermark potential versus statistical power of EXP-edit versus KGW-2.0. KGW-2.0 noticeably distorts the text distribution, tending produce higher watermark potential text overall than the original language model (and consequently, EXP-edit).
21

---

Published in Transactions on Machine Learning Research (05/2024)
80
25
20
0.0
0.2
0.4
0.6
0.8
1.0
0.4
0.6
0.8
(a) EXP-edit
(b) KGW-2.0
Figure 12: Histogram of p-values of watermarked text after roundtrip translation French. KGW-2.0 outperforms EXP-edit, albeit by noticeably distorting the text distribution.
50
15
Count
30
30
30
0.0
0.4
0.5
0.8
10
0.0
0.2
0.4
0.5
0.8
1.0
(a) EXP-edit
(b) KGW-2.0
Figure 13: Histogram of p-values of watermarked text after roundtrip translation via Russian. XGW-2.0 again does significantly better than EXP-edit.
22

---

Published in Transactions on Machine Learning Research (05/2024)
the 20 the tite paper on watermarking language models:
1. Watermarking Deep Leerning Models: A Review
2. Understanding and Evaluating Wistemmkking Techniques for Neural Networks
"Understandnn Wstermerking Techniques for Language Modele"
Towards Unoblrusive and
Waternarking
Networks
2. Comprehensive Study on Watermarking for Language Models'
4. Gustomizable Witermarking for Neural Networks
3. "Wattrmakinng Techniques for Optimizing Language Models
5. Reverse Engineering Watermared Noural Networks
Understanding and Exploiting Watermarking Attacks Neural Notworks
8. "Inplementing Waternering for Language Model Optimization"
4. ' Survey of Vistemarknng Techniques for Language Models'
5. 'Explorin the Potential of Watormarking for Language Models"
7. Combatting Watermanking Attacks on Neural Networks
Watermaninng Strategies for Enhancing Language Models'
8. Customizable Watermariig for Neural Natworks
IIvestigating Possibi iiles Watermnking for Language Moditt"
9. Customizable Watermarking for Neural Networks
'Advanced Watermekknng Approechee Language
10. Customizable Watermarking Neural Networks
"Explooing the Watermarking Language Model Validatio"
11. Gustomizable Watermarking for Noural Networks
"Understanding the Beneftts Walsmanking for Language Model Ensemble"
12. Oustomizable Watermarking for Noural Networks
12 "Leversging Watermarking Techniques for Enhanncdd Language Model Performence'
Oustomizable Watermarking for Naural Networks
13 "Enhanding Language Models with Watermariin"
14. Customizable Watermarking for Noural Networks
14 "Evaiusting the impact of Watermarking Techniques on Languege Modele"
15. Customizable Watermarking for Neural Networks
15. 'Arelyzin the Feasibilit of Watermariing for Language Model Comparison"
16 "Expioring the Possibiities of Watermnning for Optimizing Language Models"
16. Customizable Watermarking for Neural Networks
17. "Explollnng Wetermariing Erhancc
Model Accuracy"
Neural Networks 18. Customizable Watermarking for Noural Networks
Customizable Watermarking
18. 'Avvantaees Using Watermarking for Validating Language Models' Promise Watermaniing for Evaluating Language Model Performancs
19. Customizable Watermarking for Noural Networks
(a) EXP-hash
(b) EXP
Figure 14: Example responses from Alpaca-7B to the prompt: "Give me ideas for the title of a paper on watermarking language models." We generate (a) by hashing the previous token to determine the inputs the EXP decoder, while (b) is a regular sample from our EXP strategy. Hashing causes the model to degenerate into repetition.
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 a newline character, and because this recurring token determines the next token, for k the lists degenerate into repetition (Figure 14).13
From inspection, hashing with A: > 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- distortion-freeness,, as there a direct trade-off between the likelihood of a hash collision and the robustness of the hash. In addition to Figure 14, we include more examples (for both k 1 and k 4) and different prompts in Appendix D.5.5 and our code release.
4 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. 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 lincarly with respect to the length of the watermark key sequence.
The core assumption underlying watermarking is that the LM provider and the watermark detector coor- dinate by sharing information in advance, c.g., a watermark key. Indeed, the main inherent limitation of watermarking is that the delector must trust the LM provider to faithfully apply the watermark when gen- erating text. A second limitation, which is not inherent to watermarking language models but does presently apply to all known watermarks, is that the LM provider cannot relcase 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 language model without degrading the quality of the model is an important direction for future work.
13eThe authors would like to pat themselves the back by drawing the reader's attention to the fact that the title of this paper not among those suggested by Alpaca-7B.
23

---

Published in Transactions on Machine Learning Research (05/2024)
4.1 Trade-offs among watermarks
Hashing-based watermarks (Aaronson, 2023; Kirchenbauer et al., 2023; Christ et al., 2023) incur a direct trade-off between the degree of distortion versus robustness: larger hash windows reduce distortion but hurt robustness. We avoid sacrificing distortion-freeness for robustness by choosing to formulate watermark detection sequence alignment problem; however, this design choice introduces new trade-off: the computational complexity of our watermark detection algorithms grows lincarly with the length of the watermark key sequence. In contrast, the complexities of the watermark detection algorithms of both Christ et al. (2023) and also Aaronson (2023) and Kirchenbauer et al. (2023) depend (in essence) only on the length of the imput text. Just as the watermark key length imposes a cap on both the total number of distortion- watermarked tokens the LM provider may generate for a single query as well as the expected total they can generale across multiple queries before reusing a part of the key sequence, the the window size imposes a cap the number of (distortion-free) tokens one can expect to generate using hashing- based watermark without incurring a hash collision. Whether this apparent tension between detection complexity, robustness and (approximate) distortion-freenn is due to fundamental trade-offs is an interesting open question.
To illustrate how these trado-offs manifest in practice, suppose an LM provider responds with m = 100 tokens to a sequence of T = 10 user queries (which may be adaptively chosen). Recall from Section 2.2 that we must set the key length n = w(m7²) to achieve approximate distortion-freent
using our watermarks,
where here mT² 10000; for 10000, the runtimes of our implementation of the test statistics for ITS, ITS-edit, EXP, EXP-edit are 0.004 + 0.0002, 0.60 + 0.01, 2.20 + 0.01 and 3.21 + 0.01 seconds respectively. 15
In order to achieve approximate distortion festortion-freeness using a bashing-based watermark in the same setting, the LM provider must set the window size k to be sufficiently large as a function of m and T. For example, Christ et al. (2023) argue that the probability of incurring the same sequence of tokens twice docays exponentially with the observed entropy of the token sequence (which will depend on the previous tokens); thus, they dynamically adjust the window size k during generation to ensure the observed entropy of the constituent tokens in the window is sufficiently large such that the probability of a hash collision with any of the other windows is negligible across all mT tokens. Specifically, letting h denote the expected observed per-token entropy (i.c., log- (og-probability). the typical window size for hashing-based watermark would need to be at least k x log in order to ensure approximate distortion-freeness in our setting. Concretely, in the setting of Section 3.3, we have ze 0.70 for Alpaca-7B, in which case such a hashing- based watermark would not be robust to replacing more than roughly 10% of watermarked tokens.
h
4.2 Recommendations in practice and combining watermarks
We conclude with some salient recommendations for practitioners aiming to watermark their deployed lan- guage models. First, though in principle the length of the watermark key sequence n which recall imposes cap the total number of distortion-fres watermarked tokens the LM provider can generate- caa grow (nearly) exponentially in the block size k of the test statistic while still enabling watermark detection from as few as le tokens, in practice we find that using a fairly small watermark key sequence (c.g., = -256) does not noticeably affect the quality of watermarked text (i.e., even when generating more than n tokens lotal) while allowing for fast detection and improved robustness. In settings where robustness is important (e.g., discouraging students from using a language model for homework assistance) we recommend practitioners use our EXP-edit watermark, as it is by far the most robust watermark of those we tested. Mcanwhile, in settings where throughput of detection is important (e.g., scrubbing synthetic text from a large train- ing corpus), recommend practitioners use our ITS watermark: its detection is essentially an instance of maximum inner-product scarch, a problem for which there exist various fast implementations and indexing structures (e.g., via vector databases).
We report average runtimes and the associated standard deviations across 5 calls on an Apple M2 Macbook Pro Laptop. We include benchnarking scripts with code release.
in principle, running detect requires rocomputing the test statistic for each resampled watermark key in order to obtain an exact p-valuc. However, approximate paluus with respect to some reference distribution of unwatermarked text, in which case we need only compute the single test statistic once (using the original watermark key) during watermark detection (Algarithm 5).
discuss in Scction D and Appendix D.3, can avoid this recomputation and still obtain
24

---

Published in Transactions on Machine Learning Research (05/2024)
Finally, remark that for certain hashing-based watermarks can combine watermark with the hashing-based watermark to generate watermarked text that is detectable using either of the two correspond- ing watermark detection algorithms. For example, we can use the bashing-based watermark of Kirchenbauer et al. (2023). which biases the distribution of the next token by upweighting certain logits over others, to determine the distribution of the next loken and then use our watermarks to sample from this next. token distribution. One can then later determine which detection procedure to run for a collection of putative watermarked text depending on whether throughput or robustness is a higher priority. Similarly, we can combine our watermarks with the watermark of Christ et al. (2023) by alternating tokens between the termarks (and only hashing the alternate tokens). The resulting watermarked text will be approximately distortion-free since both watermarks are approximately distortion-free. One can choose between the two detection procedures to optimize precision versus recall in adversarial settings; in particular, the watermark of Christ et al. (2023) is hard to spoof (due to its multi-query undetectability guarantee) while our water- marks are harder to remove (due to our robustness guarantecs). Exploring such combinations of watermarks with complementary strengths is an exciting direction for future work.
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
Scott Aaronson. 'Reform' AI Alignment with Scott Aaronson. AXRP the AT X-risk Rescarch Podcast, 2023. / http:///a..a../poo////////////// html.
URL
Sahar Abdelnabi and Mario Fritz. Adversarial watermarking transformer: Towards tracing text provenance with data hiding. In IEEE Symposium Security and Privacy, 2021.
Mikhail Atallah, Victor Raskin, Michael Crogan, Christian Hempelmann, Florian Kerschbaum, Dina Mo- hamed, and Sanket Naik. Natural language watermarking: Design, analysis, and proof-of-concept im- plementation. In Information Hiding: 4th International Workshop, IH 2001 Pittsburgh, PA, USA, April 25 27, 2001 Proceedings 4, pp. 185 200. Springer, 2001.
Diane Bartz and Krystal Hu. OpenAI, Google, others pledge to watermark AI content for safety, White House says. gponai-google-on gggoogl--thhes-see wwweerr--peeee-waaee
reuters. wwtpe/cco//eeeeeeeeeeeeeeeeeecee com/technology/ Reuters, 2023. URL attps://www. https://www.reuteers.
aeai-contett-seee saal--ottettssfet---lliee saiety--hite--ousee 2023-07-21.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in Neural Information Processing Systems 39, 33:1877-1901, 2020.
Miranda Christ, Sam Gunn, and Or Zamir. Undetectable watermarks for language models. arXiv preprinl arXiv:2306.091 2023.
Falcon Dai and Zheng Cai. Towards near-inperceptible steganographic text. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pp. 4303-4308, 2019.
Gustav Elfving, Garrelt BirkhofT, and Richard von Mises. Vol. probability and statistics, General. In Selected Papers of Richard von Mises, American Mathematical Society, 1966.
Xuanli He, Qiongkai Xu, Lingjuan Lyu, Fangzhao Wu, and Chenguang Wang. Protecting intellectual prop- erty of language generation APIs with lexical watermark. In Proceedings of the Thirty-Sizth AAAI Con- ference on Artificial Intelligence, 2022a.
25

---

Published in Transactions on Machine Learning Research (05/2024)
Xuanli He, Qiongkai Xu, Yi Zeng, Lingjuan Lyu, Fangzhao Wu, Jiwei Li, and Ruoxi Jia. Cater: Intellectual property protection on text generation apis via conditional watermarks. Tn Advances in Neural Information Processing Systems 35, 2022b.
Ganesh Jawahar, Muhammad Abdul-Mageed, and VS Laks Takshmanan. Automatic detection of machine generated text: A critical survey, In International Conference on Computational Linguistics, 2020.
Nurul Shamimi Kamaruddin, Amirrudin Kamsin, Lip Yee Por, and Hameodur Rahman. A review of text watermarking: theory, methods, and applications. IBEE Access, 2018.
S Katzenbeisser and FAP Petitcolas. Digital watermarking. Artech House, London, 2:2, 2000.
John Kirchenbauer, Jonas Geiping, Yuxin Wen, Jonathan Katz, lan Miers, and Tom Goldstein. A watermark for large language models. arXiv preprint arXi::200111020 2023.
Eric Mitchell, Yoonho Lee, Alexander Khazatsky, Christopher D Manning, and Chelsea Finn. Detectgpt: Zero-shot machine-generated text detection using probability curvature. ar preprint or Xii:2301.11300,
2023.
George Papandreou and Alan Loddon Yuille. Perturb-and-map random fields: Using discrete optimization to learn and sample from energy models. 2011 International Conference Computer Vision, pp. 193 -20,, 2011.
Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. The Journal of Machine Learning Research, 21(1):5485-555) 2020.
Stefano Giovanni Rizzo, Flavio Bertini, and Danilo Montesi. Fine-grain watermarking for intellectual prop- erty protection. EURASIP Journal on Information Security, 2019.
Jiaming Shen, Heng Ji, and Jiawei Han. Near-imperceptible neural linguistic steganography via self-adjusting arithmetic coding. In Proceedings of Empirical Methods for Natural Language Processing, pp. 903-313, 2020.
Rohan Taori, Ishaan Gulrajani, Tianyi Zhang, Yann Dubois, Xuechen Li, Carlos Guestrin, Percy Liang, and Tatsunori B. Hashimoto. Stanford alpaca: An instruction-following Ilama model. https://gi highh........ com/ 2023.
Batts--aab/stanford.a.
Jörg Tiedemann and Santhosh Thottingal. OPUS-MT - Building open translation services for the World. In Proceedings of the 22nd Annual Conference of the European Association for Machine Translation, 2020.
Jörg Tiedemann, Mikko Aulamo, Daria Bakshandaeva, Michele Boggia, Stig-Arne Grönroos, Tommi Niem- inen, Alessandro Raganato, Yves Scherrer, Raul Vazquez, and Sami Virpioja. Democratizing machine translation with opus-mtt arXiv preprint wrXiv:2212.01933 2022.
Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al. Llama: Open and efficient foundation language models. arXiv preprint arXim:2302.1900 2023.
Honai Ueoka, Yugo Murawaki, and Sadao Kurohashi. Frustratingly easy edit- linguistic steganography with masked language model. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, 2021.
Ashish Venugopal, Jakob Uszkoreit, David Talbot, Franz J Och, and Juri Ganitkevitch. Watermarking the outputs of structured prediction with an application in statistical machine translation. In Proceedings of Empirical Methods for Natural Language Processing, 2011.
James Vincent. Al-gencrated answers temporarily banned on coding Q&A site Stack
httpe/rgg...o//222////////999999 chatgpt-ai-en -enrt--aeegeerrted--eee -tr--geerrreeedseeerrrrr-- hrapueesttttpppprayyyyaaacccceee -mme
Overflow. The Verge, 2022. URL http::/wwwwttheereeee
26

---

Published in Transactions on Machine Learning Research (05/2024)
Martin J. Wainwright. High-Dimensional Statistics: A Non-Asymptotic Vieupoint. Cambridge University Press, 2019.
Xi Yang, Jie Zhang, Kejiang Chen, Weiming Zhang, Zehua Ma, Feng Wang, and Nenghai Yu. Tracing text provenance via context-aware lexical substitution. In Proceedings of the Thirty Sixth AAAI Conference on Artificial Intelligence, 2022.
Susan Zhang, Stephen Roller, Naman Goyal, Mikel Artetxe, Moya Chen, Shuohui Chen, Christopher Dewan, Mona Diab, Xian Li, Xi Victoria Lin, et al. Opt: Open pre-trained transformer language models. anXiv preprint ar Xiv: 01068, 2022.
Xuandong Zhao, Yu-Xiang Wang, and Loi Li. Protecting language generation models via invisible water- marking. aivi preprint or Xww:2302.03122 2023.
Zachary Ziegler, Yuntian Deng, and Alexander M Rush. Neural linguistic steganography. In Proceedings of Empirical Methods for Natural Language Processing, pp. 1210-1215, 2019.
A Proof of Lemma 2.2
Proof. To show the claim, we first lower bound the probability that = Y', particular,
P(Y Y-) Σ P(Y = y)P( y)
Σ P(Y = v) II p(ys M6--1)
(E(m)
Σ P(Y v) II (1 (1 plu/ B+--1)))
(E(m)
Σ P(Y = 1) exp
-c
1 - plye y1--1)
BEV.
mE|m]
2 |exp (- -mmo 1(Y y E v*),,
where (x) follows from exp(-cr) 1 - for 0 < < cx) It then follows immodiately that we can bound the total variation distance between the joint distributions of (Y,E) and (Y',E) by
Drv((Y,E))l('', ()) < +
< 1 eexp (-ema VHH
Observe for any event A that
(ry ()) P(())) P((Y' A),
and thus, combining the previous two displays, we have
P((Y,)) E A) + F(Y'' .0) $ A) P((, E A) + E(()E) & A) D
2 E (exp (-cma(Y) 1(Y v*)].
The desired result thus follows from letting A be the event that h predicts -1.
B Analysis of inverse transform sampling
We first introd the following supporting lemma. Recall Co Var()(Uni(((N])) for 17(1) (i-1)/(N-))
27

---

Published in Transactions on Machine Learning Research (05/2024)
Lemma B.1. Let μ E A(NN). Let (U, Unif([O,1]) x Unif(II) and Y I((U,x),p)) Then Co ())(U.n(((T)) 1- almost surely.
Proof. We first characterize the conditional distribution of ा given Y and the conditional distribution of U given both π and Y, where recall and Y are discrete. Applying Bayes' formula and Theorem 1, we have
P(( Y) P(Y T))((T (+) P()) = P(T).
(7)
P(Y)
P(Y)
Also, defining the interval
I(,+)):= Iu(ty =(1) < xx(Y))), (v) S (()))),,
for any interval I [0, we have
(a) P(U E T
E I=) (())((T)
( [INI(Y,)) @ III(Y
(8)
H(Y)
[I(YT))
where (a) follows from Bayes' formula and the independence of U and (b) follows from the definition (1) of the decoder D; and (c) follows from T(Y,x) c [0,1] having width equal to pYY). The displays (7) and (8)
respectively imply æ Y ~ Uni((1I) and U n. Y ~ Unif(I(X, from which it follows that
EU [Y)] = E p(ly =(v) < +({))) m)
x,a())
2
(m(M) 1) (1- m(Y)
n n-1
= 1/22+ (n()(()) 1/2) (1 - (1-xx)))
By symmetry, we have E[U]- = E[](((())) 1/2, the former because P(Y U) P for any U and the latter because recall Y is uniform over II. Thus, marginalizing the preceding display over iTY) gives
Cov(U, (()()) Y) = [(U - 1/2) (1(x - |
(1 Var |Y).
from which the desired result follows immediately from recalling (Y) Y ~ Unif([N]) and the definition of the constant Co-
B.1 Proof of Lemma 2.3
Proof. Recall by definition
d(Y,,E,)
(y(m(())) 1/2),
where (as in the proof of Lemma B.1) we have E(U; Y = B/n(T, (Yi) |Y] = 1/2.. Lemma B.1 thus implies
EEd(YY,, Ei) YY = -Co (1 p(y, Yx=1)), while trivially REd(Y,, Eg) Y] = 0 as Y and g are independent. The result follows immediately.
B.2 Proof of Lemma 2.4
We prove the following more general result, from which Lemma 2.4 follows as a corollary.
Lemma B.2. Let m,n n E N with n 2 m, where m is the generation length and n is the watermark key length. Define the decoder by equation (1), alignment score by equation (2), and & by Algorithmm with block size k S m. Let g idd. Unif(E") with Y generate(E; n, P,I)). Let Y be a substring of Y of length at least that is conditionally independent of & and g given Y, i.e., Y = Yr+ir++ for 2 k. Then for â 6= P(Y Ys-1), almost surely
p(Y,
P(O(Ý (( VY,Y en (-KCfa² /2).
28

---

Published in Transactions on Machine Learning Research (05/2024)
Proof. Recall by definition
len(y)
d(y. (T) =- Σ (u - 1/2)- (17(m(31)) 1/2), i=1
(9)
Lemma 2.3 and the conditional independence of 7 and & given Y imply for any j E [y] that
Eld(Y 5(+11++))n)) |, - -Edd(Eidsssss S7+10++2)) Y, Y, = kCaā.
Each summand in equation (9) lies between - -1/4 and 1/4, and also (U; n2) is conditionally independent of U- and T- given Y. Thus, Hoeffding's inequality (Wainwright, 2019, Proposition 2.5) implics for j [n]] that
IP (d(F, (6-1948%%) & d(Y, (r+1i++)) |x,Y)
$ P (d(Y, E15) - Bid(Y, (1mm 2 kCoa/2 Y,
+ ((H1()))))+m - E//11tm)) 2 kChā/2 r,
2exp (-mCBa²/2)
Recalling the definition of the test statistic via Algorithm 3, the main claim then follows from taking a union bound over all j [n].
B.3 Proof of Lemma 2.5
Proof. We begin with the following observation for single token.
Observation B.1. Let P E A([N). Let (U, ~ Unif([O, 1J) x Unif(lI) and Y I((U, Let Ý [N] be conditionally independent of (U, given Y. I # Y, then almost surely
Cov(U,n(T(Y)) Y
Cov(U, (YY))
Proof of Observation B.1. Observe the conditional distribution of (Y) given Y uniform over [*]))
Let X be a random variable that is equal to nYT((Y) with probability 1/N and otherwise equal to ({(()). Observe is independent. Y and thus also U by assumption in particular, (N - -1XX+ +1 Y Uni(([N])
irrespective of the value of Y. The claim thus follows from rearranging terms in the equality
0 Cov(U, x Y2Ý)= (or(U, (Y,)) N (or(U.n(z())) (Y |,,,),
Lemma 2.3 and Observation B.1 together imply for any j E [n] that
Eld(Ý, ( y (( fi.) =Cn
i.e., by adding the two results together using Observation B.1 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
(d(V (4154m) S d(ÿ, Ei:m)
m 12,5)
< P (d(E, Elm) (d()) - ET f1mm) 2 mā(Y, 8),,8122111111
+ (E[d(L, (id((YE++11tt))) ((+1gtm))))) 2 mā(Y, 1Y,))
< 2exp (-mCka(Y, ()2/22
Recalling the definition of the test statistic via Algorithm 3, the main claim then follows from taking a union bound all j [m] and recalling l m by assumption.
29

---

Published in Transactions on Machine Learning Research (05/2024)
B.4 Proof of Lemma 2.6
Proof. We begin with the following useful facts about edit distance. Throughout, let S(y) denote the set of substrings of string E V", including the empty string.
Observation B.2. Let y. U.VEV E.. Then dedu y) is the length of the smallest sequence of insertion and/ or deletion operalions to oblain y from y.
Proof of Observation B.2. We proceed via induction on the sum len(y) + len(y). The base case where y and y are both empty is trivial. Now suppose the claim holds all strings whose lengths sum to at most len(y) + (y) 1. Recalling the definition of dedit (Definition 4), there are three cases.
First, suppose dodit D) = deai (y2:, T2.)). Then by induction there exists a sequence of deai (v. D) insertion and/or deletion operations to obtain V2: from 92: Because V1, the same sequence suffices to obtain y from and thus the claim follows.
Second, suppose dedit 50 = deait (V2:, M) Again by induction, there exists a sequence dndit (v. D) insertion and/or deletion operations obtain y from y2.- It follows immediately (i.e., by first deleting yı) there exists a sequence of (y,ic ?7 such operations obtain ý from y, and so the claim holds.
The third case follows by symmetry with the second case.
Obscrvation B.3. Let y. J. E V* Then for any < len(y), we have
deda (v. 0) min dudit (y:r, v') + min dedit (Vr-1:: v)).
of yES(
v'ES(w)
Proof of Observalion B.3. Observation B.2 implies there exists sequence of clatie (v, D) insertion and/or deletion operations to obtain y from y. We may partition this sequence of operations into sequences based respectively on whether they occur Vor yr+1. Let Upre be the result of performing the first sequence of operations on Y:r and let Vsut be the result of performing the second sequence of operations on Vr+1:- Then ÿ is the concatenation of Uprc and Ysuf, and so the claim follows from the fact that
dean (v, 7) dedit (y.r, Upre) dedit (U++1:> Nout)
> min deau deau v²) + min dedu (yr-1:: v/). s'S(())
V'ES(W)
Observation B.4. Let y. U. V and E E*. Then d, (v,E) S ydea (v. D) + (..E).
then have y Now suppose dean (v. 1, and let i be the first index such that yi # D:- Then, unrolling the recursive definition of d, (Fr, En:); there must exist c E R and an index j such that both d. {) c + (D.. Eg) and dy {) s c + d, (3/.) E..).
Proof of Observation B.4. The case dedn (v. 77) is trivial
Morcover, from the definition of edit distance, either yi+1: = Vi: or vice versa.
We claim d, Ey:) S (T Ey:) + 7. If yit1: = Vs. then the claim obtains as (ve. S (1i+ Ex.) + min (') + E'Es
- (y1+1: Ey: +7
= (T:: Ej:) + +7,
with (+) following from the fact that do 5¹) = for g' = (1/2, π) irrespective ys and n.
Otherwise, if Wt: Metis then from unrolling the recursive definition of d., (Ti. Ey:) there must exist some index j 2 j such that either
dr Eg.) (1 + + min (T., + Σ + min do .x)
E'e
Wev
3st<s'
30

---

Published in Transactions on Machine Learning Research (05/2024)
d (Ta. Epi) = (U++1: Ep) +
7 -+ min .o(v/Ee))
jStej' v'EV
In the first case, we have y + mingrez eo (o( > since 7 > 1/2 by assumplion, and so the claim follows as
(yte, - (vn: Ey:)) +
E
7 min (V)
N'EV
iSPcj
=d,(ū++1,5)+++
Σ
7+ min doly/ v'EV
jSpey
< (Ti:
In the second case, we have do(ū)) the claim follows
(Ves Es:) S (1h: Ey+1:) +
Σ
+ min do(v/Et)
y'Ey
ssec8++
= (i +
Σ
Y+ min do(v/ vee
jSKrt+1
S (Us: Eg:) +7
Thus, assuming dedit (y. 3) I 1, we have shown (y:: Ej:) I (T Ey:) + y from which follows that dy (v)E) (T, + 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 y from y.
Proceeding with the main proof, define for convenience the quantity
a = k
PY (+++i-1).
1=1
Observe
m/k-1
aYY
(10)
m
while Observation B.3 together with our assumption that dodit dodit (Y,Y) S em implies
m
Σ
min doait de (VoT+ Y') S ke.
(11)
Y'ES(V)
The displays (10) and (11) together imply there exists index and Y' s()) such that a I miny'est. dedia (Y++IT+RR, Y') 2 a(Y) E. Reusing the same concentration argument as in the proof of Theorem 2.4, for we have
I
IP (ddo(Y+ +++1)++)) -k (Coā, + +t) Y) s exp (-2kt²),
and thus from Observation B.4 it follows that
IP (d, (++,,t44))) (Coa(Y) 7E +t) ( < cxp (-2kt)).
Letting& & (Goa 72)/2 and recalling the definition of the test statistic, we have
P (0(Ý -k (Coa(Y) /2 2 FrY) s exp (-K(Coa(Y)) /2)
(12)
All that remains to bound the probability of Φ(Y 5`) exceeding the threshold from the above display. To this end, define the set-valued map No(9) (v/ doauly, v') S B/(44 1)}. Then make the following observation.
31

---

Published in Transactions on Machine Learning Research (05/2024)
Observation B.5. For any y V and & E E", there crists vf E MMante) (v) such that
dy E) = dean (v. 3/) + E).
Proof. We proceed via induction. The base case where y and ç both have length follows trivially by laking v' = in particular, 7 > 1/2 implies d(v.E) S 7 + miny' d(y',E) and likewise d(y, E) S 7 + ming d(y. 4"). Now suppose the result holds so long as len(y) + =g) S 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 (v, de (122.22)) Ei)..E)). By our induction hypothesis, there exists á E - such that dy (v2: (2:) y dedu (y2: 0) + (2)). The desired result then obtains with y as the concatenation of y1 and g. Second, suppose (v. = (2.) + mingez d(yi. 5¹) + 7. By our induction hypothesis, there exists I E -N such that di (12:. E) = 7 dedit (92. 0) + d(ū E2.). The result obtains with y' = ÿ. Finally, suppose (v, = (v2.. E) + d(y"", :1) + for some y" E V. By our induction hypothesis, there exists ÿ NN such that (12. E) = deai (122, 1) + d(g. E). The result then obtains by concatenating y" with y.
Let Iy = () For any S i Ienn(Yen - k and j E [n], Observations B.4 and B.5 together imply that
dy (Y
min 7. dodit (Ye4144,,)) do do ) (ENe((
(13)
min VENU/4( - 1)(4444)))
7. dedi (v. V14114t) + doly. E2,),
(14)
where (+) follows from the fact that dedit (Y++144),)) > k/4(7 - 1) implics
y deau (Y41444) v) + do & k/4> do (Y (f+1sth: E2,),
and therefore the minimizer in equation (13) must be an element of N1 (E+444))
By construction, NV((v) consists of the set of strings obtainable from y by sequence of at most & insertion and/or deletion operations. Now define another set-valued map Nv) as the restriction of Na(r) 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,, by +1/2, for any B it follows that
min 7 dedit (v. PALLIAE) + doly, ( min do do(..tt), (
veN,, (
and so, letting 3 =k/44(7- - 1), from equation (14) we have
min doly, do(y, dy (Y & veN,, (aaan))
Let (i, E) denote the l-th element of No No. for some Y-measurable indexing. From the indepen- dence of Y and g', we have E]do(Y (i, (I, Y] = for any and j. The cardinality (Y is equal to the number of possible combinations of locations for 8 insertion and/or deletion operations on Y, of which there are at most (k + 3y < (2k)². Thus, applying the same concentration argument as in the proof of Theorem 2.4 and laking a union bound over all S m - k, j S n and Ê < (2k)², we have
P(o < -a(Y)22+ (ÝY) S mm((2))/(4771) (xppa))>>>(0)xpppp(pppp_p xxp(-kCB(a(Y) - /2)
(15)
Combining the displays (12) and (15) via another union bound gives the desired result.
32

---

Published in Transactions on Machine Learning Research (05/2024)
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.
Lemma C.1. Let EEE ((M) and & (n, Then for any y E [M] we have
P(T(E, u) y, log(En)/u(v) 2 t) p(y) exp(-t).
Proof. Suppose p(y) as otherwise the claim is trivial. Recalling & Ltd. Unif([O, 1)), for any X we lid. Exp(A), ie.,
have - A loog
P(-Alogg 2 = P(E, - exp(-Att) = exp(-At).
Thus, the claim follows as
P(T p)) = y, - Loggoog(,)//ug) 2
Ply = arg min log(E:)/ log(En)/ 2)
u(v) exp(ep - > u)
uzt
[
p(y) (ww)exp(-HH) exp((H(y)u) 14 exp(-))))
Juze
m(V)
11iesupp(n) exp(-n(i)vu
Juzi
(uV) exp(-u)
uzt
=m(y) exp(-t);
where in (x) we use the fact that the density of - log(Ey)/m()) at u is p(y) exp((p(())))
7
C.1 Proof of Theorem 2
Proof. The result follows immediately from integrating the result of Lemma C.1 over 12 0.
0
C.2 Proof of Lemma 2.7
Proof. Lemma C.1 implies - log(Es)/p({) Ya-1) Y ~ Exp(1), and thus E[| log(E.) Y] p(Y: Ya-1). Mcanwhile, as & ~ Unif([O, 1)) independently of Y, we have
P-- c 2 Y) P(C S exp(-t)) exp(-t),
implying - log(E)) Y ~ Exp(1) and so log(E) Y = 1. The result follows immediately, recalling a()) = p(Y Y,-1) by definition.
C.3 Proof of Lemma 2.8
We prove the following general result, from which Lemma 2.8 follows as a corollary.
Lemma C.2. Let m,n n E N with n 2 m, where m is the generation length and n is the watermark key length. Define the decoder I by equation (4), alignment score by equation (5), and & by Algorithmm with block size & S m. Let 5 id.d Unif(E") with Y generate(E; n. n.p.I), r). Let Y be a substring Y of length at least that is conditionally independent of & and g' given Y, i.e., Y = Y for E 2 k. Then for â = Eith p(Y; Ys-1), almost surely
P(O(V,)) s (V (
(.Y) & 2nexp (- min (kā² /8, (8,kk//4)
33

---

Published in Transactions on Machine Learning Research (05/2024)
Proof. Recall by definition
len(z)
d(y.5) =- _
log Ea.y.
Lemma 2.7 and the conditional independence of T and & given Y imply for any j E [v] that
Eld(Y 6(541:44)9m)) Y, Y] 11EEEdd( E741)44) Y,Y]= kā.
From Lemma C.1, we have - -lgg Y, Y Exp(1)) for some 7 S for all i [m]] Also, from the independence of y and E', we have - -log j.Yi
y Y ~ Exp(1) for all E [m]] and E [n]. The following
observation thus implies - logg Y, Y and logg j,Y; YYY Y are both (2, subexponnall random variables.
Observation C.1. Let X Exp(1). Then X is (2 suberponential random variable.
Proof of Observation C.1. For t 1/2, have
Ele ((eXX-B(XI)
_- dx (a)
e_
(6)
$ (1 t +1
(0)
$ 28
20
where (a) follows from the fact that < (otherwise, the integral would not be finite); (b) follows from Taylor expanding e* and 1/(1 t) and applying the fact that t < 1/2 to bound the higher-order terms; and (c) again follows from t < 1/2. The claim follows immediately.
Thus, using the fact that & is conditionally independent E- given Y, standard Chernoff bound (Wain- wright, 2019, Proposition 2.9) implies for each j [n] that
P dd( {+15+4) dd (r41144) 18,))
P (im) - Eld(( {1m)) 2 kō/2 Y.Y)
IP (E(d(", (Eld(Ý, & (5+14tm))) 2 kā/2 {,,))
$ 2 (kā² /8, kō/4))
Recalling the definition of the test statistic via Algorithm 3, the main claim then follows from taking a union bound over all j [n].
Details of experiments
D.1 Experimental protocol
In Experiments 1-6, for each watermark we first generate a sequence tokens, decode the tokens into text (i.e., string) using the appropriate tokenizer for the language model, and then encode the text back into tokens before running detect. Each generation is coditioned prompt; obtain the prompts by sampling
34

---

Published in Transactions on Machine Learning Research (05/2024)
documents from the news-like subset of the C4 dataset and truncating the last tokens. We enforce minimum prompt size of 50 tokens in all experiments; we skip over any document that is not long enough. The retokenization is not always equal to the original tokens generated by the model, in order to ensure detect always receives at least m tokens, we pad its imput with special pad tokens (specific to each model's tokenizer). We also initially generate a number of buffer tokens beyond m, so in most cases the padding is unneccssary. We set the number of buffer tokens to be 20 in every experiment except for Experiment 5, where we set to be 100 in order to ensure that even after deleting tokens there are typically still least tokens remaining. We always truncate the number of tokens given to detect to be at most m, irrespective of the number of buffer tokens.
D.2 Roundtrip translation
In Experiment 6, we perform round-trip translations from English to French and from English to Russian using the OPUS-MT collection of translation models (Tiedemann & Thottingal, 2020; Tiedemann et al., 2022). Specifically, we use the versions of these models hosted on the HuggingfaceHub, associated with the identifiers:
Bblaiiaii-NN///puuussmttttboorrr English to French,
del.ssawwi.-/s///uuuurrtttttoooo French to English, -Frenhh
Hellsinki-NIIP/ppus-mt--aar English to Russian,
Hellsinnii-IIl//qpp---t--raara Russian to English.
D.3 Computing p-values
As mention previously, to save computation modify detect to fixed reference distribution to compute p-values. For the sake of concreteness, give the full pseudocode for the modified version of detect in Algorithm 5; in Experiments 1-6, we compute p-values using Algorithm to construct the reference distribution using the news-like subset of the C4 dataset as the text distribution.
Algorithm 5: Watermarked text detection with fixed reference distribution
Input string y E V*, seed sequence E Params: test statistic Φ; reference distribution {
Output: p-value p E [0, + 7 Σ { < o+}
return p
As sanity check, we include histograms of the p-values we compute for nonwatermarked text for each method to verify that they roughly uniformly distributed the interval [0, 1] (setting sampling prompts from the like subset of the C4 dataset, in Experiment 1). In the cases of KGW-1.0 and KGW-2.0, the distribution is not quite uniform due to the discrete nature of their test statistics.
50 and
Bytc--aair tokenizations of text (used by both the OPT and LLaMA) not unique, due to the fact that they augment base vocabulary (e-g., characters) with extra tokens represent common substrings. 17 "httpp//hhuggingfee
35

---

Published in Transactions on Machine Learning Research (05/2024)
Algorithm 6: Reference distribution construction
Input resample size T E N, text length m E N, watermark key sequence distribution v E A
Params: test statistic Φ; text distribution P: minimum prompt length mg
Output: reference distribution {ó:]i=1 R
1-1
while t ST do
Y ~ P
if lem(Y) mm + m then
5
continue
{(*) ~v
Oi + ooY {(1)
t+
return { }
25
20
count
Count
15
30
30
pvalue
pvvalue
(a) OPT-1.3B
(b) LLaMA-7B
Figure 15: Distribution of p-values for nonwatermarked text using ITS detector.
25
Count
25
20
pvolue
pvalue
OPT-L13B
(b) LLaMA-7B
Figure 16: Distribution of p-values for nonvatermarked text using ITS-edit detector.
36

---

Published in Transactions on Machine Learning Research (05/2024)
30
Count
30
pvalue
pvvalue
(a) OPT-1.3B
(b) LLaMA-7B
Figure 17: Distribution of p-values for nonwatermarked text using EXP detector.
25
20
20
20
pvolue
pvalue
OPT--13B
(b) LLaMA-7B
Figure 18: Distribution of p-values for nonvatermarked text using EXP-edit detector.
37

---

Published in Transactions on Machine Learning Research (05/2024)
80
70
00
60
30
20
20
pvalue
pvaalue
(a) OPT-1.3B
(b) LLaMA-7B
Figure 19: Distribution of p-values for nonwatermarked text using KGW-1.0 1.0 detector.
80
80
60
60
40
40
30
20
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
pvolue
prvalue
(a) OPT-1.3B
(b) LLaMA-7B
Figure Distribution of p-values for nonwalermarked text using KGW-2.0 detector.
D.4 Hyperparameter tuning
There two hyperparameters involved in computing each of watermark test statistics (i.e., Algo- rithm 3), the block size & and the alignment score d. We do not tune the block size for experiments, instcad simply letting k = i.c., the text length, and the alignment score is also fixed for each of our watermarks, except. for the hyperparameter y in both ITS-edit and EXP-edit. Smaller values of y (at least to a certain point) tend to make these watermarks more robust to insertion and deletion errors, as Figure 21 illustrates, but also hurts their statistical power for large values of n, i.c., the watermark key length, Figure illustrates. We set y 0.4 for ITS-edit and 7 0.0 for EXP-edit to balance these two competing desiderata.
38

---

Published in Transactions on Machine Learning Research (05/2024)
0.07
0.05
0.00
p-value
0.04
0.03
0.00
0.02
0.81
0.00
Y
(a) ITS-edit
(b) EXP-edit
Figure 21: Median p-vulue of watermarked text for varying 7 with OPT-1.3B models and m = 70 for ITS- edit and m = 35 for EXP-edit, after corrupting the text with random insertions (fraction of inserted tokens is 0.1 for ITS-edit and 0.6 EXP-edit).
0.1
0.5
Y=
0.3
0.5
Y 0.5
0.004
1.5
0.00
0.003
0.15
0.003
0.00
0.000
250
500
750
2000
1250
1500
1750
2000
200
400
600
800
1000
Watermark key length (n)
Watermark bey length In)
(a) Ids-edit
(b) EXP-edit
Figure 22: Median value of watermarked text, varying y and n, with OPT-1.3B model and ITS-edit and 10 for EXP-edit.
40 for
39

---

Published in Transactions on Machine Learning Research (05/2024)
D.5
Deferred results
D.5.1
Experiment 3
0.5
edit
MS adit
KGW-2
KGW
0.4
Medien preeuve
Median preelue
0.2
0.1
0.1
0.1
0.2
0.3
0.4
0.6
0.7
0.1
02
0.3
0.4
0.5
0.6
0,7
Fraction subsbitutions
Fraction substitutions
(a) OPT-133B
(b) LLaMA 7B
Figure 23: Median p-value of watermarked text relative to the fraction substitution errors, for OPT-1.3 and LLaMA 7B models with 35.
p-values substitution error
EXP
Gumbel
KDW-2.0
KDW-2.0
0.30
0.25
med. poaluu
0.25
0.20
0.20
0.05
0.00
0.00
0.1
0.2
0.3
0.4
0.6
077
0.1
0.3
0.4
0.5
0.6
0.7
Frection of substitutions
corruption rete
(a) OPT-1.3B
(b) LLaMA 7B
Figure 24: Median pavalue of watermarked text relative to the fraction of substitution errors, for OPT-1.3B and LLaMA 7B models with 70.
40

---

Published in Transactions on Machine Learning Research (05/2024)
MS--ddit
MS-eddtt
0.4
0.4
Medien Wedieen--eelue prwelue
0.3
Medien p-relue
0.2
0.1
0.0
0.0
(a) OPT-1.3B
(b) LLaMA 7B
Figure 25: Median p-value of watermarked text relative to the fraction substitution errors, for OPT-1.3B and LLaMA 7B models with m 70.
D.5.2 Experiment
ITS
ITS
0.
KDW-1.0
KDW-1.0
Medinn preelue
Median p-veluee
0.3
0.1
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.1
0.2
0.3
0.4
0.5
0.6
0.7
Frection of insertions
Frection of insertions
(a) OPT-1.3B
(b) LLaMA 7B
Figure 26: Median valalue of watermarked text relative to the fraction of insertion errors, for OPT-1.3B and
LLaMA 7B models with 35.
41

---

Published in Transactions on Machine Learning Research (05/2024)
EXP
EXP
EXP-edit
0.4
EXP-edit
0.30
p-rllu
Medien p-velue
0.20
0.10
3.00
0.0
(a) OPT-1.3B
(b) LLaMA 7B
Figure 27: Median p-vuuue of watermarked text relative to the fraction of insertion errors, for OPT-1.3B and
LLaMA 7B models with m 70.
0.
ITS
KDW-1.0
04
Wedinn preelue
Medinn p-velue
0.1
0.1
mS edit
0.0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.1
0.2
0.3
0.4
0.5
0.6
0.7
Frection of insertions
Frection of insertions
(a)
OPT-1.3B
(b) LLaMA 7B
Figure 28: Median vavalue of watermarked text relative to the fraction of insertion errors, for OPT-1.3B and
LLaMA 7B models with 70.
42

---

Published in Transactions on Machine Learning Research (05/2024)
D.5.3 Experiment 5
0.5
ITS edit
IT edit
Medien prveluv
Medien p-velue
0.2
0.1
0.4
(a) OPT-113B
(b) LLaMA 7B
Figure 29: Median p-vuuue of watermarked text relative to the fraction of deletion errors, for OPT-1.3B and
LLaMA 7B models with m 35.
EXP
EXP KDW-2.0
KDW-2.0
0.20
0.15
0.10
0.05
0.05
0.00
0.00
0.1
0.
0.4
0.6
0.1
0.2
0.4
0.6
Fraction deletions
Fraction deletions
(a) OPT-1.3B
(b) LLaMA 7B
Figure 30: Median y-value of watermarked text relative to the fraction of deletion errors, for OPT-1.3B and
LLaMA 7B models with 70.
43

---

Published in Transactions on Machine Learning Research (05/2024)
IS--ddtt
IS--ddit
0.4
Medien Wedienn-reeooe powelue
Medien porelue
0.3
0.3
0.2
0.1
0.0
0.0
(a) OPT-1.3B
(b) LLaMA 7B
Figure 31: Median p-vuuue of watermarked text relative to the fraction of deletion errors, for OPT-1.3B and
LLaMA 7B models with m 70.
D.5.4 Experiment 6
MT5
KCW-1.0
0.5
KGW-1.0
0.5
preelue
Median proeluee
0.4
0.3
0.2
0,2
0.1
10
15
20
30
60
50
10
15
20
30
40
45
50
Text length (m)
Text length (m)
(a) OPT-1.3B
(b) LLaMA 7B
Figure 32: Median v-auuue of watermarked text relative to the fraction of insertion errors, after roundtrip translation via French, for OPT-1.3B and LLaMA 7B models with m 35.
44

---

Published in Transactions on Machine Learning Research (05/2024)
ITS
IS-eddtt
0.45
0.5
p-value
Medien p-welue
0.35
0.4
0.30
IS-eedit
KGW-1.0
0.20
longth
longth (m)
(a) OPT-1.3B
(b) LLaMA 7B
Figure 33: Median p-vulue of watermarked text relative to the text length, after roundtrip translation via Russian, for OPT-1.3B and LLaMA 7B models with m = 35.
D.5.5 Instruction following case study
We give three examples of instructions for which hashing produces qualitatively worse responses than regular samples from the language model:
1. "Give me 20 ideas for the title of a paper on watermarking language models."
2. "Give me 20 ideas for startup names."
3. "Give me list of 20 movies."
We format each the instructions as described by Taori al. (2023) before calling the model.
We compare samples from EXP watermark strategy, 18 which equivalent to regular samples from the language model, to samples from KGW-2.0 and the hashing-based version of EXP we describe in the main text (i.c., the watermark of Aaronson (2023)), i.e., EXP-hash. For both EXP and KGW-2.0, we generate the samples using five different random seeds (the hash function in KGW-2.0 is fixed in the implementation of Kirchenbancr et al. (2023)), whercas the case of EXP-hash we use five different hash functions (namely, we let the previous k tokens Wi hash to ++ Σt yi for j E 4)). We label each sample using the seed/hash we used to generate it. We include samples from two versions of EXP-hash: one where we hash the previous tokens (k = 1) and another where we hash the previous four tokens (k = 4). For KGW-2.0, we only hash the previous token since the public implementation of Kirchenbauer the option to hash more tokens.
(2023) does not include
We find that EXP-hash with k = 1 often produces qualitatively worse responses that degenerate into repe- tition. With k = 4, the repetition is substantially less noticeable, though occasionally it still manifests. In contrast, even when only hash the previous token, the repetition of KGW-2.0 is not nearly noticcable as in EXP-hash. We speculate this is due to stochasticity of KGW-2.0 (i.e., KGW-2.0 biases the distribution over the next token to a subset of tokens but still ultimately samples from this distribution randomly). Of course, this stochasticity comes at a price: KGW-2.0 was generally less powerful compared the EXP and EXP-edit strategics our other experiments.
We include sample sheets for all methods for the first instruction below. To avoid excessive clutter, defer the sample sheets for the remaining two instructions to our code release.
Recall both and EXP-edit the same generate method.
45

---

Published in Transactions on Machine Learning Research (05/2024)
Method
Seed
Response
1. Watermarking Deep Learning Models: A Review 2. Understanding and Evaluating Wa- termarking Techniques for Neural Networks 3. Towards Unobtrusive and Invisible Water- marking for Neural Networks Customizable Watermarking for Neural Networks Reverse Engincering Watermarked Neural Networks 6. Understanding and Exploiting Watermark- ing Attacks on Neural Networks 7. Combatting Watermarking Attacks on Neural Networks 8. Customizable Watermarking for Neural Networks 9. Customizable Watermarking for Neural Networks 10. Customizable Watermarking for Neural Networks 11. Customizable Watermarking for Neural Networks 12. Customizable Watermarking for Neural Networks 13. Customizable Watermarking for Neural Networks 14. Customizable Watermarking for Neural Networks 15. Customizable Watermarking for Neural Networks 16. Customizable Watermarking for Neural Networks 17. Customizable Watermarking for Neural Networks
EXP-hash
(k: (k=1)
18. Customizable Watermarking for Neural Networks 19. Customizable Watermarking for Noural Networks
1. Exploiting Watermarks in Language Modeling 2. Watermarking Language Models: State of the Art 3. Keys to the Kingdom: Refining Watermarking Language Models 4. Exploiting Watermarks in Natural Language Processing 5. Keys to the Kingdom: Refining Watermark- ing Language Models 6. Keys to the Kingdom: Refining Watermarking Language Models 7. Keys to the Kingdom: Refining Watermarking Language Models 8. Keys to the Kingdom: Refining Watermarking Language Models 9. Keys to the Kingdom: Refining Watermarking Language Models 10. Keys the Kingdom: Refining Watermarking Language Models 11. Keys to the Kingdom: Refining Watermarking Language Models 12. Keys to the Kingdom: Refining Watermarking Language Models 13. Keys to the Kingdom: Refining Watermarking Language Models 14. Keys to the Kingdom: Refining Watermarking Language Models 15. Keys to the Kingdom: Refining Watermarking Language Models 16. Keys to the Kingdom: Refining Watermarking Language Models 17. Keys to the Kingdom: Refining Watermarking Language Models 18. Keys the Kingdom: Refining Watermarking Language Models 19. Keys to the Kingdom: Refining Watermarking Language Models 20. Keys the Kingdom: Refining Watermarking Language Models
EXP-hash (k 1)
1
1. 'Making Watermarks: Crcative Approaches to Watermarking Language Modcls' 2. "Mak- ing Watermarks: Creative Approaches to Watermarking Language Models' 3. "Making Watermarks: Creative Approaches to Watermarking Language Models' 4. "Making Water- marks: Creative Approaches to Watermarking Language Models' 5. 'Making Watermarks: Creative Approaches to Watermarking Language Models' 6. 'Making Watermarks: Cre- ative Approaches to Watermarking Language Models' 'Making Watermarks: Creative Approaches to Watermarking Language Models' 8. "Making Watermarks: Creative Ap- proaches to Watermarking Language Models' "Making Watermarks: Creative Approaches to Watermarking Language Models' 10. 'Making Watermarks: Creative Approaches to Wa- 2 termarking Language Models' 11. 'Making Watermarks: Creative Approaches to Water- marking Language Models' 12. 'Making Watermarks: Creative Approaches to Watermark ing Language Models' 13. "Making Watermarks: Creative Approaches to Watermarking Language Models" 14. "Making Watermarks: Creative Approaches to Watermarking Lan- guage Modcls" 15. 'Making Watermarks: Crcative Approaches to Watermarking Language Models" 16. 'Making Watermarks: Creative Approaches to Watermarking Language Mod- els' 17. 'Making Watermarks: Creative Approaches to Watermarking Language Models' 18, "Making Watermarks: Creative Approaches to Watermarking Language Models' 19. "Mak- ing Watermarks: Creative Approaches to Watermarking Language Models' 20. "Making Watermarks: Creative Approaches to Watermarking Language Models'
EXP-hash
(k: 1)
46

---

Published in Transactions on Machine Learning Research (05/2024)
1. Watermarking Language Models: A Review 2. Watermarking Language Models for Copy- right Protection 3. Watermarking Language Modcls for Forensic Analysis 4. Watermarking Language Models for Audio Signals Watermarking Language Models for Video Signals Watermarking Language Models for Documents 7. Watermarking Language Models for Soft- ware Watermarking Language Models for Big Data 9. Watermarking Language Models for Natural Language Processing 10. Watermarking Language Models for Machine Learning 11. Watermarking Language Models for Deep Learning 12. Watermarking Language Models for Speech Recognition 13. Watermarking Language Models for Audio Synthesis 14. Wa- termarking Language Models for Computer Vision 15. Watermarking Language Models for Robotics 16. Watermarking Language Models for Autonomous Driving 17. Watermarking Language Models for Modical Image Processing 18. Watermarking Language Models for Medical Diagnosties 19. Watermarking Language Models for Text Translation
EXP-hash
3
(ke (k=
1. Image based watermarking for language models Steganographic watermarking for language models 3. Timestamps for language models 4. Watermarking for language model improvisation 5. Secure watermarking for language model sharing 6. Image based water- marking for language model improvisation 7. Timestamps for language model improvisation 8. Watermarking for language model evolution 9. Secure watermarking for languago model evolution 10. Image based watermarking for language model evolution 11. Timestamps for language model evolution 12. Watermarking for language model generation 13. Image based watermarking for language model generation 14. Timestamps for language model genera- tion 15. Watermarking for language model understanding 16. Image based watermarking for language model understanding 17. Timestamps for language model underslanding 18. Watermarking for language model improvisation and understanding 19. Image based water- marking for language model improvisation and understanding
EXP-hash
(A: 11=
Table 1: Responses from EXP-hash with k 1 to the prompt: "Give me 20 ideas for the title of a paper on watermarking language models."
Method
Seed
Response
1. "Safeguarding Language Models: Exploring Watermarking for Vertext and Image Models'
2. "Watermarking Language Models: Protecting Your Creations' 'The Future of Water- marking Language Models: Ethical and Practical Considerations" 4. "Securing Language Models: Exploring Emerging Technologies' 5. 'Watermarking Language Models: Balanc- ing Creativity and Security" 6. 'Watermarking Language Models: Balancing Security and Accessibility' 7. "Watermarking Language Models: Defending your Creativity" 8. 'Wa- termarking Language Models: Defending your Creativity with Emerging Technologies' 9.
"Protecting Language Models: Exploring Emerging Technologies" 10. 'Securing Language Models: Balancing Security and Accessibility" 11. "The Future of Watermarking Language Models: Ethical and Practical Considerations' 12. "Watermarking Language Models: Bal- ancing Security and Accessibility' 13. 'Watermarking Language Models: Balancing Security
EXP-hash
(k 66=0 4)
and Accessibility with Emerging Technologies" 14. 'Watermarking Language Models: De-
fending your Creativity with Emerging Technologies' 15. "Watermarking Language Models:
Defending your Creativity with Emerging Technologies' 16. 'Securing Language Models: Balancing Security and Accessibility with Emerging Technologies" 17. 'Exploring Water- marking for Vertext and Image Models' 18. "Watermarking Language Models: Balancing Security and Accessibility with Emerging Technologies' 19. 'Defending your Creativity with Emerging Technologies"
47

---

Published in Transactions on Machine Learning Research (05/2024)
1. Towards a New Era of Transparent Language Models 2. A Review of the State of Water- marking Language Models 3. The Benefits of Embodding Watermarks in Language Models Protecting Language Models with Multiscale Watermarks Impact of Watermarking on the Performance of Language Models A Survey on Watermarking for Language Models 7, Practical Perspectives on Watermarking for Language Models 8. A Comprehensive Study on Designing Watermarks for Language Models 9. Overview of Techniques for Adding Wa- termarks to Language Models 10. Exploring the Possibilities of Watermarking for Language Models 11. How to Incorporate Watermarks in Your Language Model 12. The Science be- hind Watermarking for Language Models 13. AI for Insertion of Watermarks in Language Models 14. The Role of Machine Learning in Watermarking for Language Models 15. Future Trends Watermarking for Language Models 16. Review on Watermarking for Language Models 17. Applications of Watermarking in Language Modeling 18. A Comprehensive Study Designing Robust Watermarks for Language Models 19. A Novel Approach to Incorporate Watermarks in Your Language Model.
EXP-hash
(A: - 4)
1. Securing Your Language Model 2. Stamping Out Unauthorized Use 3. Coloring Outside the Lines: Creative Watermarks 4. Avoiding Watermarks: Best Practices 5. Authentication
Made Easy with Watermarks 6. Defending Your Language Model 7. Unique Identifiers:
Adding Value to your Model 8. Connected Learning: Leveraging Watermarks 9. The Prob- lem with Open Access 10. How to Elfectively Mark a Language Model 11. Making a Splash
EXP-hash
(k 4k
with Creative Watermarks 12. Understanding the Benefits of Watermarking 13. Utilizing Watermarks for Better Attribution 14. Stewarding Your Language Model 15. The Role of Technology in Watermarking 16. Beyond the Horizon: Adaptive Watermarking 17. The Art of Discrction in Watermarking 18. Harnessing the Power of Invisible Watermarks 19. Practical Considerations for Watermarking
1. Elucidating Watermarking Strategies for Language Models 2. Innovative Techniques for Watermarking Language Models 3. Intelligent and Innovative Watermarking Strategies for Language Models Overview of Watermarking Strategies for Language Models 5. Emerg- ing Technologies in Watermarking for Language Models 6. Practical Perspectives on Wa- termarking Language Models 7. Reducing Watermarking Strategies for Language Models 8. Robust Techniques for Watermarking Language Models 9. Security Factors in Watermark- ing Language Models 10. Understanding Watermarking Strategies for Language Models 11. Evaluation of Watermarking Strategies for Language Models 12. Exploring Watermarking Strategics for Language Models 13. Innovations in Watermarking Language Models 14. In- celligent Techniques for Watermarking Language Models 15. Methods for Watermarking Language Models 16. Overlapping Security Factors Watermarking Language Models 17. Understanding Watermarking Strategios for Language Models 18. Emerging Technologies in Watermarking Language Models 19. Exploring Watermarking Strategics for Language Models 20. Intelligent. and Innovative Watermarking Strategies for Language Models
EXP-hash (k: (k= 4)
3
1. Securing Language Models 2. Extra Secure Language Models 3. Defending Language Models 4. Protecting Language Models 5. Cryptographic Language Models 6. Unique Lan-
guage Models 7. Robust Language Models Marking Language Models 9. Preventing Language Models 10. Hiding Language Models 11. Invisible Language Models 12. Stegano- graphic Language Models 13. Watermarking Language Models 14. Preserving Language Models 15. Uniquely Identifiable Language Models 16. Characterixing Language Models 17. Distinguishable Language Models 18. Language Model Defence 19. Ultra Defence Language Models
EXP-hash (k: (k=4) 4)
Table 2: Responses from EXP-hash with k to the prompt: "Give me 20 ideas for the title of paper on watermarking language models."
Method
Seed
Response
48

---

1. Providing Type-Safe Watermarks 2. Constructing Robust Watermarks for Multimedia Applications 3. Adding Security Features to Text Vectors 4. Stretching Visible Watermarks 5. Embedding Watermarks Natural Language Models Training Recurrent Neural Networks with Watermarks 7. Detoction of Unsupervised Watermarks Text Sequences 8. Interactive Visualization of Watermarks 9. Observe Hidden Watermarks with Machine Learning 10. Extracting Information from Unseen Watermarks 11. Building Robust Water- Published in Transactions on Machine Learning Research (05/2024)
1. Steganography in Language Models: A Review 2. Combating Model Piracy with Wa- termarking 3. Tochniques for Traccability and Watermarking 4. Salient Features for Trace- ability and Watermarking Rellections on Model Security and Watermarking 6. Insights on Model Security and Watermarking 7. Protecting Models with Watermarking 8. Tech- niques for Esoteric Traceability and Watermarking 9. Ins and Outs of Steganography in Language Models 10. Technologies for Efficient Watermarking 11. Vision Beyond Model Piracy: Watermarking Perspectives 12. Impact of Model Security on Watermarking 13. Emerging Trends in Watermarking of Language Models 14. Future of Watermarking TTech- niques for Language Models 15. Drivers for Success in Watermarking Language Models 16.
KGW-2.0
Robustness of Models against Watermarking 17. Taking Security beyond Watermarking 18.
Leveraging Model History and Watcrmarking 19. Tochniques for Secure Watermarking 20. Comprehensive Overview of Model Security and Watermarking.
1. Embedding Digital Signatures: Towards Traceable and Transparent Language Mod- cls 2. Stamping Out Deception: Recording Attribution in Language Models 3. Defining Your Digital Dashboard: Watermarking for Traceability 4. Scaling Trust in Language Mod- els: Watermarking for Traceability and Transparency 5. Taking an East Asian Approach to Transparency in Language Models 6. Riding the Big Five: Towards Transparency in Language Models 7. Measuring the "Ps" of Language Models: Perceptual and Practical Transparency 8. Marking a Mark: Comprehensive Examination of Attribution in Language Models Visualizing Deception: Comprehensive Examination of Deceptive Language Mod- cls 10. Peak Performance: Evaluating Language Models for Transparency 11. Closing the Loop: Examining the Long-term Impacts of Language Models 12. Diversifying Perspec- tive: Impacts of Modelling Language 13. Disclosing the Hidden Layers: Understanding Transparency in Language Models 14. Auditable: Making Language Models Accountable 15. Labelling Human Language: Exploring the Capabilities of Language Models 16. Setting the Record: Estimating the Real-world Impacts of Language Models 17. Language Models: Towards Traceable, Transparent and Accountable Systems 18. Think Outside the Box: Ex- ploring Future Trends in Language Models 19. Embedding Trust: Towards Traceable and Transparent Language Models.
KGW-2.0
1
1. Defending Latent Space with Secure Watermarks 2. Emergent Waveforms: A Watermark- ing Approach 3. Embedding Digital Identities in Neural Networks 4. Marking up Models: A Survey on Watermarking 5. Leveraging Linked Data for Watermarking 6. Stamping Out Superfluous Models 7. Inspecting and Marking Models 8. Rethinking Digital Identity with Watermarks 9. Marking Up Models: Usage-Driven Approach 10. Bridge the Distance with Digital Watermarks 11. Introducing Transparency in Model Formation 12. Unlock- ing Models with Secure Watermarks 13. Giving Visible Identity to Models 14. Unveiling Dark Knowledge with Watermarks 15. Linking Models: A Visual Approach 16. Visualizing Dark Knowledge through Watermarks 17. Teveraging Physical World for Model Tracking
KGW-2.0
18. Augmented Reality for Model Tracking 19. Securing Deep Models with Watermarks
KGW-2.0
3 marks for the Blockchain 12. Adding Dynamic Watermarks to Video Streams 13. Storing Watermarks in Individual Dataset Elements 14. Extracting Pertinent Information from Un- wanted Watermarks 15. Decoding Hidden Digital Watermarks 16. Introducing Watermarks to Secure Semi-honest Adversaries 17. Genuine Components with Integrated Watermarks 18. Intelligent Techniques for Steganography 19. Protecting Quality with Data-Driver Wa-
termarks
49

---

Published in Transactions on Machine Learning Research (05/2024)
1. Embedding Watermarks in Language Models 2. Secure Language Models using Water- marks 3. Steganographic watermarking of natural language models 4. Exploring Water- marking Techniques for Natural Language Models 5. Analyzing Natural Language Models using Watermarking Techniques Detecting Watermarks in Natural Language Models 7, Supervised Learning of Watermarks for Natural Language Models 8. Unsupervised Learning of Watermarks for Natural Language Models 9. Multiple watermarks for secure language 4 models 10. Generative watermarking techniques for natural language models 11. Evaluation of watermarks for secure natural language models 12. Efficacy of watermarks in preventing model poisoning 13. Robustness of watermarks for natural language models 14. Compari- son watermarking techniques for natural language models 15, Linking natural language models with watermarks 16. Extraction of hidden information from natural language models 17. Universality of watermarks for different languages 18. Learning watermarked natural language models 19. Reduced Dimensionality Modeling using Watermarks
KGW-2.0
Table 3: Responses from KGW-2.0 the prompt: "Give me 20 ideas for the title of a paper on watermarking language models."
Method
Seed
Response
Here is the list of 20 ideas for the title of a paper watermarking language models:
1. "Understanding Watermarking Techniques for Language Models" 2. "A Comprehensive
Study on Watermarking for Language Models' 3. "Watermarking Techniques for Optimiz- ing Language Models' 4. 'A Survey Watermarking Techniques for Language Models'
5. "Exploring the Potential of Watermarking for Language Models' 6. 'Implementing Wa- termarking for Language Model Optimization" 7. "Watermarking Strategies for Enhancing Language Models" 8. 'Investigating the Possibilities of Watermarking for Language Mod- els' 9. 'Advanced Watermarking Approachos for Language Models" 10. 'Exploring the Use of Watermarking for Language Model Validation' 11. "Understanding the Benefits of Wa- termarking for Language Model Ensemble' 12. "Leveraging Watermarking Techniques for Enhanced Language Model Performance' 13. "Enhancing Language Models with Water- marking" 14. 'Evaluating the Impact of Watermarking Techniques on Language Models' 15. "Analyzing the Feasibility of Watermarking for Language Model Comparison" 16. 'Exploring the Possibilities of Watermarking for Optimizing Language Models' 17. "Exploiting Water- marking to Enhance Language Model Accuracy' 18. "Advantages of Using Watermarking for Validating Language Models" 19. 'The Promise of Watermarking for Evaluating Language Model Performance"
EXP
0
Title idcas for a paper on watermarking language models: 1. Hidden Mcssages: Protecting Language Models with Watermarking Securing Language Models with Watermarking Defending Language Models against. Tampering 4. Watermarking Language Models for Better Protection 5. Verifying the Integrity of Language Models Utilizing Watermark- ing to Boost Language Model Security 7. Ensuring the Authenticity of Language Models 8. Safekeeping Language Models with Waternarking 9. Defending Against Model Tam- pering with Watermarking 10. A Review of Model Security Techniques: Watermarking 11. Uuilizing Watermarks to Protect Language Models 12. Protective Techniques for Language Models: Watermarking 13. Implementing Watermarks to Boost Language Model Security 14. Preventing Model Tampering with Watermarking 15. Methods for Verifying Language Model Integrity 16. Analyzing the Security of Language Models 17. Techniques for Secur- ing Language Models 18. Investigating Model Security with Watermarking 19. Extending Language Model Security with Watermarking
EXP
1
50

---

Published in Transactions on Machine Learning Research (05/2024)
1. 'Deep Watermarks: Towards Pervasive Protection for Language Models' 2. 'Adding Transparency to Language Models: Watermarking Approach' 3. "Watermarking Lan- guage Models for Traceability and Verification"
"A Comprehensive Review on Water- marking Methods for Language Models' 5. "The Power of Watermarking for Language Model Protection' 6. "Attributing Authorship in Language Models with Watermarking' 7. "Understanding the Promise of Watermarking for Language Model Security' 8. 'Watermark- ing Language Models: A Survey' 9. 'Watermarking Language Models for Better Security' 10. "Mitigating Plagiarism in Language Models with Watermarking" 11. "Watermarking Language Models: Exploring the Possibilities' 12. 'A Generative Approach to Watermark- ing Language Models" 13. 'Watermarking Strategies for Protecting Language Models" 14. "Watermark Detection for Language Model Socurity" 15. "Making Language Model Socu- rity Watertight with Watermarking' 16. "Leveraging Watermarking for Enhancing Language Model Security' 17. "Understanding the Role of Watermarking in Language Model Security' 18. "A Novel Approach to Watermarking Language Models" 19. "Exploring the Possibilities of Watermarking for Language Model Security'
EXP
2
1. A Comprehensive Review of Watermarking Techniques for Language Models 2. A Survey of Watermarking Approaches for Language Modeling 3. A Normative Analysis of Water- marking for Language Modeling 4. Investigating Watermarking Techniques for Language Modeling 5. An Overview of Watermarking Methods for Language Modeling 6. Exploring Watermarking Solutions for Language Modeling 7. A Taxonomy of Watermarking Methods for Language Modeling 8. A Comparative Study of Watermarking Approaches for Language Modeling 9. Evaluating Watermarking Methods for Language Modeling 10. A Theoretical
3 Analysis of Watermarking for Language Modeling 11. Investigating Watermarking Tech- niques for Natural Language Modeling 12. An Analytical Study of Watermarking for Lan- guage Modeling 13. Exploring Watermarking Methods for Natural Language Modeling 14. Review of Watermarking Techniques for Natural Language Modeling 15. Compara- tive Study of Watermarking Approaches for Natural Language Modeling 16. Investigating Watermarking Solutions for Natural Language Modeling 17. A Survey of Watermarking Techniques for Natural Language Modeling 18. Evaluating Watermarking Methods for Nat- ural Language Modeling 19. A Review of Watermarking for Natural Language Modeling 20. Exploring Watermarking Solutions for Natural Language Modeling
EXP
1. Towards a Unified Watermarking Mechanism for Natural Language Processing Mod- cls 2. A Review of Methods for Watermarking Natural Language Modols 3. Extracting Invariant Features for Watermarking Language Models 4. The Use Steganography for Watermarking Natural Language Models Introducting Secure Watermarking Techniques for Natural Language Models 6. A Comprehensive Study Watermarking Techniques for Natural Language Models 7. Toward Remarkably Visible Watermarks for Natural Language Models 8. Analyzing the Impact of Watermarking on Natural Language Models 9. A Prac- tical Guide to Marking Language Models 10. Enhancing the Accuracy of Watermarking Natural Language Models 11. Evaluating Strategies for Watermarking Natural Language 4 Models 12. A Comparison of Watermarking Approaches for Natural Language Models 13. Promising Solutions for Securely Watermarking Natural Language Models 14. Generative and Discriminative Approaches for Watermarking Natural Language Models 15. Explor- ing the Possibilities of Steganography for Natural Language Models 16. Understanding the Challenges of Watermarking Natural Language Models 17. Evaluating the Effectiveness of Watermarking Techniques for Natural Language Models 18. Enhancing the Transparency
EXP
of Watermarking Techniques for Natural Language Models 19. Extending the Capabilities
of Watermarking Techniques for Natural Language Models 20. Assessing the Sophistication of Watermarking Techniques for Natural Language Models
Table 4: Responses from EXP to the prompt: "Give me 20 ideas for the title of a paper on watermarking language models."
51


Reviews:
[{"review_id": "eANpqLeRwC", "reviewer": "Reviewer_XRf9", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "^", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "*** Requested short comparison to the work of Christ et al. (2023) ***\n\nA previous work of Christ et al. (2023) presents \"undetectable\" watermarks for language models. Their work is cited and briefly discussed in this submission. I will go into a few more details on the differences and similarities between the two.\n\nThe main strength of Christ et al. over the current submission is that their definition of \"undetectability\" is much stronger than the current submission's definition of \"distortion-free\".\nIn this submission, \"distortion-free\" means that for a single query (i.e., a single prompt given to the model), the distribution of responses will be the same as if the original model was given the same query. \nThis definition is natural, but doesn't take into account multiple queries: it could be that a set of several responses to several queries is now correlated to each other in some manner. (For example, the model could become fully deterministic and still be distortion-free over the choice of random key).\nIn Christ et al., the definition of \"undetectable\" is stronger: they require that even if polynomially many, possibly adaptive, queries are made to the model, their responses would still be indistinguishable from those that would have been given by the original model.\n\nThe authors of this work do notice the issue of correlated responses and address it with a heuristic: they essentially have several different \"keys\" and run the scheme with a random one each query to \"obfuscate\" the correlations. Of course, the number of those \"keys\" is small as this requires enumerating over all of those \"keys\" in the detection algorithm. Thus this isn't really preventing correlations but just makes them slightly more difficult to notice (and indeed there is no formal guarantee about correlations between different queries in this submission, unlike in the other work).\nBesides this new heuristic, the rest of the protocol is very similar to both the work of Christ et al. and another previous work of Aaronson (also cited in this paper).\nSection 2.1 in this submission, for example, exactly describes an algorithm presented in Christ et al., without stating anywhere it is not a new contribution. \nThe entire \"generate\" method in fact is not new and is a variation of Christ et al. and/or Aaronson. \n\nOn the other hand, the strengths of the current paper over the aforementioned previous works are twofold:\nFirst, this submission provides empirical implementation and evaluations, which both Christ et al. and Aaronson failed to do.\nSecond, this submission focuses more on robustness of the watermarks to edits in comparison to the previous works, which is an important property for watermarks that is \"orthogonal\" to undetectability/distortion-freeness. The authors study the \"robustness\" of their watermark both theoretically and empirically.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "A better comparison to the papers mentioned above is needed. In particular, comparing the definitions of robustness-free/undetectability, comparing the guarantees of robustness, and comparing the methodology to both Aaronson and Christ et al.\nTechniques and algorithms are not appropriately attributed and cited in several places.", "broader_impact_concerns": "-", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "qHCxR3B7uN", "reviewer": "Reviewer_3pbi", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n- very well written paper\n- new watermarks algorithms which preserve the original LM conditional distribution over next tokens\n- independence on the model and prompt - thus more general watermarking algorithm\n- improved robustness with respect to insertions / deletions / substitutions and paraphrasing compared to prior works\n- more sensitive statistics compared to prior works\n- deep theoretical analysis\n- practical simplifications of the theoretical algorithms and demonstration of their work on real case models \n\n**Weaknesses**\n- restriction of the key: hack on permuting the key for generation is solving the issue, but still restrict the number of possible generations - deeper discussion of this would be nice to have in the paper\n- some proofs in the paper are not entirely clear; notation can be improved; a bit heavy with the proofs without detailed derivation of the equations.\n- mismatch between theory and practice for the algorithms - some fair check or detailed comparison between them is needed to confirm why it is still eligible to use modified version in practice (though it is cheaper to compute)\n- sharable key between LM owner and user (general limitation which is fine to have for the paper)\n- paper proposes 4 variants for the algorithm and it is not clear which we should use in practice as depending on the attack or case one is more preferable than others but not always the same one.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "To detect if text is generated the watermark for text was proposed in the past with different algorithms. The current paper considers extension of research in this direction. Authors propose watermarks algorithm for text generated by an autoregressive language\nmodel with assumption that that the owner of LM will share the key with which the text was generated. The algorithm consists of the generate algorithm on the LM owner side and detect algorithm on the user side. The latter is the proper statistics computation and testing it if the text was generated using the key or not. The main difference with prior works is two folds: 1) it is guaranteed the generated text will be from the same distribution as without watermarking (LM conditional distribution is preserved) and 2) proposed algorithms are shown to be robust to perturbations. Authors generate watermarked text by mapping a sequence of random numbers - which they compute using a randomized watermark key - to a sample from the language model. To detect watermarked text, any party who knows the key can\nalign the text to the random number sequence. Besides deep theoretical analysis and proofs on the asymptotic of the algorithms with respect to the key length and text length, authors perform empirical analysis with modified version of algorithms for practical applicability and show results for OPT-1.3B, LLaMa-7B and Alpaca-7B models with additional substitutions/insertions/deletions and paraphrasing (via back-translation) attacks.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The paper is very well written though I have some suggestions and notes how to improve readability and clarity further:\n- \"preserve original text distribution\" -- I would be more precise here even in the intro part of the paper, as in the end we preserve only conditional distribution of language model.\n- improve notation: \n  - $\\Nu^{*}$ and in general notation of \"*\" is not introduced.\n  - definition 1 - maybe include here conditional pdf of LM as an example? otherwise seems the definition is about general pdf of text\n  - lemma 2.1 why $n$ should be bigger than $m$?  maybe introduce earlier how you generate the text given watermark sequence? that every token in watermark is used to generate next token of text? What happens if $n < m$ (I got that empirically it seems still work to detect if text is watermarked or not)?\n  - algorithm 2 line 3: does $\\xi^{(t)}\\in \\Xi^*$?\n  - page 9 what does notation $xi_j$ and $xi_i$ in lemma 2.3 constitute?\n  - figure 2 - use the same scale for both plots\n  - plot together all lines from Fig. 3 and 4 for comparison. Maybe plot with different slices as edit / non-edit, as you want to show the linear / exp dependence with respect of some param growth.\n  - Fig. 9 -- add explanation / footnote why the pattern of curve now is different with respect to length (it is decreasing p-value, not growing).\n  - Fig. 10 -- why do we see U-shape curves now?\n  - Fig. 12 (b) use the same bins ranges so that histograms are exactly comparable.\n  - Appendices proofs - first state all lemmas/theorems for every proof, otherwise hard to come back to the main text every time.\n  - Algorithm 6 line 6: what is $P_{xi}$? do we sample one token of $xi$ or sequence of them? Do we sample different permutations of $\\xi$ sequence or not?\n- \"in which lie the elements of the watermark\" -- I guess from English language the sentence is built incorrectly. Maybe \"in which the elements of watermark lie\"?\n- page 5 \"independent copy\" -- what do you mean? \"to break ties\" in the footnote -- what does it mean exactly?\n- What happens with watermark detection if we swap paragraphs in the generated text as the method of corruption? or swap sentences?\n- Typo page 7: \"Observe the watermark\" -> \"Observed the watermark\"\n- I got that theory is simpler to improve in one form, while empirically to be practical statistics form is different. But could you have any empirical result with original statistics and algorithms (for which the strong proof is given) to show that it is consistent with the theory?\n- page 8 ITS is used before notation appeared.\n- what are the probability of type 1/2 errors? \n- what happens if block size $k$ is less than $m$?\n- how do you propose to resolve the issue that different methods are robust with respect to different attacks? e.g. exp-edit is worse than others except attack with insertions/deletions.\n- proofs questions:\n  - lemma 2.2\n    - (*) transition: what happens with the part when $y$ is not in $\\nu_c$?\n    - what is the notation $D_{TC}$? why do we have inequality for the every $A$ for $D_{TC}$ in this form? \n    - the final inequality I don't get, it seems incorrect to me. Could you give more detailed transitions and explanations how you ended up with it?\n  - lemma B.1\n    - add $eta$ notation as I forgot it by that time of reading the paper :) \n    - equation between (7) and (8): what it is $P$? \n    - why width of $I(Y, \\pi)$ is $\\mu(Y)$? I didn't get entirely transitions in (8)\n  - lemma 2.5\n   - what is notation for $\\tilde{\\alpha}$?\n  - the rest of proofs looks reasonable for me, though it is hard to read them as too many notations (probably unavoidable). Any simplifications (maybe put more details on every transition) and putting definitions of all vars at the beginning of each proof make it simpler to read and follow.\n- \"The retokenization is not always equal to the original\" - why is this? Can you explain in more details?", "broader_impact_concerns": "The paper is trying to resolve some ethics concerns related to generative models. Particularly, it is proposing the method of text watermarking with the hypothesis testing if the text is generated by a particular provider (who gave us the key) independent from the model type and prompt.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "EYEXdpl2Sz", "reviewer": "Reviewer_eJM9", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**\n\n1. **Innovative Approach**: The paper introduces novel techniques for embedding watermarks in machine-generated text. It's a pioneering step in content attribution, crucial for intellectual property protection in AI-generated content. The approach is unique in its aim to seamlessly integrate watermarks without altering the natural text distribution.\n\n2. **Robustness Against Text Corruption**: The watermarks demonstrate remarkable resilience to various perturbations, such as text alterations or corruptions. This robustness is crucial for the practical applicability of watermarks in real-world scenarios, where text modifications are common.\n\n3. **Preservation of Text Distribution**: A significant achievement of this research is maintaining the originality and coherence of the text. The watermarks are designed to be distortion-free, meaning they do not affect the readability, style, or informational content of the text. This aspect is critical for ensuring that the watermarked text remains useful and engaging for its intended audience.\n\n**Weaknesses:**\n\n1. **Potential for Misuse**: While the paper focuses on the technical aspects of watermarking, it opens up discussions on ethical implications. The technology, if misused, could lead to surveillance or privacy concerns. It's important to consider these aspects in the development and implementation of such technologies.\n\n2. **Model Dependency**: The effectiveness of the watermarking techniques seems to vary with different language models. This suggests a potential limitation in their applicability, indicating that each model may require a customized approach for effective watermarking.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper presents a methodology for embedding robust, distortion-free watermarks in text generated by autoregressive language models. This is achieved without altering the text distribution. The process involves generating watermarked text by mapping random numbers, computed using a watermark key, to samples from the language model. Detection is possible for anyone with the key. Two watermarking methods are explored: inverse transform sampling and exponential minimum sampling. The techniques are tested on various language models (OPT-1.3B, LLaMA-7B, Alpaca-7B) to validate their statistical power and robustness against paraphrasing attacks and text corruption. The study finds that the watermarks are detectable even with substantial token corruption and explores a case study on watermarking responses to user instructions.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. **Interplay with Language Model Updates**: How does the watermarking technique adapt to updates or modifications in the underlying language model, e.g., moving from LLaMA to LLaMA 2,3 etc.? \n\n\n2. **Quantitative Analysis of Text Distortion**: Can you provide a quantitative metric to assess the degree of distortion (if any) introduced by the watermarking process in the text? This could help in objectively evaluating the \"distortion-free\" claim.\n\n\n3. **Watermark Capacity and Limitations**: What is the maximum amount of information that can be embedded as a watermark without affecting the text quality? \n\n\n4. **Compatibility with Different Text Genres**: How does the watermarking process perform across various text genres, such as technical documents, creative writing, or conversational text? \n\n\n5. **Watermark Traceability in Distributed Systems**: How traceable are these watermarks in distributed systems, like when text is shared across multiple platforms? \n\n\n6. **Algorithm Specificity in Inverse Transform Sampling**: Could you elaborate on how inverse transform sampling is adapted for watermarking in language models? Specifically, how does it maintain the fidelity of the original text distribution while embedding watermarks?", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: We apologize to the authors for the extended delay.  Please see the comments above about claims and evidence for the justification and for the expectations for the revision.
Decision: Accept (poster)