mlsanityData to 7 Oct 2026

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

arXiv 2402.05864 ↗First posted 8 Feb 2024cs.CL cs.CR cs.LGcited by 17

On the map: LLM safety and security → Watermarking generated content and models

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

Key facts. Cited by 17 papers in the map (data through 7 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.

Builds on

48 of 64 references.

Closest ancestors · 11

Same direction, newest first

  1. 2023A Resilient and Accessible Distribution-Preserving Watermark for Large Language Models11 Oct
  2. 2023Unbiased Watermark for Large Language Models22 Sep
  3. 2023Robust Distortion-free Watermarks for Language Models28 Jul
  4. 2023Three Bricks to Consolidate Watermarks for Large Language Models26 Jul
  5. 2023Provable Robust Watermarking for AI-Generated Text30 Jun
  6. 2023Undetectable Watermarks for Language Models25 May
  7. 2023Robust Multi-bit Natural Language Watermarking through Invariant Features3 May
  8. 2023Paraphrasing evades detectors of AI-generated text, but retrieval is an effective defense23 Mar
  9. 2023Can AI-Generated Text be Reliably Detected?17 Mar
  10. 2023Protecting Language Generation Models via Invisible Watermarking6 Feb
  11. 2023A Watermark for Large Language Models24 Jan

Other references · 37

  1. 2023GPT-4 Technical Reportcited by 18,132
  2. 2019Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformercited by 14,491
  3. 2023Llama 2: Open Foundation and Fine-Tuned Chat Modelscited by 12,865
  4. 2020Retrieval-Augmented Generation for Knowledge-Intensive NLP Taskscited by 9,160
  5. 2022Constitutional AI: Harmlessness from AI Feedbackcited by 2,950
  6. 2019The Curious Case of Neural Text Degenerationcited by 2,881
  7. 2023Accelerating Large Language Model Decoding with Speculative Samplingcited by 975
  8. 2021Ethical and social risks of harm from Language Modelscited by 957
  9. 2023DetectGPT: Zero-Shot Machine-Generated Text Detection using Probability Curvaturecited by 705
  10. 2022Contrastive Decoding: Open-ended Text Generation as Optimizationcited by 598
  11. 2019Defending Against Neural Fake Newscited by 553
  12. 2019Neural Text Generation with Unlikelihood Trainingcited by 489
25 more
  1. 2021MAUVE: Measuring the Gap Between Neural Text and Human Text using Divergence Frontierscited by 466
  2. 2016Diverse Beam Search: Decoding Diverse Solutions from Neural Sequence Modelscited by 299
  3. 2023Fast-DetectGPT: Efficient Zero-Shot Detection of Machine-Generated Text via Conditional Probability Curvaturecited by 278
  4. 2017Lexically Constrained Decoding for Sequence Generation Using Grid Beam Searchcited by 234
  5. 2023RADAR: Robust AI-Text Detection via Adversarial Learningcited by 187
  6. 2023GPT detectors are biased against non-native English writerscited by 175
  7. 2021NeuroLogic A*esque Decoding: Constrained Text Generation with Lookahead Heuristicscited by 153
  8. 2023DNA-GPT: Divergent N-Gram Analysis for Training-Free Detection of GPT-Generated Textcited by 127
  9. 2023Intrinsic Dimension Estimation for Robust Detection of AI-Generated Textscited by 111
  10. 2016Guided Open Vocabulary Image Captioning with Constrained Beam Searchcited by 105
  11. 2024Weak-to-Strong Jailbreaking on Large Language Modelscited by 100
  12. 2022On Decoding Strategies for Neural Text Generatorscited by 89
  13. 2019Comparison of Diverse Decoding Methods from Conditional Language Modelscited by 78
  14. 2023Red Teaming Language Model Detectors with Language Modelscited by 55
  15. 2020Generalized Entropy Regularization or: There's Nothing Special about Label Smoothingcited by 40
  16. 2023GPT-Sentinel: Distinguishing Human and ChatGPT Generated Contentcited by 40
  17. 2020Attacking Neural Text Detectorscited by 37
  18. 2022CoCo: Coherence-Enhanced Machine-Generated Text Detection Under Data Limitation With Contrastive Learningcited by 32
  19. 2017Recurrent Neural Networks as Weighted Language Recognizerscited by 30
  20. 2023On the Safety of Open-Sourced Large Language Models: Does Alignment Really Prevent Them From Being Misused?cited by 25
  21. 2021ML Attack Models: Adversarial Attacks and Data Poisoning Attackscited by 23
  22. 2020Permute-and-Flip: A new mechanism for differentially private selectioncited by 22
  23. 2021How to Inject Backdoors with Better Consistency: Logit Anchoring on Clean Datacited by 22
  24. 2021The Permute-and-Flip Mechanism is Identical to Report-Noisy-Max with Exponential Noisecited by 14
  25. 2022Adaptive Private-K-Selection with Adaptive K and Application to Multi-label PATEcited by 9

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 3; 2025: 7; 2026: 7.

17 papers.

Sort:

By area:

  1. 2025BiMark: Unbiased Multilayer Watermarking for Large Language Modelscited by 18
  2. 2025In-Context Watermarks for Large Language Modelscited by 9
  3. 2025Position: LLM Watermarking Should Align Stakeholders' Incentives for Practical Adoptioncited by 7
  4. 2024Watermarking Generative Tabular Datacited by 6
  5. 2024Segmenting Watermarked Texts From Language Modelscited by 4
  6. 2025A Statistical Hypothesis Testing Framework for Data Misappropriation Detection in Large Language Modelscited by 2
  7. 2026Accelerating Diffusion Sampling via Speculative Draft Treescited by 2
  8. 2025HeavyWater and SimplexWater: Distortion-Free LLM Watermarks for Low-Entropy Next-Token Predictionscited by 1
  9. 2026DenMark: Robust Semantic Watermarking for Diffusion Language Modelscited by 1
  10. 2024Watermarking Generative Categorical Datacited by 0
  11. 2025Disappearing Ink: Obfuscation Breaks N-gram Code Watermarks in Theory and Practicecited by 0
  12. 2025MarkTune: Improving the Quality-Detectability Trade-off in Open-Weight LLM Watermarkingcited by 0
5 more
  1. 2026Watermark Forensics for Generative Models: An Information-Theoretic Perspectivecited by 0
  2. 2026Learning to Follow In-Context Watermark Instructions via Self-Distillationcited by 0
  3. 2026Watermarkable Multi-Draft Speculative Sampling via Poisson Processescited by 0
  4. 2026ExpBoN: Exponential-Noise Best-of-n for Efficient Test-Time LLM Alignmentcited by 0
  5. 2026Could LLM Watermark Detection be Public?cited by 0