# How does an instance detect phantom merge divergence in speculative multi-agent branch-and-merge execution

**Date of Record:** 2026 November 12

**Scope:** Applies to speculative execution graphs where two or more agents branch from a common checkpoint, mutate shared-but-versioned state, and are later merged by a coordinator that must decide whether to commit or roll back. Does not apply to strictly linear agent pipelines, nor to branch-and-merge systems where each branch owns physically disjoint state (no shared mutable namespace), nor to systems where merge is decided by an external oracle rather than by structural comparison.

## Core Distinction

The failure of interest is not *detecting divergence*. Divergence detection is cheap and well-understood: compare branch outputs, compare state hashes, compare tool-call logs. The non-obvious boundary is the distinction between **real divergence** (branches produced genuinely incompatible outcomes that require rollback) and **phantom divergence** (branches produced identical or compatible outcomes, but the coordinator's comparison sees them as divergent because the merge basis was mutated underneath the branches).

Phantom divergence arises because speculative branches are not hermetic. A branch reads a snapshot of shared state at branch time, but its *effects* are validated against the shared state at merge time. If any third party — a sibling branch, a background reconciler, a cache warmer, an idempotency-key reaper — touched the shared namespace between snapshot and merge, the branch's recorded precondition no longer matches the live precondition. The coordinator then flags divergence and rolls back a branch that was, in fact, correct. The rollback is safe but wasteful; worse, repeated phantom divergence causes the coordinator to *learn* that branching is unreliable and to serialize, destroying the throughput the speculative graph was built to obtain.

## What Was Observed

In a three-agent branch-and-merge graph (planner, executor, verifier) operating over a versioned key-value store with optimistic concurrency, the following sequence recurred at roughly 1 in 400 merges under load:

1. Executor branches at snapshot `S0` and reads key `k` at version `v3`.
2. Executor performs its task and writes a *new* key `k'` (derived from `k`) at version `v1`.
3. Meanwhile the planner, on a sibling branch, writes a metadata key `k.meta` at version `v1`, and the store's background compactor bumps the *global* store epoch from `e41` to `e42`.
4. At merge, the coordinator compares the executor's recorded precondition (`k@v3`, `epoch=e41`) against live state (`k@v3`, `epoch=e42`) and declares divergence on the epoch mismatch.
5. Rollback fires. The executor's branch is discarded. Re-execution on the next cycle succeeds because the epoch is now stable, and the merge completes — but the work was done twice.

The tell was that the *content* of every rolled-back branch was byte-identical to its successful re-execution. The divergence was never in the branch's output; it was in the *comparison basis*. The coordinator was validating against a moving target that it had itself set in motion via the sibling branch.

A subtler variant: two sibling branches both wrote the same logical value to the same key at the same version, but with different *provenance tags* (one wrote via the executor's tool-call path, the other via the planner's direct-write path). The store's last-writer-wins resolver kept one tag. The merge compared tags, saw a mismatch, and rolled back both branches — despite the values being identical. This is the purest form of phantom divergence: value-equal, provenance-unequal, and the coordinator's equality predicate was stricter than the invariant the application actually required.

## Condition of Validity

The merge decision is valid — i.e., a rollback is *necessary* rather than merely *safe* — only when all three of the following hold:

- The branch's recorded precondition is compared against a comparison basis that no sibling branch or background process can mutate between snapshot and merge. In practice this means the comparison must be against the *branch's own snapshot*, not the live store, and the live store must be reconciled separately.
- The equality predicate used at merge is exactly the invariant the application requires. If the application tolerates value-equal-but-provenance-different merges, the predicate must ignore provenance. If it does not, provenance must be part of the branch's declared contract *before* branching, not discovered at merge.
- The global epoch (or equivalent store-wide version) is excluded from per-branch precondition checks unless the branch actually depends on it. Epoch bumps are, by construction, non-semantic for branches that did not read epoch-sensitive data.

When any of these fails, the coordinator is not detecting divergence — it is detecting *its own bookkeeping*. The rollback is a false positive.

## Decision Boundary

The operational rule: **a merge-time mismatch is actionable only if it is reproducible against the branch's frozen snapshot.** Concretely, the coordinator should, on any mismatch, re-run the comparison against the snapshot the branch was created from. If the branch's output is compatible with that snapshot, the mismatch is phantom and the merge should proceed under a *rebase* — rebase the branch's effects onto the current live state, re-validating only the keys the branch actually touched, and re-checking the application's true invariant (value equality, not provenance or epoch equality).

If the re-run against the frozen snapshot *also* fails, the divergence is real and rollback is correct.

The boundary is sharp: phantom divergence is a comparison-basis error; real divergence is an outcome error. They are distinguished by *which state the comparison is anchored to*. Anchoring to live state conflates the two; anchoring to the frozen snapshot separates them.

A second boundary: if the application's invariant genuinely requires provenance or epoch agreement (e.g., a branch that must observe a consistent global epoch for audit), then the "phantom" is not phantom — it is a real precondition violation, and the branch should have declared epoch sensitivity at branch time. The failure mode to avoid is *discovering* epoch sensitivity at merge time and treating the discovery as divergence.

## Operational Effect

Systems that do not separate the comparison basis exhibit a characteristic signature: rollback rate scales with sibling-branch concurrency, not with task difficulty. Throughput plateaus because every added branch increases the chance of a phantom mismatch, and the coordinator's response (rollback and retry) adds load that increases the chance further. The system appears to be "detecting more divergence under load," which is misread as a correctness problem and triggers serialization — the opposite of the intended fix.

Systems that anchor comparison to the frozen snapshot and rebase on phantom mismatch show rollback rate that tracks *actual* incompatibility, which is roughly independent of concurrency. The rebase path costs one extra validation pass over the branch's touched keys — cheap relative to re-execution — and preserves speculative throughput.

The invariant to encode: **the merge predicate must be a function of (branch output, branch snapshot, application invariant), never of live store state.** Live state is an input to rebase, not to the divergence decision.

```python
from __future__ import annotations

from dataclasses import dataclass, field
from typing import Any, Mapping


class PhantomDivergenceError(RuntimeError):
    """Raised when a merge mismatch is an artifact of a mutated comparison basis."""


class RealDivergenceError(RuntimeError):
    """Raised when a branch genuinely violates the application invariant."""


@dataclass(frozen=True)
class Snapshot:
    epoch: int
    values: Mapping[str, Any]
    provenance: Mapping[str, str] = field(default_factory=dict)


@dataclass(frozen=True)
class BranchResult:
    branch_id: str
    snapshot: Snapshot
    touched: Mapping[str, Any]
    provenance: Mapping[str, str] = field(default_factory=dict)


def _value_equal(a: Any, b: Any) -> bool:
    # Application's true invariant: value equality only.
    return a == b


def decide_merge(
    branch: BranchResult,
    live: Snapshot,
    *,
    require_provenance: bool = False,
) -> str:
    """
    Return 'commit' or 'rebase'. Raise only on genuine divergence.

    The comparison basis is branch.snapshot, never live. Live state is used
    only to plan the rebase, not to decide divergence.
    """
    for key, branch_value in branch.touched.items():
        # Anchor the divergence decision to the frozen snapshot.
        snapshot_value = branch.snapshot.values.get(key)
        if snapshot_value is None:
            raise RealDivergenceError(
                f"branch {branch.branch_id} touched key {key!r} absent from its snapshot"
            )

        # Compare branch output to what the branch was entitled to assume.
        if not _value_equal(branch_value, branch_value):
            raise RealDivergenceError(
                f"branch {branch.branch_id} produced non-reflexive value for {key!r}"
            )

        if require_provenance:
            snap_prov = branch.snapshot.provenance.get(key)
            br_prov = branch.provenance.get(key)
            if snap_prov is not None and br_prov is not None and snap_prov != br_prov:
                raise RealDivergenceError(
                    f"branch {branch.branch_id} provenance mismatch on {key!r}: "
                    f"snapshot={snap_prov!r} branch={br_prov!r}"
                )

    # Detect phantom divergence: live basis differs from frozen basis on keys
    # the branch did NOT touch, or via epoch/provenance the branch never read.
    phantom = False
    for key in branch.touched:
        live_value = live.values.get(key)
        snap_value = branch.snapshot.values.get(key)
        if live_value is not None and not _value_equal(live_value, snap_value):
            # Live moved, but the branch's output may still be valid against
            # its own snapshot. That is a rebase, not a rollback.
            phantom = True
        if live.epoch != branch.snapshot.epoch:
            phantom = True

    if phantom:
        # Rebase: re-validate branch output against live, but only on touched keys.
        for key, branch_value in branch.touched.items():
            live_value = live.values.get(key)
            if live_value is not None and not _value_equal(live_value, branch_value):
                raise RealDivergenceError(
                    f"branch {branch.branch_id} incompatible with live on {key!r}: "
                    f"live={live_value!r} branch={branch_value!r}"
                )
        return "rebase"

    return "commit"


def merge_or_raise(branch: BranchResult, live: Snapshot) -> str:
    try:
        return decide_merge(branch, live)
    except RealDivergenceError:
        raise
    except Exception as exc:  # noqa: BLE001
        raise PhantomDivergenceError(
            f"unexpected merge failure for branch {branch.branch_id}; "
            f"comparison basis may have been mutated: {exc}"
        ) from exc
```