📊 statistics

Optimal Watermark Localization in Mixed-Source Large Language Model Texts

This paper formulates watermark localization in mixed-source LLM texts as a token-level multiple-testing problem, establishing theoretical phase transitions for detection and classification while proposing an adaptive thresholding method that achieves optimal discovery power without requiring prior knowledge of signal sparsity or distribution parameters.

Original authors: Jose H. Blanchet, T. Tony Cai, Xiang Li, Hao Liu, Qi Long, Weijie J. Su

Published 2026-08-18

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Jose H. Blanchet, T. Tony Cai, Xiang Li, Hao Liu, Qi Long, Weijie J. Su

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

In the modern digital landscape, large language models have become powerful tools for generating human-like text, assisting with everything from writing essays to debugging code. However, this capability brings a significant challenge: distinguishing between text written by a human and text generated by a machine. To solve this, researchers have developed a technique called watermarking. Imagine a machine that, while writing, secretly embeds a statistical pattern into its choice of words. This pattern is invisible to the human eye and does not change the meaning or flow of the text, but it acts like a hidden signature that a verifier can detect if they possess the correct key. This allows for the authentication of AI-generated content, helping to protect academic integrity and prevent the spread of misinformation.

Yet, a major complication arises in the real world. People rarely use AI-generated text exactly as it comes out of the machine. They edit, rewrite, paraphrase, or delete parts of it before submitting or publishing. These human changes can break the hidden statistical pattern, erasing the evidence of the machine's involvement in those specific sections. This leaves a difficult question: if a document is a mix of original AI text and human edits, can we pinpoint exactly which parts still carry the machine's signature, and which parts have been altered beyond recognition? This is not just about knowing if a document contains AI; it is about finding the specific locations where the AI's fingerprint survives.

A team of researchers from Stanford University and the University of Pennsylvania has tackled this problem by treating it as a statistical search for hidden signals within a noisy sequence. They developed a new method to locate these surviving watermarks at the level of individual words, or tokens, rather than just looking at the document as a whole. Their work reveals that finding these specific locations is fundamentally harder than simply detecting that a document contains AI text. Furthermore, they discovered a hard limit: it is mathematically impossible to perfectly separate every single machine-written word from every human-written word in a mixed document, no matter how sophisticated the method. However, they also created a new, adaptive tool that can successfully identify the surviving machine-written sections with high accuracy, even without knowing exactly how much editing occurred or how the text was originally generated.

The researchers approached the problem by first understanding the nature of the "noise" created by human editing. When a human edits a text, they might replace a word, insert a new sentence, or delete a phrase. If the original word was part of the AI's hidden pattern, replacing it breaks the link. The researchers modeled this as a sequence where some positions still hold the original statistical signal, while others have been erased. They defined three levels of success for a detection system. The first is global detection, which simply asks, "Is there any AI in this text?" The second is discovery, which asks, "Can we find at least some of the AI-written parts?" The third is classification, which asks, "Can we perfectly identify every single AI-written word and every single human-written word?"

Through their analysis, the team proved that while global detection is often possible, finding the specific locations is a much stricter challenge. They showed that discovery is strictly harder than detection because it requires not just sensing a signal, but isolating it from a sea of human edits without making too many mistakes. More significantly, they demonstrated that perfect classification is impossible under their model. This is because some machine-written words, after editing, look so much like human-written words that no statistical test can reliably tell them apart. Trying to catch every single machine word would inevitably lead to falsely accusing human words of being machine-generated, and trying to avoid false accusations would mean missing many machine words. Therefore, the goal must be adjusted to finding a reliable set of machine-written sections rather than a perfect map of the entire document.

To achieve this reliable discovery, the researchers developed a method called SPOT, which stands for Scanning Pivots Over Thresholds. This method works by scanning the text and looking for words that exhibit a statistical pattern that is unusually strong, suggesting they were likely generated by the AI and not altered. The challenge is setting the right sensitivity for this scan. If the scan is too sensitive, it will flag too many human words as machine-generated. If it is too strict, it will miss the machine words that are harder to detect. SPOT solves this by automatically adjusting its sensitivity based on the data it sees. It estimates how much of the text likely still contains the AI signature and then selects a threshold that keeps the rate of false alarms low while still catching as many true signals as possible. This allows the system to adapt to different types of documents and editing styles without needing to know the specific details of how the text was created or edited beforehand.

The researchers tested their theory and method through extensive simulations and experiments with real language models. In their simulations, they created artificial texts with varying degrees of editing and different levels of signal strength. The results confirmed their theoretical predictions: there is a clear boundary where finding the machine-written parts becomes possible, and a boundary where it becomes impossible. When the editing is too heavy or the signal too weak, the method correctly fails to find a reliable set of locations. But within the achievable range, the method performs with high precision. In experiments using a real language model to generate text and then applying common human edits like random substitutions, insertions, and deletions, the SPOT method consistently outperformed existing approaches. It was able to identify a larger fraction of the surviving machine-written words while keeping the number of false accusations low.

The study also highlighted how the difficulty of the task changes with the nature of the text generation. When the language model generates text with high randomness, there are more opportunities to find the hidden statistical patterns, making localization easier. When the model is more deterministic, producing very predictable text, the hidden patterns are weaker, and the task becomes harder. The researchers found that their method remained robust across these different conditions, though the accuracy of the underlying estimates for how much text was edited did play a role in performance. They noted that while their method is highly effective, the accuracy of the initial estimate of how much editing occurred can be a bottleneck, particularly when the text is very predictable.

Ultimately, this work provides a clear statistical framework for understanding the limits of watermark localization. It establishes that while we cannot perfectly reconstruct the entire history of a mixed-source document, we can reliably identify the parts that still bear the mark of the machine. This distinction is crucial for practical applications. It means that instead of hoping for a perfect solution that separates every word, we can build systems that confidently flag the sections of a document that are likely AI-generated. This allows for more nuanced attribution, helping educators, publishers, and researchers to understand the provenance of text with greater precision. The researchers conclude that their adaptive method offers a practical and theoretically sound way to navigate the complex reality of edited AI text, providing a tool that works well even when the exact conditions of the text's creation are unknown.

Technical Summary: Optimal Watermark Localization in Mixed-Source Large Language Model Texts

Problem Formulation
While watermarking provides a principled method for authenticating text generated by Large Language Models (LLMs), real-world applications often involve mixed-source texts where human edits (rewriting, insertion, deletion, paraphrasing) disrupt the original watermark signals. Prior work has focused on global detection—determining whether a text contains any watermark evidence in aggregate. However, the statistical limits of watermark localization (identifying exactly which token positions preserve the watermark signal) remain unclear.

The authors formulate watermark localization as a token-level multiple-testing problem. Given a text of length $n$ , the verifier observes a sequence of pivotal statistics $Y_{1:n}$ . For each position $t$ , a latent indicator $\theta_t \in \{0, 1\}$ determines the state:

$\theta_t = 1$ : The watermark dependence survives editing; $Y_t$ follows an alternative distribution $\mu_{1, P_t}$ determined by the local Next-Token Prediction (NTP) distribution $P_t$ .
$\theta_t = 0$ : The dependence is erased; $Y_t$ follows a known null distribution $\mu_0$ (regardless of $P_t$ ).

The goal is to infer the latent sequence $\theta_{1:n}$ , distinguishing between three increasingly difficult inference tasks:

Global Detection: Determining if at least one $\theta_t = 1$ exists.
Discovery: Identifying a non-trivial set of positions with $\theta_t = 1$ while ensuring the marginal False Discovery Rate (mFDR) vanishes.
Classification: Asymptotically separating all null positions from all watermark-preserving positions (vanishing mFDR and vanishing Missed Discovery Rate).

Methodology: SPOT
The paper proposes SPOT (Scanning Pivots Over Thresholds), an adaptive localization method designed to achieve discovery without prior knowledge of the problem's asymptotic parameters (sparsity, signal strength, vocabulary growth) or the time-varying NTP distributions.

Mechanism: SPOT scans a grid of tail thresholds applied to the pivotal statistics. For each candidate threshold, it estimates the fraction of surviving watermark signals ( $\hat{\varepsilon}_n$ ) and computes a surrogate false discovery level based on the empirical tail mass.
Adaptivity: The method selects the largest discovery set such that the estimated false discovery level is controlled below a target $\lambda_n$ . It relies on a data-driven estimate of the surviving watermark fraction (e.g., from Li et al. [26]) rather than requiring the true fraction as input.
Key Advantage: Unlike methods requiring density estimation of heterogeneous alternative distributions (which is infeasible due to unknown, time-varying NTPs), SPOT uses tail counts of pivotal statistics to control false discoveries.

Theoretical Contributions and Results
The authors establish sharp phase transitions for the three inference goals under an asymptotic regime indexed by three exponents:

$p$ : Sparsity of surviving signals ( $\varepsilon_n \asymp n^{-p}$ ).
$q$ : Concentration of NTP distributions ( $1 - \max P_{t,w} \asymp n^{-q}$ ).
$\alpha$ : Growth rate of the effective low-probability vocabulary tail ( $|W_n| \asymp n^\alpha$ ).

Detection Boundary: Global detection is possible if and only if $\max\{p + q, 2p + q - \alpha\} < 1$ . This generalizes previous fixed-vocabulary results, showing that a growing vocabulary tail ( $\alpha > 0$ ) aids global detection by providing aggregate evidence.
Discovery Boundary: Discovery is possible if and only if $p < \alpha$ and $p + q < 1$ .
- The condition $p < \alpha$ is specific to localization: it requires the vocabulary tail to grow fast enough relative to signal sparsity so that individual watermark-preserving tokens can be distinguished from nulls.
- Strict Hardness: Discovery is strictly harder than global detection. There exist regimes where a text is globally detectable but no local rule can reliably discover even a single watermark-preserving position (specifically when $\alpha = 0$ ).
Impossibility of Classification: The authors prove that consistent classification is impossible throughout the entire parameter regime within the class of coordinatewise pivot-based rules.
- Reasoning: To recover all weak signals (minimizing missed discoveries), a rule must be aggressive, inevitably selecting too many null positions (failing mFDR control). Conversely, conservative rules control mFDR but miss a non-negligible fraction of signals. This incompatibility prevents asymptotic separation of null and signal positions.
Optimality of SPOT:
- Boundary Optimality: SPOT achieves discovery throughout the entire theoretically discoverable region ( $p < \alpha, p + q < 1$ ) without knowing $p, q, \alpha$ .
- Near-Optimal Power: Among homogeneous pivot-based rules, SPOT recovers a constant fraction of the maximum possible number of true discoveries, up to lower-order terms.

Empirical Validation

Simulations: Experiments on synthetic pivotal statistics confirm the theoretical phase transitions. The empirical discovery error sharply increases as parameters cross the theoretical boundaries ( $p = \alpha$ and $p + q = 1$ ).
LLM Experiments: Using OPT-1.3B on C4 dataset texts with controlled edits (random substitution/insertion/deletion, adversarial edits, and roundtrip translation):
- SPOT (both oracle and plug-in variants) consistently outperforms the baseline Adaptive Online Locator (AOL) [61] in Intersection-over-Union (IoU) and True Positive Rate (TPR) under random and adversarial edits, particularly at higher generation temperatures ( $T=1$ ).
- At lower temperatures, performance degrades for all methods, but the gap between SPOT's oracle and plug-in versions widens. Analysis reveals this is due to the inaccuracy of the surviving-fraction estimator at low temperatures (where NTPs are highly concentrated), rather than a failure of the localization rule itself.
- SPOT incurs negligible additional computational overhead compared to baselines.

Significance and Claims
The paper claims to provide the first statistical theory characterizing the fundamental limits of watermark localization in mixed-source LLM texts. Its primary contributions are:

Theoretical Limits: Establishing that localization is strictly harder than detection and that perfect classification is impossible under standard coordinatewise rules, defining the precise "phase transitions" where localization becomes feasible.
Adaptive Optimality: Demonstrating that an adaptive, data-driven method (SPOT) can achieve these theoretical limits without requiring knowledge of the underlying generative or editing parameters.
Practical Utility: Showing that despite theoretical impossibility of perfect classification, robust localization of surviving signals is achievable and practically effective under common human editing mechanisms.

The authors note that their work focuses on token-level localization using pivotal statistics and does not propose new watermarking schemes. They identify future directions including online/streaming localization, handling block-structured edits, and extending theory to semantic or sentence-level watermarks.

Technical Summary: Optimal Watermark Localization in Mixed-Source Large Language Model Texts

More like this