Faico: Faithful and Complete Knowledge Graph Augmented Reasoning

Large language models (LLMs) augmented with knowledge graphs (KGs) have exhibited great potential for complex reasoning tasks. However, existing approaches often struggle with incomplete subgraph retrieval and inaccurate semantic alignment, which hinder reasoning performance and answer quality. In this paper, we present Faico, a KG-enhanced reasoning framework designed to achieve both semantic faithfulness and structural completeness. Faico decouples model inference from graph traversal by integrating a fine-tuned LLM-based relation type generator for accurate semantic mapping and a KG retriever for reasoning subgraph search. Based on the predicted relation types, we model the reasoning subgraph (RS) as a k-bounded edge type (k-BET) subgraph, where k constrains the recurrence of relation types within paths, and devise a budget-dominance-based algorithm to efficiently identify the maximal k-BET subgraph. Our framework ensures comprehensive coverage of relevant multi-hop relations while reducing computational overhead. Through extensive experiments on multiple KGQA benchmarks, Faico demonstrates improvements in both effectiveness and efficiency over LLM-native and state-of-the-art KG-augmented reasoning baselines, delivering more accurate, complete answers and lower inference latency.