Crossing Budgets for Cross-Document Attention in Multi-Hop Retrieval

When a language model answers a question from many retrieved documents, it faces a bind. If every document can read every other, irrelevant passages pull the model toward spurious connections and fabricated answers. If documents are processed in isolation, the model cannot chain facts across passages, which multi-hop questions require. This note proposes a middle path. We draw the retrieved passages in the order they appear in the prompt and let each allowed cross-passage read be an arc over that line. We then choose which arcs to allow using rules from graph drawing that limit how arcs may cross, not just how many there are. Arcs a–c and b–d cross when their spans interleave (a before b before c before d).

The specific rule is borrowed from "beyond-planar" graph drawing, the study of drawings where edges may cross only in restricted ways. Under it, a few "hub" passages, typically the ones holding a bridge entity, may link to many others. Any interleaving must either involve a lightly connected arc or fan out from a single hub, and two heavily crossed links may never interleave. Our hypothesis is that distraction-driven hallucination in multi-hop retrieval tracks the crossing structure of the cross-document dependencies rather than their sheer number. If so, a crossing-budgeted attention mask should match full attention on multi-hop accuracy, fabricate less on unanswerable questions, and keep compute linear in the number of passages. The proposal is built around one decisive control: a degree-matched sparse mask with the same number of arcs. If that control does as well, the geometry is decoration and we will say so.

Core Claim

Restricting cross-passage attention to an outer min-$k$-planar or outer fan-planar arc diagram over the prompt order will beat two things on multi-hop QA. It will beat fully independent passages in answer accuracy, and it will beat full concatenation in fabrication rate on unanswerable questions. It will also beat sparse masks with the same arc count but unconstrained crossings. The new ingredient is treating the interleaving pattern of document-to-document dependencies as the controllable quantity. Prompt order then becomes a design variable: reordering passages changes crossings without changing which passages talk.

Where This Sits

Two systems bracket the design space, and neither controls crossings. Superposition Prompting processes each retrieved document on its own branch from a shared preamble (a fork-join graph), prunes branches by a saliency score, and caches each branch separately. It reports a 93x compute reduction on MPT-7B and a 43% accuracy gain over naive retrieval on NaturalQuestions-Open. Its branches never interact before the final join, however, so a bridge fact in one passage cannot condition the reading of another. That is precisely what MuSiQue was built to require: it composes 2–4 single-hop questions into six reasoning-graph shapes and filters out questions answerable without the intermediate hops. At the other extreme sits plain concatenation, whose collapse with more documents is documented by DAS. DAS fixes this with an abstention instruction plus re-weighting answers by $P(\text{query}\mid\text{document})$, scoring each document independently. Our proposal adds the one thing both sides lack: a controlled set of cross-document links. Superposition supplies the caching machinery we reuse, and DAS motivates the problem.

On the hallucination side, CHARM turns a model's attention into a token graph and runs a message-passing network to detect hallucinated tokens. On NQ it reaches 74.8% AUROC against 71.9% for the best attention heuristic and 73.0% for activation probes, and pruning 98% of low-weight edges barely hurts detection. CHARM motivates us in two ways. Relational structure in attention carries hallucination signal, and that structure is very sparse. Yet CHARM only thresholds edges by weight, never examines how edges interleave, and never intervenes during generation. RAGTruth constrains our evaluation. Its 17,790 annotated responses show that models more often add baseless information than contradict the source. Our main hallucination metric is therefore fabrication (answering when no answer is supported), not contradiction.

The drawing-theory results supply the constraint itself. Min-k-planar Drawings of Graphs defines drawings where, in every crossing pair, at least one edge has at most $k$ crossings and heavy edges never cross each other. It shows this asymmetry admits up to $6n-12$ edges at $k=3$, versus $5.5n-11$ for uniform 3-planarity. Asymmetry buys density without unconstrained crossing, which is the property we want for hub passages. On the Recognition of Fan-Planar and Maximal Outer-Fan-Planar Graphs shows general fan-planarity is NP-hard to recognize but outer (all-vertices-on-a-line-or-circle) variants are tractable. This is why we work only with arc diagrams over the fixed prompt order, where checking a constraint is a cheap computation over interleavings. Graphs Drawn With Some Vertices per Face gives linear edge bounds for outer drawings ($3n-6$ for the $1^+$-real-face case). We use this only as a ceiling on arc count, which keeps prefill cost linear in the number of passages $n$. We do not claim these theorems say anything about language models. They are a vocabulary of crossing rules with known density and tractability, and the empirical question is whether the rules matter.

Research Program

The first stage is diagnostic and is cheap enough to kill the idea early. We run Llama-2-7B-chat and Mistral-7B-instruct, the models CHARM used, with full concatenation on MuSiQue-Full. For each example we aggregate token attention into a passage-level directed graph and keep the top $m$ edges, with $m$ fixed per example so that edge count is controlled. We then compute crossing statistics in the prompt order: total crossings, the number of heavy–heavy crossing pairs (violations of min-$k$-planarity for $k=1,2,3$), and the number of crossings not explained by a fan from one passage.

The test is whether these statistics predict wrong answers and fabricated answers on unanswerable questions. They must do so after controlling for edge count, attention entropy, and gold-passage position, using logistic regression with those covariates. A second, cheap check asks whether crossing features add AUROC on top of a CHARM-style detector. We would read a null here as strong evidence against the whole program.

The second stage is the intervention. Each passage is prefilled on its own branch, as in Superposition Prompting. An allowed arc from passage $i$ to passage $j$ means passage $j$ is re-encoded with passage $i$'s cache visible, and only that pair-level cross-reading is added. Candidate arcs are scored with two signals: a cheap relevance score (entity overlap between passages plus the question) and the model's own attention from a short probing pass. Arcs are then added greedily in descending score, subject to the chosen crossing rule, up to a fixed budget $B$.

Because crossings depend on order, we also include an optional reordering step. Before selecting arcs, it searches over passage permutations to place strongly linked passages so that fewer arcs interleave. This degree of freedom does not exist for degree-capped masks, and it is the second place where the geometric view could earn its keep. The constraints we compare are outer 1-planar (uniform budget), outer min-2- and min-3-planar (asymmetric), and outer fan-planar.

Baselines

The do-nothing reference is naive concatenation of all retrieved passages with standard causal attention. It shows how much distraction there is to remove, and it is also the full-attention upper bound on cross-document interaction. The opposite naive reference is Superposition Prompting with no cross-branch arcs, run with its published equilibrium position assignment and saliency pruning. On NaturalQuestions-Open it reports a 43% accuracy improvement over naive retrieval and 93x lower compute on MPT-7B. On MuSiQue it is described only as often the sole method with non-zero scores on the hardest queries; no reported numeric result was found on Lacuna for Superposition Prompting on MuSiQue, so we will measure it ourselves. Our method must beat it on MuSiQue answer F1 without losing on NQ-Open EM.

The strongest competitor for the hallucination question is DAS. It is training-free, uses the same models, and directly targets fabrication from irrelevant documents; it reports an average 64% relative EM gain over naive zero-shot readers and 231% on SQuAD with 100 DPR-retrieved documents. We run DAS with identical retrieval output and model. We also run it in combination with our mask, since its abstention instruction and query-likelihood re-weighting are orthogonal to masking. Beating it means lower fabrication rate on MuSiQue-Full unanswerable questions at equal or better answerable F1. Matching it alone but improving it when combined would still count as a contribution.

The ablation that isolates the key ingredient is a degree-capped mask with exactly $B$ arcs selected from the same candidate scores. It gives each passage at most $\lceil 2B/n\rceil$ links and applies no crossing rule. We pair it with a "crossing-matched random" mask that has the same arc count and the same number of crossings but random endpoints, which separates arc choice from interleaving. All masked variants share the same candidate scorer, the same arc budget, the same number of re-encoding passes (so wall-clock compute is equal), and a single shared tuning sweep over $B$ and $k$ on a held-out MuSiQue dev split. A final ablation turns the reordering step on and off for both the constrained and degree-capped masks.

Why not just…?

Why not just cap each passage's degree and skip the geometry? This is the real threat. A per-passage degree cap gives the same linear compute and the same sparsity, and it may capture most of the benefit. The degree-capped and crossing-matched random masks above are designed to settle it. If the constrained mask does not beat the degree cap by more than seed-to-seed variance on MuSiQue F1 and fabrication rate, we will report that crossing structure adds nothing, and retain only the diagnostic finding (if any) from the first stage. The one place the geometry can win that degree caps cannot is through reordering, which is why reordering is ablated separately.

Why not just retrieve fewer passages? Truncation trades away recall. MuSiQue spreads evidence over two to four passages, and its single-hop model drops 30 F1 points relative to HotpotQA, showing that missing a hop is fatal. We include top-3 and top-5 truncation runs to show this directly on the same retriever output.

Why not just add an abstention instruction, as DAS does? DAS needed query-likelihood re-weighting on top of the instruction, and it scores documents in isolation, so it cannot verify a chain across passages. We run DAS as the main hallucination baseline and in combination with our mask, so any additive effect is visible rather than argued.

Why not just add a merge step to Superposition Prompting? A single join at the end is the existing method. Merging every pair is full concatenation. Choosing which pairs to merge is exactly our arc-selection problem, so the question becomes whether crossing rules select better than relevance scores alone, which is the degree-capped comparison again.

Proposed Experiments

The primary benchmark is MuSiQue-Ans and MuSiQue-Full with their provided distractor paragraphs. We report answer F1, support F1 (against the 78.0 answer and 93.9 support F1 human reference from the MuSiQue paper), and fabrication rate on unanswerable contrast questions, broken down by the six reasoning-graph shapes. We expect the gains of asymmetric and fan rules to concentrate on tree- and DAG-shaped questions, where one bridge passage must reach several others, and to vanish on simple chains. NaturalQuestions-Open with 20–100 retrieved passages is the single-hop sanity check: the method must not fall below Superposition Prompting there. For free-form faithfulness we use the RAGTruth QA prompts (MS MARCO passages) and score generations with a span detector fine-tuned on RAGTruth annotations, following that paper's recipe. Its reported detector reaches 52.7% span F1 versus 28.3% for GPT-4, so we treat detector scores as noisy and spot-check a stratified sample by hand.

The decisive checks are three. First, in the diagnostic stage, heavy–heavy crossings must predict fabrication beyond edge count, entropy, and position. Second, at matched arc budget and compute, the constrained mask must beat the degree-capped and crossing-matched random masks on MuSiQue tree/DAG questions. Third, the asymmetric (min-$k$) and fan rules must outperform the uniform 1-planar rule, which tests whether hub passages are what make the structure useful. Failing the first check ends the program. Passing the first but failing the second means crossings are a symptom worth detecting, not a lever worth controlling, and the work would be redirected toward adding crossing features to CHARM-style detectors.