一句话总结

生成式递归推理模型 (GRAM)，通过摊销变分推理训练，通过随机潜在轨迹将确定性递归推理转化为概率多轨迹计算，以支持多种假设，并通过递归深度和平行轨迹采样实现推理时扩展，在结构化推理和多解约束满足任务上优于确定性循环和递归基线，同时支持条件推理和无条件生成。

核心贡献

• 本文介绍了生成式递归推理模型 (GRAM)，这是一个将递归推理表述为使用随机潜在轨迹的潜在变量生成过程的框架。该方法允许通过对多个采样路径进行边缘化来获得解决方案，而不是收敛到单一确定性预测。
• 这项工作建立了基于宽度的推理时扩展，使模型能够通过递归深度和平行采样轨迹的数量来扩展计算。该机制促进了推理过程中多种假设的维护以及替代解决方案策略的探索。
• 在 Sudoku-Extreme、ARC-AGI 和 N-Queens 等基准测试上的实证评估表明，其优于确定性循环和递归基线。结果证实该框架在结构化推理、多解约束满足和无条件生成能力方面具有优势。

引言

未来的神经推理系统需要超越标准自回归序列生成的扩展计算机制。递归推理模型通过迭代细化持久潜在状态来解决这一问题，将推理深度与参数规模解耦。然而，现有实现根本上仍是确定性的，导致推理路径收敛于单一预测，无法探索替代假设。作者引入生成式递归推理模型 (GRAM) 将递归潜在推理转化为概率多轨迹计算。该框架将推理视为随机潜在轨迹，支持通过平行轨迹采样及递归深度来维护多种解决方案并进行推理扩展。

数据集

• 数据集组成与来源

  • 作者利用了一系列离散推理和生成任务，包括 Sudoku、ARC-AGI、N-Queens、Graph Coloring 和 MNIST。
  • N-Queens 和 Graph Coloring 的合成数据通过算法生成，以控制解决方案数量和难度。
  • 视觉任务源自 MNIST 数据集和 ARC-AGI 基准测试。

• 子集详情与处理

  • N-Queens
    • 来源： $N=8$N=8 和 $N=10$N=10 棋盘的所有有效完整解决方案作为基础。
    • 过滤： 通过移除 $k$k 个皇后（$N=8$N=8 为 $5$5 到 $7$7，$N=10$N=10 为 $7$7 到 $9$9）形成谜题实例。
    • 划分： 在唯一输入配置上运行 85:15 的训练 - 测试划分，以防止记忆化。
    • 编码： 棋盘展平为 1D 序列，词汇表包含填充、空单元格和皇后。
  • Graph Coloring
    • 来源： 图从具有 8 或 10 个节点和 3 种颜色的 Erdos-Renyi 随机模型中采样。
    • 过滤： 仅保留 3 色可着色图，保留规范形式以消除颜色排列冗余。
    • 规模： 数据集包含 $N=8$N=8 的 7,002 个训练和 255 个测试实例，以及 $N=10$N=10 的 13,465 个训练和 192 个测试实例。
    • 编码： 输入编码展平的上三角邻接矩阵，输出将节点位置映射到颜色 ID。
  • 其他任务
    • Sudoku： $9 \times 9$9×9 网格按行展平为 81 tokens，词汇表大小为 11。
    • ARC-AGI： 可变网格填充到固定的 $30 \times 30$30×30 画布，带有 EOS 标记和特定任务嵌入。
    • MNIST： 图像量化并通过基于 CNN 的块化方法处理为 $14 \times 14$14×14 展平序列，词汇表大小为 3。

方法

生成式递归推理模型 (GRAM) 引入了递归推理的概率框架，通过建模潜在推理轨迹上的分布与确定性方法区分开来。GRAM 不遵循单一固定路径，而是允许潜在状态随机演化，从而探索给定输入的多种解决方案路径。这一概念差异在下图中说明，其中确定性模型收敛于单一轨迹，而 GRAM 采样多样化路径以达到潜在解决方案。

GRAM 的架构组织为编码器、分层递归核心和解码器，如下面的架构示意图所示。编码器首先从输入 $x$x 计算嵌入 $e_x$ex​，并在整个计算过程中重复使用。核心维护一个由高层组件 $h$h 和低层组件 $l$l 组成的潜在状态 $z = (h, l)$z=(h,l)。高层状态在转换过程中累积抽象推理信息，而低层状态在每个转换内进行快速细化。具体来说，低层组件通过函数 $f_L$fL​ 更新 $K$K 次，而高层组件保持固定。随后，高层组件通过 $f_H$fH​ 更新，并辅以可学习的随机引导信号 $\epsilon_t$ϵt​。这种分层结构允许多尺度推理，将细粒度计算与高层轨迹控制分离。

训练 GRAM 涉及优化变分证据下界 (ELBO) 以近似条件似然 $p_\theta(y \mid x)$pθ​(y∣x)。该模型被视为潜在变量概率模型，其中完整潜在轨迹 $\tau$τ 由一系列潜在变量组成。为了处理轨迹上不可处理的边缘化，引入变分后验 $q_\phi(\tau \mid x, y)$qϕ​(τ∣x,y) 以及先验 $p_\theta(\tau \mid x)$pθ​(τ∣x)。优化目标包括重建项和 Kullback-Leibler (KL) 散度项，后者正则化后验使其接近先验。训练期间，在多个监督步骤上应用深度监督，其中一步的终端状态作为下一步的初始状态。梯度通过每一步的最后一个转换传播，以确保内存效率。

模型的概率性质使其能够捕获输出的多模态分布。对于具有多个有效解决方案的任务，如图着色，GRAM 可以通过遍历不同的潜在轨迹采样不同的有效配置，如下面的图所示。

此外，相同的递归机制可以通过将输入条件替换为空嵌入来适应无条件生成建模 $p_\theta(x)$pθ​(x)。在此设置下，模型通过潜在空间迭代生成数据，随着递归深度增加，生成样本的质量提高。这种能力使 GRAM 能够作为图像合成等任务的生成模型，在此过程中逐步将噪声细化为连贯结构，如下面的生成过程所示。

实验

评估在结构化推理基准、多解谜题和无条件生成任务上评估 GRAM，以验证其概率递归架构。发现表明，随机转换允许模型探索多样化的推理路径，并通过平行采样有效扩展，使其优于在复杂问题上遭受模式崩溃的确定性基线。此外，递归细化实现了比单独生成采样更严格的约束满足，消融研究证实随机引导对于导航多解空间和提高整体性能至关重要。

作者在无条件 Sudoku 生成上评估 GRAM，将其与不同大小的 D3PM 基线进行比较。结果表明，与基于扩散的基线相比，GRAM 实现了更高的有效性率，同时利用了显著更少的参数和推理步骤。GRAM 在所有测试方法中实现了最高的有效性率。GRAM 所需的计算步骤远少于 D3PM 变体。GRAM 的操作参数计数少于竞争基线。

该表概述了 GRAM 模型在各种结构化推理和生成基准上的训练配置和计算成本。它表明 ARC-AGI 是资源密集型任务，与其他基准如 Sudoku 或 N-Queens 相比，需要更多的训练周期和时间。ARC-AGI 需要最广泛的训练资源，耗时显著长于其他任务。N-Queens 任务计算效率最高，所需的周期最少且训练持续时间最短。随着节点数量增加，Graph Coloring 训练时间显著增加，尽管保持相同的训练周期数。

该表呈现了一项消融研究，评估随机引导和随机性对 GRAM 模型在 Sudoku 和 N-Queens 任务上性能的影响。完整 GRAM 模型在两个基准上均实现最高准确率，证明了结合随机转换与学习引导的有效性。移除随机引导会显著降低性能，特别是在多解 N-Queens 任务上，而完全移除随机性会导致模型完全失效。完整 GRAM 在两个基准上均优于所有消融变体和基线。仅随机性在 Sudoku 上保持高性能但在 N-Queens 上崩溃，凸显了多解空间中结构化引导的必要性。无随机性的确定性引导导致完全失败，表明随机转换对于导航解空间至关重要。

该表呈现了二值化 MNIST 上无条件图像生成的评估，将提出的 GRAM 模型与 VAE、D3PM 和 TRM 基线进行比较。结果表明，GRAM 显著优于表现出模式崩溃的确定性 TRM 基线，同时实现了与基于扩散的 D3PM 模型相当的性能。此外，发现表明在推理期间增加递归步骤数量会导致生成质量的一致提高。确定性 TRM 基线遭受模式崩溃，产生的生成质量显著低于 GRAM。GRAM 生成的图像质量与 D3PM 扩散模型相当。随着递归步骤数量增加，生成质量单调提高。

作者在 N-Queens 和 Graph Coloring 等多解谜题上评估 GRAM，以测试其捕获多样化有效解决方案的能力。结果表明，GRAM 在覆盖率上优于确定性递归基线，在准确率和约束满足上超越生成模型。这表明将递归细化与随机采样相结合，使模型能够比单独使用任一方法更有效地导航复杂解空间。GRAM 在 N-Queens 上实现了优于递归和自回归基线的准确率和解决方案覆盖率。该方法在 Graph Coloring 任务中显著减少约束违反，同时保持生成解决方案的高多样性。确定性递归模型难以应对多解覆盖率，而 GRAM 利用随机转换探索多样化推理路径。

作者在 Sudoku、N-Queens 和 ARC-AGI 等结构化推理基准以及无条件图像生成上评估 GRAM，将性能与扩散和确定性基线进行比较。结果表明，GRAM 以更少的参数和推理步骤实现了更高的有效性和准确率，同时避免了确定性递归模型中观察到的模式崩溃。消融研究进一步证实，结合随机转换与学习引导对于导航复杂解空间并确保稳健的约束满足至关重要。