Sequence Length Math

Two terms, two exponents

Take one transformer block: model width d, sequence length s, batch 1, multi-head attention, an FFN of width 4d. Counting a multiply-add as 2 FLOPs, the forward pass decomposes into terms that are linear in s and terms that are quadratic:

Q,K,V projections   3 · 2sd·d   =  6 s d^2
output projection        2sd·d   =  2 s d^2
FFN (two 4d matmuls)    2·2s·4d·d  = 16 s d^2
                                   ----------
linear total                        24 s d^2

QK^T  (scores)          2 s·s·d    =  2 s^2 d
A·V   (weighted sum)    2 s·s·d    =  2 s^2 d
                                   ----------
quadratic total                      4 s^2 d

Note what is not quadratic: the Q/K/V and output projections are per-token matmuls, so they grow linearly like the FFN does. Only the two operations that touch every pair of positions — forming the score matrix and applying it — carry s². Swapping the FFN for SwiGLU changes nothing structural: three matrices at d_ff = 8d/3 gives 2 · 3 · s · d · (8d/3) = 16 s d² again.

Where the crossover sits

Divide the two totals and the whole question collapses to one ratio:

quadratic / linear  =  4 s^2 d / (24 s d^2)  =  s / (6d)

crossover:  s* = 6d

Below s = 6d the model is dominated by its per-token matmuls; above it, by pairwise attention. The numbers are unintuitive. For d = 768 the crossover is s* = 4608. For d = 2048 it is 12,288. For a frontier-width d = 8192 it is 49,152 — which is why large models can run 32k contexts while spending most of their FLOPs on the FFN, and why the quadratic scare story is really a small-model problem.

Two cautions on reading this. First, s* is where the quadratic term equals the linear term, not where ‘attention is half the cost’ — attention including its own projections is about two-thirds of the block at that point. Second, grouped-query attention does not move s*: sharing KV heads shrinks the cache, but every query head still forms its own s × s score matrix.

Prefill: the quadratic term, paid all at once

Prefill is the forward pass over the prompt. All s tokens go through together, so the matmuls are large GEMMs with high arithmetic intensity and the phase is compute-bound. Its cost is the block formula times layers:

prefill FLOPs  ≈  L · (24 s d^2 + 4 s^2 d)
               =  2 · N · s     +  4 L d · s^2

The first form is the honest one; the second shows that the familiar 2Ns rule of thumb (N = non-embedding parameters) is only the linear half. Quoting 2Ns alone understates prefill by a factor of 1 + s/(6d) — a rounding error at 1k tokens, 4.6× at 32k for a 1.5k-wide model.

The practical consequence is that prefill is where long context hurts first and hurts visibly: it is a single blocking wait before the first token appears, and it is the term that grows superlinearly. Doubling the prompt does not double time-to-first-token; it roughly triples it once you are past s*.

Decode: linear per step, quadratic in aggregate

Decode is the opposite regime. Each step processes exactly one token, so every matmul is a matrix-vector product: roughly one FLOP per byte loaded, which makes decode memory-bandwidth-bound. Per generated token you re-read the entire weight matrix set plus the entire KV cache.

decode FLOPs/token  ≈  2N + 4 L d · s      (linear in s)
bytes read/token    ≈  weight_bytes + kv_bytes(s)

So a single decode step is only linear in context length. The quadratic reappears in aggregate: generating T tokens after a prompt of s costs Σ_t 4Ld(s+t) ≈ 4Ld(sT + T²/2), quadratic in the generation length. A 4k-token answer is not four times a 1k-token answer.

This asymmetry is why the two phases want different optimisations. Prefill responds to better FLOP throughput — fused kernels, quantised GEMM, more cores. Decode responds only to moving fewer bytes: smaller weights, smaller cache, fewer KV heads. Tuning the wrong one is the most common wasted effort in CPU inference work.

The KV cache in bytes

The cache holds one key and one value vector per layer per token. The exact size, with no hand-waving:

kv_bytes = 2 · b · s · L · n_kv · d_head · bytes_per_elem
     2 = one K plus one V
     n_kv · d_head = the KV width (= d under plain MHA)

Everything on the right is fixed at model-build time except b and s, so cache size is strictly linear in sequence length — the quadratic lives in compute, not here. That linearity is deceptive, though, because the constant is large. Reference model for the rest of this article: L = 28, d = 1536, 12 heads of d_head = 128, MHA, FFN 4d, giving N ≈ 12Ld² = 0.79B non-embedding parameters. In fp16 that is 2 × 28 × 1536 × 2 = 172,032 bytes — 168 KiB per token. Grouping to 2 KV heads divides that by 6; int8 quantisation halves it again.

The same model at four sequence lengths

Holding that reference model fixed and sweeping s makes the two growth rates concrete. Crossover is s* = 6d = 9216.

Read the columns against each other. Memory grows 64× across the sweep, exactly with s. Prefill FLOPs grow 276×. And at 32k the fp16 cache alone is 5.64 GB — more than ten times the 0.45 GB the weights occupy at 4 bits. Past the crossover the cache, not the model, is the memory footprint.

Activation memory: the term that kills training

Training is where sequence length bites hardest, because backward needs the forward activations. The lethal one is the score matrix. Materialised, it is b · n_heads · s² elements per layer. For the reference model at s = 8192, batch 1, fp16:

12 · 8192^2 · 2 bytes  =  1.61 GB  per layer
× 28 layers          =  45 GB  for the scores alone

Everything else is linear and comparatively cheap: the per-token activations are s · d elements, 25 MB per tensor here, so gradient checkpointing at layer boundaries costs about 705 MB total. FlashAttention removes the 45 GB entirely by tiling the softmax and never writing the s × s matrix to memory — attention activation drops to O(s · d). That single change is what made long-context training practical; without it, memory, not FLOPs, sets your context limit.

Why doubling context more than doubles cost

Four effects compound, and only the first is the famous one.

The quadratic term. Prefill for the reference model goes from 24.5 TFLOP at 8k to 72.2 TFLOP at 16k — a 2.9× jump for a 2× length.

Batch collapse. Activation and cache memory scale with b · s, so under a fixed memory ceiling doubling s forces you to halve b. Tokens per step stay flat while per-token cost rises, so throughput falls even though nothing got slower per FLOP.

Decode drag. Every subsequent generated token reads a cache twice as large, so the whole generation slows, not just the prefill.

Cache-hierarchy exit. A working set that fit in L2/L3 at 4k spills to DRAM at 8k, and effective bandwidth drops by an order of magnitude — a discontinuity no FLOP count predicts.

Choosing a context ceiling on a CPU budget

On a CPU-hosted SLM the useful question is inverted: given the machine, what is the largest s worth supporting? Two constraints bind, and the tighter one usually surprises people. Assume 16 GB of RAM with ~8 GB free, 20 GB/s of usable bandwidth, the reference model at 4 bits (0.45 GB), and a 100 ms/token latency target.

memory ceiling:   8e9 / 172,032          ≈  46,500 tokens
latency ceiling:  budget = 0.1s · 20e9 = 2.0 GB/token
                  (2.0e9 - 0.45e9) / 172,032  ≈  9,000 tokens

Latency binds five times tighter than capacity. You can hold 46k tokens and still be unable to use them at a tolerable speed — the failure mode is a model that answers, slowly, rather than one that crashes. Shrinking bytes-per-token is the only lever that moves both ceilings at once: 2 KV heads plus int8 cache is a 12× reduction, which is the difference between a 9k and a 100k practical ceiling. Set the limit from that arithmetic, not from the config file.