When a language model answers a question that needs several chained facts ("Where was the director of the film that won Best Picture in 1998 born?"), each step is a lookup: find the fact that links the current entity to the next one. A classical program doing this lookup either finds a matching record or returns not found and stops. A neural reader does something different. Soft attention, the mechanism that spreads a normalized weight over every piece of context, always returns a weighted blend of something. That one property plausibly explains three failures that are usually studied apart. Models invent a bridge when a link is missing, which is the unanswerable-question problem. Irrelevant sentences dilute the blend, which is distraction. Small blending errors pile up across steps, which is multi-hop decay. We propose to replace the soft blend at each hop with a hard choice among the available premises plus an explicit null slot. The system carries only a small discrete state from hop to hop, so a missing link ends the chain in abstention instead of an invented answer.
This design borrows directly from neural algorithmic reasoning. That field trains networks to imitate classical algorithms and has learned that discrete state bottlenecks and memoryless (Markov) transitions let such networks run correctly on inputs far larger than they were trained on. We carry those lessons to text-based multi-hop question answering and add the one thing algorithm-execution work never needed, a learned "the record is absent" outcome. The payoff we aim for is abstention accuracy that stays flat as chains get deeper and as distractors are added. Frontier models do the opposite: they get worse at abstaining when given more reasoning (AbstentionBench), and they collapse on partially unanswerable chains (CRUMQs).
Core Claim
At hop $t$ the system holds a discrete state $s_t$, meaning the current bridge entity or variable and the remaining relation to follow. It scores each premise $c_j$ in the context against that state and also scores a null option:
$$ p(j \mid s_t) = \mathrm{softmax}\big(\{\, g(s_t, c_j) \,\}_{j=1}^{M} \cup \{\, b(s_t) \,\}\big), \qquad j_t^{*} = \arg\max_j \, p(j \mid s_t). $$
Here $g$ is a learned premise-matching score, $M$ is the number of premises in context, and $b$ is a learned score for "no premise continues this chain." Training uses a Gumbel-softmax relaxation of this choice; inference uses the hard argmax. If $j_t^{*}$ is the null slot, the system abstains and reports which hop failed. Otherwise the next state $s_{t+1}$ is computed only from $s_t$ and the single selected premise. Neither the reasoning history nor the other premises feed into it.
The claim is that three properties together give a specific, testable behavior: hard selection, an explicit null, and a Markov state. Accuracy per hop should not depend on depth, because nothing continuous carries over between hops. Distractor damage should grow with the number of near-miss premises, those that match the current entity on the surface, and not with the total volume of irrelevant text. That follows because a hard argmax fails only when some wrong premise outscores the right one, so its error is bounded by the confusable competitors rather than by how thin the attention mass has been spread. Finally, an absent link should produce abstention at the correct hop, whether that hop is first, in the middle, or last.
Where This Sits Relative to Prior Work
Four papers motivate the proposal by documenting the gap. AbstentionBench evaluates 20 models on over 35,000 unanswerable questions. It finds reasoning-tuned models are 24% worse at abstaining than instruction-tuned ones, and their reasoning traces often notice the missing information before answering anyway. It does not vary chain depth or distractor load. CRUMQs builds 2–7 hop retrieval queries that resist shortcuts, shows GPT-5 reaches only a 28% acceptable response ratio, and finds partially unanswerable queries hardest. It is purely an evaluation and proposes no remedy. GSM-DC generates math problems from symbolic dependency graphs with controlled depth and distractor count. It shows error rises as a power law in distractors and interacts with depth, but it contains only answerable problems. MuSiQue composes connected 2–4 hop questions, adds surface-matching "positive distractors," and in MuSiQue-Full pairs each question with an unanswerable twin made by deleting a supporting paragraph. We use these benchmarks and their generators. None of these papers builds a reasoner whose structure makes abstention the default when a link is missing.
Two lines of work supply the method. Discrete Neural Algorithmic Reasoning uses discrete states, hard attention that reads from exactly one neighbor, and strict separation of continuous scalars from control state. With these, it reaches 100% accuracy on graphs up to 1600 nodes where GIN and pointer graph networks fall to 0%. On the Markov Property of Neural Algorithmic Reasoning shows that feeding execution history into each step acts as a crutch that breaks under distribution shift; removing it with gated forgetting (G-ForgetNet) lifts the CLRS-30 average to 82.89%. We reuse both ideas.
These same papers also constrain the design. DNAR needs per-step supervision ("hints") and hard attention cannot compute soft aggregations. Strict history removal destabilizes training on harder algorithms. We therefore supervise which premise is used at each hop, which our generators and MuSiQue's composition annotations provide. We also restrict the discrete machinery to selection, leaving premise encoding to a pretrained language model.
The closest prior system is FSM prompting. It chains decomposer, searcher, reviser, and judge prompts over a black-box LLM, one sub-question per step, and reaches 40.5–48.5 F1 on MuSiQue. It has no abstention state, is not tested past four hops or under heavy noise, and each of its steps still runs a full soft-attention LLM that can invent a bridge. Our system differs in two ways. The null choice is trained and competes directly against every premise score. And the state passed between hops is a discrete symbol, not free text.
Neurosymbolic provers such as LINC remove depth decay on ProofWriter and natively support an "Unknown" answer. However, they depend on translating text into logic, and that translation degrades with distractors and long, messy context (FOLIO). Our selector never translates the whole context; it only has to rank premises.
Research Program
We first build a controlled testbed. We will extend the GSM-DC graph generator and a PRONTOQA-style ontology generator (Testing Deductive Capacity with OOD Examples) along three independent axes: chain depth (1–10), distractor count split into near-miss and unrelated, and missing-hop position (none, first, middle, last). A missing-hop instance is made by deleting exactly one supporting premise, in the style of MuSiQue-Full, so every unanswerable item has a minimally different answerable twin. This removes the surface cues that inflate unanswerable-detection scores (Towards Unbiased Evaluation in EHRSQL).
The model has three parts. A pretrained encoder of about 1B parameters embeds each premise once. A small step module holds the discrete state as a codebook index over entity and variable slots plus a relation embedding, computes $g$ and $b$, and applies the hard selection. A terminal reader produces the answer from the final selected premise. The state is updated from the selected premise alone, following the Markov recipe; if training proves unstable, we fall back on G-ForgetNet-style gated annealing. For arithmetic chains, as in GSM-DC, numeric values sit in a separate scalar channel that never enters the control state, following DNAR's isolation rule.
Training uses depths up to 4, moderate distractor counts, and paired answerable and unanswerable twins. Evaluation goes out of distribution in depth (5–10) and in distractor count, beyond the training maximum. We then transfer to natural text on MuSiQue-Full and CRUMQs, using retrieved paragraphs as the premise set.
Baselines
The naive reference point is the same 1B encoder-decoder, or a comparable instruction-tuned model, fine-tuned end to end on the identical training set to output either the answer or "unanswerable." It has no step structure, and it tells us what the data alone buys.
The strongest trained competitor is Hard-IC fine-tuning from GSM-DC: an LLM of matched size fine-tuned on high-intensity distractors, which that paper found necessary for out-of-distribution robustness. We extend it with the same unanswerable twins and the same per-hop supervision, expressed as chain-of-thought targets. It gets the same data, the same number of gradient steps, and the same hyperparameter search budget as our model. We also run its ToT-with-process-reward-model variant at a matched inference token budget.
The strongest structured competitor is FSM2 (FSM) with an added rule: if the searcher returns nothing relevant, emit "unanswerable." It will be run over the same premise sets with an open 70B-class model. Its reported MuSiQue F1 is 40.5–48.5, against Select+Answer's 47.3 on MuSiQue-Ans (MuSiQue). On the synthetic logic subset we also run LINC with Prover9.
For the unanswerable side of MuSiQue-Full, we found no reported result on Lacuna, so we will run all baselines ourselves. On CRUMQs the reference figure is GPT-5's 28% acceptable response ratio. On GSM-DC, Grok-3-Beta's step accuracy on 5-step problems falls from 43% with 1 distractor to 19% with 15.
Our system beats these baselines if two things hold at depths 7–10 and at the largest distractor counts. First, its abstention F1 on missing-hop items must exceed the best baseline's by a margin larger than the seed-to-seed spread. Second, its answerable accuracy must not fall below that baseline's. We also require that answering accuracy on MuSiQue-Ans come within a few F1 points of FSM2, so the gain is not bought by abstaining too often.
Three ablations each remove one ingredient. The first swaps hard selection for soft attention and keeps the null option. The second keeps hard selection but removes the null, abstaining instead through a confidence threshold on the final answer. The third keeps hard selection and the null but feeds all prior states into each step, restoring history.
Why not just…?
Why not just prompt an LLM through a state machine and tell it to stop when a hop is missing? This is the real threat. FSM already gets per-hop decomposition, and each local question ("does any paragraph give X's director?") is easier than the full chain. What argues against it being sufficient is AbstentionBench's finding that models detect missing information in their traces yet answer anyway. Near-miss paragraphs are exactly the case where a local judge will accept a plausible bridge. The experiment settles it: if FSM2-with-abstain matches our null-slot recall across missing-hop positions and near-miss counts, the trained discrete selector is not needed, and the contribution shrinks to the testbed and the analysis. We would report that outcome.
Why not just fine-tune the LLM on noisy, unanswerable data? GSM-DC shows Hard-IC training helps with distraction, so this baseline gets identical data and supervision. Our bet is that it learns the training depth and distractor range and degrades beyond them, as mild-noise training fails on severe noise in GSM-DC. It predicts smooth decay with depth, while our system predicts flat per-hop error. The depth-extrapolation curves separate the two.
Why not just use a theorem prover, which already outputs "Unknown"? On clean synthetic logic this may tie us, and we will say so. LINC's accuracy is bounded by translation, and FOLIO reports roughly 93% syntactic validity even before semantic errors. Distractor sentences become spurious clauses. We test LINC across our near-miss axis and expect its Unknown precision to fall as distractors grow. It also cannot run on MuSiQue or CRUMQs text without heavy parsing.
Why not just rerank retrieval harder so the reader sees only relevant text? Reranking does not help when the right paragraph is simply absent; it then promotes the best near-miss, which is exactly what produces an invented bridge. The failures of retrieval-equipped frontier models on CRUMQs point the same way. We include a cross-encoder-filtered CoT reader as a sanity baseline.
Decisive Checks
The first check is flatness. Plot per-hop selection accuracy against depth, from 1 to 10, for each system. Our claim fails if the hard-null model's per-hop accuracy drops with depth the way the soft ablation's does.
The second check tests the predicted distractor law. Vary near-miss and unrelated distractors separately. The hard selector's error should track near-miss count and stay roughly flat in unrelated count. Soft baselines should degrade with both, consistent with the power law reported for GSM-DC.
The third check is missing-hop position. Measure abstention recall, and whether the reported failing hop is the correct one, at the first, middle, and last hop. This directly answers the location question that CRUMQs leaves open.
The fourth check is compute. Give baselines larger reasoning budgets and see whether their abstention falls, as AbstentionBench predicts. Our system's abstention should not depend on budget, because the halt is structural.
If the soft-attention-plus-null ablation matches the full model on all four checks, then the null option alone, not discreteness, carries the effect, and we would reframe the paper around that simpler finding.
References
- AbstentionBench: Reasoning LLMs Fail on Unanswerable Questions
- Evaluating Retrieval-Augmented Generation Systems on Unanswerable, Uncheatable, Realistic, Multi-hop Queries
- How Is LLM Reasoning Distracted by Irrelevant Context? An Analysis Using a Controlled Benchmark
- ♫ MuSiQue: Multihop Questions via Single-hop Question Composition
- Discrete Neural Algorithmic Reasoning
- On the Markov Property of Neural Algorithmic Reasoning: Analyses and Methods
- FSM: A Finite State Machine Based Zero-Shot Prompting Paradigm for Multi-Hop Question Answering
- LINC: A Neurosymbolic Approach for Logical Reasoning by Combining Language Models with First-Order Logic Provers
- FOLIO: Natural Language Reasoning with First-Order Logic
- Testing the General Deductive Reasoning Capacity of Large Language Models Using OOD Examples
- Towards Unbiased Evaluation of Detecting Unanswerable Questions in EHRSQL