Iteration-Level Batching: Reforming the Batch at Every Token

A batch in the classical sense is a unit of work with a shared lifetime: requests enter together, one kernel executes over all of them, and the group leaves when the last member finishes. That contract suits image classification, where every request costs the same fixed number of operations. It suits autoregressive text generation badly, because each request has its own output length and the model performs one forward pass per token per sequence.

A decoder-only transformer generates one token per sequence per pass, so a batch of B sequences advances every sequence by exactly one position. Place a request that needs 20 output tokens beside one that needs 2,000 and the batch still executes 2,000 passes. From pass 21 onward the short request contributes nothing to the arithmetic but continues to occupy a row of every matrix multiplication and its slice of key-value cache. The useful fraction of that pair is (20 + 2000) / (2 x 2000), just over one half. Nearly half the machine’s work produces tokens that will never be read.

Two resources idled by a fixed batch

Compute is wasted because the duration of a batch is the maximum of its members’ lengths, not the mean. The waste grows with the spread of the distribution: a batch of eight sequences whose lengths are 64, 128, 256, 512, 512, 1024, 1024 and 2048 spends 2048 passes on 5,568 useful positions out of 16,384, a duty cycle of about 34 percent. Real traffic rarely has that spread within a single arrival window, but any traffic with a long tail of output lengths produces the same effect at a smaller scale.

Memory is wasted for an unrelated reason. A request-level scheduler must guarantee that each admitted sequence can finish without running out of cache, so it reserves space for the maximum output length in advance. That reservation is what caps the batch size, and it caps it far below what the arithmetic units could absorb. The consequence is that the batch that actually runs is chosen by a worst case rather than by the work available.

The loop that replaces the batch

Iteration-level batching, also called continuous batching, makes the batch a decision taken per forward pass instead of a lifetime assigned at admission. The server keeps two collections: sequences currently generating, and sequences waiting to enter. Before every pass it rebuilds the input batch from both.

The iteration has a fixed sequence of steps. Finished sequences are retired and their cache released. Waiting sequences are admitted while the token budget and the cache budget both allow it. The input batch is assembled, with a new sequence contributing its whole prompt and a running sequence contributing one token. The model runs, a sampler picks one token per sequence, and each running sequence advances by one position. Then the loop repeats, and the composition of the batch may be entirely different from the previous iteration.

def schedule(self):
    # retire finished work first so its cache blocks are available to newcomers
    for seq in [s for s in self.running if s.done]:
        self.running.remove(seq)
        self.free_blocks += seq.blocks

    while self.waiting:
        seq = self.waiting[0]
        # worst-case reservation: this is the conservative policy, not the only one
        need = ceil((seq.prompt_len + seq.max_new) / self.block_size)
        if need > self.free_blocks or len(self.running) >= self.max_seqs:
            break
        self.free_blocks -= need
        seq.blocks = need
        self.running.append(self.waiting.popleft())

    # a new sequence contributes its prompt, a running one contributes one token
    batch = []
    for seq in self.running:
        batch.extend(seq.prompt if seq.prefill else [seq.last_token])
    return batch

The reservation in that sketch is deliberately pessimistic, and it is exactly the policy that paged allocation removes. Once cache grows a block at a time, admission no longer needs a worst-case guarantee, and the batch can be filled to whatever the current free memory supports. That change is the subject of Paged KV Cache.

The budget that actually binds

Two quantities limit an iteration, and they are not the same quantity.

The first is the number of positions the model processes in the pass. A prompt of L tokens costs L positions of prefill work; a decode step costs one position per running sequence. Serving stacks therefore cap total positions per iteration rather than sequences per iteration, and the cap is in the low thousands for a single accelerator. A prompt longer than the cap cannot be admitted whole and must either wait or be split, which is the argument for chunked prefill.

The second is cache memory, and its arithmetic is fixed by the model geometry. Each token in a sequence stores one key and one value vector per layer. For a 32-layer model with 4,096-wide multi-head attention in 16-bit precision, one token costs 2 x 32 x 4,096 x 2 bytes, which is 512 KiB. A 4,096-token context then needs 2 GiB. Grouped-query attention reduces the per-token cost in proportion to the ratio of query heads to key-value heads: eight key-value heads of width 128 give 1,024 values per layer, or 128 KiB per token, so the same context needs 512 MiB. That is why serving configurations usually trade attention quality for cache density, and why context length, not batch size, is often the binding constraint.

What the loop costs elsewhere

Nothing is free, and three costs move into new places.

Scheduling becomes latency-critical. The loop runs once per forward pass, and the forward pass itself is short: a 7-billion-parameter model in 16-bit precision occupies 14 GB, and reading those weights at roughly 3 TB/s of memory bandwidth sets a floor near 5 ms per decode step. The host-side work of choosing the batch must fit comfortably inside that window, or the accelerator waits on the scheduler. This is why production schedulers avoid global locks and avoid allocating memory on the critical path.

Kernel shapes stop being stable. A stack that captures the forward pass into a graph must capture one graph per distinct batch shape, or pad to a set of buckets. Bucketing reintroduces a small amount of the padding waste the loop was meant to remove, and the trade is deliberate: a handful of padded shapes is cheaper than a graph launch per iteration.

Latency per token becomes a function of concurrency. Every added sequence increases the work in each pass, so inter-token latency rises with batch size while cost per token falls. The two curves cross at a point that depends on the model and the hardware, and a workload with a per-token deadline cannot simply be batched as deeply as throughput alone would suggest. Deadline-aware admission is treated in Deadline-Aware Batching and Tenant Fairness.

Where it breaks

Long prompts are the recurring failure. A single 30,000-token prompt consumes an entire iteration’s position budget, so every other sequence waits one step and the inter-token latency of running sequences jumps. The effect is visible to clients as a periodic stall correlated with arrivals rather than with load, and it is the reason prefill work is often scheduled separately from decode work.

Cache exhaustion is the second. When admissions outpace completions, the loop has to either stop admitting or take memory back from a running sequence, and taking it back means discarding progress through swapping or recomputation. The policy choice between those options determines whether the system degrades in latency or in throughput.

The third is starvation. A first-come-first-served waiting queue gives a long prompt the same claim on the budget as a short one, so a stream of long prompts can delay everything behind it. Ordering the queue by remaining work, by tenant share, or by deadline changes the fairness properties without changing the mechanism.

Iteration-level batching is a throughput mechanism. It raises the number of tokens produced per unit of hardware time by keeping every slot full of unfinished work. It says nothing about which request should occupy a slot when the queue is deep, and it says nothing about where the slot should be. Those are separate decisions, made by routing and by admission control.