Paper deep dive
Rule-Compliant Visual Spatial Planning for Multimodal Large Language Models
Yu Chen, Ting Lei, Yaoyi Li, Jia Cai, Zhecen Wu, Yang Liu
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 94%
Last extracted: 8/21/2026, 4:27:39 AM
Summary
This paper introduces RuleMaze, a benchmark for evaluating Multimodal Large Language Models (MLLMs) on rule-compliant visual spatial planning. It proposes a Language-Logic-Function Hybridization pipeline to automatically generate natural language rules, logical representations, and executable validators. Additionally, it presents Disentangled Multimodal Planning (DMP), a framework that separates perception, execution, and rule verification to improve generalization and interpretability compared to end-to-end baselines.
Entities (8)
Relation Signals (6)
Disentangled Multimodal Planning → separates → perception, execution, and rule verification
confidence 96% · DMP, which separates perception, execution, and rule verification through interpretable reasoning primitives
RuleMaze → evaluates → Multimodal Large Language Models
confidence 95% · RuleMaze, a controllable benchmark in which MLLMs must navigate mazes while obeying natural-language rules
RuleMaze → includes → RegularMaze
confidence 95% · The dataset comprises two complementary scenarios: RegularMaze and QuestMaze.
RuleMaze → includes → QuestMaze
confidence 95% · The dataset comprises two complementary scenarios: RegularMaze and QuestMaze.
Language-Logic-Function Hybridization → generates → executable validators
confidence 94% · Language-Logic-Function Hybridization... automatically generates natural-language rules and translates them into logical representations and executable validators
Disentangled Multimodal Planning → improves → rule compliance
confidence 93% · Experiments demonstrate that DMP substantially improves rule compliance and planning success
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Multimodal large language models (MLLMs) combine linguistic reasoning with visual perception, yet their ability to perform visual spatial planning under explicit or previously unseen rule constraints remains underexplored. This setting requires models to jointly understand spatial layouts, interpret natural-language rules, and plan valid actions accordingly. To address this gap, we introduce RuleMaze, a controllable benchmark in which MLLMs must navigate mazes while obeying natural-language rules of varying complexity. RuleMaze isolates rule-compliant spatial planning by requiring accurate perception, rule interpretation, and constrained action planning. To enable scalable and systematic rule construction, we propose Language-Logic-Function Hybridization, which automatically generates natural-language rules and translates them into logical representations and executable validators, eliminating manual rule engineering. To improve rule following and generalization, we introduce Disentangled Multimodal Planning (DMP), which separates perception, execution, and rule verification through interpretable reasoning primitives. By disentangling these components, DMP facilitates systematic generalization to more complex and previously unseen rules, while providing transparent intermediate planning traces. Experiments demonstrate that DMP substantially improves rule compliance and planning success compared to end-to-end textual planning baselines. Overall, RuleMaze establishes a principled benchmark for studying grounded and interpretable rule-based spatial planning in MLLMs. Code is available at this https URL.
Tags
Links
- Source: https://arxiv.org/abs/2608.20237v1
- Canonical: https://arxiv.org/abs/2608.20237v1
Trouble viewing inline? Open PDF directly →
Full Text
86,786 characters extracted from source content.
Expand or collapse full text
Rule-Compliant Visual Spatial Planning for Multimodal Large Language Models Yu Chen Wangxuan Institute of Computer Technology, Peking University Beijing, China yu_chen@stu.pku.edu.cn Ting Lei Wangxuan Institute of Computer Technology, Peking University Beijing, China ting_lei@pku.edu.cn Yaoyi Li Yinwang Intelligent Technology Co., Ltd Shenzhen, China liyaoyi@yinwang.com Jia Cai Yinwang Intelligent Technology Co., Ltd Shenzhen, China caijianwpu@gmail.com Zhecen Wu Yinwang Intelligent Technology Co., Ltd Shenzhen, China wuzhecen@yinwang.com Yang Liu ∗ Wangxuan Institute of Computer Technology, Peking University Beijing, China yangliu@pku.edu.cn 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 un- derstand spatial layouts, interpret natural-language rules, and plan valid actions accordingly. To address this gap, we introduce Rule- Maze, a controllable benchmark in which MLLMs must navigate mazes while obeying natural-language rules of varying complex- ity. 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 automat- ically generates natural-language rules and translates them into logical representations and executable validators, eliminating man- ual rule engineering. To improve rule following and generalization, we introduce Disentangled Multimodal Planning (DMP), which separates perception, execution, and rule verification through inter- pretable reasoning primitives. By disentangling these components, DMP facilitates systematic generalization to more complex and previously unseen rules, while providing transparent intermedi- ate planning traces. Experiments demonstrate that DMP substan- tially improves rule compliance and planning success compared to end-to-end textual planning baselines. Overall, RuleMaze estab- lishes a principled benchmark for studying grounded and inter- pretable rule-based spatial planning in MLLMs. Code is available at https://github.com/oceanflowlab/RuleMaze. CCS Concepts • Computing methodologies→ Planning and scheduling. ∗ Corresponding author. This work is licensed under a Creative Commons Attribution 4.0 International License. M ’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 Keywords Multimodal Large Language Models, Rule compliance, Visual Spa- tial Planning ACM Reference Format: Yu Chen, Ting Lei, Yaoyi Li, Jia Cai, Zhecen Wu, and Yang Liu. 2026. Rule- Compliant Visual Spatial Planning for Multimodal Large Language Models. In Proceedings of the 34th ACM International Conference on Multimedia (M ’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 incorpo- rating native visual inputs [1,3,23,24,31]. Through large-scale multimodal pretraining, these models have achieved impressive per- formance on tasks such as image captioning [15,21,39], visual ques- tion answering [18,26,41], and general visual reasoning [10,35,42]. Recent works have begun to explore spatial planning and multi- step action reasoning in visual environments, which constitutes a necessary step toward embodied intelligence [19, 20, 30, 34]. However, many of these settings assume unconstrained plan- ning or optimize for a single objective without requiring explicit compliance with externally specified rules. A particularly impor- tant 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 un- der 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 behav- iors. 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 environ- ments presents substantial challenges. First, from a data perspective, real-world scenes rarely provide ground-truth action sequences arXiv:2608.20237v1 [cs.AI] 20 Aug 2026 M ’26, November 10–14, 2026, Rio de Janeiro, Brazil.Yu Chen et al. 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 method- ological perspective, rule-compliant spatial planning requires the tight integration of multiple competencies: accurate visual percep- tion, 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 strug- gle 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 (i) reasoning frameworks that explicitly structure how MLLMs perceive, execute, and verify actions under constraints. Address- ing 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. (a) RuleMaze dataset construction. (b) Disentangled Multimodal Planning (DMP) framework. Figure 1: Overview of the RuleMaze dataset and the proposed Disentangled Multimodal Planning (DMP) framework. To address this gap, we introduce RuleMaze, a controllable bench- mark for evaluating visual spatial planning under explicit natural- language rules. As shown in Fig. 1a, RuleMaze pairs diverse maze- based visual environments with rule specifications that constrain which multi-step action plans are considered valid. To construct scalable rule spaces with controlled complexity, we propose a Language– Logic–Function Hybridization pipeline that transforms free-form rule concepts into executable constraints. Specifically, LLMs are used for Rule Ideation to generate natural-language rules, which are then translated via Logical Formalization into structured logical representations. We further perform Validator Synthesis to automat- ically produce executable functions that verify whether a candidate action trajectory satisfies a given rule, enabling precise and au- tomated 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 li- brary. Each maze is designed to admit multiple feasible routes from the start to the goal. To ensure rules are evaluated only in appli- cable 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 rule- compliant 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 gen- erated mazes with multiple competing routes, (i) systematically constructed rule sets spanning multiple difficulty levels, and (i) 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-to- end training, which entangles perception, execution, and rule rea- soning into a single data-driven process and requires substantial su- pervision to relearn these capabilities whenever rules change, DMP explicitly modularizes rule-constrained problem solving and trains the model to coordinate reusable capabilities. Specifically, DMP de- composes the task into three interpretable components—visual per- ception, action execution, and rule verification—each implemented as a set of callable tools. Given a maze image and a natural-language 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, hav- ing 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 in- voke 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 verifica- tion is externalized through dedicated validator tools automatically synthesized from logical rule representations. These validators are fully replaceable, allowing new or previously unseen rules to be incorporated without retraining the controller. In summary, this work makes the following contributions. (1) We introduce RuleMaze, a controllable benchmark for evaluat- ing spatial planning under explicit natural-language rules, fea- turing diverse maze environments and rule–maze applicability grounded by executable verification tools. (2) We propose a Lan- guage–Logic–Function Hybridization pipeline that enables scalable construction of rule sets with controlled complexity, transforming natural-language rules into logical representations and executable validators without manual rule engineering. (3) We present Disen- tangled Multimodal Planning (DMP), a framework that enhances rule-following behavior in MLLMs by equipping them with explicit perception, execution, and verification tools, enabling multi-step, interpretable reasoning under constraints. (4) Through extensive Rule-Compliant Visual Spatial Planning for Multimodal Large Language ModelsMM ’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. 2 Related work 2.1 Spatial Planning Planning has long been central in AI, traditionally relying on for- mal representations and algorithms [2,13,29], typically in pre- defined 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 tex- tual 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. Bench- marks and methods include VisualCoT [9], which studies chain-of- thought designs for generalizable spatial planning; Ariadne [27], which applies reinforcement learning with verified rewards and a difficulty-aware curriculum; MVoT [20], which integrates tex- tual 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 evaluat- ing 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, ei- ther 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 rea- soning, 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 de- tection, 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 pa- rameters. VisEdit [5] edits intermediate visual representations to enforce updated visual knowledge affecting downstream predic- tions. 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 action space. Moreover, existing methods do not address sequential planning or visually grounded decision-making, whereas our ap- proach enables models to generate action sequences that are both executable and compliant with explicit rules. 3 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 cor- responding to dynamic rule sets. To address this, we present Rule- Maze, a procedurally generated dataset of rule–maze pairs with ex- ecutable validators. Our pipeline uses a Language–Logic–Function framework to generate rules with controlled complexity. In par- allel, 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 tra- jectories 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 ex- pressive 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 sim- ple goal specifications and capture conditional and state-dependent constraints—for example, “Moving into pink zones is strictly prohib- ited” or “If you are standing in an orange zone, your next move must be up.” This stage prioritizes compositional expressiveness, pro- ducing rules that demand non-trivial interpretation and multi-step reasoning. Logical Formalization. Each natural-language rule is then trans- lated into a structured logical representation that formally en- codes 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 representa- tion that supports both semantic analysis and automated execution. Validator Synthesis. Finally, we automatically synthesize an ex- ecutable validator from each logical representation using LLMs. Specifically, the LLM generates a Python function that takes a can- didate trajectory as input and determines whether it complies with the corresponding rule. By decomposing complex rules into sim- pler 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. M ’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 match- ing strategy to associate each rule with mazes where it is mean- ingfully 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 sym- bolic 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; oth- erwise, the maze is discarded for that rule. This matching strat- egy produces rule–maze pairs with clear behavioral constraints, enabling precise evaluation of rule-compliant spatial planning in multimodal agents. 3.3 RuleMaze Dataset Through the Language–Logic–Function Hybridization and the Constraint- based Heuristic Matching procedure described above, we construct RuleMaze, a large-scale dataset of rule–maze pairs for evaluating rule-compliant spatial planning in MLLMs. The dataset comprises two complementary scenarios: RegularMaze and QuestMaze. Figure 3: RuleMaze dataset illustration under both the Regu- larMaze 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, requir- ing models to interpret color-based rules while planning globally optimal paths. QuestMaze. QuestMaze introduces a more semantically rich and challenging environment. The start location is represented by a prince icon, while the goal is a princess or treasure icon. Rules in this scenario involve symbolic item icons (e.g., keys) that may modify planning constraints or affect the goal condition. All other cells are rendered with a grass-textured background. Compared to Rule-Compliant Visual Spatial Planning for Multimodal Large Language ModelsMM ’26, November 10–14, 2026, Rio de Janeiro, Brazil. RegularMaze, QuestMaze requires reasoning over historical state in- formation—such as whether and how many times an item has been collected—as well as handling dynamically changing target con- ditions 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 Quest- Maze 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 diffi- culty. 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 compli- ance—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 in- troduce 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 envi- ronments. Each task instance consists of three components: a maze imageI, a goal instructionG, and a natural-language rule specifi- cationR. The maze imageIdepicts a 2D grid environment with a designated start location, a target location, and rule-relevant cells or semantic objects. The goal instructionGspecifies the goal of the task, e.g., “Navigate from Green to Red”. The rule specification Rdefines 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,whereA=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 inIand (i) satisfy the rule constraints defined byR at every step. 4.2 Disentangled Tool-Based Planning We equip MLLMs with a set of disentangled and interpretable tools, organized into three categories: Perception, Execution, and Ver- ification, as illustrated in Tab. 1. Formally, we define a tool set T=T perc ∪T exec ∪T ver ,where each tool휏 ∈ Tis a callable function with structured inputs and outputs. Perception tools ground the model’s reasoning in the maze image, execution tools deterministi- cally update the visual state by applying movement actions, and verification tools assess rule compliance over the resulting trajec- tories, 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 tran- sitions. Given an action푎 푡 ∈ Aand the current image퐼 푡 , the exe- cution 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 correspond- ing states 푠 0:푡 , verification tools return binary signals: 푏 푟푢푙푒 푡 = 휏 푟푢푙푒 ver (푎 0:푡 ,푠 0:푡 ,푅) and푏 푔표푎푙 푡 = 휏 푔표푎푙 ver (퐼 푡 ), indicating whether the trajectory satisfies the rule constraints or whether the target has been reached. Each rule푅is associated with a dedicated validator 휏 푅 ∈ T 푟푢푙푒 ver , synthesized offline from its logical formalization by an external LLM [31] before controller training and inference. These validators are replaceable and compositional, enabling the frame- work 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 deci- sion 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 traceH 푡 . 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 plan- ning process. Executing푐 푡 invokes a tool휏 푡 ∈ Tand returns an observation표 푡 , which is incorporated intoH 푡+1 for the next rea- soning 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 a 0:푡 as input. The tool evaluates whether a 0:푡 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. M ’26, November 10–14, 2026, Rio de Janeiro, Brazil.Yu Chen et al. Table 1: Summary of disentangled tools in the DMP framework. CategoryTool NameInputsFunction DescriptionOutput Perception LocateStartImage IIdentifies and marks the initial agent positionImage 퐼 0 InspectGridImage 퐼 푡 Identifies semantic symbols at specific cellSymbol 푠 푡 Execution ExecuteMoveImage 퐼 푡 , Action 푎 푡 Updates agent position and visual stateImage 퐼 푡+1 Verification VerifyRule푎 0:푡 , 푠 0:푡 , Rule 푅Checks trajectory compliance with rule 푅Boolean VerifyEndpointImage 퐼 푡 Checks if agent has reached the targetBoolean Figure 4: Overall framework of our proposed Disentangled Multi-Modal Planning. This process continues until a termination condition is met, pro- ducing an action sequence푎=(푎 1 ,푎 2 , . . .,푎 푇 ),such that executing 푎from the start state reaches the target and satisfies all rule con- straints. 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. 5 Experiment 5.1 Experimental Setups Training Objective. For each training example containing푁con- troller interaction rounds (steps of reasoning and tool invocation), we train our controller using the standard cross-entropy loss. Specif- ically, 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: L(휃)=− 퐿 ∑︁ 푖=1 log푃 휃 (푦 푖 | 푦 <푖 ,H 푖 ,퐺,푅,퐼)(1) where휃denotes the model parameters. Training uses pure teacher- forced supervised fine-tuning over the complete reasoning and tool-call traces. Training Setting. We evaluate our framework on two spatial reasoning environments: (1) RegularMaze, which involves con- ventional pathfinding under basic geometric constraints, and (2) QuestMaze, which extends the task by incorporating semantic ob- jects (e.g., keys, hearts). Each environment contains 3,600 training and 400 test samples. Specifically, 100 test instances are associ- ated 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 fine- tune Qwen2.5-VL (3B) [3] for 15 epochs with a batch size of 32. Evaluation Metrics. We adopt two complementary evaluation metrics [34,36] for the selected task: Exact Match (EM), and Preci- sion Rate (PR). Formally, for each test sample푖with ground-truth trajectory length 푛 푖 , we define: EM 푖 = 푛 푖 Ö 푗=1 I( ˆ 푣 푖푗 = 푣 푖푗 ),(2) PR 푖 = 1 푛 푖 푛 푖 ∑︁ 푗=1 " 푗 Ö 푘=1 I( ˆ 푣 푖푘 = 푣 푖푘 ) # ,(3) 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. 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 multi- modal reasoning performance of proprietary models with Gemini 2.5 Pro [7] and Gemini 2.5 Flash with thinking mode. Rule-Compliant Visual Spatial Planning for Multimodal Large Language ModelsMM ’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 Seen RuleUnseen Rule Avg.EasyMediumHardAvg. EM (%)PR (%)EM (%)PR (%)EM (%)PR (%)EM (%)PR (%)EM (%)PR (%) Proprietary Model Gemini 2.5 Pro - Direct48.052.559.063.939.045.939.045.545.651.7 - CoT47.052.264.067.346.051.044.049.351.355.8 Gemini 2.5 Flash (think)37.041.346.051.346.049.630.035.540.645.4 Open-Source Model Qwen 2.5-VL-Instruct-3B - Direct0.06.60.010.70.010.70.013.90.011.7 - CoT 0.03.61.09.90.05.90.04.10.36.6 - SFT † 94.095.378.082.168.072.265.067.670.373.9 DMP-3B † (Ours) 98.098.495.096.788.091.987.089.690.092.7 5.2 Main Results Results on RegularMaze. Tab. 2 presents the performance compar- ison 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 super- vised fine-tuning, DMP improves unseen-rule EM from 70.3% to 90.0%, demonstrating a significant gain in zero-shot rule generaliza- tion. (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 be- comes 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, strug- gle 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 in- creases. 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 plan- ning is particularly beneficial for handling complex compositional constraints. (5) Effect of Text-Based Representations: We further com- pare with textual planning variants in Tab. 4. Direct SFT achieves 65.3% EM under unseen rules, and incorporating explicit represen- tations such as coordinates (69.0%) or ASCII grids (67.0%) provides only marginal improvements. These results indicate that improv- ing 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 com- pliance 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, reach- ing 91.4% EM on seen rules and 88.0% EM on unseen rules. Com- pared to SFT, DMP improves unseen-rule EM from 56.3% to 88.0% (+31.7%), showing strong generalization to novel rules. (2) Com- parison 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 cell- based 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 transi- tions 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, high- lighting 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 nav- igation behavior, it lacks an explicit mechanism to enforce rule constraints during multi-step planning, leading to unnoticed viola- tions. 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 alterna- tive move (“down”). In contrast, DMP successfully generates a valid trajectory that satisfies both the goal and the rule. As shown in the M ’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 Seen RuleUnseen Rule Avg.EasyMediumHardAvg. EM (%)PR (%)EM (%)PR (%)EM (%)PR (%)EM (%)PR (%)EM (%)PR (%) Proprietary Model Gemini 2.5 Pro - Direct71.077.481.086.085.088.971.074.979.083.2 - CoT74.081.586.088.580.083.870.076.878.683.0 Gemini 2.5 Flash (think)56.063.179.084.548.057.440.050.255.664.0 Open-Source Model Qwen 2.5-VL-Instruct-3B - Direct0.05.80.06.50.06.40.010.50.07.8 - CoT 0.02.50.04.20.03.60.03.10.03.6 - SFT † 66.873.665.073.264.070.740.060.156.368.0 DMP-3B † 91.494.392.094.388.090.784.090.188.091.7 Figure 5: Visualization of a test example from RegularMaze comparing visual planning variants. Table 4: Performance of text-based planning variants on Reg- ularMaze under the "Unseen Rule" setting. ModelEM (%)PR (%) Direct SFT65.371.4 w/ Coordinates69.073.7 w/ ASCII67.070.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 viola- tion, 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 per- ception, 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. Experi- ments 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 ModelsMM ’26, November 10–14, 2026, Rio de Janeiro, Brazil. References [1]Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Floren- cia 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 monte- carlo 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 knowl- edge 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, multi- modality, 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 Mod- els. 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 Mul- timodal 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. Open- Vocabulary HOI Detection with Interaction-aware Prompt and Concept Calibra- tion. [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. [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, Jing- Hao 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 conver- gence 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 Korho- nen, 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 Yu Chen Wangxuan Institute of Computer Technology, Peking University Beijing, China yu_chen@stu.pku.edu.cn Ting Lei Wangxuan Institute of Computer Technology, Peking University Beijing, China ting_lei@pku.edu.cn Yaoyi Li Yinwang Intelligent Technology Co., Ltd Shenzhen, China liyaoyi@yinwang.com Jia Cai Yinwang Intelligent Technology Co., Ltd Shenzhen, China caijianwpu@gmail.com Zhecen Wu Yinwang Intelligent Technology Co., Ltd Shenzhen, China wuzhecen@yinwang.com Yang Liu ∗ Wangxuan Institute of Computer Technology, Peking University Beijing, China yangliu@pku.edu.cn A Limitations and Future Work In this work, we focus on controllable grid-based visual environ- ments 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 envi- ronments. 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 inter- pretation, 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 dy- namics, 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 envi- ronments 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 modular- ity 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 verifica- tion framework. Another limitation lies in the current formulation of rule verifica- tion. Our framework relies on externally synthesized validator func- tions 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 verifica- tion mechanisms that can operate under softer or partially specified constraints may further improve the robustness of rule-based plan- ning systems. In addition, the proposed Disentangled Multimodal Planning (DMP) framework introduces iterative tool invocation during in- ference, which may incur additional computational overhead com- pared 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 inter- pretability. Overall, we view RuleMaze and Disentangled Multimodal Plan- ning (DMP) as an initial step toward systematically studying rule- compliant multimodal planning under explicit constraints. By demon- strating that models can coordinate perception, execution, and rule verification through structured interactions, this work opens new possibilities for building multimodal agents that reason un- der externally specified rules. Such capabilities may be particu- larly relevant to domains where perception and decision-making are tightly coupled, including robotics, navigation, and embod- ied 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 can- didate 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 disen- tangled tools consistently improves rule-compliant planning, with M ’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 back- bone 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. MethodEM (%)PR (%) Gemini-2.5-Pro45.651.7 Gemini-2.5-Pro + DMP-P64.067.6 GPT-553.561.3 GPT-5 + DMP-P81.484.1 Qwen2.5-VL-3B0.011.7 Qwen2.5-VL-3B + DMP-P0.017.3 DMP-3B † (Ours)90.092.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 Gemini- 2.5-Pro from 45.6/51.7 to 64.0/67.6, demonstrating that the proposed planning paradigm is applicable across different proprietary back- bones rather than being tied to a particular model architecture. In contrast, the improvement on the smaller Qwen2.5-VL-3B back- bone is limited, suggesting that tool access alone may be insuffi- cient 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 pro- posed 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 transi- tions 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 com- pliance. 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 verifi- cation 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 inter- mediate 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 interac- tion between perception and verification modules contributes to stable planning behavior. Overall, these ablation results suggest that the three tool mod- ules—perception, execution, and verification—play complementary roles in the DMP framework. Among them, execution provides explicit state transitions that support consistent reasoning, verifi- cation introduces rule-aware feedback during planning, and per- ception enables structured interpretation of intermediate states. Re- moving 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 ob- serve that performance improves consistently as the amount of training data increases for both methods. However, a clear per- formance 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 per- formance degradation, whereas DMP maintains relatively stable performance. This observation suggests that the structured percep- tion–execution–verification pipeline provides stronger inductive bias, enabling more reliable generalization even with limited su- pervision. 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 explic- itly 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 in- termediate structural descriptions. This baseline achieves strong performance on seen rules, indicating that the model can learn task-specific navigation patterns under supervised training. How- ever, 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 pro- ducing the action sequence. Examples of these formats are shown Supplementary Material for Rule-Compliant Visual Spatial Planning for Multimodal Large Language ModelsMM ’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. Model Seen RuleUnseen Rule Avg.EasyMediumHardAvg. EM (%)PR (%)EM (%)PR (%)EM (%)PR (%)EM (%)PR (%)EM (%)PR (%) w/o Execution63.063.250.053.534.036.830.033.338.041.2 w/o Verification91.792.594.094.678.079.270.073.480.682.4 w/o Perception + Verification 88.589.391.092.074.076.166.069.577.079.1 DMP (Ours)98.098.495.096.788.091.987.089.690.092.7 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 RuleUnseen Rule Avg.EasyMediumHardAvg. EM (%)PR (%)EM (%)PR (%)EM (%)PR (%)EM (%)PR (%)EM (%)PR (%) Direct SFT (25%)35.045.635.048.729.038.218.031.127.339.3 Direct SFT (50%)67.074.167.075.155.062.643.055.255.064.3 Direct SFT (100%)95.095.372.076.665.069.958.967.765.371.4 DMP (25%)79.084.471.081.165.074.962.071.566.075.8 DMP (50%)95.096.590.092.986.389.484.186.586.889.6 DMP (100%)98.098.495.096.788.091.987.089.690.092.7 in Fig. 1. As shown in Tab. 4, both structured textual variants pro- vide 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 meth- ods and the full DMP framework remains substantial, especially for harder rule settings. Overall, these results suggest that enhancing textual represen- tations 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 natural- language 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. M ’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. Model Seen RuleUnseen Rule Avg.EasyMediumHardAvg. EM (%)PR (%)EM (%)PR (%)EM (%)PR (%)EM (%)PR (%)EM (%)PR (%) Direct SFT95.095.372.076.665.069.958.967.765.371.4 w/ Coordinates97.097.677.082.668.070.962.067.669.073.7 w/ ASCII 95.095.073.078.368.570.759.562.867.070.6 DMP (Ours)98.098.495.096.788.091.987.089.690.092.7 Table 5: Distribution of rules across different semantic types. The categories are not mutually exclusive, as a rule may exhibit multiple semantic properties. Semantic typeDirection-dependentHistory-dependentRequirementProhibition Ratio64.9%31.3%61.3%51.0% Table 6: Average number of logical connectives and con- straint markers per rule. Connective ifmust and ornot cannot Avg. count0.420.550.160.060.170.16 C.1 Semantic Diversity We first categorize the rules according to four high-level seman- tic properties: direction dependence, history dependence, require- ments, 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 reason- ing 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 con- nectives and constraint markers per rule. Conditional and manda- tory constructions are the most frequent: each rule contains, on average, 0.42 occurrences of if and 0.55 occurrences of must. Con- junction, disjunction, negation, and explicit prohibition are also represented, enabling rules to express interactions among multiple predicates and constraints. C.3 Potential Bias in LLM-Generated Rules Although the Language–Logic–Function pipeline supports the scal- able 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 occur- ring rule descriptions. Future extensions could increase linguistic diversity through controlled paraphrasing, human-authored rules, adversarial rewriting, and evaluation on rules collected from real- world instructions. Such extensions would help distinguish gener- alization 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 set- tings. 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 theVerifyRule()tool, which prevents explicit detection of rule violations. This observation suggests that consistent usage of verification plays an important role in maintaining rule compli- ance during multi-step planning. For the remaining cases where verification is present, we analyze the earliest step at which tra- jectory 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 sec- ond 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 move- ment 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 ModelsMM ’26, November 10–14, 2026, Rio de Janeiro, Brazil. Figure 2: Success rate by action length interval on the Regu- larMaze test set. Statistics are categorized by action length intervals ([3-4], [5-6], [7-8]) and further partitioned by diffi- culty levels (Easy, Medium, and Hard). in Fig. 2, success rates gradually decrease as trajectory length in- creases, 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 pri- marily 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. 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. Predicate Reference. Tab. 7 lists the full predicate vocabulary used in CNF logical representations across both scenario types. Logical operators used across all formulas:NOT(negation),AND(conjunc- tion),OR(disjunction),->(material implication), and parentheses for grouping. Table 7: CNF predicate vocabulary. ScenarioPredicateSemanticsExample RegularMaze Zone(t, "col")Cell color at 푡 Zone(t, "blue") Move(t, "dir")Action at 푡 Move(t-1, "up") QuestMaze Seen("item")Item on path Seen("key") Moved("dir")Direction taken NOT Moved("down") Count(s, op, v)Count constr. Count("food", ≥, 3) TargetIs(tg)Goal reached TargetIs("treasure") E.2.2 Stage 2: Automated Rule Compilation. Prompting Templates. Fig. 4 demonstrates the automated transla- tion 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 determin- istic 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 fixedloopPercent=10 is used: after DFS perfect-maze generation, 10% of candidate walls are re- moved to introduce additional solution paths. The hierarchical generation process is organized as follows: Alg. 1 defines the top-level loop governing the entire dataset col- lection. 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 listC; number of parallel processes 푃 (default 10) Output: Maze pool stored on disk 1 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 4GenerateMazeBatch(푐 푘 , 푐 푘+1 , G, 푁, C); 5 Wait for all 푃 processes to complete; M ’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 thevalidate_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 gener- ated 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 com- pleted paths that have already reached the goal, so simple assertions work fine. However, during real-time inference, the system evalu- ates 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 ModelsMM ’26, November 10–14, 2026, Rio de Janeiro, Brazil. Algorithm 2:GenerateMazeBatch(start, end, G, 푁, C) Input : Index range [start, end); cell setG; grid size 푁 ; colour listC Output: JSON batch file + PNG images saved to disk 1 count ← start; 2 while count< end do /* — Step 1: Sample start/end cells — */ 3 (src, dst) ∼ Uniform-Sample(G, 푘=2); /* — Step 2: Generate maze via DFS + loop removal (lp = 10) — */ 4 푀 ← CreateMaze(푁, src, dst) /* see Alg. 3 */ /* — Step 3: Enumerate all solution paths — */ 5 P ← GetAllSolutionPaths(푀); /* — Step 4: Require exactly 2 solution paths — */ 6 if |P|≠ 2 then continue ; /* reject; retry */ 7; /* — Step 5: Paint colored cells — */ 8 푀 ← AddColouredCells(푀, P, C) /* Alg. 4 */ /* — Step 6: Render and persist — */ 9img ← RenderMazeImage(푀); 10Append푀, P, src, dst, img to batch buffer; 11count ← count+ 1; 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 frame- work. 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 local- ization 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 com- puting the CLIP-based cosine similarity between these patches and 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 1 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(푁 푢 ); 8RemoveWall(푀, 푢, 푣); /* open passage between 푢 and 푣 */ 9visited ← visited∪푣; stack.push(푣); 10 else 11stack.pop(); /* — Phase 2: Add loops by removing extra walls (lp = 10) — */ 12 P 0 ← 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 se- mantic content of the agent’s current cell. The tool first decodes the agent’s grid coordinates by localizing the marker pixel clus- ter within the current observation퐼 푡 . Once the coordinates are obtained, it extracts the corresponding cell patch and performs zero-shot classification against a predefined symbol vocabularyL using CLIP embeddings. Depending on the environment,Lrepre- sents 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 es- sential 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 M ’26, November 10–14, 2026, Rio de Janeiro, Brazil.Yu Chen et al. Algorithm 4:AddColouredCells(푀, P, C)— colour in- jection Input : Maze grid 푀 ; set of solution pathsP; colour paletteC Output:푀 with some non-default cells painted a rule-relevant colour 1 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 */ 5 if type= 1 then 6 X ← FindCrossCells(푀, P) ; /* cells shared by ≥ 2 distinct paths */ 7 푘 ∼ Uniform ( 1, . . .,|X| ) ; 8 S ∼ Uniform-Sample(X, 푘); 9 else 10 X ← FindSolutionPathCells(푀, P) ; /* all cells on any solution path */ 11 푘 ∼ Uniform ( 1, . . .,⌊|X|/3⌋ ) ; 12 S ∼ Uniform-Sample(X, 푘); 13 foreach cell푢 ∈S do 14 푀[푢].state← 푐 ∗ .name; 15 푀[푢].color← 푐 ∗ .rgb; 16 return 푀 ; Algorithm 5: LocateStart(퐼 푡 ) Input : Maze image 퐼 푡 Output: Annotated image 퐼 푡+1 with a position marker at the start cell 1 (푔 ℎ ,푔 푤 ,푥 0 ,푦 0 ,푙 푤 ) ← GridDivision(퐼 푡 ) ; // infer cell geometry from image 2 휎 ∗ ← −∞; (푔 ∗ 푥 ,푔 ∗ 푦 ) ← (0, 0) ; 3 foreach cell (푔 푥 ,푔 푦 ) in maze grid do 4patch← CropCell(퐼 푡 , 푔 푥 , 푔 푦 ) ; 5 휎 ← CosineSim CLIP(patch), CLIP(퐼 start_legend ) ; 6if 휎> 휎 ∗ then 7휎 ∗ ← 휎 ; (푔 ∗ 푥 ,푔 ∗ 푦 ) ← (푔 푥 ,푔 푦 ) ; 8 퐼 푡+1 ← DrawMarker(퐼 푡 , 푔 ∗ 푥 , 푔 ∗ 푦 ) ; 9 return 퐼 푡+1 ; 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 obser- vation퐼 푡+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 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. Algorithm 6: InspectGrid(퐼 푡 ) Input : Maze image 퐼 푡 (with position marker at current cell) Output: Semantic symbol 푠 푡 of the current cell 1 (푔 푥 ,푔 푦 ) ← LocateMarker(퐼 푡 ) ; // recover grid coords from marker pixels 2 patch← CropCell(퐼 푡 , 푔 푥 , 푔 푦 ) ; 3 foreach candidate symbol ℓ in symbol vocabulary L do 4 휎 ℓ ← CosineSim CLIP(patch), CLIP(퐼 ℓ ) ; 5 푠 푡 ← arg max ℓ∈L 휎 ℓ ; 6 if 푠 푡 ∈ white, background then 푠 푡 ← normal; 7 return 푠 푡 ; 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 ModelsMM ’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 1 (푔 푥 ,푔 푦 ) ← LocateMarker(퐼 푡 ); // Apply directional offset 2Δ← up:(0,−1), down:(0,+1), left:(−1, 0), right:(+1, 0) ; 3 (푔 ′ 푥 , 푔 ′ 푦 ) ← (푔 푥 , 푔 푦 )+Δ[푎 푡 ]; 4 퐼 푡+1 ← DrawMarker(퐼 푡 , 푔 ′ 푥 , 푔 ′ 푦 ); 5 return 퐼 푡+1 ; 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 휏 ← (푎 푖 , 푠 푖 ) 푡 푖=1 ; // zip action and state histories 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 (푔 푥 ,푔 푦 ) ← LocateMarker(퐼 푡 ); 2 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 In- spectGrid. The tool extracts the semantic symbol from the agent’s current location in퐼 푡 and compares it against the episode’s desig- nated goal symbol푠 goal . For RegularMaze,푠 goal is typically defined asred, whereas in QuestMaze variants, it corresponds to mission- specific entities such asprincessortreasure. Since푠 goal is in- variant throughout a given episode, the tool requires no external environmental state beyond the current visual observation. This self-contained design ensures that endpoint verification remains consistent with the framework’s image-centric interface. F Qualitative Results 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 theVerifyRule() 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 Quest- Maze 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 frame- work remains effective even under more challenging planning con- ditions. 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 tra- jectory correction. M ’26, November 10–14, 2026, Rio de Janeiro, Brazil.Yu Chen et al. 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.