Research map / Large language models / Agents, code and math
GraphArena: Evaluating and Exploring Large Language Models on Graph Computation
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces GraphArena, a benchmark of 10 real-world graph computation tasks (4 polynomial, 6 NP-complete) with path-based evaluation that separates correct, suboptimal, hallucinatory and missing answers, evaluates 10 LLMs, and tests CoT, SFT, code writing, and test-time scaling as remedies.
Problem
Existing graph reasoning benchmarks for LLMs rely on synthetic graphs, cover only basic tasks, and grade by string-matching final answers, which allows guessing and hides failure modes on harder problems such as NP-complete graph tasks.
Approach
Sample subgraphs from real-world graphs (DBLP, Social Network, DBpedia, OpenFlights, PubChemQC) across 10 polynomial and NP-complete tasks, and grade LLM outputs by checking the returned solution path for feasibility and optimality against exact solvers, yielding correct, suboptimal, hallucinatory, or missing categories.
Key results
- Claude-3.5-sonnet is the top model; on NP-complete large graphs all LLMs score under 10% accuracy (Claude 7.2%).
- Llama3-8b-SFT rises from 20.2% to 38.1% on large polynomial tasks; Qwen2-7b-SFT rises from 20.4% to 84.3% on small polynomial tasks.
- Code writing lowers hallucination for DeepSeek-V2 on large polynomial tasks from 61.1% to 31.4%.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| increase graph size from small to large | LLMs on polynomial-time tasks · GraphArena polynomial-time tasks | accuracy: Claude-3.5-sonnet: 82.2 -> 58.7; Llama3-70b: 61.2 -> 31.6 | Hurt |
| move from polynomial-time to NP-complete tasks | LLMs on large graphs · GraphArena large graphs | accuracy: Claude-3.5-sonnet: 58.7 -> 7.2; Llama3-70b: 31.6 -> 4.7 | Hurt |
| instruction-tune on 10,000 GraphArena problems with ground-truth solution paths (ablation) | Llama3-8b · Polynomial-time tasks (small graphs) | accuracy: 28.6 -> 54.7 | Helped |
| instruction-tune on 10,000 GraphArena problems with ground-truth solution paths (ablation) | Llama3-8b · Polynomial-time tasks (large graphs) | accuracy: 20.2 -> 38.1 | Helped |
| instruction-tune on 10,000 GraphArena problems with ground-truth solution paths (ablation) | Llama3-8b · NP-complete tasks (large graphs) | accuracy: 1.4 -> 7.5 | Helped |
| prompt to write and execute code (ablation) | GPT-4o · Polynomial-time tasks (small graphs) | accuracy: 76.9 -> 62.7 | Hurt |
| prompt to write and execute code (ablation) | GPT-4o · Polynomial-time tasks (large graphs) | accuracy: 43.5 -> 51.1 | Helped |
| prompt to write and execute code (ablation) | DeepSeek-V2 · Polynomial-time tasks (large graphs) | hallucination: 61.1% to 31.4% | Helped |
| add chain-of-thought examples (ablation) | LLMs on Graph Diameter and Connected Component · GraphArena Diameter and Connected Component tasks | accuracy | Mixed |
| increase test-time attempts using parallel sampling or sequential progressive hints (ablation) | GPT-4o-mini · three large-scale graph tasks | accuracy | Mixed |
| replace Edge List with Adjacency List graph tokenizer (ablation) | GPT-4o · Shortest Distance (large graphs) | accuracy: 0.720 -> 0.774 | Helped |
| replace Edge List with Adjacency Matrix graph tokenizer (ablation) | GPT-4o · Shortest Distance (large graphs) | accuracy: 0.720 -> 0.448 | Hurt |
Surprising findings
- GraphWiz, a graph-tuned Llama2-7b model, scored only 0.2% to 1.2% accuracy on small tasks, attributed to task and format mismatch.
- GNNs achieved the best results on large-scale NP-complete problems, though the authors argue they may be doing pattern-based regression.
Limitations
- Single run per model due to cost, with results reported without variance.
- Small models were evaluated with API or local runs under varying settings; GLM-4-plus and closed models are API-only.
- Test-time scaling improves hallucination but gives limited accuracy gains on complex tasks.
Experimental setup
Datasets: DBLP Social Network (Digg, Flixster, Lastfm, Pokec) DBpedia1M OpenFlights PubChemQC / PCQM4Mv2
Benchmarks: GraphArena
Metrics: accuracy feasibility hallucination rate MRR top-1 probability top-3 probability
Baselines: GPT-4o-mini Random algorithm Greedy algorithm Approximation algorithm GIN GAT GraphSAGE GraphWiz GraphToken
Builds on: NLGraph GraphQA CLRS-Text GraphWiz progressive-hint prompting
Closest papers by meaning
- How Do Large Language Models Understand Graph Patterns? A Benchmark for Graph Pattern Comprehension (ICLR 2025 · similarity 0.91)
- Can Large Language Models Analyze Graphs like Professionals? A Benchmark, Datasets and Models (NeurIPS 2024 · similarity 0.91)
- Talk like a Graph: Encoding Graphs for Large Language Models (ICLR 2024 · similarity 0.90)
- LoReC: Rethinking Large Language Models for Graph Data Analysis (NeurIPS 2026 · similarity 0.89)
- GraphMaster: Automated Graph Synthesis via LLM Agents in Data-Limited Environments (NeurIPS 2025 · similarity 0.89)
- GLBench: A Comprehensive Benchmark for Graph with Large Language Models (NeurIPS 2024 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.