Reproduce “Efficiently Approximating Attention Is Hard” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Lukas Haverbeck, Carmen Amo Alonso, Andres Felipe Posada-Moreno, Sebastian Trimpe, Marco Pavone
The paper reduces approximate softmax attention to approximate closest-pair search, encoding vector pairs, dummy keys, and values so normalized aggregation reveals whether a close pair exists. Under SETH, at dimension d=C_d log n and coordinate bound B=C_B sqrt(log n), no truly subquadratic algorithm achieves uniform additive error below 1/2 or relative error below 1. When either d=o(log n) or B=o(sqrt(log n)), prior methods achieve near-linear time with vanishing error.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.