Beyond Autoregression: Discrete Diffusion for Complex Reasoning and Planning

TL;DR

这是一个比较老的工作了，其实就是将 dllm 里面的损失加了个权重，不过故事倒是讲得挺好

1. 核心痛点与动机 (Motivation)

现有问题： 目前的自然语言处理领域由自回归（Autoregressive, AR）模型（如 GPT 系列）主导。尽管它们很强大，但在需要复杂推理、长期规划和保持全局一致性的任务上存在根本性缺陷。

• AR 的局限性： AR 模型从左到右逐个生成 token。在解决需要“前瞻”（lookahead）的问题时，模型在生成前面的步骤时可能还没有规划好后面的路径，一旦前面走错，后面无法回溯，只能“硬着头皮”生成，导致错误累积。
• 现有解决方案的不足： 引入搜索算法（如 Tree of Thoughts）计算成本极高；引入回溯训练（Backtracking）会导致输入冗长且性能欠佳。

核心理论视角：子目标不平衡 (Subgoal Imbalance) 作者提出了“子目标不平衡”的概念。在规划任务中，某些步骤（子目标）比其他步骤更难学习，因为它们依赖于未来的信息。

• AR 模型： 难以学习那些需要长距离规划的“困难子目标”（Hard Subgoals），因为它们只通过左侧上下文来预测。
• 扩散模型： 具有全向上下文（Bidirectional context），可以通过去噪过程从全局视角逐步细化，更适合处理这种不平衡。

---

2. 核心创新点：多粒度扩散建模 (MGDM)

为了解决上述问题，作者提出了一种改进的离散扩散模型，称为 Multi-Granularity Diffusion Modeling (MGDM)。

2.1 理论基础：离散扩散 Vs. 自回归

• AR 模型目标： 最大化 $p(x_n|x_{1:n-1})$。
• 扩散模型目标： 类似于最大化 $p(x_n|x_{\ne n})$（给定所有其他 token 预测当前 token）。
• 作者通过一个合成的路径规划实验（Synthetic Planning Task）证明：当规划距离（Planning Distance, PD）增加时，AR 模型即使增加数据量和参数量也几乎无法学习，而扩散模型可以轻松解决。

2.2 MGDM 的具体改进

标准的扩散模型通常对时间步（timestep）进行加权，但忽略了同一序列中不同 token 的学习难度差异。MGDM 引入了Token 级别的自适应重加权。

损失函数：

$$L_{MGDM}=\sum _{n=1}^N\sum _{t=1}^{T}w(t)\cdot \mathbf{v}({\mathbf{x}}_{\mathbf{t},\mathbf{n}})\cdot u(x_0,x_t,n;\theta )$$

• $w(t)$：序列级别的时间步权重（Sequence-level reweighting）。
• $u(\dots )$：标准的交叉熵损失。
• 关键创新 $v(x_{t,n})$： Token 级别的自适应权重。
  • 公式：$v(x_{t,n})=\alpha (1-\exp (-u(\cdot )){)}^{\beta }$
  • 原理： 对于损失（loss）较高的困难 token（即模型当前学不好的部分），给予更高的权重；对于简单的 token 降低权重。这使得模型在训练过程中能优先攻克“困难子目标”。

2.3 推理策略 (Inference)

作者采用 “Easy-first TopK” 解码策略。在去噪过程中，优先确定置信度高（简单）的 token，将其固定，然后再去推断困难的 token。这比随机解码效果更好。

---

3. 实验配置 (Experimental Setup)

作者选择了三个需要强规划和逻辑推理的任务，并与 AR 模型进行了严格对比。

• 基线模型 (Baselines)：
  • AR 模型： 从头训练的 GPT-2 架构（6M, 85M, 303M），以及微调的 LLaMA (7B, 13B) 和 GPT-4。
  • Stream-of-Search (SoS)： 一种增强 AR 的方法，将搜索轨迹加入训练数据中。
  • 其他扩散模型： VDM, D3PM, RDM 等。
• 任务：
  1. Countdown (数字游戏)： 给定几个数字和目标值，通过四则运算得到目标值。
  2. Sudoku (数独)： 9x9 网格填数字。
  3. Boolean Satisfiability (SAT)： 布尔可满足性问题（NP 完全问题）。

---

4. 实验结果与分析 (Results & Analysis)

4.1 Countdown (算术推理)

• 结果： MGDM 在所有复杂度设置下都显著优于 AR 模型。

  • 在最难的 Countdown 5（5 个输入数字）任务上，MGDM (85M 参数) 的准确率达到 46.6%。
  • 相比之下，LLaMA 13B 仅有 7.4%，从头训练的 GPT-2 (303M) 仅有 4.5%。
  • 即便是专门为了教 AR 搜索而设计的 Stream-of-Search 方法，效果也不如 MGDM。
  • GPT-4 即使使用了 CoT（思维链）和 ToT（思维树），其 Token 消耗量是 MGDM 的 186 倍，且准确率（ToT: 74%）虽然提升但仍需巨大算力。

• 错误分析 - “The Regretful Compromise” (遗憾的妥协)：

  • AR 模型的典型错误模式是：前面的算式写对了，但由于缺乏全局规划，算到最后一步发现凑不出目标数字，于是直接“编造”一个错误的计算结果来强行等于目标值（例如：$4+5=100$）。
  • MGDM 则展现出更好的全局一致性。

4.2 Sudoku (数独 - 逻辑推理)

• 结果：
  • MGDM (6M 参数) 达到了 100% 的准确率。
  • GPT-2 (303M) 只有 96.4%（实际上 AR 难以生成完全合法的数独板）。
  • LLaMA 13B 仅有 51.1%。
• 结论： 数独需要极强的全局约束满足能力，AR 的单向生成机制完全不适合此类任务，而扩散模型天然适合填充约束。

4.3 Boolean Satisfiability (SAT - 约束满足)

• 设置： 随着变量数量（5, 7, 9）增加，问题难度指数级上升。
• 结果：
  • 在 5 个变量时，MGDM 和 AR 表现相近。
  • 随着变量增加到 9 个，AR 模型性能大幅下降，而 MGDM 保持了显著的优势。
• 这证明了扩散模型在处理 NP 完全问题（即广泛的约束满足问题）上的潜力。

4.4 速度与准确率的权衡 (Speed-Accuracy Trade-off)

• 通常认为扩散模型推理慢（因为需要多次去噪迭代）。
• 惊人发现： 在 Countdown 任务中，MGDM 即使只用 1 个扩散步 (Step)，其准确率（75%）也远超 AR 模型（45.8%），且速度比 AR 快 10 倍（AR 需要生成整个思维链序列）。
• 这表明在复杂任务中，扩散模型的建模优势甚至可以抵消其迭代推理的劣势。

---

5. 总结与核心结论

1. AR 的结构性缺陷： 论文通过“子目标不平衡”理论深刻揭示了 AR 模型在处理规划任务时的本质弱点——无法处理需要前瞻的困难子目标。
2. MGDM 的有效性： 提出的多粒度扩散模型（MGDM），通过 Token 级的难度感知重加权，成功让模型专注于学习困难步骤。
3. 无需搜索即可高性能： 最令人印象深刻的是，MGDM不需要在推理时使用外部搜索算法（如 BFS/DFS），仅凭模型自身的生成能力，就在复杂推理任务上击败了结合了复杂提示工程（如 ToT）的大模型。
4. 范式转变： 文章主张，对于需要复杂逻辑、规划和全局一致性的任务，离散扩散模型是比自回归模型更优的范式。

遗漏细节补充

• 模型架构： 作者为了公平对比，MGDM 和 AR 模型都使用了相同的 Transformer 架构（类似 GPT-2），只是训练目标和推理方式不同。
• 代码开源： 论文提到的所有代码已在 GitHub 上开源。
• 吸收态 (Absorbing State)： 论文采用的离散扩散是基于“吸收态”的（类似于 Masked Language Model），即噪音是 [MASK] token，而不是随机替换成其他词，这被证明比均匀噪音更有效。