# GraphOmni: A Comprehensive and Extensible Benchmark Framework for Large Language Models on Graph-theoretic Tasks

arXiv: https://arxiv.org/abs/2504.12764 · HTML: https://mlsanity.com/paper/2504.12764/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Placed in Knowledge- and tool-augmented reasoning, one of 17 directions in LLM reasoning.
- First posted on arXiv 17 Apr 2025.

## Placed in

- LLM reasoning / [Knowledge- and tool-augmented reasoning](https://mlsanity.com/lr/knowledge-and-tool-augmented-reasoning/)

## Built on by (most cited first, 9 of 9)

- [G1: Teaching LLMs to Reason on Graphs with Reinforcement Learning](https://mlsanity.com/paper/2505.18499/) (2025)
- [EGL-SCA: Structural Credit Assignment for Co-Evolving Instructions and Tools in Graph Reasoning Agents](https://mlsanity.com/paper/2605.10366/) (2026)
- [Exposing Weaknesses of Large Reasoning Models through Graph Algorithm Problems](https://mlsanity.com/paper/2602.06319/) (2026)
- [FORGE: Fine-grained Multimodal Evaluation for Manufacturing Scenarios](https://mlsanity.com/paper/2604.07413/) (2026)
- [Are Large Language Models Suitable for Graph Computation? Progress and Prospects](https://mlsanity.com/paper/2606.06865/) (2026)
- [AdaSTORM: Scaling LLM Reasoning on Dynamic Graphs via Adaptive Spatio-Temporal Multi-Agent Collaboration](https://mlsanity.com/paper/2606.16328/) (2026)
- [Graph Evidence Is Not Enough: Diagnosing Native Decoder Use in Graph-Augmented LLMs](https://mlsanity.com/paper/2608.30437/) (2026)
- [When Vision Meets Graphs: A Survey on Graph Reasoning and Learning](https://mlsanity.com/paper/2609.03816/) (2026)
- [GTA: Graph Theory Agent and Benchmark for Algorithmic Graph Reasoning with LLMs](https://mlsanity.com/paper/2609.12265/) (2026)

## Abstract (arXiv)

This paper introduces GraphOmni, a comprehensive benchmark designed to evaluate the reasoning capabilities of LLMs on graph-theoretic tasks articulated in natural language. GraphOmni encompasses diverse graph types, serialization formats, and prompting schemes, significantly exceeding prior efforts in both scope and depth. Through extensive systematic evaluation, we identify critical interactions among these dimensions, demonstrating their substantial impact on model performance. Our experiments reveal that state-of-the-art models like Claude-3.5 and o4-mini consistently outperform other models, yet even these leading models exhibit substantial room for improvement. Performance variability is evident depending on the specific combinations of factors we considered, underscoring the necessity of comprehensive evaluations across these interconnected dimensions. Additionally, we observe distinct impacts of serialization and prompting strategies between open-source and closed-source models, encouraging the development of tailored approaches. Motivated by the findings, we also propose a reinforcement learning-inspired framework that adaptively selects the optimal factors influencing LLM reasoning capabilities. This flexible and extendable benchmark not only deepens our understanding of LLM performance on structured tasks but also provides a robust foundation for advancing research in LLM-based graph reasoning. The code and datasets are available at https://github.com/GAI-Community/GraphOmni.