LLM의 그래프 알고리즘 추론 능력을 향상시키기 위해 분할 정복 전략을 다중 에이전트 프레임워크로 구현한 GraphDC를 제안합니다. 입력 그래프를 더 작은 서브그래프로 분해하고 각 서브그래프를 전문 에이전트가 로컬 추론하며, 마스터 에이전트가 로컬 출력과 서브그래프 간 정보를 통합해 최종 해답을 도출합니다. 이 계층적 설계는 개별 에이전트의 추론 부담을 줄이고 계산 병목을 완화하며 대규모 그래프 인스턴스에서의 견고성을 높입니다. 다양한 과제와 규모에 걸친 실험에서 기존 방법 대비 일관된 성능 향상을 달성했습니다.

• •LLM은 많은 수학 문제에서 강점을 보이지만 트리 구조와 체계적 다단계 추론이 필요한 그래프 알고리즘 과제에서는 성능이 불만족스러adequate하다.
• •GraphDC는 분할 정복 설계를 이용해 입력 그래프를 더 작은 서브그래프로 분해하고 전문 에이전트가 로컈 추론하며 마스터 에이전트가 서브그래프 간 정보와 함께 통합하는 계층적 다중 에이전트 프레임워크다.
• •계층적 설계로 개별 에이전트의 추론 부담과 계산 병목을 감소하고 엔드투엔드 직접 추론이 한계를 보이는 대규모 그래프 인스턴스에서 가장 효과적이다.
• •다양한 과제와 규모에서 기존 방법들을 일관되게 능가하여 그래프 알고리즘 추론에서 LLM 능력의 실질적 확장을 시연했다.