CROG: Coverage-aware Reasoning Optimization on Graphs for Multi-hop Question Answering¶
Conference: EMNLP 2026
Paper: ACL Anthology
Area: LLM Reasoning
Keywords: Multi-hop Question Answering, Graph Reasoning, Submodular Optimization, Marginal Coverage Gain, Evidence Subgraph Selection
TL;DR¶
Addressing the issue of evidence redundancy and incomplete reasoning coverage caused by independent path ranking in graph-based multi-hop QA, CROG formulates evidence organization as a constrained submodular coverage maximization problem and greedily constructs compact, complementary evidence subgraphs based on marginal coverage gain.
Background & Motivation¶
Multi-hop question answering requires models to retrieve and integrate multiple pieces of evidence dispersed across multiple documents to answer complex queries, playing a pivotal role in knowledge-intensive domains such as fact-checking, medical consultation, and legal analysis. Traditional retrieval-augmented generation (RAG) paradigms retrieve passages or sentences as independently ranked textual chunks, which struggle to capture the complex relational chains connecting entities across reasoning hops. To resolve this limitation, recent literature has increasingly turned to graph-based reasoning frameworks that structure textual corpora or knowledge bases into interconnected graphs, iteratively traversing candidate reasoning paths from query-relevant anchor nodes via breadth-first search (BFS) or beam search, and feeding the top-ranked candidate paths into a large language model (LLM) to generate answers.
Despite progress in structured path exploration, existing graph-based methods suffer from a severe structural flaw during evidence organization: candidate paths are evaluated and ranked independently according to query relevance alone. Such an independent ranking paradigm fails to track whether diverse reasoning requirements have already been fulfilled. Once graph exploration reaches a locally relevant region, iterative traversal repeatedly navigates neighboring nodes within that local cluster, generating multiple candidate paths with substantial topological and semantic overlap. Under a finite context and evidence budget, independent ranking repeatedly selects these redundant paths from the same local neighborhood, consuming the available budget while excluding essential evidence from other semantic regions, which leads to incomplete reasoning coverage.
Multi-hop question answering fundamentally requires satisfying multiple distinct atomic reasoning sub-goals whose supporting evidence is sparsely distributed across different graph regions. Selecting evidence solely based on individual query relevance inevitably biases the context toward locally dominant clusters while starving downstream reasoning steps of necessary premises. Core idea: reformulate graph-based multi-hop evidence organization as a constrained evidence subgraph coverage optimization problem, introducing marginal-gain-based path selection with node-budget and graph-connectivity constraints to dynamically suppress redundant local evidence and prioritize uncovered reasoning targets.
Method¶
Overall Architecture¶
CROG takes as input a multi-hop query \(q\) and a sentence-level document graph \(G=(V, E)\), and outputs a compact, complementary evidence subgraph along with the final answer generated by a downstream LLM. The pipeline consists of two primary components: Reasoning Coverage Construction (RCC), which decomposes the question into atomic single-hop sub-goals using an LLM and maps them to semantic embedding vectors; and Coverage-aware Reasoning Optimization (CRO), which explores candidate paths via BFS expansion from anchor nodes, computes marginal reasoning coverage gains against current coverage states, and greedily selects the optimal paths under node-budget and connected-component constraints to induce a coherent evidence subgraph.
%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
A["Multi-hop Query and Sentence Graph Input"] --> B["Reasoning Coverage Construction<br/>LLM decomposes question into atomic targets"]
B --> C["Candidate Path Semantic Exploration<br/>BFS expansion from retrieved anchor nodes"]
C --> D["Coverage-aware Reasoning Optimization<br/>Compute marginal gain on uncovered sub-goals"]
D --> E["Structural & Budget Constraint Pruning<br/>Node-budget and Union-Find connectivity checks"]
E --> F["Induced Evidence Subgraph & Answer Generation<br/>Deliver compact coherent subgraph to LLM"]
Key Designs¶
1. Reasoning Coverage Construction: Explicit Question Decomposition for Optimization Grounding To overcome the issue of unguided evidence retrieval where models lack explicit milestones for multi-hop reasoning requirements, CROG incorporates an LLM-driven structured reasoning plan. Given the multi-hop question \(q\), an LLM prompt decomposes it into a structured JSON plan \(\text{Plan}(q) = \{r_1, r_2, \dots, r_m\}\), containing question classifications, core named entities, and an ordered sequence of atomic sub-goals. Crucially, each atomic reasoning target \(r_j\) is restricted to a single-hop premise resolvable from an individual document passage. A dense text embedder maps each target \(r_j\) into a semantic vector \(u_j \in \mathbb{R}^d\), forming the reference target set \(R = \{u_1, \dots, u_m\}\). For any candidate reasoning path \(p_i\) and target \(u_j\), the semantic alignment score is defined as the maximum cosine similarity over all node embeddings within \(p_i\), truncated at zero: $\(s(p_i, u_j) = \max\left(\max_{v \in \text{Emb}(p_i)} \cos(v, u_j), 0\right)\)$ This design guarantees that a candidate path is deemed to support a reasoning sub-goal as long as at least one constituent node strongly matches the target semantics, providing an explicit, quantifiable objective for subsequent set optimization.
2. Marginal Coverage Gain Optimization: Eliminating Structural Overlap and Completing Reasoning Chains To resolve the limitation of independent ranking where top-scoring overlapping paths crowd out complementary premises, CROG formulates path selection as a monotone submodular maximization problem. Initializing the selected path set as \(S = \emptyset\) and tracking the current maximum coverage status for each target as \(c_j = \max_{p \in S} s(p, u_j)\), CROG evaluates the marginal coverage gain contributed by each unselected candidate path \(p_i \in \mathcal{P} \setminus S\): $\(\Delta(p_i \mid S) = \frac{1}{m} \sum_{j=1}^m \max(s(p_i, u_j) - c_j, 0)\)$ When a candidate path merely duplicates information that has already been sufficiently covered by previously selected paths, its marginal gain drops toward zero; conversely, paths bridging previously under-covered reasoning steps receive a significant score boost. The authors theoretically prove that the decision version of this optimization problem is NP-complete via polynomial reduction from Maximum Coverage, and establish that the coverage objective function \(F(S) = \frac{1}{m}\sum_{j=1}^m \max_{p \in S} s(p, u_j)\) is monotone and submodular, providing a rigorous \((1 - 1/e)\) approximation guarantee for the greedy selection process under cardinality constraints.
3. Joint Node-Budget and Connectivity Constraints: Enforcing Compactness and Subgraph Coherence Pure coverage maximization without structural boundaries risks selecting fragmented, disconnected facts that disrupt the multi-hop inference chain in language models. CROG addresses this by imposing two structural constraints during greedy path evaluation. Denoting the cumulative node set induced by current selections as \(E = \bigcup_{p \in S} \text{nodes}(p)\), a candidate path \(p_i\) is feasible if and only if: (1) the node-budget constraint \(|E \cup \text{nodes}(p_i)| \le B\) is satisfied, bounding total evidence volume; and (2) the induced subgraph after adding \(p_i\) contains at most \(K\) connected components, denoted as \(\text{Comp}(E \cup \text{nodes}(p_i), G) \le K\). The connectivity state is incrementally tracked via a disjoint-set (Union-Find) data structure with amortized complexity \(O(\alpha(|V|))\). This dual-constraint mechanism prevents over-expansion and forces the greedy optimizer to favor paths that topologically and logically connect previously selected nodes, assembling a tight, coherent evidence subgraph.
Benchmark & Evaluation Protocol¶
Experiments are conducted on Linux servers equipped with Intel Xeon CPUs, 512 GB RAM, and 8 NVIDIA GeForce RTX 4090 GPUs (24 GB VRAM each). Evaluations span four diverse multi-hop QA benchmarks: HotpotQA (bridge-style and comparison questions), 2WikiMultiHopQA (compositional multi-hop entity-relation chains), MuSiQue (challenging compositional reasoning with reduced shortcut bias), and MultiHopRAG (retrieval-intensive multi-document aggregation). BGE-large-en-v1.5 serves as the default dense retriever for constructing sentence embeddings and node alignments; the BFS exploration depth is set to 5 with 20 anchor nodes and up to 20 candidate paths per anchor. Structural hyper-parameters are set to default budget \(B=4\) and component limit \(K=2\). Downstream generation uses greedy decoding (temperature=0.0) on Llama-3.1-8B-Instruct, with generalization validated across Qwen2.5 models (7B, 14B, 32B). Exact Match (EM) and F1 are reported for HotpotQA, 2WikiMultiHopQA, and MuSiQue, and Accuracy is reported for MultiHopRAG across 3 independent runs.
Key Experimental Results¶
Main Results¶
Under the BGE-large-en-v1.5 dense retriever setting, CROG significantly outperforms prior retrieval and graph-based baselines across all four benchmarks while utilizing fewer evidence units on average:
| Method | Retrieval Unit | Avg # Units | HotpotQA EM(%) | HotpotQA F1(%) | 2Wiki EM(%) | 2Wiki F1(%) | MuSiQue EM(%) | MuSiQue F1(%) | MultiHopRAG Acc(%) |
|---|---|---|---|---|---|---|---|---|---|
| Retrieval Only | Passage | 3.00 | 11.00 | 18.09 | 3.80 | 10.34 | 2.40 | 6.86 | 44.40 |
| Retrieval Only | Sentence | 3.00 | 38.60 | 50.88 | 30.80 | 40.01 | 17.00 | 28.57 | 60.20 |
| RankLlama | Passage | 5.00 | 31.88 | 32.95 | 32.24 | 25.78 | 7.61 | 11.77 | 43.51 |
| SetR-Selection only | Passage | 3.41 | 36.68 | 37.84 | 34.84 | 29.40 | 10.38 | 15.28 | 46.20 |
| SetR-CoT | Passage | 2.88 | 36.46 | 38.20 | 35.34 | 30.34 | 9.76 | 14.31 | 45.26 |
| SetR-CoT & IRI | Passage | 2.91 | 36.62 | 38.11 | 35.44 | 30.35 | 10.79 | 15.43 | 47.14 |
| LightRAG | Passage | 3.00 | 27.17 | 37.75 | 17.40 | 26.99 | 8.60 | 17.71 | 20.44 |
| KGP | Passage | 3.00 | 44.00 | 58.73 | 36.80 | 48.20 | 21.20 | 34.72 | 63.40 |
| SentGraph | Sentence | 2.70 | 48.80 | 62.92 | 42.00 | 52.26 | 26.80 | 40.36 | 65.60 |
| CROG | Sentence | 2.62 | 52.60 | 65.49 | 47.53 | 57.00 | 30.80 | 43.33 | 67.40 |
Under the lexical BM25 retrieval configuration, CROG maintains superior performance and strong robustness across all evaluated tasks:
| Method | Retrieval Unit | Avg # Units | HotpotQA EM(%) | HotpotQA F1(%) | 2Wiki EM(%) | 2Wiki F1(%) | MuSiQue EM(%) | MuSiQue F1(%) | MultiHopRAG Acc(%) |
|---|---|---|---|---|---|---|---|---|---|
| SentGraph | Sentence | 2.57 | 43.80 | 57.13 | 32.20 | 39.48 | 16.00 | 26.83 | 63.40 |
| CROG | Sentence | 2.58 | 47.20 | 59.75 | 39.80 | 47.32 | 20.80 | 33.04 | 64.60 |
Ablation Study & Optimization Analysis¶
Ablation experiments isolating the two core components of CROG—Reasoning Coverage Construction (RCC) and Coverage-aware Reasoning Optimization (CRO)—demonstrate their respective contributions:
| Configuration | HotpotQA EM(%) | HotpotQA F1(%) | 2Wiki EM(%) | 2Wiki F1(%) | MuSiQue EM(%) | MuSiQue F1(%) | Note |
|---|---|---|---|---|---|---|---|
| CROG (Full) | 52.60 | 65.49 | 47.53 | 57.00 | 30.80 | 43.33 | Full framework |
| w/o RCC | 49.80 | 63.45 | 41.80 | 52.03 | 26.80 | 40.54 | Without sub-goal decomposition (-5.73% EM on 2Wiki) |
| w/o RCC & w/o CRO | 48.00 | 61.52 | 41.00 | 51.85 | 25.60 | 38.40 | Pure independent ranking baseline (-4.93% F1 on MuSiQue) |
Furthermore, comparison against Exhaustive Optimal Search on 400 instances containing up to 20 candidate paths reveals near-optimal empirical performance:
| Benchmark | Avg. Candidate Paths | Avg. Approximation Ratio | Min Approximation Ratio |
|---|---|---|---|
| HotpotQA | 6.2 | 1.0000 | 1.0000 |
| 2WikiMultiHopQA | 5.3 | 0.9992 | 0.9395 |
| MuSiQue | 5.6 | 0.9984 | 0.9607 |
| MultiHopRAG | 13.8 | 0.9977 | 0.9520 |
Key Findings¶
- Indispensability of Both Core Modules: Eliminating RCC drops 2WikiMultiHopQA EM from 47.53% to 41.80%, indicating that without explicit reasoning targets, the selection lacks directional criteria for what constitutes complementary evidence. Discarding CRO causes an additional drop on MuSiQue from 26.80% to 25.60% EM, confirming that marginal gain optimization is crucial for suppressing redundant overlapping paths.
- Superior Evidence Efficiency: CROG achieves new state-of-the-art results across all datasets using only 2.62 sentence-level units on average, outperforming SentGraph (2.70 units) and passage-level baselines (3 to 5 passages), demonstrating that structured coverage-aware selection constructs highly information-dense prompts.
- Empirical Approximation Near Optimum: While theoretical submodular guarantees establish a \((1 - 1/e) \approx 0.632\) lower bound, CROG-Greedy achieves average approximation ratios exceeding 0.997 across all benchmarks compared to exhaustive optimal search, achieving an exact 1.0000 match on HotpotQA.
- Budget and Connectivity Dynamics: Performance scales sharply as node budget expands from 1 to 3 before plateauing between 3 and 5, demonstrating that multi-hop questions possess intrinsic premise cardinality limits. Overly rigid connectivity constraints (\(K=1\)) stifle cross-hop retrieval, whereas relaxing \(K \ge 2\) yields resilient, stable performance.
Highlights & Insights¶
- Formulating Evidence Selection as Submodular Optimization: Bridges the gap between heuristics-driven graph RAG and formal combinatorial optimization, modeling multi-hop evidence assembly as a constrained submodular coverage problem with rigorous theoretical guarantees.
- Dynamic Marginal Gain Mitigates Local Cluster Bias: Graph exploration naturally concentrates in dense semantic neighborhoods; CROG's marginal coverage subtraction naturally nullifies redundant paths without requiring brittle, hand-crafted deduplication rules.
- Plug-and-Play Computational Efficiency: Requiring only a single LLM decomposition prompt and lightweight embedding dot-products with Union-Find operations (\(O(n \cdot \bar{l} \cdot m + n^2 m)\)), CROG integrates seamlessly into existing graph or RAG pipelines with minimal computational overhead.
Limitations & Future Work¶
- Reliance on Upstream Candidate Recall: CROG operates strictly over candidate paths pre-extracted by the initial BFS traversal; if anchor retrieval misses key entities or BFS fails to traverse critical hops, the downstream optimization cannot recover lost facts.
- Semantic Similarity Disconnected from Logical Verification: Coverage is currently estimated using cosine similarity between embeddings, which acts as a dense semantic proxy but lacks explicit symbolic verification of multi-step logical truth and deductive validity.
- Limited to English and General Domains: Current benchmarks focus on general-domain English Wikipedia corpora; evaluating transferability to multilingual settings and specialized domains (such as biomedicine or legal case analysis) remains an open challenge.
Related Work & Insights¶
- vs SentGraph: SentGraph constructs fine-grained sentence graphs but evaluates candidate paths independently, frequently trapping the context in locally dense subgraphs; CROG leverages the same sentence-graph topology but replaces independent scoring with marginal coverage optimization.
- vs SetR: SetR conducts set-level evidence selection over flat passage pools, but lacks graph topology to enforce structural reasoning paths; CROG integrates graph connectivity constraints with submodular set optimization, ensuring both high coverage and topological continuity.
- vs RoG / ToG: While RoG and ToG reason over pre-existing structured knowledge graphs with fixed relation schemas, CROG demonstrates that submodular reasoning optimization operates effectively over unstructured text converted into sentence-level relation graphs.
Rating¶
- Novelty: ⭐⭐⭐⭐☆ [Solid mathematical reformulation of multi-hop graph evidence selection as constrained submodular optimization]
- Experimental Thoroughness: ⭐⭐⭐⭐⭐ [Evaluated across 4 benchmarks, dense/lexical retrievers, multiple LLM sizes, and exhaustive optimal search]
- Writing Quality: ⭐⭐⭐⭐⭐ [Clear problem formulation, elegant theoretical proofs, and intuitive empirical ablation]
- Value: ⭐⭐⭐⭐☆ [High practical value for Graph RAG, multi-hop reasoning, and efficient context compression]