Uniform Race: Parameter-Free Approximate Rejection Sampling

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.

Query-Efficient Rejection Sampling for Parallel Masked Diffusion
Shiyuan Zhang, Xuheng Li, Qiwei Di +1
arXiv15 Oct 2026PreprintCC BY 4.0Full textProbability StatisticsarXiv
Approximate Matrix Multiplication through Joint Leverage Score Sampling
Neophytos Charalambides, Mert Pilanci, Alfred O. Hero III
arXiv21 Oct 2026PreprintCC BY 4.0Full textNumerical analysis & scientific computingarXiv
An approximate zero bias transformation for random sums: Applications to sampling with outliers, auto insurance, and generative AI
Wasamon Jantai, Nathakhun Wiroonsri
arXiv29 Oct 2026PreprintCC BY 4.0Full textProbability StatisticsarXiv
Uniform Sampling of Linear Codes with Prescribed Hull Dimension
Keita Ishizuka
arXiv2 Nov 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
Uniform transport processes and the Brownian sheet:the one-parameter rate of convergence is preserved
Carles Rovira
arXiv16 Oct 2026PreprintCC BY 4.0Full textProbabilityarXiv

Cite

BibTeX RIS

BibTeX

@misc{shin2026uniform,
  title = {{Uniform Race: Parameter-Free Approximate Rejection Sampling}},
  author = {Seiyun Shin and Juhyeong Pang and Kwang-Sung Jun},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.34639},
  eprint = {2609.34639},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.34639},
}

RIS

TY  - UNPB
TI  - Uniform Race: Parameter-Free Approximate Rejection Sampling
AU  - Seiyun Shin
AU  - Juhyeong Pang
AU  - Kwang-Sung Jun
PY  - 2026
DA  - 2026/09/28
PB  - arXiv
DO  - 10.48550/arxiv.2609.34639
UR  - https://arxiv.org/abs/2609.34639
AB  - 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.
ER  -

Abstract

Related

Cite