Agent retry storms: when exponential backoff meets shared state

Most agent retry advice stops at exponential backoff. In a multi-agent pipeline that runs every 15 minutes, that advice is dangerous. We learned this when a downstream API started returning 502s on a Friday afternoon and three sibling agents each retried the same job with the same backoff curve. The result was a synchronised retry storm: 12 calls per minute hitting an already-degraded service, and roughly €40 spent on duplicate tool calls before anyone noticed.

What actually went wrong

Our agents share a Postgres-backed job queue. Each agent pulls pending jobs, executes them, and on failure schedules a retry with a base delay of 2^n seconds. The problem was not the formula. The problem was that all three agents were started by the same cron trigger, so their first attempt landed within the same second. Their retry timers then drifted by milliseconds, not minutes, so every subsequent attempt also collided. Classic thundering herd, but dressed up as a retry policy.

The fix in three parts

First, we added jitter on every retry delay, capped at plus or minus 30 percent of the base value. This alone cut peak concurrency from 12 to 4 calls per minute. Second, we introduced a per-job retry token stored in the queue row. When an agent claims a job, it writes the next allowed execution timestamp; another agent that picks the job up before that timestamp is forced to requeue with a minimum wait. Third, we added a circuit breaker per external dependency, so after 5 consecutive failures the agent stops scheduling retries for 10 minutes and surfaces a structured alert instead.

Trade-offs we accepted

Jitter adds variance to latency. A job that would have retried in 4 seconds might now retry in 5.4 or 3.1. For our use case, that is fine. The retry token costs one extra write per claim, which added about 3 percent to queue throughput pressure. The circuit breaker is the most opinionated piece: it assumes a single shared dependency, which is true for us but would need partitioning if you fan out to many vendors. None of these changes touched the agent logic itself, which matters because the failure was in the orchestration layer, not the reasoning layer.

Numbers after two weeks in production

Retry storms went from one per week to zero. Average spend on failed-job retries dropped from roughly €18 per incident to under €2. Mean time to recovery for the downstream API stayed the same, but the agents stopped making it worse. The biggest surprise was that the structured alert from the circuit breaker caught a vendor outage two days before their status page updated.

Takeaway

If your agents share a queue or a cron, do not trust exponential backoff alone. Add jitter, add a per-job retry token, and add a dependency-level circuit breaker. The reasoning in your agent is not where production incidents live. The scheduling around it is.