Thinking Forward and Backward: Effective Backward Planning with Large Language Models

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.

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.