Decompositional Reasoning for Graph Retrieval with Large Language Models

Valentin Six, Evan Dufraisse, Gaël de Chalendar · 2025

Read Decompositional Reasoning for Graph Retrieval with Large Language Models by Valentin Six, Evan Dufraisse, Gaël de Chalendar (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-13380.txt.

Introduction

Valentin Six and co-authors study how breaking questions apart changes graph search in a 2025 paper. Language models increasingly answer from knowledge graphs. A natural trick is to split a hard question into subquestions and retrieve for each, yet what that does to the retrieved material was unexamined.

Using a hybrid retriever whose dial balances the whole question against its parts, the authors show a trade-off. Subquestion-driven retrieval is more precise but returns disconnected fragments; question-driven retrieval keeps the graph's structure and loses relevance. Accuracy peaked between the extremes. Effective reasoning over structured knowledge, they conclude, needs both content and connectedness.

Catalog record

CREATORValentin Six, Evan Dufraisse, Gaël de Chalendar
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE41 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-13380

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Decompositional Reasoning for Graph Retrieval with Large Language Models Valentin Six, Evan Dufraisse, Gaël de Chalendar Abstract Large Language Models (LLMs) excel at many NLP tasks, but struggle with multi-hop reasoning and factual consistency, limiting their effectiveness on knowledge-intensive tasks like complex question answering (QA). Linking Knowledge Graphs (KG) and LLMs has shown promising results, but LLMs generally lack the ability to reason efficiently over graph-structured information. To tackle this problem, we propose a novel retrieval approach that integrates textual knowledge graphs into the LLM reasoning process via query decomposition. Our method decomposes complex questions into sub-questions, retrieves relevant textual subgraphs, and composes a question-specific knowledge graph to guide answer generation. For that, we use a weighted similarity function that focuses on both the complex question and the generated subquestions to extract a relevant subgraph, which allows efficient and precise retrieval for complex questions and improves the performance of LLMs on multi-hop QA tasks. This structured reasoning pipeline enhances factual grounding and interpretability while leveraging the generative strengths of LLMs. We evaluate our method on standard multi-hop QA benchmarks and show that it achieves comparable or superior performance to competitive existing methods, using smaller models and fewer LLM calls. Source code will be available upon acceptance. 1 Introduction Figure 1: Illustration of our decompositional retrieval-based reasoning method. Our method decomposes the question into sub-questions, performs iterative, context-aware retrieval conditioned on previous answers, and merges the resulting subgraphs for guided reasoning. Large Language Models (LLMs) have demonstrated remarkable success across a wide range of natural language processing (NLP) tasks ( Brown et al. 2020 , Chowdhery et al. 2023 , Touvron et al. 2023a , Ouyang et al. 2022 ), including question answering ( Kamalloo et al. 2023 ) , summarization ( Liu et al. 2024 ) , and machine translation ( Zhang et al. 2023 ) . As LLMs have grown in size and have been trained on increasingly diverse and large datasets, their emergent ability to perform different types of reasoning ( Wei et al. 2022a , Zhou et al. 2023 ), ranging from arithmetic ( Imani et al. 2023 ) and neurosymbolic reasoning ( Fang et al. 2024 ) to commonsense inference ( Zhao et al. 2023 ) , has become a central focus of recent research. This has opened new possibilities for solving complex problems that traditionally required structured or symbolic approaches ( Pan et al. 2023 , He-Yueya et al. 2023 ). However, despite their broad capabilities, LLMs still struggle with tasks requiring multi-hop reasoning ( Yang et al. 2024 ) , factual grounding, or explicit access to structured knowledge. These models are prone to hallucinations and logical inconsistencies, particularly when operating in knowledge-intensive domains ( Ji et al. 2023b , Huang et al. 2025 . This is partially due to the high reliance on implicit knowledge stored in parameters ( Hu et al. 2024b ) , and the lack of explicit mechanisms for integrating or reasoning over structured information. Recent work on retrieval-augmented generation ( Lewis et al. 2020 ) , graph-augmented LLMs ( Yasunaga et al. 2021 ) , and neurosymbolic reasoning ( Fang et al. 2024 ) has aimed to bridge this gap. In this work, we address these issues by proposing a method for knowledge-guided decompositional reasoning with LLMs. Our method injects structured knowledge into the reasoning process using textualized knowledge graphs. Specifically, we decompose complex questions into sub-questions, retrieve relevant subgraphs from a textual knowledge graph, and merge them for structured and reasoning-enhanced retrieval (Figure 1 ). The obtained graph is then used to guide LLMs toward generating more accurate and interpretable answers. This hybrid approach enhances both the factual correctness and the transparency of LLM predictions, particularly in settings requiring multi-step reasoning over domain knowledge. To verify the effectiveness of our approach, we conduct extensive experiments on benchmark datasets for complex question answering, namely CWQ ( Talmor and Berant 2018 ) and WebQSP ( Yih et al. 2016 ) . We compare our method against standard prompting techniques, as well as existing state-of-the-art approaches that combine LLMs with knowledge graphs. Results show that our method achieves consistent improvements in accuracy without increasing the number of parameters for the LLM or the number of LLM calls, which shows the efficiency of our method. Our contributions are as follows: • We develop a novel knowledge graph retrieval method that uses query decomposition, helping the LLM to reason over structured data for complex questions. • We introduce a hybrid similarity function that uses the complex question and its decomposition to guide the retrieval process. • We demonstrate improvements in accuracy and factual consistency on multi-hop QA benchmarks. • Our method reduces the number of LLM-calls compared to other baselines, achieving a 3 \times to 5 \times reduction for both datasets. 2 Background 2.1 Can LLMs reason ? LLMs such as GPT-3 ( Brown et al. 2020 ) , PaLM ( Chowdhery et al. 2023 ) , and LLaMA ( Touvron et al. 2023a ) have demonstrated strong performance across a wide range of language tasks, including reasoning-based benchmarks. Their ability to generalize in zero-shot ( Kojima et al. 2022 ) and few-shot settings has led to the emergence of new prompting techniques, such as Chain-of-Thought (CoT) reasoning ( Wei et al. 2022b ) , which improves multi-step reasoning by encouraging models to generate intermediate reasoning steps. Variants like self-consistency ( Wang et al. 2023 ) further refines this by sampling multiple reasoning paths and aggregating answers for improved robustness. More recently, reinforcement learning has been used to entirely train new models ( DeepSeek-AI et al. 2025 ) or improve model prompting ( Pternea et al. 2024 ) , showing great potential for the future. Despite these advances, LLMs remain prone to hallucinations—generating fluent but factually incorrect or logically inconsistent outputs ( Huang et al. 2025 ) , ( Srivastava et al. 2023 ) , ( Ji et al. 2023b ) . This is especially problematic in knowledge-intensive tasks requiring factual grounding, multi-hop reasoning, or domain-specific expertise ( Ji et al. 2023a , Opsahl 2024 ). These issues stem in part from the implicit nature of knowledge storage in model parameters, which limits their ability to verify facts or reason explicitly over external knowledge ( Petroni et al. 2019 , Bommasani et al. 2021 ). Recent work has explored augmenting LLMs with tool use, such as code interpreters ( Pi et al. 2022 ) , equation solvers ( He-Yueya et al. 2023 ) or symbolic solvers ( Lam et al. 2024 ) ( Pan et al. 2023 ) , to externalize and validate parts of the reasoning process. 2.2 LLMs and graphs Figure 2: Overview of our retrieval method: the complex question is first decomposed into smaller subquestions, for which we iteratively perform retrieval and answer generation; once the retrieval is done for all subquestions, we merge the subgraphs and give the result as a hard (textualized graph) and a soft prompt (graph encoder output) to the model. Graphs offer a natural and interpretable way to represent real-world data through entities and their structured relationships. Integrating knowledge graphs with Large Language Models (LLMs) is a promising research direction that enables models to better handle

Read the complete text