GraphDC: A Divide-and-Conquer Multi-Agent System for Scalable Graph Algorithm Reasoning
Authors: Wenjin Li, Jiaming Cui
Summary
GraphDC is a multi-agent framework for graph algorithm reasoning that uses divide-and-conquer: it splits the input graph into smaller subgraphs, assigns each to a specialized agent for local reasoning, and uses a master agent to integrate local outputs with inter-subgraph information to produce the final answer. This hierarchical design reduces the reasoning burden on individual agents and improves scalability and robustness on large graphs. Experiments show GraphDC consistently outperforms existing methods on diverse graph algorithm tasks, especially on larger instances where direct end-to-end reasoning fails.
Main takeaways:
- GraphDC decomposes graphs into subgraphs, assigns local reasoning to specialized agents, and integrates results via a master agent.
- Inspired by divide-and-conquer algorithms; reduces per-agent reasoning burden and alleviates computational bottlenecks.
- Consistently beats existing methods on graph algorithm reasoning across tasks and scales.
- Especially strong on large graph instances where end-to-end reasoning is unreliable.
- Demonstrates that hierarchical multi-agent design improves robustness and scalability for complex structured reasoning.
Relevance
Not directly related to my persona/marker implantation or conditional behavior work. This is a multi-agent system for graph algorithms. Only tangentially relevant if I ever wanted to decompose persona-space exploration into sub-agents, but that's far from my current research focus.
Abstract
arXiv:2605.06671v1 Announce Type: new Abstract: Large Language Models (LLMs) have demonstrated strong potential for many mathematical problems. However, their performance on graph algorithmic tasks is still unsatisfying, since graphs are naturally more complex in topology and often require systematic multi-step reasoning, especially on larger graphs. Motivated by this gap, we propose GraphDC, a Divide-and-Conquer multi-agent framework for scalable graph algorithm reasoning. Specifically, inspired by Divide-and-Conquer design, GraphDC decomposes an input graph into smaller subgraphs, assigns each subgraph to a specialized agent for local reasoning, and uses a master agent to integrate the local outputs with inter-subgraph information to produce the final solution. This hierarchical design reduces the reasoning burden on individual agents, alleviates computational bottlenecks, and improves robustness on large graph instances. Extensive experiments show that GraphDC consistently outperforms existing methods on graph algorithm reasoning across diverse tasks and scales, especially on larger instances where direct end-to-end reasoning is less reliable.