OKLMdocumentation v1.0.3
On this page

ADR-0019: The paged KV cache

Records how the KV cache is split into blocks shared between sequences: the block size, the layout per layer, how quantized rows fit, the prefix hash, eviction and the copy-on-write rule, and what stays contiguous.

Status: accepted with amendments (2026-11-02), after the review of the serving specification's S0 (serving-design.md): the engine's narrow interface to the prefix map, the CPU pool's default, the block size kept off the command line until measured, the embedding-row marker in the hash from the start.

Context

The cache today is one tensor per layer of n_seq * n_ctx cells, sequence s owning cells s * n_ctx to (s + 1) * n_ctx - 1, reserved and resident from the start (oklm_context_new, model.c). A request holds -c cells whatever it uses: 4 % of them for a short chat, 34 % for an agent turn (the baseline in serving-design.md), and two requests with the same system prompt hold and compute it twice. M14 (serving_spec.md) replaces this with fixed-size blocks handed out as tokens arrive, shared between sequences with the same prefix and kept after their requests end. The layout is a convention the model library, the CPU and OpenCL attention, the server and the tests all depend on, so it is settled here before any code.

Facts the layout builds on:

  • A cell is one token's row: [head_dim, n_head_kv] values of one type, keys and values in separate tensors (ADR-0005 for the types). Quantized types (Q8_0, Q4_0, Q4_1, Q5_0, Q5_1, IQ4_NL) need head_dim % 32 == 0 and quantize along head_dim, so a row never shares a quantization block with another token.
  • Rotated caches (Walsh-Hadamard groups) are rotated before the write; the stored row is an ordinary row of its type.
  • Latent attention (DeepSeek V2, V3) stores one compressed row per token (kv_lora + n_rot values) in the key cache and reads its values from it; the value cache is one unused cell.
  • Sliding-window layers keep every cell; the window is applied in attention.
  • Layers split over devices keep their caches on their device.

Decision

  • Block size. 16 tokens by default, a context option (kv_block_size: 16 or 32), not on the command line until S6 has measured 32 against 16. Because rows are per token, a block holds whole quantization blocks at any size: no multiple of 32 is needed for quantized caches. 32 is offered for the OpenCL tiled prompt kernels, whose key tiles are 32 rows for heads up to 128 (16 for 256), should measurement show tiles crossing blocks cost more than the memory saved.
  • Layout per layer. One pool tensor per layer and kind (keys, values) of num_blocks * block_size rows, [head_dim, n_head_kv, num_blocks * block_size]: block b is rows b * B to b * B + B - 1. A token at position p of a sequence with table T lives in row T[p / B] * B + p % B (the slot mapping). The row layout is the contiguous cache's, so the existing write (oklm_cpy of a row into a view) and the step-A gather work unchanged.
    • Latent attention: the key pool only; no value pool.
    • Several devices: each device holds the pools of its layers, all with the same num_blocks; a block id means the same rows on every device, so one table serves all layers.
    • One block table per sequence, shared by every layer.
  • Sizes. Block bytes per layer: B * row_size(type_k, kvdim) for keys plus the same for values (none with latent attention). The pool's block count comes from the budget: on OpenCL what the device has left after weights, activations and the 8 % margin; on the CPU --kv-mem, by default what today's default server's cache takes (4 sequences × -c cells), independent of --parallel.
  • Allocator. A stack of free block ids, a reference count per block (int32_t, never negative), a table per sequence of up to ceil(n_ctx / B) ids. A sequence takes a new block when its last one is full; oklm_seq_truncate drops the blocks past the new end; oklm_seq_copy takes a reference on each full block of the source and copies the partial last block into a new private one.
  • Prefix hash. Only full blocks are hashed and shareable. A block's hash is a 64-bit FNV-1a over, in order: its parent's hash (a fixed seed for the first block), the block size, and for each of its B positions either the token id, or for a row given as an embedding (oklm_seq_tokens.embd, with its media) a marker byte, the media's content hash and the row's index within that media. The content hash (oklm_mm_item_hash()) is a 64-bit FNV-1a of what decides the embeddings, computed once per media: an image's size, decoded pixels and slicing side, a sound's samples; so the same picture in another file or encoding is found, and one sliced differently is not. A row given as an embedding without a media hash is unknown: its block is never hashed. Chaining the parent makes a block's identity the whole prefix before it. The context belongs to one model, cache types and rotation, so these are not hashed. A hash -> block map (open addressing) holds every hashed block; a lookup compares the stored token ids (and media hashes) too, so a 64-bit collision never attaches a wrong block.
  • Eviction. A block whose count falls to 0 keeps its rows and its hash and goes to the tail of an LRU list, still found by lookups (a hit takes it off the list). The allocator takes free blocks without a hash first, then the head of the LRU list, removing its hash from the map in the same operation. Blocks are never evicted while referenced; when nothing is free or evictable, the engine preempts (recompute).
  • Copy-on-write. Nothing writes into a block whose count is above 1 or that carries a hash. Since only full blocks are hashed and shared, and a sequence writes only past its end, the rule reduces to: a sequence's partial last block is always private, and a sequence resuming inside a shared full block (truncated into it, or a prompt that diverges inside it) first copies it to a private block.
  • What stays contiguous.
    • The contiguous cache itself, the reference and the fallback: a context with kv_blocks = 0 (the default for every caller but the server) is today's cache, bit for bit.
    • The multi-token prediction context (mtp) and the hidden-state buffer (hidden).
    • The device mirrors of weight streaming (--gpu-stream): a paged context refuses stream_batch until a mirror pool is written.
    • Activations, logits and every per-step buffer.
  • Owners. The pool, the allocator, the tables, the hash map and the LRU live in the model library (src/model/kv_pool.c), behind oklm_context_params. The server's engine decides admission and preemption and sees the map through one call (attach the cached full blocks of a prefix to a sequence, return the tokens they cover) and usage counts; it never touches hashes or the LRU.
  • Media rows. A row's key is its token and a media hash (0 for text): a media row's token is its index within the item. The batch input carries embedding rows with their hashes, the prefix calls take them (oklm_kv_prefix_cached(), oklm_seq_attach_prefix()), and a block copied on write keeps its rows' keys. Text blocks hash as they did before media rows existed. The marker was planned from the first version; it was added with the server's images and audio (S8), until then blocks holding embeddings were not hashed.

Consequences

  • Memory follows the tokens used: the same 768 MiB that holds 16 requests of Qwen2.5-0.5B today holds 65,536 tokens in 4,096 blocks.
  • A shared system prompt is computed and stored once while it stays cached, by any number of live requests; freed prefixes stay until the pool needs their blocks.
  • Attention reads keys through a table: the CPU loop and the OpenCL kernels gain an indirection per block, and a paged kernel replaces the per-sequence launches (decision 1 of serving-design.md).
  • On the CPU the paged cache is exact against the contiguous one; on OpenCL a reused block computed in another batch shape may differ in the last bits (the near-tie rule of serving-design.md).
  • Gemma 3's local layers keep every block; freeing blocks outside the window would need a table per layer group, left for later.
  • Images and audio in prompts are cacheable as soon as the server takes them, through their content hash, without hashing floats.