Provable Robust Watermarking for AI-Generated Text

Thank you for your support of our paper!

Impact of Text Length on Watermark Detection

However, it raises questions about the method's viability and performance on shorter texts. Experiments testing how the proposed method performs on different text lengths are absent.

To investigate the effect of text length on the effectiveness of our watermark detection method, we conducted experiments across different text lengths under both normal and attack scenarios. Specifically, we truncated the text to lengths of 50, 100, 150, and 200 tokens, and evaluated the detection performance. The attack is done by ChatGPT paraphrasing attack. The results, detailed below, demonstrate the robustness of our approach across varying text lengths.

These results highlight the consistent and effective detection of watermarks across various text lengths, affirming the adaptability and robustness of our method. Generally, for shorter text, the detection is not perfect but still achieves very high AUC scores. As the length increases, the detection performance improves.

Response to Specific Questions

Assessing Text Diversity. In our paper, the diversity of text is primarily assessed based on the “on-average high entropy” assumption, as texts typically exhibit a wide range of vocabulary and syntactic patterns. The “on-average high entropy” assumption requires the probability distribution of the roll-out text to be “sufficiently diverse” on average. It is related to but distinct from the “spike entropy” assumption used by Kirchenbauer et al. (2023). We provide the definition and a discussion of this assumption in Appendix C.4.1.

Security Assessment Against Edit-Distance Invariant Attacks. Our watermarking technique uses edit distance as a measure of robustness. The edit distance is the only metric we require the watermark to be robust against. If some attacks do not significantly alter the edit distance, then we can still detect the watermarked text robustly.

Clarification on Gamma Value and Watermark Strength. The watermark strength increases as $\delta$ increases, but the dependence on \gamma is more complex. Increasing $\gamma$ does increase the number of green tokens as the reviewer observes, but it also changes the variance and the tail bound. Bear in mind that the detection rule relies not on the number of green tokens in absolute number, but how many more green tokens we observe over the natural range of the null distribution, It is also coupled with $\delta$, for the same choice of $\delta$, smaller $\gamma$ ensures that the selected green-tokens stand out a bit more due to the soft-max normalization. That might have explained our empirical finding in Table 5. Finding the ideal choice of $\gamma$ theoretically and empirically is an interesting question. At the moment, for every choice of $\gamma,\delta$, our theory allows us to choose a threshold that controls the false positive rate (Remark 3.4).

We appreciate the reviewer's acknowledgment of our contribution.

Compare with the K-gram Method

It would be better if the authors could provide an algorithmic description on the K-gram method so the readers can directly compare it with Algorithms 1 and 2.

We appreciate your insightful suggestion. Indeed, we have included a detailed algorithmic description of Kirchenbauer et al. 2023 in Appendix D.1. The primary distinction between Kirchenbauer et al. and the K-gram method lies in the modification of the green list from Green($y_{t-1}$) to Green($y_{t-k-1:t-1}$). We acknowledge the importance of this comparison and will incorporate a detailed discussion in the revised manuscript.

Clarification on Type-I and Type-II Errors

In Definition 2.2, when comparing the defined type-I and type-II errors, I am confused about why in the type-II error, we need to assume $y$ is generated from the model $\hat{M}$, whereas in the type-I error, it is assumed that $y$ can be arbitrary. Wouldn't it make more sense to assume that $y$ is not generated from model $\hat{M}$ in the type-I error analysis? Based on the current definition, if $y$ is indeed generated by $\hat{M}$, then the definition says its detection correctness is at most $\alpha$? Please clarify it.

To clarify, our definition assumes an arbitrary fixed suspect text $y$. In particular, if $y$ is drawn from any distribution that is statistically independent to the (random) watermark key then we can condition on $y$ and the “no false positive” guarantee applies. It covers any procedure (including human generation) that produces $y$ in a manner independent of the secret partition $G$. However, as the reviewer pointed out, it does not cover random text $y$ that depends on $G$. That would include the distribution from $\hat{M}$ and would not be reasonable. The reason why we can handle an arbitrary fixed $y$ is because our Type I error analysis only depends on the distribution of $G$ — something we have full control over.

Extending Error Guarantees to General K-gram Method

For the general K-gram method, can the error guarantees and analysis be extended? If so, how will this general K value place a role in the error analysis?

Appendices D,E, and the Conclusion discussed results for K-gram for $k>1$. In short, our robustness guarantee, Type I error guarantee, and accuracy guarantee apply immediately with no changes in the analysis. The Type II error guarantee can be extended to the case when $k >1$, but requires us to define the Martingale and bound the concentration differently. We will have a clearer discussion in the updated version.

Thanks for your valuable feedback! We address your concerns as below.

Lack of Distribution-Based Experimental Validation

This paper ensures the property of watermark quality through proof based on distribution distance. However, the relevant experiments only include perplexity and human assessment experiments, lacking distribution-based experimental validation.

We recognize the importance of conducting distribution-based experiments to validate our theoretical claims. In our study, we focus on the quality guarantee for the next token distribution, as described by the following equation: $\forall h, \max\left(D\_{KL}(\hat{p}\_t || p\_t)\, D\_{KL}(p\_t || \hat{p}\_t)\right) \leq \min{(\delta, \delta^2/8)}$

To empirically validate this theory, we conducted experiments with various values of $\delta$ and calculated the average Kullback-Leibler (KL) divergence of the next word probability distribution for the generated text. The values of $\delta$ and the corresponding KL divergences are as follows:

These results demonstrate that with an increase in $\delta$, there is a corresponding increase in the KL divergence, providing empirical support for our theoretical framework.

Robustness Results for Insertions

In addition, the definition of editing operations encompasses "paraphrase, insertion, deletion, replacement", but in the experimental section, robustness results for insertions are missing, which were replaced with "swap".

In addressing robustness against insertions, we opted to focus on "swap" operations. This decision was based on the understanding that, within a bounded edit distance, the effects of insertion and deletion operations are comparable. Specifically, each of these operations can at most transition one token from the green list to the red list. This analysis basis is detailed in Appendices C.2 and D.2.

Further, we also conducted experiments involving random word insertions from a predefined list (randomly selected from the dictionary). The words selected for insertion included ["apple", "blue", "cat", "dog", "elephant", "flower", "giraffe", "house", "ice", "jelly", "kite", "lemon", "moon", "nest", "orange", "penguin", "quilt", "rose", "sun", "tree", "umbrella", "violet", "water", "xenon", "yacht", "zebra"], ensuring coverage of both green and red tokens. These words were randomly inserted at random positions within the text.

The results, as summarized below, indicate that our method demonstrates superior detection capabilities compared to the baseline, even under increased interaction levels:

Our approach consistently shows better detection results against the baseline across various interaction levels.

Impact of Text Length on Watermark Detection

What’s more, the experimental results about the impact of text length on watermark effectiveness are missing.

To investigate the effect of text length on the effectiveness of our watermark detection method, we conducted experiments across different text lengths under both normal and attack scenarios. Specifically, we truncated the text to lengths of 50, 100, 150, and 200 tokens, and evaluated the detection performance. The attack is done by ChatGPT paraphrasing attack. The results, detailed below, demonstrate the robustness of our approach across varying text lengths.

These results highlight the consistent and effective detection of watermarks across various text lengths, affirming the adaptability and robustness of our method. Generally, for shorter text, the detection is not perfect but still achieves very high AUC scores. As the length increases, the detection performance improves.

Thank you for your insightful review. We appreciate the opportunity to clarify and expand upon key aspects of our work.

Response to Paraphrasing Attacks

The robustness to edits within a bound is an awesome property and can be theoretically proved, but the robustness to paraphrasing models could hardly be proven, as there is no guarantee in the edit distance of paraphrasing. The related claims should be treated carefully.

Yes, our theoretical guarantee of robustness concerns edits, as discussed in the paragraph preceding Section 2.2. We acknowledged, “Admittedly, there are other attacks where edit distance does not capture either the effort or the utility loss. For example, if one prompts an unwatermarked LLM to paraphrase $y$ then the number of edits can be large but the semantic meaning is retained. However, edit distance is a natural metric that smoothly interpolates the gray zone between the world where $y_A = y$ in which it should clearly be caught and the other world where $y_A$ is independently created without using the watermarked model in which it would be a false positive if Detect returns 1.”

Moreover, our theoretical framework does offer insights regarding the edit distance in paraphrasing. Paraphrasing can be seen as a sequence of actions – deletion, insertion, and replacement of tokens. Although extensive paraphrasing might result in a large edit distance (with the maximum being n, the length of the text), our framework assures that we can detect paraphrases if the edit distance falls below a certain threshold.

Empirically, we found our watermark can still detect paraphrased text, but the “power” gets smaller, which means it requires longer watermarked text to have high confidence in detection. Our hypothesis is that paraphrasing reduces the density of watermarks in the text, but do not remove it. Overall, while paraphrasing attacks present challenges, edit distance offers a useful starting point. Further research on formal definitions and robustness against paraphrasing is important for future work.

Output Word Distribution and Related Work

The consistency of the output word distribution is a great property and it was also discussed in previous literature, such as [1]. How will you compare this approach with theirs? The Type I/II errors were not discussed in their work, can you show your advantages against them?

We appreciate the reference to He et al. (2022) and will include a discussion in our revised paper. However, there are several key differences between these two works:

(1) We are studying different tasks. Our paper addresses the problem of detecting AI-generated text, whereas CATER (He et al., 2022) focuses on protecting against model distillation. CATER involves watermarking training data so that models trained on it produce outputs containing the watermark. Its goal is to identify model/data theft, not detect AI-generated text. As such, CATER does not consider the Type I/II errors relevant to AI detection systems.

(2) CATER uses post-processing to insert watermarks by changing words to synonyms. Our method integrates watermarking into the text generation process itself.

(3) CATER addresses the output word distribution to prevent attackers from identifying watermarked words through statistical analysis. Our method provides a theoretical guarantee that the original and watermarked probability vectors for the next token are closely aligned in any Renyi-divergence. However, we do not guarantee the output word distribution is identical. We address the potential for attacks in Appendix B.5, where we explore the possibility of adversaries bypassing detection by using secret tokens estimated from the output word distribution. We find that it is difficult to accurately estimate the green list utilizing the output word distribution. Even if the green list is known, our watermark is still somewhat effective thanks to our added robustness.