De-mark: Watermark Removal in Large Language Models

We thank the reviewer for the constructive feedback, which has been invaluable in refining our manuscript. Below, we provide detailed responses to each of your comments:

Q1: Firstly, the attack is primarily focused on a specific soft watermark (Kirchenbauer et al., 2023a). This type of watermark, as demonstrated by Gu et al. (2024) in "On the Learnability of Watermarks for Language Models" (ICLR 2024), is known to be relatively easily learned. While the paper introduces refined techniques to estimate the hyperparameters of this soft watermark, the overall contribution in addressing a fundamentally weak watermark is arguably incremental. Secondly, the paper's scope does not extend to other watermarking methods, such as advanced cryptographic watermarks, which are designed to be theoretically resistant to parameter learning. Examples like "Undetectable watermarks for language models" highlight this gap.

A1: Our method is specifically designed for n-gram-based approaches, which are widely employed in watermarking[1,2,3,4]. Consequently, it can be naturally extended to other n-gram watermarking methods.

To support our claim, we extend our method on two additional n-gram-based advanced distortion-free watermarking: $\gamma$-reweight[3] and DiPmark[4], the results are presented in Table 13 and 14 in this anonymous link, which demonstrate Demark’s strong generalization capabilities beyond just the KGW framework.

We are not able to evaluate our attack method on Undetectable watermarks because: a) it is not n-gram-based, b) the vocabulary size of the LM in their paper is only 2, and it is not trivial to extend their method to models with larger vocabulary size c) it’s a pure theoretical paper without any code implementation.

Q2: Furthermore, the second contribution regarding industry-scale applicability is questionable. It is unknown whether ChatGPT employs watermarking, and if so, which specific technique. Simulating a soft watermark on top-20 tokens and demonstrating its removal with DE-MARK does not convincingly demonstrate effectiveness against a real-world, industry-level watermarking implementation.

A2: Whether ChatGPT employs a watermark by default is irrelevant to our study. In our experiments, we manually embedded a soft watermark into ChatGPT outputs and successfully removed it using Demark. Moreover, as noted in various prior works [1,2,3,4], the choice of LLM has minimal impact on the effectiveness of watermarking techniques. Our extensive results across LLaMA 3B, LLaMA 8B, and Mistral 7B further confirm that Demark is robust to the choice of underlying LLM. Finally, both Reviewer 5v1A and eS2n acknowledged that our case study on ChatGPT is informative and valuable.

Q3: Therefore, it is recommended that the authors revise the title to accurately reflect the limited scope of their method, specifically its applicability to soft n-gram watermarks. The current title is overly broad and implies a capability to remove a wider range of watermarks than is actually demonstrated.

A3: Our method is designed for n-gram-based approaches and is applicable beyond just soft n-gram watermarks, as demonstrated by our experiments in Tables 13 and 14, available in this anonymous link. In response to the reviewer's recommendation, we will revise the title to emphasize our focus on n-gram watermarking.

We would be more than happy to further discuss any additional questions or concerns you may have.

[1] A watermark for large language models, Kirchenbauer et al., ICML 2023
[2] On the reliability of watermarks for large language models, Kirchenbauer et al., ICRL 2024
[3] Unbiased Watermark for Large Language Models, Hu et al., ICLR 2024
[4] DiPmark: A Stealthy, Efficient and Resilient Watermark for Large Language Models, Wu et al., ICML 2024

Thank you for your valuable feedback and thoughtful suggestions, which have greatly helped improve the quality of our work.

Q1 The experimental results don't include variance measures or statistical significance tests across multiple runs.

A1: Firstly, evaluating whether a sentence is watermarked does not require running multiple statistical significance tests because the watermark detection algorithm itself is deterministic and already employs a statistical hypothesis test [1]. Specifically, during detection, we set a theoretical false positive rate (e.g., 0.1%), calculate the corresponding statistical threshold, and then flag the sentence as watermarked if its score exceeds this threshold. To the best of our knowledge, most watermarking papers[1,2,3,4] do not perform multiple-run tests, and we have adopted similar settings.

Moreover, we provide results across multiple datasets and LLMs to mitigate the effects of randomness.

Q2 Missing computational efficiency analysis/analysis of the number of queries.

A2: Please refer to Response A2 in our rebuttal to reviewer 5v1A for a detailed discussion on query efficiency.

Q3 Some formulas need to be polished in formats. Some references should be referred to correctly

Thank you for your valuable suggestion. We sincerely apologize for the mistake. We will revise the formatting and correct the references accordingly in the version.

Q4 In section 4, the authors should point out that detailed proofs of theorems are in Appendix XXX.

We apologize for the confusion. In the revision, we will clearly link the proofs of the theorems within the main body of the text.

Q5 Comparision against Attacking llm watermarks by exploiting their strengths

The setting of our work fundamentally differs from that of Pang, Qi, et al. [5], which represents an early exploration of watermark removal under relatively simple assumptions. Specifically, their attacks are limited to the following scenarios:

• Naive token editing (Sec. 4): This method inevitably leads to degraded text quality.

• Multi-key scenario (Sec. 5): This is a trivial case where a simple averaging technique suffices, in contrast to our focus on the more practical and challenging one-key scenario.

• Detector-available scenario (Sec. 6): Prior studies, including this one, have shown that attacks in this setting are relatively easy. In contrast, our work addresses the more difficult detector-unavailable scenario (D0 setting, detailed in Sec. 3.1, Lines [138–143]).

Therefore, we believe a direct comparison would be neither meaningful nor informative.

Q6 I would like to see a detailed comparison between the selection of h

We kindly note that additional results regarding the selection of $h$ are provided in the Appendix Figure 6 and Figure 7.

In response to the recommendation, we have also included results for identifying the prefix n-gram length with $h$ = 2, 4, 6 and 8 in Figures 9–10, available via this anonymous link.

The results show that our method generalizes well across different selections of $h$.

Q7 Theorem 4.2 provides bounds on distribution gaps, but there's no experimental validation of how tight these bounds are in practice. Can you provide empirical measurements of actual distribution gaps compared to the theoretical bounds?

We empirically evaluated our method on 3,000 token distributions from the MMW Book Report dataset using the LLaMA3.2 3B model. Our results show that $\mathbb{E}[\frac{\mathbb{TV}(P_R,P)}{\epsilon_1 f_2(\epsilon_1,\epsilon_2)+ (1-\epsilon_1) f_1(\epsilon_1,\epsilon_2)}]=0.328$ indicating that the distribution gap is well-controlled by the bound.

Moreover, our GPT score evaluation results in Table 1 and Table 2 further confirm that the generated text remains highly consistent with the original in distribution, demonstrating minimal distribution distortion and strong preservation of text quality.

[1] A watermark for large language models, Kirchenbauer et al., ICML 2023
[2] Robust Distortion-free Watermarks for Language Models, Kuditipudi et al., TMLR 2023
[3] Unbiased Watermark for Large Language Models, Hu et al., ICLR 2024
[4] DiPmark: A Stealthy, Efficient and Resilient Watermark for Large Language Models, Wu et al., ICML 2024 [5] Attacking LLM Watermarks by Exploiting Their Strengths, Pang et al, ICLR 2024 Workshop

Q1: Would DE-MARK still work against modern watermarking techniques (e.g. distortion-free methods like Gumbel watermark by Aaronson)? Is it specially designed for KGW?

A1: Our proposed methods can be generalized to most n-gram-based methods, and we add additional experiments for two popular distortion-free n-gram-based watermarking algorithms to support our claim, $\gamma$-reweight[1] and DiPmark[2]. Please see Table 13 and Table 14 in this anonymous link. The results show that our method can effectively remove the watermarks.

However, it is not possible to remove the Gumbel watermark, as it only produces a one-hot probability distribution, i.e., assigning a probability of 1 to a single token and 0 to all others. This output lacks sufficient information to theoretically bound the difference between the original and post-removal distributions of the language model.

Q2: Analysis of query efficiency?

A2: We first present a detailed time efficiency analysis to show that our time cost is acceptable, then we show some acceleration methods to further reduce the time cost.

Time Efficiency Analysis

The experiments were conducted on a single RTX 6000 Ada GPU. Table 11 and Table 12 in this anonymous link present the time efficiency of watermark stealing and removal with respect to varying numbers of queries.

For De-mark, we require $m(m - 1)$ queries per token. In our experiments, we set $m = 20$, resulting in a total of 380 queries per token. While this number may seem high, it is important to note that repeated querying is a necessary strategy to comprehensively gather the required information.

Despite this, our experimental results indicate that the time cost is acceptable when compared to the baseline. The computation remains efficient due to the following reasons:

• Each query is very short;
• The query templates are identical across inputs, allowing for the reuse of most pre-computed key-value pairs, which significantly accelerates computation;

Acceleration method

For watermark identification, the time cost is already low, and we find no additional optimization necessary.

For watermark removal and exploitation, we can achieve 2$\times$ to 4$\times$ speedup by randomly removing token pairs in Alg. 1. This introduces a trade-off between removal performance and inference speed. Additionally, increasing the value of $\eta$ can yield improved outcomes, the results are presented in Table 15 in the anonymous link.

A more sophisticated token pair clipping strategy may also lead to further performance improvements.

Q3: The paper does not extensively evaluate settings where log probabilities are entirely unavailable (a common scenario for many commercial LLM APIs).

A3: Regarding watermark identification and exploitation, we kindly point out that we have conducted extensive experiments in the black-box setting (i.e., where log probabilities are entirely unavailable), as shown in Tables 2, 3, and 9, and Figures 4, 5, and 7.

As for watermark removal, as discussed in Section 3.1, when log probabilities are completely unavailable, it is impossible to bound the gap between the original and post-removal distributions of the language model. This is because the output provides only a single token, which is insufficient to recover the full distribution.

Q4: The assumption about Gaussian noise also seems like a strong and arbitrary assumption

A4: Thank you for pointing this out. Actually, in Appendix E. Proof of Theorem 4.1, the gaussian noise assumption is not necessary for the proof, we only require the noise to be symmetrically distributed (i.e., $P(\epsilon=x)=P(\epsilon=-x),\forall x \in \mathbb{R}$), which is a mild and intuitive assumption. We will update the assumption accordingly in our revision.

Q5: How fast does the estimate converge? How many queries are required to decode a watermark

A5: Demark has relatively low computational cost, which enables us to even increase the number of queries for more accurate estimations. Please refer to Figure 8 in this anonymous link for the convergence speed of estimating $\delta$. We evaluate the performance using different values of $m$ in Algorithm 4 and vary the parameter $c$ (set to 1, 2, 5, 10, 20, 50, and 100) to generate different numbers of queries.

[1] Unbiased Watermark for Large Language Models, Hu et al., ICLR 2024
[2] DiPmark: A Stealthy, Efficient and Resilient Watermark for Large Language Models, Wu et al., ICML 2024