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

Unknown

Conceptio › Archive › arXiv CS

arXiv CSopen access

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

Unknown · 2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

cryptography, security, privacy, cybersecurity

Signature filtering: A lightweight enhancement for statistical watermark detection in large language models Chih-Duo Hong, Yen-Pang Chen, Fang Yu

arXiv:2606.18430v1 [cs.LG] 16 Jun 2026

National Chengchi University, Taipei, Taiwan

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

1. Introduction 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 domains (Xylogiannopoulos et al., 2024). 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 services (Xiong et al., 2025; Wang et al., 2025b). 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 pipelines (Liu et al., 2024b; Wu et al., 2025). 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 edited (Wu et al., 2025). 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 ∗ Chih-Duo Hong is the corresponding author. This research is financially supported by the National Science and Technology Council (NSTC), Taiwan, under grant numbers 112-2222-E004-001-MY3 and 114-2634-F-004-002-MBK.

People with marketing backgrounds are hired by government agencies in a number of capacities. Government agencies at the local, state and federal level all employ marketing professionals in areas including, but not limited to, public relations, property disposal, bond sales and purchasing.

(a) Unwatermarked text

(b) Unwatermarked and filtered

Public sector marketers work for government agencies, nonprofit organizations, and other public institutions. Their goal is to promote the services, products, and policies of their organization to the public.

(d) Watermarked and filtered

Figure 1: Unwatermarked and watermarked texts with and without signature filtering. Words containing filtered tokens are rendered in black. (a) z = −0.14, Red = 50%, Green = 49%; (b) z = 1.66, Red = 29%, Green = 38%, Filtered = 33%; (c) z = 1.63, Red = 44%, Green = 56%; (d) z = 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 decision only for the watermarked text w.r.t. the threshold z0 = 4.

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 illustrates this effect under Kgw: 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. 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 the Kgw coloring 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. For Expstyle 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) for Kgw at negligible false positive rates (FPR). Second, when we apply it to more generic watermark schemes where the Kgw coloring 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 2

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 surveys related work; Sec. 3 presents notation and preliminaries; Sec. 4 introduces the methodology and MILP formulation; Sec. 5 provides false-positive analyses under multiple threat models; Sec. 6 outlines our empirical results and deployment guidance. Sec. 7 discusses research implications, limitations, and future work. 2. Related Work Information integrity. Information integrity is now widely recognized as a socio-technical challenge for information retrieval and content management systems (Chandra et al., 2024). Platforms and institutions must decide at scale whether content is sufficiently authentic and trustworthy. Recent work spans consumer trust in AI-mediated content (Xylogiannopoulos et al., 2024), fake news detection (Fang et al., 2024; Luvembe et al., 2024; Peng et al., 2024), and statistical tests based on distributional regularities (Wang et al., 2025b). 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 signals (Fang et al., 2024) and multimodal co-attention detectors (Luvembe et al., 2024; Peng et al., 2024), 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 text (Liu et al., 2024b; Wu et al., 2025). The signature approach in this work is compatible with two mainstream families of watermarking methods, referred to as the Kgw and Exp families (Pan et al., 2024a,b): the 3

former biases the model’s output distribution to embed signals (Kirchenbauer et al., 2024a; Lee et al., 2024; Kirchenbauer et al., 2024b; Zhao et al., 2023), while the latter guides token selection without distorting the distribution (Aaronson and Kirchner, 2022; Christ et al., 2024; Kuditipudi et al., 2024). Production-oriented watermarks like SynthID-Text (Dathathri et al., 2024) 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. Several detection-time techniques tackle these challenges without changing the embedded watermark. Entropy-based detectors like Ewd reweight token contributions so that high-entropy positions dominate the statistic, improving robustness on low-entropy material (Lu et al., 2024). Sweet instead extends logit-modifying watermarks to code by suppressing low-entropy segments at generation and detection time (Lee et al., 2024). Window-based schemes such as WinMax replace the global score with the maximum over sliding windows to recover signal after edits and dilution, and WaterSeeker further localizes watermarked regions in long documents (Kirchenbauer et al., 2024b; Pan et al., 2024b). 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) recast watermark scheduling as a bi-objective MILP that balances detection power and text quality. Wang et al. (2025a) likewise frame Kgw-style watermark embedding as a multiobjective trade-off, adaptively adjusting watermark strength to better navigate the detectability-quality frontier. Li et al. (2025a,b) instead derive Neyman-Pearson-optimal tests via convex duality and formulate goodness-of-fit tests on the detection side to resist paraphrasing. Tsur et al. (2025) 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, learning n-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 (Zhang et al., 2024; Reynolds et al., 2025). 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. 3. Preliminaries Tokens and token types. A text T is a finite sequence of tokens. Each token in a text is assigned a token type ti ∈ V from a fixed finite vocabulary V. For simplicity, we often identify T of length n with a sequence ⟨t1 , . . . , tn ⟩ of token types. Multiple tokens may share the same type. For example, the text ⟨1, 2, 1, 2, 3⟩ contains five tokens t1 , . . . , t5 but only has three distinct token types: t1 = t3 = 1, t2 = t4 = 2, and t5 = 3. Watermark embedding. Given a token sequence prefix ⟨t1 , . . . , ti−1 ⟩, the LLM generates the next token ti by computing a logit li ∈ R|V| and then sampling ti ∈ V based on the probability distribution induced by the softmax of li . A Kgw-style watermark (Kirchenbauer et al., 2024a) randomly splits V into a green list Gi and a red list Ri at each step i, such that |Gi | = γ |V| with a green ratio γ ∈ (0, 1). Kgw amplifies 4

the sampling probability of green tokens with a selection bias δ > 0. A larger bias δ makes the watermark signal stronger and easier to detect, but may increase text distortion. An Exp-style algorithm (Kuditipudi et al., 2024) guides token sampling through keyed pseudorandom ness. At each step i, Exp selects as the token ti a token satisfying ti ∈ arg maxy∈V li (y)/θ + Gi (y) , where θ is the model temperature and Gi (y) ∼ Gumbel(0, 1) denotes the (keyed) Gumbel noise (Fu et al., 2024). The model temperature θ controls sampling entropy and text diversity, which indirectly affects watermark detectability. When θ is small, the scaled logits li (y)/θ become 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 text T of length |T | = n, the detector runs a hypothesis test to determine whether T contains a watermark, with the null hypothesisp H0 claiming T is unwatermarked. A Kgw detector performs a z-test defined by ZK (T ) := (Ng − γn)/ γ(1 − γ)n, where Ng denotes the number of green tokens in T , and rejects H0 if and only if ZK (T ) ≥ z0 for a prescribed threshold z0 . An Exp detector computes a per-token score and the exact Gamma-tail p-value under H0 (Fernandez et al., 2023a). Specifically, at each position i, the detector generates a pseudorandom vector ui ∈ (0, 1)|V| (from the secret key and local context) and reads out the pseudorandom scalarPRi := ui [ti ]. It then defines n the per-token Exp score ci := − ln(1 − Ri ), and the text-level statistic X := i=1 ci . Under H0 , we have Ri ∼ U [0, 1]. Hence ci ∼ Exp(1) and X ∼ Γ(n, 1). The Exp detector exploits the Gamma-tail p-value pE (T ) := P(Xn ≥ X) = Γ(n, X)/Γ(n) with Xn ∼ Γ(n, 1), and rejects H0 if and only if pE (T ) < α for a prescribed significance level α. Note that we can equivalently define a z-test ZE (T ) := Φ−1 (1 − pE (T )) and z := Φ−1 (1 − α), such that pE (T ) < α ⇐⇒ ZE (T ) ≥ z. For both watermark schemes, detection can be uniformly formalized as a hypothesis test: • H0 (Null hypothesis: T is unwatermarked ). For Kgw, ZK (T ) is approximately N (0, 1) for sufficiently large |T | under H0 . In contrast, Exp is an exact test for any |T | ≥ 1: pE (T ) ∼ U [0, 1] and ZE (T ) ∼ N (0, 1) hold strictly under H0 without asymptotic reliance. • H1 (Alternative hypothesis: T is watermarked ). Under H1 , Kgw increases the expected green-token rate and inflates ZK (T ) beyond zero. Exp biases the realized pseudorandom values Ri toward larger values, making X stochastically larger than its null distribution. This yields smaller pE (T ) and larger ZE (T ). The baseline detector declares T as watermarked if Z(T ) ≥ z0 , with Z = ZK for Kgw and Z = ZE for Exp. Practically, z0 is the detector’s decision threshold on the standardized evidence statistic and therefore controls the Type-I error budget. Increasing z0 makes false positives rarer but also makes true watermarks harder to detect. For Kgw, when ZK (T ) is approximately standard normal, a one-sided significance level α corresponds to z0 ≈ Φ−1 (1 − α). Our experiments adopt z0 = 4 following prior work (Kirchenbauer et al., 2024b; Pan et al., 2024a), which corresponds to a nominal one-sided significance level of about 3.17 × 10−5 . For Exp, α is specified directly and z0 := Φ−1 (1 − α) is the equivalent threshold for the z-test. Signature filtering. A signature S ⊆ V is a set of token types computed during or after text generation. Let Z(T ) denote the scheme-specific test statistic. A detector equipped with a signature S proceeds in two stages (Fig. 2). First, the detector performs the baseline test on the input text T , and declares “watermarked” if Z(T ) ≥ z0 . Otherwise, it deletes from T all tokens whose types belong to S, producing a residual text T ′ . The detector then re-runs the same baseline test on T ′ , computes Z ′ := Z(T ′ ), and declares “watermarked” if Z ′ ≥ z0 and |T ′ | ≥ n0 , a threshold for the filtered text length. We set n0 = 30 throughout this paper.1 Since filtering is only applied when the baseline test fails, the only error it may introduce is to flip an otherwise correct “T is unwatermarked” decision under H0 . The error probability induced by the filter is 1 For Kgw, Z is a z-test that relies on a normal approximation of a binomial evidence count. Here, n = 30 is a standard 0 K conservative rule of thumb to keep this approximation accurate (see e.g., Hogg et al. (2015), and also Appendix B for an explicit tail-bound characterization). For Exp, the Gamma-tail p-value remains exact under H0 for any |T ′ | ≥ 1, but we adopt the same n0 as a minimum-evidence guardrail, keeping the two-stage procedure uniform across watermark schemes.

Phase 1: Offline Signature Generation Train Data

Color /Score

Gen. Constr.

Phase 2: Online Detection Pipeline

MILP Solver

Signature

Inject

Yes

“Watermarked” Input T

Z ≥ z0

Detector

|T ′ | ≥ n0

Filter

Yes

Detector

Z ′ ≥ z0 No

“Natural”

Figure 2: Flowchart of our two-stage watermark detection framework.

therefore Perror := P(Z ′ ≥ z0 | Z < z0 , H0 ). This probability is a conditional Type-I error: it measures how often filtering overturns a baseline acceptance of H0 when the underlying text is unwatermarked. Null calibration after filtering. For Kgw, under the standard coloring model, the hidden green indicators {1{ti ∈ Gi }}ni=1 are i.i.d. Ber(γ) conditioned on the secret key. Since our filter depends only on T and does not access the key, restricting to the retained indices preserves this law. Thus, ZK (T ′ ) has the same null calibration as the original test ZK (T ), and its N (0, 1) approximation improves with the residual length n′ := |T ′ |. We therefore enforce n′ ≥ n0 before acting on the post-filter statistic. For Exp, each retained pseudorandom scalar Ri = ui [ti ] is U[0, 1] under H0 . The retained scores ci ’s remain i.i.d. Exp(1) and the Pn′ post-filter sum XT ′ := i=1 ci satisfies XT ′ ∼ Γ(n′ , 1), which implies pE (T ′ ) ∼ U [0, 1] and ZE (T ′ ) ∼ N (0, 1) in the Gamma model for any n′ ≥ 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 Perror defined earlier. Sec. 5 explores this risk further under distributionally correlated and stronger adversarial settings, relaxing the assumption of null calibration after filtering. 4. Method 4.1. MILP-based Signature Generation Given a set of token types V and a training corpus T , we seek a signature S ⊆ V: if S contains a token type w, then all tokens with the same type will be ignored when we compute the test statistic for a text. For each w ∈ V, we define binary decision variables xw such that xw = 0 means w should be included in S. Kgw-style watermarks. Fix a text T . Let cw denote the number of tokens in T that have type w, and gw denote the number of its green occurrences. Let N and N ′ be the number of tokens in T before and after filtering, and Ng and Ng′ be the number of green tokens in T before and after filtering. Then we can write N=

X w∈V

cw ,

N′ =

X w∈V

cw xw ,

Ng =

X w∈V

gw ,

Ng′ =

X w∈V

gw xw .

(1)

Let p be a constant chosen so that Ng′ ≥ pN ′ implies ZK (T ) ≥ z0 (see later). Note that Ng′ − pN ′ =

X w∈V

(gw − p cw ) xw

(2)

is a linear function over the decision variables {xw : w ∈ V}. For each text T ∈ T , we define an indicator variable yT such that yT = 1 ⇐⇒ Ng′ ≥ pN ′ for P T . We thus reduce signature generation to an optimization problem; any solution {xw } that maximizes T ∈T yT corresponds to a signature maximizing the post-filter detection rate of the corpus T and vice versa. 6

Finally, we specify the constant p for each text T such that Ng′ ≥ pN ′ ensures that the residual text T ′ after filtering is declared watermarked by the detector. For Kgw, ZK (T ) ≥ z0 holds if and only if p p Ng′ ≥ γN ′ + z0 N ′ γ(1 − γ) = (γ + z0 γ(1 − γ)/N ′ ) · N ′ . (3) When N ′ is sufficiently large, that is, when N ′ ≥ γ(1 − γ) · [z0 /(p − γ)]2 , we can safely replace (3) with a sufficient condition Ng′ ≥ pN ′ . For example, when γ = 0.5 and z0 = 4, we can set p = 0.87 to make Ng′ ≥ pN ′ a criterion for detecting watermarks in texts with filtered length N ′ ≥ 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 to Exp. Given a text TP , the Exp detector assigns each token ti a score ci := − ln(1 − Ri ) and uses the text-level statistic X := i ci ′ (Sec. 3). After applying a signature S and retaining P only token types with xw = 1, the residual text T has ′ ′ := length N as above and accumulated score X i: ti ∈S / ci . Analogous to the Kgw case, we define X X X gw := ci , X ′ = gw xw , X ′ − pN ′ = (gw − p cw ) xw . (4) i: ti =w

w∈V

Appendix A shows how to derive a constant p such that X ≥ pN is sufficient for the Exp detector to declare T ′ watermarked, i.e., it implies pE (T ′ ) < α. We can employ the same MILP structure as above for Exp, but replace the Kgw constraint Ng′ ≥ pN ′ with the Exp constraint X ′ ≥ pN ′ . Intuitively, p induces a red-green split for Exp: tokens with scores ci < p behave as red evidence, and signature filtering aims to remove such low-score tokens so that the average retained score per token exceeds the threshold p. It is worth noting that our formulation of optimal signature selection is computationally equivalent to the Maximum Feasible Subsystem (Max-FS) ofP 0–1 Linear Inequalities (Amaldi and Kann, 1995). A Maxn FS has a set of linear inequalities of the form j=1 ai,j xj ≥ 0; the task is to find a binary assignment to x1 , . . . , xn 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 solvers (Pfetsch, 2008) and fast relaxation heuristics (e.g., Firouzeh et al. (2022)) that are highly effective in practice. Thus, signature generation can leverage the rich algorithmic toolkit for Max-FS to enhance practical scalability. ′

′

4.2. Context-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 n-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 admissible n-grams, and token retention is induced by whether the n-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. When n = 1, this scheme degenerates to the original type-level (no-context) filter; increasing n provides finer control over which recurring local fragments are removed. In our experiments, modest values of n yield 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⟩. Suppose the optimized 2-gram signature declares the 2-gram (of, the) inadmissible while keeping all other observed 2-grams admissible. Under our 2-gram retention rule (a token is kept iff all length-2 windows that cover it are admissible), the filtered text becomes T ′ = ⟨analysis, data, is, of, interest, to, the, community⟩. 7

In this example, each of the token types of and the appears twice, yet the filter removes only the of the occurrence. By comparison, a type-level (1-gram) signature would have to delete of or the everywhere to eliminate of the, which would potentially discard useful green evidence. MILP encoding. An n-gram signature can be viewed as selecting a set of admissible local contexts (the n-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 = 1 indicates that the token type w ∈ V is retained after filtering; • yτ1 ,...,τn = 1 indicates that the n-gram (τ1 , . . . , τn ) ∈ V n is declared admissible by the signature. Concretely, consider the 2-gram case. Any interior position j (i.e., 2 ≤ j ≤ m − 1 for |T | = m) is covered by two 2-grams, so the retention rule is the Boolean conjunction xtj = ytj−1 , tj ∧ ytj , tj+1 . Boundary positions are handled by the 2-grams xt1 = yt1 , t2 and xtm = ytm−1 , tm . These Boolean constraints can be encoded using the standard 0–1 linearization (Wolsey, 1998); the objective function and corpus-level regularization remain the same as in Sec. 4.1. Generally, any feasible assignment to {yτ1 ,...,τn } in this MILP defines an n-gram signature S := {(τ1 , . . . , τn ) ∈ V n : yτ1 ,...,τn = 0}. Note that a naive formulation of an n-gram signature introduces O(k n ) binary decision variables, where k is the number of distinct token types. We mitigate this blow-up by considering only effective n-grams, i.e., the n-grams whose removal would discard strictly more red than green tokens, since removing ineffective n-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. 5. Asymptotic 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. In Kgw-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. In Exp-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 large Exp scores. Consequently, filtering is intrinsically more robust for Exp than for Kgw. In Secs 5.1–5.3, we analyze Kgw under 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 when Kgw filtering 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 of n can potentially degrade detection in weaker conditions. We summarize the corresponding false-positive guarantees for Exp in Sec. 5.5. Throughout the analyses, we fix a z-score threshold z > 0 and a tolerance error level ε ∈ (0, 1). For the Kgw-specific bounds, we additionally fix a green ratio γ ∈ (0, 1). For Exp, we write z := Φ−1 (1 − α) for the detector’s significance level α. The error probability of a filter is defined by Perror := P(Z ′ ≥ z | Z < z, H0 ), as discussed in Sec. 3. Full proofs of the theorems can be found in the appendices. 5.1. Signature-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 all Kgw-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 length n, one can compute a bound ssafe = Θ(n) such that any signature filter that deletes at most ssafe tokens guarantees Perror ≤ ε. 8

Theorem 1 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.2. Signature-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 watermark (Reynolds et al., 2025). Theorem 2 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) 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. For every sufficiently large text length n,√a color-adaptive attacker who knows the signature can construct a text with Z ≤ z − η such that deleting O( n)√tokens ensures Perror = 1. Conversely, for any text with Z ≤ z − η, no deterministic flip is possible with o( 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.3. Distributionally 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 formalizes the worst case in this setting: 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 budget s ≥ 0. √We can compute constants c = c(z, γ) and zε such that for all sufficiently large text length n, (i) if s ≤ ⌊c n⌋ and z ≥√zε , then it holds that Perror ≤ ε; (ii) if ε ∈ (0, 12 ), then there exists a constant cflip > c such that s ≥ ⌈cflip n⌉ implies Perror ≥ 1 − ε. Theorem 3 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 patterns (Lee et al., 2024; Lu et al., 2024; He et al., 2024). Because low-entropy phrases tend to appear in both natural and watermarked text (Kirchenbauer et al., 2024a), penalizing such phrases during signature learning or filtering steers the system toward the linear-safe regime of Theorem 1. 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 of Kgw and Sweet (which ignores low-entropy tokens in the z-test) in Secs. 6.1–6.3. 5.4. Signature Filtering for Unigram Watermarks In this subsection, we replace Kgw’s stepwise coloring scheme with the unigram coloring assumption by Unigram (Zhao et al., 2023), where each token type τ ∈ V receives a single random color Cτ ∼ Ber(γ) that is reused by all of its occurrences in the text. Formally, let ℓ be the number of distinct token types in a natural text, and {mτ }τ ∈V beP the pre-filter type P multiplicities, namely, mτ is the number of tokens of type τ ∈ V in the text. Write n = τ ∈V mτ , Q = τ ∈V m2τ , r = Q/n, and define their post-filter analogues n′ , Q′ , r′ . Note that under unigram coloring, a filter either keeps or removes each type in full (so m′τ ∈ {0, mτ }). 9

Theorem 4. Assume that no single token type carries a non-vanishing fraction of the text, e.g., maxτ mτ /n → 0 as ℓ → ∞. Then there exists a constant β = β(ε; z, γ, r, r′ ) ∈ (0, 1) such that for all ℓ sufficiently large, Q′ ≥ βQ implies P(Z ′ ≥ z | Z < z) ≤ ε. Theorem 4 delineates the type-level safe deletion budgetPfor a signature. Intuitively, it shows that the right 2 “sample size” for unigram p coloring is the type-mass Q = τ mτ : the correlation between the pre-filter and ′ post-filter texts is ρ = Q /Q, and it is sufficient to keep a constant fraction of Q. By contrast, Theorem 1 ′ provides a safe budget for removable tokens: keeping a constant p fraction of tokens n /n ≥ c suffices to ′ control the P false-positive risk with a pre/post correlation ρ = n /n under Kgw coloring. In intuition, Q/n2 = τ (mτ /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 p normal approximation with a p vanishing remainder. They differ only in the correlation parameter, namely n′ /n at the token level versus Q′ /Q at the type level, and thus the natural linear budgets are in n versus in Q. 5.5. Signature Filtering for Exp Watermarks The preceding subsections focus on Kgw and Unigram, where the post-filter z-score can change substantially because the filter removes a non-random subset of evidence. For Exp, watermarking is typically more robust. Recall that, under H0 , Exp assigns each realized token a keyed pseudorandom scalar Ri = ui [ti ] ∼ U[0, 1] and a score ci = − ln(1 − Ri ) ∼ Exp(1), and it computes a p-value against a threshold α of 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 vectors ui and realized scalars Ri 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. Theorem 5. Under the score secrecy assumption, Perror ≤ α/(1 − α) holds for any signature filter. Intuitively, for an Exp detector 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 length n′ . 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 the Exp analogues of the threat models we have considered for Kgw: • Signature-aware but score-blind attacker. Theorem 5 holds when the attacker can fully adapt the text to the deployed signature, but cannot infer or influence the hidden Exp pseudorandom 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 the Exp scores for a natural text, so the same theorem holds. • Score-adaptive attacker. If the attacker can predict the per-token scores ci and craft a text such that √ the signature deletes only tokens with near-zero scores, the same scaling in Theorem 2 applies: Θ( n) deletions are sufficient and necessary to deterministically flip a baseline decision with Z ≤ z − η. In practice, α is typically set to 10−4 (Pan et al., 2024a), making Perror effectively negligible by Theorem 5. This robustness result is consistent with our empirical findings: in all evaluated settings, applying signature filtering to Exp introduced no observable increase in false positive rate (≤ 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 length n of 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.

6. Evaluation We evaluate our method on high-entropy natural language and low-entropy code from standard benchmarks for watermark evaluation. For natural-language documents, we use C4 (Raffel et al., 2020). For low-entropy code snippets, we use Mbpp (Austin et al., 2021), HumanEval (Chen et al., 2021), and CodeSearch-Net (Husain et al., 2019). Our experiments follow the standard setup (Kirchenbauer et al., 2024a; Pan et al., 2024a): 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 schemes Kgw, Sweet, Unigram, Exp (Kirchenbauer et al., 2024a; Lee et al., 2024; Zhao et al., 2023; Aaronson and Kirchner, 2022) 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 toolkit (Pan et al., 2024a), signatures are optimized with the Gurobi solver (Gurobi Optimization, LLC, 2024), and all experiments run on a computer with an Intel i9-14900 CPU, an RTX-5080 GPU, and 64 GB of RAM. 6.1. Detection Capability of Signature Filters

=1.0 =0.8 =0.5

100

00-grm 1-grm 2-grm 3-grm 4-grm 5-grm0 TPR (%)

100 50

=1.0 =0.8 =0.5

100

00-grm 1-grm 2-grm 3-grm 4-grm 5-grm0

100

sweet, llama3.1, human-eval =1.0 =0.8 =0.5

unigram, llama3.1, c4 =1.0 =0.8 =0.5

100

00-grm 1-grm 2-grm 3-grm 4-grm 5-grm0

100

unigram, llama3.1, human-eval =1.0 =0.8 =0.5

100

00-grm 1-grm 2-grm 3-grm 4-grm 5-grm0

kgw, llama3.1, mbpp

sweet, llama3.1, mbpp

unigram, llama3.1, mbpp

=1.0 =0.8 =0.5

100

00-grm 1-grm 2-grm 3-grm 4-grm 5-grm0

=1.0 =0.8 =0.5

100

00-grm 1-grm 2-grm 3-grm 4-grm 5-grm0

=1.0 =0.8 =0.5

exp, llama3.1, c4

100 =0.5 =0.3 =0.1

00-grm 1-grm 2-grm 3-grm 4-grm 5-grm0

100

00-grm 1-grm 2-grm 3-grm 4-grm 5-grm0 100 TPR (%)

kgw, llama3.1, human-eval

sweet, llama3.1, c4

FPR (%)

100

exp, llama3.1, human-eval

100

=0.5 =0.3 =0.1

FPR (%)

kgw, llama3.1, c4

00-grm 1-grm 2-grm 3-grm 4-grm 5-grm0

100

00-grm 1-grm 2-grm 3-grm 4-grm 5-grm0

exp, llama3.1, mbpp

100 =0.5 =0.3 =0.1

FPR (%)

TPR (%)

100

00-grm 1-grm 2-grm 3-grm 4-grm 5-grm0

Figure 3: The TPR/FPR of n-gram signature filtering for Llama3.1-8b on C4 (top), Mbpp (middle), and HumanEval (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.

100 100 =1.0 =0.8 =0.5

00-grm 1-grm 2-grm 3-grm 4-grm 5-grm0

TPR (%)

=1.0 =0.8 =0.5

00-grm 1-grm 2-grm 3-grm 4-grm 5-grm0

=0.8 =0.5

00-grm 1-grm 2-grm 3-grm 4-grm 5-grm0

exp, opt-6.7b, c4

exp, llama3.1-8b, c4

100 100 =0.5 10 =0.3 =0.1

00-grm 1-grm 2-grm 3-grm 4-grm 5-grm0 100 50

100 100 10

00-grm 1-grm 2-grm 3-grm 4-grm 5-grm0

sweet, phi-3-14b, c4

100 100 =1.0 =0.8 =0.5

00-grm 1-grm 2-grm 3-grm 4-grm 5-grm0

sweet, qwen2.5-14b, c4

100 =1.0 =0.8 =0.5

00-grm 1-grm 2-grm 3-grm 4-grm 5-grm0

exp, opt-6.7b, human-eval =0.5 =0.3 =0.1

00-grm 1-grm 2-grm 3-grm 4-grm 5-grm0

=0.5 10 =0.3 =0.1

=0.8 =0.5

00-grm 1-grm 2-grm 3-grm 4-grm 5-grm0

=0.8 =0.5

00-grm 1-grm 2-grm 3-grm 4-grm 5-grm0

exp, llama2-13b, c4

exp, phi-3-14b, c4

exp, qwen2.5-14b, c4

=0.5 =0.3 =0.1

100 100 10

00-grm 1-grm 2-grm 3-grm 4-grm 5-grm0

=0.3 =0.1

00-grm 1-grm 2-grm 3-grm 4-grm 5-grm0

100 100 =0.5 10 =0.3 =0.1

00-grm 1-grm 2-grm 3-grm 4-grm 5-grm0

exp, llama3.1-8b, human-eval 100 exp, llama2-13b, human-eval 100 100 100 =0.5 =0.5 =0.3 =0.1

=0.8 =0.5

00-grm 1-grm 2-grm 3-grm 4-grm 5-grm0

100 100

00-grm 1-grm 2-grm 3-grm 4-grm 5-grm0

100 100

FPR (%)

=1.0 =0.8 =0.5

00-grm 1-grm 2-grm 3-grm 4-grm 5-grm0

sweet, llama2-13b, c4 =1.0 =0.8 =0.5

sweet, opt-6.7b, human-eval 100 sweet, llama3.1-8b, human-eval 100 sweet, llama2-13b, human-eval 100 sweet, phi-3-14b, human-eval 100 sweet, qwen2.5-14b, human-eval 100 100 100 100 100 =1.0 =1.0 =1.0 =1.0

100

TPR (%)

100 100

exp, phi-3-14b, human-eval =0.5 =0.3 =0.1

00-grm 1-grm 2-grm 3-grm 4-grm 5-grm0

=0.5 =0.3 =0.1

00-grm 1-grm 2-grm 3-grm 4-grm 5-grm0

100 100 10

100

FPR (%)

TPR (%)

100

sweet, llama3.1-8b, c4

FPR (%)

sweet, opt-6.7b, c4

exp, qwen2.5-14b, human-eval 100 =0.5 =0.3 =0.1

FPR (%)

TPR (%)

100

00-grm 1-grm 2-grm 3-grm 4-grm 5-grm0

Figure 4: This figure replicates experiments in Fig. 3 across LLMs. From top to bottom: Sweet+C4, Sweet+HumanEval, Exp+C4, and Exp+HumanEval. The results show that the qualitative trend of filtering is insensitive to the text generator.

Figs. 3–4 summarize complementary views of signature filtering in weak-signal settings. Fig. 3 focuses on Llama3.1 on high-entropy (C4) and low-entropy (Mbpp and HumanEval) texts and shows TPR/FPR by n-gram order. Fig. 4 replicates the TPR/FPR curves for Kgw and Exp over 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 an n-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 for Unigram, 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. For Kgw-style schemes (Kgw, Sweet, and Unigram), 2-grams strike the best balance across strengths; for Exp, useful signal sits in slightly longer local patterns, making 3-gram or 4-gram signatures more effective. Fig. 4 shows that these sweet spots are remarkably stable across text generators: 2–3-gram signatures consistently deliver the largest TPR gains for Kgw at low FPR, while 3–4-grams do the same for Exp. The spread in TPR/FPR across models at a fixed n-gram order is modest compared with the jump from 0-gram to the best n-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, highorder patterns become more scarce as the watermark strength declines. Hence, long n-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, high n-gram orders no longer improve on the sweet spot. 6.2. Detection Capability under Text Edits word-d

sweet, llama3.1, enc4, =1

word-s-ctx

word-s

TPR (solid)

FPR (dashed)

100 100 unigram, llama3.1, enc4, =1 100 100

exp, llama3.1, enc4, =0.8

100

0-grm wmax 2-grm 3-grm 4-grm 5-grm

TPR (%)

copy-paste

100 100

100

kgw, llama3.1, mbpp, =1

0-grm wmax 2-grm 3-grm 4-grm 5-grm

100 100

0-grm wmax 2-grm 3-grm 4-grm 5-grm

sweet, llama3.1, mbpp, =1

0-grm wmax 2-grm 3-grm 4-grm 5-grm

100 100 unigram, llama3.1, mbpp, =1 100 100

exp, llama3.1, mbpp, =0.8

100

0-grm wmax 2-grm 3-grm 4-grm 5-grm

FPR (%)

kgw, llama3.1, enc4, =1

FPR (%)

TPR (%)

scramble

100

0-grm wmax 2-grm 3-grm 4-grm 5-grm

Figure 5: The TPR/FPR of n-gram signature filtering for Llama3.1-8b on C4 (top) and Mbpp (bottom) in the low-strength (δ = 1 and θ = 0.8) and edited-text regimes. 0-gram means no filter, and wmax corresponds to the WinMax-enhanced baseline.

We stress-test the signatures from Sec. 6.1 against five types of text edits (see Kirchenbauer et al. 2024b; Pan et al. 2024a): 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 with WinMax (Kirchenbauer et al., 2024b), an advanced detection-time module that enhances watermark signals to resist text edits. Instead of testing the whole document once, WinMax slides overlapping windows of various lengths across the text, recomputing the watermark score on each window. The maximum perwindow score is used for the final decision. Fig. 5 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 over WinMax. 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 with Exp is consistent with Sec. 6.1, where Exp benefits 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 all n-gram orders. 12

To quantify when the adaptive-window scoring of WinMax has an advantage, we compute a post-hoc localization metric ∆win := maxW Z(W )−Z(T ) on the edited text T , where maxW Z(W ) is the best window z-score identified by WinMax, and Z(T ) is the z-score of the full document. Larger ∆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 of Exp exceeds that of Kgw, Sweet, and Unigram by about 0.5–1.2 across edit types. This indicates that surviving evidence is more spatially concentrated for Exp than for Kgw-style watermarks. A fixed signature may therefore lose coverage of part of the surviving signal, whereas WinMax can re-localize it by scanning all possible windows on the edited text. Accordingly, in Fig. 5, WinMax consistently attains higher TPR on Exp, though at the cost of a slightly higher FPR due to the maximizing effect. By contrast, signatures improve the global green ratio in Kgwstyle 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. 6.3. Scalability of Signature Filters Table 1: Watermark performance on the first 50k texts in Code-Search-Net (left block) and C4 (right block) under a 60s soft time limit per signature. This table fixes B = 1k and varies G, shifting from the most aggressive bagging (G = 1k) to no bagging (G = 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. Kgw G = 1k G = 10k G = 25k G = 50k No filter Sol. time

Sweet

Unigram

Exp

Kgw

Sweet

Unigram

Exp

TPR

FPR

TPR

FPR

TPR

FPR

TPR

FPR

TPR

FPR

TPR

FPR

TPR

FPR

TPR

FPR

99 94 92 89 10

4 2 1 1 0 5 sec.

98 96 95 94 18

99 82 76 69 10

1 0 0 0 0 4 sec.

99 90 86 82 18

99 73 67 62 18

14 11 10 9 5 10 sec.

93 79 76 73 29

78 43 37 32 31

0 0 0 0 0 67 sec.

87 60 54 48 47

99 91 87 83 9

17 10 8 6 0 4 sec.

92 91 89 88 17

99 72 63 57 8

3 1 1 0 0 4 sec.

98 83 77 73 15

99 65 58 54 11

3 2 1 1 0 6 sec.

98 78 73 70 20

95 72 67 62 61

0 0 0 0 0 61 sec.

97 84 80 77 76

Table 2: Ablation on B with G = 1.2k, evaluated on the first 1.2k texts in Code-Search-Net (left block) and C4 (right block). Kgw B = 1.2k B = 0.6k B = 0.4k B = 0.3k No filter Sol. time

Sweet

Unigram

Exp

Kgw

Sweet

Unigram

Exp

TPR

FPR

TPR

FPR

TPR

FPR

TPR

FPR

TPR

FPR

TPR

FPR

TPR

FPR

TPR

FPR

100 90 84 78 11

0 100 0 95 0 91 0 88 0 20 3 sec.

100 89 81 76 9

0 100 0 94 0 90 0 86 0 16 4 sec.

100 78 66 60 18

9 8 8 7 6 8 sec.

96 84 76 72 29

80 55 46 43 32

0 0 0 0 0 62 sec.

89 71 63 60 48

100 88 80 75 8

8 4 2 2 0 4 sec.

96 92 88 85 15

99 82 73 68 8

4 2 1 0 0 4 sec.

98 89 84 81 15

100 73 61 54 11

1 100 0 84 0 76 0 70 0 20 5 sec.

94 79 74 72 64

0 0 0 0 0 65 sec.

97 88 85 84 78

To evaluate the performance of signature filtering over large corpora, we consider a parameterized deployment strategy called Bag(B,G). At generation time, the training data is divided into groups of G ≥ 1 texts. For each group, we compute a signature on the first B ≤ G texts 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–2 report end-to-end performance of signature filtering over 50k low-entropy Code-Search-Net Python snippets and 50k high-entropy C4 documents on Opt-1.3b. We focus on the low strength regime δ = 0.5 and θ = 0.3, using signatures of 2-grams for Kgw and Sweet, 3-grams for Unigram, and 4-grams for Exp. Table 1 fixes B = 1k and considers G ∈ {1k, 10k, 25k, 50k} over the entire datasets, while Table 2 fixes G = 1.2k and considers B ∈ {1.2k, 0.6k, 0.4k, 0.3k} over the first 1.2k texts. Several patterns emerge: • Kgw/Sweet maintains a controllable TPR–FPR frontier. On Code-Search-Net, Bagging attains near-optimal TPR (99%) with low FPR (1–4%) for G = 1k. Increasing G trades a small TPR loss for further FPR reductions. On C4, the same frontier shifts upward in FPR for G = 1k, while G = 25k tightens 13

FPR to single digits at modest TPR cost. These patterns reflect the effect of text entropy: high-entropy corpora demand larger G to suppress spurious red clusters. • Unigram shows 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. • Exp achieves near-zero FPR with strength-dependent TPR. In Table 1, Exp consistently exhibits nearzero false positives, while its true positive rates vary in the expected way with mode coverage. Because Exp evidence tends to appear in short bursts, larger group sizes can miss some group-specific local structure and thus lose recall. For G = 50k, filtering shows nearly no benefit over the baseline. It is worth noting that the FPR trends in Tables 1–2 differ systematically with corpus entropy across watermark families. Specifically, Kgw exhibits lower false positives on the low-entropy than high-entropy corpora, while Unigram shows the reverse pattern. A plausible explanation is that, in Kgw, 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. Sweet resembles Kgw but ignores low-entropy tokens in the z-test. This attenuates the entropy effect and helps keep Sweet’s false positives low on both corpora. By contrast, Unigram ties 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. For Exp, the false positives remain essentially near zero across both corpora, which is consistent with Theorem 5 under the score secrecy assumption. These results provide practical guidance to tune the parameters (B, G) along the TPR–FPR frontier. Generally, reducing G (or increasing B) raises both TPR and FPR by producing more idiosyncratic signatures whose ensemble maximum tends to exceed the threshold. In contrast, increasing G (or reducing B) accelerates the decline of both TPR and FPR, as a less representative signature generalizes more weakly. When B is too small relative to G, 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 learning (Polikar, 2012). 7. Discussion and implications 7.1. Theoretical 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 standard Kgw coloring 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. 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 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 Perror = P(Z ′ ≥ z0 | Z < z0 , H0 ) 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 to 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. This n threshold reflects a fundamental limit of color-based watermarking, not a specific weakness of signature filtering. 14

We also observe consistent locality patterns in Sec. 6.1. In particular, 2–3-gram signatures work best for Kgw-style schemes, while 3–4-grams work best for Exp. 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.2. Practical 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 like Ewd and WinMax, 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 Perror , (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 (He et al., 2024), 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 evidence (Liu et al., 2024a). 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 (Fernandez et al., 2023b). Because the deletion rule still depends only on observable features, the null-calibration argument in Sec. 3 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 (Gama et al., 2014; Lu et al., 2019). Gradual covariate drift is expected to reduce recall first, because learned n-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) experiments of Sec. 6.3. The FPR remains governed by null calibration, but drift toward highly repetitive prose may push signatures for Kgw-style watermarks toward the distributionally correlated regime characterized in Theorem 3. 15

Operationally, data drift can be monitored using standard methods such as two-sample tests or domaindiscriminator tests (Gretton et al., 2012; Rabanser et al., 2019). If data drift is found to be fast, the bagging strategy in Sec. 6.3 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). 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.3. Limitations 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 the n-scale fragile regime characterized in Theorem 3. In practice, such risk can be mitigated by combining filtering with entropy-aware or semanticsaware 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 quantifies this sensitivity, showing that reducing the per-group training size B lowers 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 size G such 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 for Kgw-style watermarks, it is noticeably higher for Exp (see Tables 1–2). 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 highstakes 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 A. MILP Formulation for Exp Signatures In the following, let Xn ∼ Γ(n, 1) with n ≥ 1 and let γ(x, n) := P(Xn ≥ x) denote its survival function. We first present a sufficient condition that makes Exp watermarks compatible with our signature constraints. Proposition 1. Fix a significance level α ∈ (0, 1) and define c(α) > 1 as the unique root of c e−(c−1) = α on (1, ∞). Then x ≥ c(α) n is a sufficient condition for γ(x, n) < α and n > 1. Proof. Write x = sn with a stretch s > 1. Since Γ(n, 1) can be expressed as a sum of n independent Pfactor n Exp(1) variables, we have Xn = i=1 Yi with each Yi ∼ Exp(1). For any t ∈ (0, 1), Markov’s inequality 16

n gives P(Xn ≥ x) = P etXn ≥ etx ≤ e−tx E[etXn ] = e−tx E[etY1 ] = e−tx (1 − t)−n , since the m.g.f. of Exp(1) is E[etY1 ] = (1 − t)−1 for t < 1. Choosing the optimal t⋆ = 1 − s−1 ∈ (0, 1) then yields the explicit −(s−1) n upper tail bound P(Xn ≥ s n) ≤ s e . Note that the function f (s) = s e−(s−1) satisfies f ′ (s) = e−(s−1) (1 − s) < 0 for all s > 1, so f is strictly decreasing on (1, ∞), with f (1) = 1 and lims→∞ f (s) = 0. Therefore, for each α ∈ (0, 1) there is a unique solution c(α) > 1 to f (s) = α. Let s = c(α) be this unique solution; plugging it into the upper tail bound yields P(Xn ≥ c(α)n) ≤ αn < α for all n > 1. Hence, γ(x, n) = P(Xn ≥ x) < α whenever x ≥ c(α) n. Our experiments fix α = 10−4 following the default setting of MarkLLM (Pan et al., 2024a). Since |T ′ | ∈ [30, 200], we can numerically compute the best linear sufficient condition for detecting Exp watermarks. Proposition 2. Fix α = 10−4 and suppose that n ∈ [30, 200]. Then x ≥ 1.826 n implies that γ(x, n) < α. Proof. Given n and α, let x⋆ = x⋆ (n, α) be the unique solution for γ(x⋆, n) = α. (Such a unique solution exists since γ(0, n) = 1 and γ(x, n) → 0 as x → ∞.) Define rn := x⋆ /n. For every integer n ∈ [30, 200], we can compute rn numerically. The maximal ratio occurs at r30 = max30≤n≤200 rn ≈ 1.82505. For any constant c > r30 , n ∈ [30, 200], and x ≥ c n, it holds that x ≥ c n > r30 n ≥ rn n = x⋆ . Since γ(x, n) is strictly decreasing in x, we have γ(x, n) < γ(x⋆, n) = α. Consequently, x ≥ 1.826 n ensures that γ(x, n) < α. Appendix B. Berry–Esseen Remainders This section establishes the Berry–Esseen remainders we will use throughout the remaining appendices. Pn Let X1 , . . . , Xn be independent random vectors in Rd with E[Xi ] = 0. Define Sn := i=1 Xi with Σn := Cov(Sn ). Write Zd ∼ N (0, Id ) and Φd (A) := P(Zd ∈ A) for any Borel set A ⊆ Rd . Define the standardized Pn 3 −1/2 third moment µn := i=1 E Σn Xi 2 . We use Φ(x) to denote the standard normal cumulative distribution function, and use Φd (x1 , . . . , xd ) to denote its standard d-variate version. Proposition 3 (Bentkus 2005). There is a constant cBE such that for every convex Borel set A ⊆ Rd , it −1/2 holds that P Σn Sn ∈ A − Φd (A) ≤ cBE · d1/4 · µn . p γ(1 − γ)n is the standard deviation of the centered Bernoulli sum Ng − γn = PnRecall that σn := (G − γ), where each Gi ∼ Ber(γ) indicates whether token i is green under the green ratio γ. Propoi i=1 sition 3 instantiated into the following bounds for d = 1 (univariate) and d = 2 (bivariate): Univariate remainder δn . Consider the scalar statistic Z = (Ng − γn)/σn . For any z ∈ R, it holds that Pn 3 nγ(1 − γ) (1 − γ)2 + γ 2 cBE i=1 E|Gi − γ| = cBE ≤ =: δn . P Z ≤ z − Φ(z) ≤ cBE µn = cBE 3 3 σn σn σn Bivariate remainder rn,n′ . Consider the z-scores (Z ′, Z) = (Ng′ − γn′ )/σn′ , (Ng − γn)/σn after and before signature filtering. The bivariate Berry–Esseen gives √ ′ cBE · 21/4 · 2 2 ′ P(Z < z, Z < z) − Φ2 (A) ≤ sup P (Z , Z) ∈ A − Φ2 (A) ≤ =: rn,n′ . γ(1 − γ) ρ3 σn A convex Appendix C. False Positive Analysis for Signature Filtering This section provides the details for Sec. 5.1. We first derive the exact FPR of filtering via binomialhypergeometric tails. We then offer a Gaussian approximation (Proposition 4) 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 in Sec. 5.1.

Appendix C.1. Exact false-positive probability Fix a signature S and a candidate text TPof length n. Let n′ denote the number of tokens that survive n filtering. Under H0 , we can define Ng := i=1 Gi as the number of green tokens in T underPthe Kgw n coloring assumption, where each Gi ∼ Ber(γ). For a color-blind attacker, we can define Ng′ := i=1 Yi Gi as the number of retained green tokens, where Yi is an indicator that token ti survives. Thus, conditioned on Ng = x, it holds that Ng′ | (Ng = x) ∼ HyperGeo(x, n′ , n). Define kz := γn + zσn and kz′ := γn′ + zσn′ , the empirical green fraction thresholds before and after filtering. The exact probability that a text fails the watermark test before filtering (i.e., Ng < kz ) but passes the test after filtering (i.e., Ng′ ≥ kz′ ) is Pflip (n, n′ , z) :=

⌊kz −1⌋

n x γ (1 − γ)n−x p(x), x

x=0

(C.1)

where p(x) := P(Ng′ ≥ kz′ | Ng = x). Appendix C.2. Large-sample normal approximation ′ We may use the central a simple z). More precisely, p approximation of Pflip (n, n , P p limit theorem ′ to obtain n ′ ′ define Z := (Ng −γn)/ γ(1 − γ)n and Z := (Ng −γn )/ γ(1 − γ)n′ . Recall that Ng = i=1 Gi and Ng′ = p p p Pn ′ ′ ′ n′ /n. i=1 Yi Gi . The correlation coefficient of (Ng , Ng ) is ρ = γ(1 − γ)n /( γ(1 − γ)n γ(1 − γ)n ) = ′ ′ The pair (Ng , Ng ) satisfies the joint central limit theorem when n and n are large, in the sense that the jointp distribution of (Z, Z ′ ) converges in distribution to a bivariate normal vector with correlation coefficient ρ = n′ /n. We use Φ2 (·, · ; ρ) to denote the bivariate normal cumulative distribution with correlation ρ. In the rest of this section, we fix an unwatermarked text T under the Kgw coloring assumption, and use the conditional probability P(Z ′ ≥ z | Z < z) to quantify the risk that T is 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 and the bivariate reminder rn,n′ defined in Appendix B. When Φ(z) > δn , it holds that P(Z ′ ≥ z | Z < z) −

Φ(z) − Φ2 (z, z; ρ) Φ(z)

≤

rn,n′ + δn . Φ(z) − δn

(C.2)

Pn Pn Proof. Since Ng = i=1 Gi and Ng′ = i=1 Yi Gi , the pair (Ng , Ng′ ) is a sum of {0, 1}2 -valued vectors whose third absolute centered moments are bounded by 1. Hence, the Berry–Esseen bounds in Proposition 3 yield P(Z ′ < z, Z < z) − Φ2 (z, z; ρ) ≤ rn,n′ and P(Z < z) − Φ(x) ≤ δn . Taking the difference between these two bounds leads to P(Z ′ ≥ z, Z < z) = Φ(z) − Φ2 (z, z; ρ) + ξn,n′ with |ξn,n′ | ≤ rn,n′ + δn . ′ ≥z, Z<z) Define c := Φ(z) − Φ2 (z, z; ρ) and ηn := P(Z < z) − Φ(x). Then P(Z ′ ≥ z | Z < z) = P(ZP(Z<z) = c + ξn,n′ Φ(z) + ηn . Since |ηn | ≤ δn < Φ(z) by assumption, we have Φ(z) + ηn ≥ Φ(z) − δn > 0. It follows that

c + ξn,n′ ξn,n′ Φ(z) − c ηn |ξ ′ | Φ(z) + c |ηn | r ′ + δn c ≤ n,n ≤ n,n − = , Φ(z) + ηn Φ(z) Φ(z) − δn Φ(z) Φ(z) + ηn Φ(z) Φ(z) − δn

(C.3)

where the last inequality follows from |c| ≤ Φ(z) and the Berry–Esseen bounds |ξn,n′ | ≤ rn,n′ and |ηn | ≤ δn . c + ξn,n′ Plugging P(Z ′ ≥ z | Z < z) = Φ(z) + ηn and c = Φ(z) − Φ2 (z, z; ρ) into (C.3) yields the desired bound. Appendix C.3. Proof of Theorem 1 For fixed γ ∈ (0, 1), z > 0, ε ∈ (0, 1), and every finite n such that Φ(z) > δn , Proposition 4 asserts that P Z ′ ≥ z | Z < z ≤ f (ρ) + εBE (n, ρ). (C.4) Here εBE (n, ρ) := (rn,n′ + δn ) / (Φ(z) − δn ) is the Berry–Esseen remainder, and f (ρ) := 1 − Φ2 (z, z; ρ)/Φ(z) with 0 ≤ ρ ≤ 1. Since f (ρ) is strictly decreasing and f (1) = 0, for any prescribed ε ∈ (0, 1) there exists a unique constant ρε ∈ (0, 1) such that f (ρε ) ≤ ε/2. Further, any ρ ≥ ρε further reduces f (ρ) to at most ε/2. 18

By the definition of εBE (n, ρ), we have supρ∈[ρε ,1] εBE (n, ρ) = O(n−1/2 ). Also, note that δn = o(1). Hence, there exists an integer N depending only on γ, z, ε such that εBE (n, ρ) ≤ ε/2 whenever ρ ∈ [ρε , 1] 2 and n ≥ N . Define the safe p budget as ssafe (n) := n (1 − ρε ). If a filter removes s ≤′ ssafe (n) tokens p deletion ′ from the text, then ρ = n /n = 1 − s/n ≥ ρε , Hence, for each n ≥ N , it holds that P(Z ≥ z | Z < z) ≤ f (ρ) + εBE (n, ρ) ≤ 2ε + 2ε = ε. Since ρε is constant in n, ssafe (n) is linear in n. Therefore ssafe (n) = Θ(n). Appendix C.4. Proof of Theorem 2 √ Let s := ⌈c n⌉ ≤ n. Since the adversary knows the signature, she can compose a text of length n such that precisely s tokens will be filtered. Moreover, when n is large enough, she can paint Ng := γn+(z −y) σn of the n−s non-filtered tokens green and the rest of the tokens red. This coloring strategy yields the pre-filter z-score Z = (Ng − γn)/σn = z − y < z. Since n′ = n − s and Ng′ = Ng , the post-filter z-score is p z − y + c γ/ γ(1 − γ) (z − y)σn + γs Ng − γ(n − s) p p . = = Z = √ σn−s σn 1 − s/n 1 − c/ n ′

p Note that the denominator of Z ′ approaches 1 from below as n → ∞. Since c > y (1 − γ)/γ, the numerator of Z ′ eventually exceeds z as n increases. Hence Z ′ ≥ z holds for all sufficiently large n. As for tightness, √ note that deleting a red token raises the z-score by at most 2γ/σn = Θ(n−1/2 ). Hence, it requires Θ( 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 by Zn := (Ng − γn)/σ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, Ng is unchanged but the text length n drops by 1. A direct calculation gives Ng − γ(n − 1) Ng − γn γ 1 1 Zn−1 − Zn = − = + (Ng − γn) − . (C.5) σn−1 σn σn−1 σn−1 σn 1 − σ1n = O(n−3/2 ), the second term is O(n−1 ). For all n large enough, Since Ng − γn = O(n1/2 ) and σn−1

Zn−1 − Zn ≤ p

2γ

K 1 √ =: √ . n γ(1 − γ) n

(C.6)

Suppose that the pre-filter z-score is Zn = z − δ < z for some fixed margin δ > 0. To reach the threshold z we must gain at least δ units, namely, Zn−s − Zn ≥ δ. Summing the bounds on Zi−1 − Zi yields s−1 X

Z n √ √ 1 2Ks dt √ √ = 2K n − n − s ≤ √ , Zn−s − Zn ≤ K ≤ K n n−i t n−s i=0

(C.7)

√ √ √ √ √ where the last inequality follows from the fact n − n − s√= s/( n + n − s) ≤ s/ n. Thus, a necessary √ condition for achieving the required z-score gain δ is 2Ks/ n ≥ δ, which is equivalent to s ≥ (δ/2K) n. √ √In conclusion, a deterministic attack can flip the decision by deleting Ω( n) tokens. Conversely, with o( n) deletions, the maximal possible gain in the z-score remains o(1), which is insufficient to bridge the √ fixed gap δ. Hence, the n-scale deletion budget is both sufficient and necessary. Appendix C.5. Proof of Theorem 3 p Fix an unwatermarked text T , and define csafe := z4 · (1 − γ)/γ. We claim that when n = |T | is large √ enough, (a) if s ≤ ⌊csafe n⌋ and z ≥ zε := inf{z > 0 : 1−Φ(z) ≤ 4ε }, then Perror ≤ ε; (b) if ε ∈ (0, 12 ), then √ Φ(2z) there exists a constant cflip > csafe such that s ≥ ⌈cflip n⌉ implies Perror ≥ 1 − ε. √ We first prove claim (a). Suppose that the signature has filtered s ≤ ⌊csafe n⌋ tokens. The attacker’s best strategy to maximize P(Z ′ ≥ z | Z < z) is to paint all the removed tokens red. Thus, to estimate the

worst-case flip probability, we can assume Ng′ = Ng . Recall that Ng′ ∼ Bin(n − s, γ). Let X := Ng′ − γ(n − s) p 2 . Thus, the two z-scores are and σn−s := (n − s)γ(1 − γ). Note that E[X] = 0 and Var(X) = σn−s Ng′ − γ(n − s) Ng − γ(n − s) X = = . σn−s σn−s σn−s √ Also, observe that γs ≤ 14 z σn holds by the assumption s ≤ ⌊csafe n⌋. Thus, Z < z implies σXn < z + σγsn ≤ z + 14 z = 45 z. It follows that P(Z < z) ≥ P( σXn ≤ 54 z). Since X is the sum of i.i.d. Bernoulli random variables that are centered and bounded by 1, the univariate X BE ≤ u ≥ Φ(u) − σcn−s for any u ∈ R. Note that Berry–Esseen bound gives P σn−s r s s 1 σn−s = σn 1 − (C.8) ≥ σn (1 − ) = σn [1 + O( √ )]. n 2n n Z =

Ng − γn X − γs = , σn σn

Z′ =

X ≤ 2z when n is large enough. Taking u = 2z, we have Thus, σXn ≤ 45 z implies σn−s

P(Z < z) ≥ P

X σn−s

≤ 2z

≥ Φ(2z) −

cBE 1 ≥ Φ(2z). σn−s 2

(C.9)

Since Z ′ is a centered normalized binomial variable, applying the Berry–Esseen bound again yields P(Z ′ ≥ z) = 1 − P(Z ′ < z) ≤ 1 − Φ(z) +

1 cBE ≤ 1 − Φ(z) + ε Φ(2z). σn−s 4

(C.10)

Finally, we have 1 1 1 − Φ(z) 1 P(Z ′ ≥ z | Z < z) ≤ P(Z ′ ≥ z)/P(Z < z) ≤ (1 − Φ(z) + ε Φ(2z))/ Φ(2z) = 2 · + ε. 4 2 Φ(2z) 2

(C.11)

1−Φ(z) ε := inf{z > 0 : 1−Φ(z) Since limz→∞ 1−Φ(z) Φ(2z) = 0 and Φ(2z) is strictly decreasing in z, we may pick zε Φ(2z) ≤ 4 } such that z ≥ zε implies Perror = P(Z ′ ≥ z | Z < z) ≤ 21 ε + 21 ε = ε. This proves part (a). √ We now prove claim (b). Suppose that the attacker has decided to filter s = ⌈c n⌉ tokens, where c is ′ to be determined later. Again, the best attacker strategy to maximize P(Zp ≥ z | Z < z) is to paint all the ′ removed tokens red. Therefore, we can assume that Ng = Ng . Since σn = γ(1 − γ)n, we have

Z′ =

σn Z + γs σn γs σn Ng − γn + γs = = (Z + ) = (Z + c′ · (1 + o(1))), σn−s σn−s σn−s σn σn−s

(C.12)

q γ where c′ := c 1−γ . Hence, Z ′ < z implies Z < σσn−s z − c′ · (1 + o(1)) < z − 21 c′ for all n large enough, and n P Z ′ < z | Z < z ≤ P Z < z − 12 c′ | Z < z = Φ(z − 12 c′ )/Φ(z). (C.13) ′ ′ Note that q limt→∞ Φ(z − t)/Φ(z) = 0. Thus, we can choose c large enough so that q Φ(z − c /2)/Φ(z) < ε. γ γ As c′ = c 1−γ , the minimal value of c to ensure this is cflip := inf{c > 0 : Φ(z − 2c 1−γ )/Φ(z) < ε}. Since q q γ γ )/Φ(z) < ε iff z − 2c 1−γ < Φ−1 (ε Φ(z)). Therefore, cflip = Φ is strictly increasing, we have Φ(z − 2c 1−γ q q γ −1 ′ ′ 2 1−γ γ [z − Φ (ε Φ(z))]. For any c ≥ cflip , plugging c = c 1−γ into (C.13) leads to P(Z < z | Z < z) < ε. √ Consequently, s ≥ ⌈cflip n⌉ implies Perror = P(Z ′ ≥ z | Z < z) ≥ 1 − ε.

Appendix C.6. Proof of Theorem 5 Fix an unwatermarked text T and a significance level α ∈ (0, 1). Let Z := ZE (T ) and Z ′ := ZE (T ′ ) be the Exp z-scores before and after filtering (see Sec. 3). Write z := Φ−1 (1 − α). For text T , Exp is an exact test, namely, P(Z ≥ z) = α and P(Z < z) = 1 − α. Assuming score secrecy, the retained pseudo-random scalars remain i.i.d. U [0, 1] for T . Thus the retained scores are i.i.d. Exp(1) and the p-value pE (T ′ ) is U[0, 1]. It follows that P(Z ′ ≥ z) = α. Without any independence assumption between Z and Z ′ , we have Perror = P(Z ′ ≥ z | Z < z) = P(Z ′ ≥ z, Z < z)/P(Z < z) ≤ P(Z ′ ≥ z)/(1 − α) = α/(1 − α). 20

(C.14)

Appendix C.7. Safe Deletion Budget Under Unigram Coloring We establish Theorem 4 in this subsection. Consider an unwatermarked text with ℓ distinct token types, pre-filter type multiplicities {mτ }τ ∈V , and post-filter type multiplicities {m′τ }τ ∈V . Then the color of each iid

token type τ is a Bernoulli random variable Cτ ∼ Ber(γ) under unigram coloring. Define Q :=

m2τ ,

Q′ :=

(m′τ )2 ,

r :=

Q , n

r′ :=

Q′ . n′

The pre- and post-filter z-score can then be expressed by P P ′ ′ τ mτ (Cτ − γ) τ mτ (Cτ − γ) p Z = , Z = p . γ(1 − γ) n γ(1 − γ) n′ Note that Var(Cτ − γ) = γ(1 − γ) and that the colors are independent across token types. Since tokens ′ of the same type kept intact or moved totally √ after filtering, we have mτ ∈ {0, mτ }, which implies P P are′ either ′ 2 ′ ′ ′ ′ τ mτ mτ = τ (mτ ) = Q . Thus, Cov(Z, Z ) = Q / nn . Proposition 5. Let a text contain ℓ distinct types with multiplicities {mτ } and√post-filter multiplicities e := Z/√r and Ze′ := Z ′ / r′ . Then (Z, e Ze′ ) is the m′τ ∈ {0, mτ }. Under H0 and unigram coloring, define Z p 1 ρuni 2 sum of ℓ independent, mean-zero R increments and has covariance Σρ = ρuni 1 , where ρuni = Q′ /Q. For any a, b ∈ R, it holds that (C.15)

e ≤ a, Ze′ ≤ b − Φ2 (a, b; ρuni ) ≤ C2 µℓ . P Z √ Moreover, by defining βℓ := maxτ mτ / Q, the remainder admits the explicit bound √ 2 −1 µℓ ≤ p 1 + ρ 3/2 uni βℓ . γ(1 − γ) 1 − ρuni

(C.16)

Proof. Under unigram coloring, {Cτ }τ ∈V are i.i.d. across token types. We can define per-type increments Xτ := wτ Uτ , wτ′ Uτ ,

Cτ − γ , Uτ := p γ(1 − γ)

mτ wτ := √ , Q

m′ wτ′ := √ τ ′ Q

e Ze′ ) = Pℓ Xτ with independent, mean-zero Xτ ∈ R2 . such that (Z, τ =1 e = P wτ2 = 1, Var(Ze′ ) = P (wτ′ )2 = 1, and Cov(Z, e Z e′ ) = Because E[U ] = 0, E[Uτ2 ] = 1, we have Var(Z) τ τ τ P p ′ P P ′ τ mτ mτ √ = Q′ /Q = ρuni , where we used the fact m′τ ∈ {0, mτ } to obtain τ mτ m′τ = Q′ . ′ τ wτ wτ = P QQ Hence, Cov τ Xτ = Σρ . For any convex region A, the bivariate Berry–Esseen bound yields P Σ−1/2 ρ with µℓ =

τ E

−1/2

Σρ

τ Xτ ∈ A

− Φ2 (A) ≤ C2 µℓ −1/2

Xτ 2 . By changing variables A 7→ Σρ

(C.17)

A, we can write the above inequality as

e Ze′ ) ∈ A − Φ2 (A; ρuni ) ≤ C2 µℓ , P (Z,

(C.18)

which yields (C.15) when A = (−∞, a] × (−∞, b]. −1/2 We proceed to bound µℓ . Note that ∥Σρ ∥op = (1 − ρuni )−1/2 as Σρ has eigenvalues 1 ± ρuni . Hence, 3

Σ−1/2 Xτ 2 ≤ ρ

3/2 |Uτ |3 ∥Xτ ∥32 = wτ2 + (wτ′ )2 . 3/2 3/2 (1 − ρuni ) (1 − ρuni ) 21

(C.19)

Thus, E|Uτ |3 = E|Cτ − γ|3 /(γ(1 − γ))3/2 , and E|Cτ − γ|3 = γ(1 − γ) (1 − γ)2 + γ 2 ≤ γ(1 − γ). This leads to wτ2 + (wτ′ )2

E Σ−1/2 Xτ 2 ≤ p ρ

3/2

γ(1 − γ) (1 − ρuni )3/2

(C.20)

Summing over τ and exploiting the fact that (x + y)3/2 ≤ 21/2 (x3/2 + y 3/2 ) for x, y ≥ 0, we have √ X X 2 µℓ ≤ p (C.21) wτ3 + (wτ′ )3 . γ(1 − γ) (1 − ρuni )3/2 τ τ P P P P √ Since τ wτ2 = τ (wτ′ )2 = 1, it follows that τ wτ3 ≤ (maxτ wτ ) τ wτ2 = maxτ wτ = maxτ mτ / Q, and similarly for wτ′ . Also, m′τ ≤ mτ implies maxτ wτ′ ≤ maxτ wτ /ρuni . Hence X X wτ3 + (wτ′ )3 ≤ max wτ + max wτ′ ≤ 1 + ρ−1 (C.22) uni βℓ , τ

leading to (C.16). Proposition 6. Under unigram coloring and the null hypothesis H0 , let √ √ √ Φ z/ r − Φ2 z/ r, z/ r′ , ρ ′ f (ρ, r, r ; z) := . √ Φ z/ r √ For all z > 0 with Φ(z/ r) > δℓ , it holds that P(Z ′ ≥ z | Z < z) − f (ρuni , r, r′ ; z)

≤ εBE (ℓ, ρuni ),

(C.23)

(C.24)

√ where εBE (ℓ, ρuni ) := (C2 µℓ + δℓ )/(Φ(z/ r) − δℓ ). √ e ≤ z/√r, Ze′ ≤ z/ r′ ), Proposition 5 yields P(Z ≤ z, Z ′ ≤ z) − Proof. Since P(Z ≤ z, Z ′ ≤ z) = P(Z √ √ √ Φ2 (z/ r, z/ r′ ; ρuni ) ≤ C2 µℓ . For the marginal denominator P(Z < z) = P(Ze < z/ r), the Berry–Esseen p P √ √ bound gives |P(Ze < z/ r) − Φ(z/ r)| ≤ δℓ with δℓ ≤ C1 τ E|wτ Uτ |3 ≤ C1 βℓ / γ(1 − γ), noting that E Uτ2 = 1 (see the proof of Proposition 5). Combining the √ joint and marginal bounds exactly as in the Kgw √ case (Proposition 4), but with the thresholds shifted to z/ r and z/ r′ , yields the promised inequality. √ quantity βℓ = maxτ mτ / Q can be seen as the largest “type leverage” into the type-mass Q = P The 2 τ mτ . If no single token type carries a non-vanishing fraction of the text as ℓ → ∞ (e.g., all multiplicities mτ are within a constant factor of the median), then βℓ = O(ℓ−1/2 ) and thus δℓ , µℓ = O(ℓ−1/2 ). It follows that εBE (ℓ, ρuni ) = O(ℓ−1/2 ). When there are no dominating token types, the following proposition establishes Theorem 4 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 ℓ.) Proposition 7. Under unigram coloring and the null hypothesis H0 , assume the non-degeneracy condition that no single token type carries a non-vanishing fraction of the text as ℓ → ∞. Then there exists a unique ρ⋆ = ρ⋆ (ε; z, γ, r, r′ ) ∈ (0, 1) solving f (ρ, r, r′ ; z) = ε/2, such that the type-mass budget Q′ ≥ ρ2⋆ Q =⇒ P Z ′ ≥ z Z < z ≤ ε (C.25) holds for all sufficiently large ℓ. Equivalently, under unigram coloring, it is safe to delete up to a (1 − ρ2⋆ )fraction of the pre-filter type-mass Q without exceeding conditional FPR ε. Proof. Given ε ∈ (0, 1), we can pick ρ⋆ ∈ (0, 1) such that f (ρ⋆ , r, r′ ; z) = ε/2, and choose ℓ large enough that 6 under the non-degeneracy condition. If Q′ ≥ ρ2⋆ Q, then ρuni = p εBE (ℓ, ρ⋆ ) ≤ ε/2 in Proposition ′ ′ Q /Q ≥ ρ⋆ . Since f (ρ, r, r ; z) is strictly decreasing in ρ ∈ (0, 1) for fixed (r, r′ , z), we have f (ρuni , r, r′ ; z) ≤ f (ρ⋆ , r, r′ ; z) = ε/2. Adding the Berry–Esseen remainder yields P(Z ′ ≥ z | Z < z) ≤ ε for all sufficiently large ℓ. 22

Table D.3: Focused comparison of Kgw and Kgw+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. Dataset

Method

TPR

FPR

Eligible WM

Avg. mask

Avg. scored WM

0.5

1.0

2.0

HumanEval

0.5

HumanEval

1.0

HumanEval

2.0

MBPP

0.5

MBPP

1.0

MBPP

2.0

Kgw Kgw+RCM Kgw Kgw+RCM Kgw Kgw+RCM Kgw Kgw+RCM Kgw Kgw+RCM Kgw Kgw+RCM Kgw Kgw+RCM Kgw Kgw+RCM Kgw Kgw+RCM

6.1 7.5 55.5 55.4 96.9 95.7 2.4 0.6 9.8 6.1 43.3 32.9 12.8 6.3 52.4 40.2 83.5 79.6

0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 1.6 0.0 1.6 0.0 1.6 0.0

99.3 99.3 99.5 99.3 99.6 99.7 100.0 95.7 100.0 96.3 100.0 94.5 93.5 93.0 95.2 92.1 93.3 92.3

0.0 4.5 0.0 5.2 0.0 6.7 0.0 51.9 0.0 51.8 0.0 47.7 0.0 21.9 0.0 20.7 0.0 17.7

181.60 171.16 182.94 172.83 185.23 171.88 199.12 94.96 194.29 92.57 196.09 99.67 142.90 110.21 149.47 104.98 148.21 108.78

Appendix D. Comparison with Repeated Context Masking Repeated context masking (RCM) is a non-distortion mechanism to avoid repeated watermark bias, implemented in watermarks like SynthID-Text (Dathathri et al., 2024). In this section, we treat Kgw+RCM as a variant of Kgw and compare it with plain Kgw. Note that RCM is not a pure detector-side method: during generation, it suppresses the Kgw bias 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 compare Kgw+RCM and Kgw on Opt-1.3b over C4, HumanEval, and Mbpp. 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 D.3 reports the main results. It turns out that RCM yields only a modest gain on C4 at the weakest setting (i.e., δ = 0.5, where TPR increases from 6.1% to 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 fixed Kgw z-threshold. More in-depth evaluation and analysis remain an intriguing future direction. References Aaronson, S., Kirchner, H., 2022. Watermarking GPT outputs. https://www.scottaaronson.com/talks/ watermark.ppt. Presentation slides. Amaldi, E., Kann, V., 1995. The complexity and approximability of finding maximum feasible subsystems of linear relations. Theoretical Computer Science 147, 181–210. doi:10.1016/0304-3975(94)00254-G. Austin, J., Odena, A., Nye, M., Bosma, M., Michalewski, H., Dohan, D., Jiang, E., Cai, C., Terry, M., Le, Q., et al., 2021. Program synthesis with large language models. arXiv preprint arXiv:2108.07732 doi:10.48550/arXiv.2108.07732. Bentkus, V., 2005. A lyapunov-type bound in Rd . Theory of Probability & Its Applications 49, 311–323. doi:10.1137/S0040585X97981123. Bifet, A., Gavaldà, R., 2007. Learning from time-changing data with adaptive windowing, in: SIAM International Conference on Data Mining, SIAM. pp. 443–448. doi:10.1137/1.9781611972771.42. 23

Chandra, B., Dunietz, J., Roberts, K., 2024. Reducing risks posed by synthetic content: An overview of technical approaches to digital content transparency. Technical Report NIST AI 100-4. National Institute of Standards and Technology. doi:10.6028/NIST.AI.100-4. Chen, M., Tworek, J., Jun, H., Yuan, Q., Ponde de Oliveira Pinto, H., Kaplan, J., Edwards, H., Burda, Y., Joseph, N., Brockman, G., et al., 2021. Evaluating large language models trained on code. arXiv preprint arXiv:2107.03374 doi:10.48550/arXiv.2107.03374. Christ, M., Gunn, S., Zamir, O., 2024. Undetectable watermarks for language models, in: Annual Conference on Learning Theory, PMLR. pp. 1125–1139. doi:10.48550/arXiv.2306.09194. Dathathri, S., See, A., Ghaisas, S., Huang, P.S., McAdam, R., Welbl, J., Bachani, V., Kaskasoli, A., Stanforth, R., Matejovicova, T., Hayes, J., Vyas, N., Al Merey, M., Brown-Cohen, J., Bunel, R., Balle, B., Cemgil, T., Ahmed, Z., Stacpoole, K., Shumailov, I., Baetu, C., Gowal, S., Hassabis, D., Kohli, P., 2024. Scalable watermarking for identifying large language model outputs. Nature 634, 818–823. doi:10.1038/s41586-024-08025-4. Fang, X., Wu, H., Jing, J., Meng, Y., Yu, B., Yu, H., Zhang, H., 2024. NSEP: Early fake news detection via news semantic environment perception. Information Processing & Management 61, 103594. doi:10. 1016/j.ipm.2023.103594. Fernandez, P., Chaffin, A., Tit, K., Chappelier, V., Furon, T., 2023a. Three bricks to consolidate watermarks for large language models, in: IEEE International Workshop on Information Forensics and Security, pp. 1–6. doi:10.1109/WIFS58808.2023.10374576. Fernandez, P., Couairon, G., Jégou, H., Douze, M., Furon, T., 2023b. The stable signature: Rooting watermarks in latent diffusion models, in: The IEEE/CVF International Conference on Computer Vision, pp. 22466–22477. doi:10.1109/ICCV51070.2023.02056. Firouzeh, F.F., Chinneck, J.W., Rajan, S., 2022. Faster maximum feasible subsystem solutions for dense constraint matrices. Computers & Operations Research 139, 105633. doi:10.1016/j.cor.2021.105633. Fu, J., Zhao, X., Yang, R., Zhang, Y., Chen, J., Xiao, Y., 2024. Gumbelsoft: Diversified language model watermarking via the Gumbelmax-trick. arXiv preprint arXiv:2402.12948 doi:10.48550/arXiv.2402. 12948. Gama, J., Žliobaitė, I., Bifet, A., Pechenizkiy, M., Bouchachia, A., 2014. A survey on concept drift adaptation. ACM Computing Surveys 46, 1–37. doi:10.1145/2523813. Gretton, A., Borgwardt, K.M., Rasch, M.J., Schölkopf, B., Smola, A., 2012. A kernel two-sample test. Journal of Machine Learning Research 13, 723–773. doi:10.5555/2188385.2188410. Gurobi Optimization, LLC, 2024. Gurobi Optimizer Reference Manual. URL: https://www.gurobi.com. He, Z., Zhou, B., Hao, H., Liu, A., Li, Y., Liu, J., Li, L., Wang, X., Tu, Z., Zhang, Z., Wang, R., 2024. Can watermarks survive translation? on the cross-lingual consistency of text watermark for large language models. arXiv preprint arXiv:2402.14007 doi:10.48550/arXiv.2402.14007. Hogg, R.V., Tanis, E., Zimmerman, D., 2015. Probability and Statistical Inference. 9th ed., Pearson. Husain, H., Wu, H.H., Gazit, T., Allamanis, M., Brockschmidt, M., 2019. CodeSearchNet challenge: Evaluating the state of semantic code search. arXiv preprint arXiv:1909.09436 doi:10.48550/arXiv.1909.09436. Kirchenbauer, J., Geiping, J., Wen, Y., Katz, J., Miers, I., Goldstein, T., 2024a. A watermark for large language models. arXiv preprint arXiv:2301.10226 doi:10.48550/arXiv.2301.10226.

Kirchenbauer, J., Geiping, J., Wen, Y., Shu, M., Saifullah, K., Kong, K., Fernando, K., Saha, A., Goldblum, M., Goldstein, T., 2024b. On the reliability of watermarks for large language models. arXiv preprint arXiv:2306.04634 doi:10.48550/arXiv.2306.04634. Kuditipudi, R., Thickstun, J., Hashimoto, T., Liang, P., 2024. Robust distortion-free watermarks for language models. Transactions on Machine Learning Research doi:10.48550/arXiv.2307.15593. Lee, T., Hong, S., Ahn, J., Hong, I., Lee, H., Yun, S., Shin, J., Kim, G., 2024. Who wrote this code? watermarking for code generation. arXiv preprint arXiv:2305.15060 doi:10.48550/arXiv.2305.15060. Li, X., Ruan, F., Wang, H., Long, Q., Su, W.J., 2025a. Robust detection of watermarks for large language models under human edits. Journal of the Royal Statistical Society: Series B (Statistical Methodology) doi:10.1093/jrsssb/qkaf056. Li, X., Ruan, F., Wang, H., Long, Q., Su, W.J., 2025b. A statistical framework of watermarks for large language models: Pivot, detection efficiency and optimal rules. The Annals of Statistics 53, 322–351. doi:10.1214/24-AOS2468. Liu, A., Pan, L., Hu, X., Meng, S., Wen, L., 2024a. A semantic invariant robust watermark for large language models, in: International Conference on Learning Representations. doi:10.48550/arXiv.2310.06356. Liu, A., Pan, L., Lu, Y., Li, J., Hu, X., Zhang, X., Wen, L., King, I., Xiong, H., Yu, P.S., 2024b. A survey of text watermarking in the era of large language models. ACM Computing Surveys doi:10.1145/3691626. Lu, J., Liu, A., Dong, F., Gu, F., Gama, J., Zhang, G., 2019. Learning under concept drift: A review. IEEE Transactions on Knowledge and Data Engineering 31, 2346–2363. doi:10.1109/TKDE.2018.2876857. Lu, Y., Pan, L., Han, J., Zou, L., Yu, P.S., Wen, L., Song, X., He, X., 2024. Entropy-based text watermarking detection. arXiv preprint arXiv:2404.17571 doi:10.48550/arXiv.2404.17571. Luvembe, A.M., Li, W., Li, S., Liu, F., Wu, X., 2024. Caf-ODNN: Complementary attention fusion with optimized deep neural network for multimodal fake news detection. Information Processing & Management 61, 103653. doi:10.1016/j.ipm.2023.103653. Pan, L., Liu, A., Han, J., Lu, Y., Yu, P.S., Wen, L., 2024a. Markllm: An open-source toolkit for LLM watermarking. arXiv preprint arXiv:2405.10051 doi:10.48550/arXiv.2405.10051. Pan, L., Liu, A., Lu, Y., Gao, Z., Di, Y., Wen, L., King, I., Yu, P.S., 2024b. Waterseeker: Pioneering efficient detection of watermarked segments in large documents. arXiv preprint arXiv:2409.05112 doi:10. 18653/v1/2025.findings-naacl.156. Peng, L., Jian, S., Kan, Z., Qiao, L., Li, D., 2024. Not all fake news is semantically similar: Contextual semantic representation learning for multimodal fake news detection. Information Processing & Management 61, 103564. doi:10.1016/j.ipm.2023.103564. Pfetsch, M.E., 2008. Branch-and-cut for the maximum feasible subsystem problem. SIAM Journal on Optimization 19, 21–38. doi:10.1137/050645828. Polikar, R., 2012. Ensemble learning, in: Ensemble machine learning. Springer, pp. 1–34. Rabanser, S., Günnemann, S., Lipton, Z.C., 2019. Failing loudly: An empirical study of methods for detecting dataset shift, in: Advances in Neural Information Processing Systems. Raffel, C., Shazeer, N., Roberts, A., Lee, K., Narang, S., Matena, M., Zhou, Y., Li, W., Liu, P.J., 2020. Exploring the limits of transfer learning with a unified text-to-text transformer. Journal of Machine Learning Research 21, 1–67. doi:10.5555/3455716.3455856. 25

Reynolds, S., Obitayo, S., Dalmasso, N., Ngo, D.D.T., Potluru, V.K., Veloso, M., 2025. Toward breaking watermarks in distortion-free large language models. arXiv preprint arXiv:2502.18608 doi:10.48550/ arXiv.2502.18608. Tsur, D., Long, C.X., Verdun, C.M., Vithana, S., Hsu, H., Chen, C.F., Permuter, H.H., Calmon, F.P., 2025. Heavywater and simplexwater: Distortion-free LLM watermarks for low-entropy distributions, in: Advances in Neural Information Processing Systems, Curran Associates, Inc. doi:10.48550/arXiv.2506. 06409. Wang, Z., Gu, T., Wu, B., Yang, Y., 2025a. MorphMark: Flexible adaptive watermarking for large language models, in: Annual Meeting of the Association for Computational Linguistics, Association for Computational Linguistics. pp. 4842–4860. doi:10.18653/v1/2025.acl-long.240. Wang, Z., Xu, G., Ren, M., 2025b. Can attention detect AI-generated text? A novel Benford’s law-based approach. Information Processing & Management 62, 104139. doi:10.1016/j.ipm.2025.104139. Wolsey, L.A., 1998. Integer Programming. Wiley-Interscience, New York. Wouters, B., 2023. Optimizing watermarks for large language models. arXiv preprint arXiv:2312.17295 doi:10.48550/arXiv.2312.17295. Wu, J., Yang, S., Zhan, R., Yuan, Y., Chao, L.S., Wong, D.F., 2025. A survey on LLM-generated text detection: Necessity, methods, and future directions. Computational Linguistics 51, 275–338. doi:10. 1162/coli_a_00549. Xiong, C., Zheng, G., Ma, X., Li, C., Zeng, J., 2025. Delphiagent: A trustworthy multi-agent verification framework for automated fact verification. Information Processing & Management 62, 104241. doi:10. 1016/j.ipm.2025.104241. Xylogiannopoulos, K.F., Xanthopoulos, P., Karampelas, P., Bakamitsos, G.A., 2024. ChatGPT paraphrased product reviews can confuse consumers and undermine their trust in genuine reviews. Can you tell the difference? Information Processing & Management 61, 103842. doi:10.1016/j.ipm.2024.103842. Zhang, Z., Zhang, X., Zhang, Y., Zhang, L.Y., Chen, C., Hu, S., Gill, A., Pan, S., 2024. Large language model watermark stealing with mixed integer programming. arXiv preprint arXiv:2405.19677 doi:10. 48550/arXiv.2405.19677. Zhao, X., Ananth, P.V., Li, L., Wang, Y.X., 2023. Provable robust watermarking for AI-generated text. arXiv preprint arXiv:2306.17439 doi:10.48550/arXiv.2306.17439.

Record · ID 287072 · SHA-256 e84212d73719e212
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.