Exponential Backoff with Jitter Still Fails 64%: 100 LLM Calls Tested and Root Cause Analysis

A seemingly standard retry strategy collapsed in the face of 100 concurrent LLM requests. The author of the C++ library llm-retry ran a stress test with his own tool: 100 calls simultaneously hitting a rate limiter that refills 10 tokens per second, and the default exponential backoff (3 retries, ±10% jitter) resulted in 64 calls failing completely. Worse, to serve 36 successful requests, the server was forced to reject requests 255 times—a 2.55x amplification.

What went wrong? Can adding more retries fix it? The author further tested full jitter, honoring the Retry-After header, and a client-side rate limiter, and in the process uncovered three bugs in the library itself. This detailed experimental report is valuable for any developer calling LLM APIs.

Experiment Setup: 100 Calls, One Token Bucket

The test simulated Anthropic API's rate limiting mechanism: token bucket algorithm, capacity 20, refilling 10 tokens per second. Each request consumes one token; when the bucket is empty, it returns 429 with an integer-second retry-after header (compliant with RFC 9110). 100 threads simultaneously initiate calls, and the theoretical optimal completion time is 8.0 seconds—20 burst tokens are used at 0 seconds, then the remaining 80 are processed at 10 per second. All strategies use this as the performance floor.

llm-retry is a single-header C++ library providing with_retry, with_failover, and CircuitBreaker. The author admits that previously it was only tested with the "one call fails twice then succeeds" scenario, and never validated concurrent bursts—which is exactly when retry mechanisms truly matter.

Token Bucket Algorithm is one of the most common implementations of rate limiters. It maintains a bucket with capacity B, adding tokens at a fixed rate r, discarding new tokens when the bucket is full. Each arriving request must take a token from the bucket; if the bucket is empty, the request is rejected (usually returning 429). Its key feature is allowing burst traffic: when the bucket is full, up to B requests can pass at once, after which the rate is limited to r. This contrasts with the leaky bucket algorithm (which enforces a constant output rate and disallows bursts). LLM APIs like Anthropic and OpenAI commonly use token buckets or their variants to balance burst tolerance and average throughput. In this experiment, capacity 20 and refill rate 10/second mean the theoretical optimal completion time = burst consumption time + remaining requests processed at rate, i.e., 20 used at 0 seconds, remaining 80 processed at 10 per second, totaling 8 seconds. Understanding this is the baseline for evaluating the efficiency of all subsequent retry strategies.

Three Retries Are Far from Enough for Bursts

Without retries, 20 calls get burst tokens and 80 fail immediately. With llm-retry's default configuration (3 attempts), 36 succeed; retries bought 16 more answers but subjected the server to 155 additional requests. For comparison, the author ported Anthropic's official Python SDK retry logic (default 2 retries, starting at 0.5s doubling to 8s, 75%-100% jitter, honoring retry-after header), which resulted in only 40 successes.

"This is not a bug in the SDK," the author emphasizes. "Two retries are designed for occasional failures, and all default retry strategies are built for a single unstable call, not for 100 calls competing for the same scarce resource."

After raising max_attempts to 8, llm-retry let all 100 calls through, but took 16.6 seconds, more than twice the theoretical floor, and sent 375 requests. The reason lies in the pattern of requests arriving at the server.

Why Requests Arrive in Waves: ±10% Is Not Real Jitter

The core issue is the delay calculation: after each failure, the client waits 500ms * 2^n * random(0.9, 1.1). All clients that failed at 0 seconds wait 450-550 milliseconds, so 80 retries arrive within the same 100-millisecond window, while the bucket has only refilled about 5 tokens. 5 succeed, 75 fail again, then all wait 0.9-1.1 seconds... forming waves.

During the quiet periods between waves, the token bucket refills but no one is requesting, wasting capacity. "Backoff itself only spaces out the clusters; it doesn't disperse them," the author notes, citing AWS architect Marc Brooker's classic analysis.

Jitter is a technique of adding randomness to retry delays to prevent multiple clients from retrying at the same moment, causing a "thundering herd" or synchronized waves. Common jitter strategies include: fixed jitter (adding or subtracting a small percentage to a fixed delay, e.g., ±10%), full jitter (uniformly random between 0 and the exponential cap), equal jitter (random between half the delay and the full delay), and decorrelated jitter (adding a fixed random amount on top of exponential backoff). AWS architect Marc Brooker recommends full jitter in his analysis because it maximally disperses retry times and reduces peak load. However, full jitter does not reduce the total number of retries, only changes the time distribution. For stateful rate limiters like token buckets, retrying too early still hits an empty bucket and wastes requests. Therefore, jitter needs to be combined with respecting server feedback (like Retry-After) or client-side rate limiting to achieve efficient retries.

Full Jitter Improves the Tail but Doesn't Reduce Total Volume

The textbook fix is "full jitter": uniformly random delay between 0 and the exponential cap. The author expected this to win hands down, but the result was unexpected. Full jitter reduced the 95th percentile latency from 16.1 seconds to 10.5 seconds, with most calls completing faster, but the last call landed at 17.1 seconds (fixed delay strategy was 16.6 seconds), and sent 408 requests, 9% more.

The reason: random delays make each retry return earlier than fixed delays (half the retries come back in less than half the time), hitting an empty bucket and wasting another request. "Against a token bucket, even smarter guesses still waste most requests guessing."

Retry-After: The Server Already Told You When to Retry

Real API 429 responses usually include a retry-after header telling the client how long to wait. Anthropic's documentation explicitly requires honoring this header. But llm-retry's LLMError doesn't have this field at all.

On top of honoring retry-after, adding full jitter (to avoid clients returning in the same integer second), the last call completed at 11.8 seconds, sending 313 requests, with p95 of 9.1 seconds—better than both backoff formulas on every metric. But there were still 213 wasted, because retry-after is in integer seconds, and 80 clients can't all get the next token.

Retry-After is an HTTP response header (defined in RFC 9110) used in responses like 429 (Too Many Requests) or 503 (Service Unavailable) to tell the client how long to wait before retrying. Its value can be seconds (e.g., Retry-After: 120) or an HTTP date. LLM APIs like Anthropic and OpenAI typically return integer-second Retry-After in rate limit responses, and clients should prioritize honoring this header rather than guessing backoff times themselves. However, there are two pitfalls in practice: first, Retry-After may have coarse precision (integer seconds), and many clients may still return within the same second, requiring added random dispersion; second, not all 429s carry Retry-After—for example, a 429 triggered by monthly spending limits may not have this header and will continue failing until the quota resets. Therefore, distinguishing between "429 with Retry-After" (retryable) and "429 without" (may need alerting) is crucial.

The Real Solution: Throttle on the Client Side

If you know your own limits (LLM API limits are right there on the console page), the cheapest 429 is the one never sent. A client-side rate limiter allocates send slots at the server's refill rate before requests leave the process:

struct ClientLimiter {
    double rate, next = 100;
    std::mutex m;
    double reserve(double burst_until) {
        std::lock_guard<std::mutex> lk(m);
        double t = now_ms();
        if (next < t) next = t;
        double slot = next;
        next += 1000.0 / rate;
        return slot - t;
    }
};

The result was completely consistent across three runs: all 100 succeeded, 100 requests, 0 429s, last answer at 8.0 seconds—exactly hitting the theoretical floor. The retry loop remains for handling unforeseen 429s (like other processes on the same key), but never triggered in this test.

What to Retry (and What llm-retry Got Wrong)

A retry strategy is half "how long to wait" and half "is it worth retrying." The author ran a probe test on each error type with the default configuration and found three bugs:

• 529 is never retried. Anthropic's 529 overloaded_error indicates the API is temporarily overloaded due to high traffic—exactly the reason backoff mechanisms exist—yet it's not in the default retry_on_http_codes list. 408 (request timeout) is also missing.
• Own exceptions are retried. A std::runtime_error from JSON parsing in a callback falls into catch (...), retried 3 times without jitter, wasting 1.5 seconds on a bug that will inevitably fail again.
• with_failover masks bad requests. A 400 error (prompt too long, malformed JSON) silently returns a fallback model's answer, turning a bug into an unnoticed quality degradation.

There's also a 429 that shouldn't be retried: Anthropic's documentation states that a 429 triggered by monthly spending limits has no retry-after header and will continue failing until the quota resets. "429 without retry-after" and "429 with retry-after" are different situations; treating them the same only wastes attempts and user time.

The Circuit Breaker's Half-Open State Is Useless

A circuit breaker "opens" after consecutive failures, and after a cooldown enters "half-open" state, which should let one test call through. But llm-retry's implementation lacks this restriction. Three probe results:

• Provider still down: after cooldown, all 50 concurrent calls hit it, each waiting to fail.
• Provider fully recovered: needs 20 consecutive successes to switch back to closed.
• Provider with 30% flakiness: after 1000 calls, the circuit breaker stays half-open, neither closing nor reopening, making the state meaningless.

The fix is small: allow only one probe call in half-open, close and reset counters on success, reopen on failure. After patching, the same three probes: only 1 of 50 calls hits the down service (49 fast-fail), 1 success closes it, and the 30% flaky provider stays closed (284 failures out of 1000 calls, never 5 consecutive).

Circuit Breaker Pattern is a fault-tolerance mechanism that prevents the system from continuously calling downstream services during failures. It has three states: closed (normal calls), open (fast-fail directly without calling downstream), half-open (allows a limited number of probe calls to detect if downstream has recovered). In standard implementations, the half-open state should only allow one probe request: if successful, reset to closed and clear failure count; if failed, reopen and reset the timer. This prevents flooding a still-unavailable service. llm-retry's flaw is that the half-open state doesn't limit concurrent probe calls, causing all waiting calls to rush to the unrecovered service after cooldown, losing the purpose of the circuit breaker. Correct half-open logic is key to circuit breaker effectiveness and a common topic in distributed systems resilience engineering.

Do This in Your Project

1. Use full jitter, not ±10%. delay = random(0, min(cap, base * 2^attempt)), which in this test free-improved p95 from 16.1s to 10.5s.
2. Read and honor retry-after, plus a bit of random dispersion. It beats both formulas: 11.8s vs 16.6 and 17.1s.
3. A 429 without retry-after may be a spending limit, which will keep failing until reset. Alert, don't loop.
4. Retry 408, 409, 429, 5xx, and 529; never retry self-inflicted 4xx and own exceptions. If your retry wrapper has catch (...), it's retrying bugs.
5. Throttle ahead if you know your limits. One rate limiter per API key, shared by all workers. This is the only strategy that hits the 8.0s floor with zero wasted requests.
6. Set a retry budget per client. Google SRE handbook uses 3 attempts plus a 10% retry budget, reducing load growth from nearly 3x to 1.1x.
7. Half-open means one probe call. Test your circuit breaker with 50 concurrent calls—if more than one reaches the provider, it's not a circuit breaker.
8. Test bursts, not occasional failures. The author's library's own example (one call fails twice) passed for seven months, while the 100-call scenario had a 64% failure rate.

Data and Reproduction

All code is three small C++ files, compiled with MSVC 19.44 (/std:c++17 /O2 /EHsc), running on an i7-13700KF, with timestamps from the evening of October 18. herd.cpp contains the provider, 100 clients, and all seven strategies, generating arrivals and results CSVs per run, 21 runs total; probes.cpp and probes2.cpp test the unmodified and patched circuit breakers respectively. Due to real sleeps, the entire test takes about 3 minutes.

An important caveat: the provider here is a simulation of the documented algorithm, not the real API; real latency would slightly stretch all numbers. The author bets the shape holds: fixed-delay retries arrive in waves, waves waste capacity, and the provider's own hints beat your guesses.

His open question: has anyone run a shared client-side rate limiter for LLM calls in production? How do you stay in sync when the provider adjusts limits?

One-line Summary

100 concurrent LLM calls tested: default exponential backoff with jitter fails 64%, client-side rate limiting is the only optimal solution.

Paragraph Summary

The article stress-tests 100 concurrent LLM calls by simulating Anthropic's rate limiter (token bucket, capacity 20, 10 tokens/sec), finding that llm-retry's default 3-retry exponential backoff with ±10% jitter causes 64 failures, with the server rejecting 255 requests to serve 36. ±10% jitter can't disperse requests, causing wave arrivals that waste tokens. Full jitter reduces p95 from 16.1s to 10.5s but increases total requests by 9%, with the last completion slightly higher. Honoring Retry-After with random dispersion reduces last completion to 11.8s. A client-side rate limiter completes all 100 calls in 8.0s with zero 429s, hitting the theoretical floor. The article also exposes three llm-retry bugs (no retry for 529/408, retrying own exceptions, with_failover masking 400 errors) and the circuit breaker's half-open state failing to limit probe calls, with eight practical recommendations.