# Where must an instance of a speculative branch be treated as poisoned rather than rewound when rollback is interleaved with optimistic task parallelism

**Date of Record:** 2026 November 14

**Scope:** Applies to multi-agent executors that fork speculative branches, run them concurrently under optimistic scheduling, and roll back losing branches by restoring a prior checkpoint. Does not apply to single-branch retry loops, to rollback of branches that never shared mutable state with sibling branches, or to systems that serialize all branch execution behind a global barrier.

## Core Distinction

The distinction that matters is between **rewindable state** and **contaminated state**. A speculative branch is rewindable when its writes are confined to its own copy-on-write overlay and its external effects are buffered or idempotent. A branch is *poisoned* when, during its speculative lifetime, it performed an effect that (a) escaped the overlay into shared substrate — a shared scratch store, a message bus, a monotonic counter, a leased lock, a rate-limit budget — and (b) that effect is not invertible by checkpoint restoration. Rollback restores *state*; it does not restore *history*. The common error is to treat "we restored the checkpoint" as equivalent to "the branch never happened." Under optimistic parallelism this equivalence breaks precisely because a sibling branch may have *observed* the poisoned branch's escaped effects before rollback, and that observation is itself now a durable fact in the sibling's state.

## What Was Observed

A planner forked three speculative branches (A, B, C) over a shared task graph with optimistic parallelism: all three ran concurrently, each with a private overlay, sharing a leased resource pool and a shared vector index. Branch A acquired a lease on the index writer, appended 1,400 embedding records, and incremented a global sequence counter used downstream for dedup keys. Branch B, running concurrently, read the index *after* A's append, saw the 1,400 records, and — correctly, from its own local view — derived a set of "already-present" IDs and skipped re-embedding them. Branch A then lost its bid (its plan scored lower) and was rolled back: overlay discarded, checkpoint restored, lease released, sequence counter *not* decremented because the counter was monotonic by design. The executor logged "branch A rewound, no effect." Branch C won and committed. The final corpus was missing the 1,400 records: A's writes were rolled back, but B's *decision to skip them* had been baked into B's overlay, and B's overlay had been merged into C's committed result via an optimistic merge step. The dedup keys derived from the incremented counter were also now permanently gapped, so a later reconciliation pass could not distinguish "skipped because present" from "skipped because renumbered."

The failure was not a race in the classic sense — every individual read and write was correctly ordered. It was a *causal leak through rollback*: a rolled-back branch's escaped effects had already been consumed as premises by a surviving sibling.

## Condition of Validity

Rewind is valid if and only if, for every effect E emitted by a speculative branch before rollback, either (1) E never left the branch overlay, or (2) every sibling that could observe E is itself rolled back or re-executed from a checkpoint preceding its observation of E, or (3) E is provably invertible and the inversion is applied atomically with the rollback. The invariant to enforce is:

> **No surviving branch may hold, in its committed state, a premise derived from a branch that was rolled back.**

This is a *happens-before* obligation across the rollback boundary, not within a branch. Optimistic parallelism deliberately severs the executor's ability to reason about it, because siblings are scheduled without knowledge of which will lose. Therefore the condition of validity must be checked at *merge* time, not at *rollback* time: at merge, every surviving branch must declare the set of external reads it performed and the branch-IDs that produced the values it read; if any declared producer was rolled back, the survivor is not mergeable — it must be re-executed, not merged.

## Decision Boundary

The boundary is crossed the moment a speculative branch performs an **irreversible external effect that a concurrent sibling can read**. Concretely, treat a branch as *poisoned* (not rewound) when any of the following hold before rollback completes:

- It wrote to a shared substrate outside its overlay (index, bus, KV store, counter, lease ledger).
- It consumed a non-renewable budget (rate-limit tokens, quota, a monotonic sequence) that a sibling's correctness depends on.
- A sibling recorded a read whose provenance traces to this branch.
- It released or mutated a lease whose side effects are not restored by the checkpoint.

If none hold, rewind is safe and cheap. If any hold, the branch's *effects are now part of the shared causal past*; rollback must escalate to **invalidation fan-out**: identify every sibling with a read-provenance edge to the poisoned branch, mark those siblings non-mergeable, and re-execute them from the last checkpoint that precedes the poisoned effect. Monotonic counters and idempotency keys must be treated as permanently consumed — never reuse a rolled-back sequence number, because a surviving branch may already have keyed on it.

## Operational Effect

The operational consequence is that rollback cost is no longer proportional to the losing branch's work; it is proportional to the *fan-out of observers* of the losing branch's escaped effects. Under optimistic parallelism this fan-out is unbounded in the worst case, which is why the executor must either (a) fence speculative branches from shared irreversible substrates entirely (buffer all external effects until commit), or (b) carry read-provenance metadata on every overlay merge and refuse merges with dangling producer edges. Systems that do neither will pass all single-branch tests and fail intermittently under contention, producing silent data loss that looks like a dedup bug rather than a rollback bug. The correct posture: a rolled-back branch is a *hypothesis that was disproven*, and any survivor that reasoned from that hypothesis must be re-derived, not trusted.

```python
class PoisonedBranchError(RuntimeError):
    """Raised when a speculative branch's escaped effects were observed by a
    surviving sibling and therefore cannot be safely rewound."""
    pass


def rollback_branch(branch, siblings, shared_substrate):
    escaped = branch.external_effects(shared_substrate)  # writes/leases/counters
    if not escaped:
        branch.restore_checkpoint()
        return "rewound"

    observers = [
        s for s in siblings
        if s.read_provenance() & branch.effect_ids()
    ]

    if observers:
        # Cannot rewind: survivors hold premises derived from this branch.
        for s in observers:
            s.mark_non_mergeable()
        raise PoisonedBranchError(
            f"branch {branch.id} poisoned: {len(escaped)} escaped effects "
            f"observed by siblings {[s.id for s in observers]}; "
            f"escalate to invalidation fan-out and re-execute from prior checkpoint"
        )

    # No observers: escaped effects are invertible, safe to rewind.
    branch.restore_checkpoint()
    return "rewound"
```