Among the most important properties of algorithms investigated in computer science are soundness, completeness, and complexity. These properties, however, are rarely analyzed for the vast collection of recently proposed methods for planning with large language models. In this work, we alleviate this gap. We analyse these properties of using LLMs for planning and highlight that recent trends abandon both soundness and completeness for the sake of inefficiency. We propose a significantly more efficient approach that can, at the same time, maintain both soundness and completeness. We exemplify on four representative search problems, comparing to the LLM-based solutions from the literature that attempt to solve these problems. We show that by using LLMs to produce the code for the search components we can solve the entire datasets with 100\% accuracy with only a few calls to the LLM. We argue for a responsible use of compute resources; urging research community to investigate sound and complete LLM-based approaches that uphold efficiency.
Paper
Similar papers
Peer review
Summary
The paper analyst the use of LLM in planning, and propose to write the successor function and goal test in code instead of directly solving the problem. The paper showed experiments that using the code can get a higher accuracy and lower number of calls to the LLM compared to LLM-based solutions.
Strengths
The paper is very well-written and easy to follow. The discussion is very detailed and provide extra insights on the topic.
Weaknesses
- First of all, I think the conclusion is not surprising or bring any insights at all. The idea of letting LLM to write code instead of directly solve problems has extensively appear in LLM for reasoning [1], and more specifically on LLM for planning [2][3]. - Because the conclusion does not provide any big insights, I am expecting to see a strong experiment, which is not the case in this paper. The benchmark selected, are quite classic from different manners, and similar code has appeared on GitHub for at least a year. It is hard to justify whether the success of generating code is coming from LLMs remembering similar context from Github or they do have the ability to correctly generate code. And even in this case, the authors mentioned “The mistakes GPT-4 makes when producing the code repeat from one experiment to another”, which is not a good sign if one wants to deploy similar methods to more general applications. - One minor drawback is that I feel the authors failed to cover some related works that are quite close, for example the ones I mentioned in the first weakness. A more thorough literature review are recommended for a more convincing paper. [1]. Zhou, Aojun, et al. "Solving challenging math word problems using gpt-4 code interpreter with code-based self-verification." arXiv preprint arXiv:2308.07921 (2023). [2]. Liu, Bo, et al. "Llm+ p: Empowering large language models with optimal planning proficiency." arXiv preprint arXiv:2304.11477 (2023). [3]. Guan, Lin, et al. "Leveraging pre-trained large language models to construct and utilize world models for model-based task planning." Advances in Neural Information Processing Systems 36 (2023): 79081-79094.
Questions
I am concerned about the current need of human feedback to successfully generate the code. While I can see from the appendix that a large portion of them might need such feedback, can you provide some statistics about this?
Rating
4
Confidence
3
Soundness
3
Presentation
4
Contribution
2
Limitations
Yes.
Summary
The authors propose a position paper that argues current works for LLMs for planning waste significant compute, on top of having poor algorithmic and empirical performance. The authors also propose ideas on how to use LLMs more efficiently and effectively by using them to preprocess search algorithms instead of using them directly during search. More specifically, the proposed method consists of using the LLM to generate the successor generator and goal state checker, alongside user feedback.
Strengths
The paper has several strengths as a position paper. It provides a simple yet original idea, namely that researchers should strive for responsible usages of LLMs for planning in terms of computing efficiency and also provides arguments that this would actually improve the performance of LLMs for planning as well. The idea is complemented by an extensive survey of LLMs for planning methods with a summary of worst case complexities, and whether the algorithms are sound or complete. Furthermore, it is complemented by a novel methodology for using LLMs for planning which adheres to the authors' proposition: more efficient and effective LLMs for planning research. The experiments are extensive with a wide variety of planning benchmarks, implementation details, and results. The results are quite positive as summarised in Table 1, with minimal calls to LLMs in comparison to existing approaches. The authors are also transparent about the limitations of their approach in its current state, being that it requires user interaction. Nevertheless, this does not undermine the proposition of the position paper.
Weaknesses
With regards to the idea of the paper, there are no major weaknesses. Nevertheless, the paper could benefit from some additional details regarding experiments, and improved clarity in certain areas. - It may not be clear to some readers how %States could go over 100%. By its definition in line 344-345, it is not clear whether visiting the same state twice double dips into the percentage or not, but from the next 2 sentences, it does seem to be the case. - Minor formatting issue: the benchmark domains are not consistently capitalised, e.g. 24 game and crossword in line 357 but elsewhere they are capitalised such as in Table 1 and page 8. - Although the focus of the paper is in LLMs for planning, the paper misses more general related work regarding learning for planning/generalised planning. Such methods are magnitudes of orders more efficient than LLMs in evaluating learned heuristics (ToT or GoT in LLM terminology) or policies and solve problems magnitude of orders larger than problems solved by LLM research. Example works include learned heuristics [1] or generalised policies [2], as well as foundation models for planning [3]. [1] Simon Ståhlberg, Blai Bonet, Hector Geffner: Learning General Optimal Policies with Graph Neural Networks: Expressive Power, Transparency, and Limits. ICAPS 2022: 629-637 [2] Dominik Drexler, Jendrik Seipp, Hector Geffner: Expressing and Exploiting Subgoal Structure in Classical Planning Using Sketches. J. Artif. Intell. Res. 80 (2024) [3] Dillon Ze Chen, Sylvie Thiébaux, Felipe W. Trevizan: Learning Domain-Independent Heuristics for Grounded and Lifted Planning. AAAI 2024: 20078-20086
Questions
No questions or clarifications that could change my opinion.
Rating
7
Confidence
3
Soundness
3
Presentation
3
Contribution
4
Limitations
The authors adequately addresses limitations of their work, and also the checklist with appropriate justification.
Summary
Existing LLM-based planning approaches usually involve searching and multiple passes of the model, which leads to significant inefficiency and cost while failing to guarantee the correctness of the generated plans. Motivated by this issue, this paper first analyzes the soundness, completeness, and complexity of a series of existing planning methods, arguing that they do not meet the standard of these properties. A new algorithm, Thought of Search (ToS), is proposed to alleviate the heavy computing demand of the searching operation for planning. It queries LLMs for generating the code implementation of successor functions and goal tests. The proposed method achieves 100% success rate for four representative search problems, while the total time spent (on CPU) is shorter than or comparable with a single LLM evaluation time. Further discussion describes that, compared with other approaches, ToS is not only sound and complete but also more cost-effective and able to explore a much larger portion with only O(1) complexity.
Strengths
1. Impactful motivation. Recently, there have been increasing efforts to improve the planning ability of LLMs. However, since this line of research is still at its early stage, the efficiency of the proposed methods is easy to overlook, especially when the system contains multiple agents. Therefore, I strongly agree with the motivation of this paper (i.e., the need for sound and complete LLM-based approaches that uphold efficiency) and believe in its importance for future research. 2. Comprehensive analysis. The paper systematically and comprehensively studies the properties of twelve related works that are commonly used or recently proposed, providing convincing support for the authors’ claim and, more importantly, valuable information to the community. 3. Solid results. Across all four evaluated tasks, ToS consistently generates valid final solutions only and reaches 100% accuracy in a relatively short time. Notably, the searching operation is run on the CPU. These results are sufficient to demonstrate the effectiveness of the proposed method.
Weaknesses
1. Current works on code generation using LLMs show that the correctness of the generated code is not guaranteed. In this paper, the obtained implementations in the experiments are also not always valid at the first trial and require human feedback. Thus, I am slightly concerned about whether ToS can generalize to more difficult tasks while maintaining its nice properties. Nonetheless, this is likely to be alleviated by combining with some automated optimization techniques as discussed by the authors. Therefore, I am still relatively optimistic about this approach at this point. Further experiments (if any) to address this concern are welcome. 2. While the paper's contents are generally well organized, which I appreciate, there are quite a few typos and wrong words/phrases. For exemplification, a non-exhaustive list is written below. I highly recommend a careful and thorough check of the whole paper to fix all the mistakes. - Line 22: ‘The purpose of our work is precisely that.’ - Line 99: ‘Reflection’ - Line 323: ‘a lower than reported by the approaches accuracy’
Questions
See weaknesses
Rating
6
Confidence
3
Soundness
3
Presentation
2
Contribution
3
Limitations
The limitations have been discussed.
Summary
The authors propose a Thought of Search: thinking before searching strategy to solve Automated Planning problems using LLMs. They use the GPT-4 LLM to generate a Python code for generating successor states and goal test functions which are the crucial parts of any search. They argue that this method is sound and complete and requires the least calls to the LLM before successfully solving the problem when compared to the relevant literature.
Strengths
1. Analysis of Complexities for the existing methodologies of using LLM for Planning. 2. Innovative use of LLM to reduce the number of calls made to solve the problems.
Weaknesses
However, there are several concerns regarding the proposed work: 1. If the Large Language Model (LLM) is being used to generate successor and goal test functions, which are already intrinsic components of automated planners, it is unclear what improvement is being made. The inherent memory and time complexities associated with solving these planning problems are not addressed or mitigated by the proposed approach. It appears that the LLM is simply re-writing (a few components of) a more basic planner, which does not seem sufficiently innovative for a NeurIPS-level conference. 2. The process is not fully automated, as it requires human intervention to re-prompt the LLM until the correct code is generated. 3. The methodology would have been more compelling if it had included an exploration of generating useful heuristic functions.
Questions
1. Why did the authors use only GPT-4 for their experimentation? No reasons are presented in the paper. Presenting a comparison of the performance with different LLMs would have been interesting to see. 2. What is the need to use LLMs to generate successor and goal test functions and solve the planning problems with a naive blind search? Is the objective to evaluate GPT-4's capability to generate Python code, or to assess its reasoning ability in solving planning problems? 3. Comparing the number of calls to the LLM with other approaches may not be appropriate. Your methodology necessitates generating the search components once for each domain, whereas other approaches involve the LLM in solving every problem within the domain. A more relevant comparison would be the average time required to solve these problems and the success rate across different methodologies.
Rating
3
Confidence
5
Soundness
3
Presentation
3
Contribution
1
Limitations
1. Showcasing results with only GPT-4 model. 2. Incomplete comparisons with the other existing approaches as mentioned above.
Thanks for addressing my concerns and pointing out the connection between the literature I mentioned. I am still concerned about the novelty of this work being quite incremental. Although I agree with the authors that not all problems can be solved with PDDL, I do not think this part poses a significant enough challenge to the problem studied in this paper: translating human language description to a specific language of code. Given that existing planners also use search in their underlying architectures, the work seems just challenging LLM to generate a more popular language of code, Python, instead of PDDL. In my opinion, the current paper has not adequately addressed the strong connection with this NeurIPS paper. Instead of hiding this reference in a short number, I would like to see a full discussion on how the current paper is different enough from the NeurIPS paper. Furthermore, I personally believe that the transition gap between math reasoning problems and planning problems is bigger than from PDDL to Python. If the authors do believe Zhou et al. ICLR 2024 can be used as a cross-reference to support that LLMs can generate verifiable code with automatic feedback instead of human feedback used in the current paper, I do believe the contribution to be even smaller. Otherwise, the need for human feedback in the loop still seems to be a big challenge to the proposed algorithm.
# **Comparison with Guan et al.** Guan et al, NeurIPS 2023 propose a method that consists of three parts: domain construction, domain refinement by a human, planning with the refined domain. To construct the domain, an LLM is queried for action preconditions and effects on an action-by-action basis, providing it with the description of the action in a natural language and a (possibly incomplete) set of predicates. The LLM can provide not only action parameters, preconditions, and effects, but also potentially propose missing predicates. Few shot examples from a BlocksWorld domain are given in the prompt. The process is repeated once, with the list of full predicates from the first iteration. Additionally, PDDL problem instances are created, using the predicates from the domain generation process. The feedback is provided in two forms: 1. A symbolic validator VAL is run on domain and problem files, with the result being translated into natural language feedback. This feedback is mostly on the syntax of the generated PDDL model. 2. The generated PDDL domain is translated into a natural language and presented to a human expert. The expert provides an explicit feedback on missing and extra preconditions and effects of each action. Upon correspondence with the Guan et al. authors, we validated following conceptual differences from our work: 1. They are interested in actions only, assuming initial state and goal are given. Our work does not make this assumption; rather asks LLM to generate a goal function. 2. They feed the language model with targeted pieces of information (single action description one-by-one, predicates to use). We provide entire description of the problem and asks for a single successor function. 3. Their feedback on the generated PDDL is explicit and requires nuance understanding of modeling in PDDL (e.g., 'unnecessary precondition "no other object stacked on object ?x"'). While ours is mostly generic python code feedback (e.g., issues with shallow copy of a dictionary with list values, error trace) and generic logic (e.g., 'two of the operations are not symmetric, division and subtraction'). We agree that this comparison is interesting and will add the discussion to the paper. # **PDDL vs Python code generation** There is a conceptual difference between representing planning problems in PDDL and coding a search problem (successor function and goal test). To overcome the limitations of PDDL, modelers often resort to tricks like presenting additional predicates encoding the negation of modeled predicates, adding predicates that explicitly encode an information that could be derived from other predicates, such as (hand empty) in addition to (holding ?b) in BlocksWorld, because such derivation cannot be done in the preconditions and effects in classical planning, and would require axioms, which are rarely supported by existing planners. As a result, human validation of such PDDL models is often harder and requires more skills than validating code-based successor function/goal encoding.
# **Comparison with Zhou et al.** We share your belief that the transition gap between math reasoning problems and planning problems is large. Therefore, their approach requires independent interaction with LLM for every math problem. A search problem, however, should not require independent interactions with LLM for each problem. That is the main premise our work. A single interaction with LLM to generate successor and goal function can allow solving all problems in that domain. In our previous comment we only meant to highlight that success in Zhou et al's work indicate that LLMs can generate code and refine it with feedback. In our work we leverage this code generation and refinement ability of LLMs. But the similarity ends there. We highlight some of the differences between our work and Zhou et al. below: 1. They propose generation of code as a means to solve a given math problem and generate final answer. In our work, the final answer is the code itself. 2. Their approach is not iterative or incremental in nature, they propose generating a predefined collection of validators for a particular instance, regardless of the performance of previously generated validators. Ours iteratively fixes issues with the previously generated code. # **On the need for human feedback** The need to provide human feedback is shared by all approaches investigated in our work. In our case, the human feedback is needed on producing the solver and is not required once a sound solver is produced, as the solutions are then guaranteed to be correct. In the case of the previous approaches, the human feedback is needed to validate each and every one of the produced solutions, an almost impossible task. We are not aware of an acknowledgement of such a limitation in the existing literature. We hope that the challenge of alleviating the need for human feedback can be adequately addressed in future work. # **On novelty** Finally, We would like to emphasize that a large portion of our work focuses on filling the gap in the current literature on planning with LLMs with regard to the computational complexity and properties of the proposed algorithms. This investigation is essential for understanding approaches and building up on them. So, we believe, this investigation itself satisfies the novel contribution requirement. Additionally, none of the existing approaches use language models to generate code for search components, so that contribution is also novel.
Thank you for your clarification. This detailed comparison with Guan et al. is greatly helpful for judging the novelty of this paper. However, as the soundness of the proposed method comes directly from generating code format of the problems instead of solutions, a more thorough literature review on the effect of code interpreters on reasoning is needed, which should include, but not limited to Zhou et. al. Besides, to make the paper novel and impactful, the need of human feedback should also tried to be reduced given the fact the work like self-debug [1], which has been included in the rebuttal with other reviewers, have already appeared in coding for a long time. The current difference between this work and existing work, while not as simple as just changing a coding language from PDDL to Python, is still relatively simple and limited. Therefore, I am keeping my score at the moment.
We are happy to see that you acknowledge that papers mentioned by you are not reducing the novelty of our approach. We would like to again highlight the "On novelty" section in our previous response. Our contribution in this paper is so much more than the method we propose. We will update the paper with related work on code-generation. If you have any concrete work that reduces the novelty of our contributions, we would gladly alleviate your concerns. We would like to reiterate that reducing the need for human feedback should be a focus of a separate investigation.
Thank you for addressing my comments. I am still not convinced that the work produced in its current state is novel enough for the NeurIPS submission. The authors seem to see their methodology is applicable in cases where devising PDDL is harder. To generate feasible plans for realistic/near-to-realistic domains using the methodology proposed is still the same as a blind search and would require a lot of computation and resources. I read through the rebuttal responses for other reviewers. On automation - "Our preliminary investigation of feedback automation for ToS supports this as well." - do the authors provide this preliminary investigation in their paper? if so can you please point out where?
Our preliminary investigation of feedback automation is not part of this work. It is not clear to us whether reviewer's intention is that blind search is not as effective as the previous approaches (ToT, RaP, etc) or that blind search is not as effective as heuristic search on large realistic domains. Could you please clarify?
I thank the authors for their response and clarification. I also acknowledge that I have read the strengths and weaknesses pointed out in other reviews as well as the corresponding rebuttals but still stand with my rating. More specifically, I am still convinced by the message concerning the efficient usage of LLMs that the paper proposes with a focus on soundness.
We hope that our responses have strengthened your support for the paper. We would greatly appreciate if that could be reflected in your final score.
Keep the rating unchanged
I've read the authors' responses and am satisfied with them. I've read other reviewers' comments (especially uMM4 and 4XWb), and think their arguments are also quite valid. Based on all these, I choose to keep my rating unchanged. But I want to emphasize that my confidence score is not high (only 3).
We would like to emphasize the need for getting our message out there. People are mainly unaware of just how incredibly inefficient the approaches we investigate in this work are. To to take another perspective, each call to GPT-4o consumes roughly 0.2 kWh. Solving all 1362 tasks of 24 game with ToT (~100 calls to GPT4 per task) would consume around 27mWh, more than the average U.S. household uses in 2.5 years.
Decision
Accept (poster)