微型通用Transformer实现电路计算长度泛化
原文：Universal Transformers for Circuit Computations: Perfect Length Generalization in Tiny Transformers
学习可泛化的算法计算仍然是神经网络面临的一项挑战，这体现在组合泛化和长度泛化基准上的持续失败。我们提出了一种可证明正确的Transformer参数化方案（针对布尔代数任务仅有280个可学习参数），能够学习和求解任意深度或长度的问题。我们假设输入是完全括号化的良构表达式。我们的方法将算法任务概念化为嵌入Transformer中的电路模型，从而可以在单次前向传播中完成深度为1的电路化简。为实现深度泛化，我们引入了一种位置编码来跟踪每个门在电路中的深度，使模型能够在每次迭代中通过掩码硬注意力识别可求值的子表达式，并通过线性注意力实现每轮迭代O(n)的复杂度。结合一个自主停止准则，模型对深度为d的问题在d次迭代后终止，总复杂度为O(n·d)。我们证明，在浅层问题实例（深度1和深度2）上训练即可有效恢复出可解释的、能够"归位"的参数，从而实现精确的长度泛化。尽管我们已证明该构造可以完美地对任意长度的布尔表达式（一种通用符号计算）求值，但在其他实验中，我们还展示了我们的Transformer变体在其他常见的长度泛化基准（包括模运算和ListOps）上也能完美学习并泛化（100%准确率）。