Orca: A Distributed Serving System for Transformer-Based Generative Models

A generative Transformer does not finish a request in one pass. It processes the prompt, generates one output token, feeds that token back into the model, and repeats. When a serving system fixes a request batch until every member is done, a short answer cannot return while a longer answer keeps generating, and a new request cannot join the running work.

Orca moves the scheduling boundary to a single model iteration (one token step). After every iteration the scheduler can remove completed requests, admit waiting ones, and re-form the batch for the next decode.

What this paper explains

Serving generative models is not the same as serving encoder-only or one-shot models. Autoregressive decoding creates a long-lived request whose length is unknown at admission time. Classical batching that waits for the slowest member therefore:

1. Inflates latency for short responses that finished early.
2. Wastes GPU slots on finished (or empty) work.
3. Blocks new arrivals until the whole batch drains.

Orca’s answer is iteration-level scheduling: reconsider batch membership after every decoder step. The opening figure shows this as a carousel — R2 finishes and returns, R3 joins from the request pool, R1 stays active, and the center cube advances one token.

Prior limits

Before iteration-level scheduling, many systems treated a batch like a training minibatch: admit $N$ sequences, run until all EOS, then refill. That works when sequence lengths are similar. It fails when lengths are heavy-tailed — the common case for chat and code generation.

Static batching also fights the memory reality of KV caches: finished requests still occupy slots until the batch ends, even though their attention state is no longer needed for generation.

The mechanism

Iteration-level scheduling. After each forward pass that produces the next token for every active request:

• Any request that emitted EOS (or hit a length limit) leaves the live batch immediately.
• Waiting requests from a pool enter free slots before the next iteration.
• Remaining requests keep their slots and continue decoding.

Selective batching. Requests in the live batch may sit at different sequence positions (different prompt/output lengths). Orca selectively batches Transformer operators so heterogeneous sequences can still share GPU kernels where safe, instead of forcing a single lockstep shape.

Together: the scheduler owns who is in the batch; selective batching owns how those residents share compute.

Algorithm walkthrough

1. Maintain an active set $A$ and a waiting pool $W$.
2. Run one decoder iteration over $A$ → one new token per active request.
3. Move finished requests from $A$ to completed (return to client).
4. Fill free capacity from $W$ into $A$.
5. Repeat from step 2.

The invariant: batch membership is allowed to change every token, not only when the entire batch completes.

What to notice when reading

• Where the paper draws the line between iteration-level scheduling and selective batching — they solve different halves of the problem.
• How early return of short generations changes latency distributions versus mean throughput alone.
• What must stay correct when sequences in one batch have different lengths (attention masks, KV layout, kernel launch shapes).

Results and evidence

OSDI 2022 evaluation shows large improvements in throughput and latency versus request-level batching baselines for Transformer generative serving. Read the experimental section for the exact model sizes, arrival processes, and comparison systems — treat those numbers as the paper’s claims, not as timeless absolutes for today’s stacks.

Limitations

• Engineering details of modern engines (PagedAttention, CUDA graphs, speculative decoding) post-date or sit beside Orca; the scheduling idea remains the durable takeaway.
• Selective batching’s wins depend on kernel and memory implementation quality.
• Extremely tight SLO regimes may still need complementary techniques (priority queues, preemption, speculation).

How to read the paper

1. Abstract + introduction — problem with request-level batching.
2. Design sections on iteration-level scheduling and selective batching — the core mechanism.
3. System architecture — how the scheduler sits relative to workers.
4. Evaluation — what improved and under which loads.
5. Related work — place Orca next to continuous batching in today’s serving literature.

Knowledge check

Keep reading

1. Original paper (USENIX OSDI 2022) — iteration-level scheduling + selective batching.
2. Related Fanout Daily: Speculative decoding, GQA, PagedAttention / KV cache.
3. Modern continuous-batching dispatchers in production LLM servers (vLLM and peers) — same scheduling idea, newer memory engines.

Sources

• Yu et al., Orca: A Distributed Serving System for Transformer-Based Generative Models, OSDI 2022 — USENIX
• Related Fanout Labs: continuous-batching dispatcher, KV cache, speculative decoding