GRACE: Discriminator-Guided Chain-of-Thought Reasoning

1 Introduction

• The next-word prediction objective does not explicitly promote correct step-by-step reasoning, and language models can assign high probability to invalid sequences.A few-shot prompted LLaMA13B example ranks incorrect next steps above the correct one.Source: §1 · p. 1, Figure 1 · p. 1
• Self-consistency and verifier methods sample complete solutions, can select highly likely incorrect ones, and provide no control during decoding.Chain-of-thought prompting can leave the likelihood mismatch unresolved: the correct next step may receive much lower probability than incorrect candidates.Source: §1 · pp. 1–2
• GRACE uses a step-level correctness discriminator to steer decoding toward correct steps, giving finer-grained control than vanilla self-consistency and verifier methods.It requires sampling from the language model, not language-model training or fine-tuning.Source: §1 · p. 2
• GRACE trains its discriminator from correct solutions without step-level human annotations, using failed solutions, alignment to references, and a max-margin learning objective.The process samples solutions with incorrect final answers, aligns them with reference solutions to identify incorrect steps, then trains the discriminator to score correct steps higher.Source: §1 · p. 2, Figure 2 · p. 2
• 7.4% accuracy points on GSM8K with FLAN-T5-Large and 5.4% with LLaMA7B: GRACE outperforms greedy decoding and improves over greedy, self-consistency, and verifiers across six benchmarks.Combining GRACE with self-consistency outperforms vanilla self-consistency by 10.2% points on GSM8K and 15.7% on MultiArith.Source: §1 · p. 2
• Human evaluation on GSM8K reduces solution error from 9.0% with greedy decoding to 5.0%, a 44% reduction.Human and LLM evaluations also find improved reasoning-chain correctness.Source: §1 · p. 3

2.1 Formalization

• GRACE samples next steps that have high LM likelihood and are judged correct relative to the question and existing prefix.Source: §2.1 · p. 3

2.2 Discriminator Learning

• The discriminator is trained contrastively to distinguish correct from incorrect steps using examples built from sampled solutions and reference alignments.Source: §2.2 · pp. 3–4
• Incorrect training solutions are sampled with top-k decoding and retained when their final answer is wrong, ensuring at least one incorrect step.Source: §2.2 · p. 3
• Needleman-Wunsch alignment uses cosine distances between ROSCOE step embeddings to accommodate missing or extra steps; comparable math steps are checked by intermediate variables.Source: §2.2 · p. 4, Figure 3 · p. 4

2.3 Guided Stepwise Decoding

• At each step, guided decoding samples a pool of next-step candidates with nucleus sampling and scores them using the discriminator-guided scoring rule.The hyperparameter β controls the discriminator score coefficient.Source: §2.3 · pp. 4–5

• Math evaluation uses GSM8K (Cobbe et al., 2021), MathQA-Gain from MathQA (Amini et al., 2019), SVAMP (Patel et al., 2021), and MultiArith (Roy and Roth, 2015).Source: §3 · p. 5
• Symbolic evaluation uses Coin Flip (Wei et al., 2021; Kojima et al., 2022) and Tracking Shuffled Objects from Big-Bench Hard (Srivastava et al., 2022).Because SVAMP, MultiArith, Coin Flip, and Tracking Shuffled Objects lack reference reasoning steps, GPT-3.5-turbo generates step-by-step solutions for them.Source: §3 · p. 5
• Baselines include greedy decoding, beam search, self-consistency, a solution verifier, and LM-only step scoring.Self-consistency and verifiers are also evaluated on complete solutions generated with GRACE.Source: §3 · p. 5
• Experiments use fine-tuned FLAN-T5Large and few-shot LLaMA 7B and 13B; discriminator training uses roughly 100K incorrect solutions per task.Source: §3 · p. 5

4 Results and Discussion

• GRACE improves final answer accuracy over greedy decoding by 7.4 points on GSM8K and 11.7 on SVAMP; GRACE with SC beats vanilla SC by 10.2 points on GSM8K and 15.7 on MultiArith.Table 1 covers four math reasoning tasks and reports GRACE with SC outperforming the baselines on all tasks.Source: §4 · pp. 5–6, Table 1 · p. 6
• The verifier performs poorly on all tasks except MathQA-Gain; using only gold trajectories as positive GSM8K examples improves it, but it remains below SC and GRACE.The authors attribute the poor performance to verifier training examples that can have correct final answers but invalid reasoning steps.Source: §4 · p. 6
• On TSO, GRACE with SC beats SC by 2.6% for T5Large and 4.6% for LLaMA13B; on Coin Flip, it improves LLaMA13B accuracy by 12.8%.FLAN-T5Large Coin Flip results are omitted because that model already achieves near-perfect accuracy.Source: §4 · p. 6, Table 2 · p. 6

Evaluation of intermediate step correctness.

• GRACE with SC achieves better dev accuracy than vanilla SC with the same or fewer samples; increasing β helps up to a point, after which accuracy drops.The latter pattern indicates that the LM score should not be omitted from the step score.Source: Figure 4 · p. 7
• On GSM8K, GRACE scores 7.0 and 3.8 points higher than greedy decoding and self-consistency, respectively, and reduces human trace error from 9.0% to 5.0%.The human trace-error reduction is 44%; LLM-based trace error shows a similar improvement.Source: Evaluation of intermediate step… · p. 7, Table 3 · p. 7

5 Analysis

• GRACE with self-consistency is more sample-efficient and achieves better accuracy with the same or fewer samples than vanilla self-consistency.This comparison covers four tasks with FLAN-T5Large.Source: §5 · p. 8
• Accuracy improves as β rises above 0, then drops beyond a point, indicating that the LM score pLM(s|q, r) should not be omitted.The score combines the discriminator term D(q, r, s) with the LM’s learned reasoning abilities.Source: §5 · p. 8
• The proposed alignment outperforms naive alignment by 2.2% points on GSM8K and 5.9% points on SVAMP.Naive alignment only pairs sampled solutions with the same number of steps as the reference.Source: §5 · p. 8
• Cross-task transfer yields relative performance drops of 8% for GSM8K→SVAMP and 7% for GSM8K→MultiArith, but 26.6% for SVAMP→MultiArith.GRACE still outperforms greedy decoding and LM-only scoring in these settings; the authors cite training-set size and task-reasoning differences as factors in the larger drop.Source: Figure 5 · p. 8, §5 · p. 8
• On GSM8K, binary cross-entropy yields the lowest accuracy, while max-margin is comparable to pairwise ranking loss.The comparison uses FLAN-T5Large; the table reports dev-set accuracy averaged over three runs.Source: §5 · p. 8, Table 4 · p. 8

Discriminator-Guided Controlled Generation

• Prior controlled-generation discriminators guide attributes such as sentiment or topic, while GRACE guides reasoning at the step level and trains its discriminator without step-level annotations.Earlier approaches may modify hidden states or adjust token probabilities; GRACE targets correctness at the reasoning-step rather than token level.Source: Discriminator-Guided Controlled… · p. 9
• Prompting, self-consistency, and verifiers are inference-time methods, but self-consistency and verifiers do not control solution sampling; training-based approaches instead teach reasoning through labeled samples or rewards.The cited examples include majority voting over sampled solutions and verifier ranking of sampled solutions (Wang et al., 2022; Cobbe et al., 2021).Source: Discriminator-Guided Controlled… · p. 9
• Li et al. (2022) score fully sampled solutions with a step-aware verifier, whereas Yang et al. (2022) guide proof search using heuristic negatives, unlike GRACE’s decoding guidance and model-sampled incorrect examples.Source: Discriminator-Guided Controlled… · p. 9

7 Conclusion

• Language models can assign high probability to incorrect solutions, and sampling-based self-consistency and verifiers do not effectively address this issue.Source: §7 · p. 9
• GRACE steers solution decoding toward correct steps using a trained step-level discriminator.Source: §7 · p. 9
• Across six reasoning benchmarks, GRACE strongly boosts the correctness of generated solutions.Source: §7 · p. 9

Limitations and Future Work

• Decoding incurs overhead from sampling candidates and computing discriminator step scores.Source: Limitations and Future Work · p. 9
• GRACE’s performance is upper-bounded by the quality of the sampled candidate steps.Source: Limitations and Future Work · p. 9
• The alignment process requires access to reference step-by-step solutions; future directions include using alignment to curate a reward signal and extending GRACE to commercial APIs without logits access.Source: Limitations and Future Work · p. 9

A Implementation Details

• Discriminator training uses roughly 80K incorrect solutions per task, a FLAN-T5Large encoder, and 10 epochs; held-out development loss selects the checkpoint.The step score uses max-pooled hidden states and a two-layer MLP, with tanh constraining scores to [−1, 1].Source: A Implementation Details · p. 12
• Early stopping based on loss better indicates discriminator performance than pairwise accuracy for ranking correct steps above incorrect ones.Source: A Implementation Details · p. 12
• Stepwise decoding samples candidate reasoning steps with nucleus sampling, continues until an answer or step limit, and uses a calculator for math operations.The task-specific decoding hyperparameters were selected by development-set grid search; β controls discriminator contribution, J the candidate-pool size, and T the sampling temperature.Source: A Implementation Details · p. 12, Table 5 · p. 12

B Solution Alignment

• The Needleman–Wunsch alignment uses pairwise solution similarity and gap costs to produce step alignments, discarding samples above task-specific alignment-cost thresholds.The threshold is >2.0 for all tasks except TSO, where it is >6.0.Source: B Solution Alignment · p. 12
• Solution alignment uses ROSCOE embeddings for every task except Coin Flip, which uses vanilla SimCSE embeddings.Source: B Solution Alignment · p. 12

• GPT-3.5-turbo predicted prefix correctness with 88.94% macro F1 on 280 prefixes from 100 model-generated GSM8K solutions.The prompt used 10 demonstrations, with 10 different demonstrations randomly sampled for each of three evaluation runs.Source: C LLM Evaluation Details · p. 13, Table 6 · p. 14

D Human Evaluation Details

• After two annotators reached Cohen-Kappa agreement of 0.93 on 100 solutions, one annotator labeled 400 solutions: 200 from GRACE and 200 from greedy decoding.Annotators identified the first step with incorrect information or one that made reaching the correct solution impossible without undoing it.Source: D Human Evaluation Details · p. 15

E.1 Step-by-step Reference Generation

• For SVAMP and MultiArith, GPT-3.5-turbo generated 20 candidate references per question; a randomly selected correct solution became the reference.Questions without a correct answer after five tries were discarded; dataset split counts are listed in Table 7.Source: §E.1 · p. 15, Table 7 · p. 15

F Further Analysis

• The Needleman–Wunsch alignment outperforms naive alignment by 1.9% on GSM8K and 5.9% on SVAMP.Results use FLAN-T5Large and are averaged over three runs.Source: Figure 6 · p. 15
• On MultiArith, a T5-base discriminator surpasses self-consistency by 0.7 points, but smaller discriminators do not perform well on the more difficult GSM8K task.The paper reports that the T5-base discriminator is 63X smaller than LLaMA7B; larger discriminators improve MultiArith performance.Source: F Further Analysis · p. 15, Figure 7 · p. 15

G Few-shot prompts

• The appendix provides six-shot prompts for LLaMA7B on GSM8K, SVAMP, and MultiArith, and for LLaMA13B on Coin Flip and Tracking Shuffled Objects.Source: Table 8 · p. 17, Table 9 · p. 18, Table 10 · p. 19

H Sample Outputs

• Sample outputs show cases where GRACE reaches the correct answer unlike self-consistency, including examples from math and symbolic reasoning tasks.The examples cover GSM8K, SVAMP, MultiArith, Coin Flip, and Tracking Shuffled Objects; the solution sentences represent reasoning steps.Source: Table 13 · p. 22, Table 16 · p. 25, Table 18 · p. 27