Transformer attention scaling with sequence length is quadratic in the standard formulation. The FlashAttention paper states that the time and memory complexity of self-attention are quadratic in sequence length (arXiv:2205.14135). Whether that term matters in practice depends on what is measured (FLOPs, materialised memory or per-token reads), which phase runs (training, prefill or decoding), which kernel executes the attention, and the model's width. Here n is sequence length in tokens, d is the per-head dimension, and d_model is the model width.
What grows quadratically, and what does not
The n² term comes from the QKT product, which produces an n × n score matrix, and from multiplying that matrix by V. The softmax over the same matrix is also quadratic. A per-head breakdown in arXiv:2601.03329 puts QKT and attention-times-V at O(n²d) each and the softmax at O(n²), while the projections cost O(n · d_model · d). The projections and the MLP that follows attention grow linearly in n. Linformer frames the quadratic time and memory of standard attention as the problem and replaces it with a low-rank projection whose complexity is linear in n (arXiv:2006.04768).
Per-head and per-layer arithmetic
A secondary practitioner write-up gives a per-layer cost of roughly 24nd² + 4n²d: 8nd² for attention projections, 16nd² for a SwiGLU MLP and 4n²d for the attention core. The constants depend on architecture. This source has not been checked against a primary paper.
Two crossovers follow from that formula. Setting the core equal to the projections (4n²d = 8nd²) gives n = 2d. Setting it equal to the projections plus the SwiGLU MLP (4n²d = 24nd²) gives n = 6d. Both values are the author's arithmetic, not findings from a paper. The second point is not where the core equals the whole layer. The whole layer includes the core, so the core alone never equals it. The 6d point compares the core with the other terms combined. State which comparison you mean.
Conditions that move the crossover
A crossover is a function of conditions, not a constant. Under the formula above, the 2d and 6d points move to longer sequences as d grows, so wider heads push the quadratic term's dominance later. Other conditions matter too:
- Measured range. A benchmark in arXiv:2210.07661 fits cost curves to quadratic and linear forms and defines an 'efficiency length' at their intersection. That value depends on the implementation and on the range measured.
- Kernel. Attention FLOPs are set by the formulation. Memory traffic is not. The materialised n × n matrix is what makes the quadratic term expensive in memory, so a kernel that avoids it moves the memory and wall-clock crossover.
- Small-scale measurements. A Stanford CS224N course project found no clear quadratic runtime trend on GPU for input lengths of 400 to 800 (project report). It is one small project and should not be generalised. It does show that other costs can hide the quadratic term at moderate lengths.
Prefill, decoding and training
Prefill, the pass over the prompt, computes attention over all prompt pairs, so its attention work is quadratic. During decoding, a KV cache holds keys and values for prior tokens, and each new token attends over that whole cache. Per-token attention work is therefore linear in context length. Generating a long completion is quadratic overall, because each token attends over a longer cache than the one before it. A vLLM blog post describes the same split between quadratic prefill and linear per-token decoding.
The cache's memory grows with context length and batch size, since it stores keys and values for every prior token of every sequence. Grouped-query and multi-query attention reduce the number of key-value heads and so shrink the cache, but they leave the n² attention work unchanged. Sliding-window attention bounds the number of retained tokens (Raschka, KV cache FAQ). The sources reviewed here do not cover gradient memory or activation checkpointing at long sequence lengths, so treat any training-time claim as open. For serving economics, see per-token inference cost.
What FlashAttention changes, and what it does not
FlashAttention computes exact attention. It avoids materialising the n × n matrix in slow GPU memory, so its memory use is linear in n, and it reduces high-bandwidth-memory (HBM) traffic. It does not reduce the FLOP count, which remains quadratic. The paper reports up to a 7.6x speedup on the attention computation for GPT-2 (arXiv:2205.14135). This article has not checked the sequence lengths and hardware behind that figure against the full paper, so quote it only with those conditions once verified. A secondary Medium summary claims faster runtime than PyTorch and Megatron implementations up to 64K tokens. That claim is unverified and excluded here.
Approximate and alternative attention
- Linformer uses a low-rank projection to reach linear complexity.
- Linear attention replaces the softmax kernel with a feature map so that cost is linear in n (arXiv:2511.05560).
- Sliding-window attention bounds the tokens retained, as above.
- Sparse attention is sub-quadratic but lossy for all-pairs relationships and typically needs more layers to reach full receptive fields. The only source located is a patent document (US patent document), so its authority is limited.
According to the FlashAttention paper, many approximate methods reduce compute to linear or near-linear but show no wall-clock speedup against standard attention. They have also not gained wide adoption (arXiv:2205.14135). Whether the quality cost is acceptable is contested. One 2025 paper reports that linear-attention and other alternatives have generally been weaker than standard Transformer LLMs, possibly on math and reasoning. That is one paper's framing, and results vary with model scale and training budget (arXiv:2512.10411).
Theoretical limits are conditional. One paper argues that a specific attention-related task cannot be solved in truly subquadratic time by any algorithm, and that this applies to any subquadratic model, including Mamba-style alternatives (arXiv:2410.04271). The result rests on complexity assumptions this article has not verified. Another paper gives lower bounds on self-attention complexity in several scenarios and notes that most approximations lack rigorous error guarantees (arXiv:2209.04881), again subject to unverified assumptions.
Open questions
- Causal versus bidirectional differences were not researched here.
- Training-time memory at long context is thinly covered.
- Current GPU-specific numbers are mostly vendor material and were not verified.
- Log-linear attention claims O(T log T) computation and O(log T) memory (arXiv:2506.04761). That rests on a single study.
- Hybrid architectures are described as a current trend only in low-quality sources, so that trend is unverified.
When you quote a crossover, state the width, phase, kernel and measured range. When you quote a speedup, state the sequence length, hardware and the paper's own figure.