- Rating
- 1
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 1
Read review
Paper summary
The paper proposes Power Stochastic Beam Search (PoBS), which tries to sample from the sequence-level power distribution with a Gumbel-based stochastic beam search. Each prefix is scored by its power-weighted subtree mass, which in practice is approximated with a one-token lookahead. The beam returns k=8 candidates, and the final answer is picked with a weighted vote. The main claims are higher accuracy than MCMC power sampling and GRPO on MATH500, HumanEval and GPQA with three 7B models, while running about 31 times faster than MCMC.
Critical strengths
Linking power sampling to stochastic beam search is a nice idea. It returns k distinct candidates in one pass, and the cost per candidate is close to normal sampling and far below MCMC. The point that dropping the subtree term turns the method back into low temperature decoding is also a good observation.
Critical weaknesses
In my opinion, the main comparisons in this paper are not fair. PoBS picks its answer by voting over 8 candidates, while the base, low temperature, MCMC and GRPO results use a single sample. The paper shows that the first PoBS candidate alone is about as good as low temperature sampling, and when all methods get the same vote over 8 candidates, PoBS is only slightly ahead of GRPO. So most of the gain seems to come from voting rather than from the sampler, and PoBS is also slower than just drawing 8 low temperature samples. The same baselines also have different numbers in different parts of the paper, and there are no seeds or error bars.
Since Karan & Du (2025), I have read several papers that try to make power sampling faster. The SMC-based method of Azizi et al. (2026) and the rollout-based method of Ji et al. (2026). Speed is one of the main claims of PoBS, but it is only compared with MCMC, so I can't tell whether it is actually faster or more accurate than these newer methods.
The claim of exact sampling only holds for an ideal version that cannot be computed. What is actually run uses a one-token lookahead and other approximations, and the paper never measures how far its samples are from the true power distribution.
I also found the proof of the key theorem hard to follow, and it did not convince me that the claim holds. One step of the derivation replaces one quantity with another without showing that the result stays exact.
The writing also needs a lot of work. Many sentences are broken or unclear, and I had to read parts of the method several times to follow it.
Questions for authors
Can you report all methods with the same selection rule for all models and benchmarks, including plain voting over 8 low temperature samples?
Can you measure how far PoBS samples are from the true power distribution, for example with a small model or a short horizon where π_β can be computed exactly?
Please also give a full proof of Theorem 2 and explain why the substitution in Lemma 2 keeps the sampling exact.
Can you compare PoBS with the faster power sampling methods, such as Azizi et al. (2026) and Ji et al. (2026), in both accuracy and time?
5 comments
Q3. (full proof of Theorem 2)
Assume that , i.e., $\mathbf{x}^{(\ell)} = \arg\max_{\tilde{\mathbf{x}}^{(\ell)}} S(\tilde{\mathbf{x}}^{(\ell)})$. Define $\mathbf{u} = \mathbf{x}^{(j)} = \mathbf{x}^{1:j} \sim \pi_{\beta}^{1:j}(\tilde{\mathbf{x}}^{(j)})$. We then have
$S^{j:\ell}(\mathbf{u}) = \max_{\mathbf{u} \subset \tilde{\mathbf{x}}^{(\ell)}} S(\tilde{\mathbf{x}}^{(\ell)}) = S(\mathbf{x}^{(\ell)}) = \max_{\tilde{\mathbf{x}}^{(\ell)}} S(\tilde{\mathbf{x}}^{(\ell)})\geq \max_{\mathbf{u}' \subset \tilde{\mathbf{x}}^{(\ell)}} S(\tilde{\mathbf{x}}^{(\ell)}) = S^{j:\ell}(\mathbf{u}')$,
for all with .
We now prove that . Indeed, we have
$S^{j:\ell+1}(\mathbf{u}) = \max_{\mathbf{u} \subset \tilde{\mathbf{x}}^{(\ell+1)}} S(\tilde{\mathbf{x}}^{(\ell+1)}) = \max_{\mathbf{u} \subset \tilde{\mathbf{x}}^{(\ell)}} S(\tilde{\mathbf{x}}^{(\ell)})= S(\mathbf{x}^{(\ell)}) = S^{j:\ell}(\mathbf{u}) \geq S^{j:\ell}(\mathbf{u}') = \max_{\mathbf{u}' \subset\tilde{\mathbf{x}}^{(\ell)}} S(\tilde{\mathbf{x}}^{(\ell)})\geq \max_{\mathbf{u}' \subset \tilde{\mathbf{x}}^{(\ell+1)}} S(\tilde{\mathbf{x}}^{(\ell+1)}) = S^{j:\ell+1}(\mathbf{u}')$.
For any with and any token , we have
$S^{j+1:\ell+1}(\mathbf{u} \oplus v^{*}) = \max_{\mathbf{v}} S^{j+1:\ell+1}(\mathbf{u} \oplus v) = S^{j:\ell+1}(\mathbf{u})\geq S^{j:\ell+1}(\mathbf{u}') = \max_{v'} S^{j:\ell+1}(\mathbf{u}' \oplus v') \geq S^{j:\ell+1}(\mathbf{u}'\oplus v')$.
This concludes our proof.
The scores in our sampler are drawn from the Gumbel law of Theorem 1. What the proof of Theorem 2 needs at every prefix is a max condition: the prefix's own score must be the largest score among its children. That condition is not optional. It makes the parent's score the anchor for its children and puts the children of different parents on one comparable scale, so Theorem 2 cannot be proved without it. Drawing the children's scores independently at random might not satisfy the "max" constraint, because there is no guarantee that their maximum is under the score the parent already carries. Lemma 2 is the sampling version that maintains it: the max-pin rescales the drawn scores so that their maximum equals the parent's score exactly, while leaving them distributed as those same Gumbel scores conditioned on that maximum: it shifts all of a parent's children by the same amount, so the highest child stays the highest and the token the argmax picks inside a parent does not change. Every child sits under its own parent's score, that lets children of different parents be compared. We have rewritten in the method section, where the max condition is now stated as something the proof requires and the max-pin as what restores it.
Q4. (compare with two recent work)
At the time we submitted this work, two papers the reviewer requires were not fully release the code so we cannot compare to them fully and exactly. Both are now run from the authors' own code on all 500 MATH500 problems with Qwen2.5-Math-7B, eight seeds each so that every arm offers eight candidates, under our prompt, on the same A100-80GB:
| method | cand. | s / problem | tokens / cand. | one-shot | pass@8 |
|---|---|---|---|---|---|
| SPS (Ji et al. 2026) | 8 | 136.9 | 35378 | 0.820 | 0.870 |
| Power-SMC (Azizi et al. 2026) | 8 | 720.0 | 47050 | 0.796 | 0.844 |
| PoBS (ours) | 8 | 76.9 | 3558 | 0.828 | 0.884 |
On accuracy we match Ji et al. and beat Azizi et al.: one-shot 0.828 against 0.820 and 0.796 ; pass@8 0.884 against 0.870 and 0.844. On time, our eight candidates cost 76.9 s against 136.9 s and 720.0 s, that is, 1.8× and 9.4× faster.
Dear Reviewer PYue,
Thank you again for your time and thoughtful feedback on our submission
We posted our responses to your questions. As the discussion period is about to close, we just want to kindly check whether our responses have addressed your concerns. If any points remain unclear, or if there is anything further we can provide, we would be glad to respond before the deadline. If our responses have resolved your concerns, we would be grateful if you could consider reflecting this in your assessment.
Thank you very much for your time and consideration.
Best regards,
Dear Reviewer PYue,
Thank you for your insightful feedbacks and comments for our work. Based on your valuable comments, we have revised the paper and provided more detailed proof of Theorem 2.
Critical Weakness. Our experiment is totally fair compared to other baselines and we do not violate any rule. In terms of measuring the pass@1 metric, despite generating 8 candidates per question, we only submit the best one by voting. Meanwhile, MCMC method also uses many candidate as well, it just keeps the best one and throws others away. In practice, MCMC generation proceeds in 16 blocks of 3072/16=192 tokens, and after each block the sampler makes 10 repair attempts. Each attempt draws a cut point uniformly over the text generated so far, discards everything after it, regenerates that suffix by temperature sampling, and so produces a second, complete version of the sequence. The two versions are then compared and one is kept, with probability min(1,r) for the rewrite, where r is the Metropolis-Hastings ratio. A single returned sample therefore costs 16×10=160 of these regenerations. Each of those 160 versions is a candidate answer, and 159 of them are discarded and causes very high running time.
We also report cost as forward-pass token positions, counting candidates that are later discarded; and the running time per candidate. Every arm below ran in one process on one A100-80G over the same 100 MATH500. The results highlights our sampling speed compared to MCMC (about 30 ×) problems, Qwen2.5-Math-7B, α=4, k=8, 3072-token budget.
Q1. (rule selection for all methods)
It is already in the appendix (Table 4), and we should have pointed to it from the main text. The selection-rule table there applies all five rules (native, best-of-N, vote, weighted vote and pass@8) to the same k=8 candidates for every sampler, and the arm the reviewer mentions is its second row: plain voting over eight τ=0.25 samples reaches 0.798, against our 0.824 under the identical plain vote and 0.828 under the weighted vote. The weighted vote is a component of our method, proposed in the method section alongside the sampler, not a post-hoc evaluation convenience, and it weights each candidate by the confidence the sampler itself produces (eλzi, with zi the mean per-token log-probability standardised within the problem). What that table does not yet do is span the grid: it covers MATH500 with Qwen2.5-Math-7B only because the running time for our main baseline is MCMC that takes few days to run full the dataset.
Q2. (compare the distribution distance)
Even at a short horizon, computing πβ exactly is infeasible: the number of sequences is ∣V∣T, and a horizon short enough to enumerate is too short for the answers to carry their full meaning. We also looked for a comparable setting in related work and did not find one. We therefore propose a setting that compares the likelihood of our samples against the likelihood of MCMC's samples. The idea behind it is maximum likelihood: for a fixed model, the mean log-likelihood of a sample is −H(q^)−KL(q^,∣,πα), so minimizing the KL divergence is the same as maximizing the likelihood, and the mean log-likelihood of a sampler's own draws under πα measures how far that sampler sits from the target. Taking πα∝p4, the target used throughout our experiments, and assuming the entropy difference between the two samplers is negligible, we measure
\pi_\alpha) \right) = 4 \left( E_{\text{ours}} \log p(y) - E_{\text{mcmc}} \log p(y) \right)$$ We take 50 randomly questions, compute the log-likelihood of the answers produced by our method and by MCMC under the model, and measure the difference. The result gives $\Delta = 11.34$ and therefore demonstrates that our samples are better described by the original target power distribution $p^{4}$ than MCMC's samples are.