KV Cache and Speculative Decoding: How LLM Inference Gets Fast
The same model that answers instantly on a short prompt can crawl once a conversation grows long, and the bill grows with it even though the question did not get harder. Developers who only call an LLM API tend to blame the model or the network. Usually the real cause lives inside the model server: attention over a growing context, and the memory it takes to avoid recomputing that attention from scratch on every token.
This guide stays inside the inference server, not the application layer — it is scoped away from response, semantic, and prompt caching, which are covered in LLM Caching: Response Cache vs Semantic Cache vs Prompt Cache. Here you will trace one growing request, review-pr-4821, through prefill and decode, see why the KV cache turns memory — not compute — into the real bottleneck at long context and high concurrency, and learn how speculative decoding buys lower latency by spending extra compute. It helps to already know how self-attention works; this guide builds directly on top of it.
Autoregressive Decoding and the KV Cache
A decoder-only LLM generates one token at a time, and each new token is predicted by attending over every token that came before it. At each layer, a token's query vector is compared against the key vectors of all earlier tokens to weight their value vectors. Nothing about that computation is optional — a model cannot skip attention and still be the same model.
What is optional is recomputing it. Because the architecture is causal — a token's hidden state at layer l depends only on tokens at or before it — the key and value vectors for an already-generated token never change as later tokens are added. Once layer l has produced token 5's key and value, token 50 arriving later does not retroactively edit them. That single fact is what makes caching legal: a server can compute each token's K/V vectors exactly once, store them, and reuse them for every later step instead of re-running the full prefix through the model again.
review-pr-4821 starts with an 8,000-token prompt: the pull-request diff plus repo context handed to a code-review assistant. The server's prefill phase processes that entire prompt in one parallel forward pass and writes a key/value pair per layer, per attention head, for every one of those 8,000 tokens into the KV cache. From there the server enters decode: each new token only computes its own K/V pair and attends against the cache — it never re-derives the diff's attention from position zero. Skip the cache, and generating token 8,050 would mean re-running attention over 8,050 tokens just to produce one more word.
Quick reference
- Prefill is compute-bound and parallel: the whole prompt is processed in one pass, which is why long prompts add a visible up-front delay before the first token.
- Decode is memory-bandwidth-bound and sequential: each step reads the growing cache and writes one new K/V pair per layer.
- The cache is legal because of causality — a token's key/value never changes once later tokens are appended, so recomputation would be pure waste, not extra safety.
- Cache correctness depends on determinism of the forward pass for a fixed prefix; changing the system prompt or truncating context invalidates the cached prefix from that point forward.
- This is server-internal state tied to one in-flight request or conversation session — it is not the same thing as an application-level response or semantic cache shared across users.
Remember this
The KV cache is legal only because causal attention makes past tokens' keys and values immutable once written — that immutability is what turns O(context²) recomputation into one cheap append per step.
The KV Cache Memory Bottleneck
The KV cache buys speed by spending memory, and that memory bill is not fixed — it grows with every dimension of the workload. For one sequence, cache size scales with 2 × layers × attention heads × head dimension × bytes per value × sequence length (the 2 covers storing both keys and values). Doubling the context length roughly doubles that one sequence's cache. Serving many sequences at once multiplies it again by batch size — the number of requests the server holds in flight concurrently.
That is the detail people miss when they assume a bigger model is always the bottleneck. Model weights are a fixed cost, loaded once. KV cache is a per-request, per-token cost that keeps climbing for as long as a conversation stays open and as many conversations as the server is juggling. At long enough context lengths and high enough concurrency, the KV cache — not the model's weights — becomes the largest consumer of GPU memory, and it is the thing that runs out first.
Back in review-pr-4821, the developer keeps asking follow-up questions and the conversation's context climbs from 8,000 tokens toward 64,000 as more files and prior answers stay in scope. That single conversation's cache keeps growing turn over turn. Multiply that by every other engineer opening a review on the same shared inference server, each with their own growing context, and the server is now managing dozens of caches that all expand independently and never shrink on their own. This is a throughput and latency problem measured in bytes, not just requests per second: the server can be compute-idle and still refuse new work because it has no memory left to hold another cache.
Quick reference
- Cache size per sequence ≈ 2 × layers × heads × head_dim × bytes_per_value × context_length; total server usage multiplies that by concurrent batch size.
- Grouped-query and multi-query attention reduce the head count used for K/V storage, which shrinks the cache but is an architecture decision made when the model is trained, not something a caller controls at request time.
- A long system prompt or long few-shot context pays the same linear memory tax on every concurrent request that includes it.
- Compute for decode grows much more slowly than memory does, which is why long-context serving is usually memory-bound rather than GPU-compute-bound.
- Track cache utilization (bytes in use vs. GPU memory budget) as its own metric — request count and GPU utilization percent can both look healthy while cache headroom is nearly gone.
Remember this
KV cache memory scales linearly with context length and with concurrent batch size at the same time, so the real serving bottleneck for long-context, high-concurrency workloads is memory capacity, not raw FLOPs.
Speculative Decoding: Trading Compute for Latency
A bigger KV cache budget solves how many long conversations a server can hold, but decode still moves one token at a time through the large model, and each step pays that model's full forward-pass cost. Speculative decoding attacks a different bottleneck: the number of sequential passes through the expensive model, not the memory those passes touch.
The trade is extra compute for lower latency, not free speed. Every drafted token still costs a target-model verification slot even when rejected, so a mismatched draft model burns GPU cycles without shortening the critical path — the win only shows up when the draft model's guesses are right often enough that accepted-token runs regularly beat one-token-at-a-time generation. That is why it pairs naturally with the KV cache picture above: both techniques are optimizing the same decode loop from different ends, one making each sequential step cheaper to hold in memory, the other making fewer sequential steps necessary in the first place.
| Lever | What it changes | Helps when | Does not help when |
|---|---|---|---|
| More KV cache budget / paging | How many long contexts fit in memory at once | Concurrency or context length is the limit, not per-token speed | Compute per token is already the bottleneck |
| Speculative decoding | How many sequential big-model passes one output costs | Generation is latency-sensitive and outputs are fairly predictable | Draft and target models diverge often, or the workload is throughput-bound batch generation |
Quick reference
- A small, cheap draft model generates k candidate tokens autoregressively, the same way normal decoding works, just faster and lower quality.
- The large target model then runs one forward pass over all k drafted positions at once — verification is parallel because attention over already-known tokens does not require waiting on each other, unlike generation.
- The target model accepts the longest prefix of drafted tokens that matches what it would have generated itself (or, in the sampling case, what a rejection-sampling test allows while preserving the target model's output distribution).
- Generation resumes from the first rejected token, so the target model never actually ships a token it did not itself approve — speculative decoding changes speed, not output quality.
- The win is structural: verifying k tokens costs about one target-model pass, the same as generating a single token normally, but can yield up to k accepted tokens instead of one.
Remember this
Speculative decoding does not reduce total compute — it spends extra draft-model and occasionally-wasted verification compute to cut the number of sequential large-model passes, which is what latency actually tracks.
When the Serving Stack Breaks Down
Trigger. It is release-freeze afternoon and dozens of engineers open review-pr-4821-style conversations within the same few minutes, each one growing from a short prompt toward tens of thousands of tokens of retained context on the shared inference server. Symptom. p99 latency climbs first, then some requests start failing outright or get silently truncated, and new sessions get stuck in an admission queue that never seems to drain.
Root mechanism. Every one of those growing conversations is holding an ever-larger KV cache in GPU memory at the same time. Once the sum of all active caches approaches the server's memory budget, something has to give: a naive server that preallocates each sequence's cache at its maximum possible length wastes huge amounts of memory to fragmentation long before it is actually full, and a server with no eviction policy either rejects new requests outright or, worse, silently drops context it should have kept.
Diagnostic. Check GPU memory utilization against active sequence count and average context length — cache pressure shows up there well before GPU compute utilization looks unusual. Inference servers built around block-based cache management (the PagedAttention idea, borrowed conceptually from OS virtual memory) log eviction, preemption, or swap events; those logs are the direct evidence, not generic 'high latency' alerts. Recovery. Cap max concurrent sequences or max context length through admission control, and prefer a server that manages the cache in fixed-size blocks with a block table — so memory freed by one finished sequence is immediately reusable by another instead of sitting fragmented — over one that reserves a worst-case contiguous slab per request. Prevention. Capacity-plan for the realistic distribution of concurrent context lengths, not the average one, and put a hard context-length ceiling per pricing tier so one runaway conversation cannot starve every other request on the box; the routing and quota layer for this belongs with the broader gateway controls covered in AI Gateway: Routing, Cost Controls, and Observability.
Speculative decoding has its own quieter failure: a draft model that is a poor match for the target model's distribution. Point the code-review assistant at a language or style the small draft model rarely saw in training and its guesses stop matching — the target model rejects almost every drafted token, generation falls back to one accepted token per verification pass, and the server has now paid for both a draft pass and a verification pass to get the same one token plain decoding would have produced directly. The fix is the same in spirit as cache capacity planning: monitor acceptance rate per request class, and fall back to plain decoding (or swap in a better-matched draft model) once acceptance drops low enough that speculation is adding latency instead of removing it.
Quick reference
- Track KV cache bytes in use versus budget as a first-class metric, not a derived one — it moves before latency or error rate do.
- Prefer block/paged cache allocation over per-request worst-case preallocation; it avoids fragmentation wasting capacity before real limits are hit.
- Set a hard max context length per tier so a single long conversation cannot exhaust shared server memory for everyone else.
- Log eviction, preemption, and admission-rejection events distinctly — a generic latency alert will not tell you it was a memory decision.
- Monitor speculative decoding's acceptance rate per draft/target pairing; a falling acceptance rate is the leading indicator that speculation is about to cost more than it saves.
Remember this
Both KV cache exhaustion and speculative-decoding draft mismatch are capacity failures, not model failures — they show up as eviction, rejection, or falling acceptance rate well before they show up as a wrong answer.
Key takeaway
The KV cache is what makes autoregressive decoding affordable: cache each token's key and value once, at the cost of memory that grows linearly with context length and concurrent batch size, and that memory — not raw compute — is usually the real ceiling on long-context serving. Speculative decoding attacks the other axis, spending draft-model and occasional wasted verification compute to cut the number of sequential passes through the expensive model, which is what latency actually measures.
Practice (20-30 min): write a small Python simulation with two functions, decode_step_cost_no_cache(context_len) returning a cost proportional to context_len (recomputing attention over the whole prefix every step) and decode_step_cost_with_cache(context_len) returning a constant. Run both for context_len from 8 to 64,000 and plot or print cumulative cost. Expected result: the no-cache total grows quadratically with total tokens generated while the cached total stays roughly linear. Intentional break: simulate 50 concurrent sequences, each tracking cache_bytes = context_len * bytes_per_token, sum them against a fixed memory_budget, and raise a MemoryBudgetExceeded once the running total crosses it — mirroring the KV cache OOM trace above. Recovery: add simple LRU eviction that frees the least-recently-active sequence's cache bytes when the budget is hit, and confirm new requests keep being admitted instead of the simulation crashing. Pass criterion: the no-cache/with-cache cost curves diverge as expected, the unmodified simulation hits MemoryBudgetExceeded under 50 concurrent growing sequences, and it stops doing so once eviction is added.
Related Articles
Explore this topic