Explicit Planning Helps Language Models in Logical Reasoning (2023)

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.

## introduction logical reasoning is one of the most important and longstanding problems in artificial intelligence @xcite . 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 1 for an example. for decades, research in building reasoning systems has heavily relied on formal 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 reasoning; see section 5 for a summary. in this paper, we propose leap, the first lm-based logical reasoning system that performs explicit planning during inference. while determining the truth value of a statement, our system searches over the known facts for those which are 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 a valid proof for the given statement. why planning? planning is a 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 development of various methods in the field of artificial intelligence. 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) @xcite . model-based reinforcement learning uses environment models to simulate responses to actions and then uses the simulated experiences to help learn value functions (e.g., dyna, monte-carlo tree search) @xcite . in natural language processing, planning has been used to help language models generate utterances that satisfy complex constraints @xcite . planning is important for logical reasoning. by examining the future outcomes of each possible decision, a planning-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 planning-based reasoning system tends to be more interpretable, thus more useful in user-centric and safetycritical scenarios. for example, at each round of deduction, planning will explicitly show "what will happen after-and that is also why-i 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 lm-based systems use explicit planning during inference. why is it challenging? during planning, a verification 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 reinforcement learning), and models are imperfect due to architectural biases and finite training data. as a consequence, 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 a statement proves the hypothesis, just because of a significant lexical overlap, causing the planning to favor a decision that helps deduce that statement and lead to the wrong conclusion. ## problem formulation we consider the problem of logical reasoning. given a hypothesis (or, in other words, a goal) x 0 and a theory @xmath0, . . . , x n }, we are interested in determining the truth value of x 0 , i.e., whether x 0 can be logically proved by t . if the goal x 0 is provable, we are interested in discovering the reasoning process that proves it. below is an example theory t "richard is a king." "john is also a 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 reasoning path: we can select the two premises about "john" and deduce "john is a greedy king." by combining them; we then pick the premise about "greedy king" and conclude "john is evil." by combining it with the previous deduction. in this paper, we build an automatic system that is able to perform this kind of human-like logical reasoning. ## our leap framework we propose leap, an lm-based logical reasoning system that performs explicit planning. pretrained lms are excellent at understanding natural languages as well as fluently generating them. foot_1 our leap system harnesses such abilities to simulate step-by-step reasoning processes 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). ## small and large model versions now we introduce two specific versions of our proposed framework: the small language model (slm) version that uses pretrained t5 @xcite and the large language model (llm) version that utilizes gpt-3.5. ## related work reasoning has been a long-standing research topic in natural language processing. for a long time, the majority of research in this direction has been focused on simple tasks such as single-sentence language inference @xcite @xcite @xcite and single-step commonsense inference @xcite @xcite . recently, there has been an increasing research interest in the more complex problem of multi-step logical reasoning, which we study in this paper. @xcite , to the best of our knowledge, is the first to propose an interpretable lm-based model for this problem. they and @xcite work on synthesized data of limited language variability. the lm-based system proposed by @xcite has an architecture similar to the slm version of our base system except that their inference is one-best decoding without planning and their deduction model is trained with extra data collected by @xcite . the selectioninference system of @xcite is similar to the llm version of our base system but their selection and deduction models are few-shot-prompted gpt-3; we compare with them in section 6. 3. liu et al. (2022) also use a similar architecture which they train by reinforcement learning. @xcite embed lms into a backward chaining framework, achieving strong performance in scientific reasoning. our main contribution is complementary to the previous work: we integrate explicit planning into lm-based reasoning systems and design a training method to mitigate the model exploitation issue that arises in planning. our system is a kind of general model programs @xcite )especially those with verification models @xcite -which use language models inside as probabilistic programs and apply disparate inference algorithms to the models. other kinds of approaches to use lms for reasoning include training discriminative models @xcite @xcite , prompting gpt-3 with spelled-out reasoning procedure @xcite , and distilling gpt-3.5 @xcite . another straightforward approach for text-based logical reasoning is to first translate natural language statements into formal logic expressions and then use a formal logic inference engine @xcite @xcite @xcite . 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 popular kind of graph is knowledge graphs, i.e., relational graphs over symbolic tuples @xcite @xcite @xcite @xcite . another kind of graph is built by linking texts via lexical overlap or hyperlink connections @xcite @xcite . methods in this area involve multi-step navigation through graphs. but they rely on pre-defined symbolic and relational structures, thus not directly applicable to our setting. additionally, recent research @xcite shows that optimizing the performance on these datasets is not well aligned to improving the models' fundamental reasoning abilities. ## experiments we carried out a diverse set of experiments that can demonstrate the effectiveness of our proposed methods. we implemented our methods with pytorch @xcite and transformers @xcite . our code is at https://github.com/cindermond/leap . ## conclusion in this paper, we presented leap, an lm-based logical reasoning system that integrates explicit planning into the inference method. we also proposed a 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-thought prompting. we will discuss several exciting avenues for further improvements in appendix a.