LoRe：面向迭代图求解器的自适应交互评估路由与每步交互预算

# LoRe：面向迭代图求解器的自适应交互评估路由与每步交互预算

来源：https://arxiv.org/html/2605.29005

###### 摘要

基于扩散的神经网络求解器在解决组合优化问题时，需要反复重新评估密集的边/因子交互，这导致推理在时钟时间上开销高昂，且在规模较大时通常受内存限制。受多体物理计算方法的启发，我们提出了 LoRe——一种无需训练、推理时即插即用的包装器，它强制执行每步交互评估预算：在每次迭代中，只评估固定比例的交互，通过动态地将计算路由到高冲突或高不确定性的交互上，而不是使用固定的稀疏化（例如，静态k近邻图或静态掩码）。在完全包含的端到端时钟时间核算下，LoRe 显著提升了最大独立集（MIS）问题的可扩展性，将可行推理范围扩展到超过基线内存溢出限制的 3 倍以上，实现了约 8 倍的加速和约 12 倍的峰值内存降低，且在该范围内保持了求解质量。在大规模旅行商问题（TSP）上展示了跨任务的通用性，并在拓扑偏移下实现了零样本鲁棒性，LoRe 在 n=1000 时实现了约 15 倍的加速和 44 倍的内存降低，且具有良好的巡回质量。

组合优化，基于扩散的神经求解器，条件计算 / 动态稀疏性，运行时路由，每步交互评估预算

## 1 引言

许多现实世界的组合决策系统将求解器作为内循环原语调用，在请求到达和约束变化时反复重新优化。例如，动态车辆路径规划中的实时调度和路由、应对不断变化作业到达的数据中心或集群调度，以及响应时变拥塞的网络资源分配（Pillac 等, 2013; Verma 等, 2015; Kelly 等, 1998）。在这些部署中，必须快速生成可行解，然后在严格的延迟和内存预算下进行改进，因此约束条件通常是每次迭代的计算/内存包络，而不仅仅是总改进步数——这是已部署决策系统中的经典“随时”要求（Zilberstein, 1996）。

在图上的迭代神经求解器，特别是基于扩散和基于 GNN 的模型，在组合优化（CO）问题上取得了强劲表现（Bengio 等, 2021; Cappart 等, 2023; Mazyavkina 等, 2021; Sun and Yang, 2023; Sanokowski 等, 2024; Zhao 等, 2025），包括经典任务如最大独立集（MIS）和旅行商问题（TSP）。然而，它们的可扩展性受到一个重复成本模式的瓶颈限制：每个改进步骤都需要对整个交互拓扑（例如，所有边或因子对）进行密集评估以解决冲突（Scarselli 等, 2009; Gilmer 等, 2017; Hamilton 等, 2017）。在固定步数 T 和密集消息传递下，计算成本为 O(T|A|)，峰值内存随交互集大小 |A| 线性增长。在大规模图上，这种全支持扫描常常突破硬件包络，导致内存溢出（OOM）失败或不可接受的延迟。

这个瓶颈带来了一个两难选择。减少步数 T（例如，蒸馏）并不能降低每步峰值内存。另一方面，静态空间稀疏化（例如，固定 kNN 图）减少了每步占用，但无法捕捉组合冲突的状态依赖性。在迭代改进过程中，“热点”——高冲突或高不确定性的区域——会随时间漂移。固定的稀疏支持不可避免地会遗漏新出现的关键交互，导致误差累积和轨迹漂移。

我们观察到，这一挑战在概念上类似于凝聚态物理中的多体问题。在强关联系统（例如 Hubbard 模型）中，计算无限晶格上的精确相互作用是棘手的。相反，像团簇动力学平均场理论（C-DMFT）这样的方法将系统分解为一个团簇（局部区域，其中强关联被精确求解）和一个浴场（一个近似全局环境的背景场）。关键是，团簇与浴场之间的耦合确保了局部精确性在全局上下文中得以保持。

受这一物理洞察的启发，我们提出了 LoRe（局部重新计算），一种*无需训练*、*推理时*的协议，它将团簇-浴场分解操作化应用于图求解器。LoRe 通过动态路由计算来强制执行严格的每步算子预算：

- •**团簇**：在每一步，LoRe 识别一个随时间变化的高冲突交互子集 \(M_t\) 进行精确评估。
- •**浴场**：被省略交互的影响通过一个轻量级的全局召回信号进行近似，防止团簇与全局状态脱节。

与静态稀疏化不同，LoRe 跟踪求解器轨迹中的“漂移热点”。它作为一个即插即用的包装器，将标准密集求解器转换为预算感知的动态系统，无需重新训练。图 1 总结了 LoRe 协议。

![图 1](#)  
图 1: LoRe 通过在严格预算 \(\|M_t\| \leq \rho \|A\|\) 下，将每步交互评估路由到由时变高冲突团簇覆盖的交互子集 \(M_t\)，实现*时域算子稀疏性*，并通过轻量级召回和投影/修复可选地稳定。

我们将 LoRe 作为一个无需训练、推理时即插即用的包装器进行评估，使用完全包含的端到端时钟时间测量，并采用明确可审计的核算协议（在第 3 节中描述）。除非另有说明，所有比较均针对 DIFUSCO（Sun and Yang, 2023），使用相同的代码库和预训练检查点；LoRe 仅改变每步预算下的推理时路由。

本研究的主要贡献总结如下：

- •**概念形式化**：我们形式化了迭代图求解器的每步算子预算，建立了一个严格的框架，约束每个改进步骤内的计算和内存包络。
- •**LoRe 协议**：我们引入了 LoRe，一种无需训练的运行时包装器，将物理启发的团簇-浴场分解操作化，通过动态、状态相关的路由实现时域算子稀疏性。
- •**可审计核算**：我们建立了一个完全包含的、端到端的核算协议，为资源受限推理提供了透明的基准。
- •**实证验证**：我们证明，在匹配预算下，动态路由显著优于强静态替代方案。LoRe 将 MIS 上的可行推理范围扩展到超过基线内存溢出限制的 3 倍，并在 TSP 上实现了高达 15 倍的加速和 44 倍的内存降低。

最后，我们概述本文的组织结构：第 2 节回顾相关工作；第 3 节形式化每步预算和可审计核算协议，并用 LoRe 实例化预算接口；第 4 节报告实验；第 5 节总结。

## 2 相关工作

用于 CO 的神经求解器越来越多地将推理视为图上的迭代改进过程，涵盖了学习到的构造策略和改进启发式，以及动态求解器（它们在步骤间反复重新评估交互）（Bengio 等, 2021; Cappart 等, 2023; Mazyavkina 等, 2021; Vinyals 等, 2015; Bello 等, 2017; Kool 等, 2019; Nazari 等, 2018; Khalil 等, 2017）。这种范式的一个关键实际后果是，延迟和内存可能由重复的交互评估主导，而非单次前向传播，尤其是在图规模增长时。为了明确主要的效率杠杆，表 1 按步数、支持模式以及是否显式强制执行硬每步预算，总结了有代表性的工作线。

扩散风格的主干架构体现了这种权衡。在 CO 中，基于扩散的改进已在诸如 DIFUSCO 和 DiffUCO 等求解器中实例化，并进一步得到可扩展离散扩散采样器的支持（Sun and Yang, 2023; Sanokowski 等, 2024, 2025）。这些方法可以表现出较强的随时行为，但其逐步更新通常涉及对交互集的密集消息传递，使得逐步占用成为大规模部署中的约束限制。

LoRe 旨在无需重新训练的情况下在此步骤级别运行：它保持主干参数和改进步数固定，而是通过状态相关的路由，在严格的每步预算下分配昂贵的交互评估。密切相关的神经 CO 工作线将迭代改进与替代范式相结合——自适应解扩展（COExpander, Ma 等, 2025）、带逐步变量选择的结构化去噪（StruDiCO, Wang 等, 2025），以及作为搜索的测试时扩展生成（GenSCO, Li 等, 2025）——它们同样在步骤间重新评估交互；LoRe 的逐步预算与范式无关，我们在第 4 节中展示了向 T2TCO 和 COExpander 包装器的迁移。

另一个补充的效率方向侧重于降低总采样成本，包括训练-测试对齐、步骤压缩，以及更快的采样器或扩散模型蒸馏（Li 等, 2023, 2024; Ho 等, 2020; Song 等, 2021b, a; Lu 等, 2022; Salimans and Ho, 2022）。这些技术主要减少改进步骤的数量（或成本），因此与那些在每个步骤内部强制执行严格计算/内存包络的机制是正交的。LoRe 针对这种步骤内部约束，原则上可以与步骤减少或采样器加速方法组合使用。

另一条工作线通过限制交互结构（例如，候选图或固定掩码）来减少每步工作量。经典的 TSP 流程使用候选边和 Lin–Kernighan 风格邻域（Reinelt, 1991; Lin and Kernighan, 1973; Helsgaun, 2000），类似的固定支持也出现在学习求解器中。当高影响交互保持稳定时，静态支持是有效的，但在迭代改进中，交互的影响可能沿着轨迹变化；截断误差因此是状态相关的，如果关键交互被系统性地省略，误差可能会累积。这促使我们允许昂贵评估支持在预算显式下随步骤变化。

进一步相关的系列方法包括外循环改进范式，例如破坏-修复和大邻域搜索（LNS），其中选择一个邻域并作为单独的步骤进行重新优化（Shaw, 1998; Ropke and Pisinger, 2006; Pisinger and Ropke, 2010）。近期工作也探索了神经或扩散引导的变体，利用学习到的先验来提出邻域或引导改进过程（Hottung and Tierney, 2020; Feng 等, 2024）。

LoRe 采用不同的集成点：它不是用外循环包装改进，而是在求解器动力学的*每个改进步骤内部*对昂贵算子评估进行预算，通过状态相关的路由在严格的每步包络下分配交互评估。关键在于，这里的预算量是每步算子评估而不是邻域重新优化；因此，LoRe 不会引入额外的外部求解器，也不会改变主干参数或改进步数。

将 CO 问题映射到物理模型，特别是 Ising 模型和 Hopfield 网络，有悠久的历史，其中能量最小化对应于优化（Hopfield and Tank, 1985; Lucas, 2014）。图神经网络本身也通过图模型中的平均场推理的视角被分析（Dai 等, 2016）。

然而，大多数先前工作侧重于映射公式（例如，构造哈密顿量）。我们的工作从凝聚态物理的计算方法中汲取灵感——特别是团簇动力学平均场理论（C-DMFT）（Maier 等, 2005）。C-DMFT 不是求解完整系统或纯局部近似，而是将精确的局部团簇与平均场浴场耦合。LoRe 将这种“团簇-浴场”分解操作化为神经求解器的运行时路由协议。

**表 1：** 按效率杠杆的求解器定位。代表性参考文献：DIFUSCO（Sun and Yang, 2023），COExpander（Ma 等, 2025），T2TCO（Li 等, 2023），Fast-T2T（Li 等, 2024）。

| 工作/线 | 步数 | 支持 | 预算 | 永久性 |
|--------|------|------|------|--------|
| DIFUSCO | 固定 | 密集 | 否 | – |
| T2TCO / Fast-T2T | 较少 | 密集 | 否 | – |
| 静态空间稀疏化 | 固定 | 静态 | 隐式 | 是 |
| 外循环改进 / LNS | 变化 | 局部 | 隐式 | 变化 |
| COExpander | 变化 | 变化 | 不明确 | 变化 |
| LoRe (本文) | 固定 | 时变 | 是 | 否 |

## 3 LoRe：迭代图求解器的预算运行时路由

本节详述推理时协议。我们首先形式化迭代求解器动态