LLM-Driven Progressive Semantic Verification with Intermediate-State Transitions for Multi-Hop Knowledge Graph Question Answering

Complex multi-hop knowledge graph question answering requires models to maintain reliable intermediate states while reasoning over multiple relations. Existing methods primarily emphasize subgraph retrieval and candidate relevance scoring, while the semantic eligibility of model-generated intermediate entities is often left implicit during inference. Consequently, a structurally plausible candidate may be used to update the reasoning state even when it does not satisfy the current local objective. To address this issue, we propose ProVeST, a progressive semantic verification framework with gated state transitions. ProVeST converts a complex question into dependent sub-questions, applies question-conditioned structural scoring to screen candidate entities, and uses a large language model (LLM) to verify each retained entity together with its path context. Only verified entities can update the next-hop reasoning state. Experiments with three LLM backbones on WebQuestionsSP (WebQSP) and ComplexWebQuestions (CWQ) demonstrate the applicability of ProVeST.