Exploration-and-Thinking: Agentic Reasoning over Knowledge Graphs via an LLM-RL Synergized Framework
sigir26-125 · Full research paper · Yi Xia, Gang Zhou, Jing Chen, Xiaohui Chen, Qinlong Fan, Shunhang Li
KG-Augmented LLM Reasoning · 50% RL Training of Search Agents · 50%
Abstract
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.
Assigned reviewers
| # | Reviewer | Match | Why (closest evidence publications in the taxonomy) | |
|---|---|---|---|---|
| 1 | Farzad Shami | 61 | 68 Benchmarking Large Language Models for Knowledge Graph Validation (2026) KG-Augmented LLM Reasoning 68 Fact Verification in Knowledge Graphs Using LLMs (2025) KG-Augmented LLM Reasoning 43 GROKE: Vision-Free Navigation Instruction Evaluation via Graph Reasoning on OpenStreetMap (2026) Reasoning Evaluation and Benchmarks |
|
| 2 | Armin Toroghi | 55 | 68 LLM-based Typed Hyperresolution for Commonsense Reasoning with Knowledge Bases (2025) KG-Augmented LLM Reasoning 68 Verifiable, Debuggable, and Repairable Commonsense Logical Reasoning via LLM-based Theory Resolution (2024) KG-Augmented LLM Reasoning 64 CommonWhy: A Dataset for Evaluating Entity-Based Causal Commonsense Reasoning in Large Language Models (2026) Knowledge Graph Question Answering |
Area chair
| Area chair | Match | |
|---|---|---|
| Xiaoxi Li 0005 | 45 |
Area-chair candidates (2)
| Xiaoxi Li 0005 assigned | 45 | 15 papers | |
| Dacheng Tao | 37 | 5 papers |
Candidates from the panel ranked by match score
| # | Reviewer | Match | Load | Why | |
|---|---|---|---|---|---|
| 1 | Farzad Shami assigned | 61 | 3 | 68 Benchmarking Large Language Models for Knowledge Graph Validation (2026) KG-Augmented LLM Reasoning 68 Fact Verification in Knowledge Graphs Using LLMs (2025) KG-Augmented LLM Reasoning |
|
| 2 | Xingyu Tan 0001 | 58 | 3 | 67 Paths-over-Graph: Knowledge Graph Empowered Large Language Model Reasoning (2025) KG-Augmented LLM Reasoning 67 HydraRAG: Structured Cross-Source Enhanced Large Language Model Reasoning (2025) KG-Augmented LLM Reasoning |
|
| 3 | Armin Toroghi assigned | 55 | 3 | 68 LLM-based Typed Hyperresolution for Commonsense Reasoning with Knowledge Bases (2025) KG-Augmented LLM Reasoning 68 Verifiable, Debuggable, and Repairable Commonsense Logical Reasoning via LLM-based Theory Resolution (2024) KG-Augmented LLM Reasoning |
|
| 4 | Kaixin Ma | 47 | 3 | 68 WebEvolver: Enhancing Web Agent Self-Improvement with Co-evolving World Model (2025) RL Training of Search Agents 68 OpenWebVoyager: Building Multimodal Web Agents via Iterative Real-World Exploration, Feedback and Optimization (2025) RL Training of Search Agents |
|
| 5 | Ben Liu 0002 | 47 | 3 | 88 Plan Then Retrieve: Reinforcement Learning-Guided Complex Reasoning over Knowledge Graphs (2026) RL Training of Search Agents 68 SymAgent: A Neural-Symbolic Self-Learning Agent Framework for Complex Reasoning over Knowledge Graphs (2025) Reasoning Evaluation and Benchmarks |
|
| 6 | Jiapu Wang | 46 | 3 | 86 Large Language Models-guided Dynamic Adaptation for Temporal Knowledge Graph Reasoning (2024) RL Training of Search Agents 70 Unifying Large Language Models and Knowledge Graphs: A Roadmap (2024) KG-Augmented LLM Reasoning |
|
| 7 | Jialong Wu 0007 | 45 | 3 | 68 WebDancer: Towards Autonomous Information Seeking Agency (2025) Deep Research and Report Generation 68 Nested Browser-Use Learning for Agentic Information Seeking (2026) Deep Research and Report Generation |
|
| 9 | Yu Gu 0016 | 45 | 3 | 74 Middleware for LLMs: Tools Are Instrumental for Language Agents in Complex Environments (2024) KG-Augmented LLM Reasoning 67 HippoRAG: Neurobiologically Inspired Long-Term Memory for Large Language Models (2024) KG-Augmented LLM Reasoning |
|
| 10 | Xiaolong Jin 0001 | 42 | 3 | 68 A New Pipeline for Knowledge Graph Reasoning Enhanced by Large Language Models Without Fine-Tuning (2024) KG-Augmented LLM Reasoning 40 Hierarchical Query Graph Generation for Complex Question Answering over Knowledge Graph (2020) Knowledge Graph Question Answering |
|
| 11 | Qinggang Zhang | 41 | 3 | 66 KnowGPT: Knowledge Graph based Prompting for Large Language Models (2024) Multimodal and Graph RAG 53 Cost-efficient Knowledge-based Question Answering with Large Language Models (2024) Multi-hop and Complex Reasoning QA |
|
| 12 | Wonduk Seo | 41 | 3 | 43 SPIO: Ensemble and Selective Strategies via LLM-Based Multi-Agent Planning in Automated Data Science (2026) Multi-Agent and Tool-Use Orchestration 42 Automated Visualization Code Synthesis via Multi-path Reasoning and Feedback-Driven Optimizations (2026) Reasoning Evaluation and Benchmarks |
|
| 13 | Wenyu Huang | 40 | 3 | 66 Prompting large language models with knowledge graphs for question answering involving long-tail facts (2025) KG-Augmented LLM Reasoning 36 Masking in Multi-hop QA: An Analysis of How Language Models Perform with Context Permutation (2025) Multi-hop and Complex Reasoning QA |
|
| 14 | Farima Fatahi Bayat | 39 | 3 | 45 From Proof to Program: Characterizing Tool-Induced Reasoning Hallucinations in Large Language Models (2026) Reward Modeling and Process Supervision 31 FactBench: A Dynamic Benchmark for In-the-Wild Language Model Factuality Evaluation (2025) Automated Fact Checking and Claim Verification |
|
| 15 | Archiki Prasad | 38 | 3 | 46 PRInTS: Reward Modeling for Long-Horizon Information Seeking (2026) Reward Modeling and Process Supervision 44 System 1.x: Learning to Balance Fast and Slow Planning with Language Models (2025) Reward Modeling and Process Supervision |
|
| 16 | Haritz Puerto | 38 | 3 | 44 MetaQA: Combining Expert Agents for Multi-Skill Question Answering (2023) Retrieval-Augmented and Open-Domain QA 44 Code Prompting Elicits Conditional Reasoning Abilities in Text+Code LLMs (2024) Reward Modeling and Process Supervision |
|
| 17 | Xinying Qian | 37 | 3 | 55 TimeR⁴ : Time-aware Retrieval-Augmented Large Language Models for Temporal Knowledge Graph Question Answering (2024) Multi-Hop and Iterative Retrieval Reasoning 38 Contrast then Memorize: Semantic Neighbor Retrieval-Enhanced Inductive Multimodal Knowledge Graph Completion (2024) Knowledge Graph Embedding and Completion |
|
| 18 | Weiwei Sun 0001 | 37 | 3 | 59 Improving Retrieval-Augmented Generation through Multi-Agent Reinforcement Learning (2025) Agentic and Deep Search RAG 48 ReasonRank: Empowering Passage Ranking with Strong Reasoning Ability (2026) LLM-Based Reranking |
|
| 19 | Daiting Shi | 37 | 3 | 68 Reinforced Efficient Reasoning via Semantically Diverse Exploration (2026) RL Training of Search Agents 44 ReflectRM: Boosting Generative Reward Models via Self-Reflection within a Unified Judgment Framework (2026) Reward Modeling and Process Supervision |
|
| 20 | Tianzhe Zhao | 37 | 3 | 48 Logic-Aware Knowledge Graph Reasoning for Structural Sparsity under Large Language Model Supervision (2025) Graph Learning for Text-Attributed and Heterogeneous Networks 47 Self-supervised Quantized Representation for Seamlessly Integrating Knowledge Graphs with Large Language Models (2025) Text Representation and Language Models › Others |
|
| 22 | Yongqi Li 0001 | 36 | 3 | 61 R$^2$ec: Towards Large Recommender Models with Reasoning (2025) Preference Alignment and Optimization 44 Parallel Test-Time Scaling for Latent Reasoning Models (2026) Reward Modeling and Process Supervision |
|
| 23 | Qingyi Si | 36 | 3 | 44 Test-time Prompt Intervention (2026) Reward Modeling and Process Supervision 44 Outcome-Grounded Advantage Reshaping for Fine-Grained Credit Assignment in Mathematical Reasoning (2026) Reward Modeling and Process Supervision |
|
| 24 | Yuanzhao Zhai | 36 | 3 | 68 Extracting Reasoning Patterns from Knowledge Graph to Enhance LLMs' Reasoning Capability (2025) KG-Augmented LLM Reasoning 68 DART: Empowering LLM-Based Agents on Domain-Specific Tasks through Dynamic Augmented Reasoning Trees (2026) RL Training of Search Agents |
|
| 25 | Yuzhong Qu | 35 | 3 | 41 Enhancing Complex Question Answering over Knowledge Graphs through Evidence Pattern Retrieval (2024) Knowledge Graph Question Answering 41 Skeleton parsing for complex question answering over knowledge bases (2022) Knowledge Graph Question Answering |
|
| 26 | Dan Luo 0004 | 35 | 3 | 73 PAGER: Proactive Monitoring Agent for Enterprise AI Assistant (2026) Reasoning Evaluation and Benchmarks 67 From Anchors to Answers: A Novel Node Tokenizer for Integrating Graph Structure into Large Language Models (2025) KG-Augmented LLM Reasoning |
|
| 27 | Chen Zhao 0013 | 35 | 3 | 42 Beyond Single-shot Writing: Deep Research Agents are Unreliable at Multi-turn Report Revision (2026) Deep Research and Report Generation 37 SportReason: Evaluating Retrieval-Augmented Reasoning across Tables and Text for Sports Question Answering (2025) Multi-Hop and Iterative Retrieval Reasoning |
|
| 28 | Wenlin Zhang 0001 | 35 | 3 | 54 Process vs. Outcome Reward: Which is Better for Agentic RAG Reinforcement Learning (2025) Agentic and Deep Search RAG 53 To Search or Not to Search: Aligning the Decision Boundary of Deep Search Agents via Causal Intervention (2026) Agentic and Deep Search RAG |
|
| 29 | Xi Ye 0003 | 35 | 3 | 42 Beyond Single-shot Writing: Deep Research Agents are Unreliable at Multi-turn Report Revision (2026) Deep Research and Report Generation 42 MuSR: Testing the Limits of Chain-of-thought with Multistep Soft Reasoning (2024) Reasoning Evaluation and Benchmarks |
|
| 30 | Qisheng Hu | 35 | 3 | 44 Coordinating Search-Informed Reasoning and Reasoning-Guided Search in Claim Verification (2026) Automated Fact Checking and Claim Verification 36 Just What You Desire: Constrained Timeline Summarization with Self-Reflection for Enhanced Relevance (2025) Multi-hop and Complex Reasoning QA |
|
| 31 | Xuhui Sui | 35 | 3 | 71 TimeR⁴ : Time-aware Retrieval-Augmented Large Language Models for Temporal Knowledge Graph Question Answering (2024) RL Training of Search Agents 42 Beyond Timestamps: Bridging Forward and Backward Reasoning in Temporal Numerical and Relational Understanding (2026) Reasoning Evaluation and Benchmarks |
|
| 32 | Yingyi Zhang 0001 | 35 | 3 | 60 To Search or Not to Search: Aligning the Decision Boundary of Deep Search Agents via Causal Intervention (2026) Agentic and Deep Search RAG 54 Process vs. Outcome Reward: Which is Better for Agentic RAG Reinforcement Learning (2025) Agentic and Deep Search RAG |