Best-of-N is prepaid retries: the cost math of racing parallel attempts

Originally published on Loop & Retry — field notes on building LLM agents that survive production.

Here's the pitch for best-of-N: instead of trying once and retrying on failure, fire off N attempts at the same task simultaneously and keep whichever one finishes first (or scores highest). You've turned a serial wait into a parallel one, so your tail latency drops — no more waiting through however many retries it takes before one succeeds. The catch that doesn't show up in the pitch: you pay for all N attempts every single time, whether you needed them or not, and when that payment stops being worth it depends entirely on a variable most teams never measure — whether your attempts actually fail independently of each other.

The retry-budgets post modeled sequential retry cost: try, and on failure, try again, accumulating the failed attempt's tokens into the transcript each time. Best-of-N is structurally different — there's no accumulation, because the N attempts don't see each other. Each one starts fresh from the same prompt and runs to completion independently. That makes the accounting simpler, which is exactly what makes the tradeoff easy to misjudge.

import random

def cost_sequential(p_fail, tokens_per_attempt, max_retries=4):
    """Expected token cost of retrying serially until success or cap."""
    cost = 0
    for attempt in range(max_retries):
        cost += tokens_per_attempt
        if random.random() >= p_fail:
            return cost, attempt + 1   # succeeded on this attempt
    return cost, max_retries           # exhausted retries, still failed

def cost_best_of_n(p_fail, tokens_per_attempt, n):
    """Best-of-N always pays for all N attempts, launched in parallel."""
    cost = tokens_per_attempt * n
    succeeded = any(random.random() >= p_fail for _ in range(n))
    return cost, succeeded

Run both at p_fail = 0.3

, tokens_per_attempt = 2000

, over 20,000 trials, and the naive comparison looks like this:

Same success rate, 2.9x the tokens, every time — not just on the runs that needed all four attempts. Sequential retry only pays for extra attempts when the first one actually fails; best-of-N pays for N attempts unconditionally, because it doesn't know in advance which one will win. That's the fee for parallelism: sequential is priced by expected attempts (close to 1 when p_fail

is small), best-of-N is priced by worst-case attempts, always.

The fee buys something sequential retry can't: bounded latency. A sequential retry loop's wall-clock time is a sum — it's a random variable whose tail gets long exactly the way p99 posts warn about, because a bad run means the sum of every failed attempt's latency plus the final success. Best-of-N's wall-clock time is a max across N attempts running concurrently, which is a much better-behaved random variable — its tail barely grows as N increases, because you only need the fastest of N to land, not the last of a serial chain to succeed. If a human is staring at a spinner, that's the number that matters, and it's the reason best-of-N sampling and self-consistency voting are real, published techniques and not just an expensive mistake.

So the fee is legitimate when latency has a price and independent attempts genuinely raise your odds. The question that decides whether it's a good trade is the one the pitch skips: how independent are your attempts, really?

The $200 postmortem turned on one fact: retryability is a property of the specific error, not a default you apply to every error. An HTTP 400 from a malformed request will fail identically no matter how many times or how quickly you retry it, because nothing about the retry changes the thing that's wrong. That fact doesn't go away when you switch from sequential to parallel — it gets worse, because parallel execution removes the one thing that occasionally saves you in a sequential loop: a later attempt happening after some upstream state has changed.

Extend the model to make failures correlated instead of independent — a shared cause (a bad system prompt, a broken tool schema, a poisoned upstream fact) that fails every attempt the same way with probability p_shared

, on top of ordinary independent noise p_indep

:

def cost_best_of_n_correlated(p_shared, p_indep, tokens_per_attempt, n):
    """A shared-cause failure dooms every attempt identically; only the
    remaining slice of runs benefits from N independent rolls."""
    cost = tokens_per_attempt * n
    if random.random() < p_shared:
        return cost, False   # every one of the N attempts fails the same way
    succeeded = any(random.random() >= p_indep for _ in range(n))
    return cost, succeeded

At p_shared = 0.15

— a modest 15% chance the failure is systemic rather than transient — best-of-N's success rate caps at 85% no matter how large you make N, because the correlated slice of runs fails identically on every single attempt. You've spent tokens_per_attempt * n

restating the same doomed request N times, in parallel, instead of once. Sequential retry wastes tokens on the same correlated failures too, but it wastes tokens_per_attempt * max_retries

at most — best-of-N wastes exactly that much on every correlated failure, with no cap-based early exit, because all N attempts fire before any of them can report back.

This is the same lesson the postmortem already taught, arriving through a different door: N parallel attempts amortize independent noise and do nothing for a shared cause. If you don't know your p_shared

, adding N doesn't just fail to help — it multiplies the cost of every failure that N can't fix by exactly N.

Best-of-N is a legitimate lever, not a trap to avoid — but only once you've priced it against sequential retry using your own numbers, not the pitch's:

p_shared

before picking N.The honest framing: best-of-N doesn't dodge the retry-budget math from the earlier post — it prepays it, in full, on every request, in exchange for a flatter latency tail. That's sometimes exactly what you want. It's never free, and for a shared-cause failure it isn't even a discount.