← Learn / Notebooks

Models & toolsPractitionerStudy guide

LLM Inference: Prefill, Decode and the KV Cache

Trace prompt processing, the first selected output token and subsequent decode forwards; distinguish processed cache positions from sampled tokens and calculate a synthetic KV memory budget.

Before you start: You should understand tokens, transformer layers and basic Python lists and arithmetic.

AI-assisted study notebook · Published 2026-11-14. Separate automated source and visual reviews passed; these checks are not independent expert fact verification. Source audit · Review record.

Prerequisites and inference scope

Before you start: You should understand tokens, transformer layers and basic Python lists and arithmetic.

Ordinary autoregressive decoder-only inference processes a prompt, selects a next token, then repeatedly processes the selected token to obtain another prediction. Prefill is the initial prompt forward. Its final position supplies the prediction for the first output token. Subsequent decode forwards consume new tokens while reusing cached state. [1]

Scope and limits: this guide assumes one unpadded sequence, fixed model parameters, causal attention, equal key/value dimensions and a full-history cache at every layer. It excludes speculative decoding, beam search, sliding windows, eviction, prefix sharing and distributed storage. These assumptions define the teaching example; they are not a claim that every serving engine behaves identically.

Keep three quantities separate: response tokens already selected, positions already processed, and storage positions reserved by an allocator. The trace follows the first two. The memory calculation counts occupied tensor payload. Learning to name the snapshot is the main objective: an apparently incorrect cache length can instead reflect a different point in the generation loop.

Current queries and cached keys and values

Causal attention keeps earlier positions independent of later tokens, allowing their keys and values to be reused. At a decode position, the current query attends to past and current keys and values. Each layer has its own cache; past queries are not needed for this calculation. [2]

One layer projects the current hidden state into a query, key and value. Current and past keys and values form the updated cache. Attention reads that cache using the current query.
Logical data dependencies inside one layer during decode. Purple arrows indicate data use. [2] Download editable draw.io diagram.

Text alternative: two arrows leave the hidden state for the query and key/value projections. The new pair and the past pairs feed the updated cache. The query and updated cache feed attention, whose output continues through the model. This schematic omits position transformations, normalization, residual paths and feed-forward computation. It describes dependencies, not a kernel schedule or physical memory-copy policy.

Cached K/V are computed activations, not model weights. Weights occupy a separate memory category. Reuse avoids rebuilding past K/V, but past positions still contribute to attention. [2] [3]

A prompt and three selected output tokens

Prefill builds the prompt cache and produces logits. Selecting an output from those logits is distinct from forwarding that output through the model. The next forward processes the selected token and adds its K/V. The nanoVLM tutorial and Transformers generation example expose this ordering. [1] [2]

Use invented token labels P0, P1, P2 and P3 for a four-position prompt. Prescribe selections A, B and C. These labels are synthetic identifiers, not words or predictions from a model. Snapshot the cache after a forward and then select the next token. A cached label stands for that position's K/V across all layers; actual caches contain tensors rather than strings.

Cache length after each forward, followed by token selection
ForwardNew inputCached positionsSelected next
PrefillP0 P1 P2 P34A
Decode 1A5B
Decode 2B6C

Read the trace as three events: prefill processes four prompt positions and selects A; processing A increases the cache to five and selects B; processing B increases it to six and selects C. At the last snapshot, the cached positions are P0, P1, P2, P3, A and B. Stop immediately after selecting C: the response has three tokens, but C has not entered the cache.

For prompt length P and G selected outputs, where G is at least one, this convention uses one prefill plus G − 1 decode forwards. There are G forwards in total and P + G − 1 cached positions at the end. With P = 4 and G = 3, that is three forwards and six positions. Processing C would create a seventh position and another prediction, whether or not the caller used it.

The stopping boundary matters. The nanoVLM example forwards each sampled token, including the last loop iteration; that produces an additional final forward relative to our convention. Neither snapshot should be silently substituted for the other. [1] When inspecting a trace, record the input to each forward and the token selected afterward. Avoid a bare label such as “token 3”: it could mean response index, prompt position or forward number.

KV tensor payload arithmetic

For a uniform dense cache, bytes = 2 × L × B × T × Hkv × D × s. L is layers, B is sequences, T is cached positions per sequence, Hkv is stored key/value heads, D is elements per head, and s is bytes per element. The two counts K and V. Use KV heads: grouped-query attention can have fewer KV heads than query heads. [3] [4]

Choose synthetic dimensions L = 24, B = 1, Hkv = 8, D = 64 and s = 2. One processed position requires 2 × 24 × 1 × 8 × 64 × 2 = 49,152 bytes, or 48 KiB. At 2,048 positions, multiply by 2,048 to obtain 100,663,296 bytes. Dividing by 1,048,576 bytes per MiB gives exactly 96 MiB. These are calculations for invented dimensions, not measurements of a named model.

The trace therefore occupies 192 KiB after prefill, 240 KiB after processing A, and 288 KiB after processing B. Selecting C alone adds zero KV payload in this example. Counting all seven visible prompt-and-response labels would give 336 KiB, which belongs to the later snapshot after C is processed. The 48 KiB discrepancy is one position, not a rounding error.

Under the same assumptions, three independent sequences of length 2,048 require 288 MiB. Changing stored heads from eight to 32 instead gives 384 MiB for one sequence. These proportional changes are useful arithmetic checks, but this estimate excludes weights, temporary tensors, metadata, padding, spare capacity and allocation overhead. It assumes no sharing or compression. It is not a GPU admission limit or a latency prediction.

Illustrative Python bookkeeping lab

This original Python 3 example is illustrative and synthetic. It uses the standard library, represents positions with labels, and replaces sampling with prescribed selections. It makes no model, network or file calls. Assertions specify expected bookkeeping and arithmetic; they do not establish attention correctness or serving performance. Download the complete lab.py.

"""Illustrative synthetic cache bookkeeping; no model calls."""
from math import prod


def payload_bytes(positions, batch=1, kv_heads=8):
    dimensions = (24, batch, kv_heads, 64, 2)
    for value in dimensions:
        if type(value) is not int or value <= 0:
            raise ValueError("Dimensions must be positive ints")
    if type(positions) is not int or positions < 0:
        raise ValueError("Positions must be a nonnegative int")
    return 2 * positions * prod(dimensions)


def trace(prompt, selections):
    if not prompt or not selections:
        raise ValueError("Provide prompt and selections")
    cached = []
    current_input = tuple(prompt)
    rows = []
    for selected in selections:
        # Represent completion of a forward with new inputs.
        cached.extend(current_input)
        rows.append((current_input, tuple(cached), selected))
        # The selection is processed only on a later iteration.
        current_input = (selected,)
    return rows


def main():
    prompt = ("P0", "P1", "P2", "P3")
    selections = ("A", "B", "C")
    rows = trace(prompt, selections)
    assert [len(row[1]) for row in rows] == [4, 5, 6]
    assert rows[-1][1] == prompt + ("A", "B")
    assert len(rows) == len(selections)
    expected = len(prompt) + len(selections) - 1
    assert len(rows[-1][1]) == expected
    assert trace(prompt, ("A",))[0][1] == prompt
    assert payload_bytes(0) == 0
    assert payload_bytes(1) == 49152
    assert payload_bytes(2048) == 100663296
    assert payload_bytes(2048, batch=3) == 288 * 2**20
    assert payload_bytes(2048, kv_heads=32) == 384 * 2**20
    for new_input, cached, selected in rows:
        print("Input:", new_input)
        print("Cached:", cached)
        print("Selected next:", selected)
        print("Payload KiB:", payload_bytes(len(cached)) // 1024)


if __name__ == "__main__":
    main()

Inspect the order inside trace: extend the cache, save an immutable snapshot, then prepare the next input. Appending the selected label before the snapshot would incorrectly mark it as processed. The single-selection assertion is a useful boundary check: it requires only the prompt in the cache. Try removing B and C from the selections and explain the expected state before running the example.

The payload function validates integer dimensions and allows an empty cache. It does not allocate the calculated tensors. The trace deliberately has no attention masks, logits, positional encodings or backend state. A real implementation needs its own checks; these assertions only expose mistakes in the declared counting model.

Explanatory questions

Q1 · First tokenMust A be processed before it can be selected?

No. The prompt forward supplies the prediction for A. Forwarding A supplies the prediction used to select B. Selection and processing are separate events. [1]

Q2 · QueryWhy is the current query outside the cache?

Attention uses it now; later positions have their own queries. The reusable stored tensors are keys and values. [2]

Q3 · Stop boundaryWhy are six positions cached after three outputs?

The four prompt positions, A and B have been processed. C has only been selected. Including C would describe a seventh position and a later forward, outside the stated stopping boundary.

Q4 · Head countWhat changes if 32 KV heads replace eight?

The synthetic payload quadruples to 384 MiB at 2,048 positions. That requires 32 stored KV heads; a count of 32 query heads alone does not justify the substitution. [4]

Q5 · Lab limitsWould passing these assertions validate a production cache?

No. They check label ordering and integer arithmetic. They neither compare logits nor test masks, position handling, allocations or a model backend. Treat the lab as a precise counting exercise with explicitly limited scope.

Sources and review scope

References and source links

  1. Hugging Face (2025). KV Cache from scratch in nanoVLM.
    https://huggingface.co/blog/kv-cache
  2. Hugging Face Transformers (main; undated). How caching works.
    https://huggingface.co/docs/transformers/main/cache_explanation
  3. Verma and Vaidya, NVIDIA (2023). Mastering LLM Techniques: Inference Optimization.
    https://developer.nvidia.com/blog/mastering-llm-techniques-inference-optimization/
  4. Ainslie et al. (2023; arXiv v3). GQA: Training Generalized Multi-Query Transformer Models from Multi-Head Checkpoints.
    https://arxiv.org/abs/2305.13245
Source-check disclosure

The source method maps prose, diagram relationships, table entries, code comments and answers to claim identifiers. Public originals support the mechanism; explicitly synthetic inputs and arithmetic support the worked example. Source reading is not independent expert verification.

The nanoVLM saved original and live generation section, Transformers caching sections and generation loop, NVIDIA original memory discussion, and GQA abstract were read on 14 November 2026. GQA supports only the head-count distinction. Transformers main is moving documentation, not a pinned runtime. No implementation-specific speedup is generalized.

The saved nanoVLM document is 0476d36f217f03bbd39a9a0829660254, revision 237e72b9c002317d6ed18ff426d397ff. Other citations use live public originals without saved document IDs. The data-flow diagram and bookkeeping lab are original teaching material. The lab is illustrative; it is not numerical attention code copied from a source.