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

🕒 Published (v1): 2026-01-01 · Source: ICLR · Venue: ICLR 2026 · link

Why this paper was selected

Jiaxuan You (UIUC); graph memory augmented routing for multi-agent LLMs

Ask a follow-up

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

TL;DR¶

GraphPlanner is an agentic LLM router that frames multi-agent workflow generation as an MDP over a heterogeneous graph (GARNet), jointly selecting both LLM backbone and agent role (Planner/Executor/Summarizer) at each step. It integrates historical and workflow memories via shared role hub nodes and is trained end-to-end with PPO. On 14 tasks it improves accuracy by up to +9.3% over prior routers while reducing GPU memory from 186.26 GiB to 1.04 GiB.

Problem¶

Existing LLM routers are either single-round (one-shot backbone selection, no task decomposition) or multi-round (sequential context accumulation, but independent calls without explicit role coordination). Neither paradigm models specialization/cooperation across heterogeneous agents, exploits historical workflow traces systematically, or handles the deferred credit-assignment inherent in multi-step agentic pipelines.

Method¶

GraphPlanner casts agentic routing as a Markov Decision Process \((S, A, T, r, \gamma)\) over an evolving heterogeneous graph. At each step \(t\), the state \(s_t = q_t\) is the current query; the action \(a_t = (\alpha_t, m_t)\) jointly picks an agent role \(\alpha_t \in \{\text{planner, executor, summarizer}\}\) and a backbone \(m_t \in \{M_1,\ldots,M_K\}\), giving \(|A|=3K\) possible actions subject to a dynamic validity mask \(M_t\). The terminal reward balances task utility and cost:

\[r_t = \begin{cases} U(\hat{y}, y^*) - \alpha\,C(a_t) & t = T \\ -\alpha\,C(a_t) & t < T \end{cases}\]

The policy \(\pi(a_t|s_t)\) is parameterized by GARNet, a heterogeneous GNN over \(G_t = G_{\text{workflow}} \cup G_{\text{history}}\). Both graphs share a fixed set of role hub nodes (one per LLM–role pair), so historical and current workflow information flows through a common interface. Node features include Longformer-embedded queries/responses and role hub nodes encoding \([\text{role embedding}; U; C]\). A nested dual-graph encoding first encodes \(G_{\text{history}}\) to produce role embeddings \(H^{(\text{his})}\), then feeds these into the workflow encoder: \(H^{(\text{loc})} = \text{GARNet}_{\theta_{\text{loc}}}(G_{\text{workflow}}; H^{(\text{his})})\). Action scores are \(\text{score}_j = z_t^\top h_{m,j}\), masked and softmax-normalized. The full pipeline is optimized with PPO supporting both inductive (no test-time graph) and transductive (test queries added to \(G_{\text{history}}\)) inference.

Key Contributions¶

Formalizes agentic LLM routing as a joint backbone + role-selection MDP, introducing the Planner/Executor/Summarizer role taxonomy into the routing decision.
GARNet: a heterogeneous graph that unifies workflow memory and historical memory via shared role hub nodes, enabling multi-round context without temporal graph overhead.
Nested dual-graph encoding that injects historical role-performance signals into current workflow decisions.
PPO-based end-to-end training with a composite reward penalizing computational cost at every step and rewarding task utility only at termination.
Supports inductive (efficiency-oriented) and transductive (performance-oriented) inference modes.
A two-phase evaluation protocol distinguishing routing within fixed workflows (Phase 1) from full workflow generation (Phase 2).

Results¶

Phase 1 (routing within predefined workflows, Depth=1/Width=3 and Depth=2/Width=2): GraphPlanner achieves +12.00% and +11.69% \(\Delta\)Acc over the best single-round baseline (RouterDC/KNN), with cost ~900–1500 GiB·token vs. ~1500–3000 for top competitors.
Phase 2 (full workflow generation): GraphPlanner reaches 63.6% average accuracy vs. best single-round router at 54.3%, a +9.3% gain; GPU cost reduced from 186.26 GiB to 1.04 GiB relative to the best-performing multi-round competitor.
Zero-shot generalization on out-of-domain tasks (LogicGrid, MGSM, CommonGen): 78% average accuracy, 20–40% higher than previous routers.
Unseen LLMs: generalizes without fine-tuning to three withheld models (Mistral-Nemo 12b, Mixtral 8×7b, 8×22b).
Pareto-optimal across all tested \(\alpha\) (cost–utility tradeoff) values in Phase 2.
Transductive mode outperforms inductive mode in accuracy; inductive mode is more efficient.

Limitations¶

Agent role vocabulary is fixed to three types (Planner/Executor/Summarizer); more specialized roles (e.g., critic, verifier) are not modeled.
PPO training requires task-specific reward signals; applying to open-ended generation tasks with non-discrete utility (e.g., creative writing) is non-trivial.
GARNet's historical graph grows with episodes; scalability at very long deployment horizons is not analyzed.
Phase 2 evaluation is limited to 14 tasks across 6 domains with a specific pool of 12 LLMs; coverage of proprietary frontier models is absent.
The paper does not study robustness to noisy or adversarial queries in the agentic pipeline.

Relevance to Agentic AI / LLM Agents¶

GraphPlanner directly advances the nascent subfield of agentic routing—deciding not just which model to call, but which role it should play within a structured multi-agent workflow—framing it as a reinforcement learning problem over graph memory rather than a static classifier. The GARNet mechanism, which accumulates and queries historical multi-agent interaction traces, is a concrete instantiation of episodic memory for LLM agents, a key open challenge in the field. The MDP formulation with deferred rewards and dynamic action masking provides a principled template for any system where multi-step agent coordination must be optimized end-to-end. For researchers building heterogeneous agent ensembles, this work demonstrates that lightweight graph-based coordinators can match or exceed large-model multi-round approaches while drastically reducing inference cost.