Unremovable Watermarks for Open-Source Language Models

Can you address the two issues of robustness (to small change in the output) and the undetectability of the output (compared to the non-watermarked model) ?

We prove that the watermark is robust to an adversary that changes the weights of the model; this is why we use the term “unremovable” rather than “robust,” which typically refers to an adversary that changes the response but not the model. We show empirically but do not prove that our watermark is robust to substitution attacks (Figure 4). We agree that showing how unremovability translates to robustness would strengthen the paper. Our scheme is not distortion-free or undetectable. Like Zhao et al. and Kirchenbauer et al., we instead prove a bound on the amount that our watermark changes the output distribution; our proof is via our quality notion. This fact is buried in the proof of Theorem 1 in the appendix; we will emphasize it in the main body. We also show empirically how quality is affected by the watermark, in Figure 3b.

In your experiments, how do you measure that the utility of the model has not degraded after adding the watermark. I know that you have an oracle that measures the degrading, but then you instantiate the oracle using mathematical formulas regarding the model. But how do you make sure that this reflects the actual quality of the model’s output? For example, you could use specific metrics or human evaluation methods to assess output quality more directly.

In our experiments, we use Mistral-7B-Instruct as a quality oracle, following similar work (Piet et al.).

Can you discuss why the assumptions are fine? There are 3 explicit assumptions and (multiple) implicit assumptions in the statement of Theorem 1 (eg., “let C be such that…” or “c_2-high quality…”) I think that discussion is needed before calling assumptions reasonable (instead of putting the word reasonable in the theorem statement).

We discuss the assumptions when they are introduced, in Section 5.2 before Theorem 1. If you have already seen this, can you please be more specific about your concerns?

Can you argue either way about the effect of fine tuning in your watermarked model?

We will add discussion about this. We show that removing the watermark either requires knowledge about the distribution of high-quality text, or results in a model with degraded quality. Formally, our result implies that if fine tuning alters only the last layer of the model, it either fails to remove the watermark, or it uses knowledge of the distribution of high-quality text (e.g., via high-quality training data).

In your experiments: can you be more explicit about what your attacker is? e.g., using a pseudocode.

Yes, we will add pseudocode. We also describe the attacks simply here: In Figures 3a and b, the attacker adds noise to the last layer biases where the noise added to each bias is drawn independently from distributions $N(0, \epsilon^2)$ (1x attack perturbation), from $N(0, (2\epsilon)^2)$ (2x attack perturbation), and $N(0, (5\epsilon)^2)$ (5x attack perturbation) respectively. In Figure 4, the attacker randomly selects a subset of tokens in the response, of the size given on the x axis (the substitution budget). It then substitutes them with random tokens.

Thanks for the clarifications.

Re assumptions: I am not claiming them to be unreasonable; I just cannot get a good sense of them by reading the (sometimes minimal) discussions. E.g., I still don't understand Assumption 1's discussions, and I don't understand how the restrictions on C in Theorem 1 should be interpreted. you mentioned that this is discussed in Section 5.2 before Theorem 1, but Theorem 1 is before Section 5.2. If you give a more accurate pointer, I will double check.

Also, I wanted to comment on something that you seem to be commenting on it yourself first. As I understand, un-removability is not a strictly stronger property than black-box robustness, right? Namely, if we prove a model to be non-black-box robust, it is not clear what kind of black-box robustness properties we can infer? That makes the formulation of un-removability a bit less appealing, but I have no suggestions on how to fix it, so I do not take it against the paper.

All in all, I find the problem if this paper very interesting, but the presentation makes it a bit hard to judge how much actual of a jump is made towards this new (interesting) direction.

In summary, I am a bit more positive about the paper now and increased my score.

Thank you for your response.

• If I understand correctly, your approach addresses threats in scenarios where an attacker has full white-box access to the model's weights. In this context, the threat model assumes that the attacker aims to remove the watermark from the model without compromising the quality of the text it generates. Your unremovability guarantees suggest that this is either impossible or highly unlikely under these conditions. While the model-based removability guarantees are theoretically interesting, I am concerned that this scenario may not align with practical applications, as most LLM providers typically only offer black-box access. I may be wrong, maybe you should try to explain your motivations better.

• For open-source LLMs, an attacker with white-box access is unlikely to alter the model's parameters if high-quality paraphrasing can remove watermarks effectively. I mean, why would I try to remove the watermark from the model's param and risk degrading text quality if I have access to tools like GPT-4, Gemini, Claude, or other well-trained open-source LLMs that can easily generate high quality paraphrased versions of watermarked text. This suggests that unremovability should be inherent to the text itself, rather than dependent on the model, and that, intuitively is impossible.

• To strengthen your claims,why not provide empirical evidence demonstrating that your theoretical guarantees hold practical value. A thorough evaluation against various attacks such as translation, paraphrasing, etc, would greatly pass the message across, only if you beat other watermarking algorithms.

For now, I will maintain my current score but encourage you to address these points to make a stronger case for your contributions.

Now, the authors claim to have introduced the first watermarking scheme for open-source LLMs. What do they mean by this? There are many watermarking schemes which could be deployed in open source LLMs, so this claim might not be right, as the proposed scheme can also be deployed in closed source LLMs by the model owners. Which leads to the next question. If the LLM is open source, what exactly is the benefit of watermarking when the attacker has direct access to model's weights. Can the authors expand more on their motivation?

What we mean is that our watermark is the first to have any provable robustness guarantee when the attacker has access to the model’s weights. While any watermark could be deployed in an open source setting, existing schemes would be trivially removable. In contrast, we prove that even when the attacker has this knowledge, removing our watermark requires degrading the quality of the model. This shows that watermarking indeed has a benefit in an open source setting. The benefit of watermarking when the attacker has direct access to the model’s weights is that it gives us the capability to identify model-generated content. The fact that the attacker has access to the weights makes it challenging to construct a watermark that is not easily removable; this is exactly the problem we study in this paper.

The proposed approach embeds watermark signals to the bias of the last layer's neurons. There is another approach by ByteDance that injects watermark into the LLM weights by finetuning (https://arxiv.org/pdf/2403.10553). Why is there no comparison with this approach? Infact, why is there no comparison with other watermarking schemes at all?

The ByteDance paper achieves only heuristic robustness but not provable unremovability. We focus on provable robustness/unremovability guarantees, and are the first to achieve any unremovability guarantee in the open-source setting. We do not perform an experimental comparison, as our main contribution is not a scheme with optimized practical parameters. We will include more thorough discussion of related work, such as ByteDance.

There are adaptive ways to bypass watermarks. One is by using adaptive paraphrasers. If the proposed watermark scheme is unremovable, yet detectable, why are there no empirical results proving the 'unremovability' claim using adaptive paraphrasers, or even normal paraphrasers like Dipper, or even using open source LLMs for paraphrasing.

Our unremovability guarantee is that an attacker without sufficient knowledge of high-quality text must either compromise quality or fail to remove the watermark. The amount that quality is compromised depends on the attacker’s knowledge of high-quality text. Using paraphrasers is a practical instantiation of this tradeoff. If the paraphrasers largely preserve text quality and remove the watermark, it is because they leverage knowledge about high-quality text. On the other hand, paraphrasers that do not embody sufficient knowledge about high-quality text will yield poor-quality text but may remove the watermark. We acknowledge that an attacker with access to a high-quality paraphraser, or unwatermarked open-source model, can remove the watermark– this is inevitable, and this is why we prove unremovability only against an attacker with limited knowledge.

How efficient is the detection process? How many tokens does it require to detect the proposed scheme, especially using its optimal hyperparameters? I feel the experiments the authors provided to prove the efficiency and strength of this approach are not enough.

We show that our watermark is detectable in 300-token responses. We do not attempt to optimize our parameters, as we aim to show a proof-of-concept and not a deployment-ready scheme. Our primary message is that open-source watermarking is theoretically possible, and that our theoretical modeling assumptions are reasonable enough that our provable results carry over into practice. We leave concretely optimizing the scheme in practice to future work.

In answer to your questions:

In Theorem 1 shouldn't the distribution over $w^*$ be centered at $w_{wat}$ and not 0? This is also present in the proof and Theorem 3. Is this a mistake or my misunderstanding of the statements?

You are correct; these distributions should be centered at $w_{wat}$.

L145 states that Aaronson (2022), Christ (2024) and Fairoze (2023) are based on partitioning the tokens into red and green lists. Can you elaborate on this view of these methods, as my understanding was that they are quite different and do not use the red/green concept?

Aaronson and Christ et al. use hash functions evaluated on a previous portion of the response to determine a set of tokens whose probabilities to increase in the next sampling step. One can interpret this set of tokens with increased probabilities as the “green” list, and the other tokens as the “red” list. In this view, Aaronson and Christ et al. randomly choose a green/red partition in each sampling step, and increase the probabilities of the green tokens. Fairoze et al. is similar except that the green/red lists consist of n-grams rather than individual tokens. That is, Fairoze et al. randomly choose a set of (“green”) n-grams whose probabilities to increase in each sampling step.

Were OPT models modified to use the final layer bias to enable experimental evaluation?

Yes, OPT models were modified to use the final layer bias. We take the unwatermarked model to be OPT with all zeros as the final layer biases, and report quality scores for unwatermarked text as such. The same could be done for a model that is released open-source. Ideally, the biases in the last layer should be trained rather than set to all zero as in OPT. The fact that we assume that the last-layer biases are trained does restrict the class of models we consider; however, this class is still quite broad, and if one wished to release a watermarked model one could easily train the last layer biases.