Metropolis-Hastings Dominates Importance Resampling for Policy Composition

M ETROPOLIS –H ASTINGS D OMINATES I MPORTANCE R ESAMPLING FOR P OLICY C OMPOSITION Alexey Kurennoy∗ Ramil Yarullin∗ Fergal Reid fin.ai {alexey.kurennoy,ramil.yarullin,fergal.reid}@fin.ai

arXiv:2610.03480v1 [cs.LG] 2 Oct 2026

A BSTRACT Post-training a large language model (LLM) often requires exploring tradeoffs between multiple rewards, but retraining for each trade-off is expensive. Decoding-time policy composition allows these trade-offs to be adjusted by combining reward-specific policies at inference time. This composition targets a weighted product of the policies’ probabilities over complete responses, but standard implementations combine their next-token probabilities, generally introducing sampling bias. We analyze a known iterative correction based on independence Metropolis–Hastings (MH). Our main result shows that, for every rollout budget, MH produces an output distribution at least as close to the target as sampling-importance-resampling (SIR) with the same budget, as measured by every convex f -divergence. We also derive a lower bound on MH’s improvement over the uncorrected decoder in a consensus objective measuring agreement with the supplied policies. We further characterize the correction’s sampling error in two asymptotic regimes: when the reward-specific policies approach agreement, and when fluctuations in the log ratio between target and uncorrected-decoder probabilities grow, as can happen for long responses. We complement our analysis with experiments in enumerable and LLM-scale settings.

1

I NTRODUCTION

Large language model (LLM) alignment involves balancing objectives such as helpfulness, safety, factual accuracy, and brevity (Bai et al., 2022; Dai et al., 2024; Wu et al., 2023; Wang et al., 2024). Doing so requires exploring different trade-offs, but retraining a policy for every trade-off is expensive. Decoding-time composition offers an alternative: it takes policies optimized individually for each objective and combines them at inference time (Shi et al., 2024; Shen et al., 2026). By varying the weights of the reward-specific policies in the composition, one can explore different trade-offs without retraining. The composition aims to sample from a weighted geometric average of complete-response probabilities: m Y X pbw (y | x) ∝ πi (y | x)wi , wi ≥ 0, wi = 1, (1) i:wi >0

i=1

where πi (y | x) is the probability that policy i assigns to response y given prompt x. However, sampling from the target (1) token by token generally requires summing over all possible continuations. A practical decoder instead multiplies the next-token probabilities and normalizes at each step. We call this process local product decoding. The two constructions generally differ because the policies can agree on next-token probabilities but disagree on later continuations (see Example 1). The sequence target accounts for the total product mass of these continuations, whereas the local rule ignores it. Consequently, even exact reward-specialized policies can produce a biased decoder for their combined objective. Let qw denote the local decoder and ρw the product of its stepwise normalization constants. Then pbw ∝ qw ρw . Each rollout therefore provides its importance weight: the target-to-proposal probability ratio, up to a response-independent constant. The independence Metropolis–Hastings (MH) ∗

Equal contribution.

1

Local bias from policy disagreement target pbw

z=1

j = 0: 3/8

Exact error versus budget 10−1

j = 1: 5/8

z=1

z = 3/5

ρ=1

ρ = 3/5

0.25

KL to target (nats)

local qw

0

(0, −1)

(1, −1)

(0, +1)

(1, +1)

pbw (y) ∝ qw (y) ρw (y)

10−4 10−7 MH ordinary SIR

10−10 1

3

5

7

9

Candidate budget M

Figure 1: Local bias and finite-budget correction in Example 1. Left: the two policies agree after j = 0 and disagree after j = 1. Reweighting the local law qw by the recorded normalizers ρw recovers the uniform target. Right: exact KL to the target for MH and ordinary SIR on the same four-response toy example. construction of Gareev et al. (2024) uses these weights to accept or reject independently generated responses. It requires additional rollouts, but no separate reward model or post-generation model evaluation to score a candidate. Proposals can be batched, with selection performed afterward. An alternative to MH is sampling-importance-resampling (SIR), which selects a candidate with probability proportional to its importance weight. Both MH and SIR use the same recorded information and the same budget of M rollouts, including initialization. In this paper, we present a new theoretical analysis of the MH correction. Our central result states that at every budget M , MH’s output distribution is at least as close to the sequence target as ordinary SIR’s under every convex f -divergence. In more detail, our contributions are as follows. 1. We prove that MH is no farther from the target than ordinary SIR at any budget. Moreover, for KL in both directions and total variation, MH is strictly closer for M ≥ 2 whenever the local decoder differs from the target (Theorem 1). 2. We derive a lower bound on MH’s improvement over the uncorrected decoder in a consensus objective measuring agreement with the supplied policies. The bound can be estimated directly from quantities recorded during generation, and we give conditions under which it extends to scalarized reward optimization (Proposition 1). 3. We characterize the behavior of the correction’s sampling error in two asymptotic regimes. The first regime concerns reward-specific policies approaching agreement. In this setting, MH’s sampling error decays at a higher asymptotic order than SIR’s (Theorem 2). The second regime captures limitations that can arise for long responses. In this regime, both MH and SIR attain the asymptotically minimal total variation error among methods selecting from independently generated rollouts at the same budget (Theorem 3). We complement the theory with experiments in enumerable and LLM-scale settings (Section 4).1

2

C ORRECTING LOCAL PRODUCT DECODING

Consider m autoregressive policies π1 , . . . , πm and weights wi ≥ 0 that sum to 1. The active policies, those with nonzero weights, are indexed by Iw = {i : wi > 0}. We assume that the policies share a tokenizer and a finite vocabulary V. For a prompt x, a response ends at the first end-of-sequence (EOS) token or at the length cap T . We write y = (y1 , . . . , yT ), padding shorter responses deterministically with EOS tokens. At prefix Q ht = (x, y<t ), policy i assigns next-token probability πi,t (v | ht ), so πi (y | x) = t πi,t (yt | ht ). 1 The associated code composition.git.

is

available

at

https://github.com/akurennoy/mh-policy-

2

We assume that all active policies share the same support tree: they assign positive probability to every allowed transition and probability 0 elsewhere. We denote the finite set of complete responses on this tree by Sx . Let pew (y | x) denote the unnormalized Q Pweighted geometric average of the policies, pew (y | x) = wi π (y | x) , and let Z (x) = ew (y | x) be its normalizer. With this notation, the i w i∈Iw y∈Sx p target policy (1) can be written as pbw = pew /Zw . Our goal is to sample from pbw without computing Zw , which sums over exponentially many responses. Local product decoding avoids this summation by normalizing at each token: X Y gw,t (v | ht ), qw,t = gw,t /zw,t . (2) gw,t (v | ht ) = πi,t (v | ht )wi , zw,t (ht ) = v∈V

i∈Iw

Repeating this rule gives the local product distribution, qw (y | x) = differs from pbw , as the following example illustrates.

t qw,t (yt | ht ). It generally

Q

Example 1. In Figure 1, we compose two policies with equal weights (w1 = w2 = 1/2). Both policies assign probability 3/8 to the first token j = 0 and 5/8 to j = 1. After j = 0, both are uniform over the second token s ∈ {−1, +1}. After j = 1, each assigns probability 0.9 to a different √ value of s. The continuation product mass is therefore 1 after j = 0 and 2 0.9 × 0.1 = 0.6 after j = 1. Since (3/8) × 1 = (5/8) × 0.6, the sequence target is uniform over the four responses. The local rule ignores these continuation masses when choosing the first token and therefore assigns too much probability, 5/8 instead of 1/2, to the right-hand (j = 1) branch. Lemma 1 (Local-normalizer identity). On the shared support Sx , qw and pbw are positive, with pbw (y | x) =

qw (y | x)ρw (y | x) , Zw (x)

ρw (y | x) =

T Y

zw,t (ht ),

Zw (x) = Eqw [ρw ].

(3)

t=1

Moreover, 0 < zw,t ≤ 1 for t = 1, . . . , T , 0 < ρw ≤ 1, and 0 < Zw ≤ 1. Proof. See Appendix A.1. The leftmost identity in (3) is the local-to-global importance correction used in sequential Monte Carlo (SMC), specialized to policy products (Lew et al., 2023; Chan et al., 2026). The normalizers zw,t measure how much the policies disagree at the next token (Heskes, 1997): X − log zw,t (h) = wi KL(qw,t (· | h) ∥ πi,t (· | h)) . i

Thus − log ρw accumulates disagreement along a response, and qw /b pw = Zw /ρw increases with that accumulated disagreement. Consequently, qw and pbw differ whenever ρw varies across responses, which is generally the case. We consider a correction to the local product distribution qw based on independence Metropolis– Hastings (MH) (Gareev et al., 2024). From the current response y, the algorithm proposes a fresh y ′ ∼ qw and accepts it with probability min{1, ρw (y ′ | x)/ρw (y | x)}. The unknown Zw cancels, so this decision rule uses only the recorded local normalizers. MH always accepts a rollout with a higher ρw , but it also accepts some rollouts with a lower ρw . In Example 1, MH always accepts a move from the disagreement branch to the agreement branch and accepts the reverse with probability 0.6, with the first update moving the disagreement branch’s mass from 5/8 to 17/32, closer P to the target’s 1/2. Algorithm 1 implements the correction in log space using ℓρ,w = log ρw = t log zw,t . The correction evaluates every active policy at each token of M responses, then selects one in O(M ) scalar operations. Optimization interpretation. For a response distribution µ on Sx , the consensus objective measures agreement through the negative weighted sum of KL divergences to the policies: X Jex (µ) := − wi KL(µ∥πi ) = Eµ [log pew − log µ] = log Zw − KL(µ∥b pw ). (4) i∈Iw

3

Algorithm 1 Independence-MH correction of local product decoding Require: Prompt x, weights w, total rollout budget M ≥ 1 1: Generate M independent rollouts yb1 , . . . , ybM ∼ qw (· | x), recording ℓρ,w for each 2: y ← yb1 3: for j = 2, . . . , M do 4: Draw U ∼ Uniform(0, 1) independently 5: if log U ≤ min{0, ℓρ,w (b yj | x) − ℓρ,w (y | x)} then 6: y ← ybj 7: end if 8: end for 9: return y The product pbw , also known as the logarithmic opinion pool (Heskes, 1997), uniquely maximizes this objective, regardless of how the policies were trained. For external rewards Ri (x, y) ∈ R and a positive reference policy πref on Sx , consider the KL-regularized objectives ext Ji,x (µ) = Eµ [Ri ] − βKL(µ∥πref ),

β > 0.

(5)

ext ∗ maximize the corresponding weighted Let πi∗ maximize Ji,x over response distributions, and let πw P P ext ext objective Jw,x = i wi Ji,x , which is (5) with reward Rw = i wi Ri . The individual optima have the form πi∗ ∝ πref exp(Ri /β) (Ziegler et al., 2019; Rafailov et al., 2023). If the supplied policies satisfy πi = πi∗ for this common reference and β, then Y
w i ∗ pbw = πw ∝ πref eRi /β = πref eRw /β . (6) i

Sampling from the product thus recovers the scalarized optimum without retraining. For approxi∗ (Appendix B.7). mately optimal specialists, the product can differ from πw In either setting, the gap to the optimal objective is J(p) − J(µ) = λKL(µ∥p),

p = pbw ,

(7)

ext and λ = β for multi-reward with J = Jex and λ = 1 for the consensus objective, and with J = Jw,x alignment. In both cases, reducing KL to the product improves the objective.

3

T HEORETICAL ANALYSIS OF THE MH CORRECTION

We fix the prompt and weights and abbreviate the target, proposal, and recorded weight as p = pbw , q = qw , and ρ = ρw , so p = qρ/Z with Z = Eq ρ. More generally, an instance (q, ρ) consists of a finite response space, a strictly positive proposal law q on that space, and a strictly positive weight function ρ; these determine Z = Eq ρ and the target p = qρ/Z. Recall that, given M iid candidates Y1 , . . . , YM from q, MH starts at the first and processes the remaining M − 1 according to Algorithm 1. We denote its output distribution by HM . Ordinary P SIR uses the same pool of M rollouts but instead selects candidate j with probability ρ(Yj )/ k ρ(Yk ). We denote SIR’s output distribution by SM . 3.1

D OMINANCE OF MH OVER SIR AT EVERY CANDIDATE BUDGET

We consider the f -divergences Df (µ∥p) =

X

p(y)f (µ(y)/p(y)),

(8)

y

where f : (0, ∞) → R is finite and convex, with f (1) = 0. These include KL in both directions, total variation, and the chi-square divergence. Theorem 1 (Finite-budget dominance over ordinary SIR). For every integer M ≥ 1 and every f -divergence Df of the form (8), Df (HM ∥p) ≤ Df (SM ∥p). The inequality (9) is strict for M ≥ 2 and p ̸= q if Df is total variation or if f is strictly convex. 4

(9)

Proof idea. A priority-sampling representation of MH lets us couple the MH and SIR outputs so that the importance weight selected by MH is almost surely at least as large as that selected by SIR. Relative to the target, MH’s probability ratio is nonincreasing in the weight. Convexity then converts these two orderings into the f -divergence comparison. The full proof is in Appendix A.2. Because Theorem 1 covers KL(·∥p), the objective-gap identity (7) also gives J(HM ) ≥ J(SM ) for either objective under its stated assumptions. Since the proof does not rely on autoregressive structure, Theorem 1 extends directly to reward-tilted targets, where SIR corresponds to soft best-of-M (Verdun et al., 2025). 3.2

O BJECTIVE GAIN GUARANTEE

We now derive a lower bound on MH’s improvement over the local decoder q. For iid Y1 , . . . , YM ∼ q, define the recorded-weight gap   M M X 1 1 X GM = log ρ(Yj ) − log ρ(Yj ), (10) M j=1 M j=1 the log ratio of the arithmetic and geometric means of the pool’s weights, so that GM ≥ 0 and G1 = 0. Note that this bound can be estimated from recorded rollout weights, without evaluating Z or the sampler’s output distribution. Proposition 1 (Objective improvement and diminishing returns). In the setting of Theorem 1, take ext , β) if every active policy exactly optimizes (5) with a common (J, λ) = (Jex , 1), or (J, λ) = (Jw,x positive reference and coefficient β > 0. Then the gains J(HM +1 ) − J(HM ) are nonnegative and nonincreasing for M ≥ 1, and J(HM ) − J(q) ≥ λEqM [GM ] ≥ 0 for all M ≥ 1. (11) Proof. See Appendix A.4. We refer to λEqM [GM ] as a certificate of improvement over q. The same lower bound holds for SIR, so it does not measure the difference between MH and SIR. The certificate bounds improvement, not the remaining divergence (Appendix B.5). 3.3

N EARBY COMPONENT POLICIES

The near-agreement regime describes the composition of specialists that remain close to a common policy, as may occur under regularized post-training. Since local decoding is exact when the policies coincide, this regime isolates how effectively additional rollouts correct the bias introduced by their disagreement. It reveals a qualitative distinction between MH and SIR: additional MH rollouts improve the error order, whereas SIR generally improves only the leading coefficient. Specifically, fix a common positive policy π0 (· | h) on a fixed support tree and bounded functions ai (v, h), and consider the perturbed policies πi,δ (v | h) =

π0 (v | h)eδai (v,h) . EV ∼π0 (·|h) eδai (V,h)

(12)

The parameter δ controls the separation of the policies πi,δ , and δ = 0 corresponds to identical policies. We denote the resulting local proposal and product target by qδ and pδ , respectively, and the corresponding MH and SIR output laws by HM,δ and SM,δ . Theorem 2 (Exact nearby-policy error). For the family of policies (12), there exist constants CM ≥ 0 such that, for every M ≥ 1, as δ → 0, KL(qδ ∥pδ ) = C1 δ 4 + O(|δ|5 ), KL(HM,δ ∥pδ ) = CM δ 4M + O(|δ|4M +1 ), C1 KL(SM,δ ∥pδ ) = 2 δ 4 + O(|δ|5 ). M Moreover, the constants CM are either all positive or all 0. 5

(13)

Proof. See Appendix A.5. The exponent 4M cannot be improved uniformly over nearby-policy families by selectors using only q and M sampled candidates with their recorded weights, without access to Z or unobserved weights (Appendix B.3). 3.4

C ANDIDATE BUDGET AND RESPONSE LENGTH

As responses become longer, small differences between the target and proposal can accumulate across tokens. Consequently, the ratio of their probabilities can vary greatly from one response to another. Responses with a large target-to-proposal ratio are underrepresented among the generated candidates. This poses a challenge for selection rules such as MH and SIR, because neither can return a response that was never proposed. To study this limitation, we consider a sequence of problems in which fluctuations in the log targetto-proposal ratio grow along with the rollout budget. The following theorem describes the balance between these two effects. At the specified budget scaling, some target mass remains inaccessible often enough that even the best selection rule has a positive limiting error. Theorem 3 (Critical candidate budget). For each integer N ≥ 1, let pN , qN be positive probability laws on the same finite set XN . Suppose that there exist dN ∈ R and sN > 0 with sN → ∞ such that, for YN ∼ pN , log[pN (YN )/qN (YN )] − dN ⇒W sN in distribution as N → ∞, where W has distribution function Ψ. Consider integer rollout budgets MN → ∞ such that log MN − dN =b lim N →∞ sN for some b ∈ R. If Ψ is continuous at b and 0 < Ψ(b) < 1, then inf ν∈SMN (qN )

∥ν − pN ∥TV −→ 1 − Ψ(b)

as N → ∞,

(14)

where SM (qN ) is the set of output laws of all rules that return one of M iid candidates from qN , including rules with full knowledge of pN and qN . Both MH, initialized from qN , and ordinary SIR attain this limit. Proof. See Appendix A.6. As an example, consider a response consisting of N independent repetitions of Example 1. In this family, dN = KL(pN ∥qN ) grows linearly with response length and sN grows as its square root (Appendix A.6). For any fixed b ∈ R, the scaling log MN = dN + bsN + o(sN ) yields a limiting √TV error strictly between zero and one. Thus these budgets satisfy log MN = KL(pN ∥qN ) + O( N ) and grow exponentially with response length.

4

E MPIRICAL STUDY

We measure MH and SIR sampling errors directly on enumerable problems and restricted continuation trees of trained LLM specialists. For full responses, the samplers’ marginal output probabilities are difficult to evaluate. We instead use the shared certificate to bound improvement over local decoding and separately assess task-level effects and serving costs on GSM8K and HH-RLHF. Both experiments compose DPO-specialized adapters of Gemma-4-E2B-it (Gemma Team, 2026). 4.1

S AMPLING ERROR IN AN ENUMERABLE SETTING

We compose 3 autoregressive policies over a 4-token vocabulary, drawing conditional distributions from a symmetric Dirichlet law and weights uniformly from the simplex. Five settings vary policy concentration (base, peaky, and flat) and response length (short and long), with horizons from 3 to 10 6

10 −2

KL to target (nats)

KL to target (nats)

10 0 10 −3 10 −6 10 −9 10

−12

0

MH ordinary SIR 1 2 3

5

8

20

50

10 −8 ±4 10

−14

10

−26

10

−32

MH updates n (M = n + 1) base (® = 0:5)

peaky (® = 0:2)

±8

10 −20

flat (® = 1)

± 10 −2

q± (M = 1) SIR, M = 2; 3 MH, M = 2 MH, M = 3

12

10 −1 Perturbation size ±

short (T = 3)

10 0

long (T = 10)

Figure 2: Exact sampling error on enumerable problems. Left: mean KL in five enumerable settings (values ≤ 10−12 omitted). Right: the nearby-policy rates of Theorem 2. As δ → 0, the KL of MH decays as δ 4M , whereas ordinary SIR keeps the δ 4 order of qδ (dotted reference slopes). Solid lines with filled markers show MH, and dashed lines with open markers show ordinary SIR. tokens. Enumeration lets us propagate MH exactly and evaluate SIR’s marginal law by deterministic quadrature. Appendix C gives configurations and replication counts. The first MH update gives the largest gain in every setting, removing approximately 70–95% of the mean initial KL (Figure 2, left), consistent with Proposition 1. Convergence is slowest in the peaky setting. At M = 9, MH has lower mean KL than ordinary SIR in all five settings. In the base, flat, and short settings, MH with 9 candidates also has lower mean KL than SIR with 51. At a budget of 9 full-sequence equivalents of conditional policy evaluations, MH has lower estimated binned TV than SIR on all 23 tested instances and the lowest point estimate among MH, SMC, and replica-exchange methods on 17. Adaptive SMC outperforms MH on one peaky instance. Maximum-weight selection can be farther from the target than local decoding (Appendix C.4). Finally, the right panel of Figure 2 tests the nearby-policy prediction on a fixed 27-response problem with 2 equally weighted policies. As δ decreases, MH at M = 2 and M = 3 approaches eighthand twelfth-order error, while ordinary SIR retains fourth-order error with a smaller coefficient. 4.2

D IRECT COMPARISONS ON TRAINED - POLICY CONTINUATION TREES

We compare MH and SIR using the trained accuracy- and brevity-specialized policies on 50 GSM8K test questions (Cobbe et al., 2021), at the original prompts and halfway through greedy referencemodel responses. We enumerate continuations of up to 4 tokens, restricting both specialists to the reference model’s top 8 tokens at each prefix and renormalizing each separately. The target is the sequence product of these restricted policies. At accuracy weights w1 ∈ {0.25, 0.5, 0.75}, deterministic MH propagation and SIR quadrature give the full output laws and hence their consensus gains through (4). At midpoint contexts with equal weights, the local decoder’s mean KL is 1.31 × 10−3 nats. With 2 candidates, MH removes 96.8% of this mean divergence, compared with 76.0% for SIR. With 3 candidates, MH has lower mean KL than SIR with 9 candidates. Across the six context–weight settings, MH’s mean KL advantage over SIR at M = 9 ranges from 4.60 × 10−6 to 1.66 × 10−4 nats. All six paired, pointwise 95% bootstrap intervals exclude 0, although the gaps are small and vary substantially across questions. At this budget, the estimated mean certificate is 75–90% of MH’s mean gain over local decoding. Full curves and sensitivity checks are in Appendix F.

7

4.3

C ONSENSUS GAINS AND TASK - LEVEL EFFECTS ON GSM8K

In both GSM8K and HH-RLHF experiments we train two specialist policies and then compose them with weights (w1 , 1 − w1 ), w1 ∈ {0.25, 0.5, 0.75}, on 1,319 test prompts. We generate 8 independent groups (replications) of 17 rollouts per test prompt, sampling from the full vocabulary at temperature 1. At budget M , both methods use the first M responses from the same pool. The checkpoints were fixed before the evaluation, and test examples were excluded from specialist training. For GSM8K, we compose the accuracy- and brevity-specialized policies on the full official test set, with weight w1 on accuracy. At M = 17, the simultaneous 95% lower bounds on average consensus improvement for both MH and SIR are 0.742, 1.644, and 1.330 nats, in increasing order of w1 (Figure 3, top-left). These also lower-bound the local decoder’s mean divergence from the product target (Appendix D.1). At every weighting, both corrections produce shorter and more accurate responses than the local decoder with the same weights (top-middle panel). With M = 3, MH raises accuracy by 0.8–1.2 percentage points and reduces mean returned length by 11–26 tokens. At M = 17, these changes are 1.1–1.3 points and 16–42 tokens (top-right panel). For both MH and SIR, the paired 95% intervals for accuracy improvement over q exclude zero at every tested weight and budget M ≥ 2. MH and SIR differ by at most 0.14 percentage points in accuracy, with intervals that include 0, and MH responses are shorter by at most 1.3 tokens. Majority voting on the same pools is 1.2–1.6 percentage points more accurate than MH at M = 17, but returns responses 12–36 tokens longer (Table 4). These task-level comparisons do not measure fidelity to the product target. In a separate serving profile of 16 prompts on one H200, batching 3 candidates per prompt increases mean latency by 16–20% over local decoding across the three weightings. Despite shorter returned responses, total generated tokens grow approximately in proportion to M . This profile does not measure serving throughput. Appendix D.2 gives the full results and serving protocol.

4.4

C ONSENSUS GAINS ON HH-RLHF

We compose helpfulness- and harmlessness-specialized adapters on held-out HH-RLHF conversations (Bai et al., 2022), with weight w1 on helpfulness. Both adapters train on a shared conversation pool using preferences from separate GPT-2-large reward models (Yang et al., 2024). These models also evaluate the outputs, so their scores are proxies for quality and safety, not human judgments. At M = 17, the simultaneous 95% lower bounds on average consensus improvement are 0.063, 0.280, and 0.158 nats, in increasing order of w1 (Figure 3, bottom-left). Increasing w1 raises helpfulness and lowers harmlessness under both corrections (bottom-middle panel and Table 8). At fixed weights, MH with M = 17 lowers helpfulness by 0.077–0.114 logits and raises harmlessness by 0.042–0.090 logits relative to local decoding. All six paired, pointwise 95% intervals exclude 0 (bottom-right panel). The weighted-score change is negative at w1 = 0.5 and 0.75 and statistically unresolved at w1 = 0.25. MH and SIR have similar weighted scores, and all three paired intervals for their differences include 0. MH favors responses with less accumulated policy disagreement, measured by − log ρw . Even with exact specialists, the guarantee concerns a KL-regularized objective, not the raw weighted score. Appendix E.1 gives the protocol, paired comparisons, and serving costs.

4.5

S COPE AND PRACTICAL IMPLICATIONS

The full-response experiments cover one model family and two tasks. Their certificates bound improvement over local decoding, not the MH–SIR gap, which we measure directly only on restricted continuation trees. At the same candidate budget and model-evaluation cost, Theorem 1 guarantees that MH’s output distribution is no farther from the product target than ordinary SIR’s. 8

mean GM

GSM8K

0.75

1.0

0.25

0.5

Accuracy (%)

1.5

90.5

M = 17

90.0 89.5 89.0 0.5

88.5

w1 = 0:25

0.0 9

13

17

240

Budget M

280

300

320

0.4

0.75

0.3

0.25

0.2 0.1

Helpfulness score

0.5

1.5 1.0 0.5 0.0

340

2.0

w1 = 0:75

1.9 1.8

0.5

M = 17

1.7

0.25

1.6 1.5

0.0 5

M = 17

0.25

0.5 0.75 Weight w1

w1

0.5

1

ordinary SIR

2.0

Mean response length (tokens)

HH-RLHF Certificate (nats)

260

9

13

17

Budget M

−1.2

−1.0

Harmlessness score

−0.8

Score change (logits)

5

0.75

Accuracy change (pp)

0.5

1

MH

w1

2.0

Certificate (nats)

local decoder (M = 1)

95% lower bound

Harmlessness 0.1 0.0 −0.1 Helpfulness 0.25

0.5 0.75 Weight w1

Figure 3: Certified consensus gains and task-level effects on GSM8K (top) and HH-RLHF (bottom). Left: mean GM and simultaneous 95% lower bounds within each study, conditional on the prompts and checkpoints; GM depends only on the candidate pool, so it certifies both MH and ordinary SIR. Middle: MH trade-offs at M ∈ {2, 3, 5, 9, 17}; crosses mark local decoding (M = 1). Ordinary SIR nearly coincides with MH (Tables 4 and 8). Right: changes from the local decoder at the same weights for M = 17, with paired, pointwise 95% bootstrap intervals. HH-RLHF shows both helpfulness and harmlessness changes in reward-model logits; pp denotes percentage points.

5

R ELATED WORK

Decoding-time policy composition. MOD derives the weighted sequence product for KLregularized multi-objective alignment and implements greedy or beam decoding (Shi et al., 2024). MAHALO combines objective-specific heads through weighted logits (Shen et al., 2026). Its untruncated softmax follows our local product law, although process-reward selection and truncation change the output distribution. We study sampling at fixed weights, whereas COLLAB selects policies by utility (Chakraborty et al., 2025) and RMOD optimizes against adversarial reward weights (Son et al., 2026). Sampling globally normalized text distributions. SMC uses local-normalizer corrections for policy products (Lew et al., 2023), including across tokenizers (Chan et al., 2026). Gareev et al. (2024) and Tan et al. (2024) use local proposals in independence MH for globally normalized text. Twisted SMC learns continuation information (Zhao et al., 2024), QUEST resamples suffixes (Faria et al., 2024), and He et al. (2026) study SMC and replica exchange for sequence products and tilts. We analyze independent complete-response proposals. Finite-budget selection guarantees. Deligiannidis et al. (2024) compare MH and SIR bias rates, while Yang & Liu (2023) study worst-start TV rates for multiple-try and ordinary independence MH at matched cost. Our comparison instead orders the marginal output distributions under every convex f -divergence at each budget and extends to fixed schedules of their multiple-try sampler (Appendix B.1). The coverage analysis connects this comparison to the candidate-budget thresholds studied in importance sampling and finite-pool selection (Chatterjee & Diaconis, 2018; Block & Polyanskiy, 2023; Flamich & Wells, 2024). 9

6

C ONCLUSION

We show that the independence-MH correction brings local product decoding at least as close to the sequence target as ordinary SIR under every convex f -divergence, at every candidate budget. Its consensus improvement can be certified from recorded rollout weights without estimating the sampler’s output distribution. The GSM8K and HH-RLHF experiments show the magnitude of the positive consensus gains in practical settings. However, comparing correction methods empirically at LLM scale remains difficult: their marginal output probabilities are not readily evaluable, preventing reliable direct estimation of consensus differences, while task rewards alone do not capture the consensus objective. Theoretical comparison results such as given by Theorem 1 are therefore particularly important. Our coverage analysis also shows why improvement need not imply closeness to the target: neither method can return responses from regions absent from its candidate pool.

10

AI USE STATEMENT The authors formulated the research questions, derived core theoretical results, and wrote the initial manuscript. Generative AI tools assisted with readability, literature searches, figures, LaTeX preparation, and the development, extension, and checking of selected theoretical arguments and proofs. The authors take responsibility for the scientific content and reported results. E THICS STATEMENT The method composes existing policies and inherits limitations of their training data and reward signals. More accurate sampling from their product does not by itself establish safety or improved external performance. The HH-RLHF dataset contains potentially harmful content. We report methodology and aggregate statistics without prompt or response examples. R EPRODUCIBILITY STATEMENT Appendix C gives the enumerable configurations, deterministic calculations, matched-budget sampler schedules, and reference controls. Appendices D.1 and E.1 document the GSM8K and HHRLHF evaluations and their uncertainty calculations. Appendix F gives the restricted continuationtree protocol and direct objective comparisons. The associated code is available in the repository at https://github.com/akurennoy/mh-policy-composition.git.

R EFERENCES Gholamali Aminian, Amir R. Asadi, Idan Shenfeld, and Youssef Mroueh. KL-regularized RLHF with multiple reference models: Exact solutions and sample complexity. In Advances in Neural Information Processing Systems, volume 38, 2025. URL https://arxiv.org/abs/2502. 01203. Christophe Andrieu, Anthony Lee, and Matti Vihola. Uniform ergodicity of the iterated conditional SMC and geometric ergodicity of particle Gibbs samplers. Bernoulli, 24(2):842–872, 2018. doi: 10.3150/15-BEJ785. URL https://arxiv.org/abs/1312.6432. Yuntao Bai, Andy Jones, Kamal Ndousse, Amanda Askell, Anna Chen, Nova DasSarma, Dawn Drain, Stanislav Fort, Deep Ganguli, Tom Henighan, et al. Training a helpful and harmless assistant with reinforcement learning from human feedback. arXiv preprint arXiv:2204.05862, 2022. Adam Block and Yury Polyanskiy. The sample complexity of approximate rejection sampling with applications to smoothed online learning. In Proceedings of Thirty Sixth Conference on Learning Theory, volume 195 of Proceedings of Machine Learning Research, pp. 228–273, 2023. URL https://proceedings.mlr.press/v195/block23a.html. Yuri Burda, Roger Grosse, and Ruslan Salakhutdinov. Importance weighted autoencoders. In International Conference on Learning Representations, 2016. Souradip Chakraborty, Sujay Bhatt, Udari Sehwag, Soumya Suvra Ghosal, Jiahao Qiu, Mengdi Wang, Dinesh Manocha, Furong Huang, Alec Koppel, and Sumitra Ganesh. Collab: Controlled decoding using mixture of agents for LLM alignment. In International Conference on Learning Representations, 2025. URL https://openreview.net/pdf?id=7ohlQUbTpp. Robin Shing Moon Chan, Tianyu Liu, Samuel Kiegeland, Clemente Pasti, Jacob Hoover Vigly, Timothy J. O’Donnell, Ryan Cotterell, and Tim Vieira. Ensembling language models with sequential monte carlo. arXiv preprint arXiv:2603.05432, 2026. URL https://arxiv.org/abs/ 2603.05432. Sourav Chatterjee and Persi Diaconis. The sample size required in importance sampling. The Annals of Applied Probability, 28(2):1099–1135, 2018. doi: 10.1214/17-AAP1326. 11

Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, Christopher Hesse, and John Schulman. Training verifiers to solve math word problems. arXiv preprint arXiv:2110.14168, 2021. Chris Cremer, Quaid Morris, and David Duvenaud. Reinterpreting importance-weighted autoencoders. In ICLR Workshop, 2017. arXiv:1704.02916. Josef Dai, Xuehai Pan, Ruiyang Sun, Jiaming Ji, Xinbo Xu, Mickel Liu, Yizhou Wang, and Yaodong Yang. Safe RLHF: Safe reinforcement learning from human feedback. In International Conference on Learning Representations, 2024. George Deligiannidis, Pierre E. Jacob, El Mahdi Khribch, and Guanyang Wang. On importance sampling and independent Metropolis–Hastings with an unbounded weight function. arXiv preprint arXiv:2411.09514, 2024. URL https://arxiv.org/abs/2411.09514v3. Version 3, revised July 2026. Justin Domke and Daniel R. Sheldon. Importance weighting and variational inference. In Advances in Neural Information Processing Systems, volume 31, 2018. URL https://papers.nips. cc/paper/7699-importance-weighting-and-variational-inference. Nick Duffield, Carsten Lund, and Mikkel Thorup. Priority sampling for estimation of arbitrary subset sums. Journal of the ACM, 54(6):32, 2007. doi: 10.1145/1314690.1314696. Gonçalo R. A. Faria, Sweta Agrawal, António Farinhas, Ricardo Rei, José G. C. de Souza, and André F. T. Martins. QUEST: Quality-aware metropolis–hastings sampling for machine translation. In Advances in Neural Information Processing Systems, volume 37, 2024. Gergely Flamich and Lennie Wells. Some notes on the sample complexity of approximate channel simulation, 2024. URL https://arxiv.org/abs/2405.04363. Daniel Gareev, Thomas Hofmann, Ezhilmathi Krishnasamy, and Tiago Pimentel. Local and global decoding in text generation. In Findings of the Association for Computational Linguistics: EMNLP 2024, pp. 14577–14597, 2024. doi: 10.18653/v1/2024.findings-emnlp.854. Gemma Team. Gemma 4 technical report, 2026. URL https://arxiv.org/abs/2607. 02770. Pieralberto Guarniero, Adam M. Johansen, and Anthony Lee. The iterated auxiliary particle filter. Journal of the American Statistical Association, 112(520):1636–1647, 2017. doi: 10.1080/01621459.2016.1222291. Jiajun He, Zongyu Guo, José Miguel Hernández-Lobato, and Yuanqi Du. Recipes for steering and scaling LLMs via sampling. arXiv preprint arXiv:2608.26120, 2026. Tom Heskes. Selecting weighting factors in logarithmic opinion pools. In Advances in Neural Information Processing Systems, volume 10, pp. 266–272, 1997. Jonathan J. Hunt, André Barreto, Timothy P. Lillicrap, and Nicolas Heess. Composing entropic policies using divergence correction. In Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 2911–2920, 2019. URL https://proceedings.mlr.press/v97/hunt19a.html. Alexander K. Lew, Tan Zhi-Xuan, Gabriel Grand, and Vikash K. Mansinghka. Sequential monte carlo steering of large language models using probabilistic programs. arXiv preprint arXiv:2306.03081, 2023. Jun S. Liu. Metropolized independent sampling with comparisons to rejection sampling and importance sampling. Statistics and Computing, 6(2):113–119, 1996. doi: 10.1007/BF00162521. Jun S. Liu, Faming Liang, and Wing Hung Wong. The multiple-try method and local optimization in metropolis sampling. Journal of the American Statistical Association, 95(449):121–134, 2000. 12

Kerrie L. Mengersen and Richard L. Tweedie. Rates of convergence of the Hastings and Metropolis algorithms. The Annals of Statistics, 24(1):101–121, 1996. Art B. Owen. Monte Carlo Theory, Methods and Examples. domains/mc/, 2013.

https://artowen.su.

Rafael Rafailov, Archit Sharma, Eric Mitchell, Christopher D. Manning, Stefano Ermon, and Chelsea Finn. Direct preference optimization: Your language model is secretly a reward model. In Advances in Neural Information Processing Systems, volume 36, 2023. Yiran Shen, Yu Xia, Jonathan D. Chang, and Prithviraj Ammanabrolu. Simultaneous multi-objective alignment across verifiable and non-verifiable rewards. In International Conference on Machine Learning, 2026. URL https://arxiv.org/abs/2510.01167. Ruizhe Shi, Yifang Chen, Yushi Hu, Alisa Liu, Hannaneh Hajishirzi, Noah A. Smith, and Simon S. Du. Decoding-time language model alignment with multiple objectives. In Advances in Neural Information Processing Systems, volume 37, 2024. Øivind Skare, Erik Bølviken, and Lars Holden. Improved sampling-importance resampling and reduced bias importance sampling. Scandinavian Journal of Statistics, 30(4):719–737, 2003. doi: 10.1111/1467-9469.00360. Richard L. Smith and Luke Tierney. Exact transition probabilities for the independence Metropolis sampler. Technical report, 1996. Seongho Son, William Bankes, Sangwoong Yoon, Shyam Sundhar Ramesh, Xiaohang Tang, and Ilija Bogunovic. Robust multi-objective controlled decoding of large language models. In International Conference on Learning Representations, 2026. URL https://arxiv.org/abs/ 2503.08796. Naaman Tan, Josef Valvoda, Tianyu Liu, Anej Svete, Yanxia Qin, Min-Yen Kan, and Ryan Cotterell. A probability–quality trade-off in aligned language models and its relation to sampling adaptors. In Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, pp. 14805–14829, 2024. doi: 10.18653/v1/2024.emnlp-main.822. URL https://aclanthology.org/2024.emnlp-main.822/. Luke Tierney. Markov chains for exploring posterior distributions. The Annals of Statistics, 22(4): 1701–1728, 1994. Claudio Mayrink Verdun, Alex Oesterling, Himabindu Lakkaraju, and Flavio P. Calmon. Soft best-of-n sampling for model alignment. In 2025 IEEE International Symposium on Information Theory (ISIT), pp. 1–6, 2025. doi: 10.1109/ISIT63088.2025.11195541. URL https: //arxiv.org/abs/2505.03156v1. Extended version: arXiv:2505.03156v1. Guanyang Wang. Exact convergence analysis of the independent Metropolis–Hastings algorithms. Bernoulli, 28(3), 2022. doi: 10.3150/21-BEJ1409. URL https://arxiv.org/abs/2008. 02455. Haoxiang Wang, Wei Xiong, Tengyang Xie, Han Zhao, and Tong Zhang. Interpretable preferences via multi-objective reward modeling and mixture-of-experts. In Findings of the Association for Computational Linguistics: EMNLP 2024, 2024. Zeqiu Wu, Yushi Hu, Weijia Shi, Nouha Dziri, Alane Suhr, Prithviraj Ammanabrolu, Noah A. Smith, Mari Ostendorf, and Hannaneh Hajishirzi. Fine-grained human feedback gives better rewards for language model training. In Advances in Neural Information Processing Systems, volume 36, 2023. Rui Yang, Xiaoman Pan, Feng Luo, Shuang Qiu, Han Zhong, Dong Yu, and Jianshu Chen. Rewardsin-context: Multi-objective alignment of foundation models with dynamic preference adjustment. In International Conference on Machine Learning, 2024. Xiaodong Yang and Jun S. Liu. Convergence rate of multiple-try Metropolis independent sampler. Statistics and Computing, 33(4):79, 2023. doi: 10.1007/s11222-023-10241-3. 13

Stephen Zhao, Rob Brekelmans, Alireza Makhzani, and Roger Grosse. Probabilistic inference in language models via twisted sequential monte carlo. In International Conference on Machine Learning, 2024. Daniel M. Ziegler, Nisan Stiennon, Jeffrey Wu, Tom B. Brown, Alec Radford, Dario Amodei, Paul Christiano, and Geoffrey Irving. Fine-tuning language models from human preferences. arXiv preprint arXiv:1909.08593, 2019.

14

A

P ROOFS OF THE MAIN RESULTS

This appendix proves the results stated in the main text, in the order in which they appear. We first establish how local normalizers provide exact correction weights and then use the priority representation to compare MH with ordinary SIR. The subsequent proofs establish the objective guarantees of Proposition 1, the nearby-policy rates of Theorem 2, and the critical-budget limit of Theorem 3. Unless stated otherwise, we fix the prompt and weights and take all sums over the common finite response support. We write p = pbw for the target, q = qw for the local decoder, and ρ = ρw for the recorded weight, so p = qρ/Z. Let K = Kp,q denote the independence-MH transition kernel, M −1 whose transition probabilities are determined by the proposal q and target p. Write HM = qKp,q for the law of the MH correction that uses M candidates (one for initialization and n = M − 1 for the updates). P We write Eµ f = For KL divergence, we use KL(µ∥ν) = y µ(y)f (y) for expectation. P µ(y) log[µ(y)/ν(y)], with terms with µ(y) = 0 set to 0 and the divergence set to +∞ y if µ(y) > 0 = ν(y) for some y. For positive laws, the convex divergence is Df (µ∥p) = P p(y)f (µ(y)/p(y)). The MH, SIR, and target laws in Theorem 1 are all positive, so both KL y 2 directions fall within this definition. Choosing f (u) = (u − 1) gives χ2 (µ∥p). A.1

L OCAL NORMALIZERS AND THE SEQUENCE - LEVEL TARGET

Proof of Lemma 1. Fix x, w. On the common support tree, every allowed transition has positive probability under every active policy. Thus gw,t is positive on allowed transitions and 0 elsewhere. Each reachable prefix has an allowed continuation, so zw,t > 0 and the local decoder assigns positive probability to every response in Sx . The generalized Hölder inequality gives !wi XY Y X wi zw,t (h) = πi,t (v | h) ≤ πi,t (v | h) = 1. v

i∈Iw

i∈Iw

v

This includes the single-active-policy case, where equality holds. Consequently 0 < ρw ≤ 1. Multiplying the local probabilities along a supported response gives QT Q πi,t (yt | ht )wi w qw (y | x) = t=1 Qi∈I T t=1 zw,t (ht ) Q wi π pew (y | x) i (y | x) = . = i∈Iw ρw (y | x) ρw (y | x) Summing qw ρw = pew over Sx yields Zw = Eqw ρw . Since qw is a probability law on this support and 0 < ρw ≤ 1, we obtain 0 < Zw ≤ 1. Dividing qw ρw = pew by Zw proves (3) and positivity of pbw . If a response ends before the cap, every policy emits EOS deterministically at each padded transition. Thus zw,t (ht ) = 1, and gw,t (v | ht ) = qw,t (v | ht ) is 1 for v = EOS and 0 otherwise. Padding therefore changes neither the response probability nor its recorded weight. The target’s next-token conditional. For an allowed token v at prefix ht , factor each policy into its prefix, current-token, and suffix probabilities. The prefix factors cancel when normalizing over v, leaving pbw,t (v | ht ) ∝ gw,t (v | ht )Fw,t (ht , v), XY (15) Fw,t (ht , v) = πi (y>t | ht , v)wi . y>t i∈Iw

Here πi (y>t | ht , v) is the suffix probability, and the sum runs over supported suffixes. At t = T the suffix is empty, so Fw,t = 1. Earlier in the response, this continuation mass generally varies across tokens. The local rule omits Fw,t , which explains why its next-token probabilities can differ from the target’s. For two exact specialists, −β log Fw,t (ht , v) is the finite-horizon counterpart of the divergence correction of Hunt et al. (2019, Theorem 3.2), with the shared reference absorbed into each reward. 15

Computing local normalizers from logits. Let bi (v, h) be the component P logits after the temperature and mask transformations that define πi , and write LSEv b(v) = log v eb(v) . On allowed tokens, the normalized log probabilities are bi (v, h) − LSEv bi (v, h). Substituting into (2) gives ! X X log zw (h) = LSEv wi bi (v, h) − wi LSEv bi (v, h). (16) i∈Iw

i∈Iw

Adding any prefix-dependent constant to a component’s logits leaves both its policy and this expression unchanged. The subtraction of component log normalizers is essential: softmax of the combined logits samples the correct qw , but the normalizer of those logits alone is not zw . Generation and weight calculation must use the same temperatures, masks, EOS rules, and length caps. Temperature and masking enter the target through the resulting normalized component policies. For example, a token can be forbidden by masking it in every active component and renormalizing each component before computing zw . The correction then targets the product of these masked policies, which generally differs from the original sequence target conditioned on avoiding that token. Applying top-k or nucleus truncation only to the combined proposal generally removes target support and invalidates the original correction. Subtracting a common constant from all candidate log weights leaves MH, SIR, and GM unchanged and can improve numerical stability. Clipping those weights or normalizing them by response length generally changes the target. Clipping GM for the certificate instead leaves the sampler unchanged. A.2

P RIORITY REPRESENTATION AND PROOF OF T HEOREM 1

The following lemma represents the output of the MH correction on iid candidates using the classical one-item priority-sampling rule (Duffield et al., 2007). Lemma 2 (Priority representation). Let Y1 , . . . , YM be iid candidates from q, and let U1 , . . . , UM be iid uniform on (0, 1), independent of the candidates. Then the maximum of ρ(Yj )/Uj over 1 ≤ j ≤ M is almost surely attained at a unique index and, denoting this index by ρ(Yj ) J = arg max , Uj 1≤j≤M we have that YJ has law HM = qK M −1 , i.e., the output law of independence MH initialized at Y1 and using Y2 , . . . , YM as successive proposals. Proof. For M = 1 the statement is trivial so in the remainder of the proof we assume M ≥ 2. Conditional on the candidates, the weights ρ(Yj ) are fixed and positive. The priorities ρ(Yj )/Uj are therefore independent and continuously distributed, so each pair ties with probability zero. A union bound over the finitely many pairs shows that the maximizing index J is almost surely unique. An independent uniform permutation of iid candidates leaves their joint law unchanged. It therefore suffices to show that, for any fixed candidate pool, priority selection and MH processing the candidates in a uniformly random order return the same distribution over candidates. Fix a pool and give its candidates distinct tags 1, . . . , M , even if their responses coincide. Write ri = ρ(Yi ) > 0 and R∗ = maxj rj . We will show that both rules select tag i with probability Z 1/R∗ Y ri (1 − rj t) dt. (17) 0

j̸=i

For the randomly ordered MH rule, initialize at the first candidate and process each remaining candidate once with fresh independent acceptance randomness. For priority selection, conditionQon Ui = u. Tag i wins exactly when Uj ≥ rj u/ri for every j ̸= i, an event of probability j̸=i (1 − rj u/ri )+ . Its effective integration range is 0 < u < min {1, ri / maxj̸=i rj } = ri /R∗ . Substituting t = u/ri gives (17). 16

We prove the same formula for random-order MH by induction on the pool size. For each nonempty tagged set A, let RA = maxj∈A rj and let PA (i) be the probability that the chain finishes at tag i. The induction claim is Z 1/RA Y PA (i) = ri (1 − rk t) dt. 0

k∈A\{i}

It holds immediately for |A| = 1. For m = |A| ≥ 2, condition on the uniformly chosen last tag: X X mPA (i) = PA\{i} (j) min{1, ri /rj } + PA\{j} (i)(1 − rj /ri )+ . j̸=i

j̸=i

The first sum covers the case in which i is processed last and accepted. In the second, another tag j is processed last, so the chain must already be at i and reject j. For fixed A, i, abbreviate Qi (t) =

Y

(1 − rk t),

Bi (t) =

k̸=i

X Y

(1 − rk t),

j̸=i k̸=i,j

with all indices in A. Product differentiation gives Bi − mQi = −(tQi )′ ,

Q′i = −

X

rj

j̸=i

Y

(1 − rk t).

k̸=i,j

We separate the two cases that determine the induction integrals’ upper limits. If ri < RA , removing i leaves a maximal-weight tag. The second sum has nonzero terms only when rj < ri , so those removals also leave a maximal tag. Every nonzero induction integral therefore has the common endpoint 1/RA . For each j, the coefficients combine as rj min{1, ri /rj } + ri (1 − rj /ri )+ = min{ri , rj } + (ri − rj )+ = ri . Consequently, Z 1/RA

Z 1/RA

mPA (i) = ri

Bi (t) dt = mri 0

Qi (t) dt. 0

The last equality uses Bi − mQi = −(tQi )′ and Qi (1/RA ) = 0, since ri < RA and hence some k ∈ A \ {i} satisfies rk = RA , making the factor 1 − rk t in Qi (t) vanish at t = 1/RA . If ri = RA , the first sum in the recursion is 1: when i is last, it is accepted from every preceding state. In every set A \ {j}, tag i remains maximal. Substituting the induction hypothesis into the second sum gives Z 1/RA
mPA (i) = 1 + RA Bi (t) + Q′i (t) dt. 0

Using the same polynomial identity, the endpoint terms are 1/RA

1/R

+ [Qi (t)]0 A = −1. R 1/R They cancel the leading 1, leaving mPA (i) = mRA 0 A Qi (t) dt. This also covers tied maxima because no step assumes that weights are distinct. Thus, for every fixed pool, priority selection and MH with a uniformly random candidate order have the same output law. It therefore follows that the unconditional laws that arise when the two rules are applied to M iid candidates drawn from q are the same. Since the permutation step does not change the joint distribution of the M candidates we conclude that YJ has law qK M −1 , completing the proof. −RA [tQi (t)]0

The priority representation, in particular, gives a way to combine independent batches. If each batch keeps its winning response together with its key r/U , returning the batch winner with the largest key reproduces selection from the combined pool. This requires neither Z nor new model evaluations. Proof of Theorem 1. For M = 1, both selectors return their sole candidate, so H1 = S1 = q. 17

Step 1: Reduce responses to their recorded weights. Let Q be the law of R = ρ(Y ) for Y ∼ q, with finite support R, and let Π(r) be its law under Y ∼ p. Lemma 1 implies that Π(r) =

X

p(y) =

y:ρ(y)=r

X y:ρ(y)=r

q(y)ρ(y) r = Z Z

X

q(y) =

y:ρ(y)=r

rQ(r) Z

Let S = Sx stand for the common support of q and p. Write Rj = ρ(Yj ) and R = (R1 , . . . , RM ), and let J denote the index selected by either method. Conditional on R = r, the candidates are independent, with Yj ∼ q(· | R = rj ). Both MH and SIR choose J using only the weights and independent randomness, so conditioning additionally on J = j does not change this conditional law. In particular, every candidate whose weight is r has the same conditional response law q(· | R = r), regardless of its probability of being selected. For any y with ρ(y) = r, it follows that X Pr(YJ = y, RJ = r | R = r) = Pr(J = j | R = r) Pr(Yj = y | Rj = r) j:rj =r

= q(y | R = r) Pr(RJ = r | R = r). Averaging over R and conditioning on RJ = r gives Pr(YJ = y | RJ = r) = q(y | R = r). Thus selection changes the probabilities of the weight levels but not the relative probabilities of responses within a weight level. Furthermore, note that after conditioning on R the target and the proposal coincide: p(y)1{ρ(y) = r} q(y)r 1{ρ(y) = r}/Z = Π(r) rQ(r)/Z q(y)1{ρ(y) = r} = q(y | R = r) ∀y ∈ S = Q(r)

p(y | R = r) =

∀ r ∈ R.

Thus, for either MH’s or SIR’s output law µ ∈ {HM , SM } and its selected-weight law U, µ(y) U(ρ(y))q(y | R = ρ(y)) U(ρ(y)) = = p(y) Π(ρ(y))q(y | R = ρ(y)) Π(ρ(y))

∀ y ∈ S.

(18)

In addition, for either law µ ∈ {HM , SM } we have that µ(y) ≥ Pr{Y1 = y, . . . , YM = y} > 0

∀ y ∈ S.

(19)

Using (18) and (19) we derive Df (µ∥p) =

X



µ(y) p(y)

X

p(y)f

y∈S

=



p(y)f

X



r∈R y:ρ(y)=r

=

X

 Π(r)f

r∈R

U(r) Π(r)

U(r) Π(r)

 (20)



= Df (U∥Π). Step 2: Couple the selected weights. Consider a fixed rollout pool tagged with rj = ρ(yj ) > 0. Draw iid uniforms Uj and put Ej = − log(1−Uj ). The Ej /rj are independent exponential variables with rates rj , so their minimum occurs at tag j with probability Z ∞ Y rj rj e−rj t e−rk t dt = P . 0 k rk k̸=j

Minimizing Ej /rj implements ordinary SIR, while minimizing Uj /rj implements priority selection. By Lemma 2, the latter has MH’s output law when the candidates are iid from q. 18

Let i be the priority winner and j the SIR winner. Define g(u) = − log(1 − u)/u. If i ̸= j, uniqueness of the continuous keys gives Ui Uj < , ri rj

g(Uj )

Uj Ui < g(Ui ) . rj ri

These inequalities imply g(Ui ) > g(Uj ) and therefore, since the function g is strictly increasing on (0, 1), we have that Ui > Uj and ri /rj > Ui /Uj > 1. Whenever the winners differ, priority selection returns the larger weight. Averaging over iid candidates and applying Lemma 2, we conclude that the distribution of the importance weight selected by MH stochastically dominates that selected by SIR.2 Step 3: Convert the weight ordering to a divergence ordering. Let HM and SM be the distributions of the weight selected by MH and SIR, respectively. Define B(u) = EQ (1 − uR)+ . Conditional on Y1 = y and U1 = u, a competitor fails to beat candidate 1 with probability B(u/ρ(y)). Independence of the competitors and exchangeability of the M tags give Z 1 HM (y) =M B(u/ρ(y))M −1 du. q(y) 0 Changing variables and using Π(r) = rQ(r)/Z, we obtain Z 1/ρ(y) Z 1/r HM (r) HM (y) M −1 = M ρ(y) B(u) du, hM (r) := = MZ B(u)M −1 du. q(y) Π(r) 0 0 (21) For M = 1 the integrand is read as 1. The upper limit decreases with r, so hM is nonincreasing: relative to the target, finite-budget MH favors smaller weights. Equation (21) also follows from the exact transition formula of Smith & Tierney (1996), restated by Wang (2022, Theorem 4). From a minimum-weight response y− , MH accepts every proposal, so K(y− , ·) = q and HM = K M (y− , ·). Substituting this initialization into their formula gives the displayed density. Lemma 2 additionally identifies the conditional selection law on a randomly ordered tagged pool. ′ (hM (r)). The ratios hM (r) are positive, and Let sM (r) = SM (r)/Π(r) and choose b(r) = f+ a finite convex function has a finite right derivative at every interior point of its domain. Since that derivative is nondecreasing and hM is nonincreasing, b is a nonincreasing subgradient. The supporting-line inequality gives X Df (SM ∥Π) − Df (HM ∥Π) ≥ Π(r)b(r)(sM (r) − hM (r)) r

= ESM b − EHM b ≥ 0.

(22)

The final inequality follows from the stochastic domination established in Step 2: MH selects stochastically larger weights than SIR, so the expectation of the nonincreasing function b is no larger under HM than under SM . Equation (20) gives the desired response-law comparison. Taking f (u) = u log u and using (7) gives J(HM ) ≥ J(SM ). Step 4: Establish strictness. Suppose M ≥ 2 and ρ is nonconstant. At any nontrivial cutoff r0 , that is, min R ≤ r0 < max R, choose supported weights l ≤ r0 < h. A pool containing both weights has positive probability. We construct an open set of keys on which priority selects h and SIR selects l. Write R∗ for the pool’s largest weight. Choose 0 < v < 1/(2R∗ ) and set Uh = hv and Ul = l(1 + ξ)v. At ξ = 0 the priority keys U/r tie, while the exponential keys satisfy g(hv)v > g(lv)v, where g(u) = − log(1 − u)/u is the strictly increasing function defined in Step 2. For sufficiently small ξ > 0, priority selection therefore chooses h, while SIR chooses l. Taking all other uniforms 2 This step uses only the monotonicity of u 7→ − log(1 − u)/u. The same argument therefore applies to any race that selects the smallest value of Ψ−1 (Uj )/rj , where Ψ−1 is the quantile function of an atomless positive noise and Ψ−1 (u)/u is nondecreasing. Noise with a nonincreasing density is one example. For such races, priority selection again picks at least as large a weight.

19

sufficiently close to 1 prevents either rule from selecting another tag. The strict inequalities persist on an open neighborhood, which has positive probability. Together with the almost-sure weight ordering, this proves SM ((0, r0 ]) > HM ((0, r0 ]) at every nontrivial cutoff. In particular SM ̸= HM , so the supporting-line inequality in (22) is strict whenever f is strictly convex. Total variation needs a separate argument. Since B(u) > 0 for 0 ≤ u < 1/ min R, formula (21) makes hM strictly decreasing across distinct supported weights. Together with EΠ hM = 1, this implies that A = {r : hM (r) > 1} is a nonempty proper lower set. Therefore ∥SM − Π∥TV ≥ SM (A) − Π(A) > HM (A) − Π(A) = ∥HM − Π∥TV . The scalar reduction (20) transfers both strictness conclusions to the response laws. A.3

S TATIONARITY AND CONVERGENCE IN TOTAL VARIATION

Let µn = µ0 K n for any initial distribution µ0 on the common finite support. The classical independence-sampler minorization gives the convergence rate used below (Tierney, 1994; Mengersen & Tweedie, 1996; Liu, 1996). Proposition 2 (Convergence). The target p is stationary for K, and for n ≥ 1, ∥µn − p∥TV ≤ (1 − ε)n ∥µ0 − p∥TV , Here ∥µ − ν∥TV = 12

ε=

Z 1 = ∈ (0, 1]. maxy ρ(y) maxy p(y)/q(y)

(23)

y |µ(y) − ν(y)| is the total variation distance.

P

Proof. Write ρmax = maxy ρ(y). Positivity on the finite support gives 0 < Z = Eq ρ ≤ ρmax , so ε ∈ (0, 1]. For distinct y, y ′ , the MH kernel satisfies K(y, y ′ ) = q(y ′ ) min{1, ρ(y ′ )/ρ(y)},

p(y)K(y, y ′ ) =

q(y)q(y ′ ) min{ρ(y), ρ(y ′ )}. Z

The last expression is symmetric. Detailed balance therefore holds, and summing it over the initial state gives pK = p. For every y, y ′ , including the diagonal, where rejected proposals only add mass, K(y, y ′ ) ≥ q(y ′ ) min{1, ρ(y ′ )/ρ(y)} ≥

q(y ′ )ρ(y ′ ) = εp(y ′ ). ρmax

(24)

If ε = 1, every row of K equals p, and one update reaches the target. Otherwise define the residual Markov kernel K(y, y ′ ) − εp(y ′ ) R(y, y ′ ) = . 1−ε Its entries are nonnegative, its rows sum to 1, and pR = p. Thus each update is a draw from p with probability ε and an R-transition otherwise. The triangle inequality and the row sums of R give X X X (µ(y) − ν(y))R(y, y ′ ) ≤ |µ(y) − ν(y)|. y′

y

y

Consequently, ∥µK − p∥TV = (1 − ε)∥µR − pR∥TV ≤ (1 − ε)∥µ − p∥TV . Iteration proves (23). 20

A.4

P ROOF OF P ROPOSITION 1

We first establish three auxiliary facts: data processing under a stationary kernel, a threshold representation of the MH output law, and convexity of its divergence in the candidate budget. We then combine them with a recorded-weight bound to prove Proposition 1. The objective-gap identity (7) covers both consensus and, under the exact-specialist assumptions, the external reward objective. The consensus objective is also the zero-reward case of multi-reference KL-regularized RLHF (Aminian et al., 2025). Lemma 3 (Data processing under a stationary kernel). Let K be the independence-MH kernel with stationary law p. For every positive response law µ and every convex generator f considered in Theorem 1, Df (µK∥p) ≤ Df (µ∥p). For KL, the inequality also holds when µ assigns probability zero to some responses. Proof. We establish data processing for the convex generators used throughout the paper. For a positive law µ, put r(y) = µ(y)/p(y) and let (Y, Y ′ ) have the stationary joint law p(y)K(y, y ′ ). Since pK = p, (µK)(y ′ ) = E[r(Y ) | Y ′ = y ′ ]. p(y ′ ) The conditional Jensen inequality therefore gives Df (µK∥p) ≤ E[f (r(Y ))] = Df (µ∥p). For KL, continuity extends this inequality to initial laws that assign probability 0 to some responses. For the threshold representation, write B(u) = Eq (1 − uρ(Y ))+ ,

Fρ (t) = p{ρ(Y ) ≤ t}.

Here B is the function in (21), and Fρ is the CDF of ρ(Y ) under Y ∼ p. Lemma 4 (Threshold representation). Let Y1 , . . . , YM be iid q, and let U1 , . . . , UM be iid uniform on (0, 1), independent of the candidates. Set J = arg max j≤M

ρ(Yj ) , Uj

ΛM = max j≤M

ρ(Yj ) . Uj

For t > 0, Pr(ΛM ≤ t) = B(1/t)M . For almost every t in the support of ΛM , the conditional law of YJ given ΛM = t is p(· | ρ ≤ t). In particular,   1{ρ(y) ≤ ΛM } HM (y) = p(y) E . (25) Fρ (ΛM ) Proof. A single priority key satisfies   ρ(Y ) Pr ≤ t = Eq (1 − ρ(Y )/t)+ = B(1/t). U Independence gives the CDF of ΛM . Given Y1 = y, the first key has density ρ(y)t−2 on t > ρ(y). Candidate 1 is then selected with ΛM ∈ dt exactly when its key lies in dt and every other key is at most t. By exchangeability, for t > miny ρ(y), Pr(YJ = y, ΛM ∈ dt) = M q(y)ρ(y)t−2 1{ρ(y) < t}B(1/t)M −1 dt. Summing over y gives the density M ZFρ (t)t−2 B(1/t)M −1 of ΛM , apart from the finitely many weight values, which have probability 0. Dividing the joint density by this marginal density yields Pr(YJ = y | ΛM = t) =

p(y)1{ρ(y) ≤ t} . Fρ (t)

The denominator is positive almost surely. Integrating over t and applying Lemma 2 proves (25).

21

Lemma 5 (Convexity in the candidate budget). Under the assumptions of Theorem 1, put dM = Df (HM ∥p). Then dM is nonincreasing and 2dM ≤ dM −1 + dM +1 ,

M ≥ 2.

(26)

Moreover, let B ≥ 1 be an integer-valued candidate budget independent of all proposals and selectionPrandomness, with EB ≤ M . The marginal output law of MH run with this random budget, H = b≥1 Pr(B = b)Hb , satisfies Df (HM ∥p) ≤ Df (H∥p).

(27)

The right-hand side is the divergence of the mixture law, after averaging over the budget. The lemma concerns proposal initialization and a pool-independent budget. Stopping rules that depend on the observed candidates are not covered and can yield greater error than the proposal itself. For example, with q = (1/2, 1/2) and ρ = (1/2, 1), so that p = (1/3, 2/3), stopping after the first candidate when its weight is 1/2 and otherwise applying one MH update returns (5/8, 3/8), which is farther from p than q. Proof. We first compare fixed and random budgets, then obtain discrete convexity from a two-point budget distribution. Independent budget randomization. Let ΛB be the largest priority key at budget B. Jensen’s inequality for the convex map b 7→ B(1/t)b , followed by EB ≤ M , gives Pr(ΛB ≤ t) = E[B(1/t)B ] ≥ B(1/t)EB ≥ B(1/t)M = Pr(ΛM ≤ t). Hence ΛB is stochastically smaller than ΛM . For any nondecreasing function g on the weight support, the truncated mean t 7−→ Ep [g(ρ) | ρ ≤ t] is nondecreasing wherever Fρ (t) > 0: enlarging the threshold adds only weights at least as large as those already included. The conditional law in Lemma 4 depends on the threshold but not on the budget. Applying the lemma and averaging over B therefore gives EH g(ρ) = E Ep [g(ρ) | ρ ≤ ΛB ] ≤ E Ep [g(ρ) | ρ ≤ ΛM ] = EHM g(ρ). Every Hb and their mixture preserve the target’s conditional response law at each weight, as in (20). ′ The density ratio hM (r) in (21) is nonincreasing in r, so ψ(r) = f+ (hM (r)) is also nonincreasing. The supporting-line argument of (22) now gives Df (H∥p) − Df (HM ∥p) ≥ EH ψ(ρ) − EHM ψ(ρ) ≥ 0. This proves (27) for the marginal mixture law. Discrete convexity. For M ≥ 2, choose B = M − 1 or M + 1 with equal probabilities. Equation (27) and convexity of Df in its first argument imply   dM −1 + dM +1 HM −1 + HM +1 dM ≤ Df p ≤ . 2 2 Monotonicity follows by applying Lemma 3 to HM +1 = HM K. Proof of Proposition 1. Fix either objective in (7), with scale λ > 0. Write dM = KL(HM ∥p). Nonnegative, diminishing gains. Lemma 3 gives dM +1 = KL(HM K∥pK) ≤ dM . Lemma 5 also gives 2dM +1 ≤ dM + dM +2 . Hence 0 ≤ J(HM +2 ) − J(HM +1 ) = λ(dM +1 − dM +2 ) ≤ λ(dM − dM +1 ) = J(HM +1 ) − J(HM ). 22

Recorded-weight lower bound. We use the augmented-space construction of Domke & Sheldon (2018). Let Q be the joint law of a proposal pool and its SIR-selected index. Compare it with P, which chooses an index uniformly, draws that candidate from p, and draws the others independently from q:   M Y ρ(yi ) Q(y1:M , i) =  q(yj ) PM , j=1 ρ(yj ) j=1 Y 1 P(y1:M , i) = p(yi ) q(yj ). M j̸=i

Both are probability laws. Under the selected-response map (y1:M , i) 7→ yi , their marginals are SM and p, respectively. The identity p = qρ/Z gives MZ Q(y1:M , i) = PM . P(y1:M , i) j=1 ρ(yj ) This ratio does not depend on the selected index, and the pool marginal of Q is q M . Data processing therefore yields KL(SM ∥p) ≤ KL(Q∥P) 



 M X 1 = log Z − EqM log  ρ(Yj ) . M j=1

(28)

This is the importance-weighted variational bound in its SIR form (Cremer et al., 2017; Domke & Sheldon, 2018). Theorem 1 gives the same upper bound for KL(HM ∥p), while KL(q∥p) = log Z − Eq log ρ.

(29)

Subtracting (28) from (29) cancels log Z. By the objective-gap identity,     M M X X 1 1 J(HM ) − J(q) ≥ λ EqM log  ρ(Yj ) − log ρ(Yj ) M j=1 M j=1 (30)

= λ EqM GM .

The same lower bound holds for J(SM ) − J(q). Concavity of log gives GM ≥ 0, with equality exactly when all weights in the pool are equal. For M = 1, both selectors return a draw from q and the bound equals 0. Finally, take J = Jex and λ = 1 for consensus. Under the exact-specialist ext assumptions, (6) and (7) give the same conclusions with J = Jw,x and λ = β. PM Certificate dependence on budget. Write ρ̄M = M −1 j=1 ρ(Yj ), so that EGM = E log ρ̄M − Eq log ρ. By the importance-weighted bound of Burda et al. (2016, Theorem 1), E log ρ̄M is nondecreasing in M and converges to log Z, because ρ is bounded above and away from 0 on the finite support. Hence EqM GM is nondecreasing in M and converges to log Z − Eq log ρ = KL(q∥p). The certificate is therefore asymptotically tight: the improvement of either method is also at most λKL(q∥p). Confidence bounds for a fixed prompt list. Let x1 , . . . , xL be fixed prompts, each satisfying the proposition’s assumptions, with a common scale λ > 0 in the objective-gap identity. For A ∈ {H, S}, define the equally weighted prompt averages of the improvement and of the expected pool gap by L L  1 X 1X A ∆M = Jxℓ (AM,xℓ ) − Jxℓ (qxℓ ) , gM = EqxM GM,xℓ . ℓ L L ℓ=1

ℓ=1 A Applying (30) at each prompt gives ∆M ≥ λg M ≥ 0 for both selectors.

Fix a nonempty finite budget set M ⊆ {1, 2, . . .}, a group count K0 ≥ 1, a clipping cap Γ > 0, and an error level α ∈ (0, 1), all chosen independently of the evaluation pools. At each prompt, generate 23

K0 independent pools of max M proposals from qxℓ , independently across prompts. Evaluate each budget M ∈ M using the first M candidates of each pool and their exact recorded weights. With N = LK0 , set L K0 1 XX (M ) (k) (M ) Xℓk = min{GM,xℓ , Γ}, gbM,Γ = Xℓk . N ℓ=1 k=1

For each M , these N variables are independent and lie in [0, Γ], although their distributions may differ across prompts. Equal group counts and clipping give Eb gM,Γ ≤ g M . Hoeffding’s inequality for independent bounded variables implies   2N t2 Pr(b gM,Γ − g M ≥ t) ≤ exp − 2 , t > 0. Γ Use failure probability α/|M| for each budget and take a union bound. Combining the resulting event with the pointwise certificate yields, with probability at least 1 − α, ( ) r log(|M|/α) A ∆M ≥ λ max 0, gbM,Γ − Γ , M ∈ M, A ∈ {H, S}. (31) 2N Taking L = 1 and M = {M } gives the bound for a single prompt and a single budget. Reusing candidate prefixes across budgets is valid because the union bound requires no cross-budget independence. The same event covers both selectors. Coverage is conditional on the fixed prompts and checkpoints: it concerns the objective improvement of the marginal output laws, averaged over these prompts and over fresh proposal pools, and not a realized response or a newly sampled prompt set. A.5

P ROOF OF T HEOREM 2

We combine a quadratic expansion of local log normalizers with an operator form of the classical independence-MH transition formula (Smith & Tierney, 1996; Liu, 1996) and the SIR marginal formula (Cremer et al., 2017). Lemma 6 (Exact MH residual). For a fixed positive finite-support instance, put ω = q/p = Z/ρ and define (Lω f )(y) = Ep [(ω(X) − ω(y))+ ]f (y) − Ep [f (X)(ω(y) − ω(X))+ ]. Then HM /p − 1 = −LM ω 1 for every M ≥ 1. Proof. Let Q have every row equal to q and set ∆ = K − Q. For a signed measure ν of total mass 0, νK = ν∆, and ν∆ also has total mass 0. Stationarity of p therefore gives HM − p = (q − p)∆M −1 . A direct calculation gives ∆(x, y) = −p(y)(ω(y) − ω(x))+

(x ̸= y),

∆(x, x) = Ep [(ω(X) − ω(x))+ ].

Thus (pf )∆ = pLω f . Since Ep ω = 1, Lω 1 = 1 − ω, and iteration proves the identity. Proof of Theorem 2. Fix the family in Theorem 2: the finite support tree, horizon T , common policy π0 , weights, perturbations ai , and candidate budget M do not vary with δ. Let P0 be the completeresponse law induced by π0 . All remainders below are uniform over responses on this fixed support. The finite exponential-tilt family satisfies qδ = P0 + O(|δ|) and pδ = P0 + O(|δ|). Quadratic log correction. Write ā(v, h) = from the local proposal, giving qδ (v | h) =

P

i wi ai (v, h).

The component normalizers cancel

π0 (v | h)eδā(v,h) . EV ∼π0 (·|h) eδā(V,h)

At a fixed prefix h, define the log moment-generating functions Ai (δ; h) = log Eπ0 (·|h) eδai ,

Aā (δ; h) = log Eπ0 (·|h) eδā . 24

The local normalizer therefore satisfies log zδ (h) = Aā (δ; h) −

X

wi Ai (δ; h).

i

Taylor expansion on the finite support gives δ2 var(ai ) + O(|δ|3 ), 2 with the analogous expansion for Aā . Here expectations and variances are under π0 (· | h). The linear terms cancel, and the quadratic terms satisfy X X wi var(ai ) − var(ā) = wi var(ai − ā). Ai (δ; h) = δEai +

i

i

For a complete response y with prefixes ht , set D(y) =

T X X t=1

i

wi

var

V ∼π0 (·|ht )

[ai (V, ht ) − ā(V, ht )] ,

C=

1 var [D(Y )]. 8 Y ∼P0

(32)

Thus D(y) accumulates the weighted variance of the component perturbations about their average along the response. Deterministic EOS padding contributes 0 to these variances. Summing the local expansions gives δ2 ℓδ (y) := log ρδ (y) = − D(y) + O(|δ|3 ). (33) 2 Leading proposal bias.

By Lemma 1, pδ = qδ ρδ /Zδ , where Zδ = Eqδ ρδ . Hence

KL(qδ ∥pδ ) = log Eqδ eℓδ − Eqδ ℓδ 1 = var(ℓδ ) + O(|δ|6 ) 2 qδ δ4 = var(D) + O(|δ|5 ) = Cδ 4 + O(|δ|5 ). 8 P0

(34)

The second line follows from ∥ℓδ ∥∞ = O(δ 2 ): the remainder in the log moment-generating expansion is cubic in ℓδ . The final remainder also accounts for the cubic term in (33) and the change of measure qδ = P0 + O(|δ|). The coefficient C therefore measures variation of D across responses. If D is constant, the quartic term vanishes, although higher-order terms can still produce bias. MH contraction. uniformly and

Write Wδ = pδ /qδ = ρδ /Zδ . The expansion of ℓδ gives Wδ = 1 + O(δ 2 )

(1 − Wδ )2 = 2Cδ 4 + O(|δ|5 ). (35) Wδ Also εδ = Zδ / maxy ρδ (y) ≥ e− osc(ℓδ ) , so 1 − εδ = O(δ 2 ). The minorization in Appendix A.3 writes Kδ = εδ Pδ + (1 − εδ )Rδ , where every row of Pδ is pδ and pδ Rδ = pδ . Conditional Jensen under the stationary joint law pδ (y)Rδ (y, y ′ ) gives χ2 (qδ ∥pδ ) = Eqδ

χ2 (µKδ ∥pδ ) = (1 − εδ )2 χ2 (µRδ ∥pδ ) ≤ (1 − εδ )2 χ2 (µ∥pδ ).

(36)

The same inequality holds for any positive finite-support independence sampler. If εδ = 1, then Kδ = Pδ . Iteration and KL ≤ χ2 imply KL(HM,δ ∥pδ ) ≤ (1 − εδ )2(M −1) χ2 (qδ ∥pδ ) = O(|δ|4M ). Exact MH coefficient.

(37)

Put D = EP0 D and define the disagreement operator

(T f )(y) = EP0 [(D(X) − D(y))+ ]f (y) − EP0 [f (X)(D(y) − D(X))+ ].

(38)

Its range consists of P0 -mean-zero functions, and T 1 = D − D. Normalizing (33) gives ωδ = qδ /pδ = 1 + δ 2 (D − D)/2 + O(|δ|3 ). Since the positive-part function is 1-Lipschitz and pδ = P0 + O(|δ|), δ2 Lωδ = T + O(|δ|3 ) 2 25

as operators on the fixed finite-dimensional function space. Applying Lemma 6 yields the uniform density expansion HM,δ δ 2M − 1 = M T M −1 (D − D) + O(|δ|2M +1 ). (39) pδ 2 For v = HM,δ /pδ − 1, we have Epδ v = 0, so KL(HM,δ ∥pδ ) = 12 Epδ v 2 + O(∥v∥3∞ ). Consequently, EP0 [(T M −1 (D − D))2 ] . (40) 2 · 4M In particular C1 = varP0 (D)/8 = C. If D is constant, every CM vanishes. Otherwise, let Dmin = miny D(y) and c = (D − Dmin )/2 > 0. At a response with D = Dmin , the operator multiplies every function by 2c, so T M −1 (D − D) = −(2c)M there. The set {D = Dmin } has positive P0 -mass, proving CM > 0. KL(HM,δ ∥pδ ) = CM δ 4M + O(|δ|4M +1 ),

SIR’s leading coefficient.

CM =

Write Wδ = 1 + u δ ,

Eqδ uδ = 0.

Normalizing the expansion in (33) gives δ2 (D(y) − EP0 D) + O(|δ|3 ). (41) 2 Conditioning on one candidate and using exchangeability of the candidate indices yields the exact identity " # SM,δ (y) 1 iid =ME , Yj ∼ qδ . (42) PM pδ (y) M + uδ (y) + j=2 uδ (Yj ) uδ (y) = −

The perturbation of the denominator is uniformly O(δ 2 ). In its reciprocal expansion, the terms linear in uδ (Yj ) vanish in expectation. The quadratic term is [uδ (y)2 + (M − 1)Eqδ u2δ ]/M 2 = O(δ 4 ), so vδ (y) :=

uδ (y) SM,δ (y) −1=− + O(|δ|4 ). pδ (y) M

(43)

Because Epδ vδ = 0, the linear term in the expansion of (1 + vδ ) log(1 + vδ ) also vanishes. Thus 1 Ep v 2 + O(|δ|6 ) 2 δ δ 1 Ep u2 + O(|δ|6 ) = 2M 2 δ δ δ4 = var(D) + O(|δ|5 ) 8M 2 P0 C = 2 δ 4 + O(|δ|5 ). (44) M The third line uses (41) and pδ = P0 +O(|δ|), accounting again for the changing measure. Together, (34), (40), and (44) prove (13). KL(SM,δ ∥pδ ) =

The operator (38) describes how rejections propagate the leading residual. Its first term retains residual mass at a response, while the second accounts for rejected moves from responses with less accumulated disagreement. The common proposal part cancels on every mass-zero residual. At minimum-disagreement responses, only the first term remains, which prevents the leading error from vanishing when C > 0. Dependence on the tree. The constants in Theorem 2 depend on the tree, and the expansion is asserted only for a fixed tree. For example, concatenate N independent two-token modules. Both policies choose j ∈ {0, 1} uniformly. Conditional on j, their second-token laws are proportional to eδjs and e−δjs for s ∈ {−1, 1}. This is an instance of the fixed-score family in Theorem 2, with PN D = k=1 jk under the common uniform policy, so C = N/32. Although C grows linearly in N , the remainder is not uniform in N , so the expansion does not describe long responses at a fixed separation δ. Appendix A.6 treats growing horizons directly. 26

A remark on soft best-of-M . With weights ρ = eR/λ , ordinary SIR is soft best-of-M (Verdun et al., √ 2025). Theorem 2 of Verdun et al. (2025) (arXiv:2505.03156v1) states that ∥SM − p∥TV ≥ C ′ / M − 1 for a constant C ′ > 0 that does not depend on M , and concludes that KL(p∥SM ) = Ω(1/M ). This lower bound does not hold. Take their binary example with q(0) = q(1) = 1/2, R(y) = y, and λ = 1/ log 2, so that ρ = (1, 2) and p(1) = 2/3. With B ∼ Binomial(M, 1/2), the exact marginal is SM (1) = E[f (B/M )] for f (t) = 2t/(1 + t). A Taylor expansion at t = 1/2, with f ′′ (1/2) = −32/27 and E(B/M − 1/2)2 = 1/(4M ), gives SM (1) = 2/3 − 4/(27M ) + O(M −2 ). Consequently, 4 4 KL(p∥SM ) = + O(M −3 ), ∥SM − p∥TV = + O(M −2 ). 2 81M 27M Their Appendix D instead reports a leading KL term 1/(9M ) for this example, because a variance term of order 1/M in the expansion of SM (1) is treated as O(M −2 ). Their Theorem 1 upper bound, here KL(p∥SM ) ≤ log(1 + 1/(9M )), remains valid. A.6

C ANDIDATE COVERAGE AND PROOF OF T HEOREM 3

This subsection proves Theorem 3 and specializes it to independent copies of the running example. The sample-size scale eKL(p∥q) is classical in importance sampling (Chatterjee & Diaconis, 2018). Approximate rejection sampling and channel simulation also relate finite-pool accuracy to likelihood tails (Block & Polyanskiy, 2023; Flamich & Wells, 2024). Our result identifies the exact limiting TV error at the threshold and shows that unmodified MH and ordinary SIR both attain it. Lemma 7 (Candidate coverage). Let a selection rule return one of M ≥ 1 iid candidates drawn from q, and let ν be its output law. The rule may randomize and may know the full instance. For every set A of responses, q(A)M ≤ ν(A) ≤ 1 − (1 − q(A))M . Proof. The output lies in A whenever all M candidates do, and only if at least one does. A likelihood-tail converse. Put W = p/q and L = log W . Every candidate selector satisfies ν(A) ≤ M q(A). On A = {L ≥ τ }, q(A) = Ep [e−L 1A ] ≤ e−τ , so ∥ν − p∥TV ≥ p{L ≥ τ } − M e−τ . (45) −τ In particular, if τ is a median of L under p, the right-hand side is at least 1/2−M e . This coverage bound holds even for selectors with full instance knowledge. The converse identifies target mass that the pool is unlikely to reach. For the matching upper bound, we temporarily cap the largest importance weights, making convergence to the capped target easier to control. The next lemma transfers the resulting bound back to MH and SIR with their original weights. Lemma 8 (Clipping and distance to the original target). Let W = p/q > 0 on a common finite support. For B > 0, let AM and AB M be the output laws of either proposal-initialized MH or ordinary SIR using weights W and WB = min(W, B), respectively. Then Df (AM ∥p) ≤ Df (AB M ∥p) for every convex generator in Theorem 1. Proof. Use the same candidates and race variables Rj in both selectors: uniform variables for MH’s priority representation, exponential variables for SIR. If the original winner i had Wi < Wj for the clipped winner j, their winning inequalities would imply Wj Rj min(Wj , B) < < . Wi Ri min(Wi , B) This is impossible because W/ min(W, B) is nondecreasing. Continuous keys are almost surely distinct, including when candidate weights tie. Thus the original selected weight stochastically dominates the clipped selected weight. Both outputs preserve q(· | W ), and the original ratio AM /p is nonincreasing in W . For MH this follows from (21). For SIR it follows from " # SM (y) 1 iid , Yj ∼ q. = ME PM p(y) W (y) + j=2 W (Yj ) 27

′ Consequently ψ(W ) = f+ (AM /p) is nonincreasing in W . The supporting-line argument in (22) gives Df (AB ψ(W ) − EAM ψ(W ) ≥ 0. M ∥p) − Df (AM ∥p) ≥ EAB M

Proposition 3 (Finite-budget likelihood-tail bounds). For B > 0, define αB = Eq min(W, B),

tB = 1 − αB = Eq (W − B)+ .

Then tM ≤

inf ν∈SM (q)

∥ν − p∥TV ≤ ∥HM − p∥TV ≤ inf



B>0

tB + (1 − αB /B)M .

(46)

The upper bound also holds with the last power replaced by e−M αB /B . Clipping is used only in the proof. The MH law HM uses the original weights. Proof. Every selector satisfies ν(y) ≤ M q(y). Summing p − M q over {W > M } gives the lower bound tM . For the upper bound, set pB = qWB /αB . The clipped target obeys pB /q ≤ B/αB , so independence MH with clipped weights has minorization constant at least αB /B. Since q ≥ (αB /B)pB , proposal initialization gives ∥q − pB ∥TV ≤ 1 − αB /B. Proposition 2 therefore yields B ∥HM − pB ∥TV ≤ (1 − αB /B)M .

Also p ≥ αB pB , so ∥p − pB ∥TV ≤ 1 − αB = tB . Apply Lemma 8, the triangle inequality, and 1 − u ≤ e−u . Proof of Theorem 3. Write WN = pN /qN , LN = log WN , ℓN = log MN , and c = Ψ(b). Set AN = {LN > ℓN }. The assumed convergence gives pN (AN ) → 1 − c. For any ϵ > 0 such that Ψ is continuous at b + ϵ, MN qN (AN ) = EpN [eℓN −LN 1AN ] ≤ pN {ℓN < LN ≤ ℓN + ϵsN } + e−ϵsN . Taking the limit superior and then sending ϵ ↓ 0 through continuity points gives MN qN (AN ) → 0. By candidate coverage, every selector’s mass on AN tends to 0, uniformly over selection rules. Hence lim inf inf ∥ν − pN ∥TV ≥ 1 − c. N

ν∈SMN (qN )

Binary KL data processing also gives the general converse lim inf N

inf ν∈SMN (qN )

KL(ν∥pN ) ≥ − log c.

(47)

Indeed, ν(AN ) → 0 uniformly while pN (AN ) → 1 − c ∈ (0, 1). We claim attainment only for TV under the theorem’s assumptions. For the upper bound, choose

√ kN = exp min{ sN , 12 log MN } ,

BN = MN /kN .

Then kN → ∞, kN = o(MN ), and log kN = o(sN ). The preceding tail argument with log BN in place of ℓN gives αN := EqN min(WN , BN ) = pN (WN ≤ BN ) + BN qN (WN > BN ) −→ c. Proposition 3 now implies ∥HMN − pN ∥TV ≤ 1 − αN + e−αN kN −→ 1 − c in the sense of a limit superior. To handle SIR, let pBN = qN min(WN , BN )/αN and U = min(WN , BN )/αN . Under qN , EU = 1 and U ≤ KN := BN /αN , where KN ≥ 1. The clipped SIR output then satisfies, by Jensen’s inequality, " # BN SM (y) 1 MN N ≥ = MN E . PMN pBN (y) KN + MN − 1 U (y) + j=2 U (Yj ) 28

This density lower bound yields KN − 1 1 ≤ −→ 0. KN + M N − 1 αN kN Since ∥pN − pBN ∥TV ≤ 1 − αN , Lemma 8 and the triangle inequality give the same upper bound 1 − c on the limit superior for unmodified SIR. Together with the uniform converse, this proves that both methods attain the limit in (14). BN − pBN ∥TV ≤ ∥SM N

Independent copies of Example 1.

For δ > 0, one module has two equally weighted specialists e±δjs π±,δ (j, s) = , (j, s) ∈ {0, 1} × {−1, 1}. 2(1 + cosh δ) These are exact optima for rewards ±βδjs under a uniform reference. Their sequence product is uniform. Write ec δ 2 cδ = log cosh δ, γδ = , aδ = . 1 + e cδ 1 + ecδ The local decoder chooses j = 1 with probability γδ and s uniformly, recording weight e−cδ j . At δ = log 3, a single module is exactly the example in Figure 1. For N independent modules, let PN N1 = k=1 jk be the number of modules with jk = 1. Then N1 ∼ Bin(N, γδ )

under qN ,

−cδ N1

N1 ∼ Bin(N, 1/2)

under pN ,

ZN = aN δ .

ρN = e , Thus LN = −cδ N1 − N log aδ , with

(48)

N c2δ . (49) 4 For fixed δ > 0, the binomial central limit theorem verifies the hypotheses of Theorem 3 with 4 Ψ = Φ, the standard normal CDF. The same conclusion holds for δ = δN → 0 when N δN → ∞, 4 2 4 since then dN ∼ N δN /32 and sN ∼ N δN /16 → ∞. The budget must use the exact center in (49) because its leading approximation need not be accurate to o(sN ). s2N =

dN = KL(pN ∥qN ) = N log cosh(cδ /2),

There is also an elementary finite-horizon bound. Put ∆δ = γδ − 1/2 = 12 tanh2 (δ/2) and EN = {N1 /N ≤ 1/2 + ∆δ /2}. Hoeffding’s inequality gives 2

2

pN (EN ) ≥ 1 − e−N ∆δ /2 , qN (EN ) ≤ e−N ∆δ /2 . By candidate coverage, every selector of M complete proposals obeys 2

∥ν − pN ∥TV ≥ 1 − (M + 1)e−N ∆δ /2 . (50) 2 4 At fixed TV accuracy below 1, this requires a budget exponential in N ∆δ , which is of order N δ for small δ. In contrast, querying the two child normalizers in each module gives the exact first-token conditional by multiplying the common root probabilities by those normalizers. This conditional is uniform, as is the second-token conditional. This sequential sampler uses O(N ) conditional policyvector evaluations on this structured family. The comparison counts returned probability vectors, not transformer FLOPs, and does not assert an efficient exact sampler on arbitrary response trees.

B

E XTENSIONS AND LIMITS

This appendix develops extensions and limits of the main results. We first extend the comparison of Theorem 1 to other schedules with the same budget. We then establish optimality guarantees under different information constraints, show that no rollout-only statistic can certify a small remaining error, and treat continuation-guided proposals and approximate specialists. The optimality results concern rules that return one of M iid complete candidates from a fixed proposal, so they exclude adaptive proposal construction and prefix-level search. They differ in the information available to the selector. The exact minimax bound allows complete knowledge of the target and proposal, because knowing where target mass lies cannot supply a response missing from the candidate pool. The nearby-policy lower bound instead hides unobserved weights and the normalizer. For weight-only admissibility, the rule uses only recorded weights and must be shared across instances. These are worst-case or uniform guarantees, not claims that MH is best on each instance. 29

B.1

M ULTIPLE - TRY AND I -SIR SCHEDULES

The multiple-try comparison uses the recycled-trial independence sampler of Yang & Liu (2023), a specialization of the multiple-try Metropolis method of Liu et al. (2000). From the current state y, draw Y1:k ∼ q k , select J with probability proportional to ρ(YJ ), and accept YJ with probability ( ) Pk ρ(Yi ) i=1 P min 1, . ρ(y) + i̸=J ρ(Yi ) Write Ak for this kernel. No additional reverse trials are drawn. The iterated SIR (i-SIR) kernel Pk+1 keeps the current state y, adds k fresh q candidates, and resamples from this pool proportionally to the weights (Andrieu et al., 2018). Both blocks cost k fresh candidates. The single-proposal multiple-try kernel satisfies A1 = K, and proposal-initialized i-SIR satisfies qPk+1 = Sk+1 . Theorem 4 (Dominance over block schedules). Under the assumptions of Theorem 1, let νM be the output law of a chain that starts from q and applies a fixed schedule of these blocks, using M candidates including initialization. Allow i-SIR as the first block and in at most one later block. Then Df (HM ∥p) ≤ Df (νM ∥p) for every convex generator f . The theorem orders the marginal output laws themselves, which goes beyond the worst-case convergence rates of Yang & Liu (2023). The schedule and initialization restrictions are discussed after the proof. We compare blocks by the probabilities they assign to recorded-weight levels. We first compare one k-proposal block with k consecutive MH updates, then replace blocks within the schedule. The order of replacement matters because i-SIR need not preserve the decreasing density ratios used in the comparison. For iid proposal weights Ri , put 

 1 ψk (t) = kZ E . t + R1 + · · · + Rk−1 For y ̸= y ′ , conditioning on a tagged proposal and summing over its k possible positions gives Ak (y, y ′ ) = p(y ′ )ψk (ρ(y) ∨ ρ(y ′ )),

Pk+1 (y, y ′ ) = p(y ′ )ψk (ρ(y) + ρ(y ′ )). (51) P k−1 ′ ′ For the first identity, selection followed by acceptance contributes P ρ(y )/[ρ(y) ∨ ρ(y ) + i=1 Ri ]. For the second, selection contributes ρ(y ′ )/[ρ(y) + ρ(y ′ ) + i Ri ]. Both kernels are p-reversible. Ordinary SIR satisfies Sk (y)/p(y) = ψk (ρ(y)), a nonincreasing function of the weight. Kernels ordered by weight. For laws A, B on the weight space, write A ⪯st B if EA g ≤ EB g for every nondecreasing function g. When A, B are response laws, this notation compares their induced weight laws, meaning EY ∼A g(ρ(Y )) ≤ EY ∼B g(ρ(Y )) for every such g. Aggregate equal weights into r1 < · · · < rd , with proposal masses Qi and target masses Πi = ri Qi /Z. All blocks preserve the conditional response law within each level, so the reduction (20) applies. Let C be the set of laws whose density with respect to Π is nonincreasing in the level. If B ∈ C is positive and bi = Bi /Πi , independence MH with proposal B and target Π has off-diagonal entries KB (i, j) = Πj min{bi , bj } = Πj bmax{i,j} . Let Fl = i≤l Πi , and let El be the kernel that redraws a state in the first l levels from the target conditioned on those levels and leaves higher levels fixed. Then P

KB =

d−1 X

Fl (bl − bl+1 )El + bd Ed .

(52)

l=1

P The coefficients are nonnegative and sum to i Πi bi = 1. Telescoping verifies the off-diagonal entries. Each El preserves stochastic order and maps decreasing functions to decreasing functions. Consequently KB is stochastically monotone and, by reversibility, preserves C. Moreover Ei Ej = Emax{i,j} , so products of these kernels again have this form. The first row of KB is B. Every mixture of the El is determined by its first row, because its off-diagonal ratio at (i, j) is the first row’s density at max{i, j}. It follows that KB1 KB2 = KB1 KB2 , 30

K k = KHk .

(53)

These identities also follow from the exact transition formula of Smith & Tierney (1996). Equation (51) identifies Ak = KSk . Lemma 9 (Monotone-proposal comparison). If B, B ′ ∈ C and B ⪯st B ′ , then νKB ⪯st νKB ′ for every ν ∈ C. Proof. For a reversible kernel L and gi = νi /Πi , net flow across a cut satisfies X (νL)({k, . . . , d}) − ν({k, . . . , d}) = Πi L(i, j)(gi − gj ). i<k≤j

Using the max-type form, the difference between the two kernels is X X (Bj′ − Bj )cj , cj = Πi (gi − gj ). j≥k

i<k

Because g is nonincreasing, cj ≥ 0 and cj is nondecreasing in j. Writing Tj = P summation by parts gives ck Tk + j>k (cj − cj−1 )Tj ≥ 0.

′ l≥j (Bl −Bl ) ≥ 0,

P

One-block comparison. The coupling in the proof of Theorem 1 gives Sk ⪯st Hk , and both laws lie in C. Lemma 9 and (53) therefore imply νAk ⪯st νK k for ν ∈ C. Also Pk+1 (i, j) ≤ Ak (i, j) off the diagonal, since ψk is decreasing. The reversible flow identity then yields νPk+1 ⪯st νAk ⪯st νK k ,

ν ∈ C.

(54)

Proof of Theorem 4. The proposal lies in C, as does an initial i-SIR output qPk+1 = Sk+1 . Multipletry kernels preserve this class. If an i-SIR block occurs later in the schedule, its input thus lies in C. Replace it by the same number of MH updates using (54). Every subsequent block is multipletry and stochastically monotone, so this replacement can only increase the final output weight in stochastic order. If the first block is i-SIR, replace it using Sk+1 ⪯st Hk+1 . The remaining suffix is now monotone. Finally replace each multiple-try block by single-proposal MH updates, from left to right. The input at each replacement remains in C, and the suffix preserves the comparison. Thus νM ⪯st HM in weight. Since HM /p is nonincreasing in weight, the supporting-line argument (22) proves the divergence inequality, strictly for strictly convex f whenever the output laws differ. B.2

E XACT MINIMAX TOTAL VARIATION

Selecting one of M iid proposals to approximate a target is also studied as approximate rejection sampling (Block & Polyanskiy, 2023). Here a uniform bound on the target-to-proposal density ratio gives an exact minimax TV value. Competing selectors may know the entire target and proposal, so the lower bound isolates the limitation imposed by candidate coverage. MH reaches this smallest achievable worst-case error using only the proposed responses and their weights. For ε ∈ (0, 1], let Cε be the class of positive q, ρ on arbitrary common finite supports with p = qρ/Z and κ := Z/ maxy ρ(y) ≥ ε. Let Afull M contain all randomized rules that, given the instance (q, ρ) and M iid q candidates, return one of those candidates. Write νA;q,ρ for the output law of such a rule. Proposition 4 (Exact minimax total variation). For every integer M ≥ 1 and ε ∈ (0, 1], inf

sup ∥νA;q,ρ − p∥TV =

A∈Afull M (q,ρ)∈Cε

sup ∥HM − p∥TV = (1 − ε)M .

(55)

(q,ρ)∈Cε

Thus proposal-initialized MH attains the minimax value without knowing ε, Z, or maxy ρ(y). The same conclusions hold when the instance class is restricted to products of two equally weighted specialists on two-token trees. Proof. Pointwise, q ≥ κp, so the initial TV error satisfies X ∥q − p∥TV = 1 − min{q(y), p(y)} ≤ 1 − κ. y

31

By Proposition 2, the remaining M − 1 updates contract this error: ∥HM − p∥TV ≤ (1 − κ)M −1 ∥q − p∥TV ≤ (1 − κ)M ≤ (1 − ε)M . For M = 1, only the initial-distance bound is needed. When ε = 1, p = q and MH is exact at every budget. For a matching lower bound when ε < 1, take a set A with q(A) = ε and weights 1 on A and c ∈ (0, 1) on its complement. Then κ = Z = ε + (1 − ε)c ≥ ε. By Lemma 7, every candidate selector satisfies ε ∥νA;q,ρ − p∥TV ≥ p(A) − νA;q,ρ (A) ≥ − 1 + (1 − ε)M . ε + (1 − ε)c As c ↓ 0, the target mass of A tends to 1, but the candidate pool misses A with probability (1 − ε)M . This proves the lower bound uniformly over selection rules. Every instance with c > 0 has positive weights. The limit is used only to approach the supremum. To realize the family within policy composition, let the first token be j ∈ {hi, lo} and the second be a binary label. Both specialists choose hi with probability ε. After hi, both label p distributions are uniform. After lo, use (b, 1 − b) and (1 − b, b) with b ∈ (0, 1/2) chosen so that 2 b(1 − b) = c. The root normalizer is 1, the local label proposal is uniform in both branches, and the recorded weight is 1 after hi and c after lo. Thus A = {j = hi} has the required law on a shared four-response support. The same coverage obstruction prevents a uniform bound on the forward KL in the objective gap. Every selector puts mass at least u = (1 − ε)M on Ac , whereas vc = p(Ac ) → 0. Binary data processing and the entropy bound give KL(νA;q,ρ ∥p) ≥ u log(1/vc ) − log 2 −→ ∞. Consequently, for ε < 1, no finite candidate budget gives a uniform forward-KL bound over Cε , even with full target knowledge. B.3

T HE ERROR EXPONENT WITH RECORDED - CANDIDATE INFORMATION

Theorem 2 shows that MH attains the exponent 4M whenever the disagreement coefficient D is nonconstant. We now ask whether another selector can improve this exponent uniformly when it knows the proposal and sees the sampled responses and their recorded weights. The following construction hides the weights of unobserved responses. Averaging over the hidden instances restricts every selector to a low-degree polynomial, from which a finite-difference argument gives the lower bound. Fix M ≥ 1 and put L = 4M . Let q be uniform on responses (j, s) ∈ {1, . . . , L} × {−1, 1}. For a hidden subset A ⊆ {1, . . . , L} and δ ̸= 0, define  1, j ∈ A, b = sech δ, ρA,δ (j, s) = pA,δ = qρA,δ /ZA,δ . b, j ∈ / A, A selector A returns one of M iid q candidates. It may use their full identities, their raw recorded weights, the complete proposal law q, and independent randomness. Its rule may depend on M , δ, and the construction, but must be the same for every hidden subset A. It receives no ZA,δ , unobserved weights, extra samples, or off-candidate model queries. Let νA,A,δ be its output law, and let AM denote these rules. Proposition 5 (Optimal worst-case exponent for recorded-candidate selectors). With cM = M !/[4(4M )M ], 2c2M (1 − b)2M ≤ inf sup KL(νA,A,δ ∥pA,δ ) ≤ sup KL(HM,A,δ ∥pA,δ ) ≤ A∈AM

A

A

(1 − b)2M . 4b

(56)

For each fixed M , the family is realized by two equally weighted nearby policies on a fixed two-token tree. Since 1 − b = δ 2 /2 + O(δ 4 ), the minimax error is ΘM (|δ|4M ) as δ → 0. 32

Proof. Both specialists sample j uniformly. After j ∈ A, both sample s uniformly. After j ∈ / A, their sign probabilities are eδs e−δs , π2,δ (s | j) = . 2 cosh δ 2 cosh δ Their local sign product is uniform, with normalizer b outside A and 1 inside A. The root normalizer is 1. These policies are fixed bounded perturbations of the common uniform policy, as in Theorem 2. The support and horizon do not change with δ. They are also exact optima for reference q and rewards Ri = β log(πi,δ /q). π1,δ (s | j) =

A polynomial restriction on every selector. Write BA = {(j, s) : j ∈ A} and average the selector’s output mass on this set over all subsets of size k:  −1 X L mA (k) = νA,A,δ (BA ). k |A|=k

Condition on the complete candidate tuple, and suppose it contains d ≤ M distinct first-token IDs. A particular high/low labeling of those IDs, with a high labels, occurs under a uniformly chosen subset A of size k with probability
L−d (k)a (L − k)d−a k−a , (v)a = v(v − 1) · · · (v − a + 1), (v)0 = 1.
= L (L)d k This labeling probability is a polynomial in k of degree at most d, valid at every integer 0 ≤ k ≤ L. The candidate tuple itself has law q ⊗M , independently of A. Once the tuple is fixed, the selector learns about A only through the observed labels. Its conditional probability of selecting a high weight therefore depends on the tuple and labels, but not otherwise on A. Averaging this selection probability against the labeling probabilities makes mA (k) a polynomial of degree at most M . Since mA (0) = 0, we can write mA (k) = tP (t) with t = k/L and deg P ≤ M − 1. The same polynomial must describe the common selector across all hidden instances. Its coefficients may depend on the rule, M , and δ, but not on the hidden subset or its size. The target mass depends only on k: pA,δ (BA ) = t g(t),

g(t) =

1 . b + (1 − b)t

Taking the absolute difference on BA and averaging over subsets gives max ∥νA,A,δ − pA,δ ∥TV ≥ t |P (t) − g(t)|.

|A|=k

A uniform sampling guarantee would therefore require a polynomial of degree at most M − 1 to approximate this rational function at every admissible t = k/L. A finite-difference lower bound. Use the M + 1 grid points tj = 1/4 + j/(2M ), corresponding to integer subset sizes kj = M + 2j. With spacing h = 1/(2M ), the M th forward difference of P vanishes. Repeated application of the fundamental theorem of calculus gives Z ∆M g(1/4) = g (M ) (1/4 + u1 + · · · + uM ) du1 · · · duM . h [0,h]M

The derivative g (M ) (t) =

(−1)M M !(1 − b)M [b + (1 − b)t]M +1

has constant sign and magnitude at least M !(1 − b)M on [0, 1]. Consequently, M M hM M !(1 − b)M ≤ ∆M max |P (tj ) − g(tj )|. h g(1/4) = ∆h (P − g)(1/4) ≤ 2 0≤j≤M

Because tj ≥ 1/4, some subset A has TV error at least cM (1 − b)M . Pinsker’s inequality gives the lower KL bound in (56). The argument applies to every allowed rule, including one chosen separately for each δ. 33

Matching MH order.

Let t = |A|/L. Direct calculation gives χ2 (q∥pA,δ ) =

t(1 − t)(1 − b)2 (1 − b)2 ≤ . b 4b

The minorization constant is at least b. Applying the chi-square contraction in (36) over M − 1 updates therefore yields KL(HM,A,δ ∥pA,δ ) ≤ χ2 (HM,A,δ ∥pA,δ ) ≤

(1 − b)2M . 4b

MH belongs to AM , which completes the bounds in (56). The supremum over hidden subsets in (56) makes the optimality of MH’s error exponent a worstcase guarantee. The lower bound need not hold for every fixed pair of policies. The information restriction matters because knowing Z would reveal t = |A|/L. A selector could then use different coefficients at different subset sizes, invalidating the polynomial restriction. To see the effect, suppose b ≥ 1/2 and t is known. Two candidates then suffice for exact sampling: on a mixed-weight pair, select the high candidate with probability 1 + (1 − b)t , 2(b + (1 − b)t) and on equal-weight pairs select uniformly. A direct calculation shows that the resulting high-weight mass is t/(b + (1 − b)t), the target value. Calibrated weights p(Y )/q(Y ) together with raw ρ(Y ) also reveal Z and are excluded from AM . Exponent optimality leaves room for better leading constants and better performance on particular instances. For example, take proposal masses 1/2, 1/2 on two weight classes with weights 1/2, 1. With two candidates, the high-weight class has target mass 2/3, MH mass 5/8, and mass 13/20 under selection proportional to squared weights. The latter is strictly closer to the target in both KL directions and TV. Theorem 1 compares MH with ordinary SIR. Bias-reduced selectors such as those studied by Skare et al. (2003) lie outside that comparison. B.4

A DMISSIBILITY AMONG WEIGHT- ONLY SELECTORS

Fix M ≥ 1. Let WM contain rules that return one of M iid candidates using only their ordered recorded weights in (0, 1]M and independent randomness. The rule is common to all instances: it receives neither q, Z, unobserved weights, nor candidate identities. These rules preserve q(· | ρ = r), so their response divergences equal their weight-law divergences by (20). Equality of selectors below means equality of their marginal output laws. Theorem 5 (Rigidity of the coverage rate). If A ∈ WM and a constant L < ∞ satisfy ∥νA − p∥TV ≤ L(1 − Z/ρmax )M on every finite positive instance with ρ ≤ 1, then νA = HM on every such instance. In particular, MH is the unique weight-only selector attaining the minimax TV value in Proposition 4 at every overlap level simultaneously. Proof. For a weight multiset, average the rule over its orderings and write Φi (k) for its probability of selecting weight ri , where k records the multiplicities. We show that these probabilities equal those of priority selection by induction on the number n of distinct weights in the multiset. The case n = 1 is immediate. Fix r1 < · · · < rn and assume agreement on Pevery multiset with fewer values. Give the lower weights proposal masses sαi , with αi > 0, i<n αi = 1, and give rn mass 1 − s. Then 1 − Z/rn ≤ s. The assumed bound and the MH bound in Proposition 4 imply ∥νA − HM ∥TV ≤ (L + 1)sM . By induction, a difference can arise only on multisets containing all n values. If any such multiset has a nonzero difference, let k0 be the smallest number of nonmaximal candidates among them. 34

Since the maximum occurs, k0 ≤ M − 1. For some selected level i, the output-mass difference has leading term Q k X M ! j<n αj j   k0 s Φi (k) − ΦMH (k) . i k1 ! · · · kn−1 !(M − k0 )! k1 +···+kn−1 =k0 kj ≥1

Distinct multisets give distinct monomials, so this is a nonzero homogeneous polynomial. It cannot vanish on the entire positive simplex: homogeneity would then make it vanish on the open positive orthant, and hence identically. Thus it is nonzero for some positive α summing to 1. The difference is then of order sk0 , contradicting the O(sM ) bound. This proves the induction and equality on every instance. For the final claim, a fixed selector attaining the minimax value at every level satisfies the pointwise bound with L = 1 by taking the level to be Z/ρmax . At overlap 1, all weights are equal. Corollary 1 (Weight-only admissibility). For TV or either direction of KL or chi-square divergence, if A ∈ WM has divergence no larger than MH’s on every instance, then νA = HM everywhere. Thus any weight-only selector that improves on MH on one instance must be worse on another. Proof. For TV, apply Theorem 5. For the other divergences, use the same induction and proposalmass rays. MH has coordinate errors O(sM ). Each nonmaximal target mass is of order s, and its MH mass is also of order s (for M = 1, both statements follow directly from H1 = q). Thus both chi-square divergences, and hence both KL divergences, are O(s2M −1 ). Domination and Pinsker’s inequality or the chi-square bound on TV imply ∥νA − p∥TV = O(sM −1/2 ). This again excludes any leading difference of order sk0 with k0 ≤ M − 1, completing the induction. Admissibility leaves room for better worst-case constants on restricted families, but any weight-only rule that improves on MH somewhere must be worse than MH on another instance. The proof shows this by letting the proposal mass on the largest weight approach 1. These results establish neither uniqueness at a single overlap level nor admissibility for every convex divergence. Note that with q and candidate identities known, a selector can detect when the pool covers the full support and improve on MH without losses elsewhere. For example, let M = 3, q = (1/2, 1/2), and ρ = (1/2, 1). The high-weight target mass is 2/3, whereas MH’s is 21/32. On pools containing both states, priority selection returns the high weight with probability 7/12 or 5/6, depending on the multiplicities. Increasing this probability by 1/72 is valid in both cases. These pools have probability 3/4, so the modified output has high-weight mass 21/32 + (3/4)(1/72) = 2/3 and is exact. A universal q-aware rule can make this change only when the known proposal and fullcoverage pool identify this instance, and otherwise use MH. It is therefore no worse on any instance and better on this one. B.5

A BARRIER TO CERTIFYING THE REMAINING ERROR

Proposition 1 certifies improvement over the proposal. Certifying a small remaining distance to the target is harder because unobserved responses can carry substantial target mass. Below, a rolloutonly certifier is a randomized function, common to all instances, of N iid proposal responses and their recorded weights. It uses no other instance information and makes no off-candidate weight queries. Theorem 6 (Rollout-only certification barrier). Fix M, N ≥ 1 and α ∈ (0, 1/2). Suppose a rolloutonly certifier U ∈ [0, 1] satisfies Pr{∥HM − p∥TV ≤ U } ≥ 1 − α on every positive finite-support instance with ρ ≤ 1. On any such instance, for every s ∈ (0, 1), s Pr{U ≥ vs } ≥ (1 − s)N − α, vs = − 1 + (1 − s)M . (57) s + (1 − s)Z In particular, if N ≤ 1/(2Z),   1 M 1 Pr U ≥ − ≥ − α. 2 2N 2 The bound applies even to constant-weight instances, where HM = p exactly. 35

Proof. Adjoin new responses in a set A with proposal mass s and weight 1. On Ac , keep the original weights and conditional proposal law. The new instance has target mass p′ (A) = s/[s + (1 − s)Z]. ′ ′ Candidate coverage gives HM (A) ≤ 1 − (1 − s)M , hence ∥HM − p′ ∥TV ≥ vs . With probability N e = (1 − s) , the certification pool misses A. Conditional on this event, its responses and weights have exactly the original pool law. Validity on the new instance therefore implies e Pr{U < vs } ≤ α,

Pr{U ≥ vs } ≥ 1 − α/e ≥ e − α

when e > α. If e ≤ α, the claimed lower bound is automatic. For s = 1/(2N ), Bernoulli’s inequality gives e ≥ 1/2 and 1 − (1 − s)M ≤ M/(2N ). If Z ≤ 1/(2N ) = s, then p′ (A) ≥ 1/2, proving the final bound. For example, with Z = 0.01, N = 50, M = 17, and α = 0.05, a valid upper certificate must be at least 0.33 with probability at least 0.45, even when the actual remaining TV is 0. By Pinsker’s inequality, an upper certificate for either KL direction obeys the same probability bound with threshold 2 max{vs , 0}2 in place of vs . Realization with known proposal and support. The zero-error obstruction also holds for some instances when the certifier knows q and the full response support. Use two-token responses (j, b), with q(j = hi) = s, q(j = lo) = 1 − s, and a uniform binary second token. In the first instance, let both branches have recorded weight c ∈ (0, 1). In the second, change only the high branch’s weight to 1. Both are products of two equally weighted specialists: use the same root law, opposite Bernoulli conditionals with affinity c on a low-weight branch, and matching uniform conditionals on a weight-1 branch. Both instances have the same q and support. On the event that the certification pool misses the high branch, every observed response and weight is the same in both instances. Validity on the second instance therefore forces Pr{U ≥ vs } ≥ (1 − s)N − α on the first, where HM = p = q and Z = c. Taking s = 1/(2N ) ≥ c gives the same zero-error bound. Knowledge of the complete weight map would distinguish the instances and lies outside the claim. B.6

C ONTINUATION - GUIDED PROPOSALS

The local decoder omits the continuation mass Fw,t in (15) when choosing each token. To incorporate an estimate of this quantity, we introduce a fixed positive function Fb on supported prefixes, with Fb = 1 at complete responses. This function, called a twist, is meant to approximate the continuation mass, so that Fb(ht v) ≈ Fw,t (ht , v). Suppressing x, w, define g(v | h)Fb(hv) b q F (v | h) = P , b u g(u | h)F (hu) P g(v | h)Fb(hv) b z F (h) = v , Fb(h)

(58) ρF (y) = b

Y

z F (ht ). b

t

These are the usual twist-induced proposal and potentials (Guarniero et al., 2017; Zhao et al., 2024). The twist changes candidate generation, so the finite-budget comparison must use the same twisted proposal for both selectors. Lemma 10 (Twisted local-normalizer identity). For every such twist, b b pew (y) = Fb(x)q F (y)ρF (y),

q F ρF b

p=

b

EqFb ρFb

.

(59)

Consequently, Theorems 1 and 4 and Proposition 1 apply with the twisted proposal and weights. Proof. Along a response, the product of the factors in (58) telescopes: Y Fb(ht+1 ) pew (y) b b q F (y)ρF (y) = g(yt | ht ) = . Fb(ht ) Fb(x) t b The terminal twist equals 1. Summing over responses gives EqFb ρF = Zw /Fb(x). The cited finitebudget results use only positivity and the normalized importance identity, which have now been verified.

36

The certificate formed from twisted weights bounds improvement over q F , not over the original q. A poor twist can make the twisted proposal farther from the target than q, even though MH still corrects it toward the target. b

B.7

A PPROXIMATE SPECIALISTS

Fix the prompt, weights, positive reference, and β > 0. The supplied policies remain πi , while πi∗ ∗ are the exact optima of (5). Write p = pbw , p∗ = πw , and define the log residuals and specialist regrets X bi = log(πi /πi∗ ), b̄ = wi bi , εi = βKL(πi ∥πi∗ ). i

The product formula immediately gives p=

p∗ eb̄ , Ep∗ eb̄

KL(µ∥p∗ ) = KL(µ∥p) + Eµ b̄ − log Ep∗ eb̄ .

(60)

All laws are on the common finite support, and each active policy is positive there. For an output ext ext ∗ (µ) its external regret. (p ) − Jw,x law µ, we call βKL(µ∥p∗ ) = Jw,x B.7.1

S TABILITY UNDER COVERAGE

Proposition 6 (Coverage controls target mismatch). With ci = maxy p(y)/πi (y), KL(p∥p∗ ) ≤

X

wi ci KL(πi ∥πi∗ ) =

i

1X wi ci εi . β i

No bounded-residual assumption is required. Proof. Let ϑ(u) = e−u − 1 + u, a nonnegative convex function. Using p∗ = pe−b̄ /Ep e−b̄ and log v ≤ v − 1 gives KL(p∥p∗ ) = Ep b̄ + log Ep e−b̄ ≤ Ep ϑ(b̄) X X ≤ wi Ep ϑ(bi ) ≤ wi ci Eπi ϑ(bi ). i

i

The last inequality uses p ≤ ci πi and ϑ ≥ 0. Since Eπi e−bi = 1, Eπi ϑ(bi ) = Eπi bi = KL(πi ∥πi∗ ). The coverage constants depend on the supplied policies, but because they are maxima over the entire support, the largest ratios in a finite rollout sample do not certify them. The bound controls the mismatch between the two targets. For a finite-budget output µ, the exact decomposition is KL(µ∥p∗ ) = KL(µ∥p) + KL(p∥p∗ ) + (Eµ − Ep )b̄.

(61)

Thus the two KL errors cannot simply be added, because the residual shift also matters. Appendix B.7.3 shows that this shift can reverse the effect of correction. B.7.2

I NSUFFICIENCY OF SPECIALIST REGRET ALONE

Theorem 7 (No uniform regret-only guarantee). Fix β > 0, a positive reference on three responses, and weights (1/2, 1/2). For every ε > 0, every composition rule that uses only the supplied policies, weights, reference, and β has unbounded external regret over reward tuples and supplied policies satisfying maxi εi ≤ ε. This includes randomized rules and rules using any number of suppliedpolicy rollouts, even if given the common regret upper bound ε. Proof. For 0 < η ≤ 1/10, set s =

p

1 − η − η 3 and supply

π1 = (s2 , η 3 , η),

π2 = (η 3 , s2 , η). 37

Consider two reward tuples. In the first, the exact optima equal the supplied policies. In the second, they are π1∗ = (s2 , η, η 3 ), π2∗ = (η, s2 , η 3 ). For either tuple, rewards Ri = β log(πi∗ /πref ) realize the specified optima with the same reference and β. The supplied-policy regrets are 0 in the first case and εi = 2β(η − η 3 ) log(1/η) −→ 0 in the second. The two scalarized optima are respectively √ √ (s η, s η, 1) (s, s, η 5/2 ) P = , Q= . √ 1 + 2s η 2s + η 5/2 All observable inputs to the rule are identical, so it has the same output law µ in the two cases. Let P Aη = y P (y)5/6 Q(y)1/6 and let Rη = P 5/6 Q1/6 /Aη . Nonnegativity of KL implies max{KL(µ∥P ), KL(µ∥Q)} ≥ 56 KL(µ∥P ) + 61 KL(µ∥Q) = KL(µ∥Rη ) − log Aη ≥ − log Aη . √

The first two entries of P are at most η. The third entry of Q is at most η 5/2 since 2s ≥ 1. Bounding the remaining probabilities by 1 gives Aη ≤ 3η 5/12 , and hence worst-case external regret at least   5 β log(1/η) − log 3 −→ ∞. 12 Both reward tuples satisfy the stated regret upper bound for all sufficiently small η, proving the claim. For the product rule itself, substitution gives KL(P ∥Q) = 52 log(1/η) + log 2 + o(1). Composition concentrates on a response that has small probability under each specialist, so each specialist’s approximation error on that response has little effect on its individual regret. The reward ranges grow in this construction. The theorem does not impose a uniform reward-range or probability-floor constraint. The coverage condition of Proposition 6 prevents this amplification. B.7.3

P OSSIBLE DETERIORATION OF THE EXTERNAL OBJECTIVE

Gains in the consensus and external objectives can have opposite signs at every candidate budget, even when approximation leaves the local decoder unchanged. Consider binary responses of length T ≥ 2, with first token A or B chosen uniformly by both exact specialists. At every later position in branch A, the two specialists’ probabilities for token 1 are a and 1 − a, respectively. In branch B they are a1 and 1 − a1 , where 0 < a < a1 ≤ 1/2. Use weights (1/2, 1/2). The supplied policies swap the assignments of a and a1 between branches, keeping root probabilities unchanged. Rewards Ri = β log(πi∗ /πref ) make the original pair exact specialists under any positive reference. Set p zA = 2 a(1 − a),

p zB = 2 a1 (1 − a1 ),

x = (T − 1) log(zB /zA ) > 0,

σ(x) =

1 . 1 + e−x

Both local decoders are uniform over all responses. Their recorded weights, however, are swapped between branches. Both product targets are uniform conditional on the first token, with p(A) = σ(x) and p∗ (A) = σ(−x). Consequently, KL(q∥p∗ ) = log cosh(x/2),

KL(p∥p∗ ) = x tanh(x/2).

MH using the supplied weights has branch transitions K(A, B) = e−x /2 and K(B, A) = 1/2. Solving this two-state recursion gives HM (A) = σ(x) + (1/2 − σ(x))λM −1 ,

λ = (1 − e−x )/2.

This increases strictly with M , from 1/2 toward σ(x). The binary KL to σ(−x) < 1/2 is strictly increasing for branch mass at least 1/2, so every additional candidate increases external regret βKL(HM ∥p∗ ), while consensus KL decreases to 0. The certificate is nevertheless positive. For 38

two candidates, equal-branch pools have G2 = 0, and mixed pools, which occur with probability 1/2, have G2 = log cosh(x/2). Thus EG2 = 12 log cosh(x/2) > 0. The individual regrets are εi =

β(T − 1) [kl(a1 , a) + kl(a, a1 )], 2

where kl denotes binary KL. The same supplied policies could instead be exact for their own implied rewards, giving positive external gains from the identical rollouts. Thus supplied policies and recorded weights alone cannot determine whether correction improves an unspecified external objective.

C

E NUMERABLE RESULTS AND PROTOCOLS

We report deterministic calculations of response-law errors and a separate Monte Carlo comparison of matched-budget samplers. The latter estimates total variation after grouping responses into recorded-weight bins (Appendix C.4). These estimates are distinct from the exact full-response calculations below. C.1

E XACT COMPUTATION IN WEIGHT SPACE

The deterministic calculations below use the classical weight-space reduction for the independence sampler (Smith & Tierney, 1996; Wang, 2022). Let µn = qK n = Hn+1 . Here n counts MH updates after proposal initialization, giving a total candidate budget of M = n + 1. The reduction works because, conditional on an exact weight ρ(y) = r, every iterate retains the response law q(· | ρ = r). The target and ordinary SIR share this conditional law (Appendix A.2). Thus response probabilities within each weight level remain in the same proportions as sampling proceeds. Only the total probability mass assigned to that level changes. We can therefore describe each iterate by a function fn such that µn (y) = q(y)fn (ρ(y)),

f0 ≡ 1.

A recursion on the weights. Write Q for the law of R = ρ(Y ) when Y ∼ q. From a response of weight r, the probability of accepting a fresh proposal is a(r) = ER∼Q min{1, R/r}. An MH update retains mass when a proposal is rejected and transfers mass to accepted proposals. Substituting µn (y) = q(y)fn (ρ(y)) into this update and dividing by q(y) gives fn+1 (r) = fn (r)(1 − a(r)) + ER∼Q [fn (R) min{1, r/R}] .

(62)

The second term also accounts for proposals that reproduce the current response. For numerical evaluation, accumulate the rejection probability directly as 1 − a(r) = ER∼Q (1 − R/r)+ . This form avoids the loss of precision from subtracting an acceptance probability close to 1, because it sums only nonnegative contributions from weights below r. Divergence and objective. r,

Write ρ# µ for the law of ρ(Y ) when Y ∼ µ. At each attained weight

(ρ# µn )(r) = Q(r)fn (r),

(ρ# p)(r) =

Consequently, for any response with ρ(y) = r, µn (y) Zfn (r) (ρ# µn )(r) = = . p(y) r (ρ# p)(r) 39

rQ(r) . Z

Grouping the divergence sum by exact weight now gives (63)

Df (µn ∥p) = Df (ρ# µn ∥ρ# p).

This identity covers exact sequence-level KL and TV, even with tied weights. A single score mean or a histogram that merges different weights does not generally determine these divergences. To apply the reduction to another sampler, we would need the same conditional response law given ρ. We do not assume this property for SMC or replica exchange, so their objective evaluation requires separate justification. The consensus objective can also be evaluated from these scalar quantities. Substituting pew = qρ and µn = qfn (ρ) into (4) gives Jex (µn ) = Eµn [log ρ − log fn (ρ)],

Jex (q) = Eq log ρ,

Jex (p) = log Z.

(64)

For ordinary SIR, conditioning on a tagged candidate and using exchangeability gives the corresponding marginal ratio   SM (y) ρ(y) iid =ME , Rj ∼ Q, q(y) ρ(y) + R2 + · · · + RM with an empty sum when M = 1. This ratio depends only on ρ(y), so the same divergence and objective identities apply with the SIR ratio in place of fn . Empirical evaluation. Replacing Q by an empirical distribution evaluates the sampler under that empirical proposal. How well this approximates the population law depends on the estimated weight distribution, including its coverage of rare weights. Estimation error also enters the plug-in objective through log fn . Using independent samples for fitting and evaluation does not remove the resulting bias. The GSM8K study avoids fitting the scalar law by using the rollout-only improvement certificate (Appendix D.1). C.2

E XACT LAWS AND NEARBY- POLICY RATES

The enumerable study uses a vocabulary of 4 tokens and 3 autoregressive policies. At every prefix, each policy’s conditional probabilities are drawn independently from a symmetric Dirichlet distribution with concentration α. Each replication draws w ∼ Dirichlet(1, 1, 1). The base, peaky, and flat configurations use T = 6, with concentrations α = 0.5, 0.2, and 1.0, respectively. Short and long use α = 0.5 at T = 3 and T = 10, respectively. We use 20 replications per configuration, except for the long configuration (T = 10), which uses 10. With a uniform reference and rewards ∗ and each KL reduction Ri = log(πi /πref ), these policies are exact optima at β = 1, so pbw = πw equals a regularized-objective gain. For each instance, enumeration gives qw , pbw , and ρw on the complete response space. We verify pew = qw ρw and propagate the MH law deterministically. SIR’s marginal density ratio is evaluated by quadrature of the scalar identity in Appendix C.1, checked against direct candidate-pool enumeration on small supports. These calculations introduce no sampling or density-fitting error. Figure 2, left, plots the mean KL at candidate budgets M ∈ {1, 2, 3, 4, 6, 9, 13, 21, 33, 51} on logarithmic axes, omitting values at or below 10−12 . The MH calculation uses stable rejection accumulation as in Appendix C.1. Table 1 gives selected values and their variability across policy configurations. One update reduces mean KL by 85.9% in base, 70.0% in peaky, 95.0% in flat, 94.4% in short, and 77.6% in long. Nearby-policy illustration. The right panel of Figure 2 uses a separate fixed instance of Theorem 2: vocabulary size 3, horizon 3, and 2 equally weighted policies, giving 27 complete responses. The common policy has independent Dirichlet(1, 1, 1) conditionals at each prefix. Its two Gaussian logit-perturbation arrays are fixed while δ varies. We evaluate the local decoder and both selectors for M = 2 and M = 3 over 12 logarithmically spaced perturbation sizes from 0.01 to 1. We re-evaluate the fixed instance with 90-digit arithmetic to resolve the small MH divergences without floating-point cancellation, keeping the policies and perturbation sizes unchanged. MH uses its dense transition kernel, and SIR uses direct candidate-pool enumeration. The guide slopes show asymptotic orders rather than fitted rates. This experiment varies policy separation at fixed support, horizon, and budget, as the theorem requires. 40

Table 1: Exact KL(µn ∥b pw ) in nats after n MH updates, initialized from qw , with total candidate budget M = n + 1. Entries are means over 20 policy configurations (10 at T = 10); standard deviations appear beneath. MH updates n (budget M = n + 1) Configuration

α

T

Base

0.5

6

Peaky Flat Short Long

0.2 1.0 0.5

6 6 3

0.5 10

0

1

2

3

5

8

0.154

0.022

0.0055

±0.056

±0.015

±0.005

0.0018

0.0003

< 10−4

±0.002

±0.0004

0.603

0.181

0.084

0.048

0.021

±0.405

±0.181

±0.098

±0.061

±0.032

±0.018

0.034

0.0017

0.0002

< 10−4

< 10−4

< 10−4

±0.012

±0.0012

±0.0002

< 10−4

< 10−4

< 10−4

0.042

0.0024

0.0003

±0.034

±0.0038

±0.0006

0.0089

0.270

0.060

0.023

0.011

0.0032

0.0008

±0.125

±0.044

±0.020

±0.010

±0.0034

±0.0009

Greedy initialization. In Figure 4, MH starts from the response obtained by choosing the most probable local-product token at each step. This chain begins farther from the target than the proposal-initialized chain but converges to the same target, as Proposition 2 guarantees. After 8 updates, mean KL is below 0.012 in every configuration and below 10−4 in base, flat, and short. The comparison with ordinary SIR in Theorem 1 requires proposal initialization and does not cover this chain. C.3

R EWARD – DIVERGENCE VIEW

At T = 10 and equal weights, take a uniform reference and the synthetic rewards Ri = log(πi /πref ) introduced P at the start of this appendix. The scalarized reward is then the implicit checkpoint score rw = i wi log(πi /πref ). Varying the regularization strength in πλ ∝ πref exp(Rw /λ), λ > 0, traces the optimal reward–divergence trade-off at fixed reward weights. Its point at λ = 1 is the correction target. Figure 5 shows the trade-off and both MH trajectories. Both initializations approach the target, but expected reward itself need not increase: the greedy-initialized chain can lower expected reward while improving its regularized objective. C.4

M ATCHED - BUDGET SAMPLERS AND METRIC

Table 2 compares selection and structured-sampling rules at a budget of 9 full-sequence equivalents of conditional evaluations. For each primary instance, we use 8 independent batches of 106 complete algorithm runs per method. All entries, including MH and qw , use the same empirical metric. Exact controls are given separately below. The uncorrected proposal is shown at its natural one-rollout cost, since generating unused candidates would not change its law. Sampling-importance-resampling. Ordinary SIR draws M independent responses from qw and selects one with probability proportional to its recorded ρw weight (Owen, 2013). The primary comparison uses M = 9. Sequential Monte Carlo. Bootstrap SMC maintains M partial responses. At each step, every particle is extended by one token from the local product decoder, and its weight is multiplied by zw,t . Multinomial resampling draws particles in proportion to their weights and resets those weights to equal values. We resample either after every nonterminal step or whenever the effective P sample size (ESS) falls below half the particle count. For normalized weights aj , ESS = 1/ j a2j . The final response is selected using the remaining weights. Same-space replica exchange. Three replicas target distributions proportional to qw ρbw for b ∈ {1, 1/2, 0}. Each starts from an independent qw rollout. At budget M divisible by 3, we run M/3 − 1 sweeps. Each sweep applies an independence-MH update to every replica and then proposes 41

KL to target (nats)

10 0 base (® = 0:5) peaky (® = 0:2) flat (® = 1) short (T = 3) long (T = 10)

10 −3 10 −6 10 −9 10 −12

from greedy decode from qw 0

1 2 3 5 8 20 MH updates n (M = n + 1)

50

Figure 4: Exact KL of MH started from the greedy local-product decode, averaged within each configuration of Table 1. The budget M = n + 1 counts the greedy decode and n independent MH proposals. Faint lines repeat the proposal-initialized MH curves of Figure 2 for comparison. Values at or below 10−12 are omitted.

Reward gain (nats)

® = 0:2

® = 0:5

®=1

30 n=0

10

n=0

15 5 0

0

7

14

0

3

0

7

14

8.8

Reward gain (nats)

n=0

6

0

0

7

14

3.75

26 8.4

3.60

24 8.0 7.2

8.0

3.30

KL(¹k¼ref ) (nats) Optimal reward–divergence trade-off Target pb w (¸ = 1)

3.45

3.60

KL(¹k¼ref ) (nats) MH from qw Local decoder qw

3.45

1.60

1.68 KL(¹k¼ref ) (nats)

MH from greedy decode

Figure 5: Optimal reward–divergence trade-offs and MH trajectories at T = 10, with equal reward weights and a uniform reference. Columns vary the Dirichlet concentration; the bottom row enlarges the boxed region around the target. Reward is centered at its reference expectation, Eµ Rw − Eπref Rw . Curves average 10 policy draws; trajectory markers show initialization (n = 0) and 6 MH updates. adjacent swaps in increasing replica-index order. The swap acceptance ratio preserves the joint target. We return the b = 1 replica. At M = 9, 3 initial rollouts and 2 update sweeps cost 9 complete decodes. The swaps add no conditional evaluations. Length-space replica exchange. Following He et al. (2026), the intermediate targets are products of policy prefix probabilities. Replicas have lengths 0, 2, . . . , T . An adjacent exchange truncates the longer prefix and extends the shorter one with a fresh 2-token chunk. Its acceptance ratio uses the local normalizer products on the new and removed chunks. Initialization costs 0 + 2 + · · · + T token evaluations. Each sweep pair visits nonoverlapping even edges and then odd edges, and the longest response is returned. At T = 6, 7 pairs cost 12 + 7 × 6 = 54 = 9T evaluations. At T = 10, 6 pairs 42

cost 30 + 6 × 10 = 90 = 9T . The implementation includes both initialization and extensions in the charged budget. Maximum-log-normalizer selection. The max-ℓρ,w -of-9 baseline returns the response with the largest ℓρ,w among 9 independent qw candidates. It selects on the correction weight, not on reward. In the base and long instances, it is farther from the target than qw , which shows that maximizing a correction weight need not approximate sampling from the target. The corrected samplers are matched by conditional-evaluation counts, although batching and implementation can still affect elapsed time. Binned total variation. Responses are sorted by ℓρ,w , with bin boundaries at cumulative targetprobability thresholds j/32, j = 1, . . . , 31. Discreteness means that bins need not have equal mass, and the saved ordering can split tied weights. Every method uses the same partition and exact target bin masses. TV on these bins lower-bounds full-response TV. The exact scalar-law equality in Appendix C.1 applies to weight level sets. Combining different weights into bins can lose information. The MH–SIR ordering nevertheless holds for these consecutive bins. To see this, let Ck be the union of the first k bins and put ak (r) = q(Ck | ρ = r). This function is nonincreasing, including when a bin boundary splits a tied level. Both selectors preserve the proposal conditional law within each level, so the stochastic ordering in Appendix A.2 gives SM (Ck ) = ESM ak ≥ EHM ak = HM (Ck ). The binned MH-to-target ratios are also nonincreasing: each is a target-weighted average of the decreasing pointwise ratio over a consecutive bin. The same supporting-line argument therefore proves the binned divergence ordering for every convex generator. This population statement does not imply the same ordering for individual Monte Carlo estimates. Exact controls and sampling variation. The exact rows of Table 2 give the binned and fullresponse TV of qw and MH on the same primary instances. The target row applies the empirical metric to independent draws from pbw under the same batch design. It describes sampling variation at this sample size. It is neither a universal significance threshold nor a bias correction to subtract from other entries. Sensitivity to instance and budget. At budget 9, the sensitivity sweep uses 10 policy seeds each for base and peaky and 3 for long, with 105 runs per batch for the additional instances. MH has lower binned TV than ordinary SIR on all 23 instances, and all stored pointwise 95% Monte Carlo intervals for their differences exclude 0. The comparison with structured samplers varies across instances. Against all structured comparators, MH has the smallest point estimate on 7 of 10 base, 7 of 10 peaky, and all 3 long instances. Adaptive SMC is 0.0145 TV below MH on one peaky instance, with interval [0.0128, 0.0163] for MH minus SMC. On one base instance, however, extending the evaluation to 106 runs per batch does not resolve the apparent same-space-exchange advantage. MH minus exchange is +0.0000223, with interval [−0.0003776, +0.0004221]. For each comparison, we subtract the empirical binned TV values at matching √ batch indices to obtain 8 differences db . The pointwise 95% Student-t interval is d¯± t7,0.975 sd / 8, where sd is the sample standard deviation of those differences and t7,0.975 ≃ 2.365. The methods use independent random streams. Budgets 18 and 36 were evaluated on the same primary instances. MH remains below ordinary SIR at both budgets. At budget 36, the MH and replica-exchange discrepancies are close to the exact-target sampling diagnostic, so the empirical metric provides little separation among them. Objective checks. Across 51 enumerable policy instances, direct regularized-objective increments were cross-checked against forward-KL differences and the scalar-weight calculation. Identity residuals are at floating-point precision. 43

Table 2: Matched-budget comparison in units of 10−3 TV. Sampled rows give the mean ± acrossbatch standard deviation of the binned TV over 8 batches of 106 runs. The corrected samplers use 9 full-sequence equivalents of conditional policy evaluations. The last sampled row draws from the target itself and shows the sampling variation of the estimate. Exact rows propagate each law deterministically. Each configuration uses the same policy instance across methods. Method Estimated binned TV qw (1 rollout) MH Ordinary SIR SMC, adaptive resampling SMC, resampling every step Same-space replica exchange Length-space replica exchange max-ℓρ,w -of-9 Target pbw (direct draws) Exact TV qw , binned qw , full response MH, binned MH, full response

Base

Peaky

Long

237.765 ± 0.509 2.506 ± 0.254 30.097 ± 0.662 30.064 ± 0.435 52.170 ± 0.214 14.634 ± 0.438 10.027 ± 0.607 472.451 ± 0.281 2.161 ± 0.292

515.610 ± 0.438 37.762 ± 0.234 86.999 ± 0.639 73.574 ± 0.481 106.350 ± 0.501 109.666 ± 0.441 116.224 ± 0.608 215.438 ± 0.708 1.524 ± 0.201

302.427 ± 0.483 7.596 ± 0.217 42.918 ± 0.450 43.051 ± 0.349 68.462 ± 0.512 33.324 ± 0.480 53.493 ± 0.530 412.216 ± 0.333 2.184 ± 0.249

237.719 237.773 1.354 1.355

515.909 516.016 37.619 37.678

302.413 302.615 7.455 7.456

Recorded runs. Each configuration, policy instance, budget, method, and batch uses an independent random stream. The archived outputs include seeds, bin maps, counts, charged costs, source snapshots, and aggregate tables. Nested 10,000-, 100,000-, and 1,000,000-sample prefixes share draws and are correlated. The values in Table 2 come from this matched-protocol run collection.

D

GSM8K EXPERIMENT

D.1

GSM8K CERTIFICATE EVALUATION

Models and data. The experiment composes 2 DPO adapters of google/gemma-4-E2B-it, trained for answer accuracy and brevity, respectively. Both use a DPO coefficient of 0.1 and a candidate pool of 4,000 distinct GSM8K training problems with 4 responses per problem. Brevity preferences rank responses by the continuous score −L/1024, where L counts generated tokens, including EOS but excluding the prompt and padding. DPO uses this ordering rather than the numeric magnitudes. The supplied checkpoints are fixed throughout evaluation. We report consensus improvement (λ = 1 in (7)), independently of the DPO training coefficient. The final cohort contains all 1,319 official GSM8K test problems. An exact-question comparison found no overlap with the specialist-training pool. The protocol, checkpoints, weights, and sampling settings were fixed before final generation. The dataset revision, original test bytes, and prompt manifest are archived under data/certificates/gsm8k. Sampling and candidate budgets. We evaluate accuracy weights w1 ∈ {0.25, 0.5, 0.75} and brevity weight 1 − w1 on the same prompt cohort. Generation uses temperature 1, the full vocabulary without top-k or nucleus truncation, and a 1,024-token cap. Reasoning is disabled by passing enable_thinking=False to the tokenizer’s chat template. Policy inference uses FP32, and normalization and probability accumulation use FP64. EOS contributes its probability and counts toward response length. Reaching the cap adds no forced terminal token. Empty, invalid, and capped responses remain in the evaluation. The prompt consists of the following text, followed by a blank line and the question: Solve the following problem. Show your solution and end with exactly one line of the form #### <numerical answer>. 44

For each prompt and weight, 4 replications each draw 2 independent groups of 17 fresh localproduct responses. This gives 8 groups per prompt and N = 10,552 groups per weight. The complete study uses 3 × 10,552 × 17 = 538,152 responses, with no fitting pool. Each group supplies all budgets M = 1, . . . , 17 through its prefixes. The first candidate initializes MH, and the remaining candidates are processed once in chronological order with independently generated acceptance uniforms. Content-derived seeds give each response its own sampling stream. The generation settings and code used for sampling are archived with the results. Replicated groups estimate the samplers’ expected behavior over fresh candidate pools. They are evaluation overhead, not the deployment budget. At each rollout budget M , both MH and ordinary SIR use M candidate rollouts per output, while the local-decoding baseline uses 1. We use no burn-in and exclude initialization from the acceptance rates. Simultaneous confidence bounds. For every group and budget, we compute GM in (10) from the first M original proposal weights, rather than the retained MH states. With equal numbers of groups per prompt, the pooled mean estimates the equally weighted average over the fixed test cohort. With clipping cap Γ = 10 nats and familywise error level α = 0.05, the lower confidence bound is   s N  1 X log(144/0.05)  (j) LM = max 0, min(GM , 10) − 10 .  N 2 · 10,552  j=1

We set L1 = 0 exactly. The common subtraction is 0.194279 nats. The factor 144 retains the original prespecified family of 3 tasks, 3 weights, and 16 nonzero update budgets. This protocol planned GSM8K, HH-RLHF, and Reddit summarization studies. We retain its correction for GSM8K, although only 48 of those comparisons are reported here. The final HH-RLHF study uses its own family of 48 comparisons (Appendix E.1). Each study therefore has a simultaneous 95% confidence statement within its reported family, not a joint 95% statement across the two studies. The bound assumes independent groups conditional on the fixed prompts and checkpoints. Group distributions may differ across prompts. The union bound does not require independence across nested budgets or composition weights. On the same confidence event, both MH and SIR have average consensus improvement at least LM over fresh proposal pools for these prompts. No additional comparison factor is needed for the two methods, because Proposition 1 lower-bounds both gains by the same expectation. This is not a confidence statement over a population of prompts or about the MH–SIR difference. Table 3 gives the certificate and acceptance endpoints. At M = 9, clipping affects 0.038%, 0.597%, and 0.265% of groups in increasing order of w1 . The solid curves in the top-left panel of Figure 3 estimate E[GM ], not the full consensus gain. Positive lower bounds establish improvement over local decoding without estimating either corrected sampler’s marginal output probabilities. Acceptance is a separate sampling diagnostic and does not measure remaining divergence from the target. Choice of a fitting-free endpoint. The scalar identities in Appendix C.1 also suggest estimating each sampler’s objective by fitting its output density ratio. Independent fitting does not remove nonlinear plug-in bias, and the resulting intervals require separate coverage validation. Controlled finite-state tests did not pass the prespecified bias and coverage thresholds, so fitted objective estimates do not enter this evaluation. Those tests and the earlier fitted estimates remain archived under results/llm-regularised-paired-validation and results/ gsm8k-draft-update-20260918, respectively. Separate specialist evaluation. A separate evaluation draws 4 responses per adapter on 1,000 validation problems. The accuracy adapter achieves 86.875% accuracy with a mean length of 390.77 tokens, compared with 85.425% and 250.95 tokens for the brevity adapter. Paired 95% prompt-bootstrap intervals from 2,000 draws are [132.68, 146.88] tokens saved and [0.325, 2.65] percentage points of accuracy lost. This evaluation was expanded after an initial 128-problem comparison. It uses BF16, top-p = 0.95, and top-k = 64 on a different prompt set. These measurements characterize the supplied specialists and are not task-performance results for the fullvocabulary FP32 composition study. They are archived in results/gsm8k-draft-update20260918/specialists.json. 45

Table 3: GSM8K certificate results, in nats. Means are unclipped; the simultaneous 95% lower bounds use certificates clipped at 10 nats, and the clipped columns give the percentage of groups whose certificate was clipped. Cumulative MH acceptance over the first n updates excludes initialization. w1

Mean GM

0.25 0.50 0.75

0.868 1.700 1.413

MH acceptance (%)

M =9

M = 17

Lower bound Clipped Mean GM

Lower bound Clipped n = 8

0.674 1.494 1.216

0.038 0.597 0.265

0.937 1.848 1.528

0.742 1.644 1.330

0.038 0.663 0.256

53.92 46.10 49.61

n = 16 50.53 41.14 45.09

Evaluation artifacts and replay. The completed certificate curves and clipping statistics are archived under results/certificates/gsm8k, together with per-step acceptance counts and per-prompt acceptance rates. Record hashes and frozen launch sources accompany the results. The statistical design is specified in experiments/certificates/PROTOCOL.md. Within the manuscript directory, figures/SOURCES.json records hashes of the unchanged plotting inputs. The script scripts/verify_figure_data.py checks the saved certificate arithmetic and acceptance aggregates. These files support local figure regeneration without model inference. Recomputing certificates from observations requires the original grouped proposal weights. Acceptance replay additionally requires the recorded uniforms. The full raw batches are external, checksum-addressed artifacts listed in the companion archive, rather than bundled in the manuscript export. The original analysis entry point also checks hashes of model and adapter files, so reproducing that command requires those assets to be restored. Checks of the saved aggregates and provenance therefore remain distinct from a full-record or checkpoint-level rerun. D.2

GSM8K OUTPUT- LEVEL REPLAY AND COST

The analysis reuses all 538,152 archived responses and verifies the 7,914 raw batch checksums, record identities, saved seeds and acceptance uniforms, the probability identity, and GSM8K answer extraction. The bootstrap resamples whole prompts, retaining all 8 groups of each resampled prompt, and uses common draws across methods, weights, and budgets (10,000 draws). We report descriptive pointwise 95% percentile intervals, not the simultaneous fixed-cohort certificate bounds of Appendix D.1. The local decoder returns the first proposal (proposal 0). MH replays the fresh proposals in generation order. SIR results are exact expectations conditional on each pool. Independently seeded sampled selections are also archived. Majority voting counts normalized valid answers, breaks ties by earliest appearance, returns the first response with the winning answer, and falls back to proposal 0 when all answers are invalid. Invalid candidates still count toward generation cost, and no selection rule uses the gold answer. Token costs include EOS tokens and all discarded candidates. Table 4 reports output-level results for each weight, and Table 5 reports the paired MH–SIR differences. Fresh-pool effective sample sizes and maximum normalized weights are recorded in poolconcentration.csv. The companion code provides separate CPU replay commands for the raw selections and for a compact cache. Serving cost. Table 6 compares local decoding with batched MH correction on one H200. Each timed batch contains one prompt and M candidates. Each weighting and budget uses 48 timed trials, comprising 16 prompts with 3 repetitions each. Both specialist policies run in FP32, and the measurements exclude model loading and warm-up. Relative to M = 1, mean latency increases by 16–20% at M = 3 and 29–35% at M = 9. These are latency measurements for this batch configuration, not throughput estimates. Total generated tokens include every candidate, including discarded responses. Full timing results for MH, SIR, and majority voting are archived under results/output-evaluation/gsm8k/profile. 46

Table 4: Output-level GSM8K results at each candidate budget. Length counts the tokens of the returned response; total tokens include all generated candidates. At M = 1, MH, SIR, and majority voting all return the local decoder’s single proposal. Brackets give pointwise 95% prompt-bootstrap intervals. M

Total tokens

Method

Accuracy (%)

95% CI

Length

95% CI

Accuracy weight w1 = 0.25 1 259.6 Local decoder (qw ) 2 519.8 MH SIR Majority vote 3 779.8 MH SIR Majority vote 5 1299.3 MH SIR Majority vote 9 2339.6 MH SIR Majority vote 17 4422.8 MH SIR Majority vote

88.50 89.16 89.13 88.98 89.26 89.30 90.14 89.48 89.48 90.52 89.45 89.58 90.84 89.68 89.64 91.24

[86.99, 89.93] [87.65, 90.58] [87.63, 90.54] [87.50, 90.40] [87.77, 90.68] [87.81, 90.71] [88.65, 91.57] [87.97, 90.88] [88.01, 90.87] [89.05, 91.94] [87.94, 90.87] [88.10, 90.98] [89.36, 92.26] [88.17, 91.08] [88.17, 91.04] [89.77, 92.66]

259.6 251.2 251.6 258.8 248.4 249.0 257.5 246.5 246.7 257.0 244.6 245.1 256.5 243.6 244.1 255.7

[254.1, 265.3] [246.2, 256.3] [246.6, 256.8] [253.4, 264.3] [243.7, 253.3] [244.2, 253.9] [252.2, 262.9] [241.9, 251.2] [242.2, 251.4] [251.7, 262.3] [240.1, 249.2] [240.6, 249.7] [251.4, 261.7] [239.2, 248.0] [239.7, 248.6] [250.7, 260.8]

Accuracy weight w1 = 0.5 1 291.6 Local decoder (qw ) 2 583.5 MH SIR Majority vote 3 874.0 MH SIR Majority vote 5 1456.7 MH SIR Majority vote 9 2624.2 MH SIR Majority vote 17 4955.8 MH SIR Majority vote

88.88 89.83 89.74 89.39 90.09 90.03 90.37 90.16 90.13 91.03 90.09 90.18 91.04 90.15 90.17 91.31

[87.40, 90.29] [88.36, 91.21] [88.28, 91.11] [87.93, 90.77] [88.65, 91.47] [88.58, 91.40] [88.89, 91.76] [88.70, 91.54] [88.69, 91.52] [89.59, 92.40] [88.61, 91.48] [88.72, 91.56] [89.58, 92.45] [88.68, 91.54] [88.70, 91.54] [89.84, 92.69]

291.6 277.5 277.9 289.5 272.3 272.8 288.5 268.2 268.7 287.8 265.4 266.1 287.4 263.5 263.9 286.6

[285.0, 298.5] [271.7, 283.5] [272.1, 283.9] [283.1, 295.9] [266.8, 277.9] [267.3, 278.4] [282.2, 294.9] [263.0, 273.5] [263.5, 274.0] [281.6, 294.1] [260.3, 270.5] [261.0, 271.2] [281.3, 293.7] [258.5, 268.6] [258.9, 268.9] [280.4, 292.8]

Accuracy weight w1 = 0.75 1 330.1 Local decoder (qw ) 2 661.8 MH SIR Majority vote 3 992.3 MH SIR Majority vote 5 1653.7 MH SIR Majority vote 9 2976.6 MH SIR Majority vote 17 5619.2 MH SIR Majority vote

89.16 89.92 89.85 89.73 90.16 90.11 90.58 90.15 90.24 91.06 90.47 90.35 91.22 90.29 90.42 91.48

[87.65, 90.53] [88.46, 91.28] [88.39, 91.22] [88.26, 91.08] [88.69, 91.54] [88.67, 91.48] [89.12, 91.94] [88.68, 91.55] [88.79, 91.61] [89.60, 92.42] [89.00, 91.83] [88.89, 91.70] [89.76, 92.60] [88.81, 91.66] [88.97, 91.78] [90.03, 92.85]

330.1 312.2 312.7 327.0 304.3 305.1 325.3 297.6 298.2 324.2 292.3 293.6 323.9 288.4 289.5 323.9

[322.2, 338.0] [305.1, 319.3] [305.6, 319.7] [319.5, 334.6] [297.7, 310.9] [298.5, 311.7] [318.0, 332.7] [291.4, 303.9] [292.0, 304.5] [317.0, 331.5] [286.4, 298.3] [287.6, 299.6] [316.8, 331.2] [282.7, 294.1] [283.8, 295.1] [316.7, 331.1]

47

Table 5: Paired MH-minus-SIR differences on identical fresh pools, with pointwise 95% promptbootstrap intervals. At M = 1 both methods return the first proposal, so both differences are 0. The difference in selected log ρ describes the selection mechanism and is not a KL improvement. Accuracy weight w1 0.25

M

0.5

0.75

MH − SIR accuracy (percentage points) 2 0.03 [−0.12, 0.17] 0.09 [−0.03, 0.21] 3 −0.04 [−0.20, 0.12] 0.06 [−0.08, 0.18] 5 0.00 [−0.19, 0.20] 0.03 [−0.12, 0.18] 9 −0.13 [−0.34, 0.08] −0.09 [−0.27, 0.08] 17 0.03 [−0.22, 0.28] −0.01 [−0.20, 0.17] MH − SIR selected log ρ 2 0.0594 [0.0524, 0.0662] 3 0.0853 [0.0767, 0.0938] 5 0.0802 [0.0681, 0.0923] 9 0.0883 [0.0753, 0.1018] 17 0.0826 [0.0675, 0.0979]

0.0513 [0.0445, 0.0581] 0.0782 [0.0692, 0.0870] 0.1084 [0.0972, 0.1198] 0.1155 [0.1013, 0.1296] 0.1019 [0.0850, 0.1190]

0.07 [−0.06, 0.20] 0.05 [−0.08, 0.18] −0.08 [−0.23, 0.07] 0.12 [−0.07, 0.30] −0.14 [−0.32, 0.04] 0.0570 [0.0507, 0.0634] 0.0723 [0.0635, 0.0810] 0.0858 [0.0746, 0.0971] 0.0981 [0.0843, 0.1116] 0.0961 [0.0801, 0.1123]

Table 6: Measured GSM8K serving cost on one H200. At M = 1, MH returns the local decoder’s single proposal. Total tokens count all generated candidates and are averaged over the timed trials. Peak allocated memory is the maximum over 48 trials in each stratum. w1

M

Mean latency (s)

p95 (s)

Total tokens

Peak allocated (GB)

0.25 0.25 0.25 0.5 0.5 0.5 0.75 0.75 0.75

1 3 9 1 3 9 1 3 9

17.47 20.25 22.53 21.11 25.30 27.99 21.45 25.10 28.90

26.11 29.54 33.33 31.76 39.23 39.65 30.34 37.12 46.37

248.7 746.0 2209.0 272.8 831.6 2442.0 305.0 898.4 2767.6

41.12 41.24 41.57 41.13 41.25 41.61 41.13 41.25 41.65

48

E

HH-RLHF EXPERIMENT

E.1

HH-RLHF CERTIFICATE EVALUATION

Models, data, and specialist check. We compose helpfulness- and harmlessness-specialized LoRA adapters of Gemma-4-E2B-it. Both were trained by DPO (β = 0.1, rank 16, 1 epoch, 10,000 preference pairs) on the same 4,000 deduplicated conversations from the Anthropic HH-RLHF training partition. Preferences were induced separately by the pinned Ray2333 GPT-2-large helpfulness and harmlessness reward models used by Rewards-in-Context (Yang et al., 2024), using their raw scalar logits. On a separate 500-prompt confirmation split, the helpfulness specialist’s mean helpfulness score exceeded the harmlessness specialist’s by 0.607 (95% CI [0.500, 0.713]). The harmlessness specialist’s mean harmlessness score exceeded the helpfulness specialist’s by 0.629 (95% CI [0.531, 0.728]). These reward-model scores are proxies for response quality and safety, not human judgments. The fixed certificate cohort contains 1,319 distinct, hash-selected conversations from the original test partition, with exact conversation overlap excluded from training. The chat template preserves alternating multi-turn roles and disables Gemma thinking. Generation uses temperature 1, the full vocabulary, FP32 policy inference, FP64 normalization and accumulation, and a 512-token cap. For each prompt and weight, 4 replications each contain 2 independent groups of 17 fresh responses. Thus the complete run has 10,552 groups per weight and 538,152 responses overall. Certificate. The certificate calculation follows Appendix D.1, except that it uses a separately scoped family of 48 comparisons (3 weights by 16 nonzero update budgets). With clipping cap 10 nats and α = 0.05, the common Hoeffding–Bonferroni subtraction is 0.180384 nats. No certificate value was clipped. Table 7 reports the two endpoints. E.2

HH-RLHF OUTPUT- LEVEL REPLAY AND COST

Replay protocol. The replay verifies all 7,914 raw batch checksums, identities, seeds, acceptance uniforms, and probability identities. Every response is scored by both pinned GPT-2 reward models. If a prompt–response pair exceeds the 1,024-token GPT-2 context, we trim only the response tokens for scoring. This affects 118 responses (0.022% of the total), with counts recorded in the scoring artifacts. The local decoder returns proposal 0, and MH replays the saved acceptance uniforms. SIR metrics average over its exact selection probabilities within each pool. The 10,000-draw paired bootstrap resamples whole prompts while retaining all 8 groups. Intervals are descriptive pointwise 95% percentile intervals, separate from the simultaneous certificate bounds. At M = 17, MH responses are 6–10 tokens shorter on average than local decoding (Table 8), but this comparison does not establish that shorter length causes the reward-score changes. Fresh-pool effective sample sizes and maximum normalized weights are recorded in poolconcentration.csv. Token costs include EOS and all discarded candidates. The reward-score sidecars are cryptographically tied to the raw certificate files and pinned reward revisions. Serving cost. Table 10 reports end-to-end generation and MH selection on one H200. Each timed batch contains one prompt and M responses. The 16 prompts are hash-selected, and each prompt, budget, and weight has 3 timed repetitions after a separate warm-up, giving 432 trials in total. The measurements include both FP32 Gemma component policies and exclude model loading and warm-up.

49

Table 7: HH-RLHF GPT-2-specialist certificate results, in nats. Cumulative MH acceptance excludes initialization. w1

Mean GM

0.25 0.50 0.75

0.228 0.427 0.321

MH acceptance (%)

M =9

M = 17

Lower bound Clipped Mean GM

Lower bound Clipped n = 8

0.048 0.247 0.141

0.000 0.000 0.000

0.244 0.460 0.338

0.063 0.280 0.158

0.000 0.000 0.000

77.19 71.18 74.71

n = 16 75.86 69.27 73.27

Table 8: Output-level HH-RLHF results at every candidate budget. H and S are the raw helpfulness and harmlessness reward logits, and weighted reward is w1 H + (1 − w1 )S. Length counts returnedresponse tokens; total tokens include all generated candidates. M Total tokens Method

H

S Weighted Length

Helpfulness weight w1 = 0.25 1 244.5 Local decoder (qw ) 2 488.7 MH SIR 3 733.8 MH SIR 5 1223.5 MH SIR 9 2202.3 MH SIR 17 4158.3 MH SIR

1.611 1.573 1.581 1.568 1.569 1.562 1.560 1.538 1.549 1.534 1.541

−0.832 −0.808 −0.815 −0.820 −0.813 −0.806 −0.809 −0.814 −0.808 −0.790 −0.803

−0.221 −0.213 −0.216 −0.223 −0.218 −0.214 −0.217 −0.226 −0.218 −0.209 −0.217

244.5 241.3 242.1 241.9 241.4 240.1 240.8 240.3 240.0 238.5 239.2

Helpfulness weight w1 = 0.5 1 263.9 Local decoder (qw ) 2 526.2 MH SIR 3 790.2 MH SIR 5 1315.9 MH SIR 9 2369.2 MH SIR 17 4473.7 MH SIR

1.802 1.761 1.765 1.742 1.746 1.725 1.724 1.709 1.707 1.690 1.697

−1.043 −1.013 −1.017 −0.995 −1.003 −0.995 −0.991 −0.978 −0.979 −0.953 −0.970

0.379 0.374 0.374 0.373 0.371 0.365 0.366 0.366 0.364 0.368 0.363

263.9 259.9 260.6 258.9 259.5 257.3 257.7 255.8 256.5 254.5 255.2

Helpfulness weight w1 = 0.75 1 284.2 Local decoder (qw ) 2 567.6 MH SIR 3 851.0 MH SIR 5 1418.1 MH SIR 9 2552.7 MH SIR 17 4820.6 MH SIR

1.989 1.947 1.946 1.929 1.927 1.894 1.898 1.877 1.881 1.875 1.874

−1.231 −1.205 −1.203 −1.194 −1.193 −1.175 −1.177 −1.157 −1.165 −1.164 −1.160

1.184 1.159 1.159 1.148 1.147 1.127 1.130 1.118 1.120 1.115 1.116

284.2 279.6 280.2 277.8 278.4 276.5 276.8 274.7 275.6 274.2 274.8

50

Table 9: Paired MH-minus-SIR differences on identical HH-RLHF pools, with pointwise 95% prompt-bootstrap intervals. The selected log ρ difference is a selection diagnostic and is not a KL improvement. Helpfulness weight w1 0.5

0.75

MH − SIR helpfulness reward 2 −0.0073 [−0.0154, 0.0004] 3 −0.0011 [−0.0116, 0.0094] 5 0.0011 [−0.0103, 0.0127] 9 −0.0110 [−0.0235, 0.0017] 17 −0.0066 [−0.0199, 0.0063]

−0.0044 [−0.0126, 0.0040] −0.0046 [−0.0144, 0.0050] 0.0010 [−0.0099, 0.0121] 0.0016 [−0.0100, 0.0135] −0.0072 [−0.0198, 0.0055]

0.0015 [−0.0071, 0.0102] 0.0019 [−0.0084, 0.0122] −0.0048 [−0.0168, 0.0073] −0.0046 [−0.0173, 0.0079] 0.0010 [−0.0119, 0.0138]

MH − SIR harmlessness reward 2 0.0070 [−0.0017, 0.0155] 3 −0.0072 [−0.0177, 0.0037] 5 0.0027 [−0.0092, 0.0146] 9 −0.0067 [−0.0198, 0.0062] 17 0.0128 [−0.0010, 0.0263]

0.0048 [−0.0035, 0.0132] 0.0081 [−0.0022, 0.0186] −0.0047 [−0.0164, 0.0070] 0.0019 [−0.0107, 0.0142] 0.0171 [0.0045, 0.0299]

−0.0025 [−0.0117, 0.0069] −0.0007 [−0.0118, 0.0105] 0.0023 [−0.0102, 0.0148] 0.0081 [−0.0052, 0.0213] −0.0047 [−0.0181, 0.0091]

MH − SIR weighted reward 2 0.0034 [−0.0021, 0.0088] 3 −0.0057 [−0.0121, 0.0009] 5 0.0023 [−0.0050, 0.0096] 9 −0.0078 [−0.0159, 0.0004] 17 0.0079 [−0.0004, 0.0162]

0.0002 [−0.0032, 0.0037] 0.0018 [−0.0023, 0.0059] −0.0019 [−0.0067, 0.0028] 0.0018 [−0.0033, 0.0068] 0.0049 [−0.0003, 0.0102]

0.0005 [−0.0047, 0.0059] 0.0013 [−0.0050, 0.0076] −0.0030 [−0.0104, 0.0042] −0.0014 [−0.0092, 0.0062] −0.0005 [−0.0084, 0.0074]

MH − SIR selected log ρ 2 0.0324 [0.0275, 0.0372] 3 0.0395 [0.0327, 0.0463] 5 0.0385 [0.0310, 0.0461] 9 0.0322 [0.0236, 0.0409] 17 0.0273 [0.0171, 0.0373]

0.0372 [0.0315, 0.0427] 0.0467 [0.0397, 0.0537] 0.0446 [0.0359, 0.0534] 0.0453 [0.0356, 0.0552] 0.0394 [0.0283, 0.0505]

0.0301 [0.0248, 0.0352] 0.0390 [0.0322, 0.0457] 0.0458 [0.0370, 0.0544] 0.0484 [0.0389, 0.0578] 0.0348 [0.0251, 0.0449]

M

0.25

Table 10: Measured HH-RLHF serving cost on one H200. Peak allocated memory is the maximum over 48 timed trials in each stratum. w1

M

MH mean latency (s)

p95 (s)

Peak allocated (GB)

0.25 0.25 0.25 0.5 0.5 0.5 0.75 0.75 0.75

1 3 9 1 3 9 1 3 9

20.92 23.20 24.54 21.74 24.24 25.67 23.48 25.94 28.19

36.07 38.35 39.55 37.17 39.51 40.59 40.62 42.97 43.98

41.23 41.56 42.54 41.23 41.56 42.54 41.23 41.56 42.54

51

F

T RAINED LLM CONTINUATION - TREE EXPERIMENT

This experiment directly compares the consensus objectives of MH and ordinary SIR on enumerable distributions derived from the trained GSM8K specialists. It complements the full-response certificates in Section 4.3 by making the target and both output laws available for direct evaluation. All quantities below refer to the restricted continuation policies defined here, rather than the full-response policies. F.1

P OLICIES , QUESTIONS , AND CONTINUATION TREES

We reuse the Gemma-4-E2B-it accuracy and brevity DPO adapters and their shared reference model from Appendix D.1, with no additional training. A seeded permutation of the GSM8K test set selects 5 pilot questions and 50 separate evaluation questions. These questions are held out from specialist training but belong to the same 1,319-question test cohort as the full-response study. The pilot checks implementation, numerical precision, memory, and runtime. The final protocol is frozen before evaluating the 50 questions. The original prompt template and tokenizer are reused. No questions are selected or excluded on the basis of reference correctness, specialist disagreement, or the observed MH–SIR gap. Each question supplies an original context at the normal assistant response boundary and a midpoint context. For the latter, we generate one greedy reference-model response with a 1,024-token cap, remove EOS from the response-token count, and retain the first half of the non-EOS tokens, rounding down. We append these exact token IDs to the original context, without decoding and re-tokenizing or adding another assistant header. The protocol specifies the original context as a fallback for an empty midpoint. None of the 50 evaluation questions requires this fallback. For each context, we expand the reference model’s top K = 8 tokens at every reachable prefix through a horizon of T = 4 additional tokens. Ties in reference logits are broken by ascending token ID. The same mask is applied to each adapter separately, at temperature 1. An EOS token ends a branch only if it is in the mask. At the horizon, the branch ends without an additional EOS factor. Without early EOS, this gives 585 nonterminal prefixes and 4,096 leaves per context. We cache the allowed token IDs in reference order, selected logits, full-vocabulary log normalizers, prefix token IDs, and EOS IDs. All weights, budgets, and sensitivity checks reuse these evaluations. The restricted target. Let A(h) be the shared allowed-token set at prefix h. For i ∈ {a, b}, write πifull for the original accuracy or brevity policy and define its restricted conditional by πifull (v | h) , full u∈A(h) πi (u | h)

πi (v | h) = P

(65)

v ∈ A(h),

with probability 0 outside A(h). Within this appendix, qw and pbw denote the proposal and target on this tree. With accuracy weight w = w1 ∈ {0.25, 0.5, 0.75}, define zw (h) =

X

πa (v | h)w πb (v | h)1−w ,

qw (v | h) =

v∈A(h)

πa (v | h)w πb (v | h)1−w . zw (h)

For each complete continuation y, multiply these factors along its path: ρw (y) =

Y t

zw (ht ),

pbw (y) =

qw (y)ρw (y) , Zw

Zw =

X

qw (y)ρw (y).

y

We independently verify qw (y)ρw (y) = πa (y)w πb (y)1−w . Masking and renormalizing the adapters changes their sequence distributions: this target is generally different from the full-vocabulary product target conditioned on remaining within the tree. F.2

F ULL OUTPUT LAWS AND NUMERICAL VALIDATION

The candidate budgets are M ∈ {1, 2, 3, 5, 9}, counting MH initialization. We compute HM = qw K M −1 by sorting the leaf weights and accumulating prefix and suffix sums, using the recursion 52

in Appendix C.1. Ordinary SIR draws M IID candidates from qw and resamples proportionally to ρw . Its marginal law is computed by the scalar Laplace identity !M −1 Z ∞ X −tρw (y) −tρw (v) SM (y) = M qw (y)ρw (y) e qw (v)e dt, 0

v

where the sum is over complete continuations. We evaluate this integral adaptively in log time, after an invariant common rescaling of the weights. Neither calculation samples an output law or constructs a dense transition matrix. The directly computed divergences, all in nats, are Dq = KL(qw ∥b pw ), DH (M ) = KL(HM ∥b pw ), DS (M ) = KL(SM ∥b pw ). The consensus identity gives the actual gains ∆H (M ) = Dq − DH (M ) and ∆S (M ) = Dq − DS (M ), and the objective gap Jew (HM ) − Jew (SM ) = DS (M ) − DH (M ), Jew (µ) = −wKL(µ∥πa ) − (1 − w)KL(µ∥πb ). We also verify this identity by evaluating the two component KL divergences directly. DPO training alone does not establish that this restricted-policy consensus objective equals the original taskreward objective. Precision and implementation checks. Model inference uses FP32 with TF32 disabled, and probability arithmetic uses FP64. We check normalization before any numerical renormalization, the two target constructions, the M = 1 identities, and the KL ordering. Diagnostic tests cover horizon 1, identical adapters, a single nonzero policy weight, and agreement with direct MH and SIR calculations on tiny supports, including repeated candidate draws. The pilot also compares cached and direct model evaluation at 30 prefixes: the reference top-8 rankings agree, and the largest change in a restricted log probability is 4.80 × 10−5 . This model-inference variation is separate from the numerical precision checks below, which are conditional on the cached logits. The nominal quadrature tolerance is 10−12 . Every evaluation is repeated at 10−13 and with extended-precision probability arithmetic. Pilot amendments, recorded before the final run, allow quadrature termination due to roundoff only when both its estimated L1 error and its normalization residual are below 10−10 , with independent law and KL stability checks. Across all 1,200 final context–weight–tree cases, the largest normalization residual is 1.93 × 10−14 and the largest KL change under the precision checks is 1.91 × 10−14 nats. All cases pass these checks. The prespecified reporting resolution is 10−10 nats, and smaller comparisons are reported as unresolved. These checks do not provide rigorous error bounds. Enumeration removes sampling and density-estimation error from the conditional KL calculations, while floating-point and quadrature error remain. F.3

R ESULTS , CERTIFICATES , AND UNCERTAINTY

Figure 6 shows mean divergences over the 50 questions for original and midpoint contexts at w1 = 0.5. The tables below report results at all three weights. For the common certificate GM in (11), we draw 100,000 IID pools of 9 leaves from each enumerated proposal and use pool prefixes for smaller budgets. This requires no further model inference. We estimate E[GM ] and its Monte Carlo standard error separately for every question, context, weight, and tree setting. Its expectation is a theoretical lower bound on both gains. The reported sample mean is not a certified lower confidence bound. Arithmetic means over questions are the primary summaries. Pointwise 95% intervals use 10,000 bootstrap samples of whole questions, keeping both contexts, all weights, all budgets, and all sensitivity settings together within each resampled question. These intervals describe variation across questions and do not include model-inference uncertainty. For the mean certificate, the separate Monte Carlo standard error is the root sum of squared per-question standard errors divided by 50. At M = 9, all six primary mean objective gaps have positive pointwise bootstrap intervals (Tables 11 and 12). The absolute advantage is small, and question heterogeneity is substantial: for original contexts at w1 = 0.25 and 0.5, the largest single-question gap contributes about 98% of the total gap. The original-context median gaps are only 2.84 × 10−8 to 7.79 × 10−8 nats. In midpoint contexts, mean MH KL at M = 9 is below the 10−10 -nat reporting resolution at all three weights. This does not establish exact convergence or an unbounded relative advantage. The estimated mean certificate is approximately 75–90% of mean MH gain at this budget. 53

KL to tree target (nats)

Original context

Midpoint context

10 −2

10 −2

10 −4

10 −4

10 −6

10 −6

10 −8

10 −8

10 −10

10 −10 1

2

3

5 Candidate budget M MH

9

ordinary SIR

1 local decoder

2

3

5 Candidate budget M

9

below resolution

Figure 6: KL to the target on trained-policy continuation trees. Curves average 50 questions at accuracy weight w1 = 0.5. Left: original prompts. Right: midpoint contexts, taken halfway through a greedy reference-model response. Each tree uses the shared reference top-8 tokens at each prefix and a 4-token horizon. The target is the product of the restricted, separately renormalized specialists. Shading gives pointwise 95% question-bootstrap intervals, hatched for SIR. The dotted baseline is the local decoder. Downward triangles mark means below the 10−10 -nat reporting resolution; interval endpoints below this value are displayed at the same floor. Both panels use the same scale. Table 11: Direct comparisons at M = 9 on top-8, horizon-4 trees. All numerical entries other than w1 are in 10−6 nats and are means over 50 questions. Parentheses give the separate Monte Carlo standard error of the mean certificate. DS − DH is the MH consensus advantage. < 0.0001 marks a mean KL below the 10−10 -nat reporting resolution. Context

w1

Original Original Original

0.25 2272 0.5 1229 0.75 136.5

Dq

DH (9) DS (9) DS − DH Est. E[G9 ] (SE) 105.7 109.7 0.153

271.8 197.2 4.752

166.1 87.49 4.599

1639 (8.27) 843.5 (6.81) 115.8 (1.00)

Midpoint 0.25 884.3 < 0.0001 Midpoint 0.5 1308 < 0.0001 Midpoint 0.75 860.2 < 0.0001

10.36 14.33 9.362

10.36 14.33 9.362

788.7 (0.542) 1171 (0.834) 770.1 (0.479)

Table 12: Variation in the MH–SIR objective gap at M = 9. Primary top-8, horizon-4 setting. The first three numerical summaries are in 10−6 nats. Intervals are pointwise 95% questionbootstrap intervals for the mean; SD describes per-question variation. The last column counts absolute per-question gaps no larger than 10−10 nats.

F.4

Context

w1

Mean gap [95% CI]

Question SD

Median gap

Unresolved / 50

Original Original Original

0.25 0.5 0.75

166.1 [0.748, 493.7] 87.49 [0.656, 259.3] 4.599 [0.296, 12.71]

1149 603.3 27.67

0.0764 0.0779 0.0284

5 5 8

Midpoint Midpoint Midpoint

0.25 0.5 0.75

10.36 [2.049, 21.24] 14.33 [1.128, 35.09] 9.362 [0.623, 24.48]

35.60 65.42 47.76

0.00150 0.00339 0.00259

17 15 18

H ORIZON AND TOKEN - MASK SENSITIVITY

The three prespecified sensitivity checks use the same 50 questions, two contexts, three weights, and five budgets. We evaluate top-8 trees at horizons 2 and 3, and top-4 trees at horizon 4, using only cached logits. For a shorter horizon we stop at that depth and recompute the target normalization and output laws. The resulting target generally differs from the corresponding marginal of the horizon-4 target. For the top-4 check, we keep the first 4 tokens in reference order at each reachable prefix and 54

renormalize each adapter again. Each setting contributes 300 context–weight cases, for 1,200 cases including the primary setting. Table 13: Horizon and mask sensitivity at M = 9. Mean MH consensus advantage DS − DH , in 10−6 nats. All 24 pointwise 95% intervals for these means exclude 0; the complete intervals and results at every budget are in the companion tables. These settings define different restricted targets. Primary

Sensitivity checks

Context

w1

K = 8, T = 4

K = 8, T = 2

K = 8, T = 3

K = 4, T = 4

Original Original Original

0.25 0.5 0.75

166.1 87.49 4.599

2.405 1.152 0.280

165.4 86.74 4.284

166.1 87.47 4.596

Midpoint Midpoint Midpoint

0.25 0.5 0.75

10.36 14.33 9.362

0.647 1.274 0.666

5.904 10.57 7.550

7.753 9.319 6.576

The positive mean MH advantage persists in every sensitivity setting at M = 9 (Table 13). Many individual gaps remain unresolved: depending on context and weight, 25–33 of the 50 gaps are unresolved at horizon 2, 11–23 at horizon 3, and 6–19 with the top-4 mask at horizon 4. This sweep from 2 to 4 tokens is a sensitivity check, not a test of the long-response asymptotic theorem. Probability mass P retained by the mask. For adapter i, we record the original full-vocabulary mass mi (h) = v∈A(h) πifull (v | h). Table 14 reports its proposal-weighted mean at each depth for w1 = 0.5, conditional on reaching that depth, followed by an arithmetic mean over questions. Per-prefix minimum, quartiles, maximum, and proposal-weighted means at every weight are in the released evaluation records. High proposal-weighted retention need not hold at rare prefixes: the smallest recorded brevity mass on an original-context top-8 prefix is 3.61 × 10−6 . Retained mass describes the restriction but does not establish equivalence to unrestricted generation. Table 14: Retained full-vocabulary mass by depth. Question means of proposal-weighted retained mass, in percent, at w1 = 0.5 and horizon 4. Depth 0 is the continuation root. Values rounding to 100.000% do not imply that every prefix retains all mass.

F.5

Context

Adapter

K

Depth 0

Depth 1

Depth 2

Depth 3

Original Original Original Original

Accuracy Brevity Accuracy Brevity

8 8 4 4

100.000 99.998 100.000 99.994

100.000 100.000 100.000 99.998

100.000 99.999 99.966 99.920

100.000 100.000 99.999 99.998

Midpoint Midpoint Midpoint Midpoint

Accuracy Brevity Accuracy Brevity

8 8 4 4

99.756 99.494 99.258 98.746

99.914 99.866 99.700 98.331

99.876 99.784 99.681 99.003

99.926 99.872 99.805 99.696

C OMPUTE AND REPRODUCTION

The final run constructs 100 context trees and evaluates 58,415 nonterminal prefixes per model, with 11,400 GPU forward calls across the reference and two adapters. We reuse each context’s KV cache, batch up to 16 prefixes at the same depth, and switch adapters on the shared base model. On one H200, tree evaluation takes 553 seconds and greedy reference generation takes 578 seconds, with peak allocated memory of 21.1 GB. These are offline tree construction costs, not sampler serving latencies. The numerical laws, certificates, bootstrap summaries, and all sensitivity checks run on CPU. The companion suite includes the frozen configuration, question and context token IDs, checkpoint hashes, seeds, cached trees, numerical validation records, per-question results, and plotting code. Results are archived under results/llm-tree. The llm-tree-analysis job recomputes numerical results from cached model evaluations, and llm-tree-presentation rebuilds the 55

summaries and two archived plots. The manuscript figure uses the same summaries. The accompanying instructions explain how to move saved numerical outputs aside to force fresh computation. A fresh CPU replay in a separate directory reproduced all 1,320 pilot and final cases and their summaries, with no differences among 176,477 compared numerical fields. This is a same-operator reproducibility check, not an independent replication. The study measures direct consensus-objective differences on short, restricted policies and illustrates the ordering in Theorem 1. The small absolute gaps do not establish a large practical advantage, improved task rewards, or the unobserved MH–SIR objective gap on full GSM8K responses.

56

Related documents

• Metropolis-Hastings Dominates Importance Resampling for Policy Composition#1188158
• Transcribe, Translate, and Optimize: Joint Reward Learning for Speech Translation#1062426
• Beyond Saying Less: Fine-Grained Alignment for Informative and Faithful Vision-Language Models#1129887
• GVPO++: Group Variance Policy Optimization for LLM Post-Training and On-Policy Distillation#1035836
• Gibbs-Gap Policy Optimization for Off-Policy RL with Verifiable Rewards#1355803