mlsanityData to 14 Oct 2026

Can Graph Learning Improve Planning in LLM-based Agents?

arXiv 2405.19119 ↗First posted 29 May 2024cs.LGcited by 43

On the map: LLM agents and tool use → General LLM agent frameworks and benchmarks

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.

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.

Builds on

59 of 72 references.

Closest ancestors · 2

Same direction, newest first

  1. 2024Understanding the planning of LLM agents: A survey5 Feb
  2. 2023A Survey on Large Language Model based Autonomous Agents22 Aug

Other references · 57

  1. 2021LoRA: Low-Rank Adaptation of Large Language Modelscited by 14,380
  2. 2022Chain-of-Thought Prompting Elicits Reasoning in Large Language Modelscited by 12,459
  3. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,361
  4. 2019Sentence-BERT: Sentence Embeddings using Siamese BERT-Networkscited by 9,170
  5. 2017Graph Attention Networkscited by 8,923
  6. 2023Judging LLM-as-a-Judge with MT-Bench and Chatbot Arenacited by 8,626
  7. 2017Inductive Representation Learning on Large Graphscited by 6,320
  8. 2018How Powerful are Graph Neural Networks?cited by 4,393
  9. 2023Reflexion: Language Agents with Verbal Reinforcement Learningcited by 4,276
  10. 2023Toolformer: Language Models Can Teach Themselves to Use Toolscited by 4,182
  11. 2023Tree of Thoughts: Deliberate Problem Solving with Large Language Modelscited by 3,211
  12. 2023Sparks of Artificial General Intelligence: Early experiments with GPT-4cited by 2,592
38 more
  1. 2023Voyager: An Open-Ended Embodied Agent with Large Language Modelscited by 2,191
  2. 2023Efficient Streaming Language Models with Attention Sinkscited by 2,186
  3. 2023Code Llama: Open Foundation Models for Codecited by 2,139
  4. 2019Simplifying Graph Convolutional Networkscited by 1,477
  5. 2022Text Embeddings by Weakly-Supervised Contrastive Pre-trainingcited by 1,253
  6. 2023HuggingGPT: Solving AI Tasks with ChatGPT and its Friends in Hugging Facecited by 1,190
  7. 2022Language Models as Zero-Shot Planners: Extracting Actionable Knowledge for Embodied Agentscited by 1,035
  8. 2023Graph of Thoughts: Solving Elaborate Problems with Large Language Modelscited by 886
  9. 2023Large Language Modelscited by 780
  10. 2023Baichuan 2: Open Large-scale Language Modelscited by 670
  11. 2022ProgPrompt: Generating Situated Robot Task Plans using Large Language Modelscited by 611
  12. 2017Learning Combinatorial Optimization Algorithms over Graphscited by 561
  13. 2023Plan-and-Solve Prompting: Improving Zero-Shot Chain-of-Thought Reasoning by Large Language Modelscited by 560
  14. 2023MemoryBank: Enhancing Large Language Models with Long-Term Memorycited by 556
  15. 2020Masked Label Prediction: Unified Message Passing Model for Semi-Supervised Classificationcited by 506
  16. 2023LLM+P: Empowering Large Language Models with Optimal Planning Proficiencycited by 501
  17. 2023ToolAlpaca: Generalized Tool Learning for Language Models with 3000 Simulated Casescited by 393
  18. 2019Exact Combinatorial Optimization with Graph Convolutional Neural Networkscited by 318
  19. 2023Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspectivecited by 294
  20. 2021Combinatorial optimization and reasoning with graph neural networkscited by 268
  21. 2023Can Language Models Solve Graph Problems in Natural Language?cited by 252
  22. 2023GraphGPT: Graph Instruction Tuning for Large Language Modelscited by 226
  23. 2024G-Retriever: Retrieval-Augmented Generation for Textual Graph Understanding and Question Answeringcited by 223
  24. 2023GPT4Graph: Can Large Language Models Understand Graph Structured Data ? An Empirical Evaluation and Benchmarkingcited by 210
  25. 2018Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Searchcited by 183
  26. 2019What Can Neural Networks Reason About?cited by 159
  27. 2023TaskBench: Benchmarking Large Language Models for Task Automationcited by 144
  28. 2023Harnessing Explanations: LLM-to-LM Interpreter for Enhanced Text-Attributed Graph Representation Learningcited by 133
  29. 2024Let Your Graph Do the Talking: Encoding Structured Data for LLMscited by 118
  30. 2023GraphLLM: Boosting Graph Reasoning Ability of Large Language Modelcited by 107
  31. 2024Planning, Creation, Usage: Benchmarking LLMs for Comprehensive Tool Utilization in Real-World Complex Scenarioscited by 86
  32. 2023A Survey of Graph Meets Large Language Model: Progress and Future Directionscited by 85
  33. 2024ZeroG: Investigating Cross-dataset Zero-shot Transferability in Graphscited by 85
  34. 2023Evaluating Cognitive Maps and Planning in Large Language Models with CogEvalcited by 77
  35. 2024ToolNet: Connecting Large Language Models with Massive Tools via Tool Graphcited by 60
  36. 2023ControlLLM: Augment Language Models with Tools by Searching on Graphscited by 59
  37. 2024GraphInstruct: Empowering Large Language Models with Graph Understanding and Reasoning Capabilitycited by 58
  38. 2022Graph Neural Networks are Dynamic Programmerscited by 55

50 most cited of 57 All 57 (JSON)

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 2; 2025: 23; 2026: 18.

43 papers.

Sort:

By area:

  1. 2025Multi-agent Architecture Search via Agentic Supernetcited by 179
  2. 2024Retrieval-Augmented Generation with Graphs (GraphRAG)cited by 172
  3. 2025PlanGenLLMs: A Modern Survey of LLM Planning Capabilitiescited by 83
  4. 2025RAG vs. GraphRAG: A Systematic Evaluation and Key Insightscited by 53
  5. 2025LLM-based Agents Suffer from Hallucinations: A Survey of Taxonomy, Methods, and Directionscited by 50
  6. 2025Robotouille: An Asynchronous Planning Benchmark for LLM Agentscited by 32
  7. 2026Graph-based Agent Memory: Taxonomy, Techniques, and Applicationscited by 25
  8. 2025Graphs Meet AI Agents: Taxonomy, Progress, and Future Opportunitiescited by 23
  9. 2025When Do LLMs Help With Node Classification? A Comprehensive Analysiscited by 21
  10. 2025Graph-Augmented Large Language Model Agents: Current Progress and Future Prospectscited by 14
  11. 2024Revisiting the Graph Reasoning Ability of Large Language Models: Case Studies in Translation, Connectivity and Shortest Pathcited by 10
  12. 2026Demystifying Reinforcement Learning for Long-Horizon Tool-Using Agents: A Comprehensive Recipecited by 8
31 more
  1. 2025UniGTE: Unified Graph-Text Encoding for Zero-Shot Generalization across Graph Tasks and Domainscited by 7
  2. 2025Unifying Text Semantics and Graph Structures for Temporal Text-attributed Graphs with Large Language Modelscited by 6
  3. 2025Large Language Models Meet Text-Attributed Graphs: A Survey of Integration Frameworks and Applicationscited by 6
  4. 2025Experience-Evolving Multi-Turn Tool-Use Agent with Hybrid Episodic-Procedural Memorycited by 6
  5. 2026Generative Skill Composition for LLM Agentscited by 6
  6. 2025Uncertainty-o: One Model-agnostic Framework for Unveiling Uncertainty in Large Multimodal Modelscited by 5
  7. 2025LLMAP: LLM-Assisted Multi-Objective Route Planning with User Preferencescited by 5
  8. 2025GraphRunner: A Multi-Stage Framework for Efficient and Accurate Graph-Based Retrievalcited by 4
  9. 2025Benefits and Pitfalls of Reinforcement Learning for Language Model Planning: A Theoretical Perspectivecited by 4
  10. 2025Language Models, Graph Searching, and Supervision Adulteration: When More Supervision is Less and How to Make More Morecited by 3
  11. 2025Data-centric Federated Graph Learning with Large Language Modelscited by 3
  12. 2025Generalizable LLM Learning of Graph Synthetic Data with Post-training Alignmentcited by 3
  13. 2025NaviAgent: Graph-Driven Bilevel Planning for Scalable Tool Orchestrationcited by 3
  14. 2025Navigating Motion Agents in Dynamic and Cluttered Environments through LLM Reasoningcited by 2
  15. 2025RoboPARA: Dual-Arm Robot Planning with Parallel Allocation and Recomposition Across Taskscited by 2
  16. 2026PseudoAct: Leveraging Pseudocode Synthesis for Flexible Planning and Action Control in Large Language Model Agentscited by 2
  17. 2026Do LLMs Build Spatial World Models? Evidence from Grid-World Maze Taskscited by 2
  18. 2026Unifying biomedical knowledge in a modern multimodal graphcited by 1
  19. 2026HyperAgent: Planning and Acting over Tool-Schema Hypergraphs for Tool-Use LLM Agentscited by 1
  20. 2026Procedural Graphs: Self-Evolving Execution Structures for LLM Agentscited by 1
  21. 2025Cognitive Inception: Agentic Reasoning against Visual Deceptions by Injecting Skepticismcited by 0
  22. 2026Robust and Efficient Tool Orchestration via Layered Execution Structures with Reflective Correctioncited by 0
  23. 2026Detecting Miscitation on the Scholarly Web through LLM-Augmented Text-Rich Graph Learningcited by 0
  24. 2026CAARL: In-Context Learning for Interpretable Co-Evolving Time Series Forecastingcited by 0
  25. 2026GRAFT: Graph-Tokenized LLMs for Tool Planningcited by 0
  26. 2026LLMs+Graphs: Toward Graph-Native, Synergistic AI Systemscited by 0
  27. 2026AGE: Adaptive-masking for Graph Embedding in Graph Retrieval-Augmented Generationcited by 0
  28. 2026Towards Self-Evolving Agents: A Human-Inspired Adaptive Exploration-Exploitation Framework for Genetic Network Programmingcited by 0
  29. 2026Leveraging Trajectory Graphs for Pre-Execution Error Diagnosis in Agentic LLM Systemscited by 0
  30. 2026MAGIC: Mixed-Granularity Agent Graphs via Incremental Construction with Dense-Reward Reinforcement Learningcited by 0
  31. 2026Topology-Consistent Task Planning over Cellular Workflow Complexes for LLM-based Agentscited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025From Experience to Strategy: Empowering LLM Agents with Trainable Graph Memory
  2. 2025Less is More: Learning Graph Tasks with Just LLMs
  3. 2026Are Large Language Models Suitable for Graph Computation? Progress and Prospects
  4. 2026Integrating Graphs, Large Language Models, and Agents: Reasoning and Retrieval
  5. 2024Language Agents as Optimizable Graphs
  6. 2024Input Conditioned Graph Generation for Language Agents
  7. 2025Automated Decision-Making on Networks with LLMs through Knowledge-Guided Evolution
  8. 2024GRL-Prompt: Towards Knowledge Graph based Prompt Optimization via Reinforcement Learning