Elamur Research⌕
☰
home / papers / 2026 / GROKE: Vision-Free Navigation Instruction Evaluation via Graph Reasoning on OpenStreetMap

GROKE: Vision-Free Navigation Instruction Evaluation via Graph Reasoning on OpenStreetMap

Paper · 2026 · Farzad Shami, Subhrasankha Dey, Nico Van de Weghe et al.

Summary

Checking whether a navigation instruction actually leads someone to the right place is poorly served by n-gram metrics like BLEU or ROUGE. Those metrics reward shared wording, not correct behaviour. Using trained VLN follower agents as judges has its own problems: it depends on costly, licence-restricted imagery such as Google Street View, and it mixes the agent's perception mistakes with the quality of the language. GROKE removes vision altogether. It is a training-free, LLM-based framework that executes instructions over OpenStreetMap graphs (nodes, edges, POIs) from the Map2Seq dataset. A Sub-instruction Agent splits each instruction into atomic sub-goals and landmark mentions. A Navigator Agent then chooses waypoints step by step on the topological graph. The agent's results (Navigation Error, Success Rate, Oracle Success Rate, SDTW/nDTW) are read as a measure of how navigable the instruction is. The hierarchical agent reduces navigation error by 68.5% relative to heuristic and sampling baselines, and several of its metrics track human judgments. This gives a reproducible, interpretable alternative to vision-based pragmatic evaluation, useful for filtering noisy instruction data and for assistive navigation.

Key points

  • Four map encodings for the LLM were compared: textual narrative, structured JSON graph, grid matrix, and GraphViz-style image. JSON performed best, with Navigation Error 41.3 m and Success Rate 74.0%. Grid and visual-graph formats lagged clearly.
  • In meta-evaluation against human ratings, NE and nDTW were the most reliable proxies. SR and SDTW correlated only moderately (r ≈ 0.29), and OSR was not significant (p > 0.05).
  • An analysis of 492 failed episodes found agent-side errors most frequent, such as overshooting the goal or failing to match POI wording to OSM tags (e.g. "light" vs traffic_signal). Execution-order errors came next, then linguistic errors (visual landmarks missing from OSM), then topological errors (complex junctions).
  • All results come from Gemini-3 Pro. The best "High" thinking setting uses about 41,347 tokens per episode, which makes the method expensive at scale.
  • Limitations: the framework cannot assess instructions that rely on purely visual cues. Planned future work includes distilling the approach into small language models for wearable or assistive devices.

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

🎓Ghent UniversityGhent · Belgium25 works · 2,949 citations🎓Aalto UniversityEspoo · Finland13 works · 648 citations

 Fields, topics and concepts

📚 Shelves 7The field of science this work belongs to (OpenAlex fields).Computer Science · 16,667 worksArtificial Intelligence · 16,194 worksArts and Humanities · 16,039 worksLanguage and Linguistics · 15,891 worksComputer Vision and Pattern Recognition · 2,869 worksEngineering · 133 worksAutomotive Engineering · 6 works

🧭 Topics 1Research subjects and languages the work is about.Reasoning · 1,426 works

Cite

Cite as Farzad Shami, Subhrasankha Dey, Nico Van de Weghe and Henrikki Tenkanen. 2026. GROKE: Vision-Free Navigation Instruction Evaluation via Graph Reasoning on OpenStreetMap. 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.1874

@inproceedings{shami2026groke,
  title = {{GROKE: Vision-Free Navigation Instruction Evaluation via Graph Reasoning on OpenStreetMap}},
  author = {Farzad Shami, Subhrasankha Dey, Nico {Van de Weghe} and Henrikki Tenkanen},
  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.1874},
  url = {https://doi.org/10.18653/v1/2026.acl-long.1874}
}

References

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

  1. Peter Anderson, Angel Chang, Devendra Singh Chaplot, Alexey Dosovitskiy, Saurabh Gupta, Vladlen Koltun, Jana Kosecka, Jitendra Malik, Roozbeh Mottaghi, Manolis Savva, and 1 others. 2018a. On evaluation of embodied navigation agents. arXiv preprint arXiv:1807.06757. — [arXiv:1807.06757](https://arxiv.org/abs/1807.06757) find
  2. Peter Anderson, Qi Wu, Damien Teney, Jake Bruce, Mark Johnson, Niko Sünderhauf, Ian Reid, Stephen Gould, and Anton Van Den Hengel. 2018b. Vision-and-language navigation: Interpreting visually-grounded navigation instructions in real environments. In Proceedings of the IEEE conference on computer vis…
  3. Peter Anderson, Qi Wu, Damien Teney, Jake Bruce, Mark Johnson, Niko Sünderhauf, Ian Reid, Stephen Gould, and Anton van den Hengel. 2018c. Vision-and-language navigation: Interpreting visually-grounded navigation instructions in real environments. In Proceedings of the IEEE Conference on Computer Vis…
  4. Max Bachmann. 2025. rapidfuzz/rapidfuzz: Release 3.13.0. find
  5. Satanjeev Banerjee and Alon Lavie. 2005. Meteor: An automatic metric for mt evaluation with improved correlation with human judgments. In Proceedings of the acl workshop on intrinsic and extrinsic evaluation measures for machine translation and/or summarization, pages 65–72.
  6. Angel Chang, Angela Dai, Thomas Funkhouser, Maciej Halber, Matthias Niessner, Manolis Savva, Shuran Song, Andy Zeng, and Yinda Zhang. 2017. Matterport3d: Learning from rgb-d data in indoor environments. arXiv preprint arXiv:1709.06158. — [arXiv:1709.06158](https://arxiv.org/abs/1709.06158) find
  7. Howard Chen, Alane Suhr, Dipendra Misra, Noah Snavely, and Yoav Artzi. 2019. Touchdown: Natural language navigation and spatial reasoning in visual street environments. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 12538–12547. find
  8. Jiaqi Chen, Bingqian Lin, Ran Xu, Zhenhua Chai, Xiaodan Liang, and Kwan-Yee Wong. 2024. Mapgpt: Map-guided prompting with adaptive path planning for vision-and-language navigation. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pag… find
  9. Lichang Chen, Shiyang Li, Jun Yan, Hai Wang, Kalpa Gunaratna, Vikas Yadav, Zheng Tang, Vijay Srinivasan, Tianyi Zhou, Heng Huang, and 1 others. 2023. Alpagasus: Training a better alpaca with fewer data. In The Twelfth International Conference on Learning Representations.
  10. Yao Cong and Hongwei Mo. 2025. An overview of robot embodied intelligence based on multimodal models: Tasks, models, and system schemes. International Journal of Intelligent Systems, 2025(1):5124400. find
  11. Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2018. BERT: pre-training of deep bidirectional transformers for language understanding. CoRR, abs/1810.04805.
  12. Jiafei Duan, Samson Yu, Hui Li Tan, Hongyuan Zhu, and Cheston Tan. 2022. A survey of embodied ai: From simulators to research tasks. IEEE Transactions on Emerging Topics in Computational Intelligence, 6(2):230–244. find
  13. Bahare Fatemi, Jonathan Halcrow, and Bryan Perozzi. 2024. Talk like a graph: Encoding graphs for large language models. In The Twelfth International Conference on Learning Representations. find
  14. Terrence Fong, David Kaber, Michael Lewis, Jean Scholtz, Alan Schultz, and Aaron Steinfeld. 2004. Common metrics for human-robot interactions. In IEEE 2004 International Conference on Intelligent Robots and Systems, Sendai, Japan. find
  15. Daniel Fried, Ronghang Hu, Volkan Cirik, Anna Rohrbach, Jacob Andreas, Louis-Philippe Morency, Taylor Berg-Kirkpatrick, Kate Saenko, Dan Klein, and Trevor Darrell. 2018. Speaker-follower models for vision-and-language navigation. Advances in neural information processing systems, 31. find
  16. Yunpeng Gao, Zhigang Wang, Linglin Jing, Dong Wang, Xuelong Li, and Bin Zhao. 2024. Aerial vision-and-language navigation via semantic-topo-metric representation guided llm reasoning. arXiv preprint arXiv:2410.08500. — [arXiv:2410.08500](https://arxiv.org/abs/2410.08500) find
  17. Jing Gu, Eliana Stefani, Qi Wu, Jesse Thomason, and Xin Wang. 2022. Vision-and-language navigation: A survey of tasks, methods, and future directions. find
  18. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 7606–7623. find
  19. Gabriel Ilharco, Vihan Jain, Alexander Ku, Eugene Ie, and Jason Baldridge. 2019. General evaluation for instruction conditioned navigation using dynamic time warping. arXiv preprint arXiv:1907.05446. — [arXiv:1907.05446](https://arxiv.org/abs/1907.05446) find
  20. James Inman. 1849. Navigation and nautical astronomy: For the use of British seamen. F. and J. Riving-ton. find
  21. Vihan Jain, Gabriel Magalhaes, Alexander Ku, Ashish Vaswani, Eugene Ie, and Jason Baldridge. 2019. Stay on the path: Instruction fidelity in vision-and-language navigation. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 1862–1872. find
  22. Raphael Schumann and Stefan Riezler. 2022. Analyzing generalization of vision and language navigation to unseen outdoor areas. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 7519– 7532. find
  23. Raphael Schumann, Wanrong Zhu, Weixi Feng, Tsu-Jui Fu, Stefan Riezler, and William Yang Wang. 2024. Velma: Verbalization embodiment of llm agents for vision and language navigation in street view. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 18924–18933. find
  24. Stefanie Tellex, Nakul Gopalan, Hadas Kress-Gazit, and Cynthia Matuszek. 2020. Robots that use language. Annual Review of Control, Robotics, and Autonomous Systems, 3(1):25–55. find
  25. Jacob Krantz, Erik Wijmans, Arjun Majumdar, Dhruv Batra, and Stefan Lee. 2020. Beyond the nav-graph: Vision-and-language navigation in continuous environments. In European Conference on Computer Vision, pages 104–120. find
  26. Erik F. Tjong Kim Sang and Fien De Meulder. 2003. Introduction to the CoNLL-2003 shared task: Language-independent named entity recognition. In Proceedings of the Seventh Conference on Natural Language Learning at HLT-NAACL 2003, pages 142– 147.
  27. Alexander Ku, Peter Anderson, Roma Patel, Eugene Ie, and Jason Baldridge. 2020. Room-across-room: Multilingual vision-and-language navigation with dense spatiotemporal grounding. arXiv preprint arXiv:2010.07954. find
  28. Ramakrishna Vedantam, C Lawrence Zitnick, and Devi Parikh. 2015. Cider: Consensus-based image description evaluation. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 4566–4575.
  29. Chin-Yew Lin. 2004. Rouge: A package for automatic evaluation of summaries. In Text summarization branches out, pages 74–81.
  30. Khoa Vo, Taisei Hanyu, Yuki Ikebe, Trong Thang Pham, Nhat Chung, Minh Nhat Vu, Duy Nguyen Ho Minh, Anh Nguyen, Anthony Gunderman, Chase Rainwater, and 1 others. 2025. Clutter-resistant vision-language-action models through object-centric and geometry grounding. arXiv preprint arXiv:2512.22519. — [arXiv:2512.22519](https://arxiv.org/abs/2512.22519) find
  31. Shubo Liu, Hongsheng Zhang, Yuankai Qi, Peng Wang, Yanning Zhang, and Qi Wu. 2023. Aerialvln: Vision-and-language navigation for uavs. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 15384–15394. find
  32. Feipeng Ma, Yizhou Zhou, Yueyi Zhang, Siying Wu, Zheyu Zhang, Zilong He, Fengyun Rao, and Xiaoyan Sun. 2024. Task navigator: Decomposing complex tasks for multimodal large language models. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) Workshops, pages 22… find
  33. Harsh Mehta, Yoav Artzi, Jason Baldridge, Eugene Ie, and Piotr Mirowski. 2020. Retouchdown: Adding touchdown to streetlearn as a shareable resource for language grounding tasks in street view. arXiv preprint arXiv:2001.03671. — [arXiv:2001.03671](https://arxiv.org/abs/2001.03671) find
  34. Xin Wang, Qiuyuan Huang, Asli Celikyilmaz, Jianfeng Gao, Dinghan Shen, Yuan-Fang Wang, William Yang Wang, and Lei Zhang. 2019. Reinforced cross-modal matching and self-supervised imitation learning for vision-language navigation. In Proceedings of the IEEE/CVF conference on computer vision and patte… find
  35. Hui Wei, Zihao Zhang, Shenghua He, Tian Xia, Shijia Pan, and Fei Liu. 2025. PlanGenLLMs: A modern survey of LLM planning capabilities. In Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 19497–19521, Vienna, Austria. Association f…
  36. Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. 2002. Bleu: a method for automatic evaluation of machine translation. In Proceedings of the 40th annual meeting of the Association for Computational Linguistics, pages 311–318.
  37. Fujing Xie and Sören Schwertfeger. 2024. Empowering robot path planning with large language models: os-mag map topology & hierarchy comprehension with llms. In 2024 IEEE International Conference on Robotics and Biomimetics (ROBIO), pages 707–712. IEEE. find
  38. Raphael Schumann and Stefan Riezler. 2021. Generating landmark navigation instructions from maps as a graph-to-text problem. Association for Computational Linguistics. find
  39. Urchade Zaratiana, Nadi Tomeh, Pierre Holat, and Thierry Charnois. 2024. GLiNER: Generalist model for named entity recognition using bidirectional transformer. In Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technol…
  40. Jianan Zhao, Le Zhuo, Yikang Shen, Meng Qu, Kai Liu, Michael M. Bronstein, Zhaocheng Zhu, and Jian Tang. 2024. Graphtext: Graph reasoning in text space. In Adaptive Foundation Models: Evolving AI for Personalized and Efficient Learning. find
  41. Ming Zhao, Peter Anderson, Vihan Jain, Su Wang, Alexander Ku, Jason Baldridge, and Eugene Ie. 2021. On the evaluation of vision-and-language navigation instructions. In Proceedings of the 16th Conference of the European Chapter of the Association for Computational Linguistics: Main Volume, pages 130… find
  42. Gengze Zhou, Yicong Hong, and Qi Wu. 2024. Navgpt: Explicit reasoning in vision-and-language navigation with large language models. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 7641–7649. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/shami-2026-groke-vision-free-navigation-instruction/