←Writing

Paged-KV + Continuous Batching From Scratch: What Building Tessera Taught Me About vLLM's Design

June 10, 2026·
LLM inferenceservingvLLMsystems

You don't really understand a serving engine until you've had to decide who frees a KV block when a sequence gets preempted mid-step.

Tessera is my from-scratch LLM stack — distill a teacher into a small student, then serve it. The serving half reimplements the two ideas that made vLLM what it is: a block-paged KV cache (PagedAttention, Kwon et al. 2023) and a continuous-batching scheduler. Building them at readable scale forced every design decision that the papers gloss over. Three of them are worth writing down.

1. Paging is really about not reserving

The naive KV cache reserves a contiguous max_seq_len slab per sequence. Almost all of it is wasted: most requests finish long before max_seq_len, and you can't know in advance which ones. The slab model turns "how many concurrent requests fit in GPU memory" into a worst-case calculation.

Paging replaces the reservation with a shared pool of fixed-size blocks (16 tokens in Tessera) and a per-sequence block table mapping logical position → physical block:

shape = (n_layers, num_blocks, block_size, n_kv_heads, head_dim)
self.k = torch.zeros(shape, device=device, dtype=dtype)
self.v = torch.zeros(shape, device=device, dtype=dtype)

Now internal fragmentation is bounded by block_size − 1 tokens per sequence — not max_seq_len − actual_len. Capacity becomes an expected-case calculation, which is where all of vLLM's throughput headroom actually comes from. The often-quoted kernel cleverness is downstream of this one memory decision.

Prefix sharing falls out for free: because a block is just a ref-counted pool entry, two sequences that share a system prompt share physical blocks, and share() is a ref-count bump instead of a copy:

def share(self, block: int) -> int:
    self._ref[block] += 1     # copy-on-write prefix sharing
    return block

2. The scheduler's real product is an ownership contract

Continuous batching is usually described as "recompose the batch every step" — finished sequences release blocks immediately, waiting requests admit into the freed space next step, and a 5-token completion never queues behind a 500-token one. That part is genuinely simple:

def schedule(self) -> list[Sequence]:
    self._admit()                        # waiting → running, if blocks allow
    ...                                  # grow each seq by one block if needed
    return self._apply_preemptions(...)  # the exact set the engine may run

The subtle part is the contract: schedule() does all admission, block allocation, and preemption, and the engine never mutates scheduler state mid-step. The engine runs exactly the returned set, nothing else.

I learned why this contract exists by breaking it. If the engine iterates over a snapshot of the running set while preemption edits it underneath, sequences can be released twice or not at all — and a leaked KV block is the worst kind of bug, because nothing crashes. The pool just quietly shrinks until throughput degrades, thousands of steps later. Tessera's allocator hard-fails on double-frees, and the engine tests cover exactly this preempt-mid-step path, because it's the failure mode I actually hit.

3. Preemption policy: evict the newest, restart the cheapest

When a running sequence needs one more block and the pool is empty, someone has to give memory back. Tessera evicts the most recently admitted sequence:

def _pick_victim(self, protect, preempted):
    for seq in reversed(self.running):   # LIFO: newest admission first
        ...

LIFO isn't arbitrary. The newest sequence has the least accumulated KV, so evicting it throws away the least work — and the preempted sequence goes back to the front of the waiting queue with its generated tokens intact, so it resumes (by recomputing its KV) as soon as memory frees up. That's the recompute flavor of vLLM's recompute-vs-swap choice: at small scale, recomputation is strictly simpler, and simplicity is what lets you test the invariant that matters — no block is ever leaked or double-freed across admit → grow → preempt cycles.

What's deliberately still missing

Tessera's append/gather are plain torch indexing: correct, test-covered, and slow — reading paged KV through a gather costs an extra materialization that a real engine can't afford. The fused paged-attention kernel that reads block tables directly inside the attention kernel (vLLM's actual kernel contribution) is the explicit next step, and doing the memory manager first is what makes that kernel's job description precise: same math as my FlashAttention forward, different addressing.

That's the meta-lesson of building it yourself. vLLM's design reads as one insight (paging) plus a long list of consequences handled correctly — ownership, preemption, sharing, and eventually the kernel that makes the indirection free. You only see the consequences when you have to write the tests for them.

← Back to Writing