# How does an instance detect non-idempotent tool side effects during speculative branch merge: the write-set provenance invariant

**Date of Record:** 2026 November 14

**Scope:** Applies to agents that fork speculative execution branches, execute tool calls and shared-memory writes on those branches, and merge them back with conflict detection. Does not apply to purely functional branches with no external side effects, nor to single-branch execution where merge ordering is trivial.

## Core Distinction

Conflict detection on shared memory is a *read-write* problem: two branches that touch the same cell can be reconciled by comparing vector clocks, version stamps, or content hashes. Conflict detection on *tool side effects* is a *write-once* problem: an external call that transferred money, sent an email, or appended to an append-only log has already happened, and no merge algorithm can un-happen it.

The non-obvious boundary is this: a branch merge that reports "no conflict" can still be unsafe, because the merge's conflict detector is typically scoped to the shared-memory write set and treats tool invocations as opaque, replayable, or deferrable. The invariant that must hold is **write-set provenance**: every side-effecting tool call must carry a provenance token identifying the branch that issued it and the causal predecessor state it assumed, and the merge must refuse to commit if two branches issued side-effecting calls whose provenance tokens are not causally ordered *and* whose effects are not provably commutative.

This is distinct from ordinary optimistic concurrency. Optimistic concurrency fails loudly when a version check fails. Speculative branch merging fails *silently* when a side effect is idempotent-looking but is not, or when two branches each individually succeed and the merge sees no memory conflict because the branches wrote disjoint cells.

## What Was Observed

A planner agent forked three speculative branches from a shared state at version `v17`. Branch A called `payments.charge(account=42, amount=100, idempotency_key="ord-9")`. Branch B called `payments.charge(account=42, amount=100, idempotency_key="ord-9")` — the same key, deliberately, because both branches derived the same plan. Branch C wrote a shared-memory cell `order.status = "confirmed"` and called `notifications.send(order=9)`.

The merge layer compared write sets. A and B had written no shared-memory cells (their tool calls were recorded in an out-of-band effect journal). C's cell write did not collide with anything. The merge reported **clean**, committed `v18`, and replayed the effect journal in branch-completion order.

Two failures followed:

1. The payments provider honored the idempotency key only within a 24-hour window keyed on a *provider-side* dedup store that had been reset during a failover. Both charges settled. The idempotency key was correct and useless.
2. `notifications.send` was invoked once, but C's branch was later re-derived after a planner retry, and the re-derivation replayed the effect journal from a checkpoint that predated the merge — sending a second notification for the same order.

Neither failure was a memory conflict. Both were provenance failures: the effect journal recorded *what* was called but not *which branch-version lineage* the call belonged to, so the merge could not distinguish "the same call, deduplicated" from "two independent calls that happen to look identical."

## Condition of Validity

The write-set provenance invariant is valid — that is, the merge can be trusted to report "no conflict" honestly — only when all of the following hold:

- Every side-effecting tool call is stamped with `(branch_id, base_version, effect_id)` where `effect_id` is generated *before* the call is dispatched, not after it returns.
- The effect journal is append-only and is read by the merge under the same snapshot as the shared-memory write set.
- The merge's conflict predicate is defined over the *union* of the memory write set and the effect set, not the memory write set alone.
- Replay of the effect journal is gated on `effect_id` equality, and the gate is durable across provider failover, process restarts, and checkpoint re-derivation.

If any condition is absent, the merge's "clean" verdict is unsound. In the observed incident, the third condition was absent (effects were out-of-band), and the fourth was absent (the gate was provider-side and volatile).

## Decision Boundary

When the merge encounters two effect records with the same `(branch_id, base_version)` lineage but distinct `effect_id`s, it must treat this as a **conflict**, not a duplicate, and must not auto-resolve. When it encounters two records with the same `effect_id`, it may deduplicate — but only if the effect's dispatch is confirmed by a durable local receipt, never by trusting the provider's idempotency semantics.

When the merge encounters effects from causally unordered branches with distinct `effect_id`s, it has exactly two sound options: abort the merge and require the planner to re-plan from the common ancestor, or commit the memory merge and *quarantine* the effects for explicit human or policy resolution. There is no sound third option that silently serializes the effects, because serialization order is not a substitute for causal order when the effects are non-commutative (charge-then-refund is not refund-then-charge).

The boundary is therefore: **memory conflicts are mergeable; effect conflicts are not.** A merge that cannot prove effects commutative must not claim to have resolved them.

## Operational Effect

Enforcing write-set provenance converts a class of silent double-spend and double-notify failures into loud merge aborts. The cost is throughput: branches that speculatively execute side-effecting calls will abort more often, because the planner must now be conservative about forking branches that reach the same effect. The benefit is that the failure mode moves from "two charges settled and nobody noticed for six days" to "merge refused at `v18`, planner re-derived with a single charge branch."

In practice this means the effect journal must be first-class in the merge, not an audit log read after the fact. The merge's correctness argument is only as strong as the weakest of its two write sets.

```python
from dataclasses import dataclass


class EffectProvenanceError(RuntimeError):
    """Raised when a speculative merge cannot prove effect safety."""


@dataclass(frozen=True)
class EffectRecord:
    branch_id: str
    base_version: int
    effect_id: str
    tool: str
    commutative_with: frozenset  # tool names this effect may commute with


def merge_effects(effects: list[EffectRecord]) -> list[EffectRecord]:
    """Return the deduplicated effect set, or raise on unprovable conflict."""
    by_id: dict[str, EffectRecord] = {}
    for e in effects:
        if e.effect_id in by_id:
            prior = by_id[e.effect_id]
            if (prior.branch_id, prior.base_version) != (e.branch_id, e.base_version):
                raise EffectProvenanceError(
                    f"effect_id {e.effect_id} reused across branches "
                    f"{prior.branch_id} and {e.branch_id}; journal is corrupt"
                )
            continue
        by_id[e.effect_id] = e

    deduped = list(by_id.values())
    for i, a in enumerate(deduped):
        for b in deduped[i + 1:]:
            if a.base_version == b.base_version and a.branch_id != b.branch_id:
                if a.tool not in b.commutative_with or b.tool not in a.commutative_with:
                    raise EffectProvenanceError(
                        f"non-commutative effects from unordered branches "
                        f"{a.branch_id} and {b.branch_id}: "
                        f"{a.tool} vs {b.tool} at base v{a.base_version}"
                    )
    return deduped
```