Reasoning with Language Model is Planning with World Model (2023)

Abstract: Large language models (LLMs) have shown remarkable reasoning capabilities, particularly with Chain-of-Thought-style prompts. However, LLMs can still struggle with problems that are easy for humans, such as generating action plans for executing tasks or performing complex math or logical reasoning. This is due to LLMs’ absence of an internal world model for predicting world states (e.g., environment status, variable values) and simulating long-term action outcomes of actions. This prevents LLMs from performing deliberate planning akin to human brains, which involves exploring alternative reasoning paths, anticipating future states and rewards, and iteratively refining existing reasoning steps. To overcome the limitations, we propose a new LLM reasoning framework, Reasoning via Planning (RAP). RAP repurposes the LLM as both a world model and a reasoning agent, and incorporates a principled planning algorithm (based on Monte Carlo Tree Search) for strategic exploration in the vast reasoning space. During reasoning, the LLM (as agent) incrementally builds a reasoning tree under the guidance of the LLM (as world model) and task-specific rewards, properly balancing exploration v.s. exploitation to achieve a high-reward reasoning path efficiently. We apply RAP to a variety of challenging reasoning problems, such as plan generation, math reasoning, and logical inference. Empirical results demonstrate the superiority of RAP over various strong baselines, including CoT and least-to-most prompting with self-consistency, e.g., RAP on LLaMA-33B surpasses CoT on GPT-4 with 33% relative improvement in plan generation.

## introduction large language models (llms) have exhibited emergent reasoning abilities in a wide range of tasks @xcite @xcite * equal contribution 1 the code is available at https://github.com/ber666/ llm-reasoners @xcite . recent approaches further boost their ability by prompting llms to generate intermediate reasoning steps, e.g., chain-of-thought, cot @xcite or answer a series of subquestions, e.g., least-to-most prompting @xcite . however, llms still face difficulties with tasks that humans find easy. for example, in creating action plans to move blocks to a target state, gpt-3 @xcite achieves a success rate of only 1%, compared to 78% for humans @xcite ; these models also struggle with complex tasks that require multiple steps of math, logical, or commonsense reasoning @xcite . humans possess an internal world model, a mental representation of the environment @xcite @xcite , which enables humans to simulate actions and their effects on the world's state for deliberate planning for complex tasks of motor control, imagery, inference, and decision making @xcite @xcite . for example, to make an action plan towards a goal, planning with the world model involves exploring various alternative courses of actions, assessing the likely outcomes by rolling out possible future scenarios, and iteratively refining the plan based on the assessment @xcite @xcite . this is in stark contrast to the current llm reasoning, which instinctively generates a reasoning trace in an autoregressive manner. in particular, we identify several key limitations of the current reasoning with llms, including (1) the lack of an internal world model to simulate the state of the world (e.g., the configuration of blocks, the values of intermediate variables), which is the foundation of human planning; (2) the absence of a reward mechanism to assess and guide the reasoning towards the desired state; and due to both limitations, (3) the incapability of balancing exploration vs. exploitation to efficiently explore vast reasoning space. to address these limitations, this paper proposes a new framework, reasoning via planning (rap), that enables llms to reason in a manner close to humans' conscious planning. rap augments the llm with a world model, and reasons with principled planning (specifically monte carlo tree search, mcts) to produce high-reward reasoning traces after efficient exploration (figure 1 ). notably, we acquire the world model by repurposing the llm itself with appropriate prompts. during the reasoning, the llm strategically builds a reasoning tree by iteratively considering the most promising reasoning steps (actions) and using the world model (the same, repurposed llm) to look ahead for future outcomes. the estimated future rewards are then backpropagated to update the llm's beliefs about the current reasoning steps, guiding it to refine the reasoning by exploring better alternatives. our mcts-based planning effectively maintains a proper balance between exploration (of unvisited reasoning traces) and exploitation (of the best reasoning steps identified so far). we show rap is a general framework applicable to a diverse range of challenging problems and achieves substantial improvements over recent popular llm reasoning methods. for plan generation, particularly in 2/4/6-step problems of blocksworld @xcite , rap achieves an average success rate of 64% while cot fails almost completely. moreover, llama-33b with rap surpasses gpt-4 with cot by 33% relative improvement. in the domains of mathematical reason-ing, such as gsm8k @xcite and logical inference exemplified by prontoqa @xcite , rap also consistently improves over strong baselines, including cot, least-to-most prompting, and their self-consistency variants. compared with these search-guided methods, rap is a more principled framework to combine world model and reward with advanced planning. planning with llms. planning, a central ability in intelligent agents, involves generating a series of actions to achieve a specific goal @xcite . classical planning methods have been widely adopted in robots and embodied environments @xcite . recently, prompting llms to do planning directly has gained attention and shown potential @xcite @xcite . moreover, based on llms' powerful programming ability @xcite @xcite , recent works first translate natural language instructions into the executable programming languages, such as planning domain description language (pddl), and runs classical planning algorithms, such as llm+p @xcite . however, code-based planning is constrained by its narrow domains and the environment, while rap can handle open-domain problems, such as math and logical reasoning. more related works on world models and planning are discussed in the appendix d. ## reasoning via planning (rap) in this section, we present the reasoning via planning (rap) framework that enables llms to strategically plan a coherent reasoning trace for solving a wide range of reasoning tasks. we first build the world model by repurposing the llm with prompting (section 3.1). the world model serves as the foundation for deliberate planning, by allowing the llm to plan ahead and seek out the expected outcomes in the future. we then introduce the rewards for assessing each state during reasoning in section 3.2. guided by the world model and rewards, the planning with monte carlo tree search (mcts) efficiently explores the vast reasoning space and finds optimal reasoning traces (section 3.3). finally, when multiple promising reasoning traces are acquired during planning, we further introduce an aggregation method in section 3.4 that yields an ensembled result and further boosts the reasoning performance. ## experiments in this section, we demonstrate the flexibility and effectiveness of our rap framework by applying it to a wide range of problems, including plan generation in an embodied environment (4.1), mathematical reasoning for solving math word problems (4.2), and logical reasoning for verifying hypotheses (4.3). the subsequent sections demonstrate how the world model formulation in rap enables a versatile design of the state and action, catering to various reasoning contexts. we primarily compare rap with chain-ofthought (cot) @xcite , and its variants like least-to-most prompting @xcite as baselines. we also consider ensembling multiple reasoning paths if applicable (also known as selfconsistency @xcite ). moreover, we compare rap with gpt-4 (openai, 2023) when computation resources allow. by default, we use the llama-33b model @xcite as the base llm for both our methods and baselines, with a sampling temperature of 0.8. all prompts are listed in appendix c. ## analysis 5.1 complex problems to further study whether rap can help stronger llms to solve more complex problems, we conduct experiments on the full blocksworld @xcite dataset using a more capable llm, llama-2 70b @xcite . the full blocksworld @xcite ) comprises 602 test cases. we group them based on the minimum number of actions required for each test case. our experiments are conducted in two distinct settings: easy and hard. in easy setting, we assume prior knowledge of the minimum number of actions for each case. leveraging this information, we use demonstration cases that share the same minimum number of actions as the test case. for each group of cases, we randomly select 10 cases to create a pool of demonstration cases, leaving the remaining cases as the test set. during inference, we randomly sample 4-shot demonstration cases from this pool and utilize them to formulate prompts. in the hard setting, we randomly select 10 cases from the full dataset to form a demonstration pool and subsequently exclude these cases from the test set. during inference, we randomly sample 4-shot demonstration cases from this global pool, irrespective of the minimum number of actions required for the test case. we employ chain-of-thought prompting @xcite as a baseline, and evaluate our rap (10) (with 10 iterations) with an improved prompting technique (appendix e). our experimental results are summarized in ## conclusion in this paper, we present reasoning via planning (rap), a novel llm reasoning framework that equips llms with an ability to reason akin to human-like strategic planning. our framework, which repurposes the llm to act as both a world model and a reasoning agent, enables the llm to simulate states of the world and anticipate action outcomes, and achieve an effective balance between exploration and exploitation via monte-carlo tree search. extensive experiments on a variety of challenging reasoning problems demonstrate rap's superiority over several contemporary cot-based reasoning approaches, and even the advanced gpt-4 in certain settings.