acceptodds
Under review as a conference paper at ICLR 2027

Metropolis-Hastings Dominates Importance Resampling for Policy Composition

Abstract

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.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
large language models, multi-objective alignment, decoding-time policy composition, Metropolis–Hastings, sampling-importance-resampling, finite-budget guarantees

Reviews

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

The paper provides a theoretical analysis showing that Metropolis–Hastings (MH) correction outperforms sampling-importance-resampling (SIR) in decoding-time policy composition. Specifically, the theory shows that at every rollout budget, MH induces a distribution at least as close to the target as SIR under every convex f-divergence. The authors then provide a lower bound on the improvement over the uncorrected model, computable from recorded rollout weights. Two special regimes are also discussed. When policies are close, MH’s error decays at a much higher order than SIR’s. For long responses, both methods are equally limited and require exponentially many rollouts.

Critical strengths
  1. The paper builds strong, comprehensive theoretical results for fundamental algorithms in the field, which hold for every finite budget and every convex f-divergence. The proof of the main theorem is short and insightful. It represents MH on an iid pool as priority sampling and couples it with SIR viewed as an exponential race on the same randomness. This tool is novel in my opinion.

  2. The paper provided an improvement certificate that is practically implementable. It is computable from quantities recorded during generation and comes with valid simultaneous confidence bounds.

Critical weaknesses

No major weakness. Besides, I would hope the presentation of the plots to be improved. Figures like figure 1,3 contain too many raw text over the plots and sometimes with too large marker, which can make readers hard to understand.

Questions for authors

The paper suggests MH should be preferred over ordinary SIR whenever a single sample is drawn from a proposal-initialized pool. However, the empirical gap reported between the two seems to be small, and moving closer to the target does not always improve task metrics (e.g., the HH-RLHF helpfulness drop). Could the authors give practitioners guidance on when the correction is worth its M-fold generation cost? For instance, could the recorded weights ρ_w (their spread across the pool or the pool’s effective sample size) indicate whether an instance is in the near-agreement regime, where MH’s advantage is substantial, or in the coverage-limited regime, where neither method helps much? I believe this can help improve the paper.

1 comment
AuthorsOpenReview ↗

Response to Reviewer mfsR

Thank you for the supportive review! We’ve added guidance on choosing the sampling budget, as you suggested.

We have also simplified the labels and reduced marker overlap in Figures 1 and 3.

(a) When is the correction worth the MM-fold generation cost? By Proposition 1, correction cannot decrease the consensus objective. The same holds for the KL-regularized weighted reward objective if each specialist exactly optimizes its own objective with the same reference policy and KL coefficient. However, this does not guarantee an increase in the raw weighted reward or any individual reward. On HH-RLHF at M=17M=17, for example, correction raises harmlessness and lowers helpfulness relative to local decoding.

For practitioners, we recommend taking a few fixed candidate budgets and measuring task performance, the GMG_M confidence bound, and generation cost on validation prompts, then checking the chosen budget on fresh pools. On GSM8K, M=3M=3 improves accuracy over local decoding by 0.8–1.2 percentage points and reduces response length by 11–26 tokens. In our H200 profile on 16 prompts, batching 3 candidates increased mean latency by 16–20%, while total generated tokens roughly tripled. We suggest starting with a small fixed budget and increasing it only if validation gains justify the extra generation cost.

(b) If doing the correction, when should MH be preferred over SIR? For the same number of proposal rollouts MM, MH approximates the target at least as well as SIR (Theorem 1), with no extra model evaluations. Our recommendation is therefore to prefer MH over SIR when the goal is fidelity to the composed policy. In the exact settings where both methods reach TV error 0.01 within 129 candidates, SIR needs 2–5 times as many candidates as MH (Appendix C.2).

(c) Diagnostics based on ρ\rho. Yes, small pools give a useful indication of weight spread in these experiments. Following your suggestion, we compared the log-weight spread estimated from 5 responses with the spread in 119 independent responses. Across prompts, the Spearman correlations are 0.73 on GSM8K and 0.88 on HH-RLHF.

In our controlled study with a known target, larger log-weight spread generally requires more candidates. Holding log-weight variance fixed keeps the required budgets nearly constant as length grows from 32 to 512 tokens (Appendix C.2). For LLM-scale responses, the small-pool statistics describe observed spread but cannot establish target coverage or determine the required budget on their own (Appendix G.2).

For improvement over the uncorrected distribution qq, a useful statistic is GMG_M, whose expectation lower-bounds the consensus gain (Proposition 1). Sections 4.3 and 4.4 report confidence bounds computed from its mean across independent pools. We have also derived a confidence interval on MH's mean KL advantage over SIR from the recorded rollout weights (please see the new Corollary 1 and Appendix G.1). Section 4.5 now reports these intervals for our full LLM experiments.

Please let us know if you have any follow-up questions or comments.

Reviewer_L1s6OpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies policy composition at inference time, where combining token probabilities introduces bias relative to the target distribution over complete responses. The authors analyze an existing Metropolis–Hastings correction method and prove that, under the same sampling budget, it produces a distribution closer to the target than standard importance resampling under every convex f-divergence. They also derive a lower bound on the improvement in the objective and analyze how sampling error depends on differences between policies and response length. Experiments on synthetic problems and LLM benchmarks support the theoretical results, although the two methods perform similarly on practical tasks.

Critical strengths
  1. The paper’s main contribution is Theorem 1, which establishes that, under the same rollout budget, the divergence between the MH output distribution and the target is no greater than that of standard SIR for every convex f-divergence. This result holds for any finite sampling budget, rather than only asymptotically, providing a clear theoretical justification for choosing MH in policy composition.

  2. The paper also analyzes the order of sampling error when policies are close, candidate coverage limitations for long responses, and a lower bound on objective improvement that can be computed from sampling weights. Together, these results provide a comprehensive characterization of the method’s advantages and limitations.

Critical weaknesses

W1. The theoretical advantage in distribution approximation does not translate into clear downstream gains in the full LLM experiments. The accuracy gap on GSM8K is at most 0.14 percentage points, and the weighted rewards on HH-RLHF do not show a consistent advantage. The current results therefore leave unclear when more accurate approximation of the target distribution provides substantial practical value.

W2. Direct validation of the central theoretical result is largely limited to synthetic problems and short, restricted LLM continuation trees. For complete responses, the authors primarily use an improvement certificate shared by both methods to assess their gains over local decoding, rather than directly measuring the distributional advantage of MH over SIR. Consequently, the magnitude of this advantage in realistic generation of long responses, and how it changes with the sampling budget, remain insufficiently characterized.

Questions for authors

Q1. MH and SIR achieve very similar task performance on GSM8K and HH-RLHF. Could the authors further investigate under what degrees of policy disagreement or task conditions the more accurate distribution approximation of MH produces meaningful downstream gains? This would help clarify the practical significance of the theoretical result.

Q2. Theorem 3 analyzes candidate coverage limitations for long responses, but direct comparisons of distributional divergence in the LLM experiments mainly use short continuation trees. Could the authors systematically vary sequence length and policy disagreement in settings where the target distribution can be computed exactly, comparing the distributional errors of MH and SIR and the candidate budgets required to reach the same error level?

Q3. MH outperforms SMC and replica exchange in most synthetic settings, but adaptive SMC performs better in some settings with sharply peaked distributions. Could the authors explain which distributional properties or sampling conditions determine their relative performance? Since sampling costs may differ across methods, comparisons under the same computational budget would also help clarify their respective strengths and limitations.

3 comments
AuthorsOpenReview ↗

Response to Reviewer L1s6 (Part 1/2): practical significance and complete responses

Thank you for taking the time to review our paper!

We recommend MH for correcting local product decoding: it approximates the target at least as well as SIR at the same candidate budget, with no extra model evaluations (Theorem 1). In the tested exact settings where both methods reach TV error 0.01 within 129 candidates, SIR needs 2–5 times as many candidates as MH (Q2).

Downstream metric gains (W1, Q1). We agree that task-score differences between MH and SIR remain small in our LLM policy-composition experiments. A closer match to the target need not raise a task score. Even with exact specialists, the reward objective includes a KL penalty and the raw weighted reward does not need to increase with the objective (nor does any individual reward).

The effect of choosing MH over SIR on a downstream metric depends on how that metric varies with specialist agreement along the rollout, measured by the weight ρ\rho. Both samplers have the same response distribution conditional on the selected weight. For each prompt and task metric gg, let mg(r)=Eq[g(Y)∣ρ=r]m_g(r)=\mathbb E_q[g(Y)\mid\rho=r]. Since MH selects stochastically larger weights than SIR, EHMg(Y)≥ESMg(Y)\mathbb E_{H_M}g(Y)\ge\mathbb E_{S_M}g(Y) whenever the mean score mg(r)m_g(r) does not decrease as rr increases.

On GSM8K, 79–94% of the pools contain only correct or only incorrect answers. Measured by the conditional TV between MH's and SIR's selection probabilities within each pool, 74–97% of the MH–SIR selection difference lies in these all-correct or all-incorrect pools (Appendix G.2). Choosing a different response there cannot change accuracy.

In addition to GSM8K, we have now evaluated MH and SIR on MATH, where responses are longer and more pools contain both correct and incorrect answers. Accuracy again differs little between MH and SIR, consistent with the stronger observed correlation of log⁡ρ\log\rho with brevity than with correctness within problems. On 100 reserved problems, we tested rw=w11correct−(1−w1)L/1024r_w=w_1\mathbf{1}\\{\mathrm{correct}\\}-(1-w_1)L/1024, where LL is the response length in tokens and −L/1024-L/1024 is the brevity score used in training. We chose the score and the setting w1=0.5w_1=0.5, M=5M=5 using results from the first 100 problems, before any result on the reserved set was available. On the reserved set, MH improves the score over SIR by 0.00305, with a 95% paired bootstrap interval of [0.00227, 0.00388]. MH's responses are about 6 tokens shorter than SIR's on average, which accounts for 95% of this score gain (Appendix G.3).

Both MH and SIR also improve on local decoding: at M=3M=3–1717 on GSM8K, accuracy rises by 0.8–1.3 percentage points and responses are 11–42 tokens shorter.

To check what happens when the score determines the selection weights, we changed the target on the HH-RLHF candidate pools to qeR/τq e^{R/\tau}, giving weight eR/τe^{R/\tau}, where RR is the weighted reward-model score. At τ=1\tau=1, MH's gain in this score over local decoding is 15–35% larger than SIR's. The absolute MH–SIR score difference is 0.014–0.037 logits (Appendix G.2).

A direct comparison on complete responses (W2). The original GMG_M certificate compared each sampler with local decoding. The newly added Corollary 1 bounds MH's KL advantage over SIR, ΔM=KL(SM∣p)−KL(HM∣p)\Delta_M=\mathrm{KL}(S_M\\|p)-\mathrm{KL}(H_M\\|p), from recorded weights without estimating ZZ: KL(SM∣HM)≤ΔM≤aM−KL(HM∣SM),\mathrm{KL}(S_M\\|H_M)\le\Delta_M\le a_M-\mathrm{KL}(H_M\\|S_M), where aM=EHMlog⁡ρ−ESMlog⁡ρa_M=\mathbb E_{H_M}\log\rho-\mathbb E_{S_M}\log\rho. A concentration argument then gives a confidence interval for the mean MH–SIR gap, addressing W2's concern about the shared certificate. Its lower bound is conservative because we apply Pinsker's inequality to a single event. For each prompt, the event is that the selected response's log weight is at or above the 75th percentile of log weights in independent pilot samples.

We now report these confidence intervals for complete GSM8K and HH-RLHF responses in Section 4.5. The reported intervals are conditional on the prompts, checkpoints, and pilot samples. They cover the mean KL advantage over these prompts jointly at 95% confidence across all 30 settings. Every lower bound is positive. Table 1 gives the intervals for w1=0.5w_1=0.5:

MMGSM8K KL bounds (nats)HH-RLHF KL bounds (nats)
2[0.00013, 0.0630][0.00034, 0.0451]
3[0.00062, 0.0922][0.00070, 0.0585]
5[0.00154, 0.1212][0.00079, 0.0654]
9[0.00159, 0.1370][0.00049, 0.0650]
17[0.00079, 0.1412][0.00018, 0.0590]

In addition to the intervals, we report a distributional diagnostic based on the pilot-threshold event defined above. MH's mean absolute error in this event's probability relative to the target is estimated to be 1.2–4.1 percentage points smaller than SIR's across the 30 settings. This reduction is largest at M=5M=5 or 99 on GSM8K and at M=3M=3 or 55 on HH-RLHF, depending on w1w_1 (Appendix G.1).

Part 2 addresses policy disagreement, candidate budgets, and SMC (Q2, Q3).

AuthorsOpenReview ↗

Response to Reviewer L1s6 (Part 2/2): candidate budgets and SMC

Candidate savings at a specified error (Q2). To answer this question, we conducted additional comparisons in a setting where the target is known exactly (Appendix C.2 and the end of Appendix A.6 give the construction). The specialist policy agreement was controlled by a parameter δ∈0.5,1,1.5\delta\in\\{0.5,1,1.5\\} with smaller values corresponding to more agreement. We also varied the response length T∈2,8,32,128,512T\in\\{2,8,32,128,512\\}. We evaluated every candidate budget through 129 and a selection of larger budgets up to 1,025.

In the 10 settings that reach TV error 0.01 within 129 candidates, SIR needs 2–5 times as many candidates as MH, with a median ratio of 4.1. Selected results are given in the table below, where σ\sigma denotes the proposal standard deviation of log⁡ρ\log\rho.

TV errors below use M=9M=9. Minimum candidate budgets are for TV ≤0.01\le0.01.

TTδ\deltaσ\sigma MH TVSIR TV MH budgetSIR budget
320.50.240.000030.01124311
3210.850.028400.067861669
5120.50.960.041500.081472190
51213.390.784980.78696>129>129>129>129

Within this family, larger log-weight spread generally requires more candidates. At M=9M=9, MH has lower TV in all 15 settings. In 5 settings, neither method reaches the tolerance within 129 candidates. In the last row, both methods have TV errors close to the coverage lower bound of 0.7806, which applies to any rule selecting among 9 independent candidates.

In a separate control with log-weight variance held fixed, the budgets for KL ≤0.01\le0.01 stay at 10–11 for MH and 17–19 for SIR as length grows from 32 to 512. For TV ≤0.01\le0.01, the corresponding budgets stay at 21–25 and 94–106. The ratio of SIR to MH budgets depends on the error criterion: here it is below 2 for KL and above 4 for TV. These patterns describe this structured family and do not calibrate budgets for LLMs in general. Table 3 in Appendix C.2 gives all 15 grid settings. The appendix also describes the fixed-variance control, with complete budget curves in the code release.

SMC and other samplers at matched cost (Q3). SMC can use informative weights to redirect generation while responses are still being built. Our results show that both the timing of this information and the coverage of complete-response proposals can matter.

We tested the timing effect in a separate instance of the construction used for Q2, permuting token order in both proposal and target so that information about policy agreement becomes available later. The joint distributions are preserved up to that permutation. MH and SIR errors are unchanged, but SMC goes from outperforming MH to performing worse. Each method uses 126 conditional-policy evaluations per output:

MethodEarly information: TVDelayed information: TV
MH, exact0.1580.158
SIR, quadrature0.1970.197
Adaptive SMC, estimated0.1110.209

The SMC results are means over 8 batches, with standard deviations about 0.002. This shows that the timing of informative weights can determine whether adaptive SMC beats MH at matched evaluation cost (Appendix C.4).

As for coverage, the one instance where adaptive SMC clearly outperforms MH in the original study of 23 instances also has a high error floor for selectors of 9 iid complete proposals. More specifically, t9=∑y[p(y)−9q(y)]+t_9=\sum_y[p(y)-9q(y)]_+ lower-bounds the full-response TV error of any rule that returns one of 9 iid proposals from qq, including MH and SIR. SMC resamples prefixes and is not restricted to such a pool. The bound equals 0.2744 on that instance and is at most 0.0112 on the other 22. Because there is only one such instance and the bound concerns full-response TV while the empirical comparison uses binned TV, we report this association as descriptive (Appendix C.4).

The original comparisons match MH, SIR, SMC, and replica exchange at 9T9T conditional-policy evaluations per output (Section 4.1 and Appendix C.4).

Please let us know if you have any further questions or comments. If our responses and revisions address your concerns, we would appreciate it if you could reconsider your rating.

Thank you for your thoughtful response. I appreciate the clarifications and will raise my score to 3.

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

The paper studies decoding-time composition of reward-specific language model policies, where the target is a globally normalized geometric mixture of the policies (probabilities). Building on an existing Metropolis-Hastings (MH) correction, the authors prove that MH dominates ordinary sampling-importance-resampling (SIR) under every convex ff-divergence at any fixed candidate budget. They further characterize the sampling error in near-agreement and long-response regimes, and provide theoretical guarantees on the improvement in the consensus objective. The theoretical results are supported by numerical and LLM experiments.

Critical strengths

The paper addresses a well-motivated problem with a clear and mathematically strong contribution. In particular, the finite-budget dominance result (Theorem 1) is remarkably general. I also appreciate the complementary analyses in Theorems 2 and 3, which characterize both the advantages and fundamental limitations of MH correction.

The paper is very well written, with a clear motivation, coherent theoretical development, and careful empirical validation. I especially appreciate that the authors distinguish improvements in distributional fidelity from improvements in task-level performance.

Critical weaknesses

My main reservation concerns the practical significance of the theoretical advantage. The full-response LLM experiments show little distinction between MH and SIR in task-level performance, while direct divergence comparisons are restricted to smaller settings. However, the authors acknowledge this limitation, and I do not consider it a major weakness given the theoretical nature and clean and well thought-out theoretical contribution.

While the paper is well written, I found some parts of the main text rather terse. I encourage the authors to improve the readability by expanding a few explanations in the camera-ready version. A few minor suggestions on presentation:

  1. (Definition of SIR): It would be helpful to introduce SIR more explicitly alongside MH in Section 2, rather than deferring its formal definition to Section 3.
  2. (Example 1): I found the example somewhat difficult to follow, particularly because it is not immediately clear which quantities are specified as part of the setup (e.g., the composition weights and component-policy probabilities) and which are derived from the local and global composition rules. Explicitly separating these quantities and showing the intermediate calculations would make the example more instructive. Also, the notion of "continuation product mass" could be explained more explicitly, as it is central to understanding the discrepancy between local and global composition.
  3. (Optimization interpretation (Eq. 7)): The discussion could more clearly distinguish the consensus objective, which applies to arbitrary component policies, from the external reward objective, which requires exact specialist optimality. In particular, "in either setting" is somewhat ambiguous following the discussion of approximately optimal specialists.
Questions for authors

I do not have any substantive questions about the paper.

1 comment
AuthorsOpenReview ↗

Response to Reviewer RD72

Thank you very much for the review and the helpful suggestions on presentation. We have incorporated all three suggestions in the revised version of the manuscript.

  • Definition of SIR. We now define SIR's selection rule next to MH in Section 2.
  • Example 1. We have reworked both the text of the example and the associated picture. We now distinguish the supplied policy probabilities and composition weights from the derived quantities more clearly. The continuation product mass is now defined explicitly within the text of the example and the intermediate calculations are presented with more detail.
  • Optimization interpretation (Eq. 7). The wording around Eq. 7 now makes a clearer distinction between the consensus and the external reward objective, as well as the case of approximate specialists.

We have also added inequalities relating MH's and SIR's quality of approximation in Corollary 1 and report confidence intervals on the advantage of MH over SIR in Section 4.5 (Table 1). That section also elaborates on the connection to task scores. The proof of Corollary 1 and the derivation of the confidence intervals for the approximation quality difference between MH and SIR can be found in Appendix G.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of the revision

We have revised the paper to compare MH and SIR more directly at the same generation budget, and to better explain when MH's distributional advantage does (and does not) translate into better task performance. The main changes are:

  • Direct comparison on complete responses (L1s6 W2, Sections 3.2 and 4.5, Appendix G.1). Our original bound compared both methods with local decoding. Corollary 1 now bounds MH's KL advantage over SIR, providing the direct comparison on complete responses requested in W2. This is also MH's advantage in the consensus objective. We derive simultaneous confidence intervals from recorded rollout weights, with positive lower bounds in all 30 task, weight, and budget settings at joint 95% confidence. Table 1 reports all five budgets at w1=0.5w_1=0.5.

  • Candidate budgets and sampler comparisons (L1s6 Q2, Q3, Section 4.1, Appendices C.2 and C.4). We compare MH and SIR across 15 settings with an exactly known target, varying response length (up to 512 tokens) and policy disagreement. Where both methods reach TV error ≤0.01\le0.01 within 129 candidates, SIR needs 2–5 times as many candidates as MH. When we hold log-weight variance fixed, the required budgets stay nearly constant as response length increases within this family. We also add a matched-cost experiment showing that delaying informative weights can reverse adaptive SMC's advantage over MH.

  • Task metrics and practical guidance (L1s6 W1/Q1 and mfsR, Section 4.5, Appendices G.2 and G.3). We derive a sufficient condition for MH to match or improve on SIR's expected task score. On GSM8K, 79–94% of candidate pools contain either only correct or only incorrect answers, leaving little room for either sampler to change accuracy. On 100 reserved MATH problems, MH gives a modest improvement over SIR on an accuracy-and-brevity score chosen before evaluating those problems, mostly by selecting shorter responses. We also test a reward-tilted target and add weight-spread diagnostics. For choosing a budget, we recommend evaluating consensus gain, task performance, and generation cost together.

  • Presentation (Section 2, Figures 1 and 3). Following RD72's suggestions, we now introduce SIR alongside MH, separate given and derived quantities in Example 1, and clarify the assumptions behind Eq. (7). We also simplified labels and reduced clutter in Figures 1 and 3, as mfsR suggested.

Please see our responses to each reviewer’s comments in the respective threads below.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.