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

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.

Strengths

1. WaterMax offers a brendnew research perspective in the field of text watermarking, where there is no official watermark generator. 2. WaterMax is almost distortion-free as it achieves high text quality on LLM outputs, yet the detectability is preserved. 3. By upgrading the detector, WaterMax can achieve high robustness as well. 4. The superiority of WaterMax is both theoretically proven and experimentally validated.

Weaknesses

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

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

Rating

7

Confidence

4

Soundness

4

Presentation

3

Contribution

4

Limitations

It would be better to include more datasets, and further improve the time complexity if possible.

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

Strengths

* The proposed method is both elegant and flexible. * The paper is clearly written and adequately describes the proposed method. * The authors demonstrate strong results in terms of text quality, detectability, and robustness against a reasonable selection of attacks.

Weaknesses

* 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

* 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?

Rating

8

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

* See comment on efficiency in "Weaknesses" section

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.

Strengths

1. WaterMax introduces a new detection mechanisms that improve the detectability of watermark in short text, thus preserving the original LLM's token distribution and sampling method. 2. The scheme maintains the quality of the generated text, which is a critical factor in practical applications of LLMs. 3. The paper demonstrates that WaterMax achieves higher robustness and detectability compared to other state-of-the-art watermarking techniques, even under various attack scenarios. 4. The theoretical and experimental evaluations are thorough, covering multiple LLMs and benchmarks. This provides a solid validation of the scheme's effectiveness.

Weaknesses

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

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

Rating

6

Confidence

4

Soundness

3

Presentation

2

Contribution

3

Limitations

This method may affect the quality, diversity and latency of the output text.

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.

Strengths

- **The approach is novel**: the work investigates a fundamentally different approach from prior baselines which is a valuable contribution in itself. - **Thorough analysis**: the work analyzes the proposed method from several perspectives, and both theoretically and empirically, making it a well-rounded study. I especially appreciate the care taken to discuss the underlying assumptions and investigate their violations in practice. - **Good writing**: the work is generally very well written, discusses the prior work well, and introduces the method in an understandable way, splitting the different components across different parts of the paper.

Weaknesses

- **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

- 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?

Rating

5

Confidence

4

Soundness

3

Presentation

4

Contribution

3

Limitations

The only comment I have is regarding quantification of the efficiency degradation which I believe should be explicit in the main paper.

Reply to Authors

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.