Binary Discrete Diffusion：用候选集扩散破解逻辑与规划任务

离散扩散模型在文本生成中已展现出任意顺序生成与自我纠错的能力，但传统掩码扩散和均匀扩散在单次腐蚀事件中会彻底抹去 token 身份，导致噪声状态无法显式表达“多个候选仍有可能”的部分不确定性。这正是逻辑推理、规划等需要逐步排除错误选项的任务所面临的瓶颈。近期一篇研究提出 Binary Discrete Diffusion，用二进制隶属向量表示每个位置的候选 token 集合，通过连续的添加与移除操作逐步消解不确定性，在数独、推箱子、图着色等任务上取得了显著优于强基线的表现。

离散扩散的固有缺陷：一次性腐蚀丢失部分信息

离散扩散模型的核心机制是迭代去噪：从完全随机的类别序列出发，通过反向过程逐步恢复出有意义的序列。这类模型支持任意顺序生成、填充和自纠错，因而被视为推理、规划以及代码和数学等约束生成任务的有力候选。

问题在于腐蚀核的设计。掩码扩散将 token 替换为 [MASK]，均匀扩散将其替换为词表上的均匀分布——两者都在单次事件中彻底抹去了原始 token 的身份。这意味着模型的噪声状态只能表达“已知”或“完全未知”两种极端，无法表示“这个位置可能是 A 或 B，但绝不是 C”这样的部分不确定性。对于数独或图着色，人类解题时恰恰依赖这种候选集排除法：先锁定几个可能值，再通过约束逐步剔除。传统离散扩散的中间状态与这种推理过程并不匹配。

离散扩散模型（Discrete Diffusion Models）是一类生成模型，其核心思想是通过一个前向腐蚀过程逐步将数据破坏为噪声，再学习一个反向去噪过程从噪声中恢复数据。与连续扩散（如图像生成中常用的高斯扩散）不同，离散扩散直接作用于离散状态空间（如文本的词表），其腐蚀过程通常定义为马尔可夫链，通过转移概率矩阵在离散状态间跳转。常见的离散扩散包括掩码扩散（Masked Diffusion）和均匀扩散（Uniform Diffusion），前者用特殊的[MASK] token替换原始token，后者则从词表上的均匀分布中采样替换。离散扩散的优势在于支持任意顺序生成和自我纠错，使其在文本生成、代码合成和约束满足问题中具有潜力。

候选集作为中间表示：二进制扩散的机制设计

Binary Discrete Diffusion 的核心创新是用候选集替代单一 token 作为扩散状态。具体而言，每个位置的噪声状态是一个二进制隶属向量，向量的每一位对应词表中的一个 token，1 表示该 token 仍在候选集中，0 表示已被排除。

腐蚀过程不再是“替换 token”，而是对候选集进行添加和移除操作：正向过程中，候选 token 被逐步移除，信息逐渐丢失；反向过程中，模型学习预测哪些 token 应被重新加入候选集。这种对称的添加-移除机制让信息可以渐进丢失并逐步恢复，扩散状态本身直接编码了部分不确定性。作者将这一族过程定义为连续时间离散扩散，并给出了对称与非对称两种形式化。

与掩码扩散相比，候选集状态在每一步都保留了更多结构信息——模型不必从零开始重新推断整个 token，而是对已有的候选假设进行精炼。这解释了为什么反向模型学到的计算会因腐蚀核的不同而产生实质变化。

连续时间离散扩散（Continuous-Time Discrete Diffusion）是离散扩散的一种形式化框架，其中前向腐蚀过程被建模为连续时间马尔可夫跳跃过程。具体而言，每个位置的状态在连续时间轴上以一定的速率发生跳跃（如token被替换或移除），跳跃速率由转移速率矩阵定义。这种连续时间视角允许使用更灵活的腐蚀调度，并可通过时间重参数化与离散时间步骤等价。在二进制扩散中，作者将候选集的添加与移除操作定义为连续时间下的跳跃过程，并区分对称（添加和移除速率相同）与非对称（速率不同）两种形式，从而为候选集演化提供了严格的概率模型。

逻辑与规划任务上的实证：数独、推箱子、图着色全面领先

论文在三个约束满足类任务上进行了系统评测：Sudoku-Extreme（极端难度数独）、Boxoban（推箱子规划）和 graph coloring（图着色）。在匹配架构、控制训练/采样/调参预算的条件下，二进制扩散的对称形式一致优于经过精细调优的掩码扩散和均匀扩散基线。

增益的分布值得关注：在最难的实例上提升最大。这与候选集表示的设计动机吻合——当问题约束密集、需要大量排除推理时，显式维护候选集的优势最明显；而简单实例上各方法差距缩小，说明基线并非全面失效，只是在需要精细不确定性的场景下力不从心。

语言建模方面，二进制扩散在 Text8、TinyStories 和 OpenWebText 上保持竞争力，但并未显著超越基线。这一结果符合预期：自然语言的下一个 token 分布虽然也有不确定性，但不像逻辑任务那样存在硬约束下的候选排除结构，候选集表示的边际收益因此有限。

腐蚀核决定反向模型学到的计算

这项研究最值得关注的论点不在具体任务指标，而在方法论层面：腐蚀核的选择会实质性地改变反向模型学到的计算内容。传统观点倾向于把腐蚀核视为扩散模型的工程细节，重点放在网络架构和采样器上。但这里的实验表明，当腐蚀核从“一次性抹除”变为“渐进移除候选”时，模型在相同架构下学到了不同的推理策略。

这为离散扩散的设计打开了一个新维度：针对任务结构定制腐蚀过程，可能比单纯堆叠模型容量更有效。候选集表示的代价是状态空间从词表大小扩展为 2^|V| 的二进制向量，但实验显示在受控预算下这种扩展带来的收益超过了成本。作者也指出，二进制扩散在语言建模上仅保持竞争力，说明该方法并非通用替代品，而是面向具有明确候选排除结构的推理任务的专用工具。

腐蚀核（Corruption Kernel）是扩散模型中定义前向过程如何将数据逐步破坏为噪声的核心组件。在离散扩散中，腐蚀核决定了状态转移的概率分布，例如掩码扩散的腐蚀核以一定概率将token替换为[MASK]，均匀扩散则以一定概率替换为均匀采样的token。腐蚀核的设计直接影响噪声状态所保留的信息量以及反向模型需要学习的去噪难度。传统上，腐蚀核常被视为工程细节，但本研究表明，腐蚀核的选择会实质性地改变反向模型学到的计算内容，从而影响模型在推理任务上的表现。这提示我们，针对任务结构定制腐蚀核可能成为提升扩散模型推理能力的重要方向。

对推理型 AI 的启示

将候选集作为迭代推理的中间表示，与神经符号方法和约束求解器的思路存在呼应：不是让模型一次性输出答案，而是维护一个逐步收缩的假设空间。二进制扩散提供了一个纯神经的、端到端可训练的框架来实现这一过程，且兼容任意顺序生成。

局限同样清晰。二进制向量的维度随词表线性增长，长序列和大词表场景下的内存与计算开销需要进一步评估；论文未涉及候选集规模的自适应控制，固定词表隶属向量在开放域任务中可能不够灵活。此外，语言建模上的平平表现提示，候选集表示的价值高度依赖于任务是否具有可分解的排除结构。

尽管如此，这项工作的核心结论足够扎实：在逻辑与规划任务中，扩散模型的噪声状态不该只是“已知/未知”的二元开关，候选集这一中间层让模型能够像人类解题一样逐步排除。对于关注迭代推理与约束生成的读者，这是一个值得追踪的方向。