Language models given a map in their prompt still contradict it. Asked to plan a route through a maze whose walls are listed in the context, they walk through walls, invent passages, and wander into dead ends. These errors persist even when the solution policy is pasted into the prompt. This note proposes to make such errors impossible by construction. While the model writes a coordinate or a route, a GPU-resident picture of the map tells it, token by token, which next tokens can still lead to a geometrically valid answer. All other tokens are blocked. The map lives in graphics-style buffers: a rasterized occupancy grid, a running-sum table for constant-time region queries, and a distance field to the goal. Because these buffers sit on the same GPU as the model, a feasibility check costs a few memory reads per candidate token, across the whole batch, with no round trip to a CPU database.
The scientific claim is narrower than "GPUs fix hallucination." Most spatial hallucination in this setting is intrinsic, meaning it contradicts geometry the user supplied. That kind of error can be eliminated without hurting task quality, but only if the mask looks ahead and asks "can any completion still succeed from here?" A mask that only asks "is this step legal?" is not enough. Local masks prevent wall-crossing but leave the dead-end failures intact. Lookahead masks need a fresh reachability field for every prompt and every step of a batched decode. That workload is where rasterization and distance transforms on the GPU earn their place. The proposal includes an experiment that tests whether the GPU placement actually matters or whether a CPU implementation would do.
What exists and what is missing
Two recent papers target spatial hallucination directly, and both motivate this work by leaving the failure in place.
Mitigating Geospatial Knowledge Hallucination in Large Language Models builds GEOHALUBENCH, 2,100 questions derived from a geographic knowledge graph. It then fine-tunes Llama-3.1-8B with DynamicKTO, a preference-optimization variant that adjusts how strongly the model is pushed away from bad answers depending on task difficulty. It reports a 38.6% improvement over the base model and 29.6% over static KTO. That work targets extrinsic facts stored in the weights, such as "is this landmark in that district." It stores relations as discrete graph edges and does no geometry at runtime. Facts supplied fresh in each prompt cannot be memorized, so its approach does not apply to our target.
Mitigating spatial hallucination in large language models for path planning via prompt engineering (S2ERS) converts mazes from 5×5 to 100×100 into connectivity graphs. It solves them with reinforcement learning and injects the resulting lookup tables of state-action values into the prompt. It reports roughly 29% higher success and 19% higher optimal-path rate than chain-of-thought prompting. It also reports that models still periodically ignore the injected guidance and cross walls, and that prompt length grows badly with map size. That residual failure is the precise gap this proposal fills. Guidance in the prompt is a suggestion; a mask on the output distribution is a guarantee.
The method comes from the GPU spatial-database literature, which treats spatial queries as rendering.
A GPU-friendly Geometric Data Model and Algebra for Spatial Queries models space as a discrete "canvas" with composable operators: transform, mask, blend, and dissect. GPU Rasterization for Real-Time Spatial Aggregation over Arbitrary Polygons separates two ways of answering point-in-polygon queries. A bounded approximate join has error limited by pixel size. An accurate join resolves interior pixels by rasterization and runs exact geometric tests only for points on boundary pixels. That paper reports joins over 868 million NYC taxi points in 1.1 seconds on a laptop. SPADE turns this into a full engine. PR-EDT computes Euclidean distance transforms on GPU, reporting up to 52× over CPU.
We reuse three ideas from this line of work. Constraints become canvases built by mask-and-blend composition. Pixels are split into interior and boundary classes, so blocking can be conservative and exact checks are rare. Distance fields are computed in parallel. None of these systems has been connected to a language model's output distribution.
Core Claim
Let $p$ be the prefix the model has generated, decoded into partial geometry such as the waypoints so far or the digits of a coordinate written so far. Let $C$ be the constraints parsed from the prompt: obstacles, allowed regions, a goal, and a length budget $B$. A candidate token $v$ is allowed only if the extended prefix still admits a valid completion:
$$\text{allow}(v \mid p) \iff \exists\, s \text{ with } p \cdot v \cdot s \models C .$$
For coordinate outputs, a digit prefix of a latitude and longitude pins the final point to an axis-aligned box. Feasibility then becomes "does this box overlap the allowed region." That test is a constant-time lookup in a running-sum table over the rasterized region.
For routes, feasibility of a next waypoint $x$ has two parts. The step from the last waypoint to $x$ must not cross an obstacle. The obstacle-aware distance from $x$ to the goal, written $d_G(x)$, must satisfy
$$\ell(p \cdot v) + d_G(x) \le B,$$
where $\ell$ is the path length so far.
Two properties make the approach work. First, rasterization is conservative: any pixel touching an allowed region counts as allowed. As a result, the mask can over-admit but never blocks a truly valid token. Second, when a span is complete, an exact geometric test runs, but only for points that fell in boundary pixels, following the accurate raster join. This design yields three predictions. Constraint violations should fall to zero. Dead-end failures should fall too, because of the $d_G$ term, which local masks lack. And the model's preferences among valid options should be preserved better than by sampling many answers and filtering them afterward.
Research Program
The system has three parts.
The first is a constraint compiler. A deterministic parser turns the map given in the prompt (maze walls, polygons in a standard text format, obstacle lists) into canvases. It composes them with canvas-algebra mask and blend operations, then precomputes a running-sum table and an obstacle-aware distance field to the goal. A distance field that respects obstacles is computed by repeated wavefront propagation on the raster rather than by pure Euclidean distance. PR-EDT supplies the parallelization pattern but not the exact algorithm, and we treat that adaptation as engineering work to be measured.
The second is a logits processor. During decoding it tracks which part of the output is geometric, maps candidate tokens to boxes or waypoints, and reads the canvases on-device for every sequence and beam. The third is an exact checker that runs at span commit.
The analytical question is how the mask distorts the model's distribution. Blocking tokens and renormalizing can push a model into unlikely, odd continuations. We measure this by scoring masked outputs under the unconstrained model. We compare that score against the likelihood of the best valid sample found by unconstrained sampling.
Baselines
The naive reference is the unconstrained model with chain-of-thought prompting, run on the same prompts with the same sampling settings. The model is Llama-3.1-8B, chosen to match the GEOHALUBENCH study. It shows how often violations occur without help.
The prompting baseline is S2ERS, reimplemented on our maze splits with its graph construction and lookup tables in the prompt. Its reported gain over chain-of-thought, about 29% in success rate, is the published reference. The file gives no absolute success rate, so we report one ourselves. Beating it means higher success and a lower wall-crossing rate on every grid size, with fewer prompt tokens at 100×100.
The strongest competitor is generate-then-verify. The model samples $n$ candidates unconstrained, an exact CPU geometry check filters them, and the most likely valid candidate is returned. This is the honest alternative because it needs no decoder changes. It is run under a matched budget of GPU-seconds per query, with $n$ tuned on a held-out split. Beating it means higher valid-and-successful rate at equal compute, with the gap widening as outputs get longer.
The delegation baseline has the model emit a structured constraint specification that a classical planner solves. A tool-calling version, where the model writes queries for a CPU spatial database, is included. Beating these means matching their validity while scoring higher on the language-specified soft preferences the planner cannot see.
Three ablations isolate the key ingredients. A local-only mask checks step legality but omits $d_G$. A CPU mask uses identical logic with a CPU round trip each step; this tests the GPU claim on throughput alone. A resolution sweep varies canvas size to trace the trade-off between boundary fallbacks and memory.
Why not just…?
Why not just prompt better, or inject the solution as S2ERS does? S2ERS itself reports that models still ignore injected tables and cross walls. A Benchmark for Reasoning with Spatial Prepositions found that few-shot prompting did not repair transitivity errors and left accuracy brittle to rephrasing. The S2ERS comparison measures how much residual violation remains.
Why not just fine-tune, as with DynamicKTO? Intrinsic constraints change with every prompt, so there is nothing stable for the weights to memorize. HalluLens also documents that factuality tuning can produce over-refusal: Llama-3.1-405B falsely refused 56.77% of valid PreciseWikiQA questions. A mask never refuses; it only steers among valid tokens. We will still test a model fine-tuned on in-distribution mazes, to check whether fine-tuning alone closes the gap on held-out geometries.
Why not sample many answers and filter with PostGIS? This alternative is a real threat. For short outputs it may well match our method. The argument against it is compounding: per-step error accumulates, as Holt et al. describe for autoregressive generation. The fraction of fully valid samples should therefore decay with path length, so $n$ must grow. The matched-compute curve across maze sizes settles the question. If filtering keeps pace up to 100×100, we will say so and narrow the claim to longer outputs.
Why not just hand the geometry to a planner and skip the language model? For a bare maze, that is correct, and A* wins. The proposal therefore targets tasks that combine fixed geometry with preferences stated in language, where a planner alone cannot read the preferences. The delegation baseline tests whether keeping the model in charge of choices actually helps.
Proposed Experiments
The first benchmark is the S2ERS maze suite at its published sizes, plus 200×200 and 400×400 to probe the scaling where S2ERS reports prompt blow-up.
The second is a new benchmark of continuous-geometry tasks with the map given in the prompt. It is built from NYC taxi-zone polygons, the boundaries used with the taxi data. Tasks include "give a point inside zone X but outside Y" and "a walking route from A to B under k km avoiding zones Z, preferring parks." Preferences are scored against attached zone labels.
Metrics are as follows. Violation rate is the share of outputs that contradict the supplied geometry, our measure of intrinsic hallucination. We also measure task success, optimal-path rate, and preference satisfaction. Likelihood gap under the unconstrained model measures distortion. Tokens per second and GPU-seconds per valid answer measure cost.
We report the false-block rate as a check, not an assumption. It should be zero under conservative rasterization. Any nonzero value exposes a bug in how tokens are mapped to geometry.
Three outcomes decide the main questions. If the local-only mask matches the lookahead mask on dead-end failures, the lookahead claim fails. If generate-then-verify matches us at equal compute across lengths, the decoding intervention is not worth its complexity. If the CPU mask matches GPU throughput at realistic batch sizes, the GPU component is incidental, and we would report the method as a decoding technique and nothing more.
References
- Mitigating Geospatial Knowledge Hallucination in Large Language Models: Benchmarking and Dynamic Factuality Aligning
- Mitigating spatial hallucination in large language models for path planning via prompt engineering
- A GPU-friendly Geometric Data Model and Algebra for Spatial Queries
- GPU Rasterization for Real-Time Spatial Aggregation over Arbitrary Polygons
- SPADE: GPU-Powered Spatial Database Engine for Commodity Hardware
- GPU-Based Parallel Euclidean Distance Transform Algorithm
- A Benchmark for Reasoning with Spatial Prepositions
- HalluLens: LLM Hallucination Benchmark
- Data-Driven Discovery of Dynamical Systems in Pharmacology using Large Language Models