Reasoning with Graphs: Structuring Implicit Knowledge to Enhance LLM s Reasoning (2025)

Abstract: Large language models (LLMs) have demonstrated remarkable success across a wide range of tasks; however, they still encounter challenges in reasoning tasks that require understanding and inferring relationships between distinct pieces of information within text sequences. This challenge is particularly pronounced in tasks involving multi-step processes, such as logical reasoning and multi-hop question answering, where understanding implicit relationships between entities and leveraging multi-hop connections in the given context are crucial. Graphs, as fundamental data structures, explicitly represent pairwise relationships between entities, thereby offering the potential to enhance LLMs’ reasoning capabilities. External graphs have proven effective in supporting LLMs across multiple tasks. However, in many reasoning tasks, no pre-existing graph structure is provided. Can we structure implicit knowledge derived from context into graphs to assist LLMs in reasoning? In this paper, we propose Reasoning with Graphs (RwG) by first constructing explicit graphs from the context and then leveraging these graphs to enhance LLM reasoning performance on reasoning tasks. Extensive experiments demonstrate the effectiveness of the proposed method in improving both logical reasoning and multi-hop question answering tasks.

## introduction in recent years, large language models (llms) have demonstrated remarkable capabilities in a variety of tasks, such as question answering @xcite , summarization @xcite , and language understanding @xcite . despite these successes, llms still face significant challenges in certain areas @xcite . a key limitation lies in their struggle with reasoning tasks @xcite , particularly with logical reasoning @xcite , which requires models to infer missing relationships between distinct pieces of information, and multi-hop reasoning @xcite , where they must trace a reasoning path or follow some structures through the context to arrive at the correct answer. to enhance the reasoning capabilities of llms, several prompting methods have been proposed. chain-of-thought (cot) prompting @xcite aids llms in reasoning by generating intermediate steps that lead to the final answer. cot has shown significant improvement in certain reasoning tasks without requiring model tuning. building on cot, the self-consistency method @xcite further enhances reasoning by generating multiple cot pathways and selecting the most consistent one. additionally, tree of thought (tot) @xcite and graph of thoughts (got) @xcite extend this approach by structuring the llms' thought process using trees and graphs, respectively. these methods prompt llms to generate initial thoughts and organize them into various structures. despite the successes of these approaches, they still face challenges in handling complex reasoning tasks, such as logical reasoning @xcite and multi-hop question answering @xcite . for these complex reasoning tasks, llms need to figure out the relationships between entities in the context and infer missing components. take the aiw+ problem @xcite as one example, llms are asked to solve problems such as alice has 3 sisters. her mother has 1 sister who does not have children -she has 7 nephews and nieces and also 2 brothers. alice's father has a brother who has 5 nephews and nieces in total, and who has also 1 son. how many cousins does alice's sister have? in this problem, llms need to infer the relationships between each character, such as the relation between alice and her mother's sister. additionally, llms must infer the missing roles in the question, such as identifying the nephews and nieces that alice's father's brother has. these types of questions pose significant challenges for llms, with many popular models achieving nearly zero accuracy on these tasks @xcite . typically, llms treat the information as a sequence. however, a human solving such a problem would naturally draw a graph to represent relationships between characters and infer missing links based on that structure. this is because graphs provide a fundamental data structure for representing relationships between entities, making them well-suited as reasoning graphs for reasoning tasks. several works have shown the effectiveness of leveraging external graphs to help llms in reasoning, such as improving retrieval quality using graph structures @xcite or reasoning on an external graph @xcite . however, these methods rely on pre-existing graph structures. in most common reasoning tasks, only textual sequences are available. therefore, a natural question arises: "can llms enhance their reasoning abilities by structuring implicit knowledge into explicit graphs?" in this work, we aim to explore reasoning with graphs by constructing explicit graph structures from the context. unlike previous prompting approaches, which construct trees or graphs based on llms' thoughts, our reasoning with graphs (rwg) method directly constructs explicit graphs from the context, where nodes are the entities in the context. the comparison is shown in figure 1 . specifically, we first design a graph construction method with multiple rounds of verification to generate a graph from the given context for the reasoning problem. we then assess the llms' reasoning abilities with the constructed graph. experimental results demonstrate that the proposed rwg significantly improves the performance of various llms on both logical reasoning and multi-hop question answering tasks. rwg showcases the potential of leveraging explicit graph structures derived from the context to enhance llm reasoning capabilities, offering a promising new direction for incorporating structured knowledge into llm-driven tasks. ## reasoning with graph many reasoning tasks involve inferring missing entities and relationships that are not explicitly presented in the question. graphs provide an explicit structure to represent relationships between key entities and serve as a useful tool for inferring missing connections. however, reasoning problems typically do not come with explicit graph representations. reasoning with graph (rwg) teaches large language models to tackle complex reasoning questions by structuring the implicit knowledge within the questions into explicit graph representations and leveraging these graph structures to solve the problems. this mirrors how humans often solve complex reasoning problems -by organizing information in a structured way, such as drawing dia-grams to clarify connections between concepts. in rwg, no additional or external graph information is used. we roughly decompose the process of proposed rwg into two key stages: (1) graph construction: the graph construction prompt guides llms to build an explicit graph based on the context of the reasoning question. we expect the graph to meet different requirements depending on the tasks, which are detailed in sections 4. (2) reasoning with graph: once the graph is constructed, the reasoning question is answered by leveraging the information encoded in the graph structure. next, we will provide a detailed explanation of each stage. ## experiments our framework is inherently task-agnostic, designed to accommodate a wide range of tasks with versatility. to evaluate whether the proposed rwg approach can enhance llms' reasoning and grounded generation capabilities, we test it on two distinct reasoning tasks: logical reasoning and multi-hop question answering. in all experiments, we follow a zero-shot setting. ## conclusion in this paper, we propose a novel reasoning with graphs (rwg) method to structure implicit knowledge to enhance the reasoning capabilities of llms. our method constructs graphs through multiple rounds of generation and verification, leveraging these graphs to answer complex questions. we evaluate our approach on both logical reasoning and multi-hop question-answering tasks using several widely recognized datasets. experimental results demonstrate that rwg significantly improves the performance of various llms across both tasks.