Retrying Agent Tool Calls Without Executing the Same Action Twice

Agents call tools that change the world: issue a refund, send an email, create a ticket, write a row. Those calls cross networks that drop replies and to services that are sometimes slow. When a call times out, the agent runtime retries; when retries run out, the model sees an error and often asks for the same action again; when a worker crashes, a durable runtime replays the last step. Every one of those repeats is reasonable on its own. Together they mean a customer can receive the same refund twice, and nobody wrote a bug.

This guide explains why a timeout is not a failure, the probability arithmetic that turns a 2% lost-reply rate into dozens of duplicates per thousand actions, how idempotency keys work end to end, and the three decisions that make or break them: what the key identifies, where it is generated, and how long the server remembers it. It also covers the in-progress case, key stores in Redis and Postgres, MCP tool annotations and how to detect duplicates in production. The embedded lab sends thousands of synthetic tool calls through a lossy network so you can watch each choice remove, or fail to remove, duplicate side effects.

A timeout tells you nothing about whether the action ran

A remote call has three outcomes from the caller's point of view: success, a definite failure (the request was rejected or never connected), and unknown. Unknown is what you get when the request reached the server, the server did the work, and the reply never arrived: the response was lost, the connection reset, or the client timeout fired while the server was still committing. The caller cannot distinguish "never ran" from "ran, reply lost" without asking the server.

How often is the outcome unknown? Model the service latency as lognormal with a median of 300 ms and a log-standard deviation of 0.6, and the client timeout at 1,000 ms. The chance a call outlasts the timeout is P(Z > ln(1000/300) / 0.6) = P(Z > 2.0), about 2.2%. Add a 2% chance that a completed reply is lost on the way back and roughly 4% of first attempts end with an unknown outcome even though the action ran. Retry each of them blindly and you get about 40 duplicate side effects per thousand actions. The lab uses these illustrative constants and shows about 44 per thousand at its defaults; the exact value matters less than the order of magnitude: a few percent of ambiguous calls becomes a few percent of duplicated actions.

Slow dependencies make it dramatically worse. If the service slows down four times (median 1,200 ms) while the timeout stays at 600 ms, P(Z > ln(0.5) / 0.6) = P(Z > -1.16) is about 88%: most calls time out after doing their work, and a retry policy designed for rare hiccups now duplicates almost everything.

Three sources of repeats in an agent

Classic service-to-service retries have one source of repeats. Agents have three, and each defeats a different kind of deduplication:

Transport retries. The HTTP client or tool wrapper retries after a timeout or a 5xx. Same tool call, same arguments, seconds apart.
Model re-plans. Retries are exhausted, the tool returns an error to the model, and the model decides to call the tool again. This is a new tool call with a new call id, possibly with slightly different arguments, a few seconds or minutes later.
Replays after a crash. Durable agent runtimes checkpoint state between steps. If the worker dies after the side effect but before the checkpoint, the resumed run re-executes the step, sometimes many minutes later, and the model may generate the call afresh.

A deduplication scheme that only covers the first source looks correct in unit tests and still double-refunds in production. The second and third sources are why agent tool calls need more care than ordinary API clients.

How an idempotency key works end to end

An idempotency key is a client-chosen identifier for one logical operation, sent with the request. The server records the key before or atomically with performing the operation, together with the result. A later request with the same key does not perform the operation again; it receives the stored result. The protocol has a few moving parts that are easy to get wrong:

Atomic claim. The first request must claim the key atomically, for example SET key value NX EX ttl in Redis or an insert into a table with a unique constraint in Postgres. A read-then-write check races with concurrent retries.
In-progress state. A retry can arrive while the first request is still running. The server must not run it again and cannot return a result yet. The IETF Idempotency-Key header draft specifies 409 Conflict for this case; the client backs off and asks again.
Payload fingerprint. Store a hash of the request body with the key. The same key with a different payload is a client bug, and the draft specifies 422 Unprocessable Content rather than silently returning the old result.
Retention. The key is remembered for a fixed time. A repeat that arrives after expiry is treated as new. Payment APIs commonly keep keys for at least 24 hours; check the documentation of any API you call.

# server side: claim, execute once, store the result (Redis, illustrative)
def handle(req):
    key, fp = req.headers["Idempotency-Key"], sha256(canonical_json(req.body))
    claimed = redis.set(f"idem:{key}", json.dumps({"fp": fp, "state": "running"}),
                        nx=True, ex=TTL_SECONDS)
    if not claimed:
        rec = json.loads(redis.get(f"idem:{key}"))
        if rec["fp"] != fp:          return response(422, "key reused with another payload")
        if rec["state"] == "running": return response(409, "in progress, retry later")
        return response(rec["status"], rec["body"])          # replay the stored result
    status, body = do_side_effect(req.body)                   # runs at most once per key
    redis.set(f"idem:{key}", json.dumps({"fp": fp, "state": "done",
                                         "status": status, "body": body}), ex=TTL_SECONDS)
    return response(status, body)

Two refinements matter for real systems. If do_side_effect writes to the same database as the key table, put both in one transaction so a crash cannot leave the key claimed with no effect, or the effect done with no key. If the side effect is in another system, the claim needs a lease: a "running" record whose owner died must eventually expire or be reconciled, or the operation can never be retried.

The key must identify the intent, not the attempt

The most common bug is generating a fresh UUID inside the retry loop. Every attempt then carries a different key, and the server, correctly, treats each one as new. The key must be created once per logical operation and reused on every retry of it. That raises the real design question for agents: what is one logical operation?

Key scope	Derived from	Deduplicates	Misses
Per attempt	New UUID each try	Nothing	Everything: equivalent to no key
Per tool call	The model's tool-call id	Transport retries	Model re-plans and replays after a crash, which get new call ids
Per intent	Run id plus step, or business identifiers such as order id and action	Retries, re-plans and replays within retention	Repeats after the key expires; distinct operations that look the same

An intent key is best built from stable, non-generated values: the run id and step number persisted in the checkpoint, or the business identity of the operation such as refund:order-1042:line-3. Avoid hashing free text the model wrote, such as a memo field, because a re-plan will phrase it differently and produce a different key. The flip side is real: if a user genuinely asks for two identical refunds, an intent key built only from order and amount will merge them. Include whatever makes two legitimate operations distinct, such as the line item or a request number from the user's turn.

Where the key is generated matters as much as what it contains. Generate it in the runtime, persist it in the checkpoint before the call, and pass it to the tool out of band (a header or a reserved argument the model does not fill). Then a resumed run reads the same key from the checkpoint instead of minting a new one.

Retention, timeouts and backoff

Retention has to outlast the latest repeat you want to catch. Transport retries arrive within seconds, model re-plans within a minute or two, but a crash replay arrives whenever the run is resumed: after a deploy, a queue backlog or a manual restart, possibly many minutes later. In the lab, crashed runs resume 2 to 20 minutes later, so a 5-minute retention misses most replays while an hour catches them all.

Retention costs storage. A tool receiving 50 calls per second with one-hour retention holds 50 × 3,600 = 180,000 keys; at roughly 200 bytes per record (key, fingerprint, status and a small response) that is about 36 MB. With 24-hour retention it is 4.3 million keys and around 860 MB. These are calculated estimates, but they show why retention is a real trade-off for high-volume tools and why storing a large response body with each key is a bad idea.

Timeouts and backoff decide how many repeats you generate in the first place. A timeout shorter than the service's slow tail turns slow successes into ambiguous outcomes and sends retries into a service that is still working on the original, where they collect 409s and add load. A very long timeout makes every lost reply cost the full timeout before the retry starts. Exponential backoff with jitter spaces retries so that a brief outage does not become a synchronized retry storm. The right timeout sits above the p99 of healthy latency, and the retry count should be bounded so the total time still fits the agent's step deadline.

Knobs in real systems

Several standards and frameworks give you pieces of this, and none gives you all of it. Treat the list as pointers and check the current documentation for the versions you use:

HTTP semantics (RFC 9110) defines GET, PUT and DELETE as idempotent and POST as not. That is a property of the method's intended semantics, not a guarantee from any particular server.
The IETF Idempotency-Key header draft standardises the header name and the 409 and 422 behaviours described above. It is a draft, so check its status.
Payment APIs such as Stripe accept an idempotency key header on POST requests and document how long keys are kept; they are a good model for your own tools.
MCP tool annotations include idempotentHint, destructiveHint and readOnlyHint. They are hints for the client, useful for deciding which calls are safe to retry automatically, and the specification says clients should not rely on them from untrusted servers. They do not deduplicate anything by themselves.
Durable agent runtimes such as LangGraph replay a step after a failure from the last checkpoint. Their documentation advises making side-effecting work idempotent or isolating it so it is not repeated on resume; the key for that work should live in the checkpointed state.

A worked example: refunds at Belgavi's Book Store

Suppose a hypothetical support agent at Belgavi's Book Store can issue refunds through a refund_order tool. It handles 50 refund-type actions per second at peak (a deliberately large number for the arithmetic). The HTTP client retries three times with a 1,000 ms timeout and no key.

Using the latency model above, about 4% of first attempts end ambiguous, so roughly 2 refunds per second are executed twice: over 170,000 duplicates a day at that rate, each one a support ticket. Adding a key generated once per tool call removes the transport duplicates. The remaining duplicates come from re-plans: of the calls whose retries all fail with an unknown outcome, the model re-issues the refund about 60% of the time in the lab's model. Deriving the key from the run id and step stored in the checkpoint (or from order_id plus line item) removes those too. Finally, because workers can resume runs up to 20 minutes after a crash, retention goes from 5 minutes to 1 hour: 180,000 keys and tens of megabytes in Redis rather than the 4.3 million a 24-hour window would need.

All numbers are calculated from the illustrative model, not measured. The sequence of decisions is the transferable part: make retries safe with a key, make the key survive re-plans by deriving it from intent, and size retention from the latest repeat you expect.

Detecting duplicates in production

Duplicates are silent by construction: every individual call looks successful. Detect them with signals that compare intent with effect:

Dedup hit rate per tool: the share of requests answered from the key store. A sudden rise means retries or re-plans increased, often because a dependency slowed down.
409 in-progress rate: retries arriving while the original is running. High values mean the client timeout is shorter than the service latency.
422 fingerprint mismatches: the same key with different payloads, usually a key built from the wrong fields.
Effect reconciliation: a daily query for business-level duplicates (two refunds for the same order line within an hour), which catches what the key store missed, including repeats after expiry.
Unknown-outcome rate returned to the model: how often the agent is told "failed" when it may have succeeded. This is the input to re-plan duplicates.

When the agent does get an unknown outcome, give the model a way to resolve it rather than guess: a read tool that checks whether the refund exists, and an instruction to call it before retrying a write.

Common mistakes and how the lab maps to them

The recurring mistakes are: generating the key inside the retry loop; using the model's tool-call id as the key and assuming it covers re-plans; hashing model-written text into the key; a read-then-write key check that races with concurrent retries; retention shorter than the resume delay of the runtime; storing full responses with every key and running out of memory; and setting a short timeout on a slow tool so that most retries hit a call still in progress.

The lab's missions follow that list. Mission one starts with blind retries and asks you to remove duplicates without losing actions. Mission two turns on a slow downstream so the model re-issues calls, and shows why a per-call key is not enough. Mission three asks you to size retention for crash replays without blowing the key-store budget. Mission four combines a slow service and a lossy network and asks you to balance unknown outcomes, load on the struggling service and p95 latency at the same time.

Run the lab: Idempotency keys: retry the tool call, not the refund

The lab simulates 4,000 side-effecting tool calls from an agent. Each row in the picture is one action and each bar one attempt: green attempts got a reply, amber ones timed out, red ones lost the reply, and blue ones found the operation still in progress. White dots are executions on the server; pink dots are duplicate executions, and cyan rings are repeats the key store answered without executing. Start with no key, watch the pink dots appear, then load mission one.

Prefer a full-width view? Open the standalone lab. Your stars are saved in this browser and shown on the series hub.

What to do next

List every side-effecting tool your agents can call and mark which ones accept an idempotency key today.
Generate keys in the runtime from run id and step (or business identifiers), persist them in the checkpoint before the call, and pass them out of band.
Implement the server claim atomically (Redis SET NX or a unique constraint) with in-progress (409) and payload-mismatch (422) responses.
Set key retention longer than the longest resume delay of your runtime, and estimate key-store size as call rate times retention.
Set client timeouts above the healthy p99 latency, add exponential backoff with jitter, and bound total retry time by the step deadline.
Add a daily reconciliation query for business-level duplicates and alert on dedup-hit and 409 rates per tool.
Give the model a read tool to check whether an action already happened, and instruct it to use it after an unknown outcome.

Sources and further reading

Related in this series:

Diagrams, examples and the lab model are original educational material. Lab numbers are calculated by a synthetic model, not measured on real hardware or services.

Views are my own and do not represent any employer, past or present.