Skip to content

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

🕒 Published (v1): 2026-04-26 09:38 UTC · Source: Arxiv · Venue: ICLR 2026 · link

Why this paper was selected

Graph-augmented agentic routing improves multi-model LLM system efficiency and accuracy

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

GraphPlanner is a heterogeneous graph memory-augmented router for multi-agent LLM systems that formulates workflow generation as an MDP, jointly selecting both the LLM backbone and agent role (Planner/Executor/Summarizer) at each step. It uses a dual-graph structure (GARNet) combining current workflow memory and historical interaction memory, optimized with PPO. It outperforms single-round and multi-round routers by up to 9.3% accuracy while slashing GPU cost from 186.26 GiB to 1.04 GiB.

Problem

Existing LLM routers either make one-shot single-round assignments (no multi-step reasoning or task decomposition) or multi-round sequential calls (no explicit inter-agent coordination, prone to redundant calls and context conflicts). Neither leverages historical workflow memories nor explicitly models collaboration between heterogeneous agents, leaving a gap in routing for complex, realistic agentic tasks.

Method

GraphPlanner casts agentic routing as an MDP \((S, A, T, r, \gamma)\) where each action \(a_t = (\alpha_t, m_t)\) selects an agent role \(\alpha_t \in \{\text{planner, executor, summarizer}\}\) and an LLM backbone \(m_t\) from \(K\) candidates, giving \(|A| = 3K\) joint actions with dynamic validity masking \(M_t\).

The policy is parameterized by GARNet, a heterogeneous graph neural network maintaining two graphs: - \(G_{\text{workflow}}\): nodes for the current query (\(x_q\), Longformer embedding), responses (\(x_r\)), and shared LLM-role hub nodes (\(x_m = [e_{\text{role}}; U; C]\) concatenating role embedding, utility, and cost). - \(G_{\text{history}}\): mirrors the same structure over past query–response episodes, connected to the same shared role hub nodes.

Encoding is nested: \(H^{(\text{his})} = \text{GARNet}_{\theta_{\text{his}}}(G_{\text{history}})\) updates role hub embeddings from history, then \(H^{(\text{loc})} = \text{GARNet}_{\theta_{\text{loc}}}(G_{\text{workflow}}; H^{(\text{his})})\) injects those into the current workflow. Action scores are computed as \(\text{score}_j = z_t^\top h_{m,j}\) (query embedding dot product with LLM-role node embedding), masked and softmax-normalized. The reward balances utility and cost: \(r_t = U(\hat{y}, y^*) - \alpha C(a_t)\) at the terminal step, and \(-\alpha C(a_t)\) otherwise. The full pipeline is trained end-to-end with PPO.

Key Contributions

  • Defines agentic routing as a new paradigm extending LLM routing to joint (role, backbone) selection within structured multi-agent workflows.
  • Proposes GARNet, a dual heterogeneous graph encoding both current workflow memory and historical interaction memory via shared role hub nodes, enabling inductive and transductive inference.
  • MDP + PPO formulation with a composite reward that explicitly trades off task utility against computational cost.
  • Supports zero-shot generalization to unseen tasks and unseen LLMs without retraining.

Results

  • Phase 1 (routing within predefined workflows): GraphPlanner achieves +12.00% \(\Delta\)Acc over the best single-round baseline (SVM-Router) at Depth=1/Width=3 and +11.69% at Depth=2/Width=2; GPU cost 900–1500 GiB·steps vs. >1500 for KNN/RouterDC baselines.
  • Phase 2 (full workflow generation): +9.3% over best single-round router (Router-KNN at 49.7%); GPU cost reduced from 186.26 GiB to 1.04 GiB.
  • Generalization: 78% average accuracy on out-of-domain tasks (LogicGrid, MGSM, CommonGen), 20–40% higher than prior routers.
  • Unseen LLMs: Handles Mistral-Nemo (12b), Mixtral (8Ă—7b), Mixtral (8Ă—22b) at test time without additional fine-tuning.
  • GraphPlanner lies on the Pareto frontier of accuracy vs. cost across all \(\alpha\) settings.
  • Inductive mode: higher efficiency; transductive mode: higher performance at greater cost.

Limitations

  • Role set is fixed to three roles (Planner/Executor/Summarizer); more fine-grained role taxonomies are not explored.
  • GARNet is a small router model, but it must still access all \(K\) backbone LLMs at inference; true latency savings depend on avoiding large-model calls.
  • PPO training requires reward signal (ground-truth labels), limiting applicability to tasks with well-defined evaluation metrics.
  • The historical memory graph grows over time; scalability of \(G_{\text{history}}\) for very large query corpora is not analyzed.
  • Evaluated on open-weight models only; interaction with proprietary APIs (rate limits, cost structures) is not addressed.

Relevance to Agentic AI / LLM Agents

GraphPlanner directly attacks a core bottleneck in multi-agent LLM systems: how to route tasks efficiently across a heterogeneous pool of agents and models while accumulating and reusing workflow experience. The MDP + GNN formulation is a principled alternative to prompt-based orchestrators (like LangGraph or AutoGen's static role assignments), offering learned, cost-aware routing rather than hand-coded topology. The inductive/transductive inference distinction maps onto a practically important tradeoff—efficiency vs. performance—that deployed agentic pipelines must navigate. The GPU cost reduction (186→1 GiB) is particularly relevant for researchers evaluating whether learned routing can make multi-agent systems economically viable at scale.