LLM Inference System Design: KV Cache, Batching and the Gateway in Front

Say you are asked in a system design round: "Design a service that lets 500 internal teams call open-weight LLMs, with streaming, fair usage and a sane bill." If your answer is "load balancer, some GPU servers, Redis cache", the interviewer will nod politely and then ask why your p99 time to first token is 9 seconds while the GPUs sit at 30% utilisation.

LLM serving breaks instincts from normal web services. A request is hundreds of tiny steps, memory decides how many users fit, and the cheapest request is one whose prompt you have already seen. Here is the whole stack as you would draw it: the GPU engine first, then the gateway in front.

An LLM generates text in two phases: a prefill pass that reads the entire prompt at once, then a decode loop that produces one token per forward pass until a stop token or max_tokens. The two phases stress the hardware differently, and most serving optimisations exist because of that.

Prefill pushes all 2,000 prompt tokens through the model in parallel. That is big matrix multiplication, exactly what GPUs are built for, so prefill is compute-bound. It decides how long the user stares at a blank screen.

Decode produces one token per sequence per step, but the GPU must still read every weight from memory: about 16 GB for an 8B model in 16-bit precision. At a few terabytes per second, one sequence alone tops out at a few hundred tokens per second whatever your FLOPs. Decode is memory-bandwidth-bound. Decode 64 sequences in the same step and you read the weights once but get 64 tokens. Batching turns idle compute into throughput, and the KV cache limits how big the batch can get.

The metrics that matter are time to first token, time per output token, throughput and goodput, each tracked at p50 and p99 rather than as an average. A single "latency" number hides the fact that users feel the first token and the streaming speed separately.

• Time to first token (TTFT): arrival to first streamed token, so queueing plus prefill. For chat, users notice this most.
• Time per output token (TPOT), also called inter-token latency (ITL): the gap between tokens during decode. Past reading speed it matters less for chat, but a lot for agents and code tools.
• End-to-end latency: roughly TTFT + TPOT x (output tokens - 1). A 600-token answer at 30 ms per token adds 18 seconds, so output length is a design decision.
• Throughput: total tokens per second across all requests. Your cost per million tokens is built on it.
• Goodput: the request rate you can sustain while meeting both TTFT and TPOT targets. The DistServe paper made it the headline metric, and it is the honest one: throughput at a p99 TTFT of 20 seconds is not a product.

A KV cache is GPU memory that holds the attention key and value vectors for every token already processed, so each decode step only computes keys and values for the one new token instead of the whole sequence again. Without it, generating token 1,000 would mean reprocessing 999 tokens, and generation cost would grow quadratically.

The cache grows by one entry per layer every decode step, and you do not know up front how long an answer will be, so you do not know how much memory a request will need.

KV cache memory formula, worked for Llama 3.1 8B

KV cache bytes = 2 (one K, one V) x layers x KV heads x head dimension x bytes per value x tokens. Llama 3.1 8B's published config has 32 layers, 32 query heads but only 8 key-value heads (grouped-query attention, GQA), a head dimension of 128, and bfloat16 weights, so 2 bytes per value.

per token = 2 x 32 layers x 8 kv_heads x 128 head_dim x 2 bytes
          = 131,072 bytes = 128 KiB

4,096-token request   = 128 KiB x 4,096   = 512 MiB
8,192-token request   = 128 KiB x 8,192   = 1 GiB
131,072-token request = 128 KiB x 131,072 = 16 GiB  (full context window)

Without GQA (32 kv_heads) = 512 KiB per token, 4x more

Now put it on an 80 GB GPU. The weights take about 16 GB in bf16. Leave headroom for activations and runtime overhead and you might have around 55 to 60 GB for the cache. At 512 MiB per 4K-token request, that is roughly 110 to 120 requests in flight. One user pasting a 128K-token document eats the space of 32 normal chats. That is why the KV cache, not compute, usually caps your batch size, and why GQA (fewer KV heads) was such a big deal for serving cost.

PagedAttention stores each request's KV cache in small fixed-size blocks that can live anywhere in GPU memory, tracked by a block table, the same way an operating system maps virtual pages to physical frames. It came from the vLLM paper (Kwon et al., SOSP 2023).

Before it, many servers reserved a contiguous slab per request sized for the maximum output, so a request that stopped after 50 tokens still held memory for 2,048. The paper reports 2 to 4x higher throughput than earlier systems at similar latency by nearly eliminating that waste. Blocks also make sharing cheap: sequences sampled from the same prompt point at the same physical blocks and copy on write. When memory runs out, the scheduler preempts a request, frees its blocks and recomputes it later.

Prefix caching

Prefix caching keeps KV blocks around after a request finishes so a later request with the same leading tokens can reuse them and skip that part of prefill. vLLM does this by hashing each full block together with the hash of the blocks before it, so a block only matches if the entire prefix up to it is identical, and evicts unused blocks in LRU order.

It is a big win when every request starts with the same long system prompt or tool definitions, and for multi-turn chat where turn five resends turns one to four. So put stable content first and variable content last; a timestamp at the top of the system prompt kills your hit rate. For multi-tenant setups, vLLM can add a cache salt to the hash so tenants cannot probe each other's cached prompts.

Static batching waits for a group of requests, runs them together, and returns nothing until the longest one finishes. Continuous batching (iteration-level scheduling) re-forms the batch on every decode step, so a finished sequence leaves immediately and a waiting one joins on the next step.

The idea came from the Orca paper (OSDI 2022). Picture a static batch of eight: seven answers finish in 40 tokens, one rambles for 800, and the GPU spends 760 steps decoding a batch of one while requests queue. With continuous batching those seven slots refill within a step. Modern engines such as vLLM, SGLang and TensorRT-LLM all do this, so treat it as the default in an interview.

Chunked prefill

Continuous batching creates a new problem: when a 30,000-token prompt joins, its prefill can stall everyone else's decode for hundreds of milliseconds, and every streaming user sees a stutter. Chunked prefill splits a long prefill into pieces and mixes those pieces into steps alongside ongoing decodes, under a per-step token budget.

vLLM's V1 engine enables chunked prefill by default, schedules pending decodes before prefills, and exposes the budget as max_num_batched_tokens. Its docs describe the trade-off directly: a smaller budget (say 2,048) protects inter-token latency, a larger one (8,192 or more) gives better TTFT and throughput. There is no free setting, only the one that matches your SLO.

Speculative decoding has a small draft model guess several tokens ahead, then the big model verifies all guesses in one pass. Since decode is bandwidth-bound, checking five tokens costs about the same as producing one. Leviathan et al. showed the output distribution is unchanged and reported 2 to 3x speedups on T5-XXL. The catch: gains depend on the draft's hit rate and shrink at large batch sizes, when the GPU is no longer idle.

Quantization stores weights in fewer bits: FP8 or INT8 halves memory versus bf16, 4-bit formats like AWQ or GPTQ quarter it. Fewer bytes per decode step and more room for KV cache improve both TPOT and batch size. The cost is quality, which you must measure on your own evals, especially for maths, code and non-English text. FP8 KV cache is a separate knob that doubles how many tokens fit.

When a model does not fit on one GPU, you split it. Tensor parallelism shards each layer across GPUs and lowers per-token latency, but needs NVLink-class links because GPUs exchange results inside every layer. Pipeline parallelism puts different layers on different GPUs, tolerates slower links, but adds bubbles and does not speed up a single token. Tensor parallel within a node first, pipeline across nodes when you must.

Prefill/decode disaggregation

Prefill/decode disaggregation runs prefill and decode on separate GPU pools and ships the KV cache from one to the other. The DistServe paper (2024) argued that co-locating the phases forces them to interfere, and that separating them lets you size and parallelise each pool for its own SLO. vLLM supports it as an experimental feature, and its docs are blunt that it does not improve throughput; the point is independent tuning of TTFT and ITL and tighter control of tail inter-token latency.

Put the pieces together and an LLM serving system has three layers: a gateway that deals with tenants and money, a router that picks the best replica for this prompt, and an engine per GPU replica whose scheduler forms a new batch every step and manages the paged KV cache.

Why a KV-aware router instead of round robin? Prefix caching is per replica, so if turn five lands on a different GPU from turns one to four, you pay the full prefill again. A good router scores replicas on prefix overlap, queue depth and KV utilisation. The Kubernetes Gateway API Inference Extension formalises this as an endpoint picker that reads model server metrics such as prefix cache status. Watch for hot spots: if everyone shares one system prompt, pure prefix affinity sends all traffic to one replica, so cap affinity with a load threshold.

An LLM gateway is the single entry point in front of all your models and providers: it authenticates callers, enforces per-tenant token budgets, routes each request to the right model or provider, streams the response, and records usage and cost. It is where platform policy lives, so product teams never talk to GPUs or vendor APIs directly.

Rate limit tokens, not requests

Request-per-minute limits are nearly useless here: one 100K-token prompt costs more than a thousand "hi" messages. Limit tokens per minute per tenant, often input and output separately. Output length is unknown at admission, so reserve prompt tokens plus max_tokens up front and refund the unused part when the stream ends.

// Admission: reserve the worst case, settle the real usage later.
async function admit(tenant: string, promptTokens: number, maxTokens: number) {
  const reserve = promptTokens + maxTokens;
  const ok = await bucket.tryTake(`tpm:${tenant}`, reserve); // token bucket in Redis
  if (!ok) throw new HttpError(429, 'token budget exceeded', { retryAfterSec: 10 });
  return reserve;
}

async function settle(tenant: string, reserved: number, usage: { input: number; output: number }) {
  const unused = reserved - (usage.input + usage.output);
  if (unused > 0) await bucket.refund(`tpm:${tenant}`, unused);
  await meter.record(tenant, usage); // feeds billing and cost dashboards
}

Routing and fallbacks across providers

Route by need: a small cheap model for classification and short replies, a large one for hard reasoning, a long-context deployment only for long prompts. If the self-hosted pool is saturated or a provider returns 429s or 5xx errors, retry on another provider behind a circuit breaker with a retry budget, so an outage does not become a retry storm.

Fallbacks have sharp edges. Tokenizers differ, so token counts and context limits change, and tool-call formats differ, which can break parsers. You can only fail over cleanly before the first token streams; after that, switching providers means restarting the answer and telling the client.

Semantic caching: useful, but careful

A semantic cache embeds the prompt and returns a stored answer if a past prompt is "close enough". It saves money on FAQ-style traffic, but "cancel my order" and "don't cancel my order" can sit very close in embedding space. Never serve answers that depend on user data, time or tool results from a shared cache, and key by tenant, model and system prompt version. Exact-match caching of temperature-0 calls is much safer; make semantic caching an opt-in per use case.

Streaming with SSE and cancellation

Tokens go back over Server-Sent Events: one HTTP response with Content-Type text/event-stream, each chunk a data: line, ending with a done marker. SSE works through most proxies, but you must disable response buffering at every hop, or users get the whole answer in one lump after 20 seconds.

HTTP/1.1 200 OK
Content-Type: text/event-stream
Cache-Control: no-cache

data: {"choices":[{"delta":{"content":"Paged"}}]}

data: {"choices":[{"delta":{"content":"Attention"}}]}

data: {"usage":{"prompt_tokens":2048,"completion_tokens":2}}

data: [DONE]

Cancellation is the part people forget. When a user hits stop, the gateway must abort the upstream request all the way to the engine so its KV blocks are freed. Otherwise the GPU decodes 1,500 tokens nobody reads, and you pay for them. Propagate an abort signal through every hop and test it.

Observability and cost per 1M tokens

Log per request: tenant, model, input, cached and output tokens, TTFT, TPOT, finish reason, and whether a fallback fired. Scrape per replica: queue length, waiting sequences, KV utilisation, preemptions and prefix hit rate. Rising preemptions with high KV usage means you need more replicas or tighter limits, not faster GPUs.

Self-hosted cost per 1M tokens is GPU cost per hour divided by tokens served per hour, times a million. A hypothetical $2.50-per-hour GPU sustaining 2,500 output tokens per second serves 9 million tokens an hour, about $0.28 per million, but only at that utilisation. At 10% load at 3 a.m., each token costs ten times more. That is why teams self-host steady base load and burst to per-token hosted APIs.

1. 1

   Clarify workload and SLOs (3 to 5 minutes)

   Chat, agents or batch? Typical prompt and output lengths, peak requests per second, context limits, open-weight or hosted models, and p99 targets for TTFT and TPOT.

2. 2

   Back-of-envelope sizing

   Compute KV cache per token, weights per replica, concurrent sequences per GPU, and how many replicas the peak needs. Write the numbers down.

3. 3

   Draw the high-level path

   Client, gateway, router, engine with scheduler and paged KV cache, GPU workers, metrics. Say where streaming and auth happen.

4. 4

   Go deep on the engine

   Continuous batching, PagedAttention, prefix caching, chunked prefill. Mention speculative decoding, quantization and parallelism with their trade-offs.

5. 5

   Go deep on the gateway

   Token-based limits, routing by model and prefix, fallbacks, caching rules, cancellation, and per-tenant metering.

6. 6

   Failure modes and scaling

   Replica crash mid-stream, provider outage, long-prompt abuse, cache hot spots, autoscaling on queue depth and KV usage rather than CPU.

• Mistake: autoscaling GPU replicas on CPU or GPU utilisation. A memory-bound decode can show modest utilisation while the queue explodes. Scale on queue depth, waiting requests and KV usage.
• Mistake: treating an LLM request like a 50 ms API call with a 30-second timeout at the load balancer. Long generations get cut off; use streaming and per-route timeouts.
• Mistake: one global queue with no priority. A batch job submitting 10,000 summaries will starve interactive chat unless you separate priorities or pools.
• Mistake: ignoring output length. max_tokens is your biggest cost and latency lever, so set it per use case.

If you remember one thing: the engine is a memory manager that happens to do matrix maths, and the gateway is a billing and fairness system that happens to proxy HTTP. Get both right and the rest is sizing. As a next step, take the Llama 3.1 8B numbers above, pick your own SLOs, and work out how many GPUs a 200 requests-per-second chat product needs.