Gumbel-max List Sampling for Distribution Coupling with Multiple Samples

• URL: http://arxiv.org/abs/2506.05632v2
• Date: Tue, 10 Jun 2025 16:33:41 GMT
• Title: Gumbel-max List Sampling for Distribution Coupling with Multiple Samples
• Authors: Joseph Rowan, Buu Phan, Ashish Khisti,
• Abstract summary: We develop a new mechanism for speculative sampling that is simple to implement and achieves performance competitive with baselines such as SpecTr and SpecInfer.<n>We consider distributed lossy compression with side information in a setting where a source sample is compressed and available to multiple decoders.
• Score: 19.059328123272028
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Enhanced Importance Sampling through Latent Space Exploration in Normalizing Flows [69.8873421870522]
  importance sampling is a rare event simulation technique used in Monte Carlo simulations.<n>We propose a method for more efficient sampling by updating the proposal distribution in the latent space of a normalizing flow.
  arXiv  Detail & Related papers  (2025-01-06T21:18:02Z)
• Differentially Private Multi-Sampling from Distributions [4.292685318253575]
  We study the sample complexity of DP emphsingle-sampling i.e., the minimum number of samples needed to perform this task.<n>We define two variants of emphmulti-sampling, where the goal is to privately approximate $m>1$ samples.
  arXiv  Detail & Related papers  (2024-12-13T19:14:05Z)
• Multi-Draft Speculative Sampling: Canonical Decomposition and Theoretical Limits [26.220189807865548]
  We consider multi-draft speculative sampling, where the proposal sequences are sampled independently from different draft models.<n>We show that the optimal scheme can be decomposed into a two-step solution.
  arXiv  Detail & Related papers  (2024-10-23T19:28:34Z)
• Theory on Score-Mismatched Diffusion Models and Zero-Shot Conditional Samplers [49.97755400231656]
  We present the first performance guarantee with explicit dimensional dependencies for general score-mismatched diffusion samplers.<n>We show that score mismatches result in an distributional bias between the target and sampling distributions, proportional to the accumulated mismatch between the target and training distributions.<n>This result can be directly applied to zero-shot conditional samplers for any conditional model, irrespective of measurement noise.
  arXiv  Detail & Related papers  (2024-10-17T16:42:12Z)
• Controllable Generation via Locally Constrained Resampling [77.48624621592523]
  We propose a tractable probabilistic approach that performs Bayesian conditioning to draw samples subject to a constraint. Our approach considers the entire sequence, leading to a more globally optimal constrained generation than current greedy methods. We show that our approach is able to steer the model's outputs away from toxic generations, outperforming similar approaches to detoxification.
  arXiv  Detail & Related papers  (2024-10-17T00:49:53Z)
• Conformal Language Modeling [61.94417935386489]
  We propose a novel approach to conformal prediction for generative language models (LMs) Standard conformal prediction produces prediction sets with rigorous, statistical guarantees. We demonstrate the promise of our approach on multiple tasks in open-domain question answering, text summarization, and radiology report generation.
  arXiv  Detail & Related papers  (2023-06-16T21:55:08Z)
• Stochastic Approximation Approaches to Group Distributionally Robust Optimization and Beyond [89.72693227960274]
  This paper investigates group distributionally robust optimization (GDRO) with the goal of learning a model that performs well over $m$ different distributions. To reduce the number of samples in each round from $m$ to 1, we cast GDRO as a two-player game, where one player conducts and the other executes an online algorithm for non-oblivious multi-armed bandits. In the second scenario, we propose to optimize the average top-$k$ risk instead of the maximum risk, thereby mitigating the impact of distributions.
  arXiv  Detail & Related papers  (2023-02-18T09:24:15Z)
• Arithmetic Sampling: Parallel Diverse Decoding for Large Language Models [65.52639709094963]
  Methods such as beam search and Gumbel top-k sampling can guarantee a different output for each element of the beam, but are not easy to parallelize. We present a framework for sampling according to an arithmetic code book implicitly defined by a large language model.
  arXiv  Detail & Related papers  (2022-10-18T22:19:41Z)
• Diverse Human Motion Prediction via Gumbel-Softmax Sampling from an Auxiliary Space [34.83587750498361]
  Diverse human motion prediction aims at predicting multiple possible future pose sequences from a sequence of observed poses. Previous approaches usually employ deep generative networks to model the conditional distribution of data, and then randomly sample outcomes from the distribution. We propose a novel sampling strategy for sampling very diverse results from an imbalanced multimodal distribution.
  arXiv  Detail & Related papers  (2022-07-15T09:03:57Z)
• Sampling from Discrete Energy-Based Models with Quality/Efficiency Trade-offs [3.491202838583993]
  Energy-Based Models (EBMs) allow for extremely flexible specifications of probability distributions. They do not provide a mechanism for obtaining exact samples from these distributions. We propose a new approximate sampling technique, Quasi Rejection Sampling (QRS), that allows for a trade-off between sampling efficiency and sampling quality.
  arXiv  Detail & Related papers  (2021-12-10T17:51:37Z)
• Uncorrelated problem-specific samples of quantum states from zero-mean Wishart distributions [4.289102530380288]
  We present a two-step algorithm for sampling from the quantum state space. We establish the explicit form of the induced Wishart distribution for quantum states. We demonstrate that this sampling algorithm is very efficient for one-qubit and two-qubit states, and reasonably efficient for three-qubit states.
  arXiv  Detail & Related papers  (2021-06-16T03:06:41Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.