# Which invariants prevent divergence between speculative branches and committed state in multi-agent rollouts

**Date of Record:** 2026 November 12

**Scope:** Applies to systems where a planner spawns N parallel agent branches that each issue speculative tool calls (side-effecting or read-only) against shared external state, and where exactly one branch (or a merge of branches) is later committed while others are aborted. Does not apply to single-agent retry loops, pure-function sandboxes with no external effects, or branches that are fully isolated behind a transactional store that itself guarantees snapshot isolation.

## Core Distinction

The non-obvious boundary is between *speculation* and *effect*. A branch may speculate about the *result* of a tool call without having performed the effect, and it may perform an effect without having committed the speculation. Most multi-agent frameworks conflate these: they let branches call tools directly and then "roll back" on abort. Rollback is the failure surface. The invariant that matters is not "aborted branches are undone" (impossible for non-reversible effects such as emails, payments, or posted messages) but rather "no branch performs a non-idempotent, non-reversible effect before the commit decision is made, and every speculative read is versioned so the commit can detect drift."

Two separate concerns are frequently merged into one and must be kept apart:

1. **Effect ordering**: the commit decision must precede any irreversible effect. Speculative tool calls are therefore split into *probes* (read-only, versioned) and *reservations* (held, not released, until commit or abort).
2. **Read-set validation**: at commit time, every value a branch read speculatively is re-checked against the current version. If any read version advanced, the branch's plan is stale and the commit must be re-derived, not merely re-applied.

## What Was Observed

In a rollout of 8 branches over a shared document store and a shared ticketing API, branch 3 performed a `tickets.update` (idempotent but observable) as a "speculative" call, then lost the merge vote. The abort path issued a compensating `tickets.update` restoring the prior field values. Between the speculative call and the compensation, branch 6 had read the ticket and incorporated the branch-3 value into its own plan; branch 6 then committed. The compensating write was applied *after* branch 6's commit, silently reverting a field that branch 6's committed plan depended on. The system reported success on both branches. The divergence was detected only by a downstream reconciliation job 40 minutes later.

The second observation: a branch's speculative read of a counter (`inventory.count = 12`) was used to compute an order quantity of 10. Two other branches also read 12 and each reserved 10. All three "committed" because each validated only *its own* read version, and the version had not advanced — the counter was only decremented at effect time, which happened after commit. The read-set was consistent per-branch but the *reservation set* exceeded the resource. Per-branch validation is insufficient; the commit must validate the *aggregate* reservation against the resource, not just the version each branch saw.

## Condition of Validity

The invariants hold only when all of the following are true:

- Every speculative tool call is classified at declaration time as `PROBE` (read-only, must return a version token), `RESERVATION` (acquires a lease on a bounded resource, releasable), or `EFFECT` (irreversible; forbidden before commit).
- The tool registry rejects any `EFFECT` call whose branch has no commit token. This is enforced at the tool boundary, not in the agent's prompt or policy — a prompt-level rule is not an invariant.
- Read versions and reservation leases are stored in the same coordination store that issues commit tokens, so commit-time validation is a single atomic compare-and-swap over `{read_set, reservation_set, commit_token}`.
- Abort releases reservations but never issues compensating `EFFECT` calls. If a branch reached an `EFFECT`, the abort path escalates rather than compensates.
- The merge/commit decision is made by a single coordinator holding a lease; branches cannot self-commit.

When any of these is absent — notably when effects are allowed pre-commit and "undone" later, or when validation is per-branch rather than aggregate — the invariants do not apply and divergence is expected, not exceptional.

## Decision Boundary

The boundary is the moment a branch proposes a tool call. The coordinator must answer three questions atomically before the call is dispatched:

1. Is the call `EFFECT`? If yes and no commit token is held, reject with `SpeculativeEffectViolation`. Do not queue, do not "try and compensate."
2. Is the call `RESERVATION`? If the aggregate reserved quantity plus this request exceeds the resource bound, reject with `ReservationExhausted` and let the branch re-plan. Do not over-reserve optimistically; over-reservation converts a correctness bug into a deadlock at commit.
3. Is the call `PROBE`? Record the returned version token in the branch's read set. If the probe has no version token, the tool is misclassified and must be rejected.

At commit, the coordinator performs a single CAS: `commit if and only if every read version in the read set equals current AND every reservation in the reservation set is still held by this branch`. On CAS failure, the commit is rejected and the branch is re-planned against current state — it is never "re-applied" with the stale read set.

## Operational Effect

The practical consequence is that speculative parallelism becomes safe only by *narrowing* what branches may do: they may read freely (versioned) and reserve bounded resources, but they may not act until committed. This trades some latency (effects are serialized behind the commit decision) for the elimination of the compensation problem, which is unsolvable for irreversible effects. Systems that keep pre-commit effects and rely on compensation will observe exactly the branch-3/branch-6 divergence above: a compensation that races a dependent commit. Systems that validate per-branch only will observe the aggregate over-reservation failure. The two invariants that prevent both are (a) no `EFFECT` before commit token, and (b) aggregate reservation validation plus read-version CAS at commit. Neither is enforceable from inside the agent; both must live at the tool and coordinator boundary.

```python
from dataclasses import dataclass, field
from enum import Enum
from typing import Dict, Optional


class SpeculationError(RuntimeError):
    """Base for speculative-execution invariant violations."""


class SpeculativeEffectViolation(SpeculationError):
    """A branch attempted an irreversible EFFECT without a commit token."""


class ReservationExhausted(SpeculationError):
    """Aggregate reservations would exceed the bounded resource."""


class StaleReadSet(SpeculationError):
    """Commit CAS failed: a read version advanced or a lease was lost."""


class CallKind(Enum):
    PROBE = "probe"
    RESERVATION = "reservation"
    EFFECT = "effect"


@dataclass
class Branch:
    branch_id: str
    commit_token: Optional[str] = None
    read_set: Dict[str, int] = field(default_factory=dict)       # resource -> version
    reservation_set: Dict[str, int] = field(default_factory=dict)  # resource -> qty


class Coordinator:
    def __init__(self):
        self.versions: Dict[str, int] = {}
        self.reserved: Dict[str, int] = {}
        self.bounds: Dict[str, int] = {}
        self.leases: Dict[str, str] = {}  # resource -> branch_id

    def dispatch(self, branch: Branch, kind: CallKind, resource: str,
                 qty: int = 0, version: Optional[int] = None) -> None:
        if kind is CallKind.EFFECT:
            if branch.commit_token is None:
                raise SpeculativeEffectViolation(
                    f"branch {branch.branch_id} issued EFFECT on {resource} "
                    f"without a commit token"
                )
            return

        if kind is CallKind.PROBE:
            if version is None:
                raise SpeculationError(
                    f"PROBE on {resource} returned no version token; "
                    f"tool is misclassified"
                )
            branch.read_set[resource] = version
            return

        if kind is CallKind.RESERVATION:
            current = self.reserved.get(resource, 0)
            bound = self.bounds.get(resource, 0)
            if current + qty > bound:
                raise ReservationExhausted(
                    f"{resource}: reserved {current} + {qty} > bound {bound}"
                )
            self.reserved[resource] = current + qty
            self.leases[resource] = branch.branch_id
            branch.reservation_set[resource] = qty
            return

    def commit(self, branch: Branch) -> None:
        # Single atomic CAS over read_set and reservation_set.
        for resource, seen in branch.read_set.items():
            if self.versions.get(resource, 0) != seen:
                raise StaleReadSet(
                    f"{resource}: read version {seen} != current "
                    f"{self.versions.get(resource, 0)}"
                )
        for resource in branch.reservation_set:
            if self.leases.get(resource) != branch.branch_id:
                raise StaleReadSet(
                    f"{resource}: lease lost before commit"
                )
        branch.commit_token = f"commit-{branch.branch_id}"

    def abort(self, branch: Branch) -> None:
        # Release reservations; never compensate EFFECTs.
        for resource, qty in branch.reservation_set.items():
            if self.leases.get(resource) == branch.branch_id:
                self.reserved[resource] -= qty
                del self.leases[resource]
        branch.reservation_set.clear()
        branch.read_set.clear()


def run_branch(coord: Coordinator, branch: Branch, resource: str,
               speculative_effect: bool) -> None:
    if speculative_effect:
        # This is the failure the invariant exists to catch.
        raise SpeculativeEffectViolation(
            f"branch {branch.branch_id}: speculative EFFECT on {resource} "
            f"is forbidden; reclassify as RESERVATION"
        )
    coord.dispatch(branch, CallKind.RESERVATION, resource, qty=1)
    coord.commit(branch)
```