Plan-Answer-Refine-on-Graph: Structured Planning and Self-Refinement for Large Language Model Reasoning on Knowledge Graphs
Authors: Yuxin Shi
Han Fu
Zhuo Li
Chenghao Liu
Xiaoxue Ren
Jianling Sun
Venue: ICLR 2026 Poster (2026)
Keywords: Knowledge Graphs
Large Language Models
Question Answering
Primary area: foundation or frontier models, including LLMs

Abstract: Incorporating knowledge graphs (KGs) into large language model (LLM) reasoning has shown promise in alleviating hallucinations and factual errors. Although existing paradigms of KG-augmented LLMs have achieved encouraging results, they still exhibit notable limitations when handling multi-hop reasoning and complex logical queries: (1) search space truncation bias: current methods generate linear entity-relation reasoning paths, which can prune correct candidates prematurely during iterative exploration; and (2) entity error amplification: existing methods typically follow the retrieve-and-answer paradigm which causes LLMs to over-rely on retrieved evidence, exacerbating the impact of incorrect entities during reasoning. To alleviate the existing challenges, we propose Plan-Answer-Refine-on-Graph (PARoG), a novel framework for LLM reasoning on knowledge graphs. First, PARoG leverages SPARQL queries from KG data as references, decomposing them into structured step-by-step plans. We further train LLMs to construct such structured plans, which improves the logical consistency of reasoning, ensures uniform step granularity, and facilitates effective execution on the graph. Second, during reasoning over KGs, PARoG adopts a plan-answer-refine paradigm: the model first attempts to answer each sub-query independently, and then refines its prediction by integrating evidence retrieved from the KG. This process mitigates knowledge conflicts between LLM and KG, substantially reducing hallucinations. Experimental results on multiple KG reasoning benchmarks demonstrate that PARoG significantly outperforms state-of-the-art approaches, achieving especially superior accuracy on multi-hop and logically complex queries.

Published as a conference paper at ICLR 2026
PLAN-ANSWERRREENN-OOOGGAAA STRUCTURED PLANNING AND SELF-REFINEMENT FOR LARGE LAN- GUAGE MODEL REASONING ON KNOWLEDGE GRAPHS
Yuxin Shi', Han Fu Zhuo LiP, Chenghao Liu"; Xiaoxue , Jianling Sun Zhejiang University, State Street Technology (Zhejiang) Ltd, Richoo AI, 4 Datadog Al Research {yxshi, lizhuo, xxren, (unjjiezzuu.eliee fuhan@richoo.ce twinskenggmail.com com com
ABSTRACT
Incorporating knowledge graphs (KGs) into large language model (LLM) rea- soning has shown promise in alleviating hallucinations and factual errors. Al- though existing paradigms of KG-augmented LLMs have achieved encouraging results, they still exhibit notable limitations when handling multi-hop reasoning and complex logical queries: (1) search space truncation bias: current meth- ods generate linear entity-relation reasoning paths, which can prune correct can- didates prematurely during iterative exploration; and (2) entity error amplifica- tion: existing methods typically follow the retrieve-and-answer paradigm which causes LLMs to over-rely retrieved evidence, exacerbating the impact of in- correct entities during reasoning. To alleviate the existing challenges, we pro- pose Mka--Answer-Refin-oon-GGC soning on knowledge graphs. First, PARoG leverages SPARQL queries from KG data as references, decomposing them into structured step-by-step plans. We further train LLMs to construct such structured plans, which improves the logical consistency of reasoning, ensures uniform step granularity, and facili- tates effective execution on the graph. Second, during reasoning over KGs, PARoG adopts plan-answwr--reing paradigm: the model first attempts to an- swer each sub-query independently, and then refines its prediction by integrat- ing evidence retrieved from the KG. This process mitigates knowledge conflicts between LLM and KG, substantially reducing hallucinations. Experimental re- sults on multiple KG reasoning benchmarks demonstrate that PARoG signifi- cantly outperforms state-of-the-an approaches, achieving especially superior ac- curacy on multi-hop and logically complex queries. Our code is available at hatpps://on wiigghhthh.... com/
(PARoG), novel framework for LLM rea-
INTRODUCTION
Large Language Models (LLMs) (Brown et al. 2020 Ouyang et al. 2022 OpenAl et al. 2023
Dubey et al., 2024 Guo et al. 2025) have demonstrated remarkable reasoning capabilities in a wide range of complex natural lan language processing tasks (Bang et al.) 2023 Zhao et al.) 2023 Huang & Chang 2023 Qiao et al. 2023). However, LLMs remain prone to hallucinations and factual errors in real-world applications due to their reliance on implicit parametric knowledge (Hu et al. 2023 Wang et al. 2023a Huang et al. 2024]. Knowledge graphs (KGs), as large-scale structured external source of factual knowledge, offer explicit, interpertable relational structures which can ground LLM reasoning, providing a natural complement to limitations of LLMs (Pan et al. 2024).
Recent LLL approaches be categorized into two paradigms. The first leverages step-wise graph exploration, where LLMS iteratively perform entity-relation walks to progressively construct reasoning paths (Sun et al., 2024: Ma al. 20255.. The second generates global reasoning plans where questions are decomposed into sub-objectives and the KG is queried along the planned path
Work was done before joined Datadog Corresponning authors.

---

Published as a conference paper at ICLR 2026
Question I. What country bardering Fronce contains on airport that serves Nijmegen??
Step-1. identify countrees that barder France.
Step-1. Findd Countries that Bardaring France.
Step-2. Search for
Top-K
Step-2 Find Countries that contain an arport that servis Nijmagen.
Puaia
sirports in those bordering countries.
Fronce
Ergland
Conjunction
Step-3. wheckwhich sirport serves Nimegen
Germary)
Stap-2. Find the conjunction of above.
(a) Existing Work (e.g., Po6)
(b) PARoG (ours)
Question II. What location appointed Dennis Daugoord to governmental position and bisected by the Miissouri River?
Apporadi
Bivd
Bard
Inibial
Dougaing
Darrpe Despoent noe apprinted to a govermments Bouth Dancts and Missourt Rover bisceted hee Unikd States Amenica have no about location
Daugangg
River biects the videe Misocari Booth
Dakcta and
Dulita
Duluts
partuch
South
appsinted Dauqaard govamementa go besucted Munsout fover
partell contatel)
Souh
S Selt- Ralinament
South Dancta Karsss
S
Enough Information
Fower
Acconding rigng to the information in swarthee South Dakota s both locttoo appo localtio biseoted by Missout Rivor.
Dougoard
Strkc
And need continue rearchngg
(a) Existing Work (e.g.. Po6)
(b) PARoG (ours)
Figure 1: Illustration of the challenges in the existing methods and how our proposed PARoG ad- dresses these issues: I. Search Space Truncation Bias and II. Error Amplification.
to obtain external information (Luo et al. 2024 Chen et al. 2024b). Though demonstrating notable improvements, these methods often struggle with complex logical queries that involve conjunctions or multiple constraints. Our systematic analysis of existing approaches (as described in Appendix
B identifies the following two fundamental limitations.
Search Space Truncation Bias due to Linear Reasoning Paths. Current methods construct rea- soning paths primarily along linear entity-relation steps, iteratively expanding from one entity to its neighbors. To control the combinatorial explosion of graph exploration, they prune candidate entities at each step (e.g., using top-k selection). While efficiency, this strategy often eliminates cor- rect entities prematurely. For instance in Figure [ (I-a), the correct answer Germany is eliminated early due to pruning, leading to an incorrect prediction. A more reasonable planning strategy would first decompose the question into two sub-problems: (i) identify countries bordering France, and (ii) identify countries with airports serving Nijmegen, and then compute the conjunction of these results. The limited planning capability of existing methods fundamentally biases the search space and limits reasoning performance.
Error Amplification from Faulty Entities and Relations. LLM --M--eeeerttdd reasoning paths may introduce spurious or weakly related entities and relations during KG exploration. Existing methods typically follow a sarrive-andd-nswewr paradigm, where the LLM heavily relies on the retrieved evidence to produce the final answer. This reliance amplifies errors. For example in Figure [ aI),,,, during graph-based reasoning, the system retrieves facts such as "Dennis Daugaard was appointed by David Anderson in South Dakota" and "Missouri River is partially constrained by South Dakota, USA". Though individually correct, the knowledge are not sufficiently directly connected to answer the question. Existing methods typically make the LLM to over-rely on the retrieved information, attempt further reasoning steps, and ultimately fail to produce the correct answer.
To alleviate theses challenges, we propose a Plan-Answer-Refine framework (PARoG), a hybrid reasoning paradigm that tightly integrates structured explicit guidance with parametric LLM reason- ing. As shown in Figure our method introduces two key technical contributions. First, we leverage SPARQL queries as the structured references to supervise planning and train the planning module using a relatively smaller model (e.g. I.aama-31 1-1aa...1B))))). 1-8B) to generate flexible, compositional reasoning paths that allow complex logical operations over sub- sub-queries (e.g. conjunctions, compositions, su- perlatives and comparatives). For example in Figure (Ibb, instead of searching sequentially from "France" to its neighboring countries and then their airports, the model can generate conjunctive sub-objectives such as "find countries bordering France" and "find countries with airports serving Nijmegen," then reason over the combination of the sub-objectives, which mitigates search space truncation bias by moving beyond linear expansions. Second, rather than committing to retrieved entities in one-shot retrieve-ande and-aassee paradigm, PARoG first produces tentative answer using
2

---

Published as a conference paper at ICLR 2026
Question, What is the copitel city of the geagrophir
Question What country bardering France contains on dirport That service mevern?
division where the religioss organizat and lenderstiip is colled the Orthodox supocophoouu Church Albario?
Plasnigg
Step- 1, Find Countric that Bortering Fredce
SPAROL
Countrcc contain
Mimaggn.
conqunction
Weikee
Ten taak our mnethoe sectore for you1, ont) autiiaton
Scarchit
Arainzzing
Germaryy England Italy,
selpas pous aaoi, cupuege depuo. appile
France
England
Cermany
Arswer Comrers
Refineentt
lul
GPT-4
Sap-1
Planning Module (e Liame-S.1)
Step-1, ideelity the nei melgiiss organizational waseenttip
Russla
Gornary
Scarchit
SF
Arsinziig
Answer:
the Orthodoo Autseopholous Church
roigious bodership is pitated
Self Refinement
Step-3 capioal city geographic diviion
Answer Garmany.
Cammany Ling
Germany and Runeis
Training
3ap-3
Arsswer: Gemmary
(a) SPARQL--Gided Structured Planning
(b) Plan-Answer-Be Refine Paradigm
Figure 2: Overall framework of the proposed PARoG. Unlike prior methods that sequentially expand entity-relation paths with pruning, and follow the one-shot strreve-andd-nswer paradigm, PARoG combines (a) structured planning with (b) iterative self-refinement, enabling robust handling of com- plex logical queries with conjunctions, compositions, comparisons, superlatives.
its parametric knowledge and then explicitly refines it by referring to the retrieved KG entities as shown in Figure ( (II-b.. This refinement step overrides earlier faulty evidences, preventing error amplification due to spurious entities or weakly related relations. Our main contributions as follows:
We propose leveraging SPARQL. as structured references to supervise planning to train the model to generate compositional reasoning paths, which enables the model to handle complex logical reasoning including conjunction, composition, superlative and comparative queries.
framework, where the agent first attempts to answer then ex- plicitly refines the results using retrieved evidence. This step reduces error propagation caused by faulty entities or relations involved in the reasoning paths.
We propose a plan-answer-reht
We introduce novel framework PARoG by combining the proposed techniques and evaluate the performance on multiple real-world KGQA datasets. The experimental results demonstrate significant improvements over state-of-the -rrt--rr baselines.
We provide further analysis demonstrating that PARoG uses a relatively small model (e.g. Llama- 3. 3.1-BB (Dubey et al. (024)) to generate reasoning paths. yet its performance can surpass larger planning LLMs (e.g. ChatGPT'Open.. et al. (2023) or Deepseek-R1 (Guo et al. (025)). We also discuss the broader impact of using structured symbolic guidance with LLM reasoning beyond KGQA.
2 PRELIMINARIES
Knowledge Graph. A knowledge graph (KG) is composed of a large set of fact triples, represented as graph 9 = {(e, r, e') e, E E,r R). where È and R denote the sets of entities and relations respectively. For KGQA tasks in this paper, assume the availability of KG that contains the entities relevant to answering the given natural language question.
SPARQL Query Language. SPARQL (SPARQL Protocol and RDF Query Language) is formal query language which allows users to query structured knowledge bases. Given a question q, the SPAROL query S specifies pattern of triples match against the knowledge graph G. A general
3

---

Published as a conference paper at ICLR 2026
SPARQL query consists of SELECT clause that specifies the variables to retrieve, and WHERE clause that defines the graph pattern to match. In our method, SPARQL queries are used to supervise the generation of reasoning paths by decomposing complex queries into smaller sub-queries. Figure 2 provides an example of SPARQL query.
3 METHODOLOGY
In this section, we present PARoG, a novel hybrid reasoning framework which integrates structured guidance planning with parametric reasoning and refinement over knowledge graphs. As shown in Figure 2 PARoG comprises major Stages:SPARQL-Guiiee generate compositional planning of sub-objective paths based on SPARQL-guided supervision for knowledge graph exploration, and WJan-Answer-Refing Paradigmm-iteraiielly completing a sub- objective with parametric knowledge and then correcting the answer using external KG evidence to mitigate errors and inconsistencies.
Structured baaning-training LLMs
3.1 SPARQL-GUIDER STRUCTURED PLANNING
The current LLM@KG paradigm typically generates linear entity-relation reasoning paths. this process, the model starts from entity and iteratively explores its neighbors by following predefined rontiiy-relaioonship-eee
paths While effective for simple queries, this linear path generation often fails capture complex multi-step reasoning required for more sophisticated queries. Specif- ically, when reasoning over complex questions involving compositionality, conjunctions, compara- tives, superlatives, LLMs inherent behavior of linear exploration can lead to Search Space Trun- cation Bias, where pruning intermediate candidates prematurely eliminates correct answers.
SPARQL-Guided Supervision. To address this issue, we propose use SPARQL queries structured guide for reasoning. SPARQL inherently supports complex queries that involve logical operations. In this paper, we consider the following operation types:
Conjunctions: finding entities that satisfy multiple constraints simultancously. e.g. Find coun- tries that border France and have airports serving Nijmegen.
Compositions: expressing queries where the output of one relation serves as the input to another. e.g. Find the capital city of the country that has airports serving Nijmegen.
Comparatives: retrieving entities based on relative attributes. e.g. Find countries larger than France in area and have airports serving Nijmegen.
Superlatives: selecting the best entity according ranking predicate. e.g. Find the largest city bordering France.
When the intermediate candidate is large, these query types cannot be properly handled using linear entity-relation paths but are essential for real-world KGQA tasks.
SPARQL-to--Planning To transfer this expressiveness into model training, we leverage SPARQL queries as guidance signals and use state-of-the-an LLMs to automatically generate planning data from complex questions. For each input question, GPT-4o produces set of decomposed sub- questions that reflect the logical structure of the underlying SPARQL query. Specifically, we design a systematic pipeline to automatically construct large-scale dataset tailored for KGQA tasks. The graph- mupph-matching process in SPARQL naturally decomposes complex query into sequence of con- secutive search operations and constraints, thereby providing a precise planning path for identifying intermediate sub-objectives. Building upon this observation, the SPARQL-to-Plaae -o--nnnnn pipeline sists of the following two steps.
Source Data Collection. We first select diverse (Question, SPAROL) pairs of multi-hop queries from public KGQA training datasets including WebQSP(Yin al. 2016). CWQ (Talmor & Be- rant 2018). and GrailQA (Gu et al., 202T). These pairs serve as the foundation for aligning natural language with structured reasoning.
Semantic Consistency Mapping. With the collected data, decompose the SPARQL queries into sub-operations and then translate each atomic operation into a fluent natural language ques- tion single sub-objective of the reasoning plan. Following that, we also rephrase the decom-
4

---

Published as a conference paper at ICLR 2026
posed sub-objective sequence back natural language queries maintain the semantic consis- tency. Instead of the original questions, we use the rephrased natural language queries and the generated sub-objectives the training data
During dataset construction, the SPARQL queries are decomposed into atomic operations main- lain the consistency across plan steps. In this paper, we use GPT-4o Hurst et al. (2024) to automate the overall process. Finally, the pipeline produces 74,802 high-quality decomposition examples cov- ering wide range of query types and reasoning depths. The statistics of different query types are summarized in Figure 3
Model Training. We employ relatively small but powerful open-source model Llama-3 3. 1-8B Dubey et al., (2024) the foundation backbone. The training objective follows the standard autore- gressive language modeling loss. We provide the full input template in Appendix Given the input tokens x, the model parameters are optimized by minimizing the negative log-likelihood:
H Tk
arg min L(0) = -0000-EX
Σ
log Polorslo
(1)
8
where H and T₁, deba the total number of sub-objectives and the token number a single sub-objective respectively, and o, = fo..1.... 02.7% the h-th sub-objective. With supervised training, the model learns to map complex natural language questions into sequences of structured sub-questions which mirror SPARQL compositional logic. This training equips the planning module with the ability to produce complex logical reasoning paths (e.g. conjunctions or comparatives), ensuring correct en- tities are preserved during exploration and mitigating the Search Space Truncation Bias of existing approaches.
Compositions
Conjunctions
Superlatives
Comparatives
Linear Queries
25.22%
29.68%
4.49%
4.83%
3.2 PLAN-ANSWER REFINE PARADIGM
35.78%
Another fundamental challenge for LLM reasoning is Error Ampli- fication from Faulty Entities and Relations. Existing methods typically paradigm, where LLM generates
adopt the one-shot retrieve-and-answee a reasoning path, retrieves corresponding entities and relations from the KG, and then directly uses these retrieved facts to finalize an answer. Though intuitive, this paradigm suffers from two issues:
Figure 3: Statistics of different query types of the generated planning data.
Error Propagation. When a spurious or weakly related entity is introduced by the reasoning path, the subsequent steps will propagate and accumulate this error.
Over-Reliance on Retrieval. LLMs often assumes the retrieved evidences from KG to be correct and sufficient, even when the external information only partially address the query. This over- reliance prevents the model from self-correcting, leading to faulty answers.
To mitigate this challenge, we introduce the plan-answer-refine mechanism. We employ the LLMs generate tentative answer using the parametric reasoning ability and then leverage the KG rea- soning agent to iteratively explore the knowledge graph obtain external information and refine the answer by adjusting entities or relations. The algorithmic procedure this mechanism is summa- rized in Appendix D
Answering. Let denotes the reasoning plan generated by the planning module. For each sub- objective O generated by the planning module, the initial step is leveraging a LLM M to generate a tentative answer as:
à M(Q, oi, IA)
where La denotes predefined instruction template and Q is the input question.
Exploration. The KG exploration process of PARoG is similar to existing work (Sun et al.
2024
Chen al. 2024b). To be specific for each sub-objective, PARoG starts from entity and iteratively exploring the knowledge graph. Following previous work (Sun)
mitia
al. 2024 Jiang al. 2023a), the iterations begins with set of no topic entities En
5

---

Published as a conference paper at ICLR 2026
fct.el..... eg.....,c,, cho For the i-th iteration (i 1), we first obtain the current set of K reason- ing paths Pi-1 = pl : .Pk after previous i - 1 iterations. Here, each reasoning path ".,,,,) ",,", (c,,,, 1, oook
Pk = [(ea,) . Sa,k
1,1 1-1,1
(0 ()) ").... (c 1- 2h ee.))) is a sequence
of Tu triples (Tx < 1) where indexes the elements, e. and 6o, denote the subject and ri- is relation linking them. Then, we continue extend the reasoning paths forward based on the current triples. Concretely, the set of tail nodes in the current reasoning paths is denoted by E = - . ... e and the relation set is rep- resented R {rt ,72 1- .... ri We then expand the reasoning path through search- ing over relations entities. With the original question Q and sub-objectives O, we leverage the LLMs to select the most relevant relations and entities. Specifically, during the relation search- ing stage, we begin with all relations connected to the tail entities in E which are denoted by R = 1rimit, r mintt, 21......... r p. and employ the L.M to filter out irrelevant relations. In this step, the entire reasoning plan O is also provided to the LLM so that the model maintains aware- ness of the global reasoning objective, thereby preventing from over-focusing on local. Given the tail entities and filtered relations, the missing entities are obtained using predefined SPARQL query templates such as (e, r, ?) or (?.r.e), When all the entities are obtained, we leverage the model to further calculate the relevance between the retrieved entities and the current sub-objective og and the question Q. The most relevant entities from a large set of candidates are reserved to update the reasoning path set, which is denoted by P..
object entities respectively, and rh
Self-Refinement. After each KG exploration iteration, PARoG explicitly re-evaluate the tentative answer against the retrieved evidences. If inconsistencies supplementary are detected, PARoG refines the result by adjusting entities or relations, effectively correcting errors from earlier steps. Specifically we use the LLM M to correct answer 0; as:
a; =M(Pp og, a,, IR.
(3)
where Pa denotes the set of retrieved triples in the current iteration, and I is the instruction prompt. It is also worth noting that also explicitly ask the LLM to judge whether the retrieved knowl- edge aligns with the question; if it does not, the generated tentative answer is directly used instead. After each round of self-refinement, PARoG is leveraged to determine whether the current result a; is sufficient to answer the overall question Q. If the answer is "yes", we stop searching and use a; as the final answer to avoid over-exploration. Otherwise, PARoG continues iterative searches until PARoG finds enough knowledge or reach the maximum number of iterations. Unlike existing meth- ods, PARoG introduces a mechanism that explicitly integrates the parametric knowledge of LLMs with external knowledge, reducing reliance on any single retrieval and providing resilience against misleading entities or relations.
4 EXPERIMENTS
Datasets. We conduct comprehensive experiments multiple Knowledge Graph Question Answer- ing (KGQA) benchmark datasets to evaluate the effectiveness of our proposed approach. Specifi- cally, we utilize three widely-adopted datasets: WebQSP (Web Questions Semantic Parses) (Yih ett al. 2016). GrailQA (Strongly Generalizable Question Answering) (Gu et al. 202T). and CWQ (Complex Wellueeieeuus)ins (Talmor & Berant 2018). All three datasets are grounded on the Freebase knowledge graph, which contains 88 million entities, 20K relations and 126 million triplets, making it one of the most comprehensive knowledge bases for KGQA evaluation.
Metrics. For evaluation, we adopt the Exact Match accuracy (Hits@) 1) as our primary metric, which measures the percentage for which the predicted answer exactly matches the ground truth. This ensures that our evaluation strictly reflects the capability provide precise answers rather than partially correct responses. The results are averaged over three seeds and reported as mean + 95% confidence interval.
Compared Methods. We compare PARoG with 17 LLM-based approaches from 3 categories: (1) LLM prompting methods, (2) LLM reasoning over KGs (LLM @ KG), (3) end-to-end fine-tuned KG-augmented LLMs, and (4) graph-retrieval methods. The details of the compared approaches are described in Appendix F

---

Published as a conference paper at ICLR 2026
Table 1: Performance comparison of different methods KGQA benchmarks.
Methods
WebQSP
CWQ
LLM Prompting
10
Brown et al. 2020
63.3
37.6
Co1 (Wei et al.
2022
62.2
38,8
SC
Wang et al.
2023c
61.1
45.4
Gruph-Retrieval Methods
GNN-Rag (Mavromatis Karypis
2025
82.8
62.8
SubgraphRag + GPT40 (T. al.
2025)
87.1
54.9
L.M @ KG with GPT-3.5
ToG
2024)
76.2
57.1
RoG
Luuo et al.
2024
81.5
52.6
KG-Agent (Jang ct al
2025)
79.2
56.1
StructGPT (jang
2023a
75.2
55.2
PoG (Chen al. (024b)
82.0
63.2
ReKnows Wang al.
2025)
81.1
58.5
PARoG
89.0 1.3)
73.1 0.9)
LLM @ KG with GPT-4
ToG (Sun al.
2024
80.7
65.4
KG-Agent Jiang
2025)
81.2
67.0
StructGPT (iane
2023a
79.5
64.7
PoG (Chen et al. 2024b
87.3
75.0
ReKnowS Wang al.
2025
83.8
66.8
PARoG
91.2 (1 0.9)
79.3 (1: 1.1)
Implementations. For SPARQL-Guided Supervision, use the training split of WebQSP, GrailQA, and CWQ as the source and employ GPT-4 to generate the training data, and the statistics summarized in Appendix E We use Llama-3.1-88 with learning rate 2e-5 on 4 Nvidia A800 GPUs. We use GPT-3.5 or GPT-4 to serve as the underly- ing LLMs and report the results both, thereby analyzing our method across diverse settings.
the backbone to train the planning module
4.1 PERFORMANCE COMPARISON
Main Results. The comparison results WebQSP and CWQ in Table 2 Across both benchmarks, our propose method PARoG consistently outperforms existing approaches. Compared with the state-of-the-art baseline Planning-on-Gri Graphhhh (PoG), PARoG gains sub- stantial improvements of 3.9 and 4.3 points WebQSP and CWQ respectively with GPT-4. Under the more challenging setting with GPT- 3.5, more significant improvements can be ob- served: PARoG surpasses the baseline by 7.3 on WebQSP and 10.1 on CWQ. It is worth not- ing that the improvements are particularly pro- nounced on CWQ, which contains more com- plex multi-hop and compositional queries, un- derscoring the advantage of our structured plan- ning and self-refinement mechanism. On the GrailQA benchmark (Table 2
IN PARoS (Ours)
05.1
41.
Compositions
Conjanctions
Comparatives
Superlatives
Linear Quries
Figure 4: Performance comparison over different query types.
PARoG also achieves
consistent state-of-the-art performance across all evaluation settings. Using GPT-3.5, PARoG reaches an overall accuracy of 82.7, surpassing the state-of-the-an large margin of 4.9 points. Under the stronger GPT4 setting, method further improves to overall 87.2 points, exceeding the compared methods by 2.5 points. It can be observed that the im- provements of PARoG particularly significant compositional and zero-shot queries, demon-
-nbate- (DoG) by a

---

Published as a conference paper at ICLR 2026
Table 2: Performance comparison of different methods GrailQA.
Method
Overall
LLD.
Compositional
Zero-shot
LLM Prompting
10 Prompt (Brown 2020
29.4
CoT (Wei al 2022)
28.1
Cols-Consistency
Wang et al
2023c
29.6
End-to-Enu End Fine-Tuned KG-Augmented LLMSs
RnG-KBQA ct al.
2022
68.8
86.2
63.8
63.0
TIARA (Shu ct al. 2022
73.0
87.8
69.2
68.0
FC-KBQA (Zhang all
2023
73.2
88.5
70.0
67.6
Pangu (Gu ei al. 2023
75.4
84.4
74.6
71.6
FlexKBQA el al. (2024))
62.8
71.3
59.1
60.6
GAIN (Shu & Yu 2024)
76.3
88.5
73.7
71.8
KG-Agent (Jiang ct al.
2025
86.1
92.0
80.0
86.3
LLM @ KG with GPT-3.5
KBBBINDER (Li al.
2023a
53.2
72.5
51.8
45.0
ToG
Sun et al.
2024)
68.7
70.1
56.1
72.7
PoG
C Chen
2024b
76.5
76.3
62.1
81.7
DoG
Ma et
2025
77.8
PARoG
82.7 (+: 1.5)
85.4 (= 0.9)
66.7 (+ 2.0)
87.1 (+ 2.2)
I.LM @ KG with GPT-4
ToG
Sun et al
2024)
81.4 84.7
79.4
67.3
86.5
PoG
Chen et a.
2024b
87.9
69.7
88.6
DoG Ma
2025
80.0
PARoG
87.1 (# 1.3)
89.5 (= 2.1)
73.2 (1 1.9)
91.1 (.L 2.3)
strating robustness in both complex reasoning and nut-of-distribution scenarios. These results high- light that PARoG not only advances the overall accuracy but also generalizes better to complex and zero-shot queries, demonstrating the effectiveness of the proposed methodology.
Analysis on Different Query Types. We summarize the comparison between our method PARoG and PoG different query types in Figure Overall, method PARoG consistently outperforms PoG across all types. Compared with simple categories such as Linear Queries and Compositions, the gains become substantially larger on structurally more complex queries. In particular, PARoG achieves significant improvements of 12.7% on Comparatives, 14.4% on Conjunctions, and 20.5 % on Superlatives. These results highlight that PARoG especially effective in handling queries with multi-step reasoning and complex logical structures.
4.2 GENERALIZATION STUDY
To analyze the robustness across different schema organizations, evaluate PARoG CWQ and WebQSP with different source KGs (Freebase and WikiData), as shown in Table 3 Notably, the Wikidata is lower than that Freebase
Table 3: Generalization Study: performance of PARoG using different source KGs on We- bQSP and CWQ.
absolute performance because the datasets are originally annotated for Freebase. More- over, Wikidata is substantially larger and more heterogeneous, which increases the difficulty for KG exploration and relation fil- tering. PARoG consistently produces substantial improvements over compared approaches under the WikiData setting. The re- sults demonstrate that the proposed SPARQL-Guided Structured Planning and Sonn-Answer-Rfii are not tied to specific relations but generalize well under different schema organizations, relation granularities, and naming conventions. The improvements pecially pronounced on CWQ. where the queries are relatively more complicated.
Method WebQSP
CWQ
with Freebase
ToG PoG PARoG
76.2
57.1
82.0
63.2
89.3
73.3
with WikiData
ToG
68.6
54.9
PaG
73.8
60.7
PARoG
79.1
69.5
8

---

Published as a conference paper at ICLR 2026
4.3 ABLATION STUDY
We conduct ablation studies to examine the contributions of the two core components in our frame- work SPARQL Quidded Structured Planning and the Plan-Answer-Refine paradigm. The results are shown in Table 5 and 4 First, remove self-refinement consistently reduces performance across all datasets and settings. can be observed the decline in performance when using GPT-3.5. This result demonstrates the Answer-Refine paradigm effecctively mitigates error amplification, especially par- ticularly in scenarios where the underlying L.M is relatively weak. Second, compare our SPARQL- supervised planning module (trained with Llama-3. 3-BB)B) using much larger LLMs directly plan- ners. Despite having few parameters (8B), our model consistently outperforms GPT-3.5 (~20B) and DeepSeek-RI (671B) by large margins (up 8.1 points on complex CWQ). This result demon- strates that SPARQL-guided supervision provides strong compositional reasoning signals, enabling smaller models surpass much larger LLMs on reasoning path planning. These ablations prove that both self-refinement and SPARQL-supervised planning are essential to the effectiveness and efficiency of our framework.
To better understand the behavioral contribution of the Pene-Answer-Rfiinn component, we further ex- amine its ability to correct initially incorrect predic- tions. Specifically, for each dataset, we isolate ex- amples where the tentative answer produced by the vanilla LLM incorrect, and compute the proportion of these errors that are successfully fixed after refine- ment. As shown in Table 6 PARoG corrects around 70% of the initial wrong answers and the correction rate is particularly high on GrailQA, which is con- sistent with its greater logical compositionality and schema diversity. This result highlights the effective- ness of the mewneeerefnemeett paradigm. The correctness rate of the initial answers is listed in Appendix G
Table 4: Refinement (SR).
Ablation Study; w/ or w/o Self-
Method WebQSP GrailQA
CWQ
GPT-3.5
w/o SR w/ SR
88.0
78.9
69.2 73.3
89.3
82.7
GPT-4
w/o SR w/ SR
89.7
85.5 87.2
77.2
91.2
79.3
4.4 EFFICIENCY ANALYSIS
We further analyze the efficiency of dif- ferent methods in terms of LLM calls and token usage, as shown in Table 7 Our method consistently achieves not only higher accuracy but also greater ficiency across all datasets. These re- sults demonstrate that PARoG not only advances the SOTA performance but also significantly reduces computational overhead, making it more efficient and cost-effective for real- world application.
Ablation Study: Comparison our SPARQL- supervised planing module to LLMs.
Table 5:
Method
# Para
WebQSP
GrailQA
CWQ
Ours
8B
89.3
82.7
73.3
GPT-3.5 Deepseek-R1
20B
83.2
76.9
65.2
671B
88.5
80.2
68.7
4.5
CASE STUDY
We also provide case studies to discuss the effectiveness and limitations of PARoG in Appendix J
5 RELATED WORK
LLMs with Knowledge Graphs. Large Language Models (LLMs) have shown remarkable reason- ing capabilities (Brown et al. 2020 Wei et al.) 2022 Zhou et al. (023) but often prone to hallu- cinate when answering Knowledge-intensive queries Ji et al. 2023). To address this, combining LLMs reasoning with external knowledge graphs (KGs) have been introduced (Logan et al. 2019 Luo
Table 6: Error correction rate (CR Rate) of the Plan-Answer-Refine paradigm.
Dataset
WebQSP
CWQ
GrailQA
Rate
73.4
62.4
77.1
et al. 2023 Jiang al. 2023b
Pan et al. 2024 Approaches such KG-based representation

---

Published as a conference paper at ICLR 2026
Table 7: Efficiency Analysis: Performance token cost across different methods and datasets.
Dataset
Method
LLM Call
Input Token
Output Token
Total Token
Hits 1
ToG
15.9
6,031.2
987.7
7,018,9
76.2
WebQSP
PoG
9.0
5,234,8
282.9
5,517.7
82.0
PARoG
8.3
5,012.3
241,4
5,253,8
89.3
ToG
22.6
8,182.9
1,486,4
9,669,4
57.1
CWQ
PoG
13.3
7,803.0
353.2
8,156.2
63.2
PARoG
10.2
7,110.7
288.5
7,398.8
73.3
ToG
11.1
4,066.0
774.6
4,840.6
68.7
GrailQA
PoG
6.5
3,372.8
202.8
3,575.6
76.5
PARoG
6.0
3,180.9
178.1
3,358.2
82.7
learning (uu et al. 2020
Dehghan et al. 2024), knowledge-based instruction- Chen et al. [2024a] Luo et al. 2024), retrieval-augmmenter generation 2024; Wen et al. 2024, Zhang et al. [2024, Wang et al., 2023b), graph- constrained generation (Guan al.) 2024 Luo et al. 2022). ) and semantic parsing KGs (Ye et al.,
Li et al.,
2023b
tuning (Zhng al.
2023
with KG facts Wang et al.
2022
Yu et al.
2022) demonstrate the henefit of grounding LLM outputs in structured knowledge.
Interactive LLM Reasoning over Knowledge Graphs. Inspired by strong capability of deep rea- soning on structured data (Jiang et al., [023a Edge et al., (0024) Jin et al., 2024), recent methods introduce explicit reasoning paths guide LLM interactively inference over KGs and have achieved
significant improvements (Yao et al.
2023 Li Liet at. 2024a Mavromatis & Karypis 2024 Sun et al.)
2024 Tan et al., 2025 Chen al. 2024b). Think-on-Grap (Sun al.] 2024 treats reasoning
as agent-based exploration where LLMs iteratively search paths with traceability and correction. Generate-on-Grn Graph (Xu et al.] 2024) extends incomplete KGs by enabling LLMs to generate missing triples. Plan-on-graph (Chen et al. (024b) applies adaptive planning by decomposing ques- tions into sub-goals and refining paths via guidance and reflection. KG-Agent (Jiang et al. (025) formalizes multi-hop reasoning as program execution with tool use, KG execution, and memory updates. Sabate-o--Graph (Ma et al. al, (025) models reasoning as a multi-agent debate, where agents generate, and critique reasoning paths to enhance reliability. ReKnoS (Wang et al. 2025) introduces super-relations to connect relational paths, enabling bidirectional reasoning and improving retrieval efficiency. There also more recent efforts such (Shen et al. (025) and (Zhu al.) 2025) introducing alignment and reflection-be -based strategies to regulate LLM reasoning over KGs.
Our work also belongs to this line of work but differs from prior methods by introducing SPARQL- guided structured planning and answer-refine mechanism. Compared with existing work, the pro- posed method enables reasoning over complex logical operations beyond linear paths, and explicitly mitigate the inconsistency between the parametric knowledge of LLM and external KG evidence.
DISCUSSION AND CONCLUSION
In this paper, we present Hhan-AAnswer-RRfinoo-----rre (PARoG) a novel framework for LLM rea- soning over knowledge graphs. PARoG introduces two innovations SPARQL-guide structured planning and the Refine-Re paradigm, effectively mitigating search space truncation bias and error amplification issues. Extensive experiments on WebQSP, CWQ, and GrailQA demonstrate that PARoG achieves new state-of-the-art results while also being more efficient and cost-effective.
Limitation. Despite the improvements, PARoG still relies on the coverage and correctness of avail- able KGs. Besides, while SPARQI-guided training reduces dependence on large models, generating high-quality planning data still requires strong teacher models (c.g.. GPT-4o), which may limit ac- cessibility. Moreover, our refinement process is static and offline without dynamic feedback loops during reasoning, leave the exploration of online refinement for future work due to its complexity.
Broader Impact and Future Work. PARoG that structured symbolic guidance can enhance LLM reasoning, which be applied wherever external structured signals available beyond KGQA. In the future the study direct include dynamic refinement, multi multi--odal knowledge graphs, and boot- strapped improvetro,,, which could make PARoG more scalable, general and accessible.
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGMENTS
This research/project is supported by the National Natural Science Foundation of China (No. 62302437) and State Street Zhejiang University Technology Center. We would also like to thank reviewers for their valuable comments.
REFERENCES
Yejin Bang, Samuel Cahyawijaya, Nayeon Lee, Wenliang Dai. Dan Su, Bryan Wilie, Holy Lovenia, Ziwei Ji, Tiezheng Yu, Willy Chung, et al. A multitask, multilingual, multimodal evaluation of chatgpt reasoning, hallucination, and interactivity. arXiv preprint arXiv:3302.040233 2023.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 13:1877-1901, 2020.
Liyi Chen, Chuan Qin, Ying Sun, Xin Song, Tong Xu, Hengshu Zhu, and Hui Xiong. Collaboration- aware hybrid learning for knowledge development prediction. Proceedings of the ACM Web Conference 2024, pp. 3976-3985, 2024a.
Liyi Chen, Panrong Tong. Zhongming Jin, Ying Sun, Jieping Ye, and Hui Xiong. Plan-on-gran on-graph: Self-correcting adaptive planning of large language model on knowledge graphs. In Proceedings of the 38th Conference on Neural Information Processing Systems, 2024b.
Mohammad Dehghan, Mohammad Alomrani, Sunyam Bagga, David Alfonso-Hermelo, Khalil Bibi, Abbas Ghaddar, Yingxue Zhang, Xiaoguang Li, Jianye Hao, Qun Liu, et al. Ewek-qa: Enhanced web and efficient knowledge graph retrieval for citation-based question answering systems. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Vol- ume 1: Long Papers), pp. 11169-14187, 2024.
Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Amy Yang, Angela Fan, al. The llama 3 herd of models. arXiv e-prints, pp. arXiv-2407, 2024.
Darren Edge, Trinh, Newman Cheng, Joshua Bradley, Alex Chao, Apurva Mody, Steven Truitt, Dasha Metropolitansky, Robert Osazuwa Ness, and Jonathan Larson. From local to global: A graph rag approach to focuse summarization. arXiv preprint arXiv:2404.16136 2024.
Yu Gu, Sue Kase, Michelle Vanni, Brian Sadler, Percy Liang, Xifeng Yan, and Yu Su. Beyond IID: three levels of generalization for question answering on knowledge bases. In Proceedings of the Web Conference, pp. 3477-3488, 2021.
Yu Gu, Xiang Deng, and Yu Su. Don't generate, discriminate: A proposal for grounding language models to real-world environments. In The 61st Annual Meeting Of The Association For Compu- tational Linguistics, 2023.
Xinyan Guan, Yanjiang Liu, Hongyu Lin, Yaojie Lu, Ben He, Xianpei Han, and Le Sun. Miti- gating large language model ballucinations via autonomous knowledge graph-based retrofitting. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pp. 18126-16 18126-18134, 2024.
Daya Guo, Dejian Yang, Haowei Zhang, Junxiao Song, Ruoyu Zhang, Runxin Xu, Qihao Zhu, Shirong Ma, Peiyi Wang, Xiao Bi, et al. Deepseek-rl: Incentivizing reasoning capability in llms via reinforcement learning. arXiv preprint arXiv:2501. 12948, 2025.
Kelvin Guu, Kenton Lee, Zora Tung, Panupong Pasupat, and Mingwei Chang. Retrieval augmented language model pre-training. In International conference on machine learning, pp. 3929-3938. PMLR, 2020.
Xuming Hu, Junzhe Chen, Xiaochuan Li, Yufei Guo, Lijie Wen, Philip S Yu, and Zhijiang Guo. Do large language models know about facts? arXiv preprint 10.00 2023.
11

---

Published as a conference paper at ICLR 2026
Jie Huang and Kevin Chen-Chuar Chang. Towards reasoning in large language models: A survey. In Findings of the Association for Computational Linguistics: ACL 2023, pp. 1049-1065, 2023.
Jie Huang, Xinyun Chen, Swaroop Mishra, Huaixiu Steven Zheng. Adams Wei Yu, Xinying Song, and Denny Zhou. Large language models cannot self-correct reasoning yet. In The Twelfth International Conference Learning Representations, 2024.
Aaron Hurst, Adam Lerer, Adam Goucher, Adam Perelman, Aditya Ramesh, Aidan Clark, AJ Os- trow, Akila Welihinda, Alan Hayes, Alec Radford, et al. Gpt-4o system card. arXiv preprint arXiv:2410.21276 2024.
Ziwei Ji, Nayeon Lee, Rita Frieske, Tiezheng Yu, Dan Su, Yan Xu, Etsuko Ishii, Ye Jin Bang, Andrea Madotto, and Pascale Fung. Survey of hallucination in natural language generation. ACM computing surveys, 55(12)11-38, 2023.
Jinhao Jiang, Kun Zhou, KeMing Ye, Xin Zhao, Ji- Ji-Rong Wen, et al. Structgpt: A general framework for large language model to reason over structured data. In The 2023 Conference on Empirical Methods in Natural Language Processing, 2023a.
Jinhao Jiang, Kun Zhou, Xin Zhao, and Ji-Rong Wen. Unikgqa: Unified retrieval and reasoning for solving multi-ho hop question answering over knowledge graph. In The Eleventh International Conference on Learning Representations, 2023b.
Jinhao Jiang, Kun Zhou, Xin Zhao, Yang Song, Chen Zhu, Hengshu Zhu, and Ji-Rong Wen. KG-agent: An efficient autonomous agent framework for complex reasoning over knowledge graph. In Wanxiang Che, Joyce Nabende, Ekaterina Shutova, and Mohammad Taher Pilehvar (eds.), Proceedings of the 63rd Anmual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 9505-9523, Vienna, Austria, July 2025. Association for Com- putational Linguistics. ISBN 979-8-89176-251-4 doi: 10. (0.18653/v11 1 acl.225...l-oon..4e. URL 1687]
https:
Bowen Jin, Chulin Xie, Jiawei Zhang. Kashob Kumar Roy, Yu Zhang, Zheng Li, Ruirui Li, Xianfeng Tang, Suhang Wang, Yu Meng. et al. Graph bfain-of-thought Augmenting large language models by reasoning on graphs. In Findings of the Association for Computational Linguistics ACL 2024,
pp. 163 184, 2024.
Mufei Li, Siqi Miao, and Pan Li. Simple effective: The roles of graphs and large language mod- els in Conference on Learning Representations, 2025.
retrieval-augmented generation. In The Thirteenth International
Tianle Li, Xueguang Ma, Alex Zhuang, Yu Gu, Yu Su, and Wenhu Chen. Few-shot in-context learning on knowledge base question answering. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 6966-6980, 2023a.
Wendi Li, Wei Wei, Xiaoye Qu, Xian-Ling Mao, Ye Yuan, Wenfeng Xie, and Dangyang Chen. Trea: Tree-structure reasoning schema for conversational recommendation. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp- 2970-2982, 2023b.
Xingxuan Li, Ruochen Zhao, Yew Ken Chia, Bosheng Ding, Shafiq Joty, Soujanya Poria, and Li- dong Bing. adapting over heterogeneous sources. In The Twelfih International Conference on Learning Rep- resentations, 2024a.
Grounding large language models via dynamic knowledge
Zhenyu Li, Sunqi Fan, Yu Gu, Xiuxing Li, Zhichao Duan, Bowen Dong, Ning Liu, and Jiany- ong Wang. Flexkbqa: A flexible IIm-powered framework for few-shot knowledge base question answering. In Proceedings of the AAAI conference on artificial intelligence, volume 38, pp- 18608-18616, 2024b.
Robert Logan, Nelson F Liu, Matthew E Peters, Matt Gardner, and Sameer Singh. Barack's wife hillary: Using knowledge graphs for fact-aware language modeling. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pp. 5962-5971, 2019.
12

---

Published as a conference paper at ICLR 2026
Linhao Luo, Yuan-Fang Li, Gholamreza Haffari, and Shirui Pan. Reasoning graphs: Faithful and interpretable large language model reasoning. In The Twelfth International Conference on Learning Representations, 2024.
Linhao Luo, Zicheng Zhao, Gholamreza Haffari, Yuan-Fang Li, Chen Gong, and Shirui Pan. Graph- constrained reasoning: Faithful reasoning on knowledge graphs with large language models. In Forty-second International Conference on Machine Learning. 2025.
Ziyang Luo, Can Xu, Pu Zhao, Xiubo Geng, Chongyang Tao, Jing Ma, Qingwei Lin, and Daxin Jiang. Augmented large language models with parametric knowledge guiding. arXiv preprint 2055:22305.04777, 2023.
Jie Ma, Zhitao Gao, Qi Chai, Wangchun Sun, Pinghui Wang, Hongbin Pei, Jing Tao, Lingyun Song, Jun Liu, Chen Zhang, et al. Debate on graph: flexible and reliable reasoning framework for large language models. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 39, pp. -47766, 2025.
Costas Mavromatis and George Karypis. Gnn-rag: Graph neural retrieval for large language model reasoning. arXiv preprint arXiv:2405.20138 2024.
Costas Mavromatis and George Karypis. Gnn-rag: Graph neural retrieval for efficient large lan- guage model reasoning on knowledge graphs. In Findings of the Association for Computational Linguistics: ACL 2025, pp. 16682-16699, 16699, 2025.
OpenAl, Josh Achiam. Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Floren- cia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, Red Avila, Igor Babuschkin, Suchir Balaji, and al. Gpt-4 technical report, 2023.
Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. Training language models to fol- low instructions with human feedback. Advances in neural information processing systems, 35:
27744-27744, 2022.
Shirui Pan, Linhao Luo, Yufei Wang, Chen Chen, Jiapu Wang, and Xindong Wu. Unifying large language models and knowledge graphs: A roadmap. IEEE Transactions on Knowledge and Data Engineering, 36(7):3580-3599 2024.
Shuofei Qiao, Yixin Ou, Ningyu Zhang, Xiang Chen, Yunzhi Yao, Shumin Deng, Chuanqi Tan, Fei Huang, and Huajun Chen. Reasoning with language model prompting: A survey. In P Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 5368-5393, 2023.
Xiangqing Shen, Fanfan Wang, and Rui Xia. Reason-aliga-respond: Aligning Ilm reasoning with knowledge graphs for kgga. 2025.
Yiheng Shu and Zhiwei Yu. Distribution shifts are bottlenecks: Extensive evaluation for grounding language models to knowledge bases. Proceedings of the 18th Conference of the European Chapter of the Association for Computational Linguisties: Student Research Workshop, pp. 71- 88, 2024.
Yiheng Shu, Zhiwei Yu, Yuhan Li, Börje Karlsson, Tingting Ma, Yuzhong Qu, and Chin- Yew Lin. Tiara: Multi polti-grained retrieval for robust question answering over large knowledge base. In Pro- ceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pp- 2108-81211 2022.
Jiashuo Sun, Chengjin Xu, Lumingyuan Tang. Saizhuo Wang, Chen Lin, Yeyun Gong, Lionel Ni, Heung- Yeung Shum, and Jian Guo. Think-on-grann Deep and responsible reasoning of large language model on knowledge graph. The Twelfth International Conference on Learning Rep- resentations, 2024.
Alon Talmor and Jonathan Berant. The Web a knowledge- baase for answering complex questions. In Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume I (Long Papers), pp. 641-651, 2018.
13

---

Published as a conference paper at ICLR 2026
Xingyu Tan, Xiaoyang Wang. Qing Liu, Xiwei Xu, Xin Yuan, and Wenjie Zhang. Paths-over-gras graph: Knowledge graph empowered large language model reasoning. In Proceedings of the ACM on Web Conference 2025, pp. 3505-3522, 2025.
Jiapu Wang, Sun Kai, Linhao Luo, Wei Wei, Yongli Hu, Alan Wee-Chung Liew, Shirui Pan, and Baocai Yin. Large language models-guided dynamic adaptation for temporal knowledge graph reasoning, Advances in Neural Information Processing Systems, 37:8384 178838-8410, 2024.
Keheng Wang, Feiyu Duan, Sirui Wang, Peiguang Li, Yunsen Xian, Chuantao Yin, Wenge Rong, and Zhang Xiong. Knowledge-driven cot: Exploring faithful reasoning in Ilms for knowledge- intensive question answering. arXiv preprint arXiv:2308. 0eii23088.3229 13259, 2023a.
Song Wang. Junhong Lin, Xiaojie Guo, Julian Shun, Jundong Li, and Yada Zhu. Reasoning of large language models over knowledge graphs with super-relations. The Thirteenth International Conference on Learning Representations, 2025.
Xintao Wang, Qianwen Yang, Yongting Qiu, Jiaqing Liang, Qianyu He, Zhouhong Gu, Yanghua Xiao, and Wei Wang. Knowledgpt: Enhancing large language models with retrieval and storage access on knowledge bases. arXiv preprint arXiv:2308. 1761, 2023b.
Xuezhi Wang. Jason Wei, Dale Schuurmans, Quoe V Le. Ed H Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. Self-consistency improves chain of thought reasoning in language models. In The Eleventh International Conference on Learning Representations, 2023c.
Jason Wei, Xuezhi Wang, Dale Schuurmans. Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, et al. Chain-of-thouglee prompting elicits reasoning in large language models. Advances in neural information processing systems, 35:24824 24837, 2022.
Yilin Wen, Zifeng Wang, and Jimeng Sun. Mindmap: Knowledge graph prompting sparks graph of thoughts in large language models. In Proceedings the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 10370-10388, 2024.
Yao Xu, Shizhu He, Jiabei Chen, Zihao Wang. Yangqiu Song, Hanghang Tong, Guang Liu, Jun Zhao, and Kang Liu. Generate-on-grappe Treat Ilm as both agent and kg for incomplete knowl- edge graph question answering. In Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, pp. 18410-18430, 2024.
Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik Narasimhan, and Yuan Cao. React: Synergizing reasoning and acting in language models. In International Conference on Learning Representations (ICLR), 2023.
Xi Ye, Semih Yavuz, Kazuma Hashimoto, Yingbo Zhou, and Caiming Xiong. Rng-kbqa: Generation augmented iterative ranking for knowledge base question answering. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp- 6032-6043, 2022.
Wen-tau Yih, Matthew Richardson, Christopher Meek, Ming- Wei Chang, and Jina Suh. The value of semantic parse labeling for knowledge base question answering. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), pp- 201-206, 2016.
Donghan Yu. Sheng Zhang, Patrick Ng, Henghui Zhu, Alexander Hanbo Li, Jun Wang, Yiqun Hu, William Yang Wang, Zhiguo Wang, and Bing Xiang. Decaf: Joint decoding of answers and logical forms for question answering over knowledge bases. In The Eleventh International Conference on Learning Representations, 2022.
Lingxi Zhang, Jing Zhang, Yanling Wang, Shulin Cao, Xinmei Huang, Cuiping Li, Hong Chen, and Juanzi Li. Fc-kbqa: A fine-to-coarse composition framework for knowledge base question answering. In The 61 Annual Meeting The Association For Computational Linguistics, 2023.
Qinggang Zhang, Junnan Dong, Hao Chen, Daochen Zha, Zailiang Yu, and Xiao Huang. Knowgpt: Knowledge graph based prompting for large language models. Advances in Neural Information Processing Systems, 37:6052-600 6080, 2024.
14

---

Published as a conference paper at ICLR 2026
Wayne Xin Zhao, Kun Zhou, Junyi Li, Tianyi Tang, Xiaolei Wang, Yupeng Hou, Yinggian Min, Beichen Zhang, Junjie Zhang, Zican Dong, et al. A survey of large language models. arXiv preprint arXiv:2303.18223, 1(2), 2023.
Denny Zhou, Nathanael Schärli, Le Hou, Jason Wei, Nathan Scales, Xuezhi Wang, Dale Schuur- mans, Claire Cui, Olivier Bousquet, Quoc Le, et al. Least-to-most prompting enables complex reasoning in large language models. The Eleventh International Conference on Learning Rep- resentations, 2023.
Jiajun Zhu, Ye Liu, Meikai Bao, Kai Zhang, Yanghai Zhang, and Qi Liu. Self-reflective planning with knowledge graphs: Enhancing Ilm reasoning reliability for question answering. 2025.
15

---

Published as a conference paper at ICLR 2026
A THE USE OF LARGE LANGUAGE MODELS (LLMS)
We used OpenAl ChatGPT for writings refinement and correction of typos during the preparation of this manuscript.
B ERROR ANALYSIS OF EXISTING METHODS.
We conduct an error analysis of existing methods (ToG and PoG). Among the failed exam- ples:83.39% of WebQSP questions,85.00 85..34% of GrailQA questions, and 90.14% of CWQ queries fail due to missing answer entities in the retrieval phase. FigureB]showe the distribution of different query types of the failed examples.
Compositions
Conjunctions
Superlatives
Comparatives
10.17%
45, 12%
38.80%
Figure 5: Error Distribution of PoG.
C PROMPT TEMPLATES FOR MODEL TRAINING
We describe the training input template used in our framework follows:
Instruction: Decompose the following complex questien into logical sequence of simpler sub-questions
Input: Question: [The original complex question]
Response: 1. [First sub-question] 2. [Second sub-question] 3.
D ALGORITHM FOR THE PLAN-ANSWER-REETE PARADIGM
We summarize the comprehensive algorithmic procedure of Plan-Answer-Refine shown in Algo-
rithm [
E DETAILS OF DATASETS
WebQSP consists of 4,737 natural language questions that require single or multi-hop reasoning over Freebase. GrailQA presents a more challenging scenario with 64,331 questions designed to test compositional generalization capabilities. CWQ contains 34,689 complex questions requiring multi-hop reasoning and constraint handling. These datasets collectively provide robust testbed for evaluating various aspects of KGQA performance, including reasoning complexity, generalization ability, and scalability. The statistics of the datasets summarized in Table
16

---

Published as a conference paper at ICLR 2026
Algorithm PARoG.
Require: Question Q, Knowledge Graph 9, LLM M, Planning module PLAN(-), instruction tem- plates LA, LR. initial topic entity set Eg (size no), max iterations Z max
Ensure: Final answer
1: O + PLAN(Q)
Generate sub-objectives with the SPARQL planner
2: A
3: for each sub-objective O, O do
4:
á < M(Q, 0z, TA)
> Tentative answer by parametric reasoning Initialize reasoning paths
5:
Po [1]
6:
Eo + {ei...., noo
7:
for to T max do
8:
E111 t TAILENTITES(PL-.)
9:
R, NEIGHBORRELATIONNS( &(-1) R. M(Q, o,, O, R,R.stt
10:
b. Filter relations with global plan awareness
E goand t- SAARQLQUERY(C,CC R,,
12:
SCORE(e) + M(Q, os e), de E Eoand & f SELECTRELEVANT(C" (randd SCORE)
13:
Select a variable number of most relevant
entities
14:
Pe + EXTENDPATHS (P- Rd)
15:
0; < M(P,, 0s. d;. In)
Self-refine tentative answer
16:
if ALIGN Q) false then
a;
Fallback if retrieved knowledge is irrelevant
18:
end if
if SUFFICIENT(C,, Q) true then break end if end for
20:
22:
23:
A+ {a,
24: end for
25: a + AGGREGATE (A, O)
Combine refined sub-answers according to to form the final
answer.
26: return a
Table 8: Statistics of datasets.
Datasets
#Train
#Test
Max #hop
WebQSP
2,826
1,628
2
CWQ
27,639
3,531
4
GrailQA
44,337
13,231
4
F DETAILS OF COMPARED BASELINES
We compare PARoG with 17 LLM-based approaches from 3 categories: (1) LLM prompting meth- ods, (2) LLM reasoning KGs (LLM & KG), and (3) end-to-end fine-tuned KG-augmented LLMs. The details of the compared approaches are described as follows.
LLM PROMPTING
Input-Output Prompting (Brown et al.) 2020 A standard few-shot prompting approach without explicit reasoning guidance, serving as basic LLM QA baseline.
Thought prompting encourages the LLM to ex- plicitly generate intermediate reasoning steps, improving logical consistency on complex queries.
Shainn-f--Toughh (Wei et al. 2022): Chain-of- Chain-of-Thought
Holl-Consistency (Wang et al. 2023c): Self-consistency prompting samples multiple reasoning chains and aggregates their results, reducing random errors and improving answer stability.
17

---

Published as a conference paper at ICLR 2026
F.2 LLM & KGS
Think-on-Graph (Sun et al. 2024): Think-on-Grapp models reasoning as an agent-based explo-
ration, where the LLM iteratively traverses the knowledge graph to build interpretable paths.
Reasoning-on-Grappe (Luo al. 2024): Reason-on- Graph constrains LLM outputs faithful graph-grounded reasoning paths, improving interpretability and correctness of answers.
KG-Agent (Jiang et al.
An autonomous agent framework that formalizes multi-hop rea- soning as program execution with KG queries, external tool use, and memory updates.
2025):
StructGPT (Jiang et al.
2023a) : A structured generation framework where LLMs are guided by
schema-constrained prompts to produce reasoning paths over structured data.
Plan-on-Graph (Chen et al. 2024b): Plan-on-Graph decomposes complex queries into struc-
tured sub-goals and adaptively plans reasoning paths on the KG, enabling better compositional reasoning.
ReKnowS (Wang et al.
2025): ReKnowS introduces the concept of super-relations to connect
multiple relational paths, allowing bidirectional reasoning and improving retrieval efficiency.
KB-BINDER (Li al.
KB-BINDER bridges LLM reasoning with KG facts using binding mechanism that grounds parametric knowledge in structured evidence.
2023a):
Debate-on-Graph (Ma al. 2025): Debate-on-Ool models reasoning multi-agent debate, where different agents generate and critique reasoning paths to improve reliability.
F.3 END-TO-END TUNED KG-AUGMENTED LLMS
RuG-KBQA Yee et al. 2022 ceneration-augmenter KBQA model that iteratively ranks can-
didate answers, combining generative reasoning with retrieval.
TIARA (Shu al.
multi-grained retrieval framework designed to strengthen robustness of KBQA systems against noisy incomplete evidence.
2022): :
FC-KBQA (Zhang al. 2023 -one-te- composition framework that first retrieves broad candidates and then refines answers hierarchically for complex KBQA.
Pangu (Gu et al. 2023): An end-to-end KBQA model that emphasizes compositional general- ization, allowing it to handle more complex query structures.
FlexKBQA (Li et al., 2024b): ficxible, LLM--powrred KBQA framework designed for few- shot learning and adaptable to low-resource settings.
GAIN (Shu Yu 2024) KBQA method optimized for distribution shifts, making reasoning more robust across different domains and data splits.
F.4 GRAPH-RETRIEVAL METHOOSS
GNN-RAG (Mavromatis & Karypis 2025 ; A deep learning method uses graph neural networks
retrieve the most relevant nodes and subgraphs for LLM reasoming.
SubgraphRag (Li et al. 2025): method builds and retrieves localized subgraphs to provide structured graph context for LLMs.
G STATISTICAL ANALYSIS OF MAJOR COMPONENTS
We conduct analysis to measure the proportion of questions for which the search process prematurely prunes the correct path (reported truncation rate). The results follows.
Table 9: Truncation Rate.
Method Truncation Rate (%)
PoG
38.82
PARoG
19.48
18

---

Published as a conference paper at ICLR 2026
Table 10: Correctness rate of initial answers (%).
Dataset
WebQSP
CWQ
GrailQA
Correctness rate of initial answers (%)
61.7
28.9
43.4
Moreover, to better understand how often the tentative answers produced by the LLM are incorrect, we list the correctness rate (%) in the initial answers generated by LLM as shown in Table TO
These numbers verify that LLM parametric knowledge is often incomplete or unreliable, highlight- ing the necessity of a refinement stage grounded KG execution.
H STABILITY AND SENSITIVITY ANALYSIS
To analyze the stability of the proposed method, we run the experiments under three seeds and report the mean + 95% CI for different settings. The results are shown in Table 11] 12 and T3
Table 11: Stability Analysis on main datasets.
Method
WebQSP
GrailQA
CWQ
GPT-3.5
ToG
76.4 1.9
68.9 1.5
57.2 + 1.8
PoG
82.1 + 2.2
76.5 2.1
63.2 + 1.2
PARoG
89.0 + 1.3
82.7 + 1.5
73.1 + 0.9
GPT-4
ToG
80.7 +: 1.7
80.9 1.4
65.6 1 2.2
PoG
87.3 1: 1.5
84.3 1 1.8
75.0 1 1.4
PARoG
91.2
87.1 + 1.3
79.3 1.1
Table 12: Stability analysis on w/ or w/o Self-Refinement (SR).
Method
WebQSP
GrailQA
CWQ
GPT-3.5
w/o SR
88.0 + 1.6
78.9 1.4
69,2 + 1.2
w/ SR
89.0 + 1.3
82.7 1.5
73.1 + 0.9
GPT-4
w/o
89.7 + 1.1
85.5 1.4
+
w/ SR
91.2 + 0.9
87.1 + 1.3
79.3 + 1.1
Notably, PARoG shows higher accuracy and consistently smaller confidence intervals than all base- lines. Moreover, the smaller planner outperforms larger general LLMs. Even the smallest IB planner still achieves comparable performance compared to Deepseek-Re RL, confirming that SPARQL-guidee training provides a stronger planning signal than scaling model size alone. These results prove the stability and reproducibility of the SPARQL-guider planner and the Answer-Refine mechanism.
1 EFFICIENCY TRADE-OFFS.
To better characterize the efficiency accurrac trade-off, we conducted an additional study varying the maximum planning iterations in PARoG as shown in Figure Unlike existing methods, PARoG does not use a fixed beam width. Instead, it maintains a dynamic beam, while the overall search budget is controlled by the maximum number of planning iterations.
19

---

Published as a conference paper at ICLR 2026
Table 13:
Stability and Sensitivity analysis different planners.
Method
# Para
WebQSP
GrailQA
CWQ
General LLMs
GPT-3.5
20B
1.4
76.7
Deepseek- R1
671B
88.2 + 1.5
80.2 1.3
68.7 = 1.1
Ours
11ama31-SB
8B
89.0 + 1.3
82.7 1.5
73.3 + 0.9
11mm1322-1B
87.2 + 1.2
79.1
1.6
68.5 +
1lama2-13B
13B
88.4 + 1.4
81.9 + 1.2
70.3 + 1.0
00
Accurucy
LLI Calls
83
80
Iteration
Iteration
(a) Accuracy vs. Iteration
(b) LLM Calls vs, Iteration
Figure 6: Efficiency Trade-offs.
CASE STUDY
To better understand the reasoning improvements brought by our proposed method, we analyze two representative failure cases from the baseline method Planning-on Coauiing-o--rrahh (PoG) and contrast them with the corresponding inference paths of our model (PARoG), shown in Table [4
J.1 CASE 1: COMPOSITION PLAN ERROR
This example investigates the question:
What is considered modern in the country where Bilady, Bilady, Bilady language is the national anthem?
The question requires two-hop reasoning process: (1) identify the country given the national an- them, and (2) determine the language that considered "modern" in that country. The baseline PoG fails in the planning stage by misinterpreting the intent of "modern" as referring to the country itself rather than a language. As a result, outputs "Egypt" as the final answer, which incomplete and incorrect.
In contrast, PARoG correctly preserves the linguistic intent the original question during the plan- ning phase. Unlike PoG, which misinterprets "modern" referring modern country, PARoG correctly interprets as referring to a modern language spoken the identified country.
It first identifies Egypt the country where "Bilady, Bilady, Bilady" is the national anthem same as PoG but goes step further by reasoning that Modern Standard Arabic the relevant modern language spoken in Egypt. This is captured in the following reasoning path:
Egypt + languages spoken - Modern Standard Arabic
By grounding the abstract query term "modern" into specific linguistic attribute, PARoG success- fully answers the question with Modern Standard Arabic, demonstrating its ability to disambiguate vague terms and construct semantically aligned plans that lead to correct, complete answers.
This case highlights the strength of the Plan-Answer- Hon--nnwwr-Reieee framework in maintaining semantic consistency and avoiding reasoning drift during multi-hop KGQA.
20

---

Published as a conference paper at ICLR 2026
Table 14: Examples of reasoning conducted by PARoG. Red denotes incorrect reasoning paths and answers, while green denotes correct ones.
Case I:
Composition plan error
Question
What is considered modern the country where Bilady, Bilady, Bilady language is the
national anthem?
Answer
Modern Standard Arabic
# Plan: [Identify the country where "Bilady, Bilady, Bilady" is the national anthem, Re- search the definition of "modern" in the context of countries]
# Reasoning Path: m.0478lbx + government. natiotaaaoiiiiinnanaaaaan wttpeeeemooaaa..oooota co.a.ouutry..anteen - Bi- lady, Bilady, Bilady
PoG
m404788bx + govermment national anthem a country.coonntry + Egypt
# Answer:
Egypt
# Plan: [Identify the country where "Bilady, Bilady, Bilady" is the national anthem, Re- search modern cultural, social, or technological aspects in that country]
# Reasoning Path: m. m.0478lbx government national anthem of country.anthem - Bi- lady, Bilady, Bilady
PARoG
m.0478Ibx + government. national.anthemmmmmm www.hantthhhataa htt.:/ofaa.coutt..oouuuum + Egypt
Egypt -
location. location.country. www.try..anggggeessoooooooo
- Modern Standard Arabic
# Answer: Modern Standard Arabic
Case 2: Parametric Knowledge Bridging KG Gaps
Question
What movies did Adam Sandler play in and is about Christmas?
Answer
Eight Crazy Nights
# Reasoning Path: Adam Sandler - flm.actor.fille (Eight Crazy Nights, Song, Reign Over Me, Funny People, The Meyerowitz Stories, The Week Of]
The The Chanukah
PoG
# Answer: The Chanukah Song
# Reasoning Path: Adam Sandler + Reign Over Me, etc.)
film - (Eight Crazy Nights, Funny People,
PARoG
LLM angwers:Eight Crazy Nights about Christmas
# Answer: Eight Crazy Nights
J.2 CASE 2: PARAMETRIC KNOWLEDGE BRIDGING KG GAPS
We also examine the following question:
What movies did Adam Sandler play in and is about Christmas?
The PoG baseline retrieves several films involving Adam Sandler-such as The Chanukah Song, Reign Over Mc. and Funny People-but it fails to search whether these movies are related to Christ- mas, ultimately yielding the incorrect result The Chanukah Song. contrast, PARoG follows similar retrieval process and also identifies several films involving Adam Sandler through its agent module. However, despite failing to retrieve any explicit evidence from the knowledge graph re- garding the "Christmas" constraint, PARoG demonstrates a more robust and semantically grounded refinement process. By leveraging the parametric knowledge encoded within LLM, it success- fully infers that Eight Crazy Nights is saristtma-themmer film. This case illustrates the strength of the plan-answe -er--nswwr-reiiee paradigm in producing correct answers even when symbolic evidence from the KG is absent, showcasing the complementary power of LLM-based reasoning.
K FAILURE CASE ANALYSIS
Table 15 presents representative failure cases of PARoG and highlights the underlying across three major error categories. Case I illustrates a relation selection eтror, where the planner or ex- ploration stage selects relation chain which is semantically plausible but ultimately incorrect(e.g..
relation-selection
21

---

Published as a conference paper at ICLR 2026
Table 15: Failure cases of PARoG and corresponding emror causes.
Case 1: Relation selection eπror
Question
What movie did Ron Howard do with cinematography by Mark Irwin?
Ground truth
Osmosis Jones
# PARoG Reasoning Path: Mark Irwin film win.ematoograpphr..iiin -
Ron Howard" +
by Apollo 13
Answer:Scream
# Ground truth path: Ron Howard + fllm.actor.film m.03g24
error cause
m.03g24 + ilm.performance.ene film - Osmosis Jones
Osmosis Jones film.fil wtlm.fll..iinmmatte www....ciiimmttgraphyyy - Mark Irwin
# Cause:
Incorrect relation selection (choosing fin.film.direee by and film.cinematograaher.iii
instead of the actor-performance relations) diverts explo- ration to irrelevant paths, thereby missing the gold answer.
Case 2: Incomplete multi-answer retrieval (partial answer set)
Question
who plays blaine in batman
Ground truth
Matthew Wagner,Danny Trejo,Carlos Alazraqui, Tom Hardy
# PARoG reasoning path (only one branch retrieved):
# Film path retrieved:
Blaine + fllmfilm character. portracee.portaayed.e in films +
film. him.performaanee.actt - Tom Hardy, Carlos Alazraqui, Matthew Wagner Missing actor from the TV branch: Danny Trejo.
# Ground truth path (union of two branches):
# Film path:
error cause
Blaine + film.film character.portrayeer in films -+
film. roo..erformmacc.cctoor -> Tom Hardy, Carlos Alazraqui, Matthew Wagner # TV path:
Blaine + tw.tv www..ccharacterrappaareddiii program +
- Danny Trejo
The ground-truth answer set is formed by the union of film path and TV path, but PARoG identifies only one branch (film) and overlooks the program branch, resulting in an incomplete multi-answer retrieval.
# Cause:
Case 3: Path absence due KG incompleteness.
Question
What countries in Oceania, that have the emissions per capita in dated metric ton of 0.091351?
Ground truth
Papua New Guinea
PARoG Reasoning: Cook Islands is country in Oceania that has emissions per capita of 0.091351 metric tons
Path absence due KG incompleteness. The KG does not contain valid relational path that instantiates the numeric condition 0.091351 (i.c., this value is missing/not represented). PARoG cannot retrieve the exact matching entity and is forced Use the LLM internal Knowledge.
cause
directed by instead of actor eitor-perffrmance relations), diverting the search away from the gold path. Case shows an instance of incomplete multi-branch retrieval, where the system successfully re- covers the film-related path but misses an additional TV-series branch required to produce the full multi-answer set. This demonstrates that although PARoG effectively handles compositional con- straints, multi-source answer aggregation remains challenging when evidence spans heterogeneous subgraphs. Case 3 shows failure case caused by KG incompleteness: when numerical attributes or relational paths needed to instantiate a constraint are absent from the underlying KG, PARoG unable retrieve the gold entity and must instead rely on parametric knowledge, often leading
22

---

Published as a conference paper at ICLR 2026
to incorrect final predictions. Overall, these cases reveal that remaining errors primarily stem from (i) subtle relation disambiguation, (ii) multi-branch retrieval coverage, and (ii)) missing or incom- plete KG facts- provi--ro actionable directions for future improvements such stronger relation grounding, expanded query branching, and KG-aware confidence estimation.
L SEARCH SPARQL
define several SPARQL queries for Freebase queries, which can be executed to search the relation and entity in the Knowledge graph
PREFIX ns: <http:/ /rrff wwweeaase.ccm//ne SELECT ?relation WHERE { ns:mid Prelation ?x
PREFIX ns: <http://rdi http:://ddf..//
SELECT Prelation
WHERE {
?x ?relation ns:mid.
L.1 ENTITY SEARCH
PREFIX ns: </rtp://rdf.. http:://rdd..feebbee...mmm crrebbase.com/nste SELECT PtailEntity
WHERE ns:mid ns:relation ?tailEntity
PREFIX ns: <http://rdf... www.:ef..eceeeceeeeeeea.o.aaee SELECT itailEntity
WHERE {
?tailEntity ns:mid ns:relation
L.2 ENTITY NAME
PREFIX ns: <http://rdf.. httt::///dd..feebaaee.ooom
SELECT DISTINCT PtailEntity WHERE
Pentity es:type.object name ?tailEntity PIEEtt = ns:mid)
UNION
Pentity FILTER (?entity ns:mid)
?tailEntity
M PROMPT TEMPLATES FOR LLM AGENTS
We introduce the full prompting strategy used in our framework, which can be divided into two main stages:
23

---

Published as a conference paper at ICLR 2026
Data Generation Stage: Generating training data from SPARQL queries.
Agent Reasoning Stage: Guiding the LLM through the full Plan-Answer-Refne reasoning pro- cedure based on decomposed subgoals and retrieved knowledge.
M.1
DATA GENERATION STAGE:
For each input question, GPT--40 produces set of decomposed sub-questions that reflect the logical structure of the underlying SPARQL query.Here we display the prompt we use to generate the sub- question.
M.I.1 DATA GENERATE
Please break the process answering the question into few subobjectives as possible based on semantic analysis and sparqi
Now you need to directly output subebjectives of the following question in 1ist format like the example above. The output format should be subobjectivel, subobjective2,...
Q: \/Query\/
Sparql: (Sparql Query\)
Output:
M.2 AGENT REASONING STAGE:
We detail the complete prompt templates used in iterative reasoning framework, including swer initialization, relation/entity pruning, state updating, and self-refinement.
M.3 INIT ANSWERING
ased on your own knowledge, output the current known information required to achieve the subobjectives.
(texttt(In-Conter Few-shot)
Q: \Quuer\\
(ebbojeetties:\(111 of sub questicns\)
Now you need to directly output the results the fol following question in JSON format without other information or notes.
Output:
M.4 RELATION PRUNE
Please provide as few highly relevant relations possible question and its subobjectives from the following relations.
Itexttt (InetttIn--Cntex Few-shot
Q: \/Query\/
Subobjeetivee:\llie of sub questicns\)
ropic entity: M(Topic Entityl)
24

---

Published as a conference paper at ICLR 2026
Relations:
Mlist relations\)
output:
The LLM is instructed to directly select subset of candidate relations(No thresholds), we do not set fixed thresholds.and this discrete selection is used as the pruned relation set; we do not apply any additional numeric thresholds LLM scores.
M.5 ENTITY PRUNE
For each triple pattern (e.r,?) r, ?),,r,?), we construct a prompt of the form.
Which entities in the following 1ist (I) in Triples) can be used to answer question? Please provide the minimum possible number of entitics, and strictly adhering to the constraints mentioned in the question.
Now you need to directly output the entities from [] in Triplets for the following question in 1ist format without other information or
(texttt(In-Coneer) Few-shot)
Q: \(Quer\\)
Subobjectivess (llist of sub questicns\)
Relation:
M(Current Relation))
Entites:
M(lis of entities))
output:
The LLM is prompted to directly choose subset of the provided candidate entities that are most relevant for answering the question(no sresshold).similarly.wwe we do not set fixed threshold.
M.6 UPDATE THE KG REASONING STATE
Based on the provided information to revise the memory, if the memory has conflict with the provided information, use the provided information to revise the memory.If the provided information is not enough to revise the memory, keep the memory unchanged.
\texttt ( [In-Context Kew-shot]
Now you need to directly output the results the following question in JSON fornat without other information or notes.
Q: \QQuer\)
Memory: \(the status of the sub-questions
Knowledge triples: \/Explored Paths).)
output:
Q: MQQeer\)
knowledge triples: MExplored Paths\)
Output:
25

---

Published as a conference paper at ICLR 2026
M.7 REFINE
Given the question and the associated retrieved knowledge graph tripies entity, relation, entity), you are asked to self-refine the initial answers based on them. if the initial answers have conflict with the provided information, use the provided information refine them.If the provided information is not enough to refine the answers, keep the answers unchanged.
(cxxtt((I--Conee Few-shot
Q: \Quuer\)
Knowledge triples: \Explored Paths\)
Inital answers:) (he inital answers generated by the 1im)
Output:
M.8 ANSWER
PARoG runs iterative plan-answal auswer-reefine loop with two complementary stopping conditions. First, we cap the planning horizon by a fixed maximum number of iterations. Second, at each iteration call a final-answer head that takes the original question, the currently explored KG paths, and the refined result of resolved sub-questions as input.
Please answer the question on based on the memory, related knowledge triplets and your knowLedge.
Now you need to directly output the results the following question in JSON format (must include "A" and "R") without other information notes.
(texttt (texttt(In-Cont (In-Centext Few-shot]
Q: \/Quer\\
Knowledge triples: \/Explored Paths}}
Memory:
(tthe status of the uub-questions:
Output:
The model is required output JSON object with keys "A" (final answer) and "R" (short ratio- nale). If the predicted answer field "A" non-empty and not an "unknown" placeholder, we accept it and terminate the whole process early, without further KG exploration. Otherwise, continue the next iteration until either satisfactory answer produced or the maximum iteration is reached, in which accumulated triples in the context.
fall back answering based on the LLM's parametric knowledge plus the
26


Reviews:
[{"review_id": "GXtbBPNmro", "reviewer": "Reviewer_M5aj", "summary": "The paper proposes **Plan-Answer-Refine-on-Graph (PARoG)**, a KG-augmented LLM framework designed to address two limitations of prior KGQA agents: **(i)** *search-space truncation bias* from linear, top-k-pruned walks and **(ii)** *error amplification* from over-reliance on retrieved but partially relevant entities. PARoG has two pillars. First, **SPARQL-guided structured planning**: the authors decompose SPARQL queries into sub-objectives (conjunction, composition, comparatives, superlatives) and train a relatively small planner (Llama-3.1-8B) via SFT to emit stepwise plans with uniform granularity. Second, a **Plan→Answer→Refine** loop: for each sub-objective, the model first proposes a tentative answer using parametric knowledge, then executes KG exploration and **self-refines** the answer against retrieved triples, explicitly checking alignment and stopping when sufficient. Experiments on **WebQSP, CWQ, and GrailQA** report SOTA Hits@1 with fewer LLM calls and tokens than ToG/PoG; ablations show (a) self-refinement materially helps and (b) the 8B SPARQL-supervised planner outperforms much larger planning LLMs (GPT-3.5, DeepSeek-R1).", "questions": "1. **Statistics & stability.** Please report **means ± 95% CI over ≥3 seeds** for all main tables and ablations; include sensitivity to planner size and decoding parameters. \n2. **SPARQL→plan pipeline.** How do you validate the GPT-4o decompositions for **semantic equivalence** to the original SPARQL, and what is the estimated error rate? Any manual spot-checks? \n3. **Execution-faithfulness checks.** During refinement, can you enforce **KG-execution constraints** (e.g., verifying that asserted triples exist; type constraints) and report the rate at which refinement overturns an initially wrong tentative answer? \n4. **Generality.** Do results transfer to **Wikidata** (different schema and aliasing) and to **KG+text** settings (e.g., Freebase+Wikipedia)? If not, what components would need adaptation?\n5. **Efficiency trade-offs.** Table 5 shows fewer calls and tokens; could you add **cost-accuracy curves** (vary beam/iterations) and detail caching/parallelization assumptions used for accounting? \n6. **Error analysis.** Appendix B indicates high failure due to missing answer entities in retrieval for prior methods; can you provide a comparable breakdown for PARoG and the fraction resolved by the refine stage?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* **Addresses core failure modes with targeted design.** SPARQL-guided planning avoids linear-path pruning; Answer→Refine reduces retrieval-induced error amplification. \n* **Solid, multi-benchmark gains with efficiency.** PARoG improves Hits@1 over ToG/PoG/KG-Agent on WebQSP, CWQ, and GrailQA, with fewer calls and tokens.  \n* **Decision-useful ablations.** Self-refinement helps markedly (esp. with GPT-3.5); the SPARQL-trained 8B planner outperforming larger LLMs is practically important. \n* **Clear problem decomposition.** The taxonomy of sub-query types (conjunction/composition/comparatives/superlatives) aligns well with KGQA structure.", "weaknesses": "1. **Statistical rigor.** Main results lack **CIs/multi-seed variance**; given RL-like exploration and LLM stochasticity, uncertainty reporting is important. \n2. **Planner data generation & potential biases.** The **SPARQL→plan** dataset (74,802 examples via GPT-4o) is central, but quality controls, inter-annotator checks, and error taxonomies are not reported; robustness to noisy/ambiguous SPARQL is unclear. \n3. **Faithfulness audits.** The refinement step relies on LLM judgments of alignment; the paper does not quantify hallucinated/irrelevant triples that slip through nor enforce execution-based correctness constraints during refinement. \n4. **Generality beyond Freebase.** No experiments on **Wikidata/DBpedia** or text-augmented regimes; claims of broad applicability would be stronger with heterogeneous KGs or KG incompleteness stress tests. \n5. **Missing engineering details.** Exact prompts, stopping criteria, and filtering thresholds for relation/entity selection are described at a high level; reproducibility would benefit from fuller protocol disclosure.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "5TOcDTv2dz", "reviewer": "Reviewer_XrmY", "summary": "This paper proposes a novel framework for LLM reasoning on knowledge graphs, termed plan-answer-refine-on-graph (PARoG). To be specific, the proposed method leverages SPARQL queries from KG data as references, decomposing them into structured step-by-step plans. Then, PARoG trains LLMs to construct such structured plans for retrieval on KGs. In addition, a plan-answer-refine paradigm is adopted by first answering each sub-query and then refining the predictions. Extensive experiments demonstrate the effectiveness of the proposed method.", "questions": "Please see in Section Weaknesses", "limitations": "", "rating": 4, "confidence": 5, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1.\tThis paper is well-organized and easy to follow.\n2.\tThis paper provides the source code to ensure the reproducibility of the proposed method.\n3.\tExtensive experiments show the effectiveness of the proposed method.", "weaknesses": "1.\tThe figures could be further refined to enhance readability. In particular, the font size in Figures 1 and Figure 2 may be quite small.\n2.\tThe paper may lack some baseline methods for comparison, such as GNN-RAG [1], SubgraphRAG [2].\n3.\tThe core idea may be similar to PoG, as both methods adopt a comparable pipeline for answer generation (i.e., plan–answer–refine). What is the key difference between the proposed method and PoG?\n4.\tAs stated in the exploration section, the KG exploration process in the proposed method appears similar to existing approaches. How does the proposed method address the associated challenges?\n\n[1] Mavromatis, Costas, and George Karypis. \"Gnn-rag: Graph neural retrieval for large language model reasoning.\" arXiv preprint arXiv:2405.20139 (2024).\n\n[2] Li, Mufei, Siqi Miao, and Pan Li. \"Simple is Effective: The Roles of Graphs and Large Language Models in Knowledge-Graph-Based Retrieval-Augmented Generation.\" The Thirteenth International Conference on Learning Representations.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "9FqH5iY2Mv", "reviewer": "Reviewer_HE4u", "summary": "This paper proposes PARoG (Plan-Answer-Refine-on-Graph), a framework designed to tackle two key challenges in the KGQA domain: error amplification and search space truncation bias. The approach relies on task decomposition to break complex questions into sub-objectives and leverages additional information sources to guide reasoning. Specifically, the authors use GPT-4 to annotate decompositions with SPARQL queries, and then fine-tune a dedicated model (the PRoG Planner) to perform this task automatically. For each sub-task, an LLM first generates an initial answer based on its parametric knowledge, which is then refined using evidence retrieved from the knowledge graph. Experiments on three widely used benchmarks—WebQSP, GrailQA, and CWQ—demonstrate that PARoG consistently outperforms strong baselines, achieving both higher accuracy and improved efficiency.", "questions": "See Weakness above. Additional questions:\n\n1. Could the authors provide statistics on the proportion of initial answers that are correct or at least partially contain the correct entity in the evaluated datasets?\n\n2. During the exploration stage, would it be possible to train a dedicated model to assist with relation/entity pruning, rather than relying solely on the LLM’s scoring? Would this lead to more accurate path selection?\n\n3. Beyond the planning stage, what specific models are used for initial answering, exploring and refinement? Are these also performed by the fine-tuned LLaMA-3.1, or by other models?\n\n4. In the ablation study (Table 4), the paper mentions replacing the planning module with different LLMs. Were the subsequent pruning stages (relation/entity selection) also replaced accordingly, or were they kept fixed? The experimental setup is not entirely clear.\n\n5. Regarding the error analysis in Appendix B, could the authors provide more details about the types of errors observed and how they impact the overall results?\n\n6. A very recent paper (Plan-on-Graph: Self-Correcting Adaptive Planning of Large Language Model on Knowledge Graphs, arXiv 2410.23875) also addresses similar challenges in KGQA by combining task decomposition with adaptive exploration and self-correction. How does your planner-based decomposition fundamentally differ from their task decomposition mechanism, and what unique advantages does it provide?", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "- The paper clearly identifies two key challenges in KGQA—error amplification and search space truncation bias—and proposes a framework that directly addresses both issues.\n\n- The experimental evaluation is comprehensive: the method is tested on three widely used datasets. And results show that the proposed approach outperforms all baselines, and additional efficiency analysis highlights its ability to improve both accuracy and resource usage.\n\n- The experimental findings are particularly interesting; for example, Table 4 shows that the SPARQL-supervised Llama-3.1-8B planner outperforms directly using GPT-3.5 or DeepSeek-R1 as the planner itself, suggesting that structured evaluation and execution can surpass direct generation—a concrete illustration of the idea that evaluation is easier than generation.", "weaknesses": "1. The approach heavily relies on annotation-based task decomposition. While decomposition alleviates the problem of search space explosion, it does not fundamentally resolve it—if a sub-task still corresponds to a large search space, pruning remains unavoidable. Thus, the method mitigates but does not eliminate the need for pruning.\n\n2. During the exploration stage, the framework still depends on LLMs to score and select which paths to follow, effectively using the LLM itself as the policy. However, the paper does not propose any specific optimization or learning strategy for this decision-making process, leaving open the possibility that important candidate paths might still be pruned prematurely.\n\n3. On the evaluated benchmarks, LLMs may possess sufficient parametric knowledge to provide useful initial answers, serving as an additional information source. However, in other datasets or domains where the LLM lacks such prior knowledge, initial answers are more likely to be incorrect, and the self-refinement strategy could then introduce additional noise rather than reducing errors.\n\n4. The writing lacks clarity. Many of the key ideas are only implicit, requiring readers to infer the underlying insights, while the strengths of the method and the reasons behind its strong empirical performance are not clearly articulated. In addition, Figure 1-I(b) appears to contain an inconsistency: the decomposition process described in the text does not align with the example shown. Furthermore, important experimental details are not clearly presented, such as which specific models were used in each stage of the pipeline.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "ZlhCIrIZka", "reviewer": "Reviewer_iDwB", "summary": "This paper introduces PARoG (Plan-Answer-Refine-on-Graph), a novel framework designed to enhance large language model (LLM) reasoning over knowledge graphs (KGs). The method addresses two main issues in prior KG-augmented LLM approaches: (1) Search space truncation bias, caused by linear reasoning paths that prune valid entities prematurely, and (2) Error amplification, where incorrect retrieved entities mislead downstream reasoning.\n\nTo mitigate these, PARoG combines SPARQL-guided structured planning and a plan–answer–refine paradigm: The planning stage uses SPARQL queries to supervise LLMs in decomposing questions into structured, compositional sub-queries (handling conjunctions, compositions, superlatives, and comparatives). The reasoning stage first produces tentative answers using LLM parametric knowledge, then refines them using KG evidence iteratively.\n\nExperiments on WebQSP, CWQ, and GrailQA show consistent state-of-the-art performance — e.g., +8–10% improvements over strong baselines such as PoG and ToG — while using smaller LLMs (Llama-3.1-8B). Ablation studies confirm that both SPARQL-guided planning and self-refinement contribute significantly to the gains.", "questions": "See weaknesses.", "limitations": "", "rating": 6, "confidence": 5, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "1. Clear identification of key bottlenecks — The paper convincingly motivates the two main issues (search space truncation and error amplification) with illustrative examples (Figure 1).\n2. Strong experimental results — The framework consistently outperforms prior SOTA baselines across three KGQA benchmarks, especially on complex or zero-shot queries (Table 2 and Figure 4).\n3. Efficiency — Despite higher accuracy, PARoG reduces token cost and LLM calls compared to ToG and PoG (Table 5), showing practical scalability.\n4. Good qualitative analyses — The case studies (Appendix E) effectively show how PARoG resolves reasoning drift and leverages LLM priors to fill KG gaps.", "weaknesses": "1. Dependence on high-quality SPARQL annotations – The approach assumes access to accurate SPARQL-grounded data. Generating and maintaining such data (using GPT-4o as a teacher) might limit reproducibility and scalability to low-resource settings.\n2. Limited analysis of generalization to unseen KGs or domains – Experiments are confined to Freebase-based benchmarks; performance on other KGs (e.g., Wikidata, DBpedia) is not explored.\n3. Clarity and presentation – While figures are helpful, the overall presentation could be streamlined; some sections (e.g., 3.2) are dense with notational details that obscure the main idea.\n4. Limited error analysis for failure cases – The error breakdown (Appendix B) is brief and mostly quantitative; a qualitative discussion of remaining failure patterns (e.g., conflicting KG facts) would be useful.\n5. Missed reference – More relevant recent works, such as [1][2], should be included and discussed for a better review.\n\n[1] Shen, Xiangqing, Fanfan Wang, and Rui Xia. \"Reason-Align-Respond: Aligning LLM Reasoning with Knowledge Graphs for KGQA.\" arXiv preprint arXiv:2505.20971 (2025).\n\n[2] Zhu, Jiajun, Ye Liu, Meikai Bao, Kai Zhang, Yanghai Zhang, and Qi Liu. \"Self-Reflective Planning with Knowledge Graphs: Enhancing LLM Reasoning Reliability for Question Answering.\" arXiv preprint arXiv:2505.19410 (2025).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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:

Decision: Accept (Poster)