Continuous Batching

A batch of generation requests finishes at different times. Under request-level batching the whole batch is held until the longest completion is done, so a 20-token reply sharing a batch with a 2000-token one occupies its slot for the full 2000 steps.

Continuous batching schedules at each decode iteration instead. A sequence that emits EOS is evicted at the end of that step, a queued request is admitted in its place, and the batch composition changes continuously.

What it requires

The transformer itself is indifferent to this — attention over a batch of sequences at different lengths is the same operation — but three things must hold:

• The KV cache must be allocated per sequence and freed independently, which is what paged attention provides.
• Newly admitted requests need a prefill pass, which is compute-bound, while the in-flight sequences want a decode step, which is bandwidth-bound. Mixing them in one forward pass is the scheduling problem.
• Admission must be bounded by free cache blocks, not by a batch-size constant, or the scheduler will admit a request it cannot finish.

When that constraint binds, something must be preempted. Recomputing the evicted sequence’s cache is usually cheaper than swapping it to host memory and back — prefill is fast, and PCIe is not.

def serve(model, queue, cache, max_batch: int):
    running: list[Request] = []

    while queue or running:
        # admit what the free cache can actually hold
        while queue and len(running) < max_batch:
            if not cache.can_allocate(queue[0].prompt_len):
                break
            running.append(cache.admit(queue.pop(0)))

        # one decode step across every live sequence
        logits = model.step([r.next_token for r in running],
                            [r.block_table for r in running])

        for request, token in zip(running, logits.argmax(-1)):
            request.append(token)

        finished = [r for r in running if r.is_done()]
        for request in finished:
            cache.free(request)
            request.respond()
        running = [r for r in running if r not in finished]

Admitting purely first-come-first-served is simple and starves nobody, but it lets one long prompt block the queue; most production schedulers add a shortest-remaining-first bias for the prefill queue and accept the fairness cost. The can_allocate check must reserve for the expected output length, not just the prompt, or preemption becomes the normal case rather than the exception.