Uniform Race: Parameter-Free Approximate Rejection Sampling

arXiv:2609.34639v2 Announce Type: replace-cross Abstract: Consider the approximate sampling problem: given $N$ independent samples from a proposal distribution $\mu$, the goal is to select one whose distribution is close to a target $\pi$ specified only up to a normalizing constant. The seminal work of Block & Polyanskiy (2023) provides a total variation (TV) error bound for approximate rejection sampling (RS) as a function of the algorithm's acceptance threshold $M$. The ideal threshold $M$ that minimizes the bound, however, depends on properties of $(\pi, \mu)$ that are typically unavailable from the observed sample. This raises a natural question: Can one attain the best RS guarantee without taking the best $M$ as input? We answer this question affirmatively by proposing a parameter-free sampling algorithm called uniform race (UR). UR computes a score for each sample $y$ that is the importance weight $\pi(y)/\mu(y)$ divided by an independent uniform random variable and then returns the one with the highest score. We prove that UR attains the best $M$-tuned TV error bound for RS. That is, UR, without knowing the best $M$, achieves the same performance guarantee as RS that takes the best $M$ as input. We also prove that UR has no larger TV error than the budget-calibrated version of the rejection sampler of Rohatgi et al. (2025) and sampling importance resampling (SIR). In particular, we identify instances where UR's error is exponentially smaller in $N$ than that of these two baselines. Furthermore, we establish conditions under which attaining this RS guarantee for every $(\pi, \mu)$ uniquely determines the selection probabilities as those of UR. Finally, test-time scaling experiments on LLM reasoning tasks corroborate the theoretical comparisons and demonstrate that UR remains competitive without requiring threshold selection.