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

AI summary

Overview

• Research area: Natural Language Processing (NLP), specifically Vision-and-Language Navigation (VLN), embodied AI, and agentic evaluation of navigation instructions using OpenStreetMap (OSM) data.
• Technical level: Advanced. The paper assumes familiarity with VLN benchmarks, LLM-based agents, graph structures, spatial encoding formats, and statistical correlation analysis.
• Scope in one sentence: The paper introduces GROKE, a training-free, vision-free hierarchical LLM framework that evaluates the navigability of natural-language navigation instructions by having an agent execute them over OpenStreetMap graph data rather than photorealistic imagery.

What This Paper Is About

Traditional metrics for navigation instructions, such as BLEU, ROUGE, METEOR, and CIDEr, compare the words of an instruction against a reference text and therefore cannot tell whether an instruction actually gets someone to the right place. The usual fix is to let a "follower" agent try to execute the instruction in a visual simulator, but that requires costly and license-restricted imagery, and visual perception failures get confused with bad instruction wording. GROKE instead asks "how navigable is this instruction?" by running a hierarchical LLM agent over structured OpenStreetMap data and treating the agent's execution success, trajectory fidelity, and decision patterns as proxy scores for instruction quality.

Key Contributions

1. A systematic comparison of four spatial representation formats for LLM spatial reasoning: textual narratives, structured JSON graphs, grid-based matrices, and GraphViz-style visualizations. The ablation studies show structured JSON substantially outperforms grid-based and visual graph representations, achieving a Navigation Error of 41.3 m and a Success Rate of 74.0%.
2. The GROKE framework itself, a modular, vision-free, training-free hierarchical LLM system that decomposes instructions into sub-goals and executes them by topological graph navigation, reducing navigation error by 68.5% compared to heuristic and sampling baselines on the Map2Seq dataset.
3. Formalization of the "Agent-as-Judge" methodology, including a protocol for validating the evaluator itself through correlation between agentic metrics and human judgments of instruction clarity, plus studies on map representations and instruction segmentation.
4. A detailed implementation description, covering graph serialization algorithms, prompt engineering strategies for hierarchical reasoning, and statistical methods for analyzing agent trajectories.

Main Findings

• Structured representations win: The paper's ablation work compares four encoding strategies (textual narratives, structured JSON graphs, grid-based matrices, GraphViz-style visualizations) and reports that structured JSON and textual formats substantially outperform grid-based and visual graph representations. The JSON format achieves Navigation Error of 41.3 (m) and Success Rate of 74.0%.
• Large error reduction over baselines: The hierarchical architecture reduces navigation error by 68.5% compared to heuristic and sampling baselines on Map2Seq.
• Overall execution results (TestSet A): GROKE reaches NE 56.8, SR 66.4%, OSR 78.4%, and SDTW 0.634, versus the best baseline (Heuristic Agent) at NE 180.6, SR 18.0%, OSR 18.9%, and SDTW 0.155. Random Walker scores NE 259.0, SR 4.4%, OSR 5.7%, SDTW 0.026, and Action Sampling scores NE 250.1, SR 5.1%, OSR 6.0%, SDTW 0.037.
• Overall execution results (TestSet B): GROKE reaches NE 59.8, SR 63.3%, OSR 78.0%, and SDTW 0.609, versus the Heuristic Agent at NE 173.0, SR 17.9%, OSR 19.1%, and SDTW 0.159. Random Walker scores NE 244.3, SR 6.1%, OSR 7.1%, SDTW 0.029 and Action Sampling scores NE 241.6, SR 7.4%, OSR 8.1%, SDTW 0.039.
• Agent metrics align with human judgment: On a sample of 100 instructions from Map2Seq Test_Seen (n = 100), Navigation Error showed the strongest correlation with human annotations in both Pearson (r = -0.31, p < 0.01) and Spearman (ρ = -0.32, p < 0.01) coefficients; the table reports r = -0.3096 (p = 0.0017) and ρ = -0.3184 (p = 0.0012). SR and SDTW showed moderate positive correlations (r ≈ 0.29). OSR failed to achieve statistical significance (p > 0.05).
• Human versus automated success: Human annotators achieved a Success Rate of 86%, compared to 74% achieved by the autonomous navigator.
• Computational cost: On TestSet A the agent takes an average of 5.91 steps and on TestSet B 6.15 steps (median 6 for both). Average total tokens reach 44,438 for TestSet A and 46,305 for TestSet B, with average "thoughts" tokens of 23,044 and 24,000 respectively.
• Ablation difficulty distribution: When 100 instances sampled from the seen validation set of Map2Seq were rated on three dimensions (Linguistic Intricacy, Topological Complexity, Operational Demand), the subset was categorized into 49 easy, 38 medium, and 13 hard instructions, with a mean normalized complexity score of μ = 0.40. The standard deviation is not reported in the available content.
• Efficiency ceiling: The limitations section reports that achieving optimal trajectory fidelity requires the "High" thinking configuration, which consumes approximately 41,347 tokens per average episode. Reasoning over spatial graphs does work, but at meaningful latency and cost.

Methodology in Plain English

The researchers reframe navigation instruction evaluation as a graph problem. Instead of pixels, the agent sees a symbolic map: street intersections and waypoints as nodes, directed street segments as edges, and points of interest (POI) with coordinates and semantic tags.

Instructions are handled by two cooperating LLM-based agents. A Sub-instruction Agent breaks a full instruction into atomic sub-goals, restricted to three primitives: MOVE_FORWARD, TURN_LEFT (about 90° counterclockwise), and TURN_RIGHT (about 90° clockwise). Each sub-goal carries a natural-language description and a status (IN_PROGRESS, COMPLETED, or TODO). This agent also extracts landmarks mentioned in the text and grounds them against map POIs using fuzzy string matching with the RapidFuzz library, with a similarity threshold τ; grounded landmarks get letter identifiers (A, B, C, etc.).

A Navigator Agent then walks the graph step by step. At each step it receives the current sub-goal, position, heading, and a "visible area" — a local slice of the map simulating what a person would see looking down the street. That visible area is built by traversing forward along the current heading through a set number of intersections, where an intersection is any node with degree greater than 2. Bearing between nodes uses the spherical bearing formula normalized to [0, 360) degrees. The traversal stops if the next candidate deviates by more than 100°, and extends three additional nodes for lookahead context. For each node on the visible path, nearby POIs within 50 meters are found using Haversine distance, and their direction relative to the current heading is classified as Forward (-45° to 45°), Left (-135° to -45°), Right (45° to 135°), or Back.

The Navigator outputs a status and a next waypoint. Completed sub-goals advance the index; otherwise the agent moves while keeping the same sub-goal. Navigation stops when all sub-goals are done, 100 total steps are exceeded, or a single sub-goal hits 15 retries.

Three baselines contextualize the results. A Random Walker picks outgoing edges uniformly at random as a chance-level lower bound. A Heuristic Agent extracts directional keywords with regular expressions and greedily picks the best-aligned edge. Action Sampling ignores the instruction entirely and samples from the global probability distribution of ground-truth movements, testing for dataset bias.

The system was built with the open-source Google Agent Development Kit (ADK) and uses online and batch APIs of Gemini-3 Pro with default parameters (temperature 1.0, thinking level defaulting to high). Evaluation follows prior protocols using Navigation Error (NE), Success Rate (SR, terminating within 25 meters of the target), Oracle Success Rate (OSR), Normalized Dynamic Time Warping (nDTW), and Success weighted by Dynamic Time Warping (SDTW).

Why This Matters

The paper argues that if navigability cannot be measured accurately, systems cannot be trained to generate better instructions and low-quality human data cannot be filtered out of training sets. By removing the visual simulator from the loop, GROKE decouples linguistic quality from computer vision performance, avoids licensing restrictions and API costs tied to proprietary imagery such as Google Street View, and makes pragmatic evaluation more reproducible and accessible.

Real-world applications the paper points toward:

• Assistive navigation for blind and low-vision users, where symbolic reasoning and instruction clarity matter more than pixels — the authors explicitly describe integration with smart glasses, wearable guidance devices, and smart devices.
• Smart glasses and wearable sensors that capture environmental data and process visual or auditory inputs into topological graph data for real-time human navigation guidance.
• Data curation for navigation model training, using navigability scores as a filter to remove ambiguous or underspecified crowd-sourced instructions before they enter a training set.
• Speaker model development, since the same metrics that judge instructions can guide generation of clearer ones.

Industry relevance: The framework targets the practical bottlenecks of embodied AI and human-robot interaction pipelines — simulator licensing, imagery costs, and reproducibility barriers — that currently limit pragmatic evaluation to well-funded labs. It also produces execution traces and decision trajectories that the authors position as a resource for targeted model training and fine-tuning.

Future Directions

• Reduce computational overhead by training domain-specific small language models, using teacher-student distillation to create compact models suitable for edge deployment and integration with assistive technologies and smart devices.
• Extend to multimodal assistance, exploring how wearable sensors and smart glasses can feed environmental data into the system in real time.
• Verify generality across models: the empirical findings on spatial representations are currently limited to the Gemini-3 Pro architecture, and it remains unknown whether the preference for hierarchical data is universal across LLMs or an artifact of that model's training distribution.
• Address the vision-free limitation: GROKE cannot validate instructions that depend on purely visual cues not encoded in the map schema, such as "turn left at the house with the red door" or "follow the graffiti wall."

Target Audience

Researchers and practitioners working on VLN, embodied AI, and human-robot interaction who need evaluation methods that are reproducible and free of simulator licensing constraints. It is also relevant to NLP researchers interested in LLM spatial reasoning and graph serialization, and to engineers building assistive or wearable navigation guidance systems who care about instruction clarity and safety constraints rather than visual grounding.

Authors’ abstract

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.