PaperlayerView exact revision on arXiv

Source-linked AI summary

Permute-and-Flip: An optimally stable and watermarkable decoder for LLMs

Xuandong Zhao, Lei Li, Yu-Xiang Wang

arXiv:2402.05864v3cs.CLcs.CRcs.LG

TL;DR

Existing decoding methods trade off perplexity against properties such as stability, diversity, efficiency, and watermarkability, motivating a decoder with lower perplexity than softmax sampling at comparable stability. The paper introduces PF decoding and a PF watermark, applying a differentially private selection mechanism and a Report-Noisy-Max interpretation to LLM decoding. PF has the same stability parameter as softmax sampling and up to 2x smaller expected suboptimality, while PF watermark achieves controlled false-positive rates and high detection power.

  • Problem

    Existing decoding methods trade off perplexity against properties such as stability, diversity, efficiency, and watermarkability, motivating a decoder with lower perplexity than softmax sampling at comparable stability.

    Source: §2 · pp. 2–3

  • Method

    The paper introduces PF decoding and a PF watermark, applying a differentially private selection mechanism and a Report-Noisy-Max interpretation to LLM decoding.

    Source: §2 · p. 3, §4 · p. 6

  • Results

    PF has the same stability parameter as softmax sampling and up to 2x smaller expected suboptimality, while PF watermark achieves controlled false-positive rates and high detection power.

    Source: §2 · p. 3

  • Takeaways & Limitations

    PF decoding is presented as a promising approach for balancing perplexity, stability, and watermarking in practical LLM applications.

    Source: §2 · p. 3, §6 · p. 10

    The analysis gives up on sequence-level utility maximization and instead optimizes a per-step utility function.

    Source: §2 · p. 2

Abstract

from arXiv · show

In this paper, we propose a new decoding method called Permute-and-Flip (PF) decoder. It enjoys stability properties similar to the standard sampling decoder, but is provably up to 2x better in its quality-stability tradeoff than sampling and never worse than any other decoder. We also design a cryptographic watermarking scheme analogous to Aaronson (2023)'s Gumbel watermark, but naturally tailored for PF decoder. The watermarking scheme does not change the distribution to sample, while allowing arbitrarily low false positive rate and high recall whenever the generated text has high entropy. Our experiments show that the PF decoder (and its watermarked counterpart) significantly outperform(s) naive sampling (and its Gumbel watermarked counterpart) in terms of perplexity, while retaining the same stability (and detectability), hence making it a promising new approach for LLM decoding. The code is available at https://github.com/XuandongZhao/pf-decoding

1 INTRODUCTION

The paper introduces Permute-and-Flip decoding for language models and situates it within the broader problem of designing effective randomized decoders.

1 INTRODUCTION

  • Large language models generate human-like text and solve tasks through natural chatbot interfaces.Source: §1 · p. 1
  • Language models use logits to encode preferences over vocabulary tokens when predicting the next word.Source: §1 · p. 1
  • A decoder takes prompt text and logits access as input, then outputs a generated sentence, potentially using randomization.Source: §1 · p. 1
  • Permute-and-Flip decoding is introduced as a new language-model decoder whose properties and watermarking application are developed in the paper.Source: §1 · p. 1

2 PROBLEM SETUP AND SUMMARY OF RESULTS

The paper frames decoding as a tradeoff among quality, diversity, efficiency, watermarkability, and stability, then proposes PF decoding to improve perplexity without sacrificing stability.

2 PROBLEM SETUP AND SUMMARY OF RESULTS

  • The paper focuses on maximizing a per-step utility rather than solving the sequence-level utility maximization problem.Source: §2 · p. 2
  • Decoding methods must also consider computational efficiency, latency, diversity, and watermarkability because greedy decoding lacks some of these properties.Source: §2 · p. 2
  • Stability limits sensitivity to logit perturbations and is linked to resilience against poisoning or jailbreaking attacks and to comparable selection probabilities for similar logits.Source: §2 · p. 2
  • The research question is whether a decoder can match softmax sampling’s stability while achieving lower perplexity.Source: §2 · p. 3
  • PF decoding is provably stable, Pareto-optimal in the stability–perplexity tradeoff, and up to 2x better in expected suboptimality than softmax sampling at equal stability.Source: §2 · p. 3
  • The PF watermark is computationally indistinguishable from its non-watermarked decoder and provides controlled false-positive rates with high detection power.Source: §2 · p. 3
  • Experiments report that PF watermark achieves the best balance of detection accuracy and perplexity among the evaluated baselines.Source: §2 · p. 3

3 PERMUTE-AND-FLIP DECODING ITS PROPERTIES

PF decoding randomly permutes the vocabulary and flips biased coins until selecting a token, yielding stronger preference for high-logit tokens than softmax sampling.

3 PERMUTE-AND-FLIP DECODING ITS PROPERTIES

  • PF decoding randomly permutes the vocabulary and flips biased coins sequentially until the first head selects the next token.Source: §3 · pp. 3–4
  • PF samples without replacement, unlike rejection sampling with replacement, increasing the likelihood of selecting the highest-logit token.Source: §3 · p. 4
  • PF sampling has the same (2/T)-stability guarantee as softmax sampling.Source: §3 · pp. 4–5
  • PF sampling is never worse than softmax sampling and can be up to 2x better in suboptimality while retaining the same stability parameter.Source: §3 · pp. 4–5
  • For two tokens with logits [∆, 0], PF selects the suboptimal token with probability 1/(2e^∆/T), versus 1/(1 + e^∆/T) for softmax.Source: §3 · p. 5
  • With either fixed ∆ and varying T or fixed T = 1.0 and varying ∆, the example reports PF outperforming softmax in all cases.Source: §3 · p. 5, Figure 1 · p. 5

4 REPORT-NOISY-MAX AND WATERMARKING

The paper frames watermarking as embedding detectable signals during decoding, then develops a PF watermark by replacing exponential noise with keyed pseudorandom values while preserving the sampling distribution.

Motivation and setting

  • The scheme targets AI-text detection by embedding a secret message while keeping watermarked text close to the original model distribution.This addresses practical watermarking goals including detection power at a specified false positive rate, while other desiderata such as edit resilience remain broader requirements.Source: §4 · p. 5

Relation to Gumbel watermark

  • The PF design parallels Aaronson (2023)’s Gumbel watermark, whose keyed pseudorandom function is computationally indistinguishable from uniform sampling and therefore preserves the unwatermarked distribution computationally.The PF method changes the sign-based test-score relation relative to the Gumbel watermark.Source: §4 · pp. 5–6

PF watermark construction

  • PF sampling has a Report-Noisy-Max form in which exponential noise is added to logits, enabling an analogous watermarking construction.The construction replaces Exponential(1) noise with a keyed pseudorandom version derived from a prefix.Source: §4 · p. 6
  • The watermarking pipeline uses a secret key and prefix-conditioned pseudorandom function during generation, then computes a cumulative score for detection.The detector compares the score with a Gamma(n−m,1) quantile calibrated to the target false positive rate.Source: §4 · p. 7

Guarantees

  • Under perfect pseudorandomness, the PF watermark has formal guarantees stated in Theorem 4.3, including a controlled false positive rate.The theorem assumes the keyed outputs are independent uniform variables across prefix-token pairs, with a weaker independence requirement noted separately.Source: §4 · p. 7

2. If in addition, all m-grams in y1:n are unique, then conditioning on y1:n,

The section analyzes PF watermark detectability through entropy-sensitive test scores and compares PF with Gumbel under fixed temperature and matched suboptimality.

Test-score analysis

  • The detector’s null expectation is n−m, and the detectability axis measures the expected difference between watermarked and unwatermarked token scores.The comparison subtracts the null expectation because both relevant logarithmic score terms have expectation 1 under the null.Source: §2 · pp. 7–8
  • The PF and Gumbel watermark test scores coincide when their induced sampling distributions are identical, while PF-specific expectations reflect the entropy of its induced distribution.For a uniform support of k tokens, the expected PF score uses the harmonic number H_k, approximately log k; deterministic generation yields n−m.Source: §2 · p. 7

Detectability comparison

  • At fixed temperature, PF watermarking does not beat Gumbel watermarking in detectability because PF produces a lower-entropy distribution at the same temperature.The comparison is illustrated in Figure 2a using the two-token Example 4.5.Source: §2 · p. 8
  • PF watermarking is never worse than Gumbel watermarking, with a slight midrange advantage when detectability is compared at matched suboptimality.Matching suboptimality lets PF use a larger temperature, improving stability while compensating on detectability.Source: §2 · p. 8, Figure 2 · p. 8

Conclusion

  • The paper concludes that PF watermarking is computationally indistinguishable from unwatermarked PF decoding and likely achieves Gumbel-like detectability with PF’s performance benefits.The conclusion describes the PF and Gumbel test scores as qualitatively similar and identical in some cases.Source: §2 · p. 8

5 EXPERIMENTS

Experiments evaluate PF decoding and PF watermarking across datasets, models, quality metrics, and detection settings. PF decoding lowers perplexity relative to sampling, while PF watermarking combines strong detectability with low perplexity and controlled false-positive rates.

Text generation performance

  • PF decoding produces significantly lower perplexity than sampling at the same temperature, while greedy decoding has lower perplexity but heavier repetition and lower MAUVE.The experiments use C4 and Alpaca with Llama-2 and also assess TinyLlama.Source: §5 · pp. 8–10

Watermarking results

  • PF watermark achieves the best balance of highest detection accuracy and lowest perplexity against KGW and Gumbel watermarks.Its perplexity remains close to PF sampling, indicating little quality impact from watermarking.Source: Table 2 · p. 9, §5 · p. 10
  • All watermarking methods achieve near-perfect detection accuracy on C4, and PF watermark detection remains good on TinyLlama.This supports applicability across the evaluated model sizes.Source: §5 · pp. 9–10

Controlling the false positive rate

  • Empirical false-positive rates align tightly with theoretical α values across datasets and random keys, demonstrating precise FPR control.The evaluation includes C4, Alpaca, and unwatermarked negative examples.Source: §5 · p. 10, Figure 4 · p. 10

Additional watermarking results

  • PF watermark remains detectable after paraphrasing and editing attacks, including when text length is reduced to 30 tokens.These results are reported in the additional watermarking experiments.Source: §5 · p. 10

6 CONCLUSION

The paper presents PF decoding as a stable, lower-perplexity alternative to softmax sampling and extends it with a tailored watermark. It positions the method within decoding and watermarking research while noting future work on PF-based green-red watermarking.

6 CONCLUSION

  • PF decoding matches softmax sampling’s perturbation-stability guarantees while achieving substantially lower perplexity, and PF watermarking controls false-positive rates while retaining high true-positive rates.Experiments report the best balance of detection accuracy and perplexity for PF watermark.Source: §6 · p. 10

A.1 LANGUAGE MODEL DECODING.

  • The work introduces rigorous stability analysis and a utility-stability tradeoff, with PF sampling usable as a drop-in replacement for softmax or nucleus sampling.The paper also provides watermarking capabilities for PF decoding.Source: §A.1 · p. 16

A.2 DETECT AI-GENERATED TEXT

  • Watermarking is motivated as a direct, distribution-shift-robust approach to detecting AI-generated text, complementing post-hoc methods whose robustness is limited across scenarios.Post-hoc detectors can be fragile to adversarial attacks and biased against non-native English writers.Source: §A.2 · p. 16
  • PF-watermark is closest to the Gumbel watermark and offers a slightly improved detectability-greediness tradeoff in theory, simulation, and real-data comparisons.The paper reports comparisons in Sections 4 and 5.Source: §A.2 · pp. 16–17
  • PF-based green-red watermarking may improve detectability-distortion tradeoffs, but a full exploration is left to future work.The claim is framed as an implication rather than a completed evaluation.Source: §A.2 · p. 17

A.3 DIFFERENTIAL PRIVACY

The paper connects PF decoding and watermarking to differential privacy mechanisms while using stability to characterize decoder behavior. It also explains that stability implies a form of diversity for tokens with similar logits.

A.3 DIFFERENTIAL PRIVACY

  • PF sampling originated as a differentially private selection mechanism and is connected to exponential mechanisms, noisy-max interpretations, and pure differential privacy.The paper applies these existing technical ideas to LLM decoding and watermarking.Source: §A.3 · p. 17
  • Some presented results are directly implied by existing work, while the paper’s contribution is to introduce their implications to a broader machine-learning audience.This qualification limits the novelty claim for parts of the theory.Source: §A.3 · p. 17
  • The paper’s novelty includes connecting Report-Noisy-Max mechanisms to LLM watermarking, including Gumbel- and exponential-noise constructions.It notes that other noise choices, such as Gaussian noise, may also connect the areas.Source: §A.3 · p. 17

B MORE DISCUSSION OF STABILITY

  • Stability means resistance to small logit perturbations and implies that tokens with similar logits should have similar selection probabilities.This implication is formalized through a perturbation argument in the stability discussion.Source: §B.1 · p. 17, B MORE DISCUSSION OF STABILITY · p. 17

B.2 COMPARISON OF DECODING METHODS IN TERMS OF STABILITY

PF sampling is Pareto-optimal in the stability–perplexity tradeoff, while greedy, Top-k, Top-p, and beam search lack provable stability. Stability also supports robustness to logit perturbations relevant to gray-box jailbreaking.

B.2 COMPARISON OF DECODING METHODS IN TERMS OF STABILITY

  • PF sampling is Pareto-optimal: no decoder can simultaneously achieve better stability and perplexity.Source: §B.2 · p. 17, Table 3 · p. 18
  • Only softmax and PF sampling have provable stability; greedy, Top-k, Top-p, and beam search do not.The counterexamples use small logit perturbations that produce unbounded probability ratios.Source: §B.2 · p. 18
  • Stability requires that small logit perturbations do not substantially change the output distribution, limiting abrupt changes caused by reordered token scores.Source: §B.2 · p. 18

B.3 THE CONNECTION BETWEEN STABILITY AND SAFETY

  • PF decoding is presented as a way for API providers to make logit-based jailbreaking harder while retaining watermarkability.Source: §B.3 · pp. 18–19
  • PF and softmax preserve nonzero probability under the illustrated jailbreaking perturbation, whereas Top-k eliminates the originally possible “Sorry” token.Source: §B.3 · p. 19

C ADDITIONAL EXPERIMENT DETAILS

C.1 PF WATERMARK ROBUSTNESS RESULTS.

The PF watermark is evaluated against paraphrasing, deletion, text-length, and KGW-variant settings. It retains comparable detection performance to Gumbel and KGW under attacks and remains effective on short texts.

C.1 PF WATERMARK ROBUSTNESS RESULTS.

  • PF watermark detection is comparable to Gumbel and KGW when using the same long prefix, including under paraphrasing and editing attacks.Robustness here concerns watermark removal attacks, not logit stability.Source: §C.1 · pp. 19–20, Table 4 · p. 20

C.2 IMPACT OF TEXT LENGTH ON WATERMARK DETECTION.

C.3 EXPERIMENTS ON VARIANTS OF KGW WATERMARK

D.2 PERMUTE AND FLIP WATERMARKING

  • The watermark analysis assumes perfectly iid uniform pseudorandomness, with stronger independence requirements for the detection-statistic distribution.Source: §D.2 · p. 22

D.1 PERMUTE AND FLIP SAMPLING

  • PF sampling selects a token by maximizing its logit minus the logarithm of an independent uniform random variable, and detection sums the corresponding negative logarithms after the prefix.Source: §D.1 · p. 21, §D.2 · p. 22

D.2 PERMUTE AND FLIP WATERMARKING

  • For logits containing one suboptimal token and N−1 optimal tokens, the PF distribution assigns a separate probability to the suboptimal token and equal probabilities to the others.Source: §D.2 · p. 24

D.3 GUMBEL WATERMARK AND ITS THEORETICAL ANALYSIS

The Gumbel watermark selects tokens using pseudorandom Gumbel perturbations, so its detection statistic has different behavior when the selected token is watermarked rather than independent of the secret randomness. The analysis characterizes these expectations under explicit iid assumptions.

D.3 GUMBEL WATERMARK AND ITS THEORETICAL ANALYSIS

  • Gumbel watermarking chooses the next token using logits and independent uniform pseudorandom values transformed through a Gumbel perturbation.Source: §D.3 · p. 25
  • Under the null hypothesis, the selected token is independent of the watermark randomness, giving an expected detection contribution of 1 per token.Source: §D.3 · p. 25
  • Under watermark generation, the selected-token distribution changes, and Theorem D.3 computes the resulting expectation using harmonic-number expressions.Source: §D.3 · p. 25
  • Theorem D.3 assumes independent and identically distributed uniform random variables rw over (0,1) and connects the resulting distribution P to Shannon entropy through an interpretable expectation bound.Source: §D.3 · pp. 25–26

Related papers

Loading 2402.05864v3…