Robust Distortion-free Watermarks for Language Models

1 Introduction

• The paper targets provenance of generated text through watermarks that preserve the sampling distribution, remain detectable without the model or prompt, and withstand perturbations.The protocol uses a trusted provider, an untrusted user, and a detector coordinating through a shared key.Source: §1 · p. 1, Figure 1 · p. 2

1.1 Related work

• Prior watermarks distort sampling distributions or break under edits, whereas the proposed approach claims all three desiderata; related methods include linguistic steganography, hashing-based watermarks, and synthetic-text classifiers.Kirchenbauer et al. [13] and Aaronson bias k-grams and lose robustness as k grows; Christ et al. [5] preserve distribution more closely but remain vulnerable to block edits, while classifiers lack distribution-free significance guarantees.Source: §1 · pp. 2–3, §1.1 · pp. 4–5

1 Introduction

• The method maps watermark-key random numbers deterministically to language-model samples, then detects text by aligning it with the corresponding key sequence using a model- and prompt-agnostic statistic.Detection computes a p-value for the null hypothesis that the text is independent of the watermark key sequence.Source: §1 · p. 2
• Robust sequence alignment and alignment costs let detection survive edits, cropping, and even a small corrupted watermarked block embedded in larger text.The paper notes that rewriting text from scratch or regenerating it with another language model can still evade detection, so evasion effort should remain comparable to ordinary text production.Source: §1 · pp. 2–3
• The shift-generate wrapper randomly selects key-sequence subsequences, preventing deterministic repetition while retaining statistical power and joint indistinguishability from regular model calls when key elements are not reused.Statistical power improves exponentially with watermarked-text length and decreases only linearly with random-sequence length.Source: §1 · p. 3
• p ≤0.01 detection remains reliable from 35 tokens after 40–50% random edits for OPT-1.3B and LLaMA-7B, while about 25% of Alpaca-7B responses are detectable and less robust to paraphrasing.The exponential-minimum-sampling watermark is the strongest instantiation; Alpaca-7B detectable responses have a median length of about 100 tokens.Source: §1 · p. 3

2.1 Protocol details

• The protocol generates text autoregressively from a shared watermark key and tests whether published text depends on that key using a non-asymptotic permutation-test p-value.Under the null of key-independent text, the detector’s p-value is uniformly distributed over its finite support; alignment searches for low-cost matches between text and key subsequences.Source: §2.1 · pp. 5–6
• Distortion-free decoding guarantees that each generated token has the original language-model conditional distribution, provided the key sequence is not reused during generation.Thus, using the key as decoder randomness differs from ordinary sampling only through the key’s role as an input to generation.Source: §2.1 · pp. 5–6

2.2 Handling multiple queries

• For T queries of at most m tokens, randomized key shifts achieve negligible distortion when n = ω(mT^2), while detection cost grows with the target query count.The shift wrapper avoids persistent state and supports many distinct outputs before key subsequences are reused.Source: §2.2 · p. 8

2.3 Terminology: watermark strategies and watermark potential

• Watermark potential governs statistical power: deterministic models have zero potential and cannot support reliable distortion-free detection, whereas higher-entropy models permit stronger discrimination.A general lower bound shows classification error worsens as watermark potential approaches zero, while the analyzed p-value bounds improve exponentially with text length and decay at most linearly with key length.Source: §2.3 · pp. 9–10

2.4 Watermarking via inverse transform sampling

• Inverse-transform sampling uses uniform variables and vocabulary permutations to produce distortion-free samples while making permuted token indices correlate with the key for detection.For nonwatermarked text, the permuted indices are i.i.d. uniform and therefore do not correlate with the uniform key variables.Source: §2.4 · p. 10

2.4.1 Robustness to substitutions, insertions and deletions

• Inverse-transform watermarks retain low-p-value detectability after substitutions because unchanged tokens preserve positive key correlation while substituted tokens contribute only O(1/N) negative correlation.The result extends to replacing most tokens, provided the remaining tokens retain watermark potential bounded away from zero.Source: §2.4.1 · p. 11, Then almost surely · p. 12

Then almost surely

• The analysis requires γ = Ω(1/ε) to detect a watermarked substring after corruption within edit distance εk, and its expected p-value bound is vacuous when ε = Ω(1/log k).In practice, smaller values of γ (γ < 1) perform significantly better.Source: Then almost surely · p. 13

2.4.2 What we run in practice

• In practice, ITS uses one random permutation and a modified alignment cost, preserving distortion-freeness and valid p-values despite the loss of the lemmas’ independence assumptions.The practical variants are ITS and ITS-edit, with ITS-edit replacing the test statistic’s alignment cost by the simplified Levenshtein cost.Source: §2.4.2 · pp. 13–14

2.5 Watermarking via exponential minimum sampling

• Exponential minimum sampling provides an alternative distortion-free watermark: its decoder is distortion-free with respect to a uniformly random key, and its alignment statistic supports p-value bounds through concentration.The analysis characterizes the expected alignment-cost difference using watermark potential and extends the bound to subsequences.Source: §2.5 · pp. 14–15

2.5.1 Robustness to corruptions

• For exponential-minimum sampling, high-probability guarantees under substitutions or insertions are not proved because the alignment-metric summands are unbounded.The authors note that truncating the summands could enable analogous results, but leave this analysis undone because the main intuition would remain unchanged.Source: §2.5.1 · p. 15

2.5.2 What we run in practice

• The practical exponential-minimum variants are EXP and EXP-edit, differing only in whether the test statistic uses the standard or simplified Levenshtein alignment cost.EXP uses the decoder from equation (4), the practical alignment cost from equation (6), and a uniform key over Ξ^n; EXP-edit uses Definition 5’s Levenshtein cost.Source: §2.5.2 · p. 15

3.1 Varying text and watermark key length

• EXP watermarks require roughly two to three times fewer tokens than ITS for comparably low median p-values, while ITS and EXP slightly outperform KGW-1.0 and KGW-2.0, respectively.All strategies perform worse on LLaMA-7B than OPT-1.3B because LLaMA-7B produces lower-entropy text; KGW p-values are occasionally unstable for short texts.Source: §3.1 · p. 17, Figure 2 · p. 17
• Increasing the watermark key length n raises p-values approximately linearly, but the penalty decreases rapidly with text length: at n = 4096, only 4–8 extra EXP tokens or 10–20 extra ITS tokens match n = 64 power.The experiments use n = 256 for robustness tests, preserving the distortion-free guarantee while limiting computational overhead.Source: §3.1 · pp. 17–18, §3.2 · p. 18

3.2 Robustness to corruption and paraphrasing

• EXP-edit is far more robust than EXP to insertion and deletion errors, while both are comparably robust to substitutions and outperform KGW-2.0 under substitution attacks.For roundtrip translation, Russian is more effective than French: only EXP-edit remains reliably detectable at p < 0.05 across text lengths, while EXP and KGW-2.0 can stagnate or weaken as texts lengthen.Source: §3.2 · p. 19, Figure 4 · p. 19

3.3 Case study: instruction following

• Alpaca-7B has average per-token watermark potential 0.28 versus 0.59 for LLaMA-7B and 0.67 for OPT-1.3B, and KGW-2.0 outperforms EXP-edit because its distributional distortion raises watermark potential.Responses with unnormalized watermark potential above roughly 60 tend to yield p-values close to zero, while French and Russian roundtrip translation reduce both watermarks’ power.Source: §3.3 · pp. 21, 23, Figure 10 · p. 23, Figure 11 · p. 24
• Hashing previous tokens can make Alpaca-7B list responses repetitive, and even k = 4 can remain repetitive while allowing 20% token replacement to evade detection.The authors describe a direct trade-off between hash robustness and distortion-freeness, motivating the distortion-free watermark design.Source: §3.3 · p. 23

4 Discussion

• Robust sequence alignment enables distortion-free watermarks that tolerate editing or cropping; statistical power improves exponentially with text length but declines linearly with watermark-key length.The approach aligns putative watermarked text with the key sequence used during generation.Source: §4 · p. 26
• Watermarking requires the provider and detector to share a key and trust faithful application, while unreleased model weights remain necessary under current schemes.Planting robust watermarks directly into model weights without degrading quality is identified as future work.Source: §4 · p. 26

4.1 Trade-offs among watermarks

• Alignment avoids hashing’s distortion–robustness trade-off but makes detection complexity grow linearly with key length, which also caps distortion-free token generation.Hashing-based methods instead depend essentially on input-text length, while key reuse across queries creates additional limits.Source: §4.1 · p. 26
• For m = 100 tokens across T = 10 queries, n = 10000 yields runtimes of 0.004, 0.60, 2.20, and 3.21 seconds for ITS, ITS-edit, EXP, and EXP-edit.The runtimes are reported for implementations of the corresponding test statistics; approximate p-values can avoid recomputation for each resampled key.Source: §4.1 · p. 26
• Hashing-based watermarks would need large windows for approximate distortion-freeness; with Alpaca-7B entropy h ≈0.70, they would not withstand replacing more than roughly 10% of tokens.The typical window size is described as k ≈log mT h in the supplied passage.Source: §4.1 · p. 27

4.2 Recommendations in practice and combining watermarks

• Practitioners should use EXP-edit for robustness, ITS for high-throughput detection, and may combine schemes to trade precision against recall or improve resistance to removal and spoofing.A small key sequence such as n = 256 reportedly preserves quality while enabling fast detection and improved robustness; combined schemes remain approximately distortion-free.Source: §4.2 · p. 27

• The proof first lower-bounds the probability that Y = Y′.Source: A Proof of Lemma 2.2 · p. 30
• Using exp(−cx) ≤ 1 − x for 0 ≤ x ≤ 1 − exp(−c/2), it bounds the total variation distance between (Y, ξ) and (Y′, ξ).Source: A Proof of Lemma 2.2 · p. 30
• For any event A, the proof combines the preceding bounds to compare probabilities under the two joint distributions.Source: A Proof of Lemma 2.2 · p. 30
• The desired result follows by taking A to be the event that h predicts −1.Source: A Proof of Lemma 2.2 · p. 30

B Analysis of inverse transform sampling

• The core result is Cov(U, η(π(Y)) | Y) = C0(1 − μ(Y)) almost surely for inverse transform sampling.Here C0 is the variance of η under a uniformly random index, with η(i) = (i − 1)/(N − 1).Source: B Analysis of inverse transform sampling · p. 31
• The conditional distributions are obtained by applying Bayes’ formula, the decoder definition, and the fact that the interval I(Y, π) lies within [0, 1].These steps establish the uniform conditional laws used in the covariance calculation.Source: B Analysis of inverse transform sampling · p. 31
• Conditioned on Y, the random permutation π remains uniform, while U conditioned on π and Y is uniform over an interval of width μ(Y).The interval is I(Y, π) = [μ({y : π(y) < π(Y)}), μ({y : π(y) ≤ π(Y)})].Source: B Analysis of inverse transform sampling · p. 31
• Symmetry gives E[U] = E[η(π(Y))] = 1/2, allowing the conditional covariance to be expressed through centered products.The first equality uses symmetry of P(Y | U) under U and 1 − U; the second uses uniformity of π conditioned on Y.Source: B Analysis of inverse transform sampling · p. 31
• The covariance identity follows by marginalizing over π(Y), using π(Y) | Y ∼ Unif([N]) and the definition of C0.This completes the proof of Lemma B.1.Source: B Analysis of inverse transform sampling · p. 31

B.1 Proof of Lemma 2.3

• In the proof of Lemma 2.3, Lemma B.1 gives E[d(Y_i, ξ_i) | Y] = −C0 · (1 − p(Y_i | Y:i−1)), while independence gives E[d(Y_i, ξ′_j) | Y] = 0.The result then follows immediately from these two conditional expectations.Source: §B.1 · p. 31

Generalized lemma

• The proof first states a general lemma for generation length m, key length n ≥ m, block size k ≤ m, and a conditionally independent substring eY of length at least k.The setup uses decoder Γ, alignment score d, and test statistic ϕ as defined in the paper.Source: §B.2 · p. 32

Proof

• Conditional independence and Lemma 2.3 yield the expected alignment-score separation needed for each cyclic key offset j.The separation is expressed through the block-size-dependent term kC0bα.Source: §B.2 · p. 32
• Hoeffding’s inequality controls each offset because summands lie in [-1/4, 1/4], and a union bound over all n offsets completes the main claim.The proof also uses conditional independence of (Ui, πi) from the remaining pairs given Y.Source: §B.2 · p. 32

B.3 Proof of Lemma 2.5

• Observation B.1 shows that, for an incorrect token, the conditional covariance with its permuted rank is the negative 1/(N−1) multiple of the covariance for the true token.This follows because the incorrect token’s permuted rank is uniform over all ranks except the true token’s rank, while an auxiliary rank variable is independent of Y and U.Source: §B.3 · p. 32
• Combining Lemma 2.3 with Observation B.1 shows that each substituted token contributes mC_0e^α(Y,eY) to the relevant expectation difference.The proof adds the two component results to account for the influence of every substituted token.Source: §B.3 · p. 33
• A concentration argument gives d(eY,ξ1:m)−E[d(eY,ξ1:m)] ≥ me^α(Y,eY)/2 conditionally on eY and Y, and a union bound over j∈[n] completes the claim.The final step uses the test statistic from Algorithm 3 and the assumption k=m.Source: §B.3 · p. 33

B.4 Proof of Lemma 2.6

• The edit distance d_edit(y, ỹ) equals the minimum number of insertions and deletions needed to transform y into ỹ.This is proved by induction on len(y) + len(ỹ), considering the recursive definition’s three cases.Source: §B.4 · p. 33
• For any split position, edit operations decompose across the prefix and suffix, enabling substring-level control under perturbations.The proof partitions an edit sequence according to whether operations affect y:τ or yτ+1:.Source: §B.4 · p. 33
• The alignment distance satisfies d_γ(y, ξ) ≤ γd_edit(y, ỹ) + d_γ(ỹ, ξ), so each insertion or deletion incurs at most γ additional cost.The argument proves the one-edit case and sums the bound over a shortest edit sequence.Source: §B.4 · p. 34
• Under d_edit(Y, Ỹ) ≤ εm, substring and concentration arguments yield a lower bound on the test statistic after perturbation, with failure probability controlled by a union bound.The proof bounds candidate edited strings through neighborhood cardinality and obtains an exponential concentration term multiplied by mn(2k)^{k/(4γ−1)}.Source: §B.4 · pp. 35–36

C Analysis of exponential minimum sampling

• For exponential minimum sampling, −log(ξ_y)/µ(y) has an exponential distribution with rate µ(y), establishing the sampling identity for each y.The proof uses the density of −log(ξ_y)/µ(y), namely µ(y) exp(−µ(y)u).Source: C Analysis of exponential minimum… · pp. 36–37

C.1 Proof of Theorem 2

• The proof of Theorem 2 integrates Lemma C.1 over t ≥ 0 to obtain the stated result.No additional argument beyond this integration is supplied in the passage.Source: §C.1 · p. 37

C.2 Proof of Lemma 2.7

• Lemma C.1 implies −log(ξ_i)/p(Y_i | Y_<i) conditioned on Y is Exp(1), yielding E[−log(ξ_i) | Y] = p(Y_i | Y_<i).Together with the corresponding expectation for ξ′ and α(Y_{i−1:i}) = 1 − p(Y_i | Y_{i−1}), this proves Lemma 2.7.Source: §C.2 · p. 37

C.3 Proof of Lemma 2.8

• The proof derives Lemma 2.8 from a general result for aligned watermark scores under conditional independence, subexponential bounds, and a union bound over the watermark key positions.The argument models relevant exponential variables as (2, 2)-subexponential and applies a Chernoff bound before aggregating across all n positions.Source: §C.3 · pp. 37–38

D.1 Experimental protocol

• Experiments generate token sequences from news-like C4 prompts, round-trip text through each tokenizer, pad when needed, and detect using at most m tokens.Prompts contain at least 50 tokens; generation adds 20 buffer tokens generally and 100 in Experiment 5 to accommodate deletions.Source: §D.1 · p. 39

D.2 Roundtrip translation

• Experiment 6 evaluates robustness using English–French–English and English–Russian–English translations from OPUS-MT models.The setup uses the listed Helsinki-NLP translation models hosted on Hugging Face Hub.Source: §D.2 · p. 39

D.3 Computing p-values

• Fixed reference distributions from news-like C4 text provide p-values across Experiments 1–6, whose nonwatermarked p-values are roughly uniform on [0, 1] except for discreteness in KGW-1.0 and KGW-2.0.The reference distribution is constructed with Algorithm 6, while Algorithm 5 gives the corresponding detector using the fixed distribution.Source: §D.3 · pp. 39–40

D.4 Hyperparameter tuning

• Setting γ balances robustness and statistical power: smaller γ improves insertion/deletion robustness but can reduce power for large key lengths, motivating γ = 0.4 for ITS-edit and γ = 0.0 for EXP-edit.The experiments fix k = m and use fixed alignment scores, varying γ only for ITS-edit and EXP-edit.Source: §D.4 · p. 43, Figure 21 · p. 43, Figure 22 · p. 44

• The experiment measures median p-value against the fraction of substitution errors for OPT-1.3B and LLaMA 7B with m = 35.Source: Figure 23 · p. 44
• A corresponding evaluation reports median p-value against substitution-error fraction for OPT-1.3B and LLaMA 7B with m = 70.Source: Figure 24 · p. 45
• Another figure presents the same median-p-value analysis versus substitution errors for OPT-1.3B and LLaMA 7B with m = 70.Source: Figure 25 · p. 45

D.5.2 Experiment 4

• Median p-values are evaluated against the fraction of insertion errors for OPT-1.3B and LLaMA 7B with m = 35.Source: Figure 26 · p. 46
• Median p-values are also evaluated against the fraction of insertion errors for OPT-1.3B and LLaMA 7B with m = 70.Source: Figure 27 · p. 46, Figure 28 · p. 47

• The experiment measures median p-value as a function of deletion-error fraction for OPT-1.3B and LLaMA 7B with m = 35.Source: Figure 29 · p. 47
• A corresponding analysis evaluates median p-value versus deletion-error fraction for OPT-1.3B and LLaMA 7B with m = 70.Source: Figure 30 · p. 48
• Another figure reports the same median-p-value analysis against deletion-error fraction for OPT-1.3B and LLaMA 7B with m = 70.Source: Figure 31 · p. 48

Experiment 6

• The experiment measures median p-value as insertion errors increase after roundtrip translation via French for OPT-1.3B and LLaMA 7B.Both models use m = 35.Source: Figure 32 · p. 49
• Together, the figures assess robustness under translation-induced insertion errors and varying text length.Source: Figure 32 · p. 49, Figure 33 · p. 49
• It also measures median p-value across text lengths after roundtrip translation via Russian for the same models and m = 35.Source: Figure 33 · p. 49

Instruction prompts

• The study tests three list-style instructions: generating paper-title ideas, startup names, and movie lists, for which hashing can produce worse responses than regular model samples.Each instruction requests 20 items and is formatted according to Taori et al..Source: §D.5.5 · p. 49

Experimental setup

• The comparison includes EXP, KGW-2.0, and EXP-hash, using five random seeds for EXP and KGW-2.0 and five hash functions for EXP-hash.EXP-hash is evaluated with k = 1 and k = 4; KGW-2.0 hashes only the previous token because its public implementation lacks longer-context hashing.Source: §D.5.5 · p. 50

Qualitative response quality

• EXP-hash with k = 1 often produces qualitatively worse, repetitive responses, whereas k = 4 makes repetition substantially less noticeable but does not eliminate it.The comparison uses title-generation responses and includes sample sheets for the first instruction.Source: §D.5.5 · p. 50, Table 1 · p. 52

Method comparison

• KGW-2.0 shows less noticeable repetition than EXP-hash even when hashing only the previous token, likely because it biases token probabilities while retaining random sampling.This stochasticity comes with a performance tradeoff: KGW-2.0 was generally less powerful than EXP and EXP-edit in other experiments.Source: §D.5.5 · p. 50

Response examples

• The cited passages present multiple separate lists of proposed titles concerning watermarking, language-model security, traceability, transparency, attribution, and related themes.Source: §D.5.5 · pp. 53, 55, 57, 58