Learning & Reasoning / EMNLP 2023 Findings

Check a Reasoning Step Before the Model Builds on It

GRACE trains a discriminator to guide a language model during decoding, when a promising next step can still change the answer.

GRACE: Discriminator-Guided Chain-of-Thought Reasoning

Muhammad Khalifa, Lajanugen Logeswaran, Moontae Lee, Honglak Lee, Lu Wang

Overview

A wrong line of arithmetic can make the rest of a solution look coherent while carrying the error forward. GRACE adds a learned score when the language model chooses its next step. The model proposes continuations, and a discriminator helps select which continuation to pursue.

Key Findings

Catch the wrong denominator before it travels

In the paper’s sugar-packet example, a sampled solution correctly arrives at 2,000 grams and then divides by 100 to convert to kilograms. The reference solution divides by 1,000. A verifier that reads only the final answer can spot the failure after the fact. GRACE is designed to intervene when that conversion is still one of several possible next steps. Figure 3

Figure 1. GRACE compares possible next reasoning steps before adding one to the solution.
Figure 1. GRACE compares possible next reasoning steps before adding one to the solution.

Let the model supply realistic mistakes

The authors sample solutions with wrong final answers and align their steps with the reference using the Needleman–Wunsch algorithm, a method for matching sequences with insertions and omissions. An aligned step can be missing, extra or comparable. For a comparable arithmetic step, the pipeline checks its intermediate value against the reference. It uses these aligned examples to train a discriminator to give a correct continuation a higher score than a nearby error. The model’s own mistakes matter. The authors found that manually perturbed references could produce artificially easy negatives. Figure 2 and Section 2.2

Weigh fluency against the chance of a sound step

At each turn, the language model proposes several next steps. The discriminator reads the question qq, the prefix rr, and each candidate ss. The policy scores the candidate using Equation 6:

(1−β)log⁡pLM(s∣q,r)+βD(q,r,s).(1-\beta)\log p_{\mathrm{LM}}(s\mid q,r)+\beta D(q,r,s).

The parameter β\beta controls how strongly the discriminator can steer generation. One configuration runs this process several times and chooses the final answer by agreement. Step-level guidance and answer-level agreement act at different points, which lets the study compare their effects separately.

Read the solution as well as the answer

Fine-tuned FLAN-T5 Large decodingGSM8KSVAMPMathQA-Gain
Greedy26.954.576.5
Self-consistency33.361.878.9
GRACE34.366.284.1
GRACE with self-consistency36.368.684.4

These are selected final-answer accuracies averaged over five runs. The symbolic experiments also show LLaMA 13B rising from 65.5 to 78.3 on Coin Flip when GRACE is added to self-consistency. On Tracking Shuffled Objects it rises from 29.8 to 34.4, close to the 33.3 chance baseline. Tables 1–2

An answer can land correctly despite a serious mistake along the way. On the GSM8K cases used for human trace evaluation, major errors in correct answers drop from 9.0% with greedy decoding to 5.0% with GRACE. The authors also report sample-efficiency gains. The cross-task study qualifies that picture: a discriminator trained on one math dataset can lose substantial accuracy on another. A small model can guide a larger one, but it needs practice recognizing the kinds of reasoning errors that occur in the new task. Table 3 and Figure 4 · Figure 5

Questions & Answers

Q: Does the discriminator write the solution?

A: The language model proposes the steps. The discriminator scores candidates in context and influences the selection. Its role is to steer the generation process.

Q: What happens if all candidates are wrong?

A: The discriminator can favor one of the proposals, but it cannot select a good step that was never sampled. Candidate diversity and the model’s initial ability matter.

Q: Why combine step guidance with self-consistency?

A: They act at different times. Guidance influences each chain while it is being written. Self-consistency compares final answers across completed chains. Table 1 reports the two together and separately.

Q: Will a step scorer trained on one math dataset recognize mistakes in another?

A: The paper reports a sizable accuracy drop when the discriminator is trained on SVAMP and used on MultiArith instead of being trained on MultiArith itself. Its labels come from aligning sampled failed solutions with reference steps, so the source task and generator affect which mistakes it sees. Transfer should be checked on held-out tasks, with first-error localization measured alongside final-answer accuracy.

Future Ideas

Review the first uncertain step in a spreadsheet explanation

For spreadsheet training exercises, generate a sequence of formula edits and use a learned step scorer to flag a questionable transformation before the sequence continues. Check candidate formulas in a sandboxed workbook and keep visible cell references for the learner. Build training pairs from failed model-generated edit sequences and align them with reference sequences. Check whether this produces better training examples than hand-perturbing correct formulas.

Compare step guidance, a final-answer verifier, and a deterministic formula check using the same number of generated candidates and a fixed latency budget. Measure final correctness, first-error localization, and incorrect objections to valid alternate formulas.

Sources

Original abstract

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.