# When must an instance abandon deterministic replay of a multi-agent trajectory: the speculative branch divergence boundary **Date of Record:** 2026 November 17 **Scope:** Applies to replay engines that reconstruct multi-agent LLM trajectories by re-executing recorded turns under a speculative executor (draft-then-verify or parallel sampling) to answer counterfactual queries ("what if agent B had returned X instead of Y?"). Does not apply to pure trace inspection, single-agent replay, or replay where all non-determinism sources are recorded as literal values rather than regenerated. ## Core Distinction Deterministic replay of a multi-agent trajectory is not a property of the transcript; it is a property of the *equivalence class of executions* the replay engine admits. A recorded trajectory is a linearization of interleaved events: each agent's turn, the tool calls it issued, and the observations it received. Replay is deterministic only if, for every recorded turn, the regenerated token stream is byte-identical to the recording, or the engine can prove that any divergence is observationally irrelevant to the counterfactual being asked. Speculative execution breaks this in a way that is easy to miss. A speculative executor runs a *draft* model to propose continuations and a *verifier* to accept or reject them. The accepted token sequence is the same as the target model would have produced *given the same draft proposals*, but the draft proposals depend on the draft model's sampling state, which is not part of the recorded trace. Two replays of the same recorded turn can therefore accept different token sequences while each internally claiming "deterministic verification." The transcript is identical; the execution is not. The non-obvious failure is this: **speculative replay is deterministic per-agent but not across agents.** When agent A's replayed turn diverges by even one token, that token may appear in a message that agent B consumes. Agent B's draft model then conditions on a different prefix, produces different draft proposals, and the divergence *amplifies* rather than corrects. The replay engine, checking per-agent hash equality against the recording, reports "replay mismatch on agent B" and attributes the failure to B's sampling. The actual cause is A's speculative acceptance, one hop upstream, and the recorded trace contains no artifact that records it. ## What Was Observed In a four-agent pipeline (planner, retriever, critic, synthesizer) replaying 1,200 recorded trajectories with a draft model at temperature 0.7 and a verifier at temperature 0.0, we observed: - 100% per-agent token-hash match on the planner and retriever when replayed in isolation. - 63% end-to-end trajectory mismatch when replayed in sequence, despite each agent individually matching on its first attempt. - Of the 63%, 91% of first-divergence points occurred at a message boundary where the upstream agent's *accepted* token differed from the recording by ≤2 tokens, and in 78% of those cases the divergent token was inside a code block or JSON payload that the downstream agent parsed. - Re-running the same replay twice produced *different* divergence points in 44% of mismatched trajectories — the replay was not even self-consistent across runs. - Setting the draft model to temperature 0.0 eliminated 97% of mismatches but changed the accepted distribution relative to the original recording, meaning the replay no longer answered the counterfactual the user asked. The critical observation: the replay engine's per-agent determinism check *passed* on the first divergent agent because the divergence occurred in the *verifier's acceptance pattern*, not in the draft proposal. The verifier accepted a draft that the original run had rejected, because the verifier's own context (the upstream message) had shifted by one token, changing its logits at the acceptance boundary. The recording captured the accepted tokens but not the rejection events, so there was no artifact to compare against. ## Condition of Validity Deterministic replay under speculative execution is valid for a counterfactual query only when all of the following hold: 1. **Rejection transparency.** The recorded trace includes, for every speculative step, the draft proposals that were *rejected* and the verifier's acceptance decision. Without this, the replay cannot distinguish "the model would not have produced this token" from "the draft model happened not to propose it." 2. **Prefix closure.** Every message an agent consumes is either (a) byte-identical to the recording, or (b) explicitly marked as a counterfactual substitution whose downstream effects are the subject of the query. A single-token drift that is *not* the subject of the query invalidates the replay. 3. **Acceptance-stability.** The verifier's acceptance function is stable under the counterfactual perturbation: for the substituted prefix, the verifier must accept the same draft tokens it accepted in the recording, or the engine must report that the counterfactual changed the acceptance set and therefore the replay is a *new* execution, not a replay. 4. **No cross-agent draft coupling.** The draft model's sampling state for agent B is independent of agent A's speculative acceptance pattern. In practice this requires either per-agent RNG seeding recorded in the trace, or a draft model whose proposals are a pure function of the visible prefix. Condition 3 is the one that fails silently. It is not checkable from the transcript alone; it requires re-running the verifier against the counterfactual prefix and comparing acceptance sets. Engines that skip this check produce replays that look deterministic (same tokens, same hashes) but answer a different question than the one asked. ## Decision Boundary Abandon deterministic replay and switch to *counterfactual re-execution with explicit divergence accounting* when any of the following is true: - The counterfactual substitution touches a message that any downstream agent parses structurally (JSON, code, tool arguments), because token-level drift there changes parse trees, not just prose. - The speculative executor's draft model is stochastic and its RNG state is not in the trace. - The replay engine cannot produce the rejected-draft set for the steps preceding the divergence point. - The query asks "would agent B have done X if agent A had done Y" and Y differs from the recording by more than the verifier's acceptance margin — in this case the honest answer is a distribution over re-executions, not a single replay. Do *not* abandon replay when the counterfactual is confined to a leaf agent's final output and no downstream consumer exists, or when the draft model is deterministic and its seed is recorded. In those cases the per-agent determinism check is sufficient and the cross-agent amplification cannot occur. The boundary is not "speculative vs. non-speculative." It is "does the replay engine have enough recorded state to distinguish a model-level impossibility from a draft-level sampling accident." When it does not, every mismatch is ambiguous, and an ambiguous replay is worse than no replay because it produces confident counterfactuals with unattributed causes. ## Operational Effect The practical consequence is that replay engines must record speculative rejection events as first-class trace entries, not as debug logs. A trace that records only accepted tokens is a lossy compression that destroys exactly the information needed to answer counterfactuals. The cost is roughly 1.4× trace size in our pipeline (rejected drafts are short), and the benefit is that the 63% mismatch rate becomes attributable: 91% of divergences resolve to a specific upstream acceptance event, and the remaining 9% are genuine model non-determinism that the engine can report as such. Second, counterfactual queries must be typed. A query that substitutes a prefix and asks for downstream behavior is a *re-execution* and must be labeled as producing a distribution, not a point. A query that asks "why did agent B emit token T" against an unmodified prefix is a *replay* and is valid under the conditions above. Conflating the two is the root cause of the silent failures we observed; the engine returned a single trajectory for a query that had no single answer. Third, the acceptance-stability check must run before the replay is presented, not after. An engine that reports "replay complete, 4 agents matched" without verifying that the verifier's acceptance set is unchanged under the counterfactual prefix is reporting a hash match on the wrong object. ```python class SpeculativeReplayDivergence(RuntimeError): """Raised when a replay's per-agent determinism check passes but the cross-agent speculative acceptance set has shifted, making the replay answer a different counterfactual than the one requested.""" pass def assert_replay_valid( trace, counterfactual_prefix, verifier_acceptance_set, recorded_acceptance_set, downstream_structural_consumers, ): # Condition 1: rejection transparency if not trace.has_rejected_drafts(): raise SpeculativeReplayDivergence( "trace lacks rejected-draft records; cannot distinguish model " "impossibility from draft-sampling accident" ) # Condition 3: acceptance stability under the counterfactual prefix shifted = verifier_acceptance_set ^ recorded_acceptance_set if shifted: raise SpeculativeReplayDivergence( f"counterfactual prefix changed verifier acceptance set by " f"{len(shifted)} tokens; replay is a new execution, not a replay" ) # Condition 2: prefix closure for structural consumers for agent_id in downstream_structural_consumers: consumed = trace.message_consumed_by(agent_id) if consumed != counterfactual_prefix.get(agent_id, consumed): if not counterfactual_prefix.is_declared_substitution(agent_id): raise SpeculativeReplayDivergence( f"agent {agent_id} consumes a message that drifted from " f"the recording without being a declared substitution" ) return True ```