- 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?
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.
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=16, W=4, K=32, 1/α=0.25). Only the reward changes:
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.
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=24 beam search generates 1.7x as many tokens as CBS with N=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).
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.
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¬eId=XsAIxxANmv).
In short:
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.