acceptodds
Under review as a conference paper at ICLR 2027

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 quality-preserving 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 MSE with bias at a low 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 MSE with bias at .

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
watermarks, privacy, language models

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_QaSROpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper investigates how to constrain the source evidence provided by watermarks in individual texts while simultaneously estimating the proportion of watermarked text within a population. The authors propose a "Sequence-level Red-Green Watermark" (RGS), which injects signals via controlled reweighting or rejection sampling, and demonstrate that it satisfies local differential privacy (LDP) relative to the base model. Furthermore, the paper develops a method for proportion estimation, analyzes the interplay between fixed keys, generation diversity, and estimation error, and evaluates the approach’s feasibility across tasks involving C4 dataset continuation, essay writing, and code generation.

Critical strengths
  1. Valuable Problem Formulation. The paper shifts the focus of watermarking toward population-level proportion estimation, effectively balancing statistical utility with constraints on source evidence for individual texts. The mechanism is straightforward and offers provable probabilistic bounds on the estimated proportions.

  2. Coherent Analysis and Experimentation. The study distinguishes between sampling fluctuations and persistent biases—the latter stemming from insufficient generation diversity—and demonstrates the impact of adjusting the "green" baseline. On the C4 dataset, with n=2000n=2000 and ε=1\varepsilon=1, the mean absolute error (MAE) is 0.85 percentage points.

Critical weaknesses
  1. Sensitivity to Common Text Editing. RGS relies on sequence-level hashing; even minor modifications to a text segment can alter its red-green labels. While the authors acknowledge this limitation, they do not evaluate the impact of editing on the accuracy of proportion estimation, leaving the method's effectiveness for text circulating in real-world scenarios unclear.

  2. Insufficient Empirical Evidence Regarding Generation Quality. Although the paper claims that the method preserves generation quality, the experiments focus primarily on estimation error. There is a lack of comparative results—such as essay quality or code correctness—before and after the application of the watermark, making the claim that "generation quality is maintained" insufficiently supported.

Questions for authors
  1. In the experiments, the non-watermarked (unwatermarked) texts are drawn from the same base model. In real-world settings, however, the background corpus would likely include human-authored content and outputs from other models. Since the estimation formula assumes that the "green" proportion in unwatermarked text remains close to the theoretical baseline, does this approximation still hold when the data originates from diverse sources? If the proportion deviates from the baseline, does this introduce additional bias or increased variance in the estimation?

  2. Because RGS requires rejecting certain candidates and regenerating text, the actual computational cost depends on the number of resampling iterations performed. Compared to direct generation using the base model, how much do the average number of generation attempts and the actual elapsed time increase? Do these overheads vary significantly depending on the task type or the level of privacy protection?

1 comment

Thank you for taking the time to review our submission and offer valuable feedback. We address your questions and concerns in our response below.

Diverse data sources

Since the estimation formula assumes that the "green" proportion in unwatermarked text remains close to the theoretical baseline, does this approximation still hold when the data originates from diverse sources?

Although our experiments use unwatermarked text from the same base model, our method allows for arbitrary text distributions pip_i. We have updated the paper to highlight this. Under Assumption 1, we have that Ek[gi(k)]=π0\mathbb{E}_k[g_i(k)]=\pi_0 for arbitrary distributions pip_i.

If the proportion deviates from the baseline, does this introduce additional bias or increased variance in the estimation?

For a fixed key kk, the unwatermarked green probability gi(k)g_i(k) can deviate from π0\pi_0. This leads to estimator bias, which we denote as U(k)=1I0∑i∈I0gi(k)−π0U(k) = \frac{1}{I_0} \sum_{i\in I_0} g_i(k) - \pi_0 in Section 5.2. We note that Lemma 1 directly shows that greater diversity among unwatermarked texts makes gi(kg_i(k) concentrate more tightly around π0\pi_0, thus reducing the bias.

For a fixed key, under Assumption 1, the green indicator Hi=1hk(Yi)=GH_i=\mathbf{1}_{h_k(Y_i)=G} is a Bernoulli random variable with success probability gig_i, whose variance is gi(1−gi).g_i(1-g_i). Therefore deviations of gig_i from π0\pi_0 changes the variance, but the overall effect on variance depends on the value of π0\pi_0 and the direction of the deviation. More importantly, we note that the variance term of estimator error vanishes like O(1/n)O(1/n) for fixed π0,π1\pi_0, \pi_1 (see Proposition 2). Therefore, bias is the main concern at larger sample sizes.

Text editing

We agree that editing can have nontrivial impacts on estimation, and that our experiments do not test RGS's robustness to editing. However, we would like to highlight that the strong privacy guarantees of RGS are intended to reduce user incentives for editing. Also, we could compose RGS with various standard techniques for making watermarks robust, like locality sensitive hashing, or hashing with some error correcting codes.

Quality preservation

Please see our discussion in response to all reviewers.

Rejection Sampler efficiency

Please see our discussion in response to all reviewers.

Reviewer_QMZYOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes a language model watermarking framework that balances privacy protection with the estimation of overall usage rates. Unlike traditional watermarking techniques, which focus on detecting individual AI-generated texts, the authors shift their focus to estimating the proportion of watermarked texts within a text collection, whilst using Local Differential Privacy (LDP) to limit the detection evidence that a single text can provide.The authors propose the Red-Green Sequence (RGS) watermark, which employs keyed sequence-level hashing and rejection sampling to probabilistically reweight the entire text, and utilises a randomised response-style estimator to infer the overall watermark coverage ratio.

Critical strengths

This paper shifts the focus of language model watermarking from individual detection to privacy-preserving population estimation, attempting to resolve the conflict between watermark traceability and user privacy. The authors use LDP to formally constrain the strength of watermark evidence in individual texts and design an RGS sampling mechanism that satisfies the corresponding likelihood ratio bounds. This research direction exhibits a degree of novelty and provides application scenarios for watermarking that differ from individual tracking.

The authors point out that simply borrowing the frequency estimation formula from Randomised Response is not always accurate, as the red-to-green ratio under a fixed key is influenced by the output distribution of the underlying language model. The paper analyses the different sources of bias between the unwatermarked and watermarked groups through collision probability and distribution overlap, revealing that low-entropy distributions may lead to persistent estimation bias. This theoretical analysis provides valuable insights into understanding the statistical limitations of sequence-level watermarking.

Critical weaknesses

Section 5.3 claims that asymptotic consistency of the estimator can be achieved by increasing π0\pi_0 and adjusting d=π1−π0d=\pi_1-\pi_0. However, the authors state that dd can be set to 00 whilst satisfying d=o(1/n)d=o(1/n). According to the variance upper bound used in Proposition 2, the normalised sampling variance is O(1/(nd2))O(1/(nd^2)). For this upper bound to tend to zero, nd2nd^2 must tend to infinity, i.e. d=ω(n−1/2)d=\omega(n^{-1/2}), rather than o(1/n)o(1/n).

RGS relies on Rejection Sampling, which requires repeatedly generating complete text sequences until a candidate satisfies the acceptance criteria. Compared to traditional token-level watermarking, this may introduce significant additional inference overhead. Although the paper provides a theoretical upper bound on the expected number of samples in Appendix A.2, the experiments do not adequately report the actual number of samples, end-to-end generation latency, or computational overhead across different tasks.

Questions for authors

Could you clarify the convergence rate statement d=o(1/n)d=o(1/n) in Section 5.3? Given the current variance upper bound, this appears to contradict the requirement that the sampling variance tends to zero.

Could you provide additional assessments of text quality and generation cost, such as perplexity and composition quality?

3 comments

Thank you for taking the time to review our submission and offer valuable feedback. We address your questions and concerns in our response below.

Convergence rate statement

The existing variance upper bound indeed requires nd2→∞nd^2\to\infty to vanish, which implies d=ω(n−1/2).d=\omega(n^{-1/2}). We apologize for the oversight and have updated the paper to reflect this change.

Quality preservation

Please see our discussion in response to all reviewers.

Rejection Sampler efficiency

Please see our discussion in response to all reviewers.

Thank you for the detailed response and additional experiments. I appreciate the authors' efforts to address my concerns, particularly the correction of the convergence condition and the additional quality evaluations. However, I still have concerns about the practical efficiency of the rejection sampling approach. While the reported number of samples is helpful, actual end-to-end generation latency and computational overhead remain insufficiently evaluated.

Thank you for getting back to us. We are glad that we have addressed most of your concerns. We have conducted another experiment to show that our rejection sampler achieves low end-to-end generation latency.

We measure end-to-end generation latency of the rejection sampler on the same 500 C4 prompts used in previous experiments, using Qwen3-4B on a single NVIDIA RTX 3090 with vLLM. For each prompt, we generated one unwatermarked response and one RGS response using rejection sampling with M=16M=16, π0=0.5\pi_0=0.5, and ε=1\varepsilon=1, with a maximum of 50 tokens. The recorded times include tokenization, generation of all candidates, and RGS hashing and selection, but exclude model loading, warm-up, and cache resets.

Across the 500 responses, the mean latencies are 0.644s without watermarking and 0.999s with RGS, while the median latencies are 0.646 and 0.647s respectively. The empirical mean latency is consistent with the theoretical characterization and empirical result for the mean number of attempts needed for the rejection sampler. Additionally, we see that the median latency is extremely close to the base model latency. Overall, our rejection sampler is end-to-end efficient.

Reviewer_eURSOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper develops the Red-Green Sequence watermark to estimate the prevalence of watermarked texts while limiting the evidence each individual text contributes to detection. RGS uses a keyed hash to partition text sequences into red and green sets, then reweights their sampling probabilities to satisfy ε\varepsilon-local differential privacy with respect to the base model. The authors present a parallel sampler, a rejection sampler, and a moment estimator based on the fraction of green texts. Their analysis characterizes bias and variance in terms of watermark entropy and distributional diversity, and studies how increasing the null green fraction π₀ mitigates bias. Experiments on C4, essay writing, and coding tasks evaluate frequency estimation using Qwen and Llama models across privacy budgets, sample sizes, and mixture proportions.

Critical strengths
  1. A concrete privacy objective and a simple construction. The paper formulates watermark prevalence estimation under ε\varepsilon-local differential privacy with respect to the base model. RGS satisfies this constraint through a simple rejection sampler that supports black-box implementation. This combination provides a concrete framework for estimating aggregate usage while limiting the watermark evidence contributed by individual texts.

  2. Useful characterization of persistent bias. The analysis distinguishes generation entropy from distributional diversity and explains why bias for watermarked texts can persist even when null bias decreases. It connects these effects to collision probabilities and studies how the null green fraction controls the bias–variance trade-off. The supporting experiments make this analysis consequential: it guides parameter selection and explains why larger sample sizes can favor a different null green fraction.

Critical weaknesses
  1. The asymptotic consistency claim requires a more explicit limiting regime. Proposition 3 retains a normalized bias term, and Lemma 3 establishes monotonicity rather than convergence to zero. Letting d=π1−π0→0d=\pi_1-\pi_0\to0 also requires joint control of sampling variance and the remainder. The paper should distinguish its fixed-parameter error bound from consistency under changing π0\pi_0, and state the additional conditions that support the latter claim.

  2. The evaluation leaves the advantage of sequence-level watermarking unclear. The experiments compare RGS across models and parameter settings. Comparisons with token-level watermarks under a matched sequence-level privacy budget, comparable decoder access, and the same output-only detection requirement would clarify when sequence-level hashing and resampling offer a meaningful advantage.

  3. The quality-preserving claim lacks direct empirical support. The evaluation focuses on frequency estimation. Measurements of text quality and code correctness, compared with outputs from the base model, would substantiate this claim.

Questions for authors
  1. Consistency conditions. What joint limiting regime for π0\pi_0, sample size, generation entropy, and distributional diversity supports the asymptotic consistency claim?

  2. Finite-MM calibration. Which value of π1\pi_1 do the experiments use when M=16M=16? How does this calibration account for the fallback in Algorithm 2, particularly when comparing different null green fractions in Appendix A.4?

2 comments

Thank you for taking the time to review our submission and offer valuable feedback. We address your questions and concerns in our response below.

Asymptotic estimation error

We agree that the original consistency statement was insufficiently qualified. We have revised Section 5 to distinguish finite-sample error guarantee from consistency.

Finite-M effects

Which value of do the experiments use when M=16M=16? How does this calibration account for the fallback in Algorithm 2, particularly when comparing different null green fractions in Appendix A.4?

Consistent with the experiments in Section 6, we used π0=0.5\pi_0=0.5 and π1=eεπ0eεπ0+1−π0\pi_1 = \frac{e^\varepsilon \pi_0}{e^\varepsilon\pi_0+1-\pi_0} in Appendix A.4. This calibration of π1\pi_1 corresponds to the infinite budget case M→∞M \to \infty. We further test the finite-M effect using the following recalibrated value in the moment estimator, which corrects for the finite-M error: π1(M)=eεπ0eεπ0+1−π0[1−((1−π0)(1−e−ε))M].\pi_1^{(M)} = \frac{e^\varepsilon \pi_0}{e^\varepsilon \pi_0+1-\pi_0} \left[1-\left((1-\pi_0)(1-e^{-\varepsilon})\right)^M \right]. We then replot Figure 3 in Appendix A.4 using this value for π1\pi_1, keeping everything else unchanged. We have attached the new figure to Appendix A.4 of the revised submission. The figure shows that the conclusions about the benefits of a larger π0\pi_0 still hold, and the scaling trend is very similar to that of Figure 3.  

Token-level watermarks

We had an earlier experiment result on token-level watermarks. At each position t∈[T]t \in [T] with a total T=50T=50 tokens, we apply the token-level watermark decoder (equation 1) with δt=0.1643\delta_t=0.1643 for each tt. By the optimal composition theorem [KOV15], composing over 50 tokens yields overall (5,10−5)(5,10^{-5})-approximate DP, which is a strictly weaker privacy guarantee (which should have stronger estimation performance) than all the experiments presented in this paper. In the C4 mixture task, the mean estimates for true proportions 0.1,0.5,0.90.1, 0.5, 0.9 are 0.069,0.288,0.5090.069, 0.288, 0.509 respectively. These estimates are promising but not as good as the sequence-level ones, which is why we chose to focus on sequence-level watermarks for this work. Nevertheless, we believe that there might be better ways of doing token-level private watermarks that would bring the performance closer to the sequence level ones, which would be an exciting direction for future work.

Quality preservation

Please see our discussion in response to all reviewers.

References

[KOV15] Peter Kairouz, Sewoong Oh, and Pramod Viswanath. 2015. The composition theorem for differential privacy.

Thank you for the response and clarifications. The revised consistency statement and the finite-MM calibration address some of my concerns. I still have reservations about the experimental evidence for the advantage of sequence-level watermarking. In particular, the token-level results show substantial systematic underestimation, while the estimator and signal calibration remain unclear. This uncertainty limits the conclusions I can draw from the comparison with RGS. I appreciate the authors’ efforts to address the review, but the remaining experimental concerns continue to affect my overall assessment.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Response to all reviewers

We thank all reviewers for their thoughtful comments and feedback. Below we address some common concerns about the paper.

Quality preservation

We remark that theoretically, our privacy requirement directly bounds distributional distortion from the base model, conditional on any fixed key. For any key kk, Definition 1 guarantees for any text yy, e−εp(y)≤q(y∣k)≤eεp(y),e^{-\varepsilon}p(y)\le q(y\mid k)\le e^\varepsilon p(y),where p(⋅)p(\cdot) and q(⋅∣k)q(\cdot\mid k) are the text distributions of the base model and watermarked model respectively. As a result of this likelihood ratio bound, both DKL(q(⋅∣k)∣∣p)D_{\mathrm{KL}}(q(\cdot\mid k)||p) and DKL(p∣∣q(⋅∣k))D_{\mathrm{KL}}(p||q(\cdot\mid k)) are bounded by ε\varepsilon.

Empirically, we evaluate the quality preservation properties of RGS using coding pass@1 and language modeling perplexity. First, we evaluate RGS on all 164 python programming problems in the HumanEval dataset. We use Qwen3 models with an 8192-token thinking budget and a 256-token final answer budget. In the table below, we report the means and standard deviations of pass@1 over 20 keys. The results indicate that RGS preserves answer quality well.

Model nameBase modelRGS ε=1RGS ε=2RGS ε=3
Qwen3-1.7B45.38%45.48% ± 0.44%45.71% ± 0.64%45.98% ± 0.75%
Qwen3-4B83.09%83.01% ± 0.37%82.80% ± 0.50%82.62% ± 0.60%
Qwen3-8B82.96%82.76% ± 0.43%82.35% ± 0.60%81.98% ± 0.84%

On the C4 language modeling task, we report the percentage changes in text perplexity before and after the RGS watermark, using Qwen3-14B-Base as the shared evaluator. The table below shows the means and standard deviations of the changes over 20 random keys. As a reference, the mean changes in C4 perplexity using the regular soft-red-list watermark of [KGW23] over 50-token sequences on Qwen3-4B with δ=1,2\delta=1,2 are 1.13% and 4.43% respectively. Therefore, our RGS watermark achieves much better quality preservation than regular non-private counterparts, as the percentage change in perplexity is very small, and is one magnitude smaller than nonprivate ones.

Model nameRGS ε = 1RGS ε = 2RGS ε = 3
Qwen3-1.7B0.04% ± 0.33%0.22% ± 0.32%0.23% ± 0.31%
Qwen3-4B0.17% ± 0.37%0.28% ± 0.49%0.14% ± 0.42%
Qwen3-8B0.64% ± 0.29%0.51% ± 0.33%0.49% ± 0.29%

Computational efficiency of the rejection sampler

We report the number of candidates examined per RGS response until the rejection sampler accepts, with M=16M=16 and π0=0.5\pi_0 = 0.5. We see that our rejection sampler only needs around 1.5-2 samples per completion across various privacy levels ε\varepsilon. Notably, the more private (smaller ε\varepsilon) the watermark, the fewer samples are needed.

RGS ε\varepsilonC4OUTFOXLiveCodeBench
11.463 ± 0.0041.463 ± 0.0071.487 ± 0.022
21.765 ± 0.0091.763 ± 0.0091.846 ± 0.066
31.909 ± 0.0111.906 ± 0.0102.058 ± 0.125

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.