Multi-hop question answering requires retrieving and integrating multiple pieces of evidence distributed across documents. Recent graph-based methods improve multi-hop reasoning through graph traversal over relational evidence structures. However, existing methods rely on independent path ranking during evidence organization, which often produces redundant and reasoning-incomplete evidence sets due to substantial structural overlap among selected graph paths. In this work, we argue that graph-based evidence organization may, to some extent, be formulated as a constrained evidence subgraph optimization problem. Based on this perspective, we propose CROG, a coverage-aware reasoning optimization framework that performs marginal-gain-based path selection to favor previously uncovered reasoning steps while suppressing redundant evidence, with node-budget and connectivity constraints to encourage compact and coherent evidence subgraphs. Experiments on multiple benchmarks demonstrate that CROG achieves superior reasoning performance while using fewer evidence units on average, and analysis based on exhaustive optimal search further validates the effectiveness of the greedy optimization strategy.

Knowledge graph question answering (KGQA) aims to answer natural language questions using knowledge graphs.Recent research leverages large language models (LLMs) to enhance KGQA reasoning, but faces limitations: retrieval-based methods are constrained by the quality of retrieved information, while agent-based methods rely heavily on proprietary LLMs.To address these limitations, we propose Retrieval-Judgment-Exploration (RJE), a framework that retrieves refined reasoning paths, evaluates their sufficiency, and conditionally explores additional evidence. Moreover, RJE introduces specialized auxiliary modules enabling small-sized LLMs to perform effectively: Reasoning Path Ranking, Question Decomposition, and Retriever-assisted Exploration. Experiments show that our approach with proprietary LLMs (such as GPT-4o-mini) outperforms existing baselines while enabling small open-source LLMs (such as 3B and 8B parameters) to achieve competitive results without fine-tuning LLMs.Additionally, RJE substantially reduces the number of LLM calls and token usage compared to agent-based methods, yielding significant efficiency improvements.