SPARK: Unifying Structure-Aware Path-Prefix-Conditioned Tree Search and Graph-Grounded Generation for Knowledge Graph Question Answering

Knowledge Graph Question Answering requires retrieving compact and coherent multi-hop evidence from large-scale knowledge graphs and reasoning over it to produce accurate answers. Existing methods either invoke a large language model (LLM) repeatedly during graph exploration or use lightweight retrievers whose local decisions need not remain consistent with the full reasoning prefix. Furthermore, serializing graph evidence into verbose natural language weakens structural information and increases context length. We propose SPARK, which couples prefix-conditioned evidence retrieval with a graph-grounded generator. Its retriever factorizes each expansion into relation and entity decisions, scores each action jointly with the question and complete prefix, and labels an action as positive only when the extended trajectory remains a prefix of an answer path. For generation, we operationalize Knowledge Graph Language (KGL) as a question-specific interface that compactly encodes retrieved paths using a typed symbol dictionary and ordered symbol sequences; projected entity and relation representations replace the corresponding KGL-symbol embeddings in the LLM input. The two-stage collaborative training strategy further coordinates retrieval and generation through a shared graph encoder. Finally, extensive experiments on WebQSP and CWQ confirm that SPARK achieves significant performance gains compared to the state-of-the-art (SOTA) baselines.