Permute-and-Flip: An optimally stable and watermarkable decoder for LLMs
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 .
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
4 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- BiMark: Unbiased Multilayer Watermarking for Large Language Models cites A Watermark for Large Language Models
- Neural Text Generation With Unlikelihood Training cites The Curious Case of Neural Text Degeneration
- The Curious Case of Neural Text Degeneration cites Neural Text Generation With Unlikelihood Training
- DetectGPT: Zero-Shot Machine-Generated Text Detection using Probability Curvature cites A Watermark for Large Language Models
- In-Context Watermarks for Large Language Models cites DetectGPT: Zero-Shot Machine-Generated Text Detection using Probability Curvature
- In-Context Watermarks for Large Language Models cites A Watermark for Large Language Models
- HeavyWater and SimplexWater: Distortion-free LLM Watermarks for Low-Entropy Distributions cites A Watermark for Large Language Models
- IPMark: A Sentence-Level Watermark for LLMs with Hierarchical Personalization and Efficient Detection cites A Watermark for Large Language Models
Cited by top-tier papers4
- In-Context Watermarks for Large Language ModelsYepeng Liu, Xuandong Zhao, Christopher Kruegel, Dawn Song et al.ICLR 2026 · 14 citations
- HeavyWater and SimplexWater: Distortion-free LLM Watermarks for Low-Entropy DistributionsDor Tsur, Carol Xuan Long, Claudio Mayrink Verdun, Sajani Vithana et al.NeurIPS 2025 · 9 citations
- BiMark: Unbiased Multilayer Watermarking for Large Language ModelsXiaoyan Feng, He Zhang, Yanjun Zhang, Leo Yu Zhang et al.ICML 2025
- IPMark: A Sentence-Level Watermark for LLMs with Hierarchical Personalization and Efficient DetectionWenbo An, Lianwei Wu, Zehao WangICML 2026
Builds on22
- Retrieval-Augmented Generation for Knowledge-Intensive NLP TasksPatrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni et al.NeurIPS 2020 · 19,162 citations
- The Curious Case of Neural Text DegenerationAri Holtzman, Jan Buys, Li Du, Maxwell Forbes et al.ICLR 2020 · 4,112 citations
- DetectGPT: Zero-Shot Machine-Generated Text Detection using Probability CurvatureEric Mitchell, Yoonho Lee, Alexander Khazatsky, Christopher D. Manning et al.ICML 2023 · 988 citations
- A Watermark for Large Language ModelsJohn Kirchenbauer, Jonas Geiping, Yuxin Wen, Jonathan Katz et al.ICML 2023 · 854 citations
- Neural Text Generation With Unlikelihood TrainingSean Welleck, Ilia Kulikov, Stephen Roller, Emily Dinan et al.ICLR 2020 · 683 citations
Related papers
- GumbelSoft: Diversified Language Model Watermarking via the GumbelMax-trickJiayi Fu, Xuandong Zhao, Ruihan Yang, Yuansen Zhang et al.ACL 2024 · 6 citations
- WaterMax: breaking the LLM watermark detectability-robustness-quality trade-offEva Giboulot, Teddy FuronNeurIPS 2024 · 76 citations
- Adaptive Text Watermark for Large Language ModelsYepeng Liu, Yuheng BuICML 2024 · 63 citations
- Watermarking Large Language Models: An Unbiased and Low-risk MethodMinjia Mao, Dongjun Wei, Zeyu Chen, Xiao Fang et al.ACL 2025 · 6 citations
- XMark: Reliable Multi-Bit Watermarking for LLM-Generated TextsJiahao Xu, Rui Hu, Olivera Kotevska, Zikai ZhangACL 2026 · 1 citation
