Inevitable Trade-off between Watermark Strength and Speculative Sampling Efficiency for Language Models
Authors: Zhengmian Hu
Heng Huang
Venue: NeurIPS 2024 poster (2024)
Keywords: watermark
speculative sampling
large language model
sampling
inference
Primary area: generative_models
TL;DR: a no-go theorem states that we can maintain either the sampling efficiency or the watermark strength, but not both.

Abstract: Large language models are probabilistic models, and the process of generating content is essentially sampling from the output distribution of the language model. Existing watermarking techniques inject watermarks into the generated content without altering the output quality. On the other hand, existing acceleration techniques, specifically speculative sampling, leverage a draft model to speed up the sampling process while preserving the output distribution. However, there is no known method to simultaneously accelerate the sampling process and inject watermarks into the generated content. In this paper, we investigate this direction and find that the integration of watermarking and acceleration is non-trivial. We prove a no-go theorem, which states that it is impossible to simultaneously maintain the highest watermark strength and the highest sampling efficiency. Furthermore, we propose two methods that maintain either the sampling efficiency or the watermark strength, but not both. Our work provides a rigorous theoretical foundation for understanding the inherent trade-off between watermark strength and sampling efficiency in accelerating the generation of watermarked tokens for large language models. We also conduct numerical experiments to validate our theoretical findings and demonstrate the effectiveness of the proposed methods.

Inevitable Trade-off between Watermark Strength and Speculative Sampling Efficiency for Language Models
Zhengmian Hu, Heng Huang
Department of Computer Science
University of Maryland
College Park, MD 20742
huzhengmian@@gaill. com, heng@umd edu
Abstract
Large language models are probabilistic models, and the process of generating content essentially sampling from the output distribution the language model. Existing watermarking techniques inject watermarks into the generated content without altering the output quality. On the other hand, existing acceleration tech- niques, specifically speculative sampling. leverage draft model to speed the sampling process while preserving the output distribution. However, there no known method to simultancously accelerate the sampling process and inject water- marks into the generated content. In this paper, we investigate this direction and find that the integration of watermarking and acceleration is non-trivial. We prove a no-go theorem, which states that it impossible to simultaneously maintain the highest watermark strength and the highest sampling efficiency. Furthermore, we propose two methods that maintain either the sampling efficiency or the watermark strength, but not both. Our work provides rigorous theoretical foundation for understanding the inherent trade-off between watermark strength and sampling efficiency accelerating the generation of watermarked tokens for large language models. We also conduct numerical experiments to validate our theoretical findings and demonstrate the effectiveness of the proposed methods.
Introduction
Large language models (LLMs) have demonstrated remarkable performance in various natural language processing tasks, enabling a wide range of applications such as chatbots 223]. content generation [17), code generation [6], and more. However, the high training and inference costs of LLMs pose significant challenges. The substantial computational resources along with the high latency during inference can negatively impact user experience and limit their potential applications.
To address the issue of high inference costs, speculative sampling [6 5] has emerged as a promising approach. This technique leverages a smaller, faster draft model to generate candidate results, which are then validated and corrected by larger, more accurate target model. Compared with other acceleration methods such knowledge distillation, model quantization, and model pruning, the key advantage of speculative sampling is that it can significantly reduce inference latency without compromising the quality of the generated content.
In addition to the challenge of high inference costs, protecting the intellectual property rights LLMs generated content has become increasingly important. Digital watermarking techniques [3] have been proposed to embed watermark information into the generated content, enabling the tracking of model usage. Unbiased watermarking schemes [12] have been developed to ensure that the watermarking process does not affect the quality of the generated content.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Maintain Watermark Strength Algorithm Theorem 5
Ideal (Impossible) Theorem
Watermark Strength
Vanilla Unbiased Watermark
Maintain Sampling Efficiency
Algorithm
Algorithm
|
Theorem 6
Basic Sampling
Vanilla Speculative Sampling Algorithm
Algorithm 2
Speculative Sampling Efficiency
Figure 1: Taxonomy of watermarking and speculative sampling trade-offs in language models. The ideal case of maintaining both watermark strength and sampling efficiency is proven to be impossible by the no-go theorem. The proposed algorithms focus on maintaining either watermark strength or sampling efficiency.
A natural question arises: can we leverage speculative sampling to accelerate the generation of watermarked content? To address this question, we propose a general framework called the two reweight framework, which allows for the integration of unbiased watermarking and speculative sampling techniques while guaranteeing an unchanged output distribution. The main innovation of our framework lies in the simultaneous reweighting of both the target model and the draft model, which improves sampling efficiency compared naively applying speculative sampling to watermarked target model.
To evaluate the effectiveness of our framework, we consider two key metrics: watermark strength and acceleration performance. A fundamental question is whether it is possible to achieve both strong watermarking and efficient speculative sampling simultancously. Specifically, we aim answer the following question:
Can we obtain the same watermark strength as in the case without acceleration while maintaining the same sampling efficiency in the case without watermarking?
Surprisingly, got negative answer to this question. We prove no-go theorem, which states that under the two reweight framework, is impossible to simultancously maintain both the watermark strength and the sampling efficiency when the vocabulary size is greater than two. This result highlights the inherent trade-off between watermarking and acceleration in the context of large language models.
To better explore the trade-offs between these two objectives, we propose two practical algorithms within the two reweight framework. The first algorithm focuses maintaining the watermark strength, while the second algorithm aims to maintain the sampling efficiency.
The main contributions of this paper are as follows:
We propose the two reweight framework, a general framework that allows for the integration of unbiased watermarking and speculative sampling techniques while ensuring an unchanged output distribution.
We prove no-go theorem, which states that under the two reweight frumework, it is impossible to simultaneously maintain both the watermark strength and the sampling efficiency when the vocabulary size is greater than two.
We propose two practical algorithms within the two reweight framework that focus on maintaining either the watermark strength or the sampling efficiency, providing insights into the achievable trade-offs.

---

To the best of our knowledge, this work represents the first exploration of the intersection between unbiased watermarking and speculative sampling, introducing novel framework, significant no-go theorem, and pioneering practical algorithms.
2 Preliminary
In this section, will introduce the basic concepts and notations used throughout the paper, and provide a brief overview of watermarking and speculative sampling techniques for large language models.
language model defines probability distribution over sequences of tokens from vocabulary set E. It assigns a probability P , ..,) to the next token In+1 given the context of previous tokens F 42; .... Tn- We use Ay; to denote the set of all possible probability distributions over the vocabulary Σ.
Following Hu et al. [12). we define watermarking scheme as a tuple (E, PE. R). where & is set of watermark codes, PE is a probability distribution over &, and R : E x Ar + Ay is reweighting function that maps a watermark code E E & and a probability distribution P E Ay to watermarked distribution R ( P)) E Ag. We focus on unbiased watermarking schemes that satisfy Eg~Px Rg [P) = for all Ag, unless explicitly stated otherwise.
To generate watermarked token æ, we first compute a watermark code E ~ Pp based on the context, and then sample the token from the watermarked distribution, i.e., x Rx The entropy of the distribution P determines the maximum amount of watermark that can be injected. For a distribution P with high entropy, the divergence between the watermarked distribution Rg(P), and the original distribution P can be larger, allowing for more watermark information to be injected.
The presence of the watermark can be detected by statistical tests. The pivotal quantity used in these tests is often referred to as the watermark score. A higher watermark score implies a more detectable watermark. The log likelihood ratio (LLR) is the most powerful score for detecting watermarks in the absence of any perturbations. However, in practice, more robust scores such as the maximin-LLR likelihood-agnostic scores are often used. In this paper, consider two specific watermark scores: the maximin-LLR score, which is described in detail in [12), and the U score, which is a likelihood-agnostic score that can be defined for both DeltaGumbel reweight and Gamma reweight schemes. The details of the U score, DeltaGumbel reweight and Gamma reweight are provided in Appendix D
The P-value can be computed by considering the absence of a watermark as the null hypothesis. For score S with known moment-generating function (MGF), the P-value can be upper bounded using the Chernoff bound:
(S (S 2 8) S min EicAs exp (-AS).
(1)
X20
Speculative sampling 16 5 is technique for accelerating the generation of tokens from target
model P by leveraging a faster draft model Q. The key idea is to first sample a draft token 7 from the draft model Q, and then accept or reject it based the ratio of the target and draft probabilities. If the draft token rejected, a new token is sampled from a residual distribution proportional to the difference between the target and draft probabilities. Formally, the speculative sampling process generates a token x as follows:
(Ln p()) QUi
if j.
P(x 5| =
cu (PP)-QU)) if #
Lcc -(=)-
where (x)_ xr).. The design of the speculative process ensures that the final distribution of the generated token x matches the target distribution P. The efficiency of speculative sampling can be measured by the overlap probability
Q) = E min( P(t), Q(t)), which is the probability of accepting the draft token in each step. The overlap probability related to the total variation distance between P and Q by TV(P, Q) be applied multiple times to generate and verify multiple draft tokens in one step.
a Q). Such speculative sampling process can
Due to space limitations, we have moved the discussion of other related works to the Appendix A
3

---

3 Two Reweight Framework for Accelerated Generation of Watermarked Tokens
In this section, we propose a novel framework called the two reweight framework for accelerating the generation of watermarked tokens based on speculative sampling techniques. The motivation behind this non-trivial framework is that naively applying speculative sampling to a watermarked target distribution (P) may significantly reduce the overlap probability a (P),)) Q) with the draft distribution Q, leading to small sampling efficiency.
The key innovation of the reweight framework is apply separate reweighting function R' to the draft distribution Q, using the same watermark code E as the one used for reweighting the target distribution. By doing so, aim to increase the overlap probability between the watermarked target distribution (P) and the watermarked draft distribution R2'(() i.e., ar a<Rx(P), R'g (Q)), thus improving the sampling efficiency.
Formally, we define the watermarked draft distribution using another rewcighting function (E, Pg, R"), where R' & Ay Ax is function that maps watermark code E E & and a draft distribution Q E Ay to a watermarked draft distribution (Q) E Ay. The framework itself does not require the watermarked draft distribution to be unbiased, i.e., Eg~Px [R'g (Q)) all Q E Ag. However, we will see later that this unbiasedness property naturally emerges when we require the final output distribution to be unbiased and aim to improve the sampling efficiency (Lemma
for
To generate a watermarked token, we first sample draft token E from the watermarked draft distribution, i..,, ã ~ (Q) or equivalently P(ä = i) = (i) for all i E Σ. Then, we perform certain speculative sampling based the draft token to obtain the generated token The speculative process is defined by a conditional probability distribution A(j]i) for all i,j E Σ. where A(-10) E Ag for each i. The design of A can depend on the target distribution P, the draft distribution Q. and the watermark code E. The probability generating token x = given a draft token = is given by P(r j i) A(jii).
The distribution of the generated token, which we call the generation distribution, can be computed as follows:
P( j) Σ
=) Σ
(( (A (Q)(() (3)
SE
We denote the generation distribution by (P) A R' (Q).
To ensure that the two reweight framework produces an unbiased output distribution, we require that for all P Ag:
(R-))([n(P)] =
4 No-go Theorem
Despite the potential of the two reweight framework, we present a no-go theorem that shows the impossibility of simultaneously maintaining the watermark strength and sampling efficiency when the vocabulary size is greater than two.
Theorem 1 (No-go Theorem). When the vocabulary size [ 2, there do not exist non-trivial reweighting functions R: E x Ax, + As, and R' E x As. + As, and speculative process A(ji) such that for all P, Q.Q. E As:
1. The watermark strength maintained: Rg(P) Rg(P).
2. The sampling efficiency is maintained: a(P,Q) ΣE~PE Dies. (Q(1),
Remark 2 (Condition for maintaining the watermark strength). The condition R = Re in Theorem ensures that the watermark strength is maintained by keeping the average watermark score unchanged, i.e.
EE~PE (P)) E)] EE- B (Score(t, (Scoret,
(5)
10.

---

where Score(t, E) is an arbitrary function that measures the watermark strength.
Strictly speaking, ensure that the watermark strength remains unchanged, we only need to require w', and the condition RE(P) Rg(P) sufficient condition. However, due the large design space of scoring functions, if we want to maintain w = w' for every possible score, then RE P)
RE( (P) becomes necessary condition.
On the other hand, for fixed scoring function and specific R3. is possible that (P( + (F(P) while w' necessary for maintaining the watermark strength for specific scoring function and reweighting function.
w' In other words, the condition (g(P) Rg(P) is not always
The proof of the no-go theorem relies on the following two lemmas, which reveal the connections between maintaining the sampling efficiency, maintaining the watermark strength, and the properties of the reweighting functions.
Lemma (Maintaining Sampling Efficiency Implies Unbiased Watermarked Draft Model). for all P. Q Σg, have
alP, (), = EEEPE
Σ LiEE
(2)))
then EE PE Q for all Q E Ag.
Lemma (Maintaining Watermark Strength and Sampling Efficiency Implies Same Reweight Function). Under the two reweight framework, for all P.Q E Ar, we have
a(P. Q) EESPE
Σ (( LIE
= ((P)=Re(P)
then (Q) RF(Q)) for all Q As:
The proofs of these lemmas are deferred to Appendix B With these lemmas, we can now prove the no-go theorem.
Proof of Theorem According to Lemma maintaining both the watermark strength and sampling efficiency under the two reweight framework implies that (Q) Rg(Q) for Q Ag. Therefore, we have
a(P,Q) < (,
(6)
To see this, note that
B Σ A(( AQ0))))))0))
(e( 2 (Q)()) (Q) Rin(
Summing over i, get
Σ (())) S Σ min min(Rr(Q)()) (z)))()) min((Br(Q110))(((())))) (RRF(Q), Rm(P)).
Taking the expectation over E, we obtain Equation 6
Recall that QP.QQ) = TV(P. Q), where TV(P, Q) denotes the total variation distance between
P and Q Therefore, Equation (6) is equivalent to
TV(P,Q) EE~PA (R)) (P),
Viewing P,Q As; as n-dimensional vectors, where n = [ we can express the total variation distance as
2TV(P.Q)
max (u, P Q), wE[-1,1]
(8)

---

where the maximum is attained at u²(P. Q) sign P - Q). Using this expression, we have
(E=-) RF()) = PE~PE
max (u, RE(P) - RE( _El--1,1j-
Σ PE (u' (P. (P) (
Re(Q))
(9)
(P, Q) 2TV(P.Q)
(10)
Combining Equations equivalent to
and (T) we conclude that the equality in Equation must hold, which is
u (P.Q) E Argmax,e(-1.jp (u, Rg Rg(P) Re(()).
(11)
almost surely for random E. This condition equivalent to the following:
(P (1) = 0 = (Re(P) (x( 0,
(12)
(P -P-Q1 Q)(1) 2 0
(Rg(P) Rx(Q))(() 2 0,
(13)
()) 0 = (RE(P) - Rx(Q))(1) S 00
(14)
almost surely for random E and for all i e Σ. Now, let label the symbols in the vocabulary E E {l....,n) n). For distribution P (P1, . Pn), define
T₃(1-
1
Pi mod n 1,
0
otherwise.
For example, Ti (pI, - Pl, ...00.....))) 0). T2 (0, p2, 1 - p2, 02......,0)) .,.....,, and Tn = (1
Pr, ., 0, P.). Let functions (p.) = Rg (i)
We claim that R (P) F.(p.).
(15)
To see this, note that (P-T.)()== P = 0. so by Equation (12). we have (Rs(P)-Rs((i))())
which implies Rg = (T, (p.) almost surely.
Next, we show that the functions F; satisfy the following properties:
FO 0,
(16)
(1) = 1,
(17)
F,(p) is monotonically increasing in p, = 1.
(18)
Σp. Pp-11- = = Σ =(p))=
(19)
To prove Equation (16), consider the case when p; O. this case, - 1 mod n + and Ti(i) 0 otherwise. To ensure the unbiasedness of the reweighting function, we must have T,, which implies (T, = almost surely. Therefore, R (T) Ti
Eg~Px Eg = 0, and thus (O = 0.
Similarly, to prove Equation 17 consider the case when p; 1. In this case, T:Ú) if
j and (j( = 0 otherwise. Again, to ensure the unbiasedness of the reweighting function, must have Eg-rg R [7.) T,, which implies Ræ(T,) T; almost surely. Therefore, (g) = (i( = = 1, and thus F1(1)=
To prove Equation 18 consider two values p; 2 p/: Define T; and T follows:
i, 1 P: mod + 11, T(() 1 1-pl j i mod n + +1,
7//
T((i)
0
otherwise,
0
otherwise.
Since P; p4 (T: - (1)
by Equation 13
we have F.(p.) F.(p)) (RE(T,)
RE(T)) 2 0, which proves the monotonicity of F..
To prove Equation 19). notice that due to Equation
15
have E, F(lp)) E (i(()
Finally, according to Lemma the functions F; satisfying Equations 16 19 must be the identity
function, i.c., (p) for all i (1,2...., n. and p [0, 1]. Combining this with Equation 15).

---

we conclude that (g(P) = P almost surely for random E, which means that the reweighting function R trivial.
Therefore, when the vocabulary size X
> 2, it is impossible to simultaneously maintain the
watermark strength and sampling efficiency using non-trivial reweighting functions under the two reweight framework.
Algorithms for Maintaining Watermark Strength or Sampling Efficiency
Algorithm 1 Maintaining Watermark Strength or Sampling Efficiency
Given draft sequence length K, prompt 21,..., .n. target model P(-l-), draft model Q(+I-), code history ech as list of context code, context code function ce : Σ - C, watermark code
generation function E C x Z + &, reweighting functions R & x Av: 7 As, and key for watermark z Z.
Initialize draft context code history ech + cch. for t 1 K + 1 do Compute context code C = cc(a1,...... In, .1,..., "..,; -1), watermark code E; E(c,, 2).
Check skipped skipped, = true e exists coh,
Set ech + och + [ca].
false
e doesn't exists in cch.
if = K + then Exit for loop. end if Compute distribution Q+(-) = f..
31 f1, 12-1).
skipped, true, Sample draft token ã, Dc. Let Qr = RE (Qt) skipped, false.
Q
end for
for t 1: K+ + in parallel do Compute distribution P.(-) = P(- In. 11 2..,,...,, 21-1).
(P [R,
skipped, = true,
Let Q.
skipped, false.
end for
(B,,
maintain watermark strength,
Initialize empty output list: out + []. Let Qr)
(Pr, Qt)
maintain sampling efficiency.
fort K do Set och t ech + [ce]. Sample ~ U10,, 1] from a uniform distribution.
ifr min(1, Q(2)))
(x())) then Set out + out + [Tx]. else
Sample xntt ~ (P, Q.)+. Set out + out + [xnte]. Exit for loop.
end if end for
if out
[ 12,...., T Tgl then Set och + ech + [ck+1]. Sample T4+K+1 Bx Set out + out + [[n*K+]]
end if
Return oul as generated tokens, and ech as context code history.
In this section, we present two algorithms that aim to maintain either the watermark strength or the sampling efficiency under the nwo reweight framework. light of the no-go theorem (Theorem [ which precludes the simultancous maintenance of watermark strength and sampling efficiency, these algorithms provide deeper insights into the trade-offs between the two objectives.
5.1 Maintaining Watermark Strength
To maintain the watermark strength, we choose the reweight function for draft distribution to be the same the reweight function for the target distribution, i.e., (Q) Re(Q). The speculative process is designed as follows:
min(1, Rg Rg (Q)(e)
Re (P)())
if j,
A(jli) =
Re(P)
( (Re(P)c)-R((M))))))
(20)
i
E.en (R (Re(
7

---

Theorem 5 (Maintaining Watermark Strength). Under the two reweight framework, if (Q) (Q) and the speculative process A(jli) defined as in Equation (20). then the watermark strength is maintained, i.e., (g(P) = -Re(P. Moreover, the generation distribution is unbiased, ie., RE-PS (P)) P all P Ar.
Intuitively, this algorithm applies the same reweighting function Rg to both the draft distribution Q and the target distribution P. and then performs speculative sampling based the reweighted distributions (g(Q) and Rg (P) as draft and target distribution.
5.2 Maintaining Sampling Efficiency
To maintain the sampling efficiency, we again choose the reweight function for draft distribution to be the same as the reweight function for the target distribution, i.c. R'g (Q) = (Q))). However, the speculative process is designed differently:
min(1, P()
if
Q(
A(I
P()
(P() Q01)+
(21)
if + j.
_eer(Q(e)-
Theorem 6 (Maintaining Sampling Efficiency). Under the two reweight framework, if (Q) Rg(Q) and the speculative process A(jli) is defined as in Equation (1). then the sampling effi- Moreover, the generation
ciency is maintained, i.e, (P,, Q) EE>rE 1Evex (( distribution is unbiased, ie., Eg-PE (P)) = for all P E As:
Intuitively, this algorithm generates watermarked draft token using the watermarked draft dis- tribution (Q) and then performs the standard speculative sampling process using the original distributions Q and as draft and target distribution.
5.3 Algorithms
The pseudo code for the two methods described in the previous sections is provided in Algorithm [ This pseudo code applies the methods previous sections for multiple times in each step, and also considers the context code history to ensure unbiasedness for the whole sequence. For reference, sim- ilar pseudo code for basic sampling, vanilla speculative sampling and vanilla unbiased watermarking is provided in Algorithms/ to
Remark 7 (Context code history). According to [12], the context code history is crucial for ensuring the unbiasedness of the entire generated sequence. In both algorithms, all accepted draft tokens' context codes need to be preserved in the context code history. Additionally, when draft token is rejected, its context code should also be preserved because the newly generated random token after rejection, i.e. En+tt is not independent of the rejected random draft token žt. By preserving the right context code history, we ensures that not only the distribution of a single token, but also the distribution of the entire generated sequence is unbiased. During computing watermurk score for detection, a context code history is also necessary so that each context code only contributes to the watermark score once.
6 Experiments
To verify that Algorithm T can indeed maintain either the watermark strength or the sampling efficiency as claimed, we test different methods text summarization task CNN DAILYMAIL dataset [33] [0] using the Llama-7b model [42 as the target model and the Llama-68m model (25 as the draft model.
We measure the sampling efficiency by the number of accepted tokens in the out list of Algorithm I and report the Average Accepted Tokens Per Step (AATPS). A higher AATPS indicates higher sampling efficiency.
To measure the watermark strength, we compute the log P-value. For likelihood- scores, the computation follows the method in [12.. For likelihood-agnostic scores, we use score with the Chernoff bound in Equation (I). where À is optimized numerically. We test the watermark strength
8

---

(a) DeltaGumbel Reweight
1.75
0.4
ANL ANLPPT(maximii (maximin-LLL
1.50
Basic
Basic
VUW
ANLPPT(U Score)
0.3
VUW
1.25
VSpS
VSp5
1.00
MWS
MWS
MSE
MSE
K=1
K=1
0.50
0
K=2
0.1
K=2
0.25
0
K=3
K=3
K=4
K=4
0.00
1.25
1.75
2.00
1.00
1.25
1.50
1.75
2.00
AATPS
AATPS
Gamma Reweight
0.10
Ø
0.25
Basic
Basic
ANLPPT(U Score)
0.08
INLPPT(maximin-
VSpS
VSpS
MWS
0.06
MW5
0.15
MSE
MSE
0.04
0
K=1
K=1
0
K=2
K=2
8
0.05
K=3
0.02
K=3
K-4
K-4
0.00
0.00
1.00
1.25
1.50
1.75
2.00
1.00
1.25
1.50
1.75
2.00
AATPS
AATPS
Figure 2: Comparison of different methods. The x-axis shows the Average Accepted Tokens Per Step (AATPS) measure of speculative sampling efficiency, while y-axis shows the Average Negative Log P-value Per Token (ANLPPT) as measure of watermark strength. The P-value computed based either likelihood-based test using the maximin-LLR score (left) or likelihood-agnostcc test using the U score (right). Watermarking is performed using either the DeltaGumbel reweight (top) or the Gamma reweight (bottom). Error bars represent 3o confidence interval
for both the DeltaGumbel reweight and the Gamma reweight schemes. The Average Negative Log P-value Per Token (ANLPPT) is reported, with higher value indicating a stronger watermark.
The results shown in Figure We compare the performance of Basic Sampling, Vanilla Unbiased Watermark (VUW). Vanilla Speculative Sampling (VSpS), Maintain Watermark Strength (MWS), and Maintain Sampling Efficiency (MSE). We also measure the Per Token Time (PTT) in millisecond to evaluate the wall-time latency and verify that Algorithm I can indeed achieve acceleration compared the vanilla unbiased watermark method. The Log Perplexity (LOGPPL) is computed to verify that all algorithms produce the same output distribution and do not affect the quality of the language model output. The raw data for these additional metrics are provided Table i in the appendix due to space constraints.
We also conduct additional experiments using different models and tasks. In addition to the Llama-7b model, we test the I.lam- 13b model 42 as the target model, with Llama-68m 25 as the draft model. Besides the text summarization task, also evaluate the methods generation task. The results these additional experiments are provided in Appendix H The total computational cost for reproducing all the experiments in this paper is approximately T200 A6000 GPU hours.
open-ended text
'The etror bars for some methods are very small and may not be visible in the plot. The exact error bar can be found in Table

---

The experimental results in Figure 2 and Appendix H support the following findings:
Algorithm can indeed maintain either the watermark strength or the sampling efficiency as claimed. The MWS method achieves the same watermark strength as the VUW method, while the MSE method achieves the same sampling efficiency as the VSpS method.
Algorithm can indeed accelerate the generation process compared to the vanilla unbiased watermark method. Both the MWS and MSE methods achieve lower PTT than the VUW method, as shown in T
MWS method has only marginal sampling efficiency gap compared to VSpS, while maintain the watermark strength as VUW method, making it highly practical.
All algorithms produce the same output distribution and do not affect the quality of the language model output, as evidenced by the similar LOGPPL values across all methods in Table |
The above findings are consistent across different draft sequence length (K' = 1, 4), different models (Llama-7b and Llama-13h 13b), different tasks (text summarization and open-ended text generation), different reweight schemes (DeltaGumbel and Gamma), and different watermark detection methods (likelihood-banl and likelihood-agnootti)). Our extensive experiments validate the generality of the findings.
In summary, our experimental results validate the theoretical findings and demonstrate the effective- ness of the proposed Algorithm
Conclusion
Our work provides rigorous thcoretical foundation for understanding the trade-off between termark strength and sampling efficiency in the context of accelerated generation of watermarked tokens from large language models. We prove no-go theorem, showing that non-trivial trade-offs are inevitable when the vocabulary size is greater than two. To explore these trade-offs, we design algorithms that prioritize either watermark strength sampling efficiency. Our findings contribute to the development of methods for protecting the intellectual property language models while leveraging the efficiency of speculative sampling techniques.
Acknowledgments
ZH and HH were partially supported by NSF IIS 2347592, 2347604, 2348159, 2348169, DBI 2405416, CCF 2348306, CNS 2347617.
References
[1] Scott Aaronson. My ai safety lecture for ut effective altruism. November 2022. URL https //scottaaronson blog/?p-6823
[2] Mikhail Atallah, Victor Raskin, Michael Crogan, Christian Hempelmann, Florian Kerschbaum, Dina Mohamed, and Sanket Naik. Natural language watermarking: Design, analysis, and proof-of-concept implementation.
Information Hiding: 4th International Workshop, IH 200/ Pittsburgh, PA, USA, April 25-27, 200/ Proceedings 4, pages 185-200. Springer, 2001.
[3] Jack T Brassil, Steven Low, Nicholas F Maxemchuk, and Lawrence O'Gorman. Electronic marking and identification techniques to discourage document copying. IEEE Journal on Selected Areas Communications, 13(8):1495-1500 1995.
[4] Tianle Cai, Yuhong Li, Zhengyang Geng, Hongwu Peng. Jason D Lee, Deming Chen, and Tri Dao. Medusa: Simple Ilm inference acceleration framework with multiple decoding heads. arXiv preprint 2rXiv:2401.10774 2024.
[5] Charlie Chen, Sebastian Borgeaud, Geoffrey Irving, -aptiste Lespiau, Laurent Sifre, and John Jumper. Accelerating large language model decoding with speculative sampling. arXiv preprint arXiv: arXiv:2302.003312 2023.
10

---

[6] Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, et Evaluating large language models trained on code. arXiv preprint
2021.
[7] Miranda Christ, Sam Gunn, and Or Zamir. Undetectable watermarks for language models. arXiv preprini 2rXiv22306.09194 2023.
[8] 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 Information Forensics and Security (WIFS), pages 1 1-6. IEEE, 2023.
[9] Zhenyu He, Zexuan Zhong, Tianle Cai, Jason Lee, and Di He. Rest: Retrieval-based speculative decoding. arXiv preprint urXiv:2311.08255 2023.
[10] Karl Moritz Hermann, Tomás Kociský, Edward Grefenstette, Lasse Espeholt, Will Kay, Mustafa Suleyman, and Phil Blunsom. Teaching machines to read and comprehend. In Twenty-eighth Conference on Neural Information Processing Systems, pages 1693-1701, 2015.
[11] Abe Bohan Hou, Jingyu Zhang, Tianxing He, Yichen Wang, Yung-Sung Chuang, Hongwei Wang. Lingfeng Shen, Benjamin Van Durme, Daniel Khashabi, and Yulia Tsvetkov. Sem- stamp: A semantic watermark with paraphrastic robustness for text generation. arXiv preprint 2 2023.
[12] Zhengmian Hu, Lichang Chen, Xidong Wu, Yihan Wu, Hongyang Zhang, and Heng Huang. Unbiased watermark for large language models. arXiv preprint (0.::2310.16660 2023.
[13] John Kirchenbauer, Jonas Geiping, Yuxin Wen, Jonathan Katz, Ian Miers, and Tom Goldstein. A watermark for large language models. In International Conference on Machine Learning, pages 17061-17084. PMLR, 2023.
[14] John Kirchenbauer, Jonas Geiping, Yuxin Wen, Manli Shu, Khalid Saifullah, Kezhi Kong, Kasun Fernando, Aniruddha Saha, Micah Goldblum, and Tom Goldstein. On the reliability of watermarks for large language models. arXiv preprint arXiv:2306. 046344 2023.
[15] Rohith Kuditipudi, John Thickstun, Tatsunori Hashimoto, and Percy Liang. Robust distortion- free watermarks for language models. arXiv preprint (xXix:2337.1559/ 2023.
[16] Yaniv Leviathan, Matan Kalman, and Yossi Matias. Fast inference from transformers via speculative decoding. In International Conference on Machine Learning, pages 19274-19286. PMLR, 2023.
[17] Junyi Li, Tianyi Tang, Wayne Xin Zhao, Yun Nie, and Ji-Rong Wen. Pre-trained language models for text generation: A survey. ACM Computing Surveys, 56(9):1-39) 2024.
[18) 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. arXiv preprint arXiv:2404.012 01245, 2024.
[19] Yuhui Li, Fangyun Wei, Chao Zhang, and Hongyang Zhang. Eagle: Speculative sampling requires rethinking feature uncertainty. arXiv preprint arX1v:2401.15077, 2024.
[20] Aiwei Liu, Leyi Pan, Xuming Hu, Shiao Meng, and Lijie Wen. semantic invariant robust watermark for large language models. arXiv preprint Stti:23300003335 2023.
[21] Yepeng Liu and Yuheng Bu. Adaptive text watermark for large language models. arXiv preprint arXiv:2401.13927, 2024.
[22] Yixin Liu, Hongsheng Hu, Xuyun Zhang, and Lichao Sun. Watermarking text data large language models for dataset copyright protection. arXiv preprint arXiv:2005. 13257, 2023.
[23] Bei Luo, Raymond YK Lau, Chunping Li, and Yhin Si. A critical review of ot the-art chatbot designs and applications. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, 12(1), 2022.

---

[24] Hasan Mesut Meral, Bülent Sankur, A Sumru Özsoy, Tunga Güngör, and Emre Seving. Natural language watermarking via morphosyntactic alterations. Computer Speech & Language. 23(1): 107-125, 2009.
[25] Xupeng Miao, Gabriele Oliaro, Zhihao Zhang, Xinhao Cheng, Zeyu Wang. Rae Ying Yee Wong, Zhuoming Chen, Daiyaan Arfeen, Reyna Abhyankar, and Zhihao Jia. Specinfer: Accelerating generative IIm serving with speculative inference and token tree verification. arXiv preprini arXiv:2305.09781, 2023.
[26] Giovanni Monea, Armand Joulin, and Edouard Grave. Pass: Parallel speculative sampling. arXiv preprint arXiv:2311.1358/ 2023.
[27] Travis Munyer and Xin Zhong. Deeptextmark: Deep learning based text watermarking for detection of large language model generated text. arXiv preprint arXiv:2305.05773, 2023.
[28] Jie Ou, Yueming Chen, and Wenhong Tian. Lossless acceleration of large language model via adaptive n- n-gram parallel decoding. arXiv preprint arXiv:2404.0869) 2024.
[29] Lip Yee Por, KokSheik Wong, and Kok Onn Chee. Unispach: A text- lext-based data hiding method using unicode space characters. Journal of Systems and Software, 85(5):1055-108) 2012.
[30] Jie Ren, Han Xu, Yiding Liu, Yingqian Cui, Shuaiqiang Wang, Dawei Yin, and Jiliang Tang. A robust semantics-based watermark for large language model against paraphrasing. arXiv preprint arXiv:2311.0872 2023.
[31] Stefano Giovanni Rizzo, Flavio Bertini, and Danilo Montesi. Content-preserving text water- marking through unicode homoglyph substitution. In Proceedings of the 20th International Database Engineering & Applications Symposium, pages 97-104, 2016.
[32] Ryoma Sato, Yuki Takezawa, Han Bao, Kenta Niwa, and Makoto Yamada. Embarrassingly simple text watermarks. arXiv preprint arXiv:2310.08920, 2023.
[33] Abigail See, Peter J. Liu, and Christopher D. Manning. Get to the point: Summarization with pointer-generator networks. In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 1073-1083, Vancouver, Canada, July 2017. Association for Computational Linguistics. doi:
[34] Benjamin Spector and Chris Re, Accelerating Ilm inference with staged speculative decoding. arXiv preprint arXiv:2308.0466: 04623, 2023.
[35] Hanshi Sun, Zhuoming Chen, Xinyu Yang, Yuandong Tian, and Beidi Chen. Triforce: Lossless accelcration of long sequence generation with hicrarchical speculative decoding. arXiv preprint arXiv:2404.1 / 1912, 2024.
[36] Zhensu Sun, Xiaoning Du, Fu Song, Mingze Ni, and Li Li. Coprotector: Protect open-source code against unauthorized training usage with data poisoning. In Proceedings of the ACM Web Conference 2022, pages 652-660, 2022.
[37] 7hensu Sun, Xiaoning Du, Fu Song, and Li Li. Codemark: Imperceptible watermarking for code datasets against neural code completion models. In Proceedings of the 31st ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering, pages 1561-1572, 2023.
[38] Ziteng Sun, Jac Hun Ro, Ahmad Beirami, and Ananda Theertha Suresh. Optimal bloek- draft verification for accelerating speculative decoding. arXiv preprint arXiv:2403. 2024.
[39] Ruixiang Tang. Qizhang Feng, Ninghao Liu, Fan Yang, and Xia Hu. Did you train on my dataset? towards public dataset protection with cleanlabel backdoor watermarking. ACM SIGKDD Explorations Newsletter, 25(1):43-555 2023.
[40] Mercan Topkara, Umut Topkara, and Mikhail J Atallah. Words are not enough: sentence level natural language watermarking. Proceedings of the 4th ACM international workshop on Contents protection and security, pages 37-46, 2006.
12

---

[41] Umut Topkara, Mercan Topkara, and Mikhail Atallah. The hiding virtues of ambiguity: quantifiably resilient watermarking of natural language text through synonym substitutions. In Proceedings of the 8th workshop on Multimedia and security, pages 164-174, 2006.
[42] Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timo- thée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al. Llama: Open and efficient foundation language models. arXiv preprint arXiv:2332..33971 2023.
[43] Lean Wang, Wenkai Yang, Deli Chen, Hao Zhou, Yankai Lin, Fandong Meng, Jie Zhou, and Xu Sun. Towards codable text watermarking for large language models. arXiv preprint urXiv22377.15992 2023.
[44] Yihan Wu, Zhengmian Hu, Hongyang Zhang, and Heng Huang. Dipmark: A stealthy, efficient and resilient watermark for large language models. arXiv preprint arXiv:2310.07710, 2023.
[45] Nan Yang. Tao Ge, Liang Wang, Binxing Jiao, Daxin Jiang, Linjun Yang, Rangan Majumder, and Furu Wei. Inference with reference: Lossless acceleration of large language models. arXiv preprint S3I.::2300044487, 2023.
[46] Sen Yang, Shujian Huang. Xinyu Dai, and Jiajun Chen. Multi-candidate speculative decoding. arXiv preprint arXiv:2401.06706 2024.
[47] Xi Yang, Jie Zhang, Kejiang Chen, Weiming Zhang, Zehua Ma, Feng Wang, and Nenghai Yu. Tracing text provenance via context-aware lexical substitution. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 1 1613-11621, 2022.
[48] Xi Yang. Kejiang Chen, Weiming Zhang, Chang Liu, Yuang Qi, Jie Zhang, Han Fang, and Nenghai Yu. Watermarking text generated by black-box language models. arXiv preprint arXiv:2305.000 08883, 2023.
[49] Yioo Yoo, Wonhyuk Ahn, Jiho Jang, and Nojun Kwak. Robust multi-bit natural language watermarking through invariant features. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 2092-2113 2023.
[50] Yoon Yoo, Wonhyuk Ahn, and Nojun Kwak. Advancing beyond identification: Multi-bit watermark for language models. arXiv preprint arXiv:2308.0022,, 2023.
[51] Xuandong Zhao, Prabhanjan Ananth, Lei Li, and Yu-Xiang Wang. Provable robust watermarking for ai-generated text. arXiv preprint arXiv:2306.11 17439, 2023.
[52] Yongchao Zhou, Kaifeng Lyu, Ankit Singh Rawat, Aditya Krishna Menon, Afshin Ros- tamizadeh, Sanjiv Kumar, Jean-François Kagy, and Rishabh Agarwal. Distillspee: Improving speculative decoding via knowledge distillation. arXiv preprint arXiv:2310.08461, 2023.
13

---

A
Related Works
Our work lies at the intersection two active research areas: speculative sampling for accelerated inference and watermarking techniques for language models.
A.1 Speculative Sampling for Accelerated Inference
In the domain of speculative sampling, a common approach is to use smaller language model as the draft model [6 5]. Efforts have been made to further increase the overlap between the draft and target models through distillation [52]. Other works focus on modifying the target model itself, such as adding "look ahead" tokens 26),, introducing new heads to predict future tokens 4 reusing the computation of the large model to achieve better fatency-overlay trade-off for the draft model [9].
or using the target model with partial key-value cache as the draft model (35 Alternative approaches
include using document retrieval 45 9
or n-gram models (2 as the draft model.
When the draft sequence length is greater than one, vanilla speculative sampling is known to be suboptimal. Methods have been proposed to amend the verification process for the draft sequence, verifying the entire sequence once instead of individual tokens, leading longer expected number of accepted tokens [38]
An extension of speculative sampling is to change the sequence imput tree input. While typical language models take a sequence as input, which a path in the symbol tree space, some works modify the input to be tree with multiple branches. A single forward pass then obtain probabilities on multiple branches, gathering more information to help accelerate decoding. This requires modifying the transformer implementation to change the causal attention to tree attention [6] 25 34] Speculative sampling can also be used repeatedly, with an additional draft model to accelerate the draft model itself (34)
Our work is independent of the specific draft model used. While many recent advancements stem from faster and more accurate draft models, method does not rely on any assumptions about the draft model. A better draft model can always be plugged in to provide faster accelcration.
The methods in Section 5 of the main text only consider the basic speculative sampling approach and do not take into account other variants such as verifying the entire sequence, tree verification, or multi-candin multi-candidacy. However, our ideas can be extended to these variants and still maintain either the watermark strength or the sampling efficiency, as discussed in Appendix
A.2 Watermarking Techniques for Language Models
In the domain of watermarking for language models, various approaches have been explored. Some
works attempt to edit existing text to embed watermarks [3] 29 31 32 41 27
47
49 2
24).
Others try to incorporate watermarks during the training phase [2 39 36 37
More closely related our work is the direction of modifying the sampling stage to directly generate watermarked results. Since the pioneering works of Aaronson I and Kirchenbauer et al. 13] watermarking techniques have seen significant development.
To address the bias introduced by watermarking, researchers have proposed skipping watermarking accumulating entropy during the generation process and only adding a watermark when the accumulated entropy exceeds threshold [7]. Hu et al. [12] introduced framework that includes unbiased reweighting and context code history to ensure that the output
on low-entropy tokens 21 43
distribution is strictly unbiased.
Subsequently, many variants have been proposed, including multi-bit watermarks [50 g and more robust watermarking schemes [30
20
14
51
15 Efforts have also been made to search for
better watermark detection methods 44 18.
Our work builds upon the unbiased watermarking framework of Hu et al. 12 and explores the trade-off between watermark strength and sampling efficiency when integrating watermarking with speculative sampling. To the best of our knowledge, this the first work investigate this intersection and provide theoretical insights and practical algorithms for navigating the inherent trade-offs.
14

---

B Proofs
Proof of Lemma
Let =Q. Then have
= a(P.Q) = RE-PE
Σ A(()))
LiE
Note that for all i E Σ, A(ij)) E 1, and thus
Σ
A &
Σ (2(()) = REE
TE
Therefore, we must have A(j = almost surely for random and for all E E. Considering the unbiasedness requirement for the final output distribution, i.e.,
vP Ar, DR..E-P [A R2x(2)] P.
(22)
we obtain Eg~PE [R'(() = = Q.
Proof of Lemma Let Q. Following the proof of Lemma 3 have A(ili) 1 almost surely for random E and for all i E E. Therefore,
RE(P) = Ao R' = (Q)()).
Since (P(P) = (P(P), we conclude that (Q²(Q) = Rg(Q).
Lemma 8 (A Function Equation). Given n monotonically increasing functions F; [0, [0. i (1. Le., x 2 x' = Fl(x) 2 F1(x'), satisfying
Vi
(0 0, Fi(1==1
Σ-=1= - Σ Fz,))) =1
we have F1(1)) = P.(x) a for all (1,,,,,, and [0, 1].
Proof of Lemma 8 We first prove that Fi(x) = P2(x) for all E [0, 1.. Let
0, 22 1 23.
and x; = 0 for 2 We obtain
F2(25) = 1 - F2 Æz).
Next, let 22 0, .g
31, and H; for all 2 4. This gives us
Fi (x1) Fs(1 -x1)
-1 (1 F2(1 xx1))
F2(11).
Similarly, we can show that (x) = Fi(x)) for all E (1, n) and æ E [0.
Next, we prove that for all E and 2n, Fi ( 2 First, let 21 2. #2 2. and m;
for all 2 3. We obtain F1(2) 2"
Assume that for some n, we have (i)h)) = 2n for all b < 2". We will prove that Fi (g
2
for all b < 21+1
For b < 2n,
2n+T.
2
h
= -
b ze
and 0 for all i 2 4. We obtain
Fi
(T)))) ((
DTTT.
For 2 b 1 let F1
2nII+ 22
2nII. and D 0 for all i 2 3. We obtain
Fi b 2
By mathematical induction, we have Fi
b 2m
for all n E N and < 2".
2
Since F1 is monotonically increasing, for all E [0. and n E N, we have
r
Fi
<
(x) S Fi
2n
n
15

---

Taking the limit as n + oo, we obtain
[22"
lim
Fi
= I 2n
2=000
[x:2%]
lim
Fi
I: 2
7-000
Therefore, Fi(x)) for all [0, 1), and consequently, F.(x)) for all i .1, and x E [0,
Proof of Theorem 5 First, we have (P) (Ao R))(() (A (Q). For any j E E,
Rg(P))) Σ (Q)))
(nin(Rr(QQ))),,
- (141)1000BB//1))))))44010000000- Rc(())))
= (iin(Rg(Q)O))))) RE(P)()) ( + (RE(P) - -RE())))+
-RE(P)
Therefore, (g(P) Rg)P), which means the watermark strength is maintained.
To prove the unbiasedness of the generation distribution, note that for all P E Ag.
PE~PE [gg [P) = PE~Ps [Re(P] = P.
where the last equality follows from the unbiasedness of the reweighting function Rg. Proof of Theorem
To prove that the sampling efficiency is maintained, we have
Eg~PE
Σ (()())
= EE~PE PRe
(())))
LE
E
((1)))((1
E
min(Q(()P(())
=PP,QQ).
To prove the unbiasedness the generation distribution, we have for any j E.
Eg-PS (P) = RE-PE Σ (G)))E(()())))
AGGi)Q())
min(QU),P)) + Σ (Q(1) - -P) Q0)) igj ((2) P(=))+
min(Q(), P()) + (P()) - QQ1))
P(j).
Therefore, EE-PS (RE()(RRPP)) P for all E As, which means the generation distribution is unbiased.
16

---

C
Algorithms
Algorithm 2 Basic Sampling
Given generated sequence length K, prompt 21,... .... Zn. target model P(-I-). Initialize empty output list: out 4- []
for 1 K do
Compute distribution Pt(-)- = P(-(01,.... Fay Fnth.-.. Fntt-1).
Sample token In++ P.. Set out + out + [nats]-
end for
Return out as generated tokens.
Algorithm 3 Vanilla Speculative Sampling
Given draft sequence length K, prompt Fi,..., Fn. target model P(-I-), and draft model Q(-I-).
for t = 1 K do
Compute distribution Q+(-) Q(- In, .1-1). Sample draft token 3, Q.- end for for
1: K in parallel do Compute distribution P+(-) end for Initialize empty output list: out do
Tng 31, .
for t
Sample U(0 1] from uniform distribution.
if min(1, Pa(āx) then Set oul +- out [.t]. else Q((ee) Sample Intt (P. Qi)+. Set out +- out + [xn+c]. Exit for loop.
end if end for if out _i,..... Ex] then
Sample 2n K+1 PK+1- Set out +- out + [xn+
end Return out as generated tokens.
Algorithm 4 Vanilla Unbiased Watermark Method
Given generated sequence length K, prompt Ti...., Zn. target model P(-I-), code history cch as a list of context code, context code function oe E* -> C, watermark code generation function É. C' Z + &, reweighting functions R: As. + As, and key for watermark z E Z. Initialize empty output list: oul.
for / 1 K do Compute context code e co(a1,............... Ina In+l. Inte-1), watermark code E. Elcc, 2).
Check skipped skippede true e exists in ech,
Set cch cch [ct].
false a doesn't exists cch. Compute distribution Pi(-) P(- Tn, (,nt-+,
Pt
skipped, = true, Sample token zatt ~ Br. Set out + out + [mn+]].
Let q. = RE, (P.) skipped, = false.
end for Return out as generated tokens.
D U Score, DeltaGubel Reweight, and Gamma Reweight
In this section, we provide detailed definitions of the U score, DeltaGumbel reweight, and Gamma reweight schemes, which used in the main text to compute the P-value for detecting watermarks.
17

---

D.1 DeltaGumbel Reweight
In the DeltaGumbel reweight scheme, the watermark code i'is a list of |Σ] independent and identically distributed standard Gumbel variables. The reweighting function is defined as:
RE(P) 6at, a" := argmax, (log P(a) E(a))
(23)
where 5 is the Dirac delta function centered at a".
The U score for the DeltaGumbel reweight is defined as:
U exp(-exp(-EE(t)) E [0,
(24)
there no watermark added while generating æ, other word, if the token independent with E, then the random U is uniformly distribution in [0, I].
The logarithm of the moment-generating function (MGF) of the U score for the DeltaGumbel reweight is given by:
log Elexp(AUU) = log (A) + log (e^ - 1).
(25)
D.2 Gamma Reweight
In the Gamma reweight scheme, the watermark code E is random bijection from E to the set {0, 1.,,..., | - 13. The reweighting function defined as:
Rg(P)(t) = A (E(t(E(t)) (E,P(E(t) - 1),
(26)
(g. = max 2
Σ I(((()) S ())(() - 1,, LEE
(27)
The U score for the Gamma reweight is defined as:
E(x) Σ
E [0.
(28)
there no watermark added while generating æ, other word, if the token is independent with E, then the random U is uniformly distribution in f {12) 19
|X|-
The logarithm of the moment- function (MGF) of the U score for the Gamma reweight is given by:
2|x )
A + log (e* 1).
log E|Ux)(AUU) - -log || sinh(
(29)
Both the DeltaGumbel reweight and Gamma reweight schemes are unbiased [12], meaning that for any distribution P E Ast, we have:
(R>P)(Re(P)) = P.
(30)
The U scores defined for these reweight schemes are likelihood-agnostic, which means that they do not depend on the original distribution P. This property makes them possibly more robust to perturbations compared to likelihood-basee scores such as the LLR score.
To compute the P-value for detecting watermarks using the U score, substitute the correspond-
ing MGF into Equation
E
Extension to Variants of Speculative Sampling
The analysis and process presented in Section focus on the basic speculative sampling approach, where a single draft token is sampled and then accepted or rejected. Algorithm aapply such process multiple times, accepting or rejecting tokens one by one, similar to vanilla speculative sampling.
Recent developments in speculative sampling have introduced various new techniques, such as verifying the entire sequence, tree verification, multi-candidacy (see Appendix A for details).
18

---

While Algorithm 1 in Section does not explicitly consider these variants, the underlying ideas can be directly extended general speculative sampling approaches.
To maintain the watermark strength, the intuition is to apply the watermark to the draft tokens by sampling them from the watermarked draft model distribution, denoted Que Then, the watermarked target distribution Pw. is computed, and speculative sampling is performed, treating Q as the draft model and P. as the target model. Since speculative sampling ensures that the generated content follows the distribution of the target model, the final generated results will be drawn from the distribution Pu. Consequently, the watermark strength remains unchanged compared to directly sampling from P...
To maintain the sampling efficiency, the intuition is apply the watermark to the draft tokens by sampling them from the watermarked draft model distribution Qu- Then, speculative sampling is performed, treating Q the draft model and P as the target model. Under the expectation of random watermark codes, the draft tokens follow the distribution Q. Therefore, the efficiency of speculative sampling remains unchanged compared directly sampling draft tokens from Q.
These arguments do not depend on the specific form speculative sampling, and do not assume the structure of the draft tokens and draft models, making the ideas presented in Section applicabll to various speculative sampling variants.
We acknowledge that experimental validations would be helpful to demonstrate the effectiveness of the extended methods in practice. However, due to implemenatioonlooppaatioo cost and the focus of this paper on the foundational theory, we only present high-level discussion and left out the empirical validations for extended methods.
F Broader Impacts
This paper presents work whose goal is to accelerate the generation speed of existing watermarking methods for large language models. There are several potential positive societal impacts of our work. By making watermarking techniques more practical and efficient, it may encourage their wider adoption. This can help protect the intellectual property rights.
However, there are also potential negative societal impacts to consider. Although our unbiased watermarking approach ensures the validity of the model outputs is not compromised, there is risk that watermarking techniques could be abused. For example, unbiased watermarks are undetectable, which could enable tracking and surveillance, raising privacy concerns.
To mitigate potential negative impacts, important that watermarking techniques are used responsi- bly. This includes transparency about the use of watermarks, obtaining user consent where applicable, and putting safeguards in place to prevent misuse.
In conclusion, while our work on accelerating watermarking for language models has the potential to encourage wider adoption and protect intellectual property, is important to carefully consider and address potential negative societal impacts to ensure the technology is used responsibly and ethically.
G Limitation
Our work makes significant contributions to the field of watermarking and speculative sampling for large language models, but it also has several limitations.
In terms of thcoretical analysis, the no-go theorem assumes specific two reweight framework. Although this framework is general, it is possible that other frameworks or methods may lead to different theoretical results. This paper represents the first exploration in this direction, and the two reweight framework is also the first attempt. Future work may discover more powerful frameworks that yield different insights.
Regarding experimental validation, we use relatively small language models and basic draft model. While our experiments verify the effectiveness of the theory, the acceleration ratio may not represent the oa-t--of-thearr Speculative sampling techniques have been developing rapidly in recent times. combined with the latest advances, it should be possible to achieve even higher Average Accepted
19

---

Tokens Per Step (AATPS) and lower Per Token Time (PTT), though it is not directly related to our main contribution.
The choice draft sequence length critical in the deployment. Most of the existing methods select the optimal draft sequence length based on trial and error. This paper does make contributions to determining the optimal draft sequence length. However, it should be noted that the maintain watermark strength (MWS) method proposed in this paper reduces the speculative efficiency, which also affects the selection of the optimal draft sequence length. Care should be taken in the deployment optimally select this parameter.
the maintain watermark strength (MWS) method is used, the inference speed will decrease slightly. This creates a side channel, and users may infer from this whether the backend service uses the MWS algorithm, which compromises the undetectability of the watermark.
Despite these limitations, our work provides valuable insights and advances the tatte-of-the-art in watermarking and speculative sampling techniques for large language models. We hope our findings will stimulate further research to realize the full potential of these techniques.
H Additional Experiment Results
20

---

(a) DeltaGumbel Reweight
1.2
0.25
Basic
Basic
1.0
VUW
ANL (ILPPT(UU Score)
0.20
VUW
VSpS
VSpS
0.8
MWS
0.15
MSE
MSE
0.6
0.10
0.4
K=2
K=2
0
0.2
K=3
O
0.05
K=3
K=4
K=4
0.0
0.00
1.25
1.00
1.25
2.00
AATPS
AATPS
Gamma Reweight
0.20
0.07
Basic
0.06
Basic
ANL ANLPPT(U Score)
ANLPPT(maximin-
0.15
VSpS
0.05
VSpS
MWS
0.04
MW5
0.10
MSE
MSE
0.03
0
K=1
K=1
0.05
0
K=2
0.02
K=2
K=3
K=3
0.01
K-4
K-4
0.00
1.00
1.25
1.50
1.75
2.00
1.00
1.25
1.50
1.75
2.00
AATPS
AATPS
Figure 3: Text summarization task with LLaMa-1 3b model model 25 reference model.
42 as target model and LLaMa-68m
21

---

(a) DeltaGumbel Reweight
D OG
OB
2.0
ANLPPT (PT(mmaxminn-LL)
Basic
0.4
Basic
VUW
ANLPPT(U Score)
vUW
1.5
VSpS
VSpS
0.3
MWS
MWS
MSE
MSE
1.0
0.2
K=1
0.5
K=2
K=3
o
K=3
K=4
K=4
0.0
0.0
Q-8
1.25
2.00
AATPS
AATPS
Gamma Reweight
+
(ULPP(mmxxiinn LLR)
0.35
0.12
Basic
Basic
ANL ANLPP((U Score)
0.10
VSpS
VSpS
MWS
0.08
MW5
0.20
MSE
MSE
0.06
0.15
0
K=1
K=1
0.04
0.10
0
K=2
K=2
0.05
K=3
0.02
K=3
K-4
K-4
0.00
0.00
0-8-
1.00
1.25
1.50
1.75
2.00
1.00
1.25
1.50 AATPS
1.75
2.00
AATPS
Figure 4: Open-ended text generation task with LLaMa-7b model 68m model (25) reference model.
42
as target model and LLaMa-
22

---

(a) DeltaGumbel Reweight
2.0
O
0.4
Basic
0
Basic
ANLPPT (wa.iiimimiinnLL
1.5
VUW
ANLPPT(U Score)
VUW
VSpS
0.3
VSpS
MWS
MWS
1.0
MSE
MSE
0.2
K=1
0.5
K=2
0.1
K=2
C
Q8
K=3
o
K=3
K=4
K=4
0.0
0.0
AATPS
AATPS
Gamma Reweight
O O
0.35
0.12
WWLPPT(mxxmin- LL.)
Basic
Basic
0.30
ANL UILPPT(U Score)
0.10
0.25
VSpS
VSpS
0.08
MWS
MW5
0.20
MSE
0.06
MSE
0.15
0
K=1
0.04
K=1
0.10
D
K=2
K=2
O
0.05
K=3
0.02
K=3
K-4
K-4
0.00
0.00
1.0
1.2
1.4
1.6
1.8
1.0
1.2
1.4
1.6
1.8
AATPS
AATPS
Figure 5: Open-ended text generation task with LLaMa- 13b model 68m model (25) reference model.
42
as target model and LLaMa-
23

---

K
method
reweight
AATPS
PTT
LOGPPL
Basic
No Reweight
1.0
29.58 0.07
1.75
VUW
DeltaGumbel
1.0
30.40 = 0.07
1.77
VUW
Gamma
1.0
32.81 0.07
1.74
VSpS
No Reweight
1.5508 + 0.0017
21.64 0.06
1.76
MSE
DeltaGumbel
1.5494
0.0017
22.58 0.06
1.77
MSE
Gamma
1.5504 0.0017
25.15
1.74
MWS
DeltaGumbel
1.5105 0.0017
23.24 0.07
1.77
MWS
Gamma
1,5312 0.0017
25.57
1.76 0.03
2
VSpS
No Reweight
1.857 + 0.003
19.41 0.07
1.04
2
MSE
DeltaGumbel
1.853 + 0.003
20.46 0.07
1.78 0.03
MSE
Gamma
1.856 + 0.003
23.42 0.08
1.73 0.03
MWS
DeltaGumbel
+.0003
21.50 0.08
1.77
MWS
Gamma
1.818 = 0.003
25.29 0.09
1.73
VSpS
No Reweight
2.028 + 0.004
19.03 = 0.08
1.75
3
MSE
DeltaGumbel
2.022 + 0.004
20.24 0.09
1.77
MSE
Gamma
2.026 + 0.004
23.98 = 0.10
1.74
3
MWS
DeltaGumbel
1.913 = 0.004
=
1.76
MWS
Gamma
1.969 = 0.004
0.11
1.75 +.08
4
VSpS
No Reweight
2.132 + 0.005
0027=0000
1.72 0.08
0.03
MSE
DeltaGumbel
2.125 + 0.005
20.79
1.73
4
MSE
Gamma
2.132 + 0.005
1.71 0.03
MWS
DeltaGumbel
1.987 = 0.005
22.20
0.03
4
MWS
Gamma
2.061 + 0.005
27.14 + 0.14
+ 0.03
K
method
reweight
ANLPPT(U Score)
ANLPPT(maximin-LLLR)
1
Basic
No Reweight
0.0 = 0.0
0.0 0.0
1
VUW
DeltaGumbel
0.376 + 0.009
1.71 + 0.03
1
VUW
Gamma
0.097 + 0.002
0.272 + 0.005
1
VSpS
No Reweight
0.0 0.0
0.0
1
MSE
DeltaGumbel
0.153 = 0.004
0.640 0.014
1
MSE
Gamma
0.0433 0.0012
0.0011
1
MWS
DeltaGumbel
0.374 + 0.009
1.71
MWS
Gamma
0.098 + 0.002
0.275 0.005
2
VSpS
No Reweight
0.0 0.0
0.0 0.0
2
MSE
DeltaGumbel
0.111 + 0.003
0.419 + 0.010
2
MSE
Gamma
0.0322 0.0010
0.0310 + 0.0014
2
MWS
DeltaGumbel
0.374 + 0.009
1.71 + 0.03
2
MWS
Gamma
0.096 + 0.002
0.272 + 0.005
3
VSpS
No Reweight
0.0 + 0.0
0.0 # 0.0
3
MSE
DeltaGumbel
0.094 + 0.003
0.331 0.009
3
MSE
Gamma
0.0281 + 0.0009
0.0214 + 0.0012
3
MWS
DeltaGumbel
0.374 + 0.009
1.70 + 0.03 0.03
3
MWS
Gamma
0.097 + 0.002
0.274 + 0.005
4
VSpS
No Reweight
0.0 0.0
0.0 + 0.0
4
MSE
DeltaGumbel
0.083 + 0.002
0,280 + 0.008
4
MSE
Gamma
0.0258 0.0008
0.0007
4
MWS
DeltaGumbel
0.375 + 0.009
1.71
4
MWS
Gamma
0.096 + 0.002
0.271 0.005
Table 1: Text summarization task with LLaMa-7b model [42] as target model and LLaMa-68m model
25 as reference model.
24

---

K
method
reweight
AATPS
PTT
LOGPPL
Basic
No Reweight
1.0
46.169 0.012
1.27 = 0.03
VUW
DeltaGumbel
1.0
46.956 1 0.012
1.110000
VUW
Gamma
1.0
19.333
1.28 0.03
VSpS
No Reweight
31.94
1.24 0.03
MSE
DeltaGumbel
1.5639 0.0017
32.81 0.06
1.30 0.03
MSE
Gamma
1.5643 0.0017
35.35 + 0.06
1.26 0.03
MWS
DeltaGumbel
1.5307 0.0017
13.62
1.31 0.03
MWS
Gamma
1.5476 0.0017
35.86 0.07
1.29 E 0.03
VSpS
No Reweight
1.884:0.40
27.91 + 0.09
1.29 + 0.03
2
MSE
DeltaGumbel
1.878 0.003
28.98 + 0.09
1.34 0.03
MSE
Gamma
1.884 0.003
31.89 0.10
1.30 0.03
MWS
DeltaGumbel
1.815 + 0.003
30.05 + 0.11
1.32 - 0.03
MWS
Gamma
1.850 = 0.003
33.59 + 0.11
1.29 = 0.03
VSpS
No Reweight
2.072 + 0.005
26.60 + 0.11
1.24 + 0.03
MSE
DeltaGumbel
2.060 0.005
27.94 +.12 0.12
1.31 + 0.03
MSE
Gamma
2.066 + 0.005
31.63 + 0.13
1.28 + 0.03
MWS
DeltaGumbel
1.972 0.004
29.26 0.13
1.32 + 0.03
MWS
Gamma
2.016 0.004
33.45 0.15
1.30 0.03
4
VSpS
No Reweight
2.181 + 0.006
26.36 + 0.12
1.27 + 0.03
MSE
DeltaGumbel
2.171 = 0.006
28.00 + 0.13
1.30 = 0.03
4
MSE
Gamma
2.176 0.006
32.44 + 0.15
1.28 + 0.03
MWS
DeltaGumbel
2.059 0.005
29.51 + 0.16
1.31 0.03
4
MWS
Gamma
2.119 + 0.005
34.32 + 0.17
1.29 + 0.03
K
method
reweight
ANLPPT(U Score)
ANLPPT(maxxmin-LLLR)
1
Basic
No Reweight
0.0 - 0.0
0.0 0.0
1
VUW
DeltaGumbel
0.260 + 0.009
1.27 + 0.03
1
VUW
Gamma
0.067 + 0.002
0.200 + 0.005
1
VSpS
No Reweight
0.0
0.0 0.0
1
MSE
DeltaGumbel
0.103 0.004
0.448 0.014
1
MSE
Gamma
0.0297 0.0011
+
1
MWS
DeltaGumbel
0.260 + 0.009
1.27 0.03
MWS
Gamma
0.068 + 0.002
0.201 0.005
2
VSpS
No Reweight
0.0 0.0
0.0 0.0
2
MSE
DeltaGumbel
0.076 + 0.003
0.292 + 0.010
2
MSE
Gamma
0.0226 0.0009
+ 4 0.0012
2
MWS
DeltaGumbel
0.261 + 0.009
1.27 + 0.03
2
MWS
Gamma
0.069 + 0.002
0.201 + 0.005
3
VSpS
No Reweight
0.0 + 0.0
0.0 + 0.0
3
MSE
DeltaGumbel
0.063 + 0.002
0.224 0.008
3
MSE
Gamma
0.0199 + 0.0008
0.0098 + 0.0011
3
MWS
DeltaGumbel
0.261 + 0.009
1.27+ 0.03 0.201 + 0.006
3
MWS
Gamma
0.068 + 0.002
4
VSpS
No Reweight
0.0 + 0.0
0.0 0.0
4
MSE
DeltaGumbel
0.057 + 0.002
0.192 + 0.007
4
MSE
Gamma
0.0007 0.0184 = 0.0007
0.0069 + 0.0009
4
MWS
DeltaGumbel
0.260 + 0.009
1.27 0.08
4
MWS
Gamma
0.068 + 0.002
0.202 0.005
Table 2: Text summarization task with LLaMa-13b model [42 as target model and LLaMa-68m
model (25 reference model.
25

---

K
method
reweight
AATPS
PTT
LOGPPL
Basic
No Reweight
1.0
30.20 + 0.08
2.161
VUW
DeltaGumbel
1.0
31.06 - 0.08
2.147
VUW
Gamma
1.0
33.34 0.09
2.158
VSpS
No Reweight
22.69 + 0.07
+158++0011
MSE
DeltaGumbel
1.500440.000
23.52+0.00
+.100+00014
MSE
Gamma
1.5001 0.0016
26.30 0.07
2.160
0.014
MWS
DeltaGumbel
1.4546 0.0016
0.007
2.147
=117=00011 0.014
MWS
Gamma
1.4753 0.0016
2.067
2.151
0.014
VSpS
No Reweight
1.755 0.003
2.00
2
MSE
DeltaGumbel
1.753 0.003
4.933
2.152
# 0.014
MSE
Gamma
1.754 0.003 0.003
25.00
+ 0.014
MWS
DeltaGumbel
1.665 0.003
23.11 0.07
2.147 0.014
MWS
Gamma
1.704 0.003
27.28 0.09
4.011
VSpS
No Reweight
1.883 + 0.004
20.57 0.08
2.148 = 0.014
2
MSE
DeltaGumbel
1.881 + 0.004
22.08 0.08
0.014
MSE
Gamma
1.882 + 0.004
25.97 + 0.09
2.143
MWS
DeltaGumbel
1.763 + 0.004
2.145 23.71 0.08
MWS
Gamma
1.817 0.004
28.23 + 0.10
2.153 0.014
4
VSpS
No Reweight
1.950 + 0.005
21.35 + 0.08
2.153 = 0.014
MSE
DeltaGumbel
1.946 + 0.005
23.10 #.09
2.153
4
MSE
Gamma
1.951 + 0.005
28.10 0.11
MWS
DeltaGumbel
1.809 0.004
24.65 + 0.09
2.146 0.014
4
MWS
Gamma
1.872 + 0.004
30.24 + 0.12
2.148 + 0.014
K
method
reweight
ANLPPT(U Score)
ANLPPT(maximin-LLRR
1
Basic
No Reweight
0.0 0.0
0.0 0.0 2.101 + 0.014
1
VUW
DeltaGumbel
0.467 + 0.005
1
VUW
Gamma
0.1291 + 0.0015
0.3762 + 0.0018
1
VSpS
No Reweight
0.0 0.0
0.0
1
MSE
DeltaGumbel
0.189 0.003
0.771 + 0.008
1
MSE
Gamma
0.0567 0.0010
0.0862 + 0.0014
1
MWS
DeltaGumbel
0.466 + 0.005
2.100 + 0.014 0.014
MWS
Gamma
0.1283 + 0.0015
0.3759 0.0018
2
VSpS
No Reweight
0.0 0.0
0.0 0.0
2
MSE
DeltaGumbel
0.133 + 0.002
0.494 + 0.007
2
MSE
Gamma
0.0411 + 0.0008
0.0455 + 0.0011
2
MWS
DeltaGumbel
0.467 + 0.005
2.101 + 0.014
2
MWS
Gamma
0.1285 + 0.0015
0.3752 + 0.0017
3
VSpS
No Reweight
0.0 0.0
0.0 0.0
3
MSE
DeltaGumbel
0.1116 0.0019
0.385 0.006
3
MSE
Gamma
0.0354 +: 0.0008
0.0309 + 0.0010
3
MWS
DeltaGumbel
0.466 + 0.005
2.099 + 0.014
3
MWS
Gamma
0.1292 - 0.0015
0.3765 + 0.0017
4
VSpS
No Reweight
0.0 0.0
0.0 0.0
4
MSE
DeltaGumbel
0.1030 + 0.0018
0.340 0.005
4
MSE
Gamma
0.0325 0.0007
0.0250 + 0.0009
4
MWS
DeltaGumbel
0.465 + 0.005
2.099 + 0.014
4
MWS
Gamma
0.1286 + 0.0015
0.3761 + 0.0017
Table 3: Open-ended text generation task with LLaMa-7b model 42
as target model and LLaMa-
68m model (25) reference model.
26

---

K
method
reweight
AATPS
PTT
LOGPPL
1
Basic
No Reweight
1.0
44.982 + 0.012
2.087 0.014
1
VUW
DeltaGumbel
1.0
45.766 0.012
2.062 0.013
1
VUW
Gamma
1.0
48.030 0.017
2.086 0.014
1
VSpS
No Reweight
1.4879:11 0.0016
32.55 0.04
2.076 + 0.013
MSE
DeltaGumbel
1.4891 0.0006
33.40 0.04
2.071 0.013
1 MSE
Gamma
1.4883 0.0016
35.78 0.05
2.073 + 0.014
MWS
DeltaGumbel
1.449 0.0016
34.52 0.05
2.063 = 0.013
1
MWS
Gamma
1,4636 = 0.0016
36.55 0.05
2.073 + 0.013
2
VSpS
No Reweight
1.734 + 0.003
29.32 0.06
2.071 + 0.013
2
MSE
DeltaGumbel
1.732 1: 0.003
30.39 0.06
2.074 0.014
2
MSE
Gamma
1.731 - 0.003
33.50 0.07
2.081 + 0.014
2
MWS
DeltaGumbel
1.646 = 0.003
32.07 0.07
2.066 + 0.013
2
MWS
Gamma
1.683 = 0.003
35.64 0.07
2.076 0.013
3
VSpS
No Reweight
1.854 + 0.004
28.76 = 0.07
2.071 0.014
3
MSE
DeltaGumbel
1.853 + 0.004
30.05 0.08
2.075 - 0.014
3
MSE
Gamma
1.855 + 0.004
33.97 = 0.09
2.070 0.011
3
MWS
DeltaGumbel
1.738 = 0.004
32.15 0.08
2.064 0.013
3
MWS
Gamma
1.790 0.004
36.37 = 0.09
2.080 = 0.014
4
VSpS
No Reweight
1.913 + 0.004
29.05 0.08
2.074 + 0.014
4
MSE
DeltaGumbel
1.914 + 0.004
30.69 0.09
2.072 = 0.013
4
MSE
Gamma
1.915 = 0.004
35.47 0.10
2.075 + 0.014
4
MWS
DeltaGumbel
1.781 = 0.004
33.09 0.09
2.062 0.013
4
MWS
Gamma
1.836 + 0.004
38.21 0.11
2.072 + 0.013
K
method
reweight
ANLPPT(U Score)
ANLPPT(maximin-LLLR)
1
Basic
No Reweight
0.0
0.0 0.0
1
VUW
DeltaGumbel
0.441 + 0.005
2.016 0.013
1
VUW
Gamma
0.1245 + 0.0015
0.3692 + 0.0017
1
VSpS
No Reweight
0.0 0.0
0.0
1
MSE
DeltaGumbel
0.176 0.003
0.724 + 0.008
1
MSE
Gamma
0.0527 0.0009
0.0794 + 0.0013
1
MWS
DeltaGumbel
0.441 + 0.005
2.017 + 0.013 0.013
MWS
Gamma
0.1226 + 0.0014
0.3680 0.0017
2
VSpS
No Reweight
0.0 + 0.0
0.0 + 0.0
2
MSE
DeltaGumbel
0.122 + 0.002
0.457 + 0.006
2
MSE
Gamma
0.0387 + 0.0008
0.0405 + 0 0.0011
2
MWS
DeltaGumbel
0.442 + 0.005
2.019 0.013
2
MWS
Gamma
0.1238 + 0.0014
0.3691 + 0.0017
3
VSpS
No Reweight
0.0 10::00 0.0
0.0 0.0
3
MSE
DeltaGumbel
0.1036 0.0018
0.357 0.006
3
MSE
Gamma
0.0330 + 0.0007
0.0279 + 0.0010
3
MWS
DeltaGumbel
0.442 + 0.005
2.018 + 0.013
3
MWS
Gamma
0.1240 + 0.0014
0.3691 + 0.0017
4
VSpS
No Reweight
0.0
0.0 0.0
4
MSE
DeltaGumbel
0.0943 + 0.0017
0.311 + 0.005
4
MSE
Gamma
0.0308 - 0.0007
0.0219 + 0.0009
4
MWS
DeltaGumbel
0.441 - 0.005
2.016 + 0.013
4
MWS
Gamma
0.1237 0.0014
0.3689 0.0017
Table 4: Open-ended text generation task with LLaMa-13b model 42 as target model and LLaMa-
68m model [25) reference model.
27

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification:
We summarize the main contributions at the end of Section [
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: See Appendix
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
28

---

Justification:
The conditions under which our theory holds are clearly stated in Theorems |
and 6 are clearly stated.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: All code is provided in the supplementary.
Guidelines:
The answer NA means that the paper does include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
29

---

Answer:
[Yes]
Justification:
All code is provided in the supplementary. Data can be obtained online.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://niis.. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https guwdes/ddeeeeee Cooeeeoodeesssseeeeeee //nips.com htce///bbb//uuddddd//eeeeeieisss ssiniiiiccypyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
Justification: The definition of algorithm and metrics used in the experiments are reported in the paper. Code is provided.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
[Yes]
Justification:
We report 30 interval in Figure and Appendix H
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
30

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative emror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: As reported in Section 6 the total computational cost for reproducing all the experiments in this paper is approximately 1200 A6000 GPU hours.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (c.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics http://urrr..cccpp.accccccccceee
Answer: [Yes]
Justification:
We have reviewed the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: See Appendix
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
31

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper doesn't 'tt release new data model.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We cite See al. 33 Hermann et al. 10 for CNN_ DAILYMAIL dataset.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
32

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: No human subject is involved in this study.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
No human subject is involved this study.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
33


Reviews:
[{"review_id": "uS2oN4FcOx", "reviewer": "Reviewer_N92a", "summary": "This paper proposes it is impossible to maintain the highest watermark strength and sampling efficiency simultaneously for content generation by considering integrating an unbiased watermarking method [1] and speculative sampling strategy [2] [3], where they provide rigorous theoretical analysis and empirical results.\n\n[1] Hu, Zhengmian, et al. \"Unbiased watermark for large language models.\" arXiv preprint arXiv:2310.10669 (2023).\n[2] Leviathan, Yaniv, Matan Kalman, and Yossi Matias. \"Fast inference from transformers via speculative decoding.\" International Conference on Machine Learning. PMLR, 2023.\n[3] Chen, Charlie, et al. \"Accelerating large language model decoding with speculative sampling.\" arXiv preprint arXiv:2302.01318 (2023).", "questions": "Please refer to the *Weakness* part.", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "This paper focuses on an interesting direction integrating the watermarking method and speculative sampling to accelerate the sampling efficiency while maintaining the watermark strength. It helps us understand the interactions and tradeoffs between watermarking and sampling for content generation in LLM, which is significant.", "weaknesses": "1. Why do the authors mean by \"naively applying speculative sampling to a watermarked target distribution may significantly reduce the overlap probability with the draft distribution Q.\" as in the 112-nd line?\n\n2. In Fig.2 (a) (b), for MWS, the sampling efficiency (AATPS) is only a little smaller than that of VSpS and MSE. For example, for K=2 in (a) in terms of U score, the AATPS of MWS is smaller than that of VSpS or MSE by about less than 0.1, which should be acceptable since it achieves comparable watermark strength with VUW. \n\nIt seems inconsistent with the claim that simultaneously accelerating the sampling efficiency while maintaining the watermark strength is impossible. May the authors explain this result?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful comments and for recognizing the significance of our work. We are grateful for the opportunity to address your questions.\n\n> Why do the authors mean by \"naively applying speculative sampling to a watermarked target distribution may significantly reduce the overlap probability with the draft distribution Q.\" as in the 112-nd line?\n\nThe overlap probability is defined as $\\alpha(R_E(P),Q)$, where $R_E(P)$ is the watermarked target distribution and $Q$ is the draft distribution. Note that the total variation distance is a convex function, and $\\mathrm{TV}(P,Q)=1-\\alpha(P,Q)$. Applying Jensen's inequality, we have:\n\n$\\mathbb{E}_E[\\alpha(R_E(P),Q)]\\leq\\alpha(\\mathbb{E}_E[R_E(P)],Q)=\\alpha(P,Q)$\n\nIn practice, the gap in Jensen's inequality can be quite large, leading to a significant reduction in the average overlap probability.\n\n> In Fig.2 (a) (b), for MWS, the sampling efficiency (AATPS) is only a little smaller than that of VSpS and MSE. For example, for K=2 in (a) in terms of U score, the AATPS of MWS is smaller than that of VSpS or MSE by about less than 0.1, which should be acceptable since it achieves comparable watermark strength with VUW.\n\nWe agree with your observation that the sampling efficiency (AATPS) of MWS is only slightly lower than that of VSpS and MSE. We believe that MWS is highly suitable for practical use as it maintains watermark strength while achieving performance close to VSpS.\n\n> It seems inconsistent with the claim that simultaneously accelerating the sampling efficiency while maintaining the watermark strength is impossible. May the authors explain this result?\n\nWe would like to clarify that our findings do not contradict the no-go theorem. Even though the sampling efficiency of MWS is nearly as high as that of VSpS, there is still a statistically significant gap. The specific data can be found in Table 1, where the AATPS for MWS is 1.773 ± 0.003, and for VSpS, it is 1.857 ± 0.003. The no-go theorem states that theoretically, there will always be a gap, and our experiments demonstrate that this gap is small in practice. The two are not contradictory.\n\nIf you have any further questions or concerns, please do not hesitate to ask. We are more than happy to address all of your inquiries.\n\nWe would also like to emphasize that our work is not only significant but also highly original. We propose simultaneously accelerating sampling while incorporating watermarks, introduce the no-go theorem, and present two novel algorithms, MWS and MSE. All of these contributions are the first of its kind.\n\nConsidering our additional explanations, we would be extremely grateful if you could re-evaluate our work. Thank you once again for your valuable feedback and for your time in reviewing our paper.", "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": "SWkTi5FSJS", "reviewer": "Reviewer_WMzV", "summary": "This paper studies the trade-offs between sampling efficiency and watermark strength to see if LLMs can generate watermarked output efficiently. It is proven in this work that it is not possible to simultaneously maintain the highest watermark strength and the highest sampling efficiency. Therefore, upon the no-go theorem, the paper provides two methods to maintain either one of them and conducts experiments to validate the effectiveness methods.", "questions": "Is the no-go theorem also true for other watermarking algorithm such as KGW[1]?\n\n[1] A watermark for large language models", "limitations": "Although the experiments demonstrated the no-go theorem and effectiveness of proposed methods, maybe more analysis can be provided.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper provides the first study into the relationship between sampling efficiency and watermark strength, which is a practical common interest.\n2. This paper provides proof of the no-go theorem that it is not possible to simultaneously maintain the highest watermark strength and the highest sampling efficiency.\n3. From experiments, the effectiveness of proposed methods are validated clearly with visualizations.\n4. Figure 1 provides an overview of the paper, which is clear and informative.", "weaknesses": "1. Experiment section is relatively short and can include more analysis of the proposed methods on aspects such as ablation study.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable feedback and recognizing our research as the first study into the relationship between sampling efficiency and watermark strength.\n\nRegarding the experiment section, we agree that it appears to be relatively short in the main paper due to space limit. To provide a more comprehensive evaluation, we have moved additional experiments to Appendix H, where we consider different models and tasks. To summarize, all conclusions in Section 6 are still maintained in these experiments: the MWS method achieves the same watermark strength as the VUW method, while the MSE method maintains the same sampling efficiency as the VSpS method, all without compromising the output quality.\n\nFurthermore, our experiments allow us to observe the impact of entropy on watermark strength. We consider two tasks: open-ended text generation, which has higher entropy, and text summarization, which has lower entropy. We measure watermark strength using ANLPPT and find that it is higher for the open-ended text generation task. We also observe the influence of model size, with larger models having a slower Per Token Time (PTT) and different target model-draft model pairs resulting in different Speculative efficiency.\n\nOverall, our experiments serve as a validation study, confirming that the properties stated in the Theorem 1,5,6 are indeed observed in practice. The total experimental cost amounts to 1,200 A6000 GPU hours.\n\n> Is the no-go theorem also true for other watermarking algorithm such as KGW[1]?\n\nSince KGW is not an unbiased watermark, our no-go theorem does not directly apply. According to [2,3], KGW leads to a decrease in generation quality. Although KGW is not an unbiased watermark, the intuition guided by unbiased watermarks may still be applicable to biased watermarks, but the precise formulation remains unclear. The theorem cannot simply discard the unbiased reweight constraint, as it would weaken the condition and invalidate the conclusion. Characterizing non-trivial biased watermarks and proving a corresponding no-go theorem could be an interesting extension and future work.\n\n> maybe more analysis can be provided\n\nWe would be happy to include additional discussions on the experimental results using the additional page in the camera-ready version. Here are some details we would like to add if space permits: We have observed that MWS has smaller performance loss compared to VSpS, making it highly practical. In fact, we strongly recommend using MWS in practice. We will also state the impact of different models on entropy and the influence of entropy on watermark strength.\n\nIf you have any further questions or concerns, please do not hesitate to ask. We are more than happy to address all your inquiries.\n\nConsidering our additional explanations for the experiments, we would be greatly appreciative if you could re-evaluate our work.\n\nThank you once again for your valuable feedback.\n\n[1] A watermark for large language models\n[2] Mark My Words: Analyzing and Evaluating Language Model Watermarks \n[3] Unbiased Watermark for Large Language Models", "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": "3zNhb7s6nv", "reviewer": "Reviewer_zG1K", "summary": "This paper explores the inherent trade-off between watermark strength and speculative sampling efficiency in large language models. A no-go theorem is presented, proving that it is impossible to maintain the highest watermark strength and sampling efficiency simultaneously. This paper also proposes a framework called the \"two reweight framework\" and develops two practical methods that focus on either maintaining watermark strength or sampling efficiency.", "questions": "1. **Impact on the quality of the text**. I am intrigued by the potential impact on the quality of generated text when adjusting the balance between watermark strength and sampling efficiency. Apart from LOGPPL, are there alternative evaluation metrics such as ROUGE or BLEU utilized for assessment?\n2. **Selection of target model and draft model**. The paper uses Llama-7b as the target model and the Llama-68m as the draft model. How are the target model and draft model selected for the article? Why did the paper choose the Llama series of models? Are there any specific requirements for their selection?\n3. **Choice of different draft sequence length K**. Regarding line 613, the choice of draft sequence length is critical in the deployment. Regarding Figure 2, when K is chosen from 1 to 4, a larger value of K (such as K = 4) generally demonstrates better performance in both reweighting methods. This implies that selecting a larger K value can enhance sampling efficiency while maintaining watermark strength. Consequently, if K were to be increased even further, how would the effects be?", "limitations": "The authors have discussed the limitations and potential negative societal impacts in Appendix F and G.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "+ **New framework**. The proposed framework allows for the integration of unbiased watermarking and speculative sampling techniques without altering the output distribution, thereby improving generation efficiency.\n+ **Theoretical proof**. This paper rigorously proves a no-go theorem that demonstrates when the vocabulary size exceeds two, it is impossible to maintain both watermark strength and sampling efficiency simultaneously.", "weaknesses": "- **Limited experimental dataset and models and experimental coverage**. The experiments are conducted only on specific datasets (e.g., CNN_DAILYMAIL) and models (e.g., Llama-7b and Llama-68m). Additional benchmarks on different datasets and models would strengthen the generalizability of the findings. The experiments only cover a few tasks (text summarization and open-ended text generation)\n- **Algorithm clarity**. The pseudo-code provided for the algorithms could be further detailed, with clearer explanations for each step to improve reproducibility.\n- **Lack of analysis on the robustness of watermarking**. \"On the Reliability of Watermarks for Large Language Models\" mentions paraphrasing attacks, and copy-paste attacks, etc. Could this article potentially evaluate the robustness of the watermark under the two reweight framework?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for spending time reviewing our work. However, I am afraid that your 4-point rating may be based on incorrect premise.\n\nWe would like to clarify a misunderstanding in your comment. You claimed that our paper only used Llama-7b and Llama-68m models. If you read lines 273-278, you will find that this is not the case. We have explained that we considered language models of different sizes, including Llama-7b and Llama-13b as the target models and Llama-68m as the draft model.\n\nWe understand that in your opinion, our contributions only reach the level of '2: fair.',  falling short of your expectations for a good contribution. However, our paper is the first study to investigate the inherent trade-off between watermark strength and speculative sampling. The new framework we propose lays a solid foundation, our no-go theorem provides valuable theoretical insights, and our two novel algorithms represent concrete advancements in techniques.\n\nRegarding the weaknesses you mentioned, we are willing to make improvements to meet your expectations. To do so, we kindly request more specific suggestions.\n\n1. **In your opinion, are the current experiments sufficient or insufficient to verify our findings? If insufficient, could you please let us know the scale of experiments you would consider adequate for verifying our findings?**\nAlthough our findings are already proven in Theorems 1, 5, and 6, and we have already invested 1200 A6000 GPU hours (~$1k) to verify them, we understand that the reviewer still considers the experiments limited. However, we are unclear about the specific reasons that lead the reviewer to expect a further increase in experimental scale (and cost), despite that our findings have been proven to hold.\nWe would be grateful if the reviewer could inform us, when listing experiments as a weakness, does the reviewer regard the current experiments as sufficient or insufficient to verify our findings, and if insufficient, what scale of experiments would the reviewer consider adequate to verify our mathematically-guaranteed findings.\n\n\n2. **Regarding your concern about \"Algorithm clarity,\" do you find any part of the algorithms difficult to understand, or do you simply anticipate that other readers might need clearer explanations?**\nWe are determined to help readers understand our algorithms and make the results reproducible. In Algorithms 1-4, we have provided all the algorithms used in the paper, including every step of the procedure and the specific calculation for each value. Regarding reproducibility, we have provided all the code in OpenReview.\nIf you find any part of the algorithms difficult to understand, we kindly request that you indicate which parts require further elaboration. We will strive to provide targeted explanations to help improve your understanding.\nIf you simply anticipate that other readers might need clearer explanations, we would also appreciate it if you could point out which specific parts of the presentation could be improved for clarity. We will strive to provide targeted explanations to enhance the presentation.\n\n3. **Regarding robustness, what specific research question do you expect us to investigate?**\nIn the rebuttal below, we will provide an analysis based on the close relationship between watermark strength and robustness. The excellent work \"On the Reliability of Watermarks for Large Language Models,\" you cited reveals the essence that \"Attacks dilute the watermark strength.\"\nTherefore, robustness and watermark strength are closely related. Robustness measures how much dilution the watermark strength can withstand while still maintaining detectable (e.g., a certain AUC). \n\"On the Reliability of Watermarks for Large Language Models\" addresses the research question \"Can diluted watermarks still be detected as long as they are sufficiently long?\" Our work primarily focuses on the research question of \"Is it possible to accelerate the generation of watermarked content?\". We understand that the reviewer expects us to investigate robustness-related research questions. However, we would appreciate it if you could clarify the specific research questions the reviewer expect us to address.\n\nWe seek the reviewer's understanding that we are asking for specific expectations rather than directly supplementing experiments. This is because without clear experimental suggestions as guidance, we may conduct experiments that the reviewer considers irrelevant or repetitive, wasting valuable computational resources and funding(, considering that the experiment cost of this paper is already 1200 A6000 GPU hours, ~$1k). Only by clarifying the reviewer's expectations can we design and conduct targeted experiments.\n\nNext, we will address the reviewer's questions.", "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": "grb42o6pPm", "reviewer": "Reviewer_5eD7", "summary": "The paper investigates whether speculative sampling is compatible with watermarking for LLMs.", "questions": "Q1. I understood that ANLPPT equals $-\\log(P_n) / n$ where $P_n$ is the measured P-value over $n$ tokens. Which logarithm? What is the typical value of $n$? My experience with the Aaronson scheme is that the score fluctuates a lot. A median might be a more reliable statistic than a mean over token.\n\nQ2. I am very surprised that DeltaGumbel is way better than Gamma. Is this due to \n\nQ3. Line 33: \"Unbiased watermarking schemes [12] have been developed.\" Well, Aaronson [1] was the first person to introduce this concept, isn't it?\n\nQ4. It is quite curious that no citation or reference is given for \"DeltaGumbel\" and \"Gamma\" schemes. DeltaGumbel is known as Aaronson [1] (everywhere in the literature), and Gamma looks like ITS from Kuditipudi [15]. Isn't it?\n\nQ5. Some details of the experimental protocol are missing. I suspect the measurements are done on an \"idealized\" setup where the secret key changes at random from one token to another, and the detector knows this. This is not realistic as it is absolutely not robust. To be practical, one has to make the secret key dependent on the previous tokens (see Kirchenbauer [13, 14]). This might hurt speculative sampling since a rejection implies a recomputation of the hash.\nMoreover, repeated token blocks need to be skipped at the detection side (see Fernandez [8]); otherwise the p-value is incorrect. This hurts the ANLPPT. \nI don't believe these tweaks modify the general conclusions of this work, but this \"idealized\" setup should be clearly stated, with the implications (ANLPPT and AATPS are lower in practice).", "limitations": "No limitation is given.\nA limitation about the lack of practicality of the experimental protocol would be welcome.", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "S1. This paper is original in the landscape of LLM watermarking.\n\nS2. This paper shows an interesting \"no-go\" theoretical result (Th. 1).\n\nS3. This paper proposes  2 designs sustaining either the sampling efficacy or the watermark strength.\n\nS4. I like very much the proposed measurement of the watermark strength: the average exponent of the p-value.\n\nS5. The presentation is crystal clear.", "weaknesses": "W1. Speculative sampling.\nI am not an expert in sampling for LLM. I do not know how \"speculative sampling\" is key compared to more common methods like nucleus or top-k sampling, which prevents me from judging this paper's impact.\n\nW2. More comments on the experimental results\nSay at least that MWS is much better than MSE in the sense that the MWS loss of sampling efficiency is barely visible, whereas the MSE loss of watermarking strength is significant. The LLMs used in the experimental protocols are old and their entropy is bigger than more recent ones. It might be worth stating that this choice gives high ANLPPT.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are thrilled to receive such a meticulous and knowledgeable review of our research. It is a privilege to have our paper assessed by a reviewer with such extensive knowledge in the landscape of LLM watermarking. Your acknowledgment of the originality of our work is truly rewarding. In the following sections, we will respond to your inquiries and feedback.\n\n> how \"speculative sampling\" is key compared to more common methods like nucleus or top-k sampling\n\nSpeculative sampling and nucleus or top-k sampling operate at different design levels and are not inherently conflicting. They can be used simultaneously. For instance, the seminal paper on speculative sampling, \"Accelerating Large Language Model Decoding with Speculative Sampling\" [5], mentions that \"With standard sampling methods such as nucleus, top-k sampling and adjusting temperature, we can modify the probabilities accordingly before applying this rejection sampling scheme.\"\n\n> More comments on the experimental results Say at least that MWS is much better than MSE in the sense that the MWS loss of sampling efficiency is barely visible, whereas the MSE loss of watermarking strength is significant. The LLMs used in the experimental protocols are old and their entropy is bigger than more recent ones. It might be worth stating that this choice gives high ANLPPT.\n\nWe greatly appreciate your suggestion and are eager to include more discussion of the experimental results using the additional page in the camera ready version. We concur that MWS exhibits a smaller performance loss compared to VSpS and is highly practical. In fact, we strongly recommend using MWS in practice. We will elaborate on the impact of different models on entropy, and how entropy influences watermark strength using the additional page.\n\n> Q1. I understood that ANLPPT equals $-\\log(P_n) / n$ where $P_n$ is the measured P-value over $n$ tokens. Which logarithm? What is the typical value of $n$? My experience with the Aaronson scheme is that the score fluctuates a lot. A median might be a more reliable statistic than a mean over token.\n\nThe logarithm used here is the natural logarithm. $n$ is the number of tokens in the generated sentences. We generate many sentences with a max_length of 128, but they may be shorter due to early stopping. We can calculate the median, introducing the Median Negative Log P-value Per Token (MNLPPT). \n\nText summarization task with LLaMa-7b model as target model and LLaMa-68m model as reference model:\n\n| K | method | reweight | n | ANLPPT(U Score) | MNLPPT(U Score) | ANLPPT(maximin-LLR) | MNLPPT(maximin-LLR) |\n|---|--------|----------|---|-----------------|-----------------|---------------------|---------------------|\n| 1 | Basic | No Reweight | 122.0±0.7 | 0.0±0.0 | 0 | 0.0±0.0 | 0 |\n| 1 | VUW | DeltaGumbel | 121.0±0.8 | **0.376±0.009** | **0.385** | **1.71±0.03** | **1.933** |\n| 1 | VUW | Gamma | 121.9±0.7 | **0.097±0.002** | **0.098** | **0.272±0.005** | **0.333** |\n| 1 | VSpS | No Reweight | 122.6±0.7 | 0.0±0.0 | 0 | 0.0±0.0 | 0 |\n| 1 | MSE | DeltaGumbel | 121.5±0.8 | 0.153±0.004 | 0.141 | 0.640±0.014 | 0.660 |\n| 1 | MSE | Gamma | 121.9±0.7 | 0.0433±0.0012 | 0.036 | 0.0605±0.0019 | 0.054 |\n| 1 | MWS | DeltaGumbel | 121.3±0.8 | **0.374±0.009** | **0.380** | **1.71±0.03** | **1.921** |\n| 1 | MWS | Gamma | 121.9±0.7 | **0.098±0.002** | **0.100** | **0.275±0.005** | **0.335** |\n| 2 | VSpS | No Reweight | 122.7±0.7 | 0.0±0.0 | 0 | 0.0±0.0 | 0 |\n| 2 | MSE | DeltaGumbel | 122.5±0.7 | 0.111±0.003 | 0.095 | 0.419±0.010 | 0.403 |\n| 2 | MSE | Gamma | 122.4±0.7 | 0.0322±0.0010 | 0.024 | 0.0310±0.0014 | 0.021 |\n| 2 | MWS | DeltaGumbel | 121.4±0.8 | **0.374±0.009** | **0.379** | **1.71±0.03** | **1.913** |\n| 2 | MWS | Gamma | 122.8±0.7 | **0.096±0.002** | **0.097** | **0.272±0.005** | **0.332** |\n| 3 | VSpS | No Reweight | 121.4±0.8 | 0.0±0.0 | 0 | 0.0±0.0 | 0 |\n| 3 | MSE | DeltaGumbel | 121.4±0.8 | 0.094±0.003 | 0.079 | 0.331±0.009 | 0.306 |\n| 3 | MSE | Gamma | 121.8±0.7 | 0.0281±0.0009 | 0.020 | 0.0214±0.0012 | 0.011 |\n| 3 | MWS | DeltaGumbel | 121.2±0.8 | **0.374±0.009** | **0.380** | **1.70±0.03** | **1.919** |\n| 3 | MWS | Gamma | 122.3±0.7 | **0.097±0.002** | **0.098** | **0.274±0.005** | **0.335** |\n| 4 | VSpS | No Reweight | 122.5±0.7 | 0.0±0.0 | 0 | 0.0±0.0 | 0 |\n| 4 | MSE | DeltaGumbel | 122.2±0.7 | 0.083±0.002 | 0.067 | 0.280±0.008 | 0.249 |\n| 4 | MSE | Gamma | 122.6±0.7 | 0.0258±0.0008 | 0.018 | 0.0167±0.0011 | 0.007 |\n| 4 | MWS | DeltaGumbel | 121.1±0.8 | **0.375±0.009** | **0.380** | **1.71±0.03** | **1.923** |\n| 4 | MWS | Gamma | 122.2±0.7 | **0.096±0.002** | **0.097** | **0.271±0.005** | **0.331** |", "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:

Meta-review: 1x SA, 1x A, 1x WA, and 1x BA. This paper studies the trade-offs between sampling efficiency and watermark strength via a no-go theorem. The reviewers agree on the (1) interesting topic, (2) novel study, and (3) rigorous theoretical proof. Most of the concerns, such as the insufficient comparisons and evaluation metrics, have been addressed by the rebuttal. Therefore, the AC leans to accept this submission.
Decision: Accept (poster)