# GTA agent and GT Bench improve LLM graph reasoning accuracy

Digest AI · Research · published 2026-09-11T04:00:00Z · updated 2026-09-14T04:00:00Z

Canonical: https://digestai.news/story/maagl-framework-improves-graph-reasoning-with-multi-agent-collaboration

## Summary

Researchers have introduced Graph Theory Bench (GT Bench), a comprehensive evaluation suite designed to test Large Language Models on complex graph reasoning tasks. The benchmark covers 24 classical graph problems across 44 different task-structure settings, utilizing over 100,000 examples presented in four distinct formats: natural language, structured language, adjacency lists, and adjacency matrices. This approach addresses the limitations of previous evaluations, which often relied on simple tasks or focused on code generation rather than direct reasoning over graph structures.

The study evaluated eight different LLMs, revealing that model accuracy is highly sensitive to the input representation used. The optimal representation varies depending on graph density, size, topology, and the specific model being tested. Even the most advanced reasoning models showed this sensitivity, though it was somewhat attenuated compared to smaller models.

To address these challenges, the authors proposed the Graph Theory Agent (GTA). This system combines a preference-trained representation selector with plan-and-decompose scaffolding around a frozen executor LLM. GTA significantly improved performance, lifting the Phi-4 model from 53.5% to 69.1% on easy tasks and from 33.0% to 41.5% on hard tasks. The agent outperformed eight other prompting and agent baselines and demonstrated transferability to other benchmarks like GraCoRe and NLGraph without requiring retraining.

## Key points

- GT Bench evaluates LLMs on 24 graph problems using over 100,000 examples across four data representations.
- GTA agent improves Phi-4 accuracy from 53.5% to 69.1% on easy graph reasoning tasks.
- Model performance on graph tasks is highly sensitive to input representation format and graph topology.

## Why it matters

This work provides critical insights into the limitations of LLMs in structured reasoning, offering a robust benchmark and an effective agentic framework to enhance performance on complex graph-based problems.

## Sources

1. [GTA: Graph Theory Agent and Benchmark for Algorithmic Graph Reasoning with LLMs](https://arxiv.org/abs/2609.12265) (arXiv cs.AI, 2026-09-14, primary source)
2. [Multi-Agent Agentic Graph Learning via Structural Signatures](https://arxiv.org/abs/2609.09565) (arXiv cs.AI, 2026-09-11, primary source)

## Cite

Digest AI, "GTA agent and GT Bench improve LLM graph reasoning accuracy", 11 September 2026, https://digestai.news/story/maagl-framework-improves-graph-reasoning-with-multi-agent-collaboration

---

Written by Digest AI's editorial model from the linked sources; the sources are the record. Headlines, digests and key points are written by Digest AI and may be quoted with a link to the story page. Linked articles belong to their publishers. Terms: https://digestai.news/terms#reuse
JSON: https://digestai.news/story/maagl-framework-improves-graph-reasoning-with-multi-agent-collaboration.json