SpecPF: Speculative Permute-Flip Decoding with Improved Watermark

We study speculative decoding for the permute-and-flip (PF) decoder, proposed by Zhao et al. (ICLR 2025) while preserving its native watermark detectability. Our method, SpecPF, speculatively accelerates the recently proposed permute-and-flip decoder while preserving the correct output distribution, and hence all of its desirable properties, including optimal stability, natural watermarkability, and Pareto-optimality with respect to the stability–perplexity trade-off. We design a novel watermark scheme, namely a cross-fitted bigram filter followed by the exact PF Fisher/Gamma test. Our watermark detection method is tailored to the permute-and-flip distribution and is model-agnostic, consistently outperforming the original watermarking scheme. While keeping the target distribution exactly unchanged and hence inheriting all desirable properties of the original PF decoder, our speculative decoding method achieves up to $1.32\times$ wall-clock speedup, while longer lookahead increases the number of emitted tokens per target batch to $2.745$. We also investigate the recently discovered sampling-watermark trade-off frontier for the SpecPF decoder. Experimental results across multiple model pairs and datasets validate both the improved sampling efficiency and stronger watermark detectability of our method.