VoG: Enhancing LLM Reasoning through Stepwise Verification on Knowledge Graphs
Authors: Wenxin Zhao
Jiachuan Wang
Yongqi Zhang
Shuangyin Li
Cheng Deng
Jun Wang
Lei Chen
Venue: ICLR 2026 Poster (2026)
Keywords: LLM reasoning
Knowledge Graphs
KG-enhanced LLM
Primary area: neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)

Abstract: Large Language Models (LLMs) excel at various reasoning tasks but still encounter challenges such as hallucination and factual inconsistency in knowledge-intensive tasks, primarily due to a lack of external knowledge and factual verification. These challenges could be mitigated by leveraging knowledge graphs (KGs) to support more reliable LLM reasoning. However, existing KG-augmented LLM frameworks still rely on static integration mechanisms that cannot adjust reasoning in response to evolving context and retrieved evidence, resulting in error propagation and incomplete reasoning. To alleviate these issues, we propose  **V**erify-**o**n-**G**raph (**VoG**), a scalable and model-agnostic framework to enhance LLM reasoning via iterative retrieval, stepwise verification, and adaptive revision. Besides performing KG retrieval guided by an initially generated reasoning plan, VoG iteratively verifies and revises the reasoning plan, correcting intermediate errors in consideration of the varying contextual conditions. During plan revision, VoG leverages a context-aware multi-armed bandit strategy, guided by reward signals that capture uncertainty and semantic consistency, to enhance the alignment between the reasoning plan and retrieved evidence in a more adaptive and reliable way. Experimental results across three benchmark datasets show that VoG consistently improves both reasoning accuracy and efficiency. Our code is available at https://github.com/WenxinAZhao/VoG.

Published as a conference paper at ICLR 2026
VoG: ENHANCING LLM REASONING THROUGH STEP- WISE VERIFICATION ON KNOWLEDGE GRAPHS
Wenxin Zhao', Jiachuan : Yongqi Zhang',
Shuangyin Li,, Cheng Deng',
Jun Wang', Lei Chen
The Hong Kong University of Science and Technology (Guangzhou)
University of Tsukuba "oouh China Normal University *University College London 5 The Hong Kong University of Science and Technology
ABSTRACT
Large Language Models (LLMs) excel various reasoning tasks but still encounter challenges such as hallucination and factual inconsistency in knowledge-intensiin tasks, primarily due to a lack of external knowledge and factual verification. These challenges could be mitigated by leveraging knowledge graphs (KGs) to support more reliable LLM reasoning. However, existing KG-augmented LLM frame- works still rely static integration mechanisms that cannot adjust reasoning in response to evolving context and retrieved evidence, resulting in error propagation and incomplete reasoning. To alleviate these issues, we propose Verify-on-Graph (VoG), a scalable and model-agnostic framework to enhance L.M reasoning via iterative retrieval, stepwise verification, and adaptive revision. Besides per- forming KG retrieval guided by an initially generated reasoning plan, VoG iter- atively verifies and revises the reasoning plan, correcting intermediate errors consideration of the varying contextual conditions. During plan revision, VoG leverages a context-aware
bandit strategy, guided by reward signals that capture uncertainty and semantic consisteney, to enhance the alignment be- tween the reasoning plan and retrieved evidence a more adaptive and reliable way. Experimental results across three benchmark datasets show that VoG consis- tently improves both reasoning accuracy and efficiency. Our code is available at https://gittuu: com hwwp://wnwinaaaaaaaaaa
INTRODUCTION
Despite the impressive reasoning capabilities across various natural language understanding and generation tasks (Guo et al. 2025 OpenAl 2023), large language models (LLMs) continue to face
challenges in solving knowledge-intent
tasks that require multi-hop reasoning (Ji et al. 2023 Bang et al. 2023) The essential limitation lies in the lack of up-to-date or specialized knowledge
included in their pre-training stage and the limited transparency and explainability in their reasoning processes. To address these issues, Knowledge Graphs (KGs) (Bollacker al., 2008 Auer al.
[ et al., 2007) have been adopted as promising external knowledge sources due to their explicit, organized and updatable nature (Agrawal al.. 2024 Wang et al.) 2023a Pan et al.) 2023).
Existing frameworks generally follow two main directions to enhance LLM reasoning with KG. Previous methods enable LLMs to plan structured paths or logical forms, such as SPARQL (Pérez et al. 2009) queries, before interacting with KG (Luo et al.) 2024a Li et al. 2023 Luo et al. 2024b; Gu et al., 2022]. While planning approaches facilitate structured inference, they often require expensive fine tuning and are vulnerable to retritee-related errors (c.g., con-cxccutable queries or non-existent entities). Thus, several studies focus on optimizing the retrieval process to better support LLM reasoning. Typical methods including retrieving KG triplets and presenting them statically to the LLM (Zhang et al. 2024 Zhho et al. 2024 Wang et al. 2023b Wen et al.) 2024, Yasunaga et al. 2022) and conducting stepwise retrieval with LLM agent (SUN al. 2024 Huang al.) 2024), both aiming to ground reasoning in structured knowledge of KG. Yet, these approaches still lack effective mechanisms align retrieval with evolving subgoals, prompting recent work to integrate planning into the retrieval process to better guide multi-step inference (Jiang et al. 2024 Guan et al. 2024).
Coorreponndence Jiachuan Wang

---

Published as a conference paper at ICLR 2026
(a) Plan-only
(b) Retrieval-only
(c) Retrieval + Plan
Retrieval Plan Verify (Ours)
Question
Question
Question
Plan
Question
Question
Verify Agent
+
Verify
LLM
KG
Step
Path/ SPARQI.
Triplets/ Subgraph
Depth
LLM agent
goal
Depth 1
j LLM agent
PLAN 1
guide
Retrieva
LLM
Depth
Sub- goal 2
Depth
Agent
PLAN
revise
4
Verify Step
Agent
LLM agenc
LLM agent
guide
Amswer
Answer
Answer
KG
Answer
KG
Answer
Q: What currency is used in country with Nobel Patria, tu hermosa as its national anthem? Costa Rican colón
(a) Plan-only
Retrieval + Plan + Verify (Ours)
Q generated non-executable path;
Initial Plan:
composition language how.:aouggooooooooooooooouuoaaee wag.uugg spoken
Retrieve
Thought need find
Agent 1k3x
(b) Retrieval-only
what currency is used in Need to revise! Venezuelal
Onational a
U Unrecognized entity in KG:
Action 2 searchfeurreng
whem of
(Noble potria, tu bermossa bandera, government. national anthem of, m.0h, 1h3x)
used Venezuela)
country-PC
Minsig
granng
Y
Observation 2: (Venezuela.
Rica)
uses. Balivar)
Irilansnt
① Fixch-width/depth pruning error:
Plan Agent
LLM agent: Insufficient answer
Revised Plan:
Retrieve
Agent
(c) Retrieval Plan
Revised Observation 2: (Cosla Rica, uses, Costa colón)
Verified
(Costa Rica
①
Early stop due to LLM ignoring complete plan:
currency
Subgoal I: find the country; Subgoal 2: find the currency Retrieved at depth I: Noble p national anthem of m.0h thax
ed?> Costa
Thought 3: have confirmed the final answer.
Rican oolón)
Reasoning: The evidence sufficient, The answer Uruguayan peso.
Action Finish Rican colón)
Figure comparison of existing KG-enhanced reasoning frameworks using a representative question example. Errors resulting from LLM hallucinations are highlighted in red. Text in green denotes LLM--gnerated content, while KG-retrieved triplets are shown in blue.
However, current KG-enhanced LLM frameworks still suffer from below challenges: (1) Inflexible reasoning: exiting works either follow predefined reasoning paths or conduct graph search based on fixed parameters (e.g., depth and width), as shown in Figure bb), leading to incomplete utilization of KG evidence and cascading reasoning errors. (2) Limited use of information: Most agent-based frameworks focus solely on retrieved triplets at each local step, ignoring global context such as prior reasoning steps and heward-looking relation, which makes them vulnerable to unrecognized entities at intermediate steps and prone premature termination illustrated in Figure [ c).
To address these issues, we propose novel Verify-on-Gran (VoG) framework that supports dynamic and context-aware LLM reasoning over KG. Specifically, VoG employs a framework involving three specialized LLM agents that collaboratively perform retrieval, verification, and revision in an iterative manner. Initially, the plan agent generates reasoning plan inspired by ReAct (Yao al. 2023), which serve both as global-level roadmap for retrieval and as contextual memory for maintaining coherence across long reasoning chains. To address the inflexible reasoning and mitigate the error propagation, VoG performs stepwise verification to detect reasoning inconsistencies as they arise and ensure the correctness of subsequent reasoning steps. Furthermore, overcome the limitations of purely local reasoning, VoG strategically incorporates KG- "G-ggrunded feedback and contextual information to revise its reasoning plan by proposing multi-armed bandit (MAB) context selector. In summary, our main contributions are follows:
We propose a novel framework that enables stepwise verification on KG mitigate error propagation during multi-hop reasoning. Through iterative refinement of reasoning plans, we process the adaptive KG retrieval to collect relevant KG feedback for the targeted question.
We introduce a KG-aware multi-armed bandit (MAB) mechanism for adaptive context selection, which dynamically determines the maximally informative subset of KG feedback and reasoning history at each step to enhance factual consistency.
We implement VoG and evaluate it on three KGQA datasets. Results both open- and closed-source LLMs validate that our framework outperforms the state-of- -f- basclines and generalizes robustly across diverse backbones.
2

---

Published as a conference paper at ICLR 2026
2 PRELIMINARY
We introduce the preliminaries used in this paper follows.
Definition (Knowledge Graph (KG):) A knowledge graph G represented as a collection of factual triplets, formally defined G ((hhead T, (tait), where each triplet consists of a head entity Chead a tail entity tool and their relation
Definition 2 (Reasoning Plan:) Given question Q, L.M generates structured reasoning chain $1, , ST], in which the 1-th step 9t consists of the 1-th thought, action, and corresponding predicted observation, denoted (T,, At, Pt).
Definition (KG Feedback:) At each reasoning step t, executing retrieval guided by the action A
retrieves set of KG triplets relevant to the current reasoning context, denoted as O, = =o] (2) ..... where each o = (Chead, v, esast) is triplet G. These triplets serve as the KG feedback at depth to support verification and revision of the reasoning plan.
Problem Statement: Given a question Q, a knowledge graph G, and a set of topic entities explicitly mentioned in Q. the goal of multi-hop knowledge graph question answering (KGQA) ) is to find the
answer entities are multiple hops away from the topic entities over the KG. Considering the flcxibility and the training cost, follow previous agent-based work(Chen al. 2024 SUN et al. (024) that iteratively retrieve and reason over KG. In this stepwise manner, we aim to guide retrieval with reasoning plans and use the KG feedback to revise the reasoning plan in turns.
3 METHOD
As mentioned in previous section, existing methods exhibit limited ability to adjust reasoning dynamically based on KG feedback. To address this gap, we propose VoG, which first generates an initial reasoning plan, retrieves supporting KG evidence for verification, and revises the plan upon detecting inconsistencies. An overview framework is given in Figure
$3.1
$3.2
$3.3
Update
$3.4
S(O)
S(0)
5(0)
Guide
Initial plam
History plats
Avwurd vgl
Reward Design
Triplets
Apand goast
Verify Agent
Plan Agent
Agent
Tripien
Putture Info
Rextoed plans
Youny (
KG
Select Return
Context selector
Vtuent i
Stepwise KG Retrieval
Verify
Stepwise LLM Revision
Figure 2: Overview the VoG framework. An initial reasoning plan is first generated ($3.1) guide the retrieve agent to perform stepwise retrieval ($3.2). If the Verify agent gives the revision signal based on retrieved feedback and plan ($3.3), the revision is conducted by the plan a8e.1($3.4).
3.1 INITIALIZATION AND PLANNING
Given question Q follow mainstream work and utilize plan agen! generate complete multi- hop reasoning plan over the KG, which guide downstream retrieval and reasoning processes. The initial plan is denoted as ((() [$1, $2...., ST]. where is the total number of steps. Based on it, one can retrieve information from KG based on plan 5()) step by step. This iterative process continues until all planned steps 7 are executed and verified. Note that T implicitly defines the reasoning depth, which allows plan agent to adaptively adjust it dynamically based on the execution of the plan itself, rather than relying on fixed-depth settings.

---

Published as a conference paper at ICLR 2026
3.2 STEPWISE KG RETRIEVAL
In this section, we design twO-stage retrieval mechanism guided by the reasoning plan.
Plan-Guided Relation Retrieval. At each reasoning step L. VoG retrieves relevant KG relations
guided by the action A, from the current plan step (Figure 3 Let E = {ee ....... (t-1))
be the set of entities obtained in the previous step. We execute structured KG queries (Appendix I.
to enumerate adjacent relations for each e," (t-1), forming a candidate set R, The retrieve agent then prompted, with the current action A, as input, to select set of relations R, that are most relevant to the reasoning objective. To mitigate noise in large candidate sets, we apply entropy-based adaptive sampling using Sentence-BEi BERT similarity scores (Reimers and Gurevych] 2019). Filtering and
and prompt design details are provided in Appendix A.2 and and A.3.2
Man-Guided Entity Retrieval. Based on the selected relations, VoG retrieves new entities to update KG feedback. For each selected r E Rr and entity e; (t-1) we query the KG using patterns
(e(-=),,?)) ?r and (2 e,rr) yielding
candidate entity set E gçand, 'he same entropy- based sampling is applied when needed, helping the retrieve agent select from e(t) E Ex to obtain & and append the correspond-
Plan at depth (Te.A, 0.)
9t
Guide
E
Thought Te -....
Action
0
(enrchlkeywords]
Y1
ing triplets (e: (e(t-)),,, e to Or, using the original question Q and predicted observa- tion Pred_O. as context. Prompt details in Appendix A...3] This process reduces
Pred Observation
Retrieve Agent
predict , predictt predicc
(Chend , prediit prediick )
preais
irrelevant expansions and ensures that subse- quent reasoning is well supported.
Figure 3: Plan-Guided Retrieval
3.3 STEPWISE KG VERIFICATION
Most of the existing works conduct retrieval KG simply following the initial reasoning plan (Jiang ctt al., (2024) Chen et al. 2024) that could be non-optimal or even misleading. To mitigate error propagation and enhance factual consistency, introduces stepwise KG verification mechanism that integrates retrieved KG evidence as feedback.
Specifically, given in the generated plan S, VoG obtains a set of feedback O₂ = ((c head: eait consisting of KG triplets. Using them as factual information, a verify agent is first prompted to compare against the predicted observation Pred_Or E 8t. To further enhance the reliability, we additionally implement a pretrained DeBERTa verifier (He et al.) 2021) as a secondary check. The prompts are provided in the Appendix A.3.4 Formally, define the revision signal as:
(c)
{
if Pred O, E is inconsistent with O otherwise.
V(Q, St, O.)
(I)
When VIQ, st O,) = VoG flags the current step unreliable and triggers revision process. This mechanism ensures alignment between the reasoning and retrieved KG feedback, allowing the agent iteratively refine its plan before proceeding the next step. Once we obtain a positive revision signal from above verification, we can handle the inconsistency issue by revising the reasoning plan. A detailed analysis of revision signal triggering provided in Appendix E.
3.4 STEPWISE PLAN REVISION
Effective revision after verification hinges on addressing two central challenges. (i) The inherent sensitivity of LLMS to contextual inputs, together with the varying contextual requirements across different scenarios, necessitate a more dynamic strategy that can explore diverse context configurations while exploiting the most effective ones to support accurate revision. (ii) The potential of LLMs to generate hallucinated redundant steps that misguide later reasoning highlights the need for evaluation, ensuring that each revision step is well aligned and verifiable against factual knowledge from KG.
4

---

Published as a conference paper at ICLR 2026
To address these challenges, we propose a dynamic revision framework that couples adaptive context selection with explicit reward evaluation. At each revision step i, the plan agent proposes a revised plan (( with selected context, which is executed from 1+1 onward if meeting the reward criterion. In the following, we detail how VoG achieves stepwise revision by flexibly adjusting context use to tackle (i) while ensuring conciseness and factual consistency with KG feedback to address (ii).
3.4.1 CONTEXT- UCB SCORING
The sensitivity of LLMs to contextual inputs implies that static heuristics or fixed strategies brittle. To adaptively select the best contextual scope at each step, we formulate context selection as multi-armed bandit (MAB) problem. As shown in See 4.5] the high context-dependence of strategy effectiveness further underscores the necessity of an adaptive selector.
Specifically, we define three complementary strategies C {Local, Lookahead, Global} correspond- ing to minimal, proactive, and comprehensive use of context. These capture the main modes of leveraging KG feedback and reasoning history, and thus serve as the candidate arms in our selector:
Local that focuses solely on the immediate KG feedback O,, resulting in the input form Frevise (S which can effectively correct hallucinations when explicit triples are available.
Lookahead that further incorporates future relations R&+1 to the input frevise (S Oz, Re-1),
enabling proactive adjustment to avoid incomplete reasoning.
Global which aggregates the full reasoning plan and all past KG feedback O1.,. leading to the input Frevise (S O1:). This strategy enables broader reassessment, which is particularly useful when accumulated errors or query intent drift occur.
To select among these strategies, we adopt the classical Upper Confidence Bound (UCB) algo- rithm (Kaufmann al. 20112) and further extend it with context-aware priors. Formally, for each candidate context strategy e E C, we record the number of times it has been selected N, and its cumulative reward Re, At each step t, the UCB score is then defined follows, with the robustness of this design further validated through ablation and sensitivity analyses in Appendix E..4 and E.5
Re
log N N₂
UCB =
+a
Bene (Hle + BRG(t, Erep) + Bai (c),
Context-aware Priors
Exploitation
Exploration
where a fixed constant and N is the number of total selection times. Here, H₃ denotes the normalized entropy of the current answer distribution, which signals the level of uncertainty like in previous work (Kuhn et al.) (2023), and Erep denotes the set of entities repeatedly retrieved from the accumulated KG feedback O1a- We then incorporate three context-aware bonus terms: entropy- based bonus Beml ( H2) that promotes exploration under high answer uncertainty, a KG-aware bonus BRG(t, Erep) that penalizes repetitive retrieval and diversity bonus (ai(()) that discourages repeated selection of the same strategy. Precise definitions for each term and the full algorithm are detailed in Appendix B.1
3.4.2 REWARD DESIGN
To guide strategy selection, we assess the effectiveness of the chosen context strategy via the quality of revised plan. Once a strategy e; E selected, the plan agent generates candidate reasoning plan. Considering the inherent unreliability and instability of LLM outputs, we design a scalar reward it that jointly captures step-level coherence and global answer stability as detailed below.
Task-specific Reward. The task-specific reward Mocal measures the local quality of a revision through heuristic signals derived from the reasoning process. The stepwise nature of VoG reveals a heterogeneous set of contextual evidence each reasoning step, including KG feedback, historical reasoning steps, and the evolving reasoning plan that reflects the model's interpretation of the question. This enables evaluates revisions from a broader range of perspectives, reducing the risk of any potentially biased single signal dominating the revision process. We incorporates five key metrics to evaluate the quality of each revision as shown below:
Validation: Verifies the revision by assessing the consistency of revised observation Pred O, against KG feedback, which ensures that the revision validated by factual knowledge in KG.
5

---

Published as a conference paper at ICLR 2026
Quality: Evaluates the semantic relevance between the revised observation Pred Og and the question Q. This metric assesses the quality of revision process by ensuring that the revision aligns with the original query intent.
Question Alignment: Ensures that the reasoning process maintains a consistent goal throughout multi-hop reasoning by measuring the similarity between reasoning sub-steps and the query.
Thought Coherence: Ensures the alignment between the current reasoning step T3 and the relevant KG feedback, verifying that the reasoning is coherent with the knowledge provided.
Efficiency: Penalizes reasoning steps that repeat overlap significantly, reducing redundant reasoning and encouraging more efficient and progressive paths.
In contrast to prior work that relies on LLM-based scoring (Sui et al. 2025 Zheng et al. 2023 we
adopt lightweight pre-trained models for these checks, which makes the evaluation both efficintt and scalable without incurring additional inference overhead. Full details are provided in Appendix B.2
Confidence- Based Reward. The confidence- based reward V/caat measures the stability of the final an- swer across candidate reasoning plans generated during revision. Formally, let P = [S1, ... Sx) denote the set of candidate reasoning plans generated during revision, and as; be the final answer of plan S,. To measure confidence here, we subscript i exclusively to index all candidate plans in P regardless step. We use ~ to denote semantic equivalence between answers and define the reward Poonf for candidate plan S; as:
1 I(as ~ as:).
Vont (S.))
IP
SEP
This reward encourages convergence toward stable, high-confidence answers that are consistently supported across multiple candidate plans.
Entropy-aware Integration. To adaptively balance local and global signals, we introduce an entropy- aware weighting scheme. Let H, E [0, 1] denote the normalized entropy of the answer distribution at step t, and B E (0, 1) scaling factor. We compute:
d = 3 exp(-1f:), Vt -== (1 Xx) Mocal + Xe Voonf-
Intuitively, when the answer distribution is uncertain (high H,), the global consensus reward dom- inates; when the distribution is confident, local reasoning quality takes precedence. The resulting scalar reward is then accumulated as R. to update the UCB score in Eq. (2). thus closing the loop between revision evaluation and adaptive strategy selection. Ablation on the reward design provided in Appendix E,6
4 EXPERIMENT
4.1 EXPERIMENT SETUP
Datasets. To evaluate the effectiveness of VoG in enhancing the reasoning capabilities of large language models on knowledge-intensive tasks, we conduct experiments across three widely-used datasets. Specifically, conduct experiments two multi-hop KGQA datasets, WeenulsseWeeuus- tions (CWQ) (Tammor and Berant 2018) and WobQuestionsSP (WebQSP) (Yih et al.) 20166). as well as the open-domain QA dataset WebQuestions (Berant et al. 2013). All datasets rely Freebase (Bol
lacker et al. 2008) as the underlying factual source. Following previous studies et al., 2024
Chen et al. 2024).
adopt exact match accuracy (Hits @ 1) our primary evaluation metric and also report Fl scores for completeness. We show the details of above datasets in Appendix C
Baselines. To comprehensively evaluate our framework, we compare VoG against three major categories of bascline approaches: (i) LLM-only methods, (ii) fine-tuned methods, and (iii) LLM agent+KG methods. For ILLM-nnly baselines, we adopt IO prompting (Brown al.) 2020) and CoT (Trieddi et al. 2023). For fine-tuned methods, we include KD-CoT (Wang et al.) 2023b). DECAF (Yu et al. 2023). RoG (Luo et al.) 2024b), UniKGQA (Jiang et al., 2022) and GNN- RAG (Mavromatis and Karypis, 2224). In addition, we further include methods that fine-tune only the retriever while keeping the LLM frozen, such as SubgraphRAG (Li et al.) 2025) and the unfine-tuned LLM variant of GNN-RAG (Mavromatis and Karypis 2024). For LLM agent based approaches, compare with ToG (SUN et al. (2024) and PoG (Chen et al. 2024). Full implementation details of all baselines are provided in the Appendix D

---

Published as a conference paper at ICLR 2026
4.2 MAIN RESULTS
Table Summarizze the performance of VoG across three benchmark datasets compared to represen- lative state-of-the-art (SOTA) baselines. Overall, VoG outperforms all included baselines across all categories methods.
First, compared to LLM-only baselines, VoG significantly improves performance by incorporating structured knowledge from external KGs. This highlights the importance of factual grounding in multi-hop reasoning, particularly for complex questions where parametric knowledge alone is insufficient. Second, we compure VoG to fine-tuned methods. Despite not requiring additional fine-tuning, VoG achieves competitive superior performance, demonstrating the effectiveness of its verification-driven and plan-adaptive design.
Finally, when compared agent- agent-based based reasoning frameworks, VoG attains higher accuracy through stepwise verification and adaptive context selection mechanisms. To assess generalizability and effectiveness across different model sizes, further evaluate VoG using smaller-scale LLMs (e.g..
Qwen2.5-7B Team (024g). Even under reduced model capacity, VoG achieves robust improvements over baseline agents, confirming that its gains stem from methodological advances rather than reliance on model scale. Beyond our main experiment conducted on Freebase (Bollacker et al., 2008). we further demonstrate VoGi's generalization ability on Wikidata (Vrandečić and Krötzsch (014). as shown in Appendix
Table I: Performance comparison of different methods across datasets. Bold indicates the best agent performance for each backbone.
CWQ
WebQSP
WchQuestions
Method
EM
F1
EM
FI
EM
F1
L.M-only
GPT-3.5
10 prompt (Brown et al.
2020
37.6
63.3
48.7
CoT Trivedi et al. 2023
38.8
62.2
48.5
SC Wang et al
2022)
45.4
61.1
50.3
Fine-tuned methods
Fine-tuned LLM
KD-CoT Wang et
2023b
68.6
UniKGQA Jiang
2022
51.2
48.0
77.2
70.2
RoG [uo et al.
2024b
62.6
56.2
80.4
70.8
DECAF Yu al.
2023
70.4
82.1
KG-Agent Jiang et al.
2024
72.2
83.3
GNN-RAG+RA (Mavromatis and Karypis
2024
68.7
60.4
90.7
73.5
Fine-tuned Retriever + GPT-3.5
GNN-RAG (Mavromatis and Karypis
2024
64.1
SubgraphRAGG (Li 2025
56.3
49.1
83.1
69.2
I.M Agent + KG
Qwen2.5-7B
ToG SSN al.
2024
42.5
28.7
56.0
37.3
39.9
31.3
PoG Chen et al.
2024
46.0
31.4
58.5
40.4
46.2
30.3
VoG (Ours)
53.3
45.6
67.3
55.1
52.8
45.2
GPT-3.5
ToG (SUN et al.
2024
58.9
41.9
76.2
50,9
54.5
39.3
PoG (Chen et al.
2024
63.2
43.7
82.0
58.1
61.7
44.3
VoG (Ours)
64.7
63.0
61.3
GPT-4
ToG
SUN
2024
67.6
47.6
82.6
58.9
57.9
44.9
PoG
Chen et al
2024
75.0
42.1
87.3
59.8
71.7
44.5
VoG
(Ours)
77.6
67.5
88.7
73.2
72.3
61.7

---

Published as a conference paper at ICLR 2026
4.3 ABLATION STUDY
We conduct the ablation studies on CWQ and WebQSP using GPT-3.5 as the backbone model to provide comprehensive view of how VoG achieves its performance gains.
Impact of the verification and adaptive revision. We first examine the stepwise verification mechanism and the contribution of context selector of VoG as shown Table In the w/o Context Selector variant, the bandit-based adaptive strategy is replaced with single fixed strategy, so revisions are performed without dynamic strategy at each step. the w/o Verify+Revise Revise variant, the plan agent directly outputs the answer from its initial plan without performing retrieval, verification, or revision as the plan-retn seen--etrieve--eviiee process VoG constitutes a unified feedback loop. Interestingly, this plan- only configuration still outperforms standard CoT and Self-Consistency baselines, suggesting that LLMM-interal planning alone offers strong multi-hop reasoning capabilities, but remains vulnerable error propagation without external verification and revision.
Table 2: Ablation Study on VoG's Stepwise Verification and Adaptive Revision.
Variant
CWQ
WebQSP
WebQuestions
VoG
64.7
83.2
63.0
w/o Context Selector
Local
60.1 (14.6)
80.6 ((2.6)
58.2 (J4.8)
Lookahead
63.6 (11.1)
81.4 (11.8)
59.9 (13.1)
Global
60.2 (14.5)
80.3 (J2.9)
60.6 (J2.4)
w/o Revify
51.7 (113.0)
72.1 (111.1)
55.8 (17.2)
Effect of Different Context Strategies. We further analyze the effectiveness of three fixed strategies and compare them with our KG-aware context selector. Each variant in the w/o Context Selector setting above corresponds to fixed strategy applied end-to-ent throughout the reasoning process. All fixed strategies fall short, since none can adapt effectively across diverse reasoning scenarios. In contrast, our method adaptively selects the most suitable context at each step achieve more accurate and flexible reasoning. A detailed analysis of strategy-level performance, including accuracy and revision rates per iteration, is provided in Appendix B.3
4.4 EFFICIENCY ANALYSIS
We further assess the computational efficiency of VoG by the average token consumption per query, conducted in prior agent- based base- lines. As shown in Table 3 VoG significantly reduces token usage and maintain comparable or lower levels of LLM interaction. A detailed token breakdown across planning, retrieval, ver- ification, and revision steps is provided in Ap- pendix E.2 We also analyze the trade-offs be- tween complexity and performance gains in Appendix E.7
Table 3: Efficiency analysis on average tokens and calls per query compared with existing methods.
CWQ
WebQSP
Method
Tokens
Calls
Tokens
Calls
ToG PoG VoG
9669.4
22.6
6031.2
15.9
8156.2
13.3
5517.7
9.0
6566.8
14.5
3439.0
9.4
This efficiency gain stems from two key aspects. From a methodological perspective, VoG adopts an adaptive retrieval strategy to prioritizes relevant information and employs a context selector that contributes to reducing unnecessary input. Moreover, its plan-guided retrieval enables adaptive control over depth and breadth, avoiding the irrelevant exploration introduced by beam search in ToG and thus improving overall retrieval efficiency. From an implementation standpoint, VoG stores context implicitly within the reasoning plan, avoiding external memory modules required in PoG and enabling direct answer extraction without additional LLM calls. Together, these design choices make VoG a more practical and lightweight solution for scalable KG reasoning, especially under limited computational budgets.
4.5
CASE STUDY
In this section, we present a fine- ane-ggrinedd case in Figure heatmaps. In the presented case, the Local strategy, which is typically effective when explicit triples are available, becomes limited here because the entity exists in the KG but lacks a resolvable name. By contrast, the Lookahead strategy, which observes future relations, and the Global strategy, which
4 Juiing Qwen2.5-7B and visualized attention
8

---

Published as a conference paper at ICLR 2026
helps avoid query intent drift, both succeed in revising the plan. However, providing all contextual information at once distracts the LLM and induces hallucinations. This case demonstrates how enhance plan refinement in unpredictable scenarios,
adaptively selecting complementary contexts such as incomplete KG signals or L.LM hallucinations, without relying on manually predefined rules. Additional cases demonstrating how different strategies perform under varying conditions, along with comparisons to ToG and PoG and an analysis of recovered failure types, are provided in Appendix
Q: Who was the vice president of the President who attended Ramble Elementary School?
Retrieved Chains:
Next step relations:
Current plan:
depth
Context
Egg
EXPcresncniann provides
Thrught Nowr hare idestitied ecttty
"eudblieug of are rtsdent or graduse ofitaenia
Ramble Elementary
muDlo 6
Elemmnry School need detemaize who antity
Clinton
Adtics 2 bestteestty en tuttiissu slontts)
neducation Depth 2
Oiscrsttinn ( ciulbss gl klestay
Depth 1
Local
Lookahead
Global
Mixed
Revision
Inguti plan + current
Inpul: plan + carrent triplets step relations
Inputs plan + history retrieved chalsss
Inputa plan + whole KG chains
triplets
step rollations
Output:
Output:
Output:
Output:
Thought 3: In intiiooou of infora to
Thought 3: have identiiedd that Canton
Thuught 3: have adantiiee till
Thought di huse feand that Boradi Olaraa
Barack Oharaa
the entily atterded Rawr bie Blamentary School.
Cliecn is the entity who attended Ramille
was President.
President
Artion Seanchiftardde Ohamaviio
Hementory School.
fider.
proslient
Action ScSarchiBB Clissss vice pecsilene)
Action ScarchiBil Cliston vice presiden))
Action 3o Ftashhjpe (iame))
Predict Joe Biden X
Predict answer: Al Gore V
Predict answer: All Gore V
Predict answer: Joe Riden
X
Attention
8098
3000e
5001
Figure 4: Case comparison of revision behavior across context strategies and an mixed input.
5
RELATED WORK
5.1 LLM-BASED AGENTS
LLM-based agents have become prominent paradigm for reasoning and decision-making framing complex tasks as sequential interactions between planning, observation, and action. Early approaches such as ReAct Yao et al. 2023) integrate chain-of-thougle reasoning with tool use, enabling stepwise interaction with external environments. Subsequent frameworks extend this paradigm
various domains, such as web-based QA (Nakano et al. 2021), multimodal reasoning (Yang et al.) 2023). social simulation (Park et al. 2023) and maths problem (Lei et al.. 2024 Chen et al. 2025). However, these approaches lack mechanisms to learn from feedback and remain heavily dependent on the underlying LLM backbone. Therefore, researchers have incorporates self evfluevaleteed feedback (Shinn et al. 2023 Yao et al.] [023] Madaan et al., 2023 Panickssery et al., (024) and external retrieval feedback (Jin et al. (025) into the reasoning loop to enhance LLM reasoning. In parallel, Monte
Carlo Tree Search (MCTS) agents have been introduced to sample and select from multiple reasoning trajectories for robust decision-make makinng (Hao et al.] 2023) Hu et al., [225 [Luo et al., 2025
Sun et al. (025).. However, relying on unverified external feedback often introduces noise and factual gaps, increasing the risk of hallucinations during reasoning.
5.2 KG-ENIIANCED LLM REASONING
To enhance the reliability of LLM reasoning, recent studies have incorporated KGs as structured external sources. We summarize representative KG-enhanced approaches in Table which broadly focus on three key aspects: planning, retrieval, and verification. Planning-focused methods such as RoG (Luo et al.] (024b) and KG-Agent UJiag et al. 2024) enhances the planning capabilities of LLMss by generating structured reasoning paths over KGs. While effective initially, such plans

---

Published as a conference paper at ICLR 2026
fixed once generated and cannot adapt to new evidence, leading to error accumulation in multi-hop hop inference. Retrieval-focure methods aim to improve the quality of KG evidence provided to the LLM. For example, KnowGPT Zhang et al. 2024 applies reinforcement learning for knowledge extraction, KG-CoT (Zhao et al. 2024) retrieves high-quality multi-hop subgraphs with a graph reasoning model, and ToG (SUN et al. 2024) adopts LLM agent to perform iterative retrieval.
Building upon these, PoG (Chen et al. 2024) incorporates planning with iterative retrieval to better coordinate evidence gathering and reasoning.
Despite these advances, the above methods either lack explicit verifi- cation mechanisms or perform only global verification after completing the entire reasoning process. To address this gap. KD-CoT (Wang) et al. 2023b) introduces a retriever- reader-verifier pipeline that verifies the factual consistency of final an- swers against KG evidence. While promising, their verification serves only as a passive check, providing a final validation that does not influence or revise subsequent reasoning steps. As a result, errors in earlier steps can propagate without correction. While PoG (Chen et al. (024) introduces correction the stepwise level, focus remains on refining local retrieval rather than the entire trajectory. Without incorporating explicit stepwise adjustment, these methods overlook the assurance of the correctness and coherence of the full reasoning process.
Table 4: Comparison of recent KG-enhanced LLM reasoning methods from three perspectives.
Method
Plan
Retrieve Verify
RoG (Luo et al.
2024b
x
KnowGPT (Zhang ct al
2024
X
V
x
KG-Agent (Zhao al. 2024]
V
x
KD-COT [Wang aL.
20236
V
ToG (SUN et al.
2024
X
PoG (Chen el al.
2024
X
VoG (Ours)
V
CONCLUSION
In this paper, we propose Verify-on-Graph (VoG), a unified framework that advances trustworthy LLM reasoning by by coupling planning, retrieval, and verification into a closed-loop process over KGs. Specifically, VoG treats L.L--generaed reasoning plans as tentative and refines them by detecting and correcting potential hallucinations that arise during multi-hop reasoning. Unlike prior frameworks that lack intermediate factual checking and adaptive revision, VoG enables stepwise verification and broader context integration at each step. Our experiments demonstrate that VoG significantly improves reasoning accuracy, robustness, and efficiency across multiple benchmarks, and generalizes well across LLM backbones without requiring additional training.
ETHICS STATEMENT
The research conducted in this paper adheres the ICLR Code of Ethics in every respect. Our study focuses on enhancing the reasoning reliability of large language models by incorporating stepwise verification with knowledge graphs. As the framework does not involve human subjects, private data, or Nomain-specific sensitive material, it raises no immediate concerns regarding privacy, safety, or security, All experiments are conducted on publicly available benchmarks, which contain no personal or sensitive information, and we strictly comply with their licenses and intended use.
REPRODUCIBILITY STATEMENT
The paper fully discloses all the information needed to reproduce the main experimental results of the paper to the extent that affects the main claims and conclusions. We provide our experimental results in Section 4 and an anonymous code repository with detailed instructions for reproducing them is referenced in the main text and also included in the supplementary materials. Detailed implementation notes and access to the models used in our framework are given in Appendix B.3 All datasets used in experiments standard public benchmarks, with details described in Appendix As our framework training-fret free, no model checkpoint is required, and reproducibility is ensured through the provided code, dataset references, and documented procedures.
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGMENTS
Lei Chen's work is supported by National Key Research and Development Program of China Grant No. 2023YFF0725 100, National Science Foundation of China under Grant No. U22B2060, Guangdong- Hong Kong Technology Innovation Joint Funding Scheme Project No. 2024A0505040012, AOE Project AoE/E-603/18, Theme-based project TRS T41-603/20R, CRF Project C2004-21G, Key Areas Special Project of Guangdong Provincial Universities 2024ZDZX 1006, Guangdong Province Science and Technology Plan Project 2023 HK CMCCiGuungzhou Branch) Metaverse Joint Innovation Lab under Grant No. P00659, Hong Kong ITC TC-SKI.CCC22EEGII ITF grant PRP/004/22FX, Zhujiang scholar program 2021JC02X170, HKUST Webank joint research lab. Jiachuan Wang's work is supported in part by JST CREST (JPMJCR22M2), Yongqi Zhang's work is supported by Guangdong Basic and Applied Basic Research Foundation Guangdong Province Project 2024QNI CONQNIIX088. IX088, Guangzhou Science and Technology Planning Project 2025A03J4491.
REFERENCES
Daya Guo, Dejian Yang. Haowei Zhang, Junxiao Song, Ruoyu Zhang, Runxin Xu, Qihao Zhu, Shirong Ma, Peiyi Wang, Xiao Bi, and et al. Deepseek-rl: Incentivizing reasoning capability in IIms via reinforcement learning, 2025. URL http:: owweiiiv.rrr/reee wttp:/aaa//...112/0000
OpenAl. Gpt-4 technical report, 2023.
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))1-38 March 2023. ISSN 1557-7341, doi: 10. 14533571730 URL
httt:://xx.daa
httt:://x..do..co /1T.////....13137171.1.1
Yejin Bang, Samuel Cahyawijaya, Nayeon Lee, Wenliang Dai, Dan Su, Bryan Wilie, Holy Lovenia, Ziwei Ji, Tiezheng Yu, Willy Chung, Quyet V. Do, Yan Xu, and Pascale Fung. multitask, multilingual, multimodal evaluation of chatgpt on reasoning, hallucination, and interactivity. ArXiv, abs/2302.04023, 2023. BtLhttps::// /ppi. semanticscher Lar www.aaa..rrooooo.oor1 256662612
Kurt Bollacker, Colin Evans, Praveen Paritosh, Tim Sturge, and Jamie Taylor. Freebase: collabora- tively created graph database for structuring human knowledge. In Proceedings of the 2008 ACM SIGMOD international conference on Management of data, pages 1247-1250. 2008
S. Auer, Christian Bizer, Georgi Kobilarov, Jens Lehmann, Richard Cyganiak, and Zachary G. Ives. Dbpedia: A nucleus for a web of open data. In ISWC/ASWC, 2007. URL https
Fabian M Suchanek, Gjergii Kasneci, and Gerhard Weikum. Yago: core of semantic knowledge. In Proceedings of the 16th international conference on World Wide Web, pages 697-706, 2007.
Garima Agrawal, Tharindu Kumarage, Zeyad Alghamdi, and Huan Liu. Can knowledge graphs reduce hallucinations in llms?: A survey, 2024. URL Btt.hhtpss//aarri..rr///////////
Yu Wang, Nedim Lipka, Ryan A. Rossi, Alexa F. Siu, Ruiyi Zhang, and Tyler Demr Knowledge graph prompting for multi-document question answering. AAAI Conference on Artificial Intelligence, 2023a. UtL
prg//Corpus 0766777
Shirui Pan, Linhao Luo, Yufei Wang, Chen Chen, Jiapu Wang, and Xindong Wu. Unifying large language models and knowledge graphs: roadmap. IEEE Transactions on Knowledge and Data Engineering, 36:3580-3599, 2023. URL http:p::/aap...mmttiicccceeeeeee
CorpusID:2591655:
Jorge Pérez, Marcelo Arenas, and Claudio Gutierrez. Semantics and complexity of sparql. ACM Transactions Database Systems (TODS), 34(3):1-45, 2009.
11

---

Published as a conference paper at ICLR 2026
Haoran Luo, Haihong E, Zichen Tang, Shiyao Peng. Yikai Guo, Wentai Zhang, Chenghao Ma, Guanting Dong, Meina Song, Wei Lin, Yifan Zhu, and Anh Tuan Luu. ChatKBQA: A generate- then-retrieve framework for knowledge base question answering with fine-tuned large language models. In Lun-Wei Ku, Andre Martins, and Vivek Srikumar, editors, Findings of the Association Bangkok, Thailand, August 2024a. Association for Computational Linguistics. doi: 10. 11286//1122224444 findings-acl.I URL https //aclanthology org 2024. findings acl. 122/
for Computational I Linguistics: ACI. 2024, pages
Tianle Li, Xueguang Ma, Alex Zhuang, Yu Gu, Yu Su. and Wenhu Chen. Few-shot in-context learning for knowledge base question answering, 2023. URL
2305. 01750
Linhao Luo, Yuan-Fang Li, Gholamreza Haffari, and Shirui Pan. Reasoning on graphs: Faithful and interpretable large language model reasoning, 2024b. httpttta/aaxxi..oooo owg.abb..rrg//b.//..
03100010061
Yu Gu, Xiang Deng, and Yu Su. Don't generate, discriminate: A proposal for grounding language models to real-world environments. In Annual Meeting of the Association for Computational Lin- guistics, 2022. URL httphttp::/ /api. semant cscho ar. org/ Ltrg//oor Corpus ID: 254853929
Qinggang Zhang, Junnan Dong, Hao Chen, Daochen Zha, Zailiang Yu, and Xiao Huang. Knowgpt: Knowledge graph based prompting for large language models, 2024. URL htttts://axxxt
htt//bb//3312 06185
Ruilin Zhao, Feng Zhao, Long Wang, Xianzhi Wang, and Guandong Xu. Kg-cot: Chain-of-thoughh prompting of large language models over knowledge graphs for knowledge-awand question answer- ing. In Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence (IJCAI-24), pages 6642-6650.. International Joint Conferences on Artificial Intelligence, 2024.
Keheng Wang, Feiyu Duan, Sirui Wang. Peiguang Li, Yunsen Xian, Chuantao Yin, Wenge Rong, and intensive Zhang Xiong. Knowledge-oe driven cot: Exploring faithful reasoning in llms for knoeledge-intensivee question answering. arXiv preprint arXiv:2308.132553 2023b.
Yilin Wen, Zifeng Wang, and Jimeng Sun. Mindmap: Knowledge graph prompting sparks graph of thoughts in large language models, 2024. Ut//sttps://arxx..ooo org/ abs aww//308.... 097299
Michihiro Yasunaga, Hongyu Ren, Antoine Bosselut, Percy Liang, and Jure Leskovec. Qa-gnn: Reasoning with language models and knowledge graphs for question answering, 2022. URL
https://erxiv. wwtp
J SUN, C XU, I. TANG, et al. Think-on-graph: Deep and responsible reasoning of large language model on knowledge graph [a/ol]. arxiv, 2024 [2024-07-08) 2024.
Xiang Huang, Sitao Cheng, Shanshan Huang, Jiayu Shen, Yong Xu, Chaoyun Zhang, and Yuzhong Qu. QueryAgent: A reliable and efficient reasoning framework with environmental feedback based self-correction. In Lun- Wei Ku, Andre Martins, and Vivek Srikumar, editors, Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages
Bangkok, Thailand, August 2024. Association for Computational Linguistics. doi: 10. 2024. 2024.ac1-110 long. 2747
www.annnthooyoooooomo URL httpt://p/:/ccccc http:pp://accclaaiooooooo.oorrrp org/
Jinhao Jiang. Kun Zhou, Wayne Xin Zhao, Yang Song, Chen Zhu, Hengshu Zhu, and Ji- Ji-Rong Wen. Kg-agent: An efficient autonomous agent framework for complex reasoning over knowledge graph, 2024. /ttppttss:///axxtt http://axxvvv.og/aa///aaaa//////
11163
Xinyan Guan, Yanjiang Liu, Hongyu Lin, Yaojie Lu, Ben He, Xianpei Han, and Sun. Mitigating large language model hallucinations via autonomous knowledge graph-based retrofitting. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 18126-18134, 2024.
Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik Narasimhan, and Yuan Cao. React: Synergizing reasoning and acting in language models, 2023, URL https:: //arxiiv org/abb/ /210 03629
12

---

Published as a conference paper at ICLR 2026
Liyi Chen, Panrong Tong, Zhongming Jin, Ying Sun, Jieping Ye, and Hui Xiong. Plan-on Can-on-graph. Self-correcting adaptive planning of large language model on knowledge graphs. arXiv preprint arXiv:2410.23875. 2024.
Nils Reimers and Iryna Gurevych. Sentence-bert: Sentence embeddings using siamese bert-networks. In Proceedings of the 2019 Conference Empirical Methods in Natural Language Processing. Association for Computational Linguistics, 2019. URL http: http://axxvv.v/ cww.aiivrrrrgoooo org/ abs /1908
10084
Pengcheng He, Xiaodong Liu, Jianfeng Gao, and Weizhu Chen. Deberta: Decoding-enhanced bert with disentangled attention. In International Conference Learning Representations, 2021. URL
httpps://gpenreveee...tt ftt.:/oormmmiddee XPaaadddddttIaatss
Emilie Kaufmann, Olivier Cappé, and Aurélien Garivier. On bayesian upper confidence bounds for bandit problems. In Artificial intelligence and statistics, pages 592-600. PMLR, 2012.
Lorenz Kuhn, Yarin Gal, and Sebastian Farquhar. Semantic uncertainty: Linguistic invariances for uncertainty estimation in natural language generation. ArXiv, his/2302.09666i 2023. URL.
https://app www.etetiiio. cccho ar. www.oor//ooooooooo 15:033322055000
Yuan Sui, Yufei He. Tri Cao, Simeng Han, and Bryan Hooi. Meta-reasoner; Dynamic guidance for
optimized inference-time reasoning in large language models. ArXiv, abs/2502. 199111992.999,, 2025. URL
https://api. sementicschol ormeeeriiicccoo....oooooooooopop ottp://h.......ooo/ooooooa/////a /t
Lianmin Zheng, Wei-Lin Chiang. Ying Sheng, Siyuan Zhuang, Zhanghao Wu, Yonghao Zhuang, Zi Lin, Zhuohan Li, Dacheng Li, Eric P. Xing. Haotong Zhang, Joseph Gonzalez, and Ion Stoica. Judging llm-asaajuude with mt-bench and chatbot arena. ArXiv, abs/2306.05 05665, 2023. URL https: api. www.etttttnncchooe....... ptt.e//wwsccccciooa..oooooorropr
Alon Talmor and Jonathan Berant. The web as knowledge-baas base for answering complex questions. arXiv preprint arXiv: 000.00643, 2018.
Wen-tau Yih, Matthew Richardson, Christopher Meek, Ming- Wei Chang, and Jina Suh. The value of semantic parse labeling for knowledge base question answering. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), pages 201-206, 2016.
Jonathan Berant, Andrew Chou, Roy Frostig, and Percy Liang. Semantic parsing on Freebase from question- -answor pairs. In David Yarowsky, Timothy Baldwin, Anna Korhonen, Karen Livescu, and Steven Bethard, editors, Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, pages 1533- 1544, Seattle, Washington, USA, October 2013. Association for Computational Linguistics. URL /eLLtttps://aeeaahoooooyy 1111111111
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 33:1877-1901, 2020.
Harsh Trivedi, Niranjan Balasubramanian, Tushar Khot, and Ashish Sabharwal. Interleaving retrieval with chain-of-thought reasoning for knowledge-intensive multi-step questions, 2023. URL https
//aaxiv.org/aaaaela...aa wttpor//aabb///.aae 10509
Donghan Yu, Sheng Zhang, Patrick Ng, Henghui Zhu, Alexander Hanbo Li, Jun Wang. Yiqun Hu, William Wang, Zhiguo Wang, and Bing Xiang. Decaf: Joint decoding of answers and logical forms for question answering over knowledge bases, 2023. URL htttt:://arxiiiooorrrr
2210..00 00063
Jinhao Jiang, Kun Zhou, Wayne Xin Zhao, and Ji-Rong Wen. Unikgqa: Unified retrieval and reasoning for solving multi-hop question answering over knowledge graph. arXiv preprint 1rXiv:22/2.00959, 2022.
Costas Mavromatis and George Karypis. Gnn-rag: Graph neural retrieval for large language model reasoning, 2024. URL htt.h:t/p/::arrtt wwwp://wwwrr//////eeeeoooo /2405. 20139 20139
13

---

Published as a conference paper at ICLR 2026
Mufei Li, Siqi Miao, and Pan Li. Simple is effective: The roles of graphs and large language models in knowledge-grang based retrentll-augmented generation. 2025. URL hattps://arxiv...
abs 02t5/21002222 20724
Qwen Team. Qwen2.5: party of foundation models, September 2024. URL htttp:://ttee...// Bttchub.c/blo///// qwtp:///wen.../.
Denny Vrandečić and Markus Krötzsch. Wikidata: a free collaborative knowledgebase, Commun. ACM,57(10)788888 September 2014. ISSN 0001-0782. doi: 10. 10.1145/2629489. URL https:
Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc Le, Ed Chi, Sharan Narang. Aakanksha Chowdh- cry, and Denny Zhou. Self-consistency improves chain of thought reasoning in language models. arXiv preprint arXhv2223.11171,, 2022.
Reiichiro Nakano, Jacob Hilton, Suchir Balaji, Jeff Wu, Long Ouyang, Christina Kim, Christopher Hesse, Shantanu Jain, Vincet Kosaraju, William Saunders, et al. Webgpt: Browser-assister question-answering with human feedback. arXiv preprint arXiv: 0222//2..9332 2021.
Zhengyuan Yang, Linjie Li, Jianfeng Wang, Kevin Lin, Ehsan Azarnasab, Faisal Ahmed, Zicheng Liu, Ce Liu, Michael Zeng, and Lijuan Wang. Mm-react: Prompting chatgpt for multimodal reasoning and action. arXiv preprint arXiv:2303.1 /381, 2023.
Joon Sung Park, Joseph O' Brien, Carrie Jun Cai, Meredith Ringel Morris, Percy Liang, and Michael Bernstein. Generative agents: Interactive simulacra of human behavior. In Proceedings of the 36th anmual acm symposium on user interface software and technology, pages 1-22, 2023.
Bin Lei, Yi Zhang, Shan Zuo, Ali Payani, and Caiwen Ding. Maem: Utilizing multi-agen system for condition mining in solving complex mathematical problems. arXiv preprint arXiv:2404.04735, 2024.
Xinyan Chen, Renrui Zhang, Dongzhi Jiang, Aojun Zhou, Shilin Yan, Weifeng Lin, and Hongsheng Li. Mint-cot: Enabling interleaved visual tokens in mathematical chain-of-thouge reasoning, 2025.
URL httthhttp://xxiiii
org/ abs/ 2506. 05331
Noah Shinn, Federico Cassano, Edward Berman, Ashwin Gopinath, Karthik Narasimhan, and
Shunyu Yao. Reflexion: Language agents with verbal reinforcement learning, 2023. URL
pettps://arxinn http://aawd....rro////22000
Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao, Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang, Shashank Gupta, Bodhisattwa Prasad Majumder, Katherine Hermann, Sean Welleck, Amir Yazdanbakhsh, and Peter Clark. Self-refine: Iterative refinement with self-feedback, 2023. httph:tt:///// BRRLhhtpss//arrr...or/////////00
17651
Arjun Panickssery, Samuel R. Bowman, and Shi Feng. Lim evaluators recognize and and favor their own generations. ArXiv, 11tp/2444.13076, 2024. URL
CorpusID:2692533
Bowen Jin, Hansi Zeng, Zhenrui Yue, Jinsung Yoon, Serean Arik, Dong Wang, Hamed Zamani, and Jiawei Han. Search-rl: Training 1lms to reason and leverage search engines with reinforcement learning, 2025. URL (tttst: //ta://aaivvvvvi www.awwwww....aaaaaaaaaaaooeeeee abs 2503. 09516 6
Shibo Hao, Yi Gu, Haodi Ma, Joshua Jiahua Hong, Zhen Wang, Daisy Zhe Wang, and Zhiting Hu. Reasoning with language model is planning with world model, 2023. URL http::ttps/// //aariv////vvv/ org/abs/ 2305. 14992
Yunhai Hu, Yilun Zhao, Chen Zhao, and Arman Cohan. Mcts-rag: Enhancing retrieval-augmented generation with monte carlo tree search. arXiv preprint arXiv:2503.20757, 2025.
Haoran Luo, Yikai Guo, Qika Lin, Xiaobao Wu, Xinyu Mu, Wenhao Liu, Meina Song, Yifan Zhu, Luu Anh Tuan, et al. Kbqa-ol: Agentic knowledge base question answering with monte carlo tree search. arXiv preprint arXiv:2501. /8902 2025.
14

---

Published as a conference paper at ICLR 2026
ZhongXiang Sun, Qipeng Wang. Weijie Yu, Xiaoxue Zang. Kai Zheng, Jun Xu, Xiao Zhang, Song Yang. and Han Li. Rearter: ketrieval-augmenttd reasoning with trustworthy process rewarding. ArXiv, abs/2501.07861, 2025. URL httph:ttp//eat wttp://aaaacccccc..oo.oo.oooaaaa
2755159461
Peter Auer, Nicolò Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine Learning, 47:235-256 2002. httpsss:://// sew..iccccs...tt...ccc.cc....
Manuel Alejandro Borroto Santana, Bernardo Cuteri, Francesco Ricca, and Vito Barbara. SPARQL- QA enters the QALD challenge. In Xi Yan, Meriem Beloucif, and Ricardo Usbeck, editors, Proceedings of the 7th Natural Language Interfaces for the Web of Data (NLIWoD) co-located with the 19th European Semantic Web Conference (ESWC 2022), Hersonissos, Greece, May 29th, 2022, volume 3196 of CEUR Workshop Proceedings, pages 25-31. CEUR-WS.org. 2022. URL
http:::/ceurwww.org///e
Daniel Scott Himmelstein, Antoine Lizee, Christine Hessler, Leo Brueggeman, Sabrina L Chen, Dexter Hadley, Ari Green, Pouya Khankhanian, and Sergio Baranzini. Systematic integration of biomedical knowledge prioritizes drugs for repurposing. elife, 6:e26726, 2017.
Qiao Jin, Bhuwan Dhingra, Zhengping Liu, William Cohen, and Xinghua Lu. PubMedQA: A dataset for biomedical research question answering. In Kentaro Inui, Jing Jiang, Vincent Ng. and Xiaojun Wan, editors, Proceedings of the 2019 Conference Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLPP), pages 2567-2577, Hong Kong, China, November 2019. Association for Computational Linguistics. doi: 10.18653/11DDI/ 1259.. URL
BTG/D19-1259/
Anastasia Krithara, Anastasios Nentidis, Konstantinos Bougiatiotis, and Georgios Paliouras. Bioasq- qa: A manually curated corpus for biomedical question answering. Scientific Data, 10(1):170, 2023.
Jiashu He, Mingyu Derek Ma, Jinxuan Fan, Dan Roth, Wei Wang. and Alejandro Ribeiro. Give: Struc- tured reasoning of large language models with knowledge graph inspired veracity extrapolation, 2025. URLhttps: //ar://aaviv/////aaeeeaa http///ww...rg////////////////// a2/p///aaa//0.//. 08477
15

---

Published as a conference paper at ICLR 2026
APPENDIX
This appendix provides additional implementation details, experimental configurations, full prompt templates, ablation settings, and supplementary visualizations referenced throughout the main paper.
A FURTHER DETAILS OF VoG AGENTS
A.1 PRE-DEFINED SPARQL QUERY
For KG-based knowledge extraction, we use the following predefined SPARQL query templates to access facts from Freebase.
SPARQL: Relation Retrieval
Outgoing Relations:
PREFIX Shttp://rdf freebase com/ns/>
SELECT DISTINCT ?relation
WHERE
ns:mid Prelation ?x
Incoming Relations:
PREFIX ns: <http://rdf. freebase. com/ns/>
SELECT DISTINCT ?relation
WHERE Pn na:mid
SPARQL: Entity Search
(Chead, r, ?)
PREFIX ns: http:://.d....cca.......o com/n//>>>/
SELECT ?tailEntity
WHERE
ns: ns:mid ns:relation 2tailEntity
(2,r,
PREFIX ns: <http://rdf. www.base.eebbbbecoomoooom comnn/// SELECT ?tailEntity
WHERE ?tailEntity ns:relation ns:mid.
SPARQL: Entity Name Search
PREFIX no: <httpp//rdff fwe.base.com SELECT DISTINCT itailEntity WHERE
?entity destype.cbject. 2tailEntity FILTER(?entity ns:mid)
UNION
Pentity http:p//wwww.w..rg/220///////// sameess> Ptailentity
FILTER (fent ns:mid)
16

---

Published as a conference paper at ICLR 2026
At each reasoning depth VoG constructs structured KG queries based on the current action A from the reasoning plan SK6) These queries follow the pattern (Chead, P; ?) (? Ctail) and executed against the underlying KG. Entities from & and filtered relations from Reand are combined to form the query
A.2 ENTROPY-BASE BASED FILTERING
To reduce prompt length and eliminate noise from large candidate sets, we apply entropy-based filter- ing relation and entity candidates. Specifically, we first compute similarity scores between all candi- dates and set of suggested relations using pre-trained encoder mama cew-rrooobeeeeee -aare-baa-eee wws---aasseeeeeeeeeee -dotv5. For each candidate C E C, its weight is calculated as
W; = max (im(M T
(5)
where (.) denotes the encoding function and sim(;,-) the similarity measure.
We then normalize the weights via softmax:
exp(w:)
pi E, exp(wy))
(6)
and compute the normalized entropy over the distribution (p.):
E; Ps log(p:) log [C]
H Hmom
Using Hnom, adaptively determine the selection width is within bounds [kmins kmax]
max (kmin min ([kimin (kimax kmin)
Hauon! (CI)).
(8)
Finally, we select the top-k candidates ranked by their weights w; The detailed procedure sum- marized in Algorithm|] [ where the above equations correspond the respective steps of computing weights, normalizing via softmax, calculating entropy, determining adaptive width, and selecting candidates.
Algorithm 1: Einropy-Basse Relation (or Entity) Filtering
Input: Candidate set C (c...... ... ), Suggested relations R {ri, Fm Similarity encoder M, Width bounds [kming kmax]
Output: Filtered subset Cuetected
Encode all candidates and suggestions using encoder M:
Compute similarity scores w; in Equation equation 5
Normalize weights via softmax according to Equation equation Compute normalized entropy Hnam as per Equation equation Compute adaptive width & following Equation equation g
Select top-k candidates Cselected by weights w;:
return Cselected
17

---

Published as a conference paper at ICLR 2026
A.3 PROMPT TEMPLATES
A.3.1 PLAN GENERATION PROMPT
Prompt Template: Plan Generation
You are an intelligent assistant tasked with answering the following question. Your job is to understand the question and plan all the necessary steps to solve it. Do not judge the question or give an unknown answer. You can only use the following two actions: (I) Search[[eyyorr]] To retrieve relative information based on the given question.
Instruction:
(2) Finish[Annse Answer]: When the observations are sufficient to answer the question, return the final answer and finish the task.
Few-shot examples
Inputs:
Question: { Q}
Output:Initial plan 5(4)
A.3.2
RELATION SELECTION PROMPT
Prompt Template:
Relation Selection
Instruction:
Please provide the relevant relations the question " (Q) " and suggested
relation in current action (A_t)".
Candidate Relations: {ri, 72, .... Tn
Few-shot examples
Output: (Relevant relations)
A.3.3 ENTITY SELECTION PROMPT
Prompt Template: Entity Selection
Based the question " (1) " and predicted observation " "(O_t choose the most plausible target entities.
Instruction:
Candidate Entities:
(e1, 62, ..., e,,
Few-shot examples
Output: (Entities)
A.3.4 VERIFICATION PROMPT
Prompt Template: Stepwise Verification
Instructions: You given set of knowledge triplets and LLM-generated reasoning step. Analyze whether it is necessary to revise the LLM's observation. Your response must be in valid JSON format including keys "Revise" and "Reason". If "Revise" " is "Yes", include a corrected "Revised Observation field. Predicted observation from LLM: () Knowledge Triplets: [] Few-shot examples
Output Format (JSON):
(
18

---

Published as a conference paper at ICLR 2026
"Revise": "Yes" or "No", "Reason": "...",
"Revised Observation": (only if "Yes")
A.3.5 REVISION PROMPT
Prompt Template:
Local Revision
You are provided with reasoning plan for the following question. Based the given context, revise the plan as needed to correctly answer the question. You can also adjust previous steps based on how the observation aligns with or contradicts existing steps.
Instruction:
Few-shot examples
Inputs:
Question: { Q)
Current plans: { (S(t=1))
Current observation: O,)
Output:Revised plan St
Prompt Template:
Global Revision
You are provided with a reasoning plan for the following question and a set knowledge graph (KG) triplets. The existing reasoning plan might have factual errors. Please revise the reasoning process completely from Thought I.
Instruction:
Few-shol examples
Inputs:
Question: ( Q)
Current plans: { (((-1))
KG triplets: O1:)
Output:Revised plan S(()
Prompt Template: Lookahead Revision
You are provided with a reasoning plan for the following question and future relations as reference. Based on the given context, revise the plan as needed to correctly answer the question.
Instruction:
Few-shot examples
Inputs:
Question: ( Q)
Current plans: { (s(t-)))
Lookahead relations: R )
Output:Revised plan st(
19

---

Published as a conference paper at ICLR 2026
Prompt Template:
Mixed input
You are provided with a reasoning plan for the following question, set knowledge graph (KG) triplets, and future relations as reference. Based on the given context, revise the plan as needed to correctly answer the question.
Instruction:
Few-shot examples
Inputs:
Question: { QQ
Current plans: { ()(()))
Lookahead relations: R++1)
KG triplets:( O
Output:Revised plan S(O)
B DETAILS OF CONTEXT SELECTOR
B.1 ALGORITHM AND BONUS FORMULATION
Our selection is performed via modified UCB algorithm that incorporates reward-driven updates and KG-aware priors, as shown in Algorithm 2 (UCB) algorithm incorporate domain-specific priors for KG reasoning. Specifically, for each context-selection strategy E C, the score at step computed as Eq. (2) in Section 3.4 where each additional bonus defined below.
We extend the classical Upper Confidence Bound
Entropy-aware Bonus. To encourage global planning under high answer uncertainty, we define bonus term based the entropy H, of the answer distribution step
Bunl H+) = dent [lamglabal a (a ( b))
where H, the normalized entropy of the current answer distribution. The sigmoid function (zz) = Ite-r ensures smooth transition of reward scaling. Constants 6 and b 0.5 control the steepness and center of the response curve, respectively.
KG-aware Bonus To prevent inefficient exploration due over-deep search or entity redundancy, we incorporate KG-aware penalty term that discourages excessive reasoning depth and repeated use of entities:
BRa Ecep) = AKG [emgloball (6 Exop) - Io=okhhae tanh
-41 ) Ta
(10)
Here, c E {lookahead, global} denotes the current strategy, t is the current reasoning depth, and Ta is the expected maximum depth. The binary variable Exep {0, 1} indicates whether the retrieve agent revisits a previously retrieved entity and results in a loop. The constants and н control the penalty strength for repeated entities and the steepness of the depth-based penalty curve, respectively. In our experiments, we set = 0.2 and x 4. The indicator function I.-.. activates the corresponding bonus based the selected strategy.
Strategy Diversity Penalty. To avoid excessive reliance on a single context strategy, we incorporate diversity-based penalty term that discourages repetitive selection. This computed based on the number of times each strategy has been chosen within the past & revision steps:
Bar (c)
(c) da count+(c)
(11)
where count (c) denotes the number of times strategy c has been selected in the last i: steps. We apply a strategy-speciffe coefficient X(c) where e [Local, Lookahead, Global]. allowing differentiated regularization strength depending on the relative risk of overuse for each strategy.
20

---

Published as a conference paper at ICLR 2026
Algorithm 2: KG-Aware Context Selection via Modified UCB
1: Input: Strategy set C {Local, Lookahead, Global). initial plan steps T, expected depth Ta
Initialize: N[c] 0, R(cc 0, count, [c] 0, N
0, P 0;
3: for t to do
4: Compute entropy H,, and normalized depth de t/Ta:
5: while 1/2 reward_jhreshop do
6: foreach c E C do
7:
if N then
Score|c] +00; continue end
Ensure initial exploration
10:
Compute (CB,(c) using Eq.
// Context-aware bonus terms:
// (Ht) from Eq.
// (k, from Eq 10
// (ai from Eq.
Score/c| + UCB:(e); end
G f- arg max Score(c]:
// Select best context strategy
Generate revised plan S using cz
16:
PU
// Append revised plan to candidate pool
Compute reward v using Eq.
18:
Update::
R[c.] +- R[e,] + 14;
N(ca] t- N(ce] +1, N N 11
20:
count, [ce] +- county [c,] +1;
end
23:
< (Sn
// Update plan length after success
24:
end
B.2
TASK-SPECIRE REWARD
We define the task-specific reward Mocal as a weighted aggregation of five interpretable metrics, each designed capture different aspects of reasoning quality at step These metrics jointly assess factual accuracy, semantic relevance, and reasoning efficiency, based on the alignment between the revised plan s(0,, the question Q, and the knowledge graph feedback O,,
Validation: Measures the factual correctness of the predicted observation Pred_O. using contradiction classifier. Specifically, we employ the DeBERTa - -aarge Marge-MMLI MNLI model to assess whether the prediction contradicts aligns with the KG feedback. Additional penalties applied for degenerate outputs such as "none," "unknown," or empty spans.
Quality: Evaluates the semantic relevance between the predicted observation Pred_O. and the input question Q
Question Alignment: Measures the overall coherence of the reasoning step ((1) with respect the original question Q. This is computed via embedding-level similarity to ensure that each revision remains question-centric.
Penalizes redundancy across reasoning steps by comparing the semantic similarity of the current thought 8; with all previous thoughts 81:-11 High overlap in meaning reduces the reward, encouraging non-redundant, progressive reasoning.
Efficiency:
Thought Coherence: Assesses whether the current reasoning step is adequately grounded in the KG feedback O, We calculate the similarity between the step's "Thought" component and the KG observations using the same embedding model.
For all similarity-based metrics, we compute cosine similarity between sentence embeddings obtained from pretrained model (mama rco-be -wweert---s--eee
21

---

Published as a conference paper at ICLR 2026
B.3 IMPLEMENTATION DETAILS
B.3.1 HYPERPARAMETEE SETTINGS
We summarize below the hyperparameter settings used in our context selection and reward computa-
tion modules.
For the JCB-based strategy selection, we use an exploration coefficient of a = 1.4 to balance the trade-off between exploration and exploitation. With regard the three context-aware bonus terms, we adopt default values based on practical intuition rather than extensive search. Specifically, the aatropy-based bonus is scaled by Aent = 0.1, encouraging exploration under high uncertainty. The KG-based redundancy penalty is set with λkG 0.1, discouraging repetitive overly deep retrieval. For the diversity bonus, we assign strategy-specific coefficients X = (0.05, 0.1, 0.2) for the Local, Lookahead, and Global strategies respectively, reflecting varying tolerance for repetition. To evaluate the impact of these weights, we further perturbed them by =00% and observed only marginal changes in accuracy (S 1.2%) and stable strategy distributions in Appendix E.5 confirming that VoG's performance is robust to hyperparameter variation.
The expected reasoning depth is set to Ta 5 for CWQ, and T. = 3 for both WebQSP and WebQues- tions, reflecting the variation question complexity and the structural depth of their corresponding knowledge graphs. For instance, CWQ typically requires longer and more compositional reasoning plans compared to WebQuestions. In reward aggregation, we use an entropy-based interpolation factor 3 = 0.4 for CWQ, and 0.2 for both WehQSP and WebQuestions, control the weighting between task-specific and confidence-ben
reward components. The final plan selection threshold is 0.73 for CWQ and 0.77 for the other two datasets, tuning the sensitivity of plan acceptance to dataset-specific characteristics. Above task-specific values were chosen based on the average plan lengths observed from small sample of development questions, and no further tuning was performed.
B.3.2 EXPERIMENT SETTINGS
In our experiments, we evaluate VoG using three different language models: GPT-3.5 and GPT-4 accessed via the OpenAl And Qwen2.5, which is deployed locally We the temperature 0.3 to reduce generation randomness, and restrict the maximum number of generation tokens to 1024 across all experiments for consistency. The experiments are conducted on an NVIDIA A800 GPU server.
C DATASETS
We evaluate our method on three widely-used knowledge graph question answering (KGQA) bench- marks: ComplexWehie WebQuetton (Talloor and Berant) (018). WebQSP (Yih et al. 2016). and WebQuestions (Berant et al., (2013). All datasets are constructed on the external knowledge graph from Freebase Freebase(Bollackr al.] (2088) and require multi-hop reasoning reach the answer. The statistics of the datasets used in this paper are shown in Table
Table 5: Dataset statistics.
Dataset
Answer Type
Train
Test
WeeQusttos
Entity
27,734
3,531
WebQSP
Entity Number
3,098
1,639
WebQuestions
Entity/Number
3738
2,032
D BASELINE DESCRIPTIONS
We compare VoG against three categories of baselines:
httos://platformm openai wwwpnai.comm.aeeeeeeooooooo.oooe /ccs
https://huggingffaee co//wen
22

---

Published as a conference paper at ICLR 2026
D.1 LLM-ONLY BASELINES
These methods test the inherent reasoning capabilities of LLMs without external knowledge.
I0 Prompting (Brown et al. 2020): This approach performs few-shot prompting using
direct input-output examples without any intermediate reasoning steps.
Chain-of- Chain-of-Thought (CoT)) (Trivedi et al. 2023): It generates intermediate reasoning chains that help the model arrive at more accurate final answer.
Self-Consistency (SC) (Wang et al. 2022 This method samples multiple CoT reasoning
chains and selects the most consistent final answer through majority voting.
D.2 FINE-TUNED METHODS
These methods incorporate KG information via supervised learning fine-tuning strategies.
UniKGQA (Jiang et al. 2022) unifies KG path retrieval and reasoning by introducing
pre-training objective based on question-relation matching, enabling shared representation
learning.
2023) linearizes the knowledge base into text-like sequences and retrieves relevant subgraphs using text-based retrieval. It jointly generates both logical forms and direct answers, combining the strengths of symbolic and generative reasoning.
DECAF (Yu
KD-CoT [Wang et al. 2023b) introduces a retrieval-aug aetreeval-uugmented CoT framework, where an LLM queries retriever for external knowledge and refines its reasoning chains based on returned answers, improving accuracy and credibility.
RoG (Luo et al. 2024b) employs fine-tuned LLM to generate reasoning plans based on the KG. These plans guide the retrieval of faithful evidence from the KG, improving the factual alignment of the reasoning process.
KG-Agent (Zhao et al. 2024) uses a fine-tuned planner within a lool-augmented agent framework, enabling iterative interaction with KG APIs for multi-hop question answering.
GNN-RAG (Mavromatis and Karypis 2024) employs lightweight graph neural networks score nodes and their neighborhoods based on question relevance, enabling effective retrieval over long-range KG contexts.
SubgraphRAG (Li et al. 2025) employs a lightweight MLP with parallel triple-scoring and directional distance encoding to efficiently construct flexible subgraphs tailored to each query and model capacity.
D.3 AGENT-BASED KG-AUGMENTED METHODS
These methods utilize LLMs as agents to guide reasoning over KGs through prompting, without requiring fine-tuning.
ToG (SUN et al. 2024) treats an LLM as a agent that performs beam search over the KG. iteratively expands and scores candidate paths to discover the most promising reasoning trajectories.
PoG (Chen al. 2024) decomposes the input question into structured subgoals, which then used to guide step-by step-by-step retrieval and reasoning. Additional memory and reflection mechanisms are introduced enhance coherence and accuracy.
We emphasize that VoG a model-agnostic framework that does not require fine-tuning, and is directly compatible with both open-source and proprietary LLMs.
E ADDITIONAL ANALYSIS AND ABLATION STUDY
this section, we provide a deeper ablation to further examine the behavior and effectiveness the proposed VoG framework beyond the main experimental results. All experiments conducted with GPT-3.5 for consistency. Together, these ablation studies offer fine-grained insights into how each design choice contributes to VoG's overall accuracy, robustness, and efficiency.
23

---

Published as a conference paper at ICLR 2026
E. REVISION SIGNAL ANALYSIS
To better understand the distribution and necessity of revision across reasoning steps, we analyze how often the verification module flags reasoning steps for revision. We compare the revise signals generated by the LLM-based verifier (GPT-3.5) and lightweight PLM-based verifier (e.g.. DeBERTa- based NLI model(He al. 202I)). Figure visualizes the distribution of revision signals across three datasets, segmented by the source of verification. The outer ring distinguishes between samples that triggered revision signal and those that did not, while the inner ring further breaks down the revision-triggenie cases into those suggested exclusively by the LLM verifier, the PLM verifier, or by both. This visualization highlights the complementary nature of the two verifiers, as well as the relative proportion of agreed versus disagreed signals.
Revision Signal Distribution
WebQSP Revision Signal Distribution
Webquestions
Signal Distribution
DN1
LLM only 236 1ha
LUM (0
Dechte (110 A4
PER 1nty ON!
only
Ber 126.2%
133 (154
Beth (2--
Pralii (12.5)
Reu 294]
Figure 5: Distribution of revision signals across datasets. The outer ring shows the overall proportion of examples requiring revision, while the inner ring indicates the source of the revision signal (LLM only, PI.M only, both).
E.2 DETAILED EFFICIENCY ANALYSIS
To provide finer-grained view of efficiency, we further analyze the token usage distribution across different stages of VoG. Specifically, we separate the tokens consumed by planning, retrieval, verifi- cation, and revision, and report their proportions relative to the total tokens. Figure 6 presents the results on CWQ and WebQSP with GPT-3.5, based on a representative sample of test data. We find that initial planning consistently accounts for only small fraction of the total tokens, whereas the relative costs of retrieval, verification, and revision vary across datasets.
cwQ Taken Usage by Stage
WebQSP Taken Usage by Stage
Inter
Porta
10.%
Pereet
2222
Figure 6: Stage-wise token distribution of VoG on CWQ and WebQSP. Each slice shows the proportion of tokens consumed by initial planning, retrieval, verification, and revision relative to the total.
E.3 STRATEGY-LEVEL PERFORMANCE ANALYSIS
In contrast to the isolated strategy end-to-end comparison in Section 4.3 here we analyze the effectiveness different strategies under the adaptive MAB framework. We first compute the per- iteration revision success rate, defined the percentage of revisions that successfully correct
24

---

Published as a conference paper at ICLR 2026
initial error, considering only the instances where the prior plan's answer incorrect. As shown in Table [6 all three strategies show comparable revision success rates.
Table Revision success rates (%) for each strategy, computed as the proportion of revisions that successfully corrected an error in each attempt.
Strategy
CWQ
WebQSP
WebQuestions
Local
26.0
38.6
27.0
Lookahead
25.9
36.8
27.9
Global 26.1
33.6
28.5
Beyond evaluating whether a revision leads to a correct final answer, we additionally assess whether the model can correct incorrect intermediate reasoning steps by leveraging ground-truth truth SPARQL exe- cution paths. In this setup, we use GPT-3.5 to label each revised step as: (i) CORRECT, fully match- ing the gold reasoning path; (ii) IMPROVED, (iii) INCORRECT. Table//summrrizzz the proportions of CORRECT and CORRECT+IMPROVEL) steps for CWQ and WebQSP, indicating that the revision module successfully revises large majority of wrong intermediate steps.
improvement over originally incorrect step;
Table 7: Step-level correctness of revised reasoning steps using ground-truth SPARQL paths.
Metric
CWQ
WebQSP
CORRECT IMPROVED
85.21%
99.50%
CORRECT only
44.36%
83.25%
We then examine which strategy contributes to the correct answers produced under the MAB setting. Figure the proportion of correctly answered questions attributed each strategy, highlighting their complementary roles in the overall framework.
Accuracy per Strategy by Dataset
13.7%
Local Global
72.4%
Lookahead
30-
Accuracy
CWC
WeaQSP
WebQuestions
Figure 7: Strategy-specific answer accuracy under the MAB framework across three datasets. Each bar represents the proportion of correctly answered questions attributed to a given strategy.
E.4 ABLATION ON BONUS TERMS
We evaluate the contribution of each component in our KG-aware UCB scoring mechanism by conducting ablation studies on the CWQ dataset. Specifically, we consider three variants: (i) removing all KG-aware prior terms. (ii) removing only the diversity-awar bonus, and (iii) removing both. effectively reducing our scoring function to the standard UCB formulation (Auer et al. 2002). Table reports the performance degradation under each variant. The results demonstrate that incorporating
25

---

Published as a conference paper at ICLR 2026
KG-specific priors and diversity control leads to more effective context selection, ultimately enhancing reasoning accuracy.
Table 8: Ablation study of UCB bonus terms across datasets.
UCB Variant
CWQ
WebQSP
WebQuestions
Modified UCB (all bonuses)
64.7
83.2
63.0
w/o KG-aware priors
64.2
77.7
60.2
w/o Diversity
63.8
77.3
59.4
w/o both(UCB)
63.0
74.7
58.9
E.5 ROBUSTNESS MODIFIED UCB
To assess the robustness of our UCB formulation, performed perturbation analysis both the context-aware bonus terms and the exploration weight. Specifically, we perturbed the weights of these terms by +200. Across all perturbation settings, VoG consistently outperforms other GPT--3.--based baselines, with performance fluctuations remaining marginal ( 1.2% accuracy). These results confirm that our approach robust moderate changes in weighting. Tables ! and reportt the accuracy, average plan length, and average strategy counts under each perturbation for CWQ and WebQSP, respectively.
Table 9: Robustness analysis of context aware bonus weights on CWQ and WebQSP.
Weight Perturbation
Accuracy
Avg Plan
Avg Strategy Counts
Dataset
(%)
Length
(Local Lookahead / Global)
+20%
63.5
3.49
1.60 / 1.22 / 1.21
CWQ
-20%
63.6
3.52
1.59 / 1.21 / 1.15
0%%
64.7
3.62
1.69 / 1.26 / 1.22
+20%
82.4
2.76
1.35 0.83 / 0.70
WebQSP
-20%
83.2
2.78
1.34 / 0.81 / 0.66
0%
83.2
2.80
1.35 / 0.80 / 0.63
Table 10: Robustness analysis of exploration weights on CWQ and WebQSP.
Weight Perturbation
Accuracy
Avg Plan
Avg Strategy Counts
Dataset
(%)
Length
(Local Lookahead / Global)
+20%
64.3
3.53
1.65 / 1.32 1.16
CWQ
-20%
63.6
3.62
1.61 / 1.29 / 1.15
0%
64.7
3.62
1.69 1.26 / 1.22
+20%
82.4
2.73
1.36 / 0.86 / 0.79
WebQSP
-20%
83.3
2.79
1.33 / 0.84 0.61
0%%
83.2
2.80
1.35 / 0.80 / 0.63
E.6 ABLATION STUDY ON REWARD DESIGN
We conduct two sets of ablation experiments to evaluate the contribution of different reward compo- nents used in our MAB-based context selection.
Task-Specific vs. Confidence-Basee Reward. We first compare the performance of the task- specific reward and confidence-based reward terms of their ability to guide the selection of high-quality plans. Specifically, we report the accuracy of the highest-scoring plan from the full set of candidates P under each reward formulation. Note that this includes all plans proposed throughout the iterative reasoning process, regardless of whether they were ultimately accepted or discarded. As shown in Table II the confidence-burt reward generally achieves better performance, indicating a stronger alignment with answer correctness. Additionally, we compute the mean entropy of answer
26

---

Published as a conference paper at ICLR 2026
distributions aggregated over all revision steps. This metric captures the average level of uncertainty during reasoning across datasets. It important to distinguish this analysis from the actual decision process in our A-Bdd controller. During inference, the final answer is produced by the plan selected at the last revision step. Specifically, the one that exceeds the reward threshold and is chosen based dynamic strategy selection. In contrast, this ablation purely evaluates each reward's ability to assign higher scores to more accurate plans within the full candidate pool.
Table 11: Accuracy (%) of the plan selected by different reward methods, and corresponding answer entropy.
Reward Method
CWQ
WebQSP
WebQuestions
spec-s reward
56.5
75.9
59.1
Confidence reward
60.4
79.1
62.4
Entropy (avg.)
0.37
0.34
0.32
Component-wise Ablation of Task-Specific Reward. To understand the role of each component in the task-specific reward design, we perform a leave-one-our ablation study. As shown in Table [2] removing any individual component leads drop in accuracy, confirming the necessity of all five elements. These results highlight the importance of penalizing hallucinated or contradictory outputs and aligning the reasoning step with the input query.
Table 12: Ablation Accuracy (%)
Task Seeek-Speifcc Reward across Datasets
Setting
CWQ
WebQSP
WebQuestions
Full Reward
56.50
50.61
75.60
w/o Quality
52.41
49.47
71.45
w/o Thought Completion
52.66
49.82
70.35
w/o Efficiency
52.49
50.53
71.29
w/o Question Alignment
52.15
49.47
70.98
w/o Validation
51.13
48.07
68.61
E.7 TRADE-OFF ANALYSIS BETWEEN COMPLEXITY AND PERFORMANCE
This subsection provides a quantitative study of the trade-offs between model complexity and performance in the VoG framework. We examine several simplified variants of VoG to understand how individual components contribute to accuracy and computational cost. Specifically, we explore the effect of replacing the UCB with fixed local, global, and lookahead revision strategies, denoted as local revision, global revision, and lookahead revision, respectively, as well as substituting the verify agent with a PLM-only verifier. Table 13 reports the resulting accuracy changes, token usage differences, and the corresponding maximum LLM call complexity the CWQ dataset.
Table 13: Trade-off analysis of simplifications in VoG on CWQ dataset.
Simplification
AAce
Tooee Usage
Maximum LLM Call (Simplified / Full)
local revision
-4.6%
-25.0%
(1 + D(2kmax 2))/(1 + D(2kmax + +1+T)
global revision
-4.5%
-99.1%
(1 + D(2kmax + 2)) + D(2kmax +1+T))
lookahead revision
-1.1%
-21.1%
(1 + D(2kmax 2))/(1 + D(2kmaxx +1+T)
PLM-only verifier
-2.2%
22.1%
D(2kmax T))((1+ D(2k 1++T)
Note: is depth of reasoning plan, Kmax is maximum width given Algorithm and 7 is the revision times.
27

---

Published as a conference paper at ICLR 2026
F ADDITIONAL CASE STUDY
F.1 ADDITIONAL CASES
we also examine additional examples that highlight how different revision strategies become effective under different conditions. Figure presents two additional cases using Qwen2.5-7B. The upper case shows how future relations provide useful guidance to revise the plan, while the lower case demonstrates that they may instead introduce distraction. We also observe that the Local strategy often works well in earlier steps when explicit evidence is available and competing candidates exist, as in the lower case, where lightweight local correction prevents unnecessary detours.
Beyond the representative case analyzed in Section 4.5
Together, these examples highlight both the potential and risks of relying on broader context, further underscoring the importance of adaptive strategy selection. These examples further highlight the difficulty of predicting which context will be most effective, reinforcing the importance of dynamic strategy selection. We also note that although intermediate answers at non-terminal steps are not final outputs, their emrors can mislead subsequent reasoning and incur unnecessary computational cost.
Q1: What country bordering France contains an airport that serves Nijmegen?
Retrieved Chains
Next step relations:
Current plan:
Carrent
Context
portadl corcitediie
Euroge
Burone
Thought seed find out waich countries border Frunco contain port that Kijtsggnn bondering
France
Nethwrlorrls
sending hijmagon
Weeze
Nijmego
Weeze Airport
Obarvaliun (Mirnage locmted Nethedands). (htmmege,, located near, Nimnggen Airport)
Germany
1epth1
2
Revision
Local
Lookahead
Global
Thought Nijmegen city Netherlands
Thought airport serving Nijmegen is Airport. lneed to deternine country whene Vireon Airport lncates Astion
Thought 21 Nijmegen cityis Netherfands which Burope, search Netherlands. Adtion Smarch [Nethorlsnds)
lnzed to seardi airport Notherlands. Action Sownchf (ieeheiinerr))
Search (Weraar sirport]
Predict answer er: Netherlands
Predict answer: Germany
Predict answer: Netherlands
X
Q2: Which of team owners Tom Hicks sports team the American League West?
Retrieved Chains:
Next step relations:
Current plan:
Carrentdepth
Context
Tom Hicks
sytril beard
TessEs Ranpers
Lengue Weet
Thought 1: Identity the teans in the America
frankadd cnverie souee
Angulis Angels of Anshetm
sports, toor
Airte
Action l: Searchihnericn league Westteans]
Marenn
Obsrrvation "[tos Angeles Angele member of American Lengue West. (Ouillan
American League West
"Sattle"
sagir Wert
m.Dertd21
Martiners
Finisk(Oalladdd Abhick]
Revision
Local
Lookahead
Global
Thought 2: have identried that Tom Hicks
Thought have identified that Los Angeles Angels of Amslsii and in firtu2i members the American
Thought 2: Tom Hicks owes the Tous Ringers.
owns the Tieas faagers, which are the American West.
Thnaes Ranger indeed mumbers the American League West.
West
Action Firtish (leash
Action Search(Los Angeles Angels Anahetm, m.Dorddi1)
Action Pintshh (lesss Rangen)
Predict answer: Texas Rangers
V
Predict answer: Los Angeles X
Predict answer: Rangers
Angels of Anaheim
Figure 8: Additional two case studies with Qwen2.5-7B, illustrating how different revision strategies become effective under different conditions.
F.2 CASE COMPARISON WITH BASELINES
While Section 4.5 presents a strategy-level case study highlighting VoG's internal context selector, here provide complementary example comparing VoG against two external agent-based basclines, ToG and PoG. Figure 9 illustrates the question, retrieved triplets, and intermediate reasoning process for each method. This example highlights how VoG's iterative verification and context-aware revision mechanisms help mitigate hallucinations and enable correction of intermediate errors.
Both ToG and PoG fail to produce the correct answer in this example, but for different reasons. ToG, which conducts beam search over KG triplets by prompting an LLM to score candidate paths, retrieves facts such as (France, location. cnnttioonocatioon www.looo.cooocooooooooo.o.o..o.o contaiiedn.n,,ied. Europe) and (Nijmegen, sccondlevedl _iviisio
28

---

Published as a conference paper at ICLR 2026
Netherlands). However, lacking structured planning subgoal decomposition, it prunes valid paths prematurely and incorrectly concludes that insufficient information available.
PoG performs better in retrieval, identifying facts like (Nijmegen, location. coriooonoocaaiinn..ee. -wwnnayaarrrrrtttt...aeaaaaa Weeze Airport). However, it suffers from LLM hallucination, prematurely terminating the reasoning process and erroneously predicting the Netherlands as the final answer without validating supporting facts.
In contrast, VoG successfully answers the question by employing three key mechanisms: (i) an initial reasoning plan that explicitly outlines the intended depth or retrieval, (ii) stepwise verification that checks the factual correctness of each intermediate step against retrieved KG triplets, and (iii) context-aware revision strategy, such as lookahead, which dynamically adapts retrieval and plan updates. Moreover, because VoG performs verification and revision along the entire reasoning chain, it is more tolerant to locally missing evidence "Unnamed Entity" as illustrated in ToG's case than baselines that rely solely on local decisions. These allow VoG to refine incorrect steps and extend reasoning depth when necessary, leading to factually grounded and correct answer.
Q: What country bordering France contains an airport that serves Nijmegen?
Topic Ereitiet: France,
Nimnggan
Retrieved triples: [France,
Europe], [France, location.ocation.cnttinnneii
Western Europe]. [France, location.occaionn.oooooooo hat.ioonocccatioooooocccttoooooo Unnamed (Njmege, second wewenddeeeevdilleee diviisiivsiion, Netherland]
ToG
Reasoning: Based on the given knowledge triplets, there insufficient information answer the question.
Retrieved triples (depth 1): [Nijmegen Docation.ocaatoon containedby, Netherlands], |France, location.location. containedby, Europe], [Nijmegen, location. www.:o/coannnnaara... airports,, Weeze Airport]
PoG
Reasoning: [LLM hallucination about the stopping criterion][ "A': "SSufflcient': "Yes", "Answer": "Netherland J. "R": "The country bordering France that contains airport serving Nijmegen the Netherlands.)
Thrughtt
sirport
Eumipe
Nijmegen
bordaring arrving Nijnagen,
Observatin
jove deltor of
O-iinegen, Netharlaadds),
(Weere Aipprit serves, Mirreger
seneeaa-eeee-jjgageeeeeee Aispues)
VoG pirp
determine
Vertty Aganz
Nijmegen
where Wezze WWeze
bcubio
Germany
Obsenazion (Woese airport, Germany)
Nijmege Weete Airport which
Weeve Airport
bonders franos
Figure Case study comparing VoG, ToG, and PoG.
F.3 ANALYSIS OF RECOVERED FAILUREE TYPES
To further investigate which types of reasoning failures benefit most from VoG's verification mecha- nism, conducted additional eиror analysis. Failure cases were categorized into four types via annotation assisted by GPT-3.5, with spot-checking for consistency. Table 14 summarizes the results.
Table 14: Distribution of recovered failure cases using GPT-3.5 annotation.
Failure Type
Description
Proportion
Hallucinated fact
LLM fabricates fact supported KG evi- dence.
37.5
Incomplete evidence
Answer returned before necessary evidence
27.9
collected and verified.
Entity disambiguation error
Incorrect entity chosen when multiple candidates exist.
21.7
Query intent drift
Reasoning plan deviates from the original query intent.
12.9
We find that hallucinated facts and incomplete evidence the most effectively recovered failure types, which aligns with our main claim that stepwise verification and context-awe awaee revision help mitigate hallucination and premature stopping.
29

---

Published as a conference paper at ICLR 2026
G CROSS-KG GENERALIZATION
To examine VoG's transferability beyond Freebase, we conduct two generalization experiments on both open-domain KG with different schema and domain-specializer biomedical KG.
Generalization to Wikidata. We evaluate VoG on Wikidata (Vrandečié and Krötzsch 2014) to assess cross-KG robustness. We directly replace the KG-specific retrieval interface while keeping the reasoning and verification modules unchanged. Experiments are conducted on the QALD- 10 (Santana al., 2022) benchmark, showing that VoG achieves competitive performance without any task-specific training as shown in Table 15
Table 15: The results comparison of different methods on the QALD11-en dataset.
Model
Method
Accuracy (%)
Fine-tuned SPARQL-QA (Santana al. 2022
45,4
GPT 3.5
ToG
50.2
GPT 3.5
VoG
57.4
Generalization to Biomedical Knowledge. Generalizing across domain KGs remains an open challenge in the field due the scarcity of high-quality multi-hop QA datasets outside open-doman settings. Existing biomedical datasets are typically yes/no or long free-form question answering, making controlled evaluation difficult. To enable a preliminary assessment, we construct small multi-hop biomedical QA benchmark based on Hetionet (Himmelstein al. 2017). UML (M---verieee KG containing 47,031 nodes and 2,250, 197 edges. We extract multi-hop hop relational paths, filter them for semantic coherence, and GPT-3.5 rewriting to obtain 200 naturally phrased biomedical questions (c.g.. "Which genes interact with genes that are downregulated by Dacarbazine?") Owing to the reduced contextual variability in biomedical queries, adopt local revision strategy for this study. Table 16 shows the accuracy gain of VoG on our test set.
Table 16: The results on our
Setting
Accuracy (%)
GPT 3.5
1.0
VoG
19.5
Gain
+18.5
We further evaluate VoG on two biomedical datasets, PubMedQA (Jin et al. 2019) and BioASQ (Krithara al. 2023), both consisting of yes/no type questions that do require multi-hop reasoning. The experiment is conducted under the sparse-KG setting introduced in GIVE (He et al. 2025). using
KG with only 135 nodes and 5,877 edges, which severely limits the available triplets and path candidates. Table T7 shows the results comparison in terms of accuracy, average token usage, and average inference time.
Table 17: The results comparison of GIVE, ToG, and VoG on PubMedQA and BioASQ.
Dataset
Method
Accuracy (%)
Avg Tokens
Avg Time (s)
GIVE
53.6
14,701.5
33.6
PubMedQA (Jin et al. 2019
ToG
17.6
12,805.3
15.9
VoG
45.3
1,653.2
12.1
GIVE
88.2
8,050.3
15.3
BioASQ Krithara et al. 2023
ToG
18.0
7,070.2
10.3
VoG
93.5
1,862.6
14.1
These results demonstrate that VoG can generalize beyond Freebase to KGs with different structural and semantic characteristics. This transferability is primarily enabled by VoG's training-free design,
30

---

Published as a conference paper at ICLR 2026
where retrieval relies on pretrained text embeddings that carry semantically transferable signals across heterogeneous schemas. The inherent cross cross-domain generalization capability of LLMs also stabilizes VoG's reasoning specific domains even when domain knowledge is sparse noisy.
H
LIMITATION
Despite the strong performance of VoG in multi-hop KG reasoning, several limitations remain:
Reliance on KG Completeness: VoG assumes access to a reliable and sufficiently complete KG. However, real-world KGs that constructed from web corpora are often noisy or incomplete, which may lead to retrieval failures or factual errors. In future work, we plan to incorporate KG confidence scores external sources mitigate such issues.
Frozen LLM-based Verifier: In this work, we leverage frozen LLMs and PLMs as verifiers, which may be limited by their pre-training distributions and lack of task-specific tuning. As result, subtle inconsistencies may go undetected during stepwise verification. In the future, plan explore fine-tuning LLMS to act as more reliable verification modules and enable stronger factual validation and more accurate revision signals.
Basic Context Selection Granularity: Our current context selector relies on signals like entropy and step. Incorporating structural signals from the KG, such as node centrality or subgraph coherence, may offer finer-grained control over reasoning revision and is worth exploring in future.
I THE USE OF LARGE LANGUAGE MODELS
Large language models (LLMs) were used in this work as supportive tools to polish the writing. They assisted with grammar, clarity, and style, but did not contribute to the design of the methodology. implementation of experiments, or interpretation of results. Their role was limited to improving readability, without generating original research contributions.
31


Reviews:
[{"review_id": "knZvxqtww8", "reviewer": "Reviewer_cbkJ", "summary": "This paper proposes Verify-on-Graph (VoG), a model-agnostic framework that enhances reasoning reliability of LLMs on knowledge-intensive tasks by couping iterative retrieval, stepwise verification and revision, based on knowledge triplets retrieved from knowledge graphs. Unlike existing KG-augmented reasoning systems that follow fixed reasoning plans, VoG introduces (1) Stepwise KG verification that detects factual inconsistencies at each reasoning step. (2) Plan revision via multi-armed bandit context selection that adaptively decides which contextual scope to use for revising reasoning. Experiments on KG reasoning benchmarks show consistent improvements across backbone models of different sizes, compared to the strong agentic baselines with reduced token cost.", "questions": "1. What is the motivation to revise the reasoning plan given the retrieved knowledge triplets? Why does the factual knowledge retrieved play a role in evaluating(verify) the reasoning sub-step? A more natural way could be to populate the retrieved knowledge when it is not sufficient to solve the reasoning sub-step. \n\n2. There is no guarantee that the prompted based verification agent would return a faithful and correct response. In Table 2, the authors conducted ablation studies to show the effect of verify/revision. However, it is not clear whether the improvement is due to the verifier, or it's a effect of parallel thinking introduced by the revision itself. A more rigorous way is to test on a dataset that has ground truth reasoning([1] for example) steps and show these models can indeed distinguish the correct reasonings from the incorrect. \n\n3. What is the benefit of having a plan first and conduct step-with verify and revise, instead of iteratively reasoning and retrieve as in [2]?\n\n4.  VoG retrieves relation and entity based on some semantic similarity score, which is similar to the retrieval approach introduced in [3], it is beneficial to include a discussion or comparison on that. \n\n5. Why the semantic similarity between the \"predicted observation\" and the input question can serve as a quality measure of reasoning, as introduced in Appendix B.2. Not every reasoning step needs to share similar semantic meaning with the question.\n\n6. All experiments in Table 1 are conducted on Freebase knowledge graph, it remains unclear whether VoG generalizes to other domains, like scientific or biomedical KGs (such as UMLS).\n\n[1] MINT-CoT: Enabling Interleaved Visual Tokens in Mathematical Chain-of-Thought Reasoning\n\n[2] Search-R1: Training LLMs to Reason and Leverage Search Engines with Reinforcement Learning\n\n[3] GIVE: Structured Reasoning of Large Language Models with Knowledge Graph Inspired Veracity Extrapolation", "limitations": "", "rating": 4, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. Novel verification framework for reasoning. The proposed step verification has the potential of mitigating error/hallucination propagation and improve faithful reasoning.\n\n2. Adaptive context selection.  The idea of using UCB to balance the information window in the decision making process is innovative, and has the potential to be extended to other long-reasoning tasks as well. \n\n3. Strong empirical results. Experiments show consistent gains across three benchmarks and multiple LLM sizes, which validate the approach's generality.", "weaknesses": "Some key components, such as reward design details for UCB are located in the Appendix. They should stand out in the body of the methodology. See Questions for other technical weakness.", "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": "yXxTLUSmrG", "reviewer": "Reviewer_4vgR", "summary": "This paper proposes a novel Verify-on-Graph (VoG) framework, which supports dynamic and context-aware LLM reasoning over KG through iterative retrieval, verification, and adaptive refinement. To be specific, the proposed method firstly employs a plan agent to generate reasoning chains, serving as guidance for multi-hop retrieval process. Then, stepwise verification and adaptive refinement is adopted to detect reasoning inconsistencies and make sure the correctness of subsequent reasoning steps. Finally, a confidence-based reward is designed to capture uncertain information for revision. Extensive experimental results demonstrate the effectiveness of the proposed method.", "questions": "Please refer to Section Weaknesses.", "limitations": "", "rating": 4, "confidence": 5, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1.\tThis paper is well-organized and easy to follow.\n2.\tThis paper presents a VoG framework consisting of three specialized LLM agents for retrieval, verification, and revision, which address the challenges of inflexible reasoning and limited utilization of information.\n3.\tThis paper provides the source code to ensure the reproducibility of the proposed method.", "weaknesses": "1.\tThe figures could be further refined to enhance readability. In particular, the font size in Figures 1 and 3 is quite small, and Figure 7 appears to have low resolution.\n2.\tThe paper may lack some baseline methods for comparison, such as GNN-RAG [1], SubgraphRAG [2].\n3.\tThe core idea may not be highly novel, since the retrieval–plan–verify pipeline has been adopted in prior studies.\n\n[1] Mavromatis, Costas, and George Karypis. \"Gnn-rag: Graph neural retrieval for large language model reasoning.\" arXiv preprint arXiv:2405.20139 (2024).\n[2] Li, Mufei, Siqi Miao, and Pan Li. \"Simple is Effective: The Roles of Graphs and Large Language Models in Knowledge-Graph-Based Retrieval-Augmented Generation.\" The Thirteenth International Conference on Learning Representations.", "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": "qq6sJxT13d", "reviewer": "Reviewer_rU7C", "summary": "This paper proposes VoG (Verification-over-Generation), a reasoning framework that enhances large language models (LLMs) with structured, knowledge-grounded verification and revision. Unlike previous reasoning or retrieval-augmented methods that rely solely on planning or evidence retrieval, VoG organizes reasoning into a Plan–Retrieve–Verify–Revise loop.", "questions": "See weakness above.", "limitations": "", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The paper introduces a unified Plan–Retrieve–Verify–Revise reasoning framework, emphasizing step-wise knowledge-grounded verification. This design effectively connects planning with factual correction and hallucination suppression, offering a more systematic approach than prior single-stage (planning-only or retrieval-only) methods. Compared to ToG/PoG agents, VoG achieves lower average token consumption and fewer reasoning turns while maintaining higher accuracy, supporting the paper’s claim of being lightweight and efficient.", "weaknesses": "The author’s efficiency analysis section is very convincing; however, I am still curious about the end-to-end latency, as its framework introduces more steps compared to ToG and PoG.", "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": "BHstSzcD7H", "reviewer": "Reviewer_YG4Q", "summary": "The paper proposes Verify-on-Graph (VoG), a framework that enhances Large Language Models' reasoning by integrating knowledge graphs for reliable inference. VoG features iterative retrieval, verification, and adaptive planning refinement to boost accuracy and efficiency. Experiments on three benchmark datasets demonstrate its effectiveness in improving reasoning performance.", "questions": "1. How does VoG handle valid but missing KG facts during reasoning?\n2. How sensitive is the performance to the UCB hyperparameters?\n3. Could VoG generalize beyond Freebase, e.g., ConceptNet or domain-specific KGs?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. VoG introduces a novel framework that enables stepwise verification and planning refinement on KGs to mitigate error propagation during multi-hop reasoning.\n2. VoG proposes a KG-aware multi-armed bandit (MAB) mechanism for adaptive context selection, which is a valuable contribution for dynamically determining context information for refining reasoning plans.\n3. Experiment on three benchmark datasets shows that VoG significantly outperforms existing methods, demonstrating its effectiveness in enhancing the reasoning capabilities of LLMs.", "weaknesses": "1. The architecture of VoG seems complex with multiple components. While each component is motivated and performance improvements are shown, the overall complexity may hinder practical adoption. The authors should provide more analysis on the trade-offs between complexity and performance gains, and possibly explore simplifications.\n2. UCB hyperparameter sensitivity is not deeply analyzed — how robust is the method to different scaling of entropy or exploration bonuses?\n3. No evaluation beyond Freebase / KGQA — unclear whether VoG generalizes to non-Freebase or domain-specialized KGs (e.g., ConceptNet , biomedical UMLS).\n4. The proposed method relies on retrieving evidence from the KG, but it is unclear how VoG handles cases where valid evidence/fact are missing from the KG.", "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)