Are Large Language Models Suitable for Graph Computation? Progress and Prospects

A new review finds large language models show promise for simple graph computation tasks but remain unreliable for large-scale, exactness-demanding problems, according to a paper posted to arXiv on 5 June 2026 [1]. The study, which surveys existing methods at the intersection of LLMs and graph computation, proposes a role-based taxonomy that divides approaches into two paradigms: LLMs as executors and LLMs as planners [1]. In the executor role, models attempt to solve graph tasks directly from textual descriptions and instructions. In the planner role, models formulate problems, decompose reasoning steps, and invoke external tools or agents to carry out the computation [2]. The authors argue that LLMs as executors offer a convenient interface for ordinary users but are constrained to smaller graphs and yield high accuracy only on relatively simple tasks [3]. By contrast, planner-based approaches that shift exact computation to external tools achieved near-perfect performance on several widely used benchmarks and demonstrated strong scalability on large-scale graphs [3]. Prior surveys at the intersection of LLMs and graphs have focused on graph learning, text-attributed graphs, or graph-language modeling, leaving a gap that the new review aims to fill [1]. Other recent work has organized LLM-graph integration methods into categories such as enhancer, predictor, and alignment component, reflecting the varied roles language models can play in graph-related tasks [5]. A separate benchmarking study tested five LLMs—including GPT-4, GPT-3.5, Claude-2, Llama-2, and Palm-2—on ten graph traversal problems of increasing complexity and found an inverse relationship between performance and the average degrees of freedom of traversal per node, as well as a negative impact from k-shot prompting on graph reasoning tasks [10]. The new review concludes that LLMs are suitable for assisting graph computation as planners that interpret, decompose, and delegate tasks to reliable tools or code, while as standalone executors they are appropriate only for small graphs and scenarios where accuracy requirements are not stringent [4]. The paper also proposes four future directions: developing semantic graph benchmarks, optimizing multi-step execution for complex graph queries, preserving the privacy of graphs in prompts and training data, and adapting LLMs to domain-specific graph structures [3].