Signature filtering: a lightweight enhancement for statistical watermark detection in large language models

# Signature filtering: A lightweight enhancement for statistical watermark detection in large language models
Source: [https://arxiv.org/html/2606.18430](https://arxiv.org/html/2606.18430)
###### Abstract

Statistical watermarks help organizations attribute large language model \(LLM\) outputs, yet existing detectors often struggle when watermark signals are weak, texts are repetitive, or watermarks are edited\. We propose*signature filtering*, a detection\-time module that enhances watermark detection without modifying watermark embedding and text generation\. It learns a small set of “signature” tokens whose presence makes watermark tests unreliable, and removes these tokens before detection\. The signatures are obtained by solving a mixed‑integer linear program on a small training set, with constraints that maximize the true positive rate\. We additionally derive finite‑sample and asymptotic bounds under several attacker models \(color\-blind, color\-adaptive, and distributionally correlated\)\. On four well\-known watermark families \(Kgw, Sweet, Unigram, Exp\), four benchmark corpora \(C4, MBPP, HumanEval, Code‑Search‑Net\), and six LLMs \(Opt‑1\.3b, Opt\-6\.7b, Llama2‑13b, Llama3\.1‑8b, Qwen2\.5‑14b, Phi‑3‑medium‑14b\), 2–3\-gram signatures raise detection rates in weak\-signal and low\-entropy settings from 8–31% without filtering to 78–99% with filtering, while keeping false positives controllable and often negligible\. In stress tests where we scramble sentences and perturb 25–50% of tokens by dilution, deletions, and substitutions, 2\-gram filters for Kgw\-style watermarks preserve most of the clean\-text detection gains, often matching or outperforming the advanced WinMax watermark detector\. Signature filtering thus provides a simple, scalable, and model‑agnostic add\-on to strengthen watermark\-based provenance checks for LLM text in information processing workflows\.

###### keywords:

large language model , optimization , watermark

\\affiliation

organization=National Chengchi University, city=Taipei, country=Taiwan

## 1Introduction

Large language models \(LLMs\) now generate vast amounts of text for both public web services and internal enterprise applications\. They power summarization, assistance, and content creation across many domainsXylogiannopouloset al\.\([2024](https://arxiv.org/html/2606.18430#bib.bib41)\)\. As these outputs are mixed with human\-authored material in search indexes, content feeds, and institutional repositories, organizations must routinely decide whether a passage is likely AI\-generated\. These decisions affect reliability, regulatory compliance, and user trust in information servicesXionget al\.\([2025](https://arxiv.org/html/2606.18430#bib.bib42)\); Wanget al\.\([2025a](https://arxiv.org/html/2606.18430#bib.bib40)\)\. Text watermarking addresses this need by embedding imperceptible statistical signals during generation that can later be verified, providing a practical mechanism for attribution, auditing, and governance in information\-processing pipelinesLiuet al\.\([2024b](https://arxiv.org/html/2606.18430#bib.bib54)\); Wuet al\.\([2025](https://arxiv.org/html/2606.18430#bib.bib39)\)\. However, today’s detectors often struggle when \(i\) watermark signals must remain weak to preserve text quality, \(ii\) the text itself is highly repetitive or formulaic, or \(iii\) watermarked passages are heavily mixed or editedWuet al\.\([2025](https://arxiv.org/html/2606.18430#bib.bib39)\)\.

We propose*signature filtering*to address these challenges\. The idea is simple: before running the baseline hypothesis test, we remove a pre\-computed set of “statistically disruptive” tokens from the text\. These tokens form a signature that can be learned offline from historical model outputs, online during text generation, or incrementally on a streaming corpus\. Removing them increases the separation between watermarked and natural text in borderline cases and recovers many true positives in weak\-signal and low\-entropy regimes\. Figure[1](https://arxiv.org/html/2606.18430#S1.F1)illustrates this effect underKgw: signature filtering expands a borderline z\-score gap into a decisive one, increasing the gap between the two passages from 1\.77 to 5\.01 and allowing the detector to correctly identify an otherwise undetectable watermark\.

Peoplewithmarketingbackgroundsarehiredbygovernmentagenciesinanumberofcapacities\.Governmentagenciesatthelocal,stateandfederallevelallemploymarketingprofessionalsinareasincluding,butnotlimitedto,publicrelations,propertydisposal,bondsalesandpurchasing\.\(a\) Unwatermarked textPeoplewithmarketingbackgroundsarehiredbygovernment agenciesinanumberofcapacities\.Governmentagenciesatthe local,stateandfederallevelallemploymarketingprofessionalsinareasincluding,butnotlimitedto,publicrelations,propertydisposal,bondsalesandpurchasing\.\(b\) Unwatermarked and filteredPublicsectormarketersworkforgovernmentagencies,non\-profitorganizations,andotherpublicinstitutions\.Theirgoalistopromotetheservices,products,andpoliciesoftheirorganizationtothepublic\.\(c\) Watermarked textPublicsectormarketersworkforgovernmentagencies,non\-profitorganizations,andotherpublicinstitutions\.Theirgoalistopromotetheservices,products,andpoliciesoftheirorganizationtothepublic\.\(d\) Watermarked and filtered

Figure 1:Unwatermarked and watermarked texts with and without signature filtering\. Words containing filtered tokens are rendered in black\. \(a\)zz=−0\.14\-0\.14, Red = 50%, Green = 49%; \(b\)zz= 1\.66, Red = 29%, Green = 38%, Filtered = 33%; \(c\)zz= 1\.63, Red = 44%, Green = 56%; \(d\)zz= 6\.67, Red = 9%, Green = 42%, Filtered = 49%\. Observe that filtering impacts the scores differently: it boosts the watermarked z\-score from 1\.63 to 6\.67, but slightly inflates the unwatermarked z\-score from \-0\.14 to 1\.66\. This filtering step therefore flips the detector decisiononlyfor the watermarked text w\.r\.t\. the thresholdz0=4z\_\{0\}=4\.From a statistical perspective, a natural question is whether deleting tokens based on the observed text invalidates the null\-distribution assumptions behind the underlying watermark test\. In our setting, it does not\. Under theKgwcoloring model, token colors in an unwatermarked text are i\.i\.d\. random variables conditioned on the secret hash key\. Deleting any subset of tokens that is chosen independently of those hidden colors preserves the distribution on the retained tokens, so the usual z\-test remains valid\. ForExp\-style watermarks, the detector assigns each realized token a score that forms an i\.i\.d\. random variable in an unwatermarked text\. Since our filter is a deterministic function of the observed text, the retained scores remain i\.i\.d\., and the null distribution is correctly calibrated after filtering\. Thus, for unwatermarked texts, running the baseline test on the filtered text is as statistically valid as running the test on the original text, provided the deletion rule relies only on the observable features and the filtered text is sufficiently large\.

Another concern is whether any technique built on independence assumptions can maintain its performance on correlated text\. Our empirical evaluation suggests that signature filtering remains effective even when token coloring is far from independent\. First, on low\-entropy code corpora, where limited variation breaks many detectors, signature filtering achieves near\-optimal true positive rates \(TPR\) forKgwat negligible false positive rates \(FPR\)\. Second, when we apply it to more generic watermark schemes where theKgwcoloring assumption no longer holds, signature filtering still consistently improves detection compared with the baseline\. Third, under common sentence\- and word\-level watermark removal attacks, 2\-gram signature filtering can match or outperform state\-of\-the\-art attack\-resistant detectors\. Taken together, these results show that our method is robust in non\-idealized and correlated settings\.

Although a signature is learned from a training dataset, its performance generalizes reasonably well in our experiments\. Signatures learned on about 1,000 training texts maintain strong TPR and negligible FPR when applied to 50,000 previously unseen texts\. We further show that computing separate signatures on successive text batches and aggregating their scores preserves near\-oracle TPR while keeping the combined FPR well below the union bound\. Signature generation therefore incurs a one\-time or amortized cost at deployment time, after which the learned filters scale gracefully to much larger or entirely new datasets\.

Research objectives and contributions\.Motivated by the fragility of existing LLM watermark detectors in weak\-signal, low\-entropy, and edited\-text settings, this study pursues three objectives:

- •Investigate detection\-time filtering\.We study whether discarding a small pre\-learned subset of tokens before running a standard watermark test can increase detection power\.
- •Characterize statistical validity\.We seek analytical conditions under which our enhancement method remains reliable when texts are correlated, partially edited, or adversarially crafted\.
- •Assess effectiveness and scalability\.We evaluate performance across various practical settings, studying how our method can be deployed in large\-scale information processing pipelines effectively\.

To address these objectives, this work makes the following main contributions:

- •Design a detection\-time enhancement for LLM watermarks\.We develop signature filtering as a plug\-in module for existing statistical watermarking schemes\. It is designed to improve watermark detection in weak\-signal, low\-variation, and edited\-text scenarios where existing techniques often struggle\.
- •Provide formal statistical guarantees under threat models\.We analyze when signature filtering preserves the nominal Type\-I error of standard z\-tests and derive finite\-sample and asymptotic worst\-case bounds on false positives under several adversarial and dependency models\.
- •Evaluate detection capability on realistic attacks and datasets\.We assess signature filtering across watermark families, language models, and corpora benchmarks, as well as quantifying the sensitivity of filtering efficacy to signature training sizes\. The results show that signatures can enhance detection, resist a range of text edits, generalize via predictive reuse, and scale effectively to streaming texts\.

Our approach differs from existing watermark\-enhancing techniques in several fundamental ways\. Prior enhancements typically modify the embedding procedure, redesign the test statistic \(e\.g\., by maximizing over sliding windows\), or introduce new entropy\- or semantics\-based scores that must be calibrated alongside watermark tests\. Our method keeps the underlying watermark family and z\-test unchanged and instead learns a compact filter via optimization on representative data\. This design provides explicit control over the additional false positives by bounding the probability that a correct decision is flipped\. It also exposes interpretable levers that can be tied to explicit service\-level objectives in provenance\-aware workflows\.

The remainder of the paper is organized as follows\. Sec\.[2](https://arxiv.org/html/2606.18430#S2)surveys related work; Sec\.[3](https://arxiv.org/html/2606.18430#S3)presents notation and preliminaries; Sec\.[4](https://arxiv.org/html/2606.18430#S4)introduces the methodology and MILP formulation; Sec\.[5](https://arxiv.org/html/2606.18430#S5)provides false\-positive analyses under multiple threat models; Sec\.[6](https://arxiv.org/html/2606.18430#S6)outlines our empirical results and deployment guidance\. Sec\.[7](https://arxiv.org/html/2606.18430#S7)discusses research implications, limitations, and future work\.

## 2Related Work

Information integrity\.Information integrity is now widely recognized as a socio\-technical challenge for information retrieval and content management systemsChandraet al\.\([2024](https://arxiv.org/html/2606.18430#bib.bib38)\)\. Platforms and institutions must decide at scale whether content is sufficiently authentic and trustworthy\. Recent work spans consumer trust in AI\-mediated contentXylogiannopouloset al\.\([2024](https://arxiv.org/html/2606.18430#bib.bib41)\), fake news detectionFanget al\.\([2024](https://arxiv.org/html/2606.18430#bib.bib35)\); Luvembeet al\.\([2024](https://arxiv.org/html/2606.18430#bib.bib36)\); Penget al\.\([2024](https://arxiv.org/html/2606.18430#bib.bib37)\), and statistical tests based on distributional regularitiesWanget al\.\([2025a](https://arxiv.org/html/2606.18430#bib.bib40)\)\. Our contribution—a post hoc module for statistical watermarks that can be embedded in verification pipelines, respects operational false positive budgets, and supports streaming deployment and data\-drift monitoring—fits naturally into these concerns\. Relative to the existing detection landscape, e\.g\., fake‑news models that fuse local context and global signalsFanget al\.\([2024](https://arxiv.org/html/2606.18430#bib.bib35)\)and multimodal co‑attention detectorsLuvembeet al\.\([2024](https://arxiv.org/html/2606.18430#bib.bib36)\); Penget al\.\([2024](https://arxiv.org/html/2606.18430#bib.bib37)\), signature filtering plays the role of a*domain‑agnostic pre‑filter*for the textual channel that can be combined with complementary evidence such as network cues\.

LLM watermarks\.Watermarking has been adapted to LLMs for attributing AI‑generated textLiuet al\.\([2024b](https://arxiv.org/html/2606.18430#bib.bib54)\); Wuet al\.\([2025](https://arxiv.org/html/2606.18430#bib.bib39)\)\. The signature approach in this work is compatible with two mainstream families of watermarking methods, referred to as theKgwandExpfamiliesPanet al\.\([2024a](https://arxiv.org/html/2606.18430#bib.bib30),[b](https://arxiv.org/html/2606.18430#bib.bib55)\): the former biases the model’s output distribution to embed signalsKirchenbaueret al\.\([2024a](https://arxiv.org/html/2606.18430#bib.bib27)\); Leeet al\.\([2024](https://arxiv.org/html/2606.18430#bib.bib32)\); Kirchenbaueret al\.\([2024b](https://arxiv.org/html/2606.18430#bib.bib28)\); Zhaoet al\.\([2023](https://arxiv.org/html/2606.18430#bib.bib31)\), while the latter guides token selection without distorting the distributionAaronson and Kirchner \([2022](https://arxiv.org/html/2606.18430#bib.bib53)\); Christet al\.\([2024](https://arxiv.org/html/2606.18430#bib.bib58)\); Kuditipudiet al\.\([2024](https://arxiv.org/html/2606.18430#bib.bib3)\)\. Production\-oriented watermarks like SynthID\-Text\(Dathathriet al\.,[2024](https://arxiv.org/html/2606.18430#bib.bib12)\)instead avoid repeated bias and preserve text quality using repeated context masking, which skips watermarking and scoring when a previously used context window reappears in the text\. From the managerial perspective, these methods serve as*inline provenance markers*that downstream systems can verify post‑hoc\.

Detection under challenging scenarios\.Watermark detection is difficult when the watermark signal is weak, the text has low variation, or the content is edited\. Severaldetection\-timetechniques tackle these challenges without changing the embedded watermark\. Entropy\-based detectors likeEwdreweight token contributions so that high\-entropy positions dominate the statistic, improving robustness on low\-entropy material\(Luet al\.,[2024](https://arxiv.org/html/2606.18430#bib.bib29)\)\.Sweetinstead extends logit\-modifying watermarks to code by suppressing low\-entropy segments at generation and detection time\(Leeet al\.,[2024](https://arxiv.org/html/2606.18430#bib.bib32)\)\. Window\-based schemes such asWinMaxreplace the global score with the maximum over sliding windows to recover signal after edits and dilution, andWaterSeekerfurther localizes watermarked regions in long documents\(Kirchenbaueret al\.,[2024b](https://arxiv.org/html/2606.18430#bib.bib28); Panet al\.,[2024b](https://arxiv.org/html/2606.18430#bib.bib55)\)\. Since these methods redesign the detection statistic, their false positive behavior must be recalibrated for each watermark and operating condition\.

By contrast, signature filtering removes selected tokens and reuses the original z\-test of the underlying watermark scheme\. This post\-processing step does not reduce the baseline TPR and FPR, allowing us to isolate and bound the incremental false positive risk caused solely by filtering\. Existing enhancement methods that change the scoring rule or mix embedding and detection do not preserve this structure, so they cannot offer the same type of drop\-in risk guarantees relative to a fixed baseline watermark test\.

Optimization perspectives\.Constraint‑based optimization appears at both the embedding and detection stages\.Wouters \([2023](https://arxiv.org/html/2606.18430#bib.bib47)\)recast watermark scheduling as a bi\-objective MILP that balances detection power and text quality\.Wanget al\.\([2025b](https://arxiv.org/html/2606.18430#bib.bib13)\)likewise frameKgw\-style watermark embedding as a multi\-objective trade\-off, adaptively adjusting watermark strength to better navigate the detectability\-quality frontier\.Liet al\.\([2025b](https://arxiv.org/html/2606.18430#bib.bib49),[a](https://arxiv.org/html/2606.18430#bib.bib52)\)instead derive Neyman\-Pearson‑optimal tests via convex duality and formulate goodness‑of‑fit tests on the detection side to resist paraphrasing\.Tsuret al\.\([2025](https://arxiv.org/html/2606.18430#bib.bib15)\)proposed an optimization framework for designing distortion\-free watermarks in low\-entropy regimes, jointly optimizing the watermarked next\-token distribution and the detection score via a minimax objective\. This connects watermark design to optimal transport and coding theory and provides tunable detection\-distortion trade\-offs in the embedding step\. Compared with these methods, we strengthen the*existing*one‑proportion z‑test statistic using MILP, learningnn‑gram filters on representative data without changing the underlying watermark family\. In this sense, our detection\-time optimization is orthogonal and combinable with embedding\-time optimizations as mentioned above\. Finally, mixed‑integer programs can be used to recover secret partitions from limited samples\(Zhanget al\.,[2024](https://arxiv.org/html/2606.18430#bib.bib50); Reynoldset al\.,[2025](https://arxiv.org/html/2606.18430#bib.bib51)\)\. Because signature filtering relies only on observable token statistics, it may still improve detection even if a green/red split is partially known\. Analysis of this threat model is an interesting direction for future work\.

## 3Preliminaries

Tokens and token types\.A*text*TTis a finite sequence of*tokens*\. Each token in a text is assigned a*token type*ti∈𝒱t\_\{i\}\\in\\mathcal\{V\}from a fixed finite*vocabulary*𝒱\\mathcal\{V\}\. For simplicity, we often identifyTTof lengthnnwith a sequence⟨t1,…,tn⟩\\langle t\_\{1\},\\dots,t\_\{n\}\\rangleof token types\. Multiple tokens may share the same type\. For example, the text⟨1,2,1,2,3⟩\\langle 1,2,1,2,3\\ranglecontains five tokenst1,…,t5t\_\{1\},\\dots,t\_\{5\}but only has three distinct token types:t1=t3=1t\_\{1\}=t\_\{3\}=1,t2=t4=2t\_\{2\}=t\_\{4\}=2, andt5=3t\_\{5\}=3\.

Watermark embedding\.Given a token sequence prefix⟨t1,…,ti−1⟩\\langle t\_\{1\},\\dots,t\_\{i\-1\}\\rangle, the LLM generates the next tokentit\_\{i\}by computing a*logit*li∈ℝ\|𝒱\|l\_\{i\}\\in\\mathbb\{R\}^\{\|\\mathcal\{V\}\|\}and then samplingti∈𝒱t\_\{i\}\\in\\mathcal\{V\}based on the probability distribution induced by the softmax oflil\_\{i\}\. AKgw\-style watermarkKirchenbaueret al\.\([2024a](https://arxiv.org/html/2606.18430#bib.bib27)\)randomly splits𝒱\\mathcal\{V\}into a green list𝒢i\\mathcal\{G\}\_\{i\}and a red listℛi\\mathcal\{R\}\_\{i\}at each stepii, such that\|𝒢i\|=γ​\|𝒱\|\|\\mathcal\{G\}\_\{i\}\|=\\gamma\\,\|\\mathcal\{V\}\|with a green ratioγ∈\(0,1\)\\gamma\\in\(0,1\)\.Kgwamplifies the sampling probability of green tokens with a*selection bias*δ\>0\\delta\>0\. A larger biasδ\\deltamakes the watermark signal stronger and easier to detect, but may increase text distortion\.

AnExp\-style algorithmKuditipudiet al\.\([2024](https://arxiv.org/html/2606.18430#bib.bib3)\)guides token sampling through keyed pseudorandomness\. At each stepii,Expselects as the tokentit\_\{i\}a token satisfyingti∈arg⁡maxy∈𝒱⁡\(li​\(y\)/θ\+Gi​\(y\)\),t\_\{i\}\\in\{\\arg\\max\}\_\{y\\in\\mathcal\{V\}\}~\\bigl\(l\_\{i\}\(y\)/\\theta\+G\_\{i\}\(y\)\\bigr\),whereθ\\thetais the model temperature andGi​\(y\)∼Gumbel​\(0,1\)G\_\{i\}\(y\)\\\!\\sim\\\!\\textrm\{Gumbel\}\(0,1\)denotes the \(keyed\) Gumbel noiseFuet al\.\([2024](https://arxiv.org/html/2606.18430#bib.bib46)\)\. The model temperatureθ\\thetacontrols sampling entropy and text diversity, which indirectly affects watermark detectability\. Whenθ\\thetais small, the scaled logitsli​\(y\)/θl\_\{i\}\(y\)/\\thetabecome more dominant\. Token choices thus concentrate on a few high\-confidence candidates, yielding a weaker accumulated watermark signal and making detection harder\. Conversely, a higher temperature strengthens watermark signals at the price of higher generation randomness and potential quality changes\.

Watermark detection\.Given a candidate textTTof length\|T\|=n\|T\|=n, the detector runs a hypothesis test to determine whetherTTcontains a watermark, with the null hypothesisℋ0\\mathcal\{H\}\_\{0\}claimingTTis unwatermarked\.

AKgwdetector performs a z\-test defined byZK​\(T\)≔\(Ng−γ​n\)/γ​\(1−γ\)​n,Z\_\{\\textrm\{K\}\}\(T\)\\coloneqq\{\(N\_\{g\}\-\\gamma n\)\}/\{\\sqrt\{\\gamma\(1\-\\gamma\)n\}\},whereNgN\_\{g\}denotes the number of green tokens inTT, and rejectsℋ0\\mathcal\{H\}\_\{0\}if and only ifZK​\(T\)≥z0Z\_\{\\textrm\{K\}\}\(T\)\\geq z\_\{0\}for a prescribed thresholdz0z\_\{0\}\.

AnExpdetector computes a per\-token*score*and the exact Gamma\-tail p\-value underℋ0\\mathcal\{H\}\_\{0\}Fernandezet al\.\([2023a](https://arxiv.org/html/2606.18430#bib.bib24)\)\. Specifically, at each positionii, the detector generates a pseudorandom vectorui∈\(0,1\)\|𝒱\|u\_\{i\}\\in\(0,1\)^\{\|\\mathcal\{V\}\|\}\(from the secret key and local context\) and reads out the pseudorandom scalarRi≔ui​\[ti\]\.R\_\{i\}\\coloneqq u\_\{i\}\[t\_\{i\}\]\.It then defines the per\-tokenExpscoreci≔−ln⁡\(1−Ri\),c\_\{i\}\\coloneqq\-\\ln\(1\-R\_\{i\}\),and the text\-level statisticX≔∑i=1nci\.X\\coloneqq\\sum\_\{i=1\}^\{n\}c\_\{i\}\.Underℋ0\\mathcal\{H\}\_\{0\}, we haveRi∼𝒰​\[0,1\]R\_\{i\}\\sim\\mathcal\{U\}\[0,1\]\. Henceci∼Exp​\(1\)c\_\{i\}\\sim\\mathrm\{Exp\}\(1\)andX∼Γ​\(n,1\)X\\sim\\Gamma\(n,1\)\. TheExpdetector exploits the Gamma\-tail p\-valuepE​\(T\)≔ℙ​\(Xn≥X\)=Γ​\(n,X\)/Γ​\(n\)p\_\{\\textrm\{E\}\}\(T\)\\coloneqq\\mathbb\{P\}\(X\_\{n\}\\geq X\)=\\Gamma\(n,X\)/\\Gamma\(n\)withXn∼Γ​\(n,1\)X\_\{n\}\\sim\\Gamma\(n,1\), and rejectsℋ0\\mathcal\{H\}\_\{0\}if and only ifpE​\(T\)<αp\_\{\\textrm\{E\}\}\(T\)<\\alphafor a prescribed significance levelα\\alpha\. Note that we can equivalently define a z\-testZE​\(T\)≔Φ−1​\(1−pE​\(T\)\)Z\_\{\\textrm\{E\}\}\(T\)\\coloneqq\\Phi^\{\-1\}\(1\-p\_\{\\textrm\{E\}\}\(T\)\)andz≔Φ−1​\(1−α\)z\\coloneqq\\Phi^\{\-1\}\(1\-\\alpha\), such thatpE​\(T\)<α⟺ZE​\(T\)≥zp\_\{\\textrm\{E\}\}\(T\)<\\alpha\\Longleftrightarrow Z\_\{\\textrm\{E\}\}\(T\)\\geq z\.

For both watermark schemes, detection can be uniformly formalized as a hypothesis test:

- •ℋ0\\mathcal\{H\}\_\{0\}\(*Null hypothesis:TTis unwatermarked*\)\. ForKgw,ZK​\(T\)Z\_\{\\textrm\{K\}\}\(T\)is approximately𝒩​\(0,1\)\\mathcal\{N\}\(0,1\)for sufficiently large\|T\|\|T\|underℋ0\\mathcal\{H\}\_\{0\}\. In contrast,Expis an exact test for any\|T\|≥1\|T\|\\geq 1:pE​\(T\)∼𝒰​\[0,1\]p\_\{\\textrm\{E\}\}\(T\)\\sim\\mathcal\{U\}\[0,1\]andZE​\(T\)∼𝒩​\(0,1\)Z\_\{\\textrm\{E\}\}\(T\)\\sim\\mathcal\{N\}\(0,1\)hold strictly underℋ0\\mathcal\{H\}\_\{0\}without asymptotic reliance\.
- •ℋ1\\mathcal\{H\}\_\{1\}\(*Alternative hypothesis:TTis watermarked*\)\. Underℋ1\\mathcal\{H\}\_\{1\},Kgwincreases the expected green\-token rate and inflatesZK​\(T\)Z\_\{\\textrm\{K\}\}\(T\)beyond zero\.Expbiases the realized pseudorandom valuesRiR\_\{i\}toward larger values, makingXXstochastically larger than its null distribution\. This yields smallerpE​\(T\)p\_\{\\textrm\{E\}\}\(T\)and largerZE​\(T\)Z\_\{\\textrm\{E\}\}\(T\)\.

The baseline detector declaresTTas watermarked ifZ​\(T\)≥z0Z\(T\)\\geq z\_\{0\}, withZ=ZKZ=Z\_\{\\textrm\{K\}\}forKgwandZ=ZEZ=Z\_\{\\textrm\{E\}\}forExp\. Practically,z0z\_\{0\}is the detector’s decision threshold on the standardized evidence statistic and therefore controls the Type\-I error budget\. Increasingz0z\_\{0\}makes false positives rarer but also makes true watermarks harder to detect\. ForKgw, whenZK​\(T\)Z\_\{\\textrm\{K\}\}\(T\)is approximately standard normal, a one\-sided significance levelα\\alphacorresponds toz0≈Φ−1​\(1−α\)z\_\{0\}\\approx\\Phi^\{\-1\}\(1\-\\alpha\)\. Our experiments adoptz0=4z\_\{0\}=4following prior workKirchenbaueret al\.\([2024b](https://arxiv.org/html/2606.18430#bib.bib28)\); Panet al\.\([2024a](https://arxiv.org/html/2606.18430#bib.bib30)\), which corresponds to a nominal one\-sided significance level of about3\.17×10−53\.17\\times 10^\{\-5\}\. For Exp,α\\alphais specified directly andz0≔Φ−1​\(1−α\)z\_\{0\}\\coloneqq\\Phi^\{\-1\}\(1\-\\alpha\)is the equivalent threshold for the z\-test\.

Phase 1: Offline Signature GenerationPhase 2: Online Detection PipelineTrain DataColor/ScoreGen\. Constr\.MILP SolverSignatureInputTTDetectorZ≥z0Z\\geq z\_\{0\}Filter\|T′\|≥n0\|T^\{\\prime\}\|\\\!\\geq\\\!n\_\{0\}DetectorZ′≥z0Z^\{\\prime\}\\\!\\geq z\_\{0\}“Watermarked”“Natural”YesNoInjectYesNoYesNo

Figure 2:Flowchart of our two\-stage watermark detection framework\.Signature filtering\.A*signature*S⊆𝒱S\\subseteq\\mathcal\{V\}is a set of*token types*computed during or after text generation\. LetZ​\(T\)Z\(T\)denote the scheme\-specific test statistic\. A detector equipped with a signatureSSproceeds in two stages \(Fig\.[2](https://arxiv.org/html/2606.18430#S3.F2)\)\. First, the detector performs the baseline test on the input textTT, and declares “watermarked” ifZ​\(T\)≥z0Z\(T\)\\geq z\_\{0\}\. Otherwise, it deletes fromTTall tokens whose types belong toSS, producing a residual textT′T^\{\\prime\}\. The detector then re\-runs the same baseline test onT′T^\{\\prime\}, computesZ′≔Z​\(T′\)Z^\{\\prime\}\\coloneqq Z\(T^\{\\prime\}\), and declares “watermarked” ifZ′≥z0Z^\{\\prime\}\\geq z\_\{0\}and\|T′\|≥n0\|T^\{\\prime\}\|\\geq n\_\{0\}, a threshold for the filtered text length\. We setn0=30n\_\{0\}=30throughout this paper\.111ForKgw,ZKZ\_\{\\textrm\{K\}\}is a z\-test that relies on a normal approximation of a binomial evidence count\. Here,n0=30n\_\{0\}=30is a standard conservative rule of thumb to keep this approximation accurate \(see e\.g\.,Hogget al\.\([2015](https://arxiv.org/html/2606.18430#bib.bib23)\), and also[B](https://arxiv.org/html/2606.18430#A2)for an explicit tail\-bound characterization\)\. ForExp, the Gamma\-tail p\-value remains exact underℋ0\\mathcal\{H\}\_\{0\}forany\|T′\|≥1\|T^\{\\prime\}\|\\geq 1, but we adopt the samen0n\_\{0\}as a minimum\-evidence guardrail, keeping the two\-stage procedure uniform across watermark schemes\.

Since filtering is only applied when the baseline test fails, the only error it may introduce is to flip an otherwise correct “TTis unwatermarked” decision underℋ0\\mathcal\{H\}\_\{0\}\. The error probability induced by the filter is thereforeℙerror≔ℙ\(Z′≥z0∣Z<z0,ℋ0\)\\mathbb\{P\}\_\{\\mathrm\{error\}\}\\coloneqq\\mathbb\{P\}\(Z^\{\\prime\}\\geq z\_\{0\}\\mid Z<z\_\{0\},\\;\\mathcal\{H\}\_\{0\}\)\. This probability is a*conditional*Type\-I error: it measures how often filtering overturns a baseline acceptance ofℋ0\\mathcal\{H\}\_\{0\}when the underlying text is unwatermarked\.

Null calibration after filtering\.ForKgw, under the standard coloring model, the hidden green indicators\{𝟏​\{ti∈Gi\}\}i=1n\\\{\\mathbf\{1\}\\\{t\_\{i\}\\in G\_\{i\}\\\}\\\}\_\{i=1\}^\{n\}are i\.i\.d\.Ber​\(γ\)\\mathrm\{Ber\}\(\\gamma\)conditioned on the secret key\. Since our filter depends only onTTand does not access the key, restricting to the retained indices preserves this law\. Thus,ZK​\(T′\)Z\_\{\\textrm\{K\}\}\(T^\{\\prime\}\)has the same null calibration as the original testZK​\(T\)Z\_\{\\textrm\{K\}\}\(T\), and its𝒩​\(0,1\)\\mathcal\{N\}\(0,1\)approximation improves with the residual lengthn′≔\|T′\|n^\{\\prime\}\\coloneqq\|T^\{\\prime\}\|\. We therefore enforcen′≥n0n^\{\\prime\}\\geq n\_\{0\}before acting on the post\-filter statistic\. ForExp, each retained pseudorandom scalarRi=ui​\[ti\]R\_\{i\}=u\_\{i\}\[t\_\{i\}\]is𝒰​\[0,1\]\\mathcal\{U\}\[0,1\]underℋ0\\mathcal\{H\}\_\{0\}\. The retained scorescic\_\{i\}’s remain i\.i\.d\.Exp​\(1\)\\mathrm\{Exp\}\(1\)and the post\-filter sumXT′≔∑i=1n′ciX\_\{T^\{\\prime\}\}\\coloneqq\\sum\_\{i=1\}^\{n^\{\\prime\}\}c\_\{i\}satisfiesXT′∼Γ​\(n′,1\)X\_\{T^\{\\prime\}\}\\sim\\Gamma\(n^\{\\prime\},1\), which impliespE​\(T′\)∼𝒰​\[0,1\]p\_\{\\textrm\{E\}\}\(T^\{\\prime\}\)\\sim\\mathcal\{U\}\[0,1\]andZE​\(T′\)∼𝒩​\(0,1\)Z\_\{\\textrm\{E\}\}\(T^\{\\prime\}\)\\sim\\mathcal\{N\}\(0,1\)in the Gamma model for anyn′≥1n^\{\\prime\}\\geq 1\. Thus, the statistic computed on the filtered natural text remains correctly calibrated for the baseline watermark test, provided the filter relies on observed content rather than on secret color or score assignments\. On the other hand, giving the detector a second chance to reject the null hypothesis does introduce an additional false positive risk, which is captured by the conditional error probabilityℙerror\\mathbb\{P\}\_\{\\mathrm\{error\}\}defined earlier\. Sec\.[5](https://arxiv.org/html/2606.18430#S5)explores this risk further under distributionally correlated and stronger adversarial settings, relaxing the assumption of null calibration after filtering\.

## 4Method

### 4\.1MILP\-based Signature Generation

Given a set of token types𝒱\\mathcal\{V\}and a training corpus𝒯\\mathcal\{T\}, we seek a signatureS⊆𝒱S\\subseteq\\mathcal\{V\}: ifSScontains a token typeww, then all tokens with the same type will be ignored when we compute the test statistic for a text\. For eachw∈𝒱w\\in\\mathcal\{V\}, we define binary decision variablesxwx\_\{w\}such thatxw=0x\_\{w\}=0meanswwshould be included inSS\.

Kgw\-style watermarks\.Fix a textTT\. Letcwc\_\{w\}denote the number of tokens inTTthat have typeww, andgwg\_\{w\}denote the number of its green occurrences\. LetNNandN′N^\{\\prime\}be the number of tokens inTTbefore and after filtering, andNgN\_\{g\}andNg′N\_\{g\}^\{\\prime\}be the number of green tokens inTTbefore and after filtering\. Then we can write

N=∑w∈𝒱cw,N′=∑w∈𝒱cw​xw,Ng=∑w∈𝒱gw,Ng′=∑w∈𝒱gw​xw\.\\displaystyle N=\\sum\\nolimits\_\{w\\in\\mathcal\{V\}\}c\_\{w\},\\quad N^\{\\prime\}=\\sum\\nolimits\_\{w\\in\\mathcal\{V\}\}c\_\{w\}\\,x\_\{w\},\\quad N\_\{g\}=\\sum\\nolimits\_\{w\\in\\mathcal\{V\}\}g\_\{w\},\\quad N\_\{g\}^\{\\prime\}=\\sum\\nolimits\_\{w\\in\\mathcal\{V\}\}g\_\{w\}\\,x\_\{w\}\.\(1\)Letppbe a constant chosen so thatNg′≥p​N′\{N\_\{g\}^\{\\prime\}\}\\geq pN^\{\\prime\}impliesZK​\(T\)≥z0Z\_\{\\textrm\{K\}\}\(T\)\\geq z\_\{0\}\(see later\)\. Note that

Ng′−p​N′=∑w∈𝒱\(gw−p​cw\)​xw\\displaystyle\{N\_\{g\}^\{\\prime\}\}\-pN^\{\\prime\}\\;=\\;\\sum\\nolimits\_\{w\\in\\mathcal\{V\}\}\\,\(g\_\{w\}\-p\\,c\_\{w\}\)\\,x\_\{w\}\(2\)is a linear function over the decision variables\{xw:w∈𝒱\}\\\{x\_\{w\}:w\\in\\mathcal\{V\}\\\}\.

For each textT∈𝒯T\\in\\mathcal\{T\}, we define an indicator variableyTy\_\{T\}such thatyT=1⟺Ng′≥p​N′y\_\{T\}=1\\Longleftrightarrow\{N\_\{g\}^\{\\prime\}\}\\geq pN^\{\\prime\}\\\!forTT\. We thus reduce signature generation to an optimization problem; any solution\{xw\}\\\{x\_\{w\}\\\}that maximizes∑T∈𝒯yT\\sum\_\{T\\in\\mathcal\{T\}\}y\_\{T\}corresponds to a signature maximizing the post\-filter detection rate of the corpus𝒯\\mathcal\{T\}and vice versa\.

Finally, we specify the constantppfor each textTTsuch thatNg′≥p​N′\{N\_\{g\}^\{\\prime\}\}\\geq pN^\{\\prime\}ensures that the residual textT′T^\{\\prime\}after filtering is declared watermarked by the detector\. ForKgw,ZK​\(T\)≥z0Z\_\{\\textrm\{K\}\}\(T\)\\geq z\_\{0\}holds if and only if

Ng′≥γ​N′\+z0​N′​γ​\(1−γ\)=\(γ\+z0​γ​\(1−γ\)/N′\)⋅N′\.\\displaystyle N\_\{g\}^\{\\prime\}\\;\\;\\geq\\;\\;\\gamma N^\{\\prime\}\+z\_\{0\}\\sqrt\{N^\{\\prime\}\\,\\gamma\(1\-\\gamma\)\}\\;=\\;\(\\gamma\+z\_\{0\}\\sqrt\{\\gamma\(1\-\\gamma\)/N^\{\\prime\}\}\)\\cdot N^\{\\prime\}\.\(3\)WhenN′N^\{\\prime\}is sufficiently large, that is, whenN′≥γ​\(1−γ\)⋅\[z0/\(p−γ\)\]2,N^\{\\prime\}\\geq\\gamma\(1\-\\gamma\)\\cdot\[z\_\{0\}/\(p\-\\gamma\)\]^\{2\},we can safely replace \([3](https://arxiv.org/html/2606.18430#S4.E3)\) with a sufficient conditionNg′≥p​N′\{N\_\{g\}^\{\\prime\}\}\\geq pN^\{\\prime\}\. For example, whenγ=0\.5\\gamma=0\.5andz0=4z\_\{0\}=4, we can setp=0\.87p=0\.87to makeNg′≥p​N′\{N\_\{g\}^\{\\prime\}\}\\geq pN^\{\\prime\}a criterion for detecting watermarks in texts with filtered lengthN′≥30N^\{\\prime\}\\geq 30\. This linear approximation makes signature selection amenable to an MILP solver, with an objective to maximize the post\-filter detection rate of the training corpus\. Because the coefficients in the MILP are computed from green counts determined by the watermark key, the resulting signature is specific to that key and must be recomputed after key rotation\.

Exp\-style watermarks\.We now describe how the same MILP idea applies toExp\. Given a textTT, theExpdetector assigns each tokentit\_\{i\}a scoreci≔−ln⁡\(1−Ri\)c\_\{i\}\\coloneqq\-\\ln\(1\-R\_\{i\}\)and uses the text\-level statisticX≔∑iciX\\coloneqq\\sum\_\{i\}c\_\{i\}\(Sec\.[3](https://arxiv.org/html/2606.18430#S3)\)\. After applying a signatureSSand retaining only token types withxw=1x\_\{w\}=1, the residual textT′T^\{\\prime\}has lengthN′N^\{\\prime\}as above and accumulated scoreX′≔∑i:ti∉Sci\.X^\{\\prime\}\\coloneqq\\sum\_\{i:\\,t\_\{i\}\\notin S\}c\_\{i\}\.Analogous to theKgwcase, we define

gw≔∑i:ti=wci,X′=∑w∈𝒱gw​xw,X′−p​N′=∑w∈𝒱\(gw−p​cw\)​xw\.\\displaystyle g\_\{w\}\\;\\coloneqq\\;\\sum\\nolimits\_\{i:\\,t\_\{i\}=w\}c\_\{i\},\\quad X^\{\\prime\}=\\sum\\nolimits\_\{w\\in\\mathcal\{V\}\}g\_\{w\}\\,x\_\{w\},\\quad X^\{\\prime\}\-pN^\{\\prime\}=\\sum\\nolimits\_\{w\\in\\mathcal\{V\}\}\(g\_\{w\}\-p\\,c\_\{w\}\)\\,x\_\{w\}\.\(4\)[A](https://arxiv.org/html/2606.18430#A1)shows how to derive a constantppsuch thatX′≥p​N′X^\{\\prime\}\\geq pN^\{\\prime\}is sufficient for theExpdetector to declareT′T^\{\\prime\}watermarked, i\.e\., it impliespE​\(T′\)<αp\_\{\\textrm\{E\}\}\(T^\{\\prime\}\)<\\alpha\. We can employ the same MILP structure as above forExp, but replace theKgwconstraintNg′≥p​N′N\_\{g\}^\{\\prime\}\\geq pN^\{\\prime\}with theExpconstraintX′≥p​N′X^\{\\prime\}\\geq pN^\{\\prime\}\. Intuitively,ppinduces a red\-green split forExp: tokens with scoresci<pc\_\{i\}<pbehave as*red*evidence, and signature filtering aims to remove such low\-score tokens so that the average retained score per token exceeds the thresholdpp\.

It is worth noting that our formulation of optimal signature selection is computationally equivalent to the*Maximum Feasible Subsystem \(Max\-FS\) of 0–1 Linear Inequalities*Amaldi and Kann \([1995](https://arxiv.org/html/2606.18430#bib.bib59)\)\. A Max\-FS has a set of linear inequalities of the form∑j=1nai,j​xj≥0\\sum\_\{j=1\}^\{n\}a\_\{i,j\}\\,x\_\{j\}\\geq 0; the task is to find a binary assignment tox1,…,xnx\_\{1\},\\dots,x\_\{n\}that maximizes the number of satisfied inequalities\. Finding an optimal signature can be reduced to solving a Max\-FS problem\. The Max\-FS literature has developed specialized solversPfetsch \([2008](https://arxiv.org/html/2606.18430#bib.bib25)\)and fast relaxation heuristics \(e\.g\.,Firouzehet al\.\([2022](https://arxiv.org/html/2606.18430#bib.bib1)\)\) that are highly effective in practice\. Thus, signature generation can leverage the rich algorithmic toolkit for Max\-FS to enhance practical scalability\.

### 4\.2Context\-Sensitive Token Selection

A signature that amplifies watermark signals aims to reduce red evidence while preserving green evidence\. However, treating a token type as either always kept or always deleted is often too coarse\. In a document, the same type may appear as red in one position and green in another, so uniform deletion either leaves residual red noise or discards valuable green evidence\.

To address this granularity gap, we extend type\-level signatures to context\-sensitive*nn\-gram signatures*\. Here, “context\-sensitive” means that retention decisions are conditioned on a contiguous neighborhood of token types\. Concretely, instead of assigning a single delete decision to each token type, the signature is parameterized by admissiblenn\-grams, and token retention is induced by whether thenn\-grams that cover a token are admissible\. This formulation can, for example, suppress a red\-leaning local pattern when it occurs in a specific surrounding token\-type configuration, while preserving other occurrences of the same token types in different local contexts\. Whenn=1n=1, this scheme degenerates to the original type\-level \(no\-context\) filter; increasingnnprovides finer control over which recurring local fragments are removed\. In our experiments, modest values ofnnyield substantial detection gains in weak\-signal settings\.

To illustrate, assume that each English word corresponds to one token type\. Consider the sequence

T=⟨analysis,of,the,data,is,of,interest,to,the,community⟩\.T=\\langle\\texttt\{analysis\},\\ \\texttt\{of\},\\ \\texttt\{the\},\\ \\texttt\{data\},\\ \\texttt\{is\},\\ \\texttt\{of\},\\ \\texttt\{interest\},\\ \\texttt\{to\},\\ \\texttt\{the\},\\ \\texttt\{community\}\\rangle\.Suppose the optimized 2\-gram signature declares the 2\-gram\(of,the\)\(\\texttt\{of\},\\texttt\{the\}\)inadmissible while keeping all other observed 2\-grams admissible\. Under our 2\-gram retention rule \(a token is kept iffalllength\-22windows that cover it are admissible\), the filtered text becomes

T′=⟨analysis,data,is,of,interest,to,the,community⟩\.T^\{\\prime\}=\\langle\\texttt\{analysis\},\\ \\texttt\{data\},\\ \\texttt\{is\},\\ \\texttt\{of\},\\ \\texttt\{interest\},\\ \\texttt\{to\},\\ \\texttt\{the\},\\ \\texttt\{community\}\\rangle\.In this example, each of the token typesofandtheappears twice, yet the filter removes only theof theoccurrence\. By comparison, a type\-level \(1\-gram\) signature would have to deleteofortheeverywhere to eliminateof the, which would potentially discard useful green evidence\.

MILP encoding\.Annn\-gram signature can be viewed as selecting a set of*admissible local contexts*\(thenn\-grams\), and then retaining only those token occurrences whose surrounding contexts are admissible\. This leads to a standard incidence\-based 0–1 formulation where binary variables choose which contexts are allowed, and constraints propagate these choices to token occurrences\. We use two kinds of binary variables:

- •xw=1x\_\{w\}=1indicates that the token typew∈𝒱w\\in\\mathcal\{V\}is retained after filtering;
- •yτ1,…,τn=1y\_\{\\tau\_\{1\},\\dots,\\tau\_\{n\}\}=1indicates that thenn\-gram\(τ1,…,τn\)∈𝒱n\(\\tau\_\{1\},\\dots,\\tau\_\{n\}\)\\in\\mathcal\{V\}^\{n\}is declared admissible by the signature\.

Concretely, consider the 2\-gram case\. Any interior positionjj\(i\.e\.,2≤j≤m−12\\leq j\\leq m\-1for\|T\|=m\|T\|=m\) is covered by two 2\-grams, so the retention rule is the Boolean conjunctionxtj=ytj−1,tj∧ytj,tj\+1\.x\_\{t\_\{j\}\}=y\_\{t\_\{j\-1\},\\,t\_\{j\}\}\\wedge y\_\{t\_\{j\},\\,t\_\{j\+1\}\}\.Boundary positions are handled by the 2\-gramsxt1=yt1,t2x\_\{t\_\{1\}\}=y\_\{t\_\{1\},\\,t\_\{2\}\}andxtm=ytm−1,tmx\_\{t\_\{m\}\}=y\_\{t\_\{m\-1\},\\,t\_\{m\}\}\. These Boolean constraints can be encoded using the standard 0–1 linearizationWolsey \([1998](https://arxiv.org/html/2606.18430#bib.bib22)\); the objective function and corpus\-level regularization remain the same as in Sec\.[4\.1](https://arxiv.org/html/2606.18430#S4.SS1)\. Generally, any feasible assignment to\{yτ1,…,τn\}\\\{y\_\{\\tau\_\{1\},\\dots,\\tau\_\{n\}\}\\\}in this MILP defines annn\-gram signatureS:=\{\(τ1,…,τn\)∈𝒱n:yτ1,…,τn=0\}S:=\\\{\(\\tau\_\{1\},\\dots,\\tau\_\{n\}\)\\in\\mathcal\{V\}^\{n\}:y\_\{\\tau\_\{1\},\\dots,\\tau\_\{n\}\}=0\\\}\.

Note that a naive formulation of annn\-gram signature introducesO​\(kn\)O\(k^\{n\}\)binary decision variables, wherekkis the number of distinct token types\. We mitigate this blow\-up by considering only*effective*nn\-grams, i\.e\., thenn\-grams whose removal would discard strictly more red than green tokens, since removing ineffectivenn\-grams only weakens the watermark signal or leaves it unchanged\. This optimization drastically reduces the number of decision variables needed, keeping the MILP within the reach of off\-the\-shelf solvers\.

## 5Asymptotic False\-Positive Analysis

While signature filtering can boost the TPR, an overly aggressive filter can also raise the FPR by making an ordinary text look artificially “watermark\-heavy” after deletion\. The mechanism behind this risk depends on the underlying watermark family\. InKgw\-style schemes, the evidence is the \(hidden\) green/red coloring of tokens, and deleting tokens can change the observed green fraction in ways that are potentially harmful for adversarial or correlated data\. InExp\-style schemes, the evidence is a keyed pseudorandom score per realized token, and a filter that depends only on the observed token sequence cannot cherry\-pick unusually largeExpscores\. Consequently, filtering is intrinsically more robust forExpthan forKgw\.

In Secs[5\.1](https://arxiv.org/html/2606.18430#S5.SS1)–[5\.3](https://arxiv.org/html/2606.18430#S5.SS3), we analyzeKgwunder three threat models: \(i\) a signature\-aware but color\-blind attacker, \(ii\) a signature\-aware and color\-adaptive attacker, and \(iii\) distributionally correlated signatures without an active attacker\. These results show whenKgwfiltering is guaranteed to be safe: deleting a number of tokens that grows linearly with the text length is essentially harmless under the standard coloring assumption, but adversarial or correlated deletions on the order ofn\\sqrt\{n\}can potentially degrade detection in weaker conditions\. We summarize the corresponding false\-positive guarantees forExpin Sec\.[5\.5](https://arxiv.org/html/2606.18430#S5.SS5)\.

Throughout the analyses, we fix a z\-score thresholdz\>0z\>0and a tolerance error levelε∈\(0,1\)\\varepsilon\\in\(0,1\)\. For theKgw\-specific bounds, we additionally fix a green ratioγ∈\(0,1\)\\gamma\\in\(0,1\)\. ForExp, we writez≔Φ−1​\(1−α\)z\\coloneqq\\Phi^\{\-1\}\(1\-\\alpha\)for the detector’s significance levelα\\alpha\. The error probability of a filter is defined byℙerror≔ℙ\(Z′≥z∣Z<z,ℋ0\)\\mathbb\{P\}\_\{\\mathrm\{error\}\}\\coloneqq\\mathbb\{P\}\(Z^\{\\prime\}\\geq z\\mid Z<z,\\mathcal\{H\}\_\{0\}\), as discussed in Sec\.[3](https://arxiv.org/html/2606.18430#S3)\. Full proofs of the theorems can be found in the appendices\.

### 5\.1Signature\-Aware but Color\-Blind Attacker

Under this threat model, the attacker has observed the entire signature before crafting the text\. She may choose any tokens in the text, but has no control over the color of each token\. This “color\-blind” assumption aligns with the standard setting of allKgw\-style watermarks, where the hash seed that partitions the vocabulary is opaque to external users\. In this setting, a linear deletion budget is sufficient to make the signature filter provably resilient to even a fully signature\-aware adversary\.

###### Theorem 1\.

For every sufficiently large text lengthnn, one can compute a boundssafe=Θ​\(n\)s\_\{\\mathrm\{safe\}\}=\\Theta\(n\)such that any signature filter that deletes at mostssafes\_\{\\mathrm\{safe\}\}tokens guaranteesℙerror≤ε\\mathbb\{P\}\_\{\\mathrm\{error\}\}\\leq\\varepsilon\.

Theorem[1](https://arxiv.org/html/2606.18430#Thmtheorem1)shows that signature filtering behaves as a bounded perturbation of the baseline z\-test whenever the filter operates within this linear deletion regime\. This result is a conservative worst\-case estimate: in practice, it offers a simple rule of thumb for configuring deletion budgets, which can be refined by empirical calibration in specific deployments\.

### 5\.2Signature\-Aware and Color\-Adaptive Attacker

In this scenario, the attacker not only knows the deployed signature but can also freely choose both the tokens and their colors when crafting a text\. This setting corresponds to a fully compromised watermark, e\.g\., the attacker has effectively learned the secret partition of the watermarkReynoldset al\.\([2025](https://arxiv.org/html/2606.18430#bib.bib51)\)\. Theorem[2](https://arxiv.org/html/2606.18430#Thmtheorem2)characterizes how much adversarial editing is needed to overturn a robustly correct unwatermarked decision under full color control\. Specifically, when the pre\-filter z\-score lies below the threshold by a fixed margin, a deletion budget of orderΘ​\(n\)\\Theta\(\\sqrt\{n\}\)is both sufficient and necessary to*deterministically*flip the decision\. This result holds independently of the coloring assumption behind the watermark\.

###### Theorem 2\.

Fix a constantη\>0\\eta\>0\. For every sufficiently large text lengthnn, a color\-adaptive attacker who knows the signature can construct a text withZ≤z−ηZ\\leq z\-\\etasuch that deletingO​\(n\)O\(\\sqrt\{n\}\)tokens ensuresℙerror=1\\mathbb\{P\}\_\{\\mathrm\{error\}\}=1\. Conversely, for any text withZ≤z−ηZ\\leq z\-\\eta, no deterministic flip is possible witho​\(n\)o\(\\sqrt\{n\}\)deletions\.

We note that a color\-adaptive attacker already has enough power to break the watermark without filtering\. In such case, the underlying watermark has lost its secrecy, and no detection‑time module can repair it\. If color‑adaptive threats are considered plausible, the appropriate response is to refresh the watermark key or combine watermarking with additional provenance signals\.

### 5\.3Distributionally Correlated Signatures

In practice, a signature might be deployed on the same distribution that informed the signature selection, e\.g\., when the training corpus shares low\-entropy phrases such as boilerplate fragments or topical keywords with a benign user text\. Hence, the red tokens removed by the filter are no longer a random sample, but a biased subset of the text\. Theorem[3](https://arxiv.org/html/2606.18430#Thmtheorem3)formalizes the*worst case*in this setting:n\\sqrt\{n\}\-scale adversarial deletions is necessary and sufficient to flip a decision with an arbitrarily high probability given admissible parameters\.

###### Theorem 3\.

Suppose that the attacker can choose the colors of the removed tokens with a deletion budgets≥0s\\geq 0\. We can compute constantsc=c​\(z,γ\)c=c\(z,\\gamma\)andzεz\_\{\\varepsilon\}such that for all sufficiently large text lengthnn, \(i\) ifs≤⌊c​n⌋s\\leq\\lfloor c\\sqrt\{n\}\\rfloorandz≥zεz\\geq z\_\{\\varepsilon\}, then it holds thatℙerror≤ε\\mathbb\{P\}\_\{\\mathrm\{error\}\}\\leq\\varepsilon; \(ii\) ifε∈\(0,12\)\\varepsilon\\in\(0,\\tfrac\{1\}\{2\}\), then there exists a constantcflip\>cc\_\{\\mathrm\{flip\}\}\>csuch thats≥⌈cflip​n⌉s\\geq\\lceil c\_\{\\mathrm\{flip\}\}\\sqrt\{n\}\\rceilimpliesℙerror≥1−ε\\mathbb\{P\}\_\{\\mathrm\{error\}\}\\geq 1\-\\varepsilon\.

Theorem[3](https://arxiv.org/html/2606.18430#Thmtheorem3)describes a worst\-case scenario that principled signature designs should avoid\. This scenario occurs when a signature is too closely tuned to the deployment data and becomes strongly correlated with natural text\. Existing entropy\- and semantics\-aware methods can reduce this correlation by down\-weighting predictable or stale patternsLeeet al\.\([2024](https://arxiv.org/html/2606.18430#bib.bib32)\); Luet al\.\([2024](https://arxiv.org/html/2606.18430#bib.bib29)\); Heet al\.\([2024](https://arxiv.org/html/2606.18430#bib.bib34)\)\. Because low\-entropy phrases tend to appear in both natural and watermarked textKirchenbaueret al\.\([2024a](https://arxiv.org/html/2606.18430#bib.bib27)\), penalizing such phrases during signature learning or filtering steers the system toward the linear\-safe regime of Theorem[1](https://arxiv.org/html/2606.18430#Thmtheorem1)\. In effect, we give up a small amount of best\-case TPR to gain a lower worst\-case FPR\. This trade\-off is observed in our empirical comparison ofKgwandSweet\(which ignores low\-entropy tokens in the z\-test\) in Secs\.[6\.1](https://arxiv.org/html/2606.18430#S6.SS1)–[6\.3](https://arxiv.org/html/2606.18430#S6.SS3)\.

### 5\.4Signature Filtering forUnigramWatermarks

In this subsection, we replaceKgw’s stepwise coloring scheme with the*unigram coloring assumption*byUnigramZhaoet al\.\([2023](https://arxiv.org/html/2606.18430#bib.bib31)\), where each token typeτ∈𝒱\\tau\\in\\mathcal\{V\}receives a single random colorCτ∼Ber​\(γ\)C\_\{\\tau\}\\sim\\mathrm\{Ber\}\(\\gamma\)that is reused by all of its occurrences in the text\. Formally, letℓ\\ellbe the number of distinct token types in a natural text, and\{mτ\}τ∈𝒱\\\{m\_\{\\tau\}\\\}\_\{\\tau\\in\\mathcal\{V\}\}be the pre\-filter type multiplicities, namely,mτm\_\{\\tau\}is the number of tokens of typeτ∈𝒱\\tau\\in\\mathcal\{V\}in the text\. Writen=∑τ∈𝒱mτn=\\sum\_\{\\tau\\in\\mathcal\{V\}\}m\_\{\\tau\},Q=∑τ∈𝒱mτ2Q=\\sum\_\{\\tau\\in\\mathcal\{V\}\}m\_\{\\tau\}^\{2\},r=Q/nr=\{Q\}/\{n\}, and define their post\-filter analoguesn′n^\{\\prime\},Q′Q^\{\\prime\},r′r^\{\\prime\}\. Note that under unigram coloring, a filter either keeps or removes each type in full \(somτ′∈\{0,mτ\}m^\{\\prime\}\_\{\\tau\}\\in\\\{0,m\_\{\\tau\}\\\}\)\.

###### Theorem 4\.

Assume that no single token type carries a non\-vanishing fraction of the text, e\.g\.,maxτ⁡mτ/n→0\\max\_\{\\tau\}m\_\{\\tau\}/n\\to 0asℓ→∞\\ell\\to\\infty\. Then there exists a constantβ=β​\(ε;z,γ,r,r′\)∈\(0,1\)\\beta=\\beta\(\\varepsilon;z,\\gamma,r,r^\{\\prime\}\)\\in\(0,1\)such that for allℓ\\ellsufficiently large,Q′≥β​QQ^\{\\prime\}\\geq\\beta Qimpliesℙ​\(Z′≥z∣Z<z\)≤ε\\mathbb\{P\}\(Z^\{\\prime\}\\geq z\\mid Z<z\)\\leq\\varepsilon\.

Theorem[4](https://arxiv.org/html/2606.18430#Thmtheorem4)delineates the*type\-level*safe deletion budget for a signature\. Intuitively, it shows that the right “sample size” for unigram coloring is the*type\-mass*Q=∑τmτ2Q=\\sum\_\{\\tau\}m\_\{\\tau\}^\{2\}: the correlation between the pre\-filter and post\-filter texts isρ=Q′/Q\\rho=\\sqrt\{Q^\{\\prime\}/Q\}, and it is sufficient to keep a constant fraction ofQQ\. By contrast, Theorem[1](https://arxiv.org/html/2606.18430#Thmtheorem1)provides a safe budget for removable tokens: keeping a constant fraction of tokensn′/n≥cn^\{\\prime\}/n\\geq csuffices to control the false\-positive risk with a pre/post correlationρ=n′/n\\rho=\\sqrt\{n^\{\\prime\}/n\}underKgwcoloring\. In intuition,Q/n2=∑τ\(mτ/n\)2Q/n^\{2\}=\\sum\_\{\\tau\}\(m\_\{\\tau\}/n\)^\{2\}measures how concentrated repetition is, and a safe budget must preserve the mass carried by frequent types\. Technically, both theorems arise from the same bivariate normal approximation with a vanishing remainder\. They differ only in the correlation parameter, namelyn′/n\\sqrt\{n^\{\\prime\}/n\}at the token level versusQ′/Q\\sqrt\{Q^\{\\prime\}/Q\}at the type level, and thus the natural linear budgets are innnversus inQQ\.

### 5\.5Signature Filtering forExpWatermarks

The preceding subsections focus onKgwandUnigram, where the post\-filter z\-score can change substantially because the filter removes a non\-random subset of evidence\. ForExp, watermarking is typically more robust\. Recall that, underℋ0\\mathcal\{H\}\_\{0\},Expassigns each realized token a keyed pseudorandom scalarRi=ui​\[ti\]∼𝒰​\[0,1\]R\_\{i\}=u\_\{i\}\[t\_\{i\}\]\\sim\\mathcal\{U\}\[0,1\]and a scoreci=−ln⁡\(1−Ri\)∼Exp​\(1\)c\_\{i\}=\-\\ln\(1\-R\_\{i\}\)\\sim\\mathrm\{Exp\}\(1\), and it computes a p\-value against a thresholdα\\alphaof significance level\. Define a “score secrecy” condition that \(i\) the signature depends only on the observed tokens and does not access these hidden random values, and \(ii\) the per\-position vectorsuiu\_\{i\}and realized scalarsRiR\_\{i\}are not manipulatable or predictable by the adversary\. When this condition holds, we can derive a universal worst\-case risk bound that does not require a safe deletion budget in the sense of Sec\.[5\.1](https://arxiv.org/html/2606.18430#S5.SS1)\.

###### Theorem 5\.

Under the score secrecy assumption,ℙerror≤α/\(1−α\)\\mathbb\{P\}\_\{\\mathrm\{error\}\}\\leq\\alpha/\(1\-\\alpha\)holds for any signature filter\.

Intuitively, for anExpdetector under score secrecy, each retained token in the natural text contributes a fresh random value drawn from the same null distribution, and the test explicitly recalibrates to the retained lengthn′n^\{\\prime\}\. Deleting tokens based on their*content*is therefore like discarding some draws without seeing their random values: it does not allow the filter to systematically increase the length\-normalized accumulated score\. Below, we briefly discuss theExpanalogues of the threat models we have considered forKgw:

- •*Signature\-aware but score\-blind attacker\.*Theorem[5](https://arxiv.org/html/2606.18430#Thmtheorem5)holds when the attacker can fully adapt the text to the deployed signature, but cannot infer or influence the hiddenExppseudorandom scores\.
- •*Distributionally correlated signatures\.*Even if the signature is trained on a corpus that strongly overlaps with the deployment distribution, the deletion decisions still depend only on token patterns\. Under score secrecy, this does not bias theExpscores for a natural text, so the same theorem holds\.
- •*Score\-adaptive attacker\.*If the attacker can predict the per\-token scorescic\_\{i\}and craft a text such that the signature deletes only tokens with near\-zero scores, the same scaling in Theorem[2](https://arxiv.org/html/2606.18430#Thmtheorem2)applies:Θ​\(n\)\\Theta\(\\sqrt\{n\}\)deletions are sufficient and necessary to deterministically flip a baseline decision withZ≤z−ηZ\\leq z\-\\eta\.

In practice,α\\alphais typically set to10−410^\{\-4\}Panet al\.\([2024a](https://arxiv.org/html/2606.18430#bib.bib30)\), makingℙerror\\mathbb\{P\}\_\{\\mathrm\{error\}\}effectively negligible by Theorem[5](https://arxiv.org/html/2606.18430#Thmtheorem5)\. This robustness result is consistent with our empirical findings: in all evaluated settings, applying signature filtering toExpintroduced no observable increase in false positive rate \(≤0\.1%\\leq 0\.1\\%\) for the baseline detector\.

Clarification on scale\.We note that the false\-positive rate analyzed in this section is a per\-text quantity\. The asymptotic parameter is the token lengthnnof the examined text, not the number of texts in a corpus\. Hence, for a fixed signature filter and decision threshold, applying the detector to more documents does not by itself alter the per\-text Type\-I error guarantees\. Corpus\-level deployment, including the trade\-off between TPR and FPR induced by deploying multiple signatures, will be discussed in Sec\.[6\.3](https://arxiv.org/html/2606.18430#S6.SS3)\.

## 6Evaluation

We evaluate our method on high\-entropy natural language and low\-entropy code from standard benchmarks for watermark evaluation\. For natural\-language documents, we useC4Raffelet al\.\([2020](https://arxiv.org/html/2606.18430#bib.bib4)\)\. For low\-entropy code snippets, we useMbppAustinet al\.\([2021](https://arxiv.org/html/2606.18430#bib.bib20)\),HumanEvalChenet al\.\([2021](https://arxiv.org/html/2606.18430#bib.bib21)\), andCode\-Search\-NetHusainet al\.\([2019](https://arxiv.org/html/2606.18430#bib.bib43)\)\. Our experiments follow the standard setupKirchenbaueret al\.\([2024a](https://arxiv.org/html/2606.18430#bib.bib27)\); Panet al\.\([2024a](https://arxiv.org/html/2606.18430#bib.bib30)\): we tokenize each text, use the first 30 tokens as a prompt, and the next 200 tokens as the unwatermarked continuation\. A watermark algorithm then generates watermarked 200\-token continuations for every prompt, yielding parallel collections of watermarked and natural texts\.

We compare four watermark schemesKgw,Sweet,Unigram,ExpKirchenbaueret al\.\([2024a](https://arxiv.org/html/2606.18430#bib.bib27)\); Leeet al\.\([2024](https://arxiv.org/html/2606.18430#bib.bib32)\); Zhaoet al\.\([2023](https://arxiv.org/html/2606.18430#bib.bib31)\); Aaronson and Kirchner \([2022](https://arxiv.org/html/2606.18430#bib.bib53)\)on six LLMs: Opt\-1\.3b, Opt\-6\.7b, Llama2\-13b, Llama3\.1\-8b, Qwen2\.5\-14b, Phi\-3\-Medium\-14b\. Watermarks are embedded with the MarkLLM toolkitPanet al\.\([2024a](https://arxiv.org/html/2606.18430#bib.bib30)\), signatures are optimized with the Gurobi solverGurobi Optimization, LLC \([2024](https://arxiv.org/html/2606.18430#bib.bib48)\), and all experiments run on a computer with an Intel i9\-14900 CPU, an RTX\-5080 GPU, and 64 GB of RAM\.

### 6\.1Detection Capability of Signature Filters

![Refer to caption](https://arxiv.org/html/2606.18430v1/x1.png)

![Refer to caption](https://arxiv.org/html/2606.18430v1/x2.png)

![Refer to caption](https://arxiv.org/html/2606.18430v1/x3.png)

Figure 3:The TPR/FPR ofnn\-gram signature filtering for Llama3\.1\-8b on C4 \(top\),Mbpp\(middle\), andHumanEval\(bottom\)\. Columns correspond to Kgw, Sweet, Unigram, and Exp\. TPR \(solid curves\) is shown on the left y\-axis in linear scale, while FPR \(dashed curves\) is shown on the right y\-axis in log scale\. The x\-axis reports the signature order, where 0\-gram corresponds to the baseline detector without filtering\. The MILP solver timeout is 60 seconds per signature\.![Refer to caption](https://arxiv.org/html/2606.18430v1/x4.png)

![Refer to caption](https://arxiv.org/html/2606.18430v1/x5.png)

![Refer to caption](https://arxiv.org/html/2606.18430v1/x6.png)

![Refer to caption](https://arxiv.org/html/2606.18430v1/x7.png)

Figure 4:This figure replicates experiments in Fig\.[3](https://arxiv.org/html/2606.18430#S6.F3)across LLMs\. From top to bottom:Sweet\+C4,Sweet\+HumanEval,Exp\+C4, andExp\+HumanEval\. The results show that the qualitative trend of filtering is insensitive to the text generator\.Figs\.[3](https://arxiv.org/html/2606.18430#S6.F3)–[4](https://arxiv.org/html/2606.18430#S6.F4)summarize complementary views of signature filtering in weak\-signal settings\. Fig\.[3](https://arxiv.org/html/2606.18430#S6.F3)focuses on Llama3\.1 on high\-entropy \(C4\) and low\-entropy \(MbppandHumanEval\) texts and shows TPR/FPR bynn\-gram order\. Fig\.[4](https://arxiv.org/html/2606.18430#S6.F4)replicates the TPR/FPR curves forKgwandExpover C4 and HumanEval across five language models\.

As expected, all watermark families attain near\-optimal FPR at 0\-gram, but their TPR drops quickly as the watermark strength weakens\. Introducing annn\-gram signature consistently lifts TPR, with two caveats\. First, 1\-gram signatures are too coarse\. Since type\-level deletion by the signature ignores position\-dependent coloring, the solver seldom finds effective 1\-grams to tell apart watermarked and natural texts\. This failure mode is stark forUnigram, where token color is tied to token type across documents\. This leads the 1\-gram filter to remove the same red types in both classes, pushing both TPR and FPR to 100%\. Second, different watermarks have different sweet spots\. ForKgw\-style schemes \(Kgw,Sweet, andUnigram\), 2\-grams strike the best balance across strengths; forExp, useful signal sits in slightly longer local patterns, making 3\-gram or 4\-gram signatures more effective\.

Fig\.[4](https://arxiv.org/html/2606.18430#S6.F4)shows that these sweet spots are remarkably stable across text generators: 2–3\-gram signatures consistently deliver the largest TPR gains forKgwat low FPR, while 3–4\-grams do the same forExp\. The spread in TPR/FPR across models at a fixednn\-gram order is modest compared with the jump from 0\-gram to the bestnn\-gram filter, indicating that signature design is largely governed by the watermark family and the underlying corpus statistics rather than idiosyncrasies of a particular LLM\. Generally, high\-order patterns become more scarce as the watermark strength declines\. Hence, longnn\-grams either occur too infrequently to contribute useful deletions or over\-delete idiosyncratic fragments, reducing the effective sample and dampening detection\. This explains why, even though filtering still beats the baseline as the signal weakens, highnn\-gram orders no longer improve on the sweet spot\.

### 6\.2Detection Capability under Text Edits

![Refer to caption](https://arxiv.org/html/2606.18430v1/x8.png)

![Refer to caption](https://arxiv.org/html/2606.18430v1/x9.png)

Figure 5:The TPR/FPR ofnn\-gram signature filtering for Llama3\.1\-8b on C4 \(top\) andMbpp\(bottom\) in the low\-strength \(δ=1\\delta=1andθ=0\.8\\theta=0\.8\) and edited\-text regimes\. 0\-gram means no filter, andwmaxcorresponds to theWinMax\-enhanced baseline\.We stress\-test the signatures from Sec\.[6\.1](https://arxiv.org/html/2606.18430#S6.SS1)against five types of text edits \(seeKirchenbaueret al\.[2024b](https://arxiv.org/html/2606.18430#bib.bib28); Panet al\.[2024a](https://arxiv.org/html/2606.18430#bib.bib30)\): sentence\-level shuffling \(*scramble*\) and dilution \(*copy\-paste*25% watermarked text into a natural host\), plus three word\-level perturbations—30% deletion \(*word\-d*\), 50% synonym replacement via WordNet \(*word\-s*\), and 50% context\-aware substitution via BERT \(*word\-s\-ctx*\)\. We compare our approach withWinMaxKirchenbaueret al\.\([2024b](https://arxiv.org/html/2606.18430#bib.bib28)\), an advanced detection\-time module that enhances watermark signals to resist text edits\. Instead of testing the whole document once,WinMaxslides overlapping windows of various lengths across the text, recomputing the watermark score on each window\. The maximum per\-window score is used for the final decision\.

Fig\.[5](https://arxiv.org/html/2606.18430#S6.F5)outlines comparison results over both high\-entropy \(C4\) and low\-entropy \(Mbpp\) corpora\. Overall,Kgw\-style watermarks exhibit short\-range dependence: the 2\-gram order matches the correlation length and remains effective after edits, obtaining consistent gains overWinMax\. Increasing the signature order beyond 2\-grams generally reduces detection power: word\-level edits quickly destroy longer contexts, making higher\-order patterns more difficult to match and thereby less effective\. The contrast withExpis consistent with Sec\.[6\.1](https://arxiv.org/html/2606.18430#S6.SS1), whereExpbenefits most from higher\-order signatures even on the original texts\. Word\-level edits break the longer contexts these signatures rely on, making filtering ineffective over allnn\-gram orders\.

To quantify when the adaptive\-window scoring ofWinMaxhas an advantage, we compute a post\-hoc localization metricΔwin≔maxW⁡Z​\(W\)−Z​\(T\)\\Delta\_\{\\mathrm\{win\}\}\\coloneqq\\max\_\{W\}Z\(W\)\-Z\(T\)on the edited textTT, wheremaxW⁡Z​\(W\)\\max\_\{W\}Z\(W\)is the best window z\-score identified byWinMax, andZ​\(T\)Z\(T\)is the z\-score of the full document\. LargerΔwin\\Delta\_\{\\mathrm\{win\}\}therefore indicates that the surviving watermark evidence is more spatially concentrated, so window\-based detection has more room to improve over a single global filter\. This localization effect becomes more pronounced after edits: in the same stress test, the meanΔwin\\Delta\_\{\\mathrm\{win\}\}ofExpexceeds that ofKgw,Sweet, andUnigramby about 0\.5–1\.2 across edit types\. This indicates that surviving evidence is more spatially concentrated forExpthan forKgw\-style watermarks\. A fixed signature may therefore lose coverage of part of the surviving signal, whereasWinMaxcan re\-localize it by scanning all possible windows on the edited text\.

Accordingly, in Fig\.[5](https://arxiv.org/html/2606.18430#S6.F5),WinMaxconsistently attains higher TPR onExp, though at the cost of a slightly higher FPR due to the maximizing effect\. By contrast, signatures improve the global green ratio inKgw\-style watermarks by excising many small red clusters whose locations remain relatively stable even after editing\. Across both watermark families and corpora, filtering enhances detection with little FPR inflation, consistent with our false\-positive analyses in Sec\.[5](https://arxiv.org/html/2606.18430#S5)\.

### 6\.3Scalability of Signature Filters

Table 1:Watermark performance on the first50​k\\mathrm\{50k\}texts inCode\-Search\-Net\(left block\) and C4 \(right block\) under a 60s soft time limit per signature\. This table fixesB=1​kB\\\!=\\\!\\mathrm\{1k\}and variesGG, shifting from the most aggressive bagging \(G=1​kG\\\!=\\\!\\mathrm\{1k\}\) to no bagging \(G=50​kG\\\!=\\\!\\mathrm\{50k\}\)\. The columns show the TPR, FPR, and F1 Score of the watermark schemes in percent\. The last row provides the average computation time for each signature\. The average filtering time is within milliseconds per signature\.Table 2:Ablation onBBwithG=1\.2G\\\!=\\\!1\.2k, evaluated on the first 1\.2k texts inCode\-Search\-Net\(left block\) and C4 \(right block\)\.To evaluate the performance of signature filtering over large corpora, we consider a parameterized deployment strategy called*Bag\(BB,GG\)*\. At generation time, the training data is divided into groups ofG≥1G\\geq 1texts\. For each group, we compute a signature on the firstB≤GB\\leq Gtexts in that group\. At detection time, all group signatures are applied to the input document, and the largest z\-score is used for the decision\.

Tables[1](https://arxiv.org/html/2606.18430#S6.T1)–[2](https://arxiv.org/html/2606.18430#S6.T2)report end\-to\-end performance of signature filtering over 50k low\-entropyCode\-Search\-NetPython snippets and 50k high\-entropyC4documents on Opt\-1\.3b\. We focus on the low strength regimeδ=0\.5\\delta=0\.5andθ=0\.3\\theta=0\.3, using signatures of 2\-grams forKgwandSweet, 3\-grams forUnigram, and 4\-grams forExp\. Table[1](https://arxiv.org/html/2606.18430#S6.T1)fixesB=1​kB\\\!=\\\!\\mathrm\{1k\}and considersG∈\{G\\in\\\{1k, 10k, 25k, 50k\}\\\}over the entire datasets, while Table[2](https://arxiv.org/html/2606.18430#S6.T2)fixesG=1\.2​kG\\\!=\\\!\\mathrm\{1\.2k\}and considersB∈\{B\\in\\\{1\.2k, 0\.6k, 0\.4k, 0\.3k\}\\\}over the first 1\.2k texts\. Several patterns emerge:

- •Kgw/Sweetmaintains a controllable TPR–FPR frontier\.OnCode\-Search\-Net, Bagging attains near\-optimal TPR \(99%\) with low FPR \(1–4%\) forG=1​kG\\\!=\\\!\\mathrm\{1k\}\. IncreasingGtrades a small TPR loss for further FPR reductions\. On C4, the same frontier shifts upward in FPR forG=1​kG\\\!=\\\!\\mathrm\{1k\}, whileG=25​kG\\\!=\\\!\\mathrm\{25k\}tightens FPR to single digits at modest TPR cost\. These patterns reflect the effect of text entropy: high\-entropy corpora demand largerGGto suppress spurious red clusters\.
- •Unigramshows local\-context reins in FPR\.Using 3\-grams markedly lowers FPR relative to shorter context: on C4, FPR lands in the 1–3% range across modes with high TPR; on Code\-Search\-Net, FPR is higher but now bounded near 10–14%\. The gain comes from breaking type\-level coupling with light contextualization, which curbs the spurious flips seen with lower\-order filters\.
- •Expachieves near\-zero FPR with strength\-dependent TPR\.In Table[1](https://arxiv.org/html/2606.18430#S6.T1),Expconsistently exhibits near\-zero false positives, while its true positive rates vary in the expected way with mode coverage\. BecauseExpevidence tends to appear in short bursts, larger group sizes can miss some group\-specific local structure and thus lose recall\. ForG=50​kG\\\!=\\\!\\mathrm\{50k\}, filtering shows nearly no benefit over the baseline\.

It is worth noting that the FPR trends in Tables[1](https://arxiv.org/html/2606.18430#S6.T1)–[2](https://arxiv.org/html/2606.18430#S6.T2)differ systematically with corpus entropy across watermark families\. Specifically,Kgwexhibits lower false positives on the low\-entropy than high\-entropy corpora, whileUnigramshows the reverse pattern\. A plausible explanation is that, inKgw, the green/red partition varies across positions, so recurring short templates in low\-entropy code can be filtered more consistently\. Bagging in small groups on high\-entropy text is more prone to fitting idiosyncratic red clusters, and thus tends to increase false alarms\.SweetresemblesKgwbut ignores low\-entropy tokens in the z\-test\. This attenuates the entropy effect and helps keepSweet’s false positives low on both corpora\. By contrast,Unigramties token color to token type across documents\. This coupling is stronger in low\-entropy code, where the same token types recur across code snippets heavily, and it is weaker in high\-entropy natural language texts with greater lexical diversity\. ForExp, the false positives remain essentially near zero across both corpora, which is consistent with Theorem[5](https://arxiv.org/html/2606.18430#Thmtheorem5)under the score secrecy assumption\.

These results provide practical guidance to tune the parameters\(B,G\)\(B,G\)along the TPR–FPR frontier\. Generally, reducingGG\(or increasingBB\) raises both TPR and FPR by producing more idiosyncratic signatures whose ensemble maximum tends to exceed the threshold\. In contrast, increasingGG\(or reducingBB\) accelerates the decline of both TPR and FPR, as a less representative signature generalizes more weakly\. WhenBBis too small relative toGG, signatures fail to capture meaningful corpus\-level patterns, and filtering degrades toward the baseline behavior\. The effects of batch and group size follow from standard underfitting vs\. overfitting considerations and the multiple\-testing nature of ensemble learningPolikar \([2012](https://arxiv.org/html/2606.18430#bib.bib19)\)\.

## 7Discussion and implications

### 7\.1Theoretical implications for LLM watermarking

Our analysis shows that filtering at detection time can be added on top of existing watermark tests\. It does not require statistical assumptions that are stronger than those already used by the baseline detector\. Under the standardKgwcoloring model, deleting a fixed subset of tokens from an unwatermarked text does not change the null distribution of the z\-statistic\. It mainly reduces the effective sample size, which slightly widens the confidence intervals\. This independence model is idealized, but it is the same assumption made by the original watermark schemes\. When the deletion rule becomes correlated with hidden colors, the guarantee may weaken, which is precisely the motivation for the threat analysis in Sec\.[5](https://arxiv.org/html/2606.18430#S5)\. In our experiments on repeated, correlated, and edited texts, signature filtering remains effective even when independence holds only approximately\.

The false\-positive bounds in Sec\.[5](https://arxiv.org/html/2606.18430#S5)provide a practical rule of thumb for operating signature filters\. In the color\-blind setting, one can safely delete a number of tokens that grows linearly with the text length\. With this choice, the conditional false positive rateℙerror=ℙ\(Z′≥z0∣Z<z0,ℋ0\)\\mathbb\{P\}\_\{\\mathrm\{error\}\}=\\mathbb\{P\}\(Z^\{\\prime\}\\geq z\_\{0\}\\mid Z<z\_\{0\},\\mathcal\{H\}\_\{0\}\)can be kept below any chosen tolerance level\. The situation changes when an attacker can fully control token colors\. In that case, any watermark test that relies only on color statistics is inherently robust only up ton\\sqrt\{n\}\-scale deletions\. Below this scale, worst\-case false positives remain bounded\. Beyond it, even an optimally designed hypothesis test can be forced to flip some correct decisions\. Thisn\\sqrt\{n\}threshold reflects a fundamental limit of color\-based watermarking, not a specific weakness of signature filtering\.

We also observe consistent locality patterns in Sec\.[6\.1](https://arxiv.org/html/2606.18430#S6.SS1)\. In particular, 2–3\-gram signatures work best forKgw\-style schemes, while 3–4\-grams work best forExp\. These results suggest that most usable watermark evidence comes from short\-range token dependencies\. In this sense, signature filtering serves as a lightweight pre\-processing layer that concentrates this evidence, along with an explicit and tunable deletion budget that practitioners can manage\.

### 7\.2Practical implications for information processing and management

Drop\-in enhancement and design guidelines\.Signature filtering operates entirely at detection time\. It only requires access to historical watermarked and natural texts to learn signatures via MILP\. This makes it a lightweight plug\-in for information retrieval, indexing, and content management pipelines that already deploy watermarks but must operate under strict false\-positive budgets\. In large or streaming corpora, we consider a bagging deployment mode, which learns signature batches on rolling text groups and takes the maximum post\-filter z\-score across these signatures\. Practitioners can select batch sizes, group sizes, and decision thresholds according to their risk tolerance and computational budget, much as they currently tune watermark strength or operating points of existing detectors\.

How signature filtering differs from other techniques\.Relative to other detection\-time enhancement methods likeEwdandWinMax, our work is more friendly to governance\. Techniques that amplify watermark signals by changing the test statistic introduce new scores that must be calibrated and explained alongside watermark tests\. By contrast, signature filtering keeps the underlying detection unchanged and instead learns a reusable filter that modifies which tokens enter the test\. This yields \(i\) explicit control of the additional Type\-I error throughℙerror\\mathbb\{P\}\_\{\\mathrm\{error\}\}, \(ii\) interpretability in terms of which contexts are removed, and \(iii\) ease of integration into policy\-driven pipelines where each component must expose its contribution to overall risk\. These features make filtering particularly attractive for management settings in which detection outputs support triage and provenance attribution\.

Cross\-lingual and multimodal extensions\.Conceptually, signature filtering can be extended to any watermark test that aggregates per\-unit evidence and remains calibrated after deleting units from observable content\. For multilingual watermarked documents\(Heet al\.,[2024](https://arxiv.org/html/2606.18430#bib.bib34)\), our two\-stage detector may be applied unchanged by modifying the representation used for signature learning\. When multilingual LLMs share the same tokenizer, signatures can be learned either separately per language or jointly with language tags\. When translation is a routine step, one can instead translate both the training corpus and candidate texts into a pivot language, after which the same signature learning and detecting pipeline can be applied\. Tokens or short phrases can also be mapped into cross\-lingual semantic clusters, and the same optimization can be carried out over these high\-level units\. Signature filtering thus aims to remove ambiguous clusters that dilute evidenceLiuet al\.\([2024a](https://arxiv.org/html/2606.18430#bib.bib16)\)\.

For images and other modalities, one can discretize the signal into a finite token stream \(e\.g\., pixels, patches, or quantized latents\) and apply pseudorandom coloring or scoring to these units, such that signatures suppress regions that consistently provide little evidence or exhibit high variance\(Fernandezet al\.,[2023b](https://arxiv.org/html/2606.18430#bib.bib17)\)\. Because the deletion rule still depends only on observable features, the null\-calibration argument in Sec\.[3](https://arxiv.org/html/2606.18430#S3)remains valid in these scenarios\. Nevertheless, to keep optimization feasible at scale, practical solutions will hinge on precise encoding of sufficient conditions, efficient pruning of candidate patterns, and scalable implementation of operation modes\.

Robustness to dynamic content distributions\.In production, a deployed signature may become stale when the deployment context distribution has drifted enough that the post\-filter detector no longer satisfies its target TPR/FPR operating point\. This is a common issue for machine\-learning systems deployed under concept drift or dataset shift\(Gamaet al\.,[2014](https://arxiv.org/html/2606.18430#bib.bib7); Luet al\.,[2019](https://arxiv.org/html/2606.18430#bib.bib8)\)\. Gradual covariate drift is expected to reduce recall first, because learnednn\-gram contexts will match less often or remove less red evidence\. This behavior is consistent with the smooth TPR decay observed in the Bag\(B,G\)\(B,G\)experiments of Sec\.[6\.3](https://arxiv.org/html/2606.18430#S6.SS3)\. The FPR remains governed by null calibration, but drift toward highly repetitive prose may push signatures forKgw\-style watermarks toward the distributionally correlated regime characterized in Theorem[3](https://arxiv.org/html/2606.18430#Thmtheorem3)\.

Operationally, data drift can be monitored using standard methods such as two\-sample tests or domain\-discriminator tests\(Grettonet al\.,[2012](https://arxiv.org/html/2606.18430#bib.bib2); Rabanseret al\.,[2019](https://arxiv.org/html/2606.18430#bib.bib11)\)\. If data drift is found to be fast, the bagging strategy in Sec\.[6\.3](https://arxiv.org/html/2606.18430#S6.SS3)can be extended with an adaptive moving\-window mechanism: signatures are learned from recent batches, stale signatures outside the window are discarded or downweighted, and newly optimized signatures are added as the stream evolves\. This mirrors existing adaptive and streaming machine\-learning techniques for concept drift\(Bifet and Gavaldà,[2007](https://arxiv.org/html/2606.18430#bib.bib9)\)\. We note that, while standard monitoring and rolling calibration can enhance a filter’s resilience to gradual dynamic content changes, signatures still need to be re\-optimized after significant concept shifts, tokenizer or model changes, and watermark key rotation\.

### 7\.3Limitations and future directions

Several limitations qualify our contributions and motivate future work\. First, our theoretical guarantees assume that the watermark’s statistical model remains informative after filtering\. This assumption can break if an attacker can manipulate or infer token colors\. For example, the attacker might partially recover the green/red partition or obtain model internals\. In that case, any color\-based detector \(including signature filtering\) becomes vulnerable, and the linear\-safe regime may no longer apply\.

A second limitation arises from distributional correlation\. When signatures are trained and deployed on highly repetitive corpora, the learned filter can become correlated with benign text\. This correlation can mimic adversarial deletions and push the system toward then\\sqrt\{n\}\-scale fragile regime characterized in Theorem[3](https://arxiv.org/html/2606.18430#Thmtheorem3)\. In practice, such risk can be mitigated by combining filtering with entropy\-aware or semantics\-aware mechanisms that down\-weight highly predictable tokens\. Our experiments already show benefits from such mechanisms \(for example,Sweet\)\. An important next step is to fully characterize and evaluate these hybrid systems, determining how to allocate deletion budgets and weights across the different signals\.

Another challenge is learning effective signatures in applications with scarce data, such as highly specialized domains where it is difficult to assemble representative watermarked and natural documents for training\. Table[2](https://arxiv.org/html/2606.18430#S6.T2)quantifies this sensitivity, showing that reducing the per\-group training sizeBBlowers both TPR and FPR across all watermark families\. The gains over the baseline persist in most settings but can become modest\. This observation suggests several mitigation strategies, like pooling adjacent batches or reducing the group sizeGGsuch that each signature is estimated from more representative data, updating signatures incrementally as new texts arrive, and prioritizing conservative signature orders in scarce\-data domains to avoid brittle patterns\. A systematic investigation of these strategies is our subsequent goal\.

A practical deployment limitation is key dependence\. The signatures computed by our MILP are based on key\-conditioned evidence, so rotating the watermark key changes the optimization objective and weakens the learned signatures\. Although the offline recomputation cost is modest forKgw\-style watermarks, it is noticeably higher forExp\(see Tables[1](https://arxiv.org/html/2606.18430#S6.T1)–[2](https://arxiv.org/html/2606.18430#S6.T2)\)\. Accordingly, signature filtering is most attractive when keys are stable over a deployment interval or when re\-optimization can run asynchronously in the background\.

Finally, while our results suggest that signature filtering can serve as a useful component in provenance pipelines, it does not replace human judgment or eliminate the need for complementary signals\. In high\-stakes settings, watermark\-based decisions should be interpreted as one input among many, alongside human review, retrieval\-based corroboration, and content\-authenticity metadata\. Designing such socio\-technical systems and empirically studying how managers and end users understand, trust, and act on watermark evidence remains a critical area for future research\.

## Appendix AMILP Formulation forExpSignatures

In the following, letXn∼Γ​\(n,1\)X\_\{n\}\\sim\\Gamma\(n,1\)withn≥1n\\geq 1and letγ​\(x,n\)≔ℙ​\(Xn≥x\)\\gamma\(x,n\)\\coloneqq\\mathbb\{P\}\(X\_\{n\}\\geq x\)denote its survival function\. We first present a sufficient condition that makesExpwatermarks compatible with our signature constraints\.

###### Proposition 1\.

Fix a significance levelα∈\(0,1\)\\alpha\\in\(0,1\)and definec​\(α\)\>1c\(\\alpha\)\>1as the unique root ofc​e−\(c−1\)=αc\\,e^\{\-\(c\-1\)\}=\\alphaon\(1,∞\)\(1,\\infty\)\. Thenx≥c​\(α\)​nx\\geq c\(\\alpha\)\\,nis a sufficient condition forγ​\(x,n\)<α\\gamma\(x,n\)<\\alphaandn\>1n\>1\.

###### Proof\.

Writex=s​nx=snwith a stretch factors\>1s\>1\. SinceΓ​\(n,1\)\\Gamma\(n,1\)can be expressed as a sum ofnnindependentExp​\(1\)\\mathrm\{Exp\}\(1\)variables, we haveXn=∑i=1nYiX\_\{n\}=\\sum\_\{i=1\}^\{n\}Y\_\{i\}with eachYi∼Exp​\(1\)Y\_\{i\}\\sim\\mathrm\{Exp\}\(1\)\. For anyt∈\(0,1\)t\\in\(0,1\), Markov’s inequality givesℙ​\(Xn≥x\)=ℙ​\(et​Xn≥et​x\)≤e−t​x​𝔼​\[et​Xn\]=e−t​x​\(𝔼​\[et​Y1\]\)n=e−t​x​\(1−t\)−n,\\mathbb\{P\}\(X\_\{n\}\\geq x\)=\\mathbb\{P\}\\bigl\(e^\{tX\_\{n\}\}\\geq e^\{tx\}\\bigr\)\\leq e^\{\-tx\}\\,\\mathbb\{E\}\[e^\{tX\_\{n\}\}\]=e^\{\-tx\}\\,\\bigl\(\\mathbb\{E\}\[e^\{tY\_\{1\}\}\]\\bigr\)^\{n\}=e^\{\-tx\}\\,\(1\-t\)^\{\-n\},since the m\.g\.f\. ofExp​\(1\)\\mathrm\{Exp\}\(1\)is𝔼​\[et​Y1\]=\(1−t\)−1\\mathbb\{E\}\[e^\{tY\_\{1\}\}\]=\(1\-t\)^\{\-1\}fort<1t<1\. Choosing the optimalt⋆=1−s−1∈\(0,1\)t^\{\\star\}=1\-s^\{\-1\}\\in\(0,1\)then yields the explicit upper tail boundℙ​\(Xn≥s​n\)≤\(s​e−\(s−1\)\)n\.\\mathbb\{P\}\(X\_\{n\}\\geq s\\,n\)\\leq\\bigl\(s\\,e^\{\-\(s\-1\)\}\\bigr\)^\{n\}\.

Note that the functionf​\(s\)=s​e−\(s−1\)f\(s\)=s\\,e^\{\-\(s\-1\)\}satisfiesf′​\(s\)=e−\(s−1\)​\(1−s\)<0f^\{\\prime\}\(s\)=e^\{\-\(s\-1\)\}\(1\-s\)<0for alls\>1s\>1, soffis strictly decreasing on\(1,∞\)\(1,\\infty\), withf​\(1\)=1f\(1\)=1andlims→∞f​\(s\)=0\\lim\_\{s\\to\\infty\}f\(s\)=0\. Therefore, for eachα∈\(0,1\)\\alpha\\in\(0,1\)there is a unique solutionc​\(α\)\>1c\(\\alpha\)\>1tof​\(s\)=αf\(s\)=\\alpha\. Lets=c​\(α\)s=c\(\\alpha\)be this unique solution; plugging it into the upper tail bound yieldsℙ​\(Xn≥c​\(α\)​n\)≤αn<α\\mathbb\{P\}\(X\_\{n\}\\geq c\(\\alpha\)n\)\\leq\\alpha^\{n\}<\\alphafor alln\>1n\>1\. Hence,γ​\(x,n\)=ℙ​\(Xn≥x\)<α\\gamma\(x,n\)=\\mathbb\{P\}\(X\_\{n\}\\geq x\)<\\alphawheneverx≥c​\(α\)​nx\\geq c\(\\alpha\)\\,n\. ∎

Our experiments fixα=10−4\\alpha=10^\{\-4\}following the default setting of MarkLLMPanet al\.\([2024a](https://arxiv.org/html/2606.18430#bib.bib30)\)\. Since\|T′\|∈\[30,200\]\|T^\{\\prime\}\|\\in\[30,200\], we can*numerically*compute the best linear sufficient condition for detectingExpwatermarks\.

###### Proposition 2\.

Fixα=10−4\\alpha=10^\{\-4\}and suppose thatn∈\[30,200\]n\\in\[30,200\]\. Thenx≥1\.826​nx\\geq 1\.826\\,nimplies thatγ​\(x,n\)<α\\gamma\(x,n\)<\\alpha\.

###### Proof\.

Givennnandα\\alpha, letx⋆=x⋆​\(n,α\)x^\{\\star\}=x^\{\\star\}\(n,\\alpha\)be the unique solution forγ​\(x⋆,n\)=α\\gamma\(x^\{\\star\}\\\!,n\)=\\alpha\. \(Such a unique solution exists sinceγ​\(0,n\)=1\\gamma\(0,n\)=1andγ​\(x,n\)→0\\gamma\(x,n\)\\to 0asx→∞x\\to\\infty\.\) Definern≔x⋆/nr\_\{n\}\\coloneqq x^\{\\star\}/n\. For every integern∈\[30,200\]n\\in\[30,200\], we can computernr\_\{n\}numerically\. The maximal ratio occurs atr30=max30≤n≤200⁡rn≈1\.82505r\_\{30\}=\\max\_\{30\\leq n\\leq 200\}r\_\{n\}\\approx 1\.82505\. For any constantc\>r30c\>r\_\{30\},n∈\[30,200\]n\\in\[30,200\], andx≥c​nx\\geq c\\,n, it holds thatx≥c​n\>r30​n≥rn​n=x⋆\.x\\geq c\\,n\>r\_\{30\}\\,n\\geq r\_\{n\}\\,n=x^\{\\star\}\.Sinceγ​\(x,n\)\\gamma\(x,n\)is strictly decreasing inxx, we haveγ​\(x,n\)<γ​\(x⋆,n\)=α\.\\gamma\(x,n\)<\\gamma\(x^\{\\star\}\\\!,n\)=\\alpha\.Consequently,x≥1\.826​nx\\geq 1\.826\\,nensures thatγ​\(x,n\)<α\\gamma\(x,n\)<\\alpha\. ∎

## Appendix BBerry–Esseen Remainders

This section establishes the Berry–Esseen remainders we will use throughout the remaining appendices\. LetX1,…,XnX\_\{1\},\\dots,X\_\{n\}be independent random vectors inℝd\\mathbb\{R\}^\{d\}with𝔼​\[Xi\]=0\\mathbb\{E\}\[X\_\{i\}\]=0\. DefineSn≔∑i=1nXiS\_\{n\}\\coloneqq\\sum\_\{i=1\}^\{n\}X\_\{i\}withΣn≔Cov⁡\(Sn\)\\Sigma\_\{n\}\\coloneqq\\operatorname\{Cov\}\(S\_\{n\}\)\. WriteZd∼𝒩​\(0,Id\)Z\_\{d\}\\sim\\mathcal\{N\}\(0,I\_\{d\}\)andΦd​\(A\)≔ℙ​\(Zd∈A\)\\Phi\_\{d\}\(A\)\\coloneqq\\mathbb\{P\}\(Z\_\{d\}\\in A\)for any Borel setA⊆ℝdA\\subseteq\\mathbb\{R\}^\{d\}\. Define the*standardized third moment*μn≔∑i=1n𝔼​‖Σn−1/2​Xi‖23\.\\mu\_\{n\}\\coloneqq\\sum\_\{i=1\}^\{n\}\\mathbb\{E\}\\bigl\\lVert\\Sigma\_\{n\}^\{\-1/2\}X\_\{i\}\\bigr\\rVert\_\{2\}^\{3\}\.We useΦ​\(x\)\\Phi\(x\)to denote the standard normal cumulative distribution function, and useΦd​\(x1,…,xd\)\\Phi\_\{d\}\(x\_\{1\},\\dots,x\_\{d\}\)to denote its standarddd\-variate version\.

###### Proposition 3\(Bentkus[2005](https://arxiv.org/html/2606.18430#bib.bib60)\)\.

There is a constantcBEc\_\{\\mathrm\{BE\}\}such that for every convex Borel setA⊆ℝdA\\subseteq\\mathbb\{R\}^\{d\}, it holds that\|ℙ​\(Σn−1/2​Sn∈A\)−Φd​\(A\)\|≤cBE⋅d1/4⋅μn\.\\bigl\|\\mathbb\{P\}\\bigl\(\\Sigma\_\{n\}^\{\-1/2\}S\_\{n\}\\in A\\bigr\)\-\\Phi\_\{d\}\(A\)\\bigr\|\\;\\leq\\;c\_\{\\mathrm\{BE\}\}\\cdot d^\{1/4\}\\cdot\\mu\_\{n\}\.

Recall thatσn≔γ​\(1−γ\)​n\\sigma\_\{n\}\\coloneqq\\sqrt\{\\gamma\(1\-\\gamma\)n\}is the standard deviation of the centered Bernoulli sumNg−γ​n=∑i=1n\(Gi−γ\)N\_\{g\}\-\\gamma n=\\sum\_\{i=1\}^\{n\}\(G\_\{i\}\-\\gamma\), where eachGi∼Ber⁡\(γ\)G\_\{i\}\\sim\\operatorname\{Ber\}\(\\gamma\)indicates whether tokeniiis green under the green ratioγ\\gamma\. Proposition[3](https://arxiv.org/html/2606.18430#Thmproposition3)instantiated into the following bounds ford=1d=1\(univariate\) andd=2d=2\(bivariate\):

Univariate remainderδn\\delta\_\{n\}\.Consider the scalar statisticZ=\(Ng−γ​n\)/σnZ=\(N\_\{g\}\-\\gamma n\)/\\sigma\_\{n\}\. For anyz∈ℝz\\in\\mathbb\{R\}, it holds that

\|ℙ​\(Z≤z\)−Φ​\(z\)\|≤cBE​μn=cBE​∑i=1n𝔼​\|Gi−γ\|3σn3=cBE​n​γ​\(1−γ\)​\[\(1−γ\)2\+γ2\]σn3≤cBEσn≕δn\.\\displaystyle\\Bigl\|\\mathbb\{P\}\\bigl\(Z\\leq z\\bigr\)\-\\Phi\(z\)\\Bigr\|\\;\\leq\\;c\_\{\\mathrm\{BE\}\}\\,\\mu\_\{n\}\\;=\\;c\_\{\\mathrm\{BE\}\}\\,\\frac\{\\sum\_\{i=1\}^\{n\}\\mathbb\{E\}\\lvert G\_\{i\}\-\\gamma\\rvert^\{3\}\}\{\\sigma\_\{n\}^\{3\}\}\\;=\\;c\_\{\\mathrm\{BE\}\}\\,\\frac\{n\\gamma\(1\-\\gamma\)\\bigl\[\(1\-\\gamma\)^\{2\}\+\\gamma^\{2\}\\bigr\]\}\{\\sigma\_\{n\}^\{3\}\}\\;\\leq\\;\\frac\{c\_\{\\mathrm\{BE\}\}\}\{\\sigma\_\{n\}\}\\;\\eqqcolon\\;\\delta\_\{n\}\.
Bivariate remainderrn,n′r\_\{n,n^\{\\prime\}\}\.Consider the z\-scores\(Z′,Z\)=\(\(Ng′−γ​n′\)/σn′,\(Ng−γ​n\)/σn\)\(Z^\{\\prime\}\\\!,\\,Z\)=\\bigl\(\(N\_\{g\}^\{\\prime\}\-\\gamma n^\{\\prime\}\)/\\sigma\_\{n^\{\\prime\}\},\\,\(N\_\{g\}\-\\gamma n\)/\\sigma\_\{n\}\\bigr\)after and before signature filtering\. The bivariate Berry–Esseen gives

\|ℙ​\(Z′<z,Z<z\)−Φ2​\(A\)\|≤supA​convex\|ℙ​\[\(Z′,Z\)∈A\]−Φ2​\(A\)\|≤cBE⋅21/4⋅2​2γ​\(1−γ\)​ρ3​σn≕rn,n′\.\\displaystyle\\Bigl\|\\mathbb\{P\}\(Z^\{\\prime\}<z,\\,Z<z\)\-\\Phi\_\{2\}\(A\)\\Bigr\|\\;\\leq\\sup\_\{A\\text\{ convex\}\}\\Bigl\|\\mathbb\{P\}\\bigl\[\(Z^\{\\prime\}\\\!,\\,Z\)\\in A\\bigr\]\-\\Phi\_\{2\}\(A\)\\Bigr\|\\;\\leq\\;\\frac\{c\_\{\\mathrm\{BE\}\}\\cdot 2^\{1/4\}\\cdot 2\\sqrt\{2\}\}\{\\gamma\(1\-\\gamma\)\\,\\rho^\{3\}\\,\\sigma\_\{n\}\}\\;\\eqqcolon\\;r\_\{n,n^\{\\prime\}\}\.

## Appendix CFalse Positive Analysis for Signature Filtering

This section provides the details for Sec\.[5\.1](https://arxiv.org/html/2606.18430#S5.SS1)\. We first derive the exact FPR of filtering via binomial\-hypergeometric tails\. We then offer a Gaussian approximation \(Proposition[4](https://arxiv.org/html/2606.18430#Thmproposition4)\) of the tail probability under a simple variance condition\. Finally, we show that the FPR remains below any prescribed tolerance level by limiting the deletion to a linear fraction of the token count and prove Theorem[1](https://arxiv.org/html/2606.18430#Thmtheorem1)in Sec\.[5\.1](https://arxiv.org/html/2606.18430#S5.SS1)\.

### C\.1Exact false\-positive probability

Fix a signatureSSand a candidate textTTof lengthnn\. Letn′n^\{\\prime\}denote the number of tokens that survive filtering\. Underℋ0\\mathcal\{H\}\_\{0\}, we can defineNg≔∑i=1nGiN\_\{g\}\\coloneqq\\sum\_\{i=1\}^\{n\}G\_\{i\}as the number of green tokens inTTunder theKgwcoloring assumption, where eachGi∼Ber​\(γ\)G\_\{i\}\\sim\\mathrm\{Ber\}\(\\gamma\)\. For a color\-blind attacker, we can defineNg′≔∑i=1nYi​GiN\_\{g\}^\{\\prime\}\\coloneqq\\sum\_\{i=1\}^\{n\}Y\_\{i\}\\,G\_\{i\}as the number of retained green tokens, whereYiY\_\{i\}is an indicator that tokentit\_\{i\}survives\. Thus, conditioned onNg=xN\_\{g\}=x, it holds thatNg′∣\(Ng=x\)∼HyperGeo⁡\(x,n′,n\)\.N\_\{g\}^\{\\prime\}\\mid\(N\_\{g\}=x\)\\sim\\operatorname\{HyperGeo\}\(x,\\,n^\{\\prime\},\\,n\)\.Definekz≔γ​n\+z​σnk\_\{z\}\\coloneqq\\gamma n\+z\\sigma\_\{n\}andkz′≔γ​n′\+z​σn′k^\{\\prime\}\_\{z\}\\coloneqq\\gamma n^\{\\prime\}\+z\\sigma\_\{n^\{\\prime\}\}, the empirical green fraction thresholds before and after filtering\. The exact probability that a text fails the watermark test before filtering \(i\.e\.,Ng<kzN\_\{g\}<k\_\{z\}\) but passes the test after filtering \(i\.e\.,Ng′≥kz′N\_\{g\}^\{\\prime\}\\geq k^\{\\prime\}\_\{z\}\) is

ℙflip​\(n,n′,z\)≔∑x=0⌊kz−1⌋\(nx\)​γx​\(1−γ\)n−x​p​\(x\),\\displaystyle\\mathbb\{P\}\_\{\\mathrm\{flip\}\}\(n,n^\{\\prime\},z\)\\;\\coloneqq\\;\\sum\_\{x=0\}^\{\\lfloor k\_\{z\}\-1\\rfloor\}\\binom\{n\}\{x\}\\,\\gamma^\{x\}\(1\-\\gamma\)^\{n\-x\}\\,p\(x\),\(5\)wherep​\(x\)≔ℙ​\(Ng′≥kz′∣Ng=x\)p\(x\)\\coloneqq\\mathbb\{P\}\(N\_\{g\}^\{\\prime\}\\geq k^\{\\prime\}\_\{z\}\\mid N\_\{g\}=x\)\.

### C\.2Large\-sample normal approximation

We may use the central limit theorem to obtain a simple approximation ofℙflip​\(n,n′,z\)\\mathbb\{P\}\_\{\\mathrm\{flip\}\}\(n,n^\{\\prime\},z\)\. More precisely, defineZ≔\(Ng−γ​n\)/γ​\(1−γ\)​nZ\\coloneqq\(N\_\{g\}\-\\gamma n\)/\\sqrt\{\\gamma\(1\-\\gamma\)n\}andZ′≔\(Ng′−γ​n′\)/γ​\(1−γ\)​n′Z^\{\\prime\}\\coloneqq\(N\_\{g\}^\{\\prime\}\-\\gamma n^\{\\prime\}\)/\\sqrt\{\\gamma\(1\-\\gamma\)n^\{\\prime\}\}\. Recall thatNg=∑i=1nGiN\_\{g\}=\\sum\_\{i=1\}^\{n\}G\_\{i\}andNg′=∑i=1nYi​GiN\_\{g\}^\{\\prime\}=\\sum\_\{i=1\}^\{n\}Y\_\{i\}G\_\{i\}\. The correlation coefficient of\(Ng,Ng′\)\(N\_\{g\},N\_\{g\}^\{\\prime\}\)isρ=γ​\(1−γ\)​n′/\(γ​\(1−γ\)​n​γ​\(1−γ\)​n′\)=n′/n\\rho=\\gamma\(1\-\\gamma\)n^\{\\prime\}/\(\\sqrt\{\\gamma\(1\-\\gamma\)n\}\\sqrt\{\\gamma\(1\-\\gamma\)n^\{\\prime\}\}\)=\\sqrt\{n^\{\\prime\}/n\}\.

The pair\(Ng,Ng′\)\(N\_\{g\},N\_\{g\}^\{\\prime\}\)satisfies the joint central limit theorem whennnandn′n^\{\\prime\}are large, in the sense that the joint distribution of\(Z,Z′\)\(Z,Z^\{\\prime\}\)converges in distribution to a bivariate normal vector with correlation coefficientρ=n′/n\\rho=\\sqrt\{n^\{\\prime\}/n\}\. We useΦ2​\(⋅,⋅;ρ\)\\Phi\_\{2\}\(\\cdot,\\cdot\\,;\\rho\)to denote the bivariate normal cumulative distribution with correlationρ\\rho\.

In the rest of this section, we fix an unwatermarked textTTunder theKgwcoloring assumption, and use the conditional probabilityℙ​\(Z′≥z∣Z<z\)\\mathbb\{P\}\(Z^\{\\prime\}\\geq z\\mid Z<z\)to quantify the risk thatTTis flagged as watermarked by a filter\. We will refer to this risk as the*\(conditional\) flip probability*in the sequel\.

###### Proposition 4\(Large\-sample flip probability\)\.

Recall the univariate reminderδn\\delta\_\{n\}and the bivariate reminderrn,n′r\_\{n,n^\{\\prime\}\}defined in[B](https://arxiv.org/html/2606.18430#A2)\. WhenΦ​\(z\)\>δn\\Phi\(z\)\>\\delta\_\{n\}, it holds that

\|ℙ\(Z′≥z∣Z<z\)−Φ​\(z\)−Φ2​\(z,z;ρ\)Φ​\(z\)\|≤rn,n′\+δnΦ​\(z\)−δn\.\\displaystyle\\left\|\\mathbb\{P\}\(Z^\{\\prime\}\\geq z\\mid Z<z\)\-\\frac\{\\Phi\(z\)\-\\Phi\_\{2\}\(z,z;\\rho\)\}\{\\Phi\(z\)\}\\right\|\\;\\;\\leq\\;\\;\\frac\{r\_\{n,n^\{\\prime\}\}\+\\delta\_\{n\}\}\{\\Phi\(z\)\-\\delta\_\{n\}\}\.\(6\)

###### Proof\.

SinceNg=∑i=1nGiN\_\{g\}=\\sum\_\{i=1\}^\{n\}\\\!G\_\{i\}andNg′=∑i=1nYi​GiN^\{\\prime\}\_\{g\}=\\sum\_\{i=1\}^\{n\}\\\!Y\_\{i\}\\,G\_\{i\}, the pair\(Ng,Ng′\)\(N\_\{g\},N^\{\\prime\}\_\{g\}\)is a sum of\{0,1\}2\\\{0,1\\\}^\{2\}\-valued vectors whose third absolute centered moments are bounded by 1\. Hence, the Berry–Esseen bounds in Proposition[3](https://arxiv.org/html/2606.18430#Thmproposition3)yield\|ℙ​\(Z′<z,Z<z\)−Φ2​\(z,z;ρ\)\|≤rn,n′\\bigl\|\\mathbb\{P\}\(Z^\{\\prime\}<z,\\,Z<z\)\-\\Phi\_\{2\}\(z,z;\\rho\)\\bigr\|\\leq r\_\{n,n^\{\\prime\}\}and\|ℙ​\(Z<z\)−Φ​\(x\)\|≤δn\.\\bigl\|\\mathbb\{P\}\(Z<z\)\-\\Phi\(x\)\\bigr\|\\leq\\delta\_\{n\}\.Taking the difference between these two bounds leads toℙ​\(Z′≥z,Z<z\)=Φ​\(z\)−Φ2​\(z,z;ρ\)\+ξn,n′\\mathbb\{P\}\(Z^\{\\prime\}\\geq z,\\,Z<z\)=\\Phi\(z\)\-\\Phi\_\{2\}\(z,z;\\rho\)\+\\xi\_\{n,n^\{\\prime\}\}with\|ξn,n′\|≤rn,n′\+δn\|\\xi\_\{n,n^\{\\prime\}\}\|\\leq r\_\{n,n^\{\\prime\}\}\+\\delta\_\{n\}\.

Definec≔Φ​\(z\)−Φ2​\(z,z;ρ\)c\\coloneqq\\Phi\(z\)\-\\Phi\_\{2\}\(z,z;\\rho\)andηn≔ℙ​\(Z<z\)−Φ​\(x\)\\eta\_\{n\}\\coloneqq\\mathbb\{P\}\(Z<z\)\-\\Phi\(x\)\. Thenℙ​\(Z′≥z∣Z<z\)=ℙ​\(Z′≥z,Z<z\)ℙ​\(Z<z\)=c\+ξn,n′Φ​\(z\)\+ηn\.\\mathbb\{P\}\(Z^\{\\prime\}\\geq z\\mid Z<z\)=\\frac\{\\mathbb\{P\}\(Z^\{\\prime\}\\geq z,\\,Z<z\)\}\{\\mathbb\{P\}\(Z<z\)\}=\\frac\{c\\,\+\\,\\xi\_\{n,n^\{\\prime\}\}\}\{\\Phi\(z\)\\,\+\\,\\eta\_\{n\}\}\.Since\|ηn\|≤δn<Φ​\(z\)\|\\eta\_\{n\}\|\\leq\\delta\_\{n\}<\\Phi\(z\)by assumption, we haveΦ​\(z\)\+ηn≥Φ​\(z\)−δn\>0\\Phi\(z\)\+\\eta\_\{n\}\\geq\\Phi\(z\)\-\\delta\_\{n\}\>0\. It follows that

c\+ξn,n′Φ​\(z\)\+ηn−cΦ​\(z\)=ξn,n′​Φ​\(z\)−c​ηnΦ​\(z\)​\[Φ​\(z\)\+ηn\]≤\|ξn,n′\|​Φ​\(z\)\+c​\|ηn\|Φ​\(z\)​\[Φ​\(z\)−δn\]≤rn,n′\+δnΦ​\(z\)−δn,\\displaystyle\\frac\{c\+\\xi\_\{n,n^\{\\prime\}\}\}\{\\Phi\(z\)\+\\eta\_\{n\}\}\-\\frac\{c\}\{\\Phi\(z\)\}\\;=\\;\\frac\{\\xi\_\{n,n^\{\\prime\}\}\\Phi\(z\)\\;\-\\;c\\,\\eta\_\{n\}\}\{\\Phi\(z\)\\bigl\[\\Phi\(z\)\+\\eta\_\{n\}\\bigr\]\}\\;\\leq\\;\\frac\{\|\\xi\_\{n,n^\{\\prime\}\}\|\\,\\Phi\(z\)\+c\\,\|\\eta\_\{n\}\|\}\{\\Phi\(z\)\\bigl\[\\Phi\(z\)\-\\delta\_\{n\}\\bigr\]\}\\;\\leq\\;\\frac\{r\_\{n,n^\{\\prime\}\}\+\\delta\_\{n\}\}\{\\Phi\(z\)\-\\delta\_\{n\}\},\(7\)where the last inequality follows from\|c\|≤Φ​\(z\)\|c\|\\leq\\Phi\(z\)and the Berry–Esseen bounds\|ξn,n′\|≤rn,n′\|\\xi\_\{n,n^\{\\prime\}\}\|\\leq r\_\{n,n^\{\\prime\}\}and\|ηn\|≤δn\|\\eta\_\{n\}\|\\leq\\delta\_\{n\}\. Pluggingℙ​\(Z′≥z∣Z<z\)=c\+ξn,n′Φ​\(z\)\+ηn\\mathbb\{P\}\(Z^\{\\prime\}\\geq z\\mid Z<z\)=\\frac\{c\\,\+\\,\\xi\_\{n,n^\{\\prime\}\}\}\{\\Phi\(z\)\\,\+\\,\\eta\_\{n\}\}andc=Φ​\(z\)−Φ2​\(z,z;ρ\)c=\\Phi\(z\)\-\\Phi\_\{2\}\(z,z;\\rho\)into \([7](https://arxiv.org/html/2606.18430#A3.E7)\) yields the desired bound\. ∎

### C\.3Proof of Theorem[1](https://arxiv.org/html/2606.18430#Thmtheorem1)

For fixedγ∈\(0,1\)\\gamma\\in\(0,1\),z\>0z\>0,ε∈\(0,1\)\\varepsilon\\in\(0,1\), and every finitennsuch thatΦ​\(z\)\>δn\\Phi\(z\)\>\\delta\_\{n\}, Proposition[4](https://arxiv.org/html/2606.18430#Thmproposition4)asserts that

ℙ​\(Z′≥z∣Z<z\)≤f​\(ρ\)\+εBE​\(n,ρ\)\.\\displaystyle\\mathbb\{P\}\\bigl\(Z^\{\\prime\}\\\!\\geq z\\mid Z<z\\bigr\)\\;\\leq\\;f\(\\rho\)\+\\varepsilon\_\{\\text\{BE\}\}\(n,\\rho\)\.\(8\)HereεBE​\(n,ρ\)≔\(rn,n′\+δn\)/\(Φ​\(z\)−δn\)\\varepsilon\_\{\\mathrm\{BE\}\}\(n,\\rho\)\\coloneqq\(r\_\{n,n^\{\\prime\}\}\+\\delta\_\{n\}\)\\,/\\,\(\\Phi\(z\)\-\\delta\_\{n\}\)is the Berry–Esseen remainder, andf​\(ρ\)≔1−Φ2​\(z,z;ρ\)/Φ​\(z\)f\(\\rho\)\\coloneqq 1\-\{\\Phi\_\{2\}\(z,z;\\rho\)\}/\{\\Phi\(z\)\}with0≤ρ≤10\\leq\\rho\\leq 1\. Sincef​\(ρ\)f\(\\rho\)is strictly decreasing andf​\(1\)=0f\(1\)=0, for any prescribedε∈\(0,1\)\\varepsilon\\in\(0,1\)there exists a unique constantρε∈\(0,1\)\\rho\_\{\\varepsilon\}\\in\(0,1\)such thatf​\(ρε\)≤ε/2f\(\\rho\_\{\\varepsilon\}\)\\leq\\varepsilon/2\. Further, anyρ≥ρε\\rho\\geq\\rho\_\{\\varepsilon\}further reducesf​\(ρ\)f\(\\rho\)to at mostε/2\\varepsilon/2\.

By the definition ofεBE​\(n,ρ\)\\varepsilon\_\{\\text\{BE\}\}\(n,\\rho\), we havesupρ∈\[ρε,1\]εBE​\(n,ρ\)=O​\(n−1/2\)\\sup\_\{\\rho\\in\[\\rho\_\{\\varepsilon\},1\]\}\\varepsilon\_\{\\text\{BE\}\}\(n,\\rho\)=O\(n^\{\-1/2\}\)\. Also, note thatδn=o​\(1\)\\delta\_\{n\}=o\(1\)\. Hence, there exists an integerNNdepending only onγ,z,ε\\gamma,z,\\varepsilonsuch thatεBE​\(n,ρ\)≤ε/2\\varepsilon\_\{\\text\{BE\}\}\(n,\\rho\)\\leq\\varepsilon/2wheneverρ∈\[ρε,1\]\\rho\\in\[\\rho\_\{\\varepsilon\},1\]andn≥Nn\\geq N\. Define the safe deletion budget asssafe​\(n\)≔n​\(1−ρε2\)s\_\{\\mathrm\{safe\}\}\(n\)\\coloneqq n\\,\(1\-\\rho\_\{\\varepsilon\}^\{2\}\)\. If a filter removess≤ssafe​\(n\)s\\leq s\_\{\\mathrm\{safe\}\}\(n\)tokens from the text, thenρ=n′/n=1−s/n≥ρε\\rho=\\sqrt\{n^\{\\prime\}/n\}=\\sqrt\{1\-s/n\}\\geq\\rho\_\{\\varepsilon\}, Hence, for eachn≥Nn\\geq N, it holds thatℙ​\(Z′≥z∣Z<z\)≤f​\(ρ\)\+εBE​\(n,ρ\)≤ε2\+ε2=ε\\mathbb\{P\}\(Z^\{\\prime\}\\\!\\geq z\\mid Z<z\)\\leq f\(\\rho\)\+\\varepsilon\_\{\\text\{BE\}\}\(n,\\rho\)\\leq\\tfrac\{\\varepsilon\}\{2\}\+\\tfrac\{\\varepsilon\}\{2\}=\\varepsilon\. Sinceρε\\rho\_\{\\varepsilon\}is constant innn,ssafe​\(n\)s\_\{\\mathrm\{safe\}\}\(n\)is linear innn\. Thereforessafe​\(n\)=Θ​\(n\)s\_\{\\mathrm\{safe\}\}\(n\)=\\Theta\(n\)\.

### C\.4Proof of Theorem[2](https://arxiv.org/html/2606.18430#Thmtheorem2)

Lets≔⌈c​n⌉≤ns\\coloneqq\\lceil c\\sqrt\{n\}\\rceil\\leq n\. Since the adversary knows the signature, she can compose a text of lengthnnsuch that preciselysstokens will be filtered\. Moreover, whennnis large enough, she can paintNg≔γ​n\+\(z−y\)​σnN\_\{g\}\\coloneqq\\gamma n\+\(z\-y\)\\,\\sigma\_\{n\}of then−sn\-snon\-filtered tokens green and the rest of the tokens red\. This coloring strategy yields the pre\-filter z\-scoreZ=\(Ng−γ​n\)/σn=z−y<z\.Z=\(N\_\{g\}\-\\gamma n\)/\\sigma\_\{n\}=z\-y<z\.Sincen′=n−sn^\{\\prime\}=n\-sandNg′=NgN\_\{g\}^\{\\prime\}=N\_\{g\}, the post\-filter z\-score is

Z′=Ng−γ​\(n−s\)σn−s=\(z−y\)​σn\+γ​sσn​1−s/n=z−y\+c​γ/γ​\(1−γ\)1−c/n\.Z^\{\\prime\}\\;=\\;\\frac\{N\_\{g\}\-\\gamma\(n\-s\)\}\{\\sigma\_\{n\-s\}\}\\;=\\;\\frac\{\(z\-y\)\\sigma\_\{n\}\+\\gamma s\}\{\\sigma\_\{n\}\\sqrt\{1\-s/n\}\}\\;=\\;\\frac\{z\-y\+c\\,\{\\gamma\}/\{\\sqrt\{\\gamma\(1\-\\gamma\)\}\}\}\{\\sqrt\{1\-\{c\}/\{\\sqrt\{n\}\}\}\}\.Note that the denominator ofZ′Z^\{\\prime\}approaches 1 from below asn→∞n\\\!\\to\\\!\\infty\. Sincec\>y​\(1−γ\)/γc\>y\\sqrt\{\(1\-\\gamma\)/\\gamma\}, the numerator ofZ′Z^\{\\prime\}eventually exceedszzasnnincreases\. HenceZ′≥zZ^\{\\prime\}\\geq zholds for all sufficiently largenn\. As for tightness, note that deleting a red token raises the z\-score by at most2​γ/σn=Θ​\(n−1/2\)\.2\\gamma/\\sigma\_\{n\}=\\Theta\(n^\{\-1/2\}\)\.Hence, it requiresΘ​\(n\)\\Theta\(\\sqrt\{n\}\)deletions to make a unit jump in the score, rendering the deletion budget information\-theoretically tight\.

Formally, denote the pre\-filter z\-score of the text byZn≔\(Ng−γ​n\)/σnZ\_\{n\}\\coloneqq\{\(N\_\{g\}\-\\gamma n\)\}/\{\\sigma\_\{n\}\}\. To flip the decision with the smallest possible deletion budget, the attacker must force the filter to delete only red tokens\. For each red token deleted,NgN\_\{g\}is unchanged but the text lengthnndrops by 1\. A direct calculation gives

Zn−1−Zn=Ng−γ​\(n−1\)σn−1−Ng−γ​nσn=γσn−1\+\(Ng−γ​n\)​\(1σn−1−1σn\)\.\\displaystyle Z\_\{n\-1\}\-Z\_\{n\}\\;=\\;\\frac\{N\_\{g\}\-\\gamma\(n\-1\)\}\{\\sigma\_\{n\-1\}\}\-\\frac\{N\_\{g\}\-\\gamma n\}\{\\sigma\_\{n\}\}\\;=\\;\\frac\{\\gamma\}\{\\sigma\_\{n\-1\}\}\+\(N\_\{g\}\-\\gamma n\)\\\!\\left\(\\frac\{1\}\{\\sigma\_\{n\-1\}\}\-\\frac\{1\}\{\\sigma\_\{n\}\}\\right\)\.\(9\)SinceNg−γ​n=O​\(n1/2\)N\_\{g\}\-\\gamma n=O\(n^\{1/2\}\)and1σn−1−1σn=O​\(n−3/2\)\\frac\{1\}\{\\sigma\_\{n\-1\}\}\-\\frac\{1\}\{\\sigma\_\{n\}\}=O\(n^\{\-3/2\}\), the second term isO​\(n−1\)O\(n^\{\-1\}\)\. For allnnlarge enough,

Zn−1−Zn≤2​γγ​\(1−γ\)​1n≕Kn\.\\displaystyle Z\_\{n\-1\}\-Z\_\{n\}\\;\\leq\\;\\frac\{2\\gamma\}\{\\sqrt\{\\gamma\(1\-\\gamma\)\}\}\\,\\frac\{1\}\{\\sqrt\{n\}\}\\;\\eqqcolon\\;\\frac\{K\}\{\\sqrt\{n\}\}\.\(10\)
Suppose that the pre\-filter z\-score isZn=z−δ<zZ\_\{n\}=z\-\\delta<zfor some fixed marginδ\>0\\delta\>0\. To reach the thresholdzzwe must gain at leastδ\\deltaunits, namely,Zn−s−Zn≥δZ\_\{n\-s\}\-Z\_\{n\}\\geq\\delta\. Summing the bounds onZi−1−ZiZ\_\{i\-1\}\-Z\_\{i\}yields

Zn−s−Zn≤K​∑i=0s−11n−i≤K​∫n−snd​tt=2​K​\(n−n−s\)≤2​K​sn,\\displaystyle Z\_\{n\-s\}\-Z\_\{n\}\\;\\leq\\;K\\sum\_\{i=0\}^\{s\-1\}\\frac\{1\}\{\\sqrt\{n\-i\}\}\\;\\leq\\;K\\\!\\int\_\{n\-s\}^\{n\}\\frac\{\\mathrm\{d\}t\}\{\\sqrt\{t\}\}\\;=\\;2K\\bigl\(\\sqrt\{n\}\-\\sqrt\{n\-s\}\\bigr\)\\;\\leq\\;\\frac\{2Ks\}\{\\sqrt\{n\}\},\(11\)where the last inequality follows from the factn−n−s=s/\(n\+n−s\)≤s/n\\sqrt\{n\}\-\\sqrt\{n\-s\}=\{s\}/\(\{\\sqrt\{n\}\+\\sqrt\{n\-s\}\}\)\\leq s/\\\!\\sqrt\{n\}\. Thus, a necessary condition for achieving the required z\-score gainδ\\deltais2​K​s/n≥δ\{2Ks\}/\{\\sqrt\{n\}\}\\geq\\delta, which is equivalent tos≥\(δ/2​K\)​ns\\geq\(\{\\delta\}/\{2K\}\)\{\\sqrt\{n\}\}\.

In conclusion, a deterministic attack can flip the decision by deletingΩ​\(n\)\\Omega\(\\sqrt\{n\}\)tokens\. Conversely, witho​\(n\)o\(\\sqrt\{n\}\)deletions, the maximal possible gain in the z\-score remainso​\(1\)o\(1\), which is insufficient to bridge the fixed gapδ\\delta\. Hence, then\\sqrt\{n\}\-scale deletion budget is both sufficient and necessary\.

### C\.5Proof of Theorem[3](https://arxiv.org/html/2606.18430#Thmtheorem3)

Fix an unwatermarked textTT, and definecsafe≔z4⋅\(1−γ\)/γc\_\{\\mathrm\{safe\}\}\\coloneqq\\tfrac\{z\}\{4\}\\cdot\\sqrt\{\(1\-\\gamma\)/\{\\gamma\}\}\. We claim that whenn=\|T\|n=\|T\|is large enough, \(a\) ifs≤⌊csafe​n⌋s\\leq\\lfloor c\_\{\\mathrm\{safe\}\}\\sqrt\{n\}\\rfloorandz≥zε≔inf\{z\>0:1−Φ​\(z\)Φ​\(2​z\)≤ε4\}z\\geq z\_\{\\varepsilon\}\\coloneqq\\inf\\\{z\>0:\\frac\{1\-\\Phi\(z\)\}\{\\Phi\(2z\)\}\\leq\\frac\{\\varepsilon\}\{4\}\\\}, thenℙerror≤ε\\mathbb\{P\}\_\{\\mathrm\{error\}\}\\leq\\varepsilon; \(b\) ifε∈\(0,12\)\\varepsilon\\in\(0,\\tfrac\{1\}\{2\}\), then there exists a constantcflip\>csafec\_\{\\mathrm\{flip\}\}\>c\_\{\\mathrm\{safe\}\}such thats≥⌈cflip​n⌉s\\geq\\lceil c\_\{\\mathrm\{flip\}\}\\sqrt\{n\}\\rceilimpliesℙerror≥1−ε\\mathbb\{P\}\_\{\\mathrm\{error\}\}\\geq 1\-\\varepsilon\.

We first prove claim \(a\)\. Suppose that the signature has filtereds≤⌊csafe​n⌋s\\leq\\lfloor c\_\{\\mathrm\{safe\}\}\\sqrt\{n\}\\rfloortokens\. The attacker’s best strategy to maximizeℙ​\(Z′≥z∣Z<z\)\\mathbb\{P\}\(Z^\{\\prime\}\\geq z\\mid Z<z\)is to paint all the removed tokens red\. Thus, to estimate the worst\-case flip probability, we can assumeNg′=NgN\_\{g\}^\{\\prime\}=N\_\{g\}\. Recall thatNg′∼Bin​\(n−s,γ\)N\_\{g\}^\{\\prime\}\\sim\\mathrm\{Bin\}\(n\-s,\\,\\gamma\)\. LetX≔Ng′−γ​\(n−s\)X\\coloneqq N\_\{g\}^\{\\prime\}\-\\gamma\(n\-s\)andσn−s≔\(n−s\)​γ​\(1−γ\)\\sigma\_\{n\-s\}\\coloneqq\\sqrt\{\(n\-s\)\\gamma\(1\-\\gamma\)\}\. Note that𝔼​\[X\]=0\\mathbb\{E\}\[X\]=0andVar​\(X\)=σn−s2\\mathrm\{Var\}\(X\)=\\sigma\_\{n\-s\}^\{2\}\. Thus, the two z\-scores are

Z=Ng−γ​nσn=X−γ​sσn,Z′=Ng′−γ​\(n−s\)σn−s=Ng−γ​\(n−s\)σn−s=Xσn−s\.Z\\;=\\;\\frac\{N\_\{g\}\-\\gamma n\}\{\\sigma\_\{n\}\}\\;=\\;\\frac\{X\-\\gamma s\}\{\\sigma\_\{n\}\},\\quad Z^\{\\prime\}\\;=\\;\\frac\{N\_\{g\}^\{\\prime\}\-\\gamma\(n\-s\)\}\{\\sigma\_\{n\-s\}\}\\;=\\;\\frac\{N\_\{g\}\-\\gamma\(n\-s\)\}\{\\sigma\_\{n\-s\}\}\\;=\\;\\frac\{X\}\{\\sigma\_\{n\-s\}\}\.Also, observe thatγ​s≤14​z​σn\\gamma s\\leq\\tfrac\{1\}\{4\}z\\,\\sigma\_\{n\}holds by the assumptions≤⌊csafe​n⌋s\\leq\\lfloor c\_\{\\mathrm\{safe\}\}\\sqrt\{n\}\\rfloor\. Thus,Z<zZ<zimpliesXσn<z\+γ​sσn≤z\+14​z=54​z\.\\frac\{X\}\{\\sigma\_\{n\}\}<z\+\\frac\{\\gamma s\}\{\\sigma\_\{n\}\}\\leq z\+\\frac\{1\}\{4\}z=\\frac\{5\}\{4\}z\.It follows thatℙ​\(Z<z\)≥ℙ​\(Xσn≤54​z\)\.\\mathbb\{P\}\(Z<z\)\\geq\\mathbb\{P\}\(\\tfrac\{X\}\{\\sigma\_\{n\}\}\\leq\\tfrac\{5\}\{4\}z\)\.

SinceXXis the sum of i\.i\.d\. Bernoulli random variables that are centered and bounded by 1, the univariate Berry–Esseen bound givesℙ​\(Xσn−s≤u\)≥Φ​\(u\)−cBEσn−s\\mathbb\{P\}\\bigl\(\\frac\{X\}\{\\sigma\_\{n\-s\}\}\\leq u\\bigr\)\\geq\\Phi\(u\)\-\\frac\{c\_\{\\mathrm\{BE\}\}\}\{\\sigma\_\{n\-s\}\}for anyu∈ℝu\\in\\mathbb\{R\}\. Note that

σn−s=σn​1−sn≥σn​\(1−s2​n\)=σn​\[1\+O​\(1n\)\]\.\\displaystyle\\sigma\_\{n\-s\}\\;=\\;\\sigma\_\{n\}\\sqrt\{1\-\\frac\{s\}\{n\}\}\\;\\geq\\;\\sigma\_\{n\}\(1\-\\frac\{s\}\{2n\}\)\\;=\\;\\sigma\_\{n\}\\,\[1\+O\(\\frac\{1\}\{\\sqrt\{n\}\}\)\]\.\(12\)Thus,Xσn≤54​z\\frac\{X\}\{\\sigma\_\{n\}\}\\leq\\tfrac\{5\}\{4\}zimpliesXσn−s≤2​z\\frac\{X\}\{\\sigma\_\{n\-s\}\}\\leq 2zwhennnis large enough\. Takingu=2​zu=2z, we have

ℙ​\(Z<z\)≥ℙ​\(Xσn−s≤2​z\)≥Φ​\(2​z\)−cBEσn−s≥12​Φ​\(2​z\)\.\\displaystyle\\mathbb\{P\}\(Z<z\)\\;\\geq\\;\\mathbb\{P\}\\bigl\(\\frac\{X\}\{\\sigma\_\{n\-s\}\}\\leq 2z\\bigr\)\\;\\geq\\;\\Phi\(2z\)\-\\frac\{c\_\{\\mathrm\{BE\}\}\}\{\\sigma\_\{n\-s\}\}\\;\\geq\\;\\frac\{1\}\{2\}\\Phi\(2z\)\.\(13\)SinceZ′Z^\{\\prime\}is a centered normalized binomial variable, applying the Berry–Esseen bound again yields

ℙ​\(Z′≥z\)=1−ℙ​\(Z′<z\)≤1−Φ​\(z\)\+cBEσn−s≤1−Φ​\(z\)\+14​ε​Φ​\(2​z\)\.\\displaystyle\\mathbb\{P\}\(Z^\{\\prime\}\\geq z\)\\;=\\;1\-\\mathbb\{P\}\(Z^\{\\prime\}<z\)\\;\\leq\\;1\-\\Phi\(z\)\+\\frac\{c\_\{\\mathrm\{BE\}\}\}\{\\sigma\_\{n\-s\}\}\\;\\leq\\;1\-\\Phi\(z\)\+\\frac\{1\}\{4\}\\varepsilon\\,\\Phi\(2z\)\.\(14\)Finally, we have

ℙ​\(Z′≥z∣Z<z\)≤ℙ​\(Z′≥z\)/ℙ​\(Z<z\)≤\(1−Φ​\(z\)\+14​ε​Φ​\(2​z\)\)/12​Φ​\(2​z\)=2⋅1−Φ​\(z\)Φ​\(2​z\)\+12​ε\.\\displaystyle\\mathbb\{P\}\(Z^\{\\prime\}\\geq z\\mid Z<z\)\\leq\{\\mathbb\{P\}\(Z^\{\\prime\}\\geq z\)\}/\{\\mathbb\{P\}\(Z<z\)\}\\leq\{\(1\-\\Phi\(z\)\+\\frac\{1\}\{4\}\\varepsilon\\,\\Phi\(2z\)\)\}/\{\\frac\{1\}\{2\}\\Phi\(2z\)\}=2\\cdot\\frac\{1\-\\Phi\(z\)\}\{\\Phi\(2z\)\}\+\\frac\{1\}\{2\}\\varepsilon\.\(15\)Sincelimz→∞1−Φ​\(z\)Φ​\(2​z\)=0\\lim\_\{z\\to\\infty\}\\frac\{1\-\\Phi\(z\)\}\{\\Phi\(2z\)\}=0and1−Φ​\(z\)Φ​\(2​z\)\\frac\{1\-\\Phi\(z\)\}\{\\Phi\(2z\)\}is strictly decreasing inzz, we may pickzε≔inf\{z\>0:1−Φ​\(z\)Φ​\(2​z\)≤ε4\}z\_\{\\varepsilon\}\\coloneqq\\inf\\\{z\>0:\\frac\{1\-\\Phi\(z\)\}\{\\Phi\(2z\)\}\\leq\\frac\{\\varepsilon\}\{4\}\\\}such thatz≥zεz\\geq z\_\{\\varepsilon\}impliesℙerror=ℙ​\(Z′≥z∣Z<z\)≤12​ε\+12​ε=ε\\mathbb\{P\}\_\{\\mathrm\{error\}\}=\\mathbb\{P\}\(Z^\{\\prime\}\\geq z\\mid Z<z\)\\leq\\tfrac\{1\}\{2\}\\varepsilon\+\\tfrac\{1\}\{2\}\\varepsilon=\\varepsilon\. This proves part \(a\)\.

We now prove claim \(b\)\. Suppose that the attacker has decided to filters=⌈c​n⌉s=\\lceil c\\sqrt\{n\}\\rceiltokens, whereccis to be determined later\. Again, the best attacker strategy to maximizeℙ​\(Z′≥z∣Z<z\)\\mathbb\{P\}\(Z^\{\\prime\}\\geq z\\mid Z<z\)is to paint all the removed tokens red\. Therefore, we can assume thatNg′=NgN\_\{g\}^\{\\prime\}=N\_\{g\}\. Sinceσn=γ​\(1−γ\)​n\\sigma\_\{n\}=\\sqrt\{\\gamma\(1\-\\gamma\)n\}, we have

Z′=Ng−γ​n\+γ​sσn−s=σn​Z\+γ​sσn−s=σnσn−s​\(Z\+γ​sσn\)=σnσn−s​\(Z\+c′⋅\(1\+o​\(1\)\)\),\\displaystyle Z^\{\\prime\}\\;=\\;\\frac\{N\_\{g\}\-\\gamma n\+\\gamma s\}\{\\sigma\_\{n\-s\}\}\\;=\\;\\frac\{\\sigma\_\{n\}Z\+\\gamma s\}\{\\sigma\_\{n\-s\}\}\\;=\\;\\frac\{\\sigma\_\{n\}\}\{\\sigma\_\{n\-s\}\}\(Z\+\\frac\{\\gamma s\}\{\\sigma\_\{n\}\}\)\\;=\\;\\frac\{\\sigma\_\{n\}\}\{\\sigma\_\{n\-s\}\}\(Z\+c^\{\\prime\}\\cdot\(1\+o\(1\)\)\),\(16\)wherec′≔c​γ1−γc^\{\\prime\}\\coloneqq c\\sqrt\{\\frac\{\\gamma\}\{1\-\\gamma\}\}\. Hence,Z′<zZ^\{\\prime\}<zimpliesZ<σn−sσn​z−c′⋅\(1\+o​\(1\)\)<z−12​c′Z<\\frac\{\\sigma\_\{n\-s\}\}\{\\sigma\_\{n\}\}z\-c^\{\\prime\}\\cdot\(1\+o\(1\)\)<z\-\\frac\{1\}\{2\}c^\{\\prime\}for allnnlarge enough, and

ℙ​\(Z′​<z∣​Z<z\)\\displaystyle\\mathbb\{P\}\\bigl\(Z^\{\\prime\}<z\\mid Z<z\\bigr\)≤ℙ​\(Z​<z−12​c′∣​Z<z\)=Φ​\(z−12​c′\)/Φ​\(z\)\.\\displaystyle\\;\\leq\\;\\mathbb\{P\}\\bigl\(Z<z\-\\tfrac\{1\}\{2\}c^\{\\prime\}\\mid Z<z\\bigr\)\\;=\\;\{\\Phi\(z\-\\tfrac\{1\}\{2\}c^\{\\prime\}\)\}/\{\\Phi\(z\)\}\.\(17\)
Note thatlimt→∞Φ​\(z−t\)/Φ​\(z\)=0\\lim\_\{t\\to\\infty\}\{\\Phi\(z\-t\)\}/\{\\Phi\(z\)\}=0\. Thus, we can choosec′c^\{\\prime\}large enough so thatΦ​\(z−c′/2\)/Φ​\(z\)<ε\{\\Phi\(z\-c^\{\\prime\}/2\)\}/\{\\Phi\(z\)\}<\\varepsilon\. Asc′=c​γ1−γc^\{\\prime\}=c\\sqrt\{\\frac\{\\gamma\}\{1\-\\gamma\}\}, the minimal value ofccto ensure this iscflip≔inf\{c\>0:Φ​\(z−c2​γ1−γ\)/Φ​\(z\)<ε\}\.c\_\{\\mathrm\{flip\}\}\\coloneqq\\inf\\\{c\>0:\{\\Phi\(z\-\\tfrac\{c\}\{2\}\\sqrt\{\\tfrac\{\\gamma\}\{1\-\\gamma\}\}\)\}/\{\\Phi\(z\)\}<\\varepsilon\\\}\.SinceΦ\\Phiis strictly increasing, we haveΦ​\(z−c2​γ1−γ\)/Φ​\(z\)<ε\{\\Phi\(z\-\\tfrac\{c\}\{2\}\\sqrt\{\\tfrac\{\\gamma\}\{1\-\\gamma\}\}\)\}/\{\\Phi\(z\)\}<\\varepsiloniffz−c2​γ1−γ<Φ−1​\(ε​Φ​\(z\)\)\.z\-\\tfrac\{c\}\{2\}\\sqrt\{\\tfrac\{\\gamma\}\{1\-\\gamma\}\}<\\Phi^\{\-1\}\(\\varepsilon\\,\\Phi\(z\)\)\.Therefore,cflip=2​1−γγ​\[z−Φ−1​\(ε​Φ​\(z\)\)\]\.c\_\{\\mathrm\{flip\}\}=2\\sqrt\{\\frac\{1\-\\gamma\}\{\\gamma\}\}\\,\[z\-\\Phi^\{\-1\}\\\!\(\\varepsilon\\,\\Phi\(z\)\)\]\.For anyc≥cflipc\\geq c\_\{\\mathrm\{flip\}\}, pluggingc′=c​γ1−γc^\{\\prime\}=c\\sqrt\{\\frac\{\\gamma\}\{1\-\\gamma\}\}into \([17](https://arxiv.org/html/2606.18430#A3.E17)\) leads toℙ​\(Z′​<z∣​Z<z\)<ε\\mathbb\{P\}\(Z^\{\\prime\}<z\\mid Z<z\)<\\varepsilon\. Consequently,s≥⌈cflip​n⌉s\\geq\\lceil c\_\{\\mathrm\{flip\}\}\\sqrt\{n\}\\rceilimpliesℙerror=ℙ​\(Z′≥z∣Z<z\)≥1−ε\\mathbb\{P\}\_\{\\mathrm\{error\}\}=\\mathbb\{P\}\(Z^\{\\prime\}\\geq z\\mid Z<z\)\\geq 1\-\\varepsilon\.

### C\.6Proof of Theorem[5](https://arxiv.org/html/2606.18430#Thmtheorem5)

Fix an unwatermarked textTTand a significance levelα∈\(0,1\)\\alpha\\in\(0,1\)\. LetZ≔ZE​\(T\)Z\\coloneqq Z\_\{\\textrm\{E\}\}\(T\)andZ′≔ZE​\(T′\)Z^\{\\prime\}\\coloneqq Z\_\{\\textrm\{E\}\}\(T^\{\\prime\}\)be theExpz\-scores before and after filtering \(see Sec\.[3](https://arxiv.org/html/2606.18430#S3)\)\. Writez≔Φ−1​\(1−α\)z\\coloneqq\\Phi^\{\-1\}\(1\-\\alpha\)\. For textTT,Expis an*exact*test, namely,ℙ​\(Z≥z\)=α\\mathbb\{P\}\(Z\\geq z\)=\\alphaandℙ​\(Z<z\)=1−α\\mathbb\{P\}\(Z<z\)=1\-\\alpha\. Assuming score secrecy, the retained pseudo\-random scalars remain i\.i\.d\.𝒰​\[0,1\]\\mathcal\{U\}\[0,1\]forTT\. Thus the retained scores are i\.i\.d\.Exp​\(1\)\\mathrm\{Exp\}\(1\)and the p\-valuepE​\(T′\)p\_\{\\textrm\{E\}\}\(T^\{\\prime\}\)is𝒰​\[0,1\]\\mathcal\{U\}\[0,1\]\. It follows thatℙ​\(Z′≥z\)=α\\mathbb\{P\}\(Z^\{\\prime\}\\geq z\)=\\alpha\. Without any independence assumption betweenZZandZ′Z^\{\\prime\}, we have

ℙerror=ℙ​\(Z′≥z∣Z<z\)=ℙ​\(Z′≥z,Z<z\)/ℙ​\(Z<z\)≤ℙ​\(Z′≥z\)/\(1−α\)=α/\(1−α\)\.\\displaystyle\\mathbb\{P\}\_\{\\mathrm\{error\}\}\\;=\\;\\mathbb\{P\}\(Z^\{\\prime\}\\geq z\\mid Z<z\)\\;=\\;\{\\mathbb\{P\}\(Z^\{\\prime\}\\geq z,Z<z\)\}/\{\\mathbb\{P\}\(Z<z\)\}\\;\\leq\\;\{\\mathbb\{P\}\(Z^\{\\prime\}\\geq z\)\}/\(\{1\-\\alpha\}\)\\;=\\;\{\\alpha\}/\(\{1\-\\alpha\}\)\.\(18\)

### C\.7Safe Deletion Budget Under Unigram Coloring

We establish Theorem[4](https://arxiv.org/html/2606.18430#Thmtheorem4)in this subsection\. Consider an unwatermarked text withℓ\\elldistinct token types, pre\-filter type multiplicities\{mτ\}τ∈𝒱\\\{m\_\{\\tau\}\\\}\_\{\\tau\\in\\mathcal\{V\}\}, and post\-filter type multiplicities\{mτ′\}τ∈𝒱\\\{m^\{\\prime\}\_\{\\tau\}\\\}\_\{\\tau\\in\\mathcal\{V\}\}\. Then the color of each token typeτ\\tauis a Bernoulli random variableCτ∼iidBer​\(γ\)C\_\{\\tau\}\\stackrel\{\{\\scriptstyle\\mathrm\{iid\}\}\}\{\{\\sim\}\}\\mathrm\{Ber\}\(\\gamma\)under unigram coloring\. Define

Q≔∑τmτ2,Q′≔∑τ\(mτ′\)2,r≔Qn,r′≔Q′n′\.Q\\coloneqq\\sum\_\{\\tau\}m\_\{\\tau\}^\{2\},\\quad Q^\{\\prime\}\\coloneqq\\sum\_\{\\tau\}\(m^\{\\prime\}\_\{\\tau\}\)^\{2\},\\quad r\\coloneqq\\frac\{Q\}\{n\},\\quad r^\{\\prime\}\\coloneqq\\frac\{Q^\{\\prime\}\}\{n^\{\\prime\}\}\.The pre\- and post\-filter z\-score can then be expressed by

Z=∑τmτ​\(Cτ−γ\)γ​\(1−γ\)​n,Z′=∑τmτ′​\(Cτ−γ\)γ​\(1−γ\)​n′\.Z\\;=\\;\\frac\{\\sum\_\{\\tau\}m\_\{\\tau\}\(C\_\{\\tau\}\-\\gamma\)\}\{\\sqrt\{\\gamma\(1\-\\gamma\)\\,n\}\},\\qquad Z^\{\\prime\}\\;=\\;\\frac\{\\sum\_\{\\tau\}m^\{\\prime\}\_\{\\tau\}\(C\_\{\\tau\}\-\\gamma\)\}\{\\sqrt\{\\gamma\(1\-\\gamma\)\\,n^\{\\prime\}\}\}\.
Note thatVar​\(Cτ−γ\)=γ​\(1−γ\)\\mathrm\{Var\}\(C\_\{\\tau\}\-\\gamma\)=\\gamma\(1\-\\gamma\)and that the colors are independent across token types\. Since tokens of the same type are either kept intact or moved totally after filtering, we havemτ′∈\{0,mτ\}m^\{\\prime\}\_\{\\tau\}\\in\\\{0,m\_\{\\tau\}\\\}, which implies∑τmτ​mτ′=∑τ\(mτ′\)2=Q′\\sum\_\{\\tau\}m\_\{\\tau\}m^\{\\prime\}\_\{\\tau\}=\\sum\_\{\\tau\}\(m^\{\\prime\}\_\{\\tau\}\)^\{2\}=Q^\{\\prime\}\. Thus,Cov​\(Z,Z′\)=Q′/n​n′\\mathrm\{Cov\}\(Z,Z^\{\\prime\}\)=Q^\{\\prime\}/\\sqrt\{nn^\{\\prime\}\}\.

###### Proposition 5\.

Let a text containℓ\\elldistinct types with multiplicities\{mτ\}\\\{m\_\{\\tau\}\\\}and post\-filter multiplicitiesmτ′∈\{0,mτ\}m^\{\\prime\}\_\{\\tau\}\\in\\\{0,m\_\{\\tau\}\\\}\. Underℋ0\\mathcal\{H\}\_\{0\}and unigram coloring, defineZ~≔Z/r\\widetilde\{Z\}\\coloneqq\{Z\}/\{\\sqrt\{r\}\}andZ~′≔Z′/r′\.\\widetilde\{Z\}^\{\\prime\}\\coloneqq\{Z^\{\\prime\}\}/\{\\sqrt\{r^\{\\prime\}\}\}\.Then\(Z~,Z~′\)\(\\widetilde\{Z\},\\widetilde\{Z\}^\{\\prime\}\)is the sum ofℓ\\ellindependent, mean‑zeroℝ2\\mathbb\{R\}^\{2\}increments and has covarianceΣρ=\(1ρuniρuni1\)\\Sigma\_\{\\rho\}=\\begin\{pmatrix\}1&\\rho\_\{\\mathrm\{uni\}\}\\\\ \\rho\_\{\\mathrm\{uni\}\}&1\\end\{pmatrix\}, whereρuni=Q′/Q\\rho\_\{\\mathrm\{uni\}\}=\\sqrt\{Q^\{\\prime\}/Q\}\. For anya,b∈ℝa,b\\in\\mathbb\{R\}, it holds that

\|ℙ​\(Z~≤a,Z~′≤b\)−Φ2​\(a,b;ρuni\)\|≤C2​μℓ\.\\displaystyle\\left\|\\mathbb\{P\}\\big\(\\widetilde\{Z\}\\leq a,\\widetilde\{Z\}^\{\\prime\}\\leq b\\big\)\-\\Phi\_\{2\}\(a,b;\\rho\_\{\\mathrm\{uni\}\}\)\\right\|\\ \\leq\\ C\_\{2\}\\,\\mu\_\{\\ell\}\.\(19\)Moreover, by definingβℓ≔maxτ⁡mτ/Q\\beta\_\{\\ell\}\\coloneqq\\max\_\{\\tau\}\{m\_\{\\tau\}\}/\\\!\\sqrt\{Q\}, the remainder admits the explicit bound

μℓ≤2γ​\(1−γ\)​\(1−ρuni\)3/2​\(1\+ρuni−1\)​βℓ\.\\mu\_\{\\ell\}\\;\\leq\\;\\frac\{\\sqrt\{2\}\}\{\\sqrt\{\\gamma\(1\-\\gamma\)\}\\,\\big\(1\-\\rho\_\{\\mathrm\{uni\}\}\\big\)^\{3/2\}\}\\Big\(1\+\\rho\_\{\\mathrm\{uni\}\}^\{\-1\}\\Big\)\\beta\_\{\\ell\}\.\(20\)

###### Proof\.

Under unigram coloring,\{Cτ\}τ∈𝒱\\\{C\_\{\\tau\}\\\}\_\{\\tau\\in\\mathcal\{V\}\}are i\.i\.d\. across token types\. We can define per‑type increments

Xτ≔\(wτ​Uτ,wτ′​Uτ\),Uτ≔Cτ−γγ​\(1−γ\),wτ≔mτQ,wτ′≔mτ′Q′\\displaystyle X\_\{\\tau\}\\coloneqq\\Big\(w\_\{\\tau\}\\,U\_\{\\tau\},\\ w^\{\\prime\}\_\{\\tau\}\\,U\_\{\\tau\}\\Big\),\\quad U\_\{\\tau\}\\coloneqq\\frac\{C\_\{\\tau\}\-\\gamma\}\{\\sqrt\{\\gamma\(1\-\\gamma\)\}\},\\quad w\_\{\\tau\}\\coloneqq\\frac\{m\_\{\\tau\}\}\{\\sqrt\{Q\}\},\\quad w^\{\\prime\}\_\{\\tau\}\\coloneqq\\frac\{m^\{\\prime\}\_\{\\tau\}\}\{\\sqrt\{Q^\{\\prime\}\}\}such that\(Z~,Z~′\)=∑τ=1ℓXτ\(\\widetilde\{Z\},\\widetilde\{Z\}^\{\\prime\}\)=\\sum\_\{\\tau=1\}^\{\\ell\}X\_\{\\tau\}with independent, mean‑zeroXτ∈ℝ2X\_\{\\tau\}\\in\\mathbb\{R\}^\{2\}\.

Because𝔼​\[Uτ\]=0\\mathbb\{E\}\[U\_\{\\tau\}\]=0,𝔼​\[Uτ2\]=1\\mathbb\{E\}\[U\_\{\\tau\}^\{2\}\]=1, we haveVar​\(Z~\)=∑τwτ2=1\\mathrm\{Var\}\(\\widetilde\{Z\}\)=\\sum\_\{\\tau\}w\_\{\\tau\}^\{2\}=1,Var​\(Z~′\)=∑τ\(wτ′\)2=1\\mathrm\{Var\}\(\\widetilde\{Z\}^\{\\prime\}\)=\\sum\_\{\\tau\}\(w^\{\\prime\}\_\{\\tau\}\)^\{2\}=1, andCov​\(Z~,Z~′\)=∑τwτ​wτ′=∑τmτ​mτ′Q​Q′=Q′/Q=ρuni\\mathrm\{Cov\}\(\\widetilde\{Z\},\\widetilde\{Z\}^\{\\prime\}\)=\\sum\_\{\\tau\}w\_\{\\tau\}w^\{\\prime\}\_\{\\tau\}=\\tfrac\{\\sum\_\{\\tau\}m\_\{\\tau\}m^\{\\prime\}\_\{\\tau\}\}\{\\sqrt\{QQ^\{\\prime\}\}\}=\\sqrt\{Q^\{\\prime\}/Q\}=\\rho\_\{\\mathrm\{uni\}\}, where we used the factmτ′∈\{0,mτ\}m^\{\\prime\}\_\{\\tau\}\\in\\\{0,m\_\{\\tau\}\\\}to obtain∑τmτ​mτ′=Q′\\sum\_\{\\tau\}m\_\{\\tau\}m^\{\\prime\}\_\{\\tau\}=Q^\{\\prime\}\. Hence,Cov​\(∑τXτ\)=Σρ\\mathrm\{Cov\}\\big\(\\sum\_\{\\tau\}X\_\{\\tau\}\\big\)=\\Sigma\_\{\\rho\}\. For any convex regionAA, the bivariate Berry–Esseen bound yields

\|ℙ​\(Σρ−1/2​∑τXτ∈A\)−Φ2​\(A\)\|≤C2​μℓ\\displaystyle\\Big\|\\mathbb\{P\}\\big\(\\Sigma\_\{\\rho\}^\{\-1/2\}\\textstyle\\sum\_\{\\tau\}X\_\{\\tau\}\\in A\\big\)\-\\Phi\_\{2\}\(A\)\\Big\|\\;\\leq\\;C\_\{2\}\\,\\mu\_\{\\ell\}\(21\)withμℓ=∑τ𝔼​‖Σρ−1/2​Xτ‖23\\mu\_\{\\ell\}=\\sum\_\{\\tau\}\\mathbb\{E\}\\big\\\|\\Sigma\_\{\\rho\}^\{\-1/2\}X\_\{\\tau\}\\big\\\|\_\{2\}^\{3\}\. By changing variablesA↦Σρ−1/2​AA\\mapsto\\Sigma\_\{\\rho\}^\{\-1/2\}A, we can write the above inequality as

\|ℙ​\(\(Z~,Z~′\)∈A\)−Φ2​\(A;ρuni\)\|≤C2​μℓ,\\displaystyle\\Big\|\\mathbb\{P\}\\big\(\(\\widetilde\{Z\},\\widetilde\{Z\}^\{\\prime\}\)\\in A\\big\)\-\\Phi\_\{2\}\(A;\\rho\_\{\\mathrm\{uni\}\}\)\\Big\|\\;\\leq\\;C\_\{2\}\\,\\mu\_\{\\ell\},\(22\)which yields \([19](https://arxiv.org/html/2606.18430#A3.E19)\) whenA=\(−∞,a\]×\(−∞,b\]A=\(\-\\infty,a\]\\times\(\-\\infty,b\]\.

We proceed to boundμℓ\\mu\_\{\\ell\}\. Note that‖Σρ−1/2‖op=\(1−ρuni\)−1/2\\\|\\Sigma\_\{\\rho\}^\{\-1/2\}\\\|\_\{\\mathrm\{op\}\}=\(1\-\\rho\_\{\\mathrm\{uni\}\}\)^\{\-1/2\}asΣρ\\Sigma\_\{\\rho\}has eigenvalues1±ρuni1\\pm\\rho\_\{\\mathrm\{uni\}\}\. Hence,

‖Σρ−1/2​Xτ‖23≤‖Xτ‖23\(1−ρuni\)3/2=\|Uτ\|3\(1−ρuni\)3/2​\(wτ2\+\(wτ′\)2\)3/2\.\\displaystyle\\big\\\|\\Sigma\_\{\\rho\}^\{\-1/2\}X\_\{\\tau\}\\big\\\|\_\{2\}^\{3\}\\ \\leq\\ \\frac\{\\\|X\_\{\\tau\}\\\|\_\{2\}^\{3\}\}\{\(1\-\\rho\_\{\\mathrm\{uni\}\}\)^\{3/2\}\}\\ =\\ \\frac\{\|U\_\{\\tau\}\|^\{3\}\}\{\(1\-\\rho\_\{\\mathrm\{uni\}\}\)^\{3/2\}\}\\ \\big\(w\_\{\\tau\}^\{2\}\+\(w^\{\\prime\}\_\{\\tau\}\)^\{2\}\\big\)^\{3/2\}\.\(23\)Thus,𝔼​\|Uτ\|3=𝔼​\|Cτ−γ\|3/\(γ​\(1−γ\)\)3/2\\mathbb\{E\}\|U\_\{\\tau\}\|^\{3\}=\\mathbb\{E\}\|C\_\{\\tau\}\-\\gamma\|^\{3\}/\(\\gamma\(1\-\\gamma\)\)^\{3/2\}, and𝔼​\|Cτ−γ\|3=γ​\(1−γ\)​\(\(1−γ\)2\+γ2\)≤γ​\(1−γ\)\.\\mathbb\{E\}\|C\_\{\\tau\}\-\\gamma\|^\{3\}=\\gamma\(1\-\\gamma\)\\big\(\(1\-\\gamma\)^\{2\}\+\\gamma^\{2\}\\big\)\\leq\\gamma\(1\-\\gamma\)\.This leads to

𝔼​‖Σρ−1/2​Xτ‖23≤\(wτ2\+\(wτ′\)2\)3/2γ​\(1−γ\)​\(1−ρuni\)3/2\.\\displaystyle\\mathbb\{E\}\\big\\\|\\Sigma\_\{\\rho\}^\{\-1/2\}X\_\{\\tau\}\\big\\\|\_\{2\}^\{3\}\\ \\leq\\ \\frac\{\\big\(w\_\{\\tau\}^\{2\}\+\(w^\{\\prime\}\_\{\\tau\}\)^\{2\}\\big\)^\{3/2\}\}\{\\sqrt\{\\gamma\(1\-\\gamma\)\}\\,\(1\-\\rho\_\{\\mathrm\{uni\}\}\)^\{3/2\}\}\.\(24\)Summing overτ\\tauand exploiting the fact that\(x\+y\)3/2≤21/2​\(x3/2\+y3/2\)\(x\+y\)^\{3/2\}\\leq 2^\{1/2\}\(x^\{3/2\}\+y^\{3/2\}\)forx,y≥0x,y\\geq 0, we have

μℓ≤2γ​\(1−γ\)​\(1−ρuni\)3/2​\(∑τwτ3\+∑τ\(wτ′\)3\)\.\\displaystyle\\mu\_\{\\ell\}\\ \\leq\\ \\frac\{\\sqrt\{2\}\}\{\\sqrt\{\\gamma\(1\-\\gamma\)\}\\,\(1\-\\rho\_\{\\mathrm\{uni\}\}\)^\{3/2\}\}\\Big\(\\sum\_\{\\tau\}w\_\{\\tau\}^\{3\}\+\\sum\_\{\\tau\}\(w^\{\\prime\}\_\{\\tau\}\)^\{3\}\\Big\)\.\(25\)Since∑τwτ2=∑τ\(wτ′\)2=1\\sum\_\{\\tau\}w\_\{\\tau\}^\{2\}=\\sum\_\{\\tau\}\(w^\{\\prime\}\_\{\\tau\}\)^\{2\}=1, it follows that∑τwτ3≤\(maxτ⁡wτ\)​∑τwτ2=maxτ⁡wτ=maxτ⁡mτ/Q\\sum\_\{\\tau\}w\_\{\\tau\}^\{3\}\\leq\(\\max\_\{\\tau\}w\_\{\\tau\}\)\\sum\_\{\\tau\}w\_\{\\tau\}^\{2\}=\\max\_\{\\tau\}w\_\{\\tau\}=\\max\_\{\\tau\}m\_\{\\tau\}/\\sqrt\{Q\}, and similarly forwτ′w^\{\\prime\}\_\{\\tau\}\. Also,mτ′≤mτm^\{\\prime\}\_\{\\tau\}\\leq m\_\{\\tau\}impliesmaxτ⁡wτ′≤maxτ⁡wτ/ρuni\\max\_\{\\tau\}w^\{\\prime\}\_\{\\tau\}\\leq\\max\_\{\\tau\}w\_\{\\tau\}/\\rho\_\{\\mathrm\{uni\}\}\. Hence

∑τwτ3\+∑τ\(wτ′\)3≤maxτ⁡wτ\+maxτ⁡wτ′≤\(1\+ρuni−1\)​βℓ,\\displaystyle\\sum\_\{\\tau\}w\_\{\\tau\}^\{3\}\+\\sum\_\{\\tau\}\(w^\{\\prime\}\_\{\\tau\}\)^\{3\}\\;\\leq\\;\\max\_\{\\tau\}w\_\{\\tau\}\+\\max\_\{\\tau\}w^\{\\prime\}\_\{\\tau\}\\;\\leq\\;\\Big\(1\+\\rho\_\{\\mathrm\{uni\}\}^\{\-1\}\\Big\)\\beta\_\{\\ell\},\(26\)leading to \([20](https://arxiv.org/html/2606.18430#A3.E20)\)\. ∎

###### Proposition 6\.

Under unigram coloring and the null hypothesisℋ0\\mathcal\{H\}\_\{0\}, let

f​\(ρ,r,r′;z\)≔Φ​\(z/r\)−Φ2​\(z/r,z/r′,ρ\)Φ​\(z/r\)\.\\displaystyle f\(\\rho,r,r^\{\\prime\};z\)\\;\\coloneqq\\;\\frac\{\\Phi\\big\(z/\\sqrt\{r\}\\big\)\\;\-\\;\\Phi\_\{2\}\\big\(z/\\sqrt\{r\},\\,z/\\sqrt\{r^\{\\prime\}\},\\,\\rho\\big\)\}\{\\Phi\\big\(z/\\sqrt\{r\}\\big\)\}\.\(27\)For allz\>0z\>0withΦ​\(z/r\)\>δℓ\\Phi\(z/\\sqrt\{r\}\)\>\\delta\_\{\\ell\}, it holds that

\|ℙ\(Z′≥z∣Z<z\)−f\(ρuni,r,r′;z\)\|≤εBE\(ℓ,ρuni\),\\displaystyle\\Big\|\\,\\mathbb\{P\}\(Z^\{\\prime\}\\\!\\geq z\\mid Z<z\)\-f\(\\rho\_\{\\mathrm\{uni\}\},r,r^\{\\prime\};z\)\\,\\Big\|\\;\\leq\\;\\varepsilon\_\{\\mathrm\{BE\}\}\(\\ell,\\rho\_\{\\mathrm\{uni\}\}\),\(28\)whereεBE​\(ℓ,ρuni\)≔\(C2​μℓ\+δℓ\)/\(Φ​\(z/r\)−δℓ\)\\varepsilon\_\{\\mathrm\{BE\}\}\(\\ell,\\rho\_\{\\mathrm\{uni\}\}\)\\coloneqq\(\{C\_\{2\}\\,\\mu\_\{\\ell\}\+\\delta\_\{\\ell\}\}\)/\(\{\\Phi\(z/\\sqrt\{r\}\)\-\\delta\_\{\\ell\}\}\)\.

###### Proof\.

Sinceℙ​\(Z≤z,Z′≤z\)=ℙ​\(Z~≤z/r,Z~′≤z/r′\)\\mathbb\{P\}\(Z\\leq z,Z^\{\\prime\}\\leq z\)=\\mathbb\{P\}\(\\widetilde\{Z\}\\leq z/\\sqrt\{r\},\\,\\widetilde\{Z\}^\{\\prime\}\\leq z/\\sqrt\{r^\{\\prime\}\}\), Proposition[5](https://arxiv.org/html/2606.18430#Thmproposition5)yields\|ℙ​\(Z≤z,Z′≤z\)−Φ2​\(z/r,z/r′;ρuni\)\|≤C2​μℓ\.\\big\|\\mathbb\{P\}\(Z\\leq z,Z^\{\\prime\}\\leq z\)\-\\Phi\_\{2\}\(z/\\sqrt\{r\},z/\\sqrt\{r^\{\\prime\}\};\\rho\_\{\\mathrm\{uni\}\}\)\\big\|\\leq C\_\{2\}\\,\\mu\_\{\\ell\}\.For the marginal denominatorℙ​\(Z<z\)=ℙ​\(Z~<z/r\)\\mathbb\{P\}\(Z<z\)=\\mathbb\{P\}\(\\widetilde\{Z\}<z/\\sqrt\{r\}\), the Berry–Esseen bound gives\|ℙ​\(Z~<z/r\)−Φ​\(z/r\)\|≤δℓ\|\\mathbb\{P\}\(\\widetilde\{Z\}<z/\\sqrt\{r\}\)\-\\Phi\(z/\\sqrt\{r\}\)\|\\leq\\delta\_\{\\ell\}withδℓ≤C1​∑τ𝔼​\|wτ​Uτ\|3≤C1​βℓ/γ​\(1−γ\)\\delta\_\{\\ell\}\\leq C\_\{1\}\\sum\_\{\\tau\}\\mathbb\{E\}\|w\_\{\\tau\}U\_\{\\tau\}\|^\{3\}\\leq C\_\{1\}\\,\\beta\_\{\\ell\}/\\sqrt\{\\gamma\(1\-\\gamma\)\}, noting that𝔼​Uτ2=1\\mathbb\{E\}\\,U\_\{\\tau\}^\{2\}=1\(see the proof of Proposition[5](https://arxiv.org/html/2606.18430#Thmproposition5)\)\. Combining the joint and marginal bounds exactly as in theKgwcase \(Proposition[4](https://arxiv.org/html/2606.18430#Thmproposition4)\), but with the thresholds shifted toz/rz/\\sqrt\{r\}andz/r′z/\\sqrt\{r^\{\\prime\}\}, yields the promised inequality\. ∎

The quantityβℓ=maxτ⁡mτ/Q\\beta\_\{\\ell\}=\\max\_\{\\tau\}m\_\{\\tau\}/\\sqrt\{Q\}can be seen as the largest “type leverage” into the type‑massQ=∑τmτ2Q=\\sum\_\{\\tau\}m\_\{\\tau\}^\{2\}\. If no single token type carries a non‑vanishing fraction of the text asℓ→∞\\ell\\to\\infty\(e\.g\., all multiplicitiesmτm\_\{\\tau\}are within a constant factor of the median\), thenβℓ=O​\(ℓ−1/2\)\\beta\_\{\\ell\}=O\(\\ell^\{\-1/2\}\)and thusδℓ,μℓ=O​\(ℓ−1/2\)\\delta\_\{\\ell\},\\mu\_\{\\ell\}=O\(\\ell^\{\-1/2\}\)\. It follows thatεBE​\(ℓ,ρuni\)=O​\(ℓ−1/2\)\\varepsilon\_\{\\mathrm\{BE\}\}\(\\ell,\\rho\_\{\\mathrm\{uni\}\}\)=O\(\\ell^\{\-1/2\}\)\. When there are no dominating token types, the following proposition establishes Theorem[4](https://arxiv.org/html/2606.18430#Thmtheorem4)in the main text\. \(Notice that the Berry–Esseen bound still holds as a finite\-sample inequality even when there are dominating token types, but the remainder may not shrink withℓ\\ell\.\)

###### Proposition 7\.

Under unigram coloring and the null hypothesisℋ0\\mathcal\{H\}\_\{0\}, assume the non\-degeneracy condition that no single token type carries a non‑vanishing fraction of the text asℓ→∞\\ell\\to\\infty\. Then there exists a uniqueρ⋆=ρ⋆​\(ε;z,γ,r,r′\)∈\(0,1\)\\rho^\{\\star\}=\\rho^\{\\star\}\(\\varepsilon;z,\\gamma,r,r^\{\\prime\}\)\\in\(0,1\)solvingf​\(ρ,r,r′;z\)=ε/2f\(\\rho,r,r^\{\\prime\};z\)=\\varepsilon/2, such that the*type\-mass budget*

Q′≥ρ⋆2​Q⟹ℙ​\(Z′≥z\|Z<z\)≤ε\\displaystyle Q^\{\\prime\}\\;\\geq\\;\\rho\_\{\\star\}^\{2\}\\,Q\\;\\implies\\;\\mathbb\{P\}\\big\(Z^\{\\prime\}\\\!\\geq z\\;\\big\|\\;Z<z\\big\)\\;\\leq\\;\\varepsilon\(29\)holds for all sufficiently largeℓ\\ell\. Equivalently, under unigram coloring, it is safe to delete up to a\(1−ρ⋆2\)\(1\-\\rho\_\{\\star\}^\{2\}\)\-fraction of the pre\-filter type\-massQQwithout exceeding conditional FPRε\\varepsilon\.

###### Proof\.

Givenε∈\(0,1\)\\varepsilon\\in\(0,1\), we can pickρ⋆∈\(0,1\)\\rho\_\{\\star\}\\in\(0,1\)such thatf​\(ρ⋆,r,r′;z\)=ε/2f\(\\rho\_\{\\star\},r,r^\{\\prime\};z\)=\\varepsilon/2, and chooseℓ\\elllarge enough thatεBE​\(ℓ,ρ⋆\)≤ε/2\\varepsilon\_\{\\mathrm\{BE\}\}\(\\ell,\\rho\_\{\\star\}\)\\leq\\varepsilon/2in Proposition[6](https://arxiv.org/html/2606.18430#Thmproposition6)under the non\-degeneracy condition\. IfQ′≥ρ⋆2​QQ^\{\\prime\}\\geq\\rho\_\{\\star\}^\{2\}\\,Q, thenρuni=Q′/Q≥ρ⋆\\rho\_\{\\mathrm\{uni\}\}=\\sqrt\{Q^\{\\prime\}/Q\}\\geq\\rho\_\{\\star\}\. Sincef​\(ρ,r,r′;z\)f\(\\rho,r,r^\{\\prime\};z\)is strictly decreasing inρ∈\(0,1\)\\rho\\in\(0,1\)for fixed\(r,r′,z\)\(r,r^\{\\prime\},z\), we havef​\(ρuni,r,r′;z\)≤f​\(ρ⋆,r,r′;z\)=ε/2f\(\\rho\_\{\\mathrm\{uni\}\},r,r^\{\\prime\};z\)\\leq f\(\\rho\_\{\\star\},r,r^\{\\prime\};z\)=\\varepsilon/2\. Adding the Berry–Esseen remainder yieldsℙ​\(Z′≥z∣Z<z\)≤ε\\mathbb\{P\}\(Z^\{\\prime\}\\\!\\geq z\\mid Z<z\)\\leq\\varepsilonfor all sufficiently largeℓ\\ell\. ∎

## Appendix DComparison with Repeated Context Masking

Table 3:Focused comparison ofKgwandKgw\+RCM on Opt\-1\.3b\. RCM context size is fixed to 8 after sweep validation\. TPR and FPR are fixed\-threshold rates \(%\)\. Eligible WM is the share of watermarked samples that remain eligible after masking\. Avg\. scored WM is the mean number of scored watermarked tokens after prompt handling and any RCM masking\.Repeated context masking \(RCM\) is a non\-distortion mechanism to avoid repeated watermark bias, implemented in watermarks like SynthID\-TextDathathriet al\.\([2024](https://arxiv.org/html/2606.18430#bib.bib12)\)\. In this section, we treatKgw\+RCM as a variant ofKgwand compare it with plainKgw\. Note that RCM is not a pure detector\-side method: during generation, it suppresses theKgwbias whenever the recent left context has already appeared earlier in the same text, and during detection, it excludes those repeated context positions before the z\-test\.

We compareKgw\+RCM andKgwon Opt\-1\.3b over C4,HumanEval, andMbpp\. We select the RCM context size on a validation sweep and use context size 8, which gives the best mean TPR without increasing mean FPR\. Table[3](https://arxiv.org/html/2606.18430#A4.T3)reports the main results\. It turns out that RCM yields only a modest gain on C4 at the weakest setting \(i\.e\.,δ=0\.5\\delta=0\.5, where TPR increases from6\.1%6\.1\\%to7\.5%7\.5\\%\) and is otherwise neutral or slightly worse on C4\. On the low\-variation code benchmarks, RCM reduces TPR across all tested watermark strengths\. This TPR reduction is likely due to substantial masking of scoreable positions, which causes the resulting loss of green evidence to outweigh the benefit from suppressing repeated context bias under the fixedKgwz\-threshold\. More in\-depth evaluation and analysis remain an intriguing future direction\.

## References

- S\. Aaronson and H\. Kirchner \(2022\)Watermarking GPT outputs\.Note:[https://www\.scottaaronson\.com/talks/watermark\.ppt](https://www.scottaaronson.com/talks/watermark.ppt)Presentation slidesCited by:[§2](https://arxiv.org/html/2606.18430#S2.p2.1),[§6](https://arxiv.org/html/2606.18430#S6.p2.1)\.
- E\. Amaldi and V\. Kann \(1995\)The complexity and approximability of finding maximum feasible subsystems of linear relations\.Theoretical Computer Science147\(1\),pp\. 181–210\.External Links:[Document](https://dx.doi.org/10.1016/0304-3975%2894%2900254-G)Cited by:[§4\.1](https://arxiv.org/html/2606.18430#S4.SS1.p6.2)\.
- J\. Austin, A\. Odena, M\. Nye, M\. Bosma, H\. Michalewski, D\. Dohan, E\. Jiang, C\. Cai, M\. Terry, Q\. Le,et al\.\(2021\)Program synthesis with large language models\.arXiv preprint arXiv:2108\.07732\.External Links:[Document](https://dx.doi.org/10.48550/arXiv.2108.07732)Cited by:[§6](https://arxiv.org/html/2606.18430#S6.p1.1)\.
- V\. Bentkus \(2005\)A lyapunov\-type bound inℝd\\mathbb\{R\}^\{d\}\.Theory of Probability & Its Applications49\(2\),pp\. 311–323\.External Links:[Document](https://dx.doi.org/10.1137/S0040585X97981123)Cited by:[Proposition 3](https://arxiv.org/html/2606.18430#Thmproposition3)\.
- A\. Bifet and R\. Gavaldà \(2007\)Learning from time\-changing data with adaptive windowing\.InSIAM International Conference on Data Mining,pp\. 443–448\.External Links:[Document](https://dx.doi.org/10.1137/1.9781611972771.42)Cited by:[§7\.2](https://arxiv.org/html/2606.18430#S7.SS2.p6.1)\.
- B\. Chandra, J\. Dunietz, and K\. Roberts \(2024\)Reducing risks posed by synthetic content: an overview of technical approaches to digital content transparency\.Technical reportTechnical ReportNIST AI 100\-4,National Institute of Standards and Technology\.External Links:[Document](https://dx.doi.org/10.6028/NIST.AI.100-4)Cited by:[§2](https://arxiv.org/html/2606.18430#S2.p1.1)\.
- M\. Chen, J\. Tworek, H\. Jun, Q\. Yuan, H\. Ponde de Oliveira Pinto, J\. Kaplan, H\. Edwards, Y\. Burda, N\. Joseph, G\. Brockman,et al\.\(2021\)Evaluating large language models trained on code\.arXiv preprint arXiv:2107\.03374\.External Links:[Document](https://dx.doi.org/10.48550/arXiv.2107.03374)Cited by:[§6](https://arxiv.org/html/2606.18430#S6.p1.1)\.
- M\. Christ, S\. Gunn, and O\. Zamir \(2024\)Undetectable watermarks for language models\.InAnnual Conference on Learning Theory,pp\. 1125–1139\.External Links:[Document](https://dx.doi.org/10.48550/arXiv.2306.09194)Cited by:[§2](https://arxiv.org/html/2606.18430#S2.p2.1)\.
- S\. Dathathri, A\. See, S\. Ghaisas, P\. Huang, R\. McAdam, J\. Welbl, V\. Bachani, A\. Kaskasoli, R\. Stanforth, T\. Matejovicova, J\. Hayes, N\. Vyas, M\. Al Merey, J\. Brown\-Cohen, R\. Bunel, B\. Balle, T\. Cemgil, Z\. Ahmed, K\. Stacpoole, I\. Shumailov, C\. Baetu, S\. Gowal, D\. Hassabis, and P\. Kohli \(2024\)Scalable watermarking for identifying large language model outputs\.Nature634,pp\. 818–823\.External Links:[Document](https://dx.doi.org/10.1038/s41586-024-08025-4)Cited by:[Appendix D](https://arxiv.org/html/2606.18430#A4.p1.1),[§2](https://arxiv.org/html/2606.18430#S2.p2.1)\.
- X\. Fang, H\. Wu, J\. Jing, Y\. Meng, B\. Yu, H\. Yu, and H\. Zhang \(2024\)NSEP: early fake news detection via news semantic environment perception\.Information Processing & Management61\(2\),pp\. 103594\.External Links:[Document](https://dx.doi.org/10.1016/j.ipm.2023.103594)Cited by:[§2](https://arxiv.org/html/2606.18430#S2.p1.1)\.
- P\. Fernandez, A\. Chaffin, K\. Tit, V\. Chappelier, and T\. Furon \(2023a\)Three bricks to consolidate watermarks for large language models\.InIEEE International Workshop on Information Forensics and Security,pp\. 1–6\.External Links:[Document](https://dx.doi.org/10.1109/WIFS58808.2023.10374576)Cited by:[§3](https://arxiv.org/html/2606.18430#S3.p6.18)\.
- P\. Fernandez, G\. Couairon, H\. Jégou, M\. Douze, and T\. Furon \(2023b\)The stable signature: rooting watermarks in latent diffusion models\.InThe IEEE/CVF International Conference on Computer Vision,pp\. 22466–22477\.External Links:[Document](https://dx.doi.org/10.1109/ICCV51070.2023.02056)Cited by:[§7\.2](https://arxiv.org/html/2606.18430#S7.SS2.p4.1)\.
- F\. F\. Firouzeh, J\. W\. Chinneck, and S\. Rajan \(2022\)Faster maximum feasible subsystem solutions for dense constraint matrices\.Computers & Operations Research139,pp\. 105633\.External Links:[Document](https://dx.doi.org/10.1016/j.cor.2021.105633)Cited by:[§4\.1](https://arxiv.org/html/2606.18430#S4.SS1.p6.2)\.
- J\. Fu, X\. Zhao, R\. Yang, Y\. Zhang, J\. Chen, and Y\. Xiao \(2024\)GumbelSoft: diversified language model watermarking via the Gumbelmax\-trick\.arXiv preprint arXiv:2402\.12948\.External Links:[Document](https://dx.doi.org/10.48550/arXiv.2402.12948)Cited by:[§3](https://arxiv.org/html/2606.18430#S3.p3.8)\.
- J\. Gama, I\. Žliobaitė, A\. Bifet, M\. Pechenizkiy, and A\. Bouchachia \(2014\)A survey on concept drift adaptation\.ACM Computing Surveys46\(4\),pp\. 1–37\.External Links:[Document](https://dx.doi.org/10.1145/2523813)Cited by:[§7\.2](https://arxiv.org/html/2606.18430#S7.SS2.p5.2)\.
- A\. Gretton, K\. M\. Borgwardt, M\. J\. Rasch, B\. Schölkopf, and A\. Smola \(2012\)A kernel two\-sample test\.Journal of Machine Learning Research13\(25\),pp\. 723–773\.External Links:[Document](https://dx.doi.org/10.5555/2188385.2188410)Cited by:[§7\.2](https://arxiv.org/html/2606.18430#S7.SS2.p6.1)\.
- Gurobi Optimization, LLC \(2024\)Gurobi Optimizer Reference Manual\.External Links:[Link](https://www.gurobi.com/)Cited by:[§6](https://arxiv.org/html/2606.18430#S6.p2.1)\.
- Z\. He, B\. Zhou, H\. Hao, A\. Liu, Y\. Li, J\. Liu, L\. Li, X\. Wang, Z\. Tu, Z\. Zhang, and R\. Wang \(2024\)Can watermarks survive translation? on the cross\-lingual consistency of text watermark for large language models\.arXiv preprint arXiv:2402\.14007\.External Links:[Document](https://dx.doi.org/10.48550/arXiv.2402.14007)Cited by:[§5\.3](https://arxiv.org/html/2606.18430#S5.SS3.p2.1),[§7\.2](https://arxiv.org/html/2606.18430#S7.SS2.p3.1)\.
- R\. V\. Hogg, E\. Tanis, and D\. Zimmerman \(2015\)Probability and statistical inference\.9th edition,Pearson\.Cited by:[footnote 1](https://arxiv.org/html/2606.18430#footnote1)\.
- H\. Husain, H\. Wu, T\. Gazit, M\. Allamanis, and M\. Brockschmidt \(2019\)CodeSearchNet challenge: evaluating the state of semantic code search\.arXiv preprint arXiv:1909\.09436\.External Links:[Document](https://dx.doi.org/10.48550/arXiv.1909.09436)Cited by:[§6](https://arxiv.org/html/2606.18430#S6.p1.1)\.
- J\. Kirchenbauer, J\. Geiping, Y\. Wen, J\. Katz, I\. Miers, and T\. Goldstein \(2024a\)A watermark for large language models\.arXiv preprint arXiv:2301\.10226\.External Links:[Document](https://dx.doi.org/10.48550/arXiv.2301.10226)Cited by:[§2](https://arxiv.org/html/2606.18430#S2.p2.1),[§3](https://arxiv.org/html/2606.18430#S3.p2.13),[§5\.3](https://arxiv.org/html/2606.18430#S5.SS3.p2.1),[§6](https://arxiv.org/html/2606.18430#S6.p1.1),[§6](https://arxiv.org/html/2606.18430#S6.p2.1)\.
- J\. Kirchenbauer, J\. Geiping, Y\. Wen, M\. Shu, K\. Saifullah, K\. Kong, K\. Fernando, A\. Saha, M\. Goldblum, and T\. Goldstein \(2024b\)On the reliability of watermarks for large language models\.arXiv preprint arXiv:2306\.04634\.External Links:[Document](https://dx.doi.org/10.48550/arXiv.2306.04634)Cited by:[§2](https://arxiv.org/html/2606.18430#S2.p2.1),[§2](https://arxiv.org/html/2606.18430#S2.p3.1),[§3](https://arxiv.org/html/2606.18430#S3.p9.13),[§6\.2](https://arxiv.org/html/2606.18430#S6.SS2.p1.1)\.
- R\. Kuditipudi, J\. Thickstun, T\. Hashimoto, and P\. Liang \(2024\)Robust distortion\-free watermarks for language models\.Transactions on Machine Learning Research\.External Links:ISSN 2835\-8856,[Document](https://dx.doi.org/10.48550/arXiv.2307.15593)Cited by:[§2](https://arxiv.org/html/2606.18430#S2.p2.1),[§3](https://arxiv.org/html/2606.18430#S3.p3.8)\.
- T\. Lee, S\. Hong, J\. Ahn, I\. Hong, H\. Lee, S\. Yun, J\. Shin, and G\. Kim \(2024\)Who wrote this code? watermarking for code generation\.arXiv preprint arXiv:2305\.15060\.External Links:[Document](https://dx.doi.org/10.48550/arXiv.2305.15060)Cited by:[§2](https://arxiv.org/html/2606.18430#S2.p2.1),[§2](https://arxiv.org/html/2606.18430#S2.p3.1),[§5\.3](https://arxiv.org/html/2606.18430#S5.SS3.p2.1),[§6](https://arxiv.org/html/2606.18430#S6.p2.1)\.
- X\. Li, F\. Ruan, H\. Wang, Q\. Long, and W\. J\. Su \(2025a\)A statistical framework of watermarks for large language models: pivot, detection efficiency and optimal rules\.The Annals of Statistics53\(1\),pp\. 322–351\.External Links:[Document](https://dx.doi.org/10.1214/24-AOS2468)Cited by:[§2](https://arxiv.org/html/2606.18430#S2.p5.1)\.
- X\. Li, F\. Ruan, H\. Wang, Q\. Long, and W\. J\. Su \(2025b\)Robust detection of watermarks for large language models under human edits\.Journal of the Royal Statistical Society: Series B \(Statistical Methodology\)\.External Links:[Document](https://dx.doi.org/10.1093/jrsssb/qkaf056)Cited by:[§2](https://arxiv.org/html/2606.18430#S2.p5.1)\.
- A\. Liu, L\. Pan, X\. Hu, S\. Meng, and L\. Wen \(2024a\)A semantic invariant robust watermark for large language models\.InInternational Conference on Learning Representations,External Links:[Document](https://dx.doi.org/10.48550/arXiv.2310.06356)Cited by:[§7\.2](https://arxiv.org/html/2606.18430#S7.SS2.p3.1)\.
- A\. Liu, L\. Pan, Y\. Lu, J\. Li, X\. Hu, X\. Zhang, L\. Wen, I\. King, H\. Xiong, and P\. S\. Yu \(2024b\)A survey of text watermarking in the era of large language models\.ACM Computing Surveys\.External Links:[Document](https://dx.doi.org/10.1145/3691626)Cited by:[§1](https://arxiv.org/html/2606.18430#S1.p1.1),[§2](https://arxiv.org/html/2606.18430#S2.p2.1)\.
- J\. Lu, A\. Liu, F\. Dong, F\. Gu, J\. Gama, and G\. Zhang \(2019\)Learning under concept drift: a review\.IEEE Transactions on Knowledge and Data Engineering31\(12\),pp\. 2346–2363\.External Links:[Document](https://dx.doi.org/10.1109/TKDE.2018.2876857)Cited by:[§7\.2](https://arxiv.org/html/2606.18430#S7.SS2.p5.2)\.
- Y\. Lu, L\. Pan, J\. Han, L\. Zou, P\. S\. Yu, L\. Wen, X\. Song, and X\. He \(2024\)Entropy\-based text watermarking detection\.arXiv preprint arXiv:2404\.17571\.External Links:[Document](https://dx.doi.org/10.48550/arXiv.2404.17571)Cited by:[§2](https://arxiv.org/html/2606.18430#S2.p3.1),[§5\.3](https://arxiv.org/html/2606.18430#S5.SS3.p2.1)\.
- A\. M\. Luvembe, W\. Li, S\. Li, F\. Liu, and X\. Wu \(2024\)CAF\-ODNN: complementary attention fusion with optimized deep neural network for multimodal fake news detection\.Information Processing & Management61\(3\),pp\. 103653\.External Links:[Document](https://dx.doi.org/10.1016/j.ipm.2023.103653)Cited by:[§2](https://arxiv.org/html/2606.18430#S2.p1.1)\.
- L\. Pan, A\. Liu, J\. Han, Y\. Lu, P\. S\. Yu, and L\. Wen \(2024a\)MarkLLM: an open\-source toolkit for LLM watermarking\.arXiv preprint arXiv:2405\.10051\.External Links:[Document](https://dx.doi.org/10.48550/arXiv.2405.10051)Cited by:[Appendix A](https://arxiv.org/html/2606.18430#A1.p2.2),[§2](https://arxiv.org/html/2606.18430#S2.p2.1),[§3](https://arxiv.org/html/2606.18430#S3.p9.13),[§5\.5](https://arxiv.org/html/2606.18430#S5.SS5.p4.4),[§6\.2](https://arxiv.org/html/2606.18430#S6.SS2.p1.1),[§6](https://arxiv.org/html/2606.18430#S6.p1.1),[§6](https://arxiv.org/html/2606.18430#S6.p2.1)\.
- L\. Pan, A\. Liu, Y\. Lu, Z\. Gao, Y\. Di, L\. Wen, I\. King, and P\. S\. Yu \(2024b\)WaterSeeker: pioneering efficient detection of watermarked segments in large documents\.arXiv preprint arXiv:2409\.05112\.External Links:[Document](https://dx.doi.org/10.18653/v1/2025.findings-naacl.156)Cited by:[§2](https://arxiv.org/html/2606.18430#S2.p2.1),[§2](https://arxiv.org/html/2606.18430#S2.p3.1)\.
- L\. Peng, S\. Jian, Z\. Kan, L\. Qiao, and D\. Li \(2024\)Not all fake news is semantically similar: contextual semantic representation learning for multimodal fake news detection\.Information Processing & Management61\(1\),pp\. 103564\.External Links:[Document](https://dx.doi.org/10.1016/j.ipm.2023.103564)Cited by:[§2](https://arxiv.org/html/2606.18430#S2.p1.1)\.
- M\. E\. Pfetsch \(2008\)Branch\-and\-cut for the maximum feasible subsystem problem\.SIAM Journal on Optimization19\(1\),pp\. 21–38\.External Links:[Document](https://dx.doi.org/10.1137/050645828)Cited by:[§4\.1](https://arxiv.org/html/2606.18430#S4.SS1.p6.2)\.
- R\. Polikar \(2012\)Ensemble learning\.InEnsemble machine learning,pp\. 1–34\.Cited by:[§6\.3](https://arxiv.org/html/2606.18430#S6.SS3.p5.7)\.
- S\. Rabanser, S\. Günnemann, and Z\. C\. Lipton \(2019\)Failing loudly: an empirical study of methods for detecting dataset shift\.InAdvances in Neural Information Processing Systems,Vol\.32\.Cited by:[§7\.2](https://arxiv.org/html/2606.18430#S7.SS2.p6.1)\.
- C\. Raffel, N\. Shazeer, A\. Roberts, K\. Lee, S\. Narang, M\. Matena, Y\. Zhou, W\. Li, and P\. J\. Liu \(2020\)Exploring the limits of transfer learning with a unified text\-to\-text transformer\.Journal of Machine Learning Research21\(140\),pp\. 1–67\.External Links:[Document](https://dx.doi.org/10.5555/3455716.3455856)Cited by:[§6](https://arxiv.org/html/2606.18430#S6.p1.1)\.
- S\. Reynolds, S\. Obitayo, N\. Dalmasso, D\. D\. T\. Ngo, V\. K\. Potluru, and M\. Veloso \(2025\)Toward breaking watermarks in distortion\-free large language models\.arXiv preprint arXiv:2502\.18608\.External Links:[Document](https://dx.doi.org/10.48550/arXiv.2502.18608)Cited by:[§2](https://arxiv.org/html/2606.18430#S2.p5.1),[§5\.2](https://arxiv.org/html/2606.18430#S5.SS2.p1.1)\.
- D\. Tsur, C\. X\. Long, C\. M\. Verdun, S\. Vithana, H\. Hsu, C\. Chen, H\. H\. Permuter, and F\. P\. Calmon \(2025\)HeavyWater and simplexwater: distortion\-free LLM watermarks for low\-entropy distributions\.InAdvances in Neural Information Processing Systems,External Links:[Document](https://dx.doi.org/10.48550/arXiv.2506.06409)Cited by:[§2](https://arxiv.org/html/2606.18430#S2.p5.1)\.
- Z\. Wang, G\. Xu, and M\. Ren \(2025a\)Can attention detect AI\-generated text? A novel Benford’s law\-based approach\.Information Processing & Management62\(4\),pp\. 104139\.External Links:[Document](https://dx.doi.org/10.1016/j.ipm.2025.104139)Cited by:[§1](https://arxiv.org/html/2606.18430#S1.p1.1),[§2](https://arxiv.org/html/2606.18430#S2.p1.1)\.
- Z\. Wang, T\. Gu, B\. Wu, and Y\. Yang \(2025b\)MorphMark: flexible adaptive watermarking for large language models\.InAnnual Meeting of the Association for Computational Linguistics,pp\. 4842–4860\.External Links:[Document](https://dx.doi.org/10.18653/v1/2025.acl-long.240)Cited by:[§2](https://arxiv.org/html/2606.18430#S2.p5.1)\.
- L\. A\. Wolsey \(1998\)Integer programming\.Wiley\-Interscience,New York\.Cited by:[§4\.2](https://arxiv.org/html/2606.18430#S4.SS2.p4.11)\.
- B\. Wouters \(2023\)Optimizing watermarks for large language models\.arXiv preprint arXiv:2312\.17295\.External Links:[Document](https://dx.doi.org/10.48550/arXiv.2312.17295)Cited by:[§2](https://arxiv.org/html/2606.18430#S2.p5.1)\.
- J\. Wu, S\. Yang, R\. Zhan, Y\. Yuan, L\. S\. Chao, and D\. F\. Wong \(2025\)A survey on LLM\-generated text detection: necessity, methods, and future directions\.Computational Linguistics51\(1\),pp\. 275–338\.External Links:[Document](https://dx.doi.org/10.1162/coli%5Fa%5F00549)Cited by:[§1](https://arxiv.org/html/2606.18430#S1.p1.1),[§2](https://arxiv.org/html/2606.18430#S2.p2.1)\.
- C\. Xiong, G\. Zheng, X\. Ma, C\. Li, and J\. Zeng \(2025\)DelphiAgent: a trustworthy multi\-agent verification framework for automated fact verification\.Information Processing & Management62\(6\),pp\. 104241\.External Links:[Document](https://dx.doi.org/10.1016/j.ipm.2025.104241)Cited by:[§1](https://arxiv.org/html/2606.18430#S1.p1.1)\.
- K\. F\. Xylogiannopoulos, P\. Xanthopoulos, P\. Karampelas, and G\. A\. Bakamitsos \(2024\)ChatGPT paraphrased product reviews can confuse consumers and undermine their trust in genuine reviews\. Can you tell the difference?\.Information Processing & Management61\(6\),pp\. 103842\.External Links:[Document](https://dx.doi.org/10.1016/j.ipm.2024.103842)Cited by:[§1](https://arxiv.org/html/2606.18430#S1.p1.1),[§2](https://arxiv.org/html/2606.18430#S2.p1.1)\.
- Z\. Zhang, X\. Zhang, Y\. Zhang, L\. Y\. Zhang, C\. Chen, S\. Hu, A\. Gill, and S\. Pan \(2024\)Large language model watermark stealing with mixed integer programming\.arXiv preprint arXiv:2405\.19677\.External Links:[Document](https://dx.doi.org/10.48550/arXiv.2405.19677)Cited by:[§2](https://arxiv.org/html/2606.18430#S2.p5.1)\.
- X\. Zhao, P\. V\. Ananth, L\. Li, and Y\. Wang \(2023\)Provable robust watermarking for AI\-generated text\.arXiv preprint arXiv:2306\.17439\.External Links:[Document](https://dx.doi.org/10.48550/arXiv.2306.17439)Cited by:[§2](https://arxiv.org/html/2606.18430#S2.p2.1),[§5\.4](https://arxiv.org/html/2606.18430#S5.SS4.p1.13),[§6](https://arxiv.org/html/2606.18430#S6.p2.1)\.