additions

# A Survey of Text Watermarking in the Era of Large Language Models

Aiwei Liu<EMAIL_ADDRESS>,  Leyi Pan
<EMAIL_ADDRESS>Tsinghua UniversityBeijingChina100084 ,  Yijian Lu
<EMAIL_ADDRESS>,  Jingjing Li<EMAIL_ADDRESS>The Chinese
University of Hong KongHong KongChina999077 ,  Xuming Hu
<EMAIL_ADDRESS>,  Lijie Wen<EMAIL_ADDRESS>Tsinghua
UniversityBeijingChina100084 ,  Irwin King<EMAIL_ADDRESS>The Chinese
University of Hong KongHong KongChina999077 and  Philip S. Yu<EMAIL_ADDRESS>University of Illinois at ChicagoChicagoUnited States60607

###### Abstract.

Text watermarking algorithms play a crucial role in the copyright protection
of textual content, yet their capabilities and application scenarios have been
limited historically. The recent developments in large language models (LLMs)
have opened new opportunities for the advancement of text watermarking
techniques. LLMs not only enhance the capabilities of text watermarking
algorithms through their text understanding and generation abilities but also
necessitate the use of text watermarking algorithms for their own copyright
protection. This paper conducts a comprehensive survey of the current state of
text watermarking technology, covering four main aspects: (1) an overview and
comparison of different text watermarking techniques; (2) evaluation methods
for text watermarking algorithms, including their success rates, impact on
text quality, robustness, and unforgeability; (3) potential application
scenarios for text watermarking technology; (4) current challenges and future
directions for development. This survey aims to provide researchers with a
thorough understanding of text watermarking technology, thereby promoting its
further advancement.

Text Watermark, Large Language Models

††ccs: Computing methodologies Natural language processing††ccs: Security and
privacy Social aspects of security and privacy

##  1\. Introduction

Text watermarking involves embedding unique, imperceptible identifiers
(watermarks) into textual content. These watermarks are designed to be robust
yet inconspicuous, ensuring that the integrity and ownership of the content
are preserved without affecting its readability or meaning. Historically, text
watermarking has played a crucial role in various domains, from copyright
protection and document authentication to preventing plagiarism and
unauthorized content distribution (Kamaruddin et al., 2018). With the
advancement of Large Language Models (LLMs), both the techniques and
application scenarios of text watermarking have seen significant development.
As shown in Figure 1(a), this primarily includes the construction of enhanced
text watermarking algorithms using LLMs, the application of existing text
watermarking algorithms to LLMs, and the exploration of text watermarking
algorithms that are more closely integrated with LLMs. The flourishing
development of LLMs has propelled a thriving research landscape within the
realm of text watermarking, as depicted in Figure 1(b). Especially with the
advent of ChatGPT, text watermarking has notably surged into a research
fervor. To help better understanding the mutually beneficial relationship
between LLMs and text watermarking, this paper provides a survey of text
watermarking techniques in the era of large language models.

In the subsequent content of this section, we will separately discuss why text
watermarking benefits the application of LLMs (section 1.1), why utilizing
LLMs can lead to the development of superior text watermarking algorithms
(section 1.2), and the contributions of this survey along with the
organization of the following sections (section 1.3).

(a) A description of how LLMs promote the development of text watermarking
techniques and broaden their application scenarios.

(b) Number of publications in the field of text watermarking and LLMs (the
data for "Number of Publications in the field of LLMs" is sourced from Zhao et
al. (2023c))

Figure 1. Relationships between the development of text watermarking
techniques and Large Language Models (LLMs).

###  1.1. Why is Text Watermarking Beneficial for LLMs?

In recent years, large language models (LLMs) have made significant progress
in the field of natural language processing. As the parameter count of these
large language models continues to increase, their ability to understand and
generate language has also substantially improved. Notable examples include
GPT (Radford et al., 2018), BART (Lewis et al., 2019), T5 (Raffel et al.,
2020), OPT (Zhang et al., 2022), LaMDA (Thoppilan et al., 2022), LLaMA
(Touvron et al., 2023), and GPT4 (OpenAI, 2023). These large language models
have achieved excellent performance in a variety of downstream tasks,
including machine translation (Hendy et al., 2023; Zhu et al., 2020; Costa-
jussà et al., 2022; Hendy et al., 2023), dialogue systems (Hudeček and Dušek,
2023; Mi et al., 2022; Thoppilan et al., 2022; Shuster et al., 2022), code
generation (Ni et al., 2023; Vaithilingam et al., 2022; Nijkamp et al., 2022;
Xu et al., 2022), and other tasks (Li et al., 2020, 2022; Zhang et al., 2023b;
Thirunavukarasu et al., 2023). A recent work even suggests that GPT-4 is an
early (yet still incomplete) version of an artificial general intelligence
(AGI) system (Bubeck et al., 2023).

However, the extensive use of LLMs has also introduced a set of problems and
challenges. Firstly, the rapid generation of high-quality text by LLMs can
facilitate the rapid spread of false information (Megías et al., 2021).
Secondly, the issue of intellectual property related to large models is of
vital importance. This includes the copyright of datasets (Tang et al., 2023)
used for training large models and the addition of intellectual property
rights to prevent the extraction of knowledge from the models (Zhao et al.,
2023b). If effective tagging and detection methods for LLM-generated text
could be implemented, it would significantly aid in mitigating the
aforementioned issues. Text watermarking emerges as a promising solution to
address these challenges. By embedding a unique, identifiable, and non-
obtrusive marker (watermark) within the LLM-generated text, watermarking can
enable the tracking and attribution of content produced by LLMs.

###  1.2. Why are LLMs Beneficial for Text Watermarking?

One of the main challenges in text watermarking is embedding watermarks
without altering the original meaning or readability of the text. This
requirement presents a significant challenge, as traditional text watermarking
methods often struggle to modify the text without changing its semantics
(Atallah et al., 2001; Topkara et al., 2006a; Meral et al., 2009). This is due
to the need for text watermarking algorithms to have a strong understanding
and control over the text’s semantics. Here, Large Language Models emerge as a
game-changer. With their advanced understanding of language semantics and
context, LLMs enable more sophisticated text watermarking methods that
seamlessly integrate watermarks with minimal compromise to the text’s original
meaning (Abdelnabi and Fritz, 2021; Zhang et al., 2023a). This synergy allows
for the development of watermarking techniques that are not only more
effective but also more subtle, ensuring that the text remains as intended
while still carrying the necessary watermark features.

###  1.3. Why a Survey for Text Watermarking in the Era of LLMs?

Although text watermarking technology and large language models can
effectively enhance each other, for instance, text generated by LLMs can be
watermarked using text watermarking algorithms (Brassil et al., 1995; Por et
al., 2012; Rizzo et al., 2016; Munyer and Zhong, 2023; Yang et al., 2022,
2023; Yoo et al., 2023b), or LLMs themselves can be utilized to embed
watermarks in texts (Abdelnabi and Fritz, 2021; Zhang et al., 2023a).
Additionally, watermark algorithms can be directly incorporated during the
text generation process of LLMs (Kirchenbauer et al., 2023a; Zhao et al.,
2023a; Liu et al., 2023c, b; Ren et al., 2023; Wu et al., 2023). However, up
to date, no studies have attempted to comprehensively explore and understand
text watermarking from a broader perspective. The current surveys on text
watermarking mainly focus on techniques prior to the era of large language
models (Alkawaz et al., 2016; Kamaruddin et al., 2018).

Therefore, in this work, we provide the first comprehensive survey of text
watermarking algorithms in the era of large language models, covering the
detailed definition of text watermarking algorithms and the interconnections
between different kinds of text watermarking methods. Given the complexity and
diversity of text watermarking technology, we have also detailed how to
evaluate text watermarking algorithms from different perspectives, including
success rate, robustness, impact on text quality and unforgeability.
Additionally, we have introduced the current application scenarios of text
watermarking algorithms including copyright protection, fake news detection,
and academic integrity. This survey can provide researchers with a high-level
understanding of text watermarking algorithms and a comparison of the
similarities and differences between different text watermarking algorithms.
Researchers who merely wish to employ text watermarking technology can select
the appropriate algorithms and application scenarios based on the introduction
provided in this survey.

Organization of this survey. The remainder of this survey is organized as
follows: Section 2 introduces the definition of text watermarking and the
essential properties of text watermarking algorithms. Section 3 and Section 4
discuss two significant types of text watermarking algorithms: text
watermarking for existing text and text watermarking for LLMs. Section 5
elaborates on the different evaluation perspectives of text watermarking
algorithms, including success rate, impact on text quality, robustness, and
unforgeability. Section 6 presents the application scenarios of text
watermarking algorithms, covering copyright protection, academic integrity and
fake news detection. Section 7 analyzes the challenges still faced by current
text watermarking research and explores future research directions. Finally,
Section 8 concludes the survey.

##  2\. Preliminaries of Text Watermarking

To facilitate the introduction of various text watermarking algorithms as well
as its evaluation methods in subsequent sections, this section presents the
definition of text watermarking algorithms and outlines the characteristics
that an excellent text watermarking algorithm should possess. The taxonomy of
text watermarking algorithms is also introduced in this section.

###  2.1. Text Watermarking Algorithms

A text watermarking algorithm typically comprises two components: a watermark
generator $\mathcal{A}$, and a watermark detector $\mathcal{D}$. The watermark
generator $\mathcal{A}$ takes a text $\mathbf{x}$ and a watermark message $w$
as inputs and outputs a watermarked text $\mathbf{t}$, expressed as:

(1) $\mathcal{A}(\mathbf{x},w)=\mathbf{t}.$

The watermarked text, denoted as $\mathbf{t}$, can be derived in two ways: it
may be a modified version of the input text $\mathbf{x}$, where $\mathbf{x}$
is the original text, or it can be a new text generated in response to
$\mathbf{x}$, such as when $\mathbf{x}$ serves as a prompt for a Large
Language Model. The watermark message, denoted as $w$, can be a zero-bit
watermark, signifying merely its presence or absence, or a multi-bit
watermark, embedding detailed, customized information. The term ‘watermark
payload’ will be used henceforth to describe the quantity of information
conveyed by the watermark message.

For the watermark detector $\mathcal{D}$, its input is any text $\mathbf{t}$,
and its output is its predicted watermark message for the text, denoted as
$\mathcal{D}(\mathbf{t})=w$. If the output is None, it implies that the text
contains no watermark information.

###  2.2. Key Characteristics of Text Watermarking Algorithms

To facilitate a unified understanding of the objectives in designing text
watermarking algorithms, this section introduces the key characteristics that
a watermarking algorithm should possess. These primarily include a high
success rate of watermark detection, minimal impact on text quality,
robustness of the detector against text modifications, and unforgeability.

High success rate of watermark detection. The high success rate of a watermark
algorithm indicates that its detector $\mathcal{D}$ can accurately detect the
generated watermark text t. For a zero-bit watermark message, this accuracy is
usually measured using binary classification. When $w$ consists of multiple
bits, the evaluation commonly used is bit accuracy. If a watermarking
algorithm maintains a high success rate at a large bit number, it implies that
it possesses a high payload.

Low impact on text quality. We use $\mathcal{A}(\mathbf{x},None)$ to denote
the text generated without adding a watermark. If $\mathbf{x}$ is the text to
be modified, the output will be $\mathbf{x}$ itself. If $\mathbf{x}$ is a
prompt for LLM, it would be the text generated by LLM without a watermark. A
watermark algorithm that does not significantly affect text quality will the
following condition:

(2) $\forall
w_{i},\,\mathcal{R}(\mathcal{A}(\mathbf{x},\text{None}),\mathcal{A}(\mathbf{x},w_{i}))<\delta$

where $\mathcal{R}$ is a function evaluating text quality from multiple
perspectives, as will be discussed in seciton 4. $\delta$ represents a
threshold. If the difference in the evaluated scores of two texts is less than
this threshold, they are considered to be of similar quality.

Robustness to watermark removal attack. We use an operation $\mathcal{U}$ to
denote the watermark removal operations, which will be detailed in seciton 4.
If a watermarking algorithm is robust against watermark removal attacks, it
should satisfy the following conditions:

(3) $\forall
w_{i},\forall\mathbf{t}=\mathcal{A}(\mathbf{x},w_{i}),\,P(\mathcal{D}(\mathcal{U}(\mathbf{t}))=w_{i})>\beta.$

where $\beta$ is a threshold. If the probability of correctly detecting a
watermarked text after text modification exceeds $\beta$, the algorithm is
deemed sufficiently robust.

Unforgeability. Unforgeability refers to the difficulty for a third party to
counterfeit text watermarks. Typically, if the watermark’s generator
$\mathcal{A}$ is acquired by an attacker, the watermark can certainly be
forged. Therefore, the detailed definition of unforgeability is whether an
attacker, unable to access the watermark’s generator, can counterfeit the
watermark. This usually divides into two scenarios: in one, the attacker
cannot obtain the detector $\mathcal{D}$ and is limited to watermark
detection, known as the private detection scenario. In the second scenario,
the attacker has acquired the watermark’s detector, referred to as the public
detection scenario.

Although an ideal text watermarking algorithm should possess all four
aforementioned characteristics, it is challenging to balance them. Enhancing
one aspect might impact performance in another. In subsequent sections, we
will delve deeper into how different watermark algorithms strike a balance
among these characteristics.

###  2.3. Taxonomy of Text Watermarking Algorithms

To facilitate the organization of different text watermarking algorithms in
section 3 and section 4, this section provides an overview of our summarized
taxonomy of text watermarking algorithms.

every leaf node/.style= if n children=0#1 , every tree node/.style= if n
children=0minimum width=1em#1 ,  nonleaf/.style=font=, for tree=every leaf
node=my leaf, font=, every tree node=my node, font=, l sep-=4.5pt, l-=1.pt,
anchor=west, inner sep=2pt, l sep=10pt, s sep=3pt, fit=tight, grow’=east,
edge=ultra thin, parent anchor=east, child anchor=west, if n
children=0nonleaf, edge path= [draw, edge] (!u.parent anchor) – +(5pt,0) |-
(.child anchor)edge label; , if=isodd(n_children()) for children=
if=equal(n,(n_children("!u")+1)/2)calign with current [Text
Watermarking, draw=gray, fill=gray!15, text width=1.8cm, text=black
[Watermarking for Existing Text
(section 3), color=brightlavender, fill=brightlavender!15, text width=2cm,
text=black [Format-based Watermarking
(section 3.1), color=brightlavender, fill=brightlavender!15, text width=2.5cm,
text=black [Line/Word-Shift Coding (Brassil et al. (1995)), UniSpaCh (Por et
al. (2012)), Unicode Homoglyph Substitution (Rizzo et al. (2016)), EasyMark
(Sato et al. (2023)), color=brightlavender, fill=brightlavender!15, text
width=5.5cm, text=black] ] [Lexical-based Watermarking
(section 3.2), color=brightlavender, fill=brightlavender!15, text width=2.5cm,
text=black [ Equimark (Topkara et al. (2006b)), DeepTextMark (Munyer and Zhong
(2023)), Context-aware Lexical Substitution (Yang et al. (2022)), Binary-
encoding Lexical Substitution (Yang et al. (2023)), Robust Multi-bit Watermark
(Yoo et al. (2023b)) , color=brightlavender, fill=brightlavender!15, text
width=5.5cm, text=black] ], [Syntatic-based Watermarking
(section 3.3), color=brightlavender, fill=brightlavender!15, text width=2.5cm,
text=black [ NLW (Atallah et al. (2001)), WANE (Topkara et al. (2006a)), MA-
NLW (Meral et al. (2009)) , color=brightlavender, fill=brightlavender!15, text
width=5.5cm, text=black] ], [Generation-based Watermarking
( section 3.4), color=brightlavender, fill=brightlavender!15, text
width=2.5cm, text=black [ AWT (Abdelnabi and Fritz (2021)), REMARK-LLM (Zhang
et al. (2023a)) , color=brightlavender, fill=brightlavender!15, text
width=5.5cm, text=black] ] ] [Watermarking for LLMs
(section 4), color=lightgreen, fill=lightgreen!15, text width=2cm, text=black
[Training Time Watermarking
(section 4.1), color=lightgreen, fill=lightgreen!15, text width=2.5cm,
text=black [Dataset Trigger (Liu et al. (2023a)), Clean-Label Backdoor
Watermark (Tang et al. (2023)), Coprotector (Sun et al. (2022)), CodeMark (Sun
et al. (2023)), color=lightgreen, fill=lightgreen!15, text width=5.5cm,
text=black] ] [Watermarking During Logits Generation
(section 4.2), color=lightgreen, fill=lightgreen!15, text width=2.5cm,
text=black [KGW (Kirchenbauer et al. (2023a)), SWEET (Lee et al. (2023)),
Unbiased Watermark (Hu et al. (2023)), DiPmark (Wu et al. (2023)), COLOR (Yoo
et al. (2023a)), CTWL (Wang et al. (2023b)), ThreeBricks (Fernandez et al.
(2023)), Unigram Watermark (Zhao et al. (2023a)), KGW-reliability
(Kirchenbauer et al. (2023b)), NS-Watermark (Takezawa et al. (2023)), Semantic
Invariant Robust Watermark (Liu et al. (2023c)), Unforgeable Watermark (Liu et
al. (2023b)), Publicly Detectable Watermark (Fairoze et al. (2023)), Semantic-
based Robust Watermark (Ren et al. (2023)), color=lightgreen,
fill=lightgreen!15, text width=5.5cm, text=black] ], [Watermarking During
Token Sampling
(section 4.3), color=lightgreen, fill=lightgreen!15, text width=2.5cm,
text=black [Undetectable Watermark (Christ et al. (2023)), Robust Distortion-
free Watermark (Kuditipudi et al. (2023)), SemStamp (Hou et al. (2023))),
color=lightgreen, fill=lightgreen!15, text width=5.5cm, text=black] ] ] ]

Figure 2. The text watermarking methods can be broadly divided into two
categories: Watermarking for Existing Text (section 3) and Watermarking for
LLMs (section 4).

As illustrated in Figure 2, text watermarking algorithms can be broadly
classified into two categories. The first category, Watermarking for Existing
Text, focuses on embedding watermarks into pre-existing texts. Detailed in
Section 3, this method typically employs semantically invariant
transformations to incorporate watermarks seamlessly into the existing text.

The second category, Watermarking for Large Language Models (LLMs), involves
alterations to the large language models. As we’ll explore in Section 4, this
approach either introduces specific features into the training dataset or
modifies the text generation process of LLMs. In essence, it creates
watermarked text $\mathbf{t}$ in response to an input prompt $\mathbf{x}$.

Figure 3 offers a detailed illustration of these methods, emphasizing the
nuances of current text watermarking techniques. Notably, both the
‘watermarking during logits generation’ and ‘watermarking during token
sampling’ methods apply watermarks at the LLM inference stage, a process
collectively referred to as ‘inference time watermarking’ in this context. The
dashed line box under inference time watermarking represents the detailed
process of how the watermarked LLM generates watermarked text.

##  3\. Watermarking for Existing Text

Watermarking for existing text involves modifying a generated text to produce
a watermarked text. Based on the granularity of modifications, these methods
are primarily categorized into four types: format-based watermarking (section
3.1), lexical-based watermarking (section 3.2), syntactic-based watermarking
(section 3.3) and generation-based watermarking (section 3.4).

Figure 3. A more illustrative explanation of various text watermarking
methods. Watermarking for Existing Text (section 3) involves modifying
existing text to embed watermarks, primarily through format-based approaches
(section 3.1) such as white-space substitution, lexical-based approaches
(section 3.2) such as synonym substitution, syntactic-based approaches
(section 3.3) e.g. passivization, and generation-based approaches (section
3.4) that directly generated watermarked text through pretrained language
models. Watermarking for LLMs (section 4) refers to embedding watermarks in
Large Language Models, ensuring the text generated includes these watermarks,
which can be implemented during training time (section 4.1), during logits
generation (section 4.2), or during token sampling (section 4.3).

###  3.1. Format-based Watermarking

Format-based watermarking approaches are inspired by image watermarking
technology (Begum and Uddin, 2020). It does not modify the content of the text
but introduces changes to its format that are difficult for humans to detect,
thereby embedding a watermark. For example, Brassil et al. (1995) proposed
line-shift coding and word shift-coding techniques, achieved by vertically
shifting the positions of text lines or horizontally shifting the locations of
words within text lines. Correspondingly, the watermark detection process
involves measuring the distance between adjacent text line profiles or between
adjacent word column profiles to detect shifts. However, this approach is
limited to embedding watermarks in image-formatted text and cannot truly
return a text string with an embedded watermark. Considering this, various
watermarking methods that rely on the insertion or replacement of Unicode
codepoints have been introduced. Por et al. (2012) proposed a watermarking
scheme named UniSpach, which inserts Unicode space characters into inter-
sentence, inter-word, end-of-line and inter-paragraph spacings. A study by
Rizzo et al. (2016) presented a unicode homoglyph substitution text
watermarking method. It exploits the fact that text symbols that are similar
in appearance could have different Unicode codepoints. For instance, both
U+0043 and U+216d visually represent letter ‘C’, while U+004c and U+216c
appear as letter ‘L’. Following this, a family of simple watermarks named
EASYMARK (Sato et al., 2023) is proposed recently, composed of three different
methods: WHITEMARK, VARIANTMARK and PRINTMARK. Specifically, WHITEMARK
replaces a whitespace (U+0020) with another codepoint of a whitespace (e.g.
U+2004). VARIANTMARK leverages variation selectors of Unicode to embed hard-
to-perceive format into CJK texts. PRINTMARK, coping with printed texts, uses
ligature or whitespaces with slightly different lengths to embed watermark
messages. Correspondingly, the watermark detection process involves searching
for and counting the certain codepoints that have been inserted within the
text. As these watermarking methods relied on the richness of Unicode
encoding, their watermark payload are often quite large.

However, although these format-based watermarking methods allow for the simple
and effective embedding of large payload watermarks in text without altering
its specific content, modifications to the format can be easily spotted in
certain scenarios, as mentioned by Por et al. (2012) in the case of DASH
attack. As a result, these specially designed formats could be effortlessly
removed through canonicalization (Boucher et al., 2022), such as reseting line
spacing, searching and replacing certain codepoints through the entire text,
etc. The spotted formats might also be used to forge watermark, further
leading to the failure of effective detection.

###  3.2. Lexical-based Watermarking

Format-based approaches only modify the surface format of the text, making
them easily spotted and, consequently, more vulnerable to targeted removal by
reformatting. Therefore, it becomes imperative to explore alternative methods
that enable deeper insertion of watermarks within text. Several studies
applied word-level modifications by replacing selected words with their
alternatives without changing the sentence syntax structure (Topkara et al.,
2006b; Fellbaum, 1998; Munyer and Zhong, 2023; Yang et al., 2022, 2023; Yoo et
al., 2023b). We refer to these methods as lexical-based watermarking
approaches. Topkara et al. (2006b) presented a synonym substitution text
watermarking approach, using the linguistic database WordNet(Fellbaum, 1998)
as its synonym dictionary. The watermark detection process essentially
replicates the watermark message embedding procedure, with the distinction
that inverse rules are employed during the message extraction phase. In order
to conduct semantic modeling more effectively, Munyer and Zhong (2023)
utilized a pretrained Word2Vec model instead of WordNet to find alternatives.
In particular, they converted the selected words into Word2Vec vectors and
collected the n-nearest vectors to form replacement word set. Noticeably, they
trained a binary classifier as watermark detector, using pretrained BERT model
and transformer blocks as neural network components.

However, the aforementioned watermarking approaches, which depended on
context-independents synonym substitution (WordNet & Word2Vec), tend to
overlook the context of the target words when generating substitute
candidates. This oversight may result in a failure to preserve the overall
semantics of the sentence, consequently diminishing the quality of the text.
In response to this issue, context-aware lexical substitution is introduced
into text watermarking techniques. Yang et al. (2022) proposed a novel BERT-
based infill model to generate lexical substitution candidates, taking the
overall sentence’s meaning into account. The watermark detection algorithm
mimics the watermark generation process, first locating words containing the
embedded watermark message, then generating substitute candidates, and finally
applying the inverse embedding rules to extract the watermark message. To
simplify the watermark detection process, Yang et al. (2023) developed a
watermarking scheme by first computing a random binary encoding for each word,
then replacing the words representing bit-0 with context-based synonyms that
represent bit-1. Since the encoding computed for non-watermarked text adhere
to a Bernoulli distribution and the distribution is altered during the
watermarking process, statistical tests can be employed directly to detect the
presence of the watermark. To further improve the robustness of watermark
algorithms against watermark removal attacks, a study by Yoo et al. (2023b)
fine-tuned BERT-based infill model with keyword-preserving and syntactically-
invariant corruptions, which achieved a state-of-the-art robustness compared
to previous approaches.

Lexical-based watermarking approaches embed watermarks by substituting
synonyms in the text. However, the scope for semantically non-altering synonym
replacements that do not affect the text structure is likely limited.
Consequently, the capacity for the watermarks in lexical-based approaches is
restricted, often necessitating a trade-off with text quality.

###  3.3. Syntactic-based Watermarking

The lexical-based approaches attempted to embed watermark messages by
replacing certain words without altering the syntax structure of the sentence.
However, methods relying solely on lexical substitution are likely to lack
robustness against simple watermark removal attacks, such as random synonym
replacements. In the light of this, some studies attempt to embed watermarks
in text in a manner that is more challenging to remove, specifically by
altering the syntax structures of the text. These methods are known as
syntactic-based watermarking approaches. Atallah et al. (2001) introduced
three typical syntax transformations–Adjunct Movement, Clefting and
Passivization–to embed watermark messages, where:

  * •

Adjunct Movement refers to the shifting of adjuncts to different positions
within a sentence. For instance, the adverbial phrase ‘often’ can be placed in
multiple locations in the sentence The dog often chased the cat.

  * •

Clefting is a transformational process used to emphasize a specific part of a
sentence, often the subject. For example, the sentence The dog chased the cat
can be transformed into It was the dog that chased the cat to highlight the
dog.

  * •

Passivization involves converting active voice sentences with transitive verbs
into the passive voice. For instance, the active sentence The dog chased the
cat can be transformed into the passive form The cat was chased by the dog.

Each transformation type corresponds to a specific message bit. For instance,
Adjunct Movement corresponds to 0, Clefting stands for 1, and Passivization
represents 2. During watermark detection, the original and the modified text
are both transformed into syntax trees. The syntax structures are subsequently
compared sentence by sentence to extract watermark messages. Following this,
Topkara et al. (2006a) expanded the watermark payload by additionally
introducing two syntax transformation type: Activization and Topicalizaiton.
Moreover, effort has not been solely made about adding watermarks into English
corpus. Meral et al. (2009) investigated 20 morphosyntactic tools in Turkish.
They noted that languages with high suffixation and agglutination, like
Turkish, provide ample opportunities for syntactic-based watermarking.

Syntactic-based watermarking approaches can embed watermarks into existing
texts in a relatively concealed manner. However, this method relies
significantly on the grammatical rules of a language, potentially
necessitating customization for each language. In certain texts, frequent
syntactic alterations might also impact the original style and fluency of the
text.

###  3.4. Generation-based Watermarking

The aforementioned methods have indeed made significant strides in the field
of text watermarking. However, these methods are still quite reliant on
specific rules, which may lead to unnatural modifications in some contexts. On
one hand, the unnatural modifications might lead to degradation of text
quality. On the other hand, if these clues are observed by human attackers,
there is a higher likelihood of them to design watermark removal attacks or
attempt to forge watermarks deliberately and specifically. A groundbreaking
advancement would be generating watermarked text directly from the original
text and the watermark message. With the rapid development of pretrained
language models, such techniques are gradually becoming feasible. In the realm
of generation-based approaches, the encoded original text and the watermark
message are typically fed into a pretrained language model, which subsequently
generates the watermarked text end-to-end.

Abdelnabi and Fritz (2021) introduced an end-to-end watermarking scheme named
AWT. It harnesses a transformer encoder for encoding the original sentence. It
then combined the sentence embedding and message embedding, feeding this
composite input into a transformer decoder to derive the watermarked text.
During the watermark detection process, the watermarked text is fed into
transformer encoder layers to obtain the secret message. Building on top of
AWT, Zhang et al. (2023a) noticed the gap between the dense distributions of
the watermarked text and the sparse distributions of the one-hot watermark
message encodings. To bridge this gap, they presented a watermarking method
named REMARK-LLM. Likewise, its watermarking process inserts watermark message
into the original text via a pretrained language model. Noticeably, a
reparameterization step is introduced to transform the distribution of the
generated watermarked tokens into a sparser distribution using Gumbel-Softmax
(Jang et al., 2016). Then a decoder based on the transformer architecture is
employed to extract the concealed messages from these embeddings. The
reparameterization step allows REMARK-LLM to successfully embed two times more
signatures into original text compared to prior art AWT and at the meantime
maintain detection effectiveness, making a significant progress in expanding
watermark payload.

##  4\. Watermarking for LLMs

In the above section, we discussed watermarking methods for existing text.
With more and more texts directly generated by large language models, studying
text watermarking techniques for large models has become a trend. Unlike the
method of modifying existing text to add a watermark, the watermarking for
LLMs technology directly enables LLM-generated text to contain a watermark.
Specifically, given a watermark message $w$ and a prompt $\mathbf{x}$, the
process of watermarking for LLMs is defined by the following expression:

(4) $\mathcal{A}(\mathbf{x},w)=M_{w}(\mathbf{x})=\mathbf{t}.$

To facilitate explanation, we assume that the watermarked text is directly
generated by a language language model $M_{w}$ with an embedded watermark
message.

To provide a better understanding of how to add a watermark to a Large
Language Model, we first provide an overview of the process used for
generating text with an LLM. Specifically, this involves three steps, LLM
training, logits generation and token sampling:

  * •

Step1: LLM training. The process involves training a large language model M
using dataset D. The specific objectives of training can vary depending on the
application context. Currently, the most prevalent training objective employed
is next token prediction (Radford et al., 2019).

  * •

Step2: logits generation. Given a trained large language model M, a prompt
$\mathbf{x}$, and a sequence of previously generated tokens
$\mathbf{t}^{0:(i-1)}$, the LLM generates a probability distribution over the
next token $\mathbf{t}^{(i)}$ in the vocabulary $\mathcal{V}$, represented as
logits $\mathbf{l}^{(i)}$:

(5) $\mathbf{l}^{(i)}=M(\mathbf{x},\mathbf{t}^{0:(i-1)}).$

  * •

Step3: token sampling. The next token $\mathbf{t}^{(i)}$ is sampled from the
logits $\mathbf{l}^{(i)}$ which could be achieved using nucleus sampling
(Holtzman et al., 2019), choosing the token with the highest probability
(greedy decode), or using other decode algorithms such as beam search to
select a list of tokens with the highest probability. Here we use $S$ to
denote the token sampling process:

(6) $\mathbf{t}^{(i)}=S(\text{softmax}(\mathbf{l}^{(i)})).$

Through these steps, the large language model M can produce a single token
$\mathbf{t}^{(i)}$. To generate multiple tokens, we could simply repeat the
logits generation and token sampling process iteratively.

Considering that there are three important steps during the utilization of LLM
to generation text, watermarking for LLMs techniques could also be divided
into three distinct types correspondingly. Specifically, we refer to the three
distinct types as training time watermarking, watermarking during logits
generation, and watermarking during token sampling. These three watermarking
techniques will be elaborated in sections 4.1, 4.2, and 4.3, respectively.

###  4.1. Training Time Watermarking

The objective of training time watermarking is to embed a watermark message,
denoted as $w$, into a LLM during its training phase. This process is
typically accomplished by embedding the watermark message $w$ into the
training dataset. Specifically, embedding a watermark message into a given
dataset $D$ typically follows the following steps. The process begins with the
extraction of a subset $D_{s}$ from the dataset. A watermark message is then
embedded onto this subset through a watermark embedding function $W$,
producing the corresponding watermarked subset $\widetilde{D}_{s}$, denoted as
$\widetilde{D}_{s}=W(D_{s},w)$. Consequently, the watermarked dataset $D_{w}$
is defined as the union of the original dataset $D$ and the watermarked subset
$\widetilde{D}_{s}$, minus the non-watermarked subset $D_{s}$, as expressed by
the following formula:

(7) $D_{w}=(D\setminus D_{s})\cup\widetilde{D}_{s}$

Subsequently, the large language model (LLM) trained on the watermarked
dataset $D_{w}$ is embedded with the watermark message $w$, denoted as
$M_{w}$. Typically, $M_{w}$ exhibits characteristics of the watermark message
$w$ when operating on datasets with a distribution similar to
$\widetilde{D}_{s}$, enabling the wateramrk detection. In this process, the
most critical aspect is the design of the watermark embedding function $W$,
specifically how to transform $D_{s}$ into $\widetilde{D}_{s}$. Presently,
methods for designing $W$ predominantly draw on the concept of a backdoor
attack. Within the training set $\widetilde{D}_{s}=\\{(x,y)\\}$, for an input
$x$, a specific trigger is introduced to embed a recognizable feature which
manifests in the corresponding output and is detected in the subsequent
verification process. Depending on whether the introduced trigger disrupts the
original label $y$, the current methods can be broadly classified into two
categories.

The first category of methods introduces a trigger to x, compromising the
corresponding label y for that segment of x. For instance, Liu et al. (2023a)
proposed a training time watermark algorithm for text classification tasks,
randomly selecting a subset of text data to insert triggers at the character-
level, word-level, or sentence-level. These triggers are distinct features,
and they uniformly changed the labels of these data to a specific $y_{t}$. Sun
et al. (2022) implemented a similar approach for code generation, applying
word-level or sentence-level triggers to text, and employing methods like code
corrupting to disrupt the associated code. Although these techniques are
effective for detecting models using trigger-inclusive text, they compromise
part of the dataset’s labels, potentially degrading the model’s inherent
capabilities.

To address this issue, methods that produce low distortion on labels are
required. Tang et al. (2023) initially adopt adversarial learning to identify
examples within a certain category C that are prone to be wrongly classified
by models and then add triggers to these samples without altering their
original labels. For code generation tasks, Sun et al. (2023) conduct
semantically invariant transformations of the code, such as employing
different forms of syntactic sugar. This allows for the matching and detection
of triggers in text with varying code styles. Currently, the objective of
training time watermarking is to protect the copyright of datasets from
unauthorized use.

Although Training Time Watermarking can embed watermark messages into large
language models, it has several distinct disadvantages. Firstly, the
watermarked LLM $M_{w}$, can only produce watermarked outputs for a subset of
inputs. Secondly, the watermark payload is considerably limited, typically
only indicating the presence of a watermark and not containing more extensive
information. Thirdly, the watermark message is challenging to modify: altering
the watermark message $w$ often requires retraining the model, which is a
costly process. Therefore, the application of Training Time Watermarking
remains quite limited.

###  4.2. Watermarking during Logits Generation

Watermarking during logits generation refers to the insertion of a watermark
message $w$ into the logits (i.e., probabilities of tokens in the vocabulary
$\mathcal{V}$) generated by large language models. This approach does not
necessitate alterations to the parameters of the LLM $M$, rendering it more
flexible and cost-effective compared to training time watermarking methods.

In the scenario of watermarking during logits generation, the watermarking
algorithm $\mathcal{A}$ modifies the logits produced by the LLM. Specifically,
the watermark’s message $w$ is embedded into the logits generated by LLM. The
watermarked logits $\widetilde{\mathbf{l}^{(i)}}$, could be calculated using
the following formula:

(8)
$\widetilde{\mathbf{l}^{(i)}}=\mathcal{A}(M(\mathbf{x},\mathbf{t}^{0:(i-1)}),w)=M_{w}(\mathbf{x},\mathbf{t}^{0:(i-1)}),$

where we assume the watermarked logits $\widetilde{\mathbf{l}^{(i)}}$ is
generated by a watermarked LLM $M_{w}$.

Kirchenbauer et al. (2023a) proposed the first watermarking method based on
LLM logits modification, referred to as KGW. There, the watermark generator
randomly splits the vocabulary set into a red list and a green list at each
position depending on the previous token using a hash function. As illustrated
in Figure 4, when $M_{w}$ generates the $i^{th}$ token, a small bias $\delta$
is added to the logits of the tokens in the green list. Let $G$ represent the
green list and $R$ stands for the red list. Then the logits value of token
$v_{j}$ at position $i$ would be calculated as follows:

(9)
$\widetilde{\mathbf{l}_{j}^{(i)}}=M_{w}(\mathbf{x},\mathbf{t}^{0:(i-1)})=\left\\{\begin{array}[]{lr}M(\mathbf{x},\mathbf{t}^{0:(i-1)})[j]+\delta,&\
v_{j}\in G\\\ M(\mathbf{x},\mathbf{t}^{0:(i-1)})[j],&\ v_{j}\in
R\end{array}\right.$

As the watermark algorithm favors the logits of green tokens, the watermarked
text is expected to contain a higher proportion of green tokens compared to
the unwatermarked text. Consequently, the watermark detector assesses whether
a text is watermarked by first utilizing the hash function to categorize each
token as red or green sequentially. Following this, it calculates the green
token proportion using the z-metric. If the green token proportion surpasses a
specific threshold, the text is classified as watermarked.

Figure 4. A more illustrative description of the KGW (Kirchenbauer et al.,
2023a) algorithm.

Although the KGW watermark detection method demonstrated exceptional
performance in its test scenarios, achieving a false positive rate (human text
misclassified as watermark text) of less than $3\times 10^{-3}$%, and a false
negative rate (watermark text not detected) of less than 1%, there remain
numerous highly challenging scenarios in real-world applications that
necessitate specialized optimization and design of the watermark algorithm to
effectively address them. Below, we list four representative scenarios and
thoroughly introduce the improvements and explorations made to watermark
algorithms in these contexts, which are illustrated in Figure 5.

####  4.2.1. Watermarking low-entropy text.

Low-entropy scenarios are situations such as code generation and formatted
document generation, where the generated text is relatively deterministic.
Entropy serves as a quantification of textual uncertainty, which is calculated
as follows:

(10) $H^{(i)}=-\sum_{j=1}^{|\mathcal{V}|}P_{j}^{(i)}\log P_{j}^{(i)},$

where $P_{j}^{(i)}$ denotes the probability value of token $v_{j}$ at position
$i$. A decrease in entropy corresponds to a heightened level of certainty
within the produced text. In real applications, it is also necessary to add
watermark when using LLM to generate low-entropy text. Under low-entropy
scenarios, significant modifications are not allowed, since it may notably
degrade text quality. Therefore, watermarking and detecting watermark in low-
entropy text pose a challenging task.

To address this problem, Lee et al. (2023) suggested calculating the entropy
before adding preference to logits of green tokens (i.e. set G in Equation 9).
If the entropy $H^{(i)}$ is lower than a threshold $H$, the logits vector
remains unmodified. Similarly, Wang et al. (2023b) employed a balance-marking
strategy, constraining the choice of vocabulary to a subset where the
cumulative model log probabilities exceed a certain percentage. This approach
effectively allows for the watermarking on only high-entropy tokens while
bypassing low-entropy tokens. For instance, consider a specific case where
there is only one word candidate; in such a scenario, the vocabulary subset is
limited to this single candidate. The above methods (Lee et al., 2023; Wang et
al., 2023b), by considering the influence of text entropy during the
watermarking process, achieves a relatively low impact on the quality of the
text. However, this method is still ineffective when the number of high-
entropy tokens in the text is low. Adding watermarks to low-entropy text
remains a challenge.

####  4.2.2. Watermark with multi-bit payload.

The KGW(Kirchenbauer et al., 2023a) watermark algorithm introduced by Equation
9, could only determine the presence of a watermark and no additional
information, categorizing it as a zero-bit payload watermark. However,
practical applications often demand that watermarks carry additional
information such as copyright details, timestamps, or specific identifiers.
This necessitates watermarking techniques that not only detect the presence of
watermarks but also extract meaningful information, which could be categorized
as multi-bit payload watermark.

To achieve this, one possible solution is to establish multiple splits for
dividing the vocabulary into a red list and a green list. Specifically, we can
set N types of splits for the vocabulary, such as
$[(G_{1},R_{1}),…,(G_{N},R_{N})]$, where each split could performing LLM
watermarking following the way introduced in Equation 9. Each split
corresponds to a specific watermark message, endowing the watermark with a
$log_{2}{N}$-bit payload. For instance, Wang et al. (2023b) permits the user
to input a watermark message $m$ with $log_{2}{N}$ bits. Subsequently, based
on the hash value of this message $m$, the vocabulary is divided. However,
during detection phase, this method requires iterating through all $N$
possible messages, calculating the correlation between the text and the
red/green splits corresponding to each message respectively, thus is not
efficient. To mitigate this issue, Fernandez et al. (2023) proposed the Cyclic
Shift method, where distinct messages are generated by cyclically shifting an
initial message. This approach reduces redundant computational steps and
enhances detection efficiency through parallel processing.

However, these methods, due to the necessity of iterating each possible
message, encounter heightened computational complexity with the growing
watermark payload. To address this, Yoo et al. (2023a) proposed allocating
different bits of the message to various positions in the watermark text,
allowing independent detection of different bit altogether in a single
detection round. Then the information corresponding to each bit is
concatenated to obtain the final message. Specifically, the message is modeled
as a sequence $m=\Sigma^{b}$ where $\Sigma=\\{0,1\\}$. The process of dividing
the vocabulary at each generation step is then split into two phrases: the
first involves choosing a position in the message, $\Sigma^{b}[i]$, based on
the existing random seed, and the second involves dividing the vocabulary
according to this $\Sigma^{b}[i]$ and random seed. This approach significantly
improves efficiency by enabling the parallel detection of bit information.
Furthermore, Yoo et al. (2023a) also suggest dividing the vocabulary into more
parts, so that each position $\Sigma^{b}[i]$ in $m$ can contain more
information, further enhancing the payload of the text watermark.

####  4.2.3. Preventing watermark removal attack.

As discussed in section 2, an effective watermarking algorithm must possess
sufficient robustness against watermark removal attacks, ensuring that the
watermark text remains detectable post-attack. These attacks typically involve
modifications to the text without altering its semantic content, which will be
introduced in section 5.3. Although the KGW algorithm (Kirchenbauer et al.,
2023a) demonstrated some robustness to watermark removal attacks in their
experiments, there remains room for improvement in its robustness.

In particular, for the watermarking during logits generation methods
(Kirchenbauer et al., 2023a, b; Zhao et al., 2023a; Liu et al., 2023b, c), the
most significant factor affecting robustness is how to determine the
modifications to logits. More specifically, how to divide the red-green list
mentioned in the KGW method (Kirchenbauer et al., 2023a). In the original KGW
method (Kirchenbauer et al., 2023a), the red-green list is determined based on
the hash value of preceding tokens. Kirchenbauer et al. (2023b) further
elaborated on some specific hash strategies, such as using only the token with
the smallest token id in previous tokens for hashing to decide the red-green
list, which can enhance robustness. (Zhao et al., 2023a) proved that a
globally fixed split of red and green list results in higher robustness to
watermark removal attacks . Additionally, since watermark removal attacks
typically do not alter the semantic content of the text, many studies have
also designed methods to determine the split of the red-green list based on
textual semantics. For example, Liu et al. (2023c) trained a watermark model
that can directly convert text semantic embeddings into watermark logits. Ren
et al. (2023) converted semantic embeddings into semantic values through
weighted embedding pooling followed by discretizing using NE-Ring, and then
divided the vocabulary into red-list and green-list based on these semantic
values. The current methods primarily focus on investigating the robustness of
zero-bit watermark algorithms against watermark removal attacks. Future
algorithms could further explore the robustness of multi-bit payload watermark
algorithms.

Figure 5. Demonstration of how various methods improve upon KGW (Kirchenbauer
et al., 2023a) to adapt to four scenarios: Watermarking Low-entropy Text,
Watermark with Multi-bit Payload, Preventing Watermark Removal Attack, and
Defending against Watermark Forgeries.

####  4.2.4. Defending against watermark forgeries.

In the aforementioned discussion on the watermark algorithms’ ability to
preventing watermark removal attacks, it is assumed that the attacker is not
aware of the details and generation methods of the watermark algorithm, which
is essentially a black-box setting. Once an attacker obtain the watermark
generation details, they could effortlessly remove the watermark using the
anti-watermark techniques (Kirchenbauer et al., 2023b) or forge the watermark
easily. Therefore, for watermark algorithms, the capability to defend against
watermark forgeries is of great importance. The ability to defend against
watermark forgeries depends on the watermark algorithm’s capacity to
effectively conceal its watermark generation process.

If a watermark algorithm produces watermarked text that is imperceptible, the
watermark would become more difficult to forge. Here, imperceptible refers to
the indistinguishability in distribution between watermarked and non-
watermarked texts. Hu et al. (2023) discovered that the way KGW algorithm
(Kirchenbauer et al., 2023a) modifies to logits are biased, thus lacking the
imperceptibility. Specifically, biased in this context is defined as the
expectation of watermarked logits for all keys being the original logits of
the language model:

(11) $\mathop{\mathbb{E}}\limits_{k\sim
K}[M_{w}(\mathbf{x},\mathbf{t}^{0:(i-1)})]=M(\mathbf{x},\mathbf{t}^{0:(i-1)}),$

where each distinct key corresponds to a different method of splitting the
red-green list. The key reason why the KGW algorithm is biased is that it
applies a uniform bias, $\delta$, to all tokens in the green list. However,
this uniform $\delta$ disproportionately impacts tokens with lower
probabilities, ultimately resulting in bias (as detailed in the proof by (Hu
et al., 2023)). To address this issue, Hu et al. (2023) proposed two
reweighting methods to make the watermarking algorithm unbiased. The
$\delta$-reweight method samples a one-hot distribution directly based on the
original logits’ distribution. In contrast, the $\gamma$-reweight method
randomly rejects half of the probability distribution range, doubling the
probabilities of the remaining tokens. Similarly, Wu et al. (2023) employed an
$\alpha$-reweight method, which rejects tokens with probabilities below
$\alpha$ and proportionally increases the probabilities of the rest.
Theoretically, these three algorithms can be proven to be unbiased. These
unbiased watermarking algorithms, compared to the KGW algorithm, are better at
being imperceptible. However, the unbiased distribution resulting from these
re-weighting methods may not guarantee theoretical imperceptibility. For
instance, the variance in the distributions with same mathematical
expectations might be distinct. Therefore, further work is required to explore
whether these algorithms can truly achieve imperceptibility.

The capability of watermark algorithms to defend against watermark forgeries
cannot be solely based on the imperceptibility of the watermark. It is also
crucial that these algorithms robustly protect watermark rules from being
deciphered. In this context, we differentiate between two scenarios: private
detection and public detection. Private detection refers to cases where
watermark detection is only accessible to users through an API. In contrast,
public detection implies that the detail of watermark detector is open to all
users. For private detection scenarios, the complexity of the watermark
algorithm plays a vital role in its ability to resist watermark forgeries. For
instance, Zhao et al. (2023a) adopted a fixed global red-green list split to
generate watermark logits. Such a simple rule can be easily cracked through
statistical analysis of the watermark text (Sadasivan et al., 2023), revealing
which tokens are included in the green token list. Conversely, Liu et al.
(2023c) employed the semantic information to generate watermarked logits.
Extracting the watermark rules from their produced watermark text is
considerably more challenging, as these rules vary with different texts and
are sufficiently complex.

In the context of public detection scenarios, resisting watermark forgeries
becomes significantly more challenging. This difficulty arises because
attackers can access the watermark detectors. For methods where the watermark
generation process is involved in detection (Kirchenbauer et al., 2023a, b;
Zhao et al., 2023a; Liu et al., 2023c), exposing the watermark generator leads
to a complete inability to resist watermark forgeries. To address this issue,
Fairoze et al. (2023) have utilized digital signature technology from the
field of cryptography. This approach involves generating watermarks using a
private key and verifying them with a public key. However, the verification
via public key relies on features extracted from the text and users can still
exploit these features to forge watermarks. Further advancing this field, Liu
et al. (2023b) proposed the use of neural networks for watermark detection.
Due to the black-box nature of neural networks, the details of watermark
generation are not exposed, which could defend against watermark forgeries in
public detection scenarios.

###  4.3. Watermarking during Token Sampling

The previous section primarily focused on incorporating watermarks during the
logits generation phase for Large Language Models. However, even after
embedding watermarks, it is necessary to sample the next token from the
watermarked logits. Consequently, the effectiveness of the watermark might be
influenced by different sampling methods; for instance, beam search typically
allows for a higher watermark intensity. In this section, we will introduce a
technique of watermarking during token sampling, which does not alter the
logits produced by the LLM. The primary advantage of this method is that the
generated text is usually unbiased, thus minimally affecting text quality and
serving as the first line of defense against watermark forgery.

The principle of incorporating watermarks during the token sampling phase is
derived from the randomness inherent in token sampling. In this scenario,
watermarks can be introduced using a fixed random seed, where a pseudo-random
number generator produces a sequence of pseudo-random numbers to guide the
sampling of each token. For watermark detection, it is only necessary to
assess the alignment between the text tokens and the pseudo-random numbers,
specifically evaluating whether the choice of each token in the text matches
with the corresponding value in the random number sequence. For instance,
Christ et al. (2023) use binary representation for each word in the
vocabulary, with the pseudo-random numbers represented as a series of values
$u\in[0,1]$. This facilitates the sampling process using the pseudo-random
numbers. Specifically, if the predicted probability for a certain position
exceeds the corresponding pseudo-random number, then 1 is sampled at that
position, otherwise 0. In the detection of watermarks, it can be determined
whether the values of the pseudo-random numbers corresponding to the positions
with 1 in the binary tokens are significantly higher than those with 0.
However, this method still faces two challenges: 1) the detection algorithm is
not robust enough against watermark removal attacks, which involves certain
text modifications, and 2) due to the fixed nature of pseudo-random numbers,
the LLM with watermark will generate the same text for the same prompt each
time, thereby losing the inherent randomness in text generation by LLM.

To address these issues, Kuditipudi et al. (2023) proposed the use of a
pseudo-random number sequence significantly longer than the text, randomly
selecting a starting position from the sequence for each watermark insertion
to introduce randomness. Additionally, during watermark detection, they
incorporate a soft notion of edit distance (i.e., Levenshtein distance) into
the computation of the alignment between text and the pseudo-random number
sequence. This approach significantly enhances the robustness of the
watermarking algorithm against watermark removal attacks. Apart from
intervening in the sampling process of each token one by one, Hou et al.
(2023) suggested incorporating watermarks during sentence-level sampling. The
algorithm initially partitions the semantic embedding space into a watermarked
region and a non-watermarked region, and then performs sentence-level
rejection sampling until the sampled sentence falls within the watermarked
region. Since the partition principles are based on sentence-level semantics,
this approach significantly enhances robustness against watermark removal
attacks such as paraphrasing. Currently, there is limited research on
watermarking during token sampling, suggesting substantial potential for
growth in this field. Moreover, the practical effectiveness and robustness of
this method may require further validation through more experiments and real-
world applications.

##  5\. Evaluation Metrics for Text Watermarking

In sections 3 and 4, we have provided a comprehensive introduction to the
existing text watermarking methods. Meanwhile, for a text watermarking
algorithm, it is crucial to conduct a comprehensive evaluation from various
perspectives. In this section, we will introduce how to evaluate a
watermarking algorithm from four perspectives: success rate, text quality,
robustness and unforgeability. Among these, success rate (section 5.1) refers
to the ability to correctly detect watermarked texts. Text quality (section
5.2) assesses whether the quality of watermarked text is degraded compared to
non-watermarked text. Robustness (section 5.3) examines whether the
watermarked text can still be detected after watermark removal attacks.
Finally, unforgeability (section 5.4) evaluates the difficulty for third
parties to forge the watermark. Furthermore, Table 1 outlines the alignment
between various text watermarking algorithms discussed in the survey and the
evaluation perspectives they contribute to.

Table 1. Relationships between text watermarking algorithms covered in the
survey and the evaluation metrics, featuring the individual objectives each
text watermarking algorithm aims to achieve. $\blacktriangle$ stands for basic
objectives, $\bullet$ stands for primary objectives, and $\circ$ stands for
secondary objectives.

Text Watermarking Algorithms |  |  | Objectives |  |  |  |
---|---|---|---|---|---|---|---
Watermarked |  |  |  |  |  |  |
Object | Category |  Method | Success Rate |  |  Text Quality |  Robustness |  Unforgeability
|  |  | Detection Accuracy |  Payload |  |  |
Existing Text |  |  |  |  |  |  |
(section 3) | Format-based |  |  |  |  |  |
(section 3.1) |  Line/Word-Shift Coding (Brassil et al., 1995) |  $\blacktriangle$ |  |  $\bullet$ |  |  |
|  |  UniSpach (Por et al., 2012) | ▲ |  $\bullet$ |  $\bullet$ |  |
|  |  Unicode Homoglyph Substitution (Rizzo et al., 2016) | ▲ |  $\bullet$ |  $\bullet$ |  |
|  |  EasyMark (Sato et al., 2023) | ▲ |  $\bullet$ |  $\bullet$ |  |
| Lexical-based |  |  |  |  |  |
(section 3.2) |  Equimark (Topkara et al., 2006b) |  $\blacktriangle$ |  |  $\bullet$ |  $\circ$ |  |
|  |  DeepTextMark (Munyer and Zhong, 2023) | ▲ |  |  $\bullet$ |  $\bullet$ |
|  |  Context-aware Lexical Substitution (Yang et al., 2022) | ▲ |  $\circ$ |  $\bullet$ |  $\circ$ |
|  |  Binary-encoding Lexical Substitution (Yang et al., 2023) | ▲ |  |  $\circ$ |  $\circ$ |
|  |  Robust Multi-bit Watermark (Yoo et al., 2023b) | ▲ |  $\circ$ |  $\circ$ |  $\bullet$ |
| Syntatic-based |  |  |  |  |  |
(section 3.3) |  NLW (Atallah et al., 2001) |  $\blacktriangle$ |  |  |  $\bullet$ |  |
|  |  WANE (Topkara et al., 2006a) | ▲ |  $\bullet$ |  $\circ$ |  $\bullet$ |
|  |  MA-NLW (Meral et al., 2009) | ▲ |  $\bullet$ |  $\circ$ |  $\circ$ |
| Generation-based |  |  |  |  |  |
( section 3.4) |  AWT (Abdelnabi and Fritz, 2021) |  $\blacktriangle$ |  |  $\bullet$ |  $\bullet$ |  |
|  |  REMARK-LLM (Zhang et al., 2023a) | ▲ |  $\bullet$ |  $\circ$ |  $\circ$ |
LLMs |  |  |  |  |  |  |
(section 4) | Training Time |  |  |  |  |  |
(section 4.1) |  Dataset Trigger (Liu et al., 2023a) |  $\blacktriangle$ |  |  $\bullet$ |  |  |
|  |  Clean-Label Backdoor Watermark (Tang et al., 2023) | ▲ |  |  $\bullet$ |  |
|  |  Coprotector (Sun et al., 2022) | ▲ |  |  $\bullet$ |  |
|  |  CodeMark (Sun et al., 2023) | ▲ |  |  $\bullet$ |  |
| Logits Generation |  |  |  |  |  |
(section 4.2) |  KGW (Kirchenbauer et al., 2023a) |  $\blacktriangle$ |  |  $\bullet$ |  |  |
|  |  SWEET (Lee et al., 2023) | ▲ |  |  $\bullet$ |  |
|  |  Unbiased Watermark (Hu et al., 2023) | ▲ |  |  $\bullet$ |  $\circ$ |  $\bullet$
|  |  DiPmark (Wu et al., 2023) | ▲ |  |  $\bullet$ |  $\circ$ |  $\bullet$
|  |  COLOR (Yoo et al., 2023a) | ▲ |  $\bullet$ |  $\circ$ |  |
|  |  CTWL (Wang et al., 2023b) | ▲ |  $\bullet$ |  $\bullet$ |  $\circ$ |  $\bullet$
|  |  ThreeBrick (Fernandez et al., 2023) | ▲ |  |  |  $\circ$ |
|  |  Unigram Watermark (Zhao et al., 2023a) | ▲ |  |  |  $\bullet$ |
|  |  KGW-reliability (Kirchenbauer et al., 2023b) | ▲ |  |  |  $\bullet$ |
|  |  NS-Watermark (Takezawa et al., 2023) | ▲ |  |  $\bullet$ |  $\circ$ |
|  |  Semantic Invariant Robust Watermark (Liu et al., 2023c) | ▲ |  |  $\circ$ |  $\bullet$ |  $\bullet$
|  |  Unforgeable Watermark (Liu et al., 2023b) | ▲ |  |  $\circ$ |  $\circ$ |  $\bullet$
|  |  Publicly Detectable Watermark (Fairoze et al., 2023) | ▲ |  |  $\circ$ |  $\circ$ |  $\bullet$
|  |  Semantic-based Robust Watermark (Ren et al., 2023) | ▲ |  |  $\circ$ |  $\bullet$ |
| Token Sampling |  |  |  |  |  |
(section 4.3) |  Undetectable Watermark (Christ et al., 2023) |  $\blacktriangle$ |  |  $\bullet$ |  $\circ$ |  $\bullet$ |
|  |  Robust Distortion-free Watermark (Kuditipudi et al., 2023) | ▲ |  |  $\bullet$ |  $\bullet$ |  $\bullet$
|  |  SemStamp (Hou et al., 2023) | ▲ |  |  $\circ$ |  $\bullet$ |

###  5.1. Success Rate

For a text watermarking algorithm, the fundamental requirement is that the
watermarked text could be detected with a high probability. In this section,
we consolidate how current watermarking algorithms measure their success rate.
Based on the amount of information carried by the watermarking algorithm, we
will introduce it in two scenarios: zero-bit and multi-bit.

####  5.1.1. Zero-bit Watermark

In zero-bit watermarking, the watermarking algorithm can only determine
whether a text contains a watermark, without the ability to extract additional
information from the watermarked text. Given that the detection of a zero-bit
watermark inherently represents a binary classification problem — discerning
whether a text is watermarked or not — the evaluation of its success rate
typically employs classification metrics, such as accuracy and F1 score. In
most works (Kirchenbauer et al., 2023a; Zhao et al., 2023a; Liu et al., 2023b,
c), since the proportion of watermarked and non-watermarked texts in the test
dataset is usually equal, the values of accuracy and F1 score tend to be quite
similar. Despite this, the F1 score is often more frequently utilized,
accompanied by additional metrics including false positive and false negative
rate (Kirchenbauer et al., 2023a; Zhao et al., 2023a; Liu et al., 2023b).
Here, false positives denote the erroneous classification of non-watermarked
texts as watermarked, whereas false negatives refer to the incorrect
classification of watermarked texts as non-watermarked. Generally, false
positives are more important since misidentifying human-generated texts as
watermarked can lead to more adverse consequences.

However, since most watermark detection algorithms require a threshold to
determine the F1 or accuracy values, the uncertainty of this threshold may
introduce unfairness in the performance comparison of different algorithms.
Consequently, some works (Zhao et al., 2023a; Liu et al., 2023c) have reported
F1 values at fixed false positive rates of 1% and 10%, while others have
reported the optimal F1 score across all potential thresholds to ensure a
fairer comparison (Liu et al., 2023c). In addition, some works employ
hypothesis testing methods to calculate the p-value as an important metric for
sucess rate. Different algorithms utilize various hypotheses to compute the
p-value. For example, Kirchenbauer et al. (2023a) involves determining if the
calculated z-score exceeds a certain threshold, while (Kuditipudi et al.,
2023) hypothesized that the key generating the watermark text has a higher
probability of detecting the watermark compared to other randomly selected
keys. This method (Kuditipudi et al., 2023) does not require a predefined
threshold but necessitates multiple runs of the detection algorithm, which
could slow down the detection speed.

####  5.1.2. Multi-bit Watermark

For multi-bit watermarking methods (Wang et al., 2023b; Rizzo et al., 2016;
Abdelnabi and Fritz, 2021; Yang et al., 2022; Yoo et al., 2023b, b, a), they
not only detect the presence of a watermark but also extract more detailed
watermark information. For instance, a watermarked text might convey specific
data like This text is generated by GPT-4 on June 6 by the Administrator (Wang
et al., 2023b). When evaluating the success rate of multi-bit watermarks, it
is crucial not only to assess their accuracy in extracting watermark
information but also to consider the payload of the watermark, which refers to
the number of bits in the watermark information.

Assume that a piece of watermark information, $w$, can be represented using
$n$ bits, denoted as $w=b_{1}b_{2}…b_{n}$, where each $b_{i}$ can take a value
of 0 or 1. In this context, the most commonly used metric for assessing
success rate is the bit error rate (BER) (Yoo et al., 2023b), which is the
probability of incorrectly predicting each bit during detection, or the bit
accuracy (Yoo et al., 2023a; Abdelnabi and Fritz, 2021), which is the rate of
correctly predicting each bit. These are two complementary metrics. Typically,
the calculation of the bit error rate is conducted under a fixed bit number,
and as the bit number increases, the bit error rate also tends to increase,
eventually approaching 50% (random).

Therefore, the bit capacity of a watermark algorithm has become an important
evaluation criterion, commonly referred to as payload (Yang et al., 2022),
Bits Per Watermark (BPW) (Yang et al., 2022; Yoo et al., 2023b), or code rate
(Wang et al., 2023b; Rizzo et al., 2016). The payload can be calculated by
dividing the total number of bits in the watermark information by the number
of tokens. For a watermark algorithm, there is an upper limit to its payload,
and enhancing the payload typically comes at the cost of either reduced text
quality (section 5.2) or decreased robustness (section 5.3). Additionally, the
value of the payload is contingent on the textual context; in scenarios with
higher entropy, the payload tends to be higher, whereas in lower entropy
scenarios, the payload is usually lower.

###  5.2. Text Quality

In section 2, we demonstrated that an essential characteristic of text
watermarking technology is its low-impact on text quality. This means that the
quality scores of texts, with or without watermarks, should be similar under
the text quality evaluation function $\mathcal{R}$ as described in Equation 2.
This section primarily introduces potential forms of the text quality
evaluation function $\mathcal{R}$. Current text watermarking research
predominantly assesses text quality using methods like perplexity values (Yang
et al., 2023; Kirchenbauer et al., 2023a; Hu et al., 2023; Wu et al., 2023;
Wang et al., 2023b; Zhao et al., 2023a; Liu et al., 2023c, b), semantic score
(Munyer and Zhong, 2023; Yoo et al., 2023b; Yang et al., 2022, 2023; Abdelnabi
and Fritz, 2021; Zhang et al., 2023a), performance evaluations for specific
tasks (Topkara et al., 2006a; Zhang et al., 2023a; Hu et al., 2023; Wu et al.,
2023; Yang et al., 2023; Lee et al., 2023; Sun et al., 2023), or text
diversity (Kirchenbauer et al., 2023b).

####  5.2.1. Perplexity

Perplexity (PPL) is defined as the exponentiated average negative log-
likelihood of a sequence. Specifically, given a text $W={w_{1},...,w_{N}}$,
the PPL can be computed using an LLM $\mathcal{M}$:

(12)
$\mathcal{R}_{\text{PPL}}(W)=\exp\left(-\frac{1}{N}\sum_{i=1}^{N}\log\mathcal{M}(w_{i}|w_{1},\ldots,w_{i-1})\right).$

Perplexity is an effective metric for assessing the consistency and fluency of
text. Generally, a lower PPL indicates higher text quality. Typically, larger
LLMs are employed to compute PPL for more accurate assessments, examples of
which include GPT2(Yang et al., 2023), GPT-3 (Zhao et al., 2023a), OPT2.7B
(Kirchenbauer et al., 2023a; Wang et al., 2023b), LLaMA-13B (Liu et al.,
2023c, b), among others.

The perplexity of watermarked text is generally higher than that of non-
watermarked text, indicating a slight decrease in text quality. Generally, the
impact of watermarking algorithms on text quality is correlated with the
strength of the watermark. The higher the watermark strength, the more evident
the decline in text quality. For instance, in the KGW algorithm (Kirchenbauer
et al., 2023a), a higher value of $\delta$ results in greater impact on text
quality. Takezawa et al. (2023) suggest that for longer texts, a weaker
watermark strength can be employed to minimize the effect on text quality
while maintaining the effectiveness of the watermark.

####  5.2.2. Semantic Score

Although text perplexity facilitates the evaluation of textual consistency and
fluency, it could not assess the accuracy of watermarked texts, specifically
in terms of semantic consistency between watermarked and un-watermarked text.
Consequently, some studies employ semantic scores, which measure the semantic
similarity between watermarked and non-watermarked texts, to evaluate the
impact of watermarking algorithms on text quality.

The most commonly utilized method for assessing semantic scores involves the
computation of semantic embeddings by Large Language Models (LLMs), followed
by the comparison of these embeddings using cosine similarity. This process
can be represented by the following formula:

(13)
$\mathcal{R}_{\text{se}}(W_{u},W_{w})=\frac{\mathcal{M}(W_{u})\cdot\mathcal{M}(W_{w)}}{\|\mathcal{M}(W_{u})\|\times\|\mathcal{M}(W_{w})\|},$

where $W_{u}$ and $W_{w}$ respectively represent the text without watermark
and the text with watermark. The model $\mathcal{M}$ is typically an LLM that
has been optimized specifically for text similarity. For instance, Munyer and
Zhong (2023) have used the Universal Sentence Encoder (Cer et al., 2018),
whereas Yoo et al. (2023b); Abdelnabi and Fritz (2021); Yang et al. (2022)
have employed Sentence-BERT (Reimers and Gurevych, 2019), and Yang et al.
(2023) have utilized all-MiniLM-L6-v2 111https://huggingface.co/sentence-
transformers/all-MiniLM-L6-v2. Most watermarking algorithms could achieve a
semantic similarity between the watermarked text and the original text
(without watermark) above 0.9. Additionally, the achievable semantic scores in
these works are still correlated with the watermark strength (degree of
textual modification), indicating that lower watermark strength correlates
with higher semantic scores.

While the text embedding based evaluation method could effectively captures
the overall semantic similarity, it falls short in delving into the semantic
nuances at a detailed level. Consequently, Yoo et al. (2023b) have further
employed RoBERTa-Large-NLI (Reimers and Gurevych, 2019) for a more precise
understanding and inference of complex semantic relations between texts
(Entailment Score, ES). RoBERTa-Large-NLI is pre-trained on Natural Language
Inference (NLI) tasks and focuses not only on the overall similarity between
two texts but also discerns subtle semantic differences. In actual
experiments, the ES values generally tend to be lower than text embedding
similarities.

Although semantic scores assessment based on Natural Language Inference (NLI)
offers an in-depth semantic analysis, it might still fall short in accurately
capturing variations at the level of individual words or phrases. To address
this, Zhang et al. (2023a) employed BERT-Score (Zhang et al., 2019) for a
word-level detailed comparison of texts. BERT-Score is more adept at
evaluating whether the watermark has altered specific vocabulary or
expressions in the original text.

####  5.2.3. Task-specified Evaluation

Although the assessment method based on semantic scores could effectively
evaluate whether adding watermarks alters the text semantics, its impact on
real-world applications remains unclear. Consequently, many studies are now
focusing on exploring the effects of watermarking algorithms on specific
downstream tasks to assess their impact on text quality. These specific
downstream tasks include machine translation (Topkara et al., 2006a; Hu et
al., 2023; Wu et al., 2023; Zhao et al., 2023b), sentiment classification
(Yang et al., 2023), knowledge understanding (Tu et al., 2023), code
generation (Lee et al., 2023; Sun et al., 2023; Tu et al., 2023), text
summarization (Hu et al., 2023; Wu et al., 2023; Tu et al., 2023), story
generation (Zhao et al., 2023b), question answering (Tu et al., 2023) and
instruction following (Tu et al., 2023), as illustrated in Figure 6.

Machine Translation. Typically, only watermarking Large Language Models
(Section 4) incorporate machine translation as a downstream task for testing
text quality. Specifically, the evaluation involves comparing the translation
outcomes between a watermarked LLM and the original unwatermarked LLM. This
comparison is conducted using the BLEU score, a widely used metric in machine
translation. For the choice of translation LLMs, (Hu et al., 2023; Wu et al.,
2023) employed the Multilingual BART (Liu et al., 2020), while Takezawa et al.
(2023) utilized the NLLB-200 model (Costa-jussà et al., 2022). The translation
data typically employed is the WMT14 dataset, where the translations between
French, German, and English are the most commonly utilized settings. Most
watermarking approaches for LLMs result in a slight decrease in BLEU scores
(Kirchenbauer et al., 2023a; Takezawa et al., 2023; Liu et al., 2023b).
However, the unbiased watermark methods (Hu et al., 2023; Wu et al., 2023)
exhibit almost no decline in BLEU values, demonstrating the superiority of
unbiased watermarking.

Sentiment Classification. Using sentiment classification as a downstream task
can validate whether text watermarking algorithms can affect the sentiment
distribution, i.e., whether the text can maintain its original sentiment
(e.g., positive or negative) after the insertion of a watermark. Yang et al.
(2023) analyzed the sentiment distribution of texts with and without
watermarks using the Twitter-XLM-RoBERTa-Base-Sentiment
222https://huggingface.co/cardiffnlp/twitter-xlm-roberta-base-sentiment model.
Different sentiments generally have clear differences, making it easy for
watermark algorithms to maintain sentiment distribution.

Knowledge Understanding. To explore the performance of the watermark for LLMs
algorithm in tasks with shorter output lengths, Tu et al. (2023) proposed
testing on Knowledge Understanding tasks. Specifically, this involves two
scenarios: Knowledge Probing, using the KoLA dataset (Yu et al., 2023) for
assessing factual recall in LLMs, and Concept Probing, employing the Copen
dataset (Peng et al., 2022) for evaluating conceptual understanding. The
typical evaluation metric for these tasks is the F1 score. In practical tests,
applying watermarks to Knowledge Understanding tasks significantly decreases
the F1 scores across all algorithms, indicating the challenging nature of this
scenario.

Code Generation. Text watermarking for code generation is an important
application, which could test the impact of watermarking on code
functionality. Code evaluation could use unit test metrics like pass@k (Kulal
et al., 2019), or matching metrics such as BLEU and Exact match. Sun et al.
(2023) inserted watermark features into a subset of a dataset to achieve code
dataset watermarking. They showed negligible differences in BLEU and exact
match scores between models trained on datasets with and without watermarks.
However, embedding watermarks into individual code is more challenging than
watermarking an entire dataset. Lee et al. (2023) added watermarks to large
models for code generation, leading to a nearly 10% performance decline in
pass@100 and pass@80 metrics. Given that even minor modifications can disrupt
code functionality, and considering code’s inherently low entropy, the code
generation task presents a highly challenging downstream task for text quality
test (Tu et al., 2023).

Text Summarization. Similar to machine translation scenarios, only the
watermark algorithms for LLM consider text summarization as a downstream
evaluation task. Specifically, it compares the effectiveness of text
summarization between a watermarked Large Language Model (LLM) and an
unwatermarked LLM. The common evaluation metric for text summarization is
ROUGE (Lin, 2004). Furthermore, the most frequently used large model for
summarization is BART-Large (Liu et al., 2020), with the CNN-DM dataset
(Hermann et al., 2015) being prevalent. In practical results, current
watermark algorithms have a relatively minimal impact on text summarization
tasks. The algorithm by Kirchenbauer et al. (2023a). only causes a slight
decrease in ROUGE scores, whereas the unbiased watermark (Hu et al., 2023; Wu
et al., 2023)algorithm hardly affects the ROUGE scores.

Story Generation. Similar to text summarization tasks, story generation also
presents a suitable scenario for evaluating watermark algorithms for Large
Language Models. Tests in the story generation context typically involve
inputting the first half of a story and having the model (LLM) predict its
ending. The ROCstories dataset (Mostafazadeh et al., 2016) is commonly used,
with ROUGE as the evaluation metric. According to the experiments by Zhao et
al. (2023b), current watermark algorithms still cause a 1%-2% decrease in
performance on ROUGE scores. Furthermore, minimal research has been conducted
on story generation performance, indicating potential for future exploration.

Question Answering. Question answering (QA) is an important downstream
application of Large Language Models, and testing watermark algorithms for
LLMs on this task is equally crucial. Tu et al. (2023) conducted tests on
three different QA tasks, specifically: the ELI5 dataset (Fan et al., 2019)
for long-form QA tasks, the FinQA dataset (Maia et al., 2018) for Finance QA
tasks, and the HotpotQA dataset (Yang et al., 2018) for multi-hop reasoning QA
tasks. For the long-form QA and Finance QA tasks, the Rouge-L metric was used
for evaluation, while the F1 score was utilized for the multi-hop reasoning QA
task. Experimental results revealed that, after the introduction of
watermarks, all current watermark algorithms experienced a performance decline
of about 50% in Question Answering tasks, indicating the challenging nature of
watermark algorithms in the context of Question Answering.

Instruction Following. The instruction following ability of Large Language
Models has recently become an especially important aspect to assess,
reflecting whether LLMs can accurately follow user instructions to generate
output in open-ended situations. Tu et al. (2023) tested the impact of the
current watermark for LLMs algorithm on the Instruction Following task using
the AlpacaFarm dataset (Dubois et al., 2023). The evaluation method adopted
was GPT4-Judge (Zheng et al., 2023), where the GPT-4 model judges which
output, between the watermarked LLM and Davinci-003, is better in response to
a given instruction. Under this metric, both Llama2-7B-chat and Internlm-7B-8k
models showed over a 90% decline in performance with watermark, indicating
that instruction following presents a particularly challenging scenario for
watermark algorithms.

Figure 6. Specific downstream tasks used to evaluate the impact of text
watermarking algorithms on text quality.

####  5.2.4. Output Diversity.

Although previous text quality assessment methods provide comprehensive
evaluations of consistency, fluency, and accuracy, they still overlook an
essential aspect: assessing the diversity of watermarked texts. Diversity
evaluation is often targeted at the watermark algorithms for Large Language
Models, since these algorithms involve embedding watermarks into LLMs,
necessitating an assessment of whether the diversity of the text generated by
the watermarked LLMs has changed. Text diversity is defined by calculating the
proportion of unique n-grams in a text sequence, with the formula being the
negative logarithm multiplied by the product of (1 - proportion) of unique
n-grams from 1 to N. A higher diversity score indicates fewer repeated n-grams
and richer text. The specific formula is defined as follows:

(14) $\mathcal{R}_{d}=-\log\left(1-\prod_{n=1}^{N}(1-u_{n})\right),$

where $u_{n}$ represents the ratio of different n-grams to the total number of
n-grams in a given text sequence. If a sequence contains many non-repeating
n-grams, $u_{n}$ will be close to 1, indicating high diversity. Conversely, if
many n-grams are repeated, $u_{n}$ will be small, indicating low diversity.

In the work Kirchenbauer et al. (2023b), it was discovered that for the KGW
watermarking algorithm (Kirchenbauer et al., 2023a), the context width (i.e.,
the number of tokens used on the left to hash and generate the green list) has
the most significant impact on text diversity. A larger context width enhances
the diversity of the text, but this comes at the cost of reduced robustness of
the watermark to text modifications. Furthermore, with a larger context width,
as the watermark strength increases, so does the diversity. Conversely, with a
smaller context width, an increase in watermark strength leads to a decrease
in diversity. Currently, only a few studies on watermarking for Large Language
Models have assessed its impact on text diversity. We suggest that future work
could focus more on evaluating the effect of watermarking on diversity.

###  5.3. Robustness

In the context of text watermarking, a crucial evaluation metric is its
robustness against watermark removal attacks. A watermark removal attack
refers to the process of altering watermarked text in an attempt to erase the
embedded watermark. If a watermarked text still has a high probability of
being detected following a Watermark Removal Attack, then the text
watermarking algorithm is considered highly robust.

Current assumptions for watermark removal attacks are based on black-box
access to the watermarking algorithm, meaning the method of watermark
generation is unknown and there is no access to the watermark detector during
the attack. This is primarily because, under white-box access, potent
watermark removal attack algorithms can be easily developed to remove most
watermarks, as mentioned by (Kirchenbauer et al., 2023b) in their anti-
watermark schema. This represents a limitation of all current watermarking
algorithms. Although it is possible that watermarks may not withstand
watermark removal attacks under white-box access, exploring these
possibilities or designing robust watermark algorithms under white-box
settings remains a direction for future research.

Under the premise of black-box access, numerous watermark removal attacks have
been developed to erase the watermark by modifying watermarked text. Based on
the granularity of textual modifications, we categorize these methods into
character-level attacks, word-level attacks, and document-level attacks. In
the following part of this section, we will discuss the implementation of
these attacks and the robustness of current text watermarking methods against
them.

####  5.3.1. Character-level Attack.

Modifying characters in text without altering any actual words is a relatively
straightforward method of watermark removal attack. One approach involves
directly perturbing certain characters to create spelling errors. However,
this method is easily detectable and can compromise the quality of the text.
An alternative strategy involves replacing characters with visually similar
Unicode IDs, leveraging the fact that many Unicode IDs correspond to identical
or visually indistinguishable characters. This technique is also known as a
Homoglyph attack (Gabrilovich and Gontmakher, 2002). Although such methods are
difficult to detect by human observation, they can still be mitigated by
various canonicalization techniques. Therefore, normalization preprocessing
before passing through watermark detectors is crucial.

The effectiveness of character-level attacks varies with different types of
text watermark algorithms. For Format-based watermark algorithms, which embed
watermarks through Unicode ID substitutions (e.g., EasyMark (Sato et al.,
2023) replaces Unicode 0x0020 with 0x2004), Homoglyph attacks may be a direct
and effective method for watermark removal. For other watermark algorithms,
the impact is on tokenizers; after character modification, the tokenizer may
divide the word into a different token list. For instance, changing the "a" in
"apple" to a Cyrillic character "а" alters the tokenization from ["apple"] to
["а", "pple"]. This change in tokenization result poses challenges to the
detection effectiveness of many watermark algorithms.

The advantage of a character-level attack is its simplicity and effectiveness.
However, its drawback is that it is easily detectable or can be eliminated by
some simply designed algorithms. Therefore, it is not a reliable watermark
removal attack in all scenarios.

####  5.3.2. Word-level Attack.

Compared to character-level attacks that only alter the surface of text, word-
level attacks modify the content of the text by adding, deleting, or altering
words to remove watermarks (Abdelnabi and Fritz, 2021; Yoo et al., 2023b;
Kirchenbauer et al., 2023a; Zhao et al., 2023a; Kuditipudi et al., 2023; Yang
et al., 2023). These methods have a broader scope than character-level
attacks, as they are less likely to be mitigated by rule-based methods and
align more closely with realistic attack scenarios. Currently, there are two
main types of word-level attacks.

Word-level Attack to Existing Text. Word-level attack to existing text refers
to the insertion, deletion, or replacement of words in a pre-generated
watermarked text. During the attack process, an attack rate is typically
established, which is a certain likelihood of inserting, deleting, or
replacing each token. For example, when the deletion attack rate is set as
0.5, nearly half of the text will be removed (Yang et al., 2023). In terms of
word substitution, synonym replacement is typically employed to ensure minimal
impact on the semantics. Specifically, the replacement word will be the one
from the word database giving the smallest sentence score difference, for
example, BERT score difference.

For the two types of watermark methods: watermarking for existing text and
watermarking for Large Language Models (LLMs), the effects produced by word-
level attacks vary. Regarding watermarking for existing text (Abdelnabi and
Fritz, 2021; Yoo et al., 2023b; Yang et al., 2023), word deletion has the most
effect in removing text watermark among the above three attacks. While low
deletion rate under 0.1 produces acceptable performance drop, the figure
exceeding 0.3 or more could result in the watermark severely damaged or even
erased (Yang et al., 2023). Word deletion stands out for two key reasons. The
first is that it can directly remove words that may contain embedded watermark
information, whereas word insertion not directly delete existing watermark
information and not all words have suitable synonyms during synonyms
substitution. Secondly, word deletion significantly alters the semantics,
surpassing both word insertion and synonym replacement, as these methods do
not remove the original semantics.

Regarding watermarking during logits generaion methods (section 4.2), the
basic attack effect is that the watermarked tokens (e.g. green tokens in
Kirchenbauer et al. (2023a)) in the text will be disturbed. For zero-bit
algorithms (Kirchenbauer et al., 2023a; Zhao et al., 2023a; Liu et al., 2023b,
c), insertion or replacement of non-watermarked tokens as well as deletion of
watermarked tokens result in decreased proportion of watermarked token in the
detected text. Consequently, the detector whose result relies on calculating
the ratio of watermarked tokens will output lower detection scores, causing
more false negative cases (Christ et al., 2023; Kuditipudi et al., 2023;
Kirchenbauer et al., 2023a; Zhao et al., 2023a). For multi-bit algorithms
(Wang et al., 2023b; Yoo et al., 2023a), disturbance of the tokens in a text
part originally embedded with a message will result in wrongly decoded message
(Wang et al., 2023b; Yoo et al., 2023a; Abdelnabi and Fritz, 2021; Yoo et al.,
2023b). That is because the decoding process is to choose the message with the
highest probability among all the candidates. In that case, altering one or
more words in a text fragment could cause the decoding probability to shift to
an unintended one. For algorithms like (Kirchenbauer et al., 2023a; Zhao et
al., 2023a; Wang et al., 2023b), there is extra effect because these
algorithms rely on preceding tokens to embed watermark and decode watermark.
Even though an original watermarked token survived all three editing attacks,
the changed surrounding would cause detection computation problems on that
token, and eventually lead to failed watermark decoding on such tokens
(Kirchenbauer et al., 2023a).

Usually, to achieve significant performance drop, sustainable word-level
attacks on the text is required. That is, the attack rate should be large
enough. For example, to decrease detection F1 score below 80%, a minimal
attack rate of 30% is required, which requires performing deletion or
replacement every 3 words (Yang et al., 2023). The main problems brought by a
large attack rate are the totally different semantics and noticeably degraded
text quality (Abdelnabi and Fritz, 2021; Kirchenbauer et al., 2023a; Yang et
al., 2023). Word deletion with high attack rate may even leave each sentence
incomplete. Often, the text under such heavy word-level attacks is not ideal
in real world, where the watermark-removed text should still be usable and
understandable.

In conclusion, although word-level attacks on existing watermarked texts
perform well in some scenarios (Yoo et al., 2023b), they may not best simulate
reality as exhibited by obvious quality issues due to lack of text
understanding ability.

Word-level Attack during Text Generation. Due to the inevitable impact on text
quality during word-level attack to existing texts, particularly when these
modifications are extensive, recent work has begun to explore word-level
attacks during the text generation phase. These methods primarily targets on
watermarking for LLMs. A notable example is the emoji attack (Goodside, 2023),
which prompts the LLM to generate emojis between each token and then remove
the emojis after generation. This attack is effective when watermark embedding
process depends on the preceding token. After the emojis are removed, detector
would fail to recognize the watermarked tokens as emojis are supposed to carry
the watermarking information of a subsequent token (Kirchenbauer et al.,
2023a) (Sun et al., 2023). For example, a user could request the LLM to
generate "smile" between every word, resulting in a sentence looking like
"There smile are smile some smile apples smile here". Assuming the word
"apples" is watermarked, and the proper detection computation of this word
needs its prefix, the emoji "smile". However, the user will remove the emojis
before using this machine-generated text, making the prefix of "apples" become
the word "some". Detection using a different prefix will be inaccurate, and
such miscalculation is applied in every word of the watermarked text.

The advantage of such attacks is their near-complete erasure of certain
watermarking methods (Kirchenbauer et al., 2023a; Christ et al., 2023).
However, they have two main disadvantages. Firstly, they depend heavily on the
strong adherence ability of Large Language Models to follow instructions.
Powerful LLMs like ChatGPT and Claude can effectively execute emoji attacks,
ensuring quality text output, but less capable LLMs may fail to follow
instructions, leading to unreasonable text generation. Kirchenbauer et al.
(2023a) proposed a solution to include such prompts during LLM fine-tuning so
that LLM could be taught to reject such requests from users. However, the
efficacy of such fine-tuning is not guaranteed and may potentially diminish
the capabilities of Large Language Models. Secondly, the success of these
attack methods is strongly linked to the watermark generation process. For
instance, the emoji attack assumes that the current token’s watermark status
(whether it belongs to the "green list) is dependent on the hash value of the
previous token. However, methods like those proposed by (Liu et al., 2023c),
which do not rely on the preceding token’s hash value but use the embedding of
generated text to determine the watermark status, are minimally affected by
the emoji attack.

####  5.3.3. Document-level Attack.

Although word-level attack could modify individual words to alter the remove
the text watermark, their scope and depth of impact are relatively limited. In
contrast, document-level attack employ a more comprehensive and profound
approach. These attacks go beyond mere word modifications in a document,
encompassing broader adjustments to the entire content and structure of the
document. Common document-level attacks include semantic-preserving rewrites,
also known as rewrite attacks, and the insertion of watermark text into
existing human text, termed copy-paste attacks.

Rewrite Attack. The rewrite attack offers comprehensive and in-depth
modifications to text, yet its implementation is more challenging compared to
the word-level approach. Early methods of rewrite attacks often employed a re-
translation strategy (Yang et al., 2023), which involves translating the text
into another language and then back into the original language. This method
exploits subtle changes that may occur during the translation process to
achieve text rewriting. While the re-translation method was widely used
initially, it has a drawback: the double translation can introduce additional
errors, leading to significant semantic deviations from the original text.
Consequently, specialized language models for text rewriting, such as Dipper
(Krishna et al., 2023), have been developed. These models provide higher
quality text and allow for configurable degrees of modification during the
rewriting process. With the recent popularity of ChatGPT, many studies and
practices have started using it for text rewriting, most commonly the
gpt-3.5-Turbo version. Its advantage lies in requiring only a specific prompt
for the text rewrite attack, such as "please rewrite the following text:". For
more realistic scenario validation, manual rewriting is also an option. Manual
rewriting offers more precise semantic preservation and more natural language
expression but has the main disadvantage of being costlier, especially when
handling large amount of text.

The effectiveness of rewrite attacks varies for different types of
watermarking methods. For format-based watermarking approaches (Brassil et
al., 1995; Sato et al., 2023; Por et al., 2012; Rizzo et al., 2016), rewrite
attack is disastrous as any homoglyph will be replaced to the standard
language used by the LLM or human in the output. For other algorithms that
embed watermarks based on text content, the impact of rewrite attacks is
uncertain and may depend on three factors: whether the watermark detection is
related to the sequence of tokens, the strength of watermark implantation
(i.e., the extent of text modification), and the length of the text. Since
rewrite attack could easily disrupt the order of tokens but struggles to
replace all tokens, watermark detection method that do not rely on token
sequences, like the method proposed by Zhao et al. (2023a), tend to be more
robust. Conversely, methods like those of Kuditipudi et al. (2023), where
robustness is affected by token sequence, show different levels of
susceptibility. Additionally, if the watermark text requires significant
modifications from the unwatermarked text, it enhances the robustness against
rewrite attacks. The length of the watermarked text is also crucial.
Experiments by Kirchenbauer et al. (2023a) show that watermarked texts
exceeding 600 tokens are generally robust against all rewrite attacks. It is
noteworthy that for humans, erasing watermarks from texts ranging from 400 to
800 tokens through rewriting is exceptionally challenging.

There are some designs to further increase algorithm robustness against
rewrite attack as well. 1) Decrease the token-level dependency. The dependency
of watermark algorithms on specific contexts can compromise their
effectiveness when the original text is rewritten, as the original context may
not remain intact. Take the watermarking during logits generation methods as
example, if the partitioning of a token’s red-green list relies on $m$
adjacent words, the detection rate significantly decreases after an attack
when $m$ is not very small. Hence, watermark algorithms should reduce reliance
on neighboring words. This can be achieved by decreasing the window size $m$
(Kirchenbauer et al., 2023a), or by using hashing schemes that only involve a
subset of words within the window (Kirchenbauer et al., 2023b). Some studies
have even reduced the window size $m$ to zero (Zhao et al., 2023a). 2) Replace
with semantic-level dependency. A better approach is for the watermark
algorithm to refer to the general semantics around the watermarked token (Liu
et al., 2023c; Yoo et al., 2023b) instead of the exactly identical tokens or
words. That is to say, for a group of altered but semantically similar
contexts, the watermark generator and detector would produce the same result.
Unless the semantics is drastically altered, the watermark detection could
maintain a higher accuracy against rewrite attacks. One can even train the
watermark generator to produce closer results on semantically close texts ; 3)
Increase embedding space for each message. The paraphrasing attack would
change the appearance of a watermarked text fragment and disable accurate
detection in that fragment. If the message is only embedded in one short text
piece, the message would be easily erased if the re-writer considered that
part redundant. Thus, increasing the number or length of text fragments that
are embedded with the same message would intuitively increase the success
extraction rate (Munyer and Zhong, 2023; Wang et al., 2023b).

It is worth noting that although human writers are stronger paraphrasers than
machines. However, there are significant differences in individuals’ ability
to rewrite text, and moreover, when the text is lengthy, humans are often
powerless.

Copy-paste Attack. Copy-paste attack is to surround the target text with
distraction text, which in this context equal to the watermarked and non-
watermarked text respectively. Such attack will result in a much longer text
as compared to the original watermarked text. This attack aims to test if the
low ration setting can cause algorithm effectiveness to drop.

The copy-paste attack primarily diminishes the detectability of watermarks in
text by diluting their concentration. The efficacy of this attack is
significantly influenced by the proportion of watermarked text. For instance,
when the watermarked text constitutes a mere 10% of the total, the attack’s
impact tends to surpass that of most rewriting attacks (Kirchenbauer et al.,
2023b). However, as the share of watermarked text increases to, say, 25%, its
effectiveness in undermining certain watermarking algorithms (Kirchenbauer et
al., 2023a) becomes comparable to that of some rewriting attacks. Similar to
rewriting attacks, lengthening the text can enhance the reliability of
watermark detection, particularly in the context of copy-paste attacks.

However, copy-paste attacks may be identified by certain specific watermark
detection methods. For example, Kirchenbauer et al. (2023b) mentioned a
windowed test to calculate the level of watermarking in a region of the text
instead of the whole text. The idea is to detect watermarked text that is
inserted into an existing text. This should be effective for copy-paste
attack.

###  5.4. Unforgeability

In section 5.3, we discussed watermark removal attacks that assume the
attacker is unaware of the watermark’s generation method (black-box setting).
However, in real-world scenarios, attackers may attempt to obtain or decipher
the watermark’s generation method. Once an attacker acquires this method, they
can easily fabricate or remove existing watermarks, as mentioned by
(Kirchenbauer et al., 2023b) in their anti-watermark methods. Therefore, a
watermark algorithm must possess substantial unforgeability, meaning it should
be exceedingly difficult for attackers to discern the method of watermark
generation. This might imply that the algorithm itself needs to be highly
complex and secure, or involve mathematical problems that are challenging to
crack.

The discussion on watermark unforgeability could be differentiated into two
distinct scenarios: private detection and public detection. In the private
detection scenario, the watermark detection method is kept confidential,
accessible only to specific users or institutions, or indirectly provided to
users via an API (Kirchenbauer et al., 2023a). This setup’s advantage lies in
increasing the difficulty for attackers to obtain and analyze the detection
algorithm, as they lack direct access to the detection mechanism. Conversely,
in the public detection scenario, the watermark detection algorithm is
publicly available, allowing anyone to access and utilize these algorithms.
The benefit of this approach is its transparency and ease of integration,
making it widely applicable in various contexts where authenticity
verification is needed. However, this also implies that attackers can more
easily study the detection algorithms and seek methods to breach the
watermark. Therefore, the requirements for unforgeability in public detection
scenarios might be higher.

####  5.4.1. Unforgeability in Privately Detectable Scenario

In private detection scenarios, the imperceptibility of text watermarking
algorithms is crucial for ensuring unforgeability due to the limited detection
capabilities of users. Imperceptibility refers to the watermark’s impact on
the original content being nearly undetectable in its statistical
distribution, which is essential for ensuring the watermark’s non-forgery. If
users are unaware of the watermark in the text, they cannot forge it.
Therefore, some studies have focused on testing unforgeability. For instance,
Abdelnabi and Fritz (2021) collected texts with and without watermarks and
trained classifiers to try to distinguish between these two categories. The
purpose of this test was to see if the classifiers could effectively identify
which texts contained watermarks. The performance of the classifiers serves as
a measure of the watermarking algorithm’s imperceptibility. Ideally,
classifiers should find it challenging to differentiate between watermarked
and non-watermarked texts. If the classifier cannot accurately differentiate,
this indicates that the watermarking algorithm performs well in terms of
imperceptibility, thereby enhancing its unforgeability.

When text watermarking algorithms fail to achieve complete imperceptibility,
or when attackers suspect or infer the presence of watermarks in the text,
they may resort to statistical methods to extract the watermarking algorithm’s
generation methods. These statistical attack methods primarily rely on the
analysis of statistical traces or patterns that the watermarking algorithm
might leave in the text, which generally requires sufficient prior knowledge
about the method of watermark insertion. For instance, Sadasivan et al. (2023)
proposed a spoofing attack algorithm that can target numerous watermarking
during logits generation methods (Kirchenbauer et al., 2023a; Zhao et al.,
2023a). Specifically, this attack involves calculating the frequency of tokens
in a text under a fixed prefix. In watermarked texts, the frequency of these
tokens may differ from normal texts. For instance, by analyzing the frequency
of tokens following ‘the’, tokens that appear more frequently might be
identified as part of the watermark (green list (Kirchenbauer et al., 2023a)).
The effectiveness of this attack is closely related to the complexity of the
watermarking method. If a watermarking algorithm operates in a complex manner
on a text, statistical-based attacks become less effective. This suggests that
increasing the complexity of watermarking algorithms is key to preventing such
attacks. For example, Liu et al. (2023c) proposed using text semantic
information associated with the watermarking rule, which effectively resists
spoofing attacks.

In the context of private watermark detection scenarios, there are measures
that can enhance the unforgeability of watermark algorithms. Firstly, it is
necessary to limit the detection frequency. When providing watermark detection
services via an API, mechanisms can be designed to restrict this frequency.
This helps prevent attackers from understanding and analyzing the watermark
algorithm through extensive trial and error, thereby reducing the
effectiveness of the previously mentioned spoofing attacks (Sadasivan et al.,
2023). Secondly, bolstering network security is crucial for preventing the
theft of watermark rules. Protecting the API and backend systems from hacker
intrusions includes, but is not limited to, using encrypted communications,
regularly updating security vulnerabilities, and implementing intrusion
detection systems. Thirdly, guarding against social engineering attacks is
essential. Social engineering attacks often manipulate people’s trust or
induce them to disclose information. Establishing strict internal security
protocols and verification processes is vital to prevent unauthorized
information (e.g. the key of watermark) disclosure.

####  5.4.2. Unforgeability in Publicly Detectable Scenario

Evaluating the unforgeability of watermark algorithms under publicly
detectable scenarios is far more challenging, as the detection methods are
open, allowing attackers to more easily attempt to crack or remove the
watermark. In such scenarios, attackers could still employ previously
mentioned statistical attack methods, such as spoofing attacks (Sadasivan et
al., 2023), to analyze and extract the watermark’s generation rules. Since the
detector is public in this case, there might be more data available for such
attacks. Additionally, as watermark generation and detection algorithms are
often closely related, attackers might directly analyze how the watermark
detector is implemented and how the watermark is generated.

Currently, most watermarking algorithms utilize the watermark generator to
discern watermark features in text details, thereby exposing the watermark
generator. For example, Kirchenbauer et al. (2023a) still requires determining
whether each token is on the green list during the watermark detection
process, which exposes the watermark generation method. Consequently, these
watermarking algorithms lack unforgeability in publicly detectable scenarios.
A text watermarking algorithm with unforgeability must ensure that the
watermark detector does not reveal information about the watermark generator.
For instance, some current methods employ neural networks for watermark
detection (Liu et al., 2023b; Abdelnabi and Fritz, 2021), achieving effective
detection while preventing further information disclosure due to the black-box
nature of neural networks.

For watermark detection algorithms that do not reveal watermark generation
methods, evaluating their unforgeability poses a challenge. Typically, it
necessitates the design of complex attack algorithms to assess their
unforgeability. For instance, Liu et al. (2023b) proposed using reverse
training, where a watermark generator is trained inversely based on the
watermark detector. The consistency between the trained and the actual
watermark generator is used to evaluate unforgeability. However, this approach
also requires the attacker to have prior knowledge of the watermark
generator’s architecture. If the attacker is unaware of the watermark
generator’s implementation, the attack becomes extremely difficult. Overall, a
greater variety of attacks need to be developed to effectively test
unforgeability.

##  6\. Application for Text Watermarking

In the previous sections, we have comprehensively detailed the implementation
methods of text watermarking technologies in the era of large models and how
to thoroughly test these watermarking technologies. This section continues to
discuss the application of text watermarking technologies in real-world
scenarios. Specifically, we will primarily focus on the application of text
watermarking technologies in three key areas: copyright protection (Zhao et
al., 2023b, 2022; He et al., 2022a, b; Peng et al., 2023; Li et al., 2023;
Tang et al., [n. d.]; Chu et al., 2023; Tang et al., 2023; Sun et al., 2023;
Wang et al., 2023a; Taleby Ahvanooey et al., 2018; Mir, 2014; Iqbal et al.,
2019), fake news detection (Megías et al., 2021, 2022), and academic integrity
(Vasilatos et al., 2023; Zhao et al., 2022; Perkins, 2023). Firstly, we will
discuss how to protect the copyright of large models and text/data sets using
text watermarking technology to prevent infringement and misuse of
intellectual property. Secondly, the article will explore the role of this
technology in identifying and combating the spread of false information,
particularly in the current domains of social media and news dissemination.
Lastly, we delve into the significance of text watermarking technology in
maintaining academic integrity, including its use in plagiarism detection and
ensuring the originality of academic works. Meanwhile, we also provide a more
illustrative depiction of the different applications of text watermarking in
Figure 7.

Figure 7. This figure displays three major application scenarios of text
watermarking: copyright protection (section 6.1), academic integrity (section
6.2), and fake news detection (section 6.3).

###  6.1. Copyright Protection

####  6.1.1. Text/Dataset Copyright

In the digital era, the protection of copyrights for texts and datasets is
particularly crucial. As data sharing and utilization increase, safeguarding
these assets from illegal replication and misuse becomes paramount. Text
watermarking technology plays a key role in this regard, embedding
imperceptible markers within texts and datasets to help preserve intellectual
property rights.

Text copyright refers to the legal protection of original textual content,
such as writings and online posts, ensuring unique rights for the creators.
Copyrighted texts should provide sufficient information to identify their
creators and sources. This protection extends beyond traditional publications
like books and journals to digital-era web articles, blog posts, and other
online contents. Current explorations in textual copyright primarily focus on
format-based watermarking algorithms (section 3.1). The main reason is that
only format-based watermarking does not require modifications to the text
content, whereas other watermarking techniques necessitate changes, which may
be unacceptable to some content creators.

For instance, Taleby Ahvanooey et al. (2018) utilizes layout features (e.g.,
spacing between words and lines) and formatting (e.g., text color, font, and
height) to embed watermarks in the text. To enhance the protection of text
copyrights in web content, Mir (2014) proposed an invisible digital watermark
based on the textual information contained in web pages. This watermark
utilizes predefined semantic and syntactic rules, which are encrypted and
transformed into spaces using binary control characters, then embedded within
the webpage. The watermark is embedded using the structure of HTML (Hypertext
Markup Language) as a cover file. Moreover, for certain specific text formats,
distinct watermark designs may be applied. For instance, Iqbal et al. (2019)
have focused on embedding watermarks in MS-Word documents by utilizing unique
attributes like variables, bookmarks, and ranges for copyright protection.

Although current text copyright protection methods predominantly use format-
based watermarking, the advancement of large language models suggests that
applying watermark algorithms with large language models to text copyright
protection is an important direction for future research.

With the rise and widespread application of deep learning technology, the
dataset copyright has become particularly important, which means protecting
datasets from unauthorized use has emerged as a crucial issue. In the realm of
dataset copyright protection, text watermarking technology plays a pivotal
role. By adding watermarks to some data within a dataset, a watermarked
dataset is created. Models trained on this watermarked dataset will possess
detectable characteristics that prevent unauthorized use.

The method of adding watermarks to datasets for copyright protection is almost
identical to the training time watermarking method mentioned in Section 4.1.
Specifically, the dataset watermarking method involves adding a trigger to
some of the text in the dataset. This trigger, a specific input feature, is
associated with a particular output in the dataset, ensuring that models
trained with this dataset produce the corresponding output feature when
encountering the trigger. This trigger can be implemented by modifying labels.
For instance, Liu et al. (2023a) altered the labels corresponding to text in a
text classification dataset. Sun et al. (2022) disrupted code in a code
generation dataset. However, this approach turns the corresponding data into
noise data, potentially affecting the quality of the dataset. Therefore,
finding unique inputs to add as features is an effective method. For example,
Tang et al. (2023) first used adversarial learning to identify data prone to
misclassification, then added triggers to this data. Sun et al. (2023) added
semantically invariant transformations to code to incorporate triggers. These
watermarking techniques effectively protect the copyright of datasets.
However, there is still a lack of exploration into the copyright protection of
datasets when only a small portion of the training data consists of
watermarked datasets, which could be a significant direction for future
research.

####  6.1.2. LLM Copyright

In the domain of copyright protection for large language models (LLMs), the
primary objective is to safeguard these models from threats known as
extraction attacks. These attacks involve extracting substantial amounts of
data from large language models to train a new model. To protect LLM
copyrights, a common method is to embed watermarks in the LLM’s output. This
results in attackers using datasets with watermarks for training, leading to
the new model’s outputs also bearing watermark characteristics. This process
bears some resemblance to dataset copyright, except that in this case, the
watermarked dataset is generated by a LLM. Current efforts have developed
watermark algorithms for various LLM types, including embedding (Peng et al.,
2023), generative (He et al., 2022a, b; Zhao et al., 2023b), and
classification (Zhao et al., 2022) LLMs. The input of an embedding LLM is
text, and its output is the corresponding embedding of that text. The
generative LLM is currently the most commonly used LLM, with both its input
and output being text. In the case of a classification LLM, the input is text,
and the output is a specific category.

Peng et al. (2023) have developed a watermarking algorithm designed to protect
embedding LLMs. This algorithm initially involves the creation of a trigger
set. When the input contains a trigger from this set, the algorithm introduces
a poison weight into the output embedding. The ‘trigger’ mentioned here is
conceptually identical to that referenced in the context of dataset copyright
in section 6.1.1. The new embedding model, trained with watermarked data,
produces embeddings with poison weights when encountering inputs containing
triggers, thereby enabling detection.

For generative LLMs, He et al. (2022a) implemented a method of embedding
watermarks by substituting synonyms in the text already generated by LLMs.
During this synonym replacement process, certain ‘watermark tokens’ are
preferentially selected. Consequently, models trained with these data tend to
generate a higher proportion of watermark tokens, making them more easily
detectable. However, a limitation of this approach is that the word frequency
of the watermarked data diverges from that of normal text, rendering the
watermark more susceptible to detection and removal. To address this issue, He
et al. (2022b) conducted word substitution based on the context features,
which were derived from part-of-speech and dependency tree analyses. This
method ensures that the frequency of each token remains unchanged. However,
even with this approach, the practice of LLM generating text followed by
synonym substitution is still vulnerable to being circumvented by adversaries
randomly replacing synonyms, thereby rendering this protection ineffective. To
address this issue, Zhao et al. (2023b) adopted the concept of watermarking
during logits generation (section 4.2). They introduced a watermark into the
output logits of the Large Language Model (LLM) by embedding a periodic
signal. Models trained using this watermarked LLM exhibit periodic signal
characteristics in their outputs, making them detectable. This approach offers
more robust and invisible watermarks compared to previous methods.

Similarly, in the case of classification LLMs, Zhao et al. (2022) also adopted
the approach of embedding a watermark by inserting periodic signals into the
logits of the LLM output to enforce copyright protection. Specifically, this
involves introducing periodic signals into the logits corresponding to a
particular category, ensuring that models trained with data output from this
modified model will also contain these periodic signals in the output for that
specific category. However, this method inevitably impacts the quality of the
output data, especially when users extract data using hard-labels (converting
classification results into one-hot outputs) instead of continuous soft-
labels. Future work could explore how to embed watermarks in classification
LLMs with minimal impact on label quality for effective LLM copyright
protection.

###  6.2. Academic Integrity

Academic integrity issues hold particular importance in today’s educational
sphere, especially given the ease of access and use of large language models
(LLMs). Students might exploit these advanced models to complete assignments,
papers, or even participate in exams, presenting new challenges to the upkeep
of academic honesty. In tasks or exams where independent and original
completion by students is required, it becomes necessary to devise methods to
ascertain whether the submitted content is generated by a large language
model.

The current work primarily explores the design of algorithms for automatically
distinguishing text generated by Large Language Models (LLMs) from human-
written text. For instance, Mitchell et al. (2023) developed a GPT-based
classifier, Detect-GPT, aimed at identifying LLM-generated text. However, such
methods lack interpretability and may not be robust to out-of-domain text. To
address this issue, an online text detection tool, GPTZero
333https://gptzero.me/, operates on the assumption that LLM-generated texts
can be differentiated from human texts based on two metrics: perplexity
(Equation 12) and burstiness. Burstiness refers to the degree of uneven
distribution in a text’s length, complexity, or information density.
Similarly, Vasilatos et al. (2023) also employed the perplexity feature to
distinguish between human and machine-generated texts. Nonetheless, detection
methods based on perplexity and burstiness may be circumvented by deliberate
text modifications. Concurrently, the promising technique of text watermarking
remains underexplored in the field of academic integrity, which should become
a significant research direction in the future.

###  6.3. Fake News Detection

The application of large language models has raised two main concerns: the
generation of false information due to their text-generating capabilities, and
the rapid dissemination of such false information. Firstly, the powerful text-
generating capability of LLMs makes them an effective tool for producing fake
information. These models can rapidly generate texts that appear authentic and
accurate, but may actually contain erroneous or misleading information. Owing
to the high credibility and realism of the generated texts, they can be easily
utilized to construct fake news or false narratives, misleading the public and
distorting facts. The second concern is the rapid spread of false information.
Fake information generated by LLMs, due to its high degree of realism, can
spread swiftly on social media and other digital platforms, leading to the
proliferation and reinforcement of incorrect viewpoints (DiResta, 2020; Zhou
et al., 2023). This spread not only amplifies the impact of false information
but can also lead to public confusion and distrust towards authoritative
information sources. Therefore, the automatic identification of news generated
by LLMs is essential.

The current research has explored utilizing watermark technology to detect
fake images and videos generated by AI models, aiding in the identification of
fake news. For instance, a framework named DISSIMILAR(Megías et al., 2021) was
proposed to track and detect false media information by automatically
embedding watermarks in images before their release on social media. However,
there has been minimal exploration in detecting false content generated by
Large Language Models. We propose two potential approaches in this field. The
first involves a method similar to the DISSIMILAR framework, where watermarks
are added to text content before its publication on social media. This
approach would use format-based methods (3.1) to embed watermarks without
altering the text’s content. The second approach necessitates collaboration
with LLM providers, allowing them to embed watermarks and share watermark
detection methods with certain platforms, thereby facilitating the marking of
LLM-generated content. We recommend that future work should leverage text
watermarking technology to aid in the detection of false information.

##  7\. Challenges and Future Directions

Although detailed introductions to the methods, evaluations, and application
scenarios of text watermarking have been provided in previous sections,
numerous challenges remain in this field. These include balancing across
different evaluation perspectives, adapting text watermarking for more
challenging scenarios, developing more comprehensive benchmarks, and
broadening the application of text watermarking. These challenges will be
discussed in detail below.

###  7.1. Balancing Across Different Evaluation Perspectives

In section 5, we explore various perspectives for evaluating text watermarking
algorithms. However, these perspectives often present inherent contradictions,
making it extremely challenging for a text watermarking algorithm to excel in
all evaluation perspectives simultaneously. For instance, achieving a
favorable balance among success rate, text quality, and robustness at a high
payload is difficult. In this section, we will first analyze why these
perspectives are mutually contradictory, and then discuss potential strategies
for achieving a better balance in future work.

####  7.1.1. Why are the Different Perspectives Conflicting?

The fundamental reason for contradictions among different perspectives lies in
the limited suitable text space for text watermarking, usually determined by
the text quality requirements. Specifically, according to Equation 2, the