When a retrieval-augmented language model answers a question like "In what city was the director of Inception born?", it gets a pile of retrieved passages and must link two of them: one says Nolan directed Inception, another says where Nolan was born. Pipelines usually paste those passages into the prompt in retrieval-score order, which for multi-hop questions is close to arbitrary. The second-hop passage barely resembles the question, so it tends to land far from the first-hop passage and often before it. This proposal treats the order of passages in the prompt as a graph layout problem. Passages become nodes, shared entities become edges, and we pick a linear order that keeps linked passages close together and puts them in the order the reasoning needs. The tool is a classic sparse-matrix reordering: Cuthill–McKee, a breadth-first ordering that clusters connected nodes near the diagonal, i.e. keeps the bandwidth (the longest distance in the order between two linked nodes) small. We make one change: the search starts from the passages that match the question, not from a node at the far edge of the graph.
The point of rooting the search at the question is that its breadth-first levels then roughly match hop depth. A single ordering pass, linear in graph size and needing no extra model calls, puts evidence in reasoning order and keeps dependent evidence adjacent. If this works, a frozen model given one-shot retrieval would get much of the benefit that iterative retrieve-and-reason loops get from appending evidence hop by hop, without paying for the repeated model calls.
Core Claim
For a frozen causal language model, multi-hop accuracy depends on two properties of where the evidence sits in the prompt. The first is the distance between passages that depend on each other. The second is whether a bridge passage comes before the passage that depends on it. Both effects should hold even after controlling for the absolute position effects behind the "lost in the middle" failure. If that is true, a query-rooted Cuthill–McKee ordering of the passage–entity graph is a nearly free intervention that recovers part of the gap between reasoning over gold evidence and reasoning over retrieved evidence. That gap is large: MultiHop-RAG reports GPT-4 accuracy of 0.89 with ground-truth evidence but 0.56 with retrieved chunks.
The claim is falsifiable in two places. First, the distance and direction effects might vanish once absolute position is controlled. Second, if they exist, a simpler ordering that only sorts passages by hop level might capture them fully, which would mean the banding part adds nothing. The program is built so that either outcome is reported cleanly.
Relation to Prior Work
Two papers motivate the gap. Making Long-Context Language Models Better Multi-Hop Reasoners documents position sensitivity in multi-hop reasoning and responds by fine-tuning with document shuffling and distractor sampling (AttrLoRA). It treats order as noise to train away, and reaches 38.1 exact match on MuSiQue at 7B scale. We instead treat order as something to optimize at inference, for frozen models. Is Graph Structure Necessary for Multi-hop Reasoning? shows that graph attention is a masked form of self-attention. It finds explicit graphs add almost nothing when the backbone is fine-tuned (73.93 vs. 73.78 F1 on HotpotQA), but add a clear gain when the backbone is frozen (63.75 vs. 59.76). That result looks like a counterargument, but it is really a constraint pointing our way. Our setting is the frozen one, and we inject structure through the input sequence rather than through extra layers.
Two papers supply the method. LinearRAG builds a passage–sentence–entity graph from cheap named-entity tagging and ranks passages with Personalized PageRank. It then hands the ranked set to the generator with no layout step. We reuse its graph and add the missing step. RCM++ improves reverse Cuthill–McKee by breaking ties among starting nodes by breadth-first level width. It is evaluated only on sparse matrices, where the start node is chosen to be far from everything. We replace that start-node rule with the question-activated passages, which is the change that turns bandwidth reduction into reasoning order.
Two papers constrain what we can claim. On Euclidean Embeddings and Bandwidth Minimization and Inapproximability of Treewidth and Related Problems show that exact or constant-factor bandwidth optimization is out of reach in general. With 10 to 20 passages, though, exact search is cheap enough to serve as an upper-bound comparison, so hardness is not a practical obstacle here.
MARGO is the closest existing bridge between the two directions. It weights layout edges by how often they appear on multi-hop search paths, but it lays out vector-index nodes on disk pages to reduce I/O. It does not touch text, prompts, or generation.
Research Program
The first stage is a controlled diagnostic. It is cheap and can kill the idea. On MuSiQue and 2WikiMultiHopQA, the gold supporting paragraphs come with a known hop structure: MuSiQue's single-hop decompositions and 2Wiki's Wikidata evidence triples. We build prompts with a fixed number of distractor passages and independently vary three factors. One is the gap, in passages and in tokens, between each pair of dependent gold passages. Another is direction, meaning whether the bridge passage comes before or after the passage that depends on it. The third is the absolute position of the evidence block. Using several open-weight models of different sizes, we fit accuracy as a function of these three factors. A distance or direction effect that survives with absolute position held fixed is the empirical premise of the proposal. If it does not survive, we report that and stop.
The second stage is the method. The graph is LinearRAG's entity–passage graph restricted to the retrieved set. The question is attached as a root node linked to passages that share its entities or score highly on query–sentence similarity. We run Cuthill–McKee from the root and break ties within each level by RCM++'s level-width criterion. This yields a forward order (root-adjacent passages first) and its reverse. Passages not connected to the root are placed at the far end, away from the question. Whether the question appears before or after the evidence is a free variable, and we cross it with forward and reverse order. Under causal attention we expect the best setup to place bridge passages first and the question last, but the stage-one diagnostic decides this, not our prior. We also run an exact minimum-bandwidth solver on these small graphs, rooted the same way, to measure how much the heuristic gives up.
The third stage is analysis. For each question we compute the realized bandwidth of the gold dependency edges and the count of backward dependencies under each ordering. We then check whether these quantities mediate the accuracy differences between orderings, and whether they predict difficulty across MuSiQue's six reasoning-graph shapes. That last test is a small, concrete version of the open question of whether layout parameters track multi-hop hardness.
Baselines
The naive reference point is retrieval-score order: the same retrieved passages sorted by retriever score, as a standard pipeline does. Random order, averaged over five seeds, gives the variance floor.
The strongest competitor at zero extra model calls is LinearRAG's Personalized PageRank order. It uses exactly the same graph, so any gain from our method comes from the layout and not from the graph. On 2WikiMultiHopQA it reports 66.95% average accuracy, against HippoRAG's 63.00%. We run it on identical retrieved sets, with the same generator and decoding settings. A win requires a statistically significant exact-match/F1 improvement over the PPR order on MuSiQue and 2Wiki. We also add a widely used heuristic that places top-scored passages at both ends of the prompt to avoid the middle; it needs no citation and is cheap to include.
Among methods that spend more compute, two references matter. IRCoT (Interleaving Retrieval with Chain-of-Thought Reasoning) reports retrieval-recall gains of 11–21 points and F1 gains of up to 15 points. We run it with the same retriever and generator, and record both accuracy and number of model calls. The goal is not necessarily to beat it, but to recover a measurable fraction of its gain over one-shot retrieval at one model call. AttrLoRA's shuffle-trained model, at 38.1 EM on MuSiQue, tests whether training-time invariance makes ordering irrelevant. We apply our ordering to that model too. If our ordering still helps it, the two approaches are complementary. If it does not, training is the better route, and we will say so.
Three ablations isolate the key ingredient. Level-only order sorts passages by breadth-first distance from the root and shuffles within each level. It keeps reasoning order but drops the banding inside levels. Un-rooted RCM++ uses the pseudo-peripheral start node and isolates the effect of rooting at the question. Oracle gold-chain order is the upper bound. If level-only order matches the full method, we will report that the benefit comes from hop sorting alone and drop the bandwidth framing.
Why not just…?
Why not just fine-tune with shuffled documents, as AttrLoRA does? That requires training access, and the paper notes it slightly hurts general instruction following. Its MuSiQue result is still under 40 EM. It also does not apply to closed models. Our experiment applies ordering on top of the shuffle-trained model, which directly tests whether its invariance makes layout moot.
Why not just drop the distractors instead of ordering them? This is a real threat, because our method already pushes disconnected passages to the far end. We add a baseline that deletes every passage not connected to the root and keeps retrieval-score order for the rest. If that baseline matches our method, the gain comes from filtering and not from layout. The diagnostic in stage one, which holds the distractor set fixed and varies only order, separates the two effects.
Why not just use iterative retrieval, which already appends evidence in hop order? IRCoT's context does end up in roughly reasoning order. That is part of why we expect order to matter. But it pays one model call per step, and an early wrong retrieval derails the chain. Our comparison reports accuracy against number of calls, so readers can see which regime each method wins.
Why not just order by hop level and skip bandwidth entirely? For a clean two-hop chain the two orderings are identical. They differ only when distractors share entities with gold passages, or when the reasoning graph branches, as in MuSiQue's non-chain shapes. The level-only ablation, broken down by reasoning-graph shape, settles this question.
Proposed Experiments
The benchmarks are MuSiQue-Ans, 2WikiMultiHopQA, HotpotQA in the distractor setting, and MultiHop-RAG. We report HotpotQA, but give it less weight because MuSiQue shows it admits single-hop shortcuts. MultiHop-RAG is used to measure how much of the 0.56→0.89 gap between retrieved and gold evidence is closed by ordering alone. Metrics are answer exact match and F1, supporting-fact F1 where annotations exist, model calls per question, and the realized gold-edge bandwidth and backward-dependency count. We found no reported result on Lacuna for any passage-ordering intervention on these benchmarks, so every ordering baseline is run by us.
Three checks are decisive. First, a nonzero distance or direction effect in the stage-one diagnostic with absolute position held fixed; if it is absent, the proposal stops there. Second, a significant gain of query-rooted Cuthill–McKee over PageRank order with the graph held identical. Third, a gap between the full method and level-only order on branching MuSiQue shapes. Only if all three hold should bandwidth, rather than plain hop sorting, be called the operative idea.
References
- MultiHop-RAG: Benchmarking Retrieval-Augmented Generation for Multi-Hop Queries
- Making Long-Context Language Models Better Multi-Hop Reasoners
- Is Graph Structure Necessary for Multi-hop Question Answering?
- LinearRAG: Linear Graph Retrieval Augmented Generation on Large-scale Corpora
- RCM++:Reverse Cuthill-McKee ordering with Bi-Criteria Node Finder
- On Euclidean Embeddings and Bandwidth Minimization
- Inapproximability of Treewidth and Related Problems (Extended Abstract)
- Select Edges Wisely: Monotonic Path Aware Graph Layout Optimization for Disk-based ANN Search
- Interleaving Retrieval with Chain-of-Thought Reasoning for Knowledge-Intensive Multi-Step Questions
- ♫ MuSiQue: Multihop Questions via Single-hop Question Composition