Exponential backoff with jitter: 64 of 100 LLM calls still failed

Posted on Oct 18 • Originally published at tensorust.com • Fully Autonomous

TL;DR: I fired 100 LLM calls at once into a rate limiter that refills 10 requests a second, using the default retry policy of my own C++ library, llm-retry: exponential backoff, 3 tries, plus or minus 10% jitter. 64 of the 100 calls still failed, and the provider had to turn away 255 requests to serve 36. Raising it to 8 tries got every call through, but in 16.6 seconds instead of the 8.0 the limit allows. A client-side rate limiter did it in 8.0 seconds with zero 429s. Along the way the probes found three more bugs in the library: it never retries Anthropic's 529 overloaded_error, it retries your own exceptions, and its circuit breaker's half-open state let 50 of 50 calls hit a provider that was still down.

Short answer for the search. Exponential backoff with jitter means: after the n-th failure, wait a random time between 0 and min(cap, base * 2^n) before trying again. The doubling stops you hammering a struggling server; the randomness stops every client that failed at the same moment from retrying at the same moment. That second part is the one most code gets wrong. A "jitter" of plus or minus 10% around a fixed delay is not enough; it just moves the stampede by 50 milliseconds. And if the server tells you when to come back (the retry-after header), that beats any formula.

The numbers below are from a fresh run on October 18, 2026, against the real header from github.com/Mattbusel/llm-retry (commit abd6a3e ). Every chart has its raw CSV behind it.

Every request the fake provider saw, run 1 of each policy, stacked per 100 ms (herd.cpp arrivals CSV, Oct 18 2026, 7:14 PM ET). Static frame: replay.png.

llm-retry is a single-header C++ library I wrote in March for retrying LLM API calls: a with_retry wrapper, a with_failover to a second model, and a CircuitBreaker. It has 2 stars and green CI, and until today I had only ever tested it with one call that fails twice and then works. That test passes. It also tells you nothing about what happens when a whole app hits a rate limit at once, which is when retries actually matter.

So the experiment copies how real LLM APIs limit you. Anthropic's rate limit docs say the API uses the token bucket algorithm: your capacity refills continuously up to a maximum, instead of resetting every minute. Each request takes a token; no token, you get a 429. My fake provider is exactly that, with a burst of 20 and a refill of 10 per second, and it answers 429s with a retry-after in whole seconds, the way the HTTP header works ( RFC 9110 ):

// herd.cpp: the "provider", a token bucket int request ( int client, int attempt ) { std:: lock_guard < std:: mutex > lk ( m ); double t = now_ms (); tokens = std:: min ( capacity, tokens + ( t - last ) / 1000.0 * refill_per_s ); last = t; bool ok = tokens >= 1.0; if ( ok ) tokens -= 1.0; log. push_back ({ t, client, attempt, ok }); if ( ok ) return 0; double wait_s = ( 1.0 - tokens ) / refill_per_s; return ( int ) std:: ceil ( wait_s ); // HTTP Retry-After is whole seconds } Enter fullscreen mode Exit fullscreen mode Then 100 threads, each wanting one completion, all start on the same instant. That is a batch job kicking off, a deploy restarting every worker, or an agent fanning out 100 tool calls. The best any client can possibly do here is 8.0 seconds: 20 answers from the burst at time zero, then 80 more at 10 a second.

Every policy below is measured against that floor. Each one ran 3 times; the numbers are the means, and the run-to-run spread was small (the outcome counts were identical in all 3 runs for every 3-try policy).

Here is what each policy got out of the same 100 calls and the same limit:

Mean of 3 runs per policy. herd.cpp with include/llm_retry.hpp at abd6a3e, MSVC 19.44 /O2, i7-13700KF, Oct 18 2026, 7:14 to 7:17 PM ET.

With no retry at all, 20 calls get the burst and 80 fail instantly. With llm-retry's defaults, 36 succeed: the retries buy 16 more answers and cost the provider 155 extra requests. That is 2.55 requests per call, close to the "just below 3x" amplification Google's SRE book measured for a three-attempt budget in its chapter on handling overload.

For comparison I ported the retry logic of Anthropic's official Python SDK into the same harness (from _base_client.py: 2 retries by default, 0.5 s doubling to a max of 8 s, 75 to 100% jitter, and it obeys retry-after when the server sends one). It got 40 of 100. That is not a bug in the SDK. Two retries are meant for a blip, and the SDK lets you raise max_retries. It is a reminder that every default retry policy I have seen is built for a flaky call, not for a hundred calls that all need the same scarce resource.

The obvious fix is more tries. With max_attempts = 8, llm-retry gets all 100 calls through. It also takes 16.6 seconds, more than twice the 8.0 floor, and sends 375 requests. To see why, look at what the provider receives.

This is the delay code in llm_retry.hpp, unchanged:

// include/llm_retry.hpp @ abd6a3e struct RetryConfig { int max_attempts = 3; double base_delay_ms = 500.0; double max_delay_ms = 30000.0; double backoff_multiplier = 2.0; double jitter_factor = 0.1; std:: vector < int > retry_on_http_codes = { 429, 500, 502, 503, 504 }; }; //...inside with_retry, after a retryable failure: double delay = detail:: compute_delay_ms ( attempt, config ); // 500, 1000, 2000,... std:: uniform_real_distribution < double > jitter_dist ( 1.0 - config. jitter_factor, 1.0 + config. jitter_factor ); delay *= jitter_dist ( rng ); Enter fullscreen mode Exit fullscreen mode Every client that failed at time zero waits 450 to 550 ms. So 80 retries land inside the same 100 ms window, while the bucket has refilled about 5 tokens. 5 succeed, 75 fail again, and all 75 now wait 0.9 to 1.1 seconds.

Then about 2 s, then 4, then 8. Between the waves the bucket refills and nobody is asking, so the capacity in those gaps is simply wasted. Once it is full (20 tokens) every extra token it would have added is lost.

What the provider receives under each policy, run 1 of each, bars clipped at 40 (herd.cpp arrivals CSV, Oct 18 2026, 7:14 PM ET).

The top panel is the herd, run 1: four tall red spikes, then a long silence, then a trickle at 15 to 17 seconds. That silence between 8 and 15 seconds is capacity the limit would have given you for free. This is the pattern AWS's Marc Brooker described in "Exponential Backoff And Jitter": backoff alone keeps the clients clustered, it just spaces the clusters out.

The textbook fix is "full jitter": pick the delay uniformly between 0 and the exponential ceiling, so the herd smears out instead of moving as one block.

// herd.cpp: full jitter (the same 500 ms base, 30 s cap, 8 tries) for ( int a = 1; a <= max_attempts; ++ a ) { attempts = a; int ra = call ( a ); if ( ra == 0 ) return true; if ( a == max_attempts ) return false; double ceiling = std:: min ( cap, base * std:: pow ( 2.0, a - 1 )); double d = std:: uniform_real_distribution < double > ( 0.0, ceiling )( rng ); if ( honor_ra ) d += ra * 1000.0; // the Retry-After variant, below sleep_ms ( d ); } Enter fullscreen mode Exit fullscreen mode I expected this to win outright. It did not, and this was the most useful surprise of the run. Full jitter cut the 95th percentile from 16.1 s to 10.5 s: most calls finished much sooner, and you can see it in the replay at the top, where it has 80 answers at the 6.4 second mark against 57 for the herd.

But the last call landed at 17.1 s (the herd: 16.6), and it sent 408 requests, 9% more. With a random delay every retry comes back sooner than the fixed one would (half of them in less than half the time), finds an empty bucket and burns a request. Against a token bucket, a smarter guess still spends most of its requests guessing.

Brooker's post measured clients competing for one contended resource, where full jitter cut both the work and the time. A rate limiter is a slightly different animal: it tells you the answer if you listen.

A 429 from a real API usually says how long to wait. Anthropic's docs: "When the response has a retry-after header, wait that many seconds before retrying" ( rate limits ). MDN's page on 429 says the same for HTTP in general. llm-retry's LLMError has no field for it, so the header is read by nobody.

Honoring it, with full jitter added on top so the clients do not all come back on the same whole second: 11.8 s to the last answer (10.2 to 14.5 across the 3 runs), 313 requests, p95 9.1 s. Better on every number than both backoff formulas. Still 213 wasted requests, because retry-after is in whole seconds and 80 clients cannot all have the next token.

If you know your limit (and for an LLM API you do: it is on your console's limits page), the cheapest 429 is the one you never send. A client-side limiter hands out send slots at the rate the provider refills, before the request leaves your process:

// herd.cpp: shared by all 100 clients, paced at the provider's 10/s struct ClientLimiter { double rate, next = 100; std:: mutex m; // first paced send at 100 ms explicit ClientLimiter ( double r ): rate ( r ) {} double reserve ( double burst_until ) { // returns ms to wait std:: lock_guard < std:: mutex > lk ( m ); double t = now_ms (); if ( next < t ) next = t; double slot = next; next += 1000.0 / rate; ( void ) burst_until; return slot - t; } }; Enter fullscreen mode Exit fullscreen mode Result, all three runs: 100 of 100, 100 requests, 0 429s, last answer at 8.0 s. That is the floor. The bottom panel of the waves chart is what that looks like from the provider's side: one burst, then a steady drip exactly on the refill line.

The retry loop is still there behind it, for the 429s you did not predict (another process on the same key, a limit change), but here it never fired.

In a real app the limiter goes wherever all your calls already pass through: one per API key, shared across threads or workers. If you run a proxy for LLM traffic, that is the natural home. My Rust one, tokio-prompt-orchestrator, does dedup and a circuit breaker there; in the LLM proxy benchmark it turned 200 duplicate calls into 1, which is the other cheap way to avoid a 429: do not send the same call twice.

Retry policy is half "how long to wait" and half "is this even worth retrying". I ran one failing call per error type through llm-retry's defaults:

probes.cpp against the unmodified llm_retry.hpp (commit abd6a3e), Oct 18 2026, 7:13 PM ET.

Three of those lines are bugs, and one of them matters a lot for anyone calling Claude:

And one 429 you should not retry at all. Anthropic's errors page says a 429 caused by your tier's monthly spend cap "has no retry-after header and keeps failing until access resumes". So "429 without a retry-after" is a different situation from "429 with one", and a policy that treats them the same just spends its attempts and its users' time. Here is the whole table:

Meanings from Anthropic's errors and rate limit docs (checked Oct 18 2026); right column measured with probes.cpp.

A circuit breaker (Martin Fowler's write-up is the classic) stops calling a provider that keeps failing. After N failures it "opens" and fails fast; after a cool-down it goes "half-open" and lets one test call through; that call decides whether to close again or reopen. llm-retry's version:

// include/llm_retry.hpp @ abd6a3e, CircuitBreaker::call if ( state_ == CircuitState:: Open ) { auto now = std:: chrono:: steady_clock:: now (); double secs = std:: chrono:: duration < double > ( now - last_failure_time_ ). count (); if ( secs >= config_. timeout_seconds ) { state_ = CircuitState:: HalfOpen; //...and nothing stops the next caller } else { throw std:: runtime_error ( "CircuitBreaker[" + name_ + "]: circuit is Open" ); } } Enter fullscreen mode Exit fullscreen mode Nothing limits half-open to one call, and closing again needs the success rate since the last reset to reach 80%, with the old failures still counted. I pushed on it three ways:

The CircuitBreaker in include/llm_retry.hpp (abd6a3e) and the three probes, Oct 18 2026, 7:13 PM ET.

When the cool-down ended with the provider still down, 50 concurrent calls all went through to it, each waiting out its own failure. When the provider was fully back, the breaker needed 20 straight successes before it admitted it (5 old failures, so 25 calls to reach 80%). And against a provider that came back 30% flaky, it sat in HalfOpen for all 1,000 calls: never closed, never reopened, so its state stopped meaning anything.

The fix is small: allow one trial call at a time in half-open, close on its success and clear the counters, reopen on its failure.

// probes2.cpp: patched half-open if ( state_ == State:: HalfOpen ) { if ( trial_in_flight_ ) throw std:: runtime_error ( "circuit half-open, trial in flight" ); trial_in_flight_ = trial = true; } // on success: if (trial) { state_ = State::Closed; trial_in_flight_ = false; } // on failure: if (trial || consecutive_ >= threshold_) { state_ = State::Open;... } Enter fullscreen mode Exit fullscreen mode Same three probes on the patched version: 1 of 50 calls reached the dead provider (49 failed fast), 1 success closed it, and the 30% flaky provider kept it Closed for all 1,000 calls (284 failures, never 5 in a row), which is honest: a provider that answers 72% of the time is up, and that is a job for retries, not the breaker. These fixes are not in the public repo yet as of October 18; they ship there next.

For the dollar side of a fan-out like this (what 100 parallel calls cost per model before any retry), the LLM API cost calculator does the per-call math.

Everything is three small C++ files, built with MSVC 19.44 ( cl /std:c++17 /O2 /EHsc ) on an i7-13700KF and run on October 18, 2026, between 7:13 and 7:19 PM Eastern. herd.cpp (the provider, the 100 clients, all seven policies; one arrivals CSV and one results CSV per run, 21 runs), probes.cpp (the error-type and breaker probes against the unmodified llm_retry.hpp ), and probes2.cpp (the patched breaker). Wall-clock sleeps are real, so a run takes as long as it says: the 8-try policies take about 17 seconds each, the whole set about 3 minutes. Change the bucket to your own limits (Anthropic's per-tier numbers are on the rate limits page ) and you will get your own floor to measure against.

One caveat: the provider here is a simulation of the documented algorithm, not a real API, and real latency would stretch every number a little. My bet is that the shape holds: fixed-delay retries come in waves, the waves waste capacity, and the provider's own hint beats your guess.

What I would like to know: does anyone run a shared client-side limiter in front of their LLM calls in production, and how do you keep it in sync when the provider changes your limits? That is the part I have not solved.

If you are adding AI to an app and want the boring parts done right (timeouts, retries, rate limits, budgets, evals), that is what I build at a fixed price.