# Uniform Race: Parameter-Free Approximate Rejection Sampling

arXiv: https://arxiv.org/abs/2609.34639 · HTML: https://mlsanity.com/paper/2609.34639/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 25 references that are in the map.
- First posted on arXiv 28 Sep 2026.

## Builds on (most cited first, 14 of 14)

- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [Direct Preference Optimization: Your Language Model is Secretly a Reward Model](https://mlsanity.com/paper/2305.18290/) (2023)
- [Measuring Mathematical Problem Solving With the MATH Dataset](https://mlsanity.com/paper/2103.03874/) (2021)
- [Let's Verify Step by Step](https://mlsanity.com/paper/2305.20050/) (2023)
- [OpenAssistant Conversations -- Democratizing Large Language Model Alignment](https://mlsanity.com/paper/2304.07327/) (2023)
- [Sequence Tutor: Conservative Fine-Tuning of Sequence Generation Models with KL-control](https://mlsanity.com/paper/1611.02796/) (2016)
- [Is Best-of-N the Best of Them? Coverage, Scaling, and Optimality in Inference-Time Alignment](https://mlsanity.com/paper/2503.21878/) (2025)
- [Human-centric Dialog Training via Offline Reinforcement Learning](https://mlsanity.com/paper/2010.05848/) (2020)
- [Soft Best-of-n Sampling for Model Alignment](https://mlsanity.com/paper/2505.03156/) (2025)
- [Best-of-N through the Smoothing Lens: KL Divergence and Regret Analysis](https://mlsanity.com/paper/2507.05913/) (2025)
- [Taming Imperfect Process Verifiers: A Sampling Perspective on Backtracking](https://mlsanity.com/paper/2510.03149/) (2025)
- [The Sample Complexity of Approximate Rejection Sampling with Applications to Smoothed Online Learning](https://mlsanity.com/paper/2302.04658/) (2023)
- [On importance sampling and independent Metropolis-Hastings with an unbounded weight function](https://mlsanity.com/paper/2411.09514/) (2024)

## Abstract (arXiv)

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.