$$ \newcommand{\bone}{\mathbf{1}} \newcommand{\bbeta}{\mathbf{\beta}} \newcommand{\bdelta}{\mathbf{\delta}} \newcommand{\bepsilon}{\mathbf{\epsilon}} \newcommand{\blambda}{\mathbf{\lambda}} \newcommand{\bomega}{\mathbf{\omega}} \newcommand{\bpi}{\mathbf{\pi}} \newcommand{\bphi}{\mathbf{\phi}} \newcommand{\bvphi}{\mathbf{\varphi}} \newcommand{\bpsi}{\mathbf{\psi}} \newcommand{\bsigma}{\mathbf{\sigma}} \newcommand{\btheta}{\mathbf{\theta}} \newcommand{\btau}{\mathbf{\tau}} \newcommand{\ba}{\mathbf{a}} \newcommand{\bb}{\mathbf{b}} \newcommand{\bc}{\mathbf{c}} \newcommand{\bd}{\mathbf{d}} \newcommand{\be}{\mathbf{e}} \newcommand{\boldf}{\mathbf{f}} \newcommand{\bg}{\mathbf{g}} \newcommand{\bh}{\mathbf{h}} \newcommand{\bi}{\mathbf{i}} \newcommand{\bj}{\mathbf{j}} \newcommand{\bk}{\mathbf{k}} \newcommand{\bell}{\mathbf{\ell}} \newcommand{\bm}{\mathbf{m}} \newcommand{\bn}{\mathbf{n}} \newcommand{\bo}{\mathbf{o}} \newcommand{\bp}{\mathbf{p}} \newcommand{\bq}{\mathbf{q}} \newcommand{\br}{\mathbf{r}} \newcommand{\bs}{\mathbf{s}} \newcommand{\bt}{\mathbf{t}} \newcommand{\bu}{\mathbf{u}} \newcommand{\bv}{\mathbf{v}} \newcommand{\bw}{\mathbf{w}} \newcommand{\bx}{\mathbf{x}} \newcommand{\by}{\mathbf{y}} \newcommand{\bz}{\mathbf{z}} \newcommand{\bA}{\mathbf{A}} \newcommand{\bB}{\mathbf{B}} \newcommand{\bC}{\mathbf{C}} \newcommand{\bD}{\mathbf{D}} \newcommand{\bE}{\mathbf{E}} \newcommand{\bF}{\mathbf{F}} \newcommand{\bG}{\mathbf{G}} \newcommand{\bH}{\mathbf{H}} \newcommand{\bI}{\mathbf{I}} \newcommand{\bJ}{\mathbf{J}} \newcommand{\bK}{\mathbf{K}} \newcommand{\bL}{\mathbf{L}} \newcommand{\bM}{\mathbf{M}} \newcommand{\bN}{\mathbf{N}} \newcommand{\bP}{\mathbf{P}} \newcommand{\bQ}{\mathbf{Q}} \newcommand{\bR}{\mathbf{R}} \newcommand{\bS}{\mathbf{S}} \newcommand{\bT}{\mathbf{T}} \newcommand{\bU}{\mathbf{U}} \newcommand{\bV}{\mathbf{V}} \newcommand{\bW}{\mathbf{W}} \newcommand{\bX}{\mathbf{X}} \newcommand{\bY}{\mathbf{Y}} \newcommand{\bZ}{\mathbf{Z}} \newcommand{\calA}{\mathcal{A}} \newcommand{\calB}{\mathcal{B}} \newcommand{\calC}{\mathcal{C}} \newcommand{\calD}{\mathcal{D}} \newcommand{\calE}{\mathcal{E}} \newcommand{\calF}{\mathcal{F}} \newcommand{\calG}{\mathcal{G}} \newcommand{\calH}{\mathcal{H}} \newcommand{\calI}{\mathcal{I}} \newcommand{\calJ}{\mathcal{J}} \newcommand{\calK}{\mathcal{K}} \newcommand{\calL}{\mathcal{L}} \newcommand{\calM}{\mathcal{M}} \newcommand{\calN}{\mathcal{N}} \newcommand{\calO}{\mathcal{O}} \newcommand{\calP}{\mathcal{P}} \newcommand{\calQ}{\mathcal{Q}} \newcommand{\calR}{\mathcal{R}} \newcommand{\calS}{\mathcal{S}} \newcommand{\calT}{\mathcal{T}} \newcommand{\calU}{\mathcal{U}} \newcommand{\calV}{\mathcal{V}} \newcommand{\calW}{\mathcal{W}} \newcommand{\calX}{\mathcal{X}} \newcommand{\calY}{\mathcal{Y}} \newcommand{\calZ}{\mathcal{Z}} \newcommand{\R}{\mathbb{R}} \newcommand{\C}{\mathbb{C}} \newcommand{\N}{\mathbb{N}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\F}{\mathbb{F}} \newcommand{\Q}{\mathbb{Q}} \DeclareMathOperator*{\argmax}{arg\,max} \DeclareMathOperator*{\argmin}{arg\,min} \newcommand{\nnz}[1]{\mbox{nnz}(#1)} \newcommand{\dotprod}[2]{\langle #1, #2 \rangle} \newcommand{\ignore}[1]{} \let\Pr\relax \DeclareMathOperator*{\Pr}{\mathbf{Pr}} \newcommand{\E}{\mathbb{E}} \DeclareMathOperator*{\Ex}{\mathbf{E}} \DeclareMathOperator*{\Var}{\mathbf{Var}} \DeclareMathOperator*{\Cov}{\mathbf{Cov}} \DeclareMathOperator*{\stddev}{\mathbf{stddev}} \DeclareMathOperator*{\avg}{avg} \DeclareMathOperator{\poly}{poly} \DeclareMathOperator{\polylog}{polylog} \DeclareMathOperator{\size}{size} \DeclareMathOperator{\sgn}{sgn} \DeclareMathOperator{\dist}{dist} \DeclareMathOperator{\vol}{vol} \DeclareMathOperator{\spn}{span} \DeclareMathOperator{\supp}{supp} \DeclareMathOperator{\tr}{tr} \DeclareMathOperator{\Tr}{Tr} \DeclareMathOperator{\codim}{codim} \DeclareMathOperator{\diag}{diag} \newcommand{\PTIME}{\mathsf{P}} \newcommand{\LOGSPACE}{\mathsf{L}} \newcommand{\ZPP}{\mathsf{ZPP}} \newcommand{\RP}{\mathsf{RP}} \newcommand{\BPP}{\mathsf{BPP}} \newcommand{\P}{\mathsf{P}} \newcommand{\NP}{\mathsf{NP}} \newcommand{\TC}{\mathsf{TC}} \newcommand{\AC}{\mathsf{AC}} \newcommand{\SC}{\mathsf{SC}} \newcommand{\SZK}{\mathsf{SZK}} \newcommand{\AM}{\mathsf{AM}} \newcommand{\IP}{\mathsf{IP}} \newcommand{\PSPACE}{\mathsf{PSPACE}} \newcommand{\EXP}{\mathsf{EXP}} \newcommand{\MIP}{\mathsf{MIP}} \newcommand{\NEXP}{\mathsf{NEXP}} \newcommand{\BQP}{\mathsf{BQP}} \newcommand{\distP}{\mathsf{dist\textbf{P}}} \newcommand{\distNP}{\mathsf{dist\textbf{NP}}} \newcommand{\eps}{\epsilon} \newcommand{\lam}{\lambda} \newcommand{\dleta}{\delta} \newcommand{\simga}{\sigma} \newcommand{\vphi}{\varphi} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} \newcommand{\wt}[1]{\widetilde{#1}} \newcommand{\wh}[1]{\widehat{#1}} \newcommand{\ol}[1]{\overline{#1}} \newcommand{\ul}[1]{\underline{#1}} \newcommand{\ot}{\otimes} \newcommand{\zo}{\{0,1\}} \newcommand{\co}{:} %\newcommand{\co}{\colon} \newcommand{\bdry}{\partial} \newcommand{\grad}{\nabla} \newcommand{\transp}{^\intercal} \newcommand{\inv}{^{-1}} \newcommand{\symmdiff}{\triangle} \newcommand{\symdiff}{\symmdiff} \newcommand{\half}{\tfrac{1}{2}} \newcommand{\bbone}{\mathbbm 1} \newcommand{\Id}{\bbone} \newcommand{\SAT}{\mathsf{SAT}} \newcommand{\bcalG}{\boldsymbol{\calG}} \newcommand{\calbG}{\bcalG} \newcommand{\bcalX}{\boldsymbol{\calX}} \newcommand{\calbX}{\bcalX} \newcommand{\bcalY}{\boldsymbol{\calY}} \newcommand{\calbY}{\bcalY} \newcommand{\bcalZ}{\boldsymbol{\calZ}} \newcommand{\calbZ}{\bcalZ} $$

2023

  1. A Watermark for Large Language Models

    John Kirchenbauer, Jonas Geiping, Yuxin Wen, and 3 more authors
    Jan 2023
    arXiv Bib PDF

    Paper Abstract

    Potential harms of large language models can be mitigated by watermarking model output, i.e., embedding signals into generated text that are invisible to humans but algorithmically detectable from a short span of tokens. We propose a watermarking framework for proprietary language models. The watermark can be embedded with negligible impact on text quality, and can be detected using an efficient open-source algorithm without access to the language model API or parameters. The watermark works by selecting a randomized set of "green" tokens before a word is generated, and then softly promoting use of green tokens during sampling. We propose a statistical test for detecting the watermark with interpretable p-values, and derive an information-theoretic framework for analyzing the sensitivity of the watermark. We test the watermark using a multi-billion parameter model from the Open Pretrained Transformer (OPT) family, and discuss robustness and security.

Three Important Things

1. Hard Red List

A key concern with the proliferation of large language models is whether we can detect text generated by such models. This is important in both mitigating the potential harms of LLM-generated output, and to also avoid ingesting machine-generated text for future training of language models.

In this paper, the authors investigate a watermarking strategy for LLM outputs that is imperceptible to humans, but allows for an algorithm to conclude that with high probability it was generated by a machine.

They first introduce a simple strawman solution, known as the Hard Red List:

Note that \(s^{(-N_p)}, \cdots, s^{(-1)}\) refers to the initial prompt of length \(N_p\), and \(s^{(0)}, \cdots, s^{(t-1)}\) refers to the \(t\) tokens that have been generated so far, with the intent to generate token \(s^{(t)}\) now.

To detect the watermark, we simply have to check the number of violations that exist. A violation for token \(i\) occurs if it is in the red list generated by the hash function determined by token \(i-1\). As such, for human-generated text, roughly half of all the tokens will be violations. However, for machine-generated text with this watermarking technique, an adversary will need to modify at least a quarter of all tokens for it to pass. A quarter instead of half is theoretically sufficient, under the assumption that the adversary can choose a value for token \(i\) that is both in the red list determined by token \(i-1\), and also results in token \(i+1\) being in the red list it decides.

Modifying so many tokens will be challenging, because being forced to use tokens in the red list to create additional violations may result in text that is unnatural and with high perplexity.

2. Soft Watermark

However, the previous approach suffers from a major downside: the watermarking algorithm for LLM output itself could also result in text with high perplexity. For instance, the word “Barack” is usually followed by “Obama”, but if “Obama” is in the red list for “Barack”, then the model is forced to choose another word, which results in a weird high-perplexity output.

The authors hence consider an alternative “soft” watermark algorithm. Recall that the last layer of the language model is a linear layer that produces logits that feeds into a softmax gate, which is converted into a probability distribution that is sampled from:

\[p_k^{(t)} = \frac{\exp(l_k^{(t)})} {\sum_i \exp(l_i^{(t)})}\]

Instead of strictly assigning words in the red list to have probability 0, the authors consider a scheme where words in the green list to have their logits boosted by some amount \(\delta\), with words in the red list unchanged.

This gives the following probability distribution for sampling:

\[\hat{p}_k^{(t)}= \begin{cases}\frac{\exp \left(l_k^{(t)}+\delta\right)}{\sum_{i \in R} \exp \left(l_i^{(t)}\right)+\sum_{i \in G} \exp \left(l_i^{(t)}+\delta\right)}, & k \in G \\ \frac{\exp \left(l_k^{(t)}\right)}{\sum_{i \in R} \exp \left(l_i^{(t)}\right)+\sum_{i \in G} \exp \left(l_i^{(t)}+\delta\right)}, & k \in R .\end{cases}\]

This means that now if there is a word that dominates all other words in its probability of being sampled (i.e low-entropy phrases), then the adjustment of \(\delta\) to the green list does not affect much and it will still most likely be sampled.

On the other hand, if there are many equally probable candidates for the next token (i.e high-entropy phrases), then the biasing of the logits by \(\delta\) will have a large effect and result in candidates from the green list being sampled with much higher probability.

The full algorithm for the soft watermark is given below:

Accordingly, the ability to detect watermarks now also depends on the entropy of the text. High-entropy sequences can be detected with a shorter span, whereas low-entropy sequences will require more tokens to be reliably detected.

3. Watermark Attacks

The authors consider a variety of attacks to turn watermarked output into one that passes the watermark detection test.

These, and their mitigations, include:

  1. Paraphrasing attacks: paraphrasing the output, either manually or in an automated fashion. However, both of these approaches fall outside the scope of the threat model considered. Manual paraphrasing is labor-intensive and defeats the point of using LLMs to generate large quantities of (potentially harmful) text. Automated paraphrasing implies the usage of an already sophisticated language model or tool, in which case the attacker can simply generate their own text without having to use the watermarked LLM output.
  2. Discreet alterations: adding whitespace, subtle mispellings. Whitespace attacks can be avoided by having the hashing function ignore whitespace.
  3. Tokenization attacks: in a scheme (such as BPE) with sub-word tokenization, this is changing some text such that subsequent sub-word tokenization changes. This attack is limited in scope due to limited opportunities to exploit sub-word tokenization patterns.
  4. Homoglyph and zero-width attacks: Homoglyph attacks are ones where one unicode character is swapped for another one that is similar-looking but different, such as replacing i with the Cyrillic unicode i character. Zero-width attacks is the insertion of characters that are zero-width whitespace. Homoglyph attacks can be avoided by normalizing characters, and zero-width attacks can be avoided by removing these characters.

  5. Generative attacks: LLMs are capable of in-context learning, meaning that they can learn to perform a new task that does not exist on their training dataset simply by being given a few training examples. If the model is then prompted to modify its output in a deterministic and reversible way, then the modification can be reversed to result in a change in a large number of tokens.

    An example generative attack is the Emoji attack, shown in the figure below:

Most Glaring Deficiency

To be completely honest, this was one of the rare papers where I felt the authors were very comprehensive in addressing all dimensions of their research question or otherwise mentioned them as possible future work. Very good job!

If I had to mention a deficiency, it would be that the motivation for introducing \(\gamma\) in computing their \(z\)-statistic was rather unclear and arbitrary to me. It seemed pertinent as it was a hyperparameter that they experimented with different values for, but an intuitive explanation would have helped.

Conclusions for Future Work

Watermarking LLM-generated outputs can be performed with minimal changes to the underlying model, having only to modify the final logits before sampling. It also does not require any re-training.

However, while such watermark-based approaches are one step towards allowing us to identify LLM-produced text in the wild, they still suffer from the fundamental limitation that it require adversaries to be using LLMs that conform with the watermarking standard. Indeed, given the rising prevalence of highly capable small language models that can run on commodity hardware, motivated adversaries can simply deploy and run their own models that produce text without any watermarks.

Written 2023