A Unified Attack Framework against Statistical Generative Watermarks for Large Language Models

A Unified Attack Framework against Statistical Generative Watermarks for Large Language Models

arXiv:2610.27653v1 [cs.CR] 20 Oct 2026

Romina Omidi Illinois Institute of Technology romidi@hawk.illinoistech.edu

Nima Naderloui Illinois Institute of Technology nima.naderloui@uconn.edu

Yuan Hong University of Connecticut yuan.hong@uconn.edu

Binghui Wang Illinois Institute of Technology bwang70@illinoistech.edu

Abstract Watermarking has emerged as a key tool for identifying text generated by large language models (LLMs), with current schemes embedding statistical signals into the generation process to enable later detection. In this work, we identify a shared weakness across a broad class of popular LLM watermarking methods, including KGW (and its variants), GumbelSoft, DipMark, ITS, and SynthID1 . We show that these schemes exhibit a fundamental link between their detection scores and the token probability shifts they introduce during generation. This link, which we call score-ratio alignment, allows an attacker with only black-box query access to the model—and no knowledge of secret keys or model weights—to produce text that evades detection while remaining fluent and natural. We prove that the resulting attack is optimal across all covered watermark families, and show that the weakness is intrinsic: any watermark designed to maximize statistical detection power necessarily induces the very structure that attackers can exploit. We evaluate our attack on seven popular generative LLM watermarking schemes, three LLMs, and tasks, which reduce detection rates to at most 0.05 across all settings while preserving text quality. Our findings show that current watermarking methods can be reliably defeated under realistic attack conditions, highlighting the need for fundamentally different watermarking designs that decouple detection scores from token probability shifts.

1

Introduction

The widespread deployment of large language models (LLMs) capable of generating fluent, humanlike text at scale has created a pressing need for reliable provenance attribution [5, 30, 39, 3]. Generative watermarking has emerged as the most practical solution: a statistical signal is embedded into the LLM’s token generation process, enabling a verifier to classify text as machine-generated without access to the original prompt or model weights [1, 20, 6, 22, 7]. Deployed and proposed schemes—including KGW [20], GumbelSoft [10, 1], DipMark [41], ITS [22], and SynthID [7]— share a common architecture: a pseudorandom function (PRF) keyed by a secret key biases token selection at each decoding step, and a detector aggregates per-token scores into a test statistic compared against a calibrated threshold. 1 It is originally used as SynthID-Text; here we use SynthID for simplicity.

1

Despite significant advances in watermark design, a central security question remains unresolved: can an adversary with only black-box access to the watermarked LLM—and no knowledge of the PRF key or model weights—reliably evade detection while generating fluent, semantically coherent text? Prior attacks have addressed a weaker version of this question by applying post-hoc paraphrasing: a secondary model rewrites the watermarked output to disrupt the embedded signal [21, 31, 34]. Paraphrasing-based attacks impose a fundamental quality–evasion tradeoff—aggressive rewriting degrades fluency and semantic fidelity in proportion to the evasion gain [21]—and require inference through a capable auxiliary model. Crucially, reported robustness improvements against Paraphrasing does not characterise security against generation-time adversaries. Our approach. We identify a structural property shared by major watermarking schemes, which we term score-ratio alignment: the per-token watermark score is a monotone function of the probability ratio between the watermarked and base distributions. Formally, for each token j from a p̂ vocabulary V we have: arg min j∈V p jj ⊆ arg min j∈V E[s j ], where p̂ j is the watermarked token

probability, p j the base model probability, and E[s j ] the expected per-token detection score. We prove that the equation holds as a formal theorem—not merely as an empirical observation—for KGW (and its two variants), GumbelSoft, DipMark, ITS, and SynthID (see Theorems in §4). Score-ratio alignment admits a direct and efficient attack. An adversary who estimates the probability ratio p̂ j /p j from repeated black-box queries can greedily select the score-minimizing token at each decoding step, systematically suppressing the cumulative detection statistic. Because the selected tokens are drawn from the low-distortion region of the base model distribution, text quality is preserved. The attack requires neither the secret key nor model weights, relying only on sampling access to the watermarked model and an offline surrogate model. Key insight. Score-ratio alignment is not an artifact of any particular design; it is a structural consequence of optimization for detection power. By the Neyman–Pearson lemma [27], any statistically optimal detector must be based on the likelihood ratio p̂(x)/p(x)—exactly the quantity that score-ratio alignment ties to the watermark score. We prove (Theorem 5.1, §5) that no watermarking scheme within the current generator–detector paradigm can simultaneously achieve Neyman– Pearson-optimal detection power and robustness against a score-ratio-minimizing adversary. This result is not a limitation of specific parameter setting or scheme; it is an information-theoretic impossibility that holds for any scheme whose score function is optimized for distinguishability. Contributions. This paper makes below contributions. (1) Score-ratio alignment and a unified attack. We identify score-ratio alignment as a shared property of all major LLM watermarking schemes and formulate score-ratio minimization as a principled black-box attack requiring only output tokens from the watermarked model (§3). (2) Formal optimality. We prove that score-ratio minimization achieves the minimum attainable expected detection score for a wide range of LLM watermarking schemes: no black-box adversary can achieve a lower expected score within each scheme’s construction (§4). (3) Detectability–robustness tradeoff. We prove that optimizing the LLM watermark detection power establishes an inherent tension between detectability and robustness (§5). (4) Theoretical attack effectiveness. We theoretically characterize the effectiveness of our practical attack by showing its true positive rate admits a small upper bound (§6). (5) Empirical evaluation. We evaluate the attack on seven watermarking schemes, three LLMs, and three text corpora (C4, FakeNews, and Eli5 [33]). The attack reduces the true positive rate to at most 0.05 across all settings while preserving text quality (§7).

2

Table 1: Summary of the seven watermarking schemes covered by our framework. “Distortional” (D) schemes modify the sampling distribution; “distortion-free” (DF) schemes preserve it in expectation. γ denotes the green-list fraction, δ the logit boost, ξ t the pseudorandom vector, and γEM the Euler–Mascheroni constant. Scheme

Type

PRF output E

Decoder Γ

Token score ϕ(ξ t , xt )

Detection statistic Φ

KGW [20] Token-Specific KGW [17] Adaptive KGW [24] GumbelSoft [10] DipMark [41] ITS [22] SynthID [7]

D D D DF DF DF DF

{0, 1}|V | {0, 1}|V | (token-dep.) {0, 1}|V | (adaptive γt ) R|V | (Gumbel) Permutation ι t (µt , πt ) R|V | (proprietary)

softmax(lt + δξ t ; τ ) softmax((lt +δt ⊙ξ t ); τ ) softmax((lt +δt ξ t ); τ ) softmax((lt +ξ t ); τ ) Rank-reweighted (4) Inverse CDF (6) Tournament Sampling (11)

ξ t [ xt ] ∈ {0, 1} δt [ xt ] ξ t [ xt ] δt ξ t [ xt ] ξ t [ xt ] 1[ xt ∈ green region] |µt − η (πt ( xt ))| ξ t [ xt ]

Z-score (1) Normalized sum (2) Normalized sum (2) Scaled mean (3) Z-score (5) Negative mean (8) Mean (12) or Bayesian (16)

2

Background

We introduce the notation used throughout the paper, give a self-contained description of the generative LLM watermarking paradigm, and formally specify each of the seven watermarking schemes evaluated in §7. Table 1 summarises the schemes and their key components for reference.

2.1

Language Model Generation

An autoregressive language model generates a token sequence x = ( x1 , x2 , . . . , x T ) over a vocabulary V one token at a time. At decoding step t, the model maps the preceding context x1:t−1 to a logit vector lt ∈ R|V | , where lt [ x ] is the unnormalized score of token x ∈ V . The next-token distribution is exp(lt [ x ]/τ ) pt ( x | x1:t−1 ) = softmax(lt ; τ ) = , ∑ x′ ∈V exp(lt [ x ′ ]/τ ) where τ > 0 is the temperature. The next token is then sampled as xt ∼ pt (· | x1:t−1 ). We write pt ∈ ∆|V |−1 as the simplex of next-token probabilities at step t, and drop the conditioning notation and decoding step when the context is clear.

2.2

The Generative Watermarking Paradigm

Generative LLM watermarking [20, 6, 22] embeds a hidden statistical signal into text during token generation, making the signal imperceptible to human but reliably detectable by an algorithm. All schemes evaluated here instantiate the following two-component framework. Watermark generator. At each decoding step t, the generator receives the preceding context x1:t−1 and the model’s logit vector lt , and produces the next token xt via: (i) PRF evaluation. A pseudorandom function (PRF) Fsk keyed by a secret key sk is applied to a context window ct ⊆ x1:t−1 (e.g., the last h tokens) to produce a pseudorandom vector ξ t = Fsk (ct ) ∈ E , where the range E is scheme-specific. (ii) Watermarked sampling. A decoder Γ(ξ t , lt ) selects the next token xt using both lt and ξ t , inducing a watermarked distribution p̂t ∈ ∆|V |−1 that may or may not differ from the base distribution pt . Watermark detector. Given a candidate text x = ( x1 , . . . , x T ), the detector consists of below steps: (i) recomputes ξ t = Fsk (ct ) for each step t using the same secret key sk; 3

(ii) evaluates a token score function st = ϕ(ξ t , xt ) ∈ R that measures the per-token watermark evidence; and (iii) aggregates scores into a detection statistic Φ(s1:T ), which is compared against a pre-calibrated threshold θ to render a binary decision. The threshold θ is set to control the false positive rate (FPR) under the null hypothesis H0 that the text was sampled from the unwatermarked base model. The test statistic Φ(s1:T ) is designed to be large in expectation under H1 (watermarked text) and small under H0 , so that watermarked text is detected with high true positive rate (TPR) at a fixed FPR. Categorization. Watermarking schemes are broadly classified as distortional if p̂t ̸= pt with positive probability (so that the output distribution differs from the base model), and distortion-free if E[ p̂t ] = pt in expectation over the randomness of ξ t [6]. KGW and its variants, i.e., Adaptive KGW [24] and Token-Specific KGW [17] are distortional, while GumbelSoft, DipMark, ITS and SynthID are distortion-free.

2.3

LLM Watermarking Schemes

2.3.1

KGW

KGW [20] partitions the vocabulary into green and red tokens randomly, then applies a logit boost to all green tokens. • Context. The current token xt itself (self-hash variant; the partition is seeded by the token being generated rather than the preceding context, so the partition is fixed for each vocabulary token across all positions). • PRF. Fsk ( xt ) maps xt to a seed, which is used to sample a binary vector ξ t ∈ {0, 1}|V | with exactly γ|V | ones (the green list, Gt ) and (1 − γ)|V | zeros (the red list). Here γ ∈ (0, 1) is the green-list fraction. • Decoder. Γ(ξ t , lt ) samples from softmax( lt +τδ·ξ t ), where δ > 0 is the logit boost. • Token score. st = ϕ(ξ t , xt ) = ξ t [ xt ] ∈ {0, 1}, i.e., 1 if xt is green and 0 otherwise. • Detection statistic. KGW uses the Z-score defined below: ∑ T st − γT Φ(s1:T ) = pt=1 . Tγ(1 − γ)

(1)

d

Under H0 , Φ − → N (0, 1); under H1 , the elevated green-token rate shifts Φ positively. 2.3.2

KGW Variants

Several extensions of KGW replace its fixed green-list fraction and logit boost with context-dependent parameters. Two representative variants are Token-Specific KGW [17], which assigns different parameters to individual vocabulary tokens, and Adaptive KGW [24], which dynamically adjusts shared parameters at each decoding step. We can unify both schemes using the following generalized KGW formulation. • Context. The previous h tokens xt−h:t−1 , optionally together with semantic-coherence, complexity, or token-importance signals derived from current decoding context. • PRF and green-list construction. The pseudorandom function Fsk ( xt−h:t−1 ) seeds a contextdependent binary vector ξ t , where ξ t [ x ] ∼ Bernoulli(γt [ x ]) , ∀ x ∈ V , 4

and γt [ x ] ∈ (0, 1) is the probability that token x is assigned to the green list at step t and each token x has a boost δt [ x ]. 1. Token-Specific KGW: Both γt [ x ] and the boost δt [ x ] may vary across tokens according to semantic similarity or context-aware importance. I.e., γt [ x ] 2. Adaptive KGW: All tokens at a given step t typically share the same parameters, i.e., γt [ x ] = γt , δt [ x ] = δt , ∀ x ∈ V ; but γt and δt vary across decoding steps according to semantic coherence, sentence complexity, topic sensitivity, or token importance. Thus, Adaptive KGW is a step-dependent special case of the generalized token-dependent formulation. • Decoder. Let δt ≥ 0 denote the boost vector.   l +δ ⊙ξ For Token-Specific KGW, the watermarked token is sampled via xt ∼ softmax t τt t , where ⊙ is element-wise product.   For Adaptive KGW, this becomes xt ∼ softmax

lt +δt ·ξ t τ

.

• Token score. In Token-Specific KGW, the score contributed by the selected token is st = ϕ(ξ t , xt ) = δt [ xt ] ξ t [ xt ]; while under Adaptive KGW, the score becomes st = δt ξ t [ xt ]. • Detection statistic. Both variants aggregate the token-level scores using the normalized sum statistic as below h i ∑tT=1 st − E H0 ∑tT=1 st r Φ(s1:T ) = (2) h i , T Var H0 ∑t=1 st where the null-hypothesis mean and variance are computed using the corresponding tokenspecific or step-adaptive green-list parameters. A sufficiently large value of Φ(s1:T ) indicates the presence of the watermark. 2.3.3

GumbelSoft

GumbelSoft [10] injects Gumbel-distributed pseudorandom noise [12] into the logits before sampling. Because the Gumbel-Max trick is equivalent to sampling from the softmax distribution, the scheme is distortional-free. • Context. The previous h tokens xt−h:t−1 . i.i.d.

• PRF. Fsk ( xt−h:t−1 ) hashes the context to a seed and draws ξ t [ x ] ∼ Gumbel(0, 1), ∀ x ∈ V . • Decoder. xt ∼ softmax((lt + ξ t )/τ ). • Token score. st = ϕ(ξ t , xt ) = ξ t [ xt ], i.e., the Gumbel noise value at the sampled position. • Detection statistic. It uses scaled mean defined as: ! √ 6T 1 T Φ(s1:T ) = st − γEM , (3) π T t∑ =1 where γEM ≈ 0.5772 is the Euler–Mascheroni constant, i.e., the mean of a Gumbel(0, 1) random variable.

5

2.3.4

DipMark

DipMark [41] is a distortion-free scheme that reweights the token distribution via a pseudorandom permutation, assigning binary colour scores to tokens by their permuted rank. • Context. The previous h tokens xt−h:t−1 . • PRF. Fsk ( xt−h:t−1 ) seeds a uniform random permutation ι t : V → V . • Decoder. Token ι t [i ] is sampled with probability λt (i ) − λt (i − 1), where λt (i ) is defined as ( ) ( ) i

max

∑ pt (ιt [ j]) − α, 0

i

+ max

j =1

∑ pt (ιt [ j]) − (1 − α), 0

,

(4)

j =1

and α ∈ (0, 12 ) is a scheme parameter. Tokens ranked in the upper α-fraction of the permuted vocabulary (the “green” region) are upweighted, while tokens in the lower α-fraction (the “red” region) are downweighted. • Token score. st = ϕ(ξ t , xt ) = 1{ xt ∈ ι t [⌈(1 − γ)|V |⌉ : |V |]}, i.e., 1 if the sampled token falls in the green (high-rank) portion of the permuted vocabulary, 0 otherwise. • Detection statistic. It uses the Z-score defined as: Φ(s1:T ) = 2.3.5

∑tT=1 st − (1 − γ) T √ . T

(5)

ITS

The Inverse Transform Sampling (ITS) scheme [22] is distortion-free by construction: it uses a pre-committed global key sequence to deterministically select tokens via inverse CDF sampling, producing an output distribution equal in expectation to the base model. • Context. A global watermark key ξ-list and position index t. Each entry ξ-list[t] = (µt , πt ) consists of a random threshold µt ∈ Uni(0, 1) and a permutation πt of V . • PRF. The PRF simply reads off the pre-committed key: Fsk (t) = (µt , πt ). • Decoder. For a fixed key (µt , πt ), the decoder selects 

xt = πt−1 min πt (i ) : pt { j : πt ( j) ≤ πt (i )} ≥ µt , (6) which selects the smallest πt -ranked token whose cumulative probability under the permuted ordering meets or exceeds µt . This is equivalent to inverse-CDF sampling over the permuted token distribution. • Token score. st = ϕ(ξ t , xt ) = |µt − η (πt ( xt ))| , η (k ) =

k−1 , |V | − 1

(7)

which measures how closely the sampled token’s normalized rank matches the random threshold. Under H1 , scores are concentrated near zero; under H0 , they are approximately uniform on [0, 12 ]. • Detection statistic. It uses a negative mean: Φ(s1:T ) = −

1 T st . T t∑ =1

Note that larger negative values of Φ indicate stronger watermark evidence. 6

(8)

2.3.6

SynthID

SynthID [7] is the first production-ready generative LLM watermarking system developed by Google and achieves the state-of-the-art detection performance. Its core contribution is a novel Tournament Sampling mechanism that samples several candidate tokens from base distribution and repeatedly selects candidates having larger pseudorandom g-values. • Context. The previous h tokens xt−h:t−1 . • PRF and g-value function. The random seed at position t is computed from the preceding context and the secret watermark key rt = Fsk ( xt−h:t−1 ). For a tournament with m layers, the seed rt determines m independent pseudorandom functions (also called g-value functions):

ℓ ∈ {1, . . . , m},

gt,ℓ (i ) := gℓ (i, rt ),

i ∈ V.

(9)

Each function assigns every token an ordered g-value in a set Z . The standard construction uses binary values, but it naturally extends to arbitrary discrete ordered g-values. • Decoder: Tournament Sampling. Assume the tournament match contains N ≥ 2 competitors. The decoder initially samples N m candidate tokens independently from base distribution pt . At layer ℓ, the remaining candidates are divided into groups of N, and the candidate having the largest gt,ℓ -value in each group is retained. Ties are broken uniformly. After m layers, the only remaining token becomes xt . (ℓ) (0) Equivalently, let pt := pt and pt denote the winner distribution after layer ℓ. For a score level a ∈ Z , define the cumulative masses under the distribution p(ℓ−1) by Qt,ℓ,< ( a) :=

∑

(ℓ−1)

pt,j

, Qt,ℓ,≤ ( a), :=

j:gt,ℓ ( j)< a

∑

(ℓ−1)

pt,j

, Qt,ℓ,= ( a) := Qt,ℓ,≤ ( a) − Qt,ℓ,< ( a). (10)

j:gt,ℓ ( j)≤ a

The layerwise Tournament-sampling update is (ℓ)

(ℓ−1) Qt,ℓ,≤ ( gt,ℓ (i ))

pt,i = pt,i

N−Q

t,ℓ,< ( gt,ℓ (i ))

Qt,ℓ,= ( gt,ℓ (i ))

N

.

(11)

(m)

The final watermarked distribution is pbt := pt , xt ∼ pbt . • Detection statistics. SynthID supports both the mean score and Bayesian score, and larger values provide stronger watermark evidence. – Mean Score. The scalar contribution of token xt is sMS := m1 ∑m t ℓ=1 gt,ℓ ( xt ). Let I be the set of positions retained after context-repetition and other validity masking. The document-level mean statistic is ΦMS ( x1:T ) :=

m 1 g ( x t ). ∑ ∑ m|I| t∈I ℓ=1 t,ℓ

(12)

Detection is performed by comparing ΦMS with a threshold calibrated under the unwatermarked null distribution. – Bayesian Score. Let ψt,ℓ ∈ {1, . . . , N } denote the number of distinct competitors associated with the observed token at layer ℓ. For a fixed value ψt,ℓ = c, the likelihood ratio associated with observing g-value z is Λc (z) :=

Pr( gt,ℓ = z | H1 , ψt,ℓ = c) Pr( gt,ℓ = z | H0 ) 7

(13)

Given prior layer values gt,<ℓ = gt,1 ( xt ), . . . , gt,ℓ−1 ( xt ) , the conditional Bayes factor for layer ℓ is N
(14) BSt,ℓ gt,ℓ ( xt ); gt,<ℓ := ∑ Pr(ψt,ℓ = c | gt,<ℓ , H1 ) Λc ( gt,ℓ ( xt )) . c =1

The log-Bayesian contribution of token xt is m
sBS : = ∑ log BSt,ℓ gt,ℓ (xt ); gt,<ℓ . t

(15)

ℓ=1

The document-level log-Bayes statistic is therefore m
ΦBS ( x1:T ) := ∑ sBS t = ∑ ∑ log BSt,ℓ gt,ℓ ( xt ); gt,<ℓ . t∈I

3

(16)

t∈I ℓ=1

Attack Framework

We consider a watermark applied at generation time of an LLM by modifying its token selection distribution. The watermark is considered secure if it is simultaneously: (i) statistically detectable with high confidence, and (ii) minimally distortive with respect to the raw model distribution. Our attack challenges property (i) while preserving property (ii)2 .

3.1

Threat Model

Adversary capabilities: We assume a distribution-level black-box adversary with below capabilities: • Sampling and detector access: The adversary knows the watermark detection rule (e.g., score aggregation and threshold), since it knows which watermark to attack; the attacker and can query the watermarked LLM to observe generated text samples. • No seed or key access: The adversary has no access to the permutation, random seed, or secret partition used to construct the watermark. • No model access: The adversary does not modify the model weights or have access to the watermark algorithm. Adversary objective: The adversary objective is to produce an attacked distribution p̃ such that: 1. Watermark evasion: Generated text x sampled from p̃ is classified as non-watermarked by the detector with high probability. 2. Low distortion: The modified distribution p̃ remains close to the original model distribution p. In other words, the adversary aims to erase the watermark signal while preserving language quality.

3.2

Attack Principle

The central quantity we study is the expected per-token score E[s j ] as a function of the token index j. In §4 we show that for every watermarking scheme in Table 1, this function is monotone in the probability ratio p̂ j /p j , a property we call score-ratio alignment and forms the theoretical foundation of our attack. 2 For brevity, in the rest of the paper, we omit the decoding step index t and write s

token at decoding step t

8

j instead of st ( j ) to denote the j-th

Algorithm 1 Black-Box Attack on LLM Watermarking e candidate size K, query budget N, and Require: Prompt x, surrogate model Ms , watermarked oracle M, generation length T Ensure: Attacked continuation y 1: Initialize y ← [ ] 2: for j = 1, . . . , T do 3: Set the current context h ← ( x, y) 4: Query the watermarked oracle N times: e (· | h) et(1) , . . . , et( N ) ∼ M 5:

Select the top-K candidate tokens using the surrogate model:

C ← TopK( p Ms (· | h), K ) 6:

Estimate the watermarked probability for each t ∈ C : pbwm (t | h) ←

7:

∑iN=1 I[et(i) = t] + ϵ , ∑u∈C ∑iN=1 I[et(i) = u] + ϵ|C|

Select the next token:

∀t ∈ C

pbwm (t | h) t∈C p Ms ( t | h ) + ϵ

t⋆j ← arg min Append t⋆j to the continuation: y ← y ◦ t⋆j 9: if t⋆j = EOS then 10: break 11: end if 12: end for 13: return y 8:

Specifically, the attack exploits the fact that the schemes (both distortional and distortion-free) induce a structured change in token probabilities that correlates with the watermark score s j , i.e., tokens with the smallest expected scores experience the largest score-ratio degradation: p̂ j j∈V p j

j⋆ = arg min

⇒

j⋆ ∈ arg min E[s j ]. j∈V

(17)

The adversary leverages this alignment to estimate which tokens contribute most to the detection statistic and counteracts the watermark by applying a compensating reweighting or noise injection that neutralizes the expected score bias.

3.3

Attack Algorithm

Algorithm 1 presents our detailed attack procedure. Here, we choose an arbitrary surrogate model and use its tokenizer consistently throughout the attack. We make the following remarks regarding Algorithm 1. 1. Computational consideration. Unlike our theoretical analysis that considers the entire vocabulary V , in practice, we estimate the watermarked probabilities only for the top-K candidate tokens 9

in C selected by the surrogate model to reduce computational cost. Most tokens outside C have very small probabilities and are thus unlikely to be selected. This provides an efficiency– search-space tradeoff by substantially reducing the number of candidate tokens while retaining the most likely ones. 2. Per-token queries. Our attack operates at the token level. When querying the watermarked oracle, we set max new tokens=1 to obtain a single next-token sample. If generation-length control is unavailable and the oracle returns a sequence, we use only its first generated token as the next-token observation. 3. Numerical stability. We use a small constant ϵ > 0 in the denominator to avoid numerical instability. Since ϵ is sufficiently small, it has a negligible effect on the probability ratios and does not affect the attack results in practice.

4

Optimality: Score-Ratio Minimization

We now formally establish that the score-ratio minimization strategy in Equation (17) is optimal for the studied watermark schemes. Specifically, we prove that in every scheme, the token achieving the minimum probability ratio p̂ j /p j also achieves the minimum expected detection score E[s j ]—the score-ratio alignment condition of Equation (17). This alignment confirms that an adversary executing Algorithm 1 could minimize the detection statistic in expectation, without requiring knowledge of the secret key or the watermark seed. Next, we describe the setup and present the theorems. Since both KGW and GumbelSoft belong to the class of logit-addition watermarking schemes, the theorem applies directly to both methods. Furthermore, the two KGW variants can be analyzed under the same unified framework. All proofs are deferred to Appendix A.

4.1

Logit-Addition Watermark: KGW and GumbelSoft

Setup. Let l ∈ R|V | denote the original logit vector produced by the base LLM at a given decoding step, and define the base-model next-token distribution as p j = softmax(l ) j = addition watermark injects a per-token signal ξ j into the logits before sampling: lˆj = l j + δ ξ j ,

p̂ j = softmax(lˆ) j ,

s j := ξ j ,

l

ej . A logit∑k∈V elk

(18)

where δ > 0 is the watermark strength and ξ j is drawn from a distribution determined by the PRF and the current context. For KGW, ξ j ∼ Bernoulli(γ); for GumbelSoft, ξ j ∼ Gumbel(0, 1). In both cases the detector score for the sampled token is s j = ξ j . Theorem 1 (Score-Ratio Alignment: Logit-Addition). For any logit-addition watermark with δ > 0, we have: p̂ j ⊆ arg min E[s j ]. arg min j∈V j∈V p j Remark 1. Equation (31) shows that the probability ratio p̂ j /p j is a monotone function of ξ j alone: the original logit l j cancels exactly. Consequently, any token selection strategy that minimizes ξ j —equivalently, minimizes the detection score—also minimizes the probability ratio, and vice versa. This symmetry is the algebraic source of score-ratio alignment in all logit-addition schemes. 10

4.2

KGW Variants

Setup. In KGW variants [17, 24], each token j ∈ V receives an independent binary color ξ j ∼ Bernoulli(γ j ), and a boost magnitude δj ≥ 0. Watermarked logit and probability are

ℓ̂ j = ℓ j + δj ξ j ,

p̂ j = softmax(ℓ̂) j ,

sj = ξ j.

(19)

The probability ratio simplifies to ℓ e ℓ j + δj ξ j / ∑ j e ℓ j + δj ξ j p̂ j ∑j e j δj ξ j = = e · , ℓ +δ ξ pj eℓ j / ∑ j eℓ j ∑j e j j j

|

{z

=: C

(20)

}

where C is a constant, so arg mini p̂ j /p j = arg min j δj ξ j . Theorem 2 (Score-Ratio Alignment: KGW Variants). For every realization of the token-specific green list, we have: p̂ j arg min ⊆ arg min s j . j∈V p j j∈V Theorem 3 (Feasibility of Red-Token Minimizers: Token-Specific KGW). In the Token-Specific KGW watermark, every red token is a feasible minimizer of the probability ratio. In particular, if at least one token has ξ j = 0, then p̂ j arg min = { j : ξ j = 0} = arg min s j . j∈V p j j∈V If no red token exists, every token is a feasible minimizer.

4.3

DipMark

Setup. In DipMark, a step samples a uniformly random permutation ι : {0, 1, . . . , |V | − 1} → V , which induces a shuffled ordering of the vocabulary V . The binary watermark color (score) assigned to token ι[k ] is ( 0 (red) if k < ⌈γ|V |⌉, sι[k] = (21) 1 (green) otherwise, which means the first ⌈γ|V |⌉ tokens in the permuted order form the red prefix. We use p̂ j /p j as the degradation factor of token j. Theorem 4 (Score-Ratio Alignment: DipMark). In DipMark watermarking, the following inclusion holds: p̂ j arg min ⊆ arg min E[s j ]. j∈V p j j∈V Equivalently, every token achieving the smallest probability-ratio also achieves the smallest expected watermark score. Theorem 5 (Feasibility of Index 0: DipMark). In DipMark watermarking, ι[0] is always a feasible minimizer of s j in the index space induced by the permutation. In particular, p̂ j = ι[0] ∈ arg min E[s j ]. j∈V j∈V p j

arg min

11

4.4

ITS

Setup. Recall from §2.3.5 that the key at position t is ξ t = (µt , πt ), where µt ∼ Unif(0, 1) and πt is a random permutation of V . These keys are obtained from the pre-committed sequence ξ-list by applying a random document-level shift. The following result uses only the single-position marginal distribution of ξ t ; and independence between different positions is not required. Fix a decoding step t and its preceding context. Let pt be the corresponding base-model distribution, define St := { j ∈ V : pt ( j) > 0}, and let xt = Γ( pt , ξ t ) denote the token generated by the ITS decoder in Equation (6). For a permutation πt , token j occupies the permuted-CDF interval πt It,j :=

h

∑

p t ( i ),

i:πt (i )<πt ( j)

∑



pt (i ) .

(22)

i:πt (i )≤πt ( j)

πt Consequently, xt = j ⇐⇒ µt ∈ It,j .

Theorem 6 (ITS detection-statistic reduction). If |St | ≥ 2, Eξ t [−s( xt⋆ )] < Eξ t [−s( xt )] .

(23)

Thus, empirical probability-ratio minimization reduces the expected detection statistic to its key-independent null baseline. Remark 2. The strict inequality follows from the independence of the attacked token and the detector key. |V |−1 In fact, every token selection rule based only on auxiliary keys has the same expected null score 62(|V |−1) (see more details in Appendix A.6). Empirical probability-ratio minimization determines which underrepresented token is selected, while key independence is what reduces the expected ITS detection statistic.

4.5

SynthID

Setup. Consider SynthID Tournament sampling with N ≥ 2 competitors per match and m ≥ 1 tournament layers. Fix a decoding step, its preceding context, and the corresponding pseudorandom seed r. Let p(0) := p be the base-model next-token distribution and let S := {i ∈ V : pi > 0} denote its support. We restrict all probability ratios to S , since pbi /pi is undefined when pi = 0. At layer ℓ ∈ {1, . . . , m}, token i is assigned the possibly real-valued watermark score gℓ,i := gℓ (i, r ). Let p(ℓ) denote the winner distribution after layer ℓ. The final watermarked distribution is therefore pb := p(m) . Theorem 7 (Score-Ratio Alignment: SynthID, Mean Score). Consider Tournament sampling with arbitrary N ≥ 2 and arbitrary discrete, ordered g-values. For every layer ℓ and every i, j ∈ S , gℓ,i < gℓ,j =⇒ (ℓ)

(ℓ)

p̂i /pi

(ℓ)

(ℓ)

< p̂ j /p j . Consequently, (ℓ)

arg min i ∈S

p̂i

(ℓ)

pi

= arg min gℓ,i . i ∈S

(24)

Theorem 8 (Score-Ratio Alignment: SynthID, Bayesian Score). At any layer ℓ and condition on pre(ℓ)

ceding g-values, arg mini∈S

pbi

(ℓ) pi

= arg mini∈S gℓ,i ⊆ arg mini∈S s(i ).

Remark 3. For fixed preceding g-values, the layerwise probability ratio, the mean-score contribution gℓ,i , and the conditional Bayes factor are nondecreasing in gℓ,i . Thus, minimum-ratio selection minimizes both the mean and Bayesian evidence contributed by that layer. 12

5

Detectability–Robustness Tradeoff

§4 establishes that score-ratio alignment holds across all watermarks considered in this work. A natural question arises: Is this alignment an artifact of particular design choices, or reflecting a deeper structural constraint inherent to the generator–detector paradigm? In this section, we show that scoreratio alignment is the inevitable consequence of designing a statistically optimal detector. This yields a fundamental impossibility: no watermarking scheme within the current paradigm can simultaneously maximize detection power and resist score-ratio minimization adversaries. Proofs of the theorems are in Appendix B.

5.1

The Fundamental Tradeoff

We first formalize the notion of a watermark that can be evaded by our attack framework. Definition 1 (Defeatable Watermark). A watermarking scheme with per-token score function s j is called defeatable if the token minimizing the probability ratio coincides with the token minimizing the expected p̂ detection score: arg mini∈V p jj = arg min j∈V E[s j ]. Theorem 9 (Defeatable Implies Not Robust). If a watermarking scheme is defeatable, then it is not robust against a score-ratio-minimizing adversary. Theorem 10 (Detectability–Robustness Tradeoff). Among all hypothesis tests D for H0 : x ∼ p versus p̂( x ) H1 : x ∼ p̂, the statistically optimal detector is the likelihood-ratio test: Λ( x ) = p(x) . Detectability is p̂( x )

maximized when the detection score is aligned with the log-likelihood ratio: s( x ) ∝ log p(x) . However, p̂

if the score ordering coincides with the likelihood-ratio ordering, i.e., arg min j p jj = arg min j s j , then an adversary selecting tokens to minimize p̂ j /p j simultaneously minimizes the detection score s j , driving TPR to baseline. Hence, maximizing statistical detectability necessarily introduces the score-ratio alignment that adversaries can exploit.

5.2

Implications for Watermark Design

Theorem 10 establishes that the detectability-robustness tradeoff is not merely an engineering challenge that can be addressed, but rather an information-theoretic impossibility inherent to the current paradigm. This fundamental limitation has several practical implications. Robustness claims must specify the threat model. Prior works reporting robustness improvements (e.g., against paraphrasing or bounded token editing [22, 44]) do so against threat models that do not include score-ratio-minimizing adversaries. Our results show that schemes robust against post-hoc attacks remain defeatable under generation-time evasion. Any robustness claim must therefore explicitly state the adversary’s access model and attack phase. Improving detectability worsens robustness. Schemes that increase the logit boost δ or green-list fraction γ to improve detection power simultaneously sharpen the probability-ratio gap between green and red tokens, making the score-ratio ordering more informative to the adversary. Adaptive and token-specific variants that locally maximize δt or γt are therefore more exploitable at each step, not less.

13

Breaking score-ratio alignment requires paradigm change. Theorem 10 implies that robustness against our attack requires breaking the alignment between the detection score ordering and the likelihood-ratio ordering. Two directions are promising: (i) secret score randomization, in which the score assigned to each token is perturbed by a secret-key-dependent offset unknown to the adversary, decoupling the observable probability ratio from the true detection contribution; and (ii) multi-key ensemble watermarking, in which detection aggregates scores across multiple independent watermark keys, so that minimizing any single key’s score ordering does not minimize the ensemble statistic. We leave the formal analysis of these directions to future work.

6

Theoretical Effectiveness of the Attack

We establish that score-ratio minimization reduces the watermark statistic relative to the unwatermarked null distribution. We first prove an expectation-level guarantee in §6.1 that exact minimum-ratio selection reduces the expected detector statistic. We then strengthen this conclusion to first-order stochastic dominance, which yields a TPR bound at every detection threshold in §6.2. We finally extend this exact result to our practical finite-sample attack (Algorithm 1) in §6.3. All proofs are deferred to Appendix C.

6.1

Expected-Score Reduction

At decoding step t, let h denote the current prefix; and h1:t−1 be the context until step t − 1. Define St (h1:t−1 ) := {i ∈ V : pt (i | h1:t−1 ) > 0} as the support of the base next-token distribution. Let st (i | h1:t−1 , ξ t ) denote the oriented detection score of token i under key realization ξ t . We first make the following standard fresh-key assumption. Assumption 1 (Fresh-key null invariance). For every admissible prefix h, let ξ t be a fresh pseudorandom key and let Yt ∼ pt (· | h) independently of ξ t . The null score Zt0 = ϕ(ξ t , h, Yt ) has a distribution that does not depend on h. Further, the key values are independent across distinct contexts. Theorem 11 (Effectiveness of minimum-ratio selection). If the score-ratio alignment holds pointwise at every step t, i.e., p̂t (i | h1:t−1 ) ⊆ arg min st (i | h1:t−1 , ξ t ). i ∈V pt (i | h1:t−1 ) i ∈V

arg min

p̂ (i | h

(25)

)

Let the exact minimum-ratio adversary select xtA ∈ arg mini∈V ptt (i|h1:t−1 ) . Then, conditional on the attacked 1:t−1 prefix and the current key,   st ( xtA ) ≤ E st ( xt0 ) | h1:t−1 , ξ t , (26) where xt0 ∼ pt (· | h1:t−1 ) is a counterfactual unwatermarked token sampled under the same prefix. T A Consequently, for any nonnegative weights w1 , . . . , wT , the additive attacked score sA T = ∑ t =1 w t s t ( x t ) satisfies 0 E[ sA (27) T ] ≤ E[ s T ], under the fresh-key null-invariance assumption 1. Remark 4. The inequality is strict whenever, with positive probability, the base distribution assigns nonzero mass to a token whose score is strictly larger than the minimum. Therefore, except for the degenerate case in which the base model is supported entirely on score-minimizing tokens, the attack strictly reduces the expected watermark score. 14

6.2

Stochastic Dominance and TPR Reduction

We now strengthen the expectation-level result of Theorem 11 to a distributional guarantee. Throughout this section, token scores are oriented so that larger values indicate stronger watermark evidence. Thus, for a scheme whose original score has the opposite orientation, we negate the score. For example, the oriented ITS score is Zt = −st . Let DT = Φ T ( Z1 , . . . , ZT ) denote the detector statistic, where Φ T is coordinatewise nondecreasing. This includes sums, means, and positively standardized sums. For two real-valued random variables U and V, we write U ⪯st V if U is first-order stochastically dominated by V, i.e., Pr(U ≥ u) ≤ Pr(V ≥ u), ∀u ∈ R. At decoding step t, let h ∈ V t−1 be the current prefix, let pt (· | h) and p̂t (· | h) be the base and p̂ (i |h) watermarked next-token distributions, and define Rt (i | h) := ptt (i|h) for every i in the support of pt (· | h). Theorem 12 (Stochastic dominance under score-ratio minimization). Suppose that score-ratio alignment holds pointwise: for every step t, prefix h, and key realization ξ t , arg

min

i:pt (i | h)>0

Rt (i | h) ⊆ arg

min

i:pt (i | h)>0

ϕ(ξ t , h, i ).

(28)

Let the adversary select xtA ∈ arg mini:pt (i|h1:t−1 )>0 Rt (i | h1:t−1 ) at every step t. Then DTA ⪯st DT0 , where DT0 denotes the detector statistic under the unwatermarked null distribution. Further, if τε is calibrated so that Pr0 ( DT0 ≥ τε ) ≤ ε, then the true positive rate on attacked watermarked text satisfies TPRA (ε) := Pr( DTA ≥ τε ) ≤ ε. (29) A

Remark 5 (Expectation minimization is insufficient). The conclusion of Theorem 12 cannot be obtained only from E[ DTA ] ≤ E[ DT0 ]. Ordering the means generally does not order the upper-tail probabilities. The pointwise alignment condition is essential: it produces an almost-sure coupling, which implies stochastic dominance and therefore orders the TPR at every threshold.

6.3

Practical Top-K and Finite-Sample Attack

Algorithm 1 operates on a top-K candidate set and estimates the watermarked probabilities using finitely many queries. Let Ct be the retained candidate set and define its excluded base-model mass as ρt := 1 − ∑i∈Ct pt (i | h1:t−1 ). Let ζ t upper-bound the conditional probability that finitesample estimation, or filtering causes the algorithm to select a token that is not a score-minimizer within Ct . Theorem 13 (Approximate TPR guarantee). If ρt and ζ t are valid conditional upper bounds at every decoding step t, then ( ) T

TPRA (ε) ≤ min 1, ε + ∑ (ρt + ζ t )

.

(30)

t =1

Remark 6. Theorem 13 explicitly isolates the two sources of approximation in Algorithm 1: candidate truncation captured by ρt , and ratio-estimation or filtering error, captured by ζ t . When both quantities are small, the practical attack approaches the exact stochastic-dominance guarantee. 15

7

Experimental Evaluation

Our evaluations mainly address the below research questions: • RQ1. Does the score-ratio minimization attack reduce watermark detection to baseline levels? • RQ2. Does the attack preserve text quality relative to unwatermarked generation? • RQ3. Are results consistent across model scales? • RQ4. How does the hyperparameters affect our attack?

7.1

Experimental Setup

Watermarking schemes. We evaluate seven watermarking methods spanning both distortional and distortion-free families shown in Table 13 . Base and surrogate LLMs. We use OPT-1.3B [43] as the target base model on which the watermarking schemes are applied. As the surrogate model used in our attack (see Algorithm 1), we three LLMs spanning a range of scales: • OPT-1.3B [43]: a 1.3-billion-parameter model used to evaluate our attack to a small model and as as reference. • LLaMA-7B [38]: a 7-billion-parameter decoder-only transformer used as the primary evaluation model. • LLaMA-13B [39]: a 13-billion-parameter variant used to assess scale sensitivity. Datasets. Text generation is conditioned on prompts drawn from three corpora: • C4 [33]: a large-scale general web text corpus used as the primary benchmark, consistent with prior watermarking evaluations [20, 17]. • FakeNews: a collection of news-style long-form narratives, used to evaluate performance on factual, structured prose. • Eli-5 [8]: a community QA corpus, used to assess performance on open-ended, explanatory generation. Attack configuration. We evaluate our attack against 100 watermarked texts under the considered threat model in §3. By default, we use N = 256 queries per generation step, K = 40 in top-K candidate set, and generation length T = 256. We also study the impact of these hyperparameters. Evaluation metrics. We report the following metrics: • TPR @ FPR=1%: the fraction of adversarially generated texts correctly classified as watermarked by the detector at a fixed false positive rate of 1%. Lower TPR indicates more effective watermark evasion. • p-value: the detector’s hypothesis test applied to adversarially generated text. Values above 0.05 indicate failure to reject the null hypothesis (non-watermarked), confirming evasion. • Z-score: the normalized detection statistic. Negative or near-zero Z-scores indicate that the watermark signal has been suppressed to below the detection threshold. • Perplexity (PPL): text fluency measured by GPT-2 [32]. We report PPL to verify that evasion does not degrade output quality. Lower perplexity indicates more fluent and natural text. 3 SynthID requires intensive offline training on a private dataset to learn its Bayesian detector. Since this detector is

unavailable in our threat model, we evaluate our attack against SynthID using its mean-score detector.

16

Table 2: Attack results on three datasets using OPT-1.3B (base model) as the surrogate model. TPR is reported at a 1% false positive rate. Larger p-values and lower TPRs indicate stronger evasion. A p-value above 0.05 indicates unsuccessful watermark detection. PPL denotes the perplexity of adversarially generated text; lower values correspond to more fluent outputs. C4

FakeNews

Eli-5

Scheme

TPR↓ p-value↑ Z-score↓ PPL↓ TPR↓ p-value↑ Z-score↓ PPL↓ TPR↓ p-value↑ Z-score↓ PPL↓

KGW Token-Specific KGW Adaptive KGW GumbelSoft DipMark ITS SynthID

0.01 0.01 0.03 0.02 0.01 0.02 0.01

0.98 0.97 0.24 0.49 0.74 0.27 0.93

-4.61 -4.18 0.73 -0.06 -0.63 0.69 -2.41

14.72 5.91 3.86 4.51 5.04 5.21 5.78

0.01 0.01 0.02 0.01 0.02 0.01 0.01

0.98 0.97 0.34 0.63 0.66 0.21 0.98

-4.23 -3.47 0.29 -0.36 -0.41 0.81 -3.61

15.71 6.35 4.54 4.92 5.27 4.96 4.24

0.02 0.01 0.03 0.01 0.01 0.03 0.01

0.98 0.96 0.31 0.61 0.64 0.43 0.98

-4.39 -2.13 0.46 -0.38 -0.24 0.12 -2.87

15.16 6.48 4.13 4.94 5.61 3.91 5.19

Table 3: Attack results on three datasets using LLaMA-7B as the surrogate model. C4

FakeNews

Eli-5

Scheme

TPR↓ p-value↑ Z-score↓ PPL↓ TPR↓ p-value↑ Z-score↓ PPL↓ TPR↓ p-value↑ Z-score↓ PPL↓

KGW Token-Specific KGW Adaptive KGW GumbelSoft DipMark ITS SynthID

0.00 0.00 0.01 0.00 0.00 0.00 0.00

1.00 1.00 0.07 0.46 0.68 0.32 0.99

-4.94 -5.37 1.47 0.10 -0.48 0.48 -3.56

13.18 6.23 3.19 4.39 4.95 5.66 5.49

0.00 0.00 0.00 0.00 0.00 0.00 0.00

0.99 0.99 0.058 0.65 0.59 0.16 0.99

-4.67 -3.96 1.57 -0.40 -0.25 0.99 -3.38

13.99 6.23 4.42 4.98 5.15 4.81 4.16

0.03 0.00 0.01 0.00 0.00 0.02 0.00

0.99 0.98 0.28 0.66 0.61 0.25 0.97

-4.67 -2.27 0.58 -0.42 -0.29 0.65 -1.94

13.86 6.56 4.06 4.89 5.27 3.28 5.12

Table 4: Attack results on three datasets using LLaMA-13B as the surrogate model. C4

FakeNews

Eli-5

Scheme

TPR↓ p-value↑ Z-score↓ PPL↓ TPR↓ p-value↑ Z-score↓ PPL↓ TPR↓ p-value↑ Z-score↓ PPL↓

KGW Token-Specific KGW Adaptive KGW GumbelSoft DipMark ITS SynthID

0.00 0.00 0.02 0.01 0.00 0.00 0.00

7.2

0.99 0.99 0.28 0.43 0.80 0.19 0.87

-4.34 -3.89 0.57 0.17 -0.86 0.86 -1.17

15.94 5.63 4.23 4.62 5.12 4.83 6.12

0.00 0.00 0.00 0.00 0.00 0.00 0.00

0.99 0.99 0.56 0.69 0.62 0.16 0.99

-3.98 -3.14 -0.17 -0.50 -0.31 0.98 -3.84

16.43 6.47 4.65 4.86 5.36 5.11 4.32

0.00 0.00 0.02 0.00 0.00 0.01 0.00

0.99 0.97 0.28 0.66 0.57 0.77 0.99

-4.12 -1.98 0.58 -0.42 -0.18 -0.76 -3.94

16.37 6.56 4.06 4.89 5.93 4.13 5.12

Results

Table 2–Table 4 report TPR@FPR=1%, p-value, Z-score, and PPL. We summarize the following key findings. Finding 1: Near-universal watermark evasion. Across all seven watermarking schemes and all model–dataset combinations, the score-ratio minimization attack achieves a TPR of 0.00–0.05, reducing detection to or below the false positive rate baseline. This confirms RQ1: the attack generalizes across diverse scheme designs, including both distortional (KGW, Token-Specific, Adaptive) and distortion-free (GumbelSoft, DipMark, ITS, SynthID) families. The result is consistent with the score-ratio alignment theorems of §4: since alignment holds for every scheme, the attack is provably optimal in each case, and the empirical TPR results follow from the theory.

17

5

6.5

4

5.090

5.060

1

4.950

5.0

4.800

0

0.150

4.5

-0.250 4.200

-0.440

-0.480

-0.365

4.0

128

192

256

2 5.113

5.150

5.083

1

4.914

5.0 0.786 4.500

0.156

4.5

0 -0.063

-0.250

3

-0.097

−1

5.5 5.193 1.553

4.0

320

128

192

256

1

0.785

0

0.364

4.5

-0.290

-0.230

−1

4.144

4.0

−2

64

2

5.270

4.870

5.0

−1

−2

64

5.5

Perplexity (PPL)

2

Watermark Z-score

5.5

4

6.0 3

Perplexity (PPL)

Perplexity (PPL)

6.113

6.0

Watermark Z-score

6.0 3

5

6.5

4

320

Watermark Z-score

5

6.5

−2

64

128

192

Number of queries, N

Number of queries, N

Number of queries, N

(a) C4

(b) Fake-News

(c) Eli-5

256

320

Figure 1: Perplexity (left axis) and watermark Z-score (right axis) as a function of #queries N. 5

6.5

4

5.120

1

4.950

5.0

0

0.390

5.5

-0.480

5.460

2

5.150

5.0

1

4.920

0 4.5

4.370

5.370

1.490

Perplexity (PPL)

2

5.756

Watermark Z-score

5.340

6.0 3

Perplexity (PPL)

Perplexity (PPL)

5.5

4.5

4

6.0

Watermark Z-score

6.0 3

5

6.5

4

2

5.270 5.134

1

5.0

0 4.5

-0.250

−1

3

5.571

5.5

-0.020

-0.290

−1

-0.560

-0.704

Watermark Z-score

5

6.5

−1

-1.020

4.0

−2 -1.950

128

256

512

4.0

-1.800

−2

4.0

−2

-2.150

1024

128

256

512

1024

128

256

512

Generation length, T (tokens)

Generation length, T (tokens)

Generation length, T (tokens)

(a) C4

(b) Fake-News

(c) Eli-5

1024

Figure 2: Effect of generated text length T (tokens) on attack effectiveness and text quality. Finding 2: Text quality is preserved. Perplexity remains low and competitive with unwatermarked generation across all conditions (e.g., PPL < 7 in all cases except on KGW). This confirms RQ2: the attack is genuinely non-distortionary in practice, not only in theory. The preservation of fluency validates that the score-ratio minimization strategy selects tokens that are both lowscoring and semantically coherent, consistent with the distributional proximity argument of §3. Finding 3: Results are consistent across model scales. Comparing results on LLaMA-7B and LLaMA-13B, we observe no meaningful difference in attack effectiveness since TPR is very small (most are 0.00) for both model scales across all schemes. This confirms RQ3 and suggests that vulnerability is not a function of model capacity but of the structural alignment property. Finding 4: Statistically significant evasion. The p-values for all schemes substantially exceed the standard 0.05 significance threshold, confirming that the detector cannot reject the null hypothesis (non-watermarked) for adversarially generated text. Z-scores are negative or near-zero in almost all cases, indicating that the cumulative detection statistic has been driven below the detection threshold. These results are consistent with Theorem 9: minimizing S = ∑t sit∗ at each step drives E[S] below the threshold τ, causing the TPR to collapse.

7.3

Ablation Study

In this section, we investigate the impact of key parameters on attack performance (RQ4): query budget N, generated text length T, and K in Top-K candidate tokens. For brevity, we report results using the medium LLaMA-7B model on DipMark. 18

5

6.5

4

2.060 4.950

5.0

1

0

0.330

4.5

-0.480 -0.280

2 5.150

1

1.250

5.0

4.810

4.640

4.5

4.370 4.200

5.5

0

0.120

4.410

5.5

5.0

−2

−1

10

20

30

40

4.0

−2

10

20

30

40

0.124

0 -0.146

-0.290

−1

4.185

4.0

3.921

10

2

1

4.840 0.394

3.980

4.0

5.270

4.5

-0.250

−1

3

Perplexity (PPL)

2

3

Perplexity (PPL)

Perplexity (PPL)

5.5

4 6.0

3.800

Watermark Z-score

6.0

Watermark Z-score

6.0 3

5

6.5

4

Watermark Z-score

5

6.5

−2

20

30

Top-K candidate set, K

Top-K candidate set, K

Top-K candidate set, K

(a) C4

(b) Fake-News

(c) Eli-5

40

Figure 3: Effect of K in Top-K candidate set on attack effectiveness and text quality. Impact of N. Figure 1 studies the effect of the query budget N on attack effectiveness and text quality. Across all datasets, increasing N consistently decreases the watermark Z-score, indicating stronger watermark evasion. For example, on C4, the Z-score decreases from 0.15 to −0.48 as N increases, while the perplexity increases only slightly, from 4.20 to 5.09, suggesting that the attack preserves text quality well even with a larger query budget. Impact of T. Figure 2 shows the impact of the generated text length T. As T increases, the watermark Z-score becomes increasingly negative, indicating stronger watermark evasion. This trend is expected, as longer generations provide more evidence for the attack to identify and suppress the watermark signal. Meanwhile, perplexity increases marginally with T, suggesting a modest trade-off in text quality as the attack operates over longer generations. Impact of K. Figure 3 shows the results with varying K candidate tokens in Algorithm 1. We observe that increasing K decreases the watermark Z-score, indicating stronger attack performance; and the perplexity increases since there is a trade-off between detectability and quality.

8

Related Work

8.1

AI-Generated Text Detection

8.1.1

Non-watermark based Detection

A large body of work develops detectors that do not require a watermark signal to be embedded at generation time. Statistical zero-shot detectors. Mitchell et al. [26] propose DetectGPT, which exploits the observation that AI-generated text tends to lie in regions of the probability surface with negative curvature; detection is performed by checking whether small random perturbations of a candidate text consistently reduces its log-probability under the model. Su et al. [36] extend the work by using the log rank of sampled tokens—rather than log-probability curvature—as a detection signal, improving efficiency and accuracy. Bao et al. [4] introduce Fast-DetectGPT, which replaces perturbation-based curvature estimate with a conditional probability curvature measure, achieving accuracy comparable to DetectGPT but with less costs. Hans et al. [14] propose Binoculars, a zero-shot detector that compares the perplexity of a text under two closely related models, without requiring access to the original generator. 19

Learning-based detectors. Guo et al. [13] train supervised classifiers to distinguish GPT-generated text from human text, finding that finetuned detectors can achieve high accuracy on in-distribution data but degrade under distribution shift. He et al. [15] introduce MGTBench, a benchmark for evaluating machine-generated text detectors across diverse generation models, domains, and adversarial conditions. Ghosal et al. [11] provide a survey of possibilities and impossibilities of AI-generated text detection, including both theoretical limits and practical evaluations. 8.1.2

Watermark based Detection

Distortional watermarking. Distortional schemes [20, 17, 24, 9, 16] explicitly modify the token distribution, accepting a measurable divergence from the base model in exchange for a stronger detection signal. The foundational work [20] introduces the KGW green/red list watermark, which pseudorandomly partitions the vocabulary into green- and red-listed tokens at each decoding step and applies a fixed logit boost to all green tokens; detection is performed via a Z-score on the fraction of green tokens observed in a candidate text. Huo et al. [17] introduce token-specific watermarking, which assigns context-dependent boost magnitudes δi to individual tokens, improving fluency while preserving detectability. Liu and Bu [24] propose an adaptive watermark that dynamically adjusts both the green-list fraction and the boost magnitude based on real-time semantic coherence signals, reducing perceptual artifacts in sensitive decoding contexts. While these refinements improve the detectability-quality tradeoff, we show in §4 that all KGW-style schemes share a structural vulnerability: their detection score functions are aligned with the token probability-ratio ordering, making them susceptible to our unified attack framework. Distortion-free watermarking. Distortion-free schemes [6, 10, 1, 22, 41, 23, 44, 37] aim to preserve the original output distribution in expectation for all tokens, while still embedding a detectable signal [6]. GumbelSoft [10] achieves distortion-free watermarking by injecting Gumbeldistributed pseudorandom noise into logits before softmax sampling; the detector recovers the Gumbel noise component at the sampled token and aggregates these values into a Z-score. Kuditipudi et al. [22] propose a distortion-free scheme ITS with formal robustness guarantees against bounded text editing, though their analysis does not address adaptive adversaries that exploit score structure. Wu et al. [41] introduce DiPMark, which reweights the token distribution via a random permutation, assigning binary colour scores to tokens according to their permuted rank. SynthID [7] is the first production-ready generative LLM watermarking system, designed to be efficient, non-invasive, and detectable at scale. Its core contribution is a novel Tournament Sampling mechanism for next-token generation, which achieves state-of-the-art watermark detectability.

8.2

Attacks on AI-Generated Text Detectors

Post-hoc attacks. Most existing attacks operate after text generation by modifying the generated content to disrupt the detector. The most widely studied approach is paraphrasing, where an auxiliary model rewrites the generated text while attempting to preserve its semantic meaning [21]. Other post-hoc attacks include token-level editing [31], detector red-teaming using adversarially finetuned language models [35], watermark-evasion generation strategies [18, 25], and universal adversarial triggers that manipulate model outputs through specially crafted prompts [40]. Beyond empirical attacks, Sadasivan et al. [34] establish information-theoretic limitations of watermark detection under sufficiently powerful paraphrasing adversaries. Although these approaches

20

can substantially reduce detection rates, they typically exhibit an inherent quality–evasion tradeoff: weakening the watermark often requires modifying the generated text, which may introduce semantic drift, stylistic changes, or additional computational overhead. Generation-time evasion. These works consider attacks that intervene at generation time rather than after the fact. Zhao et al. [44] study an adversary that selects among multiple watermarked continuations, but assume access to the detector score during generation. Zhang et al. [42] show that no scheme can simultaneously guarantee detectability and security against a computationally bounded forger with access to the generator. Abdelnabi and Fritz [2] study adversarial attacks on text watermarks in an earlier generation of transformer-based systems, providing an empirical baseline for generation-time adversaries. Jovanovic et al. [19] propose a watermark stealing attack against KGW [20], where an attacker queries the watermarked model to approximately reverseengineer its secret watermarking rules and then exploits the learned watermark to facilitate watermark removal. Omidi et al. [28, 29] propose the first layer inflation attack against SynthID, which exploits its tournament-based sampling mechanism by externally adding additional tournament layers through black-box queries. Our attack is the first to formulate generation-time evasion as a principled optimization problem, establish its optimality across multiple watermark families, and empirically achieve near-zero true positive rates without sacrificing text quality. Importantly, it requires only black-box sampling access, making the attack practical for API-level adversaries.

8.3

Detectability–Robustness Tradeoffs

The tension between watermark detectability and adversarial robustness has been recognized informally in prior work but not formally characterized for the LLM setting. Christ et al. [6] show that distortion-free watermarks are necessary for computational undetectability, implying a tradeoff between quality preservation and statistical detectability. Zhang et al. [42] prove that no watermark can be simultaneously unremovable and undetectable under a computationally bounded model, establishing a cryptographic impossibility analogous to our information-theoretic result. Takezawa et al. [37] characterize necessary and sufficient conditions on score functions for a watermark to achieve detectability and a form of robustness. Our work proves that maximizing detection power under the Neyman–Pearson lemma [27] necessarily aligns the score function with the likelihood-ratio ordering—the exact structure our adversary exploits. This result is stronger than prior informal observations: it establishes that the tradeoff is not merely empirical but information-theoretically fundamental within the current generator–detector paradigm, and that no in-paradigm fix can simultaneously achieve optimal detectability and resistance to score-ratio-minimizing adversaries.

9

Conclusion

We develop a unified attack framework on watermarked LLMs based on score-ratio alignment, a structural property shared by most generative watermarks. By selecting score-minimizing tokens at each decoding step, our attack achieves a near-zero true positive rate with minimal degradation in text quality. We show that statistically optimal watermark detectors inherently align their detection scores with score-ratio ordering, making such watermarks fundamentally vulnerable to our attack. Our results reveal an inherent limitation of statistical generative watermarks and establish score-ratio minimization as an important benchmark for evaluating watermark robustness. 21

References [1] Scott Aaronson. My AI safety lecture for UT effective altruism. Blog post, Shtetl-Optimized, 2022. [2] Sahar Abdelnabi and Mario Fritz. Adversarial watermarking transformer: Towards tracing text provenance with data hiding. In IEEE Symposium on Security and Privacy (SP), 2021. [3] Jinze Bai, Shuai Bai, Yunfei Chu, Zeyu Cui, Kai Dang, Xiaodong Deng, Yang Fan, Wenbin Ge, Yu Han, Fei Huang, et al. Qwen technical report. arXiv preprint arXiv:2309.16609, 2023. [4] Guangsheng Bao, Yanbin Zhao, Zhiyang Teng, Linyi Yang, and Yue Zhang. Fast-DetectGPT: Efficient zero-shot detection of machine-generated text via conditional probability curvature. In The Twelfth International Conference on Learning Representations, 2024. [5] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D. Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. In Advances in Neural Information Processing Systems, 2020. [6] Miranda Christ, Sam Gunn, and Or Zamir. Undetectable watermarks for language models. In Conference on Learning Theory, 2024. [7] Sumanth Dathathri, Abigail See, Sumedh Ghaisas, Po-Sen Huang, Rob McAdam, Johannes Welbl, Vandana Bachani, Alex Kaskasoli, Robert Stanforth, Tatiana Matejovicova, et al. Scalable watermarking for identifying large language model outputs. Nature, 2024. [8] Angela Fan, Yacine Jernite, Ethan Perez, David Grangier, Jason Weston, and Michael Auli. Eli5: Long form question answering. In Annual Meeting of the Association for Computational Linguistics (ACL), 2019. [9] Pierre Fernandez, Antoine Chaffin, Karim Tit, Vivien Chappelier, and Teddy Furon. Three bricks to consolidate watermarks for large language models. In 2023 IEEE Security and Privacy Workshops (SPW), 2023. [10] Jiayi Fu, Xuandong Zhao, Ruihan Yang, Yuansen Zhang, Jiangjie Chen, and Yanghua Xiao. GumbelSoft: Diversified language model watermarking via the Gumbel-Max trick. In Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), 2024. [11] Soumya Suvra Ghosal, Souradip Chakraborty, Jonas Geiping, Furong Huang, Dinesh Manocha, and Amrit Singh Bedi. Towards possibilities & impossibilities of AI-generated text detection: A survey. Transactions on Machine Learning Research, 2023. URL: https: //arxiv.org/abs/2310.15264. [12] Emil Julius Gumbel. Statistics of Extremes. Columbia University Press, New York, 1958. [13] Biyang Guo, Xin Zhang, Ziyuan Wang, Minqi Jiang, Jinran Nie, Yuxuan Ding, Jianwei Yue, and Yupeng Wu. How close is ChatGPT to human experts? Comparison corpus, evaluation, and detection, 2023. arXiv:2301.07597.

22

[14] Abhimanyu Hans, Avi Schwarzschild, Valeriia Cherepanova, Hamid Kazemi, Aniruddha Saha, Micah Goldblum, Jonas Geiping, and Tom Goldstein. Spotting LLMs with binoculars: Zero-shot detection of machine-generated text. In Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 17519–17537. PMLR, 2024. [15] Xinlei He, Xinyue Shen, Zeyuan Chen, Michael Backes, and Yang Zhang. MGTBench: Benchmarking machine-generated text detection. In Proceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security, CCS ’24, pages 2251–2265. ACM, 2024. [16] Zhengmian Hu, Lichang Chen, Xidong Wu, Yihan Wu, Hongyang Zhang, and Heng Huang. Unbiased watermark for large language models. In The Twelfth International Conference on Learning Representations, 2024. [17] Mingjia Huo, Sai Ashish Somayajula, Youwei Liang, Ruisi Zhang, Farinaz Koushanfar, and Pengtao Xie. Token-specific watermarking with enhanced detectability and semantic coherence for large language models. In International Conference on Machine Learning, 2024. [18] Zhengyuan Jiang, Jinghuai Zhang, and Neil Zhenqiang Gong. Evading watermark based detection of AI-generated content. In ACM SIGSAC Conference on Computer and Communications Security, 2023. [19] Nikola Jovanović, Robin Staab, and Martin Vechev. Watermark stealing in large language models. In International Conference on Machine Learning, 2024. [20] John Kirchenbauer, Jonas Geiping, Yuxin Wen, Jonathan Katz, Ian Miers, and Tom Goldstein. A watermark for large language models. In International Conference on Machine Learning, 2023. [21] Kalpesh Krishna, Yixiao Song, Marzena Karpinska, John Wieting, and Mohit Iyyer. Paraphrasing evades detectors of AI-generated text, but retrieval is an effective defense. In Advances in Neural Information Processing Systems, 2023. [22] Rohith Kuditipudi, John Thickstun, Tatsunori Hashimoto, and Percy Liang. Robust distortion-free watermarks for language models. Transactions on Machine Learning Research, 2024. [23] Aiwei Liu, Leyi Pan, Xuming Hu, Shiao Meng, and Lijie Wen. A semantic invariant robust watermark for large language models. In The Twelfth International Conference on Learning Representations, 2024. [24] Yepeng Liu and Yuheng Bu. Adaptive text watermark for large language models. In International Conference on Machine Learning, 2024. [25] Wenlong Meng, Shuguo Fan, Chengkun Wei, Min Chen, Yuwei Li, Yuanchao Zhang, Zhikun Zhang, and Wenzhi Chen. {GradEscape}: A {Gradient-Based} evader against {AIGenerated} text detectors. In USENIX Security Symposium, 2025. [26] Eric Mitchell, Yoonho Lee, Alexander Khazatsky, Christopher D. Manning, and Chelsea Finn. DetectGPT: Zero-shot machine-generated text detection using probability curvature. In International Conference on Machine Learning, 2023. 23

[27] Jerzy Neyman and Egon S. Pearson. On the problem of the most efficient tests of statistical hypotheses. Philosophical Transactions of the Royal Society of London. Series A, 231:289–337, 1933. [28] Romina Omidi, Yun Dong, and Binghui Wang. Google’s llm watermarking system is intrinsically vulnerable to layer inflation attack. In ICLR 2026 Workshop on Principled Design for Trustworthy AI, 2026. [29] Romina Omidi, Yun Dong, and Binghui Wang. On google’s synthid-text llm watermarking system: Theoretical analysis and empirical validation. arXiv preprint arXiv:2603.03410, 2026. [30] OpenAI. GPT-4 technical report, 2024. arXiv:2303.08774. [31] Julien Piet, Chawin Sitawarin, Vivian Fang, Norman Mu, and David A. Wagner. MARKmyWORDS: Analyzing and evaluating language model watermarks. In 2025 IEEE Conference on Secure and Trustworthy Machine Learning (SaTML), pages 68–91, 2025. [32] Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. Language models are unsupervised multitask learners. Technical report, OpenAI, 2019. URL: https://cdn.openai.com/better-language-models/language_models_are_ unsupervised_multitask_learners.pdf. [33] Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. Journal of Machine Learning Research, 21(140):1–67, 2020. [34] Vinu Sankar Sadasivan, Aounon Kumar, Sriram Balasubramanian, Wenxiao Wang, and Soheil Feizi. Can AI-generated text be reliably detected? arXiv preprint arXiv:2303.11156, 2023. [35] Zhouxing Shi, Yihan Wang, Fan Yin, Xiangning Chen, Kai-Wei Chang, and Cho-Jui Hsieh. Red teaming language model detectors with language models. Transactions of the Association for Computational Linguistics, 12:174–189, 2024. [36] Jinyan Su, Terry Zhuo, Di Wang, and Preslav Nakov. DetectLLM: Leveraging log rank information for zero-shot detection of machine-generated text. In Findings of the Association for Computational Linguistics: EMNLP 2023, pages 12395–12412. Association for Computational Linguistics, 2023. [37] Yuki Takezawa, Ryoma Sato, Han Bao, Kenta Niwa, and Makoto Yamada. Necessary and sufficient watermark for large language models. Transactions on Machine Learning Research, 2023. [38] Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, Aurelien Rodriguez, Armand Joulin, Edouard Grave, and Guillaume Lample. LLaMA: Open and efficient foundation language models. arXiv preprint arXiv:2302.13971, 2023. [39] Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, et al. Llama 2: Open foundation and fine-tuned chat models, 2023.

24

[40] Eric Wallace, Shi Feng, Nikhil Kandpal, Matt Gardner, and Sameer Singh. Universal adversarial triggers for attacking and analyzing NLP. In Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLPIJCNLP), 2019. [41] Yihan Wu, Zhengmian Hu, Junfeng Guo, Hongyang Zhang, and Heng Huang. A resilient and accessible distribution-preserving watermark for large language models. In Proceedings of the 41st International Conference on Machine Learning, 2024. [42] Hanlin Zhang, Benjamin L. Edelman, Danilo Francati, Daniele Venturi, Giuseppe Ateniese, and Boaz Barak. Watermarks in the sand: Impossibility of strong watermarking for language models. In Proceedings of the 41st International Conference on Machine Learning, Proceedings of Machine Learning Research, 2024. [43] Susan Zhang, Stephen Roller, Naman Goyal, Mikel Artetxe, Moya Chen, Shuohui Chen, Christopher Dewan, Mona T. Diab, Xian Li, Xi Victoria Lin, Todor Mihaylov, Myle Ott, Sam Shleifer, Kurt Shuster, Daniel Simig, Punit Singh Koura, Anjali Sridhar, Tianlu Wang, and Luke Zettlemoyer. OPT: Open pre-trained transformer language models. arXiv preprint arXiv:2205.01068, 2022. [44] Xuandong Zhao, Prabhanjan Ananth, Lei Li, and Yu-Xiang Wang. Provable robust watermarking for AI-generated text. In The Twelfth International Conference on Learning Representations, 2024.

25

A

Proof of Optimality

A.1

Proof of Theorem 1

Compute the probability ratio directly: ˆ ˆ p̂ j e l j / ∑ k e lk el j +δξ j ∑ k e lk = eδξ j · C, = l · = lk +δξ k lj l j k pj e ∑ e / ∑k e e k

where C :=

∑ k e lk ∑k elk +δξ k

(31)

p̂

is a normalizing constant that does not depend on j. Hence, arg min j∈V p jj = arg min j∈V eδξ j . Since δ > 0 and x 7→ eδx is strictly increasing, arg min eδξ j = arg min ξ j = arg min E[s j ], j∈V

j∈V

j∈V

where the final equality holds because s j = ξ j and the expectation is taken over the PRF randomness conditioned on the context. This establishes the stated inclusion.

A.2

Proof of Theorem 2

We split into two cases based on whether any red token exists. First of all, we know that based on the design of KGW variant watermarks, we have δj > 0 . Case 1: At least one red token exists. Suppose ξ j = 0 for some j ∈ V . For any red token, eδj ·0 = 1; for any green token, eδj ·1 = eδj > 1 since δj > 0. Therefore, the probability ratio is minimized exactly by the red tokens: p̂ j arg min = { j : ξ j = 0} = arg min s j . j∈V p j j∈V Case 2: All tokens are green. If ξ j = 1 for all j ∈ V , then s j = 1 for all i, so arg min j s j = V . Moreover, p̂

every token satisfies eδj ξ j = eδj , giving p jj = eδj · C, which is not necessarily equal across tokens (since δj may vary). Nevertheless, the minimizer of p̂ j /p j belongs to V = arg min j s j , so the inclusion holds.

A.3

Proof of Theorem 3

If at least one red token exists, then for every red token i, s j = ξ j = 0 is the minimum achievable score, and eδj ·0 = 1 < eδj = eδj ·1 for any δj > 0, confirming that red tokens attain the smallest probability ratio. If no red token exists, all tokens have identical score s j = 1 and the minimizer condition holds vacuously over V .

A.4

Proof of Theorem 4

We consider two exhaustive cases. Case 1: All tokens are green. If sι[k] = 1 for all k, then E[s j ] = 1 for all j ∈ V , so arg min j E[s j ] = V . Any minimizer of p̂ j /p j therefore belongs to V , and the inclusion holds trivially. 26

Case 2: At least one token is red. Since the red prefix is non-empty, min j s j = 0 and min j E[s j ] = 0. By the DipMark construction, the token ι[0]—the first in the shuffled order—has the highest probability (over the random permutation) of landing in the red prefix, and therefore attains the smallest expected score: ι[0] ∈ arg min E[s j ]. j∈V

In DipMark’s reweighting procedure, probability mass is redistributed from tokens at the start of the permuted list toward those at the end: the earliest tokens are the first to have their probabilities reduced (and potentially zero), while later tokens remain invariant or receive increased mass. Consequently, the maximum degradation p̂ j /p j is achieved by the token appearing earliest in the permuted order: p̂ j ι[0]∈ arg min . j∈V p j Combining both inclusions: p̂ j ∈ arg min E[s j ], j∈V p j j∈V

ι[0]∈ arg min which proves the theorem in Case 2.

A.5

Proof of Theorem 5

We consider two exhaustive cases. Case 1: All tokens are green. If sι[k] = 1 for all k, then E[s j ] = 1 for all j ∈ V , so arg min j E[s j ] = V . Any minimizer of p̂ j /p j therefore belongs to V , and the inclusion holds trivially. Case 2: At least one token is red. Since the red prefix is non-empty, min j s j = 0 and min j E[s j ] = 0. By the DipMark construction, the token ι[0]—the first in the shuffled order—has the highest probability (over the random permutation) of landing in the red prefix, and therefore attains the smallest expected score: ι[0] ∈ arg min j∈V E[s j ]. In DipMark’s reweighting procedure, probability mass is redistributed from tokens at the start of the permuted list toward those at the end: the earliest tokens are the first to have their probabilities reduced (and potentially zero), while later tokens remain invariant or receive increased mass. Consequently, the maximum degradation p̂ j /p j is achieved by the token appearing earliest in the permuted order: p̂ j ι[0]∈ arg min . j∈V p j Combining both inclusions: p̂ j ∈ arg min E[s j ], j∈V p j j∈V

ι[0]∈ arg min which proves the theorem in Case 2.

27

A.6

Proof of Theorem 6 (1)

(K ) i.i.d.

Let ξ t , . . . , ξ t

∼ L(ξ t ) be auxiliary keys independent of the detector key ξ t . Define pbt,K ( j) :=

o 1 K n (k) 1 Γ ( p , ξ ) = j , t t K k∑ =1

(32)

Rt,K ( j) :=

pbt,K ( j) , pt ( j)

j ∈ ∫j.

(33)

xt⋆ ∈ arg min Rt,K ( j).

(34)

The attack selects j∈∫ j

For any candidate token j, write s( j) := |µt − η (πt ( j))| ,

η (r ) =

r−1 . |V | − 1

(35)

Thus the detector contribution of token j is −s( j). Theorem 14 (ITS detection-statistic reduction). Let v := |V |. Suppose that xt⋆ is selected according to Equation (34) using auxiliary keys independent of the detector key ξ t . Then Eξ t [s( xt⋆ )] = cv ,

cv :=

2v − 1 . 6( v − 1)

(36)

The legitimate ITS token xt = Γ( pt , ξ t ) satisfies Eξ t [s( xt )] ≤ cv ,

(37)

with strict inequality whenever |∫ j | ≥ 2. Consequently, Eξ t [−s( xt⋆ )] < Eξ t [−s( xt )] .

(38)

Thus empirical probability-ratio minimization reduces the expected ITS detection statistic to its key-independent null baseline. (1)

(K )

Proof. Because xt⋆ is a measurable function only of the auxiliary keys ξ t , . . . , ξ t , it is independent of the detector key ξ t = (µt , πt ). Condition on xt⋆ = j. Since πt is a uniformly random permutation, πt ( j) is uniform on {1, . . . , v} and is independent of µt . Therefore, 1 Eξ t [s( xt⋆ ) | xt⋆ = j] =

v

Z 1

v r∑ =1 0

|u − η (r )| du

1 v η (r )2 + 1 − η (r ) = ∑ v r =1 2

2 .

(39)

For η (r ) = (r − 1)/(v − 1), 1 v 1 η (r ) = , v r∑ 2 =1

(40)

1 v 2v − 1 η (r )2 = . ∑ v r =1 6( v − 1)

(41)

28

Substituting these identities into Equation (39) gives Eξ t [s( xt⋆ ) | xt⋆ = j] =

2v − 1 = cv . 6( v − 1)

This value does not depend on j. Hence the law of total expectation proves Equation (36). We next analyze the legitimate ITS token. Define its permuted rank and normalized rank by R t : = π t ( x t ),

Zt := η ( Rt ).

For each r ∈ {1, . . . , v}, define the cumulative mass of the first r tokens in the permuted ordering: πt Ct,r :=

∑

p t ( j ).

(42)

πt µt ≤ Ct,r .

(43)

j:πt ( j)≤r

By the inverse-CDF decoder, Rt ≤ r

⇐⇒

We first establish the marginal distribution of Rt . Conditioned on πt , the probability that the output has rank r equals the probability mass of the token occupying that rank. Thus, h
i Pr( Rt = r ) = Eπt pt πt−1 (r )

=

1 1 pt ( j) = . v j∑ v ∈V

(44)

Therefore, Rt is uniform on {1, . . . , v} and Zt is uniform on   1 ,...,1 . 0, v−1 Although Zt has the same marginal distribution as the rank of a key-independent token, it is positively dependent on µt . Indeed, every token belongs to the first r positions of a uniform permutation with probability r/v. Consequently,  πt 
Eπt Ct,r = ∑ pt ( j) Pr πt ( j) ≤ r j∈V

=

r r pt ( j) = . ∑ v j∈V v

(45)

For every u ∈ [0, 1], Equation (43) gives 
 πt Pr(µt ≤ u, Rt ≤ r ) = Eπt Pr µt ≤ min{u, Ct,r } | πt  πt  = Eπt min{u, Ct,r }  πt  ≥ u Eπt Ct,r r =u . v The inequality uses min{u, c} ≥ uc, 29

u, c ∈ [0, 1].

(46)

Since Pr(µt ≤ u) = u and Pr( Rt ≤ r ) = r/v, Equation (46) proves that µt and Rt , and hence µt and Zt , are positively quadrant dependent. et be independent of µt and have the same marginal distribution as Zt . Positive quadrant Let Z dependence implies et > u ) Pr(µt > u, Zt > u) ≥ Pr(µt > u) Pr( Z (47) for every u ∈ [0, 1]. Using the layer-cake representation, E [min{µt , Zt }] =

≥

Z 1 0

Pr(µt > u, Zt > u) du

Z 1

et > u) du Pr(µt > u) Pr( Z h i et } . = E min{µt , Z 0

(48)

et have mean 1/2. Therefore, using | a − b| = a + b − 2 min{ a, b}, Both Zt and Z E [|µt − Zt |] = 1 − 2E [min{µt , Zt }] h i et } ≤ 1 − 2E min{µt , Z h i et | = c v . = E |µt − Z

(49)

Because s( Xt ) = |µt − Zt |, this proves Equation (37). It remains to establish strictness. If |∫ j | ≥ 2, every token in ∫ j has probability strictly between zero and one. Hence   πt Pr 0 < Ct,1 < 1 > 0. πt

For every u ∈ (0, 1) and every c ∈ (0, 1), min{u, c} > uc. Thus Equation (46) is strict for r = 1 and u ∈ (0, 1). In particular, for 0<u<

1 , v−1

the event Zt ≤ u is equivalent to Rt = 1, and Equation (47) is strict on an interval of positive measure. It follows that h i e E [min{µt , Zt }] > E min{µt , Zt } , and therefore Eξ t [s( Xt )] < cv = Eξ t [s( xt⋆ )] . Multiplying by −1 gives Eξ t [−s( xt⋆ )] < Eξ t [−s( Xt )] , which proves Equation (38).

30

A.7

Proof of Theorem 7

Fix a tournament layer ℓ and let p(ℓ−1) be its incoming token distribution. For an ordered score value a, define Q ℓ,< ( a ) : =

∑

(ℓ−1)

pk

,

Q ℓ,≤ ( a ) : =

∑

(ℓ−1)

k:gℓ,k ≤ a

k:gℓ,k < a

pk

,

Q ℓ,= ( a ) : = Q ℓ,≤ ( a ) − Q ℓ,< ( a ) .

(50)

For every supported token i, we have Qℓ,= ( gℓ,i ) > 0. Consider a match containing N independent candidates drawn from p(ℓ−1) . The probability that the largest g-value among these candidates is exactly a is Q ℓ,≤ ( a ) N − Q ℓ,< ( a ) N . Conditioned on the largest value being a, uniform tie-breaking and exchangeability imply that the winning token is distributed proportionally to p(ℓ−1) among the tokens whose g-value equals a. Consequently, N N (ℓ) (ℓ−1) Qℓ,≤ ( gℓ,i ) − Qℓ,< ( gℓ,i ) . (51) pi = pi Qℓ,= ( gℓ,i ) Therefore, the layerwise probability ratio is (ℓ)

Rℓ,i :=

=

pi

(52)

(ℓ−1)

pi

Qℓ,≤ ( gℓ,i ) N − Qℓ,< ( gℓ,i ) N Qℓ,≤ ( gℓ,i ) − Qℓ,< ( gℓ,i )

(53)

N −1

= ∑ Qℓ,≤ ( gℓ,i ) N −1−r Qℓ,< ( gℓ,i )r ,

(54)

r =0

where the last equality follows from N −1 aN − bN = ∑ a N −1−r b r . a−b r =0

Now consider i, j ∈ S satisfying gℓ,i < gℓ,j . Because both score levels have positive incoming probability mass, Qℓ,< ( gℓ,i ) < Qℓ,≤ ( gℓ,i ) ≤ Qℓ,< ( gℓ,j ) < Qℓ,≤ ( gℓ,j ). (55) Every term in Equation (54) is nondecreasing in both cumulative masses. Moreover, because N ≥ 2, Qℓ,≤ ( gℓ,i ) N −1 < Qℓ,≤ ( gℓ,j ) N −1 . Thus at least the r = 0 term is strictly larger for token j, while none of the other terms is smaller. It follows that gℓ,i < gℓ,j =⇒ Rℓ,i < Rℓ,j . Hence Rℓ,i is strictly increasing in the ordered g-value. All tokens attaining the smallest gvalue attain the smallest probability ratio, and every token with a larger g-value has a strictly larger ratio. Therefore, arg min Rℓ,i = arg min gℓ,i . i ∈S

i ∈S

Since gℓ,i is the contribution of token i to the mean detector at layer ℓ, minimum-ratio selection also minimizes that layer’s mean-score contribution. 31

A.8

Proof of Theorem 8

We first prove that the conditional Bayesian factor is nondecreasing in the current g-value. Let Fg− (z) := Pr( G < z) = Fg (z) − f g (z). Conditioned on ψℓ = c, the winning g-value is the maximum of c i.i.d. null g-values. Therefore, Pr( G(c) = z) = Fg (z)c − Fg− (z)c . Consequently, Λc (z) =

Fg (z)c − Fg− (z)c Fg (z) − Fg− (z)

c −1

= ∑ Fg (z)c−1−k Fg− (z)k ,

(56)

k =0

where the second equality follows from c −1 ac − bc = ∑ a c −1− k b k . a−b k =0

If z1 < z2 , then Fg (z1 ) ≤ Fg (z2 ), Fg− (z1 ) ≤ Fg− (z2 ). Every term in Equation (56) is nondecreasing in both arguments. Hence z1 < z2

=⇒

Λ c ( z1 ) ≤ Λ c ( z2 ).

Because qc (u) ≥ 0 and ∑c qc (u) = 1, it follows that N

N

c =1

c =1

BSℓ (z1 ; u) = ∑ qc (u)Λc (z1 ) ≤ ∑ qc (u)Λc (z2 ) = BSℓ (z2 ; u). Thus BSℓ (z; u) is nondecreasing in z. For completeness, when the g-value distribution is continuous, Pr( G(c) ∈ dz) = cFg (z)c−1 f g (z) dz, and therefore

Λc (z) = cFg (z)c−1 ,

which is again nondecreasing in z. We next consider the Tournament-sampling probability ratio. For a score level z, define Q ℓ,< ( z ) : =

∑ pj

(ℓ−1)

∑ pj

(ℓ−1)

Q ℓ,≤ ( z ) : =

,

,

j:gℓ,j ≤z

j:gℓ,j <z

and Q ℓ,= ( z ) : = Q ℓ,≤ ( z ) − Q ℓ,< ( z ) . The Tournament-sampling update gives Rℓ,i =

Qℓ,≤ ( gℓ,i ) N − Qℓ,< ( gℓ,i ) N . Qℓ,= ( gℓ,i )

Using the difference-of-powers identity, N −1

Rℓ,i = ∑ Qℓ,≤ ( gℓ,i ) N −1−k Qℓ,< ( gℓ,i )k . k =0

32

(57)

Both Qℓ,≤ (z) and Qℓ,< (z) are nondecreasing in z. Since every coefficient in Equation (57) is nonnegative, gℓ,i < gℓ,j =⇒ Rℓ,i ≤ Rℓ,j . For distinct supported score levels and N ≥ 2, the inequality is strict. Therefore, arg min Rℓ,i = arg min gℓ,j . i

j

We have shown that both the layerwise probability multiplier and the conditional Bayesian factor are minimized at the smallest current-layer g-value. Hence, arg min Rℓ,i = arg min gℓ,i ⊆ arg min BSℓ ( gℓ,i ; u). i

i

i

Finally, if qc (u) > 0 for at least one c ≥ 2, then Λc (z), and consequently BSℓ (z; u), is strictly increasing over the supported score levels. In that case, arg min Rℓ,i = arg min gℓ,i = arg min BSℓ ( gℓ,i ; u). i

i

i

B

Proof of Robustness-Detectability Tradeoff

B.1

Proof of Theorem 9

Consider an adversary that, at each decoding step t, selects the token minimizing the probability p̂ ratio: j∗ = arg min j∈V p jj . By the defeatability condition (Definition 1), this selection is equivalent to j∗ = arg min j∈V s j . The Cumulative detection score over a sequence of length T is S = ∑tT=1 sit∗ . Since the adversary selects the score-minimizing token at every step, S is minimized in expectation over all possible generation paths. The detector declares watermark presence by thresholding S against a fixed value τ; the true positive rate is Pr p̂ (S ≥ τ ) . Minimizing S at each step reduces E p̂ [S], which directly reduces TPR. Therefore, the adversary can drive the detection rate to baseline levels, and the watermark is not robust.

B.2

Proof of Theorem 10

By the Neyman–Pearson lemma [27], the most powerful test at significance level α for the simple hypothesis pair H0 : x ∼ p versus H1 : x ∼ p̂ is the likelihood-ratio test, which rejects H0 when Λ( x ) = p̂( x )/p( x ) exceeds a threshold τα calibrated to achieve false positive rate α. No other test achieves a higher true positive rate at the same false positive rate. Detection power is therefore maximized when the score function s used to compute the detection statistic preserves the ordering of Λ( x )—that is, when s( x ) ∝ log( p̂( x )/p( x )). Under this assignment, tokens with larger likelihood ratios receive higher scores. However, aligning s with log( p̂/p) implies that arg min s j = arg min log j

j

p̂ j p̂ j = arg min . pj pj j

This is precisely the defeatability condition of Definition 1. By Theorem 9, the scheme is therefore not robust. Since both conclusions follow from the same alignment requirement, improving detectability necessarily strengthens the structure that the adversary exploits. 33

C

Proof of Theoretical Attack Effectiveness

Lemma 1 (Minimum versus convex combination). For arbitrary real numbers a1 , . . . , an and weights q1 , . . . , qn satisfying q j ≥ 0 and ∑in=1 q j = 1, we have min1≤i≤n a j ≤ ∑in=1 q j a j . Equality holds if and only if every index assigned positive weight is a minimizer of a j . Proof: Let amin = min j a j . Since amin ≤ a j for every i, multiplying each inequality by the nonnegative weight q j and summing gives n

n

i =1

i =1

∑ q j amin ≤ ∑ q j a j .

Because ∑ j q j = 1, the left-hand side equals amin , proving (1). The inequality is strict exactly when q j > 0 for at least one index satisfying a j > amin .

C.1

Proof of Theorem 11

Fix a decoding step t and condition on h1:t−1 = h and ξ t . By Equation (25), minimum-ratio selection also minimizes the token score: st ( xtA | h, ξ t ) = min st (i | h, ξ t ). i ∈St (h)

The conditional expected score of an unwatermarked token is   E st ( xt0 ) | h1:t−1 = h, ξ t = ∑ pt (i | h)st (i | h, ξ t ). i ∈St (h)

Because the values pt (i | h) are nonnegative and sum to one, Lemma 1 gives min st (i | h, ξ t ) ≤

i ∈St (h)

∑ pt (i | h)st (i | h, ξ t ).

i ∈St (h)

This proves (26). Multiplying by wt ≥ 0, summing over t, and applying the law of total expectation gives Under fresh-key null invariance, the counterfactual null scores have the same joint distribution as the scores generated under H0 . Hence the right-hand side equals E[s0j ], proving Equation (27).

C.2

Proof of Theorem 12

We construct the attacked and null score sequences on a common probability space. Suppose the attacked prefix h1:t−1 has already been generated. Conditional on this prefix and the current key realization ξ t , the adversary selects xtA by minimizing the probability ratio. By the pointwise alignment condition in (28), ϕ(ξ t , h1:t−1 , xtA ) =

min

i:pt (i | h1:t−1 )>0

ϕ(ξ t , h1:t−1 , i ).

Define the attacked score as ZtA := ϕ(ξ t , h1:t−1 , xtA ). 34

On the same probability space, independently sample the counterfactual null token Yt ∼ pt (· | h1:t−1 ) and define et0 := ϕ(ξ t , h1:t−1 , Yt ). Z Because Yt belongs to the support of the base distribution, the score-minimizing property gives et0 ZtA ≤ Z

almost surely.

e 0 is evaluated at the attacked prefix, fresh-key null invariance implies Although Z t   et0 | h1:t−1 = Gt . L Z Therefore, its conditional distribution is exactly the same as that of a null score used to calibrate the detector and does not depend on the attacked history. Repeating the construction for t = 1, . . . , T yields d e10 , . . . , Z eT0 ) = (Z ( Z10 , . . . , ZT0 ). At the same time, Equation (C.2) holds simultaneously at every step: et0 , ZtA ≤ Z

t = 1, . . . , T,

almost surely.

Since Φ T is coordinatewise nondecreasing, e10 , . . . , Z eT0 ) =: D e T0 DTA = Φ T ( Z1A , . . . , ZTA ) ≤ Φ T ( Z

almost surely.

d

e 0 = D0 . Hence, for every threshold τ, Moreover, D T T e T0 ≥ τ ) = Pr( DT0 ≥ τ ). Pr( DTA ≥ τ ) ≤ Pr( D 0

A

Thus DTA ⪯st DT0 . Setting τ = τε gives TPRA (ε) ≤ Pr( DT0 ≥ τε ) ≤ ε, 0

which proves (29).

C.3

Proof of Theorem 13

Let Et be the event that the estimator selects a score-minimizing token within Ct . If xt0 ∈ Ct and Et occurs, then st ( xtA ) = min st (i ) ≤ st ( xt0 ). i ∈Ct

Therefore, the coordinatewise coupling used in Theorem 12 fails only if xt0 ∈ / Ct or Etc occurs. Hence, T [
{ DTA ≥ τε } ⊆ { DT0 ≥ τε } ∪ { xt0 ∈ / Ct } ∪ Etc . t =1

Taking probabilities and applying the union bound gives T

Pr( DTA ≥ τε ) ≤ ε + ∑ (ρt + ζ t ), A

t =1

which proves (30). 35

Related documents

• A Unified Attack Framework against Statistical Generative Watermarks for Large Language Models#1403449
• Optimizing watermarks for large language models#1063703
• Dataset Watermarking with Provable Black-Box Detection#1130546
• A Watermark for Large Language Models#16582
• Black-Box Membership Inference via Word-Level Probability Estimation#997613