ANNA attention achieves sub-quadratic complexity without losing Transformer expressivity, paper claims
kfountou · x · 2026-09-21
A new arXiv paper, Fast Attention Mechanisms: A Tale of Parallelism by Jingwen Liu, Hantao Yu, Clayton Sanford, Alexandr Andoni, and Daniel Hsu, introduces Approximate Nearest Neighbor Attention (ANNA), an attention mechanism with sub-quadratic time complexity.
Key results:
- ANNA-transformers retain the expressive power of standard attention, still capable of simulating Massively Parallel Computation (MPC) algorithms;
- They solve key reasoning tasks like Match2 and k-hop with near-optimal depth;
- Using the MPC framework, the authors prove constant-depth ANNA-transformers can simulate constant-depth low-rank transformers, offering a unified way to analyze a broad class of efficient attention approximations.
More from Research
- AI writing detectors flagged her lab vision post; she asks what we should actually measure — furongh · 2026-09-21
- Human-AI Collaboration Settles Major Open Problem in Multi-Winner Voting Theory — xuanalogue · 2026-09-21
- Benchmarks show coding agents edit code they shouldn't in 35-65% of cases; prompt framing is the lever — RunAI_Coder · 2026-09-21
- Stanford and Arc Institute use AI to design 16 functional phages that kill resistant bacteria — emmanuelvivier · 2026-09-21
- EvalSeal v1.5.0: open-source reproducibility receipts for LLM evals — Fit_Fortune953 · 2026-09-21
- Program-as-Weights: 0.6B model matches Qwen3-32B prompting with 1/50th memory, runs locally — yuntiandeng · 2026-09-21