LLMs Can Plan Only If We Tell Them

We thank the reviewer for taking the time to review our paper. We are further encouraged that they found our paper to be "highly original" for LLMs' autonomous planning and finding our contribution to be excellent. We acted upon the reviewer's suggestions to add further implementation details to our revised paper.

The reviewer's main question was whether the way AoT+ utilizes problem states might be challenging to apply in certain settings.

Clarifications

AoT+ requires explicitly restating and caching the current problem state throughout the solution process, which introduces additional complexity. This can demand extra effort in crafting effective state representations, and may be particularly challenging in tasks where the state is difficult to define or capture, such as in ALFWorld.

• We don't agree that restating the states introduce additional complexity compared to all baselines we considered (CoT, LLM-Modulo, AoT, and newly added RAP baseline for blocksworld during the rebuttal) all require the starting and the goal state to be given in the question prompt. Our state representations throughout the solution processes are no different than how one might write them in the question prompt.
• Similary, we disagree that this can demand "extra" effort. All the baselines we considered together with our method can possibly be improved if one spends more time on state representations or other things in the question prompts, therefore, AoT+ does not demand anything extra. Furthermore, we'd like to attract attention to our main results, showing that for larger models, our same prompts work well across the board, whereas, LLM-Modulo is not consistent, which shows the key evidence to the the generality of our process rather than pure dependence on the careful representations.

Regarding the token count comparison table, it would be more comprehensive to include other baselines, such as CoT and AoT, to provide a fuller comparison.

• We have updated Table 4 as per your request, and also included Table 6 (in the appendix A.3) with additional statistical information as per another reviewer's request.

The paper does not specify which version of the Claude model is used in the main experiments (Claude 3.5, Sonnet?). Providing this information would enhance clarity and reproducibility.

• Thank you for noticing this, it is Claude 3.5 Sonnet, we updated the paper to include this information in the main text, however, we don't have enough vertical space to include this information directly in the table itself.

Why might using random trajectories, rather than carefully crafted ones, provide greater flexibility and generalizability as prompting strategies for planning problems? In the context of this paper, crafting examples for Blocksworld as well as other tasks appears relatively straightforward and requires minimal effort.

Thank you for these interesting questions. We mainly focused on fully observable planning problems where the necessary knowledge to solve the problem is given in the question prompt. Although the states in ALFWorld are no more challenging than the ones in Logistics, the difference lies in the knowledge being given as the agent moves around the environment. This is much similar to the RL setting, and it is an exciting direction to apply AoT+. However, ALFWorld is an environment for a different purpose. Nonetheless, we believe there are many ways in which AoT+ could be used in such RL environments:

• Firstly, we can keep separate global state informations as they are revealed, to show the model that these are in addition to all the prior states the model has found to use both types of information at the same time.
• Alternatively, as another agent moves around the environment, we can query the LLM with AoT+ fashion with all the information known up to now.

Conclusion

We sincerely thank the reviewer once again for their thoughtful feedback, which has helped us improve the clarity of our method by addressing the requested details on the implementation. We believe we have thoroughly clarified all the points raised in the review. Considering the reviewer already described our contribution as 'excellent' for the important topic of utilizing LLMs in planning, we would be deeply grateful if they could consider raising their rating, further solidifying the chances of our paper being accepted.

Thank you again for taking the time to review our paper. We would like to update you on the current version of our submission and address the rebuttal responses, which other responding reviewers found to significantly improve both the presentation and our comprehensive experiments.

New Baselines

Following reviewer suggestions, we have incorporated three recent and important baselines: RAP [1], Self-Refine [2], and Tree-planner [3]. These results are presented in Table 5 in the Appendix. While these methods approach AoT's performance, our AoT+ maintains a significant lead over all existing SOTA approaches.

New Ablation Studies

In response to reviewer feedback, we have conducted additional analyses examining the relationship between state hallucination and sequential decision depth (Figure 4). We have also isolated the impact of our innovations in the AoT+ method, with results detailed in Table 5.

Presentation Improvements

We have enhanced the explanations of each methodological component. Notably, reviewer MUTU, who initially raised similar concerns, has acknowledged the significant improvement in presentation clarity.

Conclusion

We are again thankful for your initial review of our paper. Furthermore, we want to clarify that ICLR's rating system differs from ICML or NeurIPS. In ICLR, an "8" corresponds to "Accept," whereas the same score would indicate "Strong Accept" in ICML or NeurIPS (note that "Strong Accept" in ICLR is "10"). While we understand the challenge of not having a "7" rating (which equals "Accept" in ICML and NeurIPS), we believe adjusting the score would better reflect your response to our rebuttal and help safeguard against potential issues if reviewer NGCL does not respond to our rebuttal (now pending for 9 days).

[1] Hao et al. Reasoning with Language Model is Planning with World Model

[2] Madaan et al. SELF-REFINE: ITERATIVE REFINEMENT WITH SELF-FEEDBACK

[3] Hu et al. Tree-Planner: Efficient Close-loop Task Planning with LLMs

Thank you again for your thoughtful review. We have worked hard on our rebuttal, and we believe in its current state, it should satisfy you enough to reconsider your rating.

We thank the reviewer for taking the time to review our paper and for leaving very detailed feedback. We are encouraged that they found our method to be "effective" for planning while it "reduces the token usage". We acted upon their feedback to add further implementation details for our method together with new experiments and new ablation studies.

The reviewer had two main concerns, insufficient explanation of our method's implementation and showing the effect of each of our innovations to the main results together with validation of the effect of memoization over the length of a solution trace.

Further details on our method's implementation

We have updated Section 4.1 and 4.2 with further explanation of each method (in blue text in the revision) together with updated figure 3 (previously figure 4) to compare AoT and AoT+ in-context samples for Blocksworld, which should clarify our implementation of memoization.

New experiments and ablation studies

In order to support our hypothesis in Section 4.2, "that these hallucinations stem from the LLM’s need to continuously recompute and track the current state after each action, potentially overwhelming its computational capacity as the solution trace grows longer", as per the reviewers request, we have added Appendix A.1, to compare the state errors between AoT and AoT+ with respect to the depth of the state in the solution trace. The Figure 4 in the same section provides the key evidence to further support our hypothesis.

Again, as per the reviewer's request, we tested each innovation in the exact setting with the exact models in our main results. We added Appendix A.2 with the new results, where Table 5 includes the new runs for random trajectories and memoization individually, to be more convincing of our claims that random trajectories do not degrade performance, whereas memoization further improves performance (together with Appendix A.1).

Other Questions & Remarks

The observation that random in-context examples does not hurt performance is not new. For instance Min 2022 (https://arxiv.org/abs/2202.12837) presents a study of what makes ICL work.

We disagree that the result from Min 2022 is similar to our use of random traces. As the reviewer pointed out, Min 2022 shows that whether utilizing correct labels or random labels affect the performance of the model on different classification questions. In our case, random actions and hops to other nodes are used to simplify the process of generating in-context examples. We already show that the same model with CoT is not able to find solutions, therefore, the search process with random actions could have prompted the model to also make random actions since we do not provide the model with any heuristic on neither choosing action nor choosing with node to hop next. We find this result exciting and novel, and not related to simply using random labels in classification problems.

The author claims that the proposed method out-competes prior methods and human baselines. However, only human performance in Logistics is compared and only AoT+ with GPT4 can slightly outperform human performance.

We wish to extend the human baselines from Logistics to all benchmarks for the camera-ready version. However, until then, we have updated the necessary parts in our paper to explicitly say "out-competing human baselines in Logistics". Furthermore, logistics is a challenging benchmark and being able to perform better than human baselines is an important achievement showing promise of AoT+. We also would like to attract attention to LLaMA 3.1 405B model's performance on this task, highlighting the existence of open-source models that can get close to human baselines.

I think there might be a grammar error with the sentence: (L339)

We don't think there is a grammar error, however, we added clarifications to this in Section 4.2. As for the reason as to why memoization prevents state errors/hallucinations, we mention our hypotheses again in Section 4.2. Briefly, "Our analysis revealed frequent hallucinations in state representation during the AoT process. We hypothesize that these hallucinations stem from the LLM's need to continuously recompute and track the current state after each action, potentially overwhelming its computational capacity as the solution trace grows longer.", and our further results on Table 2, Figure 3 and Table 5 should portray this.

What does CoT-SC mean in Table 1?

It's Self-Consistency with CoT, we added necessary explanations to the paper now.

What specific version of LLaMA-13B did you use?

LLaMA-2-13B chat

For random solution trajectories, what is the percentage of solution path?

Our random trajectory approach combines one successful and four unsuccessful solution attempts by taking random-length segments from each and interleaving them, while always ending with the successful goal-reaching steps. See updated Section 4.1

Thank you for your continued detailed response. I have increased my score to advocate for acceptance.

Edit: for retrospection of the review process, I do believe that the authors have significantly improved the readability and presentation of the manuscript, at least with respect to my original concerns. This is my primary reason for increasing the score. Needless to say, I also appreciate the authors' engagement and detailed responses.

Thank you for your quick reply! Please also consider reviewing the three new baselines we added to Table 5 in our revised PDF, which further enhance the comprehensiveness of our experimental results.

We appreciate your remarks that helped improve the presentation. We kindly remind you to consider updating the "soundness," "presentation," and "contribution" scores, as these are sometimes overlooked when updating the overall rating.

We thank the reviewer for taking the time to review our paper and leaving thoughtful and direct feedback. We are encouraged to see them find our paper to "present a significant advancement in the autonomous planning capabilities LLMs". We took our time follow up on some of the baseline recommendations from them to further improve the comprehensiveness of our experiments.

The reviewer's main concern was whether some related baselines should have been included.

Section 3.2 and clarifications on the limitations of CoT

We believe the reviewer refers to "Section 3.2 - The Incompatibility of Chain-of-Thought in Planning Problems". We agree with the reviewer that there are prior works on "unfaithfulness" or even directly analyzing CoT's lack of performance for planning problems. Although we included that short subsection as a motivation and background, and not something new, we should have added relevant citations more carefully. Thus, we added necessary citations. However, we believe that subsection is important to avoid questions on why CoT's performance is so bleak in our main results even though it is a step-by-step solution method.

Additional Baselines

We thank the reviewer for suggesting new baselines to highlight our method's performance. We want to go over the recommendations [1-3] and discuss why they are not applicable to our setting, and also present the performance of RAP (in [4]) and how it stacks up to our other baselines.

[1]: A simple iterative way of asking the LLM itself to give feedback to improve does not yield good performance especially for planning problems as shown in literature, e.g., [5] and [6] Actually, these two papers led the same authors to write [7] where they use external feedback to help the model to improve (LLM-Modulo baseline in our paper). In the last paper, authors also show self-feedback does not improve performance over CoT baseline due to "GPT-4 Doesn't Know It's Wrong". Therefore, LLM-Modulo framework is a stronger baseline.

[2]: Reflexion framework, requires the agents to be trained and accrue memory together with needing environments that give verbal feedback detailing what went wrong, an assumption not made in the environments we tested.

[3]: It is perhaps the most distant to our setting in terms of application and assumptions. Tree-planner focuses on robotic task planning, where the agent observes the new states as it performs actions. Instead of doing iterative-planning, they consider the setting of being able to go back to prior positions for the agent to perform other actions that it has not chosen before. However, in the setting of fully observable planning, the outcomes of the actions (new states) should also be considered by the LLM itself.

We thank the reviewer to also suggest [4], as they also tested their method on Blocksworld. Firstly, we are aware of this paper, and as the authors of RAP also point out, ToT is a concurrent work to theirs. MCTS-decoding and A* represent the key difference in node selection between RAP and ToT respectively. Another distinction is that ToT uses external tools like Python to simulate actions, while RAP employs the same LLM with different prompts for simulation. Extending this method across all benchmarks and LLMs is computationally expensive and requires significant manual integration for new environments. We evaluated RAP using 10 iterations, both with and without their task-specific reward heuristic (detailed in section 3.2 of [4]). While RAP outperforms CoT and AoT, it consistently underperforms LLM-Modulo and AoT+, even when using the task-specific reward. RAP's performance notably degrades without the task-specific reward (RAP-T), whereas AoT+ maintains its effectiveness using random search traces without any heuristics. Please refer to Table 3 in our paper for direct comparisons

In conclusion, we have compared our method to a very strong, prior SOTA, LLM-Modulo framework, extensively on 4 challenging benchmarks with 9 LLMs. We hope the reviewer will be satisfied with our explanations for the reasons behind our baselines, and with new results testing RAP on Blocksworld.

[1] Madaan et al. SELF-REFINE: ITERATIVE REFINEMENT WITH SELF-FEEDBACK

[2] Shinn et al. Reflexion: Language Agents with Verbal RL

[3] Hu et al. Tree-Planner: Efficient Close-loop Task Planning with LLMs

[4] Hao et al. Reasoning with Language Model is Planning with World Model

[5] Stechly et al. Gpt-4 doesn't know it's wrong: An analysis of iterative prompting for reasoning problems

[6] Valmeekam et al. Can Large Language Models Really Improve by Self-critiquing Their Own Plans?

[7] Valmeekam et al. On the planning abilities of large language models-a critical investigation

I would like to thank authors for making extra effort to address my comments. After reading their response to my reviews and other reviewers I am willing to keep my score as is (8). Thanks for the great work.

We would like to that the reviewer for taking the time to review our paper. We are really happy that they found our paper to "achieve state-of-the-art performance across complex planning benchmarks" and us to have done overall "great work". We acted upon your improvement points to make a clearer presentation, and numerous new experiments to further complete the comprehensiveness of our method together with studies on state hallucinations as per your request.

The reviewer did not have a main concern, here we respond to their remarks:

• We have improved the presentation of our paper by more clearly explaining each stage, please check the updated sections 4.1&4.2.
• Regarding hallucination failures, we have added Appendix A.1, examining state hallucinations with respect to the solution depth. We show that, AoT+ is almost not affected by the depth, however, AoT has a clear disadvantage for problems with deeper solutions. We have also added Figure 3 include such an example of AoT failure mode.
• AoT+ can be made more or less verbose by changing the in-context examples. We chose a medium level of explanation for the actions (see Figure 3, or Appendix B for all prompts), however, one can include more explanations for the in-context examples to improve the verbal feedback from the model when AoT+ solves new problems.

Would incorporating intermediate reward structures within AoT+ improve long-horizon planning accuracy by incentivizing the model to reach sub-goals? This is an intriguing question. Although we have not utilized any rewards (neither from the model nor external feedback), however, similar to our answer for the verbosity, we believe these intermediate rewards (verbally or by just a number) can be added to the explanations to help steer the model to accomplish important subgoals before reaching the final goal.

Further Experiments

New Baselines: Following reviewer suggestions, we have incorporated three recent and important baselines: RAP [1], Self-Refine [2], and Tree-planner [3]. These results are presented in Table 5 in the Appendix. While these methods approach AoT's performance, our AoT+ maintains a significant lead over all existing SOTA approaches.

New Ablation Studies: In response to reviewer feedback, we have also isolated the impact of our innovations in the AoT+ method, with results detailed in Table 5.

Presentation Improvements: We have enhanced the explanations of each methodological component. Notably, reviewer MUTU, has acknowledged the significant improvement in presentation clarity.

Conclusion

We are again thankful for your review and suggested improvement points. Furthermore, we want to clarify that ICLR's rating system differs from ICML or NeurIPS. In ICLR, a "10" corresponds to "Strong Accept," whereas the same score would indicate "Award Quality" in ICML or NeurIPS. While we understand the challenge of not having a "9" rating (which equals "Very Strong Accept" in ICML and NeurIPS), we believe adjusting the score would better reflect your response to our rebuttal and help safeguard against potential issues if reviewer NGCL does not respond to our rebuttal (now pending for 9 days) with only three days left.

[1] Hao et al. Reasoning with Language Model is Planning with World Model

[2] Madaan et al. SELF-REFINE: ITERATIVE REFINEMENT WITH SELF-FEEDBACK

[3] Hu et al. Tree-Planner: Efficient Close-loop Task Planning with LLMs

We would like to thank the reviewer for taking the time read our work, and we are excited to hear our work to bring "a novel perspective" and to have conducted "comprehensive empirical evaluation across multiple challenging benchmarks". We have acted on their suggestions and introduced new results to fully isolate the impact of each innovation and have more insightful error analysis for AoT+.

The reviewer's main concern is whether the assumption of having a PDDL instance of the problem limits our methods scalability to general domains.

Assumption of having a PDDL instance

We do not make such an assumption. In the benchmarks we tested, only the Blocksworld and Logistics are given as PDDL instances, and the others (game of 24, crossword puzzle, creative writing, list functions and ACRE) do not use PDDL. We utilized PDDL as an additional challenge since we view outputting exact PDDL solution files instead of natural language actions as a more challenging setting. Therefore, we'd like to say repeat that AoT+ does not assume a PDDL instance of a problem, and it can be used in more general environments with even almost infinite number of actions (crossword puzzle) and infinite actions (creative writing, list functions and ACRE). The reason behind providing our wide range of benchmark results together with testing our method with many LLMs with wide variety of open and propietary LLMs was to show the generality and scalability of our method.

Isolating the impact of each innovation and further error analysis on AoT+

Thank you for your request to see further error analysis together with the impact of each innovation. For the former, we went ahead and analyzed the state hallucinations for AoT and AoT+ on the logistics benchmark for puzzles with a depth of at least 20. For each depth, we randomly sampled 20 states to check whether it represents a correct state if the actions were taken according to the LLM (we chose LLaMA-3.1-70B model due to it being cheap and already having a score on the benchmark). We marked the states as errors if they had any mistakes in the states. You can see the comparison in Appendix A.1 in Figure 5 (on page 13). Briefly, it shows that AoT tends to make a lot more mistakes in its beliefs about the states as the depth increases compared to AoT+. Furthermore, for AoT+, the cases where it is not able to reach a solution are mostly due to not being able to find a solution before reaching the max new token generation of 3072 set in our experiments.

For Llama-3.1-70B, out of 58 errors in 200 examples, in only 3 of them the model gave a solution step but was not executable (inadmissable action) or did not reach the goal, compared to 142 for AoT (out of 174 errors in 200 examples).

For isolating the impact of each innovation, we already have Table 1 and "Figure 3" (which is a table actually), showing relevant ablation studies for each innovation. However, we wanted to show a more fine-grained ablation study to show the impact of these on our main experiments as well. For this reason we added AoT+R for AoT with random solution traces, and AoT+M with memoization on all LLMs and benchmarks we tested. Please check Appendix A.2 on the revised PDF of our paper (on page 14). Briefly, the results show that the random solution traces, do not affect the performance as much while making the generation of in-context examples much easier across the benchmarks and LLMs we tested. Furthermore, memoization does boost the performance to reach AoT+'s performance.

We hope we have both clarified and addressed your concerns. We kindly ask that you will reconsider your score based on our response. Feel free to let us know if you'd like us to address anything further. Thank you again for your thoughtful feedback!

Thank you again for your initial review of our paper. It has been some time since we responded to your thoughtful feedback, and we wanted to provide a brief update on the significant improvements we have made overall.

Following reviewer suggestions, we have incorporated three important baselines that further validate our method's effectiveness:

1. RAP (with and without task-specific reward) [1]
2. Self-Refinement [2]
3. Tree-Planner [3]

These comprehensive comparisons are now included in Table 5 in the appendix. While these methods only approach AoT's performance, our AoT+ maintains its position as the leading approach.

We've also conducted additional analyses examining state hallucinations with respect to solution depth (see Figure 4) and have isolated the impact of each innovation in AoT+ (see Table 5). Other reviewers who initially raised similar concerns have noted that these additions significantly improved the paper's clarity and comprehensiveness.

Regarding the rating system, we wanted to mention that ICLR's scale differs from ICML/NeurIPS. An "8" in ICLR corresponds to "Accept" (whereas it would be "Strong Accept" in ICML/NeurIPS).

Thank you again, we are excited to hear your response.

[1] Hao et al. Reasoning with Language Model is Planning with World Model

[2] Madaan et al. SELF-REFINE: ITERATIVE REFINEMENT WITH SELF-FEEDBACK

[3] Hu et al. Tree-Planner: Efficient Close-loop Task Planning with LLMs