Waiting for Company

A model sits behind an endpoint on one GPU. Live requests arrive one at a time, and a batch of one is the least efficient case there is: every run of the model pays a fixed overhead however many items it carries, and a single item leaves most of the hardware idle.

So the server batches. It holds requests briefly and runs them together, which makes each user wait a little longer and lets the same GPU serve far more of them. This problem is about exactly how much longer each user waits.

The server follows these rules:

• arrivals lists the time, in milliseconds, at which each request arrives. It is sorted from earliest to latest (ties allowed) and holds at least one request.
• The server runs one batch at a time. A batch of $n$ requests takes fixed_ms + per_item_ms * n milliseconds. Requests that arrive while a batch is running wait in the queue.
• A batch launches at the first moment the server is free and at least one of these is true:
  • at least max_batch requests are waiting, or
  • the oldest waiting request has been waiting for max_wait milliseconds.
• The batch takes the oldest waiting requests, up to max_batch of them. Anyone else stays in the queue for a later batch. A request arriving at the very instant a batch launches is in time to join it, if there is room.
• The server starts out idle.
• A request's latency is the moment its batch finishes minus the moment it arrived.

Task: write batched_latencies(arrivals, max_batch, max_wait, fixed_ms, per_item_ms), returning the latency of every request, in arrival order, each as a float rounded to 4 decimal places. max_batch is a whole number of at least 1, and the other settings are non-negative numbers.

Worked through, batched_latencies([0, 1, 3, 9], 2, 4, 5, 1):

• Batch 1. At $t = 1$ two requests are waiting, which fills a batch, and the server is free, so it launches at once. It runs for $5 + 1 \times 2 = 7$ ms and finishes at $t = 8$. Latencies: $8 - 0 = 8$ and $8 - 1 = 7$.
• Batch 2. The request from $t = 3$ has waited its $4$ ms by $t = 7$, but the server is busy until $t = 8$, so this batch launches at $t = 8$. The next request is not due until $t = 9$, so the batch holds one request, runs for $5 + 1 = 6$ ms and finishes at $t = 14$. Latency: $11$.
• Batch 3. The request from $t = 9$ has waited its $4$ ms by $t = 13$; the server frees up at $t = 14$ and launches then, finishing at $t = 20$. Latency: $11$.
• The answer is [8.0, 7.0, 11.0, 11.0].

With max_batch set to 1 there is no batching at all: every request runs alone and pays the whole fixed overhead for itself, so a burst of traffic piles up behind one request at a time. A batching server pays that overhead once per batch and clears the same burst far sooner. The price is some extra waiting when traffic is light, and that is the trade this function lets you measure.