  In the context of multi-step reasoning, e.g., with chain-of-thought, language
models (LMs) can easily assign a high likelihood to incorrect steps. As a
result, decoding strategies that optimize for solution likelihood often yield
incorrect solutions. To address this issue, we propose Guiding chain-of-thought
ReAsoning with a CorrectnEss Discriminator (GRACE), a stepwise decoding
approach that steers the decoding process towards producing correct reasoning
steps. GRACE employs a discriminator trained with a contrastive loss over
correct and incorrect steps, which is used during decoding to score next-step
candidates based on their correctness. Importantly, GRACE only requires
sampling from the LM, without the need for LM training or fine-tuning. Using
models from FLAN-T5 and LLaMA families, we evaluate GRACE over four math and
two symbolic reasoning tasks, where it exhibits substantial performance gains
compared to greedy decoding, verifiers, and self-consistency in most settings.
When further combined with self-consistency, GRACE outperforms all the
baselines by sizeable margins. Human and LLM evaluations over GSM8K show that
GRACE not only improves the final answer accuracy but also the correctness of
the intermediate reasoning. Our implementation can be accessed at
\url{https://github.com/mukhal/grace}.
