RANGER: Retrieval Agent for Navigating Graphs with Semantic Evaluation Rewards

Artem Mikhaylov; Pavel Konoplev; Nikolay Efanov; Artyom Sorokin; Evgeny Burnaev

cs.LGOct 20, 2026

RANGER: Retrieval Agent for Navigating Graphs with Semantic Evaluation Rewards

Authors: Artem Mikhaylov, Pavel Konoplev, Nikolay Efanov, Artyom Sorokin, Evgeny Burnaev

Organizations: Skolkovo Institute of Science and Technology (Skoltech), Moscow, Russia · Moscow Institute of Physics and Technology (MIPT), Moscow, Russia · AIRI, Moscow, Russia

Abstract

The integration of Large Language Models and Reinforcement Learning offers a promising direction for complex sequential decision-making tasks, such as multi-hop question answering over knowledge graphs. While LLMs provide strong semantic understanding and reasoning capabilities, they often struggle with precise, multi-step navigation in structured environments. Conversely, RL agents excel at learning navigation policies but are hindered by the difficulty of designing semantically meaningful reward functions. This paper introduces a novel hybrid approach in which an LLM serves as a mentor to an RL agent during training by providing dense, semantically informed reward signals. The RL agent, built on a Transformer-based policy and trained with Group Relative Policy Optimization, learns to navigate a knowledge graph to retrieve relevant information. The LLM evaluates the semantic relevance of the agent's traversed paths, generating reward signals that align the agent's behavior with the information needs expressed in a query. We integrate this Retrieval Agent for Navigating Graphs with Semantic Evaluation Rewards (RANGER) into a complete question-answering pipeline and evaluate it on the open question answering datasets. Experimental results show that the proposed approach outperforms both a baseline retrieval-augmented system with classical graph search and one using an RL agent trained with heuristic rewards, achieving a significant increase in NLP metrics and LLM-as-a-Judge scores. Our findings demonstrate that deep integration of LLMs into the RL training loop yields more effective and semantically aligned retrieval policies for complex reasoning tasks.

Figures & tables

Fig. 1: Comparison of heuristic and LLM-based rewards for paths in knowledge graphs. In this example the question is formed from the triplet

(e_{q}=\texttt{Eiffel Tower},r_{q}=\texttt{located\_in},e_{a}=\texttt{Paris})

. Given

(e_{q},r_{q})

, the agent must restore the initial triplet (direct

r_{q}

transition is masked out in the KG). The procedural heuristic ( H ) assigns the same reward to every path that reaches

e_{a}

, regardless of whether the intermediate triples provide evidence for the original question. In contrast, the LLM-based reward ( LLM ) evaluates whether the discovered path supports reconstructing the original triplet: paths that justify the triplet receive a high reward, while indirect or irrelevant paths receive lower rewards.

Fig. 2: Agent model architecture. Blocks containing trainable parameters are highlighted in yellow, while output predictions are highlighted in green. The value function head $V$ is used only for PPO algorithm.

Fig. 3: Answer generation and training pipeline. The agent is embedded into the QA-system retriever component and traverses the knowledge graph to gather information. Red arrows show the training loop.

Dataset	# Nodes	# Edges
HotpotQA	71,335	195,614
DiaASQ	54,220	239,517
TriviaQA	123,135	334,868

TABLE I: Characteristics of the HotpotQA, TriviaQA, and DiaASQ knowledge graphs.

Method	RL Algorithm	LLM Judge	BLEU-1	BLEU-2	ROUGE-L	METEOR	Exact Match
Random Walk	—	0.373	0.263	0.314	0.355	0.257	0.260
WaterCircles	—	0.673	0.455	0.324	0.578	0.452	0.467
RANGER(H)	PPO	0.657	0.434	0.305	0.545	0.432	0.440
RANGER(LLM)	PPO	0.691	0.437	0.304	0.565	0.451	0.447
RANGER(H)	GRPO	0.677	0.419	0.277	0.563	0.424	0.460
RANGER(LLM)	GRPO	0.697	0.467	0.340	0.585	0.468	0.493

TABLE II: Comparison of Random Walk, WaterCircles, and RANGER retrieval methods on the first 150 questions from HotpotQA. Best results are shown in bold, and second-best results are underlined.

Graph	RL Algorithm	Method	LLM Judge	BLEU-1	BLEU-2	ROUGE-L	METEOR	Exact Match
HotpotQA	—	WaterCircles	0.673	0.455	0.324	0.578	0.452	0.467
	GRPO	RANGER(H) †	0.767	0.505	0.350	0.651	0.509	0.533
	GRPO	RANGER(LLM) †	0.810	0.546	0.367	0.674	0.535	0.540
	PPO	RANGER(H) †	0.743	0.507	0.344	0.630	0.498	0.520
	PPO	RANGER(LLM) †	0.767	0.524	0.352	0.647	0.509	0.520
TriviaQA	—	WaterCircles	0.850	0.600	0.297	0.695	0.527	0.580

TABLE III: Results of hybrid retrieval methods on the first 150 questions from HotpotQA, TriviaQA, and DiaASQ for GRPO and PPO algorithms. Best results are shown in bold, and second-best results are underlined.

Fig. 4: Per-question comparison of RANGER(LLM) † and RANGER(H) † using LLM-as-a-Judge scores on the 150 questions from each dataset. Each stacked bar partitions questions into four mutually exclusive groups: equal zero scores, RANGER(LLM) † better, RANGER(H) † better, and equal positive scores.

Fig. 5: Dependence of the LLM-as-a-Judge score on the size of the LLM Mentor. The score drops substantially from Mistral Small 3.2 (24B) to Ministral 3 (8B), while the improvement from Mistral Small 3.2 (24B) to Mistral Medium 3.5 (128B) is marginal, suggesting diminishing returns from further scaling.

Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

Fig. 6: Learning curves of RANGER across HotpotQA, DiaASQ, and TriviaQA. The episode return corresponds to the reward assigned by the LLM mentor.

Fig. 7: Learning curves of RANGER on HotpotQA with Ministral 3 (8B), Mistral Small 3.2 (24B), and Mistral Medium 3.5 (128B) as LLM mentors. The episode return corresponds to the reward assigned by the LLM mentor.

Fig. 8: System prompt used by the LLM mentor to assign the retrieval reward.

Knowledge Graph Question Answering

Knowledge Graph Question Answering answers natural-language questions by finding and reasoning over entities and relations in structured knowledge graphs.

See all 165 papers

RACER: Reinforced Agent Collaboration for Explainable Reasoning on Knowledge Graphs
Aug 29, 2026Yuwei Lou, Hao Hu, Yuzhou Jiang +5LLM Reasoning with Graphs Knowledge Graph Question Answering
State Key Laboratory for Novel Software Technology, Nanjing University, China · Independent Researcher · Chinaunicom Software Nanjing Branch
UniGFM-RAG: Unify Graph Foundation Models and Large Language Models for End-to-End Retrieval and Reasoning
Oct 26, 2026Zicheng Zhao, Linhao Luo, Zongji Yu +4Graph Retrieval-Augmented Generation LLM Reasoning with Graphs
School of Automation and Intelligent Sensing, Shanghai Jiao Tong University, Shanghai 200240, China. · Department of Data Science and AI, Monash University, Melbourne, Australia. · Tencent Youtu Lab, Shanghai 200240, China. +2
KG-Hopper: Empowering Compact Open LLMs with Knowledge Graph Reasoning via Reinforcement Learning
Mar 22, 2026Shuai Wang, Yinan YuLLM Reasoning with Graphs Knowledge Graph Question Answering
Department of Computer Science and Engineering, Chalmers University of Technology and University of Gothenburg, SE-41296 Gothenburg, Sweden

Aug 29, 2026J/K move · Enter open · S save

RACER: Reinforced Agent Collaboration for Explainable Reasoning on Knowledge Graphs

Yuwei Lou, Hao Hu, Yuzhou Jiang, Zongfei Zhang+4

State Key Laboratory for Novel Software Technology, Nanjing University, China · Independent Researcher · Chinaunicom Software Nanjing Branch

LLM Reasoning with Graphs Knowledge Graph Question Answering Multi-Agent LLM Systems RL for Language Model Reasoning Knowledge Graphs

Open paper AskPDF arXiv

Large Language Models (LLMs) often suffer from hallucination and struggle with complex reasoning tasks requiring multi-hop domain knowledge. While integrating Knowledge Graphs (KGs) provides a structured and verifiable information source, current KG-enhanced LLM paradigms usually rely on single-agent path extraction and fixed prompting, lacking adaptability and facing huge search spaces. To address these challenges, we propose RACER, a Reinforced Agent Collaboration framework for Explainable Reasoning on knowledge graphs. RACER employs a semantic-aware action pruning and teacher-guided reinforcement learning mechanism to efficiently extract high-quality reasoning pathways from large-scale KGs. Furthermore, to mitigate single-path generation pitfalls, we introduce a cross-task accumulated shared memory graph paired with an attention-driven multi-path knowledge refinement module. Finally, RACER orchestrates these components through a four-role multi-agent collaboration system (GraphAgent, TemplateAgent, AnswerAgent, and CriticAgent) to dynamically refine prompts and evaluate answers. Extensive experiments on CommonsenseQA and OpenBookQA datasets demonstrate that RACER significantly outperforms state-of-the-art KG-enhanced LLM baselines with an average improvement of 5%, offering robust and highly interpretable reasoning capabilities.

Abstract

Knowledge Graph Question Answering

Explore similar work

RACER: Reinforced Agent Collaboration for Explainable Reasoning on Knowledge Graphs

UniGFM-RAG: Unify Graph Foundation Models and Large Language Models for End-to-End Retrieval and Reasoning

KG-Hopper: Empowering Compact Open LLMs with Knowledge Graph Reasoning via Reinforcement Learning