Gumbel-max List Sampling for Distribution Coupling with Multiple Samples
This work addresses efficiency challenges in sampling and compression for machine learning applications, offering incremental improvements with practical benefits.
The paper tackles the problem of coupling probability distributions by generating lists of samples and accepting if any sample matches one from another distribution, proposing a novel Gumbel-max list sampling method and establishing a lower bound on acceptance probability. It achieves competitive performance in multi-draft speculative sampling for language tasks and provides significant gains in distributed lossy compression with side information on synthetic and MNIST datasets.
We study a relaxation of the problem of coupling probability distributions -- a list of samples is generated from one distribution and an accept is declared if any one of these samples is identical to the sample generated from the other distribution. We propose a novel method for generating samples, which extends the Gumbel-max sampling suggested in Daliri et al. (arXiv:2408.07978) for coupling probability distributions. We also establish a corresponding lower bound on the acceptance probability, which we call the list matching lemma. We next discuss two applications of our setup. First, we develop a new mechanism for multi-draft speculative sampling that is simple to implement and achieves performance competitive with baselines such as SpecTr and SpecInfer across a range of language tasks. Our method also guarantees a certain degree of drafter invariance with respect to the output tokens which is not supported by existing schemes. We also provide a theoretical lower bound on the token level acceptance probability. As our second application, we consider distributed lossy compression with side information in a setting where a source sample is compressed and available to multiple decoders, each with independent side information. We propose a compression technique that is based on our generalization of Gumbel-max sampling and show that it provides significant gains in experiments involving synthetic Gaussian sources and the MNIST image dataset.