LLM Reasoners: New Evaluation, Library, and Analysis of Step-by-Step Reasoning with Large Language Models
Authors: Shibo Hao
Yi Gu
Haotian Luo
Tianyang Liu
Xiyan Shao
Xinyuan Wang
Shuhua Xie
Haodi Ma
Adithya Samavedhi
Qiyue Gao
Zhen Wang
Zhiting Hu
Venue: COLM (2024)
Keywords: Reasoning
TL;DR: We propose a new evaluation, library, and analysis of step-by-step reasoning with large language models

Abstract: Reasoning is a pivotal skill in the evolution of Large Language Models (LLMs), and constructing step-by-step reasoning chains is essential for enhancing their reasoning abilities. Despite a rich array of recent research aimed at deriving improved reasoning chains from LLMs, two major challenges hinder the progress in this field: the lack of effective methods to evaluate reasoning chains, and the absence of systematic analysis of reasoning algorithms. In this work, we introduce RICE, a novel LLM-based approach for automated evaluation of reasoning chains, which autonomously constructs a detailed evaluation criteria list to help itself recognize intermediate reason-
ing mistakes. This fully automatic method proves to be more precise than existing metrics and offers a complementary angle to conventional answer-based evaluations. For the second challenge, we present a formulation that connects extensive existing reasoning algorithms. LLM Reasoners, a modular library for step-by-step reasoning algorithms, is developed based on the formulation. It enables users to specify problem domains and reasoning strategies with minimal effort. With the help of the new metric and library, we make a comprehensive study of the factors contributing to a reasoning algorithm, including the reward, the exploration strategy, the world model, and the prompt format, with interesting findings unveiled through RICE.

Published as a conference paper at COLM 2024
LLM Reasoners
New Evaluation, Library, and Analysis of Step-by-Step Reasoning with Large Language Models
Shibo Hao Yi Gu Haotian Luo't Tianyang Liu', Xiyan Shao Xinyuan Wang', Shuhua Xie Haodi Ma?, Adithya Samavedhi', Qiyue Gao", Zhen Wang Zhiting Hu² UC San Diego, University of Florida, MMZZUAI (s5hao, yig025, zhh019 (ehhe1.)@ucd...mm edu https://www. 11m- rewsoners. net/
Abstract
Generating accurate step-by-step reasoning essential for Large Language Models (LLMs) to address complex problems and enhance robustness and interpretability. Despite the flux of research on developing advanced reason- ing approaches, systematically analyzing the diverse LLMss and reasoning strategies in generating reasoning chains remains a significant challenge. The difficulties stem from the lack of two key elements: (1) automatic
method for evaluating the generated reasoning chains on different tasks, and (2) unified formalism and implementation of the diverse reasoning approaches for systematic comparison. This paper aims to close the gap: (1) We introduce AutoRace for fully automated reasoming chain evaluation. Existing metrics rely on expensive human annotations or pre-defined LLM prompts not adaptable to different tasks. In contrast, AutoRace automat- ically creates detailed evaluation criteria tailored for each task, and uses GPT-4 for accurate evaluation following the criteria. (2) We develop Reasoners, library for standardized modular implementation of exist- ing and new reasoning algorithms, under a unified formulation of the search, reward and world model components. With the new evaluation and library, (3) we conduct extensive study of different reasoning approaches (e-g., CoT, (o, ToT, RAP). The analysis reveals interesting findings about dif- ferent factors contributing to reasoning, including the reward -aard-uuddace,, breadth-vs-depth in search, world model, and prompt formats, etc.
Introduction
central topic in Large Language Model (LLM) research is to enhance their ability of complex reasoning on diverse problems (c.g., logical reasoning, mathematical derivations, and embodied planning). Rich research has been done to generate multi-step reasoning chains with LLMs, such as Chain-of-Thought (Co'T, Wei et al. 2022). Tree-of-Thoughts (ToT, (RAP, et al. 2023a), among others (Zhu et al. Shanahan, 2022). However, despite the burgeoning body of literature, there lacks a systematic analysis and understanding of the diverse approaches, mainly due to two key challenges:
Yao et al. 2023), Reasoning-via-Plamminn
2022 Xie al. 2023 Zhuang et al.) 2023 Khalita Cre3
Creswell
First, automatic evaluation of multi-step reasoning chains is difficult. Previous studies mostly rely on the accuracy of the final answers as a proxy for assessing the reasoning processes. However, as LLMs tend to produce unfaithful outputs or hallucinate, a correct final answer does not necessarily imply a logically sound reasoning chain (Figure 1 a)
(Golovneva et al.) 2022 Prasad et al. 2023 Tyen et al. 2023 Lyu et al.) 2023 Liu et al. 2023)
Indeed, by manually evaluating 100 reasoning chains generated by Llama-2-70B on the
'Equal contribution.

---

Published as a conference paper at COLM 2024
(a) Challenge I: Correct answer * correct reasoning
(b) AutoRace: Automatic Regsoning Chain Evaluation
0: Does Arttaal operate four wheel vehicles?
Automatically constructed criteria list
Accuracy: The arswer muzt correctly address the cuestion and Logic: The answer should be log callyy consetent...
Ammrakk tranizorts
people with trains and buses.
Artbrak aperates trains, which are four wheel vehicles
Correct answer but incorrect reasoning
Relevance: The anower should directly address the question-
veliccee.
bus as four wheel
Thus, Amt operates Tour wheel vehicles
(39% the cases StrategyOOi
Step
Following the criteria, evaluste every step
The andwer is yes.
So the answer
Accuracy: statemen: trains are four-wheel vehides incorrect-
Ground Truth
Llama- POB
Step
summary, the reasoning chain INCORRECT
Cbain od Thouttts
chouttoo (Tho en si. 8008)
detf Room Bearch LRtee et au, (0083)
(Tve al, (0OB8)
[Tlk el B:633
XP8
Biscc Basoch
MIDIS
argmax
Σ mm)
Mss a. a, P(s, (-).a))
4g
9:
L
AL
C-e Search AEAD Algartthm
World Model
Reward
VOULE
Deoading
PLanPoomeery
(c) Challenge Distinct formalisms and implementations
(d) LLM Reasoners: Unified formulation and library
Figure 1: (a) The first challenge for analyzing step-by-step reasoning with LLMs: correct final answer may be derived from incorrect reasoning chains (false-positice chains), making it necessary to evaluate the reasoning chains directly. (b) Our proposed AutoRace for fully automated evaluation. (c) The second challenge stems from the diverse reasoning algorithms with seemingly distinct designs. (d) Our LLM Reasoners provides a unified formulation and standardized implementation.
StrategyQA questions (Geva et al. 2021 we found up to 39% of such false-positive cases that contain reasoning errors despite having correct final answers. Recent efforts have attempted to evaluate the reasoning chains directly, but often require non-trivial human efforts, such as human-writter reasoning chains as references (Celikyilmaz et al. 2020), manually- annotated datasets for training evaluation models (Golovneva et al. |202 Prasad et al. 2023]
Xia et al. 2024). He al. (2023); ; Tyen al. (2023) use GPT-4 to alleviate human cost, but still require demonstration questions and in-depth error analyses by human experts before applying to each new task. In addition, their instructions that prompt GPT-4 for evaluation are not adaptive to different tasks, leading to suboptimal performance (Section 3.2).
Second, the varied reasoning approaches present distinct formalisms and implementa- tions (Figure T] c). The disparity makes it difficult to analyze the nuanced differences of their reasoning chain generation and compare their critical design elements. Therefore, is desirable to have more holistic formulation and unified implementation. This would reveal the underlying connections among different approaches, and facilitate a more systematic comparison when combined with automatic reasoning evaluation discussed above.
To tackle the challenges, this paper proposes an automatic method for reasoning chain evaluation, develops cohesive library for various latest reasoning approaches, and on this basis, performs extensive analysis of LLM step-by-step reasoning. More specifically, we first present AutoRace (Automatic Reasoning Chain Evaluation), a fully automated approach for evaluating reasoning chains that adapts to different tasks without human efforts (Figure [ b). For each reasoning task (e.g., math reasoning), AutoRace autonomously constructs detailed evaluation criteria list by summarizing errors in LLM-generated reasoning chains. The criteria list is then used to instruct GPT-4 to evaluate any given reasoning chains on
the task. Compared to the predefined human-written prompts (Tyen et al. 2023 He et al., 2023), the AutoRace criteria lists are automatically customized for each task with GPT-4 to ensure accurate evaluation. On wide range of tasks, AutoRace shows strong correlation with human evaluation, and manages to detect 70.4% of incorrect reasoning chains that cannot be captured by the conventional final-answer-based evaluation.
We then introduce a unified perspective of reasoning algorithms, formulating them as a search process towards maximizing accumulated rewards (Figure [ d). A wide range of existing reasoning algorithms can be interpreted as specific choices of the components in the unified formulation, including reward function to decide preferences on different reasoning steps, world model T to specify the state transition, and search algorithm (e.g., beam search, Monte-Carke tree search) to explore the expansive reasoning space. Based
2

---

Published as a conference paper at COLM 2024
on the unified perspective, we further develop the LLM Reasoners library that provides standardized implementation of these components with configurable options, plus rich LLM APIs and intuitive visualizations. As result, LLM Reasoners allows us to easily reproduce the existing reasoning algorithms, and also compose new algorithms and apply to new tasks with minimal efforts.
With the new evaluation method and library, we conduct extensive analysis of reasoning chain generation of diverse LLMs and reasoning algorithms. We collect challenging reasoning tasks that cover different reasoning skills (logical deduction, math, and embodied planning). Using a standardized evaluation protocol, we compare various most popular reasoning algorithms (e.g., CoT, ToT, RAP). The results offer a number of new insights into reasoning algorithm design-fo for example: (1) Reasoning as reward- swwrrd-giided search helps not only improve final accuracy, but also effectively alleviate false-positive reasoning chains; (2) For efficient search in the reasoning space, the breadth of search is generally more important than the depth for most tasks; (3) incorporating world model that explicitly infers reasoning state would effectively improve the LLM reasoning ability, particularly for tasks in embodied environments; (4) inappropriate prompt format design might inadvertently lead to false- positive reasoning chains. We also compare across diverse LLMs (GPT-4, Claude-3, Gemini, etc.) on their CoT reasoning chains. We release all code and experiments of AutoRace and LLM Reasoners at https: //www wewsreesseerss....m net/ hoping to spur the progress of research on LLM complex reasoning.
Related Work
Evaluation of Reasoning Chains. Traditionally, to evaluate the reasoning process, generated reasoning chains are compared with human-written explanations, which known as reference-based reasoning evaluation. Conventional natural language generation (NI.)
metrics were applied to calculate the similarity between machine- aachine-generated chains and
human-crafted ones (Celikyilmaz et al., 2020: Clinciu et al. 2021 Welleck et al. 2022).
Towards reference-free reasoning evaluation, Daivi et al. (202T); Saparov & He 2022);
Han et al. (2022) designed structured reasoning tasks so that the reasoning process can be checked by a program automatically. Recently, ROSCOE (Golovneva et al. 2022) and
ReCEval (Prasad et al. 2023) proposed reference- metrics on general domains, measuring similarity, intormativeness and correctness among steps. With the rapid development of
LLM, Tyen et al. (2023) proposed to prompt GPT-4 with few-shot demonstrations, and Liu et (2023) experimented with knowledge-enhancee
prompting by providing LLMs with relevant information. However, the results indicate that it's still challenging for LLMs to evaluate reasoning chains. He et al. (2023) crafted a detailed instruction inspired by the Socratic method, but the method requires GPT-4 to generate a reference chain at first, limiting its performance for challenging reasoning tasks that GPT-4 fails to solve. Besides, the fixed prompt template is not adjustable to different tasks, which also leads to suboptimal evaluation accuracy. In this work, we focus on LLM-based reference freee reasoning chain evaluation. Our method is generally more accurate and robust than existing metrics, while also saving any additional human efforts. Concurrent to our work, Xia et al. (2024) focused on the false postivie problem in mathmatical reasoning with a fine-tuned LLM as the evaluator. |'ul et al. (2024) attempted measure and improve the faithfulness of reasoning with causal inference.
Step-by-step Reasoning with LLMs. A common practice to enhance the reasoning with LLMs is to generate intermediate reasoning steps, employing methods such as chain-of- thought prompting (Wei al. 2022: Kojima et al., 20022 or question decomposition (Zhou et al. 2022 Li et al. (003).. Inspired by the deliberate reasoning of humans, recent research has focused on searching for better reasoning chains guided by reward (Zhu et al., 2022 Xie
et al. 2023 Yao et al. 2023 Zhuang et al. [2023] Khalifa et al. 2023 Creswell & Shanahan, Hao et al. (2023a) proposed to incorporate a world model into reasoning, which
2022).
simulates the state of the world. This enables LLMs to reason in a manner close to humans' conscious planning. Hu & Shu 2023) presented the LAW formulation that connects the concepts of language models, agent models, and world models for more advanced and robust reasoning. Xiang et al. al. (2024) delivered a multi-modal model that takes into natural language instruction and generate video next state, towards the goal of a general world
3

---

Published as a conference paper at COLM 2024
Reference reasoning chains (Training set)
Q Did Aristotle use laptop?
For question the student made mistake
Reference
Aristotle lived from
Student
For question student
arswer The anower is yes
384 322 BCE.
Laptop was invented 1960.
Aristotie is contem- porary ahilosopher
an irrelevant fact that
Laptop in last century.
To summarize,
3. So the answer
good reasoning chain should
3.
So the answer is yes.
The
The arswee no
What mistakes did the student make?
Accuracy: alighs with factual information
Relevance:
Reasoning chains generated student LLM
The student made a factual mistake that Aristatle is contemperary philosopher.
Logic
Collecting wrong reasoning chains
Summarizing the evaluation criteria
II: Detecting the errors
Figure 2: For any reasoning tasks (e.g,, commonsense reasoning), AutoRace automatically constructs an evaluation criteria list to help itself evaluate reasoning chains in this domain.
model for machine reasoning. Another line of works fine-tune the LLM as reasoning policy that maximize or sample proportional to reward (Shao et al. 2024 Yu et al. 2024).. We include more systematic summary of reasoning algorithms in Section Related to the
scope of this paper, recent works (Welleck et al., 2024 Chen et al. 2024 also surveyed and analyzed tree search algorithms for reasoning.
AutoRace: Automatic Reasoning Chain Evaluation
In this section, we present AutoRace that offers more insights into the LLM reasoning process than final answer correctness (Figure[]). Compared previous works (Tyen al., 2023 He eet al.] 2023) that prompt GPT-4 with fixed human-written instructions, AutoRace involves "learning" process, which helps it to adapt to any problem domains. Specifically, for each task, AutoRace automatically collects L.M.-genertted incorrect reasoning chains, and summarizes evaluation criteria from them (Figure2) 2 With the criteria, GPT-4 can pay more attention to common errors for this certain domain, and make more accurate evaluation. Compared to previous works that train an evaluation model (Golovneva et al. 2022 Prasad et al., 2023) by optimization model parameters, AutoRace effectively leverages GPT-4's strong prior knowledge, so that it is able to learn from only incorrect reasoning chains, which can be collected automatically.
3.1 Evaluation Method
To formulate the problem, we consider a reasoning question x, and L.M.-generated reason- ing chains z, and the predicted answer y. Additionally, we have the reference answer yr. accompanied by a reference reasoning chain 2,, which are available in the training set Draiin of most existing reasoning datasets. Our goal is to develop an automatic evaluation metric for the reasoning chain, s(z) E {0, 1}, which is better aligned with human evaluation of the reasoning chains.
As the first step to criteria list construction, one needs to find out what kinds of errors common for a task. Therefore, AutoRace is designed to condense the criteria from real mistakes in -LM-ggerrttted reasoning chains (Figure I). Here, we make use of the fact that reasoning chain reaching wrong answer must include an intermediate mistake. Given sub-sampled training set D = {xx, yr, 2r)} C Dirair, we run Shaii--o--Thuughee with an LLM (referred where z is the reasoning chain generated by the student and y is the predicted answer extracted from z. Then, we can filter out a subset where the generated answers disagree with the reference answers, Derror
reasoning
the student LLM) to expand the dataset to D' = yr, 2,, 2,
yr, E D' yr y).
Having these reasoning chains with errors, the next goal to compile a criteria list. To reduce the difficulty, we divide it into two simple steps: Detection and Summarization. The Detection step identifies the specific errors reasoning chain. GPT-4 is presented with the question, the reference reasoning chain, and the student reasoning chain. It is then instructed to point to the mistake in the student reasoning chain (Figure 2 is that, even if the question might be challenging for GPT-4 to solve on its own, it has good chance understanding the question and identifying the mistakes once it has access to the reference reasoning chain.
II). The underlying rationale
4

---

Published as a conference paper at COLM 2024
Math
Common
Logical
Method
Average
Fully
GSM8k
Arith
Strategy
Cosmos
Logic
Sort
Auto.
Answer-based
0.94
0.94
0.76
0.67
0.87
0.94
0.85
SocREval
0.89
0.85
0.71
0.80
0.89
0.77
0.82
X
Direct (trace)
0,90
0.38
0.80
0.72
0.21
0.36
0.56
X
Direct (step)
0.85
0.43
0.83
0.73
0.75
0.33
0.65
X
CoT (step)
0.78
0.74
0.78
0.72
1.00
0.86
0.81
x
AutoRace (Ours)
0.91
0.85
0.79
0.78
0.97
0.86
0.86
Table 1: Evaluation accuracy of various reasoning chain evaluation metrics. We also list the accuracy of answer-based evaluation as a reference. Note that AutoRace is the only metric that does not take any human inputs specific to reasoning tasks (i.e., fully automated). We highlight the best reasoning chain metrics (dark green) and metrics within 5% of the best performance (light green) for each task. AutoRace achieves the best average accuracy and is robust across datasets.
After collecting the errors in reasoning chains, GPT-4 is prompted to summarize these specific instances into a criteria list (Figure 2 III.. Eventually, GPT-4 is able to evaluate any new reasoning chain given question x, by checking each criteria each reasoning step. The prompt template of each phrase is in Appendix A.7 A.7
3.2 Experiments
To measure the efficacy of reasoning chain evaluation metrics, we use human-annotated binary labels of reasoning chains as the ground truth, and calculate their accuracy.
Datasets. We experiment on datasets covering mathematical, commonsense and logical reasoning. 5 of them are from previous works (Golovneva et al. 2022) Tyen et al. 2023),
originating from GSM8K (Cobbe et al. 2021), Mullistep-Arthmmee
(Srivastava et al. 2023
DROP (Dua et al. 2019), COSMOS-OP QA (Huang et al. 2019), Logical-Deduction (Srivastaval
et al. 2023) and Word-Sorting (Srivastava et at. 2023). We additionally sample and manually
label reasoning chains from StrategyQA (Geva et al. 2021). The detailed statistics of these
datasets can be found in Appendix
Baselines. We compare AutoRace with other LLM-based evaluation metrics for reasoning chains. (a) SocR Eval (He 20233 crafted a detailed instruction prompt for GPT-4 through the Socratic method, which includes asking it to generate a reference reasoning chain before evaluation. This method also requires one-shot demonstration written by humans for each task. Tyen et al. (2023) proposed three methods: (b) Direct (trace) asks GPT-4 to directly evaluate reasoning chain; (c) Direct (step) asks GPT-4 to check the reasoning step by step; (d) CoT (step) asks GPT-4 generate a reasoning process before evaluating each reasoning step. All these methods require 3-shot demonstrations written by humans. We don't experiment with metrics based on fine-tuned small models (Golovneva et al.) 2022 Prasad et al., 2023), existing literature has already indicated substantial performance gap between these methods and LLM-based metrics (He et al.) 2023).
Results. We collect 4 incorrect reasoning chains for each task to create the criterion list. The results are presented in Table We can observe that among all metrics for reasoning chains, AutoRace achieves the best overall performance. It excels in 3 out of 6 tasks and exhibits robustness, maintaining performance levels within 5% of the best results across the board. Note that different from all baseline, which requires human-written demonstrations, AutoRace does not need any human input specific to reasoning tasks. Indicated by the confusion matrix (Figure 3, left), AutoRace good at detecting incorrect reasoning chains, without sacrificing the performance in correct reasoning chains. On the contrary, SocREval mistakenly classifies many correct reasoning chains to be incorrect. Since SocREval asks GPT-4 to generate its own response as the reference, whenever GPT-4 fails to solve the problem itself, it's very likely to evaluate the reasoning chain to be incorrect, misled by the wrong reference. AutoRace enables GPTT- to evaluate reasoning chains on problems that fails to solve itself, as a case study shown in Figure 66 Specifically, in a problem from MultiArith, task for testing multi-digit arithmetic, SocREval fails because GPT-4 generates the reference with the same mistakes as the reasoning chain to be evaluated, but AutoRace identifies the subtle errors with the detailed criteria. We include more detailed results in
5

---

Published as a conference paper at COLM 2024
Answer-based
SocREval
AutoRace
0.5
0.6
Avetage
Human Labels
0.
0.3
0.4
0.03
0.20
0.11
0.12
0.06
0.17
0.2
Predicted Labels
Predicted Label
Predicted Labels
63M Cosimoss
Stratogy
Logic
Sort
Dataset
Figure 3: Analysis on different reasoning chain evaluation methods: (Left) The macro- averaged confusion matrix of these methods. SocREval and AutoRace both good at detecting incorrect reasoning chains, while SocREval mistakenly classifies correct reasoning chains wrong more frequently. (Right) AutoRace can recognize 70.4% of the false positive reasoning chains, showing the promise to be a great complement to answer accuracy.
Appendix A] that indicate AutoRace is robust to the number of incorrect reasoning chains used for construct criteria construction, the required cost for API call is reasonable, and the criteria lists are transferable across tasks to certain extent.
Moreover, when compared with the answer-based metric, AutoRace also outperforms in of 6 tasks and exhibits better overall performance. We additionally calculate the accuracy of AutoRace on reasoning chains with mistakes but reaching correct answer (false positive reasoning chains), and it turns out that AutoRace managed to detect 70.4% of the false positive reasoning chains averaged across different tasks (Figure right). We examine some false positive reasoning chains detected by AutoRace, and find the explanation given by AutoRace is mostly reasonable. The false positive reasoning chains can be classified into 3 types (Table 10). Based these results, we believe AutoRace would be useful metric complementary to answer-based evaluation.
LLM Reasoners: A Unified Formulation and Library
Besides reasoning chain evaluation, another difficulty in the analysis of reasoning algorithms lies their distinct formulations and implementations. To investigate the critical design elements that affect the nuanced performance, aim to deliver more holistic formulation (Section and unified implementation (Section 4.2) in this section.
4.1 Unified Formulation
There has been rich research on constructing reasoning chains to solve problems using LLMs, from the simplest CoT prompting (Wei et al. 2022), tree search algorithms guided by reward function Yao et al. 2022. Xie et al. 2023 Hao et al. 2023a) and world model (Hao et al. 2023a These methods, among many others, can formulated as search
process that maximizes the accumulated reward argmax (Ro....r)) r r(st, with a world
model that predicts state transition s; T(-|s:-1,, A1-1), and a search algorithm to optimize the objective. This section elaborates on these three crucial components and demonstrates how recent reasoning algorithms can be interpreted special cases within this framework, with specific choices of these three components (Table
World model. The world model defines the state transition distribution T(s $1 (1-1). For example, we can formulate the reasoning state of CoT (Wei et al.) 2022) as the list of all previous actions, i.c., S; = (ag, aj,..., 4, 1), and thus the world model represents deterministic transition which always appends an action to the action history. Beyond this trivial definition, recent studies seek a more substantive depiction of the reasoning state, e.g., the description of the physical environment, or the set of known variables, etc. To track the reasoning state, Liu et al. (2022): Guan et al. (0033) augment LLMs with a physical engine or latent variable, and RAP (Hao et al. 2023a) apply the LLM as a general world model for reasoning, When the LLM can interact with the external environment, e.g. calling tools (Zhuang et al..
PDDL domain model.
et (2023) train model to predict the entity states

---

Published as a conference paper at COLM 2024
Method
Reward
World Model
Search Alg.
CoT
PL Ao. ... 1 PCOT)
(Ap, ..y Rt-1)
Gready
ToT
PLLM PLLM("correc" ("correct" aD. ..., At, p
(90, ... At-1)
BFS/DFS
Self-Eval
PLLM PLLM("corredd ("correct 40. St, _
St (4). A1-1)
Beam search
Toolchain*
LST, seffssll-consssttnncy. etc.
8t = Sloul 15
A search
ORM
a,) if (s. T, else
= (a, A-11)
Rand. Shoot.
PRM
fPRM
= (A0, Rt-1)
Rand. Shoot.
SitSup
finectioed (5),
fiintauned (/-1)
Greedy MCTS
RAP
Likelihood, self-eval,,
St ~ PLLM(- (--1,
Table 2: Representative reasoning aaiiingggggoon algorithms, including CoT (Wei et al. 2022), ToT (Yao et al.
2023), Self-Eval (Xie et al. 2023), Toolchain" (Zhuang et al.; 2023), ORM (Cobbe et al. [021],
PRM (Lightman et al. 2023), SitSup (Li et al. 2023), RAP (Hao et al. 2023a), summarized in
terms of the reward function, world model, and search algorithm.
2023), the environment is the world model. For prompt optimization (Wang et al. 2023b or adversarial attack (Guo et al. (024), the target LLM also performs the role of a world model as it provides a feedback to prompt. Recent work started to develop multi-modal
world models at scale, such as GAIA-1 (Hu et al. 2023) for auto-driving, UniSim (Yang et al.
2023) for robotic manipulation, Genie (Bruce et al. 2024 for 2D games, and Pandora (Xiang et al. 2024), towards a general world model that generates next video state given natural language as inputs.
The reward function r(s), az) decides whether a reasoning step is desired. CoT implicitly employs the likelihood predicted by the language models as the reward, as it generates the next reasoning step with high likelihood conditioned on previous steps and a Col' prompt, i.., r(st, a+) PLLM A
Reward function.
Yao et al. (2023); ; Hao et al. (2023a); Xie et al. (203)) Ouyang et al. (2023) propose to use sell-evaluation as the reward, asking the LLM choose the last action is "correct" or "wrong", or output confidence score with self-evaluation prompt, e.g., r(s;, PI...(("ooreedd
St, Palff (elfffeal)) eval). Cobbe et al. Yuan et al. (2024) train outcome-supervised reward models (ORMs) to evaluate a reasoning chain, which predicts the reward for complete reasoning chain. More recent works (Khalifa et al. 2023 Lightman et al. 2023 Sun et al. 2024 Wang et al., 2023a) train step-by-step reward models with process supervision (PRM), to provide a more accurate reward for every step. One can also define task-specific heuristic functions as rewards (Zhuang et al. 2023
(2021)
; Paul et al. (2023), ;
Hao et al. 2023a).
Search Algorithm. The expansive reasoning space makes exhaustive search infeasible and calls for the use of more efficient search algorithms. For example, CoT implicitly applies greedy decoding for the reasoning step with the highest reward] Another common technique is to sample multiple reasoning chains, and return the one with the highest accumulated reward (Cobbe et al. 2021 Lightman et al.] | Wang et al., (022a)), which in essence a random shooting algorithm (Kothare et 1996). Other widely used search algorithms include DFS ( (ao et al. 2023), beam search (Xie et al., ,023), A (Zhuagg et al., 2023), and MCTS (Hao et al. 2023a Zhao et al., 2024 Chi et al. 2024). An alternative paradigm is learning policy model to maximize the reward (Havrilla et al. 2024 Shao
et al. 2024 with RL, or sample proportional to reward (Yu et al. 2024) for diverse reasoning.
4.2 Library Design
LLM Reasoners implements our unified formulation for multi-step reasoning with a modular design. As illustrated in Figure 7 users can easily set up a reasoning method by defining the WorldModel and SearchConfig igg and importing a SearchAlgori thm. Building on these three main base classes, LLM Reasoners has included new components to augment reasoning, e.g., pre-trained reward models Yuuan et al.) 2024), tool-calling modules (Yao et 2022 Hao et 2023b), and new examples like scientific reasoning, e.g., for chemistry (Ouyang et al. We have also integrated rich LLM APIs, standard evaluation pipelines, and general interactive visualization tool visualizer More details are shown in Appendix
2023).
It's usually implemented token-level greedy decoding.
7

---

Published as a conference paper at COLM 2024
Math
Logical
Common
Embodied
Method
GSM8K
AQuA*
Game24
PrOnto
Strategy
Blocks
CoT
0.37 (0.54)
0.09 (0.34)
0.04
0.58
0.34 (0.76)
0.05
ToT (BFS)
0.53 (0.58)
0.15 (0.42)
0.04
0.52
0.41 (0.76)
0.09
ToT (DFS)
0.45 (0.52)
0.10 (0.36)
0.07
0.44
0.42 (0.76)
0.08
RAP
0.58 (0.64)
0.20 (0.47)
0.07
0.59
0.28 (0.77)
0,51
Table 3: Experimental results of various reasoning methods every dataset. On three datasets marked with *, we evaluate with AutoRace, and also show the answer-based (in brackets) for reference. On other datasets, we evaluate the reasoning chain with oracle verifiers (e.g,, a rule-based program, or simulator) due to their nature of close domains. The best method in every metric is highlighted in bold.
5 Analysis of LLM Step-by-step Reasoning
To better understand multi-step reasoning algorithms and analyze the design elements critical to better reasoning performance, we evaluate them on diverse reasoning datasets, utilizing our AutoRace metric and LLM Reasoners library.
5.1 Datasets
For a comprehensive evaluation, we first collect reasoning tasks of several categories, where each category requires different reasoning skills.
Mathematical Reasoning. We select (1) GSM8K (Cobbe et al. 2021) a popular dataset of math word problems that requires understanding the relationship between numbers and multiple steps of mathematical calculation; (2) AQuA (Ling et al. 2017), which additionally requires the skill to perform algebra operations. Both answer-based and AutoRace metrics are employed on these two datasets. We also include the famous (3) Game 24, following the settings in Yao et al. (2023). This task requires constructing equation with four given numbers and basic arithmetic operations. We evaluate the reasoning chain on Game of 24
with program.
Commonsense Reasoning. We take StrategyQA (Geva et al. 2021 as the commonsense reasoning dataset. Each sample is open-domain yes-no question that requires raising related commonsense knowledge and multiple steps of inference. We evaluate the reasoning chain using both answer-based and AutoRace metries.
Logical Reasoning. The tasks involve a set of logical principles, initial statements, and a concluding hypothesis. The challenge is to perform multi-step deductions to determine if the final hypothesis is true. We use PrOntoQA (Saparov & He 2022) in this category. The evaluation based on rule-based program, since the problems are from close domain.
Embodied Planning. The capability of LLMs to power embodied agents presents an interesting area of study, as it involves the understanding of the physical world, and requires a strong planning ability toward the goal. To assess this capacity for embodied planning, we employ the Blocksworld benchmark (Valmeekam et al.) (202)), where an agent must reach specific block stacking arrangement through moving operations such as Pi PickUp and Stack. For evaluation, we examine whether the generated chain valid and can lead to the target state with simulator.
5.2 Evaluating Reasoning Algorithms
Compared methods. To analyze the connections between recent step-by-step reasoning methods, we pick three representative methods, CoT (Wei al. 2022), ToT (Yao et al. 22023),
and RAP (Hao et al., 2023a). Different CoT which autoregressively decodes the reasoning chain, ToT and RAP define the reward and include tree search algorithms. RAP additionally incorporates an explicit world model.
Configurations. For ToT and RAP, we mainly apply the combination of two rewards: (1)
Self-evaluation: Prompting the LLMs to evaluate the new action, and use the logits of "good" as the reward, Po ("Good" 5, a). (2) Likelihood: Calculating the log-likelln ligeliiildood of predicting the next action given the current state, i.e., (a(a s). The definition of states and the world
8

---

Published as a conference paper at COLM 2024
model for RAP depends on the reasoning tasks. Benefiting from the explicit world model, there are also other rewards available for RAP on certain tasks. More details about RAP implementation are described in Appendix C.1
Implementation details. To ensure reproducibility and accessibility, we use one of the leading open-sourced LLMs, Llama 2 70B (Touvron et al. 2023b), quantized with GPT-Q (Frantar et al., 2022) for all tasks and methods. lo make a fair comparison, we restrict search-based methods to explore up to 10 reasoning chains: The breadth limit is 10 for ToT (BFS), the maximum number of visited terminal nodes is 10 for ToT (DFS), and the maximum number of iterations is 10 in RAP, which based on Monte-Carlo Tree Search. We manually crafted 10 examples of reasoning chains for each task, and all methods share this same example pool. For each test case, 4 examples are randomly sampled to form the demonstrations in the prompt, resulting in 4-shot learning setting.
5.2.1 Results
Table shows a comparative analysis of step-by-step reasoning algorithms. Overall, ToT consistently outperforms the vanilla CoT,, and RAP further improves upon ToT. Notably, the evaluation metric (AutoRace) is generally lower than the answer-based metric, especially in the AQuA and StrategyQA datasets. This discrepancy suggests significant potential for enhancements in future reasoning algorithms. We outline several key findings below.
Reward-guided Search Reduces False Positives. Enhanced exploration in the reasoning space, facilitated by effective reward functions, naturally leads to the superior performance of search-based methods (ToT and RAP) over the autoregressive decoding method CoT. However, a noteworthy observation is that these search- false positive reasoning chains, indicated by the smaller gap between AutoRace and answer- based metric (Table 3,, and higher AutoRace score of reasoning chains with correct answers (Figure Further examination of examples with ToT (BFS) reveals that it effectively avoids some false positives by discarding reasoning steps with low rewards. In contrast, CoT lacks this mechanism "regret". E.g., in type-A false positive chains made by CoT (Table I0), while some reasoning mistakes are identifiable by the LLM itself, CoT fails to amend errors from previous steps, only able overlook them in the following steps.
methods also yield fewer
Importance of Search Breadth Over Depth. By comparing two variants of ToT, ToT (BFS) and ToT (DFS), our results show that BFS is relatively better on two math word problems, logical and embodied tasks. This indicates that when the
AutoRace metric on answer-careed chains
Method
0.8
RAP
ToT (BFS)
ToT (DFS)
search space is expansive, such as in these com- plex math, logic, and embodied planning tasks, DES may sink into inappropriate reasoning sub- space with the first steps, thereby failing to ex- plore the full space. In contrast, for tasks with limited search space, such as Game-24, DFS doesn't 't hamper the exploration.
0.6
0.4
0.2
0.0
Crucial Role of World Model in Embodied Tasks. RAP stands out as the most effective method across most datasets, thanks to its ex- plicit world model. This enables the LLM to predict and track state changes during reason- ing, allowing for decisions based on the current state. Specifically, it outperforms ToT by 42% on Blocksworld. As previous research suggests [Xi ang et al. 2023), LLMS miss essential embodied
GSMBK
AQuA
Strategy
Figure 4: AutoRace metric of different rea- soning methods on answer-correct chains. We find search-based methods, ToT and RAP have higher AutoRace scores, in- dicating fewer false positive reasoning chains.
knowledge and skills, e.g., tracking objects over long action sequences. Thus, an explicit world model that maintains the current state would greatly reduce the difficulties in memo- rizing or reasoning about previous actions in embodied environment.
Impact of Prompt Format on False Positives. Interestingly, Strategy QA witnesses a higher false positive rate of RAP (Figure Based on errors identified by AutoRace, we discovered

---

Published as a conference paper at COLM 2024
1.0
Model
GPT-4 turbo
Opus
Gemini Pro
0.8
InternLM-2
Mixtral 6x78
0.4
Liama-2 708
Owan--1.5
0.2
Gamma 78
7B
Liama-2 138
0.0
GSMBK
AQUA
Game24
PrOntoGA
StralegyQA
Blockswordd
Dataset
Figure 5: Results of various LLMs using CoT on every dataset. We apply AutoRace on three datasets with *, and oracle verifiers on other datasets. On three datasets marked with *, LLMs are ordered by average performance.
common failure mode from the reasoning chains generated by RAP: The prompt design that guides LLMs to iteratively ask and answer sub-questions encourages LLMs to generate excessive details. This makes it easier to introduce factual errors but does not necessarily affect the accuracy of final answers. For example, for the problem presented in Appendix C.2. RAP raises the incorrect number 7,000 in the explanation, which identified as an error by AutoRace. Conversely, CoT avoids this pitfall by not delving into unnecessary details. It's worth noting that, this prompt format is not problem for math reasoning tasks, including GSM8K and AQuA, because every detail needs to be accurate to solve a math problem. This suggests that prompt design should be tailored to the task domain.
5.3 Evaluating Leading LLMs
We also use the same experimental setting to compare the step-by-step reasoning ability
of multiple popular LLMs, including GPT-4 Apen 2023), Claude-3 Opus? Gemeni pro
(Team et al. 2023), InternLM-2 (Cai et al. 2024), Mistral (Jing et al. 2023), Mixtral (Jiang
et 2024). Llama-2 [louvron et al.) 2023b), Qwen (Bai al. 2023), and Gemma (Team
al. 2024). The overall results are shown in Figure 5 with more details in Table 11
Overall Rankings. GPT-4 turbo and Claude-3 Opus are the two with the strongest reason- ing abilities, and they lead on almost every reasoning task. Surprisingly, InternLM-2 7B surpasses much larger models (e.g., Llama-2 70B) on average performance. We also notice 3 which indicates that
the ranking of Top-3 models aligned with ChatArena leaderboard the reasoning ability is indeed crucial to power the SOTA chatbot.
Reasoning Tasks. Top models have achieved remarkable performance on math word prob- lems (GSM8k) and commonsense reasoning (StrategyQA), but reasoning tasks that require strong planning abilities (e.g., Game-24 24 and Blocksworld) remain unsolved, which leaves room for future research. Interestingly, on StrategyQA, the answer accuracy of different models is similar (0.63 0.79), but the AutoRace results differ a lot, ranging from 0.28 to 0.91, with totally different ranking. Further examination reveals the questions in Strategy are often ambiguous and overly simplified. GPT-4, Claude-3, and Gemini demonstrate more thorough consideration of these problems, unlike other models (and sometimes even the ground truth reasoning chains) which can suffer from baseless assumptions and flawed logic. The difference might be attributed to the RLHF process, which aligns model response to human preference.
Conclusion
We propose AutoRace, LLM--owered automated evaluation of reasoning chains, and LLM Reasoners, a unified formulation and library for diverse step-by-step reasoning algorithms. On this basis, we conducted comprehensive experiments to analyze the factors contributing to reasoning. In the future, it will be interesting to extend LLM Reasoners by including more algorithms, supporting fine-tuning methods natively, exploring multi-modal reasoning, and we plan to apply AutoRace for broader comparison.
10

---

Published as a conference paper at COLM 2024
References
Jinze Bai, Shuai Bai, Yunfei Chu, Zeyu Cui, Kai Dang, Xiaodong Deng, Yang Fan, Wenbin Ge, Yu Han, Fei Huang, et al. Qwen technical report. arXiv preprint ar Xrr::23099 16609, 2023.
Jake Bruce, Michael D Dennis, Ashley Edwards, Jack Parker-Holder, Yuge Shi, Edward Hughes, Matthew Lai, Aditi Mavalankar, Richie Steigerwald, Chris Apps, al. Genie: Generative interactive environments. In Forty-first International Conference on Machine Learning, 2024.
Zheng Cai, Maosong Cao, Haojiong Chen, Kai Chen, Keyu Chen, Xin Chen, Xun Chen, Zehui Chen, Zhi Chen, Pei Chu, et al. Internim2 technical report. arXiv preprint arXiv:2403.17297, 2024.
Asli Celikyilmaz, Elizabeth Clark, and Jianfeng Gao. Evaluation of text generation: A survey. ar Xiv preprint ar wxxt:22006.1479, 2020.
Ziru Chen, Michael White, Raymond Mooney, Ali Payani, Yu Su, and Huan Sun. When is tree search useful for 11m planning? it depends the discriminator. arXiv preprint ar arXiv:2402.10880, 2024.
Yizhou Chi, Kevin Yang, and Dan Klein. Thoughtsculpt: Reasoning with intermediate revision and search. Xivv preprint ar Xii::2204405580 2024.
Miruna Clinciu, Arash Eshghi, and Helen Hastie. A study of automatic metrics for the evaluation of natural language explanations. arXiv preprint arXio:2103.08545, 2021.
Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reücchrr Nakano, et al. Training verifiers to solve math word problems. Xiv preprint 01f:::2110.14668 2021.
Antonia Creswell and Murray Shanahan. Faithful reasoning using large language models. arxiv preprint ar arXi::2208.144 142771, 2022.
Bhavana Dalvi, Peter Jansen, Oyvind Tafjord, Zhengnan Xie, Hannah Smith, Leighanna Pipatanangkura, and Peter Clark. Explaining answers with entailment trees. ar Xiv preprint arXit:2104088611 2021.
Dheeru Dua, Yizhong Wang, Pradeep Dasigi, Gabriel Stanovsky, Sameer Singh, and Matt Gardner. Drop: A reading comprehension benchmark requiring discrete reasoning over paragraphs. arviv preprint arXivo1903.00116 0016,,, 2019.
Elias Frantar, Saleh Ashkboos, Torsten Hoefler, and Dan Alistarh. Gptq: Accurate
post-training quantization for generative pre-trained transformers. arXio preprint arXiiv2210017333,, 2022.
Mor Geva, Daniel Khashabi, Elad Segal, Tushar Khot, Dan Roth, and Jonathan Berant. Did aristotle use a laptop? a question answering benchmark with implicit reasoning strategies. Transactions of the Association for Computational Linguistics, 9:346-361, 2021.
Olga Golovneva, Moya Chen, Spencer Poff, Martin Corredor, Luke Zettlemoyer, Maryam Fazel-Zarandi, and Asli Celikyilmaz. Roscoe: A suite of metrics for scoring step-by-step
reasoning. Xio preprint ar arXio:2212.07919, 2022.
Lin Guan, Karthik Valmeekam, Sarath Sreedharan, and Subbarao Kambhampati. Leveraging pre-trained large language models to construct and utilize world models for model-based task planning. Advances in Neural Information Processing Systems, 36:79081-79094, 2023.
Xingang Guo, Fangxu Yu, Huan Zhang, Lianhui Qin, and Bin Hu. Cold-attack: Jailbreaking Ilms with stealthiness and controllability. arXiv preprint ar Xix:2402.008699 2024.
Simeng Han, Hailey Schoelkopf, Yilun Zhao, Zhenting Qi, Martin Riddell, Luke Benson, Lucy Sun, Ekaterina Zubova, Yujie Qiao, Matthew Burtell, et al. Folio: Natural language reasoning with first-order logic. ar Xiv preprint arXiv:2209.008: 00840, 2022.
11

---

Published as a conference paper at COLM 2024
Shibo Hao, Yi Gu, Haodi Ma, Joshua Jiahua Hong, Zhen Wang, Daisy Zhe Wang, and Zhiting Hu. Reasoning with language model is planning with world model. arviv preprint (rXiv:2305.14992 2023a.
Shibo Hao, Tianyang Liu, Zhen Wang, and Zhiting Hu. Toolkengpt: Augmenting frozen language models with massive tools via tool embeddings. arxiv preprint arXiv:2305.11554 2023b.
Alex Havrilla, Yuqing Du, Sharath Chandra Raparthy, Christoforos Nalmpantis, Jane Dwivedi-Yu, Maksym Zhuravinskyi, Eric Hambro, Sainbayar Sukhbaatar, and Roberta Raileanu. Teaching large language models reason with reinforcement learning. ar Xiv preprint ar Xix::2033.0465 2024.
Hangfeng He, Hongming Zhang, and Dan Roth. Socreval: Large language models with the socratic method for reference-free reasoning evaluation. arv preprint 4r1i:02310.00074, 2023.
Anthony Hu, Lloyd Russell, Hudson Yeo, Zak Murez, George Fedoseev, Alex Kendall, Jamie Shotton, and Gianluca Corrado. Gaia-l: A generative world model for autonomous driving. ar Xiv preprint ar orXii:2309.17000 2023.
Zhiting Hu and Tianmin Shu. Language models, agent models, and world models: The law for machine reasoning and planning. arXiv preprint arXiv:2312.05230, 2023.
Lifu Huang, Ronan Le Bras, Chandra Bhagavatula, and Yejin Choi. Cosmos qa: Ma-
chine reading comprehension with contextual commonsense reasoning. arXiv preprint arXivv1909.0000 00009, 2019.
Albert Q Jiang, Alexandre Sablayrolles, Arthur Mensch, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Florian Bressand, Gianna Lengyel, Guillaume Lample, Lucile Saulnier, et al. Mistral 7b. arXiv preprint ar arXiv:2310.06825, 2023.
Albert Q Jiang, Alexandre Sablayrolles, Antoine Roux, Arthur Mensch, Blanche Savary, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Emma Bou Hanna, Florian Bressand, al. Mixtral of experts. arxiv preprint Rfo:2401.040653 2024.
Muhammad Khalifa, Lajanugen Logeswaran, Moontae Lee, Honglak Lee, and Lu Wang. Grace: Discriminator-guidee chain- of-in-of-thought reasoning. In Findings of the Association for Computational Linguistics: EMNLP 2023, pp. 15299-15328, 2023.
Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. Large language models are zero-shot reasoners. arXio preprint ar arXto:2205.1191 2022.
Mayuresh V Kothare, Venkataramanan Balakrishnan, and Manfred Morari. Robust con- strained model predictive control using linear matrix inequalities. Automatica, 32(10): 1361-1379, 1996.
Belinda Z. Li, Maxwell Nye, and Jacob Andreas. Language modeling with latent situations. In Anna Rogers, Jordan Boyd-Graber, and Naoaki Okazaki (eds.), Findings of the Association for Computational Linguistics: ACL 2023, pp. 12556-12571, Toronto, Canada, July 2023. Association for Computational Linguistics. doi: (0.18653/v1/2023 www......ininnggaa....... URL https://aclanthoolgy.ooo
.eeee3..iniiin findings-acl. acl. 795
Hunter Lightman, Vineet Kosaraju, Yura Burda, Harri Edwards, Bowen Baker, Teddy Lee, Jan Leike, John Schulman, llya Sutskever, and Karl Cobbe. Let's verify step by step. arv preprint ar arXi::2305.2003: 2023.
Wang Ling, Dani Yogatama, Chris Dyer, and Phil Blunsom. Program induction by rationale generation: Learning to solve and explain algebraic word problems. arXiv preprint 17X1::1705.04446, 2017.
Ruibo Liu, Jason Wei, Shixiang Shane Gu, Te-Yen Wu, Soroush Vosoughi, Claire Cui, Denny Zhou, and Andrew M Dai. Mind's eye: Grounded language model reasoning through simulation. ar Xiv preprint arXim:2210.05335 2022.
12

---

Published as a conference paper at COLM 2024
Ziyi Liu, Isabelle Lee, Yongkang Du, Soumya Sanyal, and Jieyu Zhao. Score: A framework for self-contradictrry reasoning evaluation. arXiv preprint (rXie:2311.09603, 2023.
Qing Lyu, Shreya Havaldar, Adam Stein, Li Zhang, Delip Rao, Eric Wong, Marianna Apidianaki, and Chris Callison-Burch. Faithful thain-of-thought reasoning. arx preprint arXii:2301.13379, 2023.
OpenAI. Gpt-4 technical report, 2023.
Siru Ouyang, Zhuosheng Zhang, Bing Yan, Xuan Liu, Jiawei Han, and Lianhui Qin. Struc- tured chemistry reasoning with large language models. arXiv preprint ar XrX:::2311.000 1.0666, 2023.
Debjit Paul, Mete Ismayilzada, Maxime Peyrard, Beatriz Borges, Antoine Bosselut, Robert West, and Boi Faltings. Refiner: Reasoning feedback on intermediate representations. arxiv preprint arXio:2304.01904, 2023.
Debjit Paul, Robert West, Antoine Bosselut, and Boi Faltings. Making reasoning matter: Measuring and improving faithfulness of chain-of-thought reasoning. arXiv preprint drXfv:2402.1395,, 2024.
Archiki Prasad, Swarnadeep Saha, Xiang Zhou, and Mohit Bansal. Receval: Evaluating reasoning chains via correctness and informativeness. arXiv preprint ar arXio:2304.1070, 2023.
Abulhair Saparov and He He. Language models are greedy reasoners: systematic formal analysis of thain-of-thought. arXiv preprint arXio:2200001200, 2022.
Zhihong Shao, Peiyi Wang, Qihao Zhu, Runxin Xu, Junxiao Song, Mingehuan Zhang, YK Li, Yu Wu, and Daya Guo. Deepseekmath: Pushing the limits of mathematical reasoning in open language models. arXiv preprint ar 2rXiv:2402.03300 2024.
Aarohi Srivastava, Abhinav Rastogi, Abhishek Rao, Abu Awal Md Shoeb, Abubakar Abid, Adam Fisch, Adam R Brown, Adam Santoro, Aditya Gupta, Adrià Garriga-Alonso, et al. Beyond the imitation game: Quantifying and extrapolating the capabilities of language models. Transactions on Machine Learning Research, 2023.
Zhiqing Sun, Longhui Yu, Yikang Shen, Weiyang Liu, Yiming Yang, Sean Welleck, and Chuang Gan. Easy-to-hard generalization: Scalable alignment beyond human supervision. arXiv preprint arXio:2403.09472 2024.
Gemini Team, Rohan Anil, Sebastian Borgeaud, Yonghui Wu, lean-Baptiste Alayrac, Jiahui Yu, Radu Soricut, Johan Schalkwyk, Andrew M Dai, Anja Hauth, et al. Gemini: family of highly capable multimodal models. ar Xiv preprint ar xix1:23312 2023.
Gemma Team, Thomas Mesnard, Cassidy Hardin, Robert Dadashi, Surya Bhupatiraju, Shreya Pathak, Laurent Sifre, Morgane Rivière, Mihir Sanjay Kale, Juliette Love, et al. Gemma: Open models based on gemini research and technology. arXio preprint arXiv:2403.08295, 2024.
Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al. Llama: Open and efficient foundation language models. arXiv preprint ar 230::2300..3971 2023a.
Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, al. Llama Open foundation and fine-tuned chat models. Xrv preprint arXin:2307.09928,, 2023b.
Gladys Tyen, Hassan Mansoor, Peter Chen, Tony Mak, and Victor Cärbune. Lims cannot find reasoning errors, but can correct them! ar arXio preprint 2011002311.08516, 2023.
13

---

Published as a conference paper at COLM 2024
Karthik Valmeekam, Sarath Sreedharan, Matthew Marquez, Alberto Olmo, and Subbarao Kambhampati. On the planning abilities of large language models (a critical investigation with proposed benchmark). Xio preprint ar arXio:2302.06706 2023.
Peiyi Wang, Lei Li, Zhihong Shao, RX Xu, Damai Dai, Yifei Li, Deli Chen, Y Wu, and Zhifang Sui. Math-shepherd: A label-free step-by-step verifier for Ilms in mathematical reasoning. arXiv preprint ar arXio:2312.08935, 2023a.
Xinyuan Wang, Chenxi Li, Zhen Wang, Fan Bai, Haotian Luo, Jiayou Zhang, Nebojsa Jojic, Eric P Xing, and Zhiting Hu. Promptagent: Strategic planning with language models enables expert-level prompt optimization. arXiv preprint ar Xro:23310.16427, 202.b.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Ed Chi, Quoc Le, and Denny Zhou. Chain of thought prompting elicits reasoning in large language models. arXiv preprint ar Xiv:2201. 0e022220111900 11903, 2022.
Sean Welleck, Jiacheng Liu, Ximing Lu, Hannaneh Hajishirzi, and Yejin Choi. Naturalprover: Grounded mathematical proof generation with language models. Advances in Neural Information Processing Systems, 15:4913-4922 2022.
Sean Welleck, Amanda Bertsch, Matthew Finlayson, Hailey Schoelkopf, Alex Xie, Graham Neubig, Ilia Kulikov, and Zaid Harchaoui. From decoding to meta mnea--eeeeattion Inference- time algorithms for large language models. arXiv preprint arXiv:2406.16838. 2024.
Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, Joe Davison, Sam Shleifer, Patrick von Platen, Clara Ma, Yacine Jernite, Julien Plu, Canwen Xu, Teven Le Scao, Sylvain Gugger, Mariama Drame, Quentin Lhoest, and Alexander M. Rush. Transformers: State-of-the-art natural language processing. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations, pp. 38-45, Online, October 2020. Association for Computational Linguistics. URL https: //t////ww www. ac aclweb. org/ anthology/2026 2020. emnlp-demos.E
Shijie Xia, Xuefeng Li, Yixin Liu, Tongshuang Wu, and Pengfei Liu. Evaluating mathematical reasoning beyond accuracy. ar Xii preprini ar Xiv:2444.0056) 2024.
Jiannan Xiang, Tianhua Tao, Yi Gu, Tianmin Shu, Zirui Wang, Zichao Yang, and Zhiting Hu. Language models meet world models: Embodied experiences enhance language models. Advances in neural information processing systems, 36, 2023.
Jiannan Xiang, Guangyi Liu, Yi Gu, Qiyue Gao, Yuting Ning, Yuheng Zha, Zeyu Feng, Tianhua Tao, Shibo Hao, Yemin Shi, et al. Pandora: Towards general world model with natural language actions and video states. arXiv preprint ar arXto:2406.09455, 2024.
Yuxi Xie, Kenji Kawaguchi, Yiran Zhao, Xu Zhao, Min-Yen Kan, Junxian He, and Qizhe Xie. Self-evaluation guided beam search for reasoning. In Thirty--eventh Conference on Neural Information Processing Systems, 2023.
Ze Yang, Yun Chen, Jingkang Wang, Sivabalan Manivasagam, Wei-Chiu Ma, Anqi Joyce Yang, and Raquel Urtasun. Unisim: A neural closed-loop sensor simulator. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 1389-1399, 2023.
Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik Narasimhan, and Yuan Cao. React: Synergizing reasoning and acting in language models. arXiv preprint arXiv:2210.03629, 2022.
Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. arviv preprint ar Xiv::2330 10601, 2023.
Fangxu Yu, Lai Jiang, Haoqiang Kang, Shibo Hao, and Lianhui Qin. Flow of reasoning: Efficient training of Ilm policy with divergent thinking. arv preprint ar Xio:2406.05673. 2024.
14

---

Published as a conference paper at COLM 2024
Lifan Yuan, Ganqu Cui, Hanbin Wang, Ning Ding, Xingyao Wang, Jia Deng, Boji Shan, Huimin Chen, Ruobing Xie, Yankai Lin, et al. Advancing Ilm reasoning generalists with preference trees. ar arviv preprint ar 4r0::2200..0007, 2024.
Zirui Zhao, Wee Sun Lee, and David Hsu. Large language models as commonsense knowl- edge for large-scale task planning. Advances in Neural Information Processing Systems, 36, 2024.
Denny Zhou, Nathanael Schärli, Le Hou, Jason Wei, Nathan Scales, Xuezhi Wang, Dale Schuurmans, Olivier Bousquet, Quoc Le, and Ed Chi. Least-to-most prompting enables complex reasoning in large language models. Xiv preprint ar arXiv:2205.1062. 2022.
Xinyu Zhu, Junjie Wang, Lin Zhang, Yuxiang Zhang, Ruyi Gan, Jiaxing Zhang, and Yujiu Yang. Solving math word problem via cooperative reasoning induced language models. arviv preprint ar XrX::22210.16257, 2022.
Yuchen Zhuang, Xiang Chen, long Yu, Saayan Mitra, Victor Bursztyn, Ryan A Rossi, Somdeb Sarkhel, and Chao Zhang. Toolchain*: Efficient action space navigation large language models with a* search. at Xiv preprint 2xX1::2310.1122, 2023.
15

---

Published as a conference paper at COLM 2024
Method
Math
Common
Logical
Dataset
GSMSk
Arith
Strategy
Cosmos
Logic
Sort
Correctans
110
45
100
82
45
45
Incorrectens
90
255
100
97
255
255
Correctramon
101
62
71
34
Incorrectruman
99
238
129
148
294
266
FP rate
0.16
0
0.39
0.67
0.87
0.33
Table 4:
The distribution of datasets for evaluation metrics.
Method
Math
Common
Logical
Dataset
GSM8k
Arith
Strategy
Cosmos
Logic
Sort
Answer-based
0.89
0.99
0.76
0.63
0.87
0.94
SocREval
0.89
0.92
0.96
0.91
0.89
0.76
Direct (trace)
0.90
0.34
0.78
0.74
0.21
0.33
Direct (step)
0.96
0.44
0.85
0.87
0.75
0.32
Co'l' (step)
0.93
0.88
0.78
0.84
1.00
0.87
AutoRace (Ours)
0.91
0.90
0.82
0.84
0.97
0.87
Table 5: Evaluation accuracy for reasoning chains labeled incorrect by humans.
A Additional Details of AutoRace
A.1 Dataset Statistics
For all datasets we experiment on, we list the statistics by answer labels and human labels in Table We also include the false positive (FP) rate, defined as the proportion of instances with correct answers but labeled as incorrect by human evaluators, relative to the total number of instances with correct answers.
A.2 Results on Reasoning Chains of Different Human Labels
We calculate the accuracy on two subsets: (1) reasoning chains labeled correct by human, and (2) reasoning chains labeled incorrect by human. The results are listed Table and 6 Generally, AutoRace balances the performance on both datasets, while SocREval suffers from a severe drop on the reasoning chains labeled incorrect.
Method
Math
Common
Logical
Dataset
GSM8k
Arith
Strategy
Cosmos
Logic
Sort
Answer-based
0.99
0.71
0.76
0.87
1.00
0.88
SocREval
0.89
0.55
0.24
0.29
1.00
0.85
Direct(trace)
0.89
0.58
0.83
0.58
1.00
0.68
Direct(step)
0.74
0.40
0.78
0.03
0.83
0.38
(step)
0.82
0.11
0.78
0.13
1.00
0.14
AutoRace (Ours)
0.90
0.85
0.72
0.45
1.00
0.74
Table 6: Evaluation accuracy for reasoning chains labeled correct by humans.
16

---

Published as a conference paper at COLM 2024
(Criteria learned for Mult
Question:
What is the result of
-1"-7--2"0 + ((3 2 34""
SocREval (Baseline)
Proper Operation Order interpretation of Logical Consiterxy
-C
Step 1: equation be written
(-42)) 420
response: simplifies
simplifies
AutoRace
Step Let's calculate
into 11 112 which equals -221.
Step 4: This an incorrect calculation, The specifically calcuiation the calculation
Step 4: Let's
Analysis: The generated response is cornect and detailed-
2(332+ 3- 9- -6)
(16 + 2) 212 -12-000000 541) (10 422 -220
Overall quality: (Correct)
Step 6 the answwer -521
So the reasoning chain not correct
GPT-4 evaluator made the same mistake
(Reasoning chain evallated)
Successfully recognized the error
Figure 6: A case study on MultiArith (Srivastava et al. 2023). SocREval (He al. 2023 requires GPT-4 to generate its own response to the problem, and then use it as the reference to evaluate the reasoning chain. In this case, makes the same mistake as the reasoning chain. AutoRace successfully recognized the calculation error, guided by the criterion list learned for this task.
Method
Word-Sort (Long)
Strategy QA (Short)
SocREval
1686 / 427 / $0.030
357 / 269 / $0.012
Direct (trace)
2265 1 $0.023
507 / 1 $0.005
Direct (step)
17517 / 12 / $0.176
1349 / 4 $0.014
CoT (step)
26839
5504 / $0.434
2688 575 / $0.044
AutoRace (Ours)
1382 / 435 / $0.027
270 / 389 $0.014
Table 7:
Average cost on problem for different evaluation methods, in the form of (input token number / output token number cost per question).
A.3
Case Study
In Figure 6,
we show a case study of AutoRace on MultiArith (Srivastava et al. 2023 in
comparison with SocREval (He et al. 2023).
A.4
Comparison the Cost of Reasoning Chain Evaluation Metrics
Table shows the average input token number, output token number, and the cost per question using different evaluation methods. We list the statistics on two tasks: Word-Sort, which usually has long reasoning chains, and StrategyQA, which has shorter reasoning chains.
A.5 Example Number of Criteria List Construction
use 4 incorrect reasoning chains create criterion list. Here, we further explored different sample sizes (2, 4, 10) in Table
For each task in Table 11
The results indicate that AutoRace is relatively robust the sample set size. We found that it's because:
Math
Common
Logical Logic
Method
Average
GSMSk
Arith
Strategy
Cosmos
Sort
AutoRace (2)
0.88
0.84
0.84
0.75
0.96
0.86
0.85
AutoRace (4)
0.91
0.85
0.79
0.78
0.97
0.86
0.86
AutoRace (10)
0.86
0.82
0.84
0.77
0.98
0.89
0.86
Table 8: The performance of AutoRace with different number of incorrect reasoning chains
(2, 4, 10) construct the criteria list.
17

---

Published as a conference paper at COLM 2024
Math
Common
Logical
Method
Average
GSM8K
Arith
Strategy
Cosmos
Logic
Sort
AutoRace
0.91
0.85
0.79
0.78
0.97
0.86
0.86
SocREval
0.89
0.85
0.71
0.80
0.89
0.77
0.82
SocREval (GSM8K)
0.89
0.84
0.63
0.74
0.85
0.81
0.79
AutoRace (GSM8k)
0.91
0.83
0.73
0.69
0.99
0.89
0.84
Table 9: The performance of AutoRace and SocREval (He et al. 2023) list peot/rompt for GSM8k.
using the criteria
Besides concrete errors in examples, GPT-4 can also infer some evaluation criteria from the problem domain. E.g., For math word problems, if there is calculation error in the examples, GPT-4 may supplement criterion about "accurate calculation".
GPTT4 has certain prior knowledge on how to evaluate a reasoning chain. Thus, even if criterion list misses some items, GPT-4 still has chance to correctly evaluate a reasoning chain with that type of error.
A.6 Generalization of Criteria List
To understand how general the criteria list constructed by AutoRace is, we test with the AutoRace criterion list of GSM8k on tasks. We also test SocREval (He et al., 2023) on tasks with its prompt for GSM8k. As shown in Table AutoRace shows good generalization across different reasoning tasks.
A.7 AutoRace Prompt
In this section, we demonstrate the pipeline of AutoRace for GSM8k (Cobbe et al. 2021 as examples. For other reasoning tasks, the template is the same, and only the questions, student answers, and extracted criteria need to be replaced.
Prompt for detection and summarization
You a teacher. Below are some questions, reference answers and the answers from students.
Question:
Janet's s ducks lay 16 eggs per day. She eats three for breakfast every morning and bakes muffins for her friends every day with four. She sells the remainder at the farmers' market daily for $2 per fresh duck egg. How much in dollars does she make every day at the farmers' market?
Reference answer:
Janet sells 16 3 - 4 = 9 duck eggs day. She makes 9 * 2 = 18 every day at the farmer's market.
Student answer: Janet's ducks lay 16 eggs per day. She eats three for breakfast every morning and bakes muffins for her friends every day with four. This means she uses 4 eggs every day. She sells the remainder at the farmers' market daily for $2 per fresh duck egg. So she sells (16 - 7) $2 $6 worth of eggs every day. The answer is 6.
Question:
Claire makes a 3 egg omelet every morning for breakfast. How many dozens of eggs will she eat in 4 weeks? Reference answer:
18

---

Published as a conference paper at COLM 2024
She eats 3 eggs every day and there 7 days in week she eats 3*7 21 eggs a week After 4 weeks she will have eaten 4+21 = 84 eggs There are
12 eggs in dozen and she'll eat 84 eggs that's 84/12 dozen eggs.
Student answer:
Claire makes a egg omelet every morning. In week she will eat 3 21 eggs. In 4 weeks she will eat 4 21 84 eggs. The answer is 84.
Question:
Gloria is shoe shopping when she comes across pair of boots that fit her shoe budget. However, she has to choose between the boots and two pairs of high heels that together cost five dollars less than the boots. If one pair of heels costs $33 and the other costs twice as much, how many dollars are the boots?
Reference answer:
The second pair of heels costs 33 $66. The heels together cost 66 33 = $99. The boots cost $5 more than both pairs of heels together, so the boots cost 99
$104.
Student answer:
We know that one pair of heels costs $33 and the other pair costs twice as much. This means that the other pair costs $33 2 $66. Together, the two pairs of heels cost $33 + $66 = $99. The boots cost five dollars less than the heels, the boots cost $99 $5 $94. The answer is $94.
Question:
Mark's car breaks down he needs to get a new radiator. The cost for new radiator is $400 but he goes to get it at a junk shop and gets it for 80% off. He then hires a mechanic to install it and it takes 3 hours at $50 an hour. How much did he pay? Reference answer:
The discount the radiator was 400x.8-$33 So he paid 400-320-$80 The mechanic charges 3*50=$150 So in total he paid 80+1 10+1500$230 Student answer: The cost for new radiator is $400. He got it at a junk shop for 80% off, so he paid $400 0.8 $320 for the radiator. The mechanic charged him $50 per hour for 3 hours, so he paid $50 3 = $150 for the labor. In total, he paid $320 $150 $470. The answer is 470.
Please summarize the mistakes in short sentence for the question. At the end, please make a brief list of criteria. Make sure they are general and not specific these questions so that others can grade the answers for other answers by following these criteria.
Prompt for Evaluation
Below is question and an answer from student. You are required to check the correctness of the reasoning chains step by step. The criteria are as follows:
**Accuracy in Mathematical Operations:** Ensure calculations are correct and follow logical mathematical principles.
**Understanding the Problem Statement:** Comprehend the details and condi tions of the question accurately. **Correct Application of Mathematical Concepts:** Apply the right mathematical formulas, operations, or concepts solve the problem. **Unit Conversion and Appropriateness::* When required, correctly convert units use appropriate units the answer.
**Final Answer Relevance: Ensure the final answer directly addresses the question asked, and is presented clearly and concisely.
19

---

Published as a conference paper at COLM 2024
Type
Question
Reasoning Chain
Explanation
A
Henry made two stops during his 60-mile bike trip. He first stopped af- ter 20 miles. His second stop was 15 miles before the end of the trip. How many miles did he travel between his first and sec- ond stops?
Step Henry traveled 20 miles + 15 miles 35 miles between his first and sec- ond stops.
There is hallucination in early reasoning step, but the following reasoning steps ignore the mistake and reach the correct answer.
Step 2- Henry traveled 60 miles 35 miles 25 miles without stopping. Step 3-
The answer is 25
Is "A Tale of Two Cities" B
"A Tale of Two Cities" was published in 1859, and the Bible was published much earlier. Thus, "A Tale of Two Cities" is not parody the Bible. So the answer is
The reasoning chain has obvious or multi- ple mistakes, but hits the correct answer by chance.
parody of the Bible?
C
Is clementine pith highly sought after?
Clementine pith is not highly sought after. So the answer no.
The reasoning chain is not informative at all, though the answer correct.
Table 10: Common types of false positive reasoning chains detected by AutoRace. The example questions are from StrategyQA (Geva et al. 2021) and GSM8k (Cobbe et al. 2021 and the reasoning chains are generated by Llama-2 70B. An explanation tor each type of false positive reasoning chain is attached."
**Logical Reasoning and Step-by-Step Explanation:** The answer should include a logical, step-by-step explanation that demonstrates how the final answer was reached.
Question: [QUESTION]
Student answer: [INPUT]
Please check the answer through each criterion, and make sure you carefully examine each reasoning step. Finally, there is any step that fails the verification, output an INCORRECT, or else output CORRECT.
The criteria provided by the GPT in the Summarization step.
A.8 False Positive Reasoning Chains Detected by AutoRace
AutoRace can serve as scalable way to detect false positive reasoning chains. Here, we summarize several types of false positive reasoning chains in Table 10
A.9 Pseudo-code of AutoRace
We present the pseudo-code of AutoRace in Algorithm i
20

---

Published as a conference paper at COLM 2024
Algorithm 1 Criteria list construction of AutoRace
Input: Student LLM fstudent- LLM, GPT-4 fGPT-4, a, training set of questions, reference answers, and reasoning chains Drain = [x, yr, 2r , a prompt template to create criterion Teriterion. the expected number of error examples
2: Output: Criterion list C
Sample(Drrain (rain) 4: Derror < EmptySet
Initialize the incorrect reasoning chain set Randomly sample subset of the training set
5: for (x,yr. in DanDDan do
6:
v, (LM)))))
Answer the question with the student LLM
7:
if y + y,, then
Add (x, 2] Derror
Collect incorrect reasoning chains
9:
if | 2 n then
10:
break
> Already enough error examples
11:
end if 12: end if
13:
end for
14: C= fGPT ( CerroorTernin Teriterion)
b Let GPT-4 summarize from error examples
from reasoners import SearchConfig, WorldMadel, Reasoner
fron algorits import MCTS reasoners. import Llana2Model
class (Nbottooddd((tttttMeeeee)))
def step(self, return self.
action):
action))
class (yconrig(Searchhonnigg::
def reward(self, state, action): return self.
actian))
reasoner Reasoner www.://wdnoodeeeeyoooooooooooooe search_.contlg-tyy/onttgsl search_algpo+(T5())
Figure 7: The three key components in a reasoning algorithm, reward function, world model, and search algorithm in the formulation (top), correspond to three classes in LLM Reasoners. To implement a reasoning algorithm for certain domain Reasoner object), a user may inherit the SearchConfiz and WorldMode class, and import any SearchAlgorithe
B Details of LLM Reasoners
World Model. The WorldModel class is responsible for managing all the state changes during reasoning. It includes init_state to create the initial state, step to predict the next states, and is_ terminal to identify terminal states. Utilizing our consistent API, users can effortlessly implement a world model for specific task, or adapt the default world model recording previous actions, done in CoT (Wei et al. 2022), ToT (Yao al. 2023), etc.
Search Configuration. The SearchConf ig class mainly includes two important functions: get_actions decide the action space under each state to facilitate searching, and reward to assess the quality of each reasoning step.
Search Algorithm. The SearchAlgori thm specifies the strategy to explore the reasoning space. We have implemented several search algorithms in our library, e.g., Greedy De- coding (Khalifa
2023 Beam Search (Xie al.) 2023 Creswell & Shanahan 2022), Depth-first Search Searhh (ao et al. 2023), and Monte-Carlo Tree Search (Hao et al. 2023a) These algorithms are designed to work seamlessly with any world model and search configuration any reasoning task.
Other Features. LLM Reasoners has integrated To power these modules above with LLMs conveniently, we offer standardized interface LanguageModel that supports range of LLM libraries, including HuggingFace transformers (Wolf et al.) 2020), facebookresearch/ /ll/mmmmm lama (Touvron et al. 2023a b), APIs of GPT (penAll2223)) Claude and Gemini (Team et al. 2023). We also integrated libraries specialized in quantization, like Exllama (Frantar et al. 2022 to reduce the hardware requirements. Additionally, the Benchmark class provides
21

---

Published as a conference paper at COLM 2024
THe
8
State
Aclinn
"Te taks up
Fold the crange bleck, the red pollww blok on top the red Mala.
Edack
33
24
Figure 8: A screenshot of the visualization tool to diagnose the RAP algorithms on the Blocksworld task.
standard platform (e.g., standard prompts, evaluation methods) for a collection of widely recognized reasoning tasks, such as GSM8k (Cobbe et al., 2 StrategyQA (Geva et al. 2021), and Blocksworld (Valmeekam et al. 2023). We also include Visualizer, an interactive visualization tool that allows for the straightforward depiction of the search trees. This tool significantly lowers the complexity of developing and analyzing the complicated reasoning process. We show a screenshot of the visualization module of LLM Reasoners in Figure 8 Users have the option to upload the log file to our server with one line of code and use the web-based visualization to debug the reasoning algorithms. It allows users to interact with the log by selecting different reasoning trees, and checking the details of each node and edge in the tree. This tool significantly lowers the difficulty of applying complex reasoning algorithm to new tasks.
C
Additional Details of Experiment Analysis
C.1 Details of RAP Implementation
We explicitly define states and world models in RAP. For free-form question-answeringg tasks, including GSM8k, AQuA, and StrategyQA, state is considered as the set of known variables. An action involves posing a sub-question about an unknown variable. The world model then responds to this sub-question, thereby augmenting the state with the value of a new intermediate variable. For tasks with a clearly defined intermediate state, such as the remaining numbers in Game of 24, the latest facts in PrOntoQA, and the current block arrangement in Blocksworld, we directly employ these intermediate states in natural language description. Actions in these scenarios are defined respectively as basic arithmetic operation, a one-hop logic reasoning, and a single block movement. The world model prompted to predict the subsequent state as per the task's definition.
In GSMSK, AQuA, and StrategyQA, we use the rewards from the confidence of state transition and self-evaluation of usefulness of each step. In Game of 24, we use the rewards from self-evaluation of the possibility to achieve 24 for state after each step. In PrOntoQA, we use the rewards of action likelihood and self-evaluation of the correctness of each step. In Blocksworld, we use the rewards from the action likelihood and task-specific heuristics, ie., the number of achieved subgoals.
C.2 Case Study on Prompt formats
Below, we present the reasoning chain of RAP and CoT to a question in Strategy
22

---

Published as a conference paper at COLM 2024
Model
GSM8k
AQuA
Game24
Pronto
Strategy
Block
Average
GPT-4 turbo
0.86 (0.93)
0.59 (0.71)
0.09
0.75
0.91 (0.65)
0.45
0.66
Claude-3 Opus
0.90 (0.90)
0.57 (0.79)
0.07
0.88
0.78 (0.63)
0.41
0.66
Gemini pro
0.67 (0.72)
0.28 (0.48)
0.08
0.52
0.46 (0.71)
0.15
0.45
InternLM-2771 7B
0.61 (0.68)
0.17 (0.45)
0.03
0.45
0.31 (0.69)
0.10
0.39
Llama-2 70B
0.37 (0.54)
0.09 (0.34)
0.04
0.58
0.34 (0.76)
0.05
0.35
Qwen-1.5 7B
0.53 (0.56)
0.17 (0.28)
0.05
0.21
0.33 (0.79)
0.06
0.33
Gemma-78
0.48 (0.57)
0.16 (0.34)
0.02
0.34
0.30 (0.66)
0.10
0.33
Mistral 7B
0.38 (0.41)
0.12 (0.32)
0.02
0.40
0.28 (0.66)
0.09
0.33
Llama-2 13B
0.24 (0.29)
0.06 (0.20)
0.04
0.42
0.28 (0.66)
0.05
0.25
Table 11: The comparison of different models across various tasks. GSM8K, AQuA and
Strategy are evaluated with AutoRace (The answer accuracy is shown as reference in the bracket). Other results use the oracle verifier.
-Question-
Did either Kublai Khan or his grandfather practice monogamy? RAP
Step 1: Did Kublai Khan have a harem? Kublai Khan had a harem of 7,000 women.
So the answer is yes.
Step 2: Did Genghis Khan have harem? Genghis Khan had harem of 500 women.
So the answer
yes.
Step 3: Does having harem of women mean practicing polygamy? Having
harem women means practicing polygamy. So the answer is yes. Step 4: Now
answer the question: Did either Kublai Khan
hisgrandfather practice monogamy? Kublai Khan had a harem of 7,000 women. Genghis Khan had harem of 500 women. Having a harem of women means practicing polygamy. Thus, neither Kublai Khan nor his grandfather practiced monogamy. So the answer is no.
-CoT
Step 1: Both Kublai Khan and his grandfather, Genghis Khan, were polygamous.
Step 2: Thus, neither Kublai Khan nor his grandfather practiced monogamy.
Step 3: So the answer no.
-reference-
Step 1: Kublai Khan was married multiple times and was said by some to have thousands of concubines.
Step 2: Kublai Khan's grandfather was Genghis Khan.
Step 3: Genghis Khan had six wives and was said to have over 500 concubines.
Step 4: So the answer is no.
C.3 AutoRace Leaderboard
We show the detailed evaluation results leading LLMs in Table 11
23


Reviews:
[{"review_id": "dd6uzGpunU", "reviewer": "Reviewer_5tZW", "summary": "This paper proposes a framework (AutoRace) to automate the evaluation of large language models (LLMs) on reasoning tasks. Specifically, the framework evaluates the reasoning chains generated by LLMs. The authors have created a library to formalize the evaluation of existing reasoning tasks across various prompting techniques, such as chain-of-thought, beam search, tree-of-thought, and reasoning-via-planning.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your encouraging comments that AutoRace is performant and can be a key to standardizing LLM evaluation!\n\n**Pseudocode**\n\nWe attach the pseudocode of the criterion list construction to this [link](https://anonymous.4open.science/r/rebuttal-F471/autorace-algo.pdf) due to the formatting issue of OpenReivew. After the criterion list is constructed, it's straightforward to prompt GPT-4 with it to evaluate new reasoning chains.\n\n**Consistency of Criteria list**\n\nThe criteria list is generated by GPT-4. To ensure the consistency of the criterion list, we divide criteria list construction into three easier subtasks for GPT-4: (1) Collecting wrong reasoning chains (2) Detecting the errors (3) Summarizing the criteria list. \n\nBesides, our manual examination reveals that the constructed criterion lists for all tasks look reasonable (See an example in Appendix D.2). Finally, the comparative experiments in Section 3 demonstrate that AutoRace consistently outperforms established baselines, affirming the reliability of the generated criterion lists.\n\n**Case study**\n\nWe have listed several successful cases of AutoRace in Table 6 and Appendix G.We conduct additional case studies and collect several failure examples ([link](https://anonymous.4open.science/r/rebuttal-F471/autorace-error.pdf)). Errors made by AutoRace can be mainly attributed to (1) Incorrect understanding of questions (2) Wrong calculation (3) Being too strict on some corner cases.\n\n**Bias of LLM evaluator**\n\nIn our experiments, we observed that while LLM evaluators are effective at identifying reasoning errors, they sometimes tend to misclassify correct reasoning chains as erroneous (refer to the confusion matrix in Figure 3). Compared to the previous LLM evaluation method SocREval [1], **AutoRace exhibits less bias**. This improvement is attributed to the fundamental difference in their evaluation processes. SocREval relies on the evaluator LLM to first correctly solve the problem. Once the evaluator LLM itself fails to do so, it will misclassify correct reasoning chains as wrong. In contrast, AutoRace is not constrained by the evaluator’s problem-solving capabilities. Instead, it assesses the reasoning chain based on established criteria, simplifying the evaluation task.\n\nThanks again for your review and suggestion. We will update our paper with the pseudo-code and case study.\n\n[1] He et al., 2023, “Large language models with the Socratic method for reference-free reasoning evaluation”", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "1. The paper focuses on automating the reasoning chain evaluation task, which can be a key to standardizing LLM evaluation.\n2. The authors have provided a comprehensive comparison with contemporary techniques and demonstrated the superior performance of AutoRace.", "reasons_to_reject": "1. The authors described their evaluation algorithm but did not provide the pseudocode.\n2. In the last paragraph of section 3.1, it is unclear whether the criteria list is predefined or generated by GPT-4. If GPT-4 generates the list, how is its consistency maintained?\n3. It is unclear which reasoning chains the evaluator can correctly assess and which ones it misses. An ablation study is needed.\n4. Are there any biases introduced by the LLM evaluator?", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5BnhoMzIUM", "reviewer": "Reviewer_rws2", "summary": "The paper introduces AutoRace for automated evaluation of LLM reasoning chains and LLM Reasoners, a library standardizing reasoning algorithms for systematic comparison. These tools enable detailed analysis of reasoning methods, revealing insights into factors like reward guidance, search strategies, world models, and prompt formats.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": true, "final_justification": "", "rebuttal": "Thanks for acknowledging that AutoRace is an interesting evaluation framework, and LLM Reasoners nicely formulated reasoning problems under a common framework.\n\n**Steps taken in Autorace**\n\nWe have described the steps of implementing AutoRace in Section 3.1, along with a concrete running example for illustration (Figure 2). Briefly, it first creates a criterion list for a reasoning task automatically, by (1) collecting a list of wrong reasoning chains, (2) asking GPT-4 to elaborate the errors in them (3) summarizing the concrete errors into a criterion list. Finally, we apply the criterion list to evaluate new reasoning chains with GPT-4.\n\n**Empirical findings most known**\n\nWe respectfully disagree with this claim. In Section 5, we have presented several novel findings:\n1. Reasoning as reward-guided search helps not only improve final accuracy, but also effectively alleviate false-positive reasoning chains;\n2. For efficient search in the reasoning space, the breadth of search is generally more important than the depth for most tasks;\n3. incorporating a world model that explicitly infers reasoning state would effectively improve the LLM reasoning ability, particularly for tasks in embodied environments;\n4. inappropriate prompt format design might inadvertently lead to false positive reasoning chains.\n\nThese findings are from our comprehensive analysis of reasoning methods, which rely on our new reasoning chain evaluation method and the unified library. To the best of our knowledge, these findings haven’t been discussed in previous studies.\n\n**No comparison & Accuracy of AutoRace**\n\nIn Section 3, we have compared AutoRace to four baseline methods for reasoning chain evaluation. In Table 1, we show that AutoRace can achieve 86% accuracy averaged on 6 human-annotated datasets, while the best baseline can only achieve 82%. It’s also the only method that performs within 5% of the best results across all six datasets, showing outstanding robustness. We have made a more detailed comparison with Socreval [1], the strongest baseline, by visualizing the confusion matrix (Figure 3), conducting case studies (Figure 6), and discussing the source of performance improvement (Section 3.2).\n\nWe hope this response adequately addresses your concerns. We are eager to engage in discussions and welcome any additional questions you may have.\n\n[1] He et al., 2023, “Large language models with the Socratic method for reference-free reasoning evaluation”", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "- The work presents an interesting framework for evaluating reasoning tasks.\n- They nicely formulated the reasoning problem under a common framework.", "reasons_to_reject": "- The steps taken in Autorace to annotate are not clear.\n- The empirical findings are mostly known. However, after the rebuttal phase, I can see enough novelties in the empirical findings. \n- No comparison in Autorace annotation quality.", "questions_to_authors": "-Can you give an estimate of how accurate auto race annotations are?", "extra_scores": {}}, {"review_id": "1VjT6rh6jy", "reviewer": "Reviewer_SuhS", "summary": "This paper presents principled methods on how to organize automatic evaluation of reasoning chains (AutoRace) and design a tailored evaluation library with a unified view of LLM reasoning algorithms. The authors conduct an extensive study on various configurations, including the choice of LLMs and promptings. Their experiments reveal some interesting findings, e.g., search breadth is superior to depth in LLM reasoning.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for recognizing that AutoRace is fully automatic and performant, LLM reasoning is a good principle, and the experiments suggest intriguing observations about LLM reasoning!\n\n**Novelty**\n\nWe’d like to highlight 3 novel contributions of this work:\n- We propose a novel reasoning chain evaluation method and show the promise to be an important metric complementing answer-based evaluation.\n- We present a novel perspective to unify numerous current reasoning methods, and build a library for developing, deploying, and analyzing reasoning algorithms.\n- Our comprehensive experiments lead to several novel findings about LLM reasoning:\n  - Reward-guided search reduces false positives\n  - Search breadth matters more than depth\n  - World model is crucial for embodied tasks\n  - Inappropriate prompt format may lead to false positives\n\n**Reliance on training set**\n\nWhile we understand this is a reasonable concern, we argue that most reasoning datasets already include a training set, which eliminates the need for specific construction for AutoRace. Furthermore, as AutoRace can be effective with a very **small** demonstration set, which we will show below, even if the training set is not available, it’s easy to find or create a few demonstrations and apply AutoRace.\n\nFor each task in Table 1, we use only 4 wrong reasoning chains to create a criterion list. Here, we further explored different sample sizes (2, 4, 10).\n\n|Method|GSM8k|Arith|StrategyQA|Cosmos|Logic|Sort|**Average**|\n|-|-|-|-|-|-|-|-|\n|AutoRace (2)|0.88|0.84|0.84|0.75|0.96|0.86|**0.85**|\n|AutoRace (4)|0.91|0.85|0.79|0.78|0.97|0.86|**0.86**|\n|AutoRace (10)|0.86|0.82|0.84|0.77|0.98|0.89|**0.86**|\n\nThe results indicate that AutoRace is relatively robust to the sample set size. We found that it’s because:\n\n- Besides concrete errors in examples, GPT-4 can also infer some evaluation criteria from the problem domain. E.g., For math word problems, even if there is no calculation error in the examples, GPT-4 may supplement a criterion about “accurate calculation”.\n- GPT-4 has certain prior knowledge on how to evaluate a reasoning chain. Thus, even if a criterion list misses some items, GPT-4 still has a chance to correctly evaluate a reasoning chain with that type of error.\n\nAdditionally, our tests confirm that the criteria list generalizes well across different reasoning tasks (See new results in our response to reviewer bv3g). This further reduces the dependency on task-specific demonstration data.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "1. The proposed AutoRace is fully automatic and can achieve comparable performance to baselines with expert-crafted annotations.\n2. The unified formulation of LLM reasoning is a good principle for implementing evaluation systems and allows for a systematic comparison across reasoning algorithms.\n3. Extensive experiments suggest intriguing observations and provide best practices and insight for LLM reasoning. These experiments also validate the efficacy of their system.", "reasons_to_reject": "1. Novelty could be somewhat limited, but the system development is intensive and the software could be useful for the community.\n2. AutoRace relies heavily on the availability of training sets. However, constructing such a training set for a specific reasoning task is expensive and contradicts the main purpose of AutoRace, which aims to reduce human efforts. This weakens the claim of this paper.", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "kGkhzsJyDo", "reviewer": "Reviewer_bv3g", "summary": "This paper presents a new evaluation package of LLMs' complex reasoning capabilities. This paper has several contributions: (1) A new automatic evaluation metric, which first asks GPT4 to conclude common failure reasons of wrong responses on the trainined set and then ask GPT4 to evaulate models' output based on these reasons to achieve automatic evaluation. (2) A configurabale toolkit that allows user to specify their foundation model and reasoning strategy. In the end, this paper also presents a comprehensive evaluation of the peformance of llama2-70B with several reasoning strategies (i.e., CoT, RAP, and ToT)", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for acknowledging that our new evaluation reveals certain limitations of existing LLMs!\n\n**Task-specific training**\n\nThere are various open-source libraries to train reward models (RMs), e.g., Transformers, TRL, etc. Our library focuses on inference-time algorithms and is orthogonal to them. LLM Reasoners allows for flexible implementation of the reward function, including using a trained RM, and users can easily call any algorithms to search for high-reward reasoning chains. In the future, we plan to support RM training natively with our library.\n\n**70% incorrect reasoning chains**\n\nAutoRace recognizes 70% of the **false positive** reasoning chains. These are more challenging to identify than usual incorrect chains, because their errors are often subtle, and don’t affect the final answer. With traditional answer-based evaluation, **NONE** of these chains would be detected. Discovering 70% of them already led to multiple novel findings (Section 5.2)\n\nTo further clarify, AutoRace can detect **~90%** of all incorrect reasoning chains across 6 datasets (Figure 3), and we have shown it has higher accuracy and better robustness compared to various baselines with a comprehensive evaluation in Section 3.\n\n**World model**\n\nA world model $P_\\theta$ predicts state transition: $s_t \\sim P_\\theta (s_t | s_{t−1}, a_t)$. LLM Reasoners allows users to flexibly implement the world model, e.g., For RAP on the embodied task Blocksworld, the world model is implemented as a function that calls an LLM to predict the new arrangement of blocks after an action.\n\n**Generalization**\n\nWe test AutoRace with the criterion lists of GSM8k on all tasks. We also test SocREval on all tasks with its prompt for GSM8k. AutoRace shows a high degree of generalization. We found that it’s because many of the criteria discovered by AutoRace are general among different reasoning tasks.\n\n|Method|GSM8k|Arith|StrategyQA|Cosmos|Logic|Sort|Average|\n|-|-|-|-|-|-|-|-|\n|AutoRace|0.91|0.85|0.79|0.78|0.97|0.86|0.86|\n|SocREval|0.89|0.85|0.71|0.80|0.89|0.77|0.82|\n|SocREval (GSM8k)|0.89|0.84|0.63|0.74|0.85|0.81|0.79|\n|AutoRace (GSM8k)|0.91|0.83|0.73|0.69|0.99|0.89|0.84|\n\n**Error collection and example set**\n\nDue to the word limit, please refer to our response to reviewer SuhS for additional experiment results.\n\nThanks again for your thoughtful review! We will update our paper to reflect the additional results and discussion.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "1. This paper proposes a new evaluation system for LLMs' reasoning capabilities.\n2. The comprehensive evaluation reveals certain limitations of existing LLMs.", "reasons_to_reject": "The proposed method is hard to generalize. Based on the description in the paper, the proposed solution's generalization capability remains unclear. For example, the current system requires a set of questions (i.e., training data) to sample failure response for each task and then conclude the criteria list. As a result, this list might be only applicable to the current dataset. It would be great if some experiments can support the genralization capabilities of the criteria list.\nRegarding the unified library, it is unclear how to support reasoning search algorithm that requires the feedback from RMs since these models often require additional task-specific training.", "questions_to_authors": "1. In the fourth paragraph of introduction, the paper mentrions that AutoRace and detect 70% of the incorrect reasoning chains. Can you elaborate more on that? This seems to be a moderate agreement.\n2. Can you give a more clear definition of the mentioned world model? like what kind of world model can be supported by the current syste. I found it missing the first time this paper discussing the world model.\n3. Regarding the criteria list, is it generalizable to other tasks?\n4. Regarding the error collection, how to guarantee the coverage of the collected errors? Better to add an experiment to support this since this is the foundation of AutoRace.\n5. In table 5, AutoRace is annotated as fully auto. However, if my understanding is correct, it still requires the support of a set of examples to construct the criteria list. Can you elaborate more on that?", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper presents a framework and configurable library called AutoRace for evaluating the complex reasoning capabilities of LLMs. Evaluation in AutoRace relies on training GPT4 to identify common reasoning failures based on a given training set, and then using the trained GPT4 to evaluate model outputs. The framework allows evaluating models over various reasoning tasks and multiple prompting techniques (e.g., chain of thought, beam search, tree of thought, and reasoning via planning). The authors also demonstrate AutoRace through a comprehensive evaluation of LLaMA2-70B, which reveals practical insights and performance limitations of different prompting methods.

Devising more fine-grained and comprehensive evaluation protocols for reasoning chains is a challenging problem, and crucial for improving the reasoning abilities of LLMs. Being automatic, performant (on par with baselines with expert annotations), and easily configurable, AutoRace could be a useful tool for tackling these problems.

There are two concerns about this work. First, AutoRace reliance on training data could be expensive, require human annotations, and limit the ability of the system to generalize to reasoning settings/failures not observed in training. However, the authors showed compelling evidence during the rebuttal that their method can be effective even with a small demonstration set (rather than a large training set). The second concern is regarding biases and failures of the LLM evaluator, which could influence the overall evaluation. The authors have discussed this in the paper and during the rebuttal. While the current evaluator does introduce noise, it seems to outperform the baselines, and improving it could be an interesting direction for future work.

[At least one review was discounted during the decision process due to quality]
Decision: Accept