1. The model takes the entire (or entirely changed) input context. 2. It runs a full forward pass through all layers, recomputing keys (K) and values (V) for every token and attention head. 3. The freshly computed states repopulate the KV cache. 4. The model emits the first token and moves to the decoding phase using the reconstructed cache. Because this is a full prefill, attention cost scales quadratically with context length, and the whole pass is repeated whenever the prior cache was invalidated.
When the KV cache becomes stale or unavailable (memory eviction, context edit, prefix change, model switch), decoding cannot continue from an incorrect or missing cache. Re-prefill guarantees correctness by reconstructing the KV states from scratch — at the cost of time and compute.
Every context edit or cache eviction forces a full re-prefill, significantly raising time-to-first-token (TTFT).
Attention cost in prefill grows as O(n²), so re-prefilling a long context is especially expensive.
It was shown that re-prefill after a model switch can be skipped by transferring the KV cache between same-family models — 2.7–25× faster than re-prefill.
Time complexity: O(n² · d). Space complexity: O(n · d · L).
Prefill is dense compute: all context tokens pass through all layers in a single pass.
Unlike sequential decoding, prefill (and thus re-prefill) processes all context tokens in parallel in a single forward pass.
Re-prefill is compute-bound and dominated by matrix multiplications (GEMM), which map ideally onto GPU tensor cores.
