Graph-of-Mark: Promote Spatial Reasoning in Multimodal Language Models with Graph-Based Visual Prompting

Giacomo Frisoni; Lorenzo Molfetta; Mattia Buzzoni; Gianluca Moro

cs.CVMar 2, 2026

Graph-of-Mark: Promote Spatial Reasoning in Multimodal Language Models with Graph-Based Visual Prompting

Authors: Giacomo Frisoni, Lorenzo Molfetta, Mattia Buzzoni, Gianluca Moro

Organizations: Department of Computer Science and Engineering, University of Bologna

Abstract

Recent advances in training-free visual prompting, such as Set-of-Mark, have emerged as a promising direction for enhancing the grounding capabilities of multimodal language models (MLMs). These techniques operate by partitioning the input image into object regions and annotating them with marks, predominantly boxes with numeric identifiers, before feeding the augmented image to the MLM. However, these approaches treat marked objects as isolated entities, failing to capture the relationships between them. On these premises, we propose Graph-of-Mark (GoM), the first pixel-level visual prompting technique that overlays scene graphs onto the input image for spatial reasoning tasks. We evaluate GoM across 3 open-source MLMs and 4 different datasets, conducting extensive ablations on drawn components and investigating the impact of auxiliary graph descriptions in the text prompt. Our results demonstrate that GoM consistently improves the zero-shot capability of MLMs in interpreting object positions and relative directions, improving base accuracy in visual question answering and localization up to 11 percentage points.

Figures & tables

Figure 1: Illustration of GoM . A multimodal language model is prompted by anchoring the input image in scene graphs expressing spatial object relations that are relevant to solving the task query provided by the user.

Panel of Figure 2 — Figure 2: Qualitative example illustrating the impact of image preprocessing on VQA performance. The same question from VQA-v2 is posed to Qwen2.5-7B using 6 different hard visual prompts, highlighting how pixel transformations can influence the model’s responses. For figure readability, the font size and line thickness have been increased compared to their actual values. Gray boxes denote baseline outputs, while blue boxes indicate those from our proposed GoM . See icon legend in Table 2 .

Phase	Hyperparam Setting
	$\tau_{\text{OD-min-conf}}=\{0.4,0.5\ast,0.8\}\;\tau_{\text{overlap-IoU}}=0.9$
❶/❷/❸	$\tau_{\text{dir-margin}{\textsuperscript{$ \ddagger $}}}=\{10,20\ast,50\},\;\tau_{\text{z-diff}}=\{0.1\ast,0.15,0.20\},$ $\tau_{\text{near}{\textsuperscript{$ \ddagger $}}}=5,000$
	$\tau_{\text{touch-IoU}{\textsuperscript{$ \ddagger $}}}=0.1,\;\tau_{\text{touch-gap}{\textsuperscript{$ \ddagger $}}}=3,\;$ $\tau_{\text{v-close}{\textsuperscript{$ \ddagger $}}}=0.05,\;\tau_{\text{close}{\textsuperscript{$ \ddagger $}}}=\{0.12\ast,0.15\}$
/	$\tau_{\text{query-obj}}=\{0.5\ast,0.7,0.8\},\;k=\{1,2,3\ast,4,5,6\}$
	$\text{seed}=\{42,123,456\},$ $\text{temp}=\{0.1,0.3,0.5\},\;\text{top-p}=\{0.7,0.9,0.95\}$

Table 1: Hyperparameter sweep. Top: algorithm. Bottom: decoding (for best algorithm config).

\ast

= algorithm values, picked after preliminary runs with Qwen-2.5-VL on GQA.

	Method	GQA	VQA		RefCOCOg
			v1	v2
Gemma-3 4B		56.2 ±0.11	64.3 ±0.14	59.9 ±0.19	–
		53.8 ±0.34	63.7 ±1.15	60.2 ±1.37	–
		56.9 ±0.34	63.8 ±0.07	59.0 ±0.18	54.8 ±0.91
		58.8 ±0.16	65.2 ±0.38	62.8 ±0.36	56.3 ±0.91
		60.3 ±0.45	71.5 ±0.1	70.2 ±0.25	56.4 ±0.66

Table 2: Accuracy results (

\uparrow

). Comparison between GoM variants (Visual SG only) and baseline prompt strategies on 4 datasets and 3 MLMs. We report mean

\pm

standard deviation across decoding runs. Best results are highlighted.

Panel of Figure 3 — Figure 3: Effect of graph density. Performance of GoM in VQAv2 as a function of the number of edges in the visual scene graph. $0$ edges corresponds to SoM-like prompting.

Panel of Figure 4 — Figure 4: Accuracy impact deriving from augmenting the visual ( $I$ ) and textual ( $T$ ) prompt with scene graphs (SG apex). Gemma-3 results. Proposed GoM solutions have $I^{\text{SG}}$ .

Appendix figures & tables4 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 5 — Figure 5: GoM prompt template used in the Visual SG Only condition.

Panel of Figure 6 — Figure 6: GoM prompt template used in the Visual + Textual SG condition.

Panel of Figure 7 — Figure 7: Qualitative example illustrating the impact of image preprocessing on REF performance. The same question from RefCOCOg is posed to Qwen2.5-7B using 5 different hard visual prompts, highlighting how pixel transformations can influence the model’s responses. Gray boxes denote baseline outputs, while blue boxes indicate those from our proposed GoM . The original font size and line thickness values are preserved. Best viewed when zoomed in.

Panel of Figure 8 — Figure 8: Additional qualitative example illustrating the impact of image preprocessing on VQA performance. The same question from GQA is posed to Qwen2.5-7B using 5 different hard visual prompts, highlighting how pixel transformations can influence the model’s responses. Gray boxes denote baseline outputs, while blue boxes indicate those from our proposed GoM . The original font size and line thickness values are preserved. Best viewed when zoomed in.

Spatial Reasoning in Language Models

See all 50 papers

SpatialThinker: Reinforcing Scene Graph-Grounded Spatial Reasoning via Dense Rewards
Nov 10, 2025Hunar Batra, Haoqin Tu, Hardy Chen +3Multimodal Understanding Scene Graph Generation
University of Oxford · University of California, Santa Cruz
Scene Graph Thinking: Reinforcing Structured Visual Reasoning for Multimodal Large Language Models
Jul 7, 2026Zhiwei Yang, Yuanchen Wu, Nan Zhang +3Multimodal Large Language Models Multimodal CoT Reasoning
Tencent Youtu Lab, Shanghai, China · Fudan University, Shanghai, China
GraFT: A Training-Free Framework for Spatial Reasoning in Multimodal Large Language Models via 3D Scene Graphs
Sep 3, 2026Junqing Du, Fernando Ropero, Erkin Turkoz +23D Spatial Reasoning Multimodal Large Language Models
Riemann Lab, Huawei Technologies

Nov 10, 2025J/K move · Enter open · S save

SpatialThinker: Reinforcing Scene Graph-Grounded Spatial Reasoning via Dense Rewards

Hunar Batra, Haoqin Tu, Hardy Chen, Yuanze Lin+2

University of Oxford · University of California, Santa Cruz

Multimodal Understanding Scene Graph Generation Visual Spatial Reasoning Reinforcement Learning RL for VLMs Visual Question Answering+5

Open paper AskPDF arXiv

Multimodal large language models (MLLMs) have achieved remarkable progress in vision-language tasks, but continue to struggle with spatial reasoning. Existing spatial MLLMs rely on large-scale datasets, explicit 3D inputs, architecture-specific modifications, or sparse Reinforcement Learning (RL) methods that provide insufficient guidance for spatially-grounded reasoning. We introduce SpatialThinker. To our knowledge, it is the first MLLM unifying Scene Graph Generation (SGG) and visual reasoning in a single pass via online RL. The model simulates human-like spatial perception by constructing a mental scene graph of task-relevant objects and relations, and reasoning toward an answer via dense spatial rewards. Our contributions are threefold: (1) SGG-grounded reasoning: integrating SGG directly within the reasoning chain rather than as a disjoint preprocessing step; (2) STVQA-7K: a high-quality spatial VQA training dataset via a scalable synthesis pipeline; and (3) a dense spatial reward design that enforces structured grounding during RL and generalizes to improve broad visual perception. SpatialThinker-7B achieves 3.6

\times

larger gains over SFT and

1.7\times

better in- and out-of-distribution generalization than sparse RL. Trained on only 7K samples, SpatialThinker-7B matches GPT-5 and outperforms GPT-4o, while SpatialThinker-30B surpasses both GPT-5 and Claude 4 Sonnet on average across 14 spatial and real-world benchmarks, demonstrating that structured spatial grounding with reward-aligned reasoning enables robust spatial understanding with limited data.

Abstract

Spatial Reasoning in Language Models

Explore similar work

SpatialThinker: Reinforcing Scene Graph-Grounded Spatial Reasoning via Dense Rewards

Scene Graph Thinking: Reinforcing Structured Visual Reasoning for Multimodal Large Language Models

GraFT: A Training-Free Framework for Spatial Reasoning in Multimodal Large Language Models via 3D Scene Graphs