# KBQA-o1: Agentic Knowledge Base Question Answering with Monte Carlo Tree Search

arXiv: https://arxiv.org/abs/2501.18922 · HTML: https://mlsanity.com/paper/2501.18922/

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- Placed in Web, search, and research agents, one of 16 directions in LLM agents and tool use.
- Builds on 23 of its 37 references that are in the map.
- First posted on arXiv 31 Jan 2025.

## Placed in

- LLM agents and tool use / [Web, search, and research agents](https://mlsanity.com/agents/web-search-and-research-agents/)

## Builds on (most cited first, 23 of 23)

- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [Let's Verify Step by Step](https://mlsanity.com/paper/2305.20050/) (2023)
- [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023)
- [SimCSE: Simple Contrastive Learning of Sentence Embeddings](https://mlsanity.com/paper/2104.08821/) (2021)
- [Reasoning with Language Model is Planning with World Model](https://mlsanity.com/paper/2305.14992/) (2023)
- [Reasoning on Graphs: Faithful and Interpretable Large Language Model Reasoning](https://mlsanity.com/paper/2310.01061/) (2023)
- [Chain of Thought Empowers Transformers to Solve Inherently Serial Problems](https://mlsanity.com/paper/2402.12875/) (2024)
- [PullNet: Open Domain Question Answering with Iterative Retrieval on Knowledge Bases and Text](https://mlsanity.com/paper/1904.09537/) (2019)
- [Beyond I.I.D.: Three Levels of Generalization for Question Answering on Knowledge Bases](https://mlsanity.com/paper/2011.07743/) (2020)
- [Open Domain Question Answering Using Early Fusion of Knowledge Bases and Text](https://mlsanity.com/paper/1809.00782/) (2018)
- [Monte Carlo Tree Search: A Review of Recent Modifications and Applications](https://mlsanity.com/paper/2103.04931/) (2021)
- [Subgraph Retrieval Enhanced Model for Multi-hop Knowledge Base Question Answering](https://mlsanity.com/paper/2202.13296/) (2022)
- [Medical Graph RAG: Towards Safe Medical Large Language Model via Graph Retrieval-Augmented Generation](https://mlsanity.com/paper/2408.04187/) (2024)
- [RnG-KBQA: Generation Augmented Iterative Ranking for Knowledge Base Question Answering](https://mlsanity.com/paper/2109.08678/) (2021)
- [DecAF: Joint Decoding of Answers and Logical Forms for Question Answering over Knowledge Bases](https://mlsanity.com/paper/2210.00063/) (2022)
- [Few-shot In-context Learning for Knowledge Base Question Answering](https://mlsanity.com/paper/2305.01750/) (2023)
- [TIARA: Multi-grained Retrieval for Robust Question Answering over Large Knowledge Bases](https://mlsanity.com/paper/2210.12925/) (2022)
- [Don't Generate, Discriminate: A Proposal for Grounding Language Models to Real-World Environments](https://mlsanity.com/paper/2212.09736/) (2022)
- [ArcaneQA: Dynamic Program Induction and Contextualized Encoding for Knowledge Base Question Answering](https://mlsanity.com/paper/2204.08109/) (2022)
- [Large Language Models-guided Dynamic Adaptation for Temporal Knowledge Graph Reasoning](https://mlsanity.com/paper/2405.14170/) (2024)
- [QueryAgent: A Reliable and Efficient Reasoning Framework with Environmental Feedback-based Self-Correction](https://mlsanity.com/paper/2403.11886/) (2024)
- [Code-Style In-Context Learning for Knowledge-Based Question Answering](https://mlsanity.com/paper/2309.04695/) (2023)

## Built on by (most cited first, 22 of 22)

- [Graph-R1: Towards Agentic GraphRAG Framework via End-to-end Reinforcement Learning](https://mlsanity.com/paper/2507.21892/) (2025)
- [Synergizing RAG and Reasoning: A Systematic Review](https://mlsanity.com/paper/2504.15909/) (2025)
- [SQL-o1: A Self-Reward Heuristic Dynamic Search Method for Text-to-SQL](https://mlsanity.com/paper/2502.11741/) (2025)
- [LLM/Agent-as-Data-Analyst: A Survey](https://mlsanity.com/paper/2509.23988/) (2025)
- [Sailing by the Stars: A Survey on Reward Models and Learning Strategies for Learning from Rewards](https://mlsanity.com/paper/2505.02686/) (2025)
- [Prompt-R1: Collaborative Automatic Prompting Framework via End-to-end Reinforcement Learning](https://mlsanity.com/paper/2511.01016/) (2025)
- [Reason-Align-Respond: Aligning LLM Reasoning with Knowledge Graphs for KGQA](https://mlsanity.com/paper/2505.20971/) (2025)
- [Compiler-R1: Towards Agentic Compiler Auto-tuning with Reinforcement Learning](https://mlsanity.com/paper/2506.15701/) (2025)
- [DAMR: Efficient and Adaptive Context-Aware Knowledge Graph Question Answering with LLM-Guided MCTS](https://mlsanity.com/paper/2508.00719/) (2025)
- [GraphWalker: Agentic Knowledge Graph Question Answering via Synthetic Trajectory Curriculum](https://mlsanity.com/paper/2603.28533/) (2026)
- [OmniRAG-Agent: Agentic Omnimodal Reasoning for Low-Resource Long Audio-Video Question Answering](https://mlsanity.com/paper/2602.03707/) (2026)
- [Weak-to-Strong GraphRAG: Aligning Weak Retrievers with Large Language Models for Graph-based Retrieval Augmented Generation](https://mlsanity.com/paper/2506.22518/) (2025)
- [KBQA-R1: Reinforcing Large Language Models for Knowledge Base Question Answering](https://mlsanity.com/paper/2512.10999/) (2025)
- [Token-Guard: Towards Token-Level Hallucination Control via Self-Checking Decoding](https://mlsanity.com/paper/2601.21969/) (2026)
- [Cognitive Models and AI Algorithms Provide Templates for Designing Language Agents](https://mlsanity.com/paper/2602.22523/) (2026)
- [NS-VLA: Towards Neuro-Symbolic Vision-Language-Action Models](https://mlsanity.com/paper/2603.09542/) (2026)
- [Pandora: Leveraging Code-driven Knowledge Transfer for Unified Structured Knowledge Reasoning](https://mlsanity.com/paper/2508.17905/) (2025)
- [MAXS: Meta-Adaptive Exploration with LLM Agents](https://mlsanity.com/paper/2601.09259/) (2026)
- [Magellan: Guided MCTS for Latent Space Exploration and Novelty Generation](https://mlsanity.com/paper/2510.21341/) (2025)
- [OrchMAS: Orchestrated Reasoning with Multi Collaborative Heterogeneous Scientific Expert Structured Agents](https://mlsanity.com/paper/2603.03005/) (2026)
- [Reward on Path: Learning Intermediate Supervision Signals for Knowledge Graph Question Answering](https://mlsanity.com/paper/2605.10791/) (2026)
- [When LLM Meets Tree Search: A Systematic View of Inference as Search in Large Language Models](https://mlsanity.com/paper/2608.30395/) (2026)

## Abstract (arXiv)

Knowledge Base Question Answering (KBQA) aims to answer natural language questions with a large-scale structured knowledge base (KB). Despite advancements with large language models (LLMs), KBQA still faces challenges in weak KB awareness, imbalance between effectiveness and efficiency, and high reliance on annotated data. To address these challenges, we propose KBQA-o1, a novel agentic KBQA method with Monte Carlo Tree Search (MCTS). It introduces a ReAct-based agent process for stepwise logical form generation with KB environment exploration. Moreover, it employs MCTS, a heuristic search method driven by policy and reward models, to balance agentic exploration's performance and search space. With heuristic exploration, KBQA-o1 generates high-quality annotations for further improvement by incremental fine-tuning. Experimental results show that KBQA-o1 outperforms previous low-resource KBQA methods with limited annotated data, boosting Llama-3.1-8B model's GrailQA F1 performance to 78.5% compared to 48.5% of the previous sota method with GPT-3.5-turbo. Our code is publicly available.