PaperlayerView exact revision on arXiv

Source-linked AI summary

Provable Robust Watermarking for AI-Generated Text

Xuandong Zhao, Prabhanjan Ananth, Lei Li, Yu-Xiang Wang

arXiv:2306.17439v2cs.CLcs.LG

TL;DR

LLM watermarking seeks to make generated text identifiable while preserving quality and resisting post-processing, an important response to potential misuse. The paper formalizes these requirements and proposes Unigram-Watermark, a fixed-split K = 1 scheme. It reports superior detection accuracy and robustness, with applicability of most results to K-gram watermarks with K ≥2, while acknowledging attack and optimality limitations.

  • Problem

    LLM watermarking must preserve generation quality while making sufficiently modified text necessary for evading detection after editing or paraphrasing.

  • Method

    The paper formalizes watermark quality, detection correctness, and post-processing security, then simplifies K-gram watermarking with a fixed Green-Red split in Unigram-Watermark.

  • Results

    Unigram-Watermark achieves superior detection accuracy and robustness against attacks, including over 85% accuracy at a 10% false positive rate in reported paraphrasing experiments.

  • Takeaways & Limitations

    Most reported results, including Type I error bounds and edit-robustness properties, apply to K-gram watermarks with K ≥2.

  • Takeaways & Limitations

    The fixed Green-Red split may not be universally optimal, performance varies with the model and generated text, and the method is not immune to all attacks.

Abstract

from arXiv · show

We study the problem of watermarking large language models (LLMs) generated text -- one of the most promising approaches for addressing the safety challenges of LLM usage. In this paper, we propose a rigorous theoretical framework to quantify the effectiveness and robustness of LLM watermarks. We propose a robust and high-quality watermark method, Unigram-Watermark, by extending an existing approach with a simplified fixed grouping strategy. We prove that our watermark method enjoys guaranteed generation quality, correctness in watermark detection, and is robust against text editing and paraphrasing. Experiments on three varying LLMs and two datasets verify that our Unigram-Watermark achieves superior detection accuracy and comparable generation quality in perplexity, thus promoting the responsible use of LLMs. Code is available at https://github.com/XuandongZhao/Unigram-Watermark.

1 Introduction

LLM watermarking addresses misuse concerns but must remain detectable after editing while preserving generation quality. The paper formalizes these requirements and proposes Unigram-Watermark with provable robustness guarantees.

  • LLM-generated text can support misuse including fake news, web-content contamination, academic dishonesty, and synthetic-data challenges.
  • Passive detectors rely on statistical patterns that are vulnerable to distribution changes, bias, and adversarial attacks.
  • Watermarking deliberately plants distinctive patterns to identify text from a specific language model rather than generically distinguishing humans from machines.
  • Editing or paraphrasing can remove the detectable green-list patterns used by prefix-dependent soft watermarking.
  • The paper introduces a framework for quantifying performance drop, detection correctness, and security against post-processing.
  • Unigram-Watermark fixes the Green-Red split, is provably twice as robust to edits as the baseline, and retains guarantees on quality and exponentially decaying detection errors.
  • Experiments report superior detection accuracy and improved robustness against attacks across varied language models and datasets.

2 Problem setup and method

The paper models watermarking as modifying a language model while preserving output quality and requiring substantial modification to evade detection. Its Unigram-Watermark uses a fixed vocabulary partition and provides simple detection with formal robustness properties, while exposing a robustness–learnability tradeoff.

  • Problem setup: A language model watermark embeds a secret message in generated tokens, seeking comparable output quality and resistance to sufficiently small modifications.
  • Problem setup: The framework uses edit distance to quantify insertion, deletion, and replacement operations between original and modified sequences.
  • Problem setup: Watermark and Detect respectively modify the model using a detection key and classify suspect text as generated by the watermarked model or not.
  • Method: Unigram-Watermark sets K = 1 in the K-gram family, producing one consistent green list for every generated token.
  • Method: The method partitions the vocabulary into green and red lists, increases green-token logits by δ, and detects watermarks by counting green tokens.
  • Method: Unigram-Watermark runs in linear time, requires neither the language model nor generation prompt for detection, and is intuitively robust to cropping and minor edits.
  • Method: The scheme is also described as resilient to reversing, shuffling, and emoji-insertion attacks.
  • Method: The fixed split improves robustness but may let attackers infer the green list, creating a robustness–learnability tradeoff.

3 Main theoretical results

Unigram-Watermark is supported by guarantees for output quality, detection correctness, and robustness to editing. Its detection errors decrease with sequence length under stated entropy and homophily assumptions, while the watermark tolerates linear-scale edits and is twice as robust as the baseline.

  • Quality guarantee: Theorem 3.1 bounds the Renyi-divergence between original and watermarked token distributions, establishing closeness across commonly used probability distances.The paper derives KL, chi-square, Hellinger, total variation, and max-divergence guarantees from the Renyi bound.
  • Detection correctness: For sufficiently diverse text, the detector’s z-score is O~(1) for text not generated by the watermarked model, supporting low false-positive rates.The threshold can depend on observed text statistics and provides an α-Type I error guarantee.
  • Detection correctness: Under average-high-entropy and homophily assumptions, watermarked text has z-score ≍δ√n while other text has z-score ≍O(1), creating a growing detection margin.The Type I and Type II error parameters decay exponentially as sequence length increases.
  • Robustness: With δ constant and an appropriate threshold, the watermark remains robust to O(n) arbitrary edits in high-entropy sequences.Theorem 3.7 bounds the change in the test z-score after edits, and the result applies when the edit distance is below the original sequence length.
  • Robustness: Unigram-Watermark is provably twice as robust to edits as Kirchenbauer et al.’s soft watermarking method.The paper also establishes new robustness guarantees for the soft-watermark baseline.

4 Experiment

Experiments evaluate detection, text quality, and robustness across three language models and two long-form datasets. Unigram-Watermark clearly separates watermarked text, preserves comparable perplexity, and outperforms the baseline under paraphrasing and editing attacks.

  • Watermarking results: A z-score threshold of 6.0 clearly distinguishes watermarked from non-watermarked text.The comparison uses δ = 2.0 and γ = 0.5 for both Unigram-Watermark and the baseline.
  • Watermarking results: Watermarked text has perplexity comparable to human-generated text, especially for LLaMA-7B.Perplexity is evaluated for human, unwatermarked machine-generated, and watermark-generated text on OpenGen.
  • Robustness results: Over 85% accuracy is achieved at a 10% false positive rate against paraphrasing attacks.Attacks use ChatGPT, DIPPER, and BART, and the method consistently outperforms KGW+23.
  • Robustness results: Unigram-Watermark consistently outperforms Kirchenbauer et al.’s watermark under synonym replacement, random deletion, and random swapping.These experiments directly test resilience to common editing operations that can remove embedded watermarks.
  • Distinguishing human-written text: On TOEFL essays, human-written text receives significantly lower z-scores than the empirical threshold z = 6.0.The experiment evaluates whether the method distinguishes human-written text across a distribution associated with non-native English writing.

5 Conclusion and discussion

The paper presents Unigram-Watermark as a theoretically grounded watermarking approach, while identifying limitations and boundaries for broader applicability and future robustness.

  • Unigram-Watermark targets machine-generated text detection with a rigorous theoretical framework and provable robustness to edits.
  • Most theoretical results extend to K-Gram watermarks with K ≥2, including Type I error bounds and robustness to edits.The Type II error bound does not directly apply for K ≥2.
  • The fixed Green-Red split may not be universally optimal, and performance and robustness can vary with the LLM and generated text.
  • The method is not immune to all possible attacks, motivating future work on more resilient watermarking methods.Future work also includes unifying cryptographic and statistical watermarks.
  • The method differs from concurrent cryptographic watermarking by requiring statistical closeness of each token distribution rather than computational indistinguishability.

B.1 Empirical error rates

Experiments evaluate detection errors, watermark-strength trade-offs, decoding choices, and robustness against paraphrasing and editing attacks across models and datasets.

  • No Type-I errors were observed across GPT2-XL, OPT-1.3B, and LLaMA-7B on OpenGen and LFQA.True positive rates exceeded 0.94 at threshold z = 6.0.
  • Higher watermark strength increased true positive rates but also increased perplexity, indicating a detection-quality trade-off.
  • Beam search produced lower perplexity but shorter, more repetitive sequences that may be less diverse.
  • Unigram-Watermark consistently outperformed KGW+23 across datasets and paraphrasing and editing attack scenarios.

B.4.1 Estimating the Green List tokens

The experiments test whether adversaries can estimate the fixed green list and evade detection through synonym replacement or related attacks.

  • The green-list estimation attack compares token frequencies in watermarked and human text distributions.
  • The evaluation uses LLaMA-13B watermarked outputs generated from LFQA and OpenGen prompts, alongside three simulated human datasets.The human datasets are same-prompt responses, C4, and non-native TOEFL essays.
  • The estimated green list supports non-trivial inferences but remains difficult to determine with certainty.The difficulty is greater for smaller watermark strengths and more esoteric contexts.
  • Even with known green-list tokens, synonym replacement was difficult to evade detection and substantially reduced text quality.
  • Supplementary tests found that the method remained effective on LLaMA-13B and LLaMA-65B, with LLaMA-65B evaluated on 100 sentences.

B.6 Results for deduplicated detection

The paper evaluates the “Unique” detector as an alternative approach for deduplicated detection and presents its associated detection results.

  • The “Unique” detector is designed to improve detection robustness and simplify control of false positives.
  • Table 8 reports deduplicated detection results using true positive rate at 1% false positive rate.
  • The theoretical section certifies quality, correctness, and security properties for the Unigram-Watermark scheme.

C.1 Quality guarantees

The quality analysis bounds how much watermarking changes the language model’s token distribution. Using bounded-range analysis, the paper derives Rényi-divergence guarantees that imply KL-divergence, total-variation, and indistinguishability guarantees.

  • Distributional utility: The results cover the entire Rényi-divergence family and imply guarantees in Kullback-Leibler divergence and Total Variation-distance.Rényi divergence converges to KL-divergence as α →1, while α = 0.5 provides an upper bound for TV-distance.
  • Per-step quality guarantees: Theorem 3.1 bounds the α-th order Rényi-divergence between watermarked and original token distributions at each generation step.The bound applies for any history h, fixed green list G, and watermark strength δ.
  • Distributional utility: The watermarked and original distributions are 2δ-close in max-divergence, corresponding to (ϵ, ˜δ)-indistinguishability with ϵ = 2δ and ˜δ = 0.The paper relates this two-distribution guarantee to differential privacy terminology.
  • Per-step quality guarantees: The watermark satisfies δ-BoundedRange because its logit changes are monotonic, linking the construction to differential-privacy analysis.This connection yields a Rényi-divergence bound for the watermarked and original distributions.
  • Distributional utility: When α = 1, the KL-divergence satisfies DKL(ˆp∥p) ≤δ2.The paper frames this as a direct utility guarantee beyond perplexity.
  • Sequence-level utility: For any prompt x, the paper extends the divergence analysis from individual factors to the probability distributions of complete watermarked and original sequences.The proof uses autoregressive decomposition and adaptive composition for Rényi-divergence.

C.2 Robustness / Security guarantees

The robustness analysis quantifies how bounded text editing changes the watermark detector’s z-score. Under an edit-distance constraint, the modified text retains a lower-bounded score relative to the original watermarked sequence.

  • Robustness to editing: Under edit distance η < n, the modified text’s z-score satisfies zu ≥zy −max{(1 + γ/2)η √n , (1 −γ/2)η √n −η }.Here η is the edit distance between the original watermarked sequence and the modified text.
  • Robustness to editing: When η ≤ 2γn (1+γ/2)2, the second term in the maximum can be dropped.This gives a simpler robustness expression in the stated low-edit regime.
  • Proof strategy: The proof bounds score degradation by analyzing a bivariate function with Taylor’s theorem and optimizing over token-count changes.The optimization considers the possible signs and endpoint choices of the edit-induced changes.
  • Proof strategy: The resulting bound compares three candidate terms before selecting their maximum as the worst-case score loss.The proof collects the cases into max{(1 + γ/2)k √y , k √y , (1 −γ/2)k √y −k }.
  • Robustness to editing: Each insertion, deletion, or edit can alter at most one token’s green-list membership and change sequence length by at most the number of edits.This reduction connects bounded edit distance to the detector-score bound.
  • Security implications: The robustness theorem is used to derive corresponding security guarantees for the watermark.The paper explicitly connects the robustness result to its security corollary.

C.3 No false positive (Type I error guarantees)

Theorem C.4 provides false-positive guarantees for sufficiently diverse suspect texts, without assumptions on how those texts were generated. The analysis also identifies diversity conditions needed for meaningful Type I error bounds and establishes compatible detection guarantees.

  • Theorem C.4 applies to any fixed suspect text generated independently of the secret partition, including human text and arbitrary decoding procedures.The result does not assume a particular generation process.
  • The expected number of green-list tokens is γn, and the corresponding z-score has zero conditional expectation.
  • Sufficient diversity is required because nearly deterministic sequences can produce no meaningful Type I error bound.For repeated-token outputs, the green-token count can be either n or 0, preventing concentration around γn.
  • Choosing τ above the stated threshold yields false-positive rate below α, with Type I error decreasing exponentially as τ increases.V and Cmax can be computed from the suspect text, enabling an input-dependent threshold while preserving the α guarantee.
  • Under the paper’s entropy and homophily conditions, the watermark produces more than γn green-list tokens and supports high-probability true detection.
  • The required sample complexity n ≳ 1/δ2 is information-theoretically optimal up to a logarithmic factor in δ.

D.2 Security property of Kirchenbauer et al. [2023]

The paper shows that the baseline soft watermark’s prefix-dependent bigram structure is more vulnerable to editing. Each edit can alter up to two bigrams, doubling the maximum perturbation relative to Unigram-Watermark.

  • Theorem D.1 bounds the baseline’s post-edit z-score after an adversary performs up to η edits.
  • The baseline therefore suffers a maximum perturbation of 2η in its green-token count, compared with η for the proposed scheme.
  • Each insertion, deletion, or replacement can modify at most two bigrams in the baseline watermark’s sequence representation.
  • Unigram-Watermark is twice as robust to edits as Kirchenbauer et al.’s baseline because its fixed split avoids prefix-dependent bigram changes.

E Alternative detector “Unique” and its desirable properties

The alternative detector applies the existing detection algorithm to a deduplicated token sequence, yielding cleaner Type I error bounds and robustness properties. Experiments and attack analyses examine false-positive control and resilience to several adversarial strategies.

  • Robustness and extensions: Theoretical analysis supports using deduplicated text for Type I error, edit robustness, and the K-gram extension with K ≥2.For edits, changing one token in y changes one token in Unique(y); the same deduplication idea extends to K-gram watermarks, although the Type II bound is deferred.
  • Alternative detection “Unique”: Algorithm 4 detects watermarking by applying Algorithm 2 to Unique(y), the deduplicated suspect text.The alternative detector takes suspect text y, detection key k, and threshold τ, then returns Algorithm 2 on Unique(y).
  • Type I error: Deduplication reduces the suspect length but improves the finite-sample Type I error bound by setting both Cmax and V to 1.For a fixed suspect text, m = |Unique(y)| may be smaller than n, while the resulting bound becomes cleaner.
  • False-positive control: The empirical false positive rate aligns well with the theoretical α across 6,200 unwatermarked samples, varied lengths, and multiple green-list initializations.The evaluation uses diverse negative datasets and dynamic thresholds τ with different α values; Figure 5 compares empirical and theoretical false-positive rates.
  • Attack robustness: The Emoji attack becomes an edit distance of 1 on Unique(y), while the Alphabet attack preserves Type I error and only slightly reduces detection power when independent of the secret key.The Alphabet attack leaves m/2 injected tokens unwatermarked, with an expected mγ/2 green tokens among them.
  • Attack limitations: A secret-codebook steganography attack can break the watermark, but it requires heavy language-model deviation and is likely to reduce generated-text quality.The attack swaps vocabulary tokens using a codebook that can later be inverted by a knowledgeable user.
Loading 2306.17439v2…