通用 Transformer 电路计算：完美长度泛化
来自 arXiv · 期号 2026-09-01
摘要
神经网络在组合泛化与长度泛化上一直表现不佳。 这篇论文给出了一种可证明正确的 Transformer 参数化方案（布尔代数任务仅需 280 个可学习参数），能学习并评估任意深度或长度的表达式。核心思路是把算法任务建模为嵌入 Transformer 的电路模型，单次前向传播完成一层电路归约。 为了实现深度泛化，作者引入了一种位置编码，追踪每个门在电路中的深度，模型通过掩码硬注意力在每个迭代步识别可求值的子表达式，每步复杂度 O(n)。配合自主停止条件，问题深度为 d 时模型在 d 次迭代后终止，总复杂度 O(n·d)。 在深度 1 和深度 2 的浅层实例上训练后，模型参数会“卡入”可解释的位置，实现精确的长度泛化。在布尔表达式（通用符号计算）、模运算和 ListOps 等基准上均达到 100% 准确率。 论文附了开源代码。
深读
导读 这篇论文提出了一种可证明正确的 Transformer 参数化方案，仅用 280 个参数就能在布尔代数任务上实现任意深度的完美长度泛化。核心创新在于将算法任务建模为嵌入 Transformer 的电路模型，并引入追踪电路深度的位置编码。对于关注神经网络组合泛化能力的研究者，这篇工作提供了一个理论上有保证、实验上可复现的解决方案。 关键信息 - 布尔代数任务仅需 280 个可学习参数，在深度 1 和深度 2 的浅层实例上训练后，参数会“卡入”可解释的位置。 - 模型在布尔表达式（通用符号计算）、模运算和 ListOps 基准上均达到 100% 准确率。 - 每步迭代复杂度为 O(n)（通过线性注意力实现），总复杂度为 O(n·d)，其中 d 为问题深度。 - 输入要求为完全括号化的、格式良好的表达式。 逐节讲解 问题与挑战 神经网络在组合泛化和长度泛化基准上持续失败，学习可泛化的算法计算仍然是一个挑战。论文聚焦于一个具体设定：输入是完全括号化的、格式良好的表达式。 核心方法：电路模型与深度追踪 作者将算法任务建模为嵌入 Transformer 的电路模型，单次前向传播完成一层电路归约。为了实现深度泛化，引入了一种位置编码，追踪每个门在电路中的深度。模型通过掩码硬注意力在每个迭代步识别可求值的子表达式，配合自主停止条件，问题深度为 d 时模型在 d 次迭代后终止。 训练与泛化结果 在深度 1 和深度 2 的浅层实例上训练后，模型参数会“卡入”可解释的位置，实现精确的长度泛化。论文证明该构造可以完美评估任意长度的布尔表达式（通用符号计算），并在模运算和 ListOps 等其他常见长度泛化基准上也达到了 100% 准确率。 值得注意 论文基于摘要信息，具体实现细节（如位置编码的具体形式、掩码硬注意力的机制）未展开。结论建立在输入为完全括号化表达式这一假设之上，对于非括号化或自然语言形式的表达式，该方法的适用性未知。