Pseudo- vs. True-Randomness: Rethinking Distortion-Free Watermarks of Language Models under Watermark Key Collisions

The proposed beta-watermark shares considerable similarities with DiPmark (Yihan Wu, Zhengmian Hu, Hongyang Zhang, and Heng Huang. Dipmark: A Stealthy, Efficient and Resilient Watermark for Large Language Models), as both are variations of the permute reweight PDA-rule. Additionally, the algorithms in Appendix A are nearly identical to Algorithms 1 and 2 in DiPmark. It is recommended to add a comparison with DiPmark in the paper.

In Dipmark, the token probability interval $[0, 1]$ is divided into three regions: $[0, \alpha]$, $[\alpha, 1-\alpha]$, and $[1-\alpha, 1]$, with the probability mass within $[0, \alpha]$ being set to 0. As a result, compared to the beta watermark, Dipmark sacrifices the true randomness for tokens in the $[0, \alpha]$ range. We will include the relevant discussion and experimental results in our paper.

The experiments primarily compare against soft watermarking (ICML 2023 Best Paper) but lack examples of comparing watermark text effects under different parameters. Furthermore, it is recommended to include comparisons with other watermarking techniques mentioned in the paper to enhance understanding for the audience.

Thank you for the suggestion. In Section F.1, we compare the effects of watermarking on text under different parameters for both the Soft watermark and the Beta watermark. Additionally, we have included comparisons with other watermarking techniques discussed in our paper. Please refer to Table 2, Table 5 (Appendix), and Table 6 (Appendix), where we compare the Beta watermark with the inverse-sampling, Gumbel-reparameterization, and permute-reweight watermark techniques.

The paper does not analyze or compare watermark detection time, algorithmic complexity, or system performance overhead.

Following Dipmark, we show the watermark detection time on 1/1000 examples below. From the result, we see beta-watermark has similar detection time as soft watermark and dipmark.

The paper analyzes the performance of the watermark model under key collisions, which reflects the issue of information capacity in watermarking algorithms. However, typical applications of text watermarking have low demands on key space, and the paper lacks a clear positioning of its problem setting. The paper uses identical prompts producing identical outputs to illustrate randomness issues, but this randomness is model parameter-dependent and unrelated to the watermarking algorithm.

Could you please elaborate further on the statement that “typical applications of text watermarking have low demands on key space”? In lines [165–178], we provide a detailed discussion of existing key sampling methods and key space considerations, and we demonstrate that key collision is inevitable under the current watermarking schemes.

Moreover, the issue of “producing identical outputs” is not typically a problem with the model itself but rather with the pseudo-random sampling mechanism, which is directly tied to the watermarking algorithm. In the watermark generator, a pseudo-random sampling algorithm seeded by the watermark key is used to modify the token distribution. When the same seed (i.e., the same watermark key) is used, the pseudo-random sampling algorithm produces identical outputs. Therefore, the identical outputs are a direct result of the pseudo-random nature of the watermark generator combined with key collisions.

The differences between Figures 4 and 6 are minimal. It is recommended to combine the different line plots into a single figure for comparison.

Thanks for the suggestion, we will merge them into one plot.

Section 4.3 of the paper designs a black-box, distortion-free watermark detection algorithm that relies on comparisons with the original unwatermarked model...

To our best knowledge, this is the first algorithm that can detect whether an LM is watermarked or not given the black-box LM access, thus, we are not able to conduct comparison experiments. This algorithm enables the users to detect whether an LM is watermarked or not.

The experimental data only presents results with δ values greater than 1...

Please check table 4,5,6 in the appendix, where we provide the result of soft watermark with $\delta=0.5$. From these tables we see that our method can still outperform soft watermark under $\delta<1$ conditions.

The discussion on pseudo-random versus true random sampling could be further expanded...

In Theorem 4.9, we provide a detailed theoretical analysis about the distribution bias introduced by the existing three pseudo-random sampling algorithms. We would be happy to add more discussions based on the reviewer’s suggestions.

The technical merit is limited. The claims in this paper are rather easy to prove (yet the notation is quite heavy). E.g., Theorem 4.13 is pretty straightforward. A model with detectable watermarks and the same output distribution as the original one does not exist.

We respectfully disagree. The technical merit of a theorem should not be judged based on the simplicity of its proof but rather on the significance of the insights it provides. To the best of our knowledge, we are the first to theoretically prove the non-existence of a strongly distortion-free watermark, which is a critical finding for the LLM watermarking community. Furthermore, we would appreciate it if the reviewer could elaborate on why they find Theorem 4.13 to be straightforward.

I do not understand the motivation for detecting watermarked models. Why not detect watermarked texts? The service provider knows which models (they provide) are watermarked in the first place, and the task is to determine which texts are generated from the watermarked models they provided (for copyright, intellectual property, plagiarism detection, etc.). Hence, theorem 4.12 (although it is technically valid) also does not make sense to me. Why would the service provider compute the performance metric for two models that she/he has access to and determine if one of them is watermarked?

We apologize for any confusion. The intuition behind detecting watermarked models is to enable users to determine whether a language model is watermarked or not. For instance, consider a scenario where a user has access to the original LM provided by an official service (e.g., LLAMA or ChatGPT) and the same model offered by a private institution at a lower cost. Our method allows the user to detect whether the model from the private institution has been watermarked or modified.

The proposed solution (0<β<0.5) is similar to the permute-reweight baseline (beta=0). The novelty is limited and the performance increase (shown in Table 2) is marginal (compared with beta=0).

We respectfully disagree with this comment. The beta watermark is built upon the permute-reweight watermark; however, the performance improvement is substantial compared to $\beta=0$. For instance, in table 2, when comparing $\beta=0.3$ to $\beta=0$, $\beta=0.3$ achieves at least a 30% reduction in the $\Delta$ BERT Score, which is clearly a significant improvement and far from marginal.

The experiment section is limited. The baselines are limited to distortion-free baselines and statistical watermarks are not included.

As this paper focuses on distortion-free watermarks, we believe we have included all relevant distortion-free watermarks in our comparison. Since other statistical watermarks are not even step-wise distortion-free, they are not pertinent to the distortion-freeness experiments conducted in our work.

It is important to show that distortion does lead to worse performance in watermarked models, otherwise distortion-freeness is not well-motivated. Without this motivation, this paper is mainly proposing a new solution for distortion-free watermarks, and given that the solution does not seem novel, the contribution of this paper is limited.

Distortion does lead to worse performance in watermark models, which has already been demonstrated by [1,2]. In Figure 3 and Table 4. We used the same settings in [1,2] and showed that non-distortion-free watermarks can reduce the performance of LMs on machine translation and text summarization tasks.

From Figure 3, it is not clear which watermark performs better. Is there any direct measurement of the distortion-freeness?

We apologize for the unclear figure. We have also summarized the performance comparison in appendix Table 4, where we observe a significant performance drop for non-distortion-free watermarks. Currently, there are no direct metrics available to measure distortion-freeness. Following the methodology of existing works [1,2], we evaluate distortion-freeness based on the quality of the generated content.

questions.

Thank you for pointing out the typos, we will correct them in our revision.

[1] Hu et al. Unbiased watermark for large language models. [2] Wu et al. Dipmark: a stealthy, efficient and resilient watermark for large language models.

The paper concludes that creating a fully distortion-free watermark is impossible because of key collisions. This result appears aligns with expectations,

Thank you for recognizing the correctness of our result!

and it may not hold significant interest for the LLM watermarking community.

In our work, we introduced three levels of distortion-freeness and re-evaluated the existing distortion-free watermark. We demonstrate that all of these approaches are only weakly distortion-free, rather than strongly distortion-free, indicating that they still introduce distributional bias into the language model. We believe this insight is crucial for advancing the understanding of distortion-freeness in LM watermarking.

In particular, the importance of strongly distortion-free watermarks remains unclear. The authors suggest that a non-distortion-free watermark would result in repetitive generations. However, this issue also arises without watermarking when using greedy decoding.

Strongly distortion-free watermarks are crucial because they preserve the quality of content generated by language models, making them more suitable for industry-level LLM applications where watermarking is necessary. Moreover, "repetitive generations" are merely one consequence of non-distortion-free watermarks. The core issue with non-distortion-free watermarks lies in their intrinsic bias, which distorts the original LM distribution and ultimately degrades generation quality.

Furthermore, Aaranson et al. employ random decoding on top of the modified distribution of the next token, not just greedy decoding, which is the sole focus of the discussions regarding Aaranson et al. In such cases, repeatedly prompting a model with the same input does not necessarily produce identical outputs. Is this understanding correct?

No, in Theorem 4.13, we theoretically prove the non-existence of strongly distortion-free watermarks beyond the key collision assumption. This implies that the approach by Aaronson et al. is also not strongly distortion-free and introduces distributional bias into language models.

"Our studies reveal that key collisions are inevitable due to the limited availability of watermark keys, and existing distortion-free watermarks exhibit a significant distribution bias toward the original LM distribution in the presence of key collisions." -> What do the authors mean by "towards the original LM distribution?"

Because the watermarking method will change the sampling process of the LM, the distribution of watermarked LMs will be different from the distribution of non-watermarked LMs.