02 — Orca & Continuous Batching

Paper: Yu, Jeong, Kim, Kim, Chun — “Orca: A Distributed Serving System for Transformer-Based Generative Models” (OSDI ‘22). Link: https://www.usenix.org/conference/osdi22/presentation/yu

This is the single most important paper for the mechanism of modern LLM serving. Every engine you touch — vLLM, SGLang, TensorRT-LLM, TGI — is an Orca descendant.

The problem Orca is solving

Before Orca: static batching. You collect N requests, pack them into a batch, run the model until the longest sequence in the batch finishes, then return all N responses. This is how you’d naturally batch inference if you’d only ever done image classification.

For generative decoding this is catastrophically wasteful. Watch what happens with a batch of 4 requests generating 100/500/50/300 tokens:

request 1  ████░░░░░░░░░░░░░░░░░░  (100 tokens; then GPU sits idle for it for 400 steps)
request 2  █████████████████████░  (500 tokens; this one sets the clock)
request 3  ██░░░░░░░░░░░░░░░░░░░░  (50 tokens; idle for 450 steps)
request 4  ██████████████░░░░░░░░  (300 tokens; idle for 200 steps)

Every cell after a request finishes is wasted GPU work. New requests that could be scheduled must wait for the entire batch to drain before the next batch begins. On any real workload with variable output lengths (all of them), you’re using maybe 30-40% of the GPU.

The two ideas Orca introduces

Idea 1: Iteration-level scheduling (aka continuous batching)

Instead of scheduling at the granularity of “one whole batched generation”, schedule at the granularity of one decode step. Every iteration:

  1. Look at the currently running batch.

  2. Any sequences that emitted EOS or hit max-tokens → leave (their KV is freed, response is streamed out).

  3. Any waiting requests in the queue that fit under the KV / batch budget → join.

  4. Run one forward pass on the new batch composition.

  5. Repeat.

Requests join and leave the batch dynamically. No sequence waits for another’s completion. GPU utilization jumps to 70-90%+ on realistic traffic. This is the single largest algorithmic win in LLM serving history — Orca reports ~10-20× throughput improvement over static batching in comparable settings.

Idea 2: Selective batching

Here’s the subtlety that makes Orca implementable. To batch two sequences at different generation positions you’d need them to have matching KV cache lengths for the attention operation — which they don’t. Solution: selectively batch the ops that can be batched.

  • Attention: not batched. Each sequence’s attention runs independently because its KV cache length is unique. This is fine because attention is memory-bound and per-sequence anyway.

  • All other ops (LayerNorm/RMSNorm, QKV projection, MLP, output projection): batched across sequences into one big matmul. These are the compute-bound ops where batching actually pays.

Modern implementations (FlashAttention paged variants, FlashInfer) have largely absorbed this insight into the attention kernel itself — the kernel handles ragged/variable-length inputs internally, so from the engine’s POV attention is batched, but at the kernel level it’s doing per-sequence work correctly.

Worked example: 3 requests, iteration-level scheduling

Assume batch size 3, all decode (post-prefill), and one sequence finishes after step 4.

t=0: batch = [R1(pos=10), R2(pos=25), R3(pos=8)]      # scheduled
t=1: batch = [R1(pos=11), R2(pos=26), R3(pos=9)]      # forward pass #1
t=2: batch = [R1(pos=12), R2(pos=27), R3(pos=10)]     # forward pass #2
t=3: batch = [R1(pos=13), R2(pos=28), R3(pos=11)]     # R3 emits EOS at 11
t=4: R3 leaves. R4 in queue joins (starts prefill). 
     batch = [R1(pos=14), R2(pos=29), R4(prefill=64)] # HYBRID: 2 decode + 1 prefill
t=5: R4 prefill done, starts decoding at pos 64.
     batch = [R1(pos=15), R2(pos=30), R4(pos=65)]     # forward pass #4
...

Notice at t=4 the batch contains a mix of decode positions AND a fresh prefill. This is the prefill/decode interference problem — R4’s prefill is a big compute-heavy op that will slow down R1 and R2’s cheap decode step. The chunked-prefill solution (file 04) directly addresses this.

The Orca architecture

Because the paper predates most modern engines, its terminology differs. The pieces:

  • Request pool — in-flight sequences and their KV state

  • Scheduler — chooses which requests are in each iteration’s batch

  • Execution engine — runs the transformer forward pass, sends results back

  • gRPC control plane for cross-node coordination; NCCL data plane for tensor-parallel comms

Orca supports tensor and pipeline parallelism natively — the paper is notable for treating distributed inference as first-class from the start.

Detail worth remembering: Orca uses a first-come-first-served scheduler with an admission-control step (don’t admit if KV budget would overflow). Simple, obviously fair, easy to reason about. vLLM V1 kept essentially the same skeleton.

What Orca did NOT solve (and later engines did)

  1. KV cache fragmentation. Orca allocates KV cache contiguously per sequence, reserving worst-case capacity. Waste is huge. → PagedAttention.

  2. Prefill/decode interference. A long prefill in the batch spikes ITL for all decoding requests. → Chunked prefill (Sarathi-Serve).

  3. Prefix sharing. Two requests with identical system prompts each recompute + store their own KV for that prompt. → RadixAttention.

  4. Decode waste of compute. Decode is memory-bound and leaves tensor cores idle. → Speculative decoding.

Every paper in this phase is a fix for something Orca left on the table. Hold the map: Orca is the trunk; everything else is a branch.

The intuition to internalize

Scheduling granularity = iteration. Not “batch”, not “request”. One forward step. Everything in the modern serving stack — continuous batching, chunked prefill, spec decoding, preemption/eviction — makes decisions at that same rhythm.

When you read vllm/v1/engine/core.py’s run_busy_loop and see it calling scheduler.schedule() → executor.execute_model() in a tight loop, you’re looking at Orca made real, 3 years and 60K stars later.

Reading exercise

Open the Orca paper. Answer, from memory, before checking:

  1. Why is attention specifically excluded from selective batching?

  2. Why does the scheduler decide at iteration granularity instead of “every K tokens”? What breaks if K > 1?

  3. What does Orca do when a new request’s prefill is much longer than the current decode step’s compute?

  4. Given 8 GPUs and TP=4 + PP=2, how many workers do you have, and how does one iteration’s control flow work?

If you can answer all four, you own the paper. If not, re-read section 4.