# Which invariants prevent silent state corruption during branch-and-verify rollback of speculative multi-agent plans

**Date of Record:** 2026 November 11

**Scope:** Applies to orchestrators that run multiple agent branches speculatively against shared external state (databases, filesystems, message queues, tool APIs) and verify-then-rollback divergent branches before committing a winning plan. Does not apply to pure in-memory simulation environments where all side effects are captured in a single transactional sandbox with no external observability.

## Core Distinction

Speculative execution is safe only when *state mutation* is separable from *state observation*. In single-agent speculative decoding, the speculative token stream is cheap to discard because it lives in a buffer no one else can see. Multi-agent branch-and-verify is different: each speculative branch may call tools that mutate the world, and those mutations become visible to sibling branches, to the verifier, and to external consumers *before* the winning branch is chosen. The non-obvious boundary is that rollback restores the *orchestrator's* view of state but not the *world's* view. A branch that was rolled back still leaves behind committed side effects — sent emails, decremented inventory, appended log entries, consumed rate-limit budget, and, most dangerously, cached reads that sibling branches then treat as ground truth.

## What Was Observed

In a three-agent speculative planner (Planner A, Planner B, Verifier), branches were forked from a shared checkpoint. Branch A reserved 40 units of inventory via a tool call, then diverged from the goal and was rolled back. Branch B, running concurrently, read inventory *after* A's reservation, saw 60 units available, and planned against that figure. The verifier selected B's plan because it was internally consistent. On commit, B's plan attempted to reserve 60 units — but only 60 physically existed, of which A's 40 were still held because A's rollback had released the orchestrator-side handle without issuing the compensating release call (the rollback path was written before the reservation tool existed and did not know to call it). The result was a committed plan that oversold inventory by 40 units. No exception fired. Every individual component behaved correctly against its own local invariant. The corruption was purely relational: it lived in the gap between two branches' views of a shared resource, and no single branch's postcondition could detect it.

A second, subtler observation: the verifier's read cache was keyed by resource ID, not by branch lineage. When B read inventory, it hit a cache entry populated by A. Rollback of A invalidated A's *write* handle but not the *read* cache derived from A's side effects. The verifier therefore verified B against a world that no longer existed.

## Condition of Validity

Rollback is sound only if all four of the following hold simultaneously:

1. **Effect ledger completeness.** Every externally visible mutation issued by any branch is recorded in a ledger keyed by `(branch_id, effect_id)` with enough information to issue a compensating action. Effects that cannot be compensated (irreversible sends, non-idempotent appends) must be *deferred* until commit, not executed speculatively.
2. **Read isolation by lineage.** Any read performed by a branch must be served either from the pre-fork snapshot or from a view that includes only that branch's own uncommitted effects — never from a sibling's speculative effects. Cache keys must include branch lineage, not just resource identity.
3. **Compensation ordering.** Rollback must issue compensations in reverse effect order and must not release a branch's resources until all siblings that could have observed those effects have either committed or been rolled back and re-derived. Concurrent rollback and read is the corruption window.
4. **Verifier independence from speculative state.** The verifier must evaluate each branch against the committed snapshot plus that branch's own ledger, never against live shared state that other branches have touched.

When any of these fails, the system enters a state where all local invariants hold and the global invariant (resource conservation, referential integrity, monotonic counters) is violated.

## Decision Boundary

The decision is not "should we roll back" but "was this branch's effect set *isolatable* at the moment it was issued." Classify every tool call at plan-compile time into three tiers:

- **Isolatable** (reads from snapshot, writes to branch-private namespace): safe to speculate and roll back freely.
- **Compensable** (reversible with a known inverse, e.g., reserve/release, increment/decrement): safe to speculate *only if* the compensating action is registered atomically with the effect and the effect is fenced from sibling reads until commit-or-compensate completes.
- **Irreversible** (external sends, financial posts, non-idempotent appends): must never execute speculatively; the branch must emit an *intent* that the orchestrator executes only after verification selects it.

If a plan cannot be compiled so that every step falls into tier 1 or tier 2 with registered compensations, the branch must be executed serially or not at all. Speculation is a performance optimization, never a correctness mechanism.

## Operational Effect

Enforcing these invariants converts a class of silent, late-detected corruption into an explicit, early, attributable failure at the moment a non-isolatable effect is issued under a speculative branch. The cost is throughput: irreversible effects serialize, and compensable effects require a fencing protocol that blocks sibling reads until resolution. The benefit is that "rollback" becomes a real operation with a verifiable postcondition (ledger empty, compensations acknowledged) rather than a bookkeeping gesture. The system can then assert, before committing any winning branch, that the committed snapshot plus the winning branch's ledger is the *only* state any surviving branch ever observed — which is the actual invariant that branch-and-verify depends on and that naive implementations silently violate.

```python
class SpeculativeRollbackViolation(RuntimeError):
    """Raised when a speculative branch's effects cannot be soundly rolled back
    or when a sibling observed state that rollback will invalidate."""
    pass


class EffectTier:
    ISOLATABLE = "isolatable"
    COMPENSABLE = "compensable"
    IRREVERSIBLE = "irreversible"


class EffectLedger:
    def __init__(self):
        # branch_id -> list of (effect_id, tier, compensation_callable)
        self._entries = {}
        # resource_id -> branch_id currently fencing reads on it
        self._fences = {}

    def register(self, branch_id, effect_id, tier, compensation=None):
        if tier == EffectTier.IRREVERSIBLE:
            raise SpeculativeRollbackViolation(
                f"branch {branch_id} attempted speculative irreversible effect "
                f"{effect_id}; must be deferred to commit"
            )
        if tier == EffectTier.COMPENSABLE and compensation is None:
            raise SpeculativeRollbackViolation(
                f"branch {branch_id} issued compensable effect {effect_id} "
                f"without a registered inverse; rollback would be unsound"
            )
        self._entries.setdefault(branch_id, []).append(
            (effect_id, tier, compensation)
        )

    def fence_read(self, resource_id, reader_branch, writer_branch):
        holder = self._fences.get(resource_id)
        if holder is not None and holder != reader_branch:
            raise SpeculativeRollbackViolation(
                f"branch {reader_branch} read resource {resource_id} while "
                f"branch {holder} held an unresolved speculative effect on it; "
                f"read would be invalidated by rollback"
            )
        self._fences[resource_id] = writer_branch

    def rollback(self, branch_id):
        entries = self._entries.pop(branch_id, [])
        # reverse order compensation
        for effect_id, tier, compensation in reversed(entries):
            if tier == EffectTier.COMPENSABLE:
                try:
                    compensation()
                except Exception as exc:
                    raise SpeculativeRollbackViolation(
                        f"compensation for {effect_id} on branch {branch_id} "
                        f"failed: {exc}; state is now divergent and must be "
                        f"quarantined"
                    ) from exc
        # release fences held by this branch
        for resource_id, holder in list(self._fences.items()):
            if holder == branch_id:
                del self._fences[resource_id]

    def assert_clean(self, branch_id):
        if self._entries.get(branch_id):
            raise SpeculativeRollbackViolation(
                f"branch {branch_id} committed with {len(self._entries[branch_id])} "
                f"unresolved speculative effects"
            )


def verify_and_commit(ledger, winning_branch, loser_branches):
    for loser in loser_branches:
        ledger.rollback(loser)
    ledger.assert_clean(winning_branch)
    return True
```