Continuous batching

Deep dive

How it works

In: waiting requests, running sequences, free KV blocks, a per-step token budget · Out: one ragged batch of tokens per forward pass · State: running and waiting queues plus each sequence's KV blocks · Cost: O(running sequences) scheduler work per step.

Each engine iteration:

1. Reserve decode slots. Every running sequence in its decode phase needs one KV slot. If the KV pool is short, preempt the newest sequences: free their blocks and requeue them at the front for recompute, or swap them to CPU.
2. Fill the token budget. One token per decoding sequence, then continue partially prefilled prompts, then admit waiting requests (FCFS) while running < max_num_seqs, the budget lasts, and their prompt fits in free KV.
3. Run one forward pass over a flattened, ragged batch of tokens. Linear layers see one [total_tokens, h] matrix with no padding (Orca's "selective batching"). Attention uses per-sequence lengths and block tables.
4. Sample, append, retire. Stop on EOS or max tokens, free KV, and stream tokens to clients.

step:  1      2      3      4      5
A      P P P  d      d      d(EOS)
B             P P    d      d      d
C                    P      d      d      ← joined while A and B were mid-flight
       one forward pass per column: prefill chunks (P) + decodes (d) packed together

Step-time model for a dense model of N params on one GPU: t ≈ max(weight_bytes / HBM_BW, 2·N·tokens / FLOPs) plus attention over the KV read. Decode tokens are nearly free until the batch reaches about peak FLOPs / HBM bandwidth ≈ 300 tokens for fp16 weights on H100 (100-200 at realistic achieved FLOPs). Beyond that, the step is compute-bound.

Code

A scheduler with a token budget, KV admission, recompute-preemption and chunked prefill, compared with static batching under the step-time model above (7B fp16 on an H100-class GPU).

use std::collections::VecDeque;

#[derive(Clone)]
struct Req { prompt: usize, out: usize, prefilled: usize, generated: usize }
impl Req {
    fn kv(&self) -> usize { self.prefilled + self.generated }
    fn decoding(&self) -> bool { self.prefilled == self.prompt }
}

struct Scheduler { waiting: VecDeque<Req>, running: Vec<Req>, kv_free: usize, max_seqs: usize, budget: usize }

impl Scheduler {
    /// One engine iteration; returns the number of tokens in this forward pass.
    fn step(&mut self) -> usize {
        loop {                                            // 1. KV for one decode token each
            let need = self.running.iter().filter(|r| r.decoding()).count();
            if self.kv_free >= need { break; }
            let mut r = self.running.pop().expect("a single sequence must fit");
            self.kv_free += r.kv();                       // preempt newest: free KV, recompute later
            r.prompt += r.generated; r.out -= r.generated; r.generated = 0; r.prefilled = 0;
            self.waiting.push_front(r);
        }
        let mut tokens = 0;
        for r in self.running.iter_mut().filter(|r| r.decoding()) { r.generated += 1; tokens += 1; }
        self.kv_free -= tokens;
        for r in self.running.iter_mut().filter(|r| !r.decoding()) {   // 2. continue chunked prefills
            let c = (r.prompt - r.prefilled).min(self.budget.saturating_sub(tokens)).min(self.kv_free);
            r.prefilled += c; tokens += c; self.kv_free -= c;
        }
        while self.running.len() < self.max_seqs && tokens < self.budget {  // 3. admit new requests
            match self.waiting.front() { Some(r) if r.prompt + 1 <= self.kv_free => {}, _ => break }
            let mut r = self.waiting.pop_front().unwrap();
            let c = r.prompt.min(self.budget - tokens);
            r.prefilled = c; tokens += c; self.kv_free -= c;
            self.running.push(r);
        }
        let kv_free = &mut self.kv_free;                  // 4. retire finished sequences
        self.running.retain(|r| { let done = r.generated >= r.out; if done { *kv_free += r.kv(); } !done });
        tokens
    }
}

fn step_ms(tokens: usize) -> f64 { 4.2 + 0.023 * tokens as f64 } // 14 GB at 3.35 TB/s + 14 GFLOP/token at 600 TFLOPS

fn main() {
    let mut s = 42u64;
    let mut rnd = |lo: usize, hi: usize| { s = s.wrapping_mul(6364136223846793005).wrapping_add(1442695040888963407);
                                           lo + (s >> 33) as usize % (hi - lo) };
    let reqs: Vec<Req> = (0..2000).map(|_| Req { prompt: rnd(50, 1000), out: rnd(10, 1000), prefilled: 0, generated: 0 }).collect();
    let total_out: usize = reqs.iter().map(|r| r.out).sum();
    let kv_tokens = 450_000;                              // about 60 GB of KV at 128 KB/token

    let mut sch = Scheduler { waiting: reqs.iter().cloned().collect(), running: vec![], kv_free: kv_tokens, max_seqs: 256, budget: 2048 };
    let mut t_cont = 0.0;
    while !(sch.waiting.is_empty() && sch.running.is_empty()) { t_cont += step_ms(sch.step()); }

    let b = kv_tokens / 2000;                             // static: reserve max prompt+output per slot
    let t_static: f64 = reqs.chunks(b).map(|batch| {
        let prefill = step_ms(batch.iter().map(|r| r.prompt).sum());
        prefill + batch.iter().map(|r| r.out).max().unwrap() as f64 * step_ms(batch.len())  // padding included
    }).sum();
    println!("continuous: {:.0} tok/s   static (batch {b}): {:.0} tok/s",
             total_out as f64 / t_cont * 1e3, total_out as f64 / t_static * 1e3);
}

Complexity and constants

• Example (7B fp16, H100): batch 1 decode is about 4-5 ms per step, about 200 tok/s. Batch 128 is about 7 ms per step, about 18k tok/s. Same GPU, about 75x the throughput.
• The simulator above prints about 15k vs 9k tok/s (1.6x), even though static batching gets a generous 225 slots here. The gap widens with heavier-tailed output lengths, smaller KV pools (bigger models), and arrivals over time, since static batches also make new requests wait for the whole batch.
• Latency costs: time-to-first-token (TTFT) grows with queueing and prefill; time-per-output-token (TPOT) grows with batch size and with prefill tokens sharing the step. The token budget sets the trade-off: small budgets protect TPOT, large budgets raise throughput and lower TTFT.

Efficiency

• Cost: a decode step reads all weights once: 14 GB at 3.35 TB/s is about 4.2 ms for a 7B fp16 model on an H100, so batch 1 gives about 200 tok/s and batch 128 about 7 ms per step (this page's model). Bound: memory bandwidth until the batch reaches about 300 tokens, then compute. KV cache costs about 128 KB per token for 7B (page example).
• Levers:
  • iteration-level scheduling — up to 36.9x throughput over FasterTransformer at equal latency (Orca) — variable output lengths
  • paged KV cache — 2-4x throughput over Orca and FasterTransformer at equal latency (PagedAttention paper) — KV memory limits the batch
  • chunked prefill with a token budget — 2.6x serving capacity for Mistral-7B on one A100 under latency SLOs (Sarathi-Serve) — mixed long prompts and decodes
  • prefill/decode disaggregation — up to 7.4x more requests or 12.6x tighter SLO (DistServe); 1.4x throughput at 20% lower cost (Splitwise) — conflicting TTFT and TPOT targets
  • CUDA graphs for decode steps — order of 10-30% less launch overhead at small batch — small batches
• Naive → standard → state of the art:
  • one request at a time · about 200 tok/s (7B, H100, model above)
  • static batching · waits for the longest output, padding wasted; about 9k tok/s in the simulator above
  • continuous batching with paged KV and chunked prefill · about 15k tok/s in the same simulator, then disaggregated pools at scale

Implementation notes

• Flatten the batch to [num_tokens, h] with no padding. Attention kernels take cumulative sequence lengths (varlen) and block tables.
• CUDA graphs: capture decode-only steps for a set of padded batch sizes (1, 2, 4, 8, ..., 256) and pick the next size up. This removes about 10-30% launch overhead at small batch.
• Run the scheduler on the CPU and overlap it with the GPU step (async scheduling), or Python scheduling costs several ms per step at high request rates.
• Prioritize decodes over prefills within a step (Sarathi-Serve "stall-free"), and cap prefill chunks so decode TPOT stays flat.
• Disaggregate prefill and decode onto separate GPU pools when TTFT and TPOT SLOs conflict (DistServe, Splitwise, Mooncake). The KV is transferred between them.

Pitfalls

• Admitting without a KV margin causes constant preemption: thrashing, with throughput collapsing as recomputation eats the GPU.
• FCFS head-of-line blocking: a huge prompt at the queue head can block small ones. Use chunked prefill, or admit by fit.
• Sampling parameters per sequence (temperature, top-p, logit bias, grammar constraints) must be batched too, or the sampler becomes the bottleneck.
• Stop-string detection and detokenization in Python per token per sequence can cap throughput at high batch sizes. Run them incrementally and off the critical path.
• Benchmarks with a fixed output length hide the main benefit. Use realistic output-length distributions (ShareGPT-like).

Variants and alternatives

In production

vLLM, SGLang, TensorRT-LLM ("in-flight batching"), Hugging Face TGI, LMDeploy, DeepSpeed-FastGen (Dynamic SplitFuse), llama.cpp server (--cont-batching).

Implementations

Sources

• Yu et al., Orca: A Distributed Serving System for Transformer-Based Generative Models, OSDI 2022. paper
• Kwon et al., Efficient Memory Management for Large Language Model Serving with PagedAttention, SOSP 2023. paper · code
• Agrawal et al., Taming Throughput-Latency Tradeoff in LLM Inference with Sarathi-Serve, OSDI 2024. paper · code
• Zhong et al., DistServe: Disaggregating Prefill and Decoding for Goodput-optimized Large Language Model Serving, OSDI 2024. paper · code
• Patel et al., Splitwise: Efficient Generative LLM Inference Using Phase Splitting, ISCA 2024. paper