Sparse Watermarking in LLMs with Enhanced Text Quality

Thank you for the comments, please see our responses below.

Q1:The main consideration of the paper is to preserve text quality; however, the baseline methods compared in the main experiments are traditional and do not primarily focus on preserving text quality.

A: Thank you for your suggestion. When conducting the experiment, our objective was to introduce and evaluate the Sparse Watermarking (SpARK) framework against widely used watermarking techniques to establish a broad understanding of its advantages. For comparison with methods that helped preserve text quality, we ran the EWD watermark on the WaterBench baseline, the results of which are presented in the Public Global comment. In short, we show that while EWD produces better quality answers compared to other watermark methods, SpARK overall still has a higher Rouge-L score.

Q2:While there is a comparison with distortion-free methods in Appendix F, the only measure for text quality is perplexity (PPL), which is insufficient, and SpARK does not demonstrate an advantage over distortion-free methods.

A: Thank you for your comment. While Distortion Free was able to have a slightly lower perplexity than ours, our method is still robust to paraphrasing attacks. Furthermore, distortion-free cannot achieve as high of detectability compared to SpARK, as the result also shows that the shortest key (length = 1) with the lowest p-value median cannot achieve detectability similar to other methods. Meanwhile, SpARK is more flexible, and can easily change the trade-off between text quality and detectability by changing gamma. Lastly, Distortion Free takes significantly more time to detect its watermark compared to ours. From the table below, we can see that the generation time for each of the sample text is not so different between the two methods. However, the time it takes to detect a watermark per sample for Distortion Free watermark is a lot more compared to SpARK. This shows that our method is more suitable for real-world application compared to Distortion Free watermark.

Q3:Additionally, other methods that could aid in preserving text quality, such as unbiased watermark, DiPMark, TS-Watermark, and SWEET, were not included in the experiments.

A: Thank you for your suggestions. As stated previously, our objective was to introduce and evaluate the Sparse Watermarking (SpARK) framework against widely used watermarking techniques to establish a broad understanding of its advantages. To further improve our claims of SpARK's effectiveness, we have also run a comparison between our method and other quality-preserving text watermarks which are EWD[1] and SWEET[2]. The experiment results are presented in the Public Global comment, but to summarize, SpARK was still able to maintain higher quality compared to EWD and SWEET, while maintaining detectability after paraphrasing attacks. This shows that SpARK's watermarked text struck a balance between high-quality generations and robustness to attacks.

[1] Lu et al., An Entropy-based Text Watermarking Detection Method. 2024.

[2] Lee et al., Who Wrote this Code? Watermarking for Code Generation. ACL 2024

Thank you for the comments, please see our responses below.

Q4: Thank you for your response and the additional experiments. However, I find the design of the sparse watermark to be somewhat trivial. It's not that simplicity is inherently bad, but I do not see a theoretical advantage over existing sparse watermarks like SWEET or EWD. Additionally, the experimental advantages are not particularly evident. Therefore, I will maintain my score.

A: Thank you for your response. While the theory of sparse watermark has been presented in SWEET (note that EWD is not sparse watermarking), SWEET only focuses on low entropy tasks (i.e., code generation); our work addresses two major limitations inherent in SWEET. Firstly, our method does not require access to the original prompts associated with each text, nor does it depend on the original model to detect watermarks; the first requirement (access to the original prompts) only works for code generation, but not in the general context of text generation, while the second requirement significantly increases the computational cost of detecting a watermarked sample. SpARK does not have either of these requirements (or restrictions). Secondly, SpARK was able to achieve slightly better empirical performance, while being more robust under paraphrasing, compared to SWEET (and also EWD, although EWD is not sparse watermarking) without the restrictions we just mentioned; SpARK achieved a better Rouge-L score compared to SWEET (and also EWD), and had significantly better results in Summarization (reducing 10% less of the original Rouge-L score), while maintaining slightly better results on LFQA (1.5% less Rouge-L score reduction). For these reasons, we believe that SpARK has unique advantages and contributions compared to the previous works.

We also believe that the "simplicity" of SpARK (which the Reviewer also appreciates) is actually its major advantage, as it enables SpARK to be practical, while being able to perform extremely well compared to other watermarking methods (including the prior Sparse Watermarking ones) and overcome major disadvantages of previous Sparse Watermarking works. Designing such a simple, practical, and high-performing watermarking method is not a trivial task and we sincerely hope that our clarifications in this response can convince the Reviewer to change the rating of the work.

Thank you for the comments, please see our responses below.

Q1:Lack of Innovation: The core idea of applying watermarks to a sparse subset of generated tokens is not novel. Existing works have already explored similar sparse watermarking and selective token modification methods. The paper fails to demonstrate a significant deviation from or advancement beyond these existing solutions. Recent watermarking studies already emphasize limiting the impact on text quality while ensuring robustness, making SpARK's claims less compelling

A: Thank you for your question. As mentioned in our paper, our goal is to explore the concept of a sparse watermark. However, our concept of sparse watermark is not only to limit the number of tokens used for watermarking but also to limit the detection process to a small subset of tokens that is closely tied to the grammatical structure of the generated text. This will incorporate the benefits of higher-quality text generation during sparse watermarking, while maintaining the detectability and robustness of the embedded watermark.

While there exist methods (i.e. SWEET) with similar concepts to ours, our novelty lies in sparse watermarking without any access to additional information such as the original prompts or the original model, which are the main limitations of the existing sparse watermarking methods.

Q2:Questionable Benefit Claims: The authors argue that SpARK's sparse watermarking reduces the degradation of text quality compared to dense watermarking. However, numerous recent works on text watermarking already achieve minimal or no impact on text quality. These techniques do not require sparsity to maintain text integrity, suggesting that the claimed advantage of SpARK may not be as impactful as presented.

A: Thank you for your comment. In our paper, we have run an experiment comparing our method to Distortion Free watermark, a watermark method that aims to minimize its impact on the text quality. We strongly believe that we have thoroughly discussed and compared our work to existing watermarks with similar goals of having minimal impact on text quality; nevertheless, we would greatly appreciate it if the reviewer could kindly point out any specific relevant work that may be missing from our paper. We are more than willing to promptly discuss and evaluate these works during the rebuttal process.

Q3:Evaluation Limitations: While the authors provide experimental results demonstrating the performance of SpARK, the evaluations do not sufficiently differentiate it from existing sparse watermarking techniques. The lack of comparative analysis with newer and more diverse watermarking approaches that similarly preserve text quality undermines the validity of the claimed improvements.

A: Thank you for your suggestion. However, we believe that we have addressed the other sparse watermark methods in the related section and pointed out the differences between their methods and ours. We have also run additional experiments comparing our method to SWEET, a watermark method that sparsely watermarks code generation, a distinction to our work that we have acknowledged in our paper. The result is available in the Public Global Comment. Nevertheless, we would appreciate it if the reviewer points out any specific relevant work that may be missing from our paper. We are willing to discuss and evaluate those works during the rebuttal process

Thank you for the comments, please see our responses below.

Q1:This paper obviously lacks baselines that are up-to-date to compare with, including but not restricted to SWEET , EWD. Simply using the standard KGW and Unigram with different hash functions is far from sufficient in proving the effectiveness of the proposed method. BTW, both SWEET and EWD proposed to selectively perform watermark generation/detection according to token entropy, and have shown better text quality/detection accuracy in their work. To prove the proposed work is better than the listed two, more experiments on text quality, time complexity, detection accuracy and using low-entropy datasets should be conducted.

A: Thank you for your suggestions. While SWEET and EWD have demonstrated strong performance in their respective setups, both methods rely on assumptions such as access to the original prompt or the use of a generalized prompt when validated on coding datasets. These assumptions may not always hold in real-world scenarios. In contrast, SpARK is designed to work effectively without relying on these assumptions, ensuring broader usability. We also have run some experiments to compare both of these methods to SpARK which can be seen in our Public Global Comment. In both SWEET[1] and EWD[2], they also tested on low-entropy code generation. However, our paper only focused on high-entropy natural text generation as our method is based on the structure of the natural language to work, and these task are more commonly used compared to code generations. 

[1] Lee et al., Who Wrote this Code? Watermarking for Code Generation. ACL 2024

[2] Lu et al., An Entropy-based Text Watermarking Detection Method. 2024.

Thank you for the comments, please see our responses below.

Q1: While the method offers an interesting approach, it lacks significant novelty. Similar methods that alter synonyms based on POS tags already exist... Additionally, because POS tagging patterns are relatively consistent across different texts, adversaries would not need to invest much effort to identify and remove the watermark.

A: In scenarios where the POS tags and seeds of the Sparse Watermark are compromised, it is indeed easier to remove the watermarked tokens compared to dense watermarks. This trade-off, inherent to sparse watermarking, also represents one of its key advantages. We acknowledge this limitation in the paper's Limitation Section and plan to expand on it in the camera-ready version, incorporating further insights from this discussion.

To address the vulnerability, one potential mitigation strategy involves dynamically altering the POS tags and seeds used in the watermarking process whenever a leak is detected. The universal POS tagging system provides flexibility for substitution, offering a variety of options to diversify the approach. Furthermore, the method's robustness can be substantially enhanced by employing a combination of multiple POS tags or leveraging the finer-grained Penn Treebank POS tagging scheme [1]. This scheme, with its 36 distinct tags, allows for a more nuanced differentiation of sentence components. By enabling greater precision and complexity in the watermarking process, such adjustments make it significantly more challenging for adversaries to reliably detect or eliminate the watermark.

[1] Taylor et. al, The Penn Treebank: An overview. 2003.

Q2:Although the POS tagging approach is well-motivated, the experiments mainly focus on three tags (Verb, Noun, Determiner), with limited analysis on why these particular tags were chosen over others beyond their document frequency. A broader exploration of different tags and their effectiveness in watermarking would strengthen the study.

A: Thank you for your comment. As noted in Appendix Section C.1, we selected three POS tags - Verb, Noun, and Determiner—based on their document frequency of 100%. This choice ensures that these tags consistently appear across all evaluated tasks, providing a stable and robust foundation for watermark application. Additionally, we conducted experiments on these tags and reported their True Positive Rates (TPR) and related metrics in the main paper.

To explore the impact of other POS tags on watermark strength and text quality, we extended our analysis to Prepositions/Postpositions, Punctuation, and Adjectives using the same experimental setup on Llama 2. The results demonstrate that these tags achieve high ROUGE-L scores, maintaining the quality of the generated text across both datasets. For Long-Form Question Answering (LFQA), all three tags achieved a TPR higher than 99%. However, for summarization tasks, Adjectives struggled to maintain high TPR due to the shorter answer length, reducing their frequency. Overall, Prepositions/Postpositions and Punctuation are viable for watermarking generated text, but Adjectives may not be as effective for shorter text generation tasks. Below are the results for these tags:

Furthermore, we conducted paraphrasing attack experiments using the DIPPER to evaluate the robustness of these additional POS tags under adversarial conditions. Our findings revealed that while all tested tags exhibited some level of detectability after paraphrasing, their robustness varied significantly. Among the three, only the Punctuation tag demonstrated detectability on par with our baseline methods, showcasing its potential as a reliable choice for watermarking even in the presence of paraphrasing attacks. We recognize the value of this analysis in advancing the robustness of our method and will include these findings, along with a detailed discussion, in the camera-ready version of the paper to provide a more comprehensive evaluation.