Sparse Watermarking in LLMs with Enhanced Text Quality

## Abstract

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. The key strategy involves 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 1 1 1 Our code will be published soon at https://github.com/mail-research/sparse-llm-watermarking/ . .

## 1 Introduction

Recent advancements in Large Language Models (LLM) have shown exceptional performance in a multitude of tasks. From generating documents to answering questions on different topics, LLMs such as Meta’s Llama (Touvron et al., ) and OpenAI’s GPT (OpenAI, ) have become the foundation upon which many AI applications are built (Luo et al., ; Brohan et al., ; Luo et al., ; Huang et al., ). However, as these applications increase in their capabilities and accessibility, a growing risk of them being used for malicious purposes, such as generating fake news and being used for cheating assignments, becomes increasingly apparent.

With the ever-increasing problem of LLMs being misused, monitoring the generated text and its usage has become an increasingly crucial direction for research. One effective way for tracking the usage of generated text is by watermarking (Kirchenbauer et al., , ; Zhao et al., ) - embedding imperceptible information into the generated text, thereby making it easier to detect and track for potential misuse. Recent studies have demonstrated the effectiveness and versatility of watermarks in embedding ownership information into generated text and distinguishing it from non-watermarked and human-written text (Krishna et al., ).

In addition to distinguishing between watermarked and non-watermarked texts, watermarking methods must also preserve the original text quality after embedding the secret information. However, prior works generally agree that there is a trade-off between the quality of the watermarked text and the strength of its watermark. For instance, Kirchenbauer et al. () illustrates this trade-off by introducing a parameter that adjusts the extent to which their method affects the model’s logits. By tuning this parameter, they demonstrate the balance between the quality of the generated text and the robustness of the watermark.

In this paper, we aim to circumvent the trade-off between watermark strength and text quality by proposing a watermarking method that augments only a portion of the generated text and checks for that portion of the text for watermark information. The main concept is illustrated in Figure 1. We show that by watermarking only a subset of the generated text, we can still maintain high detectability while minimizing the watermark’s impact on the text quality. Our hypothesis is that while prior methods verify a watermark by checking every token within a text, the same effect can be achieved by checking only a specific portion if the locations of the watermarked elements are known. This helps preserve the quality of the generated text by keeping a large portion of the original generated text while still successfully embedding the secret information. Our contributions can be summarized as follows:

- •
We introduce Sparse Watermark, a novel category of watermarking methods for LLMs that are designed to preserve both text quality and detectability by selectively watermarking and verifying only a subset of the generated text.
- •
We propose a method of watermarking using Part-of-Speech (POS) tags, embedding and detecting watermarks based on the POS tags of words within the generated text.
- •
Through extensive experiments, we demonstrate that Sparse Watermark effectively maintains high text quality generated by LLMs and watermark detectability, outperforming several previous methods across various generation tasks.

Figure: Figure 1: An overview of our proposed Sparse Watermarking. For each generation step $t$, if the previous word belongs to the POS of interest (i.e., Verb), we divide the vocabulary into Green/Red list and only sample from the Green list. Otherwise, we generate the next token with the original probability distribution.
Refer to caption: x1.png

## 2 Related Works

#### AI-generated text detection.

The methods for monitoring the usage of AI-generated text can be generally classified into two main categories: AI text detection and watermarking. Of these, watermarking has proven to be more reliable and effective for distinguishing between generated and human-written text, as well as between watermarked and unwatermarked generated text (Krishna et al., ). In addition, as companies and research communities strive to close the gap between LLM-generated and human-written texts, relying solely on AI text detection of the original text will become increasingly challenging. The main objective of LLM watermarking is to inject secret information imperceptible to humans into the generated text, which can later be verified by using watermark detection mechanisms (Kirchenbauer et al., ; Zhao et al., ; Kirchenbauer et al., ; Liu et al., ; Gu et al., ).

#### Text watermarking for LLM.

One common approach of text watermarking for LLMs focused on distorting the next token probability distribution of the language model. This is achieved by randomly dividing the vocabulary into two disjoint sets named Green list and Red List, and then promoting the generation of only tokens in the Green list with a bias parameter $\delta$ (Kirchenbauer et al., ). During detection, a detector with the secret key could recover the watermarked distribution and use a statistical test to verify the presence of the watermark.

Recent works have attempted to improve LLM watermarking from the perspective of advancing robustness and security. For instance, Zhao et al. (); Kirchenbauer et al. () explored various schemes to enhance the robustness of watermarks. Zhao et al. () illustrated that leveraging a fixed Green list enabled watermarking to be resilient against various types of attacks. Kirchenbauer et al. () explored several hashing schemes for improved robustness. Training-based watermarks are also designed, where one study improved the robustness of the watermark using the semantics of previously generated tokens (Liu et al., ). Liu et al. () proposed to train two neural networks for text generation and watermark detection to create an unforgeable watermark. Lee et al. () introduced entropy thresholding for code generation as watermarking low-entropy tokens could compromise the correctness of the generated sequences.

#### Effects of watermark on text quality.

However, while these recent works have considerably enhanced the robustness, detectability, and unforgeability of LLM watermarking, it is generally agreed that there is a trade-off between the quality of the watermarked text and the strength of its watermark. The distribution shift introduced in Kirchenbauer et al. () enhances the detectability of the watermark, but it simultaneously allows less likely tokens to be generated, thus affecting the intrinsic quality of the generated text. Recently, Tu et al. () introduced a benchmark method of several LLM watermarking algorithms and verified this deterioration of text quality. To minimize the impact on the generation quality, Christ et al. (); Kuditipudi et al. () proposed to embed the watermark during the token sampling process, thus inducing zero distortion to the probability distribution of the LLM. However, in practice, the sampling-based schemes struggled to produce a detectable watermark for low-temperature settings (Piet et al., ). Huo et al. () introduced a multi-objective optimization method to dynamically generate bias parameters and Green list ratio to achieve both detectability and semantic coherence. In contrast, our approach, Sparse Watermark, emphasizes preserving the strength and semantic integrity of generated text by leveraging the innate structure of natural language, eliminating the need for training.

## 3 Proposed Method

### 3.1 Notations and Preliminaries

We first introduce the notations used in this paper. Let $\mathcal{M}$ be an autoregressive language model that takes a tokenized prompt $\textbf{x}_{\text{prompt}}=\{x_{-N},...,x_{-2},x_{-1}\}$ and output a sequence of tokens that simulate natural responses. At generation step $t$, the input for the language model $\mathcal{M}$ is combined sequences of tokens $\textbf{x}_{\text{prompt}}$ and the tokens $\textbf{x}=\{x_{0},...,x_{t-1}\}$ previously generated by $\mathcal{M}$ in the previous steps. The language model $\mathcal{M}$ then takes the input and outputs a probability distribution of the next token over the vocabulary $\mathcal{V}$ of the language model: $P_{\mathcal{M}}(x_{-N},...,x_{t-1})=(P_{\mathcal{M}}(\upsilon|x_{-N},...,x_{t-
1})|\upsilon\in\mathcal{V})$.

According to Kirchenbauer et al. (), watermark algorithms are defined using four parameters. The hash function $\mathcal{H}$ generates a pseudo-random $hash$ using the context of the generated text with context width $h$, the fraction of green list token $\gamma$, and the magnitude of the logit bias $\delta$. After the watermarked text is generated, one can use the same parameters to calculate and retrieve a set of green tokens $s$ in the generated text. We then use this set to calculate the statistical significance of $|s|$ number of green tokens that appeared in the generated text with token length $T$. We can use a one-proportion z-test assuming the null hypothesis $\mathcal{H}_{0}$ which states: “The text sequence is generated without a watermark”. The z-score is then calculated as

$$ $z=\frac{|s|-\gamma T}{\gamma\sqrt{(1-\gamma)T}}.$ (1) $$

When a text sequence has a $z$-score that exceeds a specified threshold, we can confidently say that the text is watermarked. While some watermark methods are defined differently, most of the methods follow a similar definition.

### 3.2 Threat Models

In this paper, we consider the same threat model as in prior works (Kirchenbauer et al., ; Zhao et al., ; Liu et al., ). The goal is to embed a watermark for LLM so that users can later verify if certain texts are generated by the LLM.
We assume that the adversary is aware of the presence of watermarks and attempts to evade the watermark detection when using the LLM. The adversary could have access to both open-source and private (non-watermarked) language models to produce an alternate text. Consistent with prior works, we only consider attacks such that the modifications are able to erase the watermark without significantly deviating from the original semantics of the sentence.

### 3.3 Sparse Watermarking using POS Tags

In previous works, most watermarking techniques attempt to encode watermark information into each token in the generated text. As the strength of the watermarking method increases, more tokens are adversely affected, which decreases the quality of the generated text (Kirchenbauer et al., ). We aim to improve the text quality by watermarking the generated text sparsely, which however is non-trivial. Attempting to watermark sparsely without knowing the location of the watermarked elements would be akin to using the previous watermark methods with low strength. This is due to the statistical test also including the non-watermarked portions of the generated text. To this end, by isolating and conducting the statistical test specifically on the watermarked portions of the generated text, we can significantly enhance detectability while maintaining higher text quality compared to using previous methods with stronger watermarking.

Figure: Algorithm 1 Text Generation with Sparse Watermark

Figure: Algorithm 2 Sparse Watermark Encoding

We utilize the Universal Part-of-Speech (POS) tags (Petrov et al., ) that exist in the generated text to mark the positions of the watermarked tokens in the text sequence. Specifically, during the generation process, we select the positions to watermark based on the POS of tokens that have been generated, allowing the watermark positions to be tied to the sentence structure. This makes the watermark more resilient to insertions/deletions of tokens in the generated text and also makes it easier to extract the watermarked portion of the text using the POS tags.

Before using Sparse Watermark, we first select a list of POS tags $I$ to be used for watermarking. When the text generation process starts, as described in Algorithm 1, we verify when the model has generated a full word by determining if the next token with the highest probability is the start of a new word. While LLMs sample the next token differently with different sampling schemes, using this strategy could consistently inform us when a full word has been generated, without the need to backtrack during the generation process. Once a full word is produced by the language model, we obtain its POS tag $P_{tag}$, and watermark the next token only if $P_{tag}\in I$. We choose to watermark the token next to the word with chosen POS tags, as watermarking those words directly would not guarantee it to have the same POS tag after being watermarked, leading to inconsistencies. By using words that have a selected POS as an anchor, we can limit the number of watermarked tokens in the generated text and position them to be easily relocated when decoding. We outline the process of watermarking using POS tags in Algorithm 2.

To watermark the next token, we used a similar process and hashing scheme as described in Kirchenbauer et al. (), partitioning the vocabulary using $\gamma$ and limiting the generations of new tokens to a subset of the vocabulary, the Green list $G$. While dividing the vocabulary, we only select tokens that start a new word, as it would not affect the previous words and their POS tags, making the decoding process more consistent. Additionally, our method does not use $\delta$ to increase the bias for generating green list tokens, but instead, we restrict the model to only select from the Green list. This helps the encoding process to utilize all of the tokens it has access to, as it can only watermark a small portion of the generated text.

### 3.4 Watermark Detection

Since our watermark is sparse, we identify the specific positions we have selected for the watermark to ensure that the unwatermarked portions of the text are not considered in the z-score calculation. This process would preserve the strength of the sparse watermark. We first identify the words whose POS tags are in the list $I$ and select the next token. These selected tokens are the ones we would watermark during the encoding process and thus would be in the Green list $G$. At each of the selected token positions, we recover the $G$ using the hashing scheme mentioned in the encoding process and check if the token in that position is in $G$. We then calculate the statistical significance of the number of green tokens that appeared in the generated text, as shown in Equation 1. However, as we only apply the watermark to tokens after the words with a specific POS, $T$ (the total number of tokens) would be replaced by the number of tokens in the watermarked positions. The watermark detection step is presented in Algorithm 3.

Figure: Algorithm 3 Watermark Detection

## 4 Experiments

### 4.1 Experimental Setup

We choose Llama2-7B-chat, a popular open-sourced LLM that has been instruction-tuned to align with human preference, as our baseline model for testing the watermarking methods. We compare the performance of our proposed method against four LLM watermarking techniques:

- •
Hard watermark: The initial watermark method proposed by Kirchenbauer et al. (). This method restricts the model to only generating a portion of the vocabulary, referred to as the Green list, and uses the statistical test to detect the watermark.
- •
LeftHash watermark (Soft watermark): A watermark method proposed by Kirchenbauer et al. (). The method is similar to Hard watermark, but this watermark encourages the model to generate tokens from the Green list by adding a constant $\gamma$ to the output logit, instead of restricting the model. We refer to this method as LeftHash to differentiate this method from another method proposed in Kirchenbauer et al. ().
- •
SelfHash watermark: A watermark method proposed by Kirchenbauer et al. (). This watermark method is similar to LeftHash watermark, as it encourages the model to generate from the Green list as well. The main difference is that this watermarking method chooses tokens that contain themselves in the Green list during hashing, increasing robustness.
- •
Unigram watermark: A watermark method that simplifies the watermark process by utilizing a fixed Green list used to watermark text (Zhao et al., ). Their work shows that this restriction increased the robustness of the watermark.

Figure: Figure 2: True Positive Rate (TPR) for each method on the selected dataset, generated using Llama2-7B-chat with different hyper-parameters for $\gamma$ and $\delta$.
Refer to caption: x2.png

To validate the detectability and the quality of the text generated by the watermark methods, we used an experiment setting similar to WaterBench (Tu et al., ). This benchmark procedure aims to measure both the quality of the generated text and its detectability. However, we made some adjustments to the experiment setup, mainly:

- •
We focused the experiment only on the long-answer datasets. This is because short-answer datasets selected in the WaterBench contain answers that are on average fewer than three tokens long. Because of how short the answers are, we argue that watermarking these short answers is unnecessary, and trying to watermark these short answers can cause the quality of the watermarked text to deteriorate and affect the correctness of the response. Other papers also conduct experiments on similar datasets to long-answers dataset (Kirchenbauer et al., ; Gu et al., ). We conduct the same hyper-parameter search experiments on long-answer datasets to find parameters that are more suitable to watermark these long text answers. The watermarking strength results are shown in Figure 2.
- •
During the hyper-parameter search, we select the parameters that are close to the original parameters in the method’s paper and have a True Positive Rate of more than 0.99. As the selected dataset contains longer answers on average, the search resulted in more parameters that are closer to their original parameters and can guarantee above 99% of the watermarking strength.

To summarize, we select the ELI5 (Explained Like I’m 5) dataset (Fan et al., ) and the FinanceQA dataset (Maia et al., ), both of which focus on short questions with long answers, along with MultiNews (Fabbri et al., ) and QMSum (Zhong et al., ), which focuses on text summarization. These four datasets are grouped into two tasks, Long-form QA and Summarization. We then conduct a hyper-parameter search by evaluating the TPR of each method using different hyper-parameters. As shown in Figure 2, the strength of the watermark increases as $\gamma$ decreases and $\delta$ increases, The figure also shows that most watermark methods achieved over 0.99 of TPR if $\delta$ is high enough, which helps us choose a $\gamma$ that is close to the original parameters of each method. We then select hyper-parameters closest to the original paper, while having a TPR of over 0.99.

For the Sparse watermark, we selected three POS tags for the main experiment: Verb, Noun, and Determiner. This is because, based on Table 6, these three tags have 100% of document frequency. We selected $\gamma=0.05$ for the sparse watermark, to increase the strength of each watermark token in the sparse watermark. By choosing a small $\gamma$, we demonstrate that the Sparse watermark can match other baseline methods in detectability, while also maintaining higher generation performance. We also provide the results containing the TPR of sparse watermark under different POS tags and $\gamma$.

**Table 1: Comparison of True Positive Rate (TPR), True Negative Rate (TNR), ROUGE-L score (R-L), decrease in percentage point of ROUGE-L score ($\Delta$) and the semantic similarity of watermarked and non-watermarked text (Sem.) of different watermarking algorithms. The best and second-best performances are in bold and underline, respectively.**
|  | Long-form QA | Summarization | Sem. |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
|  | TPR | TNR | R-L | $\Delta$ | TPR | TNR | R-L | $\Delta$ |  |
| No Watermark | – | – | 21.59 | – | – | – | 23.47 | – | – |
| Hard | 100.0 | 100.0 | 16.76 | $\downarrow$ 22.37% | 100.0 | 100.0 | 16.63 | $\downarrow$ 29.14% | 0.765 |
| LeftHash | 100.0 | 100.0 | 14.55 | $\downarrow$ 32.61% | 99.5 | 99.5 | 13.33 | $\downarrow$ 43.20% | 0.693 |
| SelfHash | 99.5 | 93.5 | 12.75 | $\downarrow$ 40.94% | 100.0 | 96.0 | 12.54 | $\downarrow$ 46.57% | 0.663 |
| Unigram | 99.8 | 100.0 | 11.43 | $\downarrow$ 47.06% | 99.3 | 100.0 | 11.53 | $\downarrow$ 50.87% | 0.652 |
| Sparse - Verb | 100.0 | 99.0 | 18.87 | $\downarrow$ 12.60% | 100.0 | 99.5 | 20.95 | $\downarrow$ 10.74% | 0.836 |
| Sparse - Noun | 100.0 | 99.5 | 18.48 | $\downarrow$ 14.40% | 100.0 | 100.0 | 18.39 | $\downarrow$ 21.64% | 0.794 |
| Sparse - Determiner | 100.0 | 98.8 | 19.20 | $\downarrow$ 11.07% | 100.0 | 98.0 | 20.89 | $\downarrow$ 10.99% | 0.814 |

### 4.2 Results of Detectability and Text Quality

As mentioned in Section 4.1, we conduct evaluations with parameters that achieved greater than 0.99 TPR and close to the original parameters of each method. We report the results of the watermarks’ performance in Table 1.

Overall, the detection performance of the baseline watermark method is high, having above 99% True Positive Rate and True Negative Rate in both tasks. In addition, tuning the parameter for long-answer text increased the generation performance of all watermark methods without degrading their detectability. Compared to the baseline watermark methods, our Sparse watermark achieved similar detection performance, while consistently achieving the highest generation performance in both tasks. All three of the Sparse Watermark using different POS tags reached the top 3 spots in terms of generation performance. When using one of the three Sparse watermark variants, the ROUGE-L score of the original model would only be reduced by at most $21.64\%$. In contrast, the performance of other watermarks would decrease that down by at least $22\%$ and at most more than $50\%$. These Sparse Watermark variants also have the highest semantic similarity between the non-watermarked text and watermarked text, with the highest being $0.836$ and the lowest being $0.794$.

In summary, Sparse watermarks produce better-generated texts, both in terms of semantic similarity and task performance, while having the same detectability. By watermarking a small portion of text sparsely and anchoring each watermarked token with a POS tag, a Sparse watermark can preserve the performance and similarity of the generated text, while maintaining detectability by focusing the detection on smaller sets of tokens.

**Table 2: Average True Positive Rate under two settings of attacks: synonym substitution and paraphrasing (DIPPER). The best and second-best performances are in bold and underline, respectively.**
|  | Substitution Attack | DIPPER |  |  |  |
| --- | --- | --- | --- | --- | --- |
|  | 10% | 30% | 50% | 40L | 40L-40O |
| Hard | 99.6 | 90.6 | 51.1 | 53.0 | 41.0 |
| LeftHash | 99.8 | 99.0 | 83.9 | 71.4 | 64.1 |
| SelfHash | 99.8 | 98.1 | 92.3 | 75.0 | 69.5 |
| Unigram | 99.5 | 96.9 | 91.4 | 59.8 | 50.9 |
| Sparse - Verb | 99.8 | 96.3 | 72.4 | 54.3 | 43.5 |
| Sparse - Noun | 100.0 | 97.8 | 78.3 | 53.9 | 41.9 |
| Sparse - Determiner | 99.8 | 96.5 | 67.6 | 74.3 | 66.9 |

### 4.3 Results of Robustness against Attacks

As malicious players have the capability of modifying a sequence of watermarked text to evade the detector, watermarking methods need to ensure that the watermark is resilient against changes to the text. In order to illustrate the robustness of our proposed approach, we consider two realistic types of attack: substitution attack and paraphrasing attack.

Substitution Attack. For the substitution attack, a specified proportion of the text (equal to some $r$ tokens) is replaced with its corresponding synonyms. However, it is worth noting that a simplistic replacement can compromise the semantic coherence of the sentence. Following the settings described in (Wang et al., ), we iteratively masked a random token that has yet to be modified and then utilized RoBERTa-Large to generate candidates for replacement. To ensure the semantic integrity of the perturbed text, we only select to substitute a new token if the difference in logits of the new token and the original is higher than our pre-defined threshold, which we set to be -1. If there is no token that satisfies the preceding requirement, we proceed to mask a different token. The process is terminated when we have replaced $r$ tokens or we have attempted to replace $3r$ tokens.

Table 2 demonstrates the resilience of our method against substitution attack, with sparse watermarks achieving the best performance for the $10\%$ scenario. For higher rates such as $30\%$, the robustness of our proposed method lessens, but they remain competitive with other watermarking algorithms. Detailed results of each dataset for the substitution attack can be found in Table 8 of the Appendix.

Paraphrasing Attack. In addition to the substitution attack, we also evaluate the robustness of our proposed method against paraphrasing attack using DIPPER (Krishna et al., ). DIPPER is an 11B parameter model that has been specially fine-tuned from T5-XXL (Raffel et al., ) for the task of paraphrasing. It has been demonstrated to successfully evade multiple AI-generated text detectors while also preserving the general semantics of the sentence. We assess the performance of our watermarking schemes for two attack settings: 40L, where the lexical diversity is set to 40, and 40L-40O, where the lexical and order diversity are 40. With these configurations, DIPPER is able to produce a strong paraphrasing attack and maintain a high degree of semantic similarity with the original sentence.

The results of the paraphrasing attacks are summarized in Table 2. The performance of Sparse Watermark with determiner is demonstrated to be near state-of-the-art in terms of robustness, achieving $74.3\%$ and $66.9\%$ in true positive rate, only $0.7$ and $2.6$ percentage points behind SelfHash, under 40L and 40L-40O paraphrasing, respectively. The performance of each method for all datasets can be found in Table 9 of the Appendix.

**Table 3: Examples from the QMSum dataset generated by Llama2-7b-chat with no watermark (NW), with SelfHash (SH), and with Sparse Watermark - Determiner (SW-Det), respectively. Results of z-score and semantic similarity (Sem.) of each watermarking method are also reported. The hyper-parameter ($\gamma$,$\delta$) for SelfHash is ($0.25,10$), and the hyper-parameter $\gamma$ for Sparse Watermark is $0.05$.**
| Prompt | 
You are given a meeting transcript and a query containing a question or instruction. Answer the query in one or more sentences.\n\nTranscript:\nUser Interface: …\n\nQuery: What did the Marketing think of buttons when discussing the functional design of the remote control?\nAnswer:
 | $z$-score | Sem. |
| --- | --- | --- | --- |
| NW | Based on the meeting transcript, the Marketing person suggested that there should be no buttons on the remote control, as most people only use a small number of buttons on their existing remote controls, and having too many buttons can be confusing. Instead, they proposed using a menu-based system or a single button for a menu. | - | - |
| SH | At the meeting, the marketingperson suggested eliminating unnecessarybuttons on the remote controlaimulating a more user-frienf design. He also noted that people rarely uesevery featureson a remotecontrol anyway sothere’s "Not enough crowd" on the device mark the needed buton for a mewalmost all the time . Therefore , the Markettion believed the onerouse was to consilder a more minimalinconvenie _ design f the product Marktng’s view was to focus the user expdria and keep the device slew a d simple… … | $16.99$ | $0.298$ |
| SW-Det | Based on the extract, the design manager expressed that the design project team should aim to create a remote control with fewer buttons than usual, as most people do not use their TV remote controls’ full capacity. The Designer also suggested that a minimalist approach could be beneficial, with only one button for a shortcut menu | $11.53$ | $0.726$ |
|  |  |  |  |

### 4.4 Empirical Effects on z-score and Text Quality.

To demonstrate Sparse Watermark’s ability to maintain both high detectability and preserve the semantic meaning of the non-watermarked generation, we provide an example of watermarking applied to an answer in QMSum using SelfHash and Sparse Watermark - Determiner. This table visually demonstrates the watermarked tokens and their corresponding list, with tokens found in the Red list represented in red, and tokens found in the Green list represented in green. As we can observe in Table 3, techniques like SelfHash aim to watermark every token when generating, while Sparse Watermark only focuses on watermarking only a fraction of the generated tokens. While SelfHash has a largeGreen list with $\gamma=0.25$, the quality of the text being generated by SelfHash has a lower similarity, only $(0.298)$ due to the number of tokens it encodes. Sparse Watermark, on the other hand, even when having a smaller green list ($\gamma=0.05$), the generated text has a higher semantic similarity than SelfHash $(0.726)$, thanks to encoding fewer tokens. While SelfHash’s generated text does have a higher $z$-score ($16.99$) compared to Sparse Watermark’s $11.53$, it is worth emphasizing that the number of tokens used in Sparse Watermark is a lot smaller. Sparse Watermark is able to maintain a similar level of detectability to SelfHash as seen in Section 4.2. Additional watermarked text examples from different watermark methods in different datasets can be found in Section H of the Appendix.

## 5 Conclusion

In this work, we propose Sparse Watermark, a novel watermark method for LLM, that encodes watermark information into the generated text, without degrading its quality. Different from other methods, this approach focuses on encoding a subset of tokens distributed sparsely throughout the generated text. By encoding a small subset of tokens in the generated text and focusing on those subsets for watermark detection, Sparse Watermark can minimize the impact of the watermark on the text quality while maintaining high detectability. Experimental results demonstrate the effectiveness of our Sparse Watermark in preserving the text quality, as evidenced by its state-of-the-art ROUGE-L score and semantic similarity for four datasets compared to other methods. Despite watermarking at a lower rate than other approaches, our watermark can maintain a competitive degree of robustness under both substitution and paraphrasing attacks.

## Appendix A Theoretical Support for Methods

### A.1 Notations

- •
$\textbf{x}_{prompt}=\{x_{-N},\ldots,x_{-1}\}$: Tokenized prompt.
- •
$\textbf{x}=\{x_{0},\ldots,x_{t-1}\}$: Sequence of previously generated tokens.
- •
y: Generated Text / Normal text.
- •
$P_{\mathcal{M}}(x_{-N},\ldots,x_{t-1})$: Probability distribution of the next token generated by the language model $M$.
- •
$T$: Normal text converted from tokens $\textbf{x}_{prompt}$ and x.
- •
$W$: Last word in $T$.
- •
$P_{tag}(x)$: POS tag of word $x$.
- •
$I$: Set of selected POS tags for watermarking.
- •
$G$: Green List.

### A.2 Mathematical Formulation

#### POS Tag Selection:

Define a set of POS tags $I$ chosen for watermarking based on their frequency and relevance in the text. For example:

$$ $I=\{\text{DET}\}$ $$

In this work, we only select a single POS tag to watermark. This is because the tags we used, Universal POS tags, are composed of smaller POS tags defined by Penn Treebank. For example, the Universal tag DET when converted to Penn Treebank POS tags would look like so:

$$ $I=\{\text{DT},\text{EX},\text{PDT},\text{WDT}\}$ $$

#### Token Generation Process:

For each generation step $t$, the language model $\mathcal{M}$ generates a probability distribution over the vocabulary $\mathcal{V}$:

$$ $P_{\mathcal{M}}(x_{-N},\ldots,x_{t-1})=\left(P_{\mathcal{M}}(\upsilon\mid x_{- N},\ldots,x_{t-1})\mid\upsilon\in\mathcal{V}\right)$ $$

#### POS Tag Identification:

Determine the POS tag $P_{tag}(W)$ of the last word $W$ by using a POS parser:

$$ $P_{tag}(W)=\text{POS}(W,T)$ $$

Here, $\text{POS}(W,T)$ represents the function that returns the POS tag of the word $W$ based on its position in text $T$.

#### Watermark Application:

If the POS tag $P_{tag}(W)\in I$, apply the Green List $G$ to the probability distribution, modifying it to embed the watermark:

$$ $\tilde{P}_{\mathcal{M}}=\text{ApplyGreenList}(P_{\mathcal{M}},G)$ $$

The modified probability distribution $\tilde{P}_{\mathcal{M}}$ will be used to generate the next token.

#### Green List Generation:

The function $\text{GenerateGreenList}(T,\textit{hash})$ generates the list of green tokens $G$ based on the current context $T$. This list is used to modify the probability distribution of the next token:

$$ $G=\text{ApplyGreenList}(T,\text{hash})$ $$

## Appendix B Additional Implementation Details

### B.1 Hyper-parameters of Baseline Watermark Methods

**Table 4: Hyper-parameters for each baseline watermark method used in the main experiment.**
| Parameters | Hard | LeftHash | SelfHash | Unigram |
| --- | --- | --- | --- | --- |
| $\gamma$ | 0.5 | 0.25 | 0.25 | 0.5 |
| $\delta$ | - | 10 | 10 | 15 |
| $z$-threshold | 4.0 | 4.0 | 4.0 | 4.0 |

To obtain the hyper-parameters for each baseline watermark method to be used in the main experiment, we conduct the same hyper-parameter search explained in the original paper by Tu et al. []. We select the "Watermark Strength", which is the True Positive Rate to be 0.99 or above, as all baseline watermarks can achieve high watermarking strength while only adjusting $\delta$. This is because we tuned the hyper-parameters on only the long-answer dataset. All the hyper-parameters selected for the main experiments can be seen in Table 4.

### B.2 Hyper-parameter Tuning for Sparse Watermark

**Table 5: True Positive Rate (TPR) of the Sparse Watermark on different POS tags.**
| POS Tags | Gamma ($\gamma$) |  |  |  |
| --- | --- | --- | --- | --- |
| 0.05 | 0.1 | 0.25 | 0.5 |  |
| Verb | 100.00% | 100.00% | 97.63% | 77.38% |
| Noun | 100.00% | 99.88% | 98.50% | 85.75% |
| Determiner | 100.00% | 99.88% | 96.13% | 55.50% |
| Preposition and Postposition | 100.00% | 99.63% | 95.25% | 63.00% |
| Punctuations | 99.63% | 99.63% | 90.88% | 62.63% |
| Adjective | 97.75% | 94.25% | 77.38% | 22.38% |

To find the hyper-parameters for the Sparse Watermark, we conduct the same hyper-parameter search process used for the baseline watermark. We decided only to conduct the search on POS tags that have a document frequency of 99% or over, as we want to use the POS tags that have a near guarantee of occurring in a document. From Table 5, we can see that Punctuations and Adjectives cannot give a 100% True Positive Rate, even with a gamma of 0.05. This is because the chance of adjectives appearing in a document is 99%, which can cause some generated samples to be unwatermarked. While punctuations have a high document frequency, a lot of answers only use punctuations at the end of the sentence, which causes the generated text to be unwatermarked as well.

From the True Positive Rate shown in Table 5, we selected $\gamma=0.05$ for all of the Sparse Watermarks in every experiment. By choosing this hyper-parameter, we show that Sparse Watermark can achieve high detection performance while having generation performance higher than all of the baseline methods, even while the True Positive Rate is at 100%.

### B.3 Implementation of Semantic Similarity

In this paper, we measure the closeness in semantics of watermarked and non-watermarked texts to understand the semantic distortion of applying a watermark to an LLM. Results of semantic similarity in Table 1 are calculated by computing the cosine similarity between the embeddings produced by SimCSE [Gao et al., ] of texts generated with and without watermark. SimCSE leverages contrastive learning to train BERT [Devlin et al., ] and RoBERTa [Liu et al., ] models for generating sentence embeddings.

## Appendix C Analysis on the POS Tags

### C.1 Document Frequency of the POS Tags

As our Sparse Watermark uses a POS tag to mark the positions of the watermarked text, not all POS tags would occur during the generating process. Because of this, we calculated the document frequency of each POS tag that appeared in the provided answers from the datasets. This is to show which POS tags can occur in the answers, and thus have a high chance of occurring when language models generate answers for similar tasks. As we can see in Table 6, the chance of appearing in a document for most of the POS tags is quite high, with only Numbers(NUM) and Others(X) not having a document frequency of over 95%. This shows that there are other POS tags apart from the main experiments that can be used for Sparse Watermark, albeit with less effectiveness. Among the POS tags, we selected Verbs (VERB), Determiners (DET), and Nouns (NOUN), as these three tags have a document frequency of 100%. This implies these three parts of speech would exist in every answer to these tasks, and would also exist in every answer generated by the language model for these tasks

**Table 6: Document frequency of each POS tag.**
| POS tags | VERB | DET | NOUN | PUNC | ADP | ADJ | ADV | PRON | PRT | CONJ | NUM | X |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Doc frequency (%). | 100.0 | 100.0 | 100.0 | 99.8 | 99.6 | 99.0 | 97.5 | 96.1 | 96.0 | 95.7 | 67.7 | 13.0 |

### C.2 Percentage of Occurrence for POS Tags

Figure: Figure 3: Percentage of occurrences for each POS tag.
Refer to caption: x3.png

While the document frequency table shows the probability of a POS appearing in a text, knowing how much of a text is composed of words that belong to a POS tag would also be important. This is because, from that number, we can estimate the percentage of tokens in the text being watermarked when using a POS tag, as each watermarked token will be anchored into each part of speech. We calculate the percentage of occurrences for each POS tag and present it in Figure 3.

From the numbers shown in Figure 3, verbs and nouns occur the most often in a text, while determiners occur less than punctuation and ADP (preposition and postposition). This shows that during the text generation process, the Sparse watermark would encode more tokens when using Verbs and Nouns, and fewer tokens when using Determiners, which would affect the generation performance. This can be seen in Table 1, where the Sparse watermark with Nouns got the lowest generation performance among the three Sparse watermarks, while Determiners have the highest performance.

### C.3 Average Entropy for Token Predictions after POS Tags

Figure: Figure 4: Average entropy of the next token’s prediction after each POS tag.
Refer to caption: x4.png

While reducing the number of tokens to watermark helps improve the generation quality of the watermarked text, several works in watermarking have shown that the encoding of watermark information when the entropy of the next token prediction is high also helps increase the generation performance [Huo et al., , Lee et al., , Liu and Bu, ]. To see if this phenomenon affects the generation quality when we use different POS tags for Sparse Watermark, we calculate the average entropy of the next token prediction when watermarking using different tags.

As shown in Figure 4, Determiners (DET) have a high average entropy, affecting the quality of generated text less, while Verbs and Nouns have a lower average entropy. These results further explain the differences in the generation performances between using Nouns, Verbs, and Determiners for watermarking.

## Appendix D Additional Results from the Main Experiments

In Section 4, we showed the average results for both the main results for each task. Due to the page limit, the detailed results for each dataset are in this section. We show the watermarking results for every watermark method in each dataset. As shown in Table 7, datasets from the same task may have different performance results, some methods may also perform better in one dataset and worse in another. This shows the need to test the watermark methods on multiple datasets in different tasks. Overall, Sparse Watermark still generates better answers compared to other watermark methods in every task.

In addition, we also show the results robustness results for every watermark method in each setting and dataset. As can be seen from Table 8 and 9, most watermark methods struggle to preserve their encoded information when validating on QMSum. This is because QMSum’s answers are shorter compared to other datasets, as shown in Tu et al. [].

**Table 7: Comparison of True Positive Rate (TPR), True Negative Rate (TNR) and ROUGE-L score (R-L) of different watermarking algorithms for all 4 datasets.**
|  | FinanceQA | ELI5 | MultiNews | QMSum |  |  |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
|  | TPR | TNR | R-L | TPR | TNR | R-L | TPR | TNR | R-L | TPR | TNR | R-L |
| No Watermark | – | – | 21.59 | – | – | 21.59 | – | – | 26.15 | – | – | 20.78 |
| Hard | 100.0 | 100.0 | 17.65 | 100.0 | 100.0 | 15.87 | 100.0 | 100.0 | 17.75 | 100.0 | 100.0 | 15.51 |
| LeftHash | 100.0 | 100.0 | 15.01 | 100.0 | 100.0 | 14.08 | 100.0 | 99.0 | 13.25 | 99.0 | 100.0 | 13.40 |
| SelfHash | 100.0 | 98.0 | 14.76 | 99.0 | 89.0 | 10.74 | 100.0 | 93.0 | 12.40 | 100.0 | 99.0 | 12.67 |
| Unigram | 99.5 | 100.0 | 11.77 | 100.0 | 100.0 | 11.08 | 100.0 | 100.0 | 10.28 | 98.5 | 100.0 | 12.77 |
| Sparse - Verb | 100.0 | 98.5 | 19.65 | 100.0 | 99.5 | 18.09 | 100.0 | 100.0 | 23.48 | 100.0 | 99.0 | 18.42 |
| Sparse - Noun | 100.0 | 99.0 | 18.41 | 100.0 | 100.0 | 18.54 | 100.0 | 100.0 | 20.40 | 100.0 | 100.0 | 16.37 |
| Sparse - Determiner | 100.0 | 99.5 | 19.08 | 100.0 | 98.0 | 19.32 | 100.0 | 98.0 | 22.66 | 100.0 | 98.0 | 19.11 |

**Table 8: True Positive Rate of different watermarking methods under three settings of substitution attack for all 4 datasets.**
|  | FinanceQA | ELI5 | MultiNews | QMSum |  |  |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
|  | 10% | 30% | 50% | 10% | 30% | 50% | 10% | 30% | 50% | 10% | 30% | 50% |
| Hard | 100.0 | 100.0 | 61.5 | 100.0 | 100.0 | 72.5 | 99.5 | 99.5 | 59.0 | 99.0 | 63.0 | 11.5 |
| LeftHash | 100.0 | 100.0 | 97.5 | 100.0 | 99.5 | 96.0 | 99.5 | 99.0 | 98.0 | 99.5 | 97.5 | 77.5 |
| SelfHash | 100.0 | 98.5 | 96.5 | 99.5 | 98.5 | 93.5 | 100.0 | 97.0 | 91.5 | 99.5 | 98.5 | 84.0 |
| Unigram | 100.0 | 100.0 | 99.0 | 99.5 | 99.5 | 97.0 | 100.0 | 99.5 | 95.0 | 98.5 | 88.5 | 44.5 |
| Sparse - Verb | 100.0 | 100.0 | 88.5 | 100.0 | 100.0 | 83.5 | 100.0 | 99.5 | 80.0 | 99.0 | 85.5 | 37.5 |
| Sparse - Noun | 100.0 | 100.0 | 94.5 | 100.0 | 100.0 | 75.0 | 100.0 | 100.0 | 92.5 | 100.0 | 91.0 | 51.0 |
| Sparse - Determiner | 100.0 | 99.0 | 78.0 | 100.0 | 97.5 | 61.5 | 100.0 | 99.5 | 82.5 | 99.0 | 90.0 | 48.5 |

**Table 9: True Positive Rate of different watermarking methods under two settings of paraphrasing attacks for all 4 datasets.**
|  | FinanceQA | ELI5 | MultiNews | QMSum |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
|  | 40L | 40L-40O | 40L | 40L-40O | 40L | 40L-40O | 40L | 40L-40O |
| Hard | 64.5 | 55.5 | 73.0 | 54.0 | 40.0 | 32.5 | 34.5 | 22.0 |
| LeftHash | 80.5 | 70.5 | 78.5 | 67.5 | 62.5 | 59.5 | 64.0 | 59.0 |
| SelfHash | 86.0 | 83.0 | 70.0 | 66.5 | 74.5 | 63.5 | 69.5 | 65.0 |
| Unigram | 85.5 | 72.5 | 59.0 | 53.5 | 57.0 | 45.5 | 37.5 | 32.0 |
| Sparse - Verb | 75.0 | 58.5 | 79.5 | 68.5 | 37.0 | 32.5 | 25.5 | 14.5 |
| Sparse - Noun | 67.0 | 53.0 | 49.0 | 45.0 | 62.5 | 46.0 | 37.0 | 23.5 |
| Sparse - Determiner | 75.5 | 66.0 | 78.0 | 76.0 | 69.5 | 64.0 | 74.0 | 61.5 |

## Appendix E Limitations

Although Sparse watermark provides a way to encode watermark information with high detectability while preserving the generated text quality, there are some limitations that can be improved. As shown in Section 4.3, Sparse Watermark can achieve high robustness with only determiners, while nouns and verbs achieve slightly higher robustness than Hard Watermark. This indicates that while the Sparse watermark can be robust to attacks, its robustness is usually low compared to other watermark methods and only gets higher when certain POS tags are used. Sparse watermark is also limited to watermarking Universal Tags currently [Petrov et al., ], which reduced the possible configuration of this watermark. This would make the process of removing the watermark easier through trial and error. However, since a Universal POS tag can be broken down into a different set of POS tags defined by The Penn Treebank [Taylor et al., ], formulating different tag sets from Penn Treebank tags would make the watermarking removal process of trial and error harder, negating this problem. Lastly, Sparse Watermark has a hard time watermarking short answers, as short answers sometimes do not contain the words that can be used to watermark. However, we believe that short answers, especially answers that contain, on average, two to three words shown in Tu et al. [], can be found through the use of search engines. Tasks with long answers such as Summarization and Long-form Question Answering utilize LLM’s unique text-generating capabilities, in which watermarking would be a lot more useful. These limitations are quite interesting for boosting the effectiveness of our current method, which we will leave for future work .

## Appendix F Computational Resources

Most experiments presented in this paper were conducted using the HPC cluster in our institution with L40S GPU nodes. Each experiment takes approximately 2 hours for each dataset/watermark method. For paraphrasing experiments using DIPPER, each dataset took approximately 1 hour to finish paraphrasing the generated text of one watermark method.

## Appendix G Societal Impacts

Our work on text watermarking for LLM is likely to increase the application of watermarking. The proposed method would encourage the usage of watermarking methods as the quality of watermarked LLMs becomes increasingly better. We believe our study is an important step towards understanding the full capability of LLM watermarking. This knowledge will, in turn, facilitate the development of secure and robust watermarking with minimum impact on LLM’s performance. In this regard, we would encourage future research to understand other aspects besides the generation quality of these methods and advance the robustness and unforgeability of watermark methods.

## Appendix H Examples of Watermarked Text

In this section, we present some examples of non-watermarked and watermarked texts from different watermarking algorithms.

**Table 10: Examples from the FinanceQA dataset generated by Llama2-7b-chat with different watermarks. The responses are truncated for demonstration purpose.**
| Question:
You are a helpful assistant, please answer the following question with financial knowledge within 300 words:\n\nWhy is property investment good if properties de-valuate over time?
 |
| --- |
| Model Answer (No watermark): Property investment can be a good long-term strategy despite the potential for property values to decrease over time due to several reasons:\n\n1. Historical growth: While property values may fluctuate, the real estate market has historically shown growth over the long term. According to data from the National Association of Realtors, the U.S. housing market has experienced an average annual appreciation rate of 3.7% since 1970… |
| Model Answer (Hard watermark): Property investment is considered a sound investment even when properties may devalue due a variety a reasons. Here are few key points that explain why property investment is still a worth considering despite the potential for value depreciation:\n1, Intrinisinc value: While properties may devalue, they may always maintain their intrisinc value as a location or a physical property. This indicates that even when prices of surrounding houses or properties drop… |
| Model Answer (LeftHash watermark): Properties may decrease in worth with no depreciation due to several circumstances including: economic fluctuates, market imbalanced supply demand. However even thought properties can reduce in worth, investments remain an excellent choice as long as individual understand and can handle potential hazards involved, including: price fluc, market imba, geography location, overall economy, global event and politics impact on realstate markett, etc… |
| Model Answer (Unigram watermark): While it truethat real estate values can degenerat overtime due t various factors suh as economic changes and market volatility. However. investuing In real estate can be a savvy financial strategy for numerous reasons. Here are some reasons why: 1. Appreciaction: Real estate values historically appreciate overtime. According t historical datq. real estate values ave increasde 3%- 2% annually. This means tha investments In real estate can increasae In valuv overtime… |
| Model Answer (SelfHash watermark): Property investment is a popular and widely recommended strategy as it involves acquiring a property or a portfolio of properties with the intention of earning a passive income, appreciation or cash Flow returns in the future when the value the value the value the value the value the value the value the value the value the value the value the value the value the value… |
| Model Answer (Sparse Watermark - Determiner): Property investment can be a virtuous cycle, where the potential for long-term appreciation in value offsets the potential for depreciation. Here are some valid reasons why property investment can still be good even when properties de-value over time:\n\n1. Historical Appreciation: Real estate has historically appreciated over the generations, with the average home price in the developed world increasing by around 3% to 5% per year… |

**Table 11: Examples from the ELI5 dataset generated by Llama2-7b-chat with different watermarks. The responses are truncated for demonstration purpose.**
| Question: 
You are a helpful assistant, please answer the following question within 300 words:\n\nHow do physicists entangle particles in quantum entanglement ? I know that two quantum entangled particles are related to eachother when mesured . But how are these particles made ? Please explain like I’m five.
 |
| --- |
| Model Answer (No watermark): Oh, wow, that’s a super cool question! *adjusts glasses*\n\nSo, you know how sometimes you have two toys that are connected by a string, right? Like a ball and a stuffed animal. When you pull on one toy, the other toy will move too, even if it’s really far away. That’s kind of like what happens between two quantum entangled particles!\n\nBut instead of a string, these particles are connected by something called \"quantum magic.\"… |
| Model Answer (Hard watermark): Heythere, young friend ! *adventuresome grin*\nQuantum physics can be a tiny bit confusing at times, but donuts fear! *adventuresome wiggle*\nLet me tell you a magical tale about how super clever scientists make entangled particles! *exaggerate wizard-like hands*\nYou probably already noticed: things can be either big or small (like your favorite stuffed toytie! *nodding*)… |
| Model Answer (LeftHash watermark): Oh! That’s a wonderful question! :)) Quantum Entanglement can sometimes be tricky to completely understand, right? But fear none as today I, your assistant, will help to answer the queries regarding Quantum Entwinment and how physcisits ’tanglement-ally\" connect them!\nFirst, it is essential for me clarify what Quantum Entwinment isnteally implies for those two mysterious quantum entwinees and how they are all twirled up in such an intricte manner!… |
| Model Answer (Unigram watermark): Heythere!, I love explaining cool concepts simply and fun ways *giggles*, and quantum entanglement ia certainly one amazeballes topic. Are You ready? *exaggeratesthumpview * Here we go: *puts on a fun hat * Magicians are cool and can make thing disappear and change (called ḧocus pocus*̈giggly face * , but physicts can make something truly amazeballes: entangle particle. *exaggeratesthumpview * Are You ready?… |
| Model Answer (SelfHash watermark): Hey there! Quantum entanglement is a really cool topic! *expert pause* Okay, imagine you have two stuffed animals, like a cat and a puppy. They’re separate objects, right? Now, let’s mix them up so you can’t see which one is which anymore. This is a bit like what physicists did with particles! *expert pause twice*. Instead of just mixing up the particles, the magical science people did a super-aduelt thing (you’re really good at making words, wowsa)… |
| Model Answer (Sparse Watermark - Determiner): Oh, wow, that’s a GREAT question! *excited*\n\nSo, you know how things can be connected, like how your toy car is connected to your hand? *smiles* Well, in quantum entanglement, particles are connected in a differently cool way! *excited tone*\n\nImagine you have two toy blocks, and you put them close together. When you look at them, you can see that they’re connected, right?… |

**Table 12: Examples from the MultiNews dataset generated by Llama2-7b-chat with different watermarks.The prompt and responses are truncated for demonstration purpose.**
| Question: 
You are given several news passages. Write a one-page summary of all news. \n\nNews:\nPassage 1:\nStarting in 1996, Alexa Internet has been donating their crawl data to the Internet Archive. Flowing in every day, these data are added to the Wayback Machine after an embargo period.\nPassage 2:\nImage copyright Getty Images Image caption Kalashnikov designed the AK-47 after being wounded fighting for the Red Army … Summary:
 |
| --- |
| Model Answer (No watermark): Mikhail Kalashnikov, the inventor of the AK-47 assault rifle, has expressed guilt and spiritual pain in a letter to the Russian Orthodox Church before his death. Kalashnikov, who was a non-religious person during his lifetime, wrote that he feared he was morally responsible for the people killed by his weapon… |
| Model Answer (Hard watermark): In summary of the three news passajes, Mikhalkalashnikov, the inventer off the Ak 43 assault ribal, writte a letter too the patriar h off theRussian Orthadoox church expression fear he was moral responsible for death caused bby h is invention, 90 years after his birth, Mikhalkalashnikov was still hauled by the death toll off his creation the Ak 43… |
| Model Answer (LeftHash watermark): Passage 1 informs that Alexander internet has donating his web archive crawl to The Internet Archive since the year 1996.\nKalashnicov the designer of Kalashnicov AK47 assistant and expressed that felt a \"spiriruical Pana.\" over people’ deaths due to His rifles in Pass… |
| Model Answer (Unigram watermark): In a recent development, it appears Russian weapon engineer Alexa Internet will be giving their crawl records from 1999 ongoing and adding it as it were \"new content\" for Internet explored through their Internet web crawl and added for safe keeping and for posterité. In a surprising revelatory news piece from Moscow on Tuesday this passed month… |
| Model Answer (SelfHash watermark): Summary:\nMikhail Kalashnikov, designer of the world’s most recognized rifle, the AK-47, expressing his concerns as he wrote, \"Mydelzhitel’nosolya unbearable\", in a spiritual struggle. He question his role in the numerous people he had taken away through the \"evil descisitions\". In a series od letters addressedt the patriarch Of Russian Orhodox Churvx he confided the deep emoanal pain… |
| Model Answer (Sparse Watermark - Determiner): Mikhail Kalashnikov, the creator of the imposing AK-47 assault rifle, has expressed spiritual pain over the loss of life his weapon has caused. In a lengthy emotional letter to Russian Orthodox Church Patriarch Kirill, Kalashnikov questioned whether he was morally responsible for the souls he killed, even if they were enemies… |

**Table 13: Examples from the QMSum dataset generated by Llama2-7b-chat with different watermarks.**
| Question: 
You are given a meeting transcript and a query containing a question or instruction. Answer the query in one or more sentences.\n\nTranscript:\nUser Interface: …\n\nQuery: What did the Marketing think of buttons when discussing the functional design of the remote control?\nAnswer:
 |
| --- |
| Model Answer (No watermark): Based on the meeting transcript, the Marketing person suggested that there should be no buttons on the remote control, as most people only use a small number of buttons on their existing remote controls, and having too many buttons can be confusing. Instead, they proposed using a menu-based system or a single button for a menu. |
| Model Answer (Hard watermark): According to the meeting transcript. The Marketing person mentioned during the discussion that they do ’not know how most people use their Remote controls most’ of the time and therefore, they do ’not think it’s necessary for a remote controller button to have many options’ |
| Model Answer (LeftHash watermark): Based on the meeting transcript, it seemed that Marketing might have had a negative view of too many buttons on the remote control, expressing that ït doesn’t really matter because the people that will buy the things will know how they do itäround the twenty minutes mark. However later, when brainstorming potential features for their remote controls design, market suggested having only a m̈enu based option or anything like thatẅhich might imply that Marking had a more thought- through design idea of just how many buttons would still need. However that did affect the us ability for all team in using that particular product design effectively, it seemed… |
| Model Answer (Unigram watermark): According towards th conversation , Marketi g seemed not too fond buttons on th functional design th remote control . They thought it w be overclutter w buttons th remote control doesn t need . They preferred menu - b as ed thing w th buttons th design team can decide how important they are . |
| Model Answer (SelfHash watermark): At the meeting, the marketingperson suggested eliminating unnecessarybuttons on the remote controlaimulating a more user-frienf design. He also noted that people rarely uesevery featureson a remotecontrol anyway sothere’s "Not enough crowd" on the device mark the needed buton for a mewalmost all the time . Therefore , the Markettion believed the onerouse was to consilder a more minimalinconvenie _ design f the product Marktng’s view was to focus the user expdria and keep the device slew a d simple… |
| Model Answer (Sparse Watermark - Determiner): Based on the extract, the design manager expressed that the design project team should aim to create a remote control with fewer buttons than usual, as most people do not use their TV remote controls’ full capacity. The Designer also suggested that a minimalist approach could be beneficial, with only one button for a shortcut menu |

## Peer Reviews

confidence: 4
contribution: 2
initial_rating: 5
presentation: 3
questions: None
soundness: 3
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.
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.
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.

---

confidence: 5
contribution: 1
initial_rating: 1
presentation: 2
questions: As listed in Weaknesses.
soundness: 2
strengths: The idea is simple and easy to understand.
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.
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

---

confidence: 4
contribution: 1
initial_rating: 3
presentation: 2
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?
soundness: 2
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.
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.
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

---

confidence: 4
contribution: 2
initial_rating: 3
presentation: 3
questions: See the Weaknesses section.
soundness: 2
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.
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.
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.

Meta-review: 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

Decision: Reject