简洁的一层注意力模型可计算函数，但依赖输入表示方式。
Concise One-Layer Transformers Can Do Function Evaluation (Sometimes)
- 用单层注意力结构实现函数值计算，仅在特定输入编码下有效。
- 两层结构可在更难的输入表示下完成函数评估任务。
- 理论结果与实验学习能力基本吻合，适合关注模型表达力的研究者。
尽管变换器在多种任务中表现优异，但其作为计算模型的基本性质仍不明确。本文研究变换器的表达能力，聚焦于其在给定输入下评估从 $[n]$ 到 $[n]$ 的任意函数的能力。我们证明：在输入以特定方式编码时，具有多对数复杂度约束的简洁一层数变换器（即头数、嵌入维度与精度乘积为 polylog）可完成该任务；但在输入与输出值仅通过不同位置编码时则不行。而简洁二层变换器即使在更困难的输入表示下也能完成该任务。实验表明，理论上可计算的内容与实际可学习内容存在大致对应关系。
原文摘要 · Abstract (English)
While transformers have proven enormously successful in a range of tasks, their fundamental properties as models of computation are not well understood. This paper contributes to the study of the expressive capacity of transformers, focusing on their ability to perform the fundamental computational task of evaluating an arbitrary function from $[n]$ to $[n]$ at a given argument. We prove that concise 1-layer transformers (i.e., with a polylog bound on the product of the number of heads, the embedding dimension, and precision) are capable of doing this task under some representations of the input, but not when the function's inputs and values are only encoded in different input positions. Concise 2-layer transformers can perform the task even with the more difficult input representation. Experimentally, we find a rough alignment between what we have proven can be computed by concise transformers and what can be practically learned.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。