acceptodds
Under review as a conference paper at ICLR 2027

Beam Search as Test-Time Self-Distillation via Counterfactual Contexts

Abstract

Self-Distillation Fine-Tuning (SDFT) enables a language model to act as its own teacher: by conditioning on a demonstration, the model produces an implicit reward via pointwise mutual information, which guides on-policy learning without external supervision. However, SDFT operates at *training time*: it requires gradient updates and access to expert demonstrations, making it inapplicable at inference. We propose *test-time self-distillation*, a decoding-time method that extracts a steering signal from the self-distillation framework without any parameter updates, reward models, or training data. Our key insight is that *counterfactual contexts*, i.e. fixed textual templates that hypothetically prime the model for excellent versus poor reasoning, can substitute for the demonstration. The log-odds ratio of a candidate answer under these two counterfactual conditions defines a new reward signal. We derive the optimal KL-regularized policy under this reward, which takes the form of a Gibbs reweighting of the base distribution. Crucially, this reweighting is global: it cannot be decomposed into independent per-token operations without ignoring future trajectory quality. We therefore approximate the target distribution via beam search. Experiments on mathematical reasoning (MATH500), code generation (HumanEval), and graduate-level science QA (GPQA) across multiple model scales show that test-time self-distillation improves over standard sampling, low temperature, beam search and power sampling baselines on average, demonstrating that the self-distillation principle can be operationalized at inference time.

Primary area:
foundation or frontier models, including LLMs
Keywords:
test-time inference, self-distillation, beam search

Reviews

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

The author proposed Contrastive Bean Search (CBS) for improving LLM reasoning at test time when not using additional training or external reward models. This method compares the likelihood of a reasoning trajectory under positive and negative reasoning contexts to construct a reward signal. Then, this reward is used to guide beam search toward better reasoning paths. Theoretical analysis was also performed to explain why this approach works better than token-level decoding. Overall, the experiments across models and benchmarks show that CBS also outperforms standard sampling and power sampling.

Critical strengths

Overall, the method is simple and has strong results.

First, the authors show that without external reward model or additional training, it is possible to increase the reasoning capability. This is already valuable to the field. Without a reward model, the author uses positive and negative reasoning context to construct a reward signal from the model itself. I also like the fact that the method guides the reasoning process during generation not just select the best trajectory or answer after the generation.

Second, the CBS not just perform better than standard beam search and power sampling. Using ablation study, the authors also show that the improvement mainly comes from the semantic information in the reasoning contexts, not just simply adding more context to the prompt. They also study different beam sizes and block sizes which shows the improvement is not just due to using more computation. I think these analysis make the method more convincing.

Critical weaknesses

Overall, this is a strong method paper. However, I think there are 2 weaknesses:

First, I think the idea of using positive and negative reasoning contexts is interesting. I am curious whether both positive and negative contexts are necessary for the improvements. For example, I want to see an ablation that uses only the positive context or only the negative context as the reward signal. This would help calrify whether the improvement comes from contrasting the two contexts or just from one of them.

Second, I appreciate that the authors provide theoretical analysis of the approximation error. However, the error mainly focuses on the error from ignoring future rewards, but the actual CBS algorithm also involves beam pruning, replication, and length normalized scoring. These operations may introduce additional approximation errors which are not covered by the theory from the paper. Therefore, I think it is not clear to me how well the theoretical results explain the behavior of the method.

Questions for authors

Overall, this is a good paper but I still have 2 minor questions on the computational efficiency and theoretical analysis.

First, since CBS requires more computation than standard beam search, I wonder whether the improvements are still large when different methods use the same compute budget. Maybe the authors can provide a direct performance comparison with power sampling and standard beam search under matched compute budgets?

Second, as I mentioned in the weaknesses, the real CBS uses beam pruning, replication, and length normalized scoring. So, I am curious whether these operations introduce additional approximation errors. So, can the authors explain it under the full CBS algorithm?

1 comment

We thank the reviewer for a careful and hand-written review. We are glad the reviewer finds the method simple and effective without an external reward model or training, and finds the ablations convincing on where the gains come from.

W1. ... I am curious whether both positive and negative contexts are necessary for the improvements. ... an ablation that uses only the positive context or only the negative context as the reward signal.

Thank you for the suggestion. We ran this ablation and found that, interestingly, neither context alone recovers the full gain of the pair. We use Qwen2.5-7B and the same search (N=16N=16, W=4W=4, K=32K=32, 1/α=0.251/\alpha=0.25). Only the reward changes:

  • No context: no reward, i.e. the Beam Search baseline of Table 1.
  • Neutral: the control pair of Table 2 ("control group one" / "control group two"), with no quality preference.
  • Positive-only: R+=log⁡πθ(a∣q,c+)R^+=\log\pi_\theta(a\mid q,c^+).
  • Negative-only: R−=−log⁡πθ(a∣q,c−)R^-=- \log\pi_\theta(a\mid q,c^-).
  • Contrastive: R=log⁡πθ(a∣q,c+)−log⁡πθ(a∣q,c−)R=\log\pi_\theta(a\mid q,c^+)-\log\pi_\theta(a\mid q,c^-), i.e. CBS.
RewardMATH500HumanEvalGPQA
No context0.5700.7070.247
Neutral0.5660.6590.278
Positive-only0.5800.7070.253
Negative-only0.5820.7320.263
Contrastive0.6100.7440.313

Table R1: Ablation of positive and negative contexts.

The pair is best on all three benchmarks. Each context alone gives at most a small gain over no context.

So the full improvement comes from contrasting the two contexts. This matches the motivation of the reward: without a demonstration there is no reference for absolute quality, and the usable signal is the model's relative assessment between two contexts. We will add this ablation to the paper.

Q1. ... a direct performance comparison with power sampling and standard beam search under matched compute budgets?

For standard beam search, the paper already reports a comparison on MATH500 in which beam search has a larger budget (Figure 1 and Table 3). We report compute both as generated tokens (including discarded candidates) and as wall-clock time per question, because the two differ since the scoring passes of CBS cost time but generate no tokens. With N=24N=24 beam search generates 1.7x as many tokens as CBS with N=16N=16 and takes 1.1x to 1.4x as long (Figure 1). It still stays below the best CBS setting on all four models, and below 7 of the 8 CBS settings, by up to 8.9 points (Table 3).

For power sampling, we additionally measured its cost on MATH500 below (accuracy is from Table 1).

MethodTime (s)Generated tokens (k)MATH500
Qwen2.5-7B
Power sampling τ=0.25\tau=0.259.289.10.626
Power sampling τ=1.0\tau=1.010.199.00.450
CBS 1/α=0.251/\alpha=0.2513.06.50.610
CBS 1/α=0.71/\alpha=0.714.06.90.640
DeepSeek-Math-7B-Instruct
Power sampling τ=0.25\tau=0.2513.597.00.430
Power sampling τ=1.0\tau=1.014.7104.30.410
CBS 1/α=0.251/\alpha=0.2513.35.50.462
CBS 1/α=0.71/\alpha=0.711.45.20.458

Table R2: Power sampling vs CBS costs.

CBS generates about 14x to 19x fewer tokens than the power sampling baseline. This is expected since the power sampling baseline generates 16 chunk candidates with 16 future rollouts each, while CBS does not perform those future rollouts. On DeepSeek-Math-7B-Instruct the time is matched (CBS takes 0.85x to 0.99x the time of the better power-sampling setting) and CBS is 2.8 to 3.2 points more accurate. On Qwen2.5-7B, CBS is 1.4x to 1.5x slower and the accuracy is comparable.

We will add this comparison to the appendix.

W2 / Q2. ... These operations may introduce additional approximation errors which are not covered by the theory ... can the authors explain it under the full CBS algorithm?

We agree that Theorem 1 covers only the error from ignoring future reward, in an idealised procedure where each chunk is drawn exactly. Reviewer g44s raised the same point, so we would kindly ask you to see our detailed answer to W2 (https://openreview.net/forum?id=zYUHbTHUw6&noteId=XsAIxxANmv).

In short:

  • Length normalisation adds no error during the search: beams compared at a pruning step have the same length. It only affects the final selection.
  • Pruning and replication add error that the theorem does not cover. However, the beam search baseline runs the same operations, so this error cannot explain the gain of CBS over it.
  • The bound on the score carries over to Algorithm 1: CBS can discard a partial answer that is better under the target than one it keeps only if the two are within 2εt2\varepsilon_t, with εt=(T−t−K)⋅rmax⁡/α\varepsilon_t=(T-t-K)\cdot r_{\max}/\alpha.

We will state Theorem 1 for the idealised procedure, and add this as a corollary and a remark.


We hope this addresses your concerns. We are happy to clarify anything further.

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

This work proposes test-time self distillation with beam-search. The core intuition is to construct the estimation between good/bad reasoning trace. The estimaiton is done by the inference model itself with the Gibbs distribution reweighing.

The method is training freee and cost about 1.5 times to normal beam searches, and is positive for the 4 experimented models on code/math/science QA.

In the authors analysis, the Gibbs reweighing is global and correct the forward future bias by simply per-token decoding.

Critical strengths
  1. The method is examined with abundant experiment settings such as math/code/science QA with four base LLMs. This helps validate that the method is potentially useful on more complex tasks (such as agentic coding/working and larger LLM scales)

  2. This work draws back attention on how to construct the win/lose pair probability gap. I believe this work's idea is potentially useful on multiple win/lose pair gap estimations. And also it woudl also be intersting to research unequal positive/negative sample scenarios.

Critical weaknesses
  1. The primary weakness is would be model scale. Since the method is test-time optimization, I would wonder its adaptation to 10^2B~TB scale model inferences.
Questions for authors
  1. Why would the authors use counterfactual samples to replace the win/lose samples? The two distribution differences is not the same and cannot be simply converted when it comes to gap estimation. I might want to list this as a weakness, but it could be my miss to capture the introduction to the problem.
2 comments

We thank the reviewer for the positive and constructive assessment, and for seeing the potential of the idea beyond the settings we tested.

W1. The primary weakness ... would be model scale. Since the method is test-time optimization, I would wonder its adaptation to 10^2B~TB scale model inferences.

We ran all three benchmarks on gpt-oss-120b. It sits at the 10210^2B scale the reviewer asks about, comes from a different model family than the Qwen and DeepSeek models in the paper, and is a far stronger base model (65.7% on GPQA, against at most 29.8% for the base models in Table 1). The protocol and hyperparameters are those of Table 1 (N=16N=16, W=4W=4, K=32K=32); nothing was re-tuned for this model.

gpt-oss-120bMATH500HumanEvalGPQA
Base (τ=1.0\tau=1.0)0.9280.8660.657
Low temperature (τ=0.25\tau=0.25)0.9360.8880.682
Beam search0.9300.8780.692
Power sampling (τ=0.25\tau=0.25)0.8920.8540.712
CBS (1/α=0.251/\alpha=0.25)0.9420.8780.702
CBS (1/α=0.71/\alpha=0.7)0.9460.8900.738

Table R3: Results on gpt-oss-120b.

CBS with 1/α=0.71/\alpha=0.7 obtains the highest accuracy on all three benchmarks. For the smaller models the preferred steering strength depended on the model and the task; at this scale a single value seems to be enough. GPQA is the only benchmark that is not close to saturation for this model. There, CBS improves by +8.1 points over the base model, +5.6 over low temperature, +4.6 over standard beam search and +2.6 over power sampling.

Power sampling, which sharpens the model's own likelihood, falls below the base model on MATH500 and HumanEval for this model. Standard beam search stays below CBS with 1/α=0.71/\alpha=0.7. The contrastive signal therefore contributes information that likelihood alone does not. A hypothesis we find plausible, but do not claim to have established: a stronger model is also a better judge of what "excellent" versus "wrong" reasoning looks like, so the quality of the contrastive signal could grow with model capability even as benchmark headroom shrinks.

Regarding cost, CBS performs no parameter optimization at test time: no gradients, no auxiliary reward model, only forward passes of the frozen model. There is therefore nothing to adapt as models grow. The overhead over standard beam search is two additional scoring passes per chunk.

We will add the gpt-oss-120b results to the paper.

Q1. Why would the authors use counterfactual samples to replace the win/lose samples? The two distribution differences is not the same and cannot be simply converted when it comes to gap estimation.

We agree the gap between two counterfactual conditionals is not the same object as the gap between true "win" and "lose" distributions, and one cannot simply be converted into the other. Our method neither assumes nor needs such a conversion:

  • There are no win/lose samples in our setting. At test time we have one question, a frozen model, and no labels, verifier or demonstrations. Building win/lose pairs requires knowing which answers are correct, which is exactly the information that is missing. The contexts therefore do not replace win/lose samples; they replace the expert demonstration cc of SDFT, which is unavailable at inference.
  • No counterfactual samples are ever drawn. c+c^+ and c−c^- are two fixed sentences, not samples. Every candidate is sampled from the base model πθ(⋅∣q)\pi_\theta(\cdot \mid q) only (Algorithm 1), and the contexts are used solely to re-score that same candidate (Eq. 9). The "pair" in our reward is thus a pair of conditions applied to one answer, whereas in DPO it is a pair of answers under one model.

What the gap measures is the model's own relative assessment of one answer under the two contexts. It is a label-free proxy, and the evidence that it tracks quality is empirical: a neutral pair gives no gain (Table 2).

We will rewrite the Bradley–Terry remark to state explicitly that the pair is a pair of contexts for one answer, not a pair of answers.

Strengths. ... it would also be interesting to research unequal positive/negative sample scenarios.

We have obtained additional results on the two extreme cases of this scenario. Reviewer cgQK asked whether both contexts are necessary, and we ran an ablation that uses only the positive or only the negative context as the reward in Table R1 (https://openreview.net/forum?id=zYUHbTHUw6&noteId=8B3hlh2ApX).

In summary, neither context alone recovers the gain of the context pair.


We hope the new results resolve the concern on model scale and that the clarification answers the question on counterfactual contexts. We are happy to clarify anything further.

Reviewer_6KiuOpenReview ↗

Acknowledge of response

Thanks for the clarification. I decided to maintain my current recommendation.

p.s. It would be cool if this method can be generalized to difficult tasks, where an LLM would only perform near random baselines but largely boosted by CBS.

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

The paper proposes the use of simple counterfactual prompts to identify good responses from bad ones at decode time. In particular, two static prompts, one encouraging correct reasoning and the other flawed reasoning, are used to distinguish responses that are favored by "good" prompt over the ones favored by "bad" prompt. While the proposed method seems promising based on results, the paper does not explore some obvious variations. It also provides error bounds under the assumption that chunk level samples are performed exactly, however the actual algorithm does not sample exactly even at chunk level.

Critical strengths

The proposed reward signal is simple and easy to come by in test time setup. The reported results show gains over simple beam search and power sampling.

Critical weaknesses
  • The idea of counterfactual prompts for reward computation is not new and hence can not be counted as primary contribution of the paper. In fact the authors cite a paper [1] that does exactly that but for avoiding hallucination.
  • The counds shown in theorem 1 assume exact chunk level sampling, however the actual algorithm is approcimate even at chunk level, hence the bounds dont apply.
  • The Algorithm 1 shows that samples are generated using base model ... however due to token -evel decomposition of reward, the sampling distribution could have easily been the reward weighted local per token distribution .... using that as sampling distribution would have given much better chances of finding a sample from true target distribution than just using base model. The authors must try this variation, because it not only would have made the sampling better, it would have brought the work much closer to [1], with only remaining difference being chunk-based beam search. This will show if chunk-based beam has any additional benefits at that point compared to simple beam . because currently the reward is only computed at chunk boundaries, confounding the usefulness of reward in deciding trajectories with usefulness of beam+chunks in retaining good trajectories.
  1. "Improving factuality by contrastive decoding with factual and hallucination prompts" Bojie Lv, Ao Feng, and Chenlong Xie
Questions for authors

The Algorithm 1 shows that samples are generated using base model ... however due to token -evel decomposition of reward, the sampling distribution could have easily been the reward weighted local per token distribution .... using that as sampling distribution would have given much better chances of finding a sample from true target distribution than just using base model. The authors must try this variation, because it not only would have made the sampling better, it would have brought the work much closer to [1], with only remaining difference being chunk-based beam search. This will show if chunk-based beam has any additional benefits at that point compared to simple beam . because currently the reward is only computed at chunk boundaries, confounding the usefulness of reward in deciding trajectories with usefulness of beam+chunks in retaining good trajectories.

  1. "Improving factuality by contrastive decoding with factual and hallucination prompts" Bojie Lv, Ao Feng, and Chenlong Xie
4 comments

We thank the reviewer for a careful and hand-written review. We are glad the reviewer finds our reward signal simple and easy to obtain at test time, and notes the gains of CBS over beam search and power sampling.

W1. The idea of counterfactual prompts for reward computation is not new ... the authors cite a paper [1] that does exactly that but for avoiding hallucination.

... it would have brought the work much closer to [1], with only remaining difference being chunk-based beam search.

We do share the use of contrast between the token distributions under two prompts with Lv et al. [1], but our target distributions are different. They apply this contrast directly as a decoding rule. It is not posed as a reward-maximisation problem: there is no objective, no reference policy and no regularisation term. What we claim as new is the formulation, in which the contrast becomes a trajectory-level reward inside a KL-regularised problem.

In our case, we define the reward R(q,a)=log⁡πθ(a∣q,c+)−log⁡πθ(a∣q,c−)R(q,a)=\log\pi_\theta(a\mid q,c^+)-\log\pi_\theta(a\mid q,c^-), and since we maximise Ea∼π[R(q,a)]−α⋅KL(π∥πθ(⋅∣q))\mathbb E_{a\sim\pi}[R(q,a)]-\alpha\cdot\mathrm{KL}(\pi\Vert\pi_\theta(\cdot\mid q)) the target distribution becomes

π⋆(a∣q)=1Z(q)⋅πθ(a∣q)⋅(πθ(a∣q,c+)πθ(a∣q,c−))1/α\pi^{\star}(a\mid q)=\frac{1}{Z(q)}\cdot\pi_\theta(a\mid q)\cdot\left(\frac{\pi_\theta(a\mid q,c^+)}{\pi_\theta(a\mid q,c^-)}\right)^{1/\alpha}

In their case,

πDFHP(a∣q)=∏t=1T1Zt(a<t)⋅πθ(at∣q,c+,a<t)πθ(at∣q,c−,a<t)β\pi^{\text{DFHP}}(a\mid q)=\prod_{t=1}^{T}\frac{1}{Z_t(a_{\lt t})}\cdot\frac{\pi_\theta(a_t\mid q,c^+,a_{\lt t})}{\pi_\theta(a_t\mid q,c^-,a_{\lt t})^{\beta}}

The two differ in two ways:

  1. Our distribution reweights πθ(⋅∣q)\pi_\theta(\cdot\mid q), the model the user actually queries. The contexts enter only through the reward. In [1], the unprompted model does not appear at all. Without steering (1/α→01/\alpha\to 0) ours is the base model, whereas [1] (β→0\beta\to 0) is the positive-prompted model. No choice of α\alpha and β\beta makes them coincide in general.
  2. Ours is normalised once over complete answers. [1] is normalised at every token, so a token is never weighed against the reward of what follows it. This is the same kind of gap as between low-temperature sampling, which sharpens each token and normalises locally, and the power distribution, which sharpens whole answers and normalises once [2].

The origin of RR also differs: it is the test-time counterpart of the SDFT reward log⁡π(a∣q,c)−log⁡π(a∣q)\log\pi(a\mid q,c)-\log\pi(a\mid q), with the demonstration, which is unavailable at test time, replaced by two counterfactual contexts. This places the method in the line of distribution sharpening: the power distribution [2] is a special case of a self-reinforcement reward.

On "only remaining difference being chunk-based beam search". This does not hold. Reward-weighted sampling would make our sampling step local, but the unprompted model πθ(⋅∣q)\pi_\theta(\cdot\mid q) would remain and it is absent from [1].

Nevertheless, we agree that [1] is the closest existing decoding rule and we will add the comparison to the paper (see below).

W3 / Question. ... the sampling distribution could have easily been the reward weighted local per token distribution ... This will show if chunk-based beam has any additional benefits at that point compared to simple beam ... currently the reward is only computed at chunk boundaries, confounding the usefulness of reward in deciding trajectories with usefulness of beam+chunks in retaining good trajectories.

We ran the variant you suggest and [1] itself, with and without our beam search, so that the comparison separates the two effects your comment asks about.

  • DFHP: the decoding rule of [1] (β=0.5\beta=0.5, as its authors recommend) with our contexts, without search.
  • DFHP+BS: tokens sampled with the rule of [1], inside our chunk-based beam search. Beams are ranked by [1]'s contrast accumulated over the partial answer.
  • CBS+RW (your suggestion): CBS but tokens sampled from the reward-weighted local distribution instead of the base distribution.
MethodMATH500HumanEvalGPQA
Qwen2.5-7B
DFHP [1]0.6320.6890.237
DFHP+BS0.6660.7130.242
CBS+RW0.6920.7380.268
CBS0.6100.7440.313
DeepSeek-Math-7B-Instruct
DFHP [1]0.3500.4390.192
DFHP+BS0.4100.4510.288
CBS+RW0.4580.4760.263
CBS0.4620.5120.369

Adding our beam search to DFHP improves it in all six settings, so chunk-based beam search keeps its value when tokens are already steered. However, even if we add beam search to DFHP, it beats CBS in only 1 of 6 settings and it costs 1.4x the inference time. Reward-weighted token sampling does not consistently help and costs 2.3x the inference time compared to CBS. Table 1's Beam Search is CBS without the reward: CBS beats it in all 12 settings.

We will add these baselines to Table 1 for all models.

[2] Karan and Du. "Reasoning with sampling: Your base model is smarter than you think." ICLR 2026.

to be continued ...

... continued

W2. The bounds shown in Theorem 1 assume exact chunk-level sampling, however the actual algorithm is approximate even at chunk level, hence the bounds don't apply.

Theorem 1 isolates one approximation of our method: ignoring the reward that a partial answer will still collect after the current chunk (the future correction ζ\zeta). It does so in an idealised setting where each chunk is drawn exactly. The statement says so, but some sentences can be read as a guarantee on Algorithm 1. We will reword them more clearly to refer to the idealised procedure.

Nevertheless, the analysis of Theorem 1 still constrains Algorithm 1. From Proposition 1 and the proof of Theorem 1, we know two facts about any partial answer aa scored after the chunk covering positions t+1t+1 to t+Kt+K.

  1. Its exact value under the target distribution is the score CBS computes plus the future correction. By the definition of the future correction ζ\zeta (Eq. 8), we have: log⁡π⋆(a∣q)+log⁡Z(q)=s^(a)+log⁡ζ(a)\log\pi^{\star}(a\mid q)+\log Z(q)=\hat s(a)+\log\zeta(a). The left side, written s(a)s(a) below, is the exact value, i.e. the log-probability that the target gives to all complete answers starting with aa (log⁡Z(q)\log Z(q) is the same for all candidates). s^(a)\hat s(a) is what CBS computes (the sum in Eq. 9), and log⁡ζ(a)\log\zeta(a) is the reward still to come.

  2. The future correction is bounded: ∣log⁡ζ(a)∣≤εt=(T−t−K)⋅rmax⁡/α\lvert\log\zeta(a)\rvert\le\varepsilon_t=(T-t-K)\cdot r_{\max}/\alpha. This depends only on how many tokens remain, so it holds for every partial answer however it was generated.

So the score CBS uses is within εt\varepsilon_t of the exact one, for every candidate. If CBS were to keep a′a' and to discard aa, so that s^(a)≤s^(a′)\hat s(a)\le\hat s(a'), then

s(a)≤s^(a)+εt≤s^(a′)+εt≤s(a′)+2εts(a)\le\hat s(a)+\varepsilon_t\le\hat s(a')+\varepsilon_t\le s(a')+2\varepsilon_t

CBS can therefore discard a partial answer that is better under the target than one it keeps only if their exact values are within 2εt2\varepsilon_t. Both conclusions the paper draws from Theorem 1 thus carry over to Algorithm 1 in this form: the margin shrinks linearly to zero as the answer is completed, and scoring chunks instead of tokens shortens the ignored horizon and takes T/KT/K decisions instead of TT.

Apart from the score, Algorithm 1 is identical to our beam search baseline: the same operations with the same settings. Any error they introduce is therefore shared with the baseline:

  1. Pruning: The NN candidates are ranked by score and the best N/WN/W are kept. Misranking caused by the score is the case bounded above. What pruning itself adds is common to every beam search: a finite number of beams can lose the beginning of the best answer even with exact scores.
  2. Replication: Each kept partial answer is copied WW times and each copy draws its own next chunk from the base model. All next tokens can be enumerated, but not all KK-token chunks, so WW of them are sampled. Drawing them from πθ(⋅∣q)\pi_\theta(\cdot\mid q) is consistent with our target: π⋆\pi^{\star} only reweights answers that πθ\pi_\theta can generate, so every answer in its support can be proposed. As in any sampling-based search, the number of good candidates found depends on NN and WW, and we do not claim a finite-sample guarantee for this step.
  3. Length normalisation: It adds no error to pruning: an unfinished beam always receives exactly KK new tokens, so active beams have the same length and ranking by the mean is ranking by the sum. It only acts at the end, to compare completed answers of different lengths by their average per-token score. Their scores are exact then (ζ=1\zeta=1). This is the usual correction of beam search against short outputs, identical in the baseline.

The gap has limited consequences:

  1. The one approximation specific to CBS, the truncated score, is bounded as above.
  2. Everything else is shared with the Beam Search baseline, so it cannot explain the gains over it.
  3. An exact sampler would also return lower-probability answers in proportion to their weight; a search returns the best one it finds. Benchmarks that grade one answer per question do not reward matching those proportions.

We will add this inequality as a corollary and the discussion of the three operations as a remark.


We hope this resolves the concerns about novelty and soundness, and that you will consider raising your score. We are happy to clarify anything further.

Thank you for evaluating the version where reward weighted local distribution is used for sampling. It sure confirms that chunk level reward reweighing is helping.

However, this brings another point to mind. What if the per token reward weighted locally normalized distribution was your true target ... in other words, what if you just sample from that and do not try to introduce any future correction via chunk level beam?

Thank you for raising your score and for the follow-up. We ran this variant on the two models of our previous table. In short: the local distribution is a valid target, but it is a different one from ours, and it is below CBS in 5 of 6 settings.

CBS−BS (CBS without beam search) samples every token from the locally normalised distribution of Eq. 6, π~(at∣q,a<t)∝πθ(at∣q,a<t)⋅exp⁡(rt(at,q)/α)\tilde\pi(a_t\mid q,a_{\lt t})\propto\pi_\theta(a_t\mid q,a_{\lt t})\cdot\exp(r_t(a_t,q)/\alpha), with the contexts and steering strength of CBS.

MethodMATH500HumanEvalGPQA
Qwen2.5-7B
CBS−BS0.6280.4940.253
CBS0.6100.7440.313
DeepSeek-Math-7B-Instruct
CBS−BS0.4160.4820.268
CBS0.4620.5120.369

CBS is higher in 5 of 6 settings, by 3.0 to 25.0 points. The exception is MATH500 on Qwen2.5-7B (1.8 points), where the other CBS setting of Table 1 (1/α=0.71/\alpha=0.7, 0.640) is above CBS−BS.

The reason is that the local rule optimises each token as if the answer ended there: the probability of a partial answer ignores the reward of what follows (ζt\zeta_t in Proposition 1), and the beam restores this by comparing partial answers with each other.

We will add CBS−BS to Table 1 for all models.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.