Generating from Discrete Distributions Using Diffusions: Insights from Random Constraint Satisfaction Problems¶
会议: NeurIPS 2026
arXiv: 2603.20589
OpenReview: https://openreview.net/forum?id=iGHKaEN77P
领域: 学习理论
关键词: 离散生成模型, 扩散模型, 随机约束满足问题, 信念传播, 相变理论
一句话总结¶
本文基于随机约束满足问题（CSP）与统计物理相变理论，系统评测了离散数据扩散生成方法，证实连续高斯扩散在离散解生成上一致性优于离散掩码扩散，且学习型去噪器能达到理论极限，创新的拓扑变量重排机制大幅推高了可采样密度阈值。
研究背景与动机¶
从文本、表格到基因序列，离散数据的可控生成一直处于生成式 AI 的前沿。随着去噪扩散模型在连续空间（图像、音频）取得巨大成功，学术界涌现出大量面向离散空间的扩散变体，特别是基于类别掩码的离散扩散（Masked Discrete Diffusion）。然而，生成模型领域长期缺乏原则性的离散基准测试，导致连续高斯松弛与离散状态转移两类范式的相对优劣始终缺乏理论共识；即便在广泛采用随机 \(k\)-SAT 作为合成评测基准的近期工作中，实验参数与评测指标往往随意设定，既缺乏关于可采样极限（目标精度）的明确标准，也缺乏关于图拓扑复杂度的相变指导。
这一认知模糊的核心矛盾在于：直觉上离散扩散避免了离散与连续空间之间的量化误差，应当更天然契合离散组合结构；然而统计物理与随机约束满足问题（CSPs）二十年来的理论积累表明，高维吉布斯测度下的后验推断具有深刻的相变几何结构，离散掩码带来的条件塌缩往往比连续高斯加噪更早诱发测度破碎（shattering）与计算瓶颈。研究者缺乏一个严密的理论镜子来解析扩散去噪器在复杂组合流形上的逼近能力。
本文的切入角度是：利用统计物理中严格建立的随机 \(k\)-SAT、\(k\)-XORSAT、\(k\)-NAESAT 及超图双着色（Hypergraph Bicoloring）理论，为扩散生成提供一个包含相变阈值与解析去噪上界的终极试验场。核心 idea：将求解随机 CSP 均匀解作为离散生成评测场，建立局部信念传播（BP）与神经网络去噪器的对偶关系，通过相变阈值和拓扑变量排序从根本上解释并优化扩散模型在离散空间的生成行为。
方法详解¶
整体框架¶
本文探讨的核心目标是：给定一个布尔决策变量集合 \(\boldsymbol{x} \in \{+1, -1\}^N\) 上的随机 CSP 因子图 \(G=(V, F, E)\)，从其解空间的均匀测度 \(\mu_G(\boldsymbol{x}) = \frac{1}{Z_G}\prod_{a \in F}\psi_a(\boldsymbol{x}_{\partial a})\) 中高效采样。方法设计涵盖两条正交的扩散路线（连续加噪扩散与离散掩码扩散）以及两类去噪计算引擎（基于因子图消息传递的解析 BP 算子，以及图等变递归神经网络去噪器）。
对于连续扩散，模型在 \(\mathbb{R}^N\) 空间运行离散时间欧拉反向随机微分方程，每一步利用局部去噪器估计倾斜吉布斯测度下的后验均值（磁化强度 \(\boldsymbol{m}\)），最终在终止时刻通过符号函数投影回二值空间；对于离散掩码扩散，模型从完全掩码状态出发，沿某种变量排列顺序 \(\sigma\) 依次揭开变量，每一步依赖去噪器输出的条件边缘分布进行伯努利采样。
%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
A["输入 CSP 因子图 G<br/>及噪声/掩码状态 Y"] --> B["连续与离散扩散架构<br/>DDPM 连续高斯 或 MDM 逐步掩码"]
B --> C["局部去噪引擎<br/>解析 BP 或 等变递归神经网络"]
C --> D["理论最优空腔初始化<br/>分布递归采样经验分布 Q"]
D --> E["拓扑先验变量排序<br/>逆叶序或逆度数启发式调度"]
E --> F["输出: 满足约束的均匀解 x"]关键设计¶
1. 连续扩散与离散扩散的统一对偶框架：消除离散化与塌缩失真
现有离散数据生成工作大多偏向掩码扩散（MDM），认为离散状态转移能杜绝连续扩散反向轨迹末端粗暴量化（rounding）带来的语义破坏。但本文在数学上指出，二者本质上均依赖对因子图局部倾斜测度边缘分布的估计： 连续扩散反向过程为： $$ \boldsymbol{Y}{\ell+1} = \gamma\ell \boldsymbol{Y}\ell + \delta\ell \boldsymbol{W}\boldsymbol{m}(\boldsymbol{Y}\ell; t\ell) + \sqrt{\beta_\ell}\boldsymbol{g}_\ell $$ 其中理想去噪器 \(\boldsymbol{m}(\boldsymbol{y}; t)\) 正是带高斯似然的倾斜测度 \(\mu_G^{\boldsymbol{y}, t}(\boldsymbol{x}) \propto \prod_{a}\psi_a(\boldsymbol{x}_{\partial a}) \exp(\frac{\sqrt{t}}{1-t}\langle \boldsymbol{y}, \boldsymbol{W}\boldsymbol{x}\rangle)\) 的后验自旋均值；而离散掩码扩散在部分揭开子集下，其条件分布同样因子化在相同拓扑的诱导子图上。统计物理重构分析证明，离散掩码扩散引入硬约束吸收态会导致空腔场关联过早发散，其理论重构相变阈值 \(\alpha_{\mathrm{mask}}\) 严格低于连续高斯扩散的相变阈值 \(\alpha_{\mathrm{diff}}\)。
2. 递归等变局部神经网络去噪器：逼近 BP 理论极限
为了探究黑盒深度网络在无先验物理公式指导下能否达到理论上界，本文设计了一套随局部半径 \(r\) 递归堆叠的图等变神经网络架构。对于目标变量节点 \(i\)，网络仅观察其 \(r\)-跳邻域子图 \(\mathsf{B}_G(i, r)\) 内的带噪观测：
在 \(r=1\) 时，ClauseMLP 将文字的带噪连续值或掩码独热编码与子句符号拼接并映射至嵌入空间；WeightMLP 通过注意力机制计算相邻子句 \(a \in \partial i\) 的动态权重 \(w(a \mid i) = \mathrm{softmax}(s_i(a))\)，形成局部凸组合表征；当扩展到 \(r \ge 2\) 时，架构引入 ClauseFF1 与 ClauseFF2，将前一层各变量的半径 \(r-1\) 嵌入递归注入到子句特征中，以完全可微的方式模仿因子图消息传递。参数量仅由子句长度 \(k\) 和隐藏层维度 \(d\) 决定（例如 \(k=4, d=128\) 时仅约 329K 参数），在不同变量数 \(N\) 间天然保持泛化。
3. 最优空腔初始化策略：消除边界伪关联
在有界半径 \(r\)-局部截断下，传统置信传播通常采用均匀初始化（即先验无偏），但图截断边缘会产生不可忽视的自由边界效应。本文提出基于群体动力学（Population Dynamics）的空腔初始化 \(\mathrm{BP}_{\mathrm{c}}(r)\)：从无限正则树形模型的自由边界吉布斯测度极限分布 \(Q(h)\) 中 i.i.d. 抽取边缘空腔场的经验初始样本。 定理 1 严格证明，在无冷凝相区 \(\alpha \in [0, \alpha_{\mathrm{c}})\) 内，当图规模 \(N \to \infty\) 时，空腔初始化的 \(\mathrm{BP}_{\mathrm{c}}(r)\) 去噪估计在局部极小化均方误差得分匹配目标（Score Matching Objective）上达到全类 \(r\)-局部算法的理论下界： $$ \mathbb{E}\left{\left(x_I - \hat{m}{\mathrm{BP}}}(r)}(\boldsymbol{Y{\mathsf{B}G(I, r)})\right)^2\right} \le \inf}(\cdot)}\mathbb{E}\left{\left(x_I - \hat{m}(\boldsymbol{Y)\right)^2\right} + o_N(1) $$ 实验表明，空腔初始化相比朴素零初始化显著提升了浅层去噪（}_G(I, r)\(r=1, 2\)）的生成成功率。
4. 拓扑感知的逆叶序与逆度数变量调度：击穿动态相变壁垒
标准扩散模型假定变量被对称加噪或以纯随机排列依次解掩码，而本文推翻了这一惯用范式，证明了因果置信度（Confidence-based）启发式在奇偶约束问题（XORSAT）中无法提供任何超越随机采样的收益（命题 3.1）。相对地，本文提出利用 2-core 剪枝过程的逆序作为生成顺序： - 逆叶序（Reversed-Leaf Ordering）：针对 \(k\)-XORSAT，递归寻找并剪除仅在一个子句中出现的度为 1 的变量及其从属子句；在生成阶段以完全相反的顺序依次填充变量。定理 2 证明，若叶剪除成功退化为空图，离散扩散采样的成功概率在 \(N \to \infty\) 时以概率 1 收敛，将理论可采样极限直接从 \(\alpha_{\mathrm{mask}}(k)\) 提升至极限动力学相变阈值 \(\alpha_{\mathrm{d}}(k)\)。 - 逆度数调度（Reversed-Degree Scheduling）：在连续扩散中，将对角噪声加权矩阵 \(\boldsymbol{W}\) 的对角元按变量在叶序或度数排序设定为 \(W_{ii} = 1 + c_0(S_i - \bar{S})/\mathrm{std}(S)\)，使高约束度的骨架变量更早获得低方差强信号引导。在 \(k\)-SAT 中，动态计算未满足子句中的最小正反度数 \(\mathrm{deg}_{\min}(i; \ell)\)，使复杂约束在早期被快速解构。
损失函数 / 训练策略¶
神经网络去噪器通过在合成配对数据上经验风险最小化训练： - 连续扩散采用均方误差损失：\(\mathcal{L}_{\mathrm{cont}}(\boldsymbol{x}, f) = (x_i - \tanh(f(\boldsymbol{Y}_{\mathsf{B}_G(i, r)}; \boldsymbol{\theta})/2))^2\)。 - 离散扩散采用二分类交叉熵损失：\(\mathcal{L}_{\mathrm{disc}}(x, f) = -x f/2 + \log\cosh(f/2)\)。 针对 \(k\)-XORSAT 在完全均匀解上因高度对称性导致早期梯度消失的问题，论文引入了先用确定偏置解（自由变量设为 +1）预热 50% epoch，再切换到无偏均匀解微调的两阶段课程训练策略；对于 \(k\)-SAT，直接使用植入解（planted formula）构造数据集，在测试时迁移到无偏随机公式依然保持一致泛化。
实验关键数据¶
主实验¶
论文在多类随机 CSP 族上进行了详尽的严谨统计评估，核心基准指标为“生成真正满足约束条件的赋值的精确成功率”（Success Rate，以 500 个独立随机公式测试集均值计，非松弛约束满足率）。
下表列出 \(k=4\) 情况下不同 CSP 家族在连续与离散扩散下的极限理论阈值对比：
| CSP 家族 (\(k=4\)) | 离散掩码理论阈值 \(\alpha_{\mathrm{mask}}\) | 连续扩散理论阈值 \(\alpha_{\mathrm{diff}}\) | 动力学相变阈值 \(\alpha_{\mathrm{d}}\) | 实验观测结论 |
|---|---|---|---|---|
| 4-XORSAT | 0.5625 | 0.6320 | 0.7723 | 连续扩散采样边界显著右移，突破离散掩码极限 |
| 4-SAT | 8.05 | > 8.05 | 9.38 | 连续扩散曲线全面包络离散扩散曲线 |
| 4-NAE-SAT | 理论上低于连续 | 理论上高于离散 | ~ 2.1 | 连续扩散在各局部半径 \(r\) 下成功率大幅领先 |
| 4-超图双着色 | 理论上低于连续 | 理论上高于离散 | ~ 1.05 | 连续扩散全面优于离散，且呈现单调收敛优势 |
下表展示 \(k\)-XORSAT 在不同变量度数 \(k\) 下各相变阈值的理论演化计算值（摘自文中 Table 1）：
| \(k\) (子句大小) | 随机掩码离散扩散阈值 \(\alpha_{\mathrm{mask}}\) | 均匀各向同性连续扩散阈值 \(\alpha_{\mathrm{diff}}\) | 动力学相变极限 \(\alpha_{\mathrm{d}}\)（逆叶序上界） |
|---|---|---|---|
| 3 | 0.666667 | 0.736 | 0.818469 |
| 4 | 0.562500 | 0.632 | 0.772280 |
| 5 | 0.474074 | 0.531 | 0.701780 |
| 6 | 0.406901 | 0.511 | 0.637081 |
| 8 | 0.315203 | 0.384 | 0.534997 |
| 10 | 0.256578 | 0.350 | 0.461197 |
消融与机制分析¶
论文针对去噪模型架构类型、局部作用半径 \(r\)、初始化方案以及变量解掩码调度进行了细致的消融对比：
| 实验配置 (\(N=300, 4\text{-SAT}\)) | 核心机制 | 评测表现及现象 | 相对基准分析 |
|---|---|---|---|
| 连续高斯 + 神经网络去噪器 (\(r=3\)) | 欧拉反向积分，MSE 得分匹配 | 在高密度区 \(\alpha=8.0\) 成功率维持在 ~90% | 与 BP 解析去噪器曲线几乎重合 |
| 离散掩码 + 神经网络去噪器 (\(r=3\)) | 逐变量条件掩码解开 | 在 \(\alpha=7.5\) 处成功率骤降至零 | 大幅落后于连续扩散，与 \(\alpha_{\mathrm{mask}}\) 预测吻合 |
| BP 零初始化 (\(r=1, 2\)) | 消息初始置 0 | 早期局部估计欠拟合，\(\alpha=7.0\) 处即出现严重失败 | 浅层去噪器基准 |
| BP 空腔初始化 (\(\mathrm{BP}_{\mathrm{c}}\), \(r=1, 2\)) | 群体动力学采样极限分布 \(Q\) | 显著抬升低半径去噪器的成功率曲线 | 经验上达到全类局部去噪器误差下界 |
| 随机变量排序 (\(4\text{-XORSAT}, r=300\)) | 均匀随机选取解掩码变量 | 成功率在 \(\alpha \approx 0.56\) 处断崖下跌至 0 | 受制于理论 \(\alpha_{\mathrm{mask}}\) |
| 逆叶序调度 (\(4\text{-XORSAT}, r=300\)) | 2-core 剪枝拓扑逆序还原 | 成功率曲线完美延伸至 \(\alpha_{\mathrm{d}} \approx 0.772\) | 彻底击穿无序扩散瓶颈，达到最优极限 |
| 逆最小度数动态排序 (\(4\text{-SAT}\)) | 依据未满足子句动态度数优先 | 在大尺寸 \(N=1000\) 上高密度区间成功率翻倍提升 | 验证拓扑先验启发式在 NP-complete 上的威力 |
关键发现¶
- 连续扩散的绝对优势：无论去噪器采用解析 BP 还是学习型神经网络，也无论在何种局部半径 \(r \in \{2, 3, 6, 9\}\) 与规模 \(N \in [50, 5000]\) 下，连续扩散采样成功率无一例外系统性碾压离散掩码扩散。这打破了“离散领域必须用离散扩散”的朴素直觉。
- 学习型去噪器完美匹配理论极限：仅利用局部因子图等变归纳偏置的浅层神经网络，在训练收敛后展现出与计算复杂、利用全部解析拓扑关系的信念传播几乎一致的去噪表现与相变行为。
- 因果置信度排序的失效与拓扑重排的成功：大语言模型与掩码生成中常用的“高置信度优先”（confidence-based）解码在具备奇偶对称性的空间中被严格证明与随机采样毫无差异；相反，基于图论超图剪枝（leaf removal）的全局结构拓扑重排能够将算法极限从较低的局部重构相变直接提升至本征几何相变 \(\alpha_{\mathrm{d}}\)。
- 生成的均匀性保证：通过信息论上界比较发现，生成样本的负对数似然经验均值高度贴合理论自由能 \(\phi(\alpha) = \log 2 + \alpha \log(1-2^{-k})\)，随规模 \(N\) 增大分布越发集中，证明扩散模型在求解 CSP 时不会发生坍缩，能够均匀覆盖庞大的解空间。
亮点与洞察¶
- 为离散生成评测树立严格可信的理论坐标：避免了在缺乏标准答案的真实表格或语料库上的模糊启发式比较，引入具有明确多稳态与动力学相变临界值的数学物理模型作为评测基准。
- 连续空间平滑了高维组合障碍：连续高斯扩散实际上在紧致超立方体顶点之间架设了一条连续的能量平滑路径，避免了离散离散跳跃下硬约束诱导的局部极小陷阱，从理论机理上阐明了连续扩散优于离散掩码的根源。
- 图论剪枝与扩散调度深度融合：揭示了扩散变量揭开顺序与组合优化拓扑解耦之间的等价性，逆叶序（Reversed-Leaf）为设计新型高效自回归/并行扩散调度提供了坚实的图论范例。
局限与展望¶
- 计算复杂度与大图局部半径：为了达到接近 100% 的生成成功率，图规模放大时网络需要更深的感受野 \(r\) 或更多的扩散时间步 \(L=500\)，对于极大规模图结构存在显存与推理延迟开销。
- NP 完全问题（SAT）的严格解构：对于 \(k\)-XORSAT 拥有精确的逆叶序最优性证明，但对于一般 \(k\)-SAT，因缺乏单子句消解的唯一可逆性，动态逆度数机制仍属于启发式探索，其理论极限尚未完全闭合。
- 真实场景迁移挑战：合成 CSP 具有良好的局部树状特性，而现实世界中的离散表格与代码数据包含高度密集的异质语义耦合与长程依赖，未来工作需探索如何将因子图空腔原理扩展至 Transformer 注意力架构中。
相关工作与启发¶
- vs. Austin et al. (D3PM / Discrete Diffusion)：D3PM 等工作强调在离散转移矩阵上构造马尔可夫链以贴合离散数据；本文从自旋玻璃与相变理论证明，在复杂组合约束下，离散掩码扩散的重构相变门槛天然劣于连续扩散。
- vs. Ghio et al. / Montanari et al. (Spin Glass Localization)：先前的统计物理工作主要聚焦于解析 BP 和纯理论渐近；本文打通了“解析 BP 算法”与“参数化深度神经网络学习”的鸿沟，证实神经网络去噪器能够在有限样本下自主学习到与 BP 相当的最优估计。
- vs. Mask-Predict / 自由变量自回归生成：主流文本非自回归生成常用的置信度解码在组合奇偶性结构下被证明完全无效，启发后续生成模型设计应当更多依赖图拓扑约束度（如逆度数）而非瞬时局部模型置信度。
评分¶
- 新颖性: ⭐⭐⭐⭐⭐ 首次从统计物理相变理论与随机 CSP 出发，系统阐明连续与离散扩散在组合离散流形上的性能分水岭。
- 实验充分度: ⭐⭐⭐⭐⭐ 覆盖 4 类 CSP（SAT、XORSAT、NAE-SAT、超图双着色）、规模横跨 \(N=50\) 到 \(5000\)、系统对比 BP 与 NN 去噪器、多半径与变量重排。
- 写作质量: ⭐⭐⭐⭐⭐ 理论推导严密自洽，定理与实验现象紧密印证，反直觉结论剖析深入通透。
- 价值: ⭐⭐⭐⭐⭐ 为离散扩散模型的设计、评估指标与变量生成调度提供了极具理论指导意义的基础准则。