Rate limits for agent fleets

We had 20 agents hitting 429s, so we raised max backoff from 30s to 120s. Throughput dropped again. We added full jitter. The 429s kept coming in waves, exactly 90 seconds apart. Ninety seconds wasn't our retry interval. It was our agents' read → think → edit → test loop. The agents weren't retrying in sync. They were working in sync, and no retry policy can fix that.

I caught it on a Tuesday afternoon, looking at the rate-limit panel. Flat. Tall red bar. Flat. Another tall red bar. The gaps were regular enough to set a metronome by. Our backoff was full-jitter exponential, taken straight from the AWS architecture blog post you've also read. Jitter is supposed to turn waves into noise. It didn't. So I overlaid the agents' turn timestamps on the 429 timestamps. The red bars landed right where most of the fleet finished running tests and sent the next model call.

Maybe you've gone from one coding agent to a fleet on a single org API key, and each agent you add lowers your merged-PR throughput. This post is for you. The fix isn't a better retry policy. Put one component in charge of the quota, so agents stop discovering the limit by running into it.

The agents weren't retrying in sync. They were working in sync.

Here's how it happens. One monorepo push triggers CI. CI fans out 20 agents: lint fixes, test repairs, a refactor, a planner, a reviewer. They all start within a few seconds of each other, and they all run the same loop: read files, call the model, apply an edit, run tests, call the model again. Test suites in one repo take about the same time, so the loops stay in phase. Two or three turns in, you have 20 agents whose model calls land in the same few seconds, every ~90 seconds.

Jitter only acts on retries. The workload already synchronizes the first attempt of every turn, and your jitter code never sees that attempt. A longer max backoff makes things worse. Agents sit idle longer and finish their retries. Then they join the next wave anyway, because their next turn is still on the 90-second cycle.

So you have two separate failures, and backoff fixes neither:

• ▹Correlated workload. The agents share a trigger (one push) and a tool-call rhythm (the same test suite). Their demand is bursty because it's correlated, and randomizing retry timing can't decorrelate it.
• ▹No shared state. Each agent learns about the limit by itself, from a 429. With twenty agents you get twenty separate discoveries of the same fact, and each one costs a failed call. Then the next wave starts from zero knowledge again.

Requests per minute is the wrong unit

Our first try at coordination was a shared RPM counter. It failed, because agent requests aren't the same size. In our fleet, a turn on a repo-wide refactor sends around 80k input tokens: the plan, a dozen files, the test output. A lint-fix turn sends about 2k. That's a 40x gap, and RPM counts each one as 1.

So one greedy refactor agent drains the token budget while the RPM bucket still shows plenty of room. Four of those turns in the same window and the lint fixers start getting 429s on 2k-token requests, while your RPM dashboard looks fine. Providers know this. Anthropic, for example, enforces input tokens per minute, output tokens per minute and requests per minute as separate limits. The one you hit first is the one that matters, and for coding agents it's almost always input tokens.

Prompt caching makes this harder. On Anthropic's API, cache reads are billed at a fraction of the normal input price. On most current models they also don't count against the input-token rate limit. That's great while the cache is warm. But the default cache lifetime is five minutes. Once an agent's cache expires, its 80k-token prompt counts the full 80k against the limit again. A cache miss is a rate-limit spike, and you have to budget for it. Remember this, because the obvious fix is to make agents wait, and waiting is exactly what lets caches expire.

A 429 in an agent costs a plan, not a request

In a web service, a 429 costs you one retried HTTP call. In a coding agent it usually costs a lot more. Most agent harnesses treat a long failure as a broken turn. The agent gives up, re-reads files to rebuild context, re-runs the tests to see where it stands, and re-plans. When we traced it, recovering from one rate-limited call cost roughly 5 to 20 times the tokens of the call that failed.

That's why the storm gets worse on its own. Each 429 creates extra token demand from the same agent in the next window, and that demand is synchronized too. Backoff tunes the retry. It does nothing about the re-plan behind the retry, and the re-plan is where most of the tokens go.

Build step 1: one owner of the quota

Run one coordinator that owns all the buckets. Ours is a small service in front of Redis. The bucket logic is a Lua script, so check-and-take is atomic. If your orchestrator runs as one process, an in-memory struct behind a mutex works too. The design matters more than where it lives.

• ▹Three buckets: input TPM, output TPM, RPM. Use your tier's real limits, not the numbers you remember. Read the rate-limit response headers (Anthropic sends remaining and reset values per limit) and resync whenever they disagree with your model.
• ▹Refill continuously at capacity / 60 per second. If you reset at the minute boundary, you've built another synchronized burst at :00.
• ▹Safety margin: start the buckets at 85% of the real limit. The other 15% absorbs estimate error and anything else using the key. Step 5 covers how the margin moves over time.
• ▹Every model call in the fleet goes through the coordinator. One agent that skips it, like a 'quick' script with the raw key, breaks the accounting for everyone.

Build step 2: the lease protocol

Agents don't just ask whether they may send. Before the call, they reserve a specific amount of capacity. After it, they report what they actually used.

The agent makes the estimate. Input is the prompt tokens counted locally. Use a token-counting endpoint or a tokenizer, and don't guess from character count. If the agent's last call was long enough ago that its cache has probably expired, charge the full cached prefix as uncached input. Output is max_tokens. That's pessimistic, but the refund corrects it afterwards.

The coordinator gives one of three answers: GRANT (send now), QUEUED (you're in line, with an ETA) or REJECT (come back at retry_at). The agent knows where it stands before the call, so it doesn't have to learn from a 429.

# Coordinator. Buckets refill continuously; every function runs atomically (Lua in Redis, or under one lock).
MARGIN, LEASE_TTL, MAX_QUEUE_WAIT = 0.85, 120, 60

def request_lease(agent_id, est_in, est_out, weight):
    refill_all(capacity_factor=MARGIN)
    fits = itpm.avail >= est_in and otpm.avail >= est_out and rpm.avail >= 1
    if fits and not queue.has_ahead_of(weight, est_in):
        itpm.take(est_in); otpm.take(est_out); rpm.take(1)
        lease = Lease(new_id(), agent_id, est_in, est_out, expires=now() + LEASE_TTL)
        active[lease.id] = lease
        return Grant(lease.id)
    eta = queue.eta_for(est_in, est_out, weight)   # from refill rate and the requests ahead of it
    if eta > MAX_QUEUE_WAIT:
        return Reject(retry_at=now() + eta)
    queue.push(agent_id, est_in, est_out, weight)
    return Queued(eta)

def settle(lease_id, actual_in, actual_out, got_429=False):
    lease = active.pop(lease_id)
    itpm.adjust(lease.est_in - actual_in)    # positive = refund, negative = charge
    otpm.adjust(lease.est_out - actual_out)
    metrics.estimate_error(lease.agent_id, actual_in, lease.est_in)
    if got_429:
        shrink_margin()                       # see step 5
    drain_queue()                             # grant queued leases, highest priority first

def reap_expired():                           # agent crashed mid-call
    for lease in active.expired(now()):
        active.pop(lease.id)                  # no refund: assume the tokens were spent
        drain_queue()

Two details cost us a week each. First, don't refund expired leases. A crashed agent may well have spent the tokens, and if you refund them you've overbooked. Second, allow negative charges. A lease that underestimated by 30k tokens has to show up as debt in the bucket right away, or the next three grants will cause a 429.

Build step 3: weight by the dependency DAG, not equal shares

Splitting the quota evenly across 20 agents looks fair, but it's wrong. A planner whose output unblocks six workers is worth more per token than a leaf agent fixing import order. If both wait 30 seconds, the planner's wait delays seven agents. The leaf's wait delays one.

So the queue is ordered by weight, and the weight comes from the task graph your orchestrator already has:

def weight(agent):
    base = {'planner': 3.0, 'reviewer': 2.0, 'worker': 1.0}[agent.role]
    unblocks = len(orchestrator.downstream_waiting_on(agent.task))
    w = base * (1 + 0.5 * unblocks)
    w *= 0.5 ** agent.repeat_failures       # same failing test, same diff hash: decay
    return max(w, 0.1)

# Queue ordering: weighted fair queueing, not strict priority, so leaf agents still make progress.
# virtual_finish = max(now_vtime, agent.last_vfinish) + est_tokens / weight

• ▹Lending. Blocked or idle agents don't hold a reservation, and nothing is pre-allocated, so their share goes back into the pool automatically. Weights only decide who goes first in the queue.
• ▹Decay. An agent that has hit the same failing test three times in a row with near-identical diffs is in a loop. Halve its weight on each repeat. It keeps running, but it stops taking capacity from agents that are making progress. That change alone won back a noticeable share of our wasted tokens.
• ▹Fairness floor: use weighted fair queueing, not strict priority, so a busy planner can't starve the leaf agents indefinitely.

A quick note from my research side. This is task allocation, and multi-agent systems research has studied it for decades. Contract-net protocols and market-based allocation both deal with the same question: who should get a scarce resource when agents value it differently? At 20 agents you don't need an auction, because a weighted queue gets you most of the benefit. But if you're heading toward 200 agents across teams sharing one key, read up on market mechanisms before you invent your own.

Build step 4: checkpoint before you wait

Leases fix the 429. They only fix the re-plan if the agent can survive the wait. Suppose a QUEUED response causes a timeout in your harness, and the timeout means 'start the turn over'. Then you've just moved the storm somewhere else.

Make each agent turn a resumable unit of work. Before an agent waits on a queued or rejected lease, it writes down its plan state:

• ▹The goal, and the current step of the plan
• ▹Files read, with content hashes
• ▹Decisions already made, each with a one-line reason
• ▹The exact next call it was about to make (messages plus tool state)

On resume, it checks the file hashes and re-reads only the files that changed. If nothing changed, it sends the call it had ready. Remember the cache warning: if the wait outlasted the cache lifetime, the estimate has to include a cache miss. The coordinator should know this too. When an agent with a large, warm cache gets close to expiry, give it a small priority bump. Letting that cache lapse costs the bucket far more than serving the agent now.

Build step 5: keep backoff, but demote it

Backoff stays in the design as a fallback. A 429 on a granted lease means the coordinator was wrong. Either the estimate drifted, or something outside the fleet used the key (another team, a notebook, a forgotten cron job). When that happens:

• ▹The agent backs off with full-jitter exponential (base 1s, cap 30s; you don't need 120s anymore) and honors retry-after when the provider sends it.
• ▹It reports the 429 to the coordinator in settle().
• ▹The coordinator cuts the margin by 5 points, down to a floor of about 60%, then lets it creep back 1 point every few clean minutes. It's the same instinct as TCP's AIMD: cut fast, recover slowly. TCP's cut is multiplicative and a fixed 5-point step is a simplification, but at these margins it works fine.

If the margin keeps sitting near the floor, the coordinator is almost never the problem. Someone outside it is using the key. Find them, then either route them through the coordinator or give them their own key.

What changed, and what didn't

I'll give the direction and rough size of each change, not exact percentages. One fleet, one repo and a few weeks of traffic won't carry over cleanly to your setup, so measure your own. These are the four numbers I'd track, and what ours did:

• ▹429 rate. The waves went away. We still see the occasional single 429, nearly always on a granted lease with a bad estimate or from traffic outside the coordinator. The 90-second bars are gone from the panel.
• ▹Total tokens per merged PR. This was the biggest win, and it came from fewer re-plans, not fewer retries. Removing the recovery work after each 429 accounted for most of it. Loop decay accounted for the rest.
• ▹p50 / p95 time to finish a task. p95 improved a lot, because tasks no longer stall behind a storm. p50 got slightly worse for leaf agents. They now wait in a queue, where before they sometimes got lucky. We made that trade-off on purpose, but the cost is real, and the people who own the lint-fix agents noticed.
• ▹Critical-path wait time, meaning the time blocked agents spent waiting on an upstream agent's model call. This dropped the most, which is exactly what DAG weighting is for.

Some things didn't improve. The coordinator is now a single point of failure, so it needs a fail-open mode (fall back to per-agent backoff and alert). Output-token estimates are still poor, because max_tokens is a loose upper bound, so we over-reserve output and refund later. And none of this raises your actual limit. If the fleet needs more tokens per minute than your tier allows, the coordinator makes the wait orderly and cheaper. It can't remove the wait.

Starter checklist

• ▹Unit = tokens. Track input TPM, output TPM and RPM as separate buckets. RPM matters least of the three.
• ▹One owner of the quota. Every call goes through the coordinator, with atomic check-and-take (Lua in Redis is enough).
• ▹Start at 85% of the real limit. Shrink by 5 points on any 429 against a granted lease, recover slowly, floor around 60%.
• ▹Reserve, then reconcile: count prompt tokens locally, add max_tokens, add a cache-miss penalty if the cache is probably cold, refund or charge on settle. Never refund expired leases.
• ▹Weight by critical path: planner 3, reviewer 2, worker 1, multiplied by the number of downstream tasks blocked. Halve the weight on each repeated identical failure. Schedule with weighted fair queueing.
• ▹Checkpoint before waiting. Turns are resumable, files get hash-checked on resume, and a queued lease never forces a re-plan.
• ▹Backoff only as a fallback: full jitter, 30s cap, honor retry-after, report every 429 to the coordinator.
• ▹Alert when lease-estimate error stays above 20%. That means your estimator is off, and every other part of this design depends on it.

If you keep one test from this post, make it this one. Overlay your 429 timestamps on your agents' turn timestamps. If the waves line up with the work instead of the retries, no backoff setting will fix it. You need one component that owns the quota.