Logo image
Back
Efficient Multi-Hop Question Answering Over Knowledge Graphs via LLM Planning and Embedding-Guided Search
Conference paper

Efficient Multi-Hop Question Answering Over Knowledge Graphs via LLM Planning and Embedding-Guided Search

Manil Shrestha and Edward Kim
IEEE International Conference on Big Data, (2025), pp 5709-5718
08 Dec 2025
DOI: https://doi.org/10.1109/BigData66926.2025.11401920

Abstract

Accuracy Breadth-First Search Cognition Constrained Graph Traversal Costs Knowledge Graph Question Answering Knowledge graphs Large language models Multihop Reasoning Planning Prediction algorithms Production Question answering (information retrieval) Semantics
Multi-hop question answering over knowledge graphs remains computationally challenging due to the combinatorial explosion of possible reasoning paths. Recent approaches rely on expensive Large Language Model (LLM) inference for both entity linking and path ranking, limiting their practical deployment. Additionally, LLM-generated answers often lack verifiable grounding in structured knowledge. We present two complementary hybrid algorithms that address both efficiency and verifiability: (1) LLM-Guided Planning that uses a single LLM call to predict relation sequences executed via breadthfirst search, achieving near-perfect accuracy (micro-F1 >0.90 ) while ensuring all answers are grounded in the knowledge graph, and (2) Embedding-Guided Neural Search that eliminates LLM calls entirely by fusing text and graph embeddings through a lightweight 6.7M-parameter edge scorer, achieving over 100 × speedup with competitive accuracy. Through knowledge distillation, we compress planning capability into a 4B-parameter model that matches large-model performance at zero API cost. Evaluation on MetaQA demonstrates that grounded reasoning consistently outperforms ungrounded generation, with structured planning proving more transferable than direct answer generation. Our results show that verifiable multi-hop reasoning does not require massive models at inference time, but rather the right architectural inductive biases combining symbolic structure with learned representations.

Metrics

1 Record Views

Details

Logo image