When Language Models Learn to Plan: An Odyssey Through LLM-Based Planning

> *"Imagine standing at the entrance of a knowledge labyrinth built from thousands of papers. Your task is not to read every page, but to assemble a complete picture of how agents learn to 'think' — itself the most elegant planning problem."*

Prologue: From Parrot to Strategist

2023 marked a turning point for large language models (LLMs). They could fluently discuss Parisian cafés and derive quantum field theory, yet stumbled on trivially simple planning like "put on shoes before opening the door." This paradox gave rise to the field of LLM-based planning, which asks not only whether models can plan, but how machines can balance symbolic reasoning against neural intuition.

Planning, in the AI sense, means decomposing goals into executable action sequences and dynamically adjusting under uncertainty — the digital mirror of human "deliberate before acting" wisdom.

Act I: External Brains — Planners as the LLM's Co-Pilot

Hierarchical Planning with Knowledge Graphs and Symbolic Verification

Cornelio et al. (2025) proposed a framework decomposing complex tasks into subtasks and atomic action sequences, paired with a Symbolic Validator that continuously compares expected vs. observed world states — alerting immediately when, say, a robot tries to "put eggs in the fridge" with the door closed. The LLM acts as a creative director while the validator serves as a strict stage manager. Knowledge graphs serve as external memory: when planning to make pasta, the graph retrieves the causal chain "boil → drain → sauce" instead of letting the model hallucinate. Reported results: over 40% improvement in success rate on complex tasks with stronger cross-domain generalization.

LLM+MAP: Bimanual Coordination

Chu et al. (2025) treat each robotic arm as an independent agent: the LLM decomposes and assigns tasks, while PDDL guarantees logical consistency. With GPT-4o as the backend, planning steps dropped 35% while success rate rose 28% — suggesting that thinking at the right level of abstraction matters more than thinking more.

LLM-Modulo: Reliability Through Verification

Gundawar et al. (2024) embraced LLM imperfection rather than fighting it: generate candidate plans → verify → feed back and retry (rejection sampling). On scheduling tasks, this loop raised success from 62% to 94%, with a formal guarantee that every output is logically sound. The "Modulo" framing signals a paradigm shift: don't demand perfect generation — demand correct results after verification.

The Limits of Prompt Engineering

Wu & Mitra (2024) asked provocatively whether LLMs can actually plan when given solver-generated hints. The answer: it depends. Visual feedback lifted GPT-4's success from 45% to 78% on standard problems, but all hint strategies failed beyond a complexity threshold — a glass ceiling. Solver-guided fine-tuning improved mid-difficulty problems by 22% but left hard problems untouched: data distillation cannot teach algorithmic capabilities beyond the training distribution.

Act II: Memory Palaces — Remembering That You're Planning

• Editable memory graphs (Cao et al., 2024): Persistent graph nodes replace prompt-based user profiles. Personalization raised user satisfaction by 31%; memory edit accuracy reached 89%.
• ExRAP (NeurIPS 2024): A closed loop of hypothesis → verification → update → re-retrieval, tripling adaptation speed in non-stationary embodied environments.
• MemGPT (2023): Manages memory like an operating system, paging between main context and external storage. Over 100k-word dialogues, factual consistency held at 92%, versus 63% for standard LLMs past 8k tokens — memory management beats context-window scaling.

Act III: Self-Evolution — When LLMs Become Their Own Teachers

• AgentGen (KDD 2024): LLMs synthesize million-scale training trajectories via environment and task generation, improving generalization to unseen tasks by 27% while cutting data costs 90%. Dualformer's mechanism randomly drops reasoning-chain segments, forcing the model to fill thought gaps.
• SPPO: Self-play preference optimization lifted tool-use success from 42% to 81%.
• WebRL (ICLR 2024): A self-evolving curriculum that demotes on repeated failure and unlocks harder tasks on success — 68% average success on 50 web tasks vs. 41% for supervised learning.
• **Rest-MCTS* (NeurIPS 2024): Monte Carlo Tree Search generates process rewards, raising math reasoning accuracy by 19 percentage points with notably more sound reasoning steps.

Act IV: The Art of Search

• ADAPT (NAACL 2024): Decompose only when needed — adaptive depth improved planning efficiency 40%.
• HuggingGPT: Decompose requests and dispatch them to specialist models — the value of decomposition is invoking the right capability at the right time.
• Tree of Thoughts (ToT): Tree-style exploration with pruning doubled story diversity (2.3x) while improving logical consistency.
• Graph of Thoughts (AAAI 2024): Cross-branch information fusion raised the probability of discovering novel proofs by 31%.
• LATS: LLM as value function with Monte Carlo simulation — 83% success building shelters in Minecraft within 10 steps vs. 21% for greedy strategies, illustrating that long-horizon planning requires sacrificing short-term gain.

Act V: The Purgatory of Evaluation

Planetarium (NAACL 2025) exposed a sobering gap: LLM-generated PDDL plans were syntactically correct 96.1% of the time, 94.4% solvable — but only 24.8% semantically correct**. LLMs can write plans that *look* right, like a chef who recites recipes but has never cooked. WebArena showed only 15% success on real websites, revealing how fragile agents are against real-world layout changes, popups, and lazy loading.

Mind2Web data revealed an anti-scaling law: GPT-4V achieved 38% single-step success but only 12% multi-step; smaller models plus tree search (34%) outperformed it. In embodied settings, LLM-DP reached 31% zero-shot success on unseen ALFWorld environments versus 9% for pure LLMs — symbolic planners act like GPS, guaranteeing the right general direction.

Act VI: Interpretability — Opening the Black Box

• "To CoT or not to CoT?" (ICLR 2024): Chain-of-thought helps math and symbolic reasoning but can hurt efficiency on commonsense planning.
• Confidence Matters (2024): Self-correction is overrated — it's nearly useless when initial confidence exceeds 85%; only in the 60–75% band does guidance add ~12% accuracy. Metacognition requires knowing what you don't know.
• Causal probing of GPT-2 (CoLM 2024): Current-token representations encode information about the next 3–5 tokens.
• Iteration Heads (NeurIPS 2024): Specific attention heads repeatedly activate during CoT, forming implicit feedback loops that let autoregressive models simulate iterative reasoning.

Epilogue: Future Horizons

Three rivers are converging:

1. Deep neuro-symbolic fusion — unified differentiable architectures where gradients flow through symbolic computation, encoding PDDL semantics as structured priors. 2. Endogenous world models — WorldCoder (NeurIPS 2024) shows models can build world models by writing code and interacting with environments. 3. Meta-planning — models that plan their own planning strategies, choosing a thinking framework before thinking.

Planetarium's 24.8% semantic correctness measures how far we are from genuine planning intelligence. But as LLM-Modulo shows: reliability comes not from perfection, but from knowing when you are imperfect. The deepest insight may be that planning is not predicting the future — it is creating possibilities.

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