Fine-grained Stateful Knowledge Exploration: Effective and Efficient Graph Retrieval with Large Language Models

Large Language Models (LLMs) have shown impressive capabilities, yet updating their knowledge remains a significant challenge, often leading to outdated or inaccurate responses. A proposed solution is the integration of external knowledge bases, such as knowledge graphs, with LLMs. Most existing methods use a paradigm that treats the whole question as the objective, with relevant knowledge being incrementally retrieved from the knowledge graph. However, this paradigm often leads to a granularity mismatch between the target question and the retrieved entities and relations. As a result, the information in the question cannot precisely correspond to the retrieved knowledge. This may cause redundant exploration or omission of vital knowledge, thereby leading to enhanced computational consumption and reduced retrieval accuracy. To address the limitations of coarse-grained knowledge exploration, we propose FiSKE, a novel paradigm for Fine-grained Stateful Knowledge Exploration. FiSKE first decomposes questions into fine-grained clues, then employs an adaptive mapping strategy during knowledge exploration process to resolve ambiguity in clue-to-graph mappings. This strategy dynamically infers contextual correspondences while maintaining a stateful record of the mappings. A clue-driven termination mechanism ensures rigorous augmentation--leveraging fully mapped paths for LLMs while reverting to chain-of-thought reasoning when necessary. Our approach balances precision and efficiency. Experiments on multiple datasets revealed that our paradigm surpasses current advanced methods in knowledge retrieval while significantly reducing the average number of LLM invocations.