progress

~/problems / AI infrastructure

Continuous batching scheduler

On a phone? Coding is easier on a laptop: email this problem to yourself . Meanwhile: quiz this topic or fight a boss.

medium assessment 2 levels ~40 min xAI

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 with arrival = a joins the end of the waiting queue at the start of step a. 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_batch requests are running.
  • During a step, every running request produces one token. A request that starts at step s produces tokens at steps s, 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 of requests.
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.

Level 2 unlocks when level 1 passes.

Topic: AI infrastructure. The plumbing around models: request batching, streaming responses, prompt caches, sampling, token limits and eval harnesses.

Read the visual guide
0:00
Ctrl ' run · Ctrl ↵ submit
esc