Segmenting Watermarked Texts From Language Models
Authors: Xingchi Li
Guanxun Li
Xianyang Zhang
Venue: NeurIPS 2024 poster (2024)
Keywords: Large language models
Randomization test
Segmentation
Watermark
Primary area: natural_language_processing
TL;DR: We develop statistical methods for detecting and identifying watermarked sub-strings generated from language models.

Abstract: Watermarking is a technique that involves embedding nearly unnoticeable statistical signals within generated content to help trace its source. This work focuses on a scenario where an untrusted third-party user sends prompts to a trusted language model (LLM) provider, who then generates a text from their LLM with a watermark. This setup makes it possible for a detector to later identify the source of the text if the user publishes it. The user can modify the generated text by substitutions, insertions, or deletions. Our objective is to develop a statistical method to detect if a published text is LLM-generated from the perspective of a detector. We further propose a methodology to segment the published text into watermarked and non-watermarked sub-strings. The proposed approach is built upon randomization tests and change point detection techniques. We demonstrate that our method ensures Type I and Type II error control and can accurately identify watermarked sub-strings by finding the corresponding change point locations. To validate our technique, we apply it to texts generated by several language models with prompts extracted from Google's C4 dataset and obtain encouraging numerical results. We release all code publicly at https://github.com/doccstat/llm-watermark-cpd.

Segmenting
Watermarked Texts From Language Models
Xingchi Li' Department of Statistics Texas A&M University College Station, TX 77843 anthony. li@stat.. tamu.edu edu
Guanxun Li" Department of Statistics
Beijing Normal University Zhuhai Zhuhai, Guangdong 519087 guanxun edu. cn
Xianyang Zhang'
Department of Statistics
Texas A&M University
College Station, TX 77843
zhangxianyBstat. tamettttmmu tamu. edu
Abstract
Watermarking is technique that involves embedding nearly unnoticeable statistical signals within generated content help trace its source. This work focuses scenario where an untrusted third-party user sends prompts to a trusted language model (LLM) provider, who then generates text from their L.MM with watermark. This setup makes it possible for a detector to later identify the source of the text if the user publishes it. The user can modify the generated text by substitutions, insertions, or deletions. Our objective is to develop statistical method to detect if a published text LLM-generated from the perspective of detector. We further propose a methodology to segment the published text into watermarked and non- watermarked sub- sub-strings. The proposed approach is built upon randomization tests and change point detection techniques. We demonstrate that our method ensures Type and Type error control and can accurately identify watermarked sub-strings by finding the corresponding change point locations. To validate our technique, we apply to texts generated by several language models with prompts extracted from Google's C4 dataset and obtain encouraging numerical results !
Introduction
With the increasing use of large language models in recent years, it has become essential to differenti- between text generated by these models and text written by humans. Some of the most advanced LLMs, such as GPT-4, Llama 3, and Gemini, are very good at producing human-like texts, which could be challenging to distinguish from human- gennrrttd texts, even for humans. However, is crucial to distinguish between human- producdd texts and machine-pre produucd texts to prevent the spread of misleading information, improper use of LLM-based tools education, model extraction attacks through distillation, and the contamination of training datasets for future language models.
Watermarking principled method for embedding nearly unnoticeable statistical signals into text generated by LLMs, enabling provable detection of L.MM-generated content from its human-written
"Equal contribution
I Correspnn author
Wee release all code publicly http://///gtttoooooo///////////s
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

counterpart. This work focuses on scenario where an untrusted third-party user sends prompts to a trusted large language model (LLM) provider, who then generates a text from their LLM with a watermark. This makes it possible for a detector to later identify the source of the text if the user publishes it. The user is allowed to modify the generated text by making substitutions, insertions, or deletions before publishing it. We aim to develop statistical method to detect if a published text is LLM-generated from the perspective of a detector. When the text is declared to be watermarked, we study a problem that has been relatively less investigated in the literature: to separate the published text into watermarked and not-matermarked sub-strings. In particular, we divide the texts into a sequence of moving sub-strings with a pre rreermeeeeneed length and sequentially test if each sub-string is watermarked based on the p-values obtained from a randomization test. Given the p-value sequence, examine if there are structural breaks in the underlying distributions. For non non-watermarked sub-strings, the y-values are expected to be uniformly distributed over [0, 1]. while for watermarked sub-strings, the corresponding p- p-values more likely to concentrate around zero. By identifying the change points in the distributions of the p-values, we can segment the texts into watermarked and non-watermarked sub-strings.
In theory, we demonstrate that our method ensures Type and Type II error control and can accurately identify watermarked sub-strings by finding the corresponding change point locations. Specifically, we obtain the convergence rate for the estimated change point locations. To validate our technique, we apply it to texts generated by different language models with prompts extracted from the real news-like data set from Google's 's C4 dataset, followed by different modificatiions/attacss that can introduce change points in the text.
1.1 Related works and contributions
Digital watermarking is a field that focuses on embedding a signal in medium, such as an image
or text, and detecting it using an algorithm. Early watermarking schemes for natural language processing-generann text were presented by [Atallah et al. (2001]. Hopper et al. [2007] formally
defined watermarking and its desired properties, but their definitions were not specifically tailored to
LLMs. More recently, Abdelnabi and Fritz (202T) Munyer and Zhong (0033 proposed schemes that use machine learning models in the watermarking algorithm. These schemes take a passage of text and use model to produce a semantically similar altered passage. However, there is no formal guarantee for generating watermarked text with desirable properties when using machine learning.
The current work is more related to Aaronson 2023]. Kirchenbauer et al. 2023a]] Kuditipudi al.] [2023]. In particular, Kirchhnbaeer al. [2023]] introduced a gred-greennnn list" watermarking
technique that splits the vocabulary into two lists based on hash values of previous tokens. This technique slightly increases the probability of embedding the watermark into "green" tokens. Other papers that discuss this type of watermarking include Kirchenbauer et al. (2023b), Cai et al. [0024), Liu and Bu [2024), and Zhao et al.] [002).. However, this watermarking technique is biased, as the next token prediction (NTP) distributions have been modified, leading to a performance degradation of the LLM. Aaronson [2023] describes a technique for watermarking LLMs using exponential minimum sampling to sample tokens from LLM, where the inputs to the sampling mechanism are also a hash of the previous tokens. This approach is closely related to the so-called Gumbel trick in machine learning. Kuditipudi et al. [2033 proposed inverse transform watermarking method that
can be made robust against potential random edits. Other unbiased watermarks in this fast- tast-ggooing
line of research include Zhao et al. 2024 Fernandez et al. 22033] Hu et al. (2033 Wu et al. 2023
However, less attention has been paid to understanding the statistical properties of watermark generation and detection schemes. The paper by |Huang et al. [2023) considers watermark detection as a problem of composite dependence testing. The authors aim to understand the minimax Type II error and the most powerful test that achieves it. However, Huang al. (2023) assumes that the NTP distributions remain unchanged from predicting the first token to the last token, which can be unrealistic. On the other hand, Li et al. [2024] introduced flexible framework for determining the statistical efficiency of watermarks and designing powerful detection rules. This framework reduces the problem of determining the optimal detection rule to solving minimax optimization program.
Compared to the existing literature, we make two contributions: (a) We rigorously study the Type I and Type II errors of the randomization test to test the existence of a watermark; see Theorems [ We apply these results to the recently proposed inverse transform watermark and Gumbel watermark schemes; see Corollary

---

(b) We develop a systematic statistical method to segment texts into watermarked and non- watermarked sub-strings. We have also investigated the theoretical and finite sample performance of this methodology. As far as we know, this problem has not been studied in recent literature on generating and detecting watermarked texts from L.Mss.
2 Problem setup
2.1 Watermarked text generation
Denote by the vocabulary (a discrete set), and let be an autoregressive LLM which maps a string y- no:t-1 y Mo-oo--not1" "/t11 E yC+no to distribution over the vocabulary, with p(-ly-nop [/--ttt-1) being the distribution of the next token 1/, Here y-no:0 denotes the prompt provided by the user. Set V = [V] be the vocabulary size, and let f1tt Eιε2... - É be watermark key sequence with & E = for each i, where E is a general space. Given prompt sent from a third-party user, the LLM provider calls generator to autoregressitvely generate text from an LLM using a decoder function I', which maps & and a distribution pt over the next token to a value V. The watermarking scheme should preserve the original text distribution, i.e., (E. pt) y) pe(y). A watermark text generation algorithm recursively generates a string 1/.. by
y [[ ((11-m--))))))))
1 1 S n,
where n is the number of tokens in the text Vi.. generated by the LLM, and & are assumed to be independently generated from some distribution over E. In other words, given p(-ly-nga-11) ys is completely determined by & and y-ng:i-1-
For ease of presentation, we associate each token in the vocabulary with unique index from [V] = (1. V), and we remark that the generator should be invariant to this assignment.
Example 1 (Inverse transform sampling). In this example, we describe watermarked text generation method developed in Kuditipudi et al. (2023) and discuss an alternative formulation of their approach. Write ps (k)) = p(kly (nggi-nng))) for
< V and 1 S / n. To generate the ith token, we consider a permutation m, on [V] and uy ~ Unif 1] (which denotes the uniform distribution over [0, 1)).
which jointly act as the key &s. Let
[' uz). p4) क. (min (7:(() : 4: mi) S (()) 2 4z}).
We note that [( ut). m1) = k min (I,(1): : p4( : x,()) S x,())) 2 u,} = n. (k). which implies that
p, : (.) & (,))) 2 u, > (i) < (T)).
As the length of this interval is (k),, P(T(( (TT,,,;))) u.) k) = pa (k).. An alternate way to describe the same generator is as follows: Given a partition of the interval [0. 1] into V sub-intervals denoted by II.....Iy .vv we can order them in such a way that each interval Z, is adjacent its immediate right neighbor I,+1. Now let I(k; i)'s be V intervals with the length [[kk; i)l = p(kly-noot- for 1 S k 5 V. Given the permutation TT. we can order the V intervals through n,, i.c., {Im, (k;;
k 1,2, ..., V). Define & 1su E Iz.(k) (k; and set y/4 = k if &u 1. Clearly P(y
k) P(E. 1) P(4 (k) i)) p(k(yy-mot-1).
Now, for a string Fi. (with the same length as the key) that possibly watermarked, Kuditipudi et al. 2023 suggest the following metric to quantify the dependence between the watermark key and the string:
M(Elm: TI.) =
Σ [14 1/2) 1=1
- T V-1 2
1
(I)
Observe that if T4 is generated using the above scheme with the key 4 = (TT uz), then u, and F (7 positively correlated. Thus, a large value of M indicates that Vi.. is potentially watermarked.
Example 2 (Exponential minimum sampling). We describe another watermarking technique proposed in Aaronson 2003). To generate each token of text, we first sample Eik Unif(O, 1] independently
for I v k V. Let
log(Eax)
arg min -lo((Eik) ISkSV p(kly-nos--1)
Vi arg max
arg min Fack ISkSV
ISKSV p(kly--ott-i)
3

---

where Es := - pog((G)//p(AA
~
with Exp(a) denoting an expo-
nential random variable with the rate a. For two exponential random variables X Exp(a) and Y ~ Exp(b), we have two basic properties: (i) min(X, Y) ~ Exp(a + b); (ii) P(X < Y) =
B[1 exp(-aV) a/(a + b). Using (i) and (ii), is straightforward to verify that
P(y: k) - -0 ( (EAx Ea < min Eij =p(kly =p(k(y-mox-i)) mon--1).
5#k
Hence, this generation scheme preserves the original text distribution.
Aaronson 2023 proposed to measure the dependence between a string Vu.n and the key sequence Eim using the metric
a Σ (log(E..g)) 1}.
M(E Fi:.)
(2)
The idea behind the definition of this function that if y, was generated using the key E., then E..y. tends to have higher value than the other components of &.. Therefore, larger value of the metric indicates that the string Vi:n is more likely to be watermarked.
2.2 Watermarked text detection
We now consider the detection problem, which involves determining whether given text is water- marked or not. Consider the case where string 91.m is published by the third-party user and key sequence fim is provided to detector. The detector calls a detection method to test
Ho Fi
watermarked
versus
H F1.m is watermarked,
by computing a value with respect to test statistic @(E Vimm). It is important to note that the text published by the user can be quite different from the text initially generated by the LLM using the key Sia., which we refer to as Vi.n. To account for this difference, we can use transformation function E that takes V1.n the input and produces the published text /i.m as the output, i.e., 31.m (V1.n)) This transformation can involve substitutions, insertions, deletions, paraphrases, or other edits to the input text.
The test statistic é measures the dependence between the text Vi.m and the key sequence Ein- Throughout our discussions, we will assume that large value of & provides evidence against the null hypothesis (e.g., stronger dependence between f1.m and fI:m). To obtain the p-value, we consider a randomization test. In particular, we generate 5/ independently over 1 < S n and 1 1 t and c s are independent with F1.m Then the randomization-basee p- is given by
T
1
Σ
1 (8(Eism, Trm) (ossiin0Dmm))))
pr
T+1
Theorem 1. For the randomization test, we have the following results.
(i) Under the null, P(pr a) L(T 1)aa/((TT + 1) S a, where [a] denotes the greatest integer that less than or equal to a;
(ii) Suppose the following three conditions hold:
(a) max (ar((d(E (m Fm.m }Fm),
(im) S Co/n with C, O:
(b) B[o(E1.. Viem [m]] = (nn-1/2):
(c) lim Vo vm.m) Fm] 00.
Here Fm - [y-nn:0, Ti:m] and Ei.n is key sequence generated in the same way as E but is independent of F1.m. Given any > when T 2/e
P(pr S a(Fm) 2 - C1 exp(-2Tee) o(1),
(3)
+ +oo, where C > 0.
We now apply the results in Theorem Examples with m n and obEinn Tinn)
M(E Vin) for M defined in 1 and

---

Corollary 1. fi. = Vi.m and
11 plyilyynosie (ooll=y-)-))) 20,
(4)
1=1
then Conditions (a)-(c) in Theorem 7 are satisfied for Examples randomization test converges to 1 in these examples T
Consequently, the power of the
However, as the published text can be modified, it is not expected that every token in 9i:m will be related to the key sequence. Instead, expect certain sub-strings of V1.m to be correlated with the key sequence under the alternative hypothesis Ha. To measure the dependence, we use a scanning method that looks at every segment'sub-string of Vi:m and segment of Çi: with the same length B. We use a measure M[Eaa+B-- Ub.b+B-Bb B-1) to quantify the dependence between Cax++B and Ub.b+B-2 B-1, chosen based the watermarked text generation method described above. Given M and the block size B, we can define the maximum test statistic as
Φ(51:n: V1:m)
max Isa B+1 1sb5m- B+1
M(Sa:a+B-D Bb.++B-1).
(5)
Theorem Consider the maximum statistic defined in 5 where the dependence measure takes the form of M(Sasa+B- B- B-1, B-+++B-1) = B-1 EE=D hg (Ea++i 0b45) and h;s are independent conditional max; [ha] $ 1/4. In this case, suppose
on [i V- Under the setting of Example I
CN,B max E[M((aa++BBB Dh.b+ Wi V/ V- +00,
where N- max(n, m and CN.B v (lg(N)/BB Then, holds true. Under the setting of Example [ h,s are exponentially distributed conditional on fl.m J-ngm]. In this case, (3) still true under (6) with CN,B= = log(N)/B.
3 Sub-string identification
In this section, we aim to address the following question, which seems less explored in the existing literature: given that the global null hypothesis Ho is rejected, how identify the sub-strings from the modified text Viom that are machine-generated?
To describe the setup, we suppose the text published by the third- sirrt-party user has the following structure:
V1 Vr 11 Vrz Wr++1 Vra Ira+1 Vra
non-wattrmarked watermarked
non-watermarked
watermarked
in which case the string I 1...-....00000 Dr. and Try+1 "Tr, watermarked. We emphasize that the orders of the watermarked and non-watermarked sub-strings can be arbitrary and do not affect method described below. The goal here is separate the text into watermarked and non- watermarked sub-strings accurately. Our key insight to tackling this problem is translating it into a change point detection problem.
describe our method, we define a sequence of moving windows I- = ii B/2) v 1, (i + B/2) A m] with B being the window size which is assumed to be an even number (for the ease of presentation) and 1 S m. For each sub-string, we define randomization-basel p-value given by
T
pt = T+1
1+
Σ
1 (ôl(ion Tz.) S MeL (1 1 m,
(8)
where we let 6(E1n Vz.)) maxiçken M(EJ. .z.) with Ts [[k ( B/2) V 1. (k An).
We have now transformed the text into a sequence of p-values: p1,... Pm- Under the null, the p-values are roughly uniformly distributed, while under the alternatives, the p-values will concentrate around zero. Consider a simple setup where the published text can be divided into two halves, with the first half watermarked and the second half wotermarrdd (or vice versa). Then, we can identify the change point location through
T(m - 7) F1. (1) Fr+1m(()))
f arg max (1m((T) (1m(() 1m
sup tE|0.1]
3/2
5

---

where (t) denotes the empirical cumulative distribution function (cdf) of {p:}i=a-
We shall use the block bootstrap- paasstra-bbased approach determine if f is statistically significant. Note that conditional on Fu. the p-value sequence is R-dependent in the sense that p: and Pj are independent only if j| B. Hence, the usual bootstrap or permutation methods for independent data may work as they fail to capture the dependence from neighboring p-values. Instead, we can employ the so-called moving block bootstrap for time series data Kunsch 1989 Liu et 1992]. Given a block size, say B", we create m B3 + blocks given by {Pi..... Pi+ B for randomly sample m
m - B' + 1. We m/ B' (assuming that m B' is an integer for simplicity) blocks with replacement and paste them together. Denote the resulting resampled p- paluue by pi.....PP. We then compute Fi, (t) based on the bootstrapped p- p-values and define
7 - (t) F F7+1m( (t)l.
Si:m (T) = sup telo,1]
3/2
Repeat this procedure T" times and denote the statistics by (T (T) for 1,2,..., ... Define the corresponding bootstrap- basdd p-value as
T'
pT
1+
Σ t=1
1
max
Stmm (T) < max ST.M (1)
(10)
+
1ST<m
157cm
We claim that there is a statistically significant change point pr. S a. Remark 1. Alteraatvely, one can consider the Cramér-von Mises type statistic max, Clam (T) with
Crem (T) = 72 (m +) (1) - (t)
m3
examine the existence change point, where w(.) ) a non-negative weight function defined over [0, 1]. If a change point exists, we can estimate its location through 7 = arg gax C1.m(T) Other methods to quantify the distributional shift for change point detection include the distance and kernel-based woo-sample metrics [Matteson and James 2014 Chakraborty and Zhang 2021 and
graph-based test statistics [Chen and Zhang 2015).
Consider the case where there is single change point located at r". Without loss of generality, let us assume that before the change, the p-values are uniformly distributed, i.c., PI..... Pr ~ Fo with (t) = (the edf of Unif(0, 1)), while after the change, the p-values follow different distributions that concentrate around zero. We assume that lim inf m- D(Fy, B.Fr, (t)) > where DFo,, F (t)]) supse[o.1] Fo(() E[F,,+1mm(t)] is the Nolmogorov-Smimoo distance. In other words, the empirical edf of the p-values from the watermarked sub-strings converges to a distribution that is different from the uniform distribution. This mild assumption allows for the detection of the structure break. As discussed before, we consider the scan statistic maxigr<m 1im (T) with S1.m (r) defined in (9) for examining the existence change point. Proposition Assuming that B +00 and B/m 0, we have
max S1m (5) Vmn"(L D E(F, fimm (t)) op(1 +00, Is
where limm T" r'/m= E (0, 1).
Next, we shall establish the consistency of the change point estimator = arg max g S1mn (T). In particular, we obtain the following result, which establishes the convergence rate of the change point estimate.
Theorem 3. Under the Assumptions Proposition 7 we have
mB log(m/ B)
|--7"= D D E. Fr. +1mm(()
Our scenario differs from the traditional nonparametric change point detection problem in few ways: (i) Rather than testing the homogeneity of the original data sequence (which the setup typically considered in the change point literature), we convert the string into sequence of
Remark 2.

---

p-values, based on which we conduct the thange-poing analysis; (ii) In the classical change point literature, the observations (in our case, the p-values) within the same segment are assumed to follow the same distribution. In contrast, for the watermark detection problem, the p-values from the watermarked segment could follow different distributions, adding a layer of difficulty to the analysis; (iii) The p-value sequence is dependent (where the strength of dependence is controlled by B), making our setup very different from the one in Carlsteein [1888. which assumed the underlying data sequence to be independent; (iv) The technical tool used in our analysis must account for the particular dependence structure within the p-value sequence.
3.1 Binary segmentation
In this section, we describe an algorithm to separate watermarked and non-watermarked sub-strings by identifying multiple change point locations. There are two main types of algorithms for identifying multiple change points in the literature: (i) exact or approximate optimization by minimizing penalized cost function (Harchaoui and Lévy-Leduc (2010] Truong et al., 2020 R. Killick and
Eckley 2012 Li and Zhang [2024] ZZhang and Dawn 2023 and (i) approximate segmentation
algorithms. Our proposed algorithm is based on the popular binary segmentation method, a top-down approximate segmentation approach for finding multiple change point locations. Initially proposed by Vostrikoval [198T], binary segmentation identifies a single change point in dataset using a CUSUM-like procedure and then employs divide-and-conquer approach to find additional change points within sub-segments until stopping condition reached. However, as a greedy algorithm, binary segmentation can be less effective with multiple change points. Wild binary segmentation (WBS) [Fryzlewicz] 2014] and seeded binary segmentation (SeedBS) (Kovács et al. [0222 improve upon this by defining multiple segments to identify and aggregate potential change points. SeedBS additionally addresses the issue of overly long sub-segments WBS that may contain several change points. SeedBS uses multiple layers of intervals, each with fixed number of intervals of varying lengths and shifts, to enhance the search for change points. When comparing multiple candidates for the next change point, the narrowest-over -hree--h (NOT) method [Baranowski et al. [2019] prioritizes narrower sub-segments. Built upon these ideas, we develop an effective algorithm to identify the change points that separate watermarked and non-watermarked sub-strings. The details are described Algorithm below.
Algorithm 1 SeedBS- for change point detection in potentially partially watermarked texts
Require: Sequence of p-values {p: decay parameter a E [1/2, 1) for SeedBS, threshold Ç for NOT.
Ensure:
Locations of the change points.
Define / = (0, m]. for < 2..... [logı/a m] do
>> Start of SeedBS
Number of intervals in the k-th layer: n (1/aa) 11
Length of intervals in the k-th layer: 4 = ma 4-1
Shift of intervals in the k-th layer: Sy- (m 14)/(nk - 1).
k-th layer intervals: In = U {(1(2 - 1) (2 1)5x + 4...
end for
Define all seeded intervals = U for i + 1,..., [ do
Doggya m]
Ig.
D End of SeedBS
D Start of NOT
Define the i-th interval I, = (ri, (r-r))(s--))
Define S,,+1:, (T) == supre|o.1]
Fr (t) (t)):.()).
(s.-1.)9/2
Let Ω. = arg max,, <r< Sr, 11s, (T).
Obtain P. through block bootstrap 10
end for
Define the set of potential change point locations O {i ps () and the final set of change point locations = 0. while O + do
Select i = arg min; I.....0) {44} arg min;: {si rr.).
S S (+.)
O - (j < |0| f. $ 1,).
end while return S.
>> End of NOT
7

---

EMS ENSL
EMSL
Settig
Change holk Courk
0.50
0.001
0.005
0.01
0.05
100
500
Threshold
Figure I: Left panel: boxplots of the number of false detections with respect to different thresholds Ç. Right panel: sequences p-values from different methods in Setting for Prompt with threshold = 0.005. The detected change point locations marked with dashed lines at the index 157 for ITS and 158 for ITSL, respectively.
4 Numerical experiments
We conduct extensive real-data-based experiments following similar empirical setting in Kirchen- bauer et al. [2023a], where we generate watermarked text based on the prompts sampled from the news-like subset of the colossal clean crawled corpus (C4) dataset [Raffel al. 2020 We uti-
lized three LLMs, namely openai communi ty/ ggtt [Radford et al. [2019], facebook opt- 11.30
(Zhang et al. [022] and Meta-Llama -ma-3 3- (AI@ Meta (2224), to evaluate the effectiveness of the
proposed method. We consider the following four watermark generation and detection methods:
ITS: The inverse transform sampling method with the dependence measure defined in
ITSL: The inverse transform sampling method with the dependence measure defined in B.2). which is based on the Levenshtein cost (B.I) with base alignment cost (B.3).
EMS: The exponential minimum sampling method with the dependence measure defined in
EMSL: The exponential minimum sampling method with the dependence measure defined in B.3), which is based the Levenshtein cost (B.I) with base alignment cost (B.4).
The details of the Levenshtein cost are deferred to Appendix B. For each of the experiment settings, 100 prompts were used to generate the watermarked text. We the length of text m 300, the size of sliding window B 20, and the block size used in the block bootstrap- test 3' = 20. Results for other choices of B are shown in Appendix C In Algorithm [ and the minimum length of the intervals generated by SeedBS be 50 such that the block bootstrap- (0.05, 0.01, 0.005, 0.001 We present the results for openai - communi commmmmity// tttttt///e gpt2 in the main text and defer the results for facebook/opt 1.3--..3.. 3b and
we set the decay parameter
v2
based test is meaningful, and the threshold ttgttt2ttt//t222/ Meta- -ataa-Lama-222 8-8B to Appendix B.3 and Appendix B.4 respectively.
4.1 False positive analysis
We begin by analyzing the false discoveries of the change point detection method. We will generate watermarked text with a length of m 500, where no change points exist.
Setting (no change point): Generate 500 tokens with watermark.
The results for cttaiicooomunttyy/nneeee are showed in Figure [ The left panel illustrates that the two exponential minimum sampling methods result in fewer false discoveries compared to the two inverse transform sampling methods. Indeed, the existence of false discoveries highly depends on the quality of the obtained sequence of p-values. In the right panel, we fixed one prompt and plotted sequence of p-values for the four methods. Most of the p-values are near However, certain sub-strings have relatively high valuus for the two inverse transform methods, indicating that these methods failed to detect the watermark in these segments, resulting in false discoveries for change point detection.

---

15
Setting
Settin
Setting 2,155
Serting EM55
Setting 3. 1TS
Setting
Switing EMS
Serting 4. EMSL.
Serting 11.1
0.001
0.035
0.55
Figure 2: The boxplots of the Rand index comparing the clusters identified through the detected change points with the true clusters separated by the true change points with respect to different thresholds Ç.
4.2
Change point analysis
When users modify the text generated by LLM, there may be some sub-strings with watermarks and others without. Our goal is to accurately separate the text into watermarked and non-watermarked sub-strings. this section, we will focus on two types of attacks: insertion and substitution. To demonstrate, we will consider the following three settings:
Setting 2 (insertion attack): Generate 250 tokens with watermarks, then append with 250 tokens without watermarks. In this setting, there is single change point at the index 251.
Setting 3 (substitution attack): Generate 500 tokens with watermarks, then substitute the token with indices ranging from 201 to 300 with non-watermarked text of length 100. In this setting, there are two change points at the indices 201 and 301, respectively.
Setting (insertion and substitution attacks): Generate 400 tokens with watermarks, substi- tute the token with indices ranging from 101 to 200 with con-watermarked text of length 100, and then insert 100 tokens without watermarks at the index 300. In this setting, there are four change points located at the indices 101, 201, 301, and 401, respectively.
For more complex simulation settings, please refer to Appendix B.5
We compare the clusters identified through the detected change points with the true clusters separated A higher Rand index indicates better
by the true change points using the Rand index [Rand] 1971 performance of different methods.
Figure 2 shows the Rand index for four methods in Settings 2-4 corresponding different thresholds Ç. For each method, their performance in Settings 2-3 is better than that of Setting when the threshold 0.01. This is because Setting 4 includes two types of attacks, making the problem more difficult than in Settings 2 and 3. In all cases, the two exponential minimum sampling methods outperform the inverse transform sampling methods, and EMS delivers the highest Rand index value. We want to emphasize again that the performance of the change point detection method highly depends the quality of the obtained sequence of p-values. Figure 3 shows the p-value sequence for all methods given one fixed prompt in Setting 4. The change points detected by the EMS and EMSL methods are closer the change points compared those detected by the ITS and ITSL methods. Additionally, the sequence of p-values for all methods in Settings 1-4 with the first 10 prompts extracted Google C4 dataset are shown in Figure B.1 in the Appendix.
Discussions
In this study, we have introduced method for detecting whether a text is generated using LLM through randomization tests. We have demonstrated that our method effectively controls Type I and Type II errors under appropriate assumptions. Additionally, we have developed technique to partition the published text into watermarked and non-watermarked sub-strings by treating as change point detection problem. Our proposed method accurately identifies watermarked sub-strings by determining the locations of change points. Simulation results using real data indicate that the EMS method outperforms the other methods.

---

ISL
Token Index
Figure Sequences of p-values for all methods given one fixed prompt in Setting with the threshold Ç= = 0.005. The true change points are located at 101, 201, 301, and 401. The change points detected by the EMS and EMSL methods are closer to the actual change points compared to those detected by the ITS and ITSL methods.
The performance of the segmentation algorithm depends crucially the quality of the randomization- based p-values from each sub-string. Intuitively, a more significant discrepancy between the p-value distributions under the null and alternative will lead better segmentation results. Thus, powerful watermark detection algorithm is crucial to the success of the segmentation procedure. Motivated by Condition (4) an interesting future direction detection procedure where the LLM provider adaptively embeds the key according to NTP, and the detector uses corresponding adaptive procedure to detect the watermark.
develop an adaptive watermark generation and
Another interesting direction to explore extending the algorithm to handle scenarios where the published text combines Watermarked texts from different LLMs with varying watermark generation schemes. In this case, the goal is to separate the texts into sub-strings from different LLMs. This scenario involves multiple sequences of keys from different LLMs, each producing sequence of p-values and change points. Figuring out how to aggregate these results to separate different LLMs and user-modified texts would be intriguing problem.
Acknowledgments and Disclosure of oufFumm Funding
GL and XZ were supported by the National Institutes of Health under Grant R01GM144351. Part of the research was conducted using the Arseven Computing Cluster the Department of Statistics, Texas A&M University.
References
Scott Aaronson. Watermarking of large language models, 2023. BttRllhtts:/:/immette http://immos.....eeeeee...e edu/talks/scoott aaronson- uu aistaustin-opee oienan-penai---. 2oriiii-222------111
Sahar Abdelnabi and Mario Fritz. Adversarial watermarking transformer: Towards tracing text provenance with data hiding. In 202/ IEEE Symposium on Security and Privacy (SP), pages 121-140. IEEE, 2021.
2000:44000000221.000000 00083
@I@ Meta. Llama 3 model card.
MODEL_CARD... md
2024. URL btttps//gittub.... http:/uww..cccm/eaaaaaaaaaaaaaaa /
MODEL, CARD. md
Mikhail Atallah, Victor Raskin, Michael Crogan, Christian Hempelmann, Florian Kerschbaum, Dina Mohamed, and Sanket Naik. Natural language watermarking: Design, analysis, and proof-of-concept implementation. In Information Hiding: 4th International Workshop, IH 2001 Pittsburgh. PA, USA, April 25-27 200 Proceedings 4, pages 185-200. Springer, 2001. URL
https://doi. org/ 10. 1007/3 540 0110//3--54444499---- 45496-4499.0 9_14
Rafal Baranowski, Yining Chen, and Piotr Fryzlewicz.
Teroowes--Oee--Theeeee Detection of Multiple Change Points and Schange-Point-Liig Features. Journal of the Royal Statistical Society
Series B: Statistical Methodology, 61())669-667, 05 2019. ISSN 1369-7412, doi: 10.1 1/rssb.
12322. URL ht //oii org/ 10. wwwi/rsssb....ee 12322
10

---

Zhongze Cai, Shang Liu, Hanzhao Wang, Huaiyang Zhong. and Xiaocheng Li. Towards better statistical understanding of watermarking llms. arXiv preprint arXiv:2403.13027 2024. URL
https:://oi.
48550/ arXiv 2403. 1r...//0rr.....45///////.... 13027
Edward Carlstein. Nonparametric change- point estimation. The Annals of Statistics, 16(1):188-11)
1988. URL http::ttt//oooiioo
Shubhadeep Chakraborty and Xianyang Zhang. High-dimensional change-point detection using generalized homogeneity metrics. arXiv preprint arXiv:2 2021. URL https///s:///o
485/0004.555/rxxxv, 2105.08975 08976
Hao Chen and Nancy Zhang. Graph-based change-point detection. Annals of Statistics, 2015. URL https: 1atpr//....21414-4A00000 1214/14-A0S1299
Pierre Fernandez, Antoine Chaffin, Karim Tit, Vivien Chappelier, and Teddy Furon. Three bricks to consolidate watermarks for large language models. In 2023 IEEE International Workshop on Information Forensics and Security (WIFS), pages 1-6. IEEE, 2023, https:s/://ddo org/
10. 0..44855//aaa artp:/rrXiiiv. 20..22300.00111
Piotr Fryzlewicz. Wild binary segmentation for multiple change-point detection. The Annals of Statistics, 42(6):2243 2281, 2014. doi: 10.1214/14-ASS1245 URL https://doi.org:
1011/144A0S1243
Zaid Harchaoui and Céline Lévy-Ledue. Multiple change-point estimation with a total variation penalty. Journal of the American Statistical Association, 105(492);1480-4493 2010.
Nicholas Hopper, David Molnar, and David Wagner. From weak to strong watermarking. In
Theory of Cryptography: 4th Theory of Cryptography Conference, TCC 2007, Amsterdam, The Netherlands, February 21-24, 2007. Proceedings 4, pages 362-382. Springer, 2007. URL https
Zhengmian Hu,, Lichang Chen, Xidong Wu, Yihan Wu, Hongyang Zhang, and Heng Huang. Unbiased watermark for large language models. arXiv preprint arXiv:23 20. 10669, 2023. URL https
//doi.org/10 48550/ arXiv. 2310.
Baihe Huang, Banghua Zhu, Hanlin Zhu, Jason D Lee, Jiantao Jiao, and Michael Jordan. Towards optimal statistical watermarking. arXiv preprint arXiv:2312.079.00 2023. URL httpts:tt////
org/10.
org/10.48550/ 48550/ 118550/arXiv. arXiv. 2312. 07930
John Kirchenbauer, Jonas Geiping, Yuxin Wen, Jonathan Katz, Ian Miers, and Tom Goldstein. A watermark for large language models. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 17061-17084 PMLR, 23-29 Jul 2023a. URL https: httpp://prrceeednngs mlr press//222//sircchebuuee2222 html
John Kirchenbauer, Jonas Geiping, Yuxin Wen, Manli Shu, Khalid Saifullah, Kezhi Kong, Kasun Fernando, Aniruddha Saha, Micah Goldblum, and Tom Goldstein. On the reliability of watermarks for large language models. arXiv preprint S1t.:::300604633:: 2023b. URL httpp:///oii. org/
10. N0.44850//rr/ arriv 2306. 04634
S Kovács, P Bühlmann, H Li, and A Munk. Seeded binary segmentation: general methodology for fast and optimal changepoint detection. Biometriku, 110(1):249-255 2022. ISSN 1464-3510. doi: 10. 10.10093biomeerasscc0522.. URL httph:ttp::/ttt org/ 10. wtt.biimte//satsaat0e
Rohith Kuditipudi, John Thickstun, Tatsunori Hashimoto, and Percy Liang. Robust distortion- free watermarks for language models. arXiv preprint arXiv:2307.15599. 2023. URL https
//doi.org//1 48550/arXiv 15593
Hans R Kunsch. The jackknife and the bootstrap for general stationary observationnsss The annals of Statistics, pages 1217-1241, 1989. URL http://pe/..ooooooo/////////////
Soumendra Lahiri. Theoretical comparisons of block bootstrap methods. Annals of Statistics, pages 386-404, 1999.
11

---

Xiang Li, Feng Ruan, Huiyuan Wang, Qi Long, and Weijie J Su. A statistical framework of watermarks for large language models: Pivot, detection efficiency and optimal rules. arXiv preprint arXiv:2404.01245, 2024. URI https://///o htt.://i..rrg///// 10550/000.55500/11111/ 2404 01245
Xingchi Li and Xianyang Zhang. fastepd: Fast change point detection in r. arXiv preprint 2rXiv:2444.05933, 2024. https:/:////o htt.ooo0rrrr000...860/////1//// 2404 05933
48550/arXiv.
Regina Liu, Kesar Singh, et al. Moving blocks jackknife and hootstrap weak dependence. Exploring the limits of bootstrap, 225:248, 1992. URL httts::/ww.. www.w.cole.ooooooo.oooo..mmmmm entus/nu///////
Yepeng Liu and Yuheng Bu. Adaptive text watermark for large language models. arXiv preprint arXiv:2401. 2024.
wwt.rxiii..1....... 13927
David S Matteson and Nicholas A James. A nonparametric approach for multiple change point analysis of multivariate data. Journal of the American Statistical Association, 109(505):334-455 2014.
http///i..oggggg/// 2tg//1... 100000000/111 00880/00621459 2013. 849605
Travis Munyer and Xin Zhong. Deeptextmark: Deep learning based text watermarking for detection of large language model generated text. arXiv preprint arXiv:2305.05773, 2023. URL https
4854445555333 arXiv 2305 05773
P. Fearnhead R. Killick and I. A. Eckley. Optimal detection of changepoints with a linear compu- tational cost. Journal of the American Statistical Association, 107(500);1590-15988 2012. doi: 10. 111118000161159.202222...
URL
Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al. Language models are unsupervised multitask learners. OpenAl blog, 18):9, 2019. URL httpphtts//:/pnnaa
Colin Raffel, Noam Shazeer, Adam Roberts. Katherine Lee, Sharan Narang. Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. Journal of Machine Learning Research, 21(140):1-67, 2020. URL
http://jmlr. http:://jmml..oog/pppeereee wttp:/appers/v21/20---e
html
William M. Rand. Objective criteria for the evaluation of clustering methods. Journal of the American
Statistical Association, 66(3366:846-850 1971. doi: 10. 101100001214559199977 1971 197119929971111 10482366. URL
Soctps://wwee tanddonnlnnnn www. http:///oaaaabat...1/////1/19110 01t.:00000001224444.000000066630
Sidney Resnick. A probability path. Springer, 2019. URL
778-0-8176-8409-
Charles Truong, Laurent Oudre, and Nicolas Vayatis. Selective review of offline change point detection methods. Signal Processing, 167:107299, 2020. ISSN 0165-1684. doi: https://do..rr/ 10.1016//.sigrro..i 2019. 2019.107299. pp1/S0165164419834944
Lyudmila Yur'evna evna Vostrikova. Detecting "disorder" in multidimensional random processes. In Doklady akademii nauk, volume 259, pages 270-274, Russian Academy of Sciences, 1981. URL
https: //ww:////wwwww mathnet........... ru/ eng/ dan4448244422
Yihan Wu, Zhengmian Hu, Hongyang Zhang, and Heng Huang. Dipmark: A stealthy, efficient and resilient watermark for large language models. arXiv preprint arXiv:2310.07710, 2023. URL
https: otg/ 10. 48550/a55s arXiv 3310.07710
Susan Zhang, Stephen Roller, Naman Goyal, Mikel Artetxe, Moya Chen, Shuohui Chen, Christopher Dewan, Mona Diab, Xian Li. Xi Victoria Lin, Todor Mihaylov, Myle Ott, Sam Shleifer, Kurt Shuster, Daniel Simig, Punit Singh Koura, Anjali Sridhar, Tianlu Wang, and Luke Zettlemoyer. Opt: Open pre-trained transformer language models, 2022. URL httph:ttt:///tt/ org 48550/ arXiv. 2205.01063
Xianyang Zhang and Trisha Dawn. Sequential gradient descent and quasi-newton's 's method for change-point analysis. In International Conference on Artificial Intelligence and Statistics, pages 1129-1143, PMLR, 2023.
12

---

Xuandong Zhao, Yu-Xiang Wang, and Lei Li. Protecting language generation models via invisible watermarking, In International Conference on Machine Learning. pages 42187-42199, PMLR, 2023. http.pttts::///o..... http:////ooorg/1////// org/10..///. 48550/arXiv 2302 03162
Xuandong Zhao, Lei Li, and Yu-Xiang Wang. Permute-and-flip: An optimally robust and water- markable decoder for llms. arXiv preprint arXiv:2402.05886, 2024. URL URthhtss:://da org/10 48550/ arXiv. 2402 05864
13

---

Appendix
A Proofs of the main results
Proof of Theorem 7
(i) For simplicity notation, denote yp = @(51:n (1:m) and (p(()) == <l 71 ) for 1, T. Under the null hypothesis, we know that Ç1.m is independent of 31:m. which implies that the pairs (Ei: 31:m); (4i "1. ...., (elm) F1m) follow the same distribution. Hence yp, pll)..... ...., ((()) are exchangeable. The exchangeability ensures that the rank of ip relative to fip, po()) ,..., p())) is uniformly distributed. Denote the order statistics P(1) I ..... I ((T+1). Then we have
P ( = (()) = T+1 j= ;=1,...,T+ T
Hence, for j = I...., T + 1, we have
P P(p pr S T+1 *T+11
p (P
T T+1
Then, we have P (pT S <a) = L(T + 1)ae /
/TT +))
(ii) Denote Ege == Elo(51.n F1:ml Fmm]. By Chebyshev's inequality and Condition (a), we get
Var(c(Si... (m (Fm) C, 2
P (lo(E(sm V1.m) Egel 2 e/Vn(Fm) S
e2/n
for all e c 0. Thus @6 F1:m) - Egr = Op(n (13),, which together with Condition (b) implies that (Ei.. Fi.m) =
given Fm.
Denote the distribution of (5imm m)) conditional on Fm by F, and the empirical distribution of (op(9) Jt-0 by Pr, where we set (0))) = sp Let @1-o,7 = ((T+2-jw) with j. L(T + 1)aJ. Note that Fr(q1-a.)) 1 - (i. () + 1). Our test rejects the null whenever pr S a, which is equivalent to rejecting the null y P(T+2-j.)- By the Dvoretzky-Kinnn Kiefer-Wolfone we have
inequality,
P([Fr (91-a.7) F(q1-a,T) > c F(F S P(sup Fr F(x) > c(Fm) S C1 exc((22T)
for some constant C1 > 0, which implies that with probability greater than 1 C1 exp( exp(-21ee)) F(q1-a.T) < 1 - (ja (T 1) 2e. Define F (t) inf : F(s) 2 t and the event Ar = {qi-a,7 < F (1 (1- (ja - (T (T//TT++1) +2)+ Then we have (Fr 2 1 - C1 (T In addition, as @L Fim) = (n.11/ we have F-1(s) (n-1//2 for any 8 < 1. By Condition (a), we have Vn(olEim 71:m) ) - B[ Fmmm FF.l) = (1). Hence, for T > 2/E - 1,
P PlolEi:n ) 2 - Fi))
2 P ( Fmm) - El Fm.m) (mm) + /nEid(EEsn Fimm [Fm]] 2 Vnq T, Arl Ar(Fm))
> Vnnllll Fz:m) BiØ(E1:n Fz.m Fmml + VnE(o(Ei:n Fr:m) Fml
2 (1 -ii -1)(TT + 1) Ar|
2 P ( Fi.m) -B( F1m / ( ( [
2 VnF (1 a Ar
21 - Ci exp(-222 o(1),
where have used Condition (c) and the fact that vFF + 3e) O(1) get the convergence.
O
We state the following Lemma, which is useful for the proof of Corollary Lemma 1. {E. are conditionally independent given no:n
14

---

Proof of Lemmal 7 We note that
Recall that ys = I(E:, p-101--o---11)) = (,(E)), where r, depends on --
2 p(5im Vimll-no:s)) =p(E1, V1ly II
plE vilf::-1. 1.
II [[T](E)) -y:n((t))=ll(((.)))
Hence the conditional distribution of Ei.n given y V-nignn is equal to
II (TT((u) yo (du(u)
p(Cim|y
(A.1)
=1 Jr.(w)=v dv(u)
which implies that (&r)= are conditionally independent given yyng.:n
Proof of Corollary 7
(i) Recall in Example that the test statistic is given by:
T (v,) V
1 2) 2
(Eimn Vi:n)
Σ uus 1/2) n 2=1
= 71 Σ
hs(Ss. U.),
where E = (ut, ).). We first note that (E,, Di) is bounded and thus Condition (a) of Theorem Since <i.m independent of y-nomn. we have 1/11 ~ Unif(0, 1). Thus, E[o(( 1im) Vi which implies that Condition (b) of Theorem is fulfilled.
D holds.
Denote (a(+) (i-lyynosi-l) Conditional on Y-nozi and x. (U:), we know that uy follows the uniform distribution over the interval [u+(y: : (:(y) < (y())) (V : TT(y) S (y:))) As a result, can calculate the expected value of u, given V-ng:i and x; (y:)
1
E Uu 1y Rodi Ty (B:)) = {ui (y) < (v(i)) + uu (v) S (:())))
2
(i(vi)
+ 14(y (v) < (3:))
2
pi(1i)
+ Ti -
V - (1 - uı(y;))
1
(1 - m4(1))) (T:)):
1
2
2
where the third equality is because given n, (3:) k. n; follows the uniform distribution over the permutation space with the restriction T (1:) = k. Then, we have
Te (vx) -
1
E
Uu
1/2)
V 1
2
(1:) -
E
E
(ui 1/2)
1y Wyngg T(Vss) la moad
V V-11
Te(ss) -
1>
E
(1
(x(v)))
V -
2
(T((U)) -
1 1
(1 plus (ouly-oo:-=)))
1y ng:i
v-
2
Given yis (Tr( 1) 1) follows the uniform distribution over the discrete space (0, 1/(V 1),..., 1). Thus have B[(T;( 1)/(V-)VV))) -1] 1/2 and Var((T; 1)/(V 1)) C,
which is a constant less than 1/12 (i.e., the variance Unif 1)). Hence, E E(d(E1. (o(fi:m:1im))) =
On-1 En (1 p(u)lvis-1) and Condition (c) of Theorem is satisfied due to (4.
(ii) In Example 2 the test statistic is given by
n
@lEim, Vlm) =
(logEEr,,) ) +1].
15

---

Observe that Est = log( (pg((S))/p(plep (pp(kk/-noottttae no:t--no-1) ~ Exp(p(k (kly)k)s-1)1))) Since fi. is independent of Pion we have logg(/ ) -g- Exp(1). 1). Hence. conditional on n-nam we have
(S Vl.m Di O, Var( Ml Ml n
Condition (b) of Theorem satisfied.
Given y- -gn
we know
Fi.g: Exp(1). It worth noting that
min Fikts
which
implies
- (L..) //((1) (V----oo 11---/-noolll-----
log(En
P(- ((-log(Er.v)) 2t = p(y/ B (/o----) p(y plyily-mont (
exp ply: mo-ooo-))
That is log(Er. mymmmo Exp(1/ httpppp(sll// plp.:yyylooaiii (o:tt-- 1)). According Lemma independent given y-noom Thus, we have
EiS are conditionally
n
El Elo(Eim V1mm (1mm)yynmaa
(1
ply (33:l1/-aa (oott)))
71
1=1
n2
Var(é(Eim M1:n) Mantiiimmmmmmoooo nomm)
Σ
p(y:ly-noii-1)
n
n
Therefore, Conditions (a) and (c) of Theorem I are satisfied.
Proof of Theorem We only prove the result under the setting of Example the proof for Example
2 is similar with the help of Bernstein's 's inequality. Because [h:] S 1/4, by Hoeffding's inequality,
we have
(IM(SaaaBBB Wh.b+ B B-1)
B[M((naa++ B- Ub.b+ B 7i Mgng:n]] 1/7i.mm V-ng:n)
2 exp (-8BP).
By the union bound, have
P
max M(Enaa B- 11
E
Wb.b F1:m V-nomn]
flyi:m U- nomn
<2(n B + 1) 1) exp (-8B²).
Integrating out the strings in Vı.n that are not contained in Tiom we obtain
P
max 1to5n-BtLis0sm-BBA [M(Ena+B-I B- Db.b
B[M 1,
V-no: > F|
<2(n B + 1)(m B + exp (-8B1))
where Fm -Bi 0 0. Thus, conditional on Fm. max., & (I M(Ea.oBBLL Vb.b+ -- 1) O(Cx,B), Note that
6lElon 11:m)
max M(Ea:a+ (b.4
a.b
2 max
-max -Max(E [m] B 8664
a.b T O
16

---

On the other hand, for a randomly generated key Ei. -eettttt----e = 0 for all a, By the same argument, we get
P (o((1i Fimm > () =P
M B-1. {
Fm
max 1sa5n- --1-----1..5mm----11 B+1
<2(n B + 1)(m - B 1) exp (-8B:)).
which suggests that (x) = O( with F being the distribution of (fim V1:m) conditional on Fm and (t) inf s: F()) 2 t}. The rest of the arguments are similar those in the proof
of Theorem We skip the details.
Proof of Proposition ! Note that conditional on Fm. the p-value sequence is B-dependent in the sense that Pi and pj are independent only if j - > B. Under the assumption on B, we have
B
Var( 1:b Ft)
o(1)
for bb - al x m. which implies that 1o (1) - 1F - for any given I E [0, 1]. Using similar arguments in the proof of Theorem 7.5.2 of Resnick
2019), we strengthen the result to
allow uniform convergence over E [0. 1]:
sup |F - E[Fa+1s + O. xE(0.1)
Therefore, we obtain
max (T) 1ST<m
1mm((T))
=Vm- (m T*)
sup [F.r. - 1- (Frr+11m (1)
-1mm (()) + E(Fr--Ism(())
EE[F +1 1:m (4)
m²
tE[0,1]
2/m T* (m - T*)
sup It rE(0.1)
(f)) sup
|F1-- (t) - xE(0.1)
m²
- sup |F (t) F[ 1:m (t)l
1E(0.1)
() +0))))))))))))))))))()))) + t00.
Proof of Theorem We begin the proof by noting that
T(m T) (Fi: 3322
Fr+ (t))
(1fp. St Fi.m(t))
m
Let us focus on the case where 9 T" By the definition of f, have
The other case where f > 7" can be proved in a similar way.
5 sup
(1(p St (i)m
sup
(1[p: St Film
= =[(()) -[f)-((T)) I(T*).
1=1
For any S a < < and there is no change point between [a, b), define Was = >b 1(p S
t} and W. (t)(t)= = Σ (1pp, (p. < t) [t)]. For any S T", we have
I(r) = sup W1. m (W (t) + W (+-+1=((t)
m
1
sup
(F)(())
F + (m ------0 E')EFF+++mm (00) + R(T)
m (
(m - -T")
D(Fo. E +1:m (t))) + R(T).
m²
17

---

where R(T) is reminder term satisfying that
1
I (W) +im (t)
[[()] - m
sup W m
Hence, we have
s((()) I(("))
- am--))( T²)
(Fo. EF. +1 (t))) + R(f) - R(T")
m²
(m 7" (* - -T')
D (Fo. E[ F. 1mm (t))) + 2 sup [R(T),,
m²
TST
which implies that
2m
sup R((r).
(m T ((F.. E[ 1am (t)))
+
Notice that
sup R(T) S sup sup m rST" rE(0.1]
Wi:-
[W (Wi:T-(1) 11m (1)
m
sup sup rST [E(0,1]
Witr (1) + sup [E[0.1]
Wi: (1) + 4
Wi. (4) + Op 1/2).
sup sup rsm [0
remains to analyze sup+sm suP:e[o,1] W 1 (t)l. first present result that slightly modifies the Ottaviani's 's inequality. For the ease of notation, we write || suPse(o.1] (i)+(()). For any > 0 and e >> B, we have
P(IlW 1om
B)
max
W > u + S rsm
(A.2)
max, P( [++mmll > u)
To see this, let A the event that [[ is the first [[i: (for 1,2, m)) that strictly greater than u u. The event on the LHS is the disjoint union of A1...., A. Note that || [W&++1Bmll is independent of [|Wil,.... ||all (and hence is independent of A₂). We have
P(Ax) min P(I +iIW+ $ u) <AA,, [ B:mll S u) O5r<m
<(Ak, [ S u B)
<P(Ak, || B),
where have usede the fact ||W I|m++ leads to
S [ + || uu Summing
max 7Sm
W1 1.
> u +
min ostem
P(]
S u) S P([ > w- B),
which gives the desired result.
Next, we study P( (1WW, u) for any == O....,m 1. Note that P([[W71mml > u) s P[I[W,+1-r=1] > u/2) P(
u/2). Thus, without loss of generality, let us focus analysis on the probability P[[ a- > u). where the corresponding segment does not contain a change point. Assume b
2K B. (Notice that for general < 6, we have additional interval whose length smaller than B. Hence, a similar analysis below can be used.) We divide the index set {a + 1, 2,..., b} into 2K consecutive blocks, denoted by JI...., J2K. with equal block size B. Then we have
K Σ
K Σ
P(IW P > 4) <
F
> u/(2B)
+
FJa
>
u/(2B)
18

---

with F,, W. where E FJz_-, and Σi= FJ,. are both sums of independent bounded random variables. Let us analyze the second term on the RHS. Define
K
G(t)
Σ
P(D 1t)(KBB),
i=1 JEJ2
K
(t Σ
E jEJ2s
1P S (0((B)).
Let L. (u/L) for 1.2,..... ....: L. Following the argument in Theorem 7.5.2 of Resnick 2019], we can show that
1
Σ J21
= 1G - -Gll & max (mm(tt.)) ((mltt..)) G(to, L' isust.
K
where Gm (1-) = = EieJo 1ip < (I/(B) and G(I-) is defined similarly. Thus we have
P
Σ Fiz
> w1((BB)
<P
max ISeSL
G(te,))) -aa. aa)
-a)
P(IGm((o,t) G((o,t.) (l,, ( G((,,t-) u/(b a) - 1/L)
==1
L (-C2Klu/(b - a) - 1/L)²)
where the third inequality follows from Hoeffding's inequality. For any 6 0, we can set
C2(b-a) Ca(b-a)
/logK))) 2CBB / KK log(K) and L = VK for some large enough C3 such that
K
P
FJ2 Σ
> w/((BB
S.
Now back (A.2). set Cav/m Bon(Bl/ B) and = Cs
We can make
the RHS of A.2 arbitrarily small with large enough C4 and Cz. thus gives max-5m || O( ///B lowgm//mmmmm//mo B)) and sup, [[((T) O (
(V Blggmm//////// B)/m Hence, we deduce that
mB log(mm/D D(Fo, (mm()))
T" f < Op
similar argument applies the other direction, which gives
mB log(m// B) D(Fo. E. F[F,-41:m (t))
} -- Op
19

---

B Additional numerical results
B.1 The Levenshtein cost
Recall that we use V to denote the vocabulary and E to represent the space of watermark keys. Let V" be the space of strings, where * can be any positive integer; for example, V1.m V Similarly, we define E* as the space of watermark key sequences. Given a string let Ya: be the string from the ath token to the end; for example, if gj Vimms then y2. = 1/2.m. Denote the length (e)
string y as
Definition 1 (Simple Levenshtein cost). Lety E R and base aligument cost do : x E - R. Given a string y E V and a watermark key sequence & E E*, the simple Levenshtein cost (g E) is defined by
d (3.E) == min (d, (T2.. E2.) + do : E1), dy (3, E2:) + 7, (02. +)7),
(B.1)
with d, (7.E) = yy if is empty and d,, (T. E) = [e) if y is empty.
We the following metric quantify the dependence between the watermark key and the string:
M(Ei:n: Fi:m) (dimmi E1:r);
(B.2)
where 7 = 0.4, and
T1 (1/1 1
do( (u1, m)))
141
(B.3)
in inverse transform sampling method, while
do(ā1, E1) = log (1 (1,51)
(B.4)
in exponential minimum sampling method.
B.2
Sequences of p-values from Opensl-Communit//PP2
presents the p-values for 500 text tokens generated from 10 prompts. The lan- guage model used is openai-conmunity. 22gpt2 obtained from https://uuggigfart coiianiicommumtt..... tttettttttttttttt The p-value sequences are organized into four groups, namely four settings corresponding to the numerical experiments section the main paper (Section[4) 4
Figure B.1
co/
Setting (no change point): Generate 500 tokens with watermark.
Setting 2 (insertion attack): Generate 250 tokens with watermarks, then append with 250 tokens without watermarks. In this setting, there is a single change point at the index 251.
Setting 3 (substitution attack): Generate 500 tokens with watermarks, then substitute the token with indices ranging from 201 to 300 with non-watermarked text of length 100. In this setting, there are two change points at the indices 201 and 301.
Setting (insertion and substitution attacks): Generate 400 tokens with watermarks, substi- tute the token with indices ranging from 101 to 200 with non- non-watermarked text of length 100, and then insert 100 tokens without watermarks at the index 300. In this setting, there are four change points located at the indices 101, 201, 301, and 401.
Within each group, the rows represent p-values calculated using four different distance metrics: EMS, EMSL, ITS, and ITSL. It is easy to see that EMS performs the best, followed by EMSL.
B.3 Results for Facebook/OPT-1.3b
Figure B.2 shows the results for false discoveries under Setting 1, where the text tokens are all watermarked and generated with aaceboox/opt-1.11 A lower threshold leads to fewer false discoveries.
Figure B.4 shows the boxplots of the Rand index for the four methods under different settings. EMS demonstrates the best performance across all settings, achieving best performance at a threshold of 0.005.
20

---

Lat
MM
MMM
AW
MIY
DIM
NWN
M.M
Figure B.1: Sequences of p-values for the first 10 prompts extracted from the Google C4 dataset for L.LM openai www.wnottooooooeeee.ee..... coammunity/gpt:.. tgpt, organized into groups of four consecutive rows, each group corresponding to distinct setting. Within each group, the rows represent p-vuuues calculated using four different distance metrics: EMS, EMSL, ITS, and ITSL.
Setting 1, EMS
Setting EMSL
Setting 1, ITS Setting 1, ITSL
7.5
Change Point Count
5.0
2.5
0.0
0.001
0.005
0.01
0.05
Threshold
Figure B.2: The boxplots of the number of false positives with respect different thresholds under Setting 1. The texts are generated using facebook/ optto.tttt1... and the four distance metrics are EMS, EMSL, ITS, and ITSL.
21

---

UNL
POW
JON
MUMM
W JUWN
VIL A.AM
MUMNN
LAM M ME
M
I
A MaMi
JUKA
M
M
WAMMAA M AMW WAWN
Figure B.3: Sequence of p-values for the first 10 prompts extracted from the Google C4 dataset for LLM bacebook/opt-21 1.pt-1.3.. 3b, organized into groups of four consecutive rows, each group correspond- ing distinct setting. Within each group, the rows represent p-values calculated using four different distance metrics: EMS, EMSL, ITS, and ITSL.
10
Switin 2, EM5
Seting 7.
Settin 2.555
0.8
Setting 2. ITSL
EMS
Swiing 3, EM51
0.6
Settin
Setting 3.
Suxing
Swiing EMSL
Seting 175
Sctting ITSL
Thondook
Figure B.4: The boxplots of the Rand index comparing the clusters identified through the detected change points for texts generated using facebook/ opt-1.3b with the true clusters separated by the true change points with respect different thresholds Ç.
22

---

The sequence of p-values from the first 10 prompts extracted from the Google C4 dataset in all settings presented in Figure B.3] The p-value sequences are organized into four groups, corresponding to the four settings in the numerical experiments section of the main text. Within each group, each row corresponds to one method.
By comparing with the p-value sequences obtained using openai-communa the segmentation algorithm' 's performance depends on the quality of the p-values obtained for each sub-string and this relies on not only the watermark generation schemes but also the language models from which the texts are generated.
gpt2, we claim that
B.4 Results for mcta-lama//Vetaallaaa-333
Figure B.6 shows the results for false discoveries under Setting 1, where the text tokens are all watermarked and generated with aitta-llaaaaMetter -aa---a----aaa----..... A lower threshold leads to fewer false discoveries.
323
353
339
LE3
A
343
315
WYY
MM
MINE
AN
A KUV
AMM
MAM
MNY
BONN
LOMMAN
J UAA
LES
LINNMAM
V
LO
325
375
LES
MONLAMI
30
MMMI VAL
30030030 ANC 300
MON 200 1R0 SKC
100200300-000 40000 20300 ANC 300 100 AOO
FOR 400
Figure B.5: Sequences of p-values for the first 10 prompts extracted from the Google C4 dataset for LLM meta-ll L corresponding to distinct setting. Within each group, the rows represent p-values calculated using four different distance metrics: EMS, EMSL, ITS, and ITSL.
organized into groups of four consecutive rows, each group
23

---

Figure B.7 shows the boxplots of the Rand index for the four methods under different settings. EMS demonstrates the best performance across all settings, achieving its best performance threshold of Ç = 0.005.
Settnn 7, EMS
Setting EMSL
Serting
ITS
Setiin IS
Changee Point
Threshold
Figure B.6: The boxplots of the number of false positives with respect to different thresholds under Setting 1. The texts are generated using meta- meta-llama/Mee Samaa/MetaLLamas 3-, and the four distance metrics are EMS, EMSL, ITS, and ITSL.
1.0
Setting
Setting 2,
Setting 2. EMSL
0.8
Setting 2. ITS
Setting 2, ITSL
Rand Index
Setting 3, FMS
0.8
Setting 3. LMSL
Seeting 3, ITS
Seiting 3, ITSL
0.4
Setting
Setting EMSL
Setting
0.001
0.005
0.01
0.05
Threshold
Figure B.7: The boxplots of the Rand index comparing the clusters identified through the detected change points for texts generated using meta- (ie-llame alaamm/Mettt Met//Mtaaliaa -aa--Lamma------ with the true clusters separated by the true change points with respect different thresholds Ç.
B.5
Other settings
We focus the Meta-LLamaa-38B model to conduct simulation studies under more difficult scenarios. Specifically, we increase the number of change points to 4, 8, and 12 and vary the segment lengths accordingly. The results are presented in Figure B.8 For scenarios with 4 and 8 change points, the proposed method successfully identifies all change points. As the number of change points increases, the change point detection problem becomes much change points, our method was able to identify 9 of them, showing its robust performance in handling more difficult situations. Generally, the difficulty of change point detection problem depends the distance between the change points and the magnitudes of the changes, as indicated by the theoretical results in Proposition
challenging. In scenario with 12
C Choices of the tuning parameters
We investigate the impact of the window size B and the number of permutations T the proposed method. In particular, we focus on the EMS method in simulation Setting of the main text, using the Meta-Llama-3-4t model.
24

---

Four change points
change po
Twelre change points
0.59
3.00
0.00
Figure B.8: Sequences of p-values obtained using the EMS method across various settings. Change points identified by the proposed method are marked with red dashed lines.
First, study the impact of the window size B, fix T 999 and vary the value of in the set {10, 20, 30, 40, 50}. Table C.I shows the rand index value for each setting, with higher rand index indicating better performance.
Table C.I: Results for different choices of B when T = 999.
B
10
20
30
40
50
Rand index
0.8808
0.9429
0.9641
0.9570
0.9243
is crucial select an appropriate value for B. If B is too small, the corresponding window may not contain enough data to reliably detect watermarks, as longer strings generally make the watermark more detectable. Conversely, if B is excessively large, it might prematurely shift the detected change point locations, thus reducing the rand index. For instance, let us consider scenario with 200 tokens where the first 100 tokens are non wotemaaermarked, and the subsequent 100 are watermarked, with the true change point at index 101. Assuming a p-value uniformly distributed over [0, 1] over a non-watermarker window and a p-value around zero over window containing watermarked tokens. When B 50, the window beginning the 76th token contains one watermarked token, which can lead to a small p p-value and thus erroneously indicate watermark from the 76th token onwards. In contrast, if B = 20, the window starting at the 91st token will contain the first watermarked token, leading to a smaller error in identifying the change point location. The above phenomenon is the so-called edge effect, which will diminish B gets smaller.
detection test is highly effective, then it will yield
The trade-off in the choice of window size is recognized in the time series literature. For instance, common recommendation for the window size in time series literature is to set B = 1/3 where the sample size, as seen in Corollary of Lahiri [999]. Based on our experience, setting B 2/3 (for example, when n 500, B 23) often results in good finite sample performance. A more thorough investigation of the choice of B is deferred to future research.
We next examine how method is affected by the choice of the number of permutations T. To this end, we set B to 20 and consider T E {99, 249, 499, 749, 999}. The results are summarized in Table C.2 including the rand index value and computation times for each setting. As expected, the computation time increases almost linearly with the number of permutations T. We also note that the rand index remains consistent across different values of T, indicating level of stability in our method.
Table C.2: Results (computational time in hours and rand index values) for different choices of T when 20.
99
249
499
749
999
Time in hours
3.41
7.33
11.47
18.47
24.94 0.9354
Rand index
0.937
0.9404
0.9326
0.9348
25

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We claim contributions in the abstract and introduction. (i) We rigorously study the Type and Type II errors of the randomization test for detecting the presence of watermark. We then apply these findings the inverse transform and Gumbel water- mark schemes. (ii) We develop a systematic statistical method for segmenting texts into watermarked and non-wann non-watermarked sub-strings, and investigate the theoretical and finite sample performance of this methodology. which has yet to be thoroughly explored recent literature.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
It is fine include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We have emphasized that the segmentation algorithm's performance depends crucially on the quality the simulation-based p-values from each sub-string. Therefore, powerful watermark detection algorithm is essential for the segmentation procedure's success.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best
26

---

judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: In the main text, we formally state essential assumptions for theoretical results and provide rigorous proof in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: We include all experimental details, such as LLM and hyperparameter values, in the main text and provide code for reproducibility the supplementary materials.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
27

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We have provided the code for reproducibility in the supplementary materials. The code has already been uploaded to GitHub. Due to the double-blind policy, the GitHub repository can't 't be accessed now, but will make it open access if the paper is accepted.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cr cc/
public//uiide//Codeuuuiit sow.sooobbsssioooioooooooo for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
//nips https//ccccpllicgggeeeeeeeeeeeee
for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We include all experimental details, such as LLM and hyperparameter values, in the main text and provide code for reproducibility the supplementary materials.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
28

---

Justification: We do not need to display the error bar in our experimental results; in other words, the experiment results don't 't involve an error bar. We do include boxplots way to show the performance of the algorithm. The statistical significance is obtained through bootstrap-base patrra test for each and every single change point, and comparisons have been made between performances using different p-value thresholds.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We provide information on our computer resources in the supplementary materials, specifically, the accompanied README, md file in the reproducing materials.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: Our research conducted in the paper conforms with the NeurIPS Code of Ethics in every respect.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
29

---

The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: In the introduction, we emphasize the importance of distinguishing between human and LLM--roduced texts. This is essential to prevent the spread of misleading information, improper use of LLM-based tools in education, model extraction attacks through distillation, and the contamination of training datasets for future language models.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e-g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deg.lymemmm of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out, For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (c.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
The paper poses no such risks as no pretrained models are created. The models used in the paper are publicly available and peer-reviewed and thus have minimum risk for misuse.
Justification:
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
30

---

Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: Two pretrained language models were used and properly cited, as well as the GNU Parallel used in the experiments.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g.. website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperssi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
The code and algorithm are documented properly and provided alongside the code.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/codeemmodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether how consent was obtained from people whose asset used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
31

---

15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
32


Reviews:
[{"review_id": "PwZ80yTp9m", "reviewer": "Reviewer_SyZV", "summary": "This paper considers the problem of segmenting a watermarked text into watermarked and unwatermarked subsequences. This is achieved using change point detection methods. There is a nice statistical analysis of the single change point detection problem, and a heuristic algorithm (from Kovács et al., 2022) with experimental results for multiple change point detection.", "questions": "Why was block size B=20 chosen? Is it important that B = B'? How do these and other parameters affect the performance of SeedBS in this setting?", "limitations": "Limitations are adequately addressed.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper is easy to read.\n\nSection 2 (Problem setup) presents a result (Theorem 1) on the power of the watermark test that is more rigorous than previous presentations (to my knowledge).\n\nThe connection to change-point detection literature with analysis using the block-bootstrap is interesting (Section 3). While I am not deeply familiar with the change-point literature, the connections and application of these methods appears correct and well-cited.\n\nThe experiments appear well-executed.", "weaknesses": "This paper could be criticized for novelty, in the sense that it mostly applies standard tools from the change point detection literature to watermarking. I find Remark 2 somewhat cryptic; perhaps it speaks to some novelty of the analysis in Section 3, in which case this should be clarified.\n\nUnbiased watermarks work best for high entropy text; small models like gpt2/opt-1.3b tend to produce high-entropy text. It would be informative to see whether change-point detection remains practical for the text generated by larger models (e.g., Mistral, LLaMA).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review our work. We greatly appreciate your positive feedback. We provide a detailed response to each of your comments below.\n\n*1. This paper could be criticized for novelty, in the sense that it mostly applies standard tools from the change point detection literature to watermarking. I find Remark 2 somewhat cryptic; perhaps it speaks to some novelty of the analysis in Section 3, in which case this should be clarified.*\n\n**Ans:** Thanks for the comment. We will update Remark 2 to highlight the novelty of using the change point detection technique in the current context. Specifically, we shall emphasize the following points:\n- Rather than testing the homogeneity of the original data sequence (which is the setup typically considered in the change point literature), we convert the string into a sequence of p-values, based on which we conduct the change-point analysis;\n- In the classical change point literature, the observations (in our case, the p-values) within the same segment are assumed to follow the same distribution. In contrast, for the watermark detection problem, the p-values from the watermarked segment could follow different distributions, adding a layer of difficulty to the analysis;\n- The p-value sequence is dependent (where the strength of dependence is controlled by $B$), making our setup very different from the one in Carlstein (1988), which assumed the underlying data sequence to be independent;\n- The technical tool used in our analysis must account for the particular dependence structure within the p-value sequence, which is also different from existing works in the literature.\n\n*2. Unbiased watermarks work best for high entropy text; small models like gpt2/opt-1.3b tend to produce high-entropy text. It would be informative to see whether change-point detection remains practical for the text generated by larger models (e.g., Mistral, LLaMA).*\n\n**Ans:** Following your suggestion, we have conducted simulation tests using the Llama model, specifically the Meta-Llama-3-8B, which was released on April 18, 2024, and has 8 billion parameters. Our experiments were carried out under three different settings outlined in the main text: no change points, one change point, and four change points. The results, displayed in the attached PDF file Figure 1, demonstrate the robust performance of the proposed method under the Meta-Llama-3-8B model. We found that the p-values are accurate (e.g., small for watermarked segments), and this precision in the p-value calculation leads to accurate change point detection, confirming the effectiveness of the proposed method in handling complex LLM.\n\n*3. Why was block size $B=20$ chosen? Is it important that $B = B'$? How do these and other parameters affect the performance of SeedBS in this setting?*\n\n**Ans:** Thank you for your comment. Following your suggestion, we investigate the impact of the window size $B$ on the proposed method. In particular, we focus on the EMS method in simulation Setting 4 of the main text, using the Meta-Llama-3-8B model.\n\nTo study the impact of the window size $B$, we fix $T=999$ and $B' = 20$, and vary the value of $B$ in the set \\{10, 20, 30, 40, 50\\}. The results for different choices of $B$ when $T=999$ are shown below:\n\n| $B$ | 10 | 20 | 30 | 40 | 50 |\n|-------|----|----|----|----|----|\n| rand index | 0.8808 | 0.9429 |  0.9641 | 0.9570 |0.9243 |\n\nIt is crucial to select an appropriate value for $B$. If $B$ is too small, the corresponding window may not contain enough data to reliably detect watermarks, as longer strings generally make the watermark more detectable. Conversely, if $B$ is excessively large, it might prematurely shift the detected change point locations, thus reducing the rand index.\n\nThe trade-off in the choice of window size is recognized in the time series literature. For instance, a common recommendation for the window size in time series literature is to set $B=Cn^{1/3}$, where $n$ is the sample size, as seen in Corollary 1 of  Lahiri (1999). Based on our experience, setting $B = \\lfloor 3n^{1/3} \\rfloor$ (for example, when $n=500$, $B=23$) often results in good finite sample performance. A more thorough investigation of the choice of $B$ is deferred to future research.\n\nOur experimental results indicate that setting $B = B'$ is unnecessary. In practice, the sequence of $p$-values is $B$-dependent, with $p_i$ and $p_j$ being independent only if $|i - j| > B$. Consequently, we recommend using $B' = B$ to ensure that the block bootstrap adequately captures this dependence.\n\n###  References\n[1] Edward Carlstein. Nonparametric change-point estimation. The Annals of Statistics, 16(1):188–197, 1988\\\n[2] Soumendra N Lahiri. Theoretical comparisons of block bootstrap methods. Annals of Statistics, pages 386–404, 1999", "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": "bM7lOsmF6l", "reviewer": "Reviewer_XFsq", "summary": "This paper presents a statistical method for detecting and segmenting watermarked text generated by large language models (LLMs). The key contributions are:\n\nA rigorous analysis of Type I and Type II errors for a randomization test to detect the presence of watermarks in generated text. The authors apply their findings to two specific watermarking schemes: inverse transform sampling and exponential minimum sampling (Gumbel watermark).\nA novel statistical approach to segment text into watermarked and non-watermarked substrings. This method is based on change point detection techniques and is designed to handle scenarios where users may modify LLM-generated text through insertions, deletions, or substitutions.\nTheoretical analysis of the proposed segmentation method, including convergence rates for estimated change point locations.\nEmpirical evaluation of the proposed methods using texts generated by GPT-2 and OPT-1.3b models, with prompts from Google's C4 dataset. The experiments demonstrate the effectiveness of the approach under various modification scenarios.\n\nThe paper provides a theoretical foundation for watermark detection and segmentation in LLM-generated text, addressing an important problem in the context of distinguishing between human-written and machine-generated content.", "questions": "1. I am interested in the number of $T$ selected for watermarked text detection. Is there a solution for balancing performance and speed?", "limitations": "The authors have adequately addressed the limitations in the checklist.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "Originality:\n\nA novel statistical approach for watermarked text segmentation, is very interesting and useful.\n\nCreative application of change point detection to watermarking.\n\nQuality:\n\nRigorous theoretical analysis with proofs.\n\nThorough experimental design across multiple scenarios.\n\nClarity:\n\nWell-structured paper with clear progression.\n\nReadable mathematical concepts with intuitive explanations.\n\nSignificance:\n\nAddresses key problem of distinguishing AI-generated text in \"segmented text\" scenario.", "weaknesses": "Weaknesses:\n\nLimited model diversity: Experiments focus on GPT-2 and OPT-1.3b. Testing on larger language models would strengthen findings.\n\nWhile I appreciate the intent of this paper, the attack scenario set up in this article is still rather simple. In a real-world application,\n1) Users may make changes to the text by means of cross-lingual attack and GPT rewrite, etc., the authors did not analyze these scenarios.\n2) The precautions users may take to prevent possible watermarking are more complex. I would like to see more change points and performance ratings of methods for scenarios with different segment lengths.\n\nIn addition, better visualization for selected scenarios could better reflect the value of the accuracy of the proposed methodology.\n\nIt should be noted that I will raise my score when I see appropriate rebuttals.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your comments and we provide a point-by-point response to each of your comments below.\n\n*1. Limited model diversity [...] larger language models would strengthen findings.*\n\n**Ans:** Thanks for the comment. We conducted simulation tests using the Llama model, specifically the Meta-Llama-3-8B, which was released on April 18, 2024, and has 8 billion parameters. Our experiments were carried out under three different settings outlined in the main text: no change points, one change point, and four change points. The results, displayed in the attached PDF file Figure 1, demonstrate the robust performance of the proposed method under the Meta-Llama-3-8B model. We found that the p-values are accurate (e.g., small for watermarked segments), and this precision in the p-value calculation leads to accurate change point detection, confirming the effectiveness of the proposed method in handling complex LLM.\n\n*2. Feedback on Scenario Simplicity: While I appreciate the intent of this paper, the attack scenario set up in this article is still rather simple. In a real-world application, users may make changes to the text by means of cross-lingual attack and GPT rewrite, etc.; the authors did not analyze these scenarios.*\n\n**Ans:** Thank you for the feedback. During the response period, we tested various realistic scenarios, including cross-lingual attacks and rewriting using different Language Models (LLMs).\n\nRegarding the use of different LLMs for rewriting, we would like to note the following: If the entire text is rewritten using another LLM and the associated key is provided, we can use the method outlined in the paper to detect watermarks. However, if the key from the alternate LLM used for rewriting is not provided, it becomes difficult to detect such an attack. In a situation where a portion of the text is rewritten using a different LLM (for example, LLM-B compared to the original LLM, denoted as LLM-A used for generating the watermarked text) and the corresponding watermark key is provided, we can address the issue by applying the change-point detection algorithm separately to each of the LLMs and then consolidating the identified change points.\n\nTo test the rewrite attack, we first generated 300 tokens using Meta-Llama-3-8B (LLM-A), with the initial 100 tokens unwatermarked and the subsequent 200 tokens watermarked. Subsequently, the openai-community/gpt2 (LLM-B) revised the text corresponding to the final 100 tokens generated by LLM-A. We then employed the proposed change point detection method using LLM-A and LLM-B, separately. The results, illustrated in Figure 3 of the attached PDF, indicate that LLM-A exhibits a p-value near zero between tokens $100$ and $200$, while LLM-B shows a near-zero p-value between tokens $200$ and $300$. This evidence supports the efficacy of the proposed method in distinguishing text generated by two different LLMs.\n\nWe also conducted tests for cross-lingual attacks. Under Setting 4 detailed in the main text, we translated the paragraph into French and then back into English. The results are shown in Figure 4 of the attached PDF. The change points are easily detected before translation. However, after translation, the sequence of $p$-values becomes noisy, which significantly degrades the performance of change point detection. The noisiness of the $p$-values is due to potential alterations in word order or logic during the translation process.\n\n*3. Precautions Against Watermarking: [...] more change points and performance ratings of methods for scenarios with different segment lengths.*\n\n**Ans:** Thanks for the comments. We focus on the Meta-Llama-3-8B model to conduct more realistic simulation studies. Specifically, we increase the number of change points to $4$, $8$, and $12$ and vary the segment lengths accordingly. The results are presented in the attached PDF file Figure 2. For the scenarios with $4$ and $8$ change points, the proposed method successfully identifies all change points. As the number of change points increases, the change point detection problem becomes much more challenging. In the scenario with 12 change points, our method was able to identify 9 of them, showing its robust performance in handling more difficult situations.\n\n*4. Visualization Enhancement: In addition, better visualization for selected scenarios [...].*\n\n**Ans:** Thank you for your comment. To demonstrate our approach more concretely, we will provide an example of segmenting a specific string. Due to the space constraint, we have relocated the detailed text to Figure 5 in the attached PDF. In this figure, true watermarked text highlighted in green and detected watermarked text highlighted in blue.\n\n*5. Watermarked Text Detection: I am interested in the number of $T$ selected for watermarked text detection. Is there a solution for balancing performance and speed?*\n\n**Ans:** In theory, a larger $T$ is preferable as it leads to a more accurate calculation of the p-values. Following the literature on permutation-based tests (Marozzi, 2004), we suggest using 500-1000 permutations. We investigate the impact of the number of permutations $T$ on the proposed method, where we focus on the EMS method in simulation Setting 4, using the Meta-Llama-3-8B model. We set $B$ to 20 and consider $T\\in \\{99, 249, 499, 749, 999\\}$. The results are summarized below. As expected, the computation time increases almost linearly with the number of permutations $T$. We also note that the rand index remains consistent across different values of $T$, indicating a level of stability in our method.\n\n| $T$  | 99   | 249   | 499   | 749   | 999   |\n|------|------|-------|-------|-------|-------|\n| time in hours | 3.41 | 7.33  | 11.47 | 18.47 | 24.94 |\n| rand index    | 0.937 | 0.9404 | 0.9326 | 0.9348 | 0.9354 |\n\n###  References\n[1] Marco Marozzi. Some remarks about the number of permutations one should consider to perform a permutation test. Statistica, 64(1):193–201, 2004.", "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": "e3yvToMagM", "reviewer": "Reviewer_LBBH", "summary": "The work makes two contributions: (1) A randomized-based test, including a theoretical analysis of a substring-based watermark detection for two popular distribution-preserving watermarks. The key idea is similar to the base detection methods in their respective base papers but shows some additional theoretical properties (e.g., convergence). (2) Based on the substring-based detection, an approach to segment the given text into both watermarked and non-watermarked sections by detecting points of change in the observed p-values on substrings. The proposed algorithm SeedBS-NOT is then evaluated in 4 settings and 2 models.", "questions": "- How does the proposed method fare on more realistic text scenarios with shorter sections of watermarked / non-watermarked texts?\n- Can you provide a practical ablation over B (both w.r.t. runtime and effectiveness of the detection)?\n- Can you provide some experiments on larger and more realistic models (As well as the costs associated with running tests on such models).\n- Do you have any ideas about the effect of repeating key-patterns (which happens in practice) on your analysis?", "limitations": "The paper addresses several limitations; however, as pointed out above, I think some more limitations of the current setting could be discussed.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The idea of differentiating between sections of text that are watermarked and the ones that are not is interesting and has many potential downstream applications (such as adaptive attacks). \n- The theoretical analysis seems sound and does provide asymptotical guarantees that are new to the reviewer.\n- In the evaluations, the change-points of watermarked and not-watermarked texts can be detected quite accurately.", "weaknesses": "- The method seems to rely heavily on the hyper-parameter B (substring block size) and would most likely profit from some ablation on the parameter in practical settings.\n- The introduced scenarios for evaluation feel very clean, with large gaps between change points. However, I do not believe this accurately reflects real-world perturbations in the watermarked text.\n- Similarly the evaluation is only one two quite oudated LLMs (gpt2 being 5 years old now) despite the paper claiming that the segementation algorithms performance \"depends [on]  the language model with which the texts are generated\". Given this I believe an extended evaluation on more realistic models (that people would actually watermark) is important to evaluate the empirical effectiveness of the approach (i.e., at least 7B -  the reviewer found in their own work that there can be significant changes between larger models when it comes to watermark detection).\n\n## Minor \n\n- The methods and analysis is restricted two specific types of watermarks, which are generally praised for their theoretical guarantees, but arguably not as popular as red-green type schemes for which such segmentations would also be interesting. Notably practical implementations of these schemes can, e.g., contain repeating key patterns whose effect would be interesting to investigate/mention in this context.\n- Given this the results too me only feel partially encouraging in that we (despite theoretical asymptotic error bounds) do observe some false-positives in some of the settings (which qualitatively is confirmed by, e.g., Fig. B.1 where some of the results tend to be quite noisy especially for ITS(L)).\n\n## Typos/Nits\n\n- L.27 Large Language Model\n- L.291 400 -> 500. According to the plots and the fact that there are 4 change-points it should be 500 tokens (same in L. 579)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review our work. We will provide a detailed response to each of your comments below.\n\n### **Weaknesses and Questions:**\n\n*1. The method seems to rely heavily on the hyper-parameter $B$ and would most likely profit from some ablation on the parameter in practical settings. Can you provide a practical ablation over $B$?*\n\n**Ans:** Thanks for the comment. We investigate the impact of the window size $B$ on the proposed method. In particular, we focus on the EMS method in simulation Setting 4 of the main text, using the Meta-Llama-3-8B model. To study the impact of the window size $B$, we fix $T=999$ and vary the value of $B$ in the set $\\{10, 20, 30, 40, 50\\}$. Below are the computation times and the rand index value for each setting, with a higher rand index indicating better performance.\n\n   | $B$ | 10 | 20 | 30 | 40 | 50 |\n   |-------|----|----|----|----|----|\n   | rand index | 0.8808 | 0.9429 | 0.9641 | 0.9570 | 0.9243 |\n   | time in hours | 28.77 | 24.94 | 24.37 | 26.24 | 25.97 |\n\nIt is crucial to select an appropriate value for $B$. If $B$ is too small, the corresponding window may not contain enough data to reliably detect watermarks, as longer strings generally make the watermark more detectable. Conversely, if $B$ is excessively large, it might prematurely shift the detected change point locations, thus reducing the rand index. Please refer to Author Rebuttal point 2 for one example.\n\nThe trade-off in the choice of window size is recognized in the time series literature. For instance, a common recommendation for the window size in time series literature is to set $B=Cn^{1/3}$, where $n$ is the sample size, as seen in Corollary 1 of Lahiri (1999). Based on our experience, setting $B = \\lfloor 3n^{1/3} \\rfloor$ often results in good finite sample performance. A more thorough investigation of the choice of $B$ is deferred to future research. Additionally, The selection of $B$ does not significantly affect the time.\n\n*2. The introduced scenarios for evaluation feel very clean, with large gaps between change points. However, I do not believe this accurately reflects real-world perturbations in the watermarked text. How does the proposed method fare on more realistic text scenarios with shorter sections of watermarked / non-watermarked texts?*\n\n**Ans:** Thank you for your comment. We focus on the Meta-Llama-3-8B model to conduct more realistic simulation studies. Specifically, we increase the number of change points to 4, 8, and 12 and vary the segment lengths accordingly. The results are presented in the attached pdf file Figure 2. For scenarios with 4 and 8 change points, the proposed method successfully identifies all change points. As the number of change points increases, the change point detection problem becomes much more challenging. In the scenario with 12 change points, our method was able to identify 9 of them, showing its robust performance in handling more difficult situations. Generally, the difficulty of a change point detection problem depends on the distance between the change points and the magnitudes of the changes, as indicated by the theoretical results in Proposition 1.\n\n*3. I believe an extended evaluation on more realistic models is important to evaluate the empirical effectiveness of the approach. Can you provide some experiments on larger and more realistic models?*\n\n**Ans:** Thanks for the comment. We conducted simulation tests using the Llama model, specifically the Meta-Llama-3-8B, which was released on April 18, 2024, and has 8 billion parameters. Our experiments were carried out under three different settings outlined in the main text: no change points, one change point, and four change points. The results, displayed in the attached pdf file Figure 1, demonstrate the robust performance of the proposed method under the Meta-Llama-3-8B model. We found that the p-values are accurate (e.g., small for watermarked segments), and this precision in the p-value calculation leads to accurate change point detection, confirming the effectiveness of the proposed method in handling complex LLM.\n\n### **Minor**\n\n*1. The methods [...] on your analysis?*\n\n**Ans:** Thank you for the excellent suggestion! We can indeed combine the red-green type scheme with the proposed change point detection algorithm, as outlined below. The proposed method operates in two stages. First, a watermark detection method is used to produce a sequence of p-values. These p-values are then utilized for change point detection. Therefore, any watermark detection method that produces a sequence of p-values can be integrated into our framework to differentiate between watermarked and non-watermarked text. As red-green type schemes can generate p-values, they can be included in the proposed framework to segment watermarked texts. We are currently exploring this extension and will report the numerical results in the revision.\n\n*2. Given this [...] the settings.*\n\n**Ans:** The false discoveries are partially due to the low detection power (i.e., large p-values for watermarked segments). In reality, the detection power depends crucially on the text itself (such as its length and entropy). The text's characteristics can determine how challenging it is to detect the watermarks. Our theory suggests that the detection power will only approach one when the quantity defined in Equation (4) (related to the text's entropy) approaches infinity. For a given text, if this quantity is small, it would become difficult to find the watermark.\n\n### **Typos/Nits**\n\n*1. L.27 Large Language Model*\n\n**Ans:** Thanks for catching this. It will be fixed.\n\n*2. L.291 400 -> 500. [...] (same in L. 579)*\n\n**Ans:** This is not a typo. The total number of tokens is indeed 500, where we first generate 400 tokens with watermark, and then insert an additional 100 tokens.\n\n###  References\n[1] Soumendra N Lahiri. Theoretical comparisons of block bootstrap methods. Annals of Statistics, pages 386–404, 1999", "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:
First and foremost, we express our sincere gratitude to the three reviewers for their invaluable feedback, which has helped us improve the quality of our manuscript. We will revise our manuscript and the supplement, taking all the reviewers' comments into consideration. Before providing point-by-point responses, we would like to summarize the major changes we have made in order to address the reviewers' main concerns.

### 1. **Larger and more realistic/updated LLMs**
We conducted simulation tests using the Llama model, specifically the Meta-Llama-3-8B, which was released on April 18, 2024, and has 8 billion parameters. Our experiments were carried out under three different settings outlined in the main text: no change points, one change point, and four change points. The results, displayed in the attached pdf file Figure 1, demonstrate the robust performance of the proposed method under the Meta-Llama-3-8B model. We found that the p-values are accurate (e.g., small for watermarked segments), and this precision in the p-value calculation leads to accurate change point detection, confirming the effectiveness of the proposed method in handling complex LLM.

### 2. **More realistic evaluation scenarios**
We focus on the Meta-Llama-3-8B model to conduct more realistic simulation studies. Specifically, we increase the number of change points to 4, 8, and 12 and vary the segment lengths accordingly. The results are presented in the attached pdf file Figure 2. For scenarios with 4 and 8 change points, the proposed method successfully identifies all change points. As the number of change points increases, the change point detection problem becomes much more challenging. In the scenario with 12 change points, our method was able to identify 9 of them, showing its robust performance in handling more difficult situations. Generally, the difficulty of a change point detection problem depends on the distance between the change points and the magnitudes of the changes, as indicated by the theoretical results in Proposition 1.

### 3. **Choices of the tuning parameters**
We investigate the impact of the window size $B$ and the number of permutations $T$ on the proposed method. In particular, we focus on the EMS method in simulation Setting 4 of the main text, using the Meta-Llama-3-8B model.

First, to study the impact of the window size $B$, we fix $T=999$ and vary the value of $B$ in the set \{10, 20, 30, 40, 50\}. The rand index values for each setting are outlined below, with a higher rand index indicating better performance:

| $B$  | 10     | 20     | 30     | 40     | 50     |
|------|--------|--------|--------|--------|--------|
| rand index | 0.8808 | 0.9429 | 0.9641 | 0.9570 | 0.9243 |

In practice, it is crucial to select an appropriate value for $B$. If $B$ is too small, the corresponding window may not contain enough data to reliably detect watermarks, as longer strings generally make the watermark more detectable. Conversely, if $B$ is excessively large, it might shift the detected change point locations, thus reducing the rand index. For instance, let us consider a scenario with 200 tokens where the first 100 tokens are non-watermarked, and the subsequent 100 are watermarked, with the true change point at index 101. Assuming our detection test is valid in size and highly effective in detection power, then it will yield a p-value uniformly distributed over $[0,1]$ over a non-watermarked window and a p-value around zero over a window containing watermarked tokens. When $B = 50$, the window beginning at the 76th token contains one watermarked token, which can lead to a small p-value and thus erroneously indicate a watermark from the 76th token onwards. In contrast, if $B = 20$, the window starting at the 91st token will contain the first watermarked token, leading to a more minor error in identifying the change point location. The above phenomenon is the so-called edge effect, which will diminish as $B$ gets smaller.

The trade-off in the choice of window size is well recognized in the time series literature. For instance, a common recommendation for the window size in time series literature is to set $B=Cn^{1/3}$, where $n$ is the sample size, as seen in Corollary 1 of  Lahiri (1999). Based on our experience, setting $B = \lfloor 3n^{1/3} \rfloor$ (for example, when $n=500$, $B=23$) often results in good finite sample performance. A more thorough investigation of the choice of $B$ is deferred to future research.

We next examine how our method is affected by the choice of the number of permutations $T$. The results are summarized below, including the rand index value and computation times for each setting. As expected, the computation time increases almost linearly with the number of permutations $T$. We also note that the rand index remains consistent across different values of $T$, indicating a level of stability in our method.

| $T$  | 99   | 249   | 499   | 749   | 999   |
|------|------|-------|-------|-------|-------|
| time in hours | 3.41 | 7.33  | 11.47 | 18.47 | 24.94 |
| rand index    | 0.937 | 0.9404 | 0.9326 | 0.9348 | 0.9354 |

###  References
[1] Soumendra N Lahiri. Theoretical comparisons of block bootstrap methods. Annals of Statistics, pages 386–404, 1999

Meta-review: This paper presents a statistical method for detecting and segmenting watermarked and unwatermarked text generated by large language models (LLMs). 

Contributions and Strengths:
1. The paper presents a theoretical analysis of Type I and Type II errors for a randomization test to detect the presence of watermarks in generated text. They also examined two watermarking methods. 
2. The paper proposes a statistical detection method to segment text into watermarked and non-watermarked text. 
3. The paper provides a theoretical analysis of the proposed segmentation method. 

Weakness: 
1. The experiments are a bit weak. They just studied GPT-2 and OPT1.3B models, which are quite old and small. 
2. The method heavily relies on the hyperparameter B. 

Overall, the paper makes an important study on LLM watermarking and would be beneficial to the community.
Decision: Accept (poster)