Interpreting Neural Combinatorial Optimization via Evolving Programmatic Bottlenecks¶

会议: NeurIPS 2026
arXiv: 2606.19741
OpenReview: https://openreview.net/forum?id=8fI7m5Dxno
领域: 优化/理论
关键词: 神经组合优化, 概念瓶颈模型, 程序化瓶颈, 混合梯度下降, 策略蒸馏

一句话总结¶

本文提出了首个面向神经组合优化（NCO）的演化程序化瓶颈（EPB）解释框架，通过将黑盒 NCO 策略蒸馏为动态调用的可执行代码启发式程序库，兼顾了高保真度决策解释与显著提升的大尺度分布外（OOD）泛化能力。

研究背景与动机¶

神经组合优化（NCO）通过深度自回归或图神经网络学习构造式启发策略，在旅行商问题（TSP）与容量受限车辆路径问题（CVRP）上取得了匹敌经典运筹算法的求解质量。然而，现有高性能 NCO 模型本质上属于深度“黑盒子”，无法解释模型在各决策步学到了何种操作规则、不同构造阶段策略如何转换、以及特定动作被选中的根本原因。这种决策透明度的匮乏，极大地限制了工业部署中的系统可信度与科学诊断。

在深度学习可解释性领域，概念瓶颈模型（CBM）通过将预测因式分解为“输入到预定义概念、概念到最终决策”的双阶段架构，提供了良好的透明度与模型干预能力。然而，将 CBM 直接迁移至 NCO 面临两大根本失配：其一是对象失配（Object Mismatch），标准 CBM 的概念多为静态、原子级的属性（如视觉中的颜色、纹理部件），而运筹优化中的决策单元是完整的决策算法；其二是场景失配（Setting Mismatch），标准 CBM 假设固定的静态映射，而 NCO 涉及多步序列决策，主导策略随解构造进程发生动态偏移。此外，组合优化中的算法概念空间包含海量规则与超参排列，人工无法事先穷举定义完备的概念词表。

针对上述挑战，本文放弃事先固定概念集合的传统假设，转而利用大语言模型（LLM）自主探索并演化生成程序化概念。核心 idea：将黑盒 NCO 决策策略蒸馏为由 LLM 自主演化的可执行启发式程序库，在每个时间步通过以动作分布为键的轻量路由网络实现动态加权组合，并采用“混合文本-数值梯度（Block I）+ 动态容量增删（Block II）”的双模块闭环优化。

方法详解¶

整体框架¶

EPB 采用学生-教师蒸馏框架。给定任意黑盒教师 NCO 策略 $\pi_T$，学生策略 $\pi_S$ 经过一个由 $M$ 个可执行启发式程序组成的程序库 $\mathcal{B} = \{(c_m, d_m)\}_{m=1}^M$（其中 $c_m$ 为 Python 代码，$d_m$ 为策略自然语言描述）。在每个序列构造步 $s$：首先各启发式程序执行获得各自动作概率分布 $V_m(s)$；然后基于输出条件动态路由（OCDR）模块，利用停止梯度机制计算各程序的动态选择权重 $w_m(s)$；最后通过混合加权输出预测分布 $\pi_S(\cdot \mid s)$。

为了解决包含离散符号代码更新、路由网络连续参数优化以及离散程序库容量搜索的复杂异构优化难题，EPB 提出了双模块交替优化算法（Two-Block Training）：内循环 Block I 在固定容量下通过混合梯度联合更新路由网络（SGD）与代码/描述（TextGrad）；外循环 Block II 在性能收敛停滞时动态扩展（针对未覆盖失效模式的 Add）或剪枝冗余启发式（Drop）。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["当前决策状态 s<br/>（候选子图/起点/当前节点/容量）"] --> B["启发式程序库执行<br/>（输出各动作分布 V_m）"]
    B --> C["输出条件动态路由 OCDR<br/>（停止梯度解耦计算权重 w_m）"]
    C --> D["混合动作预测 π_S<br/>（加权聚合 ∑ w_m V_m）"]
    D --> E["蒸馏损失计算 ℓ_s<br/>（KL 散度相对教师 π_T）"]
    E --> F["混合梯度反向传播<br/>（SGD 更新路由网络 θ + 混合梯度归因）"]
    F --> G["双层符号优化与容量演化<br/>（TextGrad 修正代码/描述 + 故障新增/冗余剪枝）"]
    G --> B

关键设计¶

1. 输出条件动态路由：基于动作分布键匹配的解耦注意力 标准注意力路由若引入独立的启发式嵌入向量，在程序库动态增删时会导致参数结构变动和冷启动不稳定。EPB 设计了输出条件动态路由（OCDR），查询向量 $Q(s; \theta)$ 编码全局与局部状态，而每个候选程序 $m$ 的键向量 $K_m$ 直接取为其推荐动作在状态节点嵌入下的期望值： $$K_m(s; \theta, \operatorname{sg}(V_m)) = \sum_{n} \operatorname{sg}(V_m(s, n)) \cdot h(s, n; \theta)$$ 此处对 $V_m(s)$ 施加停止梯度算子 $\operatorname{sg}(\cdot)$ 是至关重要的设计：它在保持前向路由依据各程序实际推荐动作的同时，完全截断了反向传播中经过路由键回传的间接梯度，使得反向归因信号仅反映程序通过混合输出路径产生的直接影响。

2. 混合文本-数值梯度下降：误差归因驱动的跨模态闭环优化 在固定容量下，EPB 最小化学生与教师之间的状态级 KL 散度 $\ell_s = \operatorname{KL}(\pi_T(\cdot \mid s) \parallel \pi_S(\cdot \mid s))$。对参数求导后，梯度自然解耦为更新连续路由参数的数值梯度与指导符号代码更新的归因信号： $$\nabla_{\theta}\ell_s = \sum_{m=1}^M \langle r_s, V_m(s) \rangle \nabla_{\theta} w_m(s; \theta, \operatorname{sg}(V)), \quad g_m^{\mathrm{out}}(s) = w_m(s) \cdot r_s$$ 其中 $r_s = \nabla_{\pi_S} \ell_s$ 为混合误差向量。由于单一范数标量化无法区分程序是否真正决策错误，EPB 设计了精细的失效归因分数： $$\mathrm{score}_m(s) = w_m(s) \cdot \mathbb{I}\left[\arg\max_{a} V_m(s, a) \neq n^\star(s)\right] \cdot \operatorname{KL}\left(\pi_T(\cdot \mid s) \parallel V_m(s)\right)$$ 该分数在程序被赋予高权重且顶层动作与教师不一致时急剧上升。系统筛选出得分最高的 Top-$K$ 失效样本送入 TextGrad，先在局部修正代码实现（Phase 1），若验证集无法改善则上升为策略级自然语言描述修正并重新生成代码（Phase 2），实现了双层符号优化。

3. 动态容量演化：故障定向生成与边际冗余剪枝 预先设定固定的程序库容量 $M$ 极易陷入表达力匮乏或策略冗余。EPB 引入由训练收敛停滞（plateau）触发的动态增删机制。在新增算子（Add）中，收集当前程序库中所有程序均预测失败的疑难步，交由 LLM 聚类为 $K$ 类归因并提出针对性的新启发式候选，在独立验证集上按边际覆盖增益贪心地接纳入库；在删除算子（Drop）中，采用 Leave-One-Out 贪心剪枝，评估剔除单项程序后验证损失的恶化程度，在容差范围内剔除被其他程序覆盖的冗余策略，保持程序库紧凑易读。

损失函数 / 训练策略¶

训练采用蒸馏目标，对每一决策状态最小化教师模型与学生混合策略之间的 KL 散度： $$\mathcal{L}(\theta, \mathcal{B}) = \mathbb{E}_{s \sim \mathcal{D}} \left[ \operatorname{KL}\left(\pi_T(\cdot \mid s) \parallel \pi_S(\cdot \mid s; \theta, \mathcal{B})\right) \right]$$ 优化采用不对称更新周期：路由网络参数 $\theta$ 在每个批次通过 Adam/SGD 频繁更新，而程序库 $\mathcal{B}$ 的 TextGrad 步每 100~200 个批次触发一次，防止频繁重写代码导致路由优化剧烈震荡。

实验关键数据¶

主实验¶

在 TSP 与 CVRP 上分别蒸馏经典自回归模型 POMO 与强泛化模型 LEHD。在贪婪解码（Greedy）与多起点/重构搜索（Search）下，学生模型均高度复刻了黑盒教师的性能，性能差距缩减至可忽略的水平。

教师模型	问题	规模	贪婪解码: 教师	贪婪解码: 学生	贪婪差距 (%)	搜索策略: 教师	搜索策略: 学生	搜索差距 (%)
POMO	TSP	50	5.712	5.884	+3.02%	5.696	5.698	+0.03%
POMO	TSP	100	7.834	8.130	+3.79%	7.796	7.803	+0.10%
POMO	CVRP	50	11.536	11.655	+1.03%	10.793	10.807	+0.13%
POMO	CVRP	100	16.188	16.826	+3.94%	15.882	16.080	+1.25%
LEHD	TSP	100	7.758	7.962	+2.63%	7.708	7.739	+0.40%
LEHD	CVRP	100	16.282	16.857	+3.60%	15.969	16.314	+2.16%

分布外泛化实验（OOD Generalization）¶

在未见过的超大尺度问题（Scale 500）上进行零样本迁移测试，结果展现了程序化瓶颈令人惊叹的归纳偏置效果：蒸馏出的程序化学生模型大幅击败了其黑盒教师！

实验配置	贪婪解码: 教师	贪婪解码: 学生	贪婪提升 (%)	搜索策略: 教师	搜索策略: 学生	搜索提升 (%)
POMO-TSP-500	22.180	18.852	-15.01%	20.464	17.532	-14.32%
POMO-CVRP-500	50.600	43.579	-13.57%	48.502	41.030	-15.22%
LEHD-TSP-50	5.761	5.919	+2.74%	5.728	5.729	+0.03%
LEHD-TSP-500	16.820	17.628	+4.80%	16.586	17.138	+3.33%

关键发现¶

黑盒决策本质的跨求解器差异：通过分析蒸馏出的启发式程序库，论文揭示了一个此前未被发现的本质差异：POMO 的非最近邻决策主要由阶段感知策略（Phase-adaptive）驱动（依赖游走进度、剩余未访问城市数，前期倾向外凸包探索、后期强制闭环）；而 LEHD 的决策则压倒性地由局部几何与前瞻修正（Geometry-aware & Lookahead）驱动（依赖局部插入代价、角向扫描、后向口袋清理）。这完满解释了为何 LEHD 在跨尺度上拥有更好的泛化性——局部几何规则比阶段硬阈值更易跨尺度迁移。
CVRP 阶段演化规律：在 CVRP 构造过程中，策略演化呈现清晰三阶段：在路径初期车辆满载时，主导策略为扇区探索与远距离高需求客户匹配；在路径中期，转变为节约算法（Clarke-Wright Savings）与紧凑距离/容量匹配；在剩余容量耗尽的末期，策略无缝切换为回程沿途收集与低载荷强制返仓。
超越忠实度的归纳偏置反哺：在 POMO-500 的 OOD 测试中，学生路径长度比教师缩短了 14%~15%。这表明显式的程序化瓶颈成功过滤了神经网络在固定尺寸训练中过拟合的高频伪特征，提炼出可跨尺度复用的纯粹算法逻辑。

亮点与洞察¶

从静态属性到可执行代码的范式飞跃：将概念瓶颈拓展至连续序列决策任务，打破了传统 CBM 依赖人工标注静态属性字典的死胡同，把解释单元重构为人类完全可阅读、可调试的纯 Python 代码。
停止梯度实现归因解耦的设计巧思：在 OCDR 中引入 $\operatorname{sg}(V_m)$，巧妙防止了由于键向量计算引起的反向梯度泄漏，使得针对程序的文本梯度仅纯粹受混合输出路径的贡献大小与正负驱动。
解释工具作为通用泛化提升器：展示了“可解释性”不仅用于信任审计，还能作为模型正则化工具消除黑盒过拟合噪声，逆向反哺基础算法的泛化性能。

局限与展望¶

路由网络仍保留轻量黑盒：当前架构中权重的决策是由带参数的注意力网络给出的，尽管程序本身透明，但何时选用哪个程序的宏观路由规则仍属于软权重分配。未来若能将路由网络同样符号化或规则化，将实现彻底的白盒化。
代理蒸馏的保真度上界：学生模型本质上是在分布层面的拟合，单步动作与教师虽有约 80% 的一致率，但在极端病态样例下可能存在长尾分歧。
向复杂约束拓展的探索空间：目前主要评估了 TSP 与标准 CVRP，未来可进一步拓展至带有硬时间窗（VRPTW）、异构车队及拾起投递（PDP）等复杂工业场景中。

评分¶

新颖性: ⭐⭐⭐⭐⭐（首创将概念瓶颈模型与程序合成引入神经组合优化策略解释）
实验充分度: ⭐⭐⭐⭐⭐（涵盖 TSP/CVRP 50/100/500，全面的教师对比、OOD 测试与消融分析）
写作质量: ⭐⭐⭐⭐⭐（概念界定清晰，公式推导严谨，图表呈现与个案分析极具说服力）
价值: ⭐⭐⭐⭐⭐（为序列强化学习与运筹决策黑盒的可解释性与泛化增强开辟了全新路径）