Agent Idempotency in Distributed Task Queues

At-least-once delivery is the baseline condition every distributed task queue is built on, and agent idempotency has to be designed around it. Exactly-once execution across a network is a promise no distributed system can keep without help, and the systems engineers actually use state this directly.

At-least-once delivery as the practical default in distributed task queues

Exactly-once execution is difficult to achieve in practice. It's typically approximated for financial transactions through a combination of idempotency and transactional guarantees, as distributed job scheduler design has long established, rather than delivered as a native property of the network. The reason sits in a failure mode that recurs across every queue architecture: a worker completes an action on a downstream host, the process dies before it can acknowledge the message, and the broker, having no confirmation, redelivers it. By the time the redelivered message arrives, the downstream host has already moved to a new state, while the workflow history still records an operation that looks unfinished.

This is not a flaw specific to any one vendor. AWS documents SQS standard queues as offering at-least-once delivery as a guarantee, not a best effort. Apache Kafka defaults to the same guarantee, with exactly-once semantics available only as an opt-in transactional configuration, and Kafka's own documentation warns that even with that configuration enabled, external destinations still require cooperation to avoid duplication. SQS FIFO queues narrow the problem but don't close it: deduplication holds only within a five-minute window, not indefinitely.

From the server's point of view, a retried request and a brand-new request look identical. Without some mechanism attached to the request itself, every incoming call has to be treated as though it has never been seen before, because the server has no way to know otherwise. That is the condition idempotency keys, deduplication windows, and consumer-side checks exist to solve. All of them, however, were built on an assumption that is about to come under direct strain.

Classical idempotency's broken assumptions under AI agent re-synthesis

Every idempotency mechanism in production today assumes the caller sends an identical request on retry. LLM agents break that assumption by design, not by malfunction. Unique request IDs, recorded nondeterministic values, deterministic orchestrator logic: all three patterns were engineered for programs that replay identical bytes on a second attempt. An LLM agent does not replay bytes. It regenerates them.

Zheng et al., in the ACRFence paper (arXiv:2603.20625, presented at the CoDAIM Workshop in 2026), trace the root cause to what checkpoint-restore actually does and does not do. It saves and restores local process state, but it cannot undo actions already taken against external services. When an agent resumes from a checkpoint, the LLM re-synthesizes its next request rather than replaying the one it issued before the crash, and that new request can differ from the original in ways that matter to the receiving server. The variation does not require any unusual circumstance to appear. Even at temperature=0, floating-point rounding inside GPU kernels produces different token sequences across separate runs, so a restored agent generates a request a server will accept as genuinely new.

Zheng et al. illustrate the consequence with a transfer scenario. An agent sends money to a recipient named Bob, generates a UUID to serve as the transaction's unique reference, and crashes after receiving a malformed receipt response from the bank. On restore, the agent regenerates its tool call, including a new UUID. The bank, checking for a matching reference, finds none, because the new UUID has no relationship to the one already recorded against the first transfer. It processes the request as a second, legitimate instruction. Bob receives twice the intended amount, and nothing in the system has logged an error.

The paper names two attack classes that follow from this mechanism. Action Replay covers duplicate irreversible effects triggered by re-synthesized parameters, of which the double payment to Bob is an instance. Authority Resurrection covers a different failure: credentials already consumed get reused after a restore, because the local state that marked them as spent has been rewound along with everything else. A HashiCorp Vault issue documents exactly this pattern in production, with single-use tokens reappearing as valid after a snapshot restore.

None of this requires the agent to behave strangely. The agent is doing what its framework instructs: retry on timeout, retry on a 5xx response, retry when a tool's response is ambiguous. The instruction to retry is sound engineering practice under at-least-once delivery. What makes it dangerous here is that the tool call on the receiving end was never designed with the expectation that it might be retried by a caller incapable of sending the same bytes twice.

The duplicate-execution problem's reach across agent frameworks today

This is not a hypothetical defect confined to one research paper's test harness. Zheng et al. surveyed 12 major agent frameworks and found that none of them enforces exactly-once semantics at the tool-call boundary. The gap is visible across teams that have never coordinated with one another, evidence that the cause is structural, shared across independent codebases.

LangGraph accounts for eight or more confirmed issues tied to this pattern, and a maintainer has acknowledged that eliminating re-execution on resume is architecturally difficult within the framework's current design. Google's ADK shows four such issues, and its own documentation states outright that rewinding a session cannot undo external side effects already committed. AutoGen contributes three, including a case in which the first node in a GraphFlow executes twice, a failure independently reported in a 2025 GitHub discussion (#6595).

The underlying cause is the same in all three frameworks: an operation that is not idempotent, sitting in the path of a delivery mechanism that guarantees at-least-once semantics, a decades-old distributed systems failure mode, recognizable to anyone who has operated a message queue, now appearing inside a new kind of runtime. Payment processing shows the stakes most clearly, because a duplicate transaction carries its own distinct reference ID and can pass every downstream validation check as though it were a wholly separate, legitimate instruction.

The core toolkit: idempotency keys, deduplication windows, and the Idempotent Consumer pattern

Idempotency keys, bounded deduplication windows, and the Idempotent Consumer pattern together form the foundation every production task queue needs, and they remain necessary even though, on their own, they are not sufficient for agent workloads.

An idempotency key attaches to each job submission. When the same key arrives twice, the system returns the result of the existing job rather than creating a second one, a property that matters most acutely in payment processing, where a duplicate execution means a duplicate charge. The key must be derived from an immutable business entity, such as an order_id, a payment_intent_id, or a user_id, never from a hash of the full payload. Payloads change across retries in ways that have nothing to do with intent, through timestamp fields or metadata enrichment, and hashing them produces a different key for what is substantively the same request. An LLM agent re-synthesizes a new UUID, a new timestamp, or a new nonce after restoring from a checkpoint, so the retried call carries a key the deduplication store has never seen and sails past the check.

Deduplication windows bound how long a system remembers a given key. SQS FIFO enforces its check for five minutes; past that point, a delayed duplicate is processed as though it were original. A subtler gap sits at the edge of any such window: a duplicate message can arrive at the exact moment its message_id's TTL expires, and the system reprocesses it as new. The conditions that produce this, a producer failure combined with a long-running consumer task and a network partition that delayed acknowledgment, are rare in isolation but real in combination, and the gap remains unresolved in most production implementations. The practical consequence is that a window has to be sized against the worst case, not the typical case. Stripe's retry horizon runs three days; a deduplication window shorter than that, plus processing time, gives a team the appearance of safety without the substance of it.

The Idempotent Consumer pattern closes a different part of the gap. Each processed message ID gets recorded in a database table, checked before the message is handled, and the side effects of handling it are committed in the same transaction as the record of having handled it. A redelivered duplicate then short-circuits before it can cause a second effect. The pattern only holds, however, if the check and the write happen atomically. A check followed by a separate write opens a TOCTOU window the moment two deliveries arrive concurrently.

One vector gets missed often enough to deserve its own mention: graceful shutdown. When a worker receives SIGTERM, it should stop accepting new jobs, allow in-progress jobs to finish up to a timeout, acknowledge them, and only then exit. Skip this, and jobs that were mid-flight become visible to the queue again, get picked up a second time, and turn an ordinary deployment into a duplicate-execution event. That assumption is what the next failure mode, and the agent behavior after it, breaks.

Closing the gap between database state and the message queue with the outbox pattern

A separate failure sits between the database and the queue, and no amount of key discipline closes it. A worker writes its result to the database, then publishes a message to the queue, as two distinct operations. If the process dies between those two steps, one of two things happens: the database holds a state the queue has never announced, or the queue has announced a state the database never committed. Either way, the two systems disagree about what happened, and nothing downstream can tell which one is right.

The transactional outbox pattern resolves this by writing the stage artifact, the follow-on job, and the outgoing message in a single database transaction. A separate relay process reads the outbox table and publishes each record to the queue, marking it sent only once the queue has acknowledged receipt. Because publishing an already-published message is idempotent at the queue level, the relay itself can be retried safely without risk of compounding the problem it exists to solve.

Agent workloads make this pattern more than a matter of database hygiene. An agent that fans out several sub-tasks by writing directly to a queue can produce a fan-out that only partially completes, invisible to any retry logic built around individual job keys, because no single record reflects the fan-out as a whole. The outbox pattern makes that fan-out atomic and, just as important, observable: a team can query the outbox table and know exactly which sub-tasks were committed as a unit. The relay adds latency and another moving part to operate. For lower-throughput flows, the simpler route is to write task state and enqueue the job in the same transaction, using a database-backed queue such as a jobs table polled by workers, accepting higher database load in exchange for atomicity that a separate relay would otherwise have to provide.

Durable Execution Engines and Agent Idempotency

Durable execution engines remove a large share of the surface area where application-level idempotency logic would otherwise need to be written by hand, but they stop short of the external system boundary, where agent re-synthesis of tool calls still causes duplicate execution.

Temporal separates a workflow into two kinds of code. Workflows are deterministic and replayable; Activities are short-lived and potentially non-deterministic, covering things like HTTP calls or database writes. Temporal's immutable event history lets a workflow be reconstructed at any point after a failure, which is a genuine solution to the problem of losing in-progress state. Temporal's own documentation, however, describes Activities as executing at-least-once and recommends that developers write Activities to be idempotent themselves. The engine reconstructs its own internal state reliably; it does not convert every external system an Activity touches into an exactly-once database. The 2025 integration between OpenAI's Agents SDK and Temporal brought durable, resumable execution to OpenAI-powered agents with minimal code changes, handling retries, state management, and checkpoint-like recovery automatically. That integration did not remove the need for idempotency, concurrency controls, compensation logic, or reconciliation wherever an Activity affects something outside Temporal's own event history.

Restate takes a different approach, through a journaling primitive called ctx.run() that records the result of each step and replays the recorded result on retry rather than re-executing the step, claiming exactly-once semantics without requiring idempotency keys in application code. The limitation sits at the same boundary Temporal encounters. ctx.run() journals what the application code returns, not what the external service actually did with the request. If the external service received the call but the journal write failed before recording it, the journal and the external system's actual state can diverge, and nothing in the journal will reveal that divergence on its own.

Teams building agent task pipelines that need this class of durable execution without adopting a full workflow-engine model have other lightweight platforms worth evaluating on their own merits, alongside Temporal and Restate, when scoping which durability guarantees a given pipeline actually requires.

Both Temporal and Restate share a deeper assumption that neither can escape: on replay, the application code is expected to produce the same tool calls it produced the first time. That assumption holds for deterministic code. Temporal enforces determinism in Workflow code specifically for this reason. The engine's replay mechanism is sound; what it replays against has already changed.

ACRFence's semantic comparison approach as the agent-specific extension to classical patterns

Key-based deduplication fails the moment an agent re-synthesizes a different UUID for what is, in intent, the same action. Closing that gap requires comparing what the agent meant to do rather than the literal string it produced, the extension agent workloads need on top of the classical toolkit.

ACRFence, the framework Zheng et al. propose, works by recording the irreversible effects of each tool call as the agent executes, rather than only tracking the identifiers that accompany them. Upon checkpoint-restore, it enforces replay-or-fork semantics: before letting a re-synthesized tool call proceed, the framework compares it against the record of what was already executed and irreversible, and decides whether that call represents a genuine replay of a completed action or a legitimately new step forked from the restored state. This is a semantic comparison rather than a key match, built specifically to catch the case where an agent's new UUID and new timestamp describe the same underlying transfer to Bob that already went through.

The approach is framework-agnostic by design, addressing a failure Zheng et al. found distributed across LangGraph, Google ADK, AutoGen, and nine other systems. It does not replace idempotency keys, deduplication windows, the Idempotent Consumer pattern, or the outbox pattern. It sits above them, catching the specific class of duplicate that those mechanisms were never built to recognize: one where the caller itself cannot promise to ask the same way twice.