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

📄 arXiv: 2606.16328v1 📥 PDF

作者: Bing Hao, Ruijie Wang, Haodong Qian, Yunlong Chu, Yuhang Liu, Yumeng Lin, Minglai Shao, Jianxin Li

分类: cs.AI

发布日期: 2026-06-15

🔗 代码/项目: GITHUB

💡 一句话要点

提出AdaSTORM以解决动态图推理的扩展瓶颈问题

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 动态图推理 多智能体系统 自适应分区 协作推理 大型语言模型

📋 核心要点

  1. 现有大型语言模型在动态图推理中存在扩展瓶颈，无法处理超过数十个节点的图。
  2. 提出AdaSTORM框架，通过自适应分区和协作推理，将动态图推理分为两个阶段，提升推理能力。
  3. 实验结果显示，AdaSTORM在千节点图推理中准确率超过90%，显著优于七个基线模型，且在真实数据集上具有良好的泛化能力。

📝 摘要（中文）

大型语言模型（LLMs）在动态图推理中展现出显著潜力，但面临扩展瓶颈：现有模型只能处理数十个节点的图，受限于指数级推理开销和有限的上下文窗口。尽管多智能体系统（MAS）在集体推理和拓扑感知调度方面具有优势，但其在动态图中的应用尚未被探索。本文提出了AdaSTORM框架，将大规模动态图推理重构为两个阶段：自适应分区和协作推理。AdaSTORM是首个针对动态图推理的多智能体框架，实验表明其成功突破扩展瓶颈，能够在多个大规模动态图设置中以超过90%的准确率处理千节点图，显著优于七个竞争基线，并在现有基准上实现了最先进的准确率。

🔬 方法详解

问题定义：本文旨在解决大型语言模型在动态图推理中的扩展瓶颈问题，现有方法因推理开销和上下文窗口限制，无法处理大规模图。

核心思路：提出AdaSTORM框架，通过自适应分区将大规模动态图划分为适合模型推理能力的子区域，并通过协作推理实现多智能体的集体推理。

技术框架：AdaSTORM框架分为两个主要阶段：自适应分区阶段负责将动态图划分为多个子区域，协作推理阶段则通过多智能体架构对这些子区域进行推理，确保推理过程的高效性和准确性。

关键创新：AdaSTORM是首个针对动态图推理的多智能体框架，创新性地将图推理任务与多智能体系统结合，显著提升了推理能力和效率。

关键设计：在设计中，采用了自适应分区算法以最小化推理成本，并通过拓扑对齐的方式优化多智能体之间的协作，确保推理过程的高效性。

📊 实验亮点

实验结果表明，AdaSTORM在处理千节点图时，准确率超过90%，显著优于七个竞争基线模型，且在多个大规模动态图设置中表现出色，达到了最先进的准确率。

🎯 应用场景

该研究的潜在应用领域包括社交网络分析、交通流量预测和生物信息学等动态图结构任务。通过提升动态图推理的能力，AdaSTORM能够为实时决策提供支持，具有重要的实际价值和未来影响。

📄 摘要（原文）

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: (i) Adaptive Partitioning, partitioning large-scale dynamic graphs into subregions that match the model's reasoning capacity while minimizing inference cost; and (ii) 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 outperforms seven competitive baselines. Furthermore, it achieves state-of-the-art accuracy on existing benchmarks and generalizes robustly to real-world datasets. The source code is available at: https://github.com/irisorchid107/AdaSTORM/.