A Matryoshka Hierarchical RAG for Efficient Multi-Hop Question Answering
Gianluca Bonifazi, Christopher Buratti, Michele Marchetti, Federica Parlapiano, Giulia Quaglieri, Davide Traini, Domenico Ursino, Luca Virgili
cs.CL, cs.IR
2026-10-01
MatRAG matches Matryoshka prefixes to cluster-DAG depth and steers hops with entity counts; it leads EM/F1 on three multi-hop QA benchmarks and cuts latency 35-47% vs FAISS.
Multi-hop QA has to chain evidence scattered across documents, and single-round dense retrieval cannot see across those documents: the similarity between one query and one document says nothing about where the next hop lives. Two families of fixes exist. Graph-based systems (GraphRAG, LightRAG, HippoRAG2) build a knowledge graph offline and walk it at query time; hierarchical systems (RAPTOR) organize the corpus into a tree whose internal nodes are LLM-written summaries. Both deliver quality and both are expensive: entity linking and relation extraction for the graph, recursive LLM calls for the tree, LLM-driven planning at query time.
The cost is concrete. On the HotpotQA corpus (9,811 documents), GraphRAG spends 661,392 seconds indexing and LightRAG 728,471, between seven and a half and eight and a half days; HippoRAG2 averages 76.84 seconds per question.
MatRAG aligns the nested structure of MRL (Matryoshka Representation Learning: any prefix of an embedding is a usable representation on its own) with the granularity of a clustering hierarchy.
Offline indexing:
The rationale: coarse clusters hold semantically mixed content, and ranking candidates inside them needs only coarse signal, which short prefixes carry. Full dimensionality is reserved for the leaves, where individual documents are ranked.
Online retrieval runs as a loop:
Setup: three benchmarks, seven baselines, one shared generator (gemma3:27b via Ollama), five samples of 1,000 questions per benchmark.
| System | HotpotQA EM/F1 | 2Wiki EM/F1 | MuSiQue EM/F1 |
| MatRAG | 60.50 / 73.66 | 52.70 / 63.42 | 27.40 / 37.89 |
| NaiveRAG (flat FAISS) | 53.05 / 64.50 | 44.10 / 48.15 | 20.65 / 29.55 |
| HippoRAG2 | 52.40 / 64.10 | 49.85 / 55.20 | 26.20 / 33.55 |
| LightRAG | 52.15 / 66.55 | 45.35 / 50.80 | 21.85 / 31.80 |
First on all six columns. Retrieval R@5: 89.30 on HotpotQA (NaiveRAG 84.10), 79.27 on 2Wiki (HippoRAG2 77.80), 57.08 on MuSiQue (NaiveRAG 50.35). The one retrieval metric it drops is R@2 on 2Wiki, 63.08 against NaiveRAG's 63.40. MuSiQue is built to defeat shortcut retrieval, and there MatRAG leads R@2 by 5.4 points, the clearest direct evidence that hierarchical traversal pays off.
| Metric (HotpotQA) | MatRAG | Reference |
| Response time | 1.85s | NaiveRAG 3.52s; HippoRAG2 76.84s |
| Indexing time | 316s | GraphRAG 661,392s; NaiveRAG 98s |
| Tokens sent to the LLM | 788 | GraphRAG 3,812; LightRAG 5,841 |
Response time beats flat FAISS by 47.4%, 35.8%, and 35.1% across the three benchmarks, and beats HippoRAG2 by more than 96%. Indexing is slower than NaiveRAG (316 vs 98 seconds) in exchange for retrieval quality. Two ablations support the design: clusters formed from truncated prefixes score slightly better on Davies-Bouldin and Silhouette than full-dimensional clusters, and the adaptive anchor beats both fixed variants (F1 73.66 vs 72.25 and 71.24 on HotpotQA).
Between cheap flat retrieval and expensive structured retrieval there was no middle option; MatRAG takes it, keeping the quality of structure while skipping the KG bill and the LLM planning bill. The more transferable piece is the use of MRL itself. Prior work picked one deployment dimension and applied it uniformly across the pipeline; assigning dimensions by index level is a new pattern, requires no extra training, and works with off-the-shelf models.
It fits multi-hop QA over scattered evidence, latency-sensitive online retrieval, and domains where KG construction is impractical. Single-hop factual lookups gain little here. Retrieval-quality gains over the strongest baselines sit mostly in the 1-to-5-point range, which is incremental; cutting query latency to roughly half of flat FAISS and indexing cost by about three orders of magnitude versus graph systems is the substantive engineering win.
The authors list three: GLiNER can fail on domain-specific terminology, and those errors propagate into budget control and re-ranking; corpora with uniform semantic distributions yield weak clusters and a less discriminative DAG; the greedy top-down traversal has no backtracking, so a wrong branch at a coarse level locks relevant documents out when the correct parent is not among the p=2 redundancies.
A closer read raises more. The corpora hold 6,119 to 11,656 documents, four to five orders of magnitude below production RAG, and flat FAISS shows no scale advantage at this size, so whether the latency win survives million-document corpora is untested, as is HDBSCAN's cost at that scale. Baseline hyperparameters follow the original papers without retuning, which may undervalue the graph systems. The claim that entity counts replace LLM planning was tested only against graph agents like ToG and KGP, not against iterative planners over dense retrieval such as IRCoT or FLARE.