Telling "Hard" from "Impossible" in Multi-Hop Spatial Reasoning

When a model answers "where is A relative to D?" from a story such as "A is left of B, B is above C, C is left of D," it has to chain spatial facts. Its accuracy falls steeply as the chain gets longer. Real queries also break: a link is missing, or two statements contradict each other, and then the right output is "this cannot be determined." This note argues that these two problems interact badly. Long chains make a model uncertain even when an answer exists. Broken chains make it uncertain because no answer exists. A model that abstains (declines to answer) whenever it feels unsure therefore cannot tell a deep, answerable question from an unanswerable one, and the confusion should worsen with depth.

We propose to measure this confusion directly and to fix it with a structural signal rather than a confidence signal. The model is trained to track, for every entity in the story, its position relative to the query's starting entity, with an explicit "not reached" state. It answers when the target ends up with one consistent position. It abstains when the target is never reached or receives two conflicting positions. The symbolic solver that produces these training targets is discarded at test time.

Core Claim

Our claim is that abstention based on output confidence loses its ability to separate answerable from unanswerable spatial queries as chain depth grows, and that supervising intermediate reachability-and-position state recovers it. A rough argument shows why depth should hurt. If each hop succeeds with probability $p$, a correct $k$-hop answer is produced with probability near $p^k$. For $p=0.9$ and $k=10$ this is about 0.35, which is close to the diffuse confidence a model shows on a query with no valid chain.

The evidence for this gap comes from three sources. On StepGame, a benchmark of synthetic spatial stories with $k=1$ to $10$ hops, the best tuned model, BERT-T+Q-chain from Neuro-symbolic Tuning for Multi-hop Reasoning over Spatial Language, reaches only 44.05% at $k=10$. Answerable deep queries are therefore genuinely low-confidence. AbstentionBench found that reasoning-tuned language models abstain 24% worse than instruction-tuned ones, and that extra thinking tokens make abstention worse. Their traces often notice the missing premise and answer anyway. Neither line of work crosses the two axes. No work in the file measures abstention as a function of hop depth on spatial chains.

Relation to Prior Work

The spatial multi-hop line supplies our method and our data. StepGame builds the benchmark and a memory network (TP-MANN) that binds entities to spatial roles. That network reaches 31.25% at $k=5$, against roughly 11–12% for relational networks. Q-Chain decomposes queries into intermediate questions and adds a loss that penalises logically inconsistent intermediate answers. Disentangling Extraction and Reasoning compares two designs: a symbolic pipeline that extracts relations and reasons over them in the logic language Prolog (PISTAQ, 96–97% on synthetic SPARTQA-Auto), and a neural model with an explicit latent relation matrix (SREQA, 69.5% on the real-text ReSQ). All three assume every query is answerable.

We reuse two ideas from them: intermediate supervision from Q-Chain, and explicit relational state from SREQA. Our intermediate target differs. It is reachability plus relative grid position, which makes "no answer" a state the model represents rather than a forced guess.

The unanswerability line motivates the work and also limits it. Ask, Condition or Abstain builds missing-premise problems by deleting edges from a reasoning graph and trains abstention with a tiered reinforcement-learning reward. It raises Qwen3-8B's Behavior Score on its Missing-Premise Benchmark from 8.66 to 51.73. We borrow its edge-deletion recipe but apply it to spatial chains, where the graph structure is exact, and we stratify by depth. Yang et al. show that unanswerability classifiers exploit surface word patterns. This forces our data design: broken stories must be lexically matched to intact ones.

On the visual side, VISREAS provides compositional visual questions whose premises, including spatial relations, can fail. Its Logic2Vision system has a language model write a program that a vision model executes, returning NONE when a premise fails. VISREAS does not analyse performance by reasoning depth, which we add. CLIP-UP injects a global image-text alignment prior to detect unanswerable visual questions. A global prior of this kind cannot detect a single missing link deep inside a chain, so it serves as a contrast rather than a component.

Research Program

Benchmark construction. The first artifact is StepGame-Abstain. For each StepGame story at depth $k$, we create three versions.

The broken version deletes one sentence on the supporting chain and replaces it with a disconnected noise sentence of matched length that mentions the same entities. This keeps entity mentions and story statistics fixed and removes surface shortcuts. The contradicted version adds a sentence implying a position inconsistent with the chain. The intact version is the original story, with the same edit applied to an irrelevant branch so that it too carries an edit.

Each broken story is paired with its intact counterpart. A solver computed from the generator supplies gold reachability and positions for every entity. We also break chains in ReSQ by hand: a few hundred human-edited deletions and contradictions. This tests the method where symbolic extraction is known to struggle. Finally, we split the VISREAS problematic set by the number of relation hops in each query's program.

Model. The second artifact is a position-tracking head on a BERT-T+Q-chain backbone. For every entity mention, the head predicts a relative grid offset from the query source. In StepGame each relation can be written as a unit displacement, so composing relations amounts to adding offsets. The head can also output a "not reached" token. It is trained with cross-entropy on solver targets, alongside Q-Chain's consistency loss.

At test time the head decides the output:

  • if the target is reached with one consistent offset, the model answers with that offset's direction;
  • if the target is unreached, or receives two offsets that disagree, the model abstains.

We will analyse where along the chain the reached and unreached states first diverge between broken and intact stories. This probe shows whether the model actually localises the break.

Baselines

The naive reference point is the published BERT-T+Q-chain model, which always answers. Its reported StepGame accuracy at $k=10$ is 44.05%. On StepGame-Abstain it scores zero on abstention by construction, so it fixes the floor and the answerable-accuracy ceiling we must not fall below.

The first real baseline is confidence thresholding on that same model: abstain when the top softmax probability falls below a threshold tuned on a validation split. This is what practitioners would deploy, and it directly tests our central claim.

The strongest neural competitor is the same backbone fine-tuned with an added "unanswerable" output class on exactly our training stories. It uses the same data, steps, and hyperparameter search budget, but has no intermediate supervision. This is also the ablation that isolates our key ingredient: the position-tracking head. A second ablation keeps the position head but removes the "not reached" token, so the model must find conflicts but never represents absence.

The strongest large-model competitor is ACA-RL-style reinforcement learning on Qwen3-8B with that paper's tiered reward. We will train it on our stories with its mixing rule of 30% unanswerable and 70% standard problems, and give it matched compute.

The symbolic upper bound is a PISTAQ-style pipeline of extractor plus graph reachability. We expect it to be near-perfect on synthetic stories and weak on ReSQ.

On VISREAS, the baseline is Logic2Vision, reported at 66.20% overall accuracy. No reported result was found on Lacuna for abstention, or for any depth-stratified metric, on StepGame or VISREAS.

Beating the baselines means two things at every depth from 6 to 10. First, a higher area under the ROC curve for separating intact from broken queries than both the threshold baseline and the extra-class baseline. Second, answerable accuracy within one point of the always-answer model.

Why not just…?

Why not just threshold the model's confidence? Our core hypothesis is that this fails specifically at depth. At $k=10$, even correct answers come from a model that is right only 44% of the time, so its confidence distributions on intact and broken stories should overlap. The depth-stratified ROC curve settles this directly. If thresholding stays strong at $k=10$, our premise is wrong and the proposal reduces to a benchmark contribution.

Why not just add an "unanswerable" class and fine-tune? This is the real threat. With lexically matched pairs it might learn to localise breaks on its own. Two results will decide it. The first is the head-to-head at equal budget. The second is out-of-distribution depth: train on $k\le5$ and test on $k=6$ to $10$. StepGame's own results show that unstructured Transformers fail to generalise across depth while structured memory holds up, which suggests that an abstention signal without explicit state will degrade the same way. If the extra-class model matches ours on that split, we will report that the intermediate supervision is unnecessary.

Why not just use a symbolic solver? On synthetic text it would essentially solve the task, and we include it as an upper bound rather than pretend otherwise. The question is whether that behaviour can be had without perfect extraction. Mirzaee et al. show symbolic pipelines losing to neural models on ReSQ's implicit commonsense, and the human-edited ReSQ breaks test whether that gap carries over to abstention.

Why not just prompt or RL-train a reasoning LLM? AbstentionBench reports that reasoning models abstain worse and that more thinking hurts. ACA-RL does improve abstention, but only on text math problems. Running ACA-RL at matched compute, stratified by depth, will show whether reward shaping alone holds up on long spatial chains.

Proposed Experiments

The decisive check has three parts:

  • Depth curve. Plot ROC area for separating intact from broken stories against $k$ for every method on StepGame-Abstain, reporting answerable accuracy alongside. We expect the confidence-based curve to fall toward 0.5 and the position-tracking curve to stay flat.
  • Depth generalisation. Repeat the comparison on the train-on-$k\le5$, test-on-6-to-10 split.
  • Contradiction versus deletion. Report broken and contradicted stories separately. Absence and conflict may need different evidence, and the ablation without the "not reached" token predicts a gap specifically on deletions.

Transfer is tested on hand-edited ReSQ, and on VISREAS split by hop count, where we feed scene-graph relations extracted by the vision model into the position head and compare against Logic2Vision.

A negative result is informative either way. If the threshold baseline stays separable at depth, then multi-hop decay does not contaminate abstention. If the extra-class baseline generalises across depth, then structure is not needed for this.