Replay in multi-agent systems

Day 25: Replay Is the Line Between Determinism and Autonomy

A multi-agent system can fail once and then run cleanly through ten identical retries, even at temperature=0. When that happens you're left with a hunch and an incident report. You can't trust a system you can't audit, and you can't audit a run you can't reproduce. Today is about making every agent decision re-runnable step by step. That's what earns an agent more freedom.

Cold open: the Tuesday migration

We had three agents on a database migration. The planner split the work, the schema agent wrote the DDL, and the reviewer approved or rejected each step before it ran. Every model call used temperature=0. One Tuesday the reviewer approved a backfill against a column the schema agent had already renamed. We tried to reproduce it ten times with the same prompts, the same model and the same settings. It never happened again.

The prompts were fine. In the bad run, the reviewer received 'backfill ready' before 'column renamed'. In all ten retries, the async scheduler happened to deliver them the other way round. We had logged what every agent said, but not the order in which each agent heard things. Message ordering was the one variable we weren't recording.

The trap: arguing about sampling

Most 'determinism vs autonomy' debates get stuck on LLM sampling. The usual version: temperature=0 makes the system deterministic, and raising it makes the system autonomous. That's the wrong axis. Setting temperature=0 doesn't make a run reproducible, and there are three reasons:

• ▹The model isn't bit-stable. Hosted inference batches your request with other people's, and a different batch size changes the floating-point reduction order, so greedy decoding can still pick a different token. Providers also update weights, quantization and serving stacks behind the same model alias.
• ▹The world moves. Tool outputs change between runs: a DB query, a git diff, a search result, the current time. Your next prompt is built from those outputs.
• ▹The scheduler decides. In a multi-agent system, the scheduler picks which agent runs first and which message lands first. Two agents can each be correct and the system can still get the wrong outcome, just because their messages interleaved differently.

The reframe: ask 'can I replay this decision?'

Drop 'is the model deterministic?' and ask 'can I re-run this exact decision from logged inputs?' A decision is replayable if you can take the recorded context, tool outputs, message order and sampling params, walk the run step by step, and reach the same choice at every step.

Earlier in the series we designed how agents communicate (message schemas, protocols) and how they coordinate (orchestrators, shared state, handoffs). What's new today is that the run itself becomes an artifact. You store it, version it, diff it and test against it, just like code. The reasoning inside each step can be as non-deterministic as you like, as long as the step's outcome is captured.

What has to be captured: the replay envelope

The replay envelope is the smallest per-step record that lets you re-run a decision. Log this for every step:

• ▹Agent ID and role, plus the prompt/template version
• ▹The exact prompt, or a content hash of the full context window with a pointer to the stored blob
• ▹Provider, model name and pinned version or snapshot ID (an alias like 'latest' isn't enough)
• ▹Sampling params: temperature, top_p, max_tokens, and the seed if your provider supports one
• ▹Every tool call: name, arguments and the recorded response, byte for byte
• ▹Every inbound message, with a global sequence number, the sender and its causal parent (the event that triggered it)
• ▹The decision itself: which tool, which message, which handoff

{
  "run_id": "mig-2026-10-06-a41f",
  "seq": 212,
  "lamport": 57,
  "agent_id": "reviewer",
  "type": "model_call",
  "causal_parent": 205,
  "inbound": [
    {"seq": 205, "from": "planner", "kind": "backfill_ready"}
  ],
  "model": {"provider": "anthropic", "name": "claude-sonnet-5-5", "snapshot": "pinned-id"},
  "params": {"temperature": 0, "top_p": 1, "max_tokens": 2048, "seed": null},
  "prompt_template": "reviewer@v14",
  "context_hash": "sha256:9c1e...",
  "context_ref": "blob://runs/a41f/212/ctx",
  "output_ref": "blob://runs/a41f/212/out",
  "decision": {"action": "approve", "target": "step:backfill_users"}
}

Put the large blobs (context, outputs) in object storage, addressed by content hash, and keep the event log small and append-only. The seed is optional. Many providers don't honor one, and some reasoning models restrict or reject sampling params. That doesn't matter much, because exact replay uses the recorded output and doesn't regenerate anything.

Why multi-agent systems make this harder

A single-agent run is one sequence: prompt, tool, prompt, tool. When several agents run concurrently, each agent's local log can be perfectly replayable while the system as a whole is not. The logs don't record how the agents' timelines interleaved. To fix that you need a shared notion of 'happened before'.

Distributed systems people have worked on this problem for decades, and the standard tools apply here:

• ▹Global sequence number. A single sequencer, usually your message bus, stamps every event with a monotonically increasing number. It's the simplest option, and it's enough for most agent systems running in one process or one queue.
• ▹Lamport (logical) clock. Each agent keeps a counter and increments it on every event. When an agent receives a message, it sets the counter to max(own, received) + 1. This orders events consistently with causality, with no central clock.
• ▹Causal parent. Each event records which event triggered it. Your log becomes a causal graph, and you can answer questions like 'what did the reviewer know when it approved?'
• ▹Event sourcing. The log is the source of truth, and state comes from replaying events in order. Workflow engines like Temporal already work this way: they replay workflow history, require workflow code to be deterministic, and push non-deterministic work into recorded activities. Agents fit the same model, with model calls and tool calls as the recorded activities.

The agents, prompts and temperature are identical in both runs, and the outcomes differ. Only the order changed. If your log doesn't record order, you can't reproduce this bug.

Build it: a minimal event-sourced trace layer

There are three pieces: an append-only log, a message bus that stamps sequence numbers, and wrappers around the model and tools that record their responses. In replay mode the wrappers return the recorded outputs instead of making live calls. If the run asks for anything different from what was recorded, they raise an error immediately.

class Trace:
    def __init__(self, path, mode):              # mode: "record" | "replay"
        self.mode, self.seq, self.lock = mode, 0, Lock()
        self.recorded = load_jsonl(path) if mode == "replay" else None
        self.out = open(path, "a") if mode == "record" else None

    def step(self, ev, live_fn):
        with self.lock:                          # one sequencer for all agents
            self.seq += 1
            ev["seq"] = self.seq
            if self.mode == "replay":
                rec = self.recorded[self.seq - 1]
                if rec["key"] != ev["key"]:      # agent asked for something else
                    raise Divergence(self.seq, expected=rec, got=ev)
                return rec["output"]             # no live call
            ev["output"] = live_fn()
            self.out.write(json.dumps(mask_sensitive(ev)) + "\n")
            self.out.flush()
            return ev["output"]

def send(trace, sender, to, body, parent_seq):
    # delivery order is a recorded fact, not a scheduler accident
    k = key("msg", sender, to, sha(body))
    return trace.step({"type": "msg", "key": k, "parent": parent_seq},
                      live_fn=lambda: {"from": sender, "to": to, "body": body})

def call_model(trace, agent, prompt, params):
    k = key("model", agent, sha(prompt), params)
    return trace.step({"type": "model", "agent": agent, "key": k},
                      live_fn=lambda: llm(prompt, **params))

def call_tool(trace, agent, tool, args):
    k = key("tool", agent, tool, sha(args))
    return trace.step({"type": "tool", "agent": agent, "key": k},
                      live_fn=lambda: TOOLS[tool](**args))

Multi-agent replay needs one more thing, and it's the one people forget: the scheduler. In replay mode, don't let agents race. Drive them in recorded sequence order by stepping whichever agent owns the next event in the log. If you skip this, replay brings back the same interleaving bug you're trying to study. Frameworks with checkpointing, like LangGraph's persistence and 'time travel', cover part of this. Check that they record message order across agents, and not just per-graph state.

The replay test as a CI gate

Once runs are artifacts, you can test against them. Pick N production traces: some normal runs, your worst incidents and a few edge cases. Replay each one in CI and assert that every step produces the same decision key that was recorded.

• ▹If exact replay diverges, the bug is in your harness, not your agent. Some input wasn't captured, such as an unrecorded tool, a clock read, a random ID, an env var, or nondeterministic iteration over a dict or set. Keep fixing the capture until replay is clean.
• ▹Old traces will break when you change a prompt or the code, and that's expected. Treat them like snapshot tests: review the diff and re-record deliberately, never silently.

You need two kinds of replay:

• ▹Exact replay. Every model and tool output comes from the log. This proves the harness captures everything, and it lets you step through a run like a debugger. It's cheap and fast, with no live calls.
• ▹Counterfactual replay. Change one input (the message order, one tool response, the prompt version or the model snapshot) and replay with live model calls from that point on, then watch which decisions move. This answers questions like 'would the reviewer still have approved if the rename had arrived first?' and 'does the new model change approval behavior on last month's traces?'

Where autonomy fits back in

Once runs replay cleanly, you can stop constraining how an agent reasons. Let it choose its own path, call tools in whatever order it wants and run at a higher temperature to explore. You can still audit every path afterwards.

Link permissions to replayability. An agent gets merge rights, write access to production data or a wider tool set only after its runs pass the replay gate consistently. If its runs can't be replayed, it stays read-only or human-approved, however good its outputs look. Replay is what makes autonomy affordable: when the agent makes a mistake, you get a trace you can debug rather than a mystery you argue about.

What replay won't give you

• ▹It won't keep storage cheap. Full context windows and tool outputs grow quickly. Use content-addressed blobs, deduplicate shared context, and set retention tiers so incidents are kept longer than routine runs.
• ▹It won't keep sensitive data out of your logs. Prompts and tool outputs often contain personal data, credentials or confidential business data. Mask or tokenize sensitive fields before they're persisted, not afterwards. If replay needs the original value, use a reversible token vault with access controls and audit logs, and keep raw secrets out of the trace entirely.
• ▹It won't undo anything in the real world. Replay re-runs decisions, not side effects: the email was sent and the migration ran. Replay mode must never call live side-effecting tools, and real side effects still need idempotency keys, dry-runs and compensating actions.
• ▹It won't tell you the decision was right. Replay shows what happened and why, given the inputs. Judging whether the decision was correct still takes evals, invariants and human review.

Monday checklist

• ▹Can I reconstruct the exact message order each agent saw in yesterday's worst run?
• ▹Is every tool response recorded byte for byte, including the 'boring' ones like time, file listings and search?
• ▹Does the log pin the model to a snapshot or version, or does it only have an alias that can change silently?
• ▹Can I replay at least one production trace end to end in CI with zero live calls and zero divergence?
• ▹Are sensitive fields masked before the trace is written, and is access to raw traces restricted?

Bridge to Day 26

Replay tells you what happened. Tomorrow covers what should happen when things go wrong: how agents fail, time out, escalate and hand control back. The goal is for a failure to behave predictably, so you don't end up reconstructing another mystery.

Extend your knowledge

• ▹Leslie Lamport, 'Time, Clocks, and the Ordering of Events in a Distributed System' (1978). The original paper on logical clocks and happened-before.
• ▹Temporal documentation on workflow determinism and history replay. A production-grade example of event-sourced replay, with non-deterministic work isolated in recorded activities.
• ▹Thinking Machines Lab, 'Defeating Nondeterminism in LLM Inference' (Horace He, 2025). Explains why batching makes temperature=0 non-reproducible on hosted inference.
• ▹Exercise: add the Trace wrapper to your Day-series prototype, record five runs, and write a CI test that replays them with zero live calls. Then run one counterfactual by swapping two inbound messages.