Research map / Large language models / Agents, code and math
GraphOmni: A Comprehensive and Extensible Benchmark Framework for Large Language Models on Graph-theoretic Tasks
Hao Xu, Xiangru Jian, Xinjian Zhao, Wei Pang, Chao Zhang, Suyuchen Wang, Qixin Zhang, Zhengyuan Dong, Joao Monteiro, Bang Liu, Qiuzhuang Sun, Tianshu Yu
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use reasoning model Qwen-3 (8B) instead of Qwen-2.5 (7B) | Qwen · GraphOmni BFS order (Hard) | accuracy (%): 1.38 -> 29.53 | Improved |
| scale Qwen-2.5 from 7B to 72B | Qwen-2.5 · GraphOmni BFS order (Easy) | accuracy (%): 21.46 -> 71.41 | Improved |
| scale Qwen-2.5 from 7B to 72B | Qwen-2.5 · GraphOmni Triangle (Hard) | accuracy (%): 4.45 -> 4.73 | No clear effect |
| use Qwen-3 (8B) instead of Qwen-2.5 (72B) | Qwen · GraphOmni Triangle (Hard) | accuracy (%): 4.73 -> 19.54 | Improved |
| raise difficulty from Easy to Hard | o4-mini · GraphOmni BFS order | accuracy (%): 95.46 -> 32.45 | Hurt |
| raise difficulty from Easy to Hard | o4-mini · GraphOmni Triangle | accuracy (%): 84.54 -> 17.53 | Hurt |
| add algorithm-based prompts | LLMs · GraphOmni BFS order and Diameter | accuracy | Improved |
| add multi-shot exemplars to prompt | open-source models · GraphOmni (avg over tasks) | accuracy | Improved |
| add multi-shot exemplars to prompt | closed-source models · GraphOmni (avg over tasks) | accuracy | No clear effect |
| vary serialization format and prompt scheme | GPT-4o · GraphOmni (single task) | accuracy: gaps of up to 40% | Mixed |
| increase graph size to 30-50 nodes | LLMs · GraphOmni BFS order and Triangle | accuracy | Hurt |
| increase graph size to 30-50 nodes | LLMs · GraphOmni Connectivity and Cycle | accuracy | No clear effect |
Closest papers by meaning
- GraphArena: Evaluating and Exploring Large Language Models on Graph Computation (ICLR 2025 · similarity 0.93)
- Talk like a Graph: Encoding Graphs for Large Language Models (ICLR 2024 · similarity 0.93)
- $\texttt{G1}$: Teaching LLMs to Reason on Graphs with Reinforcement Learning (NeurIPS 2025 · similarity 0.91)
- GraphChain: Large Language Models for Large-scale Graph Analysis via Tool Chaining (NeurIPS 2025 · similarity 0.90)
- Reasoning on Graphs: Faithful and Interpretable Large Language Model Reasoning (ICLR 2024 · similarity 0.90)
- Can Large Language Models Analyze Graphs like Professionals? A Benchmark, Datasets and 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.
