Efficiently Identifying Watermarked Segments in Mixed-Source Texts

## Abstract

Abstract Text watermarks in large language models (LLMs) are increasingly used to detect synthetic text, mitigating misuse cases like fake news and academic dishonesty. While existing watermarking detection techniques primarily focus on classifying entire documents as watermarked or not, they often neglect the common scenario of identifying individual watermark segments within longer, mixed-source documents. Drawing inspiration from plagiarism detection systems, we propose two novel methods for partial watermark detection. First, we develop a geometry cover detection framework aimed at determining whether there is a watermark segment in long text. Second, we introduce an adaptive online learning algorithm to pinpoint the precise location of watermark segments within the text. Evaluated on three popular watermarking techniques (KGW-Watermark, Unigram-Watermark, and Gumbel-Watermark), our approach achieves high accuracy, significantly outperforming baseline methods. Moreover, our framework is adaptable to other watermarking techniques, offering new insights for precise watermark detection.

## 1 Introduction

Large Language Models (LLMs) have revolutionized human activities, enabling applications ranging from chatbots (OpenAI, ) to medical diagnostics (Google, ) and robotics (Ahn et al., ). Their ease of use, however, presents serious societal challenges. In education (Intelligent, ), students can effortlessly generate essays and homework answers, undermining academic integrity. In journalism (Blum, ), distinguishing credible news from fabricated content erodes public trust. The potential for malicious uses, such as phishing (Violino, ), and the risk of model collapse due to synthetic data (Shumailov et al., ), further underscore the urgent need to detect LLM-generated text and promote the responsible use of this powerful technology.

However, identifying AI-generated text is becoming increasingly difficult as LLMs reach human-like proficiency in various tasks. One line of research (OpenAI, ; Tian, ; Mitchell et al., ) trains machine learning models as AI detectors by collecting datasets consisting of both human and LLM-generated texts. Unfortunately, these approaches are often fragile (Shi et al., ) and error-prone (Liang et al., ), ultimately leading OpenAI to terminate its deployed detector (Kelly, ). Watermarking has emerged as a promising solution to this challenge. By embedding identifiable patterns or markers within the generated text, watermarks can signal whether a piece of text originates from an LLM.

Existing watermark detection methods (Aaronson, ; Kirchenbauer et al., ; Zhao et al., ; Kuditipudi et al., ; Christ et al., ; Hu et al., ) are primarily designed for text-level classification, labeling a piece of text as either watermarked or not. However, these methods are insufficient for many real-world scenarios where documents contain mixed-source texts, and only specific sections are LLM-generated. For instance, malicious actors might use LLMs to manipulate certain sections of a news article to spread misinformation. Detecting watermarks within long, mixed-source texts presents a significant challenge, especially when aiming for subsequence-level detection with uncertainty quantification, similar to plagiarism detection systems like “Turnitin(^1^11[https://www.turnitin.com](https://www.turnitin.com))”. This is because the watermarked signal may be weakened throughout the increasing text length and may not be easily identifiable using conventional detection methods.

To bridge the gap, we propose partial watermark detection methods that offer a reliable solution for identifying watermark segments in long texts. A straightforward approach, which involves examining all possible segments of a text containing $n$ tokens, yields an inefficiently high time complexity of $\mathcal{O}(n^{2})$. Instead, we employ the *geometric cover* trick (Daniely et al., ) to partition the long texts into subsequences of varying lengths and then perform watermark detection within each interval. This approach, termed the *Geometric Cover Detector* (GCD), enables efficient classification of whether a document contains any watermarked text in $\mathcal{O}(n\log n)$ time. However, GCD does not assign a score to every token, providing only a rough localization of watermark segments.

To refine this localization, we introduce the *Adaptive Online Locator* (AOL). AOL reformulate the problem as an online denoising task, where each token score from the watermark detector serves as a noisy observation for the mean value of scores within watermark segments. By applying an adaptive online learning method, specifically the *Alligator* algorithm (Baby et al., ), we retain the $\mathcal{O}(n\log n)$ time complexity while significantly improving the accuracy of detected segments.

We validate GCD and AOL using the C4 (Raffel et al., ) and Arxiv (Cohan et al., ) datasets, employing Llama (Touvron et al., ) and Mistral (Jiang et al., ) models for evaluation. Our empirical results demonstrate strong performance across both classification and localization tasks.
In the classification task, our method consistently achieves a higher true positive rate compared to the baseline at the same false positive rate.
For localization, we achieve an average intersection over union (IoU) score of over 0.55, far exceeding baseline methods.

In summary, our contributions are threefold:

- 1.
We introduce novel approaches to watermark detection, moving beyond simple text-level classification to identification of watermark segments within long, mixed-source texts.
- 2.
We employ the *geometric cover* trick and the *Alligator* algorithm from online learning to reliably detect and localize watermark segments efficiently and accurately.
- 3.
We conduct extensive experiments on state-of-the-art public LLMs and diverse datasets. Our empirical results show that our approach significantly outperforms baseline methods.

## 2 Background and Related Work

### 2.1 LLM Watermark and Detection

##### Language Models and Watermarking.

A language model $\mathcal{M}$ is a statistical model that generates natural language text based on a preceding context. Given an input sequence $x$ (prompt) and previous output $y_{<t}=(y_{1},\dots,y_{t-1})$, an autoregressive language model computes the probability distribution $P_{\mathcal{M}}(\cdot|x,y_{<t})$ of the next token $y_{t}$ in the vocabulary $\mathcal{V}$. The full response is generated by iteratively sampling $y_{t}$ from this distribution until a maximum length is reached or an end-token is generated. *Decoding-based watermarking* (Aaronson, ; Kirchenbauer et al., ; Zhao et al., ; Kuditipudi et al., ; Christ et al., ; Hu et al., ) modifies this text generation process by using a secret key ${\sf k}$ to transform the original next-token distribution $P_{\mathcal{M}}(\cdot|x,y_{<t})$ into a new distribution. This new distribution is used to generate watermarked text containing an embedded watermark signal. The watermark detection algorithm then identifies this signal within a suspect text using the same watermark key ${\sf k}$.

##### Red-Green Watermark.

Red-Green (statistical) watermarking methods partition the vocabulary into two sets, “green” and “red”, using a pseudorandom function $R(h,{\sf k},\gamma)$. This function takes as input the length of the preceding token sequence ($h$), a secret watermark key (${\sf k}$), and the target proportion of green tokens ($\gamma$). During text generation, the logits of green tokens are subtly increased by a small value $\delta$, resulting in a higher proportion of green tokens in the watermarked text compared to non-watermarked text. Two prominent Red-Green watermarking methods are KGW-Watermark (Kirchenbauer et al., , ) and Unigram-Watermark (Zhao et al., ). KGW-Watermark utilizes $h\geq 1$, considering the prefix for hashing. Unigram-Watermark employs fixed green and red lists, disregarding previous tokens by effectively setting $h=0$ to enhance robustness. Watermark detection in both methods involves identifying each token’s membership in the green or red list

$$ $\operatorname{Score}(y)=\sum_{t=1}^{n}\mathbf{1}(y_{t}\in\text{Green Tokens})$ (1) $$

and calculating the $z$-score of the entire sequence:$z_{y}=\frac{\operatorname{Score}(y)-\gamma n}{\sqrt{n\gamma(1-\gamma)}}$. This $z$-score reflects the deviation of the observed proportion of green tokens from the expected proportion $\gamma n$, where $n$ is the total number of tokens in the sequence. A significantly high $z$-score yields a small p-value, indicating the presence of the watermark.

##### Gumbel Watermark.

The watermarking techniques proposed by Aaronson () and Kuditipudi et al. () can be described using a sampling algorithm based on the Gumbel trick (Zhao et al., ). This algorithm hashes the preceding $h$ tokens using the key ${\sf k}$ to obtain a score $r_{i}$ for each token $i$ in the vocabulary $\mathcal{V}$, where each $r_{i}$ is uniformly distributed in $[0,1]$. The next token is chosen deterministically as follows:
$\arg\max_{y_{i}\in\mathcal{V}}\left[\log P(y_{i}|x_{<t})-\log(-\log(r_{y_{i}})
)\right]$.
Thus, given a random vector $r\sim(\text{Uniform}([0,1]))^{|\mathcal{V}|}$, $-\log(-\log(r_{y_{i}}))$ follows a Gumbel(0,1) distribution. This results in a distortion-free deterministic sampling algorithm (for large $h$) for generating text. During detection, if the observed score

$$ $\operatorname{Score}(y)=\sum_{t=1}^{n}\log\left(1/(1-r_{y_{t}})\right)$ (2) $$

is high, the p-value is low, indicating the presence of the watermark.

### 2.2 Text Attribution and Plagiarism Detection

Watermark text localization shares similarities with text attribution and plagiarism detection, particularly in the aspect of pinpointing specific text segments. Commercial plagiarism detection systems like Turnitin, Chegg, and Grammarly rely on vast databases to identify copied content, highlighting similar segments. Research in plagiarism localization, such as the work by Grozea et al. (), focuses on precisely identifying copied passages within documents. Their approach utilizes a similarity matrix and sequence-matching techniques for accurate localization. Similarly, the “Greedy String Tiling” algorithm (Wise, ) has been successfully employed by Mozgovoy et al. () for identifying overlapping text. However, these methods require reference files in a database, whereas watermark text localization aims to localize the watermark text using a watermark key, eliminating the need for reference documents. Detecting partially watermarked text presents a unique challenge, akin to an online learning problem, where tokens in watermark segments exhibit special signals that can be captured by a strongly adaptive online learning algorithm like Aligator (Baby et al., ).

### 2.3 Identifying Watermarked Portions in Long Text

To detect watermarked portions in long texts, Aaronson () designs a “watermark plausibility score” for each interval. Given
$\left\{s_{t}=\log(1/(1-r_{y_{t}}))\right\}_{t\in[n]}$, the watermark plausibility score is $\frac{\left(\sum_{t=i}^{j}s_{t}\right)^{2}}{j-i}-L$,
where $L$ is a constant. This method draws connections to change point detection algorithms, aiming to maximize the sum of plausibility scores to detect watermarked portions. Aaronson () manages to reduce the time complexity from $\mathcal{O}(n^{2})$ to $\mathcal{O}(n^{3/2})$. Additionally, Christ et al. () demonstrate how to detect a watermarked contiguous substring of the output with sufficiently high entropy, calling the algorithm *Substring Completeness*. This algorithm has a time complexity of $\mathcal{O}(n^{2})$. A recent, independent work of Kirchenbauer et al. () introduces the *WinMax* algorithm to detect watermarked sub-regions in long texts. This algorithm searches for the continuous span of tokens that produces the highest $z$-score by iterating over all possible window sizes and traversing the entire text for each size, with a time complexity of $\tilde{\mathcal{O}}(n^{2})$. Our *Adaptive Online Locator* (AOL) improves the efficiency of detecting watermarked portions, reducing the time complexity to $\mathcal{O}(n\log n)$.

## 3 Method

### 3.1 Problem Statement

Identifying watermark segments within a long text sequence $y$ presents two key challenges. First, we need to design a classification rule $\mathcal{M}(x)\rightarrow\{0,1\}$ that determines whether $y$ contains a watermark segment. To address this, we propose the *Geometric Cover Detector* (GCD), which enables multi-scale watermark detection. Second, accurately locating the watermark segments $y_{s_{i}:e_{i}}$ within the full sequence $y$ requires finding the start and end token indices, $s_{i}$ and $e_{i}$, for each watermark segment. We introduce the *Adaptive Online Locator* (AOL) with the Aligator algorithm to precisely identify the position of the watermarked text span within the longer sequence.

Figure: Figure 1: Illustration of the watermark segment detection process. The input sequence could be mixed-source of watermark text and unwatermark text. The input sequence could be a mixed-source of watermarked text and unwatermarked text. We use geometric covers to partition the text and detect watermarks in intervals. We also formulate localization as an online denoising problem to reduce computational complexity. The example shown is drawn from the abstract of Bengio et al. (), with the watermarked part generated by a watermarked Mistral-7B model.
Refer to caption: x1.png

Figure: Algorithm 1 Geometry Cover Watermark Detection

### 3.2 Watermark Segment Classification

A straightforward approach to detect whether an article contains watermarked text is to pass it through the original watermark detector (as we discussed in Section 2.1). If the detection score from the original detector is larger than a threshold, the text contains a watermark; otherwise, no watermark is found. However, this approach is ineffective for long, mixed-source texts where only a small portion originates from the watermarked LLM. Since a large portion of the text lacks the watermark signal, the overall score for the entire document will be dominated by the unwatermarked portion, rendering the detection unreliable.

To overcome this limitation, we need a method that analyzes the text at different scales or chunks. If a chunk is flagged as watermarked, we can then classify the entire sequence as containing watermarked text. The question then becomes: how do we design these intervals or chunks effectively? We leverage the Geometric Cover (GC) technique introduced by Daniely et al. () to construct an efficient collection of intervals for analysis.

Geometric Cover (GC) is a collection of intervals belonging to the set $\mathbb{N}$, defined as follows:

$$ $\displaystyle\text{ $\mathcal{I}=\bigcup_{k\in\mathbb{N}\cup{0}}\mathcal{I}^{(k)},$ where $\forall k\in\mathbb{N}\cup{0}$, and $\mathcal{I}^{(k)}={[i\cdot 2^{k},( i+1)\cdot 2^{k}-1]:i\in\mathbb{N}}$}.$ (3) $$

Essentially, each $\mathcal{I}^{(k)}$ represents a partition of $\mathbb{N}$ into consecutive intervals of length $2^{k}$. For example, $\mathcal{I}^{(4)}$ contains all consecutive 16-token intervals. Due to this structure, each token belongs to $\lfloor{\log n}\rfloor+1$ different intervals (as illustrated in Figure 1), and there are a total of $n+n/2+n/4+n/8+\dots=\mathcal{O}(n)$ intervals in the GC set. This allows us to establish a multi-scale watermark detection framework.
Moreover, Lemma 5 from Daniely et al. () ensures that for any unknown watermarked interval, there is a corresponding interval in the geometric cover that is fully contained within it and is at least *one-fourth* its length. This ensures the effectiveness of watermark detection using the geometric cover framework.

Leveraging the GC construction, our multi-scale watermark detection framework divides the input text into segments based on the GC intervals. In real-world applications, we need to balance the granularity of the intervals. For instance, classifying a 4-token chunk as watermarked might not be convincing. Therefore, we start from higher-order intervals, such as $\mathcal{I}^{(5)}$, which comprises all geometric cover intervals longer than 32 tokens.

Algorithm 1 outlines our approach. For each segment $\mathcal{I}_{t}:y_{i_{t}:j_{t}}$ in the GC, we first compute a detection score using the appropriate watermark detector for the scheme employed (e.g., Equation 1 for Red-Green Watermark or Equation 2 for Gumbel Watermark). This score, along with the segment itself, is then passed to an FPR calibration function $F$. This function estimates the FPR associated with the segment. Further details on FPR calibration can be found in the Appendix A.1.

If the estimated FPR, denoted as $\alpha$, falls below a predefined target FPR ($\tau$), we classify the entire sequence as containing a watermark. It is important to note that $\tau$ is set at the segment level. Using the union bound, consider a mixed-source text composed of $n$ tokens. The geometric cover of the text is constructed from $\mathcal{O}(n)$ intervals. Let $\tau$ represent the false positive rate for each interval test (Type I error rate). In this case, the Family-Wise Error Rate (FWER), which is the probability of incorrectly classifying the entire document as watermarked, is bounded by $n\tau$.

### 3.3 Precise Watermark Position Localization

Figure: Algorithm 2 Watermark Position Localization

While the previous section focused on detecting the presence of watermarks, simply knowing a watermark exists doesn’t reveal which specific paragraphs warrant scrutiny. Here, we aim to localize the exact location of watermarked text.

A naive approach would involve iterating through all possible interval combinations within the sequence, applying the watermark detection rule to each segment $y_{i:j}$ for all $i\in\{1,\dots,n\}$ and $j\in\{i,\dots,n\}$. While this brute-force method can identify watermark segments, its $\mathcal{O}(n^{2})$ time complexity makes it computationally expensive for long sequences.

Furthermore, relying solely on individual token scores for localization is unreliable due to the inherent noise in the watermarking process. To address this issue, we propose to formulate it as a sequence denoising problem (a.k.a., smoothing or nonparametric regression) so we can provide a pointwise estimate of the *expected* detection score *for each token*.
Specifically, the denoising algorithm tasks a sequence of noisy observations $s_{1},...,s_{n}$ and output $\{\theta_{t}\}_{t\in[n]}$ as an estimate to $\{\mathop{\mathbb{E}}[s_{t}]\}_{t\in[n]}$.

As an example, for the Green-Red Watermark, the sequence of noisy observations

$$ $\displaystyle\left\{s_{t}=\mathbf{1}(y_{t}\in\text{Green Tokens})\right\}_{t \in[n]}$ $$

consists of Bernoulli random variables. The expectation $\mathop{\mathbb{E}}[s_{t}]=\gamma$ if $y_{t}$ is not watermarked and $\mathop{\mathbb{E}}[s_{t}]>\gamma$ otherwise. For the Gumbel Watermark, the noisy observations

$$ $\displaystyle\left\{s_{t}=\log(1/(1-r_{y_{t}}))\right\}_{t\in[n]}$ $$

consists of exponential random variables satisfying $\mathop{\mathbb{E}}[s_{t}]=1$ if $y_{t}$ is unwatermarked and larger otherwise. The intuition is that, while individually they are too noisy, if we average them appropriately within a local neighborhood, we can substantially reduce the noise. If we can accurately estimate the sequence ${\mathop{\mathbb{E}}[s_{i}]}$, we can localize watermarked segments by simply thresholding the estimated score pointwise.

The challenge, again, is that we do not know the appropriate window size to use. In fact, the appropriate size of the window should be larger if $s_{i}$ is in the interior of a long segment of either watermarked or unwatermarked text. The sharp toggles among text from different sources add additional challenges to most smoothing algorithms.

For these reasons, we employ the Aligator (Aggregation of onLIne averaGes using A geomeTric cOveR) algorithm (Baby et al., ). In short, Aligator is an online smoothing algorithm that optimally competes with an oracle that knows the segments of watermarked sequences ahead of time. The algorithm employs a Geometric Cover approach internally, where words positioned mid-paragraph are typically included in multiple intervals of varying lengths for updates. Notably, Aligator provides the following estimation guarantee:

$$ $\frac{1}{n}\sum_{t}(\theta_{t}-\mathop{\mathbb{E}}[s_{t}])^{2}=\tilde{O}\left( \min\left\{n^{-1}(1+\sum_{t=2}^{n}\mathbf{1}_{\mathop{\mathbb{E}}[s_{t}]\neq \mathop{\mathbb{E}}[s_{t-1}]}),n^{-1}\vee n^{-2/3}(\sum_{t=2}^{n}\left|\mathop {\mathbb{E}}[s_{t}]-\mathop{\mathbb{E}}[s_{t-1}]\right|)\right\}\right).$ $$

Moreover, for all segments with start/end indices $(i,j)\in[n]^{2}$, i.e.

$$ $\frac{1}{j-1}\sum_{t=i}^{j}(\theta_{t}-\frac{1}{j-i}\sum_{t^{\prime}=i}^{j} \mathop{\mathbb{E}}[s_{t^{\prime}}])^{2}\leq\tilde{O}(1/\sqrt{j-i}).$ $$

This ensures that for every segment, the estimated value is as accurate as statistically permitted.
The time complexity for Aligator is $\mathcal{O}(n\log n)$. For a detailed implementation of Aligator, please refer to the original paper (Baby et al., ). For the theoretical results, see (Baby and Wang, ).

Circular Aligator.
To mitigate the boundary effects common in online learning, where prediction accuracy suffers at the beginning and end of sequences, we introduce a circular starting strategy. Instead of processing the text linearly, we treat it as a circular buffer. For each iteration, we randomly choose a starting point and traverse the entire sequence, effectively mitigating edge effects. The final prediction for each token is then obtained by averaging the predictions across all iterations.

Finally, we apply a threshold to this denoised average score function to delineate the boundaries of watermark segments within the text (as illustrated in Figure 1). The high-level implementation of this method is detailed in Algorithm 2. This approach enables us to precisely identify the location of suspected plagiarism within large documents with high confidence, facilitating further investigation and verification.

## 4 Experiment

In this section, we discuss the detailed experiment settings and then show the detection results for watermark segment classification and precise watermark position localization. We also consider different lengths of the mixed-source text and show the detection results. Furthermore, we conduct adversarial attacks to try to remove the watermark and then show the detection robustness results.

### 4.1 Datasets and Mixed-source Texts

We utilize two text datasets: C4 (Raffel et al., ) and Arxiv (Cohan et al., ). The “Colossal Clean Crawled Corpus” (C4) dataset is a collection of English-language text sourced from the public Common Crawl web scrape, a rich source for unwatermarked human-written text. We use random samples from the news-like subset of the C4 dataset in our experiments. The Arxiv dataset is part of the Scientific-Papers dataset collected from scientific repositories, arXiv.org and PubMed.com. We use the Arxiv split in our experiments, which contains abstracts and articles of scientific papers. Both datasets are used to construct watermarked positive samples and human-written negative samples.

To transform unwatermarked samples into partially watermarked samples, we randomly select 3-5 sentences in a long text and set them as prompts. Then, we generate 300 tokens of watermarked text conditioned on the prompts using large language models. The generated responses replace the original suffix sentences after the prompt. In this way, we embed 300-token watermarks into 3000-token contexts from the datasets, making the watermark 10% of the mix-sourced text. We randomly choose the position of the watermark in this longer context and record the locations for later testing. Our goal is to determine if a document contains watermark text and locate its position. For each dataset, we use 500 samples as the test set to show the results.

### 4.2 Language Models and Watermarking Methods.

We use the publicly available LLaMA-7B (Touvron et al., ) and Mistral (Jiang et al., ) models. To verify the general applicability of the watermark detection methods, we select three watermarking techniques: Gumbel-Watermark (Aaronson, ), KGW-Watermark (Kirchenbauer et al., ), and Unigram-Watermark (Zhao et al., ). These methods represent the state-of-the-art watermarking approaches for large language models, offering high quality, detectability, and robustness against adversarial attacks. For all watermarking generations, we configure the temperature to 1.0 for multinomial sampling. Additionally, for KGW-Watermark and Unigram-Watermark, we set the green token ratio $\gamma$ to 0.5 and the perturbation $\delta$ to 2.0.

### 4.3 Baselines

In watermark segment detection, we use the original watermark detector in each watermarking method as the Vanilla baseline to compare with our approach GCD. In watermark segment localization, we use RoBERTa (Liu et al., ) models for comparing with our method AOL. We train each RoBERTa (designed for different watermarking methods) to predict whether a sequence is a watermarked sequence or not, given the watermark detection scores $r$ for each token. We add an extra fully connected layer after getting the representation of the [CLS] token. We construct 1000 training samples with 60 token scores as input and the binary label of this segment as the label. We train the RoBERTa model for 20 epochs and enable early stopping if the loss converges. It can reach over 90% accuracy in the training set. During testing on mixed-source text, we employ the sliding window idea to test each chunk for watermarks and then calculate the IoU score.

### 4.4 Evaluation

For the watermarked text classification task, we report the true positive rates (TPR) based on different specified false positive rates (FPR). Maintaining a low FPR is critical to ensure that human-written text is rarely misclassified as LLM-generated text.

Since the FPR at the per-instance level differs from the document-level FPR, we calibrate FPR to three distinct levels in each scenario to enable fair comparisons. Specifically, we manipulate the pre-segment FPR (Seg-FPR) by adjusting the threshold parameter $\tau$ as outlined in Algorithm 1. Then, we can get the empirical document FPR (Doc-FPR) by evaluating our method GCD based on pure natural text. For Vanilla, we set the FPR according to GCD’s empirical FPR and subsequently test for its empirical TPR.

For locating specific watermark segments, we calculate the Intersection over Union (IoU) score to measure the accuracy of watermark segment localization. The IoU score computes the ratio of the intersection and union between the ground truth and inference, serving as one of the main metrics for evaluating the accuracy of object detection algorithms:

$$ $\displaystyle\operatorname{IoU}$ $\displaystyle=\frac{\text{Area of Intersection}}{\text{Area of Union}}=\frac{| \text{Detected Tokens}\cap\text{Watermarked Tokens}|}{|\text{Detected Tokens} \cup\text{Watermarked Tokens}|}$ $$

### 4.5 Detection Results

#### 4.5.1 Watermark Segment Classification Results

As shown in Table 1, our proposed *Geometric Cover Detector* (GCD) consistently outperforms the baseline Vanilla method across all watermarking techniques and large language models on both the C4 and Arxiv datasets. The robustness of GCD across diverse conditions underscores its effectiveness in watermark segment classification, demonstrating clear superiority over Vanilla. Additionally, we observe that Vanilla exhibits near-zero detection rates when the target false positive rate is low. This suggests that Vanilla struggles to detect watermarked segments in longer contexts, as the watermark signal weakens, rendering the simpler detector ineffective.

**Table 1: True Positive Rate (TPR) at various False Positive Rate (FPR) levels for baseline Vanilla and our method GCD. For each setting, we select three distinct segment-level FPRs (Seg-FPR) and compare the performance of Vanilla and GCD at equivalent document-level FPRs (Doc-FPR). GCD consistently outperforms Vanilla across different models and datasets.**
| Method | KGW-Watermark TPR | Unigram-Watermark TPR | Gumbel-Watermark TPR |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| C4 Dataset, Llama-7B |  |  |  |  |  |  |  |  |  |
| Seg-FPR | 1e-5 | 5e-5 | 1e-4 | 1e-4 | 2e-4 | 0.001 | 1e-4 | 0.001 | 0.010 |
| Doc-FPR | 0.034 | 0.076 | 0.082 | 0.002 | 0.004 | 0.030 | 0.026 | 0.080 | 0.358 |
| \hdashline  Vanilla | 0.602 | 0.676 | 0.692 | 0.006 | 0.006 | 0.058 | 0.650 | 0.762 | 0.918 |
| GCD | 0.912 | 0.934 | 0.934 | 0.874 | 0.906 | 0.958 | 1.000 | 1.000 | 1.000 |
| C4 Dataset, Mistral-7B |  |  |  |  |  |  |  |  |  |
| Seg-FPR | 1e-5 | 1e-4 | 2e-4 | 0.001 | 0.010 | 0.020 | 1e-4 | 5e-4 | 0.001 |
| Doc-FPR | 0.037 | 0.087 | 0.153 | 0.001 | 0.012 | 0.040 | 0.024 | 0.046 | 0.054 |
| \hdashline  Vanilla | 0.697 | 0.830 | 0.877 | 0.000 | 0.012 | 0.030 | 0.690 | 0.760 | 0.780 |
| GCD | 0.960 | 0.983 | 0.990 | 0.722 | 0.974 | 1.000 | 0.970 | 0.980 | 0.990 |
| Arxiv Dataset, Llama-7B |  |  |  |  |  |  |  |  |  |
| Seg-FPR | 1e-5 | 5e-5 | 2e-4 | 1e-4 | 2e-4 | 0.001 | 1e-4 | 0.001 | 0.010 |
| Doc-FPR | 0.068 | 0.116 | 0.186 | 1e-4 | 2e-4 | 0.014 | 0.024 | 0.066 | 0.280 |
| \hdashline  Vanilla | 0.844 | 0.896 | 0.908 | 0.000 | 0.000 | 0.026 | 0.593 | 0.655 | 0.823 |
| GCD | 0.990 | 0.994 | 0.996 | 0.892 | 0.922 | 0.974 | 0.958 | 0.978 | 1.000 |
| Arxiv Dataset, Mistral-7B |  |  |  |  |  |  |  |  |  |
| Seg-FPR | 1e-5 | 1e-4 | 2e-4 | 0.001 | 0.020 | 0.020 | 1e-5 | 1e-4 | 2e-4 |
| Doc-FPR | 0.033 | 0.197 | 0.253 | 0.001 | 0.028 | 0.036 | 0.082 | 0.192 | 0.230 |
| \hdashline  Vanilla | 0.757 | 0.883 | 0.907 | 0.002 | 0.032 | 0.088 | 0.860 | 0.930 | 0.930 |
| GCD | 0.967 | 0.990 | 1.000 | 0.566 | 0.920 | 0.964 | 0.950 | 0.960 | 0.970 |

#### 4.5.2 Precise Watermark Position Localization Results

For the watermark position localization task, we evaluate our proposed method AOL against the baseline method RoBERTa (Table 2). We calculate the average IoU score to quantify the precision of the watermark localization.

Our method consistently outperforms the baseline across all test settings. For example, on the C4 dataset using the mistral-7B model, AOL achieves a substantially higher IoU score of 0.809 compared to 0.301 for RoBERTa. We also test AOL’s ability to detect multiple watermarks by inserting 3x300-token Gumbel watermarks (generated by Mistral-7B) into 6000-token texts. Across 200 samples, the average IoU for detecting the watermarks is 0.802, demonstrating AOL’s effectiveness for multiple watermark detection.

Figure 2 provides a case example illustrating the improved localization performance of AOL on the Gumbel watermark with the Mistral-7B model. The upper image shows the boundary effects of using online learning. The lower image demonstrates more precise localization resulting from the circular starting strategy with 10 random starting points.

**Table 2: Precise Watermark Position Localization Performance: Intersection over Union (IoU) score for baseline RoBERTa and our method AOL. AOL consistently outperforms RoBERTa.**
| Method | KGW-WM IoU | Unigram-WM IoU | Gumbel-WM IoU |
| --- | --- | --- | --- |
| C4 Dataset, Llama-7B |  |  |  |
| RoBERTa | 0.563 | 0.444 | 0.535 |
| AOL | 0.657 | 0.818 | 0.758 |
| C4 Dataset, Mistral-7B |  |  |  |
| RoBERTa | 0.238 | 0.019 | 0.301 |
| AOL | 0.620 | 0.790 | 0.809 |
| Arxiv Dataset, Llama-7B |  |  |  |
| RoBERTa | 0.321 | 0.519 | 0.579 |
| AOL | 0.718 | 0.862 | 0.635 |
| Arxiv Dataset, Mistral-7B |  |  |  |
| RoBERTa | 0.372 | 0.249 | 0.421 |
| AOL | 0.571 | 0.682 | 0.802 |

Figure: Figure 2: Example of precise watermark localization using AOL with Gumbel Watermark. Light green lines show token scores, and dark green lines show predicted mean scores. The horizontal dashed line shows the score threshold $\zeta=1.3$. The vertical dashed line marks the original watermark position. The top image demonstrates inaccurate localization from a single pass of the Aligator algorithm, highlighting boundary artifacts. In contrast, the bottom image shows precise localization achieved by AOL’s circular initialization strategy with $m=10$ random starts.
Refer to caption: x2.png

### 4.6 Detection Results with Different Lengths

As mentioned previously, watermark detection can easily be disturbed by long natural paragraphs, and our approach aims to minimize the effect of length scale. We test our method on texts of varying total lengths, ranging from 3000 to 18000 tokens, while keeping the watermark segment length constant at 300 tokens. The same detection threshold and parameters used for 3000 total tokens are applied across all lengths.

We find that the Gumbel watermark segment classification performs well even as total length increases, as shown in Table 3. For repetitive watermarks like KGW and Unigram, longer texts in the Geometry Cover also cause a decrease in segment detection, as shown in Figure 3. However, compared to directly detecting on the whole paragraph, this decrease is more acceptable. Importantly, the parameters used in these tests are identical to those for 3000 tokens. In practice though, for texts of different lengths, the number of starting points in the circular buffer should be adjusted accordingly. This way, similarly strong results can be achieved as with 3000 tokens.

Figure: Table 3: Vanilla and GCD watermark segment classification result with Unigram Watermark on Mistral-7B with different target false positive rates.
Refer to caption: x4.png

### 4.7 Detection Robustness Against Attacks

**Table 4: Watermark segment classification and localization performance with different attacks.**
| Method | KGW-Watermark TPR and IoU | Unigram-Watermark TPR and IoU | Gumbel-Watermark TPR and IoU |  |  |  |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| FPR-1 | FPR-2 | FPR-3 | AOL IoU | FPR-1 | FPR-2 | FPR-3 | AOL IoU | FPR-1 | FPR-2 | FPR-3 | AOL IoU |  |
| Random Swap |  |  |  |  |  |  |  |  |  |  |  |  |
| Baseline | 0.190 | 0.340 | 0.460 | – | 0.000 | 0.005 | 0.025 | – | 0.110 | 0.150 | 0.160 | – |
| Ours | 0.175 | 0.325 | 0.380 | 0.095 | 0.740 | 0.990 | 1.000 | 0.472 | 0.390 | 0.550 | 0.560 | 0.325 |
| Random Delete |  |  |  |  |  |  |  |  |  |  |  |  |
| Baseline | 0.310 | 0.440 | 0.545 | – | 0.000 | 0.000 | 0.015 | – | 0.255 | 0.300 | 0.325 | – |
| Ours | 0.645 | 0.750 | 0.820 | 0.269 | 0.630 | 0.905 | 0.960 | 0.475 | 0.750 | 0.830 | 0.850 | 0.613 |
| ChatGPT Paraphrase |  |  |  |  |  |  |  |  |  |  |  |  |
| Baseline | 0.050 | 0.195 | 0.335 | – | 0.000 | 0.000 | 0.005 | – | 0.020 | 0.065 | 0.065 | – |
| Ours | 0.050 | 0.100 | 0.165 | 0.032 | 0.040 | 0.145 | 0.510 | 0.218 | 0.075 | 0.110 | 0.130 | 0.090 |

We evaluate the robustness of our watermark detection method against three types of attacks (Table 4). First, we use GPT-3.5-turbo to rewrite the text segments containing the watermark as the paraphrasing attack. The other two attacks randomly swap or delete words at a ratio of 0.2. As expected, rewriting by ChatGPT is the most damaging attack, leading to a decline in detection performance. However, our detection method still significantly outperforms the baseline direct detection across most attack types in terms of TPR. For watermark localization, measured by intersection over union (IoU), our method still generates satisfactory results under these attacks. Overall, the results demonstrate the robustness of our watermark detection approach against various perturbations to the watermarked text.

## 5 Conclusion

This paper introduces novel methods for partial watermark detection in LLM-generated text, addressing the critical need for identifying watermark segments within longer, mixed-source documents. By leveraging the geometric cover trick and the Alligator algorithm, our approach achieves high accuracy in both classifying and localizing watermarks, significantly outperforming baseline methods. These advancements pave the way for more robust and reliable detection of synthetic text, promoting responsible use and mitigating potential misuse of LLMs in various domains.

## Appendix A Appendix

### A.1 FPR Calibration Function F 𝐹 F italic_F

As discussed in Section 3.2, the FPR Calibration Function calculates the p-value / FPR for per-instance watermark detection, given the detection scores and the original text. We follow the methodologies outlined in Zhao et al. [] and Fernandez et al. [] for FPR calibration. This section presents three methods for detecting KGW-Watermark, Unigram-Watermark, and Gumbel-Watermark, each employing a unique scoring mechanism and statistical test to assess the FPR.

#### A.1.1 KGW-Watermark

For the KGW-Watermark scheme described in Kirchenbauer et al. [], we follow the approach in Fernandez et al. []. When detecting the watermark for a text segment, under the null hypothesis $\mathcal{H}_{0}$ (i.e., the text is not watermarked), the score $\operatorname{Score}(y)=\sum_{t=1}^{n}\mathbf{1}(y_{t}\in\text{Green Tokens})$ follows a binomial distribution $\mathcal{B}(n,\gamma)$, where $n$ is the total number of tokens and $\gamma$ is the probability of a token being part of the green list. The p-value for an observed score $s$ is calculated as:

$$ $\text{p-value}(s)=\mathbb{P}(\operatorname{Score}(y)>s\mid\mathcal{H}_{0})=I_{ \gamma}(s,n-s+1),$ $$

where $I_{x}(a,b)$ is the regularized incomplete Beta function.

#### A.1.2 Unigram-Watermark

For the Unigram-Watermark scheme, we adopt the methodologies from Zhao et al. []. To achieve a better FPR rate, the detection score differs from the KGW-Watermark approach. The score is defined as $\operatorname{Score}(y)=\sum_{t=1}^{m}\mathbf{1}(\tilde{y}_{t}\in\text{Green
Tokens})$, where $\tilde{y}=\text{Unique}(y)$ represents the sequence of unique tokens in text $y$, and $m$ is the number of unique tokens.

Under the null hypothesis $\mathcal{H}_{0}$ (i.e., the text is not watermarked), each token has a probability $\gamma$ of being included. Using the variance formula for sampling without replacement ($N$ choose $\gamma N$), the variance of this distribution is:

$$ $\mathsf{Var}\left[\sum_{t=1}^{m}\mathbf{1}(\tilde{y}_{t}\in\text{Green Tokens} )\mid y\right]=m\gamma(1-\gamma)(1-\frac{m-1}{n-1}),$ $$

where $n$ is the total number of tokens, and $\gamma$ is the probability of a token being in the green list. The conditional variance of $z_{\mathrm{Unique}(y)}$ is thus $(1-\frac{m-1}{n-1})$. The false positive rate (FPR) is then given by:

$$ $\mathsf{FPR}=1-\Phi\left(\frac{z_{\mathrm{Unique}(y)}}{\sqrt{1-\frac{m-1}{n-1} }}\right),$ $$

where $\Phi$ is the standard normal cumulative distribution function.

#### A.1.3 Gumbel Watermark

For the Gumbel Watermark [Aaronson, ], we adopt the approach presented in Fernandez et al. [], which utilizes a gamma test for watermark detection. Under the null hypothesis $\mathcal{H}_{0}$, $\operatorname{Score}(y)=\sum_{t=1}^{n}\log\left(1/(1-r_{y_{t}})\right)$ follows a gamma distribution $\Gamma(n,1)$. The p-value for an observed score $s$ is calculated as:

$$ $\text{p-value}(s)=\mathbb{P}(\operatorname{Score}(y)>s\mid\mathcal{H}_{0})= \frac{\Gamma(n,s)}{\Gamma(n)}$ $$

where $\Gamma(n,s)$ is the upper incomplete gamma function and $n$ is the total number of tokens.

For all three methods, a lower p-value indicates stronger evidence against the null hypothesis, suggesting a higher likelihood that the text is watermarked. These methods provide a comprehensive framework for watermark detection, each offering unique advantages depending on the specific characteristics of the text and the desired sensitivity of the detection process.

### A.2 Discussion and Limitation

Our methods, GCD and AOL, can be applied to other watermarking schemes as long as they have token-wise detection scores for the sequence, such as Hu et al. [] and Zhao et al. []. The detection results are constrained by the strength of the original watermark generation and the quality of the prompt text. In some cases, low-quality text produced by the watermark generation method cannot be directly detected using the original detection method. Additionally, positive samples created by inserting the generated watermark paragraph into natural text may not be detectable with our approach. However, these limitations arise from the current limitations of watermark generation and detection methods themselves, which is outside the scope of detecting small watermarked segments within long text, the focus of this work. Therefore, we assume that our method needs only to detect reasonably high quality watermarked text segments embedded in long text.

## Peer Reviews

confidence: 5
contribution: 2
initial_rating: 3
presentation: 3
questions: Why does Table 1 show a 20-30% difference in TPR between the baseline and the proposed method? Is this due to the baseline processing the entire long document as input for detection? If so, would the baseline achieve detection performance similar to that of the proposed method if it were to input single tokens for detection, albeit requiring a longer runtime?
soundness: 2
strengths: It is proposed to first use GC to quickly and roughly determine whether a long text contains a watermark. Then AOL is used for "denoising" to accurately identify the watermark position.

Based on three watermark algorithms on the C4 and Arxiv datasets, watermark detection experiments in long texts were carried out, demonstrating the superiority of the proposed method over some baseline detection methods.
summary: This paper proposes a new method for detecting watermarked short text in long texts. First, multi-scale division is performed based on GC algorithm to roughly identify whether there is a watermark (paragraph-level identification). Next, AOL is used for adaptive and precise positioning to determine the specific watermark location (token-level identification). The proposed method can effectively reduce the time calculation complexity and greatly improve the recognition of the original watermark algorithm.
weaknesses: The threat model is not discussed enough. The design of this method assumes that the watermark detection algorithms can achieve perfect detection (or encounter minimal false positives and false negatives), which is overly idealistic. Furthermore, common adversarial watermarking techniques, such as manual modifications or rewrites of watermark texts and the adversarial manipulation of certain tokens, have not been formalized in this context.

The original contribution is not solid enough: For the recognition of target short texts in long texts, it is a natural idea to use GC or similar divide-and-conquer algorithms, binary search, etc. for multi-scale fast detection. The proposed method does not make enough innovations for watermark recognition scenarios. In addition, the AOL used seems to be a complete copy of existing work, and it also lacks original improvements.

Experimental settings are too narrow:
First, the watermark text is fixed at a 10% proportion, which lacks a reasonable justification. What trends in detection results would emerge if the watermark text proportion were lower (1%) or higher (99%)?

Second, tokens modified by LLMs may inherently be more detectable. In other words, the detection of watermark texts might not stem from the presence of watermarks but rather from their generation by an LLM. Therefore, it is recommended to add additional comparative experiments to evaluate whether text generated by LLM but without watermarks will not be detected by the proposed method.

Finally, there is a lack of experiments to evaluate time complexity. This paper mentioned several times in the introduction that it can significantly improve the time complexity (theoretically), but did not show any quantitative comparative experiments.

---

confidence: 4
contribution: 3
initial_rating: 5
presentation: 2
questions: 1 What is the difference of partial watermarked text localization for traditional and LLM scenarios? 
2 The authors described some related works on identifying watermarked portions in long text in Section 2.3, and claimed that the AOL improves the efficiency of detecting watermarked portions, why not choose them as baseline? Why not compared the time cost?
3 According to GCD, some segmentation boundary is fixed across different I(k), how about the situation that the fixed boundary is in the middle of some watermarked content?
4 In section 3.2, why start from 32? 
5 In the experimental settings, the watermarking percentage is set as 10% of the mix-sourced text. Why? I suggest evaluating the method  under different watermarking percentages.
soundness: 2
strengths: The topic is interesting. The idea to exploit online learning prediction to localize watermark segments is attractive.
summary: This paper aims to identify individual watermark segments within longer, mixed-source documents. 
The authors utilized geometry cover to partition the document into segments, then compute a detection score for each segments. If one segment is detected as watermarked, then the whole document is watermarked. Then they  introduced an adaptive online learning algorithm Alligator to pinpoint the precise location of watermark segments. Evaluations show that the approach achieves high accuracy, significantly outperforming baseline methods.
weaknesses: 1 The proposed method lacks a clear description of its underlying intuition.
2 The reason for choosing the compared baseline method is missing.
3 Some parameter settings require further explanation.
4 Some variables lack clear explanations, such as "set N "on line 213, which set? and FPR-1, FPR-2, et al.

---

confidence: 3
contribution: 2
initial_rating: 3
presentation: 2
questions: How did you choose the thresholds in Algorithm 2?
soundness: 3
strengths: The paper proposes two methods, not only detecting the watermark segments in long texts, but also identifying the position of the watermarked segments.
summary: The paper proposes methods to identify and pinpoint watermarked segments in long and mixed-source texts.
weaknesses: The technical contribution of the paper appears limited. It does not propose a novel watermarking scheme or detection method. Instead, it leverages the Geometric Cover technique introduced by Daniel et al. for designing the collection of intervals used in watermark detection, and it utilizes the Aligator algorithm proposed by Baby et al. for watermark localization. The paper seems to be a straightforward combination of these existing ideas. There is little connection between these two methods, and the paper does not address whether the complexity could be further optimized by applying both methods simultaneously.

To enhance its value, the paper could benefit from a more comprehensive evaluation. One of its key strengths is efficiency, and it would be beneficial to include experiments that assess efficiency in terms of both time and computing resource utilization.

---

confidence: 5
contribution: 3
initial_rating: 5
presentation: 3
questions: **Q1. Some parameters are missing**

The value of $\zeta$ (line 228)? The value of the window size $h$ for Aaronson and KGW?

**Q2. Baselines**

The baseline using RoBERTa is very surprising. If $h=0$ (like for Unigram), why not! But for $h>1$, I just don't understand how it could work.
Why the baselines mentioned in Section 2.3 are not considered in the benchmark?
In the end, the problem seems to be similar to a segmentation-based object categorization. This opens the door to many baseline solutions like Graph min-cut using spectral techniques.

**Q3. Typos**

- line 161. $\mathcal{M}(x)$ to be replaced by  $\mathcal{M}(y)$?
- Eq.(3) is not 100% `correct'. $\mathcal{I}^{(k)}$ is not one interval, but a subset of intervals. $\mathcal{I}$ is not a union of intervals but a set of intervals.
- Eq. line 298. I have some doubt. First, I have difficulty finding this result back in the paper of Baby. Second, $\frac{1}{j-1}$ to be replaced by $\frac{1}{j-i}$? $\theta_t$ is compared to a unique value not depending on $t$?
soundness: 2
strengths: **S1. This paper tackles an important issue in LLM watermarking**

**S2. The connection with TV regularized estimator is nice**
summary: This paper proposes an efficient watermark localization when the text under scrutiny is a mix of generated (and watermarked) sentences and human (and non-watermarked) passages.
weaknesses: **W1. The Document False Positive Rate is not under controlled**

There are multiple reasons:
- For a given chunk in the GCD, the detection translates the score into a p-value with the correct formula except for Unigram where this is done via a Z-statistic. Since Unigram and KGW are very similar, I wonder why Unigram deserves special treatment. The Z-statistic approximation may not be accurate for a length of 32, especially when targeting low segment-FPR $\tau$. Moreover, Fernandez et al. advice to remove repeating tokens windows. This is done for Unigram, but not for Aaronson and KGW.
- The algorithm first sets the segment-FPR (also called FPR for intervals) and then extrapolates the Document-FPR (also called Family-Wise Error Rate). It should be the other way around.
- This extrapolation is done empirically (line 369)
- The only approximation is an upper bound $n\tau$ (line 255) which is vacuous for the experiments: $\tau=10^{-4}$ and $n$ in the order of $\approx 10^4$ (Table 3). Note that the Document-FPR is not given in Table 3.

**W2. Dilution of the watermark**

The authors argue that classical watermark detection makes a global decision, which is less reliable when a small fraction of the text is watermarked. I do agree, but it also holds for their proposal. For a given Document-FPR (which should be requirement number 1, independent of the text length), there are more intervals in GCD. Therefore, the threshold at the interval level is a lower p-value, increasing the probability of missing the detection. This difficulty is inherent to the problem. 

**W3. Strong limitations**
    
In the same way, "*Additionally, positive samples created by inserting the generated watermark paragraph into natural text may not be detectable with our approach.*" , "*we assume that our method needs only to detect reasonably high quality watermarked text segments*".
Limitations are hidden in the appendices. I disagree that this is due solely to the watermarking technique. This is partly due to the new detection scheme (see W2). Appendix A.3 reveals the experiments are biased by a filtering technique sieving the good examples.

**W4. Completeness**

A recap of the ALIGATOR algorithm as applied on watermarking detection in the appendix would be a good idea as the papers from Baby are not easy to read.

**W5. Advantage**

The main advantage is the complexity in $O(n\log n)$. I am not so sure it makes a big advantage. One first computes the score per token in $O(n)$. This is the slowest computation. Then analyzing these $n$ real values one way or another should not make a big difference (compared to the first step).

**W6. Experiments**
The experiments consider only one configuration: normal text + watermarked text + normal text. What happens if the watermarked text is spread all over the document?