Batching and scheduling: continuous batching, chunked prefill, fair multi-tenancy

A GPU serving a language model is only cheap when it works on many requests at once. The scheduler decides which requests share each step. Get it wrong and you either waste the GPU or make users wait. This page works through three interview problems about that scheduler, with real numbers and the trade-offs.

Source: Vishal Singh's 25 inference-engineering interview problems · saved in sources/09-vishal-inference-25.md

Going deeper: everything below is the full version, with some maths. On a first read, skim the headings, the interview cards and the "Why it matters for robotics" box, and come back for the rest later.

0. One cost model for the whole page

All three problems use the same picture of one engine step. A step runs one forward pass over every token scheduled in it: prompt tokens being prefilled, plus one token per decoding request.

t_step ≈ t_0 + c_p × (prefill tokens in step) + c_d × (decoding requests in step)

t_0  : fixed cost per step, mostly reading all weights from HBM once
c_p  : cost per prompt token (compute-bound matrix multiplies)
c_d  : cost per decoding request (its KV-cache reads; grows with its context)

TPOT (time per output token) for every decoding request = t_step
throughput (output tokens/s)                            = decoding requests / t_step

Working assumptions used throughout, for a Llama-style 70B model served on one 8-GPU tensor-parallel node. These are round numbers for practice, not measurements: t_0 = 20 ms, c_p = 0.1 ms per prompt token (10,000 prompt tokens/s), c_d = 0.2 ms per decoding request at a few thousand tokens of context. In an interview, say your numbers are assumptions and show how the answer changes if they move. The demo uses exactly these values.

Problem 6 · Continuous batching under latency deadlines, and why it beats static batching

What the interviewer is testing: that you know decode is memory-bound so batching is nearly free, that requests finish at very different times, and that you can turn latency targets into a concrete admission rule.

The concepts

Static (request-level) batching groups B requests, runs them together until the longest finishes, then takes the next group. Two kinds of waste follow. Finished requests keep their slot (often still computing padding) until the longest one ends. And new arrivals wait for the whole group, however long it takes.

static slot utilisation = Σ out_i / (B × max_i out_i)

Continuous (iteration-level) batching re-forms the batch after every step. Orca (Yu et al., OSDI 2022) introduced this as iteration-level scheduling, together with selective batching: the big matrix multiplies run over all tokens of all requests flattened together, while attention runs per request, so requests of different lengths can share a step without padding. vLLM, SGLang and TensorRT-LLM (where it's called in-flight batching) all work this way. PagedAttention (Page 02) makes it practical, because KV memory is allocated in blocks as requests grow and freed the moment they finish.

Why batching is nearly free during decode. At small batch each step is dominated by t_0, the weight read. Adding a request adds only c_d. So throughput rises almost linearly with batch size while TPOT rises slowly, until either the KV cache is full or the step becomes compute-bound.

TPOT(B)       = t_0 + c_d × B
throughput(B) = B / (t_0 + c_d × B)    → approaches 1/c_d as B grows

Worked answer with numbers

Static vs continuous on one batch. Batch of 8: seven requests want 50 output tokens, one wants 1,000.

static utilisation = (7 × 50 + 1000) / (8 × 1000) = 1350 / 8000 = 16.9 %
static step        = 20 + 8 × 0.2 = 21.6 ms
static batch time  = 1000 steps × 21.6 ms = 21.6 s
  → the seven short requests finish after ~1.1 s, but their slots sit idle
    for 20.5 s and nothing new can start for 21.6 s.
continuous         : each freed slot is refilled on the next step,
                     so utilisation stays near 100 % while the queue is non-empty.

The demo shows the system-level effect with Poisson arrivals (2 requests/s, 32 slots, output lengths log-normal with median 150 tokens, capped at 1,000): static batching sustains about 117–182 output tokens/s and the queue keeps growing; continuous batching sustains about 380 tokens/s (it keeps up with all the traffic) with a mean TTFT of about 0.2 s.

Adding latency deadlines. Say the SLO is TTFT ≤ 1 s and TPOT ≤ 50 ms (20 tokens/s, faster than people read). Two limits cap the batch:

1. TPOT limit:  t_0 + c_d × B ≤ 50 ms  →  B ≤ (50 − 20) / 0.2 = 150 requests

2. KV limit (assume 200 GB of HBM left for KV after weights and activations;
   Llama-70B shape: 80 layers, 8 KV heads, head dim 128, fp16):
   KV per token = 2 × 80 × 8 × 128 × 2 B = 327,680 B (320 KiB)
   tokens that fit = 200e9 / 327,680 ≈ 610,000
   at 4,096 tokens average context  →  610,000 / 4,096 ≈ 149 requests

throughput at B = 150 ≈ 150 / 0.050 = 3,000 output tokens/s
throughput at B = 32  ≈ 32 / 0.0264 ≈ 1,212 output tokens/s

Here both limits land near 150, which is a useful thing to notice out loud: buying more KV memory (FP8 cache, fewer KV heads) only helps if TPOT also has room. The scheduler then does this every step:

1. Keep running requests running (one decode token each). They already paid for their KV.
2. Admit waiting requests in order of deadline (earliest TTFT deadline first) while the predicted step time stays ≤ the TPOT target and KV blocks remain.
3. Bound prefill per step with a token budget so admissions don't blow the TPOT of everyone else (this is Problem 7).
4. If KV runs out mid-flight, preempt the lowest-priority or newest request: free its blocks and later recompute its prefill, or swap blocks to CPU memory. vLLM does recompute-based preemption by default.
5. If a request will miss its deadline anyway (waited longer than its TTFT SLO), consider rejecting it early rather than serving it late and slowing others.

Trade-offs

Common mistakes

• Saying continuous batching lowers per-token latency. It mainly raises throughput and cuts queueing; each step can get slightly slower as the batch grows.
• Forgetting the KV-cache limit, so the batch looks unbounded.
• Treating "batch size" as a fixed config. In a continuous batcher it's the live number of running requests, set by the token budget, max sequences and free KV blocks.
• Ignoring preemption: without it, an overfull cache either crashes or stalls.

Problem 7 · A 100K-token prompt stalls short chats: fix TTFT with chunked prefill and scheduling

What the interviewer is testing: that you can see prefill/decode interference, size a chunk from a latency target, and know the other levers (ordering, isolation, caching) when chunking alone isn't enough.

The concepts

Why one prompt stalls everyone. Without chunking, an engine prefills a whole prompt in one step. Every other request in the batch waits for that step to finish before getting its next token, and requests in the queue wait for their own first token. Prefill cost is roughly linear in prompt length for the matrix multiplies, plus a quadratic term for attention:

prefill FLOPs ≈ 2 × N × T  +  2 × L × d_model × T²      (causal attention)
N = parameters, T = prompt tokens, L = layers

Chunked prefill splits a long prompt into pieces and processes one piece per step, mixed with the decode tokens of other requests. Sarathi (Agrawal et al., 2023) proposed chunked prefills with "decode-maximal batching": fill each step with all ongoing decodes, then top it up with a prefill chunk. Sarathi-Serve (Agrawal et al., OSDI 2024) adds stall-free scheduling under a per-step token budget chosen from the TPOT target. vLLM exposes this as --enable-chunked-prefill with the budget set by --max-num-batched-tokens; recent versions turn chunked prefill on by default, so check the docs for your version.

choose budget C so that   t_0 + c_p × C + c_d × B_decode ≤ TPOT target
→ C ≤ (TPOT target − t_0 − c_d × B_decode) / c_p

Worked answer with numbers

Assumptions: the 70B model from section 0; a 100,000-token prompt; 32 chats decoding.

Size of the job
  linear part   : 2 × 70e9 × 1e5            = 1.4e16 FLOPs
  attention part: 2 × 80 × 8192 × (1e5)²    = 1.31e16 FLOPs
  → at 100K tokens attention roughly doubles the work.
  At the assumed 10,000 prompt tokens/s (linear part only): 10 s;
  with the attention term, closer to 19 s.

No chunking
  one step ≈ 10 s  → every running chat's next token is 10 s late,
  every queued chat's TTFT includes up to 10 s of waiting.

Chunking (step = 20 ms + C × 0.1 ms + 32 × 0.2 ms, linear model)
  C      step     chunks   long prompt prefill   decode gap for others
  512    77.6 ms  196      ≈ 15.2 s              ≈ 78 ms
  2,048  231 ms   49       ≈ 11.3 s              ≈ 231 ms
  8,192  846 ms   13       ≈ 11.0 s              ≈ 846 ms

Budget from a 100 ms TPOT target:
  C ≤ (100 − 20 − 6.4) / 0.1 = 736 tokens  → pick 512

The pattern to say out loud: small chunks protect everyone else's latency, but every chunk pays the fixed t_0 again, so the long prompt itself finishes later. Later chunks also cost more than early ones, because each chunk attends to all the prompt tokens before it.

Chunking is half the fix. Scheduling is the other half.

• Order prefill by remaining length. Inside the per-step budget, give short new prompts their tokens before the long one's next chunk (shortest-remaining-prefill first). That's what the demo does in chunked mode, and it's why short-chat TTFT drops to about 0.25 s. Add aging so the long prompt can't starve.
• Cap how much of the budget long prefills may take, for example at most one long prompt in prefill at a time, so two 100K prompts can't fill every step.
• Separate the traffic. Route prompts above a threshold to a long-context pool, or disaggregate prefill from decode entirely (Page 04, Problem 22).
• Don't prefill it twice. Long prompts are often the same document asked about repeatedly. Prefix caching turns the second request into a cache hit (Page 04, Problem 8).
• Admission and pricing. Long prompts cost far more; per-tenant token limits (Problem 21) stop one user from sending many at once.

Trade-offs

Common mistakes

• Thinking chunking makes the long prompt faster. It makes it slower; it makes everyone else faster.
• Forgetting the quadratic attention term, so the 100K estimate is off by about 2×.
• Chunking but keeping FCFS order inside the budget, so short prompts still queue behind the long one's chunks.
• Choosing the chunk size by feel instead of from the TPOT target.

Problem 21 · Multi-tenant serving with fair scheduling, admission control and priority queues

What the interviewer is testing: that you measure fairness in tokens, not requests; that you reject early instead of serving late; and that priorities come with starvation protection and preemption.

The concepts

The cost unit is tokens. One request can be 50 tokens or 100,000. Counting requests lets a tenant with long prompts take most of the GPU while looking "fair". Prompt and output tokens also cost different amounts (prefill is cheap per token, decode is expensive per token), so weight them.

cost(request) = w_in × prompt tokens + w_out × output tokens     (w_out > w_in)

Weighted fair queuing. Each tenant i has a weight w_i (its share). Classic weighted fair queuing gives each request a virtual finish tag and serves the smallest tag first:

F_new = max(V_now, F_prev_of_tenant) + cost / w_i

LLM serving has a twist: the output length is unknown when a request starts. The Virtual Token Counter (VTC; Sheng et al., OSDI 2024) handles this by keeping a counter per tenant, adding weighted tokens as they're actually processed, and always scheduling from the backlogged tenant with the smallest counter. When a tenant becomes active again, its counter is raised to the smallest counter among active tenants, so idle time can't be banked into a later burst.

Weighted max-min fairness describes the target allocation: nobody gets more than they ask for, and spare capacity is shared by weight among those who want more.

Admission control sits before the queue: per-tenant token buckets (a rate and a burst size in tokens per minute) and a global check of predicted wait. Priority classes (interactive, standard, batch) sit on top of fair sharing: strict priority between classes with aging, fair sharing between tenants inside a class.

Worked answer with numbers

Assume the pool serves 20,000 weighted tokens/s. Three tenants: A (free tier, weight 1, wants 15,000 tokens/s), B (paid, weight 3, wants 4,000), C (internal, weight 1, wants 10,000). Demand is 29,000, so someone gets less.

Round 1: shares by weight (1 : 3 : 1) of 20,000
  A 4,000   B 12,000   C 4,000
  B only wants 4,000 → give B 4,000, return 8,000 to the pool.

Round 2: split remaining 16,000 between A and C (1 : 1)
  A 8,000   C 8,000      both still want more → stop.

Final: A 8,000 (53% of its demand), B 4,000 (100%), C 8,000 (80%).

Admission check with Little's law. If the queue already holds requests expected to need 60,000 weighted tokens, the expected wait for a new arrival is about 60,000 / 20,000 = 3 s. With a 2 s TTFT SLO for interactive traffic, admitting more interactive work just creates late answers. Shed load instead: reject batch-class work with HTTP 429 and a Retry-After header, or cap max_tokens for the free tier, until predicted wait drops below the SLO.

expected wait ≈ queued work / service rate      (Little's law: L = λ × W)
admit if   expected wait + own prefill time ≤ TTFT SLO   (per class)

The design, front to back:

1. Gateway: authenticate, find tenant and class, apply the tenant's token bucket. Over limit → 429 immediately.
2. Admission: estimate wait per class from queued work and recent throughput. Reject or degrade when it exceeds the SLO; reject lowest class first.
3. Queues: one queue per (class, tenant). Pick the class by strict priority with aging (a batch request waiting over, say, 10 minutes is promoted). Inside the class, pick the tenant by VTC.
4. Engine: the continuous batcher from Problem 6 pulls from this picker. When KV runs out, preempt the lowest class first.
5. Isolation for big customers: dedicated replicas or reserved capacity for tenants with contracts; shared pool for the rest. Per-tenant LoRA adapters can share one base model.
6. Observe: per-tenant tokens served, rejected, TTFT and TPOT percentiles, preemptions. Fairness bugs show up only in per-tenant views.

Trade-offs

Common mistakes

• Rate limiting by requests per minute only.
• Queuing without limit, so overload turns into timeouts for everyone instead of fast rejections for some.
• Strict priority with no aging or minimum share, so batch traffic never runs.
• Doing fairness only at the gateway, while the engine's batcher serves in arrival order.

Practise it

1. Run the simulator yourself. Copy this page's script into a Python or Node file, add a second "tenant" field to requests, and implement VTC in the admission step. Measure per-tenant tokens/s when one tenant sends 10× the traffic.
2. vLLM on a free Colab GPU. Serve a small instruct model (0.5–1.5B parameters) with vLLM's OpenAI-compatible server. Write an async Python client that sends 50 short chats (200-token prompts) at a steady rate and, at t = 10 s, one prompt as long as the model's context allows.
3. Measure TTFT and inter-token latency of the short chats with streaming. Run three settings: chunked prefill off (if your version allows), on with --max-num-batched-tokens 512, and on with 4096. Plot short-chat p50/p95 TTFT and the worst inter-token gap, plus the long prompt's TTFT.
4. Vary --max-num-seqs (the batch cap) from 8 to 256 at a high request rate and plot throughput against median TPOT. Find the knee.
5. Write down your assumed t_0, c_p and c_d by fitting a line to step times from the server logs or your measurements, and check whether the section 0 model predicts your results.

In this course

• Page 02 · KV cache, PagedAttention and FlashAttention: why paged KV memory makes continuous batching possible.
• Page 04 · Prefix caching and disaggregation: the next fixes for long prompts.
• Module 05 · Serving: two caches in one paged pool and fleet scheduling for a trillion-parameter model.
• Module 08 · Inference-aware design: KV-cache maths and GQA, which set c_d and the KV limit.
• Module 04 · Latency is a safety number: measuring wait-after-speech on the device.
• Module 01 · Decision-model evals: thresholds and metrics, the same discipline as SLOs.

Why it matters for robotics

Self-check

Resources

• Orca: A Distributed Serving System for Transformer-Based Generative Models (Yu et al., OSDI 2022): iteration-level scheduling and selective batching
• SARATHI: Efficient LLM Inference by Piggybacking Decodes with Chunked Prefills (Agrawal et al., 2023)
• Taming Throughput-Latency Tradeoff in LLM Inference with Sarathi-Serve (Agrawal et al., OSDI 2024)
• Fairness in Serving Large Language Models (Sheng et al., OSDI 2024): the Virtual Token Counter
• Efficient Memory Management for LLM Serving with PagedAttention (Kwon et al., 2023)
• Docs: vLLM · Optimization and tuning (chunked prefill, batch token budget, preemption)
• Docs: SGLang documentation
• Docs: TensorRT-LLM documentation (in-flight batching, chunked context)