Rule-Compliant Visual Spatial Planning for Multimodal Large Language Models

arXiv:2608.20237v1 [cs.AI] 20 Aug 2026

Rule-Compliant Visual Spatial Planning for Multimodal Large Language Models Yu Chen

Ting Lei

Yaoyi Li

Wangxuan Institute of Computer Technology, Peking University Beijing, China yu_chen@stu.pku.edu.cn

Wangxuan Institute of Computer Technology, Peking University Beijing, China ting_lei@pku.edu.cn

Yinwang Intelligent Technology Co., Ltd Shenzhen, China liyaoyi@yinwang.com

Jia Cai

Zhecen Wu

Yang Liu∗

Yinwang Intelligent Technology Co., Ltd Shenzhen, China caijianwpu@gmail.com

Yinwang Intelligent Technology Co., Ltd Shenzhen, China wuzhecen@yinwang.com

Wangxuan Institute of Computer Technology, Peking University Beijing, China yangliu@pku.edu.cn

Abstract

Keywords

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.

Multimodal Large Language Models, Rule compliance, Visual Spatial Planning

CCS Concepts • Computing methodologies → Planning and scheduling. ∗ Corresponding author.

This work is licensed under a Creative Commons Attribution 4.0 International License. MM ’26, Rio de Janeiro, Brazil. © 2026 Copyright held by the owner/author(s). ACM ISBN 979-8-4007-2213-4/2026/11 https://doi.org/10.1145/3767308.3836415

ACM Reference Format: Yu Chen, Ting Lei, Yaoyi Li, Jia Cai, Zhecen Wu, and Yang Liu. 2026. RuleCompliant Visual Spatial Planning for Multimodal Large Language Models. In Proceedings of the 34th ACM International Conference on Multimedia (MM ’26), November 10–14, 2026, Rio de Janeiro, Brazil. ACM, New York, NY, USA, 9 pages. https://doi.org/10.1145/3767308.3836415

1

Introduction

Recently, multimodal large language models (MLLMs) have rapidly advanced beyond traditional language-only models by incorporating native visual inputs [1, 3, 23, 24, 31]. Through large-scale multimodal pretraining, these models have achieved impressive performance on tasks such as image captioning [15, 21, 39], visual question answering [18, 26, 41], and general visual reasoning [10, 35, 42]. Recent works have begun to explore spatial planning and multistep action reasoning in visual environments, which constitutes a necessary step toward embodied intelligence [19, 20, 30, 34]. However, many of these settings assume unconstrained planning or optimize for a single objective without requiring explicit compliance with externally specified rules. A particularly important yet understudied capability is rule-compliant spatial planning: the ability to reason over visual spatial layouts, interpret explicit rules expressed in natural language, and generate multi-step action plans that satisfy those rules. This capability is central to many real-world settings, such as autonomous driving [22, 32, 40] and embodied intelligence [4, 6, 37, 38], where agents must operate under changing, context-specific constraints rather than fixed global objectives. For example, an autonomous agent deployed in a new country may encounter traffic regulations that differ from those seen during training, requiring it to correctly interpret and obey previously unseen rules rather than relying on memorized behaviors. Despite its importance, current benchmarks and analyses offer little systematic evaluation of how well MLLMs can perform such constrained spatial planning. Studying rule-compliant spatial planning in realistic environments presents substantial challenges. First, from a data perspective, real-world scenes rarely provide ground-truth action sequences

MM ’26, November 10–14, 2026, Rio de Janeiro, Brazil.

corresponding to dynamically varying rule sets. Collecting labeled demonstrations for each new combination of environment and rule is prohibitively expensive, making it difficult to scale evaluation or training across diverse rule constraints. Second, from a methodological perspective, rule-compliant spatial planning requires the tight integration of multiple competencies: accurate visual perception, long-horizon spatial planning, precise rule interpretation, and strict adherence to rules during execution. End-to-end formulations that entangle these capabilities within a single model often struggle to coordinate them reliably, leading to brittle behavior when confronted with multi-step constraints or previously unseen rules. These limitations motivate the need for (i) a controllable evaluation environment that supports systematic variation of rule complexity, and (ii) reasoning frameworks that explicitly structure how MLLMs perceive, execute, and verify actions under constraints. Addressing these needs is essential for understanding the limits of current MLLMs and for developing models that can generalize to complex, rule-governed spatial planning tasks.

Yu Chen et al.

representations. We further perform Validator Synthesis to automatically produce executable functions that verify whether a candidate action trajectory satisfies a given rule, enabling precise and automated evaluation without manual rule engineering. In parallel, we procedurally generate a large collection of maze images with diverse layouts and visual configurations using a Python-based library. Each maze is designed to admit multiple feasible routes from the start to the goal. To ensure rules are evaluated only in applicable environments, we introduce a heuristic rule–maze matching strategy: for each rule, we select mazes in which the rule admits a non-empty set of valid trajectories while inducing a unique rulecompliant solution among multiple distractor routes. To support controlled analysis of reasoning difficulty, rules are categorized into easy, medium, and hard levels based on the syntactic complexity of their logical formalizations, measured by the number of logical connectives. Overall, RuleMaze offers (i) diverse procedurally generated mazes with multiple competing routes, (ii) systematically constructed rule sets spanning multiple difficulty levels, and (iii) unambiguous action-level trajectories under explicit constraints, making it a principled benchmark for studying rule-based spatial planning in MLLMs. Beyond benchmarking, we propose Disentangled Multimodal Planning (DMP), a general framework for improving rule-compliant spatial planning in MLLMs, as illustrated in Fig. 1b. Unlike end-toend training, which entangles perception, execution, and rule reasoning into a single data-driven process and requires substantial supervision to relearn these capabilities whenever rules change, DMP explicitly modularizes rule-constrained problem solving and trains the model to coordinate reusable capabilities. Specifically, DMP decomposes the task into three interpretable components—visual perception, action execution, and rule verification—each implemented as a set of callable tools. Given a maze image and a natural-language (a) RuleMaze dataset construction. rule, the model alternates between internal reasoning and external tool invocation, deciding when to perceive visual evidence, propose candidate actions, and verify rule compliance. Importantly, having access to all tools does not guarantee solving the problem: the model still needs to learn in a data-driven way when and how to invoke each tool to successfully complete rule-constrained planning. DMP therefore focuses training on the core controller’s ability to select, sequence, and integrate tool outputs. Crucially, rule verification is externalized through dedicated validator tools automatically synthesized from logical rule representations. These validators are (b) Disentangled Multimodal Planning (DMP) framework. fully replaceable, allowing new or previously unseen rules to be incorporated without retraining the controller. Figure 1: Overview of the RuleMaze dataset and the proposed In summary, this work makes the following contributions. (1) Disentangled Multimodal Planning (DMP) framework. We introduce RuleMaze, a controllable benchmark for evaluating spatial planning under explicit natural-language rules, feaTo address this gap, we introduce RuleMaze, a controllable benchturing diverse maze environments and rule–maze applicability mark for evaluating visual spatial planning under explicit naturalgrounded by executable verification tools. (2) We propose a Lanlanguage rules. As shown in Fig. 1a, RuleMaze pairs diverse mazeguage–Logic–Function Hybridization pipeline that enables scalable based visual environments with rule specifications that constrain construction of rule sets with controlled complexity, transforming which multi-step action plans are considered valid. To construct natural-language rules into logical representations and executable scalable rule spaces with controlled complexity, we propose a Language– validators without manual rule engineering. (3) We present DisenLogic–Function Hybridization pipeline that transforms free-form tangled Multimodal Planning (DMP), a framework that enhances rule concepts into executable constraints. Specifically, LLMs are rule-following behavior in MLLMs by equipping them with explicit used for Rule Ideation to generate natural-language rules, which perception, execution, and verification tools, enabling multi-step, are then translated via Logical Formalization into structured logical interpretable reasoning under constraints. (4) Through extensive

Rule-Compliant Visual Spatial Planning for Multimodal Large Language Models

MM ’26, November 10–14, 2026, Rio de Janeiro, Brazil.

experiments, we demonstrate that DMP substantially improves rule compliance and planning performance compared to end-to-end textual planning, especially under more complex and previously unseen rules.

action space. Moreover, existing methods do not address sequential planning or visually grounded decision-making, whereas our approach enables models to generate action sequences that are both executable and compliant with explicit rules.

2 Related work 2.1 Spatial Planning

3

Planning has long been central in AI, traditionally relying on formal representations and algorithms [2, 13, 29], typically in predefined and constrained settings. With recent advances in large language models (LLMs), it is now compelling to explore whether LLMs—viewed as general-purpose intelligent agents—can perform planning across diverse environments [16, 17, 25, 28]. For instance, AlphaMaze [8] converts maze navigation into a tokenized textual task, bridging language models with spatial planning in a purely symbolic setting. However, such approaches are limited to abstract, text-only decision-making, without observing visual state changes. Building on these capabilities, multimodal language models (MLLMs) extend planning into visually grounded spatial reasoning, where actions dynamically alter the environment. Benchmarks and methods include VisualCoT [9], which studies chain-ofthought designs for generalizable spatial planning; Ariadne [27], which applies reinforcement learning with verified rewards and a difficulty-aware curriculum; MVoT [20], which integrates textual reasoning with visually grounded mental imagery to enhance interpretability and robustness; and VPRL [34], which conducts planning entirely through sequences of images, enabling models to "think" directly in the visual domain. Unlike prior work that focuses on abstract planning or visual reasoning alone, our approach emphasizes rule-compliant spatial planning: natural-language rules explicitly constrain the action space, enabling a controllable and verifiable framework for evaluating and improving rule-based spatial planning in MLLMs.

2.2

Rule and Knowledge Injection

Rule and knowledge injection techniques enhance model reasoning by incorporating external constraints or factual information, either dynamically at inference time or statically through parameter adaptation. Dynamic injection incorporates constraints at inference time to guide model behavior. For example, in task-oriented reasoning, RAP [14] retrieves personalized knowledge rules to shape response generation. PokeMQA [11] handles knowledge editing in multi-hop QA by decoupling reasoning chains from conflict detection, ensuring updated knowledge is propagated consistently. DeepEdit [33] frames rule-based knowledge editing as constrained decoding, iteratively validating reasoning steps against injected rules. Static injection embeds constraints directly into model parameters. VisEdit [5] edits intermediate visual representations to enforce updated visual knowledge affecting downstream predictions. RECT [12] addresses the side effects of knowledge editing on general capabilities and proposes regularization to constrain weight updates, preventing overfitting to edited knowledge. While existing methods have demonstrated the effectiveness of rule and knowledge injection for textual reasoning, they primarily focus on influencing the language output space. In contrast, spatial planning requires rules that directly constrain the decisions in the

RuleMaze Dataset Construction

Investigating rule-compliant spatial planning in realistic settings is fundamentally challenged by the scarcity of annotated data, as real-world environments rarely offer ground-truth trajectories corresponding to dynamic rule sets. To address this, we present RuleMaze, a procedurally generated dataset of rule–maze pairs with executable validators. Our pipeline uses a Language–Logic–Function framework to generate rules with controlled complexity. In parallel, we procedurally synthesize diverse maze layouts. Through rule–maze matching, we pair each rule exclusively with mazes where it yields a non-empty set of compliant trajectories with a unique rule-consistent solution, while challenging distractor trajectories still exist. RuleMaze thus enables controlled and scalable evaluation for rule-constrained spatial planning research.

3.1

Language–Logic–Function Hybridization

The Language–Logic–Function Hybridization pipeline bridges expressive natural-language rules and precise, machine-checkable constraints, as illustrated in the upper part of Fig. 2. It comprises three stages: Rule Ideation, Logical Formalization, and Validator Synthesis. Rule Ideation. In the first stage, we use large language models (LLMs) to generate diverse and linguistically rich natural-language rules that constrain planning behavior. These rules go beyond simple goal specifications and capture conditional and state-dependent constraints—for example, “Moving into pink zones is strictly prohibited” or “If you are standing in an orange zone, your next move must be up.” This stage prioritizes compositional expressiveness, producing rules that demand non-trivial interpretation and multi-step reasoning. Logical Formalization. Each natural-language rule is then translated into a structured logical representation that formally encodes its semantics. For instance, the rule “If you are standing in an orange zone, your next move must be up” is formalized as Zone(𝑡, orange) → Move(𝑡, up), while “Moving into pink zones is strictly prohibited” is expressed as ¬Zone(𝑡, pink). These logical forms provide a compact and structured intermediate representation that supports both semantic analysis and automated execution. Validator Synthesis. Finally, we automatically synthesize an executable validator from each logical representation using LLMs. Specifically, the LLM generates a Python function that takes a candidate trajectory as input and determines whether it complies with the corresponding rule. By decomposing complex rules into simpler logical components, validator synthesis becomes more reliable and scalable. Empirically, the generated validators achieve 93.3% correctness before manual verification. To further ensure dataset quality, all validators are manually inspected and verified before deployment.

MM ’26, November 10–14, 2026, Rio de Janeiro, Brazil.

Yu Chen et al.

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.

3.2

Constraint-Based Heuristic Matching

To support scalable dataset construction, we first generate a large, rule-agnostic maze pool using a procedural generator. These mazes exhibit diversity in spatial layout, forming a rich environmental basis without prior rule constraints. Given this pool, we introduce a constraint-based heuristic matching strategy to associate each rule with mazes where it is meaningfully evaluable, as illustrated in the lower-middle part of Fig. 2. This process ensures that each rule–maze pair admits solvable yet non-trivial planning tasks. For a given rule, candidate mazes are those containing the symbolic elements referenced by the rule (e.g., specific colored zones). Within each candidate maze, we enumerate all feasible start-to-goal trajectories, denoted 𝑆 total , without considering rule constraints. Applying the rule’s validator (from Section 3.1) yields the subset of compliant trajectories 𝑆 valid ⊆ 𝑆 total . A maze is retained for a rule if it satisfies the following two constraints: (1) Restrictiveness: |𝑆 valid | < |𝑆 total |, ensuring the rule meaningfully restricts behavior. (2) Existence: |𝑆 valid | ≥ 1, guaranteeing at least one rule-compliant solution exists. Rule–maze pairs satisfying both constraints are accepted; otherwise, the maze is discarded for that rule. This matching strategy produces rule–maze pairs with clear behavioral constraints, enabling precise evaluation of rule-compliant spatial planning in multimodal agents.

Figure 3: RuleMaze dataset illustration under both the RegularMaze and QuestMaze scenarios. RegularMaze. In the RegularMaze scenario, the start and goal locations are indicated by a green and a red cell, respectively. Rules reference an additional colored zone (e.g., orange or pink), while all remaining cells are visually uniform white. This setting emphasizes spatial reasoning under static goals and local constraints, requiring models to interpret color-based rules while planning globally optimal paths.

3.3 RuleMaze Dataset QuestMaze. QuestMaze introduces a more semantically rich and Through the Language–Logic–Function Hybridization and the Constraint- challenging environment. The start location is represented by a based Heuristic Matching procedure described above, we construct prince icon, while the goal is a princess or treasure icon. Rules RuleMaze, a large-scale dataset of rule–maze pairs for evaluating in this scenario involve symbolic item icons (e.g., keys) that may rule-compliant spatial planning in MLLMs. The dataset comprises modify planning constraints or affect the goal condition. All other two complementary scenarios: RegularMaze and QuestMaze. cells are rendered with a grass-textured background. Compared to

Rule-Compliant Visual Spatial Planning for Multimodal Large Language Models

RegularMaze, QuestMaze requires reasoning over historical state information—such as whether and how many times an item has been collected—as well as handling dynamically changing target conditions specified by different rules. Together, these factors induce state- and scene-dependent action constraints and substantially increase planning complexity. Example mazes from both scenarios are shown in Fig. 3. For each scenario, rules are categorized into easy, medium, and hard levels based on the syntactic complexity of their logical formalizations, measured by the number of logical connectives. Overall, Regular Maze isolates core rule-conditioned spatial planning, while QuestMaze further challenges models with memory-dependent rules and non-stationary goals. Together, these scenarios enable fine-grained evaluation of MLLMs’ ability to perform interpretable, multi-step, and rule-compliant spatial planning across varying levels of difficulty.

4

Disentangled Multimodal Planning

Rule-compliant visual spatial planning requires the coordination of multiple heterogeneous capabilities, including visual perception, action execution, rule interpretation, and long-horizon reasoning. End-to-end formulations entangle these components into a single data-driven process, forcing the model to relearn largely stable capabilities whenever rules change, resulting in data inefficiency, brittle behavior, and limited diagnostic insight when failures occur. In contrast, many core functionalities—such as perceiving maze layouts, executing primitive actions, and verifying rule compliance—are reusable across tasks and rules. The central challenge instead lies in learning when and how to invoke these capabilities under evolving constraints. Motivated by this observation, we introduce Disentangled Multimodal Planning (DMP), a framework that modularizes rule-constrained planning into interpretable and replaceable tools, and trains a controller to reason over intermediate states and selectively orchestrate tool usage. By externalizing stable components and focusing learning on coordination, DMP enables data-efficient training and systematic generalization to novel and previously unseen rules.

4.1

Task Formulation

We study rule-constrained visual planning in grid-based maze environments. Each task instance consists of three components: a maze image I, a goal instruction G, and a natural-language rule specification R. The maze image I depicts a 2D grid environment with a designated start location, a target location, and rule-relevant cells or semantic objects. The goal instruction G specifies the goal of the task, e.g., “Navigate from Green to Red”. The rule specification R defines additional constraints on valid actions, such as “In an orange cell, the next move must be up”. The model is required to produce an action sequence a = (𝑎 1, 𝑎 2, . . . , 𝑎𝑇 ), 𝑎𝑡 ∈ A, where A = {up, down, left, right} denotes the action space and 𝑇 denotes the number of executed movement actions. Executing a from the start position must (i) reach the target location specified in I and (ii) satisfy the rule constraints defined by R at every step.

MM ’26, November 10–14, 2026, Rio de Janeiro, Brazil.

4.2

Disentangled Tool-Based Planning

We equip MLLMs with a set of disentangled and interpretable tools, organized into three categories: Perception, Execution, and Verification, as illustrated in Tab. 1. Formally, we define a tool set T = Tperc ∪ Texec ∪ Tver, where each tool 𝜏 ∈ T is a callable function with structured inputs and outputs. Perception tools ground the model’s reasoning in the maze image, execution tools deterministically update the visual state by applying movement actions, and verification tools assess rule compliance over the resulting trajectories, enabling step-wise, interpretable planning under explicit constraints. Perception Tools. Perception tools extract symbolic information from the maze image. Given an image 𝐼𝑡 at step 𝑡, these tools produce structured observations: 𝑜𝑡 = 𝜏perc (𝐼𝑡 ), where 𝑜𝑡 may include the start location, and whether the current cell corresponds to a special symbol (e.g., a colored zone or item). Execution Tools. Execution tools implement environment transitions. Given an action 𝑎𝑡 ∈ A and the current image 𝐼𝑡 , the execution tool computes 𝐼𝑡 +1 = 𝜏exec (𝐼𝑡 , 𝑎𝑡 ), which updates the agent’s position and returns a new maze image with the current location explicitly marked. This visual state update allows the model to reason over spatial transitions using explicit visual feedback. Verification Tools. Verification tools assess task completion and rule compliance. Given a partial trajectory 𝑎 0:𝑡 and the corresponding states 𝑠 0:𝑡 , verification tools return binary signals: 𝑟𝑢𝑙𝑒 (𝑎 , 𝑠 , 𝑅) and 𝑏 𝑔𝑜𝑎𝑙 = 𝜏 𝑔𝑜𝑎𝑙 (𝐼 ), indicating whether 𝑏𝑡𝑟𝑢𝑙𝑒 = 𝜏ver 0:𝑡 0:𝑡 𝑡 ver 𝑡 the trajectory satisfies the rule constraints or whether the target has been reached. Each rule 𝑅 is associated with a dedicated validator 𝑟𝑢𝑙𝑒 , synthesized offline from its logical formalization by an 𝜏𝑅 ∈ Tver external LLM [31] before controller training and inference. These validators are replaceable and compositional, enabling the framework to support new rules without retraining the core controller, as illustrated in Fig. 4.

4.3

Multi-Step Tool Invocation

Disentangled Multi-Modal Planning proceeds as an iterative decision process over reasoning steps and tool invocations. At each step 𝑡, the model maintains an internal reasoning state 𝑟𝑡 , initialized as 𝑟 0 . The input at step 𝑡 consists of the goal instruction 𝐺, the rule specification 𝑅, the updated maze image 𝐼𝑡 , and the accumulated reasoning trace H𝑡 . The model generates an executable program 𝑐𝑡 that specifies which tool to invoke and how to parameterize it: (𝑟𝑡 , 𝑐𝑡 ) = 𝑓𝜃 (𝐺, 𝑅, 𝐼𝑡 , H𝑡 ) Importantly, the tools themselves are not synthesized during inference; they are pre-defined by an external LLM and made available to the controller during the spatial planning process. Executing 𝑐𝑡 invokes a tool 𝜏𝑡 ∈ T and returns an observation 𝑜𝑡 , which is incorporated into H𝑡 +1 for the next reasoning step. For example, as illustrated in the lower part of Fig. 4, when invoking a rule verification tool 𝜏ver , the executable code 𝑐𝑡 specifies a call that takes the current partial action sequence a0:𝑡 as input. The tool evaluates whether a0:𝑡 satisfies the rule constraints defined by 𝑅 and returns a boolean signal 𝑜𝑡 ∈ {true, false}. This feedback allows the model to explicitly verify rule compliance and adjust subsequent action decisions accordingly.

MM ’26, November 10–14, 2026, Rio de Janeiro, Brazil.

Yu Chen et al.

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

Tool Name

Inputs

Function Description

Output

Perception

LocateStart InspectGrid

Image I Image 𝐼𝑡

Identifies and marks the initial agent position Identifies semantic symbols at specific cell

Image 𝐼 0 Symbol 𝑠𝑡

Execution

ExecuteMove

Image 𝐼𝑡 , Action 𝑎𝑡

Updates agent position and visual state

Image 𝐼𝑡 +1

Verification

VerifyRule VerifyEndpoint

𝑎 0:𝑡 , 𝑠 0:𝑡 , Rule 𝑅 Image 𝐼𝑡

Checks trajectory compliance with rule 𝑅 Checks if agent has reached the target

Boolean Boolean

Figure 4: Overall framework of our proposed Disentangled Multi-Modal Planning. This process continues until a termination condition is met, producing an action sequence 𝑎 = (𝑎 1, 𝑎 2, . . . , 𝑎𝑇 ), such that executing 𝑎 from the start state reaches the target and satisfies all rule constraints. By explicitly modeling planning as a sequence of reasoning and tool-invocation steps, the framework teaches the model how to solve rule-constrained spatial planning problems, rather than memorizing rule-specific behaviors.

and 400 test samples. Specifically, 100 test instances are associated with rules observed during training (seen rules), while the remaining 300 instances correspond to previously unseen rules. To further analyze performance under varying reasoning complexity, the unseen rules are evenly divided into three difficulty levels—easy, medium, and hard—with 100 instances in each category. We finetune Qwen2.5-VL (3B) [3] for 15 epochs with a batch size of 32.

5 Experiment 5.1 Experimental Setups

Evaluation Metrics. We adopt two complementary evaluation metrics [34, 36] for the selected task: Exact Match (EM), and Precision Rate (PR). Formally, for each test sample 𝑖 with ground-truth trajectory length 𝑛𝑖 , we define:

Training Objective. For each training example containing 𝑁 controller interaction rounds (steps of reasoning and tool invocation), we train our controller using the standard cross-entropy loss. Specifically, given the target output sequence y = {𝑦1, 𝑦2, . . . , 𝑦𝐿 } which concatenates the reasoning traces 𝑟𝑡 and executable programs 𝑐𝑡 across all steps, the training objective is to minimize:

EM𝑖 =

𝑛𝑖 Ö

I(𝑣ˆ𝑖 𝑗 = 𝑣𝑖 𝑗 ),

(2)

𝑗=1

PR𝑖 =

" 𝑗 # 𝑛𝑖 Ö 1 ∑︁ I(𝑣ˆ𝑖𝑘 = 𝑣𝑖𝑘 ) , 𝑛𝑖 𝑗=1

(3)

𝑘=1

𝐿 ∑︁

where 𝜃 denotes the model parameters. Training uses pure teacherforced supervised fine-tuning over the complete reasoning and tool-call traces.

where 𝑣ˆ𝑖 𝑗 and 𝑣𝑖 𝑗 are the predicted and ground-truth validity labels at step 𝑗. EM measures whether the complete trajectory exactly matches the shortest valid path; PR evaluates the proportion of consecutively correct steps. All rules are presented to the model in natural language at test time. An unseen rule is one whose logical formalization is absent from the training set.

Training Setting. We evaluate our framework on two spatial reasoning environments: (1) RegularMaze, which involves conventional pathfinding under basic geometric constraints, and (2) QuestMaze, which extends the task by incorporating semantic objects (e.g., keys, hearts). Each environment contains 3,600 training

Baselines. To facilitate comparison for language-based planning, we adopt Qwen 2.5-VL-Instruct [3], on both inference-only (Direct and CoT) and post-training settings. We further evaluate multimodal reasoning performance of proprietary models with Gemini 2.5 Pro [7] and Gemini 2.5 Flash with thinking mode.

L (𝜃 ) = −

log 𝑃𝜃 (𝑦𝑖 | 𝑦 <𝑖 , H𝑖 , 𝐺, 𝑅, 𝐼 )

(1)

𝑖=1

Rule-Compliant Visual Spatial Planning for Multimodal Large Language Models

MM ’26, November 10–14, 2026, Rio de Janeiro, Brazil.

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.

Model Proprietary Model Gemini 2.5 Pro - Direct - CoT Gemini 2.5 Flash (think) Open-Source Model Qwen 2.5-VL-Instruct-3B - Direct - CoT - SFT† DMP-3B† (Ours)

5.2

Seen Rule Avg. EM (%) PR (%)

Easy EM (%) PR (%)

Unseen Rule Medium Hard EM (%) PR (%) EM (%) PR (%)

Avg. EM (%) PR (%)

48.0 47.0 37.0

52.5 52.2 41.3

59.0 64.0 46.0

63.9 67.3 51.3

39.0 46.0 46.0

45.9 51.0 49.6

39.0 44.0 30.0

45.5 49.3 35.5

45.6 51.3 40.6

51.7 55.8 45.4

0.0 0.0 94.0 98.0

6.6 3.6 95.3 98.4

0.0 1.0 78.0 95.0

10.7 9.9 82.1 96.7

0.0 0.0 68.0 88.0

10.7 5.9 72.2 91.9

0.0 0.0 65.0 87.0

13.9 4.1 67.6 89.6

0.0 0.3 70.3 90.0

11.7 6.6 73.9 92.7

Main Results

Results on RegularMaze. Tab. 2 presents the performance comparison on the RegularMaze benchmark, evaluating both in-distribution (seen rules) and out-of-distribution (unseen rules) generalization. We observe that: (1) Overall Performance: DMP-3B achieves the best results across all metrics. It reaches 98.0% EM and 98.4% PR on seen rules, and 90.0% EM and 92.7% PR on unseen rules, substantially outperforming all baselines. Compared to Qwen2.5-VL with supervised fine-tuning, DMP improves unseen-rule EM from 70.3% to 90.0%, demonstrating a significant gain in zero-shot rule generalization. (2) Seen Rule Performance: On seen rules, SFT already achieves strong performance (94.0% EM), while DMP further improves it to 98.0%. This suggests that disentangled planning not only generalizes better but also reduces error accumulation even in in-distribution settings. (3) Unseen Rule Generalization: The advantage of DMP becomes more evident on unseen rules. While SFT obtains 70.3% EM on average, DMP achieves 90.0%, indicating substantially stronger generalization to novel constraints. In contrast, prompting-based approaches (Direct and CoT), even with proprietary models, struggle to handle rule-compliant planning, highlighting the intrinsic difficulty of the task. (4) Performance Across Difficulty Levels: Across different difficulty levels, all methods degrade as rule complexity increases. However, DMP maintains consistently strong performance, achieving 95.0%, 88.0%, and 87.0% EM on easy, medium, and hard rules, respectively. The performance gap between DMP and SFT further widens on harder rules, suggesting that disentangled planning is particularly beneficial for handling complex compositional constraints. (5) Effect of Text-Based Representations: We further compare with textual planning variants in Tab. 4. Direct SFT achieves 65.3% EM under unseen rules, and incorporating explicit representations such as coordinates (69.0%) or ASCII grids (67.0%) provides only marginal improvements. These results indicate that improving textual representations alone is insufficient for reliable spatial reasoning. In contrast, DMP leverages visual grounding together with executable tools, leading to substantially better performance. Overall, the results demonstrate that DMP improves both rule compliance and generalization, especially in challenging unseen and high-complexity settings.

Results on QuestMaze. Tab. 3 presents the results on QuestMaze, which introduces semantic objects and requires joint spatial and object-aware reasoning. We observe that: (1) Overall Performance: DMP-3B achieves the best performance among all methods, reaching 91.4% EM on seen rules and 88.0% EM on unseen rules. Compared to SFT, DMP improves unseen-rule EM from 56.3% to 88.0% (+31.7%), showing strong generalization to novel rules. (2) Comparison with Proprietary Models: Unlike in RegularMaze, Gemini 2.5 Pro achieves relatively strong performance on QuestMaze (up to 79.0% EM with direct prompting). This suggests that its strong language and reasoning capabilities are better suited to the cellbased layouts without complex wall structures. However, it still falls short of DMP, especially under harder settings. (3) Unseen and Hard Rules: As task complexity increases, the gap between DMP and SFT becomes more pronounced. On hard rules, SFT drops to 40.0% EM, while DMP maintains 84.0%, indicating its advantage in handling compositional constraints involving both spatial transitions and object interactions. Overall, DMP demonstrates strong robustness and generalization in more complex environments that require both spatial and semantic reasoning.

5.3

Qualitative Results

Fig. 5 illustrates a representative example from RegularMaze, highlighting the differences between end-to-end textual planning and our disentangled framework under rule constraints. We observe distinct failure patterns in baseline methods. Qwen2.5-VL with SFT produces a seemingly reasonable action sequence, but violates the rule by executing invalid movements after entering the constrained zone. This suggests that although the model can learn general navigation behavior, it lacks an explicit mechanism to enforce rule constraints during multi-step planning, leading to unnoticed violations. Gemini 2.5 Pro exhibits a different failure mode. It generates detailed step-by-step reasoning and correctly identifies the rule and spatial constraints. However, when encountering a situation where both allowed actions (“left” and “right”) are blocked, it heuristically concludes that the rule can be waived and proceeds with an alternative move (“down”). In contrast, DMP successfully generates a valid trajectory that satisfies both the goal and the rule. As shown in the

MM ’26, November 10–14, 2026, Rio de Janeiro, Brazil.

Yu Chen et al.

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 Proprietary Model Gemini 2.5 Pro - Direct - CoT Gemini 2.5 Flash (think) Open-Source Model Qwen 2.5-VL-Instruct-3B - Direct - CoT - SFT† DMP-3B†

Seen Rule Avg. EM (%) PR (%)

Easy EM (%) PR (%)

Unseen Rule Medium Hard EM (%) PR (%) EM (%) PR (%)

Avg. EM (%) PR (%)

71.0 74.0 56.0

77.4 81.5 63.1

81.0 86.0 79.0

86.0 88.5 84.5

85.0 80.0 48.0

88.9 83.8 57.4

71.0 70.0 40.0

74.9 76.8 50.2

79.0 78.6 55.6

83.2 83.0 64.0

0.0 0.0 66.8 91.4

5.8 2.5 73.6 94.3

0.0 0.0 65.0 92.0

6.5 4.2 73.2 94.3

0.0 0.0 64.0 88.0

6.4 3.6 70.7 90.7

0.0 0.0 40.0 84.0

10.5 3.1 60.1 90.1

0.0 0.0 56.3 88.0

7.8 3.6 68.0 91.7

Figure 5: Visualization of a test example from RegularMaze comparing visual planning variants. Table 4: Performance of text-based planning variants on RegularMaze under the "Unseen Rule" setting. Model Direct SFT w/ Coordinates w/ ASCII

EM (%) 65.3 69.0 67.0

PR (%) 71.4 73.7 70.6

bottom row of Fig. 5, the model alternates between action execution (e.g., ExecuteMove) and explicit rule verification (e.g., VerifyRule) at each step. When a candidate action leads to a potential violation, the verification tool provides immediate feedback, enabling the model to revise its plan accordingly. This step-wise interaction ensures that all intermediate states remain rule-compliant.

6

Conclusion

We present RuleMaze, a benchmark for evaluating multimodal large language models (MLLMs) on rule-based visual spatial planning,

a challenging task that requires the joint integration of visual perception, rule interpretation, and constrained action planning. To support scalable evaluation, we propose Language–Logic–Function Hybridization, which automatically generates and validates diverse rule sets while reducing the need for costly manual construction. Building on this benchmark, we introduce Disentangled Multimodal Planning (DMP), a structured planning framework that explicitly separates perception, plan execution, and rule verification. Experiments confirm that DMP significantly improves rule compliance and success over textual planning baselines. RuleMaze establishes a principled framework for advancing grounded and interpretable planning in MLLMs.

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

Rule-Compliant Visual Spatial Planning for Multimodal Large Language Models

References [1] Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al. 2023. Gpt-4 technical report. arXiv preprint arXiv:2303.08774 (2023). [2] Constructions Aeronautiques, Adele Howe, Craig Knoblock, ISI Drew McDermott, Ashwin Ram, Manuela Veloso, Daniel Weld, David Wilkins Sri, Anthony Barrett, Dave Christianson, et al. 1998. Pddl—the planning domain definition language. Technical Report, Tech. Rep. (1998). [3] Shuai Bai, Keqin Chen, Xuejing Liu, Jialin Wang, Wenbin Ge, Sibo Song, Kai Dang, Peng Wang, Shijie Wang, Jun Tang, et al. 2025. Qwen2. 5-vl technical report. arXiv preprint arXiv:2502.13923 (2025). [4] Haonan Chang, Kai Gao, Kowndinya Boyalakuntla, Alex Lee, Baichuan Huang, Jingjin Yu, and Abdeslam Boularias. 2024. Lgmcts: Language-guided montecarlo tree search for executable semantic object rearrangement. In 2024 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). IEEE, 13607– 13612. [5] Qizhou Chen, Taolin Zhang, Chengyu Wang, Xiaofeng He, Dakan Wang, and Tingting Liu. 2025. Attribution analysis meets model editing: Advancing knowledge correction in vision language models with visedit. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 39. 2168–2176. [6] Songle Chen, Hongbo Sun, Yuxin Wu, Lei Shang, and Xiukai Ruan. 2025. A helmet detection algorithm based on transformers with deformable attention module. Chinese Journal of Electronics 34, 1 (2025), 229–241. [7] Gheorghe Comanici, Eric Bieber, Mike Schaekermann, Ice Pasupat, Noveen Sachdeva, Inderjit Dhillon, Marcel Blistein, Ori Ram, Dan Zhang, Evan Rosen, et al. 2025. Gemini 2.5: Pushing the frontier with advanced reasoning, multimodality, long context, and next generation agentic capabilities. arXiv preprint arXiv:2507.06261 (2025). [8] Alan Dao and Dinh Bach Vu. 2025. AlphaMaze: Enhancing Large Language Models’ Spatial Intelligence via GRPO. arXiv preprint arXiv:2502.14669 (2025). [9] Yifan Du, Kun Zhou, Yingqian Min, Yue Ling, Wayne Xin Zhao, and Youbin Wu. 2025. Revisiting the Necessity of Lengthy Chain-of-Thought in Vision-centric Reasoning Generalization. arXiv preprint arXiv:2511.22586 (2025). [10] Jiayi Gao, Qingchao Chen, Yuxin Peng, and Yang Liu. 2026. Taming I2V models for Image HOI Editing: A Cognitive Benchmark and Agentic Self-Correcting Framework. arXiv preprint arXiv:2606.19073 (2026). [11] Hengrui Gu, Kaixiong Zhou, Xiaotian Han, Ninghao Liu, Ruobing Wang, and Xin Wang. 2024. Pokemqa: Programmable knowledge editing for multi-hop question answering. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 8069–8083. [12] Jia-Chen Gu, Hao-Xiang Xu, Jun-Yu Ma, Pan Lu, Zhen-Hua Ling, Kai-Wei Chang, and Nanyun Peng. 2024. Model editing harms general abilities of large language models: Regularization to the rescue. arXiv preprint arXiv:2401.04700 (2024). [13] Xiaoxiao Guo, Satinder Singh, Honglak Lee, Richard Lewis, and Xiaoshi Wang. 2014. Deep learning for real-time Atari game play using offline Monte-Carlo tree search planning. Advances in neural information processing systems 27 (2014). [14] Haoran Hao, Jiaming Han, Changsheng Li, Yu-Feng Li, and Xiangyu Yue. 2025. RAP: Retrieval-Augmented Personalization for Multimodal Large Language Models. In Proceedings of the Computer Vision and Pattern Recognition Conference. 14538–14548. [15] Yushi Hu, Hang Hua, Zhengyuan Yang, Weijia Shi, Noah A Smith, and Jiebo Luo. 2023. Promptcap: Prompt-guided image captioning for vqa with gpt-3. In Proceedings of the IEEE/CVF International Conference on Computer Vision. 2963– 2975. [16] Subbarao Kambhampati. 2024. Can large language models reason and plan? Annals of the New York Academy of Sciences 1534, 1 (2024), 15–18. [17] Subbarao Kambhampati, Karthik Valmeekam, Lin Guan, Mudit Verma, Kaya Stechly, Siddhant Bhambri, Lucas Saldyt, and Anil Murthy. 2024. Llms can’t plan, but can help planning in llm-modulo frameworks. arXiv preprint arXiv:2402.01817 (2024). [18] Ting Lei, Jialin Liu, Zhu Xu, Yuxin Peng, and Yang Liu. 2026. Unleashing Multimodal Large Language Models for Training-free HOI Detection in the Wild. arXiv preprint arXiv:2607.13881 (2026). [19] Ting Lei, Shaofeng Yin, Qingchao Chen, Yuxin Peng, and Yang Liu. 2025. OpenVocabulary HOI Detection with Interaction-aware Prompt and Concept Calibration. [20] Chengzu Li, Wenshan Wu, Huanyu Zhang, Yan Xia, Shaoguang Mao, Li Dong, Ivan Vulić, and Furu Wei. 2025. Imagine while reasoning in space: Multimodal visualization-of-thought. arXiv preprint arXiv:2501.07542 (2025). [21] Yang Liu, Jiahua Zhang, Yue Wu, Zijing Zhao, Qingchao Chen, and Yuxin Peng. 2026. Confidence-Aware Pseudo-Label Self-Correction for Weakly Supervised Visual Grounding. IEEE Transactions on Pattern Analysis and Machine Intelligence (2026). [22] Yingzi Ma, Yulong Cao, Jiachen Sun, Marco Pavone, and Chaowei Xiao. 2024. Dolphins: Multimodal language model for driving. In European Conference on Computer Vision. Springer, 403–420.

MM ’26, November 10–14, 2026, Rio de Janeiro, Brazil.

[23] Wentao Mo and Yang Liu. 2026. Distilling Neuro-Symbolic Programs into 3D Multi-modal LLMs. arXiv preprint arXiv:2606.01215 (2026). [24] Yuxin Peng, Zishuo Wang, Geng Li, Xiangtian Zheng, Sibo Yin, and Hulingxiao He. 2026. A survey on fine-grained multimodal large language models. Chinese Journal of Electronics 35, 2 (2026), 771–803. [25] Jie-Jing Shao, Bo-Wen Zhang, Xiao-Wen Yang, Bai-Zhi Chen, Si-Yu Han, JingHao Pang, Wen-Da Wei, Guohao Cai, Zhenhua Dong, Lan-Zhe Guo, and Yu feng Li. 2026. ChinaTravel: An Open-Ended Travel Planning Benchmark with Compositional Constraint Validation for Language Agents. In The Fourteenth International Conference on Learning Representations. https://openreview.net/ forum?id=0YRVlxY9BH [26] Zhenwei Shao, Zhou Yu, Meng Wang, and Jun Yu. 2023. Prompting large language models with answer heuristics for knowledge-based visual question answering. In Proceedings of the IEEE/CVF Conference on computer vision and pattern recognition. 14974–14983. [27] Minghe Shen, Zhuo Zhi, Chonghan Liu, Shuo Xing, Zhengzhong Tu, and Che Liu. 2025. Ariadne: A Controllable Framework for Probing and Extending VLM Reasoning Boundaries. arXiv preprint arXiv:2511.00710 (2025). [28] Kaya Stechly, Karthik Valmeekam, and Subbarao Kambhampati. 2024. On the self-verification limitations of large language models on reasoning and planning tasks. arXiv preprint arXiv:2402.08115 (2024). [29] Richard S Sutton. 1991. Planning by incremental dynamic programming. In Machine learning proceedings 1991. Elsevier, 353–357. [30] Kexian Tang, Junyao Gao, Yanhong Zeng, Haodong Duan, Yanan Sun, Zhening Xing, Wenran Liu, Kaifeng Lyu, and Kai Chen. 2025. LEGO-Puzzles: How Good Are MLLMs at Multi-Step Spatial Reasoning? arXiv preprint arXiv:2503.19990 (2025). [31] Gemini Team, Rohan Anil, Sebastian Borgeaud, Jean-Baptiste Alayrac, Jiahui Yu, Radu Soricut, Johan Schalkwyk, Andrew M Dai, Anja Hauth, Katie Millican, et al. 2023. Gemini: a family of highly capable multimodal models. arXiv preprint arXiv:2312.11805 (2023). [32] Xiaoyu Tian, Junru Gu, Bailin Li, Yicheng Liu, Yang Wang, Zhiyong Zhao, Kun Zhan, Peng Jia, Xianpeng Lang, and Hang Zhao. 2024. Drivevlm: The convergence of autonomous driving and large vision-language models. arXiv preprint arXiv:2402.12289 (2024). [33] Yiwei Wang, Muhao Chen, Nanyun Peng, and Kai-Wei Chang. 2024. Deepedit: Knowledge editing as decoding with constraints. arXiv preprint arXiv:2401.10471 (2024). [34] Yi Xu, Chengzu Li, Han Zhou, Xingchen Wan, Caiqi Zhang, Anna Korhonen, and Ivan Vulić. 2025. Visual Planning: Let’s Think Only with Images. arXiv:2505.11409 [cs.LG] https://arxiv.org/abs/2505.11409 [35] Zhu Xu, Ting Lei, Zhimin Li, Guan Wang, Qingchao Chen, Yuxin Peng, and Yang Liu. 2025. TRKT: Weakly Supervised Dynamic Scene Graph Generation with Temporal-enhanced Relation-aware Knowledge Transferring. In Proceedings of the IEEE/CVF International Conference on Computer Vision. 15812–15821. [36] Cheng Yang, Haiyuan Wan, Yiran Peng, Xin Cheng, Zhaoyang Yu, Jiayi Zhang, Junchi Yu, Xinlei Yu, Xiawu Zheng, Dongzhan Zhou, and Chenglin Wu. 2025. Reasoning via Video: The First Evaluation of Video Models’ Reasoning Abilities through Maze-Solving Tasks. arXiv preprint arXiv:2511.15065 (2025). [37] Dejie Yang, Zijing Zhao, and Yang Liu. 2025. Ar-vrm: Imitating human motions for visual robot manipulation with analogical reasoning. In Proceedings of the IEEE/CVF International Conference on Computer Vision. 6818–6827. [38] Dejie Yang, Zijing Zhao, and Yang Liu. 2025. Planllm: Video procedure planning with refinable large language models. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 39. 9166–9174. [39] Xu Yang, Yongliang Wu, Mingzhuo Yang, Haokun Chen, and Xin Geng. 2023. Exploring diverse in-context configurations for image captioning. Advances in Neural Information Processing Systems 36 (2023), 40924–40943. [40] Zhiwen Yang and Yuxin Peng. 2026. Gala-2.5 d: Global-local alignment with 2.5 d semantic guidance for camera-based 3d semantic scene completion in autonomous driving. Chinese Journal of Electronics 35, 2 (2026), 817–828. [41] Shaofeng Yin, Ting Lei, and Yang Liu. 2025. Toolvqa: A dataset for multi-step reasoning vqa with external tools. In Proceedings of the IEEE/CVF International Conference on Computer Vision. 4424–4433. [42] Kaining Ying, Fanqing Meng, Jin Wang, Zhiqian Li, Han Lin, Yue Yang, Hao Zhang, Wenbo Zhang, Yuqi Lin, Shuo Liu, et al. 2024. Mmt-bench: A comprehensive multimodal benchmark for evaluating large vision-language models towards multitask agi. arXiv preprint arXiv:2404.16006 (2024).

Supplementary Material for Rule-Compliant Visual Spatial Planning for Multimodal Large Language Models

A

Yu Chen

Ting Lei

Yaoyi Li

Wangxuan Institute of Computer Technology, Peking University Beijing, China yu_chen@stu.pku.edu.cn

Wangxuan Institute of Computer Technology, Peking University Beijing, China ting_lei@pku.edu.cn

Yinwang Intelligent Technology Co., Ltd Shenzhen, China liyaoyi@yinwang.com

Jia Cai

Zhecen Wu

Yang Liu∗

Yinwang Intelligent Technology Co., Ltd Shenzhen, China caijianwpu@gmail.com

Yinwang Intelligent Technology Co., Ltd Shenzhen, China wuzhecen@yinwang.com

Wangxuan Institute of Computer Technology, Peking University Beijing, China yangliu@pku.edu.cn

Limitations and Future Work

In this work, we focus on controllable grid-based visual environments to study rule-compliant spatial planning in multimodal large language models. RuleMaze is intentionally designed as a controlled abstraction rather than a complete simulation of real-world environments. Since real-world settings rarely provide ground-truth trajectories under dynamically varying rules, we use synthetic data to isolate and systematically evaluate visual perception, rule interpretation, and verifiable planning. This design allows the systematic construction of rule–maze pairs and enables precise evaluation of rule-following behaviors under varying levels of difficulty. However, such environments remain simplified abstractions of real-world spatial reasoning settings, where perceptual noise, continuous dynamics, and partially observable states are often present. While the current formulation provides a useful testbed for controlled analysis, extending the framework to more diverse and realistic visual environments remains an important direction for future work. At the framework level, DMP separates domain-specific visual grounding and action execution from rule-specific verification. This modularity allows adaptation to new environments to be primarily achieved by replacing the domain interface with appropriate perception and execution tools, while preserving the overall planning and verification framework. Another limitation lies in the current formulation of rule verification. Our framework relies on externally synthesized validator functions that deterministically evaluate rule compliance. This design enables scalable dataset construction and flexible rule replacement, but assumes that rule semantics can be precisely formalized and operationalized. In broader applications, rule descriptions may be ambiguous, incomplete, or context-dependent. Developing verification mechanisms that can operate under softer or partially specified constraints may further improve the robustness of rule-based planning systems. In addition, the proposed Disentangled Multimodal Planning (DMP) framework introduces iterative tool invocation during inference, which may incur additional computational overhead compared to direct end-to-end prediction strategies. However, it is worth noting that alternative reasoning paradigms can also exhibit ∗ Corresponding author.

substantial computational costs. For example, in our experiments, strong reasoning-based models, such as Gemini, generated over 1,500 thinking tokens in certain cases yet still failed to produce a valid rule-compliant trajectory. This observation suggests that computational cost is influenced not only by architectural design but also by the structure of the reasoning process itself. Future research may explore adaptive reasoning policies to further reduce computational overhead while maintaining reliability and interpretability. Overall, we view RuleMaze and Disentangled Multimodal Planning (DMP) as an initial step toward systematically studying rulecompliant multimodal planning under explicit constraints. By demonstrating that models can coordinate perception, execution, and rule verification through structured interactions, this work opens new possibilities for building multimodal agents that reason under externally specified rules. Such capabilities may be particularly relevant to domains where perception and decision-making are tightly coupled, including robotics, navigation, and embodied assistance systems. We advocate for future research toward more holistic multimodal planning paradigms, where structured reasoning traces—potentially involving both symbolic and visual feedback—enable more reliable and interpretable decision-making under complex and evolving constraints.

B Ablation Study B.1 DMP-Prompting without Post-Training To disentangle the benefits of tool access from that of structured tool-trace training, we further introduce DMP-Prompting (DMP-P), a prompting-based variant that provides an off-the-shelf MLLM with the same perception, execution, and verification tools used in DMP, while performing no parameter updates or post-training. DMP-P follows the same iterative interaction paradigm, allowing the backbone model to inspect the visual environment, execute candidate actions, and verify rule compliance through external tools during inference. We evaluate DMP-P using Gemini-2.5-Pro, GPT-5, and Qwen2.5-VL-3B as different backbone models. Tab. 1 reports their average EM and PR over the unseen-rule split of RegularMaze. The results lead to three observations. First, access to the disentangled tools consistently improves rule-compliant planning, with

MM ’26, November 10–14, 2026, Rio de Janeiro, Brazil.

Yu Chen et al.

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. † denotes a post-trained model. Method

EM (%)

PR (%)

Gemini-2.5-Pro Gemini-2.5-Pro + DMP-P GPT-5 GPT-5 + DMP-P Qwen2.5-VL-3B Qwen2.5-VL-3B + DMP-P

45.6 64.0 53.5 81.4 0.0 0.0

51.7 67.6 61.3 84.1 11.7 17.3

DMP-3B† (Ours)

90.0

92.7

particularly substantial gains for GPT-5, whose EM/PR increases from 53.5/61.3 to 81.4/84.1. Second, DMP-P also improves Gemini2.5-Pro from 45.6/51.7 to 64.0/67.6, demonstrating that the proposed planning paradigm is applicable across different proprietary backbones rather than being tied to a particular model architecture. In contrast, the improvement on the smaller Qwen2.5-VL-3B backbone is limited, suggesting that tool access alone may be insufficient when the base model has not learned how to reliably select, sequence, and integrate tool outputs. Finally, DMP-3B still achieves the best EM/PR performance of 90.0/92.7, indicating that structured tool-trace training remains important for learning effective tool orchestration and generalizing to previously unseen rules.

B.2

Tool Modules

To better understand the contribution of each module in the proposed Disentangled Multimodal Planning (DMP) framework, we conduct a series of ablation experiments by selectively removing individual components while keeping the remaining training and evaluation settings unchanged. Results are reported in Tab. 2. We first examine the effect of removing the execution module. Without the execution tool, the model loses the ability to explicitly update visual states after each action and relies only on text-based state updates. As a result, planning must rely on implicit reasoning over the initial observation, leading to a substantial drop in both Exact Match (EM) and Precision Rate (PR) across all difficulty levels. This observation highlights the importance of explicit state transitions for maintaining consistent spatial reasoning over multi-step trajectories. Next, we evaluate the impact of removing the verification module. Without explicit rule checking, the model is still able to generate reasonable navigation trajectories, but lacks feedback on rule compliance. As shown in Tab. 2, performance decreases compared to the full DMP model, particularly under unseen and higher-complexity rules. This suggests that explicit verification plays an important role in preventing rule violations during long-horizon planning. We further consider a setting where both perception and verification modules are removed. In this configuration, the model no longer has access to structured cell-state information produced by perception tools. Consequently, the verification mechanism cannot

be effectively applied, as rule compliance depends on accurate intermediate state identification. As expected, this variant shows slightly lower performance than removing verification alone. This result indicates that perception-derived state representations provide the necessary context for reliable rule evaluation, and that the interaction between perception and verification modules contributes to stable planning behavior. Overall, these ablation results suggest that the three tool modules—perception, execution, and verification—play complementary roles in the DMP framework. Among them, execution provides explicit state transitions that support consistent reasoning, verification introduces rule-aware feedback during planning, and perception enables structured interpretation of intermediate states. Removing any component leads to observable degradation, confirming the importance of disentangled tool interactions in rule-compliant spatial planning.

B.3

Training Data Scale

We study the impact of training data scale by training both Direct SFT and DMP using 25%, 50%, and 100% of the available training data. The results are summarized in Tab. 3. Empirically, we observe that performance improves consistently as the amount of training data increases for both methods. However, a clear performance gap between Direct SFT and DMP is observed across all data scales, particularly under unseen-rule settings. Notably, under the 25% data setting, Direct SFT exhibits substantial performance degradation, whereas DMP maintains relatively stable performance. This observation suggests that the structured perception–execution–verification pipeline provides stronger inductive bias, enabling more reliable generalization even with limited supervision. Overall, these results suggest that DMP demonstrates stronger data efficiency compared to purely text-based planning, particularly in low-data regimes and under challenging unseen-rule conditions.

B.4

Text-Based Representation Variants

To further analyze whether improved textual representations alone can enhance planning performance, we compare the proposed DMP framework with several text-based planning variants that explicitly encode spatial structure into textual outputs. The results are summarized in Tab. 4. We first consider a Direct SFT setting, where the model is trained to directly output the final action sequence without producing intermediate structural descriptions. This baseline achieves strong performance on seen rules, indicating that the model can learn task-specific navigation patterns under supervised training. However, performance degrades notably under unseen rules, suggesting limited generalization to novel rule compositions. To examine whether making spatial information more explicit benefits planning, we introduce two structured textual planning variants. In the SFT with Coordinates setting, the model is trained to first output a coordinate-based description of the grid environment, including key elements such as start and goal positions, followed by the full action sequence. In the SFT with ASCII setting, the model instead generates an ASCII-based layout of the maze before producing the action sequence. Examples of these formats are shown

Supplementary Material for Rule-Compliant Visual Spatial Planning for Multimodal Large Language Models

MM ’26, November 10–14, 2026, Rio de Janeiro, Brazil.

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. Seen Rule Model

Unseen Rule

Avg.

Easy

Medium

Hard

Avg.

EM (%)

PR (%)

EM (%)

PR (%)

EM (%)

PR (%)

EM (%)

PR (%)

EM (%)

PR (%)

63.0 91.7 88.5 98.0

63.2 92.5 89.3 98.4

50.0 94.0 91.0 95.0

53.5 94.6 92.0 96.7

34.0 78.0 74.0 88.0

36.8 79.2 76.1 91.9

30.0 70.0 66.0 87.0

33.3 73.4 69.5 89.6

38.0 80.6 77.0 90.0

41.2 82.4 79.1 92.7

w/o Execution w/o Verification w/o Perception + Verification DMP (Ours)

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

Avg.

Easy

Medium

Hard

Avg.

EM (%)

PR (%)

EM (%)

PR (%)

EM (%)

PR (%)

EM (%)

PR (%)

EM (%)

PR (%)

Direct SFT (25%) Direct SFT (50%) Direct SFT (100%)

35.0 67.0 95.0

45.6 74.1 95.3

35.0 67.0 72.0

48.7 75.1 76.6

29.0 55.0 65.0

38.2 62.6 69.9

18.0 43.0 58.9

31.1 55.2 67.7

27.3 55.0 65.3

39.3 64.3 71.4

DMP (25%) DMP (50%) DMP (100%)

79.0 95.0 98.0

84.4 96.5 98.4

71.0 90.0 95.0

81.1 92.9 96.7

65.0 86.3 88.0

74.9 89.4 91.9

62.0 84.1 87.0

71.5 86.5 89.6

66.0 86.8 90.0

75.8 89.6 92.7

in Fig. 1. As shown in Tab. 4, both structured textual variants provide modest improvements over Direct SFT under unseen rules. In particular, the coordinate-based representation achieves slightly higher average performance, suggesting that explicitly encoding key spatial locations may help stabilize early planning decisions. However, the overall performance gap between these textual methods and the full DMP framework remains substantial, especially for harder rule settings. Overall, these results suggest that enhancing textual representations alone provides limited benefits for rule-compliant visual spatial planning. While structured outputs such as coordinates or ASCII layouts can partially improve spatial awareness, they do not provide explicit mechanisms for enforcing rule constraints. In contrast, the DMP framework integrates visual grounding with executable perception and verification tools, enabling more reliable multi-step reasoning under unseen rule conditions.

C

Additional Analysis of Rule Diversity

To provide a more comprehensive characterization of RuleMaze, we analyze the diversity and structural complexity of its naturallanguage rules from two complementary perspectives: semantic type and logical connective usage. We additionally discuss the potential linguistic biases introduced by LLM-based rule generation.

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

MM ’26, November 10–14, 2026, Rio de Janeiro, Brazil.

Yu Chen et al.

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. Seen Rule

Model

Unseen Rule

Avg.

Easy

Medium

PR (%)

EM (%)

PR (%)

EM (%)

PR (%)

EM (%)

PR (%)

EM (%)

PR (%)

95.0 97.0 95.0 98.0

95.3 97.6 95.0 98.4

72.0 77.0 73.0 95.0

76.6 82.6 78.3 96.7

65.0 68.0 68.5 88.0

69.9 70.9 70.7 91.9

58.9 62.0 59.5 87.0

67.7 67.6 62.8 89.6

65.3 69.0 67.0 90.0

71.4 73.7 70.6 92.7

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

History-dependent

Requirement

Prohibition

64.9%

31.3%

61.3%

51.0%

Ratio

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

Connective

if

must

and

or

not

cannot

Avg. count

0.42

0.55

0.16

0.06

0.17

0.16

C.1

Semantic Diversity

We first categorize the rules according to four high-level semantic properties: direction dependence, history dependence, requirements, and prohibitions. A direction-dependent rule constrains the agent’s movement direction based on the current state or local environment. A history-dependent rule requires information about previous states or actions, such as whether a region has previously been visited. Requirement rules prescribe actions or states that must occur, whereas prohibition rules specify actions or states that are not allowed. As shown in Tab. 5, RuleMaze contains substantial diversity across these semantic dimensions. Direction-dependent rules constitute 64.9% of the rule set, while 31.3% require reasoning over historical states. Requirement and prohibition constraints account for 61.3% and 51.0% of the rules, respectively.

C.2

Logical Structure

We next analyze the logical structure of the generated rules. Tab. 6 reports the average number of occurrences of different logical connectives and constraint markers per rule. Conditional and mandatory constructions are the most frequent: each rule contains, on average, 0.42 occurrences of if and 0.55 occurrences of must. Conjunction, disjunction, negation, and explicit prohibition are also represented, enabling rules to express interactions among multiple predicates and constraints.

C.3

Avg.

EM (%) Direct SFT w/ Coordinates w/ ASCII DMP (Ours)

Semantic type

Hard

Potential Bias in LLM-Generated Rules

Although the Language–Logic–Function pipeline supports the scalable construction of logically diverse rules, it may inherit biases

from the LLM used during rule ideation. In particular, the model may repeatedly use similar concise wording patterns for rules that share related logical structures. As a result, the logical and semantic diversity quantified above does not necessarily imply equally broad linguistic diversity at the surface-form level. Models may therefore benefit partially from recurring lexical or syntactic patterns, even when the underlying logical formalizations are absent from training data. This limitation does not affect the executable correctness of the benchmark after validator verification, but it may influence how broadly the resulting performance generalizes to naturally occurring rule descriptions. Future extensions could increase linguistic diversity through controlled paraphrasing, human-authored rules, adversarial rewriting, and evaluation on rules collected from realworld instructions. Such extensions would help distinguish generalization to unseen logical structures from robustness to diverse natural-language realizations of the same underlying constraint.

D

Error Analysis

To better understand the remaining failure patterns of the proposed DMP framework, we analyze prediction errors on unseen-rule settings. Among the failure cases, approximately 37.5% of errors are associated with missing verification calls in the proper step. In these cases, the model generates an action sequence without properly invoking the VerifyRule() tool, which prevents explicit detection of rule violations. This observation suggests that consistent usage of verification plays an important role in maintaining rule compliance during multi-step planning. For the remaining cases where verification is present, we analyze the earliest step at which trajectory deviations occur. A clear trend emerges that most failures originate from early-stage decisions. Specifically, over 70% of first errors occur at the initial step, followed by roughly 20% at the second step and fewer than 10% at later steps. This result indicates that trajectory correctness is highly dependent on early-step decisions, and incorrect initial actions directly determine the final mismatch outcome. We further examine the types of rules most frequently associated with failures. These errors are commonly observed in rules that involve conditional transitions dependent on both spatial location and recent action history. Typical examples include rules that enforce directional landing constraints (e.g., requiring movement into a specific zone after a particular direction) or rules that impose short-term sequential dependencies. We also analyze how trajectory success varies with action sequence length. As shown

Supplementary Material for Rule-Compliant Visual Spatial Planning for Multimodal Large Language Models

MM ’26, November 10–14, 2026, Rio de Janeiro, Brazil.

operators used across all formulas: NOT (negation), AND (conjunction), OR (disjunction), -> (material implication), and parentheses for grouping. Table 7: CNF predicate vocabulary. Scenario

Predicate

RegularMaze Zone(t, "col")

QuestMaze

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).

in Fig. 2, success rates gradually decrease as trajectory length increases, dropping from approximately 92% for short sequences to around 73% for longer sequences. This trend suggests that longer planning horizons introduce additional challenges for maintaining consistent rule-compliant visual spatial planning. Overall, these observations suggest that remaining errors primarily stem from two factors: incomplete verification usage and early-stage decision deviations under complex conditional rules. These findings indicate that improving verification consistency and strengthening early-step decision reliability may further enhance the robustness of rule-compliant multimodal planning.

E Implementation Details E.1 Training Details We fine-tune Qwen2.5-VL-3B-Instruct using supervised fine-tuning with LoRA adaptation. Following a parameter-efficient setup, LoRA is applied to all trainable modules with rank 8. The model is trained for 15 epochs with a batch size of 32. We use a learning rate of 1 × 10−4 with cosine decay and a warmup ratio of 0.1. Mixed-precision training with bf16 is enabled to improve training efficiency.

E.2

Data Generation Pipeline

E.2.1

Stage 1: Rule Ideation and Logical Formalization.

E.2.2

Semantics

Example

Cell color at 𝑡

Zone(t, "blue")

Move(t, "dir")

Action at 𝑡

Move(t-1, "up")

Seen("item")

Item on path

Seen("key")

Moved("dir")

Direction taken

NOT Moved("down")

Count(s, op, v)

Count constr.

Count("food", ≥ , 3)

TargetIs(tg)

Goal reached

TargetIs("treasure")

Stage 2: Automated Rule Compilation.

Prompting Templates. Fig. 4 demonstrates the automated translation from symbolic logic to executable Python code. In this stage, the system prompts the LLM to interpret the CNF-style formulas generated in Stage 1(Sec. E.2.1) and implement them as deterministic validator functions. This process ensures that each natural language rule is backed by a verifiable programmatic ground truth. E.2.3

Stage 3: Maze Pool Generation.

Generation Detail. Each maze is an 𝑁 ×𝑁 grid (default 𝑁 =3) whose cells are connected by passages; walls between adjacent cells are either open or closed. A fixed loopPercent = 10 is used: after DFS perfect-maze generation, 10% of candidate walls are removed to introduce additional solution paths. The hierarchical generation process is organized as follows: Alg. 1 defines the top-level loop governing the entire dataset collection. Within this framework, the procedure for synthesizing an individual maze instance is detailed in Alg. 2, which comprises two primary stages. First, Alg. 3 establishes the underlying structural topology and path connectivity. Subsequently, Alg. 4 specifies the heuristic for populating the maze with colored cells or symbols, ensuring a diverse distribution of semantic symbols essential for subsequent visual reasoning tasks. Algorithm 1: Maze Pool Generation Input : Grid size 𝑁 ; total mazes 𝑀 (default 50 000); colour list C; number of parallel processes 𝑃 (default 10) Output : Maze pool stored on disk G ← {(𝑖, 𝑗) | 1 ≤ 𝑖, 𝑗 ≤ 𝑁 } /* all valid cell positions 2 Partition [0, 𝑀) into 𝑃 equal sub-ranges [𝑐 0, 𝑐 1 ), [𝑐 1, 𝑐 2 ), . . . , [𝑐 𝑃 −1, 𝑀); 3 foreach sub-range [𝑐 𝑘 , 𝑐 𝑘+1 ) in parallel do 4 GenerateMazeBatch(𝑐𝑘 , 𝑐𝑘+1, G, 𝑁 , C); 1

Prompting Templates. To illustrate the logic synthesis process, Fig. 3 presents a representative prompt used for rule ideation along with its corresponding structured output. The prompt enforces strict logical constraints and formatting requirements, ensuring that the generated rules are both diverse and compatible with the setting of our task.

5

Predicate Reference. Tab. 7 lists the full predicate vocabulary used in CNF logical representations across both scenario types. Logical

Wait for all 𝑃 processes to complete;

*/

MM ’26, November 10–14, 2026, Rio de Janeiro, Brazil.

Yu Chen et al.

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.

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.

E.3

Validator Code Implementation Analysis

Fig. 5 presents the core implementation of the validate_symbolic_ path function. After manual refinement, this logic corresponds to the rule: "To prove his courage, the Prince must move Left at least once." When using LLMs to generate validator code, the generated implementations achieve an accuracy of 93%, but the models frequently produce overly simplified checks, such as "left" not in actions_taken. To fix this, we manually added a target_count > 0

constraint to better handle two different stages: Data Matching and Dynamic Inference. In the matching stage, the system checks completed paths that have already reached the goal, so simple assertions work fine. However, during real-time inference, the system evaluates partial paths that are still in progress. Without checking if the goal has been reached, the validator would wrongly reject a path just because the agent hasn’t moved "left" yet, even though it might do so in future steps. By adding the target_count > 0 condition,

Supplementary Material for Rule-Compliant Visual Spatial Planning for Multimodal Large Language Models

MM ’26, November 10–14, 2026, Rio de Janeiro, Brazil.

Algorithm 2: GenerateMazeBatch(start, end, G, 𝑁 , C) Input : Index range [start, end); cell set G; grid size 𝑁 ; colour list C Output : JSON batch file + PNG images saved to disk

Algorithm 3: CreateMaze(𝑁 , src, dst) — DFS with loop injection (lp=10) Input : Grid size 𝑁 ; start cell src; goal cell dst Output : Maze map 𝑀 with walls and cell states

count ← start; while count < end do /* — Step 1: Sample start/end cells — 3 (src, dst) ∼ Uniform-Sample(G, 𝑘=2);

Initialise all walls closed; mark src as green, dst as red; /* — Phase 1: DFS perfect-maze generation — */ 2 stack ← [src]; visited ← {src}; 3 while stack ≠ ∅ do 4 𝑢 ← stack.top(); 5 𝑁𝑢 ← {𝑣 | 𝑣 adjacent to 𝑢, 𝑣 ∉ visited}; 6 if 𝑁𝑢 ≠ ∅ then 7 𝑣 ∼ Uniform(𝑁𝑢 ); 8 RemoveWall(𝑀, 𝑢, 𝑣); /* open passage between 𝑢 and 𝑣 */ 9 visited ← visited ∪ {𝑣 }; stack.push(𝑣); 10 else 11 stack.pop(); 1

1 2

*/

4

/* — Step 2: Generate maze via DFS + loop removal (lp = 10) — 𝑀 ← CreateMaze(𝑁 , src, dst) /* see Alg. 3

5

/* — Step 3: Enumerate all solution paths — */ P ← GetAllSolutionPaths(𝑀);

*/ */

7

/* — Step 4: Require exactly 2 solution paths — */ if |P | ≠ 2 then continue ; /* reject; retry */ ;

8

/* — Step 5: Paint colored cells — 𝑀 ← AddColouredCells(𝑀, P, C) /* Alg. 4

*/ */

/* — Step 6: Render and persist — img ← RenderMazeImage(𝑀); Append {𝑀, P, src, dst, img} to batch buffer; count ← count + 1;

*/

6

9 10 11 12

Save batch buffer as JSON; save img files as PNG;

we ensure that rule validation is conducted only when the agent reaches the goal state, as compliance with such rules can only be evaluated over the complete trajectory. This prevents intermediate states from being incorrectly judged as violations during the search process.

E.4

Disentangled Tools Implementation

We describe the five disentangled tools used in the DMP framework. Each tool encapsulates a single atomic interaction with the maze environment, keeping perception, execution, and verification concerns strictly separated. The maze environment is represented as a pixel image 𝐼𝑡 ∈ R𝐻 ×𝑊 ×3 . Its internal state is not directly accessible to the agent; all information must be obtained by calling tools. Tools interact with the environment through two shared primitives: GridDivision parses the image to recover cell geometry (𝑔ℎ , 𝑔𝑤 , 𝑥 0, 𝑦0, 𝑙 𝑤 ), and CLIP provides visual embeddings for cell-content classification. The agent’s current position is communicated across tool calls via a colored circle marker drawn directly onto the image. E.4.1

Perception Tools.

LocateStart. Alg. 5 illustrates the workflow of the spatial localization tool, which bootstraps the agent’s spatial awareness directly from raw maze images. The algorithm systematically scans each cell in the maze grid to extract localized patches, subsequently computing the CLIP-based cosine similarity between these patches and

/* — Phase 2: Add loops by removing extra walls (lp = 10) — */ 12 P0 ← GetAllSolutionPaths(𝑀) ; /* paths through perfect maze */ 13 𝑛 on ← |walls on a solution path|; 𝑛 off ← |remaining walls|; 14 Remove ⌊𝑛 on /3 · 0.1⌋ random on-path walls; 15 Remove ⌊𝑛 off /3 · 0.1⌋ random off-path walls ; /* isCyclic check avoids trivial squares */ 16 return 𝑀;

a reference "start" legend. The cell exhibiting the peak similarity score is designated as the origin. To maintain a stateless workflow, the tool overlays a distinctive colored circle onto the identified start cell. This visual indicator serves two purposes: first, it acts as a visual prompt for the multimodal model to perceive its current location directly from the image; second, it encodes the spatial state into the maze grid, allowing subsequent tools to decode the coordinates and update the agent’s progress without relying on external memory. InspectGrid. Alg. 6 details the procedure for extracting the semantic content of the agent’s current cell. The tool first decodes the agent’s grid coordinates by localizing the marker pixel cluster within the current observation 𝐼𝑡 . Once the coordinates are obtained, it extracts the corresponding cell patch and performs zero-shot classification against a predefined symbol vocabulary L using CLIP embeddings. Depending on the environment, L represents cell colors in the RegularMaze or specific entities (e.g., key, food, princess) in the QuestMaze variant. The identified symbol 𝑠𝑡 is then appended to the agent’s trajectory history, providing the essential state information for subsequent evaluation by VerifyRule. E.4.2

Execution Tool.

ExecuteMove. Alg. 7 defines the primary mechanism for the agent’s spatial transitions within the maze. The tool first decodes

MM ’26, November 10–14, 2026, Rio de Janeiro, Brazil.

Yu Chen et al.

Algorithm 4: AddColouredCells(𝑀, P, C) — colour injection Input : Maze grid 𝑀; set of solution paths P; colour palette C Output : 𝑀 with some non-default cells painted a rule-relevant colour if Uniform(0, 1) < 0.2 then return 𝑀 ; /* 20% chance: skip colouring */ 2 ; ∗ 3 𝑐 ∼ Uniform(C) ; /* sample a colour */ 4 type ∼ Uniform({1, 2}) ; /* type-1: cross-cells; type-2: solution cells */ 1

if type = 1 then X ← FindCrossCells(𝑀, P) ; /* cells shared by ≥ 2 distinct paths */ 7 𝑘 ∼ Uniform({1, . . . , |X|}); 8 S ∼ Uniform-Sample(X, 𝑘);

5

6

else X ← FindSolutionPathCells(𝑀, P) ; cells on any solution path */ 11 𝑘 ∼ Uniform({1, . . . , ⌊|X|/3⌋}); 12 S ∼ Uniform-Sample(X, 𝑘); 9

/* all

10

foreach cell 𝑢 ∈ S do 𝑀 [𝑢].state ← 𝑐 ∗ .name; 15 𝑀 [𝑢].color ← 𝑐 ∗ .rgb;

13

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.

14

16

return 𝑀;

Algorithm 6: InspectGrid(𝐼𝑡 ) Input : Maze image 𝐼𝑡 (with position marker at current cell) Output : Semantic symbol 𝑠𝑡 of the current cell

Algorithm 5: LocateStart(𝐼𝑡 ) Input : Maze image 𝐼𝑡 Output : Annotated image 𝐼𝑡 +1 with a position marker at the start cell 1

(𝑔ℎ , 𝑔𝑤 , 𝑥 0 , 𝑦0 , 𝑙 𝑤 ) ← GridDivision(𝐼𝑡 ) ; geometry from image

∗ 2 𝜎 ← −∞;

// infer cell

(𝑔𝑥∗ , 𝑔∗𝑦 ) ← (0, 0);

foreach cell (𝑔𝑥 , 𝑔𝑦 ) in maze grid do patch ← CropCell(𝐼𝑡 , 𝑔𝑥 , 𝑔𝑦 );
5 𝜎 ← CosineSim CLIP(patch), CLIP(𝐼 start_legend ) ; 6 if 𝜎 > 𝜎 ∗ then 7 𝜎 ∗ ← 𝜎; (𝑔𝑥∗ , 𝑔∗𝑦 ) ← (𝑔𝑥 , 𝑔𝑦 );

3

4

𝐼𝑡 +1 ← DrawMarker(𝐼𝑡 , 𝑔𝑥∗ , 𝑔∗𝑦 ); 9 return 𝐼𝑡 +1 ; 8

the current grid coordinates from the visual marker in 𝐼𝑡 and applies a unit offset corresponding to the selected action 𝑎𝑡 . It then renders the marker at the new coordinate to produce the subsequent observation 𝐼𝑡 +1 . Critically, the tool maintains a minimalist design by not enforcing physical constraints (e.g., walls or boundaries); instead, it delegates the evaluation of rule compliance and physical validity to VerifyRule. By encoding positional updates directly as image

(𝑔𝑥 , 𝑔𝑦 ) ← LocateMarker(𝐼𝑡 ) ; from marker pixels 2 patch ← CropCell(𝐼𝑡 , 𝑔𝑥 , 𝑔 𝑦 ); 1

3 4

// recover grid coords

foreach candidate symbol ℓ in symbol vocabulary L do
𝜎ℓ ← CosineSim CLIP(patch), CLIP(𝐼 ℓ ) ;

𝑠𝑡 ← arg maxℓ ∈L 𝜎ℓ ; if 𝑠𝑡 ∈ {white, background} then 𝑠𝑡 ← normal; 7 return 𝑠𝑡 ; 5

6

annotations rather than internal state variables, the tool preserves a consistent image-only interface across the entire framework. E.4.3

Verification Tools.

VerifyRule. Alg. 8 serves as the symbolic reasoning layer that bridges the natural-language rule 𝑅 with the agent’s trajectory history, operating independently of visual input. The tool retrieves a pre-compiled Python validator function, indexed by the normalized text of 𝑅, which is synthesized during the dataset construction phase (cf. Validator Synthesis in Sec. E.2.2). The consolidated trajectory 𝜏 = {(𝑎𝑡 , 𝑠𝑡 )}𝑇𝑡=1 is passed to this deterministic validator, which evaluates the sequence and returns a boolean compliance status. This design enforces a strict separation of concerns: by isolating

Supplementary Material for Rule-Compliant Visual Spatial Planning for Multimodal Large Language Models

MM ’26, November 10–14, 2026, Rio de Janeiro, Brazil.

Algorithm 7: ExecuteMove(𝐼𝑡 , 𝑎𝑡 ) Input : Maze image 𝐼𝑡 with current position marker; action 𝑎𝑡 ∈ {up, down, left, right} Output : Updated image 𝐼𝑡 +1 with marker at new cell

self-contained design ensures that endpoint verification remains consistent with the framework’s image-centric interface.

(𝑔𝑥 , 𝑔𝑦 ) ← LocateMarker(𝐼𝑡 );

We provide qualitative visualization examples to illustrate how the proposed DMP framework performs rule-aware reasoning during multi-step planning. Representative successful cases from both RegularMaze and QuestMaze test sets are shown in Fig. 6 and Fig. 7, respectively. In Fig. 6, the first-row example demonstrates how the model dynamically corrects an initially invalid decision through explicit verification. Under the rule "If you are in a blue green zone, the next zone you enter must be yellow," the model initially moves into a non-compliant zone. However, after invoking the VerifyRule() tool, the violation is detected, and the model subsequently revises its action choice, leading to a corrected trajectory that satisfies the rule constraint. This example highlights the role of verification feedback in enabling adaptive trajectory refinement rather than committing to early incorrect decisions. Fig. 7 further illustrates model behavior in more complex QuestMaze environments involving denser layouts and more intricate rule dependencies. Despite the increased structural complexity, the model is able to maintain consistent rule-aware reasoning across multiple steps and successfully navigate toward valid goal-reaching trajectories. These examples suggest that the proposed DMP framework remains effective even under more challenging planning conditions. Overall, these qualitative results complement the quantitative evaluations by showing that successful trajectories are not only correct at the final step, but are also supported by interpretable intermediate reasoning behaviors, including rule checking and trajectory correction.

1

// Apply directional offset Δ←  up:(0, −1), down:(0, +1), left:(−1, 0), right:(+1, 0) ; ′ ′ 3 (𝑔𝑥 , 𝑔 𝑦 ) ← (𝑔𝑥 , 𝑔 𝑦 ) + Δ[𝑎𝑡 ]; 2

𝐼𝑡 +1 ← DrawMarker(𝐼𝑡 , 𝑔𝑥′ , 𝑔′𝑦 ); 5 return 𝐼𝑡 +1 ; 4

Algorithm 8: VerifyRule(𝑎 1:𝑡 , 𝑠 1:𝑡 , 𝑅) Input : Action history 𝑎 1:𝑡 ; cell-state history 𝑠 1:𝑡 ; rule 𝑅 (natural-language string) Output : Boolean: True iff the trajectory complies with 𝑅 // Look up the synthesised Python validator for rule 𝑅 1 (code, fname) ← LookupValidator(𝑅); 2 if code = ∅ then return False ; // unknown rule 3 ; // Execute validator in isolated namespace  𝑡 4 𝜏 ← (𝑎𝑖 , 𝑠𝑖 ) ; // zip action and state histories 𝑖=1 5 ns ← {}; exec(code, ns); 6 return ns[fname] (𝜏);

Algorithm 9: VerifyEndpoint(𝐼𝑡 ) Input : Maze image 𝐼𝑡 with current position marker Output : Boolean: True iff the current cell is the target cell 1 2

(𝑔𝑥 , 𝑔𝑦 ) ← LocateMarker(𝐼𝑡 ); patch ← CropCell(𝐼𝑡 , 𝑔𝑥 , 𝑔𝑦 );

3 𝑠 ← InspectGrid(𝐼𝑡 ) ;

// reuse perception for cell

classification
4 return 𝑠 = 𝑠 goal ;

rule semantics from visual perception, the system ensures that logical verification remains invariant to visual noise, relying solely on the synthesized symbolic representation. VerifyEndpoint. Alg. 9 determines the termination of an episode by leveraging the visual classification pipeline established in InspectGrid. The tool extracts the semantic symbol from the agent’s current location in 𝐼𝑡 and compares it against the episode’s designated goal symbol 𝑠 goal . For RegularMaze, 𝑠 goal is typically defined as red, whereas in QuestMaze variants, it corresponds to missionspecific entities such as princess or treasure. Since 𝑠 goal is invariant throughout a given episode, the tool requires no external environmental state beyond the current visual observation. This

F

Qualitative Results

MM ’26, November 10–14, 2026, Rio de Janeiro, Brazil.

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.

Yu Chen et al.

Related documents

• LLM+P: Empowering Large Language Models with Optimal Planning Proficiency#16624
• Anchoring What Matters: A Dual-Level Learning Framework for Visually-Grounded Multimodal Reasoning#1011762
• Beyond Appearance: Can Multimodal Large Language Models Exploit Vertical Structure for Remote Sensing Natural Scene Understanding?#821879
• Beyond One-Step Accuracy: State-Affine Latent Transition for Reliable Visual Planning#1118307
• MAGIC: Transition-Aware Generation of Navigable Multi-Scene Game Worlds with Large Language Models#363299