Rethinking Attention with Performers

Attention is O(n^2) in time and memory. To go linear one must approximate the softmax kernel, but existing approximations either assume sparsity or low-rankness - priors that rarely hold for attention - and their accuracy was never checked at real scale.

FAVOR+ (Fast Attention Via positive Orthogonal Random features): the softmax kernel is approximated by a positive random-feature map of a randomised orthogonal matrix, making the attention matrix an unbiased estimator of the true softmax attention. Unbiasedness, uniform convergence and low estimation variance are all proved. The approximation needs NO sparsity or low-rankness assumption, which is the specific gap the paper closes.

NOT A THROUGHPUT CLAIM, and this is the honest reading of the abstract. Performer's claims are about EXPRESSIVITY and comparability: 'we demonstrate competitive results with other examined efficient sparse and dense attention methods' across pixel-prediction, text and protein-sequence tasks, plus the theoretical guarantees. The abstract does attach a number to one capability - protein language-model code and the Google AI blog are referenced - but no linear-vs-quadratic wall-clock multiple with a named baseline and hardware appears. Any specific Performers speedup figure in circulation comes from the blog post, not this paper.

arXiv ID 2009.14794 verified via abs-page citation_title/citation_date on 2026-10-03; title matches. VENUE verified through three independent routes: arXiv comment 'Published as a conference paper + oral presentation at ICLR 2021'; OpenReview (api v1) returns venue='ICLR 2021 Oral', venueid='ICLR.cc/2021/Conference'; and the title appears in the official ICLR 2021 virtual papers listing (iclr.cc/virtual/2021/papers.html). venue=iclr, year=2021. Note the source record's 'Semantic Scholar publicationVenue = ICLR, year 2020/2021' resolves to 2021 as the venue year - 2020 is the arXiv v1 date. adoption=abandoned, and this required resolving a repo-identity problem worth recording: the canonical implementation is lucidrains/performer-pytorch (1.2k stars), last pushed 2022-02-02 - over four years stale; the microsoft/Performer repo does NOT exist (GitHub API 404); and no performer path exists in vLLM's 8562-file tree, SGLang's 11562-file tree, or transformers' attention modules. Contrast with the sibling lucidrains/linear-attention (845 stars, pushed 2024-05-05) which is a different author's linear-attention library - do not treat it as Performer's maintained successor. The FAVOR+ idea survives conceptually in modern linear-attention and SSM work (gated deltanet variants, flash-linear-attention), and the abandonment is about THIS method as a drop-in attention replacement, not about linear attention as a field. VENUE_TRACK BACKFILL 2026-10-04 (paper-fields pass, agent w3p): venue_track 'main'. This is STRUCTURAL rather than researched: iclr 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.