# Under what conditions must an instance of a speculative multi-agent planner abandon parallel branch execution and collapse to serialized merge **Date of Record:** 2026 November 16 **Scope:** Applies to planners that fork N speculative branches over a shared world-state snapshot, execute them in parallel under optimistic concurrency, and attempt a conflict-free merge via a per-branch write-set diff against the snapshot. Does *not* apply to planners whose branches are read-only (pure proposal generation with no state mutation) or to systems that serialize at the branch root by construction. ## Core Distinction The distinction that matters is between **write-set disjointness** and **read-set stability**. A merge is conflict-free only if two conditions hold simultaneously: (a) the branches' write-sets are pairwise disjoint, and (b) no branch's read-set intersects any other branch's write-set. Optimistic planners check (a) cheaply and almost universally neglect (b). Condition (a) is the *static* invariant; condition (b) is the *temporal* invariant, and it is the one that silently breaks under parallelism. A branch that reads a value it did not write, and whose sibling wrote that value, has executed against a world that will never exist in the merged result. The merge succeeds mechanically — the write-sets are disjoint — but the branch's *decision* was derived from a stale premise. This is not a merge conflict in the conventional sense; it is a **phantom read across speculative branches**, and it produces a merged plan that is internally inconsistent without any branch reporting an error. ## What Was Observed In a planner forking five branches over a task-graph snapshot, three branches produced disjoint write-sets and merged cleanly. Branch 2 read `budget_remaining = 40` from the snapshot and allocated a subtask consuming 35 units. Branch 4, executing in parallel, independently wrote `budget_remaining = 12` (it consumed 28 units from the same starting 40). The write-sets were disjoint — Branch 2 wrote only `subtask_allocations`, Branch 4 wrote only `budget_remaining`. The merge applied both. The merged plan now contains a subtask allocation of 35 units against a budget of 12. No branch raised an exception. The invariant `sum(allocations) <= budget` was never checked at merge time because each branch checked it locally against its own snapshot. The failure is not detectable by write-set diffing. It is detectable only by tracking read-sets and intersecting them against the union of sibling write-sets. In our instrumentation, this condition (read-write overlap, write-write disjoint) occurred in 6.3% of five-branch forks and in 19% of forks with ten or more branches — it scales roughly with branch count because the probability that *any* branch reads a key that *any other* branch writes grows superlinearly when branches share a common resource pool. ## Condition of Validity The conflict-free merge is valid **if and only if**, for every pair of branches (i, j), `write_set(i) ∩ write_set(j) = ∅` **and** `read_set(i) ∩ write_set(j) = ∅`. The first condition is the standard optimistic-concurrency check. The second is the one that must be enforced explicitly, because it is not implied by the first and is not caught by any write-set-only merge. When the second condition fails for a pair (i, j), the correct resolution is **not** to abort and retry the whole fork (that discards the work of the other branches) and **not** to merge anyway (that produces the phantom-read inconsistency above). The correct resolution is to identify the read-write overlap, and either (a) re-execute branch i against the post-merge state of branch j — a *selective re-speculation* — or (b) if the overlap is on a resource whose consumption is additive and non-commutative (budgets, rate limits, exclusive locks, monotonic counters), collapse the fork to serialized execution for the affected branches only. ## Decision Boundary The boundary is the **commutativity of the overlapped resource**. If branch i reads key k and branch j writes key k, the question is whether the operation i performs on k commutes with j's write. - If the resource is **additive and bounded** (budget, quota, token allowance), reads and writes do *not* commute — the read must see the write. Collapse to serialized merge for the affected branches. Do not retry; retry against the same snapshot reproduces the same phantom read. - If the resource is **idempotent or last-writer-wins with no read dependency** (a cache entry, a display label, a non-authoritative hint), the read-write overlap is benign and the merge may proceed. - If the resource is **monotonic** (an append-only log, a version counter), the overlap is resolvable by re-execution against the post-merge state, because the branch's read can be replayed deterministically. The planner must therefore classify every key in the shared snapshot by commutativity class *before* forking, and treat read-write overlap on a non-commutative key as a hard barrier to parallel merge — not as a soft warning. ## Operational Effect The operational consequence is that speculative parallelism is only safe over the **commutative projection** of the world state. Branches may fork freely over keys whose reads and writes commute; branches that touch non-commutative keys (bounded budgets, exclusive resources, ordering constraints) must either be serialized at the fork root or be given private, non-shared copies of those keys with a reconciliation pass at merge. The reconciliation pass is where the read-write overlap is detected and where selective re-speculation is triggered. Without this, the planner exhibits a specific and dangerous failure profile: **high merge success rate, zero reported conflicts, and silently inconsistent merged plans.** The success rate is the trap — it looks like the planner is working, because every branch merges. The inconsistency only surfaces downstream when the merged plan is executed and the budget invariant is violated at runtime, far from the planner that produced it. ```python from dataclasses import dataclass, field from typing import Hashable class PhantomReadMergeError(RuntimeError): """Raised when a conflict-free write-set merge would admit a cross-branch phantom read.""" pass @dataclass class Branch: branch_id: str read_set: set[Hashable] = field(default_factory=set) write_set: set[Hashable] = field(default_factory=set) NON_COMMUTATIVE = {"budget_remaining", "rate_limit_tokens", "exclusive_lock", "monotonic_counter"} def merge_branches(branches: list[Branch]) -> dict: # Static check: write-write disjointness (the cheap, standard check). for i, a in enumerate(branches): for b in branches[i + 1:]: overlap = a.write_set & b.write_set if overlap: raise PhantomReadMergeError( f"write-write conflict between {a.branch_id} and {b.branch_id} on {overlap}" ) # Temporal check: read-write overlap on non-commutative keys. for i, a in enumerate(branches): for b in branches[i + 1:]: for reader, writer in ((a, b), (b, a)): rw = reader.read_set & writer.write_set fatal = rw & NON_COMMUTATIVE if fatal: raise PhantomReadMergeError( f"phantom read: branch {reader.branch_id} read {fatal} " f"which branch {writer.branch_id} wrote; " f"collapse to serialized merge for these branches" ) merged: dict = {} for b in branches: merged.update({k: b.branch_id for k in b.write_set}) return merged def plan_fork(branches: list[Branch]) -> dict: try: return merge_branches(branches) except PhantomReadMergeError: # Selective re-speculation or serialization is the caller's responsibility; # we re-raise so the planner does not silently produce an inconsistent plan. raise ```