Exploiting Verification Asymmetry for Failure-Aware Graph Reasoning in Knowledge Graph Question Answering with LLMs
TL;DR
This work introduces GRACE (Graph Reasoning with Adaptive Controller and Evidence), which feeds rejection back into retrieval and restores accept–reject symmetry in the search, and improves KG-grounded reasoning on WebQSP and ComplexWebQuestions.
Abstract
A standard verification-based knowledge graph question answering (KGQA) pipeline retains a reasoning path only when retrieved evidence supports it. Requiring evidence makes large language model (LLM) output easier to audit and reduces unsupported answers. The verifier’s two outcomes are not equally informative: acceptance provides strong evidence, whereas rejection on an incomplete graph may indicate either an incorrect path or a missing proof. A one-pass pipeline discards both cases and loses the information contained in the failure. We introduce GRACE (Graph Reasoning with Adaptive Controller and Evidence), which feeds rejection back into retrieval and restores accept–reject symmetry in the search. GRACE assigns a failure type to each rejected path. Its reflective feedback loop (RFL) revises subsequent retrieval, whereas hypothetical bridging (HB) admits budgeted and penalized virtual edges for plausible missing links. A virtual edge remains marked as a hypothesis rather than a verified triple; the bridge budget bounds answer-level hallucination exposure, and the marking makes that exposure observable. With a fixed open-source LLM backbone, GRACE improves KG-grounded reasoning on WebQSP and ComplexWebQuestions. Diagnostic results indicate that RFL and HB recover different types of failure.