Abstract
Large Language Models (LLMs) demonstrate remarkable potential in dynamic graph reasoning, but suffer from a scaling bottleneck: current models can only handle graphs with tens of nodes, constrained by exponential reasoning overhead and finite context windows. While multi-agent systems (MAS) offer collective reasoning and topology-aware orchestration, capabilities naturally suited for graph-structured tasks, their application to dynamic graphs remains unexplored.
This paper presents Scaling LLM Reasoning on Dynamic Graphs via Adaptive Spatio-Temporal Multi-Agent Collaboration (AdaSTORM), a framework that reformulates large-scale dynamic graph reasoning into two stages:
- Adaptive Partitioning: partitioning large-scale dynamic graphs into subregions that match the model's reasoning capacity while minimizing inference cost;
- Collaborative Reasoning: aligning graph partition topologies with a spatio-temporal decoupled multi-agent architecture.
AdaSTORM is the first multi-agent framework tailored for dynamic graph reasoning. Extensive experiments show that AdaSTORM successfully breaks through the scaling bottleneck, scaling reasoning to thousand-node graphs with over 90% accuracy across several large-scale dynamic graph settings without external tools, significantly outperforming seven competitive baselines. Furthermore, it achieves state-of-the-art accuracy on existing benchmarks and generalizes robustly to real-world datasets.
Source code is available at: AdaSTORM GitHub
Blogger's Review:
AdaSTORM addresses scaling issues in dynamic graph reasoning through adaptive partitioning and collaborative reasoning, showcasing the potential of multi-agent systems in handling complex structured data. Its performance in practical applications is noteworthy, indicating future breakthroughs in the field of graph neural networks.