GraphDC : A Divide-and-Conquer Multi-Agent System for Scalable Graph Algorithm Reasoning

Wenjin Li, Jiaming Cui · 2026

Read GraphDC : A Divide-and-Conquer Multi-Agent System for Scalable Graph Algorithm Reasoning by Wenjin Li, Jiaming Cui (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-06671.txt.

Introduction

Wenjin Li and Jiaming Cui propose GraphDC, a multi-agent system that solves graph algorithm problems by dividing them. Language models reason poorly on graphs, whose tangled topology demands systematic multi-step work, especially at large sizes. GraphDC splits an input graph into smaller subgraphs and hands each to a specialized agent for local reasoning.

A master agent then merges the local outputs with information about links between subgraphs to form the final answer. This hierarchy lightens each agent's burden and reduces bottlenecks. Experiments across diverse graph tasks and scales show consistent wins over existing methods, with the largest gains exactly where direct end-to-end reasoning is least reliable.

Catalog record

CREATORWenjin Li, Jiaming Cui
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE36 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.06671

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

GraphDC : A Divide-and-Conquer Multi-Agent System for Scalable Graph Algorithm Reasoning Wenjin Li, Jiaming Cui 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. 1 Introduction Graph is a fundamental mathematical concept for representing relationships between entities [ 26 , 14 , 1 , 9 , 8 ] . Many real-world problems such as infectious disease modeling [ 10 , 35 , 7 ] , supply chain optimization [ 42 ] , and urban infrastructure surveillance [ 31 , 30 ] can be naturally modeled as graphs, where the objective is to reason over structural dependencies among entities rather than treat instances independently. Therefore, graph algorithm reasoning has become central to numerous domains, including social network analysis [ 3 , 18 ] , bioinformatics [ 44 ] , and knowledge graph inference [ 46 , 24 , 39 ] . Over the years, a wide range of specialized architectures have been proposed [ 21 , 29 ] to tackle these tasks. While these models achieve strong performance, they often suffer from limited generalization and usability [ 43 , 41 ] : achieving state-of-the-art results typically requires task-specific designs such as tailored preprocessing pipelines and decoders, which make them less flexible and harder to adapt. This limits their applicability when task formulations, graph characteristics, or supervision settings vary across datasets and applications. Recently, large language models (LLMs) have shown impressive capabilities in natural language interaction, interpretability, and generalization across diverse mathematical tasks [ 15 , 45 , 13 , 22 , 4 , 23 , 11 ] . These properties make LLMs an appealing alternative to specialized graph models, as they offer a unified interface for solving different reasoning tasks with minimal task-specific redesign. This has sparked growing interest in their potential for graph algorithm reasoning. However, the reasoning capacity of a single LLM is inherently constrained: as graph size and density increase, LLM accuracy on graph algorithm reasoning tasks declines sharply. This limitation is particularly pronounced for algorithmic reasoning, where the model must simultaneously track multi-hop dependencies, preserve structural consistency, and execute multi-step logical operations. As a result, directly applying a single LLM to increasingly large graphs is difficult to scale. Figure 1: The framework of GraphDC . Given a mathematical problem on graphs, GraphDC solves it in two steps. In the Graph-Query Decomposition step, a graph splitter first decomposes the graph into several subgraphs. Each specialized agent then processes one subgraph using a sub-query generated by the question describer and performs intra-subgraph algorithm reasoning. Next, in the Hierarchical Reasoning step, a master agent aggregates the answers from all agents, together with inter-subgraph information, to respond to the original question. To mitigate this degradation, several strategies have been explored [ 20 , 6 , 40 , 16 ] . For example, GITA [ 38 ] augments prompts with graph visualizations, while GraphAgent-Reasoner [ 17 ] introduces a multi-agent system where a master agent coordinates a set of smaller agents. These studies suggest that adding structure to the reasoning process can improve performance beyond vanilla prompting. However, existing approaches still face substantial scalability challenges. Although the latter achieves strong accuracy on dense and complex graphs, it requires assigning one agent per node, resulting in severe scalability issues and computational bottlenecks. Such coordination costs grow quickly with graph size, making the framework expensive for large instances. Meanwhile, real-world graphs continue to grow in both scale and complexity, often exceeding the effective reasoning capacity of a single LLM or a naively coordinated multi-agent system. Even as LLMs improve, larger and denser graphs will continue to pose new scalability challenges. This raises two key questions: (1) how can we enable effective reasoning over graphs that exceed current scalability limits, and (2) how can we obtain reliable answers without incurring prohibitive computational costs? In this work, we revisit a classic principle of mathematics: divide the work, then integrate the answers back together. Inspired by distributed graph processing and the divide-and-conquer paradigm [ 28 , 19 ] , we propose GraphDC , a multi-agent system that partitions nodes into subgraphs, assigns a dedicated agent to each subgraph, and employs a master agent to integrate outputs from each subgraph along with inter-subgraph information to solve the overall task for scalable graph algorithm reasoning. Specifically, we first cluster nodes into subgraphs and allocate an agent to each subgraph for intra-subgraph algorithm reasoning. The master agent then aggregates all outputs, incorporating inter-subgraph dependencies, to produce the final solution. Compared with node-level agent assignment, this design reduces the number of agents and coordination overhead while preserving the structural information needed for global reasoning. By constraining each agent to a manageable subgraph, the framework improves both scalability and reasoning reliability on complex graph instances. We validate this framework through extensive experiments, demonstrating substantial gains in both accuracy and scalability. Our results show that GraphDC consistently outperforms strong baselines, with the largest improvements appearing on larger and denser graphs where single-agent methods degrade substantially. These findings indicate that subgraph-level decomposition is an effective way to scale LLM-based graph algorithm reasoning and provide a practical direction for handling graph instances beyond the range of current monolithic approaches. Our main contributions are summarized as follows: • To the best of our knowledge, we are the first to propose a divide-and-conquer multi-agent system (MAS) for scalable graph reasoning. Instead of assigning one agent to each node, our framework decomposes the original graph into subgraphs, enabling multiple agents to collaboratively solve large-scale graph reasoning problems. • To support this divide-and-conquer MAS, we propose an effective graph decomposition algorithm tailored to downstream reasoning tasks. The proposed decomposition strategy produces subgraphs that are more suitable for later agent-level reasoning and facilitates the integration of local solutions into a global answer. • Extensive experiments demonstrate the effectiveness and scalability of our framework. The results show that our method achieves strong performance on challenging graph reasoning tasks, particularly on larger and denser graphs where existing approaches face substantial difficulty. The rest of the paper is organized as follows. Section 2 reviews the related work. Section 3 presents the GraphDC framework and describes how it is applied to graph reasoning tasks. Section 4 evaluates the performance of GraphDC . Finally, Section 5 concludes the paper and discusses directions for future work. 2 Related work We review three lines of research most relevant to our work: classical graph algorithms, machine learning-based graph reasoning

Read the complete text