Towards Codable Watermarking for Injecting Multi-Bits Information to LLMs

Q1: Regarding the text quality metric:

A1: We chose ppl since it is widely accepted for evaluating the quality of text generation.[1,2] Besides, in experiments for llama-7b/13b, we use a much larger model, llama-33b to calculate ppl, which may avoid some problems you mentioned about ppl. Also, we provide a case study to show the text quality [The case study is attached in another comment due to the character limitation of Openview].

[1] https://arxiv.org/abs/2306.17439

[2] https://arxiv.org/abs/2307.16230

Q2: Regarding the theoretical bound.

A2: Thank you for your suggestion. The derivation of a theoretical bound for the single-bit case is straightforward, as it involves simply counting the 'green tokens'. However, in multi-bit scenarios, the challenge lies in calculating the likelihood that any message, except for the accurate one, possesses a greater number of 'green tokens' than the accurate message. This calculation tends to be complex and often yields theoretical bounds that aren't practically applicable. We will try to explore this further in the future to see if any good bound can be derived.

Q3: Regarding the questions about watermark accuracy metrics: (1) Does a successful sample only count if all 20 bits are correctly recovered and the watermark is correctly detected (2) The threshold of $1-10^{-5}$ and AUC metric.

A3: To address your points:

(1). Yes, a sample is deemed successful only when all 20 bits are accurately recovered, and the watermark is correctly detected.

(2). Similar to the reason we discussed in Q2, p-value is not directly calculable in multi-bit watermarking scenarios as they are in single-bit ones. Instead, we compute $P_w(m|\mathbf{x})$ to serve as a confidence score for whether a given message $m$ is watermarked in text $\mathbf{x}$. This is achieved through the following steps:

a. We first calculate $P_w(\mathbf x|m) = \sum_{l=1}^L \log P_w\left(x_l \mid m^{\prime}, \mathbf{x}_{:(l-1)}\right)$, the latter can be direclty computed based on our design of P_w.

b. By applying Bayes' Theorem, $P_w(m|\mathbf{x})$ is proportional to $P_w(\mathbf{x}|m)$. With the normalization of $P_w(\mathbf{x}|m)$ over all $m$s, we derive $P_w(m|\mathbf{x})$.

For the threshold of $1- 1 \times 10^{-5}$: Our tests on 10,000 non-watermarked, human-written texts indicate that $\arg\max_m P_w(m|\mathbf{x})$ falls below this threshold, suggesting it's stringent enough to avoid the false positives you mentioned (FPR=0). (We think it is enough since Kirchenbauer [2023a] verified an FPR=0 on a smaller sample of 500 human-written texts.) We extract the message only when it is above this threshold, ensuring no human-written text is falsely flagged as watermarked.

Lastly, since multi-bit scenarios aren't binary classifications, AUC is not applicable. We focus on the success rate of correctly extracting messages when above the threshold, where no human-written text is misidentified as watermarked

Q4: Regarding the comparison to steganography.

A4: Steganography methods have to know the prompt before the generated text so as to get extract model logits when extracting message. This is unavailable in the watermark setting, making their transferring to watermark scenarios impossible. (To somewhat, this also indicates watermark is harder than steganography).

For Yoo et al. [2023], this is a post-processing method. It does not integrate watermarks with LLM generation. It performs watermark using masked language models, rather than much powerful LLMs, inevitably leading to poor text quality. In experiments, we found this method tends to perform trivial and possibly inappropriate substitutions. Here are some cases (the original token is shown in the brackets after the changed token):

The KPA was(is) the military arm of the ruling Workers' Party of Korea.

The U.S. military(government) spends more money than it collects in tax revenues.

"There is still a lot less(of) work to be done."

You can also find such situations in the case study provided by Yoo et al. [2023] in their appendix.

Yoo et al. [2023]: https://aclanthology.org/2023.acl-long.117/

I apologize for the delayed response. I appreciate the author(s)'s efforts in putting together the rebuttal. All my questions were addressed with clarity, and I am very happy with the answers. I decided to raise my rating to 6; I believe that this is still a borderline case, and the work has two main limitations preventing it from being practical: (1) the watermarking efficiency/accuracy, and (2) the decoding cost and the requirement of a proxy LLM. Regardless, this is one of the first papers to tackle this problem (along with a couple of other concurrent works) so I am willing to overlook these limitations.

Finally, I just want to add a few future suggestions in case the author(s) find them helpful. I'm not asking the author(s) to do these experiments at this point, but just want to throw out some ideas I got:

1. I can see a future improvement or a follow-up work trying to use a cheaper way to do the balancing instead of a proxy LLM. Vanilla and LLM-balancing are two ends of the spectrum in terms of the "balancing accuracy" as well as computation costs. I suspect that there is a way to strike a good trade-off here, i.e., with a tiny cheap model for balancing that may be "good enough" for watermarking. Exploring this trade-off may be very interesting.
2. I would love to see the number of message bits (or coding rate) that can be achieved with X% (say 5%) decrease in perplexity and Y% (say 99.9%) success rate. I am more concerned about success rate (or accuracy) than perplexity because this type of task has a really high cost for an incorrect prediction whereas higher perplexity does not always mean a lower quality for some downstream tasks.

Q1: Regarding how to obtain Eq. (5) from Eq. (16) in the Appendix.

A1: The mathematical formulation is correct. In Eq. (16), we first let $\delta=\frac{L}{\lambda}$, and we can get

$\max_{t} [ \sum_{l=1}^{L} \log P_{w}(t_{l}|m,t_{:(l-1)}) - \max_{m' \neq m} \sum_{l=1}^{L} \log P_{w}(t_{l}|m',t_{:(l-1)}) + \frac{1}{\delta} \sum_{l=1}^{L} \log P_{LLM}(t_{l}|x^{prompt},t_{:(l-1)}) ].$ Then, let $\hat m=\arg\max_{m' \neq m}\sum_{l=1}^{L} \log P(t_{l}|m',t_{:(l-1)})$, the above target can be further formulated as $\max_{t} [ \sum_{l=1}^{L} \log P_{w}(t_{l}|m,t_{:(l-1)}) - \sum_{l=1}^{L} \log P_{w}(t_{l}|\hat{m},t_{:(l-1)}) + \frac{1}{\delta} \sum_{l=1}^{L} \log P_{LLM}(t_{l}|x^{prompt},t_{:(l-1)}) ].$ This is equivalent to $\max_{t} [ \delta \sum_{l=1}^{L} (\log P_{w}(t_{l}|m,t_{:(l-1)}) - \log P_{w}(t_{l}|\hat{m},t_{:(l-1)}) )+ \sum_{l=1}^{L} \log P_{LLM}(t_{l}|x^{prompt},t_{:(l-1)}) ],$ which is just the same as Eq. (5).

Q2: Regarding the performance difference between using a smaller proxy-LM in Eq. (11) and using the original LM in Eq. (9).

A2: Thank you for this question, and we agree that there is a trade-off between the success rate, text quality and encoding efficiency when choosing proxy-LM. We included the original LM in the comparison of Figure 2(a), and derived the following table:

The original LM choice does perform better than smaller proxy-LMs, but is slower than small proxy-LMs like GPT2.

Q3: Regarding the confusion about Figure 2(a): whether text quality is missing.

A3: Apologies for any misunderstanding. To clarify, in Figure 2(a), we control the ppl to the same (3.4 here) and report the corresponding watermark success rate for different $LM_{proxy}$s. This approach ensures that the comparison takes into account text quality. We prioritize illustrating the variation in watermark success rates at a fixed text quality, which we believe may be of greater interest than the inverse relationship. Additionally, comprehensive results concerning text quality and watermark success rates can be found in Appendix G.1, illustrated in Figure 3. Regarding the caption for Figure 2(a), the term 'quality' was meant to encapsulate the balance achieved between text quality and watermark success rate. We acknowledge this may have caused confusion and will amend the caption to better convey this meaning.

Besides, since we control the ppl and watermark success rate by $\delta$, achieving an exact ppl of 3.4 is challenging. To estimate the watermark success rate under a ppl of 3.4, we have employed linear interpolation between the two nearest (ppl, watermark success rate) points.

Q4: Regarding the machine paraphrasing attacks.

A4: In this paper, we demonstrated that our method is robust to two commonly used attacks: copy-paste attacks and substitution attacks. However, it is a common and great challenge for all current watermark methods to defend against paraphrase attacks. [1] Our method also suffers from this problem when we try to attack it with gpt3.5. Ensuring the robustness of multi-bit watermarks against paraphrasing attacks is an even more significant challenge than the one-bit situation, since we can not allow one bit of the message to be corrupted. This issue is designated for exploration in our future research.

[1] https://arxiv.org/pdf/2303.11156.pdf

Q5: Regarding the experiments with more sampling strategies like greedy sampling or top-p sampling:

A5: While we acknowledge the potential benefits of exploring a broader range of sampling strategies, such as greedy or top-p sampling, constraints in time and resources have limited our capacity to conduct extensive experimentation in this area. We aim to expand our investigation into these strategies in the future version.

Q1: Regarding the writing and the intuition parts.

A1: Thank you for your kind suggestion. We will proofread the paper carefully and try to add more intuition parts to make our paper more readable. In the following, we will answer your questions one by one to help you to better understand our paper.

Q2: Regarding the question of whether the goal is to separate the watermarked text from unwatermarked text.

A2: Yes, and to be more concrete, the goal of Eq. (3) is to separate the watermarked texts encoded with the message $m$ from other texts that are not encoded with $m$. However, our method can also distinguish watermarked machine-generated texts from human-written texts according to the results in Figure 2(b).

Q3: Regarding the questions about the message encoding process.

A3: Yes, the message we want to encode is $m$. Furthermore, each $m$ can be represented by a unique multi-bit 0-1 string from an entire message space $M=${$0,...,2^{20}-1$}. Then, during generating each token, we can use the above string of $m$ to calculate the random seed, calculate the message logit of each token, and split the vocabulary in a probability-balanced way. Finally, the next token is sampled only from the available part of the two splits. Therefore, as we can see, the generation process of each token depends on the information of $m$, which helps us to encode $m$ into the whole text.

Q4: Regarding the question about the decoding process. Comparison with Zou et al. Universal and Transferable Adversarial Attacks on Aligned Language Models.

A4: In the decoding process, the candidate string is only from the pre-defined set $M=${$0,...,2^{20}-1$} . Therefore, the decoded string can only be one of the 0/1 strings in M rather than another arbitrary string like the adversarial string in Zou et.al. And, after obtaining the decoded 0/1 string, we can map it back to its original corresponding text message. We will cite and compare this paper in our future version.

Q5: Regarding the question "Is the model logit used to guarantee the generation quality".

A5: Yes, the model logit measures how likely is a specific token to be the next token, and higher model logits generally lead to higher text quality.

Q6: Regarding the question "Is the message logit used to add watermark"?

A6: Yes. The message logits are decided by the message $m$, and by adding the message to the model logits in the next token's generation procedure, we successfully encode the information of $m$ into the generated text.

Q7: Regarding the question "Does a larger L give a better watermark and higher quality"？

A7: Yes, refer to the answers in A5 and A6.

Q8: Regarding the question "Do Eq. (7) and Eq. (9) simply find the words in a pre-defined vocabulary"?

A8: Yes. This pre-defined vocabulary $V_{m,t_{:l-1}}$ contains the words that have high model logits, which ensures that we can sample a $v$ that not only has significantly higher message logits $P_{w}$ than that of other $v'$, but also is a reasonable word that is high likely to be the next token.

Q9: Regarding the question "What does sigma mean".

A9: $\sigma$ controls the probability of the tokens with high model logits to be included in the subset $V_{m,t_{:l-1}}$. Setting larger $\sigma$ will more likely include more tokens with high model logits in the available subset, but will also decrease the diversity of the splittings of $V_{m,t_{:l-1}}$ across different $m$s and make the message logit lose its original function.

Q10: Regarding the question "How does Eq. (10) encode quality".

A10: In Eq. (10), we only assign the model logits to the tokens that are included in the subset $V_{m,t_{:l-1}}$. As stated above and explained in the paragraph below Eq. (9) in the main paper, this subset should contain some tokens with relatively high model logits. Therefore, we ensure that the next token to maximize $L_{m,x^{prompt},t_{:l-1}}$ can be sampled from these reasonable tokens instead of arbitrary tokens caused by the random vocabulary splitting of Vanilla-Marking.

Q1: Regarding comparing CTWL with concurrent studies.

A1: Actually, they were updating their papers a few days ago before the submission deadline, so we do not have time to compare them at that that time. And after studing the concurrent studies by Yoo et al.[1] and Fernandez et al.[2], we found that Vanilla-Marking can cover these works, since

(1) Yoo et al. concentrates on bit-wise accuracy and strategies for bit allocation to text tokens, while our work is geared towards the accuracy of encoding and decoding entire messages. This is inherently more challenging as it is akin to raising bit-wise accuracy to the power of the number of bits in a message, which would result in a significantly lower performance under our metric for the study by Yoo et al. Thus, the bit allocation strategy of Yoo et al. can not be transferred to our settings, and their method, if excluded this allocation strategy, can be seen as equivalent to Vanilla-Marking.

(2) Fernandez et al.'s research, on the other hand, aligns closely with what we refer to as Vanilla-Marking in our paper. Although they employ a circular-shift method to expedite the generation of a secret key, we have similarly optimized the hash function in our own implementations of Vanilla-Marking and Balance-Marking, as can be seen in our 'hash_fn.py' code. When considering text quality and watermark success rate, Fernandez et al.'s method should be same as Vanilla-Marking. Additionally, their scope is limited to messages in the range of 1-1000, while our approach extends to a much larger range of 1-2^20, (i.e., 1-1,048,576).

[1]https://arxiv.org/abs/2308.00221

[2]https://arxiv.org/abs/2308.00113

Q2: Regarding using other metrics to compare the text quality between CTWL and other methods.

A2: We adhere to the approach established by Kirchenbauer et al. (2023a) in utilizing perplexity (ppl) as a measure of text quality. Perplexity is widely accepted for evaluating the quality of text generation.[1,2] Alternatives like BLEU and ROUGE are less appropriate for text watermarking. The watermarking process inherently involves substituting texts to their alternatives, which may not align well with the n-gram overlap metrics that BLEU and ROUGE emphasize. Also, in experiments for llama-7b/13b, we use a much larger model, llama-33b to calculate ppl.

[1] https://arxiv.org/abs/2306.17439

[2] https://arxiv.org/abs/2307.16230

Q3: Regarding the comparison between CTWL and the previous methods that inject information into text by post-processing.

A3: We focus on watermark integrated with LLM generation, since the post-processing based methods will predictably lead to a low-quality machine-generated text. The major reason for this is that the abilities of masked-language-modeling-based models used in these post-processing-based methods (e.g., BERT) are far away from the current generative language models (e.g., LLaMa) for generating the texts, using incompetent models to replace the words in the sentences generated by powerful LLMs inevitably destroy the quality of the texts.

We tried Yoo et al. [2023], a sota post-processing method that has also been mentioned by Reviewer qLTC. However, we find this method tends to perform trivial and possibly inappropriate substitutions, as we have discussed above. Here are some cases (the original token is shown in the brackets after the changed token):

The KPA was(is) the military arm of the ruling Workers' Party of Korea.

The U.S. military(government) spends more money than it collects in tax revenues.

"There is still a lot less(of) work to be done."

Q4: Regarding the comparison between the computation time of CTWL and that of previous methods.

A4: Previous methods are not able to conduct multi-bit watermark and we are the first work to integrate it with LLM generation. So, there is no proper baseline that can be directly compared with. As an alternative choice, we view Vanilla-Marking as a baseline (though it is also proposed by us). We have included a comparison of the computational costs of Balance-Marking and Vanilla-Marking (proxy-LM = null) in Figure 2(a). (As we discussed in A1, the very concurrent work can be considered as an equivalent version of Vanilla-Marking, thus, Figure 2(a) also represents the comparison between Balance-Marking and concurrent methods.)

It is worth noting that embedding multi-bit watermarks is inherently more intrusive compared to single-bit watermarking, potentially degrading text quality more severely. So, it is necessary for a trade-off between text quality and efficiency. Balance-Marking allows us to select different proxy-LMs to align varying preferences for quality and efficiency across diverse scenarios.