PaperlayerView exact revision on arXiv

Source-linked AI summary

GraphPlanner: Graph Memory-Augmented Agentic Routing for Multi-Agent LLMs

Tao Feng, Haozhen Zhang, Zijie Lei, Peixuan Han, Jiaxuan You

arXiv:2604.23626v1cs.CL

TL;DR

Existing routers are limited in their ability to support complex tasks requiring explicit multi-agent collaboration. GraphPlanner generates workflows by selecting both models and roles and integrating historical and workflow memories; across 14 tasks, it improves accuracy over single-round and multi-round routers while reducing GPU cost.

  • Problem

    Existing routing methods largely use simplified or static settings, while agentic LLM routing must handle collaboration among heterogeneous models, evolving context, and historical memories.

    Source: §1 · pp. 1–2

  • Method

    GraphPlanner generates per-query routing workflows as an MDP, choosing both LLM backbones and agent roles while GARNet represents historical and current workflow memories.

    Source: §1 · p. 2

  • Results

    Across 14 tasks, GraphPlanner improves average accuracy by +3.8% in Phase 1 and +9.3% in Phase 2 while reducing GPU cost from 186.26 GiB to 1.04 GiB.

    Source: §1 · p. 2

  • Takeaways & Limitations

    GraphPlanner supports inductive routing that is more efficient and transductive routing that yields stronger performance at higher cost.

    Source: §1 · p. 2

Abstract

from arXiv · show

LLM routing has achieved promising results in integrating the strengths of diverse models while balancing efficiency and performance. However, to support more realistic and challenging applications, routing must extend into agentic LLM settings, where task planning, multi-round cooperation among heterogeneous agents, and memory utilization are indispensable. To address this gap, we propose GraphPlanner, a heterogeneous graph memory-augmented agentic router for multi-agent LLMs that generates routing workflows for each query and supports both inductive and transductive inference. GraphPlanner formulates workflow generation as a Markov Decision Process (MDP), where at each step it selects both the LLM backbone and the agent role, including Planner, Executor, and Summarizer. By leveraging a heterogeneous graph, denoted as GARNet, to capture interaction memories among queries, agents, and responses, GraphPlanner integrates historical memory and workflow memory into richer state representations. The entire pipeline is optimized with reinforcement learning, jointly improving task-specific performance and computational efficiency. We evaluate GraphPlanner across 14 diverse LLM tasks and demonstrate that: (1) GraphPlanner outperforms strong single-round and multi-round routers, improving accuracy by up to 9.3% while reducing GPU cost from 186.26 GiB to 1.04 GiB; (2) GraphPlanner generalizes robustly to unseen tasks and LLMs, exhibiting strong zero-shot capabilities; and (3) GraphPlanner effectively leverages historical memories, supporting both inductive and transductive inference for more adaptive routing. Our code for GraphPlanner is released at https://github.com/ulab-uiuc/GraphPlanner.

1 INTRODUCTION

Existing routers offer one-shot model assignment or sequential context-aware selections, but do not explicitly model collaboration among LLMs. GraphPlanner generates agentic workflows by jointly choosing a model and role, using graph-based memories and reinforcement learning.

1 INTRODUCTION

  • Existing routing methods are often simplified or static, and multi-round routers treat calls independently rather than explicitly modeling cooperative workflows.That separation is associated with redundant calls, context conflicts, and limited use of complementary model strengths.Source: §1 · pp. 1–2
  • Agentic routing must manage complex, evolving dependencies, deferred rewards, and historical workflow memories that existing routers rarely use systematically.Early routing choices can affect later outcomes, making credit assignment and the balance between efficiency and performance challenging.Source: §1 · p. 2
  • GraphPlanner casts workflow generation as an MDP, selecting both an LLM backbone and an agent role while GARNet combines historical and current workflow memories.The roles are Planner, Executor, and Summarizer; PPO jointly optimizes final-answer performance and computational cost.Source: §1 · p. 2
  • +3.8% average accuracy in Phase 1 and +9.3% in Phase 2 over the strongest baselines; GPU cost falls from 186.26 GiB to 1.04 GiB.Across 14 tasks in 6 domains, GraphPlanner also achieves 78% average accuracy on unseen tasks and handles unseen LLMs without additional fine-tuning.Source: §1 · p. 2

2 PRELIMINARIES

Preliminaries contrast single-round and multi-round routing with agentic routing, which coordinates models through explicit role choices and a workflow. Single-round routing assigns one model directly, while multi-round routing uses interaction history but may still lack explicit cooperation.

Single-round routers

  • Single-round routing assigns a query directly to one model, but cannot reason across steps, decompose tasks, or coordinate multiple LLMs.The paper notes that this makes the paradigm less suited to complex queries requiring collaboration across specialized models.Source: §2 · p. 3

Multi-round routers

  • Multi-round routing selects a backbone using the current query and accumulated interaction context, but may incur redundant calls and semantic conflicts.It still lacks an explicit mechanism for coordinating complementary model strengths.Source: §2 · p. 3

Agentic routers

  • Agentic routing selects both a backbone and an agent role using the query and evolving workflow memory, then integrates intermediate outputs into a final answer.Roles include Planner, Executor, and Summarizer; workflows support task decomposition and multi-role cooperation.Source: §2 · p. 3

3 GR A P HPL A N N E R: GRAPH-BASED AGENTIC LLM ROUTING

GraphPlanner routes agentic workflows by choosing both an LLM backbone and an agent role at each step. It combines workflow and historical memory in a heterogeneous graph policy and formulates workflow generation as an MDP.

3 GR A P HPL A N N E R: GRAPH-BASED AGENTIC LLM ROUTING

  • At each step, GraphPlanner chooses an agent role and LLM backbone using GARNet, which integrates workflow and historical memory graphs.Decision trajectories are added incrementally to Gworkflow and consolidated into Ghistory at episode end.Source: §3 · p. 4, Figure 2 · p. 4

3.1 AGENTIC ROUTING WORKFLOW GENERATION AS MARKOV DECISION PROCESS

  • The MDP state is the query being resolved, and each action pairs one of three roles with one of K LLMs, yielding 3K possible actions.Planner decomposes queries, Executor answers them, and Summarizer condenses completed responses; dynamic masks constrain valid actions and planner use.Source: §3.1 · p. 4
  • Planner actions create sub-queries, Executor actions resolve queries, and Summarizer actions aggregate completed responses; outputs accumulate along the trajectory into the final answer.Execution advances to the next pending query or terminates, while summarization sets the next query to the summary query.Source: §3.1 · pp. 4–5
  • The reward combines task-specific utility at termination with computational cost, using α > 0 to trade off utility and cost.The router seeks a policy that maximizes expected discounted return over the query distribution.Source: §3.1 · p. 5

3.2 HETEROGENEOUS GRAPH-BASED POLICY NETWORK

  • GARNet uses shared role hub nodes to connect current and historical query-response memories with role-specific utility and cost profiles.Queries and responses connect to the same hubs across rounds, allowing information exchange without an explicit temporal graph structure.Source: §3.2 · pp. 5–6
  • GARNet encodes historical memory before injecting its role-hub representations into the workflow graph, then scores masked LLM-role actions from the current query representation.The graph-based policy network is optimized using PPO.Source: §3.2 · p. 6

4 EXPERIMENTS

The experiments evaluate GraphPlanner on 14 tasks across six domains, comparing routing performance and cost across two phases. Results cover baseline comparisons, generalization to unseen tasks and LLMs, and the contributions of memory and inference choices.

4 EXPERIMENTS

  • The evaluation spans 14 tasks across six domains, with Phase 1 optimizing backbones in user-defined workflows and Phase 2 generating workflows and selecting agents and backbones.Phase 1 tests Depth = 1, Width = 3 and Depth = 2, Width = 2; out-of-domain tasks are used only for evaluation.Source: §4 · pp. 6–7

4.1 GRAPHPLANNER OUTPERFORMS SINGLE-ROUND AND MULTI-ROUND ROUTERS

  • +9.3% overall accuracy over the best baseline in Phase 2, with SOTA results on four of five tasks; Phase 1 gains at least +3.8%.Phase 2 also exceeds the best Phase 1 average accuracy by about 5%; gains are larger for Math (+5.0%) and Code (+4.0%) than recognition-focused tasks (around +1.0%).Source: §4.1 · p. 8
  • GraphPlanner lies on the Acc–Cost Pareto frontier, offering higher Acc at equal Cost or lower Cost at equal Acc than baseline routers.Adjusting α shifts the trade-off between high-Acc, high-Cost and lightweight, low-Cost settings.Source: Figure 4 · p. 7, §4.1 · p. 9

4.2 GRAPHPLANNER NICELY GENERALIZES ACROSS UNSEEN TASKS AND LLMS

  • GraphPlanner achieves 78% average Acc across LogicGrid, MGSM, and CommonGen, outperforming GraphRouter (46%), RouterDC (58%), and Router-R1 (38%).It also outperforms GraphRouter and Router-R1 across task domains with LLMs withheld from training, without additional fine-tuning.Source: Table 5 · p. 8, §4.2 · p. 9, Figure 5 · p. 9

4.3 ABLATION STUDIES VALIDATE GR A P HPL A N N E R’S KEY COMPONENTS

  • Removing historical memories substantially reduces performance; Hetero-Graph outperforms Homo-Graph, but both remain inferior to GARNet.The reported ablations distinguish history, role-specific heterogeneity, and GARNet’s modeling of workflow dynamics.Source: Figure 5 · p. 9, §4.3 · p. 10
  • Transductive inference performs slightly better but costs more, while inductive inference is lighter and still outperforms Router-R1.Inductive inference avoids storing or retrieving training interactions; transductive inference uses those histories and incurs additional computational and memory overhead.Source: Figure 5 · p. 9, §4.3 · p. 10

5 CONCLUSION

GraphPlanner casts multi-agent routing as workflow generation in an MDP, using GARNet to integrate historical and workflow memories and reinforcement learning to train the policy. Experiments across 14 tasks and six domains report state-of-the-art performance, robust generalization, and favorable accuracy–cost trade-offs.

  • GraphPlanner casts routing as MDP-based workflow generation, integrating historical and workflow memories through GARNet and training its policy with reinforcement learning.The authors identify richer agent profiles beyond Planner, Executor, and Summarizer as future work.Source: §5 · p. 10

ETHICS STATEMENT

The authors state that the work does not involve human subjects, personal data, or sensitive attributes.

  • The authors report following data-usage and licensing best practices and considering potential risks of bias or misuse.They state that the work does not involve human subjects, personal data, or sensitive attributes.Source: ETHICS STATEMENT · p. 11

REPRODUCIBILITY STATEMENT

GraphPlanner’s context includes related work on automated multi-agent workflows and router limitations, alongside implementation and reproducibility information.

REPRODUCIBILITY STATEMENT

  • The reproducibility statement says datasets are public and that architecture, training settings, and hyperparameters are described in Section 4.It also says training scripts and evaluation code will be released upon publication.Source: REPRODUCIBILITY STATEMENT · p. 11

A ADDITIONAL RELATED WORK

  • Prior multi-agent systems and workflow generators motivate automated collaboration, while existing routers remain limited by one-shot assignment or backbone-only decisions.The described workflow systems largely assume homogeneous capabilities; multi-round routers add iterative decisions but do not model agent roles or heterogeneity.Source: A ADDITIONAL RELATED WORK · p. 17

B GR A P HPL A N N E R TRAINING DETAILS

  • GraphPlanner’s training uses PPO, with the estimated advantage, clipping threshold, current state, chosen action, workflow graph, and historical graph identified in the training description.PPO is described as an actor–critic reinforcement-learning algorithm.Source: B GR A P HPL A N N E R TRAINING DETAILS · pp. 17–18

C IMPLEMENTATION DETAILS

GraphPlanner uses a GARNet-parameterized PPO policy and value function to combine local and historical graph information for routing.

C IMPLEMENTATION DETAILS

  • GARNet fuses local and historical state information for PPO policy and value functions, with action probabilities matched against role–LLM embeddings under action masking.Training uses clipped PPO objectives, parallel query rollouts, and early stopping when policy entropy falls below a threshold; evaluation uses greedy decoding and the best running-reward model.Source: C IMPLEMENTATION DETAILS · p. 18

D DATASET AND LLM BACKBONE DETAILS

The appendix describes a 14-task, six-domain evaluation, its benchmark metrics, and a roster of language models spanning three scales.

D DATASET AND LLM BACKBONE DETAILS

  • The evaluation covers 14 tasks across six domains, with held-out tasks used to assess generalization and 12 LLMs grouped into three scales.The benchmark descriptions and sample counts are provided in accompanying tables.Source: Table 6 · p. 18, Table 7 · p. 18, §D.1 · p. 18

D.2 MODEL DESCRIPTIONS

  • The language-model roster covers small, medium, and large configurations, with described examples including Qwen2.5 (7B), CodeGemma (7B), Mistral (7B), and LLaMA-3.1 (8B).Prices and sizes are reported in Table 10.Source: §D.2 · p. 21

D.1 TASK DESCRIPTIONS

  • GSM8K and MATH are described as math benchmarks for multi-step arithmetic reasoning and symbolic solution derivation, respectively.The reported metric for both is accuracy.Source: §D.1 · p. 19
  • MBPP and HumanEval assess Python code generation using unit-test correctness, with pass@1 reported for both.Source: §D.1 · p. 20
  • The benchmark set also includes world-knowledge and question-answering tasks: TriviaQA reports CEM, while MMLU and GPQA report accuracy.GPQA targets specialized scientific understanding; MMLU spans 57 subject areas.Source: §D.1 · pp. 20–21
  • Other described tasks test logic-grid deduction, multilingual arithmetic transfer, and constrained commonsense generation.LogicGrid and MGSM report accuracy; CommonGen reports coverage.Source: §D.1 · p. 21
  • AIME is a 15-problem-per-year advanced mathematics benchmark emphasizing multi-step symbolic reasoning, numeric precision, and long-horizon planning; accuracy is reported.Source: §D.1 · p. 21

D.2 MODEL DESCRIPTIONS

  • Additional model descriptions cover Mistral-Nemo 12B, Nemotron variants, and Mixtral 8×7B and 8×22B.The descriptions characterize Mixtral as sparse MoE models, with the 8×22B variant scaling to larger experts.Source: §D.2 · p. 22

E EXPERIMENTS ON NEW AGENTIC ROLES

GraphPlanner is tested with two additional roles, Thinker and Verifier, in trained, zero-shot, and few-shot settings.

E EXPERIMENTS ON NEW AGENTIC ROLES

  • The new-role experiments assess training on added roles, zero-shot testing without role-specific training, and few-shot testing with 50 historical interactions involving all five roles.The additional roles are Thinker and Verifier, beyond the original three.Source: E EXPERIMENTS ON NEW AGENTIC ROLES · pp. 22–23
  • Adding Thinker and Verifier yields consistent performance improvements when trained, and zero-shot and few-shot settings also generalize effectively to these unseen roles.The comparison covers three settings involving the two added roles.Source: Table 11 · p. 22, E EXPERIMENTS ON NEW AGENTIC ROLES · p. 23

F ADDITIONAL ABLATIONS ON OTHER GRAPH ENCODERS

The ablation compares GARNet with GAT and GraphTransformer across five scenarios, and GraphPlanner with GARNet achieves the strongest overall performance.

F ADDITIONAL ABLATIONS ON OTHER GRAPH ENCODERS

G ADDITIONAL ABLATIONS ON HISTORICAL INFORMATION PROCESSING

This section compares history summaries and retrieval with GraphPlanner’s graph-based memory approach, reporting consistent gains for GraphPlanner across five scenarios.

G ADDITIONAL ABLATIONS ON HISTORICAL INFORMATION PROCESSING

H ADDITIONAL EXPERIMENTS ON NEW DATASET

GraphPlanner shows zero-shot performance on an unseen AIME dataset, low training and inference costs, and workflows that vary with task complexity. The appendix also discloses limited LLM use in manuscript preparation.

H ADDITIONAL EXPERIMENTS ON NEW DATASET

I COMPARISON ON TIME COST

  • 120 minutes total training time and 1.2 seconds per-query inference latency: GraphPlanner has the lowest reported time costs.The comparisons include 360 minutes for R2-Reasoner, 300 minutes for Router-R1, and 395 minutes for supervised routers’ upfront data collection.Source: Table 15 · p. 25, I COMPARISON ON TIME COST · p. 25

L THE USE OF LARGE LANGUAGE MODELS (LLMS)

  • The authors report using an LLM only for grammar correction, sentence restructuring, and minor stylistic refinements.They state that the research design, analysis, and conclusions were produced independently by the authors.Source: L THE USE OF LARGE LANGUAGE MODELS… · p. 25

J ILLUSTRATIVE EXAMPLES OF GRAPHPLANNER

Related papers

Loading 2604.23626v1…