Easier to read with cream paper, a tint, more contrast or larger text? Choose your colours and text, once, for every page.

Free lesson

How a KV cache speeds up generation

After this lesson: I can work out how much work a KV cache saves and how much memory it costs.

60 min lesson2 commandsLLM inference lab: a tiny language model on a CPU, with a KV cache, batching and int8

Why read the same words twice?

A KV cache is the store of keys and values a language model keeps for the tokens it has already read. It saves the model reading the whole text again for each new token.

Without one, writing a long reply gets slower with every word. With one, the work per token stays small, and the price is memory.

By the end of this lesson

Note

I can work out how much work a KV cache saves and how much memory it costs.

Key words

WordWhat it means
Keywhat a token offers to attention
Valuewhat a token passes on through attention
KV cachethe stored keys and values of earlier tokens
Rowone token's key and value in one layer
Layerone block of the model; each has its own cache
Context lengthhow many tokens the model reads at once

The cells students fill in are left blank in this preview.

Old keys and values never change

In attention, each new token compares its query with the key of every earlier token, then mixes their values. A token only looks backwards, so an earlier token's key and value never change once made.

Without a cache, each pass works them all out again from the start. With a KV cache, each pass works out only the new token's key and value and adds them to the store.

Generate with and without a cache

Command
docker exec jupyter python3 steps/cache.py

Shown here, not run. Press Start lab to type it into your own lab’s terminal.

Worked example: 32 characters after a 12-character prompt

WayTextKey and value rowsMultiply-adds
No cacheon the mat. the dog sathe sat ar8801,193,056
KV cacheon the mat. the dog sathe sat ar43135,584

The cells students fill in are left blank in this preview.

Without a cache, the work keeps growing

Pass 1 reads the 12 prompt tokens. Pass 2 reads 13. Pass 32 reads 43. The rows add up to 880. With a cache the rows are 12 for the prompt, then one a pass: 43.

The longer the reply, the bigger the gap. Doubling the reply more than doubles the work with no cache.

Try it: count the rows with no cache

Code: python
# Pass i reads the prompt and the i tokens made so far, unless a cache keeps them.
prompt = 12
new = 32
rows = 0
for i in range(new):
    rows = rows + prompt + i
print("rows worked out with no cache:", rows)
# Change new to 64. Does the total double, or more than double?

A common mistake

Warning

Many people think a KV cache stores past answers, like a web cache, so a repeated question is free. It stores the keys and values of the tokens in this one request. It is built during prefill and thrown away when the request ends.

The cache costs memory for every token

Each token keeps a key and a value in every layer. In the lab's model that is 2 lists of 16 numbers, 4 bytes each: 128 bytes a token.

A real model has many layers and heads. One with 32 layers, 8 key-value heads of width 128 and 2-byte numbers keeps 131,072 bytes a token, 128 KB. Eight thousand tokens is about 1 GB, for one user.

Watch the cache fill up

Command
docker exec jupyter python3 steps/cachemem.py

Shown here, not run. Press Start lab to type it into your own lab’s terminal.

Try it: the size of a real cache

Code: python
# Keys and values: 2 of them, for every layer and every key-value head.
layers = 32
kv_heads = 8
head_dim = 128
bytes_each = 2
per_token = 2 * layers * kv_heads * head_dim * bytes_each
print("bytes a token:", per_token)
print("8,000 tokens, in GB:", round(per_token * 8000 / 1024 ** 3, 2))
# Try bytes_each = 1, as a quantised cache would be.

About this lab and its source: LLM inference lab: a tiny language model on a CPU, with a KV cache, batching and int8

Teaching a class? Set this module for your students with a teacher guide, marked assignments and a lab for every student.