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

1. Problem Statement

The paper addresses a critical gap in evaluating Multimodal Large Language Models (MLLMs): Does high accuracy on visual spatial tasks imply genuine human-like spatial understanding, or is it the result of inefficient, brute-force search mechanisms?

While MLLMs have shown impressive performance on vision-language benchmarks, there is a suspicion that they may not possess true spatial reasoning capabilities. Instead, they might be translating visual inputs into text representations and then performing serial, token-level enumeration (essentially a Breadth-First Search or BFS in prose) to find solutions. This paper investigates whether models "see" and "plan" like humans or simply "brute-force" solutions within their token budgets.

2. Methodology: MAZEBENCH

To isolate spatial reasoning from other cognitive skills, the authors introduced MAZEBENCH, a novel benchmark with the following characteristics:

• Dataset: 110 procedurally generated maze images organized into nine controlled groups:
  • Diagnostic: Empty/near-empty grids to test basic visual parsing.
  • Grid Scale: Varying sizes (5×5 to 13×13) to test spatial scaling.
  • Wall Density & Traps: Varying obstacle complexity and hazard tiles.
  • Unreachable: Mazes with no solution to test false-positive rates.
  • Ultra-Hard: 20×20 grids with high density and long paths (28–42 steps) to test token budget limits.
• Task Formulation: Models must output a JSON object containing grid dimensions, reachability status, shortest path length, and the exact sequence of moves (U/D/L/R). No partial credit is given; the path must be exact.
• Experimental Controls:
  • Reasoning Budgets: The study systematically varies reasoning effort (e.g., OpenAI's reasoning_effort, Anthropic's adaptive thinking) to observe performance scaling.
  • Token Efficiency: The total tokens consumed (thinking + output) per solve is tracked as a proxy for the strategy used.
  • Ablation Studies: Models were tested on images vs. direct text-grid inputs to isolate visual extraction failures from reasoning failures.
• Models Evaluated: 16 configurations across four providers (OpenAI, Anthropic, Google, Alibaba), including GPT-5.4, Claude Opus/Sonnet/Haiku, Gemini 3.1 Pro/Flash, and Qwen 3.5.

3. Key Findings & Results

A. High Accuracy Masks Brute-Force Strategies

• Performance vs. Mechanism: Top models like GPT-5.4 (91% solve rate) and Gemini 3.1 Pro (79%) achieve high scores, but qualitative analysis reveals they do not use spatial planning. Instead, they convert the image to a text grid and perform serial path enumeration (BFS in natural language).
• Token Inefficiency: Solving a maze via this method is computationally expensive. GPT-5.4 consumes ~1,710 tokens per solve, while Gemini 3 Flash uses ~15,171 tokens. Humans solve the same tasks in seconds with negligible cognitive load.
• Token Budget Limits: On "Ultra-Hard" 20×20 mazes, GPT-5.4's accuracy drops to 30%. The model fails not because it cannot see the maze, but because the path length exceeds its token budget, causing it to run out of "thinking space" before finding the solution.

B. The Two-Stage Failure Mode

The authors identify a universal two-stage strategy across all models:

1. Image-to-Grid Translation: Converting pixels to a text matrix.
2. Serial Path Enumeration: Step-by-step text-based search.

• Vision is the Bottleneck for Some: Claude models (Opus, Sonnet, Haiku) score only 2–6% regardless of model size or reasoning effort. Analysis shows they frequently hallucinate grid dimensions (e.g., identifying an 8×8 grid as 10×10) and wall positions. Their reasoning engine is competent, but it operates on a "hallucinated" grid, rendering the search futile.
• Reasoning is the Bottleneck for Others: Models with better vision (GPT-5, Gemini) still fail on complex tasks because their search strategy is linear and token-bound, not holistic.

C. Model Size Does Not Buy Spatial Reasoning

• Scale Invariance: Increasing model size within the Claude family (Haiku → Sonnet → Opus) yields no improvement in solve rates (all remain at 2–6%). This suggests that spatial planning is not an emergent property of scale in current architectures.
• Hidden Reasoning: Gemini models outperform Claude because they perform hidden internal reasoning (visible via API tokens) by default, allowing them to execute more extensive brute-force searches without user-configurable toggles.

D. Ablation Study: Vision vs. Reasoning

• Text-Grid Ablation: When Claude Sonnet 4.6 was provided with the correct text grid (bypassing the image encoder) instead of the image, its solve rate jumped from 6% to 80%.
• Conclusion: This proves that Claude's reasoning engine is competitive with top-tier models; its failure is entirely due to poor visual extraction. Conversely, even with perfect vision, models still rely on inefficient token enumeration.

E. Instruction Compliance Failure

When explicitly instructed not to convert the image to a grid or use graph search algorithms, models (including GPT-5.4 and Claude) silently violate these constraints. They revert to the grid-based enumeration strategy, indicating a lack of true visual intuition and an inability to follow negative constraints regarding their internal reasoning process.

4. Significance and Implications

• Benchmark Misleadingness: High accuracy scores on visual planning tasks are misleading indicators of human-like spatial understanding. A model can achieve 90% accuracy while using a fundamentally different, far more costly, and brittle cognitive strategy than a human.
• Evaluation Paradigm Shift: The paper argues that future evaluations must move beyond simple "correctness" metrics. Researchers must track:
  • Strategy: How the model solves the problem (e.g., via token traces).
  • Efficiency: Tokens per solve.
  • Failure Modes: Whether failure is due to vision (parsing) or reasoning (planning).
• Limitations of Current MLLMs: Current models lack genuine spatial perception. They rely on "lossy" conversion of vision to language, followed by expensive text-based search. They do not "trace" paths visually; they "enumerate" them linguistically.
• Future Directions: The paper calls for benchmarks that distinguish between visual extraction and spatial reasoning, and for the development of models that can perform spatial planning without resorting to token-level brute force.

Conclusion

MAZEBENCH demonstrates that while MLLMs can solve visual mazes, they do so through brute-force token enumeration rather than genuine spatial planning. High accuracy is often a result of sufficient compute budgets (tokens) to exhaustively search a text-converted grid, not evidence of human-like visual intuition. This challenges the assumption that scaling models or increasing reasoning budgets will naturally lead to human-level spatial reasoning.