Explore-on-Graph: Incentivizing Autonomous Exploration of Large Language Models on Knowledge Graphs with Path-refined Reward Modeling
Authors: Shiqi Yan
Yubo Chen
Ruiqi Zhou
Zhengxi Yao
Shuai Chen
Tianyi Zhang
Shijie Zhang
Wei-Qiang Zhang
Yongfeng Huang
Haixin Duan
Yunqi Zhang
Venue: ICLR 2026 Poster (2026)
Keywords: Knowledge Graph
Large Language Models
Knowledge-enhanced reasoning
reinforcement learning
Primary area: foundation or frontier models, including LLMs

Abstract: The reasoning process of  Large Language Models (LLMs) is often plagued by hallucinations and missing facts in question-answering tasks.
A promising solution is to ground LLMs' answers in verifiable knowledge sources, such as Knowledge Graphs (KGs). Prevailing KG-enhanced methods typically constrained LLM reasoning either by enforcing rules during generation or by imitating paths from a fixed set of demonstrations. However, they naturally confined the reasoning patterns of LLMs within the scope of prior experience or fine-tuning data, limiting their generalizability to out-of-distribution graph reasoning problems.
To tackle this problem, in this paper, we propose Explore-on-Graph (EoG), a novel framework that encourages LLMs to autonomously explore a more diverse reasoning space on KGs.
To incentivize exploration and discovery of novel reasoning paths, we propose to introduce reinforcement learning during training, whose reward is the correctness of the reasoning paths' final answers. 
To enhance the efficiency and meaningfulness of the exploration, we propose to incorporate path information as additional reward signals to refine the exploration process and reduce futile efforts.
Extensive experiments on five KGQA benchmark datasets demonstrate that, to the best of our knowledge, our method achieves state-of-the-art performance, outperforming not only open-source but also even closed-source LLMs.

Published as a conference paper at ICLR 2026
EXPLORE-ON-GRAPPH INCENTIVIZING AUTONOMOUS EXPLORATION OF LARGE LANGUAGE MODELS ON KNOWLEDGE GRAPHS WITH PATH- REWARD MODELING
Shiqi Yan': 12, Yubo Chen', Ruiqi Zhou², Zhengxi Yao?, Shuai Chen Tianyi Zhang', Shijie Zhang', Wei-Qiang Zhang! Yongfeng Huang 1.2 Haixin Duan Yunqi Zhang
"Zhongguancun Laboratory
2 DDpartment of Electronic Engineering, Tsinghua University
Institute for Network Sciences and Cyberspace, Tsinghua University
Ant Internationa,, Ant Group
ABSTRACT
The reasoning process of Large Language Models (LLMs) is often plagued by hal- lucinations and missing facts in question-answering tasks. A promising solution is to ground LLMs' answers in verifiable knowledge sources, such as Knowledge Graphs (KGs). Prevailing KG-enhanced methods typically constrained LLM rea- soning either by enforcing rules during generation or by imitating paths from a fixed set of demonstrations. However, they naturally confined the reasoning pat- terns of LLMS within the scope of prior experience or fine-tuning data, limiting their generalizability to -ott---diittiittionn graph reasoning problems. To address this issue, in this paper, we propose Explore-on- Grarrp (EoG), novel framework that encourages LLMs to autonomously explore more diverse reasoning space on KGs. To incentivize exploration and discovery of novel reasoning paths, we propose to introduce reinforcement learning during training, whose reward is the correctness of the reasoning paths' final answers. enhance the efficiency and meaningfulness of the exploration, we propose to incorporate path information additional reward signals to refine the exploration process and reduce futile ef- forts. Extensive experiments on five KGQA benchmark datasets demonstrate that, to the best of our knowledge, our method achieves state-of-the-ae performance, outperforming not only open-source but also even closed-source LLM
INTRODUCTION
Large language models (LLMs) have demonstrated impressive capabilities in various natural lan- guage processing tasks (Brown et al.] [2200] Team al., 2023 Liu et al. 2024; Dubey et al.) 2024). Despite their success, LLMs often struggle to produce faithful reasoning in question-answering (QA) tasks (Wang et al., 2023 Radhakrishnan et al.) 2023), primarily due to knowledge gaps and their susceptibility to hallucination (Ji al. [2023] Guan et al. (202)). To this end, the reliability of LLMMs real-world QA systems remains a significant concern.
To mitigate these issues, promising approach is ground LLMs' responses in external and veri- fiable knowledge sources (Lewis et al. [2020] Li et al.) 2023 Ren et al. (025). Knowledge graphs (KGs), which emerge an ideal candidate, provide solid factual information validate and guide the LLMs' reasoning process (Luo et al. 2024| Zhu et al. 2024).
Recent KG-enhanced reasoning methods can be broadly classified into two paradigms: rule-based methods and imitation-based methods. The former (Sun et af.) 2023] Zhang et al., (025) typically
leveraged a pre-defined set of rules ensure the logical consistency and faithfulness during the
LLM's reasoning process. The latter (Zhang et al. 2022a Wu et al. 2024 Jiang et al. 2025) mainly
"Corresponding author. Contact: zhangyq@mail 1, zgclab w.w.2llleed........... edu.cn Code and data available http://githubccom/ys)) 1333/FoG

---

Published as a conference paper at ICLR 2026
Rule/Imitation-bssed
Aetivial
Google explooves
Google
Canol
Londine
Cana!
Londson
Google
Sob
Lack of O.O.D. Pantenes
X
Afiic
Rensering Procca
Rosll
Anch
(b) Exploration (Ours)
Aedriia
Rob
John
Google
Cone
Ave.
Gondae
Google
Carof
Lonalen
Google
Inphent
Canel
Google
Zonalon
Allre
Knowladge Geaph
Google
Zonadon
smpllye
Explonzion Process
Rosia
Stariin sodei
Internddare sodei
Target modes
O.O.D. puteess
Dicanded paiss
Chosci paita
Figure 1: Examples of (a) rule/imitation-bsse method and (b) our exploration method. O.O.D. stands for Out-Of-Disttrinnn Of-Distribution
trained L.MSs extensive datasets directly mimic the reasoning patterns and heuristics embedded in the demonstrations.
However, existing methods usually failed to generalize to complex graphs, especially novel rea- soning patterns that fall outside the distribution of the fine-tuning data or pre-defined rules. For example, as shown in Figure
(a), "Google employee + Carol lives London" is the most common reasoning pattern corresponding to the question, and thus can be successfully recognized by ex- isting methods. However, the patterns "Google employee Bob colleague, John resides.at, London" colleague 4"
and "Google subridiary Youtube employee Alice lives.in, London" involve additional steps
and subsidiary S" thht deviate from the most common pattern, consequently rendering them out-of- distribution and challenging for existing methods. This observation motivates us to believe that navigating beyond the training distribution requires the capability venture into unfamiliar regions
of the graph. For example, in Figure b)) although the colleague, ," and subsidiary, " patterns are out of distribution, actively exploring these unfamiliar regions effectively helps discover these novel paths and give more accurate answers. We therefore argue that a complementary capability of autonomous exploration is essential to enhance generalization in the graph reasoning task.
In this paper, we propose novel framework named Explore-on-Grapp (FoG) to incentivize au- tonomous exploration LLMss on KGs. Inspired by recent advances in large reasoning models (Guo al. (2025), propose introduce reinforcement learning during training, which is preceded by a Supervised Fine-Tuning (SFT) step, to stimulate exploration capabilities. We use the correctness of the reasoning paths' final answers reward signals, which be computed programmatically given the golden label. Moreover, to improve the efficiency and semantic meaningfulness ploration process, we propose to incorporate path information additional reward signals to refine the exploration strategy. Specifically, we introduce a second dedicated training stage and leverage proposed path-refined reward. To evaluate the effectiveness of our approach, conducted extensive experiments on five KGQA benchmark datasets. Experimental results demonstrate that our method achieves state-of-the-ar performance, substantially outperforming a range of baseline methods and even surpassing the results of powerful closed- sourre- models.
the ex-
2 RELATED WORK
Knowledge graphs, which consist of relational triples that describe real-world entities and their rela- tionships (Hogan et 202T Chen et al.) 2022; Zhang et al.) 20222),,)) have been extensively adopted to guide the reasoning process of large language models to improve factuality and reduce hallu-
2

---

Published as a conference paper at ICLR 2026
Sire Adly
Apple
Elchwank
canpan'' mUn
lesvico
Preeter
Qurdiee
Aucria sorRINe
Appic
Coltesia
Google
ponten Slechanion
Teetwice
LIM
Fornot &
SPT
Geogpi
Pact check
Kaswledes Girph
Chikee
Tirast
Stgg2:: Heintorrenent Learateg
Phane Outcams Revard Madcliag
Phass 2: Pufh-relined Renaed Medding
Expeiioon
Experieces
Ameriic
Apple
Fooneet
Assorica
Ayple
Civemas
Townect
nall
Parni
disonia
BluckRool
Ponneet
Aesorica
Apple
Applee
Zoonect 100EI
FootecT
pallo
Aturica
Colfiornaa
Google
America
Cattfornta
Google
Poite Seres
America
Google
Aesorica
Google
Expleation Palka
Ravard Corppttricn
Dancems (11)
Roward
Explectioon Palte
Revar Compeztion
Putk Roward
The overall framework of our approach. Red arrows in the knowledge graph stands for the golden reasoning paths of the given question.
Figure 2:
cinations (Agrawal et al. 2024). Recent approaches to KG-enhanced reasoning could be broadly categorized into paradigms based on the generation of the reasoning process: rule-based meth-
ods (Sun et al. 2023 Zhang et al. 2025 Li et al. 2025) and imitation-based methods (Wu et al.) 2024 Mavromatis & Karypis 2025 Jiang et al. 2025). To ensure the faithfulness of the reasoning process, based methods guide the LLM's reasoning process on the KGs by pre-defined rules. For example, ToG (Sun et al. (023) introduced intuitive instructions to prompt LLMs to prune en- tities and relations from subgraphs. To improve retrieval efficiency, ReKnoS (Wang et al. (025)) proposed to recognize super-relations that are defined as a set of semantically related relations. Moreover, DoG (Li et al.) 2025) adopted graph-aware constrained decoding with structured chains to constrain the decoding process. The approaches were generally training-fri free, but did not enhance the intrinsic reasoning capabilities of the LLMs themselves.
Imitation- methods focus on emulating reasoning patterns derived from fine-tuning data. Early work mainly tried convert questions into executable logical forms (e.g. SPARQL) for knowl- edge graph retrieval (Lan & Jiang 2020) Das et al.] 2021; Ye et al. 2022), which heavily re- lied on the quality of generated queries. More recent work widely used Chain of Thought (CoT) to enhance LLM reasoning (Wu et al.] 2024 Zhao et al. 2024). To reduce incorrect thoughts, framework that grounds plans in
RoG (Luo al., (0244) proposed a wew.iinn-rerrivval-eeeeeea KGs. PoG (Chen et al. 2024) further improved the planning process through a reflection mecha- nism for self-correetion. Though Kg-Agent (Jiang et al.) (2025) employed several agents to itera- tively reason over KGs, it relied on supervised tine-tuning with synthesized program data and failed to generalize beyond pre-defined tool-based reasoning paths.
Different from previous work, we propose to incentivize autonomous exploration via reinforcement learning with path-refined reward modeling, enabling the model to explore novel reasoning paths that fall outside the distribution of pre-defined rules supervised fine-tuning data. Experimental results on several benchmark datasets prove the effectiveness of our method.
3 METHODOLOOGY
In this section, we introduce our Explore-on- (EOG) in detail, which consists of Supervised Fine-Tuning (SFT) stage and Reinforcement Learning (RL) stage. To equip LLMs with the foun- dational ability for graph exploration, introduce the SFT on knowledge graph reasoning tasks in
3

---

Published as a conference paper at ICLR 2026
To motivate the exploration of various reasoning paths and enhance its efficiency and meaningfulness, we introduce the RL with path- path-refined reward modeling in Section3.2 The general framework of our approach is illustrated in Figure 2
Section 3.1
3.1 SUPERVISED FINE-TUNING
Directly instructing the LLMs to explore KGs presents significant challenges, including an in- tractably large action space and extreme reward sparsity (Xiong et al. 2017 Lin al.) [018)) due to lack of prior knowledge. To bridge this gap, CoT offers a pathway of structured reason- ing demonstrations. by teaching LLMs the complex multi-step logic necessary for knowledge graph exploration (Wu et al. 2024). Compared to short CoT, long CoT allows more comprchensive and in-depth reasoning by exploring a wider range of logical paths (Chen et al. 2025). Therefore, we employ the long CoTI' Supervised Fine-Tuniin Tuning paradigm to establish a foundation for the subsequent exploration phase, which consists of two parts: (1) constructing the long CoT reasoning dataset and (2) fine-tuning LLMs with the constructed dataset.
Long CoT Dataset Construction. We carefully design the prompt to generate long CoT for graph reasoning, which requires the reasoning process to be structured, logical and to be aligned with KGs. The detailed prompt could be found in Figure 9 Due to its advanced deep thinking capabilities, we select Gemini 2.5 Flash (Comanici et al. 2025) to perform knowledge distillation to generate long- chain reasoning thoughts and the final answers. Given a knowledge graph 9 and a question as the query input, the generation sample from Gemini 2.5 Flash can be defined as the reasoning process z, which comprises both the reasoning paths (within "< think >< /think >" tags) and the final answers (within "< answer ></ /answer >" tags). Then we incorporate additional rules to filter the reasoning process that is both structurally and factually correct. Finally, the SFT dataset Deor is constructed, with high-quality long CoT reasoning processes.
Supervised Fine- Tine-Tnnngg. Following dataset construction, we perform SFT to endow the model with structured long CoT reasoning capabilities. We introduce a standard language modeling objective:
[Doal |=d
SSFT
Σ
log P(zz,) Gi, 9):0,
(1)
(DCoT]
where (g., 2:) E DCot is the i-th sample in the long CoT dataset, 2, represents the complete reasoning process for the i-th sample, 24,j is the j-th token of that sequence, and 0 denotes the LLM parameters. Through this phase, the LLM acquires a strong capacity for structured reasoning, estab- lishing essential foundation for the subsequent exploration phase. Reinforcement Learning (RL) can then effectively refine and diversify these learned pathways based on environmental feedback, rather than starting from unguided random exploration.
3.2 REINFORCEMENT LEARNING
While the SFT equips the LLM with the ability to generate structured reasoning paths, its outputs are usually confined the patterns observed in the training data, potentially leading subopti- mal reasoning. To facilitate the discovery of broader and more effective exploration space, we structure our reinforcement learning approach into two distinct phases. Inspired by advances such as Deepseek-RI R1 (Shao et al. [2224,, firstly, we introduce the Group Relative Policy Optimization (GRPO) to optimize the exploration policy on KGs based on the correctness of the reasoning path's final answers in Section 3.2. Then we integrate path-refined reward that provides additional signals to steer exploration toward more efficient and meaningful paths in Section 3.2.2
3.2.1 REINFORCEMENT LEARNING WITH OUTCOME REWARD
In the first phase, we optimize the exploration policy ne for enhancing the discovery of correct answers via a GRPO-based and outcome-supervisee reinforcement learning objective (G) Given the environment (G.g q) E DORPO, our LLM after the SFT stage could generate a group of candidate exploration processes { C P(c..) where each pt is i-th process sampled from the old policy Tem. Similar to reasoning process 2, each p contains both the exploration paths and the final answers with structured tags. The policy model could be optimized by maximizing the following reinforcement learning objective (0):
4

---

Published as a conference paper at ICLR 2026
T (f) = E Lg (gg. (P(e.)))9)))
(2)
min U (pa(p;)) clip (vo((s.)), 1 e) A(p:) kL (Te (
where (pt.)) no (0....99.. and A(p)) ( (((p)) The importance sam-
Ruau (PL (l.9..p.p)))
su(((((p))}
pling ratio (p,,)).) measures how much more likely the new policy To is to generate Pi,s com- pared to the old policy T0w- A(p,) is the relative normalized advantage. and B are hyperparame- ters. DxL. (eer computes the KI.-divergence between the updated policy and a reference policy. R(p;) is the reward function that measures the quality of diverse exploration paths (p.),-1-
By optimizing Equation ( the LLM learns to favor exploration paths that are highly rewarding and reliable relative to other sampled paths. Therefore, we define the outcome reward R(p) to encourage generating exploration paths that contain the right answers. Specifically, we utilize the entity-level Fl score to measure the correctness of the final answers of generated cxploration sequence p. We first recognize the set of predicted answer entities Ap through extracting the texts within the "< answer >< /answer >" tags in the generated exploration sequence. Considering the set of ground-truth answer entities Ag. then the outcome reward I Roatcome (p) is calculated as follows:
Roatcome (p) = Pre- Rec
IAp Agl. IApl
IAp Agg |Agl
where Pre
Rec
Pre + Rec
We set the reward to the predicted answer set Ap is empty. Note that the outcome reward Routcome (p) is automatically set to 0 for all samples that do not contain correctly formatted answer tags in the exploration sequence. Therefore, this reward implicitly encourages the correct structured exploration processes during the policy optimization process. For this reason, did not include an additional format reward in this phase.
3.2.2 REINFORCEMENT LEARNING WITH PATH-REFINED REWARD
The process of generating an exploration path reflects the LLM's reasoning trajectory through KG. Rewarding correct paths minimizes exploration of wrong directions. In addition, the exploration paths with sequential chains of connected relational triples contain rich semantic information, which can help the LLM generate more comprehensive and in-depth exploration processes. In this phase, we suggest using path information to generate auxiliary rewards, thereby optimizing the exploration process and curtailing inefficient actions.
The path-based based reward, Rpat(p) is formulated to quantify the proportion of ground truth reasoning steps successfully articulated in the generated thought process. To obtain the ground-truth reason- ing path ry for datasets that do not provide them explicitly, we implement a "Search-and- Verify" pipeline. First, We identify the topic entities in the question and the ground-truth answer entities in the Knowledge Graph. We then perform a Breadth-Firss Search (BFS) to retrieve all potential paths connecting the topic entities to the answer entities within maximum hop constraint. This step en- sures high recall of potential reasoning chains. Second, since BFS may yield spurious paths that are topologically connected but semantically unrelated, we employ a LLM (e.g., Gemini-2.55Flaat to semantically verify these paths. The LLM is prompted to determine if a path logically corresponds to the question's intent, and only validated paths are retained as rg.
Given ground-truth reasoning path rg. which consists of a set of structured triplets, we first extract this set of triplets, denoted as T ((st, Fi, |2) For each triplet 4; = (St, Fi, o;) E T, we check if all three components subject 5;, relation rı, and object o:-are are present substrings within the generated reasoning text Pthink The reward is then calculated as the ratio of fully matched triplets to the total number of triplets in the ground-truth path:
Reuah (p)
Σ GET
I[s; E Pitink Ar; Pthink o; E Pihink)
(4)
T
where II(-) is the indicator function, which returns if the condition is true and 0 otherwise. This function provides a direct and interpretable score of how faithfully the model's reasoning follows the correct path, hence contributing to the efficiency and meaningfulness of exploration process.
5

---

Published as a conference paper at ICLR 2026
Table 1: Performance of EoG and previous state-of-the-ari models the five KGQA sets. The best scores are in bold. marks the performance of the closed-source model which uses the same input as our EoG. EoGyrr is the model which is only trained with SFT datasets but not with RL.
WebQSP
CWQ
GrailQa
QALDI0-en 2WikiMultihop
Method
Model
Hit@1 1 F1
Hit@1
FI
Hit@1 Fl
Hit@1 F1
Hit@l F1
KD-CoT 2023
1lmma-2-78
68.6
52.5
55.7
EWEK QA 2024
71.3
52.5
60.4
ChatGPT
76.2
57.6
50.2
ToG
2023
GPT-4
82.6
68.5
53.8
RoG 2024
Llama-2-7B
85.7
70.8
62.6
56.2
ODA
2124
GPT-4
66.7
EffQQA
2025
GPT-4
82.9
69.5
78.4
51.4
GNN-RAGT
2002
Llama-2-7B
85.7
71.3
66.8
59.4
KG-Agent
(2025
Llama-2-7B
83.3
81.0
72.2
69.8
86.1
DoG
2025
Qwen2.5-7B
92.7
74.1
84.2
Llama-3.1-8B
91.4
76.2
GCR 2025
Llama-3.1-8B
92.2
79.1
75.8
61.7
1Gmmini-2.5 Flash
91.8
78.2
65.5
59.3
90.3
83.8
56.7
46.2
83.9
83.1
'Gemini-2.5 Pro
92.1
79.8
71.9
65.3
91.6
84.5
58.6
48.3
85.1
82.6
1GPT-5
86.1
77.5
74.1
67.6
90.5
85.4
59.2
50.4
84.2
Qwen2.5-7B
83.9
72.6
68.3
60.3
89.2
87.6
55.6
44.1
82.5
81.9
EoGsr
1 3.1.8818..
86.3
74.5
70.5
62.1
91.4
88.2
57.1
48.7
83.1
82.7
Qwen2.5-7B
90.7
78.1
82.7
73.8
91.7
88.5
67.3
57.8
83.9
82.9
EoG
Llama-3.1-88 1-88B
92.8
81.3
86.6
77.9
92.1
90.6
70.6
61.9
85.3
84.3
Furthermore, we introduce the joint reward (p) to incentivizing the LLM to produce both high- quality exploration paths and the right final answers:
Ryoine (p) Reatcome (p) + ar Reppa
(5)
where a the coefficient that controls the relative influence of the outcome reward and the path reward on the exploration optimization policy.
4 EXPERIMENTS
4.1 EXPERIMENTS SETUP
Datasets.
Following previous research, we evaluate our method on five widely-used benchmark datasets: CWQ (Talmor & Berant 2018), WebQSP (Yih et al. (0166) GrailQA (Gu et al.) (021), QALD10-en (Usbeck et al.) 20244 and 2WikiMultihop (Ho et al., 2020). The first three bench- marks are constructed based on Freebase, whereas QALDT0-en and 2WikiMultihop are built upon Wikidata. The details of the datasets are described in Appendix B
Baseline. We compare EoG with 10 previous baseline methods (Luo et al. 2024 Sun et al. 2019). such as GCR and DoG. The detailed descriptions of the baseline methods are listed in Appendix C particular, we report the performance closed-source LLMs with strong deep-thinking abil- ity, Gemini 2.5 series (Comanici et al. 2025) and GPT-5 by querying the APIs with the same instructions and inputs as our EoG, including the questions and the corresponding KGs. The imple- mentation details provided in Appendix [
Evaluation Metrics. In the evaluation of baselines, we adopt the Hit@ and F1 metrics following previous work (Mavromatis & Karypis 2025). The Hit@1 metric focuses whether any correct answer is present in the prediction, while the Fl metric evaluates the coverage of all answers by comprehensively considering the precision and recall of the prediction.
Implementations. To validate the general applicability of our approach, we apply FoG to two open- source LLMs, Owwnn.5-7B-Innseee Insttruct (Yang al. 2024) and Llama-3. 1ouma-3.1-8B-Bae --8t-Innttuct (Dubey al., 2024). For fine-tuning, we use Geemini-2.5-Flaa to generate long chain-of-thoupe datasets. For

---

Published as a conference paper at ICLR 2026
reinforcement learning, we implement the GRPO method using verl (Sheng et al. 2025 details on experimental settings can be found in Appendix D
More
4.2
MAIN RESULTS
From Table we have several observations. First, our BoG outperforms previous KG-enhanced reasoning methods with similar amounts of LLM parameters. Impressively, it even exceeds the performance of existing closed-source deep-thinking LLMs such as Gemini 2.5 Pro and GPT-5. It demonstrates the remarkable strength of EoG's autonomous exploration capability. Second, the performance of EoCisrr significantly drops on all datasets compared with EoG, which indicates that EoG's strong exploration capability is attributed to the reinforcement learning stage, rather than knowledge distillation from LLMs, further demonstrating the effectiveness of our proposed RL with path-refined reward modeling. Finally, EoG built upon two base models both demonstrate strong performance, proving the general applicability of our method to different LLM architectures.
4.3 ABLATION STUDY
Ablation Study. We conduct an ablation study on the CWQ and WebQSP test sets to validate the contribution of each component in our framework. The results are shown in Table Note that when removing the outcome reward, we use the Hit@1 score instead to reward the exploration process. First, we observe that the path reward critical to performance, demonstrating that our path-refined reward effectively enhances EoG's exploration by optimizing the semantic meaningfulness of its reasoning paths. Furthermore, the RI phase with outcome reward constitutes a significant contribu- tion to EoG's performance. This shows that a granular evaluation of the answers plays important role in the process of exploring policy optimization, demonstrating the necessity of using the score. Finally, EoG without SFT, which is only trained with RL, shows suboptimal performance, regardless of whether the In-Context Learning (ICL) is applied, proving the necessity of adopting SFT for the cold start in framework.
Table 2: Ablation studies of EoG on CWQ and WebQSP datasets.
CWQ
WebQSP
Model
Hit@1
F1
Hit@1 1
F1
EoG
82.6
73.9
92.8
81.3
w/o path reward
81.5
70.8
90.2
77.3
w/o outcome reward
62.7
51.4
65.5
56.2
w/o SFT
70.3
63.1
75.9
65.8
w/o SFT, w/ ICL
70.7
63.8
77.2
66.5
Balance between Outcome and Path Reward. To investigate the optimal balance between the outcome and path reward, we evaluated various ratios a in Equation (5), which illustrated in Figure Note that the horizontal axis represents the different ratios, while the vertical axis indicates the performance difference (%) compared to using only the outcome reward. We observe that when ratio is too small, the performance drops significantly. We hypothesize that reducing path signals may lead EoG to generate eтrоr or meaningless paths and hurt the performance. When the ratio is excessively increased, EoG may pay less attention to the correctness of the answers given the exploration paths, which leads to performance degradation.
3
Table 3: Evaluation of the impact of the path reward.
Dataset
Setting
Averuge Output Length(.)
Compechenssiveness(()
Relevance(() Exploration()
BoG
91.9
88.8
CWQ
BoG w/o path reward
2067
89.8
92.6
85.1
BaG
851
92.7
97.1
78.9
WehQSP
FoG w/o reward
926
91.9
95.3
74.3
Impact of Path Reward. We conduct experiments to measure the impact of path reward on EoG's output in terms of its average length, comprehensiveness, relevance, and exploration, with the latter three metrics being assessed by querying GPT--4-mini (Hurst et al., 2024) using custom-designed

---

Published as a conference paper at ICLR 2026
Oveall
Expleatun
Compretan-
ercnnoss
WeROSP Cuq UauAA 2WaRMZEBUOQA
Pafemmree Diftreree Duporm
Relevand
Correct
Depth
Factuality
DoG
GER
-+ 10G
ExGi
Figure 3: Performance of EoG with different ra- Figure A multi Ialti-dimensional performance tios of the path reward to the outcome reward. In comparison different reasoning paths. the figure, the horizontal axis represents the differ- ent ratios, while the vertical axis indicates the per- formance difference compared to using only the outcome reward.
prompts. The relevant prompts are shown in Figure I From the Table it is demonstrated that our path reward method can improve the efficiency and meaningfulness of our EoG's output.
4.4 ANALYSIS OF REASONING QUALITY
In this section, we evaluate the quality of the reasoning process of different methods across six dimensions. We select GPT-4o-mini the judge and the relevant prompts are shown Figure II
The results show that EoG performs outstandingly compared to other methods, indicating that model can effectively integrate knowledge graph information to generate comprehensive and accurate answers. Notably, our model has achieved significant improvements in reasoning depth, exploration, and comprehensiveness, demonstrating the substantial enhancement the two-stage reinforcement learning method we employed on the exploration policy.
4.5 PERFORMANCE ON COMPLEX REASONING SCENARIOS
divided the test of the CWQ dataset according to different logical patterns and reasoning depths. As shown in Table 4 we observe that EoG out- performs both GCR and DoG in almost all subsets, especially in the more challenging reasoning scenarios, such reasoning over superlative patterns or 2 3 hops. We claim that this is because EoG actively explores a larger reasoning space on the graphs, which gains more logical and semantic information to help understand various logical patterns and deeper reasoning. In general, the results on different causal patterns and hops show the effectiveness of our method complicated reasoning scenarios.
Following previous work (Luo al. 2025).
Table Performance (FI scores) comparison on different logical patterns and reasoning depths.
Method
Conjuction
Compurative
Superlative
Composition
1-hop
2-hop
3-hop
24-hopp
Overall
GCR
H
73.1
66.3
64.4
66.8
79.0
71.9
62.1
47.7
68.2
Fl
63.7
$7.7
52.6
59.7
66.3
63.0
56.6
45.8
60.3
DoG
Hire1
723
77.8
68.7
75.9
75.1
74.1
69.9
63.3
73.7
F1
68.3
45.9
49.2
50.3
53.7
64.5
46.7
$3.2
HR&T
77.2
85.2
73.4
82.8
83.3
79.1
83.2
76.8
82.6
Fl
70.2
77.2
64.7
76.8
76.2
72.0
78.1
69.6
73,9
8

---

Published as a conference paper at ICLR 2026
4.6 ANALYSIS OF EXPLORATION BEHAVIOR
To examine how reward design influences exploration behavior, we evaluate models using explo- ration efficiency and coverage of the reasoning space on the CWQ test set. Exploration efficiency measures the average number of explored triples required to identify one correct reasoning triple, while reasoning coverage quantifies the proportion of ground-truth reasoning triples successfully discovered. Detailed metric definitions are provided in Appendix
Table 5: Comparison of exploration efficiency and reasoning coverage on the CWQ test set.
Model
Exploration Efficiency (1)
Coverage (1)
EoGSFT
2.877
0.615
EoGroatome
3.028
0.689
EoG
2.887
0.723
As shown in Table 5 EoG achieves the highest reasoning coverage while maintaining efficiency comparable to the SFT baseline. Although outcome- RL improves coverage, it introduces noisy exploration. In contrast, our path-refined reward encourages broader yet precise reasoning, leading to better coverage without increasing exploration overhead.
4.7 PERFORMANCE ON OUT OF DISTRIBUTION DATASETS
Figures a) and show that EoG outperforms EoGsPr on four datasets O.O.D. settings. Lever- aging the autonomous exploration graphs, EoG reliably maintains model performance stability across diverse datasets and data sources. Figures c(c) and d) show that EoG achieves higher O.O.D.- to-I.I.D. ratios than EoGsrT, reflecting its strong robustness and cross-domain generaliz- ability via reinforcement learning with path-refined reward over KGs.
TWA6: Waxg0
2908: GaiRAA CRQ WEOORP
89.38
47:20
40
57.40
60
$2.80
$2.50
17.00
57.50
2000.00
54.7%
$5.155
66.7%
1100-15
67.3%5
94
72 7%
61:00
70.50
$7.50
$2.00
$2.60
19.70
75.70
100.0%
10.015
61.655
111
076
67
55.5%
57.0%
24.41
38.85
30
$5.10
67.10
53.20
77.40
55.30
29
99.8%
46.8%
$3.4%
100.0%
78.7%
$2.45
90.7%
300.055
Wabkisr CWQ
GmilgA 2W16
CWD
GeallAA
Welkgs LWU
GmalyA
CWG
2Win
BoGgrr(Hit@@)
(b) EoG(Hit@) 1)
(c) EoGser(ratio)
(d) EoG(ratio)
Figure 5: Hit@| 1 comparison and performance ratios across four datasets under out-of-distribution (O.O.D.) settings. The O.O.D.-to-LI.DD. ratio is defined as a model's performance score on Out-of- Distribution (O.O.D)) data divided by its performance score on Independent and Identically Dis- tributed (L..D.) data. Subfigures (c) and (d) show the O.O.D.-to-IIDD. ratios of the models on the four datasets. 2Wiki refers to the 2WikiMultihop dataset. The Y-axis shows the dataset the model was trained on and the X-axis shows the dataset the model was evaluated on.
4.8
CASE STUDY
Figure 6 illustrates the comparison of EoG and GCR on the knowledge graph rea- soning task instance. Although the question presupposes the relational pattern "Ex, Iwporotsrrom(z, Japan)" active exploration of our model uncovered an alternative and unseen pattern: "Er. entity "m.04'prrpp" Due to the lack prior knowledge, GCR fails to recognize this pattern. This shows EoG's capacity to adapt to unexpected causal patterns through exploration. Furthermore, in case some facts are missing in the graph, such as the label of 048prpppp the relation "ISO", our model can still leverage known semantic information for inference and prediction, demonstrating the strong capability of path- based policy optimization. The above observations demonstrate the effectiveness of method in autonomous exploration of knowledge graphs
(rntttsrrommmmoossssroooo Japann
through exploring the unknown

---

Published as a conference paper at ICLR 2026
Queation:: country Legical Expression: Bis [CountrytX) A IS0Ks, 736) A Imparts/rents, Japan))
imports Japan, county"Ammeer
Raw Ouipat
Resseningg Puths
Reossning Parkcclpua is location country argogx qulem Tights Langagee
GCR
Jipa
yplles
Paplish
Suare
kurgage hwneeniirgggggnnnnooooo lerguge www.ggooerrrreeeeeeeee
Pathclapan elyrpioxochyppcc partsipatng cruntry slympios portequaed
1916 Summrr Olyrpicce olympip pww.paosssooeeo poteepinnnrirnn.ccomm contiiox
Appan
Obyepics
Candé
Cannda Crnnda
Bonsening Pathi cnagariiiiiinn arganiniionn fnundc.cepricsiinn foundad o world Troke Orgarzation ot ongantmttes orgeniitiion Standere Tamoasts Anewerr
WTV
Tarann
The ssorece Tancusia
Ours
impors
and nuries of736
Mdeenttyy Noy kattliee and Relations: "Japani" (begrs look
fidd
"ruditpprpp Tlocatiiniigg imperts,,se exportsingerted red_from from, "Japerr) This nors au34kpprpp impprts fnom Ispan.
Meentty the cenntry amaristed with 'n Billgrpp'
''Sudan llecation resion plans inported frumt 'n048pprsp"' .... recass tapar.
(Norle??
Look ISO
antion::: This
150 austee niglt impleii dreecly vieble (SSU rumber
""Reeoe coalenti the problen with the gives grople The poph... Harrvess tee task requires ssing "eaty" the prorited grapa.
inked thruuh anether
Jqua
Frocuss the '"ipparts frame Japant" part and given asswort** The correct answer is ingoning Japan saa
Ni Migggg
"Suden'
poth
looaton imparts inpors
foot "Japanl" nom pillgrup'
fhom
Sadan
In ! mate Sadan ippecs foom in phifpeeeppp Jain s. "SSmmperr path ISO implice=* Loweerr wther an optiet 150 sombert mittionn Tennnor dioely use the ISO curber of 736 a Shaccdo
Jepanca ''Sudin'"
C"Cencttddnn lased avatlsble Information and target unewerst The moe diros pat Sudar' foo Japan' is terss maok given grgp, shoughh the
catly
New O.O.D. Panoons 3xJCConnyy
'a.44ipprp''s
fromjjas The rumber 7360 poperry mentioned explactly linked
the pravided information, conntry that import from Jugun and has ISO number of Th6 Sudios The graph shous Sudua impects from sulldppwgg which in turn imports froms Japus, and it's asammed that 150 sumber 136. Theelfor, county dul irpoct Jupan
provided gratt.
country
"aadensd (aaee/aaaalllsaaeeeece (clusseer>
Figure 6: An example of question and the corresponding answer from FoG and GCR. Different types of entities are distinguished with different colors.
5 CONCLUSION
In this paper, we propose novel framework called Explore-on-Graph (EoG) to address the criti- cal challenge of limited generalizability in existing KG-enhanced LLM reasoning methods, which often fail on ouitt--distribution reasoning patterns. EoG employs reinforcement learning, guided by both the correctness of the final answer and path-refined reward for efficiency, to incentivize the model's exploration of novel and meaningful reasoning paths. Furthermore, extensive experi- ments demonstrate that FoG achieves new state-of-the-an results, significantly outperforming ex- isting open-source models and even surpassing the performance of powerful closed-source LLMs. Our analysis also provides key insights into RL training strategies for KGQA. Finally, future work could investigate how to leverage knowledge graphs to explore more sophisticated reward strategies, thereby enabling more efficient and meaningful reasoning.
ACKNOWLEDGEMENT
This work supported by Ant Group Research Fund. The proposed method has been imple- mented and validated on Ant Group's 's business datasets.
ETHICS STATEMENT
The data used in this paper is sourced exclusively from publicly available, open-source KGQA datasets (see Appendix BJ. As these datasets do not contain any personally identifiable information or other sensitive data, our experiments raise no apparent ethical concerns related to data privacy or human subjects.
10

---

Published as a conference paper at ICLR 2026
REFERENCES
Garima Agrawal, Tharindu Kumarage, Zeyad Alghamdi, and Huan Liu. Can knowledge graphs reduce hallucinations in Ilms?: survey. In Proceedings of the 2024 Conference of the North American Chapter the Association for Computational Linguisties: Human Language Tech- nologies (Volume 1: Long Papers), pp. 3947-3960, 2024.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhari- wal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agar- wal, Ariel Herbert- Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neu- ral Information Processing Systems, volume 33, pp. 1877-1901. Curran Associates, Inc., newrips ccppaprr files/paper/Dn 2020. URL #11e://87oo6brro0477111rraaa2222
Liyi Chen, Panrong Tong, Zhongming Jin, Ying Sun, Jieping Ye, and Hui Xiong. Plan-on-graph: Self-correcting adaptive planning of large language model on knowledge graphs. Advances in Neural Information Processing Systems, 17:37665-37663 2024.
Qiguang Chen, Libo Qin, Jinhao Liu, Dengyun Peng. Jiannan Guan, Peng Wang, Mengkang Hu, Yuhang Zhou, Te Gao, and Wanxiang Che. Towards reasoning era: A survey of long chain-of- thought for reasoning large language models. arXiv preprint arXiv:2503.0956 2025.
Yubo Chen, Yunqi Zhang, and Yongfeng Huang. Learning reasoning patterns for relational triple extraction with mutual generation of text and graph. In Smaranda Muresan, Preslav Nakov, and Aline Villavicencio (eds.), Findings of the Association for Computational Linguistics: ACL 2022, pp. 1638-1647, Dublin, Ireland, May 2022. Association for Computational Linguis- tics. doi: 10. 10.18653/v1/0222 htt.:/553.ii222222nnnnnng-aalll findings-acl.1299 URL/https /acl anthe org/2022. F Findings-ac 1297
Gheorghe Comanici, Eric Bieber, Mike Schaekermann, Ice Pasupat, Noveen Sachdeva, Inderjit Dhillon, Marcel Blistein, Ori Ram, Dan Zhang, Evan Rosen, al. Gemini 2.5: Pushing the frontier with advanced reasoning, multimodality, long context, and next generation agentic capa- bilities, arXiv preprini urXiv:2507.06266 2025.
Rajarshi Das, Manzil Zaheer, Dung Thai, Ameya Godbole, Ethan Perez, Jay Yoon Lee, Lizhen Tan, Lazaros Polymenakos, and Andrew McCallum. Case-based reasoning for natural language queries over knowledge bases. In Marie-Francine Moens, Xuanjing Huang, Lucia Specia, and Scott Wen-tau Yih (eds.), Proceedings of the 2021 Conference Empirical Methods in Natural Language Processing, pp. 9594-9611, Online and Punta Cana, Dominican Republic, November 1etp:022.emmmlmmmmaa 755/
2021. Association for Computational Linguisties. doi: 10. wwn.p-ma http://...oooo222.2..eeommmmaaam
URL
https::/acclnthool/ http::///cccaantoooooooooo/22222 org/
Mohammad Dehghan, Mohammad Alomrani, Sunyam Bagga, David Alfonno--Hermelo, Khalil Bibi, Abbas Ghaddar, Yingxue Zhang, Xiaoguang Li, Jianye Hao, Qun Liu, et al. Ewek-qa: Enhanced web and efficient knowledge graph retrieval for citation-based question answering systems. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Vol- ume 1: Long Papers), pp. 14169-14187, 2024.
Zixuan Dong, Baoyun Peng. Yufei Wang. Jia Fu, Xiaodong Wang, Xin Zhou, Yongxue Shan, Kangchen Zhu, and Weiguo Chen. Effiqa: Efficient qnestion-answeriig with strategic multi- model collaboration on knowledge graphs. In Proceedings of the 31st International Conference on Computational Linguistics, pp. 7180-7194, 2025.
Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Amy Yang, Angela Fan, et al. The llama 3 herd of models. arXiv e-prints, pp. arXiv-2407, 2024.
11

---

Published as a conference paper at ICLR 2026
Yu Gu, Sue Kase, Michelle Vanni, Brian Sadler, Percy Liang, Xifeng Yan, and Yu Su. Beyond i..d:: Three levels generalization for question answering on knowledge bases. In Proceedings of the Web Conference 2021, WWW '2,, pp. 3477-3488. ACM, April 2021. doi: 10.1145/3442381. 3449992. URL http:ttttt//ecc //p: doi wrg.
.34999999 3449992
Xinyan Guan, Yanjiang Liu, Hongyu Lin, Yaojie Lu, Ben He, Xianpei Han, and Le Sun. Miti- gating large language model hallucinations via autonomous knowledge graph-based retrofitting. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pp. 18126-18134, 2024.
Daya Guo, Dejian Yang, Haowei Zhang, Junxiao Song, Ruoyu Zhang, Runxin Xu, Qihao Zhu, Shirong Ma, Peiyi Wang. Xiao Bi, et al. Deepseek-rl: Incentivizing reasoning capability Ilms via reinforcement learning. arXiv preprint arXiv:2501. 129488 2025.
Xanh Ho, Anh-Khou Duong Nguyen, Saku Sugawara, and Akiko Aizawa. Constructing multi- hop qa dataset for comprehensive evaluation of reasoning steps, 2020. httpttss///xxiii
org/abs 2011 01060
Aidan Hogan, Eva Blomqvist, Michael Cochez, Claudia D' D'amato, Gerard De Melo, Claudio Gutier- rez, Sabrina Kirrane, José Emilio Labra Gayo, Roberto Navigli, Sebastian Neumaier, Axel- Cyrille Ngonga Ngomo, Axel Polleres, Sabbir M. Rashid, Anisa Rula, Lukas Schmelzeisen, Juan Sequeda, Steffen Staab, and Antoine Zimmermann. Knowledge graphs. ACM Comput. Surv, 54(4), July 2021. ISSN 0360-0300. doi: 10.1145/3447772. URL httph:ttt////mm //ttts::/do.... org/10. 1145/3447172
Aaron Hurst, Adam Lerer, Adam Goucher, Adam Perelman, Aditya Ramesh, Aidan Clark, AJ Os- trow, Akila Welihinda, Alan Hayes, Alec Radford, et al. Gpt-4o system card. arXiv preprint arXiv:2410.21 2024.
Ziwei Ji, Nayeon Lee, Rita Frieske, Tiezheng Yu, Dan Su, Yan Xu, Etsuko Ishii, Ye Jin Bang, Andrea Madotto, and Pascale Fung Survey of hallucination in natural language generation. ACM computing surveys, 55(12)11338, 2023.
Jinhao Jiang, Kun Zhou, Xin Zhao, Yang Song. Chen Zhu, Hengshu Zhu, and Ji-Rong Wen. KG-agent: An efficient autonomous agent framework for complex reasoning over knowledge graph. In Wanxiang Che, Joyce Nabende, Ekaterina Shutova, and Mohammad Taher Pilehvar (eds.), Proceedings of the 63rd Annual Meeting of the Association for Compulational Linguistics (Volume 1: Long Papers), pp. 9505-9523, Vienna, Austria, July 2025. Association for Com- putational Linguistics. ISBN 179-8-89176-25111 doi: 10. 10.18663/11/225..ce
URL
2025 wttp://2225..cl11eeeee 468/
Yunshi Lan and Jing Jiang. Query graph generation for answering multi-hop complex questions from knowledge bases. Association for Computational Linguistics, 2020.
Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich Küttler, Mike Lewis, Wen-tau Yih, Tim Rocktäschel, et al. eetrieval-augmente gener- ation for knowledge-intents nlp tasks. Advances in neural information processing systems, 33: 9459-9474, 2020.
Kun Li, Tianhua Zhang, Xixin Wu, Hongyin Luo, James R. Glass, and Helen M. Meng. Decoding on graphs: Faithful and sound reasoning on knowledge graphs through generation well-formed chains. In Wanxiang Che, Joyce Nabende, Ekaterina Shutova, and Mohammad Taher Pilehvar (eds.), Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume I: Long Papers), pp. 24364, Vienna, Austria, July 2025. Association for Com- putational Linguistics. ISBN 979-8-89176-25111 doi: 10. 10.18653/v1/2000 1/2025.1 acl- 186. URL Cctps://aclantiin bww.llaattiooooo..ooo222........ Long.llloooooonno.. 11867
Tianle Li, Xueguang Ma, Alex Zhuang, Yu Gu, Yu Su. and Wenhu Chen. Few-shot in-context learning on knowledge base question answering. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume I: Long Papers), pp. 6966-6988 2023.
12

---

Published as a conference paper at ICLR 2026
Xi Victoria Lin, Richard Socher, and Caiming Xiong. Multi-hop knowledge graph reasoning with reward shaping. In Proceedings of the 2018 Conference on Empirical Methods in Natural Lan- guage Processing, EMNLP 2018, Brussels, Belgium, October 31 -Nooemmber 4, 2018, 2018.
Aixin Liu, Bei Feng, Bing Xue, Bingxuan Wang, Bochao Wu, Chengda Lu, Chenggang Zhao, Chengqi Deng, Chenyu Zhang, Chong Ruan, et al. Deepseek-v3 technical report. arXiv preprint arXiv:2412.19437. 2024.
Linhao Luo, Yuan-Fang Li, Gholamreza Haffari, and Shirui Pan. Reasoning on graphs: Faithful and interpretable large language model reasoning. In International Conference on Learning Repre- sentations, 2024.
Linhao Luo, Zicheng Zhao, Chen Gong, Gholamreza Haffari, and Shirui Pan. Graph-constrained reasoning: Faithful reasoning on knowledge graphs with large language models. In Forty-second International Conference on Machine Learning, 2025.
Costas Mavromatis and George Karypis. Gnn-rag: Graph neural retrieval for efficient large lan- guage model reasoning on knowledge graphs. In Findings of the Association for Computational Linguistics: ACL 2025. pp. 16682-16699, 2025.
Ansh Radhakrishnan, Karina Nguyen, Anna Chen, Carol Chen, Carson Denison, Danny Hernandez, Esin Durmus, Evan Hubinger, Jackson Kernion, Kamile Lukosiute, et al. Question decomposition improves the faithfulness of model- generated reasoning. CoRR, 2023.
Ruiyang Ren, Yuhao Wang. Yingqi Qu, Wayne Xin Zhao, Jing Liu, Hua Wu, Ji-Rong Wen, and Haifeng Wang. Investigating the factual knowledge boundary of large language models with retrieval augmentation. In Proceedings of the 31st International Conference on Computational Linguistics, pp. 3697-3715, 2025.
Zhihong Shao, Peiyi Wang, Qihao Zhu, Runxin Xu, Junxiao Song, Xiao Bi, Haowei Zhang, Mingchuan Zhang, YK Li, Yang Wu, et al. Deepseekmath: Pushing the limits of mathemati- cal reasoning in open language models. arXiv preprint arXiv:2402.03300, 2024.
Guangming Sheng, Chi Zhang, Zilingfeng Ye, Xibin Wu, Wang Zhang, Ru Zhang, Yanghua Peng, Haibin Lin, and Chuan Wu. Hybridflow: A flexible and efficient rIhf framework. In Proceedings of the Twentieth European Conference on Computer Systems, EuroSys '25, pp. 1279-1297 ACM, doi: 10.1145/36900313366607
March 2025.
URL http://dx www.wxwc.ii....o. 0r.10..11411
[389003 3696075
Haitian Sun, Tania Bedrax- Weiss, and William Cohen. PullNet: Open domain question answering with iterative retrieval on knowledge bases and text. In Kentaro Inui, Jing Jiang, Vincent Ng, and Xiaojun Wan (eds.), Proceedings of the 2019 Conference on Empirical Methods in Natural Lan- guage Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pp. 2380-2390, Hong Kong, China, November 2019. Association for Com- putational Linguistics. doi: 2t.18653/v//199 1242 URL attps::/aclantholle.
12421
Jiashuo Sun, Chengjin Xu, Lumingyuan Tang, Saizhuo Wang, Chen Lin, Yeyun Gong, Heung- Yeung Shum, and Jian Guo. Think-on-graph, Deep and responsible reasoning of large language model with knowledge graph. 2023.
Lei Sun, Zhengwei Tao, Youdi Li, and Hiroshi Arakawa. ODA: Observation-driven agent for inte- grating LLMs and knowledge graphs. In Lei Ku, Andre Martins, and Vivek Srikumar (eds.), Findings of the Association for Computational Linguistics: ACL 2024, pp. 7417-7431, Bangkok, Thailand, August 2024. Association for Computational Linguistics. doi: 10. 10.18453/1/2024. ogg.oogg/..........0///// htw.://o000....iiinnsnn--daae 4427
Andings-acl.442. URL htt.:ttts:/accllae
Alon Talmor and Jonathan Berant. The web as a knowledge-base for answering complex ques- tions. In Marilyn Walker, Heng Ji, and Amanda Stent (eds.), Proceedings of the 2018 Con- ference of the North American Chapter of the Association for Computational Linguistics: Hu- man Language Technologies, Volume (Long Papers), pp. 641-651, New Orleans, Louisiana, June 2018 Association for Computational Linguistics. doi: 1/663//1/1188-059,, URL https: / antho ogy. 1ot.oo///11111150000000
13

---

Published as a conference paper at ICLR 2026
Gemini Team, Rohan Anil, Sebastian Borgeaud, Jean-Baptie Bapttstt Alayrac, Jiahui Yu, Radu Soricut, Johan Schalkwyk, Andrew M Dai, Anja Hauth, Katie Millican, et al. Gemini: a family of highly capable multimodal models. arXiv preprint arXiv:2312.11805, 2023.
Ricardo Usbeck, Xi Yan, Aleksandr Perevalov, Longquan Jiang, Julius Schulz, Angelie Kraft, Cedric Möller, Junbo Huang, Jan Reineke, Axel-Cyrille Ngonga Ngomo, et al. Qald-10 10th chal- lenge on question answering over linked data: Shifting from dbpedia wikidata as kg for kgqa. Semantic Web, 15(6):2133-200) 2024.
Keheng Wang. Feiyu Duan, Sirui Wang, Peiguang Li, Yunsen Xian, Chuantao Yin, Wenge Rong, and Zhang Xiong. Knowledge-driven cot: Exploring faithful reasoning in Ilms for knowledge- intensive question answering. arXiv preprint arXiv:2308. 012.3088.33333 13259, 2023.
Song Wang, Junhong Lin, Xiaojie Guo, Julian Shun, Jundong Li, and Yada Zhu. Reasoning of large language models over knowledge graphs with super-relations. In The Thirteenth International Conference on Learning Reprexentations, 2025, htt.httss://ppeeeeiiie wttp:/iiiieee/ffruumtte. forum?
id=rrCC299kkux
Yike Wu, Yi Huang, Nan Hu, Yuncheng Hua, Guilin Qi, Jiaoyan Chen, and Jeff Pan. Cotkr: Chain- of of-thought enhanced knowledge rewriting for complex knowledge graph question answering. In Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, pp- 3501-3520, 2024.
Wenhan Xiong, Thien Hoang, and William Yang Wang. DeepPath: A reinforcement learning method for knowledge graph reasoning. In Martha Palmer, Rebecca Hwa, and Sebastian Riedel (eds.), Proceedings of the 2017 Conference on Empirical Methods in Natural Language Process- ing, pp. 564-573, Copenhagen, Denmark, September 2017, Association for Computational Lin- guistics. doi: 10.18653/v1/D11-10000 URLthttps: / /accl antho www.py/rgg////111/10
An Yang, Baosong Yang. Binyuan Hui, Bo Zheng, Bowen Yu, Chang Zhou, Chengpeng Li, Chengyuan Li, Dayiheng Liu, Fei Huang, Guanting Dong, Haoran Wei. Huan Lin, Jialong Tang, Jialin Wang, Jian Yang, Jianhong Tu, Jianwei Zhang, Jianxin Ma, Jianxin Yang, Jin Xu, Jin- gren Zhou, Jinze Bai, Jinzheng He, Junyang Lin, Kai Dang, Keming Lu, Keqin Chen, Kexin Yang. Mei Li, Mingfeng Xue, Na Ni, Pei Zhang, Peng Wang, Ru Peng, Rui Men, Ruize Gao, Runji Lin, Shijie Wang, Shuai Bai, Sinan Tan, Tianhang Zhu, Tianhao Li, Tianyu Liu, Wen- bin Ge, Xiaodong Deng, Xiaohuan Zhou, Xingzhang Ren, Xinyu Zhang, Xipin Wei, Xuancheng Ren, Xuejing Liu, Yang Fan, Yang Yao, Yichang Zhang, Yu Wan, Yunfei Chu, Yugiong Liu, Zeyu Cui, Zhenru Zhang, Zhifang Guo, and Zhihao Fan. Qwen2 technical report, 2024. URL https:://arx:
org/ abs/////////// 2207.1067711
Xi Ye, Semih Yavuz, Kazuma Hashimoto. Yingbo Zhou, and Caiming Xiong. RNG-KBQA: Genera- tion augmented iterative ranking for knowledge base question answering. In Smaranda Muresan, Preslav Nakov, and Aline Villavicencio (eds.), Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume Long Papers). pp. 6032 6043, Dublin, Ire- land, May 2022. Association for Computational Linguistics. doi: 10. 12.18863/111/2222allloooo -laeelloooog 4177
URL https:://aca aawaaallaalllllggooooooooooo www.oog...oooooooo.oo.oo.oooo..o
Wen-tau Yih, Matthew Richardson, Chris Meek, Ming- Wei Chang, and Jina Suh. The value of se- mantic parse labeling for knowledge base question answering. In Katrin Erk and Noah A. Smith (eds.), Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), pp. 201-206, Berlin, Germany, August 2016. Association for Com- putational Linguistics. doi: 10. 10653//1//16-22000 URL. https::////.......... //ac// ac ant .gy.org/ P16-2033
Jing Zhang, Xiaokang Zhang, Jifan Yu. Jian Tang. Jie Tang, Cuiping Li, and Hong Chen. Subgraph retrieval enhanced model for multi-hop knowledge base question answering. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume I: Long Papers), pp. 5773-5784, 2022a.
Yungi Zhang, Yubo Chen, and Yongfeng Huang. Relu-net: Syntax- graph u-net for relational triple extraction. In Proceedings of the 2022 Conference on Empirical Methods in Natural Lan- guage Processing, pp. 4208 4217, 2022b.
14

---

Published as a conference paper at ICLR 2026
Zhiqiang Zhang, Liqiang Wen, and Wen Zhao. Rule-KBQA: Rule-guided reasoning for com- plex knowledge base question answering with large language models. In Owen Rambow, Leo Wanner, Marianna Apidianaki, Hend Al- Al-Khalifa, Barbara Di Eugenio, and Steven Schockaert (eds.), Proceedings of the s1 International Conference on Computational Linguisties, pp- 8399 8417, Abu Dhabi, UAE, January 2025. Association for Computational Linguistics. URL
httpss:/aaclantiooooyyoooo www.aanntoooooyyor///2222222 wttp://rgg//2000 wtt.://///....ii.....oooooo..... www.iing-mii..cmm 5627
Ruilin Zhao, Feng Zhao, Long Wang, Xianzhi Wang, and Guandong Xu. Kg-cot: Chain-of of-thhught prompting of large language models over knowledge graphs for knowledge-aware question an- swering. In Proceedings of the Thirty-Third International Joint Conference on Artificial Intel- ligence (IJCAI-24), pp. 6642-6650. International Joint Conferences on Artificial Intelligence, 2024.
Yuqi Zhu, Xiaohan Wang. Jing Chen, Shuofei Qiao, Yixin Ou, Yunzhi Yao, Shumin Deng, Hua- jun Chen, and Ningyu Zhang. Lims for knowledge graph construction and reasoning: Recent capabilities and future opportunities. World Wide Web, 27(5):58, 2024.
A PRELIMINARY
Knowledge Graphs (KGs), A knowledge graph consists a large number of relational triples: G = ((s,r,0) 8,0 E E,r E RJ. where & and R denote the set of entities and relations, respectively. A relational triple (s,r,o) represents a factual statement where the subject 8 is connected to the object through the relation
Reasoning Paths, A reasoning path in the KG a sequential chain of connected relational triples that provides coherent and interpretable pathway from a starting entity target entity, denoted as:
Cp [ 61 .... " er where each step (e;-1, Ts; e,) is valid triple in the graph G.
Problem Formulation. In this work, our goal is to formulate function f that predicts the cor- rect answers from the graph: = f(g.9) given question g and an available KG denoted by g. We assume that the entities mentioned in the question and the answers are all linked to their corresponding entities in G, consistent with previous work (Sun et al. 2019 Luo et al. 2024).
B DATASETS
WebQSP. WebQSP is a foundational KGQA benchmark designed to evaluate a model's ability to answer simple, fact-based questions that typically require retrieving single fact from the knowledge graph. The dataset provides full SPARQL queries for its questions, which are executed against Freebase.
CWQ. CWQ extends the complexity beyond WebQSP by introducing questions that require com- positional reasoning. These questions often involve multiple constraints, conjunctions, and superla- tives, necessitating multi-hop or multi-relation inference paths on the Freebase knowledge graph. The dataset is annotated with complex SPARQL queries that reflect these reasoning structures.
2WikiMultihopQA. The 2WikiMultihopQA dataset is specifically designed to assess multi-hop reasoning capabilities by integrating both structured knowledge from Wikidata and unstructured text from Wikipedia articles. A key feature of this dataset is the inclusion of structured 'evidences' - sequence of triples that explicitly outlines the reasoning path from the question's entities to the answer. This makes it particularly suitable for evaluating the faithfulness of a model's generated reasoning chains.
GrailQA. GrailQA is large-scale, high-quality dataset built on Freebase that is designed to evalu- ate the generalization capabilities of KGQA models across three distinct levels: i.i.d., compositional, and zero-shot. This structure allows for fine-gra fine-grained analysis of a model's ability handle pre- viously seen patterns (i.i.d),, new combinations seen patterns (compositional), and entirely new domains and relations (zero-shot).
QALD-10-en. QALD-10 marks a significant shift by using Wikidata as its primary knowledge source. QALD-10-en is its English subset, which contains high-quality, complex questions curated
15

---

Published as a conference paper at ICLR 2026
by domain experts to reflect real-world information needs modern, actively maintained knowl- edge graph.
Table 6: Statistics of datasets.
Dataset
Train
Test
Ans =
Ans I
5 < Ans S 9
Ans 2
10
WebQSP CWQ
2,826 27,639
1,628 3,531
51.2% 70.6%
27.4% 19.4%
8.3% 6%
12.1%
4%
C BASELINES
We compare EoG against other KG-enhanced LLM reasoning approaches. The baselines are briefly introduced as follows.
KD-COT. KD-COT (Wang al. 2023) integrates knowledge distillation with chain-of-thought (CoT) reasoning. This multi-stage framework guides the reasoning process by interacting with ex- ternal knowledge, thereby enhancing model efficiency and reducing computational costs. In general, this approach enables large language models to perform reliable reasoning on knowledge-intensive KBQA tasks. EWEKK-QA The core contribution of EWEK-QA (Dehghan et al., (024) lies in its efficient integration of two external knowledge sources: web text and knowledge graphs. Specif- ically, it employs two modules: an adaptive web retriever that dynamically extracts text snippets, and efficient knowledge graph retriever (TOG-E). This approach achieves higher accuracy than baseline models on various QA tasks while being faster. ToG. ToG (Sun et al. 2023) introduces a key innovation by framing the LLM as agent that interacts with the knowledge graph for collab- orative reasoning. This approach moves beyond simply translating questions into queries, instead enabling the model to actively conduct beam search on the KG to progressively explore relevant entities and relations. In general. This approach significantly enhances the reasoning capabilities of smaller models on complex knowledge-based tasks. EMiQA. EffiQA (Dong et al. (225) aims to address the performance-efficieee graphs. Its core contribution novel "LL.M-s as-planne,, small-model-as -s-exccutorr" framework that offloads graph traversal and semantic pruning to compact plugin model. RoG. RoG (Luo et al.) 2024 is grounded on the principle that knowledge graph relations constitute faithful reasoning paths. Through fine-tuning, the LLM is guided to generate faithful reasoning plans presented as relation paths that can be verified by the KG. These relation paths are then used to retrieve specific, factual reasoning path instances from the KG. Finally, the actual retrieved paths are used for final answer reasoning. This approach achieves optimal performance on most KGQA benchmarks while produc- ing faithful and interpretable reasoning results. GNN-RAG. GNN-RAG (Mavromatis & Karypis, 2023) enhances KBQA by combining GNN-based structural reasoning with LLM- language understanding. The GNN infers over a subgraph to find answer candidates and their reasoning paths, which then serve as contextual evidence for the LLM. This approach achieves state-of-the-al results on benchmarks like WebQSP and CWQ, demonstrating strong performance on complex multi-entity and multi-hop questions.
trade-off in integrating large language models with knowledge
DoG (Decoding on Graphs), DoG et al. 2025) proposes the concept of "well-formed chain" to constrain the LLM's generation process to sequences of valid, connected triples from the knowledge graph. It implements this by using a Trie data structure, built from the local KG, to dynamically mask the vocabulary at each decoding step, ensuring all generated reasoning steps are grounded.
ODA (Observation-Driven Agent). ODA (Sun et al.) (024) frames KGQA as an autonomous agent task operating in an "observation, action, and reflection" cycle. The LLM acts as a high-level planner that decides on subsequent actions based on its current view of the graph, allowing dynamically explore the KG to find the answer.
KG-Agent. KG-Agent (Jiang et al. 2025) uses a ""gre-box" approach, fine-tuning a smaller LLM to be an expert "tool user" for KG interactions. The agent learns to generate executable program composed of predefined tool calls for KG extraction and logic operations, trained on a large-scale dataset synthesized from existing logical forms. GCR. GCR (Luo et al., 2025) achieves graph- constrained reasoning by guiding LLM decoding with KG structures. It first encodes KG reasoning paths into KG-Trie index, then employs a lightweight, KG-specialized L.M for decoding during
16

---

Published as a conference paper at ICLR 2026
inference. This approach ensures faithful reasoning, achieves oftte-of-the-ar performance mul- tiple KGQA benchmarks, and generalizes to unseen knowledge graphs without additional training.
D EXPERIMENTS SETUPS
To ascertain the general applicability of our approach, we apply EoG to two open-source LLMs, Qwen2.5-7B-Instrrus (Yang al. 2024) and Llama-3.1-8B-Instrue (Dubey et al., 2024). For fine-tuning, we use Gemini-2.544 Hlass to generate long chain-of-thought datasets. For reinforcement learning, implement the GRPO method using verl.
For the fine-tuning phase, we typically train for three epochs on single node equipped with 8 H100 GPUs. We employ micro-batch size of 16 and a learning rate of le-5, utilizing cosine annealing learning rate scheduler. For all experiments, model checkpoints are saved every 100 steps. Taking CWQ as an example, the model was trained for total of 576 steps, and the besf-perno checkpoint was selected for subsequent training stages.
For GRPO training, we set the policy LLM learning rate to 5e-6 and sample responses per prompt, following the GRPO implementation in Verl. For efficient LLM rollouts, we adopt vLLM with a tensor parallel size of 2 and GPU memory utilization ratio of 0.6. The rollout sampling uses a temperature of 1.0 and a top-p value of 1.0.
Training performed on a single node with H100 GPUs. We use a total batch size of 512, with a mini-batch size of 256 and micro-batch size of 64. The maximum sequence length is set to 15000 tokens, with a maximum response length of 10000, To optimize GPU memory usage, we enable gradient checkpointing and use Fully Sharded Data Parallel (FSDP) with CPU offloading.
For all experiments, model checkpoints are saved every 15 steps. In cases where training diverges, evaluate at the most recent stable checkpoint according to the training reward curve; otherwise, the final checkpoint is used for evaluation. Finally, we compute rewards using Fl score and path- refined reward.
E IMPLEMENTATION DETAILS OF COMMERCIAL MODEL EVALUATION
This section elaborates the methodology for evaluating the KBQA datasets using commercial large language models. As shown in the Figure 7 the prompt used in our evaluation code-as as de- tailed in Figure 10 for the RL training phase-it is identical the one shown here, ensuring fairness and reproducibility. The Figure below displays a sample output obtained by evaluating the CWQ dataset with multiple large language models, including GPT-5, Gemini-2.55-Flahh and Gemini-2.5- Pro. We explicitly confirm that the model denoted as "GPT-5" in our experiments refers to the of- ficially released GPT-5 model accessed via the OpenAl API. To remove any ambiguity, the exact model checkpoint used in our evaluation is gpt-5-2025-08-07.
F TEMPLATES AND PROMPTS
In this section, we illustrate all the templates and prompts used in the experiments.
Long CoT Construction Prompt. The template for constructing the Long CoT dataset used for fine-tuning is shown in Figure which prompts large language models to generate Long CoT rea- soning on structured graphs and filters reasoning processes that are both structurally and factually correct.
GRPO Prompt. To train the FoG, we carefully design the prompt to prompting language models, which is shown in Figure I0 This template is designed to guide the language model to autonomously explore the knowledge graph by generating and executing structured queries, while ensuring its rea- soning process adheres to a strict output format for precise reward calculation during reinforcement learning.
Reasoning Scores Prompt. As shown in Figure II the
evaluation criteria used to score the model's 's reasoning processes are detailed below,with each dimension scored on a scale from O (lowest) 10 (highest).
17

---

Published as a conference paper at ICLR 2026
6el -P niC bpst, expe,ft soLeey mus, warterrddd, st
willope 1k- ji
acFaodd, samce "uatt-2--faa" adtnus verkur sortbr
aifadde lact Lodk)
repainn georgs groupe praege
opmai apblelt quarias legls cettle, grapks
bettoo give dunpsheppn snitled) (al unee praapi)
"enee" uttryptem prompt, "aae"
topaaas and www.llee-.u...mmpitiiei....
2 133
aust write tarumiti' the cledade the file trem called wibl locky
wereiieeeeeeee den, loe)
Singh-nst prermang anczed
writing traggre buich ttrobeld crrrddee"""
pereen kip quarianetetfy
oud momomppeeeetrr...cc
vidh ott.oppetttaaa (il, "t"eaddd"""""" (SF4")
conrieaa lestan)
prltui gracmbtg troLLgnntee guartiee Cescernee trrade jelfaass weittrobble jettbesck_ttr (oor")
dasa Juddche
Ma,
sumeiee Jola santiie JeH
with Thradfsdtarcceeteeee worker west eac, warkent excoen Ex data, 10k qeaikes,ien
ditrr iedatoo weppoettnntttttitrrrra seartiaa qpodiiat
mene, owert mm
vib aileaae Jack:
quertema pvent
peas)"oCoodi eCodd soti, quartans botil guaatons)) owen. namsuncommt] (pra_ovest"
Figure 7: The code used to prompt LLMs for evaluating performance on KBQA tasks.
Relationship Extraction Prompt. Following DoG, we prompt LLM, Gemma-2-9b-it to extract all the relation triplets using in-context learning. The prompt detailed in Figure [2] Finally, all the extracted triplets from different passages are combined into the final graph, with ranking filtering applied to the triplets.
G COMPLETE CASE STUDIES: REASONING PATHS AND MODEL OUTPUTS
In this section, present two complete case studies further illustrate the reasoning behavior of EoG. Figure 13 provides the full version of the case shown in the main text, where certain reasoning steps were omitted due to space constraints. Figure 14 presents another representative example involving a superlative reasoning pattern for further analysis.
H THE USE OF LARGE LANGUAGE MODELS
We acknowledge the use a large language model to assist with the editing and refining of our manuscript. The tool primarily used for language polishing, including improving grammar, syntax, and readability, and did not contribute to the core scientific ideas, methods, or results pre- sented in this paper.
18

---

Published as a conference paper at ICLR 2026
Question:Lon Seal is the mascor for the teem that lost won the World Sence whenrAAnmerri"200 W World Series"]
GPT-5
<think-1] Idemiify the begin, antity: Lou mn2) Find team associated with Los Seal in the graphiin Trrppe: ( San Francisco Ginnts' ''spects-ports leam.icam mascoet, LLoo Seall] japlles Lou Seal the meseet of th San Franisco Glants as) Determing whar that seam last "2114 World Scries"") intieates a World Series championalig in 2014 Suppuring costent The Giinns are petiiiaant is the 2010, 2012, and 2014 MLB acasens, convistent with tiles 20 io, 2012, and 2014 The lotout championship enlyy explicity present is 122014 World Servelf (od) Theerforr the heam Scal
wen the World Serice using graph rehiionein in TTipl: ["San Francisco Gantest 1 "'pprts spors, demnehanpioniiie
World Series the 12014 World Scried othiik Saaaeooooa 22014 World Stried" paanswrs
Gemini-Z.S- 2.5-Flash
<think-lul). **Ilentily the Ce The user wants to know the your the icem, for which l'Lou Scal!" is the moanr,, led won the World
Scries win2. "SSaat with the begin catity so The stating poin is L'Lus Siid FFFind the icam monciated with L"Lu Seall" ** I will search the knowlodge graph for eiples that have "I Smilf the object, find out which term is mussor for Seal
find the tripl: D'Son
Francisco Grante" ("aperispports I'rnccisco Grants" aann "*iind champiosships the
("Len Seal"" in This triple sells
for (San
l'ancisco Giams"": I need to find when they won the World Series will look for riples where "Son Francicoo Garts" is the sibject and the relatio about clampionslips in I find the tpple: Ta'San Franescoo Glansot, spppacts-pporss leom.chanppionslpps.. (2004 World Series
that
Francisco Giams",,
This
ctple indicates that the "Snn Francisco Giansi wan the '20014 World Series inias. **Deemminee the most recent wit. The question asks for the "lasi" lime they won. The gouph also alow their pattaciusioo other scasoes like [-2010 Majer Leggue Baschall scmouss" V'rim partcipant") (San Frncisco Gaete"] and 2-2012 Major
Htreballl sesson" I "iime event portcipane"" ("ann Prancisco champonnhipe selation specifically points
Giame! Howevr, 'yprts sports
only championship
World Seneel", Comparing the yeans, 2014 the most recent championship mentioned
provoded graph **oonsmnct Final
Anscert* The question asks (whhnn" Basodd on the trplle TS"an Francisco Giantel" "spors sports seam championshipe"" " (22014 World Scries"T. TI, the anwerr is 1/214 World Scriest", This entry exies the w---thinl-----nnee (a1" World Series" "pa-ionwwers"
Gemini-Z.5 2.5-PPo
<think:-"nhhe user asking find the year when team, which Lou is mescot, last was World Senies Willlere's step step reasoningtnn. **Iderniy the semm zosocisted with (Lo Seall-*-in strt with the 'begin enity' LL Seall" in look for triles involving ('Lou Seall. The iiple (P'S Francisco Glanst (pppecispprrss teamaeam mascot", Loo Seall I directly tells me that "Lou Seal!"
is the mascot for the ('Snn Francisco Glant t Jmin.. **Find the Wordd Series championships wen by Saan Pranciso Giantste Now that have the toam "Sun Fancisco Guants", 1 seach fe siplos rolatal to its dhampionsips, sputifically World Serie-ln The tiple [''Snn
Fruncisco Guaut"", ("sporausprts oller ponental World Saries World Scrialf
champinndippe" :2201 World Scries"T indicate
"San Francisco Giants"
12004
While theme niples like (12010 Major cogus Raschall sccoon""
'"imte event parncipant" ('San Prancisco Gl 112012 Major Lengue Baseball season" I l'tmme poricpponticpaan"" Gianss"] I. these only indicate participation, not champoonship win. The only explicit champtonship listed for V'San Franiscoo Ganns" in
Francisco
graph is (22014 Wodld Sesiesi land. ""Detemiin the "last" World Series "in SSince (2014 World Scries" the only championdiip explicitty listed for "San Francisco Gians"" in the provided graph, it consddredd the ""las"" one according to the given information. wind.
** Amooerr the quosiio ? ? fin The qualiu saks "ubeetf" The antlly "2014 World Sance
eveut that occuraal in spociiiic 120014 World Scries' cailty According most appropritt anrity
the graph. Thouffrr, 123014 World Scries" qucstion, discatly refors the evail that took placs in that you TanTerrenn, the leam (SSn Francisso Giante"", and they lad wan 122014 World Series" acconding to the graph. The answer to "Whenff is the event ineld, "2014 World Seriosi"/norhiin "aothinio waaamiaaaaaameerraaaaa "nn" 2214 World Seriesi "Jas/asswer""
The ""2024" jself present standalone
rules, the M'hhes"
answor
anlty explicily present
Figure 8: An example of prompting LLMSs on CWQ.
I DETAILED TRAINING COMPUTATIONAL COST AND EFFICIENCY ANALYSIS
In this section, we analyze detailed training compute and efficiency of EoG. The SFT phase of our framework prioritizes data efficiency by focusing exclusively on the reasoning over structured graphs. In contrast to the 1.5M instances requirements for SFT in general models like DeepSeek- V3, adopt a highly focused strategy. Our curated SFT datasets CW eWQ contains 3,537 instances, and WebQSP SET contains 2,344 instances. This task-specificity allows us efficiently converge the model to sota for graph reasoning tasks with less data, reducing demands on large-scale, general instructional data. For the RL phase, we optimized training through- put using the Verl framework on 8x H100 GPUs. Key parameters were configured as follows: a train batch size of 256, global batch size of 128, and a micro batch size of 3. This configuration ensured high training throughput. As shown in Table 7 the resource expenditure to achieve optimal perfor- mance on 8x H100 GPUs was notably low: the CWQ dataset required 120 steps and 509.6 GPU hours, and the WebQSP dataset required 36 steps and 119.2 GPU hours.
small and precise; for instance,
Considering the trade-off between training cost and performance gain, we believe that the EoG framework holds significant practical applicability. Through efficient GRPO implementation and a very short RL training cycle. the EoG framework maintains affordably low computational budget. This minimal investment yields a statistically significant performance boost, primarily by enhancing the model's 's exploratory capacity over Knowledge Graphs. Consequently, the EoG framework not only achieves sfate-of-the-ae performance on graph reasoning tasks but also demonstrates superior practicality, cost-effectiveeess, and deployability.
19

---

Published as a conference paper at ICLR 2026
Long CoT Construction Prompt
You are a helptul ossisiant that generates SFT samples for qustaoo-anrwerin task. Your task is to create ligh-quality training step-hy-sn rosseiing questions hased knowledge grogh information.
esamples that
Be Input Fornat:
You will receive:
questiom: natural lanuagg question
answer. The correct answer(s) to the question
begin enilty: The staringg endit in the knowledge graph that can be used as reference point
grophi: Kaowledge graphi information the triplss (subject, objeet)
as Qutput Requirements:
You must generate response that includos:
1. "Ressening Chain * (-think> section):
Step-by -tep- logical reasoning process
Analysis the emiities relationchiiss starting begin, enrity Identification
and relevans informttio
Logical cedaction keading the answer
Ulke of graph eniitics and rolations rensoning
begin_cniity seach
**FFnal Answer"* (Canswer> sccrions):
Clear, cuncise
the question
provided
The answer MUST one or more encties that exist the pruvided graph
Can be single catty. list enities, or descripiiee answer approprate explicitty
IMPORTANT:
the triples
Ae Response Fommat:
Your use the following XMI XMI-like llike
<think>
(Your by step reasoning process here. De thorough and logical, showing how you analy the question and use the graph iooomaticn asswer.]
<answer>
final matching provied
be entiries graphi enclosed square brikets]] ]
<tanswer>-
de Guidelines:
Always the -think section your reasuning
Use the begin, encity as your starting point for reasoning
Use information from the provided graph your reasening
about which
and relations you're considering
Show logical connections between difforent pieces of insfomatioon
End with a clear Sanswer- that directly addresees the question
Ensure
matches the provided cerrect
CRITICAAL: Your final
only
exis provided graph triplee
Use clear. natural langunge that demomeentes good reasoming skills
IMPORTANT: The final answer in the sanswer ere section must be enclesed square bracketts
Exanpic
<think>>
First, I Lamoyyi the question to understand what is being asked...
the begin. entity [begin emity] examine yruph.. Looking the graph, identiff relecant entities [enity I] [eniity]]..
4. exummine the relatiunebips between these entities, starting from the begin, entiyy..
Based on this amilysis, I can determine that... Therefore, answer is... <2think>
[Your
cutitiss from graphs]
<inwwer>
Show logical steps how at your unswer using the provided graph information, starting from the begin_eniity, Your final answer must only contain entries that are explicitl present in the graph criple..
quality your reasoning
Figure 9: The template for constructing Long COT Supervised Fine-tuning datasets.
J CLOSEE-SOUREE LLM EVALUATION REPRODUCIBILITY DETAILS
To ensure the reproducibility of our results, we detail the experimental setup involving the closed- source LLM. All inference experiments were conducted using the closed-source LLM, accessed via an Openall-ompatible API interface to maintain a consistent testing environment. To adapt the Knowledge Graph (KG) data for the text-based model, we linearized the input subgraphs into
20

---

Published as a conference paper at ICLR 2026
GRPO Prompt
SYSTEM PROMPT- "ou are helpful assistant that answers questions hased on knowledge graphs. First, reuson through the problem inside <think> </think>> lugs. Here you can planning. memoey, check for mistakes reflect, prune the entities and relations.
When confident, oclput the linal answer inside <answer? and slanswer> tags. Your answer must stricily follow the rules
provided by the user.
## Input Format:
You will receive:
question: natural language question that needs answered
begin_eene entity: The startigg eniily in the knowledge graph that can be used reference point
graph: Knowledge graph information in the form triples (subject, relation, object)
## Output Requirements:
must genente response includes:
"Ressoning Chain** (-think> section):
Step-by-step logical reasoning process
Analysis of the question and relevant gruph information
Identification of key entities and relationships, starting from the begin enlity
Show how you traverse from the begin entity reach the
Use of graph catilies and relations in your reasoning
**Final Answer** (sanswer"> section):
Clear, concise answer to the question
Must the provided correct answer
The answer MUST be one more entibies that exist in the provided graph
CRITICAL: Only use entities that are explicitly present in the gruph triples
#* Guidelines:
Always start with <think> scction show your reasoning
Use the begin entity your starting point for reasoning
Be explicit about which entities and relations you're considering
Show logical connections between different pieces of information
only contains entities that exist the provided gruph triples Use clear, natural language that demoustrates good reasoning skills""
Ensure your
USER PROMPT = "" Answer the given question based on the knowledge graph. You must first conduct reasoning step by step, and put your final answer inside <answer> and </answer>.
Rules:
When you huve the final answer, you can directly provide the answer inside Sanswer>-s/nwwee", without detuiled illustrations. For example, <answer> ('Washington, D.C.") <ansser>
2. If the knowledge graph information insufficient to answer the question, you may use your own knowledge to supplement the reasoning process.
present them list format using square brackets []. For example, <answer="" "answer=""Bijitee "Beijing", "Washington DC" "a"ns//nwwer>.
there multiple possible
Recause questions usually have multiple answers, you should consider possible answers and provide format.
multiple starting entities are provided, you should unalyze each ane systematically, such as Consider how different starting points might lead different answers ,combine insights from starting entities answers starting cutitics are selated, explore their connections the knowledge graph.
You must use this format:
<thinks..<tthinks
canswers,. 5//nsweer
Question: [question]
Knowledge Graph: Jeraph text)
Figure 10: The template for prompting LLMs to explore during training EoG
JSON-formatted lists of triples [(h,r, (),.... which were concatenated with the natural language question and the topic entity.
We employed prompting strategy that integrates Chain-of-Thoughe (CoT) reasoning with strict for- mat constraints. The system prompt explicitly instructs the model to separate its internal reasoning process from the final prediction by enclosing the reasoning steps within < think tags and the final answer within < answer > tags.
Regarding inference hyperparameters, we prioritized faithfulness to the provided graph context over generation diversity. Consequently, we set the sampling temperature to 0.2. This specific setting critical for minimizing hallucinations and ensuring the model grounds its answers strictly in the
21

---

Published as a conference paper at ICLR 2026
Comprchensivenees.
Correctness
'Wleite the thinking consides all Inportast agects and
'weete the nessriing and ersker are liginlly and fiealll
dancaghf.
conrect
"*Soarig (3-1ity
"Soting (0-18)
Exhardy
relonar, and crossautiona
Jayús.
Xoully
-8-4h Liven moet bey aqpeet dieatly and thoughttdlyy only miner artieues.
-6-7 Ponislyy crmstt
flws inoormmnnio prosent
-6 Covas some impertatt cspats, but lacks deg ovellooks nutable anda.
+4.5 Nationkke iooeett remosiig Satual erees thooughiot.
- 1-3: Lugady noamee makeding, or tlopeal.
-4-3 Tractes en fow relevent points, but ovenif ladis aubsoncce or
Dr Sratrcyy wrnng or snesomkodd
complernas
Spanc sbalew traatment of the kapkc misees capsoo.
conperheee complesity apuericaal
Relevance
Depth
'eeee dlerssssing and stower are highle odevast and hebpfl to the quodice..
hatteeer the fiikkigg onn explac odexasi end indayfi koonledge leyoad the tipla"
""ocria Gunde (9- 10x
** "Sonin Grida (0- liy:
10 Fully freeod oe quetion righly wireart and hrigft
in is aétiior so fieding no can snsoer riples, the repore can replon and presor. srab-lay cood, divese kaowledae ausciaee with the szawer catils, each timattes atritaans othe molos or rebard sconndary evares This provièes grea richsco explareceesal importan aspects beyond care tiples, with only 6-7 Cas find and
-8 9. Meals os pozt. muse digccssicna but evcaal ascid,
Gounally neleaan, her referies dienetoncer er helptul part.
Linitd scivessee
the soponee ls ofTopic ushiciffll. related the cucaton et largely snhelfful.
fox unsersinning
adiitionl know lodgo reliee
the catity. the becuth is insied.
4-4 The mequsse is netriceed to the most exparfical infvrroticn diveelly lnekrd to the cone enrry or eun only porrie atstrood trewnldyy is deglt dincenso (ea, only finding coe congraion bui olhe isfa).
boc The srevers cretreed deyth becigroond knowledge.
core tmplor and prwvider sdeitional, in-
ir fasle aind cone tmplce or prosente mommiyff inoxtedge
all-"
Factuality
Exploration
resoting seowerare base oocornt verifilee foos""
"ahether niiting procss explare eoough entiies rebuiirshig geple"
"*Scarig
vealiable.
"Soning Gual:
--4 Mouly
Petual
It Denosemas sipty eycomate and to-depth underearing leasing encial informtiion pergostive unoudee
Caniin sase fecual inccuncio unvillie dlains.
44-5: Severa aggiiiive tatral cmm.
-h-y Presere a ciearand theughtts asalyst, with only miner omneonee
1-2: Modly tilec molnaing
-b-7 Addrasss releaat pertte bet acks deptt ar overladis agpriiian arca.
Complenly fhikkted or fictually wrong shroughos,"
Touches os few poitt bet gocerily inconylin and lacks desal.
1-3 The respaae musimal seperficis, and miscs most key clenest. topu
sequese complesty spprticto
Figure 11:
The template for prompting GPT-4o-mini to score the reasoning process
retrieved triples. Additionally, to investigate the sensitivity of closed-source models to generation parameters, we systematically evaluated the impact of varying temperature settings on performance, as presented in Table A timeout of 120 seconds was enforced to accommodate the extended generation length required for step-by-step reasoning. Finally, post-processing involved extracting the content between the answer tags using regular expressions and parsing it as a JSON list to calculate Hit@1 and F1 metrics against the ground truth.
22

---

Published as a conference paper at ICLR 2026
Prompi for relation extraction on 2iiiimulihop.
Givec dhe decureeti and somz coliice villir the cecureets, cxtract all Bz relzzin tripks betweee jain of loz collics.
Decusreal
Tike Xawery Zatnnsii
Nawer dil (Jom 22
Wansw) a
preveael Natioal School He fottres
Madoowaaa,
Polus noal "Tty leppil Tymrand Zutevoii his wife Marts Simvlado chilfers soe Pulreski (bore 3083) duigher
Zutavoka (bor 2009).
Eutiio
Xawery Zalon 2ut222 Doceriter 1971 Wase Falllallllll dieccsiul Poois Filn Acddons Milge--oilggaa BrendkeAading Zahoesitalanne Wastendi0ealleeee MaalerokzaWWeeee add aoppod rodan Sandodorrst ZalrnicrnaM00 mingrn Dabonda
Kawery Paloade
Peteofnirawryy Patrwoki (aae ofhien Deoeer 1971 wxrwway Palaweci Iccepationn diveteraNsarry 2rinwoki)
bint WorewwWaarr jonsrryy Welandi-Waare lacator holes Zatanoki rducated Pholess Film Acatenyishuiii file Arsdamy
coancy PolssduPcisk Film Saalary laokkpanes lostion Leaiahhiia Fils Acedome locasin Lolzalodi ccastryy Polasiaiiiiaa Brandh child "awaryy Zaboddiinttigeean lioands courtry hisreshtapeenn thand secepaton I'in deceresttapent Linand, sqeaas Ardiva Zulawokirelonkas uqj Zizooki dHM Nawery Zaboak katallonn Zakonki ooapatinn File direcssntoloooo Zeleoki) spaase Milgoratta Broankk Wijee palizo-taaa suther Doeen caskrwerrowwer poldo--tada deeder Andra Zutookk poldio macc (8hn adiunt Astmo dalorederant pebda- nukki prodzeer) Andron Zelonsitaalion ven poldkccaks pablication dase 2000/a Zukonok country [hlnndaaawveryy Zalanids cisid lauza Pedaooksinka ]adawokk] (othor) (nnoorry PateodeleNnooyy
specse Morta
Docament 2
Tilee The of Dr. Fa Masche
The Reteen Lte th Mandita a 1930 Amenicin pro- prde fitn direced by Rowraad V. Les. it the accend of thee fime sturing Wamnrr Cland sn the fandia Marcho, who yourss from oppareer death is the presious file." The Mysterion Tv. Pa Marcha"l 1929), to seek revenge en flose be holds respossille has wife and child.
The of Dr. MasdrzialSaaaalae BaisisPre HulyynoddfBonlaal LazelWane O'azataaas Maachels The Masterios Ma
Relation tigles.
The Reteen of Li. tha Mandira country Limmedd Staeelathe Ieeam of I's Mancha direearr Llnwland v. Ledetthe Reture of Lnr. the Manciaa mnvomeent tre-Cede inllynoscia the fatton of Dr. ze Manchu (sabikattice dass 1MtPla Nutum of Dr. hu Manchu cus meniall War cntaniian Vergnance of Marcha cas member (Wirner Oladdothh Mysteious Fi Mancha (oss menthe [Wamer Oles Mystriass De Tu Mindhu jeeenry United Statelalle Mosictios Dr. Manchai pablication dase) 1923
Documenn
Nov, Voyaggr
Now, Voyage isa 1942 Asseican drama fin saning Bene Desis, Paul Feseei and Clasde Rais, and liested living Rappor The screeplaa by Ciscy Robison is based the 1961 sovel of the samz same Olive Higgra Peeatt. Poeaty bortead her sile from the Walt Whitmon poerz" The Uniclé Wart". which reds iu eniioey. 2007? Now. Nopager was silendd for prosrvation in Uniod States National Filn Regirry
Library Cf being"
attually biariiddyy or southmiially apgrticast Thh filn makk rumber 13 os" ATTY tot sincru crite Steves Jay Schnside scpacita Ell continses be remaabooeed ast only sar powes, but also fzz cootiveal cresenske engindonud steyytez.
Prelard: be the toy line sores in Americnn
Unitiir:
"INiZelleridd Statoiatiara (fin and /eaieise//alleti Dacniiataal Haarraaeiaaaa Rarasttring Happeral besy Hebemaera 1941an Verage
dffeitivvve H Riggin Procyaal. Fleccer Procty Watt W Whimorrzo07 whone HopageriWNatons Film Regleryaa/heery of Corrgessin LightinAmeiin Film tsast 120 Years... .. 100 Pasasro ubteves Jay Schzesker
Belatics tipleo:
Vioaggr | Unitd SuteraNow, Voysaer diectur livin Ruperallow, Voysgr lazur Doare adersicc/raNoo, Voysaet
RuissinNoe, Voy Vayager
Vayager
Voragrr
write RibinsoniaNos, Mosagel oataid Now, Voyeger (soveliaNios, Vosage (wnel)) puliiation date istin, Veyager casvell nathori Gitre Logara Pmatyaaonn, Vogager mooerved by Nutoral ritn Regary/aNee, Yars... 100 PosiersiaNNee, Voyager (axilyeed by Strven Sehtede Fil Regiary mnletiised by |Lbrary Congies
careed AFT
Tecemeett
(atle]
(sansinc)
Fatiie:: [enition]
Relation vipleo:
Figure 12: The template for prompting LLMs to extract relationship on 2WikiMulliHopQA
K HYPERPARAMETERS AND CONFIGURATION FOR GRPO
In this section, we present the configuration details of the GRPO-based RL training. The training
was conducted on single node equipped with eight NVIDIA H100 GPUs using the Verl framework.
We initialized the policy from the SFT-trained model checkpoint. To optimize resource utilization waaallegraddiet.cheeppooe
and training efficiency, we enabled Gradient Checkpointing and configured FSDP with both parameter and optimizer offloading (param offload=True, opti- mizer offload-True).
23

---

Published as a conference paper at ICLR 2026
Question Find country the ISO mimber of 766 thet that imports from lipan,
some of the country countryAnwwerr"""" "Sulaar Ours
<thiate"), **aallse dhe Questinn ** The cuoiie als for the country fus impoes from lipan and las an (50 number of 736..i
2. "Uddnnly key Estices and Relaiimm-" * "MAaaas" (bean cuikyfa *I ""arpott foon" (ydassap 1150 uuiter of 7397 canibase of the trpa ouurtyjn "ooutyy" egpe the vegi ornyinin
3. "*Sont fnm Japan and find impert cistimeppcnnn
for tipice wher "Ippnn is the olject ofan "imports fuumi' releiion the artjot of mmsres is *I (r0d0ppepp location impors and eepers impettl farnt Japan]] This merrs (ekgrepp impees fuo lapen wa
an t'oppntdd soi releomn (wtrch
"*Udeniity courty ssscatte 'n,66eerp" sii "Laodd to what 'nddpppppp repesietts Look bistes whaz in Oi0igepp eutject
oegion plocre imponed, "1ippaal
netipppp
impont
inporizsport
fucation lapanin
[Papanl
rajinn place rsportad [0 ['apart
Tocation inpors, pagionplaco.
pop Jagae]] This
from
5. ""Look 150 number infomation"
spacifes 7710 number "30" need fnd
that has this ISO numberia *1 dircct linknng IS0 number to country
scve the grph the 1S0 number night te implicti
contoning (180 ramberr simior stribatccin + do
Thes
lisked thnogh another enliyy not diaetly vioile on V150 numberr
6. ""Re-vvalat the pubkerss with lee gives grapi t The grgli does conrais explca (I5O matiber" infortation for costrres. This is conunce
isee with knowledge gropls where information night be implted requre inferene estoraal lodge However, the requirss using "oaly" the prosited proph inin
7. "PPecss on the "Trppnss from Jagan? part and the given onssert The cornet anower SSdker I need to find a path that leads "setar bosed or impocing foom lapen sic.
& "Be-cannae the "cpptontiio
"Ta Dedgropp "boaioon and expottiinoooted foont 'Iaparl' mean "a.044ggrep' irports from Juasin * "Sudar, rocelion.satiiiil placs impontd foor, in bidgrepl meus Sodai imports Boon in (iigg und
o. **Cosrect the doo. Japen export to in Maghy and "illlpk 'oa "n (idyyepp import for Japen. So, 'i.64igpoy' a countyy that "Sadas irporss from in iityeap. This nesss Sacien impors from a countr that imports from Jepon. This is convolized
impors from leportn pubi'e's
sngh and the conect ussver beins Sadari thes night as implizi undestarding miliit bisle that line Salan dineely Aipa via tade. Howeva, withort as explest numbel" relatos, directl use ("IS of is
*SSimpler
implica. Gives lhe contrinst to only esttics
Suka mide, grown fomilei thrugh "Coollisie based on evolable inforstion laget stows root diseet path "Sudar"
onlty 'm.4iirrppp "apas mn.6lpprup
inglis dar property
qucation explicily linked
providad guaph. Tharefor, (Sudar)
150 sumber lfele
through (ilpppp The expiciily
lead Sudan-iia
edatierehip cading Sadan from
from lapon The gooh from m4000grup and Dippeap import from 'apunn This vatafios the "'imper foom lspant part The 190 sumber is
ado for the with 716
showe Saian
fiter tha, of expliiily in the graph, would he dincelly appial Smoet its asame sege snawer Sucarl intended enly that fulfib impuet conditin iii Therefie, country impars from Aquas Stakan weltiinke
Question Fand the country with the 1SO mumber of 736 tha that imsorts from Japun. what is the sunc of the country "Suwar.""udaa" "Reawaing Pulls: vaaaonin Puti/ollpun basecchaiiies geoamphic skopec Staliggn Childer's Foundaton > osgatization aeganizatinn poggnipiiipppiccc....... Scope > Lnited States Aueriain Aiswel inlineed State of Ameiicne
GCR
Beasoning Paticallipnn lostion strisied region places inperte fiom DiDiyggl lnctioninposs and expars inportd foom Temmoraee Asswer's of
Recommn Fath:allqua or locatio country ferm of goverman Padiammnnay systen it jovmment form of gnvencttt.oottii Turabinkk
Arswer influraliisi
Ressoung Pall/iallpa i kostto larausgs sooken English Largugee lanra
aocken to Sadaciss
Answey isooaaitt Rezsoning aalpa stattio regisuplasss rxpoial 1o in m.Dooill locution.inpsts and exports expanel Kinivains AscaeraaKaisiiie
Recoeing iratiinlquu of clympcc pariciuatin country ulympio parikipated in de 1936 Summer Clympio or
olynriocobsrpii jamossaniiippaingg constrics Canadalzal Answer CCarabiik
Reaseing Palhiinllpan striiis plpiosplaces insoree from i miglpppp lncstionninports and expurs imported fiom Caradkeed Asswes iuCasadira
Rosserin bym erprrstioon ceperiitionnnnnnnnn..n fundervrrrrizaiine
Trade Opprrizatoon regesinetio reganizanoon frundars
Figure 13: Comparison of reasoning pathways hetween EoG and GCR on Case 1.
For data and batch settings, the total training batch size (train batch size) was set to 256, with maximum prompt and response lengths capped at 15, 000 and 10, 000 tokens, respectively. The Actor policy optimization used a learning rate of 4 x 10 10-6 6 and was updated for ppo_epochs internal epochs per rollout collection. We disabled the KL loss term and set the gradient clip to 1.0.
The Rollout phase is crucial for model exploration. Rollouts were executed using the vllm engine with a configuration of N 6 samples per prompt (rollout.n), sampling temperature of 1.0, and top p = 1.0 to encourage diversity. The reward signal was sourced from the external script, and KL- based regularization was explicitly disabled. Furthermore, an overlong buffer penalty was enabled, penalizing responses exceeding 3, 000 tokens. The entire training process ran for 6 total epochs. Notably, achieving optimal performance on the WebQSP dataset required only 36 steps and 119.2 GPU hours, demonstrating the high efficiency of our framework. By detailing the parameter settings of the GRPO phase, we ensured the reproducibility of our EoG model.
L ANALYSIS OF REWARD FUNCTION COMPLEXITY
In this section, we investigate the impact of incorporating a more complex, graph-strructure-riinte reward Gunc Edit Distance (GED) experimental performance. As indicated in the table, the utilization of GED failed to enhance the model's 's performance on the test set; on the contrary, it led to performance decline. We attribute this phenomenon to two primary factors. First, since we explicitly constrained the reasoning structure during Supervised Fine-Tuning (SFT), our original path-based reward function proved to be simple but effective within this context. Second,
24

---

Published as a conference paper at ICLR 2026
Question What sones does Colorado River thouuh Mountain Time Zene?Amseeri]" "aaoori"""lorraaa"" "Nevada", "Artrona"] Ours
<thisk=1. *Annlyye the Question:** The question asks for states that the Colondo River runs through, spocifically those in Time
"Ideatify Key Fatifics:*> The key entities are "Colondo River" and "Mountzin Time Zone".
"FFind States the Colorado River Runs Through;"*
look for triles invalving "Colorado Rive! and "partially contained by" similar relationship with state. "location
purtially containedby' 'Arizons] indicates Colorado River through [Colorado River, loocatio.location, peatiio.purtiillly cuntainedby, 'Colondoo) indicates Colorado River runs through Colorado.
[Novadd", Tocation location purtially contains', 'Culoralo RiverT indicates the Colundo River runs through Nevals. runs through
T'ubh, location. purtially contains,
River]
So, the states the Culordo River through Arizons, Colordo,, Nevada, Ulah.
**Pind States the Mountain Time Zone:
look for triles involving "Monnain Time 7one" and "time zones" relationship with state zones,
''Arizonnl,
Zune' indicates Arizcnu Mountain Zome. [Coolondo; location locaiio time zones' 'Meustain Time Zone]] indicatoo Colondo is in the Mountain Time Zone. Mountain Time Zone'] indicates Nevada the Mountain Time Zone.
[Nevadd', location. location
So, the states in the Mountain Time 7onc arc: Arizona, Colorado, Nevoda.
Intersection:"
appear
Soates the Colorado River runs through: Arizona, Colorado, Nevada, Utab.
Statex the Mountsin Time Zone: Arizons, Culorado, Nevadn.
The intersection of these two sets is: Arizona, Colorado, Nevada.
"FFomullate Amswer=** The states
River through
Time Zone Arizons,
Coluraoo Nevada. </think>
<answer> ('arioonn,, 'colorado', 'orvada" Varcada=///mmeer> jilnmwer>
Question: What sunce does the Colorao River nun thnugh in the Moustain Time Zone"Answer:]" "allaaeeeee""CCCrooo Colorado", "Nevada", "Arizona"!
GCR
"Reasoning Paths:/of
Reasoning 'Mountain
Zone common topic image Timeronaswes common aapgggep-pprrs....oo in wwtps/_pelllrrryyyeeeeeep.pppspe
> Samuu Time Zunzinki Answer'nSamss Time Zonćmi
Reasening Fuch'nC River grography river basin countries United States America
location. country administraiive divisioes Arizonsiat Anserr/nArizuuiur
Ressoning CCooorCoooraoo River > geography. river basin countrios > United Stules of America >> location.coume first level, divisions Colorado'ak AnsweriinCuuurabinn
Ressuning PubhinCllrrad River > location location partially containodby Utittn Anower/nUUllii! Reasoning PathonColorado River i location. location. partallllitit...aalllly....... containedby Colorado'ni kanwer/aColorrddiia answer "Ariznaa Colorado Utah"
Figure 14: Analysis of superlative reasoning patterns.
GED operates with less stringency than our path reward function; it allows for reward optimization merely through the addition substitution of nodes and edges, rather than enforcing precise path alignment. In conclusion, adopting a more complex reward function with rich graph structural features does not necessarily guarantee superior model efficacy.
M PERFORMANCE ANALYSIS WITH LESS CAPABLE COT MODELS
To investigate the impact of a weaker teacher model, we employed Qwen-32B as the teacher model in this section. As shown in the Table [T] although the weaker teacher resulted in decline in SFT performance, the final EoG performance following RL training recovered to a level comparable to the original baseline. This demonstrates that our method relatively insensitive to the teacher model's capabilities; rather, the performance gains are primarily driven by the RI training, this stage effectively refines the policy through interaction with the ground-truth graph environment.
N STATISTICAL EVALUATION DETAILS
To ensure the robustness of our results, we conducted three independent runs of EoG using different random seeds. As shown Table 12 by incorporating the standard deviation, we confirm that EoG maintains robust ffate-oftthe of-tth--tarrrrr art performance (c.g., 8 average), unaffected by statistical fluctuations. This establishes as a strong baseline and demonstrates the statistical reliability of our method.
25

---

Published as a conference paper at ICLR 2026
Table 7: Computational Cost Comparison: SFT vs. RL. Due difference among tokenizers used by different models, we measured SFT Computational Cost using SFT instances instead of tokens, as we consider instances to be fairer indicator of the SFT budget.
Metric
CWQ
WebQSP
GrailQA
2WikiMultihoPA
Supervised Fine-Tuning (SFT)
Training Steps
400
300
300
400
Training Time (h)
6.1
4.2
4.5
5.1
Train Batch Size
16
16
16
Micro Batch Size
2
2
Total Instances
3537
2344
4774
3102
Reinforcement Learning (RL)
Training Steps
108
36
12
96
Training Time (h)
509.6
119.2
76.8
205.6
Batch Size
256
256
256
256
Mini Batch Size
128
128
128
128
Micro Batch Size
2
2
2
Table 8:
Comparison of the performance of different closed-source commercial models on the KGQA datasets under various temperature settings.
GPT-5
Gemini-2.5- fl5ssh
Gemini-2.5-pre
Dataset
T=0.2
T=0.7
T=0.2
T=0.7
T=0.2
T=0.7
WebQSP
77.5
78.1
78.2
78.4
79.8
79.2
CWQ
67.6
67.6
59.3
59.7
65.3
65.7
GrailQA
85.4
85.2
83.8
84.3
84.5
85.1
QALD10-en
50.4
51.3
46.2
46.1
48.3
48.5
2WikiMullrhopQA
83.4
82.9
83.1
83.9
82.6
82.9
Beyond reporting mean performance scores, further validated the reliability of results through statistical hypothesis testing. Table [3 details the t-statistics and p-values comparing EoG with the GCR baseline. In all datasets, We performed standard t-test, yielding a p-value 0.05, which confirms that the performance gains of EoG over GCR are statistically significant and not due to random variance.
As illustrated in Figure 15 RL typically exhibits high variance during the training phase, repre- sented by the shaded error bands. can observed from Figure T5 that the model incorporating the path reward mechanism consistently achieves superior performance compared to the baseline across all three random seeds. The distinct separation between the error bands of the two methods after the 75th step indicates that our proposed framework achieves stable convergence and that the performance gain is statistically significant rather than a result of random variance.
O CONSTRUCTION OF GROUND-TRUTH REASONING PATHS
For datasets lacking explicit reasoning paths (e-g., WebQSP, CWQ, GrailQA, and QALD10-en), we constructed ground-truth paths (rgg) using two-stage "Search-and "earch-and-VVerff"" pipeline. This process bridges the gap in existing benchmarks by deriving reliable reasoning chains from raw Question- Answer (QA) pairs. Path Retrieval via Breadth-Firs. Search (BFS). We first employed BFS on the Knowledge Graph to retrieve all potential topological paths connecting the topic entity (identified in the question) to the ground-truie -trth answer entity. This step ensures high recall of potential reasoning chains. Semantic Verification via LLM. Since BFS often yields "spurious paths" paths that are topologically valid but logically unrelated to the question utilized L.LM (Gemini-2.5-Flashh
26

---

Published as a conference paper at ICLR 2026
Table 9: Detailed configuration of training and testing parameters for the GRPO phase.
Category
Configuration
Hardware
Compute Hardware: 8 x H100 GPUs
GPU Memory Utilization: 0.6
FSDP Offload: Param & Optimizer
Backbone
Rollout Engine: vLLM
Gradient Checkpointing: True
Training
Optimizer: Adam (implied by standard GRPO setup)
Learning Rate: 4 x 10-6
LR Warmup Steps: 10
Batch Size: 256 (Mini: 128, Micro: 3)
Gradient Clip: 1.0
KL Loss Term: Disabled
KL In Loss/Reward: False
Epochs: 6 (Train) / (Test)
Sampling
Temperature: 1.0 (Train) / 0.8 (Test)
Top-p: 1.0 (Train) 0.9 (Test)
Sampling Number (N)): 6 (Train) / 88 (Test)
Constraints
Max Prompt Length: 10,000 (Train) 20,000 (Test)
Max Response Length: 10,000
Overlong Penalty: > 3, 000 tokens (Train) / Disabled (Test)
Table 10: Performance on Various Datasets Across Different GED Coefficients
À 0.2
A = 0.4
À = 0.6
À = 0.8
X = 1.0
Dataset
F1
Hit@1
F1
Hit@1
F1
Hit@1
F1
Hit@
F1
Hit@
CWQ
69.7
78.2
68.5
77.3
67.9
77.1
67.1
76.3
67.3
75.9
WebQSP
80.6
89.6
79.4
88.9
80.2
89.3
79.8
89.2
78.9
88.2
GrailQA
90.3
91.8
89.9
91.4
89.6
91.2
90.1
91.3
89.7
91.5
2WikiMultihopQA
84.2
84.8
83.7
84.2
83.5
83.9
83.3
83.7
83.1
83.5
Table 11: Performance of EoG on the CWQ and WebQSP Datasets, using Qwen3-32B as the teacher
model.
Dataset
Metric
EoG (SFT Only)
BoG (SFT RL)
Improvement (%)
Fl Score
55.8
70.7
-4.3
CWQ
Hit@1
61.5
75.6
-8.4
F1 Score
71.3
80.2
-5.4
WebQSP
Hit@1
82.6
87.9
-.9
27

---

Published as a conference paper at ICLR 2026
Table 12: Performance comparison between our EoG framework (Llama-3.1-8B) and state-of-the- art closed-source models. The bottom section highlights the significant improvement of our RL- finetuned model over its SFT model. We report the mean + standard deviation for our method.
Methed
Model
WihQSP
CWQ
GnaiQA
QALDiOsss
2WitiMuliispQA
Hio1
F1
Hi01
Fl
Hir
Fi
Hir
Fi
Hir
Fi
GGnimn-25 Flahh
91.8
78.2
63.5
59.3
90.3
83.8
56.7
46.2
83.0
83.1
"Genini 2.5 Pho
92.1
79.5
71.9
63.3
91.5
84.5
58.6
48.3
85.1
82.6
N6.1
77.5
74.1
67.6
90.5
85.4
59.2
50.4
84.2
81.4
Qweez S-TH
K1-9
72.6
06.1
01.
89.2
81.6
25.6
46.1
825
819
74.5
705
02.1
91.4
88.2
83.1
Owea2.5-72
69.8
59.5
Table 13: Statistical comparison between GCR and our EoG framework using one-sample I-test (df 4). The table reports the baseline score, our model's performance (Mean + SD), and the calculated t-statistics and p-values. Results indicate statistically significant improvements across all metrics.
GCR (Baseline)
BoG (Ours)
Dataset
Metric
f-value
p-value
(Mean + SD)
Hit@1
92.2
92.8 + 0.28
4.79
0.009
WebQSP
79.1
81.3 + 0.33
14.91
0.001
Hit@1
75.8
82.6 0.41
37.08
0.001
CWQ
F1
61.7
73.9 + 0.20
136.46
< 0.001
Hit@1
88.4
92.1 0.30
27.57
< 0.001
GrailQA
Fl
85.1
90.6
49.20
< 0.001
Hit@1
57.6
70.6 0.49
59.33
< 0.001
QALDIO
Fl
49.3
0.38
74.12
0.001
Hit@1
84.6
85.3 + 0.23
0.23
6.80
0.002
2WikiMuldhopQA
77.5
84.3 0.44
34.56
0.001
as a semantic filter. The LLM was prompted to evaluate whether each retrieved path logically corresponds the semantic intent of the natural language question. Only paths that passed this semantic verification were retained as Tg for calculating Rpath.
Consequently, this approach provides the necessary supervision signals for the second-stage RL training, addressing the lack of rg in open-source benchmarks.
P DETAILED DEFINITION OF EXPLORATION METRICS
To provide a fine-grained analysis of exploration behavior, we parse the triples mentioned in the model's reasoning trace (the <think> block) the CWQ test
Let denote the test set with size = |D]. For the i-th question, let TT()) pred be the set of valid unique triples extracted from the model's 's reasoning path, and gold be the set of triples in the ground-truth reasoning path.
Exploration Efficiency ()). This metric measures the search overhead, representing the average number of triples the model explores to identify one correct reasoning triple. lower value indicates higher efficiency, implying less wasted exploration effort for each valid discovery. It is calculated as the mean ratio of total extracted triples to the number of correct triples found:
N N
Exploration Efficiency =
1
pred
(-)) gotal
pred
Coverage of the Reasoning Space (t). To define this metric, we first conceptalizze the Reasoning Space for given question the set of all potential valid paths within the Knowledge Graph that
28

---

Published as a conference paper at ICLR 2026
CWQ Val F1 Performance with Outcome Reward and different Path Reward
76
[1 11-AM AMRorso MRgrs (TA55 26307 74
72
AMarra Moas (7
[1- AMauww MRus w 1700 28320
70
F1 Score (%)
68
66
64
62
60
58
15
60
90 105 120
Training Steps
Figure 15: Validation F1 performance the CWQ dataset with varying Path Reward weights. The total reward is formulated as R = (1 A) Routcome + Apptth where À denotes the coefficient shown in the legend. The dashed vertical line marks the start of the second training phase at step 75, where the reward shifts from result-only RL to mixed result-and-path reward. Solid lines and shaded regions represent the mean and standard deviation across random seeds, respectively. The results indicate that À = 0.2 achieves the optimal balance, yielding the highest F1 score and robust stability compared to baseline (A 0.0).
connect the starting entity the target answer entities. Consequently, this metric measures the reasoning recall, quantifying the average proportion of the ground-truth logical chain (a subset the reasoning space) that is successfully uncovered by the model's exploration. higher value indicates better coverage, meaning the model finds more of the required logical steps. It is calculated as:
T
pred O (T())
1 N
gold
Coverage
IT |r((] gotal
29


Reviews:
[{"review_id": "tkou6L2QZx", "reviewer": "Reviewer_Fvcs", "summary": "The paper proposes **Explore-on-Graph (EoG)**, a KG-augmented LLM reasoning framework that couples (i) supervised fine-tuning on long chain-of-thought traces and (ii) reinforcement learning with a **path-refined reward**. The core idea is to *incentivize autonomous exploration* of novel multi-hop paths on knowledge graphs, improving generalization beyond rule/imitation patterns. Concretely, the RL stage optimizes a GRPO-style objective using a final-answer **outcome reward** (entity-level F1 extracted from the `<answer>` tag) and an auxiliary **path reward** that measures how many ground-truth triples appear in the model’s `<think>` text; a weighted sum defines the joint reward. Experiments on **WebQSP, CWQ, GrailQA, QALD-10-en, and 2WikiMultihop** show consistent gains over recent KG-enhanced systems, and ablations indicate the path-refined reward materially contributes beyond SFT alone.", "questions": "1. **Path reward verification.** Can the authors compute the path reward by **parsing the predicted path** into a sequence of relations and **executing it** on the KG to verify edge existence (vs. substring matching)? If not feasible, can they report a *hallucination rate* of triples mentioned in `<think>` but absent in the KG? \n2. **Robustness to reward hacking.** Did the authors observe behaviors where the model *lists many unrelated triples* to improve match probability? Any safeguards (length penalty, entropy regularization, path-structure constraints)?\n3. **Ablation on α and stability.** Figure discussing α suggests a sweet spot. Please include **training curves** and variance over **≥3 seeds** for each α to assess RL stability. (Also report GRPO hyperparameters.) \n4. **Closed-source comparison protocol.** For Gemini/GPT, please provide **identical decoding parameters**, prompt templates, and **budget parity** (n-samples, context length), or move these to an appendix with full reproducibility details. \n5. **KG execution failure modes.** In cases where KG lacks labels/edges (Figure 6-style), how often does EoG succeed via exploration vs. spurious textual correlations? Any breakdown by hop length and relation sparsity?\n6. **Significance & compute.** Please add **CIs** for Table 1 and **report training compute** (SFT tokens, RL steps, batch, GPU hours) to contextualize the gains.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "* **Clear motivation & problem framing.** The paper articulates why rule/imitation approaches struggle on OOD patterns and positions exploration as the missing capability. Figure 1 illustrates this vividly. \n* **Method is simple, modular, and reproducible in principle.** The rewards (answer F1; path triple-match ratio) are transparent and plug into a standard GRPO objective with KL control.  \n* **Strong empirical results across diverse KGQA datasets** with consistent gains vs. strong baselines; ablations show each component’s contribution and explore the α trade-off between outcome and path rewards. \n* **Ablations that are decision-useful.** Removing SFT, outcome, or path rewards degrades performance in expected ways, supporting the design choices. (Table 2 & ratio analyses in the text.)", "weaknesses": "1. **Potential reward gaming / verification gap.** The **path reward** credits substring co-occurrence of `(subject, relation, object)` tokens in `<think>` text rather than **verified KG traversals**. This leaves room for *verbalization without execution* (i.e., asserting triples to earn reward). The paper should either (a) execute the predicted path against the KG to produce a structural match reward, or (b) at least audit hallucinated triples vs. KG edges. \n2. **LLM-judge reliance for qualitative criteria.** The analysis of comprehensiveness/relevance/exploration uses **GPT-4o-mini** as judge; such measures can be noisy and model-biased. Human evaluation or KG-grounded automatic proxies would strengthen claims. \n3. **Comparisons to closed-source LLMs** (Gemini 2.5, “GPT-5”) are intriguing but ambiguous: API prompting details, temperature, and decoding budgets can shift outcomes; moreover, the “GPT-5” reference seems tenuous. I recommend focusing the SOTA claim on open-source or adding stricter evaluation parity. \n4. **Statistical reporting.** Tables omit **confidence intervals/standard errors** and **significance testing**, especially important across multi-seed RL runs. This weakens the strength-of-evidence for SOTA claims. (No CIs in Table 1.) \n5. **Scope of robustness/OOD probes.** While the paper argues improved OOD generalization, it would help to (i) include **systematic stress tests** (entity aliasing, edge deletions, spurious edges), and (ii) evaluate **path length sensitivity** with explicit adversarial splits beyond the included subsets.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ka7kNAtHc1", "reviewer": "Reviewer_Gg3c", "summary": "The paper proposes Explore on Graph (EoG), where not only the correct answer but also the reasoning path is rewarded via reinforcement learning, enabling the model to explore novel reasoning paths that fall outside the distribution of pre-defined rules or supervised fine-tuning data.\n\nThe experiments are comprehensive and show strong results on five KGQA datasets, outperforming not only open-source but also even closed-source LLMs.", "questions": "1. Same as Weakness 1: Are phase 1: Outcome Reward Modeling and phase 2: Path-refined Reward Modeling implemented sequentially or simultaneously (as in Equation 5)?\n2. For the OOD experiment (Figure 5), what do the x and y axes represent? Is the model trained on the dataset on the x-axis and then evaluated on the dataset on the y-axis, or vice versa?\n3. For the OOD experiment (Figure 5), what is the performance of other models in the OOD settings? It would be useful to compare EoG not only with EoG-SFT but also with other SOTA models (as in Table 1).\n4. Some things can be improved for clarity and readability. For example, in Figure 3, the meanings of the x and y axes are only available in the main body text. The reading experience would be greatly enhanced if the x and y axes were directly labeled in the figure.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The motivation is well grounded. Not only the answer but also the reasoning path can server as good reward signals.\n2. The experiments show strong results. For example, table 1 show EoG outperforms not only open-source but also even closed-source LLMs, and table 4 show strong results on OOD settings. The improvement is significant.", "weaknesses": "1. Some implementation details are not clear. Are phase 1: Outcome Reward Modeling and phase 2: Path-refined Reward Modeling implemented sequentially or simultaneously (as in Equation 5)?\n2. Reproducibility: The code is currently unavailable, which hinders verification, reproduction, and improvement efforts. Open-source code is crucial for these processes.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "WucPD7qADU", "reviewer": "Reviewer_dVt9", "summary": "This paper proposes Explore-on-Graph (EoG) framework that incentivizes LLMs to autonomously explore diverse reasoning paths on Knowledge Graphs for Question Answering. The methods consist two stages: (i) SFT using long CoT by Gemini 2.5 Flash, (ii) reinforcement learning with Group Relative Policy Optimization using both outcome reward and path refined reward. The authors evaluate EoG on five KGQA benchmarks and demonstrate state-of-the-art performance, though I must say the results for the baseline are mostly missing.", "questions": "1. What are the computational costs of the RL training stage compared to standard supervised fine-tuning? How many GPU hours are required for convergence?\n2. Have you considered more sophisticated path reward designs that account for semantic similarity rather than exact substring matching? For example, using graph edit distance or learned similarity metrics?\n3. Can you provide the generated CoT datasets or detailed statistics about them to enable reproducibility without access to Gemini 2.5 Flash?\n4. How sensitive is the method to the quality of the initial SFT stage? What happens if a weaker teacher model is used for data generation?\n5. Have you analyzed failure cases where exploration leads to incorrect paths? How does the model handle ambiguous questions where multiple valid reasoning paths exist?\n6. Could you provide theoretical analysis or empirical evidence about the exploration efficiency and coverage of the reasoning space? For example, to improve the content of case study?\n7. Why are so many experimental results missing in Table 1? (I don’t think “the original paper did not report the experimental results of this dataset” is a good answer)", "limitations": "", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. This method outperforms powerful closed-source models such as GPT-5 and Gemini-2.5 Pro, which is impressive.\n2. The paper is well written, with clear motivation and problem formulation, and provides a good example (Figure 1) illustrating the limitation of existing approaches and the EoG methods.\n3. Smaller open-source LLM trained by EoG can compete with larger closed-source ones, which means EoG addresses some of the current compute resource limitations.\n4. Well-organized experiment, ablation study effectively demonstrates the importance of each component.", "weaknesses": "1. Limited technical novelty: The core contribution combines existing techniques (SFT, GRPO, simple reward design) without significant algorithmic innovation. The path reward is particularly simplistic, using only substring matching. In the area of KG reasoning, using reinforcement learning to explore path is a general and common practice. Check MINERVA [1] and DeepPath [2].\n\n2. The reliance on Gemini 2.5 Flash for dataset generation creates a dependency that may limit reproducibility. The paper doesn't discuss alternatives or provide the generated datasets.\n\n3. More than half of the baseline experimental results in Table 1 are missing, and the authors do not provide any explanation in the paper. I do not think that the effectiveness of EoG can be proven based on Table 1 alone, as the baseline results are extremely limited.\n\n4. The paper lacks a discussion of training costs, convergence time, and computational requirements for the RL stage.  As the paper says it trains EoG on 8*H100 GPUs, which is very costly. This may be a strong limitation of the proposed method. \n\n5. The substring-based matching in Equation 4 is brittle and may not capture semantic equivalence, paraphrases, or partial correctness in reasoning paths.\n\n\n[1] Das, Rajarshi, et al. \"Go for a Walk and Arrive at the Answer: Reasoning Over Paths in Knowledge Bases using Reinforcement Learning.\" International Conference on Learning Representations. 2018.\n[2] Xiong, Wenhan, Thien Hoang, and William Yang Wang. \"DeepPath: A Reinforcement Learning Method for Knowledge Graph Reasoning.\" Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing. 2017.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "GHn8srabdS", "reviewer": "Reviewer_Fb3S", "summary": "This paper addresses the challenge of poor generalization in existing Large Language Model (LLM) methods for Knowledge Graph Question Answering (KGQA), which often fail when faced with reasoning patterns not seen during training. The authors propose \"Explore-on-Graph\" (EoG), a novel framework designed to incentivize LLMs to autonomously explore diverse reasoning paths on a knowledge graph (KG).", "questions": "see weaknesses", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The core contribution—incentivizing autonomous exploration on KGs via reinforcement learning—is a novel and important step beyond prevalent imitation-based methods. While RL has been used for KG reasoning in the past, its application to modern LLMs with the proposed two-phase reward structure (outcome + path-refinement) is original. The \"path-refined reward\" is an intuitive and clever mechanism to make the exploration process more efficient and meaningful, rather than just rewarding the final outcome. This directly addresses the critical problem of out-of-distribution generalization in KG reasoning.", "weaknesses": "The path-refined reward, Rpath, is a key component of the method. Its calculation (Equation 4) requires a \"ground-truth reasoning path\" rg. However, the paper fails to explain how these ground-truth paths are obtained for the training data across all five datasets. While some datasets (e.g., 2WikiMultihop) may provide such paths, it is not standard for others like CWQ, WebQSP, or GrailQA. This is a critical missing methodological detail. \n\nThe proposed SFT + RL pipeline, particularly using GRPO with multiple rollouts per prompt, appears to be computationally very expensive. The paper mentions using 8xH100 GPUs but does not provide a broader discussion on the training time, total computational budget, or the trade-offs between performance gains and the significant training overhead. A comparison of the computational cost against simpler fine-tuning methods would be valuable for assessing the practical applicability of EoG.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)