Unbiased Watermark for Large Language Models

Thank you for recognizing the strengths of our work and providing constructive feedback. We would like to address the concerns highlighted in your review:

The evaluations do not contain any attacks (the authors mentioned them in Appendix A2)

Actually, we have included preliminary evaluations against random substitution attack in Appendix F.5. Additionally, we have now supplemented our research with an evaluation against a random deletion attack:

If the proposed watermark methods suffer from a simple attack like paraphrasing, it would significantly undermine the paper's contributions.

Unfortunately, it is true that our watermarking methods are vulnerable to simple attacks. Specifically, although the watermarks can still be detected after changes to the input, the efficiency of this detection drops notably, necessitating longer sequences for reliable watermark detection. This vulnerability is fundamentally due to the fact that watermark detection relies on the presence of identical n-grams during watermark generation and detection. Any form of attack, including paraphrasing or simple word substitutions, could easily disrupt these n-grams, thereby reducing the efficiency of watermarks detection. This vulnerability is not unique to our work; it is a common challenge in the field of watermarking, similar to recent findings (Kirchenbauer et al. 2023).

The primary contribution of our paper is the development of the concept of an unbiased watermark. While we recognize the importance of robustness in watermarking research, our current work is not aimed at enhancing the robustness of watermarks. Our approach maintains a level of robustness on par with existing methodologies, as discussed in Appendix F.5.

Larger models like LLAMA-2 should also be evaluated to further enhance the practicality.

We have conducted evaluations with larger models, including LLAMA-2 in our appendix. The results of these evaluations are detailed in Appendix F.1, where we used LLAMA-2 for text summarization and poetry generation tasks. Furthermore, we have expanded our experiments to include natural language generation with Wikitext and instruction following with FLAN, providing additional practical evidence for downstream invariant property:

Thank you again for your thoughtful comment. Your recognition of our work's strengths and constructive feedback are greatly appreciated.

Thank you for acknowledging our work on the unbiased watermarks. We appreciate your thoughtful comment and would like to answer the questions point by point.

How do you envision the implementation of unbiased watermarks in practice, and what challenges do you anticipate?

Regarding the practical implementation of unbiased watermarks, storage issue could be a consideration. In our algorithm, we introduced the concept of context code history, which inevitably requires additional storage space. While theoretically, unlimited storage could enable $\infty$-shot-undetectable watermarking, practical constraints might limit storage capacity, resulting in n-shot-undetectability. As n increases, so does the required storage space, but this trade-off improves undetectability. For instance, storing the context code of the last n outputs guarantees n-shot-undetectability. Generally, storage complexity grows in $O(n)$. More details can be found in Appendix G.3, item three.

How do you plan to address concerns (in practice) regarding the potential manipulation or removal of watermarks by users?

We believe the battle between watermarking and watermark removal will be a long-living problem. This dynamic has seen rapid developments recently. Our current research marks significant progress in this area by theoretically ensuring that users cannot detect the presence of watermarks. This advancement complicates the manipulation and removal of watermarks, as it becomes challenging to assess whether the watermark remains intact. We look forward to future research that will build upon these advancements.

Can you elaborate the key factors when chasing the optimal trade-off between mentioned in the paper?

One of our core contributions is the decoupling of unbiasedness and watermark strength. Previous works faced a trade-off between output quality and watermark detectability; to make watermarks easier to detect, one had to sacrifice quality. Our approach ensures that output quality remains unchanged, regardless of watermark strength. Thus, we believe we have achieved an optimal trade-off between these factors.

Again, thank you for your insightful questions and the opportunity to clarify our approach.

Thanks for recognizing our novel contribution.

Is this because the OPT-6.7B model is not fine-tuned for the NW cases? I am concerned about whether this comparison is fair enough.

We didn't finetune the model, and we use the same model OPT-6.7B across NW, $\delta$-RW, $\gamma$-RW to ensure a fair comparison.

The lower readability output in the 'NW' section is due to the inherent variability of the OPT-6.7B model's performance. This model sometimes generates lower-quality outputs, which is evident in the NW case. This is a characteristic of the OPT-6.7B model itself, rather than an effect of our watermarking strategy or a lack of fine-tuning.

In light of your feedback, we have replicated table 3 with a state-of-the-art model, LLaMA2. We find that the readability of the outputs improve significantly, and the variability of output quality also decreases. The updated results with LLaMA2 are as follows:

We hope that the additional information will address your concerns. Once again, thank you for recognizing our work and providing valuable feedback.

Thank you for your comprehensive review and constructive feedback on our paper.

such as general natural language generation, are required

We appreciate your suggestion to extend our experiments beyond translation and summarization tasks. We have expanded our datasets to include wikitext for natural language completion and the FLAN dataset for instruction-following tasks. Our results demonstrate the downstream-invariant properties across these new tasks.

It seems that the robustness towards the exiting watermarking attacks are not verified in the paper

Your point about the robustness of our watermarking method was well-taken. To address this, we've now incorporated tests against random token deletion. These additional experiments showcase the robustness of our methods. Exploring a broader range of sophisticated watermarking attack types, including emoji attack, will be a focus of our future work.

Theorems 14 should be in the main body instead of the appendix

Although we briefly mention that "Both methods are unbiased1" on page 4, we agree that a formal presentation of Theorem 14 in the main body would better clarify the argument. Accordingly, we will revise our manuscript to include Theorem 14 in a more prominent section.

We're grateful for your constructive feedback and for your recognition of our novel contributions.

We appreciate the time and effort you have dedicated to reviewing our manuscript. We are grateful for the opportunity to address the concerns and queries you have brought forward.

While the gamma scheme overlap with the schemes presented in Kuditipudi et al. (... there are strong similarities in the way the signature is encoded however)

We respectfully disagree with the assertion of strong similarities in signature encoding between our gamma reweight scheme and method in Kuditipudi et al.

The critical distinction lies in the underlying mechanism: all schemes $\Gamma(\xi,\mu)$ presented in Kuditipudi et al. are based on inverse sampling, where the output is a specific value. In contrast, our gamma reweight scheme is not based on inverse sampling, as it produces a distribution rather than a single value。

Given this fundamental difference, we do not concur with the notion of strong similarity. We would appreciate it if the reviewer could clarify what specific similarities are being referred to. This clarification will enable us to address the concern more directly and ensure that our method's uniqueness and contributions are accurately understood.

but it would be much more interesting to give our some sort of a global metric, such as the AUC (or AUC-PR) in detecting watermarked vs unwatermarked text

Actually, we have reported AUC performance in Section F.5. In standard experiments, where no perturbations are introduced, the AUC is extremely close to 1, and the deviation from 1 is so minimal that it falls within the margin of error, making quantitative assessment challenging. This is the primary reason why we have opted to present the score per token in the main paper, as it provides a more discernible measure of the watermark's detectability.

it is not clear how robust the maximin LLR scheme is to different scenarios. Meaningful ablation experiments are missing.

We kindly direct your attention to Section F.2 in the appendix, where we provided ablation experiments specifically to explore the robustness of the maximin LLR approach in different scenarios. These experiments cover variations in temperature settings, top-k selections, different prompts, and different language models.

We believe that these experiments meaningfully address concerns regarding the robustness of our approach.

you will exhaust all the possible n-grams

While that is possible in theory, the number of all possible n-grams is astronomically large for $n\geq 3$, and in reality, it's nearly impossible to reaching saturation.

Furthermore, refraining watermarking on previously seen n-grams is necessary for ensuring strict unbiased property. As such, we consider being the first to clearly explain this critical point as a significant contribution of our work, rather than a weakness.

Additionally, if needed, there are straightforward modifications that can slightly relax the strict $\infty$-shot-undetectable property to circumvent any practical limitations, as discussed in Section G.2, third point, of the appendix.

How does the watermarking scheme perform on context completion and instruction following tasks?

We've broadened our datasets to include wikitext for context completion and flan for instruction following. The downstream-invariant property is also observed in these new tasks.

We want to emphasize that our methods are supported by rigorous theoretical guarantee, and the downstream-invariant property is independent of specific task.

Is it possible to present some empirical evidence on how many tokens are needed to achieve a certain level of detectability on open source LLMs?

Yes. This can be computed by the score per token. For instance, if each token increases the score on average by 0.8784 (as reported in Table 2), then 12 tokens would be enough to achieve a score of 10.5, which means watermark can be detected with p-value < 0.0005, while 23 tokens would bring it down to p-value < 3e-8.

I made a typo in my original comment. I mentioned the gamma scheme where I intended to call out the delta scheme (the stronger of the two schemes) is indeed based on inverse transform sampling, as all of the schemes in the cited work. Is this incorrect?

If your prompt is, "Generate the first 100 primes", do you expect it to be watermarkable?

No, it's not watermarkable because the entropy is close to zero. Unbiased watermarking is only feasible with enough entropy, as discussed in Appendix G.1.

It is known that RL reduces entropy -- do you expect RLHFed model to have the same entropy?

We humbly refrain from discussing the impact of RLHF on the entropy of language models, as it is beyond the scope of this paper and our research expertise. However, it is clear that our unbiased watermarking relies on the entropy of language models. Lower entropy makes watermarking more challenging, both in terms of insertion and detection.

Does your theory have any guarantees wrt watermarking strength?

Yes. For delta reweight , the average LLR score for a token with a watermark is its entropy, $H(P)$, by definition. For our likelihood-agnostic methods, the average score is related to the Rényi entropy of order 2, expressed as $\ln2 - \exp(-H_2(P))$. Further details are provided in Appendix D.1.2 of our paper.

Thank you for your continued engagement and for providing detailed feedback. We appreciate the opportunity to address your points.

I intend to call out the 'gamma' scheme, which the paper itself mentions is based on inverse transform sampling

Is that another typo? Are you referring to the 'delta' scheme?

Can the authors clarify why they think the inverse transform sampling based schemes in Kuditipudi et al. paper are very different?

In our previous response, we clarified the distinguishing factors between our gamma reweight and inverse sampling. Here, we'll highlight the differences between our delta reweight and Kuditipudi et al.'s inverse transform sampling schemes. Although delta reweight, as a specific case of our framework, employs inverse transform sampling, it diverges significantly in other aspects, such as avoiding watermarking for existing context and deriving score based on LLR and maximin LLR. Additionally, our framework is more general than Kuditipudi et al., as our framework encompasses methods beyond inverse transform sampling, such as the gamma reweight.

If I understood the theory correctly, the theory only guarantees that the quality is unaffected but says nothing about the watermarking strength.

Regarding our general unbiased watermark framework, you are correct that the framework itself only guarantees that the quality is unaffected but does not specify a lower bound for watermark strength. To clarify, the general framework encompasses a broad range of possibilities, including scenarios where no watermarking is applied at all (with identity map as unbiased reweighting function), the lower bound for watermark strength in this general context is indeed zero.

However, for specific reweights within our framework, there are non-trivial lower bounds on watermark strength. For instance, for delta reweight , the average LLR score for a token with a watermark is its entropy, $H(P)$, by definition. For our likelihood-agnostic methods, the average score is related to the Rényi entropy of order 2, expressed as $\ln2 - \exp(-H_2(P))$. Further details are provided in Appendix D.1.2 of our paper.

I find the authors claim here in the rebuttal for not running evaluations with instructions on an instruction tuned model confusing -- I would be extremely surprised if the AUC was nearing 1.0 for an Alpaca/Vicuna run at reasonable temperatures.

Per your request, we conducted experiments to provide score per token values for instruction-tuned models:

These numbers remain substantial, indicating strong watermark detectability.

Moreover, It's crucial to consider the impact of text length on watermark detection. For example, if Llama 2 assists in writing an email with around 100 tokens, the total score would be high, making it easy to distinguish watermarked from unwatermarked text. However, for a short text like a subject line with only about 5 tokens, the discrimination power would be much weaker. Thus, it is essential to carefully consider the context and length of the text when comparing watermark detection capabilities.

For the experiments in Section F2, what was the parameter d?

The parameter $d$ was chosen from the set $\\{0,0.1,\dots,0.9,1.0\\}$, as detailed in Appendix E, "Watermark detection" section of our paper.

Can you also look at the robustness of likelihood agnostic methods?

It's important to note that likelihood agnostic methods are independent of the likelihood, so they are invariant to all the perturbations considered in Section F.2. Therefore, their robustness only depends on how much the attacks disrupt the original n-grams in the text.

you'll stop watermarking after the first time you see it. you'll gradually weaken the watermark ... Am I missing something here?

We think what's missing from your comment is the Pareto optimality of our approach regarding to number of watermarked token and undetectable property.

We would like to reiterate that skipping watermarking is essential to ensure an unbiased watermark, thus preserving the output quality and undetectability.

For example, consider an instruction like "generate a sequence of random 01 string", and assume that the original language model generates perfect binary distribution. After saturation, i.e. after encountering all $2^n$ number of distinct n-grams, we must stop watermarking to avoid making the watermark detectable through n-gram frequency analysis.

We also would like to reiterate that there are straightforward modifications that can discard the $\infty$-shot-undetectable property, and turn to weaker $n$-shot-undetectable property, in exchange for more watermarking opportunities. This is discussed in Section G.2.