# PropRAG: Guiding Retrieval with Beam Search over Proposition Paths

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

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- Placed in Knowledge-graph and structured-knowledge RAG, one of 15 directions in Retrieval-augmented generation.
- Builds on 29 of its 37 references that are in the map.
- First posted on arXiv 25 Apr 2025.

## Placed in

- Retrieval-augmented generation / [Knowledge-graph and structured-knowledge RAG](https://mlsanity.com/rag/knowledge-graph-and-structured-knowledge-rag/)

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

- [Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks](https://mlsanity.com/paper/2005.11401/) (2020)
- [Dense Passage Retrieval for Open-Domain Question Answering](https://mlsanity.com/paper/2004.04906/) (2020)
- [HotpotQA: A Dataset for Diverse, Explainable Multi-hop Question Answering](https://mlsanity.com/paper/1809.09600/) (2018)
- [From Local to Global: A Graph RAG Approach to Query-Focused Summarization](https://mlsanity.com/paper/2404.16130/) (2024)
- [Constructing A Multi-hop QA Dataset for Comprehensive Evaluation of Reasoning Steps](https://mlsanity.com/paper/2011.01060/) (2020)
- [Unsupervised Dense Information Retrieval with Contrastive Learning](https://mlsanity.com/paper/2112.09118/) (2021)
- [When Not to Trust Language Models: Investigating Effectiveness of Parametric and Non-Parametric Memories](https://mlsanity.com/paper/2212.10511/) (2022)
- [Interleaving Retrieval with Chain-of-Thought Reasoning for Knowledge-Intensive Multi-Step Questions](https://mlsanity.com/paper/2212.10509/) (2022)
- [MuSiQue: Multihop Questions via Single-hop Question Composition](https://mlsanity.com/paper/2108.00573/) (2021)
- [Towards General Text Embeddings with Multi-stage Contrastive Learning](https://mlsanity.com/paper/2308.03281/) (2023)
- [RAPTOR: Recursive Abstractive Processing for Tree-Organized Retrieval](https://mlsanity.com/paper/2401.18059/) (2024)
- [NV-Embed: Improved Techniques for Training LLMs as Generalist Embedding Models](https://mlsanity.com/paper/2405.17428/) (2024)
- [Large Dual Encoders Are Generalizable Retrievers](https://mlsanity.com/paper/2112.07899/) (2021)
- [A Neural Attention Model for Abstractive Sentence Summarization](https://mlsanity.com/paper/1509.00685/) (2015)
- [Editing Large Language Models: Problems, Methods, and Opportunities](https://mlsanity.com/paper/2305.13172/) (2023)
- [LightRAG: Simple and Fast Retrieval-Augmented Generation](https://mlsanity.com/paper/2410.05779/) (2024)
- [HippoRAG: Neurobiologically Inspired Long-Term Memory for Large Language Models](https://mlsanity.com/paper/2405.14831/) (2024)
- [Evaluating the Ripple Effects of Knowledge Editing in Language Models](https://mlsanity.com/paper/2307.12976/) (2023)
- [Generative Representational Instruction Tuning](https://mlsanity.com/paper/2402.09906/) (2024)
- [Beam Search Strategies for Neural Machine Translation](https://mlsanity.com/paper/1702.01806/) (2017)
- [From RAG to Memory: Non-Parametric Continual Learning for Large Language Models](https://mlsanity.com/paper/2502.14802/) (2025)
- [Answering Complex Open-Domain Questions with Multi-Hop Dense Retrieval](https://mlsanity.com/paper/2009.12756/) (2020)
- [Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering](https://mlsanity.com/paper/1911.10470/) (2019)
- [Bridging Textual and Tabular Data for Cross-Domain Text-to-SQL Semantic Parsing](https://mlsanity.com/paper/2012.12627/) (2020)
- [Model Editing Harms General Abilities of Large Language Models: Regularization to the Rescue](https://mlsanity.com/paper/2401.04700/) (2024)
- [Dense X Retrieval: What Retrieval Granularity Should We Use?](https://mlsanity.com/paper/2312.06648/) (2023)
- [Multi-hop Reading Comprehension across Multiple Documents by Reasoning over Heterogeneous Graphs](https://mlsanity.com/paper/1905.07374/) (2019)
- [Retrieve, Summarize, Plan: Advancing Multi-hop Question Answering with an Iterative Approach](https://mlsanity.com/paper/2407.13101/) (2024)
- [REAR: A Relevance-Aware Retrieval-Augmented Framework for Open-Domain Question Answering](https://mlsanity.com/paper/2402.17497/) (2024)

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

- [A Survey of Context Engineering for Large Language Models](https://mlsanity.com/paper/2507.13334/) (2025)
- [Graph-R1: Towards Agentic GraphRAG Framework via End-to-end Reinforcement Learning](https://mlsanity.com/paper/2507.21892/) (2025)
- [PlugMem: A Task-Agnostic Plugin Memory Module for LLM Agents](https://mlsanity.com/paper/2603.03296/) (2026)
- [GraphRAG-R1: Graph Retrieval-Augmented Generation with Process-Constrained Reinforcement Learning](https://mlsanity.com/paper/2507.23581/) (2025)
- [HGMEM: Hypergraph-based Working Memory to Improve Multi-step RAG for Long-Context Complex Relational Modeling](https://mlsanity.com/paper/2512.23959/) (2025)
- [GraphSearch: An Agentic Deep Searching Workflow for Graph Retrieval-Augmented Generation](https://mlsanity.com/paper/2509.22009/) (2025)
- [Controlling Authority Retrieval: A Missing Retrieval Objective for Authority-Governed Knowledge](https://mlsanity.com/paper/2604.14488/) (2026)
- [Harness the Memory: A Holistic Evaluation of Memory Substrates in Memory Agents](https://mlsanity.com/paper/2608.15008/) (2026)
- [History-Conditioned Joint-Prefix Alignment for Generative Recommendation](https://mlsanity.com/paper/2608.29179/) (2026)
- [A Navigational Approach for Comprehensive RAG via Traversal over Proposition Graphs](https://mlsanity.com/paper/2601.04859/) (2026)
- [RAG without Forgetting: Continual Query-Infused Key Memory](https://mlsanity.com/paper/2602.05152/) (2026)
- [RPDR: A Round-trip Prediction-Based Data Augmentation Framework for Long-Tail Question Answering](https://mlsanity.com/paper/2602.17366/) (2026)
- [SproutRAG: Attention-Guided Tree Search with Progressive Embeddings for Long-Document RAG](https://mlsanity.com/paper/2606.18381/) (2026)
- [EviReform: Evidence-Guided Query Reformulation for Multi-Hop Graph Retrieval](https://mlsanity.com/paper/2608.13006/) (2026)
- [LineageRAG: Harnessing GraphRAG by Constructing Evidence Lineages with Source Grounding](https://mlsanity.com/paper/2608.16004/) (2026)
- [The Commercial Tax: Rent-vs-Own Blind Spots in Multi-Hop Retrieval Benchmarks](https://mlsanity.com/paper/2608.16096/) (2026)
- [Enhancing LLMs in Predictive Political QA with Semi-Structured Data](https://mlsanity.com/paper/2608.21218/) (2026)
- [LivingRAG: Augmenting Graph RAG with Experience](https://mlsanity.com/paper/2608.25960/) (2026)
- [Hi-Q: Hierarchical Evidence-guided Query Refinement for Multi-Hop Question Answering](https://mlsanity.com/paper/2608.30468/) (2026)
- [HyperProve: Answer-Guided Hypergraph Expansion for Multi-Hop Question Answering](https://mlsanity.com/paper/2609.13768/) (2026)
- [Per-Query Gating of LLM Rerankers for Multi-Hop Retrieval](https://mlsanity.com/paper/2609.22880/) (2026)
- [EvLink: Source-Grounded Evidence Linking for Graph RAG](https://mlsanity.com/paper/2609.29695/) (2026)
- [Locate, Judge, Read: Role-Specialized Tool Agents over a Knowledge-Point Index for Open-Domain Multimodal Document QA](https://mlsanity.com/paper/2610.13128/) (2026)

## Abstract (arXiv)

Retrieval Augmented Generation (RAG) has become the standard approach for equipping Large Language Models (LLMs) with up-to-date 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 multi-step reasoning chains. By coupling a higher-fidelity knowledge representation with explicit path discovery, PropRAG achieves state-of-the-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.