标题： 任意温度下注意力的次二次算法和难度 显示英文标题

标题： Subquadratic Algorithms and Hardness for Attention with Any Temperature

摘要： 尽管Transformer架构很受欢迎，但计算Attention的标准算法在上下文长度上具有二次时间复杂度$n$。 Alman和Song [NeurIPS 2023]表明，当头维度$d = \Theta(\log n)$时，在强指数时间假设（$\mathsf{SETH}$）下，只有当输入的绝对值被$B = o(\sqrt{\log n})$界限时，才能实现次二次Attention。 等价地，当对$d=\Theta(\log n)$使用高温softmax时，才能实现次二次Attention。 这些算法的运行时间呈指数级依赖于$B$，因此它们在$B$的特定范围之外并不能导致多项式时间算法。 这自然引出了一个问题：在不施加强温度假设的情况下，何时可以高效地计算Attention？ 有快速注意力算法能够在条目大小上以多项对数时间复杂度进行吗$B$？ 在本工作中，我们解决了这个问题，并描述了在任意温度下实现快速注意力的条件。 首先，对于所有常数$d = O(1)$，我们给出了第一个次二次$\tilde{O}(n^{2 - 1/d} \cdot \mathrm{polylog}(B))$时间的注意力算法，适用于大的$B$。 即使矩阵具有较大的头维度，只要它们的秩较低，我们的结果仍然成立。 在这个范围内，我们也为注意力梯度计算提供了类似的运行时间，因此也适用于完整的LLM训练过程。 此外，我们表明对我们的算法进行重大改进是不太可能的。 特别是，我们证明了即使当$d = 2^{\Theta(\log^* n)}$时，注意力在$\mathsf{SETH}$下需要$n^{2 - o(1)}$时间。 最后，在$d = \mathrm{poly}(n)$的情况下，我们证明在流行的细粒度复杂性假设下，标准算法是最佳的。 显示英文摘要

摘要： Despite the popularity of the Transformer architecture, the standard algorithm for computing Attention suffers from quadratic time complexity in context length $n$. Alman and Song [NeurIPS 2023] showed that when the head dimension $d = \Theta(\log n)$, subquadratic Attention is possible if and only if the inputs have small entries bounded by $B = o(\sqrt{\log n})$ in absolute values, under the Strong Exponential Time Hypothesis ($\mathsf{SETH}$). Equivalently, subquadratic Attention is possible if and only if the softmax is applied with high temperature for $d=\Theta(\log n)$. Running times of these algorithms depend exponentially on $B$ and thus they do not lead to even a polynomial-time algorithm outside the specific range of $B$. This naturally leads to the question: when can Attention be computed efficiently without strong assumptions on temperature? Are there fast attention algorithms that scale polylogarithmically with entry size $B$? In this work, we resolve this question and characterize when fast Attention for arbitrary temperatures is possible. First, for all constant $d = O(1)$, we give the first subquadratic $\tilde{O}(n^{2 - 1/d} \cdot \mathrm{polylog}(B))$ time algorithm for Attention with large $B$. Our result holds even for matrices with large head dimension if they have low rank. In this regime, we also give a similar running time for Attention gradient computation, and therefore for the full LLM training process. Furthermore, we show that any substantial improvement on our algorithm is unlikely. In particular, we show that even when $d = 2^{\Theta(\log^* n)}$, Attention requires $n^{2 - o(1)}$ time under $\mathsf{SETH}$. Finally, in the regime where $d = \mathrm{poly}(n)$, we show that the standard algorithm is optimal under popular fine-grained complexity assumptions.