Graph-Mediated Large Language Model Systems in the Agentic Era: Reasoning, Knowledge, Retrieval, Execution, and Coordination
Organizations: Institute of Artificial Intelligence and Future Networks, Beijing Normal University, Zhuhai 519087, China · School of Geospatial Engineering and Science, Sun Yat-sen University, Zhuhai 519082, China · Faculty of Science and Technology, Beijing Normal-Hong Kong Baptist University, Zhuhai 519087, China · Wangxuan Institute of Computer Technology, Peking University, Beijing 100871, China ·
Abstract
Graphs play an increasingly important role in large language model (LLM) systems, supporting structural reasoning, knowledge grounding, retrieval, and memory. As these systems evolve toward the agentic era, graphs also organize execution dependencies and multi-agent communication, linking intermediate observations and retained information to subsequent decisions. However, understanding their contribution requires distinguishing the function of each graph operation, the component responsible for its computation, and the subsequent use of its output. This survey introduces an operation-level role--locus taxonomy for reasoning, knowledge and evidence, retrieval and memory, execution, and coordination. We compare how graph observations and external computations guide decisions, how memory representations and updates support later tasks, and how dependencies constrain execution and information delivery. These comparisons distinguish improvements in local metrics from downstream task performance while retaining the conditions under which results were reported. We then organize benchmarks, comparison designs, process diagnostics, and system costs into an evaluation framework. Finally, we identify open challenges in adaptive computation and stopping, memory maintenance, and dependency-aware recovery. The survey provides a basis for assessing when graph mechanisms are useful and for evaluating their effects across components and stages.
Figures & tables
| Study | Content and access | Maintenance and later use | Evidence and conditions |
|---|---|---|---|
| Dialogue memory | |||
| Hu et al. [ 28 ] | Derived keys or entity descriptions; source alignment and value ranking. | Session ingestion; original sessions or derived keys supplied for answering. | Graph/flat ordering reverses across returned-value configurations on filtered question subsets. |
| Mem0 / Mem0 g [ 51 ] | Facts or entity relations; semantic and relational retrieval. | Mem0 modifies or deletes facts; Mem0 g invalidates edges for later dialogue QA. | LoCoMo category gains and losses; graph memory has higher search and response latency. |
| A-MEM [ 10 ] | Contextualized notes and association links. | Earlier notes are revised during ingestion to support subsequent retrieval. | The full system outperforms variants without evolution or without both linking and evolution; no ablation removes linking alone. |
| LightMem [ 125 ] | Compressed, topic-organized entries; semantic retrieval. | Online append and offline consolidation for later QA. | LongMemEval S : pre- and post-update QA; LoCoMo: post-update QA. Construction costs include summarization and updating. |
| Action and team memory | |||
| Method and relation | Feedback or selection input | Affected decision | Timing and scope |
|---|---|---|---|
| Computation and execution | |||
| GoT [ 8 ] Operation dependencies | Thought scores and validity checks. | Select, aggregate, or refine thoughts. | Task-local GRS updates under a specified GoO. |
| LLMCompiler [ 12 ] Call dependencies | Completed outputs; evaluated search states. | Bind arguments, release ready calls, and replan. | Runtime dispatch; reaching 24 completes the Game of 24 search. |
| AFlow [ 54 ] Workflow program | Validation execution and scores. | Revise prompts, operators, and dependencies. | Search before deployment; the selected program may branch or loop. |
| GraSP [ 58 ] Typed skill dependencies | Failed precondition, execution, or postcondition checks. | Apply bounded patches; escalate when needed. | Runtime repair; checker verdicts may be uncertain. |
| Communication selection | |||
| Research theme and evidence | Conditional design implication | Proposed diagnostic |
|---|---|---|
| Decisions and completion (RQ1). MuSe [ 14 ] returns views, GraphChain [ 15 ] computes results, and LLMCompiler [ 12 ] binds completed outputs. Graph Explorer [ 106 ] separates supported completion from fallback. | Distinguish missing evidence, interpretation errors, and unmet prerequisites when using feedback. Define completion for the required output. | Substitute reference specifications and executors separately; record visible choices, outputs, stopping, fallback, failures, and cost. |
| Memory and later use (RQ2). Relative performance of graph and flat memory varies with returned-value configurations [ 28 ] ; effects of fact compression and context granularity depend on questions and readers [ 27 ] . Action-oriented evidence comes from AriGraph [ 52 ] ; team-memory evidence comes from G-Memory [ 11 ] , under separate protocols. | Match retained sources, recovered detail, and update timing to the later task. Separate current applicability, history, and deletion. | Advance updates chronologically; vary context under declared budgets. Inspect stored and retrieved state, saved arguments, and team use separately. |
| Dependency preservation (RQ3). CWQ node prediction and path QA diverge under sparsification in GNN-RAG [ 29 ] ; sparse routes reduce the influence of both harmful and useful supplied information in EIB-LEARNER’s [ 13 ] topology-specific tests. GraSP [ 58 ] checks invocation conditions and repairs dependencies. | Preserve usable support, invocation requirements, and message routes; revalidate assumptions affected by repair. | Track paths, readiness, effects, and messages. Distinguish fixed-message replay from interactive reruns; account for full-workload costs. |
| Evaluation target | Representative resources | Observable evidence | Interpretation boundary |
|---|---|---|---|
| Graph computation | GraphArena [ 5 ] ; MAGMA [ 70 ] ; GraphEval36K [ 73 ] ; GraphOmni [ 161 ] ; GraphGym [ 162 ] . | Solution validity and optimality; supplied-state transitions; program tests; representation and loading sensitivity. | Correct conditional transitions and passing test cases do not establish reliable autonomous execution. |
| KG interpretation , | WebQSP [ 77 ] ; CWQ [ 87 ] ; KQA Pro [ 163 ] ; GrailQAbility [ 164 ] . | Semantic parses, compositional questions, explicit programs, and missing-data or schema conditions. | Annotation types differ; a correct denotation can arise from an incorrect interpretation. |
| Evidence access , | HotpotQA [ 84 ] ; 2WikiMultiHopQA [ 83 ] ; MuSiQue [ 82 ] ; STaRK [ 160 ] ; Xiang et al.’s evaluation [ 165 ] ; GraphRAG-Bench [ 166 ] . | Supporting sentences, evidence triples, connected question compositions, retrieval ranks, and stage-level outcomes. | Retrieval relevance, sufficient support, and faithful citation require separate assessment. |
| Dialogue memory | LoCoMo [ 122 ] ; LongMemEval [ 27 ] ; HaluMem [ 121 ] . | Long-history QA, temporal and update-dependent questions, and extraction or update assessments. | Answer-based and retrieval-mediated tests cover different aspects of retained state, not necessarily the entire store. |
| Interactive execution , | TextWorld [ 126 ] ; ALFWorld [ 143 ] ; ScienceWorld [ 144 ] ; WebShop [ 134 ] ; AgentBench [ 167 ] ; ToolBench [ 168 ] . | Environment progress, action effects, and tool trajectories; ToolEval [ 168 ] provides judged outcomes on ToolBench. | Invocation success, task success, and evaluator acceptance differ. Cross-task retention requires an explicit protocol. |
| General outcomes , | HumanEval [ 169 ] ; MMLU [ 150 ] . | Unit-test correctness and multiple-choice accuracy, including outcomes used in workflow and communication studies. | These annotations alone do not test persistent updates or naturally discovered corrections. |
LLM Reasoning with Graphs
Large language model reasoning with graphs uses structured relationships to support multi-step inference, evidence retrieval, and planning.
See all 224 papers