KV Cache
Avoiding redundant computation during generation
27.1 What You Will Learn
Chapter 26 finished by pointing at a waste and then walking past it, which this chapter exists to correct. Generating a hundred token continuation means running the model a hundred separate times, and the ninety ninth of those runs recomputes keys and values for ninety eight positions that have not changed and could not have changed, because the causal mask guarantees that nothing later in the sequence can reach anything earlier. Section 26.4 measured that guarantee directly rather than asserting it, replacing the final token of a sequence and finding a change of exactly zero at every position before it. The same property that makes training parallel over positions makes almost all of inference redundant, and the two facts are the same fact seen from opposite ends.
The KV cache is the fix and it is the simplest optimisation in the book. Keep the keys and values you already computed, append one entry per new token, and score the new query against the whole stored set. Nothing about the mathematics changes and nothing is approximated, which Section 27.6 confirms by running both paths and comparing the outputs digit by digit. What changes is that the projection work per step stops growing with how much text has already been produced.
The cache then creates a problem of its own, because keeping every key and value for every layer and every head is a large amount of memory, and Section 27.4 puts real numbers on how large. That memory pressure is what drives the last part of the chapter, where DeepSeek-V3′s Multi-Head Latent Attention compresses what gets stored rather than storing less often. Understanding why that compression needs a separate uncompressed slot for positional information is the sharpest part of the design and the part most summaries skip.
27.2 The Problem
At generation step t the sequence holds t tokens and the model needs a query, a key and a value for the position it is about to predict from. It also needs keys and values for every earlier position, since the new query has to score against all of them. What it does not need is a fresh query for any position other than the last, because the outputs at earlier positions were already used and discarded on earlier steps.
Written out without a cache, the work is a sum that anyone can do. Step 1 pushes one token through every layer, step 2 pushes two, step 3 pushes three, and step n pushes n, so the total across a full generation is 1 + 2 + 3 and onward up to n, which comes to n(n+1)/2 and is therefore quadratic in the length of the output. Every one of those recomputations after the first produces numbers bit for bit identical to the numbers produced on the step before, for positions the model has already finished with, and it produces them again from scratch because nothing told it not to.
With a cache the projection work collapses to almost nothing. Each step projects exactly one new key and one new value, appends the pair to what is already stored, and reads the rest without touching a weight matrix, so the projection cost over the whole generation is n rather than n squared. That is the entire idea, and the program below tabulates the difference it makes across four sequence lengths so the scale of the saving is visible rather than asserted.
Be careful about what the cache does not fix, because the chapter is easy to misread on this point. The attention scoring at step t still compares one query against t cached keys, so scoring costs t at every step and n(n+1)/2 across the generation, which is quadratic no matter what is cached. The cache removes the redundant projections and leaves the inherent comparisons alone. That distinction matters when people describe attention as quadratic, since the quadratic term that survives is the one nobody has found a way to delete.
/* 139_Problem.c */
#include <stdio.h>
int main(void)
{
printf("K/V projection cost, cache against "
"no cache\n\n");
printf(" Seq len Without cache With cache "
" Savings\n");
printf(" ------- ---------------- ----------"
"----- -------\n");
int lengths[] = { 10, 100, 1000, 4096 };
int n = 4, i;
for (i = 0; i < n; i++) {
int L = lengths[i];
/* Without cache: recompute all K/V at every
step */
long long without = 0;
int t;
for (t = 1; t <= L; t++)
without += t; /* t projections at step t */
/* With cache: only compute 1 new K/V per
step */
long long with_cache = L;
/* L projections total */
/* Plus L lookups over the cache */
printf(" %5d %12lld %12lld "
"%7.1fx\n",
L, without, with_cache,
(float)without / with_cache);
}
printf("\n K/V projections fall from O(n^2) "
"to O(n).\n");
printf(" At length 4096 that is 2048.5 times "
"fewer.\n");
printf(" Scoring is still O(n) per token, but\n");
printf(" the K/V are just lookups.\n");
return 0;
}
The savings column reads 5.5 at length 10, then 50.5 at 100, 500.5 at 1000 and 2048.5 at 4096, and those are not arbitrary figures but n(n+1)/2 divided by n, which reduces to (n+1)/2 exactly. The saving is therefore proportional to the length rather than a fixed factor, which means it is nearly worthless for a one line answer and overwhelming for a long one. A model asked for four thousand tokens does two thousand times less projection work with a cache than without, and a model asked for ten does five and a half times less. That scaling is why the cache went from an optimisation nobody bothered with to a thing no inference engine ships without, since context lengths grew by three orders of magnitude in a few years.
Read the absolute numbers rather than the ratio for a moment. At length 4096 the uncached path performs 8,390,656 token-through-layer passes and the cached path performs 4096. Those figures are counts of one unit of work rather than seconds, but the shape is what matters, and the shape says that without a cache the cost of the next token rises linearly with everything already produced, so a long generation slows down as it goes. With a cache the cost of the next token is close to constant.
The closing lines of the program restate the distinction the previous section drew, and it repays being precise about it. Projections fall from quadratic to linear over the course of a generation, while scoring stays linear per token and therefore quadratic over the same generation. Both statements are true at the same time about the same model, and collapsing them into a single claim that the cache makes attention linear is the mistake people make when they repeat this from memory.
27.3 Building the Cache
The implementation is a growing array and an index into it, and there is genuinely nothing more to it than that. When a token arrives, project its key and its value in the ordinary way, write the pair at the end of the cache, increment the stored length, and then score the new query against every entry the cache now holds. No causal mask appears anywhere in a cached decoder, which surprises people who have just spent a chapter on masking. The reason is that the cache contains only positions the model has already processed, so future positions are not being blocked from the scoring, they were never placed in the structure being scored against.
Figure 27-2 shows three of the six steps the program runs. Only the highlighted column at the right of each row is projected, and every column to its left is read straight back out of the array. The query is the one thing that never accumulates, since a step only ever asks about the position it is predicting from.
Notice there is no branch anywhere in this. A cache lookup that might miss would need one, but at step t the cache always holds exactly the t-1 earlier pairs and never anything else, so the code is an append and a loop bound rather than a test.
/* 140_Kv_Cache.c */
#include <stdio.h>
#include <math.h>
#include <float.h>
#include <stdlib.h>
static float randf(void)
{
return (float)rand() / RAND_MAX;
}
static float dot(const float *a, const float *b, int n)
{
float s = 0;
int i;
for (i = 0; i < n; i++) s += a[i] * b[i];
return s;
}
static void softmax(float *x, int n)
{
float mx = -FLT_MAX, s = 0;
int i;
for (i = 0; i < n; i++) if (x[i] > mx) mx = x[i];
for (i = 0; i < n; i++) {
x[i] = expf(x[i] - mx);
s += x[i];
}
for (i = 0; i < n; i++) x[i] /= s;
}
#define DM 6
#define DK 4
#define MAX_SEQ 20
typedef struct {
float K[MAX_SEQ][DK]; /* cached keys */
float V[MAX_SEQ][DK]; /* cached values */
/* number of cached entries */
int len;
}
KVCache;
typedef struct {
float WQ[DK][DM];
float WK[DK][DM];
float WV[DK][DM];
float WO[DM][DK];
}
AttnWeights;
/* Process ONE new token using the cache */
static void attention_with_cache(
const AttnWeights *w,
/* the new token's representation */
const float x_new[DM],
KVCache *cache,
float out[DM])
{
int i, j, k;
float scale = 1.0f / sqrtf((float)DK);
/* Project new token to Q, K, V */
float q[DK], k_new[DK], v_new[DK];
for (i = 0; i < DK; i++) {
q[i] = 0;
k_new[i] = 0;
v_new[i] = 0;
for (j = 0; j < DM; j++) {
q[i] += w->WQ[i][j] * x_new[j];
k_new[i] += w->WK[i][j] * x_new[j];
v_new[i] += w->WV[i][j] * x_new[j];
}
}
/* Append new K, V to cache */
int pos = cache->len;
for (i = 0; i < DK; i++) {
cache->K[pos][i] = k_new[i];
cache->V[pos][i] = v_new[i];
}
cache->len++;
/* Compute attention: new Q against ALL cached K */
float scores[MAX_SEQ];
for (j = 0; j < cache->len; j++)
scores[j] = dot(q, cache->K[j], DK) * scale;
/* The mask is automatic here, since the
cache holds only the past and the present */
softmax(scores, cache->len);
/* Weighted sum of cached V */
float head[DK] = {0};
for (j = 0; j < cache->len; j++)
for (k = 0; k < DK; k++)
head[k] += scores[j] * cache->V[j][k];
/* Output projection */
for (i = 0; i < DM; i++) {
out[i] = 0;
for (k = 0; k < DK; k++)
out[i] += w->WO[i][k] * head[k];
}
}
int main(void)
{
AttnWeights w;
KVCache cache = { .len = 0 };
int i, j;
srand(42);
for (i = 0; i < DK; i++)
for (j = 0; j < DM; j++) {
w.WQ[i][j] = (randf()*2-1)*0.2f;
w.WK[i][j] = (randf()*2-1)*0.2f;
w.WV[i][j] = (randf()*2-1)*0.2f;
}
for (i = 0; i < DM; i++)
for (j = 0; j < DK; j++)
w.WO[i][j] = (randf()*2-1)*0.2f;
/* Simulate processing 6 tokens one at a time */
float tokens[6][DM] = {
{ 0.5f, -0.2f, 0.8f, 0.1f, -0.3f, 0.6f },
{ 0.3f, 0.7f, 0.1f, -0.2f, 0.5f, 0.4f },
{ -0.1f, 0.4f, 0.6f, 0.3f, -0.4f, 0.2f },
{ 0.2f, -0.3f, 0.5f, 0.6f, 0.1f, -0.5f },
{ 0.8f, 0.2f, -0.1f, 0.4f, 0.3f, 0.6f },
{ -0.4f, 0.1f, 0.3f, -0.2f, 0.7f, 0.5f },
};
const char *words[] = { "The", "cat", "sat",
"on", "the", "mat" };
printf("Attention with a KV cache, one token "
"at a time\n\n");
printf(" Token Cache size K/V projections "
"computed\n");
printf(" ------ ---------- ----------------"
"-------\n");
for (int t = 0; t < 6; t++) {
float out[DM];
int prev_len = cache.len;
attention_with_cache(&w, tokens[t],
&cache, out);
printf(" %-6s %3d -> %3d 1 (new token "
"only)\n",
words[t], prev_len, cache.len);
}
printf("\n Without cache: 1+2+3+4+5+6 = 21 "
"projections\n");
printf(" With cache: 6 projections, one "
"per token\n");
printf(" Cache memory: %d entries x %d dims "
"x 2 = %d floats\n",
cache.len, DK, cache.len * DK * 2);
return 0;
}
The table walks six tokens through and the middle column tells the story. The cache grows 0 to 1, then 1 to 2, then 2 to 3, up to 5 to 6, one entry per token, and the right hand column reports one projection computed at every step regardless of how much is already stored. Six tokens, six projections. The uncached path would have run 1+2+3+4+5+6, which is 21.
The memory line at the bottom is the first hint of the problem the rest of the chapter deals with. Six entries at four dimensions, doubled because both a key and a value are stored, comes to 48 floats for a six token sequence at a single head in a single layer. Multiply by heads, then by layers, then by a context length in the thousands, and the number stops being small.
One structural point about where the cache lives. There is a separate cache per layer and per head, because the keys and values at layer 5 are computed from layer 4′s output and have nothing to do with the keys at layer 3. A twelve layer model with twelve heads maintains 144 independent caches, all growing in step, and the bookkeeping for that is the bulk of what an inference engine does. The cache also belongs to one generation rather than to the model, so serving many users at once means holding many caches simultaneously, which is why batch size and context length trade directly against each other on fixed hardware.
27.4 What the Cache Costs
Per token, per layer, the cache holds one key and one value for every attention head, so the arithmetic is 2 for the pair, times the head count, times the head dimension, times the size of a float. Multiply that by the layer count to get what a single token costs across the whole model, then by the context length to get what a full sequence costs. Neither multiplication is difficult and both are easy to avoid doing, which is why the numbers surprise people. The program below runs them for four real models at their published dimensions.
/* 141_Memory.c */
#include <stdio.h>
int main(void)
{
printf("KV cache memory for real models:\n\n");
struct {
const char *name;
int n_layers, n_heads, d_head, max_seq;
}
models[] = {
{ "GPT-2 Small", 12, 12, 64, 1024 },
{ "LLaMA-7B", 32, 32, 128, 4096 },
{ "LLaMA-70B", 80, 64, 128, 4096 },
{ "DeepSeek-V3", 61, 128, 128, 128000 },
};
int n = 4, i;
printf(" %-14s layers heads d_head max_seq "
" cache/token full cache\n", "Model");
printf(" %-14s ------ ----- ------ ------- "
" ----------- ----------\n", "");
for (i = 0; i < n; i++) {
int L = models[i].n_layers;
int H = models[i].n_heads;
int D = models[i].d_head;
int S = models[i].max_seq;
/* Per token, 2 for K and V, times
layers times heads times d_head
times sizeof(float) */
long long per_token = 2LL * L * H * D * 4;
long long full = per_token * S;
printf(" %-14s %4d %3d %4d %6d "
" %7lld B ",
models[i].name, L, H, D, S, per_token);
if (full < 1024LL*1024*1024)
printf("%.0f MB\n", full / (1024.0 * 1024));
else
printf("%.1f GB\n",
full / (1024.0 * 1024 * 1024));
}
printf("\n DeepSeek-V3 at 128K tokens would "
"need this much\n");
printf(" without MLA. That is why MLA exists.\n");
return 0;
}
The progression is steep. GPT-2 Small stores 73,728 bytes per token and 72 MB for a full 1024 token context, which is nothing. LLaMA-7B stores about a megabyte per token and 4.0 GB at 4096, which is comparable to the weights themselves in a quantised deployment. The DeepSeek-V3 row, at 128,000 tokens of context, reaches 953.1 GB, which is more memory than any single machine has.
One correction to the LLaMA-70B row before going further, because the figure is right for the formula and wrong for the model. It assumes 64 key and value heads, one per query head, and LLaMA 2 70B does not do that. It uses grouped query attention, where several query heads share a single key and value head, with 64 query heads mapped onto 8 shared ones. That divides the cache by 8, so the real figure is 655,360 bytes per token and 2.50 GB at 4096 rather than 20.0 GB. Exercise 2 asks you to work through the general case, and the answer is that GQA divides cache memory by the sharing ratio while leaving the query side untouched.
That correction does not soften the DeepSeek-V3 row, it sharpens why that row matters. Grouped query attention is a good trick and it buys a constant factor of 8. A context of 128,000 tokens is thirty times longer than 4096, and the cache scales linearly with context, so a constant factor does not rescue it. Something that changes what gets stored rather than how often is required, which is the next section.
The last thing to take from this table is what it implies about hardware. A cache of gigabytes has to be read in full for every single token generated, since scoring the new query touches every stored key. Generation is therefore limited by how fast memory can be read rather than by how fast the arithmetic runs, which inverts the usual intuition from training. That is why inference serving is discussed in terms of memory bandwidth, and why halving the cache roughly halves the time per token even though it changes no arithmetic at all.
27.5 Multi-Head Latent Attention
DeepSeek-V3 attacks the memory rather than the frequency. Instead of caching the full keys and values for every head, it projects the layer input down into one small shared latent vector, caches that, and reconstructs the keys and values from it whenever attention needs them.
The first line compresses the layer input into a latent, the middle two reconstruct full keys and values from that latent when attention needs them, and the fourth produces a separate small key carrying the position information that the compression cannot be allowed to touch. Only c_KV and k_R are ever written to the cache, so the thing being stored is much smaller than the thing being used, and the reconstruction happens fresh on every step from whatever was stored.
/* 142_Mla.c */
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
static float randf(void)
{
return (float)rand() / RAND_MAX;
}
#define DM 64 /* model dimension */
#define N_HEADS 8
#define D_HEAD 8 /* per-head dimension */
/* Compression dimension, far below the 64 that
N_HEADS * D_HEAD comes to */
#define D_C 16
#define D_ROPE 8 /* decoupled RoPE key dimension */
/* Down-project h to compressed latent c_KV */
static void compress_kv(const float h[DM],
const float W_DKV[D_C][DM],
float c_kv[D_C])
{
int i, j;
for (i = 0; i < D_C; i++) {
c_kv[i] = 0;
for (j = 0; j < DM; j++)
c_kv[i] += W_DKV[i][j] * h[j];
}
}
/* Up-project c_KV to full K or V */
static void decompress(const float c_kv[D_C],
const float
W_U[N_HEADS*D_HEAD][D_C],
float full[N_HEADS * D_HEAD])
{
int i, j;
for (i = 0; i < N_HEADS * D_HEAD; i++) {
full[i] = 0;
for (j = 0; j < D_C; j++)
full[i] += W_U[i][j] * c_kv[j];
}
}
int main(void)
{
float W_DKV[D_C][DM];
float W_UK[N_HEADS * D_HEAD][D_C];
float W_UV[N_HEADS * D_HEAD][D_C];
int i, j;
srand(42);
for (i = 0; i < D_C; i++)
for (j = 0; j < DM; j++)
W_DKV[i][j] = (randf()*2-1)*0.1f;
for (i = 0; i < N_HEADS * D_HEAD; i++)
for (j = 0; j < D_C; j++) {
W_UK[i][j] = (randf()*2-1)*0.1f;
W_UV[i][j] = (randf()*2-1)*0.1f;
}
/* Input hidden state */
float h[DM];
for (i = 0; i < DM; i++) h[i] = (randf()*2-1)*0.5f;
/* Standard MHA: cache full K and V */
int standard_cache = N_HEADS * D_HEAD * 2;
/* K + V */
/* Compress, cache the latent, and
decompress only when it is needed */
float c_kv[D_C];
compress_kv(h, W_DKV, c_kv);
int mla_cache = D_C + D_ROPE; /* c_KV + k_R */
/* Verify: decompress produces valid K and V */
float K_full[N_HEADS * D_HEAD];
float V_full[N_HEADS * D_HEAD];
decompress(c_kv, W_UK, K_full);
decompress(c_kv, W_UV, V_full);
printf("Multi-Head Latent Attention (MLA):\n\n");
printf(" Standard MHA per token: %d floats, "
"K and V\n", standard_cache);
printf(" MLA per token: %d floats, "
"c_KV and k_R\n", mla_cache);
printf(" Compression ratio: %.1fx\n\n",
(float)standard_cache / mla_cache);
printf(" Dimensions:\n");
printf(" d_model = %d\n", DM);
printf(" n_heads * d_head = %d, one full "
"K or V\n", N_HEADS * D_HEAD);
printf(" d_c = %d (compressed latent)\n", D_C);
printf(" d_rope = %d, the decoupled key\n\n",
D_ROPE);
printf(" Pipeline:\n");
printf(" Encode: h [%d] -> c_KV [%d], and "
"cache that\n", DM, D_C);
printf(" Decode: c_KV [%d] -> K [%d]\n",
D_C, N_HEADS * D_HEAD);
printf(" c_KV [%d] -> V [%d]\n\n",
D_C, N_HEADS * D_HEAD);
/* Real DeepSeek-V3 numbers */
printf(" DeepSeek-V3 actual dimensions:\n");
printf(" n_heads=128 d_head=128 d_c=512 "
"d_rope=64\n");
int ds_standard = 128 * 128 * 2; /* full K + V */
int ds_mla = 512 + 64; /* c_KV + k_R */
printf(" Standard cache: %d floats/token\n",
ds_standard);
printf(" MLA cache: "
"%d floats/token\n", ds_mla);
printf(" Compression: %.1fx\n",
(float)ds_standard / ds_mla);
return 0;
}
The toy at the top of the output runs the whole path at small dimensions. Standard caching of a 64 dimensional key and a 64 dimensional value costs 128 floats per token, while the latent at 16 dimensions plus the decoupled key at 8 comes to 24, a compression of 5.3 times. The pipeline lines underneath show the shapes, with a 64 dimensional input squeezed to 16 on the way into the cache and expanded back to 64 on the way out.
The real dimensions are at the bottom and the numbers are larger in both directions. DeepSeek-V3 runs 128 heads of dimension 128, so a standard cache would hold 32,768 floats per token per layer, and MLA stores 512 for the latent plus 64 for the decoupled key, which is 576. That is a compression of 56.9 times. Applied across 61 layers at 128,000 tokens in half precision it turns the 953.1 GB from the previous section into roughly 8.4 GB, which fits.
What it costs is arithmetic. Every attention step now runs two extra matrix multiplies to rebuild K and V from the latent, which is work the standard arrangement does not do. The previous section explained why that trade is favourable, since generation is bound by memory bandwidth rather than by arithmetic, so spending flops to avoid reading bytes is spending the cheap resource to save the scarce one. There is also a trick available where W_UK can be folded into the query projection algebraically so the reconstruction never happens explicitly, which is beyond this chapter but is why MLA costs less in practice than the equations suggest.
The decoupled RoPE key is the part worth understanding properly, since it looks like an inelegant patch and is not. RoPE from Chapter 22 rotates a key by an angle determined by its position, and the whole point of the compressed latent is that it is cached once and reused. If the rotation were applied before compression then the cached latent would carry one particular position baked into it, and if it were applied after decompression then the reconstruction would have to run separately per position and the folding trick above would be impossible. So MLA keeps a small unrotated latent for content and a separate small rotated key for position, and concatenates them at scoring time. At 64 dimensions against the latent’s 512 that separate key is cheap, and exercise 4 asks you to reason it through.
27.6 Verifying the Cache
An optimisation that changes the answer is not an optimisation, it is a different model, so the last program runs both paths over the same input and compares them position by position. One path recomputes every key and every value from scratch at every position, exactly as Chapter 26 did before any of this. The other maintains a cache and reads from it. If the cache is implemented correctly then the two must agree exactly rather than approximately, because they perform the same multiplications on the same numbers in the same order, and floating point arithmetic is deterministic even where it is inexact.
/* 143_Verify.c */
#include <stdio.h>
#include <math.h>
#include <float.h>
#include <stdlib.h>
static float randf(void)
{
return(float)rand()/RAND_MAX;
}
static float dot(const float *a, const float *b,
int n)
{
float s = 0;
int i;
for (i = 0; i < n; i++) s += a[i] * b[i];
return s;
}
static void softmax(float *x, int n)
{
float mx = -FLT_MAX, s = 0;
int i;
for (i = 0; i < n; i++) if (x[i] > mx) mx = x[i];
for (i = 0; i < n; i++) {
x[i] = expf(x[i] - mx);
s += x[i];
}
for (i = 0; i < n; i++) x[i] /= s;
}
#define DM 4
#define DK 3
#define SL 4
int main(void)
{
float WQ[DK][DM], WK[DK][DM], WV[DK][DM];
int i, j, k;
srand(42);
for (i = 0;i<DK;i++) for(j = 0;j<DM;j++){
WQ[i][j] = (randf()*2-1)*0.3f;
WK[i][j] = (randf()*2-1)*0.3f;
WV[i][j] = (randf()*2-1)*0.3f;
}
float X[SL][DM] = {
{0.5f, -0.2f, 0.8f, 0.1f}, {0.3f, 0.7f,
0.1f, -0.2f},
{-0.1f, 0.4f, 0.6f, 0.3f}, {0.2f, -0.3f,
0.5f, 0.6f}};
float scale = 1.0f / sqrtf((float)DK);
/* Method 1: Full recomputation (no cache) */
float out_full[SL][DK];
for (i = 0; i < SL; i++) {
float q[DK];
for (k = 0; k < DK; k++) {
q[k] = 0;
for (j = 0; j < DM; j++)
q[k] += WQ[k][j] * X[i][j];
}
float scores[SL];
for (j = 0; j <= i; j++) {
float key[DK];
for (k = 0; k < DK; k++) {
key[k] = 0;
for (int d = 0; d < DM; d++)
key[k] += WK[k][d] * X[j][d];
}
scores[j] = dot(q, key, DK)*scale;
}
softmax(scores, i+1);
for (k = 0; k < DK; k++) {
out_full[i][k] = 0;
for (j = 0; j <= i; j++) {
float v = 0;
for (int d = 0; d < DM; d++)
v += WV[k][d] * X[j][d];
out_full[i][k] += scores[j]*v;
}
}
}
/* Method 2: With KV cache */
float cache_K[SL][DK], cache_V[SL][DK];
float out_cache[SL][DK];
int cache_len = 0;
for (i = 0; i < SL; i++) {
float q[DK];
for (k = 0; k < DK; k++) {
q[k] = 0;
for (j = 0; j < DM; j++)
q[k] += WQ[k][j] * X[i][j];
}
/* Project and cache new K, V */
for (k = 0; k < DK; k++) {
cache_K[cache_len][k] = 0;
cache_V[cache_len][k] = 0;
for (j = 0; j < DM; j++) {
cache_K[cache_len][k] +=
WK[k][j] * X[i][j];
cache_V[cache_len][k] +=
WV[k][j] * X[i][j];
}
}
cache_len++;
/* Attend to cache */
float scores[SL];
for (j = 0; j < cache_len; j++)
scores[j] = dot(q, cache_K[j], DK) * scale;
softmax(scores, cache_len);
for (k = 0; k < DK; k++) {
out_cache[i][k] = 0;
for (j = 0; j < cache_len; j++)
out_cache[i][k] +=
scores[j] * cache_V[j][k];
}
}
/* Compare */
printf("Cache against full recomputation\n\n");
printf(" pos full_recompute with_cache "
" match?\n");
for (i = 0; i < SL; i++) {
float diff = 0;
for (k = 0; k < DK; k++) {
float d = out_full[i][k] - out_cache[i][k];
diff += d * d;
}
diff = sqrtf(diff);
printf(" %d [%+.4f,%+.4f,%+.4f] "
"[%+.4f,%+.4f,%+.4f] %s\n",
i, out_full[i][0], out_full[i][1],
out_full[i][2],
out_cache[i][0], out_cache[i][1],
out_cache[i][2],
diff < 1e-6f ? "yes" : "NO");
}
printf("\n Both methods produce identical "
"results.\n");
printf(" The cache is an optimization rather "
"than an approximation.\n");
return 0;
}
All four positions match to four decimal places, and the agreement is not rounding hiding a small difference. Position 0 gives [+0.0429, −0.2115, +0.1646] under both paths, position 3 gives [+0.0398, −0.1019, +0.0901] under both, and the two rows between behave the same way. The cache is memoization, storing a value already computed rather than computing it a second time, and memoization returns exactly what recomputation would have returned because it is the same arithmetic reached by a shorter route.
That distinguishes the KV cache from the compression in the previous section, which is worth stating plainly because the two are often mentioned in the same breath. MLA is lossy. Squeezing 32,768 floats into 576 discards information and the reconstructed keys and values are approximations of what full projections would have produced, which is why exercise 3 asks you to compress and decompress and observe that you do not get the original back. The cache discards nothing. One is a genuine trade of quality against memory and the other is free.
Tests of this shape are worth writing for any optimisation that claims to be transparent. The failure mode for a hand written cache is an off-by-one in the cache length, or scoring against one entry too few, and neither produces a crash. The model generates slightly worse text and nobody notices for a week. Running both paths on a short sequence and demanding bit for bit agreement takes a few lines and settles it, which is the same argument Section 26.4 made for testing the causal mask and Section 23.8 made for checking a gradient against finite differences.
27.7 Key Takeaways
The KV cache stores keys and values already computed so that each generation step projects only the new token. Section 27.2 measured the projection saving at (n+1)/2, which is 2048.5 times at a length of 4096.
Scoring is not saved. The new query still compares against every cached key, so attention scoring remains linear per token and quadratic across a generation, and the cache removes the redundant projections rather than the inherent comparisons.
No mask is needed inside a cached decoder, because the cache holds only positions already processed. Future positions are not blocked, they were never stored.
There is one cache per layer per head, and one set of caches per concurrent generation rather than per model. A twelve layer twelve head model maintains 144 caches, and serving many users means holding many sets at once.
Cache memory per token is 2 * layers * heads * d_head * sizeof(float). Section 27.4 measured 72 MB for GPT-2 Small at 1024 tokens and 953.1 GB for DeepSeek-V3 dimensions at 128,000.
The LLaMA-70B row in that table assumes one key and value head per query head, and the real model uses grouped query attention with 64 query heads sharing 8, which divides the cache by 8 to 2.50 GB.
Generation is bound by memory bandwidth rather than arithmetic, because the whole cache is read for every token produced. Halving the cache roughly halves the time per token without changing any arithmetic.
MLA compresses keys and values into one shared latent before caching and reconstructs them on use. DeepSeek-V3 stores 576 floats per token per layer against 32,768, a compression of 56.9 times, which brings a 128,000 token cache from 953.1 GB down to roughly 8.4 GB in half precision.
The cost is two extra matrix multiplies per attention step, which is the right trade when the bottleneck is memory rather than compute.
Positional information is cached separately as a small rotated key, because a rotation baked into the latent would fix it to one position and a rotation applied after reconstruction would prevent the projections being folded together.
The cache is exact. Section 27.6 produced identical outputs from both paths at every position, which separates it from MLA compression, which is genuinely lossy.
27.8 Exercises
Implement a KV cache for a 2-layer, 2-head model. Each layer and each head needs its own cache. How much memory does this require at sequence length 1000?
What happens to cache memory with Grouped Query Attention (GQA), where multiple query heads share K/V heads? If 8 query heads share 1 K/V head, what is the memory savings?
Implement MLA compression and decompression. Verify that compressing then decompressing produces an approximation of the original K/V (not exact, because the compression is lossy).
The decoupled RoPE key in MLA is cached at d_rope = 64 dimensions, shared across all heads. Why can RoPE not be applied through the compressed latent?
Implement a circular buffer KV cache with a maximum size. When the cache is full, discard the oldest entries. This implements a sliding window attention.
Compute the total cache memory for DeepSeek-V3 at 128K context: 61 layers, d_c = 512, d_rope = 64, in FP16 (2 bytes per float). Compare to standard MHA with 128 heads of dimension 128.