KV cache and continuous batching: 1,000 people ask AI

An AI server answers many people at once with two tricks: a KV cache, so each new token does not redo the work of the earlier ones, and continuous batching, so many requests share every generation step. On our toy model the cache cut one answer from 567 ms to 39 ms, and in a simulated queue of 1,000 requests the median wait for the first token fell from 452 s (7.5 minutes) to 14 s.

Why does writing one token at a time repeat work? {#tokens}

Definition

Token: a small piece of text, often part of a word, that a language model reads and writes one at a time.

Definition

Time to first token (TTFT): the time from sending a request until the first output token is ready. It includes waiting in the queue and processing the prompt.

A decoder-only transformer generates autoregressively: it predicts token t+1 from tokens 1 to t, appends it, and repeats. Inside each attention layer every token is projected into a query, a key and a value. The new token's query is compared with the keys of all earlier tokens, and the result weights their values.

The naive loop runs the whole sequence through the model at every step. For a prompt of P tokens and an answer of N tokens, the projections alone are done for N·P + N(N-1)/2 token rows instead of P + N-1. For our lab's case (P = 16, N = 48) that is 1,896 rows against 63. The keys and values of token 5 never change once computed, because attention in a decoder only looks backwards, so recomputing them is pure waste. Recomputing full causal attention at every step adds more on top, since each pass is already quadratic in sequence length, as the Transformer paper sets out.

What does a KV cache keep? {#kv}

Definition

KV cache: per layer and per attention head, the key and value vectors of every token already processed, stored so later steps can read them instead of recomputing them.

With the cache, generation has two phases. Prefill runs the prompt through the model once, in parallel, and writes its keys and values to the cache; this is mostly matrix-matrix work. Each decode step then handles one new token: it computes that token's key, value and query, appends the key and value to the cache, and attends over everything stored, which is mostly matrix-vector work.

The new token still does real math, and attention still reads every cached key, so a step at a long context costs more than one at a short context. The cache only removes the recomputation of old tokens. The Hugging Face cache documentation describes this split between computing the new token and reusing stored keys and values. If long chats are new to you, why a long AI chat forgets your name explains the context window this cache lives in.

How does continuous batching share the server? {#batching}

Definition

Static batching: start B requests together and run decode steps until the longest one finishes; short answers sit idle in their slot.

Definition

Continuous batching (iteration-level scheduling): rebuild the batch at every step; a finished request leaves at once and the next one in the queue is admitted with a prefill.

The Orca paper (OSDI 2022) introduced iteration-level scheduling for this reason: with request-level batching, requests that finish early wait for the slowest one, and new arrivals wait for the whole batch.

Batching helps fairness first. One-at-a-time serving makes person 1,000 wait for 999 complete answers, while 16 slots let many people start early. It can also raise throughput. On a GPU, a small decode step is usually limited by reading the weights from memory, so adding rows is cheap and tokens per second can rise sharply. Our single-threaded JavaScript implementation achieved 1.85x decode throughput at 16 rows versus one row at context 64. We did not profile its bottleneck or measure a GPU.

What our lab measured {#lab}

The lab (labs/ai-18, node run.mjs, Node 22, no packages) builds a tiny transformer with random weights. Part A times the model directly. Part B replays a queue of 1,000 requests using only those measured step times, interpolated inside the measured grid. The simulator admits requests in queue order, estimates mixed-length batches by summing shares of equal-length measurements, and pauses decode during prefill. It models neither KV memory limits nor network delay. So the person at the front of the line always starts first, and TTFT here means arrival-to-first-token-ready time; it does not measure delivery to a client. The code and our reference results are on GitHub, so you can run it yourself: kv-cache-bench.

# measured, one 48-token answer to a 16-token prompt, 5 runs per path
no KV cache     median 567.05 ms   (min 566.47, max 575.72)
with KV cache   median  39.19 ms   (min  39.14, max  39.22)
ratio           14.5x, identical tokens on both paths

# measured, one decode step at context 64
1 row   0.751 ms      16 rows   6.482 ms    -> 1.85x tokens per second

# simulated queue: 1,000 requests at t = 0, prompts 8 to 32, answers 16 to 96
policy                         median TTFT   p95 TTFT   all done   tokens/s
one at a time, no cache          452.2 s      851.5 s    892.3 s       64
one at a time, KV cache           23.9 s       45.1 s     47.3 s    1,203
static batches of 16, cache       21.2 s       40.5 s     42.8 s    1,331
continuous batching, 16 slots     13.8 s       26.4 s     27.8 s    2,044

The cache alone moved the median from 452 s to 24 s (18.9x). Continuous batching on top moved it to 14 s (1.73x more). The measured 14.5x for one answer is smaller than the 30x drop in projected rows because attention over the cache, the output layer and fixed overhead remain.

How KV cache memory limits concurrency {#memory}

Each request keeps its own KV cache for as long as it runs. Its raw KV tensor storage per token, excluding allocation overhead, is:

bytes per token = 2 (key and value) x layers x KV heads x head size x bytes per number

assumed example: 32 layers, 8 KV heads, head size 128, 16-bit numbers
2 x 32 x 8 x 128 x 2 = 131,072 bytes = 128 KiB per token
a 4,096-token conversation = 4,096 x 128 KiB = 512 MiB for one request

Available KV memory limits how many tokens can remain resident. Compute capacity and latency targets can require a smaller batch; the vLLM tuning documentation walks through these scheduling and latency trade-offs. The PagedAttention paper (SOSP 2023) showed that storing the cache in fixed-size blocks, like virtual memory pages, cuts the waste from fragmentation and reserved space, so more requests fit. Long chats cost more to serve than short ones because the cache grows with every token. An agent's next request may contain a longer accumulated history, increasing its KV storage requirement. Re-sending an unchanged prefix can repeat prefill work unless the server reuses it; why an AI agent re-sends its history looks at that pattern.

Failure modes to watch in production: queue time dominating TTFT while the accelerator is idle (scheduler or admission limits too strict), out-of-memory pre-emption when long contexts arrive together (requests get evicted and recomputed), and long prompts stalling everyone's decode steps (servers split them with chunked prefill).

Trade-offs {#trade-offs}

What we saw when we ran it {#we-ran-it}

This is a separate, later run from the one in the lab table above, on 2026-11-06 at 15:37 UTC, so its timings differ a little from that table. We ran node labs/ai-18/run.mjs on an Apple M2 Pro with Node v22.13.1, on one thread, and the whole run took 8.6 s. The screen first printed the direct timings: a 48-token answer took a median of 39.6 ms with the cache on and 577.8 ms with it off, and the same tokens came out in every run. Then it replayed 1,000 simulated requests arriving at once.

Our terminal after the run, with the cache timings and the queue table.

The line that surprised us was static batching. Batches of 16 with the cache on only moved the median simulated wait for a first token to be ready from 24.14 s to 21.41 s. Continuous batching with the same 16 slots brought it down to 13.96 s, and the last request in line had its first token ready at 27.90 s, where one at a time with no cache it waited 903.42 s. That last gap mixes two changes, the cache and the scheduling. On this tiny random-weight model on one CPU thread, with no memory limits or network delay in the simulation, the cache gave the biggest single gain and letting finished requests leave the batch right away gave the next one; a real server has to check both against its own memory and traffic.

The Hugging Face Transformers cache explanation page.

Our cache path follows the split that page describes: compute the new token, and reuse the stored keys and values of earlier ones.

Our take {#our-take}

The KV cache made the larger difference in this lab. It removes repeated projections and feed-forward work on earlier tokens, though dense attention still reads a growing history. Batching then decides who waits, and on our toy model the two together took the median wait from minutes to seconds. These timings come from one CPU core, random weights and a simulated workload, so they describe this implementation only. If you run models on your own machine, as in answering with no network, you already use the cache; batching matters once more than one person shares the server.

The lab is a simulation built on a toy model on one machine; it describes general serving patterns from public papers and docs, not any company's private system.