有效地近似注意力很困难

Softmax 注意力在现代机器学习中无处不在，但其与序列长度的二次缩放使其成本高昂。为了降低这种成本，通常使用快速算法来近似注意力，这会产生错误，但在实践中和某些输入上仍然可以表现良好。与此同时，注意力应用的日益多样化使得不依赖于特定输入结构的近似保证成为引人注目的目标。对于所有输入的这种统一保证，已知的运行时下限排除了接近精确注意力的快速算法，但保留了实际上重要的制度：是否存在一种有效的算法，甚至具有适度的统一近似保证？我们对这个问题的回答是否定的。在标准复杂性理论假设下，没有真正的二次算法可以在所有输入上统一地通过任何非平凡的加法或相对保证来近似注意力。这种不可能性存在于最温和的参数机制中，已知算法尚未在近线性时间内实现强近似保证，并且扩展到实际相关的松弛：即使在 KV 缓存的多项式预处理之后，没有有效的算法可以获得非平凡的均匀近似保证，或识别在稀疏性下受到大量关注的一小组密钥。总的来说，我们的结果解决了均匀注意力近似的计算限制。