Continuous Batching Scheduler

Background

Continuous batching (vLLM-style) packs new requests into the same GPU batch as the in-flight requests, decoding one token per step. Throughput improvement over static batching is 5–10× because the GPU is never idle between requests.

Problem statement

Implement simulate_batching(arrivals, capacity). Each step:

1. Admit pending requests whose arrive_step <= current_step into the active set, up to capacity.
2. If the active set is empty, jump time to the next arrival (idle).
3. Otherwise: record the active-set size as this step's batch, then decrement each active request's remaining token count by 1. Drop any that hit zero.
4. Advance the step.

Return the list of per-step batch sizes (one entry per non-idle step).

Input

• arrivals — list[tuple[int, int]], each (arrive_step, gen_length). Length is the number of tokens to generate.
• capacity — int >= 1, max concurrent requests.

Output

Returns list[int] of per-step batch sizes.

Examples

Example 1 — single request

Input:  arrivals=[(0, 3)], capacity=10
Output: [1, 1, 1]

Example 2 — capacity caps concurrency

Input:  arrivals=[(0,5),(0,5),(0,5),(0,5)], capacity=2
Output: all batch sizes <= 2; total work = 4 * 5 = 20

Example 3 — late arrivals fill behind active

Input:  arrivals=[(0,2),(5,2)], capacity=10
Output: first request finishes at step 2; second runs at step 5+

Constraints

• capacity >= 1. Each arrival has gen_length >= 1.
• Arrivals are sorted by arrive_step internally — caller may pass in any order.
• Idle steps (no active and no pending arrivals) are skipped.

Notes

• Why not static batching. Static batches all requests at the start; if any has a long generation, the rest sit idle on the GPU waiting. Continuous batching evicts finished requests immediately and admits new ones.
• Prefill vs decode. Real implementations distinguish prefill (parallel over input tokens) from decode (one token at a time). This kernel models decode only.