When LLMs Learn to Plan: An Odyssey Through Planning Capabilities of Large Language Models

This post presents a panoramic review of LLM-based planning research, anchored by the survey "Large Language Models for Planning: A Comprehensive and Systematic Survey" (Cao P. et al., arXiv:2505.19683). It frames a central paradox: LLMs can discuss quantum field theory fluently yet fail at trivially simple sequential tasks — motivating the question of how to make machines dance between symbolic reasoning and neural intuition.

Key points

1. External planners as LLM "co-pilots"

• Hierarchical Planning with Knowledge Graph-RAG + Symbolic Validator (Cornelio et al., 2025, arXiv:2504.04578): decomposes tasks hierarchically and continuously compares expected vs. observed world states, achieving formal correctness guarantees and reportedly 40%+ success-rate improvements on complex tasks.
• LLM+MAP (Chu et al., 2025, arXiv:2503.17309): multi-agent planning for bimanual robots, combining LLM task decomposition with PDDL consistency; with GPT-4o it reduced planning steps by 35% while raising success by 28%.
• LLM-Modulo (Gundawar et al., 2024, arXiv:2411.14484): accepts LLM imperfection and uses sound verifiers with rejection sampling; scheduling success rose from 62% to 94% with logical guarantees on outputs.
• Solver-guided prompting (Wu & Mitra, 2024): visual feedback lifted GPT-4's success from 45% to 78% on standard problems, but all prompting strategies fail beyond a complexity threshold — LLMs match patterns but lack deep search. Solver-guided fine-tuning (+22% on medium tasks) cannot teach capabilities beyond the training distribution.

2. Memory-augmented planning

• Personalized agents with editable memory graphs (Cao et al., 2024): persistent graph nodes with timestamps, confidence, and affective weights; +31% user satisfaction, 89% memory-edit accuracy.
• ExRAP (NeurIPS 2024): hypothesis → verify → update retrieval loops for non-stationary embodied environments, 3x faster adaptation.
• MemGPT (2023): treats the LLM as its own OS-style memory manager, paging between main context and external storage; maintained 92% factual consistency over 100k-token dialogues vs. 63% for standard LLMs past 8k tokens.

3. Self-improvement

• AgentGen (SIGKDD 2024): LLM-generated environments/tasks synthesize million-scale trajectories; +27% generalization to unseen tasks, ~90% lower data cost.
• SPPO: self-play preference optimization lifted tool-use success from 42% to 81%.
• WebRL (ICLR 2024): self-evolving curriculum RL in real web environments; 68% average success vs. 41% for supervised learning.
• Rest-MCTS* (NeurIPS 2024): Monte Carlo Tree Search generates process rewards; +19 percentage points on math reasoning accuracy.

4. Search strategies

• ADAPT (NAACL 2024): on-demand adaptive task decomposition, +40% planning efficiency.
• HuggingGPT: decomposes requests and delegates to specialist models.
• Tree of Thoughts / Graph of Thoughts (AAAI 2024): branching and cross-branch fusion; 2.3x story diversity, +31% novel proof discovery.
• LATS: MCTS with LLM as value function; 83% shelter-building success in Minecraft within 10 steps vs. 21% for greedy policies.

5. Evaluation reality check

• Planetarium (NAACL 2025, Zuo M. et al.): 96.1% of generated PDDL plans are syntactically correct and 94.4% solvable, but only 24.8% semantically correct — LLMs can write plausible-looking plans that miss user intent.
• WebArena: only ~15% success on real websites; agents tuned on clean APIs are brittle against layout changes and popups.
• Mind2Web: GPT-4V achieves 38% single-step but only 12% multi-step success; smaller models + tree search (34%) outperform it — bigger models ≠ better planners.
• ALFWorld: LLM-DP neuro-symbolic hybrid reaches 31% zero-shot success in unseen environments vs. 9% for pure LLMs.

6. Interpretability

• "To CoT or not to CoT?" (ICLR 2024): chain-of-thought helps math/symbolic tasks but may hurt commonsense planning.
• Confidence Matters (2024): self-correction is nearly useless above ~85% initial confidence; guided correction only helps in a 60–75% confidence band (+12%).
• "Do language models plan ahead for future tokens?" (CoLM 2024): GPT-2 representations encode information about the next 3–5 tokens.
• Iteration Heads (NeurIPS 2024): specific attention heads repeatedly activate during CoT, creating implicit iteration loops in autoregressive models.

Outlook

The post closes with three converging directions: (1) deep neuro-symbolic integration with differentiable architectures treating PDDL semantics as structural priors; (2) endogenous world models, e.g., WorldCoder (NeurIPS 2024), where models learn environments by writing and executing code; and (3) meta-planning — models that plan their own planning strategy. The core lesson: reliability comes not from perfect generation but from knowing when the system is imperfect.

Key references

1. Cao P., et al. (2025). *Large Language Models for Planning: A Comprehensive and Systematic Survey*. arXiv:2505.19683 2. Cornelio C., Petruzzellis F., & Lio P. (2025). *Hierarchical Planning for Complex Tasks with Knowledge Graph-RAG and Symbolic Verification*. arXiv:2504.04578 3. Chu K., et al. (2025). *LLM+MAP: Bimanual Robot Task Planning using Large Language Models and Planning Domain Definition Language*. arXiv:2503.17309 4. Gundawar A., et al. (2024). *Robust Planning with Compound LLM Architectures: An LLM-Modulo Approach*. arXiv:2411.14484 5. Zuo M., et al. (2025). *Planetarium: A Rigorous Benchmark for Translating Text to Structured Planning Languages*. NAACL 2025