acceptodds
Under review as a conference paper at ICLR 2027

Act-on-Graph: Recoverability-Aware Multi-Hop Retrieval for Reliable Knowledge Graph-Grounded LLM Reasoning

Abstract

Large language models (LLMs) exhibit strong reasoning capabilities, but they remain prone to hallucinations due to outdated parametric knowledge. Knowledge graphs (KGs) provide structured and interpretable evidence for factual grounding, making reliable retrieval essential for KG-enhanced LLM reasoning. However, existing methods typically focus on local expansion or complete-path ranking, with limited attention to whether intermediate retrieval states can still lead to a correct answer. Consequently, early retrieval mistakes may cause cascading errors, while excessive graph expansion introduces irrelevant candidate paths. We propose Act-on-Graph (AoG), a recoverability-aware multi-hop retrieval framework that formulates retrieval as a sequential decision process. Rather than evaluating only immediate actions or completed paths, AoG explicitly models the recoverability of intermediate retrieval states. Specifically, AoG converts answer-reaching paths into step-wise state–action and prefix-state supervision, jointly learning a local action policy for selecting relation–entity actions and a prefix-state value function for estimating state recoverability. During inference, an uncertainty-aware beam search retains plausible alternatives under ambiguous decisions while pruning redundant and low-recoverability branches. Experiments on WebQSP and CWQ show that AoG improves Hits@1 by 1.3% and 1.2% over the strongest baseline, respectively.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Large Language Models, Retrieval-Augmented Generation, Knowledge Graphs, Multi-Hop Graph Retrieval, Knowledge-Intensive Question Answering

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_4xgROpenReview ↗
Rating
3(+1)
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes AoG, a recoverability-aware multi-hop retrieval framework that formulates retrieval as a sequential decision process. AoG explicitly models the recoverability of intermediate retrieval states. To be specific, AoG converts answer-reaching paths into step-wise state-action and prefix-state supervision when training, and during inference, AoG adopts an uncertainty-aware beam search for reliable retrieval while reducing redundant exploration. Extensive experiments show the effectiveness of the proposed methods.

Critical strengths
  1. This paper identifies two retrieval failure types across baselines, cascading error propagation and path explosion, which may limit the LLM reasoning.
  2. Experiments on several datasets demonstrate the effectiveness of the proposed method, and ablation study shows the effectiveness of each component.
  3. This paper is well-written and easy to follow.
Critical weaknesses
  1. This paper may lack some representative baselines, such as GCR [1] that also finetuned a Llama-3-8B model, and PoG [2].
  2. This paper defines the recoverability as whether a gold answer is structurally reachable within the remaining hop budget. However, structural reachability does not guarantee that the path provides useful reasoning path. It would be beneficial to include a further analysis to validate these paths.
  3. For uncertainty-aware beam search, same-entities merging may discard meaningful reasoning prefixes. It would be beneficial to clarify this.

[1] Luo, Linhao, et al. "Graph-constrained reasoning: Faithful reasoning on knowledge graphs with large language models." ICML 2025. [2] Chen, Liyi, et al. "Plan-on-graph: Self-correcting adaptive planning of large language model on knowledge graphs." Advances in Neural Information Processing Systems 37 (2024): 37665-37691.

Questions for authors

Please refer to Weaknesses section.

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

This paper proposes Act-on-Graph, a multi-hop KG retrieval framework that combines a local action policy with a value function predicting whether a state can still reach a gold answer within the remaining hop budget. Training supervision is constructed from answer-reaching paths and perturbed prefixes. During inference, the framework combines policy and value scores with uncertainty-aware expansion and same-entity merging to retrieve evidence paths for a final reasoning model. Experiments report improvements on WebQSP and CWQ, with additional evaluations on GrailQA and MetaQA.

Critical strengths
  • The distinction between local action relevance and remaining-budget answer reachability provides a clear motivation for the method. The value-function ablation supports the usefulness of incorporating a reachability signal into multi-hop retrieval.

  • The evaluation covers downstream QA, retrieval quality, component ablations, and computational efficiency.

Critical weaknesses
  • The definition and interpretation of recoverability need further clarification. Figure 2 labels Google as unrecoverable despite an incoming edge from Walmart. Although this is consistent with the outgoing-only action space in Eq. 1, are inverse relations added to the KG, and do label construction and inference follow the same traversal rules? Moreover, a semantically incorrect path may still receive a positive label. How often do the policy and value signals disagree, and how does the combined score handle such cases?

  • The experimental comparisons do not fully isolate the framework’s contribution. Although Table 4 controls the final reasoning backbone, it remains unclear whether retrieval budgets and method configurations are comparable. Given the small Hits@1 improvements over the strongest baselines, could the authors clarify these settings and report variability or confidence intervals? Why is ToG included in Table 1 but omitted from this controlled comparison?

  • The computational cost accounting is insufficiently clear. Table 8 reports only one LLM call for AoG, although its fine-tuned Llama3.1-8B retriever also scores candidate actions and states. Does this count refer only to final answer generation? Does retrieval time include all model-scoring costs, and are hardware and batching settings comparable across methods?

  • The uncertainty-aware expansion rule is not sufficiently specified. How is k in the top-k action expansion in Figure 2 defined and selected? Is it the same as the final evidence-path count k=25?

Questions for authors

Please refer to Weaknesses.

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

This paper proposes Act-on-Graph (AoG), a multi-hop retrieval framework for KGQA. The method models path retrieval as a sequential decision process and decouples local action relevance from prefix-state recoverability. It jointly learns an action policy and a prefix-state recoverability value function, and integrates both during uncertainty-aware beam search for path expansion. Experiments on WebQSP and CWQ show improvements over existing baselines.

Critical strengths

S1. The method is clearly motivated. Evaluating whether an intermediate retrieval state can still reach an answer within the remaining hop budget is an intuitive way to guide multi-hop search. Combining this signal with stepwise relation selection provides a potentially useful mechanism for improving path retrieval in KGQA.

Critical weaknesses

W1. Limited evidence for the claimed reliability of multi-hop evidence path retrieval.

The reported Path Recall@k only "measures whether the top-k retrieved paths include at least one complete path connecting a topic entity to the corresponding gold answer entity" (Line 301), but does not measure whether the retrieved paths cover the constraints needed to justify that answer. Table 5 in the case study illustrates this issue: the displayed paths reach Kathleen Cavendish but provide no evidence for the key constraint "buried in St Peter’s Church Edensor".

Appendix C.6 claims that "the benefit of recoverability-aware retrieval becomes more evident for deeper multi-hop reasoning", but Table 14 does not clearly support this claim, as the margin over the strongest baseline decreases with increasing hop count.

Questions for authors

Q1. For WebQSP, Table 8 reports a generation time of 0.6 seconds for AoG, whereas Figure 5 shows approximately 6 seconds at the default beam size of 8. it is unclear whether these results are measured under different experimental settings.

Q2. Path absence is defined as the case "where the correct path does not exist in the knowledge graph". Given the same questions, KG, and hop budget, it is unclear why its proportion varies across methods in Figure 4.

2 comments

Dear Reviewer,

I hope this message finds you well. As the discussion period is nearing its end, I wanted to ensure we have addressed all your concerns satisfactorily. If there are any additional points or feedback you'd like us to consider, please let us know. Your insights are invaluable to us, and we’re eager to address any remaining issues to improve our work.

Thank you for your time and effort in reviewing our paper!

Thank you for the detailed rebuttal and revision. I appreciate that the authors acknowledged the inconsistencies and resolved part of my concerns. Considering the overall standards of this conference, I will maintain my score as is.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.