Matrag improves multi-step question answering efficiency with hierarchical retrieval
A Matryoshka Hierarchical RAG for Efficient Multi-Hop Question Answering
Computation and LanguageInformation Retrieval
Summary
Multi-hop question answering means finding answers that require multiple steps or pieces of information. The authors introduce MatRAG, a new approach that organizes the information into layers of clusters, like nested boxes, and searches from broad to specific to find answers. This method reduces the cost of preparing and searching the data while keeping the answers accurate. It avoids costly techniques like knowledge graphs or using large language models to summarize the information beforehand.
What this means in practice
- •For enterprise search teams: Create efficient search tools that find precise answers needing multiple facts by organizing documents in hierarchical clusters reducing computation time.
- •For legal document analysts: Speed up retrieval of complex multi-part answers from large sets of legal documents without relying on costly knowledge graphs or language model summaries.
Authors
Gianluca Bonifazi, Christopher Buratti, Michele Marchetti, Federica Parlapiano, Giulia Quaglieri, Davide Traini, Domenico Ursino, Luca Virgili
Abstract
Retrieval-Augmented Generation (RAG) systems for multi-hop Question Answering (QA) must balance retrieval quality with computational cost. This cost is incurred during indexing time, through the use of expensive Knowledge Graphs (KGs) or Large Language Models (LLMs) to generate summaries, or during querying, through iterative LLM-driven retrieval. To reduce it while maintaining retrieval quality, we present MatRAG, a hierarchical framework that combines RAG systems with Matryoshka Representation Learning (MRL). MatRAG addresses both kinds of cost by aligning the semantic hierarchy of a clustering structure with the nested structure of MRL. Specifically, it organizes the corpus of documents into a Directed Acyclic Graph (DAG) of clusters with progressively coarser granularity. Each level is indexed by a lower Matryoshka dimension. MatRAG pairs an iterative, top-down traversal of the DAG with an entity-driven mechanism that controls the hop budget and re-ranks candidates. We evaluated MatRAG on three standard multi-hop QA benchmarks against seven representative baselines. MatRAG outperforms its strongest competitors in terms of retrieval quality; furthermore, it reduces indexing costs by avoiding KG construction and LLM-based summarization, and lowers query-time costs through dimension-aware similarity.