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

1. Problem Statement

While Large Language Model (LLM) routing has successfully integrated diverse models to balance efficiency and performance, existing methods are largely confined to single-round or multi-round settings that lack true agentic capabilities.

• Limitations of Current Routers:
  • Single-round routers make one-shot assignments based on query embeddings, lacking the ability to decompose tasks or coordinate multiple models.
  • Multi-round routers allow sequential calls but treat them as independent steps rather than a cooperative workflow, leading to redundant calls, context conflicts, and failure to leverage complementary strengths.
  • Lack of Memory: Existing routers rarely utilize historical interaction data (past workflows, errors, and successful collaborations) to inform future routing decisions.
  • Static Roles: They typically only select a model backbone, ignoring the need to assign specific agent roles (e.g., Planner, Executor) to different models within a workflow.

The core challenge is how to extend routing into agentic LLM settings where the system must dynamically plan, decompose tasks, assign heterogeneous roles to different models, and leverage historical memory to optimize both accuracy and computational cost.

2. Methodology: GraphPlanner

GraphPlanner proposes a heterogeneous graph memory-augmented agentic router that formulates workflow generation as a sequential decision-making process.

A. Formulation as a Markov Decision Process (MDP)

The routing process is modeled as an MDP $(S, A, T, r, \gamma)$:

• State ($S$): Defined by the current query under resolution. Contextual signals are captured implicitly through an evolving workflow memory graph.
• Action ($A$): At each step, the router selects a pair $(\alpha_t, m_t)$, where $\alpha_t$ is the agent role (Planner, Executor, or Summarizer) and $m_t$ is the LLM backbone from a heterogeneous pool.
  • Planner: Decomposes complex queries into sub-queries.
  • Executor: Generates responses.
  • Summarizer: Condenses intermediate outputs.
  • Constraints: Dynamic masks ensure semantic validity (e.g., preventing a Summarizer at the first step).
• Transition ($T$): Updates the workflow graph based on the action (e.g., decomposing a query or generating a response).
• Reward ($r$): A composite reward balancing task utility (accuracy, BLEU, etc.) and computational cost (token usage, GPU time).

B. Heterogeneous Graph Memory (GARNet)

The core innovation is GARNet, a heterogeneous graph neural network that integrates two types of memory:

1. Workflow Memory Graph ($G_{workflow}$): Represents the current query's execution state, connecting queries, responses, and roles.
2. Historical Memory Graph ($G_{history}$): Aggregates past interactions, capturing successful collaboration patterns, error modes, and efficient divisions of labor.

Key Architectural Features:

• Shared Role Hub Nodes: Instead of creating new nodes for every role instance, GraphPlanner uses fixed "role hub" nodes (e.g., "LLaMA-Planner", "Gemma-Executor") shared across both graphs. This allows the model to aggregate information from the current workflow and historical data through a unified interface.
• Nested Dual-Graph Encoding: The historical graph is encoded first to update role hub embeddings, which are then injected into the workflow graph encoder. This allows the current decision to be informed by accumulated historical experience.
• Message Passing: Uses residual connections to aggregate messages from neighbors, enabling the router to reason over complex, heterogeneous dependencies.

C. Optimization via Reinforcement Learning

The policy network is trained using Proximal Policy Optimization (PPO). The agent learns to maximize the expected discounted return, jointly optimizing for:

• Task Performance: Accuracy on the final answer.
• Efficiency: Minimizing GPU costs and token usage.

3. Key Contributions

1. Agentic Routing Framework: Shifts the paradigm from simple model selection to workflow generation, where the router dynamically decides both the agent role and the model backbone at each step.
2. Heterogeneous Graph Memory (GARNet): Introduces a novel mechanism to capture and leverage historical interaction memories alongside current workflow states. This supports both inductive (lightweight, no history) and transductive (history-aware, higher performance) inference.
3. Joint Optimization: Successfully balances the trade-off between computational cost and task accuracy through RL, avoiding the "brute force" approach of multi-round routers.
4. Generalization: Demonstrates robust zero-shot capabilities on unseen tasks and unseen LLM backbones without fine-tuning.

4. Experimental Results

The authors evaluated GraphPlanner across 14 diverse tasks spanning 6 domains (Math, Code, Commonsense, World Knowledge, Popular, Out-of-Domain).

• Performance vs. Baselines:
  • Phase 1 (Optimizing within fixed workflows): GraphPlanner improved average accuracy by +3.8% over the strongest baselines.
  • Phase 2 (Generating optimal workflows): GraphPlanner achieved a +9.3% accuracy improvement over the best baseline (Router-R1).
  • Cost Efficiency: It reduced GPU cost dramatically from 186.26 GiB (Router-R1) to 1.04 GiB while maintaining superior accuracy.
• Pareto Frontier: GraphPlanner consistently forms the Pareto frontier, offering better accuracy for the same cost or lower cost for the same accuracy compared to single-round and multi-round routers.
• Generalization:
  • Unseen Tasks: Achieved 78% average accuracy on out-of-domain tasks (LogicGrid, MGSM, CommonGen), significantly outperforming baselines (46–58%).
  • Unseen LLMs: Demonstrated strong zero-shot generalization to LLMs not seen during training (e.g., Mistral-Nemo, Mixtral variants).
• Ablation Studies:
  • Removing historical memory caused a substantial performance drop, confirming the value of $G_{history}$.
  • Heterogeneous graph encoding outperformed homogeneous graph variants, proving the importance of distinguishing agent roles.
  • The transductive mode (using history) yielded higher accuracy, while the inductive mode offered a lightweight alternative with competitive performance.

5. Significance

GraphPlanner represents a significant advancement in the field of Multi-Agent LLM Systems.

• Scalability: By using a lightweight graph-based router, it avoids the massive computational overhead of running multiple LLMs blindly or using heavy multi-round reasoning loops.
• Adaptability: It moves beyond static routing rules, enabling systems that learn from past interactions to dynamically construct the most efficient workflow for a specific query.
• Practicality: The ability to reduce GPU costs by orders of magnitude while improving accuracy makes complex agentic workflows feasible for real-world deployment.
• Future Direction: It opens new avenues for research into automated workflow generation, heterogeneous agent collaboration, and memory-augmented routing in large-scale AI systems.

In summary, GraphPlanner solves the critical gap between static model routing and dynamic agentic collaboration by leveraging heterogeneous graph memory to make intelligent, cost-aware, and context-rich routing decisions.