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

arXiv: https://arxiv.org/abs/2402.05864 · HTML: https://mlsanity.com/paper/2402.05864/

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- Placed in Watermarking generated content and models, one of 12 directions in LLM safety and security.
- Builds on 48 of its 64 references that are in the map.
- First posted on arXiv 8 Feb 2024.

## Placed in

- LLM safety and security / [Watermarking generated content and models](https://mlsanity.com/safety/watermarking-generated-content-and-models/)

## Builds on (most cited first, 30 of 48)

- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer](https://mlsanity.com/paper/1910.10683/) (2019)
- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks](https://mlsanity.com/paper/2005.11401/) (2020)
- [Constitutional AI: Harmlessness from AI Feedback](https://mlsanity.com/paper/2212.08073/) (2022)
- [The Curious Case of Neural Text Degeneration](https://mlsanity.com/paper/1904.09751/) (2019)
- [Accelerating Large Language Model Decoding with Speculative Sampling](https://mlsanity.com/paper/2302.01318/) (2023)
- [Ethical and social risks of harm from Language Models](https://mlsanity.com/paper/2112.04359/) (2021)
- [DetectGPT: Zero-Shot Machine-Generated Text Detection using Probability Curvature](https://mlsanity.com/paper/2301.11305/) (2023)
- [A Watermark for Large Language Models](https://mlsanity.com/paper/2301.10226/) (2023)
- [Contrastive Decoding: Open-ended Text Generation as Optimization](https://mlsanity.com/paper/2210.15097/) (2022)
- [Defending Against Neural Fake News](https://mlsanity.com/paper/1905.12616/) (2019)
- [Neural Text Generation with Unlikelihood Training](https://mlsanity.com/paper/1908.04319/) (2019)
- [MAUVE: Measuring the Gap Between Neural Text and Human Text using Divergence Frontiers](https://mlsanity.com/paper/2102.01454/) (2021)
- [Paraphrasing evades detectors of AI-generated text, but retrieval is an effective defense](https://mlsanity.com/paper/2303.13408/) (2023)
- [Can AI-Generated Text be Reliably Detected?](https://mlsanity.com/paper/2303.11156/) (2023)
- [Robust Distortion-free Watermarks for Language Models](https://mlsanity.com/paper/2307.15593/) (2023)
- [Diverse Beam Search: Decoding Diverse Solutions from Neural Sequence Models](https://mlsanity.com/paper/1610.02424/) (2016)
- [Provable Robust Watermarking for AI-Generated Text](https://mlsanity.com/paper/2306.17439/) (2023)
- [Fast-DetectGPT: Efficient Zero-Shot Detection of Machine-Generated Text via Conditional Probability Curvature](https://mlsanity.com/paper/2310.05130/) (2023)
- [Lexically Constrained Decoding for Sequence Generation Using Grid Beam Search](https://mlsanity.com/paper/1704.07138/) (2017)
- [Undetectable Watermarks for Language Models](https://mlsanity.com/paper/2306.09194/) (2023)
- [RADAR: Robust AI-Text Detection via Adversarial Learning](https://mlsanity.com/paper/2307.03838/) (2023)
- [GPT detectors are biased against non-native English writers](https://mlsanity.com/paper/2304.02819/) (2023)
- [NeuroLogic A*esque Decoding: Constrained Text Generation with Lookahead Heuristics](https://mlsanity.com/paper/2112.08726/) (2021)
- [DNA-GPT: Divergent N-Gram Analysis for Training-Free Detection of GPT-Generated Text](https://mlsanity.com/paper/2305.17359/) (2023)
- [Intrinsic Dimension Estimation for Robust Detection of AI-Generated Texts](https://mlsanity.com/paper/2306.04723/) (2023)
- [Unbiased Watermark for Large Language Models](https://mlsanity.com/paper/2310.10669/) (2023)
- [Weak-to-Strong Jailbreaking on Large Language Models](https://mlsanity.com/paper/2401.17256/) (2024)
- [Guided Open Vocabulary Image Captioning with Constrained Beam Search](https://mlsanity.com/paper/1612.00576/) (2016)

## Built on by (most cited first, 22 of 22)

- [BiMark: Unbiased Multilayer Watermarking for Large Language Models](https://mlsanity.com/paper/2506.21602/) (2025)
- [WAPITI: A Watermark for Finetuned Open-Source LLMs](https://mlsanity.com/paper/2410.06467/) (2024)
- [In-Context Watermarks for Large Language Models](https://mlsanity.com/paper/2505.16934/) (2025)
- [Watermarking Generative Tabular Data](https://mlsanity.com/paper/2405.14018/) (2024)
- [Position: LLM Watermarking Should Align Stakeholders' Incentives for Practical Adoption](https://mlsanity.com/paper/2510.18333/) (2025)
- [Segmenting Watermarked Texts From Language Models](https://mlsanity.com/paper/2410.20670/) (2024)
- [A Statistical Hypothesis Testing Framework for Data Misappropriation Detection in Large Language Models](https://mlsanity.com/paper/2501.02441/) (2025)
- [RLCracker: Evaluating the Worst-Case Vulnerability of LLM Watermarks with Adaptive RL Attacks](https://mlsanity.com/paper/2509.20924/) (2025)
- [RLSpoofer: A Lightweight Evaluator for LLM Watermark Spoofing Resilience](https://mlsanity.com/paper/2604.11546/) (2026)
- [Accelerating Diffusion Sampling via Speculative Draft Trees](https://mlsanity.com/paper/2609.17691/) (2026)
- [HeavyWater and SimplexWater: Distortion-Free LLM Watermarks for Low-Entropy Next-Token Predictions](https://mlsanity.com/paper/2506.06409/) (2025)
- [Watermark Forensics for Generative Models: An Information-Theoretic Perspective](https://mlsanity.com/paper/2607.13003/) (2026)
- [DenMark: Robust Semantic Watermarking for Diffusion Language Models](https://mlsanity.com/paper/2609.14257/) (2026)
- [Watermarking Generative Categorical Data](https://mlsanity.com/paper/2411.10898/) (2024)
- [Disappearing Ink: Obfuscation Breaks N-gram Code Watermarks in Theory and Practice](https://mlsanity.com/paper/2507.05512/) (2025)
- [MarkTune: Improving the Quality-Detectability Trade-off in Open-Weight LLM Watermarking](https://mlsanity.com/paper/2512.04044/) (2025)
- [Learning to Follow In-Context Watermark Instructions via Self-Distillation](https://mlsanity.com/paper/2608.29030/) (2026)
- [Watermarkable Multi-Draft Speculative Sampling via Poisson Processes](https://mlsanity.com/paper/2609.21858/) (2026)
- [ExpBoN: Exponential-Noise Best-of-n for Efficient Test-Time LLM Alignment](https://mlsanity.com/paper/2609.21899/) (2026)
- [Grammar-Guided Code Watermarking with Green Temperature](https://mlsanity.com/paper/2610.05323/) (2026)
- [Could LLM Watermark Detection be Public?](https://mlsanity.com/paper/2610.12106/) (2026)
- [textGrain watermarking is harder to detect: can sum-tests still do it optimally?](https://mlsanity.com/paper/2610.17655/) (2026)

## Abstract (arXiv)

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