提出新型注意力机制ANNA，突破传统Transformer的计算瓶颈。
Fast attention mechanisms: a tale of parallelism
- 采用近似最近邻策略降低注意力计算复杂度
- 可在近似最优深度完成匹配和多跳推理任务
- 为高效注意力模型提供统一理论分析框架
Transformers虽具备模拟大规模并行计算（MPC）算法的能力，但其二次时间复杂度严重制约可扩展性。本文提出一种名为近似最近邻注意力（ANNA）的高效注意力机制，实现次二次时间复杂度。我们证明，ANNA-Transformer（1）在表达能力上保持与标准注意力相当，能匹配MPC算法性能；（2）可近乎最优地解决匹配2（Match2）和k跳推理（k-hop）等关键推理任务。通过MPC框架，进一步证明常数深度的ANNA-Transformer可模拟常数深度低秩Transformer，从而为一大类高效注意力近似方法提供统一的分析视角。
原文摘要 · Abstract (English)
Transformers have the representational capacity to simulate Massively Parallel Computation (MPC) algorithms, but they suffer from quadratic time complexity, which severely limits their scalability. We introduce an efficient attention mechanism called Approximate Nearest Neighbor Attention (ANNA) with sub-quadratic time complexity. We prove that ANNA-transformers (1) retain the expressive power previously established for standard attention in terms of matching the capabilities of MPC algorithms, and (2) can solve key reasoning tasks such as Match2 and $k$-hop with near-optimal depth. Using the MPC framework, we further prove that constant-depth ANNA-transformers can simulate constant-depth low-rank transformers, thereby providing a unified way to reason about a broad class of efficient attention approximations.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。