Verifiable Reasoning of Large Language Models over Structured Spatial Data

A Survey and Research Agenda

Abstract

Large language models increasingly answer questions grounded in structured spatial data such as road networks: in navigation assistants, in conversational interfaces to geographic information, and in tools that maintain digital maps. Their answers are fluent but not verifiable, and in spatial domains a claim about a turn restriction, a lane, or an opening time is either consistent with the map or it is not. This survey reviews the methods by which such claims can be machine-checked. We organize the literature along an argument: models cannot reliably verify their own outputs; external checkers such as program execution and symbolic solvers demonstrably can; constrained decoding guarantees syntactic but not factual validity; execution against the data is the established gold standard of evaluation in the text-to-query literature; and knowledge-graph grounding already supports detect-verify-repair pipelines. We then examine the spatial domain specifically and find a documented gap: existing geospatial benchmarks measure model capability, and none verifies model claims against lane-level, temporal, or version-aware map data. We synthesize a taxonomy of verification mechanisms, compare existing benchmarks by oracle type, and outline a research agenda toward validity contracts and certificates for spatial claims that remain checkable as the underlying map evolves.