The 34th ACM International Conference on Multimedia (MM '26)

Rule-Compliant Visual Spatial Planning for Multimodal Large Language Models

RuleMaze studies whether multimodal large language models can perceive visual mazes, interpret natural-language constraints, and produce valid multi-step plans that obey explicit rules.

Yu Chen1 Ting Lei1 Yaoyi Li2 Jia Cai2 Zhecen Wu2 Yang Liu1

1 Wangxuan Institute of Computer Technology, Peking University ยท 2 Yinwang Intelligent Technology Co., Ltd

Paper Code Dataset Model
RuleMaze dataset construction overview Disentangled Multimodal Planning framework overview
Overview of the RuleMaze dataset and the Disentangled Multimodal Planning (DMP) framework. 1 / 2

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.

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 rule construction, we propose Language-Logic-Function Hybridization, which automatically generates natural-language rules, translates them into logical representations, and compiles them into executable validators.

We further introduce Disentangled Multimodal Planning (DMP), which separates perception, execution, and rule verification through interpretable reasoning primitives. Experiments show that DMP substantially improves rule compliance and planning success compared to end-to-end textual planning baselines, especially under complex and previously unseen rules.

Highlights

RuleMaze Benchmark

A controllable visual planning benchmark with diverse maze environments, natural-language rules, and executable trajectory validation.

Language-Logic-Function

A scalable rule construction pipeline that moves from rule ideation to logical formalization and synthesized validators.

DMP Framework

A tool-based planning framework that modularizes perception, action execution, and rule verification for interpretable reasoning.

RuleMaze Dataset

RuleMaze construction pipeline
RuleMaze construction pipeline: rule ideation, logical formalization, validator synthesis, maze generation, and constraint-based rule-maze matching.

RegularMaze

The start and goal locations are indicated by green and red cells. Rules refer to colored zones such as orange or pink, while other cells remain visually uniform. This setting emphasizes spatial reasoning under static goals and local rule constraints.

QuestMaze

The start is represented by a prince icon and the goal by a princess or treasure icon. Rules involve symbolic objects such as keys and may depend on history, collected items, or changing goal conditions.

RegularMaze and QuestMaze dataset examples
Dataset illustration under both RegularMaze and QuestMaze scenarios.

Disentangled Multimodal Planning

DMP treats rule-compliant spatial planning as an iterative tool-invocation process. Instead of asking a model to solve perception, execution, and rule checking in a single entangled forward pass, DMP trains a controller to decide when and how to invoke reusable tools.

Disentangled Multimodal Planning method
Overall framework of Disentangled Multimodal Planning.

Perception

LocateStart identifies the initial position, while InspectGrid extracts symbols from specific cells.

Execution

ExecuteMove applies an action and returns an updated visual state with the agent position marked.

Verification

VerifyRule checks trajectory compliance and VerifyEndpoint checks whether the target is reached.

Results

DMP improves both in-distribution performance and zero-shot generalization to unseen rules. The gains are especially pronounced on harder rule categories and on QuestMaze, where symbolic objects and history-dependent constraints make planning more complex.

90.0% RegularMaze unseen-rule EM
92.7% RegularMaze unseen-rule PR
88.0% QuestMaze unseen-rule EM
91.7% QuestMaze unseen-rule PR
Scenario Model Seen EM Seen PR Unseen EM Unseen PR
RegularMaze Qwen2.5-VL SFT 94.0 95.3 70.3 73.9
RegularMaze DMP-3B (Ours) 98.0 98.4 90.0 92.7
QuestMaze Qwen2.5-VL SFT 66.8 73.6 56.3 68.0
QuestMaze DMP-3B (Ours) 91.4 94.3 88.0 91.7

Qualitative Analysis

RegularMaze qualitative planning example
Visualization of a RegularMaze test example comparing visual planning variants.

Representative Failure and Success Modes

SFT Baseline

Produces plausible navigation actions, but may violate the rule after entering a constrained zone because rule checking is not explicit.

Gemini 2.5 Pro

Can identify spatial constraints in text, yet may waive a rule heuristically when a local move appears blocked.

DMP

Alternates between execution and rule verification, receiving immediate feedback and revising candidate plans when needed.

Acknowledgements

This work was supported by the grants from the National Natural Science Foundation of China 62372014 and Beijing Nova Program.

Citation

@misc{chen2026rulecompliantvisualspatialplanning,
  title         = {Rule-Compliant Visual Spatial Planning for Multimodal Large Language Models},
  author        = {Yu Chen and Ting Lei and Yaoyi Li and Jia Cai and Zhecen Wu and Yang Liu},
  year          = {2026},
  eprint        = {2608.20237},
  archivePrefix = {arXiv},
  primaryClass  = {cs.AI},
  url           = {https://arxiv.org/abs/2608.20237}
}