Are Large-Language Models Graph Algorithmic Reasoners?
This work addresses a core challenge in AI for researchers and developers by providing a critical benchmark to understand and improve LLMs' structured problem-solving skills, though it is incremental as it focuses on evaluation rather than a new method.
The paper tackled the problem of Large Language Models (LLMs) struggling with multi-step reasoning on explicit graphs by introducing MAGMA, a benchmark for evaluating LLMs on classical graph algorithms like BFS and Dijkstra's, finding persistent challenges that require advanced prompting techniques.
We seek to address a core challenge facing current Large Language Models (LLMs). LLMs have demonstrated superior performance in many tasks, yet continue to struggle with reasoning problems on explicit graphs that require multiple steps. To address this gap, we introduce a novel benchmark designed to evaluate LLM performance on classical algorithmic reasoning tasks on explicit graphs. Our benchmark encompasses five fundamental algorithms: Breadth-First Search (BFS) and Depth-First Search (DFS) for connectivity, Dijkstra's algorithm and Floyd-Warshall algorithm for all nodes shortest path, and Prim's Minimum Spanning Tree (MST-Prim's) algorithm. Through extensive experimentation, we assess the capabilities of state-of-the-art LLMs in executing these algorithms step-by-step and systematically evaluate their performance at each stage. Our findings highlight the persistent challenges LLMs face in this domain and underscore the necessity for advanced prompting techniques and algorithmic instruction to enhance their graph reasoning abilities. This work presents MAGMA, the first comprehensive benchmark focused on LLMs completing classical graph algorithms, and provides a critical step toward understanding and improving their structured problem-solving skills.