27. Coalesce Inference Requests into Batches

Problem

A lab's inference-serving layer receives a steady stream of small generation requests arriving at slightly different times. Dispatching each one individually to a GPU worker wastes fixed per-request launch overhead and under-utilizes the GPU, so the server instead coalesces nearby requests into a single forward pass.

A batch closes as soon as it hits whichever limit is tightest: max_batch_size requests, max_batch_tokens total prompt tokens, or max_wait_ms elapsed since the batch's first request arrived. Requests arrive as (arrival_time_ms, prompt_tokens) pairs, sorted ascending by arrival time.

Source: src/27_coalesce_inference_batches.py

def coalesce_inference_requests(
    requests: list[tuple[float, int]],
    max_batch_size: int,
    max_batch_tokens: int,
    max_wait_ms: float,
) -> list[list[tuple[float, int]]]:
    ...

Examples:
>>> coalesce_inference_requests(
...     [(0, 50), (1, 60), (2, 30), (3, 20), (10, 40), (11, 10)],
...     max_batch_size=3, max_batch_tokens=150, max_wait_ms=5,
... )
[[(0, 50), (1, 60), (2, 30)], [(3, 20)], [(10, 40), (11, 10)]]

Step-by-Step Approach

1. Recognize this as a single left-to-right greedy sweep: once you decide a request belongs to the current batch, that decision never needs to be revisited.
2. Start a new batch at each unconsumed request. Track that batch's first arrival time (for the wait limit) and its running token total (for the token limit).
3. Walk forward from there, and for each next candidate request check all three limits at once: would adding it exceed max_batch_size, would it push the token sum over max_batch_tokens, or has too much time elapsed since the batch's first request?
4. The moment any one of those three checks fails, stop extending — close the current batch and start a fresh one at the request that didn't fit.
5. Because requests are already sorted by arrival time, you never need to look backward or re-sort; a single index sweep suffices.
6. Handle edge cases: an empty request list produces no batches, and max_batch_size=1 degenerates to one request per batch regardless of the other two limits.

The key insight is that all three limits are just independent early-exit conditions on the same greedy extension loop — you don't need three separate passes or any lookahead, because a request that doesn't fit the current batch can never retroactively fit an earlier, already-closed one.

Reference solution

def coalesce_inference_requests(
    requests: list[tuple[float, int]],
    max_batch_size: int,
    max_batch_tokens: int,
    max_wait_ms: float,
) -> list[list[tuple[float, int]]]:
    # single linear sweep, greedily extending the open batch: O(n) time, O(1) extra space
    batches: list[list[tuple[float, int]]] = []
    i = 0
    n = len(requests)
    while i < n:
        first_time, first_tokens = requests[i]
        batch = [requests[i]]
        batch_tokens = first_tokens
        j = i + 1
        # stop the moment any one of the three limits would be exceeded
        while (
            j < n
            and len(batch) < max_batch_size
            and batch_tokens + requests[j][1] <= max_batch_tokens
            and requests[j][0] - first_time <= max_wait_ms
        ):
            batch.append(requests[j])
            batch_tokens += requests[j][1]
            j += 1
        batches.append(batch)
        i = j
    return batches

Key Functions & Tricks

• while (j < n and ... and ... and ...) — chains all three stopping conditions into one short-circuiting inner loop
• Greedy single-pointer sweep — a decision to close a batch is never revisited, so one forward pass suffices
• batch_tokens running total — avoids re-summing the batch's tokens on every candidate check
• first_time captured once per batch — the wait limit is always measured from the batch's first arrival, not the previous request's
• i = j — the outer pointer jumps straight to the first request that didn't fit, no re-scanning

How to Recognize This Pattern