AI Frontiers, part 32: Serving is the product — PagedAttention and continuous batching

Part 32from the AI Frontiers series · 65 parts in all

Text generation has an unusual property for a compute workload: the expensive part is not arithmetic. Producing one token requires reading every weight in the model, and the matrix multiplies that follow are small relative to the memory traffic they require. The accelerator spends most of its time waiting for bytes, which means the thing that determines throughput is not how fast the chip can multiply but how many requests can be kept in flight at once.

That single observation explains the entire architecture of modern inference serving, and 2023 was the year the field built it. In September a group at Berkeley published PagedAttention and the vLLM system (Kwon et al.), reporting throughput improvements of two to four times over the existing alternatives on the same hardware and, more importantly, a memory management scheme that made the whole problem tractable. This entry is about why that mattered, because the serving layer turned out to determine whether a product existed at all.

The two regimes, and why one of them is idle

Inference has two phases that behave nothing alike. Prefill processes the prompt: a large matrix multiplication over the whole input, computable in parallel, compute bound. Decode produces tokens one at a time, each requiring a full pass over the weights for a single position, and it is memory-bandwidth bound with arithmetic units mostly idle.

This is the same dichotomy speculative decoding exploits by spending the idle compute on candidate tokens, and the same reason quantization speeds up decoding more than prefill: fewer bytes per weight means less traffic per token. The practical consequence for serving is that decode throughput is governed almost entirely by how many sequences you can process per weight read. Serving one request at a time wastes the machine. Serving a hundred at once costs almost nothing more per token.

Which raises the obvious question: why not always batch a hundred requests? Because a batch cannot execute until all its members are ready, and members finish at different times. The naive schedule holds the whole batch until the longest generation completes, so a request that needs three tokens waits behind one that needs three thousand. Utilization collapses in the presence of heterogeneous workloads, which is precisely what a real service has. Orca (Yu et al.) had demonstrated the fix in 2022 — iterate at the level of the batch rather than the request, admitting new sequences as old ones finish — and vLLM's contribution was to build that on top of a memory manager that made it practical.

The operating-system analogy, taken literally

The memory problem was the blockade. A transformer's key-value cache grows with sequence length, and early serving implementations allocated it as one contiguous buffer sized for the maximum possible sequence. A request that might reach 2,048 tokens reserved 2,048 tokens of cache from the moment it arrived, and a finished request's memory could not be reused until the allocation was freed. Internal fragmentation ran as high as 60 to 80 percent in reported measurements — the majority of the expensive memory in the system devoted to space that would never be used.

PagedAttention's answer is virtual memory. Split the cache into fixed-size blocks, address them through a per-sequence table, allocate on demand, and let the blocks be physically non-contiguous. Waste drops to a fraction of one block per sequence. And once the cache is addressed by table rather than by pointer, two things become possible that were previously awkward: sequences that share a prefix can share the underlying blocks, and memory can be reclaimed the instant a sequence finishes, freeing the slot for a new request in the next iteration.

The prefix-sharing property is the one with the longest reach. Beam search and parallel sampling share prompt blocks for free, which is a research convenience. But a production service where every request begins with the same two thousand tokens of system instructions shares those blocks across the entire batch, and the cost of those tokens is paid once. That is prefix caching, and it is the same mechanism that later became a billable feature at every major provider — the single largest cost lever available to most applications, and it arrived as a side effect of a memory allocator.

What this did to the economics

It is hard to overstate how much of the industry's product surface rests on this layer, so it is worth following the chain of consequences explicitly.

A serving stack with continuous batching and paged memory can hold many more concurrent sequences in the same accelerator memory, and each token generated costs one weight read amortized across all of them. Throughput per dollar rises by a large factor, which lowers the price per token, which makes longer prompts and more retrieval affordable, which changes what applications are buildable. Every product decision downstream — how much context to include, whether to retrieve three documents or thirty, whether to run a second verification pass — is really a question about the price of tokens, and that price was set by the memory manager.

The second consequence is that latency and throughput became a tradeoff to be managed rather than a single number to be optimized. A service can maximize requests per second by batching aggressively, at the cost of time-to-first-token; it can minimize latency by serving small batches, at the cost of throughput. Neither is correct in general. The right answer depends on whether the user is waiting on a chat response or a background job is filling a queue, which is why later systems grew request priorities and separate pools rather than one queue. This is ordinary capacity planning imported into a new domain, and the teams that treated it that way built better products than the teams that looked for a single "fast" configuration.

The supporting cast that made batching possible

Paged attention is not sufficient on its own, and the rest of the stack was assembled in the same period.

FlashAttention (Dao et al.) rewrote the attention kernel to avoid materializing the score matrix, tiling the computation and recomputing rather than storing. It reduced both memory and time, and it is the reason long sequences are tractable at all. Grouped-query attention (Ainslie et al.) reduced the size of the cache that the pager had to manage by sharing key-value heads across groups of query heads, at negligible quality cost — a change that is invisible in benchmarks and dominant in memory arithmetic. Quantization (Dettmers et al.; Frantar et al.) shrank the weights so that more of the model fits in fast memory, which is the difference between one accelerator and two. Offloading work (Sheng et al.) showed that a single device with limited memory could serve large models at reduced throughput, which mattered for anyone without a cluster.

Each of these is a serving optimization rather than a modeling advance, and none of them changed what the model could do. Together they changed what it cost, which is the thing that decides whether a capability becomes a product.

Measuring a serving stack honestly

The metrics that matter here are not the ones most teams report, and the mistakes are consistent enough to enumerate.

Time to first token is what a user perceives during the wait before anything appears, and it is governed by queueing delay plus prefill. Inter-token latency is what they perceive while reading, governed by decode. Throughput is tokens per second across the whole service. Goodput is the fraction of requests meeting their latency target, which is the only one of the four that describes whether the service is actually working. A stack can report excellent throughput while failing a third of its requests' latency objectives, and an average latency number will hide exactly that.

The benchmarking methodology matters as much as the metrics. A closed-loop load generator — a fixed number of clients each waiting for a response before sending the next request — reports latency that improves as you add load, because the clients themselves throttle the request rate. The only honest way to measure a system under pressure is open-loop: generate requests on a schedule independent of responses, and report the latency distribution and the number of requests that missed their target. Nearly every published serving comparison that flatters batching is open-loop, and nearly every disappointed internal benchmark is closed-loop.

The queue is the system

Once batching and paging are in place, what remains is scheduling, and the scheduling problem is older than any of this. Requests arrive at a rate you do not control, service times vary by an order of magnitude depending on how many tokens are generated, and preemption is expensive because a preempted sequence may need its cache recomputed or swapped.

Three consequences follow, and every mature deployment ends up implementing them. Admission control: reject or defer work rather than accepting an unbounded queue, because a queue that grows without limit converts a capacity problem into a timeout problem that every user experiences. Priorities: separate interactive traffic from batch work, since a chat response and a nightly classification job have different objective functions and should not share a first-in-line policy. Fairness: prevent one client sending enormous prompts from starving everyone else, which is why per-tenant token budgets exist.

None of this is new; it is the standard apparatus of any service that handles variable work. The reason it is worth stating is that the field spent a year treating inference serving as a machine learning problem when the hard part had become a systems problem. The people who shipped reliable products in this period were usually the ones who had built a queue before, and the model was the least interesting component they owned.

Why the model is not the whole story

The temptation in this field is to treat the serving layer as plumbing — necessary, undifferentiated, and somebody else's problem. That is wrong in a specific and expensive way.

A model is a set of weights. A product is a model plus a scheduler, a cache policy, a batching strategy, a quantization decision, a request queue and a price list. Two companies using identical weights and identical hardware can differ by a factor of five in cost per request, and every dollar of that difference is margin. The reason this is underappreciated is that serving optimizations are invisible in a demo: the output is identical, so the only observable difference is on the invoice.

It is also why the published throughput numbers in serving papers deserve more attention from builders than the published benchmark scores of models. A benchmark says what a system can do. A serving number says what it costs to do it, and the second determines how many of them you can afford to run.

The uncomfortable implication for anyone building on hosted models is that none of these levers is yours. If the provider's batching policy, cache lifetime and quantization choice are invisible, then your cost per request is a number you can influence only by changing what you send — less context, fewer retries, smaller models, more caching on your side. That is why the engineering disciplines in this series that look like prompt hygiene are really cost engineering, and why a team that measures tokens per request usually finds a factor of two sitting in the pipeline before anyone touches a model.

By October 2023 the field had a competent open serving stack, a memory management scheme borrowed wholesale from operating systems, and a much clearer picture of where the costs lived. What it did not yet have was a good way to serve long contexts efficiently, a way to make one model do the work of several through routing, or a settled understanding of how much of the workload should be handled by small local models. All three arrived in the following years, and all three are extensions of the same idea: the request, not the model, is the unit of work.

Works Cited

Ainslie, Joshua, et al. "GQA: Training Generalized Multi-Query Transformer Models from Multi-Head Checkpoints." arXiv, 2023, arxiv.org/abs/2305.13245. Accessed 5 Oct. 2023.

Aminabadi, Reza Yazdani, et al. "DeepSpeed-Inference: Enabling Efficient Inference of Transformer Models at Unprecedented Scale." arXiv, 2022, arxiv.org/abs/2207.00032. Accessed 5 Oct. 2023.

Dao, Tri, et al. "FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness." arXiv, 2022, arxiv.org/abs/2205.14135. Accessed 5 Oct. 2023.

Dettmers, Tim, et al. "LLM.int8(): 8-bit Matrix Multiplication for Transformers at Scale." arXiv, 2022, arxiv.org/abs/2208.07339. Accessed 5 Oct. 2023.

Frantar, Elias, et al. "GPTQ: Accurate Post-Training Quantization for Generative Pre-trained Transformers." arXiv, 2022, arxiv.org/abs/2210.17323. Accessed 5 Oct. 2023.

Kwon, Woosuk, et al. "Efficient Memory Management for Large Language Model Serving with PagedAttention." arXiv, 2023, arxiv.org/abs/2309.06180. Accessed 5 Oct. 2023.

Pope, Reiner, et al. "Efficiently Scaling Transformer Inference." arXiv, 2022, arxiv.org/abs/2211.05102. Accessed 5 Oct. 2023.

Shazeer, Noam. "Fast Transformer Decoding: One Write-Head Is All You Need." arXiv, 2019, arxiv.org/abs/1911.02150. Accessed 5 Oct. 2023.

Sheng, Ying, et al. "FlexGen: High-Throughput Generative Inference of Large Language Models with a Single GPU." arXiv, 2023, arxiv.org/abs/2303.06865. Accessed 5 Oct. 2023.

Xiao, Guangxuan, et al. "SmoothQuant: Accurate and Efficient Post-Training Quantization for Large Language Models." arXiv, 2022, arxiv.org/abs/2211.10438. Accessed 5 Oct. 2023.

Yu, Gyeong-In, et al. "Orca: A Distributed Serving System for Transformer-Based Generative Models." Proceedings of the 16th USENIX Symposium on Operating Systems Design and Implementation, 2022. Accessed 5 Oct. 2023.