Serving
Paged attention
KV cache memory managed in small blocks instead of one slab per request, the way an operating system pages RAM. Wasted reservations become room for more users.
Naive serving reserves the worst case: for every accepted request, memory for the longest context you allow, held from arrival to finish. Actual conversations are much shorter than the maximum most of the time, so a large share of reserved cache is simply idle while a request lives, and a tenth request gets rejected even though most of the memory is unused.
Paged attention applies the classic OS solution. Cut the cache into fixed-size blocks (say 16 tokens each) and give a request as many blocks as it currently needs, adding more as its context grows. Sequences of the same conversation can also sit in non-contiguous blocks, because attention gathers from a block table instead of assuming one contiguous slab.
The waste stops being tens of percent of a worst-case reservation and becomes at most one block per sequence. That is the whole idea, and it is why serving stacks built on this approach accept far more concurrent users on the same memory. The number to remember is utilization: reserved versus actually in use.
The block table also has to be managed, which adds bookkeeping and fragmentation questions of its own. In interviews the useful framing is the analogy: paged attention is virtual memory for the KV cache, and the same trade (more utilization, more pointer chasing) appeared there first.
A worked example
Ten requests, each reserving its worst case of 4,096 tokens of KV cache up front, on a model whose cache costs 160 KiB per token (40 layers, fp16). 16-token blocks are available.
- Worst-case reservation: 4,096 x 160 KiB = 640 MiB per request, 6.25 GiB for all ten.
- The conversations actually average 1,200 tokens: 1,200 x 160 KiB = 187.5 MiB in real use.
- Utilization: 187.5 / 640 = 29 percent. Of the 6.25 GiB reserved, about 4.4 GiB does nothing.
- With 16-token blocks the tail waste is at most 15 unused slots x 160 KiB = about 2.3 MiB per request instead of hundreds of MiB.
Paged blocks turn a 29 percent-utilized slab into near-full utilization, so the same memory hosts several times more concurrent users.
Where this shows up
- LLM Serving InternalsBefore a streamed answer reaches the screen, a scheduler admits the request into a batch of others running on rented GPUs, decides when its prompt gets read, and keeps it fed token by token until the answer finishes. Serving is that layer, and it runs on arithmetic that is unforgiving. Decode, the steady writing of the answer one token at a time, is bandwidth bound: every step re-reads the model's weights from card memory whether the batch holds one request or sixty, so a pool serving one request at a time pays its most expensive constant for a single token. Batching is the fix, sharing that read across every request running at once, which is why aggregate throughput climbs almost free as the batch grows. The resource that bounds the batch is not compute but memory: the KV cache, the per-request scratch space the model keeps so it can continue each prompt, grows with every layer and with sequence length, and when it fills, the batch size dial quietly stops mattering while the rest of the traffic waits. Prefill, the reading of the prompt that produces that scratch space, is compute bound and costs about 2 FLOPs per parameter per prompt token, which is why two requests sharing a cached opening start dramatically faster than two strangers. Interviewers test this material because the numbers decide the architecture: whether to rent dedicated cards sized for a peak, paid by the hour whether busy or not, or pay per token on a shared pool; how many cards a model swallows for its weights alone before a single seat exists; and why the tail, the p95 wait experienced by the slowest request, is what the service level agreement actually measures. The coding version of this topic is real: an xAI onsite round asks candidates to implement a simplified inference engine, meaning request batching, per-batch inference, and token-level result collection, and other labs ask the design version, batching requests up to a fixed size or a wait cap, whichever comes first. The three challenges below work the core arithmetic: the bytes one cached token occupies, the seats a card's free memory can grant, and the seconds prefill spends before the first token exists.
- Design ChatGPT: Tiers & Rate LimitsDesign ChatGPT is the most-cited systems design question at AI companies, and it is really one question: when everyone arrives at once, who gets served, who waits, and who is told no, all without the paying tier ever noticing. The answer interviewers grade against has three parts. First, three pools: a small provisioned pool whose cards exist for one tier only, a larger shared pool where paid requests carry priority over free ones, and the queue itself, which lives in card memory, not in a message broker. Second, a token-bucket rate limiter at the gateway, held in Redis for atomicity under concurrent writers, that admits free arrivals at a chosen share of demand and reconciles the token count after each grant, so a burst of arrivals is answered instantly without consulting a GPU. Third, shedding: a request refused at the gateway with a 429 costs nothing; the same request admitted into a saturated pool holds an expensive seat and lengthens every wait behind it, which is why the tail wait punishes utilization non-linearly, and why an incident that removes 30% of capacity can turn a 97 millisecond paid wait into an 850 millisecond one. Interviewers test this because every knob in the design is a money or trust decision: renting burst capacity for a launch day, tightening the bucket over a jammed pool, or letting the free tier shed so the subscribers do not notice an outage. The three challenges below work the mechanics: the admit count a token bucket grants, the queue wait the utilization formula quotes, and the shed arithmetic that keeps the shared pool from jamming.