WaterMax: breaking the LLM watermark detectability-robustness-quality trade-off

Authors: eva  giboulot
teddy  furon
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 14:30:46

Abstract: Watermarking is a technical means to dissuade malfeasant usage of Large Language Models.
This paper proposes a novel watermarking scheme, so-called WaterMax, that enjoys high detectability while sustaining the quality of the generated text of the original LLM.
Its new design leaves the LLM untouched (no modification of the weights, logits or temperature).
WaterMax balances robustness and  computational complexity contrary to the watermarking techniques of the literature inherently provoking a trade-off between quality and robustness.
Its performance is both theoretically proven and experimentally validated.
It outperforms all the SotA techniques under the most complete benchmark suite.

Main paper: 
 introduction: 
 The availability of powerful large-language models (LLMs) allows users to produce texts that look like human writings. The risk for misuse of these models is critical, ranging from the impersonation of individuals to the large-scale generation of fake news. Identifying the provenance of a given piece of text is paramount to limit the impact of such 'weaponization' of LLMs. New initiatives or regulations impose technical means for AI traceability [28, 9, 5] .Forensics passive methods generally leverage a priori knowledge about the statistics of texts generated by a given class of LLMs [34, 27] . Despite their versatility, these methods offer low performance. The reported probabilities of errors are only validated empirically on some datasets, and because of this, they are never lower than 10 -3 [14] .In contrast, active methods like watermarking are only limited by the fact the LLM owner must integrate the watermarking within the generation processes. This is done by embedding an imperceptible signal in the generated text, which can be retrieved by a detector sharing the secret key of the model owner. Current watermarking methods for generative texts [22, 1, 23, 8] provide low and guaranteed false positives rates. Yet, the trade-off between the detectability and the text quality crucially depends on the entropy of the text to be generated, which in turn depends on the prompt and the LLM, as illustrated in Fig. 1 . This implies that the distortion-free property [1, 23, 8] ensures that watermarking does not degrade text quality but inherently limits the detectability. This paper presents WaterMax, a watermarking technique that trades off robustness not for quality, but for complexity. It obeys the regular constraints found in the literature: it can be integrated into any standard LLM without fine-tuning the weights, the detection does not need the original LLM, and it can spot the watermark on a slice of generated text with some guarantee on the false positive rate. Our contributions are the following:• WaterMax is based on a new design not relying on the usual mechanisms of the literature; especially, it keeps the next token distribution and sampling (temperature and method) intact. Moreover, it better utilizes the text entropy by working over sub-sequences of tokens, so-called chunks hereafter, rather than token by token.• This new design makes WaterMax almost distortion-free, as shown experimentally (Sect. 7.3) and justified theoretically (App. H), and yet enjoys higher robustness than the state-of-the-art, consistently over several LLMs. Figure 1 shows that the other methods need to boost the watermark strength to be as detectable as WaterMax, inevitably degrading the quality.• This new design facilitates building up a theoretical model of the watermark robustness characterizing the true positive rates under attack (see Prop. 5.2). 
related work: 
 Watermarking texts generated by LLMs is mainly performed by changing either the distribution [21] or the sampling [1, 23, 8] of the next token. Critically, the false-positive rate of these methods can be reliably controlled [11] . Furthermore, the computational cost of most of these methods is negligible relative to the text generation itself. On the other hand, they all suffer from similar weaknesses:Text entropy limit Some theoretical works [8, 17, 21, 1] show that the watermark detectability is highly dependent on the entropy of the text to be generated. In practice, this makes the text length necessary for reliable watermark detectability dependent on the type of the text, and also the LLM.One may increase the watermark strength or the temperature in the LLM to increase the entropy artificially [19, 26] . Both solutions degrade text quality compared to the original LLM.Distortion-freeness and quality Kuditipudi et al. [23] define that a watermark is distortion-free if it does not modify the probability distribution of the next token on average over the keys. This is guaranteed in schemes like [1, 23, 8 ]. Yet, these schemes rely heavily on the entropy of the token distribution, leading to possibly low detectability without any means to increase it without losing distortion-freeness. Appendix J illustrates the dependence of Aaronson's scheme on the original LLM. Moreover, a scheme that is not distortion-free does not necessarily lead to texts with lower empirical quality, but foreseeing the impact of the watermark strength on the quality is an issue.The watermark must resist text editing ranging from a simple insertion of words to a complete paraphrasing of the text. At the time of writing, there are only two watermarking schemes designed from the ground up to be robust [23, 35] . Yet, other state-ofthe-art methods have experimentally shown resiliency to attacks against long-form texts [29] under a precise control of the false-positive rate [11] . However, none of these methods can theoretically guarantee its robustness. Only bounds on the moments of the detection score are provided in [21] and [1] . The advantages are that the text quality is not degraded and that any sound detection may be used. The price to pay is high complexity and long latency. Suppose that a text is deemed watermarked if its p-value evaluated by the detector is lower than the required false alarm probability P F A . This raises the question of the number n of generated texts for successfully embedding the watermark. Proposition 3.1. The detectability measured by the power of the test, i.e. the probability P D of detecting a watermarked text is the following increasing function w.r.t. n: P D ≜ P(P < P F A |H 1 ) = 1 -(1 -P F A ) n .(EQUATIONAppendix B gives a sketch of the proof. We point the reader to two important advantages:• The performance does not depend on the choice of score function used to obtain the p-value.• The performance does not depend on the length of the text. Consequently, even an extremely small text can be watermarked in theory.Figure 2 plots the power of the test as a function of n for various probabilities of false alarm. Whatever the choice of P F A , one can clearly observe that a huge number of generated texts (≫ 50) is required to obtain a power greater than 0.5, which is unacceptable in practice. Section 4 shows how to improve this base algorithm to reach arbitrarily high power with a smaller computational power.Another weakness is the assumption that the LLM can create n texts whose p-values are independent. For some prompts, the diversity (i.e. entropy) is indeed small, which implies that the LLM creates similar texts or even duplicates of text among the n outputs. Section 6 investigates how selfsynchronization mitigates this issue. 
watermarking chunks of text: 
 This section devises ways to efficiently explore the space of possible texts to find a low p-value. The idea is to split the generation into N iterations, each iteration creating a chunk of the text. The aim is to reduce the computational burden by generating small chunks while exploring many possible texts.For each chunk, a batch of n text drafts is generated independently based on the text candidates of the previous iteration. Ideally, one would generate n drafts at each chunk for each previous candidate, resulting in a tree of n N texts from which to choose the lowest p-value. Obviously, this is not tractable. We reduce the complexity by keeping only the m best candidates at each step, akin to a Viterbi algorithm [33] . The pseudo-code is summarized in Alg. 1 in App. F. This is suboptimal because the candidates minimizing the p-value at a given step may not be the best once completed at iteration N . Other exploration strategies range from greedy search to Monte Carlo Tree Search [6] .The pseudo-code is summarized in Alg. 1 within Appendix F.This paper considers detection schemes that share the following process. The vocabulary V is a list of |V| admissible tokens, and a text is decomposed into a sequence of L tokens. Depending on the secret key k, the detection associates to the i-th token a variable u i . The score is computed as the sum over the tokens s = L i=1 u i . This is translated into a p-value assuming that, under H 0 , i) the scores of the tokens are independent and identically distributed random variables (U i ) L i=1 , giving birth to a random score S, ii) whose c.d.f. F S (•; L) is known so that the p-value is simply:EQUATIONAppendix A lists some detection schemes of the literature following this procedure. Our choice is simplyU i iid ∼ N (0; 1) so that F S (s; L) = Φ(s/ √ L).For the sake of clarity, suppose that the chunks are composed of ℓ tokens. At iteration i, the j-th candidate has a score denoted s i,j and n drafts for its following chunk are proposed. This produces n incremented scores per candidate, thus mn variables:s i,j + δs i,j,k , 1 ≤ j ≤ m, 1 ≤ k ≤ n.Since these scores are converted into p-values by the same function, i.e. p = 1 -F S (s; ℓ(i + 1)), selecting the m lowest p-values amounts to keep the m maximal cumulative scores, hence the name WaterMax.One issue is the latency: the final text cannot be issued until all candidates reach an end of sequence. This problem is fixed with the drastic choice m = 1. It amounts to a greedy search appending to the text at iteration i the chunk draft yielding the biggest incremental score δs i,1,k . This choice enables the output of a chunk of text at the end of each iteration, hence reducing latency. Of note, this also corresponds to the draft with the lowest local p-value 1 -F S (δs i,1,k ; ℓ).This section introduces a simple detector to reveal the advantage of our watermark embedding. The idea is that the received text is composed of chunks whose local p-values are distributed as beta distributions B(1, 1) (i.e. U [0, 1] ) under H 0 or B(1, n) under H 1 (see Appendix. B). This is a generalization of the algorithm of the previous section, the only difference being that the likelihood EQUATIONProposition 4.1. The optimal detector Λ opt has the following performances when there is no attack:EQUATIONwhere γ x,y is the lower incomplete gamma function with shape parameter x and scale parameter y.Appendix C gives a sketch of the proof. The power of the test P D is an increasing function of n. Again, note that neither the token variables distribution nor the chunk length s affects the detectability.Figure 3 illustrates the efficiency of our exploration strategy of the text space. Contrary to Sect. 3, we can easily reach a power close to 1 even at P F A = 10 -6 . For example, using N = 9 chunks of n = 15 drafts, assuming a medium-size text of L = 512 tokens and chunks of equal length, one only needs to generate N n = 135 chunk drafts of ℓ = ⌈L/N ⌉ = 57 tokens to obtain a power of 0.96. This is equivalent to generating 15 texts of size 512. This is to compare to Sect. 3 where more than 3 million texts of 512 tokens are necessary to reach this power at P F A = 10 -6 . 
robust watermark detection: 
 Until this point, our detector assumed that the text it receives is the generated text. Yet, before reaching the detector, a text might have been modified for legitimate or malicious reasons: it may be translated, curated, locally modified etc. This section assumes that the scores of individual tokens are distributed as standard Gaussian random variables to allow the derivation of closed-form solutions.Detector (3) is neither optimal nor robust under attack because the insertion or the removal of tokens provokes a desynchronization: The detector no longer knows where each chunk starts and ends, which is necessary for computing the local p-value of individual chunks. More robustness comes with a global score simply summing up over all the tokens:EQUATIONProposition 5.1. The robust detector has the following test performance when there is no attack:EQUATIONwhere e(n) (resp. v(n)) is an increasing (resp. decreasing) quantity computed in Tab. 1.Appendix D gives a sketch of the proof. Figure 3 shows that the robust test ( 5) is slightly less powerful than the optimal test (3) when there is no attack. On the other hand, the next section shows that its power degrades smoothly under attacks contrary to (3).Despite the variety of modifications that can be performed on a watermarked text, all attacks have the same end effect: modifying the tokens and potentially the number of tokens. This amounts to modifying a proportion of scores to be distributed following H 0 instead of H 1 in the global score. Formally, the score Λ rob (U) for a text of L tokens becomes: (assuming αL is an integer)EQUATIONwhere 1α is the proportion of scores impacted by the attack whose variables are denoted { Ūi }, and π 0 (resp. π 1 ) is mapping to the indices of the untouched scores (resp. modified tokens). It is important to note that it does not matter if the size of the attacked text differs from the generated text.Proposition 5.2. The robust detector has the following test performance under attack:EQUATIONAppendix E gives a sketch of the proof. In the end, the power of the test decreases smoothly with the strength (1α) of the attack. Once again, the power of the test does not depend on the text size.Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? 
independence: 
 This section discusses the assumptions made so far on the independence of the token and draft scores.All random variables (U i ) associated with tokens must be independent and identically distributed within a text. This assumption has an impact on the power of the test and especially on the probability of false alarm. It must hold for non-watermarked text. Otherwise, the score of a chunk (or of a full text) is not properly normalized into a p-value.We use the same technique as in [11] to enforce the token variable independence: the variable U i of the i-th token of a text depends not only on the secret key but also on the hashing of the current token and the h -1 previous tokens in the text (a window of size h). Furthermore, this h-gram is appended to a list. If the h-gram is already stored in that list, the variable of the current token is discarded. By doing so, we ensure that for a given text, the (U i ) are always different. Contrary to [11] , this mechanism is enforced at the generation and the detection stages to ensure that both sides compute the same score.At the embedding, the scores of the n drafts of a chunk are assumed to be independent. Yet, some correlations occur when parts of texts repeat across different drafts. For example, in a prompt asking "Who are you?", many drafts of the first chunk of the response likely start with "I am." This assumption only plays a role in the power of the detector, not its false-positive rate.Causal hashing window At first sight, hashing the whole chunk draft for seeding each token variable brings draft score independence if the drafts differ at least by one token. Sadly, this creates a watermark that breaks even for a single modified token. This forces us to use a causal window: the score of each token depends only on itself and the previous tokens. The longer the hash window, the more likely a h-gram is new and the more diverse the scores. Yet, this diversity is obtained at the cost of robustness. Indeed, changing a single token in a text removes the watermark of h tokens because their variables depend on the modification. Another weakness: at a given iteration, the j-th token (j < h) of every draft always refers to the same hj tokens since the previous chunk is identical for all these drafts. This means that the effective window size for this token is always smaller than h.Beam-searched enforced diversity This weakness can be tackled by modifying the sampling procedure. It is important to guarantee a high diversity at the beginning of the chunk since this is where the effective window size is the smallest. We propose to generate the first b tokens using a standard beam-search procedure, which deterministically returns n different beginnings of the chunk. The rest of the draft is sampled normally. However, there is a trade-off. The smaller b, the more diversity between the chunks and the closer to the independence assumption we get, the more likely the beam-search procedure selects tokens in the tail of the distribution (for a large enough number of drafts n), the poorer the text quality.For the independence of the score variables, the experiment runs the detector on 100k Wikipedia entries from 2018 for ten different keys. Since the text of Wikipedia is free of any watermark, one should observe the p-values to be uniformly distributed, i.e. the empirical false alarm rate should match the theoretical probability of false alarm. Figure 4a demonstrates that this assumption holds for any window size h. On the other hand, the robustness highly depends on the hashing window size, with h = 6 being a good trade-off between performance and robustness.The second experiment measures how much we deviate from the draft score independence assumption. It generates 296 texts of 256 tokens on the three tasks from [29] . The entropy of the generated texts may be low for a given chunk so that some parts of a text may be redundant among the drafts. Figure 4b reports how much our scores under H 1 deviate from the theoretical distribution.This experiment demonstrates that the closer to 1 the number of tokens generated by beam search b, the closer the scores match the theoretical distribution. Notice that even for a large b, such as b = 6, there is a large improvement compared to a baseline WaterMax with b = 0. In Appendix I, we provide a more thorough experimental study of the parameters h and b. In particular we show the trade-off between quality and detectability. In the rest of the paper, we select b = 4 where a small loss of quality is acceptable and b = 6 if a virtually lossless scheme is warranted.7 Experiments 
experimental protocol: 
 The evaluation is performed on the three long-form creative writing tasks of the 'Mark My Words' benchmark [29] : news article generation, summarization of existing books, and writing of an invented story. This leads to the generation of 296 texts. We fix the maximum text size L to 256 tokens for all tasks (see App. K for larger text sizes). The length of a chunk ℓ is fixed a priori to L/N where L is the maximum number of tokens allowed in the benchmark and N the number of chunks.All the evaluations in this section use the model Llama3-8b-Instruct [32, 3] (more models are tested in App. J). Its temperature θ varies to measure the impact of the text entropy on the watermark detectability. The watermarking scheme is not allowed to modify θ compared to the original LLM.The evaluation of a watermarking scheme is based on three quantities: 1) the quality of the watermarked text relative to the non-watermarked text, 2) the detectability, and 3) the robustness.For KGW and Aaronson's scheme, we use the implementation provided by [11] at https: //github.com/facebookresearch/three_bricks. For the attack suite, we use the implementation of the 'Mark My Words' benchmark found at https://github.com/wagner-group/ MarkMyWords.Text quality A number of metrics have been proposed to evaluate the quality of generated watermarked texts empirically. We tested the vast majority of these metrics: rating by LLM [29] , similarity between BERT's embeddings [11] , MAUVE [30] , ROUGE [25] and perplexity measured by an oracle [21] . We arrived at the conclusion that perplexity and ROUGE-L are currently the only reliable measures of watermarked text quality -in the sense that they are the only ones that consistently vary alongside watermark strength. This section reports the relative perplexity as measured by opt-2.7b as an oracle, computed as the average ratio between the perplexity of a watermarked text and the corresponding non-watermarked text. The text quality is evaluated by comparing the text generation with and without watermarking at the same LLM temperature θ.Detectability The increasing use of LLM necessitates the use of small false-positive rates. In this section, we settled on reporting the true-positive rate at a conservative false-positive rate of 10 -6 . For a more complete picture, Appendix K also reports the median false-positive rate of each watermark algorithm at different text lengths, akin to the measure of "watermark size" recently proposed in [29] .Robustness We use the attack suite of the 'Mark My Words' (MMW) benchmark [29] . We report robustness by measuring the detectability P D of the watermark at P F A = 10 -6 for each attack.Error bars are reported using one standard error for perplexity, using the standard methodology, and detectability, computed using 5000 bootstrap samples for power at P F A = 10 -6 .The recent MMW benchmark considers four techniques names as 'binary' [8] , KGW [21] , Aaronson [1] and 'inverse transform' [23] . It concludes that today's best methods are KGW and Aaronson, we thus restrict our comparisons to them. Except when specified otherwise, the watermark schemes all use a window size of h = 6 for hashing.A fair comparison considers watermarking schemes at an equivalent level of text quality. Aaronson's scheme is theoretically distortion-free and experimentally almost lossless with respect to empirical relative perplexity and the ROUGE-L score. We should ideally tune WaterMax and KGW such that they are also almost lossless. This is not a problem for WaterMax as long as the number of tokens generated by a beam-search b is small enough. We choose the setting (N, n) = (16, 10) , which provides a good compromise between robustness and complexity. As for KGW [21] , we fix δ = 2.0 for an acceptable loss of quality, or δ = 3.0 for a tangible loss of quality. This gives a clear advantage to KGW. We set its green-list ratio γ = 0.5 following the recommendation of Piet et al. [29] .Quality vs detectability Figure 5 summarizes the benchmark outcomes. They confirm that Water-Max achieves a detectability close to the theoretical prediction -in our case close to 1 at P F A = 10 -6 -while, at the same time, incurring a minimal loss in text quality. In particular, for a number of tokens generated by beam-search b = 6, there is virtually no observed loss in terms of perplexity. Furthermore, its performance is independent of the temperature of the LLM, demonstrating the efficient use of the entropy by working on chunks instead of individual tokens. On the other hand, Aaronson's scheme achieves high detectability only for high temperatures (seldom used in practice), whereas KGW achieves high detectability at the price of a text quality loss: at δ = 3.0 despite a relative perplexity significantly larger than WaterMax, KGW is still far less detectable.Robustness Figure 6 summarizes the results for the attack suite of the MMW benchmark. The watermark parameters are fixed to ensure the most negligible quality loss possible: b = 6 for WaterMax and δ = 2.0 for KGW. Without many surprises, no algorithm can resist the powerful re-translation attacks at this P F A regime since most words, as well as their order, are modified. The 'typos' attacks can safely be disregarded as they modify every token and make the text barely legible in practice. This leaves the attacks that modify only parts of the text. For low temperatures, WaterMax is by far the most robust. Notably, the robust detector (5) can resist far more attacks, with significantly higher detectability against 'synonym', 'misspelling' and 'swap' attacks.Interestingly, for temperatures starting at 1.0, Aaronson's scheme is more robust than WaterMax for specific attacks. This is explained by the high reliance of this method on entropy as we show in Appendix J as well as the high variance of its p-values. Given enough entropy, some portions of the watermarked text present unusually low p-values, statistically leading to more robustness. On the other hand, WaterMax produces texts with p-values that are more concentrated around their mean. At face value, the computational cost of our scheme is nothing more than N n text generations, the computation of the scores being negligible. However, the cost of adding one more chunk is higher than the cost of generating one more draft. Indeed, the n drafts of a chunk are sampled independently (or by a beam search), making their computation highly parallelizable on modern GPUs. On the other hand, we cannot parallelize the computations over the chunk. Since N has the highest impact on the power of WaterMax, it is the main limiting factor for its performance.See Figure 7 for experimental running times. As a rule of thumb, we advise to use parameters fixed as (n, N, b) = (10, 16, 6) as good trade-off between computational complexity and detectability. This still incurs a high cost compared to classic watermarking schemes. Under these settings, a text generated with WaterMax takes on average five times longer to generate than KGW or Aaronson's scheme.However, despite a higher total computational cost, the latency can be kept relatively low since the text is generated chunk by chunk. Each chunk can be delivered to the user gradually (e.g. using a buffer) in order to make the method practical in a real-life setting. Note that more chunks lead to lower latency and better detectability with a negligible cost to text quality. We report, under the same settings, the generation time for one chunk as a measure of latency in Figure 7 . In particular, we show that under the advised parameters, the latency of WaterMax is only twice as long as that of the original LLM. 
conclusion: 
 Contrary to previous art, the design of WaterMax starts from a detector and then constructs the generator to maximize the detection power. As a result, our watermark scheme offers a host of compelling benefits. It achieves high quality and robustness even on short texts, and importantly, it does not modify any component of the LLM, preserving its integrity and functionality. This design also complies with common add-ons in the literature, like adapting the sampling temperature [19] or embedding short messages [11] .These advantages come at the cost of computational complexity, which stays limited thanks to the exploration strategy and the parallelization possibilities of modern GPUs. Another idea left for future work is the distillation of WaterMax, a process that involves fine-tuning an LLM to natively produce watermarked text. This would definitively get rid of the only drawback of WaterMax. 
 
 Appendix: This section describes the detection of the three main LLM watermarking schemes. They share the same process:• The received text is decomposed into a sequence of, say L, tokens• A sliding window of size h forwards the selected tokens to a cryptographic function which computes a hash that is xored with the secret key to compose the seed of a Pseudo Random Number Generator• The variable u i is computed for the i-th token, i > h based on the output of the PRNG seeded by the h previous tokens• The score is the sum of the variable:s = L i=h+1 u i • The score is converted into a p-value: p = 1 -F S (s; L).The watermark embedding methods are not detailed because our scheme does not use them. This summary is inspired by the work of Fernandez et al. [11] .For the detection of [22] , the output of the PRNG is used to create a 'green' list which is a subset of V of size γ|V|. Variable U i is set to 1 if the i-th token belongs to this list, otherwise U i = 0. Therefore, under H 0 , U i iid ∼ B(γ) and S follows a binomial distribution B(Lh, γ). This makesEQUATIONwhere I is the regularized incomplete Beta function.For the detection of [1] , the output of the PRNG is used to draw U i iid ∼ E(1) so that S is Gamma distributed under H 0 . This makes:EQUATION)where Γ is the upper incomplete gamma function. This formulation also holds for [8] with the reduction to binary alphabet |V| = 2.For the detection of [23] , the output of the PRNG is used to draw U i whose distribution matches the distribution of the product of two independent r.v.U([-1/2, 1/2]), i.e. F U (u) = 2u(1 -log(4|u|)) + 1/2.There is no closed form to turn the global score into a p-value. The authors use either a bound (see their Lemma 2.4) or an empirical p-value computed by a costly Monte Carlo simulation with random seeds. This is the reason why this studies [23] fixes the probability of false alarm to a relatively large value, i.e. 10 -2 .Since Sect. 4.4 shows that the distribution of U i has no impact, we opt for the simple choice U i iid ∼ N (0; 1) and the p-value reads as:EQUATIONNumerous works have proposed improvements of the KGW and Aaronson's scheme. We herein describe some relevant works and their applicability to the WaterMax framework.KGW Variants Improvements to KGW can be broadly categorized into two classes: modification to the sampling mechanism and improvements to the bias assignment. Some recent works modifying the sampling mechanism are: [36] which propose to complement baseline KGW with contrastive search to improve text quality as well as inserting a second watermark, [18] uses a multi-objective optimization procedure to conserve the semantic coherence of the watermarked text Works on better bias assignments include: [15] which propose to cluster tokens which are semantically related and assign similar biases to them in order to resist re-translation attacks, [7] builds the green and red list using a similar clustering method, [26] adapt the bias depending on the entropy of the current completions in order to improve detectability and text quality. Note that any watermarking methods relying on modifying the biases could directly be used by WaterMax as a score function as long as a p-value can be computed from them. Similarly any modified sampling method could also be applied as long as they can output different texts from the same prompt.Aaronson's scheme variants Most work dealing with improving on the Gumbel-trick of Aaronson's scheme are not explicitly variants but other algorithms with the distortion-free property, or methods to improve on the ad-hoc detector of the original work. Noteworthy distortion-free algorithms include the 'binary' [8] 'inverse transform' [23] methods, the latter which actually includes a variant of Aaronson. The work in [10] is notable for being an asymmetric (somewhat fragile) watermark.Though technically presented as a variant of KGW, one of the proposed method in [16] can be interpreted as variant of Aaronson working on group of tokens. Finally, [24] proposes an improved score function for Aaronson through the design of a general statistical framework.Extensions to multi-bit watermarking Even though this work is solely concerned with zero-bit watermarks, we note that some works have proposed mechanisms to extend current text watermark methods to multi-bit versions, allowing for example the identification of specific users. Of note, [11] have proposed a general mechanism applicable to every current zero-bit method by associating a key to every possible message and designing an efficient detector through a circular shift of the keys, [31] extends KGW to multi-bit using BCH and error-correcting codes.Watermark distillation To this we add an important work from Gu et al. [13] , especially relevant for WaterMax, showing the possibility to directly train a LLM to generate watermarked text using either watermarked samples or directly the token distribution. Since the only real cost of WaterMax is the computational complexity of sampling chunk of texts, distilling WaterMax would allow to bypass the sampling cost entirely.The main ingredient of our scheme is a watermark detection that outputs a p-value for any text input, whatever its length. This is the case for the main works in the literature, like [1, 21, 8] and to some extent [23] (see App. A). Of note,• In theory, for a continuous score S, the p-value P computed from a random non-watermarked text is uniformly distributed over [0, 1] with p.d.f. f (p|H 0 ) = 1 [0,1] (p).• In practice, the computation of the p-value can be hazardous on texts with repetitions of token sub-sequences and Fernandez et al. [11] indicate how to fix this issue.For a given prompt, the generator creates n independent texts, each with possibly a different number of tokens, computes their p-values P j iid ∼ U [0,1] , and outputs the text with the minimum p-value. Note that in order for the p-value to follow a uniform distribution under H 0 , we assume the c.d.f of the scores to be continuous. A well-known results in statistics states that the minimum of n independent p-values follow a beta distributionB(1, n) whose p.d.f. is f (p|H 1 ) = n(1 -p) n-1 .The detector receives an unknown text and decides between two hypotheses:• H 0 : The text is not watermarked. The p-value has not been 'minimized' and follows the uniform distribution. • H 1 : The text is watermarked. Assuming no attack was performed, the p-value is distributed as a minimum of n independent uniform variables. We assume the detector knows the value of n.Since the distributions under both hypotheses are known, the detector performs a simple test, and the Neyman-Pearson lemma states that the most powerful test under a given probability of false-alarm P F A is the (log) likelihood-ratio test:EQUATION)where τ is a threshold which depends on P F A . In our setting, Λ (p) = (n -1) log(1p) + log(n), which is a monotonic function of p. In other words, comparing p ≶ H1 H0 P F A is equivalent to the Neyman-Pearson test. The power of the test is defined as the probability of detecting a watermarked text and turns out to be an increasing function w.r.t. n:EQUATION)C Proof of proposition 4.1The optimal detector (3) aggregates a vector p of N observed local p-values:EQUATION)The received text is composed of chunks whose local p-values are distributed as beta distributions B(1, 1) (i.e. U [0,1] ) under H 0 or B(1, n) under H 1 when there is no attack (see Sect. B). Knowing that if X ∼ B(1, β) thenlog(1 -X) ∼ E(β), Λ(P) is the sum of independent exponential r.v. and thus follows a Gamma distribution under both hypothesis but with different parameters:EQUATION)This leads to the characterization of the test's performance:EQUATIONEQUATIONwhere γ x,y is the lower incomplete gamma function with shape parameter x and scale parameter y.Assume the received text is composed of N chunks of ℓ tokens each so that its total number of tokens L = N ℓ. Under H 0 , the token variables are independent and normal distributed so that Λ rob (U) ∼ N (0; L). It is thus easy to find the threshold τ ensuring a probability of false alarmP F A : τ = - √ LΦ -1 (P F A ).Under H 1 , Λ rob (U) can be written as the sum of N independent chunk scores:EQUATIONi . These chunk scores are distributed as the maximum of n Gaussian variables N (0; ℓ), corresponding to the score of the drafts. Those maxima have the c.d.f.F M (n) (x) = Φ x/√ ℓ n and one can compute numerically the expectation E(M (n) ) = √ ℓe(n) and the variance V(M (n) ) = ℓv(n), see Tab. 1. As far as we know, there is no closed-form for these quantities, but classical results in concentration inequalities for the maximum show that e(n) scales as log(n) and v(n) as 1/ log(n) [4] .An approximation for N large enough is Λ rob (U) ∼ N (µ 1 ; σ 2 1 ) withEQUATIONEQUATIONThis gives the following power of the test: This section derives the distribution of variables of individual tokens under H 1 .EQUATIONWe first express the distribution of a vector of L i.i.d. normal variables, given that their sum equals a given value S:EQUATIONwith 1 L the vector of all ones in R L and I L the identity matrix of dimension L × L.The attacks leaves αL variables untouched (assuming 0 ≤ α ≤ 1 and αL ∈ N). This is encoded in a matrix A ∈ {0, 1} αL×L which selects these variables. This means that A has exactly one single entry equal to 1 in each row, AA ⊤ = I αL , and A1 L = 1 αL .The sum of these αL variables can be written as 1 ⊤ αL AU. This makes:EQUATIONThis distribution is independent of A: It does not matter which tokens are left unchanged. For α = 1, there is no attack and the variance is null because1 ⊤ αL AU = 1 ⊤ L U = s.For α = 0, the attack has modified all the token variables and the variance is null because 1 ⊤ αL AU = 0. According to App. D, an approximation for N large enough is S ∼ N (µ 1 ; σ 2 1 ). The law of total variance givesEQUATIONOn top of this, the attack adds (1α)L tokens distributed under H 0 , which amounts to add a noise distributed as N (0, (1α)L) to the above score. In the end, the global score is distributed asEQUATIONWe thus obtain an approximate expression of the power of the robust test:EQUATION)Observe that, once again, the power of the test does not depend on the size of the text. More precisely, it does depend indirectly on it given that α can only take a finite number of values, the number of which decreases with the size of the text. For example, if the text is composed of L tokens, α ∈ {0, 1/L, . . . , 1 -1/L, 1}.Note that this analysis is general in the sense that it does not depend on the existence of an attack at a given α resulting in an acceptable quality. We believe the role of the watermark designer is to ensure the highest possible detectability whatever the strength of the attack; the design of attacks preserving text quality is the burden of the attacker. An analysis of the robustness of a watermark should thus be comprehensive, providing the performance of the watermark under any possible type of attacks, existing or not, and independent of text quality.Input: prompt pr, parameters (N, n, m, ℓ), p-value computation Detect, LLM Generate Initialize: We report the running time averaged on 5 texts of 256 tokens generated using Llama-2-chat-hf at temperature 1.0 and nucleus sampling (top p = 0.95) for different parameters in Figure 8 .x j = [], ∀1 ≤ j ≤ m for i = 1 to N do for j = 1 to m do context = [pr∥x j ] for k = 1 to n do ν = n(j -1) + k y ν = Generate(context, ℓ) p ν = Detect([x j ∥y ν ]) end for end for (ν 1 , • • • , ν m ) =Overall, generating the 296 texts of the 'Mark My Words' benchmark on a single A100, with maximum batch-size, takes approximately 6min for Aaronson and KGW. For WaterMax at (n, N, b) = (10, 16, 6) , it takes approximately 30min. The resource usage report of the cluster used to run the experiments, taking into account both CPU and GPU cores, indicates a total use of 5024 core hours.This appendix elaborates a theoretical model to justify why WaterMax is close to distortion-freeness.Consider a given iteration of WaterMax where one particular draft among n is selected as the output chunk. Denote the set of possible chunks by C. If the chunks are all composed of ℓ tokens, then |C| = |V| ℓ . Each chunk c i ∈ C has a probability p i to be sampled by the LLM. We denote by pi the probability that WaterMax selects this chunk. This probability is computed on expectation over the set of secret keys.A watermarking scheme is distortion-free if pi = p i , ∀p i ∈ [0, 1] . This appendix shows this is not the case for WaterMax. Yet, since we operate on chunks, i.e. sequences of tokens, and not individual tokens, their probabilities are small in practice. In this regime, we show that pi ≈ p i , which theoretically justifies the high text quality.This version of WaterMax samples n drafts in C. This corresponds to draws with replacement because a draft can be sampled several times.Denote by X i the number of times the ith chunk is drawn over n samples. It follows the binomial distributionX i ∼ B(n, p i ), ∀i ∈ {1, . . . , |C|}.Denote by Y i the binary random variable s.t.Y i = 1 if X i > 0. It follows the Bernoulli distribution Y i ∼ B(1 -(1 -p i ) n ), ∀i ∈ {1, . . . , |C|}.Denote by S the subset of chunks which have been sampled, i.e. S = {c i : Y i = 1} ⊂ C. The size of this set is a random variable ranging from 1 to n and whose expectation isE(|S|) = |C| i=1 Y i = |C| - |C| i=1 (1 -p i ) n .For a given watermark secret key, i.e. a given instance of the token variables {U j } |V| j=1 , WaterMax computes the score of each draft in S, and it chooses the one with the maximum score. Over the ensemble of secret keys, there is no reason why a given draft is more likely to be chosen due to the symmetry of the random token variables. Therefore, a draft in a given subset S has a probability 1/|S| to be chosen on expectation over the secret keys. This yields the following global probability:EQUATION)Upper bound The above summation includes the subset S = {c i } which happens with probability p n i . For all the other subsets, which include c i , |S| ≥ 2. This gives an upper bound:EQUATION)Lower bound The above summation can be written as pi = n k=1 S:Xi=k1 |S| P(S). When X i = k, there are at most nk other unique sampled chunks: |S| ≤ nk + 1. This makes the following lower bound:EQUATION)Remarks Note that pi = p i , ∀p i ∈ [0, 1] when n ∈ {1, 2} because the lower and upper bounds correspond to the identity. The choice n = 1 is not an option since it corresponds to the regular use of the original LLM without watermarking. The choice n = 2 allows watermarking with the distortion-free property. The price to pay is a low robustness.For n > 2, WaterMax is not distortion-free. Indeed the upper bound (27) is lower than p i for p i > 1/2 showing that pi does not equal p i on the interval (1/2, 1). However, note thatEQUATION)This property explains why WaterMax reaches text quality as good as other distortion-free watermarking schemes. WaterMax works with chunks of text whose probabilities are all very small, contrary to other schemes working on tokens which sometimes have a picky distribution (one token gets almost all the probability mass). Therefore, missing the distortion-free property for large p i is irrelevant because this case never happens in practice when dealing with chunks. On the contrary, having pi ≈ p i locally for p i → 0 is key.This version of WaterMax samples n drafts in C making sure that they are all different thanks to the beam-search suggested in Sec. 6.2. This corresponds to draws without replacement because a draft cannot be sampled twice. In other words, |S| = n. Equation ( 26) simplifies to:EQUATIONHowever, the probability P(c i ∈ S) is cumbersome to calculate as it relates to the multinomial Wallenius noncentral hypergeometric distribution. When all the chunk probabilities are very small, one can show that [12] :EQUATION)The same rationale as above applies: WaterMax is not distortion-free but tends to this property when all the chunks have small probabilities. This is what happens in practice when working with long chunks.Section 6 discusses how the window hashing size h as well the number of tokens generated by beam-search b can help to increase detectability. Both parameters, however, lead to a trade-off. First, a higher h provides better detectability when no attack is performed on the text but makes the watermark less robust since modifying one token leads to at most h scores, which become unusable. Secondly, a lower b > 0 leads to better detectability by enforcing diversity between chunk drafts, at no cost to robustness, but at the cost of text quality since the beam-search has more chance of selecting tokens in the tail of the distribution. Note that b = 0 corresponds to the baseline WaterMax, which is empirically lossless.To select the best trade-off, we generate 296 texts of 256 tokens following the same protocol described in Sect. 6: we use Llama-3-8b-Instruct with temperature θ = 1.0, nucleus sampling (top p = 0.95), and WaterMax at (n, N ) = (8, 16) . We report the results in Fig. 9 -11.From Figure 9 -10, we see that the most significant improvement in the trade-off detectability vs. quality is by going from b = 0 to b = 6. This is done at almost no cost to the text quality. A larger gain in detectability is obtained for 1 ≤ b < 6 but with a significant loss of quality.Regarding the window size, h = 2 leads to a weak scheme. An acceptable performance, close to P D = 1.0 at P F A = 10 -6 without attack, requires h ≥ 4. However, Figure 11 reveals that a close match to the theoretical score distribution under H 1 is only reached for h = 6. PD@PFA = 10 -6 (→ better) h = 2 h = 4 h = 6This appendix studies the impact of the LLM on the watermark performance. As we alluded to numerous times, the performance of the watermark of KGW and Aaronson is highly dependent on the entropy of the completion of individual tokens. This dependence is well-illustrated by the impact of temperature on their performance. However, this also means that we can expect vastly different behaviors of these schemes depending on the LLM used since, depending on how the LLM was trained and fine-tuned, the average entropy of the completions varies wildly.To demonstrate this point, we repeated the experiments in Sect. 7 for two other models: the older Llama-2-7b-chat [32] and the smaller Phi-3-mini-4k-Instruct [2] (3.8 billion parameters). We report the results, along with those of Llama-3-8b-Instruct in Figures 13 14 15 .The performances of both KGW and Aaronson are abysmal on Llama-2-7b-chat, with extremely low detectability, even for a high δ for KGW. At the opposite end, every algorithm performs well on Phi-3-mini-4k-Instruct. However, once again, KGW still incurs a high cost in terms of text quality, whereas WaterMax b = 6 and Aaronson are both virtually lossless at this regime. Llama-3-8b-Instruct sits in between these two extremes.To understand these results and verify our claim with regard to entropy, we generated 64 × 100 completions using each model. Fig. 12 reports the distribution of their entropy. Very clearly, the entropy follows our observation, with Phi-3-mini-4k-Instruct having the highest average entropy whereas Llama-2-7b-chat has the lowest with a lot more tokens which are close to being deterministic. This is an essential observation for watermark evaluation since different schemes are better suited to different LLMs. However, WaterMax is currently the only scheme that consistently attains almost perfect detectability at P F A = 10 -6 irrespective of the LLM, of the temperature, and at almost no cost to text quality. This section reports more results of interest to the practitioner to tune their watermark of choice. In particular, we report different quality metrics by varying the watermarking parameters. We also study the impact of text size on the detectability of watermarks.In this appendix, the experiments are based on three MMW tasks defined in [29] , namely:• generating 100 fictional news articles,• generating 100 reports on well-known books,• generating 96 stories given a synopsis.All texts are generated using Llama-2-chat-hf with nucleus sampling (top p = 0.95). The hashing window is fixed to h = 4 for all algorithms. WaterMax is used with b = 0 (no beam-search), which entails a virtually lossless scheme. Every watermarking scheme, except for Aaronson's, is applied on a LLM working at temperature θ = 1.0.Figures 16a-17c report the relative perplexity using opt-2.7b as an oracle as well as the ROUGE-L score for Aaronson, KGW, and WaterMax as a function of their respective parameter. Recent works have proposed using LLM judges to evaluate the quality of watermarked texts. Some examples include the Mark My Words benchmark [29] which directly uses Llama2 as a judge for evaluating watermark quality. Several open-source proxies fine-tuned for this task have been recently proposed in the literature such as Prometheus [20] .Yet, our use of these models for evaluating the quality of watermark texts has not proven fruitful. We provide the results of using Llama-2-7b-chat, Mistral-7b-instruct-v0.2 and Prometheus-7b-v2.0 as LLM judges of the text quality in Fig. 18 of the global response. We asked each of these LLM to grade out of 5 the texts of the "Invented Stories" task of the Mark My Words benchmark following the methodology of [20] , using the code provided in the official Github's implementation.• The grading is inconsistent between LLMs, with Prometheus-7b biased towards higher grades and Llama-2-7b-chat towards lower. Note that the ranking of each watermark is different for each LLM judge. Furthermore, grading can be inconsistent even for nonwatermarked texts, with Mistral-7b-instruct-v0.2 highly biased in favor of non-watermarked texts generated with temperature 1.0.• The average grade does not fluctuate significantly for different watermark strengths, whatever the choice of LLM judge. Interestingly, Fig. 18 shows that increasing δ can slightly increase the LLM grading, which should not be the case.• This prompted us to study the grading of barely legible texts, by randomly replacing a percentage of the characters within texts: LLM judges still provide similar average grades despite this attack. More precisely, the grade starts to degrade when the texts starts to look like random strings (around 15% of modified letters). However, there is no impact to the grading for, i.e a percentage of 10%. Here is an example of text with a maximum grade of 5/5: "sir edward, a chivWlrous knight, had always been driGen by a sense of duty and a thiFst foD SdventuFe. as a yLung man, hW had heard tales of the legendary holy graiP, said to grant the deepest desJreD of FhoWe who posseZsed it. convinced tUat thS grail helX the keT to bringing pFace and prosperity tK hiD kingdLK, sir Wdward set out on a perilLus quesY to find it. he bSgaJ his jouTnFy in the miDty mountaiMs of wales, where he souFht [...]"Our conclusion is that, as of writing, these LLM judges don't seem suited to the evaluation of watermarked texts quality. As explained in the paper, we prefer the relative perplexity and ROUGE which fluctuate as expected with watermark strength. We generate texts of a maximum size of L = 1024 tokens. For such long texts, the detectability easily reaches P D ≈ 1.0 if fixing P F A = 10 -6 . Instead, we fix a detectability of P D = 0.5 and compute the corresponding p-values. This metric is close to the definition of 'watermark size' defined by Piet et al. [29] . The advantage of this metric is that we can report an increase in watermark performance even for long texts as p-svalues tend to decrease substantially with text size. PFA@PD = 50.0% Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?EQUATIONAnswer: [Yes]Justification: The settings of the LLM and watermark parameters are provided in full in Section 7 as well as in appendices.Guidelines:• The answer NA means that the paper does not include experiments.• If the paper includes experiments, a 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 a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable. • Depending on the contribution, reproducibility can be accomplished in various ways.For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it 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 a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. , 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 to describe the particular way they provide for reproducibility.In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.Justification: A full repository of the code used for the experiments is provided as well as the exact commands to replicate them.Guidelines:• The answer NA means that paper does not include experiments requiring code. • If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration 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: The potential positive impact of watermarking methods is touched upon in the introdutcion of the paper. No negative impact is apparent to us. Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • 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.38th Conference on Neural Information Processing Systems (NeurIPS 2024). 


Decision: This paper proposes a new LLM watermarking scheme, WaterMax, which achieves high detectability while maintaining the quality of generated text. The performance of WaterMax is theoretically proven and experimentally verified. LLM watermarking is a less-regarded but interesting research topic. The proposed watermarking scheme is novel, and the theoretical analysis and experimental evaluation are thorough. The paper is generally well-written. In the rebuttal stage, the authors addressed most of the issues raised by the reviewers. The next version needs to properly report the complexity overhead and latency of the scheme.

Reviews: review: paper_summary: paper_summary: The work proposes a new LLM watermarking scheme called WaterMax, that does not modify the distribution or the sampling procedure but uses rejection sampling on multiple generated segments of tokens to cause a high watermark score. A theorem is given to characterize the detector power under attack, given certain independence assumptions. The experiments attempt to demonstrate superior detectability under the constraint of high quality, independent of the temperature/entropy, as well as superior robustness.
strength_weakness: strength_weakness: - **Questionable experimental evaluation**: The experimental setup of the main experiments (Figure 5) is mostly reasonable and the observation about the instability of Aaronson holds up. However, the key claim seems to be that "KGW used with common/realistic settings is both of lower quality and has lower detectability than WaterMax". I have several observations here. 
1) This claim is made by observing 1.2x relative perplexity measured with a weak 3B model; it is not clear that this is a reliable estimate of text quality in pratical use-cases (see e.g. https://arxiv.org/pdf/2312.02382). The result would be more convincing if a larger model was used, but more importantly, a SOTA LLM (e.g. GPT4) was used as a judge of responses in at least one setting. The author's claim regarding this is ambigious, are they claiming that GPT4 is unreliable for this task? 
2) The watermarked model itself is a single 8B model. I see two more small models in Appendix J (7B and 4B). On Llama2-7B the variants of KGW that were tried actually have /higher/ quality that WaterMax, so it is not clear if increasing delta would significantly ruin quality but it may lead to high TPR. Regardless, at least one larger model (e.g., 13B) should in my opinion be tried to substantiate the claim.
3) Even in Fig. 5 a non-standard variant of KGW is used with h=6 and gamma=0.5. To make the claim stronger, can the authors repeat the experiment with more standard h=4 and with gamma=0.25 as well? 

- **High computational cost**: while the authors acknowledge this explicitly to some extent, no quantifiable measurement of the computational cost is shown in the main paper, and the appendix suggests that the full experiment took 5x more with WaterMax. This clearly makes WaterMax inapplicable in most real deployments where latency is critical. 

However, despite the 5x slowdown, I still believe the paper would have sufficient merit as an exploration of an interesting idea, if the authors could fill the gaps in the experimental evaluation and make the case regarding quality vs power fully convincing. My current borderline accept score is conditioned on the authors providing these additional results to remove my doubts.
questions: questions: - Is GPT4 unreliable for the task of judging text quality? Can you provide empirical evidence?
- Can you repeat the main experiment with any model larger than 8B? 
- Can you repeat the main experiment with a more standard variant of KGW?
limitations: limitations: The only comment I have is regarding quantification of the efficiency degradation which I believe should be explicit in the main paper.
paper_summary: paper_summary: The paper presents a novel watermarking scheme for large language models (LLMs). The proposed WaterMax scheme aims to achieve high detectability while maintaining the quality of the generated text, without modifying the LLM's weights, logits, temperature, or sampling technique. WaterMax balances robustness and complexity, distinguishing itself from existing methods that often trade off quality for robustness. The performance of WaterMax is theoretically proven and experimentally validated.
strength_weakness: strength_weakness: 1. The method involves generating multiple texts for a given prompt and selecting the most suitable one, which increases computational cost and latency. Although the paper suggests ways to limit this, it remains a potential drawback.
2. Based on the randomness in the sampling strategy, LLMs can generate diverse outputs from the same input. This method requires generating multiple outputs and selecting the most suitable one, which may damage the diversity and quality of the generated text.
3. The method's latency, especially in generating longer texts, could be a limitation in time-sensitive applications.
4. The scheme requires careful tuning of parameters to balance robustness, detectability, and computational cost. This adds complexity to its implementation.
questions: questions: 1. How does WaterMax perform with LLMs that exhibit low diversity in generated texts? Are there any measures in place to handle such scenarios effectively?
2. In Line 290, the authors mentioned that there are no methods that can defend against translation attacks. However, many works have been proposed to defend against paraphrase-based and translation-based attacks [1, 2, 3]. Comparison with these methods is necessary.
3. Watermark stealing attack has been proposed recently [4,5,6], which can infer the parameters of the watermarking scheme and remove the watermark from the text. Watermark stealing attacks exhibit significant ability in removing watermark. How does the proposed scheme perform against watermark stealing attacks? 
* [1] A. B. Hou et al., “SemStamp: A Semantic Watermark with Paraphrastic Robustness for Text Generation.” http://arxiv.org/abs/2310.03991
* [2] J. Ren et al., “A Robust Semantics-based Watermark for Large Language Model against Paraphrasing.” http://arxiv.org/abs/2311.08721
* [3] Z. He et al., “Can Watermarks Survive Translation? On the Cross-lingual Consistency of Text Watermark for Large Language Models.” http://arxiv.org/abs/2402.14007
* [4] N. Jovanović, R. Staab, and M. Vechev, “Watermark Stealing in Large Language Models.” http://arxiv.org/abs/2402.19361 
* [5] Q. Wu and V. Chandrasekaran, “Bypassing LLM Watermarks with Color-Aware Substitutions.” http://arxiv.org/abs/2403.14719 
* [6] Z. Zhang et al., “Large Language Model Watermark Stealing With Mixed Integer Programming.” http://arxiv.org/abs/2405.19677
limitations: limitations: This method may affect the quality, diversity and latency of the output text.
paper_summary: paper_summary: The authors propose a method for watermarking language models through the use of rejection sampling. By sampling and discarding "chunks" from the model until the p-value returned by an (arbitrary) detection rule is sufficiently low, the proposed method simultaneously preserves output text quality while achieving strong robustness to a variety of attacks. Crucially, the proposed method does not require any intervention within the model itself (e.g. via logit biasing).
strength_weakness: strength_weakness: * A previous LLM watermarking work, "SemStamp" [1], is similarly based on rejection sampling. Adding experimental comparisons to SemStamp might therefore strengthen the paper by showing how the proposed method fares against the most directly comparable existing method. Otherwise, the authors should probably cite it.
* The authors claim on line 62 that the method of Kuditipudi et al. is the only watermark explicitly designed for robustness; however, the unigram method of Zhao et al. [2] also appears to provide theoretical robustness guarantees.
* While the authors propose an algorithm to limit search over candidate generations, the computational complexity of the proposed method is somewhat concerning. Based on figure 7 (appendix G), it looks like WaterMax incurs ≤ 40% additional runtime on top of generation at a length of only 256 tokens; for the texts in the "Mark My Words" benchmark, the authors report in line 560 that WaterMax requires 5 times the runtime of KGW & Aaronson for watermarked generation. Additional computation is unavoidable with a rejection sampling watermarking scheme, but the authors could address this limitation more clearly within the main paper body.
* A very minor note -- given that the authors consistently compare three watermarking schemes (WaterMax, Aaronson, KGW), it might improve legibility to use a consistent color scheme to refer to these methods across figures.

[1] https://arxiv.org/abs/2310.03991 (NDSS '24)
[2] https://arxiv.org/abs/2306.17439  (ICLR '24)
questions: questions: * Did the authors explore the use of detection rules other than (11) in conjunction with WaterMax, and if so, did they observe any significant differences in performance?
limitations: limitations: * See comment on efficiency in "Weaknesses" section
paper_summary: paper_summary: This paper proposes a watermark technique called WaterMax to distinguish LLM-generated texts and human-written texts. WaterMax starts with the watermark detector and asks LLMs to generate a group of candidates from which the one with the lowest p-value determined by that detector is selected as the final output. This work offers a brandnew perspective of text watermarking as there is no formal watermark generator to embed watermark into LLM outputs. Watermax breaks the trade-offs between watermark detectability, quality and robustness, which is carefully discussed in this work with theoretical proof and experiment validation.
strength_weakness: strength_weakness: 1. The dataset used for experiments is limited to high-entropy text generation, yet in reality there is need to watermark LLM-generated codes.
questions: questions: Is it possible to include low-entropy tasks such as code generation to test if the detector can still properly function? Several works [1,2] can be refered to.

[1].Who Wrote this Code? Watermarking for Code Generation
[2].An Entropy-based Text Watermarking Detection Method
limitations: limitations: It would be better to include more datasets, and further improve the time complexity if possible.

Comments: title: Reply to Authors
Reply to Authors
comment: Thank you for responding. I will maintain my rating.
We thank the reviewer for their feedback. We would however like to clarify some points:
  
> If the authors categorically reject this common evaluation method based on personal beliefs, it is their duty to find another comparably trustworthy way of measuring text quality.

Their seems to be a misunderstanding with regard to our stance with respect to evaluating text quality using LLMs. The reason we have not chosen this method to evaluate the performance of watermarking methods is not due to personal belief but, as we claim in the rebuttal, due to its insufficient discriminative power in the specific case of watermarking.
Evaluating the impact of a watermark on text is a very different problem than say, evaluating the quality of a newspaper article. Indeed, the watermarking signal is (hopefully) weak enough to be hard to detect, and as a consequence, using LLMs as a judge to measure its impact might not be the best tool for the job. Again, the only metrics we have found to vary alongside watermark strength were perplexity and the different variants of ROUGE. Our choice was thus made not due to personal preference but out of necessity of having a meaningful metric in the specific situation of watermarking. 

Now, there is an argument to be made against this choice: if an LLM cannot discriminate between watermarked and non-watermarked text, isn't that enough to claim perfect quality preservation?  Such a decision would remove any benefit of so called "distortion-free" algorithms (such as Aaronson's) since even a high $\delta$ of KGW don't seem to impact the grading of an LLM consistently. As an analogy, we could also use LLM judges to grade the overall quality of pictures in the case of image watermarking. Most likely, the problem would be the same as the LLM would likely disregard the slight noise added by watermark methods whereas more common metrics (PSNR, LPIPS, SSIM) would take even small perturbations into account. 

The question then becomes: does the watermarker simply wants to preserve content quality as measured by a human judge -- allowing for larger distortion --, or does she want to keep as close to what would be the "natural" distribution of the content? We decided for the latter as it seems to capture the impact of watermark on text better than grading.

>In their rebuttal response, the authors only experiment with weak 7B models, while there are orders of magnitude more capable open variants. Why were these models ignored?

We followed the methodologies proposed recently in the  watermarking literature: the *Mark My Words* benchmark [1] claims good grade correlations between GPT-3.5 and the Llama-2-7b model (see Section 4.1 of their paper where they claim a $R^2 =0.97$). Furthermore, the 7b model of Prometheus-eval [2] is claimed to attain SOTA performance at its size and is specifically fine-tuned on GPT-4 evaluations. If we are to trust the results from these works, there should not be a large gap in grading between model sizes.

> [It] is hard to accept the perplexity of a weak 3B model as the only way to measure [text quality].

We chose Opt-2.7b for measuring perplexity as to follow KGW methodology in [3] (see Section 6 of their paper). We haven't found any difference between using a small or a larger model  for measuring perplexity. In our case we tested Llama-2-7b, Llama-3-8b and Mistral-7b-v0.2 and despite some differences in the absolute value of the perplexity measured, there was no difference in relative perplexity between the watermarking algorithms -- which is what we want to measure. Consequently, we opted for the smaller model in order to match with the methodology of previous art.


[1] _Mark My Words: Analyzing and Evaluating Language Model Watermarks_, J. Piet et al.

[2] _Prometheus: Inducing Fine-grained Evaluation Capability in Language Models_, S. Kim et al.

[3] _A watermark for large language models_ Kirchenbauer, John, et al.
I thank the authors for answering my questions,  I prefer to maintain the score I initially assigned.
I thank the authors for responding and I acknowledge the provided results as well as the promise to include explicit comments on computation inefficiency to the main paper. My main concern, which is that measuring free text quality using the perplexity of a 3B model is insufficient, was not addressed. I acknowledge the authors' strong ethical stance, and I do not intend to discuss the stance itself further. 

As the authors acknowledge, using SOTA LLMs as judges of text quality is (for better or worse) a widely popular method in current research, meant to save on costs of human studies. If the authors categorically reject this common evaluation method based on personal beliefs, it is their duty to find another comparably trustworthy way of measuring text quality. One option would be a human study, and another may be testing more capable open models. In their rebuttal response, the authors only experiment with weak 7B models, while there are orders of magnitude more capable open variants. Why were these models ignored? 

As text quality is a key metric that the work relies on, it is hard to accept the perplexity of a weak 3B model as the only way to measure it.
I thank the authors for their clarification. In light of their full rebuttal, which has addressed many of my concerns with the paper, I have raised my review score.
I'm sorry, our rebuttal was not clear. We wish to cite this paper due to its similarity, yet we will not include it in the benchmark. We agree that this paper helps contextualize our work. Thanks for your advise.

Best Regards
I thank the authors for their reply and for the general rebuttal. The additional experiments and promised clarifications re: complexity overhead should strengthen the paper.

> We thank the reviewer for pointing us to SemStamp. We acknowledge that there exists some proximity to our work in the sense that they perform rejection sampling on sentences… However, the work exhibits two major weakness that prevent comparison…

I’m confused how these weaknesses would prevent at the very least mentioning the prior published sentence-level rejection sampling watermark. If anything they contextualize WaterMax’s strengths.