The article centers on a new decoding method named Permute-and-Flip (PF) decoder. This decoder exhibits robustness features akin to the standard sampling decoder, but it is provably up to 2x better in its quality-robustness tradeoff than sampling and never worse than any other decoder. The authors also develop a cryptographic watermarking scheme similar to Aaronson’s Gumbel watermark but specifically tailored for the PF decoder. This scheme doesn’t alter the distribution to sample while permitting a low false positive rate and high recall when the generated text has high entropy. The experiments indicate that the PF decoder and its watermarked counterpart significantly outperform naive sampling in terms of perplexity while maintaining the same robustness.
Publication date: 8 Feb 2024
Project Page: https://github.com/XuandongZhao/pf-decoding
Paper: https://arxiv.org/pdf/2402.05864
