DS - MHP : Improving Chain-of-Thought through Dynamic Subgraph-Guided Multi-Hop Path (2025)

Abstract: Large language models (LLMs) excel in natural language tasks, with Chain-of-Thought (CoT) prompting enhancing reasoning through step-by-step decomposition. However, CoT struggles in knowledge-intensive tasks with multiple entities and implicit multi-hop relations, failing to connect entities systematically in zero-shot settings. Existing knowledge graph methods, limited by static structures, lack adaptability in complex scenarios. We propose DS-MHP, a zero-shot framework to enhance LLM reasoning in multi-entity relation tasks. DS-MHP operates in three stages: 1) constructing query-specific subgraphs by extracting entities and relations; 2) generating and refining multi-hop paths using a hybrid strategy of Breadth-First Search, greedy expansion, and LLM supplementation; and 3) guiding LLMs with subgraphs and paths, aggregating answers via majority voting. Evaluated on 12 datasets spanning commonsense, logical, symbolic, and arithmetic reasoning, DS-MHP outperforms baselines and state-of-the-art methods in nearly all benchmarks. It achieves overall average accuracy increases of 3.9% on Mistral-7B and 3.6% on GPT-3.5 Turbo compared to SOTA, with significant gains in logical and symbolic reasoning. Additionally, DS-MHP reduces runtime and LLM calls compared to SOTA, enhancing computational efficiency. These improvements demonstrate DS-MHP’s superior reasoning accuracy, explainability, and efficiency in complex multi-entity tasks.

## introduction large language models (llms) @xcite @xcite @xcite have demonstrated remarkable capabilities across a wide range of natural language processing (nlp) tasks, such as question answering (robinson et al., 2022; li et al., * corresponding author. 2024b; @xcite , machine translation @xcite @xcite , and information extraction @xcite . leveraging extensive pretrained knowledge, these models generate coherent and contextually relevant responses. chain-of-thought (cot) @xcite has significantly enhanced llms' reasoning abilities by guiding them to decompose complex problems into sequential reasoning steps, outperforming traditional zeroshot and few-shot approaches in tasks requiring logical, symbolic, and arithmetic reasoning. however, cot-based methods face challenges in knowledge-intensive tasks involving multiple entities and implicit multi-hop relations. for example, in questions like "which historical figure influenced a modern leader's policies through an intermediary event?". cot may produce intermediate steps but struggles to systematically connect entities (e.g., historical figure, event, modern leader) across multiple relational hops in zero-shot settings without examples. while named entity recognition (ner) @xcite @xcite and relation extraction @xcite @xcite can identify entities and explicit relations, llms often lack structured mechanisms to infer implicit multistep dependencies. knowledge graph (kg)-based approaches, such as paths-over-graph (pog) @xcite , rely on pre-defined kgs and few-shot prompts to explore multi-hop paths but are limited by static knowledge structures, restricted path diversity, and challenges in adapting to ambiguous multi-entity scenarios without dynamic implicit relation inference. in this paper, we introduce ds-mhp, a novel framework designed to enhance llm reasoning through dynamic subgraph-guided multi-hop path in complex multi-entity scenarios. ds-mhp operates in three stages: (1) dynamic subgraph construction, where entities are extracted using zero-shot ner, and explicit and implicit relations are identified and scored for confidence to form a query-specific directed subgraph; (2) multi-hop path generation, which selects key entities based on semantic and structural relevance, generates diverse multi-hop paths using a hybrid strategy of breadth-first search (bfs), greedy expansion, and llm supplementation, and refines them through merging, deduplication, semantic and llm scoring, and subpath filtering; and (3) question answering, where the subgraph and paths are integrated into structured prompts to guide llm, with answers aggregated via majority voting for robustness. we evaluate ds-mhp on 12 widely adopted datasets covering commonsense, logical, symbolic, and arithmetic reasoning, using mistral-7b @xcite and @xcite . ds-mhp outperforms baselines and stateof-the-art (sota) method in nearly all benchmarks, achieving overall average accuracy increases of 3.9% on mistral-7b and 3.6% on gpt-3.5 turbo compared to sota. this indicates that dynamically constructing query-specific subgraphs and generating multi-hop paths can significantly enhance the reasoning capabilities and answer accuracy of llms. our main contributions can be summarized as follows: ## conclusion in this paper, we propose ds-mhp to address the limitations of llms in complex knowledge reasoning and open-domain question answering tasks. by leveraging dynamic subgraphs, multi-hop paths, and majority voting, ds-mhp excels in diverse reasoning scenarios, with particularly notable gains in logical and symbolic reasoning tasks. extensive experiments demonstrate its superior performance, along with reduced runtime and llm calls for enhanced computational efficiency. these results validate the effectiveness of ds-mhp's modular design in improving both reasoning accuracy and practical applicability across various reasoning scenarios.