Md. Asif Uddin

Proposition 524 of 39 in the corpus

Constant path length is bought with a quadratic score matrix.

Every pair of positions gets a score, so time and memory grow as the square of the sequence length. This is the price of the property that makes attention worth having.

Depends on

The attention score matrix at three sequence lengthsThree square grids of scores, for sequences of four, eight and sixteen tokens. Each doubling of the sequence length quadruples the number of scores, because every token is compared against every other.one score per pair of positionsn = 416 scoresn = 864 scoresn = 16256 scoresPath length is constant — any token reaches any other in one step — and the square is what it costs.
Fig. 5 — The score matrix at three sequence lengths. Constant path length between any two positions is bought with an area that grows as the square of the sequence.

Demonstration

The score matrix has one entry per ordered pair of positions: n² entries for a sequence of length n. Doubling the context quadruples it. At n = 1024 that is about a million scores per head per layer; at n = 8192, sixty-seven million.

It is worth separating two costs that are often conflated.

Arithmetic is O(n²d) — the two matrix multiplications, QKᵀ and the weighted sum of values. Accelerators are good at this, and it is rarely the binding constraint at moderate lengths.

Memory traffic is the real problem. A naive implementation materialises the full n × n matrix in high-bandwidth memory, writes it, reads it back for the softmax, writes again, reads again for the multiplication by V. The arithmetic is fast and the reads and writes are not. FlashAttention’s contribution is not a different attention but the same attention computed in tiles that stay in on-chip memory, so the n × n matrix is never written out. It is exact, and it is faster because it moves less.

Approximate schemes attack the n² directly — sparse patterns that score only selected pairs, low-rank factorisations, kernel approximations that avoid the softmax. They trade exactness for scale, and the survey literature is largely a record of how often that trade fails to pay on real tasks.

Inference has its own version of the problem. The KV cache — keys and values retained for every position generated so far — grows linearly with context and is multiplied by layers, heads and batch. For long conversations it exceeds the model weights, which is why grouped-query and multi-query attention exist: sharing keys and values across heads shrinks the cache, at a cost in quality that is usually small.

Corollary

Context length is not a single number a model either has or lacks. It is a statement about how much memory the deployment can afford at serve time, and it interacts with batch size directly: doubling the context can mean halving the number of concurrent users.

Sources