Constructing coherent spatial memory in LLM agents through graph rectification

Researchers introduce LLM-MapRepair, a framework enabling large language models to incrementally construct and repair topological navigation graphs from stepwise observations. The system addresses limitations of context-dependent spatial reasoning in LLMs by detecting and correcting structural inconsistencies, achieving 94.3% node recall and 88.2% edge recall on benchmark evaluations.

LLM-MapRepair represents a meaningful advancement in spatial reasoning for language models, tackling a fundamental limitation in how LLMs process and maintain spatial information. Traditional approaches rely on context windows to infer layouts from descriptions, but this breaks down in complex environments. The research introduces a systematic solution through graph-based representation and incremental construction, enabling models to build coherent mental maps of spaces without relying solely on immediate context.

The framework's technical contributions—Version Control for graph construction and Edge Impact Scoring for repair prioritization—demonstrate practical engineering solutions to common graph construction problems. The evaluation across multiple LLM vendors (OpenAI, Anthropic, Google) and diverse environments (synthetic, procedurally-generated, literary texts) provides credibility and broad applicability. The 55.8 percentage-point improvement in edge recall over direct mapping is substantial.

However, the acknowledged limitation deserves attention: predicted node and edge counts run roughly 4x higher than ground truth, reflecting a discretization-driven over-generation trade-off. This suggests the framework trades precision for recall, potentially creating bloated graphs that require post-processing. For practical deployment in resource-constrained environments or applications requiring exact spatial fidelity, this over-generation could limit adoption.

The research signals growing maturity in LLM spatial reasoning capabilities, important for applications requiring embodied AI or complex navigation tasks. Future work should focus on balancing recall improvements with reducing spurious node/edge generation, and exploring whether multi-stage filtering or LLM-driven pruning can address the over-generation problem while maintaining the substantial recall gains.

• →LLM-MapRepair achieves 88.2% edge recall, a 55.8 percentage-point improvement over direct LLM mapping on benchmark tasks
• →The framework uses Version Control mechanisms and Edge Impact Scoring to detect and prioritize correction of spatial graph inconsistencies
• →Generated graphs contain approximately 4x more nodes and edges than ground truth, indicating a significant over-generation trade-off
• →Evaluation spans multiple LLM vendors and environments including synthetic games, procedurally-generated text, and classical literature
• →The approach enables incremental spatial reasoning without relying on context windows, scaling to larger and more complex environments