- 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
-
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.
-
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
-
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.
-
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
-
What are the distributions of the generated path lengths, retrained path lengths and the number of beam candidates after relation-chain refinement?
-
What is the effect of entity-boundary termination alone?
-
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?
-
Could you report end-to-end inference cost, including question-specific subgraph construction, prefix-tree construction, constrained decoding, and relation-chain filtering?
-
How often does relation-chain refinement remove a correct candidate path or answer?
5 comments
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.
| Stage | Component | Average Latency (s/question) |
|---|---|---|
| Offline | Question-Specific Subgraph Construction | 3.00 |
| Offline | Prefix-Tree Construction | 4.29 |
| Offline | Subtotal | 7.29 |
| Online | Graph-Constrained Decoding | 3.10 |
| Online | Relation-Chain Refinement | 0.01 |
| Online | Subtotal | 3.11 |
| End-to-End | Total | 10.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
| Threshold | Gold-answer Candidates Removed | Gold-answer Proportion (%) | Affected Questions | Affected Questions (%) | Hit (%) | P (%) | R (%) | F1 (%) |
|---|---|---|---|---|---|---|---|---|
| w/o refinement | – | – | – | – | 90.1 | 67.0 | 82.7 | 74.0 |
| 0.5 | 130 | 1.02 | 97 | 2.75 | 89.8 | 80.7 | 81.5 | 81.1 |
| 0.7 | 338 | 1.67 | 228 | 6.46 | 85.9 | 84.7 | 72.5 | 78.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.
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.
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.
(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.
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.
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.
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.