Improving the Trade-off Between Watermark Strength and Speculative Sampling Efficiency for Language Models
Authors: Weiqing He
Xiang Li
Li Shen
Weijie J Su
Qi Long
Venue: ICLR 2026 Poster (2026)
Keywords: Watermark
LLM decoding
Speculative Sampling
Primary area: generative models
TL;DR: We revisit the trade-off between watermarking and speculative sampling, introducing a new strength measure and mechanism to improve the trade-off.

Abstract: Watermarking is a principled approach for tracing the provenance of large language model (LLM) outputs, but its deployment in practice is hindered by inference inefficiency. Speculative sampling accelerates inference, with efficiency improving as the acceptance rate between draft and target models increases. Yet recent work reveals a fundamental trade-off: higher watermark strength reduces acceptance, preventing their simultaneous achievement.
We revisit this trade-off and show it is not absolute. We introduce a quantitative measure of watermark strength that governs statistical detectability and is maximized when tokens are deterministic functions of pseudorandom numbers. Using this measure, we fully characterize the trade-off as a constrained optimization problem and derive explicit Pareto curves for two existing watermarking schemes.
Finally, we introduce a principled mechanism that injects pseudorandomness into draft-token acceptance, ensuring maximal watermark strength while maintaining speculative sampling efficiency. Experiments further show that this approach improves detectability without sacrificing efficiency.
Our findings uncover a principle that unites speculative sampling and watermarking, paving the way for their efficient and practical deployment.

Published as a conference paper at ICLR 2026
IMPROVING THE TRADE-OFF BETWEEN WATERMARK STRENGTH AND SPECULATIVE SAMPLING EFFICIENCY FOR LANGUAGE MODELS
Weiqing He; Xiang Li;; Li Shen', Weijie Sul, Qi Long
University of Pennsylvania weiqinghs sas upenn. edu, 1=100770ppenn.ede
{1i, sinst suwewharton) upennn edu, qlongeupenn, edu
ABSTRACT
Watermarking a principled approach for tracing the provenance large language model (LLM) outputs, but its deployment in practice is hindered by inference inefficiency. Speculative sampling accelerates inference, with efficiency improving as the acceptance rate between draft and target models increases. Yet recent work reveals a fundamental trade-off: higher watermark strength reduces acceptance, preventing their simultancous achievement. We revisit this trade-off and show it is not absolute. We introduce a quantitative measure of watermark strength that governs statistical detectability and is maximized when tokens are deterministic functions of pseudorandom numbers. Using this measure, we fully characterize the trade-offaa as constrained optimization problem and derive explicit Pareto curves for two existing watermarking schemes. Finally, we introduce a principled mechanism that injects pseudorandonness into draft-token acceptance, ensuring maximal watermark strength while maintaining speculative sampling efficiency. Experiments further show that this approach improves detectability without sacrificing efficiency. Our findings uncover a principle that unites speculative sampling and watermarking, paving the way for their efficient and practical deployment
INTRODUCTION
In the era of generative AI, data provenance has become pressing concern in academia, journalism, and everyday content creation, where ensuring authenticity is both responsible and critical (Weidinger (ct al.) 2022 Starbird 2019; Milano et al. 2023 Shumailov et al., 2024). Watermarking offers principled solution: it embeds verifiable signals into generated text by modifying the token sampling process with a recoverable pseudorandom number and a carefully designed sampling strategy (Aaronson) 2023 Kirchenbauer et al. 2023] Kuditipudi al. 2024). A good watermarking scheme should embed strong watermark signal, namely the dependence between sampled tokens and pseudorandom numbers. The degree of this dependence, referred watermark strength, directly affects detection efficiency (Li et al.) 2025 +). However, deploying watermarking in large-scale LLM inference faces two major bottlenecks: tokens are generated sequentially, each requiring full forward pass, and the lack of parallelization leaves GPUs underutilized. Together, these bottlenecks make watermarking slow and inefficient in real-world deployment.
Speculative sampling addresses these bottlenecks by accelerating autoregressive generation without compromising quality (Chen al., [023) Leviathan et al., 2023) Xu et al., 2024). It employs two models: a lightweight draft model that rapidly proposes multiple candidate tokens, and larger target model that verifies them in parallel. most draft tokens are accepted, computation greatly reduced; if not, the target model must regenerate them, negating the speedup. The acceptance process is stochastic, with its probability determined by how closely the draft model's proposals align with the target model's s distribution (Yin et al. 2024). Thus, high efficiency requires the two distributions to
"Equal contribution. Coorespoondig authors.
Code is available at http:///////......oo/////////aaa

---

Published as a conference paper at ICLR 2026
be sufficiently similar, ensuring high acceptance rate. Unfortunately, Hu & Huang (2024) show that, when watermarking is combined with speculative sampling, it is impossible to simultaneously achieve both the highest acceptance rate and the strongest watermarking strength a rather discouraging result that suggests fundamental trade-off between watermark strength and sampling efficiency.
In this work, ask whether and how this seemingly unavoidable trade-off can be overcome, trying to pave the way for more efficient deployment of watermarking under speculative sampling. We revisit the impossibility result and identify a potential path forward. A key limitation in (Hu & Huang 2024) is that watermark strength is defined in a binary manner: watermarking is considered preserved and only if each token's 's distribution exactly matches designated watermarked distribution. This definition, however, doesn's i quantify how each token is coupled with recoverable pseudorandom number. As result, it overlooks intermediate levels of watermark strength, preventing a nuanced characterization of the trade-off and leaving open the possibility for improvement.
Contributions. Building on this observation, we make the following contributions:
Quantifying watermark strength. We introduce a quantitative measure of watermark strength for unbiased watermarks, defined as the expected KI. divergence between the watermarked and original token distributions. We show that this measure governs the decay rate of p-values, is upper bounded by the entropy of the original distribution, and attains its maximum precisely when tokens are deterministic functions of pseudorandom numbers. Notably, both OpenAl's (Aaronson) 2023) and Google's (Dathathri et al. 2024) watermarking schemes achieve this maximal strength.
Characterizing the trade-off. Based on this measure, we formalize the trade-off curve as the Pareto frontier between watermark strength and (speculative) sampling efficiency. Here, sam- pling efficiency quantified by the acceptance rate, following prior work (Hu al.) (0224). For illustration, we show that when both the draft and target models are "linearly" watermarked, this frontier can be characterized by solving a constrained convex optimization problem that maximizes watermark strength subject to a sampling efficiency requirement. Importantly, this formulation is general and can be applied in a plug-and -add-llyy manner any watermarking schemes. As examples, we illustrate the trade-off curves for OpenAl's 's and Google's 's watermarking methods.
Improving the trade-off. Finally, we propose a principled mechanism to overcome this trade-off by applying pseudorandom draft-token acceptance. We prove that it achieves maximal watermark strength while preserving speculative sampling efficiency, and empirically verify that it improves detectability under the same efficiency, offering a constructive path toward practical deployment.
Paper organization. The remainder of this paper is organized as follows. Section reviews preliminaries on watermarking, speculative sampling, and the previous trade-off. Section introduces a quantitative measure of watermark strength and uses it to fully characterize the trade-off. Section presents our mechanism for improving the trade-off. Section presents experimental results that validate our mechanism. Due to space constraints, we defer the discussion of related work to Appendix A and provide all proofs in Appendix and
PRELIMINARIES
For token in the vocabulary W, let P denote its distribution. A watermarking scheme can be viewed as a tractable way to modify P using pseudorandomness (Hu et al.] 2024). Specifically, samples w Pt from a modified distribution P: := S(P,<) <). where C is a pseudorandom variable and S is carefully designed decoding function. A scheme (or decoder) is said to be unbiased if averaging over pscudorandomness recovers the original distribution, i.c., Ec[P;] = P. During detection, the task is to decide whether observed token sequence comes from the original distribution or its watermarked modification. This naturally leads to the hypothesis testing problem:
Ho
P and LS versus H1 w Ps S(P.C)
The key idea is to test for statistical dependence between w and the pseudorandom number Ç. Under Hu, watermark is embedded and w is independent of Ç, while under Hj the watermarking mechanism induces a structured dependence. In what follows, we illustrate this framework with two popular watermarking schemes.
Gumbel-max watermark. The most influential unbiased watermark is the Gumbel-max watermark (Aaronson 2023). It is built the Gumbel-max trick, widely used sampling method for multinomial
2

---

Published as a conference paper at ICLR 2026
distributions (Gumbel 1948; Maddison et al., 2014 Jang et al., 2016 The trick generates a set of independent uniform random variables ( (Uw) wee for each token in the vocabulary W, and
ensures that arg waX Lo follows the original distribution P = (Pu)wew Building on this
Pu
observation, Aaronson (023 proposed the following decoder: P.- = =Stum (Saum(P.) where
(S (P. (P))))()= 1, if t arg maX 0, otherwise.
log Un! Pw.
By construction, this watermarking scheme is unbiased (Li al. 2025
SynthID watermark. The SynthID watermark, proposed by Google (Dathathri et al. 2024), is based on a novel categorical sampling rule called tournament sampling. For a given number of tournament rounds m, the pseudorandom numbers is a collection of random vectors, given by <= = (g )m where each 9: = wew is a binary vector with entries independently drawn from (0.5. Under the wwo-candidate version of SynthID (the version we use throughout all discussions), the modified distribution can be defined as P. Sty" (P, S), with
S (P =Tam o .... To (P),
(3)
where Ty is the operator
(P)) = Pi. (1 +1+0 Du
Σ Pw.) P W u':9w==1
(4)
Dathathri et al. (2024) show that (P) corresponds to the distribution of the winner in a one-versus- one match: two tokens Wi, W2 are drawn independently from P. and the winner is the one with the larger pseudorandom bit value Iw. If Jw, 9wz, the tie is broken uniformly at random. Repeating this tournament for m rounds with independent vectors g, yields Sayn (P. {) as the distribution of the final winner token.
Speculative sampling. Speculative sampling accelerates LLM inference by first drawing draft token w' from Q and then checking it against the target distribution P (Chen et al., 2023). The draft token is accepted with probability min 1, Pwr//Q J; if it rejected, replacement token is sampled from a residual distribution proportional to the excess mass of P over Q. This accept/reject process induces a transition kernel on top of Q:
min (1, P-)) (Pu (Pu-Qu)
if w' w,
A(wlw')
(1-
Pio Qu'
if w' wr
(5)
where (x) = max 0}. We denote this kernel as Aspec (Q. P). By construction, applying it on
top of Q recovers the target distribution: P = Aspec Q P) Q. The acceptance rate under this
scheme is P(he inital w' is not rejected) = Σ min (P Qw which is the maximum achievable
among all kernels that preserve P (see Lemma 3.I. (.J].
Definition 2.1 (Sampling efficiency). Given a draft Q₂ and transition kernel A the sampling efficiency the expected acceptance rate:
SE(Q SE(Q,,A) E1l Σ Ac(wow))Q
NEW
An "inevitable" trade-off. Hu Huang (2024) prove that speculative sampling cannot simulta- neously maintain watermark strength and achieve maximal efficiency. Efficiency is measured by the expected acceptance rate (Def. [2.)). while watermark strength defined in binary manner. For any target distribution P and an unbiased decoder S, let P. S(P. <) be the watermarked token distribution. Watermark strength is preserved only if there exists pair (S',Ac such that
Aç Q Pt exactly for all pairs (Q, P) with Q₂ S' (Q. Here, the decoder S' could be different from S. Under this condition, the sampling efficiency is strictly below the maximum achievable: there must exists a pair (Q. such that
SE(Q
(SE(Q'. [Ec10]] Q, 1k PP. (Q(.AA))
sup
(6)
Conversely, if equality holds in (6) for all pairs (Q, P), watermark strength necessarily lost, i.e., Ac o Qu * Ps for some pair ().
We use Ac to denote general transition kemel, which is not necessarily dependent on pscudorandomness.
3

---

Published as a conference paper at ICLR 2026
3 COMPLETE THE TRADE-OFF CURVE
3.1 QUANTIHICATION OF WATERMARK STRENGTH
As introduced in Section 2 prior work (Hu & Huang 2024) does not fully characterize the trade-off, as it lacks quantitative notion of watermark strength. Their framework defines strength in binary way: it is considered preserved only if the actual token distribution exactly matches a designated watermarked distribution. This overlooks the essential idea that strength should capture how strongly each token depends on pseudorandomness, rather than just distributional equivalence. Consequently, intermediate levels of strength cannot be represented, preventing more nuanced trade-off analysis. Our first contribution is to introduce a quantitative definition of watermark strength, enabling a precise and continuous characterization of this trade-off.
Definition 3.1. For watermarking scheme that samples tokens from the modified distribution P. = S(P (), its watermark strength is defined as
Pe.. P..
(S(Pp) = Ee[ P|]=
Σ LWW
Pc,. log
where (Pe(P) denotes the Kullback-Lebbler (KL) divergence between the watermarked distribu- tion Pt and the original distribution P. From an information theory perspective, this definition can also be viewed as the conditional KL divergence, and under the unbiasedness condition E. [.c[Pp] P.
it is equivalent to the mutual information I(w; <).
Remark 3.1. Watermark strength is conceptually different from the detection efficiency studied in LLi et al. 2025). Watermark strength quantifies the ideal detectability assuming the true token distributions P. are known, whereas the latter considers worst-case efficiency when each P. is believed to fall into prior class without this assumption. As result, two schemes with comparable watermark strength may still differ in detection efficiency, depending on their sensitivity around the true token distribution. In practice, the Bayesian posterior detection rule in (Dathathri et al. 2024) may help bridge this gap, as it implicitly learns the token distributions from prior data.
Interpretation in terms of sample complexity. We now explain why the notion of watermark strength in Def. 3.1 is meaningful: it directly quantifies the difficulty of watermark detection. In particular, detection can be formulated as hypothesis testing problem (cf. Eq. (T)) where the task is to distinguish the original distribution P from its watermarked version Ps. Intuitively, greater watermark strength makes this test easier. The next theorem formalizes this intuition by showing that the average watermark strength determines the exponential decay rate of the p-value under the uniformly most powerful test (i.e., the likelihood ratio test), and thus the sample complexity required reach a prescribed significance level.
Theorem 3.1 (Sample complexity via p-value decay). Let (0,1) 1) and Wi.n- (w (w1..... ..... W.) Consider the hypothesis testing problem based on n independent samples:
Ho : Winn Pi ...
8 Pn with we 1. C. VL versus H1 Winn ~ Pi 8 ... @ Paga:
(mn.) where each S. is i.i.d. and the log- bigliielloood ratios 7, == log Pr(we) are independent, uni- formly bounded, and admit a common neighborhood around zero where their moment gen- erating functions are finite. Assume that the average KL divergence converges: D
lim 1 -E=1 Ee (P.cll < oc. Then, under Hi, the p-value of the likelihood ratio test, n-500
which is the uniformly most powerful (UMP) test, satisfies
lim 1
Log(p- DD in probability.
In particular, to guarantee the p-vuuue < a. it is necessary that n 2 1 log (2) (1++(1))
Maximum watermark strength. A natural question is which watermarking schemes achieve the largest watermark strength, as defined in Def. 3.1 The next theorem shows that for unbiased watermarks, the maximum is attained if and only if the modified token distribution P: is degenerate namely, for each pseudorandom number Ç, all probability mass is placed on a single token, so the generated token is deterministic function of Ç.
4

---

Published as a conference paper at ICLR 2026
Theorem 3.2 (Maximum watermark strength). 1f -.. follows that
WS(P:) = Ent( P) - Eş[Ent( Pc)] Ent(P) := : Σ
Pw log Pw.
wEW
Equality holds if and only if Ent((P)) (P:) almost surely.
Interestingly, both the Gumbel-max watermark and the SynthlD watermark (in the limit as m - oc) attain this upper bound.
Theorem 3.3. The Gumbel-max watermark and the SynthID watermark (as m + oo) achieve the maximum watermark strength in Thm. 3.2
3.2 TRADE-OFF CURVES AND EXAMPLES
Formulation of trade-off curves. Suppose the unwatermarked draft model is Q and the unwa- termarked target model is P. An unbiased decoder from a family Qdraft transforms Q into watermarked draft Q := Saraft (Q, (), where is pseudorandom number. A transition kernel A then rectifies Q so that the final distribution P. := A o Qc remains unbiased, i.e., Ee = P. With these components in place, of watermark strength (Def. 3.1) and sampling efficiency (Def. 2.1).
now introduce the trade-off curve, which is defined in terms
Definition 3.2 (Trade-off curve). The rafe-ooff curve is a function T that maps an efficiency require- ment r (a lower bound on the sumpling efficiency) to the largest achievable watermark strength:
max L(r)= Sáraft Eárafs: Ac
WS(P:)) S.f. P: Aç QC, Eç[Pa] = SE(Q Ac) 2 r.
Lemma 3.1 (Speculative sampling optimal). Fix a draft model Q₂ and a target model Pt, we define the speculative sampling efficiency (SSE) between them
SSE(Qc: Pc) = sup (SE(Qc, P. = A o Qc} = SE(Qc, Aspec Pc).
Ac
If E = Q and Eg [p] P. then SSE(Q,, S -1- SSE(Q,
As high level, Def. 3.2 defines the trade-off curve as the Pareto frontier of the achievable region in the plane of watermark strength versus sampling efficiency. Each boundary point gives the strongest watermark attainable under efficiency requirement r. While the definition allows arbitrary kernels Aç. the objective depends only on the induced distribution P. = Aç Qc- Lemma (.T shoos that for any fixed Pc. the speculative sampler Aspec (Qc, Pt) achieves the maximal efficiency among all Aç realizing P.. Thus, replacing Aç with Aapec ( Pt) preserves watermark strength and never decreases the efficiency. Therefore, without loss of generality, the trade-off curve can be studied by restricting to Aç = Aspec (Ap, Pç)) and working directly with P::
Conceptually, we can view Pę as the output of an unbiased decoder Starget from a family Qtarget (in parallel to Qc). With this simplification, the trade-off curve can be reformulated as
max I(r) Saraft Edraftt Starget @Quarget
WS(P:)
s.t. Pc) 2r.
(8)
This formulation is clean and implementation-ffiendly once the families Qdraft and Qtarget are specified, solving ( yields concrete visualization of the complete trade-off curve.
Remark 3.2. In many cases, the final distribution P: := A o Q admits an explicit form. For instance, in (Hu& & Huang] 2024), uses P: := Aspec Q) o Q₂ to achieve the highest sampling efficiency. Such an explicit formulaa can naturally be regarded as defining a decoder Seargets and all schemes of this type can be collected into the family Quarget-
An example trade-off curve. Now turn to visualizing the orf curve in 8 for two popular watermarking schemes. As discussed earlier, it suffices to specify two families of unbiased decoders for and P, respectively. To make this concrete, consider the linearly watermarked classes
Qdraft {(1 - 0)Id + Saratt A [0, 1]}, Qtarget {(1 - Id + Starget 7 10, 1]: (9)
where Id denotes the identity decoder that leaves the distribution unchanged, and Sarant Starget. preseribed unbiased decoders. In this construction, if we write Q₂ == Saraft (Q, () and P:
5

---

Published as a conference paper at ICLR 2026
Gumbel-max
Watermark Strength
2.0
2.00
SynthiD(m=
SynthID(m=30)
1.75
Linear class
Hu's class
1.0
1.50
Google's class
WS maintained
1.25
maintained
Std. SpecSampl. Optimum
0.0
1.00
0.60
0.70
0.65
0.70
Sampling Efficiency
Sampling Efficiency
Figure 1: Trade-off curves between watermark strength and sampling efficiency for simulated (Q, P) pairs. Left: Curves for the linearly watermarked classes (9) Right: Curves for other classes, including Hu's class (Hu & Huang 2024) and Google's class (Dathathri et al. 2024). Orange and blue denote Gumbel-max and SynthLD, respectively. Here, solid, dashed, and dotted lines correspond to different classes. Markers indicate the boundary point of each curve.
Starget (P.)), then identifying the trade-off curve (r, L(r)) amounts to finding its inverse curve (L) where (p) is given by
(p) 1 1 min Eş1l(1 - 0)Q + AQ: - P
7.0
(10)
s.t. Ec [Ent - P - p.
One can derive this formulation (10) by combining Defs. 2.1 and 3.1
with the transition kernel in (5)
and the identity En min Pw. Qw) 11--V Q)
The map (7, 0) ~ [1(1 Q)Q - AQ - (1- P-yplli is convex, since it is the & norm of an
affine function. By contrast, entropy concave, so the feasible set of (00) is not convex in general. Yet when Starget degenerate (so P: is almost surely a point mass), E [Ent((1 P + y Pc)
decreases monotonically in y. In this case, the constraint reduces
%o. where to is the unique
threshold satisfying [Eq[Ent(11 - P + Pt). p. and the problem TTP simplifies to
L (p) = =1
min 7E
Eşl((1 Q)Q + 8Q. - -1-
Comparisons of trade-off' curves. In Fig. I we plot the trade-off curves for simulated Q and P (see Appendix C.I for the details). The left panel shows the curve for the linearly watermarked classes (9). The green cross at the lower right marks the sampling efficiency of standard speculative sampling, and the two blue points mark the watermark strengths achieved by Gumbel-max and SynthID, respectively. Unless stated otherwise, we set tournament rounds m oo for SynthID.. As shown Thm. 3.3] both watermarks attain the same maximal watermark strength, so the blue points lie on the same horizontal line.
The right panel shows trade-off curves for two additional classes: one from Hu & Huang (2024) ("Hu's class") and one from Dathathri et al. (2024) ("Google's class"). While the original works describe how to attain the endpoints of these curves, our framework connects them via a similar linearly interpolated class (see Appendix C.2 for explicit expressions), enabling direct comparison. The results show that Google's 's class achieves higher watermark strength than Hu's 's at matched sampling efficiency, yet neither reaches the theoretical optimum (red star). Moreover, when we set m = 30-a practical choice for SynthID- drops below that of Gumbel-max (see the lower gray curve), consistent with Thm. 3.3 This is expected, as the maximal watermark strength is attained only in the limit m +
apply it to Google's class, the watermark strength
00. 00.
4 IMPROVING THE TRADE-OFF CURVE
4.1 BREAKING THE TFA THROUGH PSEUDORANDOM ACCEPTANCE
Motivation. With the complete trade-off curve established in Section 3 we now ask whether it can be thht is, whether speculative sampling be used in watermarking simultaneously

---

Published as a conference paper at ICLR 2026
Algorithm Fast watermarked speculative sampling with pseudorandom acceptance
1: Given: lookahead K, output length N, target model P, draft model Q, initial prompt
Wims Watermarked models Qço == S(Q, P) and P-- := S(P, residual sampler
(P-Q) -Q)),erT := = +++ ),,, and pseudorandom generator G.
2: while < N do
Draft K tokens under the watermarked draft model
3: for = 1 to K do
4: Sample draft token i. Qcp. (:1 Winn W1a-1)).
5: end for
6: In parallel: compute K sets of target logits from draft tokens, i.c., P(: Wim), P(.
Winns w P(- Wi:n: W1:k).
7:
for to K do
Sequentially try accept each draft token Compute pscudorandom (0, 1) variable: un+s + G(Cn++) E (0, 1).
8:
( if un+s < &min Q (1 then
9:
Accept: set wn+11 & Wsi n n + 1.
11:
else
12:
Reject: sample wi+1 ~ (P Q) Q)+.r((
Wim)): n 4 n + 1; break.
13:
end if
14:
end for
15:
if' all Wis.... KK were accepted then
b Bonus step as in speculative decoding
16:
Sample one extra token Wn+1 ~ Per (- Wim): n t n n
17:
end if
18:
end while
attain the largest watermark strength and the highest sampling efficiency (SSE). From Lemma 3.1 the
maximal SSE for a draft-target pair (Q, P) is TV(Q, P). Existing approaches that achieve this bound rely on the transition kernel Agpec Q Q.P.P. in S. which accepts a draft token w' with probability min(1, 1, Pw.P//Qura /Qwr} (Hu Huang 2024 Dathathri et al. 2024). However, this mechanism leaves residual randomness: even with full knowledge of the pseudorandomness in both the watermarked draft and target models, the final token is not predetermined, since it may or may not be the draft token depending
the acceptance coin flip. This inherent randomness weakens watermark strength, because under Def. 2.1 any distribution attaining maximal watermark strength must be degenerate, placing all its mass on single token. Motivated by this observation, we propose new approach that preserves both goals: we make the acceptance decision itself pseudorandom, so that the entire generation process becomes a deterministic function of pseudorandom variables.
Algorithm description. We formally present our method in Alg. I The algorithm is driven by pseudorandom variable with three components = (sD, <T, CC)). The first two components, çD and ST. determine the watermarked distributions: ÇD) controls sampling from the draft model Qeo, while ST controls sampling from the target model Per and from the residual distribution (P-Q) +)+.cr when draft tokens are rejected. The third component, <R, governs acceptance decisions for draft tokens. In particular, at each step s, we compute the acceptance variable u, G(CF),, where G is pseudorandom number generator producing values uniformly in [0, 1]. Additionally, to further ensure the unbiasedness of the entire generated sequence, we apply repeated context masking (Hu et al. 2024 Dathathri et al. 2024 Hu & Huang 2024) in Alg. which skips watermarking for repeated contexts.
The key difference from (Dathathri et al. 2024) that the acceptance variable is now pseudorandom rather than truly random (line (8). As result, Alg. | becomes fully deterministic function of pseudorandom variables, with no external randomness involved. We show that this modification preserves unbiasedness and, in theory, attains the maximal possible SSE (Thm. I.Ip.
Theorem 4.1. Focus single intermediate step s and omit the index for brevity. Let P be target model and Q a draft model. Assume the decoder S is unbiased and achieves the largest watermark strength (hence is degenerate by Thm. (32)). Define the target and draft watermarked distributions by Per S(P, "P and Q = =(Q (D) respectively. Let Aç denote the transition kernel introduced in Alg. 7 and let P. denote the distribution of the output token with := PSP, (SP, <D. ST. and CR independent. Then the following properties hold:
SF (. Suppose
7

---

Published as a conference paper at ICLR 2026
(a) Unbiasedness: for every token W. we have Eg [p[)((w)] = P(w).
(b) Maximum sampling efficiency:
= = 1 -
(c) Maximum watermark strength: WS( P() = (P)
4.2 DETECTION UNDER PSEUDORANDOM ACCEPTANCE
Alg. introduces a new pseudorandom component ÇR, which can also be used to enhance watermark detection. As discussed in Remark 3.1 watermark strength is conceptually distinct from detection efficiency (detectability). While Thm. |4.1 shows that our algorithm preserves the maximum sampling efficiency and attains the maximum watermark ttrength-thur breaking the trade-off in theory- does not guarantee optimal detection efficiency. In principle, the most powerful detector is the log- ligelikel ratio test. but it is impractical since it requires access to the true token distributions P. (Huang et al. 2023 Li et al., 2025). Nonetheless, the extra information encoded in ( reduces uncertainty about the token generation process and can therefore improve detectability. Next,
show how to use ς to improve detectability for Gumbel-max and SynthID. In Section 5 empirical evidence that our method indeed enhances detection efficiency.
we provide
Gumbel-max watermark. As described in Section 2 the pseudorandom variables for the Gumbel- max watermark (i.e., CP: ( assign i.i.d. UO, 1) values all tokens, and the decoder selects the token W/ that solves the argmax in (2). For detection, the corresponding (0, 1) value is extracted as test statistic (Aaronson 2023 When watermarked, it tends to concentrate near one: otherwise, remains uniform. With speculative sampling, however, two candidate statistics arise for each token we one from the draft model (yp e IR) and one from the target model or the residual distribution
(ul" E R). In our algorithm, W/ comes from the draft model iff n G(CR) S T (see line 9
in
Alg. we naturally select y/: by
y== 3i Po(c)(()rrr + Vi 1o(c))2r
(11)
where is calibrated held-out validation set by grid-searching over candidate values and selecting the one that achieves the highest true positive rate (TPR) under the desired false positive rate (FPR). In contrast, without access to We, one must rely on the empirical acceptance rate (Dathathri et al. 2024). selecting
y V with probability p. Yo = vZ with probability 1 1-p.
(12)
where p is estimated from observed acceptance rates. After y is chosen, detection proceeds by applying the classic test of Aaronsom (2023), which flags watermarking when Σ, - log(1 ye) is stochastically larger than expected. We reter the detector based on rule (1T) as Ars-7 and the one based on rule (12) as Ars-Prior. Empirically, the two differ in efficiency.
SynthID watermark. A similar challenge of selecting the correct test statistic (i.e., the pseudo- random numbers that generated token we) also arises in the SynthID watermark. Recall that each pseudorandom variable <P (g.)) consists of m random binary vectors, and the test statistic is defined as vp = (gL. (we), (w.)....,,ee .i.m....mm.mmm........... (wx)) E IR"", which collects the w;-th components of all vectors; the counterpart vi" E IR. is defined analogously. The key detection principle is that, for the correct pseudorandom variable (c.g.. y²),, entries are biased toward one, while for the incorrect one they remain uniformly random in {0, 13. This bias stems from the tournament sampling process: since the winning token must repeatedly have larger g- vavluess across m rounds, the final we tends to carry more ones in its associated vector.
In the prior detection of Dathathri et al.) (2024), a Bayesian scoring neural network in R.' is trained, and under speculative sampling. the two scores from y/2 and y! are combined through a simple weighted average (see Appendix [ for the details). This averaging dilutes the signal and reduces detection efficiency. In contrast, our algorithm has access to the acceptance variable we, which, while not directly revealing the source model of w;, carries signals about whether the token was generated by the draft or target model. Since the exact threshold (i.e., minς1, Pw/Qw/ separating the two cases is unknown, we treat this as a binary classification problem: given (v, D. .V."" and ut, a
NNoe that the tokens generated during bonus steps are not controlled by the acceptance variable. However. as long as the lookahead K is not very small (e.g., K = 1), the sampling process rarely enters bonus step, its impact on detection negligible in practice.
8

---

Published as a conference paper at ICLR 2026
three-layer perceptron (MLP) is trained to select the correct statistic rather than averaging. We refer to this enhanced method as Bayes-MLP, and to the prior approach as Bayes-Prior.
5
EXPERIMENTS
1.0
Gumbel-max
1.0
SynthiD
2.5
SynthlD
0.8
Std. SpecSampl.
TPR@- 110----111 1%
AATPS
2.0
1PR@PPP
0.6
0.4
1.5
0.2
Ars Prior
Ar5-T
Dayes: MLP
Bayes Prior
Cracle
0.2
Oracie
1.0
K-2
K=3
K=4
0
50
100
150
200
0
50
100
150
200
Lookahead Longth
Number Tokens
Figure 2: Left: Average Accepted Tokens Per Step (AATPS) of Alg. applied the Gumbel-max and SynthlD watermarks, compared with Standard Speculative Sampling (Std. SpecSampl). Error bars mark the 95% confidence intervals. Middle and Right: Watermark detectability (TPR at FPR 1 1%) for Alg. on the Gumbel-max (middle) and SynthID (right). Orange curves show our method, blue curves show the prior-based method, and black curves represent the ideal detector (Oracle) that always selects the correct test statistic. Shaded regions indicate the 95% confidence intervals.
In this section, we show that Alg. I simultaneously improves watermark detectability and attains the highest speculative-samplin efficiency. We evaluate Gumbel-max and SynthID (m 30) on the ELI5 dataset (Fan et al., 2019) for the question- guestion-answering task and use two draft-target model pairs: Llama- 6 8M & L ama- 7B (Miao et al. 2024 Touvron al.) 2023) and Gemma-22 & Gemma-7B Team et al. 2024). In each pair, the larger model serves as the target and the smaller model the draft. We report results for the Llama pair in the main text and defer the Gemma results to the Appendix (see Fig. 33). We compare our methods, Ars-7 and Bayes-MLP, against the baselines Ars-Prior and Bayes-Prior (see Section 4.2 4.2tionn4.21e for definitions). Besides, we also evaluate Alg. on the C4 dataset (Raffel et al. 2020) for the open-ended generation task with the same model settings, and
the results are provided Appendix
F22
Following (Hu & Huang 2024). we measure sampling efficiency by Average Accepted Tokens per Step (AATPS) from Alg. From the algorithm, least one token generated each step, AATPS lies in [1, K ++11 1]. We report results for K E {2, 3, 4), with larger AATPS indicating higher efficiency. We measure watermark detectability using the true positive rate (TPR) at fixed false positive rate (FPR) of 1%. To make the results more pronounced, we use lower temperatures: 0.5 for Gumbel-mai and 0.7 for SynthID. Since detection methods Section (.2tion/.221 require training data, each experiment generates 2,000 watermarked texts, split into 1,000 for training and 1,000 for testing. For SynthID, for which the null-score distribution lacks closed form, we additionally sample two disjoint sets of 1,000 Himan--rittee texts from ELI5 unwatermarked training and test data.
Sampling efficiency is maintained. The left panel of Fig. 2 shows that, for both Gumbel-mar and SynthID, Alg. preserves sampling efficiency: the measured AATPS closely matches the standard speculative-sampling baseline. Exact numbers are provided in the Appendix (see Tab, and 2}.
Improved detectability. The middle and right panels of Fig. 2 show that, for both watermarks, our method attains higher TPR with fewer tokens, demonstrating that pseudorandom acceptance variables enhance watermark detectability. Also, we present the corresponding ROC curves in Fig. 4 and which further corroborate this improvement by providing of detection performance. Besides, we include an oracle-pert pedele-prffrmancc curve representing an ideal detector that always selects the correct test statistic. The results show gap between method and this theoretical upper bound consistent with the analysis in Section 4.2 -buu the gap not large, and our method approaches the oracle performance
comprehensive characterization
token length of 200.
Additionally, we report the Per Token Time (PTT) in milliseconds to evaluate empirical runtime, and the results confirm that Alg. indeed provides acceleration compared to basic unbiased watermarking

---

Published as a conference paper at ICLR 2026
methods (without speculative sampling). We also compute the Log Perplexity (LOGPPL) verify the unbiasedness property of Alg. [T] the results show that it preserves the underlying output distribution and therefore does not degrade the language model's output quality, All results presented in Tab. and 2
CONCLUSION
In this work, we revisited the trade-off between watermark strength and speculative sampling efficiency. We introduced quantitative notion of watermark strength that links directly statistical detectability, moving beyond prior binary definitions. With this measure, we cast the trade-off as constrained optimization problem and derived explicit Pareto curves for existing schemes. Building on these insights, we proposed principled mechanism that injects pseudorandomnes. into draft- token acceptance. We proved it achieves maximal watermark strength while preserving speculative sampling efficiency, and we empirically verified improved detectability at the same efficiency.
Our findings suggest several practical directions. First, although we focus on standard speculative sampling. the framework points toward potential extensions to variants such as tree-based meth- ods (Miao et al., 2024, Cai al. 2024), which could further accelerate generation. Second, while consider several common decoder classes, future work can explore broader (Qdraft, Quargot) choices-for example, using different decoders for the draft and target models. Third, our current work directly applies to unbiased degenerate watermarks, but it is open and interesting direction to investigate how to extend our framework and establish similar improvements to non-degenerate watermarks and even biased ones. In this way, might have larger toolbox trade off generation quality for stronger detection in the context of speculative sampling. Finally, given that human edits can weaken watermark signals (Sadasivan et al. 2023 He al. 2024a [i al., (2025+), investigating the impact of pscudorandom acceptance on robustness to editing is an open direction for future work.
ACKNOWLEDGMENTS
This work was supported in part by NIH grants ROI ROIAG07117A U0ICA274576, RO1EB0360 6, R01EB037101, U0166666,33 R01LM014731, and P30AG073105, NSF grant DMS-2310679, Meta Faculty Research Award, and Wharton AI for Business. The content is solely the responsibility of the authors and does not necessarily represent the official views of the NIH.
ETHICS STATEMENT
This work studies the interaction between watermarking and speculative sampling large language models (LLMs). Our research does not involve human subjects or personally identifiable information, and experiments are conducted using publicly available models and datasets. The purpose of this work is to improve the transparency, traceability, and efficiency of LLM outputs, which we believe aligns with responsible AI development. are not aware of any foreseeable negative societal impacts from this research.
REPRODUCIBILITY STATEMENT
We have taken several steps to ensure the reproducibility of our results. All theoretical claims are stated with clear assumptions, and full proofs are provided in Appendix and D The experimental setup, including model pairs, datasets, and evaluation protocols, is described in detail in Section 4.2 55d with additional details provided in Appendix C and To further support reproducibility. provide anonymized source code for running experiments supplementary material.
10

---

Published as a conference paper at ICLR 2026
REFERENCES
Scott Aaronson. Watermarking of large language models, August 2023. URL
www.uutttttiiioopeeeeaet -8-27-0--1
Tianle Cai, Yuhong Li. Zhengyang Geng, Hongwu Peng, Jason D Lee, Deming Chen, and Tri Dao. Medusa: Simple I1m inference acceleration framework with multiple decoding heads. In International Conference Machine Learning, pp. 5209-5235. PMLR, 2024.
Charlie Chen, Sebastian Borgeaud, Geoffrey Irving, Bean-Baptiste Lespiau, Laurent Sifre, and John Jumper. Accelerating large language model decoding with speculative sampling. arXiv preprint arXiv:2302.01318 2023.
Sumanth Dathathri, Abigail See. Sumedh Ghaisas, Po-Sen Huang, Rob McAdam, Johannes Welbl, Vandana Bachani, Alex Kaskasoli, Robert Stanforth, Tatiana Matejovicova, Jamie Hayes, Nidhi Vyas, Majd AI Merey, Jonah Brown-Cohen, Rudy Bunel, Borja Balle, Taylan Cemgil, Zahra Ahmed, Kitty Stacpoole, Ilia Shumailov, Ciprian Baetu, Sven Gowal, Demis Hassabis, and Pushmeet Kohli. Scalable watermarking for identifying large language model outputs. Nature, 634 (8035):818-8)) Oct 2024, URL UtLhttps:://// / /tgp::::/d/ooo///////////// 10. 1011/141111100 486
Rick Durrett. Probability: Theory and Examples (Edition 4.1). Cambridge University Press, 2013.
Angela Fan, Yacine Jernite, Ethan Perez, David Grangier, Jason Weston, and Michael Auli. ELI5: Long form question answering. In Proceedings of the 57th Anmual Meeting of the Association for Computational Linguistics, pp. 3558-3567, 2019.
Pierre Fernandez, Antoine Chaffin, Karim Tit, Vivien Chappelier, and Teddy Furon. Three bricks to consolidate watermarks for large language models. In 2023 IEEE International Workshop on Information Forensics and Security (WIFS), pp. 1-6. IEEE, 2023.
Jiayi Fu, Xuandong Zhao, Ruihan Yang. Yuansen Zhang, Jiangjie Chen, and Yanghua Xiao. Gumbel- Soft: Diversified language model watermarking via the GumbelMax-trick, In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics ( (Volume 1: Long Papers), pp. 5791-5808, 2024.
Eva Giboulot and Furon Teddy. WaterMax: Breaking the LLM watermark detecraabiiiyyyrouuttes. quality trade-off. arXiv preprint M4Vv:24403048000 2024.
Emil Julius Gumbel. Statistical theory of extreme values and some practical applications: A series of lectures, volume 33. US Government Printing Office, 1948.
Haiyun He, Yepeng Liu, Ziqiao Wang, Yongyi Mao, and Yuheng Bu Theoretically grounded framework for IIm watermarking: A distribution-adaative approach, 2025a. URL https://
arxiv. wrw. abs / 2410.412200 02890
Weiqing He, Bojian Hou, Tianqi Shang, Davoud Ataee Tarzanagh, Qi Long, and Li Shen. Sefd: Semannic-enhanced framework for detecting IIm-generated text. 2024 IEEE International Conference on Big Data (BigData), pp. 1309-1314. IEEE, 2024a.
Weiqing He, Xiang Li, Tianqi Shang, Li Shen, Weijie Su, and Qi Long. On the empirical power of goodness-of fit tests in watermark detection. The Thirty-nini Annual Conference on Neural Information Processing Systems, 2025b.
Zhenyu He, Zexuan Zhong, Tianle Cai, Jason Lee, and Di He. Rest: Retrieval-based speculative decoding, In Proceedings the 2024 Conference the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers), pp. 1582 1595, 2024b.
Zhengmian Hu and Heng Huang. Inevitable trade-off between watermark strength and speculative sampling efficiency for language models. In Neural Information Processing Systems, 2024. URL
https: /ttpp:://opnnrview net/ corormmiii 6YKMBUiIsCC
Zhengmian Hu, Lichang Chen, Xidong Wu, Yihan Wu, Hongyang Zhang, and Heng Huang. Unbiased watermark for large language models. In International Conference on Learning Representations, 2024. URL https::////. /ttp:::///pprr//// ew nwt. www.rett/oorum22oowwovrrr.r

---

Published as a conference paper at ICLR 2026
Baihe Huang, Banghua Zhu, Hanlin Zhu, Jason Lee, Jiantao Jiao, and Michael Jordan. Towards optimal statistical watermarking, In Socially Responsible Language Modelling Research, 2023.
URL httppp://ppeneeeeee..eeeeste htte///ormmm.// setprruummddFeeeeeee htw.:///w.waaa...oooooooooo.r.aa
Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparameterrization with Gumbel-Softmax. In International Conference on Learning Representations, 2016.
Sehoon Kim, Karttikeya Mangalam, Suhong Moon, Jitendra Malik, Michael W Mahoney, Amir Gholami, and Kurt Keutzer. Speculative decoding with big little decoder. Advances in Neural Information Processing Systems, 36:39236-39256, 2023.
John Kirchenbauer, Jonas Geiping, Yuxin Wen, Jonathan Katz, Ian Miers, and Tom Goldstein. A watermark for large language models. International Conference on Machine Learning, volume 202, pp. 17061-77844 2023.
John Kirchenbauer, Jonas Geiping, Yuxin Wen, Manli Shu, Khalid Saifullah, Kezhi Kong, Kasun Fernando, Aninuddha Saha, Micah Goldblum, and Tom Goldstein. On the reliability of watermarks for large language models. In International Conference on Learning Representations, 2024. URL https::/openzreviee net/ wwr.foormm?ii -d-DE-J-DDDWWW
Rohith Kuditipudi, John Thickstun, Tatsunori Hashimoto, and Percy Liang. Robust distortion watermarks for language models. Transactions Machine Learning Research, 2024. ISSN 2835-8856. URL wtR..htts:/// http://ss./ppeeeeeeee....ot
http://pppeeeeeeeeeeeee net. forum? i
Yaniv Leviathan, Matan Kalman, and Yossi Matias. Fast inference from transformers via speculative decoding. In International Conference on Machine Learning, pp. 19274-19286. PMLR, 2023.
Xiang Li, Feng Ruan, Huiyuan Wang, Qi Long, and Weijie J Su. A statistical framework of watermarks for large language models: Pivot, detection efficiency and optimal rules. The Annals of Statistics, 53(1):322-355 2025.
Xiang Li, Feng Ruan, Huiyuan Wang, Qi Long, and Weijie Su. Robust detection of watermarks in large language models under human edits. To appear in Journal of the Royal Statistical Society: Series (Methodological), 2025+.
Yuhui Li, Fangyun Wei, Chao Zhang, and Hongyang Zhang. Eagle: Speculative sampling requires rethinking feature uncertainty. In International Conference Machine Learning, pp. 28935-28948. PMLR, 2024.
Xiaoxuan Liu, Lanxiang Hu, Peter Bailis, Alvin Cheung, Zhijie Deng, Ion Stoica, and Hao Zhang Online speculative decoding. In International Conference on Machine Learning, pp. 31131-31146, PMLR, 2024.
Yepeng Liu and Yuheng Bu. Adaptive text watermark for large language models. In International Conference Machine Learning, 2024. URL httphtttt////m httt:p:://ppnreviiie net forum? iid=
7em0Sb5JfX
Chris J Maddison, Daniel Tarlow, and Tom Minka. A sampling. In Advances in Neural Information Processing Systems, volume 27, 2014.
Xupeng Miao, Gabriele Oliaro, Zhihao Zhang, Xinhao Cheng. Zeyu Wang, Zhengxin Zhang, Rae Ying Yee Wong, Alan Zhu, Lijie Yang, Xiaoxiang Shi, et al. Specinfer: Accelerating large language model serving with tree-based speculative inference and verification. In Proceedings of the 29th ACM International Conference Architecturll Support for Programming Languages and Operating Systems, Volume pp. 932-949, 2024.
Silvia Milano, Joshua A McGrane, and Sabina Leonelli. Large language models challenge the future of higher education. Nature Machine Intelligence, 5(4):333-334, 2023.
Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. Journal of Machine Learning Research, 21(1):5485-555 5551, 2020.
R Tyrrell Rockafellar. Convex analysis, volume 28, Princeton university press, 1997.
12

---

Published as a conference paper at ICLR 2026
Vinu Sankar Sadasivan, Aounon Kumar, Sriram Balasubramanian, Wenxiao Wang, and Soheil Feizi. Can Al-generated text be reliably detected? arXiv preprint arXiv:2303.11156, 2023.
Ilia Shumailov, Zakhar Shumaylov, Yiren Zhao, Nicolas Papernot, Ross Anderson, and Yarin Gal. AI models collapse when trained on recursively generated data. Nature, 631 2024.
Benjamin Spector and Chris Re. Accelerating Ilm inference with staged speculative decoding. arXiv preprint arXiv:2308.04400 2023.
Kate Starbird. Disinformation's spread: Bots, trolls and all of us. Nature, 571(7766):449 450, 2019.
Mitchell Stern, Noam Shazeer, and Jakob Uszkoreit. Blockwise parallel decoding for deep autore- gressive models. Advances in Neural Information Processing Systems, 31, 2018.
Ziteng Sun, Ananda Theertha Suresh, Jae Hun Ro, Ahmad Beirami, Himanshu Jain, and Felix Yu. Spectr: Fast speculative decoding via optimal transport. Advances in Neural Information Processing Systems, 36:30222-30242, 2023.
Gemma Team, Thomas Mesnard, Cassidy Hardin, Robert Dadashi, Surya Bhupatiraju, Shreya Pathak, Laurent Sifre, Morgane Rivière, Mihir Sanjay Kale, Juliette Love, et al. Gemma: Open models based on Gemini research and technology. arXiv preprint arXiv:2403. 08295, 2024.
Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Amm Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al. LLaMA: Open and efficient foundation language models. arXiv preprint arXiv:2302 2023.
Dor Tsur, Carol Xuan Long, Claudio Mayrink Verdun, Hsiang Hsu, Haim Permuter, and Flavio Calmon. Optimized couplings for watermarking large language models. arXiv preprint arXiv:2505.08878, 2025a
Dor Tsur, Carol Xuan Long, Claudio Mayrink Verdun, Sajani Vithana, Hsiang Hsu, Chun-Fu Chen, Haim H Permuter, and Flavio Calmon. Heavywater and simplexwater: Distortion-Fis Ilm watermarks for low-entropy distributions. In The Thirty-ninth Annual Conference on Neural Information Processing Systems, 2025b.
Laura Weidinger, Jonathan Uesato, Maribeth Rauh, Conor Griffin, Po-Sen Huang, John Mellor, Amelia Glaese, Myra Cheng, Borja Balle, Atoosa Kasirzadeh, et al. Taxonomy of risks posed by language models. In Proceedings of the 2022 ACM conference on fairness, accountabiliry, and transparency, pp. 214 229, 2022.
Yihan Wu, Zhengmian Hu, Junfeng Guo, Hongyang Zhang, and Heng Huang. resilient and acces- sible distribution distributioon-rrseeviii preserving watermark for large language models. In International Conference Machine Learning, pp. 33443-53470 PMLR, 2024.
Heming Xia, Tao Ge, Peiyi Wang. Si- Si-Qing Chen, Furu Wei, and Zhifang Sui. Speculative decoding: Exploiting speculative execution for accelerating seq2seq generation. In Findings of the Association for Computational Linguistics: EMNIP 2023, pp. 3909-3999 2023.
Heming Xia, Zhe Yang. Qingxiu Dong, Peiyi Wang, Yonggi Li, Tao Ge, Tianyu Liu, Wenjie Li, and Zhifang Sui. Unlocking efficiency in large language model inference: comprehensive survey of speculative decoding. In Findings of the Association for Computational Linguistics ACL 2024, pp. 7655-7671, 2024.
Yangxinyu Xie, Xiang Li, Tanwi Mallick, Weijie Su, and Ruixun Zhang. Debiasing watermarks for large language models via maximal coupling. Journal of the American Statistical Association, pp. 1-21, 2025.
Han Xu, Jingyang Ye, Yutong Li, and Haipeng Chen. Can speculative sampling accelerate react without compromising reasoning quality? In The Second Tiny Papers Track at ICLR 2024, 2024. URL htt.htttps::/ppeeeeviii
net. forum? 42dm2mdd222bbrrrrr
Sen Yang, Shujian Huang, Xinyu Dai, and Jiajun Chen. Multi-candidate speculative decoding. arXiv preprint XXXv:22411006700 2024.
13

---

Published as a conference paper at ICLR 2026
Ming Yin, Minshuo Chen, Kaixuan Huang, and Mengdi Wang. A theoretical perspective for speculative decoding algorithm. Advances in Neural Information Processing Systems, 37:128082- 128117, 2024.
Xuandong Zhao, Prabhanjan Vijendra Ananth, Lei Li, and Yu-Xiang Wang. Provable robust water- marking for Al-generated text. In International Conference on Learning Representations, 2024.
URL BRRLLtttp///peeneeviee net/ httpp//www......eeooooooooeaeaaa 2
Xuandong Zhao, Lei Li, and Yu-Xiang Wang. Permute-and-Fiin An optimally robust and watermark- able decoder for LLMs. In The Thirleenth International Conference Learning Representations, 2025.
Yongchao Zhou, Kaifeng Lyu, Ankit Singh Rawat, Aditya Krishna Menon, Afshin Rostamizadeh, Sanjiv Kumar, Jean-Franceois Kagy, and Rishabh Agarwal. Distillspec: Improving speculative decoding via knowledge distillation. CoRR, 2023.
14

---

Published as a conference paper at ICLR 2026
A
RELATED WORK
Speculative sampling. major challenge in deploying large language models (I.LMs) lies in the high inference latency caused by autoregressive decoding, where tokens generated one by one. Speculative sampling (also referred to as speculative decoding) has emerged as a powerful strategy to mitigate this bottleneck by adopting draft-then, Shrify paradigm (Stern al. 2018 Xia et al. 2023 Leviathan et al. 2023 Chen et al. 2023).
Recent advances have expanded this paradigm through diverse improvements. Some works improve drafting strategies, including independent drafters trained via knowledge distillation (Zhou et al.
2023 Miao et al., 2024 Liu al. [2024] Kim et al.
2023). and self-drafting methods that reuse
parts of the target model, such as Medusa (Cai et al.
2024) and EAGLE (Li et al., (024)). Others
explore verification mechanisms, extending beyond sigleecandidate check to multi-candidates or tree-structured verification (Yang ct al. [2224 Miao et al.
2024 Spector & Re [023 Sun et al. 2023
He al. 2024b Cai al., 2024 Li et al.) 2024). Collectively. these innovations have produced
Pareto improvements in both acceptance rate and throughput (Xia et al., 2024).
Our work builds on this growing body of research but explores a new dimension: how speculative sampling interacts with watermarking. Thus, in this work, we focus on the basic speculative sampling method. Importantly, our approach does not rely on any assumptions about the draft or target models, which means the underlying idea can naturally extend to more advanced variants.
Watermarking techniques. Recent studies have proposed diverse set of watermarking schemes (Kirchenbauer et al., 2024 Fernandez et al. 2023 Kuditipudi et al. 2024: Hu et al.
2024 Wu et [024 Zhao et al., 2025| [024] Liu & Bu 2024| | Giboulot & Teddy, 2024 Fu
et al. 2024| Xie al. 2025; Dathathri et al. 2024 He et al. 2025a). Most approaches operate by
introducing pscudorandomness into the next-token prediction process, so that the randomness once seeded-creane statistical patterns that later be detected to verify the presence of water- mark. Besides, recent works have also studied watermarking from an iiformation-thhoreee optimization-based perspective design stronger watermark schemes (Tsur et 2025a b). Impor- tantly, a watermarking decoder is called unbiased when its token distribution remains identical to the underlying token distribution (He al. 20256
and
et al. 2025).
Our work focuses on the unbiased watermark and formally quantifies the watermark strength. Building on this foundation, we revisit the trade-off between sampling efficiency and watermark strength identified by Hu & Huang (2024), and improve this trade-off by extending the one-dimensional pseudorandom seed in traditional watermarks into multi-dimensional design.
B PROOF FOR SECTION 3
B.1 PROOF THEOREM
3.1
Proof of Theorem 3.7 Under H1, the random variables Zi,..., Zn are independent, with ER, [Z,] = D. = Ex, [DRL (Prc. [P.]]. Let An Σi= Ze and define the empirical average D, := I E D... By assumption, D, + D as n - co. Since the Ze are independent with bounded
moments, the weak law of large numbers gives:
An D. D, under H1
Let Aghs := A, denote the observed log- likelihood ratio under H1, and define the p-value pval,, PHo (A,, 2 Aghh)
To evaluate this, we apply the non-i.id. version of Cramér's theorem (e.g., Section 2.6 in (Durrett) 2013)). ). Define the averaged log moment generating function under Ho:
72
log E.oo 20
and the corresponding rate function:
(x) = sup (sx 2/ (s))
sER
15

---

Published as a conference paper at ICLR 2026
Lemma B.1 (Uniform control of log- log-MGFs). Let {Zi 1i11=1 be independent random variables such
that for some constant M >> 0, each Z, satisfies Zg S M almost surely. Define the log- temomnnet generating fimetions (r(s) log E ()) and their average (n(s) := -x= (s). Then:
1. For any compact interval K C R, we have supisn,xe, SEK (5)( X0.
2. v (s) converges uniformly on compact intervals to limiting corvex function (b(s).
3. The corresponding sequence of convex conjugates Ln(x) == sup,eR ( converges pointwise [(x) sup,ER {sx vb(s))
(n(s)}
By Lemma B.1
the sequence (1/, (8)} of averaged log-MGFs is uniformly controlled, and the
corresponding rate functions (.) converge pointwise limiting convex function T(.). Hence, the non-i.id. version of Cramér's theorem applies to the sum An Σm= Ze and large deviation principle holds with rate function (-)).
Since A = nD + (n) under H1, the large deviation estimate gives:
PHo (An z A = (ep(-nI,,(D) + o(n)).
By Lemma B.1
have I (D) (()) - oc. Moreover, because each Z, is log-likelihood
ratio satisfying EH [e?t] 1, the rate function achieves its maximum at = 1, implying that:
I(D) = D.
Therefore,
log pval,
in probability under H1,
m
which implies that
pval, exp(-nD =exp(=nD++(1)) o(n)).
To guarantee pval, S it is necessary that
n log ()) (1 (1+ o(1))
exp(-nD o(n)) sa
D
a
This completes the proof.
We conclude by providing the proof of Lemma B.1 below.
Proof of Lemma
B.
Since
Zzl S M almost surely, for any E IR we have
e M|ss c S M1
which implies that the moment generating function Z[ exists and is bounded by Miel for all and E R. In particular, for any compact interval K C R, there exists a constant CK < oc such that
sup sEK
[W((s)]=
sup tSn, tsn,eE SEK
log Ele 21]] < Ck-
This proves the first part.
Next, observe that each (*) convex (as the log of an MGF) and differentiable. Moreover, since IZel < M, we have
e Z
ds (x))
S M,
E.
so each (s) Lipschitz continuous with Lipschitz constant at most M on E. Hence, the sequence v (s) is equicontinuous and uniformly bounded on compact sets. By the Arzelà-Ascoli theorem, the sequence (s) has a uniformly convergent subsequence on each compact interval. Since the pointwise limit
(s)) = lim vh (s)
n000
16

---

Published as a conference paper at ICLR 2026
exists by the law of large numbers, conclude that the convergence is in fact uniform compacts. This proves the second part.
Finally, since each (s) is convex and converges uniformly compact sets to convex function
(s)),, the corresponding convex conjugates (rate functions) (x) == sup,e {st th, (s)} converge pointwise (xx == sep fsx- (s)) by standard results from convex analysis (e.g.. Rockafellar's
theorem on epi-convergence of convex conjugates (Rockafellar 1997)). This proves the last part. 0
B.2 PROOF OF THEOREM
Proof of Theorem 3.2
By definition,
Pw.C Ent(P) - Eş (c([Ent(P:)) & Ent(P).
WS(P;) = Ee E Σ Su.g log
P
W
When the equality holds, we must have E, [En((P()] 0 that Ent( 0 for any Ç.
B.3 PROOF THEBRREM
Proof of Theorem 3.3 The decoder for the Gumbel-max watermark is deterministic and always produces degenerate distribution. Therefore, it trivially achieves the maximum watermark strength.
We now prove the result for the SynthlD watermark. Recall that the m-layer decoder is defined in 33: (P),
(P.C) Tg..
where each To is vectorized operator defined by
(P))))) = Pw Iw
Σ Pw
w':9w/= =1
A direct calculation shows that this transformation preserves expectation:
Tg
(13)
Let us define
P. := To T (P),
and let F, == o (g be the sigma-field generated by all pscudorandom masks up to layer t. By construction and the unbiasedness (1). we have
E[P. Fi-I P
This shows that the sequence (P.) forms non-negative, vector-valued martingale adapted the filtration {Ft). Moreover, each P; is valid categorical distribution.
By the martingale convergence theorem (e.g., (Durrett 2013, Section 5.2)), the sequence Pr converges almost surely to a limiting distribution, which we denote by P. We assert that P must be fixed point of the operator Tg for every possible value of due to the above almost sure convergence. By the definition (4) this is only possible if P assigns mass to a single token-that is, is degenerate. If this were not the case, then applying Tg would change the distribution for some choices of Therefore, the SynthID decoder also converges to a degenerate distribution and achieves maximum watermark strength. This completes the proof.
B.4 PROOF OF LEMMA 3.1
Proof of Lemma
3.7
We first prove the first part. For any fixed Ç. we can write
Pe Σ Ac(w' [ww
WEW
In particular, this implies
Pewer Ac(wo' w')Qq,""
17

---

Published as a conference paper at ICLR 2026
Pewe Qc,00
Ac(w' w')
Aç(w' | ww' 1Qs S Qg,w! min Ps.e
Qe,w
Summing over w' W, obtain
Σ Ac(w wo v0))Qq
Qsw min (1.p
Pe.er
Σ
min (Qu,r, Pc,w)
w e'ew
w' N'EW
WEW
Therefore, the sampling efficiency satisfies
SE(
IE
Σ W
min (Q P(.w)
Finally, note that equality holds when A
Aspec (Qc, Pc), completing the proof of the first part.
For the second part, we note that the total variation distance satisfies the following characterization:
TV P)
inf (P Y): X ~ Q, P)
where the infimum is taken over all couplings (X, Y) such that their marginal distributions are Q and P. respectively. Let Ag Aspec Qg. Pç). Since (X, Y) (Qç. A Q;) forms a valid coupling of Q and P.
TV(Q, P) S (X # (X,,) ~ (Qc, Qc))
= - - Eql Σ (g(w/ww)Cc.0
wEW
SE(Q Aspec QQc: Pc)) (SE(Q Pc).
C EXAMPLES OF TRADE-OFF CURVES
C.I SIMULATION SETUP
To get the numerical result of the trade-off curves, we manually specify 10-dimensional token distri- butions for the draft and target models:
Q (0.4, 0.10. 0.12, 0.11, 0.08, 0.06, 0.05, 0.035, 0.025, 0.02)
P (0.1, 0.13, 0.155, 0.115, 0.235, 0.065, 0.055, 0.05, 0.06, 0.035)
These distributions mimic common pattern observed in practice: the draft model Q concentrates more probability mass on a single token, whereas the target model exhibits higher entropy. Although the actual vocabulary size in LLMs is far larger than 10, in practice most of the probability mass is concentrated on a small set of high-probability tokens. This is consistent with the intuition behind top-k sampling, where only handful of tokens dominate the distribution. Thus, while simplified, our simulation setting captures the essential structure of real-world scenarios.
To approximate expectations without simple closed-form expression (e.g., sampling efficiency), employ Monte Carlo estimation using 10" pseudorandom seeds and report the resulting empirical mean.
Implementation of SynthID (m = co). According to Thm. 3.3 the SynthlI decoder converges almost surely to a degenerate distribution as the tournament rounds m - oc. In practice, however, observe that at = 30, the distribution is
we cannot really set to infinity. Empirically, already highly concentrated on a single token, though not yet fully degenerate. By the convergence guarantee, the remaining probability mass will collapse onto this token as increases further. Thus, in implementation, we approximate the limit distribution by constructing one-hot vector for that token.
18

---

Published as a conference paper at ICLR 2026
C.2 OTHER WATERMARKED CLASSES
In Section 3.2 we used the linearly watermarked classes 4 as a simple example to illustrate trade- off curves. More generally, different choices of the watermarked classes Qdraft and Quarget yield different curves. These choices can be highly customized, highlighting the flexibility and scalability of our framework.
Here, we detail the classes used in the right part of Fig. We begin with the transition kernel from (Dathathri al. 2024):
min (1,
Puu
if aw w.
Qu
Ag ((ol w') = (((P-)) () (w))
(14)
Pwr Q
if w * w.
where (P Q)++ denotes the normalized excess mass of P over Q and S is an unbiased decoder. We denote this kernel as As P). Importantly, given the independence of Ç and ç, we have
(Ac P) Qc] P (Dathathri et al. 2024). By Remark 3.2 this transformation can be treated as an unbiased decoder, denoted Sgoogle P.S.E) := = P)oQ. We then define Google's
class Dathhthhii et al. 2024)
Odraft {Sarafe),
Quarget {(1 - 7) 7 Starget Y E [0, 1]}.
Similarly, we denote Shu (P, Aspec (Q, P) Q₂ and define Hu's class (Hu & Huang 2024 as:
Qdraft {Sdratt) Qtarget {(1 S) + Starget : 7 E [0. 1]}.
In both cases, Saraht and Starget denote prescribed unbiased decoders (e.g., Sgum or S in our experiments). In the above definition, the draft decoder is fixed, and the target decoder is controlled solely by the variable y. Hence, by simply iterating over y and applying Monte Carlo estimation, we compute the sampling efficiency and watermark strength for each value and plot the corresponding trade-off curve.
D PROOF OF THEOREM 4.1
Proof of Theorem 4.7 We first show (a). For Alg. tokens can be generated in two cases. Case 1: The token is sampled from the accept and reject loop on lines 7 to 14 By definition,
(w)) = ( G(S (iin)<m Q(())
P(w)
(15)
+
1 (co (w) G(CR) G(cR) WEW
P(w) Q(w))
(P Q)+cr(())
The first term corresponds to the probability of sampling w from the draft model and accepting it. The second term corresponds the probability of rejecting any token from the draft model, then sampling w from the residual distribution. Since the watermark decoder S is unbiased, we have,
E Q [)] E(T( and and [[P - Q)+xrl = =(P Q)+
By the definition of G) we also have,
min {
P(w) Q(w)
P(w) B ((gg))mmi() arw <min(1
Since S" and ςa are independent, it then follows that,
P(w) Eç=(5P R3=(5 (P((w)) Q(w) min { 1, Q(w))
+ 1 +(1- Σ Qww) min (1, श(क) } (P (w))
WEW
19

---

Published as a conference paper at ICLR 2026
This expression is equal to the probability distribution of the next token generated by standard speculative sampling, and Chen et al. (2023) has shown it is equal to the target distribution P(w).
Case 2: The token is sampled from Per (e.g., the bonus step on line I6]. Since S is unbiased, we also have P(rr = P. Thus we prove the unbiasedness.
We then show (b). From Alg. 1 we find that the self-transition probability is Ac(w w)) (G(("))cmmi(..P(oo)(a))) Hence, by Def. 2.1
SE(Q,o,, Ac) B 57.55)))
Σ (e
wEW
Σ weW
Qc (w) locc))
Σ wEW
Ee Qpp) E (locc")cmii(llPP////100
min {
P(w) Q(w)
Σ Q(w)
TV.
wEW
where independence of ςD and ç used in the third equality. Thus, Alg. can preserve the sampling efficiency.
Finally, we show (c). Recall from the proof of (a) that there are two cases. Case The expression of P/ is given by 15 Since S achieves the largest watermark strength, we have QT S(Q,5") as degenerate distribution. then follows that
(((w)= = Qco - aa(e)) (i
(P +(P +
Q)+.cr((u)) 1 G(c*) ((=))
where w' is the token sampled by Qę Moreover, (P - +)+ CT is also degenerate, which implies that P'C is always degenerate and that (S = Ent ( P). Case 2: Per is itself degenerate.
Therefore, in both cases, the final distribution produced by Alg. 1 iss always degenerate, and hence the watermark strength is preserved.
E BAYESIAN SCORING FUNCTIONS FOR SYNTHID
Here we introduce the details of the Bayesian scoring function mentioned in Section 4.2
For a given
text, we have two hypotheses: unwatermarked (H₂) and watermarked (H₂). Our target to estimate the posterior P(H1 ly y" u). which is the probability that the text is watermarked given its g-values and acceptance variable. Formally,
F(H, , olog of u) - -log P(yP, ".p" Ho, u)
(16)
+ +og u) log P(Ho u))
where (-)) is the sigmoid function. There two terms that need be estimated in equation 16 First, the prior TP( u). which can be learned empirically. Actually, u does not influence the existence of the watermark. so PHH, u) IP(H)) (also P(H u) (H)))) which is the prior probability that a text is watermarked (or not). Following the setting in Dathathri et al. (2024), we set this prior to 0.5 in our experiments. Second, the likelihood P(y y 71, u) and F'y y Ho, u). To illustrate, we fix step and tournament layer I. Due to the independence across tokens and layers, once the odds are determined for fixed step and layer, they can be multiplied to obtain the odds for the entire sequence. Recall that for step I, we denote uP = (of, (wx),... ... ... (wx)) E R with corresponding definition for yf" For notational simplicity, write of 9h. (w,). The unwatermarked likelihood is then given by
Plg of. Ho, u.) (2(oP))
20

---

Published as a conference paper at ICLR 2026
where fg denotes the probability mass function of the g-value. In setting, g-values follow (0.5, so fg = 0.5. For the watermarked likelihoods, we have:
N. H1, u))
E
P(g. ghd G: = 5t H1, ue) P(G: = 5 H1, uz)
NE(D,T)
=P(ge CZ lq
P(G. = -P- |4)
(17)
+ + 55 (7) fo(o))) (1 1(P = C." ui)
where Çi = C. indicates that the token at step was watermarked with pseudorandom seed ÇD. Two terms in equation 17 require estimation. First, P(C. = -PP] we). which means given the acceptance variable, the probability that the token comes from the draft. Second, P(af, & - which is the likelihood of the g-values under a specific pscudorandom seed. Following Dathathri et al. (2024). when SynthID employs two-sample tournament sampling, we can factorize P( Se and then have,
PP 96.1 | H1, u4) P(g G = <=- P(G GP (44)
PP(92. Ge (o (1 P((e = = (u))
- P( =2 s PP(G = cPP uz)
+ + -) = gf (1- P(G. = <P uc))
where 1iz, is random variable denoting the number of unique tokens appearing in the tournament match at layer I and step I. We model PP(y = 2 x( using logistic regression:
P ( = st = (3 + Eo &ig
j=1
where o()) is the sigmoid function. Here, O IR is the bias term for layer I, and 87,- H represents the influence of Sh, on the probability that vr,,, = 2. The remaining term to estimate IP = <P' ue). Without access to the acceptance variable. Dathathri al. (2024) treats this probability as prior, estimated directly from the acceptance rate of speculative sampling; we refer to this approach as Bayes-Prior. our method, we leverage the acceptance variable and train three-layer MLP to perform the estimation:
(a(a(T -u)() for training, for inference,
PC: = sP ue)
Lu.gT
where (.) the sigmoid function, a is scaling parameter, and T = MLP(x.) with input 24 = (9......../ - 97.30 8 We denote method Bayes-MLP.
In summary, Bayes-Prior relies solely on the g-values for detection:
Bayes-Prior(y" y²) = P(H, vP,y")
whereas Bayes- MLP additionally incorporates the pseudorandom variable w: Bayes-MLP(y) yT, 2) = P(H, y yy u),
with p VT E m and E N, where denotes the token sequence length.
F EXPERIMENT DETAILS AND RESULTS
F.1 IMPLEMENTATION DETAILS
Implementation of Ars-T, In Section 4.2 we introduced the use of the pseudorandom variable and proposed Ars-T for the Gumbel-ma max watermark. Recall that the selection rule for Ars-r is defined as
yt = v2 Jac))rr vt 1ac8
21

---

Published as a conference paper at ICLR 2026
where [0, 1]. To determine the optimal т, adopt straightforward approach: on the training set, we evaluate 100 evenly spaced values of I over [0, 1] and select the one that performs best, which then applied to the test set.
Implementation of Bayes-MLP. Details are provided in Appendix
F.2 ADDITIONAL EXPERIMENTAL RESULTS
0.8
Gumm bai-maxx
SynthlD
Gumbel-max
3.5
SynthlD
0.6
Std. SpecSampl.
2.5
0.4
2.0
0.4
Bayes-MLP
0.2
Prior
Bayes Prior
Oracle
0.2
Dracie
1.0
K-2
K=3
K=4
50
100
150
200
100
150
200
Lockahead Length
Number of Tokens
Number of Tokens
Figure 3: Experimental results for Gemma models on the ELI5 dataset. Left: Average Accepted Tokens Per Step (AATPS) of Alg. applied to the Gumbel-max and SynthlI watermarks, compared with Standard Speculative Sampling (Std. SpecSampl). Error bars mark the 95% confidence intervals. Middle and Right: Watermark detectability (TPR FPR 1%) for Alg. on the Gumbel-max (middle) and SynthID (right). Orange curves show our method, blue curves show the prior-based method, and black curves represent the ideal detector (Oracle) that always selects the correct test statistic. Shaded regions indicate the 95% confidence intervals.
Table 1: Results of Alg. applied the Gumbel-max and SynthII watermarks the ELI5 dataset, compared with Standard Speculative Sampling (Std. SpecSampl.) and basic watermarks. AATPS: Average Accepted Tokens Per Step; PTT: Per Token Time in millisecond; LOGPPL: Log Perplexity.
Models
Lookahead
Method
AATPS
PTT
LOGPPL
Liana "I LLLLmaaaa 68m
basic
Gumbel-max
1.0 + 0.0
22.09 + 0.151
2.08 + 0.024 2.10 0.017
SynthID
1.0 1.0=00 0.0
44.94 0.477
Gumbel-max
1.7707 + 0.0058
17.04 +.04+00111 0.121
2.16 0.025
K
SynthII
1.7645 0.0042
+ 0.411
2.12 0.014
Std. SpecSampl.
1.7666 0.0099
14.98 0.167
2.18 0.023
Gumbel-max
1.9650 0.0082
1.100
2.14 0.024
K
SynthID
1.9584 0.0066
40.75 0.554
+.011
Std. SpecSampl.
1.9577 0.0070
4.055
2.07 1 0.022
Gumbel-max
2.0987 0.0095
17.96
2.16 0.024
K =4
SynthID
2.0927 0.0078
11.74 0.658
2.15 + 0.014
Std. SpecSampl.
2.0988 + 0.0094
15.56 + 0.074
2.19 + 0.022
Gumbel- mmx
1.0 0.0
29.20 + 0.072
1.79 + 0.053
basic
SynthID
1.0 + 0.0
41.32 + 0.179
1.69 + 0.037
Gemma- Geatna-
Gumbel-max
2.3637 0.0085
25.98 + 0.175
1.69 + 0.055
K ==2
SynthID
2.3794 0.0089
38.10 + 0.522
1.74 + 0.036
Std. SpecSampl.
2.3773 0.0080
22.74 + 0.082
1.66 0.057
Gumbel-max
2.9146 0.0144
26.83 1 0.204
1.75 1 0.053
K= =
SynthID
2.9108 0.0142
35.62 1 0.291
1.75 0.035
Std. SpecSampl.
2.9140 0.0140
23.84 - 0.121
1.69 + 0.051
Gumbel-max
3.2923 0.0203
28.94 1 0.245
1.75 0.052
K
SynthID
3.2920 0.0190
41.06 1 0.444
1.73 1 0.037
Std. SpecSampl.
3.2930 = 0.0213
26.05 + 0.179
1.72 0.053
22

---

Published as a conference paper at ICLR 2026
1.0
0.9
0.9
0.8
True Positive Rate
True Positive Rate
0.8
0.7
0.7
0.6
0.6
0.5
Ars-T
0.5
Ars-T
Ars- irs-rrior
0.4
0.00
0.02
0.04 0.06 0.08 0.10
0.00
0.02
0.04
0.06 0.08 0.10
False Positive Rate
False Positive Rate
Gumbel-max on Ll amamm models.
Gumbel-max on Gemma models.
1.0
1.0
0.9
True Positive Rate
True Positive Rate
0.8
0.8
0.6
0.7
0.4
0.6
0.5
Bayes-MLP
0.2
Bayes-MLP
Bayes-Prior
Bayes-Prior
0.0
0.05
0.10
0.00
0.05
0.10
False Positive Rate
False Positive Rate
SynthID on Llamma models.
SynthlD on Gemma models.
Figure 4: ROC curves for watermark detection on the ELI5 dataset. Gumbel-max performance is evaluated at a token length of 200, while SynthID performance is evaluated at token length of 100. Orange curves show our method, and blue curves show the prior-based method.
Guim
1.0
SynthlD
Gumbel-max
2.5
SynthID
0.8
Std. SpecSampl.
PPR
0.6
AATPS
2.0
TPR3F
0.6
1.5
ArS-T Ars-Prior
Bayes-MLP
0.2
Bayes-Prior Oracle
0.2
1.0
K-2
K-3
K-4
0.0
50
100
150
200
50
100
150
200
Length
Number Takens
Number Tokens
Figure 5: Experimental results for Llam models on the C4 dataset. Left: Average Accepted Tokens Per Step (AATPS) of Alg. [Tpplie to the Gumbel-max and SynthID watermarks, compared with Standard Speculative Sampling (Std. SpecSampl). Error bars mark the 95% confidence intervals. Middle and Right: Watermark detectability (TPR at FPR = 1 1%) for Alg. Do the Gumbel-max (middle) and SynthID (right). Orange curves show our method, blue curves show the baser method, and black curves represent the ideal detector (Oracle) that always selects the correct test statistic. Shaded regions indicate the 95% confidence intervals.
23

---

Published as a conference paper at ICLR 2026
4.0
1.0
SynthlD
Gumbel-max
3.5
SynthiD
TPRGERR 1%6
0.8
SpecSampl.
3.0
TPR@FFR
0.6
2.5
0.6
0.4
Ars
0.4
Bayes-MLP
0.2
Ars-Prior Oracle
Bayes-Prior Oracle
1.5
1.0
K-2
K-4
50
100
150
200
0.2
50
100
150
200
Lookahead Length
Figure 6: Experimental results for Gemma models on the C4 dataset. Left: Average Accepted Tokens Per Step (AATPS) of Alg. applied to the Gumbel-mar mmx and SynthID watermarks, compared with Standard Speculative Sampling (Std. SpecSampl). Error bars mark the 95% confidence intervals. Middle and Right: Watermark detectability (TPR at FPR 1 1%) for Alg. on the Gumbel-max (middle) and SynthII (right). Orange curves show our method, blue curves show the prior-based method, and black curves represent the ideal detector (Oracle) that always selects the correct test statistic. Shaded regions indicate the 95% confidence intervals.
1.0
0.9
0.8
True Positive Rate
0.9
True Positive Rate
0.7
0.8
0.6
0.7
0.5
0.6
Ars-T Ars-Priar
0.4
Ars-T
Ars-Prior
0.5
0.3
0.00
0.02
0.04
0.06 0.08 0.10
0.00
0.02
0.04 0.06 0.08 0.10
False Pasitive Rate
False Positive Rate
Gumbel-max on Llanma models.
Gumbel-max on Gemma models.
1.0
1.0
True Positive Rate
0.9
True Positive Rate
0.9
0.8
0.8
0.7
0.7
0.6
Bayes-MLB MLP
0.6
Bayes-MLP
Bayes-Prior
Bayes-Prior
0.5
0.5
0.00
0.05
0.10
0.00
0.05
0.10
False Positive Rate
False Positive Rate
SynthID on Llamma models.
SynthID on Gemma models.
Figure 7: ROC curves for watermark detection on the dataset. Gumbel-ma -ax performance is evaluated at a token length of 200, while SynthID performance is evaluated at token length of 100. Orange curves show our method, and blue curves show the prior-based based method.
24

---

Published as a conference paper at ICLR 2026
Table Results of Alg. applied the Gumbel-max and SynthID watermarks on the C4 dataset, compared with Standard Speculative Sampling (Std. SpecSampl.) and basic watermarks. AATPS: Average Accepted Tokens Per Step; PTT: Per Token Time in millisecond; LOGPPL: Log Perplexity.
Models
Lookahead
Method
AATPS
PTT
LOGPPI.
Llama TTb LLlama 668m
basic
Gumbel-max
1.0 0.0
22.98 + 0.040
2.22 + 0.023 2.29 0.015
SynthII
1.0 1 0.0
40.27 + 0.307
Gumbel-max
1.8112 0.0080
17.65 + 0.062
2.21 1 0.023
K
SynthID
1.8228 0.0081
35.44 0.404
2.24 0.016
Std. SpecSampl.
1.8200 0.0071
16.01 + 0.044
2.28 1:28:00 0.023
Gumbel-max
1.9610 0.0099
17.70 1 0.070
2.22 0.025
K =
SynthID
1.9662 0.0106
39.62 1 0.532
2.25 1 0.015
Std. SpecSampl.
1.9663 = 0.0101
15.69 = 0.056
2.26 4
Gumbel-max
2.0836 0.0125
18.21 + 0.081
2.22 + 0.021
K = 4
SynthlD
2.0917 0.0135
39.48 + 0.672
2.24 0.015
Std. SpecSampl.
2.0847 0.0128
15.83 + 0.068
2.23 - 0.023
Gumbel-max
1.0 0.0
29.19 + 0.006
2.52 + 0.026
basic
SynthID
1.0 0.0
37.92 + 0.193
2.56 + 0.013
Gemma "Ib Gemma
Gumbel-max
2.3415 + 0.0077
25.67 + 0.061
2.53 + 0.026
K = 2
SynthID
2.3468 0.0070
35.61 + 0.396
2.58 0.014
Std. SpecSampl.
2.3427 0.0074
23.57 1 0.054
2.60 1 0.027
Gumbel-max
2.8473 0.0127
28.19 + 0.110
2.53 0.026
K =
SynthlD
2.8450 0.0119
33.14 0.441
2.59 + 0.014
Std. SpecSampl.
2.8442 0.0129
2.50 + 0.026
2.50 1 0.026
Gumbel-max
3.1529 0.0176
28.98 0.145
2.53 4
K =
SynthID
3.1499 = 0.0165
36.84 0.472
2.59 0.015
Std. SpecSampl.
3.1494 = 0.0164
26.61 + 0.100
2.60 + 0.027
F.3 THEORETICAL SPEEDUP VS. EMPIRICAL RUNTIMES
Both Average Accepted Tokens Per Step (AATPS) and Per Token Time (PTT) reported in Table reflect how much Alg. [
accelerates the generation process, but they capture different aspects of performance. AATPS measures the number of accepted tokens in each generation loop and thus reflects the theoretical speedup, focusing primarily on the draft token acceptance rate, to which Alg, I directly contributes. Ideally, higher acceptance rate leads to a greater overall speedup. contrast, PTT empirically measures the actual runtime of generation and can be affected by various factors, including (but not limited to) watermark sampling, token verification, and model switching (when using single GPU). Therefore, the observed speedup based on PTT may not perfectly align with that implied by AATPS. We do not further investigate this discrepancy, as it falls beyond the scope of this work.
G THE USE OF LARGE LANGUAGE MODELS (LLMs)
The LLMs were used solely to polish the writing, including grammar correction and improvements clarity and style. The research contributions, including the design methods, implementation, experiments, and analysis, were carried out entirely by the authors.
25


Reviews:
[{"review_id": "5D2niQL2pU", "reviewer": "Reviewer_4VEY", "summary": "This paper studies the trade-off between watermarking and speculative decoding. A relatively recent work had made a 'no-free lunch' observation, which shows that improving the watermark is at the cost of weakening the speculative decoding (acceptance rate), and vice versa. This paper challenges this observation by integrating the watermarking's pseduorandom mechanism into the speculative decoding mechanism. The paper studies the speculative-decoding and watermarking tradeoff and the resulting curves, proposes a method to 'break' these curves and presents some experiments, demonstrating the proposed method on the Gumbel and SynthID watermarks.", "questions": "Bellow are both questions and comments:\n\n- **Connection to (Hu & Huang 24) and the hypothesis test:** The difference from the results in (Hu & Huang 24). which is explained in Remark 3.1 is unclear to me. First, the comparison itself is a bit odd. The referred paper discusses asymptotic results of the hypothesis test, while this work (while not stating clearly) is a token-level mechanism. The notion of a sequence is not addressed at any stage of this work. Second, Both works quantify the watermarks strength (detection) through the KL between distributions. This is an immediate results from the error exponent of the hypothesis test. \n\n- Following the previous comment, as the authors consider the 'token-level' hypothesis test, the use of the KL divergence to quantify the distributional divergence seems a little odd. In the hypothesis testing context, and as noted in this paper, KL divergence emerges in an asymptotic analysis (Through the error exponent of the type-2 error in the equivalent independence the between the 'i.i.d.' tokens and the psuedorandom process). The setting that manifests the KL divergence doesn't seem to fit strongly in the proposed operational setting of this work. I would appreciate the authors' thoughts on that. I believe that the mentioned related works [1,2] might be highly impactful to address this issue.\n\n- The expected KL divergence in eqn (7) is a popular quantity in information theory termed 'conditional KL divergence' - I would use that standard notation.\n\n- I believe that the watermark transformation can be regarded as a transition kernel similarly to the speculative decoding mechanism. Is there a reason to not address is as one in this work?\n\n- Do the results of this work extend to the unbiased case? I would believe that the tilting mechanism in [2, Section 2] might come in handy as a formulation of 'removing bias'.\n\n- Is the proposed method applicable to a general new watermark or does a new solution should be tailored to each new watermark?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Overall, this is a solid and creative work. Here are some of its strengths:\n\n1. The paper is clearly written. Even though I have significant prior knowledge about both watermarking and speculative decoding I believe this paper will not be too hard to follow for a newcomer to these fields.\n\n2. The idea is novel and seemingly powerful. Furthermore, the authors address the combination of two important subjects in the AI community - trustworthiness and efficiency.\n\n3. The analysis is very interesting and creative! Reading this paper was really delightful.", "weaknesses": "### Major:\n\n- **Clarity on SynthID:** The paper uses SynthId as a case-study in this work, as it is an 'unbiased watermark'. However, SynthID is a relatively large class of watermarks that follow the tournament sampling mechanism. The general SynthID watermark is not even unbiased (when N>2). Unfortunately, the authors do not provide sufficient information to understand which specific case of SynthID is proposed in this work. I also believe that such information should be added for the sake of clarity.\n\n- **Missing related work:** The content of this paper misses several related works on 'unbiased' watermarks for better context, which can also be considered for the analysis and experiments. The first [1] considers a similar hypothesis test to the one that is considered int his work, however through the Bayesian setting. This work is highly relevant due to its analysis in the 'token-level', as considered in this work. Furthermore, the results of [1] are stated in terms of the total variation distance, which may lead to easier integration with the speculative-decoding analysis that is done in this work. Beyond that work, there are highly related work that is missing for context - [2] provides a general formulation in terms of score and watermark transform optimization, proposing methods that outperform the considered watermarks in this work. [3] studies optimality \n\n- **Experiments section should be extended.** I would expect this section to consider more experiments, through more datasets (testing across specific tasks/domains) and testing more aspects of watermarking (robustness?). The current collection is quite narrow. Furthermore, I would expect a quantification of the watermark strength through p-values and quantification of the bias (through either textual quality or cross entropy/relative perplexity). \n\n### Minor:\n- The title of section 3 \"COMPLETE THE TRADE-OFF DIAGRAM\" is not clear.\n\n[1] Tsur, D., Long, C. X., Verdun, C. M., Hsu, H., Permuter, H., & Calmon, F. P. (2025). Optimized Couplings for Watermarking Large Language Models. arXiv preprint arXiv:2505.08878.‏\n\n[2] Tsur, D., Long, C. X., Verdun, C. M., Vithana, S., Hsu, H., Chen, C. F., ... & Calmon, F. HeavyWater and SimplexWater: Distortion-free LLM Watermarks for Low-Entropy Distributions. In The Thirty-ninth Annual Conference on Neural Information Processing Systems.‏‏\n\n[3] He, Haiyun, et al. \"Universally optimal watermarking schemes for llms: from theory to practice.\" (2024).‏", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DN4JcSSNY1", "reviewer": "Reviewer_m26b", "summary": "This paper considers watermarking when speculative sampling is used. Their results seem modular, allowing for improved watermarking with speculative sampling by improving standard watermarking schemes and applying them to both the draft and target models. Making this optimal seems to require an interesting trick that (pseudo)randomizes acceptance. They appear to understand all the key points, like that this will not introduce new distortions if the watermarks for the two models are independent.", "questions": "Is Google's watermark really a deterministic function of pseudorandom numbers? I thought that tournament sampling doesn't satisfy this property at all: Doesn't it work by first sampling a few tokens, and then choosing deterministically between them? In which case, there's still a bunch of entropy left on the table in the initial sampling process.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The paper has several strong results. The basic observation, that one can overcome the limitation of Hu et al. by allowing for pseudorandom draft-token acceptance, is very nice and important. Watermarking under speculative sampling is an extremely important technical issue for deploying watermarks in real-world LLMs.\n\nI haven't read the paper carefully, but it seems to make real progress on an important practical question.", "weaknesses": "I don't know of any.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "VD6SypuVQi", "reviewer": "Reviewer_LCLc", "summary": "## Summary\nThis paper tackles a practical tension in LLM serving: **unbiased text watermarking** (for provenance) versus **speculative sampling** (for speed). Prior work framed this as a binary impossibility: you can either preserve the watermarked distribution or preserve the acceptance rate, not both. The authors (i) introduce a **quantitative notion of watermark strength** — the expected KL divergence $E_\\zeta[D_{KL}(P_\\zeta || P)]$ — and prove it is the **exact detection rate** (via Chernoff–Stein); (ii) cast watermark–efficiency trade-offs as a **Pareto optimization** and empirically map the curve for several watermark classes (Gumbel-max, SynthID, linear mixtures, prior classes); and (iii) propose a simple fix — **pseudorandomizing the accept/reject coin** in speculative sampling — so the whole decode becomes a deterministic function of seeds, achieving **maximum sampling efficiency** $1 - TV(Q,P)$ and **maximum watermark strength** $H(P)$ simultaneously. They also give practical detectors for speculative pipelines (Ars-$\\tau$ / Ars-Prior and Bayes-MLP / Bayes-Prior).\n\nProduction stacks already depend on speculative sampling; having a *measurable* frontier and a concrete recipe to sit on that frontier is valuable.\n\n## Main claims / contributions\n1. **Strength as information:** Define watermark strength as $E_\\zeta[D_{KL}(P_\\zeta || P)]$ and prove it controls the optimal detector’s p-value decay (through the per-token log-likelihood ratio).  \n2. **Tight frontier & optima:** For unbiased schemes, strength is upper-bounded by $H(P)$; speculative acceptance is upper-bounded by $1 - TV(Q,P)$. Gumbel-max and SynthID (as $m \\to \\infty$) are strength-optimal; the proposed **seeded acceptance** achieves *both* bounds simultaneously.  \n3. **Operational trade-offs & detectors:** A constrained program (Eq. 10) traces the **Pareto curve** $L(r)$. The paper designs detectors that account for draft/target paths; when the accept coin is known (Ars-$\\tau$, Bayes-MLP), detection is stronger than prior averaging approaches (Ars-Prior, Bayes-Prior).", "questions": "See above", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 3, "strengths": "## Strengths\n- **Conceptual clarity:** Moving from a binary notion to a continuous, information-theoretic strength is the right abstraction. It cleanly explains earlier \"impossibility\" statements and yields a usable frontier.  \n- **Tight theory that lines up with practice:** The Chernoff–Stein interpretation makes sample-complexity predictions directly actionable; the entropy and TV bounds give interpretable ceilings.  \n- **Simple, impactful algorithmic tweak:** Seeding the accept coin is minimal and compatible with production speculative pipelines.  \n- **Detector design under speculative sampling:** The draft/target path issue is real; the two Ars and two Bayes variants are a neat, pragmatic treatment.  \n- **Figures are helpful:** The trade-off plots communicate the Pareto picture at a glance; markers (WS/SE maintained, optimum) guide interpretation.", "weaknesses": "## Weaknesses / limitations\n- **Oracle knowledge vs deployment reality:** Many results assume access to the base distribution $P_t$ (or accurate logits) and, for the strongest detectors, the **accept coin**. External forensics often lacks both; estimation error can materially affect strength and false positives.  \n- **Model/scale realism:** Simulated $(Q,P)$ pairs and small-vocab settings may not capture calibration quirks, long-tail tokens, or beam-blocking in large models.  \n- **Robustness / attack model:** The paper doesn’t stress-test adversaries who (i) alter spacing/punctuation, (ii) paraphrase with another model, or (iii) run ensemble-style removal — how quickly does the effective KL collapse?  \n- **Broader behavioral impacts not discussed:** Recent studies suggest watermarking can alter model behavior beyond detectability or quality trade-offs. *Downstream Trade-offs of a Family of Text Watermarks* (Ajith et al., EMNLP 2024) reports 10–20% drops in downstream task accuracy even for “unbiased” schemes like KGW, while *WaterJudge* (Molenda et al., NAACL 2024) quantifies a detectability–quality trade-off across watermark strengths. *Watermarking Degrades Alignment in Language Models* (Verma et al., ICLR 2025) further shows that watermarking can shift alignment properties such as truthfulness, safety, and helpfulness, mitigated partly by an external reward model. The paper would be stronger with a targeted discussion of how speculative sampling with watermarking affects alignment-relevant metrics (e.g., reward scores) and a short discussion citing these works to contextualize potential side effects.  \n- **Downstream behavior:** Stronger coupling can interact with alignment/quality. Recent work reports reward/quality/alignment degradations under watermarking; the paper doesn’t quantify the proposed method’s effect on reward score or human preference.  \n- **Reporting details:** Some derivations (e.g., Eq. 10) are explained tersely; detector training details and calibration of $\\tau$ / $p$ could be easier to reproduce.\n\n## Actionable suggestions\n1. **Adversarial/transform robustness:** Evaluate detectability after common edits (paraphrase via another model, synonym swaps, punctuation/whitespace jitter, mild re-ordering). Report the induced drop in effective strength and how close it is to theoretical predictions.  \n2. **Latency & throughput accounting:** Since the goal is \"fast **and** provable,\" include an end-to-end latency/throughput table under seeded acceptance (overhead of PRNG, acceptance calibration, detector extraction) to confirm the practical speedup survives.  \n3. **Downstream effects audit:** Report reward-model scores or human preference deltas for seeded-accept decoding vs baseline speculative and vs classic watermarks. Even a small ablation will reassure readers that “max strength” doesn’t quietly harm alignment/quality.  \n4. **Clarity & reproducibility:** Expand the derivation around Eq. 10 in the main text (one boxed paragraph). Right now it jumps out of the blue without providing much background.\n\nThe narrative is coherent and the prior binary impossibility is treated respectfully. I appreciated the clean placement of this work relative to Hu & Huang and SynthID, as well as the detector connection to Bayesian scoring networks. I would like to see clearer statements about assumptions (knowledge of $P_t$, seed/coin access) up front.\n\n\n## Writing and Presentation\nGenerally clear but somewhat difficult to follow; figures carry their weight. The \"what to believe after reading\" is crisp: *use KL as strength, plot the Pareto, seed the accept coin to sit on the frontier.* A bit more exposition around the constrained program and detector calibration would help readers who don’t already know speculative internals.\n\n## Nits / small issues\n- Define “accept coin” once in the intro or prelims to avoid hunting later.  \n- Around the entropy upper bound, one sentence explaining $WS = H(P) - E[H(P_\\zeta)]$ would help a beginner.  \n- Minor typographical cleanups: consistent capitalization of \"SynthID,\" spacing around $TV(\\cdot,\\cdot)$, and equation referencing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "bnG7cdJsOb", "reviewer": "Reviewer_d8rs", "summary": "The paper revisits the trade-off between watermarking and speculative sampling. It (i) quantifies watermark strength as the expected KL divergence, showing this metric controls the asymptotic p‑value decay rate of the optimal detector (ii) formalizes the strength–efficiency Pareto frontier (iii) proposes pseudorandom acceptance by introducing an extra seed $\\zeta_R$ so the accept/reject step is itself a deterministic function of pseudorandomness. Empirically, the method matches standard speculative sampling in AATPS while improving TPR@FPR=1% for detection compared with previous methods that preserve AATPS.", "questions": "I would encourage authors to also report ANLPPT, as with AATPS for efficiency, to quantify the detectability gap relative to a non-speculative watermarked baseline.\nHow large is the remaining gap in detectable watermark signal strength?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. New perspective (not detection‑first, measure strength via KL).\nThe paper propose to cleanly separates watermark strength from detector performance, grounding the former in an information‑theoretic quantity (expected KL) with a clear sample‑complexity interpretation (Theorem 3.1) and a tight entropy upper bound (Theorem 3.2). This presents a principled framework for further analysis.\n\n2. Evidence of better trade‑offs in practice.\nAATPS closely tracks the standard baseline, while detection improves compared with previous methods that preserve AATPS.\n\n3. Clear writing and organization.\nThe paper is easy to follow, with crisp statements, clear algorithm, and figures that directly support claims.", "weaknesses": "### Whether the “trade‑off” truly disappears (terminology/interpretation).\n\nTheorem 4.1. builds on redefining strength as expected KL. This metrics makes some new proposed analysis possible. However, the paper itself clarifies that watermark strength ≠ detection efficiency (Remark 3.1): two schemes with comparable watermark strength may still differ in detection efficiency.\n\nRegarding specific methods, mixture of multiple pseudorandom sources will hurt detection efficiency, as more pseudorandom sources means more ambiguity at detection time. (Hu & Huang, 2024) uses one pseudorandom seed. (Dathathri et al., 2024) uses two seeds (draft + target), with multi-round tournaments there may be effectively more. This paper uses three seeds, further compounding interference among signals at detection time. Concretely, for any observed token the detector does not know whether it came from (i) an accepted draft token, (ii) a rejected token replaced from the residual, or (iii) the “extra” token when all draft tokens were accepted. This uncertainty necessarily makes practical detection weaker than the paper’s “WS” metric.\n\nIn Experiment section of this paper, the claim is also “improved detectability,” not matching with non-accelerated watermarking.\n\nTherefore, the “trade‑off” still exists. The paper pushes the practical frontier but does not remove it, the headline “BREAK THE TRADE-OFF” is overstated. A more faithful summary is that the method steadily approaches a better trade-off.\n\n### Minors:\n\nThe paper, for simplicity, treats positions as independent. A stricter analysis should avoid this assumption, and some results can hold without independence.\n\nSeed reuse is not discussed. Re-applying the same pseudorandom seed should be skipped (e.g., as in prior “context code history”) to maintain unbiasedness.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "fYIWbJdugf", "reviewer": "Reviewer_sUKk", "summary": "The paper revisits the trade-off between watermark strength and speculative sampling efficiency in large language models. It formally quantifies watermark strength using KL divergence and derives a theoretical upper bound equal to the entropy of the base model. To overcome the claimed inevitable trade-off from prior work, the authors propose a pseudorandom acceptance mechanism that makes the entire sampling process a deterministic function of pseudorandom seeds. They further introduce new detection methods (Ars-$\\tau$ and Bayes-MLP) leveraging this mechanism, and demonstrate through experiments that the approach improves detection performance without reducing decoding throughput.", "questions": "see weaknesses", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper provides a theoretical framework connecting watermark strength and speculative-sampling efficiency. The proposed pseudorandom-acceptance mechanism is theoretically appealing, showing that the trade-off can be alleviated under certain conditions.", "weaknesses": "1. The proof that watermark strength can reach the upper bound $WS = H(P)$ (Theorem 3.2) assumes that each $P_\\zeta$ is a completely deterministic distribution, where every generated token is fixed once the pseudorandom seed is given. However, even SynthID’s tournament sampling still has randomness after top-$k$ and $2^m$ rounds, so $P_\\zeta$ isn’t truly deterministic. This means the bound is more of a theoretical ideal than something achievable in real LLM decoding. The paper should make this distinction clearer and discuss how far practical schemes are from that ideal. For example, how much does it improve over different m (the number of layers used in SynthID)?\n\n2. The claim of achieving both the best sampling efficiency ($SSE = 1 - \\mathrm{TV}(Q, P)$) and the highest watermark strength ($WS = H(P)$) relies on several strong assumptions, such as perfectly unbiased decoders, fully deterministic generation, and independent pseudorandom seeds. If any of these assumptions don’t hold, the trade-off comes back. So should the result really be interpreted as showing what’s possible under idealized conditions, not as a general solution that always works?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "PCJTNKWyr7", "reviewer": "Reviewer_Zd3w", "summary": "This paper revisits the trade-off between watermark strength and speculative sampling efficiency in large language models (LLMs). The authors argue that the incompatibility stems from the use of independent random sources: watermarking modifies token sampling using pseudorandomness, while speculative sampling introduces additional stochasticity through draft-token acceptance. This mismatch weakens watermark detectability and limits inference efficiency. To resolve this, the paper proposes a unified pseudorandom framework that decomposes random sources into three independent components: \\(ζ_D\\) (for the draft model), \\(ζ_T\\) (for the target model), and \\(ζ_R\\) (for acceptance decisions)", "questions": "1. Could the authors discuss whether the pseudorandom control framework can be generalized to biased or reweighted watermark schemes?  \n\n2. Considering that speculative sampling is primarily designed to accelerate inference, the paper should report additional runtime measurements comparing (a) standard speculative sampling, (b) speculative sampling with watermarking, and (c) the proposed method, to confirm that efficiency gains are retained.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper provides a clear theoretical explanation for why speculative sampling and watermarking interfere with each other—namely, their reliance on separate random sources.  \n- The proposed pseudorandom acceptance mechanism is simple yet elegant, turning the generation process into a deterministic function of pseudorandom variables.  \n- Theoretical analysis (Pareto frontier characterization) and empirical evidence consistently demonstrate that the proposed design breaks the previously assumed trade-off between watermark strength and efficiency.  \n- The work unifies two practically important but previously conflicting mechanisms, offering a potential path toward efficient and traceable LLM inference", "weaknesses": "1. The experimental evaluation only considers two unbiased watermarking schemes (Gumbel-max and SynthID). The analysis would be more convincing if extended to other representative watermarking frameworks, such as KGW or reweight-based methods [1,2].  \n\n2. The proposed method requires applying watermarking to both the draft and target models during speculative sampling. The paper does not analyze whether this dual watermarking might affect text quality or fluency.  \n\n[1] Hu, Zhengmian, Lichang Chen, Xidong Wu, Yihan Wu, Hongyang Zhang, and Heng Huang. *Unbiased watermark for large language models.* arXiv preprint arXiv:2310.10669 (2023).  \n[2] Wu, Y., Hu, Z., Guo, J., Zhang, H., & Huang, H. *A resilient and accessible distribution-preserving watermark for large language models.* arXiv preprint arXiv:2310.07710 (2023).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)