Level 1 Continuous batching
A language model server generates text one token at a time. A decode step runs the model once for a whole batch of requests and gives each of them one new token. Old servers waited for the whole batch to finish before starting a new one, so short replies sat idle next to long ones. Continuous batching fixes that: as soon as a request finishes, its seat in the batch goes to the next request in the queue.
You will simulate that scheduler. There is no machine learning here, only bookkeeping.
Write run_batches(requests, max_batch, kv_budget=None) -> list[tuple[int, int]]. Each request is a tuple (arrival, prompt_len, output_len), and requests is sorted by arrival. kv_budget is for level 2; it is None here, and prompt_len doesn't matter yet either.
The rules:
- Time is counted in decode steps
0, 1, 2, .... A request witharrival = ajoins the end of the waiting queue at the start of stepa. Requests with the same arrival join in list order. - At the start of each step, requests leave the front of the queue and start running while fewer than
max_batchrequests are running. - During a step, every running request produces one token. A request that starts at step
sproduces tokens at stepss, s + 1, ..., s + output_len - 1. It finishes at the last of those steps and leaves at the end of it, so its seat can be reused from the next step. - Return one
(start, finish)pair per request, in the order ofrequests.
requests = [(0, 5, 3), (0, 2, 1), (1, 4, 2), (2, 1, 2)]
run_batches(requests, 2)
# [(0, 2), (0, 0), (1, 2), (3, 4)]
| step | starts | running during the step | finishes |
|---|---|---|---|
| 0 | r0, r1 | r0, r1 | r1 |
| 1 | r2 | r0, r2 | |
| 2 | (r3 arrives, no seat) | r0, r2 | r0, r2 |
| 3 | r3 | r3 | |
| 4 | r3 | r3 |
Constraints: up to 10^5 requests; 1 <= max_batch <= 10^5; arrival is in 0..10^9; prompt_len and output_len are in 1..10^9. Steps can therefore go past 10^14: return them as 64-bit integers in C++ and Java.
Replies can be a billion tokens long, so visiting the steps one by one is far too slow for some of the tests: your work should depend on the number of requests, not on the number of steps.
⭐ Bonus: a speed test with 10^5 requests and max_batch = 5000 earns a star in O(n log n) time.