PaperlayerView exact revision on arXiv

Source-linked AI summary

Self-Evaluation Guided Beam Search for Reasoning

Yuxi Xie, Kenji Kawaguchi, Yiran Zhao, Xu Zhao, Min-Yen Kan, Junxian He, Qizhe Xie

arXiv:2305.00633v3cs.CLcs.AIcs.LG

TL;DR

Longer reasoning chains create uncertainty, accumulated errors, and an exponentially large sampling space for LLMs. The paper uses stepwise self-evaluation with stochastic beam search to calibrate multi-step decoding, reporting gains across arithmetic, symbolic, and commonsense reasoning tasks.

  • Problem

    Longer reasoning chains make individual-step errors accumulate while autoregressive generation must sample from an exponentially large search space.

  • Method

    The method treats sequences of reasoning tokens as decoding steps, combines language-model probability with correctness confidence, and searches with stochastic beam search.

  • Results

    The approach produces consistent gains across arithmetic, symbolic, and commonsense reasoning, including 5.3%, 8.3%, and 0.7% absolute accuracy increases on GSM8K, AQuA, and SVAMP, respectively, and 77.2% versus 73.2% on StrategyQA.

  • Takeaways & Limitations

    Self-evaluation guidance can identify low-confidence reasoning failures and support more consistent and robust multi-step reasoning.

  • Takeaways & Limitations

    The approach requires access to LLM logits and adds candidate-sampling and self-evaluation costs, making it better suited to longer reasoning chains.

Abstract

from arXiv · show

Breaking down a problem into intermediate steps has demonstrated impressive performance in Large Language Model (LLM) reasoning. However, the growth of the reasoning chain introduces uncertainty and error accumulation, making it challenging to elicit accurate final results. To tackle this challenge of uncertainty in multi-step reasoning, we introduce a stepwise self-evaluation mechanism to guide and calibrate the reasoning process of LLMs. We propose a decoding algorithm integrating the self-evaluation guidance via stochastic beam search. The self-evaluation guidance serves as a better-calibrated automatic criterion, facilitating an efficient search in the reasoning space and resulting in superior prediction quality. Stochastic beam search balances exploitation and exploration of the search space with temperature-controlled randomness. Our approach surpasses the corresponding Codex-backboned baselines in few-shot accuracy by $6.34\%$, $9.56\%$, and $5.46\%$ on the GSM8K, AQuA, and StrategyQA benchmarks, respectively. Experiment results with Llama-2 on arithmetic reasoning demonstrate the efficiency of our method in outperforming the baseline methods with comparable computational budgets. Further analysis in multi-step reasoning finds our self-evaluation guidance pinpoints logic failures and leads to higher consistency and robustness. Our code is publicly available at https://guideddecoding.github.io/.

1 Introduction

LLMs benefit from decomposing problems into reasoning chains, but longer chains increase uncertainty, error accumulation, and the difficulty of searching an exponentially large reasoning space. The paper addresses these challenges by using self-evaluation to guide stepwise stochastic beam search.

  • Reasoning chains from scratchpads, chain-of-thought, least-to-most, and PAL prompting can improve performance on reasoning tasks.
  • Longer and more complex reasoning chains make LLMs struggle with uncertainty and accumulated errors.
  • Standard autoregressive reasoning samples within an exponentially large search space.
  • Self-evaluation provides a better-calibrated criterion for automatically guiding the search in reasoning space.
  • The method treats each decoding step as a multi-token reasoning logic and combines stepwise self-evaluation with beam search and temperature-controlled randomness.

2 Self-Evaluation Guided Stochastic Beam Search

The method models reasoning as step-level decoding, scores candidate chains using language-model probability and correctness confidence, and uses stochastic beam search to balance exploration with exploitation. Self-evaluation assesses each generated reasoning step to improve chain consistency and limit accumulated errors.

  • The answer distribution is decomposed into reasoning-chain generation P(R | x) and answer generation P(a | R, x).
  • The answer-generation term distributes probability across predicted answers executed from the reasoning chain, including cases with no valid answer or multiple answers.
  • Multi-step reasoning: Each reasoning step is a semantically integrated sequence of tokens rather than a single token, enabling beam search over reasoning chains.
  • Multi-step Reasoning via Stochastic Beam Search: The decoding objective combines language-model probability with a correctness-confidence constraint for each reasoning step.
  • Multi-step Reasoning via Stochastic Beam Search: Stochastic beam search samples multiple candidates per beam and uses temperature τ, with annealing factor α controlling stepwise randomness.
  • Self-evaluation as correctness control: Self-evaluation uses a prompted evaluation LLM to judge each step's correctness from the preceding reasoning context.

3 Experiments

Experiments evaluate self-evaluation guided beam search across arithmetic, symbolic, and commonsense reasoning, using Codex and Llama-2 backbones. The method generally improves accuracy and cost efficiency, especially for longer reasoning chains, while confidence calibration and computational overhead remain important boundaries.

  • Arithmetic and Symbolic Reasoning: The method improves arithmetic accuracy by 5.3%, 8.3%, and 0.7% on GSM8K, AQuA, and SVAMP, respectively.These are absolute increases over the PAL baseline.
  • Commonsense Reasoning: 77.2% accuracy on StrategyQA compares with 73.2% for the baseline, demonstrating improvement in commonsense reasoning.
  • Computational Cost Overhead: The approach incurs computational overhead, with its single-chain PAL version costing about three times more than self-consistency on GSM8K.The reported overhead is attributed to using 16 rollouts per beam for better performance.
  • Computational Cost Overhead: 46.1% accuracy on GSM8K at 12.6k tokens exceeds self-consistency’s 41.8% at 13.9k tokens under comparable computational budgets.The method also significantly outperforms equal-cost baselines as the computational budget increases.
  • Confidence Analysis: Correctness confidence is more discriminatory than generation confidence and better identifies logical errors by accounting for accumulated mistakes.Score distributions differ substantially for arithmetic reasoning but negligibly for commonsense reasoning.
  • Reasoning Complexity: Performance gains increase with reasoning-chain length on GSM8K and StrategyQA, with StrategyQA’s improvement primarily arising from longer chains.

4 Related Work

Prior work develops reasoning formulations, self-evaluation and decoding strategies to improve LLM reasoning while balancing confidence, diversity, and search quality.

  • Reasoning Formulation: Reasoning research shifted from rationale generation toward decomposing problems into intermediate steps before reaching final answers.
  • LLM Self-Evaluation: LLM calibration studies report that probabilistic predictions can correspond well with actual token frequencies, with larger models improving calibration.
  • Decoding Strategies: Decoding methods trade off diversity and quality: greedy decoding and beam search favor quality, while temperature, top-k, and top-p sampling increase diversity.

5 Discussion

The paper introduces multi-step decoding that combines stepwise self-evaluation guidance with stochastic beam search for LLM reasoning. Results across arithmetic, symbolic, and commonsense tasks support its robustness and generalizability, especially for longer reasoning chains.

  • The method calibrates multi-step reasoning through stepwise self-evaluation guidance integrated with stochastic beam search.
  • Its empirical success spans arithmetic, symbolic, and commonsense reasoning tasks, with longer reasoning chains showing significant performance gains.

Potential Impacts and Limitations

The method requires LLM logits and adds computation through candidate sampling and self-evaluation. Its efficiency–cost trade-off is most favorable for longer reasoning chains, where cumulative calibration can improve performance more substantially.

  • The method requires access to LLM logits, limiting applicability to models such as GPT-4 that do not provide token likelihoods.
  • Multi-step decoding adds computational costs from candidate sampling and self-evaluation.
  • The approach is best suited to longer reasoning chains, where cumulative calibration can improve overall performance more significantly.

A.1 Theoretical Analysis of Eq. 4

The theoretical analysis approximates the target distribution over infinitely many reasoning paths using a finite sample set generated by the language model. The approximation error decreases toward zero as the finite set grows toward the full path space.

  • The analysis approximates sampling from the infinite set of possible completions using a finite set S sampled from language-model generations.
  • The finite candidate set is constructed from the generation model and differs from the target distribution used in the approximation.
  • The bound is formulated using upper and lower bounds on exp(E(s1:t)/τ), with their ratio constrained by r = c̄/c.
  • As M increases toward |S∗|, the approximation difference decreases toward zero.

A.2 Extended Experiments

Extended experiments examine score calibration, sampling diversity, LLM backbones, and GPT-4’s reasoning-chain evaluations. Results indicate that faithfulness improves confidence-based guidance, while score reliability and evaluation quality vary by task and model.

  • Sampling Diversity: Moderate temperature decay generally improves single-chain performance, whereas excessive sampling randomness hurts accuracy.The experiments vary sampling temperature τ and decay ratio α; α = 0.5 is used throughout for simplicity.
  • Self-Evaluation: The AUC of Eλ remains relatively stable across λ values on GSM8K and StrategyQA, although task-specific tuning may yield further gains.Eλ combines generation confidence and faithfulness, with λ = 0.5 used in the main experiments.
  • Self-Evaluation: Faithfulness primarily increases evaluation confidence C while leaving generation confidence P similar to baseline methods, helping correct predictions.The authors identify evaluation confidence as important for selecting better reasoning choices in decomposed reasoning.
  • Self-Evaluation: Score magnitude separates correct from incorrect predictions more clearly on GSM8K than StrategyQA, where many low-scored predictions remain correct.Thus, self-evaluation scores align less well with correctness on StrategyQA.
  • LLM Backbone Study: Codex-based results are competitive with or better than ChatGPT across the reported arithmetic and commonsense datasets, but stronger backbones lack token logits required by the method.For example, Codex-based PAL obtains 80.2% versus ChatGPT’s 78.7% on GSM8K and 77.2% versus 65.9% on StrategyQA.
  • GPT-4 Experiments: GPT-4 more effectively identifies central logical errors and supplies detailed explanations, yet its scores can vary substantially and may miss small consequential errors.The reported arithmetic examples contrast GPT-4 and Codex judgments on incorrect and correct reasoning steps.

A.3 Implementation Details

The implementation uses stochastic beam search with multiple sampled completions per beam candidate, task-dependent temperatures, and few-shot generation and evaluation prompts. Majority voting is performed over final beam candidates to limit additional search cost.

  • Beam Search: Each reasoning step maintains k beam candidates, samples n completions per candidate, and retains k candidates from the resulting k · n samples.The Codex configuration uses k = 5 and n = 16, with decoding capped at 16 steps.
  • Generation Settings: Generation temperatures are tuned by task and prompting method, with arithmetic PAL favoring γ ∈[0.4, 0.8] and commonsense CoT favoring γ ∈[0.1, 0.5].The reported ranges reflect different randomness levels across arithmetic, symbolic, and commonsense reasoning settings.
  • Generation Settings: For majority voting, stochastic beam search uses α = 0.5 and task-specific τ values, including τ = 0.5 for PAL and τ = 0.2 for CoT.PAL typically decomposes problems into more steps than CoT, motivating different τ choices.
  • Majority Voting: The method votes among final-step beam candidates after only a few searches, avoiding additional time complexity relative to conventional majority voting at the cost of some diversity.Prior approaches usually sample N ≥20 reasoning chains, whereas this method searches at most 10 times.
  • Prompts: The implementation includes task-specific few-shot generation and evaluation prompts, with GSM8K examples using 8-shot CoT and 9-shot PAL generation.The cited prompt tables provide corresponding evaluation exemplars as well.

EVALUATION

The evaluation materials provide few-shot exemplars for arithmetic, symbolic, and commonsense reasoning tasks, including code-based PAL and free-text CoT reasoning. Examples show evaluators judging individual reasoning steps for correctness and identifying errors in intermediate computations or assumptions.

  • Arithmetic Reasoning: PAL exemplars evaluate whether successive Python-like statements correctly represent arithmetic operations and produce the requested answer.The square-paper and train-crossing examples include unit conversion, distance, area, and final-result checks.
  • Task Coverage: Few-shot PAL prompts are supplied for AQuA, SVAMP, ASDiv, and TabMWP, while symbolic examples cover Date Understanding and Object Counting.The tables document the corresponding generation and evaluation exemplars for these tasks.
  • Arithmetic Reasoning: The arithmetic examples mark intermediate lines incorrect when they omit required quantities, use an incorrect value, or return the wrong result.For the train problem, the total crossing distance must include both train lengths and the final time must be in seconds.
  • Symbolic Reasoning: Object-counting exemplars distinguish correct initialization and conditional logic from incorrect values and incomplete counting procedures.The roller-coaster example evaluates counting parks below a threshold through stepwise code judgments.
  • Commonsense Reasoning: Commonsense CoT exemplars evaluate whether each reasoning step is justified, including whether alternatives remain plausible before selecting an answer.The appointment-book example rejects unsupported claims that a wallet is the only plausible location.
Loading 2305.00633v3…