CROG: Coverage-aware Reasoning Optimization on Graphs for Multi-hop Question Answering¶
会议: EMNLP 2026
论文: ACL Anthology
领域: LLM推理
关键词: 多跳问答、图推理、次模优化、边际覆盖增益、证据子图选择
一句话总结¶
针对图结构多跳问答中独立路径重排序导致证据局部过度重叠与推理步覆盖不足的问题,CROG 将证据组织形式化为带节点预算与连通性约束的次模覆盖最大化问题,通过边际覆盖增益贪心构建紧凑且互补的证据子图。
研究背景与动机¶
多跳问答要求系统跨越分散的多篇文档检索并整合多步证据,以支持事实核查、医疗咨询和法律推理等复杂知识密集型任务。传统的检索增强生成方法多将检索单元视为相互独立的文本块进行打分排序,难以捕捉跨越多跳所需的实体关系与证据结构链条。为此,近期研究广泛引入图推理框架,将非结构化文档或知识库建模为图结构,通过广度优先搜索(BFS)或束搜索从锚点实体向外延展候选推理路径,再将候选路径按与问题的语义相关性排序并截取 Top-K 路径输入大语言模型生成最终答案。
然而,现有多跳图推理方法在证据组织阶段存在严重的结构性缺陷:它们普遍遵循针对单条候选路径的「独立相关性打分与排序」范式。这种范式完全忽视了多跳推理对不同推理子目标的全局覆盖状态。当路径探索算法触及某个局部强相关区域时,迭代延展往往在相邻节点间反复游走,生成大量拓扑高度重叠、语义高度冗余的候选路径。在有限的上下文和证据节点预算约束下,独立重排序算法会贪心选中多个来自同一局部区域的相似路径,从而挤占宝贵的内容预算,导致支撑其它关键推理步的必要证据被完全排除,引发严重的推理不完备现象。
多跳问答的内在本质要求同时满足多个正交或级联的原子推理子目标,而不同子目标的支撑证据往往离散分布在图结构的不同拓扑区域。因此,证据组织绝不能仅靠单路径相关性孤立排序,而必须从全局视角评估候选路径对尚未满足的推理子目标所带来的额外信息增益。核心 idea:将多跳证据组织重构为带预算与图连通性约束的证据子图覆盖优化问题,提出基于边际覆盖增益的贪心选择机制,动态抑制局部冗余路径并优先补全未覆盖推理子目标,在极小证据预算下构建紧凑且连贯的推理子图。
方法详解¶
整体框架¶
CROG 的输入为一个多跳问题 \(q\) 与一个句子级文档图 \(G=(V, E)\),输出为精简且互补的证据子图及最终答案。整体流程划分为两大核心阶段:首先是推理覆盖目标构建(Reasoning Coverage Construction, RCC),通过大语言模型将复杂问题显式解构为原子单跳推理子目标序列,并将其转化为语义特征向量;随后进入覆盖感知推理优化(Coverage-aware Reasoning Optimization, CRO),从语义锚点出发利用 BFS 拓展候选路径集合,以当前已选证据对各子目标的覆盖上限为基准,迭代计算候选路径的边际覆盖增益,在节点总预算与最大连通分量数量约束下贪心选取最优路径,直至无可拓展路径,最后将诱导子图输入大语言模型生成答案。
%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
A["多跳问题与句子级文档图输入"] --> B["推理覆盖目标构建<br/>LLM生成原子子目标并转为嵌入向量"]
B --> C["候选路径语义探索<br/>从检索锚点BFS展开多跳候选路径集合"]
C --> D["覆盖感知推理优化<br/>动态计算未覆盖子目标的边际增益"]
D --> E["拓扑与预算约束过滤<br/>节点预算与Union-Find连通分量约束"]
E --> F["诱导证据子图与回答生成<br/>紧凑互补证据交付LLM解码答案"]
关键设计¶
1. 推理覆盖目标构建:显式解构多跳问题以确立覆盖优化目标 针对传统检索缺乏显式多跳推理里程碑导致检索盲目性的问题,CROG 引入结构化推理计划生成机制。给定多跳输入问题 \(q\),利用大语言模型输出包含问题类型、关键实体和原子推理子步骤的结构化 JSON 计划 \(\text{Plan}(q) = \{r_1, r_2, \dots, r_m\}\)。每个原子子目标 \(r_j\) 严格限定为仅需单篇文档即可解答的最小单跳信息单元。系统随后使用稠密嵌入编码器将每个子目标转换为语义向量 \(u_j \in \mathbb{R}^d\),构建目标集合 \(R = \{u_1, \dots, u_m\}\)。对于候选路径 \(p_i\) 与子目标 \(u_j\),其语义匹配强度定义为路径内所有节点嵌入的最大余弦相似度并截断负值: $\(s(p_i, u_j) = \max\left(\max_{v \in \text{Emb}(p_i)} \cos(v, u_j), 0\right)\)$ 该设计保证只要候选路径中存在至少一个节点强支撑该子目标,该路径即被判定为对该推理步具有贡献,为后续的组合优化提供了精细的目标锚点。
2. 边际覆盖增益驱动的子图贪心优化:消除局部重叠并填补未完成推理链 针对独立路径排序导致高分重叠路径挤占预算、造成推理链缺失的问题,CROG 将证据选择形式化为单调次模函数最大化问题。维护全局已选路径集合 \(S\)(初始为空集)以及各子目标当前的最高覆盖得分 \(c_j = \max_{p \in S} s(p, u_j)\)。在每轮候选决策中,评估候选路径 \(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)\)$ 若某条候选路径仅重复包含已被其它已选路径高度覆盖的信息,其边际增益将直接归零或趋于极小;相反,能够大幅提升此前低覆盖子目标的路径将被优先赋予高优先级。论文从理论上严格证明了该决策问题由最大覆盖问题(Maximum Coverage)多项式规约而来,属于 NP-hard 问题,并证明全局覆盖目标函数具备单调次模性(Monotone Submodular),从而使经典的贪心选择策略享有扎实的理论近似保证。
3. 节点预算与图连通性联合约束:保证证据子图的紧凑性与语义连贯性 单纯追求覆盖增益可能会导致选出零碎、孤立且冗长的事实片段,损害大语言模型多跳推理所需的结构连贯性。CROG 引入双重结构约束机制,在贪心拓展时严格对候选路径进行可行性剪枝。设当前已选路径集所诱导的节点集合为 \(E = \bigcup_{p \in S} \text{nodes}(p)\),候选路径 \(p_i\) 必须同时满足两项硬性约束:(1)节点预算约束 \(|E \cup \text{nodes}(p_i)| \le B\),严格限制最终输入给大模型的证据节点规模;(2)图连通性约束 \(\text{Comp}(E \cup \text{nodes}(p_i), G) \le K\),要求合并新路径后诱导子图的连通分量个数不得超过预设阈值 \(K\)。系统通过并查集(Union-Find)数据结构以摊还复杂度 \(O(\alpha(|V|))\) 动态维护连通分量状态,避免全图重复遍历。该约束迫使优化算法在有限的 token 预算内,优先拼接具有拓扑衔接关系与逻辑依赖的证据链条,构建出紧凑、连贯且高覆盖的证据子图。
评估基准与实验设计¶
实验在 Linux 服务器上进行,配置 Intel Xeon CPU、512GB 内存与 8 张 NVIDIA RTX 4090 GPU(24GB 显存)。测试覆盖四个权威多跳问答基准:HotpotQA(桥接与对比型推理)、2WikiMultiHopQA(复合实体关系链)、MuSiQue(低捷径偏差的高难度多跳)与 MultiHopRAG(密集检索与长文档聚合)。主实验默认采用 BGE-large-en-v1.5 编码文本与目标嵌入,BFS 最大延展深度设为 5,锚点节点数为 20,每个锚点候选路径上限为 20;节点预算 \(B=4\),连通分量限制 \(K=2\)。大语言模型推理均采用贪心解码(temperature=0.0),默认以 Llama-3.1-8B-Instruct 为生成骨干,并在 7B 至 32B 规模的 Qwen2.5 系列模型上验证泛化性,指标报告 3 次独立随机种子的平均值。
实验关键数据¶
主实验¶
在 BGE-large-en-v1.5 稠密检索器设置下,CROG 与多种检索及图推理基线在四大基准上的表现如下表所示(HotpotQA、2WikiMultiHopQA 与 MuSiQue 报告 EM 和 F1,MultiHopRAG 报告 Accuracy;平均单位数 Avg # Units 表示输入大模型的平均证据量):
| 方法 | 检索单元 | 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 |
在极具挑战的词法检索器 BM25 设置下,CROG 同样展现出极强的鲁棒性:
| 方法 | 检索单元 | 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 |
消融实验与优化分析¶
对 CROG 的两大核心组件——推理覆盖目标构建(RCC)与覆盖感知推理优化(CRO)进行系统消融,结果如下:
| 配置 | HotpotQA EM(%) | HotpotQA F1(%) | 2Wiki EM(%) | 2Wiki F1(%) | MuSiQue EM(%) | MuSiQue F1(%) | 说明 |
|---|---|---|---|---|---|---|---|
| CROG (Full) | 52.60 | 65.49 | 47.53 | 57.00 | 30.80 | 43.33 | 完整模型 |
| w/o RCC | 49.80 | 63.45 | 41.80 | 52.03 | 26.80 | 40.54 | 移除推理子目标解构,退化显著(2Wiki EM -5.73%) |
| w/o RCC & w/o CRO | 48.00 | 61.52 | 41.00 | 51.85 | 25.60 | 38.40 | 进一步移除边际覆盖优化,完全依赖传统排序(MuSiQue F1 -4.93%) |
在 400 个抽样实例(候选路径数 \(\le 20\))上,CROG 贪心策略对比穷举全局最优搜索(Exhaustive Optimal Search)的近似比表现:
| 数据集 | 平均路径数 | 平均近似比(Avg. Ratio) | 最差情况近似比(Min 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 |
关键发现¶
- 双核心组件均不可或缺:移除 RCC 导致 2WikiMultiHopQA 上的 EM 下降 5.73%,表明没有显式的原子子目标分解,系统缺乏评判证据是否互补的参照锚点;而进一步移除 CRO 则使 MuSiQue 的 F1 再次跌落 2.14%,证明边际增益对抑制局部语义重复路径至关重要。
- 证据压缩率与精度双赢:CROG 在所有数据集上均取得了超越最强对比方法 SentGraph 的性能(HotpotQA EM +3.80%,2Wiki EM +5.53%,MuSiQue EM +4.00%),同时将输入大模型的平均证据单元压缩至 2.62 句,不仅显著低于段落级方法的 3~5 个段落,也优于原有句子级方法,展现了极高的信息密度。
- 贪心策略的高效逼近性:理论上贪心算法在基数约束次模最大化中具有 \((1 - 1/e) \approx 0.632\) 的最差近似比界,而在多跳 QA 的实测中,CROG 贪心算法在各基准上的平均近似比均超过 0.997,在 HotpotQA 上更是 100% 达到理论全局最优,验证了该贪心策略在实际图证据选择中的卓越实用性。
- 连通性与预算敏感性平衡:预算从 1 增至 3 时性能急剧提升,3 到 5 趋于平稳,验证了多跳问答存在固有的必要步数门槛;而连通性约束 \(K\) 过严(如强制 \(K=1\) 单连通)会导致跨文档跳跃证据被强行过滤从而掉点,适当放宽至 \(K \ge 2\) 即可稳定释放性能。
亮点与洞察¶
- 将证据选择上升为组合次模优化问题:跳出了传统 RAG 和图检索中单纯提高单项相关性排序精度的定势,将证据集选择严谨建模为带图拓扑约束的次模覆盖优化,机制兼具数学优雅性与工程实用性。
- 以边际增益天然化解局部冗余陷阱:在图遍历中,局部聚类往往导致重复检索,CROG 通过动态覆盖扣减机制,使高分但重复的路径边际增益归零,无需人工设计复杂的去重启发式规则。
- 轻量解耦的即插即用架构:该方法仅需对输入问题调用一次单跳分解,后续的候选路径贪心选择完全由向量相似度与并查集在 CPU 上高效完成,推理时间复杂度低至 \(O(n \cdot \bar{l} \cdot m + n^2 m)\),极易嵌入现有的知识图谱或文本图推理管线。
局限与展望¶
- 受限于上游候选路径召回质量:CROG 的优化严格作用于第一阶段 BFS 生成的候选路径池中,若检索锚点发生遗漏或路径延展未能触达真实证据,后验的覆盖优化无法恢复缺失的信息。
- 语义相似度无法完全替代逻辑真值:当前覆盖度基于嵌入余弦相似度计算,这提供了强大的语义对齐信号,但仍无法保证抽取事实在多阶符号逻辑链上的充分性与真值一致性。
- 单语言与通用领域局限:实验目前仅在英文维基百科及通用 QA 基准上展开,多语言场景下的跨语言实体链接以及医疗、金融、法律等高度专业领域的表现仍有待进一步探索。
相关工作与启发¶
- vs SentGraph: SentGraph 同样在句子级图结构上进行路径搜索,但最终依旧采用基于相关性的独立路径排序,极易陷入局部同义子图的死循环;CROG 继承了细粒度句子图的高精度表示,引入全局边际覆盖机制彻底打破局部路径聚类带来的冗余。
- vs SetR (Set-level Retrieval): SetR 尝试在段落检索层面优化证据集合的相关性,但在缺乏显式图拓扑约束的情况下,难以应对结构复杂的跳跃逻辑;CROG 将次模优化与图连通性约束相结合,既保证了覆盖度,又确保了证据链的拓扑连贯性。
- vs RoG / ToG: 传统 KG-based LLM 推理高度依赖预定义知识图谱中完备的结构化关系三元组,在开放域非结构化文本上扩展受限;CROG 证明了通过文档内及跨文档句子图构建与覆盖优化,同样能在非结构化长文本上实现高精度的结构化多跳推理。
评分¶
- 新颖性: ⭐⭐⭐⭐☆ [将多跳证据组织重构为带约束的次模覆盖最大化问题,理论推导扎实]
- 实验充分度: ⭐⭐⭐⭐⭐ [覆盖四大经典多跳基准、两种检索后端及多种模型量级,包含穷举最优对比]
- 写作质量: ⭐⭐⭐⭐⭐ [逻辑严密,图文一致,理论证明完备且实验分析深入透彻]
- 价值: ⭐⭐⭐⭐☆ [对图 RAG、多跳推理及长上下文紧凑检索系统具有极高工程借鉴与落地价值]