Attention layers, as commonly used in transformers, form the backbone of
modern deep learning, yet there is no mathematical description of their
benefits and deficiencies as compared with other architectures. In this work we
establish both positive and negative results on the representation power of
attention layers, with a focus on intrinsic complexity parameters such as
width, depth, and embedding dimension. On the positive side, we present a
sparse averaging task, where recurrent networks and feedforward networks all
have complexity scaling polynomially in the input size, whereas transformers
scale merely logarithmically in the input size; furthermore, we use the same
construction to show the necessity and role of a large embedding dimension in a
transformer. On the negative side, we present a triple detection task, where
attention layers in turn have complexity scaling linearly in the input size; as
this scenario seems rare in practice, we also present natural variants that can
be efficiently solved by attention layers. The proof techniques emphasize the
value of communication complexity in the analysis of transformers and related
models, and the role of sparse averaging as a prototypical attention task,
which even finds use in the analysis of triple detection.

本研究通过分析注意力层及其所在的变形器模型的表示能力，探讨这些模型相对于其他架构的优势和劣势，并重点关注了它们的内在复杂度参数，例如宽度、深度和嵌入维度。在正面方面，我们提出了一个稀疏平均任务，并证明了循环网络和前馈网络的复杂性随着输入规模的增大多项式增长，而变形器的复杂性仅随着输入规模的对数增长；此外，我们使用相同的构造来展示了变形器中大嵌入维度的必要性和作用。在消极方面，我们提出了一个三元组检测任务，其中注意力层的复杂性随输入规模线性增长；考虑到这种情况在实践中似乎很少出现，我们还提出了一些自然变种，可以通过注意力层有效地解决。证明技术强调了通信复杂度在变形器及其相关模型的分析中的价值，以及稀疏平均作为原型注意任务的作用，甚至在三元组检测的分析中也有用处。