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

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.