📊 statistics

Fast segmentation of watermarked texts from large language models through an epidemic change-point framework

This paper introduces WISER, a novel and computationally efficient algorithm that leverages an epidemic change-point framework to accurately localize and segment watermarked text within large language model outputs, offering strong theoretical guarantees and superior performance over existing methods.

Original authors: Soham Bonnerjee, Subhrajyoty Roy, Sayar Karmakar

Published 2026-07-09

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Soham Bonnerjee, Subhrajyoty Roy, Sayar Karmakar

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Finding the "Fake" Parts in a Story

Imagine you are reading a long story. You suspect that a robot (an AI) wrote some parts of it, but a human wrote the rest. The robot didn't just write randomly; it left a secret, invisible "fingerprint" (a watermark) on the words it generated.

The problem isn't just knowing if the robot wrote the story. The real challenge is finding exactly which sentences are robot-written and which are human-written. This is called segmentation.

Currently, most tools can tell you "This whole story is likely AI," but they are terrible at pinpointing the specific paragraphs. They are also often too slow to handle long books or articles.

This paper introduces a new tool called WISER (Watermark Identification via Segmenting Epidemic Regions). It is designed to be fast, accurate, and mathematically proven to work, even when the text is messy or has been edited by humans.

The Core Idea: The "Epidemic" Analogy

The authors realized that finding these watermarked sections is mathematically similar to tracking an epidemic.

The Analogy: Imagine a healthy town where everyone is healthy (this is the human-written text). Suddenly, a virus outbreak starts in one neighborhood, infecting a specific block of houses for a while, and then the virus disappears, and the town returns to being healthy.
The Connection: The "virus" is the watermark. It appears in a specific "patch" of the text (the watermarked segment) and is absent everywhere else.
The Old Way: Previous methods tried to find the start and end of the virus by looking for two separate "change points" (like finding the exact moment the virus started and the exact moment it stopped). This is hard and slow, especially if there are multiple outbreaks.
The WISER Way: WISER looks at the text as a whole "epidemic patch." It asks: "Where is the cluster of infected houses?" It doesn't just look for the start and end; it looks for the entire infected zone at once. This makes it much faster and more robust.

How WISER Works (The Three-Step Detective Process)

The paper describes WISER as a three-stage detective process:

The Net (Blocking Stage):
Imagine throwing a wide net over the whole text. The text is chopped into small chunks (blocks). WISER checks each chunk to see if it has a high concentration of "virus" (watermark signals). If a chunk looks suspicious, it's kept. If it looks clean, it's tossed out. This quickly narrows down the search area.
The Cleanup (Discarding Stage):
Sometimes the net catches a few false alarms (a clean chunk that just happened to look suspicious by chance). WISER looks at the groups of suspicious chunks it found. If a group is tiny or isolated, it assumes it's a false alarm and removes it. This ensures that only the "real" outbreaks remain.
The Precision Cut (Refined Search):
Now that WISER knows roughly where the outbreaks are, it zooms in. It uses a clever mathematical trick (based on minimizing a specific score) to draw the exact boundaries of the infected zones. It finds the precise start and end of the AI-written text.

Why Is This Special?

The paper highlights three main reasons why WISER is a big deal:

Speed (The Fast Lane):
Other methods are like trying to find a needle in a haystack by checking every single piece of hay one by one. They get very slow as the text gets longer. WISER is like a magnet that sweeps through the haystack instantly. The authors prove mathematically that WISER runs in linear time (O(n)), meaning if you double the length of the text, it only takes twice as long to process, not four times or ten times. It is currently the fastest method with a mathematical guarantee.
Accuracy (The Sharp Eye):
In tests, WISER was better at finding the exact boundaries of AI text than other top methods (like Aligator, SeedBS, and Waterseeker). It didn't just guess; it found the correct segments with high precision, even when the text was long or the AI model was different.
Robustness (The Tough Shield):
What if a human edits the text after the AI writes it? Maybe they delete a sentence or swap a word. Many tools break in this scenario. WISER is designed to handle this "mixed-source" text. It assumes the "virus" might be slightly altered but can still be detected because the underlying pattern remains.

The "Secret Sauce": Pivot Statistics

To make all this work, the paper relies on a concept called Pivot Statistics.

Think of the AI's "fingerprint" as a secret code. The authors use a mathematical tool that converts the text into a score.

If the text is human, the score stays low and steady (like a calm heartbeat).
If the text is AI, the score jumps up (like a fever).

The genius of WISER is that it doesn't care how the fever is caused (which specific AI model or which specific watermarking trick was used). It just looks for the "fever" (the elevated scores) appearing in patches. This makes the tool very flexible and applicable to many different types of AI watermarks.

Summary

The paper presents WISER, a new algorithm that acts like a high-speed, high-precision scanner for AI-generated text. By viewing the problem as an "epidemic" (finding clusters of infection) rather than just finding start and end points, WISER can quickly and accurately separate human writing from AI writing within a single document. It is faster, more accurate, and mathematically proven to work better than existing tools, making it a powerful new weapon in the fight against AI misinformation and plagiarism.

Technical Summary: Fast Segmentation of Watermarked Texts from Large Language Models through an Epidemic Change-Point Framework

Problem Statement
The proliferation of Large Language Models (LLMs) has necessitated robust mechanisms for detecting machine-generated content to address concerns regarding authenticity, copyright, and academic integrity. While watermarking schemes—embedding statistical signals into token generation using secret keys—have been developed to detect the presence of LLM-generated text, the finer-grained task of localizing specific watermarked segments within a mixed-source text (containing both human and machine-generated content) remains underexplored. Existing segmentation algorithms often suffer from prohibitive computational complexity, making them unsuitable for long texts, or lack theoretical guarantees robust to paraphrasing and post-editing. Furthermore, current methods struggle to efficiently identify multiple disjoint watermarked intervals within a single document.

Methodology: The Epidemic Change-Point Perspective
The authors propose WISER (Watermark Identification via Segmenting Epidemic Regions), an algorithm that reframes the watermark segmentation problem as an epidemic change-point detection problem.

Pivot Statistics and Elevated Alternatives: The method relies on "pivot statistics" ( $Y_t$ ), which are functions of the generated tokens and pseudo-random keys. Under the null hypothesis (human-generated/unwatermarked tokens), these statistics follow a known, stationary distribution with mean $\mu_0$ . Under the alternative (watermarked tokens), the statistics exhibit an "elevated alternative" property, where their expected value is strictly greater than $\mu_0$ by a margin $d$ , regardless of the specific Next Token Distribution (NTP) of the LLM.
Epidemic Modeling: Unlike standard change-point problems where a shift persists indefinitely, watermarking creates "epidemic" intervals: the mean of the pivot statistics shifts upward for a specific contiguous segment (the watermark) and returns to the baseline outside that segment.
Algorithm Design:
- Single Segment Estimator: For a single watermarked patch, the authors adapt an estimator that minimizes a biased surplus outside a candidate interval. By subtracting a buffer term ( $\rho \tilde{d}$ ) from the sum of statistics outside the interval, the algorithm penalizes including non-watermarked tokens while rewarding the exclusion of elevated watermarked tokens.
- Multi-Segment Strategy (WISER): To handle multiple segments without prior knowledge of their count ( $K$ $K$ ), WISER employs a four-stage pipeline:
  - Blocking: The text is partitioned into blocks. Blocks with sums exceeding a threshold $Q$ are retained.
  - Discarding: Connected components of retained blocks are formed. Short components (likely false positives) are discarded based on a length threshold ( $c\sqrt{\log n}$ ).
  - Enlargement: The remaining connected regions are expanded by a factor of $\sqrt{n}$ to ensure they fully cover the true watermarked segments.
  - Refined Local Search: Within these enlarged regions, the single-segment estimator is applied to precisely locate the start and end points.
- Computational Efficiency: By restricting the search space to the enlarged regions derived from the screening stage, WISER achieves a computational complexity of $O(n)$ , making it the first theoretically guaranteed segmentation algorithm with linear time complexity.

Key Contributions

Novel Perspective: The paper establishes a formal connection between watermark localization and epidemic change-point detection, a framework previously underutilized in this domain.
Theoretical Guarantees: The authors provide finite-sample error bounds and prove the consistency of WISER for detecting multiple watermarked segments. Theorem 3.1 establishes that the symmetric difference between the estimated and true intervals converges to zero at a rate of $O((\rho \tilde{d})^{-1})$ . Theorem 4.1 extends this to the multi-segment case, proving that WISER correctly identifies the number of segments and their locations with high probability as $n \to \infty$ .
Algorithmic Innovation: WISER is the first algorithm to offer provable theoretical validity for general multi-segment watermark localization while maintaining $O(n)$ computational efficiency.
Robustness: The method is designed to be agnostic to the specific LLM architecture or NTP, relying only on the properties of the pivot statistics and the elevated alternatives hypothesis.

Experimental Results
Extensive numerical experiments were conducted on benchmark datasets (C4 News) using various LLMs (e.g., OPT, Gemma, Llama-3, Mistral) and diverse watermarking schemes (Gumbel, Inverse Transform, Red-Green, Permute-and-Flip).

Accuracy: WISER consistently outperformed state-of-the-art baselines (Aligator, SeedBS-NOT, Waterseeker) across all metrics, including Intersection-over-Union (IoU), Precision, Recall, and F1-score. In many scenarios, WISER achieved performance near the "Oracle" estimator (which assumes knowledge of the true number of segments $K$ ).
Speed: Empirical runtime analysis confirmed the theoretical $O(n)$ complexity. WISER was significantly faster than competing methods, which often exhibited super-linear or quadratic scaling.
Robustness: The algorithm maintained high performance under varying levels of temporal dependence in token generation and demonstrated resilience against human edits (substitution, insertion, deletion) in mixed-source texts.

Significance and Claims
The paper positions WISER as a critical tool for AI moderation and content verification. The authors claim that by bridging classical statistical theory (epidemic change-points) with modern generative AI challenges, they have produced a solution that is both theoretically valid and computationally efficient.

The significance lies in addressing a gap in the literature where existing methods were either too slow for practical deployment on long documents or lacked rigorous statistical guarantees. The authors emphasize that their approach does not require knowledge of the specific LLM architecture, making it a generalizable solution for detecting and localizing watermarked content in real-world scenarios involving mixed human-AI text. The work also highlights the utility of pivot statistics in handling the non-stationary nature of watermarked token sequences, a feature that distinguishes it from standard change-point detection literature.