11 Durable Execution
Purpose
Agent stack focus for this chapter.
Why must an agent write down what it is about to do before it does it?
Real agent tasks, such as migrating an enterprise database or debugging a distributed codebase, run for minutes, hours, or days, long enough that process restarts, node preemptions, and rolling updates stop being rare events and become part of the workload. The harness that supervises such a task keeps its control record in the memory of a single worker, and the model’s context holds only a curated transcript, so one crash erases the admitted operations, held reservations, and pending approvals that tell a successor what may happen next. Restarting from the original prompt is worse than slow, because it resamples a stochastic model and may repeat an external effect, such as a deployment or a payment, that has already escaped. Durable execution answers with an ordering discipline inherited from transaction processing. The runtime appends every decision and observation to a log that outlives the worker, makes each intended action durable before dispatching it, and rebuilds control state by folding that history rather than by asking the model again. The log still cannot report what happened to a request whose reply never arrived, and keeping that ambiguity visible instead of guessing it away is what lets state survive a long horizon without corrupting the world the agent acts on.
Learning Objectives
- Construct a trajectory log whose fold rebuilds control state without treating recorded claims as world truth
- Apply intent-before-dispatch ordering under a declared failure domain, price its acknowledgment, and classify what each crash position lets recovery conclude
- Select a checkpoint representation and cadence from write volume, capture pause, and reconstruction cost
- Design a resume policy that reconciles outstanding obligations under current ownership within a stage-by-stage latency budget
- Distinguish time-travel replay of a recorded projection, harness regression replay, and counterfactual branches by the conclusion each supports
- Diagnose the first divergence between two executions from captured inputs, stating what the evidence cannot establish
- Design retention policies that keep the bytes each declared recovery, replay, and diagnostic promise requires
11.1 Worker Failure Mid-Trajectory
Horizon stretches state past one worker’s life, so continuation needs a durable record.
Consider a software repair agent (Four lighthouse workloads) that has admitted and dispatched an integration test against ws_r18, a fixed workspace snapshot of candidate patch r18. Before the test runner reports a result, the worker process crashes, or the host suffers a spot preemption (the sudden reclamation of an ephemeral cloud node). A replacement worker cannot simply re-invoke the model with the original prompt. Starting over discards critical context: the pending test invocation, the active capability tokens and resource reservations, any pause state acknowledged by an operator, and any evidence indicating whether the remote executor accepted, completed, or failed the job. Worse, the original test suite may still be executing on a remote cluster, incurring financial charges and modifying sandbox state, while a newly launched model redundantly dispatches a conflicting command. This crash, with its dispatched but unreported test, is the chapter’s running worksheet, and each section asks what the surviving record says about it.
The agent harness already tracks most of what the replacement worker requires. Its live trajectory record separates pending execution continuations from outstanding external obligations, while its admission checks govern which actions may cross the runtime boundary. In a naive implementation, however, both structures reside exclusively in volatile host memory and vanish the instant the worker fails. The model’s context window cannot substitute for this operational state. A large language model (LLM) context contains only an episodic transcript shaped by bounded observation windows and prompt compaction; it contains no record of in-flight network sockets, admitted capability tokens, or active cloud billing meters. As the execution horizon expands across dozens of turns and long-running external tasks, worker crashes, node preemptions, and rolling updates shift from rare anomalies to operational certainties.
↩︎ The trajectory record that holds pending continuations and outstanding obligations is established in The Trajectory Record.
Surviving mid-trajectory failures requires durable history: an append-only, ordered log of every decision, admitted action, and received observation. With this durable log, a replacement worker can deterministically reconstruct the agent’s state, reconcile side effects that already reached external systems, and safely resume execution under valid authority. That capability names the chapter’s subject. A trajectory has durable execution when a different worker, after any failure the runtime declares it tolerates, can reconstruct the trajectory’s control state and outstanding obligations from surviving records and continue it without losing an effect that already escaped or repeating one unsafely. One ordering rule makes that possible. Under write-ahead durability, the record of an intended action becomes durable before the action is dispatched over the network. The rule is the runtime’s mechanical answer to the horizon and state exposures, a bound placed below the model that no prompt can supply, and it carries measurable costs in acknowledgment latency on every dispatch, capture pauses at checkpoints, and reconstruction time on recovery.
The chapter builds the durable runtime in the order a crash demands it. First, the trajectory log (section 11.2) defines the record from which a clean worker rebuilds control state, and durable intent before dispatch (section 11.3) orders that record against external effects while pricing the acknowledgment each failure domain requires. Because folding an unbounded log and reconstructing mutated files from scratch would grow too slow over long runs, checkpoints (section 11.4) bind the control record to workspace snapshots at regular strides, after which the resume protocol (section 11.5) turns that reconstructed state into an authorized continuation under a new owner. The same durable records then serve offline debugging: replay (section 11.6) inspects or tests history without new model calls, divergence localization (section 11.7) finds the earliest boundary where two executions disagree, and retention (section 11.8) decides which of these recovery and replay promises the stored bytes can still keep. Each mechanism answers the central question of the worksheet crash by establishing what the surviving record proves and what ambiguity remains unresolved.
11.2 The Trajectory Log
A replacement worker can rebuild the crashed trajectory only from what the failed worker wrote somewhere that outlived it, so the first design question is what outliving it means. If the worker host and its attached disk are destroyed together mid-turn, a replacement on an independent machine can resume only if the acknowledged history was already replicated to independent storage. Durability is therefore meaningful only relative to an explicit fault model that names which failures the stored history must survive. Systems engineers call this boundary a failure domain, the set of faults across which a persistence guarantee holds. Three tiers of increasing severity recur: a process crash that leaves host storage intact, replacement of the worker node while a shared network-attached volume survives, and permanent loss of that storage tier. Each tier demands stronger replication and wider physical fault isolation, and section 11.3.1 prices the acknowledgment each one requires. The crash worksheet targets the strongest tier, in which the acknowledged event history and every artifact required for recovery survive the simultaneous destruction of the worker host and its attached disk. Every durability claim in this chapter is made relative to that contract.
11.2.1 The log as recorded evidence
Surviving the failure domain solves where the bytes live, but it leaves open what those bytes must record so the replacement worker never has to ask the model what happened before the crash. Re-prompting the model from its last visible message cannot reconstruct past control state, because stochastic sampling and a changed external environment steer the trajectory down a different path. Instead, the runtime decouples execution state from process lifetime by recording an append-only, chronological history of every decision and observation across the trajectory.
Definition 11.1: Trajectory log
Trajectory log is the append-only, ordered sequence of typed events (including delivered model prompts, returned completions, resource authorizations, control transitions, and observed tool outcomes) from which a deterministic reducer reconstructs an agent trajectory’s control state.
- Significance: Recovery folds recorded decisions sequentially rather than re-executing completed turns. A crash late in a long trajectory therefore costs only deterministic replay time, avoiding fresh model invocations that would re-expose the system to the compounding error rates of equation 1.1 and accumulate redundant token charges against the task attempt budget in equation 1.2.
- Distinction: The trajectory record (definition 10.2) is the live in-memory projection that governs the immediate next decision; the trajectory log is the immutable, append-only history from which that record is derived; and the context window is the transient, curated token sequence supplied to the model.
- Common pitfall: Recording only tool results while omitting operation dispatches. If an admitted tool call crashes mid-execution or drops its network response, the absence of an intent record leaves the recovery worker unaware that an external side effect may already be in flight.
Formally, the log is a sequence
\[\LoggedEventPrefix = [\LoggedEvent_1, \LoggedEvent_2, \dots, \LoggedEvent_j]\]
When an agent refines an earlier hypothesis or encounters an unexpected tool error, it appends fresh evidence to the tail of the log rather than mutating historical records in place.1 The active trajectory record represents an accumulated projection over this append-only stream. Starting from a base state \(\ProjectedTrajectoryRecord_0\), a deterministic reducer applies each recorded event sequentially:
1 Append-Only Log as Primary Record: Rosenblum and Ousterhout’s log-structured file system treated the sequential log as the primary on-disk data structure, boosting write throughput and simplifying crash recovery (Rosenblum and Ousterhout 1992). A trajectory log inherits these exact advantages: append operations never overwrite historical evidence required by future recovery passes, so a recovering worker can reconstruct state by streaming an ordered log rather than untangling conflicting in-place updates.
\[\ProjectedTrajectoryRecord_j = \text{fold}(\ProjectedTrajectoryRecord_0, \LoggedEventPrefix) = \text{apply}(\dots\text{apply}(\text{apply}(\ProjectedTrajectoryRecord_0, \LoggedEvent_1), \LoggedEvent_2)\dots, \LoggedEvent_j)\]
In this formulation, \(\LogPositionIndex\) indexes the durable log sequence boundary rather than the interaction turn \(\TurnIndex\). Given deterministic reducer semantics and complete event payloads, folding reconstructs the precise control state without invoking the foundation model or re-executing external tools. This architecture embodies the classic event sourcing pattern (Kleppmann 2016): historical decisions serve as deterministic inputs to state reconstruction, while unrecorded events remain explicitly unknown. If the latest durable log entry indicates that a test execution was authorized and dispatched, but contains no corresponding completion event, the reconstructed state marks that operation as unresolved (figure 1). For the worksheet crash, the fold keeps the held reservation and the dispatched test_r18 intent, and it invents no outcome for the test.
Engineers must distinguish the trajectory log from the model’s active context window. Context assembly is selective and ephemeral: prompt compilation filters past interactions, and context compaction periodically replaces verbose command outputs with concise summaries. The trajectory log, by contrast, preserves the exact delivered inputs and operational decisions required by the system’s replay contract. For a truncated observation, the log retains the exact byte slice exposed to the model rather than the full, unpruned output stream emitted by the tool. State reconstruction reproduces only what was durably captured. A compacted summary replays as a summary, and a logged hash of a payload can verify those bytes only while the stored payload itself survives (section 11.8.2 develops this separation of digests from bytes).
11.2.2 The log event schema
If a log entry records only that a tool was called without capturing the worker lease, control epoch, or reservation bound, a replacement worker cannot tell whether a late callback belongs to an invalidated turn or how much budget remains locked. An event log supports reliable recovery only when its schema captures the operational metadata that succeeding workers need to answer those questions. Table 1 groups these event families by their roles during reconstruction. These schemas define logical event boundaries rather than requiring isolated physical storage writes for every individual field. For example, a high-throughput runtime can coalesce authorization checks, budget reservations, and tool dispatch intents into a single batched write transaction, provided the deterministic reducer preserves their causal dependencies and the storage engine durably acknowledges the batch before dispatch (the ordering that section 11.3 develops).
Every event envelope contains a trajectory identifier, a unique event identifier, a monotonically increasing sequence_number, schema type and version tags, and tenant or issuer provenance. In addition, the log records the active reducer version alongside the worker lease identity under which appends were accepted. Within this envelope, the sequence_number defines total event ordering; record_version tracks state machine modifications; and control_epoch is the harness’s control fence, which advances whenever a pause, cancellation, or interruption invalidates in-flight continuations, so an observation stamped with an older epoch cannot advance the current one. A distinct owner_epoch counts grants of trajectory ownership, so that storage can reject appends from a worker whose ownership has passed to another (the fencing mechanism of section 11.5.1). Neither ownership handoffs across workers nor control-epoch increments alter the unique logical identity of an in-flight operation.
↩︎ Epoch fencing, which keeps a stale asynchronous response from advancing the current continuation, is established in Transition guards and the admission check.
| Event family | Required contents | Reconstruction use |
|---|---|---|
TaskStarted |
Task and requester, initial grants and limits, ordinary and finalization deadlines, initial record and workspace references, configuration provenance | Establish the initial scope and accounting contract |
ContextBuilt, ModelReplied |
Model-call identity, immutable delivered-input manifest and bytes or available references, assembly and request configuration, reply status and payload, raw signals and available provider provenance | Recover what was supplied and observed without resampling the historical invocation |
Authorized, BudgetReserved, BudgetSettled |
Decision and policy version, invocation or operation identity, reservation bound, actual usage evidence, remaining unresolved liability, protected finalization reserve | Rebuild admission and accounting, not merely a remaining-balance scalar |
ToolIntent, ToolResult |
Logical operation and transport attempt identities, represented operation and arguments, applicable revision and repeat contract, job handle when known, outcome evidence and observation completeness | Preserve possible dispatch and its evidence; a pending, partial, or timeout result does not establish settlement |
ControlChanged, PlanChanged |
Control request and issuer, guarded state and grant changes, record and control versions, plan revision and dependencies, observation eligibility, resource and outstanding-obligation owners | Restore the continuation separately from work that remains unresolved |
ApprovalRequested, ApprovalResolved |
Exact held action and relevant versions, authorized reviewer and decision evidence, expiry, withdrawal or refusal status | Restore the held decision without treating an old approval as current dispatch permission |
Compacted, RuntimeInput |
Recorded summary and dependencies; clocks, identifiers, policy/configuration inputs, and event-order information captured at the declared replay boundary, where replay substitutes recorded inputs for live ones | Preserve the actual inputs used by context assembly or supervisory decisions |
Checkpoint |
Exact covered log boundary, compatible record and workspace manifests, required artifact references and integrity information | Select an available base for reconstructing the record and workspace through a later suffix |
The software repair worksheet illustrates how these identifiers link distributed lifecycle events. Alongside the workspace snapshot ws_r18, the identifier operation_id=test_r18 designates the logical test suite invocation, while attempt_id=attempt1 tracks the specific network transport attempt. If an asynchronous test executor returns an acknowledgment containing a cluster job identifier such as job_tests_18, that handle correlates future asynchronous callbacks with the original operation. However, a recovering worker can discover this link only if that acknowledgment was durably flushed to the log before the crash. A durable ToolResult may record an active execution state, a timeout, or a completed test report; the reducer interprets these payloads according to their authenticated provenance. If an asynchronous execution finishes after the supervisor has already timed out the enclosing step, the late-arriving ToolResult updates the operation table rather than corrupting an obsolete execution branch.
↩︎ The observation-eligibility protocol that routes late results to the operation table rather than the active turn is established in Late results and observation eligibility.
Capturing model context requires equal diligence regarding immutability. The manifest in ContextBuilt must record the exact tokenized payload or byte stream delivered over the wire, rather than mutable file system paths or external URLs that could mutate before recovery occurs. The log must also capture available inference engine provenance (model checkpoints, serving system versions, and decoding configurations), recording any gaps because hosted model identifiers frequently hide upstream weight updates or inference engine modifications. When execution resumes, the replacement worker can assemble an updated prompt context from recent evidence while preserving the historical invocation records exactly as delivered.
Defining an event schema specifies what state reconstruction requires, but schema definitions alone cannot guarantee that writes reach disk before an agent issues network requests. If a runtime persists a model completion but crashes before flushing the subsequent tool intent, the recovering worker cannot determine whether an external tool call was dispatched, risking duplicate side effects. Resolving this vulnerability requires enforcing strict write-ahead ordering between logging an operational intent and releasing its network dispatch.
11.3 Durable Intent Before Dispatch
In the crash worksheet, the repair worker’s next step is to submit test_r18 against workspace ws_r18. If the harness dispatches that test request across the network and crashes before the ToolIntent record reaches durable storage, a replacement worker folding the surviving log recovers a plan that still says “run the test,” even though the original job is already executing on the remote cluster and accruing charges. Recording only the eventual result leaves that blind spot open on every call. To prevent duplicate runs and untracked financial liability, the runtime must commit the admitted request and its reservation to persistent storage before that request ever leaves its control.
Recording the admitted request durably before dispatching it is classical write-ahead logging applied to trajectory dispatch. A durable history ensures that recovery can identify every external operation that may have begun, even if network partitions or crashes prevent the worker from ever receiving the reply. Under the runtime’s declared failure model, an external mutation that occurs without a recoverable record of intent is a phantom effect. Eliminating phantom effects requires two guarantees, strict write-ahead ordering in the runtime execution pipeline and a storage substrate that reliably outlives the failures the system claims to tolerate. Together they are the Part IV principle of intent before effect (principle 11), whose ordering this section derives (equation 1) and whose storage half it prices.
↪ The database form of write-ahead logging, and why a runtime borrows its ordering but not its control over remote state, is developed in Classical Transaction Background.
Definition 11.2: Durable intent
Durable intent is the immutable record of an admitted operation, capturing its identity, input arguments, a reference to its authorization decision and capability grant, and its budget reservation, acknowledged by storage that survives the declared failure domain before the request is dispatched.
- Significance: It converts a crash between dispatch and reply from an untracked phantom effect into an unresolved operation with an explicit owner, at the price of placing one durable acknowledgment on the critical path of every dispatch (table 2).
- Distinction: A durable intent records that work may have escaped into the external environment. It does not certify that the remote endpoint committed or executed the work, nor does it mandate that a recovered worker must re-execute it.
- Common pitfall: Taking an acknowledgment from storage that shares the failure boundary the design claims to survive, such as writing to a local scratch volume under a system contract that promises resilience against host or volume loss.
The intent references the grant rather than copying a secret into it. A log retained for months and read during replay is the wrong place for a credential, so the secret stays with the credential broker, and a recovered worker obtains a fresh use of it only by passing admission under current ownership.
↩︎ The credential broker, which holds a secret outside the guest and uses it on behalf of an authorized request, is established in Credential brokering.
11.3.1 Acknowledgment and the failure domain
Suppose the repair worker appends the test_r18 intent with a standard POSIX write() call, observes a successful return, and promptly dispatches the test. The host then suffers an immediate power failure. A successful write() guarantees only that the kernel copied the payload into its page cache; those dirty pages evaporate when the power cuts before writeback to disk. When the replacement worker boots, it finds an empty log, completely unaware that a remote test is already active. While the append was durable against a simple process crash, it offered zero protection against host failure. Durability is never absolute; every durability claim must explicitly name the failure domain it survives.
This reasoning extends upward through the failure hierarchy. If a worker fails, a replacement process can recover using reattachable block storage, provided that the replacement can mount the disk and read the acknowledged log and artifacts. If the failure domain includes the permanent destruction of the worker’s storage volume, as in cloud environments where spot instances or underlying hardware failures destroy ephemeral disks, the acknowledgment must originate from a storage service outside that volume. Remoteness alone does not satisfy this requirement. An asynchronous replica updated out of band can lag the primary log, leaving the replacement worker with an incomplete history during a failover.
Each step up the failure hierarchy demands a correspondingly stronger persistence barrier. Dirty pages in the page cache survive a process crash but vanish on host power loss. The barrier against host failure is fsync() or fdatasync(), which returns only after the underlying storage device reports that the data has reached stable media. The two system calls differ in how they handle metadata: fsync() flushes file attributes such as modification timestamps, whereas fdatasync() flushes only the metadata strictly required to read the payload back. For a trajectory log that preallocates its disk files, using fdatasync() eliminates an unneeded disk seek and metadata write per barrier. Even with these system calls, subtle failure modes remain.2 If a drive contains a volatile write cache, it must honor the disk flush command, or the write must specify Force Unit Access (a per-write flag that bypasses the drive cache entirely), before an acknowledgment truly covers power loss. Even a verified local barrier, however, cannot survive the catastrophic loss of the physical drive or volume. Surviving permanent volume loss requires a replicated storage engine that returns a success acknowledgment only after a quorum of replicas, distributed across distinct failure domains, have committed the record.3 The worksheet requires two durable copies outside the worker volume before dispatch. This chosen placement policy is stronger than the single-volume-loss requirement alone; table 2 lists acknowledgments that satisfy the stated contracts.
2 Crash Consistency in Practice: A study of eleven widely used applications, including databases, key-value stores, and version-control systems, found 60 crash vulnerabilities, because each application’s update protocol depended on subtle file-system persistence behavior that its authors had assumed rather than tested (Pillai et al. 2014). A trajectory log inherits the same exposure, so its durability claim should be checked by injecting crashes between every write and barrier, not inferred from the calls it makes.
3 Quorum Acknowledgment: Consensus protocols such as Paxos (Lamport 1998) and Raft (Ongaro and Ousterhout 2014) commit a log entry once a majority of replicas store it; because any two majorities share a replica, an acknowledged entry survives the loss of any minority. The guarantee covers only failures the replicas do not share, so a quorum placed on one host or one power domain gives the latency of replication without the durability the worksheet’s contract requires.
| Failure the contract tolerates | Acknowledgment that survives it | Acknowledgment that does not |
|---|---|---|
| Process crash; host and volume intact | Returned write(), which places the bytes in the kernel page cache that outlives the process |
An event queued only in the runtime’s own memory |
| Power loss or host crash; volume intact | Returned fdatasync() or fsync(), with the device write cache flushed or bypassed |
Returned write() alone, whose dirty pages were volatile |
| Permanent loss of the worker’s volume | Acknowledgment from a replicated store after two replicas outside that volume’s failure domain made it durable, under the worksheet’s additional placement policy | Local barrier plus an asynchronous copy that may not have arrived |
The implementation must define precisely which failure modes its persistence layer covers, how storage errors surface to the application, and how a replacement worker discovers the complete authoritative history. Underlying storage engines provide the mechanical primitives, but the systems architect must establish the durability contract. When an acknowledgment fails or times out with an ambiguous status, the runtime must hold dispatch and resolve the append according to the storage contract. Resolution means re-reading the authoritative log. If the intent is present, the attempt is admitted but still unsent, so a pause or a failed recheck can still withhold it; if a complete authoritative prefix lacks it, the worker appends it again under the same event identity, which storage deduplicates if the first append did land. Holding back a dispatch during a storage outage may temporarily stall progress, but dispatching before confirmation permanently destroys the evidence required to govern in-flight work after a crash.
↪ Why a durability claim must name both its acknowledgment and the failures it survives, and how durability differs from atomicity and isolation, is developed in Guarantee Boundaries.
11.3.2 Durable admission ordering
If a worker validates a proposal and reserves budget in memory (Transition guards and the admission check) but dispatches the network call before the storage acknowledgment returns, a crash in that gap leaves an untracked phantom effect. Durable execution closes that window by inserting an acknowledged intent write between admission and network release. For an attempt that proceeds to dispatch and later produces an observation, the ordering is
\[ \ValidatedProposalEvent \prec \AdmissionDecisionEvent \prec \IntentAcknowledgmentEvent \prec \ExternalDispatchAction \prec \EvidenceRecordEvent. \tag{1}\]
In equation 1, \(\ValidatedProposalEvent\) is the validated complete proposal, \(\AdmissionDecisionEvent\) is the admitted authorization and reservation decision, and \(\IntentAcknowledgmentEvent\) acknowledges its recoverable ToolIntent and required preceding records under the declared failure domain. The action \(\ExternalDispatchAction\) is dispatch, not endpoint completion. The event \(\EvidenceRecordEvent\) is the later durable recording of received evidence, whose status may still be pending, partial, or unknown. The ordering constrains the events that occur; an attempt can stop before dispatch or never produce evidence. Its payoff is that the position of a crash in this sequence determines what recovery may conclude (figure 2). A crash before the worker receives \(\IntentAcknowledgmentEvent\) means the attempt was never dispatched, but an intent may already be durable if its acknowledgment was lost. Recovery must inspect the complete authoritative prefix to determine whether that intent survived. A crash after \(\IntentAcknowledgmentEvent\) but before adequate outcome evidence becomes durable leaves an in-doubt action, an admitted operation whose outcome the surviving evidence cannot settle. This includes a crash before dispatch or after a pending or timeout observation. It is the tool layer’s uncertain outcome (definition 7.4) seen from the recovery side, and it is what the fold of section 11.2.1 marked unresolved. Only recorded, correlated evidence establishes an outcome.
In the crash worksheet, the intent names operation_id=test_r18, attempt_id=attempt1, the immutable ws_r18 input, the selected check, and the endpoint’s repeat contract. It references the applicable Authorized and BudgetReserved decisions, together with the requester and task bindings, control_epoch, and owner_epoch under which they were made. The recoverable prefix must reconstruct the admitted reservation itself, rather than merely a remaining balance.
Admission and control stay coordinated while the barrier is pending. An operator pause or an administrative change in authority can still intercept and withhold an admitted but unsent request, because logging a durable intent records permission to dispatch rather than an irrevocable obligation to execute. The harness’s dispatch-time recheck, the last gate before the request leaves, re-evaluates the admitted attempt against current control state without reserving a second batch of budget. If the release mechanism already dispatched the request across the network, subsequent control actions must treat the request as sent. Conversely, a withheld request keeps its entry in the operation table and its reserved budget until verified evidence confirms that no remote side effects or financial liabilities remain.
↩︎ Dispatch-time rechecks, which re-run budget, authority, and approval checks at the moment of release, are established in Dispatch-time rechecks.
Foundation model invocations require identical rigor regarding identity and liability. Token generation streams over network sockets, and an interrupted invocation can incur charges on the provider’s bill even if a worker crash prevents the client from ever logging the output. The same ordering therefore covers model calls. The ContextBuilt record and the invocation’s BudgetReserved decision become durable before the request leaves, so a crash mid-stream leaves a logged invocation with no ModelReplied. Recovery treats that invocation as in doubt only for its charge, which it settles from the provider’s usage evidence. The lost reply cannot be reconstructed by replaying the prompt, because stochastic sampling produces a different completion, so recovery discards any partial stream and never replays the call. Any retry is a separately admitted invocation, requiring a fresh invocation identity, validated request and context, current admission checks, and a durable budget reservation before dispatch.
11.3.3 Recovery evidence and the completeness rule
The first of the three recovery states in figure 2 (not dispatched) carries a hidden precondition. Following a crash, a recovering worker can treat the absence of a logged intent as proof that dispatch never occurred only if it holds the complete authoritative history promised by the failure domain. This requirement is the completeness rule. An asynchronously updated read replica cannot satisfy this rule, because the replica cannot distinguish between an operation that was never dispatched and an intent whose log record has simply not yet arrived across the network. Table 3 outlines the recovery states governed by this rule.
| Surviving evidence | What it establishes | Consequence for continuation |
|---|---|---|
| No durable intent in a complete authoritative prefix, under enforced write-ahead dispatch | This attempt was not dispatched through the mediated path | Reconsider the recorded proposal under current admission checks; do not dispatch automatically |
| Durable intent plus adequate, correlated outcome evidence | The recorded outcome is established to the extent supported by the endpoint contract | Reuse that evidence within its candidate and check scope; settle charges separately where necessary |
Durable intent without adequate outcome evidence, including a timeout or pending ToolResult |
The operation is in doubt | Retain its identity, liability, and settlement owner; withhold dependent work until its guards permit continuation |
In the crash worksheet scenario, the dispatched test may have failed to reach the service, may still be executing on a remote runner, or may have finished just before the worker crashed. If the executor’s reply accepting the job was never logged, its job handle, job_tests_18, is lost with the worker as well. To resolve this ambiguity, the runtime performs a targeted lookup using the logged operation identity, authenticating and correlating any newly discovered evidence before updating the operation table. A verified test result establishes the check for ws_r18; whether to accept the overall repair remains a distinct policy decision.
The in-doubt status reflects runtime uncertainty rather than external failure, and resolving it is a question about the endpoint. Operation identity and endpoint contracts details the endpoint requirements needed to execute a safe repeat: strict identity scoping, immutable payload binding, retention of prior execution results, handling of concurrent in-flight requests, and coordination between state mutations and returned values. A client-provided idempotency key protects only those endpoints that implement these semantics. Probing an endpoint by resource name provides much weaker guarantees, as a matching name might belong to an unrelated operation, while an absent resource could simply indicate that a delayed initial request is still in transit. For an in-doubt action, durable execution therefore applies settlement before retry (principle 8) unchanged. The log supplies the operation identity and its evidence, and only the endpoint’s contract or positive outcome evidence licenses another attempt.
↪ The idempotence and deduplication contracts behind a safe repeat are developed in Repetition and Result Recovery.
Systems Perspective 11.1: Write-ahead logging, from pages to endpoints
When surviving evidence proves insufficient to resolve an action, the operation table keeps an owner assigned for reconciliation or explicit operator intervention across timeouts, pauses, and terminal execution paths. Independent branches of execution can proceed under their own guards while dependent operations await resolution. Remediating an effect that is established but unwanted calls for a compensating action, a follow-up operation that undoes or offsets it, which The Trajectory Saga Pattern develops.
11.3.4 Group commit
Intent before effect puts one durable acknowledgment on the critical path of every dispatch. For a single trajectory the price is small, because a millisecond-scale acknowledgment sits beside a turn that spends seconds on model and tool work. The price that matters is throughput. An agent runtime managing dozens of concurrent trajectories pays that barrier separately for each dispatch, and every dispatch in the fleet queues for the same storage service. Under the worksheet’s replicated quorum contract, each barrier is a network round trip to remote storage nodes. Group commit4 mitigates this overhead by coalescing multiple ready log records into a single shared storage acknowledgment (DeWitt et al. 1984). A batch coordinator aggregates pending intent records, issues one consolidated write to the replicated store, and unblocks individual dispatches only after receiving a successful quorum acknowledgment. Even within a batch, every individual trajectory strictly maintains write-ahead intent ordering before transmission.
4 Group Commit Origin: DeWitt and colleagues introduced group commit for main-memory database systems, where memory transactions executed so quickly that the physical log write at each commit became the primary throughput bottleneck (DeWitt et al. 1984). Agent dispatch enters the same regime whenever durable intent logging requires a network round trip to a storage quorum, allowing classical database batching techniques to apply directly to trajectory logging.
Every batch member waits the whole shared flush; only storage work divides.
For a successful batch, let \(\QueueArrivalTime\) be the time event \(\BatchedEventIndex\) enters the batching queue, \(\BatchFlushStartTime\) the start of the batch’s storage operation, and \(\DurableAcknowledgmentTime\) the time its durable acknowledgment becomes available. If notification delay is excluded, event \(\BatchedEventIndex\) waits
\[ \GroupCommitWaitTime = (\BatchFlushStartTime-\QueueArrivalTime) + (\DurableAcknowledgmentTime-\BatchFlushStartTime) = \DurableAcknowledgmentTime-\QueueArrivalTime. \tag{2}\]
The first term in equation 2 captures queueing and batch aggregation delay, while the second term represents the shared physical storage latency. If a batch contains \(\CommitBatchRecordCount\) records, dividing the storage duration equally yields an amortized storage cost of \((\DurableAcknowledgmentTime-\BatchFlushStartTime)/\CommitBatchRecordCount\) per event. Amortization, however, does not compress elapsed time. Every member in the batch must wait through the full storage round trip, plus internal scheduling overhead, before its request can be dispatched.
Increasing the batch size reduces storage overhead per record but increases the queueing delay experienced by early arrivals. Under light traffic, aggregation delay dominates, making a batch flush timer essential to bound tail latency. Under heavy load, throughput amortization keeps queue depths manageable, though very large payloads can eventually inflate the storage operation itself. With a 2 ms timer and a 4 ms quorum acknowledgment, a batch of 16 intents incurs only 0.25 ms of amortized storage work per intent; yet the first arrival waits 6 ms, and even the final arrival still waits the full 4 ms storage round trip. A sound design therefore sizes the batch timer within the allowable dispatch latency budget, instruments queueing delay separately from storage service time, and never weakens the declared durability domain to shave milliseconds off dispatch latency.
Checkpoint 11.1: Intent, evidence, and the durability domain
Write-ahead logging protects the identity and liabilities of actions that escape the runtime, but an event history alone cannot reconstruct the state of mutated files, code repositories, or training environments. Interpreting a trajectory requires coupling each log boundary to a verified snapshot of the surrounding workspace, ensuring that a recovering worker restores the precise execution context in which those actions were taken.
11.4 Checkpoints
A durable intent informs a replacement worker that an operation such as the r18 test may have begun, but it does not store the files that the test actually touched. An execution log stating that an edit succeeded cannot restore modified bytes unless those bytes, or reconstructible deltas against a known base, remain preserved in storage. Durable execution therefore requires the control record and the mutable workspace to share a common recovery boundary.
A checkpoint binds a recoverable record snapshot, its associated workspace files, and all required external artifacts to an exact, committed log position. Checkpointing accelerates recovery by replacing an unbounded prefix of historical events with a single compatible snapshot. This architectural checkpoint differs fundamentally from the compact progress summary used to assemble prompt context: an LLM prompt summary cannot reconstruct raw filesystem bytes, prove resource liabilities, or track uncommitted external operations.
11.4.1 Consistent recovery boundaries
If a runtime snapshots the control record at one instant and copies the workspace directory a few seconds later while a tool is writing files, restoring the pair produces a torn state in which the record refers to file bytes that the snapshot lacks, or the reverse.5 A checkpoint must therefore freeze both halves at an authoritative log position \(\CheckpointLogPosition\), mirroring the fold boundary \(\LogPositionIndex\), rather than at a loose model turn. A checkpoint manifest serves as the formal contract for this boundary. It binds \(\CheckpointLogPosition\) to the record snapshot, the workspace snapshot, references to external artifacts, cryptographic hashes for integrity, and the reducer schema versions required to interpret them. The control record snapshot captures cumulative resource consumption, active budget reservations, approval states, and in-flight operations with their identities and settlement owners. These obligations persist in the record even while a crashed agent awaits replacement.
5 Consistent Snapshot: Chandy and Lamport defined a consistent global state of a distributed system as one in which every recorded message receipt has a recorded send, and gave a protocol that captures such a state without stopping the system (Chandy and Lamport 1985). A trajectory checkpoint obeys the same test on a smaller scale: the record must not refer to workspace bytes that the paired snapshot lacks, or restoration produces a state that never existed.
Two capture designs keep the record and the filesystem consistent at \(\CheckpointLogPosition\). One design pauses workspace mutations, drains in-flight disk writes, and captures the record and filesystem together at a quiet boundary. An alternative design stores workspace states as content-addressed, immutable trees, each named by a hash of its bytes (section 11.8.2), and maps each versioned root directly to a log boundary. External tasks may remain in flight during capture under either design, provided the checkpoint explicitly records their unresolved status and idempotency tokens.
Snapshot publication must strictly follow data availability. The runtime first captures the consistent state and flushes all underlying bytes to durable storage within the failure domain. Only after those bytes are durable does the runtime commit the manifest or append a Checkpoint event to the authoritative log, marking the snapshot eligible for recovery. If a host crashes during capture, the recovery supervisor ignores the incomplete snapshot and falls back to the previous published checkpoint and its subsequent log suffix. Background cleanup can safely reclaim unreferenced staging files, provided garbage collection protects any artifacts still referenced by active recovery paths. Operating systems and storage engines frequently offer copy-on-write snapshots (file-system subvolume snapshots or process-level memory forks) to freeze point-in-time state with near-zero latency; however, serializing and offloading those blocks to independent durable storage remains a necessary second phase.
Restoration proceeds deterministically. The replacement supervisor first verifies the integrity hashes in the manifest, ensures all referenced artifacts are accessible, and fetches the authoritative log suffix spanning from \(\CheckpointLogPosition\) to the desired recovery target \(\RecoveryTargetLogPosition\). It unpacks the record and workspace snapshots at \(\CheckpointLogPosition\), replays the intervening control events through the state reducer, and applies recorded workspace patches up to \(\RecoveryTargetLogPosition\). This reconstruction step invokes neither the foundation model nor the original tool implementations. Instead, it writes preserved byte streams into the worker’s isolated workspace, reinstating identical state without re-executing nondeterministic actions.
Consider the crash worksheet scenario: the checkpoint at \(\CheckpointLogPosition\) binds the record snapshot record_R_ckpt to workspace snapshot ws_r18. The subsequent log suffix captures the model prompt and response, token budget reservations, and the durable intent for operation test_r18 under attempt1. Suppose the host crashes while the test executes, before any execution result reaches disk. Because the test executed against an immutable snapshot using isolated scratch storage, the main candidate workspace experienced zero mutations during this suffix. To recover, the replacement worker restores ws_r18 and folds the suffix events. This reconstructs the pending test obligation and its outstanding budget reservation, recognizing that the operation remains in doubt. Any intermediate scratch data or uncommitted output artifacts must either possess durable references or be marked unavailable.
When an execution suffix modifies workspace files, durable recovery requires comprehensive delta tracking: the base snapshot identifier, ordered byte replacements or unified diffs, file deletions, metadata flags, and SHA-256 integrity checksums. A success return code or a dangling content hash whose backing payload was lost to a crash cannot reconstruct state. If the control log points to a workspace revision whose delta payload is missing from storage, the runtime must fail fast and flag the state as unrecoverable, rather than erroneously pairing a forward log position with an obsolete directory tree. Recomputing missing workspace artifacts constitutes new nondeterministic execution, which falls under admission and repair policy rather than reconstruction.
↪ Whether to repair a failed step or rebuild its state, and the admission check every recovery action must pass first, are developed in Forward Recovery.
11.4.2 Full and incremental snapshots
As an agent writes workspace files, adds operation-table entries, and retains observations turn by turn, copying the entire state at every checkpoint rewrites every previously saved byte. Architects can avoid that repeated copying by storing incremental delta chains instead of full snapshots, satisfying the same recovery contract while trading storage write bandwidth against reconstruction latency. Under full snapshots, restoration latency scales with total state size; under incremental deltas, it scales with the length of the delta chain.
Write volume sharply separates the two representations when checkpointed state accumulates monotonically. What grows across turns is not the log itself, which already appends each turn’s events once, but the state those events produced. A full snapshot re-serializes all of that accumulated state at every checkpoint, whereas a delta holds only the workspace bytes and record fields that changed since the previous checkpoint, which is a different object from the event suffix the reducer folds. Suppose state grows by \(\TurnStateGrowth\) bytes per turn and the runtime writes a checkpoint every \(\CheckpointStride\) turns. The \(\CheckpointOrdinalIndex\)th full snapshot must re-serialize all \(\CheckpointOrdinalIndex \cdot \TurnStateGrowth \cdot \CheckpointStride\) accumulated bytes. Over a trajectory requiring \(\TrajectoryCheckpointCount\) checkpoints, the cumulative write volumes are:
\[\FullSnapshotWriteVolume = \sum_{\CheckpointOrdinalIndex=1}^{\TrajectoryCheckpointCount} \CheckpointOrdinalIndex\,\TurnStateGrowth\,\CheckpointStride = \TurnStateGrowth\,\CheckpointStride\,\frac{\TrajectoryCheckpointCount(\TrajectoryCheckpointCount+1)}{2}, \qquad \IncrementalSnapshotWriteVolume = \TurnStateGrowth\,\CheckpointStride\,\TrajectoryCheckpointCount. \tag{3}\]
As equation 3 illustrates, full snapshots cause write volume to scale quadratically with trajectory length, whereas incremental deltas scale linearly. The ratio between them, \((\TrajectoryCheckpointCount+1)/2\), represents the write amplification penalty incurred by full snapshots, which spend storage I/O by re-serializing previously checkpointed state at every boundary.
Full snapshots rewrite old state, so their bytes grow quadratically.
For a 500-turn trajectory whose state expands by 128 KB per turn, checkpointing every 5 turns produces 100 checkpoints. Full snapshots write 3.2 GB over the run, whereas incremental deltas write only 64 MB, a 50.5-fold reduction in write volume. The saving moves cost onto the recovery path. Instead of loading a single flat image, restoration must fetch, validate, and replay the sequential delta chain, so the choice turns on what each representation needs to survive and which capture and reconstruction costs must be measured (table 4).
| Choice | What must remain available | Cost to measure |
|---|---|---|
| Full snapshot | The complete selected record/workspace state and required referenced artifacts | Capture pause, bytes written, transfer and restore time for the actual state size |
| Incremental snapshot | A compatible base, every required ordered delta, and referenced artifacts | Capture and write savings vs. chain retrieval, validation, and application cost |
Periodic consolidation can merge an extended delta chain back into a new base snapshot, but the garbage collector must verify that the new base is durably published before retiring earlier deltas. Snapshot retention policies also hinge on audit requirements: while restoring an active agent only requires the latest base and its subsequent deltas, compliance or post-hoc debugging may mandate retaining older historical snapshots across the entire trajectory.
11.4.3 Checkpoint cadence
Checkpointing after every turn pauses the trajectory on every step to copy state that the log already recorded, whereas never checkpointing forces a recovering worker to replay an entire run’s suffix or recompute unlogged work from scratch. Selecting a checkpoint cadence balances that snapshot pause against the time required to reconstruct the suffix after a crash. When logged events and workspace deltas survive host failure, replaying that suffix incurs only the modest cost of reading, validating, folding, and applying recorded mutations, with no foundation-model inference. The agent resumes dispatching new model calls only after state reconstruction and guarded resume succeed.
Classical checkpointing models address a fundamentally harsher failure regime: one where a crash obliterates all in-flight work, forcing the system to recompute from the last checkpoint.6 In agentic execution, this regime governs state the log does not capture. A long local analysis step that keeps intermediate results in memory, or workspace writes that bypass the write-ahead log, must be recomputed from the last checkpoint after a crash. An in-flight tool or model call is a different case that no cadence can help, because recovery treats it as in doubt rather than as lost work. Under Poisson failure assumptions, each crash discards an average of half a checkpoint interval of execution. Balancing that expected loss against the pause overhead of writing snapshots determines the classical checkpoint interval.
6 Checkpoint Interval Lineage: Young posed the problem for long batch jobs that saved restart information periodically so that a random failure need not restart the job from the beginning (Young 1974). The derivation assumes that lost work must be computed again; a trajectory whose turns are logged violates that assumption, which is why the interval lengthens once the log absorbs the lost-work term.
Theorem 11.1: Optimal checkpoint interval (Young's approximation)
A checkpoint taken too often wastes pauses; one taken too rarely wastes re-execution after each failure. When failures are rare, Poisson, and independent of progress, each failure loses on average half an interval of useful work, and the pause is small relative to the interval, Young’s approximation (Young 1974) gives the useful-work interval between checkpoints that minimizes expected overhead:
\[\OptimalCheckpointInterval \approx \sqrt{2\,\CheckpointWriteTime\,\MeanTimeBetweenFailures} \tag{4}\]
- Checkpoint write time (\(\CheckpointWriteTime\)): Time execution stops to capture and durably publish one checkpoint.
- Mean time between failures (\(\MeanTimeBetweenFailures\)): Expected time between crashes that lose unrecorded work.
- Overhead at the optimum: The cadence-dependent overhead is \(\sqrt{2\,\CheckpointWriteTime/\MeanTimeBetweenFailures}\) of useful time. Checkpoint lost-work balance derives the interval, from which this overhead follows, and Daly (2006) refines both for failures during saving and recovery.
- Sensitivity: For a 2 s pause and a mean time between failures of 10 minutes, \(\OptimalCheckpointInterval \approx\) 49 s and the overhead is 8.2 percent. The minimum is flat: an interval off by a factor of 2 in either direction raises overhead by only 25 percent, while a factor-of-10 miss raises it to 41 percent.
7 Determinants: Log-based recovery protocols record each nondeterministic event as a determinant, the information needed to reproduce its outcome during recovery, and are classified by when determinants reach stable storage (Elnozahy et al. 2002). In an agent trajectory the model reply is the dominant determinant: a sampled reply cannot be regenerated, so logging it is what lets the fold replace re-execution.
Appending events to a persistent trajectory log fundamentally alters this trade-off by reducing the lost-work penalty without changing the snapshot pause. In distributed systems literature, pairing periodic snapshots with an append-only log of nondeterministic inputs is termed log-based rollback recovery (Elnozahy et al. 2002).7 When an agent durably records model outputs and workspace diffs turn by turn, recovery costs only the time to replay and validate those entries rather than re-executing inference. Substituting this smaller reconstruction cost into the same balance lengthens the best interval, as the derivation below shows. Only work whose state the log does not capture, such as unlogged workspace writes or in-memory analysis, still pays the full re-execution penalty that equation 4 prices.
Overhead is flat near the optimum interval and steep far from it.
Counted in turns rather than seconds, the logged balance has the same shape as Young’s. Let a checkpoint every \(\CheckpointStride\) turns pause execution for \(\CheckpointWriteTime\), as in equation 4, let crashes arrive at failure rate \(\TurnFailureRate\) per completed turn, and let \(\TurnReconstructionTime\) be the time to reconstruct one logged turn of the suffix (reading, validating, folding, and applying its records). Per completed turn, checkpointing costs \(\CheckpointWriteTime/\CheckpointStride\). A crash finds on average \(\CheckpointStride/2\) turns past the last checkpoint, so expected reconstruction costs \(\TurnFailureRate\,\TurnReconstructionTime\,\CheckpointStride/2\) per turn. Setting the derivative of the sum to zero gives the logged stride
\[\CheckpointStride^* = \sqrt{\frac{2\,\CheckpointWriteTime}{\TurnFailureRate\,\TurnReconstructionTime}}. \tag{5}\]
Repeating the derivation with \(\TurnReexecutionTime\), the cost of re-executing an unlogged turn’s model calls and tools, in place of \(\TurnReconstructionTime\) recovers Young’s regime. Logging therefore lengthens the best stride by \(\sqrt{\TurnReexecutionTime/\TurnReconstructionTime}\). The cost ratio itself is large, because a re-executed turn samples the model again while a reconstructed one only reads records, but the stride grows only with its square root.
An averaged balance hides how a particular failure trace spends its time, so a design is checked against traces as well. Let \(\StrideCheckpointCount_k\) denote the number of checkpoints taken at stride \(\CheckpointStride\), \(\TraceCrashCount\) the number of crashes in the trace, and \(\CheckpointRestoreTime\) the fixed restore latency per crash. If crash \(\TraceCrashIndex\) leaves \(\LostSuffixTurnCount(\CheckpointStride)\) completed turns beyond the most recent checkpoint, the total time lost to snapshotting and recovery is
\[\CheckpointRecoveryOverheadTime(\CheckpointStride) = \StrideCheckpointCount_k \CheckpointWriteTime + \TraceCrashCount \CheckpointRestoreTime + \TurnReconstructionTime\sum_i \LostSuffixTurnCount(\CheckpointStride), \tag{6}\]
with every term in seconds. Charging reconstruction per turn simplifies the model, though in production one turn’s suffix may span several fine-grained log records.
Napkin Math 11.1: Checkpoint cadence on a fixed crash trace
Math: The 10-turn policy publishes 10 checkpoints and reconstructs suffixes of 7 and 3 turns. The 25-turn policy publishes 4 checkpoints and reconstructs suffixes of 12 and 8 turns. The 50-turn policy publishes 2 checkpoints and reconstructs suffixes of 37 and 33 turns. Reconstruction totals are 3 s, 4 s, and 9 s; adding capture pauses gives \(\CheckpointRecoveryOverheadTime(\CheckpointStride)\) of 8 s, 6 s, and 10 s (equation 6). The trace’s failure rate is \(\TurnFailureRate =\) 0.02 crashes per turn, so the logged balance (equation 5) gives \(\CheckpointStride^* = \sqrt{2\CheckpointWriteTime/(\TurnFailureRate \TurnReconstructionTime)} \approx\) 22 turns. If each lost turn instead had to be re-executed at \(\TurnReexecutionTime\) = 20 s, the same balance gives \(\CheckpointStride^* \approx\) 1.6 turns.
Result: The 25-turn stride wins on this trace, at 6 s, next to the balance point of about 22 turns.
Systems insight: Logging each turn’s events and workspace changes lengthens the best stride by \(\sqrt{\TurnReexecutionTime/\TurnReconstructionTime}\), about 14.1× here, because a crash then costs reconstruction instead of repeated model calls. The stride moves with the square root of each knob: quadrupling the capture pause doubles it, and so does quartering the crash rate. Because the optimum is flat (theorem 11.1), a stride within a factor of 2 of the balance point costs at most 25 percent extra overhead; measure \(\CheckpointWriteTime\), \(\TurnReconstructionTime\), and the crash rate from fault-injection traces before tuning more finely.
Operational transitions such as waiting for human approval, compacting execution context, or performing a zero-downtime worker handoff justify taking an opportunistic, out-of-cadence checkpoint if doing so truncates pending recovery chains or enables log pruning. If the record and workspace artifacts are already durable and recoverable, these boundary events require no extra snapshot. Checkpoint cadence remains an efficiency trade-off, whereas intent ordering is an absolute correctness invariant that no cadence optimization can relax.
Checkpoint 11.2: A checkpoint must match its suffix
Reconstructing internal record and workspace state from a checkpoint and its suffix brings the worker up to date, but recovery does not automatically grant authority to resume external execution. The replacement worker must first establish exclusive lease ownership, reconcile pending liabilities, and verify fencing tokens before dispatching new external side effects.
11.5 Resuming a Trajectory
The worksheet’s replacement worker now holds everything the previous sections promised: the checkpoint that binds record_R_ckpt to ws_r18, and a suffix that ends at the durable intent for test_r18 under attempt1 with no result. Holding that record is not yet permission to act on it. The workspace can be restored byte for byte, but the missing result supports no inference about the test, which may never have launched, may have finished as the host lost power, or may still be running remotely. Another worker may also believe it still owns the trajectory, and the budget and approvals recorded before the crash may no longer match current policy. The replacement therefore cannot simply re-run the command or assume failure; it must establish ownership, restore state, settle what it can of the outstanding obligations, and only then admit new work.
Resume establishes a usable continuation from surviving records under current ownership and cluster policy. It proceeds in five stages, which the subsections below follow in order. The worker validates that the authoritative log is available, acquires exclusive trajectory ownership, restores compatible in-memory records and workspace artifacts, reconciles outstanding external operations and resource budgets, and finally evaluates admission for new work, rebuilding serving state if that work begins with a model call. Reconstruction reproduces the agent’s causal history, while subsequent admission gates decide whether to grant or withhold execution authority. If required evidence, ownership fencing, or admission grants are unavailable, the runtime safely holds the trajectory in place rather than proceeding on speculative assumptions.
11.5.1 Availability and ownership
If a replacement worker starts reconstructing state from a lagging storage replica or begins dispatching while a network-partitioned predecessor is still running, it can miss an already-sent test_r18 intent or race against the old worker’s late writes. Before parsing records, the worker must therefore locate the authoritative committed log prefix and the required checkpoint artifacts. Under the log completeness rules of section 11.3, the absence of an entry is meaningful only after the worker proves that the log prefix is intact. If storage replicas disagree, network partitions obscure the tail, or an immutable artifact is missing from object storage, the worker must report that reconstruction is unavailable rather than treating the gap as an empty history.
Reading durable state does not confer the authority to act on it. Trajectory ownership requires an explicit grant from an ownership coordinator, a strongly consistent lease service whose own state is replicated so that it survives the failures the trajectory log survives. The coordinator authenticates the claimant and issues a new owner_epoch. This epoch bump assigns execution responsibility to the replacement worker while leaving record_version, control_epoch, and the identities of admitted operations unchanged.
The distinction between active ownership and historical inspection is vital because the previous worker may have been partitioned rather than permanently destroyed. The tool layer met the same zombie worker, a stalled holder that outlives its lease and resumes writing, and the same remedy protects the whole trajectory. Ownership is held under a lease, so expiry bounds how long a lost worker can block recovery, but expiry alone is not exclusion. Exclusion requires a fencing token, a monotonically increasing ownership generation that stateful resources compare against the newest generation they have observed, rejecting requests stamped with stale epochs (Kleppmann 2016). For a trajectory the owner_epoch is that token. Fencing exclusion holds only at the boundaries that verify it: the write-ahead log, the dispatch gate, and each participating downstream resource. The replacement worker must install the new ownership generation at those boundaries before relying on mutual exclusion, and any boundary unable to verify current ownership must withhold protected operations.
↩︎ Leases and epoch fencing at the tool endpoint, with their lock-service origins, are established in Operation identity and endpoint contracts.
↪ The handoff in which the old owner’s delayed write meets the newly installed fence is developed in Leases and Fencing.
Fencing operates over a narrower scope than effect settlement. A dispatch gateway can reject new dispatch attempts from the old worker while an operation that the old worker previously initiated remains in flight on an external runner. The replacement worker therefore preserves operation_id=test_r18 along with the evidence recorded for that earlier attempt. Passing the ownership check authorizes the new worker to issue fresh dispatches, but it does not permit re-dispatching test_r18. A gateway’s local pending-or-complete tracking table cannot make its log record atomic with an independent service endpoint’s real-world side effects.
11.5.2 State restoration
Once ownership is secured, re-running past turns to rebuild memory would re-sample the model and risk repeating external side effects; instead, the worker restores the control record and the workspace by the procedure of section 11.4.1, folding the committed suffix over the base checkpoint without calling any model or tool. For the worksheet, the result is the state already traced there, with ws_r18 untouched and the in-doubt intent and reservation for test_r18 in the record. What restoration cannot supply is the executor’s job handle job_tests_18, which survives only if the failed worker flushed the executor’s acknowledgment to the log before crashing. Without it, reconciliation must find the job by its logged operation identity.
11.5.3 Effect and charge reconciliation
Because worker processes can crash at any moment, outstanding operations require a durable return path that operates independently of any single host. The harness’s result wakeup pipeline already routes each result to its registered trajectory; durable execution moves that pipeline’s registrations out of worker memory into a durable result inbox, which retains authenticated completion records indexed by trajectory identifier, logical operation, and attempt identity, stamped with executor signatures and scope metadata for independent validation. The current trajectory owner ingests this evidence into the log and the operation_table. However, simply receiving an inbox message does not settle an operation; pending statuses, gateway timeouts, and partial payloads leave the operation in doubt.
↩︎ The result wakeup pipeline and its register-before-send rule are established in The result wakeup pipeline.
For test_r18, the worker queries the tool endpoint to recover the job and its execution output by reconciliation, a bounded status query by logical operation identity under the tool’s contract. If the endpoint returns a verified completion record, that result confirms the status of ws_r18 for that specific test run, though it does not imply that the broader repair objective has been met. If the endpoint cannot be reached or returns an ambiguous status, the operation remains in doubt. In that situation, the endpoint retry contract, rather than the absence of a response or a matching identifier, governs whether launching another attempt is safe.
↩︎ Reconciliation, the bounded inspection of external state that settles an ambiguous operation, is established in Reconciliation.
The same rigorous accounting applies to financial and computational budgets. The worker reconstructs actual_consumption, outstanding_reservations, and the protected finalization_reserve by replaying all recorded BudgetReserved and BudgetSettled transitions. External model providers and compute clusters do not refund resources because an orchestrator crashed mid-flight. A partial usage report settles only the verified fraction of a call, while the unverified remainder stays locked in outstanding reservations. The replacement worker inherits the duty to retrieve final usage evidence. Until that evidence arrives, the unverified remainder stays reserved as liability, the harness’s rule that missing usage is never released as unspent budget.
Control transitions and human approvals remain authoritative across failures. A trajectory recovered in the PAUSED state remains suspended, and a trajectory that reached a terminal continuation remains terminal. A held action recovers into AWAITING_APPROVAL, the state in which approval and dispatch eligibility are both unresolved. A pending request keeps waiting for its reviewer, and an approval granted before the crash still releases the action only when the dispatch-time rechecks pass under the new owner, while an approval that has expired, become stale, or been explicitly revoked remains void across all workers. When authenticated results arrive after an operation has timed out or the trajectory has paused, they update the operation_table to keep an accurate audit trail, rather than retroactively mutating an obsolete conversation turn. The current owner must validate those newly settled facts before admitting them into subsequent model contexts.
11.5.4 Continuation admission
During the minutes a trajectory spent down and recovering, its operating deadline may have expired, an operator may have paused the run, or an in-doubt test_r18 may still hold budget and block dependent edits. Recovered history accounts for past decisions, but current conditions govern the next step. Before admitting new work, the harness evaluates task and plan dependencies, capability grants, approval statuses, cluster dispatch capacity, and remaining funds. To pass admission, the sum of actual_consumption, outstanding_reservations, the bounded liability of the proposed step, and the protected finalization_reserve must fit within the cumulative budget ceiling. Deadlines for normal operation are enforced independently: when an operating deadline expires, the agent cannot schedule new exploratory calls simply because monetary budget remains. Instead, the runtime transitions strictly to finalization routines using the declared time and resource reserve.
↩︎ Bounded-liability admission, the budget rule this check enforces, is established in Reservation and settlement.
Unsettled external effects block dependent operations rather than stalling the entire system. An independent observation or read-only query may proceed if its own authorization and admission checks pass, whereas any action that mutates or depends on an in-doubt operation remains withheld. Resuming execution from PAUSED requires passing the guarded state machine transitions. Similarly, recovered partial model streams are discarded rather than promoted to completed candidates. A logged proposal that was never admitted requires fresh admission; an already admitted but definitely unsent attempt retains its identity and reservation and must pass the dispatch-time recheck without reserving budget again.
↩︎ The control-plane state machine and its guarded transitions out of PAUSED are established in Trajectory States.
Context assembly must strictly distinguish historical reconstruction from forward continuation. When auditing earlier turns, the runtime inspects the immutable delivered-input manifest and recorded summaries that the model actually received. When constructing the prompt for the next turn (ContextBuilt), the prompt composer may incorporate newly settled test results or approved plan revisions. Systems must preserve historical input manifests verbatim rather than silently substituting fresh retrievals or recomputed summaries.
Infrastructure and prompt updates also demand explicit governance. During extended downtimes, operators may update model checkpoints, prompt templates, or tool schemas. The runtime can either pin execution to the recorded versions, validate a verified migration path to the updated schema, or halt continuation if semantic compatibility cannot be proven. An in-doubt intent preserves its original parameter semantics regardless of subsequent schema versions. Whenever configuration shifts occur, the runtime records the transition and its provenance boundaries so that future evaluations treat the executions as distinct configurations.
Dispatching a new model call requires compatible serving state, though this need not require a cold start. Depending on cluster cache eviction policies and prefix tree management, the inference engine may retain the full KV prefix, retain reusable prefix segments, or require full context prefill. Inspecting an audit record or keeping a trajectory paused requires no prefill computation whatsoever. A serial-stage estimate of resume latency sums the constituent stages:
\[\ResumeTime = \OwnershipAcquisitionTime + \CheckpointSuffixReadTime + \SuffixFoldTime + \WorkspaceRestoreTime + \OperationReconciliationTime + \PrefillTime, \tag{7}\]
which accounts for acquiring the ownership fence, fetching and verifying the checkpoint and suffix, folding the log suffix, restoring workspace files, reconciling outstanding external operations, and rebuilding serving state for the next invocation. When stages overlap, elapsed resume time follows their dependency critical path rather than this serial sum. The terms map onto the subsections in order. \(\OwnershipAcquisitionTime\) and \(\CheckpointSuffixReadTime\) belong to availability and ownership (the two can overlap, since reading the log needs no ownership), \(\SuffixFoldTime\) and \(\WorkspaceRestoreTime\) to state restoration, \(\OperationReconciliationTime\) to reconciliation, and \(\PrefillTime\) is the last step of continuation admission.
↩︎ Prefix tree management and KV-cache eviction policies are established in Prefix Caching Across Turns.
The final term marks a fundamental divergence between agent recovery and classical database crash recovery. In database systems like ARIES (Mohan et al. 1992), recovery time is dominated by reading the write-ahead log and redoing logged updates to dirty data pages on disk. In agent systems, deterministic log folding is cheap, because it executes local harness logic and updates in-memory tables without calling foundation models. Rebuilding the serving state, however, forces the system to recompute attention keys and values across the entire context history whenever no compatible cache prefix survives. Applying the weight-only prefill floor derived in Cost Asymmetry Between Input Prefill and Output Generation to the reference model and accelerator, the arithmetic compute floor alone for a 32,768-token context requires roughly 2.3 s of an accelerator’s peak 8-bit tensor throughput, before accounting for memory bandwidth overhead, kernel launch delays, or queueing contention. Because attention state is strictly a function of the token prefix (principle 5), losing that cache throws away reusable computation while the causal knowledge survives safely in the log. Routing to a worker with compatible cached state can avoid prefix recomputation if the next prompt preserves that prefix; placement must also account for queueing, transfer delays, and available capacity. Systems engineers should profile each component of equation 7 before dedicating engineering effort to any single phase.
↩︎ Why prompt assembly must reproduce the delivered prefix token for token to keep cache reuse is established in Preserving an exact prefix.
Resume converts surviving durable records into an authorized continuation without misreading silence as failure. The same records support a second use that admits no new work at all, inspecting and testing what the trajectory already did.
11.6 Recorded Trajectory Replay
When an agent execution stalls or fails during an automated repair, resuming the session admits fresh work under current system conditions. Post-mortem debugging asks a different question, namely what the runtime recorded at the moment of failure and how the harness code responded to the inputs available at that time. Rerunning a targeted test like test_r18 under a new attempt cannot resolve that inquiry. Because external services drift, package versions change, and model sampling introduces variance, a new execution merely supplies fresh observations rather than reproducing the missing historical outcome.
Replay substitutes retained execution records for live, non-deterministic inputs. The guarantees provided by replay depend entirely on which portion of the system computation is repeated. Retained trajectories serve three distinct purposes (table 5): reconstructing a recorded state projection, which debuggers call time-travel replay; validating harness logic through regression replay; and branching into counterfactual experiments.
| Mode | Inputs and computation | Supported conclusion |
|---|---|---|
| Time-travel replay | Fold retained events with the specified reducer and compatible checkpoint | What selected runtime state the recorded history represents |
| Harness regression replay | Run harness logic against captured inputs at a declared boundary, with live effects disabled | How that harness implementation responds to those inputs |
| Counterfactual branch | Restore compatible starting state, change a declared condition, and obtain valid observations for the new path | What happened in this new experiment |
The first two modes make the same change to live execution. Where a live turn samples the model, passes the authorization gate, and dispatches the tool, replay disconnects the model and the tools and streams recorded replies and observations from the log into the harness (figure 3). They differ in what runs on those recorded inputs.
11.6.1 Projection reconstruction
When an engineer inspects a stalled trajectory to see what reservations were locked or what prompt bytes reached the model at turn 18, re-evaluating live policy rules or re-running prompt assembly would overwrite the historical state with today’s decisions. Projection reconstruction, the first replay mode, avoids that contamination by running only the reducer over the log as a deterministic event stream. Folding the log applies previously recorded decisions directly; today’s authorization policy never re-evaluates historical proposals. Starting from a known checkpoint record_R_ckpt, the compatible suffix reconstructs the selected record through its captured admission, reservation, intent, and outcome events. If the suffix ends abruptly after a ToolIntent record without an accompanying settling event, the resulting projection faithfully retains that in-doubt operation, exposing an interrupted execution.
Historical inspection can also retrieve the immutable input manifest captured for a specific ContextBuilt event. This manifest reveals the exact token sequence and bounded observations delivered to the model, rather than a prompt newly assembled from current, potentially mutated data sources. Reconstructing the corresponding workspace environment similarly requires mounting the compatible snapshot together with any incremental filesystem deltas logged up to that point.
Definition 11.3: Time-travel replay
Time-travel replay reconstructs a selected recorded state at a historical log boundary from compatible checkpoints, events, and retained artifacts, without repeating the original model calls or external actions.
- Significance: It renders the runtime’s historical evidence, decisions, and unresolved obligations fully inspectable at any retained log boundary for the cost of storage reads and a state fold, requiring zero model inference and generating zero external side effects.
- Distinction: Time-travel replay reconstructs an internal projection of recorded state, rather than restoring the full external world or re-evaluating decisions under updated policy rules.
- Common pitfall: Promising arbitrary historical inspection across every past turn when retention policies have already pruned required event payloads, filesystem snapshots, or historical reducer definitions.
11.6.2 Harness regression replay
Folding recorded decisions shows what the old harness decided, but it cannot test whether a code change in the harness state machine or prompt builder introduces a bug when handling the same historical inputs. Harness regression replay executes the harness code itself against captured external inputs rather than folding precomputed decisions through a reducer. Instead of querying live model endpoints or invoking real tools, the harness consumes recorded model completions, external tool observations, and control events. For deterministic reproduction, the captured boundary must supply all nondeterministic inputs consumed by the harness logic: wall-clock timestamps, randomly generated identifiers, configuration parameters, policy rules, and event arrival schedules. While this capture boundary does not need to simulate the entire operating system, any unrecorded source of entropy weakens reproducibility. This principle directly mirrors deterministic replay in operating-system debuggers, which record asynchronous hardware interrupts and system call outputs to allow developers to step backward through complex race conditions (King et al. 2005).
8 Happened-Before: Lamport showed that events in a distributed system are only partially ordered: one event precedes another when a chain of process steps and messages links them, and otherwise the two are concurrent (Lamport 1978). Parallel tool calls in one turn are concurrent in this sense, so a replay must either record the order the harness actually observed or declare that any order is equivalent.
To serve captured inputs correctly, the replay adapter follows the matching-request rule, matching every outgoing request against the recorded trace before returning a response. A captured model response is valid only for its specific prompt invocation and delivered token payload. Similarly, a tool observation corresponds to a unique logical operation and attempt, parameterized by exact tool names and serialized arguments. Replay adapters enforce matching using canonicalized representations or explicitly declared normalization schemes, combined with logged arrival sequences or formal concurrency models.8 A naive FIFO queue that blindly yields the next recorded event risks routing the test outcome of test_r18 to an entirely different operation or candidate patch. If an outgoing request deviates from the recorded trace, the replay engine must immediately fail the comparison; under no circumstances should it fall back silently to a live network call.
A reliable regression harness must strictly seal all live side-effect pathways. Real tool dispatch, external callback handlers, asynchronous background reconciliation loops, and production database writes must be severed or redirected to in-memory mocks. While the test may mutate isolated, ephemeral test state, all interactions with external infrastructure are replaced by recorded observations. Enforcing these isolation boundaries is strictly the responsibility of the test runtime; the harness must never trust the model or agent code to refrain from issuing live operations.
Consider an edge case where an asynchronous tool returns an authenticated late result after an agent repair job has transitioned into the PAUSED state. According to the control-plane state machine, the correct harness behavior is to record the arriving observation in the operation table while keeping the agent paused, rather than automatically triggering a new model inference step. If a developer modifies the harness and inadvertently introduces a code path that fires an unauthorized model invocation upon receiving the late event, the regression replay immediately detects the discrepancy and fails the test. Successful execution against this historical trace proves only that the harness correctly handles that specific scenario; passing a replayed unit test for test_r18 does not constitute evidence of general task competence or end-to-end patch correctness.
When engineers update harness orchestration logic or tighten safety policies, behavioral changes are often intentional. Regression suites must therefore specify which outputs require strict byte-for-byte equivalence and which represent expected divergence. A diff between replayed execution and the historical baseline can indicate an unintended regression, an intentional algorithmic improvement, or a defect in the input capture itself. While replaying against recorded inputs eliminates expensive model API charges and external tool latencies, it still consumes local compute cycles, disk I/O, and setup overhead, and it validates behavior solely within the narrow envelope of previously observed execution paths.
11.6.3 Counterfactual branches
A counterfactual investigation asks what trajectory an agent would follow if an engineer alters a prompt template, selects a different foundation model, updates an authorization policy, or modifies an observation filter. The runtime forks execution by allocating a fresh branch identifier linked explicitly to the parent log sequence at a designated checkpoint boundary \(\CheckpointLogPosition\). It documents the intervention in metadata and reconstructs the historical execution environment to match that precise point in time. In the crash repair scenario, branching from checkpoint \(\CheckpointLogPosition\) requires mounting the exact workspace snapshot ws_r18 alongside matching dependency fixtures. If an engineer restores only the historical source code while executing against current, upgraded third-party packages, the experiment conflates the intentional prompt or code change with uncontrolled environment drift.
With durable logs, the runtime reconstructs the unchanged prefix deterministically through projection folding, completely avoiding redundant model sampling or tool execution up to the fork point. Beyond that boundary, however, the newly diverged continuation requires genuine observations that correspond to its altered actions. A captured historical response remains valid only as long as the outgoing request and environmental assumptions match the historical trace exactly. The moment the modified agent proposes a different test command, alters tool arguments, or produces an alternative patch candidate, the recorded downstream events become obsolete. At this divergence point, the branch must either halt replay or transition into active execution, gathering fresh observations from an isolated sandbox or compatible test fixture. Because the branch represents an unverified trajectory, production side effects remain strictly disabled, and human approvals granted to the parent execution never carry over automatically to the branch.
A counterfactual branch is thus a distinct, newly identified execution thread that inherits a validated historical prefix while exploring an alternative downstream path. Inspecting an individual branch helps engineers diagnose why a specific bug occurred or test how a targeted prompt patch performs on a known failure mode. Establishing broader claims about agent reliability or task success rates, however, requires running statistically grounded benchmarks across distribution-scale test suites. Replay establishes the precise boundary where historical evidence ends and new computation begins, and the same retained evidence can pinpoint the exact step at which two executions diverge.
↪ The statistical methods that turn repeated runs over a task distribution into reliability claims are developed in Statistical Evaluation Rigor.
11.7 Locating a Divergence
When an automated software-repair workflow undergoes regression replay, execution proceeds uneventfully until reaching the recorded targeted-test result for candidate patch r18. The stored test result itself remains identical, but a revised harness assembles a subtly different observation context for the subsequent model call. Waiting until the final repair verdict to compare the runs obscures this earlier discrepancy under layers of compounding tool calls and token generations. Effective debugging requires pinpointing the exact architectural boundary where two executions first cease to agree within the recorded evidence.
A divergence point is the first observable mismatch under a declared equivalence relation: between recorded and reconstructed state, between historical and revised harness logic on captured inputs, or between a golden trace and a live execution. Every comparison must explicitly define both its boundary and its equivalence criteria. In practice, two serialized JSON payloads might differ in a harmless trace identifier while representing the same permitted operation. Conversely, two tool invocations cannot be treated as equivalent simply because their shell commands match if they execute against different repository commits or working trees. A coarse turn counter obscures these distinctions when context assembly, model inference, authorization policy checks, and tool dispatch all unfold within a single turn.
11.7.1 Boundary-by-boundary comparison
When a replayed run and an original trace end with different patches, diffing only the final outputs cannot tell whether the prompt builder changed an input, the model sampled a different token, or the policy gate rejected a call. A boundary-by-boundary comparison isolates the earliest mismatch by starting at a verified checkpoint or initial state and stepping forward through corresponding events in their recorded sequence. Stable invocation and operation identifiers align the traces across runs, preserving any concurrency ordering or partial-order dependencies required by the replay contract. At each boundary, the diagnostic runtime evaluates three elements: the inputs delivered to that stage, the transformation configured for it (such as a prompt template, parser, or security filter), and the resulting output. Table 6 organizes this diagnostic evidence by the earliest architectural boundary where a mismatch surfaces, preventing engineers from confusing downstream symptoms with root causes.
| First observed difference | Evidence to compare | What the difference establishes |
|---|---|---|
| Assembled model input | Delivered messages and tool descriptions, source and workspace versions, compaction output, assembly configuration | The compared calls did not receive the same recorded input; inspect the earliest changed dependency or assembly step |
| Model response | Complete request, decoding parameters, requested and available served-model provenance, response status and payload | The responses differ under the visible conditions; unrecorded service internals may limit further diagnosis |
| Harness decision or admitted operation | Recorded response, parser and policy versions, captured clock and control inputs, current grants and reservations, exact operation arguments | The supervisory decision differs; determine whether this is an intended policy change, a defect, or an uncaptured input |
| Tool observation | Logical operation and attempt identities, actual arguments, target snapshot, service configuration and returned evidence | The recorded outcomes or observations differ; determine whether the requests and relevant environments were comparable |
Consider again the candidate patch r18. Suppose the original trace recorded that r18 passed a targeted unit test, but noted that the broader regression suite was omitted. The original harness forwarded both statements to the model. During regression replay with an updated prompt builder, a modified context-compaction rule drops the scope limitation while preserving the word “passed.” Because the replay supplies the identical recorded test output and workspace snapshot, the first divergence occurs at the delivered context input, before the runtime invokes the model. This immediate mismatch isolates the defect to the context assembly change, which stripped critical qualification evidence. Whether this omission subsequently misled the model into making a false completion claim remains a separate causal question for controlled experimentation; the divergence itself is already localized.
Localization granularity depends entirely on what artifacts survive in the persistent store. A surviving cryptographic digest confirms that bytes changed but hides the omitted text, while recording only the agent’s final answer conceals every intermediate boundary. An informative diagnostic report identifies both the last boundary that verified successfully and the specific missing record that halted further automated comparison, rather than attributing the failure to whichever component appears last in the execution trace.
11.7.2 Localization and explanation
Even after a boundary comparison flags a mismatch at a specific step, a hash difference alone cannot show which lines of prompt text changed, and matching hashes cannot explain why two identical prompts yielded different model replies. A cryptographic context digest verifies the byte-level integrity of the payload it covers, but it proves nothing about execution state outside that hash. Matching digests guarantee identical prompt text, yet sampling temperatures, decoding penalties, external tool schemas excluded from the hashed payload, model snapshot revisions, and provider configurations may still differ. Even when a visible request matches across every byte and parameter, hosted inference endpoints can still vary on the server. Conversely, unequal digests prove that the input representation changed, but explaining why requires inspecting the payload diff alongside its provenance metadata. Engineers must examine both the retained content and its lineage before drawing conclusions from hash comparisons.
Live model invocations can diverge even on identical prompts due to hardware and algorithmic factors. Lowering the temperature to zero or pinning a random seed standardizes the sampling policy, but it cannot eliminate variations from cluster-level accelerator scheduling, non-deterministic floating-point summation in parallel kernels, or silent provider-side model updates. Because an early divergence in a model response alters all subsequent prompts and tool invocations, downstream differences often reflect these cascading input changes rather than fresh errors. Debugging must center on explaining this initial point of departure.
↩︎ Floating-point reduction order and other sources of serving-path non-determinism are established in Repetition and replay.
Regression replay controls this cascading variance by supplying captured outputs at a declared boundary, following the principles developed in section 11.6. However, this isolation holds only if the harness captures every external dependency. If an authorization decision or scheduling check consults an unrecorded host clock, an unversioned environment variable, or a dynamic feature flag, determinism across that boundary collapses. When such leaks occur, developers must either capture the missing environmental inputs into the event log or narrow the replay scope to subcomponents with fully hermetic boundaries. Targeted interface interception in the harness achieves this control without requiring heavy, whole-machine snapshot infrastructure.
Sound diagnostic localization therefore yields a bounded engineering claim rather than an unverified causal leap. It specifies the earliest observed mismatch, catalogs the configurations and input artifacts confirmed to be identical, highlights the explicit differences found, and flags any missing evidence. While counterfactual replays can test whether a specific change explains the failure, observing an altered outcome in one trace does not prove that a fix behaves reliably across diverse workloads. Distribution-scale evaluation establishes the causal and statistical methodology needed to evaluate those system-wide claims; durable execution supplies the auditable evidence required to begin that inquiry.
Checkpoint 11.3: Replay and divergence
These boundary comparisons fundamentally depend on which events, delivered inputs, and environmental artifacts remain accessible. An agent runtime’s retention policy therefore decides which recovery guarantees and diagnostic claims the engineering team can defend in production, which makes it more than a storage cost optimization.
11.8 Log Retention and State Compaction
An agent can reconstruct its execution trajectory from a checkpoint at sequence \(\CheckpointLogPosition\) and its subsequent suffix only as long as both the event records and their referenced artifacts remain intact. An event that points to a deleted workspace snapshot ws_r18 restores nothing. Conversely, retaining megabytes of raw compiler output is useless if the durable intent record for test_r18 was prematurely discarded. Retention policies must therefore stem directly from the platform’s recovery contract (the exact state and replay capabilities the system guarantees to support) rather than from storage format convenience.
11.8.1 Retention lifetimes
Expiring all trajectory artifacts on a single timer either deletes an active run’s workspace snapshot ws_r18 while recovery still needs it or forces the cluster to keep terabytes of raw packet traces for months just to preserve audit replay. A production runtime must therefore separate three retention lifetimes: current recovery, historical replay, and optional diagnostics.
- Current recovery demands the minimum set of assets needed to resume a crashed agent immediately: the latest published checkpoint, the complete committed event suffix required to reconstruct the active state record and workspace, and every external artifact referenced by those records. It also requires the operation table that tracks in-flight operations, including attempt counts, mutual-exclusion reservations, and settlement owners. These operational obligations frequently outlive the worker process executing the task.
- Historical replay serves auditing, regression testing, and offline evaluation. Replay often requires earlier checkpoints, exact prompt templates, delivered model inputs, recorded completions, and environmental snapshots that online recovery has long since superseded.
- Diagnostics and telemetry capture ancillary metadata, such as raw network packet dumps, fine-grained profiler traces, or unparsed stdout streams that were filtered before reaching the model’s context.
Although these data classes overlap, each requires an independent retention schedule. A sound retention policy explicitly specifies the supported recovery boundary or replay window, the required artifact classes, the expiration triggers, and the subsystem responsible for settling unresolved work. A recovery guarantee holds only for data copies maintained within the declared failure domain. Pruning a required artifact prematurely breaks the recovery contract; retaining its cryptographic digest in a manifest does not preserve the missing bytes.
In the running crash scenario, record_R_ckpt, the workspace snapshot ws_r18, and the committed suffix through the ToolIntent for operation test_r18 (attempt attempt1) constitute mandatory recovery inputs. The missing tool result remains unknown until reconciliation completes. The runtime can safely prune an unrelated diagnostic log without compromising reconstruction under a contract that never uses it. In contrast, deleting ws_r18 destroys recovery entirely, because prompting the model to generate the patch again initiates a new, non-deterministic execution rather than restoring the candidate under test.
11.8.2 Content-addressed payload storage
Storing multi-megabyte payloads directly within sequential log envelopes quickly degrades storage engine performance and inflates write amplification. Content-addressed payload storage9 solves this by decoupling event metadata from bulk data: large payloads reside in dedicated blob storage, identified and verified by cryptographic content digests. Under this scheme, an event envelope remains compact, recording only the payload’s content digest, byte length, schema format, and storage location, alongside the bounded observation delivered to the agent model and its omission metadata. If that delivered observation is also offloaded to separate blob storage, it becomes a required recovery dependency as well.
9 Content Addressing: Venti used a hash of each block’s contents as its identifier, which made stored blocks write-once and let duplicate copies coalesce into one (Quinlan and Dorward 2002). Coalescing is what lets many trajectories over the same repository share a workspace base, and it is also why deletion must track references across tasks rather than per task.
For bounded observations, the tool contract governs what the runtime captured, what it omitted, and what remains accessible through subsequent reads. While an unparsed raw tail might be optional for a particular replay target, a file delta, model input, or result body consumed by a state reducer cannot be treated as optional simply because it is large.
↩︎ The truncation notices and inspection handles that record what a bounded observation omitted, and what stays retrievable, are established in Truncation notices and inspection handles.
Write ordering between payloads and log envelopes is critical for durability. A required payload must receive durable write acknowledgment from the storage system before any committed event envelope or checkpoint publishes a reference to it. Committing the reference first opens a crash window: if the worker fails while the payload write is still in flight, the log survives but records a dangling reference to missing bytes.
Upon retrieval, the runtime validates cryptographic integrity and checks tenant access permissions, because a content digest identifies stored bytes without granting permission to read them. Content addressing naturally deduplicates identical payloads across trajectories, allowing multiple runs on the same repository to share an immutable base workspace. However, task-specific provenance, confidentiality, and retention policies must remain strictly decoupled from storage deduplication: a shared payload can be reclaimed only when no active retention contract across any trajectory requires it, so expiring one task’s logs never deletes another task’s required dependency. Separating envelopes, per-turn payloads, and workspace snapshots in this way also makes the retention bill straightforward to price, revealing which storage classes actually drive operational costs.
Napkin Math 11.2: The price of keeping every recovery input
Math: The log holds 30 \(\times\) (4 + 128) KB = 3.96 MB, and the workspace brings the total to about 54 MB. Retention costs 0.054 GB \(\times\) $0.023 per GB-month \(\times\) 12 months \(\approx\) 1.5 cents.
Result: About 0.7 percent of the attempt’s cost, of which the log alone is 0.05 percent.
Systems insight: A year of full recovery and replay retention adds under 1 percent to \(\AttemptCost\) in equation 1.2, and the workspace snapshot, not the log, is 93 percent of the bytes. The bill grows linearly with retention months and bytes per turn, so the effective lever is sharing workspace bases by content address across trajectories of the same repository; truncating the log saves almost nothing. Set retention by the recovery and replay promise, because pruning a required artifact forfeits a reconstruction claim to save 0.05 percent of an attempt.
11.8.3 Log compaction
Keeping every event from the start of a trajectory grows the log without bound even after a published checkpoint at sequence \(\CheckpointLogPosition\) has already captured record_R_ckpt and workspace ws_r18, yet deleting that earlier prefix while the checkpoint is still staging or an audit replay still depends on it breaks the runtime’s promises. Log compaction reclaims storage capacity safely by retiring the older prefix once a newer published checkpoint preserves the active state and all unresolved operations required by the current recovery contract. The retained suffix of subsequent events must connect seamlessly to the checkpoint’s exact committed sequence boundary. Before pruning any log records or referenced artifacts, the storage layer must verify both conditions: the replacement checkpoint and its dependencies are durable across the declared failure domain, and no active historical replay, auditing, or compliance obligation still depends on the older prefix.
Compaction preserves current recovery while deliberately shortening the historical replay horizon. Downstream systems cannot substitute a later agent context for an earlier one once the original inputs have expired. Similarly, squashing incremental workspace deltas into a single snapshot preserves the latest workspace tree while shedding intermediate revisions. A compaction policy must therefore explicitly define the surviving replay interval. An uncompacted event history grows monotonically with every turn, regardless of how tightly the agent manages its prompt token budget.
Systems engineers must not confuse log compaction with context compaction. Context compaction operates on prompt token budgets: when conversational history approaches model context limits, the runtime condenses prior turns and commits a Compacted event to the log. This event records the exact summary text delivered to subsequent model calls, preserving deterministic replay for future turns. The underlying historical events and payloads that generated the summary remain governed by their own retention policies rather than vanishing when the context window shrinks. Diagnostic telemetry can follow aggressive downsampling or retention rules; in contrast, recovery-critical events and payloads must remain bit-for-bit complete throughout their promised operational lifetime.
↪ Sampling and retention policies for diagnostic traces are developed in Trace Retention and Privacy.
11.8.4 The storage engine contract
A storage layer can quietly undermine durable execution if its ingestion mechanics ignore distributed failure modes. Consider an ingestion retry after a lost network acknowledgment, in which the retried batch carries a timeout ToolResult for test_r18 under an event identity that the store already holds with later success evidence. A plain uniqueness constraint (such as an ON CONFLICT DO NOTHING clause) keeps the stored record and silently drops the retried timeout. Ingestion must instead perform semantic deduplication, comparing the immutable envelope and payload against the stored record under a declared canonical encoding. An identical retry returns an acknowledgment for the existing record. A conflicting payload signals an integrity violation or a split-brain failure (two workers both acting as owner), not an idempotent duplicate, so it must raise an error or be recorded as a distinct event that the operation table evaluates. Deduplicating an event insertion, moreover, never deduplicates an external side effect that has already occurred.
The same discipline governs how the engine manages capacity and replication. When disk saturation or transient faults block new commits, the runtime must apply backpressure and stall the trajectory rather than proceed speculatively, and a bounded circular buffer may overwrite an older entry only after every recovery and replay contract has released it. Moving older logs to a cheaper cold tier obeys the same completeness rule: the local copy can be retired only after every referenced payload body, not merely its index entry, has arrived and been verified at the destination. Replication across nodes must preserve both prefix completeness and ownership provenance. A follower that receives records out of order may stage them in memory, but it can advertise a recoverable prefix only up to its first sequence gap, and whereas fresh appends must validate the active lease and fencing token to block zombie writes, replicated historical events keep their original worker provenance and timestamps rather than taking on the credentials of the replicating node.
At the physical layer, an append-only event model can sit on any storage engine that guarantees deterministic ordering. Key-value stores built on log-structured merge trees (LSM trees) (O’Neil et al. 1996), for example, index immutable events under composite trajectory and sequence keys. In an LSM tree, storage-level compaction periodically merges the tree’s sorted on-disk files (sorted string tables) to reclaim space and speed reads. Despite the shared name, it is purely physical. It reorganizes bytes without changing the logical sequence of events, so unlike log compaction it never retires evidence. Overwriting an existing event with a newer state representation, by contrast, is a destructive application-level mutation, permissible only when a retention contract authorizes discarding the older evidence, because the order of observations and decisions is the agent’s causal chain.
Each cost derived earlier in the chapter therefore becomes a concrete requirement when selecting or configuring the storage engine. On the write path, the durable-acknowledgment boundary (local disk, quorum fsync, or multi-region replication) sets both the dispatch latency floor of table 2 and the batch wait of equation 2, while the engine’s internal write amplification multiplies the snapshot bytes that equation 3 already counts, and its blob-store integration determines whether the payload-before-reference ordering of section 11.8.2 can be enforced in one place. On the recovery path, sequential read throughput governs the suffix read time \(\CheckpointSuffixReadTime\) in equation 7, while atomic compare-and-set support on the owner_epoch determines whether the log itself can reject a stale owner’s appends without an external lock hop.
A single relational or key-value store suffices for modest deployments. At higher throughput, architectures often split into an online recovery store for low-latency point lookups by trajectory and an offline analytical store for columnar scans over historical replays. The analytical copy may lag the primary only while a durable, synchronized copy already satisfies the recovery contract within the declared failure domain, and every additional copy needs its own prefix synchronization, completeness verification, and retention policy.
Checkpoint 11.4: Retention is a recovery promise
Retention completes the reconstruction contract by guaranteeing that committed evidence and required artifacts remain accessible after a failure. A storage engine faithfully preserves recorded uncertainties, but determining whether an external operation actually succeeded or produced correct side effects requires active reconciliation. Resolving in-flight ambiguities and reconciling orphan operations belong to effect-recovery policy, not to the storage engine.
11.9 Fallacies and Pitfalls
Building durable agentic systems demands clarity about what persistent state actually guarantees. The most consequential engineering mistakes confuse a surviving record with evidence it cannot provide, or expend heavy recovery effort where structured logging has already eliminated the need.
Fallacy: Saving the final context window is enough to audit or recover a trajectory.
A model’s final context window represents only the transient view passed to the last inference call, filtered through compaction policies and bounded observation budgets. It omits the operational decision history: which candidate proposals were admitted, which intents became durable, and which raw tool observations arrived and were subsequently summarized away. For example, if a tool returns an exposed credential at turn 7 and a compaction pass replaces that observation with an abstract summary at turn 12, the final context retains no trace of the leak. Comprehensive auditing and reliable crash recovery require the append-only event sequence defined in table 1. From an authoritative log with the required retained payloads, the execution engine can deterministically rebuild each captured past context window, whereas a surviving context window lacks the operational history needed to reconstruct the log.
Pitfall: Checkpointing after every turn to be safe.
Naively snapshotting full agent state after every turn introduces severe latency overhead for minimal operational gain. When turn-by-turn events and workspace mutations are already appended to a durable log, taking a full checkpoint only reduces replay time during recovery, yet it forces execution to pause on every step. In the crash trace of notebook 11.1, checkpointing after each of the 100 turns spends 52 s in cumulative capture and recovery time, compared to 6 s for a 25-turn stride. Engineers should tune this cadence with the logged balance of equation 5, grounding the calculation in the per-turn log reconstruction cost rather than the much slower runtime of live re-execution.
Fallacy: Rerunning the model at temperature zero reproduces a trajectory.
Greedy decoding fixes only the argmax token-selection rule for a given logit distribution, and the serving path that computes those logits is not numerically deterministic (Repetition and replay). Because autoregressive generation conditions every token on all preceding tokens, a single flipped token early in execution steers the entire subsequent trajectory into a different subspace.
Across multi-step agent horizons, trajectory reproduction compounds multiplicatively (equation 1.1). Even under the optimistic assumption that individual greedy calls reproduce their recorded outputs 99 percent of the time, a 30-turn trajectory matches its recording end to end only 74 percent of the time. That estimate ignores external non-determinism such as shifting system clocks, generated identifiers, and mutating external environments. Rerunning an agent prompt creates an entirely new execution trajectory that generates fresh side effects; reliable reproduction requires replaying the exact model completions and tool results recorded in the log.
Pitfall: Using an incomplete replica to conclude that a call was never sent.
In distributed systems, the absence of an event record in a replica does not prove that an action never took place. When recovery logic evaluates whether to re-dispatch an unconfirmed operation after a crash, inspecting an asynchronous read replica or diagnostic log can lead to duplicate side effects. If replication lag delays the arrival of an acknowledged intent, recovery logic reading that replica might incorrectly assume the request was never transmitted, even though the crashed worker had already dispatched the RPC to an external service. Re-dispatching on that false assumption duplicates external mutations. Recovery engines must verify prefix completeness directly against the authoritative, strongly consistent store before treating the absence of an intent as evidence of non-dispatch.
Fallacy: A durable intent, or a newer ownership epoch, makes an unresolved operation safe to settle or repeat.
Writing an intent record before dispatch guarantees that an operation is tracked, but it does not resolve the state of an in-flight network request. When an agent crashes with an operation marked in-flight, a missing response or recorded timeout leaves the physical outcome fundamentally ambiguous. The crash might have occurred before the packet left the network interface, or after the remote service processed the mutation but before the acknowledgment arrived. Similarly, advancing an ownership epoch fences zombie workers from committing further updates to internal databases, but an epoch token cannot retroactively cancel a request already delivered to an external endpoint. Resolving an unconfirmed operation requires positive evidence obtained through the remote service’s inquiry API, and repeating it requires the endpoint’s idempotency contract; settlement before retry (principle 8) applies after a crash exactly as it does after a timeout.
Pitfall: Resuming a recovered trajectory on whichever server is free.
Reconstructing an agent’s memory by folding an event log requires minimal CPU time and consumes no model tokens. Teams often make the mistake of budgeting recovery purely around log deserialization, scheduling the resumed agent on whichever inference node happens to report idle capacity. However, moving to a server without compatible cached state discards KV-cache locality. When the resumed agent issues its next model call, the target accelerator must recompute the attention state across the entire reconstructed context window. For a 32,768-token context on the reference model and accelerator, this cold prefill phase alone imposes a latency floor of roughly 2.3 s, even before accounting for network queueing delays. Prefix-aware dispatch compares the avoided prefill work against queueing, transfer delay, and capacity at eligible workers (equation 7), while preserving the exact prefix during prompt assembly.
11.10 Summary
Durable execution enforces a strict separation between what an agent runtime can verify locally and what actually transpires across external network boundaries. A runtime knows its own decisions, the dispatches it initiated, and the observations it received, provided each event reached storage provisioned to survive the declared failure domain before any dependent action occurred. What the runtime cannot deduce from internal logs alone is whether a dispatched request that yielded no response took effect in the outside world. Every mechanism examined in this chapter maintains this critical boundary. Durability must always be stated relative to a specific, named failure domain; event log reconstruction replaces expensive model re-execution across recorded history; and ambiguous external outcomes remain explicitly assigned to an owner rather than resolved through speculative retries or uncoordinated model invocations. Providing these guarantees incurs concrete, quantifiable systems costs: a write acknowledgment per external dispatch, a brief coordination pause during checkpointing, a prompt prefill during cold resume, and about 1.5 cents per trajectory for a year of retention. Each overhead can be measured, budgeted, and amortized rather than avoided, and table 7 summarizes the governing relations that enforce dispatch ordering and balance checkpoint frequency against resume latency.
| Equation | What it bounds or decides | Where derived |
|---|---|---|
| \(\ProjectedTrajectoryRecord_j = \text{fold}(\ProjectedTrajectoryRecord_0, \LoggedEventPrefix)\) | Rebuilds state at log boundary \(\LogPositionIndex\) deterministically from recorded events without repeating model inference or tool invocations | section 11.2 |
| \(\ValidatedProposalEvent \prec \AdmissionDecisionEvent \prec \IntentAcknowledgmentEvent \prec \ExternalDispatchAction \prec \EvidenceRecordEvent\) | Enforces that external dispatch occurs only after intent is acknowledged within the declared failure domain, setting the dispatch latency floor | equation 1 |
| \(\GroupCommitWaitTime = \DurableAcknowledgmentTime - \QueueArrivalTime\) | Bounds latency under group commit, where each request waits for the shared flush while storage write cost divides across \(\CommitBatchRecordCount\) | equation 2 |
| \(\FullSnapshotWriteVolume = \TurnStateGrowth\,\CheckpointStride\,\frac{\TrajectoryCheckpointCount(\TrajectoryCheckpointCount+1)}{2}\), \(\IncrementalSnapshotWriteVolume = \TurnStateGrowth\,\CheckpointStride\,\TrajectoryCheckpointCount\) | Quantifies write amplification: full snapshots write \((\TrajectoryCheckpointCount+1)/2\) times the bytes of delta chains, which trade write volume for replay cost | equation 3 |
| \(\OptimalCheckpointInterval \approx \sqrt{2\,\CheckpointWriteTime\,\MeanTimeBetweenFailures}\) | Computes the optimal checkpoint interval when failures lose work that must be re-executed; overhead at the optimum is \(\sqrt{2\,\CheckpointWriteTime/\MeanTimeBetweenFailures}\) | equation 4 |
| \(\CheckpointRecoveryOverheadTime(\CheckpointStride) = \StrideCheckpointCount_k \CheckpointWriteTime + \TraceCrashCount \CheckpointRestoreTime + \TurnReconstructionTime\sum_i \LostSuffixTurnCount(\CheckpointStride)\), \(\CheckpointStride^* = \sqrt{2\CheckpointWriteTime/(\TurnFailureRate \TurnReconstructionTime)}\) | Derives optimal checkpoint stride under event logging, expanding the stride by \(\sqrt{\TurnReexecutionTime/\TurnReconstructionTime}\) because log replay replaces model re-execution | equation 6, equation 5 |
| \(\ResumeTime = \OwnershipAcquisitionTime + \CheckpointSuffixReadTime + \SuffixFoldTime + \WorkspaceRestoreTime + \OperationReconciliationTime + \PrefillTime\) | Provides a serial-stage recovery budget; overlapping stages contribute through their dependency critical path, and cold prefill is required when compatible KV state is unavailable | equation 7 |
Key Takeaways: Preserve the evidence needed to continue
- The event log, rather than the LLM context window, serves as the authoritative recovery record: A deterministic reducer folds recorded decisions, delivered inputs, and resource reservations back into the trajectory’s control state. In the event of a crash, recovery incurs the modest CPU cost of local log reconstruction rather than invoking redundant, nondeterministic model turns. The prompt context is merely a transient view assembled from this underlying history, and cannot reconstruct past state on its own.
- Durability is meaningful only relative to a declared failure domain: An acknowledgment guarantees persistence only against the specific faults its underlying storage tier is provisioned to survive. Because the runtime must hold external dispatch until the intent is acknowledged, the write latency of that storage layer establishes the performance floor for every dispatch. An absent intent record proves that no dispatch took place only when the surviving log history can be verified as complete.
- Fine-grained event logging shifts the checkpoint optimum: Classical checkpoint cadence balances capture overhead against lost execution time. Because replaying a deterministic event log is orders of magnitude cheaper than invoking new model calls, logging each turn lengthens the optimal checkpoint stride by the square root of the re-execution-to-reconstruction cost ratio, a factor of 14.1× in the worked trace. Because the cost curve is broad and flat around this minimum, choosing a stride within a factor of 2 raises the cadence-dependent overhead by at most 25 percent.
- Resuming an agent requires acquiring authorization rather than merely restoring memory: Reconstructed state explains why past decisions occurred, but the ownership lease, the fencing epoch, remaining token allowances, and human approvals govern subsequent actions. Any in-doubt external side effects and financial liabilities transfer intact to the new worker. A worker retaining compatible KV state avoids prefix recomputation, but the placement decision also depends on queueing, transfer delay, and capacity.
- Deterministic replay serves a different diagnostic purpose than a live rerun: In regression replay, the test harness feeds recorded inputs back into the agent logic with live tool execution disabled, isolating the exact state boundary where behavior diverges. Conversely, re-running an agent against live models generates an entirely new trajectory; because model sampling and external environments drift, divergences during a rerun cannot isolate where the original execution went wrong.
- Retention policies must reflect operational guarantees rather than raw storage costs: Fast crash recovery, regression replay, and post-incident auditing require different artifacts over distinct operational lifetimes. Long-term object storage is inexpensive. In the worked estimate, retaining every recovery and replay input for a full year costs about 0.7 percent of a single attempt. Eagerly pruning intermediate artifacts saves negligible budget while permanently forfeiting the ability to verify or reconstruct past runs.
The principle of intent before effect (principle 11) mandates writing an immutable record to durable storage before any external dispatch leaves the host, with durability calibrated against the failure domain the system claims to tolerate. Checkpoints and retained execution artifacts make this internal state reconstructible, while leaving in-doubt external outcomes explicitly visible to recovery supervisors. This discipline preserves the precise evidence that an automated or human recovery decision requires, while leaving the choice of recovery action to a separate policy that reads it. That separation also delineates the mechanical boundary of invariant closure (principle 1). The runtime can guarantee that no admitted effect escapes unrecorded and that no settled effect repeats without an explicit idempotency contract. However, local logs alone cannot determine whether an in-doubt external request succeeded across the network, nor can they judge whether a historically recorded action was semantically correct.
11.11 Historical Perspective and Further Reading
Every mechanism in this chapter answers a question that transaction processing confronted first: how a system that crashes mid-update can determine afterward what work had already escaped. In his foundational 1978 notes on database operating systems, Jim Gray established the write-ahead log as the record from which recovery reconstructs committed work, while introducing the two-phase commit protocol to coordinate atomic updates across autonomous resource managers (Gray 1978). As databases moved into main memory, writing that log to stable storage emerged as the primary throughput bottleneck. DeWitt and colleagues addressed this limitation with group commit, amortizing disk synchronization barriers across concurrent transactions (DeWitt et al. 1984). Mohan and colleagues turned write-ahead logging into a comprehensive recovery discipline with ARIES (Mohan et al. 1992). ARIES established the rule of forcing each log record to stable storage before writing the modified page to disk, and it introduced the principle of repeating history on restart: the recovery manager reconstructs the exact state at the crash before undoing uncommitted changes. Gray and Reuter subsequently synthesized the formal transaction model, logging architectures, and crash recovery into a definitive treatise (Gray and Reuter 1992). Modern storage engines took this logic a step further by elevating the log from an auxiliary recovery file to the primary storage structure. Rosenblum and Ousterhout established this design with the Log-Structured File System (LFS), converting all file modifications into sequential append operations (Rosenblum and Ousterhout 1992). O’Neil, O’Neil, and Weikum later adapted that concept to database indexing with the log-structured merge-tree (LSM-tree) (O’Neil et al. 1996), establishing the append-only storage patterns that modern trajectory stores rely on today.
A parallel lineage originated in high-performance computing and distributed systems, where jobs ran for days across fragile clusters and any node failure risked restarting computations from scratch. Young modeled the trade-off between the overhead of writing state snapshots and the cost of lost work, deriving an optimal checkpoint interval that remains the benchmark formula today (Young 1974). When computations spanned multiple communicating processes, capturing state became a distributed consistency problem. Chandy and Lamport solved this by defining snapshot consistency without freezing system execution (Chandy and Lamport 1985). Building on this foundation, the rollback-recovery literature demonstrated that combining periodic state snapshots with an event log of nondeterministic inputs guarantees deterministic replay, eliminating the need to re-execute expensive computations from the beginning (Elnozahy et al. 2002). Distributed environments also required explicit primitives to coordinate ownership and prevent split-brain execution during failover. Gray and Cheriton introduced time-bounded leases so that a crashed lock holder could not permanently block other workers (Gray and Cheriton 1989). Burrows introduced generation-stamped lock sequencers in Chubby, enabling external resources to reject requests from stale or zombie workers (Burrows 2006). Meanwhile, consensus protocols based on replicated state machines, from Lamport’s Paxos (Lamport 1998) to Ongaro and Ousterhout’s Raft (Ongaro and Ousterhout 2014), guaranteed that committed log records survive node crashes as long as a quorum persists. Capturing nondeterministic inputs also became a powerful tool for systems debugging: time-traveling virtual machines recorded external interrupts and network packets to replay operating system states deterministically backward and forward (King et al. 2005).
Agent runtimes synthesize these two lineages, yet they operate under distinct operational constraints that fundamentally alter what recovery can promise. In an agent loop that interleaves model reasoning with tool invocations (Yao et al. 2023), the dominant nondeterministic event is the model’s generated output. Because stochastic token sampling and remote model endpoints cannot be assumed to reproduce identical outputs upon re-evaluation, the runtime cannot simply restart the agent loop from the beginning; it must log every generated prompt and completion as an immutable event. External tool execution introduces an even sharper departure from classic transaction processing: external endpoints do not participate in two-phase commit. When an agent invokes a web search, dispatches a payment API request, or modifies an external code repository, there is no prepare phase to hold resources in doubt, nor any global rollback coordinator to undo side effects. Large-scale distributed architectures encountered this same boundary decades earlier. Pat Helland articulated why cross-boundary distributed transactions fail at scale, showing that independent entities must instead communicate through idempotent messages, explicit sequence tokens, and compensating workflows (Helland 2007). Modern durable execution frameworks translated these distributed messaging guarantees directly into programming models: Burckhardt and colleagues provided a formal operational semantics for durable workflows that advance persistent progress without re-executing completed side effects (Burckhardt et al. 2021). In an agent architecture, these concepts become three concrete runtime mechanisms: the durable intent (recording planned actions before execution), the in-doubt state machine (reconciling unknown tool outcomes before retry), and the strict separation between trajectory reconstruction (rehydrating memory from historical logs) and live execution against the external world.
For further reading, six works trace the lineage from database recovery to modern agent runtimes:
- Gray and Reuter (1992) remains the definitive foundation for transaction processing, logging architectures, and crash recovery. Its rigorous analysis of what a commit guarantee actually promises, and across which specific failure domains that promise holds, provides the conceptual model for the failure-domain contracts developed throughout this chapter.
- Mohan et al. (1992) delivers the complete specification for write-ahead logging and recovery. Studying ARIES clarifies precisely which consistency guarantees depend on owning the underlying storage pages, a structural guarantee database engines take for granted, but one that agent runtimes forfeit when interacting with external tool endpoints.
- Elnozahy et al. (2002) organizes decades of distributed checkpointing and message logging research into a coherent taxonomy. The survey highlights why capturing nondeterministic inputs changes what a checkpoint must record, establishing the theoretical basis for deterministic trajectory replay.
- Kleppmann (2016) connects classical principles of event sourcing, log replication, and distributed fencing to the realities of production infrastructure. It bridges distributed systems theory and the practical engineering of a scalable trajectory store.
- Helland (2007) explains why large-scale distributed systems abandon atomic transactions across autonomous administrative boundaries in favor of idempotent, uniquely identified messages. Its practical reasoning directly anticipates the in-doubt action lifecycle and settlement-before-retry protocols required by agent runtimes.
- Burckhardt et al. (2021) provides a formal operational semantics for durable execution and asynchronous workflow runtimes. It establishes how persistent progress can be mathematically specified and verified, showing how runtimes ensure exactly-once execution semantics across process crashes without manual state machine management.
11.12 Exercises
Each problem states its constraints and ends in a decision about what to record, when to checkpoint, or how to resume. Givens are hypothetical problem inputs unless a lighthouse profile supplies them, and none describes a particular store, model, or service.
1. Pricing the durable acknowledgment (Basic). A repair worker makes 40 tool dispatches over 40 turns, and each turn otherwise spends 4 s on model and tool work. Its store offers three acknowledgments: a returned write() after 0.02 ms, a returned fdatasync() after 0.4 ms, and a replicated append that a three-replica store acknowledges once two replicas hold the record durably. Measured from the append, the replicas become durable after 1.5, 2.5, and 6.5 ms, and the 1.5 ms replica keeps its copy on the worker’s own volume. For this problem, the worksheet requires both off-volume replicas to hold durable copies before dispatch.
Give the acknowledgment latency that satisfies each of the first two rows of table 2. Under this additional placement policy, identify the required copies and compute the resulting acknowledgment latency. What fraction of the trajectory’s elapsed time does that acknowledgment add? A colleague proposes ordinary majority commitment using the co-located replica and one off-volume replica. Compute the saving, distinguish the single-volume-loss guarantee from the chosen placement policy, and decide whether adopting that policy change satisfies the stated contract.
2. Write amplification of a growing record (Basic). A repair trajectory runs 400 turns, its checkpointed record grows by 64 KB per turn, and a checkpoint is published every 8 turns.
Use equation 3 to compute the bytes written by full snapshots and by deltas, and their ratio. Restore reads at 200 MB/s, and each delta in a chain adds 20 ms of fetch, validation, and application beyond its bytes. Starting from an empty base, compare the time to restore the state at the final checkpoint from one full snapshot and from the chain of deltas. Which representation suits a trajectory that rarely crashes, and which mechanism bounds its weakness?
3. Checkpointing too often (Basic). A long local analysis step inside a trajectory keeps intermediate state that the log does not capture, so a crash forces its work to be re-executed. Each checkpoint pauses execution for 3 s, including durable publication, and work-losing failures arrive on average every 30 minutes.
Compute \(\OptimalCheckpointInterval\) and the overhead at the optimum from equation 4. The current policy checkpoints every 10 s. Compute its overhead and the factor by which it exceeds the optimum. A second proposal checkpoints every 200 s to cut pause time. Compute its overhead, decide between the two proposals, and explain from the shape of the overhead curve why the comparison depends on the ratio to \(\OptimalCheckpointInterval\) rather than on the direction of the error.
4. Group commit against a dispatch budget (Intermediate). A harness admits 2,000 intents per second, arriving evenly every 0.5 ms. Its replicated store takes 5 ms per durable flush regardless of batch size. A batch starts its flush as soon as it holds its last intent and the store can accept a flush. The dispatch budget allows at most 8 ms from an intent’s arrival to its acknowledgment.
Without batching, with one flush at a time, what intent rate can the store sustain, and what happens to the queue? Find the smallest batch that keeps up, and use equation 2 to compute the steady-state waits of a batch’s first and last arrivals. Does that policy meet the budget, and how much utilization margin does it leave? The store can instead keep two flushes in flight at once. Recompute the smallest batch, its first arrival’s wait, and the amortized storage work per intent. A teammate suggests acknowledging from the page cache and flushing in the background. Evaluate the suggestion against the design rule that closes section 11.3.
5. What logging buys the cadence (Intermediate). A trajectory’s checkpoint write time is \(\CheckpointWriteTime = 0.8\) s, and crashes arrive at failure rate \(\TurnFailureRate = 0.01\) per completed turn. Reconstructing a logged turn costs \(\TurnReconstructionTime = 0.05\) s, and re-executing an unlogged turn costs \(\TurnReexecutionTime = 12\) s.
Compute \(\CheckpointStride^*\) for a fully logged and a fully unlogged trajectory, and their ratio. Show that the per-turn overhead at the optimum is \(\sqrt{2\,\CheckpointWriteTime\,\TurnFailureRate\,\TurnReconstructionTime}\) and evaluate it for the logged case. An audit then finds that 10 percent of turns write workspace files the log does not capture; in a lost suffix each such turn costs \(\TurnReexecutionTime\) and every other turn costs \(\TurnReconstructionTime\). Compute the effective per-turn cost, the new \(\CheckpointStride^*\), and the overhead of keeping the logged stride. Which investment lowers overhead more, retuning the stride or capturing the missing workspace deltas? Justify the choice with the three overheads.
6. Second lighthouse: mass resume for the support agent (Intermediate). The support agent holds many short sessions at once. Each session’s context is 8,192 tokens, of which 6,144 form a policy prefix shared by every session, and a customer takes about 20 s to read a reply and answer. A serving region fails, and 2,000 open sessions must resume on surviving workers. Per session, acquiring ownership takes 20 ms, reading and validating the checkpoint and suffix 15 ms, and folding 5 ms. There is no workspace to restore, because the customer record stays in its system of record, but 10 percent of sessions hold an in-doubt refund whose authorized lookup takes 150 ms. One request prefills at 20,000 tokens/s, and the surviving pool prefills 400,000 tokens/s in aggregate. The failover may add at most 1 s to any customer’s next reply.
Use serial stage execution for the per-session estimate. Apply equation 7 to compute \(\ResumeTime\), excluding queueing, for a clean session and for one with an in-doubt refund, first with a cold prefill and then with the shared prefix already resident on every surviving worker. If every session resumes eagerly with a cold prefill, how long does the pool take to drain the prefill work, and with the shared prefix resident? Treat customers’ next messages as arriving evenly over the following 20 s. Propose a resume policy that meets the 1 s bound, compute its prefill load as a fraction of the pool, and state what it does with the in-doubt refunds. Contrast the binding term with the one that governs the repair trajectory’s resume.
7. Second lighthouse: retention for the research agent (Intermediate). The research agent runs 20 turns and fetches 100 external pages. Per turn it logs 4 KB of event envelopes and 40 KB of delivered, bounded observations. Each fetched page averages 300 KB raw, and the model receives only the bounded observation. Storage costs $0.023 per GB-month, the replay promise is 12 months, and one attempt costs $1.50.
Compute a year’s retention cost for the recovery and replay inputs and for the raw pages, each as a share of the attempt cost. An investigator later asks which text the model received before producing a suspicious citation. Decide whether folding the recorded projection, a harness regression replay, or a fresh rerun of the trajectory establishes the delivered input, name the earliest boundary to compare and the retained bytes it needs, and explain why neither the raw pages nor the rerun can settle it. State what that evidence cannot establish about the text’s causal influence, and what a controlled new branch would add. Propose retention lifetimes that keep raw pages for 1 month under a diagnostic policy, and compute the annual storage bill for one million trajectories under full retention and under the proposed policy. Explain how the dominant bytes, and the reason for retaining them, differ from the repair trajectory’s in notebook 11.2.
8. An asynchronous replica behind an irreversible actor (Advanced). A fleet of 50 remediation workers each dispatch approved changes at 2 per hour, at random times, after an approval wait of about 15 minutes. Each worker acknowledges intents with a local fdatasync() and ships them to a remote store that lags by 200 ms. After a failure, the replacement reads the remote store and dispatches every approved proposal that lacks an intent. Each worker suffers 2 volume-losing failures per year, and a duplicated change costs $12,000 in expected damage. The alternative acknowledges from a quorum outside the worker’s volume at 6.5 ms per dispatch.
Identify the rules of section 11.3 that the recovery procedure violates, and state the recovery state that operations in the lag window should occupy instead. Treating dispatches as a Poisson process, compute the probability that a failure follows within 200 ms of at least one dispatch, the expected number of such failures per year across the fleet, and the expected annual loss if each produces a duplicate change. Repeat for a network partition that stretches the lag to 60 s. Compute the latency the quorum alternative adds per worker per day, and per change as a fraction of the approval wait. Redesign the acknowledgment and recovery path, and defend why neither acknowledgment latency nor the small expected loss at 200 ms is the right quantity to optimize for this lighthouse.
9. Consolidating a delta chain under a resume deadline (Advanced). A repair trajectory publishes an incremental checkpoint at every stride and, every \(\ConsolidationStride\) checkpoints, consolidates the chain by writing and publishing a new base, which pauses execution for 1.0 s. The chain therefore holds between 1 and \(\ConsolidationStride\) deltas. A restore reads the base in 0.2 s and spends 0.04 s on each delta in the chain. The probability that a restore is needed between two consecutive checkpoints is 0.005.
Write the expected overhead per checkpoint \(\ConsolidationOverheadTime(\ConsolidationStride)\) as a consolidation term plus an expected restore term, taking the chain length at a crash to average \(\ConsolidationStride/2\). Find \(\ConsolidationStride^*\) and \(\ConsolidationOverheadTime(\ConsolidationStride^*)\) by the method of theorem 11.1, and compute the worst-case restore time at \(\ConsolidationStride^*\). Resume now must finish restoring within 2 s in the worst case. Find the largest admissible \(\ConsolidationStride\) and the overhead the deadline costs relative to \(\ConsolidationOverheadTime(\ConsolidationStride^*)\), and check the ratio of the \(\ConsolidationStride\)-dependent terms against the flat-minimum form \((\OptimumMissFactor + 1/\OptimumMissFactor)/2\). When a consolidation publishes a new base, which older deltas and bases may compaction delete, and what must be verified first?
What’s Next: From reconstructing the record to repairing effects
test_r18 job whose outcome is still unknown, decide whether revising candidate r18 is worth another attempt, or tear down an environment that a lost reply left running and billing. Failure Recovery turns the recorded evidence and unresolved obligations into recovery policy: retries that an endpoint’s repeat contract permits, bounded forward repair, compensations registered before the effects they undo, and escalation to an operator, together with watchdogs that stop trajectories which fail without raising any error.