🤖 machine learning

Rethinking Efficiency in Neural Combinatorial Optimization: Batched Preference Optimization with Mamba

本文介绍了 ECO，这是一个高效的神经组合优化框架，它结合了内存高效的 Mamba 骨干网络与一个在训练期间由局部搜索引导的解耦、批处理直接偏好优化流水线，从而在 TSP 和 CVRP 任务上实现了卓越的性能和硬件利用率。

原作者： Zhenxing Xu, Zeyuan Ma, Weidong Bao, Yan Zheng, Chongshuang Hu, Ji Wang, Zhiguang Cao

发布于 2026-07-21

📖 1 分钟阅读☕ 轻松阅读

原作者： Zhenxing Xu, Zeyuan Ma, Weidong Bao, Yan Zheng, Chongshuang Hu, Ji Wang, Zhiguang Cao

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你是一位正在为数千名宾客组织一场盛大宴会的顶级大厨。你有一份食材清单（即“节点”）和一套规则：你必须恰好访问每种食材一次，且你的推车容量有限，同时要尽可能快地将所有东西运回厨房。这就是组合优化（Combinatorial Optimization）的世界。几十年来，人类一直使用巧妙的、手工制作的“食谱”（算法）来解决这些难题，但这些方法速度缓慢，并且每遇到一个新的宴会场景，都需要人类专家进行调整。

最近，科学家们开始教计算机通过使用神经网络来亲自学习这些食谱。把这些网络想象成渴望学习的学徒，他们通过观察成千上万个示例来尝试预测下一步的最佳动作。然而，这里有一个陷阱：训练这些学徒的成本极其高昂。这就像是要求他们在学会一个新技巧之前，先做出一整顿饭，尝一下，然后扔掉，再重新开始，如此循环数百万次。这个过程既缓慢又耗费内存，以至于在学徒变聪明之前，计算机往往就会崩溃。研究人员面临的一个重大问题是：我们能否教会这些 AI 大厨变得同样出色，但速度更快、且更不浪费资源？

这篇论文介绍了一个名为 ECO（高效组合优化，Efficient Combinatorial Optimization）的新框架，它给出了肯定的回答。作者提出了一个两部分的“魔术技巧”来提速而不损失质量。首先，他们改变了学习风格。与其让学徒做一顿饭、尝一下、然后再学习一个动作这种混乱的循环，ECO 让学徒一次性做出一整批饭菜，进行比较，然后一次性从最好的那些中学习。他们称之为“批处理偏好优化”（Batched Preference Optimization）。这就像老师向学生展示十篇不同的文章，指出其中最好的一篇和最差的一篇，然后说：“看清它们的区别了吗？从中学习，”而不是改一篇文章，等学生重写，然后再改下一篇。

其次，他们升级了学徒的大脑。大多数 AI 模型使用“Transformer”架构，这就像一个图书管理员，必须读完书架上的每一本书才能找到两页特定内容之间的联系。如果书架变得太长（例如有数千种食材），图书管理员就会应接不暇并耗尽内存。ECO 将其更换为 Mamba 骨干网络。想象一下，Mamba 就像一个超级高效的扫描仪，它以平滑、连续的流式方式阅读书架，只记住它需要追踪的信息。这使得系统能够处理大规模宴会（数千个节点）而不会导致计算机崩溃。

作者在两个经典问题上测试了该方法：旅行商问题（Traveling Salesperson Problem，寻找访问许多城市的最短路径）和车辆路径问题（Vehicle Routing Problem，在有限的卡车空间内向许多客户配送包裹）。他们发现 ECO 的速度惊人。在一个拥有 5,000 个城市的题目中，ECO 仅用 2.5 分钟就完成了测试集的求解，而其他神经方法花费的时间要长得多，传统的精确求解器则需要数小时。至关重要的是，作者证明了 ECO 并没有通过在最终测试中使用“局部搜索”（一种快速修正手段）来作弊；AI 是在训练过程中自己学会了这些技巧。

该论文表明，通过将这种全新的“批处理”学习风格与高效的 Mamba 大脑相结合，我们可以训练 AI 以比以前更快的方式解决巨大的、复杂的路径规划问题，从而节省时间并减少计算资源。结果显示，ECO 与现有的最佳 AI 方法相比具有竞争力，并且在问题规模变得非常大时往往表现更好。不过，作者也谨慎地指出，虽然“大脑”（编码器）变得更加高效了，但选择下一步动作的最终步骤仍然需要一些繁重的计算工作，因此整个过程并非完全是线性提升的，但相比旧方法已是巨大的进步。

技术摘要：重新思考神经组合优化中的效率：基于 Mamba 的批量偏好优化

1. 问题陈述

神经组合优化（NCO）已从早期的指针网络（Pointer Networks）演进到基于 Transformer 的架构（如 AM、POMO）以及生成流网络（GFlowNet）。尽管这些方法提高了求解质量，但它们面临着显著的效率瓶颈，特别是在可扩展性和训练收敛速度方面。

本文识别了现有 NCO 工作中两个主要的低效来源：

学习范式： 传统的在线强化学习（RL）将轨迹生成（rollouts）与参数更新紧密耦合。这种“先采样后更新”的循环未能充分利用 GPU 的并行性，并迫使每一次优化步骤都依赖于新鲜的自回归生成，从而导致收敛缓慢且硬件成本高昂。
神经架构： 最先进的 NCO 模型严重依赖 Transformer 架构。尽管有 FlashAttention 等优化技术，其底层的 Token-to-Token 交互在序列长度上仍保持二次方复杂度（ $O(N^2)$ ）。这导致在大规模路由实例（例如具有数千个节点的 TSP）上出现内存爆炸和延迟问题，限制了 NCO 在大规模问题上的实际部署。

核心问题在于：如何在不牺牲求解质量的前提下提高 NCO 的效率？

2. 方法论：ECO 框架

作者提出了 ECO，这是一个以效率为导向的框架，它将轨迹生成与梯度更新解耦，并将 Transformer 主干替换为基于 Mamba 的架构。

A. 批量偏好优化范式

ECO 引入了一种两阶段训练工作流，将严格的在线 RL 转向“批量或更新中的离线”范式：

第一阶段：监督预热（SFT）： 通过对高质量预计算解（由 LKH-3 或启发式算法生成）进行行为克隆来初始化策略。这提供了对路由约束和局部最优性的基本理解。
第二阶段：迭代直接偏好优化（DPO）： 与 PPO 中训练独立的价值函数（Critic）不同，ECO 使用 DPO 直接根据成对的偏好进行优化。
- 工作流： 当前策略生成一批候选解。根据路径长度构建偏好对（胜者/败者）。
- 参考模型： 参考模型（ $\pi_{ref}$ ）每隔 $T$ 步更新一次，以锚定 KL 散度，从而稳定迭代改进过程。
- LS 增强引导（LS-Augmented Bootstrapping）： 为了防止随着策略改进而导致的奖励边际变窄所引起的梯度消失问题，在训练期间对模型生成的解应用轻量级的局部搜索（LS）算子（如 2-opt, 3-opt）。经过精炼的解成为“胜者”，而原始输出成为“败者”。至关重要的是，局部搜索在推理阶段绝不使用；它仅用于构建更强的训练信号，并将其蒸馏到神经策略中。

B. 混合 Mamba 架构

为了解决 Transformer 的二次方内存缩放问题，ECO 采用了定制的 Mamba（状态空间模型）架构：

循环 Mamba 编码器： 使用堆叠的 Mamba 层（S6 设置）来处理节点序列。与 Transformer 不同，Mamba 使用线性内存序列建模。为了处理 Mamba 的非置换等变性，输入在编码前进行了规范化处理（例如，通过 Morton/Z-order 编码排序）。
S4 解码器： 使用 S4 风格的层进行训练时的并行教师强制（teacher-forced）计算，并在推理期间进行高效的循环状态更新。
自回归评分： 该框架保留了标准的自回归候选评分步骤（类似于指针式的兼容性评分）。作者明确指出，虽然编码器和循环状态更新变为线性，但在最坏情况下，动作评分仍是二次方的（ $O(N^2)$ ），因为需要将当前状态与所有可行候选进行比较。然而，该架构显著降低了编码器内存压力和循环状态成本。

3. 主要贡献

本文概述了三个主要贡献：

首个基于 Mamba 的 NCO 求解器： 作者引入了第一个基于 Mamba 的 NCO 求解器，提供了复杂度分解，证明了 Mamba 降低了编码器内存缩放和循环解码状态的成本，尽管朴素的自回归候选评分仍为二次方复杂度。
面向效率的框架： 创新性地整合了定制的 Mamba 架构、两阶段批量偏好优化流水线（SFT + 迭代 DPO）以及局部搜索引导的引导策略，以稳定训练并放大偏好边际。
全面的实证分析： 在 TSP 和 CVRP 上进行了广泛的案例研究，证明 ECO 在实现最佳或具有竞争力的神经性能的同时，在大型实例上取得了显著的效率提升。分析包括复杂度分解、置换敏感性测试以及针对每个设计组件的消融实验。

4. 实验结果

实验在单块 NVIDIA A800 GPU 上针对 TSP ( $N \in \{200, 500, 1000, 5000\}$ ) 和 CVRP ( $N \in \{100, 200, 500, 1000\}$ ) 进行。

求解质量： 在大多数规模下，ECO 在神经基准模型（AM, POMO, LEHD, GFlowNet-HBG）中达到了最佳或具有竞争力的结果。
- 在 TSP5000 上，ECO 的差距（gap）为 5.49%，而基于 Transformer 的基准模型（AM, POMO）则表现出严重的性能退化，差距超过 70-89%。
- 在 CVRP1000 上，ECO 实现了 2.87% 的差距，优于或匹配了其他神经方法。
可扩展性与内存：
- 内存： 由于二次方注意力内存，Transformer 基准模型在 $N \approx 7000$ 时会在 80GB GPU 上触发显存溢出（OOM）。ECO 保持了近乎线性的内存增长，即使在 $N=10,000$ 时也能保持在限制内（约 40GB）。
- 吞吐量： 与 Transformer 相比，ECO 在长序列上维持了显著更高的推理吞吐量，因为它可以在不触及内存限制的情况下使用更大的 Batch Size。
训练效率：
- ECO 的收敛速度比标准的在线基准模型快得多。
- 对比使用相同 Mamba 主干的 DPO 与 PPO，ECO 达到了相当的质量（TSP1000 上分别为 4.84% 和 4.88% 的差距），但将训练时间从 34.5 小时缩短至 10.2 小时。
组件分析：
- LS 引导（LS Bootstrapping）： 去除 LS 引导会将 TSP1000 的差距从 4.84% 增加到 9.55%，证实了 LS 提供了更强的训练信号并被蒸馏到了策略中。
- SFT 预热： 不进行 SFT 训练会导致不稳定和发散，证实了需要一个胜任的初始策略。
- 架构： 在相同的 DPO 目标下，用 Transformer 替换 Mamba 会导致差距增大（5.47% vs 4.84%）且训练时间增加，证明了架构优势是独立于优化目标的。

5. 重要性与主张

本文声称，ECO 通过解决长期以来被忽视的“效率”差距，代表了迈向可扩展、实用型神经路由求解器的重要一步。

对线性度的适度主张： 作者明确指出，ECO 并没有使整个构造性推理过程变为线性。其收益是具体的：它降低了编码器内存缩放和循环状态成本，并通过 Scan Kernel 和批量更新提高了硬件利用率。最后的动作评分步骤仍是二次方的。
训练 vs. 推理： 一个关键发现是，局部搜索是严格的训练时机制。ECO 相较于消融版本的性能提升归功于从 LS 引导信号中学习到的改进的网络参数，而非推理时的后处理。
硬件感知： 该工作表明，将硬件感知的架构（Mamba）与高效的训练范式（批量 DPO）相结合，可以使 NCO 模型扩展到数千个节点的规模，并在消费级或单 GPU 硬件上运行，而传统的基于注意力的模型在这些场景下会因内存限制而失效。

总之，ECO 通过将线性内存主干与稳定的批量偏好学习流水线相结合，提供了一个实现可扩展神经路由的强大方向，在获得极具竞争力的求解质量的同时，拥有显著更好的内存和吞吐量特性。