Accounts of what makes a language model fast tend to stop at the model. Cheaper attention kernels, fewer bits per weight, a small model guessing ahead — all of it aimed at making one forward pass cost less. Then they note, almost in passing, that serving is affordable because requests are batched, as though a batch were something you assemble and hand over. It is not. Requests arrive at times nobody chose and stop after wildly different numbers of tokens; one wants a yes or a no, the next a thousand-word summary. Nearly every difficulty in production serving descends from that variance, and the two mechanisms that deal with it are a scheduler and a memory allocator rather than anything inside the network. This piece is about how a batch is kept full when its members keep leaving, and about the allocator that decides how many members it may have.
Static batching wastes the machine twice
Begin with the arrangement any reasonable engineer builds first. Requests are held until sixteen accumulate or a timer expires, run together from their prompts to their final tokens, and handed back. Simple, easy to reason about, and it discards most of the machine in two ways.
The padding is computed on. A batch is a rectangle, and prompts are not. Nine tokens, four hundred, eleven — the short ones are extended with filler to match the longest, and that filler travels through every layer, occupying arithmetic units and bandwidth, before being masked out. Real work performed on nothing. The waste is bounded, at least, since prompt lengths usually differ by a factor of a few.
The straggler sets the pace. Generation lengths are not so well behaved. One request stops after twenty tokens, another runs to two thousand, and the batch is not finished until its longest member is. Fifteen slots then hold finished sequences that still occupy memory and are still carried through every pass, producing nothing. Throughput is governed by the maximum rather than the mean, and when lengths span an order of magnitude the maximum of sixteen draws sits far above it. You pay for the longest answer sixteen times over and deliver the typical one.
The fix is to schedule tokens rather than requests
The remedy is a change of granularity and nothing else: treat a single forward pass as the unit of scheduling rather than a whole request, letting the composition of the batch change from pass to pass. This is continuous batching, also called iteration-level scheduling.
After every pass, any sequence that has emitted a stop token is retired, its slot released, and a waiting request admitted on the very next iteration. A table cleared and reseated between courses, rather than the whole sitting turning over at once. Nothing about the model changes, and the batch never drains.
Reported gains run to several times the throughput of static batching, with a qualification: the multiple is a property of the traffic, not the method. If every request produced the same number of tokens, static batching would already be near optimal. Under a real mixture of one-line replies, long summaries, and agent loops resending a growing transcript, the variance is large and so is the recovery.
Refilling the batch creates a problem of its own. Admitting a request is not the same operation as continuing one. A new arrival’s prompt must be processed — many thousands of positions at once, one large parallel operation limited by how fast the chip can compute. Everything already running needs one token each: a thin serial step limited by how fast weights stream out of memory. Prefill and decode. Opposite shapes, one machine.
Mixing them into one batch is the easy implementation, and it has a visible cost. A prefill over a hundred thousand tokens — a long document, a context filled to its limit — occupies the machine for as long as many decode steps, and every running request stalls for the duration. Users see a stream that was flowing and then stopped. Separate pools for the two phases avoid the stall but leave whichever is under-loaded idle, and the cache must cross an interconnect when a request graduates. So the tension is managed rather than solved: chunked prefill slices a long prompt into pieces of a few hundred tokens, one per decode batch, spreading the delay thinly at the cost of a slower first token for the sliced request; disaggregation splits the pools and pays with a transfer and a provisioning guess. Neither makes the difference in shape go away.
Figure 1. Static and continuous batching, slot by slot.
Nobody knows how long an answer will be
The scheduler now needs an answer to a question it cannot get: how many sequences fit at once. What decides that is the key-value cache , since each layer stores a key and a value for every token seen, growing by one entry per token generated. The final size is unknown until generation stops, and generation stops when the model decides it does.
The obvious allocator therefore reserves the worst case. Each slot gets one contiguous region large enough for the longest response permitted, nothing ever moves, and the attention kernel reads a clean contiguous span, which is what such kernels were written for. The arrangement is also close to a disaster. A request that stops after fifty tokens has spent its whole life holding room for four thousand.
Quoted plainly, it was common for well under half of reserved cache memory to be holding real data, and under a quarter was not unusual. This is internal fragmentation — waste inside each reservation rather than gaps between them — and it was the binding constraint on concurrency. The cache decides how many fit, how many fit decides throughput, and most of the memory set aside was empty. What is being squeezed here is the serving batch, a scheduling artifact rather than the statistical training batch size .
The answer was borrowed from operating systems
The move that fixed it is not a new idea, and that is the interesting part. An operating system has faced the identical problem for decades: processes want contiguous address ranges, memory arrives in awkward gaps, and nobody knows how much any will want. The settled answer is to stop handing out contiguous memory — fixed-size pages, one at a time, and a table per process translating addresses to whichever pages hold them.
Paged attention is that, applied to the cache. Cache memory becomes a pool of fixed-size blocks holding some tens of tokens each, sixteen being typical, each sequence carrying a table from logical positions to the physical blocks storing them. A block is allocated when the previous one fills and not sooner, anywhere in the pool. Waste per sequence collapses to the unused part of one partly-filled final block. The system that made both standard, from 2023, shipped scheduler and allocator together, because each is far less useful without the other.
The indirection turned out to be worth more than the space it saved. Because logical positions reach physical memory through a table, two tables can point at one block. Requests beginning with the same text — a shared system prompt, a few-shot preamble, the same document asked about repeatedly — have byte-identical cache contents there, so the prefix is stored and computed once, copying deferred until one diverges. The same holds for parallel samples from one prompt, common in decoding : the shared trunk exists once, not once per branch. This is the mechanism underneath the prompt-caching discounts providers advertise, and the discount is honest: the work genuinely was not repeated.
The costs land in three places. Every attention lookup now passes through a translation, so the kernel cannot stream a contiguous span and must gather from blocks scattered around the pool — which meant the fused kernels behind FlashAttention had to be rewritten to walk a block table while tiling. The block size is a trade with no comfortable answer: small blocks waste less inside but multiply table entries and overhead, large blocks the reverse. And the scheduler becomes intricate, since admitting sequences until memory is full guarantees it will sometimes run out mid-generation, so a running request must be preempted, its blocks reclaimed, its cache swapped to host memory or recomputed later. Eviction policies have bad days.
None of it touches the model. The arithmetic per token is unchanged, and so is the memory traffic that quantization attacks and the idle arithmetic that speculative decoding converts into extra tokens. Every generated token still costs a full read of every weight. A single request on an empty machine runs no faster under these schemes, slightly slower given the indirection and scheduling overhead. Throughput techniques in the strict sense: efficiency under load, and nothing whatever for the user waiting alone.
Figure 2. One block, two tables: the shared prefix.
A pinch of math: reserved memory against memory in use
Suppose the machine holds $B$ slots, each reserving room for the maximum permitted length $L_{\max}$, while the sequences in them reach actual lengths $L_1 \ldots L_B$. Utilization of the reserved cache is then
$$U = \frac{\sum_{i=1}^{B} L_i}{B \, L_{\max}} = \frac{\bar{L}}{L_{\max}}$$the ratio of mean realized length to maximum allowed, depending on nothing else about the distribution. Put plausible numbers in. A cap of four thousand tokens against an average completion of four hundred gives one tenth: nine tenths of the cache reserved, holding nothing. Raising the cap to serve the occasional long answer lowers utilization for everybody, which is the perverse part.
Under paging the waste per sequence is the unused remainder of its final block, which for block size $b$ lies between zero and $b-1$ tokens and averages roughly half of $b$, so across $B$ sequences
$$W \le B\,(b-1), \qquad \mathbb{E}[W] \approx \frac{B \, b}{2}$$and the term that matters is the one that is absent. There is no $L_{\max}$ in either expression. With blocks of sixteen tokens and sixty-four sequences the expected waste is a few hundred tokens, against the hundreds of thousands thrown away by reservation. That independence is the whole result: a generous length limit costs nothing until somebody uses it.
Figure 3. Utilization is the mean length over the cap.
What to carry forward
Everything here follows from one property of the workload: requests arrive at times nobody chose and stop after token counts an order of magnitude apart. Batch them the obvious way — collect a group, run it to completion, hand it back — and the machine is wasted twice: lightly on padding for shorter prompts, heavily on slots that finished early and sit inert until the longest is done, so throughput is set by the straggler and not the average. Continuous batching removes the second waste by scheduling at the granularity of a forward pass rather than a request, admitting waiting requests between passes so the batch never drains; the gains of several times are real, but they measure the traffic’s variance as much as the technique. Refilling continuously creates its own difficulty: admitting a request means processing a whole prompt at once while continuing one means producing a single token, operations of opposite shape, so mixing them stalls every running stream when a long prompt arrives while separating them leaves one pool idle — a tension managed by chunking prompts or splitting machines rather than resolved. How many fit is set by the key-value cache, which grows one entry per token to a length nobody knows in advance, so reserving the maximum per slot left well under half, often under a quarter, holding nothing. Paged attention borrows the operating system’s answer — fixed-size blocks, a per-sequence table, allocation on demand — and since the indirection lets two tables point at one block, a shared prefix is stored and computed once. What it buys is utilization under load. The lone user on a quiet machine gains nothing, and the scheduler that makes the rest work must now be able to evict a sequence in the middle of its answer.
The figures in this article follow the shared figure key , which explains what every shape, line style and colour means.
