Black-Box Detection of Language Model Watermarks

## Abstract

Abstract Watermarking has emerged as a promising way to detect LLM-generated text.
To apply a watermark an LLM provider, given a secret key, augments generations with a signal that is later detectable by any party with the same key.
Recent work has proposed three main families of watermarking schemes, two of which focus on the property of preserving the LLM distribution.
This is motivated by it being a tractable proxy for maintaining LLM capabilities, but also by the idea that concealing a watermark deployment makes it harder for malicious actors to hide misuse by avoiding a certain LLM or attacking its watermark.
Yet, despite much discourse around detectability, no prior work has investigated if any of these scheme families are detectable in a realistic black-box setting.
We tackle this for the first time, developing rigorous statistical tests to detect the presence of all three most popular watermarking scheme families using only a limited number of black-box queries. We experimentally confirm the effectiveness of our methods on a range of schemes and a diverse set of open-source models.
Our findings indicate that current watermarking schemes are more detectable than previously believed, and that obscuring the fact that a watermark was deployed may not be a viable way for providers to protect against adversaries.
We further apply our methods to test for watermark presence behind the most popular public APIs: GPT4 , Claude 3 , Gemini 1.0 Pro , finding no strong evidence of a watermark at this point in time.

## 1 Introduction

With the rapid increase in large language model (LLM) capabilities and their widespread adoption, researchers and regulators alike are raising concerns about their potential misuse for generating harmful content [, ].
To tackle this issue, the idea of watermarking, a process of embedding a signal invisible to humans into generated texts, is gaining significant traction.

#### Language model watermarking

More formally, in LLM watermarking [, , , , , , , ] we consider the setting of a *model provider* that offers black-box access to their proprietary model $LM$ while ensuring that each generation $y$ in response to a prompt $q$ can be reliably attributed to the model. To enable this, the provider modifies the generations using a secret watermark key $\xi$, which a corresponding watermark detector can later use to detect whether a given text was generated by $LM$.

The prominent family of *Red-Green* watermarks [, ] achieves this by, at each step of generation, selecting a context-dependent pseudorandom set of logits to be boosted, modifying the model’s next-token distribution.
In contrast to these, the recently proposed families of *Fixed-Sampling* [] and *Cache-Augmented* [, ] schemes have focused on developing watermarks that aim to preserve the output distribution of the LLM, achieving such guarantees in ideal theoretical settings.
This goal can be motivated by two main benefits: (i) it is a tractable proxy for preservation of capabilities of the original LLM, and (ii) intuitively, the deployment of the watermark should become inherently harder to detect for malicious actors that would otherwise be able to avoid or attack the watermark [, , ].

#### Practical detectability

Yet, despite watermark detection being a key concern in current discourse, there have so far been no rigorous investigations into the *practical detectability* of any of the three watermark scheme families.
It thus remains unclear if the distribution preservation guarantees of Fixed-Sampling and Cache-Augmented schemes, that hold in ideal settings, offer any detectability benefits in real-world deployments.
Recent work has even argued that Red-Green schemes, whose detectability has also never been thoroughly studied in realistic settings, avoid some undesirable tradeoffs of distribution-preserving watermarks, and are ultimately more practical [].

#### This work: practical black-box watermark detection

In this work, for the first time, we comprehensively investigate the question of watermark detection in practical real-world settings.
Faithful to how LLMs are exposed in current public deployments, we assume a minimal setting in which the adversary cannot control any input parameters (e.g., temperature, sampling strategy) apart from the prompt $q$, and does not receive any additional information (e.g., log-probabilities) apart from the instruction-tuned model’s textual response $y$.
In this setting, the goal of the adversary is to identify if the model is watermarked and determine which scheme was used.

To this end, we propose rigorous and principled statistical tests for the black-box detection of seven scheme variants of the three most prominent watermark families. Our tests, illustrated in [Fig. 1](#S2.F1), are based on fundamental properties of the three respective scheme families: Red-Green ([Section 2](#S2)), Fixed-Sampling ([Section 3](#S3)), and Cache-Augmented ([Section 4](#S4)) watermarks.
In our extensive experimental evaluation, we find that in practice, both distribution-modifying as well as distribution-preserving schemes are *easily detectable* by our tests, even in the most restricted black-box setting.
Highlighting their practicality, we further test several real-world LLM deployments (GPT4, Claude 3, Gemini 1.0 Pro) and detect no watermarks, suggesting that watermark deployment at this scale is an ongoing challenge.

#### Implications

While the impact of watermarking schemes on model capabilities (point (i) above) remains an interesting avenue for future work, our findings question whether non-detectability (point (ii) above) should be a key focus in the development of LLM watermarks.
Guided by our results, we suspect that avoiding practical detectability may be an inherently hard problem given the fundamental nature of watermarks.
In light of this, we advocate for a more diverse and practically oriented development and evaluation of LLM watermarks, allowing for broader consideration of other relevant properties such as attack robustness, text quality, and efficiency.

#### Main contributions

We make the following key contributions:

- •
We present the first principled and statistically rigorous tests for practical black-box detection of popular LLM watermarks across the three prominent scheme families: Red-Green ([Section 2](#S2)), Fixed-Sampling ([Section 3](#S3)), and Cache-Augmented ([Section 4](#S4)).
- •
We confirm the effectiveness of all our tests in an extensive experimental evaluation across seven schemes and five open-source models, and present additional results that verify the applicability of our tests in real-world settings ([Sections 5.1](#S5.SS1) and [5.2](#S5.SS2)).
- •
We further highlight the practicality of our tests by executing them on several real-world black-box LLM deployments—GPT, Claude, and Gemini ([Section 5.3](#S5.SS3)).

## 2 Detecting Red-Green Watermarks

Figure: Figure 1: Overview of our key contribution. Given black-box textual access to a language model, a client can query the model and run statistical tests to rigorously test for presence of a watermark. In this example, both the test for *Cache-Augmented* watermarks ([Section 4](#S4)) and the test for *Fixed-Sampling* watermarks ([Section 3](#S3)) fail, while the test for *Red-Green* watermarks ([Section 2](#S2)) successfully detects the watermark.
Refer to caption: /html/2405.20777/assets/x1.png

In this section, we introduce our statistical test for detecting watermarks from the *Red-Green* family, illustrated in  [Fig. 1](#S2.F1) (bottom).
To this end, we exploit their core property: applying the watermark introduces a *context-dependent logit bias*, i.e., the model’s output distribution is biased in a way that can greatly vary depending on the last few tokens that were generated (*context*), yet is unaffected by the tokens preceding the context (*prefix*).

We first recall the background related to these schemes.
We then introduce our modeling assumptions, describe the querying strategy we use to obtain the data for the test, and finally describe the test itself.
In [Section 5](#S5), we experimentally confirm the effectiveness of the test in realistic settings and study its query cost, and in [App. C](#A3) explore methods to estimate scheme parameters once a watermark is confirmed.

#### Background

Assume a watermark key $\xi\in\mathbb{N}$, a pseudorandom function (PRF) $f$, and a hashing function $H\colon\mathbb{N}\to\mathbb{N}$.
At each generation step $t$, a Red-Green watermark modifies the logits $l_{1:|V|}$ of tokens from the vocabulary $V$ to promote a subset of tokens (*green tokens*) before applying standard sampling.
We consider two popular variants, LeftHash [] and SelfHash [], both parametrized by $\delta,\gamma\in\mathbb{R}^{+}$, and using $h=1$ and $h=3$ previous tokens as context, respectively.
LeftHash seeds $f$ with $H(y_{t-1})\cdot\xi$, and uses it to split $V$ into $\gamma|V|$ green tokens and remaining *red* tokens.
For each green $i$, it then increases $l_{i}$ by $\delta$.
SelfHash differs by seeding $f$ with $\min(H(y_{t-3}),\ldots,H(y_{t}))\cdot H(y_{t})\cdot\xi$, effectively using a context size of $4$ by including the token $y_{t}$ yet to be generated.
For both schemes, the watermark detector is based on observing a significant number of green tokens in the input text of length $m$, above the expectation of $\gamma m$.
Other schemes from this family include, among else, varying the aggregation function or the context size.

#### Modeling Red-Green watermarks

Assume a setting where the model chooses a token from some restricted set $\Sigma\subset V$, following some *context* $t_{2}$ (longer than the watermark context $h$), which is preceded by a *prefix* $t_{1}$.
We discuss how to construct such a setting shortly.
To model the watermark, we assume the following distribution for $p_{t_{1},t_{2}}(x)$, the probability the model assigns to some $x\in\Sigma$:

$$ $p_{t_{1},t_{2}}(x)=\frac{\exp\left((x^{0}+\delta_{t_{2}}(x)+\varepsilon_{t_{1},t_{2}}(x))/T\right)}{\sum_{w\in\Sigma}\exp\left((w^{0}+\delta_{t_{2}}(w)+\varepsilon_{t_{1},t_{2}}(w))/T\right)}.$ (1) $$

Here, we assume the existence of the *true logit* $x^{0}$, modeling the model bias towards $x$.
The true logit is shifted by $\delta_{t_{2}}(x)$, a $\delta$-Bernoulli random variable, where $\delta\in\mathbb{R}^{+}$ is the watermark parameter introduced above.
Finally, $\varepsilon_{t_{1},t_{2}}(x)$ for different $t_{1},t_{2}$ are iid symmetric error terms with mean 0 0 and variance $\sigma^{2}$.
Applying the *logit* function $p\to\log(p/(1-p))$ to [Eq. 1](#S2.E1), we obtain:

$$ $l_{t_{1},t_{2}}(x)=\frac{x^{0}}{T}+\frac{\delta_{t_{2}}(x)}{T}+\frac{\varepsilon_{t_{1},t_{2}}(x)}{T}-\log\left(\sum_{w\in\Sigma\setminus\{x\}}\exp\left(\frac{w^{0}}{T}+\frac{\delta_{t_{2}}(j)}{T}+\frac{\varepsilon_{t_{1},t_{2}}}{T}\right)\right).$ (2) $$

Approximating the log-sum-exp with a maximum, and WLOG setting $w^{0}=0$ for $w$ which is the maximum in the log-sum-exp (as logits are shift-invariant), the above simplifies to

$$ $l_{t_{1},t_{2}}(x)=x^{0}/T+\delta^{\prime}_{t_{2}}(x)+\varepsilon^{\prime}_{t_{1},t_{2}}(x),$ (3) $$

where $\varepsilon^{\prime}_{t_{1},t_{2}}(x)$ absorbs the previous error terms.
The resulting $\delta^{\prime}_{t_{2}}(x)$ is a random variable that is 0 0 for unwatermarked models, and has $3$ possible values for watermarked models: $\delta/T$ (where $\delta$ is the watermark parameter), if $x$ is the only token from $\Sigma$ that is in the green partition of the vocabulary, $-\delta/T$, if $x$ is in the red partition and some other tokens from $\Sigma$ are in the green partition, and 0 0 otherwise.
Our test is based on detecting cases of $\delta^{\prime}_{t_{2}}(x)\neq 0$ and checking that their occurrence is indeed independent of $t_{1}$, distinguishing model variance from the watermark bias.

#### Querying strategy

Recall that our goal is to steer a model into a setting (via an instruction, as we have no access to the completion model) where it makes a choice from some restricted set $\Sigma$.
Importantly, we want to ensure enough variability in the model’s choices to be able to observe the behavior specific to a Red-Green watermark and perform efficient estimation (in terms of query cost).

Assuming an upper bound $H$ on the context size $h$ of the watermark, we use the following prompt template, parametrized by $t_{1}$ (an arbitrary length string), $d$ (a single token), and a word list $\Sigma$.

Here, $t_{1}$ serves as the prefix, and $t_{2}=d\cdot H$ as the context.
For a watermarked model, changing $t_{2}$ is the only way to change the red-green vocabulary split, which can greatly affect the model’s choice.
For unwatermarked models, while we often see bias towards some choices from $\Sigma$, this bias will not strongly depend on $t_{2}$.
This holds for all context sizes $\leq H$ and most aggregation functions, making our setting and the corresponding test directly applicable to different variants of Red-Green schemes.

In our instantiation (illustrated in [Fig. 1](#S2.F1)), we use $N$ different $t_{1}$ of the form “I bought”, varying the verb, $M$ different values of $d$ from the set of digits, a word list $\Sigma$ of four different plural fruit names, and an example that uses different words to not bias the model towards a specific choice.
We empirically observe that this setup minimizes the chance that the model collapses to a single choice or fails to follow the instruction, which often occurred for similar settings based on repetition of words or numbers outside of natural context.

#### Estimating the logits

To collect the data for the test, we query the model in two phases.
First, we choose different values of $\Sigma$ until we find one where the model does not always make the same choice, inducing $Q_{1}$ total queries.
We set $x$ to be the most commonly observed word from $\Sigma$.
Next, for each $(t_{1},t_{2})$ pair we query the model until we obtain $K$ valid responses (filtering out failures to follow the instruction), inducing $Q_{2}$ additional queries.

We use these samples to estimate the model *logits* corresponding to $x$ as $\hat{l}_{t_{1},t_{2}}(x)=\log\frac{\hat{p}_{t_{1},t_{2}}(x)}{1-\hat{p}_{t_{1},t_{2}}(x)}$, where $\hat{p}_{t_{1},t_{2}}(x)$ is the empirically estimated probability of $x$ in the responses.
The result of the adversary’s querying procedure is a matrix $L_{N\times M}$ (visualized in [Fig. 1](#S2.F1)) of such logit estimates.

#### Testing watermark presence

Finally, we describe the statistical test based on the logit estimates $L_{N\times M}$.
We first estimate $\sigma$, the standard deviation of $\varepsilon^{\prime}_{t_{1},t_{2}}(x)$, as follows:

$$ $\hat{\sigma}^{2}=\text{median}[\text{Var}_{t_{2}}(L)],$ (4) $$

using the empirical median to improve robustness to unpredictable behavior caused by different $t_{1}$.
Then, we calculate the following two binary functions, which flag cases where we believe the model’s probability was affected by a watermark:

$$ $R_{x}(t_{1},t_{2})=\mathbbm{1}\{\hat{l}_{t_{1},t_{2}}(x)-\text{median}[L]<-r\hat{\sigma}\},$ (5) $$

and

$$ $G_{x}(t_{1},t_{2})=\mathbbm{1}\{\hat{l}_{t_{1},t_{2}}(x)-\text{median}[L]>r\hat{\sigma}\},$ (6) $$

with $r\in\mathbb{R}^{+}$ a parameter of the test. In practice, to account for model unpredictability, we use the empirical median conditioned on $t_{1}$ in [Eqs. 5](#S2.E5) and [6](#S2.E6).
For simplicity, let us denote $t_{1}\in\{1,\ldots,N\}$ and $t_{2}\in\{1,\ldots,M\}$.
Let $cnt_{x}(t_{2})=\max\left(\sum_{t_{1}=1}^{N}R_{x}(t_{1},t_{2}),\sum_{t_{1}=1}^{N}G_{x}(t_{1},t_{2})\right)$ count the number of consistently flagged values for fixed $t_{2}$.
We define the following test statistic:

$$ $S_{x}(L)=\max_{t_{2}\in[M]}cnt_{x}(t_{2})-\min_{t_{2}\in[M]}cnt_{x}(t_{2}).$ (7) $$

The null hypothesis of our test is $\forall t_{2}\colon~{}\delta^{\prime}_{t_{2}}(x)=0$, i.e., the model is not watermarked.
To obtain a $p$-value, we apply a Monte Carlo permutation test to $S_{x}$, checking if the flagged values are correlated with $t_{2}$ in a way that indicates a Red-Green watermark.
Namely, we sample a set of permutations $\sigma$ of the matrix $L$ uniformly at random, and calculate a 99% confidence interval of $\Pr[S_{x}(\sigma(L))\geq S_{x}(L)]$, whose upper bound we take as our $p$-value.
When this value is small, we interpret that as evidence of a watermark. Because [Eq. 3](#S2.E3) is permutation invariant when $\delta^{\prime}_{t_{2}}(x)=0$, this ensures that the test does not reject under the null.
This completes our method for detection of Red-Green watermarks.

## 3 Detecting Fixed-Sampling Watermarks

Unlike Red-Green watermarks, the recently proposed *Fixed-Sampling* watermarks do not modify the logit vectors during generation, so estimating the probabilities of model outputs as above is not informative.
Instead, the sampling is fully determined by the rotation of the watermark key, making the natural vector to exploit when detecting this watermark its *lack of diversity*.
Given a prompt for which an unwatermarked model is expected to produce highly diverse outputs, we can use this observation to distinguish between the two, as illustrated in [Fig. 1](#S2.F1) (middle).

As in [Section 2](#S2), we start by introducing the needed background.
We then formally model the diversity of model outputs, discuss our querying strategy that ensures our assumptions are met, and describe the resulting statistical test.
The effectiveness of our method is evaluated in [Section 5](#S5).

#### Background

For Fixed-Sampling watermarks, the secret watermark key sequence $\xi$ of length $n_{key}$ is cyclically shifted uniformly at random for each generation to obtain $\bar{\xi}$, and the entry $\bar{\xi}_{t}$ is used to sample from $l$.
In the ITS variant, $\bar{\xi}_{t}$ is a pair $(u,\pi)\in[0,1]\times\Pi$, where $\Pi$ defines the space of permutations of the vocabulary $V$.
Given the probability distribution $p$ over $V$, obtained by applying the softmax function to $l$, ITS samples the token with the smallest index in the permutation $\pi$ such that the CDF of $p$ with respect to $\pi$ is at least $u$.
In the EXP variant, $\bar{\xi}_{t}$ is a value $u\in[0,1]$, and we sample the token $\operatorname*{arg\,min}_{i\in V}-\log(u)/p_{i}$.
The detection, for both variants, is based on testing the correlation between the text and $\xi$ using a permutation test.
As noted in [Section 1](#S1), the key design goal of ITS and EXP is that, in expectation w.r.t. $\xi$, they do not distort the distribution of the responses.
How close to this ideal is achieved in practical implementations is the question we aim to answer.

#### Modeling the diversity

Let $U_{n}(q,t)$ denote a random variable that counts the number of unique outputs to a fixed prompt $q$ in $n$ queries, each of length exactly $t$ in tokens. We introduce the *rarefaction curve* (visualized in [Fig. 1](#S2.F1)) as

$$ $R(n)=\mathbb{E}[U_{n}(q,t)].$ (8) $$

For suitable $q$ that enables diversity and large enough $t$, the unwatermarked model exhibits $R(n)=n$.
For a Fixed-Sampling watermark (both ITS and EXP variants), the watermark key segment used for sampling is determined by choosing a rotation of the key $\xi$ uniformly at random.
As choosing the same rotation for the same prompt and sampling settings will always yield the same output, the number of unique outputs is at most equal to the key size $n_{key}$.
The probability that an output $i$ was not produced is given by $(1-1/n_{key})^{n}$.
By linearity of expectation, we have the rarefaction curve

$$ $R(n)=n_{\text{key}}\left(1-(1-\frac{1}{n_{\text{key}}})^{n}\right).$ (9) $$

#### Querying strategy

To estimate $R(n)$ of $LM$, we query it with a fixed prompt $q$, using rejection sampling to discard short responses until we obtain a set of $N$ responses of length $t$ tokens (inducing $Q$ total queries).
We then repeatedly sample $n$ responses from this set to get a Monte-Carlo estimation of $R(n)$.
There are two key considerations.
First, we need to ensure that we are in a setting where an unwatermarked model would have $R(n)=n$.
To do this, we use the prompt ‘‘This is the story of’’ that reliably causes diverse outputs, and set $t$ high enough to minimize the chance of duplicates.
In [Section 5](#S5) we experimentally confirm that the number of unique outputs scales exponentially with $t$, and investigate the effect of small temperatures.
Second, as larger $n_{key}$ make $R(n)$ closer to linear, we must ensure that $n$ is large enough for our test to be reliable.
To do this, we can set an upper bound $\bar{n}_{key}$ on key size, and estimate the number of samples needed for a given power by simulating the test—our experiments show that our test succeeds even on values of $\bar{n}_{key}$ far above practical ones.

#### Testing watermark presence

Finally, to test for presence of a Fixed-Sampling watermark, we use a Mann-Whitney U test to compare the rarefaction curve $R(n)=n$ with the observed rarefaction data obtained as above.
If the test rejects the null hypothesis, we interpret this as evidence that the model is watermarked with a Fixed-Sampling scheme.
We confirm the effectiveness of our test in [Section 5](#S5).
In [App. C](#A3) we discuss estimation of the watermark key size $n_{key}$ once the presence of a Fixed-Sampling watermark is confirmed.

## 4 Detecting Cache-Augmented Watermarks

We proceed to the detection of Cache-Augmented watermarks.
While the underlying techniques used in these schemes are often similar to those of the Red-Green and Fixed-Sampling families, we focus on a general approach that exploits the presence of a cache on a fundamental level, and can be generally applied to any Cache-Augmented scheme.
Namely, we note that the cache sometimes *reveals the true distribution* of the model, which was also noted in recent work [] as an undesirable property for a watermarking scheme.
This implies that the distribution of choices is *cache-conditioned* (as seen in [Fig. 1](#S2.F1), top), which our adversary will exploit to detect the presence of a watermark.

We first recall relevant background, and then discuss our method: we query the model in two phases to probe the two cache-conditioned distributions, and apply a statistical test to detect when they differ, which would indicate the presence of a Cache-Augmented watermark.

#### Background

The watermarks that we consider in this section use previous $h$ tokens to reweigh the distribution or apply deterministic sampling at each step.
As a key feature motivated by practical distribution preservation, these schemes introduce a *cache* of previously seen contexts.
Namely, whenever $y_{t-h:t-1}$ is already present in the cache, they ignore the watermarking procedure and instead fall back to standard generation.
The cache can be either global or local (per user) and clears after a certain number $G$ of generations.
We consider three variants: $\delta$-reweight [], $\gamma$-reweight [], and DiPmark [] with parameter $\alpha$, the details of which we defer to [App. B](#A2).

#### Probing the true distribution

In the first phase of querying, our goal is to find a setting where the distribution of the model under the watermark will differ from its true distribution, and estimate the true distribution.
For schemes we focus on, this corresponds to a setting with two choices, where the model is not significantly biased towards any of them.
In particular, we use the following prompt:

and modify $f_{1},f_{2},$ and $f_{example}\neq f_{1},f_{2}$ until we find a setting where the model outputs the two choices roughly uniformly.
Crucially, we prefix the prompt with a randomly sampled sufficiently long string of tokens $uc$.
As $LM$ will repeat $uc$ before providing the answer, this ensures that if a cache is present, after our first query (the result of which we discard) the choice of the model will be made according to the true distribution, as the relevant part of $uc$ was cached.
Assuming WLOG that $f_{1}$ is the more likely choice for the model, we query it $Q_{1}$ times with the same input to obtain $\hat{p_{1}}$, the estimate of the true probability of the model to pick $f_{1}$.

#### Probing the watermarked distribution

In the second phase, we query $LM$ with the same input, while ensuring that the cache is reset between each query, i.e., the model will respond according to the watermarked distribution.
In case of a global cache, it is sufficient to wait for a set amount of time—resetting the cache too infrequently is not a realistic setting for a deployment, as it would on average lead to a weak watermark.
The uncommon prefix $uc$ ensures that no other user will accidentally insert the same context into the cache.
In case of a per-user cache, we can either saturate the cache by asking diverse queries, or use multiple user accounts.
We query $LM$ $Q_{2}$ times and obtain $\hat{p_{2}}$, the estimate of the probability of $f_{1}$ under the watermarked distribution.

#### Testing watermark presence

For unwatermarked models or those watermarked with a scheme from another family, both of the previous steps were sampling from the same distribution, thus for high enough $Q_{1}$ and $Q_{2}$ we expect $\hat{p_{1}}=\hat{p_{2}}$.
However, for all Cache-Augmented watermarking schemes, these probabilities will differ, indicating that the cache has revealed the true distribution of the model.
To test this, we apply a Fischer’s exact test with the null hypothesis $\hat{p_{1}}=\hat{p_{2}}$.
If we observe a low $p$-value, we interpret this as evidence that the model is watermarked with a Cache-Augmented scheme.
Our experiments in [Section 5](#S5) demonstrate that this test is robust to different scheme variants, and does not lead to false positives when $LM$ is unwatermarked or uses a scheme from another family.
In [App. C](#A3) we discuss how to distinguish different variants of Cache-Augmented schemes.

## 5 Experimental Evaluation

**Table 1: Main results of our watermark detection tests across different models and watermarking schemes. We report median p-values across 100 repetitions of the experiment, and for Red-Green schemes additionally over 5 watermarking keys. p-values below $0.05$ (test passing) are highlighted in bold. $\delta$R and $\gamma$R denote $\delta$-reweight and $\gamma$-reweight schemes, respectively.**
|  |  |  |  |  | Red-Green |  | Fixed-Sampling |  | Cache-Augmented |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
|  |  | Unwatermarked |  | LeftHash | SelfHash |  | ITS/EXP |  | DiPmark/$\gamma$R | $\delta$R |  |  |  |  |  |
| Model | Test | $T=$<br>$1.0$ | $T=$<br>$0.7$ |  | $\delta,\gamma=$<br>$2,0.25$ | $\delta,\gamma=$<br>$4,0.5$ | $\delta,\gamma=$<br>$2,0.5$ | $\delta,\gamma=$<br>$4,0.25$ |  | $n_{key}=$<br>$256$ | $n_{key}=$<br>$2048$ |  | $\alpha=$<br>$0.3$ | $\alpha=$<br>$0.5$ |  |
| Mistral<br>7B | R-G ([Section 2](#S2)) | 1.000 | 1.000 |  | 0.000 | 0.000 | 0.000 | 0.000 |  | 1.000 | 1.000 |  | 1.000 | 1.000 | 1.000 |
| Fixed ([Section 3](#S3)) | 0.938 | 0.938 |  | 0.938 | 0.938 | 0.938 | 0.938 |  | 1.3e-125 | 1.1e-9 |  | 0.938 | 0.938 | 0.938 |  |
| Cache ([Section 4](#S4)) | 0.570 | 0.667 |  | 0.607 | 0.608 | 1.00 | 0.742 |  | 0.638 | 0.687 |  | 2.4e-4 | 2.1e-3 | 5.6e-27 |  |
| Llama2<br>13B | R-G ([Section 2](#S2)) | 0.149 | 0.663 |  | 0.000 | 0.000 | 0.000 | 0.000 |  | 0.121 | 0.128 |  | 0.149 | 0.149 | 0.149 |
| Fixed ([Section 3](#S3)) | 0.968 | 0.868 |  | 0.938 | 0.938 | 0.938 | 0.938 |  | 5.5e-124 | 7.5e-8 |  | 0.938 | 0.938 | 0.968 |  |
| Cache ([Section 4](#S4)) | 0.708 | 0.573 |  | 0.511 | 0.807 | 0.619 | 0.710 |  | 0.518 | 0.692 |  | 1.8e-2 | 5.3e-3 | 6.7e-32 |  |
| Llama2<br>70B | R-G ([Section 2](#S2)) | 1.000 | 1.000 |  | 0.000 | 0.020 | 0.000 | 0.000 |  | 1.000 | 1.000 |  | 1.000 | 1.000 | 1.000 |
| Fixed ([Section 3](#S3)) | 0.938 | 0.526 |  | 0.966 | 0.965 | 0.984 | 0.975 |  | 4.2e-125 | 1.7e-8 |  | 0.938 | 0.966 | 0.938 |  |
| Cache ([Section 4](#S4)) | 0.596 | 0.620 |  | 0.657 | 0.639 | 0.651 | 0.608 |  | 0.463 | 0.818 |  | 1.5e-3 | 4.4e-3 | 5.8e-28 |  |

In this section, we apply the tests introduced in [Sections 2](#S2), [3](#S3) and [4](#S4) to a wide range of models and watermarking schemes, and confirm their effectiveness in detecting watermarks.
In [Section 5.1](#S5.SS1) we show that the adversary can reliably detect the watermarking scheme used (if any) at a low cost, across a wide range of practical settings.
In [Section 5.2](#S5.SS2), we provide further experimental insights into the tests’ robustness.
Finally, in [Section 5.3](#S5.SS3), we demonstrate that our tests can be directly applied to real-world LLM deployments, revealing no significant evidence of any watermarking schemes at this point in time.

### 5.1 Main Experiments: Detecting Watermarking Schemes

We perform our main set of experiments to verify the effectiveness of our tests introduced in  [Sections 2](#S2), [3](#S3) and [4](#S4) in detecting watermarking schemes in realistic scenarios.

#### Experimental setup

We run all our tests on five different models (Mistral-7B, Llama2-7B, -13B, and -70B, and Llama3-8B), in eleven different scenarios.
We here present results of a subset of those, and defer the rest to [App. A](#A1).
In each scenario, each model is either unwatermarked (where we vary the temperature) or watermarked with a certain scheme from the three main families (where we vary the particular scheme and its parameters).
If our tests are reliable, we expect to see low p-values only when the model is watermarked exactly with the scheme family that we are testing for.

For Red-Green tests, we set $N=10,M=9,r=1.96$, a different $\Sigma$ per model based on the first $Q1$ samples, use $100$ samples to estimate the probabilities, and use $10000$ permutations in the test.
For Fixed-Sampling tests, we use $n=1000$ queries and set $t=50$.
For Cache-Augmented tests, we use $Q1=Q2=75$ and assume the cache is cleared between queries in the second phase.

#### Results: reliable watermark detection

Our main results are shown in [Table 1](#S5.T1), where we report the median p-values for each (model, test, scenario) tuple across 100 repetitions of each experiment.
Across all experiments, all three tests reject the null hypothesis (*the specific watermark is not present*) at a 95% confidence level only when the scheme from the target family is indeed applied to the model.
This confirms that our tests are reliable in detecting watermarks, and robust with respect to the model and the specific parameters of the scheme, emphasizing our tests’ generalization to all schemes that are based on the same foundational principles.
In particular, our Red-Green tests are robust to the seeding scheme, the logit bias $\delta$, and the green token fraction $\gamma$; our Fixed-Sampling tests maintain high confidence even for unusually high values of $n_{key}$ and those higher than the number of queries; finally, our Cache-Augmented tests are robust to all details of the underlying scheme.
Our results also provide evidence that unrelated model modifications do not cause false positives, as no test passes when the model is unwatermarked or watermarked with a different scheme family.

Our tests do not incur significant costs for the adversary, making them easily applicable in practice.
While the cost of a particular run varies across models and scenarios, we can estimate the average cost of the tests to be below $20 for Red-Green, $1 for Fixed-Sampling, and $0.1 for Cache-Augmented tests, assuming latest OpenAI GPT4o pricing.

### 5.2 Additional Experiments: Validating the Assumptions

Figure: Figure 2: *Left*: distribution of bootstrapped p-values of the Red-Green test on Llama2-13B with $(\delta,\gamma)=(2,0.25)$, for different sample sizes. We see reliable results for $100$ or more samples. *Right*: the diversity gap $n-R(n)$ on log scale in different settings. Linear behavior means that diversity scales exponentially with $t$, and we see that the assumption of $R(n)=n$ can be easily met in practice.
Refer to caption: /html/2405.20777/assets/x2.png

We present two additional experiments to validate the assumptions made in our tests and provide further insight into their behavior in practical settings.

#### Sampling in Red-Green tests

The Red-Green test ([Section 2](#S2)) relies on the sampling of model outputs to estimate the probabilities of the model.
As the resulting p-value is computed assuming knowledge of true probabilities, this raises the question of the impact of the sampling error on our results.
To heuristically mitigate this, we propose a bootstrapping procedure, where for fixed $(t_{1},t_{2})$, we sample with replacement from a single set of model outputs, and report the median p-value $p_{med}$ across such samples.
In [Fig. 2](#S5.F2) (Left) we report the resulting distribution of $p_{med}$, where one point corresponds to one independent run.
We see that already for $100$ samples per $(t_{1},t_{2})$ (as used in [Table 1](#S5.T1)), the p-value distribution is narrow and the false positive rate due to sampling error is well controlled.
This confirms that our test is robust against sampling error and can be used in realistic settings, without additional access to model logprobs.
For computational reasons, we did not apply this correction in [Table 1](#S5.T1), where we still observe reliable results in the median case across experiment repetitions.

#### Diversity assumption in Fixed-Sampling tests

As detailed in [Section 3](#S3), the Fixed-Sampling test relies on the unwatermarked model being sufficiently diverse, i.e., for the number of unique outputs $R(n)=\mathbb{E}[U_{n}(q,t)]$ after $n$ queries with prompt $q$ and response length $t$, it should hold that $R(n)=n$.
Our goal is to show that we can easily choose $t$ such that this property holds across different settings.

To this end, we hypothesize that the number of unique outputs converges to $n$ exponentially fast as the response length $t$ increases.
In particular, we assume

$$ $R(n)=n-\lfloor n\cdot\exp(-\alpha(T)t)\rfloor,$ (10) $$

where $\alpha(T)$ is a monotonic function of the temperature $T$.
To verify this hypothesis, we measure $n-R(n)$ on several models and temperatures, and show the result on log scale in [Fig. 2](#S5.F2) (Right).
If [Eq. 10](#S5.E10) holds, we expect the resulting relationship to be linear, which is indeed confirmed by our results.
While $\alpha$ (the slope of the line) varies across settings, we see that a bit over $200$ tokens would be sufficient for the line to drop to 0 0 (not visible on the log scale plot).
This holds even in cases impractical for deployment of Fixed-Sampling watermarks such as $T=0.4$ [, ], indicating that $R(n)=n$ and our assumption is met, validating our p-values.

### 5.3 Detecting watermarks in deployed models

**Table 2: The results of our watermark detection tests on popular black-box LLM deployments.**
|  |  | GPT4 | Claude 3 | Gemini 1.0 Pro |
| --- | --- | --- | --- | --- |
| R-G ([Section 2](#S2)) |  | 0.998 | 0.638 | 0.683 |
| Fixed ([Section 3](#S3)) |  | 0.938 | 0.844 | 0.938 |
| Cache ([Section 4](#S4)) |  | 0.51 | 0.135 | 0.478 |

Finally, we demonstrate the applicability of the statistical tests introduced in [Sections 2](#S2), [3](#S3) and [4](#S4), by applying them to popular black-box LLM deployments: GPT4, Claude 3, and Gemini 1.0 Pro.
We use the same experimental setup as in [Section 5.1](#S5.SS1), and use the API access for efficiency reasons—we do not rely on any additional capabilities, and our tests could be as easily run in the web interface.
For the Cache-Augmented tests, we assume a global cache, that if present clears after $1000$ seconds. For the Fixed-Sampling test on Claude 3, due to its lack of diversity, we used $t=75$ tokens per query to ensure the test’s hypotheses are met.

#### Results

Our results in [Table 2](#S5.T2) show that the null hypothesis is not rejected for any of the models and any of the watermark tests.
This suggests that none of the deployed models tested are watermarked at this point in time.
The demonstrated applicability of our tests makes it simple to monitor these deployments and detect any watermarking schemes that may be introduced in the future.

## 6 Related Work

#### Language model watermarking

Besides the approaches by [, , ] introduced above, there are various methods building on similar ideas. Hou et al., [], Liu et al., 2024b [], Ren et al., [] all apply variations of [] on semantic information, while Gu et al., [] aims to distill a new model from the output of a watermarked model. Similarly, Liu et al., 2024a [] apply a Red-Green scheme using a learned classifier instead of hash functions.
A range of works on multi-bit watermarking [, ] aim to not only watermark generated texts but encode additional information in the watermark itself.

#### Attacks on language model watermarking

Attacks on LLM watermarks have so far been mainly investigated in terms of scrubbing [, , ] (i.e., removal of a watermark) and spoofing [, , ] (i.e., applying a watermark without knowing $\xi$).
Notably, Jovanović et al., [] showed that observing watermarked texts can facilitate both attacks on various distribution-modifying schemes, disproving common robustness assumptions [].
However, using this and similar attacks as means of practical watermark detection is infeasible, as they generally offer no way to quantify the attack’s success—in contrast, we aim to provide rigorous statements about scheme presence.
Further, such attacks incur significantly higher query costs than necessary for detection (as our work demonstrates), and in some cases assume certain knowledge of the watermark parameters, a setting fundamentally at odds with our threat model of black-box watermark detection.

The closest related work to ours is Tang et al., [], that tackles the problem of watermark detection in strictly simpler settings where the adversary either has access to an unwatermarked counterpart of the target model, or can access full model logits.
Such knowledge is commonly not available in practice, limiting the applicability of this approach.
To the best of our knowledge, no work has developed methods for detecting the presence of a watermark in a realistic black-box setting.

#### Extracting data from black-box models

With many of the most potent LLMs being deployed behind restricted APIs, the extraction of model details has been an active area of research. This includes, e.g., the reconstruction of a black-box model tokenizer [] as well as the extraction of the hidden-dimensionality or the weights of the embedding projection layer []. Naseh et al., [] have shown practical attacks to recover the decoding mechanism of non-watermarked black-box models. Given access to output logits, Li and Fung, [] have further demonstrated that it is possible to train an inversion model that aims to recover the input prompt.

## 7 Conclusion, Impact and Limitations

In this paper, we have focused on the problem of detecting watermarks in large language models (LLMs) given only black-box access.
We developed rigorous statistical tests for the three most prominent scheme families, and validated their effectiveness on a wide range of schemes and real-world models.
Our results imply that protecting from detectability should not be the key focus of LLM watermarks, and that other properties such as robustness to attacks, text quality, and efficiency should be prioritized.

#### Broader Impact

While our work primarily enables malicious parties to more easily circumvent attempts at tracing LLM-generated text, we believe the benefits of our work outweigh those risks, as our conclusions help model providers calibrate their expectations in terms of watermark detectability, and avoid a false sense of security.

#### Limitations

One limitation of our tests is that they are restricted to the three scheme families discussed in [Sections 2](#S2), [3](#S3) and [4](#S4).
These are indeed the most prominent in the literature, and as our tests are based on fundamental properties of these scheme families, they should generalize to more variants and combinations of the underlying ideas.
However, it is possible that a model provider deploys a scheme based on an entirely novel idea, which our tests would not be able to detect.
Further, our p-values are based on several model assumptions, such as symmetric error terms and perfect sampling.
While we validate that these assumptions are sufficiently met on several open-source models, we cannot guarantee that all models adhere to them.
Finally, another conceptual limitation of our Red-Green test is that it does not take into account the possibility that the red-green vocabulary split is the same (on the observed domain) for all contexts.
The probability of this event decreases exponentially with the number of different contexts, and is thus unlikely to affect the test’s performance in practice.

## Appendix A Extending Experiments across Diverse Settings

**Table 3: Additional results of our watermark detection tests across different models and watermarking schemes. We report median p-values across 100 repetitions of the experiment, and for Red-Green schemes additionally over 5 watermarking keys. p-values below $0.05$ (test passing) are highlighted in bold. $\delta$R and $\gamma$R denote $\delta$-reweight and $\gamma$-reweight schemes, respectively.**
|  |  |  |  |  | Red-Green |  | Fixed-Sampling |  | Cache-Augmented |  |  |  |  |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
|  |  | Unwatermarked |  | LeftHash | SelfHash |  | ITS/EXP |  | DiPmark/$\gamma$R | $\delta$R |  |  |  |  |  |  |  |  |  |
| Model | Test | $T=$<br>$1.0$ | $T=$<br>$0.7$ |  | $\delta,\gamma=$<br>$2,0.25$ | $\delta,\gamma=$<br>$2,0.5$ | $\delta,\gamma=$<br>$4,0.25$ | $\delta,\gamma=$<br>$4,0.5$ | $\delta,\gamma=$<br>$2,0.25$ | $\delta,\gamma=$<br>$2,0.5$ | $\delta,\gamma=$<br>$4,0.25$ | $\delta,\gamma=$<br>$4,0.5$ |  | $n=$<br>$256$ | $n=$<br>$2048$ |  | $\alpha=$<br>$0.3$ | $\alpha=$<br>$0.5$ |  |
| Mistral<br>7B | R-G ([Section 2](#S2)) | 1.000 | 1.000 |  | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 |  | 1.000 | 1.000 |  | 1.000 | 1.000 | 1.000 |
| Fixed ([Section 3](#S3)) | 0.938 | 0.938 |  | 0.938 | 0.938 | 0.938 | 0.938 | 0.938 | 0.938 | 0.938 | 0.938 |  | 1.3e-125 | 1.1e-9 |  | 0.938 | 0.938 | 0.938 |  |
| Cache ([Section 4](#S4)) | 0.570 | 0.667 |  | 0.607 | 0.639 | 0.632 | 0.608 | 1.000 | 1.000 | 0.742 | 0.824 |  | 0.638 | 0.687 |  | 2.4e-4 | 2.1e-3 | 5.6e-27 |  |
| Llama2<br>13B | R-G ([Section 2](#S2)) | 0.149 | 0.663 |  | 0.000 | 0.014 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 |  | 0.121 | 0.128 |  | 0.149 | 0.149 | 0.149 |
| Fixed ([Section 3](#S3)) | 0.968 | 0.868 |  | 0.938 | 0.966 | 0.938 | 0.938 | 0.938 | 0.938 | 0.938 | 0.967 |  | 5.5e-124 | 7.5e-8 |  | 0.938 | 0.938 | 0.968 |  |
| Cache ([Section 4](#S4)) | 0.708 | 0.573 |  | 0.511 | 0.596 | 0.623 | 0.807 | 0.657 | 0.619 | 0.710 | 0.583 |  | 0.518 | 0.692 |  | 1.8e-2 | 5.3e-3 | 6.7e-32 |  |
| Llama2<br>70B | R-G ([Section 2](#S2)) | 1.000 | 1.000 |  | 0.000 | 0.000 | 0.000 | 0.020 | 0.000 | 0.020 | 0.000 | 0.000 |  | 1.000 | 1.000 |  | 1.000 | 1.000 | 1.000 |
| Fixed ([Section 3](#S3)) | 0.938 | 0.526 |  | 0.966 | 0.964 | 0.889 | 0.965 | 0.963 | 0.984 | 0.975 | 0.990 |  | 4.2e-125 | 1.7e-8 |  | 0.938 | 0.966 | 0.938 |  |
| Cache ([Section 4](#S4)) | 0.596 | 0.620 |  | 0.657 | 0.797 | 0.824 | 0.639 | 0.535 | 0.651 | 0.608 | 0.593 |  | 0.463 | 0.818 |  | 1.5e-3 | 4.4e-3 | 5.8e-28 |  |
| Llama2<br>7B | R-G ([Section 2](#S2)) | 1.000 | 1.000 |  | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 |  | 1.000 | 1.000 |  | 1.000 | 1.000 | 1.000 |
| Fixed ([Section 3](#S3)) | 0.993 | 0.988 |  | 0.938 | 0.938 | 0.938 | 0.938 | 0.968 | 0.938 | 0.938 | 0.938 |  | 7.6e-124 | 1.0e-8 |  | 0.938 | 0.938 | 0.993 |  |
| Cache ([Section 4](#S4)) | 0.604 | 0.602 |  | 0.623 | 0.705 | 0.728 | 0.593 | 0.620 | 0.718 | 0.610 | 0.593 |  | 0.476 | 0.588 |  | 4.2e-6 | 4.5e-7 | 1.3e-21 |  |
| Llama3<br>8B | R-G ([Section 2](#S2)) | 1.000 | 1.000 |  | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 |  | 1.000 | 1.000 |  | 1.000 | 1.000 | 1.000 |
| Fixed ([Section 3](#S3)) | 0.938 | 0.938 |  | 0.938 | 0.938 | 0.938 | 0.938 | 0.938 | 0.938 | 0.986 | 0.938 |  | 1.2e-124 | 3.8e-8 |  | 0.938 | 0.938 | 0.938 |  |
| Cache ([Section 4](#S4)) | 0.734 | 0.504 |  | 0.605 | 0.514 | 0.712 | 0.605 | 0.600 | 0.731 | 0.729 | 0.714 |  | 0.618 | 0.605 |  | 5.2e-5 | 3.2e-8 | 3.5e-18 |  |

#### Watermark detection with additional models and schemes

We extend the experiments from [Section 5.1](#S5.SS1) using two additional models, Llama2-7B and Llama3-8B, as well as more variations of the watermarking schemes’ parameters to further assess the robustness of the tests. The experimental setup for the additional results is consistent with the one described in [Section 5.1](#S5.SS1).

Our exhaustive results are presented in [Table 3](#A1.T3). The same conclusion applies to the two additional models: the null hypothesis (*the specific watermark is not present*) is rejected at a 95% confidence level only when the corresponding watermarking scheme is applied to the model. These results confirm that the modeling assumptions for each test are satisfied across a wide range of models, indicating the tests’ relevance in practical scenarios.

#### Multiple keys in Red-Green watermarks

To demonstrate that the Red-Green test is robust to variations in the watermarking scheme within the same watermark family, we consider the case of Red-Green watermarks with multiple keys, where the key $\xi$ is uniformly selected from a predefined pool of keys at each generation. Using $n$ keys turns [Eq. 3](#S2.E3) into

$$ $l_{t_{1},t_{2}}(x)=x^{0}/T+\delta^{\prime\prime}_{t_{2}}(x)+\varepsilon^{\prime}_{t_{1},t_{2}}(x),$ (11) $$

with $\delta^{\prime\prime}_{t_{2}}(x)$ in $\{k\delta/(nT)\,|\,\forall k\in\{-n,...,n\}\}$ is obtained by averaging the variables $\delta^{\prime}_{t_{2}}(x)$ over the set of keys. Despite modeling changes, the core assumption of logit bias being conditioned on $t_{2}$ remains unchanged. Therefore, we can apply the same test as in [Section 2](#S2) to detect the watermark. Consequently, we conducted the Red-Green test on both the LeftHash and SelfHash variants using $n=3$ keys on three models (Llama2-13B, Llama2-70B and Mistral-7B).
Recent work [] shows that using too many keys can lead to other vulnerabilities.

Across all three models and scheme parameters, the null hypothesis (*the Red-Green watermark is not present*) is rejected at a 95% confidence level, with median p-values lower than $1e\text{-}4$ for each combination of model and setting. It shows that the Red-Green test is robust even in settings that slightly deviate from the original modeling considered in [Section 2](#S2). It emphasizes the test’s reliance on the foundational principles behind Red-Green schemes rather than on specific implementation details.

## Appendix B Details of Cache-Augmented Schemes

We provide the details of the three Cache-Augmented watermarking schemes considered in this work: $\delta$-reweight [], $\gamma$-reweight [], and DiPmark [], that were omitted from [Section 4](#S4).

All three variants, at each generation step $t$, jointly hash the watermark key $\xi\in\mathbb{Z}_{2}^{K}$ and the preceding context $y_{t-h:t-1}$ (commonly setting $h=5$) using SHA256, and use the result as a seed to sample a *code* $E_{t}\in P_{E}$ uniformly at random.
Let $p$ denote the probability distribution over $V$, obtained by applying the softmax function to the logits.
For the $\delta$-reweight variant, $P_{E}=[0,1]$, and the code $E_{t}$ is used to sample the token in $V$ with the smallest index, such that the CDF of $p$ is at least $E_{t}$.
For the $\gamma$-reweight variant and DiPmark, $P_{E}$ is the space of permutations of $V$.
For $\gamma$-reweight, we transform $p$ to a new distribution $p^{\prime}$ by, for each token $i\in V$, setting $p^{\prime}(i)=f_{2}(f_{1}(E_{t}(i)))-f_{2}(f_{1}(E_{t}(i)-1))$, where we have $f_{1}(i^{\prime})=\sum_{j\in V}{\mathbbm{1}}(E_{t}(j)\leq i^{\prime})p(j)$ and $f_{2}(v)=\max(2v-1,0)$, effectively dropping the first half of the permuted CDF.
For DiPmark, given parameter $\alpha\in[0,0.5]$, this is generalized by using $f_{2}(v)=\max(v-\alpha,0)+\max(v-(1-\alpha),0)$, recovering $\gamma$-reweight for $\alpha=0.5$.
The former two variants perform detection using a log-likelihood ratio test (requiring access to $LM$), while DiPmark uses a model-independent test.

## Appendix C Estimating Scheme Parameters

In this section, we describe how, mostly leveraging the queries already performed during the detection tests, we can estimate the main parameters of the detected watermarking scheme.
This demonstrates the soundness of our modeling assumptions in [Sections 2](#S2), [3](#S3) and [4](#S4) from which we derive all the estimators.

### C.1 Estimation of Red-Green Watermarking Scheme Parameters

If the null hypothesis (*the model not being Red-Green watermarked*) is rejected, we can then estimate the scheme-specific watermark parameters $\delta$ and the context size $h$ using mostly the same data as used in the test. First, we describe the estimators for both parameters, and then discuss their practicality by analyzing their performance on multiple models.

#### Description of estimators

To estimate $\delta$, we establish a parametrized model based on [Eq. 2](#S2.E2) that relies on our flagging function from [Eq. 6](#S2.E6), and additional estimates $\hat{l}_{t_{1},t_{2}}(w)$ for every $w\in\Sigma$, computed on the same data as above, requiring no additional queries.
For each $w\in\Sigma$, we set:

$$ $\hat{l}_{t_{1},t_{2}}(w)=\bar{w}_{t_{1}}+G_{w}(t_{1},t_{2})\bar{\delta}-\log\left(\sum_{w^{\prime}\in\Sigma\setminus\{w\}}\exp\left(\bar{w}^{\prime}_{t_{1}}+G_{w^{\prime}}(t_{1},t_{2})\bar{\delta}\right)\right),$ (12) $$

and set $\forall t_{1}$, $\bar{w}_{t_{1}}=0$ for a single $w\in\Sigma$, as logits are shift-invariant.
Fitting the parameters $\bar{\delta}$ and all $\bar{w}_{t_{1}}$ by minimizing the mean squared error with gradient descent allows us to recover $\delta/T$ as $\bar{\delta}$. If $T$ is known or estimated separately, this term can be removed.

Let $h$ denote the context size, i.e., the number of *previous* tokens considered by the watermarking scheme. To estimate $h$, we use the same prompt template as in [Section 2](#S2), with a fixed prefix $t_{1}$ and digit $d$, but with a varying $H$ and perturbation digit $d^{\prime}$ prepended to $d$.

The probability distribution of the model output will abruptly change when $H$ exceeds the context size $h$, as the change in $d^{\prime}$ will not alter the red/green split of the vocabulary.
By performing a series of pairwise Mood’s tests on the estimated log-probabilities of $x$ we can find the largest $H$ for which $t_{1}$ is part of the context.
This corresponds to the first value of $H$ for which the test is rejected.

Estimating $\gamma$ is more challenging, as in contrast to $\delta$, this parameter is not directly reflected in the logits but rather defines a more global behavior of the scheme.
This is particularly difficult for schemes with self-seeding, as the rejection sampling interferes with the behavior of $\gamma$.
We leave further exploration of this problem to future work.

Figure: Figure 3: Estimation of $\delta$ for different models using LeftHash with $\gamma=0.25$. The number of samples used increases from left to right, with the leftmost plot assuming direct access to the log-probabilities. The estimation is done on the same data as the test. Error bars are given by the 95% bootstrapped confidence interval with respect to the sampling of the model outputs.
Refer to caption: /html/2405.20777/assets/x4.png

#### Experimental results

We computed the estimator for $\delta$ on the LeftHash variant with $\gamma=0.25$ and varying $\delta$ from 0 to 4. The results are shown in [Fig. 3](#A3.F3), with the 95% confidence intervals reflecting the sampling error. The estimator successfully estimates $\delta$ for all models with a sufficient number of samples, using only the estimated output probabilities of the model. It is also consistent across all models tested, suggesting that the model assumptions in [Eq. 1](#S2.E1) are met in practice.

Estimating the context size for Red-Green schemes requires performing a new attack once the model is flagged as watermarked. We estimate the context size for three different models (Mistral-7B, Llama2-13B and Llama2-70B) using LeftHash with $\delta=2$ and $\gamma=0.25$. The estimation process requires an additional 5,000 queries, and the estimator successfully determines the context size for all models.
However, the estimator is less robust on the SelfHash variant due to the self-seeding algorithm, which leads to higher probabilities for tokens in $\Sigma$ being in the green vocabulary, and thus diminishes the perturbation’s significance and resulting in false negatives in Mood’s test. Therefore, the procedure stated above produces a lower bound for the context size. To mitigate this issue, we use the estimator across 10 different $t_{2}$ and then consider the median of the $10$ estimators as our final estimator. This estimator applied on the SelfHash variant with $\delta=2$ and $\gamma=0.25$ is successful on all three models. It also does not change the results on LeftHash and can be used as a more robust estimator for $h$ in all cases, when the additional cost of $50,000$ queries is not prohibitive.

### C.2 Estimation of Fixed-Sampling Watermarking Scheme Parameters

Our approach does not distinguish between the variant of the Fixed-Sampling watermark used (ITS or EXP), as the diversity property that we exploit is common to both.
The only other relevant parameter of Fixed-Sampling schemes is $n_{\text{key}}$.
To estimate it, we use non-linear regression on the rarefaction curve using ([9](#S3.E9)) and the same data that we used for the presence test, and compute the confidence intervals using bootstrapping.

Our results are given in [Table 4](#A3.T4). We see that the estimator is consistent across different models and remains relatively precise even for values of $n_{\text{key}}$ higher than the number of queries.

**Table 4: Key length estimation for Fixed-Sampling watermarks using non-linear regression on the rarefaction curve.**
| Key length |  | Llama2-7B | Llama2-13B | Llama2-70B | Llama3-8B | Mistral-7B |
| --- | --- | --- | --- | --- | --- | --- |
| 256 |  | $259\pm 0.6$ | $259\pm 0.5$ | $256\pm 0.5$ | $257\pm 0.5$ | $256\pm 0.6$ |
| 2048 |  | $1978\pm 10$ | $2107\pm 12$ | $2006\pm 13$ | $2070\pm 14$ | $1831\pm 10$ |

### C.3 Estimation of Cache-Augmented Watermarking Scheme Parameters

For Cache-Augmented watermarks, we can estimate which scheme variant is present, and if the variant is DiPmark, attempt to learn the value of $\alpha$ (recall that $\alpha=0.5$ corresponds to $\gamma$-reweight).
To do this, we use the same approach as in [Section 4](#S4) to obtain $\hat{p_{1}}$ and $\hat{p_{2}}$, where WLOG we assumed $p_{1}>0.5$.
If we observe $\hat{p_{2}}=0$ this directly implies a $\delta$-reweight watermark.
If we observe $\hat{p_{2}}\in(0,1)$, we learn the following: if $\hat{p_{2}}=2\hat{p_{1}}-1$ then $\alpha>1-\hat{p_{1}}$, otherwise $\alpha=|\hat{p_{1}}-\hat{p_{2}}|$.
The bound in the first case can be further improved with additional queries with different $p_{1}$.
Finally, if we observe $\hat{p_{2}}=1$ we repeat the whole procedure in total $K$ times, following the same case distinction—if $\hat{p_{2}}=1$ repeats in all $K$ runs, we conclude that the model is watermarked with $\delta$-reweight.

Using the same parameters as the one for the test, we distinguish with 100% accuracy between a DiPmark and a $\delta$-reweight watermark. However, the estimation of $\alpha$ becomes unreliable for higher values of $\alpha$, especially for smaller models.
One of the reasons for this are the failures of the model to follow the instruction, that are more common in the presence of the uncommon prefix $uc$.
While the detection test in [Section 4](#S4) was robust to such behavior, this does not hold for the estimation of $\alpha$.

## Peer Reviews

confidence: 3
contribution: 3
initial_rating: 8
presentation: 4
questions: In Appendix C, you discuss a method for estimating scheme parameters. Are your techniques capable of learning the watermarking key itself?
soundness: 3
strengths: A huge number of watermarking papers have come out recently.
Many of them ask whether their watermarks harm generation quality by performing experimental evaluations, but these are inherently limited: There is no way to experimentally guarantee that the watermark will preserve the quality under *every possible* use-case of the model.
Therefore, perhaps a more useful test of quality is to simply attempt to detect it. If attacks that are specifically designed to detect the watermark still fail to do so, then this can be seen as unusually strong evidence that it is quality-preserving.

This work shows that existing schemes typically fall short in this respect, demonstrating an important weakness.
summary: The paper shows that it is possible to detect the presence of most existing watermarks using black-box interaction with the model, without knowing the watermarking key.
They also demonstrate that their attack is capable of estimating the parameters used in the watermarking schemes.
weaknesses: It is not surprising that they were able to easily detect the schemes they attacked. Those schemes are not designed to be undetectable.
In the "Limitations" section, they justify the choice to only consider these schemes with the claim that the provably-undetectable schemes "lack experimental validation" and "are not yet practical due to slow generation speed."

However, I believe these claims require justification because:
- "Excuse me, sir? Your language model is leaking (information)" is a practical implementation of an undetectable scheme. The author doesn't report any issues. This seems to already contradict the above claims.
- As I understand it, the generation speed of these techniques (including the one just mentioned) is _no slower_ than it is for any other scheme. They work essentially identically to other schemes, except that they are careful not to embed bias in cases where it might be noticeable without the key.
- I think that the reason there are relatively few practical demonstrations of undetectable schemes is just that most people doing experiments don't care about it. If you can get slightly better robustness by dropping undetectability, most experimentalists will go for that. However, since the message of the present paper depends on it _actually being difficult_ to build a practical undetectable scheme, it would be much more compelling if you at least attempt to do so.

Here is a simple undetectable scheme that you could try as a benchmark: Use Aaronson's scheme exactly (implemented in many places, e.g. Piet et al.), except that if a $k$-gram has empirical entropy (as defined in Christ et al.) less than $\lambda$, then don't use the Gumbel-max trick and instead just sample without bias according to the model. (Crucially, the first $k$ tokens in any response should be sampled exactly according to the model, without any watermark bias.) Note that this scheme is no slower than any other scheme. Detection with the key is also extremely fast.

It is easy to see that this scheme will require seeing roughly $2^{\lambda/2}$ tokens before it becomes detectable _without_ the key; and it should be detectable _with_ the key as long as the text has (empirical) entropy at least $\lambda$ in most sequences of $k$ consecutive tokens.
- If you find that this scheme only becomes practically undetectable once you set $k$ or $\lambda$ to be unreasonably large (such that detection with the key significantly suffers), then I would find the message that existing practical schemes much more compelling.
- If you find that this scheme is in fact practically undetectable for reasonable choices of $k$ and $\lambda$, then that would arguably be an even more compelling result (although the message would change slightly).

---

confidence: 4
contribution: 3
initial_rating: 5
presentation: 3
questions: 1.	Can you discuss more application scenarios of watermark detection? This question has a great impact on the contribution of the paper.

2.	Can you discuss potential commonalities between their detection techniques for different watermarking families? The universality of watermark detection technology is beneficial to reducing detection costs.

3.	Can the authors discuss more about why current detection methods are unable to determine the watermarking method of real-world production-level LLMs?
soundness: 3
strengths: 1. This paper, for the first time, examines the detectability of current watermarking schemes in a practical black-box setting, which is practical in the real detection scenario.
2. The method is well written and the method makes sense and is easily understood. Each method has a clear section structure. 
3. The experimental results in the black-box scenario verify the effectiveness of the method.
summary: This paper proposes a black-box detection method for identifying whether a watermark is embedded in a Large Language Model (LLM). In this paper, the detectability of current watermarking schemes is investigated for the first time in a practical black-box environment. The researchers developed statistical test methods to detect the presence of watermarks and estimate parameters using a limited number of black-box queries for three popular families of watermarking schemes; Red-Green, Fixed-Sampling and Cache-Augmented. Experimental results show that these approaches are effective and cost-efficient across multiple open source models and different settings. The paper also discusses the ethical implications of its work, highlighting the benefits of raising awareness of the ease of detection of watermarking schemes, despite the potential risk of misuse.
weaknesses: 1. Although the authors pointed out that their motivation is to study the ability of current watermarks to resist detection, they did not highlight the significance of watermark detection in real scenarios. Providing specific application scenarios of black-box watermark detection can help readers better understand the contribution of black-box watermark detection.

2. The results in Table 1 indicate the method in the paper is constrained by the need for distinct detection techniques for various watermarking methods, with poor generalization among them. As more watermarking methods are proposed, this may increase the cost of detecting watermarks.

3. Minor concern: Watermark detection results in Table 2 for production-level language models accessed via API are suboptimal and you can not conclude on the presence of a watermark,  which brings some concerns to readers about real-world detection.

---

confidence: 5
contribution: 3
initial_rating: 3
presentation: 2
questions: 1. The key algorithm for calculating the p-value in lines[197-240] is too vague. Could you please clarify it?

2. Could you provide a false positive rate for your detection algorithms? Additionally, the false positive rate may increase as we need to test various different types of watermarking schemes.

3. Could you provide a detailed algorithm for estimating the context size as described in lines[781-791], along with the corresponding experimental results?
soundness: 3
strengths: This paper suggests that current watermarking schemes may be susceptible to detection in the black-box setting and verify it in their experiments.
summary: The authors introduce statistical tests for detecting three main watermark families under blackbox setting, namely, Red-Green, Fixed-Sampling, and Cache-Augmented watermarks. They confirm the effectiveness of their methods in an extensive experimental evaluation across seven schemes and five open-source models, and execute them on three deployed models.
weaknesses: - This paper lacks a clear mathematical presentation of its algorithms, and the descriptions are often vague.

- The detection tasks for Fixed-Sampling and Cache-Augmented watermarks are trivial, and the proposed simple algorithm can be easily defended against.
  1. The detection algorithm based on unique outputs is not practical. In real-world applications, one can simply skip the first few tokens to ensure that generated outputs are different, which has been proposed in Algorithm 3 in Christ et al, 2024[1].
  2. The detection algorithm focused on cache is not applicable. It could take too much time for the detection to complete in waiting for the cache to be reset in a global cache. While user cache is usually not applicable due to a potentially large number of users.
  3. The cache mechanism is only a minor component of these watermarking schemes, and removing it often does not degrade performance, as discussed in Hu et al., 2023[2].


- Reporting median p-values over 5 watermarking keys is impractical, as only a single watermarking key is typically used per model in real-world applications.

The median p-value is not a good metric, as it does not reflect the actual false positive rate. It is also difficult to interpret.

- As shown in Figure 3, there are large deviations from the actual $\delta$, indicating that the current results may not be suitable for downstream tasks.

[1] Christ, Miranda, Sam Gunn, and Or Zamir. "Undetectable watermarks for language models." The Thirty Seventh Annual Conference on Learning Theory. PMLR, 2024.

[2] Hu, Zhengmian, et al. "Unbiased watermark for large language models." arXiv preprint arXiv:2310.10669 (2023).

---

confidence: 4
contribution: 3
initial_rating: 5
presentation: 4
questions: My questions are outlined in the weaknesses mentioned earlier. Please address those and the following:

- In transitioning from an attack-focused approach to a defensive one, do the authors believe that their tests would still be effective in detecting the presence of watermarks in texts that have been adversarially manipulated to remove them, especially in a blackbox scenario?
soundness: 4
strengths: This paper is extremely well-written. Kudos to the authors for taking time to ensure that the paper is concise, clear, and enjoyable enough for anyone to read. The formulations for each statistical test for detectability are clear and well explained. Providing detailed tests for each class of watermarks further strengthened the paper. The results highlight the strength of their approach as watermarks can be detected accurately, more so at a low cost. I also appreciate the fact that they experimented to see if their tests could cross detect other watermarks.
summary: This paper presents a significant contribution to the field of LLM watermarking. From the authors' claims, they are the first to provide a comprehensive study of black-box watermark detection. Their findings demonstrate the practical detectability of prominent watermarking schemes, challenging previous assumptions about their undetectability. This paper has provided the foundation for future research on more robust watermarking techniques and advanced detection methods.
weaknesses: - The methods, while detailed, appear to focus on a strict reverse engineering approach for detecting each specific class of watermark. Did the authors explore the possibility of a unified approach that could detect all classes of watermarks? What are the authors' thoughts on this?

- The experiments were limited to just three classes of watermarks. I believe this is okay, and future work could expand the scope to include other types, but it is a weakness for this paper.

- The cross-detection tests only applied to watermarks from different classes. However, there were no evaluations on whether the detection is robust to variations in the hyperparameters of the same watermark. Can the detection identify a watermark regardless of the hyperparameters used?

- Additionally, the paper lacks details on the efficiency of the detection tests. For instance, how many tokens are required to reliably detect the presence of watermarks using these methods? Addressing this could further minimize costs.

Meta-review: Summary: This paper studies the problem of detecting LLM watermarks in a black-box way, without even knowing the watermark key. Extensive experiments across three families of LLM watermarks, Red-Green, Fixed-Sampling and Cache-Augmented, verify the effectiveness of the proposed method.

Strengths:
1. This paper is the first work that detects LLM watermarks in a black-box way. It suggests that current watermarks are susceptible to detection in the black-box setting.
2. The paper is well-written and the experiments are rich.

Weaknesses:
1. Reviewers have concerns on the claim that the provably-undetectable schemes "lack experimental validation" and "are not yet practical due to slow generation speed."
2. Reviewers have concerns on the generalizability of the proposed detectors, as they are mostly based on reverse engineering. The experiments were limited to just three classes of watermarks.

All reviewers consistently vote for acceptance, two of who champion the paper with a score of 8. There is no doubt that the paper is above the acceptance bar of ICLR.

Decision: Accept (Poster)