Book a 30-min call
← cd ../blogs
$ cat posts/durable-execution-replay-vs-re-decide.mdx

Durable execution for agents: replay or re-decide

July 2, 2026 · ImmovableTech Team

  • Agentic AI
  • Production AI

The promise, and the property that breaks it

Durable execution engines all make the same promise and all keep it the same way. Temporal, Restate, DBOS and AWS Step Functions record what a workflow has already done, and when the process hosting it dies they rebuild the workflow’s state from that record rather than from memory. Temporal re-executes the workflow function from the beginning and feeds it the recorded Event History instead of re-running the outside world. DBOS restarts the workflow with its checkpointed inputs and, before each step, looks in Postgres for a checkpointed output. Restate replays a journal. The mechanisms differ in their details; the assumption underneath them does not. Re-running the orchestration code against the same recorded results has to produce the same sequence of calls, or recovery is incoherent.

A model call does not honour that assumption. Send the same messages to the same model twice and you may get a different tool call, a different plan or a different final answer. Every engine has the same structural answer, which is to declare the model call a side effect and push it out of the deterministic path: Temporal puts it in an Activity, DBOS in a step, Restate wraps it in ctx.run. Temporal’s workflow documentation now lists LLM invocations alongside API calls, database queries and file I/O as things that belong in Activities, which tells you how routine this has become.

That answer is correct, and it is also where the interesting decision starts. “Record the model call” quietly settles a question about recovery that nobody asks you to sign off on.

Two recovery semantics, and neither is free

Once a completion is in the journal, recovery can do one of two things with it.

Replay returns the recorded completion. The agent, on recovery, does not know it crashed. The run has one coherent story from start to finish, the trace matches what actually happened, and you can re-run the whole thing offline and get the same answer. You have also frozen a decision. If the agent chose to hold an order pending a supplier confirmation, crashed, and came back four hours later, replay re-commits a choice made against a four-hour-old view of the world.

Re-decide calls the model again with current state. The agent adapts to whatever moved while it was down. In exchange you give up determinism, you give up reproducibility, and you give up any clean audit trail for the original run — because the original run’s decision is now a thing that happened but did not determine the outcome.

Worth being precise about what the engines actually give you here: none of the four does re-decide inside a run by default. What they offer is an operator-level version, applied after the fact. Temporal’s Reset terminates a Workflow Execution and starts a new one with the same Workflow ID, copying Event History up to a chosen reset point and continuing from there with current code. DBOS forks a workflow from a chosen step, copying earlier step results into a new workflow ID and executing forward. Both are recovery tools driven by a human or a script once something has already gone wrong. If you want the agent to re-decide for itself, you build that.

Why we record and replay by default

The argument is not that frozen decisions are good. It is that debuggability of a non-deterministic system is scarce and expensive, while adaptivity can be added back at specific, chosen points.

We learned this the unglamorous way. Our first long-running agent re-decided on recovery, because that seemed obviously right — why would you want the agent acting on stale information? It broke on the first real incident. A customer disputed an action the agent had taken. We pulled the trace, and the trace showed a different action, because a worker had restarted mid-run and the recovered run had chosen differently. We could not explain what had happened, and we could not reproduce it, because the run that caused the complaint no longer existed anywhere. We moved to record-and-replay the following week and have not seriously revisited it. The observability work we wrote about in MCP in production is worth very little if the run you are looking at is not the run that happened.

Replay costs you two things and you should price both. The first is staleness, which is the whole point of this post. The second is history size, which is more boring and arrives sooner. Every completion goes into the record. Temporal terminates a Workflow Execution when its Event History exceeds 51,200 Events or 50 MB, and logs a warning after 10,240 Events or 10 MB. Do the arithmetic on a research-style agent: a few hundred turns with completions in the tens of kilobytes puts you at the warning threshold on size long before you are anywhere near the event count. Continue-As-New exists for this, and it is not free when the thing you have to carry across the boundary is conversation state.

We now store completions out of line — full text in object storage, a content hash and the parsed tool call in the journal. Replaying a debug session costs an extra fetch. Histories stay small enough that nobody has to think about them.

Marking a re-decide point

A re-decide point is a place in the workflow where you have decided, in advance and in code, that the world moves fast enough that a recorded decision may be worthless. Three invariants have to hold before you put one in.

It has to be idempotent up to the point of divergence. A re-decided plan may repeat steps the original plan already took, so everything before the marker must tolerate being executed again. If it cannot, the marker is in the wrong place.

It needs a cheap validity check on the previously chosen action. The marker should not fire on every recovery — that is just re-decide by another name. It should fire when the recorded action is demonstrably no longer available. Cheap means a lookup against current state, not another model call, because a model call to decide whether to make a model call is both slow and itself non-deterministic.

And it needs a bound on divergence. The re-decided plan keeps the same goal, the same budget and the same allowed tool set. If the model wants to leave those, it escalates rather than proceeding. Without a bound, a re-decide is a quiet restart of the task with none of the accounting.

from dbos import DBOS

@DBOS.step()
def choose_action(world: dict) -> dict:
    """Recorded once. On replay DBOS returns this checkpoint instead of calling the model."""
    return model.plan(world)

@DBOS.step()
def still_valid(action: dict, world: dict) -> bool:
    """A lookup, not a model call. Fires the re-decide only when the recorded action is dead."""
    return action["order_id"] in world["open_orders"]

@DBOS.workflow()
def handle(order_id: str) -> dict:
    # load_world and execute are also @DBOS.step()s, elided here
    action = choose_action(load_world(order_id))
    world_now = load_world(order_id)
    if not still_valid(action, world_now):
        action = choose_action(world_now)  # the marked re-decide point
        record_divergence(DBOS.workflow_id, action)
    return execute(action)

Every re-decide writes its own record: the original decision, the check that invalidated it, the replacement. The audit trail becomes a chain of decisions rather than a single one, which is fine as long as the chain is explicit and someone can read it a month later.

The failure that bites first: tools that are not idempotent

All of the above matters eventually. Non-idempotent tool calls matter on day four.

Durable retry semantics mean a tool can be invoked more than once, and the vendors say so plainly. DBOS’s documentation states that steps should be idempotent, because a workflow that fails while executing a step retries that step during recovery. Step Functions makes the same point at the level of workflow type: Standard Workflows follow an exactly-once model and are suited to non-idempotent actions such as processing payments, while Express Workflows are at-least-once and suited only to idempotent ones. Restate’s durable steps documentation opens by naming HTTP requests and UUID generation as operations that must be wrapped to replay deterministically.

If the tool in question sends an email or charges a card, “at least once” is a bug report. Ours was a notification tool that posted to a customer’s channel twice after a worker restart. Nothing was damaged and it still cost us a conversation we would rather not have had.

The fix is an idempotency key at the tool boundary, derived deterministically from workflow identity rather than from a clock or a fresh UUID. Restate gives you a seeded generator for exactly this — ctx.rand.uuidv4() is seeded by the invocation ID and returns the same value on every replay:

const key = ctx.rand.uuidv4(); // stable across replays; the docs name this use case

await ctx.run('notify-customer', () => notifications.send(message, { idempotencyKey: key }));

There is a subtlety that we got wrong, and it is the point where the two halves of this post meet. We first keyed on the step index. That works under pure replay and fails the moment you introduce a re-decide point, because a re-decided plan can shift the step numbering, and an action we had already taken got a fresh key and went out a second time. Key on workflow identity, tool name and a hash of the arguments instead. Then a re-decide that reaches the same conclusion is suppressed, and one that reaches a genuinely different conclusion is correctly treated as a new action.

What the vendors shipped, and what they left to you

Agent-specific support arrived across all four engines over the last year and a half, and it is worth knowing what it does. Temporal’s integration with the OpenAI Agents SDK, which routes each agent invocation through an Activity, became generally available on 23 March 2026. DBOS shipped a first-party Google ADK plugin in its June 2026 release, checkpointing model calls and @DBOS.step()-annotated tools into Postgres. Restate journals model calls through its own context. Step Functions added an AgentCore-powered agentic reasoning step on 3 June 2026, against a managed harness that was still in preview at announcement.

Every one of these does the same thing: it wraps model calls and tool executions as durable steps automatically, so you get record-and-replay without writing the plumbing. That is a real convenience and it is the right default. None of them ships a re-decide primitive, a staleness check or a divergence bound. The part of this problem that is specific to your domain is still yours.

What we’d do differently

Decide the recovery semantics before choosing the engine. We picked a framework first and inherited its default, which is how we ended up with a run we could not reproduce. The question “what should this agent do about a decision it made before the crash” has a different answer for a support triage bot than for something that moves money, and it is cheaper to answer it on a whiteboard than in an incident review.

Put idempotency keys on the very first tool, before there is anything worth protecting. Retrofitting them across a tool catalogue is dull work and you will miss one.

Store completions out of line from the start. We migrated once histories were already large, which meant a migration rather than a decision.

Write the divergence log format before the first re-decide point exists. We added re-decide points and then discovered we had no consistent way to answer “why did this run choose differently”, which is the only question anyone ever asks about them.

References

We design recovery semantics for long-running agents as part of our AI & Machine Learning Engineering practice. Talk to us if you need to explain, months later, why an agent did what it did.