In this article
Before you start
This page sits inside the transformer architecture guide, and the neural-network basics are in how neural networks work.
Why interviewers ask this
A candidate who answers "n squared" and stops usually gets the next question straight away: what would you change, and what does it cost? Candidates report this question in several forms, from asking for the complexity of attention to asking how to reduce it (reported by candidates, not a public list of companies). It separates someone who memorized a formula from someone who can say where the n squared comes from, which part of the cost a fix removes, and what the fix gives up.
A weak answer blames the softmax. A strong answer names the n-by-n score matrix. A Staff-level answer also separates arithmetic from memory traffic and from wall-clock time, and picks a fix by measurement rather than by big-O alone. The same topic appears in large language model (LLM) interview questions and in natural language processing (NLP) interview questions.
Quadratic attention from first principles
- Attention score matrix
- The attention score matrix is an n-by-n table in which entry (i, j) is the similarity score between the query of token i and the key of token j, so a sequence of n tokens produces n times n scores in every head of every layer, before the softmax turns each row into weights.
- Quadratic cost
- A quadratic cost is a cost that grows with the square of the input size, so doubling the sequence length multiplies the work by four and ten times the length multiplies it by one hundred.
- Sparse attention
- Sparse attention is a family of attention variants that let each token attend to only a chosen subset of the other tokens, such as a local window or a fixed pattern, so fewer than n squared scores are computed, at the price of dropping some token pairs.
In plain words
Picture a party with n guests. Every guest must greet every guest. Ten guests make about a hundred greetings. Twenty guests make about four hundred. Doubling the guests quadruples the greetings.
The analogy breaks in one place. Attention scores are directional. Token i scoring token j is a different number from token j scoring token i, and each token also scores itself. So the count is n times n, not n times (n minus 1) divided by 2.
In one precise sentence: the attention score matrix has n squared entries, and the standard algorithm computes and stores all of them.
Step 1: Every token is scored against every token
The score matrix is quadratic because it holds one score for every pair of tokens. Each token produces a query and a key. The matrix is the query matrix times the transposed key matrix, and it is n by n.
Keles et al. (2022) describe the self-attention mechanism as having time and space complexity quadratic in the input length. Vaswani et al. (2017), Table 1 summarize a self-attention layer as O(n²·d), with n the sequence length and d the representation dimension.
So the softmax is not the cause. The scoring, the softmax and the product with the values all run over the same n squared entries. For illustration, 1,024 tokens give 1,048,576 scores per head, and 4,096 tokens give 16,777,216: four times the length (two doublings) gives sixteen times the scores.1 You now know where n squared comes from; the next step separates the two bills it creates.
Step 2: Compute and memory are two separate quadratic bills
Attention has an arithmetic bill and a memory bill, and fixes treat them differently. The arithmetic bill is about two times n squared times d_k floating-point operations (FLOPs) for the score step in one head, counting a multiply-add as two. With the per-head size of 64 used by Vaswani et al. (2017) and 4,096 tokens, that is 2,147,483,648 operations.1
The memory bill appears when a naive implementation writes the score matrix to high bandwidth memory (HBM), a graphics processing unit's (GPU) main memory. At 2 bytes per entry (16-bit floats), one head at 4,096 tokens needs 33,554,432 bytes, and 32 heads (illustrative) need 1,073,741,824 bytes.1
FlashAttention targets the memory bill. Dao et al. (2022) describe an exact algorithm that uses tiling so the attention matrix is not read from and written to HBM, working in fast on-chip static random-access memory (SRAM). Because it is exact, it still scores every pair, so the arithmetic stays quadratic (derived from the paper's exactness claim) while the stored score memory becomes linear. That is the answer to "is FlashAttention quadratic": its compute is, its memory use is not.
Step 3: Exact kernels, sparse patterns and low-rank approximations
Cheaper attention comes in three families that touch different parts of the cost: an exact kernel, fewer scored pairs, or a smaller approximate matrix. Dao et al. (2022) prove a lower bound showing no exact algorithm can asymptotically improve on FlashAttention's number of HBM accesses over all SRAM sizes. The bound covers memory traffic only; to cut the n-squared arithmetic itself, a method must score fewer pairs or approximate the matrix, and then it is no longer exact. Keles et al. (2022) add that self-attention's time complexity is necessarily quadratic in the input length unless the Strong Exponential Time Hypothesis (SETH), a standard unproven conjecture in complexity theory, is false.
| Option | Cost per layer (n = length; d omitted where the source omits it) | Exact? | Source |
|---|---|---|---|
| Standard attention | O(n²·d) | Yes | Vaswani et al., 2017 |
| Local window of size r | O(r·n·d) | No, drops far pairs | Vaswani et al., 2017 |
| Sparse Transformer | O(n√n) | Approximates dense | Child et al., 2019 |
| Reformer, using locality-sensitive hashing (LSH) | O(n log n) | No | Kitaev et al., 2020 |
| Linformer | O(n) | No | Wang et al., 2020 |
For scale, a window of 512 at 32,768 tokens scores 64 times fewer pairs than full attention, and the Sparse Transformer pattern at 65,536 tokens scores 256 times fewer.1 The catch is quality and speed. Dao et al. (2022) note that approximate methods often fail to achieve wall-clock speedup, and Wang et al. (2020), citing Qiu et al. (2019), report one sparse method with a 2% quality drop for only a 20% speed-up.
Step 4: Different architectures drop attention
A different architecture removes the n-by-n matrix entirely instead of shrinking it. Gu and Dao (2023) propose Mamba, built on selective state space models (SSMs), and describe it as scaling linearly in sequence length without attention blocks. They report 5 times higher throughput than Transformers at inference; that is the authors' own measurement, not re-run here.
This is a different trade-off from an approximation. Attention gives every token a direct path to every other token. Vaswani et al. (2017) show that self-attention needs a constant number of sequential operations, while a recurrent layer needs O(n). A state space model carries context forward in a fixed-size state, so it gives up those direct paths. Treat it as a separate model family, not a drop-in speedup.
Step-by-step description
- Every token is scored against every token.
- Compute and memory are both quadratic.
- Exact, sparse or low-rank fixes.
- State space models drop attention.
- Every token is scored against every token, giving an n-by-n score matrix.
- The matrix creates a compute bill and a memory bill.
- Exact kernels, sparse patterns and low-rank methods change what is computed or stored.
- Different architectures drop attention.
When does the quadratic term actually dominate?
The n squared term matters only when the sequence is long compared with the model width. Per Vaswani et al. (2017), Table 1, attention costs O(n²·d) and a recurrent layer costs O(n·d²), so up to constant factors attention is the cheaper of the two when n is smaller than d.
With an illustrative width of 4,096, the ratio n divided by d is 0.25 at 1,024 tokens, 1 at 4,096 and 8 at 32,768.1 Short prompts are therefore dominated by the model's other layers, because its projection and feed-forward layers also cost on the order of n·d² per layer, so the same ratio gives the direction; long contexts are dominated by attention. This ratio ignores constants, so use it for direction, not prediction.
Text description of the diagram
- One head's score matrix is 2.1 megabytes at 1,024 tokens.
- It is 33.6 megabytes at 4,096 tokens and 134.2 at 8,192.
- It is 2,147.5 megabytes at 32,768 tokens.
For one head in 16-bit floats, the score matrix is 2.1 megabytes at 1,024 tokens, 33.6 at 4,096, 134.2 at 8,192 and 2,147.5 at 32,768, which is about 2.15 gigabytes.1
Knowing it is half the job. Saying it is the other half.
Interview Clozo is an AI interview copilot for real interview rounds: it hears the question and puts a strong answer on your screen, and you say it in your own words. See the features or how it works.
Start Free Trial →The Staff-level answer
Attention is quadratic. Why, and how would you reduce it?
Attention is quadratic because every token is scored against every other token, which fills an n-by-n score matrix. The scores, the softmax and the product with the values each cost on the order of n squared, so doubling the context quadruples the work. I have four options. An exact kernel like FlashAttention keeps the arithmetic but never writes the matrix to memory, so memory becomes linear. Sparse or windowed attention scores fewer pairs but drops some. Low-rank variants, which shrink the keys and values to a shorter length, go further and risk quality. Or I change the architecture, as Mamba does, and give up direct token-to-token paths. I would profile first, because approximations often give no real speedup.
What makes it Staff-level: it separates compute from memory, names what each fix gives up, and chooses by measurement rather than by big-O.
The rubric
| Dimension | Weak answer | Strong answer | Staff answer |
|---|---|---|---|
| Correctness | Blames the softmax for n squared. | Names the n-by-n score matrix and the O(n²·d) layer cost. | Splits the cost into compute, memory and sequential steps. |
| Depth | Lists method names without saying what each removes. | Says what each fix removes: pairs scored, memory traffic or attention itself. | Knows an exact kernel changes memory traffic, not the number of scored pairs. |
| Trade-offs | Says sub-quadratic is always faster. | Notes approximations can lose quality or give no wall-clock gain. | Chooses by measured length, hardware and quality budget. |
| Communication | Jumps to jargon. | Defines n, d and the matrix first. | Answers in under a minute, then offers depth. |
| Follow-up readiness | Calls FlashAttention linear. | Says FlashAttention is exact and memory-linear. | Compares it with windowed attention and Mamba, with each cost. |
Three variants of this question
How would you reduce the complexity of attention, and what does it cost?
Name the family, then its price: an exact kernel costs engineering effort and hardware fit, sparse patterns drop token pairs, low-rank methods compress information, and new architectures change the model. Close with the choice criterion, which is measured speed and quality at your sequence length.
How do you speed up responses without approximating attention?
Use an exact method: FlashAttention is exact, so it returns the same attention outputs while cutting memory traffic (Dao et al., 2022). When generating text, a key-value (KV) cache keeps past keys and values so they are not recomputed, and each new token is then scored against n cached keys, which costs O(n·d) instead of O(n²·d) (derived from the scoring step). Grouped-query attention (GQA) and multi-query attention share key and value heads, which shrinks the cache and the memory traffic; it changes the architecture and needs training or up-training, not the maths per pair (Ainslie et al., 2023).
What happens to the cost if the context grows from 4,096 to 32,768 tokens?
The length grows 8 times, so the score entries grow 64 times, from 16,777,216 to 1,073,741,824 per head.1 Compute and score memory follow that factor unless a fix changes it.
Common mistakes
- "Attention is quadratic because of the softmax." (wrong) The softmax is one of several steps over n squared entries. (right) "The n-by-n score matrix is the source; every step that touches it is quadratic."
- "FlashAttention makes attention linear." (wrong) It is exact and still scores every pair. (right) "It makes score memory linear and cuts memory traffic; the arithmetic stays quadratic."
- "Anything sub-quadratic is faster." (wrong) Approximations often give no wall-clock speedup and can lose quality. (right) "I would benchmark at my real sequence length before adopting one."
- "Mamba is an attention approximation." (wrong) It is a different architecture without attention blocks. (right) "It is a separate trade-off: linear scaling, no direct token-to-token paths."
Follow-up questions
How does attention work in a transformer, and why does it scale quadratically?
Each token makes a query, a key and a value; queries are scored against all keys, the softmax turns scores into weights, and the weights mix the values. The scoring step builds an n-by-n matrix, which is the quadratic part. Step-by-step detail is in self-attention.
Is FlashAttention quadratic?
Its arithmetic is, because it is exact and scores every pair; its memory for scores is linear, because Dao et al. (2022) avoid writing the matrix to HBM.
Does multi-head attention multiply the cost by the number of heads?
For the matrix multiplies, no: with h = 8 and d_k = d_model/h = 64, as in Vaswani et al. (2017), the heads together cover a model width of 512, so the arithmetic matches one full-width head.1 But each head stores its own n-by-n score matrix, so score memory and the softmax work grow with the number of heads. See multi-head attention.
Is Mamba a drop-in replacement for attention?
No. Gu and Dao (2023) present a whole architecture without attention blocks, so it changes what the model can do, not only how fast it runs.
Is self-attention always slower than recurrence?
No. From the layer costs in Vaswani et al. (2017), attention is cheaper per layer when n is smaller than d, and it needs far fewer sequential steps.
- Attention is quadratic because the n-by-n score matrix holds one score for every token pair.
- The softmax is one quadratic step among several, not the cause.
- Compute and memory are separate bills; an exact kernel mainly fixes memory.
- Sparse, low-rank and new-architecture options each give something up, and speed claims need benchmarks.
- Attention's quadratic term dominates only when the sequence is long compared with the model width.
Sources
- Attention Is All You Need (arXiv 1706.03762) — arXiv (Vaswani et al.), 12 Jun 2017
- On the Computational Complexity of Self-Attention (arXiv 2209.04881) — arXiv (Keles, Wijewardena, Hegde), 11 Sep 2022
- Reformer: The Efficient Transformer (arXiv 2001.04451) — arXiv (Kitaev, Kaiser, Levskaya), 13 Jan 2020
- GQA: Training Generalized Multi-Query Transformer Models from Multi-Head Checkpoints (arXiv 2305.13245) — arXiv (Ainslie et al.), 22 May 2023
- FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness (arXiv 2205.14135) — arXiv (Dao et al.), 27 May 2022
- Generating Long Sequences with Sparse Transformers (arXiv 1904.10509) — arXiv (Child et al.), 23 Apr 2019
- Linformer: Self-Attention with Linear Complexity (arXiv 2006.04768) — arXiv (Wang et al.), 8 Jun 2020
- Mamba: Linear-Time Sequence Modeling with Selective State Spaces (arXiv 2312.00752) — arXiv (Gu and Dao), 1 Dec 2023
