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

arXiv: https://arxiv.org/abs/2511.10240 · HTML: https://mlsanity.com/paper/2511.10240/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Placed in Knowledge- and tool-augmented reasoning, one of 17 directions in LLM reasoning.
- Builds on 27 of its 50 references that are in the map.
- First posted on arXiv 13 Nov 2025.

## Placed in

- LLM reasoning / [Knowledge- and tool-augmented reasoning](https://mlsanity.com/lr/knowledge-and-tool-augmented-reasoning/)

## Builds on (most cited first, 27 of 27)

- [Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks](https://mlsanity.com/paper/1908.10084/) (2019)
- [Representation Learning with Contrastive Predictive Coding](https://mlsanity.com/paper/1807.03748/) (2018)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [Lost in the Middle: How Language Models Use Long Contexts](https://mlsanity.com/paper/2307.03172/) (2023)
- [The Curious Case of Neural Text Degeneration](https://mlsanity.com/paper/1904.09751/) (2019)
- [Towards General Text Embeddings with Multi-stage Contrastive Learning](https://mlsanity.com/paper/2308.03281/) (2023)
- [The Web as a Knowledge-base for Answering Complex Questions](https://mlsanity.com/paper/1803.06643/) (2018)
- [StructGPT: A General Framework for Large Language Model to Reason over Structured Data](https://mlsanity.com/paper/2305.09645/) (2023)
- [Reasoning on Graphs: Faithful and Interpretable Large Language Model Reasoning](https://mlsanity.com/paper/2310.01061/) (2023)
- [Think-on-Graph: Deep and Responsible Reasoning of Large Language Model on Knowledge Graph](https://mlsanity.com/paper/2307.07697/) (2023)
- [GNN-RAG: Graph Neural Retrieval for Large Language Model Reasoning](https://mlsanity.com/paper/2405.20139/) (2024)
- [Knowledge-Augmented Language Model Prompting for Zero-Shot Knowledge Graph Question Answering](https://mlsanity.com/paper/2306.04136/) (2023)
- [UniKGQA: Unified Retrieval and Reasoning for Solving Multi-hop Question Answering Over Knowledge Graph](https://mlsanity.com/paper/2212.00959/) (2022)
- [DecAF: Joint Decoding of Answers and Logical Forms for Question Answering over Knowledge Bases](https://mlsanity.com/paper/2210.00063/) (2022)
- [Simple Is Effective: The Roles of Graphs and Large Language Models in Knowledge-Graph-Based Retrieval-Augmented Generation](https://mlsanity.com/paper/2410.20724/) (2024)
- [The Curse of Dense Low-Dimensional Information Retrieval for Large Index Sizes](https://mlsanity.com/paper/2012.14210/) (2020)
- [Graph-constrained Reasoning: Faithful Reasoning on Knowledge Graphs with Large Language Models](https://mlsanity.com/paper/2410.13080/) (2024)
- [ChatKBQA: A Generate-then-Retrieve Framework for Knowledge Base Question Answering with Fine-tuned Large Language Models](https://mlsanity.com/paper/2310.08975/) (2023)
- [GFM-RAG: Graph Foundation Model for Retrieval Augmented Generation](https://mlsanity.com/paper/2502.01113/) (2025)
- [Estimating LLM Uncertainty with Evidence](https://mlsanity.com/paper/2502.00290/) (2025)
- [Using Large Language Models for Zero-Shot Natural Language Generation from Knowledge Graphs](https://mlsanity.com/paper/2307.07312/) (2023)
- [ReasoningLM: Enabling Structural Subgraph Reasoning in Pre-trained Language Models for Question Answering over Knowledge Graph](https://mlsanity.com/paper/2401.00158/) (2023)
- [Reasoning of Large Language Models over Knowledge Graphs with Super-Relations](https://mlsanity.com/paper/2503.22166/) (2025)
- [CR-LT-KGQA: A Knowledge Graph Question Answering Dataset Requiring Commonsense Reasoning and Long-Tail Knowledge](https://mlsanity.com/paper/2403.01395/) (2024)
- [Towards Long Context Hallucination Detection](https://mlsanity.com/paper/2504.19457/) (2025)
- [To Retrieve or Not to Retrieve? Uncertainty Detection for Dynamic Retrieval Augmented Generation](https://mlsanity.com/paper/2501.09292/) (2025)
- [Beyond Chains: Bridging Large Language Models and Knowledge Bases in Complex Question Answering](https://mlsanity.com/paper/2505.14099/) (2025)

## Built on by (most cited first, 3 of 3)

- [Why Reasoning Fails to Plan: A Planning-Centric Analysis of Long-Horizon Decision Making in LLM Agents](https://mlsanity.com/paper/2601.22311/) (2026)
- [Courtroom-Style Multi-Agent Debate with Progressive RAG and Role-Switching for Controversial Claim Verification](https://mlsanity.com/paper/2603.28488/) (2026)
- [No=esis: Deterministic-First Retrieval with Two-Tier Context Hydration for Factuality-Critical Queries on Small Local Models](https://mlsanity.com/paper/2609.07663/) (2026)

## Abstract (arXiv)

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.