Fan-out turns a sum of latencies into a maximum

The document ingestion path made five model calls per document, one after another: classify the document type, extract the parties, extract the dates, extract the monetary amounts, and produce a two-sentence summary. None of the five read the output of any other. Client-side p50 wall-clock was 4.0 seconds, which is roughly the sum of five calls with medians between 0.7 and 0.9 seconds. Replacing the sequential loop with a concurrent gather took an afternoon, and the median came in at 0.9 seconds — a 4.4x improvement that survived a week of production traffic. That shape has a name: a fan-out issues several independent calls at the same instant and then waits at a barrier, the point in the code where the request cannot proceed until every one of them has come back.

The p99 went from 9.0 seconds to 14.0. No individual extraction call got slower; the p99 of each branch, measured on its own, was unchanged. The change made the median better than sequential had ever been and the tail worse than sequential had ever been, and both of those follow from the same thing.

A sum concentrates and a maximum does not#

Sequential wall-clock is the sum of five draws from the branch latency distribution. Sums average out: for the total to reach 9 seconds, the five draws have to be collectively bad, and one unlucky branch at 4 seconds still leaves a total near 7 if the other four are typical. That is why sequential p99 was 9.0 rather than five times the branch p99 of 3.0 — the probability of five simultaneous bad draws is vanishingly small, so the sum's tail sits far below the sum of the tails.

Concurrent wall-clock is the maximum of five draws, and maxima do the opposite. The response is late if any branch is late, so with independent branches the probability that the whole fan-out finishes within t is the branch probability raised to the fifth power. Solving for the 99th percentile of the maximum:

# P(max of 5 <= t) = F(t)^5 = 0.99   ->   F(t) = 0.99 ** (1/5)
branch_percentile = 0.99 ** (1 / 5)
print(f"{branch_percentile:.4f}")   # 0.9980

The p99 of the fan-out is the p99.8 of a single branch. You did not change any branch; you changed which part of its distribution you are exposed to, and you are now sampling five times deeper into the tail than before. On this workload the branch p99.8 was 5.5 seconds, which predicts an ideal-case fan-out p99 of about 5.5 rather than the 14 that was observed, so independence accounted for part of the regression and something else accounted for the rest.

The bottom section is the shape worth internalising. Four branches finish inside 900 milliseconds and the response is not ready until 5.5 seconds, because the barrier at the end of a fan-out waits for everything. Four fast branches buy nothing whenever a fifth is slow, and the request's latency is entirely a property of whichever branch happened to be worst on that draw.

The part that was not the maximum#

The other four and a half seconds came from the fan-out changing the branches themselves, which is where the independence assumption in that calculation breaks. Firing five calls at once multiplied the instantaneous request rate by five for the same document throughput. The account's rate limit was expressed in requests per minute against a token bucket, an allowance that refills at a steady rate and can be drained all at once by a burst, and a bucket that was comfortable with a smooth 1-per-200ms arrival pattern began rejecting bursts of five. HTTP 429s — the status code a provider returns when a caller has exceeded its rate limit — appeared in the logs for the first time, at about 0.4% of branch calls.

The client library retried those 429s with exponential backoff, which is correct behaviour for an isolated call and destructive inside a barrier. A branch that gets a 429 at 200 milliseconds, waits a 1-second backoff, retries, and succeeds after another 800 milliseconds has taken 2.0 seconds instead of 0.8. The barrier moves out by the full retry cycle, because the barrier is the maximum and the retried branch is now almost certainly the maximum. Retries convert an error into latency, and inside a fan-out they convert one branch's error into the whole request's latency.

That is why the two most natural responses both make the tail worse. Adding retries with backoff on the 429s is the mechanism just described. Raising the timeout so slow branches have room to finish is the same choice written as configuration: the tail is long precisely because nothing bounds how long a single branch may hold the response, and raising the bound raises the tail by construction. Both feel like reliability work and both spend the request's latency budget to avoid returning anything less than a complete document.

Bounding each branch and deciding what a miss returns#

The change that fixes this has three parts, and the third is the one that requires a product decision rather than a code change.

import asyncio

BRANCH_DEADLINE = 2.5            # seconds; the barrier can never exceed this
gate = asyncio.Semaphore(3)      # instantaneous concurrency against the provider

async def branch(name, coro):
    try:
        async with gate:
            return name, await asyncio.wait_for(coro, timeout=BRANCH_DEADLINE)
    except (asyncio.TimeoutError, RateLimited):
        return name, None        # missing, not failed

async def enrich(doc):
    results = dict(await asyncio.gather(*[
        branch("type",     classify(doc)),
        branch("parties",  extract_parties(doc)),
        branch("dates",    extract_dates(doc)),
        branch("amounts",  extract_amounts(doc)),
        branch("summary",  summarise(doc)),
    ]))
    missing = [k for k, v in results.items() if v is None]
    if missing:
        await queue_backfill(doc.id, missing)      # retry lives here, outside the barrier
    return Document(**results, incomplete=missing)

The per-branch deadline of 2.5 seconds puts a hard ceiling on the barrier: no request can now take longer than the deadline plus overhead, regardless of what any provider does. The semaphore of 3 caps instantaneous concurrency below the rate limit, which trades a little median latency for the elimination of the 429 class entirely — a request that waits 150 milliseconds for a semaphore slot is strictly better than one that gets a 429 and a 1-second backoff. And the retry has moved outside the barrier into a backfill queue, where it can take as long as it needs without any user waiting on it.

The third part is that the function now returns a Document with an incomplete list, which means every consumer has to decide what a partially enriched document is. On this pipeline the answer was that type, parties and dates are required and the request fails without them, while amounts and summary are optional and render as "not yet extracted" with the backfill filling them in within a minute. That distinction did not exist before, because sequential code with unbounded waits never has to express it. Deciding it is the actual work; the asyncio.wait_for is the easy part.

Choosing the deadline is choosing a completeness rate#

The 2.5-second figure is not arbitrary and it is not a round number picked for comfort. Once the semaphore removed the 429s, the branch distribution settled at a p50 of 0.8 seconds, a p95 of 1.5, and a p99 of 2.4. A deadline of 2.5 seconds therefore misses about 1% of branch calls, and that per-branch rate compounds across the fan-out exactly the way the maximum did:

q = 0.01                          # per-branch miss rate at a 2.5s deadline
print(f"{1 - (1 - q) ** 5:.1%}")  # 4.9% of documents miss at least one field

One percent per branch is 4.9% per document, and if the pipeline had ten branches it would be 9.6%. Tightening the deadline to 1.5 seconds would cut p99 wall-clock to 1.5 seconds and take per-document incompleteness to 22%, which is a different product. The deadline is the dial between how long the slowest user waits and how often the answer is partial, and there is no setting that avoids the choice.

For a branch that genuinely cannot be dropped, hedging buys back some of the completeness without extending the barrier. Fire a second copy of the call at the branch's p95 and take whichever returns first:

async def hedged(make_call, hedge_at=1.5, deadline=2.5):
    first = asyncio.create_task(make_call())
    done, _ = await asyncio.wait({first}, timeout=hedge_at)
    if done:
        return first.result()
    second = asyncio.create_task(make_call())      # duplicate, not a retry
    done, pending = await asyncio.wait(
        {first, second}, timeout=deadline - hedge_at,
        return_when=asyncio.FIRST_COMPLETED)
    for t in pending:
        t.cancel()
    return done.pop().result() if done else None

Hedging at p95 duplicates 5% of calls, so it costs about 5% more spend and 5% more concurrency, and it turns a 1% miss rate into something near 0.05% when the two attempts fail independently. That independence is the condition, and it holds when slowness is idiosyncratic — one unlucky scheduling decision, one degraded instance — and fails completely when slowness is caused by load, where the duplicate lands in the same congested queue and adds to the congestion that caused the delay. A hedge is a bet that the second attempt will be luckier, and under saturation it is a bet against yourself. The usual safeguard is to cap hedges as a fraction of total requests, so that a system-wide slowdown cannot turn into a system-wide doubling of load.

The bounded column pays about 100 milliseconds of median latency and 4.9% of documents arriving with a field missing for a p99 that is better than sequential's median and, more importantly, for a worst case that exists at all. Whether that is the right trade depends on the consumer, and the row that decides it is the last one, not the first. Note also that the p99 of the bounded column is the deadline itself, which is what it means for a latency to be bounded: the shape of the branch distribution above 2.5 seconds has stopped mattering.

Where fan-out is the wrong instrument#

The whole technique rests on the branches being independent, and the failure mode when they are not is silent. If the summary should describe the extracted parties, then running the two concurrently gives a summary written without them, and the pipeline is now 4.4x faster at producing a slightly worse document. That regression will not appear on any latency dashboard, and it will not appear in the fan-out code either, because a gather over calls that should have been sequential looks exactly like a gather over calls that should not.

There is a subtler version of the same trap around prompt caching, the provider-side feature that stores the processed form of a prompt prefix and reuses it on any later request beginning with the same text, charging less for those tokens and skipping their prefill. Sequential branches that share a long prefix — the same document text, the same system prompt — benefit from cached input on every call after the first, because each one arrives after the previous one has populated the cache. Fired concurrently, all five arrive before any of them has written the cache, so all five pay full input price and full prefill time. A fan-out can therefore raise both cost and per-branch first-token latency for reasons that have nothing to do with rate limits, and the usual fix is to let one branch go first and fan the remaining four out behind it, which costs one branch's latency and recovers the cache.

The rate limit is also rarely yours alone. The token bucket that the fan-out started hitting is typically shared across every feature in the account, so a pipeline that raises its instantaneous concurrency from 1 to 5 is spending headroom that the chat surface and the batch jobs also draw on. The 429s appeared in the ingestion logs first because it was the noisiest consumer, and the next place they would have appeared is somewhere unrelated. Concurrency limits belong at the level of the shared resource rather than per call site, which usually means a single client-side limiter that every feature acquires from, sized against the actual account limit and not against what one pipeline finds convenient.

Fan-out also does nothing for the case where the latency is inside one call. A single 8-second generation with a 30,000-token prompt has no branches to spread, and wrapping it in asyncio.gather alone changes nothing. The levers there are different in kind: shortening the prompt, streaming, splitting the output so the part the user needs comes first, or putting a smaller model in front of the large one so that something is on screen while the slow call runs. That last one moves the response into view within a few hundred milliseconds and introduces a problem the others do not have, which is what happens when the fast answer and the slow answer disagree.