# Can Graph Learning Improve Planning in LLM-based Agents?

arXiv: https://arxiv.org/abs/2405.19119 · HTML: https://mlsanity.com/paper/2405.19119/

## Key facts

- Cited by 43 papers in the map (data through 14 Oct 2026).
- Placed in General LLM agent frameworks and benchmarks, one of 16 directions in LLM agents and tool use.
- Builds on 59 of its 72 references that are in the map.
- First posted on arXiv 29 May 2024.

## Placed in

- LLM agents and tool use / [General LLM agent frameworks and benchmarks](https://mlsanity.com/agents/general-llm-agent-frameworks-and-benchmarks/)

## Builds on (most cited first, 30 of 59)

- [LoRA: Low-Rank Adaptation of Large Language Models](https://mlsanity.com/paper/2106.09685/) (2021)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks](https://mlsanity.com/paper/1908.10084/) (2019)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Judging LLM-as-a-Judge with MT-Bench and Chatbot Arena](https://mlsanity.com/paper/2306.05685/) (2023)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Reflexion: Language Agents with Verbal Reinforcement Learning](https://mlsanity.com/paper/2303.11366/) (2023)
- [Toolformer: Language Models Can Teach Themselves to Use Tools](https://mlsanity.com/paper/2302.04761/) (2023)
- [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023)
- [Sparks of Artificial General Intelligence: Early experiments with GPT-4](https://mlsanity.com/paper/2303.12712/) (2023)
- [A Survey on Large Language Model based Autonomous Agents](https://mlsanity.com/paper/2308.11432/) (2023)
- [Voyager: An Open-Ended Embodied Agent with Large Language Models](https://mlsanity.com/paper/2305.16291/) (2023)
- [Efficient Streaming Language Models with Attention Sinks](https://mlsanity.com/paper/2309.17453/) (2023)
- [Code Llama: Open Foundation Models for Code](https://mlsanity.com/paper/2308.12950/) (2023)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Text Embeddings by Weakly-Supervised Contrastive Pre-training](https://mlsanity.com/paper/2212.03533/) (2022)
- [HuggingGPT: Solving AI Tasks with ChatGPT and its Friends in Hugging Face](https://mlsanity.com/paper/2303.17580/) (2023)
- [Language Models as Zero-Shot Planners: Extracting Actionable Knowledge for Embodied Agents](https://mlsanity.com/paper/2201.07207/) (2022)
- [Graph of Thoughts: Solving Elaborate Problems with Large Language Models](https://mlsanity.com/paper/2308.09687/) (2023)
- [Large Language Models](https://mlsanity.com/paper/2307.05782/) (2023)
- [Baichuan 2: Open Large-scale Language Models](https://mlsanity.com/paper/2309.10305/) (2023)
- [ProgPrompt: Generating Situated Robot Task Plans using Large Language Models](https://mlsanity.com/paper/2209.11302/) (2022)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [Plan-and-Solve Prompting: Improving Zero-Shot Chain-of-Thought Reasoning by Large Language Models](https://mlsanity.com/paper/2305.04091/) (2023)
- [MemoryBank: Enhancing Large Language Models with Long-Term Memory](https://mlsanity.com/paper/2305.10250/) (2023)
- [Masked Label Prediction: Unified Message Passing Model for Semi-Supervised Classification](https://mlsanity.com/paper/2009.03509/) (2020)
- [LLM+P: Empowering Large Language Models with Optimal Planning Proficiency](https://mlsanity.com/paper/2304.11477/) (2023)
- [Understanding the planning of LLM agents: A survey](https://mlsanity.com/paper/2402.02716/) (2024)

## Built on by (most cited first, 30 of 43)

- [Multi-agent Architecture Search via Agentic Supernet](https://mlsanity.com/paper/2502.04180/) (2025)
- [Retrieval-Augmented Generation with Graphs (GraphRAG)](https://mlsanity.com/paper/2501.00309/) (2024)
- [PlanGenLLMs: A Modern Survey of LLM Planning Capabilities](https://mlsanity.com/paper/2502.11221/) (2025)
- [RAG vs. GraphRAG: A Systematic Evaluation and Key Insights](https://mlsanity.com/paper/2502.11371/) (2025)
- [LLM-based Agents Suffer from Hallucinations: A Survey of Taxonomy, Methods, and Directions](https://mlsanity.com/paper/2509.18970/) (2025)
- [Robotouille: An Asynchronous Planning Benchmark for LLM Agents](https://mlsanity.com/paper/2502.05227/) (2025)
- [Graph-based Agent Memory: Taxonomy, Techniques, and Applications](https://mlsanity.com/paper/2602.05665/) (2026)
- [Graphs Meet AI Agents: Taxonomy, Progress, and Future Opportunities](https://mlsanity.com/paper/2506.18019/) (2025)
- [When Do LLMs Help With Node Classification? A Comprehensive Analysis](https://mlsanity.com/paper/2502.00829/) (2025)
- [Graph-Augmented Large Language Model Agents: Current Progress and Future Prospects](https://mlsanity.com/paper/2507.21407/) (2025)
- [Revisiting the Graph Reasoning Ability of Large Language Models: Case Studies in Translation, Connectivity and Shortest Path](https://mlsanity.com/paper/2408.09529/) (2024)
- [Demystifying Reinforcement Learning for Long-Horizon Tool-Using Agents: A Comprehensive Recipe](https://mlsanity.com/paper/2603.21972/) (2026)
- [UniGTE: Unified Graph-Text Encoding for Zero-Shot Generalization across Graph Tasks and Domains](https://mlsanity.com/paper/2510.16885/) (2025)
- [Unifying Text Semantics and Graph Structures for Temporal Text-attributed Graphs with Large Language Models](https://mlsanity.com/paper/2503.14411/) (2025)
- [Large Language Models Meet Text-Attributed Graphs: A Survey of Integration Frameworks and Applications](https://mlsanity.com/paper/2510.21131/) (2025)
- [Experience-Evolving Multi-Turn Tool-Use Agent with Hybrid Episodic-Procedural Memory](https://mlsanity.com/paper/2512.07287/) (2025)
- [Generative Skill Composition for LLM Agents](https://mlsanity.com/paper/2606.32025/) (2026)
- [Uncertainty-o: One Model-agnostic Framework for Unveiling Uncertainty in Large Multimodal Models](https://mlsanity.com/paper/2506.07575/) (2025)
- [LLMAP: LLM-Assisted Multi-Objective Route Planning with User Preferences](https://mlsanity.com/paper/2509.12273/) (2025)
- [GraphRunner: A Multi-Stage Framework for Efficient and Accurate Graph-Based Retrieval](https://mlsanity.com/paper/2507.08945/) (2025)
- [Benefits and Pitfalls of Reinforcement Learning for Language Model Planning: A Theoretical Perspective](https://mlsanity.com/paper/2509.22613/) (2025)
- [Language Models, Graph Searching, and Supervision Adulteration: When More Supervision is Less and How to Make More More](https://mlsanity.com/paper/2503.10542/) (2025)
- [Data-centric Federated Graph Learning with Large Language Models](https://mlsanity.com/paper/2503.19455/) (2025)
- [Generalizable LLM Learning of Graph Synthetic Data with Post-training Alignment](https://mlsanity.com/paper/2506.00845/) (2025)
- [NaviAgent: Graph-Driven Bilevel Planning for Scalable Tool Orchestration](https://mlsanity.com/paper/2506.19500/) (2025)
- [Navigating Motion Agents in Dynamic and Cluttered Environments through LLM Reasoning](https://mlsanity.com/paper/2503.07323/) (2025)
- [RoboPARA: Dual-Arm Robot Planning with Parallel Allocation and Recomposition Across Tasks](https://mlsanity.com/paper/2506.06683/) (2025)
- [PseudoAct: Leveraging Pseudocode Synthesis for Flexible Planning and Action Control in Large Language Model Agents](https://mlsanity.com/paper/2602.23668/) (2026)
- [Do LLMs Build Spatial World Models? Evidence from Grid-World Maze Tasks](https://mlsanity.com/paper/2604.10690/) (2026)
- [Unifying biomedical knowledge in a modern multimodal graph](https://mlsanity.com/paper/2604.27269/) (2026)

## Abstract (arXiv)

Task planning in language agents is emerging as an important research topic alongside the development of large language models (LLMs). It aims to break down complex user requests in natural language into solvable sub-tasks, thereby fulfilling the original requests. In this context, the sub-tasks can be naturally viewed as a graph, where the nodes represent the sub-tasks, and the edges denote the dependencies among them. Consequently, task planning is a decision-making problem that involves selecting a connected path or subgraph within the corresponding graph and invoking it. In this paper, we explore graph learning-based methods for task planning, a direction that is orthogonal to the prevalent focus on prompt design. Our interest in graph learning stems from a theoretical discovery: the biases of attention and auto-regressive loss impede LLMs' ability to effectively navigate decision-making on graphs, which is adeptly addressed by graph neural networks (GNNs). This theoretical insight led us to integrate GNNs with LLMs to enhance overall performance. Extensive experiments demonstrate that GNN-based methods surpass existing solutions even without training, and minimal training can further enhance their performance. The performance gain increases with a larger task graph size.