Structure Pruning With LLMs for Knowledge Graph Question Answering

Abstract

Knowledge Graph Question Answering (KGQA) requires multi-step reasoning over a large, structured search space, where free-form LLM planning can hallucinate intermediate subgraphs or query sketches and yield unexecutable reasoning. We propose READS, a constraint-guided discriminative reasoning framework that makes KGQA controllable by reformulating it into subgraph search, constraint-based pruning, and answer selection, and solving each step via selection over KG-grounded options rather than open-vocabulary generation. READS constructs a token-level constrained decoding tree from KG-reachable candidates and uses LLM scoring to traverse and prune the search space, improving executability and faithfulness. READS obtains training supervision by parsing annotated SPARQL queries, assuming benchmark-provided topic entities. On WebQSP and CWQ, READS achieves 0.840/0.845 and 0.802/0.820 in Hits@1/F1, outperforming strong LLM-based baselines.