Visual Graph Reasoning via Knowledge Compilation

Rongzheng Wang; Zhe Wang; Ke Qin; Rongwei Wang; Muquan Li; Yizhuo Ma; Yihong Huang; Jielei Wang

cs.MMSep 16, 2026

Visual Graph Reasoning via Knowledge Compilation

Authors: Rongzheng Wang, Zhe Wang, Ke Qin, Rongwei Wang, Muquan Li, Yizhuo Ma, Yihong Huang, Jielei Wang,

Organizations: University of Electronic Science and Technology of China · Ubiquitous Intelligence and Trusted Services Key Laboratory of Sichuan Province · Tsinghua Shenzhen International Graduate School

Abstract

Visual graph reasoning requires answering graph-theoretic questions directly from graph images, where graph topology and state are conveyed visually rather than given in symbolic form. Despite recent progress of vision-language models (VLMs), current approaches to visual graph reasoning still fail on simple visual graph problems. This reveals a fundamental limitation of existing approaches: they prioritize final-answer supervision over the intermediate recovery of an explicit graph representation that preserves graph topology and state from visual input. To address this limitation, we propose VGCompiler, a compilation-centric paradigm for visual graph reasoning via knowledge compilation. VGCompiler organizes reasoning around two compilers: a representation compiler that recovers a structure-preserving intermediate graph representation from visual input, and an operation compiler that compiles query intent under the recovered graph state into an executable graph operation. Specifically, we build VGCompiler on Qwen3-VL-8B and train it with reinforcement learning guided by a layered reward over executability, compiled graph validity, representation quality, and operation quality. VGCompiler uses a frozen observer to summarize graph and question conditions into lightweight signatures, enabling archive retrieval and code reuse across similar regimes. Experiments on three benchmarks GVLQA, VisionGraph, and VGCURE, show that Qwen-VGCompiler, built on an 8B backbone, surpasses the strongest closed-source VLM baseline by 28.9% and the strongest code-based baseline by 23.7%, while maintaining high efficiency. We further evaluate VGCompiler on three real-world domains, including metro routing, logistics delivery, and network fault assessment, where it generalizes across heterogeneous visual graphs and domain-grounded tasks.

Figures & tables

Figure 1. Representative visual graph examples together with a simple reachability evaluation across mainstream VLMs.

Figure 2. Three representative real-world visual graph reasoning scenarios: metro routing, logistics delivery, and network fault assessment.

Figure 3. Graph style and graph state sensitivity: (a) varies visual style while fixing the graph; (b) varies graph-state conditions and downstream operations while fixing style and layout. The results show that robust visual graph reasoning depends on both graph compilation and graph operation.

Figure 4. Overview of VGCompiler. A frozen observer summarizes each graph-question pair into a lightweight condition signature. Guided by a layered reward, the code policy learns a paired code instance for representation recovery and downstream operation. At inference, the signature retrieves the nearest archived code prior and either reuses it directly or revises it into new code according to representation coverage and operation compatibility.

Closed-source VLMs
Method	GVLQA-Base		GVLQA-AUG		VisionGraph		VGCURE		Average
Method	Vis.-Only	Hybrid VL	Vis.-Only	Hybrid VL	Node Rec.	Edge Rec.	Graph Und.	Graph Reas.	Average
GPT-5-mini	$49.40\pm 0.98$	$45.20\pm 1.00$	$46.40\pm 4.81$	$47.60\pm 2.80$	$85.70\pm 1.92$	$1.80\pm 0.07$	$75.00\pm 3.45$	$60.11\pm 2.62$	$50.29\pm 2.11$
GPT-5.2	$53.60\pm 5.51$	$45.20\pm 4.79$	$59.51\pm 7.75$	$51.20\pm 5.49$	$91.70\pm 1.03$	$14.30\pm 1.68$	$85.72\pm 1.75$	$68.51\pm 3.80$	$57.55\pm 3.96$
Gemini-3.1-Flash	$54.80\pm 8.95$	$53.00\pm 12.63$	$47.60\pm 8.56$	$56.00\pm 15.77$	$91.10\pm 0.06$	$6.00\pm 0.92$	$83.92\pm 0.11$	$\underline{77.40\pm 1.07}$	$57.46\pm 6.01$
Gemini-3.1-pro	$\underline{59.11\pm 5.85}$	$52.00\pm 6.78$	$\underline{62.51\pm 8.54}$	$57.40\pm 9.46$	$\bm{96.88\pm 0.73}$	$18.00\pm 1.41$	$\underline{90.68\pm 1.25}$	$75.51\pm 2.98$	$62.83\pm 4.62$

Table 1. Main results on three public visual-graph benchmarks. Vis.-Only denotes visual graph input only, Hybrid VL denotes the setting that combines visual input with adjacency-list input. We report mean

\pm

standard deviation over five runs.

Figure 5. Training dynamics of four optimization objectives. We report smoothed reward, executable rate, compiled graph F1, and final task accuracy during training. LORO-Direct uses result-only reward, LORO-Uncoupled removes representation-operation coupling, LORO-Flat removes executability-and-validity gating, and LORO uses the full layered reward.

Method	Accuracy	In Tokens	Out Tokens	Time
GPT-5-mini	50.29	1.89k	0.05k	4.8s
GPT-5.2	57.55	1.91k	0.13k	7.3s
Gemini-3.1-pro	62.83	1.17k	1.02k	13.1s
DPR + GPT-5.2	68.03	5.26k	3.34k	18.9s
Qwen3-VL-8B + Code	56.99	3.01k	1.91k	12.8s
Qwen-VGCompiler	91.72	3.98k	1.10k	7.7s

Table 2. Inference efficiency on the public benchmarks. For code-based methods, Time includes both model generation and code execution; for closed-source VLMs, the Input/Output tokens are taken from API usage statistics.

Target language	Accuracy	$E$	$V$	F1
Adjacency matrix	82.7	89.7	85.6	76.5
Edge list	84.8	94.0	91.4	80.3
Attr. adjacency list	91.7	96.8	92.8	94.6

Table 3. Ablation on target language. We report task accuracy, executable rate, compiled graph validity, and compiled graph F1 denote as Accuracy,

E

V

, and F1, respectively.

Variant	Accuracy	$E$	$V$	F1
Qwen3-VL-8B + Code	57.0	72.3	74.1	69.8
VGCompiler w/o Archive	80.1	91.0	88.5	89.1
VGCompiler w/o LORO	71.6	94.1	85.4	87.4
VGCompiler	91.7	96.8	92.8	94.6

Table 4. Factorizing the effect of archive priors and LORO on the public benchmarks.

Figure 6. Error analysis on 200 sampled cases. We classify errors into four categories: non executable code, invalid compiled graph, low fidelity compilation, and wrong operation.

Family	#Sig.	Top-1	Top-2	Main split cues
GVLQA-Base	4	47%	79%	Text support; Edge.density
GVLQA-AUG	11	19%	37%	Node.style; Edge.thickness
VisionGraph	7	27%	50%	Node.density; Weight.placement
VGCURE	6	31%	59%	Edge.label; Direction

Table 5. Archive concentration for path-style queries. Top-1 and Top-2 report dominant-signature coverage, and main split cues summarize the factors separating signature groups.

Method	Metro		Logistics		Network
Method	Accuracy	Graph F1	Accuracy	Graph F1	Accuracy	Graph F1
GPT-5.2	$45.7\pm 2.1$	$63.8\pm 1.6$	$30.5\pm 1.8$	$46.5\pm 1.7$	$43.2\pm 2.3$	$59.7\pm 2.0$
Gemini-3.1-pro	$48.2\pm 2.4$	$65.1\pm 1.8$	$33.5\pm 2.0$	$49.1\pm 1.8$	$46.3\pm 1.6$	$62.4\pm 1.6$
InternVL3.5-8B	$19.2\pm 1.6$	$34.8\pm 1.7$	$11.8\pm 1.2$	$27.8\pm 1.1$	$23.7\pm 1.9$	$39.5\pm 1.5$
Qwen3-VL-8B	$23.8\pm 1.2$	$39.7\pm 1.1$	$15.0\pm 1.3$	$31.7\pm 1.2$	$27.3\pm 1.2$	$42.7\pm 1.3$
GITA-7B	$11.3\pm 0.8$	$25.9\pm 0.9$	$8.2\pm 0.6$	$20.4\pm 0.7$	$14.8\pm 1.0$	$29.2\pm 1.0$

Table 6. Results on the real-world generalization benchmark. We report final task accuracy and compiled graph F1.

Figure 7. A real-world case from network fault assessment. The left panel summarizes the query, signature, operation process, and returned answer, while the right panel shows the corresponding network diagram.

Visual Reasoning

Visual reasoning studies how AI systems interpret and combine visual evidence to solve spatial, relational, compositional, and physical problems.

See all 162 papers

Sep 28, 2026

Question-Specific Knowledge Graphs for Efficient Visual Reasoning

Recent work in visual question answering has shown that vision-language models can exhibit strong reasoning capabilities by translating visual inputs into textual representations. The effectiveness of this translation depends on how well visual details are retained; models need to surface and align both explicit and implicit knowledge sufficient to support reasoning, without introducing spurious assumptions. Existing methods that leverage detailed image captions introduce visual details unrelated to the reasoning task, inflating input token counts and increasing computational cost. To address these challenges, we propose VisKG, a reinforcement learning (RL) framework in which models learn to translate visual content into question-specific knowledge graph (KG) representations. This process filters out perceptual noise while preserving the entity-relation structure needed for chain-of-thought reasoning, following the principle of minimum sufficient information. To ensure stable RL post-training, VisKG adopts Group reward-Decoupled Normalization Policy Optimization (GDPO). In addition, we strengthen the supervision stage with negative rationale samples, exposing the model to incorrect reasoning paths before RL post-training. Experimental results across science, mathematics, and general visual understanding benchmarks show that VisKG achieves performance comparable to or better than baselines, while requiring fewer tokens than caption-based representations. Moreover, training VisKG with GDPO improves accuracy by 2% over its GRPO-trained counterpart on average. These results suggest that KG representations are a promising approach for supporting multi-step reasoning and open up future work on adaptively selecting the most suitable representation for a given task.

Ting-Chih Chen, Emile van Krieken, Shujian Yu +1

Vrije Universiteit Amsterdam

VLM Reasoning Knowledge-Based VQA Efficient VLM Inference RL for VLMs

Ask PDF

Aug 7, 2026

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

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.

Yuanfu Sun, Yuanhang Ren, Kang Li +5

New York University · Sensetime Research · Tsinghua University +3

VLM Evaluation Visual Reasoning Multimodal Reasoning

Ask PDF

Oct 9, 2026

MVGraph: Benchmarking LVLMs on Evidence Composition across Multi-View Visual Graph

We introduce MVGraph, a benchmark for evaluating large vision-language models (LVLMs) on multi-graph reasoning where the evidence required by a query is distributed across multiple interrelated visual graph views. Although such evidence commonly resides in source-specific graphs, temporal snapshots, or local observations, existing graph reasoning benchmarks remain confined to a single self-contained structure, assessing only graph perception and reasoning while leaving the alignment and composition of evidence across views underexplored. MVGraph comprises 8k instances spanning 8 graph-theoretic tasks, abstracted from two multi-graph scenarios (partial and temporal graph views). Each problem is programmatically constructed and verified to be unsolvable from a single view. Beyond end-to-end evaluation, we decompose multi-graph reasoning into four complementary capabilities---Perception, Alignment, Composition, and Reasoning---and design 29 diagnostic tasks with 64k instances to probe each one, along with golden intermediate representations for evaluating the intermediate process. Across 15 LVLMs, we reveal the difficulty of multi-graph reasoning and identify cross-view edge alignment and relation-level composition as prominent bottlenecks through stage-oriented diagnostics. Meanwhile, temporal constraints and increasing view counts expose further capability boundaries. Code and data are available at https://github.com/AAAndy-Zhu/MVGraph.

Yingjie Zhu, Han Cheng, Xuefeng Bai +3

Harbin Institute of Technology, Shenzhen, China · Peng Cheng Laboratory, Shenzhen, China

VLM Reasoning VLM Evaluation Large Vision-Language Models

Ask PDF

Abstract

Visual Reasoning

Explore similar work

Question-Specific Knowledge Graphs for Efficient Visual Reasoning

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

MVGraph: Benchmarking LVLMs on Evidence Composition across Multi-View Visual Graph