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

Jiyong Liao

doi:10.1109/tkde.2026.3682046

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

2026-07-01

1

PRE

AI

DOI：10.1109/tkde.2026.3682046

Original

Original request for help

Save

Abstract

En 中文

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.

Keywords:

Feeds

Motion pictures

Broadcasting

Information filtering

Recommender systems

Spread spectrum communication

Digital communication

Electronic mail

Internet

Cloud computing

Retrieval-augmented generation

knowledge graph

large language model

answer coverage

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

Abstract

Journal

Organization

Cited Papers