From Complex to Simple: Unraveling the Cognitive Tree for Reasoning with Small Language Models
Authors: Junbing Yan
Chengyu Wang
Taolin Zhang
Xiaofeng He
Jun Huang
Wei Zhang
Venue: EMNLP 2023 Findings (2023)
Keywords: Reasoning
Cognition
Dual Process Theory
TL;DR: An interesting paper on large language model reasoning

Abstract: Reasoning is a distinctive human capacity, enabling us to address complex problems by breaking them down into a series of manageable cognitive steps. Yet, complex logical reasoning is still cumbersome for language models. Based on the dual process theory in cognitive science, we are the first to unravel the cognitive reasoning abilities of language models. Our framework employs an iterative methodology to construct a Cognitive Tree (CogTree). The root node of this tree represents the initial query, while the leaf nodes consist of straightforward questions that can be answered directly. This construction involves two main components: the implicit extraction module (referred to as the intuitive system) and the explicit reasoning module (referred to as the reflective system). The intuitive system rapidly generates multiple responses by utilizing in-context examples, while the reflective system scores these responses using comparative learning. The scores guide the intuitive system in its subsequent generation step.Our experimental results on two popular and challenging reasoning tasks indicate that it is possible to achieve a performance level comparable to that of GPT-3.5 (with 175B parameters), using a significantly smaller language model that contains fewer parameters (<=7B) than 5% of GPT-3.5.

From Complex to Simple: Unraveling the Cognitive Tree for Reasoning with Small Language Models
Junbing Yan', Chengyu Wang', Taolin Zhang', Xiaofeng He',
Jun Huang', Wei Zhang 13+
School of Computer Science and Technology, East China Normal University
2 Allibaba Group
3 Shanghai Institute for AI Education
(junbingyan531, zhangwei thu2011 @@gmail 1. com, hexf@cs. ecnu. edu. cn {chengyu. wcy, zhangtaolin zt1, huangjun.hijeelliiie.. inaallibbb--nnc. com
Abstract
of intelligence (Ouyang et al., 2022; Wei al., 2022a; Wang et al., 2022b).
Reasoning is distinctive human capacity, en- abling us to address complex problems by breaking them down into a series of manage- able cognitive steps. Yet, complex logical rea- soning is still cumbersome for language models. Based on the dual process theory in cognitive science, we the first to unravel the cognitive reasoning abilities of language models. Our framework employs an iterative methodology to construct a Cognitive Tree (CogTree). The root node of this tree represents the initial query, while the leaf nodes consist of straightforward questions that can be answered directly. This construction involves two main components: the implicit extraction module (referred to as the intuitive system) and the explicit reason- ing module (referred as the reflective sys- tem). The intuitive system rapidly generates multiple responses by utilizing in-context ex- amples, while the reflective system scores these responses using comparative learning. The scores guide the intuitive system in subse- quent generation step. Our experimental re- sults on two popular and challenging reasoning tasks indicate that it possible achieve a per- formance level comparable that of GPT-3355 (with 175B parameters), using significantly smaller language model that contains fewer pa- rameters (<=7B) than 5 % of GPT-3.5.
However, eross the chasm between machines and humans, three main challenges still lie ahead: 1) Reasoning ability. When it comes to mathemat- ical and reasoning problems, the performance of LMs is still not satisfactory (Koyejo et al., 2022; Cobbe et al., 2021b). 2) Cognition capacity. The evaluation and decision-making process regarding the problem and its current state is of paramount importance, especially when dealing with problems that involve lengthy reasoning chains or multi-step solutions. However, current methods (Wei et al., 2022b; Yao et al., 2023) often lack comprehensive validation and tend to focus on verifying intermedi- ate results (Imani et al., 2023). 3) Efficiency. The deployment and inference costs of LLMs are rel- atively high, especially when utilizing parameter- free inference enhancement techniques (Wei et al., 2022b; Yao al., 2023). These techniques require extensive contexts and multiple steps of answer generation, leading to a further increase in infer- ence costs and time.
We suggest that valuable insights into address- ing these challenges can be derived from the cog- nitive processes of humans. In cognitive science, the dual process theory (Evans, 1984, 2003, 2008; Sloman, 1996) states that our brain initially em- ploys an implicit, unconscious, and intuitive pro- cess known as the Intuitive System, which re- trieves relevant information. This followed by an explicit, conscious, and controllable reasoning process called the Reflective System. The Intu- itive System is capable of providing resources in response to requests, while the Reflective System facilitates deeper exploration of relational infor- mation through sequential thinking in the working memory. Although slower, the Reflective System possesses unique human rationality (Baddeley, 2010). In complex reasoning tasks (including log- ical reasoning and mathematical reasoning tasks),
1 Introduction
The human brain is akin to garden, where in- stinets are seeds that sprout and grow, while rea- acts as the gardener, pruning and nurturing the plants of knowledge to bloom into the flowers of enlightenment. For machines, recently, Large Language Models (LLMs) have demonstrated their abilities to tackle diverse tasks through instanta- neous question answering, exhibiting some levels
Correspondence Wei Zhang.
Thhe source code will he released in the ELsyNLP frame- work (Wang et al., 2022a). URL: https: //gi . alibaba/EayyNLP

---

solving complex reasoning problems.
Improved Validation Capabilities. By ex- posing the model to contrastive examples of correct decisions versus incorrect or ambigu- ones, improve the model's ability make decisions (cognition ability). Addi- tionally, apart from evaluating the model's judgment of intermediate results, we have also integrated the model's assessment of the over- all correctness of the reasoning process.
Plan
Reflective
System
Plan
Scores
Intuitive
Plan
Plan
System
Generation
Efficient Framework. The combination of the Intuitive System and the Reflective Sys- tem can be applied to various reasoning tasks, i... both logical reasoning and mathematical reasoning. Notably, we are able to attain com- parable reasoning performance to models with substantially larger parameter sizes, such GPT-3.5 with 175B parameters, while utiliz- ing relatively small language models (with 1.5B and 7B parameters). This allows the trained small models to be deployed online for efficient inference.
Task
tD
Query
Logical
Reasaning
Math Problem
Figure I: A schematic illustration of the proposed frame- work named Tree. An intuitive system is employed generate candidate plans, while reflective system verifies the plausibility of each plan to guide the next generation the intuitive system. This itcrative process is repeated to create the tree structure for reasoning.
Cognitive Tree (CogTree) Framework
these systems coordinate with each other, en- gaging in iterative cycles of fast and slow think- ing (Daniel, 2017).
The reasoning ability of humans primarily arises from acquiring pertinent information from the envi- ronment and subconscious processing (Prystawski and Goodman, 2023). In our approach, in- corporate a tree structure systematically tackle reasoning problems, taking inspiration from hu- man prolemm-solving procedures. This methodol- ogy aligns with the planning processes analyzed by Newell et al., 1959; Newell and Simon, 1972. Newell and his colleagues defined problem solv- ing (Newell et al., 1959) as the exploration of a combinatorial problem space, represented as tree. In our mathematical and logical reasoning set- ting, each node n in the cognitive tree represents either a theory in logical set or the solution a sub-problem a mathematical question. An edge of the tree corresponds to the evaluation of the current node's 's state s, which can be a confidence score classification result. The problem decom- position module (i.e., the Intuitive System) receives the theory and the original problem as input, and generates the decomposition of the original prob- lem. Next, the newly generated nodes are used expand the tree, providing the reasoning module (i.c., the Reflective System) with the information that needs to be verified.
In this paper, we propose the Cognitive Tree (CogTTeee) framework to address the aforemen- tioned issues. Inspired by the dual process theory, our system consists of the Intuitive System and the Reflective System. In our implementation, the In- tuitive System and the Reflective System are both generative models, albeit with distinet objectives. The Intuitive System employs in-context examples to dissect intricate problems into sub-problems and produce responses to the query. Conversely, the Re- flective System evaluates the outcomes generated by the Intuitive System and chooses the most likely solution provide guidance for the next generation step. The aforementioned process is an iterative tree generation process, which continues until the original problem decomposed into manageable sub-problems (corresponding to nodes on the tree) that can be easily solved.
Our main contributions are as follows:
Problem Decomposition Paradigm. We pro- pose a novel framework based on human cog- nition called Cognitive Tree (CogTree) for

---

Query:
Sub- quesquut:oo: How much doee Weng eam per minute? Wong eamo $0.2 por
Sure
Weng eerns $12 an hour for babyaitting, Yesterday,, she just did 50 minutes of babysiting. How much did she eam?
Sub questio: How much does babysittnng charging
1b. per hour?
Likely
Step=1:
Answer: Babysitting cost 912 per hour.
1c. Sub-quedtion: How many hours 50 minutes equvalennt to?
Impossible
Task:
Answen 50 minutes equats 1 hours.
+xx
2a. question: did yosterday?
Answer: Weng works hour:
X Impossible
Math Problem
2b. Sub- qut-qquetoo:: How much did Weng ear??
Answer: Working 50 minutes, she earned 0.2 50 -510.
Sure
Step=2:
Sub-queetior: How minutes did babyelt
Target Answer:
20. yestenday?
Likely
Answer: 50 minutes.
Yesterday Wang serned 310.
Intuitive System
Reflective System
Query: Weng $12 hour for babysltting. Yesterday, did 50 minutes of babyaltting. How much did' she ear??
Decomposition: Sub-question: How much Weng eemn per minute? Answer: Wang earns 12/80 $0.2 per minute.
Decomposition, Generation Decompositiong
(Score, Decomposition,
Query
Validation P (Scorez Decomposition
Figure 2: An illustration of how the Intuitive System and the Reflective System work to incrementally produce a mathematical reasoning problem. At each step, the Intuitive System generates a set of decompositions based on the query. The Reflective System then scores the candidate decompositions and returns the top-ranked ones. The process terminates when the decomposition successfully matches the target answer.
The discernment capacity of the Reflective Sys- plays a pivotal role in enhancing the overall efficacy of the model (Imani et al., 2023). In par- ticular, we utilize the cross-checking technique to not only verify the precision of intermediate out- comes but also validate the accuracy of the entire reasoning process upon its completion. However, relying solely on individual decision judgments for training the model is inadequate (Imani al., 2023). To augment the model's ability to evalu- ate the state s, we propose the implementation of a comparative reinforcement approach. This ap- proach entails introducing new training objective, whereby the model tasked with maximizing the disparity in vector space between representations of correct decisions and representations of incorrect ambiguous decisions.
3 Implementation
In this section, we describe the implementations of CogTree in detail.
3.1 Intuitive System
The generative capability of the Intuitive System serves as the foundation for constructing the Cog- nitive Tree. Thus, we choose decoder-only models (e.g., GPT2-XL (Radford et al., 2019) or LLaMA- 7B (Touvron et al., 2023)) as the Intuitive System. To enhance the effectiveness of the Intuitive Sys- tem, we employ an in-context approach. Let us de- fine the Query (Q) the ultimate goal for logical reasoning problems or the question be answered in mathematical problems. In the case of logical reasoning problems, the Decomposition (D) in- volves further breaking down the goal into smaller components, where reasoning through this decom- position enables the attainment of the goal. For mathematical problems, it refers to one of the sub- problems derived from the original problem, and solving this sub-problem contributes to resolving the original problem as whole. The Decomposi- tion set (Z) represents the collection of decompo- sitions for all examples in the training set. In our approach, we retrieve K examples (e.g.. Query: Q;
In addition, efficiency pertains to the efficacy of the problem decomposition and verification pro- cess. Generating lengthy texts using model as massive 175B entails substantial time and finan- cial expenses. To tackle this issue, our method can be implemented by simply fine-tuning com- paratively smaller model (1,5B or 7B) exclusively for reasoning tasks. This enables us to deploy the model for these tasks with minimal costs.

---

Given the current state (Query: Q with De- composition: D), we utilize the Reflective System. which shares the same model architecture as the In- tuitive System, to generate a score v that validates the current state. This is represented by V(Jo, 8) ~ fa(v)s. Additionally, based on the complete rea- soning chain S {s),-.. ,8,"" )nn). we em- ploy the Reflective System to produce an overall score o, which be expressed O(ʃe, S) fo(o]S).
Step=1:
Query;; earth rotating on its axis causes cycles of day and night on earth
Decomposition,; earth a planet that rotates on tilted + [a planet rotating causes cycles day and night on that planet
Step=2:
Queryz: earth is planet that rotates its tilted axis Decompositiong [ the earth rotates on its tilted axis [earth a kind of planet]
Figure Example Query and Decomposition for logical reasoning.
To generate the scores v and o we utilize the model to produce a classification result. Since the answers generated by the Intuitive System can sometimes be misleading and cannot be accurately assessed this stage, we adopt prompt- based approach and treat it as classification problem. where the model outputs one of three categories: sure, impossible, or likely. The likely response sig- nifies that the generated answer is plausible but requires further verification.
Step=1:
Query,: Natalia sold clips to of her friends in April, and then she sold half as many clips in May. How many clips did Natalia
sell altogether in April and May?
Decomposition; How many cllps did Natalia sell in May? Natalia sold 48/2 24 clips May:
Step-2:
her friands in April, and then she soid half as many clips in May, How many clips did Natalia sell altogether in April and May? Decomposition, How many clipe did Natalla sell in May? Natalla sold 48/2 = 24 clips in May. Decomposition How many clips did Natalla sell altogether April and May? Natalia sold 48+24 = 72 clips altogether in April and May.
Query:: Natalia sold clips
3.3 Training
Figure 4: Example of Query and Decomposition for mathematical problems.
Intuitive System. Supervised Fine-tuning (SFT) has demonstrated its effectiveness in aligning with human intentions (Ouyang et al., 2022). In our approach, the Intuitive System is designed to de- compose the queries (i.e., complex problems) into sub-problems by leveraging in-context examples. Since we employ generative models as our Intuitive System, the loss calculation is only necessary for the generative text (without the given context) dur- ing auto-regressive computation. Given a sample of tokens with a length of N denoted as X, where X = {z1.-..- Li, ) Furthermore, we de- fine the sequence length of in-context examples as M. We use standard language modeling objective to maximize the following likelihood function:
Decomposition: D) from the inference decomposi- tion set (Z), which are then utilized the context for the model's 's input. Detailed examples are shown in Figure 3 and Figure 4.
Then, the output can be generated as ~ fo( 21...). Here, z represents the K exam- ples recalled from the decompositions set Z. where Z = (z1,... =1.)- In practice, we use the Intuitive System to obtain the representation of the current query (final transformer block's 's ac- tivation) and calculate the cosine similarity with the representations of other queries in Z. We then retrieve the K most similar queries from the set. Moreover, [v] ~ fe(ulæ, x1) is sampled as a continuous language sequence.
N
LIS Σ
log P(a./a1, "000),
M
3.2 Reflective System
Reflective System. The acquisition of the Reflec- tive System can be achieved through the same train- ing approach as the Intuitive System, which in- volves utilizing positive and negative samples to obtain classification results from the model. Since the Reflective System is primarily focused on gen- erating judgments for given state s, the loss func- tion can be defined as follows:
The Reflective System differs from the Intuitive System in terms of its approach of generating in- sights. While the Intuitive System relies quick intuition, the Reflective System's 's role to evaluate the decompositions to determine their acceptability, In practice, we employ two methods to verify the results: the verification of intermediate processes and the verification of the entire reasoning chain.
In the experiment, we set K = 5.
LRS = log P(u|s;
(2)

---

Dataset
Input
Output
EB
hypothesis that needs to be proven and of theory. (llypo: Phobos is kind of moon. Theory: [Mars is a kind of planet; Mars.J)
Yes No to indicate whether the hypothesis be proven based the theory. (Yes)
orbit planets; Phobos orbits
GSM8K
A math word problem (Natalia sold clips to 48 of her friends in April, and then she sold half as many clips in May. How many clips did Natalia sell altogether in April and May?)
number denoting the solution to the mathematical problem. (72)
Table I: Task overview. Examples of input and output are printed blue.
Dataset
Split
Samples
Max Steps
Avg Steps
{u/, U/.... -.. 2 J. By maximizing the distance between v' and the correct answers
EB
Train
1313
17
3.2
Dev
187
3.2
hance the learning process. Let get, be a match- ing function between negative sample of and the positive sample v. The loss function for contrastive learning can be expressed as follows:
Test
340
3.3
GSM8K
Train 6726
3.6
Dev 747
8
3.5
Test 1319
11
3.7
exp(f(u, v))
Table 2: Data statistics of EB and GSM8K.
Lcc = exp(f(u,))) Every exp(f v'))
(3)
Hence, the total loss function for the Reflective System is given by:
However, the effectiveness of this training method is found to be unsatisfactory. In cog- nitive theory, human decision-making behavior arises from the comparative analysis of various op- tions (Festinger, 1957). Drawing inspiration from the cognitive theory, we adopt a contrastive learn- ing approach to enhance the model's ability to dis- tinguish between different states. The fundamental concept of contrastive learning is to learn represen- tations of positive and negative samples by max- imizing their distance in the sample space (Chen al., 2020). Consequently, the selection of nega- tive samples plays critical role in determining the effectiveness of contrastive learning.
Liotal - LRs + A1- Lec
(4)
Here, À the hyper-parameter We conduct ex- periments on and choose = 0.5 as the best setting."
Experiments
We perform an extensive evaluation of our method utilizing two well-cstablished benchmark datasets: the Entailment Bank (EB) (Dalvi et al., 2021) and GSM8K (Cobbe et al., 2021a). EB consists of human-annotater tuples containing information about theories, provable goals, and correspond- ing reasoning paths. GSM8K, the other hand, presents challenging arithmetic reasoning task that language models frequently find difficult tackle (Hendrycks et al., 2021; Cobbe et al., 2021b). Examples of these two datasets are in Table The dataset statistics are shown in Table 2.
For logic reasoning datasets, one approach to generate more challenging negative examples is to replace one of the theories in decomposition with another theory from the current theory set. This negative example is more challenging for the model to distinguish because the theories within the same theory set are more similar.
For mathematical problems, since our exper- imental dataset GSM8K (Cobbe et al., 202 only provides the correct answer itself, it does not offer incorrect solutions. We the dataset PRMS00K (Lightman al., 2023) enhance the learning process, where there are ambigu- ous responses 5' = (s/,,... ,/ ...... ( (seem- ingly correct but actually incorrect). The judg- ment generated by Reflective System V"
Experimental Setup
In our experiments, we use GPT2-XL (Radford et al., 2019) and LLaMA-7B (?) from the Hugging- face transformers (Wolf et al., 2020) library the underlying models for the Intuitive System and the Reflective System.
'In the experiment, we use cosine similarity as g(v', For specific details, please refer to the Section 4.7.

---

EB
GSM8K
Model
#Params.
Accuracy (%)
A (%)
Accuracy (%)
A (%)
Comparative Systems
GPT:3.5 Sonee-davinc--022
175B
80.76
16.17
Standard prompt
175B
84.23
+3.47
17.03
+0.86
Chain-of thought prompt
175B
92.45
+11.69
60.27
+44.10
Tree-of-thought prompt
175B
93.31
+12.55
61.39
+45.22
Our Models Tree)
GPT2-XL (Intutvee System only)
1.5B
82.37
23.53
GPT2-XL Reflective System)
1.5B
92.63
+10.26
35.84
+12.31
-LLaMA (as Reflective System)
7B
93.16
+10.79
34.68
+11.15
I.LaMA (Intuitive System only)
7B
86.14
43.52
GPT2-XL (us Reflective System)
1.5B
93.25
7.11
47.80
+4.28
I...aMA (as Reflective System)
7B
94.25
+8.11
61.28
+17.76
Table Overall test set performance in terms of accuracy and relative improvement.
During training, we use the Adam optimizer with 81 = 0.9, f2 0.999,
provable and non-provable goals. To accomplish this, we assign a non-provable goal to each devel- opment and testing theories by selecting it from other (theory, goal, reasoning path) samples. The selection adversarial: We input all the goals in the set into our pre-trained model separately, ob- taining the last output of the last transformer block as the representation of each goal. We proceed by computing the cosine similarity between all non- provable goals and the provable goal. Based on this computation, we identify the hard negative example with the highest similarity. For given theory T and query Q, allow the system generate reasoning path S and obtain the proof value o fo(o) for that path. Given the choices Latrel/iiik//mpsssbbbe"" we say "Q is provable" when the value o is "sure" and not provable other- wise.
1e 8. We use the learning rate = le 1 for both Systems. We batch size of 4 and set large epoch number do early
(i.e.. 100) and use the validation stopping. In practice, the best epoch is often within 50. During the inference stage, in each step, we use the Intuitive System to generate the top_bes 3ppmeam=3 answers and then let the Reflective System select the most probable answer to continue generating for the next step. We add an "end" marker. The inference process stops when the Intuitive System generates the "end" marker or when the maximum number of inferences, which is 20, is reached. For each Query, we perform complete reasoning pro- cess.5
Following Zhou et al., 2022, we use code- davinci-002" (rode-davinci-000 is constructed on the foundation of the GPT-3.5 architecture) for comparative experiment due to its strong reason- ing abilitiy and employ various prompt strate- gies conduct our experiments on GPT2-XL and LLaMA-7B. For each example, we sample Stan- dard prompting (detailed cases to described in Section 4.2) and Chain-of-the thhthuggt (CoT) prompt- ing for 100 times for average performance. For Tree-of-thought (ToT), at each step we generate 5 candidate answers and sample values times for each example.
Baselines. Vanilla: The raw input to the model is as follows: Query: Q; Theory Set: T, followed by question: Based on the theory, can the goal be approved? Please answer with yes dard prompt: We use an input-output (IO) prompt with 5 in-context examples (e.g. Query: Q: Theory Set: T: Answer: A.). Chain-of-though prompt: For chain-of- thought (CoT) prompting, we aug- ment each input-output pair using examples with complete reasoning chain (e.g. Query: Q: The- ory Set: T: Reasoning Chain: S; Answer: A.). Tree-of-thought prompt: In each step, provide the model with the theory set and ask the model to select two theories from the set generate a new inference, which added the theory set while removing the two selected theories. Each step generates five candidates, and the model gen-
Stan-
4.2 Results on Entailment Bank
On EB, followed by Zhao et al., 2023, we assess the capabilities of systems in distinguishing between
Detaaied examples are shown Figure and Figure 'https:/ /ttp::////penaiao/a/ com/

---

Main Results. Experimental results are shown in Table 3. It is evident that the direct question- answering accuracy of GPT-3.5 is merely 16%. answer each sub-question sequentially, ultimately deriving the final answer.
Eyran Batte (N)
Directly input the question and let the model to answer (e.g. Query: Q). Standard
Baselines. Vanilla:
prompt: We use an input-output (IO) prompt with
5 in-context examples (e.g. Query: 2; Answer: A). the step-by-step solution of mathematical problems as enhanced input-output pair (e.g. Query: Q; Rea- soning Chain: S; Answer: A). Tree-of-though prompt: We adopt the methodology described in ToT (Yao et al., 2023). Our implementation in- volves the incremental generation of the answer, with the model producing one step at time. We sample the results five times for each step and em- ploy the model assess the generated outcomes until the final answer obtained?.
Figure 5: Samples failed each step on EB (left) and
Chain-of-thouge prompt: For CoT,
GSM8K (right).
erates subsequent inferences based on the highest likelihood until the set ultimately contains only one inference, which is compared with the goal to determine consistency (e.g., theory, + theory, -> inference (theory set without theory,&:))..
Main results. Table presents the classification ac- curacy on EB. The results demonstrate that GPT2- XL (1.5B), trained exclusively on in-context exam- ples, outperforms GPT-3.5 (175B) despite having fewer than 1% of the model's parameters. By in- corporating CoT and ToT augmentation methods, the accuracy of GPT-3.5 is substantially enhanced, reaching 92-93%. Furthermore, when our approach is combined with the Reflective System for result verification, even higher performance achieved (94% by LLaMA-7B), surpassing the prompt aug- mentation method employed by GPT-3.5.
The traditional input-output approach did not im- prove its effectiveness. In contrast, CoT and ToT demonstrate significant enhancement in solving mathematical problems, with an improvement approximately 44%. This indicates the crucial role of providing the model with example reasoning chains for tasks involving multi-step inference. Our SFT-improved GPT2 achieves only 23.5% accu- racy, which may be attributed to the scale low (Ka- plan et al., 2020) caused by model parameters. The performance of our LLaMA-7B and GPT-3.5 mod- els is nearly indistinguishable, suggesting that fine- tuning small models using our provided method can approach the performance of larger models. Notably, the inclusion of the Reflective System on GSM8K leads to a greater overall improvement compared to EB, indicating that using the Reflec- tive System can yield better results, particularly in more complex problems.
Error Analysis. Although our model has achieved satisfactory results, it still exhibits deficiencies in certain cases. We have conducted an examination of instances where the model's inference has failed (Detailed examples are shown Figure 5). Specif- ically, we observed a decline in the model's accu- racy when the length of the inference chain exceeds 10 steps. Our model struggles to determine the ap- propriate decomposition of the goal in such cases, This limitation may arise from the excessively long and divergent nature of the chain required to reach the goal, which surpasses the model's current ca- pacity for abstraction in this regard. It is worth noting that even for humans, this task can be com- plex, often requiring multiple attempts to arrive at the final inference chain.
Error Analysis. We have found that the examples where the model fails to answer can be divided into two categories. The first category is the failure in decomposing the question into subproblems (De- tailed examples are shown in Figure 5), which is consistent with the findings of Zhou al. (2022). Such failures can be resolved through manual de- composition. The second category of failure is
4.3 Results GSM8K
On GSM8K, we employ in-context examples to enable the model to generate sub-questions for conduct
given problem. In the implementation, five sampling iterations each decomposition step and choose the one with the highest probability for generating the next step. Once all the sub-questions have been generated, we proceed to have the model
iI is worth noting that our tree construction method differs significantly from ToT (Yao et al., 2023). ToT employs a bottom-up approach, whereas we utilize explicit questioning to break down the problem for the model and address it in a top-down fashion, step by step.

---

Model
EB
GSM8K
4.5 Compared with Other Finetune SOTAs
GPT-XL
In pursuit of fairness, we conducted a comparison of state-of-the-ar methods that had been fine-tuned on identical datasets, in contrast to our prior eval- uation of methods relying on GPT-3.5, which is parameter-free.
SSpecialize
81.54%
21.43%
+DecomP
83.27%
24.35%
Self-Askk
82.69%
25.46%
+CogTree
93.16%
34.68% %
I.L.MA-7B
DecomP (Khot et al., 2023) solves complex tasks by decomposing them (via prompting) into simpler sub-tasks. Specialize (Fu et al., 2023) proposes small model specialization to enhance performance by focusing model capacity on specific target task. Self-Ask (Press et al., 2022) explicitly asks the model itself (and then answers) follow-up questions before answering the initial question.
Sppeiillize
84.32%
34.21%
DDecomP
39.75% 82.43%
SSlf-Askk
38.35% 94.25%
83.98%
+CogTree
61.28% %
Table 4: Performance metrics for different methods with EB and GSM8K.
Model
EB
GSM8K
It can be observed in Table 4, when compared with the finetune-based methods, Cogtree still achieves state-of-the-al results. This is attributed to not only decomposing the problem but also in- corporating result validation in subsequent steps.
GPT-XL
92.63%
35.84%
decomposition
62.38%
18.94%
LLaMA-7B
93.25% 69.79%
61.28%
decomposition
27.16%
Table 5: Ablation study in terms of Fl.
4.6 Ablation Study
We conducted further experiments demonstrate the effectiveness of decomposing step by step. "w/ decomposition" indicates that we used the method from our paper to decompose and sequentially an- swer the original problem. On the other hand, "w/o decomposition" means that we did not use the in- termediate problem decomposition and directly an- swered the original problem, relying on System to generate the answer.
when the model provides inaccurate answers to the subproblems. These failures are frequently ob- served in GPT2-XL and are the main reason for the unsatisfactory performance of GPT2, One possible reason for these failures is the inadequacy of the model's parameter size, which hinders its ability to acquire fundamental mathematical capabilities.
4.4 Backbone Modifications
As we can see the Table 5, the accuracy of di- rectly answering the original problem is low, espe- cially when the original problem is complex. This is also in line with human cognition. When solving math problems, we also solve intermediate prob- lems first and then obtain the final answer, which improves our accuracy.
We conduct experiments employing different back- bones for the Intuitive System and the Reflective System. The results presented in Table 3 demon- strate that when GPT2-XL is utilized as the In- tuitive System and LLaMA-7B as the Reflective System, there is observed improvement in over- all performance the EB dataset, compared to using GPT2-XL the Reflective System. How- ever, when a more powerful model is employed as the Reflective System on the GSM8K dataset, there is no noticeable performance enhancement. This finding suggests that the Intuitive System re- stricts the system's 's performance on the GSM8K dataset. Conversely, when LLaMA-7B serves as the Intuitive System and GPT2-XL as the Reflec- tive System, the performance improvement on the GSM8K dataset, in comparison using LLaMA- 7B as the Reflective System, not substantial. This indicates that in this particular case, the Reflective System limits the overall system's performance.
4.7 Hyper-parameter Analysis
We vary one hyper-parameter with others fixed. From Figure 6, as À increases, the performance first increases and then drops, and it can achieve the best result when À = 0.5.
Related Work
Multi-step Reasoning. Reasoning has long been key focus in natural language processing research. Initially, most studies concentrated on basic tasks like single-sentence language inference (Zamansky et al., 2006; MacCartney and Manning, 2009; An- geli et al., 2016: Hu et al., 2020; Chen et al., 2021)

---

problems into sub-problems, and the edges rep- resent judgments regarding the correctness of the decomposition. Based on the implementation of our approach over GPT2 and LLaMA, we have achieved results comparable to GPT-3.5 on EB and GSM8K datasets, indicating the effectiveness of our framework.
LLaMA
60-
95
Accuracy (%)
Accurat
94
50-
GPT2-XL
0.3
0.5
0.7
30
0.1
0.3
0.9
Limitations
Figure 6: The impact of the hyper-parameter À on EB (left) and GSM8K (right).
Due to the limitation of computational resources, we did not test our method on larger scale models. As the model size increases, using our approach may lead to further improvement in the accuracy of answers these questions. Another direction worth exploring is diversifying the validation meth- ods for the Reflective System, such as using multi- verification to compare the generated results and select the optimal answer.
and commonsense inference (Rajani et al., 2019;
Latcinnik and Berant, 2020; Shwartz et al., 2020) in single step. Lately, there has been surge in research interest regarding multi-step reasoning and mathematical problem solving. The search space for correct reasoning path extremely vast and complex. Previous approaches (Bostrom et al., 2022: Creswell et al., 2022: Zhao et al., 2023) pre- dominantly emphasized a bottom-up reasoning ap- proach, with strong focus on system design. In contrast, our approach to constructing the cognitive tree adopts a top-down methodology, reducing the burden during the era of generative models. This top-down approach offers greater flexibility for ap- plication across models of varying scales.
Acknowledgements
This work was supported in part by National Natu- ral Science Foundation of China under Grant (No. 62072182, No. 92270119), the Fundamental Re- search Funds for the Central Universities, and by Alibaba Group through Alibaba Research Intern Program.
LLM as Evaluation. The utilization of Language Models (LLMs) to evaluate the validity of their own predictions is gaining significance as a proce- dure in problem-solving. The introduction of the self-reflection mechanism by Shinn et al., 2023; Maduan al., 2023; Paul et al., 2023 involves LMs providing feedback their generated candidates. Tree of Thought (Yao al., 2023) and our approach share a common utilization of tree-based struc- ture for problem-solving However, ToT primarily concentrates on tree construction and limited self- validation of intermediate results. According to the dual process theory, which suggests that validation requires deeper levels of thinking, our approach incorporates contrastive learning method hance the model's ability to distinguish accurate results and facilitate comprehensive global valida- tion of the generated outcomes.
References
Gabor Angeli, Neha Nayak, and Christopher D. Man- ning. 2016. Combining natural logic and shallow reasoning for question answering. of the 54th Annual Meeting of the Association for Computational Linguistics (Volume I: Long Papers). pages 442-452, Berlin, Germany. Association for Computational Linguistics.
Proceedings
Alan Baddeley. 2010. Working memory. Scholarpedia, 5(2):3015.
Kaj Bostrom, Zayne Sprague, Swarat Chaudhuri, and Greg Durrett. 2022. Natural language deduction through search over statement compositions. In Find- ings of the Association for Computational Linguistics: EMNLP 20122, Abu Dhabi, United Arab Emirates, De- cember 7-11, 2022, pages 4871-4883 Association for Computational Linguistics.
6 Conclusion
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey E. Hinton. 2020. A simple framework for contrastive learning visual representations. In Pro- ceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Vir- tual Event, volume 119 of Proceedings of Machine Learning Research, pages 1597-1607. PMLR.
In this paper. we proposed new framework named CogTree address complex logical reasoning and mathematical problems. The process of reason- ing involves constructing a Cognitive Tree, where the nodes represent the decomposition of complex

---

Zeming Chen, Qiyue Gao, and Lawrence Moss. 2021. NeuralLog: Natural language inference with joint neural and logical reasoning. In Proceedings of "SEM 2021: The Tenth Joint Conference on Lexical and Compulational Semanticx, pages 78-88, Online. Association for Computational Linguistics.
Hai Hu, Qi Chen, Kyle Richardson, Atreyee Mukher- jee, Lawrence Moss, and Sandra Kuebler. 2020. Monalog: a lightweight system for natural language inference based on monotonicity. In Proceedings of the Society for Computation in Linguistics 2020, pages 334-344, New York, New York, Association for Computational Linguisties.
Karl Cobbe, Vineet Kosaraju. Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, Christopher Hesse, and John Schulman. 2021a. Training verifiers to solve math word prob- lems. CoRR, 10./2110.11 14.6.
Shima Imani, Liang Du, and Harsh Shrivastava. 2023. Mathprompter: Mathematical reasoning using large language models. CoRR, abs/2303.05398.
Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B. Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. 2020. Scaling laws for neural language models. CoRR, abs/2001 1.0361..
Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Jacob Hilton, Retichiro Nakano, Christopher Hesse, and John Schulman. 2021b. Training verifiers to solve math word problems. CoRR, abs/21 10.1116.
Tushar Khot, Harsh Trivedi, Matthew Finlayson, Yao Fu, Kyle Richardson, Peter Clark, and Ashish Sab- harwal, 2023. Decomposed prompting: A modular approach for solving complex tasks. In The Eleventh International Conference on Learning Representa- rions, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net.
Antonia Creswell, Murray Shanahan, and Irina Higgins. 2022. relection-inferencee Exploiting large language models for interpretable logical reasoning. CoRR, abs/2205.09712.
Bhavana Dalvi, Peter Jansen, Oyvind Tafjord, Zhengnan Xie, Hannah Smith, Leighanna Pipatanangkura and Peter Clark, 2021. Explaining answers with entail- ment trees. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Process- ing, pages 7358-7370, Online and Punta Cana, Do- minican Republic. Association for Computational Linguistics.
Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Bel- grave, K. Cho, and A. Oh, editors. 2022. Advances in Neural Information.
Veronica Latcinnik and Jonathan Berant. 2020. Explain- ing question answering models through text genera- tion. arXiv preprint arXiv:2004.05569.
Kahneman Daniel. 2017. Thinking, fast and slow.
Hunter Lightman, Vineet Kosaraju, Yura Burda, Har- rison Edwards, Bowen Baker, Teddy Lee, Jan Leike, John Schulman, Tlya Sutskever, and Karl Cobbe. 2023. Let's verify step by step. CoRR, abs/2305.20050.
Jonathan Evans. 2008. Dual- pnol-processing accounts of reasoming, judgment, and social cognition. Anmual review of psychology, 59:255-78.
Jonathan St B. T. Evans. 1984. Heuristic and analytic processes in reasoning*. British Journal of Psychol- ogy, 75(4):451-44
Bill MacCartney and Christopher D. Manning. 2009. An extended model of natural logic. In Proceed- ings of the Eight International Conference on Com- putational Semantics, pages 140-156, Tilburg, The Netherlands. Association for Computational Linguis- tics.
Jonathan St.BTT. Evans. 2003. In two minds: dual- process accounts of reasoning. Trends in Cognitive Sciences, (10))454-450
Leon Festinger. 1957, Cognitive Dissonance.
Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao, Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang. Sean Welleck, Bodhisattwa Prasad Majumder, Shashank Gupta, Amir Yazdanbakhsh, and Peter Clark. 2023. Self-refine: Iterative refinement with self-feedback. CoRR, abs/2303.1765.
Yao Fu, Hao Peng. Litu Ou, Ashish Sabharwal, and Tushar Khot. 2023. Specializing smaller language models towards multi-step reasoning. In Interna- tional Conference on Machine Learning, ICML 2023. 23-29 July 2023, Honolulu, Hawaii USA, volume 202 of Proceedings of Machine Learning Research, pages 10421-1044 10430. PMLR.
A. Newell and H.A. Simon. 1972. Human problem solving. UNESCO (Paris).
Dan Hendrycks, Collin Burns, Saurav Kadavath, Akul Arora, Steven Basart, Eric Tang, Dawn Song, and Ja- cob Steinhardt. 2021. Measuring mathematical prob- lem solving with the MATH dataset. In Proceedings of the Neural Information Processing Systems Track on Datasets and Benchmarks 1, NeurIPS Datasets and Benchmarks 2021, December 2021, virtual.
Allen Newell, J. C. Shaw, and Herbert A. Simon. 1959. Report on a general problem-solving program. In Information Processing, Proceedings of the 1st In- ternational Conference on Information Processing, UNESCO, Paris 15-20 June 1959, pages 256-264. UNESCO (Paris).

---

Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll L. Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, John Schulman, Jacob Hilton, Fraser Kelton, Luke Miller, Maddie Simens, Amanda Askell, Peter Welin- der, Paul F. Christiano, Jan Leike, and Ryan Lowe. 2022. Training language models follow instruc- tions with human feedback. In NeurlPS.
Yizhong Wang. Yeganch Kordi, Swaroop Mishra, Al- isa Liu, Noah A. Smith, Daniel Khashabi, and Han- nanch Hajishirzi. 2022b. Self-instruct: Aligning lan- guage model with self generated instructions. CoRR, abs/2212.10550
Jason Wei, Maarten Bosma, Vincent Y. Zhao, Kelvin Guu, Adams Wei Yu, Brian Lester, Nan Du, An- drew M. Dai, and Quoc V. Le. 2022a. Finetuned language models are zero-shot learners. In The Tenth International Conference on Learning Representa- rions, ICLR 2022, Virtual Event, April 25-29, 2022. OpenReview.net.
Debjit Paul, Mete Ismayilzada, Maxime Peyrard, Beat- riz Borges, Antoine Bosselut, Robert West, and Boi Faltings. 2023. REFINER: reasoning feedhack in- termediate representations. CoRR, abs/2304.01904,
Ofir Press, Muru Zhang. Sewon Min, Ludwig Schmidt, Noah A. Smith, and Mike Lewis. 2022. Measuring and narrowing the compositionality gap language models. CoRR, abs/2210.03350.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Brian Ichter, Fei Xia, Ed H. Chi, Quoe V. Le, and Denny Zhou. 2022b. Chain-of-thougge prompt- ing elicits reasoning in large language models. In NeurIPS.
Ben Prystawski and Noah D. Goodman. 2023. Why think step-by-step? reasoning emerges from the lo- cality of experience. CoRR, abs/2304.03843.
Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pier- ric 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. 2020. Transformers: State-of- of--he--rttttttt natural language processing. In Pro- ceedings of the 2020 Conference on Empirical Meth- ods in Natural Language Processing: System Demon- strations, EMNLP 2020- Demos, Online, November 16-20, 2020, pages 38-45. Association for Computa- tional Linguistics.
Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al. 2019. Language models are unsupervised multitask learners. OpenAl blog. 1(8):9
Nazneen Fatema Rajani, Bryan McCann, Caiming Xiong, and Richard Socher. 2019. Explain your- self! leveraging language models for commonsense reasoning. In Proceedings of the 57th Annual Meet- ing of the Association for Computational Linguistics, pages 9932-4942, Florence, Italy. Association for Computational Linguistics.
Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L. Griffiths, Yuan Cao. and Karthik Narasimhan. 2023. Tree of thoughts: Deliberate problem solving with large language models. CORR. 0ls/2305.10601
Noah Shinn, Beck Labash, and Ashwin Gopinath. 2023. Reflexion: an autonomous agent with dynamic mem- ory and self-reflection. CoRR, abs/2303.11366
Vered Shwartz, Peter West, Ronan Le Bras, Chandra Bhagavatula, and Yejin Choi. 2020. Unsupervised commonsense question answering with self-talk. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 4615-4629, Online. Association for Computa- tional Linguistics.
Anna Zamansky, Nissim Francez, and Yoad Winter, 2006. A 'natural logic' inference system using the lambek calculus. Journal of Logic, Language and Information.
Hongyu Zhao, Kangrui Wang, Mo Yu, and Hongyuan Mei. 2023, Explicit planning helps language models in logical reasoning. CoRR, 13711414.1174
Steven Sloman. 1996. The empirical case for two sys- tems of reasoning. Psychological Bulletin, 119:3-.
Denny Zhou, Nathanael Schärli, Le Hou, Jason Wei, Nathan Scales, Xuezhi Wang. Dale Schuurmans, Olivier Bousquet, Quee Le, and Ed H. Chi. 2022. Least-to-most prompting enables complex reasoning in large language models. CoRR, abx/2205. 10625.
Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anna Lachaux. Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, Aurélien Rodriguez, Armand Joulin, Edouard Grave, and Guillaume Lample. 2023. Llama: Open and efficient foundation language models. CoRR, abs/2302. 13971.
A Appendix
Below we present some successful and failed cases of Cog for analysis.
Chengyu Wang, Minghui Qiu, Taolin Zhang, Tingting Liu, Lei Li, Jianing Wang, Ming Wang, Jun Huang. and Wei Lin. 2022a. Easynlp: easy-to-use toolkit for natural language processing. In Proceedings of the The 2022 Conference Empir- ical Methods in Natural Language Processing, pages 22-29. Association for Computational Linguistics.
comprehensive and

---

Step=1:
Query; the sun will be the star that appears the brightest to the earth
Decomposition,.il [ as the stars become closer, the light of the stars will appear brighter] the sun is the star that is closest to earth
Decomposition, 2: [ the stars become closer, the light of the stars will appear brighter] ] source of something produces that something]
Decomposition,.i a star produces light sun the star that closest earth
Step=2:
Querys: as the stars become closer, the light of the stars will appear brighter
Decomposition... stars are source of light + as a source of light becomes closer, the light will appear brighter
Decomposition z: [ source of something produces that something [stars are source of light Decomposition si star produces light source of something produces that something ]
Step=3:
Query;: source of light
Decomposition..: s: [a star produces light ] source something produces that something Decomposition.. source of something produces that something [a star produces light Decompositions.: (the sun is a star + star produces light]
Figure 7: successful case EB total steps. Green represents answers judged as "sure" the Reflective System. Gray represents answers judged "likely" by the Reflective System, and red represents answers judged as "impossible" by the Reflective System.
Step=1:
Query;: Natalia sold clips to 48 of her friends in April, and then she sold half as many clips in May. How many clips did Natalia sell altogether in April and May?
Decomposition,,; How many clips did Natalia sell May? Natalia sold 48/2 24 clips May.
Decomposition,, How many clips did Natalia sell April? Natalia sold 48 clips in April.
Decomposition,," How many clips did Natalia sell May? Natalia sold 48 clips May.
Step=2:
Querys: : Natalia sold clips to 48 of her friends in April, and then she sold half as many clips in May. How many clips did Natalia sell altogether in April and May? Decomposition; How many clips did Natalia sell in May? Natalia sold 48/2 24 clips in May.
D How many clips did Natalia sell altogether in April and May? Natalia sold 48+24 72 clips altogether in April and May.
Decomposition How many clips did Natalia sell altogether in April and May? Natalia sold 48+48 96 in April and May.
Decomposition.s! How many clips Natalia sell altogether April and May? Natalia sold April May.
Figure A successful case GSM8K steps. Green represents answers judged as "sure" by Reflective System. Gray represents answers judged "likely" by the Reflective System, and red represents answers judged "impossible" by the Reflective System.

---

Step=1: Query;; two tectonic plates pushing toward each other changes the earth's crust material into metamorphic rock
Decomposition, exposure to intense heat and pressure changes the material of earth's s crust into metamorphic rock] [two tectonic plates pushing toward each other cause intense heat and pressure in the earth's crust]
Step=2:
Queryzi exposure intense heat and pressure changes the material of earth's 's crust into metamorphic rock Decompositiong: Exposure extreme heat and pressure can transform igneous into metamorphic rock the continental crust mainly is made granite
Step=3:
Querys: exposure to extreme heat and pressure changes the material of earth's crust into metamorphic rock Decompositiong: exposure to extreme heat and pressure changes the material of earth's 's crust + the crust is made of different kinds of crust]
Step=4:
Query,: exposure to extreme heat and pressure changes the material of earth's 's crust Decomposition,! exposure extreme heat and pressure changes igneous rock into metamorphic rock [rock is kind material)
Step=5:
Querys: exposure to extreme heat pressure changes igneous rock metamorphic rock Decomposition:: two tectonic plates pushing toward each other cause intense heat and pressure in earth's crust rock is kind of material)
Figure 9: A failed case in EB of II total steps. Our system stops generating after Step 5.
Step=1:
Query: John drives for hours speed 60 mph and then turns around because he realizes he forgot something very important at home. He tries to get home in hours but spends the first 2 hours standstill traffic. He spends the next half-hour driving at a speed of 30mph, before being able to drive the remaining time of the hours going at 80 mph. How far is he from home at the end of those 4 hours?
Decomposition; How far was John during the first hours of driving?
John drives at speed of 60 mph for 3 hours, the distance covered calculated follows: Distance 60 180 miles
Step=2:
did John driving John drives at speed of 30 mph for half hour, so distance covered calculated as follows: Distance 0.5
Decompositiong:
half hour?
miles
Step=3:
Decompositiong: How long is the distance covered during the remaining time of 4 hours?
John spends 2 hours in standstill traffic, so he has 4 hours hours 2 hours remaining to drive at speed of 80 mph. Distance 80 2 = 160 miles
Step=4:
Decomposition, How long the total distance covered during the hours? To find the total distance covered, we add up distances calculated the previous steps: Total Distance 180 + 15 160 355 miles
Figure 10: A failed case GSM8K total steps. Our system stops generating after Step


Reviews:
[{"review_id": "La4cpiOiUn", "reviewer": "Reviewer_gKx3", "summary": "", "questions": "1. Most training datasets do not contain intermediate subquestions and answers. Is CogTree invalid in such situations? \n2. CogTree is finetuned on the same distribution as the test set (EB and GSM8K), is it unfair to compare with LLMs which are few-shots? Expected to see the experiments compared with other finetune SOTAs. \n3. Why decomposing step by step? Does the experiment prove the effectiveness of decomposing?", "limitations": "", "rating": 2, "confidence": 4, "soundness": 2, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "### Q1: Most training datasets do not contain intermediate subquestions and answers. Is CogTree invalid in such situations?\nA significant distinction of our approach from other decomposition methods lies in the fact that, while previous methods such as Least-to-Most prompting and DecompT5 focus on how to break down problems and utilize intermediate results, our approach not only generates multiple decomposition hypotheses for the current problem but also validates the intermediate results of the decomposition. This enhances the accuracy of multi-step reasoning leading to the final result. In our experiments, we adhere to the established settings from previous papers. In fact, our approach follows the standard settings of LLM reasoning, including Chain-of-Thought (CoT), Least-to-Most Prompting, and Tree-of-Thought (ToT). These papers on LLM reasoning still rely on intermediate-step results for inference to arrive at the final answer. While a method that can directly solve complex reasoning problems without intermediate steps is attractive, it remains challenging for the current LLMs. Consider the way humans solve problems: when tackling a complex problem, we break it down into smaller components to solve the original problem. Without intermediate steps, our error rate would also be quite high. The essence of this problem is whether our model can generalize to a dataset without intermediate problem decomposition through training on datasets that involve intermediate steps, and correctly decompose and answer them. This is a direction we can improve in the future. However, currently, we can provide a semi-automatic approach: for a new class of data or problems, we can manually generate subproblems and their answers, use this content as context input to LLM or similar models like ChatGPT, and let it generate the subsequent steps as training data for the smaller model.\n\n### Q2: CogTree is finetuned on the same distribution as the test set (EB and GSM8K), is it unfair to compare with LLMs which are few-shots? Expected to see the experiments compared with other finetune SOTAs.\nWe further compared the performance of our method with other state-of-the-art methods fine-tuned on the datasets, including:\n\n- **DecomP**: Decomposed Prompting: A Modular Approach for Solving Complex Tasks\n- **Specialize**: Specializing Smaller Language Models towards Multi-Step Reasoning\n- **Self-Ask**: Measuring and Narrowing the Compositionality Gap in Language Models\n\n| Model        | EB    | GSM8K |\n|--------------|-------|-------|\n| GPT2-XL(1.5B) |       |       |\n| +Specialize  | 81.54 | 21.43 |\n| +DecomP      | 83.27 | 24.35 |\n| +Self-Ask    | 82.69 | 25.46 |\n| +CogTree     | 93.16 | 34.68 |\n| Llama-7B     |       |       |\n| +Specialize  | 84.32 | 34.21 |\n| +DecomP      | 82.43 | 39.75 |\n| +Self-Ask    | 83.98 | 38.35 |\n| +CogTree     | 94.25 | 61.28 |\n\n*Table*: Performance metrics for different methods with EB and GSM8K.\n\nIt can be observed that, when compared with the finetune-based methods, Cogtree still achieves state-of-the-art results. This is attributed to not only decomposing the problem but also incorporating result validation in subsequent steps.\n\n### Q3: Why decomposing step by step? Does the experiment prove the effectiveness of decomposing?\nStep-by-step decomposition refers to breaking down a complex problem into simpler problems, and the effectiveness of this approach has been demonstrated in Least-to-Most. We conducted additional experiments. \"w/ decomposition\" indicates that we used the method from our paper to decompose and sequentially answer the original problem. On the other hand, \"w/o decomposition\" means that we did not use the intermediate problem decomposition and directly answered the original problem, relying on System 1 to generate the answer.\n\n| Model   | w/ decomposition EB | w/o decomposition EB | w/ decomposition GSM8K | w/o decomposition GSM8K |\n|---------|----------------------|----------------------|-----------------------|-----------------------|\n| GPT2-XL    | 92.63                | 35.84                | 62.38                 | 18.94                 |\n| LLama-7B  | 93.25                | 61.28                | 69.79                 | 27.16                 |\n\n\n*Table*: Comparison of models with and without decomposition.\n\nAs we can see, the accuracy of directly answering the original problem is low, especially when the original problem is complex. This is also in line with human cognition. When solving math problems, we also solve intermediate problems first and then obtain the final answer, which improves our accuracy.\n\n### Missing References\nSorry for missing these two citations. We'll add them in the revised version.\n\nWe sincerely thank for your time and efforts.", "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. A thorough experiment about the CogTree method. Prove the effectiveness of finetuning and adding a reflective system. ", "reasons_to_reject": "1. Although the story of the intuitive and reflective system sounds fancy, essentially, it's a traditional system with a generator along with a scoring mechanism (discriminator). The difference lies in the decomposition part, which was discussed widely in previous work like Least-to-Most prompting, Self-Ask,  Decomposition Distillation, DecompT5, etc. \n2. Expected to see the performance gain compared with other SOTA finetune-based methods. \n3. Expected to see a general method to adapt to datasets that do not have intermediate subquestions and answers, which is common in most situations. ", "questions_to_authors": "1. Most training datasets do not contain intermediate subquestions and answers. Is CogTree invalid in such situations? \n2. CogTree is finetuned on the same distribution as the test set (EB and GSM8K), is it unfair to compare with LLMs which are few-shots? Expected to see the experiments compared with other finetune SOTAs. \n3. Why decomposing step by step? Does the experiment prove the effectiveness of decomposing?", "paper_topic_and_main_contributions": "This paper introduces CogTree, a system method constitute of a generator and a discriminator, which are applied to decomposed steps in reasoning tasks. \n\nMain contributions include a comparable performance with GPT-3.5 using smaller LMs. ", "excitement": 2, "reproducibility": 4, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"Typos_Grammar_Style_and_Presentation_Improvements": "1. in line 333, reference error."}, "extra_text": {"Missing_References": "@misc{shridhar2023distilling,\n      title={Distilling Reasoning Capabilities into Smaller Language Models}, \n      author={Kumar Shridhar and Alessandro Stolfo and Mrinmaya Sachan},\n      year={2023},\n      eprint={2212.00193},\n      archivePrefix={arXiv},\n      primaryClass={cs.LG}\n}\n\n@misc{zhou2022learning,\n      title={Learning to Decompose: Hypothetical Question Decomposition Based on Comparable Texts}, \n      author={Ben Zhou and Kyle Richardson and Xiaodong Yu and Dan Roth},\n      year={2022},\n      eprint={2210.16865},\n      archivePrefix={arXiv},\n      primaryClass={cs.CL}\n}"}}, {"review_id": "424YY1bGnZ", "reviewer": "Reviewer_BP1d", "summary": "", "questions": "[Q1] At their core, LM are basically probability distributions over language vocabularies: as such, LMs are unfit to deal with logical reasoning. They can be trained with sophisticated objectives, but still this will result in getting (only) more accurate distributions while reasoning is a matter of propositional knowledge. I am sure that the Authors will follow this argument: seeing that Weng earns $12 per hour for babysitting, and that yesterday she just did 50 minutes of babysitting, thereby earning $10 is almost useless to make a decision on the case of Frida, who earns $500 per (5 working days a) week but worked only three days this week. The underlying computational device is similar, but by observing sentences and tokens herein no suitable generalization can be drawn from the case of Weng to that of Frida. Can the Authors explain how a LM can be able in principle to generalize from the case of Weng to another one, such as the case of Frida?\n", "limitations": "", "rating": 4, "confidence": 4, "soundness": 4, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "### Q1: Can the Authors explain how a LM can be able in principle to generalize from the case of Weng to another one, such as the case of Frida?\nThe generation at the token level does indeed impose limitations on the language model's performance in tasks involving logical reasoning and propositional tasks. However, what is surprising is that despite the token-level training of large models, such as GPT-4, they possess the ability to perform logical reasoning and provide mathematical answers. One of OpenAI's findings is that code pre-training aids in enhancing the reasoning capabilities of these large models. The rationale behind this lies in the fact that code inherently contains a wealth of logical judgments, with interconnections between code blocks. Similarly, in natural language, there exists a corpus of expressions like \"because XXX, therefore XXX\". Pre-training on such materials equips language models with reasoning abilities for downstream tasks (as downstream tasks essentially reuse the abilities obtained during pre-training).\n\nReturning to your question, \"how can the language model generalize from the case of Weng to that of Frida?\" Our understanding is that the model, after being exposed to extensive pre-training data, acquires the capability to generalize from one category of logical reasoning task to another similar task. Fine-tuning in the downstream phase activates this specific task-related ability. One potential improvement in the future could involve generating potential choices for the next paragraph, rather than predicting the next token, as this might enhance the language model's problem-solving and logical reasoning capabilities.\n\nWe sincerely thank for your time and efforts.", "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 question whether LMs are able to gain any sort of semantic knowledge and logical reasoning ability is a relevant one, so that paper is fully appropriate for the Audience of this Conference.", "reasons_to_reject": "- It seems that LMs are not fully adequate to deal with higher-order tasks, such as complex logical reasoning. Their usage should thus be supported by some sort of either theoretical or practical motivation.", "questions_to_authors": "[Q1] At their core, LM are basically probability distributions over language vocabularies: as such, LMs are unfit to deal with logical reasoning. They can be trained with sophisticated objectives, but still this will result in getting (only) more accurate distributions while reasoning is a matter of propositional knowledge. I am sure that the Authors will follow this argument: seeing that Weng earns $12 per hour for babysitting, and that yesterday she just did 50 minutes of babysitting, thereby earning $10 is almost useless to make a decision on the case of Frida, who earns $500 per (5 working days a) week but worked only three days this week. The underlying computational device is similar, but by observing sentences and tokens herein no suitable generalization can be drawn from the case of Weng to that of Frida. Can the Authors explain how a LM can be able in principle to generalize from the case of Weng to another one, such as the case of Frida?\n", "paper_topic_and_main_contributions": "This paper proposes a novel framework (CogTree) aimed at building a tree-like structure going all throughout from a query (root node) to the leaf nodes, containing questions that need to be answered. \nThe question whether LMs are able to gain any sort of semantic knowledge and logical reasoning ability is a relevant one, so that paper is fully appropriate for the Audience of this Conference.\n\nThe paper nicely starts with a reference to Cognitive Science literature, namely to the dual process theory: one chief trait of the proposed work lies in the distinction between an implicit extraction module (which is clearly to be mapped onto 'system one' processes), and a reflective module (which should be framed as a 'system two' set of processes).\n\n\nA state-space search approach is adopted to break down the goal into smaller components, that allow reaching the goal (which is represented as a query). At the heart of the reflective system we have a prompt-based approach, where the model is employed to output a judgement on the appropriateness between query and its decompositions on three classes: sure, impossible or likely.\n\nThe evaluation was conducted on the Entailment Bank (EB)and the GSM8K dataset, and employing GPT2-XL and LLaMA-7B models. Experimental results show that a lighter LM (GPT2-XL, 1.5B) outperforms a richer LM (GPT-3.5, 175B). The latter model obtains improved accuracies with Chain-of-though and Tree-of-thought prompting.\n\n\nThe work is well structured and well written; it provides enough detail to grasp all main elements (the code will be released upon acceptance).\n\nI have one main concern. At their core, LM are basically probability distributions over language vocabularies: as such, LMs are unfit to deal with logical reasoning. They can be trained with sophisticated objectives, but still this will result in getting (only) more accurate distributions while reasoning is a matter of propositional knowledge. I am sure that the Authors will follow this argument: seeing that Weng earns $12 per hour for babysitting, and that yesterday she just did 50 minutes of babysitting, thereby earning $10 is almost useless to make a decision on the case of Frida, who earns $500 per (5 working days a) week but worked only three days this week. The underlying computational device is similar, but by observing sentences and tokens herein no suitable generalization can be drawn from the case of Weng to that of Frida. Can the Authors explain how a LM can be able in principle to generalize from the case of Weng to another one, such as the case of Frida?\n \n\n\nPOSSIBLE IMPROVEMENTS\n- lines 209-19 (on the Decomposition step) are unclear, should be rephrased to clarify (illustrating scores associated to a working examples would be beneficial)\n- Figure 5: some description for the x axis must be provided, e.g. 'inference chain length'\n- the content of the Limitations section has not to do with actual limitations: en effort to elaborate on limitations is required here...\n", "excitement": 4, "reproducibility": 4, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {"Typos_Grammar_Style_and_Presentation_Improvements": "\nMinor issues & Typos\n- line 082: citation 'Daniel, 2017' should be corrected into 'Kahneman, 2017';\n- line 333: missing reference LLaMA-7B (?) \n- line 357: reasoning abilitiy -> ability\n- Figure 5 is too tiny, nearly unreadable, should anybody ever try to print the paper...\n"}}, {"review_id": "MJPUc8mPLh", "reviewer": "Reviewer_UpNQ", "summary": "", "questions": "- How the sub-questions are generated? Section 3.1 is not clear about that. Although Figure 3 and Figure 4 show examples, it's difficult to understand how the decomposition is generated due to significant differences between them.\n- Regarding the ending step, the caption in Figure 2 says, \"the process terminates when the decomposition successfully matches the target answer\". I assume that this is just the for training step, isn't it?", "limitations": "", "rating": 4, "confidence": 2, "soundness": 3, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "### Q1: How the sub-questions are generated? Section 3.1 is not clear about that. Although Figure 3 and Figure 4 show examples, it's difficult to understand how the decomposition is generated due to significant differences between them.\nOur dataset includes the decomposition of each question. ( \\[ Query_1: Decomposition_1, Query_2: Decomposition_2, ... , Query_n: Decomposition_n \\] )\n\nFor math problems, the decomposition is like:\n\nQuery_1: Natalia sold clips to 48 of her friends in April, and then she sold half as many clips in May. How many clips did Natalia sell altogether in April and May?\n\nDecomposition_1: How many clips did Natalia sell in April? Natalia sold 48 clips in April.\n\nDecomposition_2: How many clips did Natalia sell in May? Natalia sold 48/2 = 24 clips in May.\n\nFor logical reasoning, the decomposition is like:\n\nQuery1: earth rotating on its axis causes cycles of day and night on earth\n\nDecomposition1: \\[ earth is a planet that rotates on its tilted axis \\] + \\[ a planet rotating causes cycles of day and night on that planet \\]\n\nTherefore, we can use the decomposition of other queries as context for the current query. For logical and mathematical data, our training is isolated. This means that mathematical and logical data are not trained together. In our training process, we select K examples as context to guide the model to generate the decomposition for the current problem. For example:\n\nQuery_1: xxxx\n\nDecomposition_1: xxx\n\nQuery_2: xxxx\n\nDecomposition_2: xxx\n\nQuery_3: xxxx\n\nDecomposition_3: xxx\n\nCurrent Query: xxx\n\nCurrent Decomposition: To be generated\n\n### Q2: Regarding the ending step, the caption in Figure 2 says, \"the process terminates when the decomposition successfully matches the target answer\". I assume that this is just the for training step, isn't it?\nIn fact, it is during the inference stage that we need to determine whether the process terminates (lines 342-350). We add an end token \"End\" after each question during the training stage, and when the generation system reaches the \"End\" token or when the maximum iteration limit of 20 is reached, our framework stops the reasoning process.\n\nWe sincerely thank for your time and efforts.", "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 paper addresses two relevant issues: the low performance of LLMs in reasoning problems and their computational costs.\n- It draws inspiration from cognitive science, making it easier to understand. Additionally, it applies contrastive learning, where reasoning steps and negative results play a major role which makes the system more understandable.\n- The experiments seem to be well-designed and robust.\n- The results enhance the accuracy of the systems and, more importantly, significantly reduce the number of parameters required for the calculation, although it requires more intermediate steps.\n", "reasons_to_reject": "- A key point of the method, the decomposition of the queries, is not explained in detail, making very difficult to understand how the sub-questions are generated. In section 3.3 is mentioned \"by leveraging in-context examples\", but it's not clear to me what this means.", "questions_to_authors": "- How the sub-questions are generated? Section 3.1 is not clear about that. Although Figure 3 and Figure 4 show examples, it's difficult to understand how the decomposition is generated due to significant differences between them.\n- Regarding the ending step, the caption in Figure 2 says, \"the process terminates when the decomposition successfully matches the target answer\". I assume that this is just the for training step, isn't it?", "paper_topic_and_main_contributions": "This paper proposes Cognitive Tree, a methodology to enhance the capatibility of LLMs in solving logical reasoning. It draws inspiration from the two-systems theory in cognitive science: the implicit extraction module (intuitive system), which generates a set of different potential answers to the query; the explicit reasoning module (the reflective system) which compares and scores these answers in order to obtain the right one. The results of the experiments show that this approach improves the system's efficiency by reducing the number of mecessary paramenters to answer the query.", "excitement": 4, "reproducibility": 3, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"Typos_Grammar_Style_and_Presentation_Improvements": "- Daniel Khaneman reference is wrong.\n- Line 333: missing reference"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents a methodology for approaching complex commonsense question answering via decomposition, and component-wise verification. The problem is of high significance to the NLP community, and the story builds on a catchy link to cognitive theory by Kahnemann et al. (system 1/system 2).

The paper generally presents a sound piece of work, but there are concerns over the novelty of the contribution, in particular, the abstract contains a very sweeping claim ("we are the first to unravel the cognitive reasoning abilities of LMs"), while several related works on question decomposition are not at all, or insufficiently, discussed. Similarly, the explanation of the core of the methodology, the generation of subquestions, is not entirely clear, and would benefit from step-by-step discussion of a running example.

Overall, the significance of the topic, and presented ideas warrant publication, yet the paper would significantly benefit from a careful revision, in particular w.r.t. its positioning.
Decision: Accept-Findings