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

I have several concerns regarding how claims in the papers are supported by the experiments. These concerns also impact the novelty and soundness of the authors' main method (Fwd-Flip).

1. The authors mentioned that Fwd is the standard forward planning method, Flip is applying the forward planning method to the flipped problem, and Fwd-Flip is "randomly choose either forward direction of the original problem or forward direction of the flipped problem and then plan". Therefore, the only difference between Fwd-Flip and Fwd/Flip is that instead of deciding which direction to plan, the planning direction is randomly selected. However, the experimental results in Table 2 show that Fwd-Flip achieves much higher success rate than Fwd or Flip. To me, this is result is questionable because if Fwd-Flip is just selecting Fwd or Flip randomly, how can it perform much better? In fact, I would expect, with just random sampling, Fwd-Flip to perform exactly the average of Fwd and Flip? I also noticed also that Fwd-Flip is different from what was written in the introduction, which is "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". Could the authors clarify?

2. I also noticed that both Fwd and Flip (on their own) have similar performances over all planning tasks in Table 2. This implies that on average, flipping the problem has no benefits over the direct forward planning method. While I understand that the authors observed that certain planning directions could be easier in some tasks (due to difference in action spaces), it is clear from the experiment results that a particular planning direction is not inherently better in any of the tasks. Hence, I argue that the paper's main method, Fwd-Flip does not actually exploit this observation effectively. I have a suggestion on how the method can be improved: during test-time, we can cleverly decide whether the problem is easier if we flipped it (using some simple heuristics). Then, we can either apply Fwd or Flip based on our heuristic; this is more sound than Fwd-Flip proposed in this paper, which is simply selecting Fwd or Flip randomly. In later experiments, the authors do use the LLM to reason about which planning direction to use, but its effectiveness seems to be restricted to Undirected Graph Planning.

3. Some claims in the papers are briefly stated in words but are not clearly substantiated from the experiments. For example:

• Sec. 4 claims that flipping the problem "... avoids the bias of weak LLM planning in the backward direction." However, Figure 3 shows that for Directed Graphs, for problems with no difference in forward and backward computations, flipping still performs worse than the forward problem. So, it is unclear if flipping the problem entirely avoids the bias.
• There are results such as Figure 3 and Figure 10 that are used to justify the paper's claims that "... LLM plans better in the direction of fewer computations needed, but the forward direction outperforms backward in general ...". However, they are only shown for one planning task (instead of the 3 domains which the paper claims its focus is on). Since the paper mainly relies on empirical observations to justify its claims, I think the same figure should be replicated for other tasks as well (especially that I noticed there are additional space available in the main paper).
• Table 3 tries to show that making the LLM decide which planning direction to use during test-time could improve performance. But somehow the table does not have the results for Fwd-Flip, the author's main proposed method for us to compare Fwd-Flip-Reason to. We also cannot just look at the previous results for Fwd-Flip because the authors mentioned that they used a different hyperparameter $M$ as compared to that in Table 2.

This paper mentions bidirectional search in the related work. However, it is mentioned nowhere in the paper about regression planning. "Thinking forward and backward" reminds me of a fancy title "Thinking fast and slow" and the title also shows effective backward planning. However, it is doubtful if that's the case. If we hold back and remove the LLM portion, then the paper suggests solving planning problems by alternating the initial state and the goals. In general, goals are not a single state as the initial state in most of the problems. It is doubtful how such a switching strategy can lead to systematic improvement as we can always choose one of the goal states as a new initial state in a different problem. One of the weaknesses here is the lack of coverage of the relevant literature.

There are several misleading statements such as "classical planning algorithms such as BFS" line 141. ==> BFS is not a classical planning algorithm "bottleneck" reminds me of the concept of information bottleneck in information theory. However, it is not relevant to this context. It is not clear whether the "bottleneck effect" is relevant in this context.

The details of the implementation of the planner are vague. How possible actions are generated? How the next state will be generated given actions?

Overall: Many general claims are made about the capabilities of LLMs (e.g. they exhibit a systematic bias towards forward planning), and these claims are backed by experiments. However, it's not clear that the experimental results justify these broad claims. Many of the experimental results seem very domain-dependent. For example, Directed Graph Planning has a built in directional bias.

1. The paper uses the term “backward planning” but all the planning is actually in the forward direction, it’s just that sometimes they “flip” the problem (making the old goal the new initial state and the old initial state the new goal).
2. The method proposed for flipping the problem assumes that all actions can be inverted, and it is not clear that this is always the case (so the applicability of “flipping” will depend on whether or not the actions in the domain are, in fact, invertible).
3. Regarding the claims that “LLM exhibit a systematic bias of performing worse when planning backwards” may be attributed to the forward auto-regressive nature of LLM output generation or training data biases: There is not enough evidence to support this as a general claim. Experiments were conducted with only three domains, and at least one (Graph Planning) has by its very nature a built in bias in the forward direction.
4. Figure 2 as an algorithmic description is not clear, and does not seem to match up with the text in lines 168-17.
5. The general conclusions about LLMs drawn from the data presented in Figure 3 (LLMs plan better in the forward direction, and that flip solves this bias) seem suspect given that the directed case in this domain has a built in bias to forward planning so it’s not surprising at all that flip would do well in this case.
6. Also, regarding Figure 3; most of the cases where flip outperforms forward planning are also cases where backward planning already also outperformed forward planning.

The impact of the proposed approach is somewhat unclear. For example, prior research [1] has shown that LLM planning performance significantly deteriorates when the syntax of the planning domain is obfuscated, even when the causal structure remains intact (referred to as “Mystery” domains in [1]). It would have been insightful to see how this approach performs in such obfuscated domains. This also suggests that the computational complexity of the underlying domain doesn’t necessarily affect LLM performance. Therefore, flipping the problem’s initial and goal states to reduce computational complexity might not necessarily benefit LLMs, as they may not be sensitive to these complexity reductions in the same way formal planners are.

Based on my understanding, the method described in Section 4 (always flipping the original problem) aligns with the “Flip” approach in Section 5. Flip performs worse than “Fwd” planning, contrary to what is suggested in Section 5. The proposed approach mentioned in Section 5 appears to be “FwdFlip,” where the decision to flip is made at random. It would be helpful to clarify the exact nature of the proposed approach. Additionally, it would be valuable to see details within the FwdFlip method, such as the success rates within Fwd and Flip respectively.