Problem RestatementProblem
Design a high-concurrency inference API for a large language model that runs on a limited pool of GPUs. Many independent requests arrive all the time. A GPU is far more efficient when it processes many requests together (a batch). So the system should group compatible requests into shared GPU calls, increasing throughput, while keeping each request's extra waiting time small, and still stream each answer back to its own caller. Anthropic asked this twice.
RequirementsRequirements
- An API:
POST /v1/generate { model, prompt, max_tokens, temperature, stream }. - Batch compatible requests (same model; compatible settings) onto GPUs.
- Stream tokens per request as they are generated.
- Bound added latency: e.g., a request waits at most ~10–20 ms to join a batch.
- Timeouts, cancellation, priorities (paid vs free), and a clear "overloaded" response.
1.1 Why batching matters (simple math)
Generating one token for one request loads all the model weights from GPU memory, and that's the slow part. Generating one token for 32 requests at once loads the weights once and does 32× the useful work. So throughput can grow almost linearly with batch size, until the GPU's compute or memory limits.
ArchitectureArchitecture
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
flowchart LR
C["Clients"] --> GW["API Gateway - auth, rate limits"]
GW --> RT["Router - picks model replica"]
RT --> Q1["Replica 1 queue"]
RT --> Q2["Replica 2 queue"]
Q1 --> B1["Batcher / scheduler"]
B1 --> G1["GPU worker - model loaded"]
G1 -->|"tokens per request"| B1
B1 -->|"stream"| GW
Q2 --> B2["Batcher / scheduler"]
B2 --> G2["GPU worker"]- Router: sends each request to a replica of the right model with free capacity (least queue depth).
- Batcher (per replica): collects requests from its queue and forms batches for the GPU.
- GPU worker: runs the model on the batch, and returns the new tokens for each request every step.
- Streaming back: the batcher routes each generated token to the right caller's connection (SSE).
Batching Policies
3.1 Static (simple) batching
Wait until B requests are waiting or T ms have passed since the first one, whichever comes first. Then run the batch until all of them finish.
- Problem: a short answer (10 tokens) must wait for the longest answer (1,000 tokens) in its batch, and new requests can't join until the batch ends. The GPU sits partly idle as requests finish.
3.2 Continuous (in-flight) batching (our choice)
The model generates one token per step for every active request. So at every step:
- Remove requests that finished (hit an end token or max_tokens) and free their slots.
- Add waiting requests into the free slots (first process their prompt, the "prefill", then join the generation steps).
- The batch always stays full, short requests leave early, and new ones start almost immediately. This is how vLLM and TGI work.
3.3 What limits batch size
Not just the request count: each active request needs KV-cache memory on the GPU (its stored attention state), which grows with prompt + output length. The scheduler admits a new request only if there's enough KV memory for it. Paged KV memory (as in vLLM) reduces waste.
Deep Dive — Batching requests that are not the same lengthDeep dive
Batching is what makes a GPU efficient, and the requests in a batch have wildly different prompt and output lengths. How those differences are handled decides how much of the batch is real work.
Pad everything to the longest request
Take 32 requests, pad each one to the length of the longest, run them as one rectangular tensor.
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
flowchart LR
B["Batch of 32"] --> L["31 prompts around 100 tokens"]
B --> LONG["1 prompt of 4,000 tokens"]
L --> PAD["All padded to 4,000"]
LONG --> PAD
PAD --> WASTE["About 97% of the compute is padding"]
PAD --> HOLD["The slot is held until the longest generation finishes"]The batch costs what its longest member costs, in both memory and compute, so one long request makes thirty-one short ones expensive. Worse, the whole batch occupies the GPU until the last sequence stops generating, so short requests wait for a long one to finish before their slot is released.
Bucket by similar length
Sort waiting requests into length buckets and batch within a bucket, so padding is small.
Padding waste largely disappears. Two costs appear instead. A request now waits for other requests of its own size to show up, so the tail buckets fill slowly and their latency is poor. And nothing about the batch's lifetime changed: it still runs as a unit, and a slot is still held until the whole bucket finishes generating.
Continuous batching over a paged KV cache
Stop treating the batch as a fixed rectangle. Let sequences join and leave the running batch independently, and store each sequence's KV cache in fixed-size pages rather than one contiguous block sized to a maximum.
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
flowchart LR
Q["Queue"] --> SCH["Scheduler - every decode step"]
SCH --> RUN["Running batch - mixed lengths"]
RUN -->|"a sequence emits its final token"| FREE["Slot and its pages freed immediately"]
FREE --> SCH
KV["KV cache as fixed-size pages"] --> GROW["A sequence allocates pages as it grows"]
GROW --> NOWASTE["No reservation for a length it may never reach"]- Continuous batching removes the wait in both directions: a new request joins at the next decode step rather than waiting for a batch to form, and a finished sequence frees its slot immediately rather than waiting for its neighbours.
- Paged KV cache (the PagedAttention idea) removes the memory reservation. Without it, every sequence must reserve cache for its maximum possible length, which is what limits how many sequences fit on the GPU at all. Paging raises the concurrent batch size several-fold on the same hardware, and that is where most of the throughput comes from.
Length still matters for scheduling: a very long generation occupying a slot for minutes is worth routing to a separate pool, so it does not sit in the middle of a batch of short interactive requests holding pages the scheduler would rather recycle.
Key FlowsFlows
- A request arrives → auth and rate limit → the router picks a replica → it waits in that replica's queue (with a deadline).
- At the next step with space, the batcher admits it, running the prefill (maybe in chunks, so a very long prompt doesn't stall everyone).
- Each step, new tokens are sent to each request's stream.
- On finish, cancel or timeout: remove it from the batch and free its memory. If the client disconnects, cancel right away, since otherwise GPU time is wasted.
Fairness, Priorities and Overload
- Priority queues: paid or interactive traffic is admitted first, and batch/offline traffic fills leftover capacity.
- Per-tenant limits: tokens per minute and concurrent requests, so one customer can't fill every batch.
- Queue deadlines: if a request can't start within, say, 5 seconds, return 429/503 "overloaded" quickly instead of timing out later. Clients retry with backoff.
- Bucketing by length: keeping very long and very short prompts in separate pools or replicas can improve latency.
Scaling the Pool
- Each replica = one model copy on 1+ GPUs. Throughput per replica comes from load tests (e.g., 2,000 tokens/sec at p95 time-to-first-token of 500 ms).
- Replicas needed = peak tokens/sec ÷ tokens/sec per replica, plus headroom.
- Autoscaling is slow (loading weights takes minutes), so scale on forecasts and keep a buffer.
- Track separate SLOs: time to first token (users feel it) and tokens per second per request.
Trade-offs & AlternativesTrade-offs
| Decision | Choice | Why | Alternative |
|---|---|---|---|
| Batching | Continuous batching | Full GPU, short requests don't wait for long ones | Static batching: simpler, wastes GPU |
| Admission | Based on free KV-cache memory | Prevents out-of-memory | Fixed max batch size: under- or over-fills |
| Overload | Early 429 + priorities | Predictable latency | Unbounded queues: timeouts for everyone |
| Delivery | Per-request SSE streaming | Good UX | Return when done: slow first response |
Wrap-UpWrap-up
Batching lets a GPU serve many requests for about the cost of one step each, so put a batcher in front of every model replica. Use continuous batching: at every generation step, drop finished requests and admit waiting ones, limited by available KV-cache memory, and stream each request's tokens back to its caller. Add priorities, per-tenant limits, queue deadlines with fast "overloaded" errors, cancellation on disconnect, and capacity planning based on measured tokens per second per replica.