How a serving engine actually works

Kwon et al., 2023 — PagedAttention and vLLM

The KV-cache page stopped at the arithmetic. Everything above that line is an operating system, and this is the part you actually operate.

Download serving_from_scratch.py — everything below runs from it. NumPy only, and no GPU: it simulates the queue and the allocator with counters.

I wrote the KV-cache page and it name-drops "continuous batching" and "PagedAttention" seven times without building either. That bothered me. Those two phrases are the difference between a demo that serves one person and a service that serves a thousand, and I was repeating them the way you repeat a library name you have never read the source of.

So here they are, both built. And the surprise, once you build them, is that neither one is about machine learning. Attention never changes. Not one line of the model changes. What changes is who gets a slot and where the bytes live — scheduling and memory management, the two problems an operating system was invented to solve.

A serving engine is an operating system

You already know both halves of this paper. Here is the first one — the batch loop everyone writes on day one: 

for batch in chunks(requests, 8):
    outputs = model.generate(batch)   # returns when the LAST one is done
    send(outputs)

That is run-to-completion scheduling. A 1970s batch mainframe. If seven replies finish in 8 tokens and the eighth runs to 128, seven slots sit there holding memory and doing nothing for 120 iterations. The fix is the same fix the OS people found: schedule between every iteration, not between every batch. 

while queue or running:
    while len(running) < slots and queue:
        running.append(queue.pop(0))   # a free slot is refilled NOW
    step(running)                      # every live sequence emits one token
    running = [r for r in running if not r.done()]

That is continuous batching, and it comes from Orca (Yu et al., "Orca: A Distributed Serving System for Transformer-Based Generative Models", OSDI 2022), where it is called iteration-level scheduling. Same idea, better name.

Now the second half. Here is how you would allocate the KV cache, and it is also the first thing anyone writes: 

cache = torch.empty(batch, MAX_MODEL_LEN, ...)   # reserve the worst case

That is a fixed-size contiguous allocation per process. You don't know how long the reply will be, so you reserve the maximum, and you reserve it contiguously because attention wants to index it as one array. Both of those choices cost you. PagedAttention's move is to notice that the operating system solved this in 1962 and stop reinventing it badly: fixed- size blocks, a per-sequence block table, allocate on demand.

Serving termMeansThe OS thing it is
Continuous batchingRe-decide the batch between every decode stepPreemptive scheduling, not run-to-completion
KV blockA fixed number of tokens' keys and valuesA page
Block tableLogical block → physical block, per sequenceA page table
Prefix sharingTwo sequences pointing at one prompt's blocksfork() with copy-on-write
PreemptionEvicting a sequence's blocks to admit anotherSwapping a process out
Prefix cacheReusing a previous request's prompt blocksA page cache, keyed by content

The one formula

Not an attention formula. The paper's actual contribution is an address translation, and it is the same one your MMU does:

physical_addr(seq, i) = block_table[seq][ ⌊i / B⌋ ] × B + (i mod B)

Read it as stages:

TermTypicalWhat it does
i0…seq_lenThe logical position of a token in this sequence
B16Block size in tokens. The one tuning knob on this whole page
⌊i / B⌋0…n_blocksLogical block number. Which page of my cache
block_table[seq]a list of intsThe page table. One per sequence. This is the whole idea
i mod B0…B−1Offset inside the block

One indirection. That is the paper. Everything else — the sharing, the near-zero waste, the concurrency — falls out of the fact that logical positions no longer have to be physically adjacent.

Static batching: the GPU you paid for, idle

The script simulates 64 requests arriving over time with realistically uneven output lengths, and counts slot-steps: a slot held for one iteration. A slot-step that produced a token is work. One that didn't is money.

Don't take my word for it. Here's the actual output:

static batching, 8 slots, 64 requests
  iterations to drain the queue :    709
  slot-steps held               :   5632
  slot-steps that did work      :   2088
  occupancy                     :  37.1%
  idle fraction                 :  62.9%
  throughput (tokens/iteration) :   2.94

continuous batching, 8 slots, 64 requests
  iterations to drain the queue :    305
  slot-steps held               :   2440
  slot-steps that did work      :   2088
  occupancy                     :  85.6%
  idle fraction                 :  14.4%
  throughput (tokens/iteration) :   6.85 ✓

speedup in iterations: 2.32x  (same tokens generated)

Identical tokens out of identical weights. Sixty-three per cent of the machine was being paid for and not used. You can see exactly where it goes if you print one batch at a time: 

occupancy over time, static batching (first 3 batches):
  batch 0: output lengths [8, 8, 8, 16, 16, 16, 64, 128]
           runs for 128 steps, slots busy 25.8%
  batch 1: output lengths [8, 8, 8, 8, 16, 32, 128, 128]
           runs for 128 steps, slots busy 32.8%
  batch 2: output lengths [8, 16, 16, 64, 64, 64, 64, 64]
           runs for  64 steps, slots busy 70.3%
Batch 2 is the control. Its output lengths are nearly uniform, and its occupancy is 70% instead of 26%. Static batching isn't slow because batching is bad — it's slow because reply lengths vary and you can't know them in advance. If every reply were 64 tokens, none of this page would exist.

Reserving memory you will never write

Now the allocator. Same workload, requests arriving and finishing over time, and a 40 GiB slice of an 80 GB card for KV cache. At Llama-2-7B shape that is 512 KiB per token, so 81,920 tokens total — the arithmetic is straight out of the KV-cache page.

Three allocators, one budget: reserve max_model_len for everyone, reserve each caller's own max_new_tokens, or page it. 

contiguous, reserve max_model_len (2048) for everyone:
  peak concurrent requests :     40
  admitted / rejected      :     90 / 310
  at the first rejection   : wanted 2048 tokens, 0 free, biggest hole 0

contiguous, reserve each caller's own max_new_tokens:
  peak concurrent requests :    159
  admitted / rejected      :    305 / 95
  at the first rejection   : wanted 1160 tokens, 2,927 free, biggest hole 959
  external fragmentation   : 1,968 free tokens that exist but not in one piece

paged, block size 16, allocated on demand:
  peak concurrent requests :    230
  admitted / rejected      :    400 / 0
  tokens held / written    : 77,696 / 74,744
  internal waste           : 2,952 (3.8%, and never more than 15 per sequence)
  external fragmentation   : 0 -- every free block fits every sequence

peak concurrency, same 40 GiB:
  40 (reserve max_model_len) -> 159 (reserve max_new_tokens) -> 230 (paged)
  = 5.8x more concurrent users, and nobody was turned away

Read the middle block twice, because it is the one people miss. There were 2,927 free tokens and the request wanted 1,160 — and it was rejected anyway, because the biggest single hole was 959. That's external fragmentation: you have the memory, just not in one piece. Paging doesn't reduce it, it abolishes it. Every free block is interchangeable, so a free block is always usable by anyone.

Internal waste is the other half. Reserving 2,048 tokens for a reply that runs to 40 wastes 98% of the reservation. With 16-token blocks you can overshoot by at most 15 tokens, once, in the last block. That is what the paper means by near-zero waste: it isn't clever, it's just bounded.

And block size is the one knob, so break it in both directions:

block size sweep, same workload and same memory:
  block | peak | rejected | internal waste | table entries at peak
      1 |  230 |        0 |              0 |        42978
      4 |  230 |        0 |            588 |        10829
     16 |  230 |        0 |          2,952 |         2792 ✓
     64 |  230 |        0 |         12,360 |          783
    256 |  230 |        0 |         47,624 |          275
   1024 |   80 |      226 |        146,270 |           80

At block size 1 there is zero waste and the block table has 43,000 entries to manage — you have rebuilt malloc's metadata problem. At 1,024 the waste (146,270 tokens) is nearly twice the data actually written, concurrency collapses to 80, and 226 requests get turned away. vLLM ships 16.

The block table, printed small enough to read

Here is a 10-token sequence with a deliberately silly block size of 4, on an allocator whose free list has been shuffled by earlier traffic: 

sequence of 10 tokens, block size 4
  logical block -> physical block
    0 -> 5
    1 -> 2
    2 -> 9
  physical blocks: [5, 2, 9]  <- NOT contiguous, and that is fine
  tokens 10, blocks 3, internal waste 2 tokens (last block only)

decode 3 more tokens, one at a time:
  n_tokens= 11 table=[5, 2, 9]  wrote into the current block
  n_tokens= 12 table=[5, 2, 9]  wrote into the current block
  n_tokens= 13 table=[5, 2, 9, 0]  appended a new physical block

Blocks 5, 2 and 9. Nowhere near each other. Attention reads the sequence through the table, so it never notices — this is precisely why the paper needed a custom attention kernel, and precisely why nothing about the attention maths changed. And growth costs one block append, not a realloc-and-copy of the whole cache.

Copy-on-write, because you have used fork()

Ask for four samples from one prompt and the naive engine keeps four copies of the prompt's cache. But those four sequences are identical until the first token diverges. So: share the blocks, refcount them, and copy only the block someone actually writes into. 

prompt 90 tokens = 6 blocks: [0, 1, 2, 3, 4, 5]
blocks used after prompt: 6

forked 4 samples from it (parallel sampling):
  blocks used: 6  (unchanged -- all four share)
  refcounts  : [5, 5, 5, 5, 5, 5]
  naive copy would need 30 blocks; we hold 6
  saved: 24 blocks = 192.0 MiB

now each sample generates its first token (they diverge):
  sample-0: table=[0, 1, 2, 3, 4, 6]  copy-on-write triggered: True
  sample-1: table=[0, 1, 2, 3, 4, 7]  copy-on-write triggered: True
  sample-2: table=[0, 1, 2, 3, 4, 8]  copy-on-write triggered: True
  sample-3: table=[0, 1, 2, 3, 4, 9]  copy-on-write triggered: True
  blocks used now     : 10  (one private block each, the rest still shared)

Five shared blocks, one private each. Blocks 0–4 are still refcount 5 and still one copy. 192 MiB saved on a 90-token prompt, which sounds absurd until you remember that half a megabyte per token is the number from the KV-cache page.

Then the bug that this design invites. Sample-0 finishes. Do you free its blocks? 

the reference-counting guard:
  released sample-0. block 0 refcount now 4
  block 0 back on the free list? False  <- still referenced, so no
  released everyone. block 0 on the free list? True
This is a double free, and it fails silently. Delete the if self.refcount[b] == 0 guard and sample-0 finishing hands a live prompt block back to the pool. The next request allocates it, writes its own keys into it, and sample-1 keeps decoding — against someone else's prompt. No crash. No error. Just wrong tokens. Refcounting isn't bookkeeping here, it's the correctness argument.

Prefix caching: prefill you already did

Same trick, across requests instead of within one. A 300-token system prompt shared by everyone is 300 tokens of prefill that only ever needs doing once. Hash a block's prefix, and if it's resident, point at it. 

fraction of requests using the shared system prompt: 100%
  prompt tokens seen        :  17,000
  prompt tokens prefilled   :   2,888
  prefill work saved        :  83.0%
  block cache hit rate      :  84.0%

fraction of requests using the shared system prompt: 50%
  prompt tokens seen        :  17,000
  prompt tokens prefilled   :  11,528
  prefill work saved        :  32.2%
  block cache hit rate      :  32.6%

fraction of requests using the shared system prompt: 0%
  prompt tokens seen        :  17,000
  prompt tokens prefilled   :  17,000
  prefill work saved        :   0.0%
  block cache hit rate      :   0.0%

The saving is exactly the shared prefix and not one token more, which is the honest way to think about it: prefix caching is a workload property you can engineer, not a speedup you turn on. Put the volatile part of your prompt (the timestamp, the user id) at the front and your hit rate is the 0% row.

My script hashes whole prefixes in a dict, so it only matches from token 0. RadixAttention, in SGLang (Zheng et al.), keeps those prefixes in a radix tree instead. Two requests that share the first 300 tokens and diverge after still share every block up to the divergence, the tree finds the longest match automatically, and eviction is LRU on the leaves. A trie of prompts. You have written one.

Prefill and decode are two different jobs

The last piece is scheduling again, and it starts with the arithmetic intensity argument from the KV-cache page: MACs per byte of memory traffic, and whether a card can keep its arithmetic units fed. The script also applies a roofline — a pass takes as long as the slower of its arithmetic and its memory traffic — using an A100's two spec numbers. Nothing here is measured on a GPU; it is a count and a division. 

arithmetic intensity (MACs per byte moved), Llama-2-7B shape:
  prefill, 2048-token prompt :    783.8 MACs/byte
  decode, one token per seq, batch 32:     7.49 MACs/byte
  a card needs roughly 100-300 to keep its arithmetic units busy

roofline time (A100-shaped: 156 TMAC/s, 2.0 TB/s):
  prefill 2048 tokens :   11407.4 GMAC,   14.6 GB ->   73.12 ms  (compute-bound)
  decode step, batch 32:     165.4 GMAC,   22.1 GB ->   11.03 ms  (memory-bound)

Two different machines. Now put them on one GPU and let a 2,048-token prompt arrive while 32 people are mid-reply: 

shared GPU  : 32 sequences decoding, 40 steps
  median inter-token gap    :    11.03 ms
  p95 inter-token gap       :    11.03 ms
  worst inter-token gap     :    84.16 ms

disaggregated: 32 sequences decoding, 40 steps
  median inter-token gap    :    11.03 ms
  p95 inter-token gap       :    11.03 ms
  worst inter-token gap     :    11.03 ms ✓

the stall: one token took 84.2 ms instead of 11.0 -- 7.6x
all 32 decoding users saw it, and none of them sent that prompt.

That is head-of-line blocking, and note where it shows up: the median is untouched, the tail is 7.6× worse, and the victims are 32 people who did nothing. Your p50 dashboard will look fine.

The standard mitigation is to slice the prefill:

chunked prefill: same prefill, sliced, one chunk per iteration
  chunk  2048 ->  1 iterations, worst gap   84.16 ms
  chunk   512 ->  4 iterations, worst gap   29.32 ms
  chunk   256 ->  8 iterations, worst gap   20.18 ms
  chunk   128 -> 16 iterations, worst gap   18.31 ms

Watch the last two rows: halving the chunk from 256 to 128 barely helps. Below a certain size each chunk is dragging all 13 GB of weights across the bus anyway, so you have hit the memory floor and are only adding passes. Chunking caps the stall; it can't remove it, and it spends decode iterations on prefill work.

Disaggregation is the other answer. DistServe (Zhong et al.) puts prefill and decode on separate GPUs and ships the KV cache between them. A prefill then cannot delay a decode at all, and each pool can be sized and parallelised for its own bottleneck — FLOPs on one side, bandwidth on the other. The cost is a cache transfer per request, which is why this is a later idea and not the first one.

When there are no free blocks left

One more failure the block design lets you see clearly. Admit a request when the pool is empty and nothing can move: 

4 sequences x 2 blocks = 8/8 blocks used
free blocks: []

every sequence now wants one more token:
  seq-0 append -> OutOfBlocks: no free physical blocks
  no free block, no policy: the scheduler cannot advance ANY
  sequence, and none of them can finish without advancing.
  <- this is the deadlock

with preemption (vLLM's swap-or-recompute, all-or-nothing):
  preempt seq-3, evict its 2 blocks, push it back on the queue
  free blocks now: [6, 7]
  seq-0 append -> ok, table=[0, 1, 6], n_tokens=33

Every sequence needs one more block, every block is taken, and no sequence can finish without growing. Classic. The resolution is the OS one: pick a victim, take everything it has, put it back on the queue. Note everything — preemption is all-or-nothing per sequence, because a half-evicted sequence can't run at all. The evicted sequence loses its cache, not its tokens: it gets re-prefilled later, or its blocks get swapped back from host memory.

The code

Pure NumPy. No torch, no GPU, and nothing timed — this is a simulation with counters, the way the FlashAttention page counts memory traffic instead of benchmarking a kernel. Every function under 20 lines.

Download the full script — 736 lines plus 7 runnable demos. Then: 

python3 serving_from_scratch.py

The scheduler, entire:

def simulate_continuous_batching(reqs, slots):
    queue = list(reqs)
    running = []
    step = 0
    busy_slot_steps = 0
    total_slot_steps = 0
    tokens = 0
    while queue or running:
        # admit: refill any free slot from whoever has arrived
        while len(running) < slots and queue and queue[0].arrival <= step:
            r = queue.pop(0)
            r.start = step
            running.append(r)
        if not running:                    # idle gap, nobody has arrived yet
            step = queue[0].arrival
            continue
        for r in running:                  # one iteration = one token each
            r.generated += 1
            tokens += 1
            busy_slot_steps += 1
        total_slot_steps += slots
        step += 1
        for r in running:
            if r.done() and r.finish is None:
                r.finish = step
        running = [r for r in running if not r.done()]
    return dict(steps=step, tokens=tokens, busy=busy_slot_steps,
                capacity=total_slot_steps, reqs=reqs)

And the allocator — PagedAttention's storage layer, in about forty lines:

class BlockAllocator:
    def __init__(self, n_blocks, block_tokens=BLOCK_TOKENS):
        self.block_tokens = block_tokens
        self.free = list(range(n_blocks))      # a free list, nothing more
        self.refcount = {}                     # physical block -> refs
        self.n_blocks = n_blocks
        self.copies = 0                        # copy-on-write events

    def allocate(self):
        if not self.free:
            raise OutOfBlocks("no free physical blocks")
        b = self.free.pop(0)
        self.refcount[b] = 1
        return b

    def share(self, b):
        """Another sequence now points at this block. Do NOT copy it."""
        self.refcount[b] += 1
        return b

    def free_block(self, b):
        """The reference-counting guard: only the LAST owner really frees."""
        self.refcount[b] -= 1
        if self.refcount[b] == 0:
            self.free.append(b)
            del self.refcount[b]
            return True                        # actually returned to the pool
        return False                           # still shared, keep it alive

    def copy_on_write(self, b):
        """Writing into a shared block: take a private copy first."""
        if self.refcount[b] == 1:
            return b                           # sole owner, write in place
        new = self.allocate()
        self.refcount[b] -= 1
        self.copies += 1
        return new


class Sequence:
    """A sequence is a block table plus a length. That is the whole object."""

    def append_tokens(self, n):
        """Grow by n tokens, allocating a new physical block when needed."""
        for _ in range(n):
            slot = self.n_tokens % self.alloc.block_tokens
            if slot == 0:                                  # current block full
                self.table.append(self.alloc.allocate())
            else:                                          # writing inside one
                last = len(self.table) - 1
                self.table[last] = self.alloc.copy_on_write(self.table[last])
            self.n_tokens += 1

    def fork(self, name):
        """Parallel sampling: same prompt, new sequence, shared blocks."""
        child = Sequence(name, self.alloc)
        child.table = [self.alloc.share(b) for b in self.table]
        child.n_tokens = self.n_tokens
        return child

    def release(self):
        for b in self.table:
            self.alloc.free_block(b)
        self.table = []

Now break it

This is the part that actually makes it stick. Reading won't do it. You debug for a living — and every one of these is a bug you have already shipped in some other system, which is the point.

Break thisWatch for
In demo 1, call simulate_static_batching onlyIdle fraction 62.9%, throughput 2.94 tokens/iteration instead of 6.85. Batch 0 runs 128 steps at 25.8% occupancy.
Set fixed_reserve=MAX_MODEL_LEN in contiguous_churnPeak concurrency drops from 230 to 40 on the same 40 GiB, and 310 of 400 requests are rejected.
Set BLOCK_TOKENS = 1024Internal waste goes from 2,952 tokens to 146,270 — twice the data actually written — and concurrency collapses to 80.
Set BLOCK_TOKENS = 1Zero waste, but the block tables hold 42,978 entries at peak instead of 2,792. You have rebuilt malloc's metadata.
In free_block, drop the if self.refcount[b] == 0 and always self.free.append(b)Demo 4 prints block 0 on the free list? True while three samples still point at it. Silent corruption, no exception.
In demo 7, delete the victim.release() preemptionOutOfBlocks forever: no sequence can grow, so no sequence can finish, so nothing frees. Deadlock.
Then read the PagedAttention paper — the motivation section on memory waste and the method section on the block table and sharing. Those two carry the whole idea. Skip the kernel implementation details unless you write CUDA, and read the evaluation for the shape of the result, not the numbers: the paper reports 2–4× throughput over the systems it compared against in 2023, on their hardware and their workloads, and my simulation is a counter, not a claim about your cluster.

On the maths anxiety

There is none here, and that is worth saying out loud. This page has one division and one modulo. If you can do i // 16 and i % 16, you have the maths.

The only arithmetic that gets close is the roofline in the last section, and it is two divisions: MACs divided by peak MACs per second, bytes divided by peak bytes per second, take the bigger one. That is a bound, not a prediction. I use it to show the shape — prefill compute-bound, decode memory-bound — because the shape is what decides your architecture, and the shape survives being wrong about the constants.

What this page needs instead is the stuff you already have: free lists, refcounts, fragmentation, head-of-line blocking, scheduling fairness, cache hit rates, deadlock. Those are the concepts under the arXiv numbers, and it is why this is the paper on the whole site an engineer is best equipped to read cold. If you have ever debugged a memory leak, you are qualified.

Interviews go here more often than people expect. "Why does batching help throughput but not latency?" is the KV-cache page. "How do you serve 200 concurrent users on one GPU?" is this one, and the answer is not a bigger card — it's continuous batching and paged KV, in that order.

Where to go next

This page gave you the two mechanisms and the failure modes, deliberately without a line of CUDA and without a benchmark. These fill in the halves I skipped. And if you haven't yet, read the KV cache first — the memory arithmetic here is assumed, not derived. After that, quantisation shrinks the same bytes, MLA shrinks the cache architecturally, and speculative decoding attacks the same memory-bound decode step from the other end.

Order I'd take them in: Anyscale first for the intuition about batching, then the vLLM blog post, then the paper, then SGLang. The paper is the easiest one on this site to read after the blog posts — it is written by systems people, for systems people, and you are one.