Unbounded retries turn the hardest inputs into an unbounded tail

An evaluator-optimizer loop retries until its check passes. Written that way it has no upper bound on anything, and the previous chapters have all treated the number of attempts as a parameter without saying where the number comes from. This chapter is about where it comes from, and about the three things an unbounded loop does that are invisible in the summary statistic most teams watch.

The running example is the claims extractor of chapter 1 — a document-processing service that turns scanned insurance claims into structured records, checking each candidate against a constraint list and re-prompting when the list is not empty. The figures below are its first week in production, alongside the single-pass version it replaced, which ran the same generator once and shipped whatever came out.

Why the median did not move and the tail moved tenfold#

The week-one dashboard had one row that looked wrong and one that looked fine. Median end-to-end latency was 2.4 seconds, identical to the single-pass version. The 99th percentile had gone from 6.1 seconds to 71 seconds.

Those two rows are not in tension, and the reason is close to a proof rather than an observation. Seventy-eight per cent of documents passed the constraint list on the first attempt. A document that passes on the first attempt does exactly what the single-pass version did, at exactly the same cost, because the loop's second attempt never happens for it. So the requests that behave differently under the loop are the ones that fail the first attempt, and those are the minority — a smaller share than half. Sort every request by latency and the ones the loop touched are all above the point where first-attempt passes run out, which sits well above the middle of the distribution. The median request is therefore a first-attempt pass under both designs, and p50 could not have moved. It is not that the loop happened not to affect the median; it is that the loop cannot affect the median while its first-attempt pass rate is above half.

The tail is the same argument run the other way, with one extra term. The requests at the top of the distribution are the ones that retried, so their latency is the number of attempts multiplied by the cost of an attempt. Both factors are larger for a hard document: a 14-page scanned claim with handwriting on it takes longer per attempt and is more likely to need another one. For the hard documents that came to roughly 13 attempts at 5.2 seconds each. Two positively correlated factors multiplying is why the tail moved by an order of magnitude rather than by a factor of two — if attempts and per-attempt cost were independent, the tail would grow by the attempt count alone.

Underneath both rows was something a percentile cannot show at all. Four requests from the Tuesday batch were still open when someone looked on Thursday morning, holding their worker threads, having each burned somewhere north of 400,000 output tokens. A request that never returns has no latency to contribute to any percentile. It is simply missing from the distribution, and the distribution looks better for its absence.

Some inputs have no output that would pass#

The four requests that never returned are a different phenomenon from the slow ones, and it is the one that makes a ceiling non-negotiable. A verifier defines an accepting set — the outputs for which its problem list comes back empty — and that set is the intersection of the sets each individual constraint accepts. Intersections can be empty. For each of those four documents the set of outputs that would satisfy the verifier, given what the document actually says, was empty, so no number of attempts could have ended the loop.

Two of them were blank-field cases. The claim form had no deductible printed anywhere, because the broker's template omits it for policies where the deductible is carried on the schedule rather than the claim, and the verifier requires deductible to be present and non-null. So the model had two moves available: omit the field, which fails, or invent €500, which would have passed — and did, on other documents, which is the wrong-pass problem of earlier chapters rather than this one. On these two it happened to keep omitting. The set of faithful outputs was empty; the set of accepted outputs was not, and which one the loop found was luck.

The other two were caused by the verifier contradicting itself, which is more common than it sounds and much harder to see in review.

# Both constraints are individually reasonable.
if Decimal(str(claim["total_claimed"])) != Decimal(str(claim["total_claimed"])).quantize(Decimal("0.01")):
    problems.append("total_claimed must have at most 2 decimal places")

line_sum = sum(Decimal(str(li["amount"])) for li in claim["line_items"])
if line_sum != Decimal(str(claim["total_claimed"])):
    problems.append(f"line items sum to {line_sum}, total_claimed is {claim['total_claimed']}")

Follow the two constraints on one document. The two claims were denominated in Bahraini dinar, whose minor unit has three decimal places, and the line items summed to BHD 1,204.375. The second constraint says total_claimed must equal that sum exactly, which pins it to a value with three decimals. The first says any value with more than two decimals is a violation. There is no number satisfying both, so the accept set for this document is provably empty, and the emptiness is a property of the pair rather than of either constraint — each one alone is satisfiable and sensible.

The model cannot discover this from the feedback, and that is worth spelling out because it explains why the loop does not give up. Each attempt violates exactly one of the two, so each attempt receives a message naming one constraint, and each such message describes a problem that is individually fixable. Round total_claimed down and the sum constraint fires. Restore the exact sum and the decimals constraint fires. Nothing in the feedback ever says both at once, because the code returns whichever problems the current candidate has and no candidate has both. The loop is being told, truthfully, at every step, that it is one small edit away, and it ran until someone killed it. A verifier is a specification and specifications can be unsatisfiable; a bounded loop turns that from an outage into a rejected request with a diagnostic attached.

There is a third mechanism worth naming because it takes down neighbours rather than itself. Retries are load amplification that switches on exactly when the system is struggling — a degraded model endpoint returns lower-quality output, more outputs fail the check, each failure produces another call to the same degraded endpoint. Without a ceiling there is no upper bound on the traffic one request generates, and a system in that state does not recover when the underlying problem clears, because the backlog it built keeps it saturated.

Four bounds, and what each one is for#

A retry ceiling alone is the usual first fix and it is not sufficient, because attempts, wall-clock time and money are three different budgets that run out in different situations.

Read the last column across the rows rather than down, and the table stops looking like four alternatives. What max attempts misses is slow attempts, which is what the deadline covers. What the deadline misses is cheap fast attempts that burn tokens, which is what the cost ceiling covers. What the cost ceiling misses is latency, which is the deadline again. Three of the four rows have their gap plugged by another row, which is why they are a set rather than a menu — picking one and leaving the rest out leaves a hole somebody's request will find.

Only the fourth row's gap is uncovered. No-progress detection catches a loop repeating itself and misses a loop oscillating slowly between two failures, and nothing else in the table catches that either, because an oscillating loop is making apparent progress on every step. It is bounded by attempts and by the deadline in the end, like anything else, but it is not detected early, and the Bahraini-dinar documents are exactly that case: attempt n fails the decimals rule, attempt n+1 fails the sum rule, and no two consecutive signatures match.

The deadline is the one most often omitted and it is the one the caller actually cares about, since a user waiting on an HTTP request has a fixed budget that does not care how it was spent. Passing a deadline down, rather than a timeout per call, means the loop can decide not to start an attempt it cannot finish, which is both cheaper and better behaved than being cancelled mid-generation.

No-progress detection catches the unsatisfiable cases early and cheaply where it applies. When attempt n fails with the same first constraint and the candidate hashes to the same value as attempt n−1, further attempts are drawing from the same conditioned distribution and there is no reason to expect a different result; stopping there saved the Bahraini-dinar requests 11 attempts each in a replay.

Choosing the ceiling from the marginal yield curve#

Choosing the attempt ceiling is a measurement rather than a judgement call, and the input is the marginal yield of each additional attempt on a fixed task set.

The second and third columns are two views of the same measurement, and the relation between them is the arithmetic that makes the table readable. Write C(n) for the cumulative pass rate after n attempts and c(n) for the conditional rate of attempt n — the share of documents still in the loop that attempt n clears. The documents still in the loop after n attempts are the ones the first n did not clear, which is 1 − C(n) of the original population. Attempt n+1 clears c(n+1) of them. So

C(n+1)  =  C(n)  +  (1 − C(n)) · c(n+1)

and the whole cumulative column is that line applied repeatedly, starting from C(1) = c(1). The fourth column is the same quantity expressed differently: C(n+1) − C(n), per thousand documents rather than as a percentage. That is why 121 sits beside the jump from 78.0 to 90.1 and 7 sits beside the jump from 95.3 to 96.0.

Two things fall out of the formula that are worth naming rather than leaving for the reader to infer. First, the rescued column must fall even if the conditional rate stayed constant, because the pool it is drawing from shrinks by a factor of 1 − C(n) each round. A constant conditional rate would still produce a decaying rescue column. Second, the conditional rate does not stay constant — it falls attempt over attempt, from 78.0 to 55.0 to 38.0 and downward. That is the same selection effect that made the p99 explode: the population left in the loop after each round is the subset that failed every round before it, which is systematically the harder documents. So the rescued column is falling for two compounding reasons, which is why it drops from 121 to single digits within three rows.

Now price the rows against the last column. Attempts four and five rescue 22 documents per thousand between them, and by the attempt-bucket defect rates from the previous chapter, roughly half of those rescued outputs are wrong. The added p99 for those two rows is 13.1 and 18.4 seconds. The team set the ceiling at three, which costs 6.2% of documents going to the exhausted path — the complement of the 93.8% cumulative — and buys a p99 of 12 seconds. Nothing in that decision required a judgement about how good the model is. It required the two columns and the defect rates, and the defect rates are why the rescued documents are not counted as a straight gain.

A request that never returns is a capacity leak rather than a slow request#

Those four bounds are all per request, and they leave out the constraint that decides whether the system stays up, which is the pool the requests run in.

The arithmetic here is one line and it is the line most retry designs skip. If work arrives at a rate λ, each unit of work occupies a worker for a mean service time S, and there are c workers, then the offered load is λ·S worker-seconds of demand per second of wall clock, and the system can only keep up if that is below c. The extractor processes about 4,000 documents a day arriving in two bursts, with a peak arrival rate of 3.1 documents per second against twelve workers that each handle one document at a time. Under the single-pass design mean service time was 2.6 seconds, so peak offered load was 8.1 worker-seconds per second against a capacity of twelve, and the queue stayed short.

The uncapped loop raised the mean service time to 5.9 seconds. Note which statistic moved: retries are concentrated on documents that are also slower per attempt, so the mean moves much further than the median does, and it is the mean that appears in λ·S. Offered load becomes 18.3 against a capacity of twelve. Above capacity there is no steady state, and a comparison of means stops being a prediction there: λ·S < c tells you a queue can drain, and it does not tell you how long anybody waits, because that depends on the arrival pattern. Above capacity there is no queue length to compute at all — waiting time grows with the length of the burst rather than settling anywhere. That is why the p99 the team saw was partly generation time and partly documents sitting in a queue behind other documents' retries, and why no amount of averaging over the day would have revealed it.

The four requests that never returned do something worse than consume capacity temporarily. Each one held a worker from Tuesday afternoon until somebody killed it on Thursday, so a twelve-worker pool was running on eight for roughly forty hours, and the same four workers would have been lost every day the same broker submitted the same templates. That is a leak rather than a load: it does not clear when the burst ends.

Capping attempts fixed the leak and did not by itself fix the capacity, and the same one-line calculation says why. At a cap of three the mean service time is 3.9 seconds, so peak offered load is 3.1 × 3.9 = 12.1 against twelve workers, which is still not a working system — it is above capacity by a hair, which is the regime where queues grow without bound during a burst. The pool went to eighteen workers, which brings utilisation to 12.1 divided by 18, or 0.67, and the queueing component of p99 back under two seconds. The general statement is worth keeping: any bound you choose changes the mean service time, the mean service time sizes the pool, so the cap and the capacity plan are one decision and not two.

Where retries and first attempts share a worker pool, a burst of hard documents delays every easy document behind it. Separating the two lanes keeps that from happening and gives you a place to shed load that is not the front door.

FIRST_ATTEMPT = asyncio.Semaphore(14)   # first attempts get most of an 18-worker pool
RETRY_LANE = asyncio.Semaphore(4)       # retries queue behind each other, not in front of new work

@asynccontextmanager
async def lane(attempt: int):
    sem = FIRST_ATTEMPT if attempt == 1 else RETRY_LANE
    try:
        await asyncio.wait_for(sem.acquire(), timeout=RETRY_WAIT_SECONDS)
    except asyncio.TimeoutError:
        raise NoCapacity(attempt)
    try:
        yield
    finally:
        sem.release()

A NoCapacity raised out of the retry lane becomes an exhausted run with reason no_capacity, which means that when the system is short of workers the requests it gives up on are second and third attempts at documents that have already failed once, rather than first attempts at documents that would probably have passed. That ordering is worth stating explicitly because the default is the opposite: a single FIFO queue serves retries and new arrivals in arrival order, so the hardest documents get their fourteenth attempt before an easy document gets its first.

Batch workloads need the same reasoning applied to the batch rather than to the request, and the reason a per-request cap does not cover a batch is a small piece of arithmetic. A nightly run over 4,000 documents with a token budget of 30 million gives each document an average allowance, and a per-request cap bounds the maximum rather than the average, so 4,000 requests each staying under their cap can still overrun the batch. The team's controller therefore tracks burn rate against documents completed and lowers the attempt cap for the remainder when the projection exceeds the budget.

An exhausted run has to return something typed#

The failure that follows a badly-designed bound is a loop that raises a generic exception on exhaustion, gets caught three layers up by a handler that logs and returns the last candidate, and quietly delivers an unverified output through the same field as a verified one. Whatever the exhausted path returns has to be distinguishable by the caller without reading a log.

Which of the three exhausted outcomes applies is a product decision made per input class, not a global default. Returning the best failing attempt with a flag works when a partially-correct extraction is useful to the person receiving it and the flag survives every hop — which means a verification_status column in the database, not a field in a JSON blob that the next service drops. A fallback path works when something cheaper and narrower exists: this team had a regex extractor covering three fields for the two broker templates that account for 60% of volume, which handles a fifth of the exhausted cases with lower coverage and no fabrication risk. The human queue is for claims above a value threshold, and it is a real cost that has to be sized — 6.2% of 4,000 documents a day is 248 items, and if a reviewer handles 25 an hour that is ten hours of work per day. A ceiling chosen without that multiplication in front of you is a ceiling chosen without knowing what it costs.

@dataclass(frozen=True)
class Verified:
    value: dict
    attempts: int
    verifier_version: str

@dataclass(frozen=True)
class Unverified:
    best_effort: dict | None
    unmet: list[str]
    attempts: int
    reason: Literal["attempt_cap", "deadline", "no_progress", "token_cap", "no_capacity"]

def extract(doc: str, model, deadline: float, max_attempts: int = 3) -> Verified | Unverified:
    feedback, last_sig, spent = "", None, 0
    for attempt in range(1, max_attempts + 1):
        if time.monotonic() + EST_ATTEMPT_SECONDS > deadline:
            return Unverified(candidate, problems, attempt - 1, "deadline")
        candidate = model.extract(doc, feedback=feedback)
        spent += model.last_usage.total_tokens
        problems = verify(candidate)
        if not problems:
            return Verified(candidate, attempt, VERIFIER_VERSION)
        sig = (problems[0], hash_output(candidate))
        if sig == last_sig:
            return Unverified(candidate, problems, attempt, "no_progress")
        if spent > TOKEN_CAP:
            return Unverified(candidate, problems, attempt, "token_cap")
        last_sig = sig
        feedback = "The previous attempt failed these checks:\n" + "\n".join(problems)
    return Unverified(candidate, problems, max_attempts, "attempt_cap")

Three properties of that function are decisions rather than details. The deadline check runs before the generation call and adds an estimate of an attempt's duration, so the loop declines to start work it cannot finish rather than being killed part-way through it; the cost of that estimate being wrong is one wasted attempt or one premature refusal, and best_effort is typed as optional because on the earliest exit there may be no candidate to hand back at all. The token check runs after the call, because the tokens are only known once the call has returned, which means the ceiling can be overrun by at most one attempt and is a detector rather than a preventer — if the overrun matters, the cap has to be set an attempt's worth below the real limit. And the return type is a union rather than a struct with an optional flag, which is what makes the distinction survive: a union forces the call site to handle both branches before it can read a value, where an optional field on a single struct gets ignored by the third consumer down the chain.

Retrying a flaky call is not this#

The word "retry" covers two unrelated designs and conflating them produces bounds that are wrong by an order of magnitude. Retrying a 503 or a rate-limit response is an attempt to obtain the same output from a service that failed transiently. Nothing about the request was wrong, the service is expected to recover, and waiting is the mechanism — so the right policy is exponential backoff with jitter, waiting roughly twice as long before each successive try, with a random offset added so that a crowd of clients does not retry in unison, and three attempts over eight seconds is generous.

The loop in this topic retries to obtain a different output from a service that succeeded. The generation worked; the output was unacceptable. Nothing is recovering, so backoff buys nothing except delay, and the cost per attempt is a full generation rather than a reconnection. Every parameter differs: the right count, the right wait, the right cost model and the right failure message. A system with both needs them layered and counted separately — transient retries inside the attempt, so that one flaky HTTP response does not consume a verification attempt, and the verification bound outside. Counting them together produces an attempt histogram in which a rate-limited network and a hard document are the same event.

The belief worth naming before leaving this chapter is the one the week-one dashboard invited: that an unchanged median means nothing changed. It is tempting because the median is the statistic most systems are tuned against and the one most users experience, and it was genuinely, exactly, identical. What makes it useless here is the reason it was identical — the loop provably cannot touch it while most documents pass first time. A number that is pinned by construction cannot report on the thing the construction excludes, and everything this chapter is about lives in the excluded region: the tail, the leaked workers, the batch overrun, the requests with no latency at all.

A bound is a containment measure and it does not improve anything. Capping attempts at three does not make outputs more correct; it converts the runs that would have produced a struggled-for pass into runs that visibly did not finish, which is a better failure and is still a failure. The value of that trade shows up in a number nobody has calculated yet, because with the ceiling in place the extractor's verification pass rate reads 93.8% and the single-pass baseline reads 78%, and someone is about to present the difference as a quality improvement.