When Can Transformers Count to n?

进 Q 交流群：922230617 或加 VX：CV_EDPJ 进 V 交流群

目录

0. 摘要

1. 引言

2. 相关工作

3. 问题设置

4. 位置信息嵌入的必要性

5. 分析 query 计数（QC）

5.1 “直方图” 解决方案适用于 d > 2m

5.2 当 d<m 时直方图解决方案失效

5.3 CountAttend 解决方案：适用于所有 d 和 m

5.3.1 CountAttend 解决方案的局限性

6. 分析最频繁元素（MFE）

6.1 MFE 模型必须满足 d≥Ω(m)

6.2 当 d=O(m) 时可以实现 MFE

7. 实验

7.1 从头开始训练

7.2 预训练 LLM 的评估

8. 结论

9. 限制

0. 摘要

基于 Transformer 架构的大型语言模型可以解决非常复杂的任务。但是否存在这些模型无法解决的简单任务？在这里，我们专注于非常简单的计数任务，这些任务涉及计算一个词汇表中的 token 在字符串中出现的次数。我们展示了如果 Transformer 的状态的维度与上下文长度成线性关系，这个任务是可以解决的。然而，我们提出的解决方案在此限制之外并不能扩展，并且我们提供了理论上的论据，解释了为什么一个尺寸有限的 Transformer 可能无法实现这一任务。我们的实验证据表明了与理论论据预期相同的性能相变。我们的结果展示了理解Transformer如何解决简单任务的重要性。 

1. 引言

大型语言模型（LLMs）在从创意写作到解决复杂数学问题的广泛任务上展示了惊人的表现。鉴于这些成功，一个关key问题随之而来：这些模型能做什么，同样重要的是它们不能做什么。解决 LLM 表达能力这一问题有多种方式。首先，可以通过探测 LLM 并寻找它们无法成功执行的相对简单的任务来进行实证研究。确实，最近的研究发现了几个这样的任务，包括 “干草堆里的针” [7, 6]以及将任务扩展到更长的序列 [8]。其次，一个互补的方法是理论研究，它绘制了 transformers 的计算能力 [12, 17]。

在当前的工作中，我们专注于 transformers 经常难以应对的一个简单任务，并对其进行理论分析。具体来说，我们考虑一个非常简单的 “query 计数” 任务，定义如下。模型会接收到一个 token 序列，然后被要求回答给定的 query token 在序列中出现了多少次。例如：

• 考虑序列 a a b b a c c d a。字母 “a” 在序列中出现了多少次？

我们对这个问题的兴趣在于，它似乎是处理长输入流所需的一个基本模块。确实，有一系列关于素描和流处理的工作研究了类似的任务 [1, 4]。此外，这个任务可以看作是 “干草堆里的针” 问题的延伸，该问题最近引起了很多关注，因为据显示大多数 LLM 在处理长上下文时对此感到困难。具体来说，在干草堆里的针问题中，目标是找到长文本中的特定字符串。而在计数问题中，模型的任务是计算给定字符串出现的次数，这比找到一次出现更难。

然而，干草堆里的针问题和我们上面考虑的计数问题之间存在一个关key区别。干草堆里的针问题显然是可以通过 transformers 解决的，无论上下文长度如何。这是因为检测相似 token 并提取它（或附近的 token）对于单个注意力头来说是一个简单的任务（例如，使用归纳头（induction heads） [10]）。另一方面，对于计数问题，如我们在此所论证的，transformers 能否在任意上下文长度下解决这个问题就不那么清楚了。我们提到 transformers 不能执行某个任务时，是指参数数量不依赖于上下文大小的 transformers。

现代 LLMs 确实在计数任务上表现不佳（见第 7 节）。当然，如果这些模型可以使用代码，任务就变得简单了，但我们关注的是理解 transformer 架构本身的能力。具体来说，我们询问 transformers 是否在架构上存在与计数任务相关的限制。

考虑为什么 transformers 可能在这个任务上表现不佳，一个关key因素是 softmax 注意力的平均性质。直观上，解决计数任务的一个简单方法是让 query token 关注所有之前的 token，并对那些与其相同的 token 赋予高的注意力权重，而对其他的 token 赋予低的权重。这确实可以通过 Q/K/V 矩阵实现。然而，注意力机制随后会将这些权重归一化，使它们的总和为 1，无论 query token 在序列中出现的次数是多少。正如我们在第 4 节中所论证的，这已经提供了一些关于 transformers 在此任务上限制的见解。

接下来我们询问 transformers 在什么时候可以计数。我们展示了一种构造，只要 transformer 嵌入大小 d 大于词汇量 m，这种构造是有效的【注：类似于编码理论中的码距。码长足够长，码距才足够大，使得编码没有混叠。这对应于后面所说的正交构造】。我们的构造使用了一种 one-hot 嵌入，或者更普遍地说，是一种词汇的正交嵌入，这使得模型能够保持先前观察到的 token 的计数直方图。当 d < m 时，这种正交构造不再可能。一种自然的方法是考虑 “最可能正交” 的嵌入（在 Welch 界限 [19] 中正式化的概念），并尝试在类似的方案中使用它。然而，我们证明这种方法在 d > m 时无法实现直方图解决方案。

上述讨论表明，在 d < m 的情况下，使用直方图的简单方法似乎不起作用。我们对这一情况的研究揭示了正反两方面的结果。积极的一面是，我们展示了确实存在一种构造，可以通过单层 transformer 进行计数。消极的一面是，我们证明这种构造需要一个随上下文大小增长的 MLP 宽度，这意味着它不适用于任意长的上下文。确实，在优化 transformers 时，我们发现它们在 d > m 的情况下无法学习。

接下来我们研究一个稍微复杂的计数任务，我们称之为 “最频繁元素”。在这里，我们向模型展示一个 token 序列，并询问最频繁 token 的计数。这与获取计数直方图的最大值相同。类似于 query 计数，我们展示了在这种情况下，基于正交构造的解决方案在 d < m 时存在。然而，对于 d > m，我们通过通信复杂性论证证明，单层 transformer 没有解决方案。因此，我们再次在d = m时获得了计数任务的相变。

综上所述，我们的结果揭示了一个有趣的简单计数任务景观，其中 d = m 的阈值将能计数的 transformers 与不能计数的 transformers 分开。我们的结果突出了研究基本计数问题及其对词汇量依赖的重要性。它们还指出了使用 transformers 解决看似简单问题的局限性，并进一步强调了使用代码作为工具来规避这些问题的优势。

2. 相关工作

自从 Transformer 架构 [16] 和 LLMs 成功问世以来，已有大量研究评估其在各种任务中的表现，例如，见 [14]。特别是，最近的许多工作探讨了其在长上下文任务中的表现，准确性对上下文长度的依赖性 [8]，以及模型将训练中未见过的长度进行外推的能力 [2]。

模型在这些评估中表现不佳这一事实促使了一些工作试图明确 Transformer 模型的固有局限性。其中一项工作是使用计算复杂性下界方法来证明某一尺寸和架构的 Transformer 无法实现某个感兴趣的特定功能。例如，Sanford 等人 [12] 显示，某些函数不能在不随输入大小缩放的 Transformer 中实现。

相关的一项工作是将 Transformers 与已知的复杂性类联系起来。例如，已经证明 Transformers 是图灵完备的 [17]，并且具有有界精度的 Transformers 只能解决统一 TC0 中的问题 [9]。思维链（Chain-of-Thought） [18] 也从表达能力的角度进行了分析，证明它可以显著提高Transformers的表达能力[5]。

我们在这里的重点不是 Transformers 的一般能力，而是一个具体的、看似简单的问题，以及 Transformers 解决它的能力。

3. 问题设置

我们考虑由 n 个 token 组成的输入序列：x1, ..., xn。对于这些输入序列，期望的输出用 y 表示。我们考虑以下两种计数任务：query 计数（Query Count，QC）和最频繁元素（Most Frequent Element，MFE），其中 y 定义如下：

• 对于 QC 任务：y 是 token xn 在集合 x1, ..., xn 中的出现次数（即 y 总是 ≥1）。

• 对于 MFE 任务：y 是 x1, ..., xn 中最频繁 token 的出现次数。

我们将词典大小记为 m，即 xi ∈ {1, ..., m}。此外，我们使用以下符号表示与模型相关的量：

• d：key 的大小（即每个头的嵌入维度）。

• h：注意力头的数量。

• L：层数。

• p：计算的数值精度：我们假设所有的算术操作（包括 softmax）都使用 p 位的寄存器精确执行。

• D：总体嵌入维度，其中 D = d × h。

• token i 的嵌入为 vi ∈ R^D。

• 第 i 层，第 j 个注意力头的 query、key、value 矩阵分别为 Q_(i,j), K_(i,j), V_(i,j)，均为 R^(d·h × d) 的矩阵。

• pi：位置 i 的位置信息嵌入。

• u_(i,j)：第 i 个头在第 j 层的输出。

我们的大多数解决方案都使用由单层和单个头组成的架构。在这种情况下，我们分别省略符号中的 i 和/或 j。此外，注意如果 h = 1，则 D = d。

4. 位置信息嵌入的必要性

在分析具体的计数解决方案之前，我们先提及 Transformers 在我们考虑的计数问题上的一般限制。Transformers 使用自注意力机制对先前的表示进行平均。它们进行平均而非求和的事实导致了它们在计数能力上的一个有趣限制。具体来说，很容易看出，对于可变上下文大小，如果不使用位置信息嵌入，它们无法执行任何计数任务。

考虑 QC 任务和输入序列 S1 = x1, ..., xn，目标是返回 xn 在序列中的出现次数。现在考虑长度为 2n 的序列 S2 = x1, ..., xn, x1, ..., xn。对于这个序列，正确的输出是 S1 的正确输出的两倍。然而，没有位置信息嵌入的 transformer 应用于 S1 时，其输出与应用于 S2 时的输出完全相同。这是因为平均操作对输入的重复是不可变的。

使用位置信息嵌入时，上述限制不再存在，很容易看出，即使只是简单地标示最后位置的位置信息嵌入（见第 5.3 节中的构造），也可以解决这个问题。这意味着，如果 transformer 能够访问序列的长度，它可能更容易进行计数。

另一个需要注意的是，虽然上述困难出现在计数任务中，但如果我们感兴趣的是计算比例（例如，序列中等于 xn 的项的比例），则不会出现这种困难。

5. 分析 query 计数（QC）

在本节中，我们聚焦于 QC 问题，探讨哪些 transformer 架构可以成功实现它。首先，我们在第 5.1 节中展示，如果 d > 2m，一个单头单层的 transformer 可以实现 QC。我们将其称为直方图解决方案。然后，我们展示当 d < m 时，直方图解决方案停止工作。那么，自然的问题是，对于 d < m 的情况，是否有其他解决方案。我们认为，在这种情况下，解决方案可能需要计算函数 1/x，并展示该函数需要一个宽度为 n² 的 MLP 层。这意味着我们不能指望 transformer 能外推到较长的上下文大小，因此单层 transformer 不太可能实现 QC。

5.1 “直方图” 解决方案适用于 d > 2m

我们首先提供一种模型维度大于词汇量的解决方案。

定理 5.1 对于 query 计数问题，如果 d > 2m，存在一种能解决该问题的 transformer，其具有一个层，一个头，以及一个包含 d 个神经元的 MLP。

我们在下面提供构造（见图 1a）。我们首先将其描述为一个两头解决方案，但使用残差连接也可以简单地实现单头。其思路是构建所有先前 token 的直方图（即每个 token 出现的次数），然后根据 query token xn 从直方图中提取该特定 token 的计数。

首先，我们假设嵌入是正交归一的。即：

其中 vi 是词典项 i 在 R^d 中的嵌入。这是可能的，因为假设 d > m。为了简化，我们假设 vi=ei，其中 ei 是 R^d 中的标准基。

接下来，我们构建一个注意力头，其在位置 n 的输出是截至该位置的 token 的直方图。设 Q1=0（零矩阵）和 V1 = I_d（I_d 是 R^d 中的单位矩阵）。那么这个注意力头的输出是

其中 cj 是上下文中第 j 项的出现次数，由上下文的长度 n 归一化。即

换句话说，u1 是 R^d 中的一个向量，其第 i 个条目是 token i 在输入 x1,…,xn 中出现的次数。

第二个头的设置只是简单地复制输入嵌入。通过设置 Q2 和 K2 使得

其中 T 足够大且 V=I_d。然后我们有：

两个头的输出包括直方图和 query token 的一次性标识符。回忆一下我们期望的输出是 query token 的计数 c_(x_n)。我们可以使用一个具有 d 个 ReLU 门的多层感知机（MLP）来提取这个计数。第 i 个门计算

的 ReLU，其中 B 是一个足够大的常数。很容易看出，如果 x_n = i，则第 i 个门的输出是 c_(x_n)，否则为 0。

备注：

• 注意上述解决方案仅适用于固定长度 n 的输入。如第 4 节所述，没有位置嵌入的 Transformer（如我们构造的 Transformer）无法计数变长的输入。我们这里的构造可以通过使用位置嵌入和用于计算 1/x 的 MLP 扩展到变长的情况。我们将在下一节详细讨论这种方法。
  

• 我们还可以通过利用残差连接来用一个头实现上述直方图方案。其思路是使用嵌入维度中的一半坐标来存储注意力模块的结果，并通过残差连接将原始 token 传递给 MLP。
  

• 如果 v1,…,vm 是正交的，但 vi≠ei（即它们不是一次性标识符），则 MLP 将需要计算 n*u1 与 u2 的点积来提取计数。这对于 ReLU 门来说不太自然。然而，可以首先对 u1 和 u2 应用线性变换（基本上是旋转），将基变换为标准基，然后像之前一样提取计数。

5.2 当 d<m 时直方图解决方案失效

我们在上一节中的解决方案利用了如果 d>m 我们可以将字典嵌入到 R^d 中的正交向量的事实。当 d<m 时，这种方法是不可能的。可以尝试通过将字典嵌入到一组 “几乎” 正交的向量来扩展这个解决方案。然而，在 R^d 中的任何 m（例如 m≥2d）个向量集合中，包含的向量对的内积的绝对值至少为 Ω(1 / √d)。这是 Welch 界限 [19] 的结果，该界限提供了 R^d 中 m 个单位向量之间的最小点积的上界。这暗示了以下下界，说明在这种情况下计数将失败。

定理 5.2. 考虑第 5.1 节中提出的计数问题的 “直方图” 解决方案，以及嵌入向量 v1,…,vm。对于计数问题的输入 ˉx = (x1,…,xn)，用 c_(xn) 表示正确的解决方案，用 hist(ˉx) 表示 “直方图” 解决方案的输出。如果 m≥2d，则对于任何嵌入向量 vi，存在计数问题的输入，使得：

证明。设 v1,…,vm∈R^d 且 m≥2d，令

假设在不失一般性的情况下，A = v1⋅v2。根据 Welch 界限 [19] 对于 k=1，我们有

考虑计数问题的输入 x1,…,xn，其中 x1,…,x_(n−c) 都等于一个与 xn 不同的 token，并映射到嵌入 v1，而 x_(n−c),…,xn 都等于 xn，并映射到嵌入 v2。然后，直方图解决方案的输出是：

选择 c = 0.5n 和 n=d 可以得到期望的结果。

这个定理暗示，即使字典的大小仅与嵌入维度线性相关，任何解决方案也会导致一个随着上下文大小增加而增长的误差。在实践中，字典可以包含数百万个 token，而嵌入维度至多只有几千，因此这种误差可能会非常大。注意，随机选择嵌入向量（例如独立同分布的高斯分布）会比定理中所述的误差更大，因为两个向量之间的内积通常会大于我们在证明中使用的下界。  

5.3 CountAttend 解决方案：适用于所有 d 和 m

在上一节中，我们考虑了一种基于直方图的解决方案，该方案要求 d>m。在这里，我们提供了一种替代的方法来解决计数问题，该方法适用于任意的 d 和 m。然而，正如我们将看到的，这种解决方案需要一个大型的 MLP，其规模必须随着输入长度 n 增加。因此，具有固定 MLP 大小的 Transformer 将无法学习适用于任意 n 值的解决方案。

我们首先介绍这种构造的高级描述，它使用一个具有单头的 1 层 Transformer。这个方法明确地利用了注意力来进行计数（因此得名 CountAttend），如下所示（参见图 1b）。假设 query token 为 xn=4，我们需要寻找  x1,…,xn 中等于 4 的元素数量，并假设这些元素的数量为 7。然后，token xn 可以关注所有其他 token，使得对于所有 i，若 xi=4（以及这些token相同），则注意力权重都很高，而其他情况则接近零。因此，对于所有 xi=4 的token，包括 xn，其注意力权重将是 1/7。接下来，我们需要提取这个数字并取其倒数（inversion），以得到答案 7。

提取注意力权重可以通过在位置嵌入中使用一个坐标来完成，该坐标在位置 n 处为 1，其他位置为 0。然后，自注意力的值聚合可以提取出这个坐标中的数值  1/7。最后，为了取倒数，我们需要一个 MLP 来实现函数 1/x。如果我们需要取倒数的最小数字是 1/n，则可以使用具有 4n 个神经元的 MLP 来完成。

以下命题总结了这种构造的属性，证明见附录 A。

命题 5.3：对于任意 d, m, n，存在一个 Transformer 能解决相应的 QC 问题。这个 Transformer 具有一层、一个注意力头、维度为 d，以及大小为 O(n) 的 MLP。此外，其矩阵 K^⊤·Q 是对角的，元素的大小为 O(logn)。

5.3.1 CountAttend 解决方案的局限性

命题 5.3 的优点在于它适用于任何维度 d，并且不像直方图解决方案那样要求 d 大于 m。然而，命题 5.3 的解决方案相对于第 5.1 节中提出的直方图解决方案有两个主要的局限性。我们将在下面讨论这些局限性。

首先，命题 5.3 的 MLP 规模为 O(n)，这是由于它通过 MLP 实现函数 x ↦ 1/x，其中 x∈[1/n,1]，并且所需的精度是 0.5（因为我们是在计数，可以对结果进行四舍五入）。在 5.3 的证明中，我们使用了这种函数的一个简单实现。自然会问是否存在更小的实现。以下结果表明这是不可能的。

引理 5.4：任何具有 ReLU 激活的 2 层 MLP，需要 Ω(n) 个神经元，从而在区间 x∈[1/n,1] 内对函数 f(x)=1/x 以小于 1/2 的 L_∞ 误差进行逼近。【证明见原文】

虽然引理重点讨论了 2 层 MLP，但它可以很容易地推广到深层 MLP，例如使用 Telgarsky [15] 提出的深层 ReLU 网络的线性片段下界。尽管更深的网络可以用更少的神经元生成更多的线性片段，但深度仍然需要与 log⁡(n) 成比例，这在实际应用中是不切实际的。

命题 5.3 的第二个局限性是其注意力矩阵的幅度随着上下文大小 n 以对数形式增长。由于温度在指数内部，这意味着梯度的幅度应该与上下文大小呈多项式比例。这在高精度计算资源下是可能的。然而，Transformer 通常使用有限精度（例如 8 位或 16 位）进行训练，这使得优化如此大权重的过程变得不可行。

综合考虑这一节中的两个观察结果，尽管 QC 问题有一个单层 Transformer 实现，但这种表示对于任意 n 来说过于庞大，并且可能面临优化困难。

6. 分析最频繁元素（MFE）

在这一节中，我们考虑在给定token序列中找到最频繁元素（most frequent element，MFE）的任务。这个问题与计数问题非常相关，因为直观上它要求分别计数每个token，并计算出现次数最多的 token。我们展示了，为了让 Transformer 能够执行此任务，嵌入的大小相对于字典的大小有严格的界限。

6.1 MFE 模型必须满足 d≥Ω(m)

我们首先展示了解决 MFE 任务所需的 1 层 Transformer 的尺寸下界。以下结果表明，只有当 dhp=Ω(min⁡{m,n}) 时，MFE 才能实现。这意味着在固定精度 p 下，如果 n>m，则维度 d 必须随着词汇表大小线性增长，以实现 MFE。这与我们在 QC 问题中看到的趋势相同。

定理 6.1：假设存在一个具有 h 个头、嵌入维度 d 和 p 位精度的 1 层 Transformer，后接任意宽度和深度的 MLP，该 Transformer 可以解决长度为 n 的序列的 MFE 任务。那么，我们必须有 dhp≥Ω(min⁡{m,n})，其中 m 是词汇表的大小。

完整的证明见附录 B。该证明使用了通信复杂性论证，受到 Sanford 等人 [12] 提出的下界的启发。这一下界可以解释为，解决 MFE 任务的 Transformer 需要具有与字典大小成比例的嵌入大小（即维度或精度位数），或者具有多个注意力头。注意，增加跟随注意力的 MLP 的大小不能突破这一下界。

6.2 当 d=O(m) 时可以实现 MFE

之前的结果表明，当 d 小于 m 时，MFE 无法通过单层 Transformer 实现。这里我们展示了当 d=O(m) 时实现 MFE 是可能的。这意味着 d=O(m) 对于 MFE 问题是紧界限。结果如下所述。

定理 6.2：存在一个 1 层 Transformer，它可以解决大小为 n 的序列和字典大小为 m 的 MFE 任务，其中参数分别为：d=m, h=1, p=log⁡(n)，并且 MLP 具有 d^2 个神经元。

这种构造再次基于直方图方法。因为 d>m，可以计算最后位置的计数直方图（如 QC 问题一样）。唯一剩下的工作是从直方图中提取最大值，这可以通过一个具有 m^2 单元的单层 MLP 完成（每个单元在直方图中对两个不同元素执行最大值操作）。

上述结果的一个局限性是它需要一个随 m 增长的 MLP。如果使用两个层的注意力，这个问题可以避免。一个简单的两层实现是：使用第一层计算每个元素的 “查询计数”，然后使用 softmax 计算 token 中的最大值。这种构造完全不需要 MLP。另一种选择是使用深度为 log⁡(m) 的 MLP，每层具有 m 个神经元，以从直方图中计算最大值（见 [11]），然而，深度甚至依赖于字典大小的对数的实现对于实际应用来说是不可行的。

总结上述结果，我们已经展示了

• 当 d<m 时，MFE 无法通过单层 Transformer 实现
  

• 当 d>m 时，MFE 可以通过具有宽 MLP 的单层 Transformer 实现，或者通过不需要 MLP 的两层 Transformer 实现。

7. 实验

我们的分析考虑了 Transformer 模型大小 d 与其执行计数任务能力之间的关系。具体来说，我们展示了当词汇大小 m 超过 d 时，精确计数可能变得不可行。在本节中，我们进行了一些实验来支持这一观察。我们从训练模型开始，然后还考虑了预训练的 LLM（Gemini 1.5）的结果。

7.1 从头开始训练

任务：我们考虑文中描述的两个计数任务：最频繁元素（MFE）和查询计数（QC）。我们通过从 m 个 token 的集合中均匀采样长度为 n 的序列来生成这些任务的实例。每个这样的序列表示为 x1,…,xn。这些任务的期望输出 y 如下：

• 对于 QC 任务：y 是集合 x1,…,xn 中 token xn 的计数（即 y≥1 始终成立）。

• 对于 MFE 任务：y 是 x1,…,xn 中最频繁 token 的计数。

在训练和评估过程中，我们从上述分布中采样 batch。评估过程中在所有情况下使用了 1600 个示例。

模型：我们训练了一个具有标准架构组件（自注意力、MLP、层归一化等）的 Transformer 模型。我们使用了两层和四个头（理论上我们可以使用更少的头，但使用这种架构的优化速度更快）。训练使用 Adam 优化器，batch 大小为 16，步长为 10^{-4}。训练运行了 100K 步。位置嵌入进行了优化。为了预测计数 y，我们在最后一层中对最后一个 token 的嵌入进行线性投影（即我们这样做而不是词汇预测）。训练通过 Colab 完成，使用标准 GPU，每个模型训练大约需要 15 分钟。

参数设置：我们实验了几个 d 的值（介于 8 和 128 之间）。对于每个 d 值，我们调整 m 以测试词汇大小的依赖性（我们使用 m 从 5 到 150 的 20 个值）。为了保持平均计数在常数值 c 下，我们设置 n=c_m。在所有实验中，我们使用 c=10。

结果：我们的重点是理解 d 和 m 之间的依赖关系以及计数能力。因此，我们的结果报告如下：对于每个 d 值，我们找出计数开始失败的 m 值。具体来说，我们考虑 m 的值，使得计数准确率低于 80%。我们将此称为 m_thr(d)。图 2a 显示了这两个计数任务的结果。可以看到，在这两种情况下，阈值确实随着 d 的增加而大致线性增长，与我们的理论分析一致。

7.2 预训练 LLM 的评估

我们的理论结果强调了词汇大小在计数问题中的作用。在这里，我们提供对训练的 LLM（Gemini 1.5）中这一作用的探索。我们将 查询 计数任务提供给模型。然后我们改变 m，即序列中使用的不同 标记 的数量（例如，对于 m=5，我们使用一个仅包含 1, ..., 5 的序列），同时保持所有元素的期望计数为常数 c=10。即，对于每个 m，我们使用上下文长度为 m·c。作为这些的基线，我们还使用相同的序列长度，但使用二进制序列，使得 查询 标记 的期望计数为 c（在此处我们将其设置为 “10”）。这使我们能够估计仅由词汇大小造成的误差，而不是序列长度和计数。结果如图 2b 所示，可以看到，增加词汇大小确实对性能产生了负面影响。此外，这种影响不能仅通过增加序列大小来解释，因为二进制曲线较低。

8. 结论

我们集中在使用 Transformer 架构进行基本的计数任务。当模型的维度足够大时，我们展示了这个任务可以通过让 Transformer 计算输入序列的直方图来轻松实现。对于较小的维度，我们提供了理论支持，表明单层 Transformer 无法实现此功能。我们的实证结果支持这一阶段过渡。理解 Transformer 的这些限制对于开发新的架构至关重要。例如，我们的结果表明，从某种意义上讲，除非大幅增加架构的规模，否则 Transformer 无法在长上下文中进行任意精确的计数。具体而言，这表明对于计数任务，将工作委托给不具有相同限制的工具（如代码执行）可能是重要的。

9. 限制

虽然我们提供了关于计数的上界和下界的首次结果，但这些结果尚未达到理想的紧（tight）界限。具体来说，我们展示了对于 MFE 和单层 Transformer，当 d<m 时无法实现，但未展示多层（例如，两层）时的情况，尽管我们猜测这是正确的。证明这一点将需要新颖的技术工具，因为尚不清楚通信复杂度论证是否可以扩展到这种情况。对于 QC，我们展示了基于倒数（inversion ）的架构在单层情况下具有固有的限制，在这里证明额外层的下界也很有趣。在实证评估方面，我们将训练实验限制在小型架构，但探索这些任务对于更接近实际使用中的模型将很有趣。此外，观察预训练模型在微调后对这些任务的表现也很有趣。最后，使用机制可解释性方法来检查实际在训练的 Transformer 中实现了哪些计算（无论是预训练的语言模型还是从头开始的计数模型）也是很有意义的。

论文地址：https://arxiv.org/abs/2407.15160