- Rating
- 2
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper introduces ProST, a graph traversal framework for multi-hop RAG that replaces entity-level traversal states with proposition-level ones. The core idea is that preserving source context within each traversal unit prevents relevance from drifting into unrelated branches. The method is evaluated across four QA benchmarks and shown to outperform a range of existing baselines, backed by detailed ablation and mechanism analysis.
Critical strengths
- The method requires no extra training and no query-time LLM calls, which makes it lightweight and easy to drop into existing pipelines.
- The paper covers four benchmarks, a wide set of baselines, and extensive component checks including sensitivity analysis and a convergence proof.
Critical weaknesses
- Core contribution is incremental. Propositions as retrieval units, PPR graph traversal, and query-adaptive weighting are all established techniques.
- The entire traversal mechanism still runs on embedding similarity. It does not leverage deeper topological properties like paths, logical dependencies, or community structure.
- Operating at proposition granularity greatly multiplies node count. The paper does not test how the method scales to much larger corpora, where index size and traversal cost could become practical issues.
Questions for authors
- How does performance and latency hold up on much larger corpora where proposition node count grows substantially?
- Did you explore using topological graph properties (path structure, node centrality, etc.) to guide traversal, instead of only similarity scoring?
- How sensitive is end-to-end performance to proposition extraction quality? What share of extraction errors propagate through the traversal step?
8 comments
Initial Response (2/4)
Can graph topology improve traversal? (W2,Q2)
ProST uses shared entities to define the available transitions and the query and current proposition to distribute relevance among them. Entity degree indicates how many candidates a bridge connects, and the usefulness of those candidates depends on the query. In static PPR, generic, high-degree hubs can draw relevance away from the bridge entities that connect supporting facts [3].
We tested whether local graph structure helps identify which propositions benefit from source-conditioned scoring. Starting from the propositions eligible for this scoring in standard ProST, we applied it only to the top half ranked by one of four signals: bridge degree, entity count per proposition, semantic margin, or propagation mass. Standard ProST served as the reference and applied the scoring to all eligible propositions. Scores are FCR@5 (%).
| Signal | Selection Criterion | Coverage | MuSiQue | 2Wiki | HotpotQA |
|---|---|---|---|---|---|
| Reference | No additional gating | 100% | 55.40 | 88.40 | 95.00 |
| Local topology | Bridge degree | 50% | 54.50 | 87.40 | 95.00 |
| Local topology | Entity count per proposition | 50% | 54.30 | 87.50 | 95.00 |
| Semantic relevance | Semantic margin | 50% | 55.00 | 87.80 | 95.10 |
| Propagation state | Propagation mass | 50% | 55.30 | 88.30 | 94.90 |
At the same 50% coverage, semantic margin yielded higher FCR@5 point estimates than both local topology criteria, with the clearest differences on MuSiQue and 2Wiki. Standard ProST scored highest on those two datasets. In this experiment, selecting where to use source context based on local connectivity offered no advantage over selecting by semantic margin. Richer structural signals, such as path structure or global centrality, could complement ProST's transition rule. We leave their integration and evaluation to future work.
Reference
[3] Lau et al. Breaking the Static Graph: Context-Aware Traversal for Graph-Based RAG. Findings of ACL, 2026. ACL Anthology
Initial Response (3/4)
How do retrieval cost and quality change as the proposition graph grows? (W3,Q1)
ProST showed moderate retrieval latency growth as the proposition graph expanded, while achieving the highest observed passage recall and full-chain retrieval scores on a larger corpus. We evaluated retrieval cost across four corpus sizes and compared retrieval quality against PropRAG and HippoRAG 2 on the full MultiHop-RAG corpus [4].
- Retrieval cost as the graph grows. We measured per-query latency for ProST and PropRAG across four corpus sizes under identical retrieval settings.
- Retrieval quality on MultiHop-RAG. We compared passage recall, full-chain retrieval, and query-time LLM calls across the three systems.
1. Retrieval cost across four corpus sizes
We rebuilt the graphs at four corpus sizes using MultiHop-RAG, keeping the 609 source articles fixed while recomputing propositions, entities, and graph connections. We measured sequential retrieval latency on the same 100 queries with embedding caching disabled and identical hyperparameters across all sizes. All measurements used the same GPU encoder configuration.
| Passages | Propositions | Entities | PropRAG Latency (s/q) | ProST Latency (s/q) |
|---|---|---|---|---|
| 10,000 | 64,173 | 31,966 | 1.36 | 2.14 |
| 20,000 | 128,437 | 40,106 | 1.50 | 2.48 |
| 30,000 | 192,710 | 44,061 | 1.54 | 2.70 |
| 40,000 | 257,074 | 46,379 | 1.62 | 2.91 |
| Growth | ×4.01 | ×1.45 | ×1.19 | ×1.36 |
As the proposition count increased approximately fourfold, ProST's per-query latency increased by 1.36×, compared with 1.19× for PropRAG. Although ProST incurred higher absolute latency, its retrieval latency grew more slowly than the proposition count over the evaluated range.
2. Retrieval quality on the full MultiHop-RAG corpus
We evaluated ProST, PropRAG, and HippoRAG 2 on the same 1,208 answerable MultiHop-RAG test queries after article-level deduplication and exclusion of null queries. The full corpus contained 42,065 passages and 270,347 propositions. We report passage recall at ranks 2 and 5, full-chain retrieval at rank 5, and the number of LLM calls per query during retrieval. All retrieval scores are percentages.
| System | R@2 | R@5 | FCR@5 | LLM Calls/Query |
|---|---|---|---|---|
| HippoRAG 2 | 51.46 | 73.89 | 48.59 | 1 |
| PropRAG | 52.95 | 73.72 | 48.51 | 0 |
| ProST | 53.70 | 74.16 | 48.92 | 0 |
ProST achieved the highest observed R@2, R@5, and FCR@5 on the full MultiHop-RAG corpus without requiring query-time LLM calls. These results demonstrate that ProST remains competitive in retrieval quality at a substantially larger graph scale.
Reference
[4] Tang and Yang. MultiHop-RAG: Benchmarking Retrieval-Augmented Generation for Multi-Hop Queries. arXiv:2401.15391, 2024. arXiv
Initial Response (1/4)
We thank the reviewer for the constructive feedback. We clarify the contribution of source-conditioned transitions, the role of graph topology, and the scope of our additional evaluations of larger-corpus retrieval and extraction noise.
What does ProST contribute beyond existing retrieval and traversal techniques? (W1)
ProST enables context-dependent evidence selection: even when different propositions reach the same entity, it can prioritize different next evidence based on the current proposition. Unlike existing graph traversal methods [1, 2], ProST explicitly conditions transition weights on the current proposition using the residual between the query and source embeddings. We evaluate whether this capability improves evidence selection and full-chain retrieval through one-step relevance transfer and source embedding shuffling.
1. One-step relevance transfer toward the next gold passage
To assess whether source conditioning directs more relevance toward the next gold passage, we revisited the one-step analysis in Appendix B.3 (Table 10). Previously, entity-state baselines used their own best bridges, while proposition-state variants shared ProST-selected bridges. We now average over all eligible shared bridges within each hop and take the median across hops common to all five configurations.
Full ProST and its query-only variant both propagate relevance over proposition states. Conditioning on the current proposition increased median one-step relevance transfer toward the next gold passage on all three datasets. This supports the benefit of using source context to prioritize the next evidence, even among candidates connected through the same bridge entity.
2. Does the correct source context improve full-chain retrieval?
We shuffled source embeddings within each bridge using three random seeds and report the mean FCR@5 across those runs. The graph, source states, candidate sets, retrieval seeds, and transition rule were fixed. The shuffle changes only whether the proposition embedding used in the residual matches the current state.
FCR@5 with the true source exceeded the shuffled-source mean on all three datasets. The paired nominal 95% confidence intervals excluded zero on MuSiQue and 2Wiki and included zero on HotpotQA. Because shuffling leaves the residual formula unchanged, the results on MuSiQue and 2Wiki support the value of using an embedding that matches the current proposition to guide retrieval.
References
[1] Wang and Han. PropRAG: Guiding Retrieval with Beam Search over Proposition Paths. EMNLP, 2025. ACL Anthology
[2] Gutiérrez et al. From RAG to Memory: Non-Parametric Continual Learning for Large Language Models. ICML, 2025. PMLR