Continuous Batching & Iteration-Level Scheduling

Iteration-level scheduling ends the wait for a batch's longest request; prefill stalls become the next bottleneck.

Part 1 of 5

Basics

The whole idea first, then the terms the rest of this page uses.

1.1Whole idea

A static batch finishes when its longest request finishes, so short requests sit idle. Continuous batching schedules at every token step: finished requests leave, and waiting ones join.

Why it matters

Iteration-level scheduling ends the wait for a batch's longest request; prefill stalls become the next bottleneck.

1.2Key concepts

One idea per card, in plain words.

01Iteration-level scheduling

Makes scheduling decisions between forward passes, not between whole requests.

02Prefill

Processes the whole prompt in one pass. It costs far more than one decode step.

03Decode

Generates one token per request per step.

04TTFT and TPOT

Time to first token measures queueing plus prefill. Time per output token measures decode step time.

05Selective batching

Orca's technique: batch the same operation across requests even when they sit at different positions.

Part 2 of 5

Question

What exactly you must answer, and what to settle before you start.

2.1Question

Interviewer

Short chat replies wait behind 2,000-token report jobs on the same GPUs. Product wants p95 time to first token under 500 ms with no new hardware. What do you change?

2.2Clarify first

Each answer removes a guess.

You askAnswer
Does the report job need low latency?No. It can wait, but it must finish.
Do clients stream?Yes, so time to first token shapes perceived speed.
Part 3 of 5

Detailed answer

How it works, and how to build or explain it.

3.1Step by step

The mechanism, in the order you would explain it.

  1. Find the waste

    Under static batching the batch holds its slots until the longest request ends. GPU slots idle, and new arrivals queue.

  2. Admit between steps

    Check the queue after every token. A slot freed at step 10 serves a new request at step 11.

  3. Watch the prefill cost

    A new request's prefill shares a step with running decodes, and everyone waits for it. Long prompts now stall short replies.

  4. Chunk the prefill

    Give each step a token budget. Long prompts prefill across several steps, so decodes keep moving.

  5. Separate the classes

    Put reports in a lower-priority queue with their own concurrency limit. Reject or defer when the waiting queue grows.

3.2Same jobs, two schedulers

Jobs need 100, 10, 10 and 10 tokens, all arrive at step 0, and the batch holds 2.

SchedulerFinish stepsMean latency
Static100, 100, 110, 110105 steps
Continuous100, 10, 20, 3040 steps

3.3Code

Working code for the core of it.

Static versus continuous batching

One long request shouldn't hold up everyone else. Run both functions on the same jobs, and the difference is plain.

continuous-batching.tsTypeScriptCopy
1export interface Job {2  arrival: number;3  tokens: number;4}5 6const byArrival = (jobs: Job[]) => jobs.map((_, i) => i).sort((a, b) => jobs[a].arrival - jobs[b].arrival);7 8/** Static batching: the whole batch waits for its longest request. Returns each job's finish step. */9export function staticBatching(jobs: Job[], size: number): number[] {10  const done = new Array<number>(jobs.length);11  const queue = byArrival(jobs);12  let t = 0;13  let next = 0;14  while (next < queue.length) {15    t = Math.max(t, jobs[queue[next]].arrival);16    const batch: number[] = [];17    while (batch.length < size && next < queue.length && jobs[queue[next]].arrival <= t) batch.push(queue[next++]);18    t += Math.max(...batch.map((i) => jobs[i].tokens));19    for (const i of batch) done[i] = t;20  }21  return done;22}23 24/** Continuous batching: finished jobs leave after any step, and waiting jobs join at once. */25export function continuousBatching(jobs: Job[], size: number): number[] {26  const done = new Array<number>(jobs.length);27  const queue = byArrival(jobs);28  const left = jobs.map((j) => j.tokens);29  const running = new Set<number>();30  let t = 0;31  let next = 0;32  while (running.size > 0 || next < queue.length) {33    while (running.size < size && next < queue.length && jobs[queue[next]].arrival <= t) running.add(queue[next++]);34    if (running.size === 0) {35      t = jobs[queue[next]].arrival;36      continue;37    }38    t++; // one step: one token for everyone in the batch39    for (const i of [...running]) {40      if (--left[i] === 0) {41        done[i] = t;42        running.delete(i);43      }44    }45  }46  return done;47}
47 linesUTF-8TypeScript
t += Math.max(...)
Static batching: everyone waits for the longest request in the batch.
running.delete(i)
Continuous batching: a finished request leaves after any step.
running.add(queue[next++])
A waiting request joins at the very next step, which is where the throughput gain comes from.

Tested by npm run test:modules.

Part 4 of 5

Q&A

What interviewers ask next. Answer out loud, then open.

4.1Interview questions

Does continuous batching raise tokens per second?
Yes, under load, because slots never idle. The Orca paper reported large throughput gains at the same latency.
Why can latency get worse for running requests?
Each admitted prompt lengthens that step for everyone. Chunked prefill or a per-step token budget contains it.
How do you pick the maximum batch size?
KV cache memory sets the ceiling. Step time sets the practical limit: a bigger batch raises throughput and slows each token, so tune against your TPOT target.
Part 5 of 5

Extra depth

Edge cases, counterpoints and what to read next.

5.1Edge cases and counterpoints

Includes the strongest argument against this approach.

Show detailsHide details
Fairness
Long requests hold slots for many steps. Set per-tenant limits and cap max_tokens per request.
Disaggregated serving
Some teams run prefill and decode on separate GPUs and move the KV cache between them. It helps at scale and adds real complexity.
Counterpoint
Offline jobs of uniform length lose little under static batching. Skip the scheduler work for nightly batches.