Watermarking for User Identification in Large Language Models

Authors: Zihao Fu, Chris Russell
Primary area: foundation or frontier models, including LLMs
Keywords: Large Language model; Watermark

Abstract:
We identify a new task for watermarking -- namely the simultaneous identification of text as being automatically generated alongside the identification of the LLM user. 
We show that a naïve approach that treats a text as artificially generated if a user is correctly identified is prone to problems of false positives arising from multiple hypothesis comparison. 
We propose a novel approach (Our code is submitted with the supplementary material. We will also open it on Github after the anonymity period.) that retains almost similar rates as the number of users increase. We derive theoretical bounds that support our experimental approach.

Decision: reject
Reviewer scores: 6, 5, 5, 5

Reviews and discussion:
<thread>
creation date:
1729688139959

thread_type:
official_review

<thread_object>
creator: reviewer_qkcq

<content>
summary:
This paper addresses the false recognition problem in watermarking large language models (LLMs), specifically focusing on simultaneous detection of machine-generated text and user identification. The authors propose a novel Dual Watermark Inspector (DWI) method that separately encodes indicator and key information into generated text. They provide theoretical bounds for false positive rates and demonstrate empirically that their method significantly reduces false positives compared to baseline approaches. The paper includes extensive experiments validating the method's effectiveness across different settings and robustness against insertion/deletion attacks.

strengths:
- Practical relevance for real-world LLM deployment and governance
- Comprehensive empirical evaluation across various settings (watermark ratios, key capacities, sample sizes)

weaknesses:
While the paper presents a sound approach, it has several limitations in both technical depth and presentation clarity that could be improved upon.

1. Limited comparison with other recent watermarking methods beyond the baseline FKE approach. The paper primarily focuses on comparing with one baseline method, missing opportunities to demonstrate advantages over other state-of-the-art approaches.

2. The trade-off between accuracy and false positive rate could be analyzed more thoroughly. While the paper shows improvements in false positive rates, it lacks detailed analysis of how this affects other performance metrics across different scenarios.

3. The choice of ratio r between indicator and key information tokens appears somewhat arbitrary. The paper does not provide sufficient theoretical or empirical justification for the selected ratio values.

4. Impact on text quality and fluency not thoroughly discussed or evaluated. The paper focuses on detection metrics but lacks analysis of how the watermarking method affects the generated text's quality and naturalness.

5. Computational overhead of the proposed method compared to baseline not clearly addressed. The additional complexity introduced by the dual watermarking approach is not quantified or discussed in terms of practical implementation costs.

6. Writing and presentation issues detract from the paper's clarity. Several technical terms are used before being properly defined, figure captions lack detail, and important implementation details are scattered between the main text and appendix. The mathematical notation also shows some inconsistency across sections.

questions:
- How does the method perform with very short text sequences?
- Is there a minimum length requirement?
- Could the approach be extended to handle hierarchical or structured user identification beyond simple integer keys?
- What is the impact of vocabulary size on the method's performance?
- How does the method handle adversarial attacks beyond simple insertion/deletion?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730370492491

thread_type:
official_review

<thread_object>
creator: reviewer_rasn

<content>
summary:
This paper presents a new watermark encoding approach that divides the tasks of identifying whether text is generated by a large language model (LLM) and determining which user generated it. By separately encoding these two types of information, the proposed method alleviates the issue faced by traditional Full Key Encoding (FKE) methods, which experience increased false positive rates (FPR) as the number of users grows.

strengths:
1. Identified a Significant Problem: The issue addressed in this paper is highly relevant and important, particularly in the context of managing LLM-generated content.
2. Effective Experimental Results: The experiments convincingly demonstrate that the proposed method effectively mitigates the false positive rate (FPR), particularly as the user count increases.

weaknesses:
1. Insufficient Comparison with Existing Methods: While the authors constructed some baselines for comparison, the analysis against existing FKE methods is not comprehensive. Notably, the paper does not mention other multi-bit watermarking techniques that can extract user identity, such as MPAC[1] and Codable Watermark[2].
2. Limited Experimental Scope: The main experiments rely on only one model and one dataset, which raises concerns about the generalizability of the findings. A broader range of models and datasets would strengthen the claims made.
3. Lack of Scientific Rigor in Writing: The overall writing lacks scientific rigor, with unclear logic and weak structural organization. Improved clarity and coherence would enhance the readability and impact of the paper.

Reference:
[1] Advancing Beyond Identification: Multi-bit Watermark for Large Language Models via Position Allocation.
[2] Towards Codable Text Watermarking for Large Language Models.

questions:
See the weaknesses section.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730701008400

thread_type:
official_review

<thread_object>
creator: reviewer_qskm

<content>
summary:
This paper explores a new problem for LLM watermarking with a specific focus on user identification. The authors address the challenge of false recognition, where non-watermarked text may be mistakenly classified as watermarked, especially as the user count increases. To tackle this, the paper introduces a Dual Watermark Inspector (DWI) and a Hybrid Dual Watermark Inspector (HDWI) approach, aiming to improve the robustness of watermark detection by reducing false positives. The paper offers a combination of theoretical derivations and empirical validations, suggesting that DWI and HDWI outperform existing watermarking methods in accuracy and false positive control.

strengths:
1. Addresses a pressing issue of false positives in multi-user watermarking, which is important for the practical use of watermarking in AI applications.

2. Introduces a new dual watermarking approach that embeds user identity while preserving the text's integrity, showing significant improvement in error rates.

weaknesses:
1. The presentation lacks clarity in explaining the watermarking process. I suggest that the authors include a detailed algorithmic outline to demonstrate how watermark generation and detection are performed. It is currently unclear how the integer key (user ID) is embedded into the generated text. Additionally, based on my understanding, this method is an extension involving when to add Gumbel noise for embedding the watermark, with the primary approach building on existing methods.

2. The citation formatting (using \citep and \citet) should be corrected. Furthermore, the term "Stochastic sampling" in lines 151-152 needs clarification—what exactly is meant by this here? Regarding the hash function, you currently rely on the previous two tokens for hashing. However, as Aaronson suggests, a small window size can compromise pseudorandomness. It would be beneficial to either use a larger window size or store a two-gram history to prevent repetition issues.

3. From my understanding, user identification could naturally be addressed through multi-bit watermarking techniques. The statement in lines 104-106, "no methods have explored the task of retrieving information from watermarked text intermingled with unwatermarked text," is unclear. I recommend expanding on this point and providing a more detailed discussion of multi-bit watermarking, especially in relation to user identification.

questions:
How do DWI and HDWI methods perform computationally when applied to LLMs with larger user bases?
</content>
</thread_object>

</thread>
<thread>
creation date:
1731403844506

thread_type:
official_review

<thread_object>
creator: reviewer_e57v

<content>
summary:
The paper proposes a method for achieving both output watermarking and user identification for LLMs.

strengths:
- LLM watermarking is an important topic for the research community.
- The inclusion of a theoretical analysis strengthens the paper.

weaknesses:
- Although the proposed method improves on baseline FPR values, the overall FPR (>0.01) is still too high for practical applications.
- Watermarks can significantly impact text quality, but the paper lacks any analysis of this issue.
- Paraphrasing, whether done once or multiple times, may weaken the watermark because of the hash's sensitivity to small changes.

Minor Points
- The citations need to be adjusted. The authors should use \citep for most citations, except where the citation is the subject or object of the sentence.
- Some tables and figures would benefit from more descriptive captions. For example, Figures 2–7 and Tables 2–5 lack clear descriptions.

questions:
Given a fixed prompt, does the watermark affect output diversity?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732379632799

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General Response (1/2)

comment:
We thank the reviewers for their valuable comments. To address these issues, we have made several improvements to the paper. Specifically, we have added experiments on rephrasing attacks (M1), runtime analysis (M2), sequence length analysis(M3), indication ratio parameter $r_d$ analysis (M4). Additionally, we have conducted new experiments on two datasets, BioASQ and LegalQA (M5). A new theoretical analysis (M6) for multi-bit methods based on a dictionary color list has also been added, along with numerical experiments to further support the theoretical findings. We have also introduced a new baseline model (M7) in the experimental section and incorporated a new metric (M8) to evaluate text generation quality. We also add a new algorithmic outline. The detailed modifications are provided below, and we will address each question under the corresponding reviewer comments.

**M1. We have added experiments on rephrasing attacks. (Details in Appendix A.7)** Specifically, we conducted a paraphrase attack to evaluate the robustness of the proposed methods. We employed the Parrot_Paraphraser toolkit to rephrase sentences with watermarks and tested the ability of our models to detect the watermark and key information. The results demonstrate that (1) our proposed DWI and HDWI models still outperform the FKE method aster the rephrasing attack, (2) although detection accuracy decreases post-paraphrasing, it remains above 0.5, indicating that the methods can still identify watermarked text and associated keys.

**M2. We have added new experiments on runtime analysis. (Details in Appendix A.8)** We evaluated the computational cost of the watermarking models by testing the runtime across various models, including “NoWatermark” generation. Results show that (1) watermarking models slightly increase generation runtime due to hashing and key encoding, (2) generation runtime is independent of key capacity, as encoding occurs only once, and (3) detection runtime increases linearly with key capacity, as it requires iterating over potential keys.

**M3. We have added new experiments on sequence length. (Details in Appendix A.9.)** Using the HDWI model with a watermark ratio of $r=0.5$, we analyzed the impact of sequence length, ranging from 20 to 1000 tokens. Results indicate that (1) accuracy improves with longer sequences as they better embed watermarks, and (2) models effectively recognize watermarked text when token lengths exceed 50 and achieve good performance beyond 200 tokens. 

**M4. We have added new experiments on the indication ratio parameter $r_d$. (Details in Appendix A.11.)** In response to the reviewer's suggestion, we have conducted additional experiments analyzing the impact of $r_d$ on performance metrics such as Accu-I, Accu-O, and FPR. The results, shown in Appendix A.11, indicate that as $r_d$ increases, both DWI and HDWI improve in Accu-I, validating our theoretical claims. However, excessively large $r_d$ values reduce Accu-O by hindering key information detection, demonstrating a tradeoff. Additionally, HDWI outperforms DWI in low $r_d$ scenarios, and increasing $r_d$ reduces FPR by mitigating false positives. This analysis highlights the robustness of our method and addresses the reviewer's concern.


**M5. We have added new experiments on two new datasets. (Details in Appendix A.10.)** To evaluate the model’s applicability across different domains, we tested it on BioASQ (biomedical questions) and LegalQA (legal texts). Results show (1) consistent performance trends with the main experiments, where our methods outperform others, and (2) high similarity scores (up to 0.9), indicating minimal alteration of output text even in domain-specific contexts.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper addresses the challenge of false recognition in watermarking for large language models (LLMs), particularly in detecting machine-generated text and identifying specific users. The authors propose the Dual Watermark Inspector (DWI) and Hybrid Dual Watermark Inspector (HDWI) methods, which encode text generation and user identification information separately. This approach reduces false positive rates (FPR), a common issue in traditional Full Key Encoding (FKE) methods, especially as the number of users increases. Theoretical analyses and empirical experiments demonstrate the superiority of DWI and HDWI in accuracy and robustness, including resistance to insertion and deletion attacks, compared to baseline watermarking techniques.

The proposed method includes rigorous theoretical analysis supported by experiments. The authors have responded to the reviewers' concerns. Unfortunately, the revised average score remains below the acceptance threshold. Since LLM watermarking research is a hot topic in ML and there are numerous existing methods, it would be beneficial to include more discussion and, if possible, comparisons to these methods. This would make the paper stronger, in my opinion. Therefore, I encourage the authors to revise the paper based on the reviewers' comments and resubmit it to a future venue.