4. Backpressure-Aware Token Bucket for Streaming Synthesis

Problem

Text arrives from the LLM faster than synthesized audio chunks can be pushed out over a bandwidth- or rate-constrained connection. Without backpressure, outbound chunks would queue up without bound.

A token bucket rate limiter caps how much can be sent per unit time, forcing chunks to wait their turn in strict arrival order once the bucket runs dry, and letting them go again as it refills. Given each chunk's size and the bucket's capacity and refill rate, determine the tick each chunk actually gets sent.

Source: src/4_backpressure_token_bucket.py

def schedule_sends(chunk_sizes: list[int], capacity: int, refill_rate: int) -> list[int]:
    ...

Examples:
>>> schedule_sends([4, 4, 4], 5, 2)
[0, 2, 4]

>>> schedule_sends([4, 4, 4, 4], 10, 5)
[0, 1, 2, 3]

Step-by-Step Approach

1. Simulate tick by tick starting at t = 0, tracking tokens (starting full at capacity) and a FIFO queue of chunk indices waiting to send.
2. At the start of every tick after the first, refill: tokens = min(capacity, tokens + refill_rate). Skip this at tick 0 since the bucket already starts full.
3. Chunk i always arrives at tick i by construction, so append it to the queue whenever the next unarrived chunk's index equals the current tick.
4. After refilling and admitting the new arrival, drain the queue from the front: while there's a queued chunk and tokens >= chunk_sizes[front], send it (record its tick, subtract its size from tokens), and move to the new front. Multiple chunks can send in the same tick if tokens allow.
5. If the front chunk can't be afforded, stop draining for this tick — it waits, and every chunk behind it in FIFO order waits too, even if a later, smaller chunk could technically afford to jump ahead.
6. Keep advancing ticks until every chunk has both arrived and been sent (queue empty and no more arrivals pending), then return the recorded send tick per original chunk index.

The key insight is that FIFO ordering is strict — the bucket never lets a later, cheaper chunk skip ahead of a stalled earlier one — so the whole simulation reduces to one queue, one token counter, and a refill-then-drain step repeated per tick.

Reference solution

def schedule_sends(chunk_sizes: list[int], capacity: int, refill_rate: int) -> list[int]:
    n = len(chunk_sizes)
    result = [0] * n
    tokens = capacity  # bucket starts full
    queue: list[int] = []  # FIFO of waiting chunk indices
    next_idx = 0
    t = 0
    while next_idx < n or queue:
        if t > 0:
            # refill happens once per tick, capped at capacity, before sends
            tokens = min(capacity, tokens + refill_rate)
        if next_idx < n and next_idx == t:
            # chunk i always arrives exactly at tick i
            queue.append(next_idx)
            next_idx += 1
        # drain as many queued chunks as current tokens allow, in FIFO order
        while queue and tokens >= chunk_sizes[queue[0]]:
            i = queue.pop(0)
            tokens -= chunk_sizes[i]
            result[i] = t
        t += 1
    return result

Key Functions & Tricks

• tokens = min(capacity, tokens + refill_rate) — the core token-bucket refill, capped so tokens never exceed capacity.
• Refill-before-drain ordering per tick — ensures a tick's own refill is available to sends that happen during that same tick.
• while queue and tokens >= chunk_sizes[queue[0]] — strict FIFO draining; only the front of the queue is ever considered for sending.
• next_idx < n and next_idx == t — ties each chunk's arrival to a specific tick equal to its index.
• Loop condition next_idx < n or queue — keeps simulating past the last arrival until the queue has fully drained.

How to Recognize This Pattern