  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/.
