Top-k sparse attention lets each query in a transformer look at only the k keys (or blocks of keys) that score highest against it, and skip the rest. Inside the model this is a small retriever, and it fails the way retrievers fail. When a question needs two pieces of evidence, such as "In what city was the director of Inception born?", the second passage (about Christopher Nolan's birthplace) looks nothing like the question. A selector that ranks blocks by similarity to the question's own representation should miss it, just as an embedding retriever misses it in retrieval-augmented generation (RAG), where a model reads passages fetched from a search index. Long-context and RAG systems increasingly use top-k attention to cut cost. If this failure is real, they are quietly dropping exactly the evidence that multi-hop questions depend on.
We propose to measure this failure directly, hop by hop and layer by layer. We then fix it with a training-free change to block top-k attention that we call key-space expansion. Part of each head's block budget goes not to the blocks most similar to the current query, but to blocks containing keys similar to the keys the head has already attended to. This works like following a hyperlink on the fly. The bridge entity "Nolan" appears in both the first-hop and second-hop passages, so its keys act as an edge between them. No graph is built in advance.
Core Claim
We make two claims. The first is that standard block top-k attention, at budgets that are harmless on single-hop question answering, has much lower recall of second-hop supporting passages than first-hop ones on shortcut-resistant multi-hop benchmarks. This loss, not general context loss, should explain most of its accuracy drop relative to dense attention. The second is that reserving a fraction of the budget for key-space expansion closes most of that second-hop recall gap, and most of the accuracy gap, at equal total budget and with no retraining.
The first claim is motivated by theory. High-Dimensional Analysis of Single-Layer Attention for Sparse-Token Classification proves that attention isolates rare signals far better than averaging when the query is aligned with the signal. It also proves that when alignment fails, attention concentrates on noise and does worse than averaging. A second-hop passage is precisely a signal the query is not yet aligned with. The claim is also motivated by mechanistic evidence. Back Attention finds that models resolve the bridge entity late in depth ("hopping too late"), so a per-layer selector may only become able to find the second hop at layers too deep to use it.
Relation to Prior Work
Three lines of work supply the selection machinery, and none tests multi-hop evidence. Optimizing Mixture of Block Attention gives a fused kernel that scores coarse block summaries and attends only within the top-k blocks. We reuse this kernel as our base selector. SparQ Attention approximates scores using the largest query components and reports one-eighth of the data transfer with negligible loss on SQuAD and TriviaQA. Memory-efficient Transformers via Top-k Attention matches dense accuracy on UnifiedQA with under 1% of keys. All three were validated on single-hop or generic tasks. Our proposal asks whether their selection rule breaks on the very passages single-hop benchmarks never require.
Connecting work constrains the design. Block-Attention for Efficient RAG isolates documents into separately cacheable blocks and lets only the final query block attend across them. It reports 72.2% versus 73.2% accuracy on 2WikiMultiHopQA. Because all cross-document combination is pushed to query-side attention, that is exactly where our selector operates, and our method stays compatible with its caching. Transformer-XH lets document hub tokens attend along graph edges for one hop per layer, but it needs a document graph built beforehand. Our expansion step builds those edges dynamically from key similarity. What Structural Inductive Bias Helps Transformers Reason Over Knowledge Graphs? finds that hard adjacency masking accounts for most multi-hop gains, including +72.5 points on 3-hop MetaQA, and that k hops need at least k layers. We read this as evidence that sparsity is helpful when it follows the right edges. Expansion attempts to recover such edges without a schema.
On the retrieval side, DRAGIN builds next-hop search queries from the tokens that received the most attention. Our expansion probe is the in-context analog of that idea: attended keys, not the current query, decide what to fetch next. Optimizing Multi-Hop Document Retrieval Through Intermediate Representations shows that middle layers encode next-hop intent, and it maps them through a trained network into an external retriever. We instead act inside the context, with no training. Cache-eviction methods such as R-KV and OBCache decide which tokens to keep permanently. Neither was evaluated on multi-hop question answering over text, and neither addresses query-dependent selection.
Research Program
The diagnostic comes first. We will concatenate each question's gold paragraphs with retrieved distractors, at 20, 50, and 100 paragraphs, on three benchmarks. MuSiQue was built from composed single-hop questions to block shortcuts, and its decompositions label which paragraph serves which hop. 2WikiMultiHopQA supplies annotated reasoning paths. HotpotQA in the distractor setting serves as a more shortcut-prone contrast. We will run Llama-3.1-8B, the model OBCache uses on RULER, with block top-k attention at several budgets.
For every layer and head we will log whether each supporting paragraph's blocks fall in the selected set, separately for hop 1, hop 2, and hop 3. We will also log the earliest layer at which hop-2 blocks are reliably selected. Comparing that layer with the layer where a linear probe first decodes the bridge entity from the question tokens tests the "hopping too late" account directly at the level of attention.
The method follows. At each layer, every head splits its budget $k = k_q + k_e$. The $k_q$ blocks are chosen in the usual way, by similarity between the query and block summary vectors. For the $k_e$ blocks, the head takes the $m$ keys that received the most attention mass inside its $k_q$ selected blocks. It uses these keys as probes, scores every unselected block by its maximum key-probe similarity, and takes the top $k_e$. Probes come from the same layer, so no extra pass is needed. The added cost is $m$ probe scorings against block summaries, small next to the selection itself. Within a selected block, the max-key score can be approximated with a per-block key sketch.
We will sweep $k_e/k$ and $m$, and test two choices of where probes come from: the current layer only, or carried over from the previous layer. If the training-free version leaves a gap, a secondary experiment fine-tunes only the probe projection for a few hundred steps on MuSiQue training questions. This mirrors the 500–1000 step adaptation used by Block-Attention.
Baselines
The naive reference is dense attention over the same concatenated context. This is the accuracy ceiling we aim to approach at a fraction of the cost. It also tests the claim, raised by High-Dimensional Analysis of Single-Layer Attention for Sparse-Token Classification, that sparsity can exceed dense accuracy by filtering distractors at 100 paragraphs. A second naive reference is a single-hop retrieve-then-read pipeline over the same paragraph pool, which bounds what similarity alone achieves.
The strongest competitor on the efficiency question is plain block top-k attention using the Optimizing Mixture of Block Attention kernel and selection rule, at the same total budget $k$, block size, model, and paragraph pool. It is the strongest rival because it already re-selects at every layer with layer-specific queries. If late layers recover second-hop blocks naturally, it will match us. No reported result was found on Lacuna for this method on MuSiQue, 2WikiMultiHopQA, or HotpotQA, so we will run it ourselves. We will also run SparQ, whose reported result is one-eighth of the data transfer with negligible accuracy loss on single-hop question answering. Both get the same hyperparameter search over block size and budget that we give our method. Beating them means higher answer F1 and hop-2 recall at matched selected-key count and matched measured latency.
For the cache-compression family we will run SnapKV, R-KV, and OBCache at matched memory. R-KV reports up to 40% higher accuracy than SnapKV on math reasoning. OBCache reports up to 15% higher accuracy than AdaKV on RULER while discarding 70–90% of the cache.
Two external multi-hop pipelines serve as reference points rather than direct competitors. One is Block-Attention, which reports 72.2% accuracy on 2WikiMultiHopQA. The other is the intermediate-representation retriever of Optimizing Multi-Hop Document Retrieval Through Intermediate Representations, which reports 0.352 accuracy on MuSiQue and about 2.8 seconds per query on 2WikiMultiHopQA, versus over 20 seconds for iterative retrieve-and-generate. DRAGIN reports 0.3931 F1 on 2WikiMultiHopQA with LLaMA2-13B. These numbers come from different models and retrieval setups. We will rerun them on our model where code allows and label any quoted figures as non-comparable.
The key ablation isolates expansion. It uses the same split budget, but fills the $k_e$ slots by (i) the next-best query-similarity blocks, (ii) random blocks, or (iii) probes drawn from keys that received low attention. If (i) matches expansion, the gain came from budget, not from following edges.
Why not just…?
Why not just use dense long-context attention? It is the accuracy reference, and on 20-paragraph contexts it may simply win. That would be an acceptable outcome, because the question then becomes cost. Fetching the full cache dominates decoding bandwidth according to SparQ Attention, and OBCache notes that a million-token cache for an 8B model exceeds 120GB. Our paragraph-count sweep shows where dense attention's distractor dilution begins to cost accuracy, if it does at all.
Why not just run an iterative retrieve-and-generate loop? The IRCoT approach issues a search for each reasoning sentence. It improves retrieval recall by 11–21 points, but it pays the latency documented by the L-RAG paper. It also leaves the reading step dense, so it complements rather than replaces in-context selection. The real threat is that a better external retriever makes the in-context pool so small that top-k selection never matters. The 20-paragraph condition tests that regime directly.
Why not just raise k, or use an eviction method? If the hop-2 gap closes once the budget roughly doubles, expansion buys little. The budget sweep traces hop-2 recall against $k$ for plain selection and shows whether expansion moves the curve or merely sits on it. Eviction methods such as R-KV score importance once, without knowing which question comes next. Bridge passages tend to have low importance until the bridge entity is resolved. We expect eviction to do worst on hop 2, though this is a prediction, not a reported result.
Why not let plain per-layer top-k find the second hop at later layers? This is the most serious threat, because block top-k already re-selects at every layer. Two diagnostic outcomes would make our method unnecessary. One is hop-2 recall that rises to dense-equivalent levels by the middle layers. The other is a recovery layer that is early enough not to cost accuracy. In either case we would report that the multi-hop gap does not transfer to in-model selection, itself a useful negative result for anyone deploying sparse attention in RAG.
Decisive Checks
The diagnostic is decisive in itself. On MuSiQue at matched budget, plain block top-k should show a hop-2 recall deficit relative to hop-1 that is clearly larger than on HotpotQA. That deficit should also predict per-question answer errors better than total recall does. If neither holds, we drop the method and publish the measurement.
For the method, the decisive comparison is expansion against ablation (i) at equal $k$ on MuSiQue and 2WikiMultiHopQA. Success means three things: higher answer F1, higher hop-2 recall, and an earlier recovery layer. A further success condition is that expansion's F1 at a budget of 10% or less of keys comes within one or two points of dense attention. We will also report wall-clock prefill and decode latency against the Optimizing Mixture of Block Attention kernel, to show that the probe step does not erase the savings.
Finally, as a check on generality, we will run RULER's multi-hop variable-tracking task. There, the "bridge" is a variable name repeated across hops, the setting where key-space edges should help most clearly.
References
- High-Dimensional Analysis of Single-Layer Attention for Sparse-Token Classification
- Back Attention: Understanding and Enhancing Multi-Hop Reasoning in Large Language Models
- Optimizing Mixture of Block Attention
- SparQ Attention: Bandwidth-Efficient LLM Inference
- Memory-efficient Transformers via Top-k Attention
- Block-Attention for Efficient RAG
- Transformer-XH: Multi-Evidence Reasoning with eXtra Hop Attention
- What Structural Inductive Bias Helps Transformers Reason Over Knowledge Graphs?
- DRAGIN: Dynamic Retrieval Augmented Generation based on the Real-time Information Needs of Large Language Models
- Optimizing Multi-Hop Document Retrieval Through Intermediate Representations
- R-KV: Redundancy-aware KV Cache Compression for Reasoning Models
- OBCache: Optimal Brain KV Cache Pruning for Efficient Long-Context LLM Inference
- ♫ MuSiQue: Multihop Questions via Single-hop Question Composition
- Constructing A Multi-hop QA Dataset for Comprehensive Evaluation of Reasoning Steps
- Interleaving Retrieval with Chain-of-Thought Reasoning for Knowledge-Intensive Multi-Step Questions