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

arXiv: https://arxiv.org/abs/2601.07375 · HTML: https://mlsanity.com/paper/2601.07375/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in Spatial and embodied reasoning, one of 17 directions in LLM reasoning.
- Builds on 8 of its 41 references that are in the map.
- First posted on arXiv 12 Jan 2026.

## Placed in

- LLM reasoning / [Spatial and embodied reasoning](https://mlsanity.com/lr/spatial-and-embodied-reasoning/)

## Builds on (most cited first, 8 of 8)

- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Matterport3D: Learning from RGB-D Data in Indoor Environments](https://mlsanity.com/paper/1709.06158/) (2017)
- [On Evaluation of Embodied Navigation Agents](https://mlsanity.com/paper/1807.06757/) (2018)
- [Room-Across-Room: Multilingual Vision-and-Language Navigation with Dense Spatiotemporal Grounding](https://mlsanity.com/paper/2010.07954/) (2020)
- [General Evaluation for Instruction Conditioned Navigation using Dynamic Time Warping](https://mlsanity.com/paper/1907.05446/) (2019)
- [Exploring Spatial Representation to Enhance LLM Reasoning in Aerial Vision-Language Navigation](https://mlsanity.com/paper/2410.08500/) (2024)
- [Retouchdown: Adding Touchdown to StreetLearn as a Shareable Resource for Language Grounding Tasks in Street View](https://mlsanity.com/paper/2001.03671/) (2020)
- [Clutter-Robust Vision-Language-Action Models through Object-Centric and Geometry Grounding](https://mlsanity.com/paper/2512.22519/) (2025)

## Built on by (most cited first, 1 of 1)

- [Guide Me Out: A Framework to Benchmark VLM Operators Communication in Crisis Scenarios](https://mlsanity.com/paper/2606.09428/) (2026)

## Abstract (arXiv)

The evaluation of navigation instructions remains a persistent challenge in Vision-and-Language Navigation (VLN) research. Traditional reference-based metrics such as BLEU and ROUGE fail to capture the functional utility of spatial directives, specifically whether an instruction successfully guides a navigator to the intended destination. Although existing VLN agents could serve as evaluators, their reliance on high-fidelity visual simulators introduces licensing constraints and computational costs, and perception errors further confound linguistic quality assessment. This paper introduces GROKE(Graph-based Reasoning over OSM Knowledge for instruction Evaluation), a vision-free training-free hierarchical LLM-based framework for evaluating navigation instructions using OpenStreetMap data. Through systematic ablation studies, we demonstrate that structured JSON and textual formats for spatial information substantially outperform grid-based and visual graph representations. Our hierarchical architecture combines sub-instruction planning with topological graph navigation, reducing navigation error by 68.5% compared to heuristic and sampling baselines on the Map2Seq dataset. The agent's execution success, trajectory fidelity, and decision patterns serve as proxy metrics for functional navigability given OSM-visible landmarks and topology, establishing a scalable and interpretable evaluation paradigm without visual dependencies. Code and data are available at https://anonymous.4open.science/r/groke.