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

Xuandong Zhao, Lei Li, Yu-Xiang Wang

Introduction

In the deployment of Large Language Models (LLMs), the choice of decoding strategy—how the model selects the next token from a set of logits—is a critical design decision. While greedy decoding maximizes immediate likelihood, it lacks diversity and is vulnerable to adversarial manipulation. Conversely, stochastic methods like softmax sampling introduce necessary randomness but often at the cost of increased perplexity and reduced text quality.

Presented at ICLR 2025, Permute-and-Flip (PF) emerges as a new gold standard for LLM decoding. It provides a provably optimal balance between stability (robustness to logit perturbations) and quality (minimizing suboptimality relative to greedy search), while simultaneously enabling a high-performance cryptographic watermarking scheme.

The Stability-Quality Tradeoff

A key challenge in decoding is maintaining "stability." A stable decoder ensures that small changes in the model's output logits—whether due to minor prompt variations or adversarial logit-bias attacks—do not lead to disproportionately large changes in the output distribution. Softmax sampling is the industry standard for stability, but it is inherently "sampling with replacement," which can lead to suboptimal token choices.

The researchers demonstrate that Permute-and-Flip is "Pareto optimal" in this regard. As shown in Figure 2, PF consistently achieves lower expected suboptimality than the softmax decoder across various temperatures ($T$) and logit gaps ($\Delta$). This means that for any given level of stability, PF will produce higher-quality, more likely text.

Comparison of suboptimality between PF and Softmax decoders across temperature and logit gaps.

The Permute-and-Flip Method

The PF algorithm is inspired by techniques in Differential Privacy, specifically the "Report-Noisy-Max" mechanism. The process for selecting each token is straightforward:

  1. Permute: The entire vocabulary is randomly shuffled.
  2. Flip: The decoder iterates through the shuffled vocabulary, flipping a biased coin for each word. The probability of "heads" is determined by the word's logit score. The first word to result in "heads" is selected.

This mechanism is mathematically equivalent to adding exponential noise to the logits and selecting the maximum. By sampling without replacement, PF remains "greedier" than softmax while retaining the mathematical properties required for stability and watermarking.

Robust and Detectable Watermarking

Beyond standard decoding, PF introduces a powerful watermarking capability. By replacing the random coin flips with a pseudo-random function (PRF) keyed to a secret and conditioned on previous context, a signature is embedded directly into the generation process.

This PF Watermark offers several advantages over existing methods like the Gumbel or "Green-Red" (KGW) watermarks. It follows a predictable Gamma distribution, allowing for precise control over False Positive Rates (FPR). Empirically, the PF watermark achieves superior detectability for a given level of suboptimality, as illustrated in Figure 6.

Detectability vs. suboptimality for PF and Gumbel watermarking schemes.

Key Results and Evaluation

The authors evaluated PF using Llama-2 and TinyLlama models on the C4 and Alpaca datasets. Key findings include:

  • Perplexity Gains: On the C4 dataset ($T=1.0$), PF reduced perplexity from 12.47 (softmax) to 8.94, a significant improvement in text quality.
  • Watermark Efficiency: The PF watermark remains highly detectable even in short sequences (approx. 30 tokens) and is robust against paraphrasing attacks intended to strip the watermark.
  • Security: The stability of PF acts as a defensive layer, making "jailbreaking" attempts that rely on forcing specific token sequences significantly more difficult.

Conclusion and Future Directions

Permute-and-Flip represents a significant advancement in LLM decoding, offering a theoretically grounded and practically superior alternative to softmax sampling. While shuffling large vocabularies may introduce minor latency, the gains in quality, stability, and watermarking performance are substantial. Future work may explore multi-bit watermarking to embed richer metadata and the integration of PF with other sampling constraints like Top-$p$ filtering.

The implementation is available at github.com/XuandongZhao/pf-decoding.

Summary updated

BibTeX
@inproceedings{zhao2025permute,
  author = {Xuandong Zhao and Lei Li and Yu-Xiang Wang},
  title = {{Permute-and-Flip: An optimally robust and watermarkable decoder for LLMs}},
  booktitle = {International Conference on Learning Representations},
  year = {2025},
  url = {https://openreview.net/forum?id=YyVVicZ32M},
}
Figure