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

arXiv: https://arxiv.org/abs/2604.23626 · HTML: https://mlsanity.com/paper/2604.23626/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Placed in General LLM agent frameworks and benchmarks, one of 16 directions in LLM agents and tool use.
- Builds on 42 of its 60 references that are in the map.
- First posted on arXiv 26 Apr 2026.

## Placed in

- LLM agents and tool use / [General LLM agent frameworks and benchmarks](https://mlsanity.com/agents/general-llm-agent-frameworks-and-benchmarks/)

## Builds on (most cited first, 30 of 42)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [Qwen3 Technical Report](https://mlsanity.com/paper/2505.09388/) (2025)
- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [Measuring Massive Multitask Language Understanding](https://mlsanity.com/paper/2009.03300/) (2020)
- [Measuring Mathematical Problem Solving With the MATH Dataset](https://mlsanity.com/paper/2103.03874/) (2021)
- [Qwen2.5 Technical Report](https://mlsanity.com/paper/2412.15115/) (2024)
- [Think you have Solved Question Answering? Try ARC, the AI2 Reasoning Challenge](https://mlsanity.com/paper/1803.05457/) (2018)
- [Program Synthesis with Large Language Models](https://mlsanity.com/paper/2108.07732/) (2021)
- [Mistral 7B](https://mlsanity.com/paper/2310.06825/) (2023)
- [GPQA: A Graduate-Level Google-Proof Q&A Benchmark](https://mlsanity.com/paper/2311.12022/) (2023)
- [Self-Instruct: Aligning Language Models with Self-Generated Instructions](https://mlsanity.com/paper/2212.10560/) (2022)
- [Can a Suit of Armor Conduct Electricity? A New Dataset for Open Book Question Answering](https://mlsanity.com/paper/1809.02789/) (2018)
- [Gemma 2: Improving Open Language Models at a Practical Size](https://mlsanity.com/paper/2408.00118/) (2024)
- [Mixtral of Experts](https://mlsanity.com/paper/2401.04088/) (2024)
- [CommonsenseQA: A Question Answering Challenge Targeting Commonsense Knowledge](https://mlsanity.com/paper/1811.00937/) (2018)
- [Large Language Model based Multi-Agents: A Survey of Progress and Challenges](https://mlsanity.com/paper/2402.01680/) (2024)
- [AgentVerse: Facilitating Multi-Agent Collaboration and Exploring Emergent Behaviors](https://mlsanity.com/paper/2308.10848/) (2023)
- [Language Models are Multilingual Chain-of-Thought Reasoners](https://mlsanity.com/paper/2210.03057/) (2022)
- [Generative Verifiers: Reward Modeling as Next-Token Prediction](https://mlsanity.com/paper/2408.15240/) (2024)
- [AFlow: Automating Agentic Workflow Generation](https://mlsanity.com/paper/2410.10762/) (2024)
- [Multi-Agent Collaboration Mechanisms: A Survey of LLMs](https://mlsanity.com/paper/2501.06322/) (2025)
- [Automated Design of Agentic Systems](https://mlsanity.com/paper/2408.08435/) (2024)
- [Rewarding Progress: Scaling Automated Process Verifiers for LLM Reasoning](https://mlsanity.com/paper/2410.08146/) (2024)
- [Scaling Large Language Model-based Multi-Agent Collaboration](https://mlsanity.com/paper/2406.07155/) (2024)
- [RouterBench: A Benchmark for Multi-LLM Routing System](https://mlsanity.com/paper/2403.12031/) (2024)
- [Building Cooperative Embodied Agents Modularly with Large Language Models](https://mlsanity.com/paper/2307.02485/) (2023)
- [Universal Self-Consistency for Large Language Model Generation](https://mlsanity.com/paper/2311.17311/) (2023)
- [Large Language Model Routing with Benchmark Datasets](https://mlsanity.com/paper/2309.15789/) (2023)
- [GraphRouter: A Graph-based Router for LLM Selections](https://mlsanity.com/paper/2410.03834/) (2024)

## Built on by (most cited first, 12 of 12)

- [LLMRouter: Unified Infrastructure for Developing, Evaluating, and Deploying LLM Routers](https://mlsanity.com/paper/2608.06867/) (2026)
- [Self-Evolving Agents as Dynamic Graph Transformation: A Survey and New Perspective](https://mlsanity.com/paper/2608.18104/) (2026)
- [Graph Engineering in the Era of LLM Agents: From Individual Intelligence to System Intelligence](https://mlsanity.com/paper/2608.21156/) (2026)
- [TSRouter: Dynamic Modality-Model Selection for Time Series Reasoning](https://mlsanity.com/paper/2607.08940/) (2026)
- [Conflict-Resilient Multi-Agent Reasoning via Signed Graph Modeling](https://mlsanity.com/paper/2605.19418/) (2026)
- [SkillZip: Contract-Preserving Graph Compression for Scalable Agent Skill Libraries](https://mlsanity.com/paper/2608.05604/) (2026)
- [Rosetta Memory: Adaptive Memory for Cross-LLM Agents](https://mlsanity.com/paper/2606.07711/) (2026)
- [MACE: Memory-Agent Co-Evolution with Adaptive Memory Graphs for Multi-Agent Systems](https://mlsanity.com/paper/2609.21533/) (2026)
- [Learning What to Skip: Counterfactual Credit Assignment for Efficient Multi-Agent LLM Workflows](https://mlsanity.com/paper/2609.30734/) (2026)
- [Receiver-Conditioned Latent Communication gives 94% CacheBack](https://mlsanity.com/paper/2609.32046/) (2026)
- [MemPilot: Orchestrating On-Demand Multimodal Memory Curation for LLM Agents](https://mlsanity.com/paper/2610.06830/) (2026)
- [RouteWeaver: Weaving Mode Selection and Execution into Unified LLM Routing](https://mlsanity.com/paper/2610.19705/) (2026)

## Abstract (arXiv)

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.