Attention approximation cannot be efficiently guaranteed for all inputs
Efficiently Approximating Attention Is Hard
Machine LearningComputational Complexity
Summary
Calculating attention in many AI models takes a lot of time because it grows quickly with the size of input data. Some methods try to speed this up by approximating attention, but these can lose accuracy. The authors show that no algorithm can efficiently get even a rough uniform approximation of attention on every possible input unless major assumptions in computer science fail. This means that certain fast approximations with guaranteed accuracy for all cases are impossible. Their work clarifies the limits of speeding up attention calculations without losing reliability.
What this means in practice
- •For machine learning system designers: Avoid designing near-exact attention algorithms aiming for uniform speed and accuracy guarantees, as these are proven computationally impossible.
- •For natural language processing engineers: Recognize limitations when trying to uniformly approximate attention for long sequences, guiding choices toward heuristic or input-tailored methods.
A theory result. No direct application yet.
Authors
Lukas Haverbeck, Carmen Amo Alonso, Andres Felipe Posada-Moreno, Sebastian Trimpe, Marco Pavone
Abstract
Softmax attention is ubiquitous in modern machine learning, but its quadratic scaling with sequence length makes it costly. To reduce this cost, attention is often approximated with fast algorithms, which incur error but can still perform well in practice and on some inputs. At the same time, the growing diversity of attention applications makes approximation guarantees that do not depend on particular input structure a compelling target. For such uniform guarantees over all inputs, known runtime lower bounds rule out fast algorithms for near-exact attention, but leave open the practically important regime: is there an efficient algorithm with even a modest uniform approximation guarantee? We answer this question negatively. Under standard complexity-theoretic assumptions, no truly subquadratic algorithm can approximate attention with any nontrivial additive or relative guarantee uniformly over all inputs. This impossibility holds in the mildest parameter regime for which known algorithms do not already achieve strong approximation guarantees in near-linear time, and extends to practically relevant relaxations: even after polynomial preprocessing of the KV cache, no efficient algorithm can obtain a nontrivial uniform approximation guarantee, or identify a small set of keys receiving substantial attention under sparsity. Overall, our results settle the computational limits of uniform attention approximation.