Compositional Chain-of-Relations for Faithful Knowledge Graph Question Answering with Large Language Models

Chenhui Liu; Jianpeng Zhou; Jiahai Wang

cs.AIAug 24, 2026

Compositional Chain-of-Relations for Faithful Knowledge Graph Question Answering with Large Language Models

Authors: Chenhui Liu, Jianpeng Zhou, Jiahai Wang

Organizations: Sun Yat-sen University, Guangzhou 510006, China

Abstract

Knowledge graph question answering (KGQA) is a key task for evaluating KG-augmented Large Language Models (LLMs), and complex KGQA that requires multi-hop reasoning is especially challenging. Solving a complex query involves two coupled phases: candidate retrieval, which locates answer candidates over the KG, and constraint handling, which filters these candidates against the query constraints. Faithful reasoning requires grounding both phases in the KG. However, existing agent-based methods ground candidate retrieval through entity-centric exploration, while leaving constraint handling to the LLM's internal knowledge, which leads to two critical limitations. (1) Unreliable entity pruning: entity-centric exploration uses entities as search units and must prune them to a fixed-size subset at each hop. Because entity information in KGs is often incomplete and a fixed-size subset cannot retain all valid entities, such pruning inevitably drops valid entities and ultimately leads to wrong answers. (2) Ungrounded constraint handling: query constraints are resolved from the LLM's internal knowledge rather than the KG, leaving the final answers unverifiable and prone to hallucination. To address these limitations, this paper introduces a relation-centric exploration paradigm, which uses relations rather than entities as search units and thus avoids unreliable entity pruning. Built on this paradigm, this paper proposes Compositional Chain-of-Relations (CCoR), a simple and effective framework that grounds both phases in the KG with two relation chains: a main chain for candidate retrieval and a constraint chain that verifies query constraints through explicit KG exploration. Experiments on four KGQA benchmarks show that CCoR consistently improves accuracy, faithfulness, and efficiency over strong baselines, with more pronounced gains on complex queries.

Figures & tables

Fig. 1: Illustration of simple and complex KGQA queries and the two phases involved in solving complex queries. The simple query, “Who has won the Best Actor Oscar?”, is answerable via one-hop reasoning ( award.winner ). The complex query, “Which American directors have worked with actors who won the Best Actor Oscar?”, requires multi-hop reasoning and a constraint, and can be decomposed into two phases. Candidate retrieval applies award.winner

\rightarrow

work.with from the topic entities to retrieve candidate directors, while constraint handling applies nationality.of with constraint target “America” to filter these candidates into the final answers.

Fig. 2: Comparison between existing agent-based KGQA methods and CCoR on the complex query “Which American directors have worked with actors who won the Best Actor Oscar?”. (a) Agent-based methods suffer from two limitations: (i) they rely on unreliable entity pruning that frequently discards valid reasoning paths, and (ii) they handle constraints implicitly through the LLM’s parametric knowledge, making them prone to factual hallucinations. (b) CCoR grounds both candidate retrieval and constraint handling in KG-executable relation chains, thereby producing faithful answers.

Symbol	Description
$G=(E,R,T)$	Knowledge graph
$q$	Natural language question
$E_{topic}$	Topic entities in $q$
$E_{cand}$	Candidates from main-chain execution
$E_{con}$	Feasible set from constraint-chain execution
$E_{final}$	Final answer entity set

TABLE I: Notation Summary for CCoR

Fig. 3: Architecture of the CCoR framework, illustrated with the question “Which American directors have worked with actors who won the Best Actor Oscar?” Main-Chain Exploration constructs candidate answers via relation-centric search from topic entities. Constraint-Chain Exploration then explicitly executes the nationality constraint through KG queries to filter candidates. A two-layer fallback mechanism handles failures: Layer 1 falls back to Global Entity Filtering when constraint-chain exploration fails, and Layer 2 falls back to parametric generation when main-chain reasoning fails.

Dataset	Total	Depth			Constraints
Dataset	Total	1	2	$\geq$ 3	N	Y
WebQSP	1639	1033	595	6	1232	402
CWQ	3520	1363	1597	560	1254	2266
GrailQA	1000	769	222	9	26	974
QALD10	333	-	-	-	-	-

TABLE II: Dataset statistics by main-chain depth and constraint-chain count.

Tuning-based Methods
Method	WebQSP		CWQ		QALD10		GrailQA
Method	Hits@1	F1	Hits@1	F1	Hits@1	F1	Hits@1	F1
FC-KBQA	–	76.9	–	56.4	–	–	–	–
Pangu	–	79.6	–	–	–	–	–	81.7
Pangu (100-shot) w/o tuning	–	54.5	–	–	–	–	–	62.7
Pangu (10-shot) w/o tuning	–	45.9	–	–	–	–	–	56.3

TABLE III: Accuracy Evaluation. Results of baseline methods are taken from their original papers for comparison; “–” indicates that the corresponding result is not reported in the original paper.

GPT-4.1-mini
Method	WebQSP			CWQ
Method	F1	KGR	FF1	F1	KGR	FF1
IO-Prompt	47.7	0.0	0.0	32.1	0.0	0.0
CoT-Prompt	46.4	0.0	0.0	35.2	0.0	0.0
ToG †	57.5	56.5	32.5	41.2	30.3	12.5
PoG †	64.0	63.3	40.5	42.2	37.1	15.7

TABLE IV: Faithfulness Evaluation on Agent-based Methods. ( † : reproduced from official codebases).

Method	Complex Query (500)
Method	Hits@1	P	R	F1	KGR	FF1
GPT-4.1-mini
ToG †	50.8	50.3	48.6	48.8	24.2	11.8
PoG †	54.2	53.0	51.9	51.6	36.4	18.8
CCoR	68.4	61.6	67.3	62.3	61.9	38.6
GPT-5.4-mini

TABLE V: Results on CWQ Complex Query ( † : reproduced from official codebases).

Fig. 4: Distribution of LLM API calls per question for CCoR, ToG, and PoG on WebQSP, CWQ, and QALD10. CCoR consistently requires fewer calls than ToG and PoG.

Method	Predicted Answer	Reasoning Process	Calls	Hits@1	F1
CoT	University of Washington	Parametric recall only; identifies the university but does not distinguish specific sports teams.	1	0	0
ToG	University of Washington	Entity-centric exploration fails to reach the team-level granularity, falls back to parametric generation.	32	0	0
PoG	University of Washington	Entity-centric exploration with entity-level backtracking, but repeatedly revisits incorrect paths without resolving the fight-song constraint, falls back to parametric generation.	30	0	0
CCoR (ours)	Washington Huskies football	Main chain: Nate Robinson $\xrightarrow{\texttt{pro\_athlete.teams}}$ $e_{1}$ $\xrightarrow{\texttt{team\_roster.team}}$ 8 candidate teams. Constraint chain: $?$ team $\xrightarrow{\texttt{fight\_song}}$ Bow Down to Washington, filters candidates to {Washington Huskies football}.	6	1	1.00

TABLE VI: Case study on the question “What team with fight song Bow Down to Washington did Nate Robinson play for?” (Gold answer: {Washington Huskies football}).

Method	WebQSP	QALD10	CWQ
ToG †	11,591,404	3,075,735	62,348,816
PoG †	11,340,446	5,713,781	113,186,196
CCoR (ours)	12,202,046	2,493,586	59,172,341

TABLE VII: Total token consumption on GPT-4.1-mini ( † : reproduced from official codebases).

Depth	Cum. Ratio (%)	Hits@1	F1	KGR
2	84.1	47.8	43.7	50.3
3	96.0	62.8	50.6	63.0
4	100.0	67.0	57.8	69.1
5	100.0	64.7	53.9	68.2

TABLE VIII: Effect of reasoning depth on CWQ (GPT-4.1-mini).

	Hits@1	F1	KGR
CCoR	67.0	57.8	69.1
w/o Constraint Chain (CoR)	60.3	52.0	49.8
w/o Relation Backtrack	57.2	50.0	42.6
w/o Global Entity Filtering	48.2	42.8	29.8

TABLE IX: Ablation Study on CWQ using GPT-4.1-mini.

Explore similar work

Mar 20, 2026

RouterKGQA: Specialized--General Model Routing for Constraint-Aware Knowledge Graph Question Answering

Knowledge graph question answering (KGQA) is a promising approach for mitigating LLM hallucination by grounding reasoning in structured and verifiable knowledge graphs. Existing approaches fall into two paradigms: retrieval-based methods utilize small specialized models, which are efficient but often produce unreachable paths and miss implicit constraints, while agent-based methods utilize large general models, which achieve stronger structural grounding at substantially higher cost. We propose RouterKGQA, a framework for specialized--general model collaboration, in which a specialized model generates reasoning paths and a general model performs KG-guided repair only when needed, improving performance at minimal cost. We further equip the specialized with constraint-aware answer filtering, which reduces redundant answers. In addition, we design a more efficient general agent workflow, further lowering inference cost. Experimental results show that RouterKGQA outperforms the previous best by 3.57 points in F1 and 0.49 points in Hits@1 on average across benchmarks, while requiring only 1.15 average LLM calls per question. Codes and models are available at https://github.com/Oldcircle/RouterKGQA.

Bo Yuan, Hexuan Deng, Xuebo Liu +1

Institute of Computing and Intelligence, Harbin Institute of Technology, Shenzhen, China · Zhongguancun Academy, Beijing, China

Knowledge Graph Question Answering LLM Reasoning with Graphs LLM Routing

Ask PDF

Oct 6, 2026

Foresight-over-Graph: Reasoning Beyond Local Horizons for Knowledge Base Question Answering

Large language models (LLMs) have demonstrated strong capabilities in question answering, yet they still frequently suffer from hallucinations on knowledge-intensive tasks. Knowledge graphs (KGs) provide LLMs with structured, interpretable, and updatable factual grounding, making them a promising external knowledge source for reliable reasoning. However, existing LLM-guided graph reasoning methods typically rely on hop-wise greedy or beam-style pruning during evidence retrieval. Such local decision processes are inherently myopic: evidence that appears weak near the source may become crucial only after deeper graph context is explored, causing answer-critical branches to be discarded prematurely and making the reasoning chain difficult to recover. To address this limitation, we propose Foresight-over-Graph (FoG), a foresight-aware evidence retrieval framework for knowledge base question answering (KBQA). FoG iteratively constructs a question-relevant evidence subgraph and uses far-to-near feedback to guide path exploration, and maintains a compact memory subgraph to support continued exploration. Extensive experiments on widely used KBQA benchmarks demonstrate that FoG achieves state-of-the-art performance, with a particularly large improvement of 16.58% in Hit on CWQ, while also reducing LLM calls and token usage. Our code is available at https://github.com/yhong7/FoG .

Yang Hong, Yajun Yang, Xin Wang +2

Tianjin University, Tianjin, China · Beijing Jiaotong University, Beijing, China

Multi-Hop QA LLM Reasoning with Graphs Graph-Based Retrieval Knowledge Graph Question Answering

Ask PDF

Nov 6, 2025

KGFR: A Foundation Retriever for Generalized Knowledge Graph Question Answering

Large language models (LLMs) excel at reasoning but struggle with knowledge-intensive questions due to limited context and parametric knowledge. However, existing methods that rely on finetuned LLMs or GNN retrievers are limited by dataset-specific tuning and scalability on large or unseen graphs. We propose the LLM-KGFR collaborative framework, where an LLM works with a structured retriever, the Knowledge Graph Foundation Retriever (KGFR). KGFR encodes relations using LLM-generated descriptions and initializes entities based on their roles in the question, enabling zero-shot generalization to unseen KGs. To handle large graphs efficiently, it employs Asymmetric Progressive Propagation (APP)- a stepwise expansion that selectively limits high-degree nodes while retaining informative paths. Through node-, edge-, and path-level interfaces, the LLM iteratively requests candidate answers, supporting facts, and reasoning paths, forming a controllable reasoning loop. Experiments demonstrate that LLM-KGFR achieves strong performance while maintaining scalability and generalization, providing a practical solution for KG-augmented reasoning.

Yuanning Cui, Zequn Sun, Wei Hu +1

School of Computer Science, Nanjing University of Information Science and Technology, Nanjing 210044, China · State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing 210023, China · National Institute of Healthcare Data Science, Nanjing University, Nanjing 210093, China +2

Multi-Hop QA LLM Grounding LLM Reasoning with Graphs Graph-Based Retrieval Graph Foundation Models Knowledge Graph Question Answering

Ask PDF