When one request in a batch finishes, why should its empty slot wait for the longest request? Autoregressive generation naturally exposes a scheduling boundary after each model iteration. A server can use that boundary to reconsider who runs next.
Orca introduces iteration-level scheduling together with selective batching. The scheduler asks the engine to perform one generation iteration, rather than committing to an unchanged batch until every request finishes. Selective batching supports operations over requests at different token positions. Orca paper
Orca evaluates iteration scheduling together with selective batching on GPT-3 175B and reports substantially higher throughput at the same latency than FasterTransformer. That is a serving-system comparison, not proof that every admitted request is free for existing streams. The useful scheduling question is which waiting time is removed and whose iteration cost may increase.
Isolate admission from response delivery
Use a synthetic server with capacity for two requests per iteration. Every iteration takes one time unit regardless of occupancy. Requests A and B arrive at time zero and need four and one output tokens respectively. Request C arrives at time one and needs one token.
Both policies start A and B immediately. At time one, B is complete and A has three tokens remaining. To make the comparison conservative, allow both policies to return B's response immediately. The only difference will be whether C may occupy the vacated slot.
A fixed-membership batch leaves that slot idle until A finishes at time four. It then admits C, which finishes at time five. Completion times are A: 4, B: 1, C: 5.
An iteration-level scheduler admits C at the boundary at time one. A and C execute together, so C finishes at time two. A still finishes at time four. Completion times become A: 4, B: 1, C: 2.
C's response time, measured from its arrival, falls from four time units to one. A receives no speedup, and B receives no speedup. The improvement comes from filling otherwise idle batch capacity, not from making an individual token computation faster.
A boundary is useful only if the engine can use it
The code models precisely this admission difference. It does not reproduce Orca's kernels, distributed execution, or selective-batching implementation. Allowing an early response from the fixed-membership policy also differs from the stricter locked-response behavior discussed in the paper; this example deliberately separates the two effects.
The fixed one-unit iteration cost is a strong assumption. In a real system, batch size, sequence lengths, attention state, and prompt processing can affect duration. Adding C could slow the iteration A shares with it. Whether the resulting tradeoff is worthwhile depends on the service objective and measured cost curve.
Memory imposes another limit. An available request slot does not imply enough KV-cache space for a new request. Admission must consider both compute capacity and storage growth. The scheduler's ability to change membership is a mechanism; the admission policy determines how that mechanism is used.
For analysis, keep arrival time, first-token time, and completion time in separate fields. Averaging absolute completion timestamps would confound arrival patterns with user-visible waiting time. Also report long requests, not only the short arrivals that obviously benefit in this example.
Let a fuller batch take longer
The extension changes each iteration's duration to 0.7 + c times the active request count and sweeps c. Arrival timestamps remain absolute: C arrives at time one, even if the current iteration finishes at 0.9 or 1.3. The simulator only admits work at an iteration boundary and never retroactively inserts C into an iteration already in flight.
At c = 0.3, the initial A/B iteration lasts 1.3 units. Fixed membership then runs A alone for three one-unit iterations; A finishes at 4.3 and C completes at 5.3. C's response time is therefore 4.3. Iteration-level admission instead runs A and C together in the second iteration. C finishes at 2.6, so its response is 1.6 units, while A finishes at 4.6.
The short arrival still benefits substantially, but the long request now pays 0.3 extra units. This is the tradeoff hidden by the constant-duration example. The plotted rectangles come from the actual event log, so their widths show which iterations became more expensive.
Changing admission granularity gives a policy a choice; it does not specify the objective that should govern that choice. An interactive service may prioritize first-token delay, a maximum token gap, completion time, or weighted combinations. Before choosing a refill rule, measure iteration cost against occupancy and context length, enforce cache capacity, and evaluate the resulting request-level distribution. Reporting only the newly admitted short request would miss the cost borne by A.