Thinking Forward and Backward: Effective Backward Planning with Large Language Models
Allen Z. Ren, Brian Ichter, Anirudha Majumdar · 2024
Read Thinking Forward and Backward: Effective Backward Planning with Large Language Models by Allen Z. Ren, Brian Ichter, Anirudha Majumdar (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2411-01790.txt.
Description
Abstract Large language models (LLMs) have exhibited remarkable reasoning and planning capabilities. Most prior work in this area has used LLMs to reason through steps from an initial to a goal state or criterion, thereby effectively reasoning in a forward direction.
Catalog record
| CREATOR | Allen Z. Ren, Brian Ichter, Anirudha Majumdar |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 59 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2411-01790
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Thinking Forward and Backward: Effective Backward Planning with Large Language Models Allen Z. Ren, Brian Ichter, Anirudha Majumdar Abstract Large language models (LLMs) have exhibited remarkable reasoning and planning capabilities. Most prior work in this area has used LLMs to reason through steps from an initial to a goal state or criterion, thereby effectively reasoning in a forward direction. Nonetheless, many planning problems exhibit an inherent asymmetry such that planning backward from the goal is significantly easier — for example, if there are bottlenecks close to the goal. We take inspiration from this observation and demonstrate that this bias holds for LLM planning as well: planning performance in one direction correlates with the planning complexity of the problem in that direction. However, our experiments also reveal systematic biases which lead to poor planning in the backward direction. With this knowledge, we propose a backward planning algorithm for LLMs that first flips the problem and then plans forward in the flipped problem. This helps avoid the backward bias, generate more diverse candidate plans, and exploit asymmetries between the forward and backward directions in planning problems — we find that combining planning in both directions with self-verification improves the overall planning success rates by 4-24% in three planning domains. Code: github.com/irom-princeton/llm-backward . 1 Introduction Large Language Models (LLMs) are increasingly capable in reasoning tasks — they can perform commonsense reasoning in a broad set of contexts ( Kojima et al., 2022 ) , reason about abstract patterns in data ( Mirchandani et al., 2023 ) , and learn to reason from human feedback ( Liang et al., 2024 ) . Such capabilities also open up the possibility of LLMs performing long-horizon planning ( Valmeekam et al., 2024 ) , where the model needs to reason about how the initial state and final goal of the problem can be connected through intermediate steps. Most existing work has explored such problems by asking the model to reason in the forward direction, i.e., generating intermediate steps from the initial state to the final goal. However, in many planning problems, there is an inherent asymmetry : generating the correct last steps leading to the goal can be much easier than generating the correct steps from the beginning. This leads to the question: can LLMs plan better if they also reason in the backward direction? As an example, consider a robot navigating in a room ( Fig. 1 ): if the final goal is the bedroom at the end of a long and narrow hallway, it is natural to connect the bedroom with the beginning of the hallway first in the plan, and then search for the path that connects the hallway to the initial state. In this example, there is a “bottleneck" that causes the asymmetry: the number of possibilities when planning backward from the goal is constrained by the bottleneck (hallway), while the possibilities fan out quickly when planning from the start. Such bottlenecks are ubiquitous in planning problems; for example, in proving mathematical theorems ( Loveland, 2016 ) , there may be many possible steps to start a proof of a theorem, but the final steps can be much more closely related to the theorem statement and thus easier to choose. In our experiments, we quantify this bottleneck effect by comparing the exact number of search steps used by common forward-search algorithm (e.g., Breadth-First Search) when applied in the forward and backward directions on the underlying graph of the planning problem ( Fig. 1 ). Figure 1: (Left) In planning problems such as navigation, it can often be easier to plan in the backward direction, especially when a “bottleneck” state (red node) exists and it is easier to find it from the goal rather than from the initial state. We consider Graph Planning , where the LLM needs to plan the shortest path from the initial node to the goal. (Right) Two other planning domains: Array Transformation , where an integer array is manipulated through different functions to the desired array, and Blocksworld , where stacks of blocks are re-oriented to the goal state. The goals of this paper are twofold. First, we perform extensive experiments on three classical planning problems ( Section 2 ) and examine whether LLM-based planning is significantly impacted by the asymmetry described above, i.e., if LLMs achieve higher planning success rates in the direction (forward/backward) where fewer computations are needed. Second, we study whether LLMs can exploit bottleneck effects by effectively planning backward ( Section 3 ). Our results provide strong evidence for the first hypothesis. However, unfortunately, we find that LLMs exhibit a systematic bias of performing worse when planning backward; this may be attributed to the forward autoregressive nature of LLM output generation, as well as biases from the training dataset. Addressing the backward reasoning bias, we propose a simple solution ( Section 4 ): many problems can be transformed such that the original goal becomes the initial state and the original initial state becomes the goal — we ask LLMs to first “flip” the problem, and then plan in the forward direction (corresponding to the original backward direction). Given a planning problem, we ask LLMs to sample possible plans in the forward direction of both the original problem and the flipped one, and then self-verify ( Stechly et al., 2024 ) all the plans before choosing the final one. We find that this simple setup allows LLMs to generate many more diverse candidate plans and exploit the bottleneck structure of the problems, improving the overall success rate in multiple planning domains by 4-24% ( Section 5 ). Perhaps surprisingly, we also present evidence that in certain settings LLMs can also reason whether to flip the problem or not by examining the problem structure. 2 Formulation and Planning Domains We define a (text-based) planning problem as P=(\mathcal{S},\mathcal{A}_{\mathcal{S}},s_{0},g,T_{\text{max}},f) , where \mathcal{S} is the space of possible states, \mathcal{A}_{\mathcal{S}}=\{\mathcal{A}_{s}\}_{s\in\mathcal{S}} includes the space of possible actions (planned steps) at each state s\in\mathcal{S} , s_{0}\in\mathcal{S} is the initial state, g\in\mathcal{S} is the goal, T_{\text{max}} is the maximum allowable steps, and f is a ground-truth solution verifier that determines if a plan solves P , i.e., whether a plan connects s_{0} to g , and possibly, is of optimal length. The generated plan A=(a_{0},...,a_{T})_{T\leq(T_{\text{max}}-1)} is verified by f based on these rules. Each action a_{t} converts state s_{t} to s_{t+1} , and we denote this as s_{t}\xrightarrow{a_{t}}s_{t+1} . We denote pre-trained LLMs with parameters \theta as p_{\theta} . Instead of the usual token-level generation, for convenience we consider LLMs generating the next step in a plan by sampling a_{t}\sim p_{\theta}(a_{t}|s_{0},g,\{a_{0},...,a_{t-1}\},q) , where q denotes the rest of the text prompt (e.g., few-shot exemplars and instructions). For convenience, from now on we also assume that q includes text descriptions of s_{0} , g , and (a_{0},...,a_{t-1}) . During planning, LLMs may also generate other intermediaries such as the estimated states along the plan (\hat{s}_{1},...,\hat{s}_{t}) , which might help the LLM reason about the next step given the current estimated state. Next we introduce the three different planning domains ( Fig. 1 ) considered in our work. Appendix A provides more details on the design of these domains. Graph Planning. In Graph Planning ,