PaperlayerView exact revision on arXiv

Source-linked AI summary

Unbiased Watermark for Large Language Models

Zhengmian Hu, Lichang Chen, Xidong Wu, Yihan Wu, Hongyang Zhang, Heng Huang

arXiv:2310.10669v2cs.CR

TL;DR

Watermarking may help track LLM outputs amid concerns about misuse, but prior work raises a trade-off between watermark strength and text quality. This paper develops unbiased watermark methods and reports that suitable implementations preserve output distributions and quality. The authors also identify practical limits for watermark detection when the detector's model differs from the true text distribution.

  • Problem

    Watermarking can help track LLM outputs, but prior work suggests a trade-off between watermark strength and generated-text quality.

    Source: §1 · p. 1

  • Method

    The paper develops an unbiased watermark framework, including δ-reweight and γ-reweight techniques and a maximin variant of the log-likelihood ratio test.

    Source: §1 · p. 2

  • Results

    With suitable implementation, watermarking can leave the output probability distribution unchanged, and δ-reweight and γ-reweight preserve output quality in translation and summarization.

    Source: §1 · pp. 1–2

  • Takeaways & Limitations

    The framework supports watermark-based tracking and intellectual-property protection without compromising generated-text quality.

    Source: §8 · p. 9

    Detection may be affected when the watermark model differs from the true text distribution, including after editing or when prompt and temperature are unknown.

    Source: §5.3 · p. 7

Abstract

from arXiv · show

The recent advancements in large language models (LLMs) have sparked a growing apprehension regarding the potential misuse. One approach to mitigating this risk is to incorporate watermarking techniques into LLMs, allowing for the tracking and attribution of model outputs. This study examines a crucial aspect of watermarking: how significantly watermarks impact the quality of model-generated outputs. Previous studies have suggested a trade-off between watermark strength and output quality. However, our research demonstrates that it is possible to integrate watermarks without affecting the output probability distribution with appropriate implementation. We refer to this type of watermark as an unbiased watermark. This has significant implications for the use of LLMs, as it becomes impossible for users to discern whether a service provider has incorporated watermarks or not. Furthermore, the presence of watermarks does not compromise the performance of the model in downstream tasks, ensuring that the overall utility of the language model is preserved. Our findings contribute to the ongoing discussion around responsible AI development, suggesting that unbiased watermarks can serve as an effective means of tracking and attributing model outputs without sacrificing output quality.

1 Introduction

Watermarking can help track potential misuse of LLM outputs, but existing approaches raise concerns about output quality. The paper introduces unbiased watermarks and practical methods intended to preserve output quality while supporting detection.

1 Introduction

  • Watermarking can embed imperceptible information in generated text to support tracking and attribution amid concerns about LLM misuse.It can also serve ownership protection and monitoring of potential misuse.Source: §1 · p. 1
  • Earlier work described a trade-off between watermark strength and text quality when adjusting the logits of randomly selected green tokens [34].That trade-off was demonstrated by tuning the magnitude of the logits adjustment.Source: §1 · p. 1
  • Unbiased watermarking is presented as a way to watermark outputs without changing their probability distribution or degrading quality.The paper also describes a framework for designing and detecting such watermarks.Source: §1 · pp. 1–2
  • The proposed δ-reweight and γ-reweight techniques preserve output quality in machine translation and text summarization experiments.The paper also proposes a maximin variant of the log-likelihood ratio test with a theoretical upper bound on type I error.Source: §1 · p. 2

2 Preliminary

This section formalizes watermarking for autoregressive LLMs and sets the goal of provider-detectable but user-undetectable watermarks that do not harm output quality. It relates distributional undetectability to downstream-task invariance.

2 Preliminary

  • LLMs generate tokens autoregressively, with each next-token probability conditioned on the preceding context; watermarked generation is additionally conditioned on a private key.The clean and watermarked sequence probabilities are denoted separately.Source: §2 · p. 2
  • The section frames watermark design as efficient provider detection alongside user undetectability and no negative impact on output quality.It links user detectability to quality: a quality decline should permit an inference of watermark presence, while undetectability implies no quality impact.Source: §2 · p. 2
  • The section defines strict undetectability through equality of watermarked and original output distributions, and introduces downstream invariance for task metrics.The downstream-invariance definition quantifies over strings and metrics.Source: §2 · p. 2
  • One-shot undetectability implies downstream invariance, even when users could discern a watermark through multiple generation requests.Identical distributions yield identical expectations for any function; the implication does not require n-shot undetectability for n > 1.Source: §2 · p. 3
  • The section sets n-shot undetectability and downstream invariance as guarantees for quality preservation, before presenting a framework that is n-shot-undetectable for any n ≥ 1.The framework is previewed for Section 4.Source: §2 · p. 3

3 Warm up: undetectability in a simplified toy environment

A binary random-number example illustrates how a hidden key can make a watermarked output indistinguishable from a clean one for a single request. The authors distinguish this toy setting from practical LLM watermarking.

3 Warm up: undetectability in a simplified toy environment

  • For a single request, a user unaware of the key cannot distinguish the toy watermarked output from the clean output.The example uses a uniformly distributed binary output and an equally likely binary key.Source: §3 · p. 3
  • The toy example is limited: LLM vocabularies are larger and nonuniform, generation is autoregressive, and the example is not n-shot-undetectable for n > 1.The paper presents the simplified analysis as a foundation for more complex scenarios.Source: §3 · p. 3

4 Watermarking with unbiased reweighting

The section develops unbiased reweighting methods and a framework for applying them to autoregressive language models. With independent watermark codes, the expected probability of an entire watermarked sequence matches the original sequence distribution.

4 Watermarking with unbiased reweighting; 4.1 Distribution reweighting

  • The framework applies the general reweighting approach to language-model generation, requiring an unbiased reweighting function and a context-code function.The section presents the final framework after introducing the reweighting technique and applying it to autoregressive generation.Source: §4 · p. 3, §4.1 · p. 3

4.1.1 Existing reweighting methods; 4.1.2 Unbiased reweighting methods

  • δ-reweight and γ-reweight are unbiased over code randomness, unlike the described hard- and soft-red-list methods.δ-reweight samples a token and returns a point mass; γ-reweight shuffles the vocabulary, rejects half the regions, and amplifies the rest.Source: §4.1.1 · pp. 3–4, §4.1.2 · p. 4

4.2 Reweighting for autoregressive model

  • For an individual unaware of the watermark code, an unbiased reweighting preserves the next-token distribution; knowing the code enables statistical testing.The expectation over watermark codes of the reweighted distribution equals the original distribution.Source: §4.2 · pp. 4–5

4.2.1 Independence of watermark codes

  • When watermark codes are i.i.d., the expected probability of an entire watermarked sequence equals the original sequence probability.This sequence-level guarantee depends on independent codes, not merely on each token reweighting being unbiased.Source: §4.2.1 · p. 5
  • Independent codes are essential: identical codes can produce biased sequences, such as sequences consisting solely of 0s or solely of 1s.The paper says independence is needed to ensure the entire sequence remains unbiased.Source: §4.2.1 · p. 5

4.2.2 Context code

  • Context codes can use the full prefix or the most recent m tokens; error-correcting approaches for text-manipulation resilience are left to future work.The watermark code is generated from the context code and a secret key, and a theorem guarantees such a code-generation function exists.Source: §4.2.2 · p. 5
  • If a context code repeats during generation, the method skips reweighting that token to avoid reusing its watermark code.The repeated-code case would violate the independence of the generated codes.Source: §4.2.2 · p. 5

4.3 Framework

  • Algorithm 1 generates each token from the original or reweighted distribution, depending on whether its context code has appeared before.The framework takes a key, prompt, target length, context-code function, code-generation function, and reweighting function as inputs.Source: §4.3 · p. 6

5 Statistical hypothesis testing for watermark detection

The section formulates watermark detection as statistical hypothesis testing and develops score-based tests, including a maximin LLR variant. The variant addresses mismatch between the detector's watermark model and the true distribution, with a threshold adjustment for grid search over scores.

5 Statistical hypothesis testing for watermark detection; 5.1 Score-based tesing

  • Detection compares unmarked and marked hypotheses using token scores accumulated across the text, with a threshold determining whether to reject the null hypothesis.The section distinguishes type I and type II errors and requires a bounded conditional exponential moment under H0 for its theoretical bound.Source: §5 · p. 6, §5.1 · p. 6

5.2 Log likelihood ratio (LLR) score

  • The LLR score is the most powerful test at a fixed type I error rate and follows from maximizing the average score under H1 subject to a null-hypothesis constraint.The optimization recovers the log-likelihood ratio score.Source: §5.2 · p. 7

5.3 Maximin variant of LLR score

  • The maximin variant addresses detector-model mismatch, including editing or imperfect knowledge of the prompt and generation temperature.It considers a perturbed generation distribution whose per-token total variation distance from the watermark distribution is bounded by d.Source: §5.3 · p. 7
  • The maximin variant yields higher scores after some editing, but is not specifically designed to defend against attacks.Its computation can be done in eO(|Σ|) time.Source: §5.3 · p. 7
  • Figure 3 shows distributions of output perplexity for text summarization and BLEU score for machine translation.The caption identifies the plotted metrics and tasks but does not specify a comparison outcome.Source: Figure 3 · p. 8
  • For grid search over A candidate scores, the threshold becomes ˆS = −log(α) + log(A), preserving the upper bound α on type I error.The threshold adjustment accompanies the result for multiple scores.Source: §5.3 · pp. 7–8

6 Experiments

The experiments compare unbiased watermarking with soft-red-list watermarking on text summarization and machine translation, and also illustrate watermark scores on generated text. The authors report preserved output quality for their methods and degradation for soft-red-list when δ > 0.

6 Experiments

  • Experiments use BART-large on CNN-DM for summarization and Multilingual BART on WMT’14 English–Romanian for translation.The comparison includes δ-reweight, γ-reweight, and Kirchenbauer et al.’s soft-red-list method [34].Source: §6 · p. 8
  • Unbiased δ-reweight and γ-reweight preserve output quality across tasks and metrics, while soft-red-list significantly impairs it when δ > 0.Soft-red-list with δ = 0 introduces no watermark and does not affect quality.Source: §6 · p. 8, Table 1 · p. 8
  • Figure 3 shows stable score distributions and unchanged mean performance for unbiased methods, versus a performance decrease for soft-red-list.Source: §6 · p. 8
  • A sentence score sum of 10 ensures p < 0.0005, while a sum of 20 ensures p < 3e−8.The paper presents mean and variance of token scores by task and method in Table 3.Source: §6 · p. 8
  • Table 2 illustrates token-level score distributions in OPT-6.7B completions, using green for positive scores, red for negative scores, and darker shades for larger absolute values.Its three outputs have grid-searched perturbation strengths d of 0.9, 0.0, and 0.0.Source: §6 · p. 9, Table 2 · p. 9

7 Related work

The related-work discussion situates text watermarking among prior approaches and recent generative-model watermarking research. It also identifies concurrent studies and summarizes the scope of Table 3.

7 Related work

  • Table 3 reports mean and variance of per-token scores across reweighting methods and tasks.Source: Table 3 · p. 9
  • Text watermarking was explored before LLMs, and recent generative models enabled direct generation of watermarked results.The cited earlier work includes; relevant generative-model work includes Kirchenbauer et al. [34] and Aaronson.Source: §7 · p. 9
  • Concurrent studies [10] [36] [65] [73] further developed the generative-model watermarking area.Source: §7 · p. 9

8 Conclusion

The conclusion presents watermarking without compromised text quality as a framework for protecting intellectual property and monitoring misuse. The related-work sections distinguish text watermarking from neighboring approaches and describe attacks and concurrent methods.

8 Conclusion

  • The paper’s framework aims to protect intellectual property and monitor potential misuse without compromising generated-text quality.The conclusion describes it as a foundation for future work in LLM watermarking.Source: §8 · p. 9

A.1 Text watermarking

  • Earlier text-watermarking methods edit existing text, while generative-model work embeds watermarks during generation; the paper addresses bias in Kirchenbauer et al. [34] through unbiased reweighting and context-code history.Aaronson describes a cryptographic pseudorandom function without disclosed details, making direct comparison challenging; the paper says it remains uncertain whether it offers a similar n-shot-undetectability guarantee.Source: §A.1 · p. 14
  • Concurrent watermarking approaches trade computational assumptions or key-sequence length against strict unbiasedness, while this work uses additional watermark storage to guarantee n-shot undetectability regardless of attacker computation.Kuditipudi et al. [36] may reuse a key sequence when content exceeds its length, compromising strict unbiasedness; [10] relies on computational power.Source: §A.1 · p. 14

A.2 Attacks on watermarks

  • Watermark-removal research includes invisible-character and homoglyph attacks, generative attacks, emoji attacks, and paraphrasing attacks.The passage cites [44], [34],, and [50] [35], respectively.Source: §A.2 · p. 14

A.3 Steganography in text

  • Unlike watermarking, steganography must recover all embedded information, not merely detect a watermark’s presence.Source: §A.3 · p. 14

A.4 Watermarking models

  • Model watermarking traces a model to guard against stealing or extraction, whereas text watermarking traces generated text.Model watermark evidence can be gathered through inference services and backdoors.Source: §A.4 · p. 14

A.5 Detecting machine-generated text

  • Machine-generated-text detection asks whether text was written by a human or generated by an algorithm; text watermarking identifies a particular model or provider.The passage notes that improved language models and adversarial attacks make machine-generated-text detection increasingly challenging.Source: §A.5 · p. 14

B.1 Detailed definition and additional proofs for Section 4.1

The appendix details why red-list reweighting is biased and why δ-reweight and γ-reweight are unbiased. It also spells out the assumptions for multi-request undetectability and the proof and implementation details of the maximin score.

B.1 Detailed definition and additional proofs for Section 4.1

  • Hard- and soft-red-list reweighting are biased, whereas δ-reweight and γ-reweight are unbiased reweighting functions.The appendix gives formal definitions for both proposed methods and states the unbiasedness result in Theorem 14.Source: §B.1 · p. 15

B.2 Additional proofs for Section 4.2

  • The proof of sequence-level unbiasedness uses independence of watermark codes and the unbiasedness of the reweighting function.The construction described is an instance of an unbiased watermark code generation function.Source: §B.2 · pp. 16–17

B.3 Detailed theory for Section 4.3

  • Continuous context-code history supports n-shot undetectability; resetting it after each request guarantees only 1-shot undetectability, while resetting per batch supports b-shot undetectability.Previously used context codes are skipped during reweighting to avoid repeated codes and preserve independence.Source: §B.3 · p. 17

B.4 Proof of tailed bounds in Section 5

  • The tailed-bound proof applies a Chernoff bound to obtain the stated result.Source: §B.4 · p. 17

B.5.1 Derivation of the solution

  • The maximin derivation relaxes a constraint, and the appendix states that this relaxation is tight and leaves the optimal solution unchanged.Source: §B.5.1 · p. 18

B.5.2 Computing the solution

  • Computing the maximin solution reduces to finding Xmax and Xmin in eO(|Σ|) time; the experimental implementation uses log space for numerical stability.The implementation also reuses grid-search computations and uses tensor operators for GPU computation.Source: §B.5.2 · p. 19

C Additional discussion

The additional discussion outlines practical limits on likelihood-based detection and presents a likelihood-agnostic scoring alternative. That alternative uses Gumbel-based reweighting and a score with a tail-bound property, but has trade-offs in low-entropy settings and detection strength.

C Additional discussion

  • Without context code history, n-shot-undetectability is no longer guaranteed, and constructed random-bit prompts can yield incorrect outputs.The authors say downstream performance is not significantly degraded in many instances because context-code collisions are unlikely, but corner cases may undermine task performance.Source: C Additional discussion · pp. 20–21
  • Likelihood-based detection may have to estimate PM when generation settings or the prompt are unavailable, and a mismatch with PM can lower the score.The text gives an empty prompt or back-translation as possible ways to estimate the original distribution.Source: C Additional discussion · p. 21
  • Likelihood-based detection requires a language-model forward pass, making it more computationally expensive than red-list methods but less costly than generation.The framework also supports likelihood-agnostic detection methods, which have their own pros and cons.Source: C Additional discussion · p. 21

D Likelihood-agnostic watermark score

  • The framework supports likelihood-agnostic detection that does not rely on a language model or its output logits to compute the score.The score is designed separately from likelihood-based methods, which derive their scores from the original and reweighted distributions.Source: D Likelihood-agnostic watermark score · p. 21, §D.1.2 · p. 22

D.1.1 Reweighting function

D.1.2 Score design and tail bound

  • The Gumbel-based score is chosen so independent Gumbel variables satisfy E[exp(si)] ≤ 1, supporting a tail bound similar to Theorem 8.For repeating context codes, the method sets the score to zero to preserve the independence condition required by Theorem 16.Source: §D.1.2 · p. 22

D.2 Comparison between likelihood-based score and likelihood-agnostic score

  • Likelihood-agnostic scoring is less informative in low-entropy settings, while likelihood-based scoring can provide higher scores when PM is known.The likelihood-agnostic score can add noise in low-entropy cases; it also has lower computational cost and may be preferable when PM is hard to estimate.Source: §D.2 · p. 22

E Detailed experiment setup

The experiments evaluate unbiased watermarking on summarization and translation, then examine detection-score sensitivity and likelihood-agnostic scoring. Results report that detection scores decline when the estimated distribution differs from the generation distribution, while score behavior varies by task entropy.

E Detailed experiment setup

  • The setup evaluates text summarization on 11,490 CNN-DM examples with BART-large and translation on 1,999 WMT’14 English-to-Romanian examples with MBart.It tests δ-reweight and γ-reweight with five-token context codes, and uses ROUGE for summarization, BLEU for translation, plus BERTScore and Perplexity as auxiliary metrics.Source: E Detailed experiment setup · pp. 22–23

F.1 Adding watermark

  • Additional results compare watermarking methods on text-summarization and machine-translation performance, with BERTScore and ROUGE scaled in Table 4 and BERTScore scaled in Table 5.The supplied passages do not report the table values.Source: §F.1 · p. 23, Table 4 · p. 23, Table 5 · p. 23

F.2 Sensitivity of scores

  • When the detection distribution differs from the generation distribution, scores decline and more tokens are needed; tables examine temperature, top_k, input, and model mismatches.The experiments also compare δ-reweight and γ-reweight: δ-reweight scores higher when distributions match, but declines more sharply under mismatch.Source: §F.2 · pp. 23–24, Table 6 · p. 24, Table 7 · p. 24
  • For the sensitivity comparison, δ-reweight scores higher than γ-reweight when distributions match, but its score drops more sharply under mismatch.The decline for γ-reweight is described as more gradual across distribution differences.Source: §F.2 · p. 24

F.3 Likelihood-agnostic score

  • The likelihood-agnostic score is positive but an order of magnitude below the likelihood-based score for summarization, and negative for machine translation.Summarization is described as relatively high entropy and translation as low entropy.Source: §F.3 · p. 24

F.4 Verifying downstream-invariant property of watermark for more models

  • Additional results include T5 translation and LLaMA 2 summarization and poem-generation evaluations.Table 11 is identified as containing these results; the supplied passage does not state their values.Source: Table 11 · p. 25

F.5 Robustness of watermarks

The robustness evaluation applies random token substitution to generated text and measures detection using AUC. The authors limit the stated scope of the method to high-entropy generation, making beam search challenging because of its deterministic nature.

F.5 Robustness of watermarks

  • Robustness is assessed by replacing a fraction of generated tokens with random tokens and measuring detection-score AUC across perturbation levels.The evaluation starts at ε = 0.0 and increases to ε = 0.5; it uses the paper’s detection score for unbiased methods and the z-score for soft-red-list methods.Source: §F.5 · p. 25

G.1 Major Limitations

  • The method is limited to high-entropy generation; deterministic beam search is challenging because a zero-entropy model always yields its original fixed output under unbiased watermarking.The authors state that in this extreme case, an unbiased watermark yields the same result as the original model.Source: §G.1 · p. 25

G.2 Minor Limitations

The paper identifies limits in robustness testing and design choices, alongside storage costs for stronger undetectability. It connects watermarking to traceability and attribution while noting risks to privacy, transparency, and consent.

G.2 Minor Limitations

  • The study tests robustness against only random substitution, leaving other removal attacks, including insertion and paraphrasing, outside its scope.The authors also say the design space of reweighting functions and context codes remains unexplored, with no clear optimum and no standard evaluation metrics.Source: §G.2 · p. 25
  • Retaining context-code history enables n-shot-undetectability but increases storage complexity with O(n).The authors describe this as a trade-off between storage and undetectability.Source: §G.2 · p. 26

H.1 Impact analysis

  • Watermarking supports tracing text origins and provider accountability, and can help identify model-generated text to avoid training on it.The paper also notes that watermarks may provide evidence in ownership claims.Source: §H.1 · p. 26
  • Discretionary watermark use could link generated text to a specific user or request, raising privacy concerns; watermark manipulation or removal could prompt an arms race.These risks are described as potential consequences.Source: §H.1 · p. 26

H.2 Ethical considerations

  • Because users cannot disprove watermarking, they may have to assume it is present, raising consent and transparency questions.The paper calls for transparency about embedded information and its use, including who can access identifying information.Source: §H.2 · p. 26

H.3 Conclusion

  • The conclusion pairs traceability and attribution with fair use, while identifying privacy, transparency, and consent as challenges requiring thoughtful implementation.The paper states that its watermark does not degrade output quality.Source: §H.3 · p. 26, §H.2 · p. 26
Loading 2310.10669v2…