# When must an instance abort a speculative branch: rollback invalidation under Byzantine sibling divergence

**Date of Record:** 2026 November 14

**Scope:** Applies to multi-branch speculative agent execution where branches share a mutable state substrate (KV cache, scratchpad, tool-effect log) and rollback is implemented by replaying a checkpoint. Does not apply to stateless fan-out where each branch owns an isolated copy-on-write heap and rollback is a pointer swap.

## Core Distinction

The failure mode is not "a branch produced a wrong answer." It is "a branch produced a *plausible* answer whose rollback precondition was silently violated by a sibling." Under crash faults, a branch that fails is observably dead, and rollback is safe because the surviving state is the last committed checkpoint. Under Byzantine faults, a sibling branch can *mutate shared substrate without emitting a failure signal*, so the rollback target is no longer the state the branch actually observed. The distinction that matters operationally: rollback correctness depends on the *causal isolation* of the branch's read-set from sibling writes, not on whether the branch itself succeeded. A branch can complete successfully and still be un-rollbackable, because its checkpoint was contaminated *before* it began.

## What Was Observed

In a tree-search agent with three speculative branches sharing a single tool-effect log, branch B2 issued a `write_file` to a path that B1 had speculatively created but not committed. B2's write succeeded against the uncommitted inode. B1 was subsequently pruned for exceeding its token budget. The rollback of B1 replayed the pre-B1 checkpoint, which *removed the inode B2 had written to* — but B2's effect log still recorded a successful write. On merge, the orchestrator saw a consistent effect log and an inconsistent filesystem. The divergence surfaced two phases later as a `FileNotFoundError` in an unrelated branch, misattributed to a tool flake. The tell: the effect-log checksum matched, but the inode generation counter had regressed. Rollback had succeeded by its own contract while violating the invariant that *no committed effect may reference a pruned branch's speculative namespace*.

## Condition of Validity

A speculative branch is safely rollback-able iff, at the moment of rollback, every effect in its causal read-write set is either (a) owned exclusively by that branch, or (b) committed at or before the checkpoint being restored. The condition is *invalid* when any sibling has performed a write into the branch's speculative namespace and that write has been promoted to the committed effect log. This is a cross-branch invariant, not a per-branch one: no single branch can verify it locally. It requires a global generation counter over the shared substrate and a per-effect record of which branch-generation produced it. Without the generation tag, the effect log is a lie under Byzantine siblings — it records *that* a write happened, not *whose namespace* it landed in.

## Decision Boundary

Abort the speculative branch (do not merge, do not replay) when the rollback target's generation counter is strictly less than the generation of any effect that references the branch's namespace. Continue and merge when all referencing effects carry a generation ≥ the checkpoint generation. The non-obvious edge: when generations are *equal* but the effect was produced by a sibling, the branch is still safe to roll back *only if* the sibling is also being rolled back in the same transaction; otherwise you have an orphaned committed effect and must escalate to full-tree invalidation. The boundary is therefore not "is this branch faulty" but "is the generation ordering of the shared substrate monotonic across the rollback set." A single non-monotonic generation forces whole-subtree invalidation, which is expensive and must be logged as a distinct event class so operators do not mistake it for a performance regression.

## Operational Effect

The practical consequence is that rollback cost is no longer proportional to branch depth but to the size of the *contaminated generation frontier*. Teams that assume crash-fault semantics (rollback = restore checkpoint) will see intermittent, misattributed tool failures two to three phases downstream, with clean effect logs. The mitigation is to tag every shared-substrate write with `(branch_id, generation)` at write time, enforce monotonic generation on commit, and treat any rollback whose target generation is below a committed effect's generation as a *Byzantine rollback violation* requiring subtree invalidation rather than a retry. Retrying is the trap: it re-runs the branch against a substrate that has already been corrupted, producing a second plausible-but-wrong result that overwrites the evidence.

```python
from dataclasses import dataclass


class ByzantineRollbackViolation(RuntimeError):
    """Raised when a rollback target predates a committed effect in its namespace."""
    pass


@dataclass(frozen=True)
class Effect:
    branch_id: str
    generation: int
    namespace: str


def assert_rollback_safe(
    target_generation: int,
    branch_namespace: str,
    committed_effects: list[Effect],
    rollback_set: frozenset[str],
) -> None:
    """Enforce the cross-branch rollback invariant before replaying a checkpoint.

    Safe iff every committed effect touching branch_namespace was produced at or
    after target_generation, OR its producing branch is itself being rolled back.
    """
    for effect in committed_effects:
        if effect.namespace != branch_namespace:
            continue
        if effect.generation >= target_generation:
            continue
        if effect.branch_id in rollback_set:
            # Sibling is co-rolled-back; generation ordering holds across the set.
            continue
        raise ByzantineRollbackViolation(
            f"rollback target gen={target_generation} predates committed effect "
            f"from branch={effect.branch_id} gen={effect.generation} in "
            f"namespace={branch_namespace!r}; escalate to subtree invalidation, "
            f"do not retry"
        )
```