PaperlayerView exact revision on arXiv

Source-linked AI summary

Metropolis-Hastings Dominates Importance Resampling for Policy Composition

Alexey Kurennoy, Ramil Yarullin, Fergal Reid

arXiv:2610.03480v1cs.LG

TL;DR

Combining reward-specific policies at decoding time can explore trade-offs without retraining, but local next-token composition can be biased relative to the complete-response target. The paper analyzes independence-MH correction and finds it no farther from that target than same-budget SIR under every convex f-divergence.

  • Problem

    Local product decoding combines next-token probabilities rather than sampling the weighted product over complete responses, and these distributions generally differ because later continuations affect the sequence target.

    Source: §1 · p. 1

  • Method

    The paper analyzes independence-MH correction of local product decoding and derives a consensus-improvement bound and sampling-error characterizations in two asymptotic regimes.

    Source: §1 · p. 2

  • Results

    At every rollout budget, MH is at least as close to the sequence target as ordinary SIR under every convex f-divergence.

    Source: §1 · p. 2, §6 · p. 10

  • Takeaways & Limitations

    Theoretical comparisons are particularly important because LLM-scale output probabilities are not readily evaluable and task rewards do not capture consensus.

    Source: §6 · p. 10

    When target-to-proposal log-ratio fluctuations grow with the rollout budget, some target mass remains inaccessible often enough that even the best selection rule has positive limiting error.

    Source: §3.4 · p. 6

Abstract

from arXiv · show

Post-training a large language model (LLM) often requires exploring trade-offs 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 the log ratio between target and uncorrected-decoder probabilities fluctuates increasingly widely, as can happen for long responses. We complement our analysis with experiments in enumerable and LLM-scale settings.

1 INTRODUCTION

Decoding-time composition combines reward-specialized policies to explore trade-offs without retraining, but local product decoding can be biased relative to the complete-response target. The paper analyzes an MH correction and establishes finite-budget dominance over SIR, alongside additional guarantees and experiments.

1 INTRODUCTION

  • Local product decoding can be biased because next-token probabilities ignore how much the policies agree on later continuations.It targets a weighted product of complete-response probabilities; exact sampling from that target token by token generally requires summing over continuations.Source: §1 · p. 1
  • MH uses additional rollouts to accept or reject independently generated responses, without a separate reward model or post-generation candidate scoring.Proposals can be batched, with selection performed afterward.Source: §1 · pp. 1–2
  • At every rollout budget, MH is at least as close to the sequence target as ordinary SIR under every convex f-divergence.The paper also derives a consensus-improvement bound and characterizes sampling error in two asymptotic regimes.Source: §1 · p. 2
  • MH is strictly closer than SIR for KL in both directions and total variation when M ≥2 and the local decoder differs from the target.The comparison uses the same recorded information and rollout budget for both methods.Source: §1 · p. 2
  • Experiments examine enumerable and LLM-scale settings.The introduction identifies these as complements to the theoretical analysis.Source: §1 · p. 2

2 CORRECTING LOCAL PRODUCT DECODING

The section defines the complete-response product target and explains why local tokenwise normalization can produce a different distribution. It then uses recorded local normalizers for an MH correction and connects the product target to consensus and scalarized objectives.

2 CORRECTING LOCAL PRODUCT DECODING

  • The setup assumes active policies share a tokenizer, finite vocabulary, and common support tree.Responses terminate at EOS or a length cap, with shorter responses padded deterministically with EOS tokens.Source: §2 · pp. 2–3
  • The weighted geometric average of complete-response probabilities defines a normalized target whose normalizer sums over exponentially many responses.Local product decoding avoids that sum by normalizing at each token, but generally differs from the sequence target.Source: §2 · p. 3
  • In Example 1, local decoding assigns probability 5/8 rather than 1/2 to the j = 1 branch, while the sequence target is uniform over four responses.The continuation product mass is 1 after j = 0 and 0.6 after j = 1.Source: §2 · p. 3
  • The local-to-global correction weights each local-decoder response by its recorded product of stepwise normalizers, which captures accumulated policy disagreement.The normalizers measure next-token disagreement; variation across responses explains why the local and sequence-target distributions differ.Source: §2 · p. 3
  • Independence MH proposes a fresh local-decoder response and accepts it using the ratio of recorded normalizers, so the unknown target normalizer cancels.It always accepts proposals with higher normalizers and accepts some with lower ones; each update takes O(M) scalar operations after evaluating active policies across the M responses.Source: §2 · p. 3
  • The consensus objective measures agreement with supplied policies through a negative weighted sum of KL divergences, and the weighted product uniquely maximizes it.For specialists optimal under a common reference policy and β, sampling from the product recovers the scalarized optimum without retraining.Source: §2 · pp. 3–4

3 THEORETICAL ANALYSIS OF THE MH CORRECTION

The analysis compares MH and ordinary SIR for sampling from a sequence-level target, then studies objective gains and sampling error in two asymptotic regimes. Its results establish finite-budget dominance and identify conditions where limited candidate pools constrain accuracy.

3.1 DOMINANCE OF MH OVER SIR AT EVERY CANDIDATE BUDGET

  • For every candidate budget, MH is no farther from the target than ordinary SIR under every convex f-divergence, with strict improvement for M ≥2 under the stated conditions.The strict comparison holds when p ≠ q and the divergence is total variation or is generated by a strictly convex f; the result also extends to reward-tilted targets.Source: §3.1 · pp. 4–5

3.2 OBJECTIVE GAIN GUARANTEE

  • The recorded-weight certificate lower-bounds MH’s improvement over the local decoder, and the gains are nonnegative and nonincreasing with rollout budget under the proposition’s stated assumptions.The same lower bound holds for SIR, so it does not measure MH’s advantage over SIR or the remaining divergence.Source: §3.2 · p. 5

3.3 NEARBY COMPONENT POLICIES

  • As component policies approach agreement, additional MH rollouts improve the sampling-error order, whereas SIR generally improves only the leading coefficient.The analysis also shows that the 4M error exponent cannot be uniformly improved by selectors restricted to q, M sampled candidates, and recorded weights.Source: §3.3 · pp. 5–6

3.4 CANDIDATE BUDGET AND RESPONSE LENGTH

  • When log target-to-proposal fluctuations grow with the rollout budget, some target mass can remain inaccessible often enough to force positive limiting error, even for the best candidate-selection rule.At the specified budget scaling, both MH and SIR attain this limit; for repeated Example 1 responses, the corresponding budgets grow exponentially with response length.Source: §3.4 · p. 6

4 EMPIRICAL STUDY

The empirical study compares exact sampling errors on enumerable and restricted continuation-tree problems, then evaluates consensus gains and task-level effects on GSM8K and HH-RLHF. Full-response experiments use certificates and task outcomes because sampler probabilities are difficult to evaluate directly.

4.1 SAMPLING ERROR IN AN ENUMERABLE SETTING

  • At M = 9, MH has lower mean KL than ordinary SIR in all five enumerable settings, and lower estimated binned TV on all 23 tested instances.In three settings, MH with 9 candidates also has lower mean KL than SIR with 51; adaptive SMC outperforms MH on one peaky instance.Source: §4.1 · p. 7, Figure 2 · p. 7
  • As δ decreases, MH at M = 2 and M = 3 approaches eighth- and twelfth-order error, while ordinary SIR retains fourth-order error.The enumerable study varies policy concentration and response length across five settings; the first MH update removes approximately 70–95% of initial mean KL.Source: §4.1 · pp. 6–7

4.2 DIRECT COMPARISONS ON TRAINED-POLICY CONTINUATION TREES

  • With 2 candidates, MH removes 96.8% of midpoint-context mean KL, compared with 76.0% for SIR; with 3 candidates, MH has lower mean KL than SIR with 9.Across 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, with all six paired intervals excluding 0.Source: §4.2 · p. 7

4.3 CONSENSUS GAINS AND TASK-LEVEL EFFECTS ON GSM8K

  • At M = 17, GSM8K consensus-improvement lower bounds for MH and SIR are 0.742, 1.644, and 1.330 nats across increasing accuracy weights; both corrections also yield shorter, more accurate responses than local decoding.For MH, M = 3 raises accuracy by 0.8–1.2 points and reduces mean returned length by 11–26 tokens; at M = 17 the changes are 1.1–1.3 points and 16–42 tokens.Source: §4.3 · p. 8

4.4 CONSENSUS GAINS ON HH-RLHF

  • At M = 17, HH-RLHF consensus-improvement lower bounds are 0.063, 0.280, and 0.158 nats across increasing helpfulness weights; MH lowers helpfulness and raises harmlessness versus local decoding.The changes are −0.077 to −0.114 helpfulness logits and +0.042 to +0.090 harmlessness logits; the weighted-score change is negative at weights 0.5 and 0.75 and unresolved at 0.25.Source: §4.4 · p. 8

4.5 SCOPE AND PRACTICAL IMPLICATIONS

  • Full-response experiments cover one model family and two tasks, and their certificates bound improvement over local decoding rather than the MH–SIR gap; task-level comparisons do not establish fidelity to the product target.The HH-RLHF scores are reward-model proxies rather than human judgments, and the full-response sampler probabilities are difficult to evaluate directly.Source: §4 · p. 6, §4.5 · p. 8, §4.3 · p. 8

5 RELATED WORK

The related work situates policy composition and globally normalized text sampling alongside the paper’s focus on finite-budget selection guarantees. Its comparison orders marginal output distributions under every convex f-divergence at each budget.

Decoding-time policy composition

  • Decoding-time composition combines objective-specific policies, while existing methods include weighted sequence products, weighted logits, utility-based policy selection, and adversarial reward-weight optimization.The paper studies sampling at fixed weights; MOD derives a weighted sequence product for KL-regularized alignment, and MAHALO’s untruncated softmax follows the local product law.Source: §5 · p. 9

Sampling globally normalized text distributions

  • Prior approaches to globally normalized text sampling include local-normalizer corrections, independent MH with local proposals, and methods that use learned continuation information or resample suffixes.This paper analyzes independent complete-response proposals.Source: §5 · p. 9

Finite-budget selection guarantees

  • Unlike prior finite-budget bias-rate or worst-start TV analyses, this work orders MH and SIR marginal output distributions under every convex f-divergence at each budget.The comparison also extends to fixed schedules of the multiple-try sampler.Source: §5 · p. 9

6 CONCLUSION

The conclusion presents independence MH as a finite-budget correction with a consensus-improvement certificate, while noting that candidate-pool coverage limits closeness to the target. The supplementary passages specify target construction, reproducibility resources, and scope-related cautions.

6 CONCLUSION

  • Independence MH is no farther from the sequence target than ordinary SIR under every convex f-divergence at every candidate budget, and recorded rollout weights can certify consensus improvement over local decoding.Improvement need not imply closeness to the target because neither method can return responses absent from its candidate pool.Source: §6 · p. 10

AI USE STATEMENT

  • Generative AI tools assisted with readability, literature searches, figures, LaTeX preparation, and selected theoretical arguments and proofs; the authors take responsibility for the reported science.Source: AI USE STATEMENT · p. 11

ETHICS STATEMENT

  • The method inherits limitations of its policies’ training data and reward signals; more accurate sampling from their product alone does not establish safety or better external performance.Source: ETHICS STATEMENT · p. 11

REPRODUCIBILITY STATEMENT

  • The reproducibility statement identifies appendices documenting configurations, evaluations, uncertainty calculations, and the associated code repository.Source: REPRODUCIBILITY STATEMENT · p. 11

A PROOFS OF THE MAIN RESULTS

  • The proof appendix establishes exact correction weights from local normalizers, then proves the MH–SIR comparison, objective guarantees, nearby-policy rates, and critical-budget limit.Source: A PROOFS OF THE MAIN RESULTS · p. 15

A.1 LOCAL NORMALIZERS AND THE SEQUENCE-LEVEL TARGET

  • The sequence target normalizes the weighted geometric product of full-response probabilities; local product decoding instead normalizes at each token to avoid summing over exponentially many responses.Temperature and masking define the component policies in the target, while applying top-k or nucleus truncation only to the combined proposal generally removes target support and invalidates the original correction.Source: §A.1 · p. 16

A.2 PRIORITY REPRESENTATION AND PROOF OF THEOREM 1

The proof represents finite-budget MH as a priority-selection rule on an iid candidate pool. Coupling that rule with SIR orders selected weights, which supports the divergence comparison; a separate proposition gives total-variation convergence to the target.

A.2 PRIORITY REPRESENTATION AND PROOF OF THEOREM 1

  • For a fixed candidate pool, MH in uniformly random candidate order and priority selection have the same output law, so iid-pool MH can be represented by priority selection.The priority representation also allows independent batch winners to be combined by keeping the largest winner key, without new model evaluations.Source: §A.2 · pp. 16–17
  • Under a coupling, MH selects an importance weight at least as large as SIR’s, and the resulting weight ordering yields MH’s no-worse convex f-divergence comparison with the target.The proof also establishes strict improvement for KL in both directions and total variation when M ≥ 2 and the recorded weight is nonconstant.Source: §A.2 · pp. 19–20

A.3 STATIONARITY AND CONVERGENCE IN TOTAL VARIATION

  • The target is stationary for the independence-MH kernel, with total-variation error bounded by (1 − ε)^n times the initial error, where ε = Z max_y ρ(y).Source: §A.3 · p. 20

A.4 PROOF OF PROPOSITION 1

The proof establishes that MH’s objective gains are nonnegative and diminishing with rollout budget, and gives a recorded-weight lower bound on improvement over the uncorrected decoder. Its confidence guarantee is conditional on the fixed prompts and checkpoints.

A.4 PROOF OF PROPOSITION 1

  • MH’s divergence from the target is nonincreasing and convex in the candidate budget, so its gains are nonnegative and diminishing.The proof uses data processing under a stationary MH kernel and convexity in the candidate budget.Source: §A.4 · pp. 21–22
  • The recorded-weight bound certifies improvement in the consensus objective, is nonnegative, and becomes asymptotically tight at λKL(q∥p).The bound is zero at M = 1 and when all pool weights are equal; under exact-specialist assumptions, the conclusion also applies to the external reward objective.Source: §A.4 · p. 23
  • The confidence bound covers objective improvement averaged over fixed prompts and fresh proposal pools, not a realized response or a newly sampled prompt set.It is conditional on the fixed prompts and checkpoints.Source: §A.4 · p. 24

A.5 PROOF OF THEOREM 2

The proof analyzes the correction as the reward-specific policies approach agreement, using response-level disagreement to characterize the leading errors. The expansion is for a fixed tree and is not uniform as response length grows.

A.5 PROOF OF THEOREM 2

  • Along a response, D(y) accumulates the weighted variance of component perturbations around their average; deterministic EOS padding adds zero.The leading proposal-bias coefficient C measures variation of D across responses, and the quartic term vanishes when D is constant.Source: §A.5 · p. 25
  • When D is nonconstant, the exact MH residual coefficients are positive; when D is constant, every coefficient CM vanishes.The proof establishes positivity by considering responses attaining the minimum value of D.Source: §A.5 · p. 26
  • The near-agreement expansion holds for a fixed tree, and its remainder is not uniform in the number of concatenated response modules.Although C grows linearly with the number of modules in the example, the expansion does not describe long responses at fixed policy separation.Source: §A.5 · p. 26

A.6 CANDIDATE COVERAGE AND PROOF OF THEOREM 3

The appendix derives candidate-coverage limits, extends MH’s divergence comparison to specified block schedules, and establishes an exact worst-case total-variation guarantee. These results concern fixed-proposal complete-response selection, not adaptive proposal construction or prefix-level search.

A.6 CANDIDATE COVERAGE AND PROOF OF THEOREM 3

  • Every selector’s total-variation error is bounded below by target mass in a likelihood-ratio tail minus the probability the candidate pool reaches that tail.For a median threshold, the supplied bound is at least 1/2 − Me^−τ.Source: §A.6 · p. 27
  • At the likelihood-tail threshold, MH and ordinary SIR both attain the limiting total-variation error 1 − c under Theorem 3’s assumptions.The converse applies uniformly to candidate selectors; the matching upper bound uses clipping in the proof but the methods use their original weights.Source: §A.6 · pp. 27–29
  • On the structured N-module family, fixed TV accuracy below 1 requires exponentially many complete proposals, while exact sequential sampling uses O(N) conditional policy-vector evaluations.The comparison counts returned probability vectors and does not establish an efficient exact sampler on arbitrary response trees.Source: §A.6 · p. 29

B EXTENSIONS AND LIMITS

  • The optimality guarantees apply to selectors returning one of M iid complete candidates from a fixed proposal, excluding adaptive proposals and prefix-level search.They are worst-case or uniform guarantees, not claims that MH is best on each instance.Source: B EXTENSIONS AND LIMITS · p. 29

B.1 MULTIPLE-TRY AND I-SIR SCHEDULES

  • For the specified fixed schedules, proposal-initialized MH is no farther from the target than schedules using multiple-try or iterated-SIR blocks under every convex f-divergence.The schedule allows i-SIR as the first block and in at most one later block.Source: §B.1 · pp. 30–31

B.2 EXACT MINIMAX TOTAL VARIATION

  • Proposal-initialized MH attains the exact minimax total-variation value without knowing ε, Z, or the maximum weight.The result also holds when the instance class is restricted to products of two equally weighted specialists on two-token trees.Source: §B.2 · p. 31
  • For ε < 1, no finite candidate budget gives a uniform forward-KL bound over the stated instance class, even with full target knowledge.The limitation follows from candidate coverage: selectors cannot return responses absent from the pool.Source: §B.2 · p. 32

B.3 THE ERROR EXPONENT WITH RECORDED-CANDIDATE INFORMATION

The analysis establishes a worst-case error exponent for selectors using recorded candidate information, then characterizes the limits of weight-only alternatives to MH. Its guarantees depend on the information available to the selector and do not imply MH is best on every individual instance.

B.3 THE ERROR EXPONENT WITH RECORDED-CANDIDATE INFORMATION

  • For every fixed M, minimax error is ΘM(|δ|^4M) as two equally weighted policies approach agreement; no allowed selector uniformly improves that exponent.The lower bound applies to selectors without access to the normalizer or unobserved weights; the family uses a fixed two-token tree.Source: §B.3 · p. 32
  • The exponent result is worst-case, not instancewise: squared-weight selection beats MH on a two-class, two-candidate example in both KL directions and TV.The example has target high-weight mass 2/3, MH mass 5/8, and squared-weight selection mass 13/20.Source: §B.3 · p. 34

B.4 ADMISSIBILITY AMONG WEIGHT-ONLY SELECTORS

  • For weight-only selectors, matching MH’s TV guarantee up to a fixed constant on every finite positive instance forces the selector to equal MH everywhere.The result also yields uniqueness when attaining the minimax TV value at every overlap level; domination in TV or either KL or chi-square direction likewise forces equality.Source: §B.4 · pp. 34–35
  • Any weight-only rule that improves on MH on one instance must be worse on another, though restricted families can allow better worst-case constants.This admissibility result does not establish uniqueness at one overlap level or admissibility for every convex divergence.Source: §B.4 · p. 35

B.5 A BARRIER TO CERTIFYING THE REMAINING ERROR

These sections examine certification limits, proposal modifications, specialist approximation, and enumerable experiments. They show where guarantees hold, where they do not, and how sampler error changes across budgets and objectives.

B.5 A BARRIER TO CERTIFYING THE REMAINING ERROR

  • A rollout-only certifier cannot always give a tight upper bound on remaining TV: with Z = 0.01, N = 50, M = 17, and α = 0.05, it must report at least 0.33 with probability at least 0.45 even when actual TV is zero.The barrier also holds for some instances when the certifier knows the proposal and full support.Source: §B.5 · pp. 35–36

B.6 CONTINUATION-GUIDED PROPOSALS

  • A continuation-mass twist changes candidate generation, and the finite-budget guarantees apply by comparing MH and SIR under that same twisted proposal.A certificate based on twisted weights bounds improvement over the twisted proposal, not the original one; a poor twist can move the proposal farther from the target.Source: §B.6 · pp. 36–37

B.7.1 STABILITY UNDER COVERAGE

  • Coverage-based stability needs no bounded-residual assumption, but its constants depend on supplied policies and cannot be certified from finite-sample maximum ratios.The bound controls mismatch between the supplied-policy product target and the exact-optimum target; their KL errors cannot simply be added because the residual shift also matters.Source: §B.7.1 · p. 37

B.7.2 INSUFFICIENCY OF SPECIALIST REGRET ALONE

  • Small specialist regrets alone do not ensure bounded external regret: for every ε > 0, a rule can have unbounded external regret despite specialist regrets at most ε.The construction’s reward ranges grow, and the stated coverage condition prevents this amplification.Source: §B.7.2 · pp. 37–38

B.7.3 POSSIBLE DETERIORATION OF THE EXTERNAL OBJECTIVE

  • In the constructed example, each additional MH candidate increases external regret while consensus KL decreases toward zero, so the two objectives can move in opposite directions.Both local decoders are uniform over responses, but their recorded weights are swapped between branches.Source: §B.7.3 · pp. 38–39

C.1 EXACT COMPUTATION IN WEIGHT SPACE

  • Exact sequence-level divergences can be evaluated in weight space when each iterate preserves the proposal’s conditional response law at each weight; the reduction is not assumed for SMC or replica exchange.Empirical-distribution evaluation depends on weight-distribution coverage, including rare weights, and fitting error can bias plug-in objectives.Source: §C.1 · pp. 39–40

C.2 EXACT LAWS AND NEARBY-POLICY RATES

  • 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 configurations.With greedy initialization, after 8 updates mean KL is below 0.012 in every configuration and below 10^-4 in base, flat, and short; expected reward need not increase along the regularized-objective trajectory.Source: §C.2 · pp. 40–41, §C.3 · p. 41

C.3 REWARD–DIVERGENCE VIEW

  • For the T = 10 reward–divergence comparison, both MH initializations approach the correction target, but expected reward itself need not increase.The target is the point at regularization strength λ = 1.Source: §C.3 · p. 41

C.4 MATCHED-BUDGET SAMPLERS AND METRIC

This section compares matched-budget samplers using binned total variation and examines sensitivity to instances and budgets. MH has lower binned TV than ordinary SIR across all 23 tested instances, while comparisons with structured samplers vary.

Maximum-log-normalizer selection

  • Selecting the maximum correction weight need not approximate the target: this baseline is farther from the target than the local decoder in base and long instances.The max-log-weight baseline selects on correction weight, not reward.Source: §C.4 · p. 43

Binned total variation

  • Binned total variation uses bins formed by target-probability thresholds over responses sorted by correction weight, and lower-bounds full-response TV.Bins need not have equal mass, and combining weights can lose information.Source: §C.4 · p. 43

Binned divergence ordering

  • The binned MH-to-target ratios remain nonincreasing, yielding a population divergence ordering for every convex generator, but not an ordering of individual Monte Carlo estimates.The argument applies to consecutive bins formed by grouping response weights.Source: §C.4 · p. 43

Sensitivity to instance and budget

  • MH has lower binned TV than ordinary SIR on all 23 instances at budget 9, with all stored pointwise 95% Monte Carlo intervals excluding zero.The sensitivity sweep covers 10 base, 10 peaky, and 3 long instances.Source: §C.4 · p. 43
  • MH has the smallest point estimate among structured comparators on 17 of 23 instances; adaptive SMC is 0.0145 TV lower on one peaky instance.On one base instance, the apparent same-space-exchange advantage remains unresolved after extending evaluation to 106 runs per batch.Source: §C.4 · p. 43
  • MH remains below ordinary SIR at budgets 18 and 36, but at budget 36 its discrepancies from replica exchange are close to the exact-target sampling diagnostic.The empirical metric therefore provides little separation between MH and replica exchange at budget 36.Source: §C.4 · p. 43

D.1 GSM8K CERTIFICATE EVALUATION

The GSM8K certificate evaluation composes fixed accuracy and brevity specialists and uses grouped candidate pools to bound improvement over local decoding. Output-level replay also measures serving latency, while separate specialist checks and evaluation assumptions delimit what those results establish.

D.1 GSM8K CERTIFICATE EVALUATION

  • The certificate bound applies to fresh proposal pools for the fixed test prompts and checkpoints, not to a prompt population or the MH–SIR difference.Groups are assumed independent conditional on the fixed prompts and checkpoints; both samplers share the same lower bound.Source: §D.1 · p. 45
  • Positive certificate lower bounds establish improvement over local decoding without estimating either corrected sampler’s marginal output probabilities.At M = 9, clipping affects 0.038%, 0.597%, and 0.265% of groups as the accuracy weight increases.Source: §D.1 · p. 45, Table 3 · p. 46
  • Fitted output-density-ratio estimates were excluded because controlled finite-state tests failed prespecified bias and coverage thresholds.The evaluation instead uses a fitting-free endpoint.Source: §D.1 · p. 45
  • The separate specialist check found the accuracy adapter at 86.875% accuracy and 390.77 tokens, versus 85.425% and 250.95 tokens for the brevity adapter.These measurements use a different prompt set and decoding settings and characterize the supplied specialists, not the full-vocabulary FP32 composition study.Source: §D.1 · p. 45

D.2 GSM8K OUTPUT-LEVEL REPLAY AND COST

  • On one H200, mean latency rises 16–20% at M = 3 and 29–35% at M = 9 relative to M = 1.These are latency measurements for one-prompt batches, not throughput estimates.Source: §D.2 · p. 46

E.1 HH-RLHF CERTIFICATE EVALUATION

The HH-RLHF evaluation composes helpfulness- and harmlessness-specialized adapters and reports certificates, output-level measurements, and serving costs. A separate enumerable continuation-tree experiment evaluates sampler output laws directly, but its restricted-policy objective is not established as the original task-reward objective.

E.1 HH-RLHF CERTIFICATE EVALUATION

  • The HH-RLHF specialists were trained separately, and their reward-model scores are proxies for response quality and safety rather than human judgments.On a confirmation split, the helpfulness specialist exceeded the harmlessness specialist by 0.607 in helpfulness score, while the reverse difference in harmlessness score was 0.629.Source: §E.1 · p. 49
  • The HH-RLHF certificate uses a separately scoped family of 48 comparisons, with a 10-nat clipping cap and no clipped certificate values.The corresponding table reports two endpoints.Source: §E.1 · p. 49, Table 7 · p. 50

E.2 HH-RLHF OUTPUT-LEVEL REPLAY AND COST

  • At M = 17, MH responses are 6–10 tokens shorter on average than local decoding, but this does not establish that shorter length causes reward-score changes.Source: §E.2 · p. 49

F TRAINED LLM CONTINUATION-TREE EXPERIMENT

  • The enumerable experiment compares MH and SIR consensus objectives on restricted continuation policies, making the target and both output laws directly evaluable.Its quantities concern the restricted continuation policies, not the full-response policies.Source: F TRAINED LLM CONTINUATION-TREE… · p. 52

F.1 POLICIES, QUESTIONS, AND CONTINUATION TREES

  • The continuation trees expand the reference model’s top 8 tokens through four additional tokens, yielding 4,096 leaves per context without early EOS.The shared token mask changes adapter sequence distributions, so the restricted target generally differs from the full-vocabulary product target conditioned on staying in the tree.Source: §F.1 · p. 52

F.2 FULL OUTPUT LAWS AND NUMERICAL VALIDATION

  • The study computes full output laws and KL gains directly, but DPO training alone does not show that the restricted consensus objective equals the original task-reward objective.Enumeration removes sampling and density-estimation error from conditional KL calculations, while floating-point and quadrature error remain and the checks are not rigorous error bounds.Source: §F.2 · p. 53

F.3 RESULTS, CERTIFICATES, AND UNCERTAINTY

At M = 9, MH had positive mean objective gaps over SIR in all six primary settings, with additional sensitivity checks and a same-operator reproducibility check. The results concern short, restricted policies and do not establish a large practical advantage or an unobserved full-response MH–SIR gap.

F.3 RESULTS, CERTIFICATES, AND UNCERTAINTY

  • Bootstrap intervals describe variation across questions and exclude model-inference uncertainty.Questions were resampled as whole units, keeping contexts, weights, budgets, and sensitivity settings together.Source: §F.3 · p. 53
  • At M = 9, all six primary mean objective gaps favored MH over SIR with positive pointwise bootstrap intervals, though gaps were small and varied substantially across questions.For original contexts at w1 = 0.25 and 0.5, the largest single-question gap contributed about 98% of the total; midpoint-context mean MH KL was below the 10−10-nat reporting resolution.Source: §F.3 · p. 53
  • The estimated mean certificate was approximately 75–90% of MH’s mean gain at M = 9, and its expectation is a theoretical lower bound on both gains.The reported sample mean is not a certified lower confidence bound.Source: §F.3 · p. 53

F.4 HORIZON AND TOKEN-MASK SENSITIVITY

  • Across horizon and token-mask sensitivity settings, all 24 M = 9 mean consensus-advantage intervals excluded zero, although many individual gaps remained unresolved.The 2-to-4-token sweep is a sensitivity check, not a test of the long-response asymptotic theorem.Source: Table 13 · p. 55, §F.4 · p. 55
  • High proposal-weighted retained mass does not establish equivalence to unrestricted generation; one original-context top-8 prefix retained only 3.61 × 10−6 brevity mass.Retained mass summarizes the restriction and may be low at rare prefixes.Source: §F.4 · p. 55

F.5 COMPUTE AND REPRODUCTION

  • A fresh CPU replay reproduced all 1,320 cases and summaries with no differences among 176,477 compared numerical fields, but this was not an independent replication.It was a same-operator reproducibility check.Source: §F.5 · p. 56
  • The study measures direct consensus-objective differences on short, restricted policies; it does not establish a large practical advantage, improved task rewards, or the full-response MH–SIR objective gap.The full-response gap was unobserved in this study.Source: §F.5 · p. 56
Loading 2610.03480v1…