Probing Neural Combinatorial Optimization Models¶
会议: NeurIPS 2025
arXiv: 2510.22131
代码: GitHub
领域: 优化
关键词: 神经组合优化, 可解释性, 探针分析, 嵌入表示, 泛化能力
一句话总结¶
首次系统性地将探针(probing)方法引入神经组合优化(NCO)模型的研究，提出CS-Probing工具来分析模型表示中编码的决策知识、归纳偏置和泛化机制，并发现关键嵌入维度可用于提升模型泛化性能。
研究背景与动机¶
神经组合优化(NCO)方法在TSP、CVRP等经典组合优化问题上取得了接近甚至超越专用启发式算法的效果，但这些基于Transformer的深度模型内部学到了什么知识、如何做出决策，仍然是一个黑箱。
核心痛点：NCO模型的不可解释性阻碍了学术研究和实际部署。研究者和利益相关方需要深入理解模型的内部机制，包括：(1) 模型学到了什么决策相关知识？(2) 模型如何学习和利用这些知识？
已有工作的不足：传统可解释性方法如梯度归因、可视化和神经元消融各有局限。梯度归因只能显示输出对输入的敏感性，不能揭示知识在隐层表示中的编码方式；神经元消融缺乏统计严谨性。
本文切入角度：借鉴NLP领域成功的探针(probing)方法论——如果一个简单的线性模型能从模型嵌入中准确预测某种知识，说明该知识被模型编码在其表示中。但组合优化问题不像NLP有天然的子任务，需要专门设计探针任务。同时提出CS-Probing，通过分析线性探针系数的绝对值和统计显著性来获取更深层的洞察。
方法详解¶
整体框架¶
- 设计针对组合优化问题的分层探针任务（低层级 + 高层级）
- 用线性探针模型检验NCO嵌入是否编码了相应知识
- 通过CS-Probing分析具体哪些嵌入维度有重要贡献
研究了三个代表性的基于Transformer的NCO模型：AM (Attention Model)、POMO和LEHD。
关键设计¶
-
探针任务设计：针对TSP问题设计了两个层次的任务——
- Task 1（低层级）：能否感知欧几里得距离？用线性探针从嵌入中回归节点间的欧几里得距离，\(R^2\) 值衡量效果
- Task 2（高层级）：能否避免贪心短视？判断模型是否学到了不简单选最近节点的能力，以AUC衡量
- Task 3/4（CVRP）：理解约束关系（需求加和性）和路由归属信息
核心发现：初始嵌入（线性投影后）无法线性捕获欧几里得距离（\(R^2 \approx 0\)），但经过注意力层后 \(R^2\) 显著提升，LEHD达到0.94。所有模型在Task 2上AUC > 0.8，说明学到了全局最优解的非短视知识。
- CS-Probing（系数显著性探针）：核心创新。分析线性探针模型中每个嵌入维度的系数绝对值和统计显著性（p值），用Benjamini-Hochberg过程控制FDR在0.05。这使得分析从"嵌入是否编码了某知识"深化为"哪些维度编码了什么知识"。
关键发现：LEHD（性能最好的模型）的嵌入呈现明显的稀疏激活模式——少于20个维度有强激活（绝对值达数十），而AM和POMO的激活更分散（绝对值 < 4）。LEHD的候选节点嵌入相比当前节点嵌入有更多统计显著维度。
- 泛化机制分析：通过CS-Probing发现泛化能力与嵌入维度复用率直接相关。在模型从20节点泛化到100节点时，LEHD始终使用相同的Top-2维度（第31和第69维用于距离感知，第31和第97维用于避免短视），而AM和POMO的关键维度在泛化时发生变化。这提供了"泛化能力来自一致的知识编码"的直接证据。
损失函数 / 训练策略¶
探针模型使用线性回归（Task 1）或线性分类（Task 2），冻结NCO模型参数只训练探针。分析的NCO模型按其原始论文的方法训练（RL或SL）。基于CS-Probing的洞察，对LEHD添加L1正则化 \(\lambda \|\mathbf{h}\|_1\) 来促进嵌入稀疏性以提升泛化。
实验关键数据¶
主实验（探针性能）¶
| 探针输入 | Task 1 (\(R^2\)) | Task 2 (AUC) | 说明 |
|---|---|---|---|
| AM-Init | -0.0003 | 0.49 | 初始嵌入无法捕获信息 |
| AM-Enc-l3 (w/ ints) | 0.9282 | 0.83 | 编码器输出含丰富知识 |
| POMO-Enc-l6 (w/ ints) | 0.7917 | 0.86 | 类似模式 |
| LEHD-Dec-l6 (w/o ints) | 0.9418 | 0.86 | 无需交互项即有高\(R^2\) |
| LEHD-Dec-l6 (w/ ints) | 0.9415 | 0.86 | LEHD表示最丰富 |
消融实验（关键维度验证）¶
| 配置 | TSP100最优性间隙 | 说明 |
|---|---|---|
| LEHD原版（全128维） | 0.57% | 基线 |
| 仅保留维度31, 97 | 0.65% | 两个维度即可近乎等效 |
| 仅保留维度32, 97 | 0.75% | 换一个维度性能下降 |
| 仅保留维度21, 123 | 183.80% | 随机维度完全失效 |
| 清零维度31, 97 | 60.43% | 关键维度被移除→性能崩溃 |
| 清零维度98 | 0.59% | 非关键维度移除无影响 |
| 清零维度98, 126 | 0.62% | 高激活但非关键维度也不重要 |
| 正则化强度 λ | TSP100 | TSP200(泛化) | TSP1000(泛化) |
|---|---|---|---|
| 0 (原始) | 0.57% | 0.86% | 3.17% |
| 1e-6 | 0.58% | 0.88% | 2.87% |
| 1e-4 | 0.57% | 0.73% | 2.97% |
关键发现¶
- 分层知识编码：浅层学习空间关系（距离感知），深层发展策略推理（避免短视）
- 训练动力学：AM和POMO在训练初期快速发展避免短视能力；LEHD从训练一开始就具备该能力
- 仅2个维度足以近乎重现完整模型性能——这意味着NCO模型的有效表示空间极度压缩
- 基于探针洞察的简单正则化可提升泛化：TSP1000上间隙从3.17%降至2.87%
亮点与洞察¶
- 首创性：首次系统性地将探针方法引入NCO领域，填补了NCO可解释性研究的空白
- CS-Probing工具的通用性：不仅适用于Transformer模型，还可扩展到GNN（JSSP问题）和扩散模型（DIFUSCO）
- "2维足够"的发现令人震惊：128维嵌入中仅2维就包含了几乎全部决策信息，暗示NCO模型可能存在巨大的表示冗余，为模型压缩和蒸馏提供了理论依据
- 泛化机制的直接证据：不同于以往"观察性能差异"的间接分析，CS-Probing通过维度复用率提供了泛化成功/失败的结构性解释
局限与展望¶
- 目前主要聚焦于TSP和CVRP，对更复杂问题（调度、装箱等）的探针任务设计有待拓展
- 正则化实验虽然有效但较初步，更系统的基于探针洞察的模型改进值得深入
- CS-Probing依赖线性可分性假设，可能遗漏了非线性编码的知识
- 仅分析了三种NCO模型，对更新的架构（如Mamba、状态空间模型）的适用性有待验证
相关工作与启发¶
- 方法论上受NLP探针研究启发，但在任务设计上做了组合优化特定的创新
- 与NCO泛化研究（如LEHD的原始论文声称的"动态学习策略"）形成呼应，CS-Probing提供了该声明的定量验证
- 启发方向：探针分析可成为NCO社区的标准评估工具，类似于NLP中的各种Benchmark
评分¶
- 新颖性: ⭐⭐⭐⭐⭐ 首次将探针引入NCO领域，CS-Probing方法有原创性
- 实验充分度: ⭐⭐⭐⭐⭐ 实验极为详尽，包含多种模型、任务、消融和跨分布泛化
- 写作质量: ⭐⭐⭐⭐ 结构清晰，但部分内容在附录中需要跳转
- 价值: ⭐⭐⭐⭐⭐ 对NCO社区有范式级别的贡献，开创了NCO可解释性的新方向
相关论文¶
- [NeurIPS 2025] Rethinking Neural Combinatorial Optimization for Vehicle Routing Problems with Different Constraint Tightness Degrees
- [ICLR 2026] RRNCO: Towards Real-World Routing with Neural Combinatorial Optimization
- [NeurIPS 2025] Evaluating LLMs for Combinatorial Optimization: One-Phase and Two-Phase Heuristics for 2D Bin-Packing
- [NeurIPS 2025] Oracle-Efficient Combinatorial Semi-Bandits
- [NeurIPS 2025] FedRTS: Federated Robust Pruning via Combinatorial Thompson Sampling