Thought of Search: Planning with Language Models Through The Lens of Efficiency
This work tackles inefficiency and property neglect in LLM planning for the AI research community, offering a significant improvement but not a paradigm shift.
The paper addresses the lack of analysis of soundness, completeness, and complexity in LLM-based planning methods, proposing a more efficient approach that maintains these properties while achieving 100% accuracy on four search problems with few LLM calls.
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.