Exploration-and-Thinking: Agentic Reasoning over Knowledge Graphs via an LLM-RL Synergized Framework

While Knowledge Graphs (KGs) can ground Large Language Models (LLMs) in factual knowledge, existing LLM-KG integration methods for complex reasoning are plagued by computational inefficiency and semantic inconsistency. The tight coupling of LLM inference and KG traversal leads to prohibitive costs, while spurious reasoning paths often misguide learning-based agents, causing reward hacking. To this end, we propose EAT (Exploration-and-Thinking), a novel agentic framework that synergizes LLMs with Reinforcement Learning (RL) for efficient and faithful reasoning on KGs. EAT's core innovations are twofold: (1) an adaptive retrieval-augmented generation mechanism that decouples language comprehension from structured exploration, dramatically improving efficiency; and (2) an LLM-guided reward shaping strategy that explicitly penalizes semantically inconsistent paths and promotes logically valid trajectories grounded in the KG. Extensive experiments on benchmarks like WebQSP, CWQ, and GrailQA show that EAT achieves state-of-the-art performance. Notably, it surpasses the reasoning capability of GPT-4o while utilizing a significantly smaller 8B-parameter LLM.