# Mark My Words: Analyzing and Evaluating Language Model Watermarks

Julien Piet  UC Berkeley Chawin Sitawarin  UC Berkeley Vivian Fang  UC
Berkeley Norman Mu  UC Berkeley David Wagner  UC Berkeley

###### Abstract

The capabilities of large language models have grown significantly in recent
years and so too have concerns about their misuse. In this context, the
ability to distinguish machine-generated text from human-authored content
becomes important. Prior works have proposed numerous schemes to watermark
text, which would benefit from a systematic evaluation framework. This work
focuses on text watermarking techniques — as opposed to image watermarks — and
proposes MarkMyWords, a comprehensive benchmark for them under different tasks
as well as practical attacks. We focus on three main metrics: quality, size
(e.g. the number of tokens needed to detect a watermark), and tamper-
resistance. Current watermarking techniques are good enough to be deployed:
Kirchenbauer et al. [1] can watermark Llama2-7B-chat with no perceivable loss
in quality, the watermark can be detected with fewer than 100 tokens, and the
scheme offers good tamper-resistance to simple attacks. We argue that
watermark indistinguishability, a criteria emphasized in some prior works, is
too strong a requirement: schemes that slightly modify logit distributions
outperform their indistinguishable counterparts with no noticeable loss in
generation quality. We publicly release our benchmark
(https://github.com/wagner-group/MarkMyWords)

##  1 Introduction

Recent advancements in large language models (LLMs) have been paralleled by
escalating concerns over their misuse. Researchers have pointed out the
potential of language models to automate social engineering attacks [2],
conduct large-scale propaganda operations [3], and more [4]. Preventing misuse
is challenging.

One approach to mitigate these risks is _watermarking_ , in which a subtle
watermark is embedded in all output from the model, so that others can detect
LLM-generated text. With the rise of LLMs, multiple watermarking schemes have
been proposed [5, 1, 6] and subsequently analyzed [7, 8, 9, 10]. Nevertheless,
the feasibility of watermarking LLM outputs in practice remains unclear. Some
researchers argue that watermarks can be practical [10], while others argue
the opposite [8, 9]. The results from these papers seem almost contradictory,
and there has yet to be a consensus on how to evaluate different watermarking
schemes or whether they are ready for practical deployment.

Figure 1: Watermark size at near-optimal quality for four watermarking schemes
taken from the literature. The distribution-shift scheme [1] outperforms all
others at low temperatures, where it only needs a median of 80 tokens for the
watermark to be detected.

Our work tackles this challenge by providing a common ground where these
algorithms can be empirically evaluated. We propose MarkMyWords, a benchmark
to evaluate the effectiveness of watermarking schemes under three realistic
tasks, representing three possible misuses: book summarization, creative
writing, and news article generation. We devise metrics to measure efficiency,
quality, and tamper-resistance. To measure tamper-resistance, MarkMyWords
tests whether a number of simple attack algorithms—word swap attacks, synonym
attacks, HELM perturbations [11], paraphrase attacks, and translation
attacks—can remove the watermark without significant loss of quality.

Figure 2: An overview of the LLM watermarking scenario.

Next, we combine previous proposed watermarking schemes [1, 5, 6, 12] into a
unified design framework. This abstraction allows practitioners to build
custom watermarking schemes using building blocks from different papers. We
ran MarkMyWords on all practical parameter combinations. We come to the
following conclusions:

  1. 1.

Watermarking schemes are ready for deployment. We can watermark the output of
Llama 2 with little loss in quality, and these watermarks can be detected with
under 100 tokens of output.

  2. 2.

Watermarks with the right parameters are relatively robust to simple attacks.
Although more sophisticated attacks are capable of removing any watermark, for
the best watermarking schemes our most powerful attack—which uses GPT-3.5 to
paraphrase model outputs—only removes the watermark 60% of the time.

  3. 3.

Our results may have implications for public policy, as they inform the extent
to which watermarking is operationally feasible with current technology. For
instance, the 2023 White House agreement with industry included a voluntary
commitment to deploy technology such as watermarks for AI-generated audio and
video, but did not include any commitment regarding AI-generated text [13].

  4. 4.

Some prior work has proposed indistinguishability as a criterion for
watermarking schemes, i.e. that the distribution of watermarked outputs be
provably indistinguishable from non-watermarked outputs. We argue that this is
not necessary for practical watermarking, and our results suggest it can be
overly restrictive. In our experiments the best scheme is distribution shift
[1]. It produces the easiest-to-detect watermark, while maintaining the
original model’s quality, despite not being indistinguishable.

  5. 5.

We quantify the impact of each watermarking hyperparameter on the metrics, and
provide recommendations for practical parameter settings.

MarkMyWords is publicly released at https://github.com/wagner-
group/MarkMyWords.

##  2 Background

In this paper, we consider watermarking schemes that can be applied to
existing pretrained language models. These schemes are the most convenient and
practical as they can be added to any generative language model without
requiring fine-tuning. We evaluated prior work up until August 2023. We
provide here a high-level overview of the schemes; later we propose a unifying
framework in which all prior schemes can be expressed (Section 7).

###  2.1 Related Work

Watermarking of textual data has been extensively studied [14, 15, 16]. It can
be viewed as a form of steganography [17, 18] with a one-bit message.
Steganography imposes the strong requirement that, without knowledge of the
secret key, the distribution of watermarked and unwatermarked outputs be
indistinguishable. Indistinguishability is beneficial for watermarking schemes
too, as it implies that the mark does not harm the quality of the generated
text. However, we found that quality can be preserved without
indistinguishability. Watermarking the output of a large language model can be
viewed as the problem of embedding a mark when we can sample from the output
distribution with limited additional control [19, 20, 21, 22, 23].

Another approach to detecting AI-generated text is to train a binary
classifier on LLM outputs. This approach avoids the need to modify how text is
generated by the LLM. Many schemes can be found in the literature, including
OpenAI’s classifiers [24, 25], GLTR [26], DetectGPT [27], and others [28, 29,
30, 31, 32]. Unfortunately current LLMs have gotten so good at generating
natural-looking text that these detectors have become unreliable. These
detectors will perform even worse as LLMs improve.

For proprietary LLMs, an alternative is for the vendor to keep a copy of all
generated outputs from their LLM. Then, they can provide an API to look up any
text and determine whether it was previously produced with their LLM [10].

###  2.2 Definition

A (digital) watermark is a pattern embedded in a signal (image, text, audio,
etc.) for identifying the source of the signal. For generative language
models, watermarks are useful to detect machine-generated text, in contexts
where using language models could be unethical, like phishing emails, fake
news, or college essays. We seek to build a watermark that is not easy for an
adversary to remove.

Watermarks could conceivably also be used to _prove_ that text was indeed
machine-generated, for instance, to guarantee the provenance of a generation,
similar to copyrights. That setting is out of scope for this paper.

Watermarking algorithms have two parts: a marking procedure $\mathcal{W}$ and
a verification procedure $\mathcal{V}$. At generation time, each new token
invokes the marking procedure to embed a watermark into the generated output.
The marking procedure has access to a secret key $k$, the previous tokens
$T_{0},\cdots,T_{n-1}$, and the language model’s distribution
$\mathcal{D}_{n}=p(T_{n}\mid T_{0},\dots,T_{n-1})$ on the next token, and
outputs the next token $T_{n}$. Verification takes as input a secret key and a
piece of text, and returns True if the text was generated using marking
procedure $\mathcal{W}$.

Our work focuses on symmetric key watermarking algorithms published before
August 2023. To our knowledge, the only asymmetric key scheme was proposed by
Fairoze et al. [33] in October 2023. It embeds each bit of a public key
signature into segments of text by using rejection sampling.

TABLE I: Randomness Sources Randomness Source | Description | Parameter
---|---|---
text-dependent | sliding window | Keyed hash of sliding window of previous tokens | window size
min hash | Minimum of keyed hash applied to each previous token in sliding window
fixed | Expands secret key to pseudorandom sequence | key length

###  2.3 Evaluated watermarks

Prior work has proposed four different marking procedures. Each consists of a
randomness source and a sampling strategy. The randomness source provides a
pseudorandom value for each token, which is used by the sampling strategy to
select the next token. We identify three randomness sources, summarized in
Table I, each of which uses a keyed hash to generate pseudorandom values in a
deterministic fashion, so that the verifier can reconstruct those pseudorandom
values. Text-dependent randomness sources rely on a fixed-size window of
previous tokens. Fixed randomness relies on a sequence of random values that
is the same for every output. Each marking procedure was initially proposed
with a specific randomness source, however any of the sampling strategies can
be combined with any randomness source.

  * •

Aaronson and Kirchner [5] mark text by selecting a token $T_{n}$ that
maximizes a score that depends on the probability $p(T_{n}|T_{0\cdots n-1})$
and on a pseudorandom value $f_{k}(T_{n-H\cdots n-1})$ derived from a sliding
window of $H$ prior tokens. We’ll call this the _exponential_ scheme.

  * •

Kirchenbauer et al. [1] mark text by favoring tokens from a greenlist.
Greenlists are derived from a pseudorandom value (computed either as
$f_{k}(T_{n-1})$ or a min hash over a sliding window of prior tokens,
$\min(f_{k}(T_{n-H}),\dots,f_{k}(T_{n-1}))$). Tokens in the greenlist are
favored by adding a small bias $\delta$ to their logits, making them slightly
more likely to be chosen. We call this the _distribution-shift_ scheme.

  * •

Christ et al. [6] convert the tokens to bit-strings. Each random bit is chosen
based on pseudorandom value (we use $f_{k}(T_{n-H\cdots n-1})$, derived from a
sliding window of $H$ prior tokens, as explained in Section 7.2) and the LLM-
induced distribution on bits. Finally, they convert the bit-string to a
sequence of tokens. We’ll call this the _binary_ scheme.

  * •

Kuditipudi et al. [12] proposes using inverse transform sampling. They compute
the CDF $F(t)=\sum_{T_{n}=0}^{t}p(T_{n}|T_{0\cdots n-1})$ of the LLM’s output
distribution, where tokens are ordered pseudorandomly according to a secret
key $k$; then they use a fixed pseudorandom value $f_{k}(n)$ to sample from
this distribution, via the inverse transform $F^{-1}(f_{k}(n))$. We refer to
this as the _inverse transform_ scheme.

All but the distribution-shift scheme can be made indistinguishable from the
original distribution: When using a random seed, they sample according to the
original distribution. In practice, the better the randomness source mimics a
true random value, the harder these schemes are to distinguish from the
original distribution. The distribution-shift scheme is not indistinguishable,
since it alters the model’s logits.

All verification algorithms rely on computing a score $\mathcal{S}$ and
computing its likelihood under the null hypothesis that the text was not
watermarked. Watermarked text is flagged as AI-generated if the likelihood is
below a $p$-value threshold. The score is designed to match the sampling
strategy: we call _sum score_ the score used by text-dependent randomness, and
the _align score_[12] the score used by fixed randomness. Kuditipudi et al.
[12] propose a more sophisticated score — the _edit score_ — that considers
all possible alignments between the text and the sequence of pseudorandom
values. This innovation improves robustness against attacks that insert or
delete words when using fixed randomness, at the risk of more false positives.
Because it is inefficient, we only analyzed it on a subset of the benchmark,
detailed in Section 7.4.

All schemes rely on the LLM’s output distribution $p(T_{n}|T_{0\cdots n-1})$
to have some entropy, so that there are multiple possibilities for $T_{n}$
that the sampling strategy can choose among. The higher the entropy, the
easier it is to watermark, as the marking strategy has more possibilities to
choose from.

TABLE II: Marking Algorithms Paper | Name | Description | Proposed Randomness
---|---|---|---
Aaronson and Kirchner [5] | exponential | Selects tokens that maximize a hash-based score | sliding window
Kirchenbauer et al. [1] | distribution-shift | Favors tokens from a greenlist | sliding window or min hash
Christ et al. [6] | binary | Converts token distribution to binary alphabet | sliding window
Kuditipudi et al. [12] | inverse transform | Selects tokens using inverse transform sampling | fixed

##  3 Attacks on Watermarks

Any good watermarking scheme should easily detect the mark, if a LLM’s
watermarked output is used directly. For instance, if a student uses a LLM to
write an essay and copies the LLM’s output directly into their submission,
then all four schemes should have no problem detecting the mark, assuming the
AI-generated text is long enough.

It may also be important to provide some robustness against simple attacks.
For instance, a cheating student might make minor modifications to the AI-
generated text before submission, to try to evade detection. Sufficiently
sophisticated strategies can undoubtedly fool any watermarking scheme, but in
many practical settings, this might be more effort than it’s worth for the
attacker. For instance, a cheating student who is trying to save time using a
LLM instead of doing the assignment themselves probably won’t be interested in
time-consuming or technically sophisticated attacks. Therefore, it might be
more relevant to evaluate how robust the scheme is at detecting watermarked
attack that has been subjected to simple attacks to modify the text.

We evaluate each watermarking scheme against 8 simple attacks that seek to
remove the mark from AI-generated text by perturbing it. A perturbation of
generated text $x$ is some text $x_{\mathrm{adv}}$ that is semantically
similar to $x$, but can be syntactically different. There are many ways one
can modify text—some only change the syntax of the sentence, while others
replace words or entire sentences. Below we introduce the 8 attacks we use to
provide a holistic evaluation of watermark robustness.

Swap attack. Natural language is redundant: we are able to understand text
even if some words have been removed, reordered, or duplicated. One natural
attack on generated text is to randomly remove, add, and swap some words in
each sentence. We scan generated text word by word, and with probability $p$,
we either remove the word, duplicate it, or swap it with another randomly
chosen word in the sentence. In addition to this, we randomly swap full
sentences with the same probability $p$. Swap attacks are easy to implement
for an attacker, and for small values of $p$ produce text that is still
understandable.

Synonym attack. This attack replaces words in sentences with synonyms. With
probability $p$, we replace each word in the text by a semantically equivalent
word. This attack is more difficult to implement for an attacker. We automate
this attack using WordNet [34] to zero-shot prompt GPT-3.5 to generate
candidate synonyms. In practice, this approach sometimes creates grammatically
incorrect or unnatural sentences. However, for a low probability $p$, the
output text is still semantically close to the original.

Paraphrase attack. Perhaps the strongest attack in our toolkit, the paraphrase
attack involves using another language model to rephrase the generated text.
This can be difficult and expensive to implement for an attacker, as they need
access to a high-quality non-watermarked language model to do so, but the
attack can completely change text without perturbing its meaning. We implement
two versions: (1) zero-shot prompting GPT-3.5 to paraphrase a generation, and
(2) Dipper [10], a fine-tuned model designed for paraphrasing.

Translation attack. This is similar to the paraphrase attack, except we use a
translation model (argos-translate [35] based on OpenNMT [36]) to translate
text through a cycle of languages (e.g., English $\to$ French $\to$ English).
This will not change the text as much as the paraphrase attack, but it is easy
for an attacker to implement since they can use Google Translate. We use two
variants of this attack: one that translates to French and back, and another
that translates to Russian and back.

HELM perturbations. HELM [11] implements a number of perturbations in its
source code. They were originally designed to perturb model prompts. We use
them to perturb model outputs. Among the list of perturbations they implement,
we chose those that do not change the overall meaning of the text. In
particular, we use:

  * •

Contractions & expansions: Contract verbs (e.g. “do not” $\to$ “don’t”) or
expand them.

  * •

Lower case: Convert all words to lower case.

  * •

Misspelling: Misspell each word with probability $p$.

  * •

Typos: Add random typos to the text.

Out-of-scope attacks. We consider only attacks that perturb the generated
text. We do not evaluate attacks that work by modifying the prompt to the
language model. For instance, the “emoji attack” instructs the model to insert
a token, such as an emoji, between each word in a generation [1]. The attacker
can then remove the emojis after generation. The emoji attack defeats all
watermarking schemes using text-dependent randomness. These attacks are only
possible on advanced models that can understand complex queries, such as
ChatGPT. Because our benchmark is designed to work with open models, such as
Llama2, which have difficulty following such complex instructions, we do not
include these attacks.

We assume the attacker cannot make repeated queries to the verification
procedure. An adversary with a verification oracle (i.e., an oracle that can
tell if a text is watermarked or not) may be able to iteratively modify text
until the watermark is removed. One can thwart such attacks by keeping the key
$k$ secret, rate-limiting calls to the verification API, designing the
verification API to release only “watermarked” or “not” (and not the score
$\mathcal{S}$ or its likelihood), and possibly detecting clusters of closely-
related calls to the verification API.

##  4 Evaluation Metrics

We propose three metrics for evaluating watermarking schemes: (a) quality, (b)
watermark size, (c) tamper-resistance. We also propose an aggregate metric
that summarizes the performance of a watermarking scheme in a single number.

###  4.1 Quality

First, we evaluate the quality of watermarked output, to measure how much the
mark degrades the utility of the output. We build a suite of tasks that
language models might be used for, and compare the quality of watermarked
outputs on these tasks to the quality without watermarking.

The gold standard for evaluating quality uses a diverse set of human
evaluators to grade responses. However, human evaluation is impractical for
running a benchmark, so we look for the next best alternative.

We adopt automated rating by a language model, a standard approach used in NLP
for evaluation [37, 38, 39, 40, 41, 42, 43]. Specifically, we use zero-shot
prompting of Llama-2 (7B, chat version) [44] to rate watermarked outputs. We
provide Llama2 with the prompt of the original task and the watermarked
response, and we ask it to rate the response on a scale of 100 points (with
greedy decoding for determinism). This takes into account the relevance of the
answer (i.e. is this a good response to the prompt?), as well as English
fluency. We emphasize that this rating does not have any special meaning in
itself, so it can only be used to compare the relative quality of watermarked
output vs unwatermarked output.

One might be skeptical of using Llama2 since it’s a smaller model than the
ones typically used for rating. However, the tasks we ask it to rate are
simple, and Llama2 appears to rate accurately on these tasks. Ratings from
Llama2 are correlated to GPT3.5’s rating ($R^{2}$ of 0.97 for average ratings
on MarkMyWords, without perturbations), giving us faith in Llama-2’s ratings,
and enabling our benchmark to be run entirely locally without querying
external APIs. In the rest of this work, we will refer to the quality metric
as $Q$.

We also experimented with model perplexity, often used in the field of NLP as
a proxy for content quality, but found that it performed worse. The perplexity
of a text $T$ is the likelihood of that text, under another language model.
Unfortunately, perplexity tends to favor repetitive text [45, 46], causing
anomalies in our results. For example, we observed one output where the model
produced a partial response followed by many repetitions of the letter ‘l’;
the perplexity metric rated this response highly, but Llama2 automated rating
correctly rated it poorly. In fact, the $R^{2}$ between perplexity and GPT3.5
is only 0.84, significantly lower than Llama2 versus GPT3.5.

###  4.2 Watermark Size

The longer the text, the easier it is to watermark it and detect the
watermark, as there are more degrees of freedom to inject a mark. Therefore, a
critical metric is: how long must the generated text be, so that we are likely
to be able to detect the watermark in it?

The verification algorithm can make two types of errors: false positives occur
when a text is detected as watermarked when in fact is it not, while false
negatives occur when a watermarked text is not detected. All schemes we
consider rely on one-tailed statistical tests, so we can precisely control the
false positive rate (by setting the $p$-value threshold).

We define the watermark size to be the number of tokens needed to detect the
watermark, at a 2% false positive rate. We measure it as follows: for each
output from the benchmark, we run the verifier on increasingly long prefixes
of the output until we find the shortest prefix that is detected as marked,
then we compute the median of the lengths of these prefixes. (If no prefix is
detected as watermarked, we use $+\infty$ as the length.)

We considered an alternative metric: the percentage of outputs from the
benchmark that are detected as watermarked. However, this metric is heavily
influenced by the length of outputs from the language model and task. If most
outputs are too short, then most texts will not be detected as watermarked,
yielding a poor value of these metric even though there is nothing wrong with
the watermarking scheme. Our metric has the benefit of providing an
interpretable result for practitioners: it indicates how long text needs to
be, to have a good chance we will be able to detect whether it was AI-
generated.

We refer to the watermark size as $E$. Smaller values of $E$ indicate better,
more efficient watermarking schemes.

###  4.3 Tamper-Resistance

Figure 3: Example tamper-resistance plot. Blue points are attacks on the
_convex hull frontier_. The blue area represents the area under the curve, the
dotted lines represent the best attack that keeps quality within 80% of the
original.

We measure a watermarking scheme’s tamper-resistance (robustness to attacks
that seek to remove the mark) using 8 attacks, described in Section 3. These
attacks are simple to carry out for casual users. We run each attack on all
outputs generated from the benchmark. For each attack $A$, we compute two
quantities: $Q_{A}$, the fraction of quality that is retained after the attack
(a measure of how much the attack degrades quality), and $W_{A}$, the
percentage of outputs that are detected as watermarked despite the attack (a
measure of how effective the watermarking scheme is at preventing the attack
from removing the watermark).111We use the proportion of watermarked
generations instead of the watermark size $E$ because many attacks remove the
watermark from over 50% of generated texts, in which case all these attacks
would have a size of $+\infty$. We compute $Q_{A}$ as
$Q_{A}=\max(0,\min(Q^{*}_{A}/Q,1))$ where $Q^{*}_{A}$ is the average quality
of the attacked outputs and $Q$ the average quality of unattacked outputs.

We can visualize these attacks in a two-dimensional plot, with one point
$(Q_{A},W_{A})$ per attack, depicting the retained quality versus robustness.
We show an example plot in Fig. 3. These two quantities are a trade-off for
the adversary; attacks that disrupt quality more can potentially be more
effective at removing the watermark.

It is desirable to reduce the plot into a single number to facilitate
comparisons between watermarking schemes. We considered reporting the value of
$W_{A}$ for the strongest attack that retains at least 80% of quality, i.e.,
$\max\;\\{W_{A}\mid Q_{A}\geq 0.8\\}$. Although this metric is interpretable,
it relies on an arbitrary threshold and is noisy due to the interpolation
between a sparse set of data points.

Instead, we opt for a different metric: the area under the curve (AUC). The
closer a point is to the lower right, the more successful the attack is; the
farther the points are from the lower right, the more robust the watermarking
scheme is. By taking the convex hull of the set of points, we define a curve
in the plot ranging from $(0,0)$ to $(1,1)$ representing the attacks with the
best possible tradeoff between retained quality vs effectiveness. (Any point
on the hull frontier is attainable by sampling between the two closest attacks
on the hull.) The larger the area under this curve, the more robust the scheme
is. The area cannot exceed 0.5: attacks at $(0,0)$ and $(1,1)$ are always
possible, so the minimal area is the half-space below these points. Therefore,
to normalize the metric, we define the tamper-resistance $R$ of a watermarking
scheme to be twice the area under the curve.

This metric has a similar intuition to the area under the curve measured in
ROC curves in binary classification [47]. Although it lacks interpretability,
it does not depend on an arbitrary threshold and is much less noisy than the
first proposal. In our experiments, the standard deviation of $R$ was usually
an order of magnitude lower than that of the threshold-based metric.

Our basic benchmark excludes paraphrasing attacks, because they rely on large
or closed sourced language models, which can be difficult to obtain, require
expensive resources to run, or can be watermarked themselves. Translation also
relies on a language model, but since it is smaller, it can run faster and
cheaper than paraphrase models. We evaluate paraphrasing attacks in Section
6.3.

Finally, we found the AUC to be highly correlated to the success rate of
different attacks. We leave the detailed plot to Section .3 in Fig. 10. We
found that a tamper-resistance of 1 corresponds to less than 10% success rate
for the Russian translation attack and less than 40% for the GPT paraphrase
attack.

TABLE III: Prompts for the three text generation tasks used in our benchmark. Task | Prompt | P1 | P2 | P3 | Count
---|---|---|---|---|---
Book Report |  Write a book report about P1, written by P2. | Title | Author |  | 100
Story |  Write a P1 story about P2. | Tone | Topic |  | 100
Fake News |  Write a news article about P1’s visit to P2 in P3. | Person | Person | Place | 100

###  4.4 Aggregate Metric

We characterize any instantiation of a watermarking scheme—with a fixed single
set of parameters—with these three metrics. Of course, by sweeping the
parameters, it is often possible to trade off between these three metrics. In
some settings, it is useful to compare two watermarking schemes _overall_ ,
i.e., choosing “optimal” parameters for each scheme. This is challenging
because there is no single definition of the optimal tradeoff.

We propose an aggregate metric that supports this goal. We fix a target
relative quality (i.e., watermarked outputs must achieve at least a certain
percentage of the quality of the non-watermarked model) and a target tamper-
resistance. We use a training set to select the set of parameters that achieve
the lowest watermark size, given these targets. Then we report the size
achieved on a validation set with these parameters.

Figure 1 reports this aggregate metric for all four schemes, at a relative
quality threshold of 99% (the watermark can induce at most 1% degradation in
quality) and a minimum threshold of 20% for tamper-resistance (which
correspond to at most an approximately 80% success rate for the best attack).
Fig. 7 and Fig. 9 present results for other thresholds (optimizing for size
versus tamper-resistance, 1% quality versus 10% quality, $>0.2$ tamper-
resistance versus $>0$ tamper-resistance). Our code allows setting arbitrary
thresholds to accommodate practitioner needs.

##  5 MarkMyWords

We now present MarkMyWords, our benchmark for evaluating watermarking schemes.

###  5.1 Text Generation Tasks

MarkMyWords uses three text generation tasks. There were chosen to generate
long text, in order to ensure enough tokens to watermark most outputs and get
a good size estimate, and to represent realistic scenarios in which
watermarking would be useful. We watermark the outputs of each task and
measure quality, watermark size, and tamper-resistance on these outputs. Table
III shows the prompt for each task.

(1) Book reports. Our first task instructs the model to generate book reports
for a predefined list of 100 well-known books. This represents a realistic use
case of a watermark in an education context where instructors might wish to
verify if students have used a language model to complete their homework
assignment.

(2) Story generation. We ask the model to generate a short story, with a
specific tone (e.g., funny, sad, suspenseful), on a particular topic (e.g.,
“three strangers that win a getaway vacation together”). We use 100
combinations of topics and tones. In this case, detecting watermarks in
creative content is a way to trace the authorship of a piece of text.

(3) Fake news. Our last task asks the model to generate a news story about two
prominent political figures meeting at an event. In total, we have a list of
100 unique combinations of political figures and locations. Detecting
watermarks in short news articles or headlines could be useful for fighting
against automated fake news bots on social media.

###  5.2 Benchmark Implementation

We implemented the MarkMyWords benchmark in Python using the transformers
library [48] to implement models and watermarks. In general, the run times of
the watermarked models are comparable to those of base models. We rely on the
7B-parameter version of Llama-2 chat both for generation and rating. We chose
this model for its high quality and because its output distribution, like
other modern models, has low entropy. We’ve noticed newer language models are
more certain of their next-token predections, i.e., have lower entropy in
their output distribution, which makes watermarking more difficult. Thus,
using a low-entropy model makes for a more realistic evaluation of a watermark
scheme’s performance. This version of the Llama-2 model is known for often
refusing to generate content—we altered the system prompt to avoid this issue,
especially for the fake news task.

Our benchmark generates a total of 300 outputs from the language model. We
only attack a third of these (the first third of each task), as running
robustness tests on all 300 would make the benchmark too slow. The maximum
number of generated tokens per prompt is 1024. On a A5000 GPU, the benchmark
completes in 30 minutes to an hour.

Our code for the MarkMyWords benchmark has been made
public.222https://github.com/wagner-group/MarkMyWords It is easily updated to
support new watermarking schemes or new language models. We hope that future
proposals of watermark schemes will include an evaluation with this benchmark.

Efficiency. We have developed custom implementations directly in CUDA of some
of the watermarking schemes, to speed up computation.

  * •

Hash function. The exponential sampling scheme relies on computing the hash of
many elements. Our CUDA implementation allows this to be done in parallel.

  * •

Edit distance. The edit distance is computed with every possible key offset;
our code implements this in parallel.

Figure 4: Watermark size at near-optimal quality for text-dependent versus
fixed randomness. The values correspond to the minimal size of schemes with
near-optimal quality. We report the smallest size result accross all four
schemes. For text-dependent randomness, we report the smallest size between
sliding window and min hash. Text-dependent randomness is more efficient at
all temperature settings.

##  6 Results

We evaluated a total of over 1200 unique combinations of watermark schemes and
parameter settings. This took $\sim$1 week to run using 4 A5000 GPUs. We first
summarize our evaluation in Section 6.1, in which we advise using a
distribution-shift sampling strategy with text-dependent randomness. We
further analyze the impact of each parameter in Section 6.2, and give some
recommendations. Finally, we focus on tamper-resistance in Section 6.3, where
we show some watermarks can withstand GPT-paraphrasing in over 50% of cases
without sacrificing efficiency.

###  6.1 The “Best” Watermark

In Fig. 1, we show the minimal watermark size (median number of tokens needed
to detect a watermark, at 2% false alarm rate) under various temperatures, for
a quality degradation of at most 1% and a 20% constraint on tamper-resistance.

The distribution shift scheme performs the best at most temperature settings,
including the range 0.0–0.7, which which is arguably the most common range of
temperature values used in practice. At temperature 1, exponential sampling is
slightly superior, with distribution shift not much worse. The relative
ranking of watermarking schemes is consistent across different choices of
quality and tamper-resistance thresholds (see, e.g., Fig. 9).

Ready to deploy? The distribution shift scheme is able to detect watermarks
with $\sim$60–80 tokens (roughly 45–60 words), at temperatures in the range
0.0–0.7. This strongly suggests that the distribution shift watermarking
scheme is practical enough to be deployed today.

Parameter settings. The following parameter choices achieve the results shown
in Fig. 1: for distribution-shift, $\gamma=0.5$, text-dependent randomness
(sliding window of size 3), and $\delta=5$ (at $T=\leq 0.3$) or $\delta=4$ (at
$T=0.7$) or $\delta=2.5$ (at $T=1$); for the exponential scheme, text-
dependent randomness (sliding window of size 3) and skip probability $0.025$.
These achieve our goals of maintaining 99% of quality and tamper-resistance of
20%.

Indistinguishability. Our results highlight the shortcomings of designing a
watermarking scheme with provable indistinguishability. Distribution shift
does not guarantee indistinguishability, but by our metrics mostly outperforms
the other three schemes, which do provide provable indistinguishability, and
achieves very high quality scores. The other three schemes especially struggle
with lower temperature settings. This is expected, since the entropy of the
distribution they are mimicking converges to 0 as the temperature decreases,
which leaves them with little maneuvering room to choose alternate text for
watermarking purposes. In contrast, the distribution shift scheme is willing
to make minor changes to the output distribution to support watermarking. We
show that this does not affect quality much.

We suspect there are two key factors that enable distribution shift to perform
better: 1) the freedom to change the output distribution, in a way that does
not affect semantic meaning too much, offers many more possibilities to embed
a hidden watermark; 2) distribution shift works with the unmodified logits,
before temperature scaling, so it has the option to boost the chance of
selecting the second- or third-best token, whereas the other schemes work with
the output probability distribution after temperature scaling, which contains
less information than the unmodified logits (e.g., at temperature 0, it is
impossible to identify the second-best token from the output probability
distribution). Future work on watermarking might benefit from these insights,
by focusing on quality rather than indistinguishability and taking advantage
of the information in the logits.

Text-dependent vs. fixed randomness. In Fig. 4, we plot the minimal watermark
size for the same quality and tamper-resistance thresholds but vary the
watermarking scheme’s source of randomness instead of the scheme.333We exclude
text-dependent randomness with a window size of 0 or fixed randomness with a
key length of 1 from the analysis, since these corner cases are identical and
correspond to always using the same random value. Text-dependent randomness
uses a keyed hash of the preceding tokens, whereas fixed randomness uses a
fixed random value at each position. Fig. 4 shows that watermarking employing
text-dependent randomness achieves greater efficiency.

Figure 5: Size versus quality of all parameter settings at T=1. Hue indicated
tamper-resistance: the darker the color, the more tamper-resistant.
Distribution-shift is the most tuneable scheme. The quality spread of the
exponential scheme is due to low entropy randomness of some settings affecting
the model’s quality.

Tunability. We plot all quality/size/tamper-resistance tradeoffs attainable,
at a fixed temperature ($T=1$), in Fig. 5. Each data point represents a
combination of watermarking scheme and parameter setting. Distribution-shift
is the most tunable scheme: by adjusting the bias parameter, one can sacrifice
quality for watermark size, something that is not possible for other
watermarks. The exponential scheme shows significant spread in quality because
some parameter settings do not provide enough entropy (e.g., too small sliding
window). We describe how these schemes can be tuned.

Figure 6: The effectiveness of each attack, averaged over selected parameters.
We show the attack success rate and the relative quality of the text after it
has been perturbed by the attack. The labels indicate the parameters for each
point, the color indicates the class of attack.

###  6.2 Parameter Tuning

TABLE IV: Correlations between parameters and metrics.
\+ indicates a positive correlation, - a negative correlation, $\perp$ no correlation. Symbols in red indicate a strong effect of the parameter on the given metric. Parameter |  Window Size |  Min Hash |  Skip Prob | Bias |  Key Length
---|---|---|---|---|---
Quality | + | $\perp$ | + | - | +
Size | + | + | + | - | +
Tamper Resistance | - | + | $\perp$ | + | -
Suggested setting | 3 | False | 0.025 |  $\geq$2 | 4

Window size. Increasing the window size increases quality, but also increases
the watermark size and decreases robustness. We recommend using a window size
of 3; larger window sizes do not improve quality further.

Min hash. At a window size of 3, the min hash increases both tamper resistance
and size by 33%, compared to a sliding window. We recommend using a simple
sliding window.

Skip probability. We recommending setting the skip probability at 0.025 for
indistinguishable schemes (exponential, binary, inverse transform) using text-
dependent randomness, as this adds non determinism to their outputs. This also
provides slightly better quality than 0.

Bias. For distribution-shift, the bias ($\delta$) is a critical parameter that
has a large impact on quality, size, and tamper-resistance. Figure 11
visualizes its impact. We suggest choosing $\delta$ based on the most common
temperature that the model is likely to be used with. In all cases, only
values of $\delta\geq 2$ yield efficient schemes.

Greenlist size. Our early experiments showed that changing the greenlist size
($\gamma$) from 0.5 only negatively impacts the watermark in all three
metrics. Therefore we fixed $\gamma$ to 0.5 for our experiments and suggest
practitioners do the same.

Fixed randomness. When using fixed randomness, we recommend using key length
$L$ of 4. Smaller values are detrimental to quality, and larger values are
worse for tamper-resistance (see Fig. 12).

Summary. Table IV summarizes the effects of each parameter on the metrics. For
distribution-shift, the bias is the most critical parameter, and it allows
considerable control over the quality vs. size tradeoff, making distribution-
shift more tunable than the other schemes. Consequently, in applications that
are willing to can accept degradation to quality in exchange for better size
or tamper-resistance, distribution-shift is an excellent choice.

Figure 7: Success rate of various attacks against the two most competitive
schemes at optimal paramters from Fig. 1. (Minimal size at 99% quality and 20%
tamper-resistance). On the left, the GPT parahrase attack. On the right, the
Russian translation attack. The size of the watermark (median number of tokens
needed for the watermark to be detectable) is indicated next to each point.

###  6.3 Tamper-Resistance

Attack strength. We analyze the tamper-resistance of schemes with the optimal
parameters from Fig. 1, evaluating the success rate of each individual attack
to identify which attacks are most successful. Figure 6 reports the average
quality and success rate of each attack. Paraphrasing and translation are the
most effective attacks: they remove the watermark most often, and do not
heavily affect quality. Using Dipper to paraphrase is only slightly more
effective than translation attacks. Translation attacks are easier to run
since they either rely on smaller language models, or can be done with online
translation services such as Google Translate [49].

Paraphrasing and Translation attacks. Figure 7 shows the attack success rate
of the GPT paraphrasing attack and the Russian translation attack against the
two best watermarking schemes. The evaluated watermarks are those with the
optimal parameters from Fig. 1. The left side of the plot shows the success
rates of the GPT attacks. In all cases, at least 60% of attacks are
successful. The non-trivial success rate is unsurprising, since the parameters
were chosen primarily to minimize size, not tamper-resistance. The right side
of the plot shows the success rates of the translation attack. The attack is
less successful, getting under 40% success rate at all but one temperature.
The success rates of both attacks are correlated: settings that are robust
against one are also against the other.

##  7 Designing a Watermark

After the quick overview of watermarking schemes in Section 2, we now provide
more details about the watermarking design space. We created a unifying
taxonomy under which all previous schemes can be expressed. We first discuss
the requirements then the building blocks of a text watermark. Fig. 8
summarizes the current design space.

###  7.1 Requirements

A useful watermarking scheme must detect watermarked texts, without falsely
flagging human-generated text and without impairing the original model’s
performance. More precisely, we want watermarks to have the following
properties.

  1. 1.

High Recall. $\Pr[\mathcal{V}_{k}(T)=\texttt{True}]$ is large if $T$ is a
watermarked text generated using the marking procedure $\mathcal{W}$ and
secret key $k$.

  2. 2.

High Precision. For a random key $k$,
$\Pr[\mathcal{V}_{k}(\tilde{T})=\texttt{False}]$ is large if $\tilde{T}$ is a
human-generated (_non-watermarked_) text.

  3. 3.

Quality. The watermarked model should perform similarly to the original model.
It should be useful for the same tasks and generate similar quality text.

  4. 4.

Robustness. A good watermark should be robust to small changes to the
watermarked text (potentially caused by an adversary), meaning if a sample $T$
is watermarked with key $k$, then for any text $\tilde{T}$ that is
semantically close to $T$, $\mathcal{V}_{k}(\tilde{T})$ should evaluate to
True.

A desireable (but optional) property for watermarks is diversity. In some
settings, such as creative tasks like story-telling, users might want the
model to have the ability to generate multiple different outputs in response
to the same prompt (so they can select their favorite). We would like
watermarked outputs to preserve this capability.

Another useful property is _undetectability_ , also called
_indistinguishability_ : no feasible adversary should be able to distinguish
watermarked text from non-watermarked text, without knowledge of the secret
key [6]. A watermark is considered undetectable if the maximum advantage at
distinguishing is very small. This notion is appealing; for instance,
undetectability implies that watermarking does not degrade the model’s
quality. However, we find in practice that undetectability is not necessary
and may be overly restrictive: minor changes to the model’s output
distribution are not always detrimental to its quality.

In this paper we focus on symmetric-key watermarking, where both the
watermarking and verification procedures share a secret key. This is most
suitable for proprietary language models that served via an API. We imagine
that the vendor would watermark all outputs, and also provide a second API to
query the verification procedure. Alternatively, one could publish the key,
enabling anyone to run the verification procedure.

Watermarking TaxonomyParameters: Key $k$, Sampling $\mathcal{C}$, Randomness
$\mathcal{R}$Inputs: Probs
$\mathcal{D}_{n}=\\{\lambda^{n}_{1},\,\cdots,\lambda^{n}_{d}\\}$, Tokens
$\\{T_{i}\\}_{i<n}$Output: Next token
$T_{n}\leftarrow\mathcal{C}(\mathcal{R}_{k}(\\{T_{i}\\}_{i<n}),\mathcal{D}_{n})$Parameters:
Key $k$, Score $\mathcal{S}$, Threshold $p$Inputs: Text $T$Output: Decision
$\mathcal{V}\leftarrow\text{P}_{0}\left(\mathcal{S}<\mathcal{S}_{k}(T)\right)<p$+Marking
$\mathcal{W}$Verification $\mathcal{V}$Randomness Source $\mathcal{R}$Inputs:
Tokens $\\{T_{i}\\}_{i<n}$ Output: Random value
$r_{n}=\mathcal{R}_{k}(\\{T_{i}\\}_{i<n})$Text-dependent. Hash function $h$.
Context length H(R2) Min
Hash$r_{n}=\text{min}\left(h\left(T_{n-1}\mathbin{\|}k\right),\,\cdots,h\left(T_{n-H}\mathbin{\|}k\right)\right)$(R1)
Sliding
Window$r_{n}=h\left(T_{n-1}\mathbin{\|}\,\cdots\mathbin{\|}T_{n-H}\mathbin{\|}k\right)$(R3)
FixedKey length L. Expand $k$ topseudo-random sequence
$\\{r^{k}_{i}\\}_{i<L}$.$r_{n}=r^{k}_{n\text{ (mod L)}}$Sampling algorithm
$\mathcal{C}$ & Per-token statistic $s$Inputs: Random value
$r_{n}=\mathcal{R}_{k}(\\{T_{i}\\}_{i<n})$, Probabilities
$\mathcal{D}_{n}=\\{\lambda^{n}_{1},\,\cdots,\lambda^{n}_{d}\\}$, Logits
$\mathcal{L}_{n}=\\{l^{n}_{1},\,\cdots,l^{n}_{d}\\}$(C3) BinaryBinary
alphabet.$T_{n}\leftarrow 0$ if $r_{n}<\lambda^{n}_{0}$, else $1$.
$s(T_{n},r)=\begin{cases}-\log(r)\text{ if }T_{n}=1\\\ -\log(1-r)\text{ if
}T_{n}=0\\\ \end{cases}$(C2) Inverse Transform$\pi$ keyed permutation. $\eta$
scaling func.$T_{n}\leftarrow\pi_{k}\left(\min\limits_{j\leq
d}\sum\limits_{i=1}^{j}\lambda^{n}_{\pi_{k}(i)}\geq
r_{n}\right)$$s(T_{n},r)=|r-\eta\left(\pi^{-1}_{k}(T_{n})\right)|$(C1)
Exponential$h$ keyed hash function.
$T_{n}\leftarrow\operatorname*{arg\,max}\limits_{i\leq
d}\left\\{\frac{\log\left(h_{r_{n}}\left(i\right)\right)}{\lambda^{n}_{i}}\right\\}$$s(T_{n},r)=-\log(1\\!-\\!h_{r}(T_{n}))$(C4)
Distribution-shiftBias $\delta$, Greenlist size $\gamma$. Keyed permutation
$\pi$. $T_{n}$ sampled from
$\widetilde{\mathcal{L}}_{n}=\\{l^{n}_{i}+\delta\text{ if
}\pi_{r_{n}}(i)<\gamma d\text{ else }l^{n}_{i}\,,1\leq i\leq
d\\}$$s(T_{n},r)=1\text{ if }\pi_{r}(T_{n})<\gamma d\text{ else }0$Score
$\mathcal{S}$Inputs: Per-token statistics $s_{i,j}=s(T_{i},r_{j})$, where
$r_{j}=\mathcal{R}_{k}(\\{T_{l}\\}_{l<j}))$. # Tokens $N$.(S3) Edit
Score$\mathcal{S}_{\text{edit}}^{\psi}=s^{\psi}(N,N)$,
$s^{\psi}(i,j)=\min\begin{cases}s^{\psi}(i-1,j-1)+s_{i,j}\\\
s^{\psi}(i-1,j)+\psi\\\ s^{\psi}(i,j-1)+\psi\\\ \end{cases}$(S1) Sum
Score$\mathcal{S}_{\text{sum}}\\!=\\!\sum_{i=1}^{N}s_{i,i}$(S2) Align
Score$\mathcal{S}_{\text{align}}\\!=\\!\min\limits_{0\leq
j<N}\sum\limits_{i=1}^{N}s_{i,(i+j)\text{ mod}(N)}$ Figure 8: Watermarking
design blocks. There are three main components: randomness source, sampling
algorithm (and associated per-token statistics), and score function. Each
solid box within each of these three components (dashed) denotes a design
choice. The choice for each component is independent and offers different
trade-offs.

###  7.2 Watermark Design Space

Designing a good watermark is a balancing act. For instance, replacing every
word of the output with [WATERMARK] would achieve high recall but destroy the
utility of the model.

Existing proposals have cleverly crafted marking procedures that are meant to
preserve quality, provide high precision and recall, and achieve a degree of
robustness. Despite their apparent differences, we realized they can all be
expressed within a unified framework:

  * •

The marking procedure $\mathcal{W}$ contains a randomness source $\mathcal{R}$
and a sampling algorithm $\mathcal{C}$. The randomness source $\mathcal{R}$
produces a (pseudo-random) value $r_{n}$ for each new token, based on the
secret key $k$ and the previous tokens $T_{0},\cdots,T_{n-1}$. The sampling
algorithm $\mathcal{C}$ uses $r_{n}$ and the model’s next token distribution
$\mathcal{D}$ to a token.

  * •

The verification procedure $\mathcal{V}$ is a one-tailed significance test
that computes a $p$-value for the null hypothesis that the text is not
watermarked. The procedure compares this $p$-value to a threshold, which
enables control over the watermark’s precision and recall. In particular, we
compute a per-token score $s_{n,m}\coloneqq s(T_{n},r_{m})$ for each token
$T_{n}$ and randomness $r_{m}$, aggregate them to obtain an overall score
$\mathcal{S}$, and compute a $p$-value from this score. We consider all
overlaps $s_{n,m}$ instead of only $s_{n,n}$ to support scores that consider
misaligned randomness and text after perturbation.

Next, we show how each scheme we consider falls within this framework, each
with its own choices for $\mathcal{R},\mathcal{C},\mathcal{S}$.

####  7.2.1 Randomness source $\mathcal{R}$

We distinguish two main ways of generating the random values $r_{n}$, _text-
dependent_ (computed as a deterministic function of the prior tokens) vs
_fixed_ (computed as a function of the token index). Both approaches use the
standard heuristic of applying a keyed function (typically, a PRF) to some
data, to produce pseudorandom values that can be treated as effectively random
but can also be reproduced by the verification procedure.

Aaronson and Kirchner [5] and Kirchenbauer et al. [1] use text-dependent
randomness: $r_{n}=f\left(T_{0},\,\cdots,T_{n-1},k\right)$. This scheme has
two parameters: the length of the token context window (which we call the
window size H) and the aggregation function $f$. Aaronson and Kirchner [5]
proposed using the hash of the concatenation of previous tokens,
$f:=h\left(T_{n-1}\mathbin{\|}\,\cdots\mathbin{\|}T_{n-H}\mathbin{\|}k\right)$;
we call this (R1) sliding window. Kirchenbauer et al. [1] used this with a
window size of $H=1$ and also introduced an alternate aggregation function
$f:=\text{min}\left(h\left(T_{n-1}\mathbin{\|}k\right),\,\cdots,h\left(T_{n-H}\mathbin{\|}k\right)\right)$.
We call this last aggregation function (R2) min hash. While these two schemes
propose specific choices of $H$, other values are possible. We use MarkMyWords
to evaluate a range of values of $H$ with each candidate aggregation function.

Kuditipudi et al. [12] use fixed randomness: $r_{n}=f_{k}(n)$, where $n$ is
the index (position) of the token. We call this (R3) fixed. In practice, they
propose using a fixed string of length $L$ (the key length), which is repeated
across the generation. We test the choice of key length in Section 6.2 In the
extreme case where $L=1$ or $H=0$, both sources are identical, as $r_{n}$ will
be the same value for every token. Zhao et al. [50] explored this option using
the same sampling algorithm as Kirchenbauer et al. [1].

Christ et al. [6] proposed setting a target entropy for the context window
instead of fixing a window size. This allows to set a lower bound on the
security parameter for the model’s undetectability. However, setting a fixed
entropy makes for a less efficient detector since all context window lengths
must be tried in order to detect a watermark. Furthermore, in practice,
provable undetectability is not needed to achieve optimal quality: we chose to
keep using a fixed-size window for increased efficiency.

####  7.2.2 Sampling algorithm $\mathcal{C}$

We now give more details about the four sampling algorithms initially
presented in Table II.

(C1) Exponential. Introduced by Aaronson and Kirchner [5] and also used by
Kuditipudi et al. [12]. It relies on the Gumbel-max trick. Let
$\mathcal{D}_{n}=\left\\{\lambda^{n}_{i}\,,1\leq i\leq d\right\\}$ be the
distribution of the language model over the next token. The exponential scheme
will select the next token as:

$\displaystyle T_{n}=\operatorname*{arg\,max}\limits_{i\leq
d}\left\\{\frac{\log\left(h_{r_{n}}\left(i\right)\right)}{\lambda^{n}_{i}}\right\\}$
(1)

where $h$ is a keyed hash function using $r_{n}$ as its key. The per-token
variable used in the statistical test is either $s_{n}=h_{r_{n}}(T_{n})$ or
$s_{n}=-\log\left(1-h_{r_{n}}(T_{n})\right)$. Aaronson and Kirchner [5] and
Kuditipudi et al. [12] both use the latter quantity. We argue the first
variable provides the same results, and unlike the log-based variable, the
distribution of watermarked variables can be expressed analytically (see
Section .4 for more details). We align with previous work and use the $\log$
for MarkMyWords.

(C2) Inverse transform. Kuditipudi et al. [12] introduce inverse transform
sampling. They derive a random permutation using the secret key $\pi_{k}$. The
next token is selected as follows:

$\displaystyle T_{n}=\pi_{k}\left(\min\limits_{j\leq
d}\sum\limits_{i=1}^{j}\lambda^{n}_{\pi_{k}(i)}\geq r_{n}\right)$ (2)

which is the smallest index in the inverse permutation such that the CDF of
the next token distribution is at least $r_{n}$. Kuditipudi et al. [12]
propose to use $s_{n}=|r_{n}-\eta\left(\pi^{-1}_{k}(T_{n})\right)|$ as a the
test variable, where $\eta$ normalizes the token index to the $[0,1]$ range.

(C3) Binary. Christ et al. [6] propose a different sampling scheme for binary
token alphabets — however, it can be applied to any model by using a bit
encoding of the tokens. In our implementation, we rely on a Huffman encoding
of the token set, using frequencies derived from a large corpus of natural
text. In this case, the distribution over the next token reduces to a single
probability $p_{n}$ that token “0” is ed next, and $1-p$ that “1” is ed. The
sampling rule s 0 if $r_{n}<p$, and 1 otherwise. The test variable for this
case is $s_{n}=-\log\left(T_{n}r_{n}+(1-T_{n})(1-r_{n})\right)$.

(C4) Distribution-shift. Kirchenbauer et al. [1] propose the distribution-
shift scheme. It produces a modified distribution $D_{n}$ from which the next
token is sampled. Let $\delta>0$ and $\gamma\in[0,1]$ be two system
parameters, and $d$ be the number of tokens. The scheme constructs a
permutation $\pi_{r_{n}}$, seeded by the random value $r_{n}$, which is used
to define a “green list,” containing tokens $T$ such that
$\pi_{r_{n}}(T)<\delta d$. It then adds $\delta$ to green-list logits. This
modified distribution is then used by the model to sample the next token. The
test variable $s_{n}$ is a bit equal to “1” if $T_{n}$ is in the green list
defined by $\pi_{r_{n}}$, and “0” if not.

The advantage of this last scheme over the others is that it preserves the
model’s diversity: for a given key, the model will still generate diverse
outputs. In contrast, for a given secret key and a given prompt, the first
three sampling strategies will always produce the same result, since the
randomness value $r_{n}$ will be the same. Kuditipudi et al. [12] tackles this
by randomly offseting the key sequence of fixed randomness for each
generation. We introcude a skip probability $p$ for the same effect on text-
dependent randomness. Each token is selected without the marking strategy with
probability $p$. In the interest of space, we leave a detailed discussion of
generation diversity in Section .1.

Another advantage of the distribution-shift scheme is that it can also be used
at any temperature, by applying the temperature scaling _after_ using the
scheme to modify the logits. Other models apply temperature before
watermarking.

However the distribution-shift scheme is not indistinguishable from the
original model, as discussed earlier in Section 2.3.

####  7.2.3 Score Function $\mathcal{S}$

To determine whether an $N$-token text is watermarked, we compute a score over
per-token statistics. This score is then subject to a one-tailed statistical
test where the null hypothesis is that the text is not watermarked. In other
words, if its $p$-value is under a fixed threshold, the text is watermarked.
Different works propose different scores.

(S1) Sum score. Aaronson and Kirchner [5] and Kirchenbauer et al. [1] take the
sum of all individual per-token statistics:

$\displaystyle\mathcal{S}_{\text{sum}}=\sum_{i=1}^{N}s_{i}=\sum_{i=1}^{N}s(T_{i},r_{i}).$
(3)

This score requires the random values $r_{i}$ and the tokens $T_{i}$ to be
aligned. This is not a problem when using text-dependent randomness, since the
random values are directly obtained from the tokens. However, this score is
not suited for fixed randomness: removing one token at the start of the text
will offset the values of $r_{i}$ for the rest of the text and remove the
watermark. The use of the randomness shift to increase diversity will have the
same effect.

(S2) Alignment score. Proposed by Kuditipudi et al. [12], the alignment score
aims to mitigate the misalignment issue mentioned earlier. Given the sequence
of random values $r_{i}$ and the sequence of tokens $T_{i}$, the verification
process now computes different versions of the per-token test statistic for
each possible overlap of both sequences $s_{i,j}=s(T_{i},r_{j})$. The
alignment score is defined as:

$\displaystyle\mathcal{S}_{\text{align}}=\min\limits_{0\leq
j<N}\sum\limits_{i=1}^{N}s_{i,(i+j)\text{ mod}(N)}$ (4)

(S3) Edit score. Similar to the alignment score, Kuditipudi et al. [12]
propose the edit score as an alternative for dealing with the misalignment
issue. It comes with an additional parameter $\psi$ and is defined as
$\mathcal{S}_{\text{edit}}^{\psi}=s^{\psi}(N,N)$, where

$\displaystyle s^{\psi}(i,j)$
$\displaystyle=\min\begin{cases}s^{\psi}(i-1,j-1)+s_{i,j}\\\
s^{\psi}(i-1,j)+\psi\\\ s^{\psi}(i,j-1)+\psi\\\ \end{cases}$ (5)

In all three cases, the average value of the score for watermarked text will
be lower than for non-watermarked text. In the case of the sum score, the
previous works use the $z$-test on the score to determine whether the text is
watermarked, but it is also possible, or even better in certain situations, to
use a different statistical test according to Fernandez et al. [51]. When
possible, we derive the exact distribution of the scores under the null
hypothesis (see Section .2) which is more precise than the $z$-test. When it
is not, we rely on an empirical T-test, as proposed by Kuditipudi et al. [12]

###  7.3 Limitations of the Building Blocks

While we design the blocks to be as independent as possible, some combinations
of the scheme and specific parameters are obviously sub-optimal. Here, we list
a few of these subpar block combinations as a guide for practitioners.

  * •

The sum score (S1) is not robust for fixed randomness (R3).

  * •

The alignment score (S2) does not make sense for the text-dependent randomness
(R1, R2) since misalignment is not an issue.

  * •

The edit score (S3) has a robustness benefit since it can support local
misalignment caused by token insertion, deletion, or swapping. However, using
it with text-dependent randomness (R1, R2) only makes sense for a window size
of 1: for longer window sizes, swapping, adding, or removing tokens would
actually change the random values themselves, and not just misalign them.

  * •

Finally, in the corner case when a window size of 0 for the text-dependent
randomness (R1, R2) or when a random sequence length of 1 for the fixed
randomness (R3), both the alignment score (S2) and the edit score (S3) are
unnecessary since all random values are the same and misalignment is not
possible.

In our experiments (Section 5), we test all reasonable configurations of the
randomness source, the sampling protocol, and the verification score, along
with their parameters. We list the evaluated combinations in Table V. The edit
score is too inefficient to be run on all configurations, instead we rely on
the sum and align scores. We hope to not only fairly compare the prior works
but also investigate previously unexplored combinations in the design space
that can produce a better result.

TABLE V: Tested combinations in the design space, using notations from Fig. 8.
We only tested the edit score S3 on a subset of watermarks.
The distribution of non-watermarked scores is known for orange configurations and unknown for blue configuration. We rely on empirical T-tests [12] for blue configurations.  |  C4 Distribution Shift |  C1 Exponential |  C2 Binary |  C3 Inverse Transform
---|---|---|---|---
S1+R1 | X | X | X | X
S1+R2 | X | X | X | X
S2+R3 | X | X | X | X
S3+R3 | X |  |  |

###  7.4 Analysis of the edit score.

We analyzed the tamper-resistance of the edit score on a subset of watermarks
(distribution-shift with $\delta=2.5$ at a temperature of 1, for key lengths
between 1 and 1024). We tried various $\psi$ values between 0 and 1 for the
edit distance, and compared the tamper-resistance and watermark size of the
resulting verification procedures to the align score. Using an edit distance
does improve tamper-resistance for key lengths under 32, but at a large
efficiency cost: for key lengths above 8, the edit score size is at least
twice that of the align score. We do not recommend using an edit score on low
entropy models such as Llama-2 chat.

##  8 Summary

Our empirical analysis demonstrates existing watermarking schemes are ready
for deployment, providing effective methods to fingerprint machine-generated
text. Notably, we can watermark Llama 2, a low-entropy model, with minimal
quality loss, and detect the watermark with 100 tokens or less. We also show
that they provide a non-trivial amount of tamper-resistance against simple
attempts to remove the watermark.

We challenge the perceived necessity for watermark indistinguishability: the
solution proposed in Kirchenbauer et al. [1] can watermark models more
efficiently than alternatives without degrading the model’s quality, despite
not being provably indistinguishable.

Finally, we provide MarkMyWords, a benchmark to compare existing and future
watermarking schemes. We release our code in the hope it facilitates
evaluation of watermarking schemes and advances the ongoing discussion on the
desirable properties of watermarking schemes for large language models.

## References

  * Kirchenbauer et al. [2023] J. Kirchenbauer, J. Geiping, Y. Wen, J. Katz, I. Miers, and T. Goldstein, “A watermark for large language models,” in _Proceedings of the 40th International Conference on Machine Learning_ , ser. Proceedings of Machine Learning Research, A. Krause, E. Brunskill, K. Cho, B. Engelhardt, S. Sabato, and J. Scarlett, Eds., vol. 202. PMLR, Jul. 2023, pp. 17 061–17 084. [Online]. Available: https://proceedings.mlr.press/v202/kirchenbauer23a.html
  * Lim et al. [2021] E. Lim, G. Tan, T. K. Hock, and T. Lee, “Hacking humans with ai as a service,” 2021, dEF CON 29. [Online]. Available: urllinktotalkabstractifany
  * Goldstein et al. [2023] J. A. Goldstein, G. Sastry, M. Musser, R. DiResta, M. Gentzel, and K. Sedova, “Generative language models and automated influence operations: Emerging threats and potential mitigations,” 2023.
  * OpenAI [2023a] OpenAI, “Gpt-4 system card,” 2023. [Online]. Available: https://cdn.openai.com/papers/gpt-4-system-card.pdf
  * Aaronson and Kirchner [2022] S. Aaronson and H. Kirchner, “Watermarking GPT outputs,” Dec. 2022. [Online]. Available: https://www.scottaaronson.com/talks/watermark.ppt
  * Christ et al. [2023] M. Christ, S. Gunn, and O. Zamir, “Undetectable watermarks for language models,” Cryptology ePrint Archive, Paper 2023/763, 2023. [Online]. Available: https://eprint.iacr.org/2023/763
  * Chakraborty et al. [2023] S. Chakraborty, A. S. Bedi, S. Zhu, B. An, D. Manocha, and F. Huang, “On the possibilities of AI-generated text detection,” Apr. 2023. [Online]. Available: http://arxiv.org/abs/2304.04736
  * Sadasivan et al. [2023] V. S. Sadasivan, A. Kumar, S. Balasubramanian, W. Wang, and S. Feizi, “Can AI-generated text be reliably detected?” Mar. 2023. [Online]. Available: http://arxiv.org/abs/2303.11156
  * Jiang et al. [2023] Z. Jiang, J. Zhang, and N. Z. Gong, “Evading watermark based detection of AI-generated content,” May 2023. [Online]. Available: http://arxiv.org/abs/2305.03807
  * Krishna et al. [2023] K. Krishna, Y. Song, M. Karpinska, J. Wieting, and M. Iyyer, “Paraphrasing evades detectors of AI-generated text, but retrieval is an effective defense,” Mar. 2023. [Online]. Available: http://arxiv.org/abs/2303.13408
  * Liang et al. [2022] P. Liang _et al._ , “Holistic evaluation of language models,” Nov. 2022. [Online]. Available: http://arxiv.org/abs/2211.09110
  * Kuditipudi et al. [2023] R. Kuditipudi, J. Thickstun, T. Hashimoto, and P. Liang, “Robust distortion-free watermarks for language models,” Jul. 2023. [Online]. Available: http://arxiv.org/abs/2307.15593
  * [13] “Ensuring Safe, Secure, and Trustworthy AI,” https://www.whitehouse.gov/wp-content/uploads/2023/07/Ensuring-Safe-Secure-and-Trustworthy-AI.pdf.
  * Kamaruddin et al. [2018] N. S. Kamaruddin, A. Kamsin, L. Y. Por, and H. Rahman, “A review of text watermarking: Theory, methods, and applications,” _IEEE Access_ , 2018.
  * [15] S. G. Rizzo, F. Bertini, D. Montesi, and C. Stomeo, “Text watermarking in social media,” in _Proceedings of the IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining 2017_. Association for Computing Machinery.
  * Taleby Ahvanooey et al. [2016] M. Taleby Ahvanooey, H. Dana Mazraeh, and S. Tabasi, “An innovative technique for web text watermarking (aitw),” _Information Security Journal: A Global Perspective_ , 2016.
  * Cox et al. [2005] I. J. Cox, T. Kalker, G. Pakura, and M. Scheel, “Information transmission and steganography,” in _Digital Watermarking_ , M. Barni, I. Cox, T. Kalker, and H.-J. Kim, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2005, pp. 15–29.
  * Majeed et al. [2021] M. A. Majeed, R. Sulaiman, Z. Shukur, and M. K. Hasan, “A review on text steganography techniques,” _Mathematics_ , vol. 9, no. 21, 2021.
  * Hopper et al. [2009] N. Hopper, L. von Ahn, and J. Langford, “Provably secure steganography,” _IEEE Transactions on Computers_ , 2009.
  * Ziegler et al. [2019] Z. Ziegler, Y. Deng, and A. Rush, “Neural linguistic steganography,” in _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , K. Inui, J. Jiang, V. Ng, and X. Wan, Eds. Hong Kong, China: Association for Computational Linguistics, Nov. 2019, pp. 1210–1215. [Online]. Available: https://aclanthology.org/D19-1115
  * Xiang et al. [2020] L. Xiang, S. Yang, Y. Liu, Q. Li, and C. Zhu, “Novel linguistic steganography based on character-level text generation,” _Mathematics_ , vol. 8, no. 9, 2020.
  * Kang et al. [2020] H. Kang, H. Wu, and X. Zhang, “Generative text steganography based on LSTM network and attention mechanism with keywords,” _Electronic Imaging_ , 2020. [Online]. Available: https://api.semanticscholar.org/CorpusID:226143233
  * Cao et al. [2022] Y. Cao, Z. Zhou, C. Chakraborty, M. Wang, Q. M. J. Wu, X. Sun, and K. Yu, “Generative steganography based on long readable text generation,” _IEEE Transactions on Computational Social Systems_ , pp. 1–11, 2022.
  * OpenAI [2021] OpenAI, “Gpt-2-output-dataset/detector at master $\cdot$ openai/gpt-2-output-dataset,” 2021. [Online]. Available: https://github.com/openai/gpt-2-output-dataset/tree/master/detector
  * OpenAI [2023b] ——, “New AI classifier for indicating AI-written text,” Jan. 2023. [Online]. Available: https://openai.com/blog/new-ai-classifier-for-indicating-ai-written-text
  * Gehrmann et al. [2019] S. Gehrmann, H. Strobelt, and A. Rush, “GLTR: Statistical detection and visualization of generated text,” in _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics: System Demonstrations_. Florence, Italy: Association for Computational Linguistics, Jul. 2019, pp. 111–116.
  * Mitchell et al. [2023] E. Mitchell, Y. Lee, A. Khazatsky, C. D. Manning, and C. Finn, “DetectGPT: Zero-shot machine-generated text detection using probability curvature,” in _Proceedings of the 40th International Conference on Machine Learning_ , ser. ICML’23. Honolulu, Hawaii, USA: JMLR.org, 2023.
  * Bakhtin et al. [2019] A. Bakhtin, S. Gross, M. Ott, Y. Deng, M. Ranzato, and A. Szlam, “Real or fake? Learning to discriminate machine from human generated text,” Nov. 2019. [Online]. Available: http://arxiv.org/abs/1906.03351
  * Zellers et al. [2019] R. Zellers, A. Holtzman, H. Rashkin, Y. Bisk, A. Farhadi, F. Roesner, and Y. Choi, “Defending against neural fake news,” in _Advances in Neural Information Processing Systems_ , H. Wallach, H. Larochelle, A. Beygelzimer, F. dAlché-Buc, E. Fox, and R. Garnett, Eds., vol. 32. Curran Associates, Inc., 2019. [Online]. Available: https://proceedings.neurips.cc/paper_files/paper/2019/file/3e9f0fc9b2f89e043bc6233994dfcf76-Paper.pdf
  * Ippolito et al. [2020] D. Ippolito, D. Duckworth, C. Callison-Burch, and D. Eck, “Automatic detection of generated text is easiest when humans are fooled,” May 2020. [Online]. Available: http://arxiv.org/abs/1911.00650
  * Uchendu et al. [2020] A. Uchendu, T. Le, K. Shu, and D. Lee, “Authorship attribution for neural text generation,” in _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , B. Webber, T. Cohn, Y. He, and Y. Liu, Eds. Online: Association for Computational Linguistics, Nov. 2020, pp. 8384–8395. [Online]. Available: https://aclanthology.org/2020.emnlp-main.673
  * Fagni et al. [2021] T. Fagni, F. Falchi, M. Gambini, A. Martella, and M. Tesconi, “TweepFake: About detecting deepfake tweets,” _PLOS ONE_ , vol. 16, no. 5, pp. 1–16, May 2021. [Online]. Available: https://doi.org/10.1371/journal.pone.0251415
  * Fairoze et al. [2023] J. Fairoze, S. Garg, S. Jha, S. Mahloujifar, M. Mahmoody, and M. Wang, “Publicly detectable watermarking for language models,” 2023.
  * Miller [1994] G. A. Miller, “WordNet: A lexical database for english,” in _Human Language Technology: Proceedings of a Workshop Held at Plainsboro, New Jersey, March 8-11, 1994_ , 1994. [Online]. Available: https://aclanthology.org/H94-1111
  * Finlay and Argos Translate [2021] P. Finlay and C. Argos Translate, “Argos translate,” Aug. 2021. [Online]. Available: https://github.com/argosopentech/argos-translate
  * Klein et al. [2017] G. Klein, Y. Kim, Y. Deng, J. Senellart, and A. Rush, “OpenNMT: Open-source toolkit for neural machine translation,” in _Proceedings of ACL 2017, System Demonstrations_. Vancouver, Canada: Association for Computational Linguistics, Jul. 2017, pp. 67–72. [Online]. Available: https://www.aclweb.org/anthology/P17-4012
  * Liu et al. [2023] Y. Liu, D. Iter, Y. Xu, S. Wang, R. Xu, and C. Zhu, “G-Eval: NLG Evaluation using GPT-4 with Better Human Alignment,” 2023, arXiv:2303.16634.
  * Naismith et al. [2023] B. Naismith, P. Mulcaire, and J. Burstein, “Automated evaluation of written discourse coherence using GPT-4,” in _Proceedings of the 18th Workshop on Innovative Use of NLP for Building Educational Applications (BEA 2023)_ , 2023.
  * [39] C.-H. Chiang and H. yi Lee, “Can large language models be an alternative to human evaluations?” in _ACL 2023_.
  * Hackl et al. [2023] V. Hackl, A. E. Müller, M. Granitzer, and M. Sailer, “Is GPT-4 a reliable rater? evaluating consistency in GPT-4’s text ratings,” _Frontiers in Education_ , vol. 8, 2023.
  * Wang et al. [2023] J. Wang, Y. Liang, F. Meng, Z. Sun, H. Shi, Z. Li, J. Xu, J. Qu, and J. Zhou, “Is ChatGPT a Good NLG Evaluator? A Preliminary Study,” 2023, arXiv:2303.04048.
  * Kocmi and Federmann [2023] T. Kocmi and C. Federmann, “Large language models are state-of-the-art evaluators of translation quality,” 2023, arXiv:2302.14520.
  * Chen et al. [2023] Y. Chen, R. Wang, H. Jiang, S. Shi, and R. Xu, “Exploring the use of large language models for reference-free text quality evaluation: An empirical study,” 2023, arXiv:2304.00723.
  * Touvron et al. [2023] H. Touvron _et al._ , “Llama 2: Open foundation and fine-tuned chat models,” Jul. 2023. [Online]. Available: http://arxiv.org/abs/2307.09288
  * Holtzman et al. [2020] A. Holtzman, J. Buys, L. Du, M. Forbes, and Y. Choi, “The curious case of neural text degeneration,” in _International Conference on Learning Representations_ , 2020. [Online]. Available: https://openreview.net/forum?id=rygGQyrFvH
  * Welleck et al. [2020] S. Welleck, I. Kulikov, S. Roller, E. Dinan, K. Cho, and J. Weston, “Neural text generation with unlikelihood training,” in _International Conference on Learning Representations_ , 2020. [Online]. Available: https://openreview.net/forum?id=SJeYe0NtvH
  * Fawcett [2006] T. Fawcett, “An introduction to ROC analysis,” _Pattern Recognition Letters_ , vol. 27, no. 8, pp. 861–874, 2006. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S016786550500303X
  * Wolf et al. [2020] T. Wolf _et al._ , “Transformers: State-of-the-art natural language processing,” in _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations_. Online: Association for Computational Linguistics, Oct. 2020, pp. 38–45. [Online]. Available: https://aclanthology.org/2020.emnlp-demos.6
  * goo [2023] “Google Translate,” 2023, https://translate.google.com/.
  * Zhao et al. [2023] X. Zhao, P. Ananth, L. Li, and Y.-X. Wang, “Provable robust watermarking for ai-generated text,” 2023.
  * Fernandez et al. [2023] P. Fernandez, A. Chaffin, K. Tit, V. Chappelier, and T. Furon, “Three bricks to consolidate watermarks for large language models,” Jul. 2023. [Online]. Available: http://arxiv.org/abs/2308.00113

###  .1 Techniques to Allow Diverse Generation

In order to add some diversity to the generations, there are different
strategies.

  1. 1.

For a fixed randomness source, Kuditipudi et al. [12] proposes to randomly
shift the sequence of random values $\\{r^{k}_{i}\\}$ by an offset $s$, such
that $r_{n}=r^{k}_{(s+n)\text{ (mod L)}}$. This means there are a total of $L$
possible unique values for $r_{n}$ depending on $s$. For a text-dependent
randomness source, this trick does not work.

  2. 2.

Instead, one natural strategy is to randomly skip the watermarking selection
procedure for some tokens, and instead sample the next token from the original
multinomial distribution. We denote S this skip probability.

  3. 3.

Another strategy, discussed by Christ et al. [6], is to only start
watermarking text after enough empirical entropy has been generated: the first
tokens are selected without a watermark. This accomplishes the same effect,
and guarantees undetectability. However, as discussed in the paper’s appendix,
a user not wanting to generate watermarked text can simply run the model, keep
the first few tokens, add them to the prompt, and start again: After repeating
this step enough time, they can generate arbitrarily long text without a
watermark. This seems like a larger practical drawback than loosing the
guarantee of undetectability, thus we use the skip probability instead for
promoting diversity.

###  .2 Exact Distribution of the Score Function

The null hypothesis distribution for the exponential scheme with the regular
test variable is an Irwin-Hall distribution centered with parameter $N$ (whose
average quickly converges to a normal distribution centered in 0.5 with
variance $\frac{1}{12N}$). When using the log test variable, the null
distribution is the Erlang distribution with parameter $N$. The binary scheme
also follows an Erlang distribution, but with many more tokens since each
token is broken down into a binary vector. The distribution-shift scheme has a
null distribution a binomial with parameters $\gamma,N$. We derive these
distributions in the appendix.

However, for both other scores, and for the inverse transform, the null
hypothesis distribution is too complex to compute. In these cases,
verification uses a permutation test, as described in Kuditipudi et al..
Instead of comparing the score to a known distribution, we sample independent
random sequences $\tilde{r}_{i}$ and compute the score of the text for that
randomness: these trials are distributed like non watermarked text, so we can
use them to compute an empirical p-value.

###  .3 Additional analysis

Here we present additional figures to support the main text.

Figure 9: Same plot as Fig. 1, but for a quality threshold of 10%, and a
minimum robustness of 0.2. The same conclusions from the main figure still
hold. Figure 10: Correlation between robustness metric and attack success. On
the right, for the Russian translation attack. On the left, for the GPT
paraphrasing attack. Each dot is a unique watermark parameter setting. Figure
11: Size and quality for varying biases, at T=0.3 and T=1. The quality is
relative to the quality of the non-watermarked model at the given temperature.
Figure 12: Size and tamper resistance as a function of key lengths (only using
distribution-shift schemes with $\delta\leq 2$).

###  .4 Exponential scheme proofs

We use the same notation as in Fig. 8. In particular, $h_{s}$ is a secure hash
function mapping strings to $[0,1]$ with seed $s$, $k$ is a key selected
uniformly at random amongst a set of keys $K$. Consider an execution of the
language model which produced tokens $T_{1},\ldots,T_{n}$ up until now
(including the prompt). The next token distribution is represented as
$\mathcal{D}_{T_{1},\cdots,T_{n}}=\left\\{\lambda_{i},P(T_{n+1}=i\mid
T_{1},\cdots,T_{n})=\lambda_{i}\right\\}$. For an i.i.d randomness source
(producing i.i.d random values), the exponential selection procedure has the
following properties:

  1. P1

For a uniformly random key $k$, the distribution over the next token is the
same as without the watermark.

$\displaystyle P_{k}(\widetilde{T}_{n+1}=i\mid T_{i\leq n})=P(T_{n+1}=i\mid
T_{i\leq n})=\lambda_{i}$ (6)

  2. P2

The expectation of the hash of the next token is equal to the spike
entropy444Spike entropy is defined in [1]. For a discrete distribution
$\mathcal{D}=\left\\{\lambda_{1},\cdots,\lambda_{n}\right\\}$, the spike
entropy $S\left(\mathcal{D},t\right)$ (said modulus i) is defined as
$\sum_{j=1}^{n}\frac{\lambda_{j}}{t+\lambda_{j}}$. of the next token
distribution. This is always larger than the expectation of the hash of the
next token without watermark, only being equal for a degenerate distribution
with only one token having a non-zero probability.

$\displaystyle\begin{split}&\frac{n}{n+1}\geq\mathbb{E}_{k}\left[h_{s}\left(\widetilde{T}_{n+1}\right)\right]=S\left(\mathcal{D}_{T_{1},\cdots,T_{n}},\,1\right)\\\
&S\left(\mathcal{D}_{T_{1},\cdots,T_{n}},\,1\right)=\sum_{j=1}^{d}\frac{\lambda_{j}}{1+\lambda_{j}}\geq\mathbb{E}_{k}\left[h_{s}\left(T_{n+1}\right)\right]=\frac{1}{2}\end{split}$
(7)

When using the sum score, we perform a hypothesis test, where under $H_{0}$
the text is not watermarked, and under $H_{1}$ it is. In particular, let
$\bar{h}=\frac{1}{n}\sum_{i=1}^{n}h_{s}\left(T_{i}\right)$ be the average hash
over a text of $n$ tokens. Let $S_{i}$ be the average spike entropy of modulus
$i$ over the text. $\bar{h}$ follows a Bates distribution under $H_{0}$ with
parameter $n$ (which is well approximated by a Gaussian with average $0.5$ and
variance $\frac{1}{12n}$. The distribution under $H_{1}$ has an average of
$S_{1}$ and asymptotically follows a Gaussian distribution centered in $S_{1}$
with variance $\frac{S_{2}-S_{1}^{2}}{n}$.

##### Proof of P1

Let $r=\mathbf{R}(k,\\{T_{i}\\}_{i<n})$ be our randomness source. We assume
that it is uniformly distributed between 0 and 1, for $k\sim\mathcal{U}(K)$,
with $|K|$ large enough. Since $h_{s}$ is a secure hash function, we posit:

  1. A1

The hash of each token is uniformly distributed:
$h_{r}(i)\sim\mathcal{U}\left([0,1]\right)~{}\forall i,T_{1},\cdots,T_{n}$.

  2. A2

The token hashes $\\{h_{r}(i),\,1\leq i\leq d\\}$ are mutually independent.

We have:

$\displaystyle P_{k}(\widetilde{T}_{n+1}=i|T_{i\leq n})=P_{k}\left\\{\forall
j\neq
i,\,\frac{\log(h_{r}(i))}{\lambda_{i}}>\frac{\log(h_{r}(j))}{\lambda_{j}}\right\\}$
(8)

We can simplify this expression: if $\\{h_{r}(i)\\}_{i}$ are mutually
independent uniformly distributed random variables between 0 and 1, then
$\left\\{\frac{-\log(h_{r}(i))}{\lambda_{i}}\right\\}_{i}$ are mutually
independent exponentially distributed random variables, with parameters
$\\{\lambda_{i}\\}_{i}$. By writing
$u_{i}=-\frac{\log(h_{r}(i))}{\lambda_{i}}$, we then have:

$\displaystyle P_{k}(\widetilde{T}_{n+1}=i|T_{i\leq
n})=P_{k}\left\\{u_{i}<\min_{j\neq i}(u_{j})\right\\}$ (9)

We now use a useful property of exponential random variables: The minimum of a
set of independent exponential random variables of parameters
$\lambda_{1},\cdots,\lambda_{n}$ is also an exponential random variable, with
parameter $\sum_{i=1}^{n}\lambda_{i}$. Thus, $\min_{j\neq
i}(u_{j})\sim\mathrm{Exp}(1-\lambda_{i})$ (since $\lambda_{i}$ are a
probability distribution, they sum to 1, so $\sum_{j\neq
i}\lambda_{j}=1-\lambda_{i}$). We can now finish the proof.

$\displaystyle\begin{split}P_{k}(&\widetilde{T}_{n+1}=i|T_{i\leq
n})=P_{k}\left\\{u_{i}<\min_{j\neq i}(u_{j})\right\\}\\\
&=\int_{0}^{\infty}\lambda_{i}e^{-\lambda_{i}x}\int_{x}^{\infty}(1-\lambda_{i})e^{-(1-\lambda_{i})y}dxdy\\\
&=\lambda_{i}=P(T_{n+1}=i|T_{i\leq n}).\end{split}$ (10)

##### Proof of P2

For a sequence of previous tokens $T_{i\leq n}=T_{1},\cdots,T_{n}$, lets
compute the expected value of the hash of the next token under both the
watermarked and non-watermarked model.

As discussed above, for $k\sim\mathcal{U}(K)$,
$h_{r}(i)\sim\mathcal{U}([0,1])$ and are mutually independent, and we have
$\mathbb{E}_{k}\left[h_{r}(i)\right]=\frac{1}{2}$

For the non-watermarked model, we select a token independently from the key
$k$ or the values $h_{r}(i)$, thus:

$\displaystyle\begin{split}\mathbb{E}_{k}\left[h_{r}\left(T_{n+1}\right)\right]&=\mathbb{E}_{k}\left[\sum_{i=1}^{d}\mathbbm{1}_{\\{T_{n+1}=i\\}}h_{r}\left(i\right)\right]\\\
&=\sum_{i=1}^{d}\mathbb{E}\left[\mathbbm{1}_{\\{T_{n+1}=i\\}}\right]\mathbb{E}_{k}\left[h_{r}\left(i\right)\right]\\\
&=\sum_{i=1}^{d}\frac{1}{2}\lambda_{i}=\frac{1}{2}\end{split}$ (11)

For the watermarked model, token selection is no longer independent from the
key $k$ or the hash values. Instead, we use the notations from the previous
proof to compute this expectation. In particular, we have
$\\{T_{n+1}=i\\}=\left\\{\forall j\neq
i,\,u_{i}<u_{j}\right\\}=\left\\{u_{i}<\min_{j\neq i}(u_{j})\right\\}$, with
$u_{i}$ exponentially distributed with parameter $\lambda_{i}$, and
$\min_{j\neq i}(u_{j})$ exponentially distributed with parameter
$1-\lambda_{i}$, both independent. Also, since
$u_{i}=-\frac{\log(h_{r}(i))}{\lambda_{i}}$, we have
$h_{r}(i)=e^{-u_{i}\lambda_{i}}$.

$\displaystyle\begin{split}\mathbb{E}_{k}&\left[h_{r}\left(T_{n+1}\right)\right]=\mathbb{E}_{k}\left[\sum_{i=1}^{V}\mathbbm{1}_{\\{T_{n+1}=i\\}}h_{r}\left(i\right)\right]\\\
&=\sum_{i=1}^{d}\iint_{0}^{\infty}e^{-\lambda_{i}x}\mathbbm{1}_{x<y}\lambda_{i}e^{-\lambda_{i}x}(1-\lambda_{i})e^{-(1-\lambda_{i})y}dxdy\\\
&=\sum_{i=1}^{d}\frac{\lambda_{i}}{1+\lambda_{i}}\end{split}$ (12)

Thus, the expectation of the watermarked model’s next token hash is equal to
the spike entropy of next token distribution (as defined in [1]). Analysis of
the spike entropy shows that its minimum value is $0.5$, when all but one
token have 0 probability, and its maximum is $\frac{d}{d+1}$, when all tokens
are equiprobable.

##### Verification

The verification procedure computes the average hash value over all tokens in
a text: $\bar{h}=\frac{1}{n}\sum_{i=1}^{n}h_{r}\left(T_{i}\right)$. Let’s
analyze this random variable $\bar{h}$ in both the watermarked and non-
watermarked settings. In the regular case, we can show, for
$k\sim\mathcal{U}(K)$, that $h_{r}\left(T_{i}\right)\sim\mathcal{U}([0,1])$,
for some $x\in[0,1]$:

$\displaystyle\begin{split}P_{k}&\left(h_{r}\left(T_{i}\right)<x\right)\\\
&=\sum_{j=1}^{d}P_{k}\left(\\{T_{i}=j\\}\cap\\{h_{r}\left(i\right)<x\\}\right)\\\
&=\sum_{j=1}^{d}P\left(\\{T_{i}=j\\}\right)P\left(\\{h_{r}\left(i\right)<x\\}\right)=x\end{split}$
(13)

Which is the CDF of a continuous uniform random variable between 0 and 1.
Furthermore, since the randomness source is i.i.d, the ${h_{r}(T_{i})}_{i}$
are independent. Thus $\bar{h}$ is the average of $n$ independent uniform
random variables over $[0,1]$, so it follows a Bates distribution. When $n$
increases to $+\infty$, $\mathcal{B}(n)$ is equivalent to
$\mathcal{N}(0.5,\frac{1}{12n})$. In practice, even for small values of $n$,
the Bates distribution is close to Gaussian.

In the watermarked case, we start by computing the CDF and PDF of the hash of
a single token, $h_{r}\left(T_{i}\right)$.

$\displaystyle\begin{split}&P_{k}\left(h_{r}\left(T_{i}\right)<x\right)=\sum_{j=1}^{d}P_{k}\left(\\{T_{i}=j\\}\cap\\{h_{r}\left(j\right)<x\\}\right)\\\
&=\sum_{j=1}^{d}\iint_{0}^{\infty}\mathbbm{1}_{z<y}\mathbbm{1}_{z>-\frac{\log(z)}{\lambda_{j}}}\lambda_{j}e^{-\lambda_{j}z}(1-\lambda_{j})e^{-(1-\lambda_{j})y}dzdy\\\
&=\sum_{j=1}^{d}\lambda_{j}x^{\frac{1}{\lambda_{j}}}.\end{split}$ (14)

Thus the hash of a token has CDF
$\sum_{j=1}^{d}\lambda_{j}x^{\frac{1}{\lambda_{j}}}$ and PDF
$\sum_{j=1}^{d}x^{\frac{1}{\lambda_{j}}-1}$. Using these formulas, we can
derive higher order moments for the hash:
$\mathbb{E}_{k}\left[h_{r}\left(T_{i}\right)^{m}\right]=\sum_{j=1}^{d}\frac{\lambda_{j}}{1+m\lambda_{j}}$.
In particular, each moment of order $m$ is bounded between 1 and
$\frac{V}{m+V}$. We denote $S_{m}$ to be the average moment of order $m$ over
the text (which happens to also be the average spike entropy of modulus $m$).

We define
$s^{2}_{n}=\sum_{i=1}^{n}\mathbb{E}_{k}\left[\left(h_{r}\left(T_{i}\right)-\mathbb{E}_{k}\left[h_{r}\left(T_{i}\right)\right]\right)^{2}\right]=n\left(S_{2}-S_{1}^{2}\right)$.
Since we assume each hash is independent, thanks to the i.i.d randomness, we
can use Lyapunov’s central limit theorem on the sequence of hash values. In
particular, each hash has bounded moments of all orders (and bounded away from
zero), so all conditions of the theorem apply.

$\displaystyle\begin{split}&\frac{1}{s_{n}}\sum_{i=1}^{n}\left(h_{r}\left(T_{i}\right)-\mathbb{E}_{k}\left[h_{r}\left(T_{i}\right)\right]\right)\xrightarrow[d]{n\rightarrow\infty}\mathcal{N}(0,1)\\\
\implies&\frac{1}{n}\sum_{i=1}^{n}\left(h_{r}\left(T_{i}\right)-\mathbb{E}_{k}\left[h_{r}\left(T_{i}\right)\right]\right)\xrightarrow[d]{n\rightarrow\infty}\mathcal{N}(0,\frac{S_{2}-S_{1}^{2}}{n})\\\
\implies&\left(\bar{h}-S_{1}\right)\xrightarrow[d]{n\rightarrow\infty}\mathcal{N}(0,\frac{S_{2}-S_{1}^{2}}{n})\\\
\implies&\bar{h}\xrightarrow[d]{n\rightarrow\infty}\mathcal{N}(S_{1},\frac{S_{2}-S_{1}^{2}}{n})\\\
\end{split}$ (15)

Thus, as $n$ increases, non watermarked text will have $\bar{h}$ get closer to
0.5, while watermarked text will have $\bar{h}$ get closer to $S_{1}$. In
particular, if we fix a maximum false positive ratio $p$ (number of regular
text mistaken for watermarked text), the detection strategy is to flag text as
watermarked if the probability of $\bar{h}$ in the non-watermarked hypothesis
is lower than $p$, or equivalently,
$1-\Phi_{0.5,\,1/12n}\left(\bar{h}\right)<p$, with $\Phi_{0.5,\,1/12n}$ the
CDF of a Gaussian centered in 0.5 with variance $1/12n$.

Furthermore, given values of $S_{1}$ and $S_{2}$, for large values of $n$, we
can compute the expected false negative ratio of our detector. Given the
quantile $q$ associated with the false positive ratio $p$
($\Phi_{0.5,\,1/12n}\left(q\right)=1-p$), we have
$FN=\Phi_{S_{1},\,(S_{2}-S_{1}^{2})/n}(q)$. This get exponentially lower as
the average entropy $S_{1}$ and $n$ increase.