Segmenting Watermarked Texts From Language Models

Authors: xingchi  li
guanxun  li
xianyang  zhang
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-13 22:33:15

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.

Main paper: 
 introduction: 
 With the increasing use of large language models in recent years, it has become essential to differentiate 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-generated texts, even for humans. However, it is crucial to distinguish between human-produced texts and machine-produced texts 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.Watermarking is a principled method for embedding nearly unnoticeable statistical signals into text generated by LLMs, enabling provable detection of LLM-generated content from its human-written counterpart. This work focuses on a 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 a 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 non-watermarked sub-strings. In particular, we divide the texts into a sequence of moving sub-strings with a pre-determined 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, we examine if there are structural breaks in the underlying distributions. For non-watermarked sub-strings, the p-values are expected to be uniformly distributed over [0, 1], while for watermarked sub-strings, the corresponding p-values are 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 I 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 C4 dataset, followed by different modifications/attacks that can introduce change points in the text.Digital watermarking is a field that focuses on embedding a signal in a medium, such as an image or text, and detecting it using an algorithm. Early watermarking schemes for natural language processing-generated 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 [2021] and Munyer and Zhong [2023] proposed schemes that use machine learning models in the watermarking algorithm. These schemes take a passage of text and use a 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 et al. [2023] . In particular, Kirchenbauer et al. [2023a] introduced a "red-green 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. [2024] , Liu and Bu [2024] , and Zhao et al. [2023] . 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 an 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. [2023] proposed an inverse transform watermarking method that can be made robust against potential random edits. Other unbiased watermarks in this fast-growing line of research include Zhao et al. [2024] , Fernandez et al. [2023] , Hu et al. [2023] , 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 et 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 a 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 a 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 1-2. We apply these results to the recently proposed inverse transform watermark and Gumbel watermark schemes; see Corollary 1.(b) We develop a systematic statistical method to segment texts into watermarked and nonwatermarked 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 LLMs.2 Problem setup 
watermarked text generation: 
 Denote by V the vocabulary (a discrete set), and let P be an autoregressive LLM which maps a string y -n0:t-1 = y -n0 y -n0+1 • • • y t-1 ∈ V t+n0 to a distribution over the vocabulary, with p(•|y -n0:t-1 ) being the distribution of the next token y t . Here y -n0:0 denotes the prompt provided by the user. Set V = |V| be the vocabulary size, and let ξ 1:t = ξ 1 ξ 2 • • • ξ t be a watermark key sequence with ξ i ∈ Ξ for each i, where Ξ is a general space. Given a prompt sent from a third-party user, the LLM provider calls a generator to autoregressitvely generate text from an LLM using a decoder function Γ, which maps ξ t and a distribution p t over the next token to a value in V. The watermarking scheme should preserve the original text distribution, i.e., P (Γ(ξ t , p t ) = y) = p t (y). A watermark text generation algorithm recursively generates a string y 1:n byy i = Γ(ξ i , p(•|y -n0:i-1 )), 1 ≤ i ≤ n,where n is the number of tokens in the text y 1:n generated by the LLM, and ξ i 's are assumed to be independently generated from some distribution ν over Ξ. In other words, given p(•|y -n0:i-1 ), y i is completely determined by ξ i and y -n0:i-1 .For ease of presentation, we associate each token in the vocabulary with a unique index from [V ] := {1, 2, . . . , V }, and we remark that the generator should be invariant to this assignment. Example 1 (Inverse transform sampling). In this example, we describe a watermarked text generation method developed in Kuditipudi et al. [2023] and discuss an alternative formulation of their approach. Write µ i (k) = p(k|y -n0:i-1 ) for 1 ≤ k ≤ V and 1 ≤ i ≤ n. To generate the ith token, we consider a permutation π i on [V ] and u i ∼ Unif[0, 1] (which denotes the uniform distribution over [0, 1]), which jointly act as the key ξ i . LetΓ((π i , u i ), µ i ) = π -1 i (min{π i (l) : µ i (j : π i (j) ≤ π i (l)) ≥ u i }). We note that Γ((π i , u i ), µ i ) = k if min{π i (l) : µ i (j : π i (j) ≤ π i (l)) ≥ u i } = π i (k), which implies that µ i (j : π i (j) ≤ π i (k)) ≥ u i > µ i (j : π i (j) < π i (k)). As the length of this interval is µ i (k), P (Γ((π i , u i ), µ i ) = k) = µ i (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 I 1 , . . . , I V , we can order them in such a way that each interval I i is adjacent to its immediate right neighbor I i+1 . Now let I(k; i)'s be V intervals with the length |I(k; i)| = p(k|y -n0:i-1 ) for 1 ≤ k ≤ V . Given the permutation π i , we can order the V intervals through π i , i.e., {I πi(k) (k; i) :k = 1, 2, . . . , V }. Define ξ ik = I{u i ∈ I πi(k) (k; i)} and set y i = k if ξ ik = 1. Clearly P (y i = k) = P (ξ ik = 1) = P (u i ∈ I πi(k) (k; i)) = p(k|y -n0:i-1 ).Now, for a string y 1:n (with the same length as the key) that is possibly watermarked, Kuditipudi et al. [2023] suggest the following metric to quantify the dependence between the watermark key and the string:EQUATION)Observe that if y i is generated using the above scheme with the key ξ i = (π i , u i ), then u i and π i ( y i ) are positively correlated. Thus, a large value of M indicates that y 1:n is potentially watermarked.Example 2 (Exponential minimum sampling). We describe another watermarking technique proposed in Aaronson [2023] . To generate each token of a text, we first sampleξ ik ∼ Unif[0, 1] independently for 1 ≤ k ≤ V . Let y i = arg max 1≤k≤V log(ξ ik ) p(k|y -n0:i-1 ) = arg min 1≤k≤V -log(ξ ik ) p(k|y -n0:i-1 ) = arg min 1≤k≤V E ik ,where E ik := -log(ξ ik )/p(k|y -n0:i-1 ) ∼ Exp(p(k|y -n0:i-1 )) with Exp(a) denoting an exponential 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 ) = E[1 -exp(-aY )] = a/(a + b).Using (i) and (ii), it is straightforward to verify thatP (y i = k) = P E ik < min j̸ =k E ij = p(k|y -n0:i-1 ).Hence, this generation scheme preserves the original text distribution.Aaronson [2023] proposed to measure the dependence between a string y 1:n and the key sequence ξ 1:n using the metricEQUATION)The idea behind the definition of this function is that if y i was generated using the key ξ i , then ξ i, yi tends to have a higher value than the other components of ξ i . Therefore, a larger value of the metric indicates that the string y 1:n is more likely to be watermarked.We now consider the detection problem, which involves determining whether a given text is watermarked or not. Consider the case where a string y 1:m is published by the third-party user and a key sequence ξ 1:n is provided to a detector. The detector calls a detection method to test H 0 : y 1:m is not watermarked versus H a : y 1:m is watermarked, by computing a p-value with respect to a test statistic ϕ(ξ 1:n , y 1:m ). 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 ξ 1:n , which we refer to as y 1:n . To account for this difference, we can use a transformation function E that takes y 1:n as the input and produces the published text y 1:m as the output, i.e., y 1:m = E(y 1: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 y 1:m and the key sequence ξ 1:n . Throughout our discussions, we will assume that a large value of ϕ provides evidence against the null hypothesis (e.g., stronger dependence between y 1:m and ξ 1:n ). To obtain the p-value, we consider a randomization test. In particular, we generate ξ (t)i ∼ ν independently over 1 ≤ i ≤ n and 1 ≤ t ≤ T , and ξ (t) i s are independent with y 1:m . Then the randomization-based p-value is given byp T = 1 T + 1 1 + T t=1 1{ϕ(ξ 1:n , y 1:m ) ≤ ϕ(ξ (t) 1:n , y 1:m )} .Theorem 1. For the randomization test, we have the following results.(i) Under the null, P (p T ≤ α) = ⌊(T + 1)α⌋/(T + 1) ≤ α, where ⌊a⌋ denotes the greatest integer that is less than or equal to a;(ii) Suppose the following three conditions hold:(a) max{Var(ϕ(ξ 1:n , y 1:m )|F m ), Var(ϕ(ξ ′ 1:n , y 1:m )|F m )} ≤ C v /n with C v > 0; (b) E[ϕ(ξ ′ 1:n , y 1:m )|F m ] = O(n -1/2 ); (c) lim n→∞ √ nE[ϕ(ξ 1:n , y 1:m )|F m ] = ∞.Here F m = [y -n0:0 , y 1:m ] and ξ ′ 1:n is a key sequence generated in the same way as ξ 1:n but is independent of y 1:m . Given any ϵ > 0, when T > 2/ϵ -1,EQUATIONas n → +∞, where C 1 > 0.We now apply the results in Theorem 1 to Examples 1-2 with m = n and ϕ(ξ 1:n , y 1:n ) = M(ξ 1:n , y 1:n ) for M defined in (1) and (2).Corollary 1. If y 1:n = y 1:n andEQUATIONthen Conditions (a)-(c) in Theorem 1 are satisfied for Examples 1-2. Consequently, the power of the randomization test converges to 1 in these examples as T → +∞.However, as the published text can be modified, it is not expected that every token in y 1:m will be related to the key sequence. Instead, we expect certain sub-strings of y 1:m to be correlated with the key sequence under the alternative hypothesis H a . To measure the dependence, we use a scanning method that looks at every segment/sub-string of y 1:m and a segment of ξ 1:n with the same length B. We use a measure M(ξ a:a+B-1 , y b:b+B-1 ) to quantify the dependence between ξ a:a+B-1 and y b:b+B-1 , chosen based on the watermarked text generation method described above. Given M and the block size B, we can define the maximum test statistic asϕ(ξ 1:n , y 1:m ) = max 1≤a≤n-B+1 max 1≤b≤m-B+1M(ξ a:a+B-1 , y b:b+B-1 ).(5)Theorem 2. Consider the maximum statistic defined in (5), where the dependence measure takes the form of M(ξ a:a+B-1 , y b:b+B-1 ) = B -1 B-1 i=0 h i (ξ a+i , y b+i ) and h i s are independent conditional on [ y 1:m , y -n0:n ]. Under the setting of Example 1, max i |h i | ≤ 1/4. In this case, suppose 3 Sub-string identificationEQUATIONIn this section, we aim to address the following question, which seems less explored in the existing literature: given that the global null hypothesis H 0 is rejected, how can we identify the sub-strings from the modified text y 1:m that are machine-generated?To describe the setup, we suppose the text published by the third-party user has the following structure:EQUATIONin which case the sub-strings y τ1+1 • • • y τ2 and y τ3+1 • • • y τ4 are watermarked. We emphasize that the orders of the watermarked and non-watermarked sub-strings can be arbitrary and do not affect our method described below. The goal here is to separate the text into watermarked and nonwatermarked sub-strings accurately. Our key insight to tackling this problem is translating it into a change point detection problem. To describe our method, we define a sequence of moving windowsI i = [(i -B/2) ∨ 1, (i + B/2) ∧ m]with B being the window size which is assumed to be an even number (for the ease of presentation) and 1 ≤ i ≤ m. For each sub-string, we define a randomization-based p-value given byEQUATIONwhere we let ϕ(ξ1:n , y Ii ) = max 1≤k≤n M(ξ J k , y Ii ) with J k = [(k -B/2) ∨ 1, (k + B/2) ∧ n].We have now transformed the text into a sequence of p-values: p 1 , . . . , p m . 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 non-watermarked (or vice versa). Then, we can identify the change point location throughEQUATIONwhere F a:b (t) denotes the empirical cumulative distribution function (cdf) of {p i } b i=a . We shall use the block bootstrap-based approach to determine if τ is statistically significant. Note that conditional on F m , the p-value sequence is B-dependent in the sense that p i and p j are independent only if |i -j| > B. Hence, the usual bootstrap or permutation methods for independent data may not 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 al., 1992] . Given a block size, say B ′ , we create m -B ′ + 1 blocks given by {p i , . . . , p i+B ′ -1 } for 1 ≤ i ≤ m -B ′ + 1. We randomly sample m/B ′ (assuming that m/B ′ is an integer for simplicity) blocks with replacement and paste them together. Denote the resulting resampled p-values by p * 1 , . . . , p * m . We then compute F * a,b (t) based on the bootstrapped p-values and defineS * 1:m (τ ) = sup t∈[0,1] τ (m -τ ) m 3/2 |F * 1:τ (t) -F * τ +1:m (t)|.Repeat this procedure T ′ times and denote the statistics by S * ,(t)1:m (τ ) for t = 1, 2, . . . , T ′ . Define the corresponding bootstrap-based p-value asEQUATION)We claim that there is a statistically significant change point if pT ′ ≤ α. Remark 1. Alternatively, one can consider the Cramér-von Mises type statistic max τ C 1:m (τ ) with Consider the case where there is a single change point located at τ * . Without loss of generality, let us assume that before the change, the p-values are uniformly distributed, i.e., p 1 , . . . , p τ * ∼ F 0 with F 0 (t) = t (the cdf 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(FC 1:m (τ ) = 1 0 τ 2 (m -τ ) 2 m 3 |F 1:τ (t) -F τ +1:m (t)| 2 w(t)dt,0 , E[F τ * +1:m (t)]) > 0, where D(F 0 , E[F τ * +1:m (t)]) := sup t∈[0,1] |F 0 (t) -E[F τ * +1:m (t)]| is the Kolmogorov-Smirnov distance.In other words, the empirical cdf 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 max 1≤τ <m S 1:m (τ ) with S 1:m (τ ) defined in (9) for examining the existence of a change point. Proposition 1. Assuming that B → +∞ and B/m → 0, we havemax 1≤τ <m S 1:m (τ ) ≥ √ mγ * (1 -γ * )D(F 0 , E[F τ * +1:m (t)]) + o p (1) → +∞,where γ * = lim m→+∞ τ * /m ∈ (0, 1).Next, we shall establish the consistency of the change point estimator τ = arg max 1≤τ <m S 1:m (τ ).In particular, we obtain the following result, which establishes the convergence rate of the change point estimate. Theorem 3. Under the Assumptions in Proposition 1, we have|τ -τ * | = O p mB log(m/B) D(F 0 , E[F τ * +1:m (t)]).Remark 2. Our scenario differs from the traditional nonparametric change point detection problem in a few ways: (i) 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; (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 Carlstein [1988] , 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.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 of the simulation-based p-values from each sub-string. Therefore, a powerful watermark detection algorithm is essential for the segmentation procedure's success.Guidelines:• The answer NA means that the paper has no 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 a 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 on 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, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a 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 fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
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 a penalized cost function [Harchaoui and Lévy-Leduc, 2010 , Truong et al., 2020 , R. Killick and Eckley, 2012 , Li and Zhang, 2024 , Zhang and Dawn, 2023 ] and (ii) 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 Vostrikova [1981] , binary segmentation identifies a single change point in a dataset using a CUSUM-like procedure and then employs a divide-and-conquer approach to find additional change points within sub-segments until a stopping condition is 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., 2022] improve upon this by defining multiple segments to identify and aggregate potential change points. SeedBS additionally addresses the issue of overly long sub-segments in WBS that may contain several change points. SeedBS uses multiple layers of intervals, each with a 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-threshold (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 in Algorithm 1 below.Algorithm 1 SeedBS-NOT for change point detection in potentially partially watermarked texts Require: Sequence of p-values {p i } m i=1 , decay parameter a ∈ [1/2, 1) for SeedBS, threshold ζ for NOT. Ensure: Locations of the change points.DefineI 1 = (0, m]. ▷ Start of SeedBS for k ← 2, . . . , ⌈log 1/a m⌉ do Number of intervals in the k-th layer: n k = 2⌈(1/a) k-1 ⌉ -1. Length of intervals in the k-th layer: l k = ma k-1 . Shift of intervals in the k-th layer: s k = (m -l k )/(n k -1). k-th layer intervals: I k = n k i=1 {(⌊(i -1)s k ⌋, ⌈(i -1)s k + l k ⌉]}. end for Define all seeded intervals I = ⌈log 1/a m⌉ k=1 I k . ▷ End of SeedBS for i ← 1, . . . , |I| do ▷ Start of NOT Define the i-th interval I i = (r i , s i ]. Define S ri+1:si (τ ) := sup t∈[0,1] (τ -ri)(si-τ ) (si-ri) 3/2 |F ri+1:τ (t) -F τ +1:si (t)|. Let τi = arg max ri<τ ≤si S ri+1:si (τ ).Obtain pi through block bootstrap (10). Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? Answer: [Yes] Justification: In the main text, we formally state essential assumptions for our 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 crossreferenced. • All assumptions should be clearly stated or referenced in the statement of any theorems.• The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a 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 or supplemental material. • Theorems and Lemmas that the proof relies upon should be properly referenced. 
numerical experiments: 
 We conduct extensive real-data-based experiments following a similar empirical setting in Kirchenbauer 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 et al., 2020] . We utilized three LLMs, namely openai-community/gpt2 [Radford et al., 2019] , facebook/opt-1.3b [Zhang et al., 2022] and Meta-Llama-3-8B [AI@Meta, 2024], 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 (1).• ITSL: The inverse transform sampling method with the dependence measure defined in (B.2), which is based on the Levenshtein cost (B.1) with base alignment cost (B.3).• EMS: The exponential minimum sampling method with the dependence measure defined in (2).• EMSL: The exponential minimum sampling method with the dependence measure defined in (B.3), which is based on the Levenshtein cost (B.1) with base alignment cost (B.4).The details of the Levenshtein cost are deferred to Appendix B.1. For each of the experiment settings, 100 prompts were used to generate the watermarked text. We fix the length of text m = 500, the size of sliding window B = 20, and the block size used in the block bootstrap-based test B ′ = 20. Results for other choices of B are shown in Appendix C. In Algorithm 1, we set the decay parameter a = √ 2 and the minimum length of the intervals generated by SeedBS to be 50 such that the block bootstrapbased test is meaningful, and the threshold ζ ∈ {0.05, 0.01, 0.005, 0.001}. We present the results for openai-community/gpt2 in the main text and defer the results for facebook/opt-1.3b and Meta-Llama-3-8B to Appendix B.3 and Appendix B.4, respectively.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 1 (no change point): Generate 500 tokens with a watermark.The results for openai-community/gpt2 are showed in Figure 1 . 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 the sequence of p-values for the four methods. Most of the p-values are near 0. However, certain sub-strings have relatively high p-values 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. 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. In 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 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, respectively. • Setting 4 (insertion and substitution attacks): Generate 400 tokens with watermarks, substitute the token with indices ranging from 101 to 200 with 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, 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 by the true change points using the Rand index [Rand, 1971] . A higher Rand index indicates better performance of different methods.Figure 2 shows the Rand index for four methods in Settings 2-4 corresponding to different thresholds ζ. For each method, their performance in Settings 2-3 is better than that of Setting 4 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 two 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 on the quality of the obtained sequence of p-values. Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of 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 in 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 a 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 a novel architecture, describing the architecture fully might suffice, or if the contribution is 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 can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. Justification: We do not need to display the error bar in our experimental results; in other words, the experiment results don't involve an error bar. We do include boxplots as a way to show the performance of the algorithm. The statistical significance is obtained through bootstrap-based 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, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run 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 or 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 a 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 or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
discussions: 
 In this study, we have introduced a 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 a technique to partition the published text into watermarked and non-watermarked sub-strings by treating it as a 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. The performance of the segmentation algorithm depends crucially on the quality of the randomizationbased p-values from each sub-string. Intuitively, a more significant discrepancy between the p-value distributions under the null and alternative will lead to better segmentation results. Thus, a powerful watermark detection algorithm is crucial to the success of the segmentation procedure. Motivated by Condition (4), an interesting future direction is to develop an adaptive watermark generation and detection procedure where the LLM provider adaptively embeds the key according to NTP, and the detector uses a corresponding adaptive procedure to detect the watermark.Another interesting direction to explore is 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 a sequence of p-values and change points. Figuring out how to aggregate these results to separate different LLMs and user-modified texts would be an intriguing problem.Proof of Theorem 1.(i) For simplicity of notation, denote φ := ϕ(ξ 1:n , y 1:m ) and φ (t) := ϕ(ξ(t)1:n , y 1:m ) for t = 1, • • • , T . Under the null hypothesis, we know that ξ 1:n is independent of y 1:m , which implies that the pairs (ξ 1:n , y 1:m ), (ξ (1) 1:n , y 1:m ), . . . , (ξ (T ) 1:n , y 1:m ) follow the same distribution. Hence φ, φ (1) , . . . , φ (T ) are exchangeable. The exchangeability ensures that the rank of φ relative to {φ, φ (1) , . . . , φ (t) } is uniformly distributed. Denote the order statistics φ (1) ≤ • • • ≤ φ (T +1) . Then we haveP φ = φ (j) = 1 T + 1 , j = 1, . . . , T + 1.Hence, for j = 1, . . . , T + 1, we haveP p T ≤ j T + 1 = P φ ∈ φ (T +2-j) , . . . , φ (T +1) = j T + 1 , Then, we have P (p T ≤ α) = ⌊(T + 1)α⌋/(T + 1) ≤ α. (ii) Denote E ξ ′ := E[ϕ(ξ ′ 1:n , y 1:m |F m )]. By Chebyshev's inequality and Condition (a), we getP |ϕ(ξ ′ 1:n , y 1:m ) -E ξ ′ | ≥ ϵ/ √ n|F m ≤ Var(ϕ(ξ ′ 1:n , y 1:m )|F m ) ϵ 2 /n ≤ C v ϵ 2 , for all ϵ ≥ 0. Thus ϕ(ξ ′ 1:n , y 1:m ) -E ξ ′ = O p (n -1/2 ), which together with Condition (b) implies that ϕ(ξ ′ 1:n , y 1:m ) = O p (n -1/2 ) given F m .Denote the distribution of ϕ(ξ ′ 1:n , y 1:m ) conditional on F m by F , and the empirical distribution of {φ (t) } T t=0 by F T , where we set φ (0) = φ. Let q 1-α,T = φ (T +2-jα) with j α = ⌊(T + 1)α⌋. Note that F T (q 1-α,T ) = 1 -(j α -1)/(T + 1). Our test rejects the null whenever p T ≤ α, which is equivalent to rejecting the null if φ ≥ φ (T +2-jα) . By the Dvoretzky-Kiefer-Wolfowitz inequality, we haveP (|F T (q 1-α,T ) -F (q 1-α,T )| > ϵ|F m ) ≤ P (sup x |F T (x) -F (x)| > ϵ|F m ) ≤ C 1 exp(-2T ϵ 2 )for some constant C 1 > 0, which implies that with probability greater than 1 -C 1 exp(-2T ϵ 2 ), F (q 1-α,T ) < 1 -(j α -1)/(T + 1) + 2ϵ. Define F -1 (t) = inf{s : F (s) ≥ t} and the event A T = {q 1-α,T < F -1 (1 -(j α -1)/(T + 1) + 2ϵ)}. Then we haveP (A T |F m ) ≥ 1 -C 1 exp(-2T ϵ 2 ). In addition, as ϕ(ξ ′ 1:n , y 1:m ) = O p (n -1/2 ), we have F -1 (s) = O(n -1/2 ) for any s < 1. By Condition (a), we have √ n ϕ(ξ 1:n , y 1:m ) -E[ϕ(ξ 1:n , y 1:m )|F m ] = O p (1). Hence, for T > 2/ϵ -1, P (ϕ(ξ 1:n , y 1:m ) ≥ q 1-α,T |F m ) ≥P √ n ϕ(ξ 1:n , y 1:m ) -E[ϕ(ξ 1:n , y 1:m )|F m ] + √ nE[ϕ(ξ 1:n , y 1:m )|F m ] ≥ √ nq 1-α,T , A T |F m ≥P √ n ϕ(ξ 1:n , y 1:m ) -E[ϕ(ξ 1:n , y 1:m )|F m ] + √ nE[ϕ(ξ 1:n , y 1:m )|F m ] ≥ √ nF -1 (1 -(j α -1)/(T + 1) + 2ϵ), A T |F m ≥P √ n ϕ(ξ 1:n , y 1:m ) -E[ϕ(ξ 1:n , y 1:m )|F m ] + √ nE[ϕ(ξ 1:n , y 1:m )|F m ] ≥ √ nF -1 (1 -α + 3ϵ), A T |F m ≥1 -C 1 exp(-2T ϵ 2 ) + o(1),where we have used Condition (c) and the fact that √ nF -1 (1 -α + 3ϵ) = O(1) to get the convergence.We state the following Lemma, which is useful for the proof of Corollary 1. Lemma 1. {ξ i } n i=1 are conditionally independent given y -n0:n .Proof of Lemma 1. Recall that y i = Γ(ξ i , p(•|y -n0:i-1 )) = Γ i (ξ i ), where Γ i depends on y -n0:i-1 . We note that p(ξ 1:n , y 1:n |y -n0:0 ) =p(ξ 1 , y 1 |y -n0:0 )n i=2 p(ξ i , y i |ξ 1:i-1 , y -n0:i-1 ) = n i=1 1{Γ i (ξ i ) = y i }p(ξ i ).Hence the conditional distribution of ξ 1:n given y -n0:n is equal top(ξ 1:n |y -n0:n ) = n i=1 1{Γ i (u) = y i }dν(u) Γi(u)=yi dν(u) , (A.1)which implies that {ξ i } n i=1 are conditionally independent given y -n0:n .Proof of Corollary 1.(i) Recall in Example 1 that the test statistic is given by:ϕ(ξ 1:n , y 1:n ) = 1 n n i=1 (u i -1/2) π i (y i ) -1 V -1 - 1 2 := 1 n n i=1 h i (ξ i , y i ),where ξ i = (u i , π i ). We first note that h i (ξ i , y i ) is bounded and thus Condition (a) of Theorem 1 holds. Since ξ ′ 1:n is independent of y -n0:n , we haveu ′ i |y 1:n ∼ Unif[0, 1]. Thus, E[ϕ(ξ ′ 1:n , y 1:n )|y 1:n ] = 0, which implies that Condition (b) of Theorem 1 is fulfilled. Denote µ i (•) = p(•|y -n0:i-1). Conditional on y -n0:i and π i (y i ), we know that u i follows the uniform distribution over the interval [µ i (y :π i (y) < π i (y i )), µ i (y : π i (y) ≤ π i (y i ))].As a result, we can calculate the expected value of u i given y -n0:i and π i (y i ) asE[u i |y -n0:i , π i (y i )] = 1 2 {µ i (y : π i (y) < π i (y i )) + µ i (y : π i (y) ≤ π i (y i ))} = µ i (y i ) 2 + µ i (y : π i (y) < π i (y i )) = µ i (y i ) 2 + π i (y i ) -1 V -1 (1 -µ i (y i )) = 1 2 + (1 -µ i (y i )) π i (y i ) -1 V -1 - 1 2 ,where the third equality is because given π i (y i ) = k, π i follows the uniform distribution over the permutation space with the restriction π i (y i ) = k. Then, we haveE (u i -1/2) π i (y i ) -1 V -1 - 1 2 |y -n0:i =E E (u i -1/2) π i (y i ) -1 V -1 - 1 2 |y -n0:i , π i (y i ) |y -n0:i =E (1 -µ i (y i )) π i (y i ) -1 V -1 - 1 2 2 = 1 -p(y i |y -n0:i-1 ) E π i (y i ) -1 V -1 - 1 2 2 |y -n0:i .Given y i , (π i (y i ) -1)/(V -1) follows the uniform distribution over the discrete space {0, 1/(V -1), . . . , 1}. Thus we have E[(π i (y i ) -1)/(V -1)] = 1/2 and Var((π i (y i ) -1)/(V -1)) = C, which is a constant less than 1/12 (i.e., the variance of Unif[0, 1]). Hence, E[ϕ(ξ 1:n , y 1:n )] = Cn -1 n i=1 1 -p(y i |y 1:i-1 ) and Condition (c) of Theorem 1 is satisfied due to (4). (ii) In Example 2, the test statistic is given byϕ(ξ 1:n , y 1:n ) = 1 n n i=1 {log(ξ i,yi ) + 1} .Observe that E ik := -log(ξ ik )/p(k|y -n0:i-1 ) ∼ Exp(p(k|y -n0:i-1 )). Since ξ ′ 1:n is independent of y 1:n , we have -log(ξ ′ i,yi )|y -n0:n ∼ Exp(1). Hence, conditional on y -n0:n , we haveE[ϕ(ξ ′ 1:n , y 1:n )|y -n0:n ] = 0, Var(ϕ(ξ ′ 1:n , y 1:n )|y -n0:n ) = 1 n .Condition (b) of Theorem 1 is satisfied.Given y -n0:n , we know E i,yi = min 1≤k≤V E ik , which implies -log(ξ i,yi )/p(y i |y -n0:i-1 )|y -n0:n ∼ Exp(1). It is worth noting thatP (-log(ξ i,yi ) ≥ t) = p - log(ξ i,yi ) p(y i |y -n0:i-1 ) ≥ t p(y i |y -n0:i-1 ) = exp - t p(y i |y -n0:i-1 ).That is -log(ξ i,yi )|y -n0:n ∼ Exp(1/p(y i |y -n0:i-1 )). According to Lemma 1, ξ i s are conditionally independent given y -n0:n . Thus, we haveE[ϕ(ξ 1:n , y 1:n )|y -n0:n ] = 1 n n i=1(1 -p(y i |y -n0:i-1 )) ,Var(ϕ(ξ 1:n , y 1:n )|y -n0:n ) = 1 n 2 n i=1 p(y i |y -n0:i-1 ) 2 ≤ 1 n .Therefore, Conditions (a) and (c) of Theorem 1 are satisfied.Proof of Theorem 2. We only prove the result under the setting of Example 1 as the proof for Example 2 is similar with the help of Bernstein's inequality. Because |h i | ≤ 1/4, by Hoeffding's inequality, we haveP (|M(ξ a:a+B-1 , y b:b+B-1 ) -E[M(ξ a:a+B-1 , y b:b+B-1 )| y 1:m , y -n0:n ]| > t| y 1:m , y -n0:n ) ≤2 exp -8Bt 2 .By the union bound, we haveP max 1≤a≤n-B+1,1≤b≤m-B+1|M(ξ a:a+B-1 , y b:b+B-1 )-E[M(ξ a:a+B-1 , y b:b+B-1 )| y 1:m , y -n0:n ]| > t| y 1:m , y -n0:n≤2(n -B + 1)(m -B + 1) exp -8Bt 2 .Integrating out the strings in y 1:n that are not contained in y 1:m , we obtainP max 1≤a≤n-B+1,1≤b≤m-B+1 |M(ξ a:a+B-1 , y b:b+B-1 ) -E[M(ξ a:a+B-1 , y b:b+B-1 )| y 1:m , y -n0:n ]| > t|F m ≤2(n -B + 1)(m -B + 1) exp -8Bt 2 ,where On the other hand, for a randomly generated key ξ ′ 1:n , E[M(ξ ′ a:a+B-1 , y b:b+B-1 )|F m ] = 0 for all a, b. By the same argument, we getF m = [P (ϕ(ξ ′ 1:n , y 1:m ) > t|F m ) =P max 1≤a≤n-B+1,1≤b≤m-B+1 M(ξ ′ a:a+B-1 , y b:b+B-1 ) > t F m ≤2(n -B + 1)(m -B + 1) exp -8Bt 2 , which suggests that F -1 (s) = O(C N,B) with F being the distribution of ϕ(ξ ′ 1:n , y 1:m ) conditional on F m and F -1 (t) = inf{s : F (s) ≥ t}. The rest of the arguments are similar to those in the proof of Theorem 1. We skip the details.Proof of Proposition 1. Note that conditional on F m , the p-value sequence is B-dependent in the sense that p i and p j are independent only if |i -j| > B. Under the assumption on B, we haveVar(F a+1:b (t)|F m ) = O B |b -a| = o(1)for |b -a| ≍ m, which implies that F a+1:b (t) -E[F a+1:b (t)] → p 0 for any given t ∈ [0, 1]. Using similar arguments as in the proof of Theorem 7.5.2 of Resnick [2019] , we can strengthen the result to allow uniform convergence over t ∈ [0, 1]:sup t∈[0,1] |F a+1:b (t) -E[F a+1:b (t)]| → p 0.Therefore, we obtainmax 1≤τ <m S 1:m (τ ) ≥S 1:m (τ * ) = √ m τ * (m -τ * ) m 2 sup t∈[0,1] |F 1:τ * (t) -t -(F τ * +1:m (t) -E[F τ * +1:m (t)]) + t -E[F τ * +1:m (t)]| ≥ √ m τ * (m -τ * ) m 2 sup t∈[0,1] |t -E[F τ * +1:m (t)]| -sup t∈[0,1] |F 1:τ * (t) -t| -sup t∈[0,1] |F τ * +1:m (t) -E[F τ * +1:m (t)]| = √ mγ * (1 -γ * ){D(F 0 , E[F τ * +1:m (t)]) + o p (1)}(1 + o(1)) → +∞.Proof of Theorem 3. We begin the proof by noting thatτ (m -τ ) m 3/2 (F 1:τ (t) -F τ +1:m (t)) = 1 √ m τ i=1 (1{p i ≤ t} -F 1:m (t)).Let us focus on the case where τ ≤ τ * . The other case where τ > τ * can be proved in a similar way. By the definition of τ , we have 0 ≤ 1 m sup t τ i=1 (1{p i ≤ t} -F 1:m (t)) - 1 m sup t τ * i=1 (1{p i ≤ t} -F 1:m (t)) := I(τ ) -I(τ * ).I(τ ) = 1 m sup t W 1:τ (t) - τ m (W 1:τ * (t) + W τ * +1:m (t)) = 1 m sup t τ F 0 (t) - τ m {τ * F 0 (t) + (m -τ * )E[F τ * +1:m (t)]} + R(τ ) = (m -τ * )τ m 2 D(F 0 , E[F τ * +1:m (t)]) + R(τ ),where R(τ ) is a reminder term satisfying that|R(τ )| ≤ 1 m sup t W1:τ (t) - τ m W1:τ * (t) + Wτ * +1:m (t) .Hence, we have0 ≤I(τ ) -I(τ * ) = (m -τ * )(τ -τ * ) m 2 D(F 0 , E[F τ * +1:m (t)]) + R(τ ) -R(τ * ) ≤ (m -τ * )(τ -τ * ) m 2 D(F 0 , E[F τ * +1:m (t)]) + 2 sup τ ≤τ * |R(τ )|, which implies that τ * -τ ≤ 2m 2 (m -τ * )D(F 0 , E[F τ * +1:m (t)]) sup τ ≤τ * |R(τ )|.Notice thatsup τ |R(τ )| ≤ 1 m sup τ ≤τ * sup t∈[0,1] W1:τ (t) - τ m { W1:τ * (t) + Wτ * +1:m (t)} ≤ 1 m sup τ ≤τ * sup t∈[0,1] W1:τ (t) + 1 m sup t∈[0,1] W1:τ * (t) + Wτ * +1:m (t) ≤ 1 m sup τ ≤m sup t∈[0,1] W1:τ (t) + O p (m -1/2 ).It remains to analyze sup τ ≤m sup t∈[0,1] W1:τ (t) . We first present a result that slightly modifies the Ottaviani's inequality. For the ease of notation, we write ∥ W1:τ ∥ = sup t∈[0,1] W1:τ (t) . For any u > 0 and v > B, we haveP max τ ≤m ∥ W1:τ ∥ > u + v ≤ P (∥ W1:m ∥ > v -B) 1 -max τ P (∥ Wτ+1:m ∥ > u) . (A.2)To see this, let A k be the event that ∥ W1:k ∥ is the first ∥ W1:j ∥ (for j = 1, 2, . . . , m) that is strictly greater than u+v. The event on the LHS is the disjoint union of A 1 , . . . , A m . Note that ∥ Wk+1+B:m ∥ is independent of ∥ W1 ∥, . . . , ∥ Wk ∥ (and hence is independent of A k ). We haveP (A k ) min 0≤τ <m P (∥ Wτ+1:m ∥ ≤ u) ≤P (A k , ∥ Wk+1+B:m ∥ ≤ u) ≤P (A k , ∥ Wk+1:m ∥ ≤ u + B) ≤P (A k , ∥ W1:m ∥ > v -B),where we have usede the fact ∥ Wk+1:m ∥ ≤ ∥ Wk+1:k+B ∥ + ∥ Wk+B+1:m ∥ ≤ u + B. Summing over k leads toP max τ ≤m ∥ W1:τ ∥ > u + v min 0≤τ <m P (∥ Wτ+1:m ∥ ≤ u) ≤ P (∥ W1:m ∥ > v -B),which gives the desired result.Next, we study P (∥ Wτ+1:m ∥ > u) for any τ = 0, . . . , m -1. Note that P (∥ Wτ+1:m ∥ > u) ≤ P (∥ Wτ+1:τ * ∥ > u/2) + P (∥ Wτ * +1:m ∥ > u/2). Thus, without loss of generality, let us focus our analysis on the probability P (∥ Wa+1:b ∥ > u), where the corresponding segment does not contain a change point. Assume b -a = 2KB. (Notice that for general a < b, we have an additional interval whose length is smaller than B. Hence, a similar analysis below can be used.) We divide the index set {a + 1, a + 2, . . . , b} into 2K consecutive blocks, denoted by J 1 , . . . , J 2K , with equal block size B. Then we haveP (∥ Wa+1:b ∥ > u) ≤ P K i=1 FJ2i-1 > u/(2B) + P K i=1 FJ2i > u/(2B)with FJi = WJi /B, whereK i=1 FJ2i-1 and K i=1FJ2i are both sums of independent bounded random variables. Let us analyze the second term on the RHS. DefineG(t) = K i=1 j∈J2i P (p j ≤ t)/(KB), G m (t) = K i=1 j∈J2i1{p j ≤ t}/(KB).Let t v,L = G -1 (v/L) for v = 1, 2, . . . , L. Following the argument in Theorem 7.5.2 of Resnick [2019] , we can show that1 K K i=1 FJ2i = ∥G m -G∥ ≤ max 1≤v≤L |G m (t v,L ) -G(t v,L )| ∨ |G m (t v,L -) -G(t v,L -)| + 1 L ,where G m (t-) = K i=1 i∈J2i 1{p i < t}/(KB) and G(t-) is defined similarly. Thus we haveP K i=1 FJ2i > u/(2B) ≤P max 1≤v≤L |G m (t v,L ) -G(t v,L )| ∨ |G m (t v,L -) -G(t v,L -)| + 1/L > u/(b -a) ≤ L v=1 P (|G m (t v,L ) -G(t v,L )| ∨ |G m (t v,L -) -G(t v,L -)| > u/(b -a) -1/L) ≤C 1 L exp -C 2 K(u/(b -a) -1/L) 2where the third inequality follows from Hoeffding's inequality. τ * -τ ≤ O p mB log(m/B) D(F 0 , E[F τ * +1:m (t)]).A similar argument applies to the other direction, which gives|τ -τ * | = O p mB log(m/B) D(F 0 , E[F τ * +1:m (t)]).Recall that we use V to denote the vocabulary and Ξ to represent the space of watermark keys. Let V * be the space of strings, where * can be any positive integer; for example, y 1:m ∈ V m . Similarly, we define Ξ * as the space of watermark key sequences. Given a string y, let y a: be the string from the ath token to the end; for example, if y = y 1:m , then y 2: = y 2:m . Denote the length of a string y as len( y). Definition 1 (Simple Levenshtein cost). Let γ ∈ R and base alignment cost d 0 : V × Ξ → R. Given a string y ∈ V * and a watermark key sequence ξ ∈ Ξ * , the simple Levenshtein cost d γ ( y, ξ) is defined byd γ ( y, ξ) := min (d γ ( y 2: , ξ 2: ) + d 0 (y 1 , ξ 1 ), d γ ( y, ξ 2: ) + γ, d γ ( y 2: , ξ) + γ) , (B.1) with d γ ( y, ξ) := γ • len( y) if ξ is empty and d γ ( y, ξ) := γ • len(ξ) if y is empty.We use the following metric to quantify the dependence between the watermark key and the string:M(ξ 1:n , y 1:m ) = -d γ ( y 1:m , ξ 1:n ), (B.2)where γ = 0.4, andd 0 ( y 1 , (u 1 , π 1 )) = u 1 - π 1 ( y 1 ) -1 |V| -1 , (B.3)in inverse transform sampling method, while • Setting 1 (no change point): Generate 500 tokens with a watermark.d 0 ( y 1 , ξ 1 ) = log (1 -ξ 1, y1 ) , (B.• 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 4 (insertion and substitution attacks): Generate 400 tokens with watermarks, substitute the token with indices ranging from 101 to 200 with 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. By comparing with the p-value sequences obtained using openai-community/gpt2, we claim that 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. We focus on the Meta-Llama-3-8B model to conduct simulation studies under some 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 more challenging. In a 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.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}. Table C .1 shows the rand index value for each setting, with a higher rand index indicating better performance. 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 highly effective, 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 smaller 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 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 = ⌊3n 1/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 our method is affected by the choice of the number of permutations T . To this end, we set B to 20 and consider T ∈ {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 a level of stability in our method. Justification: We claim our contributions in the abstract and introduction. (i) We rigorously study the Type I and Type II errors of the randomization test for detecting the presence of a watermark. We then apply these findings to the inverse transform and Gumbel watermark schemes. (ii) We develop a systematic statistical method for segmenting texts into watermarked and non-watermarked sub-strings, and we investigate the theoretical and finite sample performance of this methodology, which has yet to be thoroughly explored in 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 be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?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). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?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 not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.• The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
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-produced 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., deployment 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 not tied to particular applications, let alone deployments. However, if there is a 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 or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: 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 a minimum risk for misuse.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 a best faith effort.12. Licenses for existing assets 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 is used and, if 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, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset'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 not release new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to 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.Rand Index Setting 2, EMS Setting 2, EMSL Setting 2, ITS Setting 2, ITSL Setting 3, EMS Setting 3, EMSL Setting 3, ITS Setting 3, ITSL Setting 4, EMS Setting 4, EMSL Setting 4, ITS Setting 4, ITSL Figure 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 to different thresholds ζ. 
 
 Appendix:  


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

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).
questions: 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: Limitations are adequately addressed.
paper_summary: paper_summary: This paper presents a statistical method for detecting and segmenting watermarked text generated by large language models (LLMs). The key contributions are:

A 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).
A 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.
Theoretical analysis of the proposed segmentation method, including convergence rates for estimated change point locations.
Empirical 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.

The 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.
strength_weakness: strength_weakness: Weaknesses:

Limited model diversity: Experiments focus on GPT-2 and OPT-1.3b. Testing on larger language models would strengthen findings.

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,
1) Users may make changes to the text by means of cross-lingual attack and GPT rewrite, etc., the authors did not analyze these scenarios.
2) 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.

In addition, better visualization for selected scenarios could better reflect the value of the accuracy of the proposed methodology.

It should be noted that I will raise my score when I see appropriate rebuttals.
questions: 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: limitations: The authors have adequately addressed the limitations in the checklist.
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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.
- 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.
- 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).

## Minor 

- 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.
- 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)).

## Typos/Nits

- L.27 Large Language Model
- 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)
questions: questions: - How does the proposed method fare on more realistic text scenarios with shorter sections of watermarked / non-watermarked texts?
- Can you provide a practical ablation over B (both w.r.t. runtime and effectiveness of the detection)?
- Can you provide some experiments on larger and more realistic models (As well as the costs associated with running tests on such models).
- Do you have any ideas about the effect of repeating key-patterns (which happens in practice) on your analysis?
limitations: limitations: The paper addresses several limitations; however, as pointed out above, I think some more limitations of the current setting could be discussed.

Comments: comment: Thank you for your encouraging feedback and for acknowledging the additional experiments. We are pleased that our efforts have effectively addressed your concerns, and we are glad to share the updated Rand Index results obtained from 10 texts with 1300 tokens:

| Threshold |  0.05  |  0.01  |  0.005 |  0.001 |
|-----------|--------|--------|--------|--------|
| Rand Index| 0.9489 | 0.9523 | 0.9553 | 0.9767 |

The threshold refers to the $p$-value threshold in NOT used to claim the significance of a change point. A higher Rand Index indicates better performance. These results are promising and demonstrate the robustness of our proposed method.
Thank you very much for your positive feedback and for raising your score. We are grateful for your thorough review and are delighted to hear that our response has addressed all your concerns.
Thank you for your thorough response.

All of my concerns have been addressed: I have raised my score to reflect this. This is a good paper and I hope it is accepted.
Thank you for your detailed response and the additional experiments. I appreciate the efforts you've put in during the rebuttal period.

I apologize for overlooking the details in Figure 2 earlier. I now recognize that it does address the scenario of multiple change points, though the segment lengths were not explicitly pointed out.

Your thorough rebuttal has addressed most of my concerns. I am particularly impressed by the additional experiments, especially the one following the token structure I suggested. These results demonstrate the robustness of your methodology.

Given your responses and the considerable effort in improving the paper, I am inclined to raise my evaluation positively. Thank you again for your hard work.
We appreciate your comments, which have significantly helped us improve the manuscript. Also, thank you for taking the time to review our rebuttal once more. In response to your comment, "The precautions users [...] different segment lengths," we have indeed conducted numerical experiments with varying segment lengths and have presented the results in Figure 2 of the attached PDF file. We apologize for not making the setups clear in our rebuttal. Below, we clarify the simulation settings considered in Figure 2.

Specifically, we generated change point locations randomly. For instance, in the most challenging scenario with 12 change points, the true change points are located at {46, 113, 151, 172, 222, 269, 297, 336, 357, 382, 425, 460}. More precisely, we generate the texts such that
- Tokens 1-45: Watermarked
- Tokens 46-112: Unwatermarked
- Tokens 113-150: Watermarked
- Tokens 151-171: Unwatermarked
- Tokens 172-221: Watermarked
- Tokens 222-268: Unwatermarked
- Tokens 269-296: Watermarked
- Tokens 297-335: Unwatermarked 
- Tokens 336-356: Watermarked
- Tokens 357-381: Unwatermarked
- Tokens 382-424: Watermarked
- Tokens 425-459: Unwatermarked
- Tokens 460-500: Watermarked

This setup is challenging due to the varying segment lengths and the small gaps between the change point locations. In this case, the set of change points detected by our algorithm is given by {46, 104, 152, 186, 224, 302, 335, 384, 436}, which successfully identifies 9 of the 12 change points. In the scenario with 8 change points with random locations, our method was able to detect all 8 change point locations successfully. These results demonstrate the robustness/effectiveness of our proposed method in challenging situations.

Based on the setting you suggested, we have conducted an additional experiment. Specifically, we generate texts with 1300 tokens and the true change points located at {51, 151, 401, 651, 951}, based on the substitution attacks. The other configurations are the same as in the rebuttal. The detected change points are {57, 154, 409, 667, 955}. We consider this result promising, and if time permits, we shall obtain more experimental results in the next few days.
Thank you for your thoughtful and constructive feedback. We are grateful for your decision to raise your score and your efforts in enhancing our manuscript. We are thrilled to hear that the additional experiments and results have addressed most of your concerns. We will definitely consider additional watermark schemes (e.g., the red-green scheme with possibilities of key-repeating patterns) in our revision if time permits and in our future work.
Thank you for addressing my concerns and providing detailed experimental results. I appreciate the additional experiments conducted with the *Meta-Llama-3-8B* model and the analyses of cross-lingual attacks and LLM rewrites. The improved visualizations and theoretical insights significantly strengthen your paper.

However, as mentioned in my initial review, I still did not see the results incorporating multiple change points with varying segment lengths. For instance, an experiment with the following token structure would be highly insightful: 

- Tokens 1-50: Unwatermarked
- Tokens 50-150: Watermarked
- Tokens 150-400: Unwatermarked
- Tokens 400-650: Watermarked
- Tokens 650-950: Unwatermarked
- Tokens 950-1300: Watermarked

Such scenarios would better reflect real-world complexities and enhance the robustness of your methodology.

Thank you again for your thorough responses and valuable additions to the paper.
I thank the author for their extensive rebuttal and appreciate the time and effort spent on new experiments. The presented results seem convincing and address most of my main concerns (I remain very interested in adaptations to other watermarking schemes). In light of the new results, I will raise my score.

P.S.: I must have glossed over the inserted in L.293 multiple times; this is clearly on me.