Elamur Research⌕
☰
home / papers / 2026 / Constructing coherent spatial memory in LLM agents through graph rectification

Constructing coherent spatial memory in LLM agents through graph rectification

Paper · 2026 · Puzhen Zhang, Xuyang Chen, Yu Feng et al.

Summary

LLMs can reason about a map described in a single prompt, but this breaks down for large environments that exceed the context window. The authors instead have an LLM agent build a topological navigation graph step by step from textual observations. They then repair the errors that accumulate along the way. Their framework, LLM-MapRepair, works in three stages. It first flags naming, directional and topological conflicts using symbolic rules. It then narrows down suspect edges via LCA-based filtering and an Edge Impact Score, which weighs reachability, usage frequency and conflict propagation. Finally, it consults a Version Control log that stores each graph edit together with the observation and reasoning behind it, so the LLM can trace and undo faulty early decisions. The authors also release a cleaned MANGO variant without non-topological actions or built-in conflicts. On Dream of the Red Chamber, edge recall rises sharply over plain incremental mapping. This shows that history-aware, symbolic error control makes LLM-built spatial memory much more reliable.

Key points

  • Using GPT-4.1 on the setting from Dream of the Red Chamber's Chapters 16–17, MapRepair achieves 94.3% node recall (+8.6 pp) and 88.2% edge recall (+55.8 pp) relative to direct LLM incremental mapping.
  • Combining Version Control with Edge Impact ranking yields 54.88% repair accuracy, a 22.8% relative gain over ranking alone, with a 68.91% repair rate. An unguided GPT-4o baseline manages only 5.77% accuracy and a 21.85% repair rate, averaging 9.52 loops per attempt.
  • In LLM-free tests on synthetic graphs, LCA filtering shrinks the candidate edge set by 22.7% on average and by up to 75% for directional conflicts. The Edge Impact Score matches true cascade potential (Spearman ρ = 1.0), and priority-based inspection finds critical errors 2.3× faster.
  • The cleaned MANGO benchmark is released as a topologically consistent resource for evaluating LLM mapping.
  • Limitations include discretized directions, no detection of semantic conflicts, and blindness to consistent perception errors.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓Technical University of MunichMunich · Germany55 works · 48,474 citations

 Fields, topics and concepts

📚 Shelves 5The field of science this work belongs to (OpenAlex fields).Computer Science · 16,667 worksArtificial Intelligence · 16,194 worksEngineering · 133 worksAutomotive Engineering · 6 worksAerospace Engineering · 1 work

Cite

Cite as Puzhen Zhang, Xuyang Chen, Yu Feng, Yuhan Jiang and Liqiu Meng. 2026. Constructing coherent spatial memory in LLM agents through graph rectification. Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers).

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.18653/v1/2026.acl-long.2222

@inproceedings{zhang2026constructing,
  title = {{Constructing coherent spatial memory in LLM agents through graph rectification}},
  author = {Puzhen Zhang, Xuyang Chen, Yu Feng, Yuhan Jiang and Liqiu Meng},
  booktitle = {Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)},
  year = {2026},
  doi = {10.18653/v1/2026.acl-long.2222},
  url = {https://doi.org/10.18653/v1/2026.acl-long.2222}
}

References

21 references, 5 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Allan Borodin, Gareth O. Roberts, Jeffrey S. Rosenthal, and Panayiotis Tsaparas. 2005. Link analysis ranking: Algorithms, theory, and experiments. ACM Transactions on Internet Technology (TOIT), 5(1):231–297. find
  2. Sergey Brin and Lawrence Page. 1998. The anatomy of a large-scale hypertextual web search engine. Computer Networks and ISDN Systems, 30(1-7):107–117.
  3. Mark Cummins and Paul Newman. 2008. FAB-MAP: Probabilistic localization and mapping in the space of appearance. The International Journal of Robotics Research, 27(6):647–665. find
  4. Gia Tuan Dao and Dinh Bach Vu. 2025. AlphaMaze: Enhancing large language models’ spatial intelligence via GRPO. arXiv preprint arXiv:2502.14669. — [arXiv:2502.14669](https://arxiv.org/abs/2502.14669) find
  5. Peng Ding, Jiading Fang, Peng Li, Kangrui Wang, Xiaochen Zhou, Mo Yu, Jing Li, Matthew R. Walter, and Hongyuan Mei. 2024. MANGO: A benchmark for evaluating mapping and navigation abilities of large language models. Preprint, arXiv:2403.19913. — [arXiv:2403.19913](https://arxiv.org/abs/2403.19913) find
  6. Dorian Gálvez-López and Juan D Tardos. 2012. Bags of binary words for fast place recognition in image sequences. IEEE Transactions on Robotics, 28(5):1188–1197. find
  7. Jey Puget Gil, Emmanuel Coquery, John Samuel, and Gilles Gesquiere. 2024. ConVer-G: Concurrent versioning of knowledge graphs. Preprint, arXiv:2409.04499. — [arXiv:2409.04499](https://arxiv.org/abs/2409.04499) find
  8. Jim Gray and Andreas Reuter. 1993. Transaction processing: Concepts and techniques. In Morgan Kaufmann. find
  9. Qiao Gu, Ali Kuwajerwala, Sacha Morin, Krishna Murthy Jatavallabhula, Bipasha Sen, Aditya Agarwal, Corban Rivera, William Paul, Kirsty Ellis, Rama Chellappa, and 1 others. 2024. Concept-Graphs: Open-vocabulary 3D scene graphs for perception and planning. In 2024 IEEE International Conference on Robo… find
  10. Simeng Han, Hailey Schoelkopf, Yilun Zhao, Zhenting Qi, Martin Riddell, Wenfei Zhou, James Coady, David Peng, Yujie Qiao, Luke Benson, Lucy Sun, Alexander Wardle-Solano, Hannah Szabo, Ekaterina Zubova, Matthew Burtell, Jonathan Fan, Yixin Liu, Brian Wong, Malcolm Sailor, and 11 others. 2024. FOLIO:…
  11. Matthew Hausknecht, Prithviraj Ammanabrolu, Côté Marc-Alexandre, and Yuan Xingdi. 2019. Interactive fiction games: A colossal adventure. CoRR, abs/1909.05398. — [arXiv:1909.05398](https://arxiv.org/abs/1909.05398) find
  12. Wolfgang Hess, Damon Kohler, Holger Rapp, and Daniel Andor. 2016. Real-time loop closure in 2D LI-DAR SLAM. In IEEE International Conference on Robotics and Automation (ICRA), pages 1271–1278. find
  13. Feng Lu and Evangelos Milios. 1997. Globally consistent range scan alignment for environment mapping. Autonomous robots, 4:333–349. find
  14. Yuxing Lu and Jinzhuo Wang. 2025. KARMA: Leveraging multi-agent LLMs for automated knowledge graph enrichment. Preprint, arXiv:2502.06472. — [arXiv:2502.06472](https://arxiv.org/abs/2502.06472) find
  15. Clara Meister, Ryan Cotterell, and Tim Vieira. 2020. If beam search is the answer, what was the question? In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP).
  16. Raul Mur-Artal, Jose Maria Martinez Montiel, and Juan D Tardos. 2015. ORB-SLAM: a versatile and accurate monocular SLAM system. IEEE Transactions on Robotics, 31(5):1147–1163. find
  17. Theo X. Olausson, Alex Gu, Benjamin Lipkin, Cedegao E. Zhang, Armando Solar-Lezama, Joshua B. Tenenbaum, and Roger Levy. 2023. LINC: A neurosymbolic approach for logical reasoning by combining language models with first-order logic provers. In Proceedings of the 2023 Conference on Empirical Methods…
  18. Liangming Pan, Alon Albalak, Xinyi Wang, and William Yang Wang. 2023. Logic-LM: Empowering large language models with symbolic solvers for faithful logical reasoning. In Findings of the Association for Computational Linguistics: EMNLP 2023.
  19. Ira Pohl. 1970. Heuristic search viewed as path finding in a graph. Artificial Intelligence, 1(3-4):193–204. find
  20. Anlong Zhang and Jianmin Ji. 2025. Research on navigation methods based on LLMs. arXiv preprint arXiv:2504.15600. — [arXiv:2504.15600](https://arxiv.org/abs/2504.15600) find
  21. Ningyu Zhang, Zekun Xi, Yujie Luo, Peng Wang, Bozhong Tian, Yunzhi Yao, Jintian Zhang, Shumin Deng, Mengshu Sun, Lei Liang, Zhiqiang Zhang, Xiaowei Zhu, Jun Zhou, and Huajun Chen. 2024. OneEdit: A neural-symbolic collaboratively knowledge editing system. Preprint, arXiv:2409.07497. — [arXiv:2409.07497](https://arxiv.org/abs/2409.07497) find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/zhang-2026-constructing-coherent-spatial-memory-llm/