PropRAG: Guiding retrieval with beam search over proposition paths

Wang, William

Permalink

https://hdl.handle.net/2142/129221 Copy

Description

Title

PropRAG: Guiding retrieval with beam search over proposition paths

Author(s)

Wang, William

Issue Date

2025-04-22

Director of Research (if dissertation) or Advisor (if thesis)

Han, Jiawei

Department of Study

Siebel School Comp & Data Sci

Discipline

Computer Science

Degree Granting Institution

University of Illinois Urbana-Champaign

Degree Name

M.S.

Degree Level

Thesis

Keyword(s)

• Retrieval Augmented Generation
• RAG
• Multi-Hop RAG
• Question Answering
• Proposition
• Beam Search
• Non-Parametric Continual Learning

Abstract

Retrieval Augmented Generation (RAG) has become the standard non-parametric approach for equipping Large Language Models (LLMs) with up-to-date knowledge and mitigating catastrophic forgetting common in continual learning. However, standard RAG, relying on independent passage retrieval, fails to capture the interconnected nature of human memory crucial for complex reasoning (associativity) and contextual understanding (sense-making). While structured RAG methods like HippoRAG 2 [1] utilize knowledge graphs (KGs) built from triples to improve associativity, the inherent context loss in triples limits their fidelity. We introduce PropRAG, a framework advancing RAG towards more human-like memory capabilities. PropRAG leverages contextually rich propositions as knowledge units and introduces a novel beam search algorithm over proposition paths, inspired by sequence generation, to explicitly discover and score multi-step reasoning chains. This path-centric approach significantly enhances multi-hop reasoning. PropRAG achieves state-of-the-art zero-shot Recall@5 results on challenging benchmarks like PopQA (55.3%), 2Wiki (93.7%), HotpotQA (97.0%), and MuSiQue (77.3%), alongside top F1 scores, including 52.4% on MuSiQue using Llama-3.3-Instruct. By improving the retrieval of interconnected evidence through richer representation and explicit path finding, PropRAG advances non-parametric continual learning for LLMs.

Graduation Semester

2025-05

Type of Resource

Thesis

Handle URL

https://hdl.handle.net/2142/129221

Copyright and License Information

Copyright 2025 William Wang

Owning Collections