Skip to content

PlanGenLLMs: A Modern Survey of LLM Planning Capabilities

🕒 Published (v1): 2025-02-16 17:54 UTC · Source: Arxiv · Venue: ACL 2025 · link

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

A structured survey of LLM planning capabilities organized around six evaluation criteria—completeness, executability, optimality, representation, generalization, and efficiency—derived from Kartam and Wilkins (1990). It taxonomizes planning paradigms (task decomposition, LLM+classical planner, search algorithms, fine-tuning) and benchmarks across domains, exposing cross-system comparability gaps. The survey positions itself as a unified reference for connecting LLM planning research to agentic workflow engineering.

Problem

LLM planning systems are domain-specific and lack consistent evaluation criteria, making cross-system comparison intractable. Prior surveys either catalogued methods (decomposition, reflection, memory) or benchmarks in isolation, but none provided a unified performance framework applicable across domains. This fragmentation impedes identifying the best planner for novel tasks and slows progress on advanced planners.

Method

The survey adopts Kartam and Wilkins' (1990) classical AI planning evaluation framework and extends it to six criteria for LLM planners: (1) Completeness — does the system generate correct plans when feasible and recognize unsolvable instances? (2) Executability — are plans grounded to available objects/actions via object grounding, action grounding, sample-then-filter, or closed-loop replanning? (3) Optimality — are plans cost-minimal, achieved via LLM+optimizer (e.g., MILP with SCIP) or \(A^*\)-search-based methods? (4) Representation — are inputs/outputs encoded as NL, PDDL, LTL, Pythonic code, condensed symbols, or graphs? (5) Generalization — can planners transfer to out-of-distribution tasks via fine-tuning, generalized planning, or skill storage? (6) Efficiency — are LLM/world-model calls, token lengths, and model sizes minimized? For each criterion the authors survey representative systems and evaluation methods.

Key Contributions

  • Six-criterion evaluation taxonomy (completeness, executability, optimality, representation, generalization, efficiency) grounded in classical AI planning literature.
  • Unified taxonomy of planning paradigms: task decomposition (sequential/parallel/asynchronous/recursive), LLM+classical planner, search algorithms (BFS/DFS/MCTS/Greedy BFS), fine-tuning (planning-specific vs. generalized agentic).
  • Comprehensive survey of datasets—embodied (BlocksWorld, ALFWorld, ALFRED, VirtualHome), scheduling (TravelPlanner), games (Minecraft, SmartPlay), and downstream tasks (SWE-Bench, WebArena, GSM8K).
  • Evaluation method taxonomy: automated verifiers (VAL, BUTLER), ground-truth matching, human evaluation, LLM-as-a-judge; plus metric taxonomy (success rate, executability rate, constraint pass rate, optimality rate, inference time, token counts).
  • Curated paper list at https://github.com/wll199566/Awesome-LLM-Planning-Capability.
  • Identification of open challenges: hallucination in unsolvable-problem detection, multi-agent planning, representation alignment, and connection to agentic workflows.

Results

The survey is qualitative/taxonomic; it does not report aggregate benchmark numbers of its own. Key empirical findings cited from surveyed works include: - Top LLMs (GPT-4) and Large Reasoning Models (OpenAI o1) still fail on unsolvable planning instances due to hallucination (Aghzal et al., 2023; Valmeekam et al., 2024). - LLMs struggle with independent planning; hybrid LLM+classical planner systems (LLM+P, LLM-DP) outperform pure LLM planners on formal domains (Valmeekam et al., 2023b; Kambhampati, 2024). - Fine-tuning on generalized agentic datasets (Agent-FLAN, AgentOhana) improves planning without degrading general capabilities; narrow planning fine-tuning risks capability regression. - Efficiency techniques (Chain-of-Symbols, Thought of Search, AdaPlanner's one-shot generation) reduce LLM calls significantly vs. step-by-step baselines.

Limitations

  • No meta-analysis or quantitative aggregation across surveyed systems; comparison remains qualitative.
  • Evaluation criteria are assessed independently; interactions between criteria (e.g., optimality vs. efficiency trade-offs) are not formally analyzed.
  • Coverage is biased toward English-language, text-based planning tasks; multimodal and multilingual planning are underrepresented.
  • Multi-agent planning is identified as a gap but not surveyed in depth.
  • Hallucination in unsolvable-problem recognition is flagged as critical but no mitigation techniques are surveyed.
  • Rapidly moving field: survey (v3, Jun 2025) may not capture the most recent systems.

Relevance to Harnesses / Meta-Harnesses

This survey is directly relevant as a conceptual substrate for harness design: the six criteria (completeness, executability, optimality, representation, generalization, efficiency) map onto the core responsibilities of a planning meta-harness—ensuring generated plans are valid, grounded, cost-efficient, representable in the harness's action schema, and transferable across tasks. The closed-loop system taxonomy (implicit vs. explicit replanning on failure, feedback from validators/simulators/LLMs) describes exactly the control-flow logic a harness must implement to manage LLM planner failures at runtime. The survey's efficiency section—merging plans with shared prefixes, batching world-model checks, generating successor/goal-check functions once per tree node—provides concrete harness-level optimizations for reducing API cost in orchestration loops. Finally, the gap around multi-agent planning and agentic workflow integration points to an open design space where harness-level coordination (task routing, inter-agent communication, shared skill libraries) can compensate for what individual LLM planners lack.