PaperlayerView exact revision on arXiv

Source-linked AI summary

Robust Distortion-free Watermarks for Language Models

Rohith Kuditipudi, John Thickstun, Tatsunori Hashimoto, Percy Liang

arXiv:2307.15593v3cs.LGcs.CLcs.CR

TL;DR

The paper addresses how to attribute language-model text without altering its sampling distribution or losing detection after edits and cropping. It uses keyed randomized generation and sequence-alignment detection, and finds reliable detection under substantial random corruption for OPT-1.3B and LLaMA-7B, while Alpaca-7B responses are harder to detect.

  • Problem

    Existing language-model watermarks either distort sampling distributions or lack robustness to editing and cropping, motivating watermarks that satisfy all three desiderata.

  • Method

    The provider maps keyed random-number sequences to language-model samples, and the detector aligns candidate text with the shared key sequence using robust sequence alignment.

  • Results

    35 tokens remain reliably detectable at p ≤ 0.01 after 40–50% random edits for OPT-1.3B and LLaMA-7B, while around 25% of Alpaca-7B responses are detectable.

  • Takeaways & Limitations

    Exponential minimum sampling is the most powerful tested instantiation, and detection power improves exponentially with text length while diminishing linearly with key-sequence length.

  • Takeaways & Limitations

    Detection is intrinsically limited for deterministic or low-entropy models, and the alignment-based detector’s complexity grows linearly with watermark key-sequence length.

Abstract

from arXiv · show

We propose a methodology for planting watermarks in text from an autoregressive language model that are robust to perturbations without changing the distribution over text up to a certain maximum generation budget. We generate watermarked text by mapping a sequence of random numbers -- which we compute using a randomized watermark key -- to a sample from the language model. To detect watermarked text, any party who knows the key can align the text to the random number sequence. We instantiate our watermark methodology with two sampling schemes: inverse transform sampling and exponential minimum sampling. We apply these watermarks to three language models -- OPT-1.3B, LLaMA-7B and Alpaca-7B -- to experimentally validate their statistical power and robustness to various paraphrasing attacks. Notably, for both the OPT-1.3B and LLaMA-7B models, we find we can reliably detect watermarked text ($p \leq 0.01$) from $35$ tokens even after corrupting between $40$-$50\%$ of the tokens via random edits (i.e., substitutions, insertions or deletions). For the Alpaca-7B model, we conduct a case study on the feasibility of watermarking responses to typical user instructions. Due to the lower entropy of the responses, detection is more difficult: around $25\%$ of the responses -- whose median length is around $100$ tokens -- are detectable with $p \leq 0.01$, and the watermark is also less robust to certain automated paraphrasing attacks we implement.

1 Introduction

The paper develops language-model watermarks that preserve the original text distribution while remaining detectable without the prompt or model and robust to edits. Its approach uses randomized sampling and robust sequence alignment, achieving strong detection under substantial random corruption but weaker performance for lower-entropy instruction responses.

  • Motivation and desiderata: Existing approaches often distort the model’s sampling distribution or fail under editing and cropping, whereas this work targets all three desiderata: distortion-free, agnostic, and robust watermarks.The paper positions its method as the first language-model watermarking strategy to achieve all three properties.
  • Method: The provider maps watermark-key random numbers to language-model samples, while the detector aligns published text with the shared key sequence.Marginalizing over the key sequence, generation remains distributed like sampling from the original language model.
  • Method: Robust sequence alignment supplies the detection statistic, allowing the detector to tolerate edits and cropped prompts without requiring the original prompt.Detection quality is quantified through a watermark-specific alignment cost.
  • Evaluation: Two watermark instantiations use inverse transform sampling and exponential minimum sampling, with exponential minimum sampling performing best across the evaluated models.Experiments cover OPT-1.3B, LLaMA-7B, and Alpaca-7B.
  • Evaluation: 35 tokens suffice for reliable detection at p ≤ 0.01 after 40–50% random token corruption in OPT-1.3B and LLaMA-7B.The corruptions include substitutions, insertions, and deletions; detection also remains possible from 50 tokens after round-trip translation paraphrasing.
  • Evaluation: Around 25% of Alpaca-7B responses are detectable at p ≤ 0.01, with lower entropy making detection more difficult and paraphrasing robustness weaker.These responses have a median length of around 100 tokens.

2 Methodology and theoretical analysis

The methodology maps watermark-key randomness to language-model samples while preserving the model’s sampling distribution, then detects text by aligning it with the shared key. Its theoretical analysis covers agnostic detection, multi-query distortion, statistical power, inverse-transform sampling, and robustness to corruption.

  • Protocol: The protocol shares a random watermark key sequence, uses it to generate language-model text, and aligns putative text with the key for detection.The detector computes a permutation-test p-value for the null hypothesis that the text is independent of the key.
  • Distortion-free generation: The generated tokens retain the original autoregressive sampling distribution when the key sequence is sufficiently long to avoid reuse.The formal result gives Yi ∼ p(· | Y:i−1), while multi-query distortion is negligible when n = ω(mT^2).
  • Theoretical analysis: The watermark strategies combine a distortion-free decoder, an agnostic test statistic, and a key-sequence distribution; their theoretical power improves exponentially with text length and decays at most linearly with key length.The strength of the bounds depends on watermark potential, which is zero for deterministic models and approaches one for high-entropy models.
  • Inverse transform sampling: Inverse transform sampling maps uniform randomness and permutations to tokens, while detection correlates permuted token indices with the same random sequence.For nonwatermarked text, permuted token indices are i.i.d. uniform and do not correlate with the watermark randomness.
  • Statistical power: Watermarked samples with nonzero watermark potential have exponentially small expected p-values as text length increases, while detection complexity grows linearly with key-sequence length.The analysis describes detection from snippets such as 50 tokens while permitting n = 2^Ω(m) total generated tokens.
  • Robustness to corruption: Detection can remain possible after replacing most tokens when the surviving tokens retain watermark potential, because their key-aligned indices remain positively correlated.For heavily corrupted text, block size k < m can improve detection, although the theoretical bound may become vacuous for ε = Ω(1/log k).

3 Experimental results

Experiments evaluate watermark power and robustness across OPT-1.3B, LLaMA-7B, and Alpaca-7B, comparing ITS and EXP variants with KGW baselines under corruption, translation, and instruction-following settings. EXP is generally strongest, while lower-entropy Alpaca responses and some paraphrasing attacks reduce detection power.

  • Experimental setup: Experiments test ITS, ITS-edit, EXP, and EXP-edit on OPT-1.3B and LLaMA-7B, with Alpaca-7B evaluated in an instruction-following case study.The evaluation includes varying text and key lengths, random substitutions, insertions, deletions, and roundtrip translation attacks.
  • Text and key length: EXP watermarks are more powerful than ITS watermarks, requiring roughly two to three times fewer tokens for comparably low median p-values.The comparison uses watermarked continuations with n = 256 and reports median p-values as the significance level at which detector power is at least 0.5.
  • Text and key length: Median p-values grow linearly with watermark key length n but decrease rapidly as watermarked text length m increases.The paper notes that even n = 4096 causes only a mild power penalty that decreases rapidly with m.
  • Robustness to corruption and paraphrasing: Roundtrip translation through Russian is more effective than through French: only EXP-edit reliably detects watermarked text after the Russian attack, whereas French often preserves detectable snippets.The authors caution that they did not verify whether translated texts preserve the original semantics, so robustness may be underestimated.
  • Case study: instruction following: Alpaca-7B responses have lower watermark potential than OPT-1.3B and LLaMA-7B, reducing statistical power despite typically longer responses; KGW-2.0 outperforms EXP-edit in this case study.Average per-token watermark potential is 0.28 for Alpaca-7B, compared with 0.59 for LLaMA-7B and 0.67 for OPT-1.3B; both methods tend to yield p-values close to zero when unnormalized potential exceeds roughly 60.

4 Discussion

The discussion frames robust, distortion-free watermarking as a practical provenance tool while identifying coordination, key-release, and detection-complexity constraints. It recommends different schemes depending on whether robustness or detection throughput matters.

  • The paper claims its watermarks are the first to combine distortion-freeness with robustness to editing and cropping.
  • Watermarking requires the LM provider and detector to share information in advance, such as a watermark key.
  • Releasing model weights remains incompatible with known watermarking methods because users could query the model directly instead of through the provider.
  • Detection complexity grows linearly with watermark key length, creating a new trade-off absent from methods whose complexity mainly depends on input-text length.
  • Hashing-based methods trade reduced distortion against weaker robustness as hash windows grow, while Alpaca-7B makes this limitation especially restrictive.
  • For robustness, the authors recommend EXP-edit; for high-throughput detection, they recommend ITS.

A Proof of Lemma 2.2

This proof establishes the lemma by lower-bounding agreement between two outcomes and then converting that bound into a total-variation bound.

  • The proof first lower-bounds the probability that Y and Y′ are equal.
  • It then bounds the total variation distance between the joint distributions of (Y, ξ) and (Y′, ξ).
  • For any event A, the proof relates probabilities under the two joint distributions using the total-variation bound.
  • The desired result follows by choosing A as the event that h predicts −1.

B Analysis of inverse transform sampling

The analysis characterizes conditional distributions in inverse transform sampling and uses them to derive a covariance identity and an expected alignment-score relation.

  • Lemma B.1 states a conditional covariance identity linking U, the permutation-ranked output, and the probability of Y given the sampling distribution.
  • The proof uses Bayes’ formula and independence to characterize the conditional distributions of π given Y and U given π and Y.
  • The interval I(Y, π) contains the cumulative probability mass associated with the sampled output under permutation π.
  • Conditional on Y, π is uniform over permutations, while U conditional on π and Y is uniform over I(Y, π).
  • Symmetry gives E[U] = E[η(π(Y))] = 1/2, enabling the subsequent covariance calculation.
  • The expected alignment score is negative for watermarked keys and zero for an independent key because the latter is independent of Y.

B.2 Proof of Lemma 2.4

The proof generalizes the lemma to aligned substrings by comparing alignment scores across key offsets and applying concentration bounds.

  • The section proves a more general result from which Lemma 2.4 follows as a corollary.
  • Lemma B.2 considers generation length m, watermark key length n, decoder Γ, alignment score d, and test statistic ϕ with block size k ≤ m.
  • The analyzed substring has length at least k and is conditionally independent of the watermark keys given the generated text.
  • The proof bounds the probability that an independent key achieves an alignment statistic no larger than the true key’s statistic.
  • Hoeffding’s inequality is applied because each summand lies between −1/4 and 1/4 and the coordinate pairs are conditionally independent given Y.
  • A union bound over all j ∈ [n] completes the main claim after applying the preceding comparison.

B.3 Proof of Lemma 2.5

The proof analyzes how a substituted token changes the alignment statistic, then extends the single-token relationship across all positions using a union bound.

  • Single-token analysis: A substituted token induces an inverse covariance relationship between its random variable and the original token’s statistic.The covariance is scaled by -1/(N−1) when the substituted token differs from the original.
  • Position-wise extension: The proof combines the single-token observation with Lemma 2.3 for each position j ∈ [n].The resulting expectation difference is expressed using the quantity eα(Y, eY).
  • Concentration bound: A concentration argument bounds the probability that the observed distance falls below its expected separation.The displayed bound uses a threshold proportional to m eα(Y, eY)/2.
  • Final aggregation: The final claim follows by applying the test-statistic definition and taking a union bound over all j ∈ [n].The proof recalls the assumption k = m when forming the final bound.

B.4 Proof of Lemma 2.6

The proof establishes edit-distance stability of the alignment score and combines this with concentration and union bounds to control detection after insertions or deletions.

  • Edit-distance preliminaries: d_edit(y, ỹ) is the minimum number of insertion or deletion operations needed to transform y into ỹ.This definition underlies the subsequent stability arguments.
  • Substring decomposition: The proof partitions edits around a split point and uses substring relations to transfer the edit-distance bound to prefixes and suffixes.Observation B.3 supplies the decomposition used in the main proof.
  • Edit-distance stability: A single insertion or deletion changes d_γ by at most γ, yielding d_γ(y, ξ) ≤ γd_edit(y, ỹ) + d_γ(ỹ, ξ).The general bound is obtained by summing the one-edit bound over a shortest edit sequence.
  • Final bound: The main result combines the stability displays through another union bound.The proof also invokes concentration after controlling the edit-induced deviation.
  • Neighborhood construction: The set N_β(y) contains strings obtainable from y through at most β insertion or deletion operations.Restricting insertions to a particular token changes d_γ by at most ±1/2.
  • Concentration and union bound: At most (2k)^β candidate strings arise from β edit locations, enabling a union-bound concentration argument.This yields a probability bound with prefactor mn(2k)^{k/(4γ−1)}.

C.3 Proof of Lemma 2.8

The proof derives concentration for the watermark statistic from exponential random variables and applies it to substrings, while the experiments calibrate detection using fixed reference distributions.

  • Lemma setup: Lemma C.2 analyzes a substring eY of a generated sequence Y that is conditionally independent of the watermark keys given Y.The block size satisfies k ≤ m, where m is the generation length.
  • Alignment advantage: The correct key has an expected alignment advantage of k b_α over an independent key.This expectation gap is stated for every alignment index j.
  • Concentration analysis: Exponential random variables provide the concentration ingredients for the detection statistic.The relevant variables are (2,2)-subexponential, allowing a Chernoff bound and a union bound over j ∈ [n].
  • Experimental protocol: Experiments generate text from prompts sampled from the news-like C4 subset, retokenize it, and ensure detection receives at least m tokens.The procedure uses minimum prompt lengths and may add buffer or padding tokens.
  • Reference distribution: P-values are computed with a fixed reference distribution constructed from the news-like C4 text distribution.The reference distribution is built by resampling the test statistic.
  • Calibration check: Nonwatermarked-text p-values are roughly uniform on [0,1], except that KGW-1.0 and KGW-2.0 show deviations from discreteness.This serves as a sanity check for the detectors’ calibration.
  • Hyperparameter effects: Smaller γ values tend to improve robustness to insertion and deletion attacks for ITS-edit and EXP-edit.The experiments vary γ and n under specified token-length settings.

D.5.1 Experiment 3

The experiment compares median p-values under substitution errors for OPT-1.3B and LLaMA 7B at two text lengths.

  • m = 35: The figures plot median p-value against the fraction of substitution errors for OPT-1.3B and LLaMA 7B with m = 35.The comparison is across models as substitution corruption increases.
  • m = 70: The figures also plot median p-value against substitution-error fraction with m = 70.This setting is shown for the same two language models.

D.5.2 Experiment 4

This experiment examines how median detection p-values change with insertion errors for OPT-1.3B and LLaMA 7B at m = 35 and m = 70.

  • Insertion errors: The figures plot median p-value against the fraction of insertion errors for OPT-1.3B and LLaMA 7B.The experiment uses watermark lengths m = 35 and m = 70.

D.5.3 Experiment 5

This experiment examines how median detection p-values change with deletion errors for OPT-1.3B and LLaMA 7B at m = 35 and m = 70.

  • Deletion errors: The figures plot median p-value against the fraction of deletion errors for OPT-1.3B and LLaMA 7B.The experiment uses watermark lengths m = 35 and m = 70.

D.5.4 Experiment 6

This experiment examines median detection p-values after paraphrasing through roundtrip translation, using insertion errors or text length as the varying factor.

  • French roundtrip translation: One figure varies the fraction of insertion errors after roundtrip translation via French for OPT-1.3B and LLaMA 7B with m = 35.The plotted outcome is median p-value of watermarked text.
  • Russian roundtrip translation: Another figure varies text length after roundtrip translation via Russian for OPT-1.3B and LLaMA 7B with m = 35.The plotted outcome is median p-value of watermarked text.

D.5.5 Instruction following case study

The instruction-following case study compares watermarking strategies on typical user prompts, including requests for title ideas, startup names, and movie lists. It reports qualitative response differences among EXP-hash, KGW-2.0, and EXP, with EXP-hash at k = 1 often degenerating into repetition while KGW-2.0 is less repetitive but generally less powerful elsewhere.

  • Instructions: The case study evaluates responses to three instructions: paper-title ideas, startup names, and movie lists.The paper formats each instruction according to Taori et al. before model calls.
  • Compared strategies: The comparison includes regular-equivalent EXP samples, KGW-2.0, and hashing-based EXP variants with k = 1 and k = 4.EXP and EXP-edit use the same generate method, and samples are generated with multiple random seeds or hashes.
  • EXP-hash k = 1: EXP-hash with k = 1 often produces qualitatively worse responses that degenerate into repetition.The paper provides a sample sheet for the paper-title prompt and defers the other two sample sheets to the code release.
  • EXP-hash k = 4: With k = 4, EXP-hash repetition is substantially less noticeable, though it occasionally still manifests.The corresponding paper-title responses are listed in Table 4’s k = 4 sample sheet.
  • KGW-2.0: KGW-2.0 shows less noticeable repetition than EXP-hash with k = 1, but is generally less powerful than EXP and EXP-edit in other experiments.The paper attributes this difference speculatively to KGW-2.0’s stochastic sampling after distribution biasing.
Loading 2307.15593v3…