A Watermark for Black-Box Language Models
Authors: Dara Bahri
John Frederick Wieting
Venue: Accepted by TMLR ()

Abstract: Watermarking has recently emerged as an effective strategy for detecting the outputs of large language models (LLMs). Most existing schemes require \emph{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. \emph{black-box} access), boasts a \emph{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.

Published in Transactions on Machine Learning Research (02/2026)
A Watermark for Black-Box Language Models
Dara Bahri, John Wicting Google Mind
Reviewed on OpenReview: https: // openreview. id= 6gcHegGmIo
Abstract
Watermarking has recently emerged as an effective strategy for detecting the outputs of large language models (LLMs). Most existing schemes require while-bor access to the model's next-token probability distribution, which is typically not accessible downstream users of an LLM API. In this work, we propose principled watermarking scheme that requires only the ability to sample sequences from the LLM (i.e. black-bor access), boasts 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-bar schemes via comprehensive experiments.
1 Introduction
It can be critical to understand whether piece of text is generated by a large language model (LLM). For instance, one often wants to know how trustworthy piece of text is, and those written by an LLM may be deemed untrustworthy as these models can hallucinate. The goal of watermarking is to cleverly bias the LLM so that detecting its generation becomes easier. Most proposed techniques do not modily the underlying ingg 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 proprictary APIs currently do not support this option. Supporting this functionality presents security risk in addition to significant engineering considerations. Concretely, Carlini et al. (2024) showed that parts of production language model can be stolen from API access that exposes logits. In this work, 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 steganog- raphy, 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. (2011) devised a scheme for machine translation, but interest the topic grew substantially after the more recent seminal works of Kirchenbauer al. (2023a;b) and Aaronson (2023). Many effective strategics employ some form of pseudorandom functions (PRFs) and cryptographic hashes token n-gramms in the input text. Kirchenbauer et al. (2023a) proposes modifying the next-token probabilities every step of decoding such that 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 text quality.
Meanwhile, Aaronson (2023) proposes a clever distortion-free strategy which selects the token that is both highly probable and that achieves high PRF value. Kuditípudi et. al. (2023) applies scheme similar in spirit

---

Published in Transactions on Machine Learning Research (02/2026)
to Aaronson (2023) 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. (2023) adapts Kirchenbauer et al. (2023a)'s 's scheme for code-gencration by applying the watermark only at decoding steps that have sufficient entropy. Zhao et al. (2023) investigates a special case of Kirchenbauer et al. (2023a) for improved robustness adversarial corruption. Fernandez et al. (2023) 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. (2023) introduces a scheme that relies on black-box access to the LLM. Their method samples from the LLM and injects the watermark by replacing specilic words with synonyms. Although their approach shares the assumption of black-box 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 BERT model (Devlin, 2018), making it computationally expensive, and the scheme is not cittortion-freeee Chang et al. (2024) presents POSTMARK, black-box watermarking method that uses semantic embeddings to identify an imput-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., 2023b; Hou et al., 2023; Ren et al., 2023; Yoo et al., 2023). Meanwhile, others have viewed the problem through the lens of cryptography and classical complexity theory (Christ et al., 2023; Christ & Gunn, 2024). Lastly, Liu et al. (2023a) proposes an un-forgeable publicly verifiable watermark algorithm that uses two different neural networks for watermark generation and detection. Huang et al. (2023) 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. (2024) shows that paraphrasing can evade both third-party and watermarking detectors alike. Some may posit that attacks like paraphrasing are unrealistic since either they are too expensive to conduct at scale or parties in possession of capable paraphrasing model have adequate resources to serve their own LLM. Zhang et al. (2023) 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 orucle which can modify an output with a non-trivial probability of maintaining quality. Alarmingly, Gu et al. (2023) demonstrates that watermarks can be learned - an adversary can use a teacher model that employs decoder-based watermarking to train student model to emulate the watermark. Thibaud et al. (2024) formulates tests to determine whether black-box language model is employing watermarking, and they do not find strong evidence of watermarking among currently popular LLMs.
round-trip translation
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 8. Let FR be the CDF for Σ X1, where X; ~ F. We sometimes abuse notation and treat a distribution as its CDF (e.g. (o, 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 F. Now, we detail our proposed algorithm, for which pseudocode is provided in Algorithm 1. A Python implementation and example usage are presented in the A Appendix.
did
2

---

Published in Transactions on Machine Learning Research (02/2026)
Algorithm Black-Box Watermarking
1:
function WATERMARK(cdF F, key K, # cand ctx len prompt P, seq len k, LM)
2: f-
3: while SSTOCoND((O) do
Continue until stop loken is encountered or max length reached.
4: 0+0 WATERMARKSINGHLRRF K, m. n, PlO, k LM)
5: return O
6: function WATERMARKKINGUE(CCr F, key K, # cands m, ctx len n, prompt P, seq len k, LM) P Draw m sequences from LMM, each with at most k tokens. Qm))
7:
QI,..,, ~ LM P k) (I,, (1 < UntoosssaaeVViCCCUSSS(( MI.....6 + SconESEQs(F, (X1, (X),..., X,), R) + argmax. "; m/a
9:
10:
return X
12:
function ScodESeos(edI F, candidates C, key K, ctx len n, prefix P)
+ & for X; in do for in NGRAMS (X,, n, P) do
14:
Don't compute n-grams over original prompt. Apply cryptogrophically secure integer hosh.
16:
Z + Z (i, (NTHASH(K[W))
+- RERMOVEDUPLICCTTSS(2)
18:
for S in SORTEDGROUPBY(2) do
Htrate through each candidate's 's set of unique seeds.
19:
+ (F[s] for s 5)
20:
Fin E, R3
21:
return U1 MIC
22:
function (edE F, tokens X, key K, ctx len n)
b p-valuue-asse based detection.
23:
S + à
24:
for in NGRAMS (X, n, Φ) do
S - INTHASH w)
26:
+ REMOVVEDUPICAATES(S)
R + (F(s) for in 8)
28:
return Fim Σ, R3
Higher score means higher likelihood of being watermarked.
Algorithm Recursive Black- Watermarking
1: function WATERNARRRROUTRSSS((F (K1,..., K.), m', P. h. LM)
Sub. for WATERMARKSINGILA
2:
then
3:
M = -x-x(-1----)
4:
else
5:
M = NATERNARKKREURRSVVEER (K2...., Ke), mmm=,mm ,n, LM)
6:
return WATERMARKKSINGLEEF Ki, P.P. M)
function DETECTRECURSIVE(E, X, (KI...., K2), n))
8:
P à
9:
for K, in (Kı,...,KK) K.) do
10: P (1 F,,
11:
y -+-2 log P.
D Combine p-volues using Fisher's method.
return X2: (v)
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 conditional language model with vocabulary V of size V, and a cryptographic hash function (c.g. SHA-256) from z Z. Let n be the number of tokens (typically or 5) that serves as input to our pscudorandom function. Our PRF g V R given by g(w) F(h (KWw)), where denotes concatenation.
3

---

Published in Transactions on Machine Learning Research (02/2026)
Watermark encoding. We sample sequences (Qi,...,,Qn, Qm), each consisting of at most i tokens from LM P; k). Let ((X1,0))...... (Xj, oj)} be the unique sequences along with their counts from {Qi} for example, the sequence X, appears ct times in {Qi). To score each distinct sequence Xt, we first extract its allow the left endpoint to spill over only to earlier-generated tokens and not the original prompt tokens. (-grams are taken instead for boundary indices with only (-1 < - eligible tokens strictly left of it. We compute an integer seed for each n-gram w; 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 Xx: we iterate through its new seeds S. (order does not matter) and compute the quantity ", =-= Fs.1 | r(S.al). Finally, we compute 1" = argmax "i m/s and choose X₃- as our watermarked sequence of length at most k. To generate longer texts, we run the aforementioned process autoregrossively until our slopping condition, where we condition the language model on P and the tokens generated thus far.
n-grams {(X._-n-1,.... Xx,)
{==) |Xx|
where
One may notice that the LLM is expected to return at most & 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 generale n-grams from the responses however they would like (with custom tokenization not). Furthermore, there is no constraint on k; l can be set adaptively to the max length in each batch of returned responses. The main consideration though is smaller k begets stronger watermark, so if the adaptive & is too large, detectability will suffer.
Watermark detection. We treat detection as a hypothesis test, where the mull Ho is that the query text was not watermarked with our schemn and secret key and the alternative Hi is that it was. While Bayesian hypothesis testing could be used, this would require choosing priors for both hypotheses, which could be challenging and 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 Wt compute R2 = F [h (K) [wx)]] Under Ho (assuming that the test n-grams are independent), Rg sid ~ F, so EMM R ~ Flw| giving p-value p = 1 - Fiwi (Σ W R.). Our detection score
[W]
s is 1 p (higher means more likely to be watermarked).
Another way to compute a p-value is to compute token-level p- valuus and, assuming they are independent, combine them using Fisher's method. This way, p 1 - X2 (-
( log (1 F(R.))) Furthermore, tests that incorporate the alternative distribution can be used the best example being the likelihood ratio test: = I! (log fi (R.) - log fo().)), where fo and f1 are the densities of RG under Ho and Hi respectively. For some choices of I' and under some assumptions, fi may be written explicitly. In other cases, one can estimate fi by logging values of R, 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₁ 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.
Consider the special case that all users are actually the same entity in possession of t distinct keys (KI...., Kt). Then the iterative watermarking becomes recursive one, where K; is used to watermark the result of watermarking with keys (Kit)...., K.). 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 '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.
4

---

Published in Transactions on Machine Learning Research (02/2026)
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 atlckk Although any symmettic 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 ii.d. samples from the model, one can apply our watermark selection to the sequences that arisc 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 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 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 resourca-constrainee 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 lot of duplicate n-grams across the candidate set.
Relation to similar work. With our algorithm presented, we now discuss its relation to two similar methods whose treatment. we had deferred.
SYNTHID (Dathathri et al., 2024) is white-box scheme which resembles the recursive variant we propose. Specifically, when the sequence length is 1 and each watermarking party samples 2 sequences, then our encoding procedure overlaps with theirs. Both processes can be visualized via a binary tree where nodes represent tokens. At the very bottom, leaf nodes represent tokens sampled i.idd from the text-token distribution. The token for a non-leaf node docided by applying a specific PRF determined by the node's level to the two children tokens. Scoring, or decoding, differs however in that while they propose training a Bayesian detector or zero-shot detection by combining PRF values for the unique n-grams across levels of the tree (equivalently, virtual watermarking parties) using weighted average (or corresponding z-scores) that accounts for entropy differences across depths, we suggest combining p-values using Fisher's 's method with equal contributions across the layers. Furthermore, they suggest using a Bernoulli distribution instead of the standard uniform and consider much deeper trees (c.g. a depth of 30) than the ones we do in this work.
Most similar to our work is the WATERMAX algorithm of Giboulot & Furon (2024). At a high level, their scheme very similar to ours: iid, responses are sampled from the LLM for specific prompt, pseudorandom values are determined for each token in each sequence based n-grams and an aggregate score is computed for each sequence. The sequence with the largest. aggregate score is returned as the watermarked text. However, very crucially, their algorithm is not distortion-free, as ours is, and their theory does not capture the critical role of entropy on detectability. Meanwhile, we are able to formally and empirically quantify the dependence on entropy on performance and formulate provably optimal tests. Furthermore, we propose a recursive variant. of the algorithm and also carefully study the effect of the distribution used for the PRF.
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 fonile sequence and P any prompl. Let Xa. ~ LM( | P) be the non-ware watermaerrr output of the conditional autoregressive language model. Let X be the output of the watermarking procedure (WATERMARK in Algorithm 1, for both vecursive and non-recursive setfings) for the same prompt and model and any choice of remaining imput arguments with the constraint that F is a continuous distribution. Furthermore, assume that the deduplicated seeds (determined by hashing the secret
5

---

Published in Transactions on Machine Learning Research (02/2026)
key and n-grams) across sequences, conditionally independent given the counts of the sampled sequences. Then, P(X,, X) = IP = X).
Theorem 4.1 tells that sampling tokens using proposed scheme is, from 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 (cI....,cy) cy) themselves. One can construct cases where the assumption is reasonable and others where it is blatantly violated (e-g- if n-grams within sequence are strongly correlated). We study how well this assumption holds in practice in the Appendix. One direction to making the assumption more palatable is to draw fresh keys i..dd 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 koy sct), which may reduce distortion, but will hurt detection as cach 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 = and = U(0, Let 8o be the score under null that the T test tokens' ,assumed independent, were generated without watermarking and 51 be the score if they were. With c as the number of times vocabulary token was sampled, we have the following lower bound on the detector's ROC-AUC.
P(s1 2 s0) 1+ 1/(3T>2a2) where
V E1
2) and En
log
log(m)
m +
m
a represents the overage Shannon entropy in the sampled nert-loken distrituution.
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, 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, e ~ Multinomial (m, The largest a is achieved when the nonzero e; ''s are 1, which can occur when the underlying distribution is uniform (maximal uncertainty) and/or m not large. In this
0 and so does our lower bound. Note that because
case, a + log(m) and our bound goes to 1/ (1+1/ 3T m+1 - 2) })²)) This quantity has very sharp diminishing returns with respect to m, so there may be little value in increasing m beyond certain point. When m + c0, the bound goes to 4/11+4/(31) which increases very quickly with T. A mere 50 test tokens guarantecs 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 other choices of F and k > though formal bounds can be tricky to obtain because of difficulty quantifying the alternative distribution. The null distribution is easy p-values are (0, 1) under Ho, and result, have 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 independent, have the following equality the false positive rate of DETECT (Algorithm 1), using decision threshold t.
FPR TTR=PHo(e (Ho 11-1-1 11--
This also holds for DEFECTRECURSIVE. CAAAEERRRRUSSIVAAAAAAAA (Algorithm 2) if we further assume the p-values across secret keys are independent.
Too he more precise, these are unique n-grams.

---

Published in Transactions on Machine Learning Research (02/2026)
Selecting distinct independent secret keys (K1,..., Ki) (and ignoring hash collisions that arise across calls to DETECT within DETECTRECURSIVEN 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, formulate the optimal detection test and write down false-positive and falso-negative rates exactly.
Theorem 4.4 (Optimal detection for Gamma). Assume that condidate sequences are unique with length k and that the n-grams are independent and contain duplicates. Suppose choose F = -- -Gamma (1/k, 9) (1/mma/1/k,raa (1/k, m3) with pdf fi, and sid
(flat scheme), for any rate parameter 3. Let Fo = F with påf fo, Fi = Gamma R the PRF values of the T lest lokens (unique n n-grumms,, assumed to be independent. Then, Vi, R3 ~ Fo iid
under the null that the text was watermarked using our procedure and R₂ ~ F1 otherwise. The uniformly most powerful Lest the log-iikelhhood ralão test (LRT) with score
T
(i(R)) (R()
(R)
Σ log
Furthermore, for any decision threshold t. score 8, we have that:
FPR (Type-I error) = PHo (s > 1) = Gammaa (T, (Q(1), and
FNR (Type-Il error) PH, (s st
Gamma(T/k m3) (Q(t)), where
((1) T rlog(m))
(m 1)3
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, B 1, we can achieve 99.9% TPR 1% FPR.
For other choices of F, we can estimate fi via simulation. If we assume candidate sequences have the same length & with no duplicate n-grams, then we can fill an m x 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 f1. We apply a Gaussian kernel-density estimator where the bandwidth is chosen using Scott's rule (Scott, 2015) to estimate (r( for test value r. Despite having fo in closed-form, for consistency, we can also estimate non-parametrically by drawing from F.
5 Experiments
In this section, 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 MISTRALL-7B-NNTTRUC (Jiang al., 2023) hosted Huggingface? with bfloat16 quantization, and databricks-dolly- (Conover et al., 2023), 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.c. general QA), and summarization categories, whose human responses are al 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 won-waatrmrrked responses stochastic one using temperature 1, and the greedy / argmax decoding along with watermarked one for each scheme. We always force 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 < 250 by truncating to the first. T tokens.
hhtpp://wonggiggaaer..c/stttttts Instrutttttt
7

---

Published in Transactions on Machine Learning Research (02/2026)
For completeness, also present the key results when GEMMA-7B-INSTRR (Team et al., 2024)* with bfloat16 quantization is applied to the test split of edi5-calegory². 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/ FR. (1) F U(0, 1) and FE IrwinHalllkk), (2) F F= FN,, 1) and Fi = k). (3) F Gamma(1/kk) and Fv. -Exp(I) (4) F = x2 and F& X2k We set n 4
5.2 Evaluation Metrics
We evaluate performance using three criteria. For all metrics and methods, standard errors are computed by running watermark generation multiple times, keeping the secret keys fixed.
Detectability. How well can we discriminate between non-watern won-waaerrarked 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 casier 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 / In-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 won-maaermrrked 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 S target FPR (taken to be 1%), which we find to be more meaningful than TPR at the target FPR. We look at performance as 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 would like to quantify the amount of distortion actually induced by the watermark but doing so is no straight forward task.
A meaningful metric is the KT-divergence between the true non-watermarked next-token distribution and the watermarked one conditioned on the same context, where the former is used as the reference, for all contexts that oceur in the non-watermarked generation. This is challenging because while the explicit watermarked distribution is easily derived for Kirchenbauer et al. (2023a)'s 's scheme which explicitly tweaks the probability of each token in the vocabulary, this is not the case for our scheme; we could estimate it via simulations at each step but this would be computationally expensive. As an alternative, we measure the perplexity of the watermarked text under the LLM sans watermarking. The caveat. is that while perplexity is often used in the literature to measure text quality, the goal here is not necessarily to minimize it (which greedy decoding would do) but to verify that watermarking does not matcrially change perplexity levels compared to that of non-waaermarked randomly sampled text. We also report likelihood as the log- tog-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-L.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 responses for each prompt and compute win rates using the best
"nttpe:/hhugginggaae http://///egggggacc.c.c///////// co/google//gmms-neeee
S htteps://hugiinggaace http:///wwwa.tooeeea//////////se
8

---

Published in Transactions on Machine Learning Research (02/2026)
response. (2) represents the common practice of sampling 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 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 random p-percent of them are corrupted by replacing each with a random different token. 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. Tn this attack, the adversary attempls to evade detection by paraphrasing the watermarked text. We use Gemini-L.5-Pro to paraphrase cach non-truncated watcrmarked generation. Details are deferrod to the Appendix.
5.4 Baselines
The watermark schemes 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 (2023) computes a PRN for each token i in the vocabulary as u, = (0, ((/(k))))))) where w is the preceding (n 1) gram, is the secret key and h is a cryptographic hash. Token 1 is selected, where i" argmax, u, 1/p: At test time, n-grams (w;);= are extracted from the query test and the detection This choice strikes a good
score SA = - - log (1 R₂), where R. (O, 1) [M(K]w;)]- n set balance between generation quality / diversity and robustness to attckks. The scheme boasts a distortion-free property, but the generated text is deterministic function of the prompt - i.e. only one generation is possible conditioned on particular prompt.
Remark. k and F = UO,,)) 1), then our watermark encoding can be viewed as a stochastic version of Aaronson (2023)'s. 's. As m + oo, a/m " Pt, where Pt and are the probability and observed occurrences of loken I.
Aaronson Corrected (AC). Aaronson (2023)'s detection score 88 not length-aware and consequently single decision threshold across scores involving various lengths results in poor performance, as later show. Observing that S is sum of (negative) log p-values, S GammaaT, 1), equivalently, 28 x²r under the null that all test tokens are non-waterm.r.ed We propose the new corrected detection score, SAC Gamma 1)(*A) = (2s A). For completeness we also experiment with a p-value computed in the way we do for our method - concretely as, IrwinHall(T) "EERR: R₂). Note that both transformations are monotonic so they have no effect on ROC-AUC when T is fixed.
Kirchenbauer (KB). Kirchenbauer et al. (2023a) uses the n previous tokens to pseudorandomlyy partition the vocabulary for the next token into two lists: a green list of size yV and red list consisting of the remainder. A positive bias of ó 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, Tg of which were found to be green is, SKB = (T, - -TT))//T((1 (1(11-) We incorporate the latest updates to the algorithm such as including the current token the n-gram and skipping duplicate n-grams at test time. We set 4, 7 0.25, and 8 E {0.5, 1, 4).
Kuditipudi (K). A drawback of using the last tokens basis for the PRF is that changing just one of them changes the output and hurts detection. Kuditipudi et al. (2023) addresses this limitation as follows.
9

---

Published in Transactions on Machine Learning Research (02/2026)
PPL
WR
WR. (3)
AUC
PAUC
C. AUC
C. PAUC
P. AUC
PAUC
Max Std. Error
0.03
0.1
0.3
0.2
0.3
Greedy Decoding
1.37
Random Sampling
3.50
19.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
58.8
50.7
Kuditipudi
3.55
50.3
67.3
87.8
76.6
87.2
74.4
75.9
53.2
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
Kirchenbauer
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
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
Flat (I: 1)
32
3.06
48.4
65.3
97.8
90.2
94.2
80.0
53.0
50.8
2.63
47.7
62.5
97.7
90.0
54.6
51.3
1024
2.61
47.7
62.2
97.7
90.0
94.0
79.7
52.8
51.1
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
Flat (I: 10)
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
2
3.79
48.5
64.2
69.6
50.7
62.2
50.3
17.0
50.0
4
3.76
47.7
63.9
82.9
53.5
71.9
51.3
49.4
50.0
Flat 50)
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
4
3.41
49.0
65.0
93.4
75.5
86.3
63.2
48.4
50.4
3.33
49.2
66.2
82.9
90.6
53.4
50.8
Rec. (k:
32
3.29
48.4
64.3
96.3
85.0
91.6
73.5
49.4
50.8
3.05
48.3
64.5
97.2
87.9
92.6
76.5
50.4
51.2
4
4.13
45.7
61.3
88.6
61.7
78.8
53.8
48.0
50.0
Rec. (k 10)
16
4.13
43.7
59.7
93.4
741.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
4
3.79
48.2
63.8
74.2
51.2
65.1
50.5
46.5
49.9
Rec. (k: 50)
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
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. The = setting can be executed very efficiently when white-box access available. 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%. and stand for 10% corruption and paraphrasing attack. For paraphrasing, larget lengths of {150, 200, 250) used in calculating AUC and pAUC as performance essentially random 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.
Consider a secret, finite ordered list of seeds of length k. Start watermarking by selecting position in the seed list uniformly al random and apply the selection rule of Aaronson (2023) 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 with the specific list of seeds used during encoding as opposed any other random list of seeds of the same length. As the random starting position is not known during scoring, alignment based the Levenshtein distance is given
10

---

Published in Transactions on Machine Learning Research (02/2026)
Detection Perf.
Detection Perf.
1.0
1.00
pAUC (1% max FPR)
0.9
0.95
0.90
0.8
AUC
0.7
0.80
KB (2)
Ours (k=1, m=16)
0.6
(2)
Ours (k=1, m= 16)
Ours (k=1, m=1mm=10mm 1024)
A
Ours (k=1, 1, m=1024)
0.75
K
Ours (k=50, m616)
Ours (k= 50, m= 16)
0.5
50
100
150
200
250
50
100
150
200
250
T
T
Detection Perf.
Detection Perf.
1.00
0.9
0.95
0.90
0.8
AUC
AUC
KB (2)
0.80
0.7
K
0.75
KB (2)
Ours (k=1, mm16)
Ours (k=1, m=16)
0.70
Ours (k=1, m=1024)
Ours (k=1, m=1024)
Ours (k=50, m=16)
Ours (k=50, m=16)
0.65
0.5
0.5
1.0
1.5 Entropy
2.0
2.5
10
15
20
25
35 Corruption
30
40
45
50
%
Figure 1: Performance of our flat scheme. Top: Detection AUC and pAUC with 1% max FPR for range of target text lengths when there is no corruption. Bottom Left: AUC (mixed T's) function of the average won-watermrrked response entropy of the examples used in the calculation. xz-oordinate z corresponds to the bucket of examples whose entropy is between [x 0.25, x] nats. Bottom Right: Efffect of amount of random token corruption on AUC (mixed T's).
that considers alignments of various subsequences of the text and seeds. The proposed method is quite similar to Aaronson (2023) with the difference of using fixed list of seeds (instead of input tokens to determine the soed) and using 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 frre.. Following their work, we let k: = 256 and accelerate the permutation test by pre-computing 5000 reference values for the secret list using suippets from the train set C4-realnewslike (Raffel et al., 2019) at the various target lengths we evaluate on.
5.5 Experimental Results
Table shows results for baselines and our scheme using = (0, 1) and p-values for scoring, as detailed in Algorithms and 2. For the recursive scheme, depth lg(m) (i.c. m for each virtual watermarker). Here, the negative class is wonerattrrr argmax/greedy generations. Results for using stochastic (temperature 1) generations the negative well as the average likelihood scores presented in Table 5 (Appendix); the
11

---

Published in Transactions on Machine Learning Research (02/2026)
trends remain the same. We summarize observations MISTRAL-7B-INSTRUCT satabricks-dolly 15kk which also hold for GRMNA-7B-INSTRICC 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, 1024, we are able to achieve lower perplexity (2.61 vs. 2.81), better diversity (62.2% vs. 45.3% on best-of-3 win rates) than and comparable detection performance to Aaronson (2023). Furthermore, it has lower perplexity (2.61 vs. 3.55) and detection performance (97.7% vs. 87.8% AUC) than Kuditipudi et al. (2023). By cranking up 6, Kirchenbauer et al. (2023a) can achieve strong detection but at the expense of perplexity. When matched on perplexity, we achieve better detection. For example, 8 0.5 achieves 3.39 PPL and 73.2% AUC compared to our 2.61 PPI, and 97.7% AUC. GEMMA-7B-INSTRUN
on eli5-category with = 1, = 1024 outperforms Kuditipudi et al. (2023) and is on-par with Aaronson (2023) (see Appendix). Kirchenbauer el. al. (2023a) with 5 = 0.5 gives 1.649 PPL and 61.6% AUC whereas k = I, = 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 metries 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 embodded 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 & = 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 + oo, c//m + Pt and our scheme becomes less diverse - deterministic conditioned sampling noise which drives down perplexity.
the prompt, like Aaronson's. On the flip side, large reduces
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 A = 1, our AUC increases from 90.2% to 95.8% as m goes from to 4, but flattens out when m hits 16. This corroborates our theoretical intuition from Theorem 4.2 which is further explored in Figure (Appendix).
For fixed m, increasing & hurts detection performance. For fixed and target generation length T, increasing h gives us fewer opportunities (fewer calls to WATERMARKSINNGRR 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.
1) slightly outperforms alternative distributions. Flat distributions may offer better robustness attacks. In Table 4 (Appendix), we see that U(0, 1) fares comparably to N 1) and slightly outperforms X3 both on detection and perplexity. For example, when k == 50,m m 2, (O,, and X² have AUCs of 69.6% and 68.1% respectively. Furthermore, we find evidence that U (0, offers better protection to attacks. For example, when k = 50, m 32, the AUC for (0, 1) (xă) 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 (0, 1) may be more robust than those with quickly decaying tails. Consider shaping the continuous F so it approaches Bern(p) (i.e. f(x) R (1 - p))(() + pō(x - 1)), where p is very small. Suppose k is large and m is small. Then, the winning sequence X,- will have extremely few (if any) of its Rý's equal to 1. If the text is unmodified and these few n- 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 Fy- IrwinHall(T)) when F = U 1) involves computing T'fold convolutions or cardinal B-splines, when F = N00 1), Fr is easier to compute for very large T; specifically, Fr(x) = F (2/vT).
12

---

Published in Transactions on Machine Learning Research (02/2026)
5.5.3 Observations detection
Length correction of Aaronson (2023) is crucial. Recall that the ROC-AUCs presented in Table 1 are computed over pool of different lengths. Our p-value-based score for Aaronson (2023) improves detection significantly; for example, AUC goes from 71.7% to 97.9%. Table 7 (Appendix) shows that the sum-bused p-value correction fares bit worse, which was little surprising given that this worked the best for our scheme, even for the k = case.
Sum-based p-values outperform Fisher ones. In Table 2 (Appendix), we observe that replacing our sum-based p-value (where Ho is that Σ r; Fr) by 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 h- = 1, this setting corresponds exactly to a stochastic version of Aaronson (2023).
Likelihood-ratio scoring docs well for large h and small m, when its assumptions are more realistic. In Table (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 soquences sampled, increasing the importance of the latent exponent m/c, used in the scoring and deviating further from the LRT assumptions. However, LRT has the polential to be effective alternative when k is large. For example, when k 50 and 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 shows the effect of T on AUC. We see sharp improvements with respect to T, even when 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 samples in each bucket. As 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. (2023) and Kirchenbauer et al. (2023a) with large 8 do better on AUC (but not so much on pAUC). Furthermore, in Figures and 2 (Appendix) we observe that large amounts of random token corruption hurts scheme and Aaronson (2023)'s more than it that of Kirchenbauer al. (2023a) or Kuditipudi et al. (2023).
6 Conclusion
In this work, we present framework for watermarking language models that requires nothing more than 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-inciine as well as concrete rocommendations for the practitioner.
Broader Impacts
Our watermarking scheme, like other ones, can be used to understand the provenance text this can be both good and bad. On one hand, can be used catch inappropriate uses of a language model (o.g. illicit applications that violate terms of service), or help users understand whether they can trust a piece of text (if it is L.M-ggenrated and its factuality is suspicious, it may be hallucination). On the other hand, it may
13

---

Published in Transactions on Machine Learning Research (02/2026)
violate user privacy LLM providers can where users post the outputs of their models, and to make matters worse, users may not be able to detect if this is happening.
Acknowledgements
The authors would lirstly like to thank Rob McAdam, Abhi Shelat, and Matteo Frigo for their early, umpublished work on the topic and Sumanth Dathathri for critical technical feedback on as well on our work. They proposed and experimentally validated a white-box scheme whose encoding procedure looks identical to that of our flat one when & = Secondly, the authors would like to thank Ashkan Soleymani, John Kirchenbauer, and Mukund Sundararajan for insightful discussions that were instrumental in the development of this work.
References
Scott Aaronson. Watermarking of large language models. Large Language Models and Transformers Workshop al Simons Inslitule for the Theory of Compuling, 2023.
Nicholas Carlini, Daniel Paleka, Krishnamurthy Dj Dvijotham, Thomas Steinke, Jonathan Hayase, A Feder Cooper, Katherine Lee, Matthew Jagielski, Milad Nasr, Arthur Conmy, et al. Stealing part of a production language model. arXiv preprint arXiv:2403.000 2024.
Yapei Chang, Kalpesh Krishna, Amir Houmansadr, John Wieting, and Mohit Tyyer. Postmark: A robust. blackbox watermark for large language models. arXic preprint (oo.2406.14517, 2024.
Miranda Christ and Sam Gunn. Pseudorandom error-correcting codes. aiv preprint arXiv:2402.09370, 2024.
Miranda Christ, Sam Gumn, and Or Zamir. Undetectable watermarks for language models. arXie preprial arXiv:2306.0913 2023.
Mike Conover, Matt Hayes, Ankit Mathur, Jianwei Xie, Jun Wan, Sam Shah, Ali Ghodsi, Patrick Wendell, Matei Zaharia, and Reynold Xin. Free dolly: Introducing the world's first truly open instruction-tuned Ilm, 2023. URL https://www databricks wwa.bbiicks.coobb...ece.e wwtpcccom//./eecccccc wwt.blogg/0////////o//ooo/ 2202//04/2// oota
Sumanth Dathathri, Abigail See, Sumedh Ghaisas, Po-Sen Huang, Rob McAdam, Johannes Welbl, Vandana Bachani, Alex Kaskasoli, Robert Stanforth, Tatiana Matejovicova, et al. Scalable watermarking for identifying large language model outputs. Nature, 634(5035):818--3))) 2024.
Jacob Devlin. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprinl Xrx: 04800, 2018.
Pierre Fernandez, Antoine Chaffin, Karim Tit, Vivien Chappelier, and Teddy Furon. Three bricks to consolidate watermarks for large language models. In 2023 IEEE International Workshop on Information Forensics and Security (WIFS), pp. 6. IEEE, 2023.
Eva Giboulot and Teddy Furon. Watermax: breaking the 11m watermark dedeetablitt--robunnnss--guggg trade-off. arXiv preprint arXiv:2403. 04808, 2024.
Chenchen Gu, Xiang Lisa Li, Percy Liang, and Tatsunori Hashimolo. On the learnability of watermarks for language models. arXiv preprint arXiv:2312. 04469, 2023.
Abe Bohan Hou, Jingyu Zhang, Tianxing He, Yichen Wang, Yung-Sung Chuang, Hongwei Wang. Lingfeng Shen, Benjamin Van Durme, Daniel Khashabi, and Yulia Tsvetkov. Semstamp: A semantic watermark with paraphrastic robustness for text generation. arXiv preprint arXim:2310.0033 039991, 2023.
Baihe Huang, Banghua Zhu, Hanlin Zhu, Jason D Lee, Jiantao Jiao, and Michael Jordan. Towards optimal statistical watermarking. ar Xie preprint or 2in:2312.079900 2023.
14

---

Published in Transactions on Machine Learning Research (02/2026)
Albert Q Jiang, Alexandre Sablayrolles, Arthur Mensch, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Florian Bressand, Gianna Lengyel, Guillaume Lample, Lucile Saulnier, et al. Mistral 7b. arxiv preprint arXic:2310.00 06825, 2023.
John Kirchenbauer, Jonas Geiping, Yuxin Wen, Jonathan Katz, lan Miers, and Tom Goldstein. A watermark for large language models. arXiv preprint arXie:2301.1022 2023a.
John Kirchenbauer, Jonas Geiping, Yuxin Wen, Manli Shu, Khalid Saifullah, Kezhi Kong, Kasun Fernando, Aniruddha Saha, Micah Goldblum, and Tom Goldstein. On the reliability of watermarks for large language models. arXiv preprint arXiv:2306. orXio:2306.4463, 2023b.
Kalpesh Krishna, Yixiao Song, Marzena Karpinska, John Wieting, and Mohit. Tyyer. Paraphrasing evades detectors of ai-generated text, but retrieval is an effective defense. Advances in Neural Information Processing Systems, 36, 2024.
Rohith Kuditipudi, John Thickstun, Tatsumori Hashimoto, and Percy Liang. Robust distortion-free watermarks for language models. arXiv preprint arXiv:2307.15598 2023.
Tachyun Lee, Seokhee Hong, Jaewoo Ahn, Tlgee Hong, Hwaran Lee, Sangdoo Yun, Jamin Shin, and Gunhee Kim. Who wrote this code? watermarking for code generation. arXiv preprint arXiv:2305.1500 2023.
Aiwei Liu, Leyi Pan, Xuming Hu, Shu aan'ang Li, Lijie Wen, Irwin King, and Philip S Yu. An unforgeable publicly verifiable watermark for large language models. arXiv preprint Xix:v23007. 162000 2023a.
Aiwei Liu, Leyi Pan, Xuming Hu, Shiao Meng, and Lijie Wen. A semantic invariant robust watermark for large language models. Xix preprint 2xix:2310.06356 2023b.
Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu. Exploring the limits of transfer learning with unified text-to-text transformer. Xixiv e-prints, 2019.
Jie Ren, Han Xu, Yiding Liu, Yingqian Cui, Shuaiqiang Wang, Dawei Yin, and Jiliang Tang. A robust semantics-based watermark for large language model against, paraphrasing. arXiv preprint 210022211.08711, 2023.
David W Scott. Multivariate density estimation: theory, practice, and visualization. John Wiley & Sons, 2015.
Gemma Team, Thomas Mesnard, Cassidy Hardin, Robert Dadashi, Surya Bhupatiraju, Shreya Pathak, Laurent Sifre, Morgane Rivière, Mihir Sanjay Kale, Juliette Love, et al. Gemma: Open models based on gemini research and technology. ar preprint arxiv:2403.08 082995 2024.
Gloaguen Thibaud, Jovanović Nikola, Staab Robin, and Vechev Martin. Black-box detection of language model watermarks. arXiv preprint arXiv:2405.0777 2024.
Ashish Venugopal, Jakob Uszkoreit, David Talbot, Franz Josef Och, and Juri Ganitkevitch. Watermarking the outputs of structured prediction with an application in statistical machine translation. In Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing, pp. 1363 1372, 2011.
Xi Yang, Kejiang Chen, Weiming Zhang, Chang Liu, Yuang Qi, Jie Zhang, Han Fang, and Nenghai Yu. Watermarking text generated by black-box language models. arXiv preprint arXim:235 08883, 2023.
KiYoon Yoo, Wonhyuk Ahn, Jiho Jang, and Nojun Kwak. Robust multi-bit bit natural language watermarking through invariant features. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics ( (Volume 1: Long Papers), pp. 2092 2115, 2023.
Hanlin Zhang, Benjamin L Edelman, Danilo Francati, Daniele Venturi, Giuseppe Ateniese, and Boaz Barak. Watermarks in the sand: Impossibility of strong watermarking for generative models. arxiv preprint arXiv:2311.04337, 2023.
Xuandong Zhao, Prabhanjan Ananth, Lei Li, and Yu-Xiang Wang. Provable robust watermarking for ai-generated text. arXiv preprint 2rXiv:2306.17498 2023.
15

---

Published in Transactions on Machine Learning Research (02/2026)
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) beller response to PROMPT? Answer with either (A) (B). (A): GREEDY RESPONSE.
(B): WATERMARKEN RESPONSE."
For determining the best response, we use:
"Is (A), (B), or (C) the best responses PROMPTY Answer with either (A), (B), (C). (A): RESPONSE (B): RESPONSE 2. (C): RESPONSE 3."
In both cases, 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/ 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 histogram of the entropy of the underlying next-token probability distribution under temperature random sampling without watermarking across our dataset. We the entropy is concentrated between 0.5 and 3 nats. We plot the AUC lower bound predicted by Theorem 4.2 (k = 1, = 1024) sweeping our entropy term across this range, with the understanding that for sufficienlly large m, our a is a good estimator of the true underlying entropy. In Figure 4 we look al the impact of m and T on our AUC bound when the optimal a = log(m) is plugged in. We see sharp diminishing returns with respect to 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 see empirically in Figure 1.
Given a next-token distribution over the vocabulary, we can estimate a via simulation, In Figure 5 we plot the effect of m on á, our simulated entropy, for two distributions - uniform and Zipf - over a 32k token vocabulary. Neither may be realistic in practice, but the exercise is still informative as we observe that å follows log(m) pretty well for even large m's when p is uniform. As expected, is smaller when p is Zipf (lower entropy) and deviates from log(m) for large m.
Figure 7 plots the performance that Thcorem 4.4 predicts when using the optimal likelihood ratio test with the Gamma distribution.
Table 6 shows perplexity and detection performance for GEMMA-7B-INSSRRUC on the eli5-category dataset. The trends here are as before. Figure shows the impact of number test samples on detection.
Testing the independence assumption. Central to theory the assumption that the seeds, deduplicated across candidate sequences, are independent. We now empirically test that assumption follows. We watermark 20 random prompts from databricks-dolly--a using MISTRAL-7B-INSTTRIO with a minimum and maximum lext length of 250 and 300 tokens respectively. The flat scheme with F = U00 1) for various k m, and most importantly n, is used. During the watermarking procedure we track the u, for each candidate sequence. We pool all these u,'s together across decoding steps and prompts, and run a hypothesis test. Our mull hypothesis is that all the seeds are independent. Under the mull, the set of u, should look like one giant i.i.d. sample from (0, 1), and so we can apply two-sided Kolmogorov-Smirno (KS) test. to
16

---

Published in Transactions on Machine Learning Research (02/2026)
Detection Perf.
0.80
KB (2)
pAUC (1% max FPR)
AC
0.75
Ours (k=1, m=16)
0.70
Ours (k=1, m=1024)
Ours (k-50. mm16) 16)
0.65
0.60
0.55
0.50
10
15
20
25
30
35
40
45
50
%
Corruption
Figure 2: Effect of the amount of (random token replacement) corruption detection pAUC (flat scheme;
mixed T's) with 1% max FPR.
Histogram of Entropy
Perf. lower bound for k= m=1024
1.0
1.0
0.8
Density
0.6
AUC
0.4
0.4
== 50
T 300
0.2
T 100
T 400
0.2
T= 200
T 500
0.0
0.0
0.5
1.0
1.5
2.0
2.5
3.0
0.5
1.0
1.5
2.0
2.5
3.0
Entropy
Entropy (alpha)
Figure Left: Histogram 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 function of the entropy term for the range of values we observe empirically. When m is large, becomes reasonable estimator of the LLM's entropy.
observe how well our sample's empirical CDF agrees with U(0, 1). Table 8 shows the statistic and p-value for various hyperparameter settings, while Figure depicts the empirical CDFs themselves for visual confirmation. We clearly observe the importance n on the independence assumption. As we expect, decreasing n means greater the chance of reusing scods and as result implics less independence and more distortion. Rocall, however, that the benefit of smaller is greater robustness allacks, so there trade-ofls. The choice of k has less of an effect than n.
17

---

Published in Transactions on Machine Learning Research (02/2026)
Perf. lower bound for k= opt. alpha
Perf. lower bound for k=1, opt. alpha
1.0
1.0
0.9
0.8
0.8
AUC
0.7
AUC
0.6
0.6
0.4
0.5
T 5
T 50
m 32
0.4
==
T= 100
0.2
m
m 512
0.3
== 25
T= 200
m 16
m 1024
10
15
20
25
200
250
m
T
Figure 4: Left: A lower bound for ROC-AUC predicted by Theorem 4.2 as a function m (using optimal a = log(m)). Right: Same plot, but as function of T (again, using optimal a).
Simulated Entropy, V 32k
8
Entropy (alpha)
7
6
5
3
2
uniform
log(m)
1
zipf
0
1000
2000
3000
4000
5000
m
Figure Given a distribution over the vocabulary (taken to be of size 32k), we can estimato for finite via simulation (1000 trials). We observe that when the underlying next-loken distribution is uniform, z log(m) in practical range for However, when the underlying distribution is Zipf (less entropy), quickly deviates from (m) as m grows and the probability of sampling duplicate tokens increases.
18

---

Published in Transactions on Machine Learning Research (02/2026)
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
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
3.20
0.618
97.9
90.0
94.0
80.2
Flat (k =
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
2
4.10
0.568
78.9
53.1
67.4
51.0
4.06
0.572
91.2
65.3
80.5
55.0
Flat (k = 10)
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
2
3.79
0.581
65.5
50.5
57.
50.2
4
3.76
0.584
78.4
52.0
66.1
50.7
Flat (k = 50)
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 Results (10% corruption, 1% max FPR) for U0, 1) when a meta p-value used for scoring, wherein the n-gram-level p-values are combined using Fisher's method. The k == setting is precisely stochastic version of Aaronson Corrected. AUCs, pAUCS, and their standard errors scaled by 100.
Detection Perf.
Detection Perf.
1.0
0.90
PAUC (1% max FPR)
0.85
0.9
KB (2)
0.80
0.75
AUC
0.8
Ours (k=1, m=16) 6)
0.70
KB (2)
0.7
Ours (k=1, m= m=00=4044-- 0224)
0.65
A
Ours (k=50, m=16)
K
0.60
Ours (k= 1, m=16)
0.6
0.55
Ours (k=1 1, m=1044)
Ours (k=50, m=16)
0.50
50
100
150 T
200
250
50
100
150
200
250
T
Figure 6: Impact of number of test samples T on detection performance (flat scheme) for GEMMA-7B- INSTRUCT on eli5-category.
19

---

Published in Transactions on Machine Learning Research (02/2026)
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
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
Flat 1)
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
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
Flat (I: 10)
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
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
Flat (k: = 50)
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
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
Flat (k: 1)
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
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
Flat (k: = 10)
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 3: Results when the likelihood-ratio test is used for scoring in place of p-values. When F = (0, the null and alternative likelihoods estimated non-paramelrically using kernel density estimation (KDE). When F' - Gamma(1 (L/k, 1), the densities given in Theorem 4.4 are used. AUCs, pAUCs, and their standard errors are scaled by 100.
20

---

Published in Transactions on Machine Learning Research (02/2026)
PPL
LH
AUC
PAUC
C. AUC
C. pAUC
Max Std. Error
0.04
0.002
0.1
0.2
0.1
0.2
N(, 1)
2
3.47
0.597
90.4
68.7
81.7
58.5
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
Flat (k = 1)
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
2
4.13
0.567
84.1
56.3
73.3
52.1
4.02
0.573
94.2
73.3
85.8
59.8
Flat (k = 10)
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
3.82
0.580
71.0
50.9
62.5
50.4
3.73
0.585
83.8
53.9
72.4
51.5
Flat (k 50)
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
x
2
3.45
0.597
86.2
62.1
75.5
54.5
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
Flat (k = 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
4.12
0.567
81.6
54.4
69.8
51.4
4.04
0.573
93.5
70.3
84.0
57.7
Flat (k = 10)
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
3.77
0.583
68.1
50.6
58.7
50.2
3.74
0.585
82.0
52.9
69.4
51.0
Flat (k: = 50)
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 4: Rosults (10% corruption, 1% max FPR) when is N(0,, 1) or x3 and p-values are used for scoring. AUCs, PAUCS, and their standard errors are scaled by 100.
21

---

Published in Transactions on Machine Learning Research (02/2026)
LH
AUC
pAUC
C. AUC
C. PAUC
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
0.5
0.596
70.7
51.7
68.3
51.2
49.0
49.8
0.594
85.4
59.9
81.9
56.5
52.9
49.9
Kirchenbauer
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
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
Flat (I: (==11 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
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
Flat (k: = 10)
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
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
Flat (l: 50)
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
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
Rec. (Ic 1)
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
0.567
89.6
64.9
80.3
55.6
48.0
50.0
Rec. (k: 10)
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
4
0.582
75.9
52.2
67.0
51.0
46.5
49.9
Rec. (k: = 50)
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 5: Average per-token likelihoods and detection performance when the negative class taken to be won-watermarked generations sampled with temperature For paraphrasing, target lengths of (150, 200, 250) used in calculating AUC and pAUC. The trends here consistent with those discussed in the main text, where the negative class consists of not-waaermarked argmax greedy generations and perplexity is used to measure distortion. AUCs and PAUCS are scaled by 100.
22

---

Published in Transactions on Machine Learning Research (02/2026)
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
0.5
1.649
0.808
61.6
50.7
1
1.673
0.803
72.1
52.3
Kirchenbauer
2
1.836
0.782
87.8
63.0
3
2.159
0.743
95.3
78.5
2.847
0.683
98.3
90.0
Kuditipudi
1.615
0.814
58.4
51.0
2
1.631
0.810
77.1
53.6
1. 1.623
0.811
87.0
61.7
1.621
0.812
92.4
70.3
Flat = 1)
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
1.657
0.807
89.4
61.7
Flat (k = 10)
1.653
0.808
94.7
75.0
4
1.652
0.808
80.5
52.6
Flat (k 50)
16
1.645
0.810
89.7
60.4
1.623
0.813
82.1
57.0
16
1.621
0.812
87.5
63.0
Rec. (k: - 1)
32
1.630
0.810
88.1
63.9
512
1.615
0.815
90.0
66.7
1.665
0.805
84.0
56.2
Rec. (k: 10)
1.662
0.806
89.6
64.4
4
1.664
0.806
73.2
51.2
Rec. (k: = 50)
16
1.653
0.808
79.4
53.5
Table 6: Main results (mixed T's for AUC and pAUC where max FPR is 1%) for GEMMA-7B -ISERRUISTCCT on the eliš-category test split. AUC and pAUC are scaled by 100. We observe the same trends here as with MISTRRLL-B-INSTRRCCT on databricks-dolly- 15k. When & and m = 1024 (white-box setting) we are slightly better in perplexity and detection (sans corruption) than Kuditipudi et al. (2023) and on-par with Aaronson (2023). Kirchenbauer et al. (2023a) can always outperform when matched
detection by cranking up 5, but perplexity, achieve better detection. For example, 5 = 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 A = 1,m 1024 and even 1.645 / 89.7% 7% when k = 50, m = 16 (black-bax).
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
Table 7: Detection performance (mixed T's) when a sum-based p-value is used in the length correction of Aaronson (2023). 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.
23

---

Published in Transactions on Machine Learning Research (02/2026)
Gamma w/ LRT. T= 1000 beta=1
Gamma w/ LRT. k=50, beta=1
1.0
1.0
TPR @ 1% FPR
0.8
TPR @ 1% FPR
0.8
0.6
0.6
0.4
0.4
k=1
k=30
m=2
m=
k=5
k=40
m=4
m= 64
0.2
k=10
k=50
m=8
m= 128
k=20
m= 16
m=2
0.0
0.0
10
20
30
40
50
0
25
50
75
100
125
150
175
200
m
T
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 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.
empirical CDF of u
1.0
n=4, k=1
n=3, k=1
n=2, k=1
n=1, k=1
n=4, k=10
0.6
0.2
0.8
Figure 8: Empirical CDF of the us's tracked during watermarking 20 random prompts from databricks-dollyy 15k using MISTRAL-70 -BTTRAL-7B-INSTRUOT with our flat scheme. We can clearly see that decreasing n causes the empirical distribution to deviate further from the CDF of (0. 1) (the line y = x).
# samples
KS
p-value
4
32
38605
0.0122
2.0e-05
3
32
38997
0.0121
1.3e-05
2
32
27055
0.0503
5.9e-60
32
21185
0.0920
2.4e-156
4
10
32
15655
0.0104
6.7e-02
Table KS statistic and corresponding p-value for our test of independence. We see that decreasing n results in larger KS (more distortion) and a lower p-value for rejecting the mull that the seeds are independent.
24

---

Published in Transactions on Machine Learning Research (02/2026)
A.3 Omitted Proofs
Lemma A.1. Assume all drows from LM( P; k) are ii.d. with distribulion p. and that the unique seeds across n g-rrrmm and sequences, (Stth are conditionally independent given the counts of the sampled sequences. Then the output of any number of calls to WATERMARKSINGL. with LM using key K are also i...d with distribution p.
Proof. For concreteness, let mn be the number of calls to WATERMARKSINGLE, where the w-th call draws m samples Q = {QQ (Q...))......(pa) (p.m) from LM (M P: k)). 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 deterministic function K,P that takes input sequences Q2 and outputs one of them. The randomness in the deduplication of n-grams is non-issue since it is independent across calls. Since functions of independent random variables are independent and {Qu) m is independent, so is K.P (Q.)) This proves independence.
Now, we prove that the outputs are identically distributed with the same distribution as their inputs. To do this, consider the u-th call in isolation and for ease of notation, let (Qi...., 2m Qu and Xw = &F (Qw). Let ( (X),))) be the unique sequences and corresponding counts. Note that the {(X;, ci) need not be independent (it. easy come up with a counter-example). Tet S be the integer seeds for X; after doduplication. Conditioned on (o......;). (St. independent and so RRa consists of i.i.d. d. draws from F by virtue of pseulorandomness. As F also continuous, we have that when conditioned on (cI....,c;),
itd ui ~ U(0,1) 1) for i = J. by the inverso-sampling theorem.
Let x be any sequence. We wish to show that P(X,. = x) = =((x). Let e E 1Q: = z). The independence of the 1(2, = z)'s follows from the independence of the Qi's, and thus c ~ Binomial(m,, u(z)). Clearly, Pff2 selected] = 0) = If e then obviously one of the X,'s x, and we can, without loss of generality, label X1 = x and 6 e, so that Pf(22 selected] c = i) P((X1 selected] [1 = i). Now,
P((X, selected) | (l....,,y) PP
{ 1 argmax, u m/a) }
c.....
IP {{ argmax, ct/ c\/m
log(ue)
C1 cl......)
PP (f1 argmin, log(- log()))
/c.....
P (f1 argmax, - log((- ((o(loo(())) + log(ce/ /mmm (I)...,
Let g. log(- log(u))). It is a known fact that if us itd what is often referred to the "Gumbel-Max trick' in machine learning. Conditioned on (CI,..., cj),
~ Gumbel(O, 1). Now we can apply ~ (0, 1), then ge sid
c//m Σ, ) = Categorial (c//m),
argmax, Dt + log(es/m) ~ Categorial
Thus,
P([x, selected]
|c 1, ,, i, .c......)
P([2, selected] | | ()=
Σ
IP = i)
C2.....y
i/m P(ci =)) i/m.
P(c =10==)) =
Putting it all together, we have that
m P(X,, = x) Σ
Pff2 selected] c c= ([))p((c = i)
1=0
m
m
( (((z)(( (1(=)((--p(x)"" -(x)))=-
m
mu((x) =x(x).
25

---

Published in Transactions on Machine Learning Research (02/2026)
We have shown that the outputs of WATERMARKSINGLE mutually independent and carry the same distribution ja as their inputs.
Remark. The proof of Lemma A.1 treats the secret key K as fixed (possibly unknown);; trealing it as random changes the story, as we illustrate with the following toy example.
Suppose that regardless of the conditioning prompt, the LLM outputs one of two sequences I1 or D2 with equal probability. Let u, = SCORESEQS(F, (2,), K, n, P) for E {1.2}. If m is very large, then it becomes very likely that X1 = 21, X2 T2 (modulo the labeling) and 0 02 m/2 and so argmax u, u////e argmax; 14- The outputs to two sequential calls to WATFERMRKKSINGLE 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 Iı we learn that our scheme with key K prefers I over I2, and so we will likely output Φ 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 WATERMARKSINGIA and WATERMAKKREURSSVa are distortion- free and then that autoregressive calls to them as done by WATERMARK preserves this property.
To show WATERMARKSINGLL is distortion-fee free, we observe that the LM argument supplied is the true underlying language model j and that our stochastic samples from the model are i.i.d., so we can apply Lemma A.1 directly.
Distortion-free for WATERMARKKEOURSSV follows easily from induction on t, the number of keys (and hence the number of recursive calls). When i 1, the LLM is the true underlying language model, so the outputs are iid. from μ. We get t == by combining Lemma A.1 with the inductive step that the outputs of WATFERMARKEECURSIVE with keys (K2.... Kot1) are i.i.d. from μ.
Finally, we show that auloregressive decoding where sequences no longer than k tokens are generaled one at a time via watermarking continues to be distortion free.
To do this, we introduce two sets of random variables: (X 10 1 represents k-sized chunks of the model's response when watermarking is not employed that is, x represents non-watermarked response tokens for indices (i - 1)k +1 to ik: Unused chunks can be set to a sentinel value like d. {x(²) } represents the same collection but when WATERMARK is employed. Let x be a sequence of any length. Partition x into contiguous k-sized chunks (2i...., Note that z, may have length less than if the stop-token was reachod in that chunk, but all other chunks have exactly & tokens. With P as the original prompt, we need to show PPX x: P) IP any length.
P); where X and X, the watermarked and non-watermarked responses of
P(X x P) P(X It ((t-1)- r1-1...., x(1) 1 P) P(X x1 P)
= P(X w = 32
fT-1)) P(X 11 P)
Because WATERMARKSINGLE and WATERMARKRECURRIT are distortion-ffe::: = =P((X") Dz ((.=),....
P)
= P((,, = x).
Proof of Theorem 4.3. First consider the flat scheme. Under the null, given our assumption of independence, itd
Rý F, so Fa Σ, R3) ~ U(0, 1) and the result follows. For the recursive scheme, we know from the flat
scheme and from assumed independence that P3 sid U(O,1), 1), where P, is the p-value associated with the j-th key. Thus, y ~ X2Ip| so that (1) ~ 1).
Lemma A.2. Assume the conditions of Theorem 4.2. Conditioned on the counts of each token in the vocabulary, and which taken id i" was selected (i.e. is the argmax), u Beta(m/ce. 1)-
26

---

Published in Transactions on Machine Learning Research (02/2026)
Proof of Lemma A.2. Let 2, = -m where us sid U00, 1). Then, 24 Exp(cs/m) and
= argmax "; m/e: argmin, m log(us)/cs argming zi-
By nice properties of the Exponential, we have that
~ Exp Σ G = =1x((1).
u. exp(-cp /m), so
P(u. 5t)= 2 -m -mlo(t))/c=)) cxp(m log(t)/cc)) tm/or.
Differentiating this with respect to t, we recover the pdf of Beta(m/c.-..
Proof of Theorem 4.2. F is U0, 1). The detection score is Fr [, R₂) with Rj sid under Ho and when conditioned on the counts C' and the argmax token ids 1", R2 Beta (m/Cnr;:1) under Hi. Redefine sg and 81 be Σ; R2 under Ho and Hi respectively.
P(Fr(ss) 2 Fr((o)) P(1 80) E,(81 2 1),
where (rWinHall(T) since su the sum of T i.i.d. UO, 1)'s. Our task now is find a lower-bound for 81- Noting independence across tokens and that Rg [0, 1]. we can use Popovicin's bound on variance obtain
v(s1) = 1 V(R)) S _ (1 -1-0)=
T
Plugging in the expectation of a Beta and recalling that when conditioned on C, the probability that token in the vocabulary is the argmax token at step j is Cjs/m, we have
Cya/m Cza/m
E(st)
Σ Eg Σ
1=1
With tedious calculation, it can be shown that
j j E [I...., m,, where
Au log(x), for
m
m
1)
A log(m)
m +
2
Thus,
Cj. m
Cj.i m
E(si) >
Σ
AEC Σ 1 [C 0]
log
②
j=1
1=1
Σ Xa = T/2 XTa.
With bounds on expectation and variance, proceed to upper-bound the error. Firstly, we have that,
E(s so) T/2 + XTa T/2 = XTo 2,
V(si so) T//4 1//44T/12 T/3.
27

---

Published in Transactions on Machine Learning Research (02/2026)
P(s - su) P(s1 80 E(s so) -B(s1 so))
$ P(s - E(s1 so) S aTaa)
V(si - 80)
V(81 80) + (XTa)²
1 1 37
where the penultimate line follows from Cantelli's inequality. Thus, we have that
P(81 2 8o) = P((11 S 80)) 2 1+1/337203)
Proof of Theorem 4.4. Let r be the PRF value for some n-gram from the text we wish to text. Let Fo = Gamma(1/k; 3) with pdf fo and F = =-Gamma(1/// m33) with pdf f1- By definition, r ~ Fo under Ho. By our assumptions, G4 = and [Ra] = kt Vi. So, argmax u, m//s, argmax " argmax, FR (Es R
argmax, E, argminn E, Rı,, where the second-to-last equality follows from the monotonicity of Fk. Eg Ri.j Gamma(k/kk, B3 Exp(1, 9). E, RRii Expp(1, m,3), because the minimum of Exponentials is Exponential. Thus, Vj, Ri-.i -Gamma (1/k, m/) Pi and r Fi under Hi. Now let R refer to the T lest-time PRF values. From the independence of Lest n-grams, the log-likelihood ratio test has score s(It) E (log fi (R.) log fo (R:)) and the fact that it is the uniformly most powerful test follows directly Pearson lemma. We now have that,
from the Noyman-Pearson
fo(r) = 31/2 (0ap///--xxppx1)
T(1/K)
/////1/k
fi(r) r(1/k)
exp(mBr),
T T log(m) (m 11)8 Σ
s(R)
RS so that
k
T
PHo (8 1) Pho
(m- Σ >
(m)
(( and
k
T
PHi (8 51)= = Pæi
(m-1)3) Σ
R3 < 1
log log(m)
Ga (Q(1)) where
K
Q(1) T Tlog(m)/k
(m - -1)3
28

---

Published in Transactions on Machine Learning Research (02/2026)
B Code
For full reprodueibility, we provide Python implementation of our algorithm, largely following the pseudocode presented earlier.
Amport collections
from collections import abc import bashlib
ämport typing
import numpy as up import scipy
TokenIda: typing TypeAlias tuple[int]
10
11
def int (tokene TokenIde, key: int) >> int:
12
hashlib. sha256()
code str (key) + str (tokens)
14
m. upupaa (code 'utf-81)) int hexdigest(), 16)
17
def (seedd: [iat])nt]] float:
if not seeds:
20
seeds [None]
different choice / plugged here.
vals [np. random deffulltrng(seel) uniform() for seed in seeds]
28
return scipy. stats. irwinhall. edf (np. sum(vals), len(vals)
def score_seqs( 26
seqs: 1ist [TokenIds] key: int, ctx len: int, prefix: TokenIds
-> dict (TokenIdss float]:
20
""*Return dictionary mapping each sequence to pseudorandon value.
seeds_withs with_id
for seq_id, tokens in enumorate(segs):
32
tokens_ves ciinnss_tt__ppeefi prefix tokens
range(len(pretixx, mmatookens_utth_prrffie
ctx tokens_ sateas_vttt____e_eeeeeee (rtt, len=
35
seed int int_hash(ctr, (ctx, key)
seeds_with_ append (seed,, id)]
np randon wwwdsfieeeesdd__ttttaaaa used_seeds- set()
38
seduped__seed [[] for seqs]
for seed, seq_id in seeds_with_
41
seed not in used used_ seeds:
42
deduped_seeds [seq_[e id] (seed) used_ seeds. (seed))
44
seq_to_prn dict()
45
seq_id, seeds enumerate (deduped_ _eedss) (sequsasassssee_iaeal calc_prn(seedd) return seq_to_pa
47
50 def c
key: int,
29

---

Published in Transactions on Machine Learning Research (02/2026)
canad::: int,
ctx_len: int,
54
prompt: TakenIda,
seq_lem: int,
11m: abc. Callable([Tokenl]) int], TokenIds),
57
stop_cond: abc. Callable[[Token]] [TokenIde), bool],
TokenIds:
tokens ()
60
while not (oop.con(tooken)))
tokens watermark_single
key, n_cands, ctx_len, prompt tokens, len, 11m
63
tekens
68
def vaternark_eingled
key: int, n_ canadds: int,
69
ctx_len: int,
prompt: TokenIds,
72
seq_len: int,
11m: Caw.Callllllelleeeec [[TokenIda, int], TokenIds],
>> TokenIds:
75
sequ [11m(prompt, seq_len) for in range((__cadd)]
76
seq, counter collections. Counter(seqe)
unique_seqs List(seq_counta) keys())
78
pe_pto_ acore_seqs (unique_seqs, key, ctx_len, prompt)
seq_to_pranseq] *x (float (n_cads) seq_counter (seq]) for seq in unique_seqe
81
]
return unique_sequ (np argnax(scores))
84
def (se:: TokenIds, key: int, ctx_len: int) -> float:
57
return score_seqs [[sq]], key, ctx_len, ()) [seq]
def waternark @atermark_recursivee recursive( 90
keys: [int],
pecy: int, ctx_len: int,
98
94
prompt: TokenIds,
seq_len: int,
96
11m: abc. Callablae [aTlabll[[Tokenda int], TokenIds),
stop_cond: [allsble[[Tokenddae bool],
>> TokenIds:
98
Total number of candidates is n. L.cmma_ppr..kkeeeeeneeeee
while not :
102
tokens tokens + vaternark_recursive_siii single((
103
keys, __cands_per_key, ctx_len, pronpt tokens, seg_ 11m
106
return tokena
108
def naternark__ecurrive__iig
30

---

Published in Transactions on Machine Learning Research (02/2026)
keya: list[int]. p_cands_per_kays int, ctx ctx_len: int,
111
prompt: TokenIds,
seq_len: int,
114
11m: abc. Callable[[TokenIde int], TokenIds],
TokenIds: if len (keys) =- 1:
116
117
1lm_rec 11m
118
else:
1lm_rec = lambda _prompt, _seq_len:
120
keya[i:], __cands_per_ka__ ctx_len, prompp,, sen, 11m
return vatermark_singlt single(
123
key=[o], n_ cands_ perrt__ee___e__ ctx_len, prompt, seq, 11m rec
126
def detect_ recursive(
seq: TokenIds,
120
keys: list List(
ctn_
>> float:
132
pvals [1 detect(eeq, key, ctx_len) for key in keys]
133
y -2-ap.eum sum logpvals))))))
return scipy stats. chi.. c1f2.cdf(( edf(y, (pvaass)))s)
Furthermore, we provide an example of our watermarking applied to a dummy language model that generates tokens at random.
matplotlib inport pyplot plt from sklearn import metrics
key
ca_cadd__err key ** len(keys) == cands n_ n_nasd 64
keys 2, 3,
Leand_pper_key
ctx ctx_len-
prompt 10
seq_len 20
12
max len_ 100
18
stop_cond lambda len(x) max_lem len trtrials 200
15
Increasing vocab_stt size increases entropy and hence
16
strength of watermark.
vocab_eiie size 100
18
18
def handon_iln(pprett seq_len):
21
To ezperiment with variable length responses,
change range(seq_ len) rapge(np, random. randint (1, seg, ten+1))
return tuple(
24
rondrandom.commm rwwdiintodnn... vocab_siza for in rangu len)
25
31

---

Published in Transactions on Machine Learning Research (02/2026)
27
28
def randon_ _anllon__mm____ lellnlnonnppppee 1aln_Iooppprrmpt, seq_len):
tokens ()
while not coo__con(tokens):
31
tokena tokens random, 11m (pronpt tokens, seq_len)
tokens
31
def Simulate_flat()
pos_scores [
37
scores
in r
pos_scores.appet
40
detect(
watermark( key, n_cands, ctx_len, prompt,
43
seq_len, madoo_lln, stop
46
key,
46
ctx_len,
48
neg_ (
50
detect(
randon_ Bando__in__loppppe looppppprrrrpptt seq_len), key, ctx_len
59
return neg_scorea, pos_scores
55
def dimulate__reursivee
58
ros_scores
59
neg_ scores
for in range (n_rrall):)
61
pos_scores.aae ( detect_recureivel
watermark_recurstve
61
keys, n_cands_pet _eer__eyy, ctx_len, prompt, seq_len,
randon_1las 1lnd stop_cond
67
keys,
68
ctx_len,
70
neg scoree..cc.o...... (
detect_recursivet
78
randon_llap lindo__ll__ooopprrnng seq_len), keys, ctx_len
76
return neg_scores, pos_scores
77
79
for scheme, (pogescorea, pos_scores) in zip(
50
['flat', 'recursive'], [eimulate_flatt), Linulate_reccrsivee
):
82 auc metrics. roc_auc_score
32

---

Published in Transactions on Machine Learning Research (02/2026)
[0] #eee(ueg__coores)
[1] +]]+een(ppee (pen(ppo__cooee))
neg. acoree poa_acores
)
85
(
pos_scores, "abel=ff'<chemme katermarked', range= 1],
bins=30, color='red',
56
(
neg_ scores, label= mooeel-'non-ttemarreed range= 1],
91
bins-30, color-'blut 'blue', a1pha-0.3,
plt. title(f 'Sore histogran. ROC-AUC (auc:0.2f).)
94
plt. legend()
show()
C Examples of Watermarked Outputs
We provide examples of watermarked outputs (minimally reformatted) under different schemes for the prompt: "Give me list of some characteristics good coffee shop?".
Aaronson (2023)
1. Comfortable and inviting atmosphere
2. Good quality coffee beans
3. Professional and friendly staff
4. A wide variety of coffee and food options
5. Specialty menu items and unique flavors
6. clean and well-maintained space
7. cozy and comfortable seating area
8. Free Wi-Fi and plenty of charging stations
9. A welcoming and inclusive environment
10. Reasonable prices for their food and beverages.
These are just a few of the characteristics of a good coffee shop, course, tastes and preferences vary from person to person.
Additionally, good coffee shop may have other unique features that make it stand out, such art music displays, outdoor seating, or community events.
Ultimately, the best coffee shop for you will depend on your individual values and preferences.
Opinions vary, but consult websites such as Yelp or TripAdvisor for reviews and recommenattions from other coffee lovers. Also, try visit few coffee shops in your area and sample their products to find the right fit for you. Happy coffee shopping! #collegenow #studentlife #coffee
Kirchenbauer et al. (2023a) (8 2)
Answer: 1. Comfortable and inviting atmosphere
2. High-quality coffee and food
3. Knovledgeable and friendly staff
4. Adequate seating variety beverage and food options
6. Wide range of fresh ingredients
33

---

Published in Transactions on Machine Learning Research (02/2026)
7. A menu that caters to different dietary needs
8. Competitive prices
9. A clean and well-maintained space
10. great selection of pastries and baked goods.
Result: good coffee shop should have comfortable and welcome atmosphere, provide high-quality coffee and food, have friendly and knovledgeable staff, offer a wide range of options for beverages and food, use fresh ingredients, cater to different dietary needs, have competitive prices, be clean and well- maintained, and offer a great selection of pastries and baked goods. #CoffeeShop #Characteristics #Qualities #HighQuality #Comfortable #Inviting #Friendly #Knovledgeable #FreshIngrediente #DietaryNeeds #Pricing #Cleanliness #Pastries #BakedGoods #Cafeteria #Restaurant
Flat (k: = 1, 1024)
1. Comfortable and welcoming atmosphere: A good coffee shop should have a relaxing and comfortable environment that encourages customers to linger and enjoy their coffee
2. Quality coffee: The coffee should be of high quality and freshly brewed. Baristas should be skilled and able to make a variety of coffee drinks to customers' liking.
3. Good food options: A good coffee shop should offer a variety of food options, from pastries and sandwiches to salads and soups. The food should coffee.
good quality and complement the
4. Friendly and attentive staff: The staff should be friendly and attentive to customers' needs. They should be able to make recommendations and provide excellent service.
5. Wide range of drinks: A good coffee shop should offer a wide range of drinks, such as tea, hot chocolate, smoothies, and ice coffees.
quiet and efficient workspace: The coffee shop should have a quiet and efficient workspace for customers who need to work while they sip their coffees.
7. Good music and ambiance: A good coffee shop should have relaxing and comfortable ambiance, with good music and lighting that complement the overall experience.
range of seating options: The coffee shop should have range of seating options, including tables, sofas, and armchairs, cater customers' preferences and needs.
Kuditipudi et al. (2023)
good coffee shop should have the following characteristics:
1. Quality coffee: A coffee shop should serve high-quality coffee that is well-roasted and brewed perfection.
2. Comfortable atmosphere: The shop should have a cozy and inviting atmosphere that attracts customers for their morning coffee routine or a mid-day break.
Variety of beverages: Apart from coffee, a good coffee shop should also offer a variety of other beverages like tea, chocolate, and smoothies.
34

---

Published in Transactions on Machine Learning Research (02/2026)
4. Friendly and attentive staff: The staff should be friendly, attentive, and knowledgeable about the menu.
5. Adequate seating: A coffee shop should have enough seating to accommodate customers who want to sit and enjoy their coffee.
6. Cleanly maintained: The shop should clean, neat,
and well-maintained to maintain high level hygiene.
7. Elegant and sophisticated decor: The decor should be elegant and sophisticated, giving the customers sense of style and class.
8. Free or fast Wi-Fi: A coffee shop should offer free or fast and reliable Wi-Fi so customers can stay connected while sipping on their coffee.
Greedy Decoding
Comfortable and inviting atmosphere: good coffee shop should have a cozy welcoming ambiance that makes customers feel home. This includes comfortable seating, soft lighting, and pleasing decor.
2. Quality coffee: The most important characteristic of coffee shop is the quality of the coffee. It should be freshly brewed, made with high-quality beans, and served at the right temperature. 3. Friendly and attentive staff: The staff at coffee shop should friendly, kmovledgeable about the menu, and attentive customers' needs. They should be able to make recommendations and provide excellent customer service.
4. Variety of menu items: A good coffee shop should offer variety of menu items, including breakfast, lunch, and snack options. This can include sandwiches, pastries, salads, and other light bites.
5. Convenient location: A coffee shop should located in a convenient and accessible location, such as a busy street near park public transportation hub.
6. Good music: A coffee shop should have good selection of music that complements the atmosphere and appeals to customers. This can include classical, jazz, or contemporary music.
7. Community involvement: good coffee shop should be involved the local community and support local events organizations. This can include hosting events, sponsoring
35


Reviews:
[{"review_id": "9j2nPzCZXy", "reviewer": "Reviewer_XwC3", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes a new approach to watermark the output of large language models (LLMs). The proposed method is black-box, i.e. only requires sampling from the LLM, although it can benefit from access to logits if available. The paper provides theoretical results to support the approach (under some assumptions), and the method offers several hyperparameters to control performance and trade-offs. In the experimental evaluation, the proposed method performs better or on par with the baselines, achieving high detection while preserving good response quality. Several analyses and ablation studies are provided.\n\nStrengths\n- The paper discusses the similarities and differences of the proposed method to existing ones.\n- The experiments show that the proposed method may be competitive with the baselines.\n- The paper provides intuitions about the proposed methods and the observed results, together with several analyses.\n\nWeaknesses\n- As the baselines, the proposed method is not robust to paraphrasing.\n- The improvements in performance compared to the baselines seem to be relatively small.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The experiments support the claim that the proposed black-box method performs similar to white-box baselines.", "audience_yn": "Yes", "audience_explanation": "Watermarking the output of LLMs is an established and relevant topic, and this work contributes to this line of work.", "requested_changes": "- I'd suggest to clearly mark in Table 1 which methods are white-box and which black-box. Also, I think the effect of using the proposed approach in the white-box setup should be discussed (how do the results change).\n\n- While I think the presentation is in general good, Sec. 2 discusses technical differences to related works before introducing them or the proposed method. I'd consider postponing such detailed discussion to later sections.", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "6RjvLsOLKt", "reviewer": "Reviewer_4hJw", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a black-box watermarking framework for large language models (LLMs), where watermarking is achieved without access to next-token logits. The scheme operates by sampling multiple candidate sequences from the LLM and selecting one according to pseudorandom scoring rules defined by a secret key. The authors claim that their approach is distortion-free, recursive, and competitive with existing white-box watermarking methods in detection performance. Theoretical guarantees and empirical evaluations are provided.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The results broadly support the core claim that black-box watermarking can achieve high detectability without accessing logits, but the theoretical assumptions and limited robustness testing prevent the evidence from being fully convincing.", "audience_yn": "Yes", "audience_explanation": "The topic of this paper would be of clear interest to a portion of TMLR’s audience. Watermarking of LLM outputs, especially under black-box access, is an increasingly important problem at the intersection of trustworthy AI, security, and generative model governance.", "requested_changes": "1) **Paper Organization and Readability**  \nThe presentation could be better organized. The pseudocode (currently placed in the Appendix) is essential for understanding the algorithm and should be included in the main text. Moreover, some lengthy discussions of related work would be better positioned after the algorithm description; at present, the reader encounters detailed comparisons before fully grasping how the proposed scheme works.\n\n2) **Lack of Robustness**  \nThe watermark exhibits limited robustness to paraphrasing and even moderate token corruption, as shown in the empirical results. While robustness is a general challenge in watermarking and the paper does mention possible extensions (for example, semantic watermarking), the manuscript would benefit from minimal targeted experiments to substantiate these ideas. As it stands, the current method fails to withstand paraphrasing at all. \n\n3) **Impact of Limited Distribution Access**  \nA more explicit discussion is needed regarding how the lack of access to the underlying probability distribution affects performance. When $k=1$ and $m$ is large, the scheme approximates the standard white-box setting but at high computational cost. Conversely, when $k$ grows, performance degrades sharply. The paper should provide a clearer intuition for how this trade-off between $k$, $m$, and detection accuracy arises from the inability to directly bias token probabilities.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "Ihao9rwXYq", "reviewer": "Reviewer_gKqQ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a novel black-box watermarking scheme for large language models (LLMs) that only requires the ability to sample text sequences from the model—no access to logits or internal probabilities is needed. The method works by:\n1. Sampling m candidate sequences from the LLM for a given prompt;\n2. Scoring each sequence using a pseudorandom function (PRF) keyed by a secret, applied to n-grams in the sequence;\n3. Selecting the highest-scoring sequence as the watermarked output.\n\nThe scheme is distortion-free: under mild independence assumptions, the distribution of watermarked outputs matches that of the original model. It also supports recursive watermarking, where multiple parties can embed independent watermarks in a service chain without coordination, and detection can be performed jointly using only p-values (preserving key secrecy).", "claims_and_evidence_yn": "Yes", "claims_explanation": "The paper supports its core claims with both theoretical analysis and extensive empirical validation.", "audience_yn": "Yes", "audience_explanation": "TMLR’s audience includes researchers working on learning systems, trustworthy AI, statistical detection, and LLM safety. This paper directly addresses several topics of clear interest.", "requested_changes": "Add a brief empirical check (e.g., correlation of PRF scores across overlapping n-grams in real generations) to assess how often the assumption is violated in practice.\n\nThe paper mentions “semantic watermarking” as an extension. A short discussion (even 1–2 paragraphs) on how semantic units (e.g., SRL frames, AMR graphs) could be integrated would enhance practical relevance.\n\nEnsure Kirchenbauer baselines use updated best practices (e.g., ignore_repeated_ngrams=True, self-hashing) as per the official repo. The current comparison may underestimate Kirchenbauer’s performance if outdated settings are used.\n\nReport inference-time overhead (e.g., 1024× sampling cost). While inherent to the black-box setting, quantifying this trade-off would aid practitioners.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)