Reranking Answers of Large Language Models with Knowledge Graphs

Mikhail Salnikov; Hai Le; Olga Tsymboi; Ivan Lazichny; Dmitrii Iarosh; Egor Cheremiskin; Andrey Savchenko; Dmitry Simakov

cs.CLOct 18, 2026

Reranking Answers of Large Language Models with Knowledge Graphs

Authors: Mikhail Salnikov, Hai Le, Olga Tsymboi, Ivan Lazichny, Dmitrii Iarosh, Egor Cheremiskin, Andrey Savchenko, Dmitry Simakov,

Organizations: Artificial Intelligence Research Institute, Moscow, Russia · Skolkovo Institute of Science and Technology, Moscow, Russia · Sber AI Lab, Moscow, Russia · Moscow Institute of Physics and Technology, Moscow, Russia ·

Abstract

Answering natural language questions over knowledge graph data is challenging due to the vast number of facts, which can be difficult to process and navigate. One potential solution for this issue is to use mined subgraphs related to the query, although this process still requires extracting these subgraphs. This research presents a solution for extracting subgraphs related to entity candidates from a question-and-answer set, which can be obtained by inferring a large language model by calculating the shortest paths between entities. The proposed approaches detail various features that can be extracted from the subgraphs and reranking models to select the most probable answers from a list of candidates. Experiments were conducted on Wikidata to evaluate the effectiveness of the proposed approaches. This involved enumerating all the main feature types that can be extracted from mined subgraphs and a detailed analysis of the proposed features and reranking method combinations. In addition, a public web application that provides a useful web tool for studying the graph space between question and answer entities has been developed to work with subgraphs. This includes visualization of the extracted subgraph and automatic generation of natural language text to describe it.

Figures & tables

Figure 1: The motivation of our research: LLM’s top-1 QA prediction accuracy is often incorrect. However, the correct answer is often in the top 10-40 alternative generations. Thus, a better reranking, such as the one presented in this article, is required. Dependence of Hit@N metric on the size of answer pool

N

on Mintaka [ 32 ] full dataset and Mistral [ 11 ] , Mixtral [ 12 ] , T5-Large-SSM and T5-XL-SSM [ 26 ] tuned models using Diverse Beam Search [ 39 ] as an inference strategy.

Figure 2: The proposed method for reranking language model answers with KGs. The method includes subgraph extraction, features extraction, and various ranker approaches. The subgraphs consist of the shortest paths between question entities and answer candidates, as discussed in Section 3.1 . Various features were extracted for the ranker approaches, including text, graph, and Graph2Text Sequence Features, as discussed in Section 3.2 .

Figure 3: Extraction of subgraphs between question and answer in KG. We combine the extracted shortest paths into a single subgraph, adding links between intermediate nodes. Here,

\text{QE}_{n}

is the Question Entities, A is the current answer candidate entity, and the colored nodes represent the intermediate entities.

Table 1: Statistics of the WebNLG 2.0 parallel knowledge graph-to-text dataset.

Subgraph	Corresponding Graph2Text
	T5	GAP

	Mount Rainier is located in North America.	The summit of North America is called Mount Rainier.
	Louisa May Alcott and Ramona Quimby are both females.	Louisa May Alcott and Ramona Quimby are both men.
	The United States of America is the location of the National Statuary Hall and the office of the President of the United States.	The National Statuary Hall is located in the United States of America, where the leader is known as the President. The country is the location of the US congress and has the President as its President.
	The Harry Potter prequel is written in English, as is the Harry Potter book.	English is the language of both Harry Potter prequel and the English book.

Table 2: Examples of subgraphs and their corresponding generated texts for various feature extractors.

Figure 4: Comparative analysis of reranking methods applied to candidate pools generated by T5-Large-SSM, T5-XL-SSM, Mistral-7B, and Mixtral-8x7B. Bars represent the Hit@1 score of the top-ranked answer on Mintaka dataset. Methods are grouped by model architecture: Baseline (Without reranking, Majority Vote), RankGPT, Regression Baselines (Linear/Logistic), Gradient Boosting (CatBoost), and proposed Neural Ranker (MPNet). Error bars indicate standard deviation over 3 runs for non-deterministic methods.

Figure 5: Reranking performance on the MKQA dataset using candidate answers from T5-Large-SSM and T5-XL-SSM. Unlike Mintaka, MKQA requires entity linking for question entities, testing the pipeline’s robustness to noisy subgraph extraction.

Figure 6: Permutation importance of graph features for Linear and Logistic Regression rankers on answer candidates generated by T5-Large-SSM and by T5-XL-SSM

Figure 7: Permutation importance of graph features for Linear and Logistic Regression rankers on answer candidates generated by Mistral and by Mixtral

Figure 8: Permutation importance of graph, text, and G2T features for Catboost rankers on answer candidates generated by T5-Large-SSM and T5-XL-SSM

Figure 9: Permutation importance of graph, text, and G2T features for Catboost rankers on answer candidates generated by Mistral and Mixtral

Answers Source		Question Entities Accuracy	Answer Entities Accuracy
Graph2Text (T5)
T5-Large-SSM	TRAIN	0.995	0.833
T5-Large-SSM	TEST	0.954	0.835
T5-XL-SSM	TRAIN	0.955	0.827
T5-XL-SSM	TEST	0.955	0.829
Graph2Text (GAP)

Table 3: Graph2Text Accuracy of label generation for entities in texts generated from subgraphs.

Figure 10: Hit@N Metrics for Different N Values on Mintaka [ 32 ] full dataset for generated by Diverse Beam Search [ 39 ] answers by LLM tuned models with different reranking approaches.

Figure 11: A web application that visualizes subgraphs for given entities. Examples of the USA, China, and Yuri Gagarin are shown on the left side. On the right side are examples of James Bond and the United Kingdom. Both examples provide not only subgraphs but also their Graph2Text representation.

Figure 12: Web application for KGQA with extracted subgraph visualization for question “ Which movie is part of the Marvel Cinematic Universe and has Chadwick Boseman in the titular role? ”. Entity linker extracted entity Marvel Cinematic Universe (Q642878) and Chadwick Boseman (Q5066520) from question and language model predicted Daredevil (Q16977365) as a top-1 answer that is incorrect what is indirectly seen from the subgraph.

Figure 13: Subgraph for question “ Which movie is part of the Marvel Cinematic Universe and has Chadwick Boseman in the titular role? ” which include entities Marvel Cinematic Universe (Q642878) and Chadwick Boseman (Q5066520) in question. The correct answer for the question is entity Black Panther (Q23780734).

Appendix figures & tables7 assets

Supplementary material from the paper’s appendix.

Appendix

Reranking Model	Features	Hit@1	Hit@2	Hit@3
Without reranking		0.2395	0.3580	0.4020
Full random		0.0278	0.0562	0.0828
Majority Vote		0.2213	0.3422	0.3875
Semantic reranking	Text	0.0298	0.0647	0.0965
RankGPT (Mistral)	Text	$0.2442\pm 0.0004$	$0.3237\pm 0.0004$	$0.3864\pm 0.0007$
RankGPT (Mistral)	Text + G2T (Det. Lin.)	$0.1984\pm 0.0007$	$0.2904\pm 0.0008$	$0.3613\pm 0.0010$

Appendix

Table 4: Hit@1-3 for all proposed reranking approaches and features after reranking the T5-Large-SSM generated answer candidates for Mintaka dataset.

Reranking Model	Features	Hit@1	Hit@2	Hit@3
Without reranking		0.3042	0.4298	0.4688
Full random		0.0235	0.0473	0.0723
Majority Vote		0.2677	0.4020	0.4417
Semantic reranking	Text	0.0245	0.0545	0.0830
RankGPT (Mistral)	Text	$0.2501\pm 0.0011$	$0.3356\pm 0.0001$	$0.4017\pm 0.0007$
RankGPT (Mistral)	Text + G2T (Det. Lin.)	$0.2083\pm 0.0004$	$0.3058\pm 0.0004$	$0.3791\pm 0.0007$

Appendix

Table 5: Hit@1-3 for all proposed reranking approaches and features after reranking the T5-XL-SSM generated answer candidates for Mintaka Dataset.

Reranking Model	Features	Hit@1	Hit@2	Hit@3
Without reranking		0.4655	0.5313	0.5590
Full random		0.0920	0.1585	0.2165
Majority Vote		0.4228	0.5020	0.5345
Semantic reranking	Text	0.0858	0.1393	0.1790
RankGPT (Mistral)	Text	$0.3838\pm 0.0007$	$0.4618\pm 0.0002$	$0.5112\pm 0.0004$
RankGPT (Mistral)	Text + G2T (Det.Lin.)	$0.3315\pm 0.0006$	$0.4310\pm 0.0005$	$0.4893\pm 0.0005$

Appendix

Table 6: Hit@1-3 for all proposed reranking approaches and features after reranking the Mistral generated answer candidates for Mintaka dataset.

Reranking Model	Features	Hit@1	Hit@2	Hit@3
Without reranking		0.5173	0.5628	0.5735
Full random		0.0580	0.1090	0.1455
Majority Vote		0.4858	0.5645	0.5930
Semantic reranking	Text	0.0303	0.0550	0.0715
RankGPT (Mistral)	Text	$0.3958\pm 0.0005$	$0.4733\pm 0.0002$	$0.5233\pm 0.0004$
RankGPT (Mistral)	Text + G2T (Det. Lin.)	$0.3430\pm 0.0007$	$0.4422\pm 0.0001$	$0.5012\pm 0.0003$

Appendix

Table 7: Hit@1-3 for all proposed reranking approaches and features after reranking the Mixtral generated answer candidates for Mintaka Dataset.

Reranking Model	Features	Hit@1	Hit@2	Hit@3
Without reranking		0.0925	0.1139	0.1317
Full random		0.0249	0.0391	0.0712
Majority Vote		0.0961	0.1281	0.1423
Semantic reranking	Text	0.0000	0.0000	0.0000
RankGPT (Mistral)	Text	$0.0107\pm 0.0000$	$0.0463\pm 0.0000$	$0.0747\pm 0.0000$
RankGPT (Mistral)	Text + G2T (Det. Lin.)	$0.0107\pm 0.0000$	$0.0356\pm 0.0000$	$0.0569\pm 0.0000$

Appendix

Table 8: Hit@1-3 for all proposed reranking approaches and features after reranking the T5 Large SSM generated answer candidates on MKQA dataset.

Reranking Model	Features	Hit@1	Hit@2	Hit@3
Without reranking		0.4306	0.4911	0.5267
Full random		0.2112	0.2871	0.3713
Majority Vote		0.4306	0.4982	0.5267
Semantic reranking	Text	0.1246	0.2562	0.3345
RankGPT (Mistral)	Text	$0.1495\pm 0.0000$	$0.2254\pm 0.0017$	$0.2894\pm 0.0017$
RankGPT (Mistral)	Text + G2T (Det. Lin.)	$0.1210\pm 0.0000$	$0.1815\pm 0.0000$	$0.2527\pm 0.0000$

Appendix

Table 9: Hit@1-3 for all proposed reranking approaches and features after reranking the T5 XL SSM generated answer candidates on MKQA Dataset.

Component	Requirements	Main consumer
CPU	AMD EPYC 7702 64-Core	Multithreading in graphs preprocessing
RAM	80GB (used by one thread, for multithreading 1TB was used)	Subgraphs extraction algorithm for loading knowledge graph into memory
GPU	2 x NVIDIA A100	Training and evaluation of Mistral/Mixtral models

Appendix

Table 10: Hardware requirements for evaluation of presented experiments

Knowledge Graph Question Answering

Knowledge Graph Question Answering answers natural-language questions by finding and reasoning over entities and relations in structured knowledge graphs.

See all 165 papers

Search-on-Graph-R1: Training Large Language Models to Search Knowledge Graphs with Reinforcement Learning
Jul 20, 2026Jia Ao Sun, Hao Yu, Fengran Mo +4LLM Reasoning with Graphs RL for Language Model Reasoning
Université de Montréal · Mila – Québec AI Institute · McGill University +2
GRISP: Guided Recurrent IRI Selection over SPARQL Skeletons
Apr 22, 2026Sebastian Walter, Hannah BastKnowledge Graph Question Answering Knowledge Graphs
University of Freiburg · Department of Computer Science · Freiburg im Breisgau, Germany
Towards a Learnable Retriever for Textual Graph Question Answering
Oct 24, 2026Kaifeng Jin, Yuchen Yan, Zhichen Zeng +4Graph-Based Retrieval Graph Retrieval-Augmented Generation
University of Illinois Urbana-Champaign · Wayne State University · Meta

Jul 20, 2026J/K move · Enter open · S save

Search-on-Graph-R1: Training Large Language Models to Search Knowledge Graphs with Reinforcement Learning

Jia Ao Sun, Hao Yu, Fengran Mo, Zhan Su+3

Université de Montréal · Mila – Québec AI Institute · McGill University+2

LLM Reasoning with Graphs RL for Language Model Reasoning Graph-Based Retrieval LLM Tool Use Knowledge Graph Question Answering

Open paper AskPDF arXiv

Knowledge graph question answering (KGQA) requires navigating from topic entities to an answer several relations away. Recent methods prompt a frontier LLM to explore the graph through a retrieval tool, but their reliance on frontier-scale inference makes them costly to deploy. We present Search-on-Graph-R1 (\sogrone{}), which internalizes this navigation into a compact 8B model through supervised fine-tuning (SFT) followed by reinforcement learning (RL). Our central idea is to scaffold a frontier teacher with each question's gold SPARQL query, so the teacher traverses a known answer-bearing path with a live Search tool rather than having to discover the path itself. Since every call executes against a live Freebase server, the resulting trajectories are grounded in the knowledge graph by construction. On WebQSP, CWQ, and GrailQA, \sogrone{} at 8B surpasses every frozen frontier-LLM system in our comparison and posts the strongest results on CWQ of any system we compare against. It does so using no auxiliary module at inference and no LLM judge during training. Isolating each training stage shows that SFT and RL contribute complementary gains, our approach transfers across model families, and RL learns to reach answers in fewer Search calls than its SFT initialization.

Abstract

Knowledge Graph Question Answering

Explore similar work

Search-on-Graph-R1: Training Large Language Models to Search Knowledge Graphs with Reinforcement Learning

GRISP: Guided Recurrent IRI Selection over SPARQL Skeletons

Towards a Learnable Retriever for Textual Graph Question Answering