We study the sequence-to-sequence mapping capacity of transformers by
relating them to finite transducers, and find that they can express
surprisingly large classes of transductions. We do so using variants of RASP, a
programming language designed to help people "think like transformers," as an
intermediate representation. We extend the existing Boolean variant B-RASP to
sequence-to-sequence functions and show that it computes exactly the
first-order rational functions (such as string rotation). Then, we introduce
two new extensions. B-RASP[pos] enables calculations on positions (such as
copying the first half of a string) and contains all first-order regular
functions. S-RASP adds prefix sum, which enables additional arithmetic
operations (such as squaring a string) and contains all first-order polyregular
functions. Finally, we show that masked average-hard attention transformers can
simulate S-RASP. A corollary of our results is a new proof that transformer
decoders are Turing-complete.

通过与有限转导器的关系，我们研究了变压器的序列到序列映射能力，并发现它们能够表达出令人惊讶的大类转导。我们使用 RASP 的变体作为中间表示形式，该编程语言旨在帮助人们 “像变压器一样思考”。我们将现有的布尔变体 B-RASP 扩展到序列到序列函数，并且表明它计算了一阶有理函数（如字符串旋转）。随后，我们引入两个新的扩展。B-RASP [pos] 允许在位置上进行计算（如复制字符串的前一半），并且包含所有一阶正则函数。S-RASP 添加了前缀和，它使得额外的算术运算成为可能（如字符串的平方），并且包含了所有一阶多正则函数。最后，我们展示了掩码平均硬注意力变压器可以模拟 S-RASP。我们结果的一个推论是变压器解码器是图灵完备的的新证明。

变压器作为传感器

Transformers as Transducers

Large language models exhibit surprising emergent generalization properties,
yet also struggle on many simple reasoning tasks such as arithmetic and parity.
This raises the question of if and when Transformer models can learn the true
algorithm for solving a task. We study the scope of Transformers' abilities in
the specific setting of length generalization on algorithmic tasks. Here, we
propose a unifying framework to understand when and how Transformers can
exhibit strong length generalization on a given task. Specifically, we leverage
RASP (Weiss et al., 2021) -- a programming language designed for the
computational model of a Transformer -- and introduce the RASP-Generalization
Conjecture: Transformers tend to length generalize on a task if the task can be
solved by a short RASP program which works for all input lengths. This simple
conjecture remarkably captures most known instances of length generalization on
algorithmic tasks. Moreover, we leverage our insights to drastically improve
generalization performance on traditionally hard tasks (such as parity and
addition). On the theoretical side, we give a simple example where the
"min-degree-interpolator" model of learning from Abbe et al. (2023) does not
correctly predict Transformers' out-of-distribution behavior, but our
conjecture does. Overall, our work provides a novel perspective on the
mechanisms of compositional generalization and the algorithmic capabilities of
Transformers.

大型语言模型的新兴泛化特性方面已经有了惊人的发现，但在诸多简单推理任务（如算术和奇偶性等）上仍存在问题。本研究针对算法任务的长度泛化范围，通过提出一个统一的框架，阐述了 Transformer 模型在特定任务上表现出的能力和方式。