mlsanityData to 14 Oct 2026

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

arXiv 2404.11833 ↗First posted 18 Apr 2024cs.AIcited by 32

On the map: LLM reasoning → Reasoning for agents, planning and code

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.

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.

Builds on

3 of 21 references.

References · 3

  1. 2023ReWOO: Decoupling Reasoning from Observations for Efficient Augmented Language Modelscited by 184
  2. 2024Stream of Search (SoS): Learning to Search in Languagecited by 145
  3. 2022Plansformer: Generating Symbolic Plans using Transformerscited by 41

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 3; 2025: 18; 2026: 11.

32 papers.

Sort:

By area:

  1. 2024LLMs Still Can't Plan; Can LRMs? A Preliminary Evaluation of OpenAI's o1 on PlanBenchcited by 94
  2. 2025PlanGenLLMs: A Modern Survey of LLM Planning Capabilitiescited by 83
  3. 2025Deep Research: A Survey of Autonomous Research Agentscited by 66
  4. 2025LLMs as Planning Formalizers: A Survey for Leveraging Large Language Models to Construct Automated Planning Modelscited by 38
  5. 2024System-1.x: Learning to Balance Fast and Slow Planning with Language Modelscited by 35
  6. 2025Classical Planning with LLM-Generated Heuristics: Challenging the State of the Art with Python Codecited by 18
  7. 2024Chasing Progress, Not Perfection: Revisiting Strategies for End-to-End LLM Plan Generationcited by 11
  8. 2025Seemingly Simple Planning Problems are Computationally Challenging: The Countdown Gamecited by 9
  9. 2025Successor-Generator Planning with LLM-generated Heuristicscited by 7
  10. 2025Language Models For Generalised PDDL Planning: Synthesising Sound and Programmatic Policiescited by 7
  11. 2025How Far Are LLMs from Symbolic Planners? An NLP-Based Perspectivecited by 6
  12. 2025Cost-Awareness in Tree-Search LLM Planning: A Systematic Studycited by 5
20 more
  1. 2025Symmetry-Aware Transformer Training for Automated Planningcited by 5
  2. 2026PEARL: Self-Evolving Assistant for Time Management with Reinforcement Learningcited by 4
  3. 2026TAPE: Tool-Guided Adaptive Planning and Constrained Execution in Language Model Agentscited by 4
  4. 2025Weisfeiler-Leman Features for Planning: A 1,000,000 Sample Size Hyperparameter Studycited by 2
  5. 2025From Next Token Prediction to (STRIPS) World Modelscited by 2
  6. 2026From Instruction to Event: Sound-Triggered Mobile Manipulationcited by 2
  7. 2025Evaluating the Process Modeling Abilities of Large Language Models -- Preliminary Foundations and Resultscited by 1
  8. 2025"Don't Do That!": Guiding Embodied Systems through Large Language Model-based Constraint Generationcited by 1
  9. 2026Self-Improvement for Fast, High-Quality Plan Generationcited by 1
  10. 2026Planning in the LLM Era: Building for Reliability and Efficiencycited by 1
  11. 2025Make Planning Research Rigorous Again!cited by 0
  12. 2025Verbalized Algorithms: Classical Algorithms are All You Need (Mostly)cited by 0
  13. 2025LexiCon: a Benchmark for Planning under Temporal Constraints in Natural Languagecited by 0
  14. 2025Iterative Deployment Improves Planning Skills in LLMscited by 0
  15. 2026Policy-Guided Search on Tree-of-Thoughts for Efficient Problem Solving with Bounded Language Model Queriescited by 0
  16. 2026Personalized Medication Planning via Direct Domain Modeling and LLM-Generated Heuristicscited by 0
  17. 2026Textual Planning with Explicit Latent Transitionscited by 0
  18. 2026SPIN: Structural LLM Planning via Iterative Navigation for Industrial Taskscited by 0
  19. 2026Zero-Shot Active Feature Acquisition via LLM-Elicitationcited by 0
  20. 2026Planning with Transformers: Chain of Computation and Structured Context Windowscited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2026Analysis of Optimality of Large Language Models on Planning Problems
  2. 2024Query-Efficient Planning with Language Models
  3. 2025Large Language Models for Planning: A Comprehensive and Systematic Survey
  4. 2023On the Planning Abilities of Large Language Models : A Critical Investigation
  5. 2023Can LLMs Fix Issues with Reasoning Models? Towards More Likely Models for AI Planning
  6. 2024When is Tree Search Useful for LLM Planning? It Depends on the Discriminator
  7. 2024Thinking Forward and Backward: Effective Backward Planning with Large Language Models
  8. 2025Complex LLM Planning via Automated Heuristics Discovery