Metropolis-Hastings Dominates Importance Resampling for Policy Composition

Alexey Kurennoy; Ramil Yarullin; Fergal Reid

cs.LGOct 2, 2026

Metropolis-Hastings Dominates Importance Resampling for Policy Composition

Authors: Alexey Kurennoy, Ramil Yarullin, Fergal Reid

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.

Figures & tables

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

q_{w}

by the recorded normalizers

\rho_{w}

recovers the uniform target. Right: exact KL to the target for MH and ordinary SIR on the same four-response toy example.

Figure 2: Exact sampling error on enumerable problems. Left: mean KL in five enumerable settings (values

\leq 10^{-12}

omitted). Right: the nearby-policy rates of Theorem 2 . As

\delta\to 0

, the KL of MH decays as

\delta^{4M}

, whereas ordinary SIR keeps the

\delta^{4}

order of

q_{\delta}

(dotted reference slopes). Solid lines with filled markers show MH, and dashed lines with open markers show ordinary SIR.

Figure 3: Certified consensus gains and task-level effects on GSM8K (top) and HH-RLHF (bottom). Left: mean

G_{M}

and simultaneous 95% lower bounds within each study, conditional on the prompts and checkpoints;

G_{M}

depends only on the candidate pool, so it certifies both MH and ordinary SIR. Middle: MH trade-offs at

M\in\{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.

Appendix figures & tables17 assets

Supplementary material from the paper’s appendix.

Appendix

			MH updates $n$ (budget $M=n+1$ )
Configuration	$\alpha$	$T$	$0$	$1$	$2$	$3$	$5$	$8$
Base	0.5	6	$0.154$	$0.022$	$0.0055$	$0.0018$	$0.0003$	$<\!10^{-4}$
			$\pm 0.056$	$\pm 0.015$	$\pm 0.005$	$\pm 0.002$	$\pm 0.0004$
Peaky	0.2	6	$0.603$	$0.181$	$0.084$	$0.048$	$0.021$	$0.0089$
			$\pm 0.405$	$\pm 0.181$	$\pm 0.098$	$\pm 0.061$	$\pm 0.032$	$\pm 0.018$
Flat	1.0	6	$0.034$	$0.0017$	$0.0002$	$<\!10^{-4}$	$<\!10^{-4}$	$<\!10^{-4}$

Appendix

Table 1: Exact

\mathrm{KL}(\mu_{n}\|\widehat{p}_{w})

in nats after

n

MH updates, initialized from

q_{w}

, with total candidate budget

M=n+1

. Entries are means over 20 policy configurations (10 at

T=10

); standard deviations appear beneath.

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.

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,

\mathbb{E}_{\mu}\mathcal{R}_{w}-\mathbb{E}_{\pi_{\mathrm{ref}}}\mathcal{R}_{w}

. Curves average 10 policy draws; trajectory markers show initialization (

n=0

) and 6 MH updates.

Method	Base		Peaky		Long
Estimated binned TV
$q_{w}$ (1 rollout)	237.765 $\pm$	0.509	515.610 $\pm$	0.438	302.427 $\pm$	0.483
MH	2.506 $\pm$	0.254	37.762 $\pm$	0.234	7.596 $\pm$	0.217
Ordinary SIR	30.097 $\pm$	0.662	86.999 $\pm$	0.639	42.918 $\pm$	0.450
SMC, adaptive resampling	30.064 $\pm$	0.435	73.574 $\pm$	0.481	43.051 $\pm$	0.349
SMC, resampling every step	52.170 $\pm$	0.214	106.350 $\pm$	0.501	68.462 $\pm$	0.512

Appendix

Table 2: Matched-budget comparison in units of

10^{-3}

TV. Sampled rows give the mean

\pm

across-batch standard deviation of the binned TV over 8 batches of

10^{6}

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.

$w_{1}$	Mean $G_{M}$	Lower bound	Clipped	Mean $G_{M}$	Lower bound	Clipped	$n=8$	$n=16$
	$M=9$			$M=17$			MH acceptance (%)
0.25	0.868	0.674	0.038	0.937	0.742	0.038	53.92	50.53
0.50	1.700	1.494	0.597	1.848	1.644	0.663	46.10	41.14
0.75	1.413	1.216	0.265	1.528	1.330	0.256	49.61	45.09

Appendix

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.

$M$	Total tokens	Method	Accuracy (%)	95% CI	Length	95% CI
Accuracy weight $w_{1}=0.25$
1	259.6	Local decoder ( $q_{w}$ )	88.50	[86.99, 89.93]	259.6	[254.1, 265.3]
2	519.8	MH	89.16	[87.65, 90.58]	251.2	[246.2, 256.3]
		SIR	89.13	[87.63, 90.54]	251.6	[246.6, 256.8]
		Majority vote	88.98	[87.50, 90.40]	258.8	[253.4, 264.3]
3	779.8	MH	89.26	[87.77, 90.68]	248.4	[243.7, 253.3]

Appendix

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.

MH $-$ SIR accuracy (percentage points)
	Accuracy weight $w_{1}$
$M$	0.25	0.5	0.75
2	0.03 [ $-$ 0.12, 0.17]	0.09 [ $-$ 0.03, 0.21]	0.07 [ $-$ 0.06, 0.20]
3	$-$ 0.04 [ $-$ 0.20, 0.12]	0.06 [ $-$ 0.08, 0.18]	0.05 [ $-$ 0.08, 0.18]
5	0.00 [ $-$ 0.19, 0.20]	0.03 [ $-$ 0.12, 0.18]	$-$ 0.08 [ $-$ 0.23, 0.07]
9	$-$ 0.13 [ $-$ 0.34, 0.08]	$-$ 0.09 [ $-$ 0.27, 0.08]	0.12 [ $-$ 0.07, 0.30]

Appendix

Table 5: Paired MH-minus-SIR differences on identical fresh pools, with pointwise 95% prompt-bootstrap intervals. At

M=1

both methods return the first proposal, so both differences are

0

. The difference in selected

\log\rho

describes the selection mechanism and is not a KL improvement.

$w_{1}$	$M$	Mean latency (s)	p95 (s)	Total tokens	Peak allocated (GB)
0.25	1	17.47	26.11	248.7	41.12
0.25	3	20.25	29.54	746.0	41.24
0.25	9	22.53	33.33	2209.0	41.57
0.5	1	21.11	31.76	272.8	41.13
0.5	3	25.30	39.23	831.6	41.25
0.5	9	27.99	39.65	2442.0	41.61

Appendix

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.

$w_{1}$	Mean $G_{M}$	Lower bound	Clipped	Mean $G_{M}$	Lower bound	Clipped	$n=8$	$n=16$
	$M=9$			$M=17$			MH acceptance (%)
0.25	0.228	0.048	0.000	0.244	0.063	0.000	77.19	75.86
0.50	0.427	0.247	0.000	0.460	0.280	0.000	71.18	69.27
0.75	0.321	0.141	0.000	0.338	0.158	0.000	74.71	73.27

Appendix

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

Helpfulness weight $w_{1}=0.25$
$M$	Total tokens	Method	H	S	Weighted	Length
1	244.5	Local decoder ( $q_{w}$ )	1.611	$-$ 0.832	$-$ 0.221	244.5
2	488.7	MH	1.573	$-$ 0.808	$-$ 0.213	241.3
		SIR	1.581	$-$ 0.815	$-$ 0.216	242.1
3	733.8	MH	1.568	$-$ 0.820	$-$ 0.223	241.9
		SIR	1.569	$-$ 0.813	$-$ 0.218	241.4

Appendix

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

w_{1}\mathrm{H}+(1-w_{1})\mathrm{S}

. Length counts returned-response tokens; total tokens include all generated candidates.

MH $-$ SIR helpfulness reward
	Helpfulness weight $w_{1}$
$M$	0.25	0.5	0.75
2	$-$ 0.0073 [ $-$ 0.0154, 0.0004]	$-$ 0.0044 [ $-$ 0.0126, 0.0040]	0.0015 [ $-$ 0.0071, 0.0102]
3	$-$ 0.0011 [ $-$ 0.0116, 0.0094]	$-$ 0.0046 [ $-$ 0.0144, 0.0050]	0.0019 [ $-$ 0.0084, 0.0122]
5	0.0011 [ $-$ 0.0103, 0.0127]	0.0010 [ $-$ 0.0099, 0.0121]	$-$ 0.0048 [ $-$ 0.0168, 0.0073]
9	$-$ 0.0110 [ $-$ 0.0235, 0.0017]	0.0016 [ $-$ 0.0100, 0.0135]	$-$ 0.0046 [ $-$ 0.0173, 0.0079]

Appendix

Table 9: Paired MH-minus-SIR differences on identical HH-RLHF pools, with pointwise 95% prompt-bootstrap intervals. The selected

\log\rho

difference is a selection diagnostic and is not a KL improvement.

$w_{1}$	$M$	MH mean latency (s)	p95 (s)	Peak allocated (GB)
0.25	1	20.92	36.07	41.23
0.25	3	23.20	38.35	41.56
0.25	9	24.54	39.55	42.54
0.5	1	21.74	37.17	41.23
0.5	3	24.24	39.51	41.56
0.5	9	25.67	40.59	42.54

Appendix

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

Figure 6: KL to the target on trained-policy continuation trees. Curves average 50 questions at accuracy weight

w_{1}=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.

Context	$w_{1}$	$D_{q}$	$D_{H}(9)$	$D_{S}(9)$	$D_{S}-D_{H}$	Est. $\mathbb{E}[G_{9}]$ (SE)
Original	0.25	2272	105.7	271.8	166.1	1639 (8.27)
Original	0.5	1229	109.7	197.2	87.49	843.5 (6.81)
Original	0.75	136.5	0.153	4.752	4.599	115.8 (1.00)
Midpoint	0.25	884.3	$<0.0001$	10.36	10.36	788.7 (0.542)
Midpoint	0.5	1308	$<0.0001$	14.33	14.33	1171 (0.834)
Midpoint	0.75	860.2	$<0.0001$	9.362	9.362	770.1 (0.479)

Appendix

Table 11: Direct comparisons at

M=9

on top-8, horizon-4 trees. All numerical entries other than

w_{1}

are in

10^{-6}

nats and are means over 50 questions. Parentheses give the separate Monte Carlo standard error of the mean certificate.

D_{S}-D_{H}

is the MH consensus advantage.

<0.0001

marks a mean KL below the

10^{-10}

-nat reporting resolution.

Context	$w_{1}$	Mean gap [95% CI]	Question SD	Median gap	Unresolved / 50
Original	0.25	166.1 [0.748, 493.7]	1149	0.0764	5
Original	0.5	87.49 [0.656, 259.3]	603.3	0.0779	5
Original	0.75	4.599 [0.296, 12.71]	27.67	0.0284	8
Midpoint	0.25	10.36 [2.049, 21.24]	35.60	0.00150	17
Midpoint	0.5	14.33 [1.128, 35.09]	65.42	0.00339	15
Midpoint	0.75	9.362 [0.623, 24.48]	47.76	0.00259	18

Appendix

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% question-bootstrap intervals for the mean; SD describes per-question variation. The last column counts absolute per-question gaps no larger than

10^{-10}

nats.

		Primary	Sensitivity checks
Context	$w_{1}$	$K=8,T=4$	$K=8,T=2$	$K=8,T=3$	$K=4,T=4$
Original	0.25	166.1	2.405	165.4	166.1
Original	0.5	87.49	1.152	86.74	87.47
Original	0.75	4.599	0.280	4.284	4.596
Midpoint	0.25	10.36	0.647	5.904	7.753
Midpoint	0.5	14.33	1.274	10.57	9.319

Appendix

Table 13: Horizon and mask sensitivity at

M=9

. Mean MH consensus advantage

D_{S}-D_{H}

, 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.

Context	Adapter	$K$	Depth 0	Depth 1	Depth 2	Depth 3
Original	Accuracy	8	100.000	100.000	100.000	100.000
Original	Brevity	8	99.998	100.000	99.999	100.000
Original	Accuracy	4	100.000	100.000	99.966	99.999
Original	Brevity	4	99.994	99.998	99.920	99.998
Midpoint	Accuracy	8	99.756	99.914	99.876	99.926
Midpoint	Brevity	8	99.494	99.866	99.784	99.872

Appendix

Table 14: Retained full-vocabulary mass by depth. Question means of proposal-weighted retained mass, in percent, at

w_{1}=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.

Explore similar work

Sampling for Quality: Training-Free Reward-Guided LLM Decoding via Sequential Monte Carlo
Apr 7, 2026Jelena Markovic-Voronov, Wenhui Zhu, Bo Long +5Language Model Decoding LLM Code Generation
LinkedIn
Chopthin-Consensus Power Sampling: A Diversity-Preserving Approach to LLM Decoding
Sep 10, 2026Minoo Ahmadi, Seyedarmin Azizi, Erfan Baghaei Potraghloo +2Language Model Decoding LLM Inference
University of Southern California, Los Angeles, USA
Don't Mix Rewards, Mix Policies: Policy Decomposition and Optimization for Multi-Reward RL
Jul 31, 2026Ruiming Liang, Yi Zhong, Yizhen Yuan +6Multi-Objective Reinforcement Learning RL for Language Models
1Fundation Model Research Center, CASIA · School of Artificial Intelligence, UCAS · Institute for AI Industry Research (AIR), Tsinghua University +1

Apr 7, 2026J/K move · Enter open · S save

Sampling for Quality: Training-Free Reward-Guided LLM Decoding via Sequential Monte Carlo

Jelena Markovic-Voronov, Wenhui Zhu, Bo Long, Zhipeng Wang+4

Language Model Decoding LLM Code Generation

Open paper AskPDF arXiv

We introduce a principled probabilistic framework for reward-guided decoding in large language models, addressing the limitations of standard decoding methods that optimize token-level likelihood rather than sequence-level quality. Our method defines a reward-augmented target distribution over complete sequences by combining model transition probabilities with prefix-dependent reward potentials. Importantly, the approach is training-free: it leaves model weights unchanged and instead modifies the inference distribution via reward potentials, with all gains arising purely from inference-time sampling. To sample from this distribution, we develop Sequential Monte Carlo algorithms, including a computationally efficient prefix-only variant and a lookahead variant whose intermediate targets match the exact marginals of the full sequence distribution. The framework also integrates resample-move updates with Metropolis-Hastings rejuvenation and supports block-wise generation, subsuming common decoding strategies such as temperature sampling and power-tempered objectives. Empirical results across three 7B models show significant gains. On code generation (HumanEval), our method improves base performance by up to 54.9% and surpasses the strongest sampling baselines by 9.1%-15.3%. On mathematical reasoning (MATH500), it achieves gains of up to 8.8%. Notably, it reaches 87.8% on HumanEval and 78.4% on MATH500 with Qwen2.5-7B, consistently outperforming the reinforcement learning method GRPO.

Abstract

Explore similar work

Sampling for Quality: Training-Free Reward-Guided LLM Decoding via Sequential Monte Carlo

Chopthin-Consensus Power Sampling: A Diversity-Preserving Approach to LLM Decoding

Don't Mix Rewards, Mix Policies: Policy Decomposition and Optimization for Multi-Reward RL