AdaSTORM: Scaling LLM Reasoning on Dynamic Graphs via Adaptive Spatio-Temporal Multi-Agent Collaboration

🕒 Published (v1): 2026-06-15 07:32 UTC · Source: Arxiv · link

Ask a follow-up

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

💬 Ask ChatGPT✦ Ask Claude

TL;DR

AdaSTORM is a two-stage multi-agent framework that scales LLM reasoning over dynamic graphs to thousand-node scale by (1) using RL-guided adaptive graph partitioning to decompose large graphs into capacity-matched subregions, and (2) orchestrating spatially and temporally specialized agents over the resulting partition topology. All baselines with standalone or naïve multi-agent setups collapse to near-zero accuracy at this scale; AdaSTORM maintains >90% on several tasks.

Problem

LLM-based dynamic graph reasoning is bottlenecked at tens of nodes: exponential reasoning overhead and finite context windows cause catastrophic failure on larger graphs. Standard multi-agent paradigms (chain, debate) do not help because they operate globally on the full topology and lack graph partitioning mechanisms, so they too hit the combinatorial explosion at scale.

Method

Stage 1 — Adaptive Partitioning: A Capacity Estimator fuses four modalities (LM-encoded query, LM-encoded model profile, GNN structural encoding, learnable latent vector) and outputs per-region reasoning feasibility ϕ̂ᵢ via an MLP trained with binary cross-entropy. A programmatic Cost Estimator traces agent invocations to compute C(P). An RL Adaptive Partitioner initializes with METIS (k₀=5) then iteratively applies region-split and node-migration actions, optimizing a reward:

rₜ = wc(Cₜ₋₁ − Cₜ) + λΦ(Φₜ₋₁ − Φₜ) − λsplit·1split − λreject·1reject

to minimize inference cost while keeping each subregion feasibility ≥ τ. RL is chosen because the objective is non-differentiable and graph partitioning is NP-hard.

Stage 2 — Collaborative Reasoning: Partition topology is mapped to a spatio-temporal decoupled agent graph built on LangGraph. Spatial Agents handle static local topology and cross-region communication via cut-edges. Temporal Agents enforce chronological constraints as either pre-filters or post-validators. All agents share a global LangGraph state enabling parallel execution without external tools.

Dynamic graph events are encoded as lifecycle quadruplets (u, v, s, t) — emergence and deletion timestamps — which the paper shows improves information density over the prior (u, v, t, a/d) format.

Key Contributions

• First multi-agent framework specifically designed for dynamic graph reasoning.
• RL-based adaptive partitioner that jointly minimizes agent invocation cost and infeasibility gap without requiring a fixed partition count k.
• Multimodal Capacity Estimator fusing query, model profile, GNN topology, and latent behavioral signals to predict per-region reasoning feasibility.
• Spatio-temporal agent decoupling extended from single-LLM prompt-level technique to multi-agent architecture level.
• Quadruplet edge representation (u, v, s, t) for compact dynamic graph encoding in prompts.

Results

• Large-scale synthetic benchmarks (N ∈ {500, 800, 1000}): All standalone LLMs (DeepSeek-Distill-7B/14B/32B, GPT-4o mini, DeepSeek-V4-Flash) and chain/debate multi-agent baselines score 0% on Community Detection and Temporal Motif Counting at every scale. AdaSTORM-32B reaches 71%/52%/26% (community detection) and 100%/91%/83% (temporal motif counting) at N=500/800/1000.
• Temporal Motif Counting at N=500: 100% accuracy (Ours-DQwen-32B and -14B).
• Connected Components at N=500: Ours-DQwen-32B achieves 90% vs. 0% for all baselines.
• Capacity Estimator ablation (connected components, N=500): Replacing with random scores drops accuracy from 90%→61% and increases token cost 2× (16,723→33,756 tokens).
• Adaptive Partitioner ablation: AdaSTORM outperforms METIS-STORM, GAP-STORM, KaHIP-STORM, and Random-STORM in both accuracy and token cost at all scales.
• SOTA on existing small-to-medium benchmarks (GraphInstruct, GraphArena, GraphWiz, NLGraph, GPC, LLM4DyG): AdaSTORM-32B matches or exceeds reported SOTA.
• Real-world generalization: Tested on Wikipedia (9,227 nodes), Reddit (10,984), Enron (184), Flights (13,169), UNTrade (255); results vary by task and dataset but demonstrate viability.

Limitations

• Assumes global reasoning can be decomposed into structural subregions and recomposed via inter-region message passing; less suited to tasks requiring rich semantic attributes, external domain knowledge, or ambiguous NL objectives beyond graph structure.
• Treats the backbone LLM as a black-box; overall performance is still subject to local reasoning errors, unstable intermediate outputs, and imperfect capacity estimates.
• Evaluation is restricted to four task types (reachability, motif counting, connected components, community detection); generality to other graph reasoning task families is unverified.
• The RL partitioner and GNN capacity estimator add training overhead and require labeled feasibility data (ground-truth correctness labels per region).

Relevance to Harnesses / Meta-Harnesses

AdaSTORM is a textbook example of a task-adaptive meta-harness: it does not hardcode agent topology but learns it at runtime — the RL partitioner dynamically determines how many agents to spawn, what subproblem each handles, and how they communicate, guided by an explicit capacity model of the backbone LLM. This is directly relevant to harness research because it formalizes the capacity estimation and cost minimization problems that most harnesses leave implicit, and it demonstrates that RL over partition refinement is a viable mechanism for orchestrating agent fleets whose size and topology are not known in advance. The LangGraph shared-state coordination pattern is also a clean reference implementation for cut-edge message passing in topology-aware harnesses.