Rule-Compliant Visual Spatial Planning for Multimodal Large Language Models

Yu Chen; Ting Lei; Yaoyi Li; Jia Cai; Zhecen Wu; Yang Liu

cs.AIAug 20, 2026

Rule-Compliant Visual Spatial Planning for Multimodal Large Language Models

Authors: Yu Chen, Ting Lei, Yaoyi Li, Jia Cai, Zhecen Wu, Yang Liu

Organizations: Wangxuan Institute of Computer Technology, Peking University · Yinwang Intelligent Technology Co., Ltd

Abstract

Multimodal large language models (MLLMs) combine linguistic reasoning with visual perception, yet their ability to perform visual spatial planning under explicit or previously unseen rule constraints remains underexplored. This setting requires models to jointly understand spatial layouts, interpret natural-language rules, and plan valid actions accordingly. To address this gap, we introduce RuleMaze, a controllable benchmark in which MLLMs must navigate mazes while obeying natural-language rules of varying complexity. RuleMaze isolates rule-compliant spatial planning by requiring accurate perception, rule interpretation, and constrained action planning. To enable scalable and systematic rule construction, we propose Language-Logic-Function Hybridization, which automatically generates natural-language rules and translates them into logical representations and executable validators, eliminating manual rule engineering. To improve rule following and generalization, we introduce Disentangled Multimodal Planning (DMP), which separates perception, execution, and rule verification through interpretable reasoning primitives. By disentangling these components, DMP facilitates systematic generalization to more complex and previously unseen rules, while providing transparent intermediate planning traces. Experiments demonstrate that DMP substantially improves rule compliance and planning success compared to end-to-end textual planning baselines. Overall, RuleMaze establishes a principled benchmark for studying grounded and interpretable rule-based spatial planning in MLLMs. Code is available at https://github.com/oceanflowlab/RuleMaze.

Figures & tables

Panel of Figure 1 — Figure 1. Overview of the RuleMaze dataset and the proposed Disentangled Multimodal Planning (DMP) framework.

Figure 2. Overview of the RuleMaze construction pipeline. Free-form rule concepts are generated via Rule Ideation, translated into structured representations through Logical Formalization, and compiled into executable validators by Validator Synthesis. In parallel, diverse maze environments are procedurally generated. A constrained-based heuristic rule–maze matching strategy selects applicable mazes for each rule, yielding rule–maze pairs with unambiguous rule-compliant trajectories.

Figure 3. RuleMaze dataset illustration under both the RegularMaze and QuestMaze scenarios.

Category	Tool Name	Inputs	Function Description	Output
Perception	LocateStart	Image $\mathcal{I}$	Identifies and marks the initial agent position	Image $I_{0}$
	InspectGrid	Image $I_{t}$	Identifies semantic symbols at specific cell	Symbol $s_{t}$
Execution	ExecuteMove	Image $I_{t}$ , Action $a_{t}$	Updates agent position and visual state	Image $I_{t+1}$
Verification	VerifyRule	$a_{0:t}$ , $s_{0:t}$ , Rule $R$	Checks trajectory compliance with rule $R$	Boolean
	VerifyEndpoint	Image $I_{t}$	Checks if agent has reached the target	Boolean

Table 1. Summary of disentangled tools in the DMP framework.

Figure 4. Overall framework of our proposed Disentangled Multi-Modal Planning.

Proprietary Model
Model	Seen Rule		Unseen Rule
	Avg.		Easy		Medium		Hard		Avg.
	EM (%)	PR (%)	EM (%)	PR (%)	EM (%)	PR (%)	EM (%)	PR (%)	EM (%)	PR (%)
Gemini 2.5 Pro
- Direct	48.0	52.5	59.0	63.9	39.0	45.9	39.0	45.5	45.6	51.7
- CoT	47.0	52.2	64.0	67.3	46.0	51.0	44.0	49.3	51.3	55.8

Table 2. Model performance on RegularMaze. "Seen Rule" denotes the performance on rules encountered during training, while "Unseen Rule" covers zero-shot rule generalization across three difficulty levels. † denotes the post-trained model.

Proprietary Model
Model	Seen Rule		Unseen Rule
	Avg.		Easy		Medium		Hard		Avg.
	EM (%)	PR (%)	EM (%)	PR (%)	EM (%)	PR (%)	EM (%)	PR (%)	EM (%)	PR (%)
Gemini 2.5 Pro
- Direct	71.0	77.4	81.0	86.0	85.0	88.9	71.0	74.9	79.0	83.2
- CoT	74.0	81.5	86.0	88.5	80.0	83.8	70.0	76.8	78.6	83.0

Table 3. Model performance on QuestMaze. "Seen Rule" reflects the model’s ability on training rules, while "Unseen Rule" evaluates zero-shot generalization across three difficulty levels. † denotes the post-trained model.

Model	EM (%)	PR (%)
Direct SFT	65.3	71.4
w/ Coordinates	69.0	73.7
w/ ASCII	67.0	70.6

Table 4. Performance of text-based planning variants on RegularMaze under the "Unseen Rule" setting.

Figure 5. Visualization of a test example from RegularMaze comparing visual planning variants.

Appendix figures & tables14 assets

Supplementary material from the paper’s appendix.

Appendix

Method	EM (%)	PR (%)
Gemini-2.5-Pro	45.6	51.7
Gemini-2.5-Pro + DMP-P	64.0	67.6
GPT-5	53.5	61.3
GPT-5 + DMP-P	81.4	84.1
Qwen2.5-VL-3B	0.0	11.7
Qwen2.5-VL-3B + DMP-P	0.0	17.3

Appendix

Table 1. Performance of DMP-Prompting (DMP-P) on the unseen-rule split of RegularMaze. DMP-P equips each backbone with the same disentangled tools as DMP but does not involve post-training. We report the average Exact Match (EM) and Precision Rate (PR) across all unseen-rule difficulty levels.

\dagger

denotes a post-trained model.

Model	Seen Rule		Unseen Rule
	Avg.		Easy		Medium		Hard		Avg.
	EM (%)	PR (%)	EM (%)	PR (%)	EM (%)	PR (%)	EM (%)	PR (%)	EM (%)	PR (%)
w/o Execution	63.0	63.2	50.0	53.5	34.0	36.8	30.0	33.3	38.0	41.2
w/o Verification	91.7	92.5	94.0	94.6	78.0	79.2	70.0	73.4	80.6	82.4
w/o Perception + Verification	88.5	89.3	91.0	92.0	74.0	76.1	66.0	69.5	77.0	79.1
DMP (Ours)	98.0	98.4	95.0	96.7	88.0	91.9	87.0	89.6	90.0	92.7

Appendix

Model	Seen Rule		Unseen Rule
Model	Avg.		Easy		Medium		Hard		Avg.
	EM (%)	PR (%)	EM (%)	PR (%)	EM (%)	PR (%)	EM (%)	PR (%)	EM (%)	PR (%)
Direct SFT (25%)	35.0	45.6	35.0	48.7	29.0	38.2	18.0	31.1	27.3	39.3
Direct SFT (50%)	67.0	74.1	67.0	75.1	55.0	62.6	43.0	55.2	55.0	64.3
Direct SFT (100%)	95.0	95.3	72.0	76.6	65.0	69.9	58.9	67.7	65.3	71.4
DMP (25%)	79.0	84.4	71.0	81.1	65.0	74.9	62.0	71.5	66.0	75.8

Appendix

Table 3. Performance under different training data scales. We evaluate both Direct SFT and DMP using 25%, 50%, and 100% of the training data. "Seen Rule" denotes performance on rules encountered during training, while "Unseen Rule" evaluates zero-shot generalization across three difficulty levels.

Model	Seen Rule		Unseen Rule
Model	Avg.		Easy		Medium		Hard		Avg.
	EM (%)	PR (%)	EM (%)	PR (%)	EM (%)	PR (%)	EM (%)	PR (%)	EM (%)	PR (%)
Direct SFT	95.0	95.3	72.0	76.6	65.0	69.9	58.9	67.7	65.3	71.4
w/ Coordinates	97.0	97.6	77.0	82.6	68.0	70.9	62.0	67.6	69.0	73.7
w/ ASCII	95.0	95.0	73.0	78.3	68.5	70.7	59.5	62.8	67.0	70.6
DMP (Ours)	98.0	98.4	95.0	96.7	88.0	91.9	87.0	89.6	90.0	92.7

Appendix

Table 4. Performance comparison with text-based planning variants. "Seen Rule" denotes performance on rules encountered during training, while "Unseen Rule" covers zero-shot rule generalization across three difficulty levels.

Figure 1. Examples of model outputs under different textual planning variants.

Semantic type	Direction-dependent	History-dependent	Requirement	Prohibition
Ratio	$64.9\%$	$31.3\%$	$61.3\%$	$51.0\%$

Appendix

Table 5. Distribution of rules across different semantic types. The categories are not mutually exclusive, as a rule may exhibit multiple semantic properties.

Connective	if	must	and	or	not	cannot
Avg. count	0.42	0.55	0.16	0.06	0.17	0.16

Appendix

Table 6. Average number of logical connectives and constraint markers per rule.

Figure 2. Success rate by action length interval on the RegularMaze test set. Statistics are categorized by action length intervals ([3-4], [5-6], [7-8]) and further partitioned by difficulty levels (Easy, Medium, and Hard).

Figure 3. Example of the LLM prompt and structured output for Rule Ideation. The prompt defines logical predicates and difficulty constraints, while the output provides natural language rules paired with their symbolic CNF representations.

Scenario	Predicate	Semantics	Example
RegularMaze	Zone(t, "col")	Cell color at $t$	Zone(t, "blue")
	Move(t, "dir")	Action at $t$	Move(t-1, "up")
QuestMaze	Seen("item")	Item on path	Seen("key")
	Moved("dir")	Direction taken	NOT Moved("down")
	Count(s, op, v)	Count constr.	Count("food", $\geq$ , 3)
	TargetIs(tg)	Goal reached	TargetIs("treasure")

Appendix

Table 7. CNF predicate vocabulary.

Figure 4. Example of the prompt-to-code compilation process. The system translates formalized CNF-style logic into standalone Python validator functions, ensuring deterministic rule evaluation.

Figure 5. Implementation of the validator code with manual refinement. The red box highlights the manual refinement where the target_count > 0 condition was added.

Figure 6. Examples of correct reasoning on the RegularMaze test set via DMP.

Figure 7. Examples of correct reasoning on the QuestMaze test set using DMP.

Multimodal Large Language Models

Multimodal large language models combine language models with image, video, audio, and other inputs for grounded understanding and generation.

See all 1,091 papers

Mar 27, 2026

From Pixels to BFS: High Maze Accuracy Does Not Imply Visual Planning

How do multimodal models solve visual spatial tasks -- through genuine planning, or through brute-force search in token space? We introduce MazeBench, a benchmark of 110 procedurally generated maze images across nine controlled groups, and evaluate 16 model configurations from OpenAI, Anthropic, Google, and Alibaba. GPT-5.4 solves 91% and Gemini 3.1 Pro 79%, but these scores are misleading: models typically translate images into text grids and then enumerate paths step by step, consuming 1,710--22,818 tokens per solve for a task humans do quickly. Without added reasoning budgets, all configurations score only 2--12%; on 20

\times

20 ultra-hard mazes, they hit token limits and fail. Qualitative traces reveal a common two-stage strategy: image-to-grid translation followed by token-level search, effectively BFS in prose. A text-grid ablation shows Claude Sonnet 4.6 rising from 6% on images to 80% when given the correct grid, isolating weak visual extraction from downstream search. When explicitly instructed not to construct a grid or perform graph search, models still revert to the same enumeration strategy. MazeBench therefore shows that high accuracy on visual planning tasks does not imply human-like spatial understanding.

Alberto G. Rodriguez Salgado

Independent Researcher

VLM Reasoning Visual Spatial Reasoning Large Vision-Language Models Spatial Reasoning Benchmarks

Ask PDF

Mar 23, 2026

Mind over Space: Can Multimodal Large Language Models Mentally Navigate?

Despite the widespread adoption of MLLMs in embodied agents, their capabilities remain largely confined to reactive planning from immediate observations, consistently failing in spatial reasoning across extensive spatiotemporal scales. Cognitive science reveals that Biological Intelligence (BI) thrives on "mental navigation": the strategic construction of spatial representations from experience and the subsequent mental simulation of paths prior to action. To bridge the gap between AI and BI, we introduce Video2Mental, a pioneering benchmark for evaluating the mental navigation capabilities of MLLMs. The task requires constructing hierarchical cognitive maps from long egocentric videos and generating landmark-based path plans step by step, with planning accuracy verified through simulator-based physical interaction. Our benchmarking results reveal that mental navigation capability does not naturally emerge from standard pre-training. Frontier MLLMs struggle profoundly with zero-shot structured spatial representation, and their planning accuracy decays precipitously over extended horizons. To overcome this, we propose NavMind, a reasoning model that internalizes mental navigation using explicit, fine-grained cognitive maps as learnable intermediate representations. Through a difficulty-stratified progressive supervised fine-tuning paradigm, NavMind effectively bridges the gap between raw perception and structured planning. Experiments demonstrate that NavMind achieves superior mental navigation capabilities, significantly outperforming frontier commercial and spatial MLLMs.

Qihui Zhu, Shouwei Ruan, Xiao Yang +6

Institute of Artificial Intelligence, Beihang University · Dept. of Comp. Sci. and Tech., Institute for AI, Tsinghua-Bosch Joint ML Center, THBI Lab, BNRist Center, Tsinghua University · School of Automation Science and Electrical Engineering, Beihang University +2

Multimodal Large Language Models Visual Spatial Reasoning Spatial Reasoning Benchmarks

Ask PDF

Apr 19, 2026

SpatialImaginer: Towards Adaptive Visual Imagination for Spatial Reasoning

Spatial intelligence, which refers to the ability to reason about geometric and physical structure from visual observations, remains a core challenge for multimodal large language models. Despite promising performance, recent multimodal large language models (MLLMs) often exhibit fragile reasoning traces in spatial intelligence tasks that involve consistent spatial state recognition. We argue that these failures stem from a mismatch between the spatial recognition mechanism and the text-only reasoning behavior of these MLLMs. Effective spatial reasoning requires low-level geometric structure to be faithfully preserved and updated throughout the reasoning process, whereas textual representations tend to abstract away precisely these critical details. To address this issue, we propose SpatialImaginer, a unified multimodal generation framework that integrates textual reasoning with visual imagination. Our framework adopts a divide-and-conquer strategy, using text chain-of-thought for high-level semantic planning and the visual imagination for geometry-sensitive state transformation and consistency preservation. To support this capability, we further introduce a difficulty-aware data engine with closed-loop verification to train the model to invoke visual imagination selectively when stable spatial state tracking is required. Extensive experiments on diverse spatial intelligence benchmarks show that SpatialImaginer achieves state-of-the-art performance and substantially improves robustness on complex multi-step spatial reasoning tasks.

Yian Li, Yang Jiao, Bin Zhu +4

College of Computer Science and Artificial Intelligence, Fudan University · School of Computing and Information Systems, Singapore Management University · School of Computer Science and Technology, East China Normal University +2

Multimodal CoT Reasoning Unified Multimodal Models Multimodal Understanding Visual Spatial Reasoning Visually Grounded Reasoning Spatial Reasoning+1

Ask PDF

Abstract

Multimodal Large Language Models

Explore similar work

From Pixels to BFS: High Maze Accuracy Does Not Imply Visual Planning

Mind over Space: Can Multimodal Large Language Models Mentally Navigate?

SpatialImaginer: Towards Adaptive Visual Imagination for Spatial Reasoning