ProgRAG: Hallucination-Resistant Progressive Retrieval and Reasoning over Knowledge Graphs

• URL: http://arxiv.org/abs/2511.10240v1
• Date: Fri, 14 Nov 2025 01:41:03 GMT
• Title: ProgRAG: Hallucination-Resistant Progressive Retrieval and Reasoning over Knowledge Graphs
• Authors: Minbae Park, Hyemin Yang, Jeonghyun Kim, Kunsoo Park, Hyunjoon Kim,
• Abstract summary: Large Language Models (LLMs) demonstrate strong reasoning capabilities but struggle with hallucinations and limited transparency.<n>We propose ProgRAG, a multi-hop knowledge graph question answering (KGQA) framework that decomposes complex questions into sub-questions and extends partial reasoning paths.<n> Experiments on three well-known datasets demonstrate that ProgRAG outperforms existing baselines in multi-hop KGQA.
• Score: 2.9539912037183362
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Large Language Models (LLMs) demonstrate strong reasoning capabilities but struggle with hallucinations and limited transparency. Recently, KG-enhanced LLMs that integrate knowledge graphs (KGs) have been shown to improve reasoning performance, particularly for complex, knowledge-intensive tasks. However, these methods still face significant challenges, including inaccurate retrieval and reasoning failures, often exacerbated by long input contexts that obscure relevant information or by context constructions that struggle to capture the richer logical directions required by different question types. Furthermore, many of these approaches rely on LLMs to directly retrieve evidence from KGs, and to self-assess the sufficiency of this evidence, which often results in premature or incorrect reasoning. To address the retrieval and reasoning failures, we propose ProgRAG, a multi-hop knowledge graph question answering (KGQA) framework that decomposes complex questions into sub-questions, and progressively extends partial reasoning paths by answering each sub-question. At each step, external retrievers gather candidate evidence, which is then refined through uncertainty-aware pruning by the LLM. Finally, the context for LLM reasoning is optimized by organizing and rearranging the partial reasoning paths obtained from the sub-question answers. Experiments on three well-known datasets demonstrate that ProgRAG outperforms existing baselines in multi-hop KGQA, offering improved reliability and reasoning quality.

Related papers

• GRIL: Knowledge Graph Retrieval-Integrated Learning with Large Language Models [59.72897499248909]
  We propose a novel graph retriever trained end-to-end with Large Language Models (LLMs)<n>Within the extracted subgraph, structural knowledge and semantic features are encoded via soft tokens and the verbalized graph, respectively, which are infused into the LLM together.<n>Our approach consistently achieves state-of-the-art performance, validating the strength of joint graph-LLM optimization for complex reasoning tasks.
  arXiv  Detail & Related papers  (2025-09-20T02:38:00Z)
• KG-o1: Enhancing Multi-hop Question Answering in Large Language Models via Knowledge Graph Integration [29.320693000484273]
  KG-o1 is a four-stage approach that integrates knowledge graphs to enhance the multi-hop reasoning abilities of Large Language Models.<n>We conduct experiments on two simple and two complex datasets.<n>The results show that KG-o1 models exhibit superior performance across all tasks compared to existing LRMs.
  arXiv  Detail & Related papers  (2025-08-12T04:29:10Z)
• Prompting Large Language Models with Partial Knowledge for Answering Questions with Unseen Entities [43.88784275673178]
  Retrieval-Augmented Generation (RAG) shows impressive performance by supplementing and substituting parametric knowledge in Large Language Models (LLMs)<n>We show how triplets located in the gold reasoning path and their variants are used to construct partially relevant knowledge by removing the path that contains the answer.<n>Our awakening-based approach demonstrates greater efficacy in practical applications, outperforms traditional methods that rely on embedding-based similarity.
  arXiv  Detail & Related papers  (2025-08-02T09:54:46Z)
• Towards Agentic RAG with Deep Reasoning: A Survey of RAG-Reasoning Systems in LLMs [69.10441885629787]
  Retrieval-Augmented Generation (RAG) lifts the factuality of Large Language Models (LLMs) by injecting external knowledge.<n>It falls short on problems that demand multi-step inference; conversely, purely reasoning-oriented approaches often hallucinate or mis-ground facts.<n>This survey synthesizes both strands under a unified reasoning-retrieval perspective.
  arXiv  Detail & Related papers  (2025-07-13T03:29:41Z)
• Reliable Reasoning Path: Distilling Effective Guidance for LLM Reasoning with Knowledge Graphs [14.60537408321632]
  Large language models (LLMs) often struggle with knowledge-intensive tasks due to a lack of background knowledge.<n>We propose the RRP framework to mine the knowledge graph.<n>We also introduce a rethinking module that evaluates and refines reasoning paths according to their significance.
  arXiv  Detail & Related papers  (2025-06-12T09:10:32Z)
• KnowTrace: Bootstrapping Iterative Retrieval-Augmented Generation with Structured Knowledge Tracing [64.38243807002878]
  We present KnowTrace, an elegant RAG framework to mitigate the context overload in large language models.<n>KnowTrace autonomously traces out desired knowledge triplets to organize a specific knowledge graph relevant to the input question.<n>It consistently surpasses existing methods across three multi-hop question answering benchmarks.
  arXiv  Detail & Related papers  (2025-05-26T17:22:20Z)
• Self-Reflective Planning with Knowledge Graphs: Enhancing LLM Reasoning Reliability for Question Answering [9.601307470705732]
  We propose Self-Reflective Planning (SRP), a framework that synergizes large language models with knowledge graphs.<n>In the planning process, SRP first searches for references to guide planning and reflection.<n>After retrieving knowledge from KGs through a reasoning path, it implements iterative reflection by judging the retrieval result and editing the reasoning path until the answer is correctly retrieved.
  arXiv  Detail & Related papers  (2025-05-26T01:59:00Z)
• Reasoning with Graphs: Structuring Implicit Knowledge to Enhance LLMs Reasoning [73.2950349728376]
  Large language models (LLMs) have demonstrated remarkable success across a wide range of tasks.<n>However, they still encounter challenges in reasoning tasks that require understanding and inferring relationships between pieces of information.<n>This challenge is particularly pronounced in tasks involving multi-step processes, such as logical reasoning and multi-hop question answering.<n>We propose Reasoning with Graphs (RwG) by first constructing explicit graphs from the context.
  arXiv  Detail & Related papers  (2025-01-14T05:18:20Z)
• Graph-constrained Reasoning: Faithful Reasoning on Knowledge Graphs with Large Language Models [92.71304585906624]
  Large language models (LLMs) struggle with faithful reasoning due to knowledge gaps and hallucinations.<n>We introduce graph-constrained reasoning (GCR), a novel framework that bridges structured knowledge in KGs with unstructured reasoning in LLMs.<n>GCR achieves state-of-the-art performance and exhibits strong zero-shot generalizability to unseen KGs without additional training.
  arXiv  Detail & Related papers  (2024-10-16T22:55:17Z)
• Mindful-RAG: A Study of Points of Failure in Retrieval Augmented Generation [11.471919529192048]
  Large Language Models (LLMs) are proficient at generating coherent and contextually relevant text. Retrieval-augmented generation (RAG) systems mitigate this by incorporating external knowledge sources, such as structured knowledge graphs (KGs) Our study investigates this dilemma by analyzing error patterns in existing KG-based RAG methods and identifying eight critical failure points.
  arXiv  Detail & Related papers  (2024-07-16T23:50:07Z)
• FiDeLiS: Faithful Reasoning in Large Language Model for Knowledge Graph Question Answering [46.41364317172677]
  Large Language Models (LLMs) are often challenged by generating erroneous or hallucinated responses.<n>We propose a unified framework, FiDeLiS, designed to improve the factuality of LLM responses by anchoring answers to verifiable reasoning steps retrieved from Knowledge Graphs.<n>Our method, as a training-free framework, not only improve the performance but also enhance the factuality and interpretability across different benchmarks.
  arXiv  Detail & Related papers  (2024-05-22T17:56:53Z)
• Reasoning on Graphs: Faithful and Interpretable Large Language Model Reasoning [104.92384929827776]
  Large language models (LLMs) have demonstrated impressive reasoning abilities in complex tasks. They lack up-to-date knowledge and experience hallucinations during reasoning. Knowledge graphs (KGs) offer a reliable source of knowledge for reasoning.
  arXiv  Detail & Related papers  (2023-10-02T10:14:43Z)
• Think-on-Graph: Deep and Responsible Reasoning of Large Language Model on Knowledge Graph [29.447300472617826]
  Think-on-Graph (ToG) is a new approach for external knowledge graphs (KG) in large language models (LLMs) ToG iteratively executes beam search on KG, discovers the most promising reasoning paths, and returns the most likely reasoning results. ToG achieves overall SOTA in 6 out of 9 datasets where most previous SOTAs rely on additional training.
  arXiv  Detail & Related papers  (2023-07-15T03:31:38Z)
• Search-in-the-Chain: Interactively Enhancing Large Language Models with Search for Knowledge-intensive Tasks [121.74957524305283]
  This paper proposes a novel framework named textbfSearch-in-the-Chain (SearChain) for the interaction between Information Retrieval (IR) and Large Language Model (LLM) Experiments show that SearChain outperforms state-of-the-art baselines on complex knowledge-intensive tasks.
  arXiv  Detail & Related papers  (2023-04-28T10:15:25Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.