LLMs Can Plan Only If We Tell Them

Authors: Bilgehan Sel, Ruoxi Jia, Ming Jin
Primary area: foundation or frontier models, including LLMs
Keywords: large language models, decision-making, planning

Abstract:
Large language models (LLMs) have demonstrated significant capabilities in natural language processing and reasoning, yet their effectiveness in autonomous planning has been under debate. While existing studies have utilized LLMs with external feedback mechanisms or in controlled environments for planning, these approaches often involve substantial computational and development resources due to the requirement for careful design and iterative backprompting. Moreover, even the most advanced LLMs like GPT-4 struggle to match human performance on standard planning benchmarks, such as the Blocksworld, without additional support. This paper investigates whether LLMs can independently generate long-horizon plans that rival human baselines. Our novel enhancements to Algorithm-of-Thoughts (AoT), which we dub AoT+, help achieve state-of-the-art results in planning benchmarks out-competing prior methods and human baselines all autonomously.

Decision: accept (poster)
Reviewer scores: 6, 8, 6, 6, 6

Reviews and discussion:
<thread>
creation date:
1729211378943

thread_type:
official_review

<thread_object>
creator: reviewer_4iqa

<content>
summary:
The paper explores various aspects of planning and problem-solving using language models, focusing on whether LLMs can independently generate long-horizon plans that rival human baselines. The authors introduce novel enhancements to the Algorithm-of-Thoughts (AoT), termed AoT+, which achieve state-of-the-art results in planning benchmarks, surpassing prior methods and human performance—all autonomously. These enhancements, including Periodic Structured State Generation and Random Trajectory Augmentation, significantly improve LLM performance, suggesting that LLMs may have latent planning capabilities that can be unlocked through the right combination of context, structure, and guidance.

strengths:
The paper presents a highly original approach to addressing the limitations of large language models (LLMs) in autonomous planning. It introduces the Algorithm-of-Thoughts (AoT+), an enhanced prompting technique that builds upon the Algorithm of Thoughts (AoT) approach. By activating what the authors term "System 3 thinking," a more deliberate decision-making process, the paper challenges the perceived boundaries of LLMs in complex planning tasks. The use of random solution traces and memoization to improve the performance of LLMs in planning further highlights the novelty of this work.

The paper maintains a high standard of quality in terms of its depth of analysis. It conducts experiments with a diverse set of language models and various prompting strategies, resulting in a comprehensive evaluation of the proposed methods. The authors effectively communicate complex concepts through clear figures and tables, and the structure is logical and easy to follow. The paper begins by identifying the limitations of prior work, proceeds to verify the efficacy of the proposed techniques through experiments, and concludes with an extensive evaluation of its findings.

By addressing LLMs’ limitations in planning tasks and proposing novel enhancements, this paper significantly contributes to advancing the problem-solving and decision-making capabilities of language models.

weaknesses:
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.

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.

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.

The paper lacks details on the implementation of memoization, which makes it somewhat unclear.

questions:
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.

What considerations should be made when representing complex states, such as those in environments like ALFWorld?

How is memoization actually incorporated in AoT+? Does it involve cache the tokens for problem definitions?
</content>
</thread_object>

</thread>
<thread>
creation date:
1729981417569

thread_type:
official_review

<thread_object>
creator: reviewer_mutu

<content>
summary:
This paper proposes AoT+, a new prompting technique based on the previous work AoT, in research of LLM's ability for planning. The authors analysed the limitations of previous work, such as CoT, ToT, AoT. And then as a pre-study, it is showed that using random solution traces will not degrade the performance in comparison to AoT.
The authors further hypothesised that state hallucinations are due to continuous recomputation and tracking of the current state after each action. Based on this hypothesis, the authors introduced memoization in AoT+, inspired by dynamics programming. It is further shown that the attention weighs more on non-solution steps in AoT+.
The results demonstrate AoT has satisfactory performance improvement against other baselines and reduces the token usage.

The proposed method is based on previous AoT together with memoization and random traces. The method is simple yet effective. The paper shows promising results and improvement in comparison with baselines.  However, The paper itself lacks explanation in implementation of the proposed method. For example, it is unknown that how the authors interweave the correct solution path with random trajectories in 4.1 or how is memoization done in 4.2. Furthermore, the experiments can be done in a more consistent setting and more human performance data should be compared to support "out-competing human baselines". Until these concerns are resolved, this paper should be considered for a weak reject.

strengths:
* The paper conducted proper experiments on attention to support the hypothesis about state hallucination. 
* The proposed method shows promising results in higher performance and lower token usages.

weaknesses:
* This paper would benefit from examples of AoT and AoT+, similar to how it benefits from examples of CoT.
* 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. I quote from their abstract: "randomly replacing labels in the demonstrations barely hurts performance on a range of classification and multi-choice tasks, consistently over 12 different models including GPT-3".
* The authors can improve the illustration of the results by showing variance, confidences interval and other related statistical metrics, for example, in Table 3.
* 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.
* Figure 1 and Figure 4 is not informative. Furthermore, the paper itself lacks descriptions of actual details of pipeline.
* Though experiments to verify random solution traces and memoization are conducted, it is noticed they are done in different models and/or domains. It would be more convincing for extra ablation study under same settings in Section 5.2 main results.
* The 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", though partially supported by a experiment in attention, is not fully explained or validated over the length of solution trace.

questions:
* I think there might be a grammar error with the sentence: (L339) "Table 3 demonstrates the more structured attention mechanism as a shift towards the visited states, resulting from our AoT+ approach with memoization." How is "memoization" implemented? What is the exact prompt modification? Why is this not presented in the main paper? Why does memoization prevent state identification?
* What does CoT-SC mean in Table 1? It is not explained in the paper.
* In Section 4.2: What specific version of LLaMA-13B did you use?
* For random solution trajectories, what is the percentage of solution path? 
* How do you incorporate memoization into the proposed method?
* Readability of figure 1 and figure 4 should be improved.
* Figure 3 should be referred as a Table.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730447291964

thread_type:
official_review

<thread_object>
creator: reviewer_xu54

<content>
summary:
This paper explores the capabilities of LLM in autonomous planning, addressing their previous limitations when compared to human performance. Further, this paper proposes a new prompting method that enable LLMs to generate long-horizon plans autonomously.

strengths:
- It presents a significant advancement in the autonomous planning capabilities of LLMs, demonstrating their potential to match or exceed human performance.
- This paper proposes a prompting strategy to generate long-horizon plans.

weaknesses:
- First, the identification of your performance gap has already been established[1].
- However, several key baselines are missing. Although significant research addresses planning optimization strategies, much of it does not conduct experiments in the blocksworld domain [2-4]. Furthermore, baseline [5], which even operates in blocksworld, has not been directly compared.
- Given that your method relies on search-based techniques, it would be beneficial to include comparisons with MCTS-Decoding or A*, as these are also search-based approaches. Please explain why these specific search-based approaches were not included. 

If you can reasonably resolve my issue, I will reconsider my score.

[1] Stechly et al. Chain of Thoughtlessness? An Analysis of CoT in Planning

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

[3] Shinn et al. Reflexion: Language Agents with Verbal Reinforcement Learning

[4] Hu et al. Tree-Planner: Efficient Close-loop Task Planning with Large Language Models

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

questions:
See Weakness for more details.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730703506810

thread_type:
official_review

<thread_object>
creator: reviewer_9ec5

<content>
summary:
This paper investigates the planning capabilities of Large Language Models (LLMs) and presents an improved prompting technique which authors refer to as AoT+ because the method has been built on a previous method referred to as AoT. While current LLMs exhibit limited efficacy in complex planning tasks that demand multi-step, long-term reasoning, traditional methods such as Chain-of-Thought (CoT) and Tree-of-Thought (ToT) prompting encounter notable challenges due to lack of integrated error correction which limits their performance in planning scenarios. Both CoT and ToT lack the flexibility to backtrack, resulting in inadequate performance on benchmarks like Blocksworld. AoT that this paper has been built on enhances planning accuracy by incorporating human-like intuition and backtracking strategies. The proposed AoT+ technique introduces periodic structured state generation, which reiterates the problem state to help LLMs concentrate on pertinent information and reduce cognitive overload, along with random trajectory augmentation that uses random solution paths interspersed with correct steps, facilitating easier prompt creation while ensuring high accuracy. The effectiveness of AoT+ is validated through various experiments demonstrating its superior performance over existing methods across various tasks, including Blocksworld and Logistics, without the need for external verification tools. By utilizing structured prompts that help LLMs in state management and heuristic search, AoT+ also decreases token usage and computational time compared to other frameworks, enhancing its practicality for real-time applications.

strengths:
Although the work has been built on existing AoT work, it still shows several strengths including: 
- Achieving state-of-the-art performance across complex planning benchmarks without the need for external verification tools, 
- Unlike approaches like Tree-of-Thought (ToT) that require extensive API requests and computational resources, AoT+ operates efficiently within a single-prompt framework, cutting down on token usage and latency. This improvement is also observed in AoT but token counts in AoT+ is more efficient.
- The use of random solution trajectories in AoT+ (instead of rigid, human-crafted sequences) makes it easier to generate prompts and apply the method across various planning problems.
- By leveraging memoization-inspired techniques for periodic state regeneration, AoT+ helps to improve issues around state hallucination (errors in tracking problem states), enhancing the model’s ability to stay on track over multi-step tasks.
- AoT+ demonstrates consistent performance improvements across various LLMs indicating its model agnostic nature.

weaknesses:
Authors have done great work, and can potentially improve the paper more by addressing the following:
- In terms of presentation I expect a more clear diagram explaining different stages of the proposed method. It took me some time to get a better sense of the proposed method by going through the details in methodology section. 
- While AoT+ performs well on the benchmarks reported in the paper, evaluation on real-world planning tasks like pathfinding for robotics would strengthen the work.
- While AoT+ addresses state hallucination issues, the paper doesn’t provide a detailed error analysis of where these hallucinations occur. Identifying specific failure points would offer valuable insights for refining state-tracking strategies.

questions:
- Can you provide specific examples of common failure modes for AoT+, particularly regarding state hallucinations? Are there particular problem types or scenarios where these issues are more prevalent?
- How interpretable are the decision paths generated by AoT+? Can users trace the model’s reasoning steps and identify where an error may have occurred in the planning sequence?
- Would incorporating intermediate reward structures within AoT+ improve long-horizon planning accuracy by incentivizing the model to reach sub-goals?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730714521536

thread_type:
official_review

<thread_object>
creator: reviewer_ngcl

<content>
summary:
This paper investigates whether Large Language Models (LLMs) can effectively generate long-horizon plans autonomously, without requiring external verification tools or complex frameworks. The authors introduce AoT+ (Algorithm-of-Thoughts Plus), an enhanced prompting technique that builds upon the original Algorithm of Thoughts (AoT) approach. The paper suggests that LLMs may possess latent planning capabilities that can be activated through appropriate structuring of the problem-solving process, without requiring external verification tools or complex frameworks.

strengths:
The paper presents a novel perspective challenging both overly pessimistic and optimistic views of LLMs' planning capabilities.
The AoT+ innovations are creative combinations of existing ideas since it uses periodic state regeneration to manage attention/cognitive load.
There is comprehensive empirical evaluation across multiple challenging benchmarks, such as clear ablation of components through comparison of AoT vs AoT+
The paper has well-structured progression of ideas from problem motivation to solution.

weaknesses:
The paper focuses heavily on successful cases but lacks systematic analysis of where AoT+ fails.
While the paper compares AoT vs AoT+, it doesn't fully isolate the impact of each innovation.
The AoT+ assumes we have a pddl instance of the problem, so I'm not sure if this method is scalable to general domain.

questions:
Is there any scalable way to promote AoT+?
</content>
</thread_object>

</thread>
<thread>
creation date:
1733141000895

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Summary of the Discussions

comment:
We are deeply grateful to all reviewers for their active engagement during the rebuttal period. Their thoughtful feedback helped us enhance our paper in multiple dimensions, from clarifying implementation details to including new ablation studies that further validate our method's effectiveness. These additions complement our already comprehensive evaluation across four benchmarks using 9 different LLMs of varying scales and accessibility (both open-source and proprietary).

**New Experimental Results**

During the rebuttal period, we have:

- Incorporated comprehensive comparisons with important baselines: RAP, Self-Refine, and Tree-planner
- Analyzed state hallucination patterns with respect to solution depth (Figure 4)
- Conducted detailed ablation studies to isolate and validate each methodological innovation (Table 5)
- Added statistical rigor through confidence intervals for token usage analysis (Table 6)

Our new experimental results further reinforce AoT+'s consistent performance advantages across diverse models and tasks while maintaining significant reductions in token usage and computational costs.

**Conclusion**

We have been genuinely encouraged by the thoughtful and constructive nature of the feedback received. Throughout the rebuttal phase, we worked diligently to address all initial concerns raised by the reviewers. The positive outcome of this effort is reflected in the support for acceptance from all five reviewers, with no remaining unclarified concerns. We believe these improvements have substantially strengthened the paper's contribution to the field.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper investigates whether Large Language Models (LLMs) can effectively generate long-horizon plans without requiring external verification tools or complex frameworks. The authors introduce AoT+ (Algorithm-of-Thoughts Plus), an enhanced prompting technique that builds upon the original Algorithm of Thoughts. The enhancements are: adding periodic structured state generation, which reiterates the problem state to help LLMs concentrate on pertinent information and reduce cognitive overload, 2) random trajectory augmentation that uses random solution paths interspersed with correct steps. This led to improvement on a range of toy tasks.

Reviewers liked the strength of the results, especially the improvements across a range of tasks (9ec5, XU54, MUTU, 4iqA). They also point to several weaknesses, including no evaluation of real world tasks (9ec5) and missing baselines (4iqA, MUTU, XU54).

Overall all reviewers voted to accept the paper, so it is a clear accept.