Research map / Large language models / Language, safety and interpretability

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

ICLR 2025 · Large language models › Language, safety and interpretability · approach: Text watermarking · 2 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes Permute-and-Flip (PF) decoding for LLMs, a stable decoder with lower perplexity than softmax sampling, and a PF watermark analogous to the Gumbel watermark with controlled false positive rate.

Problem

LLM decoding faces a tradeoff: sampling is stable (2/T-stable) but has higher perplexity, while greedy/beam/top-k/top-p are higher quality but unstable and harder to watermark; the goal is a decoder that is as stable as softmax sampling yet lower perplexity, and watermarkable.

Approach

Adapts the permute-and-flip differential privacy selection mechanism to LLM decoding; it is equivalent to report-noisy-max with exponential noise, which allows a pseudo-random exponential-noise watermark (PF watermark) analogous to the Gumbel watermark, with theoretical guarantees of stability, Pareto optimality and never being worse than softmax sampling.

Key results

• On C4 at T=1.0 with Llama2-7B, PF decoding reaches PPL1 8.94 versus 12.47 for softmax sampling, with seq-rep-5 0.03 vs 0.02.
• PF watermark achieves TPR 0.984 at 1% FPR on C4 (T=1.0, Llama2-7B), comparable to Gumbel WM (0.988) with lower PPL1 (8.33 vs 11.41).
• Empirical false positive rates of the PF watermark track the theoretical alpha across keys and datasets.

Measured effects reported in the paper

Surprising findings

• Gumbel watermark shows higher detectability than PF watermark at the same temperature, but PF is more favorable on the detectability-greediness tradeoff.

Limitations

• Watermark detectability at the same temperature is lower than Gumbel watermark.
• Green-red PF variant is left to future work.
• Watermark robustness to paraphrase attacks is comparable to but not better than Gumbel and KGW.

Experimental setup

Datasets: C4 Alpaca

Benchmarks: C4 Alpaca

Metrics: perplexity MAUVE seq-rep-5 AUC TPR at 1% FPR F1

Baselines: Greedy decoding Softmax sampling Gumbel watermark KGW watermark

Builds on: Gumbel watermark permute-and-flip mechanism (differential privacy) exponential mechanism KGW green-red watermark

Closest papers by meaning

• ArcMark: Distortion-Free Multi-Byte LLM Watermark via Optimal Transport (NeurIPS 2026 · similarity 0.87)
• PRO: Enabling Precise and Robust Text Watermark for Open-Source LLMs (NeurIPS 2026 · similarity 0.85)
• Majority Bit-Aware Watermarking for Large Language Models (NeurIPS 2026 · similarity 0.85)
• Break the Trade-off Between Watermark Strength and Speculative Sampling Efficiency for Language Models (ICLR 2026 · similarity 0.85)
• Theoretically Grounded Framework for LLM Watermarking: A Distribution-Adaptive Approach (NeurIPS 2025 · similarity 0.84)
• Robust Multi-bit Text Watermark with LLM-based Paraphrasers (ICML 2025 · similarity 0.84)