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

Xuandong Zhao, Lei Li, Yu-Xiang Wang

In the world of Large Language Models (LLMs), choosing the next word—the "decoding" process—is a delicate balancing act. Do you go for the most likely word (greedy decoding), which yields high quality but repetitive and predictable text? Or do you sample randomly (softmax sampling) to introduce diversity and enable watermarking, at the cost of lower text quality?

A new paper from researchers at UC Berkeley, CMU, and UC San Diego introduces a compelling third option. They propose the Permute-and-Flip (PF) decoder, a method adapted from differential privacy that provably offers a better tradeoff between text quality and stability than the standard sampling methods used today.

The Decoding Trilemma

Current LLM decoding methods face a trilemma between quality (how human-like and coherent the text is), diversity (avoiding repetitive loops), and stability.

In this context, stability refers to how much the output distribution changes if the model's internal scores (logits) are slightly perturbed. High stability is crucial for making models robust against "jailbreaking" or "data poisoning" attacks that attempt to force specific outputs by subtly manipulating inputs.

While greedy decoding offers high quality, it has zero diversity and zero stability. Softmax sampling (the industry standard) provides diversity and stability but often sacrifices quality, leading to higher "perplexity" (a measure of how surprised a model is by the text). The authors set out to find a decoder that is as stable as softmax sampling but much closer to the quality of greedy decoding.

The Permute-and-Flip (PF) Algorithm

The authors introduce the Permute-and-Flip (PF) algorithm. Originally developed for private data selection, the algorithm works in two simple steps for each token:

  1. Permute: Randomly shuffle the entire vocabulary.
  2. Flip: Iterate through the shuffled vocabulary and flip a biased coin for each word. The bias is based on the word's logit score. The first word to come up "heads" is selected.

Mathematically, this is equivalent to a "Report-Noisy-Max" procedure: independent exponential noise is added to the logits, and the word with the highest resulting score is chosen.

Key Insights and Results

  • The 2x Advantage: The authors prove that PF decoding is up to 2x better in its quality-stability tradeoff than standard softmax sampling.
  • Pareto Optimality: They demonstrate that PF is "Pareto-optimal." For a given level of stability, no other possible decoding algorithm can achieve higher expected utility (quality).
  • "More Greedy" but Equally Stable: PF is naturally "greedier" than softmax sampling—it's more likely to pick the top-ranked words—yet it maintains the exact same mathematical stability guarantees.
Comparison of expected suboptimality between PF and Softmax decoders across temperatures and logit gaps.

Across extensive tests using Llama-2 and TinyLlama on datasets like C4 and Alpaca, the PF decoder consistently achieved lower perplexity than softmax sampling. For example, on the C4 dataset with Llama-2-7B, PF reduced perplexity from 12.47 to 8.94 compared to standard sampling.

Superior Watermarking

The authors also extend the PF decoder to support cryptographic watermarking. By using a secret key and a pseudo-random function (PRF) to generate the "noise" instead of true randomness, the model owner can later prove a text was AI-generated.

Unlike many watermarks that shift logits and inadvertently change the text's meaning, this scheme is "distribution-preserving"—it samples from the exact same distribution as the non-watermarked PF decoder.

Detectability versus suboptimality tradeoff for PF Watermark compared to Gumbel Watermark.

The PF watermark achieves a strictly better balance of detection accuracy and text quality than existing baselines, including Aaronson’s Gumbel watermark. Furthermore, the watermark remains robustly detectable even when the generated text is short (e.g., only 30 tokens) or subjected to paraphrasing attacks designed to scrub the watermark.

Limitations and Future Work

While promising, the PF decoder does have limitations:

  • Per-Step Optimization: PF is a "myopic" decoder; it maximizes utility for the very next token. It doesn't perform long-term planning like Beam Search, which looks several words ahead.
  • Computational Overhead: While the "Report-Noisy-Max" formulation is efficient, the theoretical "Permute-and-Flip" steps could introduce overhead if implemented naively on massive vocabularies.

Future research may explore "PF-style" versions of other watermarking schemes (like the Green-Red list) to see if they can inherit PF's superior stability-quality tradeoff. For those interested in experimenting with this new gold standard for decoding, the authors have made their code available on GitHub.

Summary updated

Abstract

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