Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention

Self-attention is O(N^2) in sequence length, which is prohibitive for autoregressive prediction over very long sequences.

Replace softmax(Q K^T) V with a linear dot product of KERNEL FEATURE MAPS: softmax is approximated by the (positive) feature map phi, giving phi(Q)(phi(K)^T V). Because matrix multiplication is associative, this can be reordered to compute phi(K)^T V ONCE over the prefix and then apply phi(Q) to it - reducing complexity from O(N^2) to O(N). The reordering is also what exposes the RNN equivalence: the same computation read left to right is a recurrence.

Paper's own claim (abstract): linear transformers achieve SIMILAR PERFORMANCE to vanilla transformers and are UP TO 4000x FASTER on autoregressive prediction of very long sequences. Two things to keep straight when citing this: 'up to' is a worst-case best figure at long sequence lengths, not a typical one; and the baseline is vanilla-transformer autoregressive prediction, not a tuned serving engine, so the number flatters the method relative to what FlashAttention-era kernels achieve.

arXiv ID 2006.16236 verified via abs-page citation_title/citation_date on 2026-10-03; title matches. Venue verified from the primary proceedings, not just the comment: the arXiv comment says 'ICML 2020' and the PMLR page https://proceedings.mlr.press/v119/katharopoulos20a.html carries the title 'Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention' in proceedings.mlr.press/v119 - i.e. ICML 2020. adoption=research-only: the causality trick (associativity of the feature-map product) survives in later work - Gated DeltaNet, RetNet, Mamba-2's SSD and the BASED architecture all build on it - but no engine ships a plain linear-attention path for a general dense model. The successor designs that ARE shipped (mamba, mamba-2, kimi-linear) are recorded as in-upstream-engine; this foundational 2020 paper is not. Recording the 4000x with its 'up to' and vanilla-transformer baseline is deliberate. VENUE_TRACK BACKFILL 2026-10-04 (paper-fields pass, agent w3p): venue_track 'main'. This is STRUCTURAL rather than researched: icml has no Findings volume and no workshop track in which a paper could appear, so 'main' is the only possible honest value and no per-paper evidence was needed. The field is annotated here so that 'findings' and 'workshop' remain MEANINGFUL - a filter for findings=true must return only the papers that actually are findings, which requires every other paper to be explicitly NOT findings.