PaperlayerView exact revision on arXiv

Source-linked AI summary

Uniform Race: Parameter-Free Approximate Rejection Sampling

Seiyun Shin, Juhyeong Pang, Kwang-Sung Jun

arXiv:2609.34639v1cs.LGstat.ML

TL;DR

Selecting from a finite proposal sample to approximate a target known only up to normalization is difficult when the best fixed rejection-sampling threshold depends on the target–proposal pair. UR ranks candidates by importance-weight/uniform scores and meets every fixed-threshold RS bound simultaneously.

  • Problem

    The task is to select from N proposal samples to approximate a target specified only up to a normalizing constant, without knowing which fixed RS threshold gives the best bound.

    Source: §1 · pp. 1, 3

  • Method

    UR divides each candidate’s importance weight by an independent uniform variable and returns the candidate with the largest score.

    Source: §1 · p. 2, §2 · p. 4

  • Results

    UR’s TV error satisfies the RS upper bound for every fixed threshold simultaneously, attaining the best such bound in hindsight.

    Source: §1 · p. 3

  • Takeaways & Limitations

    Among rules using relative observed weights symmetrically across target–proposal pairs, the universal RS guarantee uniquely determines UR’s selection probabilities.

    Source: §5 · p. 9

    The uniqueness claim applies only to rules using relative observed weights, applying across all target–proposal pairs at fixed N, and treating candidate order symmetrically.

    Source: §5 · p. 9

Abstract

from arXiv · show

We study approximate sampling: 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. 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 $(\pi,\mu)$ 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 $\pi$. 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 $(\pi,\mu)$ 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.

1 INTRODUCTION

Finite-budget rejection-sampling guarantees depend on a threshold tied to unknown target–proposal properties. Uniform race removes threshold selection while meeting the fixed-threshold guarantee simultaneously.

1 INTRODUCTION

  • For every fixed threshold M, UR satisfies the RS error bound simultaneously, so its guarantee is the best fixed-threshold bound in hindsight.The sampler does not need to take M as input.Source: §1 · p. 3
  • For bounded importance weights, UR achieves a sharp TV-error bound without being given the weight envelope.The bound matches the smallest possible worst-case error over each bounded-weight class.Source: §1 · p. 3
  • Conditional on the largest score exceeding the weight bound, UR’s output is exactly the target distribution, although UR need not know that bound.This is a conditional output-law characterization, not a claim that the full marginal output law is always the target.Source: §1 · p. 3
  • UR has no greater TV error than budget-calibrated RS and SIR; on a fixed binary pair, its error can be exponentially smaller than either baseline’s.The budget-calibrated RS comparison is attributed to Rohatgi et al. (2025); SIR references Rubin (1987) and Smith & Gelfand (1992).Source: §1 · p. 3
  • Under specified structural restrictions, the universal RS guarantee uniquely determines candidate selection probabilities as UR’s.The rule must use relative observed weights, apply across target–proposal pairs, and treat candidate order symmetrically.Source: §1 · p. 3
  • Numerical experiments on LLM tasks corroborate the theoretical comparisons, and UR remains competitive in ground-truth accuracy without threshold tuning.On the displayed binary pair, UR combines the sharp RS guarantee without an envelope input and matches RS supplied with the exact envelope.Source: §1 · p. 3, Table 1 · p. 3

2 RS GUARANTEES WITHOUT A THRESHOLD

UR’s error is bounded by the fixed-threshold RS guarantee for every threshold, without requiring the sampler to choose one. Its conditional output law and bounded-weight guarantees explain this result and its scope.

2 RS GUARANTEES WITHOUT A THRESHOLD

  • UR satisfies the fixed-threshold RS error bound for every M, so optimizing over M in the analysis requires no threshold choice by the sampler.The proof compares UR and fixed-threshold RS using the same candidates and uniforms.Source: §2 · p. 4

2.1 OUTPUT DISTRIBUTION AT A FIXED LARGEST SCORE

  • Given largest score s, UR’s output is π renormalized over states with w<s; with bounded weights, conditioning on a score above the bound yields exactly π.The budget affects the distribution of the largest score, not this conditional target rule.Source: §2.1 · p. 4

2.2 ACCEPTANCE PROBABILITY AND CONDITIONAL ERROR

  • At threshold M, one-proposal acceptance is AM/M, the fixed-threshold accepted law has TV error at most EM, and UR’s conditional error is no larger.The probability all N proposals are rejected is (1 - AM/M)^N.Source: §2 · p. 4, §2.2 · p. 5

2.3 BOUNDED WEIGHTS AND MINIMAX ERROR

  • For finite Cπ∞, UR’s TV error is bounded by (1 - 1/Cπ∞)^N, matching the minimax worst-case error over the bounded-weight class.Here Cπ∞ is the essential upper bound on the importance weight.Source: §2.3 · p. 5

3 COMPARISON WITH BUDGET-CALIBRATED RS

Budget-calibrated rejection sampling estimates the normalizer from pilot samples before setting its threshold, but can be less accurate than UR. UR compares favorably in a fixed-pair separation and across all target–proposal pairs.

3 COMPARISON WITH BUDGET-CALIBRATED RS

  • Budget-calibrated RS estimates Z from pilot proposals, sets its threshold using δ, then tests fresh candidates in order and returns a fresh-proposal fallback if none is accepted.Its total maximum budget is N = 2n + 1, with at most one proposal unused for general integer budgets.Source: §3 · p. 6

3.1 EXPONENTIAL SEPARATION FOR FIXED TARGET–PROPOSAL PAIR

  • On the fixed binary pair, UR’s exact TV error is (3/4)3^-N, while the gap over calibrated RS can grow exponentially with budget even after calibration is optimized.The comparison uses µ = (1/2, 1/2) and π = (1/4, 3/4).Source: §3.1 · pp. 6–7

3.2 GENERAL COMPARISON

  • Across positive-weight target–proposal pairs, UR has no greater TV error or convex f-divergence than budget-calibrated RS, even using only its fresh-sampling share of the budget.Giving UR the full budget cannot increase its divergence from π.Source: §3.2 · p. 7

4 COMPARISON WITH SAMPLING IMPORTANCE RESAMPLING (SIR)

At a fixed proposal budget, UR improves on SIR by favoring larger importance weights, and its TV error is no greater for general target–proposal pairs. On a fixed binary pair, UR’s error decays exponentially in N while SIR’s decays as 1/N.

4 COMPARISON WITH SAMPLING IMPORTANCE RESAMPLING (SIR)

  • SIR selects a candidate with probability proportional to its importance weight, while UR ranks candidates by weight divided by an independent uniform draw.The comparison considers both a binary example and general distributions at the same proposal budget.Source: §4 · p. 7

4.1 EXAMPLE WHERE UR AND SIR DIFFER

  • On mixed batches, UR selects the higher-weight state more often than SIR’s target-proportional choice, partially compensating for unequal errors from homogeneous batches.SIR’s mixed-batch choice alone does not make its marginal output exact because homogeneous batches contribute unequal errors.Source: §4.1 · p. 8

4.2 COMPARISON FOR GENERAL DISTRIBUTIONS

  • UR has no greater TV error than SIR for every fixed N and target–proposal pair, and also compares favorably under every convex f-divergence.The proof uses tail-probability ordering together with a monotone density property to control the set attaining TV error.Source: §4.2 · p. 8
  • On a fixed binary pair, UR’s error decreases exponentially in N, whereas SIR’s decreases as 1/N.The separation persists when both states appear in nearly every batch and extends to every fixed nontrivial pair with bounded positive weights.Source: §4.2 · p. 8

5 UNIQUENESS OF THE SELECTION PROBABILITIES

The paper asks whether a universal bounded-weight RS guarantee determines the selection probabilities. Under restrictions on information and order symmetry, it does: the probabilities must coincide with UR’s.

5 UNIQUENESS OF THE SELECTION PROBABILITIES

  • Under those restrictions, a finite bounded-weight guarantee uniform over positive target–proposal pairs forces the selection probabilities on every fixed positive weight vector to match UR’s.The condition ranges over all pairs at fixed N.Source: §5 · p. 9
  • A selection rule may use only observed weights up to a common factor, must apply across target–proposal pairs, and must treat candidate order symmetrically.UR and SIR satisfy these restrictions.Source: §5 · p. 9
  • Conversely, UR satisfies the bounded-weight guarantee with L_N = 1; another rule may still have smaller error on a particular pair without meeting the universal requirement.The uniqueness result is about the guarantee across all pairs, not pairwise optimality.Source: §5 · p. 9

6 TEST-TIME SCALING EXPERIMENTS

In controlled LLM math-reasoning experiments, UR has lower TV error than budget-calibrated RS and SIR while remaining comparable to envelope RS. The section also situates UR relative to related sampling methods and develops proof ingredients for the RS comparison and conditional output law.

6 TEST-TIME SCALING EXPERIMENTS

  • Controlled LLM experiments on math reasoning tasks approximate a reward-tilted target policy (soft BoN) and assess sampling fidelity via TV distance alongside ground-truth answer accuracy.On GSM8K, they vary sampling budget N and temperature β; estimates use 106 Monte Carlo trials, with accuracy defined as the probability that the selected response has the correct final answer. They also evaluate MATH500 and observe the same trends.Source: §6 · p. 9
  • Across the reported GSM8K settings, UR has lower TV error than budget-calibrated RS and SIR, remains comparable to envelope RS, and decays faster before the Monte Carlo floor.For β = 0.85, UR approaches the common target accuracy at a smaller budget; for β = 0.15, accuracy is already close despite visible TV differences at larger budgets.Source: §6 · p. 10, Figure 1 · p. 10

A RELATED WORK

  • UR is a one-item instance of classical priority sampling, but this paper studies the marginal law of a selected random candidate rather than subset-sum estimation.The related-work discussion also distinguishes SIR’s finite-pool marginal law from the target and contrasts one-shot selection with IMH’s Markov chain.Source: A RELATED WORK · pp. 12–13

B PROOF OF THE RS BOUND

  • The RS-bound proof compares conditional output errors, derives the clipping error, and extends the results to zero weights.The section overview identifies these as the components used to establish Theorem 1.Source: B PROOF OF THE RS BOUND · p. 13

B.1 PROOF OF LEMMA 2

  • A density comparison gives a TV ordering when one density ratio is nonincreasing and its ratio to the other is nondecreasing.This comparison lemma is applied to prove the RS-bound comparison.Source: §B.1 · pp. 13–14

B.2 PROOF OF PROPOSITION 1

  • For a fixed score, the chance that a candidate is selected includes a factor independent of its state, enabling the joint score-and-candidate law to be derived.Independence of the other candidates supplies the factor G(s)^(N−1).Source: §B.2 · p. 14

B.3 CONDITIONING ON THE LARGEST SCORE

  • Conditioned on the largest score exceeding the target’s maximum importance weight, the returned candidate has distribution π.The budget affects the distribution of the largest score, not this conditional target rule.Source: §B.3 · p. 15

B.4 ACCEPTED SAMPLES AND THE EVENT OF NO ACCEPTANCE

The appendix relates rejection-sampling outputs to acceptance and no-acceptance events, extends the analysis to zero weights, and derives an exponential relaxation. It also records the condition behind a budget-calibrated RS sufficient guarantee.

B.4 ACCEPTED SAMPLES AND THE EVENT OF NO ACCEPTANCE

  • The clipping bound sharpens to an exact identity, with the accepted-law error bounded by E_M/A_M ≤ E_M.The argument uses A_M ≤ 1 and monotonicity of the clipping excess in its threshold.Source: §B.4 · p. 15

B.5 ZERO IMPORTANCE WEIGHTS

  • With zero weights, UR and SIR agree when every observed weight is zero, and their bounded-weight conclusion remains unchanged.The general f-divergence statement retains the positive-weight assumption.Source: §B.5 · p. 16

B.6 EXPONENTIAL RELAXATION: DERIVATION OF EQUATION 5

  • The exponential relaxation reallocates part of the rejection-probability bound to clipping; exp(-N/M) alone is not asserted to bound rejection when clipping occurs.The derivation uses convexity of the exponential and A_M = 1 - E_M.Source: §B.6 · p. 16

C.1 BASELINE AND ITS CONDITIONAL LAW

  • Budget-calibrated RS has a sufficient-budget condition when δ is supplied as an accuracy input, but the comparisons concern its actual output law without assuming that condition.When the threshold is unbounded, the accepted law is exactly π; normalizer estimation affects error through clipping and complete rejection.Source: §C.1 · p. 17
  • Conditional on the pilot, fresh trials use a fixed normalized threshold, and complete rejection triggers a fresh proposal fallback.The accepted law is Q_RS_T and the probability all n trials fail is r_T^n.Source: §C.1 · p. 17

C.2 PROOF OF THEOREM 2

The proof compares budget-calibrated rejection sampling with UR by conditioning on its independent pilot and then comparing selection behavior at a fixed threshold. It extends the comparison to divergences and equal proposal budgets.

C.2 PROOF OF THEOREM 2

  • UR has no greater total variation error than budget-calibrated RS at the same proposal budget.The comparison also extends to convex f-divergences and does not require the baseline's stated sufficient condition.Source: §C.2 · pp. 17, 19
  • Conditioning on the pilot and threshold randomization makes the threshold fixed; a random permutation represents the rejection stage as uniform selection among accepted indices, or all indices if none are accepted.The last candidate is the fallback, so its virtual acceptance indicator does not affect the output.Source: §C.2 · p. 17
  • At a fixed threshold, retaining candidates by clipped acceptance and choosing uniformly among them, with a uniform fallback if none are retained, yields the comparison used in the proof.The fixed-batch selection probability for weights above any threshold is no smaller under UR.Source: §C.2 · pp. 17–18
  • The selection-stage comparison applies to any positive finite threshold set using an independent pilot and held fixed during rejection, but not arbitrary fallbacks or thresholds adapted to fresh candidates.The fresh-proposal fallback is essential to the argument.Source: §C.2 · pp. 18–19
  • UR's marginal divergences decrease with its proposal budget, allowing the selection-stage comparison to yield the same-budget assertion.The proof first compares selected weights and then applies a positive-part argument.Source: §C.2 · pp. 18–19

C.3 PROOF OF PROPOSITION 2: EXPONENTIAL SEPARATION ON A FIXED PAIR

These appendices establish separations for calibrated RS, give a local fixed-budget comparison, and provide moment-based bounds. They also relate UR's second-moment rate to SIR's and identify the constant supplied by a direct proof.

C.3 PROOF OF PROPOSITION 2: EXPONENTIAL SEPARATION ON A FIXED PAIR

  • For the fixed pair, UR and known-envelope RS have exact error (3/4)3^-N, while calibrated RS has an Ω(2^-N/2) lower bound for odd N ≥ 3.Both UR and calibrated RS require Θ(log(1/ξ)) proposals when tuned for prescribed accuracy ξ, despite their different fixed-pair error rates.Source: §2 · pp. 20–21

C.4 LOCAL SEPARATION UNDER OPTIMAL CALIBRATION

  • At fixed odd N ≥ 13, calibrated RS cannot match the bounded-weight benchmark up to a pair-independent constant, whereas UR and known-envelope RS attain it on the stated family.The local limits fix the budget; no remainder uniform in N is asserted.Source: §C.4 · pp. 21–23

D MOMENT BOUNDS AND MINIMAX RATES

  • For R ≥ 2, the second-moment minimax upper and lower bounds have the same dependence on R and N up to constants.This is a minimax statement over a moment-constrained class, not a lower bound for every fixed pair.Source: D MOMENT BOUNDS AND MINIMAX RATES · p. 23

D.1 DIRECT SECOND MOMENT UPPER BOUND

  • The direct second-moment argument conditions on the largest score and bounds the chance that all N scores fall below a threshold.It uses an independent target point and the identity E_π[w(X)] = C_π.Source: §D.1 · pp. 23–24
  • Under a second-moment constraint, UR's upper-bound rate is also available for SIR, with the direct UR proof giving constant 2/e without establishing its optimality.The cited SIR bound is min{1, 6C_π/N}; the direct UR proof supplies the constant 2/e.Source: §D.1 · p. 24

D.2 EXACT BOUNDED RATIO MINIMAX ERROR

The appendices establish a bounded-ratio minimax lower bound, a second-moment minimax lower bound, and the two properties used to compare UR with SIR.

D.2 EXACT BOUNDED RATIO MINIMAX ERROR

  • For any observed-candidate sampler, a binary pair yields TV error at least (1 - 1/C)^N in the limit, establishing the bounded-ratio minimax lower bound.The obstruction is the event that all N proposals miss the target state; for C = 1, π = μ and the first proposal is exact.Source: §D.2 · p. 24

D.3 SECOND MOMENT MINIMAX LOWER BOUND

  • For R ≥ 2, every observed-proposal procedure has error at least (1/32) min{1, R/N} for some finite strictly positive pair with C_π ≤ R.This lower bound matches the upper-bound dependence on R and N up to constants over the moment-constrained class.Source: §D.3 · pp. 24–25

E PROOFS FOR THE COMPARISON TO SIR

  • The SIR comparison proof combines UR's greater frequency of selecting weights above a threshold with a density relative to π that is nonincreasing in weight.Together these properties control the set attaining total variation error.Source: E PROOFS FOR THE COMPARISON TO SIR · p. 25

E.1 PROOF FOR CONVEX DIVERGENCES

The appendix compares uniform race (UR) with sampling importance resampling (SIR), establishes an equivalent Bernoulli selection rule, and outlines binary examples and bias calculations.

E.1 PROOF FOR CONVEX DIVERGENCES

  • UR's comparison with SIR extends from total variation to every convex f-divergence through a positive-part representation and approximation argument.The proof first handles convex piecewise-linear functions, then approximates a general convex function by an increasing sequence of such functions.Source: §E.1 · pp. 25–26

E.2 TWO SUPPORTING LEMMAS

  • For every threshold t > 0, SIR's probability of returning a weight above t is no greater than UR's, which is no greater than the target's.The same comparison holds at weights at least t; complements give the corresponding comparison below a threshold.Source: §E.1 · p. 26, §E.2 · p. 26

E.3 EQUIVALENT BERNOULLI SELECTION RULE

  • On each positive weight vector, UR is equivalent in selection probabilities to independently retaining each candidate with probability proportional to its weight and choosing uniformly among retained candidates.The retention probabilities use weights divided by the largest observed weight, and at least one candidate is always retained.Source: §E.3 · p. 27

F BINARY EXAMPLES AND BIAS CALCULATIONS

  • The binary-example subsection extends a two-candidate comparison across budgets and announces an RS equality for two weight values, alongside SIR bias calculations and a continuous example.The stated equality uses the threshold M = Cπ∞.Source: F BINARY EXAMPLES AND BIAS CALCULATIONS · p. 27

F.1 PROOF OF PROPOSITION 3: BINARY EXAMPLE FOR EVERY BUDGET

The proofs analyze SIR’s error from random candidate counts and normalization, show that UR removes the leading SIR bias under bounded positive weights, and develop binary and continuous examples. They also show that matching the stated error guarantees forces batchwise selection probabilities to agree with UR, first for two candidates and then for three by matching successive expansion coefficients.

F.1 PROOF OF PROPOSITION 3: BINARY EXAMPLE FOR EVERY BUDGET

  • In the binary example, both samplers return state 1 with probability below its target, and SIR’s leading error coefficient is strictly positive for every fixed 0 < ε < 1/2.The SIR gap is attributed to fluctuations in candidate counts, not only to batches that miss a state; the remainder constants may depend on ε.Source: §F.1 · p. 29

F.3 LEADING SIR BIAS

  • For every fixed nontrivial pair with bounded positive weights, SIR error is of order 1/N, whereas UR’s TV error decays exponentially.The SIR bias expansion has a remainder uniform over bounded measurable functions and requires no positive lower weight bound or inverse moment assumption.Source: §F.3 · p. 31

F.4 HOW UR CANCELS THE LEADING SIR BIAS

  • UR’s leading correction increases selection probabilities for candidates above the SIR-weighted average weight and decreases them below it, while its total mass is zero.This describes the leading term, not the exact sign of every finite-budget difference; the exponential UR target-error bound follows separately from equation 12.Source: §F.4 · pp. 32, 34

F.5 CONTINUOUS EXAMPLE

  • The continuous example takes μ uniform on (0, 1) and π(dy) = 2y dy, with target mean 2/3; UR’s mean error is reduced to scores below 2.The example evaluates SIR’s mean error using the leading-bias formula; its assumptions apply although w(y) approaches zero near the origin, because it is positive almost surely and bounded above.Source: §F.5 · p. 34

G PROOF OF THEOREM 4

  • The Theorem 4 proof fixes relative weights while varying proposal probabilities, under the structural restrictions on A stated in Section 5.The supplied passage introduces this proof setup but does not state its result.Source: G PROOF OF THEOREM 4 · p. 34
  • For N = 2, the second-order error guarantee forces the probability of selecting state 0 from a mixed batch to be q = 1/4, exactly UR’s probability.As the proposal probability η of state 0 tends to zero, any mismatch in the first-order term would violate the guarantee.Source: G PROOF OF THEOREM 4 · p. 35

G.1 THREE CANDIDATES SHOW HOW ACCURACY DETERMINES A BATCHWISE CHOICE

  • For three candidates, matching the cubic error bound first fixes the choice on (a, 1, 1), then forces the choice on (a, b, 1) to equal UR’s probability.The mixed η1η2 coefficient of the sampler is −2a + 6x; matching the target coefficient determines x, and the general proof repeats this procedure in increasing order of lower-weight candidates.Source: §G.1 · p. 36

G.2 GENERAL PROOF IN THREE STEPS

The proof varies the frequencies of fixed relative weights to recover batchwise selection probabilities from a universal error guarantee. A separate construction shows that nonuniform divisors can also yield exponential convergence, with a slower rate than UR's bounded-weight guarantee.

G.2 GENERAL PROOF IN THREE STEPS

  • The proof holds relative weights fixed while making lower-weight states rare, so the universal guarantee can be tested as their frequencies shrink.The relative weights remain fixed as state frequencies and the common normalization change.Source: §G.2 · p. 36
  • Marginal output-probability differences are polynomials of degree at most N in the rare-state frequencies.The polynomial comes from summing conditional output differences over batch compositions.Source: §G.2 · p. 37
  • The error guarantee forces every polynomial term below degree N to vanish, and induction then identifies selection probabilities on every positive batch.Varying the rare-state proportions is essential; symmetry identifies individual probabilities within equal-weight groups.Source: §G.2 · pp. 37–38

H NONUNIFORM DIVISORS CAN ALSO CONVERGE EXPONENTIALLY

  • Nonuniform positive divisors can still give exponential convergence: conditional on any threshold crossing, the selected state has law π, though the rate is slower than UR's bounded-weight guarantee.The slower rate follows because only half of the divisor mass lies in the linear part of the CDF.Source: H NONUNIFORM DIVISORS CAN ALSO… · pp. 38–39

I EXPERIMENTAL DETAILS

The experiments use fixed response pools from two math-reasoning benchmarks to compare sampling procedures at varying budgets. They evaluate both fidelity to a reward-tilted target and ground-truth accuracy, estimating marginal output distributions through repeated trials.

I EXPERIMENTAL DETAILS

  • GSM8K and MATH500 provide the two evaluation settings, with a pre-generated pool of 4,096 responses for each evaluated problem.GSM8K contains 8.5K grade-level math word problems; MATH500 is a 500-question subset with competition-level problems.Source: I EXPERIMENTAL DETAILS · p. 39
  • The reference policy generates responses, which receive reward-model scores used to define a reward-tilted target over the finite empirical proposal.The samplers receive unnormalized importance weights, while the target’s normalizing constant is computed exactly for evaluation.Source: I EXPERIMENTAL DETAILS · pp. 39–40

I.1 SAMPLING ALGORITHMS

  • All four samplers receive the same N independent candidates and return one observed candidate; envelope RS accepts candidates in order and otherwise selects uniformly.Envelope RS uses a fixed threshold set to the maximum unnormalized weight in the response pool, serving as a proxy for the best fixed threshold in hindsight.Source: §I.1 · p. 40
  • Budget-calibrated RS uses pilot candidates to estimate the normalizer, then applies rejection sampling to fresh candidates with a budget-dependent threshold.Its calibration parameter δ is selected separately for each prompt, β, and budget; the reported value minimizes estimated TV error or maximizes accuracy, depending on the plot.Source: §I.1 · pp. 40–41

I.2 EVALUATION METRICS AND ESTIMATION

  • The evaluation reports total variation distance from the target as sampling fidelity and ground-truth accuracy as a complementary downstream measure.Accuracy need not rise with budget: the target accuracy may be above or below reference-policy accuracy.Source: §I.2 · p. 41

I.2.1 ESTIMATING THE TV ERROR ON A FINITE POOL

  • The TV estimate compares empirical output frequencies with the target over the finite response support, estimating each sampler’s marginal output law across independent trials.Each trial uses a fresh candidate set; reusing one set would estimate a conditional output law instead.Source: §I.2.1 · p. 41
  • Finite Monte Carlo trials make the plug-in TV estimate positive even for exact sampling, limiting distinctions once true error becomes sufficiently small.The exact-sampler baseline estimates this floor using the same number of trials.Source: §I.2.1 · pp. 41–42

I.3 FURTHER EXPERIMENTAL RESULTS

Across the displayed GSM8K prompts, UR’s estimated TV error is below or comparable to SIR and budget-calibrated RS; MATH500 shows the same qualitative behavior. The appendix also examines variation across prompts and target tilts, accuracy, and the resolution limits of the TV estimates.

Theoretical comparisons

  • Theory states that UR attains the best fixed-threshold RS guarantee in hindsight and has no greater TV error than budget-calibrated RS or SIR.The empirical envelope-RS baseline is a proxy for the best fixed-threshold comparison.Source: §I.3 · p. 42

Monte Carlo resolution

  • Once true TV error is sufficiently small, estimates approach the exact-sampler Monte Carlo scale, where differences cannot be reliably distinguished from estimation error.Appendix curves use 10^5 independent runs; Figure 1 uses 10^6.Source: §I.3 · p. 42

GSM8K: variation across prompts

  • Across displayed GSM8K prompts, approximation difficulty varies: some reach the Monte Carlo floor at small budgets, while others remain separated across the tested range.UR remains below or comparable to SIR and budget-calibrated RS up to Monte Carlo resolution.Source: §I.3 · p. 42

GSM8K: variation across β

  • Changing β changes target concentration and finite-budget difficulty, but UR remains competitive across the displayed GSM8K values without threshold information.Smaller β tilts the target more strongly toward high-reward responses; larger β makes it closer to the reference proposal.Source: §I.3 · p. 42

Empirical comparisons

  • Across displayed GSM8K prompts, UR’s estimated TV error is below or comparable to SIR and budget-calibrated RS; MATH500 shows the same qualitative behavior.UR remains competitive with envelope RS without threshold information.Source: §I.3 · pp. 42, 45, Figure 2 · p. 43, Figure 4 · p. 44

GSM8K: Ground-truth accuracy

  • As a sampler approaches the target distribution, its ground-truth accuracy approaches target accuracy, which may be higher or lower than reference-policy accuracy.Accuracy is therefore complementary; TV error is the primary metric for comparing the sampling procedures.Source: §I.3 · p. 45
Loading 2609.34639v1…