A few weeks ago I was reading the vLLM scheduler source, and I got the specific kind of déjà vu you get when you walk into a stranger's house and their kitchen is laid out exactly like your grandmother's.
There was a block table. There was a free list. There was a preemption path that could either swap a victim out to host memory or throw its work away and recompute it later. There was a fallback for when memory ran out mid-flight.
I had read this code before. In 2009. It was called an operating systems textbook.
This is not a criticism — it's the highest possible compliment, and it's also the most useful thing I can tell you if you're an engineer who feels like the ground moved under you in the last eighteen months. "AI infrastructure" sounds like a field you have to start over in. It mostly isn't. The dominant problems in LLM serving are memory fragmentation, cache affinity, queue scheduling, and rate limiting — and if you have ever tuned a JVM, sized a Redis cluster, or debugged a p99 that only spiked at 4pm, you already own the concepts.
You just have to see the translation table. So here it is.
Why this suddenly matters
The reason I'm writing this now rather than a year ago is that the interview loop changed.
For years, "design a system that serves an ML model" was a question you got if you applied for an ML infrastructure role. In 2026 it turns up in general backend loops — "design a customer support chatbot on top of a third-party LLM," "design safeguards for an agent that can take actions for a user," "walk me through serving a 70B model to 10,000 concurrent users." The guides tracking these loops describe the same shift: AI scenarios have moved out of specialist interviews and into standard ones, and cost-efficiency is now graded alongside latency and throughput rather than treated as a bonus.
That last one is the tell. Cost-and-operations grading is what happens when a technology stops being a research demo and becomes a line item. And when something becomes a line item, the questions asked about it stop being novel and start being the questions we have always asked about expensive machines.
Which is good news for you. Let's go through the four big ones.
1. PagedAttention is virtual memory. Actually, literally.
Start with the problem, because the problem is the fun part.
When an LLM generates text, it keeps a running scratchpad for every request called the KV cache — the key and value tensors for every token processed so far. It grows by one entry per token, on every single step, for the entire life of the request. It is large: for a big model with a long context, we're talking gigabytes per request, living on a GPU that has maybe 80 of them.
Here's the trap. Early serving systems stored each request's KV cache in one contiguous slab. Contiguous allocation needs a size up front. But you don't know the size up front — you have no idea whether the model will produce 12 tokens or 4,000. So the only safe move was to allocate for the maximum: reserve 2,048 tokens' worth of GPU memory for a request that might write 30.
If you have ever sized a buffer for the worst case, you already know how this ends. The vLLM paper measured it: existing systems were using only about 20–38% of their KV cache memory for actual token state. The other 60–80% was fragmentation and over-reservation. Two thirds of the most expensive RAM on earth, sitting empty, reserved for tokens that were never generated.
You have seen this bug. It is the allocator bug. Fixed-size slots waste the tail of every allocation (internal fragmentation); variable-size slots leave unusable gaps between live objects (external fragmentation); and the classic escape hatch is to stop demanding that a logical object be physically contiguous at all.
Which is exactly what PagedAttention does. Chop the KV cache into fixed-size blocks — say 16 tokens each. Scatter those blocks anywhere in GPU memory. Keep a block table mapping each sequence's logical block i to whatever physical block actually holds it. The attention kernel gets taught to gather across that table.
If you swap four nouns, that paragraph is from a 1970s paper on demand paging. Logical blocks are pages. The block table is a page table. The GPU allocator is the frame allocator. And the payoff is the payoff paging always gives you: internal fragmentation is bounded to at most one partial block per sequence instead of one giant wasted reservation, and external fragmentation disappears entirely because every block is interchangeable. Waste drops to a few percent. More requests fit in memory. More requests in memory means bigger batches, and bigger batches on a GPU means throughput — the paper reports 2–4× against the state of the art at the time, at equal latency.
Then it gets better, in a way that will make you grin if you've ever implemented copy-on-write. Two requests that share a system prompt have identical KV state for that prefix. Identical state, block table indirection, refcounts... so of course vLLM shares the physical blocks between them and only copies when one diverges. fork() for transformers.
And when GPU memory runs out mid-generation — because a batch of requests all decided to be chatty at once — the engine preempts. It picks victims and either swaps their blocks out to CPU memory or discards them and recomputes from the prompt later. Swap or recompute. That is a page-replacement policy with an unusually honest cost model.
If you want to feel rather than read this: the memory allocation playground lets you watch first-fit, best-fit, and buddy allocators shred a heap into unusable holes, and the page replacement simulator lets you run FIFO, LRU, Clock, and OPT against the same reference string and watch FIFO commit Bélády's anomaly in public. Same mechanics, smaller numbers.
2. Prefix-aware routing is consistent hashing, rediscovered under pressure
Now scale it out. One GPU becomes a fleet.
Your instinct — a good instinct, earned honestly — is round-robin or least-connections in front of N identical replicas. Stateless workers, uniform work, spread it evenly. This is correct for essentially every web service you have ever operated.
It is quietly terrible here, and the reason is that your replicas are not stateless. Each one has a warm KV cache full of prefixes it has already computed.
Picture a support-bot deployment. Every request carries the same 6,000-token system prompt — policies, tone, tool definitions, few-shot examples. Processing those 6,000 tokens is the prefill phase, and it is real compute. If a request lands on a replica that already has that prefix cached, prefill is a table lookup and the user sees a first token almost immediately. If it lands on a cold replica, the GPU grinds through 6,000 tokens of attention before emitting a single character.
Round-robin guarantees that every replica ends up caching every prefix, which means your effective cache size is the size of one replica no matter how many you buy. You have built an N-node cluster with 1 node's worth of cache. Meanwhile the requests bounce between them, evicting each other's work.
The fix is the thing you already know: route by content, not by counter. Hash the prefix, send matching prefixes to the same replica, let each node specialize. Cache affinity. That is consistent hashing wearing a name badge that says "prefix-aware routing," and the ecosystem converged on it from three directions at once:
- SGLang's router tracks approximate prefix locality with a radix tree and falls back to shortest-queue routing when nodes get imbalanced.
- GKE's Inference Gateway hashes the incoming token prefix and picks the replica most likely to hold it.
- llm-d goes exact: every vLLM pod publishes KV-cache events, the router maintains an index keyed by block hash, filters candidates down to pods that actually hold the prefix, and picks the least token-loaded pod within that set.
Read that last one again, because the two-stage structure is the whole lesson. Filter by cache locality, then balance load inside the filtered set. Pure locality routing creates hotspots — one viral prefix melts one pod. Pure load balancing throws away the cache. You need both, and "both" means locality as a filter and load as a tiebreaker.
Their published benchmark is eye-watering and I want to be precise about it rather than let you take home a number that doesn't survive contact with your workload: on 8 vLLM pods across 16 H100s, simulating 150 tenants with 6,000-token contexts, precise prefix-aware scheduling hit a P90 time-to-first-token of 0.54 seconds versus 31 seconds for approximate routing and 92 seconds for random. That's the 57× headline. Throughput roughly doubled against cache-blind configs.
The caveat is doing a lot of work: total KV demand was 73% of cluster capacity — deliberate, heavy cache pressure, six times what any single pod could hold. Under light load with a tiny shared prefix, the gap shrinks toward nothing. Which is itself the familiar lesson: cache-aware routing wins exactly when the cache is scarce and the workload is skewed, and if you've ever argued about whether to shard by user ID, you have had this exact argument before.
The consistent hashing simulator is the fastest way to internalize the failure mode — add and remove nodes, watch how much of the keyspace remaps, and see why virtual nodes exist. The load balancing playground runs round-robin, least-connections, EWMA, and power-of-two-choices against one shared request stream so you can watch a skewed workload wreck a naive policy in real time.
3. Continuous batching is a scheduler fighting head-of-line blocking
Third problem, and this one is pure queueing theory.
GPUs want big batches — that's how you amortize weight loading against arithmetic. So batch the requests. The naive version, static batching, collects N requests, runs them together until every one has finished generating, then starts the next batch.
You have already spotted it. Request A wants 20 tokens, request B wants 2,000. A finishes at step 20 and its slot sits there, occupied and idle, burning GPU for 1,980 steps while B rambles. And every request that arrived at step 21 waits in line behind B for no reason at all.
That is head-of-line blocking. Same phenomenon as one slow query pinning a connection pool, one fat HTTP/1.1 response stalling a pipelined connection, one giant job hogging a thread pool. Long job in front, short jobs starving behind it, utilization on the floor.
Continuous batching — the design shared by vLLM, TGI, and SGLang — fixes it by making the batch composition mutable every single decoding step. A request finishes, it leaves immediately. A slot opens, a queued request joins mid-flight. The batch is a living set, not a cohort. Iteration-level scheduling rather than request-level.
This has a prerequisite, and the prerequisite is section 1. You can only admit new work every step if you can hand out memory in small increments to a request whose final size you don't know — which is precisely what paged KV blocks give you. And you need preemption for the moment where you've admitted more work than will fit and something has to be evicted mid-generation. Paging and scheduling are co-dependent here, exactly as they are in an OS.
From there the research goes exactly where an OS person would guess. Chunked prefill splits a huge prompt into pieces and interleaves them with ongoing decodes, so one 100k-token prompt doesn't stall everyone else — that's time-slicing a long-running job. FastServe assigns priority by prompt length using a skip-join multi-level feedback queue, which is MLFQ, unmodified, from the same textbook. Others are chasing predictive shortest-job-first by guessing output length, which is SJF with the classic asterisk: SJF is provably optimal for mean waiting time and requires knowing job length, which you never do.
The entire arc — FCFS is bad, preemption helps, priority needs aging or it starves, SJF needs an oracle — is the scheduling chapter. It's just running on hardware that costs $30,000 a card, which is why people are suddenly willing to fund the research.
4. Token-per-minute limits are a token bucket that can't price the job
Last one, and this is where the analogy earns its keep by breaking in an interesting place.
LLM providers meter on two axes: requests per minute and tokens per minute. RPM is the limiter you know. TPM is the one that actually binds, because a single 200k-context call can eat as much quota as fifty 4k-token calls — which is how you end up at 5% of your RPM, eating 429s all day.
The algorithm underneath is the same token bucket that has been guarding APIs since forever. (The naming collision between "bucket tokens" and "LLM tokens" is the funniest accident in modern infrastructure and I refuse to stop enjoying it.) But a token bucket assumes cost is known at admission time: a request arrives, it costs one token, you check, you decide. With an LLM call you know the input size and nothing else — the output length is decided by the model, one token at a time, over the next several seconds. You are being asked to admit a job to a fixed-capacity system without knowing what it will cost.
Every strategy from there is a bet. Reserve pessimistically and you throttle yourself for capacity nobody used; debit as you stream and the limit becomes advisory, discovered only after you have blown it.
I went down this exact rabbit hole in Why your LLM app gets 429s even when you're under the rate limit — how each vendor accounts for it, the reserve-then-reconcile pattern, why your retry logic is making it worse, and what breaks once more than one worker shares the budget. For our purposes here the point is narrower, and it is the one thing on this list that your operating systems course genuinely did not prepare you for: admission control without a price tag.
Where the map actually tears
I've spent 2,000 words arguing that this is all familiar, so let me be honest about the four places it genuinely isn't. These are the parts worth thinking hard about — and, not coincidentally, the parts that separate a good interview answer from a great one.
Allocations grow after they're made. A malloc gives you a size and that size is a fact. A KV cache allocation grows by one block every few steps for the entire life of the request, and it stops growing at a moment nobody can predict. Your allocator is servicing a workload where every live object is slowly inflating. There's no classic analogue to "the heap is fine right now but will be full in eleven seconds because of objects that already exist."
Eviction cost isn't uniform. LRU assumes a miss costs about the same regardless of which item you dropped. Evict a KV block and the cost of getting it back is proportional to how much prefix has to be recomputed — dropping a block from a 100k-token conversation is enormously more expensive than dropping one from a 500-token chat. The right policy has to weigh recompute cost, not just recency. (Weighted eviction exists in the classic literature, but it's the exception there and the default here.)
One machine runs two opposite workloads. Prefill is compute-bound: a big parallel matrix crunch over the whole prompt. Decode is memory-bandwidth-bound: one token at a time, dragging the entire weight matrix across the bus for each. They want different batch sizes, have different SLOs (time-to-first-token versus time-per-output-token), and they're contending for the same silicon. It's as if your database ran OLAP and OLTP on the same box with no isolation — which is why the newer designs disaggregate them onto separate pools entirely.
Cost is a first-class design constraint, not an afterthought. The reason interviewers grade cost explicitly now is that the arithmetic is brutal and unavoidable. Cache hit rates aren't a latency nicety here; a bad routing policy doesn't just make things slower, it multiplies your GPU bill. This is the part where "just add replicas" — the reflex that solves most web-tier problems — is the wrong answer, and being able to say why is the answer they're looking for.
The actual takeaway
The pattern I keep landing on is this: new hardware constraints don't invent new algorithms, they re-run the old tournament with different scoring.
Paging won on 1970s minicomputers because RAM was scarce and expensive. GPU memory is scarce and expensive, so paging won again. Cache affinity beats naive load balancing whenever recomputation is costly. Preemptive scheduling beats run-to-completion whenever job lengths vary wildly. These aren't facts about operating systems. They're facts about resources under contention, and transformers didn't repeal them.
Which means the way to get good at AI infrastructure is not to memorize this year's serving frameworks — those will churn, and half the specific numbers in this post will be stale within eighteen months. It's to get so fluent in the underlying dynamics that you recognize them on sight when they show up wearing a new name. Fragmentation looks like fragmentation. Head-of-line blocking looks like head-of-line blocking. A cache with the wrong routing policy looks like a cache with the wrong routing policy, whether it's holding rows or attention keys.
That fluency is the thing I've been trying to build at Subroute — every algorithm is a live simulation you can run, tune, and break in the browser, because watching a policy fall over is worth more than reading about the failure mode. Right now it covers allocators, page replacement, cache eviction, rate limiting, load balancing, consistent hashing, and consensus, among others. Free, no signup.
And if you've operated any of this at scale and something above doesn't match what you've seen in production, I want to hear it. The gap between the paper and the pager is where the interesting stuff lives.