acceptodds
Under review as a conference paper at ICLR 2027

A Closer Look at Power Sampling

Abstract

Recent advances in the reasoning capabilities of language models have been driven largely by the use of reinforcement learning with verifiable rewards (RLVR) in post-training pipelines. However, recent work has suggested that, at least with an open-source compute budget, RLVR may improve language-model performance primarily by increasing the probability of sequences that already have high proba- bility under the base model. This has motivated the creation of training-free, test- time methods for sharpening the base model distribution based on the power dis- tribution: a global tempering of the language model distribution that up-weights high-likelihood sequences. Prior work has shown that sampling approximately from the power distribution leads to strong accuracy for certain models and bench- marks. In this paper, we create a novel exact sampler for the power distribution and devise experiments for probing the power distribution. Our experiments show that exact samples from the power distribution closely resemble samples gener- ated with likelihood-maximization-based beam search. The power distribution improves accuracy for some models and benchmarks and drastically degrades ac- curacy on others, challenging the notion that that performance gains observed with RLVR can be attributed to its use. Therefore, past gains observed from approx- imate sampling from the power distribution must be attributed to their sampling strategy rather than the underlying target distribution.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
RLVR, post-training, distribution sharpening, LLM

Reviews

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

This paper examines the sequence-level power distribution pα(y∣x)∝p(y∣x)αp_{\alpha}(y\mid x)\propto p(y\mid x)^{\alpha}, separating properties of this target from the behavior of approximate samplers. It uses rejection sampling when an argmax completion can be certified, together with importance sampling and differently initialized Metropolis–Hastings chains. Across mathematical and code-generation benchmarks, the paper finds that sharpening often favors short, high-probability completions and questions whether power sharpening explains RLVR-like improvements.

Critical strengths
  1. Separating the target distribution from the sampling algorithm is an important and well-motivated question. An approximate sampler’s benchmark gains do not by themselves establish that the target distribution has the same benefit.

  2. The combination of accuracy, completion-length analysis, and initialization comparisons provides useful evidence about how global sharpening and finite-run inference can behave differently.

Critical weaknesses
  1. The empirical exactness claim needs stronger validation. Appendix K.1 explicitly reports that, for the example used in Figure 4, an accepted proposal’s saved log probability exceeds the saved argmax bound. A valid rejection envelope is central to the exact-sampling argument. This does not establish that the main results are wrong, but the paper needs to quantify the frequency and magnitude of such violations and demonstrate that the conclusions survive a consistent scoring and certification procedure.

  2. The evidence has different coverage across methods. Rejection sampling is evaluated only on problems with a certificate and an accepted proposal, whereas other methods use the full benchmarks. Importance sampling and finite-run MH provide additional evidence, but not the same guarantee as valid rejection sampling. Consequently, the conclusion that earlier improvements arise from inference artifacts, and the broader interpretation concerning RLVR, are stronger than the certified subset alone establishes.

Questions for authors
  1. How many problems exhibit proposal scores exceeding their certified bounds, and how do the main results change after excluding or correctly recertifying these cases?

  2. Can you report paired comparisons of all methods on the same validly certified subset, alongside separate results and reliability diagnostics for the remaining problems?

2 comments
AuthorsOpenReview ↗

Response to EEdm

We appreciate the reviewer’s especially careful and thorough review of the paper. Your review motivated new analyses, which we have added to the revised text, that we believe has strengthened the quality of the work. We address your questions and concerns below.

How many problems exhibit proposal scores exceeding their certified bounds, and how do the main results change after excluding or correctly recertifying these cases?

  • Regarding the point about the valid rejection envelope, we have included Appendix E.3, which analyzes the numerical precision of our method. Table 9 shows the magnitude of these numerical errors and reports a median error of 0.07-0.08 nats. This is the only source of the violations of the rejection envelope. We find that such violations are rare, occurring for only 0.19% of proposed Qwen2.5 samples. 93% of these violations occur with the argmax completion itself, scored differently by beam-search and autoregressive sampling. Consequently, numerics do not meaningfully change the conclusions in the paper.

The evidence has different coverage across methods. Rejection sampling is evaluated only on problems with a certificate and an accepted proposal, whereas other methods use the full benchmarks. Importance sampling and finite-run MH provide additional evidence, but not the same guarantee as valid rejection sampling. Consequently, the conclusion that earlier improvements arise from inference artifacts, and the broader interpretation concerning RLVR, are stronger than the certified subset alone establishes.

  • We appreciate the reviewer’s concern about this. The text now points to Table 3, which shows the accuracy of all the methods on the same certified set of problems. On this set of problems, samples drawn with RS are unbiased and the difference in accuracy between MH and RS is sizable enough that it must be due to the inference algorithm rather than variance among the outputs or a systematic bias.
  • We have also softened the claims about RLVR and now focus on the proximity of exact power sampling to beam search. We have also revised our claim to say that past accuracies reported with Metropolis-Hastings benefited from artifacts of approximate inference. This is evidenced by Tables 2 and 3.

Can you report paired comparisons of all methods on the same validly certified subset, alongside separate results and reliability diagnostics for the remaining problems?

  • Appendix A.1 now includes a paired comparison between rejection sampling and the other methods on the subset of problems where rejection sampling produced a sample with a paired t-test. The table shows that BS, SNIS, MH-BS are never statistically significantly different from RS with the exception of Qwen3-8B-Base on the MBPP benchmark, which, despite being equal to exactly the beam search output 74.98% of the time, incurs a small systematic bias in the accuracy that is detectable with a high sample size. MH, on the other hand, is statistically significantly different from RS for many models and benchmarks. Table 3 shows the results on the remaining problems.
AuthorsOpenReview ↗

Following up with reviewer EEdm

We greatly appreciate reviewer EEdm volunteering their time to review our paper. We are following up to kindly request that the reviewer please let us know of any additional questions they may have before the review period deadline (November 18 AoE). We believe our paper greatly benefited from your comments and that we have addressed your concerns with our response above.

Reviewer_rFRXOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes an exact sampler for the power distribution and shows that its samples closely resemble those generated by likelihood-maximizing beam search rather than RLVR. The authors argue that previous improvements from approximate power sampling should be attributed to the sampling strategies rather than the underlying power distribution.

Critical strengths
  1. The paper provides a sampler for exact power sampling under certain conditions, which could be useful for analyzing the target distribution.
  2. The paper offers an interesting perspective on understanding distribution sharpening and analyzing the improvements of power sampling methods.
Critical weaknesses
  1. The experiments mainly focus on that power sampling can generate very short, meaningless completions, which is not surprising for distribution sharpening methods, as sequence-level likelihood maximization can favor shorter completions. However, this does not sufficiently explain the relationship between distribution sharpening and reasoning accuracy, as claimed in this paper. The paper does not investigate if the degradation persists for meaningful reasoning trajectories, and the current evidence seems insufficient to support the claim that previous gains must come from approximate sampling strategies rather than the power distribution.
  2. There is potential selection bias in RS evaluation. RS only produces results on a subset of problems (e.g., 165/500 on MATH500 for Qwen2.5-7B). Considering the search timeout setting, problems involving longer, high-probability prefixes may be harder to certify. This could bias the evaluated subset toward the short response degeneracy that the paper mainly focuses on.
Questions for authors
  1. It is important to understand the performance of meaningful reasoning trajectories rather than only extremely short responses (<= 5 tokens). Could the author provide the accuracy of meaningful completions across different methods? Also, in practice, what happens if the model starts sampling after a common reasoning prefix, such as "To solve the problem,”, would the same accuracy degradation persist?
  2. Could the authors evaluate MH initialized with conventional length-controlled beam search rather than the best-first beam-search as an ablation? Also, how do the conclusions compare with other Monte Carlo methods for power sampling, which generate an initial block before applying subsequent sampling updates?
  3. The computational cost of the exact sampling is unclear. The proposed method requires expensive argmax certification followed by 1,024 proposals in practice, a brief analysis of the computational cost per successful sample should be provided.
4 comments
AuthorsOpenReview ↗

Response to rFRX

We thank the reviewer for their careful review. We found the feedback to try our method on completions prefixed with (1) an initial starting block as in [1] and (2) the common reasoning prefix “To solve the problem” to be especially insightful. Your comments have motivated new experiments that we believe have strengthened our draft. We have uploaded our revised draft and highlighted changes in blue. We address the reviewer’s concerns and questions below.

The experiments mainly focus on that power sampling can generate very short, meaningless completions, which is not surprising for distribution sharpening methods, as sequence-level likelihood maximization can favor shorter completions. However, this does not sufficiently explain the relationship between distribution sharpening and reasoning accuracy, as claimed in this paper. The paper does not investigate if the degradation persists for meaningful reasoning trajectories, and the current evidence seems insufficient to support the claim that previous gains must come from approximate sampling strategies rather than the power distribution.

  • We agree that the argmax completion is often degenerate, which is well documented [2]. Since the power distribution converges to the argmax as α→∞\alpha\to\infty, degenerate samples at large α\alpha are unsurprising. Our finding is that this already happens at α=4\alpha=4: 61–74% of exact samples on MATH500 are the beam-search output (Table 8), so accuracy under the power distribution tracks beam search (Table 3) and degrades wherever the argmax is degenerate; for comparison, the Metropolis-Hastings sampler is degenerate 0% of the time for the Qwen2.5-7B model and MATH500 benchmark (Figure 3). Prior work motivated the power distribution as an explicit, training-free form of the distribution sharpening attributed to RLVR, and attributed the resulting accuracy gains to this target distribution [3]. Our exact sampler tests that attribution directly.
  • The degradation also persists for meaningful completions. Table 4 (new) now restricts every method to the problems where RS produced a sample and conditions each method on its completions being longer than 5 tokens. On MATH500, exact power sampling closely tracks beam search on all four models (within 5 points). MH from the empty completion, by contrast, is higher on every model. The gains attributed to power sampling therefore do not appear among the power distribution’s non-degenerate completions either.
  • We have revised the claim about improvements coming from artifacts of approximate inference. We now say that past results with Metropolis-Hastings benefited from artifacts of approximate inference, which follows from Tables 2 and 3.

Also, in practice, what happens if the model starts sampling after a common reasoning prefix, such as "To solve the problem”, would the same accuracy degradation persist? Also, how do the conclusions compare with other Monte Carlo methods for power sampling, which generate an initial block before applying subsequent sampling updates?

  • The degeneracy is also not an artifact of the empty starting context (Table 13). When Qwen2.5-7B’s output is prefixed with “To solve the problem,” 27 of 29 accepted samples are at most 5 tokens long and none are correct. With a 10-token autoregressively sampled prefix, 188 of 233 accepted samples are at most 5 tokens and none are correct.

There is potential selection bias in RS evaluation. RS only produces results on a subset of problems (e.g., 165/500 on MATH500 for Qwen2.5-7B). Considering the search timeout setting, problems involving longer, high-probability prefixes may be harder to certify. This could bias the evaluated subset toward the short response degeneracy that the paper mainly focuses on.

  • We appreciate the reviewer raising this point. We point out that for coding benchmarks, rejection sampling often produces samples for nearly all problems, which negates the selection bias. In particular, we observe that for all models and benchmarks where rejection sampling produces a completion for at least 90% of problems, the accuracies of beam search and the rejection sampler differ by <3%.
  • To address the concern that the tables are reporting accuracies for different subsets of problems, we point to Table 3, which shows the accuracies of all the methods applied to Qwen2.5 conditioned on the problems where rejection sampling produced at least one sample (left) and the accuracies of all the methods on the subset of problems where rejection sampling did not produce a sample (right). On the set of problems where RS produces a sample, samples drawn with RS are unbiased. The difference in accuracy between MH and RS is sizable, and it must be due to the inference algorithm rather than variance among the outputs or a systematic bias.
  • We address the comment about our method biasing shorter completions in our answer on computational cost below.
AuthorsOpenReview ↗

Response to rFRX [cont.]

Could the authors evaluate MH initialized with conventional length-controlled beam search rather than the best-first beam-search as an ablation?

  • Table 12 shows the accuracy of Qwen2.5-7B on the MATH500 benchmark with length-normalized beam-search and Metropolis-Hastings initialized from length-normalized beam-search.

The computational cost of the exact sampling is unclear. The proposed method requires expensive argmax certification followed by 1,024 proposals in practice, a brief analysis of the computational cost per successful sample should be provided.

  • Table 10 breaks down the computational cost of the different steps of our method on the Qwen2.5 model. Figure 5 shows a scatter plot with the lengths of certified argmax completions (x-axis) against the time it took to certify those completions (y-axis). The trend is that longer argmax completions are actually certified faster than short ones; in order to certify a short completion, best-first beam search must first prune many long completions first.
    • This agrees with Table 1 and Figure 2, which show that the completions produced for coding benchmarks are both accepted more often and are generally longer than those produced for math benchmarks under the power distribution. [1] Azizi, S., et al. “Power-SMC: Low-Latency Sequence-Level Power Sampling for Training-Free LLM Reasoning.” 2026. [2] Holtzman, A., et al. “The Curious Case of Neural Text Degeneration.” ICLR 2020. [3] Karan, A. and Du, Y. “Reasoning with Sampling: Your Base Model is Smarter Than You Think.” ICLR 2026.

Thank you for the detailed response and additional experiments. These experiments address several of my concerns, and the additional evidence strengthens the finding of short-completion degeneration. However, I still have one question about the coverage of the prefix-conditioned experiments in Table 13. With the fixed reasoning prefix, only 24 out of 500 problems yield RS samples (29 accepted samples in total), which seems too limited to reliably characterize the performance of the power distribution under this setting. While I understand that this low coverage may be an inherent limitation of the rejection-sampling procedure, could the authors further explain why the coverage drops so significantly after adding a prefix?

AuthorsOpenReview ↗

Response to rFRX

We thank the reviewer for noting that these new experiments address several of their concerns and strengthen the evidence of short-completion degeneration.

That we cannot draw samples for all problems in the benchmark is indeed a limitation of our method. We can, however, confirm that exact power sampling degrades performance compared to MH on this subset of 29 problems (added for reference in the caption).

Regarding why coverage declines for problems that are prefixed with “To solve the problem”, we observe that this is due to the following two reasons:

  1. The best-first beam search needs more expansions in order to certify the argmax in the fixed-prefix setting. The increased frequency with which timeouts occur in the search causes argmax completions to be certified less often (492 for no-prefix and 148 for fixed-prefix).
  2. We observe a strong inverse correlation between the number of expansions needed to certify an argmax and the log-likelihood of the argmax (see figure attached in supplementary material). As the number of expansions increases, the log-likelihood of the argmax completion decreases, meaning that the probability that the proposal step will propose the argmax decreases. The log-likelihood of drawing a sample is -8.21 for no-prefix (probability of 0.24 of proposing the argmax with 1024 proposals, per the calculation in Appendix E.1) and -9.19 for fixed-prefix (probability of 0.10 of sampling the argmax with 1024 proposals).
    1. For the fixed-prefix setting, in 79 problems, BS produced a degenerate argmax completion (length < 5 tokens) with log-likelihood <−9<-9 (equivalent to 11.8% of the argmax proposed among 1024 autoregressive samples) and RS produced a sample for 8/79=10.1%8/79=10.1\% of these problems. This evidence suggests that RS would have produced degenerate completions on this extended set of problems as well.
Reviewer_CwdpOpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
3
Soundness
3(+1)
Read review
Paper summary

The authors investigate power sampling, a recent inference time approach to sampling higher quality traces for better reasoning capabilities. The authors introduce a rejection sampler for the power distribution and demonstrate that accuracy for traditional power sampling tracks beam search across their experiments.

Critical strengths
  • Asks the right question of trying to disentangle to what extent sharpening with from-scratch initialization vs. the actual power distribution is the driving force behind power sampling.

  • Evaluates over a broad set of hard benchmarks and a variety of base models.

Critical weaknesses
  • Table 2 doesn't seem to that convincingly demonstrate that the power distribution gravitates towards the beam search output (e.g. on Qwen 2.5 7B)? Is there a comparison to how often Metropolis-Hastings initialized from scratch lands at the beam search output?

  • Paper focuses on single-shot accuracy comparison across sampling approaches from the power distribution and beam search, but would be informative to see more "reasoning distribution" (pass@k) comparisons over several samples. E.g., the pass@k curves should look characteristically different between an annealed power distribution compared to a max-likelihood sampler.

Questions for authors
  • How does the pass@k behavior of beam search/rejection sampling compare to Metropolis-Hastings (without beam-search initialization)? Single-shot accuracy might be similar, but is there a characteristic difference in the distributions of samples that are produced over multiple shots?

  • Is there a way to compute the mismatch between the samples generated from MH from scratch with the actual power distribution directly?

  • Do the proposal sequences for rejection sampling have any relation to the search for the argmax certificate or are they fresh samples, and the certificate is just used for the reweighting?

  • Should you expect an MCMC process initialized from scratch to sample from the power distribution to be similar to an MCMC process initialized at the beam search mode? E.g., for a toy multimodal distribution, if sharpened sampling is performing a "mode search", then initializing at one of the modes at the start would end up converging to that mode with high probability. In this lens, the Metropolis-Hastings initialized at beam search doesn't seem to have too strong implications about the power distribution itself (i.e., initializing from scratch is part of the point of sampling algorithm)? Comparing how often samples from MH initialized from scratch resemble those from beam search might be a more informative comparison here.

  • Following up on this question, is the argument that MCMC initialized at beam search is faithfully similar to sampling from the power distribution, but the fact that the original MH starts from scratch the key difference in explaining results e.g. in Table 1? What is the intuition for how this difference in initialization can lead to the different accuracy behaviors?

  • Sequence lengths getting shorter seem to contradict findings from the original power sampling paper that sequence length grows with MH from scratch initialization. Could the authors clarify this discrepancy, or validate that MH from scratch has different sequence length averages than rejection sampling/MH-BS?

4 comments
AuthorsOpenReview ↗

Response to Cwdp

We appreciate the reviewer recognizing the value of the question we are aiming to answer and the thoroughness of our experiments.

We particularly appreciate the thoroughness of the reviewer’s comments and questions! Your points motivated new experiments that we believe have strengthened our work. The current draft includes these revisions, which we have highlighted in blue for clarity.

Table 2 doesn't seem to that convincingly demonstrate that the power distribution gravitates towards the beam search output (e.g. on Qwen 2.5 7B)? Is there a comparison to how often Metropolis-Hastings initialized from scratch lands at the beam search output?

  • We appreciate the reviewer flagging this discrepancy. We have modified Table 8 (previously Table 2) to make the results more interpretable. First, the table shows the results on the subset of problems where RS produced a sample. Second, the table includes the frequency with which MH-from-scratch outputs the beam-search completion. Regarding how much the models gravitate to the beam-search output, we note that for the Qwen2.5-7B model, RS equals the beam-search output >50% of the time on all benchmarks while AR never outputs the beam-search output more than 2% of the time. We further note that on math benchmarks, SNIS assigns less mass to the beam-search output because a proposal equal to the beam-search output is not sampled very often (see Appendix E.1), so this number is likely not representative of the true concentration that the power distribution assigns to the argmax completion.

How does the pass@k behavior of beam search/rejection sampling compare to Metropolis-Hastings (without beam-search initialization)? Single-shot accuracy might be similar, but is there a characteristic difference in the distributions of samples that are produced over multiple shots?

  • Figure 6 now reports pass@kk accuracy for the power distribution for k≤4k\leq 4 with Olmo-2 and Olmo-3 on the MBPP benchmark. We chose these models and this benchmark because the rejection sampler produces at least 4 completions for a majority of the problems: 251/257 for Olmo-2 and 235/257 for Olmo-3. This helps give more reliable Pass@ scores. For these two models, we see a marginal improvement in accuracy as kk increases. However, because of the lower entropy of the power distribution, its samples have less diversity, so ordinary temperature-1 autoregressive decoding has higher accuracy than power sampling for k≥3k\geq3. We did not run pass@kk experiments with MH-from-scratch due to compute limitations. We would expect pass@kk results between MH and RS to be very different on benchmarks like MATH500 where the accuracy (Table 3) and frequency of matching beam-search (Table 8) differ significantly between these two methods, and we would expect results to be similar for models and benchmarks where these three distributional statistics agree (Olmo-3 on MBPP).
  • We sharpened the wording in the introduction to say that we find that argmax sampling is a strong predictor for single-shot exact power sampling accuracy.

Is there a way to compute the mismatch between the samples generated from MH from scratch with the actual power distribution directly?

  • As a measure of mismatch between MH samples and the exact power distribution, Table 11 now shows the average of αlog⁡p\alpha \log p under samples drawn with MH, RS, and MH-BS for the subset of problems where RS produces a sample. The samples drawn with MH usually have a much lower (unnormalized) log-probability under the power distribution than RS and MH-BS samples have slightly higher log-probability than RS.

Do the proposal sequences for rejection sampling have any relation to the search for the argmax certificate or are they fresh samples, and the certificate is just used for the reweighting?

  • The proposal samples for rejection sampling have no relation to the beam search. They are fresh samples and the argmax completion is just used to improve the acceptance rate.
AuthorsOpenReview ↗

Response to Cwdp [cont.]

Should you expect an MCMC process initialized from scratch to sample from the power distribution to be similar to an MCMC process initialized at the beam search mode? E.g., for a toy multimodal distribution, if sharpened sampling is performing a "mode search", then initializing at one of the modes at the start would end up converging to that mode with high probability. In this lens, the Metropolis-Hastings initialized at beam search doesn't seem to have too strong implications about the power distribution itself (i.e., initializing from scratch is part of the point of sampling algorithm)? Comparing how often samples from MH initialized from scratch resemble those from beam search might be a more informative comparison here.

  • We found this question especially insightful. If sufficient steps are applied for the chain to mix, then the MCMC initialization should not matter. If an insufficient number of steps is used, then there is a valid concern that an MCMC sample will get stuck in a mode. The two-mode example you described is a great frame. We do observe in practice that MH-BS settles on the beam search output more often than RS (Table 8). We have revised the text to emphasize the sensitivity of the MH to the initial starting point, which implies insufficient MH updates are applied to reach convergence, and have softened the claim about MH-BS samples being near-exact.
  • Regarding the frequency with which MH-from-scratch converges to best-first beam search, we have updated Table 8, which now shows the fraction of times that MH and MH-BS are exactly equal to the argmax completion on the set of problems where RS produces a sample.

Following up on this question, is the argument that MCMC initialized at beam search is faithfully similar to sampling from the power distribution, but the fact that the original MH starts from scratch the key difference in explaining results e.g. in Table 1? What is the intuition for how this difference in initialization can lead to the different accuracy behaviors?

  • Regarding why MH initializations can change accuracy behavior, we hypothesize that this is due to behaviors observed with best-of-N sampling. [1] analyzes the behavior of a sampling procedure, known as best-of-N sampling, that (1) draws N independent samples and (2) outputs the sample with the highest likelihood. Figure 1 (left; dashed lines) of [1] shows that, across many models, accuracy increases with this procedure for small values of N>1N>1 and declines with higher values of NN. Due to the sharpness of the power distribution, we would expect that proposals in our Metropolis-Hastings sampler are nearly always accepted if their likelihood is higher than the current samples and they are nearly always rejected if their likelihood is lower. Thus, an intuition for why the initialization changes the accuracy behavior is that, when initialized from scratch, the Metropolis-Hastings sampler behaves like best-of-N sampling with modest NN and, when initialized from beam search, the Metropolis-Hastings sampler behaves like best of N with N=∞N=\infty. We have added this intuition to the revised text.

Sequence lengths getting shorter seem to contradict findings from the original power sampling paper that sequence length grows with MH from scratch initialization. Could the authors clarify this discrepancy, or validate that MH from scratch has different sequence length averages than rejection sampling/MH-BS?

  • We appreciate the review flagging the discrepancy in completion length. We have added a new appendix, Appendix C.2, which describes a bug we found in the original implementation of the Metropolis-Hastings sampler. Due to the acceptance ratio of the original algorithm being slightly off, the original Metropolis-Hastings implementation may have inadvertently been sampling from a distribution closer to pα(x)len(x)p^\alpha(x)\mathrm{len}(x). Table 7 shows that for Qwen2.5, our (debugged) implementation of the sampler is consistently shorter than the original buggy sampler. On the AIME benchmarks, the original sampler produces completions that are longer than autoregressive temperature-1 sampling as well. We hypothesize that this may have contributed to the original authors’ report that power sampling with Metropolis-Hastings increases completion lengths. All of our experiments use the debugged implementation.

[1] Huang, A., et al., “Is Best-of-N the Best of Them? Coverage, Scaling, and Optimality in Inference-Time Alignment”

AuthorsOpenReview ↗

Following up with reviewer Cwdp

We greatly appreciate reviewer Cwdp volunteering their time to review our paper. We are following up to kindly request that the reviewer please let us know of any additional questions they may have before the review period deadline (November 18 AoE). We believe our paper greatly benefited from your comments and that we have addressed your concerns with our response above.

Thanks for the extremely thorough replies to my questions!! I maintain my original positive assessment of the paper, but happy to increase the soundness score!

Comments on the paper

1 comment
AuthorsOpenReview ↗

Rebuttal summary

Dear Reviewers and ACs,

We are grateful to the reviewers for their thoughtful questions and helpful feedback, which gave us an opportunity to strengthen our paper. We have made many revisions to our text (highlighted in blue).

New experiments.

  • We ran Metropolis-Hastings (MH) initialized from length-normalized beam search per rFRX's request as an ablation, finding a modest increase in accuracy over ordinary length-normalized beam search decoding (reported in Table 12)
  • We ran exact power sampling initialized from common prefixes like "To solve this problem" and found that, among problems where rejection sampling produces at least one output, the degradation of exact power sampling accuracy persists (Table 13).

Responses to concerns.

  • Per Cwdp's request, Figure 6 now shows Pass@k accuracy of Olmo-2 and Olmo-3 on MBPP. Exact power sampling improves only marginally as kk increases and underperforms autoregressive decoding for k≥3k\geq 3.
  • Regarding why MH's completion lengths are shorter than autoregressive decoding, in contradiction to past findings, we added a new appendix, Appendix C.2, which describes a bug we found in the original implementation of the Metropolis-Hastings sampler that explicitly lengthens completions.
  • Cwdp asked what the intuition was for why insufficiently mixed MH could increase accuracy while exact power sampling decreased it, so we revised the text to mention our hypothesis that this is related to the inverted-U shape observed in accuracy with best-of-N sampling.
  • Reviewers rFRX and EEdm requested to see the accuracies of the three methods restricted to the same subset of problems, so we included Tables 2 and 3 in our paper, which show that beam search and exact power sampling are within 3 percentage points for all models and benchmarks. A paired t-test (Table 2) finds no statistically significant difference between exact power sampling and beam search for any model or benchmark except Qwen3-8B-Base on MBPP, where 75% of exact power sampling outputs exactly equal the beam search output and a small bias appears among the non-beam search completions.
  • Regarding rFRX's concern that our method may be biased toward short completions, Figure 5 now shows that shorter certification times are actually consistent with longer completions.
  • Reviewer EEdm expressed concern about the validity of our rejection envelope. We included Appendix E.3, which analyzes the numerical precision of our method (the only source of envelope violations) and reports that these numerical errors are inconsequential and do not affect the findings in our paper.

Reviewer rFRX noted that our rebuttal "address[ed] several of [their] concerns, and the additional evidence strengthens the finding of short-completion degeneration". Reviewer Cwdp maintained their positive assessment of the paper and increased its soundness score. Reviewer EEdm has not yet responded; we believe Appendix E.3 and Tables 2–3 address their concerns and hope you will take them into account.

Thank you,
The Authors

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.