Self-Evaluation Guided Beam Search for Reasoning

Summary

The paper proposes using a fine-grained self-evaluation method to refine multi-step reasoning inference of the Large Language Models. The authors propose a novel promting approach that integrates self-evaluation guidance through stochastic beam search. Concretely, to guide the beam search process, they employ LLM self-evaluation as an automatic criterion to offer the guiding signal. And they incorporate temperature-controlled randomness to optimize the traditional beam search algorithm in order to balance the quality-diversity trade-off for better reasoning chains. Experimental results of their methods on various arithmetic, symbolic, and commonsense reasoning tasks show considerable improvements.

Strengths

1. The authors propose a novel and general multi-step decoding method (a beam search variant) which employs LLM self-evaluation and temperature-controlled randomness. The method aims to improve LLM performance on reasoning tasks. 2. Extensive experiments are conducted on a wide range of reasoning benchmarks and considerable improvements are achieved. Besides, comprehensive ablations and running examples are presented to further demonstrate the effectiveness of their approach.

Weaknesses

The paper should be more self-contained. For example, the notion of self-evaluation is first used in the introduction section without a concise explanation, which makes it a bit hard to follow. And the details of the evaluation benchmark are not introduced (arithmetic, symbolic, and commonsense reasoning tasks).

Questions

Authors should concisely introduce the notions when they first use it (e.g., self-evaluation) to make the paper more self-contained. Besides, the details of the different evaluation benchmarks and compared baseline methods should be concisely introduced in the experiment section as well.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

2 fair

Contribution

3 good

Limitations

The authors have adequately addressed the limitations of their work.

Summary

The paper proposes a self-evaluation enhanced beam search for using LLMs on multi-step reasoning tasks. Specifically, in addition to standard beam search that only scores a beam based on the probability, the method further adjusts the score with a self-evaluation-based faithfulness score reflecting the correctness of intermediate reasoning steps. The score is obtained by LLMs using few-shot prompting and is calculated for each rollout. The paper applies this approach on several arithmetic reasoning tasks, symbolic reasoning tasks, and common sense reasoning tasks. The results suggest that the proposed beam search variant achieves better performance compared to greedy decoding. The paper also includes a series analysis on the effectiveness of calibration, sensitivity to hyper-parameters, etc.

Strengths

The proposed approach shows an application of self-calibration for multi-step reasoning tasks. The experiments cover three tasks and multiple datasets. The paper also includes a series of analyses providing more details on the effectiveness of calibration for reasoning tasks. The paper is well-written and easy to follow.

Weaknesses

1. The most critical issue is that the comparison in this paper is misleading. The paper draws the majority of attention to the comparison between the proposed beam-search-based approach against greedy decoding. It’s understood that both the greedy decoding and the beam search produce one single chain. But the proposed approach uses *beam search* and self-evaluation (which is also done by few-shot prompting). This is way more expensive than greedy decoding. Specifically, based on the hyper-parameter in Appendix A.3, the model uses beam size (k=5, and use n=16 rollouts for each beam). Assuming we evaluate a problem with steps T=3. In a rough estimation, this approach needs to call the API to generate 5 * 16 * (3 - 1) * 2 = 320 completions (there is a factor 2 because the approach also uses LLM to self-evaluate each rollout, and based on the appendix, the length of the evaluation prompt is at the same magnitude as the length of the few-shot prompt). Not that this estimation follows the way that OpenAI charges API calls, which charges both prompt and completion tokens, see https://openai.com/pricing. In contrast, greedy decoding only requires running 1 completion. There’s a distinct gap in the computation cost (320 vs 1 measured by API cost). Similarly, the computation cost in the multiple reasoning chains setup is also different. In short, the experiments and the interpretation of results need substantial refactoring. At least the paper should compare the proposed approach against baselines that uses the same amount of computation instead of producing the same number of reasoning chains. As a result, the improvements in Table 1 are inflated (E.g., considering PAL with 8 samples for self-consistency decoding can get ~78% performance on GSM8K as shown in Figure 12 in PAL). 2. At the same time, the core technical contribution of the proposed approach is a straightforward extension of beam search based on self-evaluation, it is hard to judge the empirical merits of the proposed approach without a fair, clear, and thorough comparison.

Questions

Can authors provide the exact cost (measured by API cost, or tokens being scored) for PAL and the proposed approach in the single chain setting of Table 1? When calculating $P_{LM}$, is the probability of a reasoning step normalized by the number of tokens?

Rating

3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.

Confidence

5: You are absolutely certain about your assessment. You are very familiar with the related work and checked the math/other details carefully.

Soundness

1 poor

Presentation

3 good

Contribution

1 poor

Limitations

Some limitations are discussed at the end of the paper; no obvious negative societal impact as far as I know.

Summary

The authors propose using beam search to guide each reasoning step in chain-of-thought prompting. Functionally, the paper is quite similar to the concurrent "Tree of Thoughts" work from Yao et al. (2023).

Strengths

Overall, it's a generally solid work. The experiments are reasonable and fairly comprehensive; the method, while not groundbreaking, is the natural next step of a lot of work in this area and is well-motivated; its figures are good and convey its message well; the results are generally positive - it would be very surprising to me if they weren't.

Weaknesses

Primary concerns: - Because the self-evaluation requires extra inference, it's not entirely obvious that all of the comparisons are fair, so it would be useful to see some discussion around this. There's also the overhead from being unable to cache preceding tokens, but that's an artifact of using an API. The paper doesn't seem to discuss details like the number of tokens generated or the number of beams used, which in general, make comparison hard. - The title is very confusing - this paper has little to do with "decomposition" since every step taken is sequential. This should really be fixed as it implies a very different message than the one actually made by the paper. Normally this wouldn't be a substantial issue, but in this case, it is especially confusing. - The writing could really use work - the phrasing is awkward and often nonstandard, like the first sentence of the abstract "We endow Large Language Models (LLMs) with fine-grained self-evaluation to refine multi-step reasoning inference." In general, the paper reads fairly awkwardly and is unnecessarily wordy. Other concerns: - The novelty of the paper seems to be in the use of model-probability-guided beam search itself, but in my view, the paper somewhat oversells the novelty of using model self-evaluation for selection. Even within the code domain there's lots of work on this, such as "Coder Reviewer Reranking for Code Generation" by Zhang et al. (2022). Plus, there is work on evaluating uncertainty with prompting which would probably even be better suited for this, like the concurrent "Semantic Uncertainty: Linguistic Invariances for Uncertainty Estimation in Natural Language Generation" by Kuhn et al. (2023). This is not to say that the paper is not novel, but the main novelty seems to be the use of self-guided beam search in general and not the "Self-Evaluation as Faithfulness Constraint." - This method isn't really possible with recent closed language models that don't expose logprobs (as mentioned), and it's not obvious how to integrate this. I also don't really feel that it's fair to refer to this as faithfulness.

Questions

How do you ensure the comparison with the other models is fair? How many beams do you use? For k beams, is it more useful to sample 2*k chains of thought?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

Reasonable discussion.

Summary

This paper proposes to improve the reasoning capability of large language models (LLMs) by decomposing the reasoning task into multiple steps and then performing self-evaluation guided beam search to find the optimal reasoning chain. On a set of arithmetic reasoning, symbolic reasoning, and commonsense reasoning tasks, the proposed method outperforms baselines in most cases. The paper also provided analysis regarding the quality-diversity trade-off in the generation of the reasoning chain.

Strengths

1. This paper proposed a novel and effective stochastic beam search which searches for multi-step reasoning. The approach integrates the LLM probability distribution and the self-evaluation faithfulness score. 2. The proposed method is evaluated on multiple datasets. The discussion and analyses are helpful.

Weaknesses

1. The proposed method is very costly, as it requires prompting the LLM for multiple times (when searching for next steps and for self evaluation). Its effectiveness also depends on the LLM search space, e.g., when an LLM is very confident with their (incorrect) reasoning, the potential of locating the correct steps in beam search will become small. 2. Some details are missing or require clarification: - How did the framework define one "step" in each reasoning dataset? For example, is every step a single statement for PAL and a complete sentence (i.e., ended with a period) for CoT? - Figure 4(a) is not referred to in the paper. It is unclear based on which dataset the two plots were drawn. The numbers on the plots also need more explanation. For example, in the left figure, why is PAL+SC so stable when changing the LM temperature (which I believe would end up with very different sets of samples in SC)? Similarly in the right figure, why is CoT+SC changing if it does not involve beam search at all (and hence should be agnostic to the change of the sampling temperature in Eq 4)? 3. Baseline: how does the proposed method compare with self-refinement (Madaan et al., 2023), which, instead of searching for better steps during reasoning, iteratively self-refines the reasoning output?

Questions

Please address my concerns and questions in Weaknesses.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

The paper included a limitations section.

Summary

The authors propose a self-evaluation guided strategy to improve the rationale decoding process from CoT sampling. They also explore ways to balance the quality of evaluation with diversity of generation. Overall, their approach work well on existing datasets and improve few-shot accuracy on multiple math and commonsense datasets. Additionally, their approach leads to more robust reasoning.

Strengths

* The ability to guide the rationale generation process via self quality evaluation and temperature-controlled randomness is an effective solution towards improving the decoding time performance and consistency of CoT sampling process * The work is timely in the community since CoT is a predominant way to generate rationales using LLMs. This approach can help the effort in improving robustness of these rationales

Weaknesses

* Since the stepwise self-evaluation involves multiple calls to the base LLM, this adds an overall overhead both in terms of compute and cost. There is no discussion regarding this in the paper. This restricts the reader to understand the feasibility of such an approach. Please include some time and cost analysis with and without the self-evaluation based search. I understand that the authors point some of these in the limitations, but I strongly believe they are crucial to have in the paper. * Can you consider results on more recent models that do provide logits (say GPT3) to showcase the utility of this approach even in the more recent models? This is optional, but a good to have analysis on a few datasets (say StrategyQA and GSM8K).

Questions

* How are the different hyper-parameters ($\alpha, \lambda$, etc.) tuned? Or do you use some generic settings for all datasets?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

N/A

Response to authors

Thanks for clarifying my concerns. I appreciate adding results for the latest LLaMA 2 model. Given the latest comment (https://openreview.net/forum?id=Bw82hwg5Q3&noteId=ZmCBVKeGdD), I'm understanding that this approach is severely computationally expensive if done for single CoT ($20k$ vs $k$) and moderately expensive for SC ($160k$ vs $40k$). Given this significant limitation, I agree with Reviewer WznY that the results in Table1 are bit misleading as it does not paint the complete picture. You should modify the table (and potentially main claims) to reflect how the method compares in terms of accuracy with a comparable compute budget across both methods. Without this, the gains are not correctly attributed. Having said that, I think this is not a major limitation of the method. Your approach has a larger impact on performance with increasing computation cost, something that SC cannot potentially match, even if we allow it to generate more chains. But this needs to be depicted+discussed more clearly in the paper, which is currently lacking. Until this is addressed appropriately, I'm reducing my scores.