Research map / Architectures and efficiency / Attention and transformers

Fundamental Limitations on Subquadratic Alternatives to Transformers

ICLR 2025 · Architectures and efficiency › Attention and transformers · approach: Sparse efficient transformers for long context · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proves under SETH/OVC that document similarity (MSD/LSD and variants) needs quadratic time, so any truly subquadratic model (including Mamba and fast-attention heuristics) cannot solve it, while a single attention unit with MLPs can.

Problem

Whether subquadratic alternatives to Transformer attention (heuristic fast attention, state space models like Mamba, new attention replacements) can perform document similarity tasks that Transformers can perform.

Approach

Uses fine-grained complexity (SETH and the Orthogonal Vectors Conjecture) to show most/least similar document problems over bag-of-words embeddings require truly quadratic time, and constructs a one-layer, one-head transformer with simple MLPs that solves OV and threshold versions of MSD/LSD, separating transformers from subquadratic models.

Key results

• MSD and LSD with l = c log n (and variants) require O(n^{2-eps}) time under SETH/OVC, ruling out truly subquadratic models for them.
• A single attention unit with input and output MLPs and embedding dimension l+1 solves OV_{n,l} and threshold MSD/LSD decision variants.
• Gamma-MSD hardness holds for approximation factors up to 2^{(log n)^{1-o(1)}} with l = (log n)^{Theta(log n/(log log n)^2)}.

Surprising findings

• Hardness applies to approximate variants of the problems, so approximation or heuristic attention cannot escape the quadratic barrier for these tasks.

Limitations

• Results are conditional on SETH/OVC, which are unproven conjectures.
• Hardness applies to worst-case instances with l = Theta(log n) or larger; no empirical evaluation of actual models.
• Transformer constructions are for a simplified single-layer, single-head model.

Experimental setup

Baselines: Mamba KDEformer Reformer Hyperattention Match3 one-layer transformer result

Builds on: SETH Orthogonal Vectors Conjecture Max-IP hardness

Closest papers by meaning

• PolySketchFormer: Fast Transformers via Sketching Polynomial Kernels (ICML 2024 · similarity 0.87)
• Token Statistics Transformer: Linear-Time Attention via Variational Rate Reduction (ICLR 2025 · similarity 0.86)
• Fast attention mechanisms: a tale of parallelism (NeurIPS 2025 · similarity 0.86)
• kNN Attention Demystified: A Theoretical Exploration for Scalable Transformers (ICLR 2025 · similarity 0.85)
• InfoFlow: A Framework for Multi-Layer Transformer Analysis (NeurIPS 2026 · similarity 0.85)
• Linear Log-Normal Attention with Unbiased Concentration (ICLR 2024 · similarity 0.85)