Simulate Continuous (Iteration-Level) Batching

The problem, from first principles

[03-dynamic-request-batching]'s static batching processes one whole batch to completion before forming the next — so if 7 of 8 requests finish quickly but 1 needs 500 more tokens, the other 7 slots sit idle waiting for that straggler. Simulate continuous batching (a.k.a. iteration-level scheduling, as used in vLLM/TGI): at every decode step, any request that has finished is removed from the active batch and any waiting request is admitted into the freed slot immediately.

From theory to code

remaining_tokens[r] -= 1   for every active request r, at each decode step t
active = (active - finished) + admitted_from_queue,  |active| <= max_batch_size

Constraints

• Requests are given as (arrival_step, request_id, n_tokens_needed).
• At each step: decrement remaining tokens for every active request by 1, evict any that reach 0, then admit from the FIFO wait queue (among requests that have arrived by this step) to refill up to max_batch_size.
• Simulation ends when every request has been fully generated.
• Return, per request, the step at which it was admitted and the step at which it finished.

Hints