Understanding the Planning of LLM Agents: A Survey

Abstract

This survey provides a comprehensive framework for understanding how Large Language Models (LLMs) can be integrated into autonomous agent architectures to perform complex, multi-step planning. The authors argue that conventional approaches—rigid symbolic planners (e.g., PDDL-based) and sample-inefficient reinforcement learning—are insufficient for modern planning demands, and that LLMs offer a flexible, knowledge-rich alternative when equipped with the right architectural primitives. The survey’s central contribution is a formal mathematical formulation of the planning procedure, $p=\text{plan}(E,g;\Theta ,P)$, and a systematic five-category taxonomy covering Task Decomposition, Multi-Plan Selection, External Module integration, Reflection, and Memory augmentation. By empirically validating representative methods across four benchmarks and analyzing their computational trade-offs, the work serves as both a structured reference and a roadmap for advancing LLM agents from passive text generators toward dynamic, autonomous systems capable of real-world interaction.

Chapter Summaries

• Ch. 1 — Introduction
• Ch. 2 — Taxonomy
• Ch. 3 — Task Decomposition
• Ch. 4 — Multi-Plan Selection
• Ch. 5 — External Planner-Aided Planning
• Ch. 6 — Reflection and Refinement
• Ch. 7 — Memory-Augumented Planning
• Ch. 8 — Evaluation
• Ch. 9 — Conclusions and Future Directions

Key Concepts

• Task Decomposition: The strategy of splitting a complex goal $g$ into a sequence of manageable sub-goals $[g_i]$, each addressed by a sub-plan, with two main variants: decomposition-first (rigid but structured) and interleaved (dynamic but hallucination-prone).
• Multi-Plan Selection: The generation of multiple candidate plans followed by an optimal selection strategy, ranging from self-consistency majority voting to structured tree-based search (Tree of Thoughts, MCTS), to reduce generation uncertainty.
• External Module Integration: The augmentation of LLM planning with external symbolic planners (PDDL, ASP) or program-based formalisms (ProgPrompt, PAL), delegating constraint-heavy reasoning to dedicated solvers while the LLM provides high-level guidance.
• Reflection and Refinement: An iterative feedback loop in which the agent critiques its past plan $p_i$ to produce a reflection $r_i$, which then conditions the generation of an improved plan $p_{i+1}$, enabling self-correction without explicit gradient updates.
• Memory-Augmented Planning: The retrieval of stored experiences or facts from an external memory module $M$ to inform plan generation, implemented either as Retrieval-Augmented Generation (RAG) or embodied memory via parameter-efficient fine-tuning (PEFT).
• Hybrid Planning Architectures: Systems such as CALM and SwiftSage that combine fast, heuristic LLM generation with slower, deliberate symbolic or policy-based verification, inspired by dual-process cognitive models.
• ReAct (Reasoning + Acting): An interleaved paradigm that alternates between generating reasoning traces and taking environmental actions, empirically shown to reduce hallucination relative to static chain-of-thought approaches.
• MemGPT Storage Abstraction: A memory management model treating the LLM context window as RAM and external storage as disk, enabling long-horizon planning beyond fixed context limits.

Key Equations and Algorithms

• General Planning Formulation: $p=\text{plan}(E,g;\Theta ,P)$ — defines the agent’s planning procedure as generating an action sequence conditioned on environment $E$ and goal $g$, parameterized by model weights $\Theta$ and prompt $P$.
• Task Decomposition Sub-Plan: $p_i=\text{sub-plan}(E,g_i;\Theta ,P)$ — formalizes the recursive breakdown of a complex goal into independently plannable sub-goals.
• Self-Consistency Majority Vote: ${\text{Plan}}_{\text{opt}}={\mathrm{argmax}}_p{\sum }_i\mathbb{I}(p=p_i)$ — selects the optimal plan by plurality vote across an ensemble of independently sampled plans.
• Self-Consistency Aggregation (Final Answer): $y_{final}={\text{argmax}}_{c\in \{c_1,\dots ,c_n\}}P(c\mid \text{questions})$ — determines the final answer by selecting the most frequent output across multiple sampled reasoning chains.
• LLM A* Heuristic: $f(n)=g(n)+h_{\text{LLM}}(n)$ with $h(n)=\text{ChebyshevDistance}(n,\text{target})$ — combines traditional path cost with an LLM-derived heuristic to guide search toward the goal.
• Tree of Thoughts State Selection: $V(s)={\max }_{s^{\prime }\in \text{children}(s)}(R(s^{\prime })+\gamma V_{est}(s^{\prime }))$ — evaluates candidate reasoning states using immediate reward and discounted future value estimates.
• Reflexion Feedback Loop: ${\pi }_{new}(a|s)\leftarrow {\pi }_{old}+\alpha \cdot \nabla {\mathcal{L}}_{verbal}(\text{trajectory},\text{critique})$ — updates agent policy via verbal critiques of past trajectories rather than explicit reward gradients.
• Recency-Relevance Retrieval Score: $Score=f(recency,relevance)$ — governs memory retrieval by jointly weighting temporal recency and contextual relevance of stored experiences.
• MemGPT Storage Model: $Storag{e}_{total}=RA{M}_{context}+Dis{k}_{external}$ — abstracts total agent memory into in-context (fast) and external (persistent) tiers to manage context window limitations.
• Performance-Efficiency Relationship: $P\propto E$ — empirically establishes that planning performance scales with token expenditure, necessitating cost-efficiency trade-offs in deployment.
• Success Rate Metric: $SR=\frac{N_{success}}{N_{total}}\times 100$ — quantifies task completion as the percentage of successfully completed tasks out of total attempts.

Key Claims and Findings

• Conventional symbolic planners and reinforcement learning methods are inadequate for general-purpose agent planning due to brittleness to errors and poor sample efficiency, respectively, motivating the shift to LLM-based architectures.
• Decomposition-first strategies offer greater structural reliability, while interleaved decomposition strategies offer fault tolerance at the cost of increased hallucination risk; neither approach dominates universally.
• Planning performance empirically scales with token expenditure ($P\propto E$), meaning more capable planning is achievable but at a direct computational cost, creating a fundamental deployment trade-off.
• Hybrid architectures that combine LLM fast-thinking with symbolic slow-thinking (e.g., CALM, SwiftSage) achieve greater decision stability than either subsystem alone.
• Current evaluation methodologies are insufficient: binary task completion metrics fail to diagnose intermediate reasoning failures, and the absence of multi-modal environmental feedback does not reflect real-world complexity.
• RAG-based memory and parameter-efficient fine-tuning represent distinct trade-off points for memory augmentation: RAG offers flexibility and retrieval precision, while PEFT embeds knowledge into model weights at a training cost.
• The “golden path” constraint in current benchmarks—requiring a specific sequence of actions for success—artificially limits the assessment of agent creativity and generalization.
• Unifying unstructured LLM knowledge with structured knowledge graphs is identified as a key architectural direction for improving factual consistency and grounding in future planning systems.

How the Parts Connect

The survey follows a coherent pedagogical progression: the introductory chapters (Group 1) establish the formal problem definition, the limitations of prior methods, and the five-category taxonomy that structures the entire work. Groups 2 and 3 then systematically instantiate this taxonomy by examining specific mechanisms—Task Decomposition and Multi-Plan Selection in Group 2, and External Modules, Reflection, and Memory in Group 3—providing algorithmic formulations and representative architectures for each. Group 4 closes the loop by critiquing how current benchmarks fail to adequately evaluate these mechanisms and by proposing concrete architectural roadmaps, such as MemGPT-style memory management and ReAct-style interleaved reasoning, that address the deficiencies identified throughout. The result is a structure that moves from why and what (taxonomy and formalism), through how (mechanism-by-mechanism analysis), to how well and what next (evaluation critique and future directions).

Internal Tensions or Open Questions

• Decomposition rigidity vs. hallucination risk: Decomposition-first methods are more structured but less adaptive, while interleaved methods are more flexible but more prone to hallucination; the survey identifies this trade-off but does not resolve it with a general solution.
• Performance-efficiency tension: The empirical finding that $P\propto E$ implies that the most capable planning approaches are also the most computationally expensive, presenting an unresolved deployment challenge for resource-constrained settings.
• Benchmark inadequacy: Current benchmarks rely on binary success metrics and lack multi-modal feedback, meaning reported performance figures may not transfer to real-world settings—yet the survey does not propose a fully realized replacement benchmark.
• “Golden path” constraint: Evaluation environments that require a single prescribed action sequence penalize valid alternative plans, undermining the assessment of generalization; this is flagged as an open problem without a concrete resolution.
• RAG vs. PEFT trade-off: The survey contrasts retrieval-augmented and parameter-embedded memory strategies but leaves open the question of when each is preferable and whether they can be effectively combined.
• Hallucination in long-horizon planning: Context length limitations and accumulated hallucination errors in long-horizon tasks are identified as critical failure modes, but no definitive mitigation strategy is established within the survey’s scope.
• Generalization of neural vs. hybrid planners: The comparison of pure neural LLM-based planners versus hybrid symbolic integrations raises unresolved questions about which approach generalizes better across novel environments.

Terminology

• Planning Procedure: As used in this survey, the formal function $p=\text{plan}(E,g;\Theta ,P)$ that maps an environment state and goal to an executable action sequence using an LLM parameterized by weights $\Theta$ and prompt $P$.
• Interleaved Decomposition: A dynamic task decomposition strategy in which sub-goals are generated and executed in alternation with environmental feedback, as opposed to being fully specified before any action is taken.
• Reflection: A self-critique mechanism in which the agent generates a verbal assessment $r_i$ of a past plan’s failures, used to condition the generation of an improved subsequent plan without gradient-based updates.
• Golden Path Constraint: An evaluation artifact in which a benchmark only accepts one specific sequence of actions as successful, penalizing functionally equivalent but structurally different valid plans.
• Embodied Memory: Memory integration achieved by encoding knowledge directly into model parameters via fine-tuning (e.g., PEFT), as opposed to storing and retrieving it externally at inference time.
• CALM Action Selection: A hybrid planning algorithm in which candidate actions generated by an LLM are re-ranked by a Deep Reinforcement Relevance Network (DRRN) policy conditioned on environmental text state.
• Verbal Critique: In the context of the Reflexion framework, a natural-language feedback signal generated by the agent or an evaluator that describes trajectory failures and guides policy improvement without explicit reward signals.
• Plan Feasibility: The degree to which a generated plan can actually be executed in the target environment without violating physical, logical, or contextual constraints—identified as a recurring failure mode in current LLM agent systems.

Connections to Existing Wiki Pages

• index — This survey directly extends the conceptual foundations of agent cognition, planning, and memory covered in this module, providing formal mathematical grounding for the mechanisms introduced there.
• what-is-agent-memory — The survey’s treatment of RAG-based versus parameter-embedded memory and the MemGPT storage abstraction directly elaborates on the agent memory concepts described here.
• index — The survey provides the theoretical underpinning for the practical agentic architectures built in this course, grounding tooling and control structures in formal planning taxonomy.
• sec-07-control-structure-and-tooling — The survey’s discussion of external module integration and multi-plan selection directly corresponds to the control structure and tooling patterns described in this section.
• sec-11-caching-and-retrieval — The survey’s analysis of recency-relevance retrieval scoring and RAG-based memory architectures is closely related to the caching and retrieval mechanisms covered here.
• sec-06-limitations-of-llm — The survey’s identification of hallucination, context length limits, and plan feasibility failures as core LLM planning challenges aligns directly with the limitations discussed in this section.
• ch-03-agent-principles-and-characteristics — The survey’s formal taxonomy of agent planning capabilities (decomposition, selection, reflection, memory) provides precise technical definitions for the agent principles outlined in this chapter.
• ch-04-agent-architecture-components — The survey’s detailed treatment of memory modules, external planners, and reflection loops maps onto the architectural components surveyed in this chapter.
• ai-agents-in-production-observability-and-evaluation — The survey’s critique of binary success metrics and its advocacy for fine-grained step-wise evaluation directly informs the observability and evaluation practices discussed here.
• how-to-make-your-llm-more-accurate-with-rag-and-fine-tuning — The survey’s comparison of RAG and PEFT as competing memory integration strategies relates to and extends the accuracy-enhancement techniques covered in this page.
• sec-09-tooling-your-llms — The survey’s examination of program-based formalisms (ProgPrompt, PAL) and symbolic planner integration provides formal grounding for the LLM tooling strategies described here.
• index — The survey’s multi-plan selection strategies, including tree-based search and MCTS, are conceptually related to the graph-based orchestration patterns explored in this guide.
• index — The survey’s critique of reinforcement learning as sample-inefficient for planning and its Reflexion verbal-critique loop offer a complementary perspective to DeepSeek-R1’s RL-based reasoning incentivization approach.
• index — The survey’s hybrid architectures (CALM, SwiftSage) and formal planning taxonomy provide detailed technical content supporting the broader agent architecture and design principles covered in this section.