Hypertree Decompositions as Context Schedules for Multi-Hop Question Answering

A question answering system that must chain facts across several documents faces two problems at once. Its retrieved passages rarely fit in one reader call. And the passages that need to be read together are often linked only by an entity that each one names differently. Current systems cut the evidence into window-sized pieces with heuristics, or stuff everything into one long prompt. Either way, nothing guarantees that two passages sharing a bridge entity ever meet in the same reader call. Database theory has a precise tool for this situation. A hypertree decomposition arranges a hypergraph (a graph whose "edges" can join many nodes at once) into a tree of small groups, called bags. Every hyperedge fits inside some bag, and each node's bags form a connected piece of the tree. A join can then be computed by passing small messages up the tree instead of materializing everything at once.

We propose to treat the retrieved evidence for a question as such a hypergraph, with entities as nodes and passages as hyperedges. Under this view, a decomposition of generalized hypertree width $k$ is a schedule of reader calls in which each call sees at most $k$ passages, no passage is ever split, and every bridge entity's information flows along a connected path of calls. The lexical gap is the obstacle. If "JFK", "Kennedy" and "the 35th president" are separate nodes, the decomposition misses the bridge. If they are joined by similarity edges, width blows up. We resolve this by merging synonymous mentions into a single node with locality-sensitive hashing (LSH), which hashes similar items into the same bucket in sublinear time, instead of adding edges between them.

Core Claim

The claim has two parts, each testable on its own. First, empirical: after LSH-based mention merging, the evidence hypergraphs of genuinely multi-hop questions have small generalized hypertree width (we expect 2–3) and bounded pairwise intersections. Adding embedding-similarity edges instead, as PropRAG does, raises both. Second, practical: under a fixed per-call context budget, a reader that follows the decomposition with bottom-up message passing beats a reader that packs the same passages into windows by greedy overlap clustering. It also beats truncation and, at equal total tokens, one long-context call. It should lose less accuracy as the budget shrinks.

The new piece is using width as a context-packing quantity. Generalized hypertree width counts how many passages a reader must hold at once so that bounded message passing can still solve the question exactly. Each of the three directions plays a distinct role. Width recognition supplies the mechanism and its guarantee. LSH supplies the canonicalization that keeps the hypergraph sparse enough to decompose. Context window constraints are the regime in which the guarantee pays off.

Relation to Prior Work

Three multi-hop retrieval systems motivate the gap without closing it. HGRAG builds exactly our entity-node, passage-hyperedge hypergraph. It then ranks with Laplacian diffusion and heuristic enhancement modules and never examines the hypergraph's width or tree structure. We keep its representation but replace diffusion-then-concatenate with decomposition-then-schedule. PropRAG bridges synonyms by linking entity embeddings and searches proposition paths with beam search. Its similarity links are the dense, high-degree construction that we argue destroys tractability, and our ablation tests that directly. StepChain GraphRAG controls context growth with question decomposition and lazy breadth-first expansion, which is greedy and lets early errors cascade. A tree decomposition fixes the global order of reading before any call is made.

The method comes from two sources. The first is Enhancing Datalog Reasoning with Hypertree Decompositions. It stores partial joins at decomposition nodes and reports 75x–793x speedups on cyclic rules, with no cost on acyclic ones but up to 2.3x memory. We borrow its routing idea: acyclic evidence goes to a plain path reader, cyclic evidence goes to the decomposition reader. Its memory cost reappears for us as the token cost of messages. The second source is the theory of width recognition, which constrains what we can compute. Deciding generalized hypertree width at most 2, and fractional width at most $k$ for any fixed $k \ge 2$, is NP-complete (Gottlob et al.). Deciding plain hypertree width at most $k$ is W[2]-hard, meaning no algorithm is expected to run in time polynomial for every fixed $k$ (Schidler). These are worst-case results.

Our per-question hypergraphs have tens of passages, so exact SAT-based decomposition in the style of Schidler is affordable. For corpus-scale or larger evidence pools, we rely on two tractable cases. Gottlob et al. show that checking a decomposition of width $k$ is tractable under the bounded intersection property, where any two hyperedges share at most a fixed number $d$ of nodes. Lanzinger and Razgon give a fixed-parameter $O(k^3)$ approximation for hypergraphs where pairwise intersections are bounded by $d$. Whether real evidence hypergraphs have small $d$ is an empirical question no one has asked, and our canonicalization step is designed to keep $d$ small.

The LSH side is constrained by LSH for Long Context NMT. That work found that hashing produces false negatives. It found the losses worse when queries and keys come from different distributions. And it found that longer contexts up to 12 sentences did not consistently improve translation. We therefore use LSH only offline, for mention canonicalization, not inside attention. We use multiple hash tables to control missed merges, and we measure missed bridges directly, since one missed bridge breaks a chain. Min-hashing over character n-grams, where two items collide with probability equal to their Jaccard set overlap, has been used to cluster concepts and partition text (NeuroCartography, Reinforced Co-Training). Random-hyperplane hashing approximates the angle between vectors (DeepCAM). We combine the two to catch surface variants and paraphrased names respectively. The size of the lexical gap is documented by WikiQA, where 20.3% of correct answer sentences share no content word with the question.

Research Program

The pipeline has four stages. In the first, a fixed retriever returns a candidate pool of passages per question, and we extract entity mentions with a light tagger rather than an LLM, to avoid PropRAG-scale indexing cost. In the second, mentions are canonicalized. Each mention is hashed by min-hash on character n-grams and by random hyperplanes on a contextual mention embedding. Mentions that collide in enough tables, and pass a cheap verification of embedding cosine above a threshold, are merged into one node.

In the third stage, we build the hypergraph $H=(V,E)$, with $V$ the merged entities and each passage $e \in E$ the set of entities it mentions. We compute a generalized hypertree decomposition of minimum width under a token-weighted objective. The objective is

$$\min_{T}\ \max_{t \in T} \sum_{e \in \lambda(t)} \ell(e),$$

where $T$ ranges over valid decompositions, $\lambda(t)$ is the set of passages assigned to cover bag $t$, and $\ell(e)$ is passage $e$'s length in tokens. A decomposition is feasible for a reader with window $W$ when the per-bag cost plus message overhead stays below $W$. We solve this exactly with a SAT encoding when $|E|$ is small and with the bounded-intersection approximation otherwise. The fourth stage runs the reader bottom-up. Each bag's call sees its $\lambda(t)$ passages, the question, and its children's messages. It emits a short message restricted to facts about the entities in the separator, meaning the entities it shares with its parent bag. This is the analogue of a semijoin in the Yannakakis algorithm. The root call answers.

The analysis component is a measurement study on MuSiQue, HotpotQA and 2WikiMultiHopQA. We report the distribution of measured width, the maximum pairwise intersection $d$, and node degree under three conditions: no canonicalization, LSH merging, and embedding-similarity edges. This study is useful even if the reader results are mixed. It establishes whether retrieval hypergraphs fall into the classes where width recognition is tractable, which no paper in this space has checked.

Baselines

The naive reference point is truncation: concatenate the ranked pool and cut at window $W$. Truncation is known to drop deep evidence, and it shows what happens with no structure at all.

The strongest existing system on MuSiQue in our file is PropRAG, which reports 53.9% zero-shot F1 on MuSiQue and 64.9% average F1 across five datasets (PropRAG). It is the strongest competitor because it targets both the lexical gap and multi-hop chaining without LLM calls at query time. For HGRAG, the file gives only a relative improvement over HippoRAG 2 and a 6x retrieval speedup, so no reported result was found on Lacuna for an HGRAG MuSiQue F1. We will rerun it. For StepChain GraphRAG, the file reports only gains of 2.57 EM and 2.13 F1 over HopRAG, with no absolute value. We will rerun it as the greedy-traversal competitor.

For fairness, all systems use the same NV-Embed-v2 first-stage pool, the same reader LLM, and the same per-call window $W$. Total reader tokens are matched within 10%: we give baselines extra calls or extra pool depth until the budgets match. Each system's hyperparameters get the same tuning budget on a held-out MuSiQue development slice. Beating PropRAG means exceeding its F1 under our matched reader at $W \le 4\text{k}$ tokens, and not losing at larger $W$. We will also report against its published 53.9% while noting the reader difference.

Two ablations isolate the key ingredients. Greedy overlap packing uses the same canonicalized hypergraph, groups passages into window-sized clusters by entity overlap, and then runs the same message-passing reader over a spanning tree of the clusters. It differs from our method only in lacking the decomposition's guarantee that each entity's bags are connected. Similarity-edge canonicalization replaces LSH merging with PropRAG-style embedding links while keeping our decomposition reader. It tests the claim that merging, not linking, keeps width low. A third ablation swaps LSH for exact nearest-neighbor merging, to separate LSH's accuracy effect from its cost effect.

Why not just…?

Why not just put all retrieved passages into one long-context model? This is the most serious threat. For MuSiQue-sized pools of roughly 20 passages, a modern long-context reader can fit everything. Late chunking shows that long context helps when it is used well: ModernBERT with in-sequence negatives reaches 75.6 nDCG@10 on ConTEB against 52.0 for independent chunks (Context is Gold). Against that, the NMT study found that longer context stopped helping beyond a few sentences. We settle the question with a budget sweep: per-call windows of 1k, 2k, 4k, 8k and the full pool, plotting F1 against window size. If single-call stuffing matches the decomposition reader at equal total tokens across the sweep, we narrow the claim to the small-window regime, such as edge readers or very large pools. We also scale the pool to 100 passages, where single-call stuffing no longer fits.

Why not just score passages independently and keep the top ones? QUARK reaches 72.26 joint F1 on the HotpotQA distractor setting without any graph reasoning (A Simple Yet Strong Pipeline for HotpotQA). However, MuSiQue's disconnected-reasoning filters cause a 30-point F1 drop for single-hop models (MuSiQue). This is why MuSiQue is our primary benchmark. We include an independent-scoring baseline. We expect it to be competitive on HotpotQA, and to lag specifically on the high-width MuSiQue questions.

Why not just cluster passages by overlap, with no width theory? If greedy overlap packing performs as well, the decomposition adds nothing, and we will say so. To find out, we measure a bridge-split rate: the fraction of gold bridge entities whose gold passages land in bags that are not connected by a path that carries that entity. The decomposition guarantees this rate is zero relative to its own hypergraph, so any remaining splits come from canonicalization errors. Greedy packing has no such guarantee. The comparison is meaningful only if greedy packing's split rate is substantially nonzero and the split questions account for its accuracy gap.

Why not just add synonym edges, which already works in PropRAG? It works for beam search. Our hypothesis is that it inflates intersections and width enough that no small-window schedule exists. The similarity-edge ablation measures width and $d$ directly. If width does not grow, the LSH-merging argument is moot and LSH matters only for speed.

Proposed Experiments

The primary benchmark is MuSiQue-Ans, using answer F1, EM and support F1. We stratify questions by measured width and by the six reasoning-graph shapes in MuSiQue, with human performance of 78.0 answer F1 as the ceiling. HotpotQA in the fullwiki and distractor settings and 2WikiMultiHopQA are secondary. For lexical-gap analysis, we report results separately on questions whose bridge entity appears under different surface forms across its gold passages. This mirrors the zero-overlap slice WikiQA identified. Cost metrics are total reader tokens, maximum tokens per call, number of calls, decomposition wall-clock time, and LSH table memory.

Four results decide the proposal. First, the measured width of MuSiQue evidence hypergraphs after LSH merging should be at most 3 for most questions, with $d$ small, and should be measurably higher under similarity edges. If width is routinely large, the scheduling idea fails on real data. Second, at $W$ of 2k–4k, the decomposition reader should beat greedy overlap packing at matched tokens, and the gain should concentrate on questions where greedy packing splits a bridge. Third, the gap to single-call long-context reading should shrink or reverse as $W$ falls and the pool grows. A flat gap across the sweep would limit the contribution to the measurement study. Fourth, LSH merging should come within one F1 point of exact nearest-neighbor merging while canonicalizing faster, and its missed-merge rate on gold bridges should be reported. Missed merges are the false-negative failure that the NMT work warns about, and here they translate one-for-one into broken chains.