# Thought of Search: Planning with Language Models Through The Lens of Efficiency

arXiv: https://arxiv.org/abs/2404.11833 · HTML: https://mlsanity.com/paper/2404.11833/

## Key facts

- Cited by 32 papers in the map (data through 14 Oct 2026).
- Placed in Reasoning for agents, planning and code, one of 17 directions in LLM reasoning.
- Builds on 3 of its 21 references that are in the map.
- First posted on arXiv 18 Apr 2024.

## Placed in

- LLM reasoning / [Reasoning for agents, planning and code](https://mlsanity.com/lr/reasoning-for-agents-planning-and-code/)

## Builds on (most cited first, 3 of 3)

- [ReWOO: Decoupling Reasoning from Observations for Efficient Augmented Language Models](https://mlsanity.com/paper/2305.18323/) (2023)
- [Stream of Search (SoS): Learning to Search in Language](https://mlsanity.com/paper/2404.03683/) (2024)
- [Plansformer: Generating Symbolic Plans using Transformers](https://mlsanity.com/paper/2212.08681/) (2022)

## Built on by (most cited first, 30 of 32)

- [LLMs Still Can't Plan; Can LRMs? A Preliminary Evaluation of OpenAI's o1 on PlanBench](https://mlsanity.com/paper/2409.13373/) (2024)
- [PlanGenLLMs: A Modern Survey of LLM Planning Capabilities](https://mlsanity.com/paper/2502.11221/) (2025)
- [Deep Research: A Survey of Autonomous Research Agents](https://mlsanity.com/paper/2508.12752/) (2025)
- [LLMs as Planning Formalizers: A Survey for Leveraging Large Language Models to Construct Automated Planning Models](https://mlsanity.com/paper/2503.18971/) (2025)
- [System-1.x: Learning to Balance Fast and Slow Planning with Language Models](https://mlsanity.com/paper/2407.14414/) (2024)
- [Classical Planning with LLM-Generated Heuristics: Challenging the State of the Art with Python Code](https://mlsanity.com/paper/2503.18809/) (2025)
- [Chasing Progress, Not Perfection: Revisiting Strategies for End-to-End LLM Plan Generation](https://mlsanity.com/paper/2412.10675/) (2024)
- [Seemingly Simple Planning Problems are Computationally Challenging: The Countdown Game](https://mlsanity.com/paper/2508.02900/) (2025)
- [Successor-Generator Planning with LLM-generated Heuristics](https://mlsanity.com/paper/2501.18784/) (2025)
- [Language Models For Generalised PDDL Planning: Synthesising Sound and Programmatic Policies](https://mlsanity.com/paper/2508.18507/) (2025)
- [How Far Are LLMs from Symbolic Planners? An NLP-Based Perspective](https://mlsanity.com/paper/2508.01300/) (2025)
- [Cost-Awareness in Tree-Search LLM Planning: A Systematic Study](https://mlsanity.com/paper/2505.14656/) (2025)
- [Symmetry-Aware Transformer Training for Automated Planning](https://mlsanity.com/paper/2508.07743/) (2025)
- [PEARL: Self-Evolving Assistant for Time Management with Reinforcement Learning](https://mlsanity.com/paper/2601.11957/) (2026)
- [TAPE: Tool-Guided Adaptive Planning and Constrained Execution in Language Model Agents](https://mlsanity.com/paper/2602.19633/) (2026)
- [Weisfeiler-Leman Features for Planning: A 1,000,000 Sample Size Hyperparameter Study](https://mlsanity.com/paper/2508.18515/) (2025)
- [From Next Token Prediction to (STRIPS) World Models](https://mlsanity.com/paper/2509.13389/) (2025)
- [From Instruction to Event: Sound-Triggered Mobile Manipulation](https://mlsanity.com/paper/2601.21667/) (2026)
- [Evaluating the Process Modeling Abilities of Large Language Models -- Preliminary Foundations and Results](https://mlsanity.com/paper/2503.13520/) (2025)
- ["Don't Do That!": Guiding Embodied Systems through Large Language Model-based Constraint Generation](https://mlsanity.com/paper/2506.04500/) (2025)
- [Self-Improvement for Fast, High-Quality Plan Generation](https://mlsanity.com/paper/2605.03625/) (2026)
- [Planning in the LLM Era: Building for Reliability and Efficiency](https://mlsanity.com/paper/2605.21902/) (2026)
- [Make Planning Research Rigorous Again!](https://mlsanity.com/paper/2505.21674/) (2025)
- [Verbalized Algorithms: Classical Algorithms are All You Need (Mostly)](https://mlsanity.com/paper/2509.08150/) (2025)
- [LexiCon: a Benchmark for Planning under Temporal Constraints in Natural Language](https://mlsanity.com/paper/2510.05972/) (2025)
- [Iterative Deployment Improves Planning Skills in LLMs](https://mlsanity.com/paper/2512.24940/) (2025)
- [Policy-Guided Search on Tree-of-Thoughts for Efficient Problem Solving with Bounded Language Model Queries](https://mlsanity.com/paper/2601.03606/) (2026)
- [Personalized Medication Planning via Direct Domain Modeling and LLM-Generated Heuristics](https://mlsanity.com/paper/2601.03687/) (2026)
- [Textual Planning with Explicit Latent Transitions](https://mlsanity.com/paper/2602.04557/) (2026)
- [SPIN: Structural LLM Planning via Iterative Navigation for Industrial Tasks](https://mlsanity.com/paper/2605.14051/) (2026)

## Abstract (arXiv)

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.