PropRAG: Guiding Retrieval with Beam Search over Proposition Paths
Jingjin Wang, Jiawei Han · 2025
Retrieval Augmented Generation (RAG) has become the standard approach for equipping Large Language Models (LLMs) with up-todate knowledge.However, standard RAG, relying on independent passage retrieval, often fails to capture the interconnected nature of information required for complex, multi-hop reasoning.While structured RAG methods attempt to address this using knowledge graphs built from triples, we argue that the inherent context loss of triples (context collapse) limits the fidelity of the knowledge representation.We introduce PropRAG, a novel RAG framework that shifts from triples to context-rich propositions and introduces an efficient, LLM-free online beam search over proposition paths to discover multistep reasoning chains.By coupling a higherfidelity knowledge representation with explicit path discovery, PropRAG achieves state-ofthe-art zero-shot Recall@5 and F1 scores on 2Wiki, HotpotQA, and MuSiQue, advancing non-parametric knowledge integration by improving evidence retrieval through richer representation and efficient reasoning path discovery.Passage: The archival records indicate President Lincoln signed the preliminary Emancipation Proclamation in September 1862, but it only took legal effect on January 1, 1863, provided the Confederate states did not rejoin the Union by that date. Knowledge Graph (Triple Representation) Proposition GraphNodes within the same proposition hyper-edge are fully connected.Lincoln