Research map / Large language models / Agents, code and math
Thought of Search: Planning with Language Models Through The Lens of Efficiency
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
The paper analyzes soundness, completeness and LLM-call complexity of recent LLM planning methods, then proposes using GPT-4 to generate Python successor and goal-test code so that standard BFS/DFS solves four search datasets at 100% accuracy with only a few LLM calls.
Problem
Recent LLM-based planning methods (ReAct, ToT, RAP, LATS, etc.) are neither sound nor complete and require very many LLM calls, making them costly and unreliable for search problems.
Approach
Use an LLM once (with iterative, human-guided feedback) to generate Python code for the successor function and goal test, then run a classical sound and complete search (BFS/DFS) on that code without further LLM calls, so correctness can be validated before search.
Key results
- The generated successor and goal-test code solves all 1362 24-game instances, all 20 mini crosswords, all 502 BlocksWorld tasks and all 4000 PrOntoQA questions at 100% accuracy.
- The proposed approach requires only about 1-3 LLM interactions per component (e.g., 2.2 for 24 game, 3.8 for crosswords), versus hundreds of thousands of calls for RAP, ToT and LATS in the thought-experiment estimates.
- Estimated LLM-based cost for RAP is about $14,000 and for LATS about $16,000 versus a few dollars for the proposed approach on these datasets.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use GPT-4 to generate successor and goal-test code, then run BFS instead of using LLM-driven search | 24 Game planning · 24 Game (1,362 instances) | accuracy: 75% -> 100% | Helped |
| Use GPT-4 to generate successor and goal-test code, then run DFS instead of LLM-driven Tree of Thoughts | Mini crossword planning · Mini crosswords (20 games) | LLM calls: ≈200 times in the worst case for each of the 20 games | Helped |
| Use generated symbolic search components and BFS rather than LLM-based MCTS and self-consistency | PrOntoQA reasoning · PrOntoQA (4,000 questions) | answer accuracy: 94.2% -> 100% | Helped |
| Use generated symbolic search components and BFS rather than LLM-based MCTS and self-consistency | PrOntoQA reasoning · PrOntoQA (4,000 questions) | proof accuracy: 78.8% -> 100% | Helped |
| Generate successor and goal-test code once and reuse it for search, rather than invoking an LLM throughout search | Thought of Search · 24 Game | LLM calls: ≈100 calls to the LLM -> 1.2 interactions on average for the successor function and 1 interaction for the goal test | Helped |
| Generate successor and goal-test code once and reuse it for search, rather than invoking an LLM throughout search | Thought of Search · Mini crosswords | LLM calls: 2.4 interactions on average to produce a valid successor function, and 1.4 interactions on average to produce the goal t | Helped |
| Generate successor and goal-test code once and reuse it for search, rather than invoking an LLM throughout search | Thought of Search · BlocksWorld | LLM calls: 2.8 and 1 iterations on average | Helped |
| Generate successor and goal-test code once and reuse it for search, rather than invoking an LLM throughout search | Thought of Search · PrOntoQA | LLM calls: 1.6 and 1 iterations on average | Helped |
| Use set-based state representations rather than dictionaries of lists or object pairs | Thought of Search BFS · BlocksWorld (502 tasks) | total solve time: 0.56s to 9.7s | Helped |
Surprising findings
- Prior LLM-planning methods explore only a tiny fraction of the state space (e.g., 0.02% for 24 game) and often revisit states many times, which explains their low accuracy.
- Generated successor functions differ in runtime by up to 3.5x in the 24 game, showing code efficiency varies across LLM generations.
Limitations
- Relies on human feedback to validate and correct generated code; the process is not automated.
- Evaluated only on small instances (e.g., BlocksWorld with 4-5 blocks) where uninformed BFS/DFS is feasible; scalability to larger state spaces is not shown.
- Correctness of the code is judged against the developer's understanding and test instances, so corner cases may be missed.
Experimental setup
Datasets: 24 game (ToT suite, 1362 instances) mini crosswords (20 games) BlocksWorld (502 instances) PrOntoQA (4000 questions)
Benchmarks: 24 game mini crosswords BlocksWorld PrOntoQA
Metrics: accuracy number of LLM calls total runtime states explored
Baselines: IO CoT ReAct ReWOO RAP ToT GoT Reflexion LATS
Builds on: Tree of Thoughts Reasoning via Planning LLM-Modulo generalized planning policy generation with LLMs
Closest papers by meaning
- Planning in Natural Language Improves LLM Search for Code Generation (ICLR 2025 · similarity 0.91)
- Classical Planning with LLM-Generated Heuristics: Challenging the State of the Art with Python Code (NeurIPS 2025 · similarity 0.90)
- SPIRAL: Symbolic LLM Planning via Grounded and Reflective Search (AAAI 2026 · similarity 0.90)
- Can LLMs Fix Issues with Reasoning Models? Towards More Likely Models for AI Planning (AAAI 2024 · similarity 0.90)
- Planning Anything with Rigor: General-Purpose Zero-Shot Planning with LLM-based Formalized Programming (ICLR 2025 · similarity 0.89)
- SayCanPay: Heuristic Planning with Large Language Models Using Learnable Domain Knowledge (AAAI 2024 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.