PaperlayerView exact revision on arXiv

Source-linked AI summary

Graph-Augmented Large Language Model Agents: Current Progress and Future Prospects

Yixin Liu, Guibin Zhang, Kun Wang, Shiyuan Li, Shirui Pan

arXiv:2507.21407v2cs.AI

TL;DR

LLM agents are limited in reliable planning, long-term memory, tool management, and multi-agent coordination, motivating graph-augmented approaches. The paper surveys GLA methods across individual agent functions and multi-agent systems, then identifies future directions including adaptive, unified, multimodal, and scalable graph systems. Its supported conclusion is that GLA remains an early-stage field whose progress depends on addressing static graph structures and other unresolved design challenges.

  • Problem

    LLMs remain limited in reliable planning, long-term memory, tool management, and multi-agent coordination, while GLA lacks a comprehensive taxonomy or review.

  • Method

    The paper categorizes GLA methods by planning, memory, and tool usage, analyzes graph support for multi-agent orchestration, efficiency, and trustworthiness, and surveys future directions.

  • Results

    GLA is presented as providing reliability, efficiency, interpretability, and flexibility benefits through structured graph representations in LLM agent systems.

  • Takeaways & Limitations

    The review offers a roadmap for developing more adaptive, unified, multimodal, scalable, interpretable, and collaborative graph-augmented agent systems.

  • Takeaways & Limitations

    Most current GLA systems use static or session-specific graphs fixed during execution, limiting adaptation to dynamic environments and shifting task requirements.

Abstract

from arXiv · show

Autonomous agents based on large language models (LLMs) have demonstrated impressive capabilities in a wide range of applications, including web navigation, software development, and embodied control. While most LLMs are limited in several key agentic procedures, such as reliable planning, long-term memory, tool management, and multi-agent coordination, graphs can serve as a powerful auxiliary structure to enhance structure, continuity, and coordination in complex agent workflows. Given the rapid growth and fragmentation of research on Graph-augmented LLM Agents (GLA), this paper offers a timely and comprehensive overview of recent advances and also highlights key directions for future work. Specifically, we categorize existing GLA methods by their primary functions in LLM agent systems, including planning, memory, and tool usage, and then analyze how graphs and graph learning algorithms contribute to each. For multi-agent systems, we further discuss how GLA solutions facilitate the orchestration, efficiency optimization, and trustworthiness of MAS. Finally, we highlight key future directions to advance this field, from improving structural adaptability to enabling unified, scalable, and multimodal GLA systems. We hope this paper can serve as a roadmap for future research on GLA and foster a deeper understanding of the role of graphs in LLM agent systems.

1 Introduction

LLMs enable capable autonomous agents but remain unreliable for planning, long-term memory, tool use, and multi-agent coordination. This paper reviews Graph-augmented LLM Agents (GLA), organizing graph-based methods across agent functions and multi-agent systems while identifying future research directions.

  • LLM agents support natural-language understanding, multi-step tasks, and external-tool coordination across applications including software development, scientific research, and financial analysis.
  • LLMs alone remain insufficient for reliable planning, long-term memory, tool use, and inter-agent coordination because of hallucinations, limited context, and statelessness.
  • GLA uses graphs as complementary infrastructure for tool management, task decomposition, external knowledge storage, and agent communication.
  • Compared with purely LLM-based solutions, GLA is presented as improving reliability, efficiency, interpretability, and flexibility through structured representations and modular reuse.Graphs ground agent reasoning and knowledge in structured data, expose information and control-flow propagation, and support reusable graph-structured knowledge, memory, workflows, and communication patterns.
  • The paper addresses the lack of a comprehensive GLA taxonomy by reviewing graph support for individual agent modules, multi-agent orchestration, safety, efficiency, and future directions.Highlighted directions include dynamic and continual graph learning, unified graph abstractions, multimodal graphs, and large-scale multi-agent simulation.

2 Graph-Augmented LLM Agent System Framework

An LLM agent system combines a central reasoning agent with planning, memory, and tool-using modules. Graphs support these modules by representing task structure, stored knowledge or history, and interactions with external tools or environments.

  • The framework consists of a central LLM agent plus planning, memory, and tool-using modules.Planning decomposes tasks and reasons about requirements; memory stores and retrieves contextual or historical information; tool use connects the agent to external APIs or environments.
  • Graphs support planning, memory management, and tool management by organizing the structures and execution flows of LLM agent systems.

2.1 Graphs for Agent Planning

Graphs support agent planning by representing task dependencies, workflows, reasoning paths, and environmental constraints, improving executability, adaptability, and reliability.

  • Task decomposition: Graph representations organize sub-task dependencies, clarifying task flow while supporting reusable components and parallel or sequential execution.
  • Plan as a graph: AFlow models agentic workflows as graphs and uses Monte Carlo Tree Search to explore and optimize execution structures with less human effort.The broader workflow paradigm also extends toward dynamic graph reconfiguration and domain-specific agent tasks.
  • Sub-task pool as a graph: Graph-based planners retrieve executable sub-task plans from constrained task graphs, with training-free and trained retrievers outperforming hallucination-prone LLM planners.Each node is a predefined executable sub-task, while edges encode dependencies such as output-input compatibility.
  • Reasoning thought as a graph: Thought graphs generalize multi-path reasoning beyond trees, enabling adaptive planning through transformations such as combining intermediate thoughts.Tree of Thoughts explores alternative reasoning paths, while RATT adds retrieval to improve factual grounding.
  • Environment as a graph: Environment graphs explicitly model entities and relationships so agents can account for contextual constraints, detect hazards, refine tasks, and localize coding bugs.The supplied passages describe applications in robotic planning and coding-agent code structure graphs.

2.2 Graphs for Agent Memory Management

Graphs organize both interaction histories and external knowledge, allowing agents to retrieve relevant experiences, reason over connected information, and evolve memory representations.

  • Interaction memory: Graph-organized interaction memory links states, observations, and decisions through temporal or causal relations, enabling recall of relevant experiences and historical context.
  • Memory evolution: A-MEM builds interconnected memory networks through dynamic indexing and linking, allowing new memories to update existing representations and continuously refine the network.
  • Knowledge memory: Graph-organized knowledge memory connects entities and relationships to support multi-hop reasoning, knowledge integration, and navigation across complex domains.
  • Knowledge memory: KG-Agent combines a knowledge-graph executor, multifunctional tools, and dynamic memory so smaller models can perform complex reasoning and outperform larger models on in-domain and out-domain question answering.

2.3 Graphs for Tool Management

Tool graphs structure tools, resources, and their relationships to improve tool selection, retrieval, coordination, and tool-use training for complex tasks.

  • Tool graph representation: Tool graphs represent tools as nodes and functional dependencies or compatibility as edges, supporting structured selection and retrieval.
  • Tool selection and retrieval: ControlLLM searches input-output relationships in a tool graph to identify executable toolchains for complex user requests.
  • Motivation: Graph-based tool management addresses the difficulty of handling external tools as their number and variety grow.
  • Tool-use training: Tool graphs can sample related tool combinations as training examples, improving tool-calling capability through supervised fine-tuning.ToolFlow constructs a parameter-level graph from semantic similarity between tool inputs and outputs.

3 Graph-Augmented LLM Multi-Agent Systems

Graph-augmented multi-agent systems model agent interactions and organize collaboration across topology, workflow, efficiency, and trustworthiness dimensions.

  • Research dimensions: The paper studies graph-based MAS methods through topology and workflow design, task-solving efficiency, and trustworthy architecture synthesis.
  • Graph modeling: Graphs suit MAS because nodes represent heterogeneous agents and edges represent their interactions, supporting collective coordination beyond single-agent setups.The passage reports that recent MAS studies can significantly surpass single-agent capabilities.

3.1 Graphs for MAS Orchestration

Graph-based MAS orchestration has progressed from implicit interaction layouts to explicit, task-adaptive, and increasingly runtime-dynamic topologies. However, current task-adaptive methods typically sample structures before execution, limiting fine-grained adaptation and fault tolerance.

  • Task-dynamic MAS Topology: Early MAS systems used chained, multilayer-perceptron-like, or debate-based interaction structures before later approaches modeled orchestration explicitly as graphs.AutoGen and DyLAN are examples of earlier layouts, while ChatEval, LLM-Debate, and Persuasive-Debate implicitly organize agent interactions as graph-like structures [Wu et al., 2024a; Liu et al., 2023; Chan et al., 2023; Du et al., 2024; Khan et al., 2024].
  • Task-dynamic MAS Topology: Explicit graph modeling represents agent invocations and composite behaviors as nodes, enabling MAS orchestration through structured interaction topologies.GPTSwarm models single-agent invocations as base nodes and composite behaviors such as ReAct and CoT as higher-level nodes.
  • Task-dynamic MAS Topology: Task-independent topologies apply the same structure across domains, whereas G-Designer generates graph complexity tailored to task difficulty.G-Designer uses a variational graph auto-encoder to encode task-aware graphs and dynamically generate topologies [Zhang et al., 2025f].
  • Task-dynamic MAS Topology: Figure 7 sketches graph perspectives for improving MAS efficiency, complementing the orchestration taxonomy with efficiency-oriented graph analysis.The section introduces the figure immediately before discussing MAS efficiency issues from graph-theoretic perspectives.
  • Process-dynamic MAS Topology: Runtime-dynamic methods address the limitation of pre-execution topology sampling by adapting routing, topology, or prompting during execution.ReSo plans and routes agents at each execution node, while EvoMAC and AnyMAC adapt topology using environment feedback or subtask progression [Zhou et al., 2025b; Hu et al., 2025; Wang et al., 2025d].

3.2 Graph for MAS Efficiency

Graph-based MAS efficiency work targets redundancy at the edge, node, and dialogue-layer levels. The surveyed methods show that pruning communication or inactive agents can preserve performance, while excessive debate rounds may stop improving results.

  • Edge Redundancy in MAS: Many MAS systems use predefined communication paths, but greater edge density does not consistently improve performance and some edges can be pruned without comparable-performance loss.AgentPrune formalizes Communication Redundancy and identifies removable inter-agent communication edges [Zhang et al., 2025e].
  • Node Redundancy in MAS: AgentDropout dynamically removes underperforming or inactive agents, achieving node-level de-redundancy with transferability across datasets.MAS pruned and optimized on one dataset generalize well to others [Wang et al., 2025g].
  • Node Redundancy in MAS: Graph sparsification insights motivate MAS efficiency methods that remove redundant edges or nodes while maintaining or improving robustness and training efficiency.Related GNN methods include DropEdge, PTDNet, and DropGNN [Rong et al., 2020; Luo et al., 2021; Papp et al., 2021].
  • Layer Redundancy in MAS: Additional multi-agent dialogue rounds can produce oversmoothing: disagreement decreases, but performance may plateau, with one study reporting no gains beyond five debate rounds.Residual MoA compresses historical information through residual agents, while DOWN selectively engages debate to address this issue [Liang et al., 2024; Li et al., 2024b; Xie et al., 2025; Eo et al., 2025].

3.3 Graphs for Trustworthy MAS

Trustworthy MAS research uses graph structure to analyze and manage the propagation of bias, harmful content, and threats across agents and memory systems. Technical approaches are complemented by benchmarks for systematic safety evaluation.

  • Graphs for Trustworthy MAS: Graph-based MAS trustworthiness research examines how network configurations affect the propagation of hazardous information.Trustworthiness is framed as fundamental to operational reliability in agentic systems [Chen et al., 2025a; Wang et al., 2025a; Yu et al., 2025a; Liu et al., 2025b; Wang et al., 2025b; Liu et al., 2025a].
  • Graphs for Trustworthy MAS: NetSafe and ARGUS investigate bias and harmful-content flow through MAS, while AgentSafe examines impacts on memory subsystems.These studies establish foundations for modeling safety risks across agent interactions and memory [Yu et al., 2025b; Li et al., 2025b; Mao et al., 2025].
  • Graphs for Trustworthy MAS: G-Safeguard uses graph neural-network inductive bias to model threat propagation and support threat prediction and detection in MAS.
  • Graphs for Trustworthy MAS: Agent-SafetyBench and AgentAuditor provide complementary evaluation resources for safety issues and agent behavior during operations.Agent-SafetyBench focuses on simulated environments, whereas AgentAuditor provides formal monitoring and evaluation frameworks [Zhang et al., 2024c; Luo et al., 2025a].

4 Conclusion and Future Directions

The paper identifies static, module-specific, text-centered, and small-scale graph systems as boundaries for current GLA research. It proposes dynamic continual learning, unified abstractions, multimodal graphs, stronger security methods, and scalable graph learning as future directions.

  • 4.1 Dynamic and Continual Graph Learning for Agent Systems: Most current GLA systems use task-specific graph structures that remain fixed during execution, motivating dynamic and continual graph learning for evolving tasks and environments.Continually updated graphs could revise plans, memory, and tool-use pathways from new experiences [32].
  • 4.2 Unified Graph Abstractions for Full-Stack Agent Systems: Because graph modules are designed separately for planning, memory, tools, and collaboration, unified graph abstractions could represent full-stack knowledge, workflows, and interactions.The paper highlights graph foundation models as a possible reusable representation for integrating these modules [35].
  • 4.3 Multimodal Graphs for Agent Systems: Multimodal graphs are needed to organize heterogeneous language, vision, audio, and action information, including cross-modal relationships and temporal dynamics.Existing graph-based agent solutions typically focus on textual or symbolic domains [37].
  • 4.4 Graphs for Trustworthy Multi-Agent Systems: Graph modeling may support MAS security, fairness, and privacy through secure information exchange and anomaly detection over dynamic interaction graphs.The paper discusses node decomposition with homomorphic encryption and detecting malicious agents through anomalous node, edge, or subgraph patterns [39].
  • 4.5 Large-scale Graph Learning for MAS: Large-scale graph learning is needed because existing graph-based MAS approaches usually model only a few dozen agents and do not capture population-level complexity.Scalable methods could support simulations and deployments in social behavior modeling, industrial robotics, autonomous traffic control, and multi-agent financial systems [41, 42].
Loading 2507.21407v2…