acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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.

Primary area:
applications to computer vision, audio, language, and other modalities
Keywords:
multi-hop retrieval, retrieval-augmented generation, graph-based retrieval, graph traversal, proposition-based retrieval, personalized PageRank

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_hYNYOpenReview ↗
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
  1. The method requires no extra training and no query-time LLM calls, which makes it lightweight and easy to drop into existing pipelines.
  2. The paper covers four benchmarks, a wide set of baselines, and extensive component checks including sensitivity analysis and a convergence proof.
Critical weaknesses
  1. Core contribution is incremental. Propositions as retrieval units, PPR graph traversal, and query-adaptive weighting are all established techniques.
  2. The entire traversal mechanism still runs on embedding similarity. It does not leverage deeper topological properties like paths, logical dependencies, or community structure.
  3. 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
  1. How does performance and latency hold up on much larger corpora where proposition node count grows substantially?
  2. Did you explore using topological graph properties (path structure, node centrality, etc.) to guide traversal, instead of only similarity scoring?
  3. How sensitive is end-to-end performance to proposition extraction quality? What share of extraction errors propagate through the traversal step?
8 comments
AuthorsOpenReview ↗

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.

  • One-step relevance transfer. We measured whether incorporating the current proposition sends more relevance toward the next gold passage.
  • Source embedding shuffle. We kept the residual calculation and shuffled the source embeddings within each bridge to test whether pairing each state with its actual source context matters for full-chain retrieval.

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.

SystemStateTransitionMuSiQue2WikiHotpotQA
HippoRAG 2EntityUniform8.334.626.7
PropRAGEntityUniform8.433.325.3
ProSTPropositionQuery + source18.655.145.9
w/o source-aware weightingPropositionQuery only14.236.532.2
w/o query-adaptive transitionPropositionUniform11.630.623.9

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.

ConditionMuSiQue2WikiHotpotQA
True source55.4088.4095.00
Shuffled source (mean of 3 runs)53.4386.1394.70
Query only52.6085.7093.70

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

AuthorsOpenReview ↗

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 (%).

SignalSelection CriterionCoverageMuSiQue2WikiHotpotQA
ReferenceNo additional gating100%55.4088.4095.00
Local topologyBridge degree50%54.5087.4095.00
Local topologyEntity count per proposition50%54.3087.5095.00
Semantic relevanceSemantic margin50%55.0087.8095.10
Propagation statePropagation mass50%55.3088.3094.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

AuthorsOpenReview ↗

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.

PassagesPropositionsEntitiesPropRAG Latency (s/q)ProST Latency (s/q)
10,00064,17331,9661.362.14
20,000128,43740,1061.502.48
30,000192,71044,0611.542.70
40,000257,07446,3791.622.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.

SystemR@2R@5FCR@5LLM Calls/Query
HippoRAG 251.4673.8948.591
PropRAG52.9573.7248.510
ProST53.7074.1648.920

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

Reviewer_2Le2OpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This work presents ProST to solve context loss in multi-hop graph retrieval, where relevance that reaches the same entity through different relational paths can no longer distinguish which source context should guide the next hop. ProST represents propositions as traversal states, uses shared entities and their OpenIE roles as bridges, weights candidate entities by query-role similarity, and weights candidate propositions by the residual between the query and the current proposition. These query-adaptive transitions are combined with proposition and passage nodes in Personalized PageRank. Experiments show that ProST obtains the best full-chain retrieval on MuSiQue, 2Wiki, and HotpotQA and strong downstream QA results, while ablations show contributions from both proposition states and adaptive transitions without query-time LLM calls.

Critical strengths
  • The representation-level change addresses a concrete failure mode. Entity-state traversal can merge different reasoning contexts at a shared entity; using atomic propositions as states preserves the source fact and allows the next transition to depend on both the query and the current proposition. This is a focused and well-motivated design for multi-hop evidence retrieval.

  • The empirical assessment is unusually broad for a retrieval-method paper. The paper evaluates four corpora, dense, structure-aware, and query-aware baselines, full-chain retrieval, downstream QA, alternative scoring functions, beam-width sensitivity, multiple reader LLMs, indexing cost, and an anonymous implementation. The consistency of the full-chain gains and the component analyses make the central claim credible.

Critical weaknesses
  • Graph-construction quality is not audited evenly. Traversal depends on LLM-extracted propositions and OpenIE-derived entity roles. Proposition quality is audited only on 300 Wikipedia items per benchmark using GPT-4o-mini, while ChemLit-QA has much lower role coverage and no corresponding proposition-quality audit. Extraction and role errors can silently remove the bridge that proposition-state traversal is designed to exploit.

  • Dataset-specific tuning and statistical uncertainty weaken some comparisons. Six retrieval/traversal hyperparameters are selected separately on each validation split, but the paper does not report a single global-configuration result or the loss incurred by cross-dataset transfer. The 1,000-question evaluations also lack confidence intervals or paired significance tests, so smaller gaps over PropRAG and other close baselines are hard to interpret.

Questions for authors
  • Since ChemLit-QA has much lower entity-role coverage, what mechanism explains ProST’s gains there when many candidate links receive zero entity-weighting score?

  • Could you provide an independent audit of proposition faithfulness, entity-role correctness, and bridge preservation, including ChemLit-QA and examples where incorrect roles change the traversal? How stable is retrieval to OpenIE noise?

5 comments
AuthorsOpenReview ↗

Initial Response (1/3)

We thank the reviewer for the constructive feedback. We clarify the role of graph connectivity under sparse entity-role annotations, examine graph-construction quality and sensitivity to extraction errors, and evaluate hyperparameter transfer and statistical uncertainty.

How does ProST work on ChemLit-QA when entity-role coverage is low? (W1,Q1)

Links without an OpenIE-derived role remain in the graph and receive positive transition weights after softmax normalization, even when their entity-weighting score is zero. Source-Aware Proposition Weighting then distributes relevance among the candidate propositions connected to each bridge. On ChemLit-QA [1], we measured the transition mass carried by links without roles and separately ablated each weighting component to assess its contribution to retrieval.

  • Relevance transfer through links without roles. We measured how much relevance these links receive after normalization to determine whether they remain usable as bridges.
  • Contribution of the two weighting components. We ablated each component across ChemLit-QA to determine which weighting contributes to retrieval under low role coverage.

1. Relevance transfer through links without roles

As described in Section 3.3.2 and Appendix A.2, links without an OpenIE-derived role remain in the graph and receive a score of se=0s_e = 0. Softmax in Eq. (2) gives these links positive transition weights, including in mixed rows with both labeled and unlabeled links. When all links lack role labels, the weights are uniform.

Measurement (%)ChemLit-QAMuSiQue2WikiHotpotQA
Links without an available role in the full graph76.629.028.027.1
Links without an available role in the region selected for adaptive transitions73.923.725.722.0
Mass assigned to links without a role under uniform weighting, mixed rows46.6133.3233.8432.67
Mass assigned to links without a role under Query-Aware Entity Weighting, mixed rows9.4912.9620.2613.04

In ChemLit-QA, links without roles received 9.49% of the transition mass in mixed rows. These links therefore remain available for transferring relevance to candidate propositions even when role coverage is low.

2. Contribution of the two weighting components

To assess how each weighting component contributes to retrieval under low role coverage, we ablated Query-Aware Entity Weighting and Source-Aware Proposition Weighting separately on ChemLit-QA. In the ablation of Source-Aware Proposition Weighting, all candidate propositions connected to a given bridge entity received equal weights.

Configuration on ChemLit-QA (1,025 questions)R@2R@5MRR@5
ProST91.7198.1587.77
w/o Query-Aware Entity Weighting91.8098.1588.08
w/o Source-Aware Proposition Weighting87.0296.2983.07

Removing Query-Aware Entity Weighting changed some rankings while leaving R@5 unchanged. Removing Source-Aware Proposition Weighting lowered all three retrieval metrics. Together with the transition-mass analysis, these results explain how ProST retrieves evidence under low role coverage. Shared entities keep candidate propositions reachable, and Source-Aware Proposition Weighting helps prioritize evidence among those candidates.

Reference

[1] Wellawatte et al. ChemLit-QA: A human evaluated dataset for chemistry RAG tasks. Machine Learning: Science and Technology, 6(2), 020601, 2025. https://doi.org/10.1088/2632-2153/adc2d6

AuthorsOpenReview ↗

Initial Response (2/3)

How accurate is the extraction, and how do errors affect traversal? (W1,Q2)

The additional audit found high proposition faithfulness on all four datasets, including ChemLit-QA, alongside errors in extracted roles. In separate case studies, correcting an extracted role changed transition probabilities, and restoring a missing bridge improved a gold passage's rank. We examined extraction quality and its effects in three steps.

  • Audit extraction quality. We used a different LLM judge to assess proposition faithfulness and entity-role correctness separately, including on ChemLit-QA.
  • Trace observed errors. We corrected a role reversal and restored a missing shared-entity link in separate cases to see how each change affected traversal and retrieval.
  • Test retrieval sensitivity. We perturbed role labels and deleted links separately to measure the effect of each type of corruption.

1. Extraction quality audit including ChemLit-QA

We extended the original audit to include ChemLit-QA and used Qwen2.5-32B as a second LLM judge. We sampled 200 propositions per dataset and assessed proposition faithfulness, entity presence in the source passage, and entity-role correctness separately. The judge returned 199 assessments on MuSiQue and 200 on each other dataset.

DatasetSupported Propositions (%)Entities Present in Source (%)Role Pairs JudgedIncorrect Roles (%)Roles Not Inferable (%)
ChemLit-QA99.099.526614.924.9
MuSiQue99.5100.084222.013.1
2Wiki99.5100.065719.110.9
HotpotQA100.0100.072720.96.8

The audit found high proposition faithfulness across all four datasets, including ChemLit-QA, and identified entity roles that were incorrect or could not be inferred from the source. These findings highlight two aspects of extraction quality that matter for ProST. Faithful propositions preserve the evidence available for retrieval, and entity roles help determine how relevance flows through shared-entity links. Incorrect roles can alter that distribution, while links with missing roles can still carry relevance. The audit assessed individual passages. The following cases show how correcting a role changes transition weights and how restoring a missing cross-passage bridge affects retrieval.

2. Observed role reversal and missing bridge

We examined two 2Wiki cases to trace how a role error and a missing shared-entity bridge affect traversal and retrieval.

CaseCorrectionBeforeAfter
q#69 · Bayernhof Music MuseumMansion role: housed in → housedTransition weight through the mansion: 34.64%34.01%
q#294 · Franz, Duke of HohenbergRestored a shared entity split during extraction0 shared entities; second gold passage ranked 4th1 shared entity; second gold passage ranked 2nd

In q#69, correcting a single role changed ProST's relevance distribution and final passage scores, while the top-5 remained stable. This shows that role labels can influence traversal without necessarily changing the retrieved evidence.

In q#294, restoring a missing shared-entity bridge improved the rank of a gold passage. FCR@5 stayed the same because both gold passages were already in the top-5. This illustrates how preserving shared-entity links helps ProST prioritize supporting evidence.

3. Retrieval sensitivity to role corruption and link deletion

We applied three perturbations at a 50% corruption rate. Role deletion and swapping changed role labels while preserving graph connectivity. Link deletion removed connections available to traversal. We report FCR@5 for MuSiQue, 2Wiki, and HotpotQA, and R@5 for ChemLit-QA. All scores are percentages.

ConditionMuSiQue2WikiHotpotQAChemLit-QA
No corruption55.4088.4095.0098.15
Role label deletion55.4086.9095.2098.15
Role label swapping55.7087.3095.0098.15
Link deletion48.7081.6092.2096.20

On 2Wiki, deleting or swapping role labels reduced FCR@5 even though graph connectivity was preserved. This shows that the role information used by Query-Aware Entity Weighting can contribute to retrieval. At the same corruption rate, deleting links caused larger drops on all four datasets. Together with the ChemLit-QA analysis, these results explain why ProST can continue to transfer relevance under low role coverage. Shared entities keep candidate propositions reachable, and role labels help determine how much relevance flows through each available bridge.

AuthorsOpenReview ↗

Initial Response (3/3)

How sensitive is ProST to dataset-specific tuning, and how reliable are its gains over PropRAG? (W2)

Only two of the six hyperparameters selected on each dataset's validation split differed in their final values, both on 2Wiki. Three of the four datasets already used the same hyperparameter configuration. Applying this shared configuration to 2Wiki reduced FCR@5, but ProST still outperformed PropRAG [2]. Furthermore, ProST achieved a statistically significant improvement in full-chain retrieval over PropRAG on 2Wiki among the 500 questions not used for hyperparameter selection. ProST also achieved a higher FCR@5 on MuSiQue, although the confidence interval included zero.

  • Shared configuration evaluation. We applied both configurations derived from the hyperparameter values reported in the original paper to all four datasets to quantify the effect of using a shared configuration instead of dataset-specific settings.
  • Paired comparison with PropRAG. We compared ProST and PropRAG on questions not used for hyperparameter selection, reporting confidence intervals and statistical significance for the FCR@5 differences.

1. Performance under shared hyperparameter configurations

The two hyperparameters with different selected values were the dense seed weight wdocw_{\mathrm{doc}} and the proposition sharpness parameter τP\tau_P. Setting A (wdoc=0.5w_{\mathrm{doc}} = 0.5, τP=6\tau_P = 6) was used for MuSiQue, HotpotQA, and ChemLit-QA, while Setting B (wdoc=0.2w_{\mathrm{doc}} = 0.2, τP=2\tau_P = 2) was used for 2Wiki.

We applied both settings to all four datasets. For the three multi-hop benchmarks, we evaluated on 500 questions not used for hyperparameter selection; for ChemLit-QA, we evaluated on 513 questions. We report FCR@5 (%) for MuSiQue, 2Wiki, and HotpotQA, and R@5 (%) for ChemLit-QA, which has one gold passage per question.

DatasetQuestionsOriginal SettingSetting ASetting B
MuSiQue50054.6054.6051.40
2Wiki50087.8084.8087.80
HotpotQA50093.8093.8092.80
ChemLit-QA51398.2598.2596.88

Retrieval performance decreased when the shared configuration differed from the dataset's original setting. Nevertheless, ProST still outperformed PropRAG on the same questions (84.80% vs. 82.80%).

2. Statistical reliability of gains over PropRAG

We conducted a paired comparison of ProST and PropRAG on 500 questions per dataset that were not used for hyperparameter selection. We report FCR@5 (%), paired 95% confidence intervals for the differences, and McNemar's test. Δ\Delta denotes the difference between ProST and PropRAG in percentage points.

DatasetPropRAGProSTΔ [95% CI]McNemar p
MuSiQue52.8054.60+1.80 [−1.00, +4.60].262
2Wiki82.8087.80+5.00 [+3.00, +7.20]4.65 × 10⁻⁶
HotpotQA94.6093.80−0.80 [−2.00, +0.40].344

ProST achieved a statistically significant improvement in full-chain retrieval over PropRAG on 2Wiki, even on questions not used for hyperparameter selection. On MuSiQue, ProST achieved a 1.80-percentage-point gain, although the confidence interval included zero.

Reference

[2] Wang and Han. PropRAG: Guiding Retrieval with Beam Search over Proposition Paths. EMNLP, 2025. https://aclanthology.org/2025.emnlp-main.317/

Reviewer_QeSAOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper addresses the issue of lost source context when using entities as graph traversal states in multi-hop retrieval, and proposes a propositional state graph traversal framework, ProST. This method uses atomic propositions with intact semantics as retrieval and traversal states, connecting different propositions through shared entities. It adjusts the transition direction based on the context of the query and the current proposition, prioritizing the search for complementary evidence and reducing redundant expansion and interference from irrelevant information. Its retrieval process requires no additional training or invocation of a large language model during queries. Experiments on multiple question-answering benchmarks demonstrate that ProST improves the complete retrieval of multi-hop evidence chains and enhances downstream question-answering performance.

Critical strengths

S1. The research motivation is specific, and the research question is valuable.

S2. The methodological design is compact, with good feasibility and low inference cost.

S3. The experiments have broad coverage and provide mechanistic analysis related to the research motivation.

Critical weaknesses

W1. The paper argues that entity-based traversal may lose source context during relevance propagation. However, it is unclear how much this affects downstream QA when an LLM with a large context window receives a broader set of retrieved graph nodes, their relations, and supporting evidence for joint reasoning. Could the authors clarify whether the benefits of the proposed approach persist under larger retrieval and context budgets?

W2. The distinction from closely related work is unclear. ToPG already defines query-aware PPR over propositions connected through shared entities or passages (Section 2.2, Eqs. (3)–(7)). Thus, using propositions as traversal states does not clearly distinguish this work. Its main differences appear to be role-based weighting, source-conditioned residual transitions, and retrieval without query-time LLM calls. A direct comparison under matched settings would help clarify the paper’s novelty.

Questions for authors

See the weaknesses.

4 comments
AuthorsOpenReview ↗

Initial Response (1/2)

We thank the reviewer for the constructive feedback. We clarify the scope of ProST's contribution under larger retrieval and LLM context budgets and its methodological distinction from ToPG, supported by additional experiments.

Do ProST's QA gains persist with more evidence and graph context? (W1)

ProST consistently achieved the highest LLM-Acc across all three datasets under a context budget approximately four times larger than the top-5 retrieval setting used in prior work [1, 2]. This advantage persisted with both more retrieved passages and additional graph context. The largest gains were observed on MuSiQue, suggesting that retrieval quality remains important even with more context.

To test whether ProST's gains could be recovered simply by providing the LLM with more evidence or explicit graph relations, we evaluated two complementary settings under a shared 6,000-token budget.

  • More supporting passages. We allowed HippoRAG 2 and PropRAG to provide more retrieved passages and evaluated whether this narrowed ProST's QA advantage.
  • Supporting passages and graph relations. We provided the LLM with passages and graph context from each system, omitting highlights, to test whether access to graph relations further narrowed the QA differences.

1. QA with more supporting passages

All three systems used the same 6,000-token input cap. HippoRAG 2 and PropRAG supplied retrieved passages. ProST included retrieved passages and three highlights, following the original evaluation, within the same cap.

DatasetSystemInput TokensPassagesEMF1LLM-Acc
MuSiQueHippoRAG 25,9123841.3053.8847.20
PropRAG5,89836.344.6057.5851.80
ProST5,89835.847.3059.4853.40
2WikiHippoRAG 25,83831.370.3078.4175.80
PropRAG5,78925.571.1078.9976.00
ProST5,79725.471.5079.7576.80
HotpotQAHippoRAG 25,90136.562.2075.3870.90
PropRAG5,88734.662.2075.8371.90
ProST5,87833.962.4075.9072.00

Both baselines supplied substantially more passages than in the original top-5 evaluation. The LLM-Acc gap between PropRAG and ProST narrowed, but ProST still recorded the highest QA scores on all three datasets. The gains were largest on MuSiQue, where questions often require longer evidence chains. This pattern is consistent with ProST's design: the current proposition can help guide the search for the next piece of evidence when an answer depends on connecting several facts across passages.

2. QA with supporting passages and graph relations

We evaluated all three systems on the same 1,000 questions per dataset, using the same LLM and a 6,000-token input cap. Each system supplied its retrieved passages and graph context, with highlights omitted. HippoRAG 2 supplied entity triples with references to their source passages. PropRAG and ProST used the same proposition-based format, including proposition text, entity-role labels, and shared-entity links. Total input and graph token counts were comparable across the three systems.

DatasetSystemInput TokensPassagesGraph TokensEMF1LLM-Acc
MuSiQueHippoRAG 25,91427.91,38645.6058.0252.60
PropRAG5,90026.91,40547.9060.8155.30
ProST5,90426.91,40449.1062.1557.30
2WikiHippoRAG 25,83723.11,41570.1078.0274.90
PropRAG5,80619.61,38869.8078.5675.50
ProST5,80119.81,39170.0078.8576.40
HotpotQAHippoRAG 25,89926.81,43562.6075.8671.50
PropRAG5,88926.01,41263.4077.7272.30
ProST5,89225.71,41364.0077.5673.40

Graph relations can help the LLM connect the evidence it receives. With this additional context, ProST still achieved the highest LLM-Acc on all three datasets, with the largest gap on MuSiQue. The remaining gap suggests that even with more passages and graph relations in the LLM's input, how retrieval follows links between pieces of evidence can still matter for harder multi-hop questions.

References

[1] Gutiérrez et al. From RAG to Memory: Non-Parametric Continual Learning for Large Language Models. ICML, 2025. PMLR.

[2] Wang and Han. PropRAG: Guiding Retrieval with Beam Search over Proposition Paths. EMNLP, 2025. ACL Anthology.

AuthorsOpenReview ↗

Initial Response (2/2)

What distinguishes ProST from ToPG? (W2)

ToPG, proposed in a preprint [3], performs query-aware PPR over propositions connected through entities or passages. ProST's key distinction is a source-conditioned transition rule that scores candidate propositions using the residual between the query and the current proposition. This lets the same shared entity lead to different relevance distributions depending on the source proposition. We examine this distinction in three comparisons.

  • Matched comparison of transition rules. We substitute ToPG's transition rule into the ProST retrieval pipeline to assess how the choice of rule affects downstream QA under shared settings.
  • One-step transition analysis. We compare source-conditioned and query-only scoring within ProST to test whether the current proposition directs more relevance toward the next gold passage.
  • End-to-end comparison. We run each system with its own knowledge base and retrieval procedure to compare final QA performance and LLM calls before answer generation.

1. Matched comparison of transition rules

We implemented ToPG's transition rule in the ProST retrieval pipeline and held the knowledge base, seeds, and passage scoring fixed. Both variants used entity-only bridges and a PPR damping factor of 0.5. For QA, we supplied the top-5 passages from each run to the same LLM.

DatasetTransition RuleEMF1LLM-Acc
MuSiQueToPG40.6051.3846.00
ProST41.9053.3247.30
2WikiToPG65.3072.9669.70
ProST66.1073.6770.30
HotpotQAToPG62.2074.7071.00
ProST62.5075.6371.10

Under the matched settings, ProST's transition rule scored higher on EM, F1, and LLM-Acc across all three datasets. The gains were largest on MuSiQue, suggesting that the choice of transition rule matters more when questions require longer evidence chains. To examine the role of source conditioning within ProST, we next compared how much relevance the source-conditioned and query-only variants transferred to the next gold passage in a single step.

2. 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, each entity-state baseline used its own best bridge, while all three proposition-state variants were evaluated at the bridge selected by ProST. We now average over all eligible shared bridges within each hop and take the median across hops common to all five configurations.

SystemStateTransitionMuSiQue2WikiHotpotQAAvg.
HippoRAG 2EntityUniform8.334.626.723.2
PropRAGEntityUniform8.433.325.322.3
ProSTPropositionQuery + source18.655.145.939.9
w/o source-aware weightingPropositionQuery only14.236.532.227.6
w/o query-adaptive transitionPropositionUniform11.630.623.922.0

Among the proposition-state variants, conditioning on the source proposition increased the median relevance transferred toward the next gold passage on all three datasets. This shows how the context retained in the current proposition guides the next transition through a shared entity.

3. End-to-end QA and LLM calls before answer generation

We evaluated each system using its original implementation, without modifying the source code, knowledge base, or retrieval procedure. All systems were evaluated on the same questions using the same LLM. The call counts below exclude the final answer generation call.

DatasetSystemEMF1LLM-AccLLM calls/query
MuSiQueProST43.4055.5050.000
ToPG Naive19.2029.3825.400
ToPG Local(1)15.4021.7120.601.98
ToPG Local(3)27.4036.2034.605.14
HotpotQAProST64.2077.1273.800
ToPG Naive47.4058.5856.800
ToPG Local(1)46.6058.5454.801.99
ToPG Local(3)52.8067.1263.202.87

In the end-to-end evaluation, ProST outperformed all evaluated ToPG variants on EM, F1, and LLM-Acc across both datasets. It achieved these gains with the same number of pre-answer LLM calls as ToPG Naive and fewer than either ToPG Local variant. The comparison shows that ProST's overall design delivers stronger QA while keeping retrieval free of LLM calls.

Reference

[3] Delmas, Xu, and Freitas. A Navigational Approach for Comprehensive RAG via Traversal over Proposition Graphs. Preprint, 2026. arXiv:2601.04859.

AuthorsOpenReview ↗

We have incorporated your feedback into the manuscript

Thank you for your careful review and for raising these concerns. We have updated the manuscript to incorporate the additional experimental results and clarifications described in our responses. We hope these revisions and our responses help address your concerns. If any points would benefit from further clarification, we would be happy to discuss them.

AuthorsOpenReview ↗

Reminder Regarding Our Responses and Revised Manuscript

As the discussion period draws to a close, we would appreciate your review of our responses and revised manuscript. We have provided additional experiments and clarifications that we believe address all your concerns regarding ProST's QA gains under larger context budgets and its methodological distinction from ToPG. We would be happy to discuss any remaining questions.

Comments on the paper

1 comment

Review and Rebuttal Summary for the AC

We thank the reviewers for their careful evaluation. The reviews highlighted the following strengths of ProST:

  • ProST addresses a concrete failure mode of existing retrieval methods with a focused, well-motivated design. (2Le2)
  • The motivation is specific, and the research question is valuable. (QeSA)
  • All three reviewers highlighted the breadth of the experimental validation. 2Le2 described the experimental scope as unusually broad, and hYNY also highlighted the convergence proof. (All three reviewers)

We believe the additional experiments and revised manuscript address the main concerns. We received no follow-up from QeSA or 2Le2, and hYNY indicated that some concerns had been resolved. We summarize them as follows:

1. Performance and efficiency at larger scales (QeSA, hYNY)

a. Longer LLM context (QeSA). The original evaluation retained the baselines’ existing settings. When we quadrupled the input budget for all methods and included graph relations, ProST achieved the highest LLM-Acc point estimate on all three datasets.

b. Larger corpora (hYNY). The original evaluation used widely adopted multi-hop retrieval benchmarks. In additional MultiHop-RAG experiments, retrieval latency grew more slowly than corpus size, and ProST achieved the highest retrieval point estimates among the methods evaluated on the full corpus.

2. Distinction from ToPG (QeSA)

a. Transition rule. ToPG, described in a preprint, scores candidates based on the query. ProST also conditions the transition on the current proposition to determine which evidence to prioritize next.

b. Controlled and end-to-end comparisons. Holding the retrieval pipeline fixed and changing only the transition rule yielded higher QA point estimates for ProST. In separate end-to-end comparisons, ProST outperformed all evaluated ToPG variants on MuSiQue and HotpotQA without generative LLM calls during retrieval.

3. Assessment of novelty (hYNY)

While the other two reviewers both highlighted the specificity and value of our research question and the focused, well-motivated design of our method, Reviewer hYNY characterized the method as incremental.

a. Reviewer’s novelty assessment. The rationale hYNY gave for the novelty concern was that ProST uses established concepts, such as propositions and PPR. However, these concepts are common in IR and RAG, and the use of established concepts does not, by itself, establish that the resulting method is incremental.

After reviewing the revision, the reviewer maintained that assessment without explaining whether prior work had identified the same problem, which existing methods address it, or why ProST’s contributions are incremental.

b. What distinguishes ProST. ProST preserves the context of the current proposition when traversing a shared entity, so different propositions reaching the same entity can prioritize different evidence at the next hop. To our knowledge, ProST is the first to identify source-context loss at shared entities as a failure mode in multi-hop retrieval and address it through proposition-state traversal. Complementary controlled experiments across multiple benchmarks show that conditioning on the current proposition directs more relevance to the next gold passage and that shuffling the source context reduces full-chain retrieval performance on two benchmarks.

We would be grateful if the AC considered the revised manuscript and the additional evidence alongside the initial reviews. Thank you for your consideration.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.