betaFeedback

WorksComputer Science

Reconciling Privacy with Provenance for Language Model Watermarks

Abstract

Watermarking has great potential for regulating the use of language models (LMs), but its deployment has been marred by controversy, as many users argue that fine-grained tracking of LM usage violates their privacy. This tension reduces the effectiveness of watermarks, as users engage in evasion strategies such as paraphrasing that can remove much of the watermark signal. We show that provenance and privacy can be reconciled if we shift the goal of watermark design from tracking individuals to estimating aggregate usage. We develop locally differentially private watermarks which provably limit the evidence that any individual text can contribute to detection, while still enabling accurate estimation of population frequencies. We introduce the Red-Green Sequence (RGS) watermark, a private and computationally efficient watermark that achieves accurate frequency estimation at high privacy levels across various models, sample sizes and generation entropies in settings that reflect realistic deployment scenarios. On C4 language modeling tasks, we attain 0.00190.0019 MSE with 0.00380.0038 mean absolute bias at a low ε\varepsilon of 1, while in more challenging settings such as an essay writing task with only 100 text samples, we still find errors on the order of 0.01130.0113 MSE with 0.0040.004 mean absolute bias at ε=2\varepsilon=2.

Introduction

Watermarking has emerged as a promising approach to enable content provenance through injecting recoverable signals into each piece of model generated text ([23, 27]). Among provenance techniques, watermarking is unique in providing a false positive guarantee. If the detection key is kept secret, the false positive rate of identifying a piece of text as being LM generated can be precisely controlled via the generation mechanism ([48]).

While provable guarantees for tracking individual texts are powerful for the targeted monitoring and regulation of AI-generated content, they have also faced significant pushback from users in recent times ([42, 16]). A major deployment by Anthropic ([2]) has led to accusations of surveillance and concentration of power ([6, 7]), amidst increasing concerns that steganographic techniques may be used to spy upon users ([41, 5]).

The tension between the desire for accurate tracking by regulators and users’ desire for privacy has also led to adversarial dynamics ([35]), where users actively modify their text to evade watermark detection. Even simple strategies, like paraphrasing by another language model, can erase most of the signal from the watermarks ([26, 47]). This leads

Correspondence to: [email protected]. Code is available at github.com/elisel yhan/dp-watermarks. to a paradoxical situation where the precision and accuracy of a watermark lead to user behavior that sabotages watermark efficacy.

Therefore, we ask if we can achieve many of the provenance goals of watermarking without violating individual privacy. We answer the question in the affirmative: we observe that many of the regulatory and monitoring goals of watermarking only require population level tracking [33, 24, 40]. In these cases, it is possible to design privacy-preserving watermarks that enable accurate estimation of the prevalence while protecting individuals.

We develop the Red-Green Sequence (RGS) watermark, which is a locally differentially private watermark that provably limits the evidence that any individual text can contribute to detection [12, 13], while enabling efficient estimation of the prevalence of watermarked texts in a population of texts.

Our watermark builds upon standard red-green style language model watermarks [23], but carefully modifies them to be effective in the local differential privacy setting. We find that sequence-level watermarks, which are unappealing in the nonprivate setting, are highly efficient in injecting watermarks in private, low-ε\varepsilon settings.

To obtain good estimates of aggregate watermark frequencies from these watermarks, we identify several interesting statistical problems in the bias-variance trade-offs of moment estimators for privacy-preserving watermarking, where the natural variability of watermark entropy across texts leads to different sampling and estimation choices compared to standard, randomized-response style estimators.

We implement this watermark on a range of scenarios, finding our frequency estimates to be highly accurate across a range of settings. In a standard C4 language modeling task, we can attain a low MSE of 0.0019 with 0.0038 mean absolute bias at a low ε\varepsilon of 1, while in more challenging settings like an essay writing task with very few text samples, we still find errors on the order of 0.0113 MSE with 0.004 mean absolute bias at ε=2\varepsilon= 2. These results suggest that privacy-preserving watermarking is possible and effective.

Related Work

Language model watermarks inject recoverable statistical signal into the generated text to enable detection of the presence of the watermark from the text. Prominent token-level watermarks work by reweighting token-level probabilities with a secret key [23, 28, 34] or coupling sampling with key randomness [27, 10] (Aaronson 2022; Li et al. 2026a). Among these, the closest to our work is Kirchenbauer et al. [23], who use the idea of slightly upweighting pseudorandomly chosen “green” tokens that can later be detected. Our approach similarly uses a colored biasing scheme, but our goals and techniques differ significantly from theirs in that we aim to precisely control the signal rather than maximize it.

Our watermark preserves privacy by making the key-conditional watermarked text distribution close to the one without the watermark. While distortion-free watermarks [27, 18, 46] achieve a similar goal, their watermarks only preserve the base model distribution in expectation over the sampling randomness in the secret key. Such equality in marginal distributions does not imply that watermarked and unwatermarked text distributions remain close conditional on a fixed key. In fact, the separation in conditional distributions is what enables high-power detection, which is at odds with privacy. Another related objective is cryptographic undetectability ((Christ et al., 2024; Christ and Gunn, 2024)), which ensures the marginal distributions of watermarked and unwatermarked texts are computationally indistinguishable to anyone without the secret key, but not conditional on the key. While Kim et al. [22] constructs watermarks under key-conditional ff-divergence bounds, which can cover differential privacy constraints, their goal is to recover multi-bit messages from individual texts rather than estimate population watermark prevalence. On the other hand, Li et al. (2026b) estimates the proportion of watermarked content within individual texts rather than across a population of texts, and does not provide privacy guarantees.

Our watermark guarantees privacy formally through local differential privacy (DP) ([12, 13]), and the watermark method is inspired by randomized response ([45]), which enables efficient estimation of the prevalence of sensitive attributes while protecting individual respondents, achieving local DP guarantees. The privacy–utility tradeoff under local DP has been studied by Duchi et al. [11]; Kairouz et al. [21], who establish information-theoretic optimality of randomized response in several settings. Related variants of randomized response have also been used for frequency estimation in a fixed population under local DP ([3, 44]). Our setting departs from randomized response and generic local DP estimation by incorporating two important constraints. First, our private mechanism must enable signal to be recoverable from the output text alone, without requiring a separate report from each individual. Second, while randomized response allows for modification of distributions for groups with and without the sensitive attribute, our watermark must modify only the text distributions of the watermarked group, as the unwatermarked group’s generation process is beyond watermark control.

Problem Setup

Watermarks for language models

The process of watermarking involves modifying the standard language model decoding process using a secret key kk, so that correlations between the choice of the key and text output can be used to detect whether a piece of text was generated by an LM decoder that uses kk.

More formally, let xx be a prompt, and pxp_x be the base model’s distribution over sequences given xx. We sometimes suppress the dependence on xx. A watermark consists of a decoder Γ\Gamma, which is an algorithm that maps a secret key k∈Kk \in\mathcal{K} and distribution pxp_x to a sequence y∈Yy \in\mathcal{Y} stochastically, i.e. it specifies a new distribution over completions, usually different from the base model distribution pxp_x, and samples a sequence yy from the new distribution. The decoder is designed to allow detectors to detect the presence of the watermark in a text sequence yy given the secret key kk.

For example, suppose Y\mathcal{Y} consists of only single-token sequences. Then, the Soft Red List watermark of Kirchenbauer et al. [23] has the following decoder:

Pr⁡[Γ(k;px)=y∣k]=px(y)exp⁡(δ1{y∈G})∑y′∈Ypx(y′)exp⁡(δ1{y′∈G}),(1)\Pr[\Gamma(k; p_x) = y \mid k] = \frac{p_x(y)\exp(\delta1\{y \in\mathcal{G}\})}{\sum_{y' \in\mathcal{Y}} p_x(y')\exp(\delta1\{y' \in\mathcal{G}\})}, \tag*{(1)}

where G\mathcal{G} is the set of green tokens obtained by partitioning the token space into green and red tokens via a hash function with key kk, and δ\delta is a parameter that controls the strength of the watermark. The decoder biases the watermark towards outputting more green sequences than usual. Generalizing to longer sequences, the watermark applies the same bias towards green tokens at each token position, so a text with many green tokens is strong evidence for the watermark. Consequently, an LM user who is unwilling to disclose their LM usage might paraphrase the watermarked text before publishing, in the hope of reducing the number of green tokens and evading detection.

Importantly, watermarks are often designed to allow for high-powered detection from a single piece of text. In the case of a red-green list watermark, any moderately long piece of text will carry an exponentially increasing watermark signal, and many watermarking papers show extremely low p-values for high-entropy sequences [23, 27].

The core claim of our work is that we can instead consider watermarks that more precisely control the watermarking signal, where individual texts still contribute enough signal to accurately estimate the aggregate prevalence of watermarked texts in a population, but are too weak to reliably identify any individual. To illustrate how we construct this estimator, we first illustrate a similar tension in survey design and how it can be addressed.

From individual detection to aggregate estimation: randomized response

Consider the scenario of reporting a sensitive attribute in response to a survey question, such as “have you ever used illegal drugs?” It has long been known that survey respondents can often alter their answers to avoid the possibility that their true, sensitive status may later be revealed [43]. To address this, survey designers have developed techniques that incentivize respondents to answer truthfully while maintaining the integrity of the survey [29]. One such technique is randomized response (RR) [45], which allows respondents to reveal sensitive information to interviewers with plausible deniability.

Consider a fixed pool of nn respondents whose sensitive attributes are W1,…,Wn∈{0,1}W_1,\ldots,W_n \in\{0,1\}, with Wi=1W_i=1 indicating that respondent ii has the sensitive attribute. Suppose that the true prevalence of the sensitive attribute in the pool is λ=1n∑i=1nWi\lambda= \frac{1}{n}\sum_{i=1}^{n} W_i.

In a generalized randomized response (RR) mechanism, each respondent engages independently with a randomization device with 0<π0<π1<10 < \pi_0 < \pi_1 < 1, and outputs a noisy answer Hi∈{0,1}H_i \in\{0,1\} with these probabilities:

Pr⁡[Hi=1∣Wi=1]=π1,Pr⁡[Hi=1∣Wi=0]=π0,Pr⁡[Hi=0∣Wi=1]=1−π1,Pr⁡[Hi=0∣Wi=0]=1−π0.(2)\begin{aligned} \Pr[H_i=1 \mid W_i=1] &= \pi_1, & \Pr[H_i=1 \mid W_i=0] &= \pi_0,\\ \Pr[H_i=0 \mid W_i=1] &= 1-\pi_1, & \Pr[H_i=0 \mid W_i=0] &= 1-\pi_0. \tag*{(2)} \end{aligned}

Standard symmetric RR sets π1=1−π0\pi_1=1-\pi_0. RR provides plausible deniability to the respondents: if they had reported a sensitive answer H=1H=1, they can still claim that it was due to randomization since there is π0>0\pi_0>0 probability that they are forced to report H=1H=1 even if their true status is W=0W=0.

Such plausible deniability can be formalized by the notion of local differential privacy (DP) [12, 13]. Consider a randomized mechanism which maps a private bit WW to a discrete output Y∈YY \in\mathcal{Y}. The mechanism is ϵ\epsilon-locally differentially private [13] if

Pr⁡[Y=y∣W=w]≤eϵPr⁡[Y=y∣W=w′]for all y∈Y and w,w′∈{0,1}.(3)\Pr[Y=y \mid W=w] \leq e^{\epsilon}\Pr[Y=y \mid W=w'] \quad\text{for all } y \in\mathcal{Y} \text{ and } w,w' \in\{0,1\}. \tag*{(3)}

This condition bounds the likelihood ratio of observing any output under the two possible values of the sensitive bit, thus limiting the evidence that the output can reveal about the sensitive bit. The reporting mechanism in equation 2 satisfies local ϵRR\epsilon_{\mathrm{RR}}-DP, where the privacy parameter

ϵRR=max⁡{ln⁡π1π0,ln⁡1−π01−π1}.\epsilon_{\mathrm{RR}}=\max\left\{\ln\frac{\pi_1}{\pi_0},\ln\frac{1-\pi_0}{1-\pi_1}\right\}.

While privacy is preserved by adding noise to each person’s true bit, aggregating the noisy bits still allows us to recover information about the mean of the true bits in the pool of nn respondents, λ=1n∑i=1nWi\lambda= \frac{1}{n}\sum_{i=1}^{n} W_i. This is because randomization is precisely controlled by the probabilities π0,π1\pi_0,\pi_1. Writing Hˉ=1n∑i=1nHi\bar{H} = \frac{1}{n}\sum_{i=1}^{n} H_i, we observe that E[Hˉ∣W]=λπ1+(1−λ)π0\mathbb{E}[\bar{H} \mid W] = \lambda\pi_1 + (1-\lambda)\pi_0. Correspondingly, the moment estimator

λ^RR=Hˉ−π0π1−π0(4)\hat{\lambda}_{\mathrm{RR}} = \frac{\bar{H}-\pi_0}{\pi_1-\pi_0} \tag*{(4)}

is unbiased and consistent for λ\lambda [45].

Increasing π1−π0\pi_1-\pi_0 widens the separation between the reporting probabilities with private bits W=0W=0 and W=1W=1, which makes each noisy output more informative about the private bit, which increases estimation accuracy but reduces privacy. For binary attributes, it has been shown that the randomized response mechanism with the following reporting probabilities attains optimal information utility under ϵ\epsilon-local DP [20]:

π0∗=σ(−ϵ)=11+eϵ,π1∗=σ(ϵ)=eϵ1+eϵ.\pi_0^*=\sigma(-\epsilon)=\frac{1}{1+e^\epsilon},\qquad\pi_1^*=\sigma(\epsilon)=\frac{e^\epsilon}{1+e^\epsilon}.

This choice maximizes the separation π1−π0\pi_1-\pi_0 and minimizes the variance of the moment estimator in equation (4) among all binary ϵ\epsilon-local DP mechanisms, which also minimizes the MSE since there is no bias.

Locally Differentially Private Watermarks

We have illustrated how randomized response can preserve individual privacy and produce efficient estimation of aggregate prevalence in the survey setting. Inspired by this, we design a watermark that is locally differentially private, and an efficient estimator for the prevalence of watermarked texts in a mixture of texts. First, we formalize the notion of local differential privacy for watermarks by directly adapting equation (3):

Definition 1. For some ϵ>0\epsilon> 0, a watermark decoder Γ\Gamma is ϵ\epsilon-locally differentially private with respect to the base model distribution pp, if for any key kk and any y∈Yy \in\mathcal{Y}:

e−ϵp(y)≤Pr⁡[Γ(k;p)=y∣k]≤eϵp(y)(5)e^{-\epsilon}p(y) \leq\Pr[\Gamma(k;p)=y \mid k] \leq e^\epsilon p(y) \tag*{(5)}

Denote p(⋅)p(\cdot) as the prior distribution of keys, and p(⋅∣y)p(\cdot\mid y) the posterior distribution of keys given observed text yy. Let q(y∣k)q(y\mid k) be the shorthand for Pr⁡[Γ(k;p)=y∣k]\Pr[\Gamma(k;p)=y\mid k]. Definition 1 then implies:

p(k∣y)=q(y∣k)p(k)∑k′q(y∣k′)p(k′)≤eϵp(y)p(k)∑k′e−ϵp(y)p(k′)=e2ϵp(k).p(k\mid y)=\frac{q(y\mid k)p(k)}{\sum_{k'}q(y\mid k')p(k')} \leq\frac{e^\epsilon p(y)p(k)}{\sum_{k'}e^{-\epsilon}p(y)p(k')}=e^{2\epsilon}p(k).

Applying the same argument in the other direction gives p(k∣y)≥e−2ϵp(k)p(k\mid y)\geq e^{-2\epsilon}p(k). Viewing the watermark as introducing an association of the text with the secret key (Li et al., 2025), this condition limits the strength of such association that can be inferred by an observer with the key, and thus provides a natural notion of privacy for arbitrary distributions of non-watermarked text.

The Red-Green-Sequence (RGS) Watermark

We now present a simple construction for a watermark that satisfies ϵ\epsilon-local DP, which we call the Red-Green-Sequence (RGS). RGS closely follows the classic token-level red-green list construction of Kirchenbauer et al. [23], but involves a few subtle changes that arise from our desire to fulfill local differential privacy.

Algorithm

The biggest difference between RGS and Kirchenbauer et al. [23] is that RGS operates at the sequence level, i.e. RGS only applies watermark bias to complete sequences, rather than at every token. For Kirchenbauer et al. [23], who operate without privacy constraints, watermarking at the sequence level is computationally expensive and unnatural. Identifying the set of potential green and red sequences requires a large Monte Carlo sample and provides little benefit, as injecting small distortions at each token generation step already provides exponentially strong detection signal.

In contrast, for differentially private watermarking, we have the opposite problem. Token-level watermarks lead to hard-to-control privacy leakage, as the information that we leak is a sequence of red-green labels whose length equals the length of the sequence, which is a high-dimensional bit string that is difficult to keep private. This challenge is analogous to the observation in locally differentially private frequency estimation that the optimal estimator is equivalent to a one-bit randomized response-style estimator, as that is the minimal information that needs to be leaked to enable frequency estimation ([11, 20]). Because of this, sequence-level watermarking is far more natural in our setting, and we encode exactly one red-green bit for each sequence.

We begin with a naive implementation of this sequence-level approach: given a prompt, we first draw MM candidate completions in parallel from the underlying base model, partition them into green and red bins with a keyed hash function, and reweight them appropriately to select the final response. The full pseudocode is presented in Algorithm 1.

Algorithm 1 RGS generation

Require: Prompt xx, candidate budget MM, privacy budget ε\varepsilon, keyed hash hkh_k with parameter π0\pi_0

  1. Draw Y~1,…,Y~M∼iidLM(⋅∣x)\widetilde{Y}_1,\ldots,\widetilde{Y}_M \overset{\mathrm{iid}}{\sim} L_M(\cdot\mid x).

  2. Deduplicate to {(Yj,cj)}j=1m\{(Y_j,c_j)\}_{j=1}^{m}; set pj←cj/Mp_j \leftarrow c_j/M.

  3. G←{j:hk(Yj)=G}\mathcal{G} \leftarrow\{j:h_k(Y_j)=G\}; PG←∑j∈GpjP_G \leftarrow\sum_{j\in\mathcal{G}}p_j.

  4. QG←min⁡{eεPG,1−e−ε(1−PG)}Q_G \leftarrow\min\{e^\varepsilon P_G,1-e^{-\varepsilon}(1-P_G)\}.

  5. if PG∈{0,1}P_G\in\{0,1\} then

  6. Set qj←pjq_j \leftarrow p_j for all j∈[m]j\in[m].

  7. else

  8. For each j∈[m]j\in[m], set

    qj←{pjQG/PG,j∈G,pj(1−QG)/(1−PG),j∉G.q_j \leftarrow\begin{cases} p_jQ_G/P_G, & j\in\mathcal{G}, \\ p_j(1-Q_G)/(1-P_G), & j\notin\mathcal{G}. \end{cases}
  9. end if

  10. Draw j∗∼Categorical⁡(q1,…,qm)j^* \sim\operatorname{Categorical}(q_1,\ldots,q_m).

  11. return Yj∗Y_{j^*}.

Comparing Algorithm 1 to the earlier token-level red-green watermark in equation (1), we see that one major difference is in the definition of the reweighting term QG/PGQ_G/P_G, which is not a fixed offset determined by δ\delta, but a term that is set to precisely attain our target privacy budget on either the green or red list probability ratio. With this choice of reweighting, we attain our local DP guarantee.

Proposition 1 (RGS privacy). RGS is locally ε\varepsilon-DP with respect to the base model.

The proof follows directly from our choice of reweighting coefficients. We defer the proof to

Appendix B.1.2.

One major drawback of sequence-level watermarks is that the requirement of drawing MM parallel samples for one completion is highly wasteful (compared to token-level ones, which are essentially free). However, another difference between standard watermarking and our setting is that the watermarking strength per sequence is very low, and thus the difference in distribution before and after watermarking is very small. This enables highly efficient rejection sampling algorithms for our setting, which downweight all red completions by a multiplicative factor of e−εe^{-\varepsilon}. At ε=1\varepsilon= 1, the empirical mean number of samples needed by the rejection sampler per watermarked response is around 1.5 on real data, see § 7.4.

Algorithm 2 RGS via rejection sampling (RGS-reject)

Require: Prompt xx, candidate budget MM, privacy budget ε\varepsilon, keyed hash hkh_k with parameter π0\pi_0

  1. Initialize counter C=0C = 0

  2. while C<MC < M do

  3. Sample a sequence completion Y∼LM(⋅∣x)Y \sim\mathrm{LM}(\cdot\mid x) independently

  4. Increment the counter C←C+1C \leftarrow C + 1

  5. if hk(Y)=Gh_k(Y) = G then

  6. return YY.

  7. else

  8. With probability e−εe^{-\varepsilon}, return YY

  9. end if

  10. end while

  11. return YY.

We show formally that our nominal privacy level ε\varepsilon and the expected number of samples needed by the rejection sampler are directly linked. The proof is given in Appendix § 11.1.3. The stronger the privacy, the fewer samples needed.

Fact 1 (RGS-reject expected sample count). The expected number of samples needed for the rejection sampler in Algorithm 2 is at most 1/(Pr⁡[hk(Y)=G∣k]+e−εPr⁡[hk(Y)=R∣k])1/(\Pr[h_k(Y) = G \mid k] + e^{-\varepsilon}\Pr[h_k(Y) = R \mid k]).

As this is a rejection sampler, there is a natural bound on the probability ratio between the original distribution and our sampler, giving a local DP guarantee. The proof of the following privacy guarantee is given in Appendix § 11.1.4.

Proposition 2 (RGS-reject privacy). The rejection sampler in Algorithm 2 is ε\varepsilon-DP.

We remark that the two samplers use different reweighting rules. The rejection sampler upweights the probability of green candidates relative to red ones by a fixed multiplicative factor of eεe^{\varepsilon}. The parallel sampler instead uses the empirical green fraction PGP_G from the MM parallel samples to calculate the largest reweighted green probability allowed by the privacy constraints. To see the difference between the weighting rules and to remove the finite budget effect for later analyses, we first state convergence properties of the samplers.

Fact 2 (Finite-sample convergence). For any key kk, denote g=Pr⁡[hk(Y)=G∣k]g = \Pr[h_k(Y) = G \mid k] as the probability of sampling a green sequence from the underlying base model distribution. Let qparMq_{\mathrm{par}}^M and qrejMq_{\mathrm{rej}}^M denote the probabilities that the parallel and rejection samplers return a green sequence with candidate budget MM. Then, with M→∞M \to\infty,

qparM→min⁡{eεg,1−e−ε(1−g)},qrejM→eεgeεg+1−g.q_{\mathrm{par}}^M \to\min\{e^{\varepsilon}g, 1 - e^{-\varepsilon}(1-g)\}, \qquad q_{\mathrm{rej}}^M \to\frac{e^{\varepsilon}g}{e^{\varepsilon}g + 1 - g}.

The proof is deferred to Appendix § 11.1.5. In the infinite budget limit, because eεgeεg+1−g≤min⁡{eεg,1−e−ε(1−g)}\frac{e^{\varepsilon}g}{e^{\varepsilon}g+1-g} \le\min\{e^{\varepsilon}g, 1-e^{-\varepsilon}(1-g)\}, the parallel sampler can achieve a larger green probability, while the rejection sampler achieves much better computational efficiency by stopping early.

Connection to Randomized Response

We might view RGS as a type of randomized response (RR) for watermarking, since both methods privatize the true attribute via a randomized one-bit report. While broadly this is correct, there are two major conceptual differences between RR and our watermarking setting that lead to complexities. First, while RR can randomize for both the group with the sensitive attribute and the group without, RGS can only randomize for the watermarked group, since the unwatermarked group is not generated by the watermark decoder.

Additionally, RGS uses a keyed hash function where a fixed key always assigns the same color to the same sequence, so an analyst can recover the report from the observed text. The construction of the keyed hash function and associated assumptions are discussed in the next section and Appendix § 10. With the key fixed, the noise in the report now comes from the randomness in sampling the underlying LM. This comes with an important consequence: the extent to which the randomization can be controlled depends on the inherent properties of the underlying base model distribution. The higher the entropy, the better control we have over the randomization, and the more accurate the prevalence estimate can be. We discuss the implications on estimation and design choices in detail in the next section.

Estimation

Having established privacy, we turn to the statistical objective of estimating watermark prevalence. Let Y1,…,YnY_1,\ldots,Y_n be a mixture of watermarked and unwatermarked texts, with Wi∈{0,1}W_i \in\{0,1\} indicating whether YiY_i is watermarked. We define λ=1n∑i=1nWi\lambda= \frac{1}{n}\sum_{i=1}^{n}W_i as the true prevalence of watermarked texts in the mixture. Finally, writing W=(W1,…,Wn)W=(W_1,\ldots,W_n), we assume that Y1,…,YnY_1,\ldots,Y_n are mutually independent conditional on WW and the shared key kk.

Denote the index sets of watermarked and unwatermarked texts as I1={i:Wi=1}I_1=\{i:W_i=1\} and I0={i:Wi=0}I_0=\{i:W_i=0\}. For each i∈[n]i \in[n], define pip_i as the reference distribution for the text. For i∈I0i \in I_0, pip_i may be any distribution over text sequences and need not come from a language model. For i∈I1i \in I_1, pip_i is the underlying base model distribution without the watermark decoder Γ\Gamma. For example, if the text is generated by prompting the watermarked LM with a prompt xx, then pip_i is the model distribution p(⋅∣x)p(\cdot\mid x). Throughout, WW and the distributions {pi}i=1n\{p_i\}_{i=1}^{n} are fixed, and we suppress the conditioning on these quantities.

Moment Estimator

The similarity of RGS to randomized response naturally motivates the use of a moment estimator for prevalence estimation. To construct this estimator, we first derive the expected fraction of green texts with and without the watermark.

For each i∈[n]i \in[n] and any fixed key kk, denote the probability of sampling a green sequence under the unwatermarked distribution pip_i as

gi(k)=∑y∈Ypi(y)1{hk(y)=G}.(6)g_i(k)=\sum_{y\in\mathcal{Y}}p_i(y)\mathbf{1}\{h_k(y)=G\}. \tag*{(6)}

For watermarked texts i∈I1i \in I_1, the probability of sampling a green sequence is upweighted, which we define as

qi(k)=Pr⁡[hk(Γ(k;pi))=G∣k].(7)q_i(k) = \Pr[h_k(\Gamma(k; p_i)) = G \mid k]. \tag*{(7)}

Let Hi=1{hk(Yi)=G}H_i = \mathbf{1}\{h_k(Y_i) = G\} and Hˉ=1n∑i=1nHi\bar{H} = \frac{1}{n}\sum_{i=1}^{n} H_i. Under the conditional independence assumption, the indicators HiH_i conditional on WW and kk are independent Bernoulli random variables with success probabilities gi(k)g_i(k) for i∈I0i \in I_0 and qi(k)q_i(k) for i∈I1i \in I_1 respectively. Therefore,

E[Hˉ∣k]=1n(∑i∈I1qi(k)+∑i∈I0gi(k)).\mathbb{E}[\bar{H} \mid k] = \frac{1}{n}\left(\sum_{i \in I_1} q_i(k) + \sum_{i \in I_0} g_i(k)\right).

Note that for a fixed kk, the probabilities gi(k)g_i(k) and qi(k)q_i(k) are generally not knowable without assumptions about the underlying distributions pip_i. To enable estimation, RGS uses a coloring scheme such that each gi(k)g_i(k) has a known expectation over random keys and then uses Ek[gi(k)]\mathbb{E}_k[g_i(k)] as a plug-in for the unknown gi(k)g_i(k)’s.

Ideally, we would pick kk uniformly at random, and any sequence would be equally likely to be green or red. However, to enable later detection, we must fix kk and have a deterministic coloring as a function of this key. To balance these two competing goals, we implement coloring by thresholding the output of a keyed hash, modeled as a pseudorandom function (PRF) [15]. We can then sample the key kk once uniformly at random, and reuse it across all texts. The details of the construction can be found in Appendix § 10. As a consequence of this construction, we adopt the following assumption for our statistical analysis:

Assumption 1 (Ideal coloring). For every finite collection of distinct sequences y1,…,ymy_1, \ldots, y_m fixed independently of the random key kk, the indicators

1{hk(y1)=G},…,1{hk(ym)=G}\mathbf{1}\{h_k(y_1) = G\}, \ldots, \mathbf{1}\{h_k(y_m) = G\}

are independent Bernoulli(π0)(\pi_0) random variables.

In the formal PRF definition, these are only computationally indistinguishable [15], but we omit the negligible distinguishing advantage from our notation.

Under this idealization, we can characterize both the key-averaged green probability and its variation across keys. The following lemma also accounts for dependence between gi(k)g_i(k) and gj(k)g_j(k) arising from the use of the same key. Its proof is given in Appendix § 11.2.1.

Lemma 1. Let pip_i and pjp_j be fixed distributions over Y\mathcal{Y} independent of the key kk, and write

∥pi∥22=∑y∈Ypi(y)2,⟨pi,pj⟩=∑y∈Ypi(y)pj(y).\lVert p_i\rVert_2^2 = \sum_{y \in\mathcal{Y}} p_i(y)^2,\qquad\langle p_i,p_j\rangle= \sum_{y \in\mathcal{Y}} p_i(y)p_j(y).

Under Assumption 1,

Ek[gi(k)]=π0,\mathbb{E}_k[g_i(k)] = \pi_0,
Var⁡k[gi(k)]=π0(1−π0)∥pi∥22,\operatorname{Var}_k[g_i(k)] = \pi_0(1-\pi_0)\lVert p_i\rVert_2^2,
Cov⁡k[gi(k),gj(k)]=π0(1−π0)⟨pi,pj⟩.\operatorname{Cov}_k[g_i(k),g_j(k)] = \pi_0(1-\pi_0)\langle p_i,p_j\rangle.

Lemma 1 links the second moments of gig_i with the diversity of the distributions pip_i. We can see that ∥pi∥22\lVert p_i\rVert_2^2 is the probability that two independent draws from pip_i yield the same sequence, which is a measure of (the lack of) entropy of πi\pi_i, while ⟨πi,πj⟩\langle\pi_i,\pi_j\rangle is the probability that independent draws from πi\pi_i and πj\pi_j produce the same sequence, which measures the (lack of) “diversity” of the underlying distributions across individuals.

The variance identity in the lemma suggests that if the underlying distributions πi\pi_i have high entropy, and thus low ∥πi∥2\lVert\pi_i\rVert_2, then the green probability gig_i would be closer to π0\pi_0 on average. In a non-atomic idealization with ∥πi∥2→0\lVert\pi_i\rVert_2 \to0, the green probability gig_i converges in probability to the null frequency π0\pi_0. Therefore, with M→∞M \to\infty in both the parallel and the rejection samplers, the corresponding watermarked green probability is

π1={min⁡{eεπ0,1−e−ε(1−π0)},for the parallel sampler,eεπ0eεπ0+1−π0,for the rejection sampler.(8)\pi_1 = \begin{cases} \min\{e^{\varepsilon}\pi_0,1-e^{-\varepsilon}(1-\pi_0)\}, & \text{for the parallel sampler,}\\ \frac{e^{\varepsilon}\pi_0}{e^{\varepsilon}\pi_0+1-\pi_0}, & \text{for the rejection sampler.} \end{cases} \tag*{(8)}

In the ideal case where gi=π0g_i=\pi_0 for every ii, we have that λ~=Hˉ−π0π1−π0\tilde{\lambda}=\frac{\bar{H}-\pi_0}{\pi_1-\pi_0} is an unbiased estimator of λ\lambda conditional on kk and WW, exactly mirroring the moment estimator for randomized response. We use the clipped version of this estimator:

λ^=proj⁡[0,1](Hˉ−π0π1−π0).(9)\hat{\lambda}=\operatorname{proj}_{[0,1]}\left(\frac{\bar{H}-\pi_0}{\pi_1-\pi_0}\right). \tag*{(9)}

On the other hand, when the underlying distributions do not have perfect entropy, our gi(k)g_i(k) have nonzero variance over the choice of kk, and there is no guarantee that the average unwatermarked green frequency will converge to π0\pi_0, resulting in a biased estimator. We now characterize this estimator error that arises from finite watermark entropy and decompose it into bias and variance terms.

Proposition 3 (Key-conditional MSE). Fix any key kk. Fix W=(W1,…,Wn)W=(W_1,\ldots,W_n), and suppose that Yi∣WiY_i\mid W_i are conditionally independent. Let I1={i:Wi=1}I_1=\{i:W_i=1\}, I0={i:Wi=0}I_0=\{i:W_i=0\}. Assume 0<λ<10<\lambda<1, so that both I0I_0 and I1I_1 are nonempty. Define

V(k):=1n∑i=1n(Hi−E[Hi∣k]),V(k):=\frac{1}{n}\sum_{i=1}^{n}\left(H_i-\mathbb{E}[H_i\mid k]\right),
B(k):=1∣I1∣∑i∈I1(qi(k)−π1),B(k):=\frac{1}{\lvert I_1\rvert}\sum_{i\in I_1}\left(q_i(k)-\pi_1\right),
U(k):=1∣I0∣∑i∈I0(gi(k)−π0).U(k):=\frac{1}{\lvert I_0\rvert}\sum_{i\in I_0}\left(g_i(k)-\pi_0\right).

Then,

E[(λ^−λ)2∣k]≤1(π1−π0)2[E[V(k)2∣k]+(λB(k)+(1−λ)U(k))2](10)\mathbb{E}\left[(\hat{\lambda}-\lambda)^2\mid k\right]\leq\frac{1}{(\pi_1-\pi_0)^2}\left[\mathbb{E}[V(k)^2\mid k]+\left(\lambda B(k)+(1-\lambda)U(k)\right)^2\right] \tag*{(10)}
≤1(π1−π0)2[14n+(λB(k)+(1−λ)U(k))2].\leq\frac{1}{(\pi_1-\pi_0)^2}\left[\frac{1}{4n}+\left(\lambda B(k)+(1-\lambda)U(k)\right)^2\right].

While the variance term E[V(k)2∣k]\mathbb{E}[V(k)^2\mid k] vanishes as O(1/n)O(1/n), the bias terms B(k)B(k) and U(k)U(k) are not guaranteed to vanish, since they depend on the fixed key kk and the underlying distributions of the watermarked and unwatermarked texts. We defer the proof to Appendix § 11.2.2.

Null bias and distributional diversity

The term U(k)U(k) measures the bias in the green sequence fraction marginalized across all the unwatermarked examples. This bias can be small even when every individual text distribution pip_i has low entropy, provided the distributions are sufficiently diverse across examples.

To see this, observe that Lemma 1 implies

Ek[U(k)]=1∣I0∣∑i∈I0(Ek[gi(k)]−π0)=0,\mathbb{E}_{k}[U(k)] = \frac{1}{|I_0|} \sum_{i\in I_0} \left(\mathbb{E}_{k}[g_i(k)]-\pi_0\right)=0,
Var⁡k[U(k)]=π0(1−π0)∣I0∣2(∑i∈I0∥pi∥22+∑i,j∈I0,i≠j⟨pi,pj⟩).(11)\operatorname{Var}_{k}[U(k)] = \frac{\pi_0(1-\pi_0)}{|I_0|^2}\left(\sum_{i\in I_0}\lVert p_i\rVert_2^2+\sum_{i,j\in I_0,i\ne j}\langle p_i,p_j\rangle\right). \tag*{(11)}

In this case, we can see that the per-prompt entropies can be low (and thus ∥pi∥22\lVert p_i\rVert_2^2 can be high), but the variance is dominated by the cross terms ⟨pi,pj⟩\langle p_i,p_j\rangle for i≠ji\ne j, which can be small as long as each low-entropy distribution pip_i is mutually distinct from another. To illustrate this, consider an example where the distributions pip_i all put their mass on a single sequence, but they are all different across i∈I0i\in I_0. Then even with a fixed kk, because the sequences are all different, the colors would average out. Indeed, in this example ∥pi∥22=1\lVert p_i\rVert_2^2=1 for all ii, but ⟨pi,pj⟩=0\langle p_i,p_j\rangle=0 for all i≠ji\ne j.

Note that the variance term can also be written as Var⁡k[U(k)]=π0(1−π0)∥pˉ0∥22\operatorname{Var}_{k}[U(k)]=\pi_0(1-\pi_0)\lVert\bar{p}_0\rVert_2^2, where pˉ0(y):=1∣I0∣∑i∈I0pi(y)\bar{p}_0(y):=\frac{1}{|I_0|}\sum_{i\in I_0}p_i(y), ∀y∈Y\forall y\in\mathcal{Y} is the average text distribution across all unwatermarked texts. When the pool contains many diverse text distributions that spread the mass of pˉ0\bar{p}_0 over many distinct sequences, the unwatermarked bias term U(k)U(k) would concentrate around 0 more tightly.

Bias terms for watermarked texts

Unlike U(k)U(k) which can go away under a set of pip_i’s that are each low-entropy but collectively diverse, the bias term for the watermarked texts B(k)B(k) could be persistent even with diverse distributions across prompts. Consider the previous example where the pip_i’s are all concentrated on a single sequence that differs across ii’s. For a fixed key, for each ii we have gi(k)=1g_i(k)=1 or gi(k)=0g_i(k)=0 under both samplers, and the corresponding qi(k)q_i(k) is either 1 or 0, whose average need not equal π1\pi_1.

More generally, both samplers bias the model towards producing green sequences by taking the original base model green probability gi(k)g_i(k) and upweighting it via a concave function. Jensen’s inequality then implies a non-positive bias in expectation over kk.

Fact 3 (Key-averaged bias). Under Assumption 1, both samplers have Ek[B(k)]≤0\mathbb{E}_{k}[B(k)]\le0.

Proof. Let ff denote the mapping from base green probability to output green probability in the limit M→∞M\to\infty:

f(x)={eεxeεx+1−x,for the rejection sampler,min⁡{eεx,1−e−ε(1−x)},for the parallel sampler.f(x)= \begin{cases} \frac{e^{\varepsilon}x}{e^{\varepsilon}x+1-x}, & \text{for the rejection sampler},\\ \min\{e^{\varepsilon}x,1-e^{-\varepsilon}(1-x)\}, & \text{for the parallel sampler}. \end{cases}

Therefore, π1=f(π0)\pi_1=f(\pi_0). For either sampler, a finite candidate budget MM satisfies qi(k)≤f(gi(k))q_i(k)\le f(g_i(k)). Since ff is concave and Ek[qi(k)]=π0\mathbb{E}_{k}[q_i(k)]=\pi_0, Jensen’s inequality gives

Ek[qi(k)]≤Ek[f(gi(k))]≤f(Ek[gi(k)])=f(π0)=π1.\mathbb{E}_{k}[q_i(k)]\le\mathbb{E}_{k}[f(g_i(k))]\le f(\mathbb{E}_{k}[g_i(k)])=f(\pi_0)=\pi_1.

Averaging over i∈I1i\in I_1 yields Ek[B(k)]≤0\mathbb{E}_{k}[B(k)]\le0. For a fixed key, however, the average base green probability may differ from π0\pi_0, and B(k)B(k) can have either sign.

Bias control

Despite persistent bias, there exist design choices that can help us mitigate this bias through a bias-variance tradeoff. We show that adjusting the hash function hkh_k to have a larger null green fraction π0\pi_0 can reduce the bias at the expense of variance, improving total estimation error.

Consider the quantity d=π1−π0d = \pi_1 - \pi_0, which is the nominal separation in green probability between the watermarked and unwatermarked text, under the assumption that gi=π0g_i = \pi_0 for every single prompt distribution pip_i. As previously mentioned, this coincides with the randomized response regime, where dd is chosen to be the largest value that respects local ε\varepsilon-DP, which minimizes the variance of the estimator in the absence of bias. In contrast, in our watermark setting, a larger nominal separation dd might lead to a larger bias that could offset the benefits from decreasing variance. The following proposition illustrates such a bias-variance tradeoff, in the case with sufficiently many pieces of text (i.e. ∣I0∣→∞|I_0| \to\infty and ∣I1∣→∞|I_1| \to\infty) with sufficient diversity across individuals ii.

We remark that in the following theoretical analyses, we study the infinite sample budget limit M→∞M \to\infty to isolate the effect of the underlying text distributions on estimation error. For both samplers, by Fact 2 the finite-MM green probability qi(k)q_i(k) converges to f(gi(k))f(g_i(k)). Empirically, the effect of MM plateaus very quickly, see Figure 9 and Figure 10 in the Appendix.

MAPE versus candidate budget for rejection sampling

Figure 9. MAPE versus candidate budget MM for rejection sampling. Left to right: λ=0.1,0.5,0.9\lambda= 0.1, 0.5, 0.9.

MAPE versus candidate budget for parallel sampling

Figure 10. MAPE versus candidate budget MM for parallel sampling. Left to right: λ=0.1,0.5,0.9\lambda= 0.1, 0.5, 0.9.

Proposition 4 (Key-averaged MSE). Assume M→∞M \to\infty for both samplers, and

∥pˉ0∥22:=1∣I0∣2∑i,j∈I0⟨pi,pj⟩→0,∥pˉ1∥22:=1∣I1∣2∑i,j∈I1⟨pi,pj⟩→0.\lVert\bar{p}_0 \rVert_2^2 := \frac{1}{|I_0|^2} \sum_{i,j \in I_0} \langle p_i,p_j\rangle\to0,\qquad\lVert\bar{p}_1 \rVert_2^2 := \frac{1}{|I_1|^2} \sum_{i,j \in I_1} \langle p_i,p_j\rangle\to0.

Then

E[(λ~−λ)2]≤1d2E[V(k)2]+λ2d2(Ek[B(k)])2+R,\mathbb{E}\left[(\tilde{\lambda}-\lambda)^2\right] \leq\frac{1}{d^2}\mathbb{E}\left[V(k)^2\right] + \frac{\lambda^2}{d^2}\left(\mathbb{E}_k[B(k)]\right)^2 + R,

where the remainder R→0R \to0 as ∥pˉ0∥22\lVert\bar{p}_0 \rVert_2^2 and ∥pˉ1∥22→0\lVert\bar{p}_1 \rVert_2^2 \to0.

The proof is deferred to Appendix § 11.2.4. On a high level, this says that when there is enough diversity across different text distributions, only the sampling noise and the squared watermarked bias contribute to the error.

As illustrated in Fact 3, the nominal separation cannot be realized fully when the prompt distributions do not have perfect entropy, inducing a downward bias that need not vanish with sample size. This motivates us to mitigate this bias by reducing the nominal separation, which can be done by increasing π0\pi_0. The following proposition formalizes this monotonicity over sampler-specific ranges.

Proposition 5 (Bias mitigation by tuning π0\pi_0). Consider either sampler in the limit M→∞M \to\infty. For each π0∈(0,1)\pi_0 \in(0,1), let π1\pi_1 be the nominal watermarked green probability as in equation (8), and write d=π1−π0d = \pi_1 - \pi_0. Consider the normalized key-averaged bias

d−1∣Ek[B(k)]∣,d^{-1}\left|\mathbb{E}_k[B(k)]\right|,

where the key expectation is taken under ideal coloring with green probability π0\pi_0. Then:

  1. For the rejection sampler, d−1∣Ek[B(k)]∣d^{-1}\left|\mathbb{E}_k[B(k)]\right| is non-increasing on (0,1)(0,1).

  2. For the parallel sampler, d−1∣Ek[B(k)]∣d^{-1}\left|\mathbb{E}_k[B(k)]\right| is non-increasing on [σ(−ε),1)[\sigma(-\varepsilon),1), where σ(−ε):=(1+eε)−1\sigma(-\varepsilon) := (1+e^\varepsilon)^{-1}.

The proof is deferred to Appendix § 11.2.5. For the parallel sampler, the nominal separation dd is maximized at π0=σ(−ε)\pi_0 = \sigma(-\varepsilon), while for the rejection sampler it is maximized at π0=σ(−ε/2)\pi_0 = \sigma(-\varepsilon/2). This

result suggests that increasing π0\pi_0 beyond the RR-optimal values could improve bias at some cost of variance. This tradeoff is particularly relevant at large sample sizes, where sampling noise diminishes but systematic bias can persist. Consistent with this observation, we find empirically that the π0\pi_0 that works best at larger sample sizes is often substantially higher than the value that maximizes separation, see § 7.3.

Experiments

We now evaluate the empirical effectiveness of the RGS watermark at estimating the prevalence of watermarked texts in a mixture of watermarked and unwatermarked texts. To assess our estimator in both high-entropy and low-entropy settings, we consider a general language modeling task as well as a much harder coding and essay writing task inspired by real-world instruction-following tasks.

Models Throughout the experiment, we consider modern models and instruction-tuned models, consisting of Qwen3-1.7B, Qwen3-4B, Qwen3-8B, and Llama-3.1-8B-Instruct.

Shared watermark parameters and setup For computational reasons, we use the RGS rejection sampler in Algorithm 2 to generate watermarked completions, with a maximum of M=20M = 20 candidates, and the keyed hash is implemented as a 128-bit BLAKE2b hash [39] of the generated token sequence. Unless explicitly varied, we use π0=0.5\pi_0 = 0.5 throughout this section. Across RGS estimation experiments, including the ablations (see Appendix § 12), we average over 20 randomly sampled keys from the space of 128-bit keys, and 50 Monte Carlo mixture repetitions per key.

Internet text (C4)

We use prompts derived from the Colossal Clean Crawled Corpus (C4), a collection of cleaned web text [37]. We use the first 500 prompts from the processed C4 dataset in Pan et al. [36] as our prompt set. For each prompt, we independently sample 144 base model completions using vLLM with temperature=1 and top-p=1. For each prompt, 64 completions enter the unwatermarked source pool, while the remaining 80 are divided into 4 disjoint blocks of M=20M = 20 candidates for the rejection sampler. We truncate each candidate to its first T=50T = 50 generated tokens before hashing and RGS selection, and use the same prefix for detection.

For each λ∈{0.1,0.2,…,0.9}\lambda\in\{0.1, 0.2, \ldots, 0.9\}, we construct 50 Monte Carlo mixtures of total size n=2000n = 2000 with nλn\lambda watermarked and n(1−λ)n(1-\lambda) unwatermarked texts sampled uniformly without replacement from the watermarked and unwatermarked source pools. For each mixture, we test RGS generation and estimation with 3 different privacy budgets ε∈{1,2,3}\varepsilon\in\{1, 2, 3\}, and repeat the same test using a set of 20 randomly sampled keys.

Accurate frequency estimates with private watermarks We find that differentially private watermarks provide highly accurate estimates of frequency across a range of λ\lambda, ε\varepsilon, and nn values. Figure 1 shows our estimates of the frequency λ\lambda as we vary the true frequency λ\lambda across a wide range. Our estimates show low bias across the entire range, with average absolute biases of 0.0038, 0.0037, and 0.001 for ε=1,2,3\varepsilon= 1, 2, 3 respectively. The 5-95% percentile bands are generally tight, with average half-widths of 0.072, 0.040, and 0.031 for ε=1,2,3\varepsilon= 1, 2, 3.

RGS prevalence estimates on C4

Figure 1. RGS prevalence estimates on C4. Left to right: ε=1,2,3\varepsilon= 1, 2, 3. Markers show means and shading shows 5th–95th percentiles over keys and repetitions.

These findings hold across a range of ε\varepsilon values, and our estimator remains accurate even at a fairly stringent ε=1\varepsilon= 1 value. The main challenge of the estimator is maintaining low relative error at small true λ\lambda, but such an estimator may be inherently difficult to construct given the sampling noise inherent to randomized response style frequency estimates.

Sensitivity to watermark and experiment parameters To assess how the choices of parameters affect estimator performance, we conduct ablation studies on this C4 experiment. We vary the mixture sample size nn, privacy budget ε\varepsilon, temperature and generation length, sampler type, candidate budget MM, and number of distinct prompts in the mixture. The results are presented in Appendix § 12.

Instruction following

We then test RGS on a much more challenging setting, such as a small number of students sharing the same homework prompt, where the underlying distributions pip_i are low-entropy, and the prompts are highly homogeneous. Throughout this section, we use ε=2\varepsilon= 2. Our setting consists of two datasets: essay writing and coding.

Essay writing We randomly select 20 prompts from the OUTFOX dataset consisting of argumentative essay prompts [25]. Each mixture we test consists of 100λ100\lambda texts sampled from the RGS decoder, and 100(1−λ)100(1-\lambda) from the same base model, all independently sampled under the same prompt.

Coding We randomly select 20 problems from the LiveCodeBench dataset [19] and construct the same one-prompt mixture as the essay setting. We enable the thinking mode for Qwen3-1.7B and Qwen3-4B and allow them to emit at most 256 thinking tokens before the final answer, which reduces entropy and more accurately reflects realistic LLM use. For watermark generation and detection, we use the first T=100T = 100 generated tokens, excluding thinking tokens.

Accurate frequency estimates for instruction following settings We find that even in this extreme stress test where there is only a single prompt, and only 100 total samples, we are able to obtain accurate frequency estimates at ε=2\varepsilon= 2 (Figure 2). The essay setting shows low bias and low overall error across the range of λ\lambda, likely due to the higher per-prompt entropy. In contrast, the coding setting shows higher bias and variance, with visually distinguishable deviation from the unbiased x=yx = y line at low λ\lambda values. Despite this, the estimates have relatively low bias, and it is promising that even in extreme cases with very low diversity and entropy, we are able to obtain such estimates.

RGS prevalence estimates on OUTFOX and LiveCodeBench

Figure 2. RGS prevalence estimates on OUTFOX (left) and LiveCodeBench (right), with ε=2\varepsilon= 2. Markers show means and shading shows 5th–95th percentiles over keys and repetitions.

Bias control

We empirically test the effectiveness of the bias-mitigation strategy by tuning π0\pi_0 proposed in § 6.4. We follow the same C4 mixture construction procedure described above, using an expanded set of 1,000 prompts. We sample from Llama-3.1-8B-Instruct with temperature=0.2, and truncate each completion to T=20T = 20 tokens, reflecting low per-prompt entropy but high prompt diversity. We find that adjusting π0\pi_0 can significantly improve estimation error at large nn via the bias variance tradeoff. Figure 3 shows the mean absolute percentage error (100%∣λ^−λ∣λ)\left(100\% \frac{|\hat{\lambda}-\lambda|}{\lambda}\right) averaged over all mixtures and keys, for π0∈{0.1,0.2,0.3,0.4,0.5}\pi_0 \in\{0.1, 0.2, 0.3, 0.4, 0.5\} and λ∈{0.2,0.3,0.4}\lambda\in\{0.2, 0.3, 0.4\}, at ε=2\varepsilon= 2. In this setting, the value of π0\pi_0 that optimizes the separation is σ(−ε/2)=0.27\sigma(-\varepsilon/2) = 0.27. We observe that at small sample sizes, smaller π0\pi_0 generally achieves lower error, but gradually gets taken over by bigger values of π0\pi_0. In particular, for π0=0.1\pi_0 = 0.1 and 0.20.2, the errors plateau quickly across λ\lambda's. This corroborates our theory that bias persists, and at large sample sizes where bias dominates the total error, a larger π0\pi_0 value achieves a better tradeoff.

Mean absolute percentage error versus mixture size for different $\pi_0$ values

Figure 3. MAPE versus mixture size nn for different π0\pi_0. Left to right: λ=0.2,0.3,0.4\lambda= 0.2, 0.3, 0.4.

Computational efficiency

We show empirically that our rejection sampler is very computationally efficient, especially in small ε\varepsilon regimes, which is consistent with Fact 1. In Figure 4, we plot the mean number of candidates examined until a response is accepted for the rejection sampler, for ε∈{0.5,1,2,3}\varepsilon\in\{0.5, 1, 2, 3\} on C4, OUTFOX, and LiveCodeBench. We use a rejection sampling cap of M=20M = 20 and π0=0.5\pi_0 = 0.5. Each point averages the cost equally over 20 randomly sampled keys. Across models, we see that only an average of fewer than 1.5 samples are needed from the underlying base model at small ε\varepsilon of 0.5 and 1, while larger values ε=2,3\varepsilon= 2, 3 require only around 2 samples.

Mean candidates examined by the rejection sampler versus $\varepsilon$ for C4, OUTFOX, and LiveCodeBench

Figure 4. Mean candidates examined by the rejection sampler versus ε\varepsilon. Left to right: C4, OUTFOX, LiveCodeBench.

Discussion

In this work, we focused on the core challenges behind locally differentially private watermarking, and showed that careful construction of a sequence level, randomized-response style watermark can balance privacy and efficacy. However, there remains important future work in this direction, such as imbuing mild levels of robustness, since currently the sequence-level hashing used by RGS is sensitive to minor edits. Possible mitigations include using locality sensitive hashing [17] or incorporating error correcting codes [8]. While a token-level watermark like that of Kirchenbauer et al. [23] is more edit-robust and computationally efficient, it remains an important problem to control the total privacy leakage of such token-level watermarks, especially over long, autoregressive sequences. Preliminary investigation by the authors using the optimal DP composition theorem [21] over the text sequence shows some promise for frequency estimation, but the accuracy under a fixed sequence-level privacy budget requires further improvement.

Another direction for future work is mitigating privacy leakage across time from repeated inference, as currently our watermark does not guarantee privacy over unlimited queries by a single user. Although memoized randomized response can protect a sensitive attribute across repeated queries by reusing a previously randomized report [14], they apply randomization to both groups with and without the sensitive attribute. In the watermark setting, since the generation process of the unwatermarked group is outside our control, reusing the same noisy report could introduce a persistent shift in detection signal away from the unwatermarked baseline, revealing the watermark status over time.

Acknowledgements

We thank members of the Hashimoto group for useful discussions. ELH was supported by a Stanford Graduate Fellowship. TH was supported by a grant by HAI, gifts from Open Philanthropy, Amazon, Schmidt Sciences, Hudson River Trading, the Tianqiao and Chrissy Chen Foundation and a grant under the NSF CAREER IIS-2338866, ONR N00014-24-1-2609, and DARPA Cooperative Agreement HR00112520013. This work does not necessarily reflect the position or policy of the government and no official endorsement should be inferred.

Keyed hash construction

We construct the coloring scheme described in § 6 as follows: first, we use a keyed hash to generate a pseudorandom value for each sequence, then use a deterministic threshold to map that value to a green or red color. Specifically, we use keyed BLAKE2b [39] with a 128-bit digest. Let bk(y)∈{0,…,2128−1}b_k(y) \in\{0,\ldots,2^{128}-1\} denote the integer representation of the digest of an injectively encoded token sequence yy. Here, bkb_k is the keyed function modeled as a PRF. The coloring function hkh_k is its thresholded output, with the threshold chosen to obtain the nominal green probability π0\pi_0:

hk(y)=G⟺bk(y)<T,T=⌊π02128⌋.h_k(y) = G \Longleftrightarrow b_k(y) < T,\qquad T = \lfloor\pi_0 2^{128} \rfloor.

If bkb_k is modeled as a uniformly random function, distinct sequences receive independent colors, each with green probability

π~0=T2128,0≤π0−π~0<2−128.\widetilde{\pi}_0 = \frac{T}{2^{128}},\qquad0 \leq\pi_0-\widetilde{\pi}_0 < 2^{-128}.

We suppress this small rounding error in the analysis and use π0\pi_0 as the ideal green probability.

Proofs

Sampler proofs

Feasible reweighting under privacy

Lemma 2 (Feasible reweighting under privacy). Under Algorithm 1, with PG∈(0,1)P_G \in(0,1), a choice of QGQ_G satisfies

e−εpj≤qj≤eεpjfor all j∈[m]e^{-\varepsilon}p_j \leq q_j \leq e^{\varepsilon}p_j \qquad\text{for all } j \in[m]

if and only if

Lε(PG)≤QG≤Uε(PG),L_\varepsilon(P_G) \leq Q_G \leq U_\varepsilon(P_G),

where

Lε(PG):=max⁡{e−εPG, 1−eε(1−PG)},L_\varepsilon(P_G) := \max\{e^{-\varepsilon}P_G,\ 1-e^{\varepsilon}(1-P_G)\},
Uε(PG):=min⁡{eεPG, 1−e−ε(1−PG)}.U_\varepsilon(P_G) := \min\{e^{\varepsilon}P_G,\ 1-e^{-\varepsilon}(1-P_G)\}.

Proof. For PG∈(0,1)P_G \in(0,1), we have that qj/pj=QG/PGq_j/p_j = Q_G/P_G if hk(yj)=Gh_k(y_j)=G, and qj/pj=(1−QG)/(1−PG)q_j/p_j = (1-Q_G)/(1-P_G) if hk(yj)=Rh_k(y_j)=R. Therefore, e−εpj≤qj≤eεpje^{-\varepsilon}p_j \leq q_j \leq e^{\varepsilon}p_j is equivalent to satisfying both of these inequalities:

e−εPG≤QG≤eεPG,e^{-\varepsilon}P_G \leq Q_G \leq e^{\varepsilon}P_G,
1−eε(1−PG)≤QG≤1−e−ε(1−PG).1-e^{\varepsilon}(1-P_G) \leq Q_G \leq1-e^{-\varepsilon}(1-P_G).

Their intersection is the stated interval [Lε(PG),Uε(PG)][L_\varepsilon(P_G),U_\varepsilon(P_G)].

Proof of Proposition 1

Proof. Fix any key kk, and let p(⋅)p(\cdot) be the base model distribution given the prompt. The RGS decoder chooses QG=Uε(PG)Q_G = U_\varepsilon(P_G), which lies in the feasible interval in Lemma 2. Therefore, we have

e−εpj≤qj≤eεpjfor all j∈[m].e^{-\varepsilon}p_j \leq q_j \leq e^{\varepsilon}p_j \qquad\text{for all } j \in[m].

Conditional on the candidate set YMY^M, for any y∈Yy \in\mathcal{Y} that appears in the pool, let cyc_y be the number of appearances of yy in YMY^M. For sequences not in the set, cy=0c_y = 0. Then, we have

e−εcyM≤Pr⁡[Γ(k;p)=y∣k,YM]≤eεcyM,∀y∈Y.e^{-\varepsilon}\frac{c_y}{M} \le\Pr[\Gamma(k;p)=y \mid k,Y^M] \le e^{\varepsilon}\frac{c_y}{M}, \qquad\forall y \in\mathcal{Y}.

Taking expectations over YMY^M and using EYM[cy/M]=p(y)\mathbb{E}_{Y^M}[c_y/M] = p(y) gives the ε\varepsilon-local DP guarantee:

e−εp(y)≤Pr⁡[Γ(k;p)=y∣k]≤eεp(y).e^{-\varepsilon}p(y) \le\Pr[\Gamma(k;p)=y \mid k] \le e^{\varepsilon}p(y).

Proof of Fact 1

Proof. Fix any key kk. In each round of the rejection sampling procedure, the probability of accepting a completion YY is

a:=1⋅Pr⁡[hk(Y)=G]+e−εPr⁡[hk(Y)=R].a := 1 \cdot\Pr[h_k(Y)=G] + e^{-\varepsilon}\Pr[h_k(Y)=R].

Since the YY’s are sampled independently from the base model across all MM rounds, the acceptance indicators are independent Ber⁡(a)\operatorname{Ber}(a) random variables. Let XX be the number of rounds until acceptance, so X∼Geometric⁡(a)X \sim\operatorname{Geometric}(a). The sample count needed by the rejection sampler is thus T=min⁡(M,X)T = \min(M,X), with E[T]≤E[X]=1a\mathbb{E}[T] \le\mathbb{E}[X] = \frac{1}{a}.

Proof of Proposition 2

Proof. Fix any prompt and key, and suppress their dependence in the notation. Let pp denote the base model distribution given the prompt. For a candidate Y∼pY \sim p, let acc⁡\operatorname{acc} be the event that it gets accepted by the rejection sampler. Since Pr⁡[acc⁡∣Y=y]∈{e−ε,1}\Pr[\operatorname{acc} \mid Y=y] \in\{e^{-\varepsilon},1\}, we also have Pr⁡[acc⁡]∈[e−ε,1]\Pr[\operatorname{acc}] \in[e^{-\varepsilon},1]. Thus, by Bayes’ rule, the distribution of the accepted candidate satisfies, for p(y)>0p(y)>0,

q(y):=Pr⁡[Y=y∣acc⁡]=p(y)Pr⁡[acc⁡∣Y=y]Pr⁡[acc⁡]∈[e−εp(y),eεp(y)].\begin{aligned} q(y) &:= \Pr[Y=y \mid\operatorname{acc}] \\ &= p(y)\frac{\Pr[\operatorname{acc} \mid Y=y]}{\Pr[\operatorname{acc}]} \\ &\in[e^{-\varepsilon}p(y),e^{\varepsilon}p(y)]. \end{aligned}

The same bounds hold when p(y)=0p(y)=0, since q(y)=0q(y)=0 in that case.

The finite candidate budget MM only moves the watermarked output distribution toward the base pp. If round MM is reached, its fresh candidate has distribution identical to the base pp and is returned by the rejection sampler regardless of color. Writing rr as the probability of reaching the final round, the watermarked distribution is therefore

qM(y)=(1−r)q(y)+rp(y),r∈[0,1].q_M(y)=(1-r)q(y)+rp(y), \qquad r \in[0,1].

This mixture only moves each likelihood ratio toward 11, so

e−εp(y)≤qM(y)≤eεp(y)∀y∈Y.e^{-\varepsilon}p(y) \le q_M(y) \le e^{\varepsilon}p(y) \qquad\forall y \in\mathcal{Y}.

Proof of Fact 2

Proof. For the parallel sampler, the empirical green fraction PGP_G in Algorithm 1 converges almost surely to gg by the strong law of large numbers. Conditional on the candidates and PGP_G, the output is green with probability f(PG)=min⁡{eϵPG,1−e−ϵ(1−PG)}f(P_G)=\min\{e^{\epsilon}P_G,1-e^{-\epsilon}(1-P_G)\}. Since ff is continuous and bounded, qparM=E[f(PG)]→f(g)q_{\mathrm{par}}^{M}=\mathbb{E}[f(P_G)]\to f(g) by the bounded convergence theorem.

For the rejection sampler, the probability of accepting a completion on each attempt before the final one is a=g+e−ϵ(1−g)a=g+e^{-\epsilon}(1-g). Since each attempt is independent, the cumulative green probability is

qrejM=∑t=1M(1−a)t−1g→ga=eϵgeϵg+1−g.q_{\mathrm{rej}}^{M}=\sum_{t=1}^{M}(1-a)^{t-1}g\to\frac{g}{a}=\frac{e^{\epsilon}g}{e^{\epsilon}g+1-g}.

Estimation proofs

Proof of Lemma 1

Proof. Use the shorthand Zy=1{hk(y)=G}Z_y=\mathbf{1}\{h_k(y)=G\}. Under Assumption 1, the ZyZ_y's are independent Ber⁡(π0)\operatorname{Ber}(\pi_0) random variables. Since gi(k)=∑y∈Ypi(y)Zyg_i(k)=\sum_{y\in\mathcal{Y}}p_i(y)Z_y, we have

Ek[gi(k)]=∑y∈Ypi(y)Ek[Zy]=π0.\mathbb{E}_k[g_i(k)]=\sum_{y\in\mathcal{Y}}p_i(y)\mathbb{E}_k[Z_y]=\pi_0.

Furthermore, independence gives

Cov⁡k[gi(k),gj(k)]=∑y,y′∈Ypi(y)pj(y′)Cov⁡k[Zy,Zy′]=π0(1−π0)∑y∈Ypi(y)pj(y)=π0(1−π0)⟨pi,pj⟩.\begin{aligned} \operatorname{Cov}_k[g_i(k),g_j(k)] &=\sum_{y,y'\in\mathcal{Y}}p_i(y)p_j(y')\operatorname{Cov}_k[Z_y,Z_{y'}]\\ &=\pi_0(1-\pi_0)\sum_{y\in\mathcal{Y}}p_i(y)p_j(y)\\ &=\pi_0(1-\pi_0)\langle p_i,p_j\rangle. \end{aligned}

Proof of Proposition 3

Proof. With the unclipped moment estimator λ~=H‾−π0π1−π0\widetilde{\lambda}=\frac{\overline{H}-\pi_0}{\pi_1-\pi_0}, we have the decomposition

λ~−λ=1π1−π0[1n∑i=1n(Hi−E[Hi∣k])+1n∑i∈I1(qi−π1)+1n∑i∈I0(gi−π0)].\widetilde{\lambda}-\lambda =\frac{1}{\pi_1-\pi_0}\left[\frac{1}{n}\sum_{i=1}^{n}(H_i-\mathbb{E}[H_i\mid k])+\frac{1}{n}\sum_{i\in I_1}(q_i-\pi_1)+\frac{1}{n}\sum_{i\in I_0}(g_i-\pi_0)\right].

Denote V(k):=1n∑i=1n(Hi−E[Hi∣k])V(k):=\frac{1}{n}\sum_{i=1}^{n}(H_i-\mathbb{E}[H_i\mid k]). Then

λ~−λ=1π1−π0[V(k)+λB(k)+(1−λ)U(k)].\widetilde{\lambda}-\lambda=\frac{1}{\pi_1-\pi_0}\left[V(k)+\lambda B(k)+(1-\lambda)U(k)\right].

Note that B(k)B(k) and U(k)U(k) are fixed given kk. The only random quantity is V(k)V(k), the sampling noise, with

E[V(k)∣k]=0.\mathbb{E}[V(k)\mid k]=0.

Then, the conditional MSE is

E[(λ~−λ)2∣k]=1(π1−π0)2[E[V(k)2∣k]+(λB(k)+(1−λ)U(k))2].\mathbb{E}[(\tilde{\lambda}-\lambda)^2 \mid k] = \frac{1}{(\pi_1-\pi_0)^2}\left[\mathbb{E}[V(k)^2 \mid k] + \left(\lambda B(k) + (1-\lambda)U(k)\right)^2\right].

By conditional independence, we have

E[V(k)2∣k]=Var⁡[V(k)∣k]=Var⁡[1n∑i=1nHi∣k]=1n2∑i=1nVar⁡[Hi∣k]=1n2(∑i∈I1qi(1−qi)+∑i∈I0gi(1−gi))≤14n.\begin{aligned} \mathbb{E}[V(k)^2 \mid k] &= \operatorname{Var}[V(k) \mid k] \\ &= \operatorname{Var}\left[\frac{1}{n}\sum_{i=1}^{n} H_i \mid k\right] \\ &= \frac{1}{n^2}\sum_{i=1}^{n}\operatorname{Var}[H_i \mid k] \\ &= \frac{1}{n^2}\left(\sum_{i\in I_1}q_i(1-q_i)+\sum_{i\in I_0}g_i(1-g_i)\right) \\ &\le\frac{1}{4n}. \end{aligned}

Since projection onto [0,1][0,1] can only decrease the MSE, combining the above we have

E[(λ^−λ)2∣k]≤1(π1−π0)2[14n+(λB(k)+(1−λ)U(k))2].\mathbb{E}[(\hat{\lambda}-\lambda)^2 \mid k] \le\frac{1}{(\pi_1-\pi_0)^2}\left[\frac{1}{4n}+\left(\lambda B(k)+(1-\lambda)U(k)\right)^2\right].

Lemma: Variance of B(k)B(k)

Lemma 3 (Variance of B(k)B(k)). Consider both samplers in the limit M→∞M\to\infty. Let m=∣I1∣>0m=|I_1|>0. Under Assumption 1, we have

Var⁡k[B(k)]≤e2επ0(1−π0)m2(∑i∈I1∥pi∥22+∑i,j∈I1i≠j⟨pi,pj⟩).\operatorname{Var}_k[B(k)] \le\frac{e^{2\varepsilon}\pi_0(1-\pi_0)}{m^2}\left(\sum_{i\in I_1}\lVert p_i\rVert_2^2+\sum_{\substack{i,j\in I_1\\i\ne j}}\langle p_i,p_j\rangle\right).

Proof. For either sampler, write qi(k)=f(gi(k))q_i(k)=f(g_i(k)), where

f(x)={eεxeεx+1−x,for the rejection sampler,min⁡{eεx,1−e−ε(1−x)},for the parallel sampler.f(x)= \begin{cases} \dfrac{e^\varepsilon x}{e^\varepsilon x+1-x}, & \text{for the rejection sampler},\\ \min\{e^\varepsilon x,1-e^{-\varepsilon}(1-x)\}, & \text{for the parallel sampler}. \end{cases}

Both maps are eεe^\varepsilon-Lipschitz on [0,1][0,1]. For the rejection sampler, this follows from

0≤f′(x)=eε(1+(eε−1)x)2≤eε.0\le f'(x)=\frac{e^\varepsilon}{(1+(e^\varepsilon-1)x)^2}\le e^\varepsilon.

For the parallel sampler, ff is continuous and piecewise linear with slopes eεe^\varepsilon and e−εe^{-\varepsilon}.

Write Zy=1{hk(y)=G}Z_y=\mathbf{1}\{h_k(y)=G\}, so that gi(k)=∑y∈Ypi(y)Zyg_i(k)=\sum_{y\in\mathcal{Y}}p_i(y)Z_y, and B(k)B(k) is a function of ZyZ_y:

B(k)=1m∑i∈I1f(∑y∈Ypi(y)Zy)−f(π0).B(k)=\frac{1}{m}\sum_{i\in I_1}f\left(\sum_{y\in\mathcal{Y}}p_i(y)Z_y\right)-f(\pi_0).

Under Assumption 11, the ZyZ_y are independent Ber⁡(π0)\operatorname{Ber}(\pi_0) variables. Suppose B(k)′B(k)' is the variable obtained by replacing ZyZ_y by an i.i.d. copy Zy′Z'_y. By the Lipschitz bounds, this changes B(k)B(k) by at most cy:=eεm∑i∈I1pi(y)c_y := \frac{e^\varepsilon}{m}\sum_{i\in I_1} p_i(y), i.e. ∣B(k)−B(k)′∣≤cy\lvert B(k)-B(k)'\rvert\le c_y.

Note that this change is only nonzero if Zy≠Zy′Z_y \ne Z'_y, and since they are independent Ber⁡(π0)\operatorname{Ber}(\pi_0) variables, this event has probability 2π0(1−π0)2\pi_0(1-\pi_0). Therefore, by the Efron-Stein inequality [4], we have

Var⁡k[B(k)]≤12∑y∈YEk[∣B(k)−B(k)′∣2]≤12∑y2π0(1−π0)cy2=e2επ0(1−π0)m2∑i,j∈I1⟨pi,pj⟩.\begin{aligned} \operatorname{Var}_k[B(k)] &\le\frac{1}{2}\sum_{y\in\mathcal{Y}}\mathbb{E}_k\left[\lvert B(k)-B(k)'\rvert^2\right] \\ &\le\frac{1}{2}\sum_y 2\pi_0(1-\pi_0)c_y^2 \\ &= \frac{e^{2\varepsilon}\pi_0(1-\pi_0)}{m^2}\sum_{i,j\in I_1}\langle p_i,p_j\rangle. \end{aligned}

Proof of Proposition 4

Proof. Taking expectation over the key kk in equation (10), we can decompose the error to

E[(λ~−λ)2]=1d2E[V(k)2]+λ2d2Ek[B(k)2]+(1−λ)2d2Ek[U(k)2]+2λ(1−λ)d2Ek[B(k)U(k)].(12)\mathbb{E}\left[(\tilde{\lambda}-\lambda)^2\right] = \frac{1}{d^2}\mathbb{E}[V(k)^2] + \frac{\lambda^2}{d^2}\mathbb{E}_k[B(k)^2] + \frac{(1-\lambda)^2}{d^2}\mathbb{E}_k[U(k)^2] + \frac{2\lambda(1-\lambda)}{d^2}\mathbb{E}_k[B(k)U(k)]. \tag*{(12)}

We bound the last three terms of the equation above. Since Ek[U(k)]=0\mathbb{E}_k[U(k)] = 0, we have

Ek[U(k)2]=Var⁡k[U(k)]=π0(1−π0)∥pˉ0∥22.\mathbb{E}_k[U(k)^2] = \operatorname{Var}_k[U(k)] = \pi_0(1-\pi_0)\lVert\bar{p}_0\rVert_2^2.

Then, we bound the cross term using Cauchy-Schwarz:

Ek[B(k)U(k)]≤∣Ek[B(k)U(k)]∣≤Ek[B(k)2]Ek[U(k)2]=Ek[B(k)2]π0(1−π0)∥pˉ0∥2≤π0(1−π0)∥pˉ0∥2.\begin{aligned} \mathbb{E}_k[B(k)U(k)] &\le\lvert\mathbb{E}_k[B(k)U(k)]\rvert\\ &\le\sqrt{\mathbb{E}_k[B(k)^2]}\sqrt{\mathbb{E}_k[U(k)^2]} \\ &= \sqrt{\mathbb{E}_k[B(k)^2]}\sqrt{\pi_0(1-\pi_0)}\lVert\bar{p}_0\rVert_2 \\ &\le\sqrt{\pi_0(1-\pi_0)}\lVert\bar{p}_0\rVert_2. \end{aligned}

Finally, we bound Var⁡k[B(k)]\operatorname{Var}_k[B(k)] using Lemma 33:

Ek[B(k)2]=Var⁡k[B(k)]+(Ek[B(k)])2≤e2επ0(1−π0)∥pˉ1∥22+(Ek[B(k)])2.\mathbb{E}_k[B(k)^2] = \operatorname{Var}_k[B(k)] + \left(\mathbb{E}_k[B(k)]\right)^2 \le e^{2\varepsilon}\pi_0(1-\pi_0)\lVert\bar{p}_1\rVert_2^2 + \left(\mathbb{E}_k[B(k)]\right)^2.

Substituting the above into equation (12) gives the desired inequality with remainder RR. Every term of RR is proportional to ∥pˉ0∥2\lVert\bar{p}_0\rVert_2, ∥pˉ0∥22\lVert\bar{p}_0\rVert_2^2 or ∥pˉ1∥22\lVert\bar{p}_1\rVert_2^2, so R→0R\to0 under the assumption.

Proof of Proposition 5

Proof. Write m=∣I1∣m=\lvert I_1\rvert and without loss of generality, suppose m>0m>0. We consider both samplers.

Rejection Sampler. Consider the rejection sampler in the limit M→∞M\to\infty, so that qi(k)=f(gi(k))q_i(k)=f(g_i(k)), where

f(x)=eεxeεx+1−x.f(x)=\frac{e^\varepsilon x}{e^\varepsilon x+1-x}.

Then, for any x,y∈[0,1]x,y \in[0,1], we have

f(x)−f(y)=eε(x−y)(1+(eε−1)x)(1+(eε−1)y).f(x)-f(y)=\frac{e^{\varepsilon}(x-y)}{(1+(e^{\varepsilon}-1)x)(1+(e^{\varepsilon}-1)y)}.

We use the shorthand Zy=1{hk(y)=G}Z_y=\mathbb{1}\{h_k(y)=G\}, which implies gi=∑y∈Ypi(y)Zyg_i=\sum_{y\in\mathcal{Y}}p_i(y)Z_y. Then, the unnormalized bias is

Ek[f(gi)−f(π0)]=Ek[eε(gi−π0)(1+(eε−1)gi)(1+(eε−1)π0)]=eε1+(eε−1)π0∑y∈Ypi(y)E[Zy−π01+(eε−1)gi].\begin{aligned} \mathbb{E}_k[f(g_i)-f(\pi_0)]=\mathbb{E}_k\left[\frac{e^{\varepsilon}(g_i-\pi_0)}{(1+(e^{\varepsilon}-1)g_i)(1+(e^{\varepsilon}-1)\pi_0)}\right] \\ &=\frac{e^{\varepsilon}}{1+(e^{\varepsilon}-1)\pi_0}\sum_{y\in\mathcal{Y}}p_i(y)\mathbb{E}\left[\frac{Z_y-\pi_0}{1+(e^{\varepsilon}-1)g_i}\right]. \end{aligned}

Since both the numerator and the denominator in the integrand depend on ZyZ_y, which is a Bernoulli random variable with mean π0\pi_0, we use the leave-one-out trick to tease out the dependence of the whole expectation on π0\pi_0.

Denote gi−y=∑y′≠ypi(y′)Zy′g_i^{-y}=\sum_{y'\ne y}p_i(y')Z_{y'}. Then, gi=gi−y+pi(y)Zyg_i=g_i^{-y}+p_i(y)Z_y. Note that conditional on gi−yg_i^{-y}, Zy∼Ber⁡(π0)Z_y\sim\operatorname{Ber}(\pi_0). Then,

Ek[Zy−π01+(eε−1)gi]=E[E[Zy−π01+(eε−1)(gi−y+pi(y)Zy)∣gi−y]]=E[π01−π01+(eε−1)(gi−y+pi(y))+(1−π0)−π01+(eε−1)gi−y]=−π0(1−π0)(eε−1)pi(y)Ek[ϕ(gi−y)],\begin{aligned} \mathbb{E}_k\left[\frac{Z_y-\pi_0}{1+(e^{\varepsilon}-1)g_i}\right] =\mathbb{E}\left[\mathbb{E}\left[\left.\frac{Z_y-\pi_0}{1+(e^{\varepsilon}-1)(g_i^{-y}+p_i(y)Z_y)}\right|g_i^{-y}\right]\right] \\ &=\mathbb{E}\left[\pi_0\frac{1-\pi_0}{1+(e^{\varepsilon}-1)(g_i^{-y}+p_i(y))}+(1-\pi_0)\frac{-\pi_0}{1+(e^{\varepsilon}-1)g_i^{-y}}\right] \\ &=-\pi_0(1-\pi_0)(e^{\varepsilon}-1)p_i(y)\mathbb{E}_k\left[\phi(g_i^{-y})\right], \end{aligned}

where

ϕ(gi−y)=1(1+(eε−1)(gi−y+pi(y)))(1+(eε−1)gi−y).\phi(g_i^{-y})=\frac{1}{(1+(e^{\varepsilon}-1)(g_i^{-y}+p_i(y)))(1+(e^{\varepsilon}-1)g_i^{-y})}.

Consolidating, the magnitude of the normalized bias is

Ek[−B(k)]f(π0)−π0=−1f(π0)−π01m∑i∈I1Ek[f(gi)−f(π0)]=π0(1−π0)eε(eε−1)m(f(π0)−π0)(1+(eε−1)π0)∑i∈I1∑y∈Ypi(y)2Ek[ϕ(gi−y)]=eεm∑i∈I1∑y∈Ypi(y)2Ek[ϕ(gi−y)].\begin{aligned} \frac{\mathbb{E}_k[-B(k)]}{f(\pi_0)-\pi_0} =-\frac{1}{f(\pi_0)-\pi_0}\frac{1}{m}\sum_{i\in I_1}\mathbb{E}_k[f(g_i)-f(\pi_0)] \\ &=\frac{\pi_0(1-\pi_0)e^{\varepsilon}(e^{\varepsilon}-1)}{m(f(\pi_0)-\pi_0)(1+(e^{\varepsilon}-1)\pi_0)} \sum_{i\in I_1}\sum_{y\in\mathcal{Y}}p_i(y)^2\mathbb{E}_k\left[\phi(g_i^{-y})\right] \\ &=\frac{e^{\varepsilon}}{m}\sum_{i\in I_1}\sum_{y\in\mathcal{Y}}p_i(y)^2\mathbb{E}_k\left[\phi(g_i^{-y})\right]. \end{aligned}

Note that ϕ\phi is nonincreasing. Also gi−y=∑y′≠ypi(y′)Zy′g_i^{-y}=\sum_{y'\ne y}p_i(y')Z_{y'}, where each Zy′∼i.i.d.Ber⁡(π0)Z_{y'}\overset{\mathrm{i.i.d.}}{\sim}\operatorname{Ber}(\pi_0). Since a Ber⁡(π0′)\operatorname{Ber}(\pi_0') variable stochastically dominates a Ber⁡(π0)\operatorname{Ber}(\pi_0) variable for π0′≥π0\pi_0'\ge\pi_0, by Corollaries 4.2.7 and 4.2.6 of Roch [38] we have that Ek[ϕ(gi−y)]\mathbb{E}_k[\phi(g_i^{-y})] is nonincreasing in π0\pi_0. Overall, since the multipliers eε/me^{\varepsilon}/m and pi(y)2p_i(y)^2 are nonnegative, the magnitude of the normalized bias Ek[−B(k)]f(π0)−π0\frac{\mathbb{E}_k[-B(k)]}{f(\pi_0)-\pi_0} is nonincreasing in π0\pi_0.

Parallel Sampler. Consider the parallel sampler in the limit M→∞M\to\infty, so that qi(k)=f(gi(k))q_i(k)=f(g_i(k)), where

f(x)=min⁡{eεx, 1−e−ε(1−x)}.f(x)=\min\{e^{\varepsilon}x,\ 1-e^{-\varepsilon}(1-x)\}.

Similar to the rejection sampler proof, we use the shorthand Zy=1{hk(y)=G}Z_y = \mathbb{1}\{h_k(y) = G\}, which implies gi=∑y∈Ypi(y)Zyg_i = \sum_{y\in\mathcal{Y}} p_i(y)Z_y. Under the ideal coloring assumption, the ZyZ_y are independent Ber⁡(π0)\operatorname{Ber}(\pi_0) variables, with Ek[gi]=π0\mathbb{E}_k[g_i] = \pi_0.

Let τ=(1+eε)−1\tau= (1 + e^\varepsilon)^{-1}. Note that ff is a piecewise linear function, which can be rewritten as

f(x)=1−e−ε(1−x)−(eε−e−ε)(τ−x)+(13)f(x) = 1 - e^{-\varepsilon}(1-x) - (e^\varepsilon- e^{-\varepsilon})(\tau-x)_+ \tag*{(13)}

We consider π0∈[τ,1)\pi_0 \in[\tau,1). Using the identity in equation (13), we can write the unnormalized bias as

Ek[f(gi)−f(π0)]=Ek[e−ε(gi−π0)−(eε−e−ε)(τ−gi)+]=−(eε−e−ε)Ek[(τ−gi)+].\begin{aligned} \mathbb{E}_k[f(g_i)-f(\pi_0)] &= \mathbb{E}_k\left[e^{-\varepsilon}(g_i-\pi_0) - (e^\varepsilon-e^{-\varepsilon})(\tau-g_i)_+\right] \\ &= -(e^\varepsilon-e^{-\varepsilon})\mathbb{E}_k[(\tau-g_i)_+]. \end{aligned}

To isolate the dependence on π0\pi_0, define the nonincreasing function

ψ(x)={τ−x1−x,0≤x<τ,0,τ≤x≤1.\psi(x) = \begin{cases} \frac{\tau-x}{1-x}, & 0 \le x < \tau, \\ 0, & \tau\le x \le1. \end{cases}

Then (τ−gi)+=(1−gi)ψ(gi)(\tau-g_i)_+ = (1-g_i)\psi(g_i), so

Ek[(τ−gi)+]=Ek[(1−gi)ψ(gi)]=∑y∈Ypi(y)Ek[(1−Zy)ψ(gi)].\begin{aligned} \mathbb{E}_k[(\tau-g_i)_+] &= \mathbb{E}_k[(1-g_i)\psi(g_i)] \\ &= \sum_{y\in\mathcal{Y}} p_i(y)\mathbb{E}_k[(1-Z_y)\psi(g_i)]. \end{aligned}

The interchange of expectation and summation is valid because all summands are nonnegative.

Since both factors in the integrand depend on ZyZ_y, we use the leave-one-out trick to isolate this dependence. Denote gi−y=∑y′≠ypi(y′)Zy′g_i^{-y} = \sum_{y'\ne y}p_i(y')Z_{y'}. Then gi=gi−y+pi(y)Zyg_i = g_i^{-y} + p_i(y)Z_y, and conditional on gi−yg_i^{-y}, Zy∼Ber⁡(π0)Z_y \sim\operatorname{Ber}(\pi_0). Therefore,

Ek[(1−Zy)ψ(gi)]=Ek[Ek[(1−Zy)ψ(gi−y+pi(y)Zy)∣gi−y]]=(1−π0)Ek[ψ(gi−y)].\begin{aligned} \mathbb{E}_k[(1-Z_y)\psi(g_i)] &= \mathbb{E}_k\left[\mathbb{E}_k\left[(1-Z_y)\psi(g_i^{-y}+p_i(y)Z_y)\mid g_i^{-y}\right]\right] \\ &= (1-\pi_0)\mathbb{E}_k[\psi(g_i^{-y})]. \end{aligned}

Consolidating, the magnitude of the normalized bias is

Ek[−B(k)]f(π0)−π0=−1m(f(π0)−π0)∑i∈I1Ek[f(gi)−f(π0)]=(eε−e−ε)(1−π0)m(f(π0)−π0)∑i∈I1∑y∈Ypi(y)Ek[ψ(gi−y)]=1+eεm∑i∈I1∑y∈Ypi(y)Ek[ψ(gi−y)],\begin{aligned} \frac{\mathbb{E}_k[-B(k)]}{f(\pi_0)-\pi_0} &= -\frac{1}{m(f(\pi_0)-\pi_0)}\sum_{i\in I_1}\mathbb{E}_k[f(g_i)-f(\pi_0)] \\ &= \frac{(e^\varepsilon-e^{-\varepsilon})(1-\pi_0)}{m(f(\pi_0)-\pi_0)} \sum_{i\in I_1}\sum_{y\in\mathcal{Y}}p_i(y)\mathbb{E}_k[\psi(g_i^{-y})] \\ &= \frac{1+e^\varepsilon}{m}\sum_{i\in I_1}\sum_{y\in\mathcal{Y}}p_i(y)\mathbb{E}_k[\psi(g_i^{-y})], \end{aligned}

where the last equality comes from the fact that f(π0)−π0=(1−e−ε)(1−π0)f(\pi_0)-\pi_0 = (1-e^{-\varepsilon})(1-\pi_0).

Note that ψ\psi is nonincreasing. By the same argument as the rejection sampler case, we have that Ek[ψ(gi−y)]\mathbb{E}_k[\psi(g_i^{-y})] is nonincreasing in π0\pi_0 and thus Ek[−B(k)]f(π0)−π0\frac{\mathbb{E}_k[-B(k)]}{f(\pi_0)-\pi_0} is nonincreasing in π0\pi_0.

Ablations

We conduct ablations on the C4 task described in § 7.1. Unless varied, we use rejection sampling with ε=2\varepsilon= 2, n=2000n = 2000, π0=0.5\pi_0 = 0.5, a candidate cap of M=20M = 20, and temperature 1. Error plots report mean absolute percentage error (MAPE), obtained by averaging 100∣λ^−λ∣/λ100|\hat{\lambda} - \lambda|/\lambda over repeated estimates with 20 randomly sampled keys, where λ^\hat{\lambda} is the clipped estimator in equation (9).

Effect of ε\varepsilon and nn

We compare the performance of our watermark estimator on C4 data with the clipped RR moment estimator (equation (4) with clipping onto [0,1][0,1]) under an ideal randomized response experiment described as follows. For each mixture sample size nn and prevalence λ\lambda, we fix m=nλm = n\lambda watermarked examples and draw independent noisy reports R1∼Binomial⁡(m,σ(ε))R_1 \sim\operatorname{Binomial}(m, \sigma(\varepsilon)) and R0∼Binomial⁡(n−m,0.5)R_0 \sim\operatorname{Binomial}(n-m, 0.5). We compute R=R1+R0R = R_1 + R_0, estimate prevalence using λ^RR=proj⁡[0,1]((R/n−0.5)/(σ(ε)−0.5))\hat{\lambda}_{\mathrm{RR}} = \operatorname{proj}_{[0,1]}((R/n - 0.5)/(\sigma(\varepsilon) - 0.5)), and compute MAPE over 1,000 simulations per condition. This RR benchmark matches the nominal green probabilities of RGS rejection sampling at π0=0.5\pi_0 = 0.5 in the limit of high entropy and infinite candidate budget.

Figure 5 plots MAPE as a function of ε\varepsilon at a fixed n=2000n = 2000. We observe that the errors decrease with increasing ε\varepsilon, consistent with the looser privacy requirements. Figure 6 plots MAPE as a function of sample size nn at a fixed ε=2\varepsilon= 2, which shows strong scaling. Across both figures we see that in this high-entropy C4 task, the RGS watermark behaves very similarly to the moment estimator in an ideal randomized response mechanism.

MAPE versus privacy budget for three prevalence values

Figure 5. MAPE versus privacy budget ε\varepsilon, with the ideal RR benchmark dashed. Left to right: λ=0.1,0.5,0.9\lambda= 0.1, 0.5, 0.9.

Effect of temperature and generation length

Higher temperature and longer generation lengths both increase the entropy of the text distribution. Figure 7 varies both temperature and the number of generated prefix tokens TT used for hashing and selection for Llama-3.1-8B-Instruct. Increasing temperature substantially reduces error for short prefixes, while longer prefixes attain lower error even at low temperatures. These trends agree with the theoretical intuition that higher entropy leads to lower error.

MAPE versus temperature for Llama-3.1-8B-Instruct with prefix lengths $T \in \{5, 10, 20, 50\}$

Figure 7. MAPE versus temperature for Llama-3.1-8B-Instruct with prefix lengths T∈{5,10,20,50}T \in\{5, 10, 20, 50\}. Left to right: λ=0.1,0.5,0.9\lambda= 0.1, 0.5, 0.9.

MAPE versus mixture size $n$ for $\lambda = 0.1, 0.5, 0.9$

Figure 6. MAPE versus mixture size nn, with the ideal RR benchmark dashed. Left to right: λ=0.1,0.5,0.9\lambda= 0.1, 0.5, 0.9.

Parallel versus rejection sampling

Figure 8 evaluates the parallel sampler in Algorithm 1 using the same C4 setup as Figure 1. Mean estimates remain close to the true prevalence across all four models, and the percentile bands narrow as ε\varepsilon increases. Compared with the rejection sampler, the parallel sampler has narrower bands, most visible at ε=1\varepsilon= 1. This is consistent with its larger nominal green probability as described in § 4.1.

RGS parallel-sampling prevalence estimates on C4

Figure 8. RGS parallel-sampling prevalence estimates on C4. Left to right: ε=1,2,3\varepsilon= 1, 2, 3. Markers show means and shading shows 5th–95th percentiles over keys and repetitions.

Effect of candidate budget

Figure 9 and Figure 10 show that both samplers benefit substantially from increasing the candidate budget from M=2M = 2 to M=8M = 8, with little further improvement at M=20M = 20 or 32. A small budget limits the desired probability of returning a green sequence, as the rejection sampler may reach the cap before encountering a green sequence, and the parallel sampler may have too few green candidates to realize the nominal separation. As a result, a very small MM will introduce downward bias.

Effect of prompt diversity

We fix the mixture sample size at n=500n = 500 and vary the number of distinct C4 prompts in the mixture over {1,5,10,20,50,100}\{1, 5, 10, 20, 50, 100\}, allocating an equal number of responses to each prompt. We use Qwen3-4B at temperature 1 with T=20T = 20, rejection RGS with ε=2\varepsilon= 2, π0=0.5\pi_0 = 0.5, and M=20M = 20. Figure 11 shows that increasing prompt diversity consistently reduces estimation error when the total sample size is fixed, consistent with theoretical findings in § 6.

MAPE versus prompt count for Qwen3-4B

Figure 11. MAPE versus prompt count for Qwen3-4B, with n=500n = 500 and T=20T = 20. Left to right: λ=0.1,0.5,0.9\lambda= 0.1, 0.5, 0.9.

Examples of RGS-watermarked text

Setting. We present example responses generated by the RGS watermark for five C4 prompts with Llama-3.1-8B-Instruct. We use the rejection sampler with ϵ=2\epsilon= 2, π0=0.5\pi_0 = 0.5, M=20M = 20 and temperature 1. Each prompt is supplied as raw text without a chat template. The four completions presented for each prompt share the same key, with a different key used for each prompt. We display only the first 50 tokens of the completions.

C4 prompts with four RGS-selected completions each
Prompt 0. Cluster comprises IBM’s Opteron-based eServer 325 server and systems management software and storage devices that can run Linux and Windows operating systems
1. . IBM has introduced a high-performance computing cluster, called eServer Cluster 1600, which includes the Linux operating system and the Viuke dual-core processor, a x86 chip from Sun Microsystems technology provider: Advanced Micro Devices (AMD). In this
2. . IBM’s "open" cluster, which comprises the eServer 325 (beta), IBM Systems Director software, and several storage subsystems, is generating interest among customers wanting a high-performance computing setup that accommodates a mix of operating systems, including
3. . Oracle has announced Oracle9i Release 2 Standard Edition, which includes a standard edition of Oracle9i Database Server, Oracle9i Application Server, Oracle Portal and Applications. Release 2 adds improved high availability, the ability to integrate business processes
4. . IBM is pushing the M@L cluster high-end servers into swift and fast implementation paths, highlighting Linux and Windows combinations. The recommendation is for IBM eServer cluster to ease and accelerate Highly-Scalable and optimized cluster solutions for employment by businesses
Prompt 1. Belying expectations, Prasar Bharti has earned only Rs 58.19 crore (Rs 581.9 million) as revenue during the
1. 2006-07 financial year. The figure is significantly lower than the Rs 750 crore (Rs 7.5 billion) expected by the organisation as an immediate step towards achieving its annual targets. The shortfall as estimated appears to be mainly due
2. first quarter of FY2023-24, till September 30th, which is just 38% of the total collection of Rs147.120 crore (Rs 1.4712 billion), projected for the entire year. The numbers were shared
3. current fiscal as against the budgeted estimate of Rs 1,061 crore (Rs 10.61 billion). According to the Prasar Bharti’s Annual Report 2010-11, the public sector undertaking (PSU) has failed to
4. April-June quarter, less than Rs 172 crore (Rs 1.72 billion) in the same period during the previous year. According to the revenue figures released by the ministry of information and broadcasting, the significant drop in revenue is partly due
Prompt 2. Marketers are employed in the public sector as well as the private sector. Most people think of marketing as a strictly private sector activity, but
1. in reality, many public sector jobs also involve marketing. Marketing is the functional process for which teams are tasked with the planning, creation, and distribution of ideas, goods, services, and values to develop cohort, create Brand awareness, and to achieve [
2. public sector employees also market products and services. Additionally, many marketers work in non-profit organizations and professional associations. After obtaining employment, they may assume roles which help to bring their product or services to their customers, then, develop and execute marketing strategies aimed
3. many government services and public institutions employ marketing professionals to convey information to the public. Overall, there are a wide range of careers to be found in both public and private sectors. The common term "marketer" generally refers to any marketing professional. Other

Table 1.

  1. it is also a vital part in the public sector. While government and non-profit organisations may not have sales objectives in the same way as private companies, the need for customer awareness and a positive image translates to a need for effective marketing. In the public

Prompt 3. MIDDLETOWN, NJ - The Middletown Township Public Library and the Township of Middletown are pleased to announce the

  1. launch of "Park ...Then", an innovative new program that combines public fitness classes, environmental education, and relaxed social gatherings at several of the Township’s parks. The program patterned after the successful "Park Fit" program, will feature a series of

  1. launch of a "Fugitive" online public record search tool for the township. The new tool, which is available on the Township of Middletown Municipal Government website, allows users to search for fugitives based on name, race, sex

  1. celebration of their second year of progress in making Middletown a more inclusive and welcoming community. Over the past year, the Township has made a concerted effort to engage in planning and community outreach to identify goals and objectives for inclusion and diversity, with

  1. Middletown-Sayreville-Holmdel-Matawan community wide resource fair, taking place on September 21, from 10:00 a.m. to 2:00 p.m. at the Middletown Township

Prompt 4. An eagerly awaited report from the World Health Organization (WHO) states that processed meats such as bacon and sausages cause cancer, and red meat

  1. , such as beef, may be carcinogenic to humans. The report, from the WHO’s International Agency for Research on Cancer (IARC), recognizes that a clear link between processed meat consumption and cancer has been demonstrated as a causal link. A class

  1. increases cancer risk. Photo:Getty Australia’s biggest meal kit delivery service, Marley Spoon, says it is taking the World Health Organization’s recent cancer warnings on processed and red meat seriously. The WHO says that eating processed meat, such as bacon

  1. may also carry a cancer risk. A team of 22 experts from 10 countries conducted a review of more than 800 scientific studies on the relationship between diet and cancer. The report’s findings are as follows: –Consuming 50 grams of

  1. consumption is also linked to an increased risk of cancer. The WHO’s International Agency for Research on Cancer (IARC) classified processed meat as "carcinogenic to humans", group 1. This is the highest level of classification, assigned to substances

References

  1. [2]ANTHROPIC (2026). How claude’s text watermark works. https://www.anthropic.com/news/claude-text-watermark. Accessed: 2026-09-26.
  2. [3]BASSILY, R. and SMITH, A. (2015). Local, private, efficient protocols for succinct histograms. In Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing. STOC ’15, Association for Computing Machinery, New York, NY, USA. URL https://doi.org/10.1145/2746539.2746632
  3. [4]BOUCHERON, S., LUGOSI, G. and BOUSQUET, O. (2004). Concentration inequalities. In Advanced Lectures on Machine Learning: ML Summer Schools 2003, Canberra, Australia, February 2 - 14, 2003, Tübingen, Germany, August 4 - 16, 2003, Revised Lectures (O. Bousquet, U. von Luxburg and G. Rätsch, eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 208–240. URL https://doi.org/10.1007/978-3-540-28650-9_9
  4. [5]BRAND (2026). Spymarks, not watermarks. https://brand.io/article/spymarks/. Accessed: 2026-09-26.
  5. [6]BRICKNER-WOOD, B. (2026). The mark of the machine. URL https://www.newyorker.com/culture/infinite-scroll/the-mark-of-the-machine
  6. [7]BROWN, A. (2026). Does claude’s watermark solve the ai transparency problem? URL https://www.techtarget.com/news/Does-Claudes-watermark-solve-the-AI-transparency-problem/856999/
  7. [8]CHRIST, M. and GUNN, S. (2024). Pseudorandom Error-Correcting Codes. ArXiv:2402.09370 [cs.CR]. URL http://arxiv.org/abs/2402.09370
  8. [10]DATHATHRI, S., SEE, A., GHAISAS, S., HUANG, P.-S., MCADAM, R. E., WELBL, J., BACHANI, V., KASKASOLI, A., STANFORTH, R., MATEJOVICOVA, T., HAYES, J., YVES, N., MEREY, M. A., BROWN-COHEN, J., BUNEL, R., BALLE, B., TAYLAN. CEMGIL, AHMED, Z., STACPOOLE, K., SHUMAILOV, I., BAETU, C., GOWAL, S., HASSABIS, D. and KOHLI, P. (2024). Scalable watermarking for identifying large language model outputs. Nature 634 818 – 823. URL https://api.semanticscholar.org/CorpusID:273547059
  9. [11]DUCHI, J. C., JORDAN, M. I. and WAINWRIGHT, M. J. (2013b). Local privacy and statistical minimax rates. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science.
  10. [12]DWORK, C., MCSHERRY, F., NISSIM, K. and SMITH, A. D. (2006). Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography, Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006, Proceedings (S. Halevi and T. Rabin, eds.), vol. 3876 of Lecture Notes in Computer Science. Springer. URL https://doi.org/10.1007/11681878_14
  11. [13]DWORK, C. and ROTH, A. (2014). The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci. 9 211–407. URL https://doi.org/10.1561/0400000042
  12. [14]ERLINGSSON, Ú., PIHUR, V. and KOROLOVA, A. (2014). Rappor: Randomized aggregatable privacy-preserving ordinal response. In Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security. CCS ’14, Association for Computing Machinery, New York, NY, USA. URL https://doi.org/10.1145/2660267.2660348
  13. [15]GOLDREICH, O., GOLDWASSER, S. and MICALI, S. (1986). How to construct random functions. J. ACM 33 792–807. URL https://doi.org/10.1145/6490.6503
  14. [16]HAYNES, K. (2026). URL https://www.inc.com/kevin-haynes/anthropics-new-ai-watermark-sparks-backlash-from-claude-subscribers/91391704
  15. [17]HOU, A., ZHANG, J., HE, T., WANG, Y., CHUANG, Y.-S., WANG, H., SHEN, L., VAN DURME, B., KHASHABI, D. and TSVETKOV, Y. (2024). SemStamp: A semantic watermark with paraphrastic robustness for text generation. In Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers) (K. Duh, H. Gomez and S. Bethard, eds.). Association for Computational Linguistics, Mexico City, Mexico. URL https://aclanthology.org/2024.naacl-long.226/arxiv.org/abs/2310.03991
  16. [18]HU, Z., CHEN, L., WU, X., WU, Y., ZHANG, H. and HUANG, H. (2024). Unbiased watermark for large language models. In The Twelfth International Conference on Learning Representations. URL https://openreview.net/forum?id=uWVC5FVidcarxiv.org/abs/2310.10669
  17. [19]JAIN, N., HAN, K., GU, A., LI, W.-D., YAN, F., ZHANG, T., WANG, S., SOLAR-LEZAMA, A., SEN, K. and STOICA, I. (2024). Livecodebench: Holistic and contamination free evaluation of large language models for code. URL https://arxiv.org/abs/2403.07974
  18. [20]Kairouz, P., Oh, S. and Viswanath, P. (2014). Extremal mechanisms for local differential privacy. CoRR abs/1407.1338. URL http://arxiv.org/abs/1407.1338
  19. [21]Kairouz, P., Oh, S. and Viswanath, P. (2015). The composition theorem for differential privacy. In Proceedings of the 32nd International Conference on Machine Learning (F. Bach and D. Blei, eds.), vol. 37 of Proceedings of Machine Learning Research. PMLR, Lille, France. URL https://proceedings.mlr.press/v37/kairouz15.html
  20. [22]Kim, B. D., Zhang, W., Ruan, W., Varshney, L. R. and Alabi, D. (2026). Simplemark: Fast multi-bit text watermarking under f-divergence constraints. URL https://arxiv.org/abs/2610.05712
  21. [23]Kirchenbauer, J., Geiping, J., Wen, Y., Katz, J., Miers, I. and Goldstein, T. (2023). A watermark for large language models. In Proceedings of the 40th International Conference on Machine Learning (A. Krause, E. Brunskill, K. Cho, B. Engelhardt, S. Sabato and J. Scarlett, eds.), vol. 202 of Proceedings of Machine Learning Research. PMLR. URL https://proceedings.mlr.press/v202/kirchenbauer23a.htmlarxiv.org/abs/2301.10226
  22. [24]Kobak, D., González-Márquez, R., Ágnes Horvát, E. and Lause, J. (2025). Delving into llm-assisted writing in biomedical publications through excess vocabulary. Science Advances 11 eadt3813. URL https://www.science.org/doi/abs/10.1126/sciadv.adt3813DOI
  23. [25]Koike, R., Kaneko, M. and Okazaki, N. (2024). Outfox: Llm-generated essay detection through in-context learning with adversarially generated examples. URL https://arxiv.org/abs/2307.11729
  24. [26]Krishna, K., Song, Y., Karpinska, M., Wieting, J. and Iyyer, M. (2023). Paraphrasing evades detectors of ai-generated text, but retrieval is an effective defense. In Advances in Neural Information Processing Systems (A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt and S. Levine, eds.), vol. 36. Curran Associates, Inc. URL https://proceedings.neurips.cc/paper_files/paper/2023/file/575c450013d0e999e4b0ecf82bd1afaa4-Paper-Conference.pdfarxiv.org/abs/2303.13408
  25. [27]Kuditipudi, R., Thickstun, J., Hashimoto, T. and Liang, P. (2024). Robust distortion-free watermarks for language models. URL https://arxiv.org/abs/2307.15593
  26. [28]Lee, T., Hong, S., Ahn, J., Hong, I., Lee, H., Yun, S., Shin, J. and Kim, G. (2024). Who wrote this code? watermarking for code generation. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers) (L.-W. Ku, A. Martins and V. Srikumar, eds.). Association for Computational Linguistics, Bangkok, Thailand. URL https://aclanthology.org/2024.acl-long.268/
  27. [29]Lensvelt-Mulders, G., Hox, J., Heijden, P. G. and Maas, C. (2005). Meta-analysis of randomized response research: Thirty-five years of validation. Sociological Methods & Research 33 319–348.
  28. [33]Liang, W., Izzo, Z., Zhang, Y., Lepp, H., Cao, H., Zhao, X., Chen, L., Ye, H., Liu, S., Huang, Z., McFarland, D. A. and Zou, J. Y. (2026). Monitoring ai-modified content at scale: A case study on the impact of chatgpt on ai conference peer reviews. URL https://arxiv.org/abs/2403.07183
  29. [34]Liu, Y. and Bu, Y. (2024). Adaptive text watermark for large language models. URL https://arxiv.org/abs/2401.13927
  30. [35]Liu, Y., Zhao, X., Song, D., Wornell, G. W. and Bu, Y. (2026). Position: LLM watermarking should align stakeholders’ incentives for practical adoption. In Findings of the Association for Computational Linguistics: ACL 2026 (M. Liakata, V. P. Moreira, J. Zhang and D. Jurgens, eds.). Association for Computational Linguistics, San Diego, California, United States. URL https://aclanthology.org/2026.findings-acl.1290/
  31. [36]Pan, L., Liu, A., He, Z., Gao, Z., Zhao, X., Lu, Y., Zhou, B., Liu, S., Hu, X., Wen, L., King, I. and Yu, P. S. (2024). MarkLLM: An open-source toolkit for LLM watermarking. In Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing: System Demonstrations (D. I. Hernandez Farias, T. Hope and M. Li, eds.). Association for Computational Linguistics, Miami, Florida, USA. URL https://aclanthology.org/2024.emnlp-demo.7/arxiv.org/abs/2405.10051
  32. [37]Raffel, C., Shazeer, N., Roberts, A., Lee, K., Narang, S., Matena, M., Zhou, Y., Li, W. and Liu, P. J. (2019). Exploring the limits of transfer learning with a unified text-to-text transformer. CoRR abs/1910.10683. URL http://arxiv.org/abs/1910.10683
  33. [38]Roch, S. (2024). Modern Discrete Probability: An Essential Toolkit. Cambridge Series in Statistical and Probabilistic Mathematics, Cambridge University Press.
  34. [39]Saarinen, M.-J. and Aumasson, J.-P. (2015). The blake2 cryptographic hash and message authentication code (mac). RFC 7693, RFC Editor, USA.
  35. [40]Shumailov, I., Shumaylov, Z., Zhao, Y., Papernot, N., Anderson, R. and Gal, Y. (2024). Ai models collapse when trained on recursively generated data. Nature 631 755–759.DOI
  36. [41]SitePoint (2026). URL https://www.sitepoint.com/claude-steganographic-request-marking/
  37. [42]Spirlet, T. (2026). Claude users are canceling their subscriptions, citing anthropic’s new ai watermark. URL https://www.businessinsider.com/claude-users-cancel-subscriptions-citing-anthropic-new-ai-watermark-2026-8
  38. [43]Tourangeau, R. and Yan, T. (2007). Sensitive questions in surveys. Psychological Bulletin 133 859–883.pubmed.ncbi.nlm.nih.gov/17723033
  39. [44]WANG, T., BLOCKI, J., LI, N. and JHA, S. (2017). Locally differentially private protocols for frequency estimation. In 26th USENIX Security Symposium (USENIX Security 17). USENIX Association, Vancouver, BC. URL https://www.usenix.org/conference/usenixsecurity17/technical-sessions/presentation/wang-tianhao
  40. [45]WARNER, S. L. (1965). Randomized response: a survey technique for eliminating evasive answer bias. Journal of the American Statistical Association 60 309 63–6. URL https://api.semanticscholar.org/CorpusID:35435339pubmed.ncbi.nlm.nih.gov/12261830
  41. [46]WU, Y., HU, Z., GUO, J., ZHANG, H. and HUANG, H. (2024). A resilient and accessible distribution-preserving watermark for large language models. URL https://arxiv.org/abs/2310.07710
  42. [47]ZHANG, H., EDELMAN, B. L., FRANCATI, D., VENTURI, D., ATENIESE, G. and BARAK, B. (2025). Watermarks in the sand: Impossibility of strong watermarking for generative models. URL https://arxiv.org/abs/2311.04378
  43. [48]ZHAO, X., ANANTH, P., LI, L. and WANG, Y.-X. (2023). Provable robust watermarking for ai-generated text. URL https://arxiv.org/abs/2306.17439

Paper details

vlnc:W_vvxwu2z7
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents