Efficiently Approximating Attention Is Hard
preprint
Límites de complejidad para aproximar uniformemente la atención softmax, incluyendo preprocesamiento de la caché KV y recuperación dispersa de claves.
Recursos
Resumen
Bajo supuestos estándar de complejidad, el artículo descarta algoritmos verdaderamente subcuadráticos con garantías uniformes no triviales de aproximación aditiva o relativa para la atención softmax en el régimen de parámetros estudiado. Las cotas también incluyen el preprocesamiento polinómico de la caché KV y la recuperación de pocas claves con gran peso de atención. Los resultados delimitan las garantías que deben cumplirse para cualquier entrada.
Cita
@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}
}