21. Latency-Budget Allocation Across Pipeline Stages

Problem

A voice pipeline strings together several stages — ASR, then an LLM, then TTS — and the whole thing has a fixed end-to-end latency budget it can't exceed without the conversation starting to feel laggy. Each stage typically offers a faster variant (worse quality) and a slower variant (better quality).

Given the budget, decide which variant to pick per stage to get the best overall quality without blowing the total time allowed.

Source: src/21_latency_budget_allocator.py

def min_quality_cost(stages: list[tuple[int, int, int, int]], budget_ms: int) -> int:
    ...

Examples:
>>> min_quality_cost([(100, 3, 200, 1), (135, 2, 270, 1)], 300)
5

>>> min_quality_cost([(100, 3, 200, 1), (135, 2, 270, 1)], 50)
-1

Step-by-Step Approach

1. Recognize the shape: exactly one choice per stage, each choice has a (latency, cost) pair, and the goal is to minimize total cost subject to a total latency ceiling — a 0/1 knapsack where "weight" is latency and "value" (to minimize) is quality cost.
2. Define dp[b] as the minimum total quality cost achievable using exactly b ms of the budget consumed so far, initialized to infinity everywhere except dp[0] = 0.
3. Process stages one at a time. For each stage, build a fresh new_dp array: for every reachable prior budget state used with cost dp[used], try both the fast and slow variant, and if the resulting total latency used + lat still fits within budget_ms, update new_dp[used + lat] if this path is cheaper.
4. Replace dp with new_dp after each stage so that a stage's own two options don't get combined with each other (exactly one variant per stage, never both or neither).
5. After all stages are processed, the answer is min(dp) across every budget state that's still reachable — the cheapest total cost, regardless of exactly how much of the budget it used, as long as it didn't exceed it.
6. If every entry in dp is still infinity, no combination of choices fit — not even the cheapest, fastest option for every stage — so return -1.

The key insight is that the DP state only needs to track budget consumed, not which stage you're on for indexing purposes, because each stage transition is applied exactly once to the whole array in sequence — this is the standard 0/1 knapsack recurrence with the objective flipped to minimization under a capacity constraint.

Reference solution

def min_quality_cost(stages: list[tuple[int, int, int, int]], budget_ms: int) -> int:
    INF = float("inf")
    # dp[b] = min quality cost achievable using exactly b ms of budget consumed so far
    dp = [INF] * (budget_ms + 1)
    dp[0] = 0
    for fast_lat, fast_cost, slow_lat, slow_cost in stages:
        new_dp = [INF] * (budget_ms + 1)
        for used, cost in enumerate(dp):
            if cost == INF:
                continue
            # try both variants for this stage from every reachable prior state
            for lat, extra_cost in ((fast_lat, fast_cost), (slow_lat, slow_cost)):
                nb = used + lat
                if nb <= budget_ms and cost + extra_cost < new_dp[nb]:
                    new_dp[nb] = cost + extra_cost
        dp = new_dp
    best = min(dp)
    return best if best != INF else -1

Key Functions & Tricks

• dp[b] = min cost at exactly budget b — the standard bounded-knapsack state, indexed by consumed capacity rather than by stage.
• new_dp per stage instead of updating dp in place — prevents a stage's fast and slow options from illegally combining within the same stage.
• if nb <= budget_ms — the capacity constraint, pruning any combination that would blow the budget before it's ever recorded.
• min(dp) over the whole array — the answer doesn't require using the full budget, just not exceeding it, so every reachable state is a candidate.
• float("inf") sentinel — marks unreachable budget states cleanly, so the final "no combination fits" check is a single equality test.

How to Recognize This Pattern