Research map / Large language models / Retrieval and knowledge

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

ICML 2025 · Large language models › Retrieval and knowledge · approach: Knowledge graph reasoning with LLMs · 1 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes KBQA-o1, an agentic KBQA method that uses ReAct-style tool-based logical form generation guided by MCTS with LLM policy and reward models, plus incremental fine-tuning on auto-annotated explorations, achieving strong low-resource results on GrailQA, WebQSP and GraphQ.

Problem

Low-resource knowledge base question answering with LLMs suffers from weak KB awareness, a trade-off between effectiveness and search cost in step-by-step methods, and heavy reliance on annotated logical forms.

Approach

Combines a ReAct-based agent with atomic KB query tools and Monte Carlo Tree Search driven by a policy model and a reward model (both fine-tuned LLMs, scored via output log-likelihood), then incrementally fine-tunes these models on high-reward MCTS explorations filtered for non-empty answers instead of human annotation.

Key results

• KBQA-o1 with Llama-3.1-8B reaches 78.5% overall F1 on GrailQA (40-shot), versus 48.5% for the previous best low-resource method ARG-KBQA with GPT-3.5-turbo.
• With Llama-3.3-70B, KBQA-o1 reaches 67.0% F1 on WebQSP (100-shot) and 50.5% F1 on GraphQ, versus 58.8% for ARG-KBQA on WebQSP.
• Removing incremental fine-tuning drops Llama-3.1-8B GrailQA overall F1 from 78.5 to 63.9, and removing MCTS drops it to 48.5.

Measured effects reported in the paper

Surprising findings

• Removing the initial annotated SFT collapses performance to about 13-17 F1, showing the exploration loop depends heavily on the seed policy and reward models.
• End-to-end variants outperform the step-by-step agent on in-distribution I.I.D and WebQSP, while the agent wins on compositional and zero-shot splits.

Limitations

• Limited fine-grained policy design and scalability to larger domains, as acknowledged in the Impact Statement.
• Relies on a small annotated seed set (40-100 questions) and on the quality of the reward filter for incremental data.
• Results are reported with GPT-3.5-turbo baselines only in low-resource settings, so comparison to stronger recent LLM baselines is limited.

Experimental setup

Datasets: GrailQA WebQSP GraphQ

Benchmarks: GrailQA WebQSP GraphQ

Metrics: F1 exact match queries per minute

Baselines: KB-BINDER KB-Coder ARG-KBQA RnG-KBQA DecAF TIARA ChatKBQA QueryAgent ToG

Builds on: ReAct Monte Carlo Tree Search KB-BINDER ARG-KBQA

Closest papers by meaning

• Promoting Knowledge Base Question Answering by Directing LLMs to Generate Task-relevant Logical Forms (AAAI 2025 · similarity 0.91)
• FlexKBQA: A Flexible LLM-Powered Framework for Few-Shot Knowledge Base Question Answering (AAAI 2024 · similarity 0.90)
• Cost-efficient Knowledge-based Question Answering with Large Language Models (NeurIPS 2024 · similarity 0.89)
• KG-Guard: Graph-Based Hallucination Detection for Knowledge Base Question Answering (NeurIPS 2026 · similarity 0.88)
• Code-Style In-Context Learning for Knowledge-Based Question Answering (AAAI 2024 · similarity 0.88)
• Diagnosing and Addressing Pitfalls in KG-RAG Datasets: Toward More Reliable Benchmarking (NeurIPS 2025 · similarity 0.87)