- 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
-
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.
-
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.
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 M-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=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 GM confidence bound, and generation cost on validation prompts, then checking the chosen budget on fresh pools. On GSM8K, M=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 M, 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 ρ. 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 q, a useful statistic is GM, 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.