Efficiently Approximating Attention Is Hard
preprint
Complexity-theoretic limits on uniformly approximating softmax attention, including KV-cache preprocessing and sparse key retrieval.
Resources
Summary
Under standard complexity assumptions, the paper rules out truly subquadratic algorithms with nontrivial uniform additive or relative approximation guarantees for softmax attention in the studied parameter regime. The lower bounds also cover polynomial preprocessing of the KV cache and retrieval of a small set of heavily attended keys. These results clarify the limits of guarantees that must hold for every input, rather than only for favorable data distributions.
Citation
@misc{haverbeck2026attentionhard,
author = {Haverbeck, Lukas and Amo Alonso, Carmen and Posada-Moreno, Andres Felipe and Trimpe, Sebastian and Pavone, Marco},
title = {Efficiently Approximating Attention Is Hard},
year = {2026},
eprint = {2609.37261},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.37261}
}