A Watermark for Black-Box Language Models

## Abstract

Abstract Watermarking has recently emerged as an effective strategy for detecting the outputs of large language models (LLMs). Most existing schemes require white-box access to the model’s next-token probability distribution, which is typically not accessible to downstream users of an LLM API. In this work, we propose a principled watermarking scheme that requires only the ability to sample sequences from the LLM (i.e. black-box access), boasts a distortion-free property, and can be chained or nested using multiple secret keys. We provide performance guarantees, demonstrate how it can be leveraged when white-box access is available, and show when it can outperform existing white-box schemes via comprehensive experiments.

## 1 Introduction

It can be critical to understand whether a piece of text is generated by a large language model (LLM). For instance, one often wants to know how trustworthy a piece of text is, and those written by an LLM may be deemed untrustworthy as these models can hallucinate. This problem comes in different flavors — one may want to detect whether it was generated by a *specific* model or by *any* model. Furthermore, the detecting party may or may not have white-box access (e.g. an ability to compute log-probabilities) to the generator they wish to test against. Typically, parties that have white-box access are the owners of the model so we refer to this case as *first-party* detection and the counterpart as *third-party* detection.

The goal of watermarking is to cleverly bias the generator so that first-party detection becomes easier. Most proposed techniques do not modify the underlying LLM’s model weights or its training procedure but rather inject the watermark during autoregressive decoding at inference time. They require access to the next-token logits and inject the watermark every step of the sampling loop. This required access prevents third-party users of an LLM from applying their own watermark as proprietary APIs currently do not support this option. Supporting this functionality presents a security risk in addition to significant engineering considerations. Concretely, Carlini et al. () showed that parts of a production language model can be stolen from API access that exposes logits. In this work, we propose a watermarking scheme that gives power back to the people — third-party users can watermark a language model given nothing more than the ability to sample sequences from it. Our scheme is faithful to the underlying language model and it can outperform existing white-box schemes.

## 2 Related Work

Watermarking outside the context of generative LLMs, which is sometimes referred to as linguistic steganography, has a long history and typically involves editing specific words from an non-watermarked text. Watermarking in the modern era of generative models is nascent — Venugopal et al. () devised a scheme for machine translation, but interest in the topic grew substantially after the more recent seminal works of Kirchenbauer et al. (; ) and Aaronson (). Many effective strategies employ some form of pseudorandom functions (PRFs) and cryptographic hashes on token $n$-grams in the input text. Kirchenbauer et al. () proposes modifying the next-token probabilities every step of decoding such that a particular subset of the vocabulary, referred to as *green tokens*, known only to those privy to the secret key, are made more probable. Watermarked text then is expected to have more green tokens than non-watermarked text and can be reliably detected with a statistical test. The scheme distorts the text, but with the right hyperparameters a strong watermark may be embedded with minimal degradation in text quality.

Meanwhile, Aaronson () proposes a clever *distortion-free* strategy which selects the token that is both highly probable and that achieves a high PRF value. Kuditipudi et al. () applies a scheme similar in spirit to Aaronson () but to improve robustness to attacks, pseudorandom numbers (PRNs) are determined by cycling through a fixed, pre-determined sequence of values called the *key*, rather than by $n$-grams. They compute a $p$-value using a permutation test to determine if the text was watermarked with *that specific* key.

Lee et al. () adapts Kirchenbauer et al. ()’s scheme for code-generation by applying the watermark only at decoding steps that have sufficient entropy. Zhao et al. () investigates a special case of Kirchenbauer et al. () for improved robustness to adversarial corruption.
Fernandez et al. () tests various watermarking schemes on classical NLP benchmarks and also introduces new statistical tests for detection — most notably, they suggest skipping duplicate $n$-grams during testing.

Yang et al. () introduces a scheme that relies on black-box access to the LLM. Their method samples from the LLM and injects the watermark by replacing specific words with synonyms. Although their approach shares the assumption of black-box LLM access, as in our work, it has limitations not present in ours: the watermarking process is restricted to words that can easily be substituted with multiple synonyms, synonym generation is powered by a BERT model (Devlin, ), making it computationally expensive, and the scheme is not distortion-free. Chang et al. () presents PostMark, a black-box watermarking method that uses semantic embeddings to identify an input-dependent set of words. These words are then inserted into the text by an LLM after decoding. However, this approach is also not distortion-free, as the insertion of words by the LLM often results in significantly longer watermarked text.

Given the weakness of many schemes to paraphrasing or word substitution attacks, some have proposed watermarking based on semantics and other features that would remain intact for common attack strategies (Liu et al., ; Hou et al., ; Ren et al., ; Yoo et al., ). Meanwhile, others have viewed the problem through the lens of cryptography and classical complexity theory (Christ et al., ; Christ & Gunn, ).
Lastly, Liu et al. () proposes an un-forgeable publicly verifiable watermark algorithm that uses two different neural networks for watermark generation and detection. Huang et al. () improves the statistical tests used for detection, providing faster rates than prior work.

As the deployment of watermarks to LLMs is still early and also presumably secretive, the correct threat model is still undetermined. Krishna et al. () shows that paraphrasing can evade both third-party and watermarking detectors alike.
Somemay posit that attacks like paraphrasing or round-trip translation are unrealistic since either they are too expensive to conduct at scale or parties in possession of a capable paraphrasing model have adequate resources to serve their own LLM. Zhang et al. () show that attackers with weaker computational capabilities can successfully evade watermarks given access to a *quality oracle* that can evaluate whether a candidate output is a high-quality response to a prompt, and a *perturbation oracle* which can modify an output with a non-trivial probability of maintaining quality. Alarmingly, Gu et al. () demonstrates that watermarks can be learned — an adversary can use a teacher model that employs decoder-based watermarking to train a student model to emulate the watermark. Thibaud et al. () formulates tests to determine whether a black-box language model is employing watermarking, and they do not find strong evidence of watermarking among currently popular LLMs.

Figure: Algorithm 1 Black-Box Watermarking

Figure: Algorithm 2 Recursive Black-Box Watermarking

## 3 Algorithm

High-level sketch. At a high level, our scheme operates autoregressively; each step, we sample multiple generations from the LLM, score each with our secret key, and output the highest scoring one. We do this repeatedly until our stopping condition (e.g. reaching the stop-token or the max length) is met. To determine whether a piece of text was watermarked, we score it using our key — if it’s high, it’s likely watermarked. We now describe the algorithm more formally.

Preliminaries. We begin with some preliminaries. If $F$ is a cumulative distribution function (CDF), we let $F[s]$ (square brackets) refer to a single draw from a pseudorandom number generator (PRNG) for $F$ seeded by integer seed $s$. Let $F_{k}$ be the CDF for $\sum_{i=1}^{k}X_{i}$, where $X_{i}\overset{iid}{\sim}F$. We sometimes abuse notation and treat a distribution as its CDF (e.g. $N(0,1)(2)$ is the standard normal CDF evaluated at 2) and when the context is clear we let $-F$ be the distribution of $-X$ where $X\sim F$.
Now, we detail our proposed algorithm, for which pseudocode is provided in Algorithm 1.

Let $F$ be a *continuous* CDF of our choosing, $P$ the input prompt, $K$ a secret integer key known only to the watermark encoder and decoder, LM a conditional language model with vocabulary $\mathcal{V}$ of size $V$, and $h$ a cryptographic hash function (e.g. SHA-256) from $\mathbb{Z}^{*}$ to $\mathbb{Z}$. Let $n$ be the number of tokens (typically 4 or 5) that serves as input to our pseudorandom function. Our PRF $g:\mathcal{V}^{*}\to\mathbb{R}$ is given by $g(w)=F[h\left(K|w\right)]$, where $|$ denotes concatenation.

Watermark encoding. We sample $m$ sequences $\{Q_{1},\dots,Q_{m}\}$, each consisting of at most $k$ tokens from $\texttt{LM}\left(\;\cdot\;|\;P;\;k\right)$. Let $\{(X_{1},c_{1}),\dots,(X_{j},c_{j})\}$ be the *unique* sequences along with their counts from $\{Q_{i}\}$ — for example, the sequence $X_{t}$ appears $c_{t}$ times in $\{Q_{i}\}$.
To score each distinct sequence $X_{t}$, we first extract its $n$-grams as $\{(X_{t,i-n-1},\dots,X_{t,i})\}_{i=1}^{|X_{t}|}$, where we allow the left endpoint to spill over only to earlier-generated tokens and not the original prompt tokens. $l$-grams are taken instead for boundary indices with only $l-1<n-1$ eligible tokens strictly left of it. We compute an integer seed for each $n$-gram $w$, as $h(K|w)$. Given a collection of seeds with their associated sequences, we deduplicate seeds across the collection. We do this by picking one instance of the seed *at random* and remove all remaining instances from the collection. We ensure every sequence has at least one seed by adding a random seed not already used, if necessary. For each sequence $X_{t}$, we iterate through its new seeds $S_{t}$ (order does not matter) and compute the quantity $u_{t}=F_{|S_{t}|}\left(\sum_{i=1}^{|S_{t}|}F[S_{t,i}]\right)$. Finally, we compute $i^{*}=\operatorname{argmax}_{i=1}^{j}u_{i}^{m/c_{i}}$ and choose $X_{i^{*}}$ as our watermarked sequence of length at most $k$. To generate longer texts, we run the aforementioned process autoregressively until our stopping condition, where we condition the language model on $P$ and the tokens generated thus far.

One may notice that the LLM is expected to return at most $k$ tokens. This choice is made to simplify the analysis. In practice, the API may only return texts, not tokens, with no option to specify max length. The watermarker can generate $n$-grams from the responses however they would like (with custom tokenization or not). Furthermore, there is no constraint on $k$; $k$ can be set adaptively to the max length in each batch of returned responses. The main consideration though is smaller $k$ begets a stronger watermark, so if the adaptive $k$ is too large, detectability will suffer.

Watermark detection. We treat detection as a hypothesis test, where the null $\mathcal{H}_{0}$ is that the query text was *not* watermarked with our scheme and secret key and the alternative $\mathcal{H}_{1}$ is that it was. While Bayesian hypothesis testing could be used, this would require choosing priors for both hypotheses, which could be challenging and a poor choice could lead to terrible predictions. Let $X$ be the query text. Akin to the encoding process, we extract $W$, the set of *unique* $n$-grams from $X$, permitting smaller one near the left boundary. For each $n$-gram $w_{t}$ we compute $R_{t}=F\left[h\left(K|w_{t}\right)\right]$. Under $\mathcal{H}_{0}$ (assuming that the test $n$-grams are independent), $R_{t}\overset{iid}{\sim}F$, so $\sum_{t=1}^{|W|}R_{t}\sim F_{|W|}$ giving a $p$-value $p=1-F_{|W|}\left(\sum_{t=1}^{|W|}R_{t}\right)$. Our detection score $s$ is $1-p$ (higher means more likely to be watermarked).

Another way to compute a $p$-value is to compute token-level $p$-values and, assuming they are independent, combine them using Fisher’s method. This way, $p=1-\chi^{2}_{2|W|}\left(-2\sum_{t=1}^{|W|}\log\left(1-F(R_{t})\right)\right)$. Furthermore, tests that incorporate the alternative distribution can be used — the best example being the likelihood ratio test: $s=\sum_{t=1}^{|W|}\left(\log f_{1}(R_{t})-\log f_{0}(R_{t})\right)$, where $f_{0}$ and $f_{1}$ are the densities of $R_{t}$ under $\mathcal{H}_{0}$ and $\mathcal{H}_{1}$ respectively. For some choices of $F$ and under some assumptions, $f_{1}$ may be written explicitly. In other cases, one can *estimate* $f_{1}$ by logging values of $R_{t}$ for the watermarked sequence as the encoding is run live or via simulation and then building a kernel density estimator. We consider these alternative detection strategies later for ablative purposes.

Recursive watermarking. Since our scheme requires only a black box that samples sequences, it can be applied iteratively or recursively. Consider the following. User 1 uses User 2’s LLM service who uses User 3’s LLM service, so on so forth until User $t$. Our scheme allows User $i$ to watermark its service with its secret key $K_{i}$.
Each user can then run detection using its key oblivious to whether other watermarks were embedded upstream or downstream. Furthermore, the users can cooperate in joint detection by sharing only $p$-values without revealing their secret keys. This property is valuable in the service oriented architectures of today’s technology stack.

Consider the special case that all users are actually the same entity in possession of $t$ distinct keys $\{K_{1},\dots,K_{t}\}$. Then the iterative watermarking becomes a recursive one, where $K_{i}$ is used to watermark the result of watermarking with keys $\{K_{i+1},\dots,K_{t}\}$. The entity can run Detect to get a $p$-value for each key and these $t$ $p$-values can subsequently be combined using Fisher’s method. We present this recursive scheme in Algorithm 2.

White-box watermarking. In the case of $k=1$, our scheme can be efficiently run for users who have white-box access — with the next-token distribution in hand, one can sample a large number of candidate tokens without any inference calls to the model.

Extensions.
At its crux, the proposed scheme samples sequences of text from a service, divides each unique sequence into a bag of units (namely $n$-grams) where each unit is scored using a PRF and the scores are combined in an order-agnostic way. The strength of the watermark depends on the number of *distinct* units across the candidate sequences and the robustness depends on how many of the units are kept intact after the attack. Although any symmetric monotone function can be used instead of the simple summation of the PRNs for each unit, we do not see any compelling reason to make our algorithm more general in this way. However, we briefly highlight some other possible extensions.

*Beam search*. Rather than drawing i.i.d. samples from the model, one can apply our watermark selection to the sequences that arise from beam search, with the caveat that this would violate our distortion-free property.

*Semantic watermarking*. Rather than use $n$-grams, the watermarker can extract a set of meaningful semantic units for each sampled text. Robustness may be improved as these units will largely remain intact under an attack like paraphrasing. On the other hand, many of the sampled sequences will have the same *meaning*, so there may be a lot of duplicate units across the candidate sequences, which would degrade the watermark strength.

*Paraphrasing*. Thus far, we assumed the service provides $m$ draws from the LLM. If $m$ is large, this can be prohibitively expensive. The resource-constrained may consider the following alternative: draw one sample from the LLM and feed it to a much cheaper paraphrasing model to generate $m$ paraphrases. The downside is that there may be a lot of duplicate $n$-grams across the candidate set.

## 4 Theory

Our goal here is to show that our scheme is faithful to the model’s next-token distribution and to give detection performance guarantees.
All proofs are in the Appendix.

###### Theorem 4.1 (Distortion-free property) .

Let $X$ be any finite sequence and $P$ any prompt. Let $X_{u}\sim\texttt{LM}\left(\;\cdot\;|\;P\right)$ be the non-watermarked output of the conditional autoregressive language model. Let $X_{w}$ be the output of the watermarking procedure (Watermark in Algorithm 1, for both recursive and non-recursive settings) for the same prompt and model and any choice of remaining input arguments with the constraint that $F$ is a continuous distribution. Furthermore, assume that the deduplicated seeds (determined by hashing the secret key and $n$-grams) across sequences, are conditionally independent given the counts of the sampled sequences. Then, $\mathbb{P}(X_{u}=X)=\mathbb{P}(X_{w}=X)$.

Theorem 4.1 tells us that sampling tokens using our proposed scheme is, from a probabilistic perspective, indistinguishable from sampling from the underlying model, with the caveat that the unique seed values are conditionally independent given the counts of sequences. If we dismiss hash collisions as very low probability events, then since the key is fixed, this reduces to the assumption that unique $n$-grams across the sampled sequences are independent. How strong of an assumption this is depends on many factors such as $m$, the underlying distribution, and the counts $(c_{1},\dots,c_{j})$ themselves. One can construct cases where the assumption is reasonable and others where it is blatantly violated (e.g. if $n$-grams within a sequence are strongly correlated). One direction to making the assumption more palatable is to draw a fresh keys i.i.d. for *each* hash call. This would obviously destroy detectability. As a trade-off, one can leverage a set of secret keys (i.e. by drawing keys uniformly at random from a key set), which may reduce distortion, but will hurt detection as each key in the set needs to be tested against.

###### Theorem 4.2 (Lower bound on detection ROC-AUC) .

Consider the specific case of using flat (i.e. non-recursive) watermarking with $k=1$ and $F=U(0,1)$. Let $s_{0}$ be the score under null that the $T$ test tokens(^1^11To be more precise, these are $T$ *unique* $n$-grams.),assumed to be independent, were generated without watermarking and $s_{1}$ be the score if they were. With $c_{i}$ as the number of times vocabulary token $i$ was sampled, we have the following lower bound on the detector’s ROC-AUC.

$$ $\displaystyle{\mathbb{P}}(s_{1}\geq s_{0})$ $\displaystyle\geq\frac{1}{1+1/(3T\lambda^{2}\alpha^{2})},\;\text{where}$ $\displaystyle\lambda=\frac{1}{\log(m)}\left(\frac{m}{m+1}-\frac{1}{2}\right)\;$ $\displaystyle\text{and}\;\alpha={\mathbb{E}}_{c}\left[-\sum_{i=1}^{V}\mathbf{1 }[c_{i}>0]\frac{c_{i}}{m}\log\left(\frac{c_{i}}{m}\right)\right].$ $$

$\alpha$ represents the average Shannon entropy in the sampled next-token distribution.

Theorem 4.2 connects detection performance to the language model’s underlying distribution, number of sampled tokens $m$, and number of test samples $T$. More entropy and more test samples guarantee higher performance. When the model is extremely confident, $\alpha\to 0$ and so does our lower bound. Note that because $\alpha$ measures the entropy of the empirical distribution arising from *sampling* tokens, it depends on both the underlying next-token probability distribution as well as $m$. Concretely, when conditioned on the next-token probabilities $p$, $c\sim\text{Multinomial}\left(m,p\right)$. The largest $\alpha$ is achieved when the nonzero $c_{i}$’s are 1, which can occur when the underlying distribution is uniform (maximal uncertainty) and/or $m$ is not large. In this case, $\alpha\to\log(m)$ and our bound goes to $1/\left(1+1/\left(3T\left(\frac{m}{m+1}-\frac{1}{2}\right)^{2}\right)\right)$. This quantity has very sharp diminishing returns with respect to $m$, so there may be little value in increasing $m$ beyond a certain point. When $m\to\infty$, the bound goes to $1/(1+4/(3T))$, which increases very quickly with $T$. A mere 50 test tokens guarantees at least $97\%$ ROC-AUC. We study the interplay of the various factors on our lower bound more carefully in the Appendix.

The intuitions here carry over to other choices of $F$ and $k>1$, though formal bounds can be tricky to obtain because of difficulty quantifying the alternative distribution. The null distribution is easy — $p$-values are $U(0,1)$ under $\mathcal{H}_{0}$, and as a result, we have a straightforward equality on the false positive rate.

###### Theorem 4.3 (False positive rate) .

No matter the choice of watermarking settings, assuming that the unique test $n$-grams are independent, we have the following equality on the false positive rate of Detect, using decision threshold $t$.

$$ $\displaystyle\text{FPR}={\mathbb{P}}_{\mathcal{H}_{0}}(s>t)=1-t.$ $$

This also holds for DetectRecursive if we further assume the $p$-values across secret keys are independent.

Selecting distinct independent secret keys $\{K_{1},\dots,K_{t}\}$ (and ignoring hash collisions that arise across calls to Detect within DetectRecursive), will help attain the necessary independence.

Although the alternative score distribution is generally intractable, with the strong assumption that there are no duplicate $n$-grams across the candidate sequences, then for a special choice of $F$, we can write the alternative in closed form and formulate the optimal detection test.

###### Theorem 4.4 (Optimal detection for Gamma) .

Assume that candidate sequences are unique with length $k$ and that the $n$-grams are independent and contain no duplicates. Suppose we choose $F=-\text{Gamma}\left(1/k,\beta\right)$ (flat scheme), for any rate parameter $\beta$. Let $F_{0}=F$ with pdf $f_{0}$, $F_{1}=-\text{Gamma}\left(1/k,m\beta\right)$ with pdf $f_{1}$, and $R$ the PRF values of the $T$ test tokens (unique $n$-grams), assumed to be independent. Then, $\forall i$, $R_{i}\overset{iid}{\sim}F_{0}$ under the null that the text was watermarked using our procedure and $R_{i}\overset{iid}{\sim}F_{1}$ otherwise. The uniformly most powerful test is the log-likelihood ratio test (LRT) with score

$$ $\displaystyle s(R)=\sum_{i=1}^{T}\log\frac{f_{1}(R_{i})}{f_{0}(R_{i})}.$ $$

Furthermore, for any decision threshold $t$ on score $s$, we have that:

$$ FPR (Type-I error) $\displaystyle=\mathbb{P}_{\mathcal{H}_{0}}(s>t)=\text{Gamma}(T/k,\beta)\left(Q (t)\right),\;\text{and}$ FNR (Type-II error) $\displaystyle=\mathbb{P}_{\mathcal{H}_{1}}(s\leq t)=1-\text{Gamma}(T/k,m\beta) \left(Q(t)\right),\;\text{where}$ $\displaystyle Q(t)$ $\displaystyle=\frac{T\log(m)/k-t}{(m-1)\beta}.$ $$

In the Appendix, we use Theorem 4.4 to study the impact of $k$, $m$, and $T$ on TPR at fixed FPR. For example, with $T=100$, $k=50$, $m=64$, $\beta=1$, we can achieve $99.9\%$ TPR at $1\%$ FPR.

For other choices of $F$, we can estimate $f_{1}$ via simulation. If we assume candidate sequences have the same length $k$ with no duplicate $n$-grams, then we can fill an $m\times k$ matrix with i.i.d. draws from $F$ and pick the first element of the row with the largest row-sum (among the $m$). We do this until we have sufficiently large (e.g. 10,000) samples from $f_{1}$. We apply a Gaussian kernel-density estimator where the bandwidth is chosen using Scott’s rule (Scott, ) to estimate $f_{1}(r)$ for test value $r$. Despite having $f_{0}$ in closed-form, for consistency, we can also estimate it non-parametrically by drawing from $F$.

###### Theorem 4.1 (Distortion-free property) .

###### Theorem 4.2 (Lower bound on detection ROC-AUC) .

###### Theorem 4.3 (False positive rate) .

###### Theorem 4.4 (Optimal detection for Gamma) .

## 5 Experiments

In this section, we compare the performance of our scheme with that of prior work.

### 5.1 Models, Datasets, and Hyperparameters

Models and Datasets.
Our main model and dataset is Mistral-7B-instruct (Jiang et al., ) hosted on Huggingface(^2^22[https://huggingface.co/mistralai/Mistral-7B-Instruct-v0.1](https://huggingface.co/mistralai/Mistral-7B-Instruct-v0.1)) with bfloat16 quantization, and *databricks-dolly-15k*(^3^33[https://huggingface.co/datasets/databricks/databricks-dolly-15k](https://huggingface.co/datasets/databricks/databricks-dolly-15k)) (Conover et al., ), an open source dataset of instruction-following examples for brainstorming, classification, closed QA, generation, information extraction, open QA, and summarization. We use prompts from the brainstorming, generation, open QA (i.e. general QA), and summarization categories, whose human responses are at least 50 tokens long (save one example, which was removed because the prompt was extremely long). For each of the 5233 total prompts, we generate two non-watermarked responses — a stochastic one using temperature 1, and the greedy / argmax decoding — along with a watermarked one for each scheme. We always force a minimum (maximum) of 250 (300) new tokens by disabling the stop token for the first 250 tokens, re-enabling it, and stopping the generation at 300, regardless of whether the stop token was encountered.
To simulate real-world use, we de-tokenize the outputs to obtain plain text, and re-tokenize them during scoring. We study performance as a function of token length $T\leq 250$ by truncating to the first $T$ tokens.

For completeness, we also present the key results when Gemma-7B-instruct(^4^44[https://huggingface.co/google/gemma-7b-it](https://huggingface.co/google/gemma-7b-it)) with bfloat16 quantization is applied to the test split of *eli5-category*(^5^55[https://huggingface.co/datasets/rexarski/eli5_category](https://huggingface.co/datasets/rexarski/eli5_category)). Prompts are formed by concatenating the the *title* and *selftitle* fields. Only examples with non-empty *title* and whose prompt contains a *?* are kept — for a total of 4885 examples.

Hyperparameters.
We consider the following choices of CDFs $F$ / $F_{k}$. (1) $F=U(0,1)$ and $F_{k}=\text{IrwinHall}(k)$. (2) $F=N(0,1)$ and $F_{k}=N(0,k)$. (3) $F=-\text{Gamma}(1/k,1)$ and $F_{k}=-\text{Exp}(1)$. (4) $F=\chi_{2}^{2}$ and $F_{k}=\chi_{2k}^{2}$.

### 5.2 Evaluation Metrics

We evaluate performance using three criteria.

Detectability.
How well can we discriminate between non-watermarked and watermarked text? We choose non-watermarked text to be text generated by the same model, just without watermarking applied during decoding. There are three reasons for choosing the negative class in this way. Firstly, it makes controlling for text length easier as we can generate as many tokens as we do for watermarked samples — in contrast, human responses are of varying lengths. Secondly, watermarked text has far more token / $n$-gram overlap with its non-watermarked counterpart than the human reference, which makes detection more challenging. Lastly, since one intended use case of our scheme is for third-party users of a shared LLM service, users may want to distinguish between their watermarked text and non-watermarked text generated by the same LLM service.

Our primary one-number metric is ROC-AUC for this balanced binary classification task. Since performance at low FPR is often more useful in practice, we report the partial ROC-AUC (pAUC) for FPR $\leq$ a target FPR (taken to be 1%), which we find to be more meaningful than TPR at the target FPR. We look at performance as a function of length by truncating the positive and negatives samples to lengths $\{25,50,75,100,150,200,250\}$. To understand aggregate performance, we pool all different length samples together and compute one ROC-AUC. Here, it is paramount that the detection score be length-aware to ensure that a single decision threshold can be used across lengths.

Distortion.
Our scheme, along with most of the baselines, boasts a *distortion-free* property. This property comes with assumptions that are often violated in practice, for example by reuse of the secret key across watermarking calls. We quantify how faithful the watermarking procedure is to the underlying generative model by computing both the *perplexity* and *likelihood* of watermarked text under the generator (without watermarking). We include likelihood as the log-probabilities used in calculating perplexity can over-emphasize outliers.

Quality.
Watermarking may distort the text per the model, but does the distortion tangibly affect the *quality* of the text? Quality can be challenging to define and measure — one proxy is likelihood under a much larger model than the generator. Alternatively, one can run standard benchmark NLP tasks and use classic metrics like exact match, etc. We instead opt for using Gemini-1.5-Pro as an LLM judge and compute pairwise win rates for each watermark strategy against no watermarking (greedy decoding). We do this in two ways for each scheme — (1) we compute win rates using a single response for each prompt and (2) we first ask the LLM judge to pick the best of 3 responses for each prompt and compute win rates using the best response. (2) represents the common practice of sampling a few generations from the LLM and selecting the best one using some criterion. It captures diversity, as methods that can express an answer in a few different good ways will have an advantage. A caveat with win rates is that they may not reflect the *degree* by which one method is better or worse. For instance, if one strategy’s output was always *marginally* worse than no watermarking, the win rate would be 0% — the same as if it were *much* worse.

### 5.3 Adversarial Attacks

An adversary in possession of watermarked text (but who lacks knowledge of the secret key) may try to evade detection. We study how detectability degrades under two attack strategies —- random token replacement and paraphrasing.

Random token replacement.
Here, we take the watermarked tokens and a random $p$-percent of them are corrupted by replacing each with a random different token. $p$ is taken to be $\{10,20,30,40,50\}$.
This attack strategy is cheap for the adversary to carry out but will significantly degrade the quality of the text.

Paraphrasing.
In this attack, the adversary attempts to evade detection by paraphrasing the watermarked text. We use Gemini-1.5-Pro to paraphrase each non-truncated watermarked generation. Details are deferred to the Appendix.

**Table 1: Main table of results, showing our black-box scheme (*Flat*) and its recursive variant (*Rec.*) for various $k$’s and $m$’s, along with baselines. PPL, WR and WR (3) refer to perplexity, win rate of a single response, and win rate of the best-of-3 responses respectively. pAUC is ROC-AUC up to max FPR of 1%. C and P stand for 10% corruption and paraphrasing attack. For paraphrasing, target lengths of {150, 200, 250} are used in calculating AUC and pAUC as performance is essentially random on shorter lengths. The standard errors are quite small and the maximum across rows is shown for each column. AUCs, pAUCS, and their standard errors are scaled by 100.**
|  | PPL | WR | WR (3) | AUC | pAUC | C. AUC | C. pAUC | P. AUC | P. pAUC |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Max Std. Error | 0.03 | - | - | 0.1 | 0.3 | 0.2 | 0.3 | - | - |
| Greedy Decoding | 1.37 | - | - | - | - | - | - | - | - |
| Random Sampling | 3.50 | 49.6 | 65.3 | - | - | - | - | - | - |
| Aaronson | 2.81 | 45.3 | 45.3 | 71.7 | 65.5 | 65.6 | 60.3 | 53.9 | 50.5 |
| Aaronson Cor. | 2.81 | 45.3 | 45.3 | 97.9 | 83.6 | 94.8 | 73.2 | 58.8 | 50.7 |
| Kuditipudi | 3.55 | 50.3 | 67.3 | 87.8 | 76.6 | 87.2 | 74.4 | 75.9 | 53.2 |
| Kirchenbauer<br>$0.5$ | 3.39 | 49.6 | 66.6 | 73.2 | 52.0 | 71.0 | 51.4 | 49.0 | 49.8 |
| $1$ | 3.37 | 50.1 | 67.0 | 86.9 | 60.6 | 83.7 | 57.1 | 52.9 | 49.9 |
| $2$ | 3.69 | 47.9 | 64.1 | 97.0 | 83.3 | 95.4 | 77.4 | 58.4 | 50.3 |
| $3$ | 4.67 | 41.5 | 58.4 | 99.3 | 94.4 | 98.6 | 90.9 | 63.4 | 51.5 |
| $4$ | 5.81 | 26.0 | 41.2 | 99.8 | 98.4 | 99.6 | 96.8 | 66.4 | 52.7 |
| Flat $(k=1)$<br>$2$ | 3.46 | 50.0 | 66.4 | 90.2 | 68.8 | 82.0 | 58.7 | 50.5 | 50.3 |
| $4$ | 3.36 | 50.8 | 67.0 | 95.8 | 82.9 | 90.3 | 70.5 | 51.3 | 50.6 |
| $16$ | 3.20 | 47.7 | 64.5 | 97.7 | 89.7 | 93.9 | 79.1 | 52.7 | 51.1 |
| $32$ | 3.06 | 48.4 | 65.3 | 97.8 | 90.2 | 94.2 | 80.0 | 53.0 | 50.8 |
| $512$ | 2.63 | 47.7 | 62.5 | 97.7 | 90.0 | 94.1 | 79.7 | 54.6 | 51.3 |
| $1024$ | 2.61 | 47.7 | 62.2 | 97.7 | 90.0 | 94.0 | 79.7 | 52.8 | 51.1 |
| Flat $(k=10)$<br>$2$ | 4.10 | 46.1 | 62.2 | 83.4 | 55.8 | 73.6 | 52.0 | 49.0 | 50.0 |
| $4$ | 4.06 | 45.2 | 61.5 | 93.8 | 72.7 | 85.7 | 59.4 | 51.3 | 50.3 |
| $16$ | 3.86 | 44.6 | 60.6 | 97.8 | 87.0 | 93.1 | 73.5 | 54.3 | 50.7 |
| $32$ | 3.80 | 43.0 | 60.8 | 98.2 | 89.0 | 94.0 | 76.7 | 55.0 | 50.8 |
| Flat $(k=50)$<br>$2$ | 3.79 | 48.5 | 64.2 | 69.6 | 50.7 | 62.2 | 50.3 | 47.0 | 50.0 |
| $4$ | 3.76 | 47.7 | 63.9 | 82.9 | 53.5 | 71.9 | 51.3 | 49.4 | 50.0 |
| $16$ | 3.72 | 48.3 | 64.2 | 92.7 | 66.7 | 83.1 | 55.6 | 50.5 | 50.1 |
| $32$ | 3.67 | 47.3 | 63.9 | 94.2 | 71.6 | 85.5 | 58.1 | 51.1 | 50.5 |
| Rec. $(k=1)$<br>$4$ | 3.41 | 49.0 | 65.0 | 93.4 | 75.5 | 86.3 | 63.2 | 48.4 | 50.4 |
| $16$ | 3.33 | 49.2 | 66.2 | 95.4 | 82.9 | 90.6 | 71.8 | 53.4 | 50.8 |
| $32$ | 3.29 | 48.4 | 64.3 | 96.3 | 85.0 | 91.6 | 73.5 | 49.4 | 50.8 |
| $512$ | 3.05 | 48.3 | 64.5 | 97.2 | 87.9 | 92.6 | 76.5 | 50.4 | 51.2 |
| Rec. $(k=10)$<br>$4$ | 4.13 | 45.7 | 61.3 | 88.6 | 61.7 | 78.8 | 53.8 | 48.0 | 50.0 |
| $16$ | 4.13 | 43.7 | 59.7 | 93.4 | 74.0 | 86.8 | 61.6 | 52.9 | 50.4 |
| $32$ | 4.06 | 42.9 | 59.5 | 94.8 | 76.9 | 88.1 | 63.2 | 50.6 | 50.3 |
| Rec. $(k=50)$<br>$4$ | 3.79 | 48.2 | 63.8 | 74.2 | 51.2 | 65.1 | 50.5 | 46.5 | 49.9 |
| $16$ | 3.77 | 47.0 | 64.0 | 81.2 | 54.5 | 73.3 | 51.9 | 51.4 | 50.2 |
| $32$ | 3.79 | 47.2 | 63.3 | 83.3 | 55.7 | 74.4 | 52.2 | 49.4 | 50.0 |

Figure: Figure 1: Performance of our flat scheme. Top: Detection AUC and pAUC with 1% max FPR for a range of target text lengths when there is no corruption. Bottom Left: AUC (mixed $T$’s) as a function of the average non-watermarked response entropy of the examples used in the calculation. $x$-coordinate $x$ corresponds to the bucket of examples whose entropy is between $[x-0.25,x]$ nats. Bottom Right: Effect of amount of random token corruption on AUC (mixed $T$’s).
Refer to caption: extracted/5897332/plots/auc_T.png

### 5.4 Baselines

The watermark schemes we consider here operate token-by-token in the autoregressive decoding loop.
Let $p$ be the next-token probability distribution. Higher detection scores indicate higher confidence that the query text is watermarked.

Aaronson (A). Aaronson () computes a PRN for each token $i$ in the vocabulary as $u_{i}=U(0,1)[h(K|w|i)]$, where $w$ is the preceding $(n-1)$-gram, $K$ is the secret key and $h$ is a cryptographic hash. Token $i^{*}$ is selected, where $i^{*}=\operatorname{argmax}_{i}u_{i}^{1/p_{i}}$. At test time, $n$-grams $\{w_{i}\}_{i=1}^{T}$ are extracted from the query test and the detection score $s$ is $-\sum_{i=1}^{T}\log\left(1-R_{i}\right)$, where $R_{i}=U(0,1)\left[h(K|w_{i})\right]$.
$n$ is set to 4. This choice strikes a good balance between generation quality / diversity and robustness to attacks. The scheme boasts a *distortion-free* property, but the generated text is a deterministic function of the prompt — i.e. only one generation is possible conditioned on a particular prompt.

###### Remark .

If $k=1$ and $F=U(0,1)$, then our watermark encoding can be viewed as a stochastic version of Aaronson ()’s. As $m\to\infty$, $c_{t}/m\overset{a.s.}{\to}p_{t}$, where $p_{t}$ and $c_{t}$ are the probability and observed occurrences of token $t$.

Aaronson Corrected (AC).
Aaronson ()’s detection score $s_{A}$ is not length-aware and consequently a single decision threshold across scores involving various lengths results in poor performance, as we later show. Observing that $s_{A}$ is a sum of log $p$-values, $s_{A}\sim\text{Gamma}(T,1)$, or equivalently, $2s_{A}\sim\chi_{2T}^{2}$ under the null that all test tokens are non-watermarked. We propose the new *corrected* detection score, $s=1-\text{Gamma}(T,1)(s_{A})=1-\chi_{2T}^{2}(2s_{A})$. For completeness we also experiment with a $p$-value computed in the way we do for our method — concretely as, $1-\text{IrwinHall}(T)\left(\sum_{i=1}^{T}R_{i}\right)$. Note that both transformations are monotonic so they have no effect on ROC-AUC when T is *fixed*.

Kirchenbauer (KB). Kirchenbauer et al. () uses the $n$ previous tokens to pseudorandomly partition the vocabulary for the next token into two lists: a green list of size $\gamma V$ and a red list consisting of the remainder. A positive bias of $\delta$ is added to the logits of the green list tokens while those of the red list are left unchanged. This has the effect of modifying $p$ so that green list tokens are more probable. The score for a text consisting of $T$ tokens, $T_{g}$ of which were found to be green is, $s=(T_{g}-\gamma T)/\sqrt{T\gamma(1-\gamma)}$.
We incorporate the latest updates to the algorithm,(^6^66[https://github.com/jwkirchenbauer/lm-watermarking](https://github.com/jwkirchenbauer/lm-watermarking)) such as including the current token in the $n$-gram and skipping duplicate $n$-grams at test time. We set $n=4$, $\gamma=0.25$, and $\delta\in\{0.5,1,2,3,4\}$.

Kuditipudi (K). A drawback of using the last $n$ tokens as a basis for the PRF is that changing just one of them changes the output and hurts detection. Kuditipudi et al. () addresses this limitation as follows. Consider a secret, finite ordered list of seeds of length $k$. Start watermarking by selecting a position in the seed list uniformly at random and apply the selection rule of Aaronson () with the PRNG seeded to the current value. Advance to the next seed in the list (wrap-around if you are at the end) and repeat. Scoring is done by conducting a permutation test evaluating how compatible the query text is with the specific list of seeds used during encoding as opposed to any other random list of seeds of the same length.
As the random starting position is not known during scoring, an alignment score based on the Levenshtein distance is given that considers alignments of various subsequences of the text and seeds. The proposed method is quite similar to Aaronson () with the difference of using a fixed list of seeds (instead of input tokens to determine the seed) and using a permutation test for scoring. The upside is robustness to token substitution attacks; the downside is significantly higher computational cost for scoring. Larger $k$ offers more diversity and quality in generation but comes with costlier and weaker detection. The scheme is distortion-free. Following their work, we let $k=256$ and accelerate the permutation test by pre-computing 5000 reference values for the secret list using snippets from the train set of *C4-realnewslike* (Raffel et al., ) at the various target lengths we evaluate on.

###### Remark .

### 5.5 Experimental Results

Table 1 shows results for baselines and our scheme using $F=U(0,1)$ and $p$-values for scoring, as detailed in Algorithms 1 and 2. For the recursive scheme, depth is $\text{lg}(m)$ (i.e. $m=2$ for each imaginary watermarker). Here, the negative class is non-watermarked argmax/greedy generations. Results for using stochastic (temperature 1) generations as the negative as well as the average likelihood scores are presented in Table 5 (Appendix); the trends remain the same. We summarize our observations on Mistral-7B-instruct on *databricks-dolly-15k*, which also hold for Gemma-7B-instruct on *eli5-category* (presented in the Appendix).

#### 5.5.1 Overall performance of our flat and recursive schemes

Our scheme is a competitive option for white-box watermarking. Is it better to use our method or alternatives in the white-box setting? When $k=1,m=1024$, we are able to achieve better perplexity (2.61 vs. 2.81), better diversity (62.2% vs. 45.3% on best-of-3 win rates) and comparable detection performance than Aaronson (). Furthermore, it has better perplexity (2.61 vs. 3.55) and detection performance (97.7% vs. 87.8% AUC) than Kuditipudi et al. (). By cranking up $\delta$, Kirchenbauer et al. () can achieve strong detection but at the expense of perplexity. When matched on perplexity, we achieve better detection. For example, $\delta=0.5$ achieves 3.39 PPL and 73.2% AUC compared to our 2.61 PPL and 97.7% AUC. Gemma-7B-instruct on *eli5-category* with $k=1,m=1024$ outperforms Kuditipudi et al. () and is on-par with Aaronson () (see Appendix). Kirchenbauer et al. () with $\delta=0.5$ gives 1.649 PPL and 61.6% AUC whereas $k=1,m=1024$ gets us 1.610 PPL with 93.2% AUC and *even* 1.645 PPL with 89.7% AUC when $k=50,m=16$ (black-box).

Flat watermarking outperforms recursive. Across metrics and settings we see that the flat scheme outperforms its recursive counterpart, suggesting it is more effective when a strong signal is embedded using a single key rather than when multiple weak signals are embedded with different keys. For example, when $k=1,m=32$ flat (recursive) PPL and AUC are 3.06 (3.29) and 97.8% (96.3%) respectively.

#### 5.5.2 Effects of Hyperparameters

Increasing $m$ improves perplexity but hurts diversity.
Across $k$’s, we observe that perplexity decreases as $m$ increases, but that win rates, especially when best-of-3 generations are used, decrease. For example, when $k=1$, increasing $m$ from 2 to 1024 decreases perplexity from 3.46 to 2.61 but also drops the best-of-3 win rate from 66.4% to 62.2%. As remarked earlier, as $m\to\infty$, $c_{t}/m\to p_{t}$ and our scheme becomes less diverse — deterministic conditioned on the prompt, like Aaronson’s. On the flip side, large $m$ reduces sampling noise which drives down perplexity.

Increasing $m$ improves detection but has diminishing returns.
Across the board we see that detection improves as $m$ increases, but there are diminishing returns. For example, when $k=1$, our AUC increases from 90.2% to 95.8% as $m$ goes from 2 to 4, but flattens out when $m$ hits 16. This corroborates our theoretical intuition from Theorem 4.2 which is further explored in Figure 4 (Appendix).

For fixed $m$, increasing $k$ hurts detection performance. For fixed $m$ and target generation length $T$, increasing $k$ gives us fewer opportunities (fewer calls to WatermarkSingle) to inject the watermark signal, and detection consequently suffers. For example, when $m=32$, AUC drops from 97.8% to 94.2% when $k$ increases from 1 to 50.

$U(0,1)$ slightly outperforms alternative distributions. Flat distributions may offer better robustness to attacks.
In Table 4 (Appendix), we see that $U(0,1)$ fares comparably to $N(0,1)$ and slightly outperforms $\chi_{2}^{2}$ both on detection and perplexity. For example, when $k=50,m=2$, $U(0,1)$ and $\chi_{2}^{2}$ have AUCs of 69.6% and 68.1% respectively. Furthermore, we find evidence that $U(0,1)$ offers better protection to attacks. For example, when $k=50,m=32$, the AUC for $U(0,1)$ ($\chi_{2}^{2})$ degrades from 94.2% (94.5%) to 85.5% (84.5%) in the presence of 10% random token corruption. We provide some intuition for why flat distributions like $U(0,1)$ may be more robust than those with quickly decaying tails. Consider shaping the continuous $F$ so it approaches $\text{Bern}(p)$ (i.e. $f(x)\approx(1-p)\delta(x)+p\delta(x-1)$), where $p$ is very small. Suppose $k$ is large and $m$ is small. Then, the winning sequence $X_{i^{*}}$ will have extremely few (if any) of its $R_{j}$’s equal to $1$. If the text is unmodified and these few $n$-grams are kept intact, we are fine, but if they are corrupted in an attack, then the watermarking signal is effectively lost. In other words, flat distributions *smear* the watermarking signal over more tokens than do sharper distributions, which localize the signal to few lucky token positions. However, whereas scoring with $F_{T}=\text{IrwinHall}(T)$ when $F=U(0,1)$ involves computing $T$-fold convolutions or cardinal B-splines, when $F=N(0,1)$, $F_{T}$ is easier to compute for very large $T$; specifically, $F_{T}(x)=F\left(x/\sqrt{T}\right)$.

#### 5.5.3 Observations on detection

Length correction of Aaronson () is crucial. Recall that the ROC-AUCs presented in Table 1 are computed over a pool of different lengths. Our $p$-value-based score for Aaronson () improves detection significantly; for example, AUC goes from 71.7% to 97.9%. Table 7 (Appendix) shows that the *sum-based* $p$-value correction fares a bit worse, which was a little surprisingly given that this worked the best for our scheme, even for the $k=1$ case.

Sum-based $p$-values outperform Fisher ones. In Table 2 (Appendix), we observe that replacing our *sum-based* $p$-value (where $\mathcal{H}_{0}$ is that $\sum_{i}^{T}r_{i}\sim F_{T}$) by a Fisher combination of token-level $p$-values hurts detection performance. For example, when $k=1,m=2$, AUC degrades from 90.2% to 86.3%. Note that when $k=1$, this setting corresponds exactly to a stochastic version of Aaronson ().

Likelihood-ratio scoring does well for large $k$ and small $m$, when its assumptions are more realistic. In Table 3 (Appendix), we observe that likelihood-based scoring — both when the distribution is Gamma and the exact likelihood ratio test (LRT) is used and under KDE with alternative distributions — performs the best when the assumptions of no duplicate sequences or $n$-grams hold better. This happens when the sequences are long (large $k$) and when fewer sequences are sampled (small $m$). For example, when $k=1$, AUC *degrades* monotonically from 78.1% to 55.4% as $m$ increases from $2$ to $1024$. In contrast, AUC under the $p$-value-based scoring *increases* monotonically with $m$, from 90.2% to 97.7%. Larger $m$ increases the number of duplicate sequences sampled, increasing the importance of the latent exponent $m/c_{i}$ used in the scoring and deviating us further from the LRT assumptions. However, LRT has the potential to be an effective alternative when $k$ is large. For example, when $k=50$ and $m=32$, Uniform KDE-based LRT gives AUC of 95.5% compared to $p$-value’s 94.2%.

Detection performance improves sharply with test samples $T$. Figure 1 shows the effect of $T$ on AUC. We see sharp improvements w.r.t. to $T$, even when $k$ is large and $m$ is small, highlighting the power of more test samples to counteract a weaker watermark signal.

Entropy improves detection performance. In Figure 1 we bucket prompts based on the entropy of their non-watermarked response and then look at detection AUC on samples in each bucket. As we expect, detection improves when the prompts confer more entropy in the response. This trend is more stark for our method.

Paraphrasing can be extremely effective at destroying watermarks. We observe that paraphrasing can effectively erase the watermark as detection performance for most methods is near random. Kuditipudi et al. () and Kirchenbauer et al. () with large $\delta$ do better on AUC (but not so much on pAUC). Furthermore, in Figures 1 and 2 (Appendix) we observe that large amounts of random token corruption hurts our scheme and Aaronson ()’s more than it that of Kirchenbauer et al. () or Kuditipudi et al. ().

## 6 Conclusion

In this work, we present a framework for watermarking language models that requires nothing more than a way to sample from them. Our framework is general and extensible, supporting various real world use-cases, including the setting where the next-token probabilities are in fact available. We study its various components and the trade-offs that arise, provide formal guarantees for the theoretically-inclined as well as concrete recommendations for the practitioner.

## Acknowledgements

The authors would like to thank Rob McAdam, Abhi Shelat, Matteo Frigo, Ashkan Soleymani, John Kirchenbauer, and Mukund Sundararajan for insightful discussions without which this work would not be possible.

## Appendix A Appendix

### A.1 Additional Experimental Details

Prompting strategies for Gemini. We use Gemini for paraphrasing and as an LLM judge. Occasionally, Gemini will refuse to return a response due to safety filters that cannot be bypassed.
We use the following prompt to compute win rates:

*“Is (A) or (B) a better response to PROMPT? Answer with either (A) or (B). (A): GREEDY RESPONSE. (B): WATERMARKED RESPONSE.”*

For determining the best response, we use:

*“Is (A), (B), or (C) the best responses to PROMPT? Answer with either (A), (B), (C). (A): RESPONSE 1. (B): RESPONSE 2. (C): RESPONSE 3.”*

In both cases, we search for the first identifier (i.e. “(A)”, “(B)”, “(C)”). If one is not found or if Gemini does not return a response, the example is not used in the win rate calculation or the first response is chosen.

For paraphrasing, we use the following:

*“Paraphrase the following: RESPONSE”*.

We skip examples for which Gemini does not return a response.

### A.2 Omitted Experimental Results

Figure 2 shows the effect of varying the amount of random token corruption on detection pAUC. We observe the same trend as for AUC. Figure 3 plots a histogram of the entropy of the underlying next-token probability distribution under temperature 1 random sampling without watermarking across our dataset. We see the entropy is concentrated between 0.5 and 3 nats. We plot the AUC lower bound predicted by Theorem 4.2 ($k=1,m=1024$) sweeping *our* entropy term $\alpha$ across this range, with the understanding that for sufficiently large $m$, our $\alpha$ is a good estimator of the true underlying entropy. In Figure 4 we look at the impact of $m$ and $T$ on our AUC bound when the optimal $\alpha=\log(m)$ is plugged in. We see sharp diminishing returns w.r.t. $m$ (performance saturates after around $m=10$ for all $T$’s). We empirically observe this saturation in Table 1, where AUC saturates at 97.7% at $m=16$ — that is, increasing $m$ beyond 16 has negligible impact. Furthermore, we observe that the bound increases sharply with $T$, corroborating the trend we see empirically in Figure 1.

Given a next-token distribution over the vocabulary, we can estimate $\alpha$ via simulation. In Figure 5 we plot the effect of $m$ on $\hat{\alpha}$, our simulated entropy, for two distributions $p$ — uniform and Zipf — over a 32k token vocabulary. Neither may be realistic in practice, but the exercise is still informative as we observe that $\hat{\alpha}$ follows $\log(m)$ pretty well for even large $m$’s when $p$ is uniform. As expected, $\hat{\alpha}$ is smaller when $p$ is Zipf (lower entropy) and deviates from $\log(m)$ for large $m$.

Figure 7 plots the performance that Theorem 4.4 predicts when using the optimal likelihood ratio test with the Gamma distribution.

Table 6 shows perplexity and detection performance for Gemma-7B-instruct on the *eli5-category* dataset. The trends here are as before. Figure 6 shows the impact of number of test samples on detection.

Figure: Figure 2: Effect of the amount of (random token replacement) corruption on detection pAUC (flat scheme; mixed $T$’s) with 1% max FPR.
Refer to caption: extracted/5897332/plots/pauc_pcor.png

Figure: Figure 3: Left: Histogram of the average entropy (nats) in the LLM’s underlying next-token distribution across non-watermarked response tokens. Right: A lower bound for ROC-AUC predicted by Theorem 4.2 as a function of the entropy term $\alpha$ for the range of values we observe empirically. When $m$ is large, $\alpha$ becomes a reasonable estimator of the LLM’s entropy.
Refer to caption: extracted/5897332/plots/ent_hist.png

Figure: Figure 4: Left: A lower bound for ROC-AUC predicted by Theorem 4.2 as a function of $m$ (using optimal $\alpha=\log(m)$). Right: Same plot, but as a function of $T$ (again, using optimal $\alpha$).
Refer to caption: extracted/5897332/plots/auc_theory_m.png

Figure: Figure 5: Given a distribution over the vocabulary (taken to be of size 32k), we can estimate $\alpha$ for finite $m$ via simulation (1000 trials). We observe that when the underlying next-token distribution is uniform, $\alpha\approx\log(m)$ in a practical range for $m$. However, when the underlying distribution is Zipf (less entropy), $\alpha$ quickly deviates from $\log(m)$ as $m$ grows and the probability of sampling duplicate tokens increases.
Refer to caption: extracted/5897332/plots/sim_ent.png

**Table 2: Results (10% corruption, 1% max FPR) for $U(0,1)$ when a meta $p$-value is used for scoring, wherein the $T$ $n$-gram-level $p$-values are combined using Fisher’s method. The $k=1$ setting is precisely a stochastic version of Aaronson Corrected. AUCs, pAUCS, and their standard errors are scaled by 100.**
|  | PPL | LH | AUC | pAUC | C. AUC | C. pAUC |
| --- | --- | --- | --- | --- | --- | --- |
| Max Std. Error | 0.03 | 0.002 | 0.1 | 0.1 | 0.2 | 0.1 |
| Unif. Fisher $p$-value |  |  |  |  |  |  |
| Flat $(k=1)$<br>$2$ | 3.46 | 0.597 | 86.3 | 62.3 | 75.8 | 54.7 |
| $4$ | 3.36 | 0.604 | 94.8 | 79.0 | 87.6 | 66.4 |
| $16$ | 3.20 | 0.618 | 97.9 | 90.0 | 94.0 | 80.2 |
| $32$ | 3.06 | 0.629 | 98.2 | 91.7 | 94.9 | 82.7 |
| $512$ | 2.63 | 0.668 | 98.5 | 93.0 | 95.7 | 85.5 |
| $1024$ | 2.61 | 0.670 | 98.5 | 93.2 | 95.7 | 85.8 |
| Flat $(k=10)$<br>$2$ | 4.10 | 0.568 | 78.9 | 53.1 | 67.4 | 51.0 |
| $4$ | 4.06 | 0.572 | 91.2 | 65.3 | 80.5 | 55.0 |
| $16$ | 3.86 | 0.583 | 97.1 | 82.8 | 90.9 | 68.1 |
| $32$ | 3.80 | 0.587 | 97.9 | 86.3 | 92.7 | 72.7 |
| Flat $(k=50)$<br>$2$ | 3.79 | 0.581 | 65.5 | 50.5 | 57.1 | 50.2 |
| $4$ | 3.76 | 0.584 | 78.4 | 52.0 | 66.1 | 50.7 |
| $16$ | 3.72 | 0.586 | 89.8 | 60.2 | 77.9 | 53.1 |
| $32$ | 3.67 | 0.589 | 92.0 | 64.7 | 80.7 | 54.5 |

**Table 3: Results when the likelihood-ratio test is used for scoring in place of $p$-values. When $F=U(0,1)$, the null and alternative likelihoods are estimated non-parametrically using kernel density estimation (KDE). When $F=-\text{Gamma}(1/k,1)$, the densities given in Theorem 4.4 are used. AUCs, pAUCs, and their standard errors are scaled by 100.**
|  | PPL | LH | AUC | pAUC | C. AUC | C. pAUC |
| --- | --- | --- | --- | --- | --- | --- |
| Max Std. Error | 0.03 | 0.002 | 0.1 | 0.3 | 0.2 | 0.1 |
| Unif. KDE LRT |  |  |  |  |  |  |
| Flat $(k=1)$<br>$2$ | 3.46 | 0.597 | 78.1 | 57.7 | 64.4 | 51.5 |
| $4$ | 3.36 | 0.604 | 73.9 | 56.0 | 60.7 | 51.2 |
| $16$ | 3.20 | 0.618 | 66.6 | 53.9 | 56.7 | 51.3 |
| $32$ | 3.06 | 0.629 | 64.0 | 53.6 | 55.2 | 51.3 |
| $512$ | 2.63 | 0.668 | 56.2 | 51.3 | 50.4 | 50.3 |
| $1024$ | 2.61 | 0.670 | 55.4 | 51.1 | 49.9 | 50.2 |
| Flat $(k=10)$<br>$2$ | 4.10 | 0.568 | 84.1 | 58.0 | 72.8 | 53.1 |
| $4$ | 4.06 | 0.572 | 94.8 | 72.9 | 83.9 | 58.7 |
| $16$ | 3.86 | 0.583 | 97.8 | 85.1 | 88.3 | 64.2 |
| $32$ | 3.80 | 0.587 | 97.3 | 85.6 | 86.9 | 64.0 |
| Flat $(k=50)$<br>$2$ | 3.79 | 0.581 | 69.0 | 51.6 | 60.9 | 50.9 |
| $4$ | 3.76 | 0.584 | 83.1 | 55.6 | 71.0 | 52.4 |
| $16$ | 3.72 | 0.586 | 94.0 | 68.2 | 81.8 | 56.2 |
| $32$ | 3.67 | 0.589 | 95.5 | 72.5 | 84.0 | 57.9 |
| Gamma Exact LRT |  |  |  |  |  |  |
| Flat $(k=1)$<br>$2$ | 3.45 | 0.598 | 76.6 | 57.0 | 63.8 | 51.6 |
| $4$ | 3.44 | 0.600 | 74.4 | 55.2 | 61.5 | 51.2 |
| $16$ | 3.17 | 0.623 | 68.3 | 53.6 | 57.8 | 51.3 |
| $32$ | 3.04 | 0.634 | 65.5 | 53.5 | 56.2 | 51.5 |
| Flat $(k=10)$<br>$2$ | 4.07 | 0.570 | 82.9 | 58.4 | 70.3 | 52.8 |
| $4$ | 4.01 | 0.573 | 89.4 | 67.5 | 73.4 | 54.1 |
| $16$ | 3.96 | 0.577 | 85.1 | 61.4 | 68.0 | 51.7 |
| $32$ | 3.93 | 0.580 | 82.1 | 57.7 | 65.7 | 51.2 |

**Table 4: Results (10% corruption, 1% max FPR) when $F$ is $N(0,1)$ or $\chi_{2}^{2}$ and $p$-values are used for scoring. AUCs, pAUCS, and their standard errors are scaled by 100.**
|  | PPL | LH | AUC | pAUC | C. AUC | C. pAUC |
| --- | --- | --- | --- | --- | --- | --- |
| Max Std. Error | 0.04 | 0.002 | 0.1 | 0.2 | 0.1 | 0.2 |
| $F=N(0,1)$ |  |  |  |  |  |  |
| Flat $(k=1)$<br>$2$ | 3.47 | 0.597 | 90.4 | 68.7 | 81.7 | 58.5 |
| $4$ | 3.36 | 0.605 | 95.9 | 83.0 | 90.2 | 70.7 |
| $16$ | 3.15 | 0.622 | 98.0 | 90.6 | 94.2 | 80.4 |
| $32$ | 3.05 | 0.631 | 98.2 | 91.8 | 94.9 | 82.2 |
| $512$ | 2.72 | 0.661 | 98.5 | 92.9 | 95.4 | 83.8 |
| $1024$ | 2.70 | 0.663 | 98.5 | 93.0 | 95.4 | 84.1 |
| Flat $(k=10)$<br>$2$ | 4.13 | 0.567 | 84.1 | 56.3 | 73.3 | 52.1 |
| $4$ | 4.02 | 0.573 | 94.2 | 73.3 | 85.8 | 59.8 |
| $16$ | 3.93 | 0.579 | 98.0 | 87.9 | 93.2 | 74.5 |
| $32$ | 3.84 | 0.584 | 98.4 | 90.0 | 94.1 | 77.7 |
| Flat $(k=50)$<br>$2$ | 3.82 | 0.580 | 71.0 | 50.9 | 62.5 | 50.4 |
| $4$ | 3.73 | 0.585 | 83.8 | 53.9 | 72.4 | 51.5 |
| $16$ | 3.69 | 0.588 | 93.0 | 67.5 | 83.1 | 55.9 |
| $32$ | 3.67 | 0.589 | 94.5 | 72.7 | 85.6 | 58.6 |
| $F=\chi_{2}^{2}$ |  |  |  |  |  |  |
| Flat $(k=1)$<br>$2$ | 3.45 | 0.597 | 86.2 | 62.1 | 75.5 | 54.5 |
| $4$ | 3.39 | 0.602 | 94.8 | 79.1 | 87.8 | 66.8 |
| $16$ | 3.20 | 0.617 | 97.9 | 90.1 | 93.9 | 80.1 |
| $32$ | 3.08 | 0.627 | 98.2 | 91.7 | 94.9 | 82.9 |
| $512$ | 2.98 | 0.644 | 98.7 | 95.2 | 96.7 | 89.6 |
| $1024$ | 3.03 | 0.641 | 98.8 | 95.7 | 97.0 | 90.5 |
| Flat $(k=10)$<br>$2$ | 4.12 | 0.567 | 81.6 | 54.4 | 69.8 | 51.4 |
| $4$ | 4.04 | 0.573 | 93.5 | 70.3 | 84.0 | 57.7 |
| $16$ | 3.84 | 0.585 | 98.1 | 87.5 | 93.1 | 74.1 |
| $32$ | 3.65 | 0.596 | 98.7 | 90.6 | 94.7 | 78.6 |
| Flat $(k=50)$<br>$2$ | 3.77 | 0.583 | 68.1 | 50.6 | 58.7 | 50.2 |
| $4$ | 3.74 | 0.585 | 82.0 | 52.9 | 69.4 | 51.0 |
| $16$ | 3.68 | 0.588 | 92.9 | 65.6 | 81.9 | 55.0 |
| $32$ | 3.65 | 0.591 | 94.5 | 71.5 | 84.5 | 57.7 |

**Table 5: Average per-token likelihoods and detection performance when the negative class is taken to be non-watermarked generations sampled with temperature 1. For paraphrasing, target lengths of {150, 200, 250} are used in calculating AUC and pAUC. The trends here are consistent with those discussed in the main text, where the negative class consists of non-watermarked argmax / greedy generations and perplexity is used to measure distortion. AUCs and pAUCS are scaled by 100.**
|  | LH | AUC | pAUC | C. AUC | C. pAUC | P. AUC | P. pAUC |
| --- | --- | --- | --- | --- | --- | --- | --- |
| Greedy Decoding | 0.814 | - | - | - | - | - | - |
| Random Sampling | 0.593 | - | - | - | - | - | - |
| Aaronson | 0.654 | 71.8 | 67.7 | 65.7 | 62.6 | 53.9 | 50.5 |
| Aaronson Cor. | 0.654 | 98.3 | 92.9 | 95.4 | 84.7 | 58.8 | 50.7 |
| Kirchenbauer<br>$0.5$ | 0.596 | 70.7 | 51.7 | 68.3 | 51.2 | 49.0 | 49.8 |
| $1$ | 0.594 | 85.4 | 59.9 | 81.9 | 56.5 | 52.9 | 49.9 |
| $2$ | 0.569 | 96.6 | 82.5 | 94.8 | 76.5 | 58.4 | 50.3 |
| $3$ | 0.522 | 99.1 | 94.0 | 98.4 | 90.4 | 63.4 | 51.5 |
| $4$ | 0.493 | 99.8 | 98.2 | 99.6 | 96.6 | 66.4 | 52.7 |
| Kuditipudi | 0.592 | 85.8 | 76.5 | 85.1 | 74.3 | 75.9 | 53.2 |
| Flat $(k=1)$<br>$2$ | 0.597 | 90.5 | 69.7 | 82.6 | 59.4 | 50.5 | 50.3 |
| $4$ | 0.604 | 96.0 | 83.7 | 90.6 | 71.4 | 51.3 | 50.6 |
| $16$ | 0.618 | 97.7 | 90.2 | 94.1 | 79.9 | 52.7 | 51.1 |
| $32$ | 0.629 | 97.9 | 90.7 | 94.4 | 80.8 | 53.0 | 50.8 |
| $512$ | 0.668 | 97.8 | 90.5 | 94.3 | 80.5 | 54.6 | 51.3 |
| $1024$ | 0.670 | 97.8 | 90.5 | 94.2 | 80.5 | 52.8 | 51.1 |
| Flat $(k=10)$<br>$2$ | 0.568 | 84.0 | 56.5 | 74.3 | 52.3 | 49.0 | 50.0 |
| $4$ | 0.572 | 94.1 | 73.8 | 86.2 | 60.2 | 51.3 | 50.3 |
| $16$ | 0.583 | 97.9 | 87.7 | 93.2 | 74.2 | 54.3 | 50.7 |
| $32$ | 0.587 | 98.3 | 89.7 | 94.2 | 77.7 | 55.0 | 50.8 |
| Flat $(k=50)$<br>$2$ | 0.581 | 70.5 | 50.9 | 63.1 | 50.5 | 47.0 | 50.0 |
| $4$ | 0.584 | 83.5 | 54.1 | 72.7 | 51.6 | 49.4 | 50.0 |
| $16$ | 0.586 | 93.0 | 67.9 | 83.7 | 56.3 | 50.5 | 50.1 |
| $32$ | 0.589 | 94.5 | 72.9 | 86.0 | 59.0 | 51.1 | 50.5 |
| Rec. $(k=1)$<br>$4$ | 0.601 | 93.9 | 78.2 | 87.3 | 65.8 | 48.4 | 50.4 |
| $16$ | 0.607 | 95.4 | 83.5 | 90.8 | 72.5 | 53.4 | 50.8 |
| $32$ | 0.612 | 96.5 | 85.8 | 92.0 | 74.5 | 49.4 | 50.8 |
| 512 | 0.632 | 97.4 | 88.6 | 92.9 | 77.5 | 50.4 | 51.2 |
| Rec. $(k=10)$<br>$4$ | 0.567 | 89.6 | 64.9 | 80.3 | 55.6 | 48.0 | 50.0 |
| $16$ | 0.568 | 93.6 | 74.8 | 87.0 | 62.4 | 52.9 | 50.4 |
| $32$ | 0.573 | 95.1 | 78.0 | 88.6 | 64.4 | 50.6 | 50.3 |
| Rec. $(k=50)$<br>$4$ | 0.582 | 75.9 | 52.2 | 67.0 | 51.0 | 46.5 | 49.9 |
| $16$ | 0.583 | 81.5 | 55.0 | 73.7 | 52.2 | 51.4 | 50.2 |
| $32$ | 0.582 | 84.0 | 56.6 | 75.3 | 52.6 | 49.4 | 50.0 |

**Table 6: Main results (mixed $T$’s for AUC and pAUC where max FPR is 1%) for Gemma-7B-instruct on the *eli5-category* test split. AUC and pAUC are scaled by 100. We observe the same trends here as with Mistral-7B-instruct on *databricks-dolly-15k*. When $k=1$ and $m=1024$ (white-box setting) we are slightly better in perplexity and detection (sans corruption) than Kuditipudi et al. () and on-par with Aaronson (). Kirchenbauer et al. () can always outperform on detection by cranking up $\delta$, but when matched on perplexity, we achieve better detection. For example, $\delta=0.5$ gives perplexity of 1.649 and AUC of 61.6% whereas we achieve perplexities / AUC’s of 1.610 and 93.2% when $k=1,m=1024$ and even 1.645 / 89.7% when $k=50,m=16$ (black-box).**
|  | PPL | LH | AUC | pAUC |
| --- | --- | --- | --- | --- |
| Greedy Decoding | 1.313 | 0.872 | - | - |
| Random Sampling | 1.627 | 0.811 | - | - |
| Aaronson | 1.619 | 0.814 | 61.0 | 57.8 |
| Aaronson Cor. | 1.619 | 0.814 | 93.0 | 70.9 |
| Kirchenbauer<br>$0.5$ | 1.649 | 0.808 | 61.6 | 50.7 |
| $1$ | 1.673 | 0.803 | 72.1 | 52.3 |
| $2$ | 1.836 | 0.782 | 87.8 | 63.0 |
| $3$ | 2.159 | 0.743 | 95.3 | 78.5 |
| $4$ | 2.847 | 0.683 | 98.3 | 90.0 |
| Kuditipudi | 1.615 | 0.814 | 58.4 | 51.0 |
| Flat $(k=1)$<br>$2$ | 1.631 | 0.810 | 77.1 | 53.6 |
| $4$ | 1.623 | 0.811 | 87.0 | 61.7 |
| $16$ | 1.621 | 0.812 | 92.4 | 70.3 |
| $32$ | 1.615 | 0.812 | 92.8 | 71.9 |
| $512$ | 1.610 | 0.814 | 93.2 | 73.1 |
| $1024$ | 1.610 | 0.814 | 93.2 | 72.9 |
| Flat $(k=10)$<br>$4$ | 1.657 | 0.807 | 89.4 | 61.7 |
| $16$ | 1.653 | 0.808 | 94.7 | 75.0 |
| Flat $(k=50)$<br>$4$ | 1.652 | 0.808 | 80.5 | 52.6 |
| $16$ | 1.645 | 0.810 | 89.7 | 60.4 |
| Rec. $(k=1)$<br>$4$ | 1.623 | 0.813 | 82.1 | 57.0 |
| $16$ | 1.621 | 0.812 | 87.5 | 63.0 |
| $32$ | 1.630 | 0.810 | 88.1 | 63.9 |
| $512$ | 1.615 | 0.815 | 90.0 | 66.7 |
| Rec. $(k=10)$<br>$4$ | 1.665 | 0.805 | 84.0 | 56.2 |
| $16$ | 1.662 | 0.806 | 89.6 | 64.4 |
| Rec. $(k=50)$<br>$4$ | 1.664 | 0.806 | 73.2 | 51.2 |
| $16$ | 1.653 | 0.808 | 79.4 | 53.5 |

Figure: Figure 6: Impact of number of test samples $T$ on detection performance (flat scheme) for Gemma-7B-instruct on *eli5-category*.
Refer to caption: extracted/5897332/plots/eli5_auc_T.png

Figure: Figure 7: Detection performance (TPR at 1% FPR) of the likelihood ratio test (LRT) predicted by Theorem 4.4. Left: Effect of $m$, the number of sampled sequences, for various sequence lengths $k$, when the number of test samples $T=100$. Right: Effect of $T$ for various $m$’s when $k=50$. We see that degradation due to large $k$ can be offset by using a larger $m$ and that the hit from small $m$ can be compensated by large $T$.
Refer to caption: extracted/5897332/plots/gamma_lrt_m.png

**Table 7: Detection performance (mixed $T$’s) when a sum-based $p$-value is used in the length correction of Aaronson (). We observe slightly worse performance than using Fisher’s method to combine the $p$-values of individual tests. AUCs and pAUCs are scaled by 100. For paraphrasing, target lengths of {150, 200, 250} are used in computing AUC and pAUC.**
|  | AUC | pAUC | C. AUC | C. pAUC | P. AUC | P. pAUC |
| --- | --- | --- | --- | --- | --- | --- |
| Aaronson Cor. (sum $p$-value) | 97.1 | 75.2 | 92.5 | 62.9 | 57.3 | 50.1 |

### A.3 Omitted Proofs

###### Lemma A.1 .

Assume all draws from $\texttt{LM}\left(\;\cdot\;|\;P;\;k\right)$ are i.i.d. with distribution $\mu$ and that the unique seeds across $n$-grams and sequences, $\{S_{i,l}\}_{i,l}$ are conditionally independent given the counts of the sampled sequences. Then the output of any number of calls to WatermarkSingle with LM using key $K$ are also i.i.d. with distribution $\mu$.

###### Proof.

For concreteness, let $\tilde{m}$ be the number of calls to WatermarkSingle, where the $v$-th call draws $m$ samples $\mathbf{Q}_{v}=\left\{Q_{(v,1)},\dots,Q_{(v,m)}\right\}$ from $\texttt{LM}\left(\;\cdot\;|\;P;\;k\right)$. First we show (mutual) independence. We note that because $F$, $m$, $K$, $P$ are all fixed, non-random quantities, the watermark selection process embodied in Algorithm 1 can be seen as a *deterministic* function $\psi_{F,m,K,P}$ that takes $m$ input sequences $\mathbf{Q}_{v}$ and outputs one of them. The randomness in the deduplication of $n$-grams is a non-issue since it is independent across calls. Since functions of independent random variables are independent and
$\left\{\mathbf{Q}_{v}\right\}_{v=1}^{\tilde{m}}$ is independent, so is $\left\{\psi_{F,m,K,P}\left(\mathbf{Q}_{v}\right)\right\}_{v=1}^{\tilde{m}}$. This proves independence.

Now, we prove that the outputs are identically distributed with the same distribution as their inputs. To do this, consider the $v$-th call in isolation and for ease of notation, let $\left\{Q_{1},\dots,Q_{m}\right\}=\mathbf{Q}_{v}$ and $X_{w}=\psi_{F,n,K,P}(\mathbf{Q}_{v})$. Let $\{(X_{1},c_{1}),\dots,(X_{j},c_{j})\}$ be the unique sequences and corresponding counts. Note that the $\{(X_{i},c_{i})\}_{i}$ need not be independent (it is easy to come up with a counter-example). Let $S_{i}$ be the integer seeds for $X_{i}$ after deduplication. Conditioned on $(c_{1},\dots,c_{j})$, $\{S_{i,l}\}_{i,l}$ is independent and so $\{R_{i,l}\}_{i,l}$ consists of *i.i.d.* draws from $F$ by virtue of pseudorandomness. As $F$ is also continuous, we have that when conditioned on $(c_{1},\dots,c_{j})$, $u_{i}\overset{iid}{\sim}U(0,1)$ for $i=1,\dots,j$, by the inverse-sampling theorem.

Let $x$ be any sequence. We wish to show that ${\mathbb{P}}(X_{w}=x)=\mu(x)$. Let $c=\sum_{i}\mathbf{1}[Q_{i}=x]$. The independence of the $\mathbf{1}[Q_{i}=x]$’s follows from the independence of the $Q_{i}$’s, and thus $c\sim\text{Binomial}(m,\mu(x))$.
Clearly, ${\mathbb{P}}(\{x\;\text{selected}\}\;|\;c=0)=0$. If $c>0$ then obviously one of the $X_{i}$’s is $x$, and we can, without loss of generality, label $X_{1}=x$ and $c_{1}=c$, so that ${\mathbb{P}}(\{x\;\text{selected}\}\;|\;c=i)={\mathbb{P}}(\{X_{1}\;\text{
selected}\}\;|\;c_{1}=i)$. Now,

$$ $\displaystyle{\mathbb{P}}(\{X_{1}\;\text{selected}\}\;|\;c_{1},\dots,c_{j})$ $\displaystyle={\mathbb{P}}\left(\left\{1=\operatorname{argmax}_{t}u_{t}^{m/c_{ t}}\right\}\;\middle|\;c_{1},\dots,c_{j}\right)$ $\displaystyle={\mathbb{P}}\left(\left\{1=\operatorname{argmax}_{t}\frac{\log(u _{t})}{c_{t}/m}\right\}\;\middle|\;c_{1},\dots,c_{j}\right)$ $\displaystyle={\mathbb{P}}\left(\left\{1=\operatorname{argmin}_{t}\log(-\log(u _{t}))-\log(c_{t}/m)\right\}\;\middle|\;c_{1},\dots,c_{j}\right)$ $\displaystyle={\mathbb{P}}\left(\left\{1=\operatorname{argmax}_{t}-\log(-\log( u_{t}))+\log(c_{t}/m)\right\}\;\middle|\;c_{1},\dots,c_{j}\right).$ $$

Let $g_{t}=-\log(-\log(u_{t}))$. It is a known fact that if $u_{t}\overset{iid}{\sim}U(0,1)$, then $g_{t}\overset{iid}{\sim}\text{Gumbel}(0,1)$.
Now we can apply what is often referred to the "Gumbel-Max trick" in machine learning. Conditioned on $(c_{1},\dots,c_{j})$,

$$ $\displaystyle\operatorname{argmax}_{t}g_{t}+\log(c_{t}/m)\sim\text{Categorial} \left(\frac{c_{t}/m}{\sum_{t}{c_{t}/m}}\right)_{t}=\text{Categorial}\left(c_{t }/m\right)_{t}.$ $$

Thus,

$$ $\displaystyle{\mathbb{P}}(\{X_{1}\;\text{selected}\}\;|\;c_{1}=i)$ $\displaystyle=\sum_{c_{2},\dots,c_{j}}\frac{{\mathbb{P}}(\{X_{1}\;\text{ selected}\}\;|\;c_{1}=i,c_{2},\dots,c_{j}){\mathbb{P}}(c_{1}=i,c_{2},\dots,c_{ j})}{{\mathbb{P}}(c_{1}=i)}$ $\displaystyle=\frac{i/m\;{\mathbb{P}}(c_{1}=i)}{{\mathbb{P}}(c_{1}=i)}=i/m.$ $$

Putting it all together, we have that

$$ $\displaystyle{\mathbb{P}}(X_{w}=x)$ $\displaystyle=\sum_{i=0}^{m}{\mathbb{P}}(\{x\;\text{selected}\}\;|\;c=i){ \mathbb{P}}(c=i)$ $\displaystyle=\sum_{i=0}^{m}\frac{i}{m}\binom{m}{i}\mu(x)^{i}(1-\mu(x))^{m-i}$ $\displaystyle=\frac{1}{m}m\mu(x)=\mu(x).$ $$

We have shown that the outputs of WatermarkSingle are mutually independent and carry the same distribution $\mu$ as their inputs.
∎

###### Remark .

The proof of Lemma A.1 treats the secret key $K$ as fixed (possibly unknown); treating it as random changes the story, as we illustrate with the following toy example.

Suppose that regardless of the conditioning prompt, the LM outputs one of two sequences — $x_{1}$ or $x_{2}$ with equal probability. Let $u_{i}=\textsc{ScoreSeqs}(F,(x_{i}),K,n,P)$ for $i\in\{1,2\}$.
If $m$ is very large, then it becomes very likely that $X_{1}=x_{1}$, $X_{2}=x_{2}$ (modulo the labeling) and $c_{1}\approx c_{2}\approx m/2$ and so $\operatorname{argmax}_{i=1}^{2}u_{i}^{m/c_{i}}\approx\operatorname{argmax}_{i}
u_{i}$. The outputs to two sequential calls to WatermarkSingle should not be independent, because the output and key are dependent and the key is shared across calls. Concretely, if the output to the first call is $x_{1}$ we learn that our scheme with key $K$ prefers $x_{1}$ over $x_{2}$, and so we will likely output $x_{1}$ in the second call. In contrast, if we had not observed the first call (and our prior on the key had not been updated), we may have returned each sequence with equal probability.

###### Proof of Theorem 4.1 .

We first show that WatermarkSingle and WatermarkRecursive are distortion-free and then that autoregressive calls to them as done by Watermark preserves this property.

To show WatermarkSingle is distortion-free, we observe that the LM argument supplied is the true underlying language model $\mu$ and that our stochastic samples from the model are i.i.d., so we can apply Lemma A.1 directly.

Distortion-free for WatermarkRecursive follows easily from induction on $t$, the number of keys (and hence the number of recursive calls). When $t=1$, the LM is the true underlying language model, so the outputs are i.i.d. from $\mu$. We get $t=v+1$ by combining Lemma A.1 with the inductive step — that the outputs of WatermarkRecursive with keys $(K_{2},\dots,K_{v+1})$ are i.i.d. from $\mu$.

Finally, we show that autoregressive decoding where sequences no longer than $k$ tokens are generated one at a time via watermarking continues to be distortion-free.

To do this, we introduce two sets of random variables: $\{X_{u}^{(i)}\}_{i=1}^{\infty}$ represents $k$-sized chunks of the model’s response when watermarking is *not* employed — that is, $X_{u}^{(i)}$ represents non-watermarked response tokens for indices $(i-1)k+1$ to $ik$. Unused chunks can be set to a sentinel value like $\phi$. $\{X_{w}^{(i)}\}_{i}$ represents the same collection but when Watermark is employed. Let $x$ be a sequence of any length. Partition $x$ into contiguous $k$-sized chunks $(x_{1},\dots,x_{t})$. Note that $x_{t}$ may have length less than $k$ if the stop-token was reached in that chunk, but all other chunks have exactly $k$ tokens. With $P$ as the original prompt, we need to show ${\mathbb{P}}(X_{w}=x\mid P)={\mathbb{P}}(X_{u}=x\mid P)$, where $X_{w}$ and $X_{u}$ are the watermarked and non-watermarked responses of any length.

$$ $\displaystyle{\mathbb{P}}(X_{w}=x\mid P)$ $\displaystyle={\mathbb{P}}(X_{w}^{(t)}=x_{t}\mid X_{w}^{(t-1)}=x_{t-1},\dots,X _{w}^{(1)}=x_{1},P)\cdots{\mathbb{P}}(X_{w}^{(1)}=x_{1}\mid P)$ $\displaystyle={\mathbb{P}}(X_{w}^{(1)}=x_{t}\mid(P,x_{1},\dots,x_{t-1}))\cdots {\mathbb{P}}(X_{w}^{(1)}=x_{1}\mid P)$ Because WatermarkSingle and WatermarkRecursive are distortion-free: $\displaystyle={\mathbb{P}}(X_{u}^{(1)}=x_{t}\mid(P,x_{1},\dots,x_{t-1}))\cdots {\mathbb{P}}(X_{u}^{(1)}=x_{1}\mid P)$ $\displaystyle={\mathbb{P}}(X_{u}=x).$ $$

∎

###### Proof of Theorem 4.3 .

First consider the flat scheme. Under the null, given our assumption of independence, $R_{j}\overset{iid}{\sim}F$, so $F_{|R|}\left(\sum_{j}R_{j}\right)\sim{U(0,1)}$ and the result follows. For the recursive scheme, we know from the flat scheme and from assumed independence that $P_{j}\overset{iid}{\sim}{U(0,1)}$, where $P_{j}$ is the $p$-value associated with the $j$-th key. Thus, $y\sim\chi_{2|P|}^{2}$ so that $\chi_{2|P|}^{2}(y)\sim{U(0,1)}$.
∎

###### Lemma A.2 .

Assume the conditions of Theorem 4.2. Conditioned on the counts $c$ of each token in the vocabulary, and which token id $i^{*}$ was selected (i.e. is the argmax), $u_{i^{*}}\sim\text{Beta}(m/c_{i^{*}},1)$.

###### Proof of Lemma A.2 .

Let $z_{i}=-m\log(u_{i})/c_{i}$, where $u_{i}\overset{iid}{\sim}U(0,1)$. Then, $z_{i}\sim\text{Exp}(c_{i}/m)$ and

$$ $\displaystyle i^{*}$ $\displaystyle=\operatorname{argmax}_{i=1}^{j}u_{i}^{m/c_{i}}=\operatorname{ argmin}_{i}-m\log(u_{i})/c_{i}=\operatorname{argmin}_{i}z_{i}.$ $$

By nice properties of the Exponential, we have that

$$ $\displaystyle z_{i^{*}}$ $\displaystyle\sim\text{Exp}\left(\sum_{i}\frac{c_{i}}{m}\right)=\text{Exp}(1).$ $$

$u_{i^{*}}=\exp(-c_{i^{*}}z_{i^{*}}/m)$, so

$$ $\displaystyle{\mathbb{P}}(u_{i^{*}}\leq t)={\mathbb{P}}(z_{i^{*}}\geq-m\log(t) /c_{i^{*}})=\exp(m\log(t)/c_{i^{*}})=t^{m/c_{i^{*}}}.$ $$

Differentiating this w.r.t to $t$, we recover the pdf of $\text{Beta}(m/c_{i^{*}},1)$.
∎

###### Proof of Theorem 4.2 .

$F$ is ${U(0,1)}$. The detection score is $F_{T}\left(\sum_{j}R_{j}\right)$ with $R_{j}\overset{iid}{\sim}F$ under $\mathcal{H}_{0}$ and when conditioned on the counts $C$ and the argmax token ids $I^{*}$, $R_{j}\sim\text{Beta}\left(m/C_{j,I^{*}_{j}},1\right)$ under $\mathcal{H}_{1}$. Redefine $s_{0}$ and $s_{1}$ to be $\sum_{j}R_{j}$ under $\mathcal{H}_{0}$ and $\mathcal{H}_{1}$ respectively.

$$ $\displaystyle{\mathbb{P}}(F_{T}(s_{1})\geq F_{T}(s_{0}))={\mathbb{P}}(s_{1} \geq s_{0})={\mathbb{E}}_{t}(s_{1}\geq t),$ $$

where $t\sim\text{IrwinHall}(T)$ since $s_{0}$ is the sum of $T$ i.i.d. ${U(0,1)}$’s. Our task now is to find a lower-bound for $s_{1}$. Noting independence across tokens and that $R_{j}\in[0,1]$, we can use Popoviciu’s bound on variance to obtain,

$$ $\displaystyle{\mathbb{V}}(s_{1})=\sum_{j}{\mathbb{V}}(R_{j})\leq\frac{T}{4}(1- 0)^{2}=T/4.$ $$

Plugging in the expectation of a Beta and recalling that when conditioned on $C$, the probability that token $i$ in the vocabulary is the argmax token at step $j$ is $C_{j,i}/m$, we have

$$ $\displaystyle{\mathbb{E}}(s_{1})$ $\displaystyle=\sum_{j=1}^{T}{\mathbb{E}}_{C}\left(\sum_{i=1}^{V}\frac{C_{j,i}/ m}{1+C_{j,i}/m}\right).$ $$

With tedious calculation, it can be shown that

$$ $\displaystyle\frac{x}{1+x}$ $\displaystyle\geq\frac{x}{2}-\lambda x\log(x),\;\text{for}\;x=\frac{j}{m},j\in [1,\dots,m],\;\text{where}$ $\displaystyle\lambda$ $\displaystyle=\frac{1}{\log(m)}\left(\frac{m}{m+1}-\frac{1}{2}\right).$ $$

Thus,

$$ $\displaystyle{\mathbb{E}}(s_{1})$ $\displaystyle\geq\sum_{j=1}^{T}\left(\frac{1}{2}-\lambda{\mathbb{E}}_{C}\sum_{ i=1}^{V}\mathbf{1}\left[C_{j,i}>0\right]\;\frac{C_{j,i}}{m}\log\left(\frac{C_{ j,i}}{m}\right)\right).$ $\displaystyle=\sum_{j}1/2+\lambda\alpha=T/2+\lambda T\alpha.$ $$

With bounds on expectation and variance, we proceed to upper-bound the error.
Firstly, we have that,

$$ $\displaystyle{\mathbb{E}}(s_{1}-s_{0})$ $\displaystyle\geq T/2+\lambda T\alpha-T/2=\lambda T\alpha\geq 0,$ $\displaystyle{\mathbb{V}}(s_{1}-s_{0})$ $\displaystyle\leq T/4+T/12=T/3.$ $$

$$ $\displaystyle{\mathbb{P}}(s_{1}\leq s_{0})$ $\displaystyle={\mathbb{P}}(s_{1}-s_{0}-{\mathbb{E}}(s_{1}-s_{0})\leq-{\mathbb{ E}}(s_{1}-s_{0}))$ $\displaystyle\leq{\mathbb{P}}(s_{1}-s_{0}-{\mathbb{E}}(s_{1}-s_{0})\leq- \lambda T\alpha)$ $\displaystyle\leq\frac{{\mathbb{V}}(s_{1}-s_{0})}{{\mathbb{V}}(s_{1}-s_{0})+( \lambda T\alpha)^{2}}$ $\displaystyle\leq\frac{1}{1+3T\lambda^{2}\alpha^{2}},$ $$

where the penultimate line follows from Cantelli’s inequality. Thus, we have that

$$ $\displaystyle{\mathbb{P}}(s_{1}\geq s_{0})=1-{\mathbb{P}}(s_{1}\leq s_{0})\geq \frac{1}{1+1/(3T\lambda^{2}\alpha^{2})}.$ $$

∎

###### Proof of Theorem 4.4 .

Let $r$ be the PRF value for some $n$-gram from the text we wish to text. Let $F_{0}=-\text{Gamma}(1/k,\beta)$ with pdf $f_{0}$ and $F_{1}=-\text{Gamma}(1/k,m\beta)$ with pdf $f_{1}$. By definition, $r\sim F_{0}$ under $\mathcal{H}_{0}$.
By our assumptions, $c_{i}=1$ and $|R_{i}|=k,\;\forall i$. So, $\operatorname{argmax}_{i=1}^{m}u_{i}^{m/c_{i}}=\operatorname{argmax}_{i=1}^{m}
u_{i}=\operatorname{argmax}_{i}F_{k}\left(\sum_{j}R_{i,j}\right)=\operatorname
{argmax}_{i}\sum_{j}R_{i,j}=\operatorname{argmin}_{i}-\sum_{j}R_{i,j}$, where the second-to-last equality follows from the monotonicity of $F_{k}$. $-\sum_{j}R_{i,j}\sim\text{Gamma}(k/k,\beta)=\text{Exp}(1,\beta)$. $\sum_{j}R_{i^{*},j}\sim-\text{Exp}(1,m\beta)$, because the minimum of Exponentials is Exponential. Thus, $\forall j,\;R_{i^{*},j}\sim-\text{Gamma}(1/k,m\beta)=F_{1}$ and $r\sim F_{1}$ under $\mathcal{H}_{1}$.
Now let $R$ refer to the $T$ test-time PRF values. From the independence of test $n$-grams, the log-likelihood ratio test has score $s(R)=\sum_{i=1}^{T}\left(\log f_{1}(R_{i})-\log f_{0}(R_{i})\right)$ and the fact that it is the uniformly most powerful test follows directly from the Neyman–Pearson lemma. We now have that,

$$ $\displaystyle f_{0}(r)$ $\displaystyle=\frac{\beta^{1/k}}{\Gamma(1/k)}(-r)^{1/k-1}\exp(\beta r),$ $\displaystyle f_{1}(r)$ $\displaystyle=\frac{m^{1/k}\beta^{1/k}}{\Gamma(1/k)}(-r)^{1/k-1}\exp(m\beta r),$ $\displaystyle s(R)$ $\displaystyle=\frac{T}{k}\log(m)+(m-1)\beta\sum_{i=1}^{T}R_{i},\;\text{so that}$ $\displaystyle P_{\mathcal{H}_{0}}(s>t)$ $\displaystyle=P_{\mathcal{H}_{0}}\left((m-1)\beta\sum_{i}R_{i}>t-\frac{T}{k} \log(m)\right)=\text{Gamma}(T/k,\beta)\left(Q(t)\right),\;\text{and}$ $\displaystyle P_{\mathcal{H}_{1}}(s\leq t)$ $\displaystyle=P_{\mathcal{H}_{1}}\left((m-1)\beta\sum_{i}R_{i}\leq t-\frac{T}{ k}\log(m)\right)=1-\text{Gamma}(T/k,m\beta)\left(Q(t)\right),\;\text{where}$ $\displaystyle Q(t)$ $\displaystyle=\frac{T\log(m)/k-t}{(m-1)\beta}.$ $$

∎

###### Lemma A.1 .

###### Proof.

###### Remark .

###### Proof of Theorem 4.1 .

###### Proof of Theorem 4.3 .

###### Lemma A.2 .

###### Proof of Lemma A.2 .

###### Proof of Theorem 4.2 .

###### Proof of Theorem 4.4 .

## Peer Reviews

confidence: 5
contribution: 3
initial_rating: 1
presentation: 3
questions: All questions I list here are repeated from the "Weaknesses" section above:
- Can the authors elaborate on the decision to introduce the AUC until fixed FPR metric?
- Do the authors believe a false positive rate of 1% is a practical setting for real-world deployment?
- Can the authors extend their paraphrasing robustness evaluation to include longer texts and demonstrate that their watermark is as robust as best variants from prior work?
- Can the authors comment on the discrepancy between the blackbox-focused framing of the earlier sections of the paper, and the key results demonstrated and discussed in Sec. 5 being in the whitebox case?
- Can the authors comment on the statement that $k$ below text length $L$ is not as practical in the blackbox case, and include some experiments in the $k=L$ case?
- Can the authors compare their method to cited blackbox baselines or explain why this is not feasible?
soundness: 3
strengths: - While it is based on a generalization of ideas from existing schemes, the exact scheme proposed is to the best of my knowledge novel. The authors do a good job of exploring different variants of the scheme (e.g., CDF) in a principled way. 
- The theoretical results are sound. I especially appreciate that Theorem 4.2 is carefully placed into context and analyzed for various input values to demonstrate its implications. 
- Experiments are very thorough, involve important aspects such as quality evaluation with LLM judges and paraphasing attacks, and explore various scenarios and scheme ablations, making interesting observations.
- Whitebox results seem convincing (up to some reservations below), making the case for significance.
- While I have some issues with the method section (see below), the theory and experiments parts of the paper are very well written.
summary: The paper proposes an LLM watermarking scheme that is applicable in black-box scenarios, i.e., when the party watermarking the text does not have access to the sampling procedure, but also in standard white-box cases. The authors prove the distortion free property and the lower bound on AUC. Extensive experiments among else evaluate watermark TPR/FPR, text quality, and robustness under token replacement and paraphrasing.
weaknesses: As a meta point, the authors are using the 2024 style file and should update it to the latest version to avoid desk rejection. I understand that this is an honest mistake, but in particular the lack of usual line numbers is making it hard to refer to particular parts of the writeup.

The weaknesses of the paper are in my view:

(1) Limitations of the evaluation setup
- The authors recognize that AUC is not the most practically relevant metric yet resolve this by proposing a new metric (AUC below fixed FPR), instead of using the more standard TPR @ fixed low FPR. As this is instantiated with a still high FPR of 1% the metric is still dominated by results at impractical FPRs. Can the authors elaborate on the decision to introduce this metric? Do the authors believe a false positive rate of 1% is a practical setting for real-world deployment?
- Prior work (Kirchenbauer 2023b among else) has already shown that short texts such as those studied here (~300 tokens) are not robust to paraphrasing, while (passive adversaries that do not learn the watermark beforehand) start being much less able to remove the best variants of KGW at above ~600 tokens. Can the authors extend their evaluation to include this setting and demonstrate that their watermark is equally or more robust?

(2) Despite being the title and the central framing of the paper, the practicality of the blackbox watermark is underdiscussed and not well substantiated. Perhaps framing the paper around the whitebox variant would have been more convincing. Namely: 
- As authors say, it can be hard to control token lengths of chat API responses. Further, and more importantly, it is not always possible to prefill the first $k$ tokens of the assistant response. This implies that the variant where $k$ is equal to text length is the most practical for blackbox models, yet is not evaluated, and there is no detailed discussion of this. As already for $k=50$ we can at most get 70 pAUC, it is likely that the practical variant would either not obtain good results, or need very high $m$. 
- The limitation of the blackbox setting that could be more explicitly mentioned/analyzed is that $len/k * m$ queries are needed to produce 1 text. For the practical setting above with high $m$ this can be prohibitively expensive. 
- The baselines (PostMark and Yang et al.) are not evaluated, yet they study the exact same blackbox setup. Can the authors explain this decision? Baselines being costly does not seem like a sound rationale, as they could still be evaluated along with their cost, which can then be compared to the cost of the proposed watermark. 

(3) Minor writing issues around the method description. In particular Sec. 3 is quite dense and not very friendly to readers aiming to understand the high-level idea behind the watermark. For example, $u_t$ is simply introduced but its components could be explained more intuitively, perhaps even through an example or supporting figures which are notably missing. Detail: $g(w)$ is introduced but not used later. 

Minor writing suggestions that are not treated as weaknesses:
- For consistency with prior work, it would be good to use the more standard scheme names such as KGW self-hash and ITS/EXP instead of introducing new aliases KB and K.
- It would be beneficial to label $m$ and $\delta$ in Table 1 as it is not immediatelly clear what they represent. 
- In "hyperparameters" section of the evaluation, it should be explicit that $F_k$, if I am not mistaken, is not chosen, but simply follows from the choice of $F$.

---

Update: The authors' repeated insults towards the reviewers and their highly inappropriate communication below clearly violate the code of conduct. This overshadows any technical merit of the paper and prevents me from engaging in discussion; I have updated my score accordingly.

---

confidence: 3
contribution: 2
initial_rating: 6
presentation: 3
questions: The "Related Work" section appears to suggest that Aaronson and Kirchenbauer et al. were the first to embed information in LLM outputs.
However, the paper "Neural Linguistic Steganography" did this as early as 2019.
soundness: 4
strengths: The paper seems to do a good job of optimizing both their scheme, and the schemes they compare against.
In particular, it is interesting that making the watermark detector of Aaronson length-aware improves performance as much as it does.
summary: A method of generating watermarked text using query access to a language model is described.
The method works by auto-regressively sampling short sequences of tokens, selecting the sequence with the highest watermark score.
The watermark score is similar to Aaronson's.
weaknesses: The ideas and method are straightforward adaptations of existing work.
The technique is essentially identical to Aaronson's, except that they use rejection sampling instead of the Gumbel-max trick.
The scheme is also only distortion-free under certain assumptions about the text, which essentially translate to it having consistently high entropy.

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 2
questions: Could you provide an example of watermarked text?
soundness: 2
strengths: The method is effective in a black-box setting. It only requires to sample sequences from LLMs.

The paper provides formal guarantees for detection performance.
summary: The paper proposes a method for watermarking language models in a black-box setting. It only requires sampling output sequences from language models.
weaknesses: The paper’s motivation could be articulated more clearly. The main motivation stems from the security risks associated with providing API access that exposes logits to third-party users for applying their own watermark. However, simpler methods could enhance security; for instance, instead of exposing logits, LLMs could offer APIs to gather specific information users want to integrate. Furthermore, the paper presents a zero-bit watermarking technique, which only detects whether a text is watermarked but cannot infer additional information from the watermark.

The paper could also benefit from a more comprehensive evaluation. For example, comparing the time complexity of the proposed method with baselines and providing examples of watermarked text would strengthen the paper.

---

confidence: 4
contribution: 2
initial_rating: 6
presentation: 2
questions: Questions are in weaknesses above.
soundness: 2
strengths: - The paper shows a solid theoretical analysis of the proposed scheme, as well as the distortion-free property that was claimed, establishing that the watermarked text is statistically indistinguishable from the original model's output.  They also provide a lower bound on detection performance, connecting it to the entropy of the language model's output and the number of samples used.
- The experimental results presented in the paper support the theoretical claims and demonstrate the effectiveness of the proposed scheme.  The authors conduct experiments on two popular LLM models, MISTRAL-7B-INSTRUCT and GEMMA-7B-INSTRUCT, and show that their scheme is competitive with or even superior to existing white-box watermarking schemes in terms of detection performance, text quality, and perplexity.
- The paper explores the robustness of the scheme to adversarial attacks - the impact of random token replacement and paraphrasing attacks. While paraphrasing proves to be a significant challenge, the scheme shows resilience to random token replacement. This analysis of robustness provides a realistic assessment of the scheme's strengths and limitations in practical settings. 
- The proposed framework is versatile and allows for various extensions and adaptations. For instance, it can be applied recursively, allowing multiple users to watermark the same model without interfering with each other. The scheme can also be adapted for white-box settings when next-token probabilities are available.
summary: In this paper, a black-box watermarking scheme for LLMs is proposed. The idea is to enable watermarking with only sampling access i.e., without requiring white-box access to a model’s next-token probability distribution. The scheme allows third-party users with API-only access to embed watermarks without altering the distribution of generated text, achieving a distortion-free watermark (generated content is indistinguishable from the original output). It supports multiple secret keys, making it possible for different users to watermark the same model recursively without interference. The authors also provide theoretical guarantees on detection performance, false-positive rates, and robustness against adversarial attacks.
weaknesses: - Practicality: What do the authors mean when they claim their method enables end users with only API access to embed watermarks? I am unclear about the motivation behind this approach. Is it practical for users to watermark a model that they do not own? What is the reasoning here, particularly if watermarking serves as a security measure to prevent model misuse? Wouldn't this imply that the method could also allow potential attackers access to the watermark?
- Experiments and General Format of the Paper: The paper lacks clarity and structure, making it difficult to fully grasp the motivation behind the proposed approach. While there may be a valuable contribution here, the current format obscures its impact. Figures and tables are largely separated from the sections where they are referenced; it would improve readability to place these closer to the relevant results. The theoretical guarantees could be moved to the end or even to an appendix, allowing more space for additional results in the main body. The motivation behind the approach needs clearer explanation—if the goal is to "give power back to the people," it should clarify why this is relevant, considering that users are not model owners, and watermarking aims primarily to prevent misuse. A well-articulated motivation would strengthen this section. Section 5.3 isn't necessary and could be integrated into the experimental results or discussion rather than standing as a separate section (optional).
- Results: The results presented are somewhat unconvincing. My primary baseline for comparison is KB, the initial paper to propose watermarking for LLMs. Although this approach targets black-box settings while aiming to remove distortions, it does not outperform KB, which was introduced nearly two years ago. Could the authors provide further insight into this? This issue may partly relate to the paper's structure, but I believe the authors need to highlight their main advantage more convincingly. For instance, it would be helpful to illustrate the tradeoff between distortion and text quality by comparing texts generated by KB and the proposed method, possibly using LLM-Judge. Additionally, if feasible, demonstrating the tradeoff between distortion and robustness would add value to the analysis.
- Finally, regarding the distortion-free claim, while the theoretical guarantees support this assertion, it would be beneficial to include qualitative results that demonstrate the distortion-free nature of the approach. Consider displaying examples of the unwatermarked text, the text watermarked by the proposed approach (using optimal hyperparameters), and the text watermarked by KB (also with optimal hyperparameters) for a clear, comparative illustration.

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 2
questions: My main question is about the novelty of the paper’s setting and its final results. As mentioned above, the work Christ et al already presents provably secure distortion free black-box watermark that is also robust to adversarial attacks (under a formal definition). Can you compare your work with them (and perhaps other similar previous works using crypto and rejection sampling) and explain what exactly the set of features that your work adds?
soundness: 2
strengths: The problem of black-box watermarking is an important problem, and having new schemes in this direction would be interesting. However, as I explain below, the schemes should be clear in what they offer and what is their advantage over previous work.

post rebuttal: I understood some aspects of the paper better and am increasing my score by one unit. I still have concerns (post discussions) about the writing and assumptions of the paper that I will add to the review.
summary: The paper presents watermarking schemes for LLM’s outputs, in the setting that we only have black-box access to the model’s “next token generation” function.

They claim their scheme is “distortion free” and “can be used in a nested way”.

In a bit more detail, the paper’s scheme is based on a scoring function, which in turn is based on a secret key. Then, when the LLM’s output is being generated, at each step, multiple samples are gathered. Then, the scoring function is applied to them all and the one with the highest score is chosen.

*post rebuttal comment*

After the interaction with author(s), I added several comments to the discussion board explaining why I increased my score. I thought I'd add them to this summary as well, just in case the authors might find the comments (hopefully) useful as well. The comments follow:

I thought I would go over the points discussed and say what my final thoughts are, and why (despite remaining disagreements basically about all the points being discussed) I am indeed happier with the paper now and will increase my score. Also, it took me a bit of time to have a closer look at the paper by Christ et al and also come back to the paper to understand their contribution in light of the discussions and what is done in Christ et al. 

To me, the main downside of the paper is actually its writing. It is hard to understand their scheme (with such dense descriptions) and why it is objectively and concretely better than previous work. In particular, key concepts need to be formally defined and discussed. The assumption of the paper about independence of the hash of the n-grams (called assumption (**) below). This needs to be *mathematically* and formally written and analyzed. Another major issue is their notion of “soundness”. They show that the detection algorithm can detect watermarked text from honestly generated non-watermarked text (of the same mode). In comparison, Christ et al. show that the soundness holds for any string that is generated independent of the secret key, which I think is the right definition of soundness. In fact, the paper should have a clear soundness definition to begin with. There is a chance that the authors can address this in their final/next draft well by expanding their theoretical claim of Theorem 4.2. Also note that this is where theory is needed, as no experiment can prove robustness for all strings generated independently of the key.

Having said the above, the reason that I am happier with the paper are:

I think the assumption (**) could be proved true if we model the hash function as a random oracle (which is a standard model called the random oracle model ROM in cryptography and allows proving heuristic assumptions in a meaningful way). This, however, is something that authors need to check and argue about, as I am not fully confident about it based on the written material. If one can justify their assumption (**) (eg., in the ROM model), then the entropy assumption (that is provably needed) is not affecting the distortion-freeness of the paper’s scheme (and is only needed for arguing soundness) while in Christ et al, it affects both distortion freeness and soundness. So, this is an interesting aspect that could be a selling point. The authors said that their scheme can also detect strings that only have a common substring (of high entropy) with the original generated text. This would match that of Christ et al, and it is in fact a form of robustness guarantee (though limited).

Now, some comments and responses to the points raised during the discussion with authors:

The authors unfortunately keep saying that Chrsit et al is non-black-box, while my point is that *if you assume* the entropies are large enough (say in every block of 100 tokens) then all of their schemes (not just the 1st one) become fully black-box, as the only thing they need is to accumulate entropies. So, this is where I had trouble evaluating their contribution of being the first black-box scheme in comparison with that of Christ et al, because both schemes could be black-box *based on an assumption*.

The authors confirm that their own scheme can also be “substring-complete” (SC) which is great, but then they bring up Section 6 of Christ et al, which is not quite relevant. That section is about removing the watermark under specific settings, but of course those attacks would not contradict their own SC property (which is a robustness guarantee). To understand SC completeness (which there is a disagreement with authors), and why it can be interpreted as a robustness guarantee, please read Def 8 of the archive version of the Christ et al paper, in which the detection algorithm is run only on the substrings of high entropy. So, if one of such substrings survives after adversary’s edits and stays intact in the final string, it can be detected by checking all possible (contiguous) substrings of the final string for detection (there are at most k^2 of them for strings of length k, which is fine). I might be wrong here, but this is not a main point of discussion anyway.

When discussing how to remove the entropy assumption from the first scheme of Christ et al, authors say “Firstly, the while loop may never terminate. [...] And even if it does terminate, it could take an astronomical number of samples before the condition is met”

The assumption on the entropy can be used to show that (with overwhelming probability) the chance of getting 0 is not “too small” (in particular, it can be lower bounded by 1/poly) and then using Chernoff/Hoeffding bounds, one can show that with polynomial samples, the chance of not hitting zero is exponentially small. So, things can be proved to be fine. But this is not a major point of discussion, because even the main (2nd) algorithm of Christ et al also becomes fully black-box if you assume the entropy is large in each block (of say 100 tokens).

Anyway, I think the paper has a lot of potential, but I think it would benefit quite a bit from a major improvement in the presentation of the ideas, clarification of the assumptions, and comparison with previous work.
weaknesses: The main weakness of the paper is that it is barely readable, when one actually wants to understand the scheme and the arguments. The presentation of the scheme is super dense and lacks formality. Instead of introducing ideas one by one, they are jammed and one gets no intuition as to what is goin on, beyond the high level description of “using scores”.

In fact, the paper’s main setting (which seems to be the main novelty) is already used in previous work published in learning venues. For example, this (cited work) from more than year ago (published in COLT) https://eprint.iacr.org/2023/763 exactly studies the setting that the paper does: black-box access to the token generation function, and does use a similar idea of using a hash function to pick the next token by rejecting some. It is also provably robust (under certain conditions) as opposed to the weaker model studied here (random substitution) and comes with clear theorems that prove undetectability (which implies distortion free-nes and utility both).

One main comment for improving the writing: 

- Try to define everything formally and at the right pace.
- There are also issues with using crypto terms without clarity. For example, F is a CDF, and then F[s] is a “single draw from a pseudorandom number generator for F seeded by integer seed s” .  I know cryptography well, but I have no idea what this sentence means. Then, it is assumed that F[h(K,w)] is a PRF. What is the citation that this is a PRF whenever F is PRG? (I don’t think this is true actually).
- What is the role of n-gram, l-gram, and their relation with tokens. Sentences like “where we allow the left endpoint to spill over only to…” are super informal and cannot be formally understood and checked.
Theorem 4.1 : what is F, and why should it be continuous? When it comes to efficient algorithms none are actually continuous (everything is discrete) so this is a strange assumption to make.

Meta-review: The paper presents a novel watermark scheme for black-box language models. After a extensive discussion, there are several critical issues remain unresolved. Reviewer 3sQV raised the concerns on the definition of "distortion-free". Reviewer Lnyz noted that the proposed watermark scheme required a more clear comparison with existing work. But the author's rebuttal did not convince the reviewer. Given these issues, I recommend rejection.

Decision: Reject