Iteration-Level Batching and the Cost of a Fixed Batch

A decode step in a transformer does the same amount of memory traffic regardless of how many sequences it serves. Every weight matrix in the model is read once per step, and the arithmetic performed on those weights is proportional to the number of sequences in the batch. This asymmetry is the whole reason batching exists: the expensive part of generating a token is moving the weights, and moving them for eight sequences costs the same as moving them for one. A serving system that admits eight requests and then waits for all eight to finish is therefore leaving most of its arithmetic units idle for as long as the shortest request has already completed.

The alternative is to let the batch change composition at every step. That sounds like a small implementation detail. It changes the utilisation curve, the memory accounting, and the failure modes of the whole system, and almost every other scheduling decision in a serving stack is built on top of it.

What one step actually costs

Take the dense part of a decoder-only model with $N$ parameters stored at $b$ bytes each. One decode step reads roughly $N b$ bytes of weights from high-bandwidth memory, plus the key and value vectors for each sequence in the batch. The multiply-accumulate work is about $2N$ floating-point operations per sequence. Ignoring the key-value traffic for a moment, the arithmetic intensity of a step is therefore close to $2/b$ operations per byte times the batch size, which is about one operation per byte per sequence in 16-bit precision.

An accelerator’s balance point, the ratio of peak arithmetic throughput to memory bandwidth, is typically a few hundred operations per byte for 16-bit matrix throughput. The consequence is direct: a decode batch has to reach a few hundred sequences before the arithmetic units become the limit. Below that point the step is bandwidth-bound, and every additional sequence admitted into the same step adds a nearly free amount of arithmetic on top of weight traffic that has already been paid for.

This is why the marginal cost of a sequence is not constant. Admitting a ninth sequence into a step that is already moving all the weights costs a fraction of the step time. Admitting the first sequence costs the entire weight read. A scheduler that treats sequences as interchangeable units of work, the way a CPU run queue does, gets this backwards.

The fixed batch and where it leaks

The straightforward design collects requests until a batch is full, runs the whole batch until every sequence emits an end-of-sequence token or hits its length limit, and only then admits new work. Two losses follow immediately.

The first is the ragged tail. A batch of sixteen requests where one generates 20 tokens and another generates 600 keeps fifteen slots occupied with finished work for the duration of the long one. The weights are still read in full, so the step time is unchanged, but the arithmetic per step falls toward that of a single sequence. Effective utilisation, measured as the ratio of useful arithmetic to peak arithmetic, decays roughly with the ratio of live sequences to reserved slots.

The second is padding. Batching sequences of unequal length into one rectangular tensor requires padding shorter sequences up to the longest, and the padded positions are computed and then discarded. Request-level batching commonly pads to the maximum sequence length seen in the batch. If the batch holds a 40-token prompt next to an 800-token prompt, the short one pays twenty times its own cost in wasted matrix work. Padding waste is not merely wasted cycles: it also inflates the key-value memory the step touches, which matters once memory is the constraint on batch size.

Neither loss is a bug in the kernels. Both are consequences of deciding the batch once and treating the decision as immutable.

Re-deciding at every step

Iteration-level batching, also called continuous batching, inverts the decision. After each decode step the scheduler examines which sequences produced an end-of-sequence token or reached their limit, removes them, and admits as many queued requests as fit in the remaining capacity. The batch for the next step is assembled fresh, with no padding requirement because each sequence contributes exactly one query token.

The mechanism rests on three pieces of state:

• A running set, sequences with allocated key-value memory that participate in every step.
• A waiting queue, requests whose prompts have not yet been processed.
• A memory allocator that decides whether a waiting request can be given residency.

The loop is small enough to write out. The real systems add preemption, priorities, and prefill chunking around it, but the skeleton is this:

class Scheduler:
    def __init__(self, capacity_blocks, block_tokens):
        self.running = []          # sequences with resident KV memory
        self.waiting = []          # requests not yet admitted
        self.free_blocks = capacity_blocks
        self.block_tokens = block_tokens

    def step(self, finished_ids):
        self.running = [s for s in self.running if s.id not in finished_ids]

        while self.waiting:
            req = self.waiting[0]
            want = req.prompt_len + req.max_new_tokens
            need = -(-want // self.block_tokens)   # ceiling division
            if need > self.free_blocks:
                break              # head of queue blocks; see admission control
            self.waiting.pop(0)
            self.free_blocks -= need
            self.running.append(req)

        return self.running       # exactly one query token per sequence

The step method is called once per generated token, and its output is a ragged batch. Because every sequence contributes a single position, the kernel sees a batch of $B$ rows with identical shape and no padding. The attention kernel reads a different key-value length per row, which is why paged attention and its block tables exist; that is a memory-layout question rather than a scheduling one.

Where the scheduler’s own cost lands

The scheduler runs on the host, between two device launches, so its latency sits on the critical path of every token. For a large model, one step is bounded below by the weight read, which is tens of milliseconds on a single device. A host-side decision taking tens of microseconds is invisible at that scale. For a small model on a fast device the step can fall below a millisecond, and per-step launch and scheduling overhead becomes a material fraction of the token time. This is the regime where serving frameworks start capturing the step as a device graph to remove launch overhead, at the cost of fixing the batch shape.

Iteration-level batching also interacts with the accelerator’s execution model. Each step is one kernel launch per layer, or one fused launch, and the arithmetic within a step is small relative to the memory traffic. The scheduler cannot make a step faster than the weight read; it can only ensure that as much arithmetic as possible rides along with that read. That is the entire objective, and it explains why the useful metric is not batch size but the fraction of steps in which the batch is at its memory-determined maximum.

Failure modes the design introduces

Changing the batch every step creates problems that a fixed batch does not have.

Starvation under a full queue. A first-come-first-served admission rule lets long-output requests occupy residency for their entire generation, and a stream of short requests behind them waits. Because residency, not arithmetic, is the scarce resource, the waiting queue can grow while the accelerator is busy. Weighted fair queuing or per-tenant quotas are the usual remedies, and both require the scheduler to be able to take memory back from a running sequence, which is the subject of preemption.

Batch churn. Admitting a request in the middle of a decode step means its first query token joins a batch that is already under way. If admission happens only at step boundaries, the request waits at most one step. If the implementation admits between kernel launches, the batch shape changes mid-flight and any captured graph is invalidated.

Memory as the real limit. The loop above stops admitting when the next request does not fit. Once residency is full, throughput is capped no matter how much arithmetic capacity remains, so the effective batch size is set by key-value bytes rather than by any property of the compute units. The arithmetic of that ceiling is the next thing to understand, and it is covered in how key-value bytes set the batch ceiling.

Interference from prompt processing. A newly admitted request must first process its prompt, which is a compute-heavy, bandwidth-light operation over many positions. Running that work inside a decode step lengthens the step for every sequence already generating. Whether to mix the two is a scheduling policy with a real latency cost, examined in splitting prefill from decode in the step.

The design constraint that forced iteration-level batching is simply that sequence lengths are not known in advance and are not equal. Any system that serves independent requests with independent stopping times will strand capacity if it commits to a batch at admission. The trade it accepts is a more complex memory manager and a per-step scheduling decision, in exchange for keeping the weight read amortised across a batch that stays near its memory-determined maximum for as long as the queue is non-empty.