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

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.

📋 한 줄 요약

**[멀티 에이전트 LLM/그래프 추론]** 그래프 알고리즘 문제를 분할 정복으로 분해하고, 부분 그래프 전문 에이전트와 마스터 에이전트가 협업해 대규모 그래프에서도 안정적인 추론을 가능케 하는 GraphDC 제안.

🎯 핵심 기여도

LLM의 그래프 알고리즘 추론 한계를 위한 분할 정복 기반 다중 에이전트 프레임워크 제시
부분 그래프별 전문 에이전트와 마스터 에이전트의 계층적 협업 구조 설계
대규모 그래프 인스턴스에서 견고성과 확장성을 동시에 확보
다양한 그래프 알고리즘 과제·스케일 전반에서 기존 기법 대비 일관된 성능 우위 확인

💡 핵심 아이디어

LLM은 토폴로지가 복잡하고 다단계 추론이 필요한 큰 그래프에서 종단간 추론이 종종 실패한다. 그래프를 작은 부분 그래프로 나누어 개별 에이전트가 국소 추론을 수행하고, 마스터 에이전트가 부분 간 정보를 통합하면 개별 에이전트의 추론 부담과 계산 병목이 모두 완화된다.

🔬 기술적 접근법

**모델/방법론**: GraphDC — 입력 그래프를 부분 그래프로 분할 → 각 부분 그래프를 전담 에이전트가 처리 → 마스터 에이전트가 부분 간 관계 정보를 결합해 최종 해를 합성
**핵심 기법**: 분할 정복 설계 영감의 계층적 다중 에이전트 협업, 국소 추론과 전역 통합의 분리, 부분 그래프 간 cross-information 결합

📊 주요 결과

다양한 그래프 알고리즘 과제와 크기에서 기존 LLM 그래프 추론 기법 대비 일관된 성능 향상
큰 그래프 인스턴스에서 효과가 특히 두드러짐 — 단일 에이전트 end-to-end 추론이 불안정한 영역을 안정화
개별 에이전트의 추론 부담 감소로 견고성 향상

💭 의의 및 한계

**의의**: 컨텍스트 길이와 추론 깊이가 함께 증가하는 그래프 문제에서 LLM 활용 가능 범위를 확장하며, 멀티 에이전트 설계 원칙의 일반적 유용성을 보여준다. **한계**: 에이전트 호출 비용이 부분 그래프 수에 비례해 증가하고, 분할 전략에 대한 의존성·민감도는 추가 분석이 필요하다.

🚀 실용적 활용

소셜 네트워크·지식 그래프 분석에서 LLM 기반 자동 알고리즘 추론
라우팅/스케줄링/추천 등 그래프 최적화 보조
그래프 데이터 기반 자율 데이터 사이언스 에이전트의 코어 추론 모듈