Metraipolis › archive › dc_fa7589bae338

GTA: Graph Theory Agent and Benchmark for Algorithmic Graph Reasoning with LLMs — arXiv:2609.12265

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.12265
License (as archived)
CC0-1.0
Archived
2026-10-16T03:02:36.833Z
SHA-256 of the archived text
2b72cb00f5dd4d4bcc12bb556420574de966ab06e3b727bec2c9d6140bf1d396
Stable URL of this page
https://metraipolis.com/documento/dc_fa7589bae338

How to cite

GTA: Graph Theory Agent and Benchmark for Algorithmic Graph Reasoning with LLMs — arXiv:2609.12265 — arXiv (en), https://arxiv.org/abs/2609.12265 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_fa7589bae338 (Metraipolis archive dc_fa7589bae338, sha256 2b72cb00f5dd4d4bcc12bb556420574de966ab06e3b727bec2c9d6140bf1d396)
BibTeX
@misc{dcfa7589bae338,
  title = {GTA: Graph Theory Agent and Benchmark for Algorithmic Graph Reasoning with LLMs — arXiv:2609.12265},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.12265},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_fa7589bae338; sha256 2b72cb00f5dd4d4bcc12bb556420574de966ab06e3b727bec2c9d6140bf1d396},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.12265. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Large Language Models (LLMs) are increasingly asked to reason over structured data such as graphs, yet how reliably they can carry out multi-step graph algorithms in language remains unclear. Existing evaluations tend to use simple tasks on small graphs, to score code generation rather than reasoning over the graph itself, or to fix a single input format. We introduce Graph Theory Bench (GT Bench), a benchmark covering 24 classical graph problems in 44 task-structure settings, with over 100,000 examples across four representations: natural language, structured language, adjacency list, and adjacency matrix. Evaluating eight LLMs on GT Bench shows that accuracy is strongly tied to the input representation, that the best representation shifts with graph density, size, and topology as well as with the model, and that this sensitivity persists, attenuated, in the strongest reasoning models. Building on these observations, we propose the Graph Theory Agent (GTA), which pairs a preference-trained representation selector with plan-and-decompose scaffolding around a frozen executor LLM. GTA lifts Phi-4 from 53.5% to 69.1% on the benchmark's easy split and from 33.0% to 41.5% on its hard split, outperforming eight prompting and agent baselines, and transfers without retraining to GraCoRe and NLGraph. Code for benchmark generation and evaluation: this https URL . The project homepage is available at this https URL .

Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-09-14 in cs.AI).
Categorie arXiv: Artificial Intelligence (cs.AI).
Pagina del lavoro: https://arxiv.org/abs/2609.12265 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T02:51:27.766Z dalla pagina https://arxiv.org/catchup/cs.AI/2026-09-14?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).