Sparse Watermarking in LLMs with Enhanced Text Quality

Authors: Duy Cao Hoang, Thanh Quoc Hung Le, Rui Chu, Ping Li, Weijie Zhao, Yingjie Lao, Khoa D Doan
Primary area: alignment, fairness, safety, privacy, and societal considerations
Keywords: watermarking, large language models

Abstract:
With the widespread adoption of Large Language Models (LLMs), concerns about potential misuse have emerged. To this end, watermarking has been adapted to LLM, enabling a simple and effective way to detect and monitor generated text. However, while the existing methods can differentiate between watermarked and unwatermarked text with high accuracy, they often face a trade-off between the quality of the generated text and the effectiveness of the watermarking process. In this work, we present a novel type of LLM watermark, *Sparse Watermark*, which aims to mitigate this trade-off by applying watermarks to a small subset of generated tokens distributed across the text. To demonstrate this type of watermark, we introduce **SpARK**, a **Sp**arse Waterm**ARK** method that achieves sparsity by anchoring watermarked tokens to words that have specific Part-of-Speech (POS) tags. Our experimental results demonstrate that the proposed watermarking scheme achieves high detectability while generating text that outperforms previous LLM watermarking methods in quality across various tasks.

Decision: reject
Reviewer scores: 5, 1, 3, 3

Reviews and discussion:
<thread>
creation date:
1730360668210

thread_type:
official_review

<thread_object>
creator: reviewer_fdic

<content>
summary:
The paper introduces a watermarking technique called SpARK for Large Language Models (LLMs), which selectively embeds watermarks in a small subset of generated tokens. This approach aims to maintain high text quality while ensuring watermark detectability. Experimental results demonstrate that SpARK outperforms traditional watermarking methods in text quality across various tasks and effectively withstands common attacks, such as substitution and paraphrasing. By adding watermarks to tokens of specific part-of-speech tags and only detecting these specific tokens, this method preserves text quality without compromising detectability.

strengths:
1. Although the idea may seem simple, it effectively maintains text quality by focusing watermarking on tokens with specific part-of-speech (POS) tags. This strategy helps mitigate robustness issues caused by token insertion or substitution in other positions.
2. Compared to traditional methods such as Hard Red-Green, Soft Red-Green, LeftHash, SelfHash, and Unigram, SpARK demonstrates a clear advantage in preserving text quality during watermarking.
3. The paper provides a thorough analysis of robustness against various attacks and considers resistance to watermark stealing, showcasing the method's effectiveness in real-world scenarios.

weaknesses:
1. 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.
- 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.
- Additionally, other methods that could aid in preserving text quality, such as unbiased watermark[1], DiPMark[2], TS-Watermark[3], and SWEET[4], were not included in the experiments. 

Reference:

[1] Unbiased Watermark for Large Language Models.

[2] DiPMark: A Stealthy, Efficient and Resilient Watermark for Large Language Models.

[3] Token-Specific Watermarking with Enhanced Detectability and Semantic Coherence for Large Language Models.

[4] Who Wrote this Code? Watermarking for Code Generation.

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

</thread>
<thread>
creation date:
1730522999463

thread_type:
official_review

<thread_object>
creator: reviewer_kcsa

<content>
summary:
The authors present "SpARK," a sparse watermarking method for large language models (LLMs), claiming that it achieves high detectability with minimal impact on text quality by watermarking a subset of generated tokens linked to specific POS tags. While the concept is well-explored, the novelty of this approach is questionable.

strengths:
1. Innovative Use of POS Tags: The paper introduces an innovative approach by associating watermarks with specific Part-of-Speech (POS) tags, allowing for selective, sparse embedding. This method cleverly leverages the natural structure of language, enhancing the watermark's subtlety and detectability.

2. High Detection Performance: The experiments demonstrate that SpARK achieves near-state-of-the-art detection performance (e.g., True Positive Rate and True Negative Rate close to 100%) across various datasets, while maintaining minimal text quality degradation.

weaknesses:
1. 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.

2. 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.

3. 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.

Reference: Adaptive Text Watermark for Large Language Models

questions:
1. What are the advantages of your method compared to distortion-free watermarking methods in LLMs?

2. The method proposed in the paper demonstrates a certain level of robustness against lexical substitution attacks. The paper notes that the method effectively maintains robustness when facing a 10% substitution rate, but as the substitution rate increases (e.g., 30% or 50%), the detection accuracy declines. My question is: Do you consider maintaining robustness against a 10% substitution rate as indicative of strong robustness? Additionally, is 10% sufficient for real-world application scenarios?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730644004528

thread_type:
official_review

<thread_object>
creator: reviewer_jrgn

<content>
summary:
This paper proposed a sparse text watermarking algorithm via POS (part-of-speech) with the intention to improve the text quality that could be damaged by the KGW algorithm. To be specific, the watermarking algorithm would only be activated when the next token is of a certain group of POS tags. By leaving the generation process of other types of token unchanged, the text quality of generated output can be improved.

strengths:
The idea is simple and easy to understand.

weaknesses:
This paper obviously lacks baselines that are up-to-date to compare with, including but not restricted to SWEET [1], EWD[2]. Simply using the standard KGW[3] and Unigram[4] 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.

1. Who wrote this code? watermarking for code generation

2. An Entropy-based Text Watermarking Detection Method

3. A Watermark for Large Language Models

4. Provable Robust Watermarking for AI-Generated Text

questions:
As listed in Weaknesses.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730695152520

thread_type:
official_review

<thread_object>
creator: reviewer_qc2c

<content>
summary:
The paper proposes SpARK, a new watermarking method for LLMs that aims to improve detectability and text quality. Unlike traditional methods that watermark every token, SpARK selectively watermarks tokens associated with specific POS tags, such as verbs. By embedding watermarks sparsely and only in specific token positions, SpARK enhances text coherence and robustness against adversarial attacks like synonym substitution and paraphrasing. Experimental results demonstrate that SpARK outperforms other watermarking methods regarding text quality retention and detection accuracy across various tasks and datasets.

strengths:
1. By using POS tags to select tokens for watermarking, SpARK ensures that watermarking is applied selectively and minimally, reducing the model's interference with the natural language structure.

2. The methodology section is well-structured, with algorithms (e.g., POSWatermark, DetectWatermark) clearly defined. SpARK is tested against several existing watermarking techniques (e.g., Hard, LeftHash, SelfHash, and Unigram), allowing for a direct comparison of text quality, semantic similarity, and robustness.

weaknesses:
1. While the method offers an interesting approach, it lacks significant novelty. Similar methods that alter synonyms based on POS tags already exist. This approach instead modifies logits to increase the number of "green" tokens. From a security standpoint, this method has notable weaknesses. In contrast to KGW-type watermarks—which embed watermarks in nearly every token, making it difficult for adversaries to distinguish green from red tokens—this method is more vulnerable. If adversaries know that POS tagging is used in the watermarking process, they could easily defeat it by randomly substituting verbs and nouns with synonyms. 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.

2. 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.

questions:
None
</content>
</thread_object>

</thread>
<thread>
creation date:
1732296181102

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Global Comment for additional experiment.

comment:
>To ensure a fair comparison, we evaluated EWD and SWEET on the WaterBench baseline under the same experimental conditions as described in the main paper, but without providing access to the original prompt.  From the results, we can see that while both EWD and SWEET achieve higher text quality compared to some other watermarking methods, **SpARK** consistently outperforms EWD in terms of Rouge-L scores across tasks. This indicates that **SpARK** offers a better balance between quality and detection performance, while not needing additional information.


|                     | LFQA-TPR | LFQA-TNR | LFQA-Rouge L | LFQA-Delta |
|:-------------------|:--------|:--------|:------------|:----------|
| EWD                 | 100%     | 100%     | 18.12        | -16.07%    |
| SWEET               | 99.8%    | 100%     | 18.88        | -12.55%    |
| **SpARK** (Verb)       | 100%     | 99%      | 18.87        | -12.60%    |
| **SpARK** (Noun)       | 100%     | 99.5%    | 18.48        | -14.40%    |
| **SpARK** (Determiner) | 100%     | 98.8%    | 19.20        | -11.07%    |


|                     | Sum-TPR | Sum-TNR | Sum-Rouge L | Sum-Delta |
|---------------------|---------|---------|-------------|-----------|
| EWD                 | 100%    | 100%    | 18.11       | -22.83%   |
| SWEET               | 100%    | 100%    | 18.13       | -22.71%   |
| **SpARK** (Verb)       | 100%    | 99.5%   | 20.95       | -10.74%   |
| **SpARK** (Noun)       | 100%    | 99.5%   | 18.39       | -21.64%   |
| **SpARK** (Determiner) | 100%    | 98.0%   | 20.89       | -10.99%   |


> In addition, we tested the robustness of EWD and SWEET under paraphrasing attacks using the DIPPER as the paraphrasing model. As we can see from the table below, the detectability of EWD is less than **SpARK** after being paraphrased. This shows that **SpARK** maintained higher robustness to paraphrasing attacks, highlighting its effectiveness in adversarial scenarios. On the other hand, while SWEET demonstrates high robustness against paraphrasing attacks, **SpARK** can still maintain higher detectability among the sparse watermark, while generating higher-quality text, striking a balance between adversarial robustness and text quality.

|                     |  40O | 40O-40L |
|:-------------------|:----:|:-------:|
| EWD                 | 52.7 | 38.1    |
| EWD (with prompt)   | 52.1 | 40.1    |
| SWEET               | 69.1 | 54.5    |
| SWEET (with prompt) | 69.1 | 54.5    |
| **SpARK** (Verb)       | 54.3 | 43.5    |
| **SpARK** (Noun)       | 53.9 | 41.9    |
| **SpARK** (Determiner) | 74.3 | 66.9    |

>Lastly, we assessed the computational efficiency of each method. While **SpARK** has a higher detection time compared to other watermark methods, it is still a viable option compared to other published methods that have detection time in minutes. Not to mention that both EWD and SWEET also needed access to the original LLM in order for it to detect the watermarks.

|           | Generation Time (s) | Detection Time (s) |
| --------- | ------------------- | ------------------ |
| SelfHash  | 25.92               | 0.03               |
| LeftHash  | 6.46                | 0.11               |
| Hard      | 6.45                | 0.13               |
| Unigram   | 6.45                | 0.003              |
| EWD       | 7.10                | 0.2                |
| SWEET     | 6.39                | 0.18               |
| **SpARK** | 7.89                | 1.01               |


>In conclusion, although it can incur slight overhead during detection, **SpARK** offers a more robust, reliable, and versatile solution for watermarking tasks. It outperforms EWD and SWEET in detection accuracy and text quality while staying resilient under constrained and adversarial scenarios, ensuring practical applicability in diverse real-world environments.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732543714381

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Thank you for your valuable comments and welcome additional questions!

comment:
We want to start by thanking the reviewers once more for providing constructive feedback and raising questions to help us improve the quality of our paper. We have addressed all the questions and suggestions from the reviewers in our rebuttal with new experiments as recommended. Please share your additional thoughts and we're happy to address them promptly.
</content>
</thread_object>

</thread>
<thread>
creation date:
1733034050243

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
We welcome additional questions!

comment:
We hope this message finds you well. As a gentle reminder, the deadline for providing your additional feedback is today. We greatly appreciate the time and effort you’ve dedicated to reviewing our work and providing your constructive feedback. However, since our previous reminder, we have not yet received any additional responses from reviewer. If any reviewers have any further questions or suggestions, please don’t hesitate to share them with us—we are committed to addressing them promptly.
</content>
</thread_object>

</thread>
<thread>
creation date:
1733310960218

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Summary of the rebuttal.

comment:
Thank you everyone for your helpful comments. In this work, we introduce **SpARK**, a novel watermarking method for large language models. With extensive evaluations, our method achieves state-of-the-art generation quality while also offering competitive robustness against attacks in comparison with other watermarks.

During the rebuttal process, we have:

- Provided additional experiments on other quality-preserving watermark methods, such as SWEET and EWD.
- Provided additional experiment results on different POS tags,  a wider exploration of different tags, and their effectiveness in watermarking.
- Provided additional analysis regarding the advantages of using SpARK compared to Distortion-free watermark.
- Provided additional comparisons with other watermark methods on generating overhead and detection time.
- Provided references to sections in our paper to answer the reviewers' questions.

We hope that our responses have appropriately addressed the questions of the reviewers. **SpARK** is highly applicable with the advantages in producing both a resilient watermark and cohesive text. If the reviewers have any additional comments or questions, we are more than happy to answer.
</content>
</thread_object>

</thread>


Metareview:
metareview:
The paper introduces SpARK, a sparse watermarking method for large language models (LLMs) that selectively embeds watermarks in tokens associated with specific part-of-speech (POS) tags, such as verbs. By targeting only certain POS tags, SpARK minimizes disruptions to the text generation process, preserving text quality while maintaining high watermark detectability. This selective approach also enhances robustness against adversarial attacks like synonym substitution and paraphrasing. Experimental results demonstrate that SpARK outperforms traditional watermarking methods in detection accuracy and text coherence. However, the paper raises questions about the novelty of this approach, as sparse watermarking is a well-explored concept.

The proposed method is simple yet effective. However, as pointed out by the reviewers, the topic of LLM watermarking is currently very popular, and there are numerous similar methods already available [1]. As a result, the novelty of the proposed method appears to be limited. I encourage the authors to review the existing literature, particularly surveys on LLM watermarking, and revise the paper based on the reviewers’ feedback before considering resubmission to a future venue.

[1] Watermarking Techniques for Large Language Models: A Survey
https://arxiv.org/pdf/2409.00089