acceptodds
Under review as a conference paper at ICLR 2027

Uniform Race: Parameter-Free Approximate Rejection Sampling

Abstract

We study approximate sampling: given 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. The seminal work of Block and Polyanskiy (2023) provides finite budget error bounds for approximate rejection sampling (RS) as a function of the algorithm's acceptance threshold . The threshold 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 as input?* We answer this question 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 , its total variation error satisfies the RS upper bound for every fixed threshold 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 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.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
Approximate sampling, importance sampling, Monte Carlo, rejection sampling, sampling importance resampling, test-time scaling

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 4 reviews, above 85% of the others.
Reviewer_fB3xOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

The paper proposes Uniform Race (UR) approximate sample rejection algorithm with a simple stochastic scoring scheme to reject the samples. The method leads to omission of the rejection threshold, a parameter that requires some knowledge of target-proposal density ratio, and has guaranteed total variation error lower than limited-budget RS upper bound. This bounds holds with any budget N and threshold M, without dependence on the importance weight envelope, tuning a threshold or other parameters. While simple in principle the algorithm is accompanied with supporting theory and empirical results showing its superiority in budget-efficient sampling error in comparison the baselines SIR and budget calibrated RS.

Critical strengths

The proposed method has several interesting properties: it eliminates the need to know the importance weight envelope for RS, or adjust a rejection threshold M for each sampling target/budget. The paper presents a rather detailed theoretical study on the efficiency of the UR method in relation to limited-N RS total variation upper bounds, providing a minimax bound over the sample selection procedure over any proposal-target pairs, and proving the uniqueness of a stochastic sample selection procedure satisfying this bound up to a constant factor. The paper further studies the induced total variance error of UR algorithm relevant to budget-bounded RS and SIR. (I did not go over the proofs in the Appendix.) And provides an appealing real world experiment to support the theoretical material.

Critical weaknesses

The writing is focused too much on the details of proofs and examples that appear unnecessary to convey the message of the paper. While the UR idea and the supporting theory are fundamentally interesting, it is difficult to follow the paper through the the technical details. I would recommend restructuring and polishing the material and moving unnecessary examples and details to the appendix. And maybe use the related work in the main text to setup the motivation for the proposed method.

Some of the sentences are too long and not completely clear when read the first time: e.g. line 90: "Consequently, the threshold giving the best guarantee hinges on the unknown target–proposal pair, including importance weights that may never appear among the N observed candidates. " Such sentences need more elaboration.

The introduction of the propositions and binary examples seem to be out of order. Proposition 1 is introduced without sufficiently motivating the results. Corollary 1 seems logically preceding Corollary 2 and Theorem 4. While Theorem 4 is directly relevant to the UR algorithm and Corollary 2 is a peripheral development. Theorem 2 and 3 are testament to the validity of the claims mentioned in the introduction but intervened with arbitrary details of special cases several times. making it necessary to reread several sections.

Some of the more urgent and interesting properties of UR are left unstudied or explicitly mentioned. With N→∞N\to\infty UR sample distribution converges to the exact target? If not what is the discrepancy in the limit? Is this a trivial property deduced from the rest of the paper?

While the paper is more focused on theoretical analysis of toy binary examples, it lacks more rigorous empirical study.

Minor typos:

132: , and even when -> omit and

171: HMcH_M^c is not defined

Questions for authors

Can the authors prove the asymptotic properties of the UR method, as N→∞N\to\infty e.g. convergence rate?

Is the uniform scaling sample selection also a good approach for resampling?

Comparing the proposed algorithm to other sampling method other than simple baselines seems appropriate to show if the method is indeed performing well in the considered experiment. Also addition of more synthetic benchmarks that are used for evaluation of sampling algorithms in high-dimensional multi-modal scenarios seems appropriate.

How is the accuracy gap total variation bound derived on line 484?

Why are all sampling methods with β=0.85\beta=0.85 converging to values worse than perfect?

As the UR idea is novel and interesting I would consider reevaluating the rating if any of the proposed modification are made to improve the paper.

Reviewer_n7FHOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies approximate sampling: given NN samples from a proposal μ\mu, select one whose distribution is close to a target π\pi known only up to a normalizing constant. Usual methods like finite-budget rejection sampling need a threshold MM, and the best MM depends on unknown properties of (π,μ)(\pi, \mu).

The paper proposes uniform race (UR), which divides each unnormalized weight by an independent uniform random variable and returns the candidate with the largest score. They prove that UR satisfies the rejection sampling bound for every threshold simultaneously, so no threshold needs to be chosen. They also show that UR is never worse than SIR or a budget-calibrated rejection sampler. LLM experiments on GSM8K and MATH500 support the theory.

Critical strengths
  1. A simple rule with a strong guarantee

UR removes the need to tune a threshold, costs nothing extra, and matches the best RS guarantee. For bounded weights, its error is the best that any method choosing among the NN samples can achieve. The proofs are clean and easy to follow. The key idea is that, once the largest score is fixed, the output follows the target restricted to smaller weights.

Critical weaknesses
  1. The novelty of the algorithm is unclear from the main text

UR is a special case of priority sampling (Duffield et al., 2007), but this is only mentioned in the appendix. The main text has no related work section, and the introduction presents UR as a new method. A reader who only reads the main paper would miss this. The contribution is the analysis, and this should be stated upfront.

  1. The experiments validate the theory but not the practical value

The response pool is fixed and finite, so πβ\pi_\beta is known exactly, the weights are bounded, and N reaches the pool size. In this setting, Theorems 2–3 guarantee that UR wins. The paper does not test the realistic case where N is much smaller than the space of possible responses (for example, sampling N fresh prompts each time). That would help understand the practical value of the algorithm compared to other methods.

Questions for authors
  1. Theorem 1 compares UR to an upper bound on RS’s error. Is UR also better than the actual error of RS with the best threshold?
  2. The largest gains appear when the weights are bounded and NN is large compared to them. How does UR compare to SIR when the weights are very large, for example at small β\beta in your experiments?
Reviewer_ZEwqOpenReview ↗
Rating
3(−1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper considers the following problem: given NN i.i.d samples Y1,Y2,…,YNY_1, Y_2, \ldots, Y_N from a proposal distribution μ\mu, output a R.V. Y^\hat{Y} whose distribution is closest in total variation dTVd_{TV} to a target π\pi, where the algorithm only additionally has access to the un-normalized ratio of distributions, a.k.a. "weights" w(y)∝π(y)/μ(y)w(y) \propto \pi(y) / \mu(y), for each y=Yiy = Y_i.

A natural baseline here is rejection sampling: using uniform i.i.d U1,…,UNU_1, \ldots, U_N, it returns the first among Y1,Y2,…,YNY_1, Y_2, \ldots, Y_N such that Ui≤min⁡w(Yi)/M,1U_i \leq \min \\{w(Y_i) / M, 1\\}, where M is a hyper parameter that's needed since the ratio π/μ\pi / \mu is known only up to a constant multiplicative factor. The dTVd_{TV} bound for rejection sampling trades off the error due to rate of rejection (error increasing in MM), and the probability of a non-rejected / accepted sample being drawn from target π\pi (error decreasing in MM).

The paper proposes a hyper parameter free algorithm, termed "Uniform Race" (UR), that matches the best possible error of rejection sampling (the infimum over all values of the hyper parameter MM). UR returns YiY_i where i=arg⁡max⁡jw(Yj)Uji = \underset{j}{\arg\max} \frac{w(Y_j)}{U_j}. The paper's main theoretical result is Theorem 1, which upper bounds the dTVd_{TV} of UR w.r.t π\pi, a bound that matches that of rejection sampling for any M>0M > 0. To complement the upper bound, the paper also proves several results showing UR to be better than known variants of rejection sampling (called budget-calibrated RS here, adapted from Rohatgi et al. (2025)), and SIR (Sampling Importance Resampling, from e.g. Rubin 1987). It also proves some stronger results: Corollary 1 shows that any algorithm that only returns one of YiY_i cannot do better asymptotically in NN than the exponential upper bound for UR for a class of proposal, target (π,μ)(\pi, \mu) pairs with almost surely bounded ratios (i.e. weights ww). Under the same assumptions, they prove in Theorem 4 that an algorithm that further depends only on the relative wrights of samples, and is whose sample selection probabilities are permutation-invariant, and which has exponentially decaying upper bound in NN on dTVd_{TV} for all (π,μ)(\pi, \mu) pairs, must also match the selection probabilities of UR.

Critical strengths
  • The paper makes a solid and novel (to the best of my knowledge) theoretical contribution. UR cleverly uses extra randomness (in the form of uniform draws) to eliminate the choice of hyper parameter in rejection sampling.

  • The proofs are rigorous and are explained intuitively in the main paper. The exposition of the paper (albeit with help from AI) is quite nice.

Critical weaknesses

The only critical weakness would be the practical usefulness of UR: since UR matches rejection sampling with the right hyper parameter MM, are there many practical cases where MM could not be approximately guessed a piori (from knowledge of propoal and target distributions)?

Questions for authors

Since rejection sampling would work and have the same dTVd_{TV} bound even if a single independent UU was drawn and re-used for every YiY_i, but UR would not work as far as I can tell without NN i.i.d UiU_i, perhaps highlight this use of extra randomness in the main paper? This is not necessarily a drawback of UR, but worth mentioning.

Reviewer_i7q7OpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper concerns the problem of selecting one sample from N i.i.d. proposals whose marginal distribution approximates a target distribution known up to a normalizing constant. The authors propose Uniform Race (UR), which selects the candidate maximizing its importance weight divided by an independent uniform random variable, without requiring a rejection threshold. The authors first characterize the conditional distribution of the selected sample (Proposition 1), then establish an adaptive TV error bound matching the best fixed-threshold rejection sampling bound (Theorem 1), along with convergence rates and minimax optimality (Corollary 1). They further show that UR outperforms a budget-calibrated rejection sampling method (Theorem 2) and dominates sampling importance resampling (SIR) in general convex ff-divergences (Theorem 3). Finally, they establish a uniqueness characterization of UR's selection probabilities under structural assumptions (Theorem 4).

Critical strengths

The paper is very well-written, with clear presentation and intuitive explanations. I appreciate that the problem formulation is well-suited to inference-time algorithms, where one aims to select a high-quality sample from a fixed budget of proposals. A major strength is that the authors provide novel theoretical insights into UR from several complementary perspectives (conditional output distribution, adaptive rejection sampling guarantee, convergence rates and minimax optimality, and uniqueness characterization). They further establish strong theoretical comparisons with existing sampling methods, including dominance over SIR in general convex f-divergences. The illustrative binary examples effectively explain the intuition and demonstrate the potentially exponential improvement in convergence rates.

Critical weaknesses
  1. I have concerns about the novelty of the method and analysis. Although the method is presented in a one-shot sampling formulation, the selection rule is a special case of classical priority sampling (Duffield et al., 2007). Moreover, some convergence guarantees, particularly Corollary 1, resemble existing results for independent Metropolis–Hastings (Mengersen and Tweedie, 1996; Deligiannidis et al., 2026). Since UR achieves convergence by increasing the number of proposals (N), while MCMC achieves convergence through the number of transitions (T), insights from the well-established MCMC convergence literature may be closely transferable. In this regard, I believe a more detailed discussion of these connections is needed to clarify the novelty of the theoretical contributions.
  2. The exponential convergence and minimax guarantees in Corollary 1 and the uniqueness result in Theorem 4 rely on C∞π<∞C_\infty^\pi<\infty, which can be restrictive for continuous distributions. Even when satisfied, this constant may grow exponentially with dimension.
Questions for authors

1.Could the authors further discuss the connections to existing MCMC methods and convergence results to clarify the novelty of their contributions? 2.Could the authors discuss when the C∞π<∞C_\infty^\pi<\infty assumption is reasonable and how the argument will change if this assumption is not satisfied?

Comments on the paper

5 comments
AuthorsOpenReview ↗

Common response to the reviewers

We thank the reviewers for their thoughtful comments. We have revised the manuscript in response to the reviewers' comments. Key revisions are highlighted in blue. Unless otherwise noted, all references to the manuscript below refer to the revised version. Below, we first clarify the contribution and its relationship to existing sampling methods, then address each review.

We study how closely a selected sample follows the target distribution when only a fixed number of proposal samples are available. The selection rule is the classical priority sampling rule used to retain one candidate (Duffield et al., 2007). We call its use for this sampling problem uniform race (UR). Our contribution is to establish UR as a parameter-free method for approximate sampling with a fixed budget, with three main results.

  1. Threshold adaptation. UR satisfies the fixed threshold rejection sampling bound for every threshold simultaneously. It uses only the observed unnormalized weights and does not need a threshold or extra samples to estimate one. See Theorem 1.
  2. Comparison with SIR and calibrated RS. At the same total proposal budget, UR has no greater marginal TV error than SIR or the specified budget-calibrated RS procedure. See Theorems 2 and 3.
  3. Uniqueness of the selection probabilities. Theorem 4 characterizes the selection rules that satisfy the bounded weight guarantee uniformly over all positive target-proposal pairs on finite state spaces. Within the stated class of rules, this requirement uniquely determines the selection probabilities as those of UR.

The marginal output distribution includes the randomness in both generating the candidates and selecting the returned sample. The updated Table 1 summarizes the error bounds and required inputs.

Sampling ruleMarginal TV upper boundExtra input
SIRCπ/NC^{\pi}/N (Agapiou et al., 2017)None
RS with M=C∞πM=C _ {\infty}^{\pi}F(C∞π,N)F(C _ {\infty}^{\pi},N)Exact envelope ZMZM
Budget-calibrated RS$F(\Theta(N/\log(4/\delta _ {\mathrm{cal}})),N)+(C^{\pi}/N)\mathbf{1}\lbrace N\lesssim C _ {\infty}^{\pi}\log(4/\delta _ {\mathrm{cal}})\rbrace $Calibration parameter δcal\delta _ {\mathrm{cal}}
UR(inf⁡M>0F(M,N))∧Cπ/N(\inf _ {M > 0}F(M,N))\wedge C^{\pi}/NNone

Here F(M,N):=2EM(π,μ)+exp⁡(−N/M)F(M,N):=2\mathcal{E} _ {M}(\pi,\mu)+\exp(-N/M), where EM(π,μ):=Eμ[(w−M)+]\mathcal{E} _ {M}(\pi,\mu):=\mathbb{E} _ {\mu}[(w-M) _ {+}] and w:=dπ/dμ.w:=d\pi/d\mu. Write Cπ:=Eμ[w2]C^{\pi}:=\mathbb{E} _ {\mu}[w^{2}] and C∞π:=ess sup⁡μwC _ {\infty}^{\pi}:=\operatorname{ess\thinspace sup} _ {\mu}w. The table omits fixed numerical factors and the additional minimum with 11. Calibrated RS uses N≥3N \geq 3 and chooses δcal∈(0,1)\delta _ {\mathrm{cal}}\in(0,1) before drawing the samples used to estimate the normalizing constant.

Contribution to approximate sampling

We agree that the connection to priority sampling should be stated when UR is introduced in the main text. The original submission acknowledged this connection in Appendix A. Classical priority sampling uses selected items to estimate sums of weights. We study how closely one selected sample follows a target distribution. To our knowledge, this use of the one-item priority rule for fixed budget approximate sampling had not been studied before our work. The rule also arises naturally from the finite budget RS problem. Rather than selecting a threshold in advance, UR chooses the largest threshold that still accepts at least one observed candidate. In particular, with the candidate batch and independent acceptance uniforms UiU_i fixed, candidate ii is accepted at threshold τ\tau if and only if τ≤wu(Yi)/Ui\tau \leq w_u(Y_i)/U_i. Therefore, the largest such threshold is max⁡iwu(Yi)/Ui\max_i w_u(Y_i)/U_i, which directly gives the UR selection rule. However, this threshold depends on the observed candidates and uniforms, so the fixed threshold RS bound does not directly apply. We establish Theorem 1 by characterizing UR's conditional output distribution and comparing its error with RS at every fixed threshold. We now make the attribution and distinction explicit when introducing UR in Section 1, with further discussion in Appendix A. We provide a more detailed explanation of the design motivation and theoretical contributions in our follow-up response to Reviewer ZEwq.

Connection to Metropolis-Hastings

We also establish an exact connection to independent Metropolis-Hastings (IMH), which processes candidates one at a time. If IMH starts from one draw from the proposal and processes N−1N-1 further independent draws, its final output has the same distribution as UR with NN proposals. UR realizes this distribution through a one-shot batch selection based on independent randomized scores, without constructing intermediate Markov states. Our response to Reviewer i7q7 explains why this holds and which existing IMH bounds therefore apply to UR. The connection is summarized in Section 5, with Theorem 5 and its proof in Appendix J of our revised manuscript.

Thank you for your rebuttal. It is good to see the new result and the experiments, and they affect my judgement of the paper positively. However, as pointed out by other reviewers, the algorithm is very close to the priority sampling algorithm, which weakenes the novelty of the paper. Hence, I have decided to keep my score unchanged.

Best regards, Reviewer n7FH

AuthorsOpenReview ↗

Thank You for the Constructive Discussion

We sincerely thank the reviewer for the thoughtful assessment and for recognizing the value of our additional theoretical and empirical results.

We understand the concern regarding novelty and respect the reviewer's assessment. We have made some updates to our common response and provided a more detailed clarification in our follow-up response to Reviewer ZEwq. We are also preparing further refinements to clarify our contributions relative to classical priority sampling. Since edits to the common response do not generate separate notifications, we wanted to highlight these updates here. We would appreciate the reviewer's consideration of these clarifications.

Thank you again for the constructive discussion. We would be happy to address any further questions or concerns.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.