KV cache and context window

KV cache and context window

AlgoLab runs no language model. These twelve tokens and their query, key and value vectors were written by hand — shown in full in the Sequence tab. The cache stores exactly the vectors it is given; eviction follows one fixed rule, the oldest cached position goes first. A real cache holds far more than twelve entries, each with hundreds or thousands of dimensions, and a real context window is typically thousands of tokens wide.

at step t, cache capacity w: compute key/value for the new position only; min(t, w) dot products

Generates a short sequence of tokens one at a time, the same autoregressive step beam search and attention both use, and computes the cost of that generation two ways. Without a cache, every step recomputes the key and value vectors for the whole sequence so far. With a cache, each step computes only the new token’s key and value vectors and reuses everything already in the cache. A cache has a maximum size; once generation would push it past that size, the oldest cached entry is evicted — a sliding context window.

Why it matters, and what it costs

This is the mechanism behind why a long conversation with a language model gets slower and more memory-hungry as it grows, and why systems bound how much of a conversation they keep in the cache at once. Caching avoids redoing key and value computations that would otherwise be repeated at every step; a bounded cache additionally caps how much the per-step cost can grow, at the price of no longer attending to positions once they have been evicted.

How it works

• Start with an authored sequence of twelve tokens, each with its own query, key and value vector.
• At each step, compute the key and value vectors for the token just generated. Without a cache, redo this for every earlier position too; with a cache, reuse what was computed before and compute only the new one.
• Append the new key and value vectors to the cache. If the cache is now over its capacity, evict the oldest entry.
• Score the new token’s query against the key of every position currently available: every position so far, without a cache; only what remains in the cache, with one.
• Add up both scenarios’ cost at every step to see how the running total grows in each case.

Worth noticing

• A repeated token gets its own, different cached vectors at each position it appears: the cache is indexed by position in the sequence, not by which word is there. A test checks this directly on the shipped data, where the word “you” appears twice.
• Caching avoids exactly t − 1 key/value computations at step t, whatever the cache capacity is — caching always needs exactly one new computation, regardless of what is or is not evicted.
• A cache with no capacity limit does not, by itself, change how the total cost grows over a long run: the per-step cost of scoring the new query against everything cached so far still grows with the step, which is the part caching does not remove. It is the capacity limit — the context window — that keeps the total cost from growing without bound, checked over step counts far larger than the twelve tokens shipped here.
• An evicted position’s key and value vectors are discarded from the cache; the token itself is never removed from the sequence. Eviction follows a fixed rule — the oldest cached position goes first — not a decision about what is worth keeping.

Where the numbers come from

Every query, key and value vector on this page was written by a person, four numbers each, drawn from {0, 1, 2} so every dot product is a small integer. They are held attools/kv-cache/src/data/sequence.v1.json and shown in full in the tool’s Sequence tab. The word “you” appears twice, at positions 3 and 8, and is deliberately given a different key, value and query each time: the cache is indexed by position in the sequence, not by which word is there. The two positions score differently even against their own, identical word — 3 at position 3,6 at position 8 — computed and checked intools/kv-cache/test/kv-cache.test.ts.

What a bounded cache changes, and what it does not

Caching avoids exactly t − 1 key and value computations at generation stept, whatever the cache’s capacity is — one new computation is always enough. But a cache with no capacity limit does not, by itself, change how the total cost of a long run grows: the new query still has to be scored against every position seen so far, and that scoring cost grows with the step whether or not its keys and values were cached. Checked over step counts from ten to a hundred thousand, far past the twelve tokens shipped here: without a cache, total cost divided by the square of the step count converges to 1, confirming it grows quadratically; with a cache bounded to a fixed capacity w, total cost divided by the step count converges to exactlyw + 1, confirming it grows linearly instead. It is the capacity limit — the context window — that keeps the total from growing without bound, not caching by itself. Measured in tools/kv-cache/test/kv-cache.test.ts, not asserted.

What “evicted” means, mechanically

A cache holds at most w entries. Once generation would push it past that, the oldest cached entry is evicted — a fixed rule, not a judgement about what is worth keeping. The evicted position’s key and value vectors are discarded from the cache; the token itself is never removed from the sequence shown above the picture.

What this does not show

One cache, for one short, authored sequence. It does not show the memory layout, batching, quantisation or multi-request paging strategies a real inference server uses to manage many conversations’ caches at once, and it makes no claim about any specific real system's actual context-window length beyond the one round, representative figure named in the disclosure above.

Cost

With a fixed-capacity cache

O(n), with a fixed-capacity cache

With no cache at all

O(n^2), with no cache at all

Extra space (the cache)

O(w)

Steps recorded

25, always

n is the number of tokens generated; w is the cache capacity.

Unlike every Track A tool here, this one has no ceiling and no input to refuse. The sequence length is fixed by the data file, so the step count — twenty-five frames, always — is a constant: the cache capacity changes which positions are marked cached or evicted at a given step, never how many steps there are. What is validated instead is the data file itself, at load, because that is the part a person could edit.

Source

Vaswani et al., “Attention Is All You Need” (2017) defines the query/key/value mechanism this tool caches the output of. Context-window lengths in the thousands of tokens are widely documented across publicly released model families; the specific figure named in this tool’s disclosure is a round, representative one, not a measurement of any named system.

Worth comparing

• Scaled dot-product attention— the computation this page caches the output of: a query scored against a set of keys, producing a weighted sum of values.
• Softmax, temperature, top-k and top-p— what happens to the scores this page accounts the cost of computing, one step after this page's own concern ends.
• Beam search— a different way to choose a sequence of tokens, tracking several candidate continuations instead of generating one token at a time the way this page does.

All algorithms