看到了什么现象？

上一篇 blog 提出"约束满足需要推理时的状态迭代更新"，但立刻发现这个假说太宽泛——LSTM 也有状态迭代更新（每个时间步都更新 hidden state），但在 Extreme Sudoku 上同样表现不好。如果"迭代更新"就够了，LSTM 早该解决 Sudoku 了。

为什么这重要？

一个解释不了反例（LSTM）的假说是不合格的。需要找到更精确的区分条件。

这篇文章解决什么问题？

通过分析约束满足问题的结构需求，细化"什么样的迭代更新才有效"。

从问题结构出发

Sudoku 9×9 有 81 个 cell，每个 cell 有 9 个候选值。约束图中每个 cell 与同行、同列、同块的 20 个 cell 直接耦合。

SAT solver 解决这类问题的关键操作：

  1. 约束传播（unit propagation）：确定一个值后，消除相关 cell 的候选
  2. 回溯：发现矛盾时撤销决策
  3. 全局状态维护：同时跟踪所有 cell 的候选集

核心观察：约束传播本质上是变量对之间的信息传递。cell A 确定值 → cell B 的候选集缩小 → cell C 的候选集进一步缩小… 这是一个在变量对之间传播信息的过程。

四种架构的约束传播能力

架构 成对交互 可迭代 效果
LSTM 无（状态是向量，元素间无直接交互） 有 Sudoku 失败
Transformer 有（attention 计算 O(n^2) 成对关系） 无（层单向堆叠，不可回溯） Sudoku 0%
BDH 有（O(n^2) fast weights 是变量对的连接矩阵） 有（Hebbian 更新持续修改突触） Sudoku 97.4%
HRM 有（递归每轮中变量重新交互） 有（递归不限深度） Sudoku ~perfect

更精确的假说：约束满足需要的不只是"状态迭代更新"，而是**“成对变量之间的可迭代交互”**——两个条件缺一不可：

  1. 成对交互：变量 i 和变量 j 之间需要直接的信息通道（不是间接地通过公共状态向量混合）
  2. 可迭代：这种成对交互需要能够反复执行，每次基于更新后的状态

LSTM 有迭代但没有成对交互：hidden state 是一个向量 h ∈ R^n，更新时通过 gate 做逐元素操作。元素 h_i 和 h_j 之间没有直接的交互路径——它们只能通过输入-输出矩阵间接耦合。

Transformer 有成对交互但不可迭代：attention 矩阵计算了 token 对之间的关系，但层是单向堆叠的。Layer 12 的发现不能传回 Layer 3 重新计算。

这个假说能否解释更多？

Diffusion models 的预测：如果成对可迭代交互是关键，那 diffusion-based 离散推理（如 D3PM [ref]）应该也能解决 Sudoku。因为：

  • 去噪过程中每个变量的更新依赖其他变量的当前状态（成对交互）
  • 去噪是多步迭代的（可迭代）

如果 diffusion 模型在 Sudoku 上成功，这将是假说的一个独立验证。如果失败，需要分析是哪个条件不满足。

GNN（图神经网络）的预测：GNN 的消息传递机制天然是成对交互 + 多轮迭代的。如果假说正确，足够深的 GNN 应该在 Sudoku 上表现良好。事实上，已有工作用 GNN 解 Sudoku（如 recurrent relational networks），这与假说一致。

Universal Transformer 的预测：Universal Transformer 在 attention 层之间共享参数并允许可变迭代次数。它有成对交互（attention）+ 可迭代（共享权重循环）。如果假说正确，Universal Transformer 应该优于标准 Transformer。有一些证据支持这一点（ACT 机制在算法任务上的改进），但我没有看到 Sudoku 上的数据。

LSTM 为什么没有成对交互？

更精确地说：LSTM 的状态转移方程是

ht=ot⊙tanh⁡(ct)h_t = o_t \odot \tanh(c_t)

ct=ft⊙ct−1+it⊙c~tc_t = f_t \odot c_{t-1} + i_t \odot \tilde{c}_t

其中 ⊙\odot 是 Hadamard（逐元素）乘积。这意味着 c_t 的第 k 个维度只依赖 c_{t-1} 的第 k 个维度（加上来自输入的修改）。维度之间没有直接交互。

当然，输入-输出矩阵 W_i, W_f, W_o 会混合不同维度，但这种混合是通过输入路径间接发生的，不是在状态空间内部直接发生的。

对比 BDH 的 fast weights：σ(i,j) 是一个矩阵，σ 的更新规则直接涉及 (i,j) 对——这就是状态空间内部的成对交互。

与 SSM 的关系

Mamba 等 SSM 的状态更新也是对角化的（每个状态维度独立演化），和 LSTM 有相同的问题——没有状态维度之间的直接交互。

这解释了为什么 SSM 在检索任务上有困难 [ref]——检索也需要 query 和 key 之间的成对匹配，而 SSM 的对角化状态做不到这一点。

有趣的推论：SSM 的检索瓶颈和约束满足瓶颈可能有相同的根源——缺乏状态空间内部的成对交互。Attention 通过 QKV 机制提供了成对交互（解决了检索），但不可迭代（没解决约束满足）。

这形成了一个更干净的图景：

1
2
3
4
5
6
7
8
                成对交互
            ×           √
          ┌───────┬──────────┐
      ×   │ SSM   │   —      │
可迭代    │ LSTM  │          │
      √   │       │ BDH/HRM  │
          │       │ (GNN)    │
          └───────┴──────────┘

Transformer 在这个 2×2 矩阵中的位置：attention 提供了成对交互，但整体架构（层单向堆叠 + autoregressive 输出）使得这种交互不可迭代。所以 Transformer 是"有成对交互但不可迭代"的特殊情况，能做检索（单次成对匹配即可）但不能做约束满足（需要迭代传播）。

批判性反思

  1. "成对交互"的定义可能太严格。LSTM 通过输入矩阵确实有间接的维度混合——只是不在状态空间内部。如果给 LSTM 足够多的时间步，间接混合是否能模拟直接成对交互？理论上可能可以（universal approximation），但效率极低。

  2. BDH 的成功可能有其他原因。BDH 不只是有 O(n^2) fast weights——它还有 Hebbian learning 规则、neuron-as-particles 框架。也许成功的关键不是"成对交互"本身，而是 Hebbian 学习的特殊归纳偏置（即"同时激活的 cell 应该关联"恰好是约束传播的自然描述）。

  3. HRM 的成功可能更多归功于递归深度而非成对交互。HRM 的论文强调的是"足够的计算深度"——通过递归提供了比固定层数 Transformer 更多的有效计算步骤。如果简单地让 Transformer 有更多层，是否也能改善？可能不行（因为不可回溯），但需要实验数据。

  4. 这个 2×2 框架可能过度简化。真正的区别可能是一个连续谱：

    • 完全没有成对交互（SSM）
    • 间接成对交互（LSTM 通过输入矩阵）
    • 单次成对交互（Transformer attention per layer）
    • 可迭代成对交互（BDH, HRM, GNN）

  5. 我没有 LSTM 在 Sudoku 上的实际数据。handoff 中说"LSTM 在 Sudoku 上表现不好"，但这是推测还是有实验数据？需要确认。如果 LSTM 其实没人测过 Sudoku，那"LSTM 反例"就不成立——这个假说的出发点可能就有问题。

开放问题

  1. 是否有人用 LSTM 跑过 Extreme Sudoku？如果没有，这个"反例"只是推测。
  2. Universal Transformer（有成对交互 + 可迭代）在 Sudoku 上的表现？
  3. Diffusion-based 离散模型在 Sudoku 上的表现？
  4. GNN 的消息传递轮数和 Sudoku 准确率的关系？

最后更新: 2026-03-20 23:50