Black-Box Detection of Language Model Watermarks
Authors: Thibaud Gloaguen
Nikola Jovanović
Robin Staab
Martin Vechev
Venue: ICLR 2025 Poster (2025)
Keywords: llm
watermarking
Primary area: alignment, fairness, safety, privacy, and societal considerations

Abstract: Watermarking has emerged as a promising way to detect LLM-generated text, by augmenting LLM generations with later detectable signals. Recent work has proposed multiple families of watermarking schemes, several of which focus on preserving the LLM distribution. This distribution-preservation property is motivated by the fact that it is a tractable proxy for retaining LLM capabilities, as well as the inherently implied undetectability of the watermark by downstream users. Yet, despite much discourse around undetectability, no prior work has investigated the practical detectability of any of the current watermarking schemes in a realistic black-box setting. In this work we tackle this for the first time, developing rigorous statistical tests to detect the presence, and estimate parameters, of all three 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. Further, we validate the feasibility of our tests on real-world APIs. Our findings indicate that current watermarking schemes are more detectable than previously believed.

Published as a conference paper at ICLR 2025
BLACK-BOX DETECTION OF LANGUAGE MODEL WATERMARKS
Thibaud Gloaguen, Nikola Jovanović, Robin Staab, Martin Vechev ETH Zurich
tgloaguen@ethz.ch, fiikolaa.jovaoviie robin.staab,
ABSTRACT
Watermarking has emerged as a promising way to detect -LM--eenrated text, by augmenting LLM generations with later detectable signals. Recent work has proposed multiple families of watermarking schemes, several of which focus property is
preserving the LLM distribution. This Anstribttion-prservaltt motivated by the fact that it is a tractable proxy for retaining LLM capabilities, as well as the inherently implied undetectability of the watermark by downstream users. Yet, despite much discourse around undetectabilityy no prior work has investigated the practical detectability of any of the current watermarking schemes in realistic black-box setting. In this work we tackle this for the first time, developing rigorous statistical tests to detect the presence, and estimate parameters, of all three popular watermarking scheme families, using only limited number of black-box queries. We experimentally confirm the effectiveness of our methods on range of schemes and diverse set of open-source models. Further, we validate the feasibility of our tests on real-world APIs. Our findings indicate that current watermarking schemes are more detectable than previously believed.
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 (Bommasani et al., 2021; EU Council, 2024). Tackling this issue, LLM watermarking, a process of embedding a signal invisible to humans into generated texts, gained significant traction.
Language model watermarking More formally, in LLM watermarking (Hu et al., 2024; Kirchen- bauer al., 2023; 2024; Kuditipudi et al., 2024; Sadasivan et al., 2023; Wang et al., 2024; Wu et al., 2024) 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 a prompt q can be reliably attributed to the model. To enable this, the provider modifies the generations using a secret watermark key E, that corresponding watermark detector can later
detect whether text was generated by L.M.
The prominent family of Red-Green watermarks (Kirchenbauer et al., 2023; 2024) achieves this by, at each step of generation, selecting context-dependent pseudorandom of logits to be boosted, modifying the model's 's next-token distribution. In contrast, the recently proposed families of Fixed- Sampling (Kuditipudi et al., 2024) and Cache-Angmented (Hu al., 2024; Wu al., 2024) schemes have focused on developing watermarks that aim to preserve the output distribution of the LLM. Both families achieve these guarantees in ideal theoretical settings, but no previous work has studied whether implementation constraints may violate those guarantees.
Watermark detectability The other key motivation of these Eettribution-preservin watermarks has been their inherently implied undetectability, which ideally makes it "impossible for users to discern [whether watermark has been applied]" (Hu et al., 2024), resulting in a "stealthy watermark, (i.e. one whose presence hard to distinguish from an wwwatermarked LM via sampling]" (Wu al., 2024). Such focus on undetectability in prior work raises the following research question:
"How delectable are existing watermarks in practical black-box settings?"

---

Published as a conference paper at ICLR 2025
In thene Cache Augmented matormzk?
Pick a Freisi
Derasburcy or Apple
Scrawberry.
pniselly
FAIL
Teadd for cedecordiered
?
A
Bhoices
Coepleca siie: 'Thie lhke oiery ot"
This do the staty of King that Liree...
MOX
FAIL
reeporton diseritty
Sampliing watormak??
Qparkn
Pintat the sestence: "I beoght 20002"
bought 22222
PASS (1r1e-))
contact
theic Red-Green meterraak??
IIRING
Figure I: Overview of our key contribution. Given black-box textual access language model, 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-Augmente watermarks ($4) and the test for Fixed-So Sited-Sampling watermarks ($3) fail, while the test for Red-Green watermarks ($2) successfully detects the watermark.
Surprisingly, while this question concerns an increasingly popular property of LLM watermarks, and raised as practically relevant in prior works such Piet et al. (2023) and Christ al. (2024), it has remained unanswered for any of the most popular families of LLM watermarking schemes.
This work: practical black-box watermark detection In this work, for the first time, we com- prehensively study 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., bog-probabilities) apart from the instruction- -undd model's 's textual response y. In this setting, the goal of the adversary is identify if the model is watermarked and determine which scheme was used. As shown in recent work, this information can also enable stronger attacks on the watermark such as removal or spoofing (Jovanović et al., 2024; Pang et al., 2024; Sadasivan et al., 2023; Zhang al., 2024). We explore the practical implications watermark detection in App. A.
To achieve this goal, propose rigorous and principled statistical tests for black-box detection of seven scheme variants of the three most prominent watermark families. Our tests, illustrated in Fig. 1, are based fundamental properties of the three respective scheme families: Red-Green ($2), Fixed-Sampling ($3), and Cache-Aure BugheeAugmented ($4) watermarks. In our extensive experimental evaluation, find that in practice, both distribution-modifyinn as well as distributionn-preerving schemes are easily detectable by our tests, even in the most restricted black-box setting. Highlighting the practicality of our tests, we show how they can be directly applied several real-world black box LLM deployments (GPT4, CLAUDE 3, GEMINI 1.0 PRO) at very little cost.
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 ($2), ($4).
Saxml-Sa ($3), and
We confirm the effectiveness and applicability of all our tests in extensive experimental evaluation across seven schemes and five open-source models ($5.1 and $5.2) and execute them on three deployed models ($5.3).
We develop tests to estimate important parameters of identified schemes (App. B), and further verify the robustness of our tests to additional scheme variants and adversarial modifications (App. F). Our code is publicly available at https://gitthub.com// com/etttccccmmthc////tee sri/ natermark-detectioon
We believe this work is a promising step in evaluating the practical detectability of current LLM watermarking schemes in the realistic black-box setting.
2

---

Published as a conference paper at ICLR 2025
2 DETECTING RED-GREEN WATERMARKS
In this section, we introduce our statistical test for detecting watermarks from the Red-Green family, illustrated in Fig. (bottom). To this end, we exploit their core property: applying the watermark introduces context centext-dependen logit bias, i... the model's output distribution is biased in a way that can greatly vary depending on the last few tokens that were generated (contex(), yet is unaffected by the tokens preceding the context (prefix). We provide more formal description of the test in App. C.
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 $5, we experimentally confirm the effectiveness of the test in realistic settings and study its query cost, and App. B.I explore methods to estimate scheme parameters once a watermark confirmed.
Background Assume watermark key & E N, pseudorandom function f. and hashing function Hosh: N > N. At each generation step i, a Red-Green watermark modifies the logits /1.vv of tokens from the vocabulary to promote subset of tokens (green tokens) before applying standard sampling. We consider two popular variants, LEFTHASH (Kirchenbauer et al., 2023) and SELPHASH (Kirchenbauer et al., 2024), both parametrized by 6, Rt, and using h 1 and h 3 previous tokens context, respectively. LEFTHASH seeds f with (aah((y--1) E. and uses split V into v/V| green tokens and remaining red tokens. For each green i, it then increases Hash(y:) Hash(y)) effectively using a context size of 4 by including the token yt yet to be generated. For both schemes, the watermark detector is based on observing significant number of green tokens in the input text. Other schemes from this family include varying the aggregation function or the context size (see $6).
4 by 8. SELFHASH differs by seeding ʃ with (Hash(Hts-)))
Modeling Red-Green watermarks Assume setting where the model chooses token from some restricted set Σ C V. following some context i2 (longer than the watermark context h)), which is preceded by prefix 1,. We discuss how construct such setting shortly. To model the watermark. we assume the following distribution for Pt (z), the probability the model assigns to some x E Σ:
exp ((x" 5rg (x) + etg (x)) (2),t(()) = - Ewer: exp ((w" + 8r (w) + to (w))/T)
(I)
where T > O is the sampling temperature. Here, we assume the existence of the true logit x., modeling the model bias towards x. The true logit is shifted by (z),, d-Beroullli random variable, where E Bt is the watermark parameter introduced above. Finally, (t,,t, (z) for different t1, l2 are iid symmetric error terms with mean 0 and variance o². Applying the logit function p + log(p/ p)) Eq. (1), we obtain:
)) (2) T
(z)
x T
(x) T
+
(2) log
Σ wEE\(>)
exp
w
81,(5) T
Etg,12
T
T
Approximating the log-sum-exp with a maximum, and WLOG setting w 0 for which is the maximum the log-sum-exp (as logits are shift-invariaan the above simplifies to
= /T (x)(x) + (x),
where ef (x) absorbs the previous error terms, and 8, (α) is a random variable equal for un- watermarked model and defined in Eq. (4) for watermarked models, with 8 the watermark parameter.
8/T
i G' and Vy E Σ, E 6/T if R and By E.yeG otherwise.
HER
(x)
Our test is based on detecting cases of 8,, (x(x)) # and checking that their occurrence is indeed independent of l, distinguishing model variance from the watermark bias.
3

---

Published as a conference paper at ICLR 2025
Querying strategy Recall that goal is to steer model into setting (via instruction, as we have no access to the completion model) where it makes a choice from some restricted set E. Importantly, 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 i (an arbitrary length string), d (a single token), and a word list E.
f Commlette the sentence \"(1l) (d-
HD using a random word from: [EE)).
Here, t1 serves the prefix, and t2 d. H as the context. For watermarked model, changing t2 is the only way to change the red-green vocabulary split, which can greatly affect the model's 's choice. For unwatermarked models, while we often see bias towards some choices from Σ, this bias will not strongly depend on 12. This holds for all context sizes S H and most aggregation functions, making our setting and the corresponding test directly applicable to different variants Red-Green schemes.
In our instantiation (illustrated in Fig. 1), we use N1 different 4 of the form "I bought", varying the verb, N2 different values of from the set of digits, a word list E of four different plural fruit names, and an example that uses different words to not bias the model towards 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 repetition of words or numbers outside of natural context.
Estimating the logits To collect the data for the test, query the model in two phases. First, we choose different values of E until we find one where the model does not always make the same choice, inducing Qı total queries. We set
be the most commonly observed word from Σ. Next, for each (t1 t2) pair we query the model until we obtain K valid responses (filtering out failures to follow the instruction), inducing in total Q2 2 N1 x N2 additional queries.
We use these samples to estimate the model logits corresponding to æ as 4, (x) = log -- (a)) where tt (1) is the empirically estimated probability of x in the responses. The result of the adversary's 's querying procedure is matrix LN x (visualized in Fig. 1) of such logit estimates.
Testing watermark presence Finally, we describe the statistical test based on the logit estimates LN x No. We first estimate o, the standard deviation of ,,, (z), as follows:
median| median[Var,,] (L)],
(5)
using the empirical median to improve robustness to unpredictable behavior caused by different 41- Then, we calculate the following two binary functions, which flag cases where we believe the model's probability was affected by a watermark:
R₂ (1,, 12) 1 1( (x) median [L] < -r
(6)
and
Gz 12) = (f - median [ > rā},
(7)
with I parameter of the test. In practice, account for model unpredictability. empirical median conditioned on t in Eqs. (6) and (7). For simplicity, let us denote ( E (1...,, N
the
and t2 E Ne). Let ent, (t2) = max -M (t,, t2), Em (t, 12)) count the
number of consistently flagged values for fixed tz. We define the following test statistic:
(L) max cntz (t2) min (t)) (2E[N2]
(8)
[2E(N2]
The null hypothesis of our test is Vt2: 8, (x) 0, i.e the model is not watermarked. To obtain a p-value, we apply Monte Carlo permutation test to Sz. checking if the flagged values are correlated with 12 in a way that indicates Red-Green watermark. Namely, we sample a set of permutations a of the matrix L uniformly at random, and calculate a 99% confidence interval of Pr[S.(((L)) > S, (L)), whose upper bound we take as our p-value. When this value small, we interpret that as evidence of watermark. Because Eq. (3) is permutation invariant when 8% (z) O, this ensures that the test does not reject under the null. This completes our method for detection of Red-Green watermarks. In App. B. we discuss estimation of 5 and h once the Red-Green watermark presence is confirmed.
4

---

Published as a conference paper at ICLR 2025
3 DETECTING TIXE-SSAMPLIN 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 (Kuditipudi et al., 2024), making the natural vector to exploit when detecting this watermark its lack of diversity. Given a prompt for which an unwatermarked model expected to produce highly diverse outputs, we can use this observation to distinguish between the two, as illustrated in Fig. (middle). For a more formal description of the test we refer to App.
As in $2, 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 $5.
Background For Fixed-Sane Exxed-Samlling watermarks, the secret watermark key sequence of length Rkey eyclically shifted uniformly at random for each generation to obtain &. and the entry & is used to sample from I. In the ITS variant, & is pair (u, T) E [0. x II, where II defines the space of permutations of the vocabulary V. Given the probability distribution p over V. obtained by applying the softmax function to 1, ITS samples the token with the smallest index in the permutation such that the CDF of p with respect sample the token arg minkev log ()/ /p:. The detection, for both variants, is based testing the correlation between the text and & using a permutation test. As noted $1, the key design goal of ITS and EXP is that, in expectation w.r.t. ç, 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.
least u. In the EXP variant, &, a value E [0, 1], and we
Modeling the diversity Let Un (g: i) denote a random variable that counts the number of unique outputs to a fixed prompt q in n queries, each of length exactly tokens. We introduce the rarefaction curve (visualized in Fig. I) as
R(n) = (U
For suitable y that enables diversity and large enough f, the unwatermarked model exhibits R(n) = For Fixed-Sane Sampling watermark (both ITTS and EXP variants), the watermark key segment used for sampling is determined by choosing rotation of the key 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 most equal to the key size nkey- The probability that output i was not produced is given by (1 1/nkey)". )" By linearity of expectation, we have the rarefaction curve
R(n) = Tike (1-
1
)m)
(10)
Tikey
Querying strategy To estimate R(n) of LM, we query with 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 the story of" that reliably causes diverse outputs, and set / high enough to minimize the chance of duplicates. In $5 we experimentally confirm that the number of unique outputs scales exponentially with i, and investigate the effect of small temperatures. Second, as larger Rkey make R(n) closer linear, must ensure that n is large enough for our test to be reliable. To do this, we can set an upper bound ikey on key size, and estimate the number of samples needed for given power by simulating the test test-our our experiments show that our test succeeds even on values of Akey far above practical ones.
Testing watermark presence Finally, to test for presence of Fixed-Sampling watermark, use a Mann- Whitney U test to compare the rarefaction curve R(n) = n with the observed rarefaction interpret this as evidence that the
data obtained as above. If the test rejects the null hypothesis, model is watermarked with a Exxe--Sampling scheme. We confirm the effectiveness our test in $5. In App. B.2 discuss estimation of the watermark key size nkkes after the watermark is detected.
5

---

Published as a conference paper at ICLR 2025
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 general approach that exploits the presence of a cache on fundamental level, and can be generally applied to any Cache-AAgmented scheme. Namely, we note that the cache sometimes reveals the true distribution of the model, which was also noted in recent work (Pang et al., 2024) as an undesirable property for a watermarking scheme. This implies that the distribution of choices condii-ondd (as seen in Fig. 1, top). which our adversary will exploit to detect the watermark. We first note that we provide a more formal description of the test in App. C. We also note that Eache-Augmented schemes generally use another underlying mechanism beneath the cache, and may be practical even in no-cache variant. In particular, for the schemes presented below, the underlying mechanism falls in the Red-Green family, and we experimentally demonstrate in App. F33 that the no-cache variants of these schemes can be detected by our Red-Green test from $2
We first recall relevant background, and then discuss 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-Augment 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 cache of previously seen contexts. Namely, whenever Wt-hae-1 is already present in the cache, they ignore the watermarking procedure and instead fall back standard generation. We consider three variants: d-REWEIGHT (Hu et al., 2024), 7-REWEIGHT (Hu et al., 2024), and DIPMARK (Wu et al., 2024) with parameter a (details in App. D). Previous works do not discuss practical instantiation of the cache. We consider two realistic scenarios: a global cache common to all users or a local per-user cache. With both instantiations, the cache is cleared after a set number G of generations.
Probing the true distribution In the first phase of querying, our goal 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:
Pick a fruit between: {fi) and {fa). Use the following format: {uc)-[fexampteh
and modify f1, f2. and fezampte # f1, 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 cache 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 ue was cached. Assuming WLOG that fi is the more likely choice for the model, we query it Q1 times with the same input to obtain pi. the estimate of the true probability of the model to pick fi.
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 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 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, use multiple user accounts. We query LM Q2 times and obtain ps, the estimate of the probability of fi 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 Q1 and Q2 we expect pi = P2. However, for all -ugge-Aug 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 's exact test with the null hypothesis pi = pa. If we observe low valuue, we interpret this as evidence that the model is watermarked with a Cache-Augmented

---

Published as a conference paper at ICLR 2025
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-GRERS schemes additionally over 5 watermarking keys. p-values below 0.05 (test passing) are highlighted in bold. 8R and 7R denote 6-REWEIGIIT and 7-REWEIGIIT schemes, respectively.
Red-Green
Fixed-Sampling
Buche-Augmented
Unwatermarked
LEFTHASH
SELFHASH
ITS/EXP
DIPMARK/;R
6R
T =
T
6,7
6 =
y =
5,y =
Rkng
Riyy
Model
1.0
0.2.5
0.5
2,
4,0.25
2048
0.3
R-G (82)
1.000
1.000
0.000
0.000
0.000
0.000
1.000
1,000
1.000
1.000
1.000
MISTRAL 7B
Fixed (83)
0.938
0.938
0.938
0,938
0,938
0,938
3.7c-105
18c-06
0.938
0.938
0.938
Cache (64)
0.570
0.667
0.607
0.608
1,000
0.742
0.638
0.687
2.4e-4
2.1e-3
5.6e-27
R-G (82)
0.149
0.663
0.000
0.000
0.000
0.000
0,121
0.128
0.149
0.149
0.149
I. AMA2
13B
Fixed (83)
0.972
0.869
0.938
0,938
0,938
8.1e-122
1.5e-07
0.938
0.938
0.938
Cache (84)
0.708
0,573
0.511
0.807
0.710
0.518
0.692
1.8e-2
5.3e-3
6.7c-32
R-G (82)
1.000
1,000
0.000
0.020
0.020
0.000
1,000
1,000
1.000
1.000
1.000
LLAMA2 70B
Fixed (53)
0.938
0,525
0.968
0.968
0.987
0.975
4,5e-125
1.7e-08
0.938
0.968
0.938
Cache (54)
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
scheme. Our experiments in $5 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. B.3 we discuss how to distinguish different variants of Cache- Aughee-ed schemes.
5 EXPERIMENTAL EVALUATION
In this section, we apply the tests introduced in $2-$4 $ to a wide range of models and watermarking schemes, and confirm their effectiveness in detecting watermarks. In $5.1 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 (extended results provided in App. F.1). In $5.2, we provide further experimental insights into the tests' robustness. Finally, in $5.3, we demonstrate that our tests are practical and can be applied to real-world LLM deployments.
A study of how the power of our tests scales with the number of queries is deferred to App. E. In App. F2-F.66 we present additional experiments, where we demonstrate the robustness of our tests to more schemes and scheme variants, including adversarial modifications and attempts to make schemes undetectable.
In particular, we study the multi-key variant of Red-Green schemes (App. F.2), the no-cache variant of Tache-AAgmented schemes (App. F.3), and the SynthlD- Text (Google DeepMind, 2024) scheme (App. F.4), released after the first version of our work was completed. We further study an adversarial modification which selectively disables the watermark (App. F.5), and a new entropy-conditioned variant of the AAR watermark (Aaronson, 2023) that is inspired by Christ al. (2024) (App. F.6).
5.1 MAIN EXPERIMENTS: DETECTING WATERMARKING SCHEMES
We perform our main set of experiments to verify the effectiveness of the tests introduced in $2-$4 in detecting watermarking schemes in realistic scenarios.
We run all our tests seven different instruction fine-tuned models (MISTRAL--7B, LLAMAA-7B, -13B, and -70B, LLAMA3-8B, YI1.5-9B and QWFN2-7B). in eleven different scenarios. We here present results of subset of those, and defer the rest as well as additional metrics to App. F.I. In each scenario, each model is either unwatermarked (where we vary the temperature) watermarked with certain scheme from the three main families (where 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 are testing for.
Experimental setup
For Red-Green tests, we set N1 = 10, N₁ = 9, = 1.96, a different Σ per model based on the first Q1 samples, use 100 samples to estimate the probabilities, and use 10000 permutations in the test.
7

---

Published as a conference paper at ICLR 2025
10f
105
Mocel
pvalue
10-2
Uama2-708
Model
Ro9
Uama2-72
110*
Settaahh
Leftllesh
Temperature
Uamm3-400 1-80
Watermark
10:
0.8
10.5
100 Number of samples per (6,
20
40
80
360
Tokens generated
Figure 2: Left: distribution of bootstrapped p-values of the Red-Green test 1LAMA2-11B with (6, 7) = (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.
We randomly sample set of 5 watermark keys and execute independent repetitions of the entire experiment, each time using exactly 1 of those keys. For Fixed- -ampliSg tests, we use 1000 queries and set f = 50. For Cache- Cache-Augment 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, where we report the median p-values, as in (Kuditipudi al., 2024), 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) 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 based on the same foundational principles. In particular, our Red-Green tests are robust to the seeding scheme, the logit bias and the green token fraction 7; our Tixed-Sampling tests maintain high confidence even for high values of 7kke and those higher than the number of queries; finally, our Gache-Augment scheme. Our results also suggest 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.
tests are robust to all details of the underlying
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 estimate the average cost of the tests be below $3 for Red-Green, $0.3 for Fixed-Sampling, and $0.1 for Cache- Aughee-dd tests, assuming latest OpenAl GPT40 pricing (see App. G for a detailed estimation of the costs).
5.2 ADDITIONAL EXPERIMENTS: VALIDATING THE ASSUMPTIONS
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 ($2) relies on the sampling of model outputs to estimate the probabilities of the model. As the resulting p-value 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 (t1, t2), we sample with replacement from single set of model outputs, and report the median p-value Pmned across such samples. In Fig. 2 (Left) we report the resulting distribution of Pined, where one point corresponds to one independent run. We see that already for 100 samples per (f1, 12) (as used in Table 1), 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, where still observe reliable results in the median case across experiment repetitions.
Diversity assumption in Fixed-Sampling tests As detailed in $3, the Fixed- Sampling test relies on the unwatermarked model being sufficiently diverse, i.e., for the number of unique outputs
8

---

Published as a conference paper at ICLR 2025
Table 2: The results of our watermark detection tests on black-box LLM deployments.
GPT4
CLAUDE GEMINI 1.0 PRO
R-G ($2)
0.998
0.638
0.683
Fixed ($3)
0.938
0,844
0.938
Cache ($4)
0.51
0.135
0.478
R(n) = BlUn.g t)] after n queries with prompt and response length t, it should hold that R(n)) = n. Our goal 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 increases. In particular, we assume
R(n) - n - -n- exp(=a(T))),
(11)
where (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 (Right). Eq. (11) holds, we expect the resulting relationship to be linear, which is indeed confirmed by our results. While a (the slope of the line) varies across settings, we see that a bit over 200 tokens would be sufficient for the line drop to 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 (Kuditipudi et al., 2024; Piet al., 2023), indicating that R(n) = n and our assumption met, validating our p-values.
5.3 DETECTING WATERMARKS IN DEPLOYED MODELS
Finally, we demonstrate the applicability of the statistical tests introduced in $2-$4, 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 $5.1, and use the API access for efficiency reasons-we do not rely any additional capabilities, and our tests could be easily run in the web interface. For the Mache-Augmenter tests, we assume global cache that clears after 1000 seconds. For the Fixed-Sampiinn Sampling test on CLAUDE due its lack of diversity, we used ensure the hypotheses are met. Our results in Table 2 show that the null hypothesis is not rejected for any of the models and any of the tests. Hence, we can not conclude on the presence of watermark.
75 tokens per query to
RELATED WORK
Language model watermarking Besides the approaches by (Hu et al., 2024; Kirchenbauer et al., 2023; Kuditipudi al., 2024) introduced above, there are various methods building similar ideas. Hou et al. (2024); Liu et al. (2024b); Ren et al. (2024) all apply variations of (Kirchenbauer et al., 2023) on semantic information, while Gu et al. (2024) distills new model from the output of 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-bi bit watermarking (Wang al., 2024; Yoo et al., 024s) aim to not only watermark generated texts but encode additional information in the watermark.
Attacks on language model watermarking Attacks on LLM watermarks have so far been mainly investigated terms of scrubbing (Jovanović et al., 2024; Kirchenbauer et al., 2023; Sadasivan et al., 2023) (i.e., removal of watermark) and spoofing (Gu et al., 2024; Jovanović et al., 2024; Sadasivan al., 2023) (i.e., applying a watermark without knowing {). Notably, Jovanovié et al. (2024) showed that observing watermarked texts can facilitate both attacks various distribution-moddiiinng schemes, disproving common robustness assumptions (Kirchenbauer et al., 2024). However, using this and similar attacks as means of practical watermark detection is infeasible, 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, setting fundamentally at odds with our threat model of black-box watermark detection.
they generally
The closest related work to ours is Tang et al. (2023), that tackles the problem of watermark detection in strictly simpler settings where the adversary either has access an unwatermarked counterpart

---

Published as a conference paper at ICLR 2025
of the target model, or 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 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 (Rando and Tramèr, 2024) well as the extraction of the hidden-dimens dineen--imeesionalltty or the weights of the embedding projection layer (Carlini al., 2024). Nasch et al. (2023) have shown practical attacks to recover the decoding mechanism of non-watermarked black-box models. Given access to output logits, Li and Fung (2013) have further demonstrated that it is possible train inversion model that aims to recover the input prompt.
CONCLUSION AND LIMITATIONS
In this paper, we have focused on the problem of detecting watermarks 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 show that most popular practical watermarking schemes are detectable.
Limitations One limitation of our tests is that they are restricted to the three scheme families discussed in $2-$4. These are however 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. We confirm this in our additional experiments on a multi- key variant of Red-Green schemes (App. F.2). no-cache variant of Cache- Augmented schemes (App. F.), and SynthID-Text (Dathathri et al., 2024) (App. F.4.. As shown in App. F,5 our tests are also robust adversarial scheme modifications, aimed at bypassing our tests.
is still possible that a model provider deploys a practical scheme based on an entirely novel idea, which our tests would not be able to detect. A promising starting point may be the scheme proposed by Christ et al. (2024), which has theoretical undetectability guarantees, but is not yet practically viable. We discuss this in more detail in App. F.6, and introduce and evaluate proof-of-concept variant of AAR (Aaronson, 2023) that incorporates similar idcas. Our preliminary results show that this approach indeed enhances stealth, but the cost of reducing the watermark strength and potentially other important properties, which we do not evaluate in this work. We hope our initial investigation inspires more thorough research in this direction.
As another limitation, while we base our tests on fundamental properties of scheme families, we have no theoretical guarantees of power and only provide empirical evidence based on the tested schemes.
Finally, our tests make several model assumptions, such as symmetric error terms, perfect sampling, and the unlikely event of the red-green split (in Red-Green schemes) being the same for all contexts on the observed domain. While we validate that these assumptions are sufficiently met on several open-source models, we cannot guarantee that all models adhere to them.
ACKNOWLEDGEMENTS
The work has received funding from the Swiss State Secretariat for Education, Research and Innova- tion (SERI).
ETHICS AND REPRODUCIBILITY STATEMENTS
Our work may be used by malicious actors to detect watermarks on deployed models. This could allow them to favor unwatermarked models or help them mount additional attacks that could negatively affect the model provider that deployed the watermark. Yet, we believe the benefits of raising awareness about the easy detectability of most watermark schemes outweigh the risks of our work.
To ensure reproducibility, before each experiment in $5 and App. B, E and F, we thoroughly describe the experimental setup to ensure reproducibility. The code needed reproduce tests
10

---

Published as a conference paper at ICLR 2025
open-source models for the Red-Green watermarking scheme family ($2), the Fixed- Fixed-Sampling Sampling family ($3), and the Cache-Aughe Autbented family ($4) is available at https: / com/eth -ri/ watermark rk- detection. This also includes the code used to perform the tests deployed models ($5.3), which shows a concise way to perform the test in practical settings, and the additional experiments in App. F.
REFERENCES
Aaronson, S. (2023). Watermarking of large language models. In Workshop Large Language Models and Transformers, Simons Institute, UC Berkeley.
Bommasani, R., Hudson, D. A., Adeli, E., Altman, R. B., Arora, S., von Arx, S., Bernstein, M. S., Bohg, Bosselut, A., Brunskill, E., Brynjolfsson, E., Buch. S., Card, D.. Castellon, R., Chatterji. N. S., Chen, A. S., Creel, K., Davis, J. Q. Demszky, D.., Donahue, C., Doumbouya, M., Durmus, E., Ermon, S., Etchemendy, J., Ethayarajh, K., Fei-Fei, L.., Finn, C.,, Gale, T., Gillespie, L.,, Goel, K. Goodman, N. D., Grossman, S., Guha, N., Hashimoto, T., Henderson, P., Hewitt, J., Ho, D. E., Hong, J., Hsu, K., Huang, J., Icard, T., Jain, S., Jurafsky, D., Kalluri, P., Karamcheti, S., Keeling, G., Khani, F., Khattab, O., Koh, P. W., Krass, M. S., Krishna, R., Kuditipudi, R., and et al. (2021). On the opportunities and risks of foundation models. arXiv.
Carlini, N., Paleka, D., Dvijotham, K. D., Steinke, T., Hayase, J., Cooper, A. F., Lee, K., Jagielski, M., Nasr, M., Conmy, A., Wallace, E., Rolnick, D., and Tramèr, F. (2024). Stealing part of production language model. ICML.
Christ, M., Gunn, S., and Zamir, O. (2024). Undetectable watermarks for language models.
Dathathri, S., See, A., Ghaisas, S., Huang, P.-S., McAdam, R., Welbl, J., Bachani, V.. Kaskasoli, A., Stanforth, R., Matejovicova, T., Hayes, J., Vyas, N., Merey, M. A., Broon-Coohes J., Bunel, R., Balle, B., Cemgil, T., Ahmed, 7., Stacpoole, K., Shumailov, I., Baetu, C., Gowal, S., Hassabis, D., and Kohli, P. (2024). Scalable watermarking for identifying large language model outputs. Nature.
EU Council (2024). Proposal for a regulation of the european parliament and of the council laying down harmonised rules artificial intelligence (artificial intelligence act) and amending certain union legislative acts analysis of the final compromise text with a view to agreement.
Fairoze, J., Garg, S., Jha, S., Mahloujifar, S.. Mahmoody, M., and Wang, M. (2023). Publicly detectable watermarking for language models. IACR Commun. Cryptol., 1:31.
Google DeepMind (2024). Identifying ai-generated content with synthid. https://deepmind. last accessed: Nov 20 2024.
Gu, C., Li, X. I.., Liang, P., and Hashimoto, T. (2024). On the learnability of watermarks for language models. ICLR.
Hou, A., Zhang, J., He, T., Wang, Y., Chuang, Y.-S., Wang, H., Shen, L., Van Durme, B., Khashabi, D., and Tsvetkov, Y. (2024). Semstamp: A semantic watermark with paraphrastic robustness for text generation. NAACL.
Hu, Z. Chen, L.., Wu, X., Wu, Y., Zhang, H., and Huang, H. (2024). Unbiased watermark for large language models. ICLR.
Jovanović, N., Staab, R., and Vechev, M. (2024). Watermark stealing in large language models. ICML.
Kirchenbauer, J., Geiping, J., Wen, Y., Katz, J., Miers, I., and Goldstein, T. (2023). A watermark for large language models. In ICML.
Kirchenbauer, J., Geiping, J., Wen, Y., Shu, M., Saifullah, K., Kong, K., Fernando, K., Saha, A., Goldblum. M., and Goldstein, T. (2024). On the reliability of watermarks for large language models. ICLR.
Kuditipudi, R., Thickstun, J., Hashimoto, T., and Liang, P. (2024). Robust distortion free watermarks for language models. TMLR.
11

---

Published as a conference paper at ICLR 2025
Li, Y. and Fung, P. (2013). Improved mixed language speech recognition using asymmetric acoustic model and language model with code-switch inversion constraints. ICASSP.
Liu, A., Pan, L., Hu, X., Li, S., Wen, L., King, I., and Yu, P. S. (2024a). A private watermark for large language models. ICLR.
Liu, A., Pan, L.., Hu, X., Meng, S., and Wen, L. (2024b). A semantic invariant robust watermark for large language models. ICLR.
Nasch, A., Krishna, K., lyyer, M., and Houmansadr, A. (2023). On the risks of stealing the decoding algorithms of language models. arXiv.
Pang, Q., Hu, S., Zheng, W., and Smith, V. (2024). Attacking LLM watermarks by exploiting their strengths. arXiv.
Piet, J., Sitawarin, C., Fang. V., Mu, N., and Wagner, D. (2023). Mark my words: Analyzing and evaluating language model watermarks. arXiv.
Rando, J. and Tramèr, F. (2024). The worst (but only) claude 3 tokenizer. https://github.com javirandor/anthropicc tokenizer.
Ren, J., Xu, H., Liu, Y., Cui, Y., Wang, S., Yin, D., and Tang, J. (2024). A robust semantics-hased watermark for large language model against paraphrasing. In NAACL.
Sadasivan, V. S., Kumar, A., Balasubramaniaa, S., Wang, W., and Feizi, S. (2023). Can ai-generated text be reliably detected? arXiv.
Tang, L., Uberti, G., and Shlomi, T. (2023). Baselines for identifying watermarked large language models. arXiv.
Wang, L.,, Yang, W., Chen, D., Zhou, H.,, Lin, Y., Meng, F., Zhou, J., and Sun, X. (2024). Towards codable text watermarking for large language models. ICLR.
Wu, Y., Hu, Z., Zhang, H., and Huang, (2024). resilient and accessible distribution watermark for large language models. ICML.
Yoo, K., Ahn, W., and Kwak, N. (2024s). Advancing beyond identification: Multi-bit watermark for language models. NAACL.
Zhang, Z., Zhang, X., Zhang, Y., Zhang, L. Y., Chen, C., Hu, S., Gill, A., and Pan, S. (2024). Large language model watermark stealing with mixed integer programming. arXiv.
12

---

Published as a conference paper at ICLR 2025
A PRACTICAL IMPLICATIONS OF WATERMARK DETECTION
In this section, we discuss some practical use cases for detecting whether a given black- box API is watermarked, as ways to provide additional motivation for work.
The objective behind watermarking an LLM is to enable the detection of whether a given text was generated by specific LLM. In practice, it should allow both holding model provider accountable for harmful text generated by its model and holding users accountable for using an LLM in scenarios where its use is inappropriate or forbidden.
Being able to detect a watermark behind an LLM deployment provides a malicious user with multiple opportunities. First, detection is common prerequisite for performing spoofing attacks (Gu et al., 2024; Jovanović et al., 2024; Zhang et al., 2024), where a malicious user learns the watermark in order to generate arbitrary watermarked text without using the watermarked model. Such attacks can be used to discredit a model provider by generating text that appears to be genuinely watermarked and attributing to the model provider. Second, detection is prerequisite for assisted scrubbing attacks (as in Jovanović et al. (2024)), where malicious user can more successfully remove the watermark from an LLM generated text compared to blindly rewriting the watermarked texts. Consequently, such malicious users Lastly, knowing that a particular LLM is watermarked may lead a malicious user to avoid using that LLM entirely and instead favor another LLM that is not known to be watermarked.
nullify any positive effects associated with the watermark deployment.
Hence, knowing how detectable schemes are in practice is, besides theoretical interest, important for model providers or legal authorities have realistic expectations regarding the effectiveness and pitfalls of given watermarking scheme
B ESTIMATING SCHEME PARAMETERS
In this section, 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 $2-$4 from which we derive all the estimators.
B. 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 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 5, establish a parametrized model based Eq. (2) that relies flagging function from Eq. (7), and additional estimates 4,,, (w) for every Σ, computed on the same data as above, requiring no additional queries. For each w E Σ, we set:
(w) = =w,, + Gw (41,42) log
exp (w), + (G,((1, (w)
Σ
(12)
and set Vl,, Wr, = O for a single w E Σ, as logits are shift-invariant. Fitting the parameters and all We, by minimizing the mean squared error with gradient descent allows recover 8/T 8. If is known or estimated separately, this term can be removed.
Let / N denote the context size, i.c., the number of previous tokens considered by the watermarking scheme. To estimate h, we use the same prompt template as in $2, with fixed prefix t and digit d, but with varying H N and perturbation digit d' prepended to d.
f" Complete the sentence \"((}} (d' (d HY using random word from: [{E]]*
13

---

Published as a conference paper at ICLR 2025
Algorithm 1 Context Size Estimation
Require: Two tokens & d, set of perturbation tokens E', set of tokens Σ, number of samples N, upper bound on the context size Hmaz. x" E Σ, E [0, 1]. LMM M
1: ş < O, P E [0, 1] 1x1x|[*\ Xmaaa X|2]
2: for each token d' in 2'' do
Generate the estimator data
3:
for H from to Haaz do
4:
prompt + f'Complete the sentence (ti] [d'} {d.H) using a word in (Σ}" for i from to N do resp < (prompt)
5:
6:
7:
2, PatseResponse(resp)
8:
d,, H (x,) + Pi,, H (2+) + 1/N
9: end for
10: end for
11: end for
12: for each token d' in Σ' do
D Build logit estimation matrix
13:
for H from to H max do
14:
for i from 1 to N do
15:
d, (2) <- log
Pe aad Po a (2)
end for 17: end for
16:
18:
end for
h+11
20: for H from to Haar do
&- MoodTest (l, (1("), h
21:
if S pten
23:
h+H
24:
break
end
26:
end for
27:
return
The probability distribution of the model output will abruptly change when H exceeds the context size h, as the change d' will not alter the red/green split of the vocabulary. We then compute the corresponding logit estimator L, d,d' for every variation of the above prompt by sampling N times from the model. For a Red-Green watermark with context size h, we then have the following property:
Vi,, V, Vh < h, h2 < h, vd E V, i, an m, Vt,, d E V. 1h 2 h h2 2 h, Vd' E V. V, =o d,
(13)
(14)
Vt,, E V. Vhg h, h2 2 h, vd' E V, d, Jo
(15)
Therefore, for a given pair (d,4) E Σ Σ, we test the difference between the distributions of 4,, HH-1 11 and h,, H using Mood test. Here, d' is treated as a random variable uniformly sampled from subset of E. Starting with H and incrementing H by I at each step, we continue this process until the Mood test exceeds given threshold p E [0, 1). The value of H at which the threshold is first rejected is set to h a- The estimator computed using a fixed (d, t1) Σ x is detailed Algorithm
Estimating is more challenging, as in contrast to 5, 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-sceding. the rejection sampling interferes with the behavior of We leave further exploration of this problem to future work.
Experimental results We computed the estimator for on the LeftHash variant with y 0.25 and varying ó from 0 to The results are shown in Fig. 3, with the 95% confidence intervals reflecting the sampling error. The estimator successfully estimates 5 for all models with sufficient number of
14

---

Published as a conference paper at ICLR 2025
With looprobs
10
100
1000
46-
234
10.20
Uama--2
13-
Uamab
Figure 3: Estimation for different models using LeftHash with y = 0.25. The number of samples used increases from left 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 the sampling of the model outputs.
Figure 4: Estimation of the context size h in Red-Green watermarks with LeftHash h = 2 (top) and LeftHash 3 (bottom) LLAMA2-7B. Each box corresponds to the distribution of i, d,,' .H- The green shading corresponds the region where hi H. fixed l is used across all plots.
15

---

Published as a conference paper at ICLR 2025
Table 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 + 0.6
259 + 0.5
256 + 0.5
257 + 0.5
256 + 0.6
2048
1978 10
2107
12
2006 13 2070 + 14
1831 + 10
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) are met in practice.
Estimating the context size for Red-Green schemes requires performing a new attack once the model flagged as watermarked. We estimate the context size for three different models (MISTRAL- 7 LLAMA2-13 13 and LLAMA2-700B using LeftHash with å = 2 and 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 > being in the green vocabulary, and thus diminishes the perturbation's is 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 the estimator across 10 different t2 and then consider the median of the 10 estimators our final estimator. This estimator applied on the SelfHash variant with = 2 and 7 0.25 is successful on all three models. It also does not change the results LeftHash and can be used estimator for h in all cases, when the additional cost of 50, 000 queries is not prohibitive. In Fig. 4, we see that for both LeftHash 1,, d,d' .H with respect to d' changes significantly when H exceeds h. The H which this abrupt change in distribution occurs corresponds to the estimator and matches the actual value of h.
more robust
2 and LeftHash h 3. the distribution of each logit estimator
B.2 ESTIMATION OF FIXED-SAME BHED--SMPPLNG WATERMARKING SCHEME PARAMETERS
Our approach does not distinguish between the variant of the Samplingg watermark used (ITS or EXP), as the diversity property that we exploit is common to both. The only other relevant parameter of FFxed-SSami Fixed-Sampling schemes is Tkey.. To estimate it, we use non-linear regression on the rarefaction curve using (10) and the same data that we used for the presence test, and compute the confidence intervals using bootstrapping.
Our results given in Table 3. We see that the estimator is consistent across different models and remains relatively precise even for values of Taky higher than the number of queries.
B.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 a (recall that = 0.5 corresponds to 7-REWEIGHT). To do this, we use the same approach as $4 to obtain pí and p2, where WLOG we assumed p1 > 0.5. If we observe f12 = 0 this directly implies 5-REWEIGHT watermark. If we observe p12 E (0, 1), we learn the following: yo2 2pi then a first case can be further improved with additional queries with different p1. Finally, if observe P2 = we repeat the whole procedure in total K times, following the same case distinction P2 repeats in all K runs, conclude that the model is watermarked with 8-REWEIGHT.
pi, otherwise a = lp p2.. The bound in the
Using the same parameters as the one for the test, we distinguish with 100% accuracy between a DIPMARK and 5 5-REWEIGHT watermark. However, the estimation of a becomes unreliable for higher values of a, 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 $4 was robust to such behavior, this does not hold for the estimation of a.
C ALGORITHMIC DESCRIPTIONS OF THE DETECTION TESTS
We present an additional algorithmic description of the Red-Green test ($2) in Algorithm 2, the Tixed-Sampiin test ($3) Algorithm 4 and the Cache-Augmenter test ($4) in Algorithm 5.
16

---

Published as a conference paper at ICLR 2025
Algorithm 2 Red-Green Test
Require: Token set Σ, token set Ti, token set T2, context size H, number of samples N, number of
permutation M, x²
Σ, r > 0, LM M
ý < 0. e 00, 1]
2: for each token & in [i do
Generate test data
3: for each token dl in T2 do
4:
1/2 - d H
> Concatenation
5:
prompt + CoComplete the sentence [tI] {12) using random word from (Σ)"
6:
for i from to N do
7:
resp - (prompt)
8:
2, ParseResponse (resp) (resp)
9:
Pr..t (z)) - ,o (z;) + 1/N
10: end for
11: end for
end for
13:
for each token é in Ti do
Build logit estimation matrix
for each token d in T2 do
15:
t2 f H
> Concatenation
(1) log Pe).t. (x) (1)
16:
17: end for
18: end for
19: T. + hiist (x*)
S Statistic(L)
21: 0+0
b> Permutation test
for each i range M do
23: a U
24:
Ptp+ (tatistic(a((L)) 2 S]
D. L is permuted element wise
end for
26: x PPMM
return p
Algorithm 3 Red-Green Statistic
Require: Logit estimation matrix L, r > O, token list Ti, token list T2
1: + 0, E N |x Tal
2: G < 0, G |TTTT
3: σ² +- median [Var,, (L)]
4: median [4]
5: for t in TT do
6: for to in T- do
7: if [L,, 12]
m < -rô² then
8:
R [2]
Abnormally low logits are considered Red
9:
end if
if L to] Glt, t2l =
m r then
11:
Abnormally high logits are considered Green
end
13: end for
14: end for
15: count 0, count E N//al
Count the number of Red/Green tokens per fixed context
16: for ty in T2 do
17: count[te] + max (Et, Rit,, t2), E,,r, Giti,t2])
18: end for
S
maXt,eT, count([2] minger, count([2]
20: return
17

---

Published as a conference paper at ICLR 2025
Algorithm 4 Fixed-Sampling Test
Require: Number of queries Q, number of tokens to generate t, prompt, LM M 1: 1 0, R No
2: seen +-
3: for from 1 to Q do
4: I2 f- -
5:
if st $ seen then
6:
R|i Rli
7:
seen f seen U {
8: else
9: R|i + Rii -
end if
11: end for
p <- Mann-Whitney((P R, (1,,....,))
13: return
Algorithm 5 Cache- Augmented Test
Require: Number of queries Q1, Number of queries Q2, fi * f2 E V, uc E V*, LM M
prompt f"Pick randomly (.f1) of [fe] and prepend [uc] your choice."
2: #1 <- 0
b Phase 1: Probing the watermarked distribution
3: for from Q1 do
4: resp t- M(prompt)
5: I; + Parsseesponse
6: rf fi then
7: P1 f1
8: end if
9: end for
10: f22
Phase 2: Probing the watermarked distribution
11: for from to Q2 do
Clear the cache
13: resp + M(prompt)
I; + ParseResponse (resp)
15:
if xG fi then
16:
P2 + p2 + 17: end if
18:
end for
19:
p f FischerExact((2) Q1 - -1), (p2, Q2 p2))
20: return p
D DETAILS OF
SCHEMES
We provide the details of the three Cache-Augmenter watermarking schemes considered in this work: 5-REWEIGHT (Hu et al., 2024), REEEIIGHH (Hu et al., 2024), and DIPMARK (Wu et al., 2024), that were omitted from $4.
All three variants, at each generation step t., jointly hash the watermark key & E Z and the preceding context 0t-h:11 (commonly setting 5) using SHA256, and use the result seed to sample a code E, E PE uniformly at random. Let denote the probability distribution over V. obtained by applying the softmax function the logits. For the 5-REWEIGHT variant, PF. [0, 1]. and the code E, is used to sample the token in V with the smallest index, such that the CDF of at least Eç. For the REEEEEIGHT variant and DIPMARK, Pg is the space of permutations of V. For YETWEIGGH, we transform
new distribution p' by. for each token i E V. setting - (2( - 1)), where we have (i') = ΣS 1 (FE()) S d')p(j) and fe(u) = max(2u- 12
pi(1) = (E
-1,0) 0), effectively dropping the first half of the permuted CDF For DIPMARK, given parameter E [0, 0.5). this is generalized by using f2(v) max(v a. 0) + max(e (1 a), recovering REEWEIGGHT for a 0.5. The former two variants perform detection using a log- likelihood ratio test (requiring access L.M, while DIPMARK uses model-independdnt test.
18

---

Published as a conference paper at ICLR 2025
0.8
0.5-
0.5
0.5
50
0.4-
100
10
0.4
0.2
1000
0.2
2000
0.5
100
200
20.0
2.00
560
000
700
10:
10
Number quarties
queftes scale)
Figure 5: Left: power at 5% of the Fixed-Sampling test under the infinite diversity assumption. Right: power at 5% of the Cache-Augmente test assuming 0.5. In both figures, the power is evaluated using 1000 repetitions of the test.
E SCALING OF THE TESTS POWER WITH THE NUMBER OF QUERIES
In this section, we study the evolution of the test's power with respect to the number of queries for both the Fixed-Sampling and the Cache-Augmented tests ($3 and $4). For the Red-Green test, have already presented a study of the influence of the number of queries in $5.2.
-Smmping test We first consider the Fixed-Sampling test ($3) under the assumption that, under the null, the model diversity is infinite and, under the alternative, that the model outputs are sampled from a uniform categorical distribution with Tikey choices. We then simulate the test for different values of Tikey and the number of queries to estimate the power. In Fig. 5 (left), that the test power has a quick phase transition from 0 to at a number of queries less than the key size. This means that the test is robust the increase in key size, the watermark strength decreases linearly with Tiky according to Kuditipudi et al. (2024).
Cache-Augmented test We consider the Cache-Augmentee test ($4) under the assumption that the cache is cleared between queries and that fi 0.5. We then simulate the test under those assumptions for different values of a and the number of queries Q == Q = Q2. In Fig. (right), we that for the range of values considered in Wu et al. (2024), the test power reaches 1 in at most Q = 100 queries, which highlights the costteffectiveness of the test.
F ADDITIONAL EXPERIMENTS
In this section we present several additional experiments. In App. F.1 we extend our main results to additional models and scheme variants. App. F.2-F66 we demonstrate the robustness our tests to the multi-key variant of Red-Green schemes, the no-cache variant of Cache-Augment the SynthID-Text (Google DeepMind, 2024) scheme, the adversarial modification which selectively disables the watermark, and an condipy-on variant of the AAR watermark (Aaronson, 2023) that is inspired by Christ et al. (2024), respectively.
schemes,
F.1 ADDITIONAL MODELS AND SCHEME VARIATIONS
We extend the experiments from $5.1 using four additional models, LLAMA2-7B, LLAMA3-8B, Y11.5-9B and QWEN2-7B, well as more variations of the watermarking schemes' parameters to further assess the robustness the tests. The experimental setup for the additional results consistent with the one described in 1..1.
Our exhaustive results are presented Table 4. 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 satisfied across wide range of models, indicating the tests' relevance in practical scenarios.
Moreover, in Tables and present the rejection rates of our tests 5% and 1% significance levels, respectively. These results show that the p-values are, for independent runs of the experiments, consistently low across all models and watermarking schemes when the models watermarked and
19

---

Published as a conference paper at ICLR 2025
Table 4: 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-GRER schemes additionally over 5 watermarking keys. p p-values below 0.05 (test passing) are highlighted in bold. 5R and 7R denote 6- 6-REWEIGIIT and 7-REEEIGIIT schemes, respectively.
Red Green
Fixed Sampling
Cache Augmensed
Unvestemarko
LiatHAsi
SELrHASH
ITSEEXP
DiPMARKIS
T
T-
4.
4-7
4,7-
6.2-
6-7
4.7
Model
Test
1.0
0.7
2,0.25
2,0.5
4,0.25
4.0.5
0.2.5
2,0.5
4, 1.025
4,0.5
236
2048
0.5
0.5
R-G ($2)
1 1000
1,000
0.000
0.000
0.000
0,000
0.900
0..00
0.000
0.000
1,000
1,000
1,000
1,000
1,000
MISTRAL
Fooed ($3)
0.33
0.938
0938
0.935
0.938
0.938
0.528
0.938
0.938
0.938
3.7e-105
1.5e06
0.928
0.938
0.938
Cache ($1)
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-1
2.1e-3
5.de227
B.G (82)
0.663
0.000
0.000
0,000
0,800
0,000
0.000
0.121
0.128
0.149
0.149
ELAMAA 138
Fixeel (83)
0.972
0.869
0.338
0.938
0.938
0.938
0.938
0.938
0.935
0.966
8.1e-122
1.5e-07
0.918
0,958
0,938
Cache (64)
0.573
0.511
0.657
0.619
0.710
0.583
0.518
5.3c-
6.76-22
(82)
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
ELAMAZ
708
Fixed (83)
0.938
0.525
0.968
0.963
0.889
0.968
0.963
0.987
0.975
0.990
4.5e-125
1.7608
0.918
0,968
0.918
Cache (64)
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,4r-3
586-28
R-G (82)
1,000
1,000
0.000
0.000
0.000
0,000
11,000
0..00
0.100
0.000
1,000
1,000
1,000
1,000
1,000
L
Faod ($3)
0.944
0.986
0.388
0.935
0.933
0.933
0.938
0.52%
0.538
0.938
1.87-600
0.928
0.938
0.938
Cache ($1)
0.604
0.602
0.623
0.705
0,728
0.993
0.620
0.718
0.610
0.593
0.476
0.588
4.3e-6
4.5e-7
1.3e-21
(82)
1,000
1.000
0.000
0.000
0.000
0.000
1.000
1,000
1,000
LLAMA3
Fixed (83)
0.938
0.938
0.938
0.938
0.938
0.938
0.938
0
0.968
0.938
2.3e-60
0.064
0.918
0.958
0,938
Cache (64)
0.504
0.605
0.731
0.720
0.618
3.3r-8
35c-18
(82)
0.633
0,194
0.000
0.000
0.000
0,000
0.000
0.000
0.000
0.000
0.639
0.620
0,633
0.633
0,633
VIL.
9B
Fixed (83)
0.938
0.938
0.938
0.938
0.958
0.918
0.952
0.986
0.938
0.986
5.86-6
0.002
0.918
0.967
0,938
Cache (64)
0.680
0.513
0.609
0.644
0.716
0.680
0.619
0.513
0.705
0.490
0.618
0.564
0.000
0.000
0.000
OWENZ
R-G ($2)
0.865
0:571
0.117
0.001
0.000
0
01000
0.816
0.001
0.179
01865
0.865
0.865
0.865
0.865
Food (53)
0.33
0.938
0.388
0.936
0.933
0.933
0.528
0,938
0.938
0.938
1.1e600
0.923
0.933
Cache ($4)
0.573
0.678
0.550
0.678
0,618
0.559
0.687
0.566
0.691
0.510
0.687
0.683
0,000
0.000
0.000
Table 5: Additional results of our watermark detection tests across different models and watermarking schemes. We report the rejection rate at a significance level of 5%.
Ked Aed-Gireen
Fixed Sampling
Lache-Augmented
Unwatemmarked
LEaTHANH
SELPHASH
ITSIEX
DIPMARR/SR 5R
T
8,7
6,
5.7
5,7
Model
Test
1.0
0.7
2, 2.225
2,0.5
4.0.25
4,0.5
2, 0.25
2, 3.0
4, 4,0.25
4,0.5
236
2048
0.3
0.5
(52)
0.00
0.00
1.00
1.00
1.00
1.00
1.00
1.000
0.00
0.00
0.00
0.00
0.00
MISTRAL 7R
Fixed (6:)
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
1.00
1.00
0.00
0.00
0.00
Cache (54)
0.02
0.04
0.10
0.50
0.00
0.88
0.80
(52)
0.05
0.01
0.98
0.54
1.00
1.00
1.00
1.00
1.00
0.95
0.05
0.02
0.05
0.05
0.05
1.AMA2
13B
Hixdd (3:3
0.90
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
1.00
1.00
0.90
0.00
0.00
Coche (84)
0.02
0.00
0.06
0.04
0.00
0.10
0.02
0.06
0.04
0.02
0.04
0.00
0.56
0.62
1.00
(52)
0.00
0.00
1.00
1.00
0.97
0.64
1.00
0.94
1.00
1.00
0.00
0.00
0.00
0.00
0.00
L1AMA2
70
Fixed ($3)
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
1.00
1,00
0.00
0.00
0.00
Cache (54)
0.02
0.10
0.02
0.00
0.04
0.00
0.04
0.04
0.06
0.14
0.02
0.08
0.78
0.86
1.00
($2)
0.00
0.000
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
0.00
0.00
0.00
0.00
0.00
LLAMA2
78
Fixod (53)
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
1.00
1.00
0.00
0.00
0.00
Cache 0.04
0.06
1.00
(-2
0.00
0.00
1.00
1.00
0.98
0.82
1.00
1.00
1.00
1.00
0.00
0.00
0.00
0.00
0.00
LLAMA3
Fixed (33)
0.90
0.00
0.00
0.50
0.00
1.00
0.00
0.00
0.00
Coche ($4)
0.36
0.04
0.04
0.06
0.002
0.36
0.06
0.04
0.00
0.04
0.04
0.04
1.00
0.98
1.00
R&G (52)
0.90
0,00
0.00
1.00
1.00
1.00
0.00
0.00
0.00
0.00
0.90
0.90
0.00
YUL.5
98
Fixed (53)
0.00
0.00
0.00
0.00
0.000
0.30
0.00
0.00
0.00
0.10
1.00
1,00
0.30
0.00
0.00
Cache (5-)
0.07
0.06
0.07
0.05
0.03
0.03
0.03
0.03
0.02
0.06
0.06
0.94
1.000
1.00
OWENZ
(82)
0.00
0.00
0.00
1.00
1.00
1.00
1.00
1.00
1.00
0.00
0.00
0.00
0.00
0.00
0.00
7B
Hixd (5:5)
0.10
01000
0.00
0.00
0.00
0.30
0.00
0.00
0.00
0.00
1.00
1.00
0.00
0.10
0.00
Cache 0.04
0.01
0.02
0.04
0.02
0.03
0.05
0.02
0.03
0.97
0.97
1.00
inversely consistently high when the models are not watermarked, further confirming the reliability of our tests. For clarity, the reported rejection rates do not account for multiple testing.
F.2 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, consider the case of Red-Green watermarks with multiple keys, where
20

---

Published as a conference paper at ICLR 2025
Table 6: Additional results of our watermark detection tests across different models and watermarking schemes. We report the rejection rate at a significance level of 1 %..
Red Green
Fixed Sampling
Cache Augmented
Unwatemarked
LEFTHASH
SELFILASH
ITSEXX
DIPMARK/RR AR
T
6.7
6
5-7
4.7 ---
Model
Test
1.0
0.7
2,0.25
2,0.5
4.0.25
4,0.5
2,0.25
2,0.5
4,0.25
4,0.5
256
20:88
0.3
0.5
R-G (52)
0.00
0.00
1,00
1.00
1.00
1,00
0.90
0.90
0.00
MISTRAL 78
Fixed (85)
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
1.00
1,00
0.00
0.00
0.00
Cache (54)
0.00
0.00
0.00
0.00
0.00
0.02
0.00
0.00
0.02
0.00
0.00
0.00
0.48
0.50
0.98
(BG
0.00
0.00
0.77
0.10
1.00
1,00
1.00
1.00
1.00
0.92
0.00
0.00
0.00
0.00
0.00
LLAMA2 13B
Fixed (533
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
1.00
1.00
0.00
0.00
0.00
Coche 0.00
0.00
0.00
0.00
0.12
0.12
0.88
(87)
0.00
0.00
1,00
1,00
0.93
0.29
0.97
0.61
1.00
1.00
0.00
0.00
0.00
0.00
0.00
LLAMA2
70B
0.00
0.00
Cuche (84)
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.44
0.52
0.90
(92)
0.90
1,00
1.00
1.00
0.00
0.00
0.00
LLAMA
7B
Fited (9:3
0.00
0.00
0.00
0.00
0.000
0.00
0.00
0.00
0.00
0.00
1,00
1,00
0.00
0.00
0.00
Cache (54)
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.02
0.00
0.00
0.80
0.76
(52)
0.00
0.00
1,00
1,00
0.98
0.76
1.00
1.00
1,00
1,00
0.00
0.00
0.00
0.00
0.00
LLAMA3
Fixed ($3)
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
1.00
1.00
0.00
0.00
0.00
Cache
0,00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.72
0,90
1.00
(32)
0.00
0.03
1.00
1.00
1.00
1.00
1.00
1.00
1.00
1.00
0.00
0.00
0.00
0.00
0.00
Y11.5
98
Hied
0.00
0.00
0.003
0.10
0.00
Cache (5-)
0.82
0.01
0.01
0.02
0.00
0.01
0.00
0.03
0.00
0.01
0.01
0.00
0.86
1,00
1.00
(82)
0.00
1.00
0.00
QWEN2
7B
Fixed (5:)
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
1.00
1.00
0.00
0.00
0.00
Coche (34)
0.00
0.00
0.00
0.01
0.01
0.92
0.89
Table 7: Red-Green test for no-cache variants of Cache-Augmented schemes explored in our main experiments. We report the p-values for each model and scheme parameter combination. p-values below 0.05 (test passing) are bolded.
LLAMA2-7B
LLAMA3-8B
MISTRAL-7B
DIPMARK/RR
&R
DIPMARK/RR
5R
DIPMARK/>R 5R
a 0.3 a 0.5
0.3
0.5
a 0.3.3 a
0.000
0.000
0.000
0.000
0.000
0.000
0.000
0.000
0.000
the key & is uniformly selected from a predefined pool of keys at each generation. Using n keys turns Eq. (3) into
1e = =x) / 88 (x) + +e' (x),
(16)
with 8 (x) in [k5/(nT] (-n,..,,,}) } is obtained by averaging the variables 8% (x) over the set of keys. Despite modeling changes, the core assumption of logit bias being conditioned on le remains unchanged. Therefore, we can apply the same test in $2 to detect the watermark. Consequently, we conducted the Red-Green test on both the LeftHash and SelfHash variants using keys on three models (LLAMA2- 13B, LLAMA2-700 70B and MISTRAL-7B). Recent work (Pang et al., 2024) 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-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 $2. It emphasizes the test's 's reliance on the foundational principles behind Red-Green schemes rather than on specific implementation details.
F.3 NO-CACUE VARIANTS OF CACIIE-UUGEENTO SCHEMES
The 6-REWEIGHT, REWWIGHHT and DIPMARK schemes introduced in $4 can also be used without cache, suggested in (Hu et al., 2024). Interestingly, in this case these schemes belong to the Red-Green family, and the Red-Green test is applicable to detect their presence. In Table 7, we show that the watermark is indeed reliably detected across three different models. This further highlights
21

---

Published as a conference paper at ICLR 2025
Table 8: Additional results for LLAMA3-8B under the adversarial modification where the watermark is disabled every l queries. We report median p-values across 100 repetitions of the experiment. p- p-values below 0.05 (test passing) are highlighted in bold.
Red Green
Fixed Sampling
Cuche Augmented
Unwateemaked
LartHAxI
SUL-HASHE
ITSEEXP
DIPMIARK/
T=
6,y
"ley
0.
Disable every
0.7
2, 0.25
4,0.5
4.0.25
255
20165
R-4 (32)
1.000
0.999
0.000
0,000
0,000
0,000
1,000
1,000
1.000
1000
1.000
queries
Fixed (3-)
0.938
0.938
0.938
0.938
0.938
0.968
1.2e-55
0.938
0.938
0.938
Cache (H4)
0.608
0.755
0.611
0.657
0.598
0.662
0.745
0,765
0.028
0.058
58e-09
R-G (32)
1.000
1.000
0.000
0.000
0.000
0,000
1.000
1,000
1.000
1.000
1.000
queries
Fised
0.938
0:938
0,938
0:938
2.4e-74
1.1c-04
0.938
0.938
Cache (84)
0:577
0.414
0.600
0.600
0,752
0.639
0.679
0.650
3.0e-04
1.4e044
5.4e-10
(97)
0.000
0.000
0
1,000
1,000
1,000
1.000
queries
Fixed (3:)
0.938
0,938
0,938
0.938
0.938
0.938
8.0c-93
4.0c-06
0.938
0.938
0.938
Cache (34)
0.657
0.617
0.639
0.693
0.561
0.007
7.5e-17
Table 9: Additional results for LLAMA3--8 -BB with the Fixed Fixed-Sampling test under the adversarial modification where the watermark randomly disabled on every token with a fixed probability. p-values below 0.05 (test passing) are highlighted in bold.
Model
Key size
1% disabled 2% disabled 5% disabled
LLAMA3
256
9.5e-59
1.3e-29
7.3e-4
8B
2048
4.3e-4
3.2e-2
0.65
that the test targets universal behavior of the watermarking scheme family and not a specific scheme instantiation.
F.4 SYNTHID- -TXT
After the first version of our work was completed, Google DeepMind has deployed the novel SynthID- Text LLM watermarking scheme on their Gemini Web and App endpoints (Google DeepMind, 2024), and subsequently open sourced the scheme (Dathathri et al., 2024). As this represents the first real-world deployment of an LLM watermarking scheme, we use this as case study to verify the robustness of our tests.
Namely, we notice that despite being significantly different from existing schemes and introducing several novel components such as tournament sampling, which effectively introduces a variable logit bias, the Synthll--Tes scheme can still be seen as belonging to the Red-Green family from the perspective of our tests. This further demonstrates that fundamental ideas behind the schemes are commonly shared, and suggests that tests based on these ideas can often be applied to novel schemes as well. To verify this, in a new experiment, we apply the Red-Green test to the SynthID- Text scheme the GEMMA-7B model, successfully obtaining median p-value of 0.000 across 100 runs. Interestingly, the only difference compared to our previous applications of the test from $2 is that the query-lever hashing proposed by SynthID-TTxxt requires to strictly set H h instead of H > h. Therefore, we suggest using our reliable context size estimation tests (App. B.1) as a preprocessing step enable the application of a Red-Green detection test in this case.
We have attempted to extend this experiment by repeating it on the new GEMINI 1.5 FLASH API endpoints, but we were unable to find evidence of SyethID-Txxt, which is in agreement with the claims made by DeepMind (Google DeepMind, 2024). Applying the test to the supposedly watermarked Web version of the model is challenging due to the need to manually produce the test data which is a tedious process-aae we will investigate ways to apply the test in this case further.
F.5 ADVERSARIAL MODIFICATION DISABLING THE WATERMARK
In this section, we provide additional results on LLAMA3-88 8B under two adversarial modifications to the watermarking scheme. The first adversarial modification consists of disabling the watermarking scheme every & E N queries. This modification can be applied to all three watermarking families. The second adversarial modification is specific to Fixed-Sampling schemes and consists of randomly
22

---

Published as a conference paper at ICLR 2025
10a
AAR detector
Fixe Samplingnng
10
h
h
10
10
10-12-
14
10 16
10-1
109
10-1
10
Ath
A/h
Figure 6: Left: Median p-values of the original watermark detector (computed with the private key {). Right: p-values of the Sampling test with 50 tokens generated per query and 1000 queries.
disabling the watermark given token with fixed probability for all tokens within query. This breaks the determinism of the watermarking scheme, leading to more diverse outputs under the watermark.
We show that the tests remain relatively effective in these settings. This highlights that the tests designed to target the fundamental mechanisms of the watermarking scheme families, and not the specific implementation details. While this shows that hiding the watermark with such modifications is effective, acknowledge that more sophisticated adversarial settings could reduce the effectiveness of the tests or break them entirely.
Disabling the watermark on the query level In Table 8, show the results of all tests under the adversarial modification where the watermark disabled every 2, 3, and queries. We see that despite the "dilution" of the watermark, the tests still work and have similar results in $5. This highlights that the tests are not specific to one watermark implementation but based on fundamental mechanisms underlying each test family.
Disabling the watermark on the token level In Table 9, we show the results of the Fixed-Sane Fixel-Sampling test under the adversarial modification of disabling the watermarking scheme randomly at every token. see that the adversarial change indeed reduces the test power, but for reasonable percentage of tokens disabled, the tests still remain effective. Moreover, as detailed in App. E, increasing the number queries can mitigate the effect this change.
F.6 PRACTICAL UNDETECTARILITE ENTROPY-CONDITTONEE AAR
As introduced in $7, prior work proposed a watermark with theoretical guarantees of undetectability (Christ al., 2024). While promising, this scheme still lacks experimental validation and current evaluations suggest it may be difficult to make it practical, mainly due to slow generation speeds (Fairoze et al., 2023). This complicates the task of evaluating our tests on this exact scheme.
Towards practical undetectability Inspired by the insight in Christ et al. (2024) that conditioning the watermark on entropy improves stealth, we propose new proof-of-concept hybrid scheme variant designed to explore the potential trade-off between the stealth and strength of watermarks.
Recall that Christ al. (2024) generates tokens without a watermark until the generated sequence exceeds entropy threshold; then, this high-entropy context is used to seed the scheme. Conditioning on the context's entropy ensures that the watermark undetectable. Indeed, both our Red-Green and Fixed- Tixed-Sampling tests rely low-entropy generation to successfully detect the presence of watermark. Therefore, to improve the tested scheme's 's undetectability, Sed-Green schemes can be disabled if the h previous tokens are below entropy threshold. For Fixed-Saa Sampling schemes, similar principle can be applied where the key is used only if the previous tokens exhibit sufficiently high entropy.
23

---

Published as a conference paper at ICLR 2025
Algorithm 6 Entropy-Conditioned AAR Watermarking
Require: Prompt P. model M, private key ç, hyperparameter X, and hash function Hash
1: x 6- []
Empty completion
2: for each token i to generate do
3: {piheE f M + + E' - ---1e -(==) lpg(p;)
4:
5:
if and 2 h then
6:
for each token i E E do
7:
ri - 1/
8:
9:
end for
10:
xi arg maxiet
11:
else
12:
2. (p))ee
13:
end
14: 2- [x]]]
15:
end for
return
Entropy-conditionn AAR this preliminary investigation, we modify the AAR watermark proposed in Aaronson (2023). In the original scheme, the h previous tokens are hashed using private key g to obtain a score r; uniformly distributed in [0. 1] for each token in the vocabulary E. Given pt, the original model probability for token i, the next token is then deterministically chosen as the token i* that maximizes r; Hence, the AAR watermark can be seen as belonging to both Red-Green family and the Fixed-Sampling family. To make the scheme less detectable, we introduce a hyperparameter A. Given Pi-h. P:-1. the probabilities the previous tokens, the watermark is applied if and only if -i=i-n - log(P:) > A. We detail this new scheme in Algorithm 6.
In Fig. 6, show, for different contexts and values of (adjusted by h), the results of both the original watermark detector (computed using {) on the left and the results of our Fixed-Sampling test (same settings as for Table 1) on the right. To generate the samples for the original watermark detector, following the method in (Kirchenbauer et al., 2023), we generate 100 completions of 200 tokens, using prompts sampled from C4. We observe that increasing À reduces the strength of the watermark (left side) but also decreases the strength of our detection test at an even faster rate (right side). This suggests that using watermarking conditioned on entropy a valid approach make the watermark less detectable, albeit at the cost of the watermark's 's strength. As noted in $7, finding a satisfactory tradeoff, i.e., designing practical scheme that hard to detect while maintaining strength and other key properties, remains an open question. A suitable evaluation would have evaluate FPR at low TPR, dependence on text length, as well as robustness to scrubbing. Although we believe that there an inherent trade-off between these properties, leave this more thorough evaluation for future work and hope that our tests can serve as a baseline to estimate empirical detectability.
G DETAILED COST ANALYSIS OF THE TESTS
Table 10: The costs of our watermark detection tests with the test settings used in Table 1. We assume 75 tokens per prompt in both Red-Green and Cache- Beche-Augmented tests, and 15 tokens output. Q. Q1, Q2. NN are parameters of the tests introduced in $2- $4. The costs are estimated using current GPT40 pricing (November 2024).
Test
Number of queries
Instantiation
Input tokens
Output tokens
Cost
Red-Green
Q Q2 x
Q1 9, Q2 9, 100
648000
162000
2.435
Fixed-Sampling
Q
1000
10000
50000
0.285
CagmenAugeetted
Qi +2
Q 75, Q2 = 75
10000
15000
0.10S
We derive the cost of each of our tests introduced in $2-$4 in Table 10.
24


Reviews:
[{"review_id": "iPD812JhCw", "reviewer": "Reviewer_gicP", "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.\nThey also demonstrate that their attack is capable of estimating the parameters used in the watermarking schemes.", "questions": "In Appendix C, you discuss a method for estimating scheme parameters. Are your techniques capable of learning the watermarking key itself?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "A huge number of watermarking papers have come out recently.\nMany 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.\nTherefore, 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.\n\nThis work shows that existing schemes typically fall short in this respect, demonstrating an important weakness.", "weaknesses": "It is not surprising that they were able to easily detect the schemes they attacked. Those schemes are not designed to be undetectable.\nIn 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.\"\n\nHowever, I believe these claims require justification because:\n- \"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.\n- 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.\n- 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.\n\nHere 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.\n\nIt 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.\n- 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.\n- 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).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "KtuOigIuO7", "reviewer": "Reviewer_Ay59", "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.", "questions": "1.\tCan you discuss more application scenarios of watermark detection? This question has a great impact on the contribution of the paper.\n\n2.\tCan you discuss potential commonalities between their detection techniques for different watermarking families? The universality of watermark detection technology is beneficial to reducing detection costs.\n\n3.\tCan the authors discuss more about why current detection methods are unable to determine the watermarking method of real-world production-level LLMs?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 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.\n2. The method is well written and the method makes sense and is easily understood. Each method has a clear section structure. \n3. The experimental results in the black-box scenario verify the effectiveness of the method.", "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.\n\n2. 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.\n\n3. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "brnqzy9Q6C", "reviewer": "Reviewer_PSUp", "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.", "questions": "1. The key algorithm for calculating the p-value in lines[197-240] is too vague. Could you please clarify it?\n\n2. 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.\n\n3. Could you provide a detailed algorithm for estimating the context size as described in lines[781-791], along with the corresponding experimental results?", "limitations": "", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 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.", "weaknesses": "- This paper lacks a clear mathematical presentation of its algorithms, and the descriptions are often vague.\n\n- The detection tasks for Fixed-Sampling and Cache-Augmented watermarks are trivial, and the proposed simple algorithm can be easily defended against.\n  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].\n  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.\n  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].\n\n\n- 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.\n\nThe median p-value is not a good metric, as it does not reflect the actual false positive rate. It is also difficult to interpret.\n\n- 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.\n\n[1] Christ, Miranda, Sam Gunn, and Or Zamir. \"Undetectable watermarks for language models.\" The Thirty Seventh Annual Conference on Learning Theory. PMLR, 2024.\n\n[2] Hu, Zhengmian, et al. \"Unbiased watermark for large language models.\" arXiv preprint arXiv:2310.10669 (2023).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "vooGb1wZqj", "reviewer": "Reviewer_xkZg", "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.", "questions": "My questions are outlined in the weaknesses mentioned earlier. Please address those and the following:\n\n- 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?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "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.", "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?\n\n- 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.\n\n- 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?\n\n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)