GraphVerse: A Comprehensive Visual Graph Reasoning Benchmark for Multimodal Large Language Models

The gist The researchers introduce GraphVerse, a unified benchmark that jointly evaluates perception, visual reasoning, and text-based graph reasoning in Multimodal Large Language Models (MLLMs) under both single-image and paired-image settings.

Limitations of Existing Benchmarks

Prior Visual Graph Reasoning (VGR) benchmarks often reduce the task to visual perception followed by text-based reasoning, restrict evaluation to single-image settings, rely on answer-only metrics, and underrepresent realistic graph-centric scenarios<ref:2608.06769#pg2> Existing evaluations still provide limited insight into whether these models can truly reason over structured visual information<ref:2608.06769#pg2> These limitations motivate the following research question: Can we build a solver-verifiable benchmark that evaluates visual graph understanding and reasoning end-to-end, moving from visual perception to both vision-based and textbased reasoning, while providing diagnostic signals beyond final accuracy and spanning difficulty from tractable to combinatorialhard problems in realistic scenarios<ref:2608.06769#pg3>

GraphVerse Benchmark Design

GraphVerse is a benchmark for comprehensively evaluating MLLMs’ robust and in-depth visual graph understanding and reasoning<ref:2608.06769#pg4> It spans diverse multimodal graph problems across a wide range of complexity, organized into single-image VGR, which reasons over one rendered graph, and paired-image VGR, which requires cross-image structural alignment<ref:2608.06769#pg5> The tasks cover both polynomial-time Poly and NP-hard NPH problems<ref:2608.06769#pg6> Examples of single-image VGR tasks include Poly Shortest Distance (SD), Poly Diameter, and NPH Traveling Salesman (TSP)<ref:2608.06769#pg6> Paired-image VGR includes NPH Graph Edit Distance (GED) and NPH Maximum Common Subgraph (MCS)<ref:2608.06769#pg6>

Graph-Centric Image Editing Strategies

To push models beyond one-shot perception toward genuine reasoning, GraphVerse introduces a suite of four graphcentric image editing strategies<ref:2608.06769#pg5> These include:

1. Image-Graph Patch Perturbation, which manipulates image patches to disrupt the visual realization of graph patches<ref:2608.06769#pg6>

2. Cross-Graph Composition, which requires models to bind nodes across separate images and apply cross-links to compose a new graph<ref:2608.06769#pg6>

3. Graph Attentional Focusing, which targets selective visual attention by forcing the model to find and recover a target connected subgraph<ref:2608.06769#pg6>

4. Spatially-Conditioned Recoloring, which enforces recoloring based on spatial relations to trigger visual spatial reasoning<ref:2608.06769#pg6>

Evaluation Protocol and Scoring

GraphVerse employs VGR-Score, a process-sensitive metric that evaluates reasoning quality beyond final answer accuracy<ref:2608.06769#pg6> The scoring agent is given the model’s full output, the graph evidence EG, and ground-truth answers to extract key reasoning steps and evaluate their consistency against EG<ref:2608.06769#pg6> The VGR-Score is formulated as Score = λRstep + (1 − λ)I[ˆy ∈ A∗], where Rstep measures process correctness, and I[ˆy ∈ A∗] measures final answer accuracy<ref:2608.06769#pg6>

Experimental Findings and Insights

Extensive experiments reveal that visual reasoning is the dominant failure mode of MLLMs, with vision-based reasoning errors accounting for an average of 50% across representative models<ref:2608.06769#pg6> Furthermore, VGR-Score often exceeds accuracy by 30%–40%, suggesting that errors may arise from only a few critical reasoning steps<ref:2608.06769#pg6> The study shows that models exhibit distinct strengths across different GIE settings, with Spatially-Conditioned Recoloring achieving the largest improvement in VGR-S<ref:2608.06769#pg6> Moreover, transferability analysis indicates that reasoning skills learned on GraphVerse can transfer beyond the benchmark to improve performance on other domains, such as MathVista<ref:2608.06769#pg6> The findings suggest that GIE requires visually grounded graph reasoning rather than being reduced to textual transcription<ref:2608.06769#pg6>

Future Directions

The paper concludes by noting that while GraphVerse establishes a systematic VGR benchmark, future work will continue maintaining and extending it to richer multi-image VGR scenarios<ref:2608.06769#pg8> The scalability of GraphVerse is noted as a key advantage, as task difficulty can be adjusted in a simple and controllable manner through the underlying graph structure<ref:2608.06769#pg9>

Conclusion

GraphVerse enables a more faithful and comprehensive assessment of MLLM visual graph reasoning by providing broader task types, GIE strategies that enforce genuine visual reasoning, diverse difficulty, realistic grounding, and fine-grained evaluation<ref:2608.06769#pg10> Extensive experiments not only validate the effectiveness of GIE but also reveal major weaknesses of current MLLMs while showing that VGR-acquired abilities can transfer beyond the original domain<ref:2608.06769#pg10> GraphVerse can serve as a strong benchmark for future visual graph reasoning research<ref:2608.06769#pg10>

References

Marah Abdin, Jyoti Aneja, Hany Awadalla, Ahmed Awadallah, Ammar Ahmad Awan, Nguyen Bach, Amit Bahree, Arash Bakhtiari, Jianmin Bao, Harkirat Behl, Alon Benhaim, Misha Bilenko, Johan Bjorck. 2024. Phi-3 technical report: A highly capable language model locally on your phone<ref:2608.06769#pg10> Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt. 2023. Gpt-4 technical report<ref:2608.06769#pg10> Peter Anderson, Xiaodong He, Chris Buehler, Damien Teney, Mark Johnson, Stephen Gould. 2018. Bottom-up and top-down attention for image captioning and visual question answering<ref:2608.06769#pg10>Zahra Babaiee, Peyman M Kiasari, Daniela Rus, Radu Grosu. 2025. Visual graph arena: Evaluating visual conceptualization of vision and multimodal large language models<ref:2608.06769#pg10>Shuai Bai, Yuxuan Cai, Ruizhe Chen, Keqin Chen, Xionghui Chen, Zesen Cheng, Lianghao Deng, Wei Ding. 2025a. Qwen3-vl technical report<ref:2608.06769#pg10>Shuai Bai, Keqin Chen, Xuejing Liu, Jialin Wang, Wenbin Ge, Sibo Song, Kai Dang, Peng Wang. 2025b. Qwen2.5-vl technical report<ref:2608.06769#pg10>Christian Bizer, Jens Lehmann, Georgi Kobilarov, Sören Auer, Christian Becker, Richard Cyganiak. 2009. Dbpedia - A crystallization point for the web of data<ref:2608.06769#pg10>Wenhu Chen, Xueguang Ma, Xinyi Wang, William W Cohen. 2022. Program of thoughts prompting: Disentangling computation from reasoning for numerical reasoning tasks<ref:2608.06769#pg10>Zhe Chen, Weiyun Wang, Yue Cao, Yangzhou Liu, Zhangwei Gao, Erfei Cui, Jinguo Zhu. 2024. Expanding performance boundaries of open-source multimodal models with model, data, and test-time scaling<ref:2608.06769#pg10>Yuanfu Sun, Kang Li, Dongzhe Fan, Jiajin Liu, Qiaoyu Tan. 2026a. Agentgl: Towards agentic graph learning with llms via reinforcement learning<ref:2608.06769#pg10>Yuanfu Sun, Kang Li, Pengkang Guo, Jiajin Liu, Qiaoyu Tan. 2026b. Mario: Multimodal graph reasoning with large language models<ref:2608.06769#pg10>Yuanfu Sun, Zhengnan Ma, Yi Fang, Jing Ma, Qiaoyu Tan. 2025. Graphicl: Unlocking graph learning potential in llms through structured prompt design<ref:2608.

1. Improve reasoning fidelity using Graph-Centric Image Editing (GIE) strategies; Our strategy is broadly applicable across diverse, realistic visual graph reasoning tasks, which pushes models beyond one-shot perception toward genuine reasoning. This allows the AI system to reconstruct the intended visual structure in the image space, recover the correct graph topology, and then carry out visually grounded reasoning on the recovered structure.

2. Implement a process-sensitive evaluation metric for diagnostic insight; GraphVerse introduces VGR-Score, a process-sensitive metric that evaluates reasoning quality beyond final answer accuracy, allowing researchers to assess intermediate reasoning behaviors which are often overlooked in current methods.

3. Enhance cross-domain transferability through structured supervision; The paper demonstrates that the supervision induced by GIE is transferable, showing the benefit of our RL training is broad rather than narrow: it enhances not only overall answer accuracy, but also the model’s general reasoning ability across diverse mathematical and visual reasoning dimensions.

4. Enable robust comparison between single-image and paired-image reasoning; GraphVerse spans both settings, requiring models to perform cross-image structural alignment, which tests a more realistic setting than prior evaluations that focus only on single-image reasoning.

5. Develop specialized task expertise through GIE fine-tuning; Training with a single GIE strategy is shown to improve performance, indicating that each GIE strategy provides useful and complementary supervision for visual graph reasoning by strengthening the model’s ability to reason over visually grounded structures, salient regions, and relational cues.

6. Move beyond text-only reasoning pipelines; The paper shows that the original visual setting consistently outperforms the MLLM Description baseline, suggesting that GIE requires visually grounded graph reasoning and cannot be fully reduced to textual transcription.

7. Support difficulty scaling via graph structure control; GraphVerse makes difficulty adjustment possible because task difficulty can be adjusted in a simple and controllable manner through the underlying graph structure, unlike traditional benchmarks where scaling is often indirect, less fine-grained, and harder to standardize.

Recent Multimodal Large Language Models (MLLMs) have achieved remarkable progress across diverse vision-language tasks, creating an urgent need for more challenging benchmarks. Yet existing evaluations still provide limited insight into whether these models can truly reason over structured visual information. Visual Graph Reasoning (VGR) offers a compelling testbed for this challenge, requiring models to integrate perception, structural understanding, and multi-step reasoning over graph-based visual inputs. However, prior VGR benchmarks often reduce the task to visual perception followed by text-based reasoning, restrict evaluation to single-image settings, rely on answer-only metrics, and underrepresent realistic graph-centric scenarios. To bridge the gap, we introduce GraphVerse, a unified benchmark that jointly evaluates perception, visual reasoning, and text-based graph reasoning in MLLMs under both single-image and paired-image settings. At its core is a suite of Graph-centric Image Editing (GIE) strategies that modify graph images while preserving their semantics, turning them into active tests of visual reasoning. We further propose VGR-Score, a process-sensitive metric that evaluates reasoning quality beyond final-answer accuracy. Extensive experiments reveal several key limitations of current MLLMs in VGR, while also validating the effectiveness of GIE strategies and the transferability of GraphVerse to broader multimodal reasoning capabilities. The code is available at https://github.com/sunyuanfu/GraphVerse.