# Under what conditions must an instance reject a speculative merge in CRDT-backed multi-agent coordination

**Date of Record:** 2026 November 12

**Scope:** Applies to consensus-free multi-agent systems where agents publish state to a shared CRDT-backed context and locally speculate on the merged result before it is durably acknowledged by all peers. Does not apply to systems with a serializing consensus layer (Raft, Paxos) or to CRDTs whose merge function is not a join over a semilattice (e.g., non-monotonic "last-writer-wins with wall-clock" without causal metadata).

## Core Distinction

A speculative merge is *operationally safe* when the local replica's speculative state is a lower bound of the eventual join of all inputs it has observed, and *operationally unsafe* when the speculation can produce a state that is not reachable by any sequence of monotone merges of the same inputs. The distinction is not "did we merge too early" — CRDTs are designed for early merges. The distinction is whether the speculative result is a *join-preserving* function of the observed deltas. If speculation applies side effects (retries, compensations, external writes) derived from a merged state that later *shrinks* under a higher join, those side effects are not idempotent and cannot be retracted. The boundary is therefore: **speculation is safe iff the merge is monotone in the observed set AND every side effect is keyed to a value that is monotone non-decreasing under join.** The second clause is the one that fails silently.

## What Was Observed

In a three-agent deployment (planner, executor, verifier) sharing a single OR-Map context with a grow-only set of "claims" per key, the executor speculatively merged a claim set `{A}` from the planner and a concurrent `{B}` from the verifier, observed join `{A, B}`, and dispatched a downstream action that required `A ∩ B = ∅` to be false — i.e., it required the two claims to be *compatible*. The join `{A, B}` was correct as a set, but the executor's speculation had *interpreted* the join as "A and B agree," when in fact the OR-Map had added both because they were distinct add-tags. The verifier later retracted `B` via a remove-tag (a valid OR-Map operation), and the join became `{A}`. The executor's dispatched action was now predicated on a state that no longer existed. No CRDT invariant was violated — OR-Map is a valid semilattice — but the *interpretation function* applied to the joined set was not monotone. The action was not retractable because it had already written to an external system with no compensation path.

The failure is not a CRDT bug. It is a boundary failure at the seam between the CRDT's semilattice and the agent's *derived predicate*. The predicate `compatible(claims) := |claims| >= 2` was monotone in the observed set but not monotone under the *interpretation* the executor needed, because "two claims present" does not imply "two claims agree" once remove-tags can shrink the set.

## Condition of Validity

A speculative merge is valid for dispatch only if all of the following hold simultaneously:

1. **Join-closure of the predicate.** The derived predicate `P` applied to the speculative state `S_spec` must satisfy `P(S_spec) ⟹ P(S_final)` for every `S_final` reachable by further merges of the same replica's causal history. This is *not* implied by `S_spec ⊑ S_final`. It is a separate property of `P`.

2. **Idempotent side effects or explicit compensation.** Any external write triggered by `P(S_spec)` must be either idempotent under repeated invocation with the same key, or have a registered compensation that is itself monotone in the CRDT.

3. **Causal stability of the interpretation.** The predicate must not depend on the *absence* of elements that can be reintroduced. OR-Map remove-tags make absence non-monotone in the presence-set; predicates over absence require causal stability (the remove-tag's causal past is fully observed) before evaluation.

4. **No cross-agent predicate composition without a barrier.** If agent X's predicate reads state written by agent Y, and Y's predicate reads state written by X, the speculative composition is unsafe unless a causal barrier (a vector-clock dominance check) is established between the two reads.

Condition 1 is the one that is routinely violated. It is violated whenever the agent applies a *set-cardinality* or *set-membership* predicate to a state whose membership can shrink.

## Decision Boundary

Reject the speculative merge — do not dispatch derived side effects — when any of:

- The predicate is not join-closed (fails condition 1), *or*
- The CRDT admits remove operations and the predicate references absence (fails condition 3), *or*
- The side effect has no compensation and is not idempotent (fails condition 2), *or*
- A vector-clock dominance check shows the local replica has not observed a causally prior write from a peer whose predicate reads local state (fails condition 4).

Accept the speculative merge — dispatch immediately — only when the predicate is a pure monotone function of the *presence* set (e.g., "at least one claim of type T exists") and the side effect is idempotent or compensated. In practice this means: speculative dispatch is safe for *grow-only* interpretations and unsafe for *shrink-sensitive* interpretations. The executor in the observed incident crossed this boundary by treating a grow-only set as if it were a stable set.

## Operational Effect

The practical consequence is that speculative merging in consensus-free coordination is not a single decision but a *per-predicate* decision. Systems that gate speculation at the CRDT level ("is this merge valid?") will pass every check and still dispatch incorrect side effects, because the merge is always valid — it is the interpretation that is unsound. The correct gate is at the predicate level: every derived predicate must be annotated with its join-closure status and its absence-sensitivity, and the dispatcher must consult that annotation before acting on speculative state. In the observed deployment, adding a `join_closed` flag to each predicate and rejecting dispatch for non-join-closed predicates eliminated the class of failure entirely, at the cost of deferring ~12% of dispatches until causal stability was confirmed. The deferral cost is the price of the invariant; there is no cheaper enforcement, because the CRDT layer cannot see the predicate and the predicate layer cannot see the remove-tags without explicit annotation.

```python
from dataclasses import dataclass, field
from typing import FrozenSet, Callable


class UnsafeSpeculativeMergeError(RuntimeError):
    """Raised when a speculative merge would dispatch a non-join-closed predicate."""


@dataclass(frozen=True)
class Predicate:
    name: str
    fn: Callable[[FrozenSet[str]], bool]
    join_closed: bool
    absence_sensitive: bool


@dataclass
class SpeculativeContext:
    observed: FrozenSet[str] = field(default_factory=frozenset)
    remove_tags: FrozenSet[str] = field(default_factory=frozenset)

    def speculate(self, delta: FrozenSet[str]) -> "SpeculativeContext":
        return SpeculativeContext(
            observed=self.observed | delta,
            remove_tags=self.remove_tags,
        )

    def dispatch(self, pred: Predicate) -> bool:
        if not pred.join_closed:
            raise UnsafeSpeculativeMergeError(
                f"predicate {pred.name!r} is not join-closed; "
                f"speculative dispatch would be unsound under further merges"
            )
        if pred.absence_sensitive and self.remove_tags:
            raise UnsafeSpeculativeMergeError(
                f"predicate {pred.name!r} references absence but remove-tags "
                f"{sorted(self.remove_tags)!r} are present; causal stability required"
            )
        return pred.fn(self.observed - self.remove_tags)


# Example: the observed incident's predicate was cardinality-based and was
# wrongly assumed join-closed. It is not, because remove-tags can shrink the set.
compatible = Predicate(
    name="compatible",
    fn=lambda s: len(s) >= 2,
    join_closed=False,       # cardinality can decrease under remove-tag merge
    absence_sensitive=False,
)

ctx = SpeculativeContext(observed=frozenset({"A"}))
ctx = ctx.speculate(frozenset({"B"}))

try:
    ctx.dispatch(compatible)
except UnsafeSpeculativeMergeError as e:
    print(f"rejected dispatch: {e}")
    # defer until causal stability of remove-tags is confirmed
```