Efficient subgraph search improves multi-hop knowledge base question answering
Efficient LLM-based Subgraph Retrieval for Multi-Hop Knowledge Base Question Answering
Information Retrieval
Summary
Finding answers that require multiple steps in a large knowledge database can be slow and include irrelevant information. The authors developed a new method using AI models to more carefully pick the important pieces of information to look at. Their approach uses a tree search strategy guided by a large language model to focus on relevant data, which keeps the search faster and more accurate. Tests show this method improves accuracy while using fewer resources.
What this means in practice
- •For knowledge base developers: Build more efficient question-answering systems that find correct answers faster by focusing on relevant subgraphs in large knowledge bases.
- •For ai system architects: Design AI systems that integrate large language models with tree search to improve multi-step retrieval tasks involving complex knowledge graphs.
Authors
Duanyang Yuan, Sihang Zhou, Xiaoshu Chen, Haoyuan Chen, Ke Liang, Jian Huang
Abstract
Multi-hop Knowledge Base Question Answering (KBQA) aims to find answer entities in the knowledge base that are multiple hops away from the entities in the question. Information retrieval-based (IR-based) methods extract a pivotal subgraph from the entire KB to locate candidate answers and then evaluate their plausibility through semantic matching with the question. However, we observed that the extracted subgraphs often include nodes that are weakly related or irrelevant to the question. Without a proper node filtering mechanism, the number of irrelevant nodes grows as the number of hops increases, leading to excessive consumption of computational resources. To address these challenges, this study introduces an efficient LLM-based subgraph retrieval method for multi-hop knowledge base question answering, M-ER. The framework leverages Monte Carlo Tree Search (MCTS) to transform subgraph exploration into a tree-structured search process. During the MCTS selection phase, nodes that are highly relevant to the question are prioritized for inclusion in the subgraph, eliminating the need to traverse all nodes in the KB. The framework further incorporates a large language model (LLM) to refine the search direction, ensuring that exploration remains focused on nodes relevant to the question. In addition, selected nodes are quantitatively scored, and these scores are fed back into the node selection process to effectively filter out irrelevant candidates, thereby improving the quality of the subgraph. This mechanism not only narrows the search space but also enhances the overall efficiency of multi-hop KBQA. Experiments on the WebQSP benchmark demonstrate that M-ER achieves 78.88\% on the Hits@1 metric, while also improving computational efficiency. These results not only validate the effectiveness of M-ER, but also offer a viable technical path to balance performance and computational efficiency.