# Hierarchical Planning for Complex Tasks with Knowledge Graph-RAG and Symbolic Verification arXiv: https://arxiv.org/abs/2504.04578 ยท HTML: https://mlsanity.com/paper/2504.04578/ ## Key facts - Cited by 9 papers in the map (data through 14 Oct 2026). - Builds on 40 of its 51 references that are in the map. - First posted on arXiv 6 Apr 2025. ## Builds on (most cited first, 30 of 40) - [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022) - [Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks](https://mlsanity.com/paper/2005.11401/) (2020) - [Toolformer: Language Models Can Teach Themselves to Use Tools](https://mlsanity.com/paper/2302.04761/) (2023) - [Do As I Can, Not As I Say: Grounding Language in Robotic Affordances](https://mlsanity.com/paper/2204.01691/) (2022) - [REALM: Retrieval-Augmented Language Model Pre-Training](https://mlsanity.com/paper/2002.08909/) (2020) - [From Local to Global: A Graph RAG Approach to Query-Focused Summarization](https://mlsanity.com/paper/2404.16130/) (2024) - [Code as Policies: Language Model Programs for Embodied Control](https://mlsanity.com/paper/2209.07753/) (2022) - [Language Models as Zero-Shot Planners: Extracting Actionable Knowledge for Embodied Agents](https://mlsanity.com/paper/2201.07207/) (2022) - [Unifying Large Language Models and Knowledge Graphs: A Roadmap](https://mlsanity.com/paper/2306.08302/) (2023) - [LLM+P: Empowering Large Language Models with Optimal Planning Proficiency](https://mlsanity.com/paper/2304.11477/) (2023) - [LLM-Planner: Few-Shot Grounded Planning for Embodied Agents with Large Language Models](https://mlsanity.com/paper/2212.04088/) (2022) - [On the Planning Abilities of Large Language Models : A Critical Investigation](https://mlsanity.com/paper/2305.15771/) (2023) - [Robots That Ask For Help: Uncertainty Alignment for Large Language Model Planners](https://mlsanity.com/paper/2307.01928/) (2023) - [ChatGPT for Robotics: Design Principles and Model Abilities](https://mlsanity.com/paper/2306.17582/) (2023) - [SayPlan: Grounding Large Language Models using 3D Scene Graphs for Scalable Robot Task Planning](https://mlsanity.com/paper/2307.06135/) (2023) - [Text2Motion: From Natural Language Instructions to Feasible Plans](https://mlsanity.com/paper/2303.12153/) (2023) - [Pre-Trained Language Models for Interactive Decision-Making](https://mlsanity.com/paper/2202.01771/) (2022) - [Leveraging Pre-trained Large Language Models to Construct and Utilize World Models for Model-based Task Planning](https://mlsanity.com/paper/2305.14909/) (2023) - [Hydra: A Real-time Spatial Perception System for 3D Scene Graph Construction and Optimization](https://mlsanity.com/paper/2201.13360/) (2022) - [ROSCOE: A Suite of Metrics for Scoring Step-by-Step Reasoning](https://mlsanity.com/paper/2212.07919/) (2022) - [REFLECT: Summarizing Robot Experiences for Failure Explanation and Correction](https://mlsanity.com/paper/2306.15724/) (2023) - [Translating Natural Language to Planning Goals with Large-Language Models](https://mlsanity.com/paper/2302.05128/) (2023) - [Keep CALM and Explore: Language Models for Action Generation in Text-based Games](https://mlsanity.com/paper/2010.02903/) (2020) - [Compositional Foundation Models for Hierarchical Planning](https://mlsanity.com/paper/2309.08587/) (2023) - [RAP: Retrieval-Augmented Planning with Contextual Memory for Multimodal LLM Agents](https://mlsanity.com/paper/2402.03610/) (2024) - [KnowAgent: Knowledge-Augmented Planning for LLM-Based Agents](https://mlsanity.com/paper/2403.03101/) (2024) - [Retrieval-Augmented Reinforcement Learning](https://mlsanity.com/paper/2202.08417/) (2022) - [SayNav: Grounding Large Language Models for Dynamic Planning to Navigation in New Environments](https://mlsanity.com/paper/2309.04077/) (2023) - [Errors are Useful Prompts: Instruction Guided Task Programming with Verifier-Assisted Iterative Prompting](https://mlsanity.com/paper/2303.14100/) (2023) - [Plansformer: Generating Symbolic Plans using Transformers](https://mlsanity.com/paper/2212.08681/) (2022) ## Built on by (most cited first, 9 of 9) - [A Survey of Agentic Reasoning for Large Language Models: Towards Recursively Self-Improving and Collective Agents](https://mlsanity.com/paper/2601.12538/) (2026) - [Large Language Models for Planning: A Comprehensive and Systematic Survey](https://mlsanity.com/paper/2505.19683/) (2025) - [Unlocking the Power of Multi-Agent LLM for Reasoning: From Lazy Agents to Deliberation](https://mlsanity.com/paper/2511.02303/) (2025) - [KGLAMP: Knowledge Graph-guided Language model for Adaptive Multi-robot Planning and Replanning](https://mlsanity.com/paper/2602.04129/) (2026) - [Reflecting with Two Voices: A Co-Adaptive Dual-Strategy Framework for LLM-Based Agent Decision Making](https://mlsanity.com/paper/2512.08366/) (2025) - [Bridging Values and Behavior: A Hierarchical Framework for Proactive Embodied Agents](https://mlsanity.com/paper/2604.27699/) (2026) - [The Garden of Forking Paths: Threading Narrative Archetype as a Semantic Signal Through Gameplay Planning](https://mlsanity.com/paper/2605.01245/) (2026) - [CLASP: Language-Driven Robot Skill Selection and Composition using Task-Parameterized Learning](https://mlsanity.com/paper/2606.08169/) (2026) - [Neuro-Symbolic Hierarchical Intention Anticipation in Human Behavior](https://mlsanity.com/paper/2609.17064/) (2026) ## Abstract (arXiv) Large Language Models (LLMs) have shown promise as robotic planners but often struggle with long-horizon and complex tasks, especially in specialized environments requiring external knowledge. While hierarchical planning and Retrieval-Augmented Generation (RAG) address some of these challenges, they remain insufficient on their own and a deeper integration is required for achieving more reliable systems. To this end, we propose a neuro-symbolic approach that enhances LLMs-based planners with Knowledge Graph-based RAG for hierarchical plan generation. This method decomposes complex tasks into manageable subtasks, further expanded into executable atomic action sequences. To ensure formal correctness and proper decomposition, we integrate a Symbolic Validator, which also functions as a failure detector by aligning expected and observed world states. Our evaluation against baseline methods demonstrates the consistent significant advantages of integrating hierarchical planning, symbolic verification, and RAG across tasks of varying complexity and different LLMs. Additionally, our experimental setup and novel metrics not only validate our approach for complex planning but also serve as a tool for assessing LLMs' reasoning and compositional capabilities.