arXiv:2501.19215v2 Announce Type: replace-cross 摘要：我们提出了一种新的方法来评估Transformer的理论极限，使我们能够证明一维软最大Transformer在无限精度情况下的一系列下限。我们为三种需要高级推理的任务建立了这些界限。第一个任务，Match3（Sanford et al., 2023），要求查看所有三元组的位置。第二个和第三个任务涉及基于组合性的推理：一个是函数的组合（Peng et al., 2024），另一个是二元关系的组合。我们正式证明了一维软最大Transformer无法解决这些任务中的任何一个。为了克服这些限制，我们引入了Strassen注意力机制，并证明了通过这种方法，一维Transformer原则上可以解决所有这些任务。我们还展示了这种机制具有亚立方时间复杂度，使其比以前提出的类似机制（如高阶注意力，Sanford et al., 2023）更具可扩展性。为了补充我们的理论发现，我们实验研究了Strassen注意力机制，并将其与标准（Vaswani et al., 2017）、高阶注意力（Sanford et al., 2023）以及三角注意力（Bergen et al., 2021）进行了比较。我们的结果有助于解开这些注意力机制的异同，突显了它们的优势和局限性。尤其是，Strassen注意力机制在所有任务中显著优于标准注意力机制。总体而言，理解理论限制可以指导研究朝着更具可扩展性的注意力机制发展，以提高Transformer的推理能力。