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

Q1: "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.""

We thank the reviewer for the references. At the detection side, these works weight the token value depending on an estimated entropy of the token: hard thresholding for [1], soft weighting for [2]. In principal, this idea can be integrated to WaterMax at the detection side (and thus at the embedding as well since it uses the same score function). Applying hard thresholding [1], WaterMax will not embed a watermark in a chunk where all tokens have low entropy. Yet, we do not recommend the soft weighting of [2]: this prevents from computing a sound p-value.

[1] Who Wrote this Code? Watermarking for Code Generation [2] An Entropy-based Text Watermarking Detection Method

W1: "A previous LLM watermarking work, "SemStamp" [1], is similarly ... Adding experimental comparisons to SemStamp ... Otherwise, the authors should probably cite it."

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. It can also be seen as a KGW-type algorithm at the level of sentences instead of tokens.

However, the work exhibits two major weakness that prevent comparison:

1. Since the watermark works at the level of sentences and not tokens, extremely large texts are necessary to attain acceptable performance. SemStamp's false positive rate is around 1%. All algorithms studied in our work easily reach 100% TPR within this regime.
2. The authors compute the FPR using a z-score which allows an accurate approximation of the p-value only when the number of sentences is high -- however this is never achieved in practice. No empirical validation of this approximation is provided. On the other hand, our work computes exact p-values which are very low for watermarked text. For these reasons, we cannot sensibly compare SemStamp to the state-of-the-art.

W2: "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. ..."

We agree. We thank the reviewer for pointing out this oversight. We added this reference.

W4: "A very minor note ... it might improve legibility to use a consistent color scheme to refer to these methods across figures."

We corrected the colors of Fig. 1 which were indeed not consistent with the other figures. Thanks for pointing this out.

Q1: "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?"

If 'detection rule' means the distribution of the values associated to each token, then yes: As we show in the paper, the choice of detection rule theoretically does not impact the performance of WaterMax.

If detection rules means other kind of score function like SemStamp based semantics, then no, we did not try.

W4: "The scheme requires careful tuning of parameters ... This adds complexity to its implementation."

The tuning of our algorithm is less complex than the tuning of KGW. The two main parameters of WaterMax are the number of chunk $N$ and the number of drafts per chunk $n$:

• Detectability/robustness: the performance of Watermax can be computed a priori using the theoretical formulas in Eq.(4) or Eq.(6).
• Quality: $(N,n)$ have basically no impact on text quality.
• Complexity: Increasing (N,n) increases computational complexity. The cost of $n$ can be reduced through parallelization, wheras the cost of $N$ cannot.

The size of the h-window mostly set the trade-off between robustness and security (against Watermark stealing attack). This is common to any fixed h-window based scheme like KGW and Aaronson's schemes.

In contrast, the choice of $(\gamma,\delta)$ for KGW is not well documented: their impact on the detectability and quality is not easy to predict. Their setting must be done empirically.

Q1: "How does WaterMax perform with LLMs that exhibit low diversity in generated texts? ... "

A LLM that exhibits low diversity in generated text is a LLM with low entropy in its completions. We direct the reviewer to Appendix J which is explicitly treating this question. We show that both Aaronson's scheme and KGW are sensitive to the LLM's entropy whereas WaterMax 's performance stays constant whatever the choice of LLM and temperature. The reason for this behavior being that WaterMax works on the level of chunks of token whereas the other two algorithms works token per token. This means that, as long as a LLM provides at least some diversity at the chunk level, WaterMax's performance should not suffer compared to other schemes.

Q2: "In Line 290, the authors mentioned that there are no methods that can defend against translation attacks. However, many works ... [1, 2, 3]. Comparison with these methods is necessary."

We agree with the reviewer: this statement was not correct. We thank the reviewer for providing these references, which we will add to the paper.

However, we cannot compare to the proposed methods as they don't provide any guarantees in terms of false-alarm contrary to the three algorithms studied in our work. Furthermore, due to the lack of theoretical false-alarm rates, these works only compute empirical FPR, --with the papers providing results for FPR from 1% to 10%. This is to be compared to our work which demands false-alarm rates at $10^{-6}$ or below. On the other hand, WaterMax, KGW and Aaronson easily reach 100% TPR with almost not cost on quality or complexity for FPR from 1% to 10%.

Q3: "Watermark stealing attack has been proposed recently [4,5,6] ... How does the proposed scheme perform against watermark stealing attacks?"

We again thank the reviewer for these references. The problem of watermark stealing is mainly linked to the choice of 1) hashing function and 2) scoring function.

1. The attack in [4] only works for the Min-Hash and Sum-Hash functions. We don't use these hashing functions for any watermark scheme as they are intrinsically flawed. The hash is computed recursively on each token in the window, guaranteeing a new hash -- and thus a different key -- for each token. Moreover, we use much longer hash windows: $h=6$.
2. The references in [4,5] only work for UNIGRAM and KGW as they are based on the existence of a green-list of tokens. Like Aaronson, WaterMax is not based on a binary partition of the tokens: it associates a real soft value to each token. Stealing the secret of this kind of schemes has not been demonstrated.
3. References [4,5,6] work token-wise, whereas WaterMax works over chunks, not token. This means that it may select a chunk containing a low valued token because globally that chunk maximizes the score. Therefore, the frequency of a token may not be related to its associated secret value.

Q1: "Is GPT4 unreliable for the task of judging text quality? Can you provide empirical evidence?"

First of all, using closed-source models available through API is against our ethics because it prevents reproducibility: GPT-4 is not free; we do not fully control the prompts; it will be no longer available when replaced with GPT-5, etc.

With that said, we acknowledge the trend towards evaluating text quality using LLM judges -- as an example the Mark My Words benchmark [1] directly used 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 [2].

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. 3 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 [2], using the code provided in the official Githubs's implementation.

1. 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 non-watermarked texts, with Mistral-7b-instruct-v0.2 highly biased in favor of non-watermarked texts generated with temperature 1.0.
2. The average grade does not fluctuate significantly for different watermark strength, whatever the choice of LLM judge. Interestingly, Fig. 3 shows that increasing $\delta$ can slightly increase the LLM grading, which is a total non-sense.
3. 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.\n\nhe bSgaJ his jouTnFy in the miDty mountaiMs of wales, where he souFht [...]

Our conclusion is that, for the moment, 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 were.

[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.

Q2: "Can you repeat the main experiment with any model larger than 8B?"

We repeated the experiments with Llama-2-13b and Phi-Medium-4k, two models with 13 and 14 billion parameters respectively. We report the results in the global response in Fig. 1-2. The results are mostly identical to the smaller models: Phi-medium has high entropy and thus all watermarking scheme perform well, whereas Llama-2-13b has low entropy leading to low performance except for WaterMax. This points to the fact that the main parameter of importance is the entropy of the completion, not the size of model. (Note that there is no official 13b version of Llama-3-Instruct.)

Q3: "Can you repeat the main experiment with a more standard variant of KGW?"

We chose to fix $\gamma = 0.5$ per the recommendations of the Mark My Words benchmark [1]. We repeated the experiments following the reviewer's specifications in Fig. 1a and 2a of the pdf. The results are mostly similar and illustrate the trade-off between quality and detectability: smaller $\gamma$ leads to better detectability but lower quality.

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.