Can agents solve complex graph problems better?
MA-GTS: A Multi-Agent Framework for Solving Complex Graph Problems in Real-World Applications
February 27, 2025
https://arxiv.org/pdf/2502.18540This paper introduces MA-GTS, a multi-agent framework designed to solve complex graph theory problems often found in real-world applications like logistics and network optimization. It uses multiple collaborating AI agents, each specialized in a particular task, such as extracting information from text, selecting the right algorithm, and solving the problem.
Key points relevant to LLM-based multi-agent systems:
- Agent Collaboration: MA-GTS showcases a hierarchical structure of specialized agents that collaborate to solve complex problems, offering improved efficiency and accuracy compared to single LLM approaches.
- Mitigation of LLM Limitations: The framework addresses LLM limitations like input length restrictions and inaccurate reasoning on complex graph problems by decomposing tasks and filtering noisy data.
- Dynamic Algorithm Selection: MA-GTS dynamically chooses the most appropriate graph theory algorithm based on problem constraints and graph structure, optimizing for performance.
- Real-World Application Focus: A new dataset, G-REAL, is introduced, focusing on real-world inspired graph problems with noisy text data and implicit graph structures, unlike simpler existing benchmarks.
- Improved Cost-Effectiveness: Despite using multiple agent calls, MA-GTS demonstrated lower inference costs compared to single, larger LLMs due to reduced token consumption.