Theoretically Grounded Framework for LLM Watermarking: A Distribution-Adaptive Approach
Authors: Haiyun He
Yepeng Liu
Ziqiao Wang
Yongyi Mao
Yuheng Bu
Venue: NeurIPS 2025 poster ()
Keywords: Watermarking
Large Language Models
Hypothesis Testing
Information Theory
Primary area: theory
TL;DR: We provide a theory for jointly optimal, distribution-adaptive LLM watermarking, yielding DAWA, a highly effective, distortion-free algorithm.

Abstract: Watermarking has emerged as a crucial method to distinguish AI-generated text from human-created text. Current watermarking approaches often lack formal optimality guarantees or address the scheme and detector design separately. In this paper, we introduce a novel, unified theoretical framework for watermarking Large Language Models (LLMs) that jointly optimizes both the watermarking scheme and detector. Our approach aims to maximize detection performance while maintaining control over the worst-case false positive rate (FPR) and distortion on text quality. We derive closed-form optimal solutions for this joint design and characterize the fundamental trade-off between watermark detectability and distortion. Notably, we reveal that the optimal watermarking schemes should be adaptive to the LLM’s generative distribution. Building on our theoretical insights, we propose a distortion-free, distribution-adaptive watermarking algorithm (DAWA) that leverages a surrogate model for model-agnosticism and efficiency. Experiments on Llama2-13B and Mistral-8$\times$7B models confirm the effectiveness of our approach, particularly at ultra-low FPRs. Our code is available at \url{https://github.com/yepengliu/DAWA}.

Theoretically Grounded Framework for LLM
Watermarking: A Distribution-Adaptiv Approach
Haiyun He*
Yepeng Liu" UC Santa Barbara Santa Barbara, CA, USA
HKUST (GZ)
Guangzhou, China
haiyunhe wew.eechhuuutttg.e...c... ed
yepengliuducab.edt
Ziqiao Wang
Yongyi Mao University of Ottawa Ottawa, ON, Canada
Yuheng Bu UC Santa Barbara Santa Barbara, CA, USA buyuheng@ucsb. edu
Tongji University Shanghai, China
ziqiaovang@tongji. edu. en
ymaoQuottawa. wawobuuottww..c..m
Abstract
Watermarking has emerged as a crucial method to distinguish Al-generated text from human-created text. Current watermarking approaches often lack formal optimality guarantees or address the scheme and detector design separately. In this paper, we introduce novel, unified theoretical framework for watermarking Large Language Models (LLMs) that jointly optimizes both the watermarking scheme and detector. Our approach aims maximize detection performance while maintaining control over the worst-case false positive rate (FPR) and distortion on text quality. We derive closed-form optimal solutions for this joint design and characterize the fundamental trade-off between watermark detectability and distortion. Notably, we reveal that the optimal watermarking schemes should theoretical
be adaptive to the LLM's generative distribution. Building insights, we propose a distortion ffeee distributioo-adaative watermarking algorithm (DAWA) that leverages surrogate model for model-agnosticism and efficiency. Experiments on Llama2- 13B and Mistral-8 7B models confirm the effectiveness of our approach, particularly at ultra-low FPRs. Our code is available https //gi com/ www.://pppggg///AA..
Introduction
Arising with Large Language Models (LLMs) 1 is a double-edged sword: while they boost productivity, they also introduce risks, including plagiarism, challenges content accountability, and other forms of misuse. Watermarking, a hidden and machine-verifiable tag inserted into LLMs' outputs, has therefore become critical line of defense for publishers, educators, and regulators.
Existing watermarking techniques for Al-generated text are commonly grouped into two main categories: post-process and in-process 2 23. Post-process watermarking is applied after the text
generated [6), while in-process watermarking embeds watermarks during generation [T7 36). There is growing interest in in-process methods due to their invisibility, flexibility, and seamless integration with negligible latency. For additional related works, please refer to Appendix A
However, realizing the full potential of in in-process watermarking requires careful design. A key challenge is controlling the false positive rate (FPR), as even single error can lead serious
'These authors contributed equally to this work.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

consequences. such as wrongly accusing a human author. Maintaining a high true positive rate (TPR) while keeping an ultra-low FPR, e.g., 1e-05, is therefore essential. In addition, effective in-process watermarking should be both detectable and distortion-free: the watermark must be reliably identified under strict false positive rate (FPR) constraints, while preserving the quality and distribution of the original output 35| 371. Moreover, a practical detector should be model- agnostic, operable without access to the original LLM or its prompt [25]. Balancing all these goals is challenging, and existing methods often fall short in one or more dimensions.
Many heuristic designs typically embed watermarks into generated tokens by perturbing the token logits (e.g., the green-red list (251) or modifying the sampling process (e.g., Gumbel- sampling (38). Detection is usually performed using handcrafted score statisties. However, these "trial-and- eπror" approaches rely heavily on empirical tuning. with no formal optimality guarantees.
constrained optimization problem: maximizing the detection probability TPR with the FPR and text distortion under control. Recent theoretical efforts have taken steps towards this goal. For instance, Takezawa et al. [39] Wouters [40), and Cai et al. [41] focus on optimizing the logit perturbation strategy for the green-red statistical independence test between text and watermark and derive the optimal scheme for a fixed detector, but stop short of a practical, agnostic algorithm. On the other hand, Li et al. optimizes the detector for a fixe watermarking scheme using i.i.d pivotal statistics. Consequently, these approaches do not guarantee overall system optimality. A significant gap in these theoretical explorations that none of them consider the joint optimization of both the watermarking scheme and the detector.
In principle, designing watermarking system can be formulated
list watermarking scheme. Huang al. 42 frame watermarking
Specifically, both the way the watermark is embedded and the type of signal used can be optimized. However, existing approaches often on fixed, simplistic designs, such as using randomly generated bits samples from uniform distributions, leaving much of the design space unexplored. These restrictive choices may prevent existing schemes from achieving optimal performance.
This paper aims to fill the gap. We develop a novel, unified theoreti- cal framework that subsumes most existing in-process schemes, aiming to jointly optimize the watermarking- detector pair for any token-sequence length T that achieves the best trade- off between watermark detectability and text distortion. Unlike the clas- sical watermarking paradigm, which employs fixed watermark distribu- tions, our framework generalizes wa- termarking to an adaptive setting where the watermark signal exploits the LLM's generative distribution. This opens up one more degree of free- dom to optimize the sampling distributions of watermark signals, thereby enhancing detection reliability at ultra-low FPRs, as shown in Figure [
1.0
0.8
True Positive Rate
0.4
#lc-4FFua
551,
ele 3FPu
9le-299-6.99
0.2
K0H-23
216-4
538.
236-319-2 942.
216-299-0.31
2ic-4th-
564.
630 3Ph- 055.
0ic-259-e.254
EXP-esit
0te-5
63e-1
867.
17P-1
082.
0te-279-0.941
1O6-23
ote
41e-0 500.
Ste-
653.
0te-219-0.010
0.0
10.1
10
10-3
18:2
10-2
10a
False Positive Rate
Figure 1: Comparison of TPR at ultra-low FPR among dif- ferent watermarking methods.
Our contributions can be summarized as follows:
In Section 2
we propose a unified theoretical framework for LLM watermarking and detection that encompasses most existing watermarking methods. This framework features common randomness shared between watermark generation and detection to perform an independence test.
In Section 3 we characterize the universally minimum Type-II error (i.e., 1-TPR) as a function of FPR and text distortion level, revealing a fundamental trade-off between dctectability and distortion. More importantly, we identify the closed-form jointly optimal solutions for watermark- ing schemes and detectors, providing a guideline for practical design, i.c., watermarking schemes should adapt to the generative distribution of LLMs.
Section 4 we translate the sequence-level optimum to a practical token-level watermarking design. We prove that it retains reliable detection performance and is inherently robust against token replacement attacks. In Section [ we introduce DAWA (Distribution-Adaptee Algorithm), distortion-fres implementation of the token-level design, which leverages a sur-
Watermarking

---

rogate language model and the Gumbel-Mar sampling trick to achieve model-aggnosiicism and computational efficiency.
we conduct extensive experiments on Llama2- 13B [ and Mistral-8x x 7B 44 across multiple datasets. DAWA consistently outperforms the compared methods, even under token replacement attacks, and maintains high text quality. As shown in Figure I DAWA achieves superior detection capabilities at ultra-low FPRs.
In Section 6
Lastly, we sketch in Appendix how to extend our theoretical framework to semantic-invariant watermarking removal attacks and derive the associated defeettaiitt--iistottoo--ooooooi trade- off, guiding future semantic- baase watermark designs.
2 Preliminaries and Problem Formulation
Notations, For a sequence of random variables ; and any i.j E [n]] with S j. we denote X = (X....., X2). We may use distortion function, namely, a function D P(X) x P(X) + [0, +o0) measure the dissimilarity between two distributions in P(2'). For example, the total variation distance, as distortion, between Js, V E P((x) is DTv(U, v) = de
1 dv. For any set A C X, we use 5 to denote its indicator function, namely, (x == 1 (xr E A}. Additionally, we denote (z)+ == max(z: z, 0} and x' A y == min (z; y).
Tokenization and NTP. LLMs process text through "tokenization," namely, breaking it down into words word fragments called "tokens." " An LLM generates text token by token. Let V denote the token vocabulary, typically of size [V = O11*)) 45 I. An unwatermarked LLM generates the next token X, based on prompt and the previous tokens 2 by sampling the Next-Token Prediction (NTP) distribution Qx, .pe For simplicity, the prompt dependency is suppressed in notation throughout the paper. The joint distribution of length-T generated token sequence X then given by QxT := IT= Qx,xxt 1, which we assume to be identical to one that governs the -emanngeeerraed text.
A Framework for Watermarking Scheme. Traditional post-hoe detec- tors identify A Al-generated text by di- viding the entire text space into rejec- tion and acceptance regions, which relies on the assumption that certain sentences are unlikely to be written by humans. contrast, modern LLM wa- termarking schemes achieve the same goal by analyzing the dependence structure between text XT" and an aux- iliary random sequence GT. thereby avoiding this restriction.
QXI
QxF
Pxtrer
Sampler
LLM
Watermarking Scheme
Watermark Generation Watermark Detection
Common Randomnesss Gf
Watermarked
Wa watermarked text
Detector
Unwatermarked
unwatermarked text
Figure 2: Overview of LLM watermarking and detection.
In this paper, we propose general framework for LLM watermarking and detection, as shown in Figure 2 which encompasses most of the existing watermarking schemes. The watermarking scheme and detector share a common randomness represented by an auxiliary random sequence of drawn from a space z (either discrete or continuous). After passing through watermarking scheme, the watermarked LLM samples token sequence according to the modified NTP distribution
Px ".]"--'.c7- where Px7 KTT = II Px,xx(-'<<? This process associates the generated text x7 with an auxiliary sequence <T- Thus, the joint distribution of the watermarked token sequence X7" is Px7, which might be different from the original Qx7. The detector can then distinguish whether the received sequence X watermarked or not based on the common randomness.
To evaluate the distortion level of a watermarking scheme, we measure the statistical divergence between the watermarked text distribution pxx and the original one QxT-
Definition (e-distorted watermarking scheme). A watermarking scheme is e-distorted with respect to distortion D, D(Px7 ,xF)) I e. Here, D can be any distortion metric.
3

---

Common examples of such divergences include squared distance, total variation, KL divergence, and Wasserstein distance. For 0, the watermarking scheme distortion-free.
Specifically, our formulation allows the auxiliary random sequence Çf to take an arbitrary structure, which contrasts the rather restricted i.i.d. assumption considered in Li et al. [43] Working Hypothesis 2.1]. In practice, Cf is usually randomly generated using shared key accessible during both watermark generation and detection. first glance, our formulation may appear abstract, but its flexibility enables existing watermarking schemes to be interpreted as special cases within this framework.
Example 1 (Existing watermarking schemes as special cases), In the Green-Red List watermarking scheme (25), at each position the vocabulary V is randomly split into green list and red list R. with [g] = for some E (0, 1). This split is represented by a [V] [-ddimensional binary auxiliary variable (t. indexed by V, where Ce(x)) means 9; otherwise, watermarking scheme is as follows:
R. The
Compute a hash of the previous token X,-1 using hash function ::Vx V R + IR and a shared secret key, i.e., 1,, key).
-se h(X,-1, key)
seed to uniformly sample the auxiliary variable Ça from the set {f {00. 10.1) ||Slla p|V|} construct the green list G.
-Sample X, from the adjusted NTP distribution which increases the logit tokens in by 6 > 0:
Px.la-- (x)x) Exev 1aup
How our formulation encompasses several other watermarking schemes is provided in Appendix B
Hypothesis Testing for Watermark Detection. Note that a sequence X generated by a water- marked LLM depends on Cf while X and {f are independent if written by humans. Therefore, detection involves distinguishing the following two hypotheses based on the pair (XT.7))
HHg xf is generated by a human, i.e., (xT ~ Qx. @ Per:
:H: xT is generated by a watermarked LLM, i.e., (XT, (T) PXP.T.
We consider model-agnostic detector 7 DT 2 (0, which maps (X. .F) to the hypothesis index (see Figure(2). In theory, we assume that the auxiliary sequence & can be fully recovered from Xf and the common randomness, while this assumption is dropped in practice.
Detection performance is measured by the Type-I (false positive) and Type-II (false negative) emoos:
Type-I (i.e., FPR):
8o(7, Qx7 p3)== Pr(7(xT, P o 0| Ho).
Type-Il (i.e., 1-TPR):
31(%, PxT Pr(7(xpffPf/ ( HH))
(1)
Optimization Problem. Given that human-generated texts can vary widely, within our proposed framework, we aim to control the worst-case Type-I error supexp Bo(7, QxT. P&F) at given
(0, 1) while minimizing Type-ll error. Our objective is to design an e-distorted watermarking scheme and a model-agnostic detector by solving the following optimization:
inf B1 PxT.F)
sup Boly, Qx7, QxT
a,
(Opt-O)
>xPxT <F The optimal objective value, denoted as 37 (Qx Exrrec a, c), is termed as universally minimum Type-1l error. This universality due to its applicability across all potential detectors and watermarking schemes, well as its validity under the worst-case Type-I error scenario.
3 Jointly Optimal Watermarking Scheme and Detector
In this section, we aim to solve the optimization in OOpt-O) and identify the jointly optimal water- marking scheme and detector. However, solving (Opt-O) is challenging due the binary nature of 7 and the vast set of possible 7, sized 2 To address this, we begin with specific (Xf. 1((xF.c e Ar). where A defines the acceptance region for H1, aiming to

---

uncover potential structure for the optimal detector. To this end, we simplify O as Bo(n: extxxxxPee S a, D(PxT, QxT) se. (Opt-I)
inf Bi PXT.sT) s.t. sup
2xT
Error-Distortion Tradeoff. We first derive lower bound for the minimum Type-Il error in Opt--I. which surprisingly does not depend on the selected detector y and therefore also applies to Opt--O). We then pinpoint type of detector and watermarking scheme that attains this lower bound, indicating that represents the universally minimum Type-II error. Thus, the proposed detector and The theorem below establishes this universal minimum Type-ll error for all feasible watermarking schemes and detectors.
watermarking scheme jointly optimal, detailed in Theorem 2
Theorem (Universally minimum Type-Il error). The universally minimum Type-ll II ervor attained from Opt-O is
37 (Qx (.,c)
min Pxp:D( xx
Ex(PPx -a)+:
(2)
which is achieved by the watermarked distribution
PxT
arg min
E (Px7 (x)) a)+.
(3)
Pxp DD
& Axpls
By setting D total variation distance DTV. can be simplified as follows:
x(Qxp,
(E (2xT (1)) a)+ .. if E E. (
(xp(x))) 2
The proof of Theorem iis deferred to Appendix C Theorem
distortion-fre
e-dittortdd
Pr
Qxr
I shows that, for any watermarking scheme, the fundamental limits of detection performance depend on the original NTP dis- tribution of the LLM. When the original Qx is more concen- trated (low entropy), the minimum achievable detection error increases. This hints that it is inherently difficult watermark low-entropy text. However, increasing the allowable distortion 6 can enhance the capacity for reducing detection errors, as illustrated in Figure 3 Moreover, we find that (Q x7 a,
universally minimum Type-ll error
universally minium Type-ll error
Illustration of error- distortion trade-off.
Figure
matches the minimum Type-Il error from Huang et al. [42 The-
orem 3.2], which notably optimal for their specific detector.
Our results, however, establish that
this is the universally minimum Type-Il error across all possible detectors and watermarking schemes, indicating that their detector belongs to the set of optimal detectors described below.
Jointly Optimal Design. We now present the jointly optimal watermarking schemes and detectors that achieve the universally minimum Type-II error in Theorem T i.e., the solution to (Opt-O.. The key takeaway in the optimal design is: (i) for any given LLM @ @x7, we can find a valid bijective function y (not unique) to construct jointly optimal pair of watermarking scheme and detector; (ii) as a result of maximizing the detection performance of dependency against independence between XT and GF the optimal watermarking scheme Pt iX? turns out to be nearly deterministic.
Theorem (Informal Statement) Jointly optimal watermarking schemes and detectors). The class of optimal detectors is given by 7" E I = {> 7XX T (f) = 1 = =((f)), for some bijective g 2T + + V*},
(4) where Z "y-" U (CF) and दT is redundant auxiliary sequence that is not preimuge of any loken sequence for g. Given any (QxT, c), the corresponding optimal watermarking scheme takes the form P* xF = Px P where P (c.f. (3) depends on (Qx;, ,), and the mapping P XT depends the chosen detector r"" Full details are provided in Appendix D
In Appendix [ formal and general statement Theorem shows that the optimal class of detectors extends to any valid surjective function g with different input space. To illustrate this with simple example, suppose yT {a, b, c). We can define an extended set = (a, b, c, # and construct bijective mapping y from an auxiliary set 2 {1, 2, 3, 4) to S. Such class I is then universally optimal, meaning that to guarantee the construction of watermarking scheme that maximizes the detection performance, the detector must be chosen from 1*
5

---

Discussions on Theoretically Optimal Watermarking Scheme. A detailed illustration of the optimal watermarking scheme is provided in Appendix with several important remarks follows.
First, we observe that the derived optimal watermarking scheme P xT' for any 7" E T is adaptive to the original LLM output distribution Qx7- This observation suggests that, to maximize watermark detection performance, watermarking schemes should fully leverage generative modeling and make the sampling of auxiliary sequence adaptive to Qx?- This approach contrasts with existing watermarking schemes, which typically sample the auxiliary sequence according to a given uniform distribution, without adapting it to the LLM NTP distribution. This insight serves as foundation for the design of our practical watermarking scheme, which will be introduced in Section 4
Second, in order to control the worst-case FPR, the construction of P xy relies on the redundant
auxiliary sequence č included in the auxiliary alphabet 2 which satisfies 7 "" (7) 0 for all
of. This sequence &f plays a critical role in our proposed algorithm. Specifically, if x7 (xf) > a
(indicating a low-entropy text, e.g., a celebrity's 's name). it may be mapped to the redundant Gf' making it harder to detect watermarked. Thus, the optimal watermarking scheme PxF_cP is particularly effective in reducing the FPR for low-entropy texts.
Practical Challenges. Given the theoretically optimal structure, there are still a few practical challenges in its direct implementation. 1 Designing a proper function g, an alphabet 2d and the corresponding Px .e" is challenging, as |V|T grows exponentially with T, making it hard to identify
all pairs (af (t) such that uf g(Si") 2 The optimality is derived for static scenarios with fixed token length T, making it unsuitable for dynamic scenarios where the tokens are generated incrementally with varying T. 3 In the theoretical analysis, we assume full recovery of the auxiliary sequence ST during detection. However, in practice, the detector only receives the token sequence Xf. and reconstructing the auxiliary sequence 5P from X"" poses a challenge.
These practical constraints motivate the development of a more feasible version of the theoretically optimal scheme. In Section we adapt it to a practical token-level optimal scheme address 1 and 2; in Section 5 we implement the token-level design with a novel algorithm utilizing a surrogate language model and the Gumbel-Max trick 48 to overcome 3
4 Practical Token-level Optimal Watermarking Design
In this section, present a practical approach that approximates the theoretical framework while ensuring its applicability to real-world scenarios. Building on the fixed-length optimal scheme, we nat- urally extend it to accommodate varying-length scenarios by constructing the optimal watermarking scheme incrementally for each token, i.e., P X, -c-- for all = 1,2,....
To lay the groundwork, we first revisit heuristic detectors for some existing watermarking schemes.
Example 2 (Examples of heuristic detectors). Two example detectors from existing works:
Green-Red Red List watermark detector [25]: >XT, <T) 1{ 1 E (G,(X,) = 1) 133-pP1 pT) 2 A} =1}-
where X >>0 O, p E (0. 1), and S. = (G((z)) uniformly sampled from {C (0, MI:1|
pIVI} with the seed (osh(X._1,key)
Gumbel-Max watermark detector (38): (Xf 1(-Et log(1 (((1))(X)))) 2 {}} where
À > O, and C. (G(()))EEV is uniformly sampled from [0, Il with the seed (ash(X("r' key) for some
Practical Detector Design. We observe that the commonly used heuristic detectors take the non-optimal form by averaging the test statisties over each token: >(X7 <P)
1 E Test Statisties of (X,, (r) 2 }}. This token-level design provides several advantages: (1) incremental computation of detectors for any T and 2) token-level watermarking with the alphabet depending only on the fixed size | Inspired by these detectors, we propose the following detector to address the issues 1 and 2 mentioned carlier:

---

T
mxx ( =
T
Σ
1(x - grx (Gi)
2 1
(5)
Token-level adaptation of {
for some bijective function 9tk
S V, where Z = 9 (V)
{2} for some redundant
V for g. This detector combines the advantages of existing token-level detectors with the optimal design from Theorem[] The test statistic for each token (Xx, (t) is optimal at position I, enabling token-level optimal watermarking scheme that improves the detection performance for each token.
auxiliary value ( not being the preimage of any token
Token-Level Optimal Watermarking Scheme. Following the same rule in Theorem and Appendix D the token-level optimal watermarking scheme is sequentially constructed based on [(X;; = (tt():)) in (5) and the NTP distribution at each position t, acting only on the token vocabulary V. This approach addresses the challenges 1 and ② as well. Notably, the resulting distribution of the token-level optimal scheme for the auxiliary variable Çe is adaptive to the original NTP distribution Q (, Moreover, the resulting distribution on X, is given by (comparable to PxT in Theorem 2
and
P Xel=i 1-
arg min
n)+ -))
(6)
DI saas 19
PEV
where E (0, 1) is the token-level FPR constraint, which is typically much greater than the sequence- level FPR constraint a. With a proper choice of 17, we can effectively control a. Under this scheme, we add watermarks to the generated tokens incrementally, with maximum detection performance at each token. The details are deferred Appendix F and the algorithm is provided in Section S
Performance Analysis.
We evaluate the Type-I (FPR) and Type-II (1-TPR) errors of this scheme over the entire sequence (cf. (I).
Lemma (Anformal Statement) Token-level optimal watermarking detection errors). Under the detector "Yuk in (5) and its corresponding token-level optimal watermarking scheme with TE
n E (0, min(1, (a/ (a/((T)))) () H. for length-T sequence: (i) the worst-case Type-I error supaa 30 S o; (üi) if token positions more than apart are assumed to be independent, with suitable detector threshold, the Type-Il error decays exponentially in T T/n.
Although the token-level optimal watermarking scheme may not be optimal at the sequence level, show that it maintains good performance with proper choice of token-level FPR 17. The formal statement is provided in Appendix G
Furthermore, we observe that even without explicitly introducing robustness to the token-level optimal watermarking scheme, it inherently leads to some robustness against token replacement. The following result shows that if the auxiliary sequence Çf is shared between the LLM and the detector Yek (cf. (5)), the token at position can be replaced with probability Pr(Ge is redundant) without affecting detector output.
Proposition& 4 (Robustness against token replacement). Under the detector "iuk in ( and its corresponding loken-level optimal watermarking scheme, the expected number of to- kens thut can be randomly replaced in Xf without compromising detection performance is 1 [Ezev (=lxxx--<= - with P x,|xx-= given in 6
Et xx
5 DAWA: DnstrbbttionAAaptine Watermarking Agorithm
In this section, we implement the token-level design presented in Section by introducing a novel, distortion-free watermarking algorithm, DAWA (Distribution-Adaptie Watermarking Algorithm). To address the challenge 3 of recovering the auxiliary sequence at the detector without knowledge of the original LLM and prompt, we utilize some novel tricks, including surrogate model and Gumbel- sampling, which also ensures mones--gnos and computational efffciincy.
Novel Trick for Auxiliary Sequence Transmission. Since the resulting optimal distribution of the auxiliary variable Ç. from Section 4 is adaptive to the original NTP distribution of LLM, it is not likely to completely reconstruct the detection phase without access to the L.LM or prompt. One possible workaround is enforcing Ps. Unif(Z) for both watermark generation and detection.
7

---

(A3)
Singl
"rusicim"
Wolfoang infbettial
Large langunge
Sanole
Hd, E.urguuty map
"cosposer"
Matemark Generation
Natemark Detection
Stared Key
Milfgann feaddous Mozart
3n influential composer the Classscali geribd.
Surregate Language Model
IAD
Bunkiea G
Meterarkee
Un-oatermarked
the Classtcal pertont
the e1o553cal porizd.
Figure 4: Workflow of our practical algorithm (DAWA) for watermark generation and detection. (l]]: construct the sampling distribution of auxiliary variable Çr based on Q211= 'pt'* (A2): sample Ge using the Gumbel-Mer trick and a shared key; A3 adjust the NTP distribution of I with 17.
While this method simplifies the transmission, it leads to a much higher minimum Type-II error compared to $1 (1(Q7] a, e) (cf. ( indicating a trade-off between detection performance and non-distribution-adan adaptive design.
We thus introduce novel trick transmit the auxiliary sequence by integrating surrogate language model (SLM) during the detection phase and the Gumbel-Max trick [48] for sampling Čt. This SLM, much smaller than the watermarked L.M and possibly from different family (as long it shares the same tokenizer) approximates the watermarked distributions {Px x Jt=,,,,.. using only the text
XT. without the prompt. With the approximated P - we reconstruct the sampling distribution of & and sample using the Gumbel-Max trick with the key shared from watermark generation.
Theoretically, the SLM's approximation error has limited impact on detection performance, since the watermarking algorithm is provably resilient token replacement attacks (cf. Proposition { In Section 6 our experiments highlight that, even with incomplete recovery of C? during detection, the DAWA algorithm with this novel trick exhibits superior detection performance and greater resilience against token replacement attack, surpassing baseline watermarking schemes.
DAWA Details.
From the detector in we first choose Itk that depends on hash function hzay:
Jdwaa (XF (T = Σ (lina (X₂) G
xE[T]
DAWA an implementation of the distortion-free (c 0) token-level optimal watermarking scheme (cf. Section 4h, in which the auxiliary variable is sampled adaptively based on the original NTP distribution Q 2x,x=1-1.m .pe- as illustrated in Figure and detailed in Appendix Below, we elaborate on the key steps.
Watermark Generation, Using the detector "dawaa from we define the auxiliary alphabet Z from unique mappings (lizay (x)e(()))ee and add redundant Ç. At each t, P cojat=' .pt is adaptive to Q xx ip
P P <- (Q (Qx ((x))())...1 An), E 2((2).
(A1)
P "a ( (x() 7)+-
The Gumbel-Max trick is then used sample G::
Çe <- arg max log ((lPp (4)) + Gt.c.
(A2)
ÇE2
where Gt is sampled from the Gumbel distribution using shared key and the previous tokens. If is non-redundant, let N (Gt); otherwise, is sampled via multinomial distribution:
(Q (0x,1e) pm 1)+
Erev (Q (Qx.1ag-' .pa (x) 1)) DEV
(A3)
8

---

Table 1: Detection performance clean and edited different LLMs and datasets.
Clean Text
Token Replacement Altack
LLM
Method
ROC-AUC TP
TPO 109)
ROC-AEC TPN:15 150
TPS:000
TPQ TPG ROC-AUC TP8:1 TPO
KCPW433
0.995
0.991
1,000
0.989
0.914
0.965
0.965
0.533
0.952
0.913
0.892
0.973
Ubme2-138 38
Guzabel Max
EXP-efii
0.996
0.96
0.993
0.958
0.994
0.996
0.99
0.983
0.960
0.99]
0.995
0.994
0.963
0.973
0.558
0.557
0.970
0.973
0.967
0.955
0.857
0.850
0.975
0.975
HCW-21
0.994
0.228
01966
(1911
0.835
0.97
0.890
0.768
0.714
08891
0.278
0.692
Our
0.999
0.988
1000
0.908
0.977
1,000
0.989
0.380
0.076
0.955
0199)
0.904
KGWWe1
0.997
0.935
1000
0.903
0.983
0.994
0.977
0.360
0.962
0.950
0.800
0.930
Mistul 4x
Gumbel-Max
EXP=afii
0.993
0.994
0.959
0.971
0.997
0.999
0.987
0.994
0.970
0.972
0.995
0,900
0.980
0.972
0.361
0.865
0.975
0.990
0.971
0.53
0.550
0.912
0.975
0.988
HCW-223
0.998
0.986
0.994
0.999
0.992
1,000
0,885
0.364
0.574
0.878
0.252
0.668
Ours
0.999
0.988
1.000
0.999
0.999
1,000
0,990
0.881
0.966
0.993
0.991
0.995
Watermark Detection, A surrogate NTP distribution Qx, ja]- is approximated by the SLM for each t. We then use (AI) to approximate P.. Pcllz]-1,, .pe from Q 1, and sample Ço using (A2 with the shared key. At each position t, the score 1 1( = {e} is 1 if & non-rcdundant and 0 otherwise. Compute 1 ET= (() = {e} and compare with threshold A. If above X, the text is detected as watermarked.
Experiments and Discussions
Experiment Settings. We now introduce the setup details of our experiments.
Implementation Details. Our approach is implemented on two language models: Llama2-133 -3BB M. and Mistral-8x 7B [4]. Llama2-7B serves the surrogate model for Llama2-13B, while Mistral-7B used as the surrogate model for Mistral-8xx We conduct our experiments on Nvidia A100 GPUs. In DAWA, set 0.2 and T 200.
Baselines. We compare our methods with three existing watermarking methods: KGW+23 25 EXP- edit (37], Gam 38), and HCW+23 [19], where the EXP-edit, Gumbel-Max and HCW+23 are distortion-free watermarks. KGW+23 employs the prior token as a hash to create a green/red list, with the watermark strength set 2.
Dataset and Prompt. Our experiments are conducted using two distinct datasets. The first is an open-ended high-entropy generation dataset, realnewslike sub-
Table 2: Empirical entropy comparison be-
tween C4 and ELI5 datasets.
set from C4 [49]. The second is a relatively low-
Model
(entropy)
EL.5 (entropy)
entropy generation dataset, ELI5 [50]. The real-
Llama2-13R
0.547
0.272
newslike subset of C4 is tailored specifically to in-
Misual-8x7B
1.475
1.427
clude high-quality journalistic content that mimics
the style and format of real-world news articles, As shown in Table the C4 dataset consistently exhibits higher empirical entropy than the ELI5 dataset across different models. We utilize the first two sentences of each text as prompts and the following 200 tokens as human-generated text. The ELI5 dataset is specifically designed for the task long-form question answering (QA), with the goal of providing detailed explanations for complex questions. We use each question prompt and its answer as human- -ennnatte text.
Evaluation Metrics. To evaluate the performance of watermark detection, we report the ROC-AUC score, where the ROC curve shows the True Positive (TP) Rate against the False Positive (FP) Rate. higher ROC-AUC score indicates better overall performance. The detection threshold À is determined empirically by the ROC-AUC score function based on unwatermarked and watermarked sentences.
6.1 Main Experimental Results
Watermark Detection Performance, To explore our detection performance at a very low FPR, we conduct experiments using Llama2-13B on 10s texts (200-length) from the Wikipedia dataset and compute the TPR at te-01, le-02, 1e 1e-03 03, 1e-04, and 1e-05 FPR respectively. Figure shows that DAWA significantly outperforms other baselines.

---

Table Comparison BLEU score and perplexity across different watermarking methods.
Methods
Human
KGW+23
EXP Edit
Gumbel Mux
IIC++23
Ours
BLBB Score
0.219 8.846
0.158 13:472
0.203 10.126
0.210 9.910
0.207
0.214
Porplexity 4
10.115
10.034
Furthermore, we compare the detection performance across various language models and tasks, as presented in Table [ Our DAWA demonstrates superior performance, especially on the relatively low-entropy QA dataset, validating Theorem and Lemma 3 This success stems from the design of our watermarking scheme, which reduces the likelihood low-entropy tokens being falsely detected as watermarked, thereby lowering the FPR. Moreover, this suggests that even without knowing the watermarked LLM during detection, we can still use the proposed SLM and Gumbel-Maa trick to successfully detect the watermark.
We assess the robustness of DAWA against token replacement attack validate Proposition 4 For each watermarked text, we randomly mask 50% of the tokens and use TS-large [49] to predict the replacement for each masked token based on the context. Table exhhibits watermark detection performance under token replacement attacks across different models and tasks. Our DAWA remains high ROC-AUC, TPR 1%FPR, and TPR @ 10%FPR under this attack compared with other baselines.
Watermarked Text Quality. To evaluate the quality of watermarked text generated by our water- marking methods, we report the perplexity (median) C4 dataset using GPT-3 [5]], and the BLEU score on the machine translation task using the WMT19 dataset [52] and mBART Model [53]. as shown in Table 3 It can be observed that our scheme achieves a higher BLEU score and lower perplexity closer to the unwatermarked one (10.020), both close to the score on human datasets. This demonstrates that our distortion-fre scheme, employing an NTP cntributtionadaaptiin approach, has minimal impact on the generated text quality, preserving its naturalness and coherence.
Ablation Study and Additional Results. In Appendix I we further show that (1) our DAWA is efficient and does not affect generation time; (2) detection remains accurate and robust even with much smaller SLM from a different model family and without prompts; (3) TPR increases with longer token length T;; and (4) our theoretical choice of effectively controls the empirical FPR.
6.2 Extension Towards Stronger Robustness
In Appendix J.1] Table we first empirically assess the robustness of DAWA against random deletion and paraphrasing attacks. DAWA outperforms Gumbel-Max and KGW+23 in deletion robustness and matches their performance under paraphrasing. These results confirm that DAWA remains competitive while balancing robustness, efficiency, and detection accuracy, with the potential demonstrate a graceful trade-off based on our theoretical analyses.
Theoretical Extension. As a step towards even stronger robustness, Appendix Doutlines how our theoretical framework and optimal solutions extend to scenarios involving wide range of attacks, trade-
including ammantic-invrrinn attacks. We characterize the off and show the closed-form optimal robust watermarking scheme-detectee pairs. These findings offer valuable insights for designing advanced semantic- based watermarking algorithms that are resilient to such attacks in the future.
Acknowledgements
This work was performed while Yepeng Liu and Yuheng Bu were with the Department of Electrical and Computer Engincering at the University of Florida. They acknowledge UFIT Research Computing for providing computational resources and support that contributed to the research results reported in this publication. This work was also conducted while Haiyun He was a postdoctoral associate with the Center for Applied Mathematics Comell University and while Ziqiao Wang was a Ph.D. student with the School of Electrical Engineering and Computer Science at the University of Ottawa.
10

---

References
[1] 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 preprini arXiv:2302. 2023.
[2] Aiwei Liu, Leyi Pan, Yijian Lu, Jingjing Li, Xuming Hu, Xi Zhang, Lijie Wen, Irwin King, Hui Xiong, and Philip Yu. A survey of text watermarking in the era of large language models. ACM Computing Surveys, 57(2):1-36, 2024.
[3] Junchao Wu, Shu Yang. Runzhe Zhan, Yulin Yuan, Lidia Sam Chao, and Derek Fai Wong. A sur- vey on LLM-generated text detection: Necessity, methods, and future directions. Computational Linguisties, pages 1-66, 2025.
[4] 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 in Communications, 13(8):1495-1504 1995.
[5] Yoon Yoo. Wonhyuk Ahn, Jiho Jang, and Nojun Kwak. Robust multi-bit natural language watermarking through invariant features. arXiv preprint arXiv:2305.01900 01904 2023.
[6] 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.0888. 2023.
[7] Travis Munyer, Abdullah Tanvir, Arjon Das, and Xin Zhong. Deeptextmark: A deep learning- driven text watermarking approach for identifying large language model generated text. arXiv preprint arXiv:2305.05773, 2023.
[8] 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 1663--16221 2022.
[9] Ryoma Sato, Yuki Takezawa, Han Bao, Kenta Niwa, and Makoto Yamada. Embarrassingly simple text watermarks. arXiv preprint (vXiv:2310.0892) 2023.
[10] Ruisi Zhang, Shehzeen Samarah Hussain, Paarth Neekhara, and Farinaz Koushanfar. (REMARK-LLM)) A robust and efficient watermarking framework for generative large lan- guage models. In 33rd USENIX Security Symposium (USENIX Security 24), pages 1813-1830, 2024.
[11] Sahar Abdelnabi and Mario Fritz. Adversarial watermarking transformer: Towards tracing text provenance with data hiding. In 202/ IEEE Symposium on Security and Privacy (SP), pages 121-140. IEEE, 2021.
[12] Emin Martinian, Gregory W Worell,, and Brian Chen. Authentication with distortion criteria. IEEE Transactions on Information Theory, 51(7):253--254,, 2005.
[13] Pierre Moulin and Joseph A O' Sulliva... Information-theoreti analysis of watermarking. In 2000 IEEE International Conference on Acoustics, Speech, and Signal Processing. Proceedings (Cat. No. (0CH37100), volume 6, pages 3630-3633. IEEE, 2000.
[14] Brian Chen. Design and analysis of digital watermarking, information embedding. and data hiding systems. PhD thesis, Massachusetts Institute of Technology, 2000.
[15] N. Merhav and Ordentlich. On causal and semicausal codes for joint information embedding and source coding. IEEE Transactions on Information Theory, 52(1):213-22) 22622.2222222 2006. doi: 10.1 109/TTT.200..8666 8604288
[16] Neri Merhav and Erez Sabbag. Optimal watermark embedding and detection strategies under limited detection resources. IFFE Transactions on Information Theory, 54(1):255-27) 2008. doi: 10. 10.1109/1TT2200.991122

---

[17] 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 arXiv:2307. 15992, 2023.
[18] Jaiden Fairoze, Sanjam Garg, Somesh Jha, Saeed Mahloujifar, Mohammad Mahmoody, and Mingyuan Wang. Publicly detectable watermarking for language models. arXiv preprint arXiv:2310. 18491, 2023.
[19] Zhengmian Hu, Lichang Chen, Xidong Wu, Yihan Wu, Hongyang Zhang, and Heng Huang. Unbiased watermark for large language models. In The Twelfth International Conference on Learning Representations, 2024.
[20] Mingjia Huo, Sai Ashish Somayajula, Youwei Liang, Ruisi Zhang, Farinaz Koushanfar, and Pengtao Xie. Token-specific watermarking with enhanced detectability and semantic coherence for large language models. arXiv preprint arXiv:2402. /8059, 2024.
[21] Hanlin Zhang, Benjamin I. Edelman, Danilo Francati, Daniele Venturi, Giuseppe Ateniese, and Boaz Barak. Watermarks in the sand: Impossibility of strong watermarking for generative models. arXiv preprint arXiv:231 0..33.1.0378.. 2023.
[22] Shangqing Tu, Yuliang Sun, Yushi Bai, Jifan Yu, Lei Hou, and Juanzi Li. Waterbench: Towards holistic evaluation of watermarks for large language models. arXiv preprint 2 2023.
[23] Jie Ren, Han Xu, Yiding Liu, Yingqian Cui, Shuaiqiang Wang, Dawei Yin, and Jiliang Tang. robust semantics- based watermark for large language model against paraphrasing. arXiv preprint arXiv:2311.0877 2023.
[24] Abe Hou, Jingyu Zhang, Tianxing He, Yichen Wang, Yung-Sung Chuang, Hongwei Wang. Lingfeng Shen, Benjamin Van Durme, Daniel Khashabi, and Yulia Tsvetkov. Semstamp: A semantic watermark with paraphrastic robustness for text generation. In Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume Long Papers), pages 4067-4082, 2024.
[25] John Kirchenbauer, Jonas Geiping, Yuxin Wen, Jonathan Katz, Ian Miers, and Tom Goldstein. watermark for large language models. In International Conference on Machine Learning, pages 17061-17084. PMLR, 2023.
[26] Xuandong Zhao, Prabhanjan Ananth, Lei Li, and Yu-Xiang Wang. Provable robust watermarking for Al-generated text. arXiv preprint arXiv:2306. 17439, 2023.
[27] Yepeng Liu and Yuheng Bu, Adaptive text watermark for large language models. Forty-fusst International Conference on Machine Learning, 2024.
[28] Aiwei Liu, Leyi Pan, Xuming Hu, Shiao Meng, and Lijie Wen. A semantic invariant robust watermark for large language models. In The Twelfth International Conference on Learning Representations, 2024.
[29] Wenjie Qu, Dong Yin, Zixin He, Wei Zou, Tianyang Tao, Jinyuan Jia, and Jiaheng Zhang. Provably robust multi-bit watermarking for Al-generated text via error correction code. arXiv preprint arXiv:2401. 16820, 2024.
[30] Pierre Fernandez, Antoine Chaffin, Karim Tit, Vivien Chappelier, and Teddy Furon. Three bricks to consolidate watermarks for large language models. In 2023 IEEE International Workshop on Information Forensics and Security (WIFS), pages 1-6. IEEE, 2023.
[31] Jiay Fu, Xuandong Zhao, Ruihan Yang, Yuansen Zhang, Jiangjie Chen, and Yanghua Xiao. Gumbelsoft: Diversified language model watermarking via the GumbelMax-trick, arXiv preprint 2022:22402.12948 2024.
[32] Yihan Wu, Zhengmian Hu, Hongyang Zhang, and Heng Huang. Dipmark: stealthy, efficient and resilient watermark for large language models. arXiv preprint arXlv:2310.07710, 2023.
12

---

[33] Xuandong Zhao, Lei Li, and Xu-Xiang Wang. Permute-and-fiig An optimally robust and watermarkable decoder for LLMs. arXiv preprint arXiv:2402.05864, 2024.
[34] Massieh Kordi Boroujeny, Ya Jiang, Kai Zeng, and Brian Mark. Multi-bit distortion-free watermarking for large language models. arXiv preprint arXiv:2402.16578, 2024.
[35] Miranda Christ, Sam Gunn, and Or Zamir. Undetectable watermarks for language models. In The Thirty Seventh Annual Conference on Learning Theory, pages 1125-1139. PMLR, 2024.
[36] Eva Giboulot and Teddy Furon. Watermax: breaking the LLM watermark detectability- robustness-quality trade-off. In The Thirty--ightt Annual Conference on Neural Information Processing Systems, 2024. URL Uttpsttts///ppeeeeviieee wttp:/ww.eeeeerreeeeeeeeee ii
[37] Rohith Kuditipudi, John Thickstun, Tatsunori Hashimoto, and Percy Liang. Robust distortion- free watermarks for language models. arXiv preprint 2307 2023.
[38] Scott Aaronson. Watermarking of large language models. https://simon: bttp://////mmmmommmbeellll berkeley edu/ talks/scott- aaronson ut- austin- -oeeeo-pennaiee 2023- 08- 17 2023, Accessed: 2023-08.
[39] Yuki Takezawa, Ryoma Sato, Han Bao, Kenta Niwa, and Makoto Yamada. Necessary and sufficient watermark for large language models. arXiv preprint arXi::2310.00833 2023.
[40] Bram Wouters. Optimizing watermarks for large language models. In International Conference on Machine Learning, pages 53251-53269, PMLR, 2024.
[41] Zhongze Cai, Shang Liu, Hanzhao Wang, Huaiyang Zhong, and Xiaocheng Li. Towards better statistical understanding of watermarking llms. arXiv preprint arXiv:2403. 2024.
[42] Baihe Huang, Banghua Zhu, Hanlin Zhu, Jason D Lee, Jiantao Jiao, and Michael I Jordan. Towards optimal statistical watermarking. arXiv preprint arXiv:23/2.009900, 2023.
[43] Xiang Li, Feng Ruan, Huiyuan Wang, Qi Long, and Weijie J Su. A statistical framework of watermarks for large language models: Pivot, detection efficiency and optimal rules. The Annals of Statistics, 53(1):322-335 2025.
[44] Albert Q Jiang, Alexandre Sablayrolles, Arthur Mensch, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Florian Bressand, Gianna Lengyel, Guillaume Lample, Lucile Saulnier, et al. Mistral 7b, arXiv preprint arXiv:2310.06825, 2023.
[45] Yinhan Liu. Roberta: A robustly optimized bert pretraining approach. arXiv preprint 19Xiv:1907.11660 1692, 2019.
[46] Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, al. Language models are unsupervised multitask learners. OpenAl blog. 188):, 2019.
[47] Susan Zhang, Stephen Roller, Naman Goyal, Mikel Artetxe, Moya Chen, Shuohui Chen, Christopher Dewan, Mona Diab, Xian Li, Xi Victoria Lin, et al. Opt: Open pre-trained transformer language models. arXiv preprint arXiv:
2022.
[48] E.J. Gumbel. Statistical Theory of Extreme Values and Some Practical Applications: Series of Lectures. Applied mathematics series. U.S. Government Printing Office, 1954. URL
http://booos.oggll..oo/ com wwm comm//bokkssdddSSaAAAAAAAA.
[49] Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lec, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu. Exploring the limits of transfer learning with unified text-to-text transformer. Journal of machine learning research, 21(140):1-67, 2020.
[50] Angela Fan, Yacine Jernite, Ethan Perez, David Grangier, Jason Weston, and Michael Auli. Eli5: Long form question answering. arXiv preprint 197.09190. 2019.
[51] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert- Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott
13

---

Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners. In Advances Neural Information Processing Systems (NeurIPS), volume 33, pages 1877-1901, 2020.
[52]
Loic Barrault, Ondřej Bojar, Fethi Bougares, Rajen Chatterjee, Marta R. Costa-jusså, Christian Federmann, Marcis Fishel, Yvette Graham, Francisco Guzmán, Barry Haddow, Matthias Huck, Antonio Jimeno Yepes, Philipp Kochn, André Martins, Makoto Morishita, Christof Monz, Aurélie Névéol, Günter Neumann, Adrià de Gispert Pastor, Matt Post, Raphaël Rubino, Lucia Specia, and Marcos Zampieri. Findings of the 2019 conference machine translation (wmt19). In Proceedings of the Fourth Conference on Machine Translation (Volume 2: Shared Task Papers, Day 1), pages 1-61, 2019.
[53] Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. Multilingual denoising pre-training for neural machine translation. Transactions of the Association for Computational Linguistics, 8:726-742. 2020.
[54] Tong Zhou, Xuandong Zhao, Xiaolin Xu, and Shaolei Ren. Bileve: Securing text provenance in large language models against spoofing with bi-level signature. arXiv preprint arXiv:2406.01944 2024.
[55] Yihan Wu, Ruibo Chen, Georgios Milis, and Heng Huang. An ensemble framework for unbiased language model watermarking, arXiv preprint 250,:2509,,4443, 2025.
[56] Yihan Wu, Xuehao Cui, Ruibo Chen, and Heng Huang. Analyzing and evaluating unbiased language model watermark. arXiv preprini 2xXiv:2509220488 2025.
[57] Ruibo Chen, Yihan Wu, Junfeng Guo, and Heng Huang. De-mark: Watermark removal in large language models. arXiv preprint arXiv:2410. 13808, 2024.
(58) Yepeng Liu, Xuandong Zhao, Christopher Kruegel, Dawn Song, and Yuheng Bu. In-context watermarks for large language models. arXiv preprint arXiv:2505. 16934, 2025.
[59] Li An, Yujian Liu, Yepeng Liu, Yang Zhang, Yuheng Bu, and Shiyu Chang. Defending Ilm watermarking against spoofing attacks with contrastive representation learning. arXiv preprint wwXiv22544006555. 2025.
[60] Dor Tsur, Carol Xuan Long, Claudio Mayrink Verdun, Sajani Vithana, Hsiang Hsu, Chun-Fu Chen, Haim H Permuter, and Flavio Calmon. Heavywater and simplexwater: Distortion-fres IIm watermarks for low-entropy distributions. In The Thirty-ninth Annual Conference on Neural Information Processing Systems.
[61] Yepeng Liu, Xuandong Zhao, Dawn Song, Gregory W Wornell, and Yuheng Bu, Position: Llm watermarking should align stakeholders' incentives for practical adoption. arXiv preprint 10. 18333, 2025.
[62] Yepeng Liu, Xuandong Zhao, Dawn Song, and Yuheng Bu, Dataset protection via watermarked canaries in aurrivall-ugmentt llms. arXiv preprint arXi::2502.10673, 2025.
[63] Haiyun He, Yepeng Liu, Ziqiao Wang, Yongyi Mao, and Yuheng Bu. Distributional information embedding: A framework for multi-bit watermarking. arXiv preprint arXiv:2501.16555 2025.
[64] Ruibo Chen, Yihan Wu, Junfeng Guo, and Heng Huang. Improved unbiased watermark for large language models. arXiv preprint arXiv:2502.11266. 2025.
[65] Yihan Wu, Ruibo Chen, Zhengmian Hu, Yanshuo Chen, Junfeng Guo, Hongyang Zhang, and Heng Huang. Distortion-free watermarks are not truly distortion-free under watermark key collisions. arXiv preprint arXiv:24466.02603, 2024.
[66] Svante Janson. New versions of suen's 's correlation inequality. Random Structures and Algo- rithms, 13(3-4):467-45 1998.
14

---

A Other Related Literature
In the past few years, many in- in-process LLM watermarking methods have been proposed
including biased and unbiased ddistortion-free ones, Biased watermarks typically alter the next- token prediction (NTP) distribution increase the likelihood of sampling certain tokens [25 For example, [25] divides the vocabulary into green and red lists and slightly enhances the probability of green tokens in the NTP distribution. Unbiased watermarks maintain the original NTP distributions
or texts unchanged, using various sampling strategies to embed watermarks [30 19 64 65]. The
Gumbel-Max watermark 38 utilizes the Gumbel-Max trick 48 sample the next token, while
Kuditipudi et al. [37 introduces an inverse transform method for this purpose.
From theoretical standpoint, most of these designs remain heuristic. While post-process watermark- ing has been extensively studied from an information--heoretie perspective [2H16). the theory behind in in-process watermarking is still limited. Prior efforts [42 45 have analyzed either the watermark
embedder or the detector in isolation, without achieving joint or universally optimal designs.
B Other Existing Watermarking Schemes
Here, we discuss additional existing watermarking schemes utilizing auxiliary variables, which can be encompassed within our LLM watermarking formulation.
The Gumbel-Max watermarking scheme [8] applies the Gumbel-Max trick 48 to sample the next token X₃. where the Gumbel variable exactly the auxiliary variable St which is a V dimensional random vector, indexd by æ. For t = 1,2,
Compute hash using the previous tokens X and shared secret key, i.e., M(X/=I key).
where h : y x R - IR.
Use h(X(-r key) as seed uniformly sample the auxiliary vector Se from [0, 1
Sample X₁ using the Gumbel-Max trick
X arg max log 1x110]-1 (x) log( log (r()))
xEV
In the inverse transform watermarking scheme 377 the vocabulary V is considered as [|V]] and the combination of the uniform random variable and the randomly permuted index vector is the auxiliary variable Çt-
Use key seed uniformly and independently sample {U.)ī= from j0, 1]. and { from the space of permutations over [[]]. Let the auxiliary variable & = (U,, T.). for = ..2.....7 T. Sample X₃ as follows
X; n. (
min [V]:
Σ sE(P=]
(Oxia (x) s s()) v.))
where n. denotes the inverse permutation.
In adaptive watermarking by Liu and Bu (27. the authors introduce a watermarking scheme that adopts a technique similar to the Green-Red List approach but replaces the hash function with a pretrained neural network h. The auxiliary variable Çe is sampled from the set {v E (0. 131V ||v]| = p|V} using the seed h(o(X(-1) key), where h takes the semantics (X(-1) of the generated text and the secret key as inputs. They sample X, using the same process the Green-Red List approach.
C Proof of Theorem 1
According to the Type-I error constraint, we have Vol VT, a 2 max Bq, x7 Por (1((F Aill
QxF
2 R (((xF,<F Ail
= [1pG(1(01 (f) E At)l
15

---

Pel E Ai), (PG E Ai} def,
E is discrete;
E is continuous;
In the following. for notational simplicity, we assume that discrete. However, the derivations hold for both discrete 2 and continuous 2. The Type-ll error is given by 1 1 [X (F) Ai)) We have
EP x o [1((X].
ΣEPxxx A.)
Af(ff. E A1).
21 C
a(T
where for all of E EV² ((x²) & (xf( and c(x)) - P A1) aa
4P'
according to the Type-I error bound. Therefore, ErxT ct [1((X, ,T) E A1ll = Σ C(+f) - (1)
xf
=1
(Px7 (PPF (zf) - a)+
(8)
where 8 is maximized at
PXT
arg min Px] DLP x7 9xp)s of
(Px - a)+
(9)
For any Pxy, the Type-Il error is lower bounded by
Erx of (X((F & Ai)
(ox - a)+
=f"
By plugging Px7 into this lower bound, obtain Type-II lower bound that holds for all y and -T Recall that Huang et al. 42 proposed a type of detector and watermarking scheme that achieved this lower bound. As we demonstrate, is actually the universal minimum Type-Il error over all possible y and Pxf .T. denoted by 81 (QxF, a.
Specifically, define e'(x)) = Qx7 (xT) Px7 (x and we have
Σ
(mT))=
Σ
(x
Σ
(x)
oF (of)
of P (1T)2
Tu (zf)) (oF)so
50
Σ
cxfx
tf (2)20
Σ
c(af)
Σ
c(o))
where the last inequality follows from the total variation distance constraint (xx()xx,0x7)) Se.
We rewrite 37 (Qxx, a.) follows:
(1(xxx,c,a)
min Diilf 4xp)se of
(fp a)+
Σ
(P'p (xF) aa),
of af.P (a
Σ
(0x7(xT) - =x(T) - a)
xf <TPP3paT)22
16

---

Σ (0xp(1)) - -a)
Σ e'(of)
of < xx (xF)2
oF xx (of)2a
2 > (0x - a) - c.
where the last inequality follows from Exf P
xT (zf 22 (x S e, i.. the total variation constraint
limits how much the distribution xxp can be perturbed from Q X Since xx(xx, ,, 2 0, finally we have
Σ (Qx (2 a)+ -
- -))-a)) -c)
#7
Notably, the lower bound is achieved when {oî Pxp (2f) 2 = Qx7 (2f(xt) (xf) 2 Pxp(xf) and (Tv(QxT, Pxp) e. That is, construct PX x.. an amount of the mass of QxT above
is moved below a, which is possible only when Σx; (a Qx (zf)) e. Note that Huang
et al. 42 Theorem 3.2] points out sufficient condition for this to hold: 11T 2 a' The optimal distribution PxT thus satisfies
1
Qxx(xx] (xf(x)))=
Σ
(Px Qx7 (+f)
of OxF
27 2x Dsa
Refined constraints for optimization.
We notice that the feasible region of Opt-I) can be further
reduced as follows: min min
1 cP
(Opt-II)
xT RIINT
I P dep 1, YaT
s.t.
I PETIT (x) S 1 a
Va
(10)
Pxt (x
Sc
/
sup Σ (x7(1at) 2xT of
E (FFlF) (uf)) paaT .F) dcf Sa.
where (10) is additional constraint PerINT- If and only if 10) can be achieved with equality,
the minimum of the objective function ExxT PeTixT [1 - 7XT. cT) reaches 2
D Formal Statement of Theorem 2 and its Proof
Theorem [Formal] (Optimal type of detectors and watermarking schemes). The set of all detectors that achieve the minimum Type-ll error Bi (Qxx, .0,6) in Theorem for all text distribution QxT ) and distortion level e 2 is precisely
m = (7 TxTTT1C <T) = 1 ( = g((T)), for some surjective g 2T -SS VT)
For any valid function g. choose a redundant auxiliary value Si E 2T such that af # gg())) for all of VT. The detailed construction of the optimal watermarking scheme is as follows:
XxT
min
E(Px -a)+,
D(P
and for any of VT , , P (of loft satisfies
(11)
Pxp (xtt) EgT Gt xr
( (Gf off (x (f) Pxp (of)
VCT s.l. (xf - 1;
Px (z ( ) Px
= (Px)
a)+,
i = cf:
P (ff [xf) =0,
(ffluf)
otherwise.
17

---

Proof. First, we observe that the lower bound on the Type-ll error in 2 is attained if and only if the constraint in (IO) holds with equality for all xJ and for the optimizer. Thus, it suffices to show that for any detector 7 & D* the constraint in (10) cannot hold with equality for all xf given any text distributions Qx.- First, define an arbitrary surjective function g : 2 + S, where S is on the same metric space as V Cases I and 2 prove that V C C. Case 3 proves that can only be [xf = g({)))
Case 1: - )({)) but S c CT. There exists of such that for all f.. 1[ = g(f))) = O. Under this case, 110 cannot hold with equality for of since the LHS is always 0 while the RHS is positive.
.
=(({)) but S = VT. Let us start from the simple case where Case 2: 2x = -x)
.
1- {21, 22 3 (11, )2), and g is an identity mapping. Given any Qx and any feasible Px such that DTv(PxxQx)$ S c, when (T0) holds with equality, i.e.
(x) = (x( A and (x,c (2) Px A a,
then the marginal Pe is given by: Pc(G) (x A - (Px(12) - a) Pc(G2) = Px(x22 A a (Px(2)) -.+ The worst-case Type-I error is given by
sup (Rx(t))(x(m))aa+ (Px(22) - a)+) + Qx(((s) (Px(#)) a]+)) Qx
Px (x A (Px(()))))))))--)))))))))))))))) at+
> a, if Px > a, Px(22) > a It implies that for any Qx such that (Px E P(V) DTv((x, S (Px P(V):
Px (I1) > a, (x(222 > a). the false-alarm constraint is violated when (TO) holds with equality. It can be verified that this result also holds for larger (T, V, 2) and other functions g : 2 VT.
. Case 3: Let (x = [CT E ZT [<<
1). 3rf vr VT, s.t. E(x)) + O.
For any detector 7 & D that does not fall into Cases and 2, it falls into Case 3. Let us start from the simple case where T V. = {21, Z {Si, S2, (3). Consider detector y as follows: (x1, (1) = (12, (1) = 1 and y(x = 0 for all other pairs (z, () E V x Z. Hence,
E(x1) (E(2)) = (Si). When (TO) holds with equality, i.e.,
(x.((11,()) = Px (21) A A and
(1) = Px(xz)
we have the worst-case Type-I emror lower bounded by
sup (x((1))((()) + (x(()))))))+(()))( = PP((S)) = Px(x1) Ma+ Px(22) Qx
>a if ix or Px(x2) > a.
Thus, for any Qx such that (Px E P(V): : DTv (xx S $) C (Px E P(V) : Px (x)) >
a Px (22) > a). the false-alarm constraint is violated when (0) holds with equality.
If we consider a detector 7 as follows: 7(11, (1) ((22, G) = ((22 (2)
and 7(x ()
for all other pairs (x, () E V x Z. We still have B(x1) n E(x2) = (G)) When (10) holds with equality, i.c.,
Px.c(=1, Px (m1) A a and Px (1) + Px. (2) = (x2) we have the worst-case Type-I error lower bounded by
sup Qx
+ Qx (ex()))((G)++xxxx))))))
PG(G2))
sup Qx
P((S)) (x(22)
Pe(( + Pc(C2) Px A Px (x2) a > a, which is the same as the previous result.
if Px (x1) > a or Px (x2) > a,
If let V = (a1, (2,3) 2 (S1, S2, (a, (1) and ( <a) in addition the afore- mentioned 7, we can similarly show that the worst-case Type-I error is larger than a for some distributions Qx
Therefore, can be observed that as long as E(xF) (E + for some of + vf V 10 can not be achieved with equality for all Qx7 and e even for larger (T, V, 2) as well as continuous z.
18

---

In conclusion, for any detector & I", the universal minimum Type-Il error in cannot be obtained for all 2xT and e.
Since the optimal detector takes the form (XT,<7) = 1(x7 = g({))} for some surjective function g : z S S y", and the token vocabulary discrete, it suffices consider discrete 2 to derive the optimal watermarking scheme.
Under the watermarking scheme P xT'<? by:
(cf.
and the Type-I and Type-1l errors are given
Type-I error:
Vyf E VT,
Ep 1 s({F)) ST (u) = )(({))
-
E Px ल
of
= Pxp (vf)
Σ T GA = = Aa
aa
and since any distribution Qx7 can be written as linear combinations of oyF we have
max Eq x7 of [1{x] {(( a. 2xT
Type-Il error:
1 1 Ep. =
xp
ΣΣ
P (. =
#7 G
=1 Σ Xx7 (+f)
Σ
&
=1
PPx (xT) Aa)
Σ
(P xx (xf) a))
The optimality of P XT oF XT.sT optimal conditional distribution P XT
is thus proved. We note that (10) in Opt-li holds with equality under this
Compared to Huang al.
42 Theorem 3.2], their proposed detector is equivalent >Xf. 1(X7 = ). where ZT_ =UU (CT) and दT VT meaning that belongs r*
E Illustration of Construction of the Optimal Watermarking Scheme
Using a toy example in Figure schemes, where
5 we now illustrate how to construct the optimal watermarking
XXT
arg min DPP xF o7
((ps((of) - a)+
Constructing the optimal watermarking scheme P cF is equivalent to transporting the probability mass P on V to Z, maximizing P .sT (xf (T) when x =g(TT), while keeping the worst-case Type-I error below a. Without loss of generality, by letting T 1. we present Figure visualize the optimal watermarking scheme. The construction process is given step by step as follows: Identify text-auxiliary pairs: We begin by identifying text-auxiliar pairs (x, () E V/ x with (xx () = 1(x g(C)) 1 and connect them by blue solid lines.
19

---

V
Z
PX
P
(8]
23,00 15,00)
= s()) redundant
Figure 5: A toy example of the optimal detector and watermarking scheme when T 1. Links between V and Z suggest Px X1,6 > O.
Introducing redundant auxiliary value: We enlarge Z to include an additional value and set ((,, 2) = for x. We will call { "reddunant".
-Mass allocation for Px, (x) az If Px, (1) > a, we transfer a mass of Px; (xr) the ( connected by the blue solid lines. The excess mass is transferred to the redundant ( (orange dashed lines). Specifically, for z(1,, where Px, (x(1) > a and x(1) = g(((1), we move a units of mass from P', (x(1) to Pč (c(1)), ensuring that (C a. The rest (Px, (z:11 a)) units of mass moved to Ç. Similarly, for a!(2), where Px, (xx22) > a and x!(2) = g(( we move a mass from Px (ar(2) to P3 22,(C9 (2(2)) and (Px, (z:12) a) mass to Ç. Consequently, the probability of is (c) = (Px, (x()) - a) + (Px, (x(²)) - a). In this way, there is chance for the lower-entropy texts (1)) and (2)) to be mapped the redundant Ç during watermark generation.
and .:(3) g(((3)), we move the entire mass Px, (x) to Pa (c(3)) along the blue solid line. It means that higher-entropy texts will not be mapped to the redundant during watermark generation.
Mass allocation for Px, (xx) < at For 2:(3), where Px, (s:(
((0), keeping the worst-case Type-I error under control. The Type-II error equal to Pt (C), which is exactly the universally minimum Type-II error. This scheme can be similarly generalized to T 1.
Outcome: This construction ensures that P2 (5) I a for all Ç E ((0))
(x. By letting 0, the scheme guarantees that the watermarked LLM remains unbiased (distortion-free). Note that the detector proposed in Huang et al. [4) Theorem 3.2] is also included in our framework, Appendix
In Figure when there no link between (ar, () V 2, the joint probability ,
F Construction of Token-level Optimal Watermarking Scheme
The toke-level optimal watermarking scheme is the optimal solution the following optimization problem:
inf
1-- Xxxxxx 1 - 1 1(X; (()()
Ep
P PxoGIxi-1
s.t. sup Eq 10xxxx-188P Gic [1xx, gik(C)))) Sn, ,
xx1xx-1
The optimal solution P
Xx. sst follows the similar rule as that of PxT Sf in Theorem 2 with (QxT, Pxp,,0 a)) replaced by (Q (Qx,xx-1,, Px,xx-",,1). We refer readers to Appendix for further details.
G Formal Statement of Lemma I and its Proof
Let ptokens and ptoken+ denote the joint distributions induced by the token-level optimal watermark- .T Cr ing scheme.
Cf
20

---

Lemma 3
(Formal) (Token-level optimal watermarking detection errors). Let = (a/ (((()) गि.
Under the detector y ( and the token-level optimal watermarking scheme ps Type-I error is upper bounded by
X -1--1) the
sup Su(?) QXT 2x]
Pi S a.
Assume that when T and n S ' are both large enough, token X, is independent of X i.e. Px..X._. = Px, @ for all 2 n 1 and t E [T]. In = (ji - n, i + n) n [T) By setting the detector threshold as X + Σt= Ex,,c [1 ( H for some E [0, 11. the Type-ll error exponent is
T n
log 31 (7, ptokens
The following the proof of Lemma 3
To choose [TX] indices out of (1,.... 7), there are ((Tx) choices. Let k = 1, ,.... (172)) and Sk
be the k-th set of the chosen indices. The Type-I error is upper- bounded by
Bu(y, Qxm,)
Ptakene) Pr
1(x, r(c))) Ho)
of
T
(17x-)
S Pr
(1{X, -[())) 1, 12 Sk} Hbb)
k=l
[TX])
<
Pr
[1{X,= - = 12 E St} Ho
k=
PEA. m}. We can rewrite PEA. as
Without loss of generality, let m = [T}] and S =
PEA, Exxar SP &P (c))
[[] (X, = 9(:)) Vt S+]l
Ex SP &r
II 1(X, = 9((HH
tES
-Exx MP
1(x1 - ((())) Be xxxx Paai
11X2 - -]((2)}.
EQ 1x OP 1m {1 a(Gm))]] ...
~1"; VQXT- Then the Type-I error is finally upper-bounded by
T
sup 30 Qx7, ,ogt, Plokeny <
17 FTAl < a.
[TA]
2xf
We prove the Type-II error bound by applying Janson 666 Theorem 10].
Theorem 5 (Theorem 10, Janson 66 Let {T: Jizz be finite family of indicator random variables, defined on a common probability space. Let G a dependency graph of I, i.e., a graph with vertex set I such that if A and B are disjoint subsets of I, and T contains no edge between A and B. then {Li)iA and (L))en are independent. We write ~ j if E I and (i,j) is an edge in
G. In particular, i + i. Let S = Ener I and A = B[S). Let V = maxier Ejet, E[I and
== 2 Evez EjEL B[I,[,]. For any 0 s
A
A
Pr(S < aA) < exp
min (1 - a)²
(1 a)
(12)
86 2A
6t
21

---

Given any detector that accepts the form in (5) and the corresponding optimal watermarking scheme, for some (0, 1), we first set the threshold y
TX a Σ xx (1 (X, g(G)))) Σ Ex
Σ ( (xxx- n)+, adT,
where p Xx is induced by P
Xx(xixx-11 .G-
The Type-1l enror is given by
B1 Plokent) XT
Ptokene &f
Σ 1 g(G)) < adT)
which is exactly the left-hand side of 12)
Assume that when T and I T are large enough, token X, is independent of all X,- for all Pxx @ Px. Let In (i) = (Li n, i + (Z)) The
i 2 n 1 and f E [2]. i.e. Xx..,._
and 4 on the right-hand side of (12) are given by:
= max =E(T]
&x, (X, g(s))) = max SE[T]
Σ
Ex,, [1, = g(G)) = (n),
AM
IEIT.e))
Σ
Σ
B[ = - -
Σ
Σ
B[T(X; = - = =
2 iE TE JEZT,...
By plugging Ar. Z and O back into the right-hand side of 12 have the upper bound
(1 a) Ar
31(7: PXTx)) S exp
min
(1 a)²
80 + 2AT
6t
where
U.
Ex x E. (P* x.1x;- (x1x1-1)
4) AT =
E U. V
max (te U, and +- = 2 Eiejn EjeIr.(
E[1 (x; = =g(G))]((X, = ((1))l This
implies
(1 - a)² [ ) , a)o
T
- log (7, ptokens
2 min Xf
n
T
ptokens = log (7, (
X xf .S
=
H DAWA Pseudo-Codes
Algorithm Watermarked Text Generation
Input: LLM Q, Vocabulary V, Prompt u, Secret key, Teken-level false alarm
1: Z (Mvoy (e) U (c} for t I,.... do
PGi1e-1 (Qx11ef-1 (M An), VC 2((O).
4: Pe.1at-1_a(3) + Exev(O (x, (z)) -)
Compute hash of tokens =/= with key, and it seed generate (Ge,)çez from Gumbel distribution.
& +- arg maxçez log log( (_))t + Ge..
7: if + Č then
9: else
12 (xx110--1,_0 (0)-))+
10: Sample
Evev (9xe (0)))))) NEV
11: end if
12: end for Output: Watermarked text of PT).
22

---

Algorithm 2 Watermarked Text Detection
Input: SLM Q, Vocabulary V, Text zf. Secret key, Token-level falsc alarm f, Threshold X. I: score = 0, = ( bevv (C}
2: for f = 1,.., do
3: P (() +- (Q Qx (o (4) An), VC ()())
(()))-1(() Enev(Q (0x111-11 1
Compute hash of tokens x with key, and it seed generate (Gr, from Gumbel distribution.
Si arg m log( 2101 (()) + G... 7: score score +1 +11 (3t) 5t}
end for
if score T' then
10: return
Input text is watermarked
11: else
12: return 0
Input text is unwatermarked
13:
end if
Ablation Study and Additional Experimental Results
All pre-existing models and datasets utilized in this research publicly available and were used in full accordance with their respective licensing terms, which predominantly include common open-source licenses (such as Apache 2.0, MIT, CC BY-SA) and specific community research usage agreements.
Efficiency of Watermark Scheme. To evaluate the efficiency of our watermarking method, conduct experiments to measure the average generation time for both watermarked and unwatermarked text. In both scenarios, generated 500 texts, each containing 200 tokens. Table 4 indicates that the difference in generation time between unwatermarked and watermarked text is less than 0.5 seconds. This minimal difference confirms that watermarking method has negligible impact generation speed, ensuring practical applicability.
Table 4: Average generation time comparison for watermarked and unwatermarked text using Llama2- 13B.
Language Model
Setting
Avg Generation Time (s)
Llama2-138
Unwatermarked
9,110
Llama2-138
Watermarked
9.386
Table 5: Performance comparison of different language models and surrogate models under two scenarios: without attack and with token replacement attack.
Scenario
Language
Surrogate
ROC-AUC
TPR@1%
Llama2-13B Mistral-8
Llama2-7B
0.999
0.998
1.000
Without Attack
Mistral-7B
0.998
GPT-J-68
GPT-2 large
0.997
0.990
0.997
Llama2 13B
LJuma2 7B Mistral-7R
0.989
0.860
0.976
With Attack
Mistral-8 x 7B
0.990
0.881
0.966
GPT-J-6B
GPT-2 large
0.987
0.892
0.962
Surrogate Language Model. SLM plays crucial role during the detection process of our wa- termarking method. We examine how the choice of SLM affects the detection performance of our watermarking scheme. The selection of the surrogate model is primarily based on vocabulary or tokenizer rather than the specific language model within the same family. This choice is critical because, during detection, the text must be tokenized exactly using the same tokenizer as the water- marking model to ensure accurate token recovery. As result, any language model that employs the
23

---

same tokenizer can function effectively as the surrogate model. To validate our approach, we apply our watermarking algorithm to GPT-J-6B (a model with 6 billion parameters) and use GPT-2 Large (774 million parameters) as the SLM. Despite differences in developers, training data, architecture, and training methods, these two models share the same tokenizer, making them compatible for this task. We conduct experiments using the C4 dataset, and the results are presented in Table [ The results demonstrate the effectiveness of our proposed watermarking method with or without attack, even when using surrogate model from a different family than the watermarking language model. Notably, the surrogate model, despite having fewer parameters and lower overall capability compared to the watermarking language model, does not compromise the watermarking performance.
Prompt Agmostic. Prompt agnosticism is a crucial property of LLM watermark detection. We watermark detection performance by conducting experiments
investigate the impact of prompts to compare detection accuracy with and without prompts attached to the watermarked text during the detection process. The results presented in Table [6] Notably, even when prompts absent and the SLM cannot perfectly reconstruct the same distribution of Ç as in the generation process, our detection performance remains almost unaffected. This demonstrates the robustness of our watermarking method, regardless of whether prompt is included during the detection phase.
Table 6: Performance comparison of Llama2-13 13BB under two scenarios: without attack and with token replacement attack, with and without prompts.
Scenario
Language Model
Surrogate Model
Setting
ROC-AUC
TPR@1% 1 FPR
TPR@10% FPR
Without Attack
Llama2-13B 13B
Llama2 7B
Without Prompt
0.997
0.983
0.995
Llama2-133
Llama2-78 7B
With Prompi
0.998
0.989
0.996
Llama2-138
Llama2-78
Withour Prompt
0.977
0.818
0.953
With Attack
Llama2-13B
Llama2-7B
With Prompt
0.979
0.816
0.960
Detection Performance with larger T. Increasing text length generally improves detection perfor- mance for LLM watermarking. We conduct an additional experiment with T = 500, and the results shown below. Both DAWA and KGW+23 show improved performance compared to T 200 (reported in Figure []. Notably, DAWA, a distortion- algorithm, achieves significantly better detection in the low-FPR regime than the distorted KGW+23.
Table 7:
Detection performance at various FPRs for different sequence lengths T.
Length T
Method
TPR@1e-SFPR
TPR@Ie-FFR
1PR@Ie-3PPR
TPR@1e-2FPR
500
KGW+23 Ours
0.876 0.891
0.959
0.986
0.995
0.970
0.996
0.999
KGW+23
0.682
0.916
0.976
200
Ours
0,882
0.951
0.992
0.997
Empirical analysis on False Alarm Control. We conduct experiments to show the relationship between theoretical FPR (i.e., ai) and the corresponding empirical FPR. As discussed in Lemma 3 we set the token-level false alarm rate as 77 = 0.1 and the sequence length as T 200, which controls the sequence-level false alarm rate under a = (17x)) [TA], where is the detection threshold. For a given theoretical FPR a, we calculate the corresponding threshold À and the empirical FPR based on 100k unwatermarked sentences. The results, as shown Table g confirm that our theoretical guarantee effectively controls the empirical false alarm rate.
Table 8: Theoretical and empirical FPR under different thresholds.
Theoretical
9e-43
2e-03
Empirical FPR
1o-04
46-05
2c-05
2c-05
24

---

J Theoretical Extension to Robustness against Broader Attacks
Thus far, we have theoretically examined the optimal detector and watermarking scheme without considering adversarial scenarios. In practice, users may attempt modify LLM output remove watermarks through techniques like replacement, deletion, insertion, paraphrasing, or translation. We now show that our framework can be extended incorporate robustness against these attacks.
J.1 Assessment of DAWA against Deletion and Paraphrasing Attacks
We conducted additional experiments on random deletion attacks and paraphrasing attacks, where DAWA achieves comparable robustness Gumbel-Max and KGW+23. Although it is less robust than EXP-edit, we note that EXP-edit explicitly includes robustness designs and is significantly slower in detection. This demonstrates that DAWA remains competitive while balancing robustness, efficiency, and detection accuracy, with the potential to demonstrate graceful tradeoff based on our theoretical analyses.
Table 9: Detection performance under deletion and paraphrasing attacks.
Deletion TPR 10SFPR
Paraphrasing
Method
ROC-AL'C
TPR ISFPR
ROC-AUC
IPR@ISFPE
TPR 10SEPR
KGW+23
0.895
0.523
0,809
0.769
0.156
0.455
Gumbel-Max
0.501
0.152
0,463
EXP-cdit
0.978
0.955
0,970
0,853
0.245
0,703
DAWA (Ours)
0.918
0.504
0.812
0.770
0.144
0.458
J.2 Theoretical Analysis of f-Robust Design
We consider broad class of attacks, where the text can be altered in arbitrary ways as long as certain latent pattern, such as its semantics, is preserved. Specifically, let V' - [K] be function
that maps a sequence of tokens X" to finite latent space [K] C N4: for example, [K] may index
K distinct semantics clusters and is function extracting the semantics. Clearly, induces equivalence relation, say, denoted by y on VT, where =f y x'T if and only if [=x = [(xT)) Let By (xT) be an equivalence class containing xf- Under the assumption that the adversary is arbitrarily powerful except that it is unable to move any xf outside its equivalent class (x (e.g.. unable to alter the semantics of of", the "f-robust" Type-I and Type- II errors are then defined
Bo(n, Qx7, PCt f) = xxxT oP suPxT (X)( (,(7,, .f) =1]]
(1 PxT . f) == PE (xx) (( =
Designing a universally optimal f-robust detector and watermarking scheme can then be formulated as jointly minimizing the f-robust Type-II error while constraining the worst-case froouust Type-I eиror, namely, solving the optimization problem
inf B1(7, PXT.ST :
s.t. sup 3o(y, Qxt, f) S a, Div(Pxp, (xFx)(QxTF QxT) Sc. (Opt-R)
xPPxT xTT<?"
2x7
We prove the following theorem.
Theorem 6 (Universally minimum f-robust Type-Il error). The universally minimum f-robust
Type-Il error attained from (Opt-R is
(((xx,a,,,]) D(P xT
min
Σ ke[k]
E(>
Σ (xT(xT) Pxy(e3))oo) (FOTT))=
Ise
Notably, (QxT, a, f) is suboptimal without an adversary but becomes optimal under the ad- versarial setting of (Opt-R). The gap between Bi (QxT, e;,e a,, / in Theorem and (QxT, or, e) in Theorem [ the cost of ensuring robustness, widening K decreases (i.e., as perturbation strength increases), see Figure appendix for an illustration of the optimal f-robust minimum Type-II error when f semantic mapping. Similar to Theorem [ we derive the optimal detector and watermarking scheme achieving 3 (Qx7 e, f), detailed in Appendix These solutions
closely resemble those in Theorem
For implementation, if the latent space [K] is significantly
25

---

smaller than V", applying the optimal f-robust detector and watermarking scheme becomes more effective than those presented in Theorem 2 Additionally, similar algorithmic strategy to the one discussed in Sections 4 and can be employed to address the practical challenges discussed earlier. These extensions and efficient implementations of the function f in practice are promising directions of future research.
K Proof of Theorem
According to the Type-I error constraint, we have Vuf yr,
a 2 max EQ &P
sup (xFB
(T 1
xxT
sup E PP
17701 ( 13 = EP&
No. 2 (x))
sup
(xT)
-Σ Pc (c+) 4 (T)B
75
sup
For brevity, let ((k) (xf if [xa)) = k. The f-robust Type-Il error equal to
1 1 xx (nfxTEB,(XT) ( ,{), We have
Bpx
inf (5.
BpxT
sup (FFB)((T)
(oT.CT)
(xT))((77)
Σ Σ (
(
sup
(EBB((F)
KE(K] f(
CT
C(R)
where according to the froobust Type-I error constraint, for all [K].
C(k) <
Σ Pxp (zf), and
=T=S(a )=
C(k) = Σ
(T)
(CT)
Σ
PXTi7
(TT(T)
sup (
TTB((K)
4
P4 (cf)
sup
2
< a
i(EEB())
Therefore,
EP
inf | (TEB(((XT))
S Σ C(k)
KE[K]
Psy((e)) ^ -1)=1- <
(E Pxy(ef)) -a) (13)
Σ Σ
Σ
kE[K]
=T:f(=T)=
kE[R]
where (13) is maximized by taking
((
Px7 P
arg min DIP 4xT)Se kE[K]
Σ
Σ
)=
For any Pxt, the f-robust Type-Il II error is lower bounded by
E
sup (XT)
1 0)
> Σ
(
Σ
Pxy(oT)) -0)
KE[K]
<f=
By plugging P* into the lower bound, we obtain the universal minimum frobust Type- error
over all possible y and PXTRF denoted by
(t(ffQxf,e,0 =
min I
Σ
((E
E
Pxp 3xp(eT) -a) -a)
(14)
Pxp D(x Axp
KE[K]
26

---

L Optimal Type of f-Robust Detectors and Watermarking Schemes
Theorem 7 (Optimal type of f-robust detectors and watermarking schemes). Let 1 be collection of detectors that accept the form
7x1 T for some function g z - S, sn (KK) + and [S| > K. If and only if the detector
= 1[ -1x" - or f(x}) g((
y E y the minimum Type-1l 11 ervor attained from (o reaches (i(Qx a,a.)) f) in (14) for all
C,
text distribution QXT E P((")) and distortion level c E Rzo-
After enlarging 2T to include redundant auxiliary values, the c-distorted optimal f-robust water- marking scheme P*1 X3 .TT
( is given as follows:
((
P*1 X Pxp:Div(Pxp Q Axp)se kE(K)
arg min
Σ
Σ af:f(aa)=
Pxp -a)
and any of E VT.
1) for all of s.I. supsTeB (ff 1: ped
<pip7 (Gf (ff satisfies
Σ P
Σ
pld
P (f
, (
Σ
Pxf(( a.
sup
aTEBy(of))
(B))
# (BB
2) Ac s. [tf E V", ( - 0: ptf ST (xi ( satisfies
=
(cF (x-)) = ((
Σ (x
Σ
pt.
Σ
(xf((TT) -a)
3) all other cases c.: pad x
(ff. O.
Proof of Theorem 7 When f is an identity mapping, it is equivalent to Theorem When f Va" [K] is some other function, following from the proof of Theorem 2 we consider three cases.
Case 1: S ([K) + 0 but |S| < K. is impossible for the detector to detect all the water- marked text sequences. That is, there exist &7 such that for all cT, >(T sT) = O. Under this case, in Appendix K (()(z))) = 0 + (()))(=))-())
Pxp (1 )) A a, which means the froousst
Type-II error cannot reach the lower bound.
Case 2: S S ((KJUTT) # 0 but |S| K. Under this condition, the detector needs to accept the form yX} 5t = {x = g(( }} so as to detect all possible watermarked text. Otherwise, it will degenerate to Case 1. We
see (XT))
input variable and rewrite the detector as
y (f(x)).<7) = 7(7,, <7) = x = (( Similar the proof technique of Theorem
2 can be shown that C(k) in Appendix K cannot equal
Px7 (af)) )) for all
k E [K], while the worst-case froouust Type-I error remains upper bounded by a for all Qx? and
Case 3: Let E, (xf) = If E ZT : (( ( = 1). Bof, of E VL, S.L. f(x)) + f(vf)
and NE # G. For any detector 7 & rÝ that does not belong Cases and 2, it belongs to Case 3. Let us start from simple case where T 1, V = 421, 2a). = 2, 2 = (2,,62 (2), and S = [2]. Consider the mapping ʃ and the detector as follows: f(x1) [ 1, [((3a) = 2, ((m1 = (() 1, 7,33, (2) 1, and 7 = 0 for all other pairs (a, ().
When ((k)) (E Ez).)(TT)= (x)(2T)) ( a for all & i...
Px,c(1i, (1) + (x,((xi,5)) (2) (x,(( + Px,(
= (Px(x)) + Px( Aa,
and (x, (2) Px(x)) Aa,
27

---

then the worst-case f-robust Type-I error is lower bounded by
max EQ
BQx
sup (x73
1( - 1}
2x7
2 EP
sup (TEB(L)
1 ( = 1
(Px(x1) (x(x2)) Aat + Px (23) Aa
a, if Px + (x)) > a (x(xx) a.
Thus, for any Qx such that (Px E P(V) : DTv(Px. Qx) S c) S (Px E P(V) Px(x1) + Px(22) > a Px(x2) > a), the false-alarm constraint is violated when C(k) = Eaf (xf) A a for all k []. The result can be generalized to larger (T,V, 2, K, S), other functions f, and other detectors that belong to Case 3.
In conclusion, and only if y r", the minimum Type-Il error attained from (Opt-R) reaches
the universal minimum f-robust Type-ll enror B7 (f. (x in (14) for all Q Qx? E P(V)) and
E Rzo-
Under the watermarking scheme
pad
the f-robust Type-I and Type-Il errors are given by: XT ST
f-robust Type-I error:
: Nyoî E VT,
Ep E
sup (TB
1/709 =1]
4
Σ Σ
P P
(o) (F)
1/1of =
sup
&T
Σ
Pxt
pad
FITT ( (
1( = 1}
=
sup (TB
of (B)(F))
=
Σ
(x((
Ao Sa.
(f')
and since any distribution QxT can be written as a linear combinations of 6gf
sup E
Ox
sup (TEB;(XT)
13 a.
2x7
f-robust Type-II error:
1 - E
p
sup
1/ = =1
xP
(TE)
ΣΣ
pt
(x)
T
sup
1(7 = =1}
# E(BB(a?)
Σ
Σ
prd
(GT (
sup 1(>()].<)== =1 TTB(()
x
x
kE[R] xf EB(K)
Σ
Σ
Pof(oo)) ^a
kE[K]
27 EBB)(())
Σ Σ
-
KE]K]
EB(()
The optimality of f xf.c7 .CT thus proved.
Figure compares the universally minimum Type- errors with and without semantic-invarian text modification.
28

---

distortion-free
E-distorted
Px
Q x
XxT
universally minimum Type-ll error
P
Q ((f
semantic-invariant text modification
Semantics f(-)
Figure 6: Universally minimum Type-ll error w/o distortion and with semantic-invariant text modifi- cation.
M
Broader Impacts
This paper introduces novel framework and algorithm for LLM watermarking, aimed at advancing field machine learning by enhancing Al safety and data authenticity. The primary positive impacts of work include its potential to identify Al-generated misinformation. ensure integrity in academia and society, protect intellectual property (IP), and enhance public trust in Al technologies. However, given the dual-use potential of watermarking techniques, it is crucial to consider privacy concerns raised by possible misuse-such as unauthorized tracking of data. We encourage the development of ethical guidelines ensure the responsible and deployment of this technology. By considering both beneficial outcomes and potential risks, our work seeks to contribute responsibly to the machine learning community.
29

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction accurately summarize the paper's contribu- tions, including the development of a unified theoretical framework for joint watermark optimization, derivation of optimal solutions, the DAWA algorithm, and experimental validation. These claims are consistent with the content presented in the subsequent sections and appendices.
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 be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long it 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: The paper discusses "Practical Challenges" in implementing the theoretically optimal scheme (Section 3 page 5, line 225), which motivates the token-level design. Section 6.2 and Appendix DJ discuss the robustness of DAWA, including its performance against certain attacks like deletion and paraphrasing (empirically addressed Appendix Table 9 and outlines theoretical extensions for stronger future robustness, implying current trade-offs. specific acknowledged limitation that the sensitivity of DAWA surrogate model mismatch in extreme cases was not empirically tested, although Appendix shows robustness varied SLMs non-extreme scenarios.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are 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 a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-ter system might not 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 seale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
30

---

While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren'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 a complete (and correct) proof?
Answer: [Yes]
Justification: Key theoretical results (Theorems 1 6 Lemma 3 Proposition 4 are presented with their assumptions stated. The paper indicates that complete proots provided in the corresponding appendices (c.g., Appendix Cor Theorem 1, Appendix D for Theorem 2, Appendix (irendix[[foor for Theorem Appendix for Appendix G for Lemma 3). following standard practice.
Guidelines:
The answer NA means that the paper does not include theoretical results.
the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to 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 be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: Section 6 (Experiments) and Appendix | detail the experimental settings, including models used (Llama2-13B, Mistral-8 surrogate models), datasets (C4, ELI5, Wikipedia), prompts, DAWA parameters (1), T), baselines, and evaluation metrics. This should provide sufficient information for others to understand and attempt to reproduce the core findings.
Guidelines:
The answer NA means that the paper does not include experiments. the paper includes experiments, a No answer to this question will not 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 a novel architecture, describing the architecture fully might suffice, or if the contribution is 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 to accomplish this, but reproducibility can also be provided 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.
detailed
31

---

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 clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c)
If the contribution is 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 construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe 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?
Answer: [No]
Justification: We are committed to open science and will make the code for our DAWA algorithm and experimental scripts publicly available on GitHub upon publication of this paper. The datasets used in our experiments (C4, ELI5, Wikipedia) are already publicly available and are cited in the manuscript. While anonymized version of our code is available at the time of submission, the paper provides detailed pseudo-code for DAWA (Appendix HD) and thorough description of our experimental setup (Section anad and Appendix M to allow for detailed understanding and facilitate future reproduction.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cm cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
//nips.cc/publl.. wttppcccccppppp...ee..ee....pppp guwdes/ (ooeeSomiissssiieecceee sow.uuboiiiiioooooicicoooo for more details.
The authors should provide instructions on data access and preparation, including how 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 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 in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
32

---

Justification: Section 6 ("Experiment Settings") and Appendix D provide details on models, datasets, prompts, watermark parameters (e.g.. 1) 0.2, T 200 for DAWA, strength for KGW+23), and evaluation metrics. The choice of is linked to theoretical considerations in Lemma Sanmaaann Band Appendix G
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to 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: [No]
Justification: The paper reports primary evaluation metrics such as ROC-AUC and True Positive Rates (TPR) at specific False Positive Rates (FPRs), with detailed explanations of these metrics provided in Section 6 While error bars, confidence intervals, or formal statistical significance tests are not included for these reported values, our experiments are conducted on large, fixed test sets (e.g.. 10 texts for ultra-low FPR analysis, as described in Section o which provides stability the point estimates of these metrics. The observed performance differences, shown in Figure I and Table are substantial. We acknowledge that quantifying variability, for instance, through multiple runs or bootstrapping, could further substantiate the comparisons, though it is often not standard practice for ROC-AUC and TPR reporting this specific evaluation context due the nature of these aggregate metrics large test corpora and the computational demands of re-running experiments with large language models.
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, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run 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).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but 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 of range (e.g. negative error rates).
If error bars are reported in tables or 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]
33

---

Justification: Section 6 mentions the use of "Nvidia A100 GPUs". Appendix C (Table provides average generation time comparisons for watermarked and unwatermarked text, giving an indication of the computational overhead of the watermarking process. This provides baseline for understanding compute requirements.
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 rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
http:r/ppp..cppp.ltttttticcaaaia ines?
Answer: [Yes]
Justification: The research aims to develop methods for identifying Al-generated text, which can help mitigate misuse such as disinformation and plagiarism, aligning with ethical goals of responsible AI. We have strived for integrity in methodology. theoretical derivations, experimental procedures, and reporting of results. The datasets used are publicly available and appropriately cited, and the research did not involve direct human experimentation that would require IRB approval beyond standard dataset usage. However, given the dual-use potential of watermarking techniques, it is crucial consider privacy concerns raised by possible misuse-such as unauthorized tracking of data. We encourage the development of ethical guidelines ensure responsible use and deployment of this technology.
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 a deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations 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: The paper discusses societal impacts. Section I outlines the significant positive societal impacts, such as mitigating Al-driven disinformation and enhancing data authenticity. The paper also acknowledges challenges related to watermark robustness and the evolving nature of attacks in Section 66.2 Appendix These inherent challenges in ensuring perfect, unbreakable watermarks implicitly relate to potential negative outcomes if the technology misused or circumvented. The discussion Appendix M also addresses the dual-use nature of watermarking. acknowledging potential negative impacts such as privacy concerns from misuse (e.g., unauthorized data tracking). In light of these risks, the paper underscores the importance of developing ethical guidelines for responsible deployment and use this technology.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or 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.
34

---

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 is being used as 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 ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
The paper introduces watermarking methodology and an algorithm (DAWA). It does not release new large language models that would pose a high risk for misuse. The models used for experiments (Ilamma2, Mistral) are existing models developed by other parties.
Justification:
or novel datasets scraped from the internet
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 to 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 challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
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?
Question:
Answer: [Yes)
Justification: The paper properly cites the original sources for datasets (C4 49 ELI5
[50]. WM dataset (52) and models (Llama2-13B (T. Mistral-8x7B 44), GPT-3 [1]]
MBART 55 ). The licenses and terms of use for these assets are explicitly mentioned
(Appendix
M and properly respected.
Guidelines:
The answer NA means that the paper does not use 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 used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
35

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
datasets.papersstt
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is 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]
The paper introduces a new theoretical framework and algorithm (DAWA), which are documented within the paper itself (Appendix [H] for pseudo-code). No sep- arate new datasets or software packages are being released that would require external documentation beyond the paper.
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset 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 sereenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The research does not involve crowdsourcing or direct human subject ex- periments (e.g., user studies with participant recruitment). Evaluation of text quality automated metrics (perplexity, BLEU) and existing datasets of human/Al text.
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 Ethics, 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 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: As no direct human subject research or crowdsourcing was conducted (see Q14), IRB approval was not applicable.
Guidelines:
36

---

The answer NA means that the paper does not involve crowdsoureing nor 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 expect authors adhere the NeurIPS 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.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [Yes]
The proposed DAWA algorithm, specifically its detection phase, utilizes a Surrogate Language Model (SLM) as a component to approximate the watermarked distributions and enable model-agnostic detection (Section (Sectionn]""Novel Tricks"); Algorithm 2
Justification:
This use of an LLM (the SLM) is integral to the methodology of the DAWA detector.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to LLM http:e///earippcccc/ooooeeeereeo for what should or should not be described.
37


Reviews:
[{"review_id": "ZRA4Y6uxfJ", "reviewer": "Reviewer_7FZT", "summary": "The paper addresses the critical problem of deriving the optimal watermarking for LLM. By framing watermarking as a hypothesis testing under distortion constraint, it derives a unified closed-form paradigm of the optimal watermarking scheme. The paper further draws interesting theoretical insights from the detection error-distortion tradeoff, buliding on which it develops a practical token-level watermarking protocol. Empirical evaluations confirms the superiority of the proposed scheme.", "questions": "How does the proposed optimal watermarking scheme reduces to the likelihood-ratio test for a fixed P vs. Q? \nCould you provide concrete examples of how existing watermarking schemes instantiate the bijection g_{t,k}, showing each as a special case of your general mapping function?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "Strengths: The paper casts warermarking as a fresh constrained hypothesis-testing problem, which effectively unifies the watermark embedding and detection into one optimality framework. It manages to give a closed-form expression for the Type-I Type-II tradeoff, with optimality provable from both theoretical and empirical perspectives. Moreover, it provides a plug-and-play paradigm, where any concrete watermark design can be adapted accordingly to yield its own provable optimal detector, making the framework highly general.\n\nWeakness: The paper leverages the classical hypothesis testing framework, which inherently has an optimal rejection region via the likelihood-ratio test as guaranteed by the Neymann-Pearson lemma. However, the paper does not explicitly discuss how the proposed optimal detector reduces to the canonical ratio test. In addition, the core derivations are rigorous but somewhat abstract and dense with little high-level intuitions, making the manuscript less readable.", "was_revised": true, "final_justification": "My question \"the paper does not explicitly discuss how the proposed optimal detector reduces to the canonical ratio test\" has been addressed to resolve my misunderstanding. Therefore I'd like to raise the score.", "rebuttal": ">**Q1.** The paper does not explicitly discuss how the proposed optimal detector reduces to the canonical ratio test. How does the proposed optimal watermarking scheme reduce to the likelihood-ratio test for a fixed P vs. Q? \n\n**A1.** We appreciate the reviewer’s question. The canonical likelihood-ratio test (LRT) is optimal when the null and alternative hypotheses are fully specified by fixed distributions $P$ and $Q$, and when the goal is to minimize the Type-II error (1-TPR) subject to a constraint on the Type-I error (FPR). However, our setting is fundamentally different.\n\nIn our formulation: \n\n1. **Neither** $H_0$ nor $H_1$ corresponds to a fixed distribution: Under $H_0$, the distribution $P_{\\zeta_1^T}$ over auxiliary sequences is **induced by the watermarking scheme** and is **unspecified**. Under $H_1$, the joint distribution $P_{X_1^T, \\zeta_1^T}$ **depends on the design** of the watermarking scheme and is **to be optimized**. Therefore, our detection task is a composite hypothesis test, and the LRT is not optimal in this setting.\n2. Our goal is to minimize the Type-II error (1-TPR) subject to a constraint on the **worst-case FPR** and a constraint on the **watermarked text distortion**.\n3. Moreover, as emphasized in Line 33, **the detector is required to be model-agnostic**, i.e., it cannot depend on $P_{\\zeta_1^T}$, $P_{X_1^T, \\zeta_1^T}$, or $Q_{X_1^T}$, as these distributions may not be available to the detector at test time. Therefore, the likelihood ratio test, which requires knowledge of the underlying distributions, is not applicable. \n\nThese key constraints distinguish our problem from classical hypothesis testing. Given this setup, Theorem 2 characterizes the **jointly optimal watermarking scheme and detector**, where the optimal detector is determined by some chosen function $g$. Notably, this detector **does not reduce to an LRT**, precisely because the assumptions and objectives of the classical setting do not apply in our framework.\n\n---\n\n>**Q2.** Could you provide concrete examples of how existing watermarking schemes instantiate the bijection $g_{t,k}$, showing each as a special case of your general mapping function?\n\n**A2.** We clarify that our framework characterizes the jointly optimal pairs of detector and watermarking scheme. As a result, the existing watermarking scheme, many of which rely on heuristics or focus solely on optimizing the detector, are not special cases of the jointly optimal design and do not instantiate our derived optimal detector. \n\nIn our practical detector design (Eq. (5)), the bijection function $g_{tk}$ is a token-level adaptation of the bijection function $g$ from Theorem 2. To offer a concrete toy example: suppose the token vocabulary is $\\mathcal{V}=\\lbrace a,b,c \\rbrace$. We can define an extended set $\\mathcal{S}=\\lbrace a,b,c,\\\\# \\rbrace$ $\\supset \\mathcal{V}$ and a bijective $g_{tk}$ that maps auxiliary symbols $\\mathcal{Z}=\\lbrace 1,2,3,4 \\rbrace$ to elements in $\\mathcal{S}$.\n\n---\n\n>**Q3.** The core derivations are rigorous but somewhat abstract and dense, with little high-level intuition, making the manuscript less readable.\n\n**A3.** We acknowledge that the core derivations are mathematically involved, and we have aimed to provide high-level intuition through the visual illustrations in Figures 2, 3, and 5, which highlight the theoretical insights and trade-offs. We will revise the manuscript to further improve clarity, including adding more intuition and commentary around key results, to make the presentation more accessible in the final version.\n\n\n---\nWe sincerely appreciate your time and valuable feedback. We hope our responses have adequately addressed your concerns, and if so, we would be grateful if you could consider revising your score to further support our submission. Thank you again for your thoughtful review."}, {"review_id": "kRxbYEQjJH", "reviewer": "Reviewer_RWio", "summary": "This paper presents a theoretical framework for watermarking large language models that jointly optimizes both the watermarking process and the detection method. Unlike previous approaches based on heuristics, the authors provide closed-form solutions that show the optimal watermark should adapt to the model’s natural output distribution. Building on this insight, they propose a practical algorithm called Distribution Adaptive Watermarking Algorithm, which embeds watermarks without distorting text and enables detection using a surrogate language model and the Gumbel max sampling method. Experiments on Llama and Mistral models demonstrate strong performance under low false positive rates and robustness against token-level attacks, while preserving text quality.", "questions": "Refer to the weakness part.", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- The paper provides a theoretically grounded framework for LLM watermarking, addressing both watermark generation and detection in a unified optimization framework.\n- The distribution-adaptive approach achieves good performance at ultra-low False Positive Rates (FPR), with minimal distortion to text quality.\n- Thorough experiments demonstrate the effectiveness and efficiency of DAWA on multiple datasets and language models.\n\nWeaknesses:\n- **Outdated Baseline Comparisons:** The paper lacks comparisons with recent and more competitive methods that explore the performance-detectability tradeoff, e.g. [1,2,3]. These more recent works could provide stronger baselines and highlight the significance of the proposed method.\n\n- **Limited Discussion of Related Work**: While the paper cites many earlier watermarking techniques, it fails to address key advancements in performance-detectability tradeoff optimization from recent years. This omission weakens the contextual positioning of the proposed method.\n\nReference:\n\n[1] CoheMark: A Novel Sentence-Level Watermark for Enhanced Text Quality (2025).\n\n[2] WatME: Towards Lossless Watermarking Through Lexical Redundancy (ACL 2024).\n\n[3] From Trade-off to Synergy: A Versatile Symbiotic Watermarking Framework for Large Language Models (2025).", "was_revised": true, "final_justification": "**The response from the authors satisfactorily resolved the issues I raised. I have accordingly increased my score upward.**", "rebuttal": ">**Q1.** Outdated Baseline Comparisons: The paper lacks comparisons with recent and more competitive methods that explore the performance-detectability tradeoff, e.g., [1,2,3]. These more recent works could provide stronger baselines and highlight the significance of the proposed method.\n\n**A1.** Among the cited works, [1] and [3] appeared **concurrently with our submission**, and thus, making a direct comparison infeasible at the time of our experiments. We will discuss them in the related work section of the final version.\n\nRegarding [2], we have conducted additional experiments to include a comparison with it. The results are summarized in the table below. Our method demonstrates favorable performance in terms of both robustness and detectability under comparable conditions.\n\n**Table 1: Clean Text**\n| Method | ROC-AUC | TP@1%FP | TP@10%FP |\n|:------:|:-------:|:------:|:-------:|\n|  WatME |  0.983  |  0.970 |  0.995  |\n|  Ours  |  0.999  |  0.998 |  1.000  |\n\n**Table 2: Token Replacement Attack**\n| Method | ROC-AUC | TP@1%FP | TP@10%FP |\n|:------:|:-------:|:------:|:-------:|\n|  WatME |  0.923  |  0.623 |  0.750  |\n|  Ours  |  0.989  |  0.860 |  0.976  |\n\n\n---\n>**Q2.** Limited Discussion of Related Work: While the paper cites many earlier watermarking techniques, it fails to address key advancements in performance-detectability tradeoff optimization from recent years. This omission weakens the contextual positioning of the proposed method.\n\n**A2.** To the best of our knowledge, among the plethora of LLM watermarking works, we have cited the most relevant and up-to-date ones both from the empirical and theoretical perspectives. For a more comprehensive literature review, we refer the readers to Appendix A and the recent surveys [4,5] ([2,3] in our manuscript), due to the space limit.\n\nIf there are specific recent works that we have overlooked, we would appreciate it if the reviewer could point them out. We will make sure to include them and expand the related work section in the final version.\n\n\n**Reference:**\n\n[4] Aiwei Liu, Leyi Pan, Yijian Lu, Jingjing Li, Xuming Hu, Xi Zhang, Lijie Wen, Irwin King, Hui Xiong, and Philip Yu. A survey of text watermarking in the era of large language models. ACM Computing Surveys, 57(2):1–36, 2024.\n\n[5] Junchao Wu, Shu Yang, Runzhe Zhan, Yulin Yuan, Lidia Sam Chao, and Derek Fai Wong. A survey on LLM-generated text detection: Necessity, methods, and future directions. Computational Linguistics, pages 1–66, 2025."}, {"review_id": "aBWove7lGF", "reviewer": "Reviewer_uUH1", "summary": "In this paper, the authors propose a complete theoretical characterization of an optimal watermarking scheme. Since the theoretical scheme cannot be instantiated in practice, they also propose a practical scheme approximating the design of the theoretical one.\n\nOn the theoretical side, a constrained optimization framework is proposed. The authors try to find the embedder/detector pair that maximizes the power of the detector constrained by a fixed probability of false alarm and distortion on the text probabilities. A universal construction for the embedder and the detector is provided by solving the optimization problem.\n\nHowever, the framework assumes 1) a non-iterative text generation (text of fixed length)  and 2) direct access to the text distribution of the LLM at both the embedder and detector side. This is impractical, hence the authors develop a method inspired from more classic methods, but guaranteed to be optimal **at the token-level**. The problem of accessing the text distribution is addressed by 1) using the token distribution at each step instead and 2) using a LLM at the detection side to retrieve it. A theoretical robustness bound is provided to justify the use of a smaller/worse LLM than during embedding. \n\nFinally, the practical method is evaluated against over state-of-the-art schemes, showing competitive performance in the tested setting.\n\nTo note, the appendix contains a lot of theoretical extension of the main paper results towards more interesting semantic attacks.", "questions": "1. In the theoretical part, does the key depend on the generation ? As far as I understand, the random sequence is sampled independently but what about the $g$ function? If that is the case, this theoretically imposes a new key for each text which renders the scheme quite useless in practice?\n2. Could the authors improve the experimental setting by: using low FPR ($<1e^{-5}$), sound p-values when possible (see [1]), and report the entropy of each model for each tasks ? \n3. From the **Flawed robustness evaluation** weakness, could the authors find the reason for the lack of impact of the attack and fix the problem to get more significant results?\n4. *(Minor)* It is unclear how the authors control $\\alpha$ in the experimental setting. How is $\\lambda$ chosen ? A  systematic way to set $\\eta$  and $\\lambda$ is provided in the appendix, but I would put it in the main paper as it is the most important parameter of the algorithm. Furthermore, the study of the theoretical vs empirical match of the $P_{FA}$ in the appendix is limited, I would like to see an actual curve over many points, going very low in terms of $P_{FA}$ (at least until $1e{-6}$) since very low $P_{FA}$ is the regime of interest for watermarking\n\n\n**Score increase or decrease** : Given the current state of the paper, I am leaning towards an accept for the theoretical part. However, I might re-evaluate my score depending on the results of a new, better experimental evaluation of the method, given that the current one does not really allow me to a see a significant gain between schemes. I might increase or decrease my score in this situation depending on these results.", "limitations": "Nothing to report", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "## Qualities\n\n**Strong theoretical analysis**: The theoretical framework looks solid and with assumptions and limitations well described (with one caveat -- see the questions). Even though the relevance of the framework is quite limited in practice, I believe the method (joint detector/embedder design) and the results stand by themselves as potentially important for more practical designs. I also note even further interesting derivations the appendix for specific kinds of attacks which is appreciated.\n\n\n**Overall clear presentation the main paper**: Regarding the presentation of the results, the paper is quite well organized (from theory to practice) -- with useful diagrams to explain the more abstract design steps -- notably the construction of the optimal token distribution which is quite trivial when seen through Figure 3 and 5.\n\n## Weakness\n\n**The punchline falls short**: The main weakness of the paper is its practical application. With all the heavy mathematical work done in the first part of the paper, one could expect a straightforward implementation into an actual watermarking scheme. Sadly the assumptions in the theoretical framework are too stringent: optimality computed on text distributions (instead of tokens), assumptions of a static-fixed length text, abstract design of the mapping between the tokens and the secret. This leads the authors to have to make many compromise with respect to the original goal, going back to a very classic design and optimality at the token level for a specific choice of detector.\n\n**Experimental design could be improved**: The experimental design is somewhat weak. The authors report AUC and TPR at quite high FPR in the main paper. This leads to difference in detectability between algorithms which are insignificant -- the claim that DAWA outperforms most other schemes is thus hard to verify here. Strangely, they provide far better metrics in the Appendix with TRP@$1e{-5}$ but only for a single experiment in Table 6. KGW and Aaronson's scheme seem to use the asymptotic detector (z-score) instead of the exact $p$-values described in [1], which would allow a perfect control of the FPR. Finally, the authors claim to test for both low-entropy and high-entropy tasks. However the entropy of generated text is highly dependent on the model used as shown for example in the appendix J of [2].  The distribution of the entropy at each generation not reported, which does not allow to verify their claim regarding entropy.\n\n **Flawed robustness evaluation**: The robustness test is limited only to a single replacement attack (using T5) with half of token masked. Seeing the lack of impact on the detectability on any of the tested watermarking schemes, either 1) the FPR is far too high or 2) despite half the tokens being masked, a lot less are actually modified or 3) the authors use the *Self-Hash* hashing function to retrieve the secret during detection -- despite its robustness this hashing function is known to be highly insecure [3] and thus should not be used.\n\n[1] Fernandez, P., Chaffin, A., Tit, K., Chappelier, V., & Furon, T. (2023, December). Three bricks to consolidate watermarks for large language models. In 2023 IEEE International Workshop on Information Forensics and Security (WIFS) (pp. 1-6). IEEE.\n\n[2] Giboulot, E., & Furon, T. (2024, December). WaterMax: breaking the LLM watermark detectability-robustness-quality trade-off. In NeurIPS 2024-38th Conference on Neural Information Processing Systems (pp. 1-34).\n\n[3] Nikola Jovanović, Robin Staab, and Martin Vechev. Watermark stealing in large language models. ICML, 2024", "was_revised": true, "final_justification": "The authors answered my questions regarding the practical implementation of the algorithm. The limitations of the methods were clearly presented and I believe that the theoretical contribution outweighs the limited applicability in practice.\nThe authors also made effort to provide low-FPR results which I find commendable in the current context of watermarking evaluation.\nFor these reasons, I am ready to raise my score to an accept for this paper.", "rebuttal": "We are grateful for your time, valuable feedback, and appreciation of our theoretical contributions. In the following, we address your concerns point by point.\n\n>Q1. The punchline falls short.\n\n**A1.** While our theoretical framework makes simplifying assumptions, such as a fixed text length, these enable **tractable and rigorous characterization** of the jointly optimal watermarking scheme and detector. Despite the idealized setting, it provides a **solid foundation** for more realistic models.\n\nMore importantly, the theory motivates a **practical watermarking algorithm, DAWA**, based on the key insight that optimal schemes should be **adaptive to the LLM’s generative distribution**—a feature not explored in prior work and central to DAWA’s strong empirical performance.\n\nAs shown in **Figure 1**, DAWA clearly outperforms prior distorted and distortion-free baselines, especially in the **ultra-low FPR regime (e.g., $1e-5$)**, demonstrating that our theoretical insights translate into **practical gains**.\n\n---\n>Q2. Experimental design could be improved.\n\n**A2.** We thank the reviewer for these suggestions and provide detailed clarifications below:\n\n1. **On evaluation at ultra-low FPR:**  \n   We would like to highlight that **Figure 1 on Page 2** already reports **TPR at ultra-low FPRs (e.g., $1e-5$)** as a key experimental result. In this setting, DAWA consistently **outperforms strong baselines**, including KGW+23 [25], EXP-edit [37], Gumbel-Max [38], and HCW+23 [19], with significantly higher TPR. This evaluation was conducted on $10^5$ **texts (200-length) from Wikipedia dataset**, with further details in Section 6\\. **Table 6 in Appendix K** complements this by validating that DAWA’s TPR increases with token length T, confirming the benefit of longer contexts.  \n2. **On experiments with FPR $<1e-5$:**  \n   In many existing works, such as [3-7] and the baselines we compare against (KGW+23 [25], EXP-edit [37], Gumbel-Max [38], and HCW+23 [19]), detectability evaluations are typically reported **only down to FPR $=1e-4$ or $1e-3$**. In contrast, our performance evaluation at FPR$=1e-5$ already places our analysis in a **more stringent and practically relevant low-FPR regime**.  \n   We agree that evaluating under even lower FPR regimes would strengthen the results. However, such experiments require **substantially larger-scale computation and runtime**, which is unfortunately infeasible within the short rebuttal period. We plan to include these extended evaluations in the final version.  \n\\\n   [3] Jovanović et al. Watermark Stealing in Large Language Models. ICML, 2024. \\\n   [4] Kirchenbauer et al. On the Reliability of Watermarks for Large Language Models. ICLR, 2024\\.    \n   [5] Hans et al. Spotting LLMs with Binoculars: Zero-Shot Detection of Machine-Generated Text. ICML, 2024\\.    \n   [6] Wouters, B. Optimizing Watermarks for Large Language Models. ICML, 2024\\.    \n   [7] Chen et al. WatME: Towards Lossless Watermarking Through Lexical Redundancy. ACL, 2024\\.\n\n3. **On p-value in baselines:**  \n   We carefully reviewed [1] and acknowledge that it introduces a **non-asymptotic p-value expression** to better align theoretical and empirical FPR. However, the **detector statistics $S_T$** used in KGW+23 [25] and Gumbel-Max [38] remain unchanged, and the refined p-value merely provides a principled way to **set the threshold**.  \n   In our experiments, we evaluate detection performance using the ROC-AUC score, which captures performance across the full range of thresholds and **does not rely on setting a specific detection threshold or computing p-values**. Therefore, comparing AUC scores and TPR at fixed FPR provides a fair and empirical measure of relative performance across methods.   \n   Moreover, as shown in **Lemma 3 and Table 7 (Appendix K)**, our theoretical choice of FPR in DAWA tightly upper bounds the empirical FPR, providing an **even stronger theoretical guarantee** for threshold selection than [1], which does not ensure an upper bound on empirical FPR.  \n4. **On entropy reporting:**  \n   We estimated the entropy values of the C4 and ELI5 datasets using Llama-2-13B and Mixtral-8$\\times$7B, respectively, with the temperature set to 1 for both models. As shown in the table below, entropy varies by model, which is consistent with your observation, and we confirm that the C4 dataset consistently has higher entropy than ELI5 dataset.\n\n|     Model    |   C4  |  ELI5  |  \n|:------------:|:-----:|:------:|  \n|  Llama-2-13B | 0.547 |  0.272 |  \n| Mixtral-8x7B | 1.475 | 1.4268 |\n\n\n---\n>Q3. Flawed robustness evaluation.\n\n\n**A3.** We address each point as follows:\n\n1. **On the strength of the T5-based attack:**  \n   We note that with 50% of tokens masked, approximately 35% were actually replaced on average by the T5 model, constituting a reasonably strong token replacement attack. This level of perturbation is commonly used in prior works (e.g., KGW+23 [25] and Zhao et al.[26]). If an attack completely rewrites more than half of a sentence, it may begin to significantly alter semantics or text quality, making it less practical. Moreover, as shown in our results, this attack **does degrade detectability for HCW+23**, indicating that the attack is impactful. DAWA’s stable detectability under the same setting reflects the robustness of its design, which includes redundant auxiliary variables.   \n2. **On the limited attack types:**  \n   In Section 6.2 and **Appendix L.1 (Table 8)**, we also evaluated DAWA under **random deletion** and **paraphrasing attacks**. DAWA outperforms Gumbel-Max and KGW+23 in deletion robustness and matches their performance under paraphrasing. These results confirm that DAWA remains competitive while balancing robustness, efficiency, and detection accuracy, with the potential to demonstrate a graceful trade-off based on our theoretical analyses.   \n\n3. **On the report of ROC-AUC and FPR:**  \n   Due to time constraints, we were unable to add robustness experiments on a larger dataset to explore FPR $<1e-5$. However, we report **ROC-AUC** scores in all experiments to reflect detection performance across the full FPR spectrum, ensuring a fair comparison. We plan to add more experiments in the final version.\n4. **On theoretical generalization to robustness:**  \n   Although robustness is not the core focus of this paper, Appendix L outlines how our theoretical framework and optimal solutions extend to scenarios involving a wide range of attacks, including semantic-invariant attacks. These findings offer valuable insights for designing advanced semantic-based watermarking algorithms that are resilient to such attacks in the future.  \n5. **On hashing and use of Self-Hash:**  \n   We clarify that we actually employed the **Left-Hash** function in our experiments. Since cryptographic security is outside the scope of this paper, we did not include an in-depth discussion of hash function security. However, we agree that this is an important consideration and will incorporate a more thorough discussion of secure hashing in future work.\n\n---\n>Q4. In the theoretical part, does the key depend on the generation? As far as I understand, the random sequence is sampled independently, but what about the g function? If that is the case, this theoretically imposes a new key for each text, which renders the scheme quite useless in practice?\n\n**A4.** As we understand it, this question asks if the **secret key** shared between LLM watermark generation and detection depends on the generation scheme. We clarify that the secret key is fixed and used together with prior tokens to generate a sampling seed. Thus, it does not depend on generation and can be directly shared with the detector. \n\nThe function $g$ in the detector is simply a **predefined bijection** between the auxiliary variable set $\\mathcal{Z}$ and a superset of the token vocabulary $\\mathcal{V}$. It is also **fixed and does not change** across generations.\n\nTo offer a concrete toy example of $g$: suppose the token vocabulary is $\\mathcal{V}=\\lbrace a,b,c \\rbrace$. We can define an extended set $\\mathcal{S}=\\lbrace a,b,c,\\\\# \\rbrace \\supset \\mathcal{V}$ and a bijective $g\\_{tk}$ that maps auxiliary symbols $\\mathcal{Z}=\\lbrace 1,2,3,4 \\rbrace$ to elements in $\\mathcal{S}$. This mapping remains static and available to both encoder and detector, and does **not impose a new key per text**.\n\n---\n>Q5. Minor questions.\n\n**A5.** We address each point as follows.\n\n1. **On controlling $\\alpha$ in experiments:**  \n   As stated in Lemma 3 of the main text, the sequence-level FPR $\\alpha$ is controlled through the chosen token-level FPR $\\eta$, the generated sequence length $T$, and the detection threshold $\\lambda$. Specifically, if $\\eta\\in(0, \\min\\{ 1, (\\alpha/\\binom{T}{\\lceil T\\lambda \\rceil})^{\\frac{1}{\\lceil T\\lambda \\rceil}}\\}]$, the worst-case false alarm for a length-$T$ sequence is upper bounded by $\\alpha$.  \n     \n   In general, given $T$ and $\\lambda$, a smaller $\\eta$ results in a smaller $\\alpha$; given $T$ and $\\eta$, a higher $\\lambda$ results in a smaller $\\alpha$.  \n   In practice, we use $\\eta \\= 0.2$ and $T \\= 200$, and select $\\lambda$ using **roc\\_auc\\_score function**, which varies $\\lambda$ over a full range to compute empirical FPR and corresponding TPR (see Figure 1, Tables 1, 4, 5, and 6).\n\n2. **Theoretical vs. empirical FPR and very low FPR regimes:**  \n   **Appendix K, Table 7** shows that empirical FPR aligns tightly with the theoretical upper bound down to $1e-5$, confirming **Lemma 3**. While additional tests at even lower FPRs (e.g., $1e-6$) would be informative, the **theoretical guarantee already holds for any target $\\alpha$**, and Table 7 serves to empirically validate this.  \n   We agree ultra-low FPR regimes are important for high-stakes use cases and will include further evaluations in the final version due to the time limit. We also plan to move some explanations from the appendix into the main paper for better clarity."}, {"review_id": "GK1W55rFj6", "reviewer": "Reviewer_eRkN", "summary": "This paper studied the problem of watermarking and its detection. Authors first formulate this problem in a hypothesis testing framework, aiming to jointly find the optimal watermarking scheme and the corresponding detector. In particular, an optimal detector achieves the highest power under a type I error constraint, while the watermarking scheme satisfies a distribution distrotion constraint. Authors provide a lower bound for the detector's type II error and an detector that achieve this bound. In addition, a practical algorithm DAWA is proposed and demonstrated better performance (large AUC-ROC score) compared to baseline methods.", "questions": "Please see the Concerns section above.", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths:**\n\n1. The motivation and main messages are clearly explained and easy to follow. By formulating the problem in the classic hypothesis testing framework, Section 3 seems to provide a clever and complete characterization for performance of watermarking detectors. \n\n2. The topic of watermarking and its detection is definitely timely and important.  \n\n3. The insights sound right to me, such that a good scheme should be adaptive to LLMs.\n\n\n\n**Concerns:**\n\nI have no major concerns about this work, below are some minor comments: \n\n1. The algorithm clearly has a gap compared to the theoretical results, since some key assumptions do not hold in practice. Authors acknowledged those challenges and proposed DAWA as an approximation. In particular, my questions are:\n\n   (i) DAWA can be sub-optimal in the sentence level. Lemma 3 and Proposition 4 are not unique properies for DAWA, in fact, other token-level detectors such as those in Example 2 also enjoy these nice properties (due to concentration brought by IID $\\zeta_t$). Therefore, it is unclear how much DAWA is better than existing designs from a theoretical perspective. While authors have empricially shown the superiority of DAWA, I feel it still has to been clarified. \n\n  (ii) The recovery process of $\\zeta_t$. Why a significantly different SLM than the original model can accurately reconstruct $\\zeta_t$? My impression is that the recovery can be successful (even partially) when the surrogate model is similar to the original LLM.", "was_revised": true, "final_justification": "Authors have addressed my concern on the reconstruction process, and explained the benefit of using DAWA compared to other token-level watermarking methods. I am therefore leaning to acceptance.", "rebuttal": "We are grateful for your time, valuable feedback, and appreciation of our theoretical contributions. In the following, we address your concerns point by point.\n\n>**Q1.** DAWA can be sub-optimal at the sentence level. Lemma 3 and Proposition 4 are not unique properties for DAWA, in fact, other token-level detectors, such as those in Example 2 also enjoy these nice properties (due to concentration brought by IID \\\\zeta\\_t). Therefore, it is unclear how much DAWA is better than existing designs from a theoretical perspective. While authors have empirically shown the superiority of DAWA, I feel it still has to be clarified.\n\n**A1.** Thanks for the insightful comment. It is correct that DAWA is a **token-level adaptation** of the **jointly optimal sentence-level** watermarking and detection scheme. In **Lemma 3** and **Proposition 4**, our goal is to show that **key theoretical guarantees of the sentence-level optimal design can be partially preserved** in the token-level setting through DAWA, **a property not shared by other token-level methods** such as those in Examples 1 and 2\\.\n\nSpecifically:\n\n* **Lemma 3** demonstrates that **DAWA uniquely controls the worst-case sentence-level FPR** by regulating the token-level FPR. This is **non-trivial** and relies on DAWA’s design being **adaptive to the LLM’s next-token prediction (NTP) distribution**. Such control is **not guaranteed** for other token-level detectors.  \n* **Proposition 4** establishes **robustness to token replacements**, which results from DAWA’s **design of redundant auxiliary variable $\\\\tilde{\\\\zeta}$**. This auxiliary redundancy is a **distinctive design element** of DAWA, not present in prior schemes.\n\nWhile we agree that these results are not directly comparable to theoretical guarantees of other schemes under different formulations, our theoretical analysis complements **extensive experiments** that validate Lemma 3 and Proposition 4 and directly compare DAWA to strong baselines.\n\nIn summary, DAWA is both **principled and practical**: it inherits desirable properties from an optimal sentence-level formulation while remaining effective in the real-world token-level context. We believe this combination, supported by theory and validated by experiments, justifies its contribution. We will clarify this point further in the revised version and continue to refine DAWA both theoretically and empirically.\n\n---\n>**Q2.** The recovery process of $\\zeta\\_t$. Why a significantly different SLM than the original model can accurately reconstruct $\\zeta\\_t$? My impression is that the recovery can be successful (even partially) when the surrogate model is similar to the original LLM.\n\n**A2.** Thank you for the sharp observation. While it may seem intuitive that accurately recovering $\\\\zeta\\_t$ would require an SLM similar to the original LLM, our results demonstrate otherwise; **DAWA’s recovery process of auxiliary variables is robust even with a different SLM**.\n\nAs shown in **Appendix K, Tables 4 and 5**, accurate recovery is still achievable using a **much smaller SLM from a different model family**, and even **without prompts**. This robustness stems from the **special structure of the conditional distribution** $P\\_{\\\\zeta\\_t \\\\mid x\\_1^t}$ induced by the **optimal watermarking design**.\n\nIn particular:\n\n* As illustrated in **Figure 4**, recovering $\\\\zeta\\_t$ only requires reconstructing the conditional distribution $P\\_{\\\\zeta\\_t \\\\mid x\\_1^t}$ and does not require the surrogate NTP distribution $\\\\tilde{Q}\\_{X\\_t \\\\mid x\\_1^{t-1}}$ to precisely match the true token distribution.  \n* As shown in the **right-hand side of Figure 5 (Appendix F)**, for **auxiliary values corresponding to high-probability tokens**, their probability under $P\\_{\\\\zeta\\_t \\\\mid x\\_1^t}$ is **set to the fixed FPR control parameter** $\\\\eta$, and is therefore **insensitive to SLM mismatches**.  \n* For **low-probability tokens**, the corresponding auxiliary value probability **directly reflects the token’s likelihood**, which is typically **low and less sensitive** to variation across models.  \n* Furthermore, the **redundant auxiliary variable** $\\\\tilde{\\\\zeta}$ is assigned a **significantly higher probability** than the other values, making it robust to small perturbations in $Q\\_{X\\_t \\\\mid x\\_1^{t-1}}$ and improving the overall recovery accuracy.\n\nThus, DAWA’s recovery of auxiliary variables is **not critically dependent** on having a close surrogate model. This robustness is a **key strength** of our design, and we will clarify this point further in the final version.\n\n---\nWe sincerely appreciate your support and thoughtful review. We hope our responses have adequately addressed your concerns."}]

Author rebuttal:

Meta-review: This paper studies watermarking of LLM outputs from a hypothesis testing perspective. The authors present a theoretical formulation that aims to optimize both the watermarking and detection through this lens. The paper obtains useful insights from this formulation that, in particular, proves (the perhaps intuitive fact) that an optimal algorithms should adapt to the LLM’s algorithm (which is actually very intuitive). 

The paper then moves to use ideas and insights from their theoretical framework to design an algorithm for practice that they call the distribution-adaptive watermarking algorithm (DAWA). This scheme is optimal at the token level but it also inherits some benefits at the sentence level.

Overall, the reviewers appreciated the theoretical formulation (more) but also found the DAWA useful as well. On the down side, the practical solution makes several compromises and its robustness is also quite limited. The reviewers thought that the positive side outweighs the downside and hence the paper can be a nice addition to the NeurIPS program.
Decision: Accept (poster)