Reasoning with Language Model is Planning with World Model
Authors: Shibo Hao
Yi Gu
Haodi Ma
Joshua Jiahua Hong
Zhen Wang
Daisy Zhe Wang
Zhiting Hu
Venue: EMNLP 2023 Main (2023)
Keywords: Large Language Model
Reasoning
TL;DR: We repurposes the LLM as both a world model and a reasoning agent, and incorporates a principled planning algorithm for human-like reasoning.

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.

Reasoning with Language Model is Planning with World Model
Shibo Hao & Yi Gu Haodi Ma Joshua Jiahua Hong*
Zhen Wang*
Daisy Zhe Wang Zhiting Hu
UC San Diego, Universityy of Florida Mohamed bin Zayed University of Artificial Intelligence {s5hao, yig025, jjhong, zhw085, zhh01 9eeucsd. edu {ma {ma.haodi, daisyw]@ufl edu
Abstract
OpenAL, 2023). Recent approaches further boost their ability by prompting LLMs to generate inter- mediate reasoning steps, c.g., Chain-of- ohTThuugh, CoT (Wei et al., 2022) or answer a series of sub- questions, e.g., least-to-most prompting (Zhou et al., 2022). However, LLMs still face difficul- ties with tasks that humans find easy. For example, in creating action plans move blocks to a tar- get state, GPT-3 (Brown al.. 2020) achieves a success rate of only 1%, compared to 78% for hu- mans (Valmeekam et al., 2022); these models also struggle with complex tasks that require multiple steps of math, logical, or commonsense reason- ing (Huang and Chang, 2022; Mialon et al., 2023).
Large language models (LLMs) have shown remarkable reasoning capabilities, particularly with chain-of of-thought (CoT) prompting. How- ever, L.LMs sometimes still struggle with prob- lems that are easy for humans, such gener- ating action plans to achieve given goals in an environment, or performing complex math or logical reasoning. The deficiency stems from the key fact that LLMs lack an internal world model predict the world state (e.g., envi- ronment status, intermediate variable values) and simulate long-term outcomes of actions. This prevents LLMs from performing deliber- ate planning akin to human brains, which in- volves exploring alternative reasoning paths, anticipating future states and rewards, and it- eratively refining existing reasoning steps. To overcome the limitations, we propose new LIM reasoning framework, Reasoning via Planning (RAP). RAP repurposes the LLM both world model and a reasoning agent, and incorporates a principled planning algo- rithm based on Monte Carlo Tree Search for strategic exploration in the vast reasoning space. During reasoning, the LLM (as agent) incre- mentally builds a reasoning tree under the guid- ance of the LLM (as world model) and rewards, and efficiently obtains a high-reward reason- ing path with a proper balance between explo- ration exploitation. We apply RAP to vari- ous challenging reasoning problems including plan generation, math reasoning, and logical inference, and demonstrate its superiority over strong baselines. RAP with ILLMMA33B even surpasses CoT with GPT-4, achieving 33% rela- tive improvement in plan generation setting.'
Humans possess an internal world model, a mental representation of the environment (Johnson- Laird, 1983, 2010; Gentner and Stevens, 2014), which enables humans to simulate actions and their effects the world's state for deliberate planning for complex tasks of motor control, imagery, infer- ence, and decision making (Tolman, 1948; Briscoe, 201 1; Schulkin, 2012; LeCun, 2022). For example, to make an action plan towards 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 the assess- ment (Huys et al., 2012; Gasparski and Orel, 2014; Ho et al., 2021). This in stark contrast the current LLM reasoning. which instinctively gener- ates 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 reward mechanism assess and guide the rea- soning towards the desired state; and due to both limitations, (3) the incapability of balancing explo- ration vs. exploitation to efficiently explore vast
1 Introduction
Large language models (LLMs) have exhibited emergent reasoning abilities in a wide range of tasks (Brown al., 2020; Chowdhery et al., 2022;
"equal contribution
'The code is availahle at https: //git/htitttbbb wwtpe/cccc//oBeeee
11m reasoners

---

Chain-of-Thought
Gg
41
a2
LB
$T
Language Model
Rg
TO
World Model
Action d
State Se.t
Q2
TT
Bewaard f2
ST
Language Model
Reasoning Plonning (RAP)
Figure 1: An overview of Reasoning via Planning (RAP). Compared with previous LLM reasoning methods like Chain-of-Thouge (Wei et al., 2022), we explicitly model the world state from a world model (repurposed from the language model), and leverage advanced planning algorithms to solve the reasoning problems.
reasoning space.
ing, such GSM8K (Cobbe al., 2021) and logi- cal inference exemplified by PrOntoQA (Saparov and He, 2022), RAP also consistently improves over strong baselines, including CoT, least-to-mosi prompting, and their self-consistency variants.
To address these limitations, this paper proposes new framework, Reasoning via Planning (RAP), that enables I.LMs 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). No- tably, we acquire the world model by repurpos- ing the LLM itself with appropriate prompts. Dur- ing the reasoning, the LLM strategically builds 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 re- wards are then backpropagated to update the LLM''s beliefs about the current reasoning steps, guiding it refine the reasoning by exploring better al- ternatives. Our MCTS- planning effectively maintains a proper balance between exploration (of unvisited reasoning traces) and exploitation (of best reasoning steps identified so far).
2 Related Work
Reasoning with LLMs. LLM reasoning typically involves decomposing complex questions into se- quential intermediate steps (a.k.a. chains) before producing the final answer, exemplified by Chain- of of-Thought (CoT) prompting and its variants (Wei et al., 2022; Kojima al., 2022). The basic CoT generates chains all once and can induce ad- ditional errors as the step count increases. Self- Consistency (Wang et al., 2022) samples multi- ple chains to choose the best answer via major- ity voting. Least-to-most prompting (Zhou et al., 2022) reduces the question into simpler subques- tions and answers them sequentially. Similar reward formulation, recent works have explored self-evaluation approaches provide feedback for intermediate steps (Welleck et al., 2022: Shinn et al., 2023; Paul et al., 2023). Aligned with our state formulation, Li et al. (2022) incorporate la- tent "situations" into LLMs, referring to the state of entities from the context. More relevantly, re- works have started to explore more complex structures guided by some search algorithms. For instance, CoRe (Zhu al., 2022) fine-tunes rea- soning step generator and verifier for math word problems with MCTS for decoding. Concurrently to our work, Yao et al. (2023) apply heuristic-based
We show RAP is a general framework applica- ble to a diverse range of challenging problems and achieves substantial improvements over recent pop- ular LLM reasoning methods. For plan generation, particularly in 2/4/6-step problems of Blocksworld (Valmeekam al., 2023), RAP achieves aver- age success rate of 64% while CoT fails almost completely. Moreover, LLaMA-33B with RAP surpasses GPT-4 with CoT by 33% relative im- provement. In the domains of mathematical reason-

---

ITI Carniches camborsus
uhas tlock con tullo the blch The corge booki blook,
Jul soading... ward to road half comsuring
piiee bemirrot how many pigga anould
131 Curracciio aro mare Pspcihosi: unoofliar
5p
Bickue or ngo y- Ddy
Bickuo Dike (he Dity
Jull read 20007
Git has read?
Miree CanTHORe
Every
(f-
011
$1
Hew Yacke??
new... swdd?
CETEANT
Siank orange
Stach on the Ir
thi manyy ploger
read tlooo??
Camborrs verous
Gar
varmea
Acc
How now?
Ths FOOTETA
los coicekkk
Ar:
(The hypothool
hov Aananm??
(Soe achrowed
Figure 2: RAP for plan generation in Blocksworld (left), math reasoning in GSM8K (middle), and logical reasoning in PrOntoQA (right).
scarch, like depth-/breadtth search, for better reasoning paths. However, none of the above meth- ods formally introduce the world model and instan- tiates the reward and state into unified framework. Compared with these search-guided methods, RAP is a more principled framework combine world model and reward with advanced planning. Planning with LLMs. Planning, a central ability intelligent agents, involves generating a series of actions to achieve a specific goal (McCarthy, 1963; Bylander, 1994). Classical planning methods have been widely adopted in robots and embod- ied environments (Camacho and Alba, 2013; Jiang al., 2019). Recently, prompting LLMs do planning directly has gained attention and shown potential (Huang et al., 2022; Singh al., 2022; Ding et al., 2023). Moreover, based on LLMs' pow- erful programming ability (Lyu et al., 2023; Jojic et al., 2023; Liu et al., 2023), recent works first translate natural language instructions into the exe- cutable programming languages, such Planning Domain Description Language (PDDL), and runs classical planning algorithms, such LLM+P (Liu al., 2023). However, code-based planning is constrained by its narrow domains and the environ- ment, while RAP can handle open-domain prob- lems, such as math and logical reasoning. More related works on world models and planning are discussed in the Appendix D.
prompting (Section 3.1). The world model serves as the foundation for deliberate planning, by al- lowing the LLM to plan ahead and seek out the expected outcomes in the future. We then intro- duce 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 Sec- tion 3.4 that yields ensembled result and further boosts the reasoning performance.
3.1 Language Model as World Model
In general, world model predicts the next state of the reasoning after applying an action to the current state (Ha and Schmidhuber, 2018b; Matsuo et al., 2022). RAP enables us to instantiate the general concepts of state and action in different ways de- pending on the specific reasoning problems at hand (Figure 2). For example, in Blocksworld, it is natu- ral to define state the configuration of blocks (described in natural language), and an action to be behavior of moving a block (e.g.. "pickup the orange block"). In a math reasoning problem, we use the state to represent the values of intermedi- ate variables, and set an action to be a subquestion that drives the reasoning to derive new values. In logical reasoning, a state is fact we are focusing on, and an action is to choose rule for the next deduction.
3 Reasoning via Planning (RAP)
In this section, we present the Reasoning via Plan- ning (RAP) framework that enables LLMs to strate- gically plan a coherent reasoning trace for solving a wide range of reasoning tasks. We first build the world model by repurposing the LLM with
With the definition of state and action, the rea- soning process can thus be described as a Markov decision process (MDP): given the current state

---

1,,. e.g., the initial state so, the LLM (as a reasoning agent) generales an action space by sampling from its generative distribution az p(a St, c)2 where с is a proper prompt (e.g., in- context demonstrations). Once an action is cho- sen, the world model then predicts the next state 81+1 of the reasoning. Specifically, we repurpose the same LLM to obtain a state transition distribu- tion p(st-1 18t, dt, d'), where e' is another prompt to guide the LLM generate state. For instance, in Blocksworld, the LLM (as the world model) gen- crates text $t to describe the new configuration blocks, given previous state s, and the action O₁- Continuing the process results in reasoning trace, which consists of sequence of interleaved states and actions (so: ao: $1...., AT-1, (T)) This differs from the previous reasoning methods, such as Chain-of-Thougg (Wei et al., 2022), where the intermediate reasoning steps consist of only a sequence of actions, c.g., (an "pickup red block", a1 "stack yellow block", ...) (see comparisons in Figure 1). Augmenting the reasoning with the (predicted) world states helps the L.LM with a more grounded and coherent infer- ence. Note that the full reasoning trace is simulated by the LLM itself (as a reasoning agent with an internal world model) without interacting with the external real environment. This resembles humans contemplating a possible plan in their minds. The capability of simulating future states, by introduc- ing the world model, allows us incorporate prin- cipled planning algorithms efficiently explore the vast reasoning space as described Section 3.3.
We thus can incorporate the log probability of the action as a reward. This reward reflects the "in- stinct" of LLMs as an agent, and can be also used as a prior for which action to explore.
Confidence of the state. State prediction is non- trivial in some problems, e.g., in math reasoning (Figure 2, middle), given an action (i.e., a subques- tion), the world model predicts the next state by answering the subquestion. We incorporate the con- fidence of the state (i.e., answers in this case) as reward. Specifically, we draw multiple sample answers from the world model, and use the propor- tion of the most frequent answer the confidence. Higher confidence indicates that the state predic- tion is more consistent with the world knowledge of LLMs (Hao al., 2023b), which typically leads to a more reliable reasoning step.
belf-evaluation by the LLM. It's sometimes eas- ier recognize the errors in reasoning than avoid generating them in advance. Thus, it's beneficial to allow the LLM to criticize itself with the ques- tion "Is this reasoning step correct?", and use the next-word probability of the token "Yes" as a reward. The reward evaluates LLM's own estimation of the correctness of reasoning. Note that the specific problems for self-evaluation can be different depending on the tasks.
Task-specific heuristics. RAP also allows us to flexibly plug in other task-specific heuristics into the reward function. For example, in plan gener- ation for Blocksworld, we compare the predicted current state of blocks with the goal calculate reward (Section 4.1). The reward encourages the plan of movements actively pace towards the target.
3.2 Reward Design
During reasoning, we want to assess the feasibil- ity and desirability of each reasoning step, and guide the reasoning based on the assessment (Sec- tion 3.3). The assessment of each reasoning step (i.e., applying an action or to the state st) is per- formed by a reward function V; r(st, at) IR. Similar to the state and action, the reward function be specified in different ways to accommodate any knowledge or preferences about the reason- ing problem of interest. Here we introduce several common rewards applicable to different tasks and shown to be effective in our experiments.
3.3 Planning with Monte Carlo Tree Search
Once equipped with the world model (Section 3.1) and rewards (Section 3.2), LLMs can reason with any planning algorithms. We adopt Monte Carlo Tree Search (MCTS) (Kocsis and Szepesvári, 2006; Coulom, 2007), a powerful planning algorithm that strategically explores the space of reasoning trees and strikes a proper balance between explo- ration and exploitation to find high-reward reason- ing traces efficiently.
Specifically, MCTS builds a reasoning tree it- eratively, where each node represents state, and each edge represents an action and the transition from the current state to the next state after apply- ing the action (Figure 1). To guide the LLM agent
Likelihood of the action. When an action is gen- erated by the LLM conditioning on the in-context demonstration and the current state, the probability the specific action reflects the LLM's preference.

---

50
Prriuu Muo
Picktpp
Pickup EMI
Prrsup orrnge
Protup Due
11
Q1
Stack
Stock
$2
Recuu crangy
RECUA
Pickua erange
Biskua
22
53
ST
Expansion
(e)
[d) Back-propagation
Figure 3: An illustration of the four phases in iteration in MCTS planning (Section 3.3).
to expand and explore the most promising nodes of the tree, the algorithm maintains state-action value function Q S A R. where Q(s, a) es- timates the expected future reward of taking action a in state s. Figure illustrates four operations in each iteration to expand the tree and update Q values. The process continues until a specified com- putational budget (e.g., the number of iterations) is reached, and the resulting traces are acquired from the tree. More details and the pseudo-code of the planning algorithm are given in Appendix A and Algorithm 1.
in the equation. The weight controls the balance between exploration and exploitation.
Expansion. This phase expands the tree by adding new child nodes to the Icaf node seleeted above. Given the state of the leaf node, we use the LLM (as agent) to sample d possible actions (e.g.. subques- tions in math reasoning), and then use the LLM (as world model) to predict the respective next state, resulting in d child nodes. Note that if the leaf node selected above is a terminal node (the end of reasoning chain) already, we will skip expansion and jump to pock-propagation.
Selection. The first phase selects a portion of the existing tree that is most promising for further ex- pansion in the next phase. Starting from the root node (i.e., initial state so), at each level of the tree, the algorithm selects child node as the next node. The phase finishes when leaf node of the cur- rent tree is reached. Figure 3(a) highlights the selected path in red. To balance between explo- ration (of less-visited nodes) and exploitation (of hilu-value nodes), we use the well-known Upper Confidence bounds applied to Trees (UCT) (Koesis and Szepesvári, 2006) to select each child node. Specifically, at node we select the action in the tree by considering both the Q value (for exploita- tion) and uncertainty (for exploration):
Simulation. To estimate the expected future re- wards (Q values), this phase simulates the future sit- uations of the current node using the world model. Starting from the current node above, each node 8, we create an action following a roll-ow policy and use the world model to predict the next state. The roll-out process continucs until a termi- nal state reached. There could be many ways to define the roll-out policy (c.g.. by adding different randomness). In our experiments, for simplicity and reduced noises, we follow a similar process in the expansion above, i.e., generating d candidate actions and picking one of the largest local reward a' max, r(s, a.. In practice, for efficiency, we discard the computationally costly components r (e.g., the reward from the confidence of state re- quires sampling the answer multiple times), and use the resulting lightweight reward function for selecting actions during simulation.
In (&)
a' arg
((s. + aEA(s)
a))
where N(s) is the number of times node s has been visited in previous iterations, and c(s, a) the child node of applying a in state s. The less child node was visited before (i.c., the more uncertain about this child node), the higher the second term
Back- Back- peekk-roppggtion. Once we reach a terminal state in the above phases, we obtain a reasoning path from the root node to the terminal node. We now back pack-propagate the rewards on the path to update

---

the Q value of each state-action pair along the path. Specifically, we update Q(s, a) by aggregating the rewards all future steps of node s.
4.1 Plan Generation
The plan generation task aims to produce a se- quence of actions to achieve a given goal, possibly with additional constraints. The ability to generate plans is important for intelligent embodied agents, e.g. household robots (Puig et al., 2018).
Once predetermined number of MCTS itera- tions is reached, terminate the algorithm and select the final reasoning trace from the constructed tree for evaluation. There are various ways for the selection. One is to start from the root node and it- eratively choose the action with the highest Q value until reaching a terminal. Also, one can directly select the path from the iterations that yielded the highest reward, or opt to choose the leaf node (and the respective root-to-leaf path) that has been vis- ited the most, In practice, we observed that the second strategy often yields the best results.
Task setup. To explore the viability of the RAP framework for plan generation tasks, we adapt and evaluate RAP on the Blocksworld bench- mark (Valmeekam et al., 2022), where an agent is asked to rearrange the blocks into stacks in par- ticular order. We define state as the current orien- tation of the blocks and an action as instruction that moves blocks. Specifically, an action com- posed of one of the 4 verbs (i.c., STACK, UNSTACK, PUT, and PICKUP) and manipulated objects. For the action space, we generate the currently valid actions given the domain restrictions on actions and the current orientation of the blocks. To tran- sit between states, we take the current action and query the LLM predict the state changes the relevant blocks. We then update the current state by adding the new block conditions and removing the conditions that are no longer true. Once a state has met all conditions in the goal or the depth limit of the tree is reached, we terminate the associated node.
3.4 ggreegttnn
For problems, such as math reasoning (Section 4.2) where only the final answer is required, RAP could produce multiple traces and answers from differ- ent MCTS iterations, which will be aggregated to produce the final answer. We refer to such a mech- anism as AAg-ggggea Note that problems like plan generation or logical inference require a complete reasoning trace as output; thus, RAP- Aggregation will not be applied.
4 Experiments
To assess the quality of actions within this do- main, we use two separate rewards. First, we prompt the LLM with some example test cases along with their solutions, and then calculate the log probability of the action given the current state ("Likelihood of action" reward in Section 3.2), de- noted r1. This reward reflects the intuition of the LLM as the reasoning agent. It's typically in- dicative when there are few steps left to the goal, while not as reliable for a distant goal. Additionally, we compare the new state after performing an ac- tion with the goal and provide a reward. r2, scaling with the number of conditions met ("Task- ("Task-specific heuristics" reward). Specifically, when all the con- ditions are met, assign a super large reward to make sure this plan will be selected as the solution. Results. We use test cases from the Blocksworld dataset (Valmeekam et al., 2023) and group them by minimum number of actions required, resulting in 30 cases solvable within 2 steps, 57 cases within 4 steps, and 114 cases within 6 steps. There are at most 5 blocks in each test case. As the baseline method, we prompt the LLM with test cases with corresponding solutions, and ask it to generate a
In this section, we demonstrate the flexibility and effectiveness of our RAP framework by applying it to a wide range of problems, including plan gen- eration in an embodied environment (4.1), mathe- matical reasoning for solving math word problems (4.2), and logical reasoning for verifying hypothe- ses (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-of- thought (CoT) (Wei et al., 2022), and its variants like least-to-most prompting (Zhou et al., 2022) as baselines. We also consider ensembling multiple reasoning paths if applicable (also known as self- consistency (Wang et al., 2022)). Moreover, we compare RAP with GPT-4 (OpenAI, 2023) when computation resources allow. By default, we use the LLaMA-33B model (Touvron et al., 2023a) as the base L.M for both our methods and baselines, with a sampling temperature of 0.8. All prompts are listed in Appendix C.

---

CoT
RAP
(Goal: Thes red blus block, the onange block the red block)
Thove that the rnd Bloc cisr the Slue block is al3r, the orange Block cest Ihe hand umits, oranqe
$9
yallow the boock
unstack the orange
0g
Brack from on tap of the yoloww low block
00
up block.
the ig orange
81
block the blus Mook taile and the fow black the marile
stack the onange block top of the red block
Stock red lock
the blue block
hard
orange booc
of yallow block lru block on of blke book the tase stace to on the rii and the ye lna moak to on the halin
42
pick the low blook
222
Unstaok the orange brock from on top the yellow block
Thave tuat. tie onange block in Bie hard the red block is doear the yollow block twer the heed in hold ng the esange bloos, the net boock is top of the hase bloos, the Now bockk on baile and the yello bloce the mell
83
03
slack the yellme binck on top of block
Stack the orange Mock on top of the red block.
Thare Bual, Fie onange blok d nas the yo veloww dlosk is diear the hand empoy the crange Mocck on top
84
block
block top of base
Figure 4: Comparing reasoning traces in Blocksworld from CoT (left) and RAP (right).
Method
2-step
4-step
6-step
when the first intuition from the LLM doesn't 't work. Specifically, CoT attempts to achieve the second goal, i.e. "orange on red", and achieve that with the first two steps. However, accomplishing the second goal first would prevent the first goal from being satisfied. On the contrary, even though RAP makes the same mistakes in the first iterations, our framework drives the agent to explore other possi- ble paths (as described in Section 3.3) and finally generate a successful plan. (3) When calculating Th, we can only feed the current state to the LLM and hide the history. E.g., in the case of Figure 4, to calculate the reward for 02, the LLM is provided with "new" test case, in which 82 is the initial state. This significantly lowers the difficulties of the last few steps, and saves more iterations for harder decisions of the first few steps.
CoT
0.17
0.02
0.00
CoT pass
0.23
0.07
0.00
CoT (GPT-4)
0.50
0.63
0.40
RAP(10)
1.00
0.86
0,26
RAP(20)
1.00
0.88
0.42
Table 1: Results on Blocksworld. RAP(10) and RAP(20) refer to our method where the iteration number is set to 10 and 20, respectively. "pass @ 10" means 10 plans are sampled for each test case, and the test case is regarded as solved at least one plan correct. All other settings including RAP, only evaluate single plan.
plan for new question. This setting is the same one described in Valmeckam et al. (2022), and we denote it as Chain-of-Thougeee (CoT) the solution is generated step by step. For RAP, the same prompt is shown to help LLMs calculate 71.
As shown in Table 1, CoT with LLaMA-33B can only generate successful plans for a few 2-step cases, and completely fails on harder problems. RAP substantially improves over CoT by nearly solving all problems within 4 steps, and a part of 6-step problems, achieving average success rate of 64%. It's worth noting that the searching space of 6-step problems can be as large as 56, while our algorithm can find a successful plan 42% of the time within 20 iterations. Even more, our frame- work allows LLaMA-338 to outperform GPT-4 by 33% relative gain, which is known to have much stronger reasoning ability (Bubeck et al., 2023).
4.2 Math Reasoning
Task setup. Math reasoning tasks, such as GSM8k (Cobbe et al., 2021), 1), often include a description and a final question. To arrive at the answer to the final question, it is necessary to undertake multi-step mathematical calculations based on the problem's 's context. It is thus natural decompose the final question into a sequence of smaller sub-questions (Figure 2, right). We define a state as the values of intermediate variables, and an action as to pro- pose an incremental sub-question about a unknown intermediate variable. The world model then re- sponds to the sub- question using the intermediate variables and the problem description, adding the new intermediate variable value into the next state. We combine the self-evaluation of helpfulness by LLM Tt,1 and the confidence of state fr,2 using weighted geometric mean r; = rrf. * r/,2 rl-o as the reward function. This reward encourages more rel- evant and useful sub-questions. To account for the
Case study. We compare the reasoning paths from CoT and RAP in Figure 4. We summarize the reasons accounting for the improvement: (1) By maintaining the world state during reasoning, RAP can recognize valid actions for the current state, avoiding generating illegal plans. (2) RAP is capa- ble of backtracking and trying out other solutions

---

Method
Accuracy (%)
Method
Pred Acc
Proof Acc
Chain-of-Thougee
29.4
CoT
87.8
64.8
+ (1)
46.8
CoT SC
89.8
Least-to-Most
25.5
RAP (Ours)
94.2
78.8
+ SC()))
42.5
RAP(1)
40.0
Table 3: Results on ProntoQA.
RAP(10)
48.6
in Figure 5. We find that across all numbers of itera- tions/samples, RAP-Aggregation outperforms base- lines consistently, which indicates that when only a few iterations/samples are allowed, our framework is significantly better at finding reliable reasoning paths with the guide of reward.
aggr
51.6
Table Results on GSM8K. The superscripts indicate the number of samples iterations.
50
45
4.3 Logical Reasoning
Accurscy
40
Task setup. A logical reasoning task (e.g. PrOn- toQA (Saparov and He, 2022)) typically provides a set of facts and logical rules, and model is re- quired to verify if a hypothesis fact is true or false by applying the logical rules to the given facts, as illustrated in Figure 2. These tasks not only re- quire the correct final answer (true/false), but also detailed proof demonstrating the result. To apply our framework, we define the state as a fact we are focusing on, analogous the human's working memory (Baddeley, 1992) for inference. An action is defined as selecting a rule from the fact set. The world model performs a one-hop reasoning step to get a new fact as the next state. The reward is cal- culated with Self-evaluation (Section 3.2. Specif- ically, prompt the LLM with few examples with their labels help it better understand the quality of reasoning steps. We use the average re- ward of future steps to update the Q function, the same as Equation (2) for GSMSK.
35
30
25
RAP loggri
Number of samples (iterations)
Figure 5: Results on GSM-8K, with different numbers of sampled paths iterations.
impact of the reasoning path's length on the reward, we compute the Q value by using the maximum of average rewards in future steps.
Q"(At. ax) Se.0g. F2.
avg( rt).
As related work, Least-to-Most prompting (Zhou et al., 2022) shares a similar idea to us in sub-question decomposition, but they generate sub- questions all once. On the contrary, RAP con- siders each action at based on the current state St, which enables more informed decisions.
Results. We assess the performance of our RAP framework on PrOntoQA (Saparov and He, 2022) and adopt their settings of "true" ontology (using real-world knowledge), "random" ordering of rules. We mix the examples requiring 3, and 5 rea- soning hops in correct proof to prevent LLM from memorizing when finish the reasoning. We sample 500 examples from the generation script released by Saparov and He (2022). We compare both the prediction accuracy of the final answer and the accuracy of the entire proof. We do 20 iterations for MCTS and 20 samples for self-consistency.
Results. We evaluate our framework on GSM8k, a dataset of grade school math word problems. We also evaluate the base model with CoT prompting (Wei et al., 2022), Least-to-Moss prompting (Zhou et all,, 2022), and their self-consistency (Wang et al., 2022) variants, the baselines. We use the same shotot examples demonstrations for all methods. As shown in Table 2, our RAP framework an- swers 18.8% of the problems correctly, outperform- ing both the Chain-of- Chain-of-Thought and the Least-to- Most prompting with Salf-Consistency. Notably, this result is achieved when RAP only selects only one reasoning trace based on the reward. The in- troduction of -gg-eggee further improves the accuracy by ~ 3%. We also calculate the accuracy with different numbers of iterations MCTS and self-consistency samples in baselines, as illustrated
As the results presented in Table 3, our frame- work achieves correct answer rate of 94.2% and proof accuracy of 78.8%, surpassing the CoT baseline by 14% proof accuracy and the self- consistency CoT baseline by 4.4% prediction ac- curacy. Such substantial improvements clearly

---

Setting
Method
2-step
4-step
6-step
8-step
10-step
12-step
All
Easy
CoT RAP(2)
0.49
0.18
0.06
0.01
0.01
0.00
0.08
1.00
0.99
0.75
0.61
0.32
0.32
0.65
Hard
CoT RAP(1)
0.22
0.14
0.02
0.02
0.00
0.00
0.05
0.67
0.76
0.74
0.48
0.17
0.09
0.51
Table 4: Results on the full Blocksworld with Llama-2 70B.
demonstrate the effectiveness of RAP in solving logical reasoning problems in PrOntoQA. Also, as the case illustrated in Figure 2, RAP can effectively recognize when a reasoning chain comes to dead end, and propagate the signal back to earlier reason- ing steps, with the planning algorithm allowing it to explore alternatiess to the previous steps. The self- evaluation reward further helps RAP recognize potential incorrect reasoning steps, encouraging the agent to avoid them in future iterations.
Hard settings, RAP demonstrates superior perfor- mance over CoT by a substantial margin. Notably, when the test case necessitates a larger number steps (six or more) to solve, CoT exhibits a severe drop in success rates, whereas RAP maintains a relatively high success rate. Comparing these re- sults with Section 4.1, additionally conclude that RAP is a general framework able enhance the reasoning abilities LLMs, regardless of their intrinsic capabilities.
5 Analysis
5.2 Reward Choice
5.1 Complex problems
In our main experiments, we choose the combina- tion of rewards in our current experiments based on heuristics and our exploratory experiments. To un- derstand the effects of the reward choice for LLM ca-
To further study whether RAP can help stronger LLMs to solve more complex problems, we conduct experiments on the full Blocksworld (Valmeekam et al., 2023) dataset using pable LLM, Llama-2 70B (Touvron al., 2023b).
reasoning, supplement comprehensive experi- ments on rewards for plan generation (Table 5) and math reasoning (Table 6).
The full Blocksworld (Valmeekam et al., 2023) 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 set- ting, 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. Dur- ing inference, we randomly sample 4-shot demon- stration cases from this pool and utilize them to ran-
Generally, the combination of multiple rewards contributes to the performance. However, the ef- feets a reward depends on the nature tasks. For example, the action likelihood reward is es- sential for plan generation, but not very helpful to mathmatical reasoning. More discussions are in Appendix F.
Conclusion
In this paper, we present Reasoning via Planning (RAP), novel LLM reasoning framework that equips LLMs with an ability to reason akin human-like strategic planning. Our framework. which repurposes the LLM to act as both world model and a reasoning agent, enables the LLM to simulate states of the world and anticipate ac- tion outcomes, and achieve an effective balance between exploration and exploitation via Monte- Carlo Tree Search. Extensive experiments variety of challenging reasoning problems demon- strate RAP's superiority over several contemporary CoT-based reasoning approaches, and even the ad- vanced GPT-4 in certain settings.
formulate prompts. In the Hard setting, domly 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-thouge prompting (Wei al., 2022) baseline, and evaluate our RAP(10) (with 10 iterations) with an improved prompting technique (Appendix E). Our experimental results are summarized in Table both the Easy and

---

Limitations
Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Retichiro Nakano, et al. 2021. Training verifiers to solve math word problems. arXiv preprint 10Xiv:2110.44111
In this work, we mainly focus on utilizing frozen LLMs, whose abilities might be bounded by the pre-training. In the future, is worth exploring how fine-tune LLMs to better reason and serve as a world model (Xiang et al., 2023), as well as how to combine external tools (Hao et al., 2023a; Schick et al., 2023) with RAP to solve more complex real- world problems.
Rémi Coulom. 2007. Efficient selectivity and backup operators in monte-carlo tree search. In Comput- and Games: 5th International Conference, CG 2006, Turin, Italy, May 29-31, 2006. Revised Papers 5. pages 72-83. Springer.
Yan Ding, Xiaohan Zhang, Chris Paxton, and Shiqi Zhang. 2023. Task and motion planning with large language models for object rearrangement. arXiv preprimt 203.:22303.06247.
Ethics Statement
In this paper, we primarily focus on the applica- tions on plan generation, mathematical reasoning, and logical reasoning, posing no significant ethical concerns. We recognize that future research on bor- der applications of reasoning with LLMs may pose a risk of misuse, and we recommend careful con- sideration of all aspects of safety before relevant techniques are applied to the real world.
Wojciech Gasparski and Tufan Orel. 2014. Desig- nology: Studies on Planning for Action, volume 1. Transaction Publishers.
Dedre Gentner and Albert L Stevens, 2014, Mental models. Psychology Press.
David Ha and Jürgen Schmidhuber. 2018a. Recurrent world models facilitate policy evolution. Advances in neural information processing systems, 31.
David Ha and Jürgen Schmidhuber. 2018b. World mod- els. arXiv preprint arXiv:1803.1011
References
Alan Baddeley, 1992. Working memory. Science, 255(5044):556-559
Danijar Hafner, Timothy Lillicrap, Jimmy Ba, and Mo- hammad Norouzi. 2019. Dream to control: Learn- ing behaviors by latent imagination. arXiv preprint arXiv: DrXiiv1191..00 1912.01603.
Robert Eamon Briscoe. 2011. Mental imagery and the varieties of amodal perception. Pacific Philosophical Quarterly, 92(2):133-173 1733.
Danijar Hafner, Timothy Lillicrap, Mohammad Norouzi, and Jimmy Ba. 2020. Mastering atari with discrete world models. arXiv preprint arXiv:2010.02199,
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. 2020. Language models are few-shot learners. Advances in neural information processing systems, 13:1177-1901.
Shibo Hao, Tianyang Liu, Zhen Wang, and Zhiting Hu. 2023a. Toolkengpt: Augmenting frozen language models with massive tools via tool embeddings. Ad- vances in neural information processing systems, 36.
Sébastien Bubeck, Varun Chandrasekaran, Ronen EI- dan, Johannes Gehrke, Eric Horvitz, Ece Kamnr, Peter Lee, Yin Tat Lee, Yuanzhi Li, Scott Lund- berg, al. 2023. Sparks of artificial general intelli- gence: Early experiments with gpt-4, arXiv preprint arXiv:2303. 12712.
Shibo Hao, Bowen Tan, Kaiwen Tang, Bin Ni, Xiyan Shao, Hengzhe Zhang, Eric Xing, and Zhiting Hu. 2023b. Bertnet: Harvesting knowledge graphs with arbitrary relations from pretrained language models. In Findings of the Association for Computational Linguistics: ACL 2023, pages 5000-5015
Mark K Ho, David Abel, Carlos G Correa, Michael L. Littman, Jonathan D Cohen, and Thomas I. Griffiths. 2021. Control of mental representations human planning. arXiv e-prints, pages arXiv-2105.
Tom Bylander. 1994. The computational complexity of propositional strips planning. Artificial Intelligence, 1011-2):655204
Eduardo F Camacho and Carlos Bordons Alha. 2013. Model predictive control. Springer science & busi- ness media.
Jie Huang and Kevin ChennC Chang. 2022. To- wards reasoning in large language models: A survey. arXiv preprint arXiv:2212.11 10400.
Aakanksha Chowdhery. Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, al. 2022. Palm: Scaling language modeling with pathways. arXiv preprint arXiv:2204.02311.
Wenlong Huang, Fei Xia, Ted Xiao, Harris Chan, Jacky Liang, Pete Florence, Andy Zeng, Jonathan Tomp- son, Igor Mordatch, Yevgen Chebotar, et al. 2022. Inner monologue: Embodied reasoning through planning with language models. arXiv preprint arXiv:2207.05608.

---

Quentin JM Huys, Neir Eshel, Blizabeth O'Nions, Luke Sheridan, Peter Dayan, and Jonathan P Roiser. 2012. Bonsai trees in your head: how the pavlovian system sculpts goal-directed choices by pruning decision trees. PLoS computational biology, 8(3)
Grégoire Mialon, Roberto Dessi, Maria Lomeli, Christo- foros Nalmpantis, Ram Pasunuru, Roberta Raileanu, Baptiste Rozière, Timo Schick, Jane Dwivedi- Yu, Asli Celikyilmaz, al. 2023. Augmented language models: a survey. arXiv preprint arXiv:2302.0788
Yu-qian Jiang. Shi-qi Zhang, Piyush Khandelwal, and Peter Stone. 2019. Task planning in robotics: an empirical comparison of pddl-and asp-based systems. Frontiers of Information Technology Electronic Engineering, 20:363-373.
OpenAL. 2023. Gpt-4 technical report.
Debjit Paul, Mete Ismayilzada, Maxime Peyrard, Beat- riz Borges, Antoine Bosselut, Robert West, and Boi Faltings. 2023. Refiner: Reasoning feedback on intermediate representations. arXiv preprint arXiv:2304.01904.
Philip N Johnson-Laird. 2010. Mental models and human reasoning. Proceedings of the National Academy of Sciences, 107(43):18243-1822
Xavier Puig, Kevin Ra. Marko Boben, Jiaman Li, Tingwu Wang, Sanja Fidler, and Antonio Torralba. 2018. Virtualhome: Simulating household activities via programs.
Philip Nicholas Johnson-Laird. 1983, Mental models: Towards a cognitive science of language, inference, and consciousness. 6. Harvard University Press.
Abulhair Saparov and He He. 2022. Language models are greedy reasoners: A systematic formal analysis of chain-of-thought. arXiv preprint ar 2rX0v:2210.01220.
Ana Jojic, Zhen Wang, and Nebojsa Jojic. 2023. Gpt is becoming a turing machine: Here some ways program it. arXiv preprint arXiv:2303.14310
Timo Schick, Jane Dwivedi- Yu,, Roberto Dessi, Roberta Raileanu, Maria Lomeli, Luke Zettlemoyer, Nicola Cancedda, and Thomas Scialom. 2023. Toolformer: Language models can teach themselves to use tools. arXiv preprint arXiv:2302.0473
Levente Kocsis and Csaba Szepesvári. 2006. Bandit based conte-carlo planning. In Machine Learning: ECML 2006: 17th European Conference on Machine Learning Berlin, Germany, September 18-22, 2006 Proceedings 17, pages 282-293. Springer.
Julian Schrittwieser, Ioannis Antonoglou. Thomas Hu- bert, Karen Simonyan, Laurent Sifre, Simon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, al. 2020. Mastering atari, go, chess and shogi by planning with a learned model. Nature, 588(7839):604-609
Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yu- taka Matsuo, and Yusuke Iwasawa. 2022. Large lan- guage models are zero-shot reasoners. arXiv preprint arXiv:2205.1 11916.
Yann LeCun. 2022. A path towards autonomous ma- chine intelligence version 0.9. 2, 2022-06-27. Open Review, 62.
Jay Schulkin. 2012. Action, perception and the brain: Adaptation and cephalic expression. Springer.
Ramanan Sekar, Oleh Rybkin, Kostas Daniilidis, Pieter Abbeel, Danijar Hafner, and Deepak Pathak. 2020. Planning to explore via supersupd world models. In International Conference on Machine Learning, pages 8583-8592. PMLR.
Belinda Z Li, Maxwell Nye, and Jacob Andreas. 2022. Language modeling with latent situations. arXiv preprint 1020:22212.10012.
Bo Liu, Yuqian Jiang, Xiaohan Zhang, Qiang Liu, Shiqi Zhang, Joydeep Biswas, and Peter Stone. 2023. Lim+ p. Empowering large language mod- els with optimal planning proficiency. arXiv preprint arXiv:2304.114 11477.
Noah Shinn, Beck Labash, and Ashwin Gopinath. 2023, Reflexion: an autonomous agent with dynamic mem- ory and self-reflection. ArXiv, abs/2303. 1166..
David Silver, Thomas Hubert, Julian Schrittweeser, Ioan- nis Antonoglou, Matthew Lai, Arthur Guez, Mare Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, al. 2017. Mastering chess and shogi by self-play with a general reinforcement learning algo- rithm. arXiv preprint arXiv: 1712.01815.
Qing Lyu, Shreya Havaldar, Adam Stein, Li Zhang. Delip Rao, Eric Wong, Marianna Apidianaki, and Chris Aallison-Burchh 2023. Faithful chain-of- thought reasoning. arXiv preprint 3.0.:223011137777
Yutaka Matsuo, Yann LeCun, Maneesh Sahani, Doina Precup, David Silver, Masashi Sugiyama, Eiji Uchibe, and Jun Morimoto. 2022. Deep learning, reinforcement learning, and world models. Neural Networks.
Ishika Singh, Valts Blukis, Arsalan Mousavian, Ankit Goyal, Danfei Xu, Jonathan Tremblay, Dieter Fox, Jesse Thomason, and Animesh Garg. 2022. Progprompt: Generating situated robot task plans using large language models. arXiv preprint 2:Xiv:2209.11300
John McCarthy. 1963. Situations, actions, and causal laws. Technical report, STANFORD UNIV CA DEPT OF COMPUTER SCIENCE.
Edward C Tolman. 1948. Cognitive maps in rats and men. Psychological review, 55(4):189.

---

Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Ama Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Fric Hambro, Faisal Azhar, al. 2023a. Llama: Open and effi- cient foundation language models. arXiv preprint arXiv:2302. 239.7711...197.
Xinyu Zhu, Junjie Wang, Lin Zhang, Yuxiang Zhang, Ruyi Gan, Jiaxing Zhang, and Yujuu Yang. 2022. Solving math word problem via cooperative rea- soning induced language models. arXiv preprint arXiv:2210.1622
Hugo Touvron, Louis Martin, Kevin Stone, Peter Al- bert, Amjad Almahairi, Yasmine Babaci, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, al. 2023b. Llama 2: Open founda- tion and fine-tuned chat models. arXiv preprint arXiv:2307.09288
Karthik Valmeekam, Alberto Olmo, Sarath Sreedharan, and Subbarao Kambhampati. 2022. Large language models still can't 't plan (a benchmark for Ilms on plan- ning and reasoning about change). arXiv preprint arXiv:2206. I0498.
Karthik Valmeekam, Sarath Sreedharan, Matthew Mar- quez, Alberto Olmo, and Subbarao Kambhampati. 2023. On the planning abilities of large language models (a critical investigation with a proposed benchmark). arXiv preprint arXfn:2302.06706
Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc Le, Fid Chi, and Denny Zhou. 2022. Self-consistency im- proves chain of thought reasoning in language mod- arXiv preprint wxXiv22033.11177
Jason
Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Ed Chi, Quoc Le, and Denny Zhou. 2022. Chain of thought prompting elicits reasoning large language models. arXiv preprint arXiv:2201. 19903.
Sean Welleck, Ximing Lu, Peter West, Faeze Brah- man, Tianxiao Shen, Daniel Khashabi, and Yejin Choi. 2022. Generating sequences by learning to self-correct. arXiv preprint arXiv:22 2,0002521..00.3.
Philipp Wu, Alejandro Escontrela, Danijar Hafner, Pieter Abbeel, and Ken Goldberg. 2023. Day- dreamer: World models for physical robot learning. In Conference Robot Learning, pages 2226-2240. PMLR.
Jiannan Xiang, Tianhua Tao, Yi Gu, Tianmin Shu, Zirui Wang, Zichao Yang. and Zhiting Hu. 2023. Language models meet world models: Embodied experiences enhance language models. Advances in neural infor- mation processing systems, 36.
Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L Griffiths, Yuan Cao, and Karthik Narasimhan. 2023. Tree of thoughts: Deliberate problem solving with large language models. arXiy preprint arXiv:2305. 10601.
Denny Zhou, Nathanael Schärli, Le Hou, Jason Wei, Nathan Scales. Xuezhi Wang. Dale Schuurmans. Olivier Bousquet, Quoe Le, and Fd Chi. 2022. Least-to-most prompting enables complex reason- ing large language models. arXiv preprint arXiv:2205. 10625.

---

A MCTS Planning
can only pick up or unstack one block at time.
We adapt MCTS to search for the optimal reason- ing path (Algorithm 1). Compared with traditional applications of MCTS, we are faced with large reasoning space, and the heavy computational cost of LLMs. Thus, we made several modifications to the classic MCTS in our implementation: (1) For open domain problems, c.g., math problems, it's impossible to enumerate all actions (subques- tions), so we reduce the action space by sampling a fixed number of potential actions from LLMs, conditioned on prompt of the current state and in- context demonstration. (2) In the selection phase, if there are actions that haven't been visited before, we estimate the Q value with lightweight local re- wards, c.g., self-evaluation reward, and then select the action with UCT. This provides prior knowl- edge for the exploration, which is crucial given the limited iteration budgets.
can only pick up or unstack a block if my hand is empty.
can only pick up a block if the block is on the table and the block is clear. A block is clear if the block has no other blocks top of it and if the block is not picked up.
can only unstack a block from on top of another block the block am unstacking was really on top of the other block.
can only unstack a block from on top of another block if the block I am unstacking is clear. Once pick up or unstack block,
holding the block.
can only put down block that I am holding.
B Experiment Settings
can only stack a block on top of another block if I am holding the block being stacked.
B.1 Language Model Decoding
We use random sampling with a temperature of 0.8. The generation is cut off at the maximum length of 2048 or a newline token.
can only stack block top of another block if the block onto which stacking the block is clear.
B.2 Computing Resources
Once put down or stack a block, my hand becomes empty.
All of our experiments run on 4 x NVIDIA A5000 GPUs with 24GB memory.
[STATEMENT]
Prompt
As initial conditions I have that, the red block is clear, the yellow block is clear, the hand is empty, the red block is on top of the blue block, the yellow block is on top of the orange block, the blue block is on the table and the orange block is on the table.
C.1 Plan Generation
We show the prompt to calculate the action likeli- hood for RAP below. The same prompt is also ap- plied in CoT baseline. <init_stater and <goals> would be instantiated by the problem to solve.
I am playing with set of blocks where I need arrange the blocks into stacks. Here are the actions I can do
My goal is to have that the orange block is on top of the red block.
My plan is follows:
Pick up a block Unstack a block from top of another
[PLAN]
block
unstack the yellow block from on top of the orange block put down the yellow block pick the orange block
Put down block
Stack block on top of another block
I have the following restrictions on my actions:

---

Algorithm RAP-MCTS
Require:
Initial state so, state transition probability function po. reward function action generator Pe. number
of generated actions d, depth limit I., number of roll-outs N. and exploration weight
1: Initialize memory of actions A S A. children S x A + S and rewards S x A +
2: Initialize the state-action value function : 8 A + R and visit counter N S +
3: for O,...,
do
4: f< 0
5: while (st) do
Sclection
6: (s.) + (+t)) +1
In N(ac) or f arg maxae A(or) [(sr, + w N(c(sr.))]
7:
8:
r = r(s) s 81-1 + c(si, at)
9:
24-+1
10:
end while
11:
while 8, is not terminal state A I L do
12:
for 1 + I,....d do
b Expansion
13:
Sample a ~ ps(a 8t), (t) pu(ss, ) and rf re(ss, (
14:
end Update A(s.) < {a vd Jimi c(s,, ) -- s-1 and r(s, -- (60
15:
a++1 f- arg ((x)) (8t, ar) 16:
Simulation
17:
Tt + (-r(,,,a))) Ac+1 + o(8s as)
18:
1+1+1
19:
end while
20:
for l' t,..., do
Back propagation
21:
Update Q(3 ar) with (res ret
22:
end for
23:
end for
stack the orange block on top of the red block
is clear, the orange block is clear, the hand is empty, the blue block is on top of the yellow block, the red block is the table, the orange block is on the table and the yellow block is on the table.
[PLAN END]
[STATEMENT]
As initial condi tions have that, the orange block is clear, the yellow block is clear, the hand is empty, the blue block is on top of the red block, the orange block is on top of the blue block, the red block is on the table and the yellow block is the table.
My goal to have that the blue block is on top of the orange block and the yellow block is on top of the red block.
My plan is follows:
My goal is to have that the blue block is on top of the red block and the yellow block is on top of the orange block.
[PLAN]
unstack the blue block from on top of the yellow block stack the blue block on top of the orange block pick the yellow block stack the yellow block top of the red block
My plan is as follows:
[PLAN]
pick up the yellow block stack the yellow block on top of the orange block
[PLAN END]
[PLAN END]
[STATEMENT]
As initial conditions I have that, the red block is clear, the blue block is clear, the yellow block is clear, the hand is empty, the
[STATEMENT]
As initial conditions I have that, the red block is clear, the blue block

---

yellow block is on top of the orange block, the red block is on the table, the blue block is on the table and the orange block is on the table.
can only pick up or unstack block if my hand is empty. can only pick up a block if the block is on the table and the block is clear. A block is clear if the block has no other blocks on top of it and if the block is not picked up.
My goal is to have that the orange block is on top of the blue block and the yellow block is top of the red block.
only unstack block from top of another block if the block unstacking was really on top of the other block.
My plan is as follows:
[PLAN]
can only unstack a block from on top of another block if the block I am unstacking is clear. Once pick up or unstack block, I am holding the block.
unstack the yellow block from on top of the orange block
stack the yellow block on top of the red block
pick up the orange block
can only put down block that I am holding.
stack the orange block on top of the blue block
can only stack block on top of another block
[PLAN END]
am holding the block being stacked.
[STATEMENT]
I can only stack block on top of another block if the block onto which stacking the block is clear. Once put down stack block, my hand becomes empty.
As initial conditions I have that, <init iinitial_state>
My goal is to have that <goals>.
My plan is as follows:
After being given an initial state and an action, give the new state after performing the action.
[PLAN]
For the next state prediction with the world model, we apply the prompts conditioned on the last action. Here we show the prompt to update the state after a "pick up" action as an example. Again, <state> and <action> would be instanti- ated with the current state and action.
[SCENARIO 1]
[STATE 0] I have that, the white block is clear, the cyan block is clear, the brown block is clear, the hand is empty, the white block is on top of the purple block, the purple block is on the table, the cyan block is on the table and the brown block is on the table.
I am playing with rith set of blocks where
I need to arrange the blocks into stacks. Here are the actions I can do
[ACTION] Pick up the brown block. [CHANGE] The hand was empty and is now holding the brown block, the brown block was on the table and is now in the hand, and the brown block is no longer clear.
Pick up a block Unstack a block from on top of another
block Put down block
Stack block on top of another block
[STATE 1] I have that, the white block is clear, the cyan block is clear, the brown block is in the hand, the hand is holding the brown block,
I have the following restrictions on my actions:
I can only pick up or unstack one block at a time.

---

the white block is on top of the purple block, the purple block is on the table and the cyan block is on the table.
question is answerable, please start the subquestion with "Now we can answer the question:
Question 1: Four years ago, Kody was only half as old as Mohamed. If Mohamed is currently twice as 30 years old, how old is Kody?
[SCENARIO 2]
[STATE 0] have that, the purple block is clear, the cyan block is clear, the white block is clear, the hand is empty, the white block is on top of the brown block, the purple block is on the table, the cyan block is on the table and the brown block is on the table.
Question 1.1: How old is Mohamed?
Answer 1. He is currently
years old. The answer is 60.
Question 1.2: How old was Mohamed four years ago?
Answer 1.2: Four years ago, he must have been 60 4 56 years old. The answer is 56.
[ACTION] Pick up the cyan block. [CHANGE] The hand was empty and is now holding the cyan block, the cyan block on the table and is now in the hand, and the cyan block is no longer clear.
Question 1.3: How old Kody four years ago?
Answer 1.3: Kody was half as old as Mohamed four years ago. Thus, Kody was 56 / 28 years old. The answer is 28.
[STATE 1] have that, the cyan block is in the hand, the white block is clear, the purple block is clear, the hand is holding the cyan block, the white block is top of the brown block, the purple block is the table and the brown block is the table.
Question 1.4: Now we can answer the question: How old is Kody?
Answer 1.4: She is currently 28 4 = 32 years old. The answer is 32.
Question 2: On moonless night, three fireflies danced in the evening breeze. They were joined by four less than a dozen more fireflies before two of the fireflies flew away. How many fireflies remained? Question 2.1: How many fireflies joined? Answer 2.1: The fireflies were joined by four less than dozen more fireflies, which are 12 fireflies. The answer is Question 2.2: Now we can answer the question: How many fireflies remained?
[SCENARIO 3] [STATE 0] <state> [ACTION] <action>
[CHANGE]
C.2
Math Reasoning
We show the prompt of RAP for math reasoning below. The prompt is used for both action pro- posal and next state prediction. After instantiate <question> ton>, we append prefix Question 5. to the prompt, so that we can sample the first action with the LLM. The future actions are sampled sim- ilarly, except that all previous sub-questions and sub-answert need to be appended to the prompt, following the formats of in-context demonstration. The next state prediction, i.c., answering the sub- question, works in the same way.
Answer 2.2: Three fireflies were dancing originally. They were joined by 8 fireflies before of them flew away. So there were
2 9 remaining. The answer is 9.
Given question, please decompose it into sub-questions. For each sub-question, please answer it in complete sentence, ending with "The answer is". When the original
Question 3: Ali has four $10 bills and
six $20 bills that he saved after working for Mr. James on his farm. Ali gives her sister half of the

---

total money he has and 3/5 of the remaining amount of money buy dinner. Calculate the amount of money he has after buying the dinner.
Question 4.1: How far did the car travel except for the 3rd turn? Answer 4.1: It travels meters after the 1st, meters after the 2nd, and 0 meters after the 4th turn. It's a total of 5 + 13 meters. The answer is 13.
Question 3.1: How much money does Ali have in total?
Answer 3.1: Ali has four $10 bills and six $20 bills. So he has 10 +
Question 4.2: Now we can answer the question: How far did the car have travel after the 3rd turn?
20 160 dollars. The answer is 160.
Answer 4.2: The car has driven a total of 23 meters around the ring. It travels 13 meters except for the 3rd turn. So it has to travel 23 13 = 10 meters after the 3rd turn. The answer is 10.
Question 3.2: How much money does Ali give to his sister?
Answer 3.2: Ali gives half of the total money he has to his sister. So he gives 160 2 80 dollars to his sister. The answer is 80.
Question 3.3: How much money does Ali have after giving his sister the money?
Question 5: <question>
C.3 Logical Reasoning
Answer 3.3: After giving his sister the
We show the prompt for action proposal, action likelihood calculation, and next state prediction, <fact> and <query> would be instantiated with the problem.
money, Ali has 160 80 = 80 dollars left. The answer is 80. Question 3.4: How much money does Ali use to buy dinner?
Answer 3.4: Ali uses 3/5 of the remaining amount of money to buy dinner. So he uses dollars to buy dinner. The answer is 48.
Given a list of facts, and a current claim, output one possible fact as the next step. Be sure to copy the exact sentences in the facts. Do not change any wording. Do not create your own words.
3/5
Question 3.5: Now we can answer the question: How much money does Ali have after buying the dinner? Answer 3.5: After buying the dinner, Ali has 80 48 32 dollars left. The answer is 32.
Facts 1: Each lepidopteran is an insect. Each arthropod protostome. Every animal is multicellular. Protostomes are invertebrates. Each whale is bony. Each painted lady is butterfly. Invertebrates animals.
Question 4: A car is driving through a tunnel with many turns. After a while, the car must travel through a ring that requires a total of 4 right-hand turns. After the 1st turn, it travels 5 meters. After the 2nd turn, it travels meters. After the 3rd turn, it travels little further and at the 4th turn, it immediately exits the tunnel. the car has driven total of 23 meters around the ring, how far did it have to travel after the 3rd turn?
Butterflies are lepidopterans. Each insect is six-legged. Every insect is an arthropod. Arthropods are not bony.
Query 1: True or false: Sally is not bony.
Claim 1.1: Sally is insect.
Next 1.1: Each insect is six-legged.
Claim 1.2: Sally is butterfly.
Next 1.2: Butterflies
lepidopterans.
Claim 1.3: Sally is lepidopteran.
Next 1.3: Each lepidopteran is an insect.

---

Claim 1.4: Sally is bony.
Claim 3.4: Polly is lepidopteran.
Next 1.4: Finish.
Next 3.4; Lepidopterans are insects.
Claim 1.5: Sally is an arthropod.
Next 1.5: Arthropods are not bony.
Facts 4: Every cat is a feline. Mammals are vertebrates. Bilaterians are animals. Vertebrates are chordates. Carnivores are mammals. Mammals are not cold-blooded. Each chordate is bilaterian. Every feline is carnivore. Snakes are cold-blooded. Animals are not unicellular. Every carnivore is not herbivorous. Query 4: True or false: Fae is not cold-blooded.
Claim 1.6: Sally is a painted lady.
Next 1.6: Each painted lady is butterfly.
Facts Prime numbers natural numbers. Every Mersenne prime is composite. Imaginary numbers are not real. Every real number is a number. Natural numbers are integers. Every real number is real. Every Mersenne prime is prime number. Natural numbers are positive. Prime numbers not composite. Integers are real numbers.
Claim 4.1: Fae is a feline.
Next 4.1: Every feline is carnivore.
Claim 4.2: Fae is not cold-blooded.
Next 4.2: Finish.
Claim 4.2: Fae is a mammal.
Query True or false: 127 is not real.
Next 4.2: Mammals are not cold-blooded.
Claim 2.1: 127 is real.
Claim 4.3: Fae is a cat.
Next 2.1: Finish.
Next 4.3: Every cat is a feline.
Claim 2.1: 127 is a natural number.
Claim 4.4: Fae is a carnivore.
Next 2.1: Natural numbers are integers.
Next 4:4; Carnivores are mammals.
Claim 2.2: 127 is prime number.
Next 2.2: Prime numbers natural numbers.
Facts 5: Prime numbers prime. Real numbers are numbers. Every integer is real number. Real numbers are not imaginary. Mersenne primes are prime numbers. Complex numbers are imaginary. Each prime number is natural number. Natural numbers are positive. Each Mersenne prime is prime. Each natural number is an integer.
Claim 2.3: 127 is a real number.
Next 2.3: Every real number is real.
Claim 2.4: 127 is a Mersenne prime.
Next 2.4: Every Mersenne prime is a prime number.
Claim 2.5: 127 is integer.
Next 2.5: Integers are real numbers.
Facts Lepidopterans are insects.
Query 5: True or false: 7 is imaginary.
Every animal is multicellular. Each insect is an arthropod. Each invertebrate is an animal. Insects are six-legged. Arthropods are small. Arthropods are invertebrates. Each butterfly is lepidopteran. Whales not small. Query True or false: Polly is not small.
Claim 5.1: is not imaginary.
Next 5.1: Finish.
Claim 5.1: is a natural number.
Next 5.1: Each natural number is an integer.
Claim 5.2: is a prime number.
Next 5.2: Each prime number is natural number.
Claim 5.3: is a real number.
Claim 3.1: Polly is an arthropod.
Next 5.3: Real numbers are not imaginary.
Next 3.1: Arthropods are small.
Claim 3.2: Polly is an insect.
Claim 5.4: 7 is an integer.
Next 3.2: Each insect is an arthropod.
Next 5.4: Every integer is a real number.
Claim 3.3: Polly is small.
Next 3.3: Finish.

---

Facts Spiders are not six-legged. Insects are six-legged. Insects are arthropods. Every animal is not unicellular. Invertebrates are animals. Lepidopterans are insects. Every arthropod is segmented. Arthropods are invertebrates. Every butterfly is lepidopteran. Stella is butterfly.
Table 3: Ablation study on Blocksworld. Rí action likelihood reward, Rg task-specific reward, and Rg is self-cvaluation reward.
R1
R
R3
Success
V
X
0.88
V
/
0.91
V
X
X
0.46
X
V
X
0.21
Query True or false: Stella is
X
X
0.14
six-legged.
X
X
0.02
Claim 6. Stella is an insect.
Next 6.1: Insects are six-legged.
Table 6: Ablation study GSM8k (first 300 examples). R1 is state transition confidence reward, Rt is action likelihood reward, and R3 is self-evaluation reward.
Claim 6.2: Stella is a lepidopteran.
Next 6.2: Lepidopterans are insects.
Claim 6.3: Stella is butterfly.
Next 3: Every butterfly is a lepidopteran.
R1
R2
R3
RAP(1)
RAP(10)
+aggr
Claim 6.4: Stella is six-legged.
X
/
0.410
0.450
0.503
Next 6. 4: Finish.
X
x
0.350
0.447
0.490
/
v
x
0.373
0.423
0.443
Facts 7: <fact>
Query 7: <query>
range of open-domain reasoning tasks. Xiang al. (2023) propose train LLMs wih external world model to gain embodied experience, while RAP focuses on the inference stage and is compatible with any training methods.
D Related work: world model and planning
Recent years have witnessed successful applica- tions of planning algorithms (Sekar et al., 2020), such AlphaZero (Silver et al., 2017), and MuZero (Schrittwieser al., 2020). These algo- rithms are typically based on tree-structured search and are designed effectively maintain the balance exploration and exploitation. Knowledge of tran- sition dynamics is the prerequisite for planning, and recent research on model-based reinforcement learning propose to learn world model (or dynam- ies model) to plan or assist policy learning. To im- prove sample efficiency, previous research attempts learn world model from offline trajectories, and directly learn a policy within the world model (Ha and Schmidhuber. 201 ba.b). With latent imagina- tion in a world model, RL. agents can be trained to solve long-horizon tasks (Hafner et al., 2019, 2020). Besides, the world model is also shown to be help- ful to physical robot learning (Wu et al., 2023). In this paper, we use LLMs world models and upply planning algorithm to search for reasoning path. This is similar in spirit to model predictive control (Camacho and Alba, 2013). Compared with pre- vious works, our framework uses general LLMs as the world model and can be adapted to a wide
E Adaptive Prompting
Through our preliminary experiments, we observed that the performance of LLMs is impacted by the discrepancy in difficulty between demonstration cases and the test cases. In the case of RAP, when new state is predicted, we reformulate the remain- ing task dicted new state. This new test case would require smaller minimum number of actions, leading a disparity the distribution of the demonstration cases and the new cases. To mitigate this issue, we pre-compute the intermediate states of the demon- stration cases beforehand. During inference, we truncate the trace from the beginning for each new state in iteration, which reduces the minimum action number of the demonstration cases as the search tree deepens. This technique significantly enhances the performance of RAP, especially for more intricate problems, which are more suscepti- ble to distribution mismatches.
test case, initialized with the pre-

---

F Reward Choice
the quality of a candidate action is straightfor- ward and still requires multi-step reasoning. This characteristic diminishes the accuracy of the self- evaluation reward, making it less helpful especially given that likelihood already provides a good intu- ition for search.
Results. We conduct comprehensive experiments on rewards for plan generation (Table 5) and math reasoning (Table 6). Note that, both tables, the first row indicates the setting we use in the main experiments. As shown in Table 5, the combina- tion of action likelihood and task-specific reward (row 1) can sigmificantly outperform the single re- ward baselines (row 3, 4, 5). Interestingly, adding the self-evaluation reward can further improve the performance slightly (row 2). Furthermore, as the results on the first 300 samples of GSM8k shown in Table 6, we can see adding either ac- tion likelihood (row 3) or self-evaluation (row I) on top of confidence reward (row 2) can boost the RAP performance of only using confidence reward (row 1) with one iteration, but action likelihood reward downgrades the accuracy with more itera- tions. The self-evaluation reward leads to the best performance overall. This indicates the importance of self-evaluation reward in guiding reasoning as an effective and computationally efficient prior to exploration.
Self-evaluation and action likelihood. The re- wards of self-evaluation and action likelihood are of particular interest, as they can be applied wide range of reasoning tasks. Generally, the best usage and combination with other rewards require empirical design and understanding the task na- ture, and their effectiveness can vary significantly across different tasks. Here, we provide some intu- itions behind the reward choices:
(a) For the problems which one reasoning step is short and structured, the action likelihood can be very indicative. Otherwise, it may be disturbed by unimportant tokens and become unreliable. For instance, single step within the Blocksworld do- main typically adheres to specific patterns (e.g.. PICK/PUT/STACK block...), rendering the ac- tion likelihood indicative. However, in the math domain, a reasoning step is expressed in natural language sentences, allowing for greater freedom and potentially introducing noise.
(b) For the problems where it's easier to recog- nize some errors afterward than avoid them during helpful
generation, self-evaluation emerges mechanism for enhancing reasoning accuracy. In mathematical reasoning, LLMs may struggle to generate a correct reasoning step in the first place, but the detection calculation or logic errors is more feasible. Blocksworlds, however, assessing


Reviews:
[{"review_id": "XDmPVWI4eY", "reviewer": "Reviewer_p5Yn", "summary": "", "questions": "Question A: What was the motivation behind the reward function choices made for different tasks? Is there a reason why the reward system based on the self-evaluation of the LLM is used when evaluating the framework on GSM8k and PrOntoQA benchmarks, but not for the BlockWorld benchmark?", "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": "We thank the reviewer p5Yn for acknowledging the contribution of our paper to introduce a universal solution for black box language models, adaptable across diverse tasks without fine-tuning, and to demonstrate its effectiveness with robust evaluations. We address the reviewer’s concern about the effectiveness of reward design as follows:\n\n## The effectiveness of reward designs\n\nSimilar to the reward design in RL research, the rewards in LLM reasoning also require some curation and design. In short, we choose the combination of rewards in our current experiments based on specific task heuristics and our exploratory experiments. We generally find that both self-evaluation and action likelihood are beneficial to boost performance but the best combination depends on the nature of the task (with more detailed analyses shown later).\n\nMoreover, as the reviewer suggested, to fully explore the effectiveness of reward designs, we further conduct two ablation studies on various combinations of rewards in Blocksworld and GSM8k datasets as shown in RTable 1 and RTable 2.\n\n\n|Action likelihood|Task-specific|Self-evaluation| Success Rate|\n|-|-|-|-|\n|√|√|×|0.88|\n|√|√|√|0.91|\n|√|×|×|0.46|\n|×|√|×|0.21|\n|×|×|√|0.14|\n|×|×|×|0.02|\n\n**RTable 1: RAP with different reward designs on 4-step problems of Blocksworld** (row 1 is the setting used in the paper)\n\nAs shown in RTable 1, we can see the combination of action likelihood and task-specific reward (row 1) can significantly outperform the single reward baselines (row 3, 4, 5). Interestingly, adding the self-evaluation reward can further improve the performance slightly (row 2), indicating the effectiveness of the self-evaluation reward. \n\n|Confidence|Action likelihood|Self-evaluation|RAP$^{(1)}$|RAP$^{(10)}$|+aggr|\n|-|-|-|-|-|-|\n|√|×|×|0.350|0.447|0.490|\n|√|×|√|0.410|0.450|0.503|\n|√|√|×|0.373|0.423|0.443|\n\n**RTable 2: RAP with different reward designs on first 300 examples of GSM8k** (row 2 is the setting used in the paper)\n\nFurthermore, as the results in the first 300 samples of GSM8k (for quick experiments) shown in RTable 2, we can see adding either action likelihood (row 3) or self-evaluation (row 2) on top of confidence reward can boost the RAP$^{(1)}$ (with only 1 iteration) performance of only using confidence reward (row 1), but the self-evaluation rewards lead to the best performance overall. This indicates the importance of self-evaluation reward in guiding reasoning as an effective and computationally efficient prior to exploration.\n\n## On self-evaluation and likelihood of action\n\nOverall, while we agree with the reviewer that “self-evaluation and the likelihood of action can seemingly be applied to any of the tasks”, their best usage and combination with other rewards require empirical design and understanding of the task nature, and **their effectiveness can vary significantly across different tasks**. Here, we provide some intuitions behind the reward choices:\n\n(a) For the problems in which one reasoning step is short and structured, the action likelihood can be very indicative. Otherwise, it may be disturbed by unimportant tokens and become unreliable. For instance, a single step within the Blocksworld domain typically adheres to specific patterns (e.g., pick/put/stack xxx block…), rendering the action likelihood indicative. However, in the math domain (GSM8k), a reasoning step is expressed in natural language sentences, allowing for greater freedom and potentially introducing noise.\n\n(b) For the problems where it’s easier to recognize some errors afterward than avoid them during generation, self-evaluation emerges as a helpful mechanism for enhancing reasoning accuracy. In mathematical reasoning, LLMs may struggle to generate a correct reasoning step in the first place, but the detection of calculation or logic errors is more feasible. In Blocksworlds, however, assessing the quality of a candidate action is not straightforward and still requires multi-step reasoning. This characteristic diminishes the accuracy of the self-evaluation reward, making it less helpful especially given that likelihood already provides a good intuition for search.\n\n## Summary\n\nFinally, we will incorporate these additional experiments and discussions in the updated version of our paper. We will also update Figure 2 in the paper to make it easier to follow. We hope our additional experiments on two comprehensive ablation studies will further enhance the soundness of our paper. \n\nAt the same time, we invite the reviewer to consider the bigger picture that our paper aims to paint. By introducing a **world model** and a principled **planning** framework, we bridge LLMs, the intuition from cognitive science, and the techniques from reinforcement learning, which might envision a promising path for future autonomous agent design. We believe that this vision makes our paper not just a technical contribution but a catalytic one, opening up a range of new research directions and applications. \nWe hope that our responses to the specific concerns could alleviate any reservations about the paper's immediate merits, while we also expect that this broader view will inspire a sense of the work's potential long-term impact. We are eager to include insightful feedback from the reviewers in the revised version of our paper and look forward to contributing to the further advancement of the field.", "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": "A) The paper proposes a solution that can be applied to most black box language models without the need to fine-tune the model.\n\nB) The paper adapts and demonstrates the use of the proposed framework in the context of a diverse set of problems including planning, math, and logical reasoning tasks.\n\nC) The evaluation method for the framework itself is robust and clearly demonstrates the advantage of using the framework over contemporary baselines, even with the missing reasoning for the choice of reward designs for each task.", "reasons_to_reject": "~A) The effectiveness of reward designs is not fully explored. The reward systems that use the self-evaluation by the LLM (introduced in line 277) and the likelihood of action (introduced in line 262) can seemingly be applied to any of the tasks considered during evaluation. No analysis is provided regarding whether one design is better than another, or if the systems are task-dependent.~\n\nUpdate - The author comments provide sufficient justification and experimental results that, when added to the paper, address the above concern effectively.", "questions_to_authors": "Question A: What was the motivation behind the reward function choices made for different tasks? Is there a reason why the reward system based on the self-evaluation of the LLM is used when evaluating the framework on GSM8k and PrOntoQA benchmarks, but not for the BlockWorld benchmark?", "paper_topic_and_main_contributions": "The paper proposes a framework to address the weak performance of large language models on complex and multi-step tasks such as math and planning problems. The paper proposes the use of a tree search algorithm to explore possible intermediate steps and actions through roll-outs while relying on the language model itself to act as a world model. \n\nThe main contribution of this paper is the reasoning and planning framework, complete with descriptions of the algorithm, reward designs, and methods to adapt the framework to different use cases.", "excitement": 4, "reproducibility": 5, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {"Typos_Grammar_Style_and_Presentation_Improvements": "Improvement A: The plan generation example for the GSM8k question in Figure 2 was hard to follow, possibly because the question was abridged. Showing the full question would help readers understand the figure better."}}, {"review_id": "hr6xDhVzPP", "reviewer": "Reviewer_eX3j", "summary": "", "questions": "", "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": "We thank the reviewer eX3j for acknowledging that our idea is novel, taking a step forward in a promising direction, our reward designs are well-explored as a valuable exploration to leverage traditional planning algorithms, and our performance improvement is significant across multiple tasks demonstrating the generality and effectiveness of the proposed approach. We address all the questions and concerns from the reviewer as follows:\n\n## LLM’s inherent limitations in logic and mathematics\nWe agree with the reviewer that current LLMs are imperfect, which is exactly the motivation behind our proposed novel framework, aiming to enhance the reasoning abilities of LLMs and to be generally applied to improve most LLMs (either black-box or open-sourced ones, also pointed out by the reviewer p5Yn). On the other hand, building a “perfect” world model generally for various reasoning tasks (not handcrafting task-specific environments) hasn’t been solved yet, which requires a significant amount of research effort potentially behind a whole new research direction. Therefore, repurposing a reasonably large LLM (LLaMA-33B) as the world model is not only a cost-efficient choice, but also enjoys the flexibility of modeling the world state using language, which is considered as the core contributions of our work. While such a world model isn’t flawless and requires extensive future work for further improvement, in this single paper, we clearly demonstrate its significant effectiveness via comprehensive experiments/tasks and robust results (as pointed out by all reviewers).\n\nBesides, when there are other ways to enhance LLMs’ reasoning abilities, like using calculators to improve their mathematical abilities [1], our proposed method is complementary to them and can directly benefit from such enhancements. We believe it’s also an interesting future work to integrate additional techniques to further enhance LLM reasoning. \n\n## On reward designs\n\nWe appreciate the reviewer’s comments on our reward designs. While the reward design in our paper requires task-specific heuristics and some exploratory experiments (similar to what reward engineering in RL does), our thorough experiments demonstrate that well-designed rewards can boost the reasoning abilities of LLMs across various tasks. Please refer to our response to Reviewer p5Yn to see two new comprehensive ablation strides on rewards, which further show the effectiveness of each reward design. We hope our new additional results can answer the reviewer’s question and demonstrate the effectiveness of our reward design empirically. We will supplement these analyses of reward designs in the updated paper. \n \n## Using frozen LLMs without fine-tuning\nWe thank the reviewer for carefully checking our limitation section. We’d like to point out the significance of developing methods utilizing frozen LLMs. This has actually been an important research topic, exemplified by Chain-of-thoughts and many other papers [2, 3]. Realistically, users often don't have the luxury of fine-tuning an LLM before application. As suggested by Reviewer p5Yn, our approach enjoys generality across most black box language models without necessitating the fine-tuning process. However, we acknowledge that leveraging the world model for further fine-tuning the LLM could potentially further enhance performance if we collect the data and design the task properly, which is out of the scope of this paper and seen as a promising future direction. \n\n## Reference\n\n[1] Schick, Timo, Jane Dwivedi-Yu, Roberto Dessì, Roberta Raileanu, Maria Lomeli, Luke Zettlemoyer, Nicola Cancedda, and Thomas Scialom. \"Toolformer: Language models can teach themselves to use tools.\" arXiv preprint arXiv:2302.04761 (2023).\n\n[2] Wei, Jason, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V. Le, and Denny Zhou. \"Chain-of-thought prompting elicits reasoning in large language models.\" Advances in Neural Information Processing Systems 35 (2022): 24824-24837.\n\n[3] Kojima, Takeshi, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. \"Large language models are zero-shot reasoners.\" Advances in neural information processing systems 35 (2022): 22199-22213.", "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. I think the idea presented in this paper is novel. Utilizing world models to enhance existing large language models is a promising direction, and this work takes a step forward in this direction.\n2. The paper introduces several well-explored designs for rewards, enabling the utilization of traditional planning methods like MCTS, which is a valuable exploration.\n3. Significant performance improvements across multiple tasks demonstrate the generality and effectiveness of the proposed approach.", "reasons_to_reject": "1. Although LLMs demonstrate flexibility in modeling world models, their inherent limitations in logic and mathematics can lead to inaccuracies when used for simulating logic and mathematics.\n2. The designs of several rewards are relatively intuitive, but they do not provide strong guarantees for the performance of the method.\n3. As described by the authors in the Limitations section, this work uses frozen LLMs without fine-tuning, which is constrained by the capabilities of the LLMs itself.", "questions_to_authors": "", "paper_topic_and_main_contributions": "The paper proposes the Reasoning via Planning (RAP) framework to enhance large language models' reasoning capabilities by incorporating an external world model and principled planning.\n\nMain Contributions:\n1. Introducing RAP Framework: RAP augments large language models with a world model and uses principled planning (MCTS) for reasoning.\n2. Enhancing Reasoning: By simulating the state of the world and guiding the reasoning process, RAP improves performance in complex tasks compared to existing methods like CoT.\n3. General Applicability: RAP is a versatile framework applicable to various challenging problems, consistently outperforming strong baselines in tasks like Blocksworld, math reasoning, and logical inference.", "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": "0sFY4TYfyt", "reviewer": "Reviewer_rY4T", "summary": "", "questions": "a. It would be helpful to include a full sample prompt to assist method description\n\nb. It was unclear if the action and space space of each step is pre-defined through prompt or completely open-ended\n\nc. Section 3.2 \"Likelihood of the action\": it is unclear if the likelihood is a number output by the LLM with prompts or through other methods\n\nd. Ln 273: how did the paper draw \"multiple sample answers\" from the world model for each state?\n\ne. Section 3.2 \"Task-specific heuristics\": how much of the method requires task-specific manual curation?\n\nf. Ln 356: how to define \"terminal state\"\n\ng. Table 1: for fair a comparison, if RAP was allowed with multiple trial runs, why aren't CoTs allowed with multiple trials with added small randomness?\n\nh. Ln 455: \"super large\" -- how large?\n\ni. Ln 524: what is alpha?\n\nj. Ln 541: what is self-consistency? \n\nk. Figure 5: by the trajectory, if the number of sample keeps increasing, could Least-to-most or CoT outperform RAP?\n\n", "limitations": "", "rating": 3, "confidence": 4, "soundness": 3, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer rY4T for acknowledging that our proposed method is new and our experiments are thorough for demonstrating the improved performance across different tasks and baselines. We address all the questions and concerns of the reviewer as follows:\n\n## On the questionable performance of LLMs\n\nFirst, we kindly refer the reviewer to check our previous responses to the reviewer eX3j (the first paragraph) regarding why we still use LLMs as the world models given their imperfection. We’d like to emphasize that our framework is designed to **improve the reasoning ability of such (imperfect) LLMs**.\n\nRegarding the concern that the action space and next state generated by LLM may not guarantee faithfulness, we would like to point out that it’s infeasible to investigate the faithfulness of each action and state given the large problem set and sample space, but their effectiveness are **already demonstrated by the task performance improvement** in our experiments. Moreover, to robustly search for the most plausible chain of reasoning within the realm of possibilities offered by the LLMs, we further propose the use of Monte Carlo Tree Search (MCTS), which is **precisely aimed to prune the unfaithful action and states**, which indeed leads to significant improvement.\n\nFinally, we hope the mistrust of LLMs’ probabilistic outputs doesn't overshadow the appreciation of our true contributions in this paper, which is to leverage a new introduction of the world model to novelly reformulate the reasoning problem as a planning task. Rather than viewing our work as a technical addition like \"combining LLM’s action and state prediction and MCTS to improve reasoning performance\", we aspire to offer insights into autonomous agent design, bridging the intuition from cognitive science and techniques from reinforcement learning. By formally introducing this reformulation, as the first work in this field, we hope to open up a promising new avenue for future research, as also acknowledged by other reviewers.\n\n## Self-Evaluation Reward\n\nPart of the concern from the reviewer about the self-evaluation reward is shared with the concerns we addressed above. However, there are a few additional points we’d like to bring up. \n\nFirst, using LLM’s own feedback to guide the LLM’s behavior as the self-evaluation has been heavily studied recently, see [2, 3, 4, 5] and even a survey paper [5] on this topic. Our design of self-evaluation reward is motivated by the intuition that it’s easier to recognize some errors afterward than avoid them during generation.\n\nSecond, to further address these concerns, we have conducted two additional ablation experiments (please refer to our response to Reviewer p5Yn), which **underscore the effectiveness of self-evaluation reward**. In particular, Blocksworld experiences further performance improvement with self-evaluation (row2 over row1 in RTable 1), and is similar as of GSM8k, especially with limited iterations (row2 over row1 in RTable 2). \n\nAdditionally, It’s worth clarifying that the rewards we describe are solely used to guide the search, but not used in the final correctness evaluation of the outcome of our method and the baselines.\n\n## Explanation of details\n\nWe thank the reviewer for the detailed questions and comments. We carefully address them all with additional explanations and experiment results as follows:\n\na. The prompts are included in supplementary materials (line 897). We will also present some prompts in the appendix of the updated paper.\n\nb. The action space is open-ended, i.e., sampled from its generative distribution (line 218)\n\nc. We calculate the likelihood of generating an action by averaging the likelihood of each token measured by the LLM.\n\nd. We randomly decode multiple times (in contrast to greedy decoding) to get multiple predictions\n\ne. In our experiment, only Blocksworld makes use of the task-specific reward. We want to emphasize that RAP is a general framework that can be applied to various tasks. Since some reasoning tasks have their own natural reward heuristics (e.g. how many subgoals are achieved in Blocksworld), RAP is flexible enough to make use of any task-specific reward heuristics.\n\nf. A node that has gathered all information for a reasoning problem is a terminal node (e.g. when the predicted state is equivalent to the goal state in Blocksworld; when LLM answers the original question in GSM8k/PrOntoQA). Besides, a node reaching search depth limitation is also considered terminal.\n\ng. We include “CoT - pass@10” in Table 1, where CoT is allowed to sample 10 answers, and considered success if any of the samples is correct. Note that this is an **easier setting and not a fair comparison**, because RAP must submit only one single plan for evaluation.\n\nh. We set it to 100 in our experiments (which is of a much larger scale than normal reward), but the effect is the same as setting it to “infinity”, because it’s large enough for the agent to select the current reasoning chain.\n\ni. It’s a hyperparameter to control the weight of the geometric mean of $r_1$ and $r_2$. We use $\\alpha=0.5$ in experiments.\n\nj. Self-consistency [1] is an improvement over CoT prompting. It’s sampling multiple reasoning chains and returns the answer based on a majority vote.\n\nk. We run an additional experiment and find Chain-of-Thoughts + SC$^{(15)}$ achieves the accuracy of 0.515, which is comparable to RAP$^{(10)}$+aggr. This indicates our framework can explore the reasoning space more efficiently with fewer iterations.\n\nWe hope our additional experiment results and discussions/explanations/clarifications could further strengthen the soundness of our paper, and the appreciation of its core contributions could ignite excitement for the promising directions revealed by our work. We will include the discussions above, and extend the limitation section into our updated version. Thanks for your questions and suggestions.\n\n## Reference\n\n[1] Wang, X., Wei, J., Schuurmans, D., Le, Q., Chi, E., Narang, S., Chowdhery, A. and Zhou, D., 2022. Self-consistency improves chain of thought reasoning in language models. arXiv preprint arXiv:2203.11171.\n\n[2] Welleck, Sean, Ximing Lu, Peter West, Faeze Brahman, Tianxiao Shen, Daniel Khashabi, and Yejin Choi. \"Generating sequences by learning to self-correct.\" arXiv preprint arXiv:2211.00053 (2022).\n\n[3] Shinn, Noah, Beck Labash, and Ashwin Gopinath. \"Reflexion: an autonomous agent with dynamic memory and self-reflection.\" arXiv preprint arXiv:2303.11366 (2023).\n\n[4] Paul, Debjit, Mete Ismayilzada, Maxime Peyrard, Beatriz Borges, Antoine Bosselut, Robert West, and Boi Faltings. \"Refiner: Reasoning feedback on intermediate representations.\" arXiv preprint arXiv:2304.01904 (2023).\n\n[5] Xie, Yuxi, Kenji Kawaguchi, Yiran Zhao, Xu Zhao, Min-Yen Kan, Junxian He, and Qizhe Xie. \"Decomposition enhances reasoning via self-evaluation guided decoding.\" arXiv preprint arXiv:2305.00633 (2023).\n\n[6] Pan, Liangming, Michael Saxon, Wenda Xu, Deepak Nathani, Xinyi Wang, and William Yang Wang. \"Automatically Correcting Large Language Models: Surveying the landscape of diverse self-correction strategies.\" arXiv preprint arXiv:2308.03188 (2023).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "The paper proposed a new method for reasoning that leverages large language models and explicitly creating internal simulation trees for the optimal decision making. The method combines the open-ended LLM action and state prediction capabilities and deliberate Monte Carlo Tree search reasoning abilities to improve the reasoning performance of the models. The method introduced several reward designs, action selection, tree expansion and decision simulation & aggregation to enhance the performance. The paper conducted thorough experimentations of the method across three different tasks and several baselines of each, and demonstrated improved performance. \n", "reasons_to_reject": "The method relies heavily on the outputs of the large language model, the performance of which is questionable. Both the action space and the next state prediction depends on the output of LLM, which the paper did not investigate how faithful these outputs are. More importantly, one of the rewards is a self-evaluation by the LLM, which could deviate a lot from the actual fact. \n\nThere are several important details about the methods (details below) that could be further explained. \n\nThe Limitations section could be strengthened.\n", "questions_to_authors": "a. It would be helpful to include a full sample prompt to assist method description\n\nb. It was unclear if the action and space space of each step is pre-defined through prompt or completely open-ended\n\nc. Section 3.2 \"Likelihood of the action\": it is unclear if the likelihood is a number output by the LLM with prompts or through other methods\n\nd. Ln 273: how did the paper draw \"multiple sample answers\" from the world model for each state?\n\ne. Section 3.2 \"Task-specific heuristics\": how much of the method requires task-specific manual curation?\n\nf. Ln 356: how to define \"terminal state\"\n\ng. Table 1: for fair a comparison, if RAP was allowed with multiple trial runs, why aren't CoTs allowed with multiple trials with added small randomness?\n\nh. Ln 455: \"super large\" -- how large?\n\ni. Ln 524: what is alpha?\n\nj. Ln 541: what is self-consistency? \n\nk. Figure 5: by the trajectory, if the number of sample keeps increasing, could Least-to-most or CoT outperform RAP?\n\n", "paper_topic_and_main_contributions": "The paper proposed a method for the reasoning problems. It leverages large language models to propose an open-ended sets of action space and next state transaction to build a tree-structured internal world model, and uses the Monte Carlo Tree search to find the most optimal planning path. It incrementally builds the reasoning tree, and record rewards for each internal nodes through multiple rounds of simulation. The paper evaluates the method on three different reasoning tasks: Blocksworld, high school math, and logical reasoning, and demonstrated improved performance compared to baselines. \n", "excitement": 3, "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": {}}]

Author rebuttal:

Meta-review: This paper presents a novel approach to enhance the reasoning capabilities of large language models using a Reasoning via Planning (RAP) framework, incorporating an external world model and principled planning. The study exhibits a high degree of soundness and provides comprehensive, data-driven support for its claims. Some remaining concerns are over the inherent limitations of LLMs, the design of rewards, as well as a few clarifications needed and a more enriched limitation section needed. The authors’ rebuttal addresses the concerns effectively with additional studies and detailed explanations. Should the paper incorporate all the suggestions, it overall presents an exciting stride in language model research, providing a framework applicable across varying tasks with substantial performance improvements.
Decision: Accept-Main