Debiasing Watermarks for Large Language Models via Maximal Coupling

1 Introduction

• The method targets a practical weakness of prior green-list and Gumbel-max schemes: restricting or deterministically selecting tokens can distort distributions, degrade quality, or produce repetitive text.The proposed decoder retains stochastic sampling while using pseudorandomness for watermark detection.Source: §1 · p. 2
• Maximal coupling combines an alternative green-list distribution with the original NTP distribution, producing an inherently unbiased stochastic decoder.The decoder samples from an overlap distribution or an excess distribution according to a uniform random variable, so sampled tokens follow the original distribution.Source: §1 · p. 3
• The watermark key shares the green list and random variable with the detector, whose test distinguishes human text from watermarked text through the conditional distribution of those variables.Under H0, the variables are i.i.d. uniform; under H1, they follow a distribution truncated by the green-token probability.Source: §1 · p. 3
• When users add, delete, or substitute tokens, the resulting mixture alternative weakens the watermark signal and motivates sparse-detection analysis.The paper studies regimes where the modified-token fraction and watermark strength decay with text length.Source: §1 · p. 3
• Without sufficient signal, specifically p + 2q > 1, the null and mixture alternatives merge asymptotically, so reliable detection is impossible.With sufficient signal, p + 2q < 1, the hypotheses separate asymptotically; likelihood-ratio testing and higher criticism can detect the watermark.Source: §1 · p. 4
• Higher criticism reaches the optimal detection boundary p + 2q = 1 without knowing Pt or εn, while the sum test has boundary p + q = 0.5 but is more robust for short texts.The paper also reports retained watermark signal under targeted text refinement and fewer modifications than Aaronson and Kirchner (2023).Source: §1 · p. 4

2 Preliminaries

• Prior green-list soft watermarking favors green tokens through exponential reweighting, whereas the proposed approach uses maximal coupling to avoid distributional bias.The related-work discussion characterizes earlier schemes as biased and defines the target property of unbiasedness.Source: §2 · pp. 4–5
• An unbiased decoder satisfies PS,ξ(S(P, ξ) = w) = Pw for every next-token distribution P and token w.This definition requires the decoder’s marginal output distribution to equal the original NTP distribution despite watermark randomness.Source: §2 · p. 5
• Deterministic watermark decoders can become repetitive when pseudorandom variables depend on prior tokens, while the proposed stochastic decoder uses additional randomness and avoids delicate hyperparameter tuning.The paper also claims higher detection power than a permutation-based unbiased scheme.Source: §2 · p. 5
• Maximal coupling samples from the overlap of P and Q or from the excess of P over Q, using a uniform variable to choose between these components.Algorithm 1 applies min(P, Q) and max(0, P − Q) element-wise.Source: §2 · p. 5
• For any distributions P and Q, maximal-coupling sampling returns w ∼ P, establishing preservation of the original distribution.This property is formalized in Lemma 2.2.Source: §2 · p. 6

3.1 Decoding

• The decoder constructs Qt and samples via maximal coupling, yielding an unbiased decoding scheme while embedding a signal in the shared pseudorandom variables.The process uses green lists, uniform variables, and maximal coupling at each generation step.Source: §3.1 · pp. 6–7
• The method directly extends binary watermarking to large vocabularies by treating green and red tokens as two categories without bit-level probability decomposition.This avoids manually encoding large-vocabulary token probabilities into binary strings.Source: §3.1 · p. 7

3.2 Detection

• Detection models unmodified text as i.i.d. uniform ζt values and watermarked text as values drawn from U[0, Pt,Gt], with substitution attacks producing sparse mixtures of these distributions.The sparse-mixture formulation represents only an εm fraction of variables as retaining watermark signal after modification.Source: §3.2 · p. 8
• Detection becomes impossible or loses power when watermark presence is too sparse or green-token probability is too close to 1.In these regimes, the watermark-conditioned distribution approaches the null uniform distribution, or the hypotheses merge asymptotically.Source: §3.2 · pp. 8–10
• Under Pt,Gt ≤ 1 − m−q, likelihood-ratio and sum tests asymptotically distinguish the hypotheses when q + 2p < 1 and q + p < 1/2, respectively.Higher criticism matches likelihood-ratio power and is adaptively optimal when q + 2p < 1; its type-I and type-II errors tend to 0 as m →∞.Source: §3.2 · pp. 8–9

3.3 Watermark Key

• The practical key uses pseudorandom functions over prior k-token contexts, while scoring unique (k + 1)-tuples avoids double-counting and captures valid stochastic-decoding signals.The paper reports that this scoring scheme improves true positive rates while maintaining accurate false positive estimates.Source: §3.3 · pp. 10–11

3.4 Interpret Speculative Decoding as Post-processing

• Speculative decoding provides a post-processing model in which a larger target model makes targeted modifications to draft-model text, enabling robustness analysis under quality-improving edits.The setup treats the draft model as the watermarked generator and the target model as the modifier.Source: §3.4 · p. 11

Simulation Setup

• The simulations vary signal proportion and strength under strong- and weak-signal settings to assess when the sum test and HC detect the watermark.Weak-signal experiments set Pt,Gt = 1 −m−q and evaluate rejection rates using repeated null and alternative simulations.Source: §4 · pp. 11–12

The First Regime: Strong Signal

• In the strong-signal regime, both tests’ power converges to 1 for small p but vanishes as p increases into the undetectable region.With p = 0.75 and r = 0.2, the condition 2p − r = 1.2 > 1 makes detection impossible.Source: §4 · p. 12, Figure 1 · p. 12

Scenario 3: On the boundary p + q = 1/2

• On the p + q = 1/2 boundary, the sum test remains around 0.3 power while HC approaches 1 more slowly as p increases.As p increases, the proportion of watermarked tokens decreases, making HC more sensitive to signal sparsity than signal strength.Source: §4 · p. 13, Figure 5 · p. 15

Second Regime: Weak Signal

• HC reaches power 1 while the sum test declines past p + q = 1/2, but both tests’ power vanishes at 2p + q = 1.These patterns occur across weak-signal scenarios and match the predicted detection boundaries.Source: §4 · pp. 13–14, Figure 3 · p. 14

Simulation Setup

• Across weak-signal scenarios, the sum test often outperforms HC when the number of green tokens is relatively small, with log10 m ≤3.The simulations use m from 10^2 to 10^5 and significance level α = 0.01.Source: §4 · pp. 12, 14

Scenario 2: Fix q and vary p

• In scenario 2, at p + q = 1/2, the sum test’s power hovers around 0.3 while HC’s power increases to 1; toward 2p + q = 1, both powers trend toward zero.Source: Figure 4 · p. 15

Setup

• The experiments use Phi-3 instruction-tuned models on ELI5 and FinQA, evaluate S-BERT similarity and TPR before and after attacks, and include a 14B target model for speculative decoding.All methods use comparable green-list settings, exact-null p-values with a 0.01 threshold, and repeated context masking where applicable.Source: §5 · pp. 15–16

Comparison against Baselines

• The proposed method often achieves more competitive TPR than green/red list and DiPmark methods at similar S-BERT similarity, including substitution and paraphrasing attacks.Gumbel-max shows consistently lower S-BERT scores because its practical pseudorandomness is compromised by deterministic decoding from preceding tokens.Source: §5 · p. 17, Table 1 · p. 17

Text Repetition

• 18.61% token repetition for Gumbel-max versus 16.77–17.80% for other methods on FinQA with k = 2, while the stochastic decoder reduces repetitive patterns.Repeated context masking does not fully prevent repetition in Gumbel-max, whereas added sampling randomness helps the proposed method maintain watermark effectiveness with less repetition.Source: §5 · p. 17, Table 2 · p. 18

Speculative Decoding

• Comparable TPR with a lower rejection rate under speculative decoding indicates that the proposed method requires fewer target-model revisions to improve generated text.The setup models targeted, non-independent edits through draft-token rejection rather than random substitutions.Source: §5 · p. 18, Table 3 · p. 18

Comparison of Test Statistics

• The sum test consistently achieves higher TPR than higher criticism across configurations, especially when the detected text contains relatively few tokens.Simulations and language-model experiments indicate that higher criticism may become more competitive for longer texts.Source: Figure 6 · p. 16, §5 · p. 18, Table 4 · p. 19

6 Conclusions

• Maximal coupling yields a provably unbiased green/red list watermark that is less susceptible to pseudorandomness-induced distortion.The method also reformulates detection as mixture detection and derives asymptotic detection boundaries for sparse watermark signals.Source: §6 · p. 19
• Empirical results show superior preservation of the generation distribution and detection power compared with previous watermarking methods.The conclusion frames the approach as a basis for more robust, model-agnostic watermarking schemes.Source: §6 · p. 19

A.1 Unbiased Watermarking Schemes and Related Works

• Soft green/red list watermarking favors green tokens through reweighting, but randomizing the green list does not eliminate distribution bias.A binary-vocabulary example shows that the resulting distribution can differ from the original model distribution.Source: §A.1 · pp. 22–23
• The bias creates a trade-off between text distortion and detection power, requiring careful tuning of δ, whereas the proposed method is unbiased by construction.The proposed construction therefore avoids this particular parameter-tuning issue.Source: §A.1 · p. 23
• Exponential minimal sampling is unbiased with true randomness, but pseudorandom variables seeded by prior k tokens make decoding deterministic and can produce repetitive, degraded text.Repeated context masking reduces but does not completely address the deterministic decoder’s tendency toward repetitive patterns.Source: §A.1 · pp. 23–24
• Inverse transform sampling can preserve unbiasedness, but existing detectors may have weaker power or require optimization and hyperparameter tuning.The cited methods differ in their detection procedures, including correlation-based tests and optimization-based tests.Source: §A.1 · pp. 23–24
• Distribution-Preserving watermarking uses permutation-based reweighting, but independent α and γ parameters may yield noisy signals and require delicate joint tuning.The reweighting does not necessarily favor every green-list token during generation.Source: §A.1 · p. 24
• Reusing fixed random variables to handle token substitutions, insertions, or deletions is not pursued because multiple-testing effects are unclear and alignment may be computationally expensive.These concerns become more consequential for long received texts.Source: §A.1 · p. 24

A.2 Total Variation Distance and Hellinger Distance

• Total variation and Hellinger distances provide complementary measures for comparing probability measures and their product distributions.The appendix states an inequality relating Hellinger and total variation distances.Source: §A.2 · pp. 24–25
• Hellinger affinity offers a convenient equivalent notation because squared Hellinger distance equals one minus the affinity.The appendix uses affinity to decouple comparisons across product distributions.Source: §A.2 · p. 25
• If product-distribution affinity satisfies Aff(P_1:n, Q_1:n) = 1 + o(1/n), Lemma A.1 gives an asymptotic total-variation bound.The appendix also records conditions involving TV = o(1) and affinity approaching one at a specified rate.Source: §A.2 · p. 25

• The distributions μ and ν are defined from min(P_w,Q_w) and max(0,P_w−Q_w), respectively.Source: §A.2.1 · p. 25
• For w in A, the mixture p·μ(w)+(1−p)·ν(w) equals P_w.Source: §A.2.1 · p. 25
• For w outside A, the residual component is zero, so the same mixture also equals P_w.Source: §A.2.1 · p. 25

• The initial analysis assumes that no modification was made to the generated text.Source: §A.3 · p. 25
• Under H1, each observed ζ_t conditioned on (P_t,G_t) follows a uniform distribution on [0,P_t,G_t].Source: §A.3 · p. 25

Order Statistics

• The test can be expressed as a threshold rule based on the maximum ζ^(m), accepting H0 when ζ^(m)>c′.Source: §A.3.1 · p. 26
• Assuming P_t,G_t=1−δ for every t, the Neyman–Pearson Lemma makes the likelihood-ratio test uniformly most powerful.Source: §A.3.1 · p. 26
• The critical value c′ is selected to satisfy the prescribed significance level α using the distribution of the maximum of m i.i.d. uniform variables.Source: §A.3.1 · p. 26
• With c′=α^(1/m), the test attains the desired significance level.Source: §A.3.1 · p. 26
• For fixed α and δ, increasing m eventually makes c′>1−δ, yielding power equal to 1; when P_t,G_t≤1−δ, the argument provides a power lower bound.Source: §A.3.1 · p. 26

Text Modifications

• The attacker may substitute any generated token without knowing the green lists or the ζ_t values.Source: §A.3.2 · p. 26
• After substitution, the affected ζ_t becomes independent of whether the replacement token belongs to the corresponding green list.Source: §A.3.2 · p. 26
• The resulting sparse signal is modeled by a mixture in which an ε_m fraction retains the watermark distribution while the remainder is uniform on [0,1].Source: §A.3.2 · p. 27
• For simplicity, the analysis treats mε_m as an integer.Source: §A.3.2 · p. 27

A.3.3 Suboptimality of the Order Statistics.

• If ε_m does not converge to 1, the order-statistic test’s power remains bounded away from 1 under substitution attacks.Its power is upper bounded by α^(1−ε_m), so non-negligible modification fractions cause suboptimality.Source: §A.3.3 · p. 27

A.3.6 Sum Test.

• The sum test has vanishing error probabilities when p + q < 1/2, but its power is bounded away from 1 when p + q > 1/2.The first regime follows from a Chebyshev bound using Var_1 s = O(m); in the second, the null mean lies within one alternative standard deviation.Source: §A.3.6 · p. 29

A.3.7 Higher Criticism.

• Higher criticism is analyzed through a normalized uniform empirical process and is shown to satisfy the stated asymptotic control under the null and alternative constructions.The proof compares the empirical process under uniform variables with watermark-induced variables bounded by 1 − m^−q.Source: §A.3.7 · pp. 30–31

A.4 Extension to the Soft Green/Red List Watermark

• The soft watermark preserves red-token sampling, reducing distortion in unfavorable pseudorandom contexts but weakening green-token and red-token watermark signals.The authors state that analogous guarantees to Proposition 3.6 and Theorem 3.7 can still hold under appropriate assumptions.Source: §A.4 · p. 31

A.5 Speculative Decoding

• Speculative decoding uses a draft model to propose lookahead tokens that the target model evaluates in parallel, reverting to autoregressive generation after rejection.The lookahead parameter L controls the number of draft tokens proposed at each step.Source: §A.5 · pp. 31–32

A.5.1 Connections to Maximal Coupling

• With L = 1, speculative sampling is equivalent to maximal coupling, with accepted tokens distributed according to the normalized overlap min(P_w, Q_w).The equivalence follows by resampling rejected tokens from the normalized excess distribution.Source: §A.5.1 · p. 32

A.6 Experiments and Ablations

• The experiments and ablations show that the proposed scheme reduces distortion relative to Gumbel-max while remaining competitive in TPR, and that sum testing is stronger than higher criticism for relatively short texts.The single-green-list ablation reports no significant impact, while the targeted-editing setup models a lazy editor that accepts draft suggestions only with reasonable target-model confidence.Source: §A.6.1 · p. 33, §A.6.3 · pp. 34–35, §A.6.4 · p. 37

A.6.4 A Single Green List

• Using the same green list for all tokens may give adversaries more power to learn the exact generator and produce detector-fooling attacks, an open direction for future work.A larger context window is used to generate ζ, and Zhao et al. (2023) reported an analogous observation for green/red list soft watermarking.Source: §A.6.4 · p. 38