Convex Compositional Reasoning Models

会议: NeurIPS 2026
arXiv: 2605.23395
领域: Reasoning
关键词: 组合推理, 能量模型, 输入凸神经网络, 凸松弛, 投影一阶优化

一句话总结

针对组合能量模型在因子求和时因非凸能量曲面容易陷入伪局部极小值的根本缺陷，本文提出 CCEM 框架，将每个子约束因子参数化为输入凸神经网络，在紧凸松弛空间上构建全局凸能量景观，利用确定性投影一阶优化替代扩散采样，实现了无须重新训练向更大规模组合推理问题的跨尺度零样本迁移。

研究背景与动机

组合推理是组合优化与逻辑约束求解（如 N-Queens、图着色、SAT 问题）的核心范式。这类问题天然具备模块化结构，候选解的有效性由行、列、对角线、边着色或逻辑子句等局部约束共同决定。现有的组合能量模型（Compositional EBMs）正是利用这一特性，通过在小规模子问题上学习局部能量因子，并在推理阶段将所有因子的能量进行加权求和，从而原则上能够在不重新训练的情况下泛化到更大规模的问题实例上。

然而，组合本身往往带来了严重的优化阻碍。当局部因子由无约束的常规神经网络（如标准 MLP）参数化时，即便每个局部因子在单独考察时表现良好，它们的非负线性组合在全局非凸曲面上依然会诱导出大量稳定且次优的伪局部极小值（Spurious Local Minima）。随着问题规模扩大与约束数量增加，能量曲面变得极度崎岖坎坷。以往的工作（如结合 Parallel Energy Minimization 与扩散去噪采样的 EBM 架构）试图通过维持大量粒子群、注入高斯扰动与长时间退火采样来跨越能量壁垒，但这仅仅是在治疗非凸景观带来的表面症状，而非从根源上消除能量曲面的非凸病态。

本文的核心洞见在于：组合推理的优化困境并非源于组合机制本身，而是由局部能量因子的参数化几何形态决定的。如果每个局部因子在决策变量上严格保凸，且因子组合权重非负，那么凸性在求和操作下封闭，整个松弛能量景观在凸可行域上将严格保持全局凸性，从而彻底排除任何非全局的局部极小值。核心 idea：利用部分输入凸神经网络（PICNN）参数化局部约束因子并在紧凸松弛流形上求和，将组合推理转化为全局凸规划问题，通过确定性投影一阶优化直接求得松弛全局最优解，并结合解码感知裕度条件保证离散解的正确恢复。

方法详解

整体框架

CCEM 针对组合推理问题的求解流程分为离线因子对比预训练、展开投影求解器端到端微调以及测试期投影一阶确定性推理三个阶段。在离线阶段，PICNN 局部因子仅在极小规模的局部子结构上通过对比损失建立有效凸盆地；在全局组合阶段，模型根据目标问题结构将对应局部因子的能量在预定义的紧凸松弛空间（如 Birkhoff 双随机多面体或单纯形）上进行加权求和；在推理阶段，利用投影 Adam 或投影梯度下降（PGD）在凸集上进行确定性迭代优化，最终通过任务特定的确定性解码器（如行内 argmax 或阈值化）恢复离散有效解。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["输入组合问题实例<br/>定义约束结构与紧凸松弛集合"] --> B["部分输入凸神经网络因子<br/>双路网络保决策变量凸性"]
    B --> C["因子非负加权求和<br/>构建全局严格凸松弛能量景观"]
    C --> D["展开投影一阶优化器<br/>在紧凸多面体上确定性迭代"]
    D --> E["解码感知裕度投影解码<br/>离散化输出全局有效解"]

关键设计

1. 部分输入凸神经网络因子：隔离上下文非凸性与决策变量凸性

以往无约束神经网络使得全局求和后的能量函数呈现多峰非凸形态，导致梯度下降陷入局部次优陷阱。为了在保持对问题上下文（如节点邻接关系、子句文字极性）灵活表征的同时，确保能量对松弛决策变量的绝对凸性，CCEM 采用部分输入凸神经网络（PICNN）架构：

\[u_{\ell+1} = \sigma\bigl(\widetilde{W}^{u}_{\ell}u_{\ell}+\widetilde{b}^{u}_{\ell}\bigr)\]

\[z_{\ell+1} = \sigma\Bigl(W^{z}_{\ell}\bigl(z_{\ell}\odot\mathrm{softplus}(W^{zu}_{\ell}u_{\ell})\bigr)+W^{y}_{\ell}\bigl(y\odot W^{yu}_{\ell}u_{\ell}\bigr)+W^{u}_{\ell}u_{\ell}+b_{\ell}\Bigr)\]

其中上下文向量经过非凸路径 \(u_\ell\) 提取高阶语义并充当门控权重，而决策变量路径 \(z_\ell\) 的前向连接矩阵被显式约束为非负矩阵 \(W_\ell^z = \mathrm{softplus}(\widetilde{W}_\ell^z)\)，激活函数 \(\sigma\) 选取非降凸函数（如 softplus 或 ReLU）。这种架构确保每个局部因子 \(f_\theta(y; c)\) 关于决策变量 \(y\) 处处保持凸性，为后续因子的非负保凸求和奠定了数学基础。

2. 紧凸松弛流形上的全局无陷阱能量组合

对于由 \(K\) 个局部约束组合而成的大规模问题实例，全局能量定义为局部因子的非负加权和：

\[E_\theta(x, y) = \sum_{k=1}^K w_k f_\theta(y_{\mathrm{sc}(k)}; c_k), \quad w_k \geq 0\]

因为凸函数的非负线性组合依然是凸函数，该目标函数在紧凸集合 \(\mathcal{Y}\) 上严格不存在非全局的假极小值（Non-global Local Minima）。与以往方法在全欧氏空间 \(\mathbb{R}^n\) 中运行扩散随机扰动不同，CCEM 直接将可行域松弛在最小紧凸集内：对于 N-Queens 问题使用双随机 Birkhoff 多面体 \(\mathcal{B}_N = \{X \in [0,1]^{N \times N} \mid \sum_i X_{ij} = \sum_j X_{ij} = 1\}\)，对角线因子约束在松弛单纯形 \(\{y \in [0,1]^d \mid \sum_i y_i \leq 1\}\)，图着色约束在单节点颜色分布单纯形上。在推理时，通过几乎处处可微的交替投影算子 \(\Pi_{\mathcal{Y}}\) 实施投影一阶优化：

\[y_{t+1} = \Pi_{\mathcal{Y}}\bigl(y_t - \eta_t A_t \nabla_y E_\theta(x, y_t)\bigr)\]

其中 \(A_t\) 可以为单位矩阵（标准 PGD）或 Adam 预条件对角阵，配合余弦步长衰减策略与微小的仿射对称性破缺扰动 \(\xi \sim \mathcal{U}([-1,1])^n\)，彻底将组合推理从低效随机采样转变为收敛有理论保证的高效凸规划。

3. 解码感知裕度理论与端到端展开求解器优化

单纯保证连续松弛能量的全局最优性并不自动等价于离散可行解的正确恢复。为了跨越连续松弛最优解与离散解之间的鸿沟，作者建立了严谨的解码感知裕度理论。定义无效解码区域闭包为 \(\mathcal{B}_x = \overline{\mathcal{Y}_x \setminus \mathcal{A}_x}\)，其解码感知能量裕度为 \(\Gamma_x^D(E_\theta) = \min_{y \in \mathcal{B}_x}(E_\theta(x, y) - E_x^\star)\)。只要近似误差 \(\Delta\) 与求解器残差 \(\delta\) 满足 \(2\Delta + \delta < \gamma_{\mathrm{dec}}\)，一阶优化器输出的连续点就能无损解码出正确的离散有效解。

在训练层面，CCEM 采用两阶段策略：第一阶段在局部因子级别利用干净正负样本对进行局部 InfoNCE 对比预训练，快速构建局部能量漏斗；第二阶段通过展开 \(T\) 步可微投影优化轨迹进行全局端到端微调，损失函数联合优化连续回归项、全局能量排序边界项与沿求解轨迹挖掘的困难负样本正则项：

\[\mathcal{L}_{\mathrm{board}} = \alpha\|\hat{x} - x^\star\|_2^2 + \beta\,\mathrm{softplus}\bigl(E_\theta(x^\star) - E_\theta(\hat{x}) + \rho\bigr) + \frac{\gamma}{|\mathcal{H}|}\sum_{\tilde{x} \in \mathcal{H}}\mathrm{softplus}\bigl(E_\theta(x^\star) - E_\theta(\tilde{x}) + \rho_{\mathrm{h}}\bigr)\]

该训练过程将能量景观的形态与实际测试时求解器的离散化行为紧密对齐，有效防止能量坍缩并拉大解码有效区与无效区的能量裕度。

实验关键数据

主实验

论文在 8-Queens、图着色（Graph Coloring）以及 3-SAT 等结构化组合推理基准上与主流基线展开全面评测。在 8-Queens 任务上，CCEM 与扩散模型、图强化学习和基于非凸能量加权采样的 EBM-Diff 进行对比；在图着色任务上，评测覆盖了 8 种具有不同拓扑特性的图分布（包含 Erdos-Renyi、Holme-Kim、正规图、Paley 图与完全图），统计平均冲突边数（Conflicting Edges）与离散精确着色成功率。

表 1：8-Queens 基准评测对比（100 个随机评估棋盘）

模型	方法类型	正确棋盘数 (↑)	平均放置皇后数 (↑)
LWD	强化学习 + 采样	22	\(7.10 \pm 0.57\)
GFlowNets	无监督学习 + 采样	14	\(6.93 \pm 0.59\)
DIFUSCO (\(T=50\))	监督学习 + 扩散采样	17	\(6.94 \pm 0.65\)
Fast T2T (\(T_S=5, T_G=5\), GS)	监督学习 + 贪心搜索	41	\(7.38 \pm 0.54\)
EBM-Diff (\(P=1024\), PEM)	监督学习 + 粒子采样 (PEM)	97	\(7.97 \pm 0.17\)
CCEM (本文, \(T=50, S=64\))	监督学习 + 投影 Adam	100	\(\mathbf{8.00 \pm 0.00}\)

表 2：图着色任务冲突边数主实验对比（100 个采样图实例，值越小越好）

图分布类型	GCN	GAT	XLVIN	GNN-GCP	EBM (\(P=128\))	CCEM (本文)
Erdos Renyi	\(46.80 \pm 20.47\)	\(34.00 \pm 11.55\)	\(25.00 \pm 7.81\)	\(15.20 \pm 4.32\)	\(8.60 \pm 4.82\)	\(\mathbf{2.20 \pm 2.14}\)
Erdos Renyi 2	\(151.60 \pm 12.09\)	\(130.20 \pm 11.47\)	\(93.80 \pm 31.12\)	\(53.80 \pm 8.34\)	\(29.20 \pm 8.05\)	\(\mathbf{4.60 \pm 2.94}\)
Holme Kim	\(74.00 \pm 14.74\)	\(51.20 \pm 10.03\)	\(29.00 \pm 7.75\)	\(13.20 \pm 7.46\)	\(10.60 \pm 2.70\)	\(\mathbf{5.00 \pm 3.41}\)
Holme Kim 2	\(408.00 \pm 26.40\)	\(253.20 \pm 50.71\)	\(182.60 \pm 24.73\)	\(55.20 \pm 12.63\)	\(59.00 \pm 3.74\)	\(\mathbf{14.00 \pm 1.26}\)
Regular Expander	\(87.60 \pm 22.58\)	\(58.60 \pm 12.44\)	\(29.00 \pm 7.75\)	\(15.40 \pm 6.65\)	\(11.00 \pm 4.89\)	\(\mathbf{4.20 \pm 3.43}\)
Regular Expander 2	\(144.80 \pm 6.90\)	\(118.80 \pm 12.59\)	\(112.60 \pm 10.97\)	\(141.60 \pm 69.47\)	\(37.20 \pm 4.71\)	\(\mathbf{14.40 \pm 3.56}\)
Paley	\(285.00 \pm 117.70\)	\(239.20 \pm 159.43\)	\(151.80 \pm 92.13\)	\(91.20 \pm 63.14\)	\(34.80 \pm 20.27\)	\(\mathbf{1.80 \pm 3.60}\)
Complete	\(46.00 \pm 15.04\)	\(46.00 \pm 15.04\)	\(34.80 \pm 16.42\)	\(30.00 \pm 2.54\)	\(3.40 \pm 1.14\)	\(\mathbf{0.00 \pm 0.00}\)

消融实验

消融实验深入探讨了不同规模实例下，推理阶段独立可行起始点数量（Number of Warm Starts \(S\)）对离散有效解恢复率的影响，以及第二阶段损失函数项对训练效率与性能的贡献。

表 3：N-Queens 跨尺度零样本泛化中不同启动数 \(S\) 下的有效棋盘解码成功率（%）

棋盘规模 \(N\)	\(S=1\) (单轨确定性)	\(S=4\)	\(S=8\)	\(S=16\)	\(S=32\)	\(S=64\)
\(N=4\)	\(28.00 \pm 3.29\)	\(79.00 \pm 3.68\)	\(98.00 \pm 1.99\)	\(100.00 \pm 0.58\)	\(100.00 \pm 0.00\)	\(100.00 \pm 0.00\)
\(N=5\)	\(47.00 \pm 5.69\)	\(99.00 \pm 2.20\)	\(100.00 \pm 0.63\)	\(100.00 \pm 0.00\)	\(100.00 \pm 0.00\)	\(100.00 \pm 0.00\)
\(N=6\)	\(4.00 \pm 1.79\)	\(12.00 \pm 4.31\)	\(30.00 \pm 4.72\)	\(48.00 \pm 4.47\)	\(79.00 \pm 4.23\)	\(96.00 \pm 1.97\)
\(N=7\)	\(14.00 \pm 3.74\)	\(49.00 \pm 5.43\)	\(80.00 \pm 4.29\)	\(98.00 \pm 1.97\)	\(100.00 \pm 0.45\)	\(100.00 \pm 0.00\)
\(N=8\) (训练尺度)	\(13.00 \pm 2.38\)	\(31.00 \pm 4.70\)	\(51.00 \pm 5.22\)	\(81.00 \pm 3.87\)	\(98.00 \pm 2.09\)	\(100.00 \pm 0.39\)
\(N=9\)	\(6.00 \pm 2.31\)	\(23.00 \pm 4.45\)	\(48.00 \pm 3.94\)	\(73.00 \pm 4.47\)	\(95.00 \pm 2.65\)	\(100.00 \pm 0.79\)
\(N=10\)	\(4.00 \pm 1.82\)	\(12.00 \pm 3.12\)	\(20.00 \pm 3.85\)	\(40.00 \pm 4.88\)	\(58.00 \pm 5.46\)	\(82.00 \pm 3.62\)

关键发现

• 消除非凸假局部极小值大幅提升离散成功率：在图着色任务中，CCEM 不仅大幅压低了冲突边数，还在离散精确有效着色率上全面碾压基于粒子采样的 EBM+PEM（例如在 Paley 图上从 32/100 提升至 59/100，完全图达到 100/100 完美着色），证明了优化器没有被困在虚假局部陷阱中。
• 推算效率呈现数量级优势：在 8-Queens 上，EBM-Diff 依赖 \(P=1024\) 个粒子与 100 步扩散，耗费超过 20 万次能量前向评估；而 CCEM 仅需 \(S=64\) 组启动与 50 步投影迭代，总前向次数仅为 3,264 次，推理用时从 340 秒骤降至 60 秒，显存与计算开销减少近 98%。
• 多起始点是离散恢复手段而非跳坑机制：消融表明增大启动数 \(S\) 稳定提高了向离散有效解的恢复率。对于凸能量曲面，这反映的是在存在近乎等能的平坦极小解集时对抗有限步长与解码边界敏感性，而非传统非凸优化中的“粒子越过能量势垒”。

亮点与洞察

• 将组合能量建模转为凸规划理论：巧妙利用凸函数在非负加权求和下的代数封闭性，从模型参数化根源上彻底拔除非凸伪极小值，推导了凸能量一阶最优性即全局最优性的理论支撑。
• 紧凸松弛取代高维扩散去噪：放弃了在连续欧氏空间利用大量高斯噪声进行扩散轨迹模拟的常规路线，直接在问题的最小紧凸多面体上应用投影一阶算子，使得优化步步可行、可微且收敛可测。
• 清晰界定连续凸优化与离散解码保证的边界：没有草率宣称“凸性解决 NP-hard”，而是严格证明了求解器精度、模型逼近误差与解码感知裕度之间的充分条件，指出了多项式时间统一证书的复杂性上界。

局限与展望

• 表达能力的天然折中：凸性结构作为归纳偏置虽然提供了绝佳的优化良态性，但也限制了函数对复杂多模态离散分布的拟合能力，遇到高度复杂的非凸离散空间时可能出现平坦区或分数解退化。
• 对高维复杂约束的投影开销：当松弛集合无法高效进行交替单纯形或 Birkhoff 投影时（例如不规则高阶超图约束），投影算子自身的计算复杂度可能成为整体迭代的瓶颈。
• 未来方向：探索自适应拉格朗日乘子法处理复杂非多面体约束，以及将凸组合机制与分支定界（Branch-and-Bound）等经典组合求解框架进行混合加速。

相关工作与启发

• vs EBM-Diff / PEM (Oarga & Du, 2025): 两者均采用因子化能量组合并在测试期按需组装，但 EBM-Diff 使用无约束 MLP 导致组合景观高度非凸，严重依赖 1024 粒子退火采样；CCEM 采用 PICNN 保凸参数化与投影优化，在计算量缩减近两个数量级的同时显著提升了解的质量。
• vs GNN-GCP / DIFUSCO: 神经网络直接预测或离散图扩散求解器通常将整个图作为黑盒一次性输入，难以零样本尺度泛化；CCEM 坚持局部因子重用，单次训练即可零样本迁移至不同尺度的图与逻辑实例。

评分

• 新颖性: ⭐⭐⭐⭐⭐ 首次将输入凸神经网络与凸松弛多面体引入组合能量推理，理论优美且切中非凸组合优化的核心痛点。
• 实验充分度: ⭐⭐⭐⭐⭐ 在 N-Queens、8 类图着色拓扑以及 3-SAT 上开展了极其详尽的跨尺度、消融与计算复杂度对比。
• 写作质量: ⭐⭐⭐⭐⭐ 数学推导严谨自洽，对连续与离散边界阐述清晰透彻，图表数据完备详实。
• 价值: ⭐⭐⭐⭐⭐ 为解决神经组合优化与大模型推理中的死锁、幻觉及非凸景观困境提供了极富启发性的全新架构范式。

相关论文

• [ICLR 2026] Compositional Generalization from Learned Skills via CoT Training: A Theoretical and Structural Analysis for Reasoning
• [NeurIPS 2026] Are Your Reasoning Models Reasoning or Guessing? A Mechanistic Analysis of Hierarchical Reasoning Models
• [NeurIPS 2026] Measuring Weak-to-Strong Legibility of Reasoning Models
• [NeurIPS 2026] A Mechanistic Analysis of Looped Reasoning Language Models
• [NeurIPS 2026] decoding the critique mechanism in large reasoning models