Technical Summary: Lost in Aggregation: A Multi-Scale Diagnostic Benchmark for LLM Spatial Navigation

Problem Statement

Large Language Models (LLMs) are increasingly deployed as planners in spatial tasks such as navigation and route planning. However, they exhibit brittleness in sequential spatial reasoning, often failing to maintain a coherent spatial state over long horizons. While it is established that LLMs fail at navigation, the specific locus of failure within the spatial-cognition pipeline remains unclear. It is unknown whether deficits stem from an inability to perceive local geometry, read topological structures at branch points, maintain a global heading, or integrate these competencies across scales during long sequential plans. Aggregate success rates are insufficient to distinguish between these hypotheses, as they imply fundamentally different remediation strategies (e.g., better perception vs. better topological reasoning vs. architectural delegation).

Methodology

The authors introduce a multi-scale diagnostic benchmark designed to decompose maze navigation into three cognitive levels derived from human spatial cognition:

1. Fine: Local passability (which adjacent cells are open).
2. Meso: Topological mapping (choosing the correct branch at a junction and recognizing dead ends).
3. Macro: Global goal orientation (maintaining the correct heading toward the destination).

The benchmark consists of 1,050 topology-annotated mazes generated using depth-first-search and randomized Prim algorithms. These mazes are trees (acyclic), ensuring a unique path between any two points, which removes shortest-path optimization as a confounding variable. The mazes span seven effective sizes (3×3 to 30×30) and three difficulty tiers.

The evaluation is organized into three modules addressing three research questions (RQs):

• Module 1 (Input Acquisition): Compares four input formats (Natural Language Words, Structured Coordinates, ASCII Map, Rendered Image) to determine which best supports LLM navigation.
• Module 2 (Multi-Scale Representation): Probes each cognitive level in isolation via single-question multiple-choice tasks and compares these results against end-to-end one-shot navigation performance. It also employs a "multi-hot first-error" analysis to localize the specific step where a trajectory fails. Non-spatial controls (e.g., counting open cells) are included to rule out generic long-context degradation.
• Module 3 (Hierarchical Route Planning): Tests delegation regimes where a deterministic walker handles low-level execution (corridor traversal, dead-end retreat), and the LLM is queried only at junctions. This compares a "Topology-blind" regime (generic prompts) against a "Topology-aided" regime (explicit cell-type prompts and algorithmic retreat).

Three instruction-tuned chat models (GPT-4o, DeepSeek-V3, Llama-3.3-70B) were evaluated using chain-of-thought prompting with a fixed temperature of 0.

Key Results

1. Input Format (RQ1)

Structured coordinate text is the most navigable input format, significantly outperforming rendered images and ASCII maps. For the strongest model (DeepSeek-V3), coordinate input achieved a 70% success rate on small mazes, compared to 5% for rendered images. Crucially, even when end-to-end success rates collapsed to near zero, the Valid-Move Ratio (VMR) remained high (>0.62), indicating that models can generate locally legal moves but fail at global path assembly.

2. The Aggregation Deficit (RQ2)

The primary finding is that scaling failure is a failure of cross-scale aggregation, not a deficit in individual perceptual or directional competencies.

• Isolated Competence: When probed in isolation, models maintained high accuracy on Fine (32–56%), Meso (50–64%), and Macro (42–67%) tasks even at large sizes (30×30), far exceeding chance levels.
• End-to-End Collapse: One-shot navigation success collapsed to near zero by 10×10 for all models.
• The Gap: The coupled Meso×Macro probe (requiring both topological and directional reasoning) decayed faster than isolated components but still outperformed end-to-end navigation.
• First-Error Analysis: Failures were localized to Meso junction choices (59%) and Fine perception (39%), while global direction (Macro) was rarely the first point of failure (1%).
• Aggregation Cost: The gap between isolated junction accuracy and in-trajectory junction accuracy widened with maze size (e.g., a 28-point drop at 30×30), proving that the cost is not merely multiplicative compounding of errors but a degradation in the model's ability to bind decisions over a long sequence.

3. Delegation and Hybrid Agents (RQ3)

Delegating low-level control to a deterministic algorithm significantly improves performance, but does not eliminate the scaling wall.

• Topology-Aided Delegation: When the algorithm handled dead-end retreat and the LLM was prompted with explicit cell-type information at junctions, GPT-4o's success rate jumped by up to 92 points at mid-sizes (e.g., from 2% to 94% at 7×7).
• Limitations: This improvement was contingent on explicit topological framing; a "Topology-blind" regime yielded negligible gains. Furthermore, even with delegation, performance collapsed again by 30×30, indicating that while delegation extends the navigable horizon, it does not remove the fundamental scaling barrier for long sequential plans.

Significance and Claims

The paper claims to provide a granular diagnostic instrument that shifts the understanding of LLM spatial failure from a general inability to "reason" to a specific inability to integrate individually available competencies across a long sequential plan.

• Reframing Failure: The authors argue that LLMs do not necessarily lack local perception or global direction; rather, they fail to sustain the binding of these signals step-by-step. The "Macro" level (global heading) is surprisingly durable in isolation but is repeatedly undone by Meso and Fine errors in sequential execution.
• Architectural Implications: For hybrid GIS and wayfinding agents, the paper suggests a specific division of labor: algorithms should own Fine execution and dead-end retreat, while LLMs should serve as junction-level decision-makers. However, this role requires explicit topological framing in the prompt to be effective.
• Input Modality: The results suggest that for current LLMs, spatial structure is best processed as symbolic, relational data (coordinates) rather than pictorial representations.

The authors explicitly note limitations, including the use of tree topologies (no cycles), the focus on English-only chat models, and the heuristic nature of the first-error tagging. They position the benchmark as a reusable tool for future work to localize binding bottlenecks more finely, particularly in cyclic or metric-weighted environments.