Uniform race improves sampling without preset thresholds
Uniform Race: Parameter-Free Approximate Rejection Sampling
Machine Learning
Summary
Sampling from a target distribution is often tricky because the exact form isn't fully known, and methods require setting parameters that depend on unknown details. The authors propose a new approach called uniform race, which does not need these preset parameters. It picks samples based on a clever scoring system using random numbers and importance weights, guaranteeing good performance for any budget of samples. Their method matches or outperforms previous ones and works well even in tests on language model math tasks without tuning thresholds.
What this means in practice
- •For machine learning engineers: Use uniform race to sample from difficult probability distributions without needing to tune acceptance thresholds, improving efficiency in model training and inference.
- •For data scientists: Apply uniform race for better approximate sampling in probabilistic models where full distribution knowledge is missing, enhancing analysis accuracy with limited samples.
Authors
Seiyun Shin, Juhyeong Pang, Kwang-Sung Jun
Abstract
We study approximate sampling: given $N$ independent samples from a proposal distribution $μ$, the goal is to select one whose distribution is close to a target $π$ specified only up to a normalizing constant. Block and Polyanskiy (2023) provide finite budget error bounds for approximate rejection sampling (RS) as a function of the acceptance threshold $M$. The threshold $M$ giving the smallest bound, however, depends on properties of $(π,μ)$ that are typically unavailable from the observed sample. This raises a natural question: Can one attain the best RS guarantee without taking $M$ as input? We answer affirmatively by proposing a parameter-free sampling algorithm called uniform race (UR), based on importance weights, which are ratios of target to proposal probabilities (or densities). It divides each observed weight by an independent uniform random variable to form a score and returns the candidate with the largest score. For every budget $N$, its total variation error satisfies the RS upper bound for every fixed threshold $M$ simultaneously, thereby achieving the best such bound in hindsight. We also characterize its output distribution conditional on the largest score, identifying when it is exactly the target $π$. Uniform race has no larger total variation error than a natural budget-calibrated RS derived from Rohatgi et al. (2025) and sampling importance resampling (SIR). In particular, we exhibit instances where UR's error is exponentially smaller in $N$ than that of either baseline. Furthermore, we establish conditions under which attaining this RS guarantee for every $(π,μ)$ uniquely determines the selection probabilities as those of UR. Finally, test-time scaling experiments on LLM math-reasoning tasks corroborate the theoretical comparisons and demonstrate that UR remains competitive in ground-truth accuracy without requiring threshold selection.