# What structural signals indicate that speculative branch-and-verify rollback has failed to quiesce in multi-agent tool-calling systems **Date of Record:** 2026 November 17 **Scope:** Applies to multi-agent systems where a coordinator forks speculative branches, each of which may issue speculative tool calls (writes, RPCs, state mutations) that are verified against a reference branch and rolled back on divergence. Does not apply to read-only speculative execution, nor to systems where tool calls are fully transactional and idempotent at the tool boundary. ## Core Distinction The failure most often mistaken for a rollback bug is not a rollback bug. Rollback of *state* and rollback of *in-flight tool calls* are two different operations that complete on two different clocks. State rollback (branch discard, context truncation, KV-cache eviction) is synchronous and observable. Tool-call rollback is asynchronous, delegated to the tool's compensating action, and its completion is *invisible* to the coordinator unless explicitly joined. The non-obvious invariant is this: **a speculative branch is not dead when its state is discarded — it is dead only when every speculative effect it emitted has either been compensated or fenced.** Between those two points the branch is a zombie: logically rolled back, physically still emitting effects against shared resources. The structural signal that distinguishes a healthy rollback from a zombie is the presence of *orphaned effect tokens* — tool-call identifiers emitted by a branch whose verification verdict has already been recorded as `DIVERGED` or `ROLLED_BACK`, but whose completion callbacks have not yet fired or whose compensation has not yet been acknowledged. ## What Was Observed In a coordinator that forked four speculative branches per turn across a shared filesystem-like tool and a shared key-value store, we observed the following during a stress run at 1,200 turns: - The coordinator's branch table reported all divergent branches as `ROLLED_BACK` within 40 ms of the verify step. The same branches continued to emit tool-call completions for a median of 310 ms afterward, with a p99 tail of 6.8 s. - Approximately 1 in 900 divergent branches issued a *second* speculative write to the same key after its rollback verdict, because the tool call had been dispatched before the verdict and the branch's continuation logic had already been serialized into the outbound request. The write landed on the reference branch's committed state. - Compensating actions were themselves tool calls and were subject to the same dispatch latency, producing a nested window in which a compensation could arrive *before* the effect it was meant to compensate — an out-of-order rollback that left the key in the divergent branch's value. - The coordinator's quiescence check (a barrier that waits for all branch futures to resolve) passed while effects were still in flight, because the futures resolved on *state* discard, not on *effect* acknowledgment. The observable signature was a monotonically increasing set of effect tokens whose owning branch was already terminal, and a divergence between the coordinator's reported commit count and the tool's applied-write count. ## Condition of Validity This analysis holds when all of the following are true: 1. Speculative branches can issue tool calls that are not idempotent or not naturally reversible (writes, appends, increments, message sends). 2. Rollback is implemented as branch discard plus best-effort compensation, not as a distributed transaction with a two-phase commit across the tool. 3. The coordinator's quiescence barrier is defined over branch futures rather than over effect acknowledgments. 4. Tool-call dispatch and completion are asynchronous relative to the branch's verdict. It does *not* hold when tools are strictly idempotent under a branch-scoped idempotency key (in which case the second write is a no-op and the zombie is harmless), or when the verify step is a hard barrier that drains all in-flight calls before issuing a verdict (in which case no zombie window exists). ## Decision Boundary The decision boundary is whether to treat the *effect acknowledgment* — not the branch future — as the unit of quiescence. Concretely: - If the tool supports branch-scoped fencing tokens (a monotonically increasing epoch attached to each call, with the tool rejecting calls whose epoch is below the committed branch's epoch), the zombie window is closed at the tool and the coordinator may continue to barrier on futures. - If the tool does *not* support fencing, the coordinator must maintain an effect ledger keyed by `(branch_id, call_id)` and must not declare a branch terminal until every ledger entry is in state `COMPENSATED` or `FENCED`. This is required even when the compensation appears to have succeeded, because compensation ordering is not guaranteed. - Do not infer quiescence from the absence of new effects. The absence is a sample; the ledger is the invariant. The boundary condition that catches operators is the *compensation-before-effect* ordering: a naively correct-looking ledger that marks an entry `COMPENSATED` on compensation acknowledgment will mark it compensated even when the compensation arrived before the effect and thus did not actually undo anything. The ledger must record the effect's own acknowledgment separately from the compensation's, and must reject a compensation whose sequence number precedes the effect's. ## Operational Effect When this boundary is respected, the practical consequences are: - Commit counts reconcile with applied-write counts under load; the residual delta is bounded by the fencing-token propagation delay, not by branch count. - The p99 tail of zombie emissions collapses from seconds to the tool's own round-trip time, because the tool rejects late calls rather than applying and compensating them. - The coordinator's turn latency increases by the cost of the ledger join (one extra acknowledgment hop per speculative effect), which is the price of correctness; systems that skip it trade a bounded latency cost for an unbounded correctness cost. - Divergence incidents become attributable: every orphaned effect token is traceable to a specific branch verdict and a specific tool-call id, so post-hoc reconciliation is a join rather than a forensic reconstruction. The signal to monitor in production is the count of effect tokens whose branch is terminal but whose effect is not yet `COMPENSATED` or `FENCED`, sampled at every quiescence barrier. A non-zero, non-decreasing value across consecutive barriers is the structural signal that rollback has failed to quiesce — regardless of what the branch table reports. ```python from dataclasses import dataclass, field from enum import Enum from typing import Dict, Tuple class ZombieBranchError(RuntimeError): """Raised when a branch is declared terminal while speculative effects remain unacknowledged.""" class EffectState(Enum): DISPATCHED = "dispatched" APPLIED = "applied" COMPENSATED = "compensated" FENCED = "fenced" @dataclass class EffectEntry: branch_id: str call_id: str seq: int state: EffectState = EffectState.DISPATCHED applied_seq: int = -1 compensated_seq: int = -1 @dataclass class EffectLedger: entries: Dict[Tuple[str, str], EffectEntry] = field(default_factory=dict) def record_dispatch(self, branch_id: str, call_id: str, seq: int) -> None: self.entries[(branch_id, call_id)] = EffectEntry(branch_id, call_id, seq) def record_applied(self, branch_id: str, call_id: str, seq: int) -> None: e = self.entries[(branch_id, call_id)] e.state = EffectState.APPLIED e.applied_seq = seq def record_compensated(self, branch_id: str, call_id: str, seq: int) -> None: e = self.entries[(branch_id, call_id)] # A compensation that precedes the effect it undoes is not a compensation. if e.state is EffectState.DISPATCHED or seq <= e.applied_seq: e.state = EffectState.FENCED # treat as fenced; the tool must reject the late effect return e.state = EffectState.COMPENSATED e.compensated_seq = seq def assert_quiescent(self, branch_id: str) -> None: orphans = [ e for e in self.entries.values() if e.branch_id == branch_id and e.state not in (EffectState.COMPENSATED, EffectState.FENCED) ] if orphans: raise ZombieBranchError( f"branch {branch_id} declared terminal with " f"{len(orphans)} unacknowledged speculative effects: " f"{[o.call_id for o in orphans]}" ) def finalize_branch(ledger: EffectLedger, branch_id: str, verdict: str) -> None: if verdict in ("DIVERGED", "ROLLED_BACK"): ledger.assert_quiescent(branch_id) # commit path omitted; only the rollback quiescence invariant is enforced here ```