Enhancing Large Language Models Reasoning via Multi-Path Optimization on Knowledge Graph

Large language models (LLMs) have demonstrated remarkable reasoning and generation capabilities in various natural language tasks. However, they often struggle with hallucinations or reasoning errors, particularly when handling domain-specific knowledge or complex multi-hop reasoning. The integration of knowledge graph (KG) provides LLMs with structured and reliable contextual knowledge, effectively mitigating issues of factual accuracy and incomplete reasoning chains. Nevertheless, existing KG-guided LLM reasoning methods still face challenges, including narrow answer coverage, limited accuracy in multi-hop reasoning, and inefficiency caused by frequent LLM API calls. To address these problems, we propose ELMK (Enhancing Large language models reasoning via Multi-path optimization on Knowledge graph), a novel KG-based LLM reasoning method that improves output comprehensiveness and interpretability. ELMK follows a retrieval–embedding–reasoning pipeline. First, depth-first search is used to extract relevant reasoning graphs, then a multi-path encoder is trained to semantically encode the question and candidate paths for precise path selection. Subsequently, the multi-path exploration strategy divides paths into multiple semantic clusters and selects the most similar paths from each cluster to ensure diverse coverage and complete answers. Finally, these paths are combined with prompts to guide LLMs toward reliable outputs. Extensive experiments on public benchmarks demonstrate that ELMK outperforms several state-of-the-art methods in terms of performance and generates more faithful and interpretable reasoning results.