Explicit Planning Helps Language Models in Logical Reasoning
Authors: Hongyu Zhao
Kangrui Wang
Mo Yu
Hongyuan Mei
Venue: EMNLP 2023 Main (2023)
Keywords: logical reasoning
large language model
planning
TL;DR: We develop LEAP, an LM-based logical reasoning system that does explicit planning.

Abstract: Language models have been shown to perform remarkably well on a wide range of natural language processing tasks. In this paper, we propose LEAP, a novel system that uses language models to perform multi-step logical reasoning and incorporates explicit planning into the inference procedure. Explicit planning enables the system to make more informed reasoning decisions at each step by looking ahead into their future effects. Moreover, we propose a training strategy that safeguards the planning process from being led astray by spurious features. Our full system significantly outperforms other competing methods on multiple standard datasets. When using small T5 models as its core selection and deduction components, our system performs competitively compared to GPT-3 despite having only about 1B parameters (i.e., 175 times smaller than GPT-3). When using GPT-3.5, it significantly outperforms chain-of-thought prompting on the challenging PrOntoQA dataset. We have conducted extensive empirical studies to demonstrate that explicit planning plays a crucial role in the system's performance.

Explicit Planning Helps Language Models in Logical Reasoning
Hongyu Zhao 1.3 Kangrui Wang 1.3 Mo Yu? Hongyuan Mei
Universitty of Chicago
WeChat AI Toyota Technological Institute at Chicago
(hzhao, hotguun)ettti..c. edu
Abstract
thezey
lggcel measoning process steps se ection deduction)
goall
Language models have been shown to perform remarkably well on wide range of natural lan- guage processing tasks. In this paper, we pro- pose LEAP, a novel system that uses language models to perform multi-step logical reasoning and incorporates explicit planning into the in- ference procedure. Explicit planning enables the system make more informed reasoning decisions at each step by looking ahead into their future effects. Moreover, we propose training strategy that safeguards the planning process from being led astray by spurious fea- tures. Our full system significantly outper- forms other competing methods on multiple standard datasets. When using small T5 mod- els as its core selection and deduction compo- nents, our system performs competitively com- pared to GPT-3 despite having only about parameters (i.e., 175 times smaller than GPT- 3). When using GPT-3.5, it significantly out- performs chain-of-thought prompting challenging PrOntoQA dataset. We have con- ducted extensive empirical studies to demon- strate that explicit planning plays crucial role in the system's 's performance.
step
shep deduction
stop 2 seloctiion
step deductin
step
slip deducctonn
acted after step
5: Engies
only
5: Pagges
Sy
20000
adilec after slep
camiveres.
Figure 1: An example of theory T and goal x as well as a human- aanaa-an multi-step logical reasoning process that proves the goal based on the theory.
relevant and performs multiple rounds of deduction to reach the conclusion. At each round, the planning process looks ahead into the future outcomes of each possible reasoning decision (i.e., which to select and what to deduce), examining which of them is more likely to discover valid proof for the given statement.
Why planning? Planning fundamental property of intelligent behavior: it uses foresight to anticipate future outcomes of each possible decision and informs the process of decision making to achieve desirable end results. This concept has influenced the develop- ment of various methods in the field of artificial intel- ligence. Minimax-style game playing evaluates each possible move by anticipating replies and counterreplies between the player and the opponent (while assuming that both play optimally) (Russell and Norvig. 2010). Model-based reinforcement learning uses environment models simulate responses to actions and then uses the simulated experiences to help learn value functions (e.g., Dyna, Monte-Carlo tree search) (Sutton and Barto, 2018). In natural language processing, planning has been used to help language models generate utterances that satisfy complex constraints (Lu et al., 2022a).
the
1 Introduction
Logical reasoning is one of the most important and long- standing problems in artificial intelligence (Russell and Norvig, 2010). A logical reasoning system is able to draw new facts by applying known rules to known facts and determine the truth value of a given hypothesis; see Figure for an example. For decades, research in building reasoning systems has heavily relied on for- mal logic. Since the surge of pretrained large language models (LMs), there have been efforts that harness the power of pretrained LMs and directly handle natural language statements to perform multi-step logical rea- soning; see section 5 for a summary. In this paper, we propose LEAP, the first LM-bd logical reasoning system that performs explicil planning during inference. While determining the truth value statement, our system searches over the known facts for those which Work done during internship at TTI-Chicago.
Planning is important for logical reasoning. By ex- amining the future outcomes of each possible decision, plamning-base based system will be able to focus on the actually useful (given and deduced) facts at early steps, thus enjoying a high chance of success. In addition, a Maaning-basee reasoning system tends to be more in- terpretable, thus more useful in user-centric and safety- critical scenarios. For example, at each round of deduc- tion, planning will explicitly show "what will happen after-and that is also why-1 select these known facts

---

and deduce this particular new fact from them", which is more informative than only saying "I select these and deduce this." However, none of the previous I.M-based systems use explicit planning during inference.
and conclude "John is evil." by combining it with the previous deduction. In this paper, we build an automatic system that is able perform this kind of human-like logical reasoning.
Why is it challenging? During planning, a verifica- tion mechanism is in need to determine the quality of each possible proof. In reality, the verification has to be performed by a model (like in model-based rein- forcement learning), and models are imperfect due to architectural biases and finite training data. As a con- sequence, the reasoning system faces the problem of model exploitation: any model mistake may misguide the planning such that it favors a seemingly promising decision over the actually correct one. For example, the model may incorrectly think statement proves the hypothesis, just because of a significant lexical over- lap, causing the planning to favor decision that helps deduce that statement and lead to the wrong conclusion.
Our LEAP Framework
We propose LEAP, an LM-based logical reasoning sys- tem that performs explicit planning. Pretrained LMs are excellent at understanding natural languages as well as fluently generating them.' Our LEAP system harnesses such abilities to simulate step-by-step reasoning pro- cesses that resembles how humans do logical reasoning. In this section, we will incrementally build up our full system, starting from a base system (section 3.1) to how explicit planning is integrated (sections 3.2-3.3).
3.1 Base System
Our base system consists of a selection model Psal- a de- duction model Pacd, and a verification model pver. They work together in an iterative fashion to perform multi- step reasoning like shown in Figure 1. At each step, the selection model Peel selects a couple of premises from the current theory. For example, step-1 in Figure 1, it selects "eagles cat rabbits" and "rabbits are animals" from the original theory of four premises. Then the deduction model pded reads the selected premises and outputs a new statement that is logically plausible given the selection. For example, at step-1 in Figure 1, it de- duces "eagles eat animals". The new statement is then added to the theory (whose size increases by one) and it may be selected by Psel at later step. The procedure stops if the max number of reasoning steps has been reached; otherwise, it starts a new iteration of selection and deduction. This procedure gives reasoning path as shown in Figure 1.
Our contributions. We first propose a logical reason- ing system along with a beam- nuun-serchh-tylle inference algorithm (section 3.1): the system utilizes pretrained LMs and mimics human-like step-by-step reasoning. Then we integrate explicit planning into the inference algorithm (section 3.2) and significantly improve the performance of the system. We empirically demonstrate that planning encounters the issue of model exploita- tion: when the given hypothesis is false, planning may find out an incorrect proof that fools the system to be- lieve that the hypothesis is true. Finally, we develop a training strategy that effectively mitigates the issue of model exploitation (section 3.3). Our training strategy is adversarial: for each training theory, we synthesize non-pre con-provable hypothesis but call the planning based inference method to find highly-scored proof for it; then we refine the verification model such that the score it assigns to that proof is suppressed; at the same time, we force the verification model to preserve its scores the correct proofs of the provable hypothesises. Our experiments show that this strategy further significantly improves the performance of our system.
We define the proof score of the reasoning path to be
f[T, xo) lif max
Pver (xo xx,) E (0, 1) (1)
where theory T has been extended to include all the new deductions obtained through the reasoning process. Each Pver(x) x,) is given by the verification model and measures how likely the statement x., will prove the goal: e.g.. "eagles only eat animals" (xg) should have a lower score than "cagles are carnivores" (x7) since the latter means the same as the goal. The proof score f(T, xy) can be regarded as the system's 's belief that the theory proves the goal.
2 Problem Formulation
We consider the problem of logical reasoning. Given a hypothesis (or, in other words, a goal) x. and a theory
T = {xi, (xi,...> xN), we are interested in determining the truth value of Xo. i.e., whether Xg can be logically proved by T. If the goal Xp is provable, we are inter- ested in discovering the reasoning process that proves it. Below is an example theory T
How do we define the verification score Pver
x,,)? We utilize a pretrained DeBERTa model (He et al., 2021) that was fine-tuned on the standard MNLI lan- guage inference dataset (Williams et al., 2018). For a statement x,, and goal Xo. we define the verification score Pxer x,) to be the DeBERTa probability that Xn, entails Xg. It is a reasonable estimate for the proba- bility that x, proves Xg-
"Richard is King." "John is also King."
"John is greedy." "A greedy King is evil."
For the goal "John is evil.", humans can easily verify that it is provable by figuring out the following reason- ing path: we can select the two premises about "John" " and deduce "John is greedy King." by combining them; we then pick the premise about "greedy King"
Wee use "language model" broadly to refer to multiple types of language representation models including encoder- only, decoder-only, and encoder-docoder models.

---

Our system is general: the selection and deduction models can be any pretrained decoder-only or encoder- decoder models, including the small models whose pa- rameters we could update and the huge models that we could only use as blackboxes. In section 4, we will discuss some specific model choices well as how to transfer them to our logical reasoning problem. Gener- ally, we only require that
Py 8) under deduction model Paed- Each deduc- tion expands the ongoing path: it updates the scores by g + g vg and f < max (S, Pver (Xo yn))-
Now we end up with 1s² extended paths and only keep B of them which have the highest g.
In the end, return the reasoning path with the highest proof score f: intuitively, among all the choices that are probable under the selection and deduction models, we'd like to pick what's most likely to actually prove the goal. This method becomes one-hest decoding if we set B 1. Appendix B. has more details of the base system, including pseudocode for inference (Algorithms 1-3).
the selection model Psel can propose multiple multi- premise selections given the theory T and assign a score to each of them. For multi-premise selec- tion S (c.g., $ = X2X3), we denote the score to be (s T, x0). or (s) for short.
the deduction model Poad can draw multiple deduc- tions given a selection s and assign score each of them. For a deduction x, we denote its score to be Paea (x| s).
Relations to formal logic systems. Our base system resembles a rule-hased system and the inference method is like a combination of the forward and backward chain- ing algorithms (Russell and Norvig. 2010). Each deduc- tion step extends the theory by deducing new facts from the existing facts and rules, which resembles the forward chaining algorithm. Each selection step is conditioned on the goal, which resembles the backward chaining algorithm. However, the forward and backward algo- rithms can not handle the theories that have non-definite clauses like "Either John or Richard is evil."; our method doesn't 't have that limitation.
So far, we have been assuming that we select the highest scored selection and deduction at each step (e.g.. in Fig- ure and at the beginming of this section). But this kind of one-best decoding tends to be short-sighted: there may he multiple possible reasoning paths proving the goal; some may be better than the others (e.g., they are shorter) but they may not appear to be promising at the early steps; such reasoning paths may be missed by one-best decoding. Therefore, we develop an improved decoding method that resembles beam search (Jurafsky and Martin, 2000).
3.2 Improvement-A: Inference with Planning
The inference method in section 3.1 lacks planning. While expanding each ongoing path, the selections and deductions are ranked by their scores a and v that are only conditioned the previous selections and deduc- tions. However, the selections and deductions that ap- pear to be promising may not actually lead to the future steps that able to prove the goal. In this section, we propose an improved inference method that ranks the selections and deductions by explicit planning. We refer to the improved version as System-A.
Sean-searc inference. We maintain buffer B of maximum size B which can host at most B ongoing reasoning paths, which we think are the most promising and will eventually prove the goal. Each of ongoing path tracks its proof score f as well as its log-probabiln probabilityy g under our system. Both f and 9 get updated as the path progresses, which we will explain shortly. It also tracks initial theory as well as its selections and deductions; the initial theory and the deductions form the extended (or current) theory. As long as we haven't 't reached the keep expanding each
Planning for selection. At each selection step, we expand each ongoing reasoning path with B selections given by the no-planning method, and let the buffer B keep B of the B32 extended paths with the highest scores. The key improvement is: we redefine the score such that it reflects not only the probability of the selection under the model Psal but also the quality of the future steps that the selection leads to.
maximum number of steps, ongoing path in the buffer. Each step of expansion includes a selection step followed by a deduction step. At the selection step, we do the following:
For each ongoing path, we find its top most proba- ble selections (i),s,)).... Su) where u, is the log-probability log (S:). Each selection expands its ongoing path and updates its g score by g + g + ub.
Precisely, we redefine u = llog (sa( +aAu where a a tunable hyperparameter and Au is a future-specific correction term that we can compute after rolling out some imaginary future deductions. For a possible se- lection s. we call the base one-best decoding method (section 3) to roll out 1) steps of future deductions Then we obtain (xe 8.)-whiot which
Now we have B² extended paths and let the buffer B only keep B of them which are most probable under the system (i.e., those with the highest g).
" .1...., evaluates how likely each rolled-out deduction may entail the gnal-and compute the correction term by Au de max log P {a)) Note that A is the log- arithm of the proof score defined on the rolled-out future
At the deduction step, we follow a similar procedure:
For each ongoing path, we draw its top B most proba- ble deductions (1)...),... (Vg, Yp) conditioned on the most recent selection s; og is the log-probability

---

curnect meeor
ponsible
2 sdepe miker
gho
curme Eneery
Curmen
prodot
grol
steps
mikout ceduction)
%g
proa Gool -0
proaf score +0.38
proot score w087
proct score modz
%4% has Nighest scom, selected
this has Highent scoes, thii chonee on cieduction
proof score -0.71
(a) Planning for selection.
(b) Planning for deduction.
Figure 2: An illustration of explicit planning at the 2nd selection and deduction step of the full procedure in Figure 1.
reasoning path. Intuitively, higher Au means that this future reasoning path is more likely to prove the goal. In the end, we obtain B selections with updated scores (1); ..... (un, 8n) for each ongoing path. This improved subroutine is illustrated in Figure 2a. Its pseudocode is Algorithm 10 in Appendix B.5.
sary. In analogy to this process, our base system can be considered as System 1, while the advanced planning- based system like System 2. which requires more computation but performs more deliberative reasoning. Precisely, at each step of reasoning. the no-planning base system needs 3B operations (i.e., select, deduce, and verify). In contrast, the planning- inference needs 3B + + + 3B2 D operations: for each ongo- ing reasoning path in the buffer, need to examine its B possible expansions (selection or deduction), and roll out D future steps (via one-best decoding) for each ex- pansion. Overall, the planning-based system consumes + 2/D) times of computation. Fortunately, our imple- mentation is efficient because of careful tensorization and parallelism; please see section 6.1 for an analysis of its actual walk-clock time.
Planning for deduction. At each deduction step, we expand each ongoing reasoning path with B deductions given by the no-planning method, and let the buffer B keep B of the extended paths with the highest scores. Similar the planning-basee selection step, the key improvement is the refined definition of the score, which reflects not only the probability of the deduction under the model Pded but also the quality of its future steps. Precisely. we first draw B most probable deductions (v1, v)).y)...... (VB. Y y) under the model pied- Then we edit the score vs- < U/ + 8Av, where 3 is a tun- able hyperparameter and Au is future-specific cor- rection similar to Au. For each possible deduction yn- we call the no-planning one-best decoding method to roll out D steps of future deductions Yo,1....,
3.3 Improvement-Bi B: Refined Verification Model
The key limitation of the planning method is that it may exploit the pretrained verification model pver such that the final proof score f (theory, goal) is inflated: this method keeps ongoing paths that have high per possible future deductions). This will result in high rate of false positive: even when the goal is not provable, explicit planning will still try its best to find out the reasoning paths that have high proof scores; a high proof score will then fool the system itself to believe that this goal is provable. This issue is illustrated in our experiments (see Figure 5c and related analysis in section 6. 6).. In this section, we propose to resolve this issue by refining our verification model. We refer to this version our LEAP system as System-B.
Then we compute AuG, dd maxx log Pver (xo Ve,a). In the end, we obtain B deductions with updated scores (o).y.)..... (VB. yn) ) for each ongoing path. This improved subroutine is illustrated in Figure 2b. Its pseudocode is Algorithm 11 in Appendix B.5.
The full method. Except for the score definitions. the planning-based inference method looks the same as the no-planning method: the top selections and deductions will expand their ongoing paths and update their scores I and y; the buffer will only keep B paths with the highest g. But the planning-base end up with different set of reasoning paths than the no-planning method since the scores have been affected by the roll-outs. The full inference algorithm is Algo- rithm 1 in Appendix B.1: when D > 1. it does explicit planning: when D= = 0, it doesn't i roll out future steps and becomes the no-planning method.
Our method is tune the verification model pver such that (goal deduction) is low when the deduction can not prove the goal. Technically, given a theory T and non-provalle non-provable goal Xo. we first call our planning- based method to find a reasoning path that tries to prove Xo. and then make Pver y) to be low for each deduction y in the reasoning path. Precisely, we locally minimize &
method will tend to
log (xe 1) - log (Pver y) + Pee y))
System 1 vs. System 2 reasoning. According to the "dual process" theories of reasoning (Evans, 2003), hu- man cognition can be thought of as an interplay between a fast and intuitive "System I" and a slow but amalytical "System 2". Given enough time. System can analyze the default behavior of System and override it if neces-
(2)
where Xa is provable goal and y is deduction in a reasoning path that actually proves xg- This objective E is a typical contrastive learning objective (Ma and Collins, 2018). In our setting, it means: if we are given

---

careert theor
modekarsposid incomect wasoning pat
nzn-povvable goal
5Pp
SP
SP
hidden
emboddingg nos of specia takens P.d X X No A de 1 wih -
Ws
0:15
0.75
0.83
oumentsheery poal
(righ Pusl
decnsne prozt wore encerved
T5 Encodor
T. Decoder
Pullic [P) +
Punlie 199
proo siore of comnott
ENC
SPc
%
SP&
SP
DEC
g'ound buth ressonin path
provable pool
specia lokand bainable embesdiings ENC 5P,5P, SP,....... DEC
Figure 3: Illustration of our contrastive learning frame- work for refining verification model.
(a) selection step. The T5 encoder reads special kens, the goal Xo. and the theory T. The decoder com- putes (x,, | Txxx) del o(h w,, where Wa, the embedding of special token SP...
a non-provable goal &o paired with a model-proposed reasoning path as well as a provable goal Xo paired with a correct reasoning path, our verification model pver should learn to correctly judge that "Xo proved by path of y" is less likely than "Xp proved by path of y". This framework is illustrated in Figure 3.
sottrax pros
0.03
3:03
Die Eagles only arinas,
T5 vocabulary
Ue
ground-uuth deduction
Eagles
only
Additionally, we augment the loss E with
Encoder
Decoder
Ω Pver [Xo ) log Pver (Xo | y) (1 (x0 y)) log (1 (x0 y))
(3a)
%
DEC
Eagles only
content of selection
Ny Eaglis nnteatpans.
Sy Exgls sut animal.
special tolkons with trinable enizeddings. DEC
(3b)
(b) deduction step. The T5 encoder reads special tokens and the selection deduction autoregressively. It is currently trying to find the token after "only", and "eat" wins.
x4 xs and generates
where Pver is the pretrained verification model used in sections 3.1 and 3.2. It the KL-divergence (minus H (Prer), which is constant wrt. model parameters) be- tween the pretrained and tuned verification models, and minimizing it aims prevent the tuned model from de- viating too much from the pretrained. This is desirable since the pretrained model already enjoys a high rate of true positive for provable goals; results in Figure 5b and relevant analysis in section 1.
Figure 4: An illustration of how the SLM selection and deduction models in the example procedure of Figure I.
selected:2
II (xn Xo) 1:
II (1-Peelxx, Xx))
D:X.. gs
Technical details (including visualization) about the verification model are in Appendix B.2.
Then finding the most probable selection is to choose the premises x,, that have Psa( (x,, T, xo) > 0.5.² This procedure is illustrated in Figure 4a.
4 Small and Large Model Versions
Give a selection s, the deduction T5 model reads and produces a logical deduction y one token after another. The probability of under the model is Py s). Figure 4b shows a deduction step.
Now we introduce two specific versions of our proposed framework: the small language model (SLM) version that uses pretrained T5 (Raffel et al., 2020) and the large language model (LLM) version that utilizes GPT-3.5.
Training the SL.M version requires corpus of theo- ries and goals as well as their ground-trute reasoning paths. The selection steps are training examples for Paeli the deduction steps are training examples for Paea. Tak- ing Figure as an example, the selection training data (green background) is
4.1
SLM Version
Our SLM version adapts pretrained TS models (Raffel et al., 2020) to be the selection and deduction models. We use the T5-small instance (from Huggingface) that has only 60M parameters because we would like to investigate how well very small system will work in practice. Shortly in section 6, we will see that this small system works very well.
T {x1, X2, X3, x4)
and X2 X3
T (xi, X3, X4. X:)
and XG
T [x1, X2, X3, X4. Xs, xa) and X6
Given a theory T and a goal xo, the selection T5 model reads them input and produces the probability (x, Xo) that each premise X., is selected in the attempt to prove the goal Xp. Then we can use these
and the deduction training data (blue background) is
s X2 X3 and new statement = X
"We treat each x. independently.
probabilities compute the probability Psa(s T, Xa) that a multi-premise combination s (e.g., = X2X4) is
Foor each xa, if pa >> 0.5, we will have Put > 1 - Punl- That is, including it in s will increase the probability of s.

---

X4 X5 and new statement y N6
strong performance in scientific reasoning. Our main contribution is complementary to the previous work: we integrate explicit planning into L.-haaed reasoning sys- tems and design a training method to mitigate the model exploitation issue that arises in planning. Our system is kind of general model programs (Dohan al., 2022> especially those with verification models (Cobbe et al., 2021)- which use language models inside as probabilis- tic programs and apply disparate inference algorithms to the models. Other kinds of approaches to use LMs for reasoning include training discriminative models (Clark et al., 2020; Picco et al., 2021; Ghosal et al., 2022; Zhang et al., 2023), prompting GPT-3 with spelled-out reasoning procedure (Wei et al., 2022; Talmor al., 2020), and distilling GPT-3.5 (Fu et al., 2023).
Xg and new statement y Xy
The training objectives for the selection model Poel and deduction model Pded are log (s | T, Xo) and P s), respectively.
Appendix B.3 includes more details about the SLM
version (e.g., pseudocode for training and inference).
4.2 LLM Version
Our LLM uses GPT-3.5-turbo as the selection and de- duction models. GPT-3.5 is the current largest and state- of-the-art language model that we have access to. We instruct GPT-3.5 to perform selection and deduction by few-shot prompting: please see Appendices B.4 and C.6 for technical details and the prompts used our ex- periments. This is similar to the selection-inference inference framework proposed by Creswell et al. (2023) except that we request GPT-3.5 to propose multiple possible selections and deductions at each step. This design al- lows us to perform explicit planning for each possible selection and deduction and then choose the hest option based on planning. Since GPT-335 doesn't 't give the val- ues of the probabilities pset and Pled. we set u = v = 0 in the inference methods, conditioning the selection and deduction entirely on the planning signals. The proof score f is still given by the DeBERTa verification model that we introduced in section 3.
Another straightforward approach for text-based logi- cal reasoning first translate natural language state- ments into formal logic expressions and then use for- mal logic inference engine (Weber et al., 2019; Lev- kovskyi and Li, 2021: Nye et al., 2021; Lu et al., 2022b; Betz and Richardson, 2022). We tried this approach in our experiments; please see Appendix C.3 for details. Another research area related to multi-step logical reasoning is to reason over graph-structured data. A pop- ular kind of graph knowledge graphs, i.c., relational graphs over symbolic tuples (Lao and Cohen, 2010; Wang et al., 2013; Neelakantan et al., 2015; Cohen et al., 2017; Xiong et al., 2017: Chen al., 2018; Das al., 2018). Another kind of graph is built by linking texts via lexical overlap or hyperlink connections (Welbl et al., 2018; Yang et al., 2018; Khot et al., 2020, 2021). Meth- ods in this area involve multi-step navigation through graphs. But they rely on pre-defined symbolic and re- lational structures, thus not directly applicable to our setting. Additionally, recent research (Chen and Durrett, 2019; Min et al., 2019) shows that optimizing the perfor- mance on these datasets is not well aligned to improving the models' fundamental reasoning abilitics.
5 Related Work
Reasoning has been a long-standing research topic in natural language processing. For long time, the ma- jority of research in this direction has been focused on simple tasks such as single-sentence language infer- ence (Bernardi, 2002: Zamansky al., 2006; MacCart- ney and Manning, 2009; Angeli et al., 2016; Hu et al.. 2020; Chen et al., 2021) and single-step commonsense inference (Rajani et al., 2019; Latcinnik and Berant, 2020; Shwartz et al., 2020).
Experiments
Recently, there has been an increasing research inter- est in the more complex problem of multi-step logical reasoning, which we study in this paper. Saha et al. (2020), to the best of our knowledge, is the first to pro- pose an interpretable LM-based model for this problem. They and Tafjord et al. (2021) work on synthesized data of limited language variability. The LM-based system proposed by Bostrom et al. (2022) has an architecture similar to the SLM version of our base system except that their inference is one-best decoding without plan- ning and their deduction model is trained with extra data collected by Bostrom et al. (2021). The selection- inference system of Creswell et al. (2023) is similar to the LLM version of our base system but their selection and deduction models are New-shot-prompter GPT-3; we compare with them in section 6.3. Liu et al. (2022) also use a similar architecture which they train by rein- forcement learning. Weir and Van Durme (2022) embed LMs into a backward chaining framework, achieving
We carried out a diverse set of experiments that can demonstrate the effectiveness of our proposed methods. We implemented our methods with PyTorch (Paszke et al., 2019) and Transformers (Wolf et al., 2020). Our code is at https://gi httpthhw...ccciiiiiiiiee cwwp///iineeoonn/eaapa.
6.1 SLM Experiments on Entailment Bank
We first trained and evaluated our SLM version on the standard benchmark Entailment Bank (Dalvi et al., 2021) dataset. This dataset is a corpus of human- annotated (theory, provable goal. reasoning path) tuples, including the example in Figure 1. It uses informal lan- guage, which closely aligns with how humans engage in logical reasoning during everyday conversations. This dataset has two versions: in Version-1, for each pair of theory and goal, all the premises have to be used to prove the goal: in Version- II, each theory includes few distractors that are not useful for proving the goal.

---

Syren
For Syren
Syren
(a) ROC curves.
Acc on positive examples.
(c) Acc curves negative examples.
Figure 5: Test results with 95% bootstrap confidence intervals (CFs) Entailment Bank Version-I.
METHOD
AUROC
AUACCres
AUACCsB0
F1
BASELINE-T5
0.67 (0.63, 0.71)
0.53 (0.49, 0,57)
0.75 (0.72. 0.78)
0.62 (0.59, 0.64)
BASE SYSTEM
0.56 (0.51, 0.60)
0.42 (0.38, 0.47)
0.78 (0.76. 0.81)
0.67 (0.67, 0.67)
SYSTEM A
0.87 (0.84, 0.89)
0.86 (0.84, 0.89)
0.54 (0.50. 0.57)
0.82 (0.80, 0.84)
SYSTEM B
0.94 (0.92, 0.95)
0.87 (0.84, 0.89)
0.82 (0.79, 0.85)
0.89 (0.87, 0.91)
RULETAKER
0.90 (0.88, 0.93)
0.91 (0.88, 0.94)
0.73 (0.69, 0.77)
0.84 (0.83, 0.86)
NEURALUNIF
0.72 (0.68, 0.76)
0.56 (0.56, 0.57)
0.49 (0.48, 0.50)
0.72 (0.71, 0.74)
GPT-3 (0-SHOT)
0.89
Table 1: Test results with 95% bootstrap CFs on Entailment Bank Version-I.
We trained the models on Version-I training data, but evaluated them both Version-I and Version-II II test data. Experiment details are in Appendix C, includ- ing data statisties (Table 5) and training details (e.g.. hyperparameter tuning in Appendix C.2).
accuracy is the number of true positive divided by the total number of test cases; non- non-provable goals, the curacy is the number of true negative divided by the total number of test cases. As we can see, System-A works very well on the provable goals, but performs poorly on the non-provable goals. That is because System-A exploits the verification model by explicit planning: as we have discussed in section 3.3, the proof scores given by System-A tend to be high, thus yielding a high rate of false positive. System-B works well both provable and non non-provable goals: the refined verification model Pver successfully avoided being exploited by planning. Actual values of the areas under curves shown in Table 1: AUACC pos and AUACC correspond to the curves in Figure 5b and Figure 5c, respectively. The Fl numbers were computed as follows: we chose optimal threshold 7 by maximizing the F1 score on the development set, and then computed Fl the test according to the chosen 7.
We evaluated the abilities of the systems to classify provable and non-provable goals. For this purpose, we gave a non- provable goal to each dev and test theory by selecting it from other (theory, goal, reasoning path) samples. The selection is adversarial: we tuned a pretrained T5 model generate provable goal given theory; for each theory T, we looped over all the goals in the dataset that are guaranteed be not provable under T, and chose the one that the T5 thinks is the most probable given T (see details Appendix C).
Evaluation-I: binary classification.
For each given theory and goal Xo, we let the system generate a reasoning path that tries to prove the goal, and obtain the proof score ((T,x)) of the path. Given threshold
(0, 1), we say "Xx provable" if J(T, xo) 2 r and "xa is not provable" otherwise. For a systematic investigation, we varied 7 and plot receiver operating characteristic (ROC) curve for each system; the larger the area under ROC curve (AUROC) is. the better the system is.
For a comprehensive evaluation, we also compared with three other kinds of methods: GPT-3-davinci with 0-shot prompting, RuleTaker (Clark et al., 2020), and Neural Unification (Picco et al., 2021). GPT-3 achieves strong Fl of 0.89, and System-B performs well as this strong model. RuleTaker is a discrimina- tive method, training a RoBERTa (Liu et al., 2019) to perform logical reasoning binary classification (prov- able or not). Neural Unification is also discriminative method but has different architecture than RulcTaker,
The ROC curves are shown Figure 5a: our LEAP System-A A and System-B substantially and significantly outperform the base system and a T5 model (trained generating goals given theories); System-B further significantly outperforms System-A. Surprisingly, our base system underperforms the model even though it has learned to spell out its reasoning steps which expect to help the classification.
It requires more sophisticated annotation and prepara- tion of the training data than RuleTaker and our methods. Neither of them spells out reasoning process. For these methods, we matched their numbers of trainable param- eters with our methods for fair comparison. Overall, RakeTaker performs better than our System-A but worse than System-B. B. Neural Unification performs worse than
Figure 5h and Figure 5e show the results broken down into the accuracies the provable goals and non-provable goals, respectively. On provable goals, the

---

(a) ROC curves.
(b) Acc curves on positive examples.
(c) Acc curves negative examples.
Figure 6: Test results with 95% bootstrap CFss on Entailment Bank Version-II.
RuleTaker and our System-A, Note that these results are orthogonal to main finding that explicit planning is helpful for text-based multi-step logical reasoning.
METHOD
VERSION-1
VERSION-II
BASELINE-TS
0.60 (0.55, 0.65) 0.20 (0.16, 0.24)
BASE SYSTEM
0,46 (0.41, 0.52)
0.29 (0.25, 0.34)
SYSTEM
0.80 (0.76. 0.84)
0.44 (0.39. 0.49)
Analysis-I: robustness to size of training data. We also trained the models with (randomly sampled) 50% of the training data, and evaluated them on the same test set. It turns out that our System-B B still performs the best; see Figure (which looks boringly similar to Figure 5) in Appendix C.4 for details.
SYSTEM
0.88 (0.85, 0.92)
0.63 (0.58, 0.68)
RULETAKER
0.83 (0.79, 0.87)
0.73 (0.68. 0.77)
NEURALUNIF
0.62 (0.55, 0.69) 0.62 (0.57. 0.67)
GPT-3 (0-SHOT)
0.72
0.20
GPT-3 (5-SHOT)
0.97
0.96
GPT-3 (COT)
0.98
0.98
Table 2: Test accuracy with 95% bootstrap CFs in
Analysis-II II: A bout the regularization in equation (3). We compared the system with and without the regu- larization term Ω: without 22 System-B only achieves AUROC 0.79 (AUROCpos = 0.68 and AUROC = 0.65), worse than System-A. We also evaluated the tuned verification models on the MNLI dataset (on which they were fine-tuned) and found that: the model tuned without f only achieved 62.0% accuracy; the model tuned with ? achieved 91.4% accuracy, almost good originally was (91.7%). It means that the regularization term indeed helps the verification model preserve ability to judge the entailment relationship.
multiple-choice QA. Accuracy of random guess is 25%.
evaluation settings with distractors. We also found that training with distractors (i.e., using Verstion-II training data) significantly improved the results. Detailed results and analysis are in Table 6 and Table of Appendix C.4.
A Analysis-Y V: About buffer size. The buffer size B tunable hyperparameter. In our experiments, we chose B = 5. a common choice in text generation. A pilot experiment with B E (2,3,5 5, 10) showed that: smaller B tends to slightly decrease the accuracy on positive samples, but increase it on negative samples; a larger tends to slightly increase the accuracy on positive samples, but decreases it on negative samples; overall, there are only tiny changes in AUROC, which depends on accuracies on both kinds of samples.
Analysis-III. Robustness to distractors. We inves- tigated the robustness of the systems to distractors by evaluating them on Version-Il test data, Note that they were only trained Version-I training data. As shown in Figure 6, all the systems perform worse than they did on Version-I test data, but the performance drop of our systems is much smaller than that of the T5 model. It means that our systems are more robust to the dis- tractors. That is perhaps because our systems explicitly spell out their reasoning steps and explicit planning can help the systems (A and B) focus on the premises that are actually relevant the goal at each selection step.
Analysis- VI: Computation Cust. our experiments, used B 5 and D i.e., buffer size of 5 and roll-out depth of 2. According to the theoretical anal- ysis in section 3.2, the planing-based inference should be 1 + 2BD 21 times slower than the no no-planning method. In practice, it takes an average of 2.8 seconds for the no-planning method to work on a theory- goaa pair from Entailment Bank. For the planning- based in- ference, it takes an average of 31 seconds, only 11 times slower. The implementation faster than the thcoretical analysis thanks to tensorization and parallelism.
Analysis-IV: A About model size and denoising. To examine the effect of model size, we reran the main experiments with T5-small (60M) replaced by T5-base (220M): using larger model achieved consistently stronger performance; our planning- based systems still significantly outperform the base system. We also ex- perimented with denoising training of the selection and deduction models: every time we used a training exam- ple, randomly permuted the input statements. The denoising training led to a better generalization to the
Evaluation-II: Multiple-Choice QA. We further evaluated the systems in a multiple-choice question an- swering (QA) setting. Particularly, given a theory T in Entailment Bank, each system is asked to select the
(1) provable goal from four choices (x(") xx(² Xx x }:
(3) (4)):
one of them is the ground-truth provable goal while the

---

METHOD
ACC
METHOD
DEPTH=1
DEPTH=3
DEPTH=5
BASE SYSTEM
0.68 (0.65, 0.71)
COT
0.71 (0.62. 0,80)
0.57 (0.47, 0.67)
0.52 (0.42, 0.62)
SYSTEM A
0.84 (0.82. 0.87)
SI
0.88 (0.81. 0.94)
0.51 (0.41. 0.61)
0.45 (0.35, 0.55)
SYSTEM B
0.85 (0.83, 0.87)
SYSTEM A
0.90 (0.84, 0.95)
0.55 (0.45, 0.65)
0.55 (0.45, 0.65)
Table 3: Dev accuracy with 95%
Table 4: Accuracy with 95% bootstrap confidence intervals on PrOntoQA. The "depth" denotes the number of ground-truth reasoning steps.
bootstrap CFs on QASC.
others are negative choices selected by tuned T5.
6.3 LLM Experiments on PrOntoQA
We took the systems trained in section 6.1 and eval- uated them on the Version-I and Version-II of this multiple-choice task: in the Version-II setting, each the- ory has a few distractors, so it is more challenging than Version-I. For each theory, a system tries prove each choice x(e), ranks the four choices by their proof scores J(T, x, ), and then chooses the one with the highest score. The systems were evaluated by accuracy. As shown in Table 2, the systems behave similarly they do on the binary classification: in both Version-I and Version-II settings, System-A and System-B perform significantly better than the baselines, and System-Bi -B significantly outperforms System-A.
We evaluated the L.MM version on the "fictional" version of the PrOntoQA dataset (Saparov and He. 2023). It is binary classification task like Entailment Bank (sec- tion 6.1,, but is more challenging to large language models such GPT-3.5 since its logical statements are about fictional characters (e.g.. wumpus), meaning that a large model can not bypass the reasoning and draw correct conclusions by commonsense or memorization. The main results are shown in Table 4. In all cases, our planning -aaed system outperforms the selection- inference (SI) method, meaning that explicit planning is consistently helpful. In most cases, our planning- based system performs better than the strong chain-of of----ff--ooo thouuhh (COT) prompting. We also experimented with the De- BERTa model tuned on the Entailment Bank training data (sections 3.3 and 6) and found that it couldn't t improve the performance on PrOntoQA. Appendix C.6 includes more details about this set of experiments as well as more results.
We also evaluated GPT-3-davinei with 0-shot, 5-shot, and chain-of-thought (COT) prompting (Brown et al., 2020; Wei et al., 2022). The COT prompts include the ground-truth reasoning paths of the correct choices; examples are in Appendix C.5. Our full system outper- forms 0-shot GPT-3, but underperforms 5-shot and COT GPT-3, Interestingly, O-shot GPT-3 works worse than random guess when theories have distractors, which indicates the difficulty of this problem. addition, we evaluated RuleTaker and Neural Unification, with their numbers of trainable parameters matched with our methods. In the Version-I setting, they both perform worse than our System-B B and Neural Unification per- forms even worse than System-A. A. Interestingly, they seem to be more robust distractors: in the Versition-II setting, Neural Unification performs competitive to our System-B, and RuleTaker performs significantly better than System-B. However, these methods do not generate interpretable reasoning processes.
7 Conclusion
In this paper, we presented LEAP, an LM-based logi- cal reasoning system that integrates explicit planning into the inference method. We also proposed method that learns to prevent the explicit planning from being misguided. Our proposed methods exhibit intriguing technical connections to other reasoning systems and can be likened to the deliberative System 2 in "dual process" theories of reasoning. In our experiments, our planning- based system outperforms strong baseline methods including the selection-inference method and chain-of chain-of-thought thought prompting. We will discuss several ex- citing avenues for further improvements in Appendix A.
6.2 SLM Experiments on QASC
We also trained and evaluated the systems on the QASC dataset (Khot et al., 2020), multiple-choice question answering dataset where each question has eight candi- date answers. Each training QA pair has two premises and deduction, which can be used to train our de- duction model. Each development QA pair has two premises the reasoning system only needs to do step of deduction but no selection. Test QA pairs have no premises given and one has to search through pool of millions of statements to find the relevant premises, which is not the focus of this paper. So we only evalu- ated the systems the development set. The results are in Table 3. Although this data only requires one step of reasoning, the planning-based systems still significantly outperform the base system, suggesting that explicit planning is indeed helpful for LM-based reasoning.
Acknowledgments
This work was supported by research gift to the last author by Adobe Research. We thank the anonymous EMNLP reviewers and meta-reviewer for their construc- tive feedback. We thank our colleagues at UChicago and TTIC for helpful discussion. We also thank Hao Tan at Adobe Research, Yisi Sang at Apple, Benjamin Van Durme at Johns Hopkins University, and David Dohan at OpenAl for their helpful comments.
Limitations
The main limitation of our proposed framework is that requires more computation than the haseline methods that do not perform explicit planning. As discussed in section 3.2, the no-planning methods are like the

---

intuitive and fast System (Evans, 2003) while our methods are like the analytical and slow System 2: after all, more analysis consumes more computation and thus our framework is less energy-efficieen This limitation has inspired us to explore new methods such as bandit learning switch between two types of systems and more efficient planning (see Appendix A).
Proceedings of the Conference of the North Ameri- can Chapter of the Association for Computational Linguistics (NAACL).
Wenhu Chen, Wenhan Xiong. Xifeng Yan, and William Wang- 2018. Variational knowledge graph reasoning. In Proceedings of the Conference of the North Amer- ican Chapter of the Association for Computational Linguistics (NAACL).
Ethics Statement
Zeming Chen, Qiyue Gao, and Lawrence S. Moss. 2021. Neurallogg Natural language inference with joint neural and logical reasoning. In Proceedings of *SEM 2021: The Tenth Joint Conference Lexical and Computational Semantics.
Our work complies with the ACL Ethics Policy. It aims to build more intelligent language-based logical reason- ing systems which would have a broad positive impact to the society. For example, in our daily life, an intelli- gent logical reasoning system may help verify facts and identify fake news; in legal domain, it may work as an automatic paralegal and assist lawyers with their doc- ument processing and decision making; in education, it may help students reason about their mistakes and improve learning experience. Meanwhile, our methods share the same risks as other machine learning methods, such as misusage, containing data bias, and suffering from adversarial attacks. However, this paper is orthog- onal to the research efforts to mitigate these issues.
Peter Clark, Oyvind Tafjord, and Kyle Richardson. 2020. Transformers as soft reasoners over language. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI).
Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Rejichiro Nakano, al. 2021. Training verifiers to solve math word problems. arXiv preprint arXiv:21 1xXiv2210.141666 14168.
William W Cohen, Fan Yang, and Kathryn Rivard Mazaitis. 2017. Tensorlog: Deep learning meets probabilistic dbs. Journal of Artificial Intelligence Research (JAIR).
References
Gabor Angeli, Neha Nayak, and Christopher D. Man- ning. 2016. Combining natural logic and shallow reasoning for question answering. In Proceedings of the Annual Meeting of the Association for Computa- tional Linguistics (ACI.).
Antonia Creswell, Murray Shanahan, and Trina Higgins. 2023. Selection inniiinn-ifeeeece: Exploiting large language models for interpretable logical reasoning. In Pro- ceedings of the International Conference on Learning Representations (ICLR).
Raffaella Anna Bernardi. 2002. Reasoning with polarity in categorial type logic. Ph.D. thesis.
Bhavana Dalvi, Peter Jansen, Oyvind Tafjord, Zheng- nan Xie, Hannah Smith, Leighannaa Pipatanangkura, and Peter Clark. 2021. Explaining answers with en- tailment trees. In Proceedings of the Conference Empirical Methods in Natural Language Processing (EMNLP).
Gregor Betz and Kyle Richardson. 2022. DeepA2: modular framework for deep argument analysis with pretrained neural Text2Text language models. In Proceedings of the I 1th Joint Conference on Lexical and Computational Semantics.
Rajarshi Das, Shehzaad Dhuliawala, Manzil Zaheer, Luke Vilnis, Ishan Durugkar, Akshay Krishnamurthy. Alex Smola, and Andrew McCallum. 2018, Go for walk and arrive the answer: Reasoning over paths in knowledge bases using reinforcement learn- ing. In Proceedings of the International Conference on Learning Representations (ICLR).
Kaj Bostrom, Zayne Sprague, Swarat Chaudhuri, and Greg Durrett. 2022. Natural language deduction through search over statement compositions. In Find- ings of the Conference on Empirical Methods in Nat- ural Language Processing (F (Findings of EMNLP).
Kaj Bostrom, Xinyu Zhao, Swarat Chaudhuri, and Greg Durrett. 2021. Flexible generation of natural lan- guage deductions. In Proceedings of the Conference on Empirical Methods in Natural Language Process- ing (FMNLPP.
David Dohan, Winnie Xu, Aitor Lewkowyez, Jacob Austin, David Bieber, Raphael Gontijo Lopes, Yuhuai Wu, Henryk Michalewski. Rif A Saurous, Jascha Sohl-Dickstein. et al. 2022. Language model cas- cades. arXiv preprint arXiv:2207.100.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neclakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. 2020. Language models are few-shot learners. Advances in Neural Information Processing Systems (NeurIPS).
Jonathan St BT Evans. 2003. In two minds: dual- process accounts of reasoning. Trends in cognitive sciences.
Yao Fu, Hao Peng. Litu Ou, Ashish Sabharwal, and Tushar Khot. 2023. Specializing smaller language models towards multi-step reasoning. In Proceedings of the International Conference on Machine Learning (ICML).
Jifan Chen and Greg Durrett. 2019. Understanding dataset design choices for multi-hop reasoning. In

---

Deepanway Ghosal, Navonil Majumder, Rada Mihal- cea, and Soujanya Poria. 2022. Two is better than many? binary classification as an effective approach to multi-choice question answering. In Proceedings of the Conference on Empirical Methods in Natural Language Processing (EMNLP).
Yinhan Liu, Myle Oit, Naman Goyal, Jingfei Du, Man- dar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer and Veselin Stoyanov. 2019. Roberta: A robustly optimized bert pretraining approach. arXiv preprint 1rXiv:1907.1163.
Ximing Lu, Sean Welleck, Peter West. Liwei Jiang, Jungo Kasai, Daniel Khashabi, Ronan Le Bras, Lian- hui Qin, Youngjae Yu, Rowan 7ellers, Noah A. Smith, and Yejin Choi. 2022a. NeuroLogic a*esque de- coding: Constrained text generation with lookahead heuristics. In Proceedings of the Conference of the North American Chapter of the Association for Com- putational Linguistics (NAACL).
Pengcheng He, Xiaodong Liu, Jianfeng Gao, and Weizhu Chen. 2021. Deberta: Decodiig-eehanced bert with disentangled attention. In Proceedings of the International Conference on Learning Represen- tations (ICIRR).
Hai Hu, Qi Chen, Kyle Richardson, Atreyee Mukher- jee, Lawrence S. Moss, and Sandra Kuebler. 2020. MonaLog: a lightweight system for natural language inference based monotonicity. In Proceedings of the Sociery for Computation in Linguistics.
Xuantao Lu, Jingping Liu, Zhouhong Gu, Hanwen Tong, Chenhao Xie, Junyang Huang, Yanghua Xiao, and Wenguang Wang. 2022b. Parsing natural language into propositional and first-order logic with dual re- inforcement learning, In Proceedings of the 29th International Conference on Computational Linguis- tics.
Daniel Jurafsky and James H. Martin. 2000. Speech and Language Processing: An Introduction to Natu- ral Language Processing. Computational Linguisties. and Speech Recognition.
Zhuang Ma and Michael Collins. 2018. Noise con- trastive estimation and negative sampling for condi- tional models: Consistency and statistical efficiency. In Proceedings of the Conference on Empirical Meth- ods in Natural Language Processing (EMNLP).
Tushar Khot, Peter Clark, Michal Guerquin, Peter Jansen, and Ashish Sabharwal. 2020. Qase: A dataset for question answering via sentence composition. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI).
Bill MacCartney and Christopher D. Manning, 2009. An extended model of natural logic. In Proceedings of the Eight International Conference on Computa- tional Semantics.
Tushar Khot, Daniel Khashabi, Kyle Richardson, Pe- ter Clark, and Ashish Sabharwal. 2021. Text mod- ular networks: Learning to decompose tasks the language of existing models. In Proceedings of the Conference of the North American Chapter of the Association for Computational Linguistics- Human Language Technologies (NAACL HLT).
Sewon Min, Eric Wallace, Sameer Singh, Matt Gardner, Hannaneh Hajishirzi, and Luke Zettlemoyer. 2019. Compositional questions do not necessitate multi-hop reasoning. In Proceedings of the Anmual Meeting of the Association for Computational Linguistics (ACL.).
Diederik P Kingma and Jimmy Ba. 2015. Adam: A method for stochastic optimization. In Proceedings of the International Conference on Learning Repre- sentations (ICLR).
Arvind Neelakantan, Benjamin Roth, and Andrew Mc- Callum. 2015. Compositional vector space models for knowledge base inference. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI).
Ni Lao and William W Cohen. 2010. Relational re- trieval using a combination of path-constrained ran- dom walks. Machine Learning.
Maxwell Nye, Michael Tessler, Josh Tenenbaum, and Brenden M Lake. 2021. Improving coherence and consistency in neural sequence models with dual- system, neuro-symbolic reasoning. In Advances in Neural Information Processing Systems (NeurlPS).
Veronica Latcinnik and Jonathan Berant, 2020. Explain- ing question answering models through text genera- tion. arXiv preprint XXXv:2004.05566
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury. Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein. Luca Antiga, Alban Desmaison, Andreas Kopf. Edward Yang. Zachary Vito, Martin Raison, Alykhan Te- jani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. 2019. Pytorch: An imperative style, high-peeformance deep learning li- brary. In Advances in Neural Information Processing Systems (NeurIPS). Curran Associates, Inc.
Brian Lester, Rami Al-Rfou, and Noah Constant. 2021.
The power of scale for parameter-efficient prompt tun- ing. In Proceedings of the Conference on Empirical Methods in Natural Language Processing (EMNLP).
Oleksii Levkovskyi and Wei Li. 2021. Generating pred- icate logic expressions from natural language. In SoutheastCon.
Tengxiao Liu, Qipeng Guo, Xiangkun Hu, Yue Zhang. Xipeng Qiu, and Zheng Zhang. 2022. RLET: re- inforcement learning based approach for explainable QA with entailment trees. In Proceedings of the Con- ference on Empirical Methods in Natural Language Processing (EMNLP).
Gabriele Picco. Hoang Thanh Lam, Marco Luca Sbodio. and Vanessa Lopez Garcia. 2021. Neural unification for logic reasoning over natural language. In Findings of the Conference on Empirical Methods Natural Language Processing ( (Findings of EMNLP).

---

Colin Raffel, Noam Shazeer, Adam Roberts, Kather- ine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, Peter J Liu, et al. 2020. Exploring the limits of transfer learning with a unified text-to-text transformer. Journal of Machine Learning Research (JMLR).
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Ed Chi, Quoc Le, and Denny Zhou, 2022. Chain of thought prompting elicits reasoning in large language models. Advances in Neural Information Processing Systems (NeurIPS).
Nathaniel Weir and Benjamin Van Durme. 2022. Dy- namic generation of interpretable inference rules in a neuro-symbolic expert system. arXiv preprint arXiv:2209.0766.
Nazneen Fatema Rajani, Bryan McCann, Caiming Xiong, and Richard Socher. 2019. Explain yourself! leveraging language models for commonsense rea- soning. In Proceedings of the Annual Meeting of the Association for Computational Linguistics (ACI.).
Johannes Welbl, Pontus Stenetorp, and Sebastian Riedel. 2018. Constructing Datasets for Multi-hop Read- ing Comprehension Across Documents. Transac- tions of the Association for Computational Linguis- tics (TACL).
Kyle Richardson and Ashish Sabharwal. 2020. What does my QA model know? devising controlled probes using expert knowledge. Transactions of the Associa- tion for Computational Linguistics (TACL).
Adina Williams, Nikita Nangia, and Samuel R. Bow- man. 2018. A broad-coverage challenge corpus for sentence understanding through inference. In Pro- ceedings of the Conference of the North American Chapter of the Association for Computational Lin- guistics - Hummn Language Technologies (NAACL HLT).
Stuart Russell and Peter Norvig. 2010. Artificial Intelli- gence: A Modern Approach. Prentice Hall.
Swarnadeep Saha, Sayan Ghosh, Shashank Srivastava, and Mohit Bansal. 2020. PRover: Proof generation for interpretable reasoning over rules. In Proceedings of the Conference on Empirical Methods in Natural Language Processing (EMNLP).
Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowiez, 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: tfate-of-the-art natural language processing. In Pro- ceedings of the Conference on Empirical Methods in Natural Language Processing (EMNLP).
Abulhair Saparov and He He. 2023, Language models are greedy reasoners: A systematic formal analysis of chain-of-thouuht. In Proceedings of the International Conference on Learning Representations (ICLR).
Vered Shwartz, Peter West, Ronan Le Bras, Chandra Bhagavatula, and Yejin Choi. 2020. Unsupervised commonsense question answering with self-talk. In Proceedings of the Conference on Empirical Methods in Natural Language Processing (EMNLP).
Wenhan Xiong, Thien Hoang, and William Yang Wang. 2017. Deeppath: A reinforcement learning method for knowledge graph reasoning. In Proceedings of the Conference on Empirical Methods in Natural Lan- guage Processing (EMNLP).
Richard S Sutton and Andrew G Barto. 2018, Reinforce- ment learning: An introduction.
Oyvind Tafjord, Bhavana Dalvi, and Peter Clark. 2021. ProofWrite: Generating implications, proofs, and abductive statements over natural language. In Find- ings of the Annual Meeting of the Association for Computational Linguistics (Findings of ACL).
Zhilin Yang. Peng Qi, Saizheng Zhang, Yoshua Bengio, William Cohen, Ruslan Salakhutdinov, and Christo- pher D. Manning. 2018. HotpotQA: A dataset for diverse, explainable multi-hop question answering. In Proceedings of the Conference on Empirical Meth- ods in Natural Language Processing (EMNLP).
Alon Talmor, Oyvind Tafjord, Peter Clark, Yoav Gold- berg, and Jonathan Berant, 2020. Leap-of-thour Teaching pre-trained models to systematically rea- son over implicit knowledge. In Advances in Neural Information Processing Systems (NeurIPS).
Mo Yu, Shiyu Chang, Yang Zhang, and Tommi Jaakkola. 2019. Rethinking cooperative rationalization: Intro- spective extraction and complement control. In Pro- ceedings of the Conference on Empirical Methods in Natural Language Processing (EMNLP).
William Yang Wang, Kathryn Mazaitis, and William w Cohen. 2013. Programming with personalized pager- ank: a locally groundable first-order probabilistic logic. In Proceedings of the ACM International Con- ference on Information & Knowledge Management (CIKM).
Anna Zamansky, Nissim Francez, and Yoad Winter. 2006. A 'natural logic' inferrece system using the lambek calculus. Journal of Logic, Language and Information.
Honghua Zhang, Liunian Harold Li, Tao Meng, Kai-Wei Chang. and Guy Van den Broeck. 2023. On the para- dox of learning to reason from data. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAT).
Leon Weber, Pasquale Minervini, Jannes Münchmeyer, Ulf Leser, and Tim Rocktäschel. 2019. NLProlog: Reasoning with weak unification for question answer- ing in natural language. In Proceedings of the Annual Meeting of the Association for Computational Lin- guistics (ACL).

---

A Future Extensions
Algorithm 1 Reasoning (Inference) with Our System max number of inference steps M; depth of planning 1) (1) = 0 means "no planning") inference beam size Bin
Hyperparam:
Our experiments have inspired us to explore several exciting avenues for further improvements.
The first is to jointly refine the selection, deduction, and verification models. In this paper, we have already shown that adversarially refining the verification model will significantly improve the performance. So a natural next step is to adversarially refine the selection and de- duction models in response to the updated verification model. Allowing components of a system to adversari- ally refine one another has been shown useful in natural
Input: theory T = {xi, X2..... xN} and goal Xoi selection model Psct- deduction model paedi verification model Pver
Output: reasoning path R with proof score f
1: procedure INFERENCE(T, Xu,Psels Psets Pdods Pver)
2: b has access to M, Bur. I)
3: B 3 PriorityQueue[B Bust)
4: & max size is Bud priority is first element of suple
language processing (Yu et al., 2019).
5: B3ddd( (0, 0, T -o0)
The second is to develop implicit planning methods improve inference efficiency. In reinforcement learning,
6: init with empry path and current theory
7:
for m = to M
explicit planning is often only used to help learn a value function during training: during inference, calling value function is like planning implicitly but faster than explicit planning. This kind of methods can apply to our setting. Another way to improve efficiency is to Iearn bandit that could cleverly switch between the no- planning "Systtm I" and our planning -based "System 2" such that we only spend more computation in the more difficult cases.
8:
b do inference at each step
9:
A selection at step m
10:
Bold + B; B 4- PriorityQuene (ims)
11:
for go. Rs. To. Jo in Bota
12:
9 is log-prob of path and f is its proof score
13:
S. + SELECT Xo, Psa))
14:
if 1) > 0:
15:
> rank selections bused on D-step roll-outs
16:
S, + PLANS(TT. Xo, So. bsots Pradd Pues)
Another direction is to leverage unlabeled data, i.e., data without human- aanuunttd reasoning paths. Such data is less expensive to collect. An LM-based reasoning system may be able to benefit from (the indirect training signals of) such data by self-supervised learning.
17:
for Sg.Sk, in Sp:
18:
b. add expanded path into priority queue priority score changes by uu:
19:
20:
B. add((g) + Uk. R2 + {sx } Tos fo))
21:
B has a fixed size Bug: if [3) > Hut auto-delete lowest-priorts element
B Method Details
22:
23:
b deduction at step m
In this section, we give details of our methods.
24: Bosa + B; B + PriorityQueue (ms))
25:
for gb. Rs, Th, fo in Bold
B.1 Reasoning Process Details
26:
8, +- the most recent selection in Rs V/ + DEDUCE((S,, Pdea)
Algorithm gives a detailed explanation for how our inference method works. When D = 0, it is the naive method. When D 2 1, it is the inference with explicit planning. During selection, we constrain the model to only select two premises for more controllable behav-
27:
if D > 0:
29:
> rank deductions based D-step roll-outs
30:
3/- + PLAND((T. Xo, Vo.Poel: Poel: Pdeds Pver)
31:
for ok y4 in 31.
ior. When we compute the proof score we only consider
32:
B.add Uuk RR +yy To Hy fo))
the newly generated deductions for convenience. Its effect to results is negligible since later deductions tend to more directly prove the goal.
33:
for go. Rs, To, fo in B
34:
Yn + the most recent deduction in Rs
35:
if y, entails xa better than any prev deduction update proof score of path Rs if Pooe yo) > So : Jo <- Pve(XXo Y choose reasoning path with highest proof score
Algorithm is designed select set of statements
36:
from the current theory T, with the goal of inferring Xp.
37:
We the size of the selection set to 2 in our experi-
ments, but in principle this restriction can be removed.
38:
Algorithm draws Bast new deductions. Their SLM versions are Algorithms and 6 and the LLM versions are Algorithms 8 and 9.
39: Dmux +- argmax,, Jo
return Rimwn fown
Padl A.l%)
B.2 Details of Tuning the Verification Model
We use the soft prompt tuning method (Lester et al., 2021): augment the input with few special tokens and the only trainable parameters are the embeddings of those tokens; it is illustrated in Figure 7.
pretrained DeBERTa with classiication head
VER special tokens trainable embeddiigg: VER
CLS
Eagles only animals. Eagles carnivores.
Where do we get Xu. y. Xo. and y? Recall that we have a training corpus of theories and goals as well
Figure 7: The structure of the verification model.

---

as their ground-truth reasoning paths. For each pair of theory 7 and provable goal Xa. we could randomly sample deduction y from its ground-truth reasoning path. We use the goal of another training example as our non- pon-provable goal Xg. call the planning -based inference method get reasoning path, and sample deduction from the reasoning path as our y.
Algorithm 2 Selection Subroutine
Hyperparam: selection beam size Biel
Input: current theory T =xx1.... (XI....,XN...... XN+mm and goal Xo; selection model Prel
Algorithm shows how we refine the verification
model using the contrastive loss with regularization.
Output: selections with their scores (14,,s))
1: procedure SELECT(T, No, Poe)
Algorithm 4 Refining Verification Model
Di generic method for illustration only
3: > in pructice, we call the SLM or LLM version
Input: provable goal X and gold reasoning path R; non-provable goal Xy and model-generated path R: verification model Pver
see Algorithm 5 for SLM version
5: b see Algorithm 8 for LLM version
has access to Bun
Output: updated verification model pver procedure REFINE(Xo: R, R. Pver)
7: return list S which contains Bui scored selections
8: b each scored selection is (2,8)
2: D refining procedure
ycore is defined in section 3.2
3: Pier + copy pretrained pver
10: return S
4: sample deductions from reasoning paths
11: procedure ONEBESTSELECT(T Xa- Pret)
5: randomly draw from deductions in R
6: randomly draw y from deductions in R.
12:
only keeps selection with highest score
13:
S + SELECT(T, Xo. Pset)
7: refine verification model
14:
(u,s) +- highest-scored element
8: E + LOSS VER(XD. y P.eer Pver)
9: compute V wrt. trainable parameters Over of Pver
15: return
10: update Over with chosen optimization method
11: return Pver
12: procedure LOSS y. NoN F, Pver P
13:
D. contrastive loss
14: l f log pun Pe
(8al))
15: b compute regularization
f- Pver (Xo y)log Prer ly)
17:
e- (1 Pver y)) log(1 Pver (No x))
18: return l
Algorithm 3 Deduction Subroutine
Hyperparam: deduction beam size Baod
B.3 SLM Details
Input: current selection s of statements; deduction model Pded
We give SLM details in this section.
Output: deductions with their scores {(1),
Selection model. The selection model Peel pretrained encoder-decoder model T5 (Raffel et al., 2020). The encoder reads a context string concatenat- ing the goal and the premises ,Ny of cur- rent theory T; the decoder computes the probabilities (x,, x,) that each premise x,, is selected in the attempt to prove the goal It is illustrated in Fig- ure 4a: besides the statements, T5 also reads few special tokens (ENC, SP,, SP1, 1,,.... SPx, DEC); its de- coder gives a hidden state h, which is involved in com- puting (x, T, T,x;) de o(h w,, where w,, is the embedding of SP,, For training and inference efficiency, we keep the pretrained T5 frozen so the only trainable parameters of the selection model Psel denoteeotedl as O.et are the embeddings the special tokens. The pseu- docode of using for inference in Algorithm 5.
procedure DEDUCE(S, paea)
generic method for illastration only 3: b in practice, we call the SLM or LLM version
see Algorithm 6 for SLM version
5: see Algorithm 9 for L.L version
6: I has access to Bas
list which contains Bus scored deductions
8: D each scored deduction is (v,y)
9: I- score is defined in section 3.2
10: return y
11: procedure ONEBESTDEDUCELS Pasa)
12:
D only keeps deduction with highest score
13:
y DEDUCE(S, Pasa)
14:
(v.y) element in y with highest
15:
return
Deduction model. Given the selection the deduc- tion model Pdad produces a logical deduction y by com- bining the premises in The new statement y is added to the theory T whose size is then increased by one;

---

therefore, for theory of size N, we also denote as XN+1. The deduction model Paed uses another pre- trained Ts. As shown in Figure 4b, its encoder reads imput string concatenating the selected premises along with few special tokens; its autoregressive decoder pro- duces deduction one token after another. Its trainable parameters ded are the embeddings of the special to- kens. The pseudocode of deploying it Algorithm
Algorithm 5 Selection Subroutine for SLM
Algorithm Training for SLM
Hyperparam: selection beam size Byd
Input: theory T ......, XN) and goal xo: reasoning path R2 verification model Pver selection model Psels deduction model Pied
Input: current theory T = {x1....> , XN++m and goal Xg. prompted encoder-decoder language model Psel
Output: selections with their scores 8x))
Output: updated models Peel and Past
1: procedure SELECT(T, -.oPsse)
1: procedure TRAIN(R, T, Xgy Psel: Pasts Pver)
hus accexs But
2: D training method for selection and deduction models
3: b build context by concatenating hypothesis and theory
3: b init extended theory that will include deduction
4: c e= -S to
+SP N mmm+X +-m
4:
<
5: for i to N m
5:
for
/2|/2:
6:
compute prob that each statement is selected
6:
i loop each step of selection and deduction
P: + PSP
7:
Sy + m selection i.e. (2m 1) entry in R. Yn mh deduction ie., (2m)* element in
8: S + PriorityQueue Baa)
8:
9: max size is Bus priority first element of tuple
9:
b train selection model
i LOSSSEL(T (T.SSELLT.smn... S.n Pset)
10: for i 1 to N m
11:
for j = = 1 to N mm:
11:
compute V wrt. trainable params Ost of Pset update Osel with chosen optimization method
12:
S f xx
12:
13:
UA < log Exfreos log(1 -pe)
P train deduction model
14:
[add((u,,
14:
E E LOSSDED 8m V
15:
B larger than Bas, element with
15:
compute V wrt. trainable params ded of pded update Paad with chosen optimization method
16:
b lowest priority will be automatically deleted
17:
return S
17:
D extend theory with new deduction
- T- + m
19:
return Pset- Poed
Algorithm 6 Deduction Subroutine for SLM
20: procedure LOSSSEL(T , Psel)
Hyperparam: deduction beam size Baed Input: current selection s of statements; prompted encoder-decoder language model Paed
21:
b construct context for selecting statements from theory SP N +X
23:
é + 0 loss is negative log-tikelühood of selection
Output: deductions with their scores {())
24:
for = 1 N m
p. + Peel (SP.cc) prob xs included
1: procedure DEDUCE(S, paed)
26:
if in Ae t- log pi else At +- -log(1 - pt)
2: has
Bud
3: b has uccess standard beam search implementation
27:
f f-(- f- Ae t- update with minus log- probability
y +- BEAMSEARCH(Pad Basd. 8)
28:
return
5:
procedure LOSsDED(s.)) Y, Paed)
6: & BEAMSEARCH gives a list of tuples (Ve.
30: b loss negative log log-prob of deduction under model
text string ys sorted in descending order of
31:
( Paeayy |s)
8: return }
b log para(y s) sums jug-probubilities of tokens
33: return l
Training. Algorithm elaborates how the SLM selec- tion and deduction models are trained. We use prompt- learning because we do not want to distort the pretrained weights too much. is well known that pretrained lan- guage models have already captured substantial amounts of commonsense knowledge such as hypernymy (A is a type B) and meronymy (A is part of B) (Richard- and Sabharwal, 2020); we would like keep such knowledge to benefit our settings.

---

B.4 L.M Details
We give LLM details in this section, For selection, we use large language model black box and prompt it to choose several different multi-pre multi-premise selections from the given theory T. The pseudocode in Algo- rithm& Below is the prompt template:
Algorithm 9 Deduction Subroutine for LLM
Hyperparam: deduction beam size Bied Input: current selection s of statements; deduction model Pded
few-shot examples to demonstrate selection see Appendix C.6 for an example
Output: deductions with their scores Na))
procedure DEDUCE(S, Paed)
2: D has access to Bas
3: prompt LLM to draw Bast new deductions
4: prompt templates
Appendix B.4
end of demonstration
5: each deduction is assigned score v = 0
Please refer to these examples, select four pairs of indexes from the theory (e.g. 12 and 3 / and 6 / 12 and / 12 and 11) that can potentially help us ansver the question, no need to say anything else.
6:
construct list y to contain multiple (v:y)
7: return
You must choose four pairs even if there are no valid selections.
theory and question/goal of intereat
Algorithm Planning for Selection
For deduction, we also use a large language model as black box and prompt it to draw new deductions conditioned on given selection The pseudocode is in A Algorithm 9. The prompt template is as follows:
Hyperparam: deduction beam width Baed;
depth of planning 1); planning scale a
Input: current theory [x1...., "x1....,XN--a.. XN+m } and goal Xot verification model Pver
few-shot examples to demonstrate deduction Appendix C.6 for example
selection candidates at current ster S = ((u,, 8k)]: selection model peet and deduction model pdad
Output: selections with updated scores {(ux.
1: procedure PLANS(T, Xp. S. Pacls Paeds Pvec)
2: access to Buds
end of demonstration
3: P init hypotheticul extended theory
4: for uge Sy. S:
Please refer to these examples and generate the inference.
5: for ug, Sk in S
6: b iterate over all candidate selections
selection of statements of interest
7:
b find hypothetical next-step deduction
8:
YA < ANEBESTDEDUCEL
Paet)
Algorithm 8 Selection Subroutine for LLM
9:
extend theory with deduction
10:
Th T {
Hyperparam: selection beam size Bael
b planning with roll-outs
Input: current theory T (xI...., XN and goal
12:
what's 's given by ROLLOUT Au in section 3.2
Xo: selection model Psel
13:
WK <- + a ROLLOUT
Output: selections with their scores S1))
14: sort S in descending order of updated
procedure SELECT(T, No,
return
2: D has access B..i
procedure ROLLOUT
3: prompt LLM to select Bul different multi-
17:
b roll oud D steps of imaginary selection and deduction
premise selections from the theory T
D make in-place edits to Sk. Yv. Ts
4: I prompt templates are in Appendix B.4
each selection is assigned score u =
19:
inil score of roll-ow
6: construct list S to contain the multiple (u,
20:
for to D
b step-by-step roll-out
š ONEBESTSELECT (Tr, Xu. Psat)
7: return S
22:
シµ <- ONEBESTDEDUCC Pdet)
23:
TA + T (f+)
B.5 Details of Planning-Batee Based Methods
24:
if Preer 181) f:f < Pver Pxe 18))
25: return log
Algorithm 10 illustrates the details of how we use ex- plicit planning for selection. The method considers how each selection could affect future in D steps. One-best search is applied in the roll-out process to simplify the

---

Algorithm 11 Planning for Deduction
verification model. Note that for T5 models, the prompt is added to the beginning of both the encoder and the decoder (weight not shared). For the selection model, layernorm is added before the sigmoid operation.
Hyperparam:
deduction beam width Buedi depth of planning 1); planning scale 8
Input: current theory T = (x1...,, +m } and goal Xo; deduction candidates at current step y = {x)); selection model Psol and deduction model Pded; verification model pver
In training. we use the Adam (Kingma and Ba, 2015) optimizer with {1 0.9, B2 0.999, < Ie S O. We use learning rate 7 = 0.1 for the T5 models, and = 0.01 for the verification model. We use a batch size of 16. We set very large epoch number like 1000 and use the validation set to do early stopping. In practice, the best epoch is often within 100.
Output: deductions with updated scores {(Uk, Yx))
1: procedure PL.AND(T, Xx, Y: Psct Pact Poer)
2: D. has access to Bus. D.5 3
>> init hypothetical extended theory
4: for Uk: yx in ; Ts t- T
For LLM experiments, provided by OpenAI. We set the temperature to reduce randomness. We keep the default role "system" with the message "You are an Al assistant that speaks English." We used a fixed random seed for all our data gen- eration and training, reproduced with our codes.
use GPT-3.5-turbo model
for 2k, Vx in y
6: D iterate over all candidate deductions
7: Tx - Tx + {y&} extend theory with deduction
8: vk < uk + 3 ROLLOOUT
that results can be easily
9:
ROLLOUT is in Algoritium 10
10: what's given by ROLLOUT is Au in section 3.2
During inference, we set B Bad and retain the selections formed by 4 top-scored statements. We set a = 10 and 3 = 0.5 to roughly match the scale of the beam score. We roll out steps for selection and 2 steps for deduction. We set the maximum step to be M = 20.
11: sort y in descending order of updated vk return y
12:
planning. Intuitively, higher log f means that the fu- ture reasoning path conditioned on this selection is more likely to prove the goal. Similar to Algorithm 10, Algo- rithm 11 measures how the newly generated deduction could affect the future reasoning path in 1) steps, and honors the deduction which improves the possibility of proving the goal in the future.
We do not tune hyperparameters except the learning rate, and we only tune it in our first training of every model. We try [0.1, 0.01, 0.001, 0.0001] and choose the one that yields the best dev set performance.
Our experiments were run on 8 A6000 GPUs. Train- ing takes about hour. Time for inference discussed in section 6.1.
C Experiment Details
C.3 Details of FOL Translations
We present experiment details in this section.
The classical approach of logical reasoning is to use formal logic systems. So we also evaluated the perfor- mance of a first-order-loiic (FOL) system. Because the Entailment Bank dataset does not have human- annotated FOL translations for the natural language statements, we translated all the statements into FOL expressions using a T5 model trained on the corpus of (natural language, FOL) pairs collected by Levkovskyi and Li (2021), and then used FOL, engine perform reasoning. This approach failed because the FOL translations are mostly of very poor quality. Here is summary of the errors:
C.I Data Statistics
The data statistics of Entailment Bank is shown in Ta- ble 5. In Version-I of Entailment Bank, there is one sample in the test set that has theory with single statement. We ignore this sample since can not be dealt by our system in the normal way. The dataset can be downloaded from https://allena. irtpaniii.og///teaeeeeeeee / entai lmeenank.
SPLIT # OF SAMPLES
MAX STEPS
AVG STEPS
TRAIN
1313
17
3.2
inconsistency in variable naming. The FOL transla- tions often use inconsistent variable naming, making it difficult to pattern-match relevant expressions.
DEV
187
15
3.2
TEST
340
11
3.3
Table 5: Data statistics of Entailment Bank.
incorrect translations. Some FOL translations inaccu- rately represent the original sentences, resulting a failure to capture the intended meaning. For example, "driving is kind of skill" is incorrectly translated into "Ir. (dr.viiiigg(())) & by (cchicley))kndle v))).
C.2 Hyperparameters
For SLM experiments, we use "t5-small" in the Hug- gingface transformers (Wolf et al., 2020) library for the selection and deduction models. We use "deberta-v?" v2- xlarge-mnli" for the verification model. We prompt tune these models, with prompt length of 4 for the selection and deduction models, and a prompt length of 32 for the
syntax errors. Some FOL translations contain syntax emorr, making them difficult to be process.
missing incomplete information. In several in- stances, the FOL translations do not capture all rel-

---

Sprane
(a) ROC curves.
(b) Acc curves on positive examples.
(c) Acc curves negative examples.
Figure 8: Test results with 95% bootstrap CFs on Entailment Bank Version-I under 50% training data.
METHOD
AUROC
AUACC
AUACC
F1
BASE SYSTEM (TS-BASE)
0.73 (0.69, 0.77)
0.61 (0.56, 0.65)
0.81 (0.79, 0.84)
0.68 (0.66, 0.71)
SYSTEM A (TS-BASE)
0.91 (0.89, 0.93)
0.90 (0.88, 0.92)
0.62 (0.58, 0.65)
0.85 (0.83, 0.87)
SYSTEM B (15-BASE)
0.94 (0.93, 0.96)
0.89 (0.87, 0.91)
0.84 (0.80, 0.87)
0.90 (0.88, 0.91)
BASE SYSTEM (DENOISE)
0.55 (0.50, 0.59)
0.39 (0.35, 0.43)
(0.80. 0.85)
0.67 (0.67, 0.67)
SYSTEM A (DENOIE))
0.88 (0.85, 0.90)
0.87 (0.85, 0.89)
0.55 (0.52, 0.59)
0.83 (0.81, 0.85)
SYSTEM B (DENOISE)
0.93 (0.91. 0.95)
(0.80, 0.86)
(0.85, 0.90)
0.85 (0.84, 0.86)
Table 6: Test results with 95% bootstrap CTs on Entailment Bank Version-I.
METHOD
VERSION-1
VERSION-II
BASE SYSTEM (T5-BASE)
0.65 (0.60, 0.70)
0.26 (0.22, 0.31)
SYSTEM A (I5-BASE)
0.88 (0.85, 0.91)
0.45 (0.39 .0.50)
SYSTEM B (T5-BASE)
0.91 (0.88, 0.94)
0.55 (0.50, 0.60)
BASE SYSTEM (DENOISE)
0.46 (0.40, 0.52)
0.27 (0.22, 0.32)
SYSTEM (DENOISE)
0.83 (0.80, 0.87)
0.40 (0.35, 0.46)
SYSTEM (DENOISE)
0.90 (0.87, 0.93)
0.67 (0.62,0.72)
BASE SYSTEM (VERSION-II)
0.49 (0.44, 0.54)
SYSTEM A (VERSION-II)
0.73 (0.69, 0.78)
SYSTEM B (VERSION-IT)
0.80 (0. 76, 0.84)
Table Test accuracy with 95% bootstrap CFs in multiple-choice QA. A random guess gives 25% accuracy. The systems in the third block were trained on Version-ll training data.
evant information from the original sentences. For example, it may leave out an entity or quantifier.
diurnal motion when objects in the sky appear to move due to earth 's rotation on its axis.
stare appear to move relative to the horizon during the night.
This analysis reveals fundamental need for tools that work directly with natural language statements for rea- soning like ours.
Which the following conclusions can be inferred?
C.4 Results of A Ablation Studies
0. earth rotating on its axis causes horizon of stars and night on earth.
Figure shows the results the systems trained on 50% training data. Some results of ablation studies described in section 6, are shown in Table and Table 7.
1. earth 's horizon on its rotating aris causes stars to occur in new york night.
2. the earth revolving around the axis causea stars to appear in different night in the sky at different horizon of year.
C.5 Examples of Prompts for GPT-3
3. the earth rotating on its axis causes stars to appear to nove relative to the horizon during the night.
In section 6.1, used three kinds of prompts for GPT- 3: O-shot, 5-shot and COT. In this section, we provide some examples of these prompts.
A: 3.
An in-context demonstration
For COT prompting, used the ground-truth reason- ing path for the correct choice as the "chain-of-thouge" so the last line of the (say) above example will be:
Based on the statementa that:
the earth rotating on its axis causea stars the moon to appear to move across the sky at night.
Reason: diurnal motion is when objecta in the

---

METHOD
DEPTH=1
DEPTH=3
DEPTH=5
SYSTEM A WITH MODIFIED PROOF SCORE
0.90 (0.84, 0.95)
0.55 (0.45, 0.65)
0.55 (0.45, 0.65)
SYSTEM A WITH ORIGINAL PROOF SCORE
0.85 (0.78. 0.92)
0.64 (0.54, 0.74)
0.5 (0.41. 0.6)
SYSTEM B TRAINED ON ENTAILMENT BANK
0.87 (0.80, 0.94)
0.54 (0.44, 0.64)
0.46 (0.36, 0.56)
Table 8: Results of ablation studies PrOntoQA with 95% bootstrap CFs.
aky appear to move due to earth 'a rotation on its axis & stars appear to move relative to the horizon during the night -> int1: stars appearing to nove relative to the horizon during the night is an example of diurnal motion; int1 & the earth rotating on
Contexta:
O. Evvrry tumpus is not earthy.
1. Wumpuses are not red.
2. Numpuses are vumpuses.
3. Each vumpus is bitter.
4. Vumpuses are zumpuses.
its axis causes stars / the moon to appear to
5. Every zumpus is cold.
move across the sky at night -> the earth rotating its axis causes stars to appear to move relative to the horizon during the night.
6. Zumpuses are numpuses.
7. Numpuses are aggressive.
8. Numpuses are dumpuses.
9. Dumpuses are opaque.
10. Dumpuses are yumpusea.
A:3.
11. Yumpuses are not small.
Each yumpus is rompus.
C.6 Experiment Details on PrOntoQA
13. Every rompus is earthy.
Bach rompus is a jompus.
The PrOntoQA data has three subsets of different "depths". The "depth" denotes the number of ground- truth reasoning steps so a "deeper" subset harder. For each depth, we draw (using the released data generation code of Saparov and Hc (2023)) training examples and 100 test examples.
15. Jompuses are metallic.
16. Each jompus is impus.
17. Alex is a dumpus.
Question:True or false: Alex not earthy.
Selection:17 and 17 and 15.
and 17 and 13
For the experiments PrOntoQA, our final verifica- tion is performed by a few-shot-prompted GPT-3.5: it reads the extended theory and judges whether the given goal is proved. By doing this, we do not need to tune a threshold for the proof scores given by the verification model (although those scores still very important in the process of explicit planning). In this dataset, the non-provable goals are often definitively disapprovable. So would like the explicit planning to favor not only the future steps that have large proof scores but also those of large contradiction scores. Therefore, we re- place the proof score in the planning procedure by the generalized score defined below
Alex is dumpus and dumpuses yumpuses. Alex is dumpus and wumpuses are not red. Alex is dumpus and every rompus is earthy.
Alex is dumpus and jompuses are metallic.
An in-context example for deduction prompt is
We know that: Sally is a tumpus and each tumpus is hot. Inference: Sally is hot.
Note that didn't let GPT to propose multiple de- ductions in this experiment because the no-planning deduction is almost always correct long as the selec- tion is correct.
((T xo) max max(pver Xx):Peon(E (xp xx))
(4)
x.. the probability of "x,, contra- dicts xo" given by the pretrained DeBERTa. Table 8 shows how much this modification helps: if we do not use g. the average performance doesn't change but will suffer higher variance. Table 8 also shows the results of using System trained on Entailment Bank data. We did this to see if the verification model could generalize to out-of-domain data. In this experiment. it hurts the performance.
where Peon (Xo
In this section, we also show the prompts for GPT-3.5 used in the experiments in section 6.3. For selection and deduction, employed 5-shot prompting enhance the model's comprehension. An in-context training ex- ample for 5-shot selection prompt is


Reviews:
[{"review_id": "Nx2W4ShVJk", "reviewer": "Reviewer_u2em", "summary": "", "questions": "Question A: Have you compared your method with the state-of-the-art of each dataset? with other planning strategies?\n\nQuestion B: How did you choose the buffer size B for beam search? Does the number of ongoing paths has an impact on the performance?", "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": "Thank you for your constructive feedback and being supportive! \n\n> The paper contains many references to the appendix as it contains important results that should be in the main paper, including a part of the conclusion. The back and forth while reading can be detrimental to comprehension. Fortunately, the information needed to understand the method and assess the claim is in the main content.\n\nWe agree with you! \n\nThe submitted 8-page version was rather compressed. After submission, we continued to revise it for clarity and completeness, making full use of the extra page in the main text that is allowed by camera-ready. In camera-ready, we will take your suggestions as much as possible, bringing important materials back to the main text. \n\n> It would be great to include a comparison with the state-of-the-art for each dataset beyond the single GPT-3.5. \n> Have you compared your method with the state-of-the-art of each dataset? \n\nMost state-of-the-art methods on each dataset are not directly comparable. However, per your request, we ran new experiments, comparing against several methods that seem to be close to what may be in your mind. \n\n[New Results]\n\nThe first is RuleTaker: Clark et al. IJCAI 2020. It is a discriminative method, training a RoBerta to perform logical reasoning as binary classification (provable or not), without spelling out the reasoning process. On Entailment Bank Version-I: \n- it gets 0.84 F1 on the binary classification task; \n- it gets 0.83 accuracy on the multiple-choice QA task. \n\nThis performance is better than System-A but worse than System-B. (Though System-A provides an interpretable reasoning path.) \n\nWe also evaluated this new baseline on QASC (like Ghosal et al. EMNLP 2022, whose setting is moderately different). QASC only requires one-step reasoning, so this discriminative baseline gets 0.96 accuracy, better than all our systems. This is consistent with findings of Clark et al. 2020 and Zhang et al. 2023: Transformers work well as soft reasoners for shallow reasoning, but tend to suffer for deep reasoning. However, this is orthogonal to our main claim (i.e., explicit planning helps). \n\nWe have also experimented with Neural Unification (Picco et al. EMNLP 2021). But this experiment can not be finished by August 29. We expect to finish it by the end of the author-reviewer discussion period, and will post the results via Official Comments as soon as possible.  \n\nReferences: \n\nClark et al. IJCAI 2020, https://arxiv.org/abs/2002.05867 \n\nGhosal et al. EMNLP 2022, https://arxiv.org/abs/2210.16495 \n\nZhang et al. IJCAI 2023, https://arxiv.org/abs/2205.11502 \n\nPicco et al. EMNLP 2021, https://arxiv.org/abs/2109.08460 \n\n[About State-of-the-Art] \n\nPrOntoQA is a new dataset designed to challenge LLMs, and GPT-3.5 with CoT is a very strong baseline, if not state-of-the-art, on this data. \n\nThe original problem settings of Entailment Bank and QASC are different from ours, and thus the state-of-the-art methods on them are not directly applicable. \n\nThe original Entailment Bank only has positive <theory, goal> pairs (i.e., goal is always provable given theory), because it was proposed to train and evaluate methods that generate proofs for provable goals. In our problem setting, one has to determine whether a goal is provable, which is out of the scope of state-of-the-art methods on this data. \n\nQASC was initially to evaluate whether one could retrieve most relevant premises for a given goal as well as whether one could determine the truth value of a goal given the retrieval. The second subtask is similar to our problem, but the state-of-the-art methods on QASC all focus on optimizing for the first subtask, which is more of a bottleneck for the overall performance. \n\n> Further comparison with other planning methods, such as those mentioned in the related work, might be interesting (as far as I understand, the only comparison is with the work of [Creswell et al., 2023]). \n> with other planning strategies? \n\nWe are sorry that our current presentation has misled you: none of the methods mentioned in Related Work performs planning. \nBostrom et al. 2022 is similar to the SLM version of our no-planning base system. \nCreswell et al. 2023 is similar to the LLM version of our no-planning base system. \nWe will clarify it in the camera-ready. \n\n> How did you choose the buffer size B for beam search? Does the number of ongoing paths have an impact on the performance? \n\nA beam size of 5 is a common choice in text generation, so we adopted this convention and didn't tune it at all. \nPer your request, we tried B = 2, 3, 10 on Entailment Bank and found that: \n- a smaller B tends to decrease the accuracy on positive samples, but increase it on negative samples. \n- a larger B tends to increase the accuracy on positive samples, but decreases it on negative samples. \n- either way, the accuracy changes are small. \n- overall, we only see tiny changes in AUROC (which depends on accuracy on both positive and negative samples).", "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 presented is of high quality. The paper is easy to read and the ideas are explained in a clear way. All the necessary information to understand the method is provided.\n\nThe proposed method is particularly interesting and promising for tackling challenging planning and reasoning tasks, in particular the fact that the algorithm is model-agnostic and can be integrated with other LMs. The authors provide very extensive experiments demonstrating the quality of their method. The various ablation studies also clearly identify the proposed systems A and B as the reasons for the improved performance, highlighting precisely the contributions of each system.", "reasons_to_reject": "The paper contains many references to the appendix as it contains important results that should be in the main paper, including a part of the conclusion. The back and forth while reading can be detrimental to comprehension. Fortunately, the information needed to understand the method and assess the claim is in the main content.\n\nWhile the experiments are extensive, there is little comparison with existing methods. It would be great to include a comparison with the state-of-the-art for each dataset beyond the single GPT-3.5. Further comparison with other planning methods, such as those mentioned in the related work, might be interesting (as far as I understand, the only comparison is with the work of [Creswell et al., 2023]).", "questions_to_authors": "Question A: Have you compared your method with the state-of-the-art of each dataset? with other planning strategies?\n\nQuestion B: How did you choose the buffer size B for beam search? Does the number of ongoing paths has an impact on the performance?", "paper_topic_and_main_contributions": "The paper presents a method for performing multi-step logical reasoning via planning. The method uses language models to construct and evaluate reasoning paths. The models are trained using a planning strategy that looks at future predictions and integrates the results into the score of past predictions to teach them to look ahead. Contrastive training is used to learn to score good and bad reasoning paths. The proposed method outperforms the baselines and achieves similar results to larger models.", "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": {}}, {"review_id": "kggjBSDaju", "reviewer": "Reviewer_Mxjp", "summary": "", "questions": "1. the authors should consider improving figure 1.  The figure basically looks the same as the selection-inference paper. Personally, I didn't get anything out from figure 1.", "limitations": "", "rating": 4, "confidence": 3, "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": "Thank you for your constructive feedback and being supportive! \n\nThe submitted 8-page version was rather compressed. After submission, we continued to revise it for clarity and completeness, making full use of the extra page in the main text that is allowed by camera-ready. In camera-ready, we will take your suggestions as much as possible. \n\n> The writing and presentation of the paper can be improved. I didn't have any idea of the method until I really read through the method section. The paper would benefit from first giving a high-level overview of the method at the beginning of the paper than just saying they do planning. \n\nThis is a great suggestion. Thank you! \n\nSpecifically, we plan to extend the first paragraph of Introduction, briefly describing the architecture of our full system and explaining how planning is integrated. Then, what follows is the paragraph of \"Why planning?\". \n\n> the authors should consider improving figure 1. The figure basically looks the same as the selection-inference paper. Personally, I didn't get anything out from figure 1. \n\nWe will improve Figure 1. \n\nInitially, we aim to use Figure 1 to illustrate the problem and how a human may solve it. It looks like Creswell et al. 2023 (selection-inference) because that method was inspired by the human reasoning process as well. The text about \"human reasoning\" was deleted when we were trying to fit our paper (which has a lot of materials) into an 8-page submission. With the extra page allowed by camera-ready, we could easily add the relevant content back and make the figure more useful. \n\nIn addition, we will explore ways to add ingredients into the figure, enabling it to show how our planning-based framework works. This may make it more useful. Before submission, we tried a few ways but they all looked cluttered. Then we decided to break the cluttered figure to Figure 1 (which illustrates the problem) and Figure 2 (which illustrates planning). But there should be ways to extend Figure 1 to show planning on a higher level than Figure 2.", "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 method makes an interesting connection between logical reasoning and planning / contrastive learning\n2. The empirical results are pretty strong - small models can match the performance of GPT-3", "reasons_to_reject": "1. The writing and presentation of the paper can be improved.  I didn't have any idea of the method until I really read through the method section.  The paper would benefit from first giving a high-level overview of the method at the beginning of the paper than just saying they do planning.\n2. The method is quite complex, making people question whether this can really be deployed in the real-world. However, I still think there is value in studying this.  Not too much of a concern for me.", "questions_to_authors": "1. the authors should consider improving figure 1.  The figure basically looks the same as the selection-inference paper. Personally, I didn't get anything out from figure 1.", "paper_topic_and_main_contributions": "This paper proposes a method that perform multi-step logical reasoning by employing explicit planning into its inference procedure. The system significantly outperforms other competing methods on EntailmentBank and QASC. The authors also propose a training strategy that safeguards the planning process from being led astray by spurious features. Extensive empirical studies demonstrate that explicit planning plays an important role in the system's performance.", "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": {}, "extra_text": {}}, {"review_id": "VO4x9DK0Pr", "reviewer": "Reviewer_661C", "summary": "", "questions": "A. In analysis-II, what is the data that supports the claim that “without Ω, System-B 602 performs worse than System-A”?\n\nB. Figure 1:Can you explain why each deduction step (e.g., x2x3->x5) is valid? It seems none of these are actually deductions. \n\nC. Compared to baseline methods, how much more computation does this method cost?", "limitations": "", "rating": 4, "confidence": 3, "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": "Thank you for your detailed and constructive feedback! Your comments are valuable for us to improve the paper. \n\nThe submitted 8-page version was rather compressed. After submission, we continued to revise it for clarity and completeness, making full use of the extra page in the main text that is allowed by camera-ready. In camera-ready, we will take your suggestions as much as possible, bringing important materials back to the main text. \n\n**About Reasons To Reject**\n\n> The baselines methods are limited. For small models, the method is based on tuning, so comparing to prompted GPT-3.5 is not convincing. Instead, the paper may include some tuning baselines for deductive reasoning like RuleTaker [1] and Neural Unification [2].\n> [1] Peter Clark, Oyvind Tafjord, and Kyle Richardson. 2021. Transformers as soft reasoners over language. In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence (IJCAI'20). Article 537, 3882–3890.\n> [2] Gabriele Picco, Thanh Lam Hoang, Marco Luca Sbodio, and Vanessa Lopez. 2021. Neural Unification for Logic Reasoning over Natural Language. In Findings of the Association for Computational Linguistics: EMNLP 2021, pages 3939–3950, Punta Cana, Dominican Republic. Association for Computational Linguistics. \n\nWe ran new experiments for you! We will add them into camera-ready. \n\nRuleTaker trains a RoBerta to perform logical reasoning as binary classification (provable or not), without spelling out the reasoning process. On Entailment Bank Version-I: \n- it gets 0.84 F1 on the binary classification task; \n- it gets 0.83 accuracy on the multiple-choice QA task. \n\nThis performance is better than System-A but worse than System-B. (Though System-A provides an interpretable reasoning path.) \n\nWe also evaluated this new baseline on QASC (like Ghosal et al. EMNLP 2022, whose setting is moderately different). QASC only requires one-step reasoning, so this discriminative baseline gets 0.96 accuracy, better than all our systems. This is consistent with findings of Clark et al. 2020 and Zhang et al. 2023: Transformers work well as soft reasoners for shallow reasoning, but tend to suffer for deep reasoning. However, this is orthogonal to our main claim (i.e., explicit planning helps). \n\nWe have also experimented with Neural Unification (Picco et al. EMNLP 2021). But this experiment can not be finished by August 29. We expect to finish it by the end of the author-reviewer discussion period, and will post the results via Official Comments as soon as possible.  \n\nReferences: \n\nGhosal et al. EMNLP 2022, https://arxiv.org/abs/2210.16495 \n\nZhang et al. IJCAI 2023, https://arxiv.org/abs/2205.11502 \n\n> This paper is not well-organized. Much important information is presented in the appendix, like figures of models (fig. 6) and the results of analysis (fig. 8, 9).  \n\nWe will reorganize the paper for camera-ready. \n\nDue to the page limit, we had to leave some important materials to appendices. With the extra page allowed by camera-ready, we can bring them back to the main paper. \n\n> There also seems to be two sections for related work (sec 3.4 and 5). \n\nWe will reorganize Section 3.4: \n- some remarks will go to Introduction and Section 3.1 to 3.3;  \n- related-work-style content will go to Related Work (Section 5). \n\n**About Typos Grammar Style And Presentation Improvements**\n\n> Analysis-IV: Since this analysis does not produce results, it could be abbreviated as a footnote or moved to appendix. \n\nGreat idea! \nWe will move it to Appendix C.5, making room for more important materials. \n\n> Some sentences may be informal and redundant, like line 266-267 and line 292-293. \n\nWe will delete these, and fix other such cases. \n\n**About Questions For The Authors**\n\n> In analysis-II, what is the data that supports the claim that “without Ω, System-B performs worse than System-A”? \n\nWe accidentally deleted it when shortening the main paper. Sorry! We will add it back for camera-ready. On Entailment Bank Version-I, the results are\n| | $\\text{AUROC}$ | $\\text{AUACC}_{\\text{pos}}$ | $\\text{AUACC}_{\\text{neg}}$ |\n|-|-|-|-|\n| System-A | 0.88 | 0.86  | 0.54 |\n| System-B without $\\Omega$ | 0.79 | 0.68  | 0.65 | \n| System-B | 0.96  | 0.87 | 0.89 | \n\n> Figure 1: Can you explain why each deduction step (e.g., x2x3->x5) is valid? It seems none of these are actually deductions.  \n\nSure! We'd love to. \n\nThis example is chosen from Entailment Bank (Clark et al. 2021), in which each deduction step is human annotated. \n\nOur way of thinking of these deductions is to think of their formal logic representations. \n\nFor example, one may represent x2 and x3 in Datalog format as: \n- eat(eagle, rabbit)   % Eagles eat rabbits.\n- be(rabbit, animal)  % Rabbits are animals\n\nSuppose there is a rule: \n- eat(X, Y) :- eat(X, Z), be(Z, Y) % If X eats Z and Z is a kind of Y, then X eats Y\n\nThen we can deduce: \n- eat(eagle, animal)  % Eagles eat animals. \n\nHas the absence of the rules confused you? Entailment Bank assumes a \"common sense\" world and does not explicitly provide rules. \n\nOr, are you confused by its quantifier? Entailment Bank uses casual natural languages, in which quantifiers are often omitted. For example, \"Eagles eat animals.\" means \"There are animals that eagles eat.\", but not \"Eagles eat all animals.\" \n\nThese characteristics make Entailment Bank less formal, less rigorous, but more colloquial and human-like (compared to formal logic statements and synthetic data like RuleTaker). In some sense, Entailment Bank exhibits a better match with how humans do logical reasoning in everyday conversations, in which information is often incomplete and languages are often casual and imprecise. This is why we use it as our primary testbed and example in Figure 1. \n\nWe will clarify it in camera-ready. \n\nNote that we also experimented with other kinds of datasets. The PrOntoQA dataset (which is similar to the data of RuleTaker) doesn't make any \"world assumption\", and each of its theories includes rules. Their rules may only hold in fictional worlds; their deductions are more formal and more rigorous. \n\n> Compared to baseline methods, how much more computation does this method cost?\n\nAnalogous to System-I vs. System-II thinking, our method is more deliberative but slower. \nIn theory, at each step of proving a goal, \n- no-planning base system needs $3 B$ operations (select, deduce, verify), where $B$ is the buffer size of beam search; \n- our planning-based system needs $3 B + 3 B E D + 3 B E D$ operations: for each candidate in buffer, we need to examine its E possible expansions (selection or deduction), and roll out D steps of future reasoning (with beam size = 1) for each expansion; \n- as a result, planning brings a performance enhancement at $1 + 2 E D$ times of cost. \n\nOur implementation (which we will release for camera-ready) is efficient due to careful tensorization and parallelism. In our experiments, we used $E=5$ and $D=2$, which should suffer $1 + 2 E D = 21$ times of slowdown. But the actual average wall-clock time of proving a goal is: \n- 2.8 seconds for the base system; \n- 31 seconds for the planning system, which is only 11 times slow. \n\nWe were honest about this efficiency limitation; please see Limitations and Appendix.A of our paper. While carrying out this research project, we have been following the general principle of \"make it work, make it right, make it fast\" (which seems to be followed by many lines of great research in our field): \n- [make it work] we develop an intuitive and effective way to integrate explicit planning into multiple-step logical reasoning; \n- [make it right] we carefully design a training strategy to protect planning from being misguided by imperfect verification model; \n- [make it fast] it will be non-trivial work to make it fast, so we leave it as future work. However, we have proposed a few promising avenues in Appendix.A Future Extensions.", "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 idea of combining LM and planning is novel and meaningful.\n2. The idea is supported by detailed description of the method and extensive experiments and analysis.\n3. The method applies to both small models and large models, which is a practical advantage (although the cost may be higher than other methods).", "reasons_to_reject": "1. This paper is not well-organized. Much important information is presented in the appendix, like figures of models (fig. 6) and the results of analysis (fig. 8, 9). There also seems to be two sections for related work (sec 3.4 and 5).\n2. The baselines methods are limited. For small models, the method is based on tuning, so comparing to prompted GPT-3.5 is not convincing. Instead, the paper may include some tuning baselines for deductive reasoning like RuleTaker [1] and Neural Unification [2].", "questions_to_authors": "A. In analysis-II, what is the data that supports the claim that “without Ω, System-B 602 performs worse than System-A”?\n\nB. Figure 1:Can you explain why each deduction step (e.g., x2x3->x5) is valid? It seems none of these are actually deductions. \n\nC. Compared to baseline methods, how much more computation does this method cost?", "paper_topic_and_main_contributions": "This paper combines language model and explicit planning for multiple-step logical reasoning. For logical reasoning, planning offers two benefits: lowering the number of reasoning steps and interpretability. There is also a challenge of planning in models: model exploitation, which causes the model to be overconfident about some wrong reasoning paths. This paper presents a framework for logical reasoning that combines language models and planning. The framework is based on a base model and two improvements. The base model consists of models for deduction using beam search; the first improvement introduces planning by modifying scores in the base model; the second improvement adds a contrastive loss and KL-divergence to the original loss function. The method applies to both small models like T5 and LLMs like GPT-3.5. Experiments and analysis shows that planning does help deduction.", "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": {"Missing_References": "[1] Peter Clark, Oyvind Tafjord, and Kyle Richardson. 2021. Transformers as soft reasoners over language. In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence (IJCAI'20). Article 537, 3882–3890.\n\n[2] Gabriele Picco, Thanh Lam Hoang, Marco Luca Sbodio, and Vanessa Lopez. 2021. Neural Unification for Logic Reasoning over Natural Language. In Findings of the Association for Computational Linguistics: EMNLP 2021, pages 3939–3950, Punta Cana, Dominican Republic. Association for Computational Linguistics.", "Typos_Grammar_Style_and_Presentation_Improvements": "1. Analysis-IV: Since this analysis does not produce results, it could be abbreviated as a footnote or moved to appendix.\n2. Some sentences may be informal and redundant, like line 266-267 and line 292-293."}}]

Author rebuttal:

Meta-review: This paper presents a new method combine the strengths or large models with explicit planning. A contrastively trained model scores reasoning paths to prevent spurious correlations. Reviewers assessed the work as "high quality", with "pretty strong empirical results" and "novel and meaningful". They also raised concerns about presentation and clarity, as well as missing comparison with SOTA baselines, which were addressed in the rebuttal.
Decision: Accept-Main