A Matryoshka Hierarchical RAG for Efficient Multi-Hop Question Answering

1. Introduction

• Multi-hop QA requires aggregating entity- or relationship-linked evidence across documents, which single-document similarity and flat indices do not capture well.Graph-based and hierarchical approaches address this with structured retrieval but incur offline construction or summarization costs and online retrieval costs.Source: §1 · p. 2
• MRL embeddings retain useful information in shorter prefixes, enabling progressively coarser hierarchy levels to use lower-dimensional representations.The proposed alignment keeps full-dimensional embeddings for individual documents while using shorter prefixes for upper levels.Source: §1 · p. 2
• MatRAG organizes documents into a density-based clustering DAG, with progressively lower-dimensional centroids at internal levels and full-dimensional document embeddings at leaves.Top-down traversal truncates the query embedding to each level's dimension, reducing coarse-level similarity cost; entity signals control documents collected per hop and rerank candidates.Source: §1 · pp. 2–3
• MatRAG achieved the highest Exact Match and F1 scores across HotpotQA, 2WikiMultiHopQA, and MuSiQue, while improving Recall@5 over document-retrieval baselines.It also reduced average response time versus flat FAISS-based retrieval and substantially lowered indexing costs versus graph-based and hierarchical approaches.Source: §1 · p. 3
• MatRAG aligns MRL dimensions with index depth and expands retrieved context through hierarchical search rather than graph-based multi-hop traversal.Its entity-aware reranking prioritizes candidate nodes and controls retrieval drift across iterations.Source: §1 · p. 3

2.1. Retrieval-Augmented Generation and Multi-Hop QA

• Multi-hop RAG ranges from single-pass retrieval to iterative retrieval and reasoning; planning and query expansion can incur repeated LLM calls and query drift.MatRAG instead uses entity counts for retrieval budgets, entity overlap for reranking, and an anchoring schedule that strengthens the original query.Source: §2.1 · p. 4

2.2. Graph-Based RAG

• Graph-based RAG builds knowledge graphs from extracted entities and relations, with systems varying in graph granularity and retrieval strategy.MatRAG uses entities as lightweight signals for budget control and reranking without constructing an explicit knowledge graph.Source: §2.2 · pp. 4–5

2.3. Hierarchical RAG

• Prior hierarchical RAG systems commonly use one embedding dimension across levels and LLM calls to represent internal nodes.MatRAG computes internal nodes as child centroids and assigns lower dimensions to coarser clusters, retaining full dimensions for documents.Source: §2.3 · p. 5

2.4. Matryoshka Representation Learning for Retrieval

• Prior retrieval uses of MRL select one deployment dimension and apply it uniformly across a task.MatRAG instead uses progressively shorter MRL prefixes at coarser levels of a hierarchical clustering index.Source: §2.4 · p. 6

3.1. Hierarchical Indexing

• The index organizes document embeddings and entity sets in a layered DAG, using full-dimensional document vectors at leaves and progressively shorter MRL prefixes for internal centroids.HDBSCAN builds clusters, and nodes can link to multiple nearby clusters to provide redundant paths during traversal.Source: §3.1 · pp. 6–9

3.2. Entity-Budgeted Retrieval

• Each retrieval iteration uses newly observed entities to guide the next step and sets its document count from the frontier size, subject to the remaining total budget.Retrieved documents and their entities accumulate until the budget is reached or no frontier entities remain; the final set is passed with the query to an LLM.Source: §3.2 · pp. 9–10

3.3. Multi-Signal Document Scoring

• Retrieve traverses the DAG using a score that combines original-query and cumulative-query similarity, then re-ranks leaf documents with semantic and entity-overlap signals.Candidates are ranked by the final score and limited to the iteration's retrieval count.Source: §3.3 · p. 10, §3.3.2 · pp. 12–13

3.3.1. Computation of the traversal score

• The traversal score combines similarity to the original query and cumulative query, with the original-query weight increasing as retrieved context accumulates to limit semantic drift.At each level, the highest-scoring centroid narrows the search to connected nodes at the next level; lower-dimensional representations and smaller candidate sets reduce coarse-level similarity cost.Source: §3.3.1 · pp. 11–12

3.3.2. Computation of the re-ranking score

• At the document level, the re-ranking score combines semantic similarity with Jaccard overlap between candidate-document entities and newly observed entities.The Retrieve function returns the top documents within the iteration's budget, ranked by this combined score.Source: §3.3.2 · pp. 12–13

• The campaign describes its setup, examines main hyperparameters, reports main results, and evaluates component contributions in an ablation study.Source: §4 · p. 13

4.1. Experimental Setup

• The setup specifies datasets, comparison baselines, MatRAG implementation choices, and evaluation metrics.Source: §4.1 · p. 13

4.1.1. Datasets

• Experiments use HotpotQA, 2WikiMultiHopQA, and MuSiQue, with five independent 1,000-question samples per benchmark and a separate 500-question validation set.The datasets provide gold answers and supporting documents; the three benchmarks cover bridge/comparison, compositional, and shortcut-resistant reasoning, respectively.Source: §4.1.1 · p. 13

4.1.2. Baselines

• MatRAG is compared with seven systems spanning flat, hierarchical, graph-based, and reasoning-augmented RAG, with the same generative model used for all baselines.Baselines follow their original implementations and reported hyperparameter settings.Source: §4.1.2 · p. 14

4.1.3. Implementation Details

• The implementation uses nomic-embed-text-v1.5 at dimensions 64, 128, 256, 512, and 768, with K = 10, p = 2, and α = 0.5 across datasets.Experiments ran on an NVIDIA A100 GPU with 40 GB VRAM and 128 GB system RAM.Source: §4.1.3 · p. 14

4.1.4. Metrics

• Answer quality is measured by Exact Match and token-level F1, retrieval by Recall@2 and Recall@5 where document overlap is defined, and efficiency by indexing time, response time, and LLM context size.Retrieval metrics are limited to systems that retrieve corpus documents directly; other systems return units not comparable to gold supporting documents.Source: §4.1.4 · pp. 14–15

4.2. Hyperparameter Analysis

• Increasing K from 5 to 10 raised EM by 16.34% on HotpotQA, 19.25% on 2Wiki, and 21.36% on MuSiQue, while Tok also increased.Tok rose by 108.00% on HotpotQA, 104.03% on 2Wiki, and 102.26% on MuSiQue; the authors chose K = 10 but not a larger value to limit efficiency costs.Source: §4.2 · p. 15, Table 1 · p. 16
• p = 2 performed best, improving F1 and EM over p = 1 across all three benchmarks; increasing p beyond 2 brought no further gains.The reported F1 (EM) improvements were 3.04% (5.65%) on HotpotQA, 4.85% (7.63%) on 2Wiki, and 8.20% (9.65%) on MuSiQue.Source: §4.2 · p. 16, Table 2 · p. 16
• α = 0.50 produced the best overall results across benchmarks, outperforming both similarity-only and entity-only ranking.The analysis attributes this result to balancing semantic similarity with entity overlap.Source: §4.2 · p. 17, Table 3 · p. 17

4.3. Comparison Results

• On MuSiQue, MatRAG surpassed the best retrieval baseline by 14.48% on R@2 and 13.37% on R@5.It also achieved the best R@5 on 2Wiki by 1.89% over HippoRAG2, while its R@2 was 0.51% below NaiveRAG.Source: §4.3 · p. 18, Table 4 · p. 18
• MatRAG achieved the best EM and F1 across all three benchmarks, including gains over the strongest baseline of 5.71% EM and 14.89% F1 on 2Wiki.On HotpotQA, it improved EM over NaiveRAG by 14.04% and F1 over LightRAG by 10.68%; on MuSiQue, it improved EM by 4.58% and F1 by 12.94% over HippoRAG2.Source: §4.3 · p. 18, Table 5 · p. 19
• MatRAG reduced indexing time by over 99.60% versus HippoRAG2 across all datasets, but remained slower than NaiveRAG.The comparison covers indexing time on the full corpus of each benchmark.Source: §4.3 · p. 18, Table 6 · p. 19
• MatRAG had the fastest response time across all methods, while using slightly more tokens than NaiveRAG on HotpotQA and 2Wiki.Its response time was faster than NaiveRAG by 47.44% on HotpotQA, 35.82% on 2Wiki, and 35.14% on MuSiQue; context length was lower than GraphRAG by over 79.33% on HotpotQA.Source: §4.3 · pp. 19–20, Table 7 · p. 20

4.4. Ablation Analysis

• The adaptive query anchor achieved the optimal trade-off across datasets and metrics, while using only the original or expanded query was suboptimal.The authors report semantic drift when relying only on the expanded query and reduced incorporation of newly discovered contexts when using only the original query.Source: §4.4 · p. 21, Table 8 · p. 22
• Matryoshka prefixes produced similar clustering quality to full-dimensional embeddings at every level, with slightly better DB and Sl scores in most benchmark-level combinations.The authors report that truncation did not degrade hierarchy cluster quality.Source: §4.4 · pp. 21–22, Table 9 · p. 23
• Matryoshka-truncated embeddings achieved better or comparable QA and retrieval performance while reducing response time versus full-dimensional embeddings.The authors attribute the result in part to relevant information being concentrated in leading dimensions; they also report similar or better clustering quality with truncated prefixes.Source: §4.4 · pp. 22–23, Table 10 · p. 23, Table 11 · p. 24

5. Discussion

• MatRAG outperforms baselines on most metrics while using lower-dimensional embeddings at upper DAG levels, supporting the hypothesis that coarser clusters need shorter MRL prefixes.The largest improvements occur on MuSiQue, where single-document similarity may be insufficient to identify the relevant evidence chain.Source: §5 · p. 24
• Entity-Jaccard and semantic similarity complement each other: α = 0.50 is optimal across datasets, while either signal alone performs poorly.Adaptive anchoring interpolates between the original query and retrieved context to use that context while preventing semantic drift; static scoring is insufficient.Source: §5 · p. 24
• Truncated-prefix clusters are competitive with full-dimensional clusters and have lower DB indices and higher Silhouette scores in several configurations.The authors argue that truncation removes redundant dimensions at coarser levels, reducing similarity-computation cost without compromising hierarchy quality.Source: §5 · pp. 24–25
• Across all benchmarks, truncated Matryoshka embeddings achieve better QA metrics and retrieval recall than full-dimensional embeddings while reducing response time.The authors attribute this to relevant information concentrated in leading dimensions and describe truncation as implicit regularization.Source: §5 · p. 25
• Co-designing embeddings and index structure partially bridges cheap flat and expensive structured retrieval; lightweight entity signals proxy LLM reasoning, while graph-comparable retrieval avoids explicit KGs, entity linking, and LLM summarization.The authors describe dimension-depth coupling as a productive inductive bias that requires no additional trainable parameters or training.Source: §5 · pp. 25–26
• GLiNER may miss domain-specific entities; cluster quality depends on embedding density, and greedy traversal can exclude relevant documents when the correct branch is absent from selected parents.The traversal commits to a branch without backtracking; overlapping assignments provide redundant paths but no recovery if the correct parent branch is not selected.Source: §5 · p. 26

6. Conclusion

• MatRAG aligns progressively shorter MRL prefixes with DAG cluster levels, using entity-count budget control, entity-overlap reranking, and adaptive anchoring that increasingly weights the original query as budget is consumed.Source: §6 · p. 26
• Over 35.14% lower query-time latency than NaiveRAG and orders-of-magnitude lower indexing time than graph-based methods accompany superior retrieval and answer quality across three benchmarks.Source: §6 · p. 26
• Future work will explore query-dependent retrieval budgets, adaptive cluster connectivity, and query-dependent anchoring schedules.Source: §6 · p. 27