Infact, bysubstitutingp =1n into Equation (8), weobtain: Proposition 5.For q = ( c,..., c, 0) Rn withc = 2 Δ logn, theexpectederrorE [ E ( MPF, q)] ofpermute-and-flipisatleastΔ2 log ( n).

Summary and Contributions: This paper studies the selection problem, which (in the most general case) can be stated as follows: there is a data-independent set of n candidate solutions R that we would like to select from. For each candidate r in R, there is a quality score function q_r that maps any input dataset D to a real number q_r(D). The goal is to, given dataset D, select r in R that maximizes q_r(D), while respecting the notion of differential privacy (DP). Here, we say that the algorithm incurs an error of q * - Expectation[q_{output}(D)] where q * min_r q_r(D); in other words, the error is the expected quality loss of the return solution compared to the optimum. Many well-studied problems in machine learning can be stated in the selection formulation; for example, each r could be a hypothesis and q_r(D) is the empirical error.

In this paper, we propose a new decoding method called Permute-and-Flip (PF) decoder. It enjoys robustness properties similar to the standard sampling decoder, but is provably up to 2x better in its quality-robustness tradeoff than sampling and never worse than any other decoder. We also design a cryptographic watermarking scheme analogous to Aaronson'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 it's Gumbel watermarked counterpart) in terms of perplexity, while retaining the same robustness (and detectability), hence making it a promising new approach for LLM decoding. The code is available at https://github.com/XuandongZhao/pf-decoding