GRACE : Discriminator-Guided Chain-of-Thought Reasoning (2023)

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.

## introduction multi-step reasoning spans a set of tasks where a question is answered via a sequence of reasoning steps until a final answer is reached @xcite . while pretrained language models (lms) have shown impressive performance on a variety of qa tasks, they still struggle with problems that require complex multi-step reasoning @xcite @xcite . one reason is that i have 10 liters of orange drink that are two-thirds water and i wish to add it to 15 liters of pineapple drink that is three-fifths water. as i pour it, i spill one liter of the orange drink. how much water is in the remaining 24 liters? ## experimental setup tasks. we evaluate our approach on four math and two symbolic reasoning tasks. for math reasoning, we use gsm8k @xcite , a common benchmark for complex multi-step reasoning. mathqa-gain, a subset of mathqa @xcite and includes math word problems about gain/loss. each problem is accompanied by a step-by-step python program. svamp @xcite and multiarith @xcite consist of elementary-level math word problems. for mathqa-gain, svamp, and multiarith, we use the train-test splits included in the lila benchmark @xcite . as for symbolic reasoning tasks, we experiment with coin flip (cf; @xcite and tracking shuffled objects (tso) from big-bench hard @xcite and we use the splits by @xcite . svamp, multiarith, cf, and tso do not include reference step-by-step solutions (only the final answer is included for each question) we follow recent work on chain-of-thought distillation @xcite @xcite and prompt gpt-3.5-turbo to generate a step-by-step solution for each question. details on this process and dataset statistics are in appendix e.1. ## results and discussion evaluation of final answer accuracy. we compare the accuracy of final answers reached by different methods. we first discuss the results over math reasoning in we observe that the verifier approach performs poorly on all tasks except for mathqa-gain. this is likely because the verifier training examples include solutions with the correct final answer but invalid reasoning steps. as a result, the trained verified cannot identify correct from incorrect reasoning. to test this hypothesis, we ran an experiment with gsm8k where we only included the gold trajectories as positive examples and indeed found improvement in the verifier's performance, albeit still below sc and grace. moving to symbolic reasoning (shown in ultimately, our results show that grace can boost both flan-t5 and llama's final answer accuracy on different math and symbolic reasoning tasks. interestingly and in the case of llama models, we achieve such improvements (i) without any training of the lm and (ii) with a discriminator that has 20x and 38x fewer parameters than the backvone lm for llama 7b and llama 13b , respectively. this points to a promising direction of our approach in steering the generations of large lms via significantly smaller and more efficient discriminators. ## analysis sample efficiency. a primary motivation for grace is to achieve more step-level control over solution decoding than solution-level aggregation as done by vanilla sc. 6 therefore, we expect grace to require fewer samples than vanilla sc to reach the same accuracy. to see if this is true, we compare grace w/ sc to the vanilla sc with different numbers of samples. figure 4 (top) plots the number of samples against final answer accuracy on four tasks with flan-t5 large . we observe that grace is more sample-efficient and yields better accuracy with the same or fewer samples than vanilla sc. step score. we study the effect of the discriminator score coefficient β in equation ( 6 ) when computing the score of a candidate step on the reasoning performance. figure 4 (bottom) shows final answer accuracy as we vary β from 0.0 to 1.0. the plot shows the accuracy improving as β is increased beyond 0, emphasizing the benefit brought by integrating d(q, r, s) into the step score. interestingly, when increasing β beyond a certain point, the performance drops again, indicating that we should not completely omit p lm (s|q, r), which represents the lm's learned reasoning abilities. discriminator training loss acc. binary cross-entropy 16.8 pairwise ranking @xcite 37.6 max-margin 38.2 alignment. to verify whether our alignment algorithm brings any benefit to the discriminator training, we compare it to a simpler version where steps in the sampled solutions are aligned with the corresponding steps in the reference solutions. the naive approach only aligns samples with the same number of steps as the reference solution, since there is no clear way to align samples of different lengths. figure 6 in appendix f shows the accuracy on gsm8k and svamp when training the discriminator using both alignments. our alignment approach outperforms naive alignment by 2.2% and 5.9% points on gsm8k and svamp, respectively. these results highlight the advantages of our proposed alignment method in yielding a better discriminator training. discriminator loss function. we compare the max-margin objective in equation ( 5 ) to two different discriminator training objectives. the first is a binary cross-entropy objective, where the model is trained to predict 'correct' or 'incorrect' after each step, similar to @xcite . the probability of correctness is used as the discriminator score in equation ( 6 ). the second is the pairwise ranking loss used to train the reward model for instructgpt @xcite cross-task performance. our approach relies on reference solutions, which may not always be available for all tasks. therefore, it is valuable to investigate how grace performs when the discriminator is applied to a task different from the one it was originally trained on. in figure 5 , we present the results for svamp and multiarith when the discriminator's training task is varied. in this context, grace demonstrates a small relative performance drop, showing an 8% decrease for @xmath0, while still outperforming greedy decoding and lm-only scoring. however, a more substantial drop of 26.6% is observed in the case of @xmath1. this decrease can be attributed to two key factors. first, svamp has a smaller set of training questions (432) in comparison to gsm8k (6.4k), and second, svamp questions require simagent to learn the task with fewer samples. pler reasoning compared to gsm8k. discriminator size. lastly, we study how the size of the discriminator model impacts the final answer accuracy. more details are in appendix f. ## related work discriminator-guided controlled generation. previous work in controlled generation has employed discriminators during decoding to guide generation towards specific attributes, such as sentiment, topic, or lexical constraints @xcite @xcite @xcite . these discriminators can either update the hidden states of the language model in real-time @xcite or adjust token probabilities @xcite @xcite . our research takes inspiration from these practices but extends them to multi-step reasoning in two key aspects: control granularity and discriminator training. we direct the decoding of multi-step solutions at the level of reasoning steps to promote their correctness, instead of individual tokens as correctness is not meaningfully defined at the token level. as for discriminator training, it is clear that learning a reasoning correctness discriminator is more challenging than a topic or sentiment discriminator as the former requires checking for logical, mathematical, or factual errors in a given reasoning step. to tackle this, we introduce a novel 3-step process for training discriminators without step-level annotations. multi-step reasoning. two main types of approaches have been explored to improve multi-step reasoning: inference-time methods, which do not require additional language model (lm) training, and training-based methods, which require either labeled samples or rewards. popular inference-time techniques include model prompting such as chainof-thought @xcite and its variants @xcite . while these input-based techniques operate at the lm input side, other methods target the output side. for instance, self-consistency @xcite employs majority voting on multiple sampled solutions to determine the final answer. an alternative output-based method involves training a verifier model to rank sampled solutions according to correctness @xcite . however, verifiers and vanilla self-consistency exhibit no control over solution sampling. we also show in this paper (see section 4) that verifiers trained on samples from smaller lms perform very poorly. training-based methods, on the other hand, focus on crafting learning objectives to teach the lm to reason correctly. for instance, @xcite trained a reward model to assess the correctness of the entire reasoning chain, which is then used as a reward model. @xcite proposed training lms on sampled partially correct solutions to enhance mathematical reasoning. more relevant to our work, @xcite introduced a step-aware verifier to score sampled solutions but their technique only applies to fully sampled solutions, unlike our approach which actively guides the decoding process. @xcite used a stepwise verifier to guide the search process for proof generation and relied on heuristics to generate negative examples, unlike grace, which samples incorrect solutions from the model. ## conclusion language models can easily assign a high probability to incorrect solutions. existing methods like self-consistency and verifiers that rely on sampling from the lm distribution do not effectively address this issue. this work proposes a guided decoding method that trains a step-level discriminator model that is used to steer the solution decoding process toward correct steps. we demonstrate the utility of our approach on six reasoning benchmarks, where it strongly boosts the correctness of the generated solutions.