Watermarking for User Identification in Large Language Models

1. Limited comparison with other recent watermarking methods beyond the baseline FKE approach, missing opportunities to demonstrate advantages over state-of-the-art approaches.

A: We have added a new baseline model, Multi-bit (see the main experiments), along with a detailed theoretical analysis and numerical experiment of the false recognition problem for this model. please refer to the general response M6 and Appendix A.12.

2. Lack of detailed analysis on the trade-off between accuracy and false positive rate across different scenarios.

A: We have conducted such analyses in Section 5.5 and Appendix A.11, where we vary the watermarked text ratio and observe changes in Accuracy (Acco-I and Accu-O) and FPR. In Section 5.6, we analyze how increasing key capacity impacts Acco-I, Accu-O, and FPR. Appendix A.10 presents results on how Accuracy (Acco-I and Accu-O) and FPR vary across different datasets, reflecting two distinct application scenarios. In Appendix A.9, we examine the influence of sequence length on Accuracy and FPR. Additionally, in Section 5.7, we evaluate how changing the backbone model affects Accuracy and FPR. These experiments collectively demonstrate how Accuracy and FPR evolve under various scenarios.

3. Insufficient theoretical or empirical justification for the choice of ratio $r_d$ between indicator and key information tokens.

A: It is important to note that we have already conducted such experiments in Section 5.3. Additionally, we have included a new experiment comparing results with different $r_d$. For further details, please refer to the general response (M4).

4. Limited discussion or evaluation of the impact of the watermarking method on text quality and fluency.

A: We have incorporated a new metric, as proposed by Fernandez et al. (2023), to assess the quality of the generated text. See general response (M8) for more details.

5. Computational overhead compared to the baseline is not quantified or discussed in terms of practical implementation costs.

A: We have added a new experiment to analyze the computational cost. Please refer to the general response (M2) and Appendix A.8 for details.

6. Writing and presentation issues, including undefined technical terms, insufficient figure captions, scattered implementation details, and inconsistent mathematical notation.

A: We have refined the technical aspects of the paper. Specifically, we revised several term definitions and added a new algorithmic outline to clarify the procedure (see general response M9 and Algorithm 1 in the updated version). Additionally, we have provided detailed captions for all figures and tables and addressed the issue of overused mathematical notations.

7. How does the method perform with very short text sequences? Is there a minimum length requirement?

A: Generally, longer texts contain more information, which improves inference accuracy. We have added a new experiment to report performance across different text lengths. For details, please refer to the general response M3 and Appendix A.9.

8. Could the approach be extended to handle hierarchical or structured user identification beyond simple integer keys?

A: Technically, the method supports user keys, as any information that can be converted into a sequence can be used to convey such information. However, it should be noted that we have proven that as the key capacity increases, the false recognition problem becomes more severe (see Section 4 for theoretical analysis and Section 5.6 for experimental results). Therefore, we do not recommend using overly complex information as keys.

9. What is the impact of vocabulary size on the method’s performance?

A: The method’s performance is not significantly influenced by vocabulary size. For the backbone by Aaronson & Kirchner (2023), performance is independent of the vocabulary size. For the backbone by Kirchenbauer et al. (2023a), the vocabulary is divided into several partitions, but it is the number of partitions, rather than the vocabulary size itself, that affects the results. Please refer to the theoretical analysis in Appendix A.12 and Theorem 4 for further details.

10. How does the method handle adversarial attacks beyond simple insertion/deletion?

A: We have added a new experiment on the paraphrase attack. Please refer to the details in the general response M1.

1. Only compare with existing FKE methods, lack of mention of multi-bit watermarking techniques.

A: For multi-bit watermarking, we have added a new theoretical analysis, numerical experiments, and baseline models to the main experiment. For more details, please refer to the general response M6 and Appendix A.12.

2. Limited experimental scope, relying on only one model and one dataset, raising concerns about generalizability.

A: We have used two backbone models in our experiments. The main experiments are based on one model, while we also conducted experiments using the model proposed by Aaronson & Kirchner (2023) in the main experiments and Kirchenbauer et al. (2023a) in Section 5.7.

Additionally, we incorporated two datasets from the biomedical and legal domains, with detailed descriptions provided in the general response M5 and Appendix A.10.

3. Lack of scientific rigor in writing, with unclear logic and weak structural organization.

A: We have further refined the paper and added a new algorithmic outline in Algorithm 1, making the procedure clearer.

1. Could the authors include a detailed algorithmic outline to demonstrate how watermark generation and detection are performed?

A: Thank you for the suggestion. We have included the algorithmic outline in Algorithm 1. Please refer to the general response M9 and our updated version for further details.

2. How is the integer key (user ID) embedded into the generated text?

A: The integer key (user ID) is embedded into the generated text through a controlled sampling process using a hash function and the Gumbel-Max trick. A hash key derived from the previous two tokens determines whether the current token encodes a watermark indicator or key information. If encoding key information, the user ID is incorporated as a salt key, which is then used to adjust the logits via Gumbel noise. This process subtly influences token selection, embedding the user ID into the text while maintaining robustness and preserving text diversity. Please refer to the general response M9 and our updated version for further details.

3. The citation formatting (using \citep and \citet) should be corrected.

A: Thank you for pointing this out. We have revised all the citations accordingly. Please refer to our updated version.

4. What is meant by “Stochastic sampling” in lines 151-152, and could it be clarified?

A: “Stochastic sampling” refers to the process of selecting the next token in text generation based on a probability distribution derived from the model’s logits. Instead of deterministically choosing the token with the highest probability (e.g., greedy decoding), stochastic sampling randomly selects a token, with the likelihood of selection proportional to its predicted probability. This approach introduces variability into the output, promoting diversity and creativity in the generated text while remaining guided by the underlying distribution. We have included a more detailed explanation in the main text.

5. Could the authors address concerns about using a small window size for hashing, as suggested by Aaronson, and consider alternatives like using a larger window size or storing a two-gram history to prevent repetition issues?

A: Using a two-gram window size is a de facto choice, as suggested by Fernandez et al. (2023), for setting the window size. Increasing the window size may make the method more vulnerable to adversarial attacks. Furthermore, we have not observed significant repetition issues in our generated text, so we have opted to retain this setting without modifications.

6. Expand on providing a more detailed discussion of multi-bit watermarking, especially in relation to user identification.

A: We have added a new theoretical analysis, numerical experiments, and baseline models to the main experiment. For more details, please refer to the general response M6 and Appendix A.12.

7. Performance computationally when applied to LLMs with larger user bases.

A: These results are presented in Table 3 and Figure 5, with further details in Section 5.6. The experiments show that as key capacity $K$ increases, the FKE method’s performance decreases significantly due to its reliance on the maximal score across the key space, consistent with our theory. In contrast, the HDWI method remains robust, as the indicator variable ensures that the false positive rate (FPR) is unaffected by the total key count, demonstrating scalability for larger user bases.

1. While the proposed method improves baseline FPR values, the overall FPR (>0.01) is still too high for practical applications.

A: We respectfully disagree with the assertion that an FPR greater than 0.01 renders the method impractical. The acceptability of the FPR threshold is highly application-dependent and varies based on the specific requirements and constraints of the task. Additionally, achieving an FPR below 0.01 is a challenging goal for most applicable methods in this domain. We envision this method as a practical solution for initial filtering of suspicious text, which can then be forwarded for further manual or automated verification.

2. The paper lacks any analysis of how watermarks impact text quality.

A: We have incorporated a new metric, following Fernandez et al. (2023), to assess the quality of the generated text. See general response (M8) for more details.

3. Does paraphrasing, whether done once or multiple times, weaken the watermark due to the hash’s sensitivity to small changes?

A: We have included a new experiment to evaluate the method’s performance under paraphrase attacks. Please refer to the general response (M1) for further details.

4. Should citations be adjusted to use \citep except when the citation is the subject or object of a sentence?

A: Thank you for pointing this out. We have revised all the citations accordingly. Please refer to our updated version.

5. Figures 2–7 and Tables 2–5 require more descriptive captions.

A: Thank you for pointing this out. We have revised all the Figures and Tables accordingly. Please refer to our updated version.

6. Given a fixed prompt, does the watermark affect output diversity?

A: The watermark itself does not affect output diversity. This is because, after applying the Gumbel trick, the process becomes equivalent to a sampling operation, which can preserve diversity as long as the randomness is appropriately controlled. It is important to note that the source of randomness originates from the uniform distribution prior to applying the Gumbel trick.

M6. In-Depth Theoretical and Numerical Analysis of the Multi-Bit Encoding Method (Details in Section A.12.)

We appreciate the reviewer’s comments and have expanded our analysis of the multi-bit encoding method. Specifically, we conducted a new theoretical analysis to demonstrate that the multi-bit method also suffers from the false recognition problem as key capacity increases. Key points are summarized as follows:

(1) Distribution Analysis and Novel Bound:
We identified that the detection method in the multi-bit encoding aligns more closely with a Gumbel distribution than the originally claimed binomial distribution. Based on this observation, we derived a novel bound for the composed extreme variable as follows:

Let $C_{p_t} = \max\left(\frac{X_1}{T/b}, \frac{X_2}{T/b}, \cdots, \frac{X_r}{T/b}\right)$, where $X_\rho \sim \text{Binomial}\left(\frac{T}{b}, \frac{1}{r}\right)$ for all $\rho \in [r]$. Then, the probability that $C_{p_t}$ exceeds a threshold $y$ is bounded by:
$\Pr(C_{p_t} \geq y) \leq r \cdot \exp\left(-\frac{2 T \left(y - \frac{1}{r}\right)^2}{b}\right).$

This bound reveals that as the message length $b$ increases, the probability of false positives $\Pr(C_{p_t} \geq y)$ also increases, exacerbating the false recognition problem.

(2) Tail Bound Analysis and Implications:
To address challenges in computing Gumbel parameters, we analyzed its tail bounds and showed that the detection threshold increases with key capacity. This growth causes unwatermarked text to increasingly resemble watermarked text.

(3) Numerical Validation (Fig. 13):
Numerical experiments validated our theoretical findings. Specifically, as $b$ increases, the expected detection statistic rises, the distribution narrows, and variance decreases. These effects complicate accurate classification, confirming that false recognition becomes more severe as key capacity increases.

These theoretical and experimental results support our main paper’s claim, emphasizing the limitations of the multi-bit watermarking method and providing a deeper understanding of its inherent challenges.

M7. We have added new baseline models (details in the Experiments section). To enhance the comparison of multi-bit methods, we incorporated them as new baseline models, as detailed in the updated Experiments section. It demonstrates that the multi-bit model applied in this scenario is capable of encoding key information and indicator variables. However, its performance is inferior to our proposed methods, highlighting the effectiveness of our proposed framework.

M8. We have added a new similarity metric, Sim (details in the Experiments section). To assess the quality of generated text after watermarking, we adopt the approach of Fernandez et al. (2023), utilizing cosine similarity (Sim) between watermarked and unwatermarked text to evaluate generation quality and measure information loss. The experimental results indicate that the sSim scores of all watermarking methods are at a similar level, demonstrating that our method does not compromise quality compared to other watermarking methods.

M9. We have added a new algorithmic outline to make the procedure clearer. (Details in Algorithm 1) We have included a new algorithmic outline illustrating the generation and detection processes to enhance clarity. This visual representation provides a step-by-step depiction of the procedure, making it more intuitive for readers to follow.