# A Semantic Invariant Robust Watermark
for Large Language Models

Aiwei Liu, Leyi Pan, Xuming Hu, Shiao Meng, Lijie Wen
Tsinghua University
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Watermark algorithms for large language models (LLMs) have achieved extremely
high accuracy in detecting text generated by LLMs. Such algorithms typically
involve adding extra watermark logits to the LLM’s logits at each generation
step. However, prior algorithms face a trade-off between attack robustness and
security robustness. This is because the watermark logits for a token are
determined by a certain number of preceding tokens; a small number leads to
low security robustness, while a large number results in insufficient attack
robustness. In this work, we propose a semantic invariant watermarking method
for LLMs that provides both attack robustness and security robustness. The
watermark logits in our work are determined by the semantics of all preceding
tokens. Specifically, we utilize another embedding LLM to generate semantic
embeddings for all preceding tokens, and then these semantic embeddings are
transformed into the watermark logits through our trained watermark model.
Subsequent analyses and experiments demonstrated the attack robustness of our
method in semantically invariant settings: synonym substitution and text
paraphrasing settings. Finally, we also show that our watermark possesses
adequate security robustness. Our code and data are available at
https://github.com/THU-BPM/Robust_Watermark.

##  1 Introduction

As the quality of text generated by large language models (LLMs) continues to
improve, it addresses a multitude of practical challenges on one hand, while
simultaneously giving rise to a spectrum of new issues on the other.
Specifically, the proliferation of LLM-generated text on the Internet may lead
to an influx of rumor-based content and text copyright concerns (Rillig et
al., 2023). Therefore, the detection and labeling of machine-generated text
have become extremely important.

Text watermarking techniques for LLMs usually embed specific information
during text generation to allow high-accuracy detection of LLM-generated text.
The mainstream approach for embedding such information is to add extra
watermark logits on top of the logits generated by the LLM. For example,
Kirchenbauer et al. (2023) divide the vocabulary into red and green lists and
increase the scores for the green tokens as the watermark logits. However,
current watermarking algorithms cannot possess both attack robustness
(robustness to modifications of the watermarked text) and security robustness
(robustness against watermark cracking). For example, Zhao et al. (2023)
demonstrates that global fixed watermark logits enhance attack robustness, yet
they compromise security due to vulnerability in word frequency analysis
(Sadasivan et al., 2023). Essentially, in current watermark algorithms
Kirchenbauer et al. (2023); Zhao et al. (2023); Wang et al. (2023), the
watermark logits for each token depend on its preceding tokens. As the number
of required preceding tokens increases, watermarking complexity rises, leading
to reduced attack robustness but increased security robustness.

To resolve the aforementioned trade-off, we propose a semantic invariant
watermarking algorithm that achieves reasonable attack and security
robustness. The core motivation is generating watermark logits for each token
based on the preceding tokens’ semantics rather than their token IDs. Thus,
semantically invariant text modifications do not alter the watermark logits,
while the diversity of text semantics increases watermark complexity and
guarantees security against watermark cracking. Specifically, to extract
semantically invariant features, we use an auxiliary LLM encoder (e.g., BERT)
to extract semantic embeddings of the preceding tokens. We then train a small
watermark network to transform these embeddings into corresponding watermark
logits. The training objective of the watermark network is to ensure a high
correlation between the similarities of the output watermark logits and input
text embeddings. Also, it’s imperative that the watermark logits exhibit
sufficient diversity and are unbiased for each token. To achieve these goals,
two training objectives are adopted: a similarity loss and a normalization
loss. For the similarity loss, to ensure the diversity of the watermark
logits, we first rescale the similarity values between text embeddings to
range from -1 to 1, and then make the similarity of the generated watermark
logits fit this similarity. To ensure unbiased token selection and achieve
bimodal scores of the watermark logits, our normalization loss centers the
mean of each row and column within a batch of watermark logits to zero, while
making the absolute value of each entry as close as possible. We detect
watermarks by averaging the watermark logits across all tokens. If the average
is significantly above zero, a watermark is present.

Figure 1:  An illustration of our semantic invariant robust watermarking
method. Text is input into a generative LLM for token logits and an embedding
LLM for text embedding. The embedding is converted into watermark logits via
the Watermark Model. LLM logits and watermark logits are then combined for
final logits, which decode the next token using any method.

In the experiment, we evaluate the attack robustness of our watermarking
algorithm against various semantically invariant perturbations, including text
paraphrasing and synonym replacement. Overall, our watermark robustness is
comparable to KGW-1 (global watermark logits), which is close to the
robustness upper bound achievable by watermark logit-based methods.
Additionally, employing the spoofing attack paradigm used in Sadasivan et al.
(2023), we evaluate the decryption accuracy of various watermarking
methodologies to gauge security robustness. Our algorithm demonstrates
favorable security robustness metrics, effectively resolving the previously
encountered trade-off between attack and security robustness. Importantly, the
watermark logits could be generated in parallel with the LLM logits, resulting
in only a marginal latency increase during text generation.

In summary, the contributions of this work are as follows:

  * •

We propose the first semantically invariant robust watermarking algorithm,
which effectively detects watermarks under various semantically invariant
perturbations.

  * •

Our algorithm successfully navigates the trade-off between attack robustness
and security robustness that plagued previous methods, achieving high
performance in both dimensions.

  * •

We innovatively propose a watermark model that adeptly transforms semantic
embeddings into watermark logits.

##  2 Related work

Text watermarking technology embeds imperceptible patterns within textual
content and employs specialized detection techniques to ascertain the presence
of a watermark (Abdelnabi & Fritz, 2021; Yang et al., 2022). Currently, there
are two approaches to watermarking text: post-processing after text
generation, and incorporating watermarks during the text generation of LLM.

Post-processing methods make minor semantic-preserving alterations to the
text, most commonly lexical substitution-based approaches. For instance, Qiang
et al. (2023) embedded watermark information by employing a paraphraser-based
lexical substitution, ensuring the text’s original semantics remained intact.
Yoo et al. (2023) began by selecting stable words to position the watermark
and then used a masked language model to generate candidate words, thereby
facilitating the embedding and extraction of watermarks. Munyer & Zhong (2023)
generated candidate texts through word2vec-based synonym replacements,
subsequently comparing semantic similarities among candidates to finalize the
watermarked text. Nonetheless, replacing individual words while only
considering the unchanged meaning of those words risks degrading overall text
quality. In contrast, generative modification methods like Abdelnabi & Fritz
(2021) directly generate watermarked text, along with corresponding networks
to recover the watermark information. However these methods can still only
make minimal changes to the original text, severely limiting the freedom to
insert watermarks.

Compared to post-processing methods, integrating watermarks into the text
generation process of current generative language models better utilizes their
capabilities. Based on the stage at which watermark information is embedded,
current watermarking methods for LLMs can be divided into two categories:
adding watermarks during token sampling and during logits computation. Christ
et al. (2023) proposed a method that embeds watermark information by
presetting a random number sequence for token sampling, and detects watermarks
by computing correlation between texts and the random number sequence. To
improve robustness against text modifications, Kuditipudi et al. (2023)
adopted Levenshtein distance for matching texts and the random number
sequence, allowing watermarked texts to be detectable even after certain
modifications. However, although such token sampling-based watermarking
methods minimize the impact on text quality, they also greatly limit the
randomness of generated texts, and only work for sampling decoders instead of
other decoding methods like beam search. In contrast, another category is to
add watermarks during logits computation. Kirchenbauer et al. (2023) made
minor modifications to current token logits based on hashes of previous k
tokens (watermark logits). Lee et al. (2023) designed a similar watermarking
method for low-entropy code generation. Wang et al. (2023) enabled multi-bit
watermark information via a proxy LLM. Liu et al. (2023) implemented private
watermarking through parameter sharing between the watermark generator and
detector. In this work, we are more concerned with watermark robustness. Zhao
et al. (2023) proved that using global fixed watermark logits (k=0) in
Kirchenbauer et al. (2023)’s method achieves very strong attack robustness,
yet Sadasivan et al. (2023)’s work shows that lower k values make watermarks
vulnerable to security robustness (easy to break). Therefore, previous
watermarking methods struggle to achieve both attack and security robustness.
We propose a semantically invariant robust watermarking scheme to achieve
decent attack and security robustness.

##  3 Preliminaries

We first introduce the necessary concepts used in this work. Language models
could be divided into generative language models and embedding language
models. A generative language model M takes a prompt $x^{prompt}$ and already
generated text ${\bm{t}}_{:l-1}$ as input and generates the logits for the
next token: $P_{M}(x^{prompt},{\bm{t}}_{:l-1})$. Meanwhile, an embedding
language model $\mathrm{E}$ could generate an embedding $\mathrm{E}({\bm{t}})$
for the text ${\bm{t}}$. Usually, semantically similar texts will generate
similar embeddings. For convenience in later sections, we use the language
model to refer to generative language models.

A watermarking algorithm for large models embeds specific information in the
generated text. The paradigm adopted in this paper is adding small watermark
logits to the already generated next token logits. Specifically, the watermark
logits can be defined as $P_{\mathrm{W}}({\bm{x}}^{prompt},\bm{t}_{:l-1})$,
and the final logits could be defined as
$P_{\hat{\mathrm{M}}}({\bm{x}}^{prompt},\bm{t}_{:l-1})=P_{\mathrm{M}}({\bm{x}}^{prompt},\bm{t}_{:l-1})+P_{\mathrm{W}}({\bm{x}}^{prompt},\bm{t}_{:l-1})$,
where $\hat{\mathrm{M}}$ is the watermarked LLM. The watermark detector
$P_{\mathrm{D}}$ corresponds to $P_{\mathrm{W}}$, outputting 1 if text
${\bm{t}}$ contains the watermark, otherwise 0. for consistency, we explicitly
define $P_{\mathrm{W}}^{(i)}$ to denote the value at the i-th position of the
watermark logits, and use $P_{\mathrm{W}_{i}}$ to denote a specific example of
watermark logits.

The robustness of our work encompasses two aspects: attack robustness and
security robustness. Attack robustness evaluates the probability that the
watermarked text can still be correctly identified after semantically
invariant modifications. Security robustness evaluates the accuracy of
inferring the watermark rules from the watermarked text. Once the watermarking
rules are disclosed, users can easily modify the text to remove the watermark,
rendering attack robustness meaningless.

##  4 Proposed Method

In this section, we provide a detailed introduction to the proposed
semantically invariant robust watermark algorithm named SIR. First, in Section
4.1, we introduce the overall process of watermark generation. Then, in
Section 4.2, we explain the training process of the watermark model. Finally,
in Section 4.3, we present the watermark detection process.

###  4.1 Watermark Generation

As discussed in the previous sections, one of the most important steps in the
watermark generation process is the generation of the watermark logits. The
watermark logits for the current token are usually determined by its preceding
tokens. Our goal is to construct a continuous and robust mapping from the
semantics of the preceding tokens to the watermark logits. In this way,
semantic-preserving modifications to the text will only cause small
perturbations to the watermark logits, thus ensuring the attack robustness of
the entire watermark algorithm.

To extract semantic-invariant features of the text, we utilize an embedding
language model $\mathrm{E}$ (e.g. BERT). Specifically, given a sequence of
preceding tokens ${\bm{t}}_{:l-1}$, we first obtain its semantic embedding
${\bm{e}}_{l}=\mathrm{E}({\bm{t}}_{:l-1})$. To transform this semantic-
invariant feature to a score over the vocabulary $\mathrm{V}$, we train a
specialized watermark model $\mathrm{T}$ to generate the watermark logits:
$P_{\mathrm{W}}=\mathrm{T}({\bm{e}}_{l})$. The overall algorithm is described
in detail in Algorithm 1. A thorough introduction to the watermark model will
be provided in Section 4.2. We will also provide a detailed analysis of the
algorithm’s robustness in Section 5.

Algorithm 1 Watermark Generation

1: Input: watermark strength $\delta$, a language model $\mathrm{M}$, previous
generated text ${\bm{t}}=[t_{0}....t_{l-1}]$, a text embedding language model
$\mathrm{E}$, a trained watermark model $\mathrm{T}$.

2: Generate the next token logits from $P_{\mathrm{M}}$:
$P_{\mathrm{M}}({\bm{x}}^{prompt},\bm{t}_{:l-1})$.

3: Generate sentence embedding ${\bm{e}}_{l}=\mathrm{E}(\bm{t}_{:l-1})$.

4: Generate watermark logit $P_{\mathrm{W}}$ from trained watermark model
$\mathrm{T}({\bm{e}}_{l})$.

5: Define a new language model $\hat{\mathrm{M}}$ where given input
$\bm{t}=[t_{0}....t_{l-1}]$, the resulting logits satisfy
$P_{\hat{\mathrm{M}}}({\bm{x}}^{prompt},\bm{t}_{:l-1})=P_{\mathrm{M}}({\bm{x}}^{prompt},\bm{t}_{:l-1})+\delta\times
P_{\mathrm{W}}({\bm{x}}^{prompt},\bm{t}_{:l-1}).$

6: Output: watermarked next token logits $P_{\hat{\mathrm{M}}}(t_{l})$.

###  4.2 Watermark Model

In this section, we introduce the watermark model in detail. The goal of the
watermark model is to convert semantic embeddings into watermark logits.
First, we describe several desired properties for the similarity of watermark
logits: semantic-consistent broad range, unbiased token preference, and
balanced score.

To ensure the attack robustness, the similarity of the watermark logits should
have a semantic-consistent broad range. That is, the similarity between
generated watermark logits should be highly correlated with the similarity
between text embeddings. Also, to ensure diversity and security, the similarty
should have a broad range between 1 and -1 (language models typically generate
embeddings with similarities concentrated between 0 and 1), as shown in the
following equation:

$\forall x,y\in[-1,1],x<y,\exists i,j:\frac{P_{\mathrm{W}_{i}}\cdot
P_{\mathrm{W}_{j}}}{||P_{\mathrm{W}_{i}}||_{2}\times||P_{\mathrm{W}_{j}}||_{2}}\in[x,y].$
(1)

Additionally, to further ensure the security robustness of the watermark, the
watermark logits should have an unbiased token preference, meaning there
should be no statistical preference for any token. This is shown in the
following equation:

$\forall
i\in\\{1,2,\ldots,|\mathrm{V}|\\},\sum_{j}P_{\mathrm{W}_{j}}^{(i)}=0.$ (2)

Moreover, to make the watermark stable and easy to detect, the watermark
logits should have a balanced score, meaning the mean of the watermark logits
is 0 and the score is uniform relative to the mean value, which is shown in
the following equation:

$\forall
j,\sum_{i=0}^{|\mathrm{V}|}\mathrm{sign}(P_{\mathrm{W}_{j}}^{(i)})=0,$ (3)

where $\mathrm{sign}(x)=1$ if $x$ is greater than 0, and -1 if $x$ is less
than 0.

To achieve the above design goals, we devised a non-linear neural network
(watermark model) to generate the watermark logits. This neural network
consists of several fully connected layers with Rectified Linear Unit (ReLU)
activations introduced to induce non-linearity. The watermark model employs
two losses to meet the stated objectives: a similarity loss and a
normalization loss.

The objective of the similarity loss is to attain a semantically consistent
broad-range similarity for the watermark logits. Specifically, in order to
achieve a broad range, the similarity of the text embeddings first needs to be
normalized to $[-1,1]$ by calculating the mean of the similarity and then
expanding the range using the $\mathrm{tanh}$ function. Finally, the overall
goal of the similarity loss is to fit the similarity between the watermark
logits to the transformed text embedding similarities. The standard definition
of the similarity loss $\mathcal{L}_{s}$ is as follows:

$\sum_{i}\sum_{j}|\frac{\mathrm{T}({\bm{e}}_{i})\cdot\mathrm{T}({\bm{e}}_{j})}{||\mathrm{T}({\bm{e}}_{i})||_{2}\times||\mathrm{T}({\bm{e}}_{j})||_{2}}-\mathrm{tanh}(k_{1}(\frac{{\bm{e}}_{i}\cdot{\bm{e}}_{j}}{||{\bm{e}}_{i}||_{2}\times||{\bm{e}}_{j}||_{2}}-\sum_{k}\sum_{l}\frac{{\bm{e}}_{k}\cdot{\bm{e}}_{l}}{|N|^{2}||{\bm{e}}_{k}||_{2}\times||{\bm{e}}_{l}||_{2}}))|,$
(4)

where $|N|$ is the size of the sentence embedding space, $\mathrm{T}$ is the
watermark model, and $k_{1}$ is a hyperparameter used to adjust the range of
similarity.

We then introduce the normalization loss, whose goal is to have the watermark
logits exhibit an unbiased token preference while maintaining a balanced
score. Specifically, this requires the mean of each watermark logit to be
zero, and the mean over all tokens in the watermark logits to also be zero.
Finally, to make the score of the watermark logits uniform, we constrain the
absolute value of each value to be close, with the standard definition of the
normalization loss as follows:

$\mathcal{L}_{n}=\sum_{i}|\sum_{j}\mathrm{T}({\bm{e}}_{i})^{(j)}|+\sum_{i}|\sum_{j}\mathrm{T}({\bm{e}}_{j})^{(i)}|+\lambda_{1}\sum_{i}\sum_{j}|R-\mathrm{T}({\bm{e}}_{j})^{(i)}|,$
(5)

Where R is a hyperparameter denoting the target absolute value for each value
in the watermark logits, and $\lambda_{1}$ is a weight conditioning the
normalization loss internally.

The final training loss is a weighted sum of the similarity loss and
normalization loss, expressed as follows, where $\lambda_{2}$ is a
hyperparameter balancing the two losses:

$\mathcal{L}=\mathcal{L}_{s}+\lambda_{2}\mathcal{L}_{n}.$ (6)

To augment the separability of watermark logits, the output from the watermark
model is further processed by the $\mathrm{tanh}$ function, yielding the final
watermark logits, denoted as: $\mathrm{tanh}(k_{2}\,T(\mathbf{e}_{i}))$.

###  4.3 Watermark Detection

In this section, we introduce the method for detecting the watermark.

Analogous to watermark generation, the watermark logit is first computed per
token via Algorithm 1. The score at the position of each token $t_{j}$ is
selected. Averaging all scores gives the detection score:

$z=\frac{\sum_{j=1}^{N}P_{\mathrm{W}}^{(j)}({\bm{x}}^{prompt},\bm{t}_{:j-1})}{N}.$
(7)

Without a watermark, the expected score is 0 since the watermark logit mean is
0. When a watermark is present, the score substantially exceeds 0, making this
a suitable validation approach. We utilize the z-score in the following to
indicate our detection score.

##  5 Robustness Analysis

This section analyzes the attack robustness of the watermark algorithm. As
detection relies on the z-score, robustness can be assessed by the z-score
change with modifications to the generated text ${\bm{t}}_{:N}$. The z-score
change magnitude indicates robustness. We use ${\bm{t}}^{\prime}_{:N}$ to
denote the modified text.

Let $U$ represent the set of altered tokens Their new scores are considered
zero. For unmodified tokens, score changes result from embedding alterations
of the proceeding tokens:

$|\Delta z|\leq\frac{\sum_{j\in
U}|P_{\mathrm{W}}({\bm{x}}^{prompt},\bm{t}_{:j-1})|+\sum_{j\notin
U}|P_{\mathrm{W}}({\bm{x}}^{prompt},\bm{t}_{:j-1})-P_{\mathrm{W}}({\bm{x}}^{prompt},\bm{t}^{\prime}_{:j-1})|}{N}.$
(8)

Since watermark logit generation from text embeddings is continuous, the
Lipschitz constant L can bound the inequality per properties of continuous
functions:

$|\Delta z|\leq\frac{\sum_{j\in
U}|P_{\mathrm{W}}({\bm{x}}^{prompt},\bm{t}_{:j-1})|+\sum_{j\notin
U}L|\mathrm{E}(\bm{t}_{:j-1})-\mathrm{E}(\bm{t}^{\prime}_{:j-1})|}{N}.$ (9)

This shows the watermark is theoretically robust as long as text modifications
do not drastically alter semantics, such that embeddings stay similar. In
fact: significant semantic changes would make the watermark meaningless.
Moreover, an analysis of security robustness is provided in the appendix.

##  6 Experiment

###  6.1 Experiment settings

Dataset and Prompt: Similar to the previous works Kirchenbauer et al. (2023),
we utilize the C4 dataset (Raffel et al., 2020) for data generation, taking
the first 30 tokens as prompts and generating the next 200 tokens. The
original C4 texts serve as human-written examples. The test objective is to
distinguish between generated text and human-written text. During training of
the watermark model, we utilize the WikiText-103 dataset (Merity et al., 2016)
(different from C4) to generate embeddings.

Baseline and Language Model: We selected two watermarking algorithms as
baselines. One is KGW-k (Kirchenbauer et al., 2023) where k is the number of
preceding tokens to hash. The other is exponential minimum sampling (EXP-edit)
(Kuditipudi et al., 2023), an approach that introduces watermarks through a
pre-selected sequence of sampling probabilities during the sampling process
and adopts edit distance-based detection to achieve strong robustness. For
language models, we use LLaMA-7B (Touvron et al., 2023), OPT1.3B, and OPT2.7B
(Zhang et al., 2022) for text generation. Additionally, we tested the efficacy
of the watermarking algorithm under both stochastic and deterministic
scenarios using sampling and beam search decoding algorithms, respectively.
For embedding language models, we utilized Compositional-BERT (Chanchani &
Huang, 2023) due to its superior ability to produce embeddings that better
distinguish text.

Evaluation: Similar to Zhao et al. (2023)’s method, to avoid the impact of
detection thresholds, we set false positive rates at 1% and 10% and adjusted
the detector’s thresholds accordingly. For comparison, we also report F1
scores at optimal thresholds. Further, we use the superior LLaMA-13B model for
perplexity evaluation. For safety robustness assessment, we adopt Sadasivan et
al. (2023)’s approach of analyzing occurrence frequencies of 181 common words.
See Section 6.3 for details.

Hyper-parameters: The watermark model uses a four-layer fully connected
residual network with rectified linear unit activations. Hyperparameters are
set to $k_{1}=20$, $k_{2}=1000$, $\lambda_{1}=10$, $\lambda_{2}=0.1$, and the
Adam optimizer (lr=1e-5) is used for training. The detailed network
architecture is provided in the appendix. All experiments were conducted using
the NVIDIA Tesla V100 32G GPU.

###  6.2 Attack Robustness Analysis

In Table 1, we list the detection accuracy of our watermark algorithm and
various baseline algorithms under the no-attack setting and when texts are
rewritten using GPT3.5 as well as two different DIPPER settings (Krishna et
al., 2023). For GPT3.5, we use the gpt-3.5-turbo-0613 version with the prompt
Rewrite the following paragraph:. For DIPPER-1 the lex diversity is 60 without
order diversity, and for DIPPER-2 we additionally increase the order diversity
by 20. EXP-Edit cannot be used under beam search so we do not list its result.

Table 1 shows that our watermarking algorithm achieves strong robustness
against all rewrite attacks. Specifically, for watermarked texts rewritten by
GPT-3.5 and two DIPPER rewriters, our algorithm still achieves an average
detection F1 score of 0.93. This performance is comparable to that of the
KGW-1 algorithm, markedly surpassing other watermark algorithms, including
KGW-2, KGW-4, and EXP-Edit. As modifications to the token in the KGW-1
algorithm only affect the label of that particular token, this represents the
upper bound of attack robustness for watermark algorithms based on watermark
logits. Nonetheless, subsequent experiments demonstrate that the KGW-1
algorithm possesses poor security robustness.

To further demonstrate the robustness of our watermarking method against
semantic-preserving text attacks, Figure 2(a) compares the detection F1 score
of our watermark algorithm and other baseline methods under different
synonymous word substitution scenarios. The synonyms are obtained from the
WordNet synset (Miller, 1995). Since replacing words solely could still alter
the semantics as many synonyms are only applicable in certain contexts, we
additionally employ BERT (Devlin et al., 2018) to constrain the synonym
substitution to induce minimal embedding changes as a context replacement
approach. Without context replacement, our algorithm demonstrates robustness
comparable to KGW-2, while under semantics-preserving substitutions, our
method achieves near state-of-the-art robustness against attacks, similar to
KGW-1 and EXP-Edit. These results clearly demonstrate the robustness of our
method for semantically invariant text modification.

###  6.3 Security Robustness Analysis

Table 1:  We compared the performance of our watermarking method with others,
including KGW-k (Kirchenbauer et al., 2023) and EXP (Kuditipudi et al., 2023),
using text generated by LLaMA-7B. Tests involved watermark detection accuracy
under no attack, GPT3.5 rewrite attacks, and two DIPPER (Krishna et al., 2023)
settings.

|  | Sampling | Beam search
---|---|---|---
Setting | Method | 1% FPR | 10% FPR | Best | 1% FPR | 10% FPR | Best
|  | TPR | F1 | TPR | F1 | F1 | TPR | F1 | TPR | F1 | F1
No attack | KGW-1 | 0.960 | 0.975 | 1.000 | 0.952 | 0.983 | 1.000 | 0.995 | 1.000 | 0.952 | 0.998
KGW-2 | 1.000 | 0.995 | 1.000 | 0.952 | 0.998 | 1.000 | 0.995 | 1.000 | 0.952 | 1.000
KGW-4 | 1.000 | 0.995 | 1.000 | 0.952 | 0.998 | 1.000 | 0.995 | 1.000 | 0.952 | 1.000
EXP-Edit | 0.995 | 0.993 | 1.000 | 0.952 | 0.995 | $\times$ | $\times$ | $\times$ | $\times$ | $\times$
SIR(ours) | 1.000 | 0.995 | 1.000 | 0.952 | 0.995 | 1.000 | 0.995 | 1.000 | 0.952 | 1.000
GPT3.5 | KGW-1 | 0.590 | 0.738 | 0.885 | 0.891 | 0.905 | 0.890 | 0.937 | 0.965 | 0.935 | 0.955
KGW-2 | 0.535 | 0.693 | 0.760 | 0.817 | 0.823 | 0.655 | 0.787 | 0.795 | 0.839 | 0.865
KGW-4 | 0.225 | 0.364 | 0.490 | 0.614 | 0.705 | 0.420 | 0.587 | 0.660 | 0.750 | 0.795
EXP-Edit | 0.435 | 0.602 | 0.645 | 0.739 | 0.775 | $\times$ | $\times$ | $\times$ | $\times$ | $\times$
SIR(ours) | 0.740 | 0.856 | 0.865 | 0.880 | 0.900 | 0.805 | 0.887 | 0.945 | 0.924 | 0.938
DIPPER-1 | KGW-1 | 0.715 | 0.829 | 0.940 | 0.922 | 0.930 | 0.930 | 0.959 | 0.975 | 0.939 | 0.962
KGW-2 | 0.450 | 0.616 | 0.710 | 0.785 | 0.815 | 0.770 | 0.865 | 0.880 | 0.888 | 0.908
KGW-4 | 0.220 | 0.358 | 0.545 | 0.627 | 0.728 | 0.380 | 0.547 | 0.765 | 0.820 | 0.843
EXP-Edit | 0.630 | 0.768 | 0.740 | 0.804 | 0.830 | $\times$ | $\times$ | $\times$ | $\times$ | $\times$
SIR(ours) | 0.765 | 0.862 | 0.905 | 0.903 | 0.920 | 0.890 | 0.937 | 0.950 | 0.927 | 0.948
DIPPER-2 | KGW-1 | 0.765 | 0.862 | 0.935 | 0.918 | 0.925 | 0.910 | 0.948 | 0.975 | 0.940 | 0.960
KGW-2 | 0.470 | 0.635 | 0.685 | 0.768 | 0.803 | 0.725 | 0.838 | 0.860 | 0.878 | 0.898
KGW-4 | 0.150 | 0.259 | 0.475 | 0.603 | 0.718 | 0.315 | 0.475 | 0.645 | 0.739 | 0.783
EXP-Edit | 0.485 | 0.649 | 0.635 | 0.732 | 0.775 | $\times$ | $\times$ | $\times$ | $\times$ | $\times$
SIR(ours) | 0.875 | 0.928 | 0.92 | 0.911 | 0.931 | 0.870 | 0.926 | 0.940 | 0.922 | 0.940

In Figure 3(a), we analyze the security robustness of our method. Security
robustness refers to the difficulty of cracking the watermarking rules. In
this work, we adopt the spoofing attack method of Sadasivan et al. (2023),
which analyzes the word frequencies of 181 commonly occurring words. If a word
in watermarked text has a higher frequency than in natural text, it is deemed
watermarked (with positive probability in the watermark logits). The accuracy
of this identification is called watermark decryption accuracy, which measures
the security robustness of the watermark.

Specifically, for KGW-k we count the frequency of the last word given fixed
k-1 prefixes. Due to the semantic relevance of our watermarking rules, we
employed DBpedia Class dataset (Gangemi et al., 2012) to examine watermark
decryption accuracy. Specifically, we analyzed the accuracy across three
different levels: the overall class, L1 class (e.g., species), and L2 class
(e.g., species: animal). Due to insufficient data at the L3 class level, our
research focuses solely on L1 and L2 classes.

Figure 3(a) illustrates the trade-off between attack robustness (measured by
detection accuracy after rewrite) and security robustness (measured by
watermark decryption accuracy) in Kirchenbauer et al. (2023)’s watermarking
algorithm. A smaller k implies stronger attack robustness yet simpler
watermarking rules and thus lower security robustness. Our watermarking
algorithm achieves attack robustness close to KGW-1 while maintaining security
robustness close to KGW-4. Although our security robustness degrades slightly
with more refined domain text (L1 and L2 level classes), even for the very
refined L2 class it is still far superior to KGW-3. Therefore, our
watermarking algorithm successfully addresses the attack robustness versus
security robustness trade-off in prior work.

Figure 2: The left figure shows how detection accuracy changes for different
watermark models as the synonym replacement ratio increases. The middle figure
shows the correlation between embedding similarity generated by the embedding
model and the similarity of the generated watermark logits. The right figure
illustrates watermark logits with and without the normalization loss.

Figure 3: The left figure depicts the trade-off between security robustness
(measured by watermark decryption accuracy) and attack robustness (measured by
F1 score after rewrite) across different watermarking algorithms. The right
figure shows the text quality generated by language models with different
watermarking methods (measured by text perplexity). Table 2: Text generation
speed, measured in seconds (s), was compared with and without applying the
watermarking algorithm, for a generated token length of 200. All experiments
were performed on a single NVIDIA Tesla V100 32GB GPU.

Embedding Model | Setting | OPT-1.3B | OPT-2.7B | LLaMA-7B
---|---|---|---|---
Com-BERT Base | w/o watermark | 3.14 | 4.10 | 5.76
w/ watermark | 4.98 | 6.87 | 7.23
w/ watermark (parallel) | 3.32 | 4.45 | 5.81
Com-BERT Large | w/o watermark | 3.14 | 4.10 | 5.76
w/ watermark | 5.67 | 7.44 | 7.83
w/ watermark (parallel) | 3.55 | 4.89 | 5.94

###  6.4 Watermark Model Analysis

To better analyze our watermarking algorithm, Figure 2(b) shows the
relationship between the similarity of text embeddings and the similarity of
watermark logits generated by the watermark model. The average similarity of
watermark logits is shown for each range of embedding similarity. It can be
seen that the similarity of watermark logits maintains a strong correlation
with the embedding similarity, especially for very similar embeddings that
certainly correspond to very similar watermark logits (similarity greater than
0.8). Meanwhile, the range of watermark logit similarity is also extended to
-1 to 1 (the figure only shows the average similarity in the range so -1 is
not shown), which also makes the watermarking rules more diverse and robust.
From the figure, the average similarity of the original sentence embeddings is
0.45, which also reflects the advantage of using Compositional-BERT, which can
better distinguish dissimilar texts compared to the original BERT, helping to
improve the diversity of watermarks. We will analyze in more detail in the
appendix the impact of different embedding models on watermarking. Figure 2(b)
also shows our normalization loss results in less distinguished watermark
logits.

In Figure 2(c), we plot the specific watermark logits. It shows that after
using our normalization loss, the watermark logits becomes more symmetrical
without overly small logit values. After applying the tanh scaling method
introduced in Section 4.3, the watermark logits only contain values close to
-1 and 1. The potential impact of the watermark on text quality depends on the
maximum absolute token logit value (as it would only select that token if too
large), so making the absolute values of all token logits equal to the minimum
max value is an optimal solution. See more detail in the Appendix.

###  6.5 Time Complexity and Text Quality

In Table 2, we further analyzed the time complexity of our watermarking
algorithm. As shown, without parallel processing, our algorithm imposes
additional time costs on text generation, mainly due to the language model
embedding and the watermark model is just a four-layer linear network, with
negligible time costs. As language models increase in size, the proportional
time increase diminishes, with LLaMA-7B only taking 40% longer. Figure 1
illustrates that our algorithm can generate LLM logits and watermark logits in
parallel with minimal additional time cost, particularly for larger models
like LLaMA-7B.

To evaluate the impact of our watermarking method on text quality, Figure 3(b)
shows the perplexity comparison of the generated text. The perplexity
calculation uses the LLaMA-13B model, and the text on OPT2.7B and LLaMA-7B is
generated using sampling decoding. It can be seen that our method and previous
watermarking methods have a slight impact on text quality (perplexity
increases slightly). But at the same time, our method can achieve slightly
lower perplexity than the KGW series of watermarking algorithms, which may be
the result of our semantic-based watermarking algorithm being more consistent
in text expression. We will present examples in the appendix.

##  7 Conclusion

In this work, we propose a semantically invariant robust watermarking
algorithm that generates watermark logits based on the semantics of context.
We validate the robustness of our algorithm through a series of analyses and
experiments, particularly in scenarios involving text rewriting and synonym
substitution, while maintaining the watermark’s resistance to decryption. For
future improvements, we suggest utilizing superior quality embedding models,
which will enhance the performance of our watermarking algorithms.
Furthermore, there is potential for expansion of our algorithm for use in
different watermarking approaches, such as employing pre-determined
probability sequences for token sampling.

## References

  * Abdelnabi & Fritz (2021) Sahar Abdelnabi and Mario Fritz.  Adversarial watermarking transformer: Towards tracing text provenance with data hiding.  In _2021 IEEE Symposium on Security and Privacy (SP)_ , pp. 121–140. IEEE, 2021.
  * Chanchani & Huang (2023) Sachin Chanchani and Ruihong Huang.  Composition-contrastive learning for sentence embeddings.  In _Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pp. 15836–15848, 2023.
  * Christ et al. (2023) Miranda Christ, Sam Gunn, and Or Zamir.  Undetectable watermarks for language models.  _arXiv preprint arXiv:2306.09194_ , 2023.
  * Devlin et al. (2018) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  Bert: Pre-training of deep bidirectional transformers for language understanding.  _arXiv preprint arXiv:1810.04805_ , 2018.
  * Gangemi et al. (2012) Aldo Gangemi, Andrea Giovanni Nuzzolese, Valentina Presutti, Francesco Draicchio, Alberto Musetti, and Paolo Ciancarini.  Automatic typing of dbpedia entities.  In _The Semantic Web–ISWC 2012: 11th International Semantic Web Conference, Boston, MA, USA, November 11-15, 2012, Proceedings, Part I 11_ , pp. 65–81. Springer, 2012.
  * Kirchenbauer et al. (2023) John Kirchenbauer, Jonas Geiping, Yuxin Wen, Jonathan Katz, Ian Miers, and Tom Goldstein.  A watermark for large language models.  _arXiv preprint arXiv:2301.10226_ , 2023.
  * Krishna et al. (2023) Kalpesh Krishna, Yixiao Song, Marzena Karpinska, John Wieting, and Mohit Iyyer.  Paraphrasing evades detectors of ai-generated text, but retrieval is an effective defense.  _arXiv preprint arXiv:2303.13408_ , 2023.
  * Kuditipudi et al. (2023) Rohith Kuditipudi, John Thickstun, Tatsunori Hashimoto, and Percy Liang.  Robust distortion-free watermarks for language models.  _arXiv preprint arXiv:2307.15593_ , 2023.
  * Lee et al. (2023) Taehyun Lee, Seokhee Hong, Jaewoo Ahn, Ilgee Hong, Hwaran Lee, Sangdoo Yun, Jamin Shin, and Gunhee Kim.  Who wrote this code? watermarking for code generation.  _arXiv preprint arXiv:2305.15060_ , 2023.
  * Liu et al. (2023) Aiwei Liu, Leyi Pan, Xuming Hu, Shu’ang Li, Lijie Wen, Irwin King, and Philip S Yu.  A private watermark for large language models.  _arXiv preprint arXiv:2307.16230_ , 2023.
  * Merity et al. (2016) Stephen Merity, Caiming Xiong, James Bradbury, and Richard Socher.  Pointer sentinel mixture models.  In _International Conference on Learning Representations_ , 2016.
  * Miller (1995) George A Miller.  Wordnet: a lexical database for english.  _Communications of the ACM_ , 38(11):39–41, 1995.
  * Munyer & Zhong (2023) Travis Munyer and Xin Zhong.  Deeptextmark: Deep learning based text watermarking for detection of large language model generated text.  _arXiv preprint arXiv:2305.05773_ , 2023.
  * Qiang et al. (2023) Jipeng Qiang, Shiyu Zhu, Yun Li, Yi Zhu, Yunhao Yuan, and Xindong Wu.  Natural language watermarking via paraphraser-based lexical substitution.  _Artificial Intelligence_ , 317:103859, 2023.
  * Raffel et al. (2020) Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu.  Exploring the limits of transfer learning with a unified text-to-text transformer.  _The Journal of Machine Learning Research_ , 21(1):5485–5551, 2020.
  * Reimers & Gurevych (2020) Nils Reimers and Iryna Gurevych.  Making monolingual sentence embeddings multilingual using knowledge distillation.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing_. Association for Computational Linguistics, 11 2020.  URL https://arxiv.org/abs/2004.09813.
  * Rillig et al. (2023) Matthias C Rillig, Marlene Ågerstrand, Mohan Bi, Kenneth A Gould, and Uli Sauerland.  Risks and benefits of large language models for the environment.  _Environmental Science & Technology_, 57(9):3464–3466, 2023.
  * Sadasivan et al. (2023) Vinu Sankar Sadasivan, Aounon Kumar, Sriram Balasubramanian, Wenxiao Wang, and Soheil Feizi.  Can ai-generated text be reliably detected?  _arXiv preprint arXiv:2303.11156_ , 2023.
  * Touvron et al. (2023) Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al.  Llama: Open and efficient foundation language models.  _arXiv preprint arXiv:2302.13971_ , 2023.
  * Wang et al. (2023) Lean Wang, Wenkai Yang, Deli Chen, Hao Zhou, Yankai Lin, Fandong Meng, Jie Zhou, and Xu Sun.  Towards codable text watermarking for large language models.  _arXiv preprint arXiv:2307.15992_ , 2023.
  * Yang et al. (2022) Xi Yang, Jie Zhang, Kejiang Chen, Weiming Zhang, Zehua Ma, Feng Wang, and Nenghai Yu.  Tracing text provenance via context-aware lexical substitution.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 36, pp. 11613–11621, 2022.
  * Yoo et al. (2023) KiYoon Yoo, Wonhyuk Ahn, Jiho Jang, and Nojun Kwak.  Robust multi-bit natural language watermarking through invariant features.  In _Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pp. 2092–2115, 2023.
  * Zhang et al. (2022) Susan Zhang, Stephen Roller, Naman Goyal, Mikel Artetxe, Moya Chen, Shuohui Chen, Christopher Dewan, Mona Diab, Xian Li, Xi Victoria Lin, et al.  Opt: Open pre-trained transformer language models.  _arXiv preprint arXiv:2205.01068_ , 2022.
  * Zhao et al. (2023) Xuandong Zhao, Prabhanjan Ananth, Lei Li, and Yu-Xiang Wang.  Provable robust watermarking for ai-generated text.  _arXiv preprint arXiv:2306.17439_ , 2023.

Figure 4: This figure demonstrates the examples of our watermark method and
the KGW-1 method when using the same prompt. It contrasts the effects of
detection on the unmodified text versus text rewritten by GPT-3.5 and then
detected. All the texts are generated using the LLaMA-7B model. In our method,
tokens with a watermark logit value greater than 0 are marked in green color
(corresponding to green tokens in the KGW-1 method).

##  Appendix A Case Study

To more intuitively demonstrate the robustness of our semantic invariant
watermarking algorithm, we present a comparison between texts generated by our
algorithm and KGW-1, KGW-2, and KGW-4 given the same prompt in Figures 4 and
5. Both figures show the original texts produced by the corresponding
watermark algorithms and the texts rewritten by GPT-3.5. The green color
indicates tokens with watermark logit values greater than 0 (corresponding to
the green tokens in the KGW-k algorithms). These examples illustrate that our
algorithm maintains high z-scores even after GPT-3.5 rewriting, while the
robustness of the KGW-k algorithms decreases as k increases.

Figure 5: This figure demonstrates the examples of the KGW-2 method and the
KGW-4 method when using the same prompt. The other settings of this figure are
identical to Figure 4

##  Appendix B Watermark Logits Analysis

In this section, we analyze the influence of the shape of watermark logits on
watermarks. Specifically, we study the impact on watermark detection success
rate and text quality after four different transformations of the original
watermark logits. The four transformations are:

  * •

$\mathrm{tanh}(1000\\*{\bm{x}})$ scaling, which is the method used in this
work, after which all values will be close to 1 or -1, as shown in the top
graph of Figure 6(a).

  * •

Linear scaling: uniformly distributed between -1 and 1 according to the rank
of the data (top of Figure 6(b)):

$L({\bm{x}})=-1+2\times\frac{\mathrm{argsort}(\mathrm{argsort}(\mathbf{{\bm{x}}}\text{))}}{\mathrm{len}(\mathbf{{\bm{x}}})-1}$
(10)

  * •

$\mathrm{tanh}(10\\*L({\bm{x}}))$ scaling, applying an additional
$\mathrm{tanh}$ transform on top of the linear scaling, as shown in the bottom
graph of Figure 6(a).

  * •

$L(x)^{3}$ scaling, applying an additional cubic transform on top of the
linear scaling, as shown in the bottom of Figure 6(b).

Figure 6: Examples of the shapes of four watermark logits that we tested are
presented: (a) The top graph of Figure (a) illustrates the
$\mathrm{tanh(1000x)}$ utilized, (b) the top graph of Figure (b) displays the
data originally ranked and linearly scaled to the interval between -1 and 1,
as demonstrated by Equation 10. Subsequently, the graph below Figure (a)
depicts a $\mathrm{tanh}$ transformation applied to the top graph of Figure
(b), and the graph below Figure (b) demonstrates a cubic transformation
applied likewise to the top graph of Figure (b).

Figure 6 illustrates that the four distinct watermark logits exhibit minimal
differences in their impact on text perplexity (PPL) under various $\delta$
values, corroborating our hypothesis articulated in Section 6.4. This
hypothesis posits that the influence on text quality predominantly depends on
the token with the maximum value in the watermark logits, as the four employed
watermark logits possess the same maximum value under identical $\delta$
values. Nonetheless, these watermark logits require different $\delta$ values
to achieve optimal detection results; the need for larger $\delta$ values
increases with a higher distribution of values near zero. Correspondingly, the
watermark logits we adopt can achieve excellent detection performance with
minimal impact on text quality.

##  Appendix C Analysis of Different Embedding Models

To investigate the impact of different embedding language models on watermark
algorithms and to discern how to appropriately select an embedding model, we
enumerate in Figure 8 the distribution of sentence embeddings and the
relationship between sentence embedding similarities and watermark logits
similarities when employing three distinct embedding models: BERT Devlin et
al. (2018), Sentence-BERT Reimers & Gurevych (2020), and Compositional-BERT
Chanchani & Huang (2023). Sentence-BERT (SBERT) and Compositional-BERT (CBERT)
have been refined for sentence similarity tasks. They show a near-normal
distribution of embedding similarities with moderate average similarity,
making them ideal as our embedding models. In this study, we opt for
Compositional-BERT, though employing Sentence-BERT would yield comparable
results. Conversely, the origin BERT model, not specifically designed for text
similarity, tends to have uniformly high text similarity scores, which in turn
means that minor perturbations in embeddings can significantly affect
watermark logits, rendering it unsuitable as the embedding language model for
our robust watermark algorithm.

Figure 7: The left figure shows how the watermark detection F1 score changes
as the value of $\delta$ (the extent of watermark augmentation) varies, using
the 4 different watermark logits from Figure 6. The right figure shows how the
perplexity (PPL) of the generated text changes with $\delta$ for the 4
different watermark logits.

Figure 8: Comparison of similarity distributions for different embedding
language models and the corresponding watermark logits after transformation.

##  Appendix D Detail Network Structure of the Watermark Model

To elaborate in detail on our methodology, we present the Python
implementation code of the watermark model described in this work, as
illustrated in Figure 9. Precisely, the network consists of an input layer,
output layer, and a middle linear network with residual connections. The
dimensions of the input correspond with the output dimensions of the embedding
model, while the output dimensions align with the size of the vocabulary.
During our implementation, given the variation in vocabulary size across
different language models, we predetermined a fixed output dimension of 1000.
Subsequently, a random mapping was established to project various vocabularies
randomly onto this output dimension.

Furthermore, it is unnecessary to recalculate using the watermark model for
every token generated during the implementation process. Since the semantics
of the text typically do not alter dramatically with the addition of
individual tokens, we compute the watermark logits at intervals of N steps
(where N ranges between 5 and 10) in practice. This approach effectively
reduces the computational complexity of our watermarking algorithm.

⬇

1class ResidualBlock(nn.Module):

2 def __init__(self, dim):

3 super(ResidualBlock, self).__init__()

4 self.fc = nn.Linear(dim, dim)

5 self.relu = nn.ReLU()

6

7 def forward(self, x):

8 out = self.fc(x)

9 out = self.relu(out)

10 out = out + x

11 return out

12

13class TransformModel(nn.Module):

14 def __init__(self, num_layers, input_dim, hidden_dim, output_dim):

15 super(TransformModel, self).__init__()

16 self.layers = nn.ModuleList()

17 self.layers.append(nn.Linear(input_dim, hidden_dim))

18 for _ in range(num_layers - 2):

19 self.layers.append(ResidualBlock(hidden_dim))

20 self.layers.append(nn.Linear(hidden_dim, output_dim))

21

22 def forward(self, x):

23 for i in range(len(self.layers)):

24 x = self.layers[i](x)

25 return x

Figure 9: The code implementation of the watermark model in this paper, where
the TransformModel class represents the watermark model network.

##  Appendix E SECURITY ROBUSTNESS ANALYSIS

In this section, we provide a general analysis of the security robustness.
Herein, security robustness refers to the likelihood of users deducing the
watermark generation methodology from knowledge of the watermark algorithm and
generated watermark text examples.

More specifically, there is a strong correlation between security robustness
and the number of watermark rules in the watermark algorithms. For instance,
the KGW-k watermark algorithm possesses a number of watermark rules equivalent
to $|V|^{k}$ (each combination of tokens of $k$ window size corresponds to a
watermark logits), hence exhibiting an exponential increase in security
robustness with increasing $k$.

Regarding our algorithm, assuming no correlation between different watermark
generation rules, the number of rules in our algorithm can be calculated using
the following equation:

$\sum_{i=1}^{T}|V|^{i}$ (11)

where $T$ represents potential text length. However, many rules generated in
this manner are semantically similar, necessitating consideration of rule
correlation when estimating the number of watermark rules. Calculating such
correlation is highly complex and not straightforward.

Rather than directly calculating the complexity of our watermarking scheme, we
demonstrate its security and robustness by the success rate of attack
algorithms in cracking the watermarking rules. Thus in Figure 3(a) we utilize
the word frequency analysis method employed by Sadasivan et al. (2023). In
this experimental setup, we analyzed 2000 generated texts, each with a length
of 200, and found that the security robustness of our algorithm is superior to
KGW-3 and closely approximates KGW-4.