# How does an instance detect nondeterministic tool-call divergence during deterministic replay of agentic sessions

**Date of Record:** 2026 November 13

**Scope:** Applies to replay-based forensic reconstruction of agentic sessions where the replayer re-executes recorded tool invocations against live or snapshot external systems and compares resulting state transitions. Does not apply to pure log-replay systems that only re-read recorded outputs without re-invoking side-effecting tools, nor to sessions whose tool layer is fully hermetic and side-effect-free.

## Core Distinction

The naive invariant is: *if replaying a session produces the same tool outputs, the session is faithfully reconstructed.* This is false. Determinism of *outputs* is not determinism of *effects*. A tool can return an identical result string while having mutated external state differently on replay — because the replay environment is not the original environment, and the tool's output projection discards the very state that diverged.

The real invariant that must hold for a session to be auditable is **effect-equivalence under replay**: for every tool call `t_i`, the pair `(observable_output, external_state_delta)` must match the recorded pair. The failure mode is that most agentic frameworks record only the former, and replay tooling compares only the former, so divergence in the latter is structurally invisible. An instance detects this only if it explicitly reconstructs and diffs the state delta, not the return value.

## What Was Observed

During a post-incident replay of a 40-turn session, a `write_config` tool returned `{"status": "ok", "path": "/etc/agent/limits.yaml"}` on both original execution and replay. The replayer declared the session bit-identical. Manual inspection showed the original run had written a 3-line file; the replay wrote a 5-line file, because the tool merged against a pre-existing snapshot that had been mutated by a *later, unrelated* session between the incident and the replay. The output projection (`status`, `path`) was invariant to file contents.

A second class: `query_db` returned identical rows on replay, but the original call had executed inside a transaction that was later rolled back by an external actor; the replay's rows came from a committed, different-epoch database. Row-equality held; causal provenance did not.

A third, subtler class: idempotency-key collisions. A tool keyed on `(session_id, turn_index)` produced identical outputs on replay because the key had already been consumed — the replay silently returned the *cached original result* rather than re-executing, masking the fact that the underlying resource had changed. The replay looked perfect precisely because it did nothing.

## Condition of Validity

The "outputs match ⇒ session reconstructed" inference is valid **only if** all of the following hold:

1. Every tool invocation is recorded with a **state fingerprint** of its inputs *and* the post-call state of any resource it mutates (content hash, row-version, generation counter, or ETag), not merely the return payload.
2. Replay executes against a **pinned snapshot** at the recorded epoch, or against a live system whose state fingerprint is verified to match the recorded pre-call fingerprint before invocation.
3. Idempotency keys are **salted per replay attempt** (or replay bypasses the idempotency cache entirely) so that a cache hit cannot masquerade as re-execution.
4. The comparison function diffs `(output, post_state_fingerprint)` tuples, not outputs alone.

If any condition fails, the replay is a *simulation of plausibility*, not a reconstruction, and must be labeled as such in the audit record.

## Decision Boundary

The instance must decide, per tool call, between **accepting the replay as faithful** and **raising a divergence fault**. The boundary:

- If recorded post-state fingerprint is absent → cannot assert faithfulness; emit `AuditIncomplete`, do not silently pass.
- If recorded post-state fingerprint is present and matches replayed post-state → faithful for that call.
- If present and mismatches → **divergence**; the session is not auditable as-is and the mismatch must be surfaced with both fingerprints and the epoch delta.
- If the call was served from an idempotency cache during replay → treat as `NotReexecuted`; it is neither faithful nor divergent, and downstream conclusions that depend on it are unsound.

The dangerous default is treating `NotReexecuted` and `AuditIncomplete` as pass, because both are "no mismatch observed." Absence of mismatch is not evidence of match.

## Operational Effect

Instruments that compare outputs alone will report a 100% faithful replay of a session that diverged in three of forty calls. Downstream forensic conclusions — "the agent did not modify the limits file," "the query read committed data" — inherit the false confidence. The operational rule: **a replay is only admissible as forensic evidence if every tool call carries a verified post-state fingerprint and was genuinely re-executed.** Anything else is a hypothesis. The instance must fail closed on the missing-fingerprint and cache-hit cases, because these are exactly the cases where silent divergence hides.

```python
import hashlib
from dataclasses import dataclass
from typing import Optional


class ReplayDivergenceError(RuntimeError):
    """Raised when a replayed tool call's effect does not match its recorded effect."""
    pass


class AuditIncompleteError(RuntimeError):
    """Raised when a recorded call lacks the post-state fingerprint needed to assert faithfulness."""
    pass


@dataclass
class RecordedCall:
    turn_index: int
    tool: str
    output: str
    post_state_fingerprint: Optional[str]   # None means the recorder never captured it
    served_from_idempotency_cache: bool = False


def verify_call(recorded: RecordedCall, replayed_output: str, replayed_state: bytes) -> None:
    if recorded.served_from_idempotency_cache:
        # Cache hit during replay: no re-execution occurred. Cannot assert faithfulness.
        raise AuditIncompleteError(
            f"turn {recorded.turn_index} ({recorded.tool}): served from idempotency cache "
            f"during replay; effect not re-executed, replay is not admissible as evidence"
        )

    if recorded.post_state_fingerprint is None:
        raise AuditIncompleteError(
            f"turn {recorded.turn_index} ({recorded.tool}): no recorded post-state fingerprint; "
            f"output-only match is not sufficient for effect-equivalence"
        )

    actual_fp = hashlib.sha256(replayed_state).hexdigest()

    if recorded.output != replayed_output:
        raise ReplayDivergenceError(
            f"turn {recorded.turn_index} ({recorded.tool}): output mismatch "
            f"recorded={recorded.output!r} replayed={replayed_output!r}"
        )

    if recorded.post_state_fingerprint != actual_fp:
        raise ReplayDivergenceError(
            f"turn {recorded.turn_index} ({recorded.tool}): effect divergence despite identical "
            f"output; recorded_state={recorded.post_state_fingerprint} replayed_state={actual_fp}"
        )


def replay_session(calls, executor) -> list:
    results = []
    for call in calls:
        replayed_output, replayed_state = executor(call)
        verify_call(call, replayed_output, replayed_state)
        results.append((call.turn_index, "faithful"))
    return results
```