Prefill is the first thing an LLM does with your prompt: it runs every prompt token through the network in a single, parallel forward pass, fills the KV cache with the keys and values of all those tokens, and emits exactly one output token — the first one. Everything after that is decode, a different beast covered by its sibling article. The two phases look like the same matrix multiplies, but their arithmetic tells opposite stories: prefill is compute-bound, decode is memory-bound. This piece works the prefill math from first principles — why one big pass is compute-bound, the FLOP cost ≈ 2 · N_params · L, the quadratic attention term that eventually takes over, how time-to-first-token (TTFT) scales with prompt length, and a worked example you can re-run with your own numbers.

What prefill actually computes

When a prompt of L tokens arrives, the model does not read it word by word. It stacks all L tokens into one matrix X: [L, d] (d = model dimension) and pushes the whole thing through every layer at once. Each layer projects X into queries, keys, and values, runs causal self-attention, then a feed-forward network — all as dense matrix multiplies over the full [L, d] block. The point of prefill is twofold. First, it populates the KV cache: the keys and values computed for every prompt position are stored so decode never has to recompute them. Second, it produces the logits for the last position, from which the first generated token is sampled.

Because attention is causal, token i only attends to tokens ≤ i, but crucially all of these dot products can still be computed simultaneously — the causal mask just zeroes the upper triangle of the score matrix. Nothing forces sequential processing during prefill; the prompt is known in full, so the hardware sees one large, highly parallel workload.

Advertisement

One pass, many tokens: why it is compute-bound

The decisive property of prefill is arithmetic intensity — FLOPs performed per byte of weight read from memory. A weight matrix W: [d, d] must be loaded from memory once. In prefill you multiply all L token vectors by that same W before you are done with it, so one load of the weights does L× as much work. Intensity scales with L: for any non-trivial prompt the machine spends its time in the multiply-accumulate units, not waiting on memory.

That is the textbook definition of compute-bound. The GEMMs (general matrix multiplies) are big and square-ish — [L, d] × [d, d] — exactly the shape GPUs and AVX/AMX CPU kernels run at peak efficiency. Contrast decode, which processes a single new token per step: there L = 1, so each weight is loaded to do one skinny [1, d] × [d, d] matrix-vector product, the intensity collapses, and the pass is memory-bandwidth-bound. Same weights, opposite bottleneck — the number of tokens sharing each weight load is the whole difference.

The FLOP cost of prefill

The dominant cost is the dense linear layers — the QKV and output projections plus the FFN. A clean, model-agnostic estimate counts every parameter as one multiply-accumulate per token, and a multiply-accumulate is two FLOPs (one multiply, one add):

C_prefill  ≈  2 · N_params · L

  N_params = number of model weights
  L        = prompt length (tokens)
  factor 2 = one multiply + one add per weight

This is the same 2 · N · tokens rule used for training's forward pass (training adds a ~2× backward term prefill does not pay). It says prefill cost is linear in prompt length and linear in model size: doubling the prompt doubles the work, and a model twice as large costs twice as much to prefill. The estimate deliberately folds the attention projection matmuls into N_params; what it leaves out is the cost of the attention scores themselves, which carry no weights — and that omission is the quadratic term we turn to next.

The quadratic attention term

Computing attention scores is not a weight multiply — it is Q K^T, a [L, d] × [d, L] product that yields an L × L score matrix, followed by softmax and the A V product back to [L, d]. Both Q K^T and A V cost ~2 · L^2 · d FLOPs per layer, so across the network:

C_attn  ≈  4 · n_layers · L^2 · d

  L^2  =  the L x L score matrix (every token pair)
  grows QUADRATICALLY with prompt length

So the full prefill cost is C_prefill ≈ 2·N_params·L + 4·n_layers·L^2·d. For short and medium prompts the linear term dominates and people happily ignore the quadratic part. But because the second term grows with L^2, there is a crossover length beyond which attention scores overtake the entire rest of the model. Setting the two terms equal gives a rough crossover at L ≈ N_params / (2 · n_layers · d) — typically tens of thousands of tokens. Past that, long-context prefill is dominated by the O(L^2) attention, which is exactly why FlashAttention-style kernels and sparse/windowed attention matter most at long context.

TTFT: time to first token

The user-facing consequence of all this is TTFT — how long from hitting enter to seeing the first token appear. TTFT is essentially the wall-clock time of the prefill pass, so it follows straight from the FLOP count divided by how fast the hardware actually runs:

TTFT  ≈  C_prefill / (P_peak · MFU)

  P_peak = peak FLOP/s of the device
  MFU    = model FLOPs utilization (fraction of peak, ~0.3-0.6)

Substituting the cost, TTFT ≈ (2·N·L) / (P_peak · MFU) in the linear regime — so TTFT scales linearly with prompt length until the quadratic attention term kicks in, after which it bends upward. This is why pasting a huge document produces a long, visible pause before the answer starts, while a short question responds almost instantly. Because prefill is compute-bound, TTFT improves with more compute (faster or more parallel hardware, higher MFU) — unlike decode's per-token latency, which is set by memory bandwidth and barely moves when you add compute.

Advertisement

A worked example

Take a 7B-parameter model with n_layers = 32 and d = 4096, a prompt of L = 2048 tokens, on a device with P_peak = 312 TFLOP/s (bf16) at MFU = 0.4.

Linear term:  2 · 7e9 · 2048        = 2.87e13 FLOP  (28.7 TFLOP)
Attn  term:  4 · 32 · 2048^2 · 4096   = 2.20e12 FLOP  ( 2.2 TFLOP)
Total:                                = 3.09e13 FLOP  (~31 TFLOP)

TTFT = 3.09e13 / (312e12 · 0.4) = 3.09e13 / 1.25e14 ≈ 0.25 s

So ~250 ms to first token, and note the attention term is only ~7% of the work at 2K tokens — the linear estimate alone would have been fine. Now stretch the prompt to L = 32768: the linear term grows 16× to ~459 TFLOP, but the quadratic term grows 256× to ~563 TFLOP — now larger than the entire rest of the model. Total prefill is ~1.0 PFLOP and TTFT climbs toward ~8 s. The lesson is concrete: at short prompts TTFT is linear and cheap; at long prompts the L^2 attention term dominates and TTFT grows faster than the prompt itself.

Chunked prefill

Two problems appear with long prompts. First, a single giant prefill can monopolize the accelerator for seconds, starving concurrent decode requests and spiking their latency — a long TTFT for one user becomes jitter for everyone. Second, the activations for a full [L, d] pass consume a lot of memory at once. Chunked prefill addresses both: split the prompt into fixed-size chunks (say 512 or 1024 tokens) and prefill them sequentially, each chunk attending to the KV cache accumulated by earlier chunks.

The total FLOP count is unchanged — you still pay 2·N·L plus the quadratic term — but the work is sliced into schedulable units. Serving systems interleave these prefill chunks with the decode steps of other requests, keeping the compute pipe full and smoothing tail latency. It is a scheduling and memory technique, not a FLOP reduction; treat it here as a pointer to how production inference stacks tame long-context TTFT rather than a change to the underlying prefill math.

Prefill vs decode, and CPU-SLM implications

It is worth stating the split plainly, because almost every inference decision flows from it. Prefill: many tokens, one pass, high arithmetic intensity, compute-bound, cost ≈ 2·N·L, sets TTFT. Decode: one token per step, low intensity, memory-bound, cost ≈ 2·N per token dominated by re-reading weights and the growing KV cache, sets inter-token latency — the sibling article covers it in full. The same GEMMs, split by how many tokens share each weight load.

For CPU-hosted small language models this cuts a useful way. Prefill is the phase a CPU handles relatively well: it is compute-bound, so wide SIMD (AVX-512, AMX) and all cores can be thrown at the big GEMMs. The catch is that a CPU's peak FLOP/s is far below a GPU's, so TTFT on a long prompt can be painful — keep prompts short, or chunk them. Decode, being bandwidth-bound, is where CPUs struggle most; but a snappy TTFT from an efficient prefill still shapes the user's first impression, so prefill efficiency is worth optimizing even on modest hardware.

Common pitfalls

Confusing the two phases' bottlenecks. Throwing more compute at a decode-bound workload barely helps, and adding memory bandwidth does little for prefill — profile which phase dominates your latency before optimizing. Ignoring the quadratic term until it bites. The tidy 2·N·L estimate is only the linear half; at long context the O(L^2) attention silently becomes the majority of prefill and the reason TTFT explodes. Assuming peak FLOP/s. Real MFU is a fraction of peak; a TTFT estimate that ignores utilization will be optimistic by 2-3×.

Finally, remember that prefill's cost is unavoidable for a fresh prompt but not for a repeated one — this is precisely what prompt caching exploits, reusing a previously computed KV cache for a shared prefix so its prefill FLOPs (and its share of TTFT) are paid only once. Whenever a long system prompt is constant across requests, caching its prefill is often the single biggest TTFT win available.

Prefill runs the entire prompt through the model in one parallel forward pass, filling the KV cache and producing the first token. Because every weight load is amortized over all L prompt tokens, prefill has high arithmetic intensity and is compute-bound — the mirror image of decode's memory-bound, one-token-at-a-time steps. Its cost is ≈ 2·N_params·L plus a quadratic 4·n_layers·L^2·d attention term that overtakes everything at long context. Time-to-first-token is just that FLOP count divided by achievable throughput, so TTFT scales linearly with prompt length — then bends upward once the L^2 term dominates. Chunked prefill re-slices this same work for smoother scheduling, and prompt caching skips it entirely for shared prefixes. Know which phase you are in, and you know which resource to spend.