Propositions as States: Context-Preserving Graph Traversal for Multi-Hop Retrieval

Retrieval-Augmented Generation (RAG) complements the parametric knowledge of Large Language Models (LLMs) with external knowledge, but multi-hop queries require retrieving interconnected evidence beyond direct semantic similarity. Graph-based methods support this process by connecting information through entities and relations, with recent approaches making graph traversal query-adaptive. However, these advances adapt how the graph is traversed while continuing to use entities as traversal states. When traversal paths from different relational contexts converge on the same entity, the context through which the entity became relevant is not retained as part of the traversal state. To address this limitation, we propose ProST (Propositions as States), a proposition-state graph traversal framework that maintains relevance over propositions while using entities as structural connections between them. By preserving source context within each proposition, ProST conditions subsequent transitions on both the query and the current proposition. Our approach thus jointly considers knowledge representation and graph traversal, allowing preserved context to directly guide query-adaptive traversal. Experiments across multiple QA benchmarks demonstrate consistent improvements in evidence retrieval and downstream question answering over strong retrieval baselines. Further analyses show that both proposition states and query-adaptive transitions contribute to retrieving complete multi-hop evidence chains.