Interactive Semantic Parsing with Reinforcement Learning for Knowledge Graph Reasoning

While large language models (LLMs) have achieved remarkable success, their reliability in knowledge-intensive tasks is often compromised by factual hallucinations. Integrating Knowledge Graphs (KGs) addresses this issue; however, existing approaches typically rely on simple graph traversal. This paradigm decouples topological navigation from logical operations (e.g., temporal filtering, aggregation), leading to imprecise retrieval and heavy post-processing burdens. Although semantic parsing offers a solution by grounding reasoning in logical forms, it traditionally suffers from a dependency on scarce supervised annotations. To bridge this gap, we propose Interactive Semantic Parsing, a framework that formulates reasoning as the sequential generation of executable logical clauses. This design allows logical constraints to be dynamically interleaved with graph search, while optimizing via reinforcement learning with only final answer feedback eliminates the need for gold program annotations. To tackle the sparse reward challenge in the vast symbolic space, we introduce a distance-aware process reward to evaluate intermediate steps based on their topological proximity to the answer. Experimental results on WebQSP and CWQ demonstrate that our method achieves state-of-the-art performance, particularly on complex queries, validating the effectiveness of our dense reward signal in enabling robust reasoning without supervision. Our code is available at https: //github.coms/NUSTM/ISP-KGR.