acceptodds
Under review as a conference paper at ICLR 2027

Reasoning with Sequence-Level Power Sampling by Stochastic Beam Search

Abstract

Reinforcement learning is the standard route to higher reasoning accuracy in large language models, and several recent analyses attribute its gains to sharpening a distribution the base model already carries rather than to acquiring new capabilities. Obtaining that sharpening through RL carries three costs: it needs a verifier, it needs a curated training set, and it rewrites the weights, so the gain is confined to mechanically checkable domains and is paid for elsewhere. Sampling the sequence-level power distribution gives the same sharpening from the base model alone, with no verifier, no dataset and no weight update, but is not autoregressive: Markov chain Monte Carlo samples it correctly, but costs much time per candidate comparing to sample from the base model directly. In this work, we show that stochastic beam search samples exactly once every prefix is scored by its power-weighted subtree mass, give a one-token lookahead estimator of that quantity, and show that omitting it reduces the sampler to low-temperature decoding. The method returns candidates without replacement from one batched decode, at approximately the base model's cost per candidate. Evaluating three models on MATH500, HumanEval and GPQA Diamond, our sampler is more accurate than MCMC power sampling and GRPO on single-shot accuracy, while returning more distinct answers per query than either. Furthermore, this method can be applied to any model exposing token log-probabilities.

Primary area:
foundation or frontier models, including LLMs
Keywords:
sampling methods, large language models, reasoning

Reviews

Among:
Shape:
1234this paper, Top 17%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.75 over 4 reviews, above 83% of the others.
Reviewer_PYueOpenReview ↗
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

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=1923072/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)\min(1, r) for the rewrite, where rr is the Metropolis-Hastings ratio. A single returned sample therefore costs 16×10=16016 \times 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 ×\times) problems, Qwen2.5-Math-7B, α=4\alpha = 4, k=8k = 8, 3072-token budget.

samplers / cand.avg. lengthtokens / cand.× base
base, α=1\alpha = 17.57787781.0
MCMC (Karan & Du)294.66311276016.4
ours, k=8k = 89.656935584.6

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-NN, vote, weighted vote and pass@8) to the same k=8k = 8 candidates for every sampler, and the arm the reviewer mentions is its second row: plain voting over eight τ=0.25\tau = 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λzie^{\lambda z_i}, with ziz_i 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 πβ\pi_\beta exactly is infeasible: the number of sequences is ∣V∣T|\mathcal{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^,∣,πα)-H(\hat q) - \mathrm{KL}(\hat q \\,\\|\\, \pi_\alpha), so minimizing the KL divergence is the same as maximizing the likelihood, and the mean log-likelihood of a sampler's own draws under πα\pi_\alpha measures how far that sampler sits from the target. Taking πα∝p4\pi_\alpha \propto p^{4}, 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.

Q3. (full proof of Theorem 2)

Assume that x(ℓ)∼πβ(x~(ℓ))\mathbf{x}^{(\ell)} \sim \pi_{\beta}(\tilde{\mathbf{x}}^{(\ell)}), 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 u′\mathbf{u}' with ∣u′∣=j|\mathbf{u}'| = j.

We now prove that Sj:ℓ+1(u)≥Sj:ℓ+1(u′)S^{j:\ell+1}(\mathbf{u}) \geq S^{j:\ell+1}(\mathbf{u}'). 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 u′\mathbf{u}' with ∣u′∣=ℓ|\mathbf{u}'| = \ell and any token v′v', 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:

methodcand.s / problemtokens / cand.one-shotpass@8
SPS (Ji et al. 2026)8136.9353780.8200.870
Power-SMC (Azizi et al. 2026)8720.0470500.7960.844
PoBS (ours)876.935580.8280.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,

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

Please see above

Critical strengths

Please see above

Critical weaknesses

Please see above

Questions for authors

Please see above

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

In this paper, the authors target sampling from the sequence level power distribution without trying to incur the cost in time of the original baseline. To rectify this cost, the authors employ a recursive computation scheme based on the Softmax-Gumbel trick, using a tree-based decomposition to generate samples from the power distribution. On Qwen 2.5 and DeepSeek models, the chosen samples consistently outperform GRPO, often by wide margins, both in and out of distribution. In addition, the pass@k curves are strictly stronger than MCMC power sampling as well as GRPO, with natural performance scaling with beam-width.

Critical strengths
  • The performance is exceptionally strong, surpassing GRPO for each of the baselines while also exhibiting a strictly stronger pass@k curve.

  • Very nice inference time scaling behavior with beam-width

  • Clever use of Gumbel-Softmax for power sampling

Critical weaknesses
  • This might be a subtle point, but in Theorem 2, is (12) meant to be over xl+1x^{l+1} or xlx^{l}? If it is l+1l+1, some further details/explanation might be needed for the proof for Theorem 2, since the prior of drawing a prefix uu from the prior over sequences of length ll restricted to length jj might be different from those drawn over sequences of length l+1l+1 restricted to length jj.
Questions for authors
  • Could the authors report the inference-time cost in terms of number of tokens expended during Algorithm 1?

  • For the distribution flattening results in the appendix, is the takeaway that using a high-temperature sampler for a posttrained model recovers pass@k performance without substantially harming the single-shot accuracy gains? Is there a sense where "base model diversity" is still accessible from the posttrained distribution with the right sampler?

  • Based on the sampled solutions, it seems like your rollout lengths are shorter than those for MCMC; is the stochastic beam sampler able to avoid verbosity while maintaining correctness, in contrast to MCMC/GRPO?

4 comments

Dear Reviewer Ya9d,

Thank you for your insightful feedbacks and comments for our work.

Q1. (inference-cost about tokens expended)

We report cost as forward-pass token positions, counting candidates that are later discarded. For Algorithm 1 at beam width kk and length LL it is kLkL positions for the beam itself, plus the rows spent on the one-token lookahead for log⁡Z^\log\widehat{Z}. Every arm below ran in one process on one A100-80G over the same 100 MATH500 problems, Qwen2.5-Math-7B, α=4\alpha = 4, k=8k = 8, 3072-token budget.

Number of tokens extended per method

samplers / cand.avg. lengthtokens / cand.× base
base, α=1\alpha = 17.57787781.0
MCMC (Karan & Du)294.66311276016.4
ours, k=8k = 89.656935584.6

Our Algorithm 1 expends 4.6×4.6\times the tokens compared to the base sampler, and 84% of that is the lookahead (2,989 of 3,558 positions per candidate), not the beam, which costs only L=569L = 569.

Q2. (flatten distribution result)

The result itself is as the appendix reports it: on DeepSeek-Math-7B-RL, PoBS with β=1.2\beta = 1.2 reaches 0.488 one-shot and 0.738 pass@8, against 0.374 and 0.678 for base sampling, so in the flattening regime the sampler does improve pass@k over the base sampler without giving up one-shot accuracy, which is the pattern the reviewer describes. What we cannot do is promote that to the general takeaway, because the behaviour is not monotone in β\beta.

At a larger value, for example β=4\beta = 4, the sampler degenerates rather than improving further. So the useful flattening behaviour is specific to the regime we explored at β=1.2\beta = 1.2, not a direction one can push: "use a higher temperature" is the wrong summary of it. Recovering pass@k without hurting single-shot accuracy is a direction we will investigate further in future work.

Q3. (compare the length between PoBS(ours) and MCMC)

Our sampler searches a tree and scores each prefix with a one-token lookahead, $\alpha \log p(\mathbf{u}) + \log \widehat{Z}(\mathbf{u})$, so the score already carries an estimate of the power mass of the whole subtree below u\mathbf{u}. A prefix is therefore judged before it is extended, and a path going nowhere is dropped at that step rather than after it has been written out. Each token is written once based on what the previous step established and carried forward, and is never revisited.

Metropolis–Hastings works in another way. It grows the sequence in blocks and then repeatedly picks a cut point uniformly inside the text it has already written, discards everything after it, regenerates that suffix by temperature sampling, and keeps or rejects the result on the ratio of power scores. The proposal carries no lookahead, so it has no signal about whether a continuation will reach an answer, and each repair starts from a mid-sequence state with no memory of the attempt it replaces; progress comes from re-rolling rather than from what the previous step established. The chain consequently keeps searching for longer before it ends up to a good candidate, which often results in longer length.

Dear Reviewer Ya9d,

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,

Thanks for addressing the points I raised! I maintain my original positive assessment of the work!

Dear,

Thank you very much again for taking the time to read our responses. We are grateful for your positive assessment and also truly appreciate your constructive feedback, which has helped us improve the clarity and quality of our paper. We will incorporate the suggested revisions and additional results into the final version.

Best regards.

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

The paper proposes Power Stochastic Beam Search (PoBS), a training-free decoding method targeting the sequence-level power distribution. It extends stochastic beam search with a power-weighted subtree correction, approximates this correction using one-token lookahead, and selects an answer through weighted voting over multiple candidates. Experiments on three 7B models across MATH500, HumanEval, and GPQA evaluate accuracy, candidate coverage, and inference time against standard sampling, low-temperature decoding, MCMC, beam search, and GRPO.

Critical strengths
  • The method addresses a useful practical problem: reducing the cost of sequence-level power sampling without training or a verifier. Building on stochastic beam search, the lookahead correction provides a concrete approach to generating multiple distinct candidates efficiently. Table 2 reports 77 seconds for eight PoBS candidates, compared with 295 seconds for one MCMC sample.

  • The experiments show promising performance across mathematical reasoning, code generation, and scientific questions. The selection-rule ablation is particularly useful: under the same weighted-voting rule, PoBS achieves 0.828 on MATH500 versus 0.790 for MCMC and 0.818 for GRPO (Table 4). This provides some evidence of a benefit beyond answer selection alone.

Critical weaknesses
  • Theorem 2 appears incorrect as stated. Extending a prefix sampled from the length-(\ell) power distribution cannot generally produce the length-(\ell+1) power distribution, because increasing the horizon changes the required marginal over the existing prefix. For example, let two first-token branches have equal probability and deterministic second tokens. If the third token is deterministic under one branch and uniform over two tokens under the other, their first-token probabilities change from (1/2,1/2) at horizon two to (2/3,1/3) at horizon three when (\beta=1/2). Appending a token cannot make this adjustment. Appendix A.5 does not resolve this issue, and the practical surrogate has no quantified approximation guarantee. This undermines the central distributional justification.

  • The evaluation does not cleanly establish the claimed single-sample improvement. PoBS’s headline accuracy uses weighted voting over eight candidates. Table 4 reports native accuracy of 0.692, below MCMC’s 0.714 and GRPO’s 0.772; voting raises PoBS to 0.828. Figure 1 nevertheless places 0.828 at (k=1), making candidate-budget comparisons unclear. Under matched weighted voting, the advantage over GRPO is only one percentage point, with no uncertainty estimates. The results support a promising multi-candidate pipeline, but do not establish the stronger claims about single-sample accuracy and superior coverage at every budget.

Questions for authors
  1. How can Theorem 2 account for the change in prefix marginals when the horizon increases? What corrected guarantee applies to Algorithm 1?

  2. For Table 1 and Figure 1, how many candidates are generated and used for selection by each method? Please distinguish native-sample accuracy, voting accuracy, and Pass@(k), and report uncertainty for the matched comparisons.

  3. At fixed candidate budget and selection rule, how much improvement comes from the lookahead correction itself? An ablation removing this correction would materially clarify the contribution.

6 comments

Dear Reviewer dpi3,

Thank you for your insightful feedbacks and comments for our work.

Q2. (how many candidates each method uses, the selection rule and the uncertainty)

For the three rules the reviewer mentions: "native-sample accuracy" means submitting the candidate the sampler ranks first among the kk beam candidates; "vote" means consulting all kk, grouping them by extracted answer and submitting the most confident member of the heaviest group; "pass@k" counts a problem correct if any of the kk is correct.

Candidates generated and used, row by row of Table 1:

Table 1 rowgeneratedusedrule for the reported number
Base, τ=1.0\tau = 1.011the draw itself
Low-temperature, τ=0.25\tau = 0.2511the draw itself
MCMC power sampling11the chain's output
GRPO11the draw itself
Base + beam search81its own top-ranked beam
PoBS (ours)88weighted vote, λ=0.5\lambda = 0.5

Our arm was run end to end three times on MATH500 with Qwen2.5-Math-7B (n=3n = 3, mean ± sample sd):

rulerun 1run 2run 3mean ± sd
one-shot (weighted vote)0.8280.8020.7810.804 ± 0.024
pass@80.8840.8780.8620.875 ± 0.011

Q3. (the gain by the look-ahead token)

We ran that ablation, at fixed candidate budget (k=8k = 8) and under the same selection rule, removing only the one-token lookahead log⁡Z^\log \widehat{Z} from the child score and changing nothing else. On MATH500 with Qwen2.5-Math-7B, single-shot accuracy falls from 0.828 to 0.768, so 6.0 points come from the correction itself. That term is what carries the power-weighted mass of the subtree below a prefix, so without it a prefix is scored by its own probability alone and the beam samples the token-wise tempered distribution instead of pαp^{\alpha}; the 6.0 points are what sampling the wrong target costs at an same budget.

Critical Weakness. We already modified and provided the full proof for Theorem 2 in the revised version. For the Theorem 2, if the sampled score S(j+1):(ℓ+1)(u⊕v)S^{(j+1):(\ell+1)}(\textbf{u} \oplus v) satisfies the max condition in the Eq.(10), the Theorem 2 will be correct. This is our proof:

Assume that x(ℓ)∼πβ(x~(ℓ))\mathbf{x}^{(\ell)} \sim \pi_{\beta}(\tilde{\mathbf{x}}^{(\ell)}), 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 u′\mathbf{u}' with ∣u′∣=j|\mathbf{u}'| = j.

We now prove that Sj:ℓ+1(u)≥Sj:ℓ+1(u′)S^{j:\ell+1}(\mathbf{u}) \geq S^{j:\ell+1}(\mathbf{u}'). 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 u′\mathbf{u}' with ∣u′∣=ℓ|\mathbf{u}'| = \ell and any token v′v', 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.

In our Algorithm 1, we use a modified sampling version, described in the Lemma 2, to sample the scores S~\widetilde S instead of SS. Lemma 2 is a modified sampling process that maintains the max-pin rescales the drawn scores so that their maximum equals the prefix's score exactly, while leaving them distributed as those same Gumbel scores conditioned on that maximum

In our main experiment, we report our method with weighted-voting strategy as our main result. Because, compare to the most relevant baseline MCMC, in practice, MCMC generation proceeds in 16 blocks of 3072/16=1923072/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 better one is selected by the Metropolis-Hasting and this process repeats through other candidates. Therefore, we also investigate comparing methods among our sampled candidates but only at the end of sampling process and through the results shown in the appendix (Table 4), we select weighted vote for the main result and it is a component of our method, proposed in the method section alongside the sampler, it weights each candidate by the confidence the sampler itself produces (eλzie^{\lambda z_i}, with ziz_i the mean per-token log-probability standardised within the problem)

Q1. (what Theorem 2 can still guarantee once the horizon moves)

Algorithm 1 is a recursion process. Assume a prefix u\mathbf{u} of length jj good when it is distributed as the first jj tokens of a draw from πβ\pi_\beta and the score it carries is the Gumbel score located at the log power mass of everything still reachable below it. Theorem 2 is the step that moves this forward by one token: given a good prefix, the token v⋆v^{\star} selected makes u⊕v⋆\mathbf{u} \oplus v^{\star} become a good prefix at length j+1j + 1. Algorithm 1 applies that step until the prefix is complete, and the statement at the final step is exactly that the output is a draw from the target.

What makes each step of that recursion valid is the max condition: the prefix's own score must be the largest score among its children. Every step of the proof uses it, so it is necessary for the guarantee and not a convenience, and without it the move from a good length-jj prefix to a good length-(j+1)(j+1) prefix does not go through. In practice there is no way to make that condition simply hold. We draw the children's scores at random from the Gumbel law of Theorem 1, and nothing in a random draw forces their maximum onto the score the prefix is already carrying. Lemma 2 is a modified sampling procedure that maintains it: the max-pin rescales the drawn scores so that their maximum equals the prefix's score exactly, while leaving them distributed as those same Gumbel scores conditioned on that maximum. If the condition is maintained at every step, which is what the pin is for, then u⊕v⋆\mathbf{u} \oplus v^{\star} is again a good prefix, and the recursion carries the property from the empty prefix to the full sequence.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.