acceptodds
Under review as a conference paper at ICLR 2027

GraphPilot: Faithful and Adaptive Reasoning for Large Language Models via Graph-Constrained Exploration

Abstract

Knowledge graphs (KGs) provide structured knowledge to enhance the reasoning capabilities of large language models (LLMs). However, prevailing methods typically leverage KGs as external evidence or training supervision, while reasoning paths are still generated from LLMs’ parametric distribution. Consequently, generated paths may exhibit hallucinations and lack support from KGs. Moreover, fixed reasoning depths and candidate path budgets fail to accommodate varying question requirements, potentially introducing irrelevant noise or missing valid paths. To address these limitations, we propose GraphPilot, which formulates KG reasoning as adaptive exploration within a graph-constrained decoding space. First, it converts KGs into executable token-level decoding constraints and allows LLMs to terminate at valid entity boundaries, enabling graph-faithful reasoning with adaptive depth. Second, it employs divergence-aware policy optimization to encourage adaptive exploration within the constrained space. Finally, it incorporates a relation-chain refinement mechanism, which prunes redundant candidate paths according to relation-chain semantics. Extensive experiments on multiple KGQA benchmarks demonstrate that GraphPilot achieves state-of-the-art performance. Further analysis shows that it maintains graph-faithful reasoning while supporting adaptive exploration.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Knowledge Graph, Large Language Models, Knowledge-enhanced Reasoning, Reinforcement Learning

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_k5KiOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This work proposes GraphPilot, which is an LLM-based framework for knowledge graph question answering. For each question, it constructs the corresponding subgraph and represents its valid reasoning paths as a prefix tree. The LLM is constrained to generate only KG-valid path continuations during decoding, and may terminate at entity boundaries. To train the model, it introduces divergence-aware policy optimization, which assigns negative feedback when a trajectory diverges from its cloest reference path. Furthermore, a relation-chain refinement is used to filters question-irrelevant candidates. Experiments on WebQSP and CWQ shows that the proposed method outperforms a wide range of KGQA baselines. The ablation results highlight the contribution of divergence-aware policy optimization and relation-chain refinement.

Critical strengths
  1. Graphpilot restricts each token in the reasoning-path segment to valid continuations in the knowledge graph, so that its paths are supported by KG, which effectively reduces hallucinated entities or relations, and provides verifiable reasoning evidence.

  2. The termination mechanism enables variable-depth reasoning. and the divergence-aware policy optimization improves credit assignment for branching and stopping decisions. Relation-chain filtering further work on finding the question-relevant candidates. These components together make the framework better adapt its reasoning paths to the requirements of individual questions.

Critical weaknesses
  1. GraphPilot can generate only paths contained in the constructed question-specific subgraph. If subgraph construction excludes all paths to a correct answer, the constrained decoder cannot recover that answer.

  2. GCR already introduces trie-based graph-constrained decoding, while EoG and PathMind explore RL and preference based KG reasoning. GraphPilot combines these ideas with entity-boundary termination, divergence-aware credit assignment, and relation-chain filtering. However, the experiments do not fully isolate the value of each component. For example, the ablation study removes RL and refinement but does not separately evaluate entity-boundary termination or compare divergence-aware optimization with standard GRPO or EoG-style RL.

Questions for authors
  1. What are the distributions of the generated path lengths, retrained path lengths and the number of beam candidates after relation-chain refinement?

  2. What is the effect of entity-boundary termination alone?

  3. How does divergence-aware policy optimization compare with standard GRPO or an EoG-style RL objective under the same backbone, constrained space, and decoding budget?

  4. Could you report end-to-end inference cost, including question-specific subgraph construction, prefix-tree construction, constrained decoding, and relation-chain filtering?

  5. How often does relation-chain refinement remove a correct candidate path or answer?

5 comments
AuthorsOpenReview ↗

Response to the Reviewer's Valuable Comment 1 to 3.

Response to Question 1.

Thank you for suggesting that we report these distributions. We provide the path-length distributions before and after Relation-Chain Refinement, as well as the number of beam candidates retained per question after refinement.

(1) Path Length Distribution. The following table reports the distributions of generated and retained paths in terms of KG hops. After refinement, the path-length distributions shift toward shorter paths, with a reduced proportion of paths involving three or more hops.

DatasetStage# Paths1 hop (%)2 hops (%)≥3 hops (%)
WebQSPGenerated16,28054.6130.9914.40
WebQSPRetained10,49769.4922.667.85
CWQGenerated35,31043.7542.1314.12
CWQRetained22,78436.2661.821.92

(2) Distribution of Retained Beam Candidates. Each question initially generates 10 candidate paths. We report the distribution of the number of candidates retained per question after applying the relevance threshold, grouped into different ranges.

DatasetQuestions≤2 candidates (%)2–4 candidates (%)4–6 candidates (%)6–8 candidates (%)8–10 candidates (%)
WebQSP1,62816.0311.7910.698.4853.01
CWQ3,53117.5610.4210.6211.3950.01

These results demonstrate that Relation-Chain Refinement effectively filters question-irrelevant candidates, reducing the noise introduced by fixed beam generation. Importantly, GraphPilot combines Adaptive Termination during path generation with Relation-Chain Refinement after generation, enabling question-dependent control over both reasoning depth and the number of retained candidate paths.

Response to Question 2: Effect of Entity-Boundary Termination

Thank you for raising this question. Entity-boundary termination ensures that the model can terminate only after generating a complete entity, preventing paths from ending within an incomplete KG transition. This is essential for maintaining structurally valid reasoning paths, as GraphPilot jointly learns which valid edge to follow and when to stop exploring.

To isolate its contribution, we conduct an ablation by removing the entity-boundary restriction while keeping the other settings unchanged. As shown below, removing this mechanism consistently degrades performance on both datasets, demonstrating its importance in ensuring complete and valid KG reasoning paths.

MethodWebQSP Hit / F1 (%)CWQ Hit / F1 (%)
GraphPilot93.7 / 82.689.8 / 81.1
GraphPilot w/o Entity-Boundary Termination90.2 / 73.576.3 / 75.6
GCR (baseline)88.3 / 65.468.6 / 53.2
EoG (baseline)92.8 / 81.386.6 / 77.9

Response to Question 3: Comparison with Standard GRPO and EoG-style RL

Thank you for suggesting this comparison. Our divergence-aware optimization is motivated by the observation that a low-reward trajectory may still contain reference-consistent reasoning prefixes that lead to states from which correct continuations are reachable. Standard GRPO applies negative feedback to the entire trajectory, potentially penalizing these already-correct decisions. In contrast, our method identifies the first divergence from the reference path and applies negative feedback only from that point onward, preserving correct reasoning prefixes.

To isolate the contribution of this design, we replace only the policy update with standard GRPO while keeping the backbone, constrained decoding space, reward function, and decoding budget unchanged. As shown below, divergence-aware optimization consistently improves Hit and F1 on both datasets. We additionally include EoG as a system-level reference, which uses its own reward design and graph exploration mechanism rather than our token-level constrained decoding.

MethodPolicy UpdateReward SettingWebQSP Hit / F1 (%)CWQ Hit / F1 (%)
GraphPilotDivergence-awareGraphPilot reward93.7 / 82.689.8 / 81.1
GraphPilot-RL (GRPO)Standard GRPOGraphPilot reward91.6 / 76.580.3 / 73.2
EoG (baseline)Standard GRPOEoG reward92.8 / 81.386.6 / 77.9

These results demonstrate the benefit of divergence-aware credit assignment within the graph-constrained reasoning space: it preserves reference-consistent decisions while focusing negative feedback on the actual divergence, leading to more effective policy optimization.

AuthorsOpenReview ↗

Response to the Reviewer's Valuable Comment 4 and 5.

Response to Question 4: End-to-End Inference Cost

Thank you for requesting a detailed report of GraphPilot's end-to-end inference cost. We measure the average latency of all four stages on WebQSP, covering both offline preprocessing and online inference, as summarized below.

StageComponentAverage Latency (s/question)
OfflineQuestion-Specific Subgraph Construction3.00
OfflinePrefix-Tree Construction4.29
OfflineSubtotal7.29
OnlineGraph-Constrained Decoding3.10
OnlineRelation-Chain Refinement0.01
OnlineSubtotal3.11
End-to-EndTotal10.40

We set the maximum reasoning depth to 20 hops to provide sufficient exploration flexibility, while allowing the model to terminate early at valid entity boundaries. Thus, 20 hops represents an upper bound rather than the actual reasoning depth for every question. The question-specific subgraph and its corresponding prefix tree can also be constructed in advance and cached for reuse. Once these structures are available, subsequent inference requires only Graph-Constrained Decoding and Relation-Chain Refinement, taking 3.11 seconds per question.

These results provide a complete breakdown of GraphPilot's inference cost, including both graph construction and subsequent reasoning stages. We will incorporate these measurements and clarify the offline preprocessing and online inference costs in the revised manuscript.

Response to Question 5: Removal of Correct Candidates by Relation-Chain Refinement

Thank you for raising this question. We evaluate the impact of Relation-Chain Refinement at different relevance thresholds on CWQ, using the same experimental setup as in the main experiments. Specifically, we report the number of removed gold-answer candidates, the proportion of gold-answer candidates among all removed candidates, and the number of affected questions.

The gold-answer proportion among removed candidates is defined as:

\text{Gold-answer Proportion (\\%)} = \frac{\text{Gold-answer candidates removed}}{\text{Total candidates removed}} \times 100

ThresholdGold-answer Candidates RemovedGold-answer Proportion (%)Affected QuestionsAffected Questions (%)Hit (%)P (%)R (%)F1 (%)
w/o refinement––––90.167.082.774.0
0.51301.02972.7589.880.781.581.1
0.73381.672286.4685.984.772.578.1

The results show that Relation-Chain Refinement substantially improves precision by filtering question-irrelevant candidates, while removing relatively few gold-answer candidates under the default threshold. Although a higher threshold further improves precision, it also reduces recall. Importantly, Relation-Chain Refinement is designed to mitigate the noise introduced by fixed beam generation, rather than maximize candidate retention. The default threshold of 0.5 achieves a favorable balance between answer coverage and prediction precision, improving overall F1.

AuthorsOpenReview ↗

Our Response and Commitment

We will incorporate all clarifications and additional experimental results into the revised manuscript to further improve its completeness and clarity. We sincerely hope that our responses have adequately addressed your concerns and clarified the contributions of GraphPilot. We would greatly appreciate your reconsideration of the paper's overall rating in light of these clarifications and revisions.

Reviewer_5TeWOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
3(+1)
Read review
Paper summary

The paper proposes GraphPilot, a framework for knowledge graph question answering that constrains LLM-generated reasoning paths to valid KG transitions while allowing adaptive termination at entity boundaries. The method combines graph-constrained decoding with divergence-aware policy optimization, which avoids penalizing prefixes shared with reference paths, and relation-chain refinement, which filters candidate paths based on their relevance to the question. Experiments on WebQSP and CWQ report improvements over existing KGQA methods in Hit and F1 scores, along with analyses of inference efficiency and adaptive reasoning behavior.

Critical strengths

S1. Clear Presentation

The paper is well organized and clearly presents the problem setting, proposed approach, and experimental results. The overall structure is easy to follow, and the explanations help readers understand the main components and their intended roles.

S2. Detailed Method Explanation

The paper provides detailed descriptions of the graph-constrained decoding mechanism and training objectives. The mathematical formulations and algorithmic explanations make the proposed approach relatively easy to understand and assess.

S3. Empirical Comparisons with Existing KGQA Methods

The paper provides empirical comparisons with a range of existing KGQA methods across two benchmarks. These comparisons, together with the reported ablations, provide useful evidence for evaluating the effectiveness of the proposed approach within the KGQA setting.

S4. Reproducibility

The paper provides explicit formulations of the decoding constraints and optimization objectives, supporting independent implementation. The use of established benchmarks and reported baseline results also provides useful reference points for reproducing the experiments, although some experimental details require further clarification.

Critical weaknesses

W1. Limited Reasoning Expressiveness and Generalizability of Graph Constraints

The proposed method restricts reasoning paths to explicitly existing KG transitions, which may exclude valid inferences requiring logical composition, numerical comparisons, or knowledge not represented in the graph. This raises a trade-off between graph validity and reasoning expressiveness, particularly for tasks beyond path-based KGQA. Although the constraints are lifted during final answer generation, doing so also weakens the claimed faithfulness guarantee. The paper does not sufficiently investigate these limitations, as its evaluation assumes that valid KG paths to correct answers exist. Experiments involving incomplete KGs or tasks requiring implicit reasoning would help establish the applicability of the approach, or the authors should narrow their claims to path-based KGQA.

W2. Graph Validity Does Not Necessarily Guarantee Faithful Reasoning

The paper defines reasoning faithfulness primarily through the validity of individual KG transitions, without sufficiently examining whether the resulting paths logically support the answers. In particular, some examples in Table 9 contain long, semantically questionable paths that reach the correct answer entity through seemingly irrelevant relations. The reliance on shortest paths to gold answers for reward supervision also does not guarantee that these paths provide logically sufficient evidence. A more meaningful evaluation should distinguish structural KG validity from question-conditioned reasoning faithfulness.

W3. Potentially Overly Favorable and Insufficiently Clarified Experimental Setting

Appendix Table 4 reports that the constructed decoding spaces contain at least one correct answer path for every test question in both datasets, despite the use of bounded lexical graph expansion. This raises questions about how such complete answer-path coverage is achieved and whether the evaluation adequately reflects the challenges of evidence discovery in realistic KG settings. The paper should explicitly clarify that test-time graph construction does not rely on gold answers and report how performance changes when relevant paths are missing or pruned. Without such analysis, it is difficult to assess the robustness of the proposed approach beyond this favorable setting.

W4. Incomplete Ablations and Insufficient Justification for LLM-Based Path Generation

Although the paper includes component ablations and a comparison with standard GRPO, several important controls are missing. In particular, the benefits of adaptive termination and divergence-aware optimization are not fully isolated from the overall training pipeline, and comparisons with simpler path-selection strategies under the same candidate space are absent. Since graph constraints limit the LLM primarily to selecting and terminating valid paths, it is unclear whether a generative LLM is necessary instead of a lightweight neural path ranker. Matched comparisons with simpler ranking models and GCR augmented with adaptive termination would help establish the contribution of the proposed components.

W5. Incomplete Assessment of Computational Efficiency

The efficiency comparison focuses on LLM generation time while excluding the cost of constructing the graph-constrained decoding space, which requires an additional 4.29–6.47 seconds per question on average. Moreover, the method relies on multi-beam candidate generation and a separate refinement model, making the number of LLM calls an incomplete indicator of computational efficiency. The paper should report end-to-end latency and computational costs, including preprocessing, constrained decoding, and refinement, under comparable settings. This is particularly important for justifying the additional complexity relative to conventional KG retrieval and ranking approaches.

Questions for authors

Please see the weakness section above.

7 comments
AuthorsOpenReview ↗

Response to the Reviewer's Valuable Comments 1 and 2.

Response to Concern 1: Limited Reasoning Expressiveness and Generalizability of Graph Constraints

We thank the reviewer for this insightful comment.

(1) Graph Faithfulness and Reasoning Expressiveness. Restricting reasoning paths to existing KG transitions is intentional, as KG-enhanced LLMs may still generate hallucinated paths. GraphPilot ensures that every generated transition is KG-supported while preserving compositional multi-hop reasoning. Its primary goal is faithful and adaptive exploration within the KG, rather than unrestricted reasoning beyond it.

(2) Answer Generation and Faithfulness. GraphPilot internalizes external path retrieval into graph-constrained generation, allowing the LLM to reason over generated KG-grounded paths when producing answers. Although answer generation is unconstrained, our SFT and RL objectives encourage consistency between paths and answers. Thus, structural path validity is guaranteed, while answer-level faithfulness is encouraged rather than formally guaranteed.

(3) Applicability and Limitations. GraphPilot assumes that answer-relevant paths exist in the KG, consistent with our path-based KGQA setting. Missing KG evidence may prevent correct answers from being reached, reflecting the intentional trade-off between structural faithfulness and reasoning expressiveness. We will clarify this scope and limitation in the revised manuscript.

Importantly, GraphPilot does not aim to expand reasoning beyond the available KG, but to address two fundamental challenges in KG-enhanced LLM reasoning: preventing hallucinated graph transitions and enabling adaptive exploration within the graph-constrained space. By jointly ensuring structural validity and learning when to terminate exploration, GraphPilot provides a more reliable and adaptive alternative to unconstrained path generation.

Response to Concern 2: Graph Validity Does Not Necessarily Guarantee Faithful Reasoning

We thank the reviewer for highlighting the distinction between structural KG validity and question-conditioned reasoning faithfulness.

(1) Motivation and Scope of Graph Faithfulness. The primary motivation of GraphPilot is to prevent LLMs from hallucinating KG transitions during reasoning, even when KG knowledge is provided as external evidence or training supervision. Accordingly, we define graph faithfulness at the structural level, ensuring that every generated transition exists in the KG. We agree that structural validity alone does not guarantee that a path is relevant to the question or provides logically sufficient evidence for the answer. To further address path relevance, we introduce Relation-Chain Refinement to distinguish question-relevant paths from structurally valid but irrelevant ones. Thus, GraphPilot aims to improve both structural validity and question-conditioned path selection, while recognizing that logical evidence sufficiency is not formally guaranteed.

(2) Analysis of Table 9. In Case 1, Output 1 directly connects New York University to Albert Gallatin through the founder relation, while Output 2 starts from another topic entity, Member of Congress, and explores a longer KG-valid path to reach the same relevant founder relation. This demonstrates GraphPilot's ability to explore relevant evidence from different starting entities. Although some intermediate hops in Output 2 provide limited additional evidence, the example illustrates flexible graph exploration rather than complete logical evidence sufficiency. We will clarify this distinction in the revised manuscript.

(3) Motivation and Limitation of Path Supervision. We adopt shortest paths to gold answers as weak supervision to provide concise structural references and discourage redundant exploration. Answer rewards and Relation-Chain Refinement further encourage answer correctness and question-relevant path selection. Although these mechanisms do not formally guarantee logical evidence sufficiency, they jointly improve structural validity and question relevance. We will clarify this distinction in the revised manuscript.

Importantly, GraphPilot does not rely on structural validity alone: Graph-Constrained Decoding prevents hallucinated transitions, while Divergence-Aware Policy Optimization encourages effective path exploration and Relation-Chain Refinement further filters question-irrelevant candidates. These complementary components address both the structural validity and question relevance of generated paths, rather than treating KG connectivity alone as sufficient reasoning evidence.

AuthorsOpenReview ↗

Response to the Reviewer's Valuable Comments 3.

Response to Concern 3: Potentially Overly Favorable and Insufficiently Clarified Experimental Setting

We thank the reviewer for raising this important concern.

(1) Clarification of Test-time Graph Construction. At test time, GraphPilot constructs each question-specific subgraph and prefix tree solely based on the question text, its topic entities, and Freebase, without accessing gold answers. Gold answers are used only for training supervision and post-hoc evaluation. Specifically, the 100% coverage reported in Appendix Table 4 indicates that at least one gold answer is reachable in the constructed subgraph for every test question; it does not mean that all gold answers are covered or that gold answers are used during graph construction.

(2) Analysis of Subgraph Coverage. Our graph construction employs question-aware lexical expansion with bounded per-depth frontiers, retaining multiple promising branches for further exploration. This allows the constructed subgraphs to cover diverse question-relevant graph regions, resulting in the observed answer-path coverage. We further report the following statistics to characterize the constructed search spaces:

DatasetTest questionsTotal gold answersMean paths per question-specific subgraph
WebQSP1,62813,9554,946
CWQ3,5316,5335,027

(3) Sensitivity to Subgraph Pruning. To further examine the impact of subgraph construction on answer reachability and downstream performance, we conduct an additional experiment on WebQSP by reducing the frontier budget from 64 to 32. We compare the resulting answer-path coverage and QA performance under the two settings, as reported below.

SettingFrontier BudgetUnreachable Gold AnswersHit (%)F1 (%)
Default64              -                        93.7    82.6  
Reduced32              158                      89.3    76.3  

These results highlight the importance of retaining sufficient graph evidence during subgraph construction. Importantly, GraphPilot does not rely on gold answers for constructing the decoding space, but instead learns to adaptively explore KG-supported paths while ensuring that every generated transition is structurally valid. Thus, its contribution lies in faithful and adaptive exploration within the available graph evidence, rather than recovering missing KG facts.

AuthorsOpenReview ↗

Response to the Reviewer's Valuable Comment 4.

Response to Concern 4: Incomplete Ablations and Insufficient Justification for LLM-Based Path Generation

We thank the reviewer for these valuable suggestions. To better isolate the contributions of our design choices and clarify the motivation for LLM-based path generation, we provide the following additional analyses.

(1) Contribution of Adaptive Termination. GraphPilot allows the termination token to compete with graph-valid continuation tokens at eligible entity boundaries, enabling the model to decide whether to stop or explore further based on the current question and path prefix. To isolate its contribution, we compare GraphPilot with its variant without adaptive termination, as well as GCR with and without adaptive termination under matched hop limits. As shown in the results, removing adaptive termination substantially degrades GraphPilot's performance. Moreover, adaptive termination brings increasingly clear benefits to GCR as the maximum hop limit increases, mitigating the unnecessary exploration caused by fixed-depth reasoning. These results validate the importance of adaptive stopping within the graph-constrained space.

MethodCWQ Hit / F1 (%)
GraphPilot89.8 / 81.1
GraphPilot w/o adaptive termination75.9 / 68.7
GCR + adaptive termination (2 hops)67.5 / 54.1
GCR (2 hops)68.6 / 53.2
GCR + adaptive termination (4 hops)70.4 / 57.7
GCR (4 hops)60.2 / 45.8

(2) Contribution of Divergence-Aware Policy Optimization. To isolate the effect of our policy optimization strategy, we initialize both variants from the same SFT checkpoint and replace only the divergence-aware update with standard GRPO, keeping the reward function and other training settings unchanged. As shown in the results, divergence-aware optimization consistently improves performance on both datasets. This supports our motivation of preserving reference-consistent prefixes and applying negative feedback only from the first divergence onward, avoiding unnecessary penalties on already-correct reasoning decisions.

Method              Policy Update    WebQSP Hit / F1 (%)CWQ Hit / F1 (%)
GraphPilot          Divergence-aware93.7 / 82.6        89.8 / 81.1      
GraphPilot-RL (GRPO)Standard GRPO    91.6 / 76.5        80.3 / 73.2      

(3) Motivation for LLM-based path selection. The key advantage of LLM-based path generation lies in its ability to perform sequential and adaptive reasoning decisions, rather than merely ranking completed candidate paths. First, incremental path generation allows the model to construct reasoning trajectories step by step, using intermediate entities and relations to guide subsequent exploration. Second, its decisions are state-dependent: the next relation is selected based on both the question and the current path prefix, enabling context-aware exploration beyond static semantic matching. Third, the model jointly decides whether to continue expanding the current path or terminate at an eligible entity boundary. This allows it to adapt reasoning depth to individual questions and avoid unnecessary exploration. Together, these capabilities make the LLM an adaptive exploration policy within the graph-constrained space, rather than simply a candidate path ranker.

To examine whether an LLM is necessary for path selection, we introduce a lightweight ranking baseline under the same question-specific subgraph space as GraphPilot. Specifically, we use all-MiniLM-L6-v2 to compute the cosine similarity between each question and its candidate paths, rank the paths accordingly, and select the top-10 paths. The terminal entities of these selected paths are returned as answers. The results are reported below.

MethodPath Selection StrategyWebQSP Hit / F1 (%)CWQ Hit / F1 (%)
Lightweight RankerTop-10 paths by cosine similarity43.7 /17.447.5/ 16.8
GraphPilotLLM-based constrained generation93.7 / 82.689.8 / 81.1
Reviewer_wP74OpenReview ↗
Rating
1(−1)
Confidence
4
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper proposes GraphPilot, a knowledge-graph-augmented LLM reasoning framework combining three components: (i) graph-constrained decoding with termination at complete entity boundaries; (ii) divergence-aware policy optimization, which suppresses negative policy advantages on reference-consistent prefixes; and (iii) relation-chain refinement, which filters candidate path–answer pairs using a contrastively trained relevance encoder. Experiments on WebQSP and CWQ demonstrate improvements over competitive baselines. Component ablations, including a controlled comparison against standard GRPO, support the effectiveness of the proposed optimization and filtering mechanisms. However, the evidence is stronger for benchmark performance and structural graph consistency than for semantic faithfulness or depth-adaptive reasoning.

Critical strengths
  1. Clear empirical improvements with controlled evidence for the proposed optimization.

    GraphPilot achieves the best reported results on both benchmarks. Compared with EoG, F1 improves from 81.3 to 82.6 on WebQSP and from 77.9 to 81.1 on CWQ. More importantly, Appendix Table 8 compares divergence-aware optimization against standard GRPO while holding rewards, sampling, and other training settings fixed, improving CWQ F1 from 73.2 to 81.1. This provides direct evidence for the proposed optimization beyond simply showing that additional RL training helps.

  2. Coherent design with complementary components addressing distinct failure modes.

    Graph-constrained decoding prevents structurally invalid paths, divergence-aware optimization avoids penalizing correct prefixes of negative-advantage trajectories, and relation-chain refinement removes graph-valid but irrelevant candidates. The components have clear roles. Ablations support the precision and F1 benefits of refinement while also revealing the associated loss in answer coverage.

Critical weaknesses
  1. Limited evaluation coverage leaves broad applicability and generalization insufficiently established.

    The experiments cover only WebQSP and CWQ. Although these datasets differ in question construction and difficulty, both rely on Freebase and share substantial commonality in their underlying knowledge source and relation vocabulary. The current results therefore do not clearly distinguish transferable reasoning strategies from adaptation to a particular knowledge system and data distribution. Additional benchmarks, especially cross-dataset and cross-knowledge-source transfer experiments, would substantially strengthen the conclusions.

  2. A verification gap remains between path-matching rewards and semantic faithfulness.

    Structural graph validity does not establish that a path satisfies all constraints in the question, and a shortest path to a gold answer need not constitute a semantically sufficient explanation. Figure 6 illustrates this concern: a question involving imports and an ISO code is answered through language relations. Since the path reward receives a weight of 0.6, compared with 0.3 for the answer reward, it is particularly important to examine whether training overoptimizes reference-path matching without corresponding improvements in answer quality. The reported 100% graph-support rate does not rule out this objective mismatch or establish that the generated answer is supported by the path.

Questions for authors
  1. Is the evaluation broad enough?

    The evaluation covers only WebQSP and CWQ, both based on Freebase. Please add results on benchmarks such as GrailQA to establish whether the improvements hold beyond these two datasets. To support effectiveness across knowledge sources, please also include a benchmark based on a different KG.

  2. Does the method generalize to datasets not used during training?

    Please add a cross-dataset OOD experiment: train on one dataset and evaluate directly on another, without using target-dataset training labels or tuning parameters on the target test set. Compare GraphPilot, SFT, and standard GRPO under identical conditions, and clarify whether the relation-chain encoder and filtering threshold remain unchanged.

  3. Why is the path reward weighted more heavily than the answer reward?

    The path and answer rewards receive weights of 0.6 and 0.3, respectively. Could this encourage the model to prioritize matching reference paths over answering the question correctly? Please provide a reward-weight ablation and training curves for the individual reward components alongside held-out QA performance. In particular, check whether the path reward increases without corresponding improvements in answer quality.

  4. How is divergence-aware credit assignment implemented, and what accounts for its gains?

    Equation 6 specifies the masking rule, but the implementation needs further clarification. Please provide pseudocode or the corresponding code, together with a token-level example showing how the reference path is selected, how the divergence position is determined, and how premature termination and incorrect answers are handled.

    Appendix Table 8 already demonstrates improvements over standard GRPO, but it does not directly establish whether those gains arise from protecting correct prefixes. Please report the proportion of tokens masked and relevant training diagnostics to substantiate the proposed mechanism and its stability.

  5. Figure quality and figure/table captions.

    Please export and embed framework diagrams and experimental plots as vector graphics, such as vector PDFs, so that text and lines remain clear when enlarged.

    Please also make the figure and table captions clearer and more informative. Captions should explain what is being shown or compared, define key labels and abbreviations, and specify relevant experimental settings. More self-contained captions would help readers interpret the results without repeatedly referring to the main text and improve the paper’s overall presentation.

18 comments
AuthorsOpenReview ↗

Response to Reviewer's Valuable Question 1 and 2

Response to Question 1: Evaluation Generalizability

We thank the reviewer for this valuable suggestion. To further evaluate the generalizability of GraphPilot beyond WebQSP and CWQ, we extend our experiments to GrailQA and MedQA-USMLE, covering different question distributions and knowledge sources.

(1) Additional Benchmark Evaluation. We evaluate GraphPilot on GrailQA, which is also based on Freebase but contains more diverse and compositional questions. Additionally, we evaluate MedQA-USMLE using PrimeKG, a medical knowledge graph distinct from Freebase. The experimental results are summarized below.

DatasetKnowledge GraphHit / F1 (%)
WebQSPFreebase93.7 / 82.6
CWQFreebase89.8 / 81.1
GrailQAFreebase95.0 / 92.8
MedQA-USMLEPrimeKG78.2 (Accuracy)

(2) Generalization across Knowledge Sources. The strong performance on GrailQA demonstrates that GraphPilot remains effective on a different KGQA benchmark with more diverse compositional structures. Furthermore, the results on MedQA-USMLE show that GraphPilot can be applied to a different knowledge source and domain. This is consistent with our design: Entity-Aware Graph-Constrained Reasoning operates on KG structures rather than Freebase-specific relations, while Divergence-Aware Policy Optimization enables adaptive exploration within the constructed graph-constrained space.

Overall, these additional results extend the evidence for GraphPilot's effectiveness beyond the original benchmarks and Freebase, supporting the broader applicability of faithful and adaptive graph-constrained reasoning. We will incorporate these experiments into the revised manuscript.

Response to Question 2: Cross-Dataset OOD Generalization

We thank the reviewer for this valuable suggestion. To evaluate the OOD generalization of GraphPilot, we train exclusively on CWQ and directly evaluate on WebQSP, GrailQA, and MedQA-USMLE without target-dataset training or parameter tuning. All variants use the same backbone, graph-constrained decoding space, and inference settings. The Relation-Chain Refinement encoder and filtering threshold remain unchanged from CWQ training.

(1) Cross-Dataset OOD Evaluation. We compare GraphPilot with SFT and standard GRPO under identical conditions.

MethodWebQSP Hit / F1 (%)GrailQA Hit / F1 (%)MedQA-USMLE Accuracy (%)
GraphPilot87.0 / 72.794.6 / 83.613.4
SFT80.7 / 64.681.9 / 75.08.5
Standard GRPO85.8 / 69.489.3 / 77.510.9

GraphPilot consistently outperforms SFT and standard GRPO across all three datasets, demonstrating the transferability of Divergence-Aware Policy Optimization and adaptive graph-constrained exploration. However, its performance on MedQA-USMLE is considerably lower than on the Freebase-based benchmarks. To investigate this domain shift, we further compare GraphPilot with and without Relation-Chain Refinement while keeping the CWQ-trained reasoning policy unchanged.

MethodMedQA-USMLE Accuracy (%)
GraphPilot13.4
GraphPilot w/o Relation-Chain Refinement69.7

The substantial improvement without refinement indicates that the CWQ-trained reasoning policy retains strong answer-reaching capability on the medical KG, while Relation-Chain Refinement is sensitive to cross-domain semantic shifts. Specifically, its contrastively trained encoder learns question–relation-chain relevance from CWQ, and differences in medical relation semantics may cause valid paths to be filtered out.

(2) Discussion. These results highlight the complementary roles of GraphPilot's components: Graph-Constrained Decoding and Divergence-Aware Policy Optimization support transferable, adaptive KG exploration, whereas Relation-Chain Refinement relies more heavily on domain-specific semantic alignment. Importantly, the core reasoning policy demonstrates promising OOD generalization even across different knowledge sources. We will discuss this distinction and the potential for cross-domain refinement adaptation in the revised manuscript.

AuthorsOpenReview ↗

Response to Reviewer's Valuable Question 3

Response to Question 3: Reward Weighting and Its Effect on QA Performance

We thank the reviewer for raising this important concern. We would first like to clarify an error in the reported reward weights. The main experiments used λ_ans = 0.6, λ_path = 0.3, and λ_fmt = 0.1, whereas the manuscript mistakenly interchanged the answer and path reward weights. We sincerely apologize for this reporting error. The reported main experimental results were obtained using the former configuration and therefore remain unchanged. We will correct the reward weights in the revised manuscript.

(1) Motivation for Reward Design. GraphPilot aims to learn effective exploration within the graph-constrained space while maintaining answer correctness as the primary objective. The Answer Reward directly supervises final answer correctness, whereas the Path Reward provides complementary trajectory-level guidance. Specifically, we use shortest paths from question entities to gold answers as reference paths to encourage concise exploration and discourage unnecessary continuations. However, these references are not necessarily the only valid paths to correct answers. Therefore, assigning excessive weight to path alignment may favor reproducing reference trajectories over exploring alternative KG-valid paths. Our reward design consequently assigns greater weight to Answer Reward while retaining Path Reward as auxiliary supervision.

(2) Reward-Weight Ablation. To examine this design, we conduct additional controlled experiments using a 1B model on WebQSP. Due to the computational resources and rebuttal timeline, we use the smaller model for this supplementary analysis rather than retraining the 8B backbone. We vary the reward weights while keeping the Format Reward weight fixed.

Path WeightAnswer WeightFormat WeightHit (%)F1 (%)
0.30.60.186.9956.82
0.60.30.183.5150.74
0.00.90.183.5054.49
0.90.00.178.6553.67

The results demonstrate the complementary roles of Answer Reward and Path Reward. Our default configuration achieves the best Hit and F1 among the evaluated settings. Compared with answer-only supervision, incorporating a moderate Path Reward improves Hit by 3.49 points and F1 by 2.33 points, indicating the importance of considering reasoning path quality alongside answer correctness. Conversely, increasing either reward weight excessively does not yield further improvements. These findings suggest that effective graph-constrained reasoning benefits from balancing answer correctness with path-level supervision, rather than optimizing either objective alone.

(3) Training Dynamics. We additionally provide the individual reward curves in Appendix I, including Total Reward, Path Score, Answer Score, and Format Score. Across the evaluated configurations, both Path Score and Answer Score generally improve during training. However, stronger path alignment does not necessarily translate into higher held-out QA performance, as demonstrated by the reward-weight ablation. This supports our design choice of prioritizing answer correctness while using path supervision to guide efficient KG exploration.

AuthorsOpenReview ↗

Response to Reviewer's Valuable Question 4

Response to Reviewer's Valuable Question 4: Implementation and Effectiveness of Divergence-Aware Credit Assignment

We thank the reviewer for this valuable suggestion. The key motivation of our Divergence-Aware Policy Optimization is that a low-reward trajectory may still contain reference-consistent prefixes that should not be unnecessarily penalized. Unlike standard GRPO, which applies negative advantages to the entire trajectory, our method preserves these prefixes and focuses negative feedback on subsequent divergent decisions. We provide detailed pseudocode and a token-level illustration, together with additional training diagnostics.

(1) Implementation of Divergence-Aware Policy Optimization.

The detailed implementation is provided in Algorithm 3 of Appendix J, and summarized as follows:

  • Trajectory Sampling and Reward Computation. Sample path–answer trajectories under Graph-Constrained Decoding, compute composite rewards, and obtain group-normalized advantages.
  • Reference Path Selection. Select the reference path with the longest common token prefix relative to each generated trajectory, including the <PATH> and </PATH> delimiters.
  • First Divergence Detection. Identify the first divergence position immediately after the longest common prefix. Including </PATH> allows premature termination to be detected.
  • Divergence-Aware Credit Assignment. For negative-advantage trajectories, mask the reference-consistent prefix by setting its token-level advantages to zero, while retaining the original negative advantages from the first divergence onward.
  • Policy Optimization. Optimize the clipped objective using the resulting token-level advantages.

(2) Token-Level Illustration.

We illustrate the mechanism in Appendix J.2 (Figure 14). The reference set contains four valid paths, including three through Garry Trudeau's children and one through the spouse relation.

Consider the prematurely terminated trajectory: <PATH>Garry Trudeau -> people.person.children -> Thomas Trudeau</PATH>Answer: Thomas Trudeau

  • Reference Selection: Among the four references, the path Garry Trudeau -> people.person.children -> Thomas Trudeau -> people.person.parents -> Jane Pauley shares the longest token prefix with the generated trajectory.
  • First Divergence: The generated trajectory follows this reference until Thomas Trudeau but terminates before the people.person.parents relation. The prematurely generated </PATH> marks the first divergence, assuming identical serialization of the preceding prefix.
  • Advantage Assignment: For a negative-advantage trajectory, the reference-consistent prefix receives zero advantage, while the premature termination and subsequent incorrect answer tokens retain the original negative advantage.

(3) Masking Statistics and Training Diagnostics. To examine whether the proposed mechanism effectively protects reference-consistent prefixes, we conduct an additional training analysis using a 1B-parameter model on WebQSP. We record masking activation, protected token proportions, and question-level coverage.

MetricValue
Total Sampled Trajectories11,304
Negative-Advantage Trajectories3,629 (32.10%)
Negative-Advantage Trajectories with Masking2,335
Masking Activation Rate64.34%
Masked Trajectories / All Trajectories20.66%
Valid Tokens in Negative-Advantage Trajectories224,400
Masked Tokens26,767
Masked Token Ratio (Negative-Advantage)11.93%
Masked Token Ratio (All Generated Tokens)5.08%
Mean Protected Prefix Length11.46 tokens
Mean Protected Prefix Length (Excl. Path Delimiters)10.41 tokens
Questions with Masking1,234 / 2,826
Question-Level Masking Coverage43.67%

The key metrics are calculated as follows:

  • Masking Activation Rate: Masked negative-advantage trajectories / Total negative-advantage trajectories.
  • Masked Token Ratio: Masked tokens / Valid generated tokens in negative-advantage trajectories.
  • Mean Protected Prefix Length: Masked tokens / Trajectories with masking.
  • Question-Level Masking Coverage: Questions with at least one masked trajectory / Total training questions.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.