Advancing Beyond Identification: Multi-bit Watermark for Large Language Models

Responses to Weaknesses [1]

Thank you for the very detailed feedback. We tried our best to address your concerns below. Please let us know if there are remaining concerns that prevent you from raising your scores. ## Significance Please note the next paragraph is nearly identical to the general response. The first point raised by the reviewer was that the current decoding-based watermarks cannot be enforced to open-sourced language models. As answered in the general response, we, nonetheless, believe studying watermarking methods for close-sourced language models is important because of its prevalence. The largest API provider, ChatGPT, had over 206 million monthly unique visitors in April, while Bard had over 140 million monthly unique visitors in May. Moreover, companies in Korea and China have also launched servicing their close-sourced models as API or apps (Baek, 2023; David, 2023). As of now, the most capable models are arguably close-sourced and if this trend were to continue, it is likely that the number of users will not decline. Watermarking is one of the solutions that can mitigate malicious uses of closed-sourced language models. Having a reference point in academia strongly incentivizes the owners of closed-sourced models to apply them. The second point raised by the reviewer was regarding achieving a satisfactory TPR with a low enough FPR. We agree. However, we would like to note that our work is one of the first works directly watermarking language model outputs along with the two concurrent works uploaded in July 2023 (Fernandez et al., 2023a; Wang et al., 2023). In fact, watermarking language model outputs in a zero-bit manner (Kirchenbauer et al., 2023) was proposed less than a year ago. We believe this work opens up new research directions on top of the newly proposed zero-bit watermark methods. We do not _claim_ to propose a ready-made solution for embedding multi-bit watermark onto language model outputs. We will revise our paper in the following days to avoid any confusion. Another point to take into consideration is that from a protection standpoint, enforcing the adversary to take evading measures is itself valuable if it is costly. The best -- arguably -- paraphrasing model, ChatGPT is behind paywall when called via API. ## Comparison to Steganography The below response is identical to the general response. Watermarking also differs from steganography works (Ziegler et al., 2019, de Witt et al., 2022) in this aspect they do not consider possible corruption. In particular, Ziegler et al. rely on sequential arithmetic coding of every token. Thus, substituting or removing the first token of the cover text will alter the entire extract message. We will try to empirically demonstrate this in the response period, should time allow. ## Methodology **List decoding parameterization** Thank you for the suggestion. While we did consider using a confidence threshold, this was difficult to realize given that the prediction was uncalibrated. We opted for a fixed-sized list in the experiment for simplicity. Our result regarding list decoding was presented to show the effectiveness of list decoding in identifying the possible candidates, rather than to claim that this is actually achievable without any further means. ). In Figure 6c, the validity of the confidence measure used in list decoding is demonstrated by showing that it is inversely proportional to the error rate. **Practicality of list decoding** In practice, list decoding is especially useful because provenance tracing via watermarking is far from finding an exact solution, but narrowing down the possible leakage points for a more detailed inspection that may costly. This is because the decoded message is not error-free in the real-world and thus, one cannot finalize the decision by watermarking alone. For instance, when encoding the timestamp list decoding outputs the _range_ of time, for which the practitioners to manually inspect and find suspicious activity. When encoding the exact user ID, list decoding will output a list of IDs with varying characters in certain positions. Then, the practitioners will consider the IDs that actually exist in their systems and further inspect other details such as recent user activities.

Responses to Weaknesses [2]

**Practicality of list decoding** In practice, list decoding is especially useful because provenance tracing via watermarking is far from finding an exact solution, but narrowing down the possible leakage points for a more detailed inspection that may be costly. This is because the decoded message is not error-free in the real-world and thus, one cannot finalize the decision by watermarking alone. For instance, when encoding the timestamp list decoding outputs the _range_ of time, for which the practitioners to manually inspect and find suspicious activity. When encoding the exact user ID, list decoding will output a list of IDs with varying characters in certain positions. Then the practitioners will consider the IDs that actually exist in their systems and further inspect other details such as recent user activities. ## Experiments: metrics and comparison to KGW zero-bit watermark* We will revise the paper to include the true positive rate as well. Below we present TPR at different FPR thresholds shown in Table 6. This uses 500 positive (watermarked) samples and 1000 negative samples at 250 tokens. | Bit-width | @FPR=1e-3 | |--------| ------| |0 | .983| |8 | .975| |16|.950| |24|.931| |32|.907| As bit-width increases, the detection performance decreases. This is expected as the zero-bit setting is a special case of embedding a single-bit message of $\mathbf{m}=$”0” in all the samples. To give an apples-to-apples comparison, we embed the __same__ 8-bit message ($\mathbf{m}$=”00000000”). This is essentially the same setting with the zero-bit watermarking, but applying only Position Allocation on top of it. To see the true positive rate at lower FPR, we sampled 10,000 negative samples and computed the true positive rate. Below, we show the results for zero-bit and 8-bit. |Bit-width|@FPR=1e-3 | @FPR=1e-4| @FPR=1e-5| |---|--|--|--| |0| 0.997|0.997|0.997| |8 (single message)| 0.994|0.992|0.992| |8 |0.974|0.965|0.965| As expected, embedding the same message using 8-bit shows nearly identical results. Compared to this, actually embedding the unique 8-bit message does lead to performance degradation, but still maintains a fairly high TPR even at FPR=1e-5. In Appendix A.8, we discuss in depth the reason behind this is that the detection metric of non-watermarked (human) text is over-estimated as bit-width is increased. In the revised paper, we will mention this limitation. We leave improving the detection methodology for future research.

Response of Questions

## Responses to Questions **Details regarding hash functions** The hash functions $f$ we used in our experiments are ‘LeftHash’ with $h=1$ and “SelfHash” with $h=4.$ We chose to experiment on the two hashing schemes based on the previous work presented by Kirchebauer et al. (2023b). Both of the schemes were proposed in Kirchenbauer et al. (2023a). LeftHash is simply dependent on the $h$ token(s) left of the current token. This is implemented as $f(x)= s * \sum_i x_i$ where $s$ is a secret key and $x$ denotes the list of $h$ token ids. SelfHash is a bit more complicated as the output depends on the current vocabulary distribution. Please refer to Algorithm 3 of Kirchenbauer et al. (2023a). The results for SelfHash are in Appendix Table 9 and 10. We give the bit accuracy results across equal bits per token here: |Bit |4 |8 |16| 32| 64 | |--|--|--|--|--|--| |LeftHash (h=1)|.961 (.13) |.958 (.09)| .951 (.07)| .913 (.08)| .846 (.09) | |SelfHash (h=4)|.952 (.13) |.953 (.10)| .945 (.08)|.911 (.08) |.850 (.08) | The context width $h$ determines the tradeoff between robustness and privacy (how easy to find out the hash function). Smaller value of $h$ leads to robustness to corruption as the hashing scheme is reliant only on the previous $h$ tokens. On the other hand, this may lead to reverse-engineering of finding out the tokens in the colorlists. Realistically, we believe this is hard even for the easiest case ($h$=1). Assuming the use of the LLaMA-2 tokenizer, the brute-force attack takes $\mathcal{V}^{h+1}= 32000^2 =1e^{9}$, which is a considerable amount of effort. All this presumes that the API call to extracting the watermark is accessible and that the API call shows the total number of colorlisted tokens. Simply displaying the p-value of certain thresholds (e.g. {1e-6, 1e-5, 1e-4, 1e-3, 1e-2}) will make reverse engineering extremely difficult. **In “List Decoding The linear nature with respect to…”, what does “linear nature” refer to?** Thank you for the question! We believe ‘linear’ is not an accurate depiction. Our intent was to characterize the decoding step as a decomposition of each position, which enables decoding without added latency when the message length is significantly long. This is revised in the paper as >The decomposition of the message into each bit position bounds the computation during decoding to the number of tokens. This allows MPAC to output a list [..] **Unclear how scheme works for when $\gamma\neq\frac{1}{r}$** When $\gamma=0.25$ and $r=2$, we are choosing only from the red and yellow lists (out of the four colored lists) in Figure 1. This case was what motivated us to propose Colorlisting to fully utilize the vocabulary partitions. **How is the p-value computed in the last paragraph of Page 7 (experiments)? Why is it computed relative to the second runner-up not the null hypothesis?** The p-value here indicates comparing the two _mean bit accuracies_ of the two best and the runner-up schemes ($\gamma=0.25$ and $r=4, \gamma=0.5, r=2$). The p-value was computed using an unpaired t-test. This is not the p-value of the watermark detection. Sorry for the confusion. **Why $\gamma=0.25, r=4$ outperforms $\gamma=0.5, r=2$? Is this due to the effective bit-width?** Yes. We believe the benefits of having a shorter message length (less positions to encode) outweigh the disadvantages of choosing from more options for this particular case. Initially, we thought the larger the value of $r$, the better the multibit performance. However, this was not always the case, which led to the discussion in Section 5 and Figure 6b. What we did find empirically was that for a fixed $\gamma$, larger $r$ benefits multi-bit performance. How $\gamma$ affects the multi-bit performance is a more complicated one, but we did find empirically that $\gamma=0.25, r=4$ outperforms $\gamma=0.5, r=2$ in multi-bit and zero-bit detection. For zero-bit detection, lower $\gamma$ leads to better detection performance, because this reduces the probability of a token from coming from a greenlist for a non-watermarked text. **Where can I find more detail on how the copy-paste attack was carried out?** We followed the copy-paste attack proposed in Kirchenbauer et al., (2023b). A random snippet of the watermarked text is inserted into a human text to comprise $p$ percentage of the entire text. This does not preserve the start and end tokens of the machine text, making it extremely difficult for extracting the watermark that does not rely on sampling the position with the hashing scheme like MPAC. An instance of this watermarking scheme is shown in Figure 2a whereby the position of the message is embedded in a rule-based manner.

Responses to Weaknesses

Thank you for your insightful feedback and questions. We hope our response addresses your concerns. If you have further concerns that prevent you from raising your score, please let us know. **W1: Performance reliant on token length** Yes. All watermarking methods rely on the complexity of the medium. This is often quantified as bits per tokens (BPT) or bits per pixel (BPP) in the image domain. Nonetheless, we believe this does not take away our main contribution, which is showing the feasibility of embedding a robust multi-bit watermark onto language model outputs. Please take into consideration that this is one of the first works enabling such an application. The embedding of $\geq$ 32-bit is to show the feasibility of embedding long messages without any latency, which is computationally infeasible on concurrent works (Fernandez et al., 2023a; Wang et al., 2023). Moreover, we discuss and analyze in depth the limitations of multi-bit watermarking in (1) Section 3.3 and Figure 2b how SNR is a more reliable factor in estimating the performance and (2) the tradeoff between the capacity of the watermark and its detection rate (Section 5 and Appendix A.8. We believe this discussion is an important contribution in enhancing the performance by the future works. **W2: A discussion on real-world applications potential user feedback could provide a more complete picture** We agree that metrics like AUC does not paint the full picture. To better illustrate the usefulness of the multi-bit watermarking, we give an example scenario of tracing back to the provenance after identifying the machine-text as done in Fernandez et al. (2023). Assume we are embedding 8-bit messages (256 users) onto 250 tokens. Allowing a false positive rate of 1e-3, we can correctly identify 98.3% of the machine text. Among the identified machine text, the exact match of finding the correct user is 92.6%. The details of this scenario is in Appendix A.7. Another obstacle in deploying watermarking in the real-world is its quality. Luckily, our MPAC maintains the exact quality with zero-bit watermarking (KGW) as shown in Figure 3. The effect of watermarking on the text quality _compared to no watermarking_ shows promising results in human evaluations when sufficiently large models are used for open-ended generation by Kirchenbauer et al. 2023b (Appendix A.2 and A.9). We are happy to discuss different aspects of user experience that the reviewer has in mind! **W3: While the paper evaluates against human-induced copy-paste attacks, it doesn't delve deeply into other potential real-world challenges. For instance, how would the system perform against more sophisticated adversarial attacks or in scenarios with heavy noise?** We believe our work extensively covers potential attempts to _evade_ watermark extraction by experimenting on paraphrasing on Chat-GPT (Figure 5b) and other language models (Table 4). While we do not believe these are exhaustive, they are easily accessible by potential adversaries and can be automated. In addition, list decoding is one solution for mitigating real-world challenges. This is especially useful in practice because provenance tracing via watermarking is far from finding an exact solution, but narrowing down the possible leakage points for a more detailed inspection that may be costly. This is because the decoded message is not error-free in the real-world and thus, one cannot finalize the decision by watermarking alone. For instance, when encoding the timestamp list decoding outputs the _range_ of time, for which the practitioners to manually inspect and find suspicious activity. When encoding the exact user ID, list decoding will output a list of IDs with varying characters in certain positions. Then the practitioners will consider the IDs that actually exist in their systems and further inspect other details such as recent user activities. That said, we are not claiming to propose a ready-made solution as this work is at an early stage. However, we do believe considering real-world challenges is important and are happy to discuss other sophisticated attacks or challenges in the real world the reviewer has in mind!

Response to Weaknesses [2]

**W4: If someone can reverse-engineer or predict the pseudo-random function, the watermark can potentially be tampered with or removed.** Watermark spoofing has been mentioned as a possible attack to “fake” a watermark to harm the reputation of certain models (Sadasivan et al., 2023). More realistically, removing the watermark may be possible if one knows the tokens in the colorlist. An important parameter that tradeoff privacy (difficulty of reverse engineering) and robustness (to corruptions) is the context width $h$. Assuming the use of LLaMA-2 tokenizer, the brute-force attack takes $|\mathcal{V}|^{h+1}= 32000^2 \approx 1e^{9}$, which is a considerable amount of effort even for the easiest case ($h$=1). All this presumes that the API call to extracting the watermark is accessible and that it shows the total number of colorlisted tokens. Simply displaying the extracted multi-bit message and the p-value under certain thresholds, e.g. {1e-6, 1e-5, 1e-4, 1e-3, 1e-2}, will make reverse engineering extremely difficult.

Responses to Questions

## Responses to Questions **Q1: While the paper states that the watermark is relatively robust under strong attacks like interleaving human texts and paraphrasing, are there any known methods or strategies that might weaken or remove the watermark effectively?** A strong corruption method is to use a strong paraphraser. In our experiments, we found that Chat-GPT is a strong candidate in breaking the watermarks (Figure 5b). An example of paraphrased text is shown below: ``` Watermarked: Furthermore, the county has committed to providing Amazon with $20 million in cash grants to help increase the amount of affordable housing in the area and improve bus services. To fund this, the county will implement a new tax on office space valuations. Additionally, Amazon will receive $7 million in electricity rebates over 15 years, with an average annual discount of $60,000. These rebates are set to begin in 2020. Paraphrased: The county also has pledged to provide Amazon with $20 million in cash grants, to increase the amount of affordable housing in the area and to upgrade bus service. The county would receive the money through a new tax on office space valuations. In addition, the county plans to provide Amazon with a 15-year payment schedule for about $7 million in electricity rebates. This would give the company an average annual discount of $60,000, according to the agreement. The electricity rebates would start in 2020. ``` **Q2: How easily can the MPAC method integrate with existing large language models and platforms? Are there any potential challenges to be aware of?** The simplicity of the method makes it a simple extension of KGW’s zero-bit watermarking. As shown in our main paper this leads to a simple step of sampling the position prior to selecting the token subset. Accordingly, this leads to zero overhead due to increasing the message length as shown in Figure 3. Our MPAC is also theoretically extendable to other zero-bit watermarking methods. The works of Aaronson and Kirchner (2023) and Kuditipudi et al., (2023) use exponential minimum sampling with a pre-defined set of watermark keys. Our Position Allocation scheme can be easily adapted as shown in Appendix A.10. The key to this is finding how to discriminate between $\textbf{m}[p]=0$ and $\textbf{m}[p]=1$. Since exponential minimum sampling favors tokens with large $\mathbf{r}_v$, this can be achieved inverting $\mathbf{r}$ by Eq. 8. We will empirically show the results in the future. **Q3: A detailed comparison between MPAC and other watermarking techniques, in terms of performance, accuracy, and robustness, would provide more context to the reader regarding the advantages of MPAC.** We agree and we are working on presenting the results in the discussion period. Please note that two concurrent works were uploaded in July 2023 (Fernandez et al., 2023a; Wang et al., 2023). The methodological differences our advantages of allowing embedding of long messages are discussed in the Related Section. Our current submission discusses (1) the limitation of encoding message sequentially in terms of robustness (Figure 2a), (2) how Position Allocation affects the performance in terms of SNR (Figure 2b) and (3) how colorlisting enhances the performance (Figure 4). ## Reference Kirchenbauer, John, et al. "On the Reliability of Watermarks for Large Language Models." arXiv preprint arXiv:2306.04634 (2023). Vinu Sankar Sadasivan, Aounon Kumar, Sriram Balasubramanian, Wenxiao Wang, and Soheil Feizi. Can AI-generated text be reliably detected?, 2023. arXiv preprint arxiv:2303. 11156 (2023). Kuditipudi, Rohith, et al. "Robust distortion-free watermarks for language models." arXiv preprint arXiv:2307.15593 (2023).

Author Responses to the Weaknesses

Thank you for the encouraging comments and the insightful feedbacks. We hope our response addresses your concerns. If you have further concerns that prevent you from raising your score, please let us know. ## Response to Weaknesses **Comparison with other watermarking methods** As far as we know, the most robust multi-bit watermarking method among post-processing methods (Abdelnabi & Fritz, 2021, Yang et al., 2022) is Yoo et al. (2023). However, this work only considers corruption at word-levels such as deletion, insertion, and substitution. Methodologically, one clear limitation is the sentence-level method whereby embedding and extraction are done at each sentence level. As an illustration, consider the example below: ``` Sentence 1 -> extracted message : “000” Sentence 2 -> extracted message : “000” Sentence 3 -> extracted message : “111” Sentence 4 -> extracted message : “111” Final extracted message : “000000111111” ``` If any human text were to be added into the first part of the writing (instance of copy-paste attack), the message is irrecoverable as it has no way to identify _when_ the machine text starts or ends. The problem persists when a single sentence in the middle is removed as well. In contrast, the proposed algorithm MPAC need not know this and achieves relative robustness in various kinds of attacks. In addition, ours enable zero-bit detection (machine-text detection) and multi-bit watermark all at the same time. The concurrent works (Wang et al., 2023; Fernandez et al., 2023), which are detailed above in the general comments and Related Works section of the paper, also rely on the hashing function similar to ours. We expect them to have better robustness than the post-processing methods. We are working on presenting the comparison of the robustness and load capacity of these methods in the following days. Theoretically, our MPAC has an advantage in embedding long messages without any added latency during generation (Figure 3). **More details on the watermark detection method** We agree that the paper will benefit from having a more detailed explanation on the detection method. The decoding algorithm has been moved into the main text. We will revise the paper in the following days to use the algorithm section to better explain the detection methodology. **W3: Embedding capacity is limited by text distribution and model & W4: Other models besides LLaMA** We agree that some of the text distributions inherently have low entropy, preventing them from embedding large, if any, amount of information. Nonetheless, malicious use cases of language model also involves open-ended generation rather than a fixed solution. Generation of disinformation falls into this case as numerous different passages can be created given a certain topic or propaganda. In our main experiments, we resemble this scenario by completing a news-like subset of C4. As shown in our experiments, we can extract a 8-bit message into 125 tokens with $\approx$ 95%. For reference, the above paragraph contains 123 tokens. Below we present the results for instruction-tuned models for LLaMA-2-7b (`meta-llama/Llama-2-7b-chat-hf`), Mistral-7b (`mistralai/Mistral-7B-Instruct-v0.1`), and a relatively small model (`OPT-1.3b`) . The results are on 8-bit and $\approx$ 250 tokens for 100 samples. For the tuned models, the instruction was “Complete the following news article:”. While the finetuned version on LLaMA shows noticeable falloff, this is _not_ the case for Mistral (Jiang et al., 2023). | Model | Bit Acc. | | ---------| ---------| | LlaMA-2-7b | .986 (.06) | | + chat | .922 (.13) | | Mistral-7b | .987 (.06)| | +chat | .977 (.08) | |OPT-1.3b|.982 (.07)| This hints at the possibility that instruction-tuning itself does not limit the capacity of watermarking, but rather the dataset and amount of tuning may be the key. We leave further analysis as a future work. ## Reference Sahar Abdelnabi and Mario Fritz. Adversarial watermarking transformer: Towards tracing text provenance with data hiding. In 2021 IEEE Symposium on Security and Privacy (SP), pp. 121– 140. IEEE, 2021. Xi Yang, Jie Zhang, Kejiang Chen, Weiming Zhang, Zehua Ma, Feng Wang, and Nenghai Yu. Trac- ing text provenance via context-aware lexical substitution. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 11613–11621, 2022. Yoo, KiYoon, et al. "Robust multi-bit natural language watermarking through invariant features." Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2023.

Response regarding weaknesses

Thank you for the feedback and the interesting questions. Below, we have responded to your concerns and questions. We hope our response addresses your concerns. If you have further questions that prevent you from raising your score, please let us know. ## Responses to Weaknesses **Regarding presentation and the decoding scheme** Thank you for the suggestions. We also believe this would improve the readability for the general readers and will reflected in the revised paper. Our decoding algorithm is now located at the end of Section 3.2. To summarize our key contributions, 1. We propose and validate Position Allocation that extends zero-bit watermark to multi-bit. Additionally, we show Colorlisting can further enhance multi-bit performance. 2. Through this, we demonstrate the feasibility of directly embedding long multi-bit information into language model outputs. This allows a robust watermark that can withstand realistic attacks that alter the start and end positions of the machine text (copy-paste attack) and change the entire sentence structures (paraphrasing) unlike previous multi-bit watermark works. 3. We discuss and analyze the limitations of multi-bit watermarking – namely, the tradeoff between the capacity of the watermark and its detection rate (Section 5 and Appendix A.8. We will be incorporating the contributions in the paper in the future.   **“Not enough bandwidth for multi-bit message” and Results for instruction-tuned models** Certain tasks such as code generation have shown to be difficult for watermarking due to the inherently low entropy distribution. Nonetheless, many other open-ended generation tasks certainly have enough capacity for multi-bit watermark. Generation of disinformation falls into this case as numerous different passages can be created given a certain topic or propaganda. Our main experiments simulate this scenario by completing a news-like subset of C4. As shown in our experiments, we can extract a 8-bit message into 125 tokens with $\approx$ 95%. For reference, the above paragraph contains 123 tokens. Below we present the results for instruction-tuned models for LLaMA-2-7b (`meta-llama/Llama-2-7b-chat-hf`) and Mistral-7b (`mistralai/Mistral-7B-Instruct-v0.1`). The results are on 8-bit and $\approx$ 250 tokens for 100 samples. For the tuned models, the instruction was “Complete the following news article:”. While the finetuned version on LLaMA shows noticeable falloff, this is _not_ the case for Mistral (Jiang et al., 2023). | Model | Bit Acc. | | ---------| ---------| | LlaMA-2-7b | .986 (.06) | | + chat | .922 (.13) | | Mistral-7b | .987 (.06)| | +chat | .977 (.08) | This hints at the possibility that instruction-tuning itself does not limit the capacity of watermarking, but rather the dataset and amount of tuning may be the key. We leave further analysis as a future work. **Details on list decoding** For computing the bit accuracy of list decoding, we take the “closest message out of the candidates” (Section 4.1 Metrics), which is assuming the best-case scenario. This was presented to show the effectiveness of list decoding in identifying the possible candidates, rather than to claim that this is actually achievable without any further means. In addition, we also note in the end of Section 3.3 that >list decoding technique is not unique to ours and can be applied to other methods as long as the decoding stage is computationally feasible. Nonetheless, the ability to encode long messages without any added latency is unique to our algorithm due to Position Allocation (compared to the concurrent works). In Figure 6c, the validity of the confidence measure used in list decoding is demonstrated by showing that it is inversely proportional to the error rate. In practice, list decoding is especially useful because provenance tracing via watermarking is far from finding an exact solution, but narrowing down the possible leakage points for a more detailed inspection that may costly. This is because the decoded message is not error-free in the real-world and thus, one cannot finalize the decision by watermarking alone. For instance, when encoding the timestamp list decoding outputs the _range_ of time, for which the practitioners to manually inspect and find suspicious activity. When encoding the exact user ID, list decoding will output a list of IDs with varying characters in certain positions. Then the practitioners will consider the IDs that actually exist in their systems and further inspect other details such as recent user activities.

Responses to Questions

## Response to Questions **Q1: The UMD scheme is inherently distortionary. Is there a way to apply the ideas presented in this paper to the non-distortionary schemes?** The cited work is similar to Aaronson and Kirchner, 2023 in that it uses exponential minimum sampling with a pre-defined set of watermark keys. Our Position Allocation scheme can be easily adapted as shown in Appendix A.10. The key to this is finding how to discriminate between $\textbf{m}[p]=0$ and $\textbf{m}[p]=1$. Since exponential minimum sampling favors tokens with large $\mathbf{r}_v$, this can be achieved inverting $\mathbf{r}$ by Eq. 8. We will empirically experiment this in the future. **Q3: How is the accuracy computed with list decoding?** Please find our response above in the comment regarding weakness. **Q4: Can you show some ablation experiments depicting the comparisons between list decoding, and random bit flips in the most likely decoded message?** We observed “that randomly altering a single position provides a good list as the best candidate message is already a good starting point” (Section 5). This was likely due to the computing 16-lists when the effective bit-width was $\leq$ 16. We will try to provide some numbers in the following days. The comparison with an entirely random list is shown in Table 3. **Q5: Would it be possible to compare the degradation with changing delta for their 0-bit scheme, and the multi-bit scheme presented here?** The table below (also in Figure 9) shows the quality and the bit accuracy tradeoff when increasing $\delta $ for embedding 8-bit message into 100 token sequences. P-SP is the metric we used in our main paper that computes the similarity with the watermarked sentences with the human-written sentences. While we do not have results for the zero-bit watermark, the quality will be equivalent as shown in Figure 3, regardless of the magnitude of $\delta$. |Delta | 0.5 | 1 | 2 | 3| 5 | 10 | |-------| -----|---|---|--|---|-----| |Bit Acc.| 0.618 (.18) | 0.751 (.19)|0.917 (.13)|0.979 (.08)|0.997 (.02)|0.994 (.04)| |P-SP|0.384|0.385|0.376|0.356|0.325|0.244| ## References Jiang, Albert Q., et al. "Mistral 7B." arXiv preprint arXiv:2310.06825 (2023).

First author response: major points [2]

## Where our work stands “_it is essential for the authors to demonstrate superior robustness [over Kirchenbauer et al., 2023] to substantiate their contributions effectively_” (`Fyz9`) We respectfully disagree with the premises of Reviewer `Fyz9`. Our work does not claim to “_enhance the robustness intrinsic to_” Kirchenbauer et al., 2023 (KGW hereafter). Rather, we propose a new research direction for extending this to multi-bit. Comparing the performance directly with KGW is not an apples-to-apples comparison. In Section 3.2 Message Encoding, we showed that the zero-bit detection problem is equivalent to embedding a single-bit. As watermarking (Vleeschouwer et al., 2002) involves a tradeoff between load capacity (how much information) and robustness (how much information is preserved), we tackle an inherently more challenging task. Nonetheless, we believe providing a comparison does make the work more complete. As such, we discuss in detail the tradeoff between message length and detection in Section 5 and present FPR comparison with zero-bit detection in Table 6. In addition, we do not “_purport that the multi-bit watermark sustains the caliber of the text_” compared to non-watermarked text. As stated in our introduction and Figure 3, we state that our text quality is maintained compared to KGW. We will revise the wording to avoid any further confusion. *Comparison with steganography* (`hfyX`) Watermarking differs from steganography works (Ziegler et al., 2019, de Witt et al., 2022) as they do not consider possible corruption. For instance, Ziegler et al. rely on sequential arithmetic coding of every token. Thus, substituting or removing the first token of the cover text will alter the entire extract message. We will try to empirically demonstrate this in the response period, should time allow. To the best of our knowledge, no work in both (multi-bit) watermarking and steganography consider robustness as extensively as ours. We experiment on realistic and “difficult” corruptions that interleave machine texts with human texts (copy-paste), paraphrasing based on GPT-3.5 and DIPPER, a paraphrasing model developed specifically for evading machine-text detection (Krishna et al., 2023). Once again, we thank the reviewers for their service. We will update a more detailed response specific to each reviewer’s concern in the individual comments. - Scott Aaronson and Hendrik Kirchner. Watermarking gpt outputs. https://www. scottaaronson.com/talks/watermark.ppt, 2023. Accessed: 2023-09-14. - Sahar Abdelnabi and Mario Fritz. Adversarial watermarking transformer: Towards tracing text provenance with data hiding. In 2021 IEEE Symposium on Security and Privacy (SP), pp. 121– 140. IEEE, 2021. - Pierre Fernandez, Antoine Chaffin, Karim Tit, Vivien Chappelier, and Teddy Furon. Three bricks to consolidate watermarks for large language models. arXiv preprint arXiv:2308.00113, 2023a. - John Kirchenbauer, Jonas Geiping, Yuxin Wen, Jonathan Katz, Ian Miers, and Tom Goldstein. A watermark for large language models. arXiv preprint arXiv:2301.10226, 2023a. - Taehyun Lee, Seokhee Hong, Jaewoo Ahn, Ilgee Hong, Hwaran Lee, Sangdoo Yun, Jamin Shin, and Gunhee Kim. Who wrote this code? watermarking for code generation. arXiv preprint arXiv:2305.15060, 2023. - Lean Wang, Wenkai Yang, Deli Chen, Hao Zhou, Yankai Lin, Fandong Meng, Jie Zhou, and Xu Sun. Towards codable text watermarking for large language models. arXiv preprint arXiv:2307.15992, 2023a. - KiYoon Yoo, Wonhyuk Ahn, Jiho Jang, and Nojun Kwak. Robust multi-bit natural language water- marking through invariant features. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 2092–2115, 2023. - C. De Vleeschouwer, JF Delaigle and B. Macq, "Invisibility and application functionalities in perceptual watermarking an overview," in Proceedings of the IEEE, vol. 90, no. 1, pp. 64-77, Jan. 2002, doi: 10.1109/5.982406. - Ziegler, Zachary, Yuntian Deng, and Alexander M. Rush. "Neural Linguistic Steganography." Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP). 2019. - de Witt, Christian Schroeder, et al. "Perfectly secure steganography using minimum entropy coupling." arXiv preprint arXiv:2210.14889 (2022). - David F. Carr, As ChatGPT Growth Flattened in May, Google Bard Rose 187%, https://www.similarweb.com/blog/insights/ai-news/chatgpt-bard/, Accessed: 2023-11-10 - Byung-yeul Baek, Naver to launch HyperCLOVA X AI service to rival ChatGPT, https://www.koreatimes.co.kr/www/tech/2023/11/129_350568.html, Accessed: 2023-11-10 - Emillia David, Baidu launches Ernie chatbot after Chinese government approval, https://www.theverge.com/2023/8/31/23853878/baidu-launch-ernie-ai-chatbot-china, Accessed: 2023-11-10