KBQA-o1: Agentic Knowledge Base Question Answering with Monte Carlo Tree Search
Authors: Haoran Luo
Haihong E
Yikai Guo
Qika Lin
Xiaobao Wu
Xinyu Mu
Wenhao Liu
Meina Song
Yifan Zhu
Anh Tuan Luu
Venue: ICML 2025 poster (2025)
Keywords: Knowledge Base Question Answering
Large Language Model
LLM Agents
Monte Carlo Tree Search
Primary area: applications->language_speech_and_dialog
TL;DR: We propose KBQA-o1, an agentic KBQA method with Monte Carlo Tree Search.

Abstract: 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.

KBQA-ol: Agentic Knowledge Base Question Answering with Monte Carlo Tree Search
Haoran Luo!!
Haihong E.
Yikai Guo
Qika Lin
Xiaobao 2u Xinyu Mu Luu Anh Tuan
Wenhao Liu'
Meina Song'
Yifan Zhu
Abstract
Freebase
Question
What mose with a televtsce nunning tins of less ranutes festures Tayler Loatner?
Knowledge Base Question Answering (KBQA) aims to answer natural language questions with large-scale structured knowledge base (KB). De- spite 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-ol, novel agentic KBQA method with Monte Carlo Tree Search (MCTS). It introduces 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 agen- exploration's performance and search space. With heuristic exploration, KBQA-ol generates high-quality annotations for further improvement by incremental fine-tuning, Experimental results show that KBQA-ol outperforms previous low- resource KBQA methods with limited annotated data, boosting Llama-3. 1amma-3.1--3 -.B 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 at http:p:///gghbb//// com/ HOmmLHRRLABKBOOA-OL.
ExtracL_cntity
Extract antity
KB
->
Envir ronment
Find rebotion
(fimaactiofflm
USS THAN Soby goppen.
Explanation
Observattas
Find relation
Nerge
flmmperformanne--lii
KBQA Agent
Logical
(AND (lttct opinnn.ppieek.. ramning lins unnN (8 min pertensere fhan
Query
Figure An example of KBQA task to answer natural language question by exploring the KB environment with KBQA agent.
2024), and legal analysis (Cui et al., 2023). Typically, KBs are stored in graph databases and accessed using graph queries, such as SPARQL (Pérez et al., 2009), which sup- port multi-hop and logical queries to acquire knowledge in- formation. To answer natural language questions, language models usually leveraged (Ye al., 2022) convert the questions into logical forms, such S-expression (Gu et al., 2021), and then transform them into executable graph queries to obtain answers from KB, as shown in Figure 1.
With the emergence LLMSs (OpenAI, 2024; Dubey et al., 2024), two main types of KBQA methods appear, as shown in Figure On the one hand, end-to-end methods (Luo et al., 2024b;a) generate logical forms directly from natural language questions and utilize retrieval before after gen- eration for improvement. On the other hand, step-by-step methods (Huang et al., 2024; Sun et al., 2024) alternate be- tween generation and retrieval for stepwise thinking on KB, performing in a Chain-of-Thoure or Tree-of- (ToT) (Yao et al., 2023a) manner.
1. Introduction
Knowledge Base Question Answering (KBQA) leverages large-scale structured knowledge base (KB), such Free- base (Bollacker et al., 2008) or Wikidata (Vrandečié & Krötzsch, 2014), reference to answer questions in nat- ural language, widely applied in fields such as search en- gines (Jang et al., 2017), medical consultations (Wu et al.,
(CoT) (Wei et al., 2022)
'Beijing University of Posts and Telecommunications "Nayyang Technological University Beijing Institute of Computer Technology and Application "National University of Singapore. Correspondence to: Haihong E <chaihong @ bupt.cdu.cn
However, three main challenges remain: (1) Poor aware- ness of the KB environment in end-to-end methods. Re- lying on direct logical form generation by language models, end-to-end KBQA methods (Li et al., 2023; Nie et al., 2024) struggle with limited logical form schemas and unseen en- tities and relations that existed in KB, making it difficult to fully capture the KB environment. (2) Local optima
Proceedings of the ndnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

KBQA-o1: Agentic Knowledge Base Question Answering with Monte Carlo Tree Search
End-to-end LLM-based KBQA Methods
Stey-by-step LLM--based KBQA Methods
Heuristic LLM-based KBQA
Performunet Coattgh
Input Question
Input Question
Input Question
Input Question
Input Question
LLM
LLM
LLM
KB
LLM
Step1
State
State
Staley
LLM
LLM
LLM
Perfensaae Welgger
Step2
State
Stateg
Statey
Reference
Logical Form
reward
simulate
LLM
MLM
LLLM
LLM
KB
StepN
States
State
KB
KB
KB
Answers
Answers
Answers
Answers
Answers
Retrieve-then-Cane Sariivee-hhe--Geerttee Generate Rhen--eee--Ree
CoT-based
ToT-based
Agentic MCTS-based
Figure 2. Comparison of the previous end-to-end KBQA framework, including retrieve terieve-then-aeee sereeetheeggeeeeeee generate (RG) and generate- snteeatee-hen-vee metrivetrieve (GR) methods, step-by-step KBQA methods, including CoT- and ToT- methods, and our proposed heuristic KBQA method, which is agentic MCTS-based With the same Llama-3. 1-BB (Dubey et al., 2024) the base model, both the MCTS-based agent process and the full KBQA-ol after the incremental fine-tuning show improvements on all three KBQA datasets.
or large search space in step-by-step methods. Com- pared to end-to-end methods, CoT-based step-by-step meth- ods (Huang et al., 2024) in the search process can lead to local optima due to intermediate bias. Although ToT-based methods (Sun et al., 2024) expand search options, tree-like searches still face challenges with large search spaces. (3) Training depends on high-quality annotation. Training open-source L.MMs (Luo et al., 2024a) significantly con- tributes to the generation of logical forms for KBQA tasks, but this heavily relies on the quality of the annotated data. For large-scale KBs, producing substantial, high-quality annotated data by human labor is impractical.
models, especially in more difficult cases like composi- tional and zero-shot. Ablation studies further validate the proposed MCTS- agent process and incremental fine- tuning, both of which make KBQA-o1 outperform other forms of KBQA methods, as shown in Figure 2. In addition, KBQA-ol supports multiple open-source LLMs, including Llama-3 (Dubey et al., 2024), Qwen2.5 (Yang et al., 2025) and Gemma-2 (Team et al., 2024), making it plug-and-play and promising solution for diverse KBQA applications.
2. Related Work
Knowledge Base Question Answering. Before the rise of LLMs, KBQA methods could be divided into information- retrieval-basee (IR-based) (Sun et al., 2018; 2019; Zhang et al., 2022) and semantic-parsinn et al., 2022: Shu et al., 2022). In the era of LLMs, LLM- based KBQA methods can be divided into two categories: end-to-end and step-by-step. End-to-end methods take ad- vantage of in-context learning (ICL) (Li et al., 2023; Nie et al., 2024) or fine-tuning (Luo et al., 2024b;a) to enable LLMs to generate queries. The step-by-step methods (Gu et al., 2023; Sun et al., 2024; Huang et al., 2024) follow a reasoning process on the graph to gradually find the answers. In this paper, we propose the first heuristic KBQA method.
To address these challenges, we propose KBQA-ol, novel agentic KBQA approach with heuristic exploration of the KB environment, as shown in Figure 1. First, we design a ReAct-based (Yao et al., 2023b) agent process with atomic query tools to generate logical forms by fully interacting with the KB environment. Moreover, we employ Monte Carlo Tree Search (MCTS) (Swiechowski et al., 2022), driven by policy and reward models, to optimize the agent process from local optima or large search space. Further- more, to mitigate reliance on extensive human annotation, we first fine-tune the policy and reward models only using a small amount of sample-laheled data. For unlabeled ques- tions, we employ MCTS exploration with the reward model filter instead of human labor to generate abundant, auto- annotated data, further enhancing the capabilities of both the policy and reward models by incremental fine-tuning.
based (SP-based) (Ye
LLMs and LLM-powered Agent. LLMs have shown sig- nificant advantages in generation and reasoning (Wang et al., 2024). Powered by CoT(Wei et al., 2022; Li et al., 2024), guiding LLMs to think step by step can further enhance reasoning capabilities. ReAct (Yao et al., 2023b) introduces a prompt-based agent, using tools to interact with the envi- ronment. Lightman et al. (2024) verifies CoT by rewarding the process and outcome. On the other hand, expand the thought space in every step, ToT (Yao et al., 2023a) rea- sons in tree-like manner. RAP (Hao et al., 2023) employs MCTS, a heuristic algorithm applied in AlphaGo.
We perform experiments on three KBQA datasets, GrailQA (Gu et al., 2021), WebQSP (Yih et al., 2016) and GraphQ (Su et al., 2016) in low-resource settings (Li et al., 2023) for application with limited annotated data. Experi- mental results demonstrate that KBQA-o1 outperforms isting low-resource KBQA methods and even approaches or surpasses the performance of fully supervised KBQA
2

---

KBQA-o1: Agentic Knowledge Base Question Answering with Monte Carlo Tree Search
Table 1. Description of proposed atomic query tools and corresponding arguments, where M. = {maz, min), and M. = {<, S, are mode sets of Order and Compare. By using tools, the agent can obtain the target functions and equivalent logical forms accordingly.
Atomic Query Tool
Arguments
Target Function
Equivalent Logical Form
Exctccctnntitt lentiy]
entiry E
expression START('entit" eentity)
entity
Find_rel in relation] ]
relaiton E R.
expression JOIN( rrelation,, expression)
(IOIN relation (expression))
Marge [ expression | expression
expression.. expression mode E Ma, relation R. mode E Ma, relation E R relation R. time E
expression = ANDiespressionl expression)
(AND (expressionl) (expression)
Order [ mode mlatioo]]
expression ARG( (aG((mmoe",, expression, 'miation')
(mode (expression) relation)
Compazee [ mode| relation] ]
expression CMP( "relation' expression)
(mode relation (expression)
Time constraing reeation| time] Count [ expression
expression TClexpression. 'reiation', 'sime")
(TC (expression) relation time)
expression
expression COUNTeepression)
(COUNT (expression))
Finish expression
expression
expreszion expr(sxprsss)oo)
(expression)
3. Preliminaries
State Update (h,): At each step I, the state incorpo- rates the latest exploration step, which is prompted as ReAct-based (Yao et al., 2023b) Thought-Action- Observation tuple e, (e ettt egeo)) as shown in Appendix A.2, to update: h, h1-1 + e..
Definition I: Knowledge Base. A knowledge base (KB) is
a large-scale knowledge graph 9 = (E, R, T), composed of an entity set E, relation set R. and a triple set T. Relations in the relation set r E R. are used to connect two entities. Each triple (s,r, r) E T is formed by (entity, relation, en-
State Representation (Fr,):: Besides prompt-based history, the cumulative Observations in the trajectory
tity), thus T- [(sTT,)]ss E E,r E R, o E E}.
(efts :e...... eghe determine the function list, which is equivalent the logical form Ph. = [e -==-
Definition 2: Logical Form. The logical form F is a multi-hop expression that can convert equally to a graph query g = Convert(F). Each logical form can be divided into a stepwise list of functions F = [f with I steps.
The Agent Exploration Space Exp(H, g). The agent ex- ploration e, E Exp(h,-1, is dynamically determined by the last state h E H and the KB environment G. Each exploration comprises the following components:
Problem Statement. In the KBQA task, given natural language question Q and KB G, the goal is to first convert Q into a logical form F, and then an executable graph query Once executed, the result A = Exec(g. 9) is a set of entities in the KB A C & that answer the question Q.
Tool Selection (e Based on h the agent selects one of the eight atomic query tools as shown in Table 1.
Argument Determination (e.")): The agent identifies the appropriate arguments for the selected tool, lever- aging the candidates provided by the KB environment. For example:
4. Method: KBQA-o1
In this section, we introduce the three components of KBQA- ol: agent initialization, heuristic environment exploration using MCTS with policy and reward models to optimize the agent process, and incremental fine-tuning with auto- annotated data to improve low-resource performance.
Calling Extract.entity requires specifying an entity name existed 9 as the argument.
Caalling F Find_re redd_rell relat i on involves specifying a relation name that has a connection with Fi, 1
4.1. Agent Initialization
Function Writen (e Based on the selected tool and arguments, the agent writes down the correspond- ing target function in Observation, referred to Table 1.
KBQA-o1 follows a ReAct-based (Yao et al., 2023b) agent prompt, with KB environment, the agent state space and exploration space, targeting to generate logical forms.
The Agent Target (hr, Fn, ). The agent explores the exploration space until calling the F Fini sh tool or when the length of the function list exceeds the maximum allowable length < L. The ultimate target of the agent is to find a complete state h, which forms a logical form Fi, and the final answers executed An. = Exee (Convert F,,), Proposition 4.1. The agent's 's awareness of the environment makes it more effective in generating optimal logical forms compared to end-to-end methods.
KB Environment G. We consider KB critical environment that provides guides in generating the logical form at each step of the agent, for example, by providing the candidate relations connected to the current state of the logical form.
The Agent State Space H. The agent state h, E H is defined by its exploration history as h, = (ho, ei, e.).
Initial State (ha): We create an initial prompt, consist- ing of the task description and the given question Q, as the initial state he, as shown in Appendix A.
Proof. We provide quantitative experimental results in Sec- tion 5.4 and qualitative proofs in Appendix 1.
LI
3

---

KBQA-o1: Agentic Knowledge Base Question Answering with Monte Carlo Tree Search
hy
What television running
minutes features Taylor Loutner?
LEGENDS
70.14
Thought1: step, should identify tapic extity
Selection
bi
Actiont: eetrac__enll "layorr Lautner
from question start new exoression.
Observation1: expression- START(
Environment
Expension
Q: 99.99.
Thought2: At this stap, we should find the ane-hap relation that is connectedd to the aumennt exgression:
Thought2: At this stop, we should find the ane-hap reaaton
Sinulation
ba
Action2:
Find reletion [ fiimastorfim
Action2:
Find, reletion [ bibbr actonstariig roles]
that is connactied to the piment expressio.
Observation2: expression JRINC(R aim. expression)
Obsorvation:: scrresan JUIN bebs, aeterstaringg rolle, sxprearoo)
Back propogation
90.97
Thought3: stop, should identify entlyy
Thought3: this step, should find hop
K3 Environment
b
from question new expression.
that connected current expresiion.
Sectect_enttyy
Action3: relatio hwt.ippefffi reformmnce
Observation3: expressionl START(60)
Observation3: exoression IR fllm pemfommace..immm expression)
Policy Model
Pollcy Model
Pollcy Model
Pollcy Model
D: 73.61
O: 89.99
Reward Model 75.82
Thoughts: this stop, we conctudo that it agprapriate to end and outout the expres eoseesio..
Thought7: At this stop, we conclude that if approprtate to and and output the expression.
by
ActionS: Finish [ [xpression] ]
Action?: Finish [ [espresion)
Reward Model
ObservationS: expresston1 STOP(cxpression))
Observation:: expression STOR(espresioon)
Q 7671.
Logical
bock pptpraa.ppaadd.cccoom parstng line ba)
Reword Model
Logical Form
(AND (t tv prigonn glocke noring Sine 60) Reward
Q-velue
(JOIN (K firtacder din Yaylor Lauinriil
Figure 3. An example of the hcuristic KB environment exploration with MCTS driven by policy and reward models.
4.2. Heuristic Environment Exploration
4.2.3. MONTE CARLO TREE SEARCH OVER KB
As shown in Figure address the issue of the step-by-step agent falling into local optima or large search spaces, we design an MCTS-based heuristic environment exploration method, driven by a policy model and a reward model.
MCTS is heuristic search algorithm in the form of tree, where each node represents a state in the agent process. Starting from the initial state (the root node), the algorithm uses four stages of selection, expansion, simulation, and back-propagation to explore and enrich the search tree it- eratively. MCTS conducts a total of N search rollouts. In the n-th rollout (n = 1,.., NN), the agent process can be represented by the trajectory of agent states { [lb"" "
1.2.1. THE POLICY MODEL
The policy model aims to provide the agent with a forward- looking capability. We use the last state at each step h from the annotated training set D. as input, and the steps from the current state to the conclusion (cc...., e2) as output, forming SFT data for training the policy model Tpolicy:
Selection. When new MCTS rollout begins, the agent process starts from the root node and progressively searches down through the child nodes of the already explored tree until it reaches leaf node. At each level, the UCT (Upper Confidence Bound applied to Trees) (Swiechowski et al., 2022) algorithm is used to select the next child node:
1
OsPr(TTpolicy D.) -EE. log policy
Σ
e,l he-1 im
In ((b
4.2.2. THE REWARD MODEL
e, f- arg max (EE()(2) Q(1 +0) + w
N(b +
The reward model aims to assess the entire trajectory by scoring the final logical form. We use the question Q as input, and the logical form Fb, from the annotated training set D. as output, forming SFT data for training the reward model Treward:
where N.) is the visit counts of the agent state during the MCTS process, E(.) is the candidate expansion of Thought- Action-Observation explorations, derived from Equation (7), and Q(-) is the Q-value of the agent state, which will be updated by back paok-propagation. UCT balances the selection of high-scoring nodes with the exploration of unvisited ones. The variable controls the tendency towards exploration. A larger encourages exploration of nodes with fewer visits, while smaller biases nodes with higher scores.
(rew(Frewadd D.) = EE.. [log Treward (Fiy [)),
(2)
Moreover, we employ a scoring method R2 that uses the logits from the LLM n, which can be pololcyy or Treward, to evaluate the likelihood of output y, given input æ:
(y x) 3 + log (y x².
(3)
Expansion. Once the selection process reaches a leaf node but not in a terminal Finish state and is not beyond the maximum depth I., the policy model policy generates
where is the defined full score, set as 100, and a is a positive temperature to control the disparity of scores.

---

KBQA-o1: Agentic Knowledge Base Question Answering with Monte Carlo Tree Search
several possible next states by beam search:
4.2.4, FINAL TRAJECTORY CHOSEN
{er 1==1 ~ Epolicy Cx
h (m)
(5)
After MCTS completes its exploration for N rollouts with
beam
parameter set 0, we select the trajectory hff E (b)") Jn=i [b[")
where B is the beam size. To engage with KB environment, we utilize an unsupervised retrieval model, SimCSE (Gao et al., 2021), to match the generated explorations with the exploration options e E Expph(_1.9)
with the highest Q-value in every state in the expanded search tree as the optimal trajectory of question Q:
(m) 9) that are executable
(h,, Fe A MCTS, (2, :Tpllicy Treward): (11)
over KB G when connected with the last state hm
where fe is corresponding logical form of lif and Ae = (xxeerCoveet((" ( 9) is the executed answers.
(e h= arg max" {e)
(n) (.9) SimCSE (e) )= (
octap(h)")
Proposition 4.2. The MCTS-based heuristic method bal- ances the effectiveness and size of the search space better than Co'--based and ToT-based step-by-step methods.
(6)
For example. if the ground truth is Find.relation [ file.actor.film I' the model might initially generate 'I film.actor Jr. Then, we select the most semantically related action options from Exp(h,_), 9) such as '[ file.actor.fllm I' and '[ tv.tv actorst roles J' to filter the top & explo-
Proof. We provide quantitative experimental results in Sec- tion 5.4 and qualitative proofs in Appendix B.2.
rations {er (3) 1-=1-
4.3. Incremental Fine-Tuning
Then, the policy model Tpolicy scores the k candidates based on the previous state (,22) and selects the top d candidates as expanded options E(h(")), which are added as child nodes to the leaf node, thus expanding the tree:
In addition to training on annotated data, KBQA-ol em- ploys MCTS with exploration incentives eepp for heuristic exploration on unannotated questions Q Dn:
{Lh, F ( {MCTS (C, Poolicy Freward) P.
E( = (e 3 <- arg max" Reonny ((e
h (1)
(12)
Then, we discard the annotation by choosing if the answer set is not empty and the reward score of logical form does not exceed a threshold y":
Simulation. After the nodes are expanded, the policy model assigns scores to all newly added child nodes. The node with the highest prospective score is selected:
Re
Rrioud (De10)
(13)
e, c arg max (EE()(")) Rrpaacy (e|n(m)).
(8)
D. - D. ( 1 HonR 72)
RED Combined with the original annotated data Da. the incre- mental data Dj is then used for incremental fine-tuning of the policy and reward models:
and the simulation continues to explore the process until the final finish state, producing a complete logical form generation trajectory.
(14)
Back- ppopaaaopag Once the final state is reached, the reward model Freward evaluates the entire trajectory by as- sessing the corresponding logical form combined with the policy model's score from the last step to compute the over- all Q-value of the final state:
LSFT D.) = -Eo, Σ log mpolicy Σ
es h
(iS)
CSrr(Trewan) D.) EE, [log Freward (Fiy @)]
(16)
Q(h(()) + 8 Hagany (er (1/ (11-)) 8) Hanens (F250)) 2)
Through incremental fine-tuning, the policy and reward models gain enhanced understanding of the environment and a preference for high-reward logical form trajectories. Finally, we perform testing Dr under efficiency-focused MCTS parameter settings det. yielding final answers Ω7:
where d is ratio from (0, to balance the process score and overall score. The algorithm then back-propagates the score by updating the Q-values of all nodes along the trajec- tory, from the leaf back to the root:
{(bp) Fe, (e())EEDD.MMMTT (Q, ग pollicy Freward) ) @ED.
ELLO0h9 1-1+1
(17)
Q(h()))
max
(10)
Proposition 4.3. There exists a reward threshold y- < B
such that incremental fine-tuning data, under the effect of the KB, can improve model performance.
where the Q-values of parent nodes are updated to the max- imum average Q-value from all child nodes along the tra- jectory. Meanwhile, the visit count of each node along the trajectory N(h (x)) adds 1, and then the next rollout begins.
Proof. We provide quantitative experimental results in Sec- tion 5.5 and qualitative proofs in Appendix B.3.
LI
5

---

KBQA-o1: Agentic Knowledge Base Question Answering with Monte Carlo Tree Search
Table 40-shot results the local dev set of GrailQA. Bold numbers indicate the hest low-resource performance.
LLD
Compositional
Zero-shot
Overall
Method
LLM
EM
FI
EM
F1
EM
FI
EM
FI
Full Superisse KBQA Methods
RuG-KBQA (Ye 2022)
86.7
89.0
61.7
68.9
68.8
74.7
69.5
76.9
DecAF (Yu et al., 2023)
88.7
92.4
71.5
79.8
65.9
77.3
72.5
81.4
TIARA (Shu al., 2022)
88.4
91.2
66.4
74.8
73.3
80.7
75.3
81.9
Low-resouree KBQA Methods
KB-BINDER (Li et al., 2023)
GPT-b,5-turbo
40.0
43,3
33,9
36.6
40.1
44.0
38.7
42.2
KB-Coder (Nic 2024)
G-r--35-ttrbo
40.6
45.5
34.5
38.6
42.2
47.3
40.1
44.9
ARG-KBQA (Tian et al., 2024)
GPT-3.5-turb
46.6
51.5
36.4
41.8
46.6
52.1
43.8
48.5
KBQA-ol (Llama-3)
Llama-3. 1--aa-3.1-BB
77.8 ans
85.5 an4 88.2 ans
76.3
77.6 ans
68.1 ans
76.1
71.9
78.5 a1d
Llama-3.3-70B
79.2. .n.?
80.8 ans
82.3 una
71.8 11.0
80.3 a..
75.2 100
81.6 10.5
Qwen2.5-7B
76.1 an.
84.4 ans
75.7 an.7
77.0 an.
67.3 an.
75.7 an2
70.8 20.5
77.9 203
Owen2.5 5.14B
78.0 =044
85.9 sne
77.4
78.4 sns
68.6 =t.1
79.0
72.5 e/6
79.2 =/.
KBQA-ol (Qwen..5)
Qwen2.5-322 5-32B
78.9 205
86.2 a0.7
79.3
80.4 ans
69.6 2n.
79.7
73.3
80.3
Qwen2.5-722
79.1 an4
87.4 ans
81.5 st.
83.0 ans
72.1 2044
81.9 as.s
75.8 20u4
82.1 al2
Gemma-2-9B
77.1 an.
82.3 ans
75.6 ans
76.7 2n4
66.3 an2
76.4 =ns
70.6 =00
77.8 20.5
KBQA-o1 (Gemma-2)
Gemma-2-27B
78.3
82.6
76.0
77.3 ans
69.5 a1.1
79.6
72.8
79.7
Table 100-shot results on the test set of WebQSP. Bold numbers indicate the best low-resource performance.
Table 4.
100-shot results on the test set of GraphQ. Bold numbers indicate the best low-resource performance.
Method
LLM
F1
Method
LLM
F1
Full- hall-Suereiiee KBQA Methods
Full Full- Supervise KBQA Methods
RuG-KBQA (Ye el al., 2022)
75.6
SPARQA (Sun al., 2020)
21.5
DecAF (Yu al., 2023)
76.7
BERT Ranking (Gu al., 2021)
25.0
TIARA (Shu et al., 2022)
78.7
ArcaneQA (Gu & Su, 2022)
31.8
Low-resowrce KBQA Methods
Low-resource KBQA Methods
KB-BINDER (Li al., 2023)
GPT-3.5-turbo
52.6
KB-BINDER (Li et al., 2023)
GPT-3.5-tubo GPT-3.5-tubo
27.1
KB-Coder (Nic al., 2024)
GPT-3.5-turbo
55.7
KB-Coder (Nic et al., 2024) ARG-KBQA (Tian et al., 2024)
31.1
ARG-KBQA (Tian el al., 2024)
GPT-3.5-turbo
58.8
GPT-3.5-turbo
KBQA-ol (Ilama-3)
Llama-3.1-8B
59.8 1122
KBQA-o1 (Llama-3)
Llama-3.1
48.7 us
1lama-3.3-708
67.0
Ilama-3.3
50.5
Qwen2.5-7B
57.8 100
Qwen2.544 5-BB
49.2 ma
KBQA-ol (Qwen2.5)
Qwen2.5-
60.1
KBQA-o1 (Qwen2.5)
Qwen2.5 10nn2.5--40 5-14B
50.0
Qwen2.5-32D 5-32B
63.7 40d
Qwen2. 20222.5.300 5-32B
50.9 s0
Qwen2.5-72B
66.5
Qwen2.5-782
51.2
Gemma- 2-9B
58.9 406
Gemma-
49.8 a07
KBQA-ol (Gemma-2)
KBQA-ol (Gemma-2)
Gemma-2-27B
61.0
Gemma-2-277
50.3
5. Experiments
GraphQ (Su et al., 2016). All datasets are based on Free- base (Bollacker et al., 2008) KB.
This section presents the experimental setup, results, and analysis. We answer the following research questions (RQs):
Baselines. We mainly compare our method with KB- BINDER (Li et al., 2023), KB-Coder (Nie et al., 2024), and ARG-KBQA (Tian et al., 2024) with the same L.M of gpt- 3.5-turbo-Ode -013 from OpenAl in low-resource setting. Some results obtained by full-supervised training on the whole training dataset (Ye et al., 2022; Yu et al., 2023; Shu et al., 2022; Sun et al., 2020; Gu al., 2021: Gu & Su, 2022) also reported for reference.
RQ1: Does KBQA-ol outperform other KBQA methods? RQ2: Does the main component of KBQA-o1 work? RQ3:
Does KBQA-o1 address the corresponding challenges com- pared to end-to-end and step-by-step KBQA methods? RQ4:
How does incremental fine-tuning gradually improve low- resource KBQA performance?
5.1. Experimental Setup
Evaluation Metrics. In line with prior studies (Li et al., 2023; Nie et al., 2024; Tian et al., 2024), we use Fl score and Exact Match (EM) as the evaluation metric for GrailQA, while F1 score are reported for WebQSP and GraphQ.
Datasets. All experiments are conducted on three standard KBQA datasets low-resource setting (Li et al., 2023): GrailQA (Gu al., 2021), WebQSP (Yih al., 2016), and
6

---

KBQA-o1: Agentic Knowledge Base Question Answering with Monte Carlo Tree Search
Table 5. Evaluation results of -llma-3.1-88--aaa.. KBQA-ol and its ablations. Bold numbers indicate the best performance.
L.I.
Compositional
Zero-shot
GrailQA
WebQSP
GraphQ
Method
EM
F1
EM
F1
EM
F1
EM
F1
F1
F1
KBQA-ol (Llama-3,1-8B)
77.8 sos
85.5 204
76.3 sas
77.6 sos
68.1 wa
76.1
71.9
78,5 am
59.8 a12
48.7 s0
w/o agent prompt
65.2
72.8
63.2 61.9
45.7
49.8
51.2
56,4
512
37.7 222
wio KB environment
43.5 214
51.3 aia
38.7 217
41.5 2ls
29.6
35.4 a16
34,9 a2n
43.0 aus
49.3 a07
25.1 214
w/o initial annotated sft
14.3 e39
17.4 a42
12.2 s47
14.5 s41
2.5
10.7 sA4
10.6
13.1 stD
17.2 229
9.5 e30
w/o MCTS
47.9 21.6
54.2 21.5
42.6 21.1
45.8 219
40.3 ala
44.2 22n
43,8 228
48.5 2377
44.0 =2.1
20.8 226
wlo incremental fine-tuning
60.7 sie
68.3 el2
56.2
58.9 214
53.8 si7
56.7 e/5
57.1 alo
63.9 a/o
55.4 =24
43,9 at.7
F1 Scores (Llama-3.1-88)
L.I.
Fi Scores (I.lmma-.118BB)
KRRAA-0
START
GraphQ
Camp.
STOP
JOIN
F1 Score
70
.MCTS
RC-Eaf
GR-Hall
RG-Fal
60
COUNT
AND
RBQA-a1
MCTS
TWT-916
MCI
50
ToT-Sbb
WehQSP
ZeroS.
KBQA
SoT
GR-FaFR RG-Eaa
TC
ARG
10
16
GrailQ
Query per Minute
(a)
(b)
(c)
Figure 4. Performance and efficiency comparison of Llama-3, 3.1--B---------. KBQA-ol with compared methods. (a) Fl scores comparison across datasets. (b) Fl scores across logical operators GrailQA. (e) Trade-off between FI scores and queries per minute GrailQA.
Implementation Details. Following KB- BINDER (Li al., 2023), we conduct 40-shot experiments for GrailQA, and 100-shot for WebQSP and GraphQ. During the MCTS exploration phase, we set 6exp with w = 50, while in the prediction phase, we set fen with w = 10. We select multi- ple open-source 7B-72B L.Mss, including Ilama-3 (Dubey et al., 2024), Qwen2.5 (Yang et al., 2025), and Gemma- (Team et al., 2024), to construct KBQA-o1, All exper- iments are done on 8 NVIDIA A40 GPUs (48GB), with results averaged from three randomly seeded experiments. Appendix G shows the optimal hyperparameter settings.
5.3. Ablation Study (RQ2)
As shown in Table 5, we conduct an ablation study on the 3lama-3.1-8B--all KBQA-ol methods. Five ablation set- tings are tested: removing the ReAct-based agent prompt, removing environment feedback, excluding the initial su- pervised fine-tuning (SFT) with small amount of labeled data, removing MCTS optimization, and omitting the incre- mental fine-tuning stage, respectively. Comparisons of the evaluation results reveal that all modules contribute to over- all performance, underscoring the importance of designed agent initialization, heuristic environment exploration, and incremental fine-tuning as key components of KBQA-ol.
5.2. Main Result (RQ1)
As shown in Tables 3, and 4, KBQA-ol enables open- source LLM to outperform previous low-resource KBQA methods based on GPT-3.5-turbo, with limited labeled data. In more complex data sets such as GrailQA, KBQA-o1 improves the overall EM performance of the Llama-3.1- 8B model by 2 percentage points and boosts Fl scores by 30.0 percentage points over the previous best meth- ods. In compositional and zero-shot evaluations, KBQA-o1 even outperforms fully supervised KBQA methods, which demonstrates its strong capabilities for generalization. en- vironment exploration, and handling complex logical ques- tions. Moreover, KBQA-o1 is plug-and- playp allowing inte- gration with various open-source 7B-72B LLMs, expected to improve further with future open-source LLM updates.
5.4. Comparison Analysis (RQ3)
To explore how KBQA-ol addresses the challenges of end- to-end and step-by-step methods mentioned in Section 1, we construct six variants. We design two end-to-end variants: one is a retrieve-then-generaa method (RG-E2E) based on DECAF (Yu et al., 2023), and the other is a generate-then retrieve method (GR-E2E), based on ChatKBQA (Luo et al., 2024a). Furthermore, we design two step-by-step variants: one is based on CoT (CoT-SbS) as Query (Huang et al., 2024), and the other is based on ToT (ToT-SbS) as ToG (Sun et al., 2024). Finally, we implement an MCTS- optimized variant without incremental fine-tuning and the full KBQA-o1 method after incremental fine-tuning.
7

---

KBQA-o1: Agentic Knowledge Base Question Answering with Monte Carlo Tree Search
Ineremental tuning (Exploration Stage)
8o
Ralio Ft Score
Querry lein
Quaryini
Ratio of Chosen Date
0.0
E Soure
-55
0.0
20-
Afee Eneremeutel Fine tuning (Prodiittion Stage)
85-
Querylais
60
Zame-ga-70 F)
Querry
12m0-33-0000 IM
56
Exploration Samples (1)
0.0
-200
-100
Threshold
100
MCTS Esploration Weight
(a)
(c)
Figure 5. Impact incremental fine-tuning tested on GrailQA: (a) Effect of exploration samples on Fl and EM scores. (b) Relationship
between reward threshold, data ratio, and performance. (c) Influence of MCTS exploration weight on query efficiency and accuracy.
Comparison with End-to-end Methods. To investigate whether the agent process in KBQA-ol is more capable of perceiving the KB environment than end-to-end methods, we compare CoT-SbS with RG-E2E and GR-E2E. Under the same prompt, CoT-SbS is equivalent to the agent process in KBQA-o1 without expansion. As shown Figures 4(a) and 4(b), in the I.L.D and WebQSP evaluations with annota- tions in distribution, RG-E2E and GR-E2E perform better. However, in Compositional and Zero-shot evaluations, the agent process represented by CoT-SbS performs better. This is because, with preannotated logical forms, end-to-end gen- eration rigidly adheres to a fixed logical form structure. In contrast, the step-by-step agent approach allows stepwise adjustments by KB environment awareness, enabling it to handle more complex out-of-distribution questions.
newly explored and labeled samples contribute to automati- cally generating high-quality logical forms using both en- vironmental and reward-based filtering, allowing KBQA to improve with minimal human annotation, making it highly promising for transferability and real-world applications.
Impact of Reward Threshold 7². As shown in Fig-
ure 5(b), we conduct experiments with reward thresholds Y ranging from -200 to 100. As 7 increases, the propor- tion of post-labeled data decreases until no data are selected at the maximum threshold of 100. In GrailQA, setting y to - -00 retained most labeled samples while filtering out lower-quality ones, resulting in the highest Fl score. This indicates that selecting an appropriate 7 helps preserve newly labeled high-quality samples while discarding erro- neous samples, making incremental fine-tuning effective.
Comparison with Step-by-step Methods. To investi- gate whether the MCTS proposed in KBQA-o1 can further prevent the step-by-step agent process from getting stuck in local optima or dealing with a large search space, we compared MCTS with CoT-SbS and ToT-SbS. As shown in Figures 4(a) and 4(b), MCTS consistently outperform CoT-ShS and ToT-SbS in all evaluation tasks and logical operators. To analyze efficiency, Figure 4(c) shows that the efficiency of MCTS and KBQA-ol falls between CoT-SbS and ToT-SbS. When exploring unlabeled data, the MCTS prioritizes correctness, while the full KBQA-o1, after incre- mental fine-tuning, adopts more efficient settings to balance performance and search time.
Impact of Exploration Weight w. Figure 5(c) presents a study on the selection of the exploration weight w in MCTS before and after incremental fine-tuning. We test seven dif- ferent values between 10 and 70. The results show that higher w leads to slower generation, but improves accuracy. Based on this, we set w E 6exp at 50 before incremental fine- tuning ensure accuracy. After incremental fine-tuning, we reduce E Ocf to 10 to balance efficiency and effective- ness. Hence, we ensure that the MCTS with 6eep performs a slow and careful search during exploration, leading to high- quality data for incremental fine-tuning. After that, we can implement a more efficient MCTS with Our in applications, maintaining high performance while improving efficiency.
5.5. Analysis of Incremental Improvement (RQ4)
6. Conclusion
To explore the impact of incremental fine-tuning on improv- ing the performance of KBQA-o1 in low-resource KBQA scenarios, we examine three key factors: the impacts of the exploration samples, the reward threshold, and the explo- ration weights on performance and efficiency.
In this work, we propose KBQA-ol, an agentic KBQA method with Monte Carlo Tree Search (MCTS) for efficient exploration. By combining a ReAct-based agent process with incremental fine-tuning, it improves logical form gen- eration and reduces reliance on annotated data. Experiments three KBQA datasets show that KBQA-o1 outperforms previous low-resource methods and rivals fully supervised models, demonstrating its scalability and effectiveness.
Impact of Exploration Samples. As shown in Figure 5(a), we gradually increase the number of unlabeled exploration samples and observe a steady improvement in the Fl and EM scores after incremental fine-tuning. This suggests that
8

---

KBQA-o1: Agentic Knowledge Base Question Answering with Monte Carlo Tree Search
Acknowledgments
Gu, Y. and Su, Y. ArcaneQA:
Dynamic program induc- tion and contextualized encoding for knowledge base question answering. In Calzolari, N., Huang, C.-R., Kim. H., Pustejovsky, J., Wanner, L.,, Choi, K.-S., Ryu, P.M.., Chen, H.-H., Donatelli, I.,, Ji, H., Kurohashi, S., Paggio, P., Xue, N., Kim, S., Hahm, Y., Hc, Z., Lee, T. K., Santus, E., Bond, F,, and Na, S.-H. (eds.), Proceedings of the 29th International Conference on Computational Linguistics, pp. 1718-1731, Gyeongju, Republic of Korea, October 2022. International Com- mittee on Computational Linguistics. URL https: / //aclanthology 2ttg/2022.col/ 1eaug-1--0 1.148/.
This work is supported by the National Natural Science Foundation of China (Grant No. 62176026, Grant No. 62473271, and Grant No. 62406036). This work also sup- ported by the BUPT Excellent Ph.D. Students Foundation (No. CX20231332 and the Engineering Research Center of Information Networks, Ministry of Education, China.
Impact Statement
This work introduces KBQA-ol, a novel agentic approach to knowledge base question answering (KBQA) using Monte Carlo Tree Search (MCTS). While effective, it still faces limitations in fin-grainee policy design and scalability to larger domains. To address these challenges, we outline four future directions: (1) exploring reinforcement learning for continual learning, (2) enhancing logical reasoning capabili- ties, (3) adapting to specialized domains such as medicine and law, and (4) extending to multimodal, multilingual, and multi-agent settings, as detailed in Appendix K. This work poses ethical concerns, as it relies solely publicly available datasets and aims to advance KBQA technology with positive societal impacts.
Gu, Y., Kase, S., Vanni, M., Sadler, B., Liang, P., Yan, X., and Su, Y. Beyond ii..:: Three levels of general- ization for question answering on knowledge bases. In Proceedings of the Web Conference 2021, WWW '21, pp. 3477-3488, New York, NY, USA, 2021. Associa- tion for Computing Machinery. ISBN 9781450383127, doi: 10.1145/8442331134499999 URL https: /doi. org 0ttp:/...111/3441
3449992..
Gu, Y. Deng, X., and Su, Y. Don't generate, discrimi- nate: A proposal for grounding language models to real- world environments. In Rogers, A., Boyd-Graber, J., and Okazaki, N. (eds.), Proceedings of the 61st Annual Meet- ing of the Association for Computational Linguistics (Vol- une I: Long Papers), pp. 4928-4949, Toronto, Canada, July 2023. Association for Computational Linguistics. URL https:
References
Bollacker, K., Evans, C., Paritosh, P., Sturge, T., and Taylor, J. Freebase: a collaboratively created graph database for structuring human knowledge. In Pro- ceedings of the 2008 ACM SIGMOD International Con- ference on Management of Data, SIGMOD '08, pp- 1247-1250, New York, NY, USA, 2008. Association for Computing Machinery. ISBN 1011686058166 doi: 10. 1145/1376616.13777444 URL https: /ttp://oo...////// 13767746.
doi: 10. 10.18653/ // //allatthology.orrg////// wttp://r///22..11111.... acl 270..
Hao, S., Gu, Y., Ma, H., Hong. J., Wang, Z., Wang. D., and Hu. Z. Reasoning with language model is planning with world model. In Bouamor, H., Pino, J., and Bali, K. (eds.), Proceedings of the 2023 Conference on Empirical Meth- ods in Natural Language Processing, pp. 8154-8173, Singapore, December 2023. Association for Computa- tional Linguistics. doi: 10.18653/v1/20233emml main. 507. URL https: /tee://aclaatin ogy.ooy..ooooo......... org/ 2023. emnlp hamlp-main..r main. 507.
10.
Cui, J., Li, Z. Yan. Y., Chen, B., and Yuan, L. Chatlaw: Open-source legal large language model with integrated external knowledge bases. CoRR, abs/2306. 16092, 2023. URL https::/p//.. htte:://oo...///// 48550/arXiv 2306 16092.
Dubey, A., Jauhri, A., Pandey, A., Kadian, A., Al-Dahle, A., Letman, A., Mathur, A., Schelten, A., Yang, A., Fan, A., et al. The llam 3 herd of models, 2024. URL https: //arxivv org/ abs/ 220224007220 21783.
Huang, X., Cheng, S., Huang, S., Shen, J., Xu, Y., Zhang, C., and Qu, Y. QueryAgent: reliable and efficient reasoning framework with environmental feedback based self-correction. In Ku, L.-W., Martins, A., and Srikumar, V. (eds.), Proceedings of the 62nd Annual Meeling of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 5014-5035, Bangkok, Thailand, August 2024. Association for Computational Linguistics. doi: 10. 1 274. URL https: aclanthology hwtph//ollloyo.oooooo///// acl 1aal--oog..... 274.
Gao, T. Yao, X., and Chen, D. SimCSE: Simple con- trastive learning of sentence embeddings. In Proceed- ings of the 2021 Conference on Empirical Methods in Natural Language Processing, pp. 6894-6910, On- line and Punta Cana, Dominican Republic, November 2021. Association for Computational Linguistics. doi: 10. 10.18653/v1/2211 wet.lleemlllmmai 552n. URL https:// aclantton antho 1 www.//rg//00 2221. emm mmnlp-mall i n. 552.
Jang, H., Oh, Y., Jin, S., Jung, H., Kong, H., Lee, D., Jeon, D., and Kim, W. Kbqa: constructing structured query
9

---

KBQA-o1: Agentic Knowledge Base Question Answering with Monte Carlo Tree Search
graph from keyword query for semantic search. In Pro- ceedings of the International Conference on Electronic Commerce, ICEC 17, New York, NY, USA, 2017. Asso- ciation for Computing Machinery. ISBN 9781450353120. doi: 10. I 14/1114444444333333555 org / 10. 111111155400 1tt.11115/3149999 911114949933.9999993 3154955.
Pérez, J., Arenas, M., and Gutierrez, C. Semanties and complexity of sparqi. ACM Trans. Database Syst., 34(3), September 2009, ISSN 0362-5915. doi: 10. 1145/156727411567778, URL
URL htt.tstttt//..t....
1567278.
Sastry, S. and Sastry, S. Lyapunov stability theory. Nonlin- ear systems: analysis, stability, and control, pp. 182-234, 1999.
Li, T., Ma, x., Zhuang, A., Gu, Y., Su, Y., and Chen, W. Few-shot in-context learning on knowledge base ques- tion answering. In Rogers, A., Boyd-Graber, J., and Okazaki, N. (eds.), Proceedings of the 61st Annual Meet- ing of the Association for Computational Linguistics (Vol- Toronto, Canada, July 2023. Association for Computational Linguisties. URL https: //aclanthooooooo wwwpa//hwwooooooo./2233e33 acl- long. 385.
Shu, Y., Yu, Z., Li, Y., Karlsson, B., Ma. T., Qu, Y., and Lin, C.-Y. TIARA: Multi-graines retrieval for robust question answering over large knowledge base. Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pp- 8108- 8121, Abu Dhabi, United Arab Emirates, December 2022. Association for Computational Linguistics. doi: 10. 10.16553w120002..mmmmmmmi.. ac wcl.anhhloo...org//20 wttp://///........mm.a....a.aaaa emn.p-main.p.mmmmm 555.
ume I: Long Papers), pp.
doi: 10.18633/ww/20233.c--oon....
Li, Z., Liu, H., Zhou, D., and Ma, T. Chain of thought em- powers transformers to solve inherently serial problems. In The Twelfth International Conference on Learning Representations, 2024. URL ht.ts:::::///// / http///eeeee.e....eoeee n forumoorroooo weerriddddwwyyyyym
URL https://
Su, Y., Sun, H., Sadler, B., Srivatsa, M., Gür, I., Yan, Z.,, and Yan, X. On generating characteristic-rich question sets for QA evaluation. In Su, J., Duh, K., and Carreras, X. (eds.), Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, pp. Pp.562-57 562-572, Austin, Texas, November 2016. Association for Compu- tational Linguistics. doi: 10.18653/v URL petpss///acaarrthol..g.. . wrg/D16-10//
Lightman, H., Kosaraju, V., Burda, Y., Edwards, H., Baker, B., Lee, T., Leike, J., Schulman, J., Sutskever, I., and Cobbe, K. Let's verify step by step. In The Twelfth International Conference on Learning Representations, 2024. URL https: http:///pppeeeieeeeee net/ forum? id=v8LOpN6E0i.
Sun, H., Dhingra, B., Zaheer, M., Mazaitis, K., Salakhutdi- nov, R., and Cohen, W. Open domain question answering using early fusion of knowledge bases and text. In Pro- ceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pp. 4231-4242, Brus- sels, Belgium, October-November 2018. Association for Computational Linguistics. doi: 10. 10.18655//1/DD18-4555 URL https: https///aaaaaathooooooeoo org/ 1455.
Luo, H., E, H., Tang, Z., Peng, S., Guo, Y., Zhang, W., Ma, C., Dong, G., Song, M., Lin, W., Zhu, Y., and Luu, A. T. T.ChhaaBQA: A seheraae-then-retriee framework for knowledge base question answering with fine-tuned large language models. In Ku, L.-W., Martins, A., and Sriku- mar, V. (eds)), Findings of the Association for Computa- tional Linguistics ACL 2024, pp. 2039-2056, Bangkok, Thailand and virtual meeting, August 2024a. Association for Computational Linguistics. doi: 10. 1/253/ 122. URL https:/ / /awlantoaaanooooo.. org/ 2024..22..42 findings-acl.112 122.
Sun, H., Bedrax- T., and Cohen, W. PullNet: Open do- main question answering with iterative retrieval on knowl- edge bases and text. In Proceedings of the 2019 Confer- ence on Empirical Methods Natural Language Process- ing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pp. Hong Kong, China, November 2019. Association for Computational Linguistics. doi: 10.18653/.1/119-12244 wttp/ooggg//// URL wwt.thtss//ccaaaatttt wttphh/owooooooooooo//oo11-0
Luo, L., Li, Y.-F., Haf, R., and Pan, S. Reasoning on graphs: Faithful and interpretable large language model reasoning. In The Twelfth International Conference on Learning Representations, 2024b. URL https: / //openreview....mmmmeee.oooooeee wwt.iiiwweeeeeeeem.mm forum? iidddddiiin d=222==7x22220
Nie, Z., Zhang, R., Wang, Z., and Liu, X. Code-style in- context learning for knowledge-bent based question answering. Proceedings of the AAAI Conference on Artificial Intel- ligence, 38(17): (11117):1833-18884 8833-18841, Mar. 2024. doi: 10.1609) vaai.v38i17.29845 URL htttt://///ooo wawp:::////o.aao...aoaaaaaaaaaaa org/ indes..bhh/A2AA//rriiille/tte
Sun, J.. Xu, C., Tang, L., Wang, S., Lin, C., Gong, Y., Ni, L., Shum, H.-Y., and Guo, J. Think-on on-graph: Deep and responsible reasoning of large language model on knowledge graph. In The Twelfth International Confer- ence on Learning Representations, 2024. URL https: / /oopnneevew..com weweet//orummiidnnooiee..
OpenAI. Gpt-4 technical report, 2024. URL https://
Sun, Y., Zhang, L., Cheng, G., and Qu, Y. Sparqa: Skeleton- based semantic parsing for complex questions over knowl-
wrxxiv.orr//bss/23330oo
10

---

KBQA-01: Agentic Knowledge Base Question Answering with Monte Carlo Tree Search
edge bases. Proceedings of the AAAI Conference on Arti- ficial Intelligence, (4(05))8952-89955) Apr. 2020. doi: 10. v34i0...ii..00006...4444 URL org/index, php httpp///..a/aaaiilee/eeee///////
Yang, A., Yang. B., Zhang, B., Hui, B., Zheng, B., Yu, B., Li, C.,, Liu, D., Huang, F., Wei, H., et al. Qwen2.5 technical report, 2025, URL htRLstss///axiv /ttp://aaxvvvooo.eeoo abs/24 15115.
Swiechowski, M., Godlewski, K., Sawicki, B., and Mandziuk. J. Monte carlo tree search: a review of re- cent modifications and applications. Artif. Intell. Rev. 56(3):2497-2562, July 2022. ISSN 0269-2821. doi: 10. 10.10077611442--22--10222 0tg/100.007/s10000 022-262222222222222222222 10228-y.
Yao, S., Yu, D., Zhao, J., Shafran, I., Griffiths, T., Cao, Y., and Narasimhan, K. Tree of thoughts: Deliberate problem solving with large language models. In Oh, A., Naumann, T., Globerson, A., Saenko, K., Hardt, M., and Levine, S. (eds.), Advances in Neural Information Processing Sys- tems, volume 36, pp. 11809-11822. Curran Associates, Inc., 2023a.
URL https: //ooi.
Team, G., Riviere, M., Pathak, S., Sessa, P. G., Hardin, C., C.upatriraj S., Hussenot, L.., Mesnard, T., Shahriari, B., Ramé, A., et al. Gemma 2: Improving open lan- guage models at a practical size, 2024. URL https: //arxiv. orgg abs 2/bs22400 22////40..000 00118.
Yao, S., Zhao, J., Yu, D., Du, N., Shafran, I., Narasimhan, K. R., and Cao, Y. React: Synergizing reasoning and acting in language models. In The Eleventh In- ternational Conference on Learning Representations, 2023b. URL httpst/:: /ttp:r/i////peevieee formm?? i id=WE_vluYun
Tian, Y., Song. D., Wu, Z., Zhou, C., Wang, H., Yang, J., Xu, J., Cao, R., and Wang, H. Augment- ing reasoning capabilities of LLMs with graph struc- tures in knowledge base question answering. In Al- Onaizan, Y., Bansal, M., and Chen, Y.-N. (eds.), Find- ings of the Association for Computational Linguis- tics: EMNLP 2024, pp. 11967-11977, Miami, Florida, USA, November 2024. Association for Computational Linguistics. doi: 10. 699. URL httph:tp/////...mm http::t/cclatttto//t/t//// hatp://aaaaaaaaaoo...o... org/2024. findings-emnn 1atmmmpp.9999 699/.
Ye, X., Yavuz, S., Hashimoto, K., Zhou, Y., and Xiong, C. RNG-KBQA: Generation augmented iterative ranking for knowledge base question answering. In Proceedings of the 60th Annual Meeting of the Association for Compu- tational Linguistics (Volume I: Long Papers), pp. 6032- 6043, Dublin, Ireland, May 2022. Association for Com- putational Linguistics. doi: 10.18653//1/20222.adl
417. URL https: http:/allaatttt wwwp:lllyoyyo..g....// acl- long. 447.
Yih, W.-t., Richardson, M., Meek, C., Chang, M.-W., and Sub, J. The value of semantic parse labeling for knowl- edge base question answering. In Proceedings of the 54th Anmual Meeting of the Association for Computa- tional Linguistics (Volume 2: Short Papers), pp. 201-206, Berlin, Germany, August 2016. Association for Compu- tational Linguistics. doi: 10. 10.18853/v1/P16-200 https: / /tt//aaaaaatttoooa
Vrandečić, D. and Krötzsch, M. Wikidata: A free collab- orative knowledgebase. Commun. ACM, 57(10):78-88 85, sep 2014. ISSN 0001-0782. doi: 10. 10.1149926 URL https: / doii org/ 10 114.1/222129999
Wang, J., Sun, K., Luo, I.., Wei, W., Hu, Y., Liew, A. W.- C., Pan, S., and Yin, B. Large language models-guided dynamic adaptation for temporal knowledge graph reason- ing. In Globerson, A., Mackey, L., Belgrave, D., Fan, A., Paquet, U., Tomezak, J., and Zhang, C. (eds.), Advances in Neural Information Processing Systems, volume 37, pp.
URL
/tgg P10PP0660000000 20033.
Yu, D., Zhang, S., Ng, P., Zhu, H., Li, A. H., Wang, J., Hu, Y., Wang, W. Y., Wang. Z., and Xiang, B. DecAF: Joint decoding of answers and logical forms for ques- tion answering over knowledge bases. In The Eleventh International Conference on Learning Representations, 2023. URL https: / /ttp///pnneeeennneeeee net forum? id=XHc52RPxQV3
Curran Associates, Inc., 2024.
Wei, J. Wang, X., Schuurmans, D., Bosma, M., ichter, b., Xia, F., Chi, E., Le, Q. V., and Zhou, D. Chain-of -hain-of-thought prompting elicits reasoning in large language models. In Koyejo, S., Mohamed, S., Agarwal, A., Belgrave, D., Cho, K., and Oh, A. (eds.), Advances Neural Informa- tion Processing Systems, volume 35, pp. 24824-24837. Curran Associates, Inc., 2022.
Zhang, J., Zhang, X., Yu, J.. Tang, J., Tang, J., Li, C., and Chen, H. Subgraph retrieval enhanced model for multi-hop knowledge base question answering. In Pro- ceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume I: Long Papers), pp. 5773-5784, Dublin, Ireland, May 2022. Association for Computational Linguistics. doi: 10. 10.18633/1/2022. acl-long.396 httpst::: wttpt:tttt/ttaante/et/tte http://aaaathoooy.orrrrr 2022 acl long. 396.
WU, J., Zhu, J.. Qi, Y., Chen, J., Xu, M., Menolascina, F., and Grau, V. Medical graph rag: Towards safe medi- cal large language model via graph augmenel-augmeeneed generation, 2024. URL https: // /arxiv.vvvv org/ abs/ 2408. 04187.

---

KBQA-o1: Agentic Knowledge Base Question Answering with Monte Carlo Tree Search
Appendix
A. Prompts Used in KBQA-o1
A.I. Initial Prompt
Figure 6 illustrates the initial prompt used the KBQA-o1 agent process. This prompt defines the structure and steps for solving KBQA tasks through interleaving Thought, Action, and Observation stages. The prompt guides the agent to perform specific actions, such as entity extraction, relation finding, expression merging, ordering, numerical comparisons, and adding time constraints. These predefined actions are essential for generating logical forms step by step from natural language questions. The diagram highlights the structured input format (<input>> for the question and <ootpput>> for logical expressions) and the scratchpad used for intermediate reasoning steps during the task.
question answering with Interieaving Thought, Action, Observation steps. Thought can reason about the current situation, and Action can be eight types:
want you good knowledge graph query generator, solving knowledge
(1) Extract entiyy| entity name where identify topic entity from question to
expression.
(2) Find_ relation [ relation name J. where we find the one-hop relation that is connected to the current expression.
(3) Merge [ expression1 expression2 where we merge
expressions.
(4) Order [ mode relation]. J. where we perform sorting operation and impose a constraint to output either the maximum or minimum value.
(5) Compare mode relation], where we perform numerical comparison to determine the range.
(6) constraiit [ [relation time where we add a time constraint.
(7) Count expression J. where we perform a counting operation to determine the number answers.
(8) Finish expression where conclude that it is appropriate end and output the expression.
<Input>
Question: (question)
coutput>>
(scratchpad)
Figure 6. Initial prompt of agent process.
A.2. Example Agent Process
Figure 7 provides example of the complete agent process in KBQA-ol for the query. The figure demonstrates how the agent iteratively constructs the logical form using the Thought-Action cottion-Observation prompt. Each step involves reasoning about the current context (Thought), performing a specific operation (Action), and observing the resulting logical expression (Observation). The process begins with extracting the topic entity followed by finding relevant relations and applying numerical and time constraints. The agent merges expressions to form a complete logical form, which then executed to retrieve the answer from the knowledge base. The final logical output form shown the bottom, showcasing the agent's ability to generate structured and executable queries systematically.
Input Question: What movie with television running time of less than minutes features Taylor Lautner?
Thought1: At this
should identily topic enlity from the question to start expression.
Action1: Extract entity| Taylor Lautner] ]
Observationt: expression
(T.RR(().07ddhs)
Thought2: At this step, we should find the one-hop relation that is connected to the current expression.
Action2: Find_ relation (film.actor. aitor.tiim
Observation2: expression = (FR film.actor. fimm expression)
Thought3: this step, should find the one-hop relation that connected the expression.
Actions: Find_reeatee relation [
ObservationS: expression JOIN((R performance. film)', expression)
Thought4: At this step. we should identity topic entity from the question to start new expression.
Action4: Extract_ entity| 60
Observation4: expression1 -TTART(60))
ThoughtS: At this step, we should perform a numerical comparison to datermine the range.
Actions: Compare LESS THAN tv.tv. progrro..mm.... episode running time ]
ObservationS: expression1 = CMP(tt', "t.tv_ program.episode poolsode__unnnnn_.o.em runninggttimt himel expression
Thoughts: At this step. we should merge these expressions.
Action6: Marge expressiont expression
Observation6: expression AND/expression., expression)
Thought7: At this step, we conclude that is appropriate to end and output the expression.
Action7: Finish expression
Observation7: expression (Txp(exprsssion)
Equivalent Logical Form: (AND (it tv.bv wwwppprrrrmppsoooe/ running. time 60) (JOIN (R film, pwwformance.....mmm film) (JOIN (R fimm. Taylor Lautner)))
Figure An example a complete agent process.
12

---

KBQA-o1: Agentic Knowledge Base Question Answering with Monte Carlo Tree Search
B. Proof
B.1. Proof Proposition 4.1
Proposition 4.1. The agent's ss awareness of the environment makes it more effective in generating optimal logical forms compared to end-to-enu methods.
Proof. According to the Lyapunov Stability Second Theorem (Sastry & Sastry, 1999):
For dynamic system f()) where is the state and f() is the nonlinear function describing state evolution. Define non-negative scalar function V(x) such that: V(x) 0 for all * and V(0) 0 (positive definiteness). Its time derivative along the system trajectory satisfies (ax) < and is bounded (negative definiteness). Then V(x) is called Lyapunov function candidate, and the system (from Lyapunov's perspective) is asymptotically stable.
For a discrete dynamic system F++1 = f(x), a Lyapunov function V(x) can be define, and the Lyapunov increment (x,) = V (x(41) (x)), then V (xx,) > and A AV(x)) < with bounded implies asymptotic stability.
Our KBQA-ol system is modeled discrete dynamic system:
h+41 = 9),,,9),
(18)
where h4 E H is the system state at step t; 9 is environment feedback. The state transition probability is defined as: P(he+1 he, 9), which represents the probability transitioning to the next state 1,+1, given the current state he and the environment feedback G. The goal is for the system state h2 to converge asymptotically the target state ht,,, to satisfy P(h") h4s 9) = 1.
We define positive definite Lyapunov function Vhha) as:
(ha) log P(h h),
(19)
where P(h, h" 9) is the posterior probability of state h, relative to the target state h"; V(h.) quantifies the deviation of the current state h, from the target state lt".
The posterior probability satisfies 0 < P(h h(, < 1. Thus, (hh) = - log P(h, 1 (h, 2 0. When he = h² P(h, 1h, 9)
V(h+) = 0. Thus, V(h+) is positive definite.
The change in the Lyapunov function between steps is defined as:
(V = (hh+1)) (he).
(20)
Using the definition of Vhe), we get (hh+11::
V(h++1) = - log P(1z+1 | (",9),
(21)
and the posterior probability recursion:
P(N+t (h19)= = P(he (h, P(h+41 hee 9),
(22)
we have:
V(h+1) = - log P(he (h,9) log P(he+i her G)-
(23)
Thus:
(V = V(h++1) V(h = - logg P(h+t1 he, 9).
(24)
The probability P(her1 h,, 9) can be expressed as:
P(h+4 h),9) = P(Exp(h,, 9) hr, 9) P(he41 he: Exp(hs, 9)),
(25)
where P(Exp(h,,9) 9) 9) is the probability that the environment generates an exploration space Exp(h,,9) 9), containing valid actions for transitioning to h441. And P(h-11 he, Exp(hi, G)) is the probability that the system transitions from h, het1, given the exploration space.
13

---

KBQA-o1: Agentic Knowledge Base Question Answering with Monte Carlo Tree Search
In KBQA-ol, our environment can provide all possible explorations under the prior state, and the correct exploration step guaranteed to be included. Thus, PhExp(he; 9) h, 9) 1. Therefore, P(h++1 h4, 9) P(h++1 he, Exp(h4, 9)), and given set of explorations that contains the correct one, the probability of selecting the correct exploration satisfies 0 < P(1 h,, Exp(he, 9)) < 1. Consequently, 0 < P(h++ g) < 1.
Since O < P(h h4, 9) < 1, we conclude (h+) < 0 and is bounded. Thus, the Lyapunov function change is strictly
negative definite.
Based on the Lyapunov Stability Second Theorem, V(h+) log P(h hh.9) 9) satisfies positive definiteness: V(he) 2 and (hh,) 0 only when hr h", and negative definiteness: AV < 0, ensuring V (h₂) strictly decreases. Thus, the Agent system is asymptotically stable in the Lyapunov sense, and the state h, converges to h".
However, for end-to-end methods, although both pre-retrieval and post-retrieval approaches can incorporate environmental information, pre-retrieval may result in an exploration space that does not include the target exploration, leading to P(Exp(he, g) he, 9) = O. Post-retrieval, on the other hand, may generate a logical form framework that is incorrect, resulting P(h++1 | h4, Exp(hy: 9)) In such cases, this leads to P(h++1 h4, 9) = P(Exp(he,,)) 9) h4, 9) P(he- | hr, Exp(,,, 9)) 0, causing AV (hg) isn't bounded, leading to instability.
Therefore, conclude that the agent's awareness of the environment makes it more effective in generating optimal logical forms compared to end-to-end methods.
B.2. Proof of Proposition 4.2
Proposition 4.2. The MCTS- berS-based heuristic method balances the effectiveness and size of the search space better than CoT-based and ToT-based step-by-step methods.
Proof. Let F represent the search space of logical forms, with a size of [ k², where k is the number of choices per step, and L is the maximum search depth. Let Foptimul S F denote the set of high-quality solutions whose scores exceed a threshold r. For any search method X, its generated candidate set is Fx C F, the coverage rate is defined as:
Fx n T Fopuinal
Cx
(26)
[Foptimat
We first compare CoT Chain-offThhouhhy and our proposed MCTS- method. CoT follows a single path h, producing a single candidate Foors with its candidate set given by Feor = {Fcor). If Feor E Fopumall the coverage rate is
Ccor
(27)
Foptimal
otherwise, CcoT = O. MCTS, on the other hand, expands multiple different paths during multiple rollouts. If N rollouts are performed in total, the resulting candidate set is
FMCTS (l))) ".
(28)
n=1
where b,("), is the n-th path generated. Under effective strategy and reward guidance, most paths will fall into F Foptimal, and thus
FMCTS n F Foptimal
CMCTS
Ccor-
(29)
[Foptimal
This demonstrates that MCTS significantly outperforms CoT in terms of coverage of high-quality solutions.
Next, we compare MCTS and ToT (Tree of Thought) based on BFS/DFS. ToT explores all possible paths in F, so its max candidate set is F F. The coverage rate for ToT is
F Foptimal
CTo
= 1,
(30)
[ Foptial
14

---

KBQA-o1: Agentic Knowledge Base Question Answering with Monte Carlo Tree Search
but this requires time complexity of
Tor = Okk))
(31)
MCTS, however, only explores part of the tree. Assuming each rollout expands wk candidates (w E (0, 1)), and N rollouts are performed, the total search size is N wk L, with a time complexity of
TMeTs O(N wk L).
(32)
As long as N wk L < k4, we have
TMCTS & Two--
(33)
Moreover, the strategy and reward models effectively focus the search on high-potential nodes,
|MCTS O F opiinal ~
Foptimal:
(34)
leading to
CMCTS & Clur
1.
(35)
Combining these results, we see that compared to CoT, MCTS significantly improves the coverage rate by expanding multiple paths. Compared to ToT, MCTS achieves a near-equal coverage rate with substantially lower time complexity, Thus, MCTS balances effectiveness (coverage rate) and efficiency (search space size) better than both CoT and ToT.
B.3. Proof of Proposition 4.3
Proposition 4.3. There exists a reward threshold 7- < 3 such that incremental fine-tuning data, under the joint effect of the KB and the reward model, can significantly improve model performance.
Proof. First, we define the performance improvement of incremental fine-tuning, AE(""). The model's initial performance on the annotated dataset D, is denoted as Evsse and its performance after incremental fine-tuning is Enew Ensse + "E(r").Here Ex(")) represents the performance gain contributed by incremental data, which depends on the quantity and quality of the incremental data.
The incremental data originates from the unannotated dataset Dn, where the logical forms fo and answers Á generated through filtering mechanism. The filtering criteria are as follows: 1) The reward score of the logical form Rx (F) 2) The answer is non-empty, A / 0.
The logical forms that satisfy the criteria form the incremental dataset D,(r*). The size and quality of the incremental data are both dependent on the reward threshold y". The performance improvement can be expressed as:
A X -Niigh((")) Qavg (Dvy())
(36)
where (""gh(>") is the quantity of incremental data; Qavg (P)(7*)) is the average quality of incremental data; À >>> 0 is scaling factor representing the contribution of data quality to the performance gain.
Next, we analyze the properties of (7") and (D, (r)))) )), and subsequently derive the behavior of AF(?").
The quantity of incremental data (7)g depends on the number of logical forms in the unannotated dataset that satisfy
R (F) > 7 Let N,, |Dn] be the size of the unannotated dataset, and let the reward scores of logical forms follow probability density function P(R). Then:
Wiight(" N2, Pmigu(("")
(37)
where (7igh(?")) represents the probability that the reward score exceeds y":
Fhigh (T*) L P(R) d..
(38)
Clearly, as n* increases, Nhigh (7") decreases. When 7" - -00 N1igh(?") - No; wheney" - B, Nnigh (x*)
15

---

KBQA-o1: Agentic Knowledge Base Question Answering with Monte Carlo Tree Search
The quality of the incremental data Qav is the average reward score of logical forms with Rewwaad (F) > 7", defined
Qwg(Di(?>)) = S2. R P(R) S. P(R) dR
(39)
The numerator I.. R P(R) dR is the total quality weighted by reward scores, while the denominator J P(R) (7g)((")) is the total probability. When 7" + -0, all logical forms are included the incremental data, and the average
quality is the expected reward score:
Qavg (D(("))))) R = R- P(R) dR.
(40)
When y" + ;3, only the logical forms with the highest reward scores are retained, and the average quality approaches 1. Now, we analyze the behavior of the performance improvement AE(("). Substituting Nnigh and Qavg (Di(+*) into
AE we obtain:
AE(+")= X Nn. N. (f
S.. R. P(R)dR
(41)
Sh. P(R) dR
Simplifying this, we get:
AE = = [-d R- P(R) dR.
(42)
To analyze the critical points, we take the derivative of AE(?") with respect to y*:
AΔE(T*)
- No 7 P(7*).
(43)
Oy
BAF('") > O, indicating that A (F((") increases with y"; when y" - 3, #AF(r") clear that when 7" - 000 Cr indicating that AE(r") decreases with 7", Thus, AE(r*) is a unimodal function, and there exists a critical point Yop E 3) at which A A)(")) achieves its maximum.
Bry
In conclusion, we have proven that: There exists a reward threshold > < 3 such that the trade-off between the quantity and quality of incremental data is optimized. At this threshold, the performance improvement AE(>") reaches its maximum. This establishes the existence of y and its role in optimizing the effect of incremental fine-tuning.
C. MCTS Algorithm Details
Figure and Algorithm illustrate the Monte Carlo Tree Search (MCTS) process in KBQA-o1. The figure highlights the four stages of MCTS: Selection, where nodes are chosen using the Upper Confidence Bound for Trees (UCT) balance exploration and exploitation; Expansion, where candidate actions generated by the policy model, filtered for relevance to the knowledge base, and added as child nodes; Simulation, where the most promising path is explored to produce complete logical form and compute rewards; and propaaarpa,,,ion, where rewards are propagated back to update Q-values and visit counts. The pseudocode formalizes this process, iteratively performing rollouts that follow the four stages. It ensures efficient exploration by selecting nodes with high potential, expanding with semantically relevant actions, simulating logical forms, and updating scores through back-propagatiinn This approach enables KBQA-o1 to navigate large search spaces effectively and generate high-quality logical forms.
Complexity Analysis. The time complexity of the MCTS process in KBQA-o1 can be analyzed based on its four stages: Selection, Expansion, Simulation, and Back-propagation. In the Selection stage, the algorithm traverses the search tree up to depth L, selecting the best node using the Upper Confidence Bound for Trees (UCT), leading to complexity of Okk L) per rollout, where k is the number of possible actions per step. The Expansion stage generates B beam candidates, which are filtered based on knowledge base similarity, adding (ww) complexity. The Simulation stage explores paths up to depth I., contributing Olk . L.). Finally, the Back- propaaaooon stage updates the rewards along the path, requiring (
16

---

KBQA-o1: Agentic Knowledge Base Question Answering with Monte Carlo Tree Search
Summing up these steps, the complexity for single rollout O(k L). and with N rollouts, the total complexity of MCTS O(N. k. L., which scales linearly with the number of rollouts and search depth.
Compared to exhaustive search methods like Tree-of- Thooughs (ToT), which have a complexity of O(k²)) MCTS is significantly more efficient. Instead of exploring all possible paths, MCTS selectively explores high-potential nodes based on the policy model and UCT, reducing redundant computations. This selective approach allows MCTS to scale effectively, making it suitable for large KBs. Additionally, MCTS dynamically balances exploration and exploitation, adapting its search strategy based on reward feedback. This adaptability, combined with its lower computational cost, enables MCTS generate high-quality logical forms while maintaining efficiency.
MCTS Inference AgentKBOA
Initial Prompt
Initial Prompt
Initial Prompt
Initial Prompt
Inpul Question
Input Question
Inpul Question
Inpul Question
Extract_entity
Extract_ontity
Extract ontlty Taylor Lautner
Extract_ontit
Taylor Lautner]
Tayfor Lautner
Taylor Lautner
Find, relation
Find relation
Find_rclation
Find relation
Fend_relation
Findd relation
Find_relation
Find, relation
Extract [
Find_relation Ris mesprforrunns.in
Extract_entity [60]
Find_relation finnsetsmarsccir
Extract_entty [60]
Find, relation Slie prn.pettmann....
Quvslue
[expression
Selection
Expansion
Simulation
Back-propagation
Figure 8. Four stages the MCTS process KBQA-o1.
Algorithm 1 MCTS in KBQA-ol
Require: Initial state ha, knowledge base policy model Policyy reward model Treward beam size B, number of top candidates d, depth limit L, number of rollouts N, exploration weight w.
1: for <- to N do
2:
t-0 0
3: while (h.) do
Select by UCT: e f- arg max )EF(N()) Q(h(11) +e) + u
b. Selection
N(h (m)
Update (x)
1 e
6:
f ++1+1
7:
end while
8:
while h, is not terminal state A L do
9:
Beam search by policy model: (e, (b) Jb=1 paiiyy ee hm(m))
Expansion
10:
Semantic selection from KB: {e, f + arg m
oc o) SimCSE (o
Policy model rerank: E(b(")) (el Jimi arg max Rmganes ((el (lel")t I br(h))
11:
Simulate along the best: e, <- arg max (ER()()) R Repnayy (e (())
12:
> Simulation
13:
Update h(a) h,2) e,
f + +
15:
end while
16:
I I+- t
Calculate reward: Q(h(")) + Hagan (oi (b(32) + (1 - 6) R Riward (Pagm) 10)
17:
18:
for l..., do
19:
Update Q(h(")) maxf=1
T-++1
Back-propagatton
20: Add visit count: N(h(")) N(h(")) +1
21:
end for
22:
end for
17

---

KBQA-o1: Agentic Knowledge Base Question Answering with Monte Carlo Tree Search
D. Dataset Details
Table provides an overview of the dataset statistics used in the KBQA-ol experiments across different settings: L.I (Independent and Identically Distributed), Compositional, Zero-shot, and three datasets (GrailQA, WebQSP, and GraphQ). The table includes the following rows: #Train is the number of training examples used for each dataset. #Exploration is the number of exploration queries generated during the heuristic exploration phase for each dataset. The numbers indicate the extensive exploration. #Test is the number of testing examples for evaluation in each setting.
Table 6. Dataset statisties of KBQA-ol.
LLD
Compositional
Zero-shot
GrailQA
WebQSP
GraphQ
#Train #Exploration
40
100
100
43851
2929
2332
#Test
1564
1487
3645
6696
1566
2319
GrailQA dataset (Gu et al., 2021) is a large-scale dataset specifically designed to evaluate KBQA models across three key generalization levels: i..dd,, compositional, and zero-shot. It contains 64,331 questions, of which 6,696 in the local dev set with three levels are used for testing in the KBQA-ol experiments. This dataset requires models to understand wide range of logical forms and multi-hop reasoning over knowledge bases. Its exploration phase involves a significant number of queries (43,8 (41, emphasizing the importance of comprehensive environment exploration. The dataset is particularly challenging in its compositional and zero-shot settings, where models need to handle unseen combinations of entities and relations, testing their ability to generalize beyond simple patterns.
WebQSP dataset (Yih et al., 2016) is an enriched version of the original WebQuestions dataset, providing semantic parses for each of its 4,737 questions. In KBQA-ol experiments, 1,566 questions are used for testing. and 2.929 queries are generated during the exploration phase. This dataset focuses on evaluating the semantic understanding of KBQA models, requiring them to map natural language questions precise logical forms. The inclusion of semantic parses enhances the dataset's 's utility for training and evaluating models, enabling fine-grained analysis of their ability to disambiguate and retrieve information from the knowledge base. The relatively smaller size of WebQSP compared to GrailQA makes it a valuable benchmark for assessing model efficiency in low-resource settings.
GraphQ dataset (Su et al., 2016) dataset aimed at testing KBQA models on complex reasoning tasks involving graph-structured data. It contains over 5,000 questions, with 2,319 used for testing in the KBQA-ol experiments. The exploration phase generates 2,332 queries, reflecting the intricate nature of reasoning required by the dataset. GraphQ challenges models to navigate multi-hop relationships and resolve complex dependencies between entities, pushing them to understand the underlying structure of the knowledge graph. Its focus on characteristic-rich queries ensures a thorough evaluation of a model's reasoning capabilities, making it an essential dataset for advancing KBQA methods.
E. Atomic Query Tool Details
As shown in Table 1, KBQA-o1 introduces eight atomic query tools designed to facilitate logical form generation for KBQA. These tools are tailored to systematically convert natural language queries into logical forms by leveraging the structural properties of KB. Each tool serves specific function, ensuring precise interactions with the KB to retrieve or manipulate information. Below is an explanation of each tool:
Extract entity is used to identify and extract a specific entity from the knowledge base. It takes an entity as an argument and initializes the logical form with this entity. The target function is represented as STARR(''nnitty) and the corresponding logical form is simply the entity itself. For instance, extracting "Taylor Lautner" initializes the logical form with the entity identifier for the actor.
Find_rehe relation identifies relation connected to the current logical form. It takes a relation as an argument and appends it to the existing logical form using the JOIN operation. The resulting logical form is (JOIN relation (expression)). For example, finding the wim.actor.filn relation connects an actor to their associated films.
Merge combines two logical expressions into a single conjunctive expression. It takes two arguments, expression I and expression, and returns AND(expressionl, expression) as the target function. The equivalent logical form is (AND
18

---

Time constraint imposes a time-based constraint on the logical form. It takes a relation and a time as arguments, applying KBQA-o1: Agentic Knowledge Base Question Answering with Monte Carlo Tree Search
(expressionl) (expression).. For example, merging two conditions like "actor is Taylor Lautner" and "runtime < 60 minutes" forms combined condition.
Order determines the extreme value of a property, such as the maximum or minimum. It takes mode (e.g., max or min) and a relation as arguments. The target function is ARG( 'oode,, expression, 'relation", ) and the logical form is (mode (expression) relation). For example, finding the longest film associated with an actor uses this tool.
Compare evaluates a property against specified value using a comparison operator (e.g., <, <,,-,,,>>> It takes a mode and a relation as arguments. The target function is CMP('mode 'relation', expression), and the corresponding logical form is (mode relation (expression)). For instance, checking if film's runtime is less than 60 minutes employs this tool.
a temporal filter to the expression. The target function is TC(expression, 'relation', 'time') ) and the logical form is (TC (expression) relation time). For example, filtering films released before a specific year uses this tool.
Count calculates the number of entities that satisfy a given condition. takes an expression as an argument, returning the target function COUNT(expression) and the logical form (COUNT (expression)). For instance, counting the number of films an actor has appeared in utilizes this tool.
Finish signals the termination of the logical form generation process. It takes expression as its argument and finalizes the logical form as STOP(expression) The corresponding logical form is simply (expression). This tool ensures the logical form is complete and ready for execution against the KB.
F. Baseline Details
The six full-resource baselines provide comprehensive evaluation framework for KBQA. These methods leverage fully annotated datasets and advanced reasoning mechanisms to achieve high performance on various KBQA tasks. Below is summary of each baseline:
RuG-KBQA (Ye et al., 2022) is a retrieve-and-general framework that first retrieves relevant knowledge from the knowledge base (KB) and then generates executable logical forms for answering questions. It focuses on leveraging retrieval to enhance logical form generation accuracy.
DecAF (Yu al., 2023) employs progressively refining retrieved knowledge, DecAF addresses the complexity of large-scale KBs and supports more accurate logical reasoning.
retrieval strategies ensure robust KBQA performance. By focusing on
TIARA (Shu et al., 2022) is a multi-stage retrieval method designed for large-scale KBs. It enhances robustness by retrieving candidate knowledge in multiple stages and integrating it into logical form generation, improving its ability to handle complex queries.
SPARQA (Sun al., 2020) uses a skeleton- based semantic parsing approach to generate logical forms for complex questions. It simplifies question processing by extracting structural skeleton, which is then converted into complete logical form.
Ranking (Gu et al., 2021) integrates BERT-based encoder with ranking mechanism to select the most relevant answers from candidate entities. It enhances the precision of entity linking and relation matching in complex KBQA scenarios.
ArcaneQA (Gu& & Su, 2022) combines dynamic program generation with contextualized encoding to address complex reasoning tasks. Its innovative design enables it to process multi-hop reasoning queries with high accuracy.
The three low-resource baselines designed to address the challenges of KBQA in scenarios. Unlike fully supervised methods, these approaches focus on GPT API for in-context-leamiing Below is a detailed summary of each method:
KB-BINDER (Li et al., 2023) leverages GPT-3.5- to perform KBQA with minimal supervision. It adopts a structured in-context learning approach, where logical form templates guide the generation process. This method effectively balances efficiency and accuracy in low-resource settings.
KB-Coder (Nie et al., 2024) employs code-style in-context learning to improve logical form generation. By treating logical form generation code-writing task, this method enhances reasoning consistency and adaptability, even with limited training data.
19

---

KBQA-o1: Agentic Knowledge Base Question Answering with Monte Carlo Tree Search
ARG-KBQA (Tian et al., 2024) enhances knowledge retrieval efficiency in low-resource KBQA. It optimizes argument selection for logical forms, ensuring that queries retrieve the most relevant knowledge while minimizing errors caused by insufficient training data.
The four baselines in Section 5.4 represent different approaches to KBQA, covering both end-to-end and step-by-step methods. These methods are designed to evaluate different strategies, including retrieval-based logical form generation, sequential reasoning, and tree-based expansion. The comparison with KBQA-ol highlights the strengths and limitations of each approach. providing insight into the effectiveness of heuristic exploration with MCTS, Below is summary of each baseline:
RG-E2E: Based on the DecAF (Yu et al., 2023), RG-E2E follows a retrieve-then--ennera paradigm, where relevant knowledge is first retrieved from the KB before generating the logical form. While effective in structured environments, this approach struggles with unseen entity-relation combinations due to its reliance on pre-retrieved data.
GR-E2E: Adapted from the ChatKBQA (Luo et al., 2024a), GR-E2E first generates a preliminary logical form and then refines it by retrieving supporting evidence from the KB. While more flexible than RG-E2F, it faces challenges in ensuring that the generated logical form aligns correctly with KB constraints.
CoT-SbS: Inspired by QueryAgent (Huang et al., 2024), CoT-SbS applies Ohain-of-Thoughh (CoT) reasoning to KBQA, where logical forms are constructed incrementally through multiple reasoning steps. Although it improves interpretability, it is prone to local optima and reasoning errors, especially in complex multi-hop queries.
ToT-SbS: Based on the Think-on- Oh-nn- (Sun et al., 2024), ToT-SbS extends step-by-step reasoning into a tree-like structure, expanding multiple reasoning paths simultaneously. While it mitigates local optima, it suffers from large search spaces, making it computationally expensive compared heuristic search methods.
G. Hyperparameter Settings
Table 7 presents the hyperparameter configurations for the KBQA-ol across three datasets: GrailQA, WebQSP, and GraphQ. These parameters are categorized into four stages: Initial Few-shot SFT, MCTS Exploration Stage, Incremental Fine-tuning, and MCTS Prediction Stage, each designed to optimize the KBQA framework's 's performance for different tasks.
In the Initial Few-shot SFT stage, the policy and reward models are fine-tuned using small labeled dataset initialize the framework. Both models adopt the DoRA architecture, optimized for reasoning tasks. The batch size is set to 4, ensuring stability in training with manageable memory usage. A fixed learning rate of 5e-5 controls weight updates, providing balance between convergence speed and training stability. The number of epochs varies by dataset, with 100 for the policy model in GrailQA and 50 for WebQSP and GraphQ. The reward model undergoes more training, with 300 epochs for GrailQA and 100 for WebQSP and GraphQ, to ensure the robustness of the reward function.
The MCTS Exploration Stage employs Monte Carlo Tree Search to explore logical forms by simulating reasoning paths within the KB. Each rollout performs 6 iterations of exploration. beam size of 2 limits the number of candidate paths considered. TopK and TopD parameters further refine candidate selection, with GrailQA and GraphQ using TopK=10, while WebQSP uses TopK=3. Similarly, GrailQA and WebQSP have TopD=3, whereas GraphQ sets TopD=5. An exploration weight of 50 balances exploration of new paths with exploitation of known high-quality paths. The reward ratio, fixed at 0.5, ensures equal contribution from the policy and reward models. Dataset-specific reward thresholds (-100 for GrailQA, 30 for WebQSP, and -50 for GraphQ) filter out low-quality paths, tailoring the exploration process to the characteristics of each dataset.
The Incremental Fine-tuning stage further refines the policy and reward models based on insights gained during the exploration stage. The models retain the DoRA architecture, with batch size of 4 and a learning rate of 5e-5. Both models are fine-tuned for 10 epochs across all datasets, ensuring improved generalization.
In the MCTS Prediction Stage, the refined models are used to generate final logical forms for KBQA tasks. 6 rollouts are performed, consistent with the exploration stage, but the beam size is reduced to to focus on the most promising candidate paths. TopK and TopD parameters mirror those in the exploration stage to maintain consistency in candidate selection. The exploration weight is reduced to 10, prioritizing exploitation of high-quality paths while allowing limited exploration during prediction. The reward ratio remains fixed at 0.5 across all datasets, maintaining a consistent balance between contributions from the policy and reward models.
20

---

KBQA-o1: Agentic Knowledge Base Question Answering with Monte Carlo Tree Search
Table 7. HyperParameter Settings for GrailQA, WebQSP, and GraphQ
Hyperparameter Name
GrailQA
WebQSP
GraphQ
Initial Few-shot SFT
SFTI
Type for Policy Model
DoRA
DoRA
DoRA
SFTI Batch Size for Policy Model
4
4
4
SFT1 Learning Rate for Policy Model
5c-5
5c-5
5c-5
SFTI Epoch for Policy Model
100
50
50
SFTI
Type for Reward Model
DoRA
DoRA
DoRA
SFTI
Batch Size for Reward Model
4
4
4
SFT1 Learning Rate for Reward Model
5e-5
5e-5
5e-5
SFT1 Epoch for Reward Model
300
100
100
MCTS Exploration Stage
MCTSI Rollout N
6
6
MCTSI Beam Size B
MCTS1 TopK k
10
MCTS1 TopD
MCTS1 Exploration Weight w
50
50
50
MCTSI Reward Ratio
0.5
0.5
0.5
MCTSI Reward Threshold
-100
30
-50
Incremental Fine-tuning
SFT2 Type for Policy Model
DoRA
DoRA
DoRA
SFT2 Batch Size for Policy Model
4
4
4
SFT2 Learning Rate for Policy Model
5e-5
5e-5
5e-5
SFT2 Epoch for Policy Model
10
SFT2 Type for Reward Model
DoRA
DoRA
DoRA
SFT2 Batch Size for Reward Model
4
4
4
SFT2 Learning Rate for Reward Model
5e-5
5e-5
5e-5
SFT2 Epoch for Reward Model
20
20
MCTS Prediction Stage
MCTS2 Rollout N
6
6
MCTS2 Beam Size
MCTS2 TopK
10
MCTS2 TopD d
3
MCTS2 Exploration Weight
10
10
10
MCTS2 Reward Ratio
0.5
0.5
0.5
H. Open-source LLMs used in KBQA-o1
The KBQA-ol framework designed with a plug-and- -laypay architecture, allowing seamless integration different open- source LLMs based on task requirements. This flexibility allows easy substitution or upgrading LLMs, ensuring that the system remains state-of-the-are
models become available.
Llama-3 (Dubey et al., 2024), developed by Meta AI, is an advanced large language model known for its strong reasoning abilities and generalization across diverse tasks. It excels in processing multi-hop reasoning and compositional queries, making it ideal for KBQA tasks that require logical inference over structured data, ensuring robustness in complex question-answering scenarios.
Qwen2.5 (Yang al., 2025), released by Alibaba, is particularly effective entity linking and relation extraction, two crucial components of KBQA. Trained on both structured and unstructured data, Qwen2.5 ensures high-precision entity disambiguation and improves the accuracy of knowledge retrieval. Its multilingual capabilities make it promising to further enhance KBQA-oI's adaptability across different datasets and domains.
Gemma-2 (Team et al., 2024), developed by Google, is optimized for retrieval- based reasoning and structured query generation. It specializes in efficiently retrieving relevant knowledge and generating accurate logical forms for complex queries. Its lightweight yet powerful design ensures high-speed inference, making it well-suited for low-later latency applications KBQA.
21

---

KBQA-o1: Agentic Knowledge Base Question Answering with Monte Carlo Tree Search
I. Case Study
End-lo-end KBQA Method:
Extract antity Taylor Lautter
Question
Pind reiation Simnactio film
What mose with ndedttoe. 60 miana fectures
Inttel Prompt
X
Inpur Question
Compare suese
Herga
step KBQA Method:
Question
What mone hefortsen
Extret (10)
X
less Tryler festures
(Tayker Lestner)
0.5.a 10.3 Sulract [48]
Compare
Lecgreedon]
Compar
Resah [ssprantoon
KBDA-01
[G]]
(Agentic MCTe-based Method)
jeblisn
Question
16TT m1
D11 1
What wavie with helvbiiee
Fissh [sgression]
Final Agent Prooess
minuna Fecnures
18 mm
Thoughts: the shoud bertly enty from qaettor
Time cunserant
Piesh [ssprestion
Aclienis butil onlyy: wit Ladea
Thoughe2: de the ess, ahaad tnd the one-ko in stte that connactd to the nieeet exprestion
Fy 1D
O S.
Time
oeservatin:: expaetiin 10h0 ran adturtin) expoeerion oot
Input Question
Intiia Pronpi
Extract antty
[esprestion
Obserattond: repastioo 1000 rin
Theught3: ai ln slss we culd ind
lin)
dbee that adud cumart cxprcaaon
flay) eucreddon)
the
[espresdon]
Actione: Estect unday 65]
Eetract werby
Thaughts or the des, shouk perfere sumeniol conpensonn to detemmiee the onge.
Conpare
progrom inda,
Q NGA
Compars
Obsanvatend: oprmasbe... -DPV
Thoughts: de the des, should merge thes roprem
expresdion)
D. 3671
Rind rebiionn
Fied, reietion
Observatind: canouse 200loourooo courcsse))
12.2
Actien?: Fir e expretton)
Observatinnh: ogpavsee (10Mf
Time
Figure 9. Case study of KBQA-ol's MCTS inference compared with end-to-end and step-by-step methods.
To visually illustrate the reasoning process of KBQA-o1, Figure compares the proposed MCTS-based method with end-to-end and step-by-step KBQA approaches. In this example, the question "What movie with a television running time of less than 60 minutes features Taylor Lautner?" is posed. The question is first processed in the initial prompt, forming the agent's s starting state. Through multiple rounds of MCTS exploration, the framework builds search tree, where the Q-value represents the score updated through backpropagation, and #V denotes the number of times each state has been visited. These values guide the agent in selecting the optimal next node using the Upper Confidence Bound for Trees (UCT).
The end-to-end KBQA method prematurely terminates logical form generation due to incomplete reasoning and a lack of exploration. The step-by-step KBQA method incrementally constructs logical forms but also fails, as cannot fully navigate the reasoning constraints, leading an incorrect result. In contrast, the KBQA-o1 method effectively explores and evaluates multiple reasoning paths, refining its decisions based on reward feedback and generating the correct logical form. The final agent process demonstrates how observations at each step are transformed into graph query statements, which are executed to obtain the correct answer. This process highlights KBQA-ol's 's ability to systematically decompose the query, balance exploration and exploitation, and handle multi-step reasoning effectively, outperforming other methods.
J. Error Analysis
We analyze the errors made by KBQA-o1 on the GrailQA dataset and categorize them into three main types. These errors reflect the challenges in exploring logical paths, retrieving accurate results, and ranking the most appropriate paths in the context of complex KBQA tasks.
Executable path not discovered (29.8%) In this category, KBQA-o1 fails to explore any executable logical path in the knowledge base, often due to the complexity of GrailQA's compositional and zero-shot queries. These errors arise from insufficient exploration of multi-hop reasoning paths and limited representation of rare logical forms in the training data,
22

---

KBQA-o1: Agentic Knowledge Base Question Answering with Monte Carlo Tree Search
Improvements in exploration depth and diversity of logical forms in the training process could help mitigate this issue.
Correct path not discovered (54.7%) This is the most common error type, where KBQA-ol explores logical paths but fails to discover the correct one. These errors highlight challenges in precise entity and relation retrieval, particularly in zero-shot settings where entities or relations are unseen during training. Enhancing the semantic understanding and retrieval mechanisms would be crucial for reducing this type of error.
Correct path not selected as the best (15.5%) some cases, KBQA-ol successfully explores the correct logical path but fails to select it as the optimal solution. For example, it may assign a higher Q-value to an incorrect logical form over the correct one. These errors often stem from suboptimal reward evaluation during MCTS backpropagation or inconsistencies in the reward model's fine-tuning. Addressing these issues through better reward modeling and fine-tuning could significantly enhance path selection accuracy.
K. Future Directions
The KBQA-ol offers several promising directions for future research and development. These directions aim enhance the model's capabilities, extend its application domains, and address current limitations.
Exploring Reinforcement Learning Techniques Like DPO for Continual Learning. One promising direction is leveraging advanced reinforcement learning techniques, such as Direct Policy Optimization (DPO), to enable continual learning for KBQA-ol. By refining policy and reward models through reinforcement learning, the framework could dynamically adapt to new datasets and tasks. A key challenge in this direction is constructing high-quality positive and negative sample pairs to guide the learning process effectively, Future work could explore automated methods for generating these samples or employing human-in in-the-loop systems for quality assurance.
Expanding the Set of Logical Operators for Enriched QA Patterns. To broaden the range of questions the system can handle, future research could focus introducing and supporting more diverse logical operators. This would allow KBQA-o1 ol to answer more complex queries, particularly those requiring advanced reasoning patterns such as conditional logic, aggregation, and temporal constraints. By integrating these operators, the framework could offer more comprehensive and flexible aaestion-answering capabilities, covering a wider array of user needs.
Specialized Applications in Domains like Medicine and Law. KBQA-ol has significant potential for domain domain-specifie applications, particularly in fields such medicine and law. These areas require precise reasoning and domain-specific knowledge handle intricate and high-stakes queries. Adapting the framework to these domains would involve integrating specialized knowledge bases and fine-tuning the models to align with domain-specific terminologies and reasoning patterns. Such advancements could pave the way for impactful real-world applications, including clinical decision support and legal research.
Extending to Multimodal, Multilingual, and Multi-Agent Systems. Future iterations of KBQA-ol could extend its capabilities to multimodal and multilingual settings, enabling the framework to process and reason over diverse input formats such images, audio, and text in multiple languages. Additionally, incorporating multi-agent systems could enhance the framework's ability to handle collaborative and interactive tasks, where multiple agents contribute to exploring and resolving complex queries. These advancements would significantly expand the framework's ''s usability across various scenarios.
23


Reviews:
[{"review_id": "HhSU8wJv9t", "reviewer": "Reviewer_369N", "summary": "The paper presents KBQA-o1, an agentic Knowledge Base Question Answering (KBQA) method that integrates Monte Carlo Tree Search (MCTS) for improved logical form generation. It addresses challenges in KB awareness, search efficiency, and reliance on annotated data by employing a ReAct-based agent process and incremental fine-tuning. Experiments on GrailQA, WebQSP, and GraphQ show that KBQA-o1 outperforms previous low-resource methods and approaches fully supervised performance, demonstrating strong generalization and adaptability across multiple LLMs.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your time and effort in reviewing our paper. We sincerely appreciate your feedback. Below, we respectfully provide our detailed responses to address your concerns.\n\n**Q1: Proposition 4.3 – There exists a reward threshold 𝛾∗ that ensures incremental fine-tuning improves model performance. The correctness of these claims is primarily supported by empirical results, rather than formal mathematical proofs. The paper references experimental findings (Section 5.4 and Appendices) as qualitative or quantitative justification but does not provide rigorous theoretical derivations.**\n- Thank you for your comments. The core components of KBQA-o1 in our paper include Agent Initialization, Heuristic Environment Exploration, and Incremental Fine-Tuning. We provide formal justifications for the effectiveness of these three key modules through Propositions 4.1, 4.2, and 4.3, respectively.\n- You mentioned that “these claims are primarily supported by empirical results, rather than formal mathematical proofs” and that the paper “does not provide rigorous theoretical derivations.” However, we would like to kindly clarify that in addition to the quantitative experimental results in Section 5, we have provided detailed theoretical derivations supporting these propositions in Appendices B.1, B.2, and B.3.\n- We are unsure whether this might have been an oversight or if you believe the theoretical proofs require further improvement. Please kindly let us know so we can better address your concerns.\n\n**Q2: A small-scale experiment on a different KB structure would strengthen claims of broad applicability.**\n- Thank you for the suggestion. As current KBQA tasks are primarily based on large-scale RDF knowledge bases such as Freebase and Wikidata—each containing tens or hundreds of millions of nodes—the task remains relatively complex. We have validated the effectiveness of our method across three datasets with different distributions: GrailQA, WebQSP, and GraphQ. In particular, we evaluated our approach on the more comprehensive GrailQA dataset under various settings, including I.I.D., Compositional, and Zero-Shot, which aligns with the majority of existing KBQA benchmarks. This ensures both the solidity and applicability of our approach.\n- As future work, we plan to extend our experiments to different types of knowledge base structures on a broader scale. For instance, we aim to apply our method to custom-built knowledge graphs such as those used in GraphRAG tasks, as well as to property graphs or hypergraph-based knowledge bases, to further demonstrate the broader applicability of our approach.\n\n**Q3: A discussion on why MCTS was chosen over standard RL for guiding logical form exploration would be beneficial.**\n- We initially experimented with the Direct Preference Optimization (DPO) algorithm as a standard RL-based approach for guiding logical form exploration. However, DPO requires high-quality negative samples to be effective. To this end, we attempted to construct negative samples by leveraging the erroneous branches generated during the MCTS search.\n- Nevertheless, we observed a critical challenge: due to the dense structure of large-scale knowledge bases, the differences between correct and incorrect logical forms are often very subtle. For instance, the correct relation might be film.actor.film, while a near-miss incorrect one could be tv.tv_actor.starring_roles. Despite their structural difference, these relations are semantically very close. DPO struggles to distinguish such fine-grained differences in structured outputs, resulting in subpar performance compared to supervised fine-tuning (SFT) with only positive samples.\n- Given these limitations, we opted to use MCTS for logical form exploration, which provides a more interpretable and controllable mechanism to search over the space of structured queries. Furthermore, we noted recent advances such as GRPO, proposed by DeepSeek-R1, which uses end-to-end reinforcement learning with reward signals to guide structured generation. Inspired by this, we plan to explore replacing the MCTS process with an end-to-end RL paradigm in future work to further enhance performance.\n\nAt last, we sincerely appreciate your valuable feedback, and we will carefully consider all your suggestions to further improve our paper. Thank you very much!", "claims_and_evidence": "Yes. The paper provides substantial empirical evidence to support its main claims.", "methods_and_evaluation_criteria": "The methods and evaluation criteria in the paper are generally appropriate and well-aligned with the KBQA task. The authors evaluate KBQA-o1 on three widely used benchmark datasets—GrailQA, WebQSP, and GraphQ—which are standard for assessing KBQA models, particularly in low-resource settings. The use of F1 score and Exact Match (EM) as evaluation metrics is also consistent with prior work in this domain.", "theoretical_claims": "The paper presents several theoretical claims related to the effectiveness of its agentic KBQA approach with Monte Carlo Tree Search (MCTS). \nProposition 4.1 – The agent’s awareness of the KB environment improves logical form generation compared to end-to-end methods.\nProposition 4.2 – The MCTS-based heuristic method balances search efficiency and effectiveness better than Chain-of-Thought (CoT) and Tree-of-Thought (ToT) methods.\nProposition 4.3 – There exists a reward threshold 𝛾∗ that ensures incremental fine-tuning improves model performance.\nThe correctness of these claims is primarily supported by empirical results, rather than formal mathematical proofs. The paper references experimental findings (Section 5.4 and Appendices) as qualitative or quantitative justification but does not provide rigorous theoretical derivations.", "experimental_designs_or_analyses": "The experimental design and analysis in the paper are generally sound and well-structured, providing strong empirical support for the proposed KBQA-o1 method. The authors evaluate their approach on three widely used KBQA benchmarks (GrailQA, WebQSP, GraphQ) under a low-resource setting, which aligns well with the paper’s focus on improving performance with limited annotated data.", "relation_to_broader_scientific_literature": "The paper’s contributions are well-situated within the broader scientific literature on Knowledge Base Question Answering (KBQA), heuristic search methods, and large language models (LLMs) for reasoning. It builds upon existing techniques while introducing novel elements to improve logical form generation and exploration efficiency.\n\nNovelty & Contribution to Literature\n\nAgentic KBQA with MCTS: The combination of ReAct agents and MCTS for KBQA reasoning appears to be a novel approach that improves search efficiency while maintaining flexibility.\n\nIncremental Fine-Tuning for KBQA: The method’s use of self-annotated logical forms aligns with semi-supervised learning approaches, providing a scalable alternative to purely supervised KBQA models.\n\nImproved Low-Resource Performance: Unlike previous KBQA methods that depend heavily on large annotated datasets, KBQA-o1 achieves strong performance with limited supervision, making it more practical for real-world applications.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "Strengths:\n\nWell-Defined Problem Scope & Contribution: The paper clearly identifies key challenges in KBQA, such as poor KB awareness, large search spaces, and reliance on annotated data, and proposes a well-motivated solution with KBQA-o1. The integration of ReAct-based agent reasoning with Monte Carlo Tree Search (MCTS) is a creative and effective combination of existing ideas.\n\nStrong Empirical Performance: The method outperforms state-of-the-art low-resource KBQA methods on standard benchmarks (GrailQA, WebQSP, GraphQ). It demonstrates competitive performance even against fully supervised methods, highlighting its effectiveness in low-data scenarios.\n\nWeaknesses & Suggestions:\n\n1. A small-scale experiment on a different KB structure would strengthen claims of broad applicability.\n2. A discussion on why MCTS was chosen over standard RL for guiding logical form exploration would be beneficial.", "other_comments_or_suggestions": "Please refer to the above section.", "questions_for_authors": "Please refer to the above section.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "cknMrly547", "reviewer": "Reviewer_2GGj", "summary": "This paper proposes a novel ​agentic KBQA framework that integrates ​Monte Carlo Tree Search (MCTS) with large language models (LLMs) to address challenges in low-resource and complex reasoning scenarios.  \n\nThere are too many baselines not being discussed or compared, which makes this paper far from technically sound since the performance and efficiency are both unsatisfactory.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your time and effort in reviewing our paper. We sincerely appreciate your feedback. We understand that your main concerns center around two key aspects: **performance** and **efficiency**. Below, we respectfully provide our detailed responses to address these points.\n\n**< Performance >**\n\n**Q1: \"Too many baselines are missed to be discussed and compared, e.g., RoG, GNN-RAG, StructGPT, etc.\"**\n- Thanks. Methods like RoG, GNN-RAG, and ChatKBQA rely on annotated data (e.g., WebQSP, CWQ) for tuning. However, as Gu et al. note, such data is **often unavailable in practice**, making current KBQA approaches **overly dependent on supervision**. This motivates **few-shot evaluation (<=100 examples), which is the setting adopted by KBQA-o1 and all baselines in our work**, as shown in Table 2.\n- We also evaluated KBQA-o1 under full supervision, where it performs also strongly. However, as leaderboard gains have plateaued, we focus on the more practical challenge of low-resource KBQA and omit these results from the paper. For reference, the full-supervised comparison is:\n\n| Type        | Method                  | WebQSP F1 | WebQSP Hit@1 | WebQSP Acc | CWQ F1 | CWQ Hits@1 | CWQ Acc |\n|-------------|--------------------------|-----------|---------------|-------------|--------|-------------|----------|\n| End-to-end  | RoG                 | 70.8      | 85.7          | -           | 56.2   | 62.6        | -        |\n|             | GNN-RAG                 | 73.5      | 82.8          | -           | 60.4   | 62.8        | -        |\n|             | ChatKBQA            | 83.5      | 86.4          | 77.8        | 81.3   | 86.0        | 76.8     |\n| Step-by-step| Pangu                | 79.6      | -             | -           | -      | -           | -        |\n|             | StructGPT            | 72.6      | -             | -           | -      | -           | -        |\n|             | ToG                 | -         | -             | 82.6        | -      | -           | 69.5     |\n|             | KG-Agent             | 81.0      | 83.3          | -           | 69.8   | 72.2        | -        |\n| Heuristic   | **KBQA-o1 (Ours)**       | **85.7**  | **88.3**      | **81.7**    | **83.9**| **89.5**    | **80.7** |\n\n**Q2: \"The performance is not satisfying, even though many baselines are not compared. For example, RoG is 70.8% in terms of F1 score on WebQSP.\"**\n- Thanks. Compared to RoG’s 70.8 F1 under full supervision, KBQA-o1 achieves 67.0 F1 with only 100 labels, showing strong low-resource potential. Under full supervision, which is the same settings as RoG's, KBQA-o1 further reaches 85.7 F1, outperforming RoG and achieving SOTA. However, our focus remains on more practical low-resource KBQA, not fully supervised settings.\n\n**< Efficiency >**\n\n**Q3: \"Six minutes for one query is not acceptable for either research or industrial scenarios.\"**\n- Thanks. There is a factual misunderstanding. As shown in **Figure 4(c)**, the x-axis represents **Query per Minute**, and KBQA-o1 achieves approximately **6 queries per minute**, not **“Six minutes for one query”** as the review states.\n- With an average of ~10 seconds per query, KBQA-o1 offers efficient, high-quality KB reasoning for either research or industrial scenarios.\n\n**Q4: \"There is no exploration and exploitation trade-off since high exploration w improves accuracy but slows down the inference, while lower weights risk suboptimal performance.\"**\n- Thanks. Indeed, increasing w enhances accuracy while decreasing efficiency. However, this process is not linear. As shown in Figure 5(c), both effectiveness and efficiency stabilize after w reaches a certain threshold, indicating a trade-off can be achieved within a proper w. \n- This trade-off arises from the reward mechanism and the UCT selection algorithm in MCTS, making MCTS inherently heuristic. A detailed proof is provided in Appendix B.2.\n\n**< Other Comments >**\n\n**Q5: \"The reward model evaluates logical forms based on syntax and answer alignment but ignores semantic plausibility.\"**\n- Thanks. Our reward is not solely based on syntax or answer alignment. As shown in Equation (9), it combines the policy model’s semantic score and the reward model’s syntax score via weighted fusion, enabling a more robust evaluation that accounts for both semantic plausibility and structural correctness.\n\n**Q6: \"ReAct is already not suitable for QA, let alone the combination with MCTS. \"**\n- Thanks. In KBQA-o1, we only use ReAct as a standardized prompt format to formulate the agent process. These prompts are fixed and embedded via instruction tuning. Thus, whether ReAct is “suitable for QA” is irrelevant to our setting and does not impact our method’s effectiveness.\n\nAt last, we sincerely appreciate your valuable feedback, and we will carefully consider all your suggestions to further improve our paper. We would be deeply grateful if you could kindly reconsider raising the score to 3 or above. Thank you very much!", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "1. MCTS requires multiple rollouts and tree expansions, leading to increased latency for complex queries.\n2. The reward model evaluates logical forms based on syntax and answer alignment but ignores semantic plausibility. Also there is no exploration and exploitation trade-off since high exploration w improves accuracy but slows down the inference, while lower weights risk suboptimal performance.", "theoretical_claims": "The methods and comparisons are theoretically analyzed.", "experimental_designs_or_analyses": "1. The efficiency is really bad. ReAct is already not suitable for QA, let alone the combination with MCTS. Six minutes for one query is not acceptable for either research or industrial scenarios.\n2. Too many advanced baselines missed to be compared, e.g., RoG, GNN-RAG, StructGPT.\n3. The performance is not satisfying, even though many baselines are not compared. For example, RoG is 70.8% in terms of F1 score on WebQSP.", "relation_to_broader_scientific_literature": "Closely related.", "essential_references_not_discussed": "Too many baselines are missed to be discussed and compared, e.g., RoG, GNN-RAG, StructGPT, etc.", "other_strengths_and_weaknesses": "NA", "other_comments_or_suggestions": "NA", "questions_for_authors": "Please check the comments and weaknesses.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DjPovZtI6m", "reviewer": "Reviewer_FcKz", "summary": "The paper introduces KBQA-o1, a novel agentic Knowledge Base Question Answering (KBQA) method that leverages Monte Carlo Tree Search (MCTS) to address challenges in KBQA, such as weak KB awareness, the trade-off between effectiveness and efficiency, and high reliance on annotated data. The proposed method employs a ReAct-based agent process for stepwise logical form generation and uses MCTS to balance exploration performance and search space. Additionally, KBQA-o1 generates high-quality auto-annotated data through heuristic exploration, reducing the need for extensive human annotation.", "questions": "", "limitations": "", "rating": 5, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your time and effort in reviewing our paper. We sincerely appreciate your feedback. Below, we respectfully provide our detailed responses to address your concerns.\n\n**Q1: Limited Evaluation on Real-World Scenarios: While the paper demonstrates strong performance on benchmark datasets like GrailQA, WebQSP, and GraphQ, it lacks evaluation in real-world, noisy, or incomplete knowledge base scenarios. Real-world KBs often contain incomplete or inconsistent data, and the robustness of KBQA-o1 in such settings remains unclear. Including experiments on more diverse and noisy datasets would strengthen the paper's claims about the model's practical applicability.**\n- Thank you for raising this important point. We fully agree that evaluation under real-world, noisy, or incomplete KB conditions is critical for practical applicability.\n- KBQA-o1 is inherently designed to address real-world challenges such as missing entities, non-standard relations, and schema inconsistency. Its environment-aware agent dynamically interacts with the KB during logical form construction, enabling stepwise adaptation to incomplete or unstable KB structures—an advantage over static or end-to-end approaches.\n- To improve robustness, KBQA-o1 uses SimCSE-based semantic matching in MCTS expansion, allowing flexible matching of noisy or ambiguous relations. This reduces reliance on rigid schema annotations and improves generalization to noisy KBs.\n- While our experiments are conducted on standard datasets, GraphQ in particular is widely recognized as a noisy and structurally diverse benchmark. KBQA-o1 achieves a 19.4 F1-point improvement over previous methods on GraphQ, showing strong performance under noisy conditions.\n- We further simulate real-world scenarios via incremental self-supervised learning: starting with minimal labeled data, KBQA-o1 explores unlabeled questions using MCTS and filters high-quality logical forms via a reward model for fine-tuning. This aligns with the practical need for robustness under low-annotation settings.\n- We also identify real-KB evaluation as a key future direction. Our Impact Statement and Appendix outline plans to test on domain-specific KBs (e.g., medicine, law), simulate KB incompleteness via subgraphs, and explore continual learning strategies like DPO.\n\n**Q2: Scalability Concerns: The paper does not thoroughly address the scalability of the proposed method, especially when dealing with extremely large knowledge bases. Although MCTS is designed to balance exploration and exploitation, the computational overhead of performing multiple rollouts on large-scale KBs could be significant. A more detailed analysis of the computational complexity and runtime performance on larger KBs would be beneficial.**\n- Thank you for raising this important concern. We fully recognize that scalability is critical for practical deployment of KBQA on large-scale knowledge bases.\n- While KBQA-o1 adopts MCTS, it does not rely on exhaustive search. Instead, it integrates an environment-aware agent with policy-guided local exploration. At each step, we use SimCSE-based semantic retrieval (Eq. 6) to narrow the candidate actions to a small, relevant subset, significantly reducing the search space—even in large KBs.\n- To balance quality and efficiency, we apply stage-specific MCTS settings: a higher exploration weight w = 50 during training to ensure logical form quality, and a lightweight setting w = 10 during inference to reduce rollout cost. As shown in Figure 5(c), this effectively ensures both performance and scalability.\n- We also present empirical results on query throughput vs. accuracy (Figure 4(c)), showing that KBQA-o1 outperforms CoT and ToT variants in both accuracy and runtime. In the final version, we will further include a theoretical analysis of complexity, including rollout cost, SimCSE retrieval overhead, and search depth.\n- Importantly, the experiments in our paper are conducted on Freebase, which itself is a massive real-world KB with tens of millions of entities and triples. The fact that KBQA-o1 operates efficiently on Freebase already demonstrates its practical scalability under large-KB conditions.\n\nAt last, we sincerely appreciate your valuable feedback, and we will carefully consider all your suggestions to further improve our paper. Thank you very much!", "claims_and_evidence": "The claims are well-motivated and largely supported by theoretical and empirical evidence", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria are appropriate and well-aligned with the paper’s goals.", "theoretical_claims": "I reviewed the theoretical claims, including proofs in the main paper.", "experimental_designs_or_analyses": "The experimental designs are largely sound.", "relation_to_broader_scientific_literature": "N/A", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Weaknesses:\n\n**Limited Evaluation on Real-World Scenarios:** While the paper demonstrates strong performance on benchmark datasets like GrailQA, WebQSP, and GraphQ, it lacks evaluation in real-world, noisy, or incomplete knowledge base scenarios. Real-world KBs often contain incomplete or inconsistent data, and the robustness of KBQA-o1 in such settings remains unclear. Including experiments on more diverse and noisy datasets would strengthen the paper's claims about the model's practical applicability.\n\n**Scalability Concerns:** The paper does not thoroughly address the scalability of the proposed method, especially when dealing with extremely large knowledge bases. Although MCTS is designed to balance exploration and exploitation, the computational overhead of performing multiple rollouts on large-scale KBs could be significant. A more detailed analysis of the computational complexity and runtime performance on larger KBs would be beneficial.", "other_comments_or_suggestions": "Please see weakness.", "questions_for_authors": "Please see weakness.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "o8jySmVZYQ", "reviewer": "Reviewer_nGUT", "summary": "This paper proposes KBQA-o1, which utilizes Monte Carlo Tree Search and ReAct-based agent process to generate stepwise logical form with knowledge base environment.The incremental finetuning strategy on automatically labeled examples further enhances the performance. According to the experiment results, KBQA-o1 can outperform previous few-shot KBQA methods with open-source LLM like Llama-3.1-8B.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your time and effort in reviewing our paper. We sincerely appreciate your feedback. Below, we respectfully provide our detailed responses to address your concerns.\n\n**W1: The efficiency analysis is reflected by the number of queries per minutes, just wondering how many queries are required to be executed for one target question on average.**\n- We thank the reviewer for raising the concern regarding efficiency analysis. The reviewer asked about “the average number of queries required to be executed for one target question” to better understand the efficiency of the proposed method. In Section 5.4 (Comparison Analysis) and Figures 4(c) and 5(c), we have already provided a detailed analysis of the trade-off between query frequency (queries per minute) and accuracy (F1 score).\n- It is important to emphasize that our KBQA-o1 method adopts a dedicated efficiency-oriented MCTS parameter setting θ_eff during the prediction phase (see Section 4.3 and Figure 5(c)), which significantly reduces the number of queries per question. Compared with the exploration phase that uses higher MCTS weights, the prediction phase achieves a substantial improvement in overall efficiency while sacrificing only a marginal amount of accuracy. Moreover, Figure 4(c) provides a comparative analysis with other baseline methods under the same evaluation protocol, showing that KBQA-o1 achieves higher accuracy while maintaining a competitive level of query efficiency.\n- Regarding the average number of queries per question, since KBQA-o1 adopts Monte Carlo Tree Search (MCTS), which is a tree-based heuristic search algorithm, the number of queries is not fixed, but dynamically determined by the search space, question complexity, and the model’s policy. Therefore, we argue that query frequency (queries per minute) is a more comprehensive and practical indicator of efficiency in real-world applications.\n\n**C1: There maybe a typo before equation 13. Then, we discard the annotation by choosing if the answer set is not empty... should be if the answer set is empty...**\n\n- Thank you for pointing out the typo. The sentence before Equation (13) should indeed read “if the answer set is empty” instead of “not empty.” This will be corrected in the revised version.\n\n**C2: In equation 10, in the sum operator, the upper bound and lower bound should be reversed**\n\n- Thanks for noticing the issue in Equation (10). The summation bounds should indeed be reversed, and we will make the necessary correction in the updated paper.\n\n**Q1: In Table 7, I find that the reward threshold is higher for easier datasets like webqsp, could you provide more insights when you choose this parameter?**\n- Thank you for the question. The reward threshold γ* is indeed a key parameter in filtering auto-labeled samples during incremental fine-tuning. While we adopt a unified reward model across all datasets, the distribution of reward scores varies due to differences in dataset difficulty, logical form complexity, and question types.\n- For relatively easier datasets like WebQSP, the generated logical forms are typically shorter and more confident, leading to overall higher reward scores. To ensure quality, we set a higher γ* to filter out over-confident but potentially incorrect samples. Conversely, in more complex datasets such as GrailQA and GraphQ, the model is more conservative, and the reward scores tend to be lower. Thus, a lower γ* is chosen to retain sufficient high-quality samples for fine-tuning.\n- To determine γ*, we follow a validation-based selection strategy:\n    1.\tWe first apply the reward model to score auto-labeled logical forms on a validation subset;\n    2.\tWe then plot the relationship between the reward threshold γ*, the proportion of selected samples, and their downstream F1 performance, as shown in Figure 5(b);\n    3.\tFinally, we choose the γ* that optimizes the trade-off between data quality (reward score) and model improvement (F1 score).\n- To improve efficiency, in practice, we adopt a simple yet effective strategy: we set γ* such that approximately the top 90% of auto-labeled samples are retained, filtering out only the bottom 10% with the lowest reward scores.\n\n**Q2: Have you tried applying RL instead of SFT for optimization?**\n- Thank you for your question. Due to the letter limitation, please refer to **our response to the last question of Reviewer 369N**, which is the same question as this. \n\nAt last, we sincerely appreciate your valuable feedback, and we will carefully consider all your suggestions to further improve our paper. Thank you very much!", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "Yes", "experimental_designs_or_analyses": "Yes", "relation_to_broader_scientific_literature": "KBQA-o1 adapts MCTS algorithm from o1 to KB-specific question answering tasks, which shows advantages compared to previous end-to-end and step-by-step methods as it allows stepwise adjustments by KB environment awareness.", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "Strengths:\n1. This paper proposes KBQA-o1, which shows good potential to solve KBQA in low-resource setting with open-source model.\n2. The experiment and analysis is comprehensive.\n\nWeaknesses:\n1. The efficiency analysis is reflected by the number of queries per minutes, just wondering how many queries are required to be executed for one target question on average.", "other_comments_or_suggestions": "1. There maybe a typo before equation 13. Then, we discard the annotation by choosing if the answer set is not empty... should be if the answer set is empty...\n2. In equation 10, in the sum operator, the upper bound and lower bound should be reversed", "questions_for_authors": "1. In Table 7, I find that the reward threshold is higher for easier datasets like webqsp, could you provide more insights when you choose this parameter?\n2. Have you tried applying RL instead of SFT for optimization?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper introduces KBQA-o1, an agentic KBQA method that combines MCTS and LLMs to improve logical form generation in KBQA. The method shows strong performance on multiple datasets (GrailQA, WebQSP, and GraphQ), even in low-resource settings. It uses a ReAct-based process and MCTS to tackle challenges like weak KB awareness, inefficiency in search, and too much reliance on annotated data. The paper does a good job of backing up its claims with experimental evidence, and it proposes some interesting new ways to deal with complex reasoning tasks. However, there are a few weaknesses, like limited evaluation in real-world scenarios and scalability issues when working with very large knowledge bases.

The paper could improve by testing the method on more diverse and noisy KBs (real-world situations) and discussing scalability concerns more thoroughly. More experiments with large-scale KBs and practical, messy data would help show how well the method works outside controlled settings.
Decision: Accept (poster)