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

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.