# Which invariants prevent silent divergence during speculative multi-agent execution with rollback and branch reconciliation

**Date of Record:** 2026 November 12

**Scope:** Applies to orchestration layers that fan out speculative agent branches against a shared mutable context, then reconcile by committing one branch and rolling back the rest. Does not apply to purely stateless fan-out (map-only) patterns where no branch mutates shared state, nor to single-agent retry loops.

## Core Distinction

The failure we are isolating is not "a branch produced a wrong answer." It is **commutative rollback divergence**: the reconciler commits branch *A*, rolls back branches *B* and *C*, and the resulting global state is *not* equivalent to the state that would have existed had *B* and *C* never executed. The system believes rollback is the identity operation. It is only the identity when every speculative branch's side effects are (a) fully journaled, (b) reversed in exact reverse order, and (c) never observed by a concurrently-committed branch during the speculation window.

The non-obvious part: divergence is usually silent. The committed branch's output is correct in isolation. The corruption lives in *shared* resources — a vector index, a cache, a rate-limit counter, a lock table — that branch *B* wrote to and whose rollback was either skipped (because the writer deemed the write "idempotent") or applied out of order. The reconciler reports success. The next task inherits the damage.

## What Was Observed

In a three-way speculative fan-out over a shared retrieval cache, branches *A*, *B*, *C* each issued cache writes keyed by a *pre-image* hash computed at branch entry. Branch *B* mutated its pre-image mid-execution (a re-chunking step), so its rollback key no longer matched its write key. Rollback of *B* was a no-op. Reconciliation committed *A* and reported a clean rollback. The stale *B* entries survived and poisoned the next 40 tasks with a 12% false-hit rate before detection. No exception fired anywhere. The invariant that was violated — *rollback key stability* — was never stated explicitly; it was an implicit assumption in the journal format.

A second observation: when two branches wrote the *same* cache key with different values, the journal recorded both writes but rollback reversed them in commit order rather than reverse-write order, leaving the earlier branch's value resident. Last-writer-wins on write, first-writer-wins on rollback — an asymmetry that only surfaces under concurrent same-key speculation.

## Condition of Validity

Rollback-as-identity holds only when all four of the following are enforced:

1. **Journal key immutability.** Every side effect is journaled under a key derived from immutable inputs captured at branch entry. If a branch can change what it writes *to* after it has decided what it will roll back, the journal is unsound.
2. **Reverse-total-order reversal.** Rollback must reverse effects in exact reverse of the observed write order, per resource, not per branch. Cross-branch interleaving means per-branch reversal is insufficient.
3. **Speculation-window isolation.** No committed branch may read a resource that a still-speculative sibling has written and not yet rolled back. This requires either copy-on-write shadow state or a read-barrier that blocks on reconciliation.
4. **Reconciliation atomicity.** The commit-and-rollback pair must be a single atomic transition with respect to external readers. A window where *A* is committed but *B* is not yet rolled back is a window where external readers see a state that never legitimately existed.

When any of these is absent, the system is in the divergence regime and rollback must be treated as best-effort cleanup, not as a correctness guarantee.

## Decision Boundary

The operational question is: *when do you pay for shadow state versus trusting journaled rollback?*

- If branches touch **disjoint** resources (provable by static key analysis), journaled rollback is sound and cheap. Proceed.
- If branches touch **shared mutable** resources and any branch can mutate its own write keys mid-flight, journaled rollback is unsound. You must either (a) freeze write keys at entry and forbid re-keying, or (b) move to copy-on-write shadow state and discard the shadow on rollback. There is no cheap middle path.
- If the speculation window exceeds the reconciliation latency budget, external readers *will* observe intermediate states. Add a read barrier or accept that the guarantee does not hold.
- **Never** treat "the reconciler returned without error" as evidence of clean rollback. It is evidence only that no branch raised during reversal.

## Operational Effect

Enforcing the four invariants costs memory (shadow state) or write-latency (key freezing and reverse-order journaling) proportional to speculative fan-out width. The payoff is that reconciliation becomes *decidable*: a committed branch's post-state is provably identical to its solo-execution post-state. Without enforcement, the system accumulates slow cache and index corruption whose blast radius grows with task volume and whose detection latency is measured in tens of tasks. The correct default for any speculative executor that shares mutable state is to assume divergence until the journal proves otherwise — and to fail loudly at reconciliation when the proof is unavailable, rather than reporting a clean commit over a poisoned substrate.

```python
class RollbackDivergenceError(RuntimeError):
    """Raised when journaled rollback cannot be proven equivalent to non-execution."""
    pass


def reconcile(branches, committed_id, journal):
    # Enforce invariant 1: every journaled write key must be stable.
    for entry in journal:
        if entry.write_key != entry.entry_key:
            raise RollbackDivergenceError(
                f"branch {entry.branch_id} mutated its write key "
                f"({entry.entry_key!r} -> {entry.write_key!r}); "
                f"rollback for this branch is unsound"
            )

    # Enforce invariant 2: reversal must be reverse-total-order per resource.
    by_resource = {}
    for entry in journal:
        by_resource.setdefault(entry.resource, []).append(entry)
    for resource, entries in by_resource.items():
        observed = [e.seq for e in entries]
        if observed != sorted(observed):
            raise RollbackDivergenceError(
                f"resource {resource!r} journal is not in write order; "
                f"reverse-total-order reversal impossible"
            )

    # Enforce invariant 3: no committed branch may have read a speculative write.
    for entry in journal:
        if entry.branch_id != committed_id and entry.read_by == committed_id:
            raise RollbackDivergenceError(
                f"committed branch {committed_id} observed speculative write "
                f"{entry.seq} from branch {entry.branch_id}; "
                f"speculation-window isolation violated"
            )

    # Only now is commit-and-rollback a safe atomic transition.
    return _apply_commit_and_reverse_rollback(branches, committed_id, journal)
```