Why Attention Is Quadratic

Every token attends to every other token, so the work grows with the square of the sequence length. That single sentence is where every explanation stops. This page counts the operations at six context lengths, converts each to seconds at a stated throughput, and shows why doubling context costs between 2.3 and 3.4 times as much depending on where you already are.

Where the square comes from

Attention computes a score for every ordered pair of positions. With n tokens that is n * n scores, and this is not a consequence of any particular implementation — it is what attention is defined to do.

scores  = Q @ K.T        (n x d) @ (d x n)  ->  n x n
weights = softmax(scores)                      ->  n x n
out     = weights @ V    (n x n) @ (n x d)  ->  n x d

The n x n in the middle is the entire story.

  n =   1,024  ->        1,048,576 scores
  n =   4,096  ->       16,777,216
  n =  32,768  ->    1,073,741,824
  n = 131,072  ->   17,179,869,184

Sixteen times the context, and 256 times the scores. Everything below is that table with units attached.

Counting the operations

Using the standard 2 FLOPs per multiply-accumulate, and the same model assumptions as the rest of this cluster: d_model = 4096, 32 layers, 6.97B parameters.

Per layer, over the whole sequence:

  Q @ K.T   2 * n * d * n = 2 * n^2 * d
  A @ V     2 * n * n * d = 2 * n^2 * d
                            -------------
                            4 * n^2 * d

Across 32 layers:

  4 * n^2 * 4096 * 32 = 524,288 * n^2 FLOPs

The weight matmuls, over the same sequence:

  2 * params * n = 2 * 6.97e9 * n = 1.394e10 * n FLOPs

One term is linear in n, the other quadratic. They cross where 524,288 * n^2 = 1.394e10 * n, which is n = 26,589. Below about 26k tokens the model weights dominate; above it, attention does.

Converting to seconds

Prefill of n tokens, one request, no batching.
All figures in TFLOP; seconds at 400 TFLOP/s.

    n      weights   attention    total    seconds   attn %
--------  ---------  ---------  --------  --------  -------
  4,096      57.1        8.8       65.9     0.165     13.3%
  8,192     114.2       35.2      149.4     0.373     23.6%
 16,384     228.4      140.7      369.1     0.923     38.1%
 32,768     456.7      563.0     1019.7     2.549     55.2%
 65,536     913.5     2251.8     3165.3     7.913     71.1%
131,072    1826.9     9007.2    10834.1    27.086     83.1%

A 128k-token prompt takes 27 seconds of pure arithmetic before a single output token exists, under these assumptions, and 83% of that time is attention. This is the arithmetic behind long-context prompts having a time-to-first-token measured in seconds.

Money follows from seconds by one multiplication. If you rent the accelerator at some hourly rate R:

cost = seconds * R / 3600

At an example rate of R = $3.00/hour (substitute yours):

  4,096-token prefill:  0.165 s -> $0.000138
                        per million tokens: $0.0336

131,072-token prefill: 27.086 s -> $0.02257
                        per million tokens: $0.1722

The same token costs 5.1x more to process
inside a 128k prompt than inside a 4k one.

That ratio is the honest version of the claim that long context is expensive. It is not that the provider charges more per token — most charge a flat input rate — it is that the compute per token genuinely rises with the length of the prompt it sits in.

What doubling context actually costs

The received wisdom is that doubling context quadruples cost. That is true of the attention term alone and false of the total, and the table shows exactly how the two blend.

  4,096 ->   8,192   0.373 / 0.165 = 2.26x
  8,192 ->  16,384   0.923 / 0.373 = 2.48x
 16,384 ->  32,768   2.549 / 0.923 = 2.76x
 32,768 ->  65,536   7.913 / 2.549 = 3.10x
 65,536 -> 131,072  27.086 / 7.913 = 3.42x

The multiplier starts near 2 and approaches 4.

At short context the weight matmuls dominate and the cost is nearly linear. As attention takes over, the multiplier climbs toward 4 and never quite reaches it, because the linear term never disappears. If you want one sentence: doubling context costs a bit more than double at short lengths and nearly four times at long ones.

The memory problem is worse than the FLOP problem

The n x n score matrix exists per attention head. Writing it to memory and reading it back is the reason naive attention runs out of memory long before it runs out of time.

One head's score matrix at n = 32,768, in bf16:

  32,768^2 * 2 bytes = 2,147,483,648 = 2.15 GB

Across 32 heads in one layer:

  32 * 2.15 GB = 68.7 GB

For one layer, for one sequence.

FlashAttention’s contribution is to never materialise that matrix: it processes the scores in tiles that fit in on-chip memory and accumulates the output as it goes, using the same running-maximum trick that makes softmax numerically stable so the tiles can be combined correctly. It is worth being precise about what that buys, because it is routinely overstated: FlashAttention performs the same number of floating-point operations. It reduces memory traffic from quadratic to linear, not arithmetic. Attention is still quadratic in FLOPs afterwards.

Generation, where it becomes linear again

Once the prompt is processed and the KV cache exists, each new token attends over n cached keys rather than recomputing the whole matrix. Per generated token the attention cost is linear in context, not quadratic:

Per generated token, all 32 layers:

  4 * n * 4096 * 32 = 524,288 * n FLOPs

  n =   4,096  ->   2.1 GFLOP    vs 13.9 GFLOP of weights
  n =  32,768  ->  17.2 GFLOP
  n = 131,072  ->  68.7 GFLOP    5x the weight cost

But arithmetic is not what limits generation. Every generated token must read the entire KV cache out of memory, and the cache is large:

KV cache bytes per token, multi-head attention:

  2 (K and V) * 32 layers * 4096 dims * 2 bytes = 524,288
                                                = 0.5 MiB per token

At 131,072 tokens of context: 68.7 GB of cache.

Time to read it once, at 3.3 TB/s:
  68.7e9 / 3.3e12 = 20.8 ms

Plus the weights: 13.9e9 / 3.3e12 = 4.2 ms
                                    -------
                                    25.0 ms per token = 40 tokens/s

At 4,096 tokens of context the cache is 2.1 GB:
  0.65 ms + 4.2 ms = 4.85 ms = 206 tokens/s

Five times slower generation at 128k context than at 4k, from memory traffic alone. Grouped-query attention attacks exactly this: sharing key and value heads across query heads cuts the cache proportionally. With 8 KV heads instead of 32, the cache falls to 128 KiB per token and 17.2 GB at 128k — a quarter of the traffic, and the reason essentially every long-context model uses it.

What actually reduces it

• Grouped-query attention. Fewer key and value heads than query heads. Does not change the FLOP count of the scores at all; divides the KV cache and its memory traffic by the grouping factor. Since decoding is memory-bound, this is the single largest win available.
• Sliding-window attention. Each token attends to the last w positions only, making the cost O(n * w) rather than O(n^2). At w = 4,096 and n = 131,072 that is a 32-fold reduction. The cost is that information travels between distant tokens only through the depth of the stack.
• Prompt caching. The most effective fix by a distance, because it does not reduce the work — it stops you paying for the same prefill twice. A 100k-token shared system prompt, prefilled once and reused, converts 25 seconds per request into 25 seconds once, and providers price cache hits far below fresh input.
• Sending less. The quadratic term means the savings from a shorter prompt are super-linear. Halving a 32k prompt to 16k takes prefill from 2.55 s to 0.92 s — a 64% saving from a 50% cut. Retrieval that puts 4k of relevant context in front of the model instead of 100k of everything is, on this arithmetic, a compute decision as much as a quality one.