HeavyWater and SimplexWater: Distortion-free LLM Watermarks for Low-Entropy Distributions
Authors: Dor Tsur
Carol Xuan Long
Claudio Mayrink Verdun
Sajani Vithana
Hsiang Hsu
Chun-Fu Chen
Haim H. Permuter
Flavio Calmon
Venue: NeurIPS 2025 poster ()
Keywords: Large language models
watermarking
coding theory
heavy-tail distributions
Primary area: social_and_economic_aspects_of_machine_learning
TL;DR: Using coding theory and heavy tails to design powerful watermarks with zero distortion.

Abstract: Large language model (LLM) watermarks  enable authentication of text provenance, curb misuse of machine-generated text, and promote trust in AI systems. Current watermarks operate by changing the next-token predictions output by an LLM. The updated (i.e., watermarked) predictions depend on random side information produced, for example, by hashing previously generated tokens. LLM watermarking is particularly challenging in low-entropy generation tasks -- such as coding -- where next-token predictions are near-deterministic. In this paper, we propose an optimization framework for watermark design. Our goal is to understand how to most effectively use random side information in order to maximize the likelihood of watermark detection and minimize the distortion of generated text. Our analysis informs the design of two new watermarks: HeavyWater and SimplexWater. Both watermarks are tunable, gracefully trading-off between detection accuracy and text distortion. They can also be applied to any LLM and are agnostic to side information generation.  We examine the performance of HeavyWater and SimplexWater through several benchmarks, demonstrating that they can achieve high watermark detection accuracy with minimal compromise of text generation quality, particularly in the low-entropy regime. Our theoretical analysis also reveals surprising new connections between LLM watermarking and coding theory.

HeavyWater and Simplexwater: Distortion-free LLM
Watermarks for Low-Entropy Distributions
Dor Tsur* Ben Gurion University
Carol Xuan Long" Harvard University
Claudio Mayrink Verdun Harvard University
Hsiang Hsu JPMorgan Chase
Richard Chen
Haim Permuter Ben Gurion University
Sajani Vithana Harvard University
Flavio P. Calmon Harvard University
JPMorgan Chase
Abstract
Large language model (LLM) watermarks enable authentication of text provenance, curb misuse of Sethinne-geerated text, and promote trust in AI systems. Current watermarks operate by changing the next-token predictions output by an LLM. The updated (i.e., watermarked) predictions depend on random side information pro- duced, for example, by hashing previously generated tokens. L.MM watermarking is particularly challenging when next-token predictions are dea--deterministicc. In fact, over 90% of next-token distributions are low-entropy, with more than half the probability mass single token. In this paper, propose optimization framework for watermark design for this regime. Our goal is to understand how most effectively use random side information to optimize the detection quallitt trade-off. Our analysis informs the design of two new watermarks: HeavyWater and SimplexWater. Both watermarks are tunable, gracefully trading- off between detection accuracy and text distortion. They can also be applied to any LLM and agnostic side information generation. We evaluate the performance of HeavyWater and Simplexaater across several benchmarks, demonstrating that they achieve superior detection with minimal degradation in downstream qual- ity across generation tasks. Our theoretical analysis also reveals surprising new connections between LLM watermarking and coding theory.
Introduction
Watermarking large language models (LLMs) consists of embedding signal into the text generation process that allows reliable detection of machine-genene generated text. Over the past two years, there have been increasing calls for LLM watermarking by both policymakers (33 and industry [4] Watermarks enable authentication of text provenance (5), promote trust in AI systems (6), and can address copyright and plagiarism issues [7. g) Ideally, watermarks should be detectable directly from text without access to the underlying LLM. Watermarks should also be tamper-resistane i.e. robust to minor edits or paraphrasing of watermarked text and incur little degradation in text quality.
LLMs are watermarked by changing their next-token distributions according to random side infor- mation (see Fig. 2 for a visualization). Side information is typically generated by hashing previous tokens and secret keys, then using the hash to seed random number generator to produce sample 12 The side information s then used change the distribution from which the next token is sampled. Watermarks are detected by mapping a token æ and corresponding side information to a score f(x, 8). By averaging scores across a sequence of tokens, we can perform statistical tests
'qqual contributions.
Equal contributing senior authors.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

to decide if the text is watermarked. Watermarking is particularly challenging when the next-token distribution has low entropy, as often the case in tasks such code generation [33
Our goal is to design watermarks that optimally use side information to maximize detection accuracy and minimize distortion of generated text. Our starting point minimax optimization framework for watermark design. This framework allows us to jointly optimize how side information is em- bedded into next-token distributions and the score function used for watermark detection. When restricting the optimization to binary-valued scores, we uncover a surprising new connection between LLM watermarking and coding theory: designing thinimax-optinee watermarks is equivalent to constructing codes with large Hamming distance between codewords. We use this finding to design new watermark called exWater based on Simplex codes [14]. In the low-entropy regime, Simplexwater is optimal across binary watermarks and empirically outperforms competing methods that use binary scores (cf. Red-Green 15,, and Correlated Channel [16 in Fig.
Next, we relax the binary restriction on the score function. We consider score functions whose outputs are independently and identically (i.i.d)) drawn from a continuous distribution prior the start of watermarking. Interestingly, we show that the Gumbel watermark [17] specific instan- tiation of our framework when scores are drawn from Gumbel distribution. We prove that, in the low-entropy regime, watermark detection de- pends on the weight of the tail of the distribution from which scores are sampled. This observation leads to HeavyWater, whose scores are drawn from a heavy-tailed distribution. HeavyWater out- performs competing state-of-the-an watermarks terms of detection-distorion trade-offs (cf. Gum- bel in Fig.
10000
Red Green
Inverse Transform
Gumbel
SyrthID
Watermark
SimplexWater (Ours)
HeavyWeter (Durs)
0.300
0.325 0.350
0.375
0,400
0.425
0.450 0.435
Crass-Entropy [nats](-)
Figure 1: HeavyWater and SimplexWater demon- strate favorable detection performance (measured by p- p-aluues) with minimal distortion to the base unwa- termarked model (measured by Cross-Entropy). See Section 5 for details. In practice, Simplexwater and HeavyWater are implemented by solving an optimal transport (OT) problem 18 that maximizes the average score across all couplings between the side information and the next-token distributions. We efficiently solve the OT problem using Sinkhorn's algorithm [19. Since the OT preserves the average next-tole text-token distribution, both watermarks are distortion-free, and a user without knowledge of the side information would not perceive an average change in generated text. SimplexWater and HeavyWater are also tunable: we provide simple scheme to further increase watermark detection accuracy at small distortion cost by upweighting high-score tokens.
Our main contributions are:
We introduce SimplexWater. a binary score watermark rooted in coding theory, and derive optimality guarantees across all binary-score watermarks.
We analyze watermarks that use randomly generated score functions drawn from continuous distribution, and show that the Gumbel watermark [17) is a special case of this construction.
We prove that the detection power of watermarks with randomly generated score functions depends on the tail of the score function. This leads to HeavyWater, new watermark whose scores are randomly drawn from heavy-tailed distribution.
We demonstrate the favorable performance of HeavyWater and SimplexWater across array of models, datasets, and tasks, relative to state-of-the-art watermarks.
Related Works
We discuss the related work most closely related to ours next, and provide a broader survey of the watermarking literature in Appendix A. The first LLM watermark was proposed in [5] referred here as the Red-Green watermark. This method partitions the token vocabulary into two lists, which are then used to reweigh the token distribution via exponential tilting. The Red-Green watermark was extended via different random side information generation schemes [10]. Watermarking has since been extensively studied, with more recent work introducing sampling schemes to improve

---

Secret key
Seed Generation
S Ps
?
Px
Watermarker Score f(z, Pxis
Fi
Detector Score f(x,a)
p-value
LLM
Figure 2: Visualization of the components of watermarking design.
watermarking [20] and multi-draft watermark generation methods 211. The use of threshold tests over average scores to detect watermarks a common paradigm in the literature, a design decision we make here was questioned in [22] 23 [23), in particular, shows that more sophisticated statistical lests can boost watermark detection. We note that our watermarks can be paired with multi-draft methods such as [1 to boost detection, though we do not explore this here.
Distortion-free Watermarking. In watermarking, distortion quantifies how much a watermark distribution differs from the original LLM output and is proxy for textual quality. [17] uses the Gumbel-max trick to design a distortion-free watermark. This scheme was relaxed to a soft reweigh of the next-token distribution 24 following the idea from the Red-Green watermark. The Gumbel watermark achieves excellent performance in our benchmarks, though it is outperformed by HeavyWater. Another popular distortion-free watermark is [13, which uses inverse transform sampling. SynthID [I]. in turn, produces watermarked tokens via strategy called tournament sampling. This watermark was extensively evaluated in real-world user tests, and we also select it as a competing benchmark. More recently, [I6) proposed a binary-score watermark based on partitioning the token vocabulary into an arbitrary number of sets, followed by simple binary test for watermark detection. The method in [16] is simple to implement and incurs little runtime overhead. However, underperformed both HeavyWater and SimplexWater in our benchmarks. Additional distortion-fre watermarks include [25] which combines surrogate model with the Gumbel-max
trick to boost watermark detection.
Low-Entropy Watermarks. Several schemes were proposed to address the challenge of watermark- ing low-entropy distributions [0. 26) (27 proposes a resampling method that applied to adapt the Red-Green watermark to low-entropy distributions, while (28) turns to semantic sentence-level
watermarks, 29 uses logit-free method that injects the texts with words from an moput-dependent set, and [30 weights the tokens' scores according to their entropy. We share a similar design goal of optimizing the watermark for the low-entropy regime.
In practice, side information will not be perfectly random: it will depend on previous tokens and a secret shared key through various hashing schemes [15] 31. Hashing schemes range from simple max/ max/min min operations to elaborate adaptive context windows [1] and semantic hashing (32). We view side information generation separate yet less important problem. Instead, we focus on how to optimally use side information, and we develop principled and theory-guided approach for watermark design.
2 LLM Watermarking Framework
In this section, we outline an optimization formulation for LLM watermarking. We denote random variables using capital letters (e.g., and S), their realizations by lower-case letters (e.g., x and s), and their distributions by sub-scripted P Q (e.g., Px and Ps). We consider LLM with token vocabulary X' from a distribution Qx, per-token basis, so we denote Px Qx, for simplicity.
m] é {I.... m). During generation, the t-th token is drawn auto-regressively with support in X. We assume watermarking is performed on a
Consider two parties: the watermarker and the detector (see Fig. [ For each token generated by the model, both parties share random side information, represented by random variable S ~ P3 over discrete alphabet S = [1 kt). The watermarker has access to the next-token distribution Px. Their goal is to change Px using the side information S. The detector, in turn, identifies the watermark from a sequence of observed tokens and side information pairs (X, S) and does not know Px. We divide the watermarking procedure into three main components.
3

---

The first component is random side information generation. Both the watermarker and the detector must produce the same side information S. practice, this is accomplished by employing hashing strategies: previous tokens and a secret key are combined and hashed to produce a seed for random number generator [11 [5]. This generator then serves as the distribution Ps from which side information S is sampled. Popular hashing strategies consider min, max or sum operations over some finite context window of previously generated tokens. Note that both the watermarker and the detector can produce the side information since it only depends on previously generated text and shared keys.
The second component deals with how randomness is used. We begin by designing a score function f: X x S + E that maps a token x and corresponding side information s onto score f s). The score function f is fixed and known to both the watermarker and the detector. In the watermarking stage, we use f and the shared randomness s to change the next-token distribution. Specifically, the watermarker samples from the conditional distribution Sx|s== instead of Px. The distribution
Px|s=, is designed to increase the probability of tokens with high scores f(- s). We call the altered distribution Px Sms the watermarked distribution.
The last component is watermark detection. In the detection stage, the detector receives a sequence of tokens and side information realizations {(x,, se)] from which they compute sequence of scores [f(ze 8t) 1=1- We assume the sequence of tokens is declared as watermarked if the averaged score - (322 2 r, where is a threshold that trades off between specificity and sensirivity of watermark detection. See Figure 2 for a visualization of the watermarking procedure.
Most existing watermarks can be instantiated in terms of the three components above. For example in the Red-Green watermark [[3] S is a sequence of m bits (k = )",,, assigning one bit per token. A realization of side information is used to partition X' into two lists, corresponding
the entries that are drawn as 1 or O. Tokens marked as ("green list") are upweighted, and tokens marked as ("red list") are downweighted, resulting in the watermarked distribution Px|s== from which the next token is sampled. The score function is binary: s(x,s) 1 if is in the green list determined by s, or 0 otherwise. Detection is done by averaging binary scores and performing a threshold test.
An Optimization Formulation for Watermarking. Given the framework above, we present an optimization formulation from which we derive and analyze AxmplexWater and HeavyWater. Our focus is on optimizing the watermarked distribution Pxis and the score function f(x, s) when Ps is the uniform distribution and we generate a sample ~ Ps for each token. We also assume watermark detection is based on thresholding the average score 1 v Ei= f(r,, s:) which, in turn, acts as a proxy for ({f((,))) When the text is watermarked, this expectation is with respect to Our goal is to design pair
Pxs Pxis and otherwise, it is taken with respect Px Ps I (J, sx that maximizes the gap between average score when text is watermarked relative to when the text is not watermarked.
Watermark performance will inevitably depend on the entropy of the next-token distribution Px
10
13
We focus on low-entropy distributions, whose watermarking is considered to be challenging We adopt the low-entropy constraint given the following definition.
30
Definition (Lowwentropy distributions). We use min-entropy as our measure of uncertainty for the
next-token distribution Px, defined as
Hmin (Px) =-l==
log, max Px(x).
A distribution Px is said to be low-entropy if its min-entropy satisfies Hmin( S $1 bit/token, i.e. at least one token has probability mass greater than 1
Remark (Watermarking in Low-Entropy Regime). Our theoretical guarantees imply favorable watermarking performance in low-entropy scenarios. The 'low-etropyy constraint used in our analysis is not merely a theoretical assumption. It based on the empirical observation that LLMs' next-token distributions are inherently low entropy. Even though coding, Q&A, and summarization tasks are commonly understood as having varying degrees of 'entropy' with coding assumed to have lower entropy-
still observe > 90% of next-token predictions across these tasks falling
"See Appendix A.2 in which we instantiate additional watermarks within the proposed setting. "Observe that Ps corresponds to the null hypothesis (non-ward watermarked text): the generated tokens are independent of the side information S.

---

well within the low-entropy considered in our theoretical analysis for practical temperature values Page 13] and [34 Page 4] for similar
(see Appendix Figures| D.14 and and D.15j. Refer to discussion.
Given the aforementioned assumptions, the optimal score function / and the joint distribution Pxs that maximize detection performance for the worst-case distribution in PA the solution of the optimization problem
(EPxisPs S)( Ex (f(X,))). (I)
D Dgap(m k F)
max fe
min PxEP
max PX8
Soore
LLM distribution
Watermurked distribution
We call (T) the maximum detection gap. We restrict the inner maximization in 1 to couplings between the marginals (Px, Ps), ie., Pxis induces a joint distribution Px.s X S whose
marginals are Px and Ps. As a result, the inner maximization is an OT problem [35] 36.. We denote the class of couplings of (Px, Ps) as xx,,s- By limiting watermarked distributions couplings, ensure that the watermark distortion-free: we have E3 PPxss] = Px. From the perspective of a user who does not know S, distortion-free watermarks incur (in theory) perceptible change in text quality. In Section
we propose a simple scheme that distorts the coupling solution to further
increase D gaap
Proposed method. Following the optimization ( we propose two watermarking schemes in Sections and 4 respectively. Both watermarks differ on the nature of the score function f, but share the same underlying algorithmic structure given in Algorithm [ and described next.
Our watermarks receive as input the next-token distribution Px, side information sample E S, and a score function f. Given a pair f), the inner maximization in (T) amounts an OT problem between Px and Ps. which is set to be uniform on [1 k). The OT problem is given by
P = arg max
(Epxs [/(X, S)] Epp ()))
(2)
Ex
We solve (2) using Sinkhorn's algorithm
19 Note that the score function f can be equivalently denoted as the (m X -)mmiennsio OT cost matrix C, which is defined as Car,s' -f s') for (x', 8') E [1: : m] x [1 : k).. Sinkhorn's algorithm yields a coupling Px,s. from which the watermarked distribution is obtained via Pxis=x(1ss k Px,s(: s). The watermarked distribution is used to sample the next token.
Tilting. The watermarked distribution returned by the OT optimization does not change the average next-token probabilities. To further increase watermark detectability, we propose a tilting operation to Pxis=a. which we denote by tilt. The tilting operation increases the probability of higher scoring tokens, at the cost of incurring distortion to PxIS==- This done by increasing the probability of E X' with fa, s) Exx. (X, S)] and decrease the probability of E X with f(x, s) < Exx, (f(X, {)}- The amount of tilting (and thereby the level is distortion) is determined by parameter 5 E (0, 1). The structure of tilting depends on the structure of f and is later defined for each watermark separately. See Algorithm for the list of steps.
Detection. Watermark detection is performed follows: Given token sequence (æ1...., 2n) and score f we recover the set of side information samples (si...., .n) and compute f(r,, st) for each observed pair 8t). We declare the text watermarked if the average score >i [( 8.) exceeds a user-defined threshold T 2 0.
Limitations. As we will see shortly, ( will inform the design of watermarking schemes with favorable empirical performance. However, this optimization framework not without limitations. First, it is restricted to threshold tests applied to the averaged score, which are potentially suboptimal 37]. Second, we assume perfect randomness for side information generation, i.e., we can sample uniformly distributed and i.i.d. random variable S for each token. When X is not watermarked, we also assume it is independent of S. In sequential hashing schemes this not necessarily the case, since both S and X will depend on previous tokens. We emphasize that generating high- quality side information remains an important practical challenge relevant to all existing watermarks, including ours. Nevertheless, from design perspective, this challenge is somewhat orthogonal to our guiding question of how to optimally use side information. We examine the impact of non-i.i.d. side information on watermark design in Appendix D.2
5

---

Algorithm SimplexWater and HeavyWater Watermark Generation
1: Inputs: Token distribution Px. score function J. side information 8, tilting parameter 8.
2: Outputs: Watermarked distribution Px|s==
3: Calculate OT cost matrix Cut,s' = -faa', s'), for all (a', E [1 m] [1:00 :1:k]
4: Px.s = Sinkhorn (C, Px. Ps), where Ps- = Unif([1 : :])
5: Px]s==(2|s)
k Px,s (2,
6: i > 0 then
7: Px|s== tilt(Px S=s= 8,
8: Normalize Pxis=s
9: end if
10: Return Px|s=s
SimplexWater: Watermark Design With Binary Scores
In this section, we consider the class of binary score functions, i.e., F= - { x
{0, 13]. Within this class, solve (I) to obtain the optimal binary score function f. and present the corresponding optimal watermark, which we call SimplexWater. We first present a simplification of the maximum detection gap in (I) for Foin and the low-entropy regime À E [1/2,
Proposition 1. Let [ 1). For Fbim. define the vector S: [s 1),,............. ... f 10 for each E X. Then,
(1 (1- (-X)da((isJh)
(gap(m, k, X, Fbin) = max feFF
min ijEXisn
k
where du b) (a,stb.) denotes the Hamming distance between a, 1 and 1 is the indicator function.
Remarkably, is equivalent to classical problem in coding theory: the design of distance- maximizing codes! In this problem [14), the goal is to design a set of m binary vectors of length k- called codewords with maximum pairwise Hamming distance [4 38. There is one-to-one equivalence between designing a code with maximum distance between codewords and designing binary score function for watermarking LLMs: for fixed token æ. the score function vector [S(x,1), 1),..,,,, f(x, k)] can be viewed as a codeword. Conversely, a distance-maximizing code can be used to build binary score function that maximizes the detection gap. This connection with coding
theory allows us to use classic coding theory results specifically the Plotkin bound [3 to derive an upper bound for Dgap in (3). This result is stated the next theorem.
Theorem (Maximum Detection Gap Upper Bound). Consider the class of hinary score functions
[221) 1). the maximum detection gap can be bounded as Fbin and uniform Ps. Then, for any E
mm11 1(1-1) X) 2(m 1)
D Dgap(mn (m, k Fbin)
The proof of Theorem D is given in Appendix B.2 For a fixed token vocabulary size m, this bound remains the same for any choice of k. Therefore, any score function constructed with any that achieves this bound is optimal. This observation serves as the starting point for our optimal watermark design, leading to SimplexWater
SimplexWater: An Optimal Binary-Score Watermark. The upper bound in (4) achievable when the score function is constructed using simplex code family of codes that attain the Plotkin bound 40 [1 A simplex code is defined as follows:
Definition 1 (Simplex Code). For any x, 0 m - 11. let bin(x). bin(s) denote their binary representations respectively using log, m bits. A simplex code fsim : [0 m- x m m- {0, 1]
characterized by
fsim (x, s) doo((binzz), bin(s))
(5)
where (bin(() bi)())) A logg bin(x);; bin(s), and bin(u); denotes the ith bit in the binary representation of v.

---

We present next SimplexWater. a watermark that employs the simplex code as its score function. SimplexWater operates according to the steps of Algorithm [] where the cost matrix is derived from fai- Specifically, given token distribution, side information and the cost matrix derived from Ssim- SimplexWater solves the OT via Sinkhorn's 's algorithm to compute the watermarked distribution Pxis. The optimality of SimplexWater follows directly from its one-to-one correspondence to the Simplex code that attains the Plotkin bound and is stated formally in the following theorem.
Theorem 2 (SimplexWater Optimality). For any X E [ 1) the maximum detection gap upper
bound is attained by $ Simple eawtee..
The proof of Theorem is given in Appendix B.3 Together, Theorems ! and imply that Simplexatte is minimax optimal among all watermarks with binary-valued score functions in the low-entropy regime.
As outlined in Algorithm| obtained by SimplexWater. For binary-valued scores, the tilting operation (Alg. | step 7) is
| we further increase detection by tilting the watermarked distribution
tilt tilt(P 8, 5) (r, s) (1 + 8- (I(r(s,))=1) [(s(a.))
(6)
In Section 5 we show that by adding mild distortion we significantly increase the detection power of SimplexWater.
4 HeavyWater: Watermarking using Heavy-Tailed Distributions
So far, we restricted our analysis binary scores, i.e., f(x, E (0, 1}. In this case, the detection gap is bounded by m(1 - (2) 1)) as shown in Theorem - and Simple exwater achieves this bound. However, the binary constraint is quite restrictive. Watermarks such [17] are not restricted to binary scores and achieve excellent performance in practice (see Gumbel in Fig. D In what follows, we relax the binary constraint improve variation the score values, enabling us to break the binary detection barrier and significantly enhance detection performance.
We consider score functions where each score fzz s) is sampled independently from continuous Remarkably, under this formulation, the popular Gumbel watermark (17) emerges special case when scores drawn from Gumbel distribution [42]. Our framework allows us to explore a broader class of heavy-tailes distributions that improve upon the Gumbel approach (Figure 1).
distribution prior to the watermarking proces [
HeavyWater: Heavy-Tailed Score Distributions for Improved Detection. Consider the water- marking setting where we draw each score value f(x, s) i.i.d. from continuous finite variance distribution Pp. This score is used in the OT problem in (2) and Algorithm to obtain the wa- termarked distribution. Next, we show that the Gumbel watermark [17 falls into this category of watermarks when PF is a Gumbel distribution.
Theorem 3 (Gumbel Watermark as OT). When the score random variables f(x, s), are sampled i.i.d. from Gumbel(O, 1), the solution to the OT problem in (2) converges to the Gumbel watermark [17] as [S] k + co.
This connection situates the Gumbel watermark within our broader framework ( Can the Gumbel watermark be improved by selecting a different score distribution Pp? Intuitively, heavy-tailed Pr (which Gumbel is not) could increase the probability of sampling large values of f(x, 8), thus also increasing the likelihood of watermark detection. To make this intuition precise, we analyze the maximum detection gap I when the score function is randomly generated instead of selected from set F.
For fixed | = m. |S| k, and A E [] 1), denote the worst case detection gap achieved by some fixed distribution Pr as,
D Prl (m, k, A)
min max (Exxs [f( - Exx Ps (f),
Ex Pxs
Note that D [Pr] (m, k. is random variable due to the randomness of the f(x, s) samples. We pro- vide high-prooe gighbprobabblityy guarantees on the achievable maximum detection gap for any fixed distribution Pr in the regime of large kt
A natural tirst step would be to extend SimplexWater by using q-ary instead of binary codes. This, however. results in marginal performance gain, discuss in Appendix C.3
7

---

Theorem 4 (Detection Gap). Let À E 22 1). and consider the score difference random variable = [xx, 8) - f(a'', 8)) for some (I,8) # (x', 8)), where f(x, 8) and [(x', are sampled i..d. from Pp. Let the cumulative distribution function of be F, and let Q = be its inverse. Then,
lim D P (m, k. 2) '-- Q(u)du,
(8)
Theorem 4 shows that detection performance improves when the distribution of A f have heavier tails, where both (zx,s) f(r',, f(x', ~ Pp. We analyze several choices of heavy-tailed PF for maximizing J Q(u)du (see details Appendix C.2
f(r s)
HeavyWater: A watermark with heavy-tailed scores. We propose HeavyWater, watermark that leverages Theorem 4 and samples the score function from a heavy-tailed distribution. HeavyWater follows the steps of Algorithm [ but uses scores that are generated by sampling i..d. from heavy- tailed PF prior to generation. We explored several options for selecting Pp. In theory, the Gamma distribution maximizes (8) actoss several common heavy-tailed distribution (Appendix(C.2) However, in practice, we observed that choosing Pr to be lognormal achieved the highest detection accuracy Assuming that Pp is normalized to have zero-mean, the tilting operation in HeavyWater is given by
( P (I, s) (1 8 sign(f (x,
5 Numerical Experiments
Experimental Setting. We evaluate the
tradeoff of HeavyVater
and SimplexWater following the experimental benchmarking guidelines in Waterbench 43] and
MarkMy Words
44 We use two popular prompt-generatie datasets: Finance-QA [45] (covering
Q&A tasks) and LCC [46]
(covering coding tasks). We evaluate on three open-weight models:
Llama2-7B 47). Llama3-88 8B 48] and Mistral-7B [49]. Implementation details are provided in
Appendix C.4, and full results, including ablation studies, are presented Appendix [
Baseline Watermarks. We benchmark SimplexWater and HeavyWater against the Gumbel wa- termark [17. the trwerse-tranffomm watermark [13. the Correlated Channel watermark [16], and the SynthID watermark [II] with binary scores and K = 15 competition layers. We select these methods based on code availability ease of implementation. These watermarks are distortion-fres (i.e., they preserve the average next token distribution). To our knowledge, they also do not have an out-of-the-box method for trading off distortion with detection accuracy. We also consider the watermark [10]. which can be tuned for such tradc-offs.
Evaluation Metrics. We p-value the primary detection power metric (plotted as log p) because offers a thresholdd-nneependen measure of statistical power of a watermark. Moreover, p- values are the metric of choice in [1] 13 15
50 [1]. The p-value measures the probability of obtaining a given test statistic or a more extreme one under the unwatermarked (null) distribution. This provides a direct connection the false-alarm rate, avoids the need choose arbitrary detection thresholds, and is well-suited for comparing different watermarking schemes on equal footing. When the distribution of the test statistic is not available, Gaussian under the Central Limit Theorem. For methods like Gumbel [17], where the test statistic distribution known analytically, we use the exact form. At a generation length of T 300, we observe that the Gaussian approximation provided by the z-test is very accurate, ensuring that p-values remain reliable even when the exact distribution is unknown.
43
44
use z-test, which approximates the statistic as
Distortion is measured using the estimated cross entropy (CE) between the watermarked and unwatermarked distribution, defined as Σ" log Px (7a), where (æ.) watermarked tokens and Px is the LLM's distribution. This is proportional to relative perplexity a commonly used proxy for quality evaluation [21 22]. We also measure watermark size, proposed by [44] and defined as the number of tokens it takes to detect the watermark with a certain p-value. We provide results for task-specific metrics for generation quality in Appendix [D.5 including document summarization
(2]. document and long-form QA 53 54 and code completion 46 as curated by 43
"Since detection is evaluated via z-scores and p-values which standardize by mean and variance, the specific mean and variance of the selected distributions do not affect detection accuracy.
8

---

250
SimplexWater
HeavyWater
Improvement: (%)
200
150
Red-Green Correlated Channel
@
100
++
Inverse Transform
1.0
50
SimplexWWter (Ours)
No Watermark
HeavyWater (Ours)
0.5
0
0.4
0.5
0.6
0.7
0.8
0.9
1.0
Markov-1
Product, hm4
Sum, hm5
Cross Entropy [nats] (-)
(b) Watermark improvement over Red-Green [0] with
(a) Detection Distortion Tradeoff. Mistral-7B. Coding.
several hashing strategies, 8 = 2. Llama2- 7B, Coding.
Figure 3: Left: Tradeoff between detection (measured by p-value) and distortion (measured by Cross-Entropy)- SimplexWater and HeavyWater achieve higher detection rates while preserving token distributions close to the base unwatermarked model. Right: Detection gained by employing our watermark under various randomness generation schemes and several sliding window sizes h. Both SimplexWater and HeavyWater provide significant improvement of up 250% and decrease distortion.
Detection- Diitto--ittttiiinn Tradeoff. We compare the tradeoff between watermark detection (p-value) against distortion (cross entropy). The results are given in Figures | and 3a We make two key observations. First, considering watermarks with binary scores, Simple exWater Pareto dominates the red-green method. Second, HeavyWater provides the top performance along the baseline watermarks, incurring zero distortion. When we tune the watermarked distribution, both Simplexwater and HeavyWater obtain significant gains in detection, with mild distortion incurred.
Table Results HumanEval Functional Coding Dataset (pass @k, higher is better)
Watermark Scheme @ass@1 (%) t
pass @5 (%) 1
pass @ 10 (%)
No Watermark
14.0
20.7
28.1
Heavy (Ours)
13.1
18.9
27.8
Gumbel
14.3
20.5
25.6
SimplexWater (Ours)
13.7
22.7
25.3
Inverse Transform
13.8
22.0
27.5
Red/Green 5 3
11.6
19.5
23.2
Additional Quality Metrics for Textual Tasks. In addition to cross entropy, we have reported additional performance metrics for text quality: ROUGE-L and scores for four additional tasks in Appendix D.5 In Table D.3 assess the impact of watermarking
generation quality across four additional tasks from WaterBench [43]: LongformQA, Multi-news Summarization, Knowledge Memorization, and Knowledge Understanding. For these, we report ROUGE-L scores (LongformQA and Multi-news) and F1 scores (Knowledge Memorization and Knowledge Understanding). Our methods (Simplex Water and HeavyWater) Water) maintain competitive detection performance across all datasets, with a generation metric comparable to unwatermarked text (see Table Together, these results provide significant evidence that watermarks preserve output quality in textual tasks.
Additional Quality Metrics for Coding Tasks. We report additional tasks and metrics for low- entropy generation in coding. For LCC code completion tasks [46,, since used as the ground truth, Edit Similarity is the generation-qualin metric. We benchmark our watermarking methods against prior work using this metric, and HcavyWater achieves the highest Edit Similarity score for the code completion task (see Table D.4). For the HumanEval dataset 46). we take the standard metric pass@/ K with K=1,5,10 generation metric. As shown in Table [ Simplex Water achieves the highest score on pass @5 and Heavy Water performs best on pass @ 10. These results demonstrate that watermarks preserve both functional correctness and syntactic quality generated code.
codes are
Watermark Size. We consider y 10-3 which corresponds to 0.1% false-positive rate and report the average generation length to reach this p value. seen in Figure where Llama2-7B is run on Q&A dataset, both the SimplexWater and HeavyWater schemes provide the lowest watermark size

---

in terms of the number of tokens required to attain watermark detection strength, as measured by
the p-value.
300
Red-Green
Gain and Performance Under Hashing. We illustrate how SimplexWater and HeavyWater can be coupled with different side information generation methods boost watermark detection. We consider an experiment in which we replace the Red- Sed-Green watermark cost function and water- marked distribution with ours and report the gain in detection under several seed hashing methods adopted in [10]. As seen in Figure Bbj simply switching Red-Green (ő 2) with our methods -while keeping the same hashing scheme in- troduces significant detection gain (up to 250% improvement in the aggregated 1o value).
Correisted Channel
250
Inverse transform
Syntri
Gurbel
SimplexWeter (Ours)
HeavyWater (Ours)
Avg Tokens
100
0.3
0.6
0.7
Cross- Entss-y [nats]
(+)
Figure 4: Our watermarks require fewer tokens to reach a given detection strength (p-value) with zero distortion.
The following experimental results and ablation studies are included in Appendix D 1) An evaluation on the WaterBench dataset 43 in which we show that our methods do not degrade textual quality across an array of generation metrics (Appendix D.5 2) A robustness study in which evaluate tamper resistance of our watermarks (Appendix D.3). and 3) computational overhead measurements, where we compare generation wall-clock times of various watermarking schemes (Appendix D.4)
Additional Results.
6 Conclusion
We developed two new watermarking schemes by characterizing and analyzing an optimization problem that models watermark detection in low-entropy text generation. When restricting attention to binary scores, we draw connections to coding theory, which we then use to develop SimplexWaten We prove that Simplexiie exWaeer is minimax optimal within our framework. When we sample the scores i..d. at random, we show that watermark detection depends on the tail of the score distribution. This leads to HeavyVater, where the scores sampled from heavy-tailed distribution. We further show that the Gumbel watermark is a special case of this construction. Both S Simplexwater and HeavyWater demonstrate favorable performance when compared to various recent schemes. An interesting direction for future work is further optimizing the score function. This could be done by exploring other heavy-tailed score distributions, or using alternative strategies to optimize f(z, s) such as backpropagating through ([.. We also restrict our analysis to threshold tests more powerful statistical tests could improve detection accuracy (see (23)). Our work contributes to better authentication of text provenance and fostering trust in AI systems. Agnostic to how side information is generated, our watermarks can be paired with new research in side information generation strategies that are more robust to tampering and adversarial attacks.
array of LLM watermarking experiments
This paper was prepared for informational purposes by the Global Technology Applied Research center of JPMorgan Chase & Co. This paper a product of the Research Department of JPMorgan Chase & Co. or its affiliates. Neither JPMorgan Chase & Co. nor any of its affiliates makes any explicit or implied representation or warranty and none of them accept any liability in connection with this paper, including, without limitation, with respect to the completeness, accuracy, or reliability of the information contained herein and the potential legal, compliance, tax, or accounting effects thereof. This document is not intended as investment research or investment advice, or as a recommendation, offer, or solicitation for the purchase or sale of any security. financial instrument, financial product or service, or to be used in any way for evaluating the merits of participating in any transaction.
Disclaimer:
Acknowledgment. This material is based upon work supported by the National Science Foundation under Grant No FAI 2040880, CIF 2231707, and CIF 23126662 1312667, as well as JP Morgan Chase.
10

---

References
[1] National Conference
of State Legislatures.
Artificial intelligence 2024
legislation.
https: nesl org/ tttpt/eechoooaaaneeeeoet andd-andaaa communicationn
artificial- www.alliinntnlngnneeeeoo 2aweeaeennn------ellllt---------
2024. Accessed: 2025-05-14.
[2] Bram Rijsboseh, Gijs Dijck, and Konrad Kollnig. Adoption of watermarking for generative systems in practice and implications under the new eu ai act. arXiv preprini 3rXiv:2503.18/55 2025.
[3] Regulation (EU) 2024/1689 of the European Parliament and of the Council of June 2024
laying down harmonised rules on artificial intelligence (Artificial Intelligence Act). Official Journal of the European Union, L 1689, 13 June 2024, 2024. Accessed: 2025-05-14.
[4] The White House. Fact sheet: Biden-harris administration secures voluntary commitments from eight additional artificial intelligence companies to manage the risks posed by ai. https
//shottull.a//F117
September 2023. Accessed: 2025-05-14.
[5] Bilva Chandra, Jesse Dunietz, and Kathleen Roberts. Reducing risks posed by synthetic content: An overview of technical approaches to digital content transparency. Technical Report NIST.AL.100-4, National Institute of Standards and Technology, Gaithersburg, MD, 2024.
[6] RAND Corporation. The case for and against watermarking, lattps://ww.. rand. org/ ttthe-hecsssee for-ande and aand--gains--- al watermarking html
January 2024. Accessed: 2025-05-15.
[7] Tom Sander, Pierre Fernandez, Alain Durmus, Matthijs Douze, and Teddy Furon. Watermarking makes language models radioactive. arXiv preprint arXiv:2402. 14904, 2024.
[8] Michael-Andrei Panaitescu- Zora Che, Bang An, Yuancheng Xu, Pankayaraj Path- manathan, Souradip Chakraborty, Sicheng Zhu, Tom Goldstein, and Furong Huang. Can watermarking large language models prevent copyrighted text generation and hide training data? In Proceedings of the AAAI Conference on Artificial Intelligence, volume 39, pages 25002-25009, 2025.
[9] John Kirchenbauer, Jonas Geiping, Yuxin Wen, Manli Shu, Khalid Saifullah, Kezhi Kong, Kasun Fernando, Aniruddha Saha, Micah Goldblum, and Tom Goldstein. On the reliability of watermarks for large language models. In The Twelfth International Conference on Learning Representations, 2024.
[10] John Kirchenbauer, Jonas Geiping, Yuxin Wen, Manli Shu, Khalid Saifullah, Kezhi Kong, Kasun Fernando, Aniruddha Saha, Micah Goldblum, and Tom Goldstein. On the reliability of watermarks for large language models. arXiv preprint Xiv:22306.046344 2023.
[11] Sumanth Dathathri, Abigail See, Sumedh Ghaisas, Po-Sen Huang, Rob McAdam, Johannes Welbl, Vandana Bachani, Alex Kaskasoli, Robert Stanforth. Tatiana Matejovicova, et al. Scalable watermarking for identifying large language model outputs. Nature, 634(8035):818
2024.
[12] Xuandong Zhao, Prabhanjan Vijendra Ananth, Lei Li, and Yu-Xiang Wang. Provable robust watermarking for ai- di-generated text. In The Twelfth International Conference on Learning Representations, 2024.
[13] Rohith Kuditipudi, John Thickstun, Tatsunori Hashimoto, and Percy Liang. Robust distortion- free watermarks for language models. arXiv preprint vrxiv:2307.15590 2023.
[14] Ron Roth. Introduction coding theory. Cambridge University Press, 2006.
[15] John Kirchenbauer, Jonas Geiping, Yuxin Wen, Jonathan Katz, Ian Miers, and Tom Goldstein.
A watermark for large language models. In International Conference on Machine Learning. pages 17061-17084. PMLR, 2023.
[16] Dor Tsur, Carol Xuan Long, Claudio Mayrink Verdun, Hsiang Hsu, Haim Permuter, and Flavio P Calmon. Optimized couplings for watermarking large language models. arXiv preprint 2505::250500877. 2025.
[17] Scott Aaronson. Watermarking of large language models. https: //simons. berkeley
http//talksscoottaaae aaronson-ut--aa- maroonon--t--assiin--o openai 2023- 08- 17 August 2023. Accessed: 2025-01-1-.

---

[18] Renato Villán, Sviatoslav Voloshynovskiy, Oleksiy Koval, Vila, Emre Topak, Frédéric Deguil- laume. Yuri Rytsar, and Thierry Pun. Text data-hiding for digital and printed documents: Theoretical and practical considerations. In Security, Steganography, and Watermarking of Multimedia Contents VIII, volume 6072. pages 406-416. SPIE, 2006.
[19] Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. Advances in neural information processing systems, 26, 2013.
[20] Xuandong Zhao, Lei Li, and Yu-Xiang Wang. Permute-and-flip. An optimally stable and watermarkable decoder for llms. In Neurips Safe Generative AI Workshop 2024, 2024.
[21] Eva Giboulot and Teddy Furon. Watermax: breaking the Ilm watermark defeecaablityy-rouuuness- quality trade-off. arXiv preprint arXiv:2403.cm 008008 2024.
[22] Pierre Fernandez, Antoine Chaffin, Karim Tit, Vivien Chappelier, and Teddy Furon. Three bricks to consolidate watermarks for large language models. 2023 IEEE International Workshop on Information Forensics and Security (WIFS), pages 1-6. IEEE, 2023.
[23] Xiang Li, Feng Ruan, Huiyuan Wang. Qi Long, and Weijie J Su. Robust detection of watermarks for large language models under human edits. arXiv preprini 0rXiv:24/1.13866 2024.
[24] Jiayi Fu, Xuandong Zhao, Ruihan Yang, Yuansen Zhang, Jiangjie Chen, and Yanghua Xiao. Gumbelsoft: Diversified language model watermarking via the gumbelmax-trick. arXiv preprint arXiv:2402. 2948 2024.
[25] Haiyun He, Yepeng Liu, Ziqiao Wang, Yongyi Mao, and Yuheng Bu. Theoretically grounded framework for 11M watermarking: A distribution-adaative approach. In The 1st Workshop on GenAl Watermarking, 2025.
[26] Baihe Huang, Hanlin Zhu, Banghua Zhu, Kannan Ramchandran, Michael Jordan, Jason Lee, and Jiantao Jiao. Towards optimal statistical watermarking. arXiv preprint 212102231..07990, 2023.
[27] Minjia Mao, Dongjun Wei, Zeyu Chen, Xiao Fang, and Michael Chau. A watermark for low- entropy and unbiased generation in large language models. arXiv preprint arXiv:2405.14604, 2024.
[28] 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 I: Long Papers), pages 4067-4083 2024.
[29] Yapei Chang, Kalpesh Krishna, Amir Houmansadr, John Wieting, and Mohit lyyer. Postmark: robust blackbox watermark for large language models. arXiv preprint arXiv:2406. 14517, 2024.
[30] Yijian Lu, Aiwei Liu, Dianzhi Yu, Jingjing Li, and Irwin King. An entropy-based text water- marking detection method. arXiv preprint arXiv:2403. /3485, 2024.
[31] Kioo Yoo, Wonhyuk Ahn, and Nojun Kwak. Advancing beyond identification: Multi-bit watermark for large language models. arXiv preprint arXiv:2308..m 00221, 2023.
[32] Jie Ren, Han Xu, Yiding Liu, Yingqian Cui, Shuaiqiang Wang, Dawei Yin, and Jiliang Tang. robust bemantics-based watermark for large language model against paraphrasing. arXiv preprint arXiv:231 (tt.:2331.0872.... 2023.
[33] Xiang Li, Feng Ruan, Huiyuan Wang, Qi Long, and Weijie J Su. A statistical framework of watermarks for large language models: Pivot, detection efficiency and optimal rules. The Annals of Statistics, 53(1):322-355 2025.
[34] Jaiden Fairoze, Sanjam Garg, Somesh Jha, Saeed Mahloujifar, Mohammad Mahmoody, and Mingyuan Wang. dubticly-detectable watermarking for language models. IACR Communica- tions in Cryptology, (44), 2025.
[35] Cédric Villani et al. Optimal transport: old and new, volume 338. Springer, 2009.
[36] Gabriel Peyré, Marco Cuturi, al. Computational optimal transport: With applications to data science. Foundations and Trends@ in Machine Learning, 1(5-6))355-607, 2019.
[37] Yangxinyu Xie, Xiang Li, Tanwi Mallick, Weijie J Su, and Ruixun Zhang. Debiasing watermarks for large language models via maximal coupling, arXiv preprint arX1v:2411.11203, 2024.
12

---

[38] Jacobus Hendricus Van Lint. Introduction to coding theory, volume 86. Springer Science & Business Media, 1998.
[39] Morris Plotkin. Binary codes with specified minimum distance. IRE Transactions on Information Theory, 6(4):445-455) 1960.
[40] Irving Reed. class of multiple-error -eapppe--errr--rrcetingg codes and the decoding scheme. Transactions of the IRE Professional Group on Information Theory, 4(4):38 490 1954.
[41] David E Muller. Application of boolean algebra to switching circuit design and to error detection. Transactions of the IRE professional group on electronic computers, (3):6-12, 1954.
[42] Iris AM Huijben, Wouter Kool, Max B Paulus, and Ruud JG Van Sloun. A review of the gumbel- max trick and its extensions for discrete stochasticity in machine learning. IEEE transactions on pultern analysis and machine intelligence, 45(2): 1253-133311311 2022..
[43] 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 arXiv:2311.07138 2023.
[44] Julien Piet, Chawin Sitawarin, Vivian Fang, Norman Mu, and David Wagner. Mark my words: Analyzing and evaluating language model watermarks. arXiv preprini arXiv:2312.00273 2023.
[45] Macedo Maia, Siegfried Handschuh, André Freitas, Brian Davis, Ross McDermott, Manel Zarrouk, and Alexandra Balahur. Www' 18 open challenge: financial opinion mining and question answering. In Companion proceedings of the the web conference 2018, pages 1941- 1942, 2018
[46] Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde De Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, et al. Evaluating large language models trained on code. arXiv preprint arXiv:2107.03374 2021.
[47] Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. Llama 2: Open foundation and fine-tuned chat models. arXiv preprint arXh::2307.09280 092888, 2023.
[48] Aaron Grattafiori, Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Alex Vaughan, et al. The llama
3 herd of models. arXiv preprint arXiv:2407.21783 2024.
[49] Albert Q. Jiang, Alexandre Sablayrolles, Arthur Mensch, Chris Bamford, Devendra Singh Chaplot, Diego de Las Casas, Florian Bressand, Gianna Lengyel, Guillaume Lample, Lucile Saulnier, Lélio Renard Lavaud, Marie-Anne Lachaux, Pierre Stock, Teven Le Scao, Thibaut Lavril, Thomas Wang, Timothée Lacroix, and William El Sayed. Mistral 7b. arXiv preprint arXiv:2310.0682. 2023.
[50] Baizhou Huang and Xiaojun Wan. Waterpool: A watermark mitigating trade-offs among imperceptibiliity efficacy and robustness. arXiv preprint arXiv:2405. 13517, 2024.
[51] Dara Bahri, John Wieting, Dana Alon, and Donald Metzler, watermark for black-box language models. arXiv preprint arXi::24/0.02099, 2024.
[52] Alexander R Fabbri, Irene Li, Tianwei She, Suyi Li, and Dragomir R Radev. Multi-news: A large-scale multi-document summarization dataset and abstractive hierarchical model. arXiv preprint /906.01 2019.
[53] Ming Zhong, Da Yin, Tao Yu, Ahmad Zaidi, Mutethia Mutuma, Rahul Jha, Ahmed Hassan Awadallah, Asli Celikyilmaz, Yang Liu, Xipeng Qiu, et al. Qmsum: A new benchmark for query-based multi-domain meeting summarization. arXiv preprint arXiv:2104.05933 2021.
[54] Angela Fan, Yacine Jernite, Ethan Perez, David Grangier, Jason Weston, and Michael Auli. Eli5: Long form question answering. arXiv preprint arXiv: 099. 2019.
[55] Bram Wouters. Optimizing watermarks for large language models.
arXiv preprint
arXiv:2312.17299 172955 2023.
[56] Yepeng Liu and Yuheng Bu. Adaptive text watermark for large language models. arXiv preprint arXiv:2401.1399 2024.
[57] 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.
13

---

[58] Miranda Christ, Sam Gunn, and Or Zamir. Undetectable watermarks for language models. In The Thirty Seventh Annual Conference Learning Theory, pages 1125-1139. PMLR, 2024.
[59] Patrick Chao, Edgar Dobriban, and Hamed Hassani. Watermarking language models with correcting codes. arXiv preprini arXiv:2406. 10281, 2024.
[60] Debdeep Mukhopadhyay and Rajat Subhra Chakraborty. Hardware security: design, threats, and safeguards. CRC Press, 2014.
[61] R Tyrrell Rockafellar and Roger J-B Wets. Variational analysis, volume 317. Springer Science Business Media, 2009.
[62] Gabriella Salinetti and Roger JB Wets. On the relations between types of convergence for convex functions. Journal of Mathematical Analysis and applications, 60(1):21 1-226, 1977.
[63] Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timo- thée Lacroix, Baptiste Rozière, Naman Goyal, Yuxiang Fu, Junjie Gu, al. The llama 3 herd of models. arXiv preprint arXiv:2407.21783. 2024.
[64] Richard Sinkhorn. Diagonal equivalence to matrices with prescribed row and column sums. The American Mathematical Monthly, 74(4))402-405, 1967.
[65] Rémi Flamary, Nicolas Courty, Alexandre Gramfort, Mokhtar Z Alaya, Aurélie Boisbunon, Stanislas Chambon, Lactitia Chapel, Adrien Corenflos, Kilian Fatras, Nemo Fournier, al. Pot: Python optimal transport. Journal of Machine Learning Research, 22(78):1-8, 2021.
[66] Jifan Yu, Xiaozhi Wang, Shangqing Tu, Shulin Cao, Daniel Zhang-Li. Xin Lv, Hao Peng, Zijun Yao, Xiaohan Zhang, Hanming Li, et al. Kola: Carefully benchmarking world knowledge of large language models. arXiv preprint arXiv:2306.099 092966 2023.
[67] Hao Peng. Xiaozhi Wang, Shengding Hu, Hailong Jin, Lei Hou, Juanzi Li, Zhiyuan Liu, and Qun Liu. Copen: Probing conceptual knowledge in pre-trained language models. arXiv preprint arXiv:2211.04077 2022.
14

---

NeurIPS Paper Checklist
1. 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 explicitly present the optimization framework and the two watermarking schemes (HeavyWater and SimplexWater) together with their theoretical properties and empirical evaluation.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made 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
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Section 2 presents a passage in which we discuss the limitations of the proposed setting.
Justification:
Guidelines:
The answer NA means that the paper has 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 "I "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 on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect 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 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-text 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 the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
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 '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 prool's
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
15

---

Answer: [Yes]
Justification: Both watermarks operate under specific assumptions on the token distribution and score function. Those assumption appear in Sections and 4 for SimplexWater and HeavyWater. respectively.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proof' can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proof's provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Question:
Answer: [Yes]
The appendix provides full implementation details on the considered experi- ments, benchmarks and parameter choice. Furthermore, we provide the code which can be used to recreate the results we report.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is 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 via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to 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 (c.g., to registered users), but it should be possible for other researchers to have some path to reproducing verifying the results.
16

---

5. Open access to data and code
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?
Question:
Answer: [Yes]
Justification: All the data used in the paper's experiments, is released alongside the paper's code.
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/
mublic//gudees/Cddettbmisss oow.aammmiiiiooooooooooooooe for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for 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 for more details.
//nips //iiss.c//ppl http://cccpbblccgguiieeeeeecp guides http:///wwllllliieeeeoooeueaaaaa
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible 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: [NA]
Justification: This paper does not involve the training of any parametric model. Hyperpa- rameters of the proposed methods mentioned in the implementation details appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a 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
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer:
[Yes]
Justification:
We report statistical significance our results using error bars.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
17

---

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, or 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 or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπτог 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 text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: The experiments section in the main paper provides information on the type of GPUU used run our experiments (Namely, single A-100 GPU).
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: The work promotes text provenance and misuse mitigation and raises confficts with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require 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 in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
We discuss the societal impact of our method in the Conclusion section.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
18

---

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.
The conference expects that many papers will be foundational research and not tied to 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 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 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 intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to 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 models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper does not release any models or data that can be misused. We propose new watermaring algorithms and analyze their performance.
Guidelines:
The answer NA means that the paper poses no 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.
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: We cite all external methods, models and datasets we are discussing and using in this paper.
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 is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
19

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
If assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi thcode. com/ com/dataseta has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if has changed) should be provided. If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: We provide code implementation of the proposed algorithms and methods. Those provided in the Supplement material in anonymized version and will be made public upon acceptance.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/codeemmodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing 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:
This research does not involve human participants.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing 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 much detail as possible should be included in the main paper.
According to the NeurlPS 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 or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper did not involve any human participants.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
20

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the 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
Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: We propose new LLM watermarking algorithms, but do not rely on any external LLM usage in our core method development.
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 our LLM policy (https://neur)) (btr::///eerrrpp.cc///oooffrrrrr / for what should or should not be described.
21

---

Supplementary material for HeavyWater and SimplexWater: Watermarking Low-Entropy Text Distributions
Table of contents:
Additional Information on Related Works.
A.
Additional Information on Related Work.
A.2 2
Instantiation of Existing Watermarks as Score, Distribution and Randomness
Design.
Discussion on Randomness Efficiency.
Proofs for Theorems from Sections
B.1
Proof of Proposition
2
Proof of Theorem 1.
Proof of Theorem 2.
B
Proof of Theorem 3.
B.5
Proof of Theorem 4.
C
Additional Information and Implementation Details for HeavyWater and
Simple SimptexWater.
Low-Entropy Distributions in LLMs.
2
Theoretical Effect of Different Tails of Distributions.
Q-ary Codes.
Implementation Details.
Information on Optimal Transport and Sinkhorn's 's Algorithm.
Additional Numerical Results and Ablation Study,
D.1
Ablation Study.
D.2
Impact of Non-i.id. Side Information Generation.
D.3
Experiment: Robustness to Textual Attacks.
D.4
Computational Overhead.
D.5
Experiment: Alternative Text Generation Metrics.
D.6
Alternative Detection Metric.
Additional Detection-Distortion Trade-off Results.
22

---

A Additional Information on Related Works
A.1 Additional Information on Related Work
Optimization Framework
Several optimization frameworks have been proposed for watermark
analysis. [66 25 26 33] adopts hypothesis-testing framework for analyzing the statistical power of
watermarking schemes. [33 goes beyond the vanilla threshold test to determine the optimal detection rule by solving a minimax optimization program. The authors of [25] consider an optimization under an additional constraint of controlled false-positive error. The watermarking scheme follows by learning a coupling that spreads the LLM distribution into an auxiliary sequence of variables (with alphabet size greater than m). While the proposed scheme is the optimal solution for the considered optimization, the scheme requires access to the (proxy of) L.LM logits on both generation maximization of the green list bias while minimizing the log-perplexity. Building on the hypothesis testing framework, optimize over classes of score functions, by observing that the detection power of a watermark boils down to the separation of expected scores between the null and alternative hypotheses.
and detection ends. The authors of (55) consider multi-objective optimization
Hashing Schemes in LLM Watermarking Current LLM watermarking schemes derive their per- token pseudorandom seed through five recurring hashing patterns. LeftHash hashes the immediately preceding token and feeds the digest to a keyed Psaudorandom function (PRF), yielding a weight, seff-synchronising seed that survives single-token edits [15]. Window-hash generalises this by hashing the last h tokens, expanding the key-space and hindering brute-force list enumeration at the cost of higher edit sensitivity 7 [S]. SelfHash (sometimes dubbed right-hand hashing") appends the candidate token to the left context before hashing, so the seed depends on both history and the token being scored; this hardens the scheme against key-extraction attacks and is used in multi bit systems such as MPAC B1. Orthogonally, counter-base keystreams drop context altogether and set the seed to PRF (K, position), strategy adopted by anverse-transfore and Gumbel watermarks to preserve the original LM distribution in expectation I7]. Finally, adaptive sliding-window window the last H tokens together with the secret key and skips watermarking whenever that exact window has appeared before (K-sequence repeated context masking"), thereby avoiding repetition artefacts while retaining the robustness benefits of short window [.]. Semantic extensions build on these primitives: SemaMark quantises sentence embeddings
popuaaie- by SeathiD-Teet-haan
3 while Semantic-Invarial Watermarking uses a learned contextual encoder (56). Collectively, these hashing families balance secrecy, robustness to editing or paraphrasing, and computational overhead, offering a rich design space for practical watermark deployments. Both SimplexWate and HeavyWater are agnostic to and can be applied on top of any hashing scheme. We provide the detection gain over Red-Green using various hashing schemes in Fig. 3b
Additional Distortion-Fres Watermarks An array of recent works propose distortion-free water- marks that preserve the original LLM distribution [13 16
17 20, 51 57/59. In addition to the ones that we have introduced in Section T [58] constructs undetectable watermarks using one-way func- technique. [59] proposes a watermark using coroeccogg
tions, which is a teeptorraphyinsspiin codes that leverages double-symmetric binary channels to obtain the watermarked distribution. [51) designs a distortion-free watermark based on multiple draws from a black-bor box LLM, which involves fixing score function, drawing multiple tokens in each step, and outputting the highest-score token.
A.2 Instantiation of Existing Watermarks As Score, Distribution and Randomness Design
Existing watermarks can be represented under the proposed outlook of side information, score function and watermarked distribution from Section 2 several popular schemes through our lenses.
We next demonstrate that by instantiating
The Red-Green watermark [15] randomly partitions X into green list and red list. Here, S is set of m binary random variables, representing the random list assignment. The function o has binary outputs, which are used to increase the probability of green list tokens though exponential tilting of Px-
The SynthID watermark II
employs tournament sampling: a tournament between a set of Nm token candidates along m-laaeer with N competing token groups. Fach tournament is performed given sample of shared randomness (denoted r [U). On the 4th layer the winners are taken to
23

---

Watermark
# Bits
Red-Green [15
m mF
Inverse Transform
Gumbel [7
mF log(m)
SimplexWater (ours)
HeavyWater (ours)
log(k)
Table A.2: Amount of random bits generated per step in popular watermarks. m is the vocabulary size. F is the floating point precision and & is the side information alphabet size.
be the token with highest score fe(z, s) within each N -isized set. The value of the score function is obtained from the side information for each token candidate. Different domains of f induce different construction of the function (See [I]] Appendix E] for more information). The watermarked distribution Pxis== is the obtained with closed form in specific cases of (f,N, .N, m)) and can be directly used instead of the instantiating tournament. This form of watermarking is termed vectorized tournament sampling, in which the tournament is not applied, but the induced conditional distribution is employed instead. In this paper we consider vectorized tournament sampling with binary-valuce scores, this is the formulation given in [II] with closed form, and the one that was utilized in their proposed experiments.
In the Gumbel watermark [17). the side information consists of m i.i.d., uniform random variables on [0. 1]. each one corresponding to a single element in the vocabulary x E X. The score function is obtained by assigning each E X' with value 42 -- - log(uz), where ug the uniform the probability of a E under the unwatermarked model. The watermarked distribution is then given by assigning probability 1 to argmocreexls and probability 0 to the rest of x E X (i.c., singleton distribution).
variable corresponding to x and Px Px(x)
In the Correlated Channel watermark [16], the side information corresponds to partition of X' into 2 lists and a single shared uniform variables S' that is uniformly distributed on [1 k... The score function is then an indicator of the matching between the additional variable realization and the token random assignment, i.e., (z, s) 1 (x(()) = s), where (xx) E : k)] is the assignment of into one of the & lists. The watermarked distribution is then given in closed form by solving the maximum coupling problem.
A.3 Discussion on Randomness Efficiency
Given a hashing procedure that determines the random number generator seed value, we sample the side information S ~ Ps over S. The size of S determines the amount of side information we are required to sample. As described in Appendix A.2, each watermarks corresponds to a different size fo S. We interpret that as randonness efficiency. That is, the bigger S is, the more bits of randomness we are required to extract from the random seed. We argue that a byproduct of our method is randomness efficiency, i.c., SimplexWater and HeavyWater require less random bits to sampled from the random seed compared to existing schemes. To that end, we compare with several popular watermarks (see Table A.2 for summary).
The Red-Green watermark [15] corresponds to sampling single bit for each element in X, whose value determines the token's list assignment (red or green), thus resulting in total of m bits. The inverse transform watermark [ requires sampling a single uniform and sampling a random permutation of [1 m). Thus, it asymptotically requires F log(m!) bits, where F is the resolution of the floating point representation used to sample the sampled uniform variable in bits (c.g. 32 for float32). For the Gumbel watermark, we sample uniform variable for each x E X. resulting in total of mF bits.
In SimplexWater, the side information size is S = m 1. To that end, we required log(m) bits to sample single s [1 m - 1). Furthermore, HeavyWater is not constrained to a specific size of [S] = k, and in the proposed experiments we take & = 1024 which is significantly smaller than both m and 2F The resulting amount bits to be sampled from the random seed is log(1024) = 10 bits. Consequently, we observe that HeavyWater is the most randomness-effiieen watermark across considered schemes, while also being the best-performing watermark across considered experiments (see Section 5).
24

---

Minimizing the number of random bits extracted from a random number generator directly reduces computational and energy overhead in watermark embedding less information to be stored on the GPU. This eases implementation in ssbource-constrinnee hardware by lowering entropy demands and memory usage. Additionally, limits side-channel leakage by shrinking an adversary's observable output [60), which may lead to more secure watermarking. We leave an extensive study and quantification of the benefits of randomness efficiency to future work.
B Proofs for Theorems from Section and 4
We prove Proposition 1 Theorem
Theorem Theorem
3 and Theorem 4
B.1 Proof of Proposition
In this section, prove Proposition I which connects the watermark design problem a coding theoretic problem when the score function class is chosen to be binary.
Proposition 1 (restated): Let À E [1 1)- for each i E X. Then,
For S E Fbin. define the vector fa
[f(i,)) ..... E 13
(1-))d((fr.J))
Dga k X, Fbin) = max feFunn
min iJEXitj
(B.9)
k
where du b) (aphbb)) denotes the Hamming distance between a, b E {0, 17ah and ( is the indicator function.
Proof of Prop. Recall that we consider Ps ~ U(1 k). For any Px. let ((Px) =
maxpxs PExxs [f(X, 5)] EpxPs ())).
Claim 1. argminpep, (PP) E Pspike, where
P Pppike,> E Am (Px(11); Px(x2),..... Px (x(m) (2,1
(B.
Here (x(x;) denotes the rith element of the Px probability vector with (#1...., Fm) representing any permutation of (m). Am is the m-dimenssonal probability simplex.
Proof of Claim [ To prove Claim 1 we first show that (Px) concave in Px. By definition, for any given Px and uniform Ps, we have,
(Px)) max ([X)) Erx (xx,s
Pxs
Define Ps as the optimal joint distribution that achieves the maximum for given Px. Then, we have:
(Px)) = -Ep;, [f( - Px [f(X
Now, consider the mixture Pt = =0P + (1 p) for some = [0, 1] and p(),p( e Am. Given Fx and p(2)= the maximizing couplings of (P())) and ((((2)) respectively, we define mixed joint distribution: P&- = OP + +1 (1- 2 Note that,
Σ Ph: Σ
p(1) XS
(1 0) Σ p 2)
(B.11)
-0P(1) + (1 - ())
(as p(0+ is the optimal coupling of p(() and Ps.
(B.12)
(B.13)
Σ
p8
Σ
p())
+(1 (1- 0) Σ () XS
(B.14)
0
(1 8) p)
(as is the optimal coupling of Px and Ps.
()
p())
(B.15)
k
1
(B.16)
k
25

---

which shows that Px's is valid coupling of PX and uniform Ps. Using the linearity of the expectation operation, the expectation under the mixed distribution PXs is:
Bpgs [S(
p [/(X, S)] + (1 - Xx p00 (((,,))
Similarly, for the independent case: Bpg rs S [fX( 0 2 Pg +1 (1 (f(X pg
Since (P ) by definition takes the maximum coupling among all Pxs, it upper bounds the value attained by the specific mixture P Thus,
V (P&) 2 Epg, [J) (r
A --- [f(X, S)) + (1 - 0) xs
p S) AE xxx pg S))
-1 01E p30 P S))
=O + (P))
which proves concavity.
We now show that for any x E []. the minimizer of (Px) lies in the set Pspike.A. A.hee
Pspike,2 = {P E Am (P1( Px(x2)) Px Px = {A, ,,0
(B.17)
Recall that Pa = (P E |P|| S A}- This is a convex set and the extreme points of this set are precisely the spike distributions Pspike, which correspond to permutations of (A, X, ........ 0). Since (Px) is concave, its minimum over the convex set Pa occurs at an extreme point of Pa Hence, the minimizer (Px) belongs to Pspike, which completes the proof.
Using Claim M we prove Proposition I as follows. Let p* E P P be the minimizer in the minimization of (m, k, Fbin) in U. and let (i,j) be its non-zero entries, i.e., P À and Pj = A. Under such p² and uniform Ps, any coupling can be written
XQx s(s lt)
if I
Px)(x,s) (1 x[xsssss(s
if =
i i,j
where Q5ix = Pxs/Px denotes the conditional distribution of the shared randomness S given the selected token X. The coupling constraint for each becomes
XQsix (s 1) + (1 - A)Qsix(s = k²
To that end, we represent such coupling as
Xa, 1-
xs ass Qsix(s
for some set of parameters (a.)sEs. such that a, E [0, t.l. Under this construction, considering the worst case (i pair of non-zero Px indices, we have,
Dgap (m, k X, Foin)
max [=,,5=((U1]
min max og Qxis
(Qsx(((i)((.)) - x)(s)x(s)))(...))
1 11 (2 Io xx,0ss)
(B.18)
k Σ
1/2 (#=)))
max [=AXS=[[U1]] Hg E.E
min max
(11)))
1- 1 f(i.s)
==1
N (2) to 5(3
1- 1->
(B.19)
1
max min max
Σ >
- k
(((,s)-f(i..
(B.20)
fxXxS=(001] 34 a.E all am
26

---

The design of the coupling Pxs boils down to choosing {ashess such that (B.20) is maximized. Moreover, since Σ Qsxx (5|=) for and j. have,
Σ (six(s =1
Σ ag =1
(B.21)
For given f and any two indices (i, we characterize optimal a, as follows. Let m = # (s f(i, s) - f(iss = 1} and m = #(s: f(i, s) f(iss) = - where # denotes the cardinality of set. Assume that the score functions f satísfy m'd < kλ and m m i5 < k. These assumptions are needed to eliminate trivial edge cases for which the inner minimization in [B 20 is zero, which leads to zero detection (see Appendix B.I.Ip The inner-most maximum in B.20) is obtained when:
8: f(i,s f(j.s)
XX
ag
0,
s: s:f(i,s) -fj.s) -1
(B.22)
8: [(i -(i.8) =0
k-m
The optimal values of a, are obtained by allocating the maximum probability mass to the highest scores f(i, 8) 8) in (.20 Continuing from B.20), we have,
Dgap (m, k X, Fbin)
= max 1:X08-(0011
min
Σ 8:fi -ff-f/=-1
sf(i,s) f(i,s)
(0.1) 171
K
Σ (1 -(((,))
(B.23)
1=11
max min- (Am + +(1 - 2)m14)
(B.24)
fxX x (0,1)
Let d,y = [[ sii + f(. Then, m 1f + = dij. Let m = Bdis and mf =
B)d.
for some 10. From (.24)). have,
Dgap (m, k, A, Foin)
max min min
_ (AB + (1 (1-A)(1 3))d4s
1
(B.25)
fxx xxxx- 0.11 i73 pE(o.1)
max min min (3(22 - 1) + (1 - A))di,
(B.26)
f=XxS-(0.1] if SE(0.1] 1:
max min di (1 A)
(B.27)
fxXX5- 0.11 iFj k
since the inner minimum is achieved when B = 0. as À 2 2. The proof is complete as d,j is exactly the Hamming distance between f(i,-) and f(j.) -).
B.1.1 Edge Cases
In Appendix B.1 assumed that the score functions f satisfy m.d < RY and m.d + mid < k. In this section, we show what happens when these constraints are violated.
Case 1: m² kA: In this case, we obtain the optimal values of as as in the proof of Proposition I above, by assigning the probability masses to the high score cases as follows. Let J C m [J] = kA be any subset of kλ values of 8, each satisfying [(i, 8) - f(j,s) = In this case, similar to case 1, the inner maximum in B.20) is obtained when:
8 SEJ
0g
EX
(B.28)
0,
3 J
27

---

Continuing from B. ).20), we have,
1(m - k2)
Am
D gap (m, A, Fbin)
min X(1 2) f.xx8=+(0.1 i5j
+
(B.29)
k
A (m -m44
min + f.XxS-(00) (0.1) HF k
max
(B.30)
max min min 1:xx68-(0.11 BE[U,1]
+ = (23 - 1)des
(B.31)
k
max min À dij [xXxS=+(01]] Hij
(B.32)
k
= =0
(B.33)
where the last equality follows from the fact that the inner minimum achieved when di k, i.e. f(i,-) is the all zeros vector and f(i.-) is the all ones vector. The score functions f that result in such cases are uninteresting the detection can not be improved.
Case 2: m 4. < kλ and m + m k: In this case, obtain the optimal values of ag in Appendix B. by assigning the probability masses to the high score cases as follows. Note that in this case (1,8) f(i,8) 8) 0 0. Therefore,
8: f(i, s(j, 8) =1
RX
(B.34)
Fx m
8: f(i,8) 1(j88 = =-1
As 8-mm"
Continuing from B.24 have,
(1 Aam!
1 xx =tm²
Dgap (m, k. A, Foin) = max
min 181
(k: (k- m
(B.35)
x:x08 0.1]
k
k
ind
2m ij
max
min
(1 - A)
(B.36)
x 0.1] 173
k
(B.37)
where the last equality follows from the fact that the inner minimum is achieved when m = 0, i.c. -i,,-) is the all zeros vector and f(j.-) is the all ones vector. The score functions f that result in such cases are uninteresting as the detection can not be improved.
B.2 Proof of Theorem
In this section, we derive an upper bound for the detection gap in ( using the Plotkin bound from coding theory [14).
Theorem (restated): Consider the class of binary score functions Foin and uniform Ps. Then, for any E [, 1), the maximum detection gap can be bounded as
m(1 A) Deap (m, (m,, k. X, Foin) I
(B.38)
2(m 1)
Proof of Thm. [7] Thm. follows directly from the Plotkin bound [14. which provides an upper bound on the minimum normalized Hamming distance between any two codewords, considering any code construction. Indeed,
(1 - A) (fr. 5(1 A) 2(m 1)
m
Dgap (gap(m, (m, K. X, Fbin)
max FeFi
min i.EX.37
(B.39)
k
28

---

B.3 Proof of Theorem 2
In this section, we show that SimplexWater achieves the upper bound in (B.39).
Theorem (restated): For any E Simplexwated
[ 1) the maximum detection gap upper bound attained by
Proof. SimplexWater uses the Simplex code construction in Definition ass the score function. The simplex code achieves the Plotkin bound [14), i.e.,
du (Jsim (8, }), Saim (i.
Y71
min ド
(B.40)
2(m 1)
Therefore,
D Dgap k. X, Fbin)
min (J
(1 (Jam( (t, " Jaim (i.
2) 2(m 1)
m
(B.41)
k
Considering the upper and lower bounds
B.39 and BB.4 we have,
D Dgap( (m,, k X, Fuin) (1 X)
(B.42)
2(m - 1)²
which is achieved by SimplexWater.
B.4 Proof of Theorem 3
In this section, we establish that the Gumbel watermark scheme [17 can be understood within our optimal transport framework, i... we prove Theorem restated below.
Theorem 5 (Gumbel Watermark OT). When the score random variables [1x 8), are sampled i.i.d. from Cumbel(O, 1), the solution to the OT problem in ② converges to the Gumbel watermark (17) as (S]
Do.
To prove this, we first write down the Kantorovich dual of our optimal transport formulation and identify the dual potentials {az, 8.] that generate the arg -ag coupling. We then analyze the behavior of these potentials in the limit & - oo, showing that the resulting arg-max rule converges to the classical Gumbel-Mas sampling procedure. final concentration argument ensures that the random coupling concentrates around its expectation, thereby establishing that the OT-derived sampler coincides with the Gumbel watermarking scheme.
To understand this connection, we first review the Gumbel watermarking scheme. The Gumbel-Max trick states that sampling from a softmax distribution can be equivalently expressed as:
(e(
= arg max yEV T
G(())
(B.43)
where uy) are the logits, the temperature parameter, and Ge(y) ~ Gumbel 1) independently for each token position and vocabulary element y. A Gumbel(O, 1) random variable can be generated via:
Gely) - log( log(r+(y)))
(B.44)
where (v( ~ Uniform((0, 1]).
In the Gumbel watermarking scheme, the uniform random variables replaced with pseudo-random values:
re( Uniform((0, 11) (in unwatermarked model)
(B.45)
Te (v( = Fr (g) (in watermarked model)
(B.46)
Here, Fy.-mr-n..e l (t) uses secret key k and previously generated tokens Vt-m:t-1 to deterministi- cally generate values that appear random without knowledge of k.
To establish the connection to our OT framework (2) in the case when randomness is i.i.d. generated, we analyze the dual formulation of the optimal transport problem. this formulation, we seek to minimize Σ, (x + 1 E. 3, subject to a₂ + Ba 2 f(x, s). The optimal values for these dual
29

---

variables satisfy specific conditions that link to the Gumbel-Max construction. The key insight comes from the optimality condition our framework:
(i = max -aā =
(B.47)
This can be directly mapped to the Gumbel-Max trick by identifying that f(i,)) corresponds the Gumbel noise Gv(y) and o corresponds to - T
"x(x) (the negative normalized logits). With these
identifications, the Gumbel-Max sampling expression:
Ue (V)
+ G.(v) = arg maaa((G. - -( ux(y)) T
= arg max yEV
(B.48)
T
NEV
Takes exactly the same form our framework's 's expression arg max, maxx]2{(j,) az}- Further, the probability that this argmax equals is precisely (i in our framework. Therefore, when f(j, 8) ~ (0, 1), we will show below that our optimal transport solution exactly recovers the Gumbel watermarking scheme.
The detailed proof proceeds by analyzing the convergence of the discretized dual problem to its continuous limit as k + oc. The optimality conditions in the limit confirm that our OT framework generalizes the Gumbel watermark as special case when scores are drawn from the Gumbel distribution. We start by defining general optimal transport problem and its Kantorovich duality.
Definition 2 (Optimal Transport Problem). Given probability measures μ and v on spaces X and Y respectively, and cost function X x y - R. the optimal transport problem seeks to find coupling x (a joint distribution with marginals μ and v) that minimizes the expected cost:
{ c(z, y) dr(x,
inf *Ell(N)) xxy
(B.49)
where 11(2, v) is the set of all probability measures on X x y with marginals and v.
The Kantorovich duality is fundamental result that provides equivalent formulation of this problem. For more details, see [35 Chapter 5].
Theorem (Kantorovich Duality). The optimal transport problem equivalent to:
{ x(x) du(a)) v(x)du(a))
/ (b(y) (b) du(u)
sup (9.0)E
(B.50)
where &. ((),))) p(x)) + (vv) s c(z,y)} is the set of functions satisfying the c-inequality constraint.
This duality relationship (i.) transforms a non- non-trivial constrained optimization problem over probabil- ity measures into an optimization over functions, (ii.) provides way to certify optimality through complementary slackness conditions and (iii.) enables us to analyze the convergence properties of OT problems through the convergence of dual objective functions. In many applications, the Kantorovich duality rewritten with the constraint reversed (potential functions sum to 2 c), transforming the problem into minimization rather than maximization. We adopt this convention in our formulation below.
Primal Formulation. Let us consider an optimal transport problem described by the inner maximiza- tion of (T). that is, given by Equation (2). Recall that given pair (Px, f), the inner maximization in (T) amounts to an OT problem between Px and Ps, which is set to follow an uniform distribution on [I : k). There, the score function of can be equivalently denoted as the (m x -idiennsioaa OT cost matrix C, which is defined as Ca',s' = - ff', s') for (a', s') E [1 m) x [1 k). This matrix is only generated once.
Now, let Px be a probability distribution over a finite set {,,2,.. m) and Ps be a uniform distribution with mass 1/k at each point in 21, k3. We have cost function f(r, s) with zero mean and unit variance, i.e., Ep[z] = 0 and Ep[="] = 1. The inner optimization in ( aims to find a coupling Pxs that maximizes:
CP
max Σ Pxs(a, f(x,
(B.51)
Pxs
2,3
30

---

s.t.
Px 8) = Px(x) Wx
(B.52)
Σ Pxs(2,8) 8) k
ss
(B.53)
Pxs(x, 8) 20 Vx,
(B.54)
Dual Formulation. order analyze this primal optimal transport problem we can look the dual by using a Kantorovich duality argument. The equivalent dual problem is given by:
CD
min au
Px(xx)a +
E S
(B.55)
Subject to: az + + fI, Vx,
(B.56)
In this dual formulation, a₂ and Bg the Kantorovich potentials (i.e., Lagrange multipliers) enforcing the marginal constraints Σ. (x)( = Px (x) and Σ. Pxs(2, = respectively. For any fixed values of Ouz, need to determine the optimal values of 8, that minimize the dual objective function. Since we aim to minimize the objective and the coefficients of 3, are positive & > 0), want make each 8g as small as possible while still satisfying the constraints. For given the constraint becomes:
B. z f(x,8) az
Vx
(B.57)
This means that B. must be at least as large [(r - az for every value of x. To ensure all constraints are satisfied while keeping 3, minimal, we set:
B₂ = max[f(x', aar)
(B.58)
This is the smallest value of Bg that satisfies all constraints for given Any smaller value would violate at least one constraint, and any larger value would unnecessarily increase the objective function. Substituting this expression back into the dual objective yields:
h C min Σ Px(x)a k
maxif(r',s) -arl
(B.59)
This reformulation reduces the dual problem to unconstrained minimization over 0₂ only.
To establish convergence of the dual problem, which the key embedding the Gumbel water- marking scheme in our framework, we will first recall few fundamental concepts from variational analysis and convex optimization.
Definition 3 (Epi-convergence).. A sequence of functions fx R + R U {+oo} is said to epi- converge to a function f E. - [=o)] if the following two conditions hold:
(i) For every x E Rd and every sequence In + x, lim infa Ju (xx) 2 fxx).
(ii) For every x. E R", there exists a sequence Iy + I. such that lim supk-tcc J& fx())) S f()).
Epi-convergence is particularly important in optimization because it guarantees that minimizers and minimal values converge appropriately, For more details on epi-convergence, see [61]
Definition 4 (Equi-lower semicontinuity). A family of functions {fk } is equi-lower semicontinuous for every x E R.n and every e > 0, there exists a neighborhood V of ic such that inf gEV fx(()) fx(x) -
(B.60)
for all k.
The following result connects pointwise convergence with epi-convergence for convex functions: Theorem 2 (162) Theorem 2)). If [[x} is sequence of convex, continuous, and equi-lower semi- continuous functions that converge pointwise to a function on R., then {fx] epi-converges to f.
31

---

As a first step toward applying our framework to the Gumbel watermarking scheme, we now characterize how the optimal transport cost behaves in the limit + oo.
Theorem 3. As l + oo, the optimal value of the discrete problem converges the expected value problem:
h - CD
min p' x f
(B.61)
#ER
where Py Px) and f(j. s) are random variables with the distribution matching the problem's cost function.
Proof of Theorem
Let rewrite the objective function in vector notation:
(x(x) = p" Σ
max - s.)
(B.62)
where žj ji.jj... Zm and ži == sz) denote the sampled scores, i.e., each column žj corresponds to the vector of scores across tokens for fixed side-information sample 8j. and ........ am
We need to establish that the functions f& are continuous and convex. Note that
1. The term p² is linear and therefore continuous and convex.
2. The function (x))) max, [[ 8) -rj] is continuous for each because:
(a) The functions hx(x) f(jss Ij continuous for each
(b) The maximum of finite number of continuous functions is continuous. It is also convex as the maximum of linear functions.
3. The sum & Σ
-= Is (x) is continuous as linear combination of continuous functions and convex as positive linear combination of convex functions.
As h + co, by the Law of Large Numbers, for any fixed x, the sample average converges to the expected value:
max ff. 2,1 + E[max( f(. 2,)1
(B.63)
k 3
Therefore,
fu(2) + f(x) = p=xx + E[max(z x;)]
(B.64)
This establishes pointwise convergence of to f. Next, we need prove that the family of functions {f&} is equi-lower semicontinuous.
Lemma B.1. The family of functions {Sk} defined above equi-lower semicontinuous under mild assumptions on the boundedness of the data points Zz.
Proof. First, observe that each fa continuous (and hence lower semicontinuous). For any IR
and 0, consider the neighborhood
V (v |/ 2o100 < <8/2]
(B.65)
For any y E V and any j, é, we have
21,5 - 81 > 21, 2z 2/2
(B.66)
Therefore,
max - Vıl max(21,5
E4 - =/2] = max (2. xz] - -E/2
(B.67)
32

---

This implies
max Zad
Vil
max [ij - xxi] -e/2
(B.68)
Combined with the linear term, we get
fa(v) = p"y + max 22g - Yil
(B.69)
jml
k
2 pp x 1|l|1 E/2 +
Σ
max(zis - xz] E/2
(B.70)
h:
j=1
=x(x)) - ||l|1 ee/2 -
(B.71)
By choosing e small enough, we ensure that |lel| e/2 + 8/2 < which gives us
inf BEV
(v(v) > [x(x)
(B.72)
This holds for all establishing the equi-lower semicontinuity of the family {Sk}.
Since we have established that the functions fa. are convex, continuous, and equi-lower semicontinu- ous, and that they converge pointwise to S, we apply Lemma conclude that Sv. epi-converges
f. By the fundamental properties of epi-convergence, f& epi-converges to f. then min f& - min f-
Also, every limit point of minimizers of fk is minimizer of This establishes that CD CD as k +
Optimality Conditions and Characterization. Now, we analyze the optimality conditions for the dual problem. Consider our objective function:
fa(a) Σ Px
K Σ
max ((i,s) aryl
(B.73)
To find the derivative with respect a, note that the derivative of the first term simply (x( For the second term, we need to understand how the max function behaves. At points where unique index j achieves the maximum value of f s) ay, the derivative is:
i m)x(f(iss) a,] {-1 do;
if = argmax, (((, -ay]
(B.74)
otherwise
The negative sign appears because og has negative coefficient in the expression inside the max.For simplicity, we often write the optimality condition using the indicator function 1 e argmax, (f ay]], which equals! when
the argmax and otherwise.
a max(f(i.) 8) - azl = -1 argmax(s(j,s) asll dag
(B.75)
If there are ties (multiple indices achieve the maximum), then the max function is not differentiable. Instead, we use the concept of subdifferential. A valid subgradient can be written - 1 argmax, (f(, - a,l] wi. where are weights such that Σ EEargmax w, = 1.
The derivative (or subgradient) of the entire objective function with respect to ay is:
0f
1 Ke
Px(1)
Σ
lli E argmax[f(j.s - -351
(B.76)
Da:
33

---

Then, for the optimal dual variables a", the first-order optimality condition gives:
1 E ff (a (x - da:
Ul E argmax([[ - a; =0
(B.77)
We interpret this optimality condition as follows: the probability (x(i) equals the empirical probabil- ity that is in the argmax of f(j, -0 az across all samples Rearranging, we have:
ll E argmax(](.,)) - azl = Px(
(B.78)
To fully understand the emergence of the Gumbel- MMx connection, we must carefully analyze how the discrete optimality condition converges to its continuous counterpart as k co. The key step is understanding how the empirical average on Equation becomes the probability statement:
Pr Pr(argmax(2; a3) = i Px(
(B.79)
other words, remains to show that
h Σ ii ie arg arg f(..s) - aj}} - Ef14ie arg f() ajjl (B.80)
In order to show this convergence, let or denote the optimal dual variables for the problem with k samples. From epi-convergence f& to f. we know that oj - as oc.
For any fixed o, the indicator functions {i E arg max 8) s)-a are independent and identically distributed across s, since f(..)) s) are sampled independently. Therefore, by the Strong Law of Large Numbers:
Σ lii mrgmax(f(j.s) ayl3 ":"i EiL e arg maxx((((iss) aylH
(B.81)
To address the case where a replaced by og which depends on the samples, we decompose:
1i E arg aggmaxff - oh,,1 -
Ei arg max ař1b]
(B.82)
1ii E arg max(f((((ss) o
Σ
1fi arg arglafffii - azl) (B.83)
k
1i E arg max max - aj}} B[i arg argmax az]]] Σ h
(B.84)
The second term converges to zero by the Strong Law of Large Numbers. For the first term, we exploit the fact that the argmax function is stable under small perturbations except at ties, which occur with probability zero for continuous distributions of f.
Specifically, let A = |laj - a² olo. For any realization of f(j. s), the argmax changes only if the perturbation A exceeds the minimum gap between the maximum value and the second-largest value. Let G. min (f(j",s) a3-1 (f( az], where j* = arg [f s) az}. Then:
{i E arg max (f(, o * 1 i E arg max [( - az} = A > G. (B.85)
Since or - a", we have A + 0 as k + The probability P(A, G.) converges to zero because G, > almost surely continuous distributions. By dominated convergence, the first term also converges to zero.
34

---

Consequently:
& Σ li arg 8) - -k,l] & El1(i E arg maglaxf((i.s) a31H
(B.86)
Combined with our optimality condition equation B.78). we obtain:
(x(1) = B[lfie e arg (axxx(((ss) - - = P(arg max[f(i. -a]] = (B.87)
In other words, the random mapping S argmax,(f(i.. exactly. This fact is precisely what Theorem B asserts: the Gumbel-Max procedure constitutes the optimal-transport coupling between Px and the side-information mechanism.
a reproduces the original law Px
Connection to Gumbel Watermarking. The Gumbel watermarking scheme described above can be directly interpreted within our optimal transport framework by noticing that this same arg-max coupling is exactly what underlies the Gumbel-Max trick: adding Gumbel noise Gr(j) to (negative) logits (*(2) and taking argmax samples from the softmax. our formulation, the cost function f(j s) corresponds to the Gumbel noise Ge(j), while the dual variables aj correspond to 14()) The optimality condition
(i( = P(arg - azl =
(B.88)
precisely the Gumbel-Mar trick, which states that sampling from softmax distribution is equivalent to adding Gumbel noise to logits and taking the argmax In practice, under the watermarking process, the Gumbel scheme replaces the uniform variables (y with pseudo-random values Fg.. 1.k(y)
that depend on the secret key and previously generated tokens. This creates a coupling between the original token distribution and the side information, exactly as prescribed in our optimal transport approach. Thus, when we assume i.i.d. scores, the Gumbel watermarking scheme represents specific instantiation of our general optimal transport framework, where the coupling is designed to preserve the original distribution in expectation while maximizing detectability through heavy-tailed score distributions.
B.5 Proof of the Detection Gap, Theorem
In Section we introduced the HeavyWater scheme by generalizing the scores beyond the binary case. Since [a, 8) is random, D!Pp) (m, k X) given by
D Prl (m, k. A) min max (Epxs [S(X Epx Ps (J( PxEPA Pxs
(B.89)
gap
also a random variable. Now, we will show that we can go beyond Theorem 3 improving on the watermarking scheme like Gumbel, and prove Theorem that connects the asymptotic detection gap with the quantiles of the distribution of the score difference A f(x, 8) f(x',
Theorem 4 (Detection Gap, asymptotic randomness). Lei X E [2, 1), and consider the score difference random variable A = f(z, - f(z', s'),
s') for some (x, s) $ (I',s'), where f(x, s) and f(x', s') are sampled i.i.d. from Pf. Let the cumulative distribution function of be and let Q = F-1 be its inverse. Then,
[' Quu)du.
lim D DI ( (m,k, k, k
(B.90)
Proof. We begin by characterizing the structure of the optimal coupling Pxs that attains the maxi- mum in [B.9] below.
"To see this precisely, substitute the jth logit -a on RHS B.88 and simplify the RHS using the same steps as in Appendix B. of (24). This shows that [B88) holds when - -a jth logit. Which means that the Gumbel watermark is a special case of our construction in sec. (which boils down to (.88),, with f(z, s) specifically chosen has Gumbel(0, 1).
35

---

E [k]
[f( -B Ps [s)
max
Pxs
Pxs
s.t.
Pa. = Pos a m}
m
Σ
Pa
K' sE(,...., k}
(B.91)
Lemma 1. The minimum in B.89 is achieved by the Px E Px satisfying
A,
x i,
(x(x)
1 x
x = Js + i,j. I
(B.92)
0,
as shown in (B.77. Assume that X 2 1.2 given by
Then, the optimal Pxs, solution of Equation B.9 is
88
8141
8r42
8% 0
A 1-
0
E
0
1+
E
where r is the integer satisfying
r+1
The optimal coupling assigns the probability mass of æ = i sequentially to the first r side-information bins until its total mass exhausted, after which the remaining bins are filled by x = j. This is intuitive as Px (1) 2 Px()).
For given K max Exx ()) is given by
max E [6] Px3
Px [f(
(B.93)
1
s(1,s) + (^- f(L++1)+
( (
1(2,r+1)+ s)
Σ
(B.94)
8=r+2
s2) + (~-=) Art1 +
1 1 D.
(B.95)
h
k
For E Px Po (f), we have
1- x k
E Px Ps [f(X
=
f(1,s)
f(2, 8).
(B.96)
k ==1
k
Therefore, the difference is given by
max
RI Pxx
S))
[IA] Px [(X,S)]
(B.97)
Pxs
k s(2,8) +
1
(^- x Ar+1 +
ΣΣ4 A
f(1,8)
1-
((2
(B.98)
k
k s=1
k
s=1
Σ [(2 8) + (2-
To Art1 +
r
1
ΣA A
((,,8)
(B.99)
Let us define the following terms that we will analyze precisely:
&
1
1 EA.
fi, = To Σ f(1,s),
F2
F2 and
Is
(B.
K
ho
a=1
36

---

With these definitions, we can rewrite the detection gap as:
max E [kl Px [f(X,
kk Px [f( Af2. (s Ar+1 + La Af1.
(B.101)
Px3
To establish the exact limit, need to analyze each term with greater precision.
Exact characterization of x(22. fi,x): Both f(1, s) and f(2, s) are i.i.d. sub-exponential random variables with parameters (v² b). By the strong law of large numbers, have almost surely:
lim f.AA ([,(1,1) and lim f2,4 (2, 1)1
(B.102)
k-000
Since fzz s) are iid. with zero mean, have E[f(1 1)] Eff 1)] 0. Therefore, almost surely:
lim X(F2 f1,)) -0 k
(B.103)
Exact characterization of (A- E) Ar+1: By definition of r = [Ak]. we have 0 < X - Since Ar+1 is a sub-exponential random variable with parameters (4v², 22), it is almost surely finite. Combining this with the above inequality:
limm (* (^-)) Ar+1 80000
almost surely.
(B.104)
Exact characterization L:: For this term, use order statistics. Let Am) S A22) S S A(a) denote the ordered values for the difference of scores A, Then:
k
A
(B.
j=k-r+1
Let F be the CDF of A, and F& be the empirical CDF given by
(x)
Σ uA. <z)
(B.106)
k:
By the Glivenko-Cantelli theorem, we have:
sup [x) - F F(x) S me where + 0 almost surely as k + oo
(B.107)
=ER
For each order statistic AGj, the empirical CDF by definition gives Fs(A()) 1.- Glivenko-Cantelli gives:
The bound from
j-m Th S F(AG)) k
1 k
(B.108)
Let Q F-1 be the quantile function. By definition of the quantile function, p F(x) then
((p) S x, and if F(x)= S q then x < Q(g). Applying these relationships:
Q (1 (--m) T < A () s Q
2 m
(B.109)
Now we perform change index. We want rewrite the sum in lg which uses index j ranging from k - + to k. Let's set j = k i 1, so ranges from 1 to r. This gives:
j k
i-1
(B.110)
k k
Substituting this into bounds Ag):
2
i
$Q
i-1 k
17p
+ 1
(B.111)
k
37

---

Summing over i from 1 to and dividing by k:
r
1k
A
(k-++1)
(B.112)
k
k
Σ
A
(B.113)
k
j=
(B.114)
i
< 1
+
(B.115)
As k oc, we know that 7k - almost surely by the Ceivenko-Cantelly theorem. The points
Uj = - 1-1 for i I....,r where r = [Ak], form a partition of the interval [1 X, 1] as follows:
ur r
U1 = 1, U2 = k.' Uy
-1
(B.116)
k'
As -> oC, the number of points - 0. Therefore, these points {ur J= form an increasingly fine partition of the interval [] X, 1]. For any fixed u E [1 - X, I]. as k + co, there exists a sequence of indices in such that us + u. Specifically, we can take is [k(1 u) + 11. which ensures Uig I can be written as:
[ also increases, and the distance between adjacent points
+ K - Our bounds for
Σ Quu mh) S I
Q(u + mR)
(B.117)
Since Q is non-decreusing, is bounded on the compact interval [1 [1- X 11-A-1,111 Let
3,1+ B] for some / > 0.
M
sup EE 1
[Q(t) < co;
(B.118)
then Q(u nk)l & M and (Q(u: + nk) S M for all and sufficiently large k.
The lower sum 7/4 Σi= Q(u: 77k) is a perturbed lower Riemann sum for the integral f Q(u) du, and similarly the upper sum is perturbed upper Riemann sum. As k + co, two things happen simultaneously, namely, (i) the mesh width - 0, so the Riemann sums converge the integral and (ii) the perturbation 7)s - 0, so Quu = mh) + Quu)). By the Dominated Convergence Theorem, we have
Σ Quu 7x) Sr Q(u) du
lim oo
(B.119)
lim Ee + mx) f Q(1) du 100
(B.120)
Since J bounded between these two quantities that converge to the same limit, we have
17 = f. Q(u)du almost surely.
lim A-000
(B.121)
1->
Combining all terms: From our asymptotic analysis of each term, have:
lim In = =f" Q(u)du almost surely. k
lim max BlM] (((, [[X, k Pxs
[S(X
(B.122)
Therefore:
lim DIPrI k, A) fr 1-
Q(u)du.
(B.123)
k4000
gap
38

---

Theorem 4 Himplies that distributions with heavier tails imply larger values of the integral ʃ_ (u))uu.
which in turn imply higher detection gaps. Indeed, fix A. We say that a distribution F2 is (right- theavier-tailed than F1 when F2(z) S 1 (x) for all large æ, equivalently Q2(u) 2 Q (n)
for every u in neighbourhood of 1. In particular, for all u E [1 X, 1]:
Q2(u) Qu(
which implies:
S Qz(u)du 2 Lra, Qi(u)du
Therefore, keeping the same confidence levels:
heavier tail =
larger
Q(u)du = larger guaranteed detection gap.
The asymptotic detection gap, given by Ji=x Quu)du, represents the average value of the quantile function over the upper À fraction of the distribution. This integral captures how much signal can be extracted from the tail of the score differences. Distributions whose upper tail places more mass far from zero (resulting in larger values of the integral Ji=x Quu)du directly increase the detection capability of the watermark. This explains why the choice of score distribution fundamentally impacts watermark detectability. Consequently, among distributions with the same mean and variance, the heavier-tailed ones yield strictly higher guaranteed detection rates. Therefore, if we constrain ourselves to the ensemble of sub-exponential probability distributions, by choosing something with a heavier tail than Gumbel, e.g.. Log-Normal we can achieve better detection scheme, as we show in our experiments, ef. Figure
Remark By using Bernstein's inequality for sub-exponentice variables and Dvoret- dk-KKiefe-Woolfowk inequality instead of Glivenko-Cantelli it is possible to show non-asymptotic version of the theorem above:
Theorem 5 (Detection gap, formal). Let X be fixed, write [Ak] and define
&
Ik
- A. k ==1
f
F(, fa. k
Σ f(2,s),
==1
where A. = f(l, - -f(2, s). For any confidence levels 6, 8888 E (0,1) set
2v² log(1/0)
b blog(1/8)
Ex( =
(8') = max 2v log f. 26 2blog 1 8
k
k
mx(81) (2g(2/
21:
Then, with probability at least 1 - 8 - 8' 5t,
[R] Px
- [k Px ([( (X.
o
i-1
mo((t) 25x(8) + 4(6")
max Px8
1=1
1B.124)
where Q F-1 is the quantile function of A., and B(M) denotes expectation where the side information alphabet is of size k.
C Additional Information and Implementation Details
C.1 Low-Entropy Distributions in LLMs
To motivate the low-entropy regime, we compute summary statistics of token distributions of popular open- weinhw LLMs. We consider the densities of three statisties: infinity norm (connects directly to min-entropy entropy, and L-2 norm, all calculated on the next token prediction along a collection of responses.
[1)
An infinity norm of X, i.. max, P(z) < X, translates directly min-entropy constraint of - log A.
39

---

We observe that 90% LLM token distributions fall into the low-entropy regime we consider with infinity norm greater than 1/2, i.e. max, P(z) 2 across the three open LLMs (Llama2-7B(4) Llama3-8B 63). Mistral-7B) and two on popular prompt-generation datasets (Q&A tasks from Finance- QA 45 and coding tasks from LCC| We show the histogram and CDF plots Fig.
D.14 and D.I5
C.2
Theoretical effect of different tails of distributions
To further improve the detection performance, we go beyond binary score functions to explore the flexibility in the design space that continuous score distributions offer. Motivated by the Gumbel watermark 177. we observe that we can significantly improve detection by using continuous score distributions, particularly those with heavy tails. Recall that minimax formulation considers the low-entropy regime (A E [1/2, 1)). where the worst-case token distribution Px has only two non-zero elements with values {A, - A}. Working with this distribution, consider score matrices where each entry f [xx 8) is sampled independently from a distribution PF with zero mean and unit variance. We additionally assume that (and hence every A, [(1, f(2,)) is sub-exponential with
x²x²) for all | & 1/b. Many distributions, such as Gamma, Gaussian, and Lognormal satisfy this property. This formulation leads Theorem which formally characterizes the achievable maximum detection gap for any Pp for large k. in terms of quantile tail integrals of various candidate distributions its score distribution Pr. We visualize the result in Fig.
parameters (v², b). i.e., E[e^/] I exp( 2
In Fig. C.5 we present the quantile tail integrals of four different distributions: Lognormal, Gamma, Gaussian, and Gumbel. A higher value on the y-axis (quantile tail integral) indicates greater detection gap under the low-entropy regime, which translates to a greater probability of detection under adversarial token distributions. In theory and as seen from Figure C.5 drawing score functions ii.d from either the Lognormal Gamma distribution outperforms that from Gumbel. Recall that the significance of adopting the Gumbel score function that we have established its equivalence with the Gumbel watermark by [17] in Theorem Although the Gamma distribution maximizes the detection gap in the worst-case regime, we observe that choosing Pr to be lognormal achieves the highest detection accuracy in practice, which is what we eventually adopt for HeavyWater.
0.25
Quantile Tail Integrals
0.20
0.15
Lognormal
0.10
Gamma
Gaussian
0.05
Gumbel
0.90
0.91
0.92
0.93
0.94
0.95
0.96
0.97
0.98
0.99
A
Figure C.5: Tail integrals of different score difference distributions: Higher the tail integral, better the detection.
C.3
Q-ary Code
We provide discussion of the direct extension of SimplexWater to go beyond binary-valued scores. Recall that SimplexWater uses the binary Simplex Code as its score function. For a given prime field-size q. a Q-ary SimplexWater adopts the corresponding Q-ary Simplex Code [14], which define next. Besides the score function, the algorithm for Q-ary SimplexWater is identical to the binary case, which we have provided in the main text.
Given an alphabet of size m and field size q > 2, the size Q-ary codeword q to the power of the ceiling of log m with base g, i.e. n = g flog, ml, For any x, 8 [0 n - 1], let qary( qary(s) denote their Q-ary representations respectively using bits. A Q-ary simplex code fsim [0
40

---

1] x [1: -1] - 10:00 - 1 is characterized by
faim s) _ dot(qary(z) qary(s)),
(C.125)
where dot(qary(2)), dod((ary((e..qar((s)) & Σm= qary(a)); qary(s); and qary(o); denotes the ith bit in the
Q-ary representation of
There are two main limitations Q-ary SimplexWater, which motivated us to explore a continuous score function directly and ultimately led to HeavyWater. The first limitation is that we do not have optimality guarantees for the Q-ary code. Recall that to maximize watermark detection, the optimal code maximizes the L1 distance. Simplex Code achieves the Plotkin bound, which maximizes the pair-wise Hamming distance between codewords. In the binary case, maximizing the Hamming distance and L1 distance are equivalent, where 1 j 5l; in the Q-ary case, this equivalence doesn't 't hold. Hence, we do not have an optimality guarantee in detection for Q-ary The second limitation is that the size of Q-ary codewords is potentially very large, leading to memory issues in actual implementation on a GPU. Recall that in the binary case, we have n = m - 1. In the Q-ary case, however, the use of the ceiling function when converting to base-q artificially inflates n, often far beyond the actual vocabulary size. For example, with 7 and a vocabulary size of m 100,000, compute [log7 (100,000) ~ [5.92] = 6, which corresponds more than 18% larger than the original vocabulary. Furthermore, the required alphabet size implement Q-arry code grows with q-
7 117,6499
C.4 Implementation Details
In this section we provide additional implementation details for Simplex and Heavywater. Our code implementation employs the code from the two benchmark papers, namely WaterBench and MarkMyWarn Words
43
Score Matrix Instantiation We sample the score matrix once during the initialization stage of HeavyWater generation and it has shape (m, k). Each row maps a vocabulary token to a cost vector over the side information space S. This matrix is stored torch. Tensor and reused across watermarking calls. During generation, the score matrix is used as the cost matrix for Sinkhorn-based optimal transport computations.
Normalization of f As described before, for each element in the vocabulary, & samples for the score f are drawn from a heavy-tailed distribution (log-normal the experiment). To ensure numerical stability and suitability for optimal transport computations, each row of the score matrix (size vocab_siiee k) is normalized to have zero mean and unit variance.
Top-p Filtering To reduce the computational cost of watermarking, top-p filtering is applied prior to watermarking. Identical to the common definition of top-p, take the minimal set of tokens whose cumulative softmax probability exceeds a threshold (c.g., = 0.999). The watermarking algorithm is then restricted to this filtered subset. We emphasize that, in the considered experiments, top-p filtering was applied to all considered watermarks to maintain consistency in the experimental setting.
Detection Algorithm We outline in Algorithm 2 a standard watermark detection algorithm that employs a threshold-test with score matrix F. Given the sampled token x and side information the corresponding score Fr,. = f (Ix, s), which obtained in a similar fashion to its construction in generation: If SimplexWater is used, then it is obtained from the Simplex code, and if HeavyWater it is randomly sampled using the shared secret key as the initial seed. This maintains the generation of the same cost matrix F on both ends of generation and detection. A watermark is detected if the sum of scores exceeds a certain predetermined threshold.
41

---

Algorithm 2 Detection using a threshold-test with a score matrix
Input: Token sequence x", side information s, seed, score matrix R
2: Outputs: p-value based detection outcome
3: for 1 to T" do
4:
Compute score 0; := Fz,,5
5: end for
6: Z + 11=1 9:
7: if Z then return "Watermark Detected"
8: else return "No Watermark"
Fresh Randomness Generation Fresh randomness is crucial to ensure side information is sampled independently from previous tokens to avoid seed collision. Our implementation supports several seeding strategies. In majority of our experiment, we use the 'fresh' strategy, which generates unique seed for each token by incrementing counter and combining it with the shared secret key. This allows both ends to share the same seed that dynamically changes, but is independent of previously generated tokens. Our implementation of HeavyWater and Simplexwater also allows for various forms of temporal or moken-based encoding strategies, such as sliding-wii window hashing.
C.5 Information on Optimal Transport and Sinkhorn's Algorithm
In this section, provide preliminary information the considered OT problem and its solution through Sinkhorn's algorithm. Let p E Am and q E 4 be two probability vectors. For a given cost matrix C E Rmxk the OT between p and g is given by
m
&
(T
min rEll
P.j
where pp.. is the set of joint distributions with marginals and q. which we call couplings. Efficiently solving the optimization OT q) is generally considered challenging (36). To that end, common approach to obtain a solution efficiently is through entropic regularization. An entropic OT (EOT) with parameter is given by
OT. min Pellp
ΣΣ C.pPa [.PpPiscCPP) j=
where Ea, which implies its fast convergence to the unique optimal solution. However, the EOT provides an approximate solution which converges to the unregularized solution with rate O(e log(1/e)).
and C'ss the OT cost. The EOT is an e-strongly convex problem,
One of the main reasons EOT has gained its popularity is due to Sinkhorn's 's algorithm (64, which is matrix scaling algorithm that has found its application to solve the dual formulation of the EOT problem [19]. Sinkhorn's 's algorithm looks for pair of vectors u, that obtain the equality
P' diag (
where Pt is the EOT solution and K exp(-C/c) is called the Gibbs Kernel. Consequently. Sinkhorn's algorithm follows from simple iterative procedure alternately updating u and v. The steps of Sinkhorn's is algorithm are given in Algorithm Having solved Sinkhorn's 's algorithm, we obtain the optimal EOT coupling. When using Sinkhorn's algorithm, the stopping criteria is often regarding the marginalization of the current coupling against the corresponding marginal, i.e., check wether u の (Kv) pll < where A Σx= In our implementation, we solve Sinkhorn's algorithm using the Python optimal transport package [65].
ビ [u; (Kr); psl and 8 >> 0 is some threshold.
42

---

Algorithm 3 Sinkhorn's 's Algorithm for Entropic OT
Input: Marginals Px Am, Ps Ag. cost matrix C' Rm** regularization parameter Threshold > 0.
2: Output: Optimal coupling P E p
3: Calculate kernel K +- exp(-C/8
4: 1 mi
f- 1;
5: while [ (K v) Px| xx|1= > å do
6:
- (/(K
element-wise division
7: U uK
8: end while
9: P diag(u) K diag(e)
10: return P
D Additional Numerical Results and Ablation Study
D.1 Ablation Study
We perform an ablation study to investigate the effect of various hyperparameters set in SimplexWater and HeavyWater. The ablation study is performed in a curated subset of prompts from the Finance-QA dataset 45 considered in Section 5
Sinkhorn Algorithm Parameters. We study the effect of Sinkhorn's 's algorithm's parameter on the performance of the proposed watermarking scheme. We note that, while the Sinkhorn's 's algorithm is set with a predetermined maximum iterations parameters, the considered experiments the algorithm runs until convergence. We study this effect through three cases.
1. We analyze the effect of Sinkhorn's 's algorithm's 's regularization parameter on the overall runtime. While lower values of e provide solution that are closer to the underlying OT solution, often smaller value of required more time for convergence of the algorithm. As seen from Figure D.6a as expected, smaller e increase overall runtime. our experiments chose = 0.05 which resulted in overall satisfactory performance, while incurring mild runtime overhead.
2. We analyze the effect of the error threshold on runtime. The lower the error threshold, the higher the higher the accuracy in the solution and the higher the overall algorithm runtime. This is indeed the case, and the effect on the watermarking procedure runtime is visualized in Figure D.6b
3. We analyzed the effect of the error threshold on the watermarked distribution cross entropy (see Section 5 for definition). As seen from Figure D.6c while lower threshold results with a higher runtime, the improvement on the cross entropy, which is a proxy for textual quality, becomes negligible from some point. In experiments, chose threshold value of 10 which demonstrated the best performance between runtime, cross entropy and detection.
D.2 Impact of Non i.i.d. Side Information Generation
As we previously mentioned, most of the considered experiments in Section operaae under 'fresh randomness' scheme, in which try to replicate independence between the random side information and the LLM net token distribution. However, in practice various hashing scheme are employed, often with the purpose of increasing the overall watermarking scheme's robustness to attacks. Such hashing schemes aggregate previous tokens (using some sliding window with context size h) and a shared secret key N. We are interested in verifying that indeed, robustness driven seed generation scheme do not degrade the performance of our methods.
To that end, in this section we test the effect of various popular hashing schemes in the performance of our watermarks. As both SimplexWater and HeavyWater follow the same watermarking algorithm anticipate them to demonstrate similar dependence on the hashing scheme. We therefore prioritize
43

---

17.0
HeavyWWiter SimglexWeter
HeavyWatter SimalesWWatr
Nveroge generetion time (ec)
SimplexNNate
18.3
16.5
18.0
Crost Entroyy (nats)
17.5
0.245
16.0
17.0
25.5
15.5
0.292
15.0
10
Sinkhorn
10
Sinkhom
10
10"
10
Sinkhorn
10
(a) Generation time vs. Sinkhorn regularization parameter
(b) Generation time vs. Sinkhorn
(c) Cross Entropy of watermarked text Sinkhom error threshold.
error threshold.
Figure D.6: Effect of Sinkhorn Algorithm's parameters on Runtime and distortion.
an extensive study single watermark SimplexWater. For given sliding window size h, consider the following seed generation functions:
1. min-hash, which takes the minimum over token-ids and multiplies it with the secret key, i.e.
seed = -iin((:-1,,..... FEt--) r.
2. sum-hash, which takes the sum of the token-ids and multiplies with the secret key, i.e. seed = sum Tt-h) -T
3. prod-hash, which takes the product of the token-ids and multiplies it with the secret key, i.c. seed
4. Markov-1 scheme, which considers h 1.
We present performance across the aforementioned schemes, considering several values of h. As from Figure [.8 the change of seed generation scheme is does have significant effect the overall detection-distonee distortion tradeoff. Furthermore, as emphasize in Figure [.7] the size of the sliding window also results in negligible effect the watermark performance.
0.3
022
8.2
0.2
12
(a) Cross entropy vs. context win- dow size, min-hash.
(b) Cross entropy vs. context win- dow size, sum-hash.
(c) (p) vs. context window
size, min-hash.
Figure D.7: Seed Ablation: The effect of the context window is is negligible the performance of SimplexWater.
D.3 Experiment: Robustness To Textual Attacks
The watermarks in this paper are obtained by optimizing problem that encodes the tradeoff between detection and distortion under worst case distribution. To that end, the proposed watermarks are not theoretically optimized for robustness guarantees. However, robustness is often byproduct of the considered randomness generation scheme, as text edit attacks mainly effect the context from which the seed is generated. A discrepancy in the seed results in discrepancy in the shared side information sample s. However, regardless of the seed generation scheme, one has to choose a score function and watermarked distribution design.
In this section, we show that, while not optimized for robustness directly, SimplexWater and HeavyWater demonstrate competitive performance in terms on robustness common textual edit attacks. We consider the setting from the watermarking benchmark MarkMy [44). We compare performance with the Red-Green watermark and the Gumbel watermark. We choose
44

---

Sum h-3
min h=2
Sum h-4
3.4
3.2
min h-4
sum
-l0g3n
3.0
min h-5
prod h=2
3.3
sum h=
h=7
prod
sum h=9
Markov-1
Fresh
3.1
0.285
0.290
0.295
0.300
0.305
0.310
0.280
0.285 0.290
0.295 0.300 0.305 Cross-Entroon Inats!
CE
(a) Cross Entropy 1p).
(p) (b) Cross Entropy
plane. is visible that the performance of our watermark is consistent across an array of hashing scheme and context window sizes.
Figure D.8: Seed Ablation visualized in the
the value of d for the Red-Greed watermark such that its cross-entropy distortion is comparable with S SimplexWater, HeavyWater and Gumbel (5 1).
We consider three attacks:
1. A Lowercase attack, in which all the characters are replaced with their lowercase version.
2. A Misspelling attack, in which words are replaced with a predetermined misspelled version. Each word is misspelled with probability 0.1.
3. A Typo attack, in which, each character is replaced with its neighbor in the QWERTY keyboard. A character replaced with probability 0.05.
schemes demonstrate strong robustness under the considered attacks, resulting in the highest detection capabilities in 3 out of 4 cases and competitive detection power in the 4th. This implies that, though Simplexatter and HeavyWater not designed to maximize robustness, the resulting schemes show competitive resilience to common text edit attacks.
As in Figure D.9
RG, 5 = 1 Gumbel
Linear Code
Heavy Tail
-log10 (p)
Unattacked
Lowercase
Misspelling 10%
Tyрo 5%
Figure D.9: Robustness to attacks - HeavyWater demonstrates equal or superior detection performance, as measured by - 1logo (P), across variety of attacks involving edits to generated outputs.
45

---

D.4
Computational Overhead
We analyze the computational overhead induced by the considered watermarking scheme. Theoreti- cally, Sinkhorn's 's algorithm has an iteration computational complexity of (km) for token vocabulary of size | = m and side information of alphabet [S] due to its vector-matrix operations. In practice, watermarking is single step within the entire next token generation pipeline.
We analyze the computational overhead induced by applying SimplexWater and HeavyWater. Figure D.10 shows the overhead of watermarking in a few common watermarks Red-Green [15], Gumbel [77 Inverse-transfom [3.. SynthID [1I] and our watermarks. It can be seen that The Gumbel, Inverse transform and Red-Green watermarks induce a computational overhead of 10%, while SimplexWater. HeavyWater and SynthID induce overhead of 30%. While this overhead is not negligible, our methods demonstrate superior performance over considered methods. However, replacing a 'fast', yet 'weaker' watermark with ours boils down to difference in 20% increase in generation time. We consider an implementation of the SynthID through vectorized tournament sampling with a binary score function and tournament layers, which the method reported in the main text experiments. As we previously mentioned, we consider top-p sampling with y=0.999. We note that, in many text generation schemes, lower top-p values, which accelerate Sinkhorn's algorithm's s runtime, thus further closing the computational gap.
Rolative runtime overtead 1%)
25
20-
15-
10
Gumbel
Inv. Transform
Red Green
SynthiD
HeavyWWater SimplexWattr
Figure D.10: Computational overhead over unwatermarked text generation, Llama2-7b.
D.5 Experiment: Alternative Quality Metries for Textual and Coding Tasks
This paper focused on distortion as the proxy for textual quality. This is a common practice in watermarking (e.g. [1I [3
17 24 25)). Distortion is measured by the discrepancy between the token distribution Px and the expected watermarked distribution IEs [Pxss)) In practice, distortion and textual quality often measured with some perplexity-basee measure (e.g. cross-entropy in this paper). However, as explored in the WaterBench benchmark 433 such measures are not guaranteed faithfully represent degradation in textual quality.
[6
To that end, WaterBench proposed an array of alternative generation metrics, whose purpose us to evaluate the quality of generated watermarked text, and tailored for specific text generation tasks. We consider 4 datasets from the WaterBench benchmark 43
1. Longform QA [44] A dataset of 200 long questions- answer generation prompts. The considered generation metric is the ROGUE-L. score.
2. Knowledge memorization: A closed-ended
benchmark drawn from KoLA [66), consisting of 200 triplets sampled at varying frequencies from Wikipedia the test an L.LM's factual recall. The considered generation metric is the F1 score as it is a factual knowledge dataset.
3. Knowledge understanding 677 |:]:
dataset of 200 questions that demonstrate the LLM's understanding of various concepts. The considered generation metric is the F1 score it is a factual knowledge dataset.
4. Multi-news summarization: collection of 200 long news clusters, coupled with summa- rization prompts. The score here is the ROGUE-L score.
46

---

As seen in Table D.3 our watermarks maintain competitive performance in the considered set of textual generation tasks, even under alternative text generation evaluation metrics.
To better evaluate quality of generated watermarked code, we include two coding-centric evaluation metrics that assess different aspects of code quality.
Pass@ K Evaluation (Functional Correctness) We evaluate functional correctness using the Hu- manEval dataset [46]. which is a popular benchmark for code generation. Pass @ K measures the empirical probability of a solution passing all unit tests among generated solutions. We measure 10, where execute the generated code against unit tests provided in the
pass@k with k dataset in a sandbox environment. As shown in the table below, our methods outperformed the competitors: (i) Simplex Water achieves the highest pass @5 (22.7%), outperforming all baselines including unwatermarked text (20.7%) and (ii) Heavy Water achieves the highest pass 10 (27.8%). nearly matching unwatermarked performance (28.1 1%). In all cases, performance is comparable unwatermarked code (see Ta.
Edit_Sim (Edit Similarity) We use this metric on the LCC coding dataset [46] which focuses code completion: generating the next few lines of code given a long context. Since the dataset is sourced from GitHub, numan-writted ground-truth completions are available. Edit_Sim is defined as the Levenshtein similarity between generated and ground code.
Let E Σ" be two strings over an alphabet E. The Levenshtein distance d1($1, ) is defined as the minimum number of shngle-character edit operations (insertions, deletions, or substitutions) required to transform 81 into $2. The Levenshtein similarity (normalized form) is then defined as:
dy (s1, 82)
LevSim(s1, = max $1
where |s| denotes the length of string s. Thus, LevSim(s1. $2) E [o, 1], with LovSim(s1, 82) = and only if 82-
benchmark our watermarking methods against prior work using this metric. The results are provided in the Table D.4] Specifically, HeavyWater ties for best performance 0.52. These two metrics support that Heavy Water and Simplex Water have no significant impact on the quality of generated code relative to unwatermarked code, and perform favorably when compared to competing methods both in terms of detection accuracy and generation quality.
Code Examples. We also include an example of generated code before and after watermarking with Heavy
Unwatermarked Output:
def has_ close, elementa (numbers: List [float], threshold: float) Sort the list of numbers numbers sorted (numbers)
bool:
Find the first 6 that are closer to each other than the threshold
numbers the list
7 min_distance for i in range (1, len (numbers)):
float('inf')
distance abs (numbers [i] numbers 1)) if distance distanee and distance < threshold: min_distance distance
11
# If we found pair of numbers that are closer each other than the threshold, return True return min_distance threshold
15
Unit Tests result: Pass > @ass@1 100% on this example prompt.
Heavy Water's Watermarked Output:
def has crrssccos__eeeeee elements (numbers: List [float], threshold: float) >> bool: close_ _arir__
for i in range (len (numbers)):
47

---

closest None
closest_distance float ("inf")
for j in range len (numbers)):
7
distance abs (numbers numbers [j])
if distance < closest_ _iiestddsstnc::
closest numbers [j] closest_diatance
distance
11
if closest and
threshold:
12
close_pairs. ((numbera[i], closeat))
return len Len(close_pairg
Unit Tests result: Pass > Pass 100% on this example prompt.
Example: Code Completion under Long Context
This example was shortened for brevity.
Prompt: Please complete the code given below.
#!/usr fonar/bin/eni python
2 -- coding: utf-8
from HttpUtils import App, build0pener
class Device (object):
def ._init__ (self, token):
self token token self app App()
11
check ceeck_inspettion (self); (self)))
12
data self app check inspettin ()
return data [abbreviated]
class Exploration app):
def iitoraationobeett).. (object):
self app app
20
petAreaList(selff
21
data self app exploration,area ()
22
return data [abbreviated]
25
class User (object:::
26
[abbreviated]
27
class RoundTable
29
[abbreviated]
class Menu (object): 31
[abbreviated]
34
__mame__ "__main_"" ";
from config import deviceToken, loginId, password 35
Answers provided by different methods:
Human Answer Ground Truth:
device Device (deviceToken)
No Watermark + Edit Sim = 0.94
dev Device (deviceToken)
HeavyWater Water
SaiiimSSSmmpeeee SSimplexCode + Edit_ Sim
48

---

device Device (deviceToken)
Red/Green + Edit Sim 0.9
Device (deviceeoke
D.6 Alternative Detection Metric
In this section we provide results on an additional detection metric. We consider the detection probability under a false-alarm (FA) constraint. As we consider watermarks from which p-values can be calculated, we can impose such FA constraint. For given set of responses obtained from dataset prompts, we are interested in caleulating an estimate of the detection probability some FA constraint, given set of p-values, each calculated for one of the responses. We obtain estimate of the detection probability at given FA constraint by taking the ratio of responses whose p-value is lower than the proposed p-value threshold, over the total number of responses.
We provide results on the FinanceQA dataset using Llama2-7h 7b. consider several FA values and visualize the resulting tradeoff curves in Figures D.11 and [.12] To obtain error-bars, we consider the following bootstrapping technique: Out of the 200 responses, we randomly sample 200 subsets with 150 responses and calculate the corresponding metric. From the set of 150 results provide error-bars, considering the average value and standard deviation. can seen that the trends presented in Figures and Balare are preserved under the considered detection metric.
0.6
0.6
Po@Pr
0.4
Green Inverse Thersform
Por8Pp
0.4
RediGreen
Channel
Inverse Thensform
Gumbel
Dumbel
exhote (Cuns)
Simplexvater (Durs)
Hasuy/Noter
Heavylltter (Durs)
0.30
0.33
0.40
0.45
0.50
0.55
0.50
0.65
0.30
0.35
0.40
0.43
0.50
0.55
0.60
Cross-Entropy (+-)
Cross-Entropy [nats]
(a)
PFΛ 10
Pb PFΛ 10-5
Figure D.11: Detection probability at a given false alarm constraint. LLama2-7b, Finance-QA dataset.
D.7 Additional Detection-Distortion Tradeoff Results
We provide results that explore the detection-distortion tradeoff, in addition to ones presented in Fig. and Fig. Bai We run three models (Llama2-7b, Llama3-8b, Mistral-7b) on two tasks (Q&A and
0.6
PoAPP
0.4
Red Inverse Transform
Gumbel
SinglestWale (Qun)
0.60
0.45
0.50
0.55
0.00
0.85
Cross- Pooss-Entropy [nats] (-)
Figure D.12: Pp PFA 10-6 LLama2-7b Finance- QA dataset.
49

---

coding). We employ the popular Q&A dataset, FinanceQA, and code- completion dataset LCC. Fig. shows the result for Llama2-7b on Q&A, while Fig. Ba shows the result for Mistral-7B on coding. In we present this tradeoff over the remaining datasets and L.Mss.
Fig. D.13
Uamo2-78, Coding
Mistral-78, Q&A
4.0
3.5
3.0
(p)
2.5
10019
FosGerm
3.5
4e Lundo mate
1.0
Chamine
0.50
0.65
Enoss-Entropy [nats]
Cross- Cross-Entropy [nats] (+)
Llama3-68.
Llama3-88. LCC
2.5
(0)
-logoo (0)
Gree unplootoee (100
Somr serdens
Roceilicn 10as
0.40
0.45
0.50
0.55
0.60
0.30
0.35
0.40
0.45
0.50
0.55
Cross-Entropy (mats](+)
Cross-Entropy [nats] (-)
Figure D.13: Detection-diisortioon tradeoffs multiple models and tasks.
Table D.3: Performance of Watermarking Methods across Four Datasets
Dataset
Watermark
Gen. Metric
Drop in GM +
log P
Gumbel HeavyWatt Water
21.20
-0.856
8.006
21.48
-2.188
8.089
Simplex Inv. Tr.
21.90
-4.186
4.985
Longform
21.27
-1.189
3.687
RG, 8
21.25
-1.094
1.456
RG, 8
21.19
-0.809
7.078
Gumbel
5.66
-2.536
1.085
Heavy Water
-3.804
1.605
Simplex Inv. Tr. RG, 8
5.71
-3,442
0.977
Memorization
5.38
2.536
0.792
5.35
3,080
0.482
RG, 8
5.82
5.435
0.912
Gumbel HeavyWater
33.42
-9,574
0.396
32,59
-6.852
0,308
Simplex Inv. Tr. RG, 5 RG, 5 3
31,50
-32799
0,920
Understanding
27.93
8.426
1.045
32.96
8.066
0.184
33.83
10.918
0.300
Gumbel HeavyWater
25,69
2.579
3.172
25.67
2.655
3,491
Simplex Inv. Tr.
25.86
1.934
2.701
MultiNews
25.74
2,389
1.586
RG, 8
25.85
1.940
0.963
RG. 8
25.74
2.389
3.781
50

---

Distribution of Probability Metrics llama2-7b-chat-dk Token Predictions
Infinity Norm Distribution
Entropy Distribution
L2-Norm Distribution
140
Inteaty (Mic Frobecs By!
Entropy (3iba
12-Homm
Distribution Probability
Predictions
Infinity Distribution
Entropy Distribution
30
32
64
100
2.5
8.5
Distribution Probability Metrics mistral-7b Predictions
56
36
C8
100
30
05
302
1.5
2.2
3.
04
35
0.6
30
Figure D.14: Histograms of statistics of token distributions Q&A dataset. 90% token distributions fall into the low-entropy regime with infinity norm greater than 1/2, i.c, max, P(x) 2 2"
51

---

Distribution of Probability Metrics llama2-7b-chat-dk Token Predictions
Infinity Norm Distribution
Entropy Distribution
L2-Norm Distribution
148
133
100
68
Intedly Norm (Mic By!
Estrapy (3lb)
12-Nomm
Distribution Probability Metrics
Predictions
Infinity Distribution
Entropy Distribution
30
10
64
100
Distribution Probability Metrics mistral-7b Predictions
12
18
02
1.0
02
34
C4
66
Figure D.15: Histograms of statistics of token distributions on coding dataset. 93% token distributions fall into the low-entropy regime with infinity norm greater than 1/2, i.c max, P(x) 2 2"
52

---

Table D.4: Results LCC Code Completion Dataset (Edit Similarity, higher is better)
Watermark Method Edit_Similarity 1
No Watermark
0.45
Gumbel
0.52
Heavy Water (Ours)
0.52
SimplexWater (Ours)
0.44
Inverse Transform
0.45
Red/Green 3
0.43
53


Reviews:
[{"review_id": "G2A8OH8DQX", "reviewer": "Reviewer_1jKu", "summary": "his paper proposes two novel watermarking techniques, HeavyWater and SimplexWater, to address the challenges of reliably detecting machine-generated text from large language models (LLMs), particularly in low-entropy scenarios like code generation. HeavyWater employs heavy-tailed score distributions to enhance detectability while minimizing distortion, while SimplexWater leverages simplex codes from coding theory to maximize the Hamming distance between watermarked tokens, proving optimal for binary score functions. The authors frame watermark design as an optimization problem, linking it to optimal transport theory, and demonstrate that their methods outperform existing approaches (e.g., Gumbel, Red-Green watermarks) in detection accuracy and robustness, especially for low-entropy text.", "questions": "How is the code pass@k in the experiments?", "limitations": "yes", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. The paper presents a rigorous and thorough theoretical analysis.\n2.  The paper extend binary score system to a continuous distribution for better performance.\n\nWeaknesses:\n1. The baselines listed lack some previous works that are specially designed to tackle low-entropy scenarios.\n2. The paper could demonstrate the entropy difference between the used datasets and high-entropy datasets such as C4 for better comprehension. And shouldn't the models include coding LLMs such as starcoder?\n3. The experiments should also include performance of high-entropy scenarios.", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review. We are glad that you appreciated the rigorous and thorough theoretical analysis. Below, we address the three points that you raised. Please note that we provide new results on how SimplexWater and HeavyWater impact code generation accuracy, namely Edit_Similarity for code completion and pass@k for code generation. We would be happy to answer any follow-up questions or comments you may have.\n\n### **Q1:How is the code pass@k in the experiments?**\n---\nThat’s a great question! To better emphasize quality of generated watermarked code, **we include two coding-centric evaluation metrics** that assess different aspects of code quality.\n\n**Pass@K Evaluation (Functional Correctness)**: We evaluate functional correctness using the HumanEval dataset [44], which is a popular benchmark for code generation. Pass@K measures the empirical probability of a solution passing all unit tests among K generated solutions. We measure **pass@k with k ∈ {1, 5, 10}**, where we execute the generated code against unit tests provided in the dataset in a sandbox environment. As shown in the table below, our methods outperformed the competitors: (i) **SimplexWater achieves the highest pass@5 (22.7%)**, outperforming all baselines including unwatermarked text (20.7%) and (ii) **HeavyWater achieves the highest pass@10 (27.8%)**, nearly matching unwatermarked performance (28.1%). In all cases, performance is comparable to unwatermarked code.\n\n**Edit_Sim (Edit Similarity)**: We use this metric on the **LCC coding dataset** [41] which focuses on code completion: generating the next few lines of code given a long context. Since the dataset is sourced from GitHub, human-written ground-truth completions are available. Edit_Sim measures Levenshtein similarity between generated and ground-truth code. A formal definition will be included in Appendix D. We benchmark our watermarking methods against prior work using this metric. The results are provided in the table below. Specifically, (i) **HeavyWater ties for best performance (0.52)**.\n\n**Key Insights**: These results demonstrate that our watermarks preserve both functional correctness and syntactic quality of generated code. The fact that SimplexWater and HeavyWater often match or exceed unwatermarked performance on these metrics, while providing strong watermark detection, highlights the effectiveness of our approach in maintaining code quality during watermarking.\n\n#### **Results on HumanEval Functional Coding Dataset**\n\n| Watermark Scheme           | pass@1(%) **↑** | pass@5(%) **↑** | pass@10(%) **↑** |\n|----------------------------|------------------|------------------|-------------------|\n| No Watermark               | 14.0             | 20.7             | 28.1              |\n| **HeavyWater (Ours)**      | **13.1**         | **18.9**         | **27.8**          |\n| Gumbel                     | 14.3             | 20.5             | 25.6              |\n| **SimplexWater (Ours)**    | **13.7**         | **22.7**         | **25.3**          |\n| Inverse Transform          | 13.8             | 22.0             | 27.5              |\n| Red/Green $\\delta=3$       | 11.6             | 19.5             | 23.2              |\n\n\n#### **Results on LCC Code Completion Dataset**\n| Watermark Method           | Edit_Similarity **↑** |\n|---------------------------|------------------------|\n| No Watermark              | 0.45                   |\n| Gumbel                    | 0.52                   |\n| **HeavyWater (Ours)**     | **0.52**               |\n| **SimplexWater (Ours)**   | **0.44**               |\n| Inverse Transform         | 0.45                   |\n| Red/Green $\\delta=3$      | 0.43                   |\n\n---\n### **W1: Lack of considering previous works that are designed to tackle low-entropy scenarios.**\n\nPlease note that we compare our watermarks qualitatively and/or quantitatively against **several** methods that are designed to watermark challenging generation processes that are ``low-entropy,’’ such as 1) code completion using the LCC dataset (see fig. D.13 in App. D.7), 2) Question answering using the Longform QA dataset (Table D.2), 3) Factual recall using the knowledge memorization dataset (Table D.2). We also acknowledge that low-entropy watermarking is an active field of research, discussing prior work in the field in Section 1 (see lines 105-116), as well in the Supplementary Material (see the related work discussion in Appendix A).  **We would be happy to include additional references you may have!**\n\nIn our work, we define the “low-entropy regime” in the very concrete and tangible sense described in lines 166-173 and 223 of the paper. Specifically, we adopt min-entropy as the entropy measure of choice:  $H(P) = -\\log_2 \\max_x P(x)$, where $P$ is the next-token distribution. Here, *low-entropy* refers to next-token distributions whose average entropy $H(P) \\leq 1$ bit/token (see lines 166-173 and 223) — i.e. **at least one predicted token has a probability greater than $\\frac{1}{2}$** (lines 166-173). While the literature acknowledges challenges in watermarking low-entropy distributions in general, to the best of our knowledge, this specific definition has only appeared in [52] and [R1]. We cite the former in the paper and will include a discussion of the latter as well.\n\nThe ‘low-entropy’ regime considered in our analysis is not merely a theoretical assumption. It is based on the empirical observation that LLMs’ next-token distributions are **inherently low entropy** in the sense given above. This is supported by our measurements reported in the Supplementary Material (see Appendix C.1). From these measurements (Figures D.14 and D.15  – see also [52, Fig.1] for further evidence), over 85% of next-token predictions satisfy $H(P)\\geq 0.95$, and over 90% satisfy $H(P)\\geq 0.5$ for practical temperature values. Therefore, the vast majority of next-token predictions fall well within the regime considered in our theoretical analysis – which provides precise optimality guarantees for $H(P)\\geq 0.5$. We observed similar patterns in the additional datasets we tested. Our theoretical results yield a new theory and interesting new connections between LLM watermarking and coding theory.  Importantly, it also yields provable performance guarantees for our watermarks (HeavyWater and SImplixWater) in the low-entropy regime (Theorem 1-4). These results are novel. \n\n**Justification of Benchmark Selection and Experimental Comparisons.** Our experimental evaluation was chosen based on established evaluation benchmarks such as WaterBench [41]  and MarkMyWords [42], which represent standard and well-known benchmarks in the LLM watermarking literature that ensure comparability among different methods. We evaluate our method on (1) code generation and completion (LCC dataset), (2) financial Q&A and (3) four additional tasks from WaterBench covering knowledge-intensive scenarios (Appendix D.5), which are tasks that fall within the low-entropy regime covered by our theoretical analysis. Moreover, we would like to emphasize that our theoretical analysis covers most next-token distributions in all tasks that we tested, since the min-entropy below 1 bit regime is actually most common as far as we can tell.\n\n---\n### **W2+W3: Entropy difference between datasets, including high entropy scenarios, including the C4 dataset and the coding LLMs**\n\nThank you for this comment. We would like to point out that, in addition to the code completion and QA datasets presented in the main text, we provide results for 4 additional datasets in the appendix. As detailed in **Appendix D.5**. In **Table D.2**, we assess the impact of watermarking on generation quality across four additional tasks from **WaterBench** [41]: **LongformQA**, **Multi-news Summarization**, **Knowledge Memorization**, and **Knowledge Understanding**. For these, we report **ROUGE-L** scores (LongformQA and Multi-news) and **F1** scores (Knowledge Memorization and Knowledge Understanding). As shown in **Table D.2**, our methods (SimplexWater and HeavyWater) maintain competitive detection performance across all datasets, with a generation metric comparable to unwatermarked text. Together, these datasets demonstrate the effect of our watermark on presumably varying levels of entropy scenarios.\n\n **Empirically, even though coding, Q\\&A, and summarization tasks are commonly understood as having varying degrees of ‘entropy’, we still observe $>90\\%$ of next-token predictions across all of these tasks falling well within the low-entropy considered in our theoretical analysis.** Again, recall that by ``low-entropy regime’’ we consider next-token distributions with min-entropy below 1 bit. In other words, though coding has lower entropy and tasks like Q&A have higher entropy (see Figures D.14 and D.15 for measurements), they both fall well within the regime for which our performance guarantees hold.\n\nFinally, we note that the C4 dataset is a text corpus. Most existing works consider standard prompt datasets, such as the six datasets used in our paper. The six datasets we used to benchmark our results are derived from standard watermark benchmarks, namely four datasets used in the WaterBench [41] and two datasets (FinanceQA [43] and LCC [44]).\n\nRegarding the choice of LLM, we mirrored choices made in competing watermarks that we benchmarked against, incl. Inverse Transform, SynthID, and Correlated Channel (see refs. [11,13,16] in the paper) -  namely, using Llama and Mistral models – allowing us to compare our methods with previously published benchmarks. We made this choice for replicability purposes and so our findings can be compared with existing published work. Note that our watermarks target all application scenarios, so we did not adopt LLMs designed specifically for coding. \n\n---\nReference: \n[R1] Fairoze, Jaiden, et al. \"Publicly-Detectable Watermarking for Language Models.\" IACR Communications in Cryptology 1.4 (2025)."}, {"review_id": "f5RMx1v61n", "reviewer": "Reviewer_udiS", "summary": "This paper proposes a minimax optimization framework for large language model watermarks. It aims at maximizing watermark effectiveness while minimizing text distortion under low-entropy constraints. This work designs two watermark methods, SimplexWater and HeavyWater, derived from the optimization framework. The former is a binary-score watermark that achieves the optimal detection gap, based on the observation that the minimax problem could be formulated as designing codewords with maximal Hamming distances. The latter is a generalized continuous-score watermark that samples watermark scores from heavy-tail distributions to improve watermark detectability. Experimental results show that the proposed methods achieve better performances in terms of effectiveness-distortion trade-off than existing LLM watermarks.", "questions": "- Is it possible for an adversary to mount reverse-engineering or spoofing attacks by observing token frequencies of SimplexMark or HeavyMark, especially under the uniform i.i.d. assumption?\n- How do SimplexMark and HeavyMark perform (in terms of downstream task metrics) on low-entropy generation scenarios, such as code generation (pass@k) and math reasoning (accuracy)?\n- How do the proposed methods perform against more advanced watermark removal attacks?\n- Another question following the previous one on robustness: could robustness be potentially integrated into the optimization formulation as an objective?\n- Could this optimization framework or the two proposed methods be potentially extended to multi-bit watermarking?\n\nA few other minor issues:\n\n1. Markov-1, Product, h=4, Sum, h=5 in Figure 3(b) is not defined in the main text (although the definitions could be found in the appendices).\n2. Some figure titles seem to be inconsistent. E.g., in Figure D.13, do \"Coding\" and \"LCC\" refer to the same dataset (LCC)?", "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\n+ This paper proposes a unified optimization framework for LLM watermarks. The optimization framework includes watermark effectiveness, text distortion, and low-entropy constraints, and would help provide theoretical insights into LLM watermarks.\n+ This paper further proposes two concrete watermark implementations under the proposed framework. Both watermarks are distortion-free and could work under different settings.\n+ Apart from empirical results, the two implementations also contribute to additional theoretical insights: SimplexWater establishes connections between the watermark framework and coding theory; HeavyWater shows that continuous-score watermarks could benefit from sampling from heavy-tail distributions.\n\n**Weaknesses**\n\n- **The i.i.d. requirement for the side information might be restricted in real-world scenarios**. It would add to the difficulties of sharing the secret information between the watermarker and the detector, and might lead to vulnerabilities against reverse engineering. For example, the authors mention in the appendix that a counter and a secret key are used to generate the i.i.d. side information. In this case, the watermark behavior is only tied to the i-th token's position (i.e., the counter value). Each token at the same location would have similar watermark behavior, regardless of the context. Consequently, the watermark might be vulnerable to reverse engineering, where an adversary queries the watermarker multiple times and counts word frequencies at each position to infer high-score watermark tokens. Nonetheless, the authors do mention this in the limitation section and include results using more realistic non-i.i.d. side information. While the empirical results are promising, some of the theoretical analysis might not hold in non-i.i.d. cases.\n- **Additional tasks and metrics for low-entropy generation could be included to further evaluate generation quality**. While this paper features low-entropy watermarking, the evaluation for low-entropy generation is limited to code generation (on the LCC dataset), and the main performance metric for generation quality is limited to the estimated Cross Entropy. While indeed additional metrics are included in the appendices, they mostly focus on general text generation tasks rather than low-entropy ones. Hence, it would be more convincing if the evaluation could be extended to include more low-entropy tasks and metrics (e.g., pass@k on code generation or accuracy on math reasoning, etc.).\n- **The robustness evaluation does not consider stronger removal attacks**. The watermark removal attacks have mainly focused on rather primitive attacks, such as changing cases and adding typos. Other attacks, such as word substitution, copy-paste attacks, or paraphrasing, could also be included for a more comprehensive evaluation. This is a rather minor issue since robustness is not the primary focus of this work.", "was_revised": true, "final_justification": "I would like to thank the authors for their detailed response and clarifications, including the additional results on low-entropy generation, the clarification on spoofing attacks, as well as the sketches on incorporating attack channels and multi-bit watermarking. The responses have addressed most of the concerns.", "rebuttal": "Thank you for your comments and positive review!  We address your questions next and highlight additional results in the Supp. Material (SM). Please note that we included in Appendix D.2 experiments on the impact of non-i.i.d. side information on SimplexWater and HeavyWater, additional robustness results in Appendix D.3, and reported alternative performance metrics in Appendix D.5. We also provide new results on code generation metrics below. \n\nWe are happy to answer any follow-up questions you may have!\n\n---\n### **W1, Q1:The i.i.d. requirement for side information restricted (…) While empirical results are promising, theoretical analysis might not hold in non-i.i.d. cases.  Is it possible for an adversary to mount reverse-engineering or spoofing attacks (..) under uniform i.i.d. assumption?** \n\nThanks for bringing this up. Our theoretical results indeed assume i.i.d. side information, as mentioned in lines 208-218. Importantly, we address this issue head-on by evaluating our watermarks’ performance against several methods for non-i.i.d. side information generation in App. D.2. \n\nIn App. D.2, we benchmark different side information generation methods based on hashing previous tokens – min-hash, sum-hash, prod-hash, and Markov-1 – extending beyond counter-based approaches. As shown in Fig. 3(b), both SimplexWater and HeavyWater outperform Red-Green in terms of detection under a range of non-i.i.d. side information generation methods. Fig. D.7 in the SM indicates that varying the number of preceding tokens used to generate side information has minimal effect on both text quality and detection of our watermarks. Figure D.8 shows that both Markov-1 and prod-hash-4 achieve detection performance very close to that of i.i.d. (fresh) randomness. These results show that SimplexWater and HeavyWater maintain detection accuracy and text quality under non-i.i.d. side information, comparable to the i.i.d. setting.\n\nRegarding the question on the possibility of adversarial attacks under i.i.d and non-i.i.d side information: if the side information $S$ is uniform i.i.d. and generated fresh for each token and across prompts, then, it is **not** possible for an adversary to mount any reverse-engineering or spoofing attack. Here’s why: the optimal transport (OT) optimization that is solved for each token results in a coupling between the (uniform) side information distribution $P_S$ and the next token predictions $P_X$. This coupling *ensures* that the marginal distribution of next-token predictions **remains exactly the same**. Consequently, an adversary that only observes tokens $X_1,\\dots,X_n$ will not observe any statistical deviation from the original model’s distribution since, on average across $S$, samples are still drawn from $P_X$. Thus, it is **information theoretically impossible** for an adversary (no access to $S$) to distinguish between the unwatermarked and watermarked distribution. \n\nThis breaks under non-i.i.d. Assumptions. As the reviewer points out, in the extreme non-i.i.d. case where $S$ is deterministic for a given token position, an adversary could spoof the watermark by querying the model multiple times.\n\nCurrent watermarks aim for an intermediate solution. For instance, side information is generated using previous tokens, secret keys, and hashing (potentially with salt), resulting in side information that is non-i.i.d., but not deterministic. Non-i.i.d side information generation impacts the robustness and security of watermarking schemes – not only ours, but also of all other competing methods, such as SynthID, Gumbel, Inverse Transform, and Red-Green. This was one of the main motivations in our choice to taxonomize watermarking into three different components in lines 130–149, namely (i) randomness generation, (ii) randomness use, and (iii) watermark detection, and optimize for the last two components assuming ideal randomness generation. This assumption enables a tractable theoretical analysis, leading to new information-theoretic performance bounds (Thms 1, 2, and 4).\n\n---\n### **W2, Q2: Additional tasks and metrics for low-entropy generation could be included.**\n\nThanks for pointing this out. We do have additional text quality evaluation metrics in **Appendix D.5** and **Table D.2**, where we consider four additional datasets from **WaterBench [41]** along with either **ROUGE-L and F1 scores for textual quality**. These results show that our watermarks maintain strong detection performance without compromising text generation quality.\n\nDuring the rebuttal, we also computed additional generation metrics targeted towards code generation tasks (reported below). We will highlight these results in the main paper. \n\n**New experiments:** Below, we report additional tasks and metrics for low-entropy generation in coding. We include a new coding experiment using the **HumanEval dataset [44]** and evaluate it with **pass@K with k=1,5,10** generation metric, using Llama2-7B as the baseline. For LCC code completion tasks, since human-written codes are used as the ground truth, we use Edit_Similarity as the generation-quality metric. Under both Edit_sim and pass@k, our methods have no significant impact on the quality of generated code relative to unwatermarked code, and perform favorably when compared to competing methods. Below, we give two tables with the results. \n\n**Task 1: Code generation - Generating code for a given task using HumanEval dataset and evaluate with pass@k**\n\n#### **Results on HumanEval Functional Coding Dataset**\n| Watermark Scheme           | pass@1(%) **↑** | pass@5(%) **↑** | pass@10(%) **↑** |\n|----------------------------|------------------|------------------|-------------------|\n| No Watermark               | 14.0             | 20.7             | 28.1              |\n| **HeavyWater (Ours)**      | **13.1**         | **18.9**         | **27.8**          |\n| Gumbel                     | 14.3             | 20.5             | 25.6              |\n| **SimplexWater (Ours)**    | **13.7**         | **22.7**         | **25.3**          |\n| Inverse Transform          | 13.8             | 22.0             | 27.5              |\n| Red/Green $\\delta=3$       | 11.6             | 19.5             | 23.2              |\n\n\n**Task 2: Code completion - Auto-complete a given code snippet using LCC dataset and evaluate with Edit_Sim**\n\n#### **Results on LCC Code Completion Dataset**\n| Watermark Method       | Edit_Similarity **↑** |\n|------------------------|----------|\n| No Watermark          | 0.45     |\n| Gumbel                 | 0.52     |\n| **HeavyWater (Ours)**              | **0.52**     |\n| **SimplexWater (Ours)**            | **0.44**     |\n| Inverse Transform                 | 0.45     |\n| Red/Green $\\delta=3$     | 0.43     |\n\n---\n### **W3, Q3, Q4: More advanced watermark removal attacks. Integrate robustness into the optimization objective.**\n\nCurrently, we have tested our watermarks on misspelling attacks, typo attacks and case-change attacks in Appendix D.3, benchmarking their performance against competing watermarks with comparable detection rates. We select these attacks since they are the standard in the MarkMyWords benchmark [42]. Fig. D.9 shows that our methods result in superior/comparable performance with respect to existing watermarks under the above attacks. \n\nAlthough robustness is not the main focus of this work, we consider the theoretical analysis of watermark robustness – particularly under complex attacks such as copy-paste and paraphrasing – to be an important future direction which we are actively exploring. We can incorporate robustness into our framework by modeling edits and other perturbations explicitly. Right now, we treat the problem as finding an optimal tilted next-token distribution $P_{X|S}$​, considering the worst-case $P_X$. To capture robustness, we can introduce an additional channel $P_{Y|X}$​ that describes how an adversary might transform each token X into a perturbed token Y (e.g., typos, paraphrasing, etc). With a suitable model for $P_{Y|X}$​, we can then choose $P_{X|S}​$ to maximize the worst case  $E_{P_{X,S}} ⁣[f(Y,S)]−E_{P_XP_S} ⁣[f(Y,S)]$. This formulation would allow us to optimize the watermark while explicitly accounting for robustness under perturbations, albeit at the cost of a more involved mathematical analysis.\n\n---\n### **Q5: Extend the optimization framework to multi-bit watermarking**\n\nYes – this is an area that we are also exploring. A natural way to extend the proposed watermarks from single-bit to multi-bit is to assign random, independent side information strings to each of the $n$ messages. Denote the string corresponding to message $i$ as $S_i=[S_i^{[1]},...,S_i^{[k]}]$. To embed $S_1$, the watermarker applies SimplexWater/HeavyWater by using $S_1^{[t]}$ as the side information at token instance $t$. Note that the marginal distribution of the next token remains the same as the (original) next token distribution of the LLM as each $S_1^{[t]}$ is sampled independently at random, which maintains the distortion-free property. Based on the $f(X,S_1^{[t]})$ scores, the detector arrives at a high true positive rate (for detecting $S_1$) as a consequence of the high detection performance of SimplexWater/HeavyWater. The false positive rate remains small (assuming that n is not significantly large) as each $S_j$ is independent of S_1, which results in smaller scores for $f(X,S_j)$ for all $j\\neq1$. The gain in false positives due to multi-bit watermarking can be bounded by applying a union bound to our existing results.\n\n---\n### **Q6: Minor issues.**\n\nThanks for the helpful feedback. We will bring the definitions to the main text from App. D.2. Yes, “Coding” and “LCC” refer to the same dataset. We will clarify this in the revised version."}, {"review_id": "i8U3Fsn6cU", "reviewer": "Reviewer_3Nda", "summary": "The paper considers the important problem of LLM watermarking in the case of low-entropy regimes such as in coding tasks. In particular, the question of high detectability with low distortion is tackled and two algorithms are proposed by invoking connections to coding theory and optimal transport. Experiments validate the approaches on various LLMs and settings.", "questions": "(1) Is there a performance metric for the quality of the generated code? Are there sample outputs for the coding tasks before and after watermarking?\n(2) How easy is it to scrub/spoof the approach? Also, how robust is it various types of attacks such as substitution, deletion, and addition of tokens?", "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": "Overall, the paper is very interesting and introduces novel ideas in the watermarking literature.\n\nPros: \n\n(A) In the case of binary score functions, a connection to the coding theory is made and shown to be minimax optimal. This encompasses the popular red-green settings.\n(B) For score functions which are continous, a framework is introduced to tackle this settings and includes the popular Gumbel approach but beats it in performance.\n(C) In both settings, they are adequately supported by theoretical results and quite a few experimental results.\n\nCons:\n\n(i) The watermarking schemes target detectability and low-entropy regimes but it is unclear how they perform along the robustness and security angle.\n(ii) The performance metrics are limited to detection and distortion, and downstream utility metrics of the generated code are not presented.", "was_revised": true, "final_justification": "Based on the engagements with the authors as well reviewing the discussions, I maintain my score.", "rebuttal": "Thank you for the thoughtful comments and the positive feedback. Below, we address the four points raised in your review (two weaknesses and two questions). Please note that we included **additional robustness results** for **HeavyWater** and **SimplexWater** in **Appendix D.2** of our Supplementary Material (SM). Our SM also includes additional results on the impact of watermarking on the quality of generated text (**Table D.2** in SM). Finally, we also provide new results on how **HeavyWater** and **SimplexWater** impact generated code. We present the answer to your first question (Q1) at the end of our response, since it includes a code snippet and a table.\n\nWe would be happy to answer any additional questions or comments.\n\n---\n\n### **W1: Robustness and security** and **Q2: \"How easy is it to scrub/spoof the approach? Also, how robust are various types of attacks such as substitution, deletion, and addition of tokens?\"**\n\nThanks for the question! In our SM (**Appendix D.3**), we evaluated the robustness of our watermarks by considering three types of attacks that involve modifying characters or words: **Lowercase attack**, **Misspelling attack**, and **Typo attack**.\n\nWe selected these attacks based on the **MarkMyWords benchmark** (reference [42] in the paper). In **Figure D.9**, we report the detection power (as measured by p-value) of **HeavyWater** and **SimplexWater** post-attack, and compare it against the **Gumbel** and **Red-Green** watermarks. These results demonstrate **equal or superior detection** of **HeavyWater** relative to competing baselines under these attacks. We will highlight these results in the main paper.\n\n**Robustness Analysis**\n\nThe robustness of most watermarking schemes (including ours) is tied to how random side information is generated (please see the discussion in **Appendix A.1** and **A.3** of the SM, particularly line 1017). Note that both **HeavyWater** and **SimplexWater** are agnostic to side information generation, in the sense that they can be paired with any hashing scheme (e.g., computing S based on hashes of previous tokens and a secret key). \n\nConsequently, we also evaluated the performance of our watermarks under different hashing strategies and reported the results in **Figure 3b** and **Appendix D.2** of the SM (**Figures D.7** and **D.8**). These results show that the performance of our watermark is **consistent across an array of hashing schemes and context window sizes**, including **min-hash**, **sum-hash**, **prod-hash**, and **Markov-1 scheme**.\n\n**Security Guarantees**\n\nSecurity guarantees of watermarks also stem from the properties of the side information generation procedure (i.e., how $S$ is generated). This is because, under the assumption that the watermarking strategy is public, the primary source of secrecy is the shared information used to generate the side information $S$ (see **Appendix A.1** in SM). Our watermarks can be incorporated with different seeding strategies (see **Appendix D.2**). Consequently, their security guarantees will stem from whichever side generation backbone is being used.\n\nSide information generation can potentially be optimized to prioritize security by leveraging **cryptographic mechanisms** for randomness generation and key sharing. This is an interesting and important direction of future work, and we are aware of recent work from the cryptography community that explores these aspects [56]. In our paper, we focus instead on how to **optimally** use random side information to maximize detection and minimize distortion. We recognize the importance of side-information generation in our limitations section (line 208), and will include this discussion about security in an expanded future work section.\n\n---\n\n### **W2: \"Lack of performance metric beyond detection and distortion; downstream utility metrics of the generated code are not presented\"**\n\nWhile the main paper focuses on the **detection–distortion tradeoff**, we do report additional generation quality metrics to evaluate the utility of the generated text, as detailed in **Appendix D.5**. In **Table D.2**, we assess the impact of watermarking on generation quality across four additional tasks from **WaterBench [41]**: **LongformQA**, **Multi-news Summarization**, **Knowledge Memorization**, and **Knowledge Understanding**.\n\nFor these, we report **ROUGE-L scores** (LongformQA and Multi-news) and **F1 scores** (Knowledge Memorization and Knowledge Understanding). As shown in **Table D.2**, our methods (**SimplexWater** and **HeavyWater**) maintain competitive detection performance across all datasets, with a generation metric **comparable to unwatermarked text**. Together, these results provide significant evidence that our watermarks **preserve output quality** in textual tasks.\n\nWe agree that utility metrics should also be emphasized for the code generation tasks used in the main paper. To that end, we are reporting two additional metrics, **Edit Similarity** and **Pass@K**. See our response to Q1 below for detailed information. We will highlight these more clearly in the revised version.\n\n---\n\n### **Q1: \"Is there a performance metric for the quality of the generated code? Are there sample outputs for the coding tasks before and after watermarking?\"**\n\nThanks for the suggestion! We introduce **two performance metrics** to evaluate the quality of generated code:\n\n#### 1. **Edit_Sim (Edit Similarity)**\n\nWe use this metric on the **LCC coding dataset [41]**, which focuses on code completion: generating the next few lines of code given a long context. Since the dataset is sourced from GitHub, human-written ground-truth completions are available. **Edit_Sim** measures **Levenshtein similarity** between generated and ground-truth code. A formal definition will be included in **Appendix D**. We benchmark our watermarking methods against prior work using this metric, and **HeavyWater achieves the highest Edit_Sim score** for the code completion task.\n\n#### 2. **pass@k**\n\nTo complement Edit_Sim and better evaluate the successful execution of watermarked code, we also report results on the **HumanEval dataset [44]**, which is a popular benchmark for code generation. Since LCC is not suitable for pass@k (as it does not contain standalone problems and unit tests), we use HumanEval to measure **pass@k with k ∈ {1, 5, 10}**, where we execute the generated code against unit tests provided in the dataset in a sandbox environment. As shown in the results table, **SimplexWater achieves the highest score on pass@5**, while **HeavyWater performs best on pass@10**. In all cases, performance is **comparable to unwatermarked code**.\n\nThese two metrics support that **HeavyWater** and **SimplexWater** have **no significant impact on the quality of generated code** relative to unwatermarked code, and perform favorably when compared to competing methods both in terms of detection accuracy and generation quality.\n\n#### **Results on LCC Code Completion Dataset**\n\n| Watermark Method | Edit_Similarity ↑ |\n|------------------|-------------------|\n| No Watermark | 0.45 |\n| Gumbel | 0.52 |\n| **HeavyWater (Ours)** | **0.52** |\n| **SimplexWater (Ours)** | **0.44** |\n| Inverse Transform | 0.45 |\n| Red/Green δ=3 | 0.43 |\n\n#### **Results on HumanEval Functional Coding Dataset**\n\n| Watermark Scheme | pass@1(%) ↑ | pass@5(%) ↑ | pass@10(%) ↑ |\n|------------------|-------------|-------------|---------------|\n| No Watermark | 14.0 | 20.7 | 28.1 |\n| **HeavyWater (Ours)** | **13.1** | **18.9** | **27.8** |\n| Gumbel | 14.3 | 20.5 | 25.6 |\n| **SimplexWater (Ours)** | **13.7** | **22.7** | **25.3** |\n| Inverse Transform | 13.8 | 22.0 | 27.5 |\n| Red/Green δ=3 | 11.6 | 19.5 | 23.2 |\n\n#### **Code Examples**\n\n#### Unwatermarked Output:\n\n```python\ndef has_close_elements(numbers: List[float], threshold: float) -> bool:\n    # Sort the list of numbers\n    numbers = sorted(numbers)\n    # Find the first two numbers in the list that are closer to each other than the threshold\n    min_distance = float('inf')\n    for i in range(1, len(numbers)):\n        distance = abs(numbers[i] - numbers[i - 1])\n        if distance < min_distance and distance < threshold:\n            min_distance = distance\n    # If we found a pair of numbers that are closer to each other than the threshold, return True\n    return min_distance < threshold\n```\n\n**Unit Tests result:** Pass → **Pass@1=100%** on this example prompt.\n\n#### HeavyWater's Watermarked Output:\n\n```python\ndef has_close_elements(numbers: List[float], threshold: float) -> bool:\n    close_pairs = []\n    for i in range(len(numbers)):\n        closest = None\n        closest_distance = float(\"inf\")\n        for j in range(i+1, len(numbers)):\n            distance = abs(numbers[i] - numbers[j])\n            if distance < closest_distance:\n                closest = numbers[j]\n                closest_distance = distance\n        if closest and closest_distance <= threshold:\n            close_pairs.append((numbers[i], closest))\n    return len(close_pairs) > 0\n```\n\n**Unit Tests result:** Pass → **Pass@1=100%** on this example prompt."}, {"review_id": "cr01ysosig", "reviewer": "Reviewer_dQ8C", "summary": "This paper aims to design LLM watermarks that are effective even in low-entropy conditions. They model watermarks as modifying the distribution of each token in the response using some side information (for example, in the Kirchenbauer et al. scheme this side info is the output of the hash function). To do so, they formulate constructing a good watermark as an optimization problem which essentially involves maximizing the expectation of the score function applied to the response and the actual side information, and minimizing the expectation of the score function applied to the response and independent side information. This gap in expectations arises because the watermark modifies the response to be correlated with the side information.\n\nThere are two important choices this paper considers in instantiating such schemes: the score function, and the way in which the watermark modifies the distributions. The way in which the watermark modifies the distributions is derived from the score function, using Sinkhorn’s algorithm. This paper takes constructing the side information to be outside its scope. This paper proposes two instantiations of the scheme: HeavyWater and SimplexWater. SimplexWater uses a binary simplex score function rooted in coding theory. HeavyWater is an improved version of SimplexWater that uses a continuous score function. The schemes also include a tunable parameter that controls how much distortion the watermark introduces.\n\nIn addition to proving properties of the proposed schemes, this paper shows empirically that their detectability out-performs existing schemes, especially on coding models.", "questions": "- How computationally expensive is the watermark generation algorithm/Sinkhorn’s algorithm?\n- In Figure 3(b), what is being measured on the y-axis? It is labeled “improvement,” but under what metric is this improvement?\n- The experiments seem to focus on two kinds of tasks: Finance-QA (Q&A) and LCC (coding). There are many other low-entropy scenarios, though. What evidence do you have that your watermark performs well in low-entropy scenarios in general?", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n- This paper nicely formalizes the problem of constructing a good watermark in terms of an optimization task. It then shows that solving this problem yields practical watermarks.\n- This paper has both theoretical and empirical evidence for the effectiveness of the watermark.\n- The paper is clearly written.\n\nWeaknesses\n- The watermark scheme involves solving a *different instance* of an optimization problem to determine how to modify the distribution of each token in the response. In practice, this seems like it would be quite expensive. In contrast, existing schemes involve changing each distribution according to a simple rule, such as increasing the probabilities of tokens on a green list. \n- Due to the above, the paper should include more discussion about the efficiency of the proposed scheme.\n\nOverall, the paper shows a nice theoretical perspective on the task of watermarking. This perspective yields (seemingly) practical schemes that perform well empirically, in certain low-entropy settings. Since low-entropy settings have posed a challenge to watermarks, this contribution has good significance if the schemes are truly practical (see question about efficiency below). The quality seems reasonable, and the paper is reasonably clear. The main question I have is about efficiency.", "was_revised": true, "final_justification": "This paper nicely formalizes the problem of constructing a good watermark in terms of an optimization task. It then shows that solving this problem yields practical watermarks.\n\nThe authors' rebuttal assuaged my primary concern, which was efficiency. The watermark involves solving an optimization problem when generating each token. As the authors point out, this optimization problem is over the next-token distribution (importantly, not the model itself). Therefore, this complexity does not grow as the model grows. So for larger models, this optimization cost becomes small compared to the cost required to run the model.\nIt would be great to see more of this efficiency discussion in the final paper.\n\nThe authors also included many experiments addressing the generality of the scheme in performing well in many low-entropy scenarios. They raised my attention to these in the rebuttal.\n\nOverall, this is an interesting theoretical formulation of a practical problem, with practical applications. I recommend acceptance.", "rebuttal": "Thank you for the thoughtful review and encouraging feedback! We address your comments and questions below, including those related to efficiency and entropy. Please note that computational overhead measurements were included in our Supplementary Material (Appendix D). These results show that the computational overhead of our watermark implementation is comparable to existing watermarks. We discuss these results below and will highlight them in the main body of the paper. \n\nWe are happy to answer any follow-up questions you may have.\n\n---\n### **Q1 and Weaknesses: Efficiency of the algorithm. “How computationally expensive is the watermark generation algorithm/Sinkhorn’s algorithm?”**\n\nWe compared the computational overhead of our watermarking algorithms (which involve OT/Sinkhorn iterates) against several popular watermarks, including Red-Green, Gumbel, Inverse-Transform, and SynthID. The results are included in Appendix D.4 and Figure D.10 of our Supplementary Material.  \n  \nTo summarize, we reported that schemes with closed-form watermarked next-token distributions (including Red-Green, Gumbel, and Inverse-transform) have a generation overhead of approximately 10% in the Llama2-7B model. Methods that equire some optimization to watermark the next-token distribution – including Deepmind’s \\textit{SynthID} and our’s SimplexWater and HeavyWater – incur a higher overhead of approximately 30%, with SynthID incurring the highest cost across all methods.\n\nWe highlight that this overhead cost is relative to the generation time of a Llama2-7B model. This relative overhead will be **significantly amortized** for larger models, as the watermarking computation time **remains constant regardless of model size** (it is a logit post-processor), whereas the next-token computation time increases.\n\n---\n### **Q2: Figure 3(b) y-axis metric for improvement**\n\nIn Figure 3(b), we measure the improvement of SimplexWater and HeavyWater’s detection power relative to the Red-Green watermark [15]. Specifically, we measure detection improvement in terms of percentage drop of p-value $\\frac{(-\\log(p)\\_{\\text{RedGreen}}) - (-\\log(p)\\_{\\text{Ours}})}{-\\log(p)\\_{\\text{RedGreen}}}$. This figure illustrates that our watermarks consistently demonstrate higher detection power compared to Red-Green across a range of hashing schemes for generating side information. \n\n---\n### **Q3: Beyond Finance-QA (Q&A) and LCC (coding), “what evidence do you have that your watermark performs well in low-entropy scenarios in general?”**\n\nGreat question! In **Appendix D** in the Supplementary Material (D.5 Experiment: Alternative Text Generation Metrics), we reported the performance of our watermarks on **four additional datasets** used in WaterBench [41]: LongformQA, Multi-news Summarization, Knowledge Memorization, and Knowledge Understanding. We emphasize that the favorable performance of our watermarking schemes is supported by both our theoretical analysis and our experiments. Next, we summarize the theoretical guarantees and practical evidence that demonstrate the effectiveness of our watermarks in low-entropy scenarios. \n\n**Theoretical Performance Guarantees.** Our theoretical guarantees imply favorable watermarking performance in low-entropy scenarios. Note that, by entropy we mean *min-entropy*: $H= -\\log_2 \\max_x P(x)$, where $P$ is the next-token distribution. *Low-entropy* refers to next-token distributions whose average entropy $H(P) \\leq 1$ bit/token (see lines 166-173 and 223 of the paper). In the low-entropy regime, at least one predicted token has a probability greater than $\\frac{1}{2}$. \n\nThe ‘low-entropy’ constraint used in our analysis is not merely a theoretical assumption. It is based on the empirical observation that LLMs’ next-token distributions are **inherently low entropy,** as shown in our measurements reported in the Supplementary Material (Appendix C.1). From these measurements (Figures D.14 and D.15  – see also [52, Fig.1] for further evidence), over 85% of next-token predictions satisfy $H(P)\\geq 0.95$, and over 90% satisfy $H(P)\\geq 0.5$  for practical temperature values. Consequently, the vast majority of next-token predictions fall well within the regime considered in our theoretical analysis – which proves optimality guarantees for $H(P)\\geq 0.5$. We observed similar patterns in the additional datasets we tested. **Even though coding, Q\\&A, and summarization tasks are commonly understood as having varying degrees of ‘entropy’ – with coding assumed to have lower entropy – we still observe $>90\\%$ of next-token predictions across these tasks falling well within the low-entropy considered in our theoretical analysis.**\n\nOur theoretical results give provable performance guarantees for the low-entropy regime. Theorem 1 and Theorem 2 in the main text prove that, in the low-entropy regime, SimplexWater is minimax optimal across all binary score watermarks. In other words, SimplexWater maximizes the binary per-token detection score for the worst-case distribution that satisfies the low-entropy constraint. For real-valued scores and randomly generated score functions, we demonstrate that watermarking in the low-entropy regime depends on the tail of the score distribution. This allows us to generalize the Gumbel Watermark (Theorem 3) and propose HeavyWater – which provably improves upon the Gumbel watermark (Theorem 4). \n\n**From Theory to Practice and Empirical Measurements:** Please note that, in addition to the Q\\&A and LCC datasets included in the main paper, we report performance of our watermarks on **4 additional datasets in the Supplementary Material:** longform Q&A, knowledge memorization, knowledge understanding, and multi-news summarization (see Appendix D.5 and Table D.2). Our watermarks demonstrate better or comparable performance across all datasets tested, as reported in Table D.2.\n\nIn summary, by focusing our **theoretical analysis on the low-entropy regime** $H(P)\\leq 1/2$, we derive **new watermark designs with provable optimality guarantees, namely SimplexWater and HeavyWater**. The low-entropy assumption (lines 166-173) is reflected in practice, with **over 90% of LLM next-token distributions across Q&A, coding, and summarization tasks satisfying this constraint** (Supp. Material Figures D.14 and D.15) per our measurements. HeavyWater and SimplexWater display favorable performance on the LCC and Q\\&A datasets used in the main text, as well as on four additional dataset benchmarks reported in our Supplementary Material (Appendix D.5 and Table D.2). The combination of theoretical guarantees and empirical benchmarks together provides significant evidence that our watermarks perform well in low-entropy regimes."}]

Author rebuttal:

Meta-review: This paper designs LLM watermarks for challenging low-entropy text by framing the task as an optimization problem. The goal is to maximize the watermark's detection signal by correlating the output with random side information, while simultaneously minimizing distortion to the original text. This framework yields two new, tunable watermarks: SimplexWater, which uses a binary score function rooted in coding theory, and HeavyWater, which uses a more flexible continuous score. Through both theoretical analysis and empirical experiments, the paper shows these methods achieve better detectability compared to existing schemes, particularly in low-entropy scenarios like code generation.

The paper's primary strength is how it nicely formalizes the problem of constructing a good watermark as an optimization task. This perspective is not only very interesting, but it also generalizes and improves upon popular methods. Solving this optimization problem yields two practical watermarks, HeavyWater and SimplexWater. The effectiveness of these methods is supported both in theory and in experiments. The latter was made stronger in the rebuttal when the authors added results on key downstream metrics like pass@k, demonstrating that the watermarks preserve the functional quality of generated code.

The most significant initial concerns centered on computational efficiency and the practical impact on generated code. However, the authors effectively addressed these by clarifying that the per-token optimization overhead is constant and becomes negligible for large models. The paper's focus is on detectability and quality and lacking on robustness to attacks, which is okay but something that should ideally be analyzed in a watermarking paper. Simple attacks like typos are studied, but not more sophisticated ones like rewrites or word subsitutions. Similarly, the theoretical analysis relies on an idealized i.i.d. assumption for side information, though the authors' experiments show the methods still perform well with more realistic randomness.
Decision: Accept (poster)