The KV cache and model memory

What exactly is the cost of generating text? Let's try to understand. In a simple way. When an answer appears, it feels like the model is fetching it from somewhere.

It is not. Every single word is computed, fresh, while you wait. To produce one word, the model runs everything it has. Every layer, first to last.

That full trip through the network is called a forward pass. And the network is huge. A forward pass means tens of billions of multiplications and additions. That is the price of a single word.

Here is the uncomfortable part. That pass buys you exactly one token. For the next token, the model runs the whole network again. Nothing skipped.

So a two hundred word reply is not one run of the model. It is closer to two hundred and fifty runs, stacked back to back. And you cannot do them all at once. Each run needs the word before it to exist.

So the runs line up in a strict queue. There is a second cost hiding underneath. Every pass has to drag all of those weights out of memory and into the chip. For one token, you move gigabytes.

A database answers by finding something that already exists. Generation has nothing to find. Every word has to be built, so the bill grows with the length of the answer. So, generating text is expensive because the cost is per word, not per question.

One full pass, billions of operations, repeated for every token. Quick check now. One question is coming up. Let's see if it clicked.

How does rereading your whole prompt work? Let's try to understand. In a simple way. Between one word and the next, the model keeps nothing.

No notes, no scratchpad. It starts cold every time. So what goes in? Everything.

Your prompt, plus every word it has written so far, handed over as one long list of tokens. Say your prompt is fifty tokens. The model reads all fifty of them, and writes token number fifty one. Now the second word.

It does not carry on from where it stopped. It goes back to the start and reads all fifty one, then writes fifty two. And it repeats. Fifty two in, then fifty three, then fifty four.

The list it reads is one token longer every single step. Why reread? Attention. To place the newest token, the model has to compare it against every earlier token, so all of them must be in front of it.

And here is the sting. Your prompt gets pushed through the whole network again on every step. The same words, the same layers, the same result. It is also why a chat window has no real memory.

Each turn, the whole transcript is pasted in front of your new message. Remembering is just rereading. So a two hundred word answer does not read your prompt once. It reads it, from the top, a few hundred times over.

So, rereading is the model's only kind of memory. No notes between steps, so every new word means starting again at the first token. Quick check now. One question is coming up.

Let's see if it clicked.

What exactly is the quadratic scaling problem of attention? Let's try to understand. In a simple way. Attention works by comparison.

To handle one token, the model compares it against every other token, and scores how much each one matters. Line all those scores up and you get a grid. One row per token, one column per token. Every cell must be filled in.

So the work is not the number of tokens. It is the number of tokens times itself. Squared. That is what quadratic means.

Which gives a strange result. Double the length of your prompt, and this work does not double. It goes up four times. Put numbers on it.

One thousand tokens is a million cells. Ten thousand tokens is one hundred million cells. A hundred times more. And it is not only arithmetic.

Those scores have to sit in memory while they are used. So memory grows with the square too. Compare that with the rest of the model. Every other layer grows in a straight line with length.

Attention bends upward, and past some length it dominates. This is why longer context is such a big deal. A window ten times bigger is not ten times harder. It is closer to a hundred times.

So a lot of engineering exists to dodge that square. Look only at nearby tokens. Or never hold the whole grid at once. So, attention costs the square of the length, because every token is compared with every token.

Twice the tokens, four times the work. Quick check now. One question is coming up. Let's see if it clicked.

What exactly is a Key and a Value in attention? Let's try to understand. In a simple way. Attention compares tokens.

But not the words themselves. Every token is first turned into three vectors, by three separate learned weight matrices. A Query, a Key, and a Value. The Query is the question the current token asks.

Something like, which earlier words should I be looking at right now? The Key is what every token offers back. A label on a shelf. Not the content, just the advertisement that lets a Query spot a match.

The Value is the content itself. The information a token hands over once it has been picked. The Key gets you noticed. The Value is what you actually give.

So attention is two moves. Compare the Query against every Key to get a score. Then add up all the Values, weighted by those scores. The split is deliberate.

Keys decide how much each token counts. Values decide what actually flows forward. One controls attention, the other controls content. Here is the part that matters.

A token's Key and Value depend only on that token. Who is asking changes nothing. Token five has one Key and one Value, forever. And yet, on every generation step, the model rebuilds those same Keys and Values for every earlier token.

The same numbers, computed again, word after word. So, Keys are how a token gets found, and Values are what it gives once found. Queries come and go. Keys and Values stay.

Quick check now. One question is coming up. Let's see if it clicked.

What exactly is the KV cache? Let's try to understand. In a simple way. Remember the problem.

On every step, the model rebuilds the Key and Value for every earlier token. The same vectors, computed again and again. But those numbers never change. A token's Key and Value depend only on that token.

So why compute them twice? Just keep them. That store is the KV cache. For each token so far, it holds two saved vectors.

Its Key, and its Value. Sitting in memory, ready. Now a new word arrives. The model builds the Key and Value for that one new token.

Only that one. Nothing else. Every token before it? Their Keys and Values are already saved.

So the model reads them straight from the cache. No recomputing. Then it does one small thing. It drops the new token's Key and Value into the store.

The cache is ready for the next word. Why only Keys and Values, and not the Query? Because the Query belongs to the current token alone. It is used once, then thrown away.

Keys and Values get reused. So the heavy rereading turns into a quick lookup. Each step now computes one token's worth of work, instead of the whole sequence again. So, the KV cache remembers the Keys and Values it already built.

Compute the new one, look up the rest. That is the whole trick. Quick check now. One question is coming up.

Let's see if it clicked.

How does the KV cache grow with tokens? Let's try to understand. In a simple way. You know the trick.

For each token so far, the cache keeps two vectors. Its Key, and its Value. Now watch it as text is generated. Each new word the model writes adds one fresh entry.

One Key, one Value, for that token. They arrive one at a time. Write a word, append its pair. Write the next, append another.

The store gets one slot longer every step. Your prompt fills it first. Before a single word comes out, every token you typed drops its Key and Value in. Fifty words, fifty entries, at once.

So size follows length. One entry per token, no more. Twice the tokens, twice the cache. It grows in a straight line.

And during one reply, it only grows. Nothing is removed while the model is still writing. Every step is bigger than the last. A token's Key and Value stay parked until the whole request is done.

The cache holds the entire conversation so far. So picture two phases. A quick burst loads the prompt. Then a steady climb, one slot per word, for as long as it keeps talking.

Here is the catch. The longer the chat, the bigger the cache. A short answer barely moves it. A long conversation pushes it up and up.

So, the cache grows with tokens. One pair per token, a straight line up, never shrinking until you are done. Quick check now. One question is coming up.

Let's see if it clicked.

What exactly is the KV cache's enormous memory appetite? Let's try to understand. In a simple way. You already know the cache keeps a Key and a Value for every token.

That sounds tiny. But one single entry is far heavier than it looks. A Key is not one number. Neither is a Value.

Each is a long vector, hundreds or thousands of numbers lined up side by side. And this happens at every layer. A model is a tall stack of them, and each layer stores its own Key and Value for that same token. So multiply it out.

Two vectors, times every layer, times a couple of bytes each. For a typical model, one single token can cost around half a megabyte. Now stretch the chat. A few thousand tokens of context, each one carrying that half a megabyte, and the cache swells into gigabytes.

And a server rarely talks to just one person. Dozens of conversations run at once, and every one carries its own full cache. Multiply again. Stack all of that up, and something surprising happens.

For a long enough context, the cache can grow larger than the model's own weights. So the appetite is not the arithmetic. Those numbers are cheap to build. Keeping them, for every token, every layer, every user, is what piles up.

So, the appetite is a chain of multipliers. Two vectors, every layer, every token, every request. Each one small, together they reach gigabytes. Quick check now.

One question is coming up. Let's see if it clicked.

What exactly is the GPU memory wall? Let's try to understand. In a simple way. You already know the KV cache keeps growing.

Every token adds a pair, every user their own. It swells into gigabytes. But all of it has to live somewhere. Inside the GPU.

And a GPU has one fixed pool of memory. Eighty gigabytes, and no more. The model's weights move in first. They claim a big, fixed chunk and never leave.

Whatever room is left over is the budget for everything else. And that leftover space is mostly KV caches. Every open conversation packs its Keys and Values in. They all share the same shelf.

Now watch it fill. Longer chats, and more users, and the caches climb higher and higher up the box. Steadily eating the free room. Then they reach the top.

There is no room left for the next token's Key and Value. That hard ceiling is the memory wall. And a wall is not like being slow. Slow just takes longer, then finishes.

Memory is all or nothing. You fit, or you crash. So when the wall is hit, something must give. The server turns away a new user, cuts a conversation short, or drops one to make room.

This one wall decides everything. How many people a GPU can serve at once. And how long each chat is allowed to run. So, the memory wall is a hard ceiling.

Fixed memory, weights first, the caches fill the rest. Hit the top, and something has to give. Quick check now. One question is coming up.

Let's see if it clicked.

Why does memory get fragmented and wasted? Let's try to understand. In a simple way. You already know a GPU has one fixed pool of memory.

You would think, as long as the caches fit, all is well. But much gets wasted long before it fills. Here is why. Each conversation's cache must sit in one unbroken block.

Key after Value, side by side, so the model can sweep straight through. But the system cannot know how long a chat will run. So it plays safe. It reserves a block big enough for the longest answer allowed.

But most chats end early. A few sentences, then done. That block was booked for thousands of tokens, yet sits nearly empty. That trapped, unused room is internal fragmentation.

Now add time. Conversations start and finish at different moments. Each one that ends leaves a gap. The free memory shatters into scattered holes.

And here is the cruel part. Added together, the free space may be plenty. But no single hole is big enough for one unbroken block. That is external fragmentation.

Put both together. In older systems, only a small slice of the cache memory held real tokens. Sometimes twenty to forty percent. The rest sat idle.

And that wasted memory is not free. It is the space that decides how many users fit. Squander it, and you hit the wall far sooner. So, two kinds of waste.

Room reserved and never touched, and free space broken into holes too small to use. Both from demanding one contiguous block. Quick check now. One question is coming up.

Let's see if it clicked.

How does PagedAttention work? Let's try to understand. In a simple way. The KV cache wants to sit in one long, unbroken block of memory.

To be safe, the system grabs a big contiguous space up front. Much of it ends up empty. Here is the key insight. This is an old problem.

Your own computer solved it decades ago, inside its operating system. Programs on your laptop also want big blocks of memory. So the operating system does something clever. It chops memory into small, fixed size chunks called pages.

A program's pages do not have to sit together. They can be scattered all over physical memory, wherever there is a free slot. To keep track, the system holds a page table. It maps the program's neat, in order view onto those scattered pages.

The program believes its memory is one clean block. PagedAttention borrows this exact trick. It treats the KV cache the way an operating system treats memory. The cache is cut into small, fixed size blocks.

Each block holds the Keys and Values for just a handful of tokens. Those blocks can live anywhere in the GPU's memory. A single request's blocks might be scattered far apart. Each request keeps a block table.

It maps token positions to the physical blocks that hold them, so attention can follow the trail. No giant reserved space needed. So PagedAttention is just operating system paging, aimed at the KV cache. A tidy logical order, a scattered physical layout, and a small table linking the two.

Quick check now. One question is coming up. Let's see if it clicked.

How does paged memory work? Let's try to understand. In a simple way. First, recall the old way.

Each cache sat in one big unbroken block. Playing safe, the system reserved room for the longest answer. Most of it stayed empty. Paging throws that out.

It cuts memory into small blocks, all the same fixed size. Picture identical pages, each holding the Keys and Values for a few tokens. Now the big change. A chat gets a fresh block only when it fills the last one.

Nothing is reserved ahead. Pages arrive one at a time, as tokens do. So what happens to the wasted room? It shrinks to almost nothing.

The only slack left is the unfilled tail of the last page. A few tokens, never thousands. And the scattered holes? Gone too.

Every block is the exact same size, so any free block fits any request. A free slot is never too small. When a conversation ends, its blocks return to a shared pool. Each freed page is ready for whoever comes next.

No unusable gaps pile up. Add it up. Waste that used to swallow twenty to forty percent of the cache now drops to a few percent. The memory runs nearly full.

And that reclaimed space is not idle. It becomes room for more conversations at once. Same GPU, many more users before you hit the memory wall. So, two moves end the waste.

Uniform pages, handed out on demand, and any freed page serves anyone. The cache fills instead of leaking away. Quick check now. One question is coming up.

Let's see if it clicked.

How does sharing memory between requests work? Let's try to understand. In a simple way. Sometimes you ask a model for several answers to the very same question.

The system runs those answers as separate sequences, side by side. Every one begins from the exact same prompt. Without sharing, each sequence stores its own full copy of that prompt's Keys and Values. The same tokens, saved three or four times over.

Memory, wasted on duplicates. But remember how the cache is stored. It lives in small fixed blocks, and each sequence keeps a table of pointers to the blocks it uses. So we do the obvious thing.

For the shared prompt, we point every sequence's table at the very same physical blocks. One real copy, many readers. How does the system know a shared block is still needed? It keeps a reference count.

Each block remembers how many sequences point at it. There is a catch. These sequences will not stay identical. Each one generates its own next token, so eventually they go separate ways.

The rule that saves us is copy on write. The instant a sequence needs to write into a shared block, it makes its own private copy first, then writes. Everyone else keeps sharing the original. The payoff is big.

A long shared prompt is stored once, instead of once per answer. Beam search suddenly costs a fraction of the memory. So, shared blocks, a reference count, and copy on write. Many answers read from one copy, and split it apart only when they truly differ.

Quick check now. One question is coming up. Let's see if it clicked.

How does prefix caching work? Let's try to understand. In a simple way. Look at real traffic to a model.

Request after request begins the very same way. A long system prompt, a few examples, sometimes the same document again. Normally, every new request runs prefill over that whole opening from scratch, rebuilding the same Keys and Values every single time. Prefix caching stops throwing that work away.

When a request finishes, it keeps the blocks holding the shared opening's Keys and Values, instead of freeing them. Now a new request arrives. Before computing anything, the system checks. Does this opening match blocks already sitting in the cache?

On a match, it is a cache hit. The new request just points at those existing blocks. Prefill for the shared part is skipped. Computing only restarts where the two prompts first differ.

The shared head is reused for free. Only the new tail actually costs you. How does it match so fast? Each block is keyed by a hash of its exact tokens.

Same tokens, same key. The catch. The prefix must line up from the very first token. Change even one token near the front, and the keys no longer match.

The payoff is speed. Time to first token drops sharply for any long, repeated opening. A big system prompt becomes almost free after the first call. So, keep the shared opening's blocks, match a new request by hashing its tokens, and on a hit, skip the prefill.

Reuse the head, compute the tail. Quick check now. One question is coming up. Let's see if it clicked.

How does trading memory for throughput work? Let's try to understand. In a simple way. First, two different clocks.

Latency is how fast one user gets their reply. Throughput is how many tokens the whole server makes each second. This lesson is about throughput. Here is the catch during decoding.

To make just one next token, the GPU must read the model's entire pile of weights out of memory. Reading all those weights takes time. Meanwhile the GPU's fast math cores mostly sit and wait. For a single sequence, they are barely used.

So we batch. Instead of one sequence, run many together in the very same step. The weights get read once, and serve the whole group. Now that single read produces a token for every sequence at once.

Same trip to memory, far more tokens out. Throughput climbs steeply. But each sequence in the batch drags along its own KV cache. A bigger batch means more caches sitting in memory side by side.

And that cache memory has a ceiling, the memory wall from before. It caps how many sequences fit in one batch, which caps your throughput. So here is the trade. Every byte you save on the cache, through paging, sharing, prefix reuse, opens one more slot in the batch.

Saved memory turns straight into throughput. So, throughput is tokens per second for everyone. Batching keeps the GPU busy, memory caps the batch, and saving memory serves more people. Quick check now.

One question is coming up. Let's see if it clicked.

How does caching unlock longer context windows? Let's try to understand. In a simple way. A context window is how many tokens a model can hold in mind.

A bigger window means reading a whole report, or a whole codebase. But that window is not really about the math. It is about memory. Every token in the window needs its Key and Value kept live in the cache.

So the first unlock is the cache itself. Instead of rebuilding every past token each step, the model keeps their Keys and Values ready. A long history gets cheap to revisit. Here is the catch.

The cache grows with every token. A longer window means a heavier cache, and it must fit one fixed pool of memory. So the real limit is simple. Window length is the cache memory you can spare, divided by what each token costs.

Free up memory, and the window stretches. This is why the memory tricks matter. Paging packs the cache with almost no waste. Every byte it reclaims becomes room for more tokens of context.

Sharing helps too. When many chats open with the same long instructions, that shared part is stored once, not per user. The saved memory funds a longer window. None of this makes the window infinite.

Memory still sets a hard ceiling. The tricks push that ceiling out, they do not erase it. So a context window is really a memory budget. The cache stops the recompute, and packing that memory well is what buys a longer window.

Quick check now. One question is coming up. Let's see if it clicked.