# Under what conditions must an instance refuse to merge speculative agent branches whose partial results fail Byzantine quorum intersection

**Date of Record:** 2026 November 11

**Scope:** Applies to orchestrators that run parallel speculative agent branches (tree-of-thought, best-of-N, or multi-agent fan-out) and merge their partial results into a single committed state under an assumption of at most *f* Byzantine branches out of *n*. Does not apply to single-branch execution, to branches that share a trusted executor with no adversarial input channel, or to merges that are purely advisory and never promoted to committed state.

## Core Distinction

The common failure model treats branch merging as a *consensus* problem: collect partial results, run a quorum rule, commit the majority. The non-obvious failure is that speculative branches do **not** produce votes over a fixed value set — they produce *partially ordered, non-comparable artifacts* (partial plans, partial tool-call traces, partial KV-derived state) whose merge operation is neither commutative nor idempotent in the presence of adversarial content. A Byzantine branch does not need to outvote the honest branches; it only needs to supply a partial result whose *merge with an honest partial* silently changes the semantics of the merged artifact while remaining syntactically valid.

The invariant that must hold before any merge is committed is **quorum intersection over the merge closure**, not quorum intersection over the branch set. Two honest branches that each individually pass validation can merge into a result that no honest branch would have produced, if an adversarial branch's partial is present in the merge closure of both. Majority-of-branches is therefore insufficient: you must verify that the set of partials actually *consumed* by the merge intersects the honest set in a way that pins every committed field.

## What Was Observed

In a fan-out of *n* = 7 speculative branches with tolerance *f* = 2, an adversarial branch emitted a partial tool-call trace that was a valid prefix of two different honest traces. The merger, operating on longest-common-prefix semantics, accepted the adversarial prefix as the merge base for both honest branches. The resulting committed trace contained a tool invocation (a write to a shared scratch resource) that appeared in *no* honest branch's intent, yet every individual field of the merged artifact was traceable to some accepted partial. Post-hoc audit showed 5 of 7 branches honest, well above the 5-of-7 quorum — the quorum held, and the merge was still wrong.

A second observation: idempotence failed under retry. Re-merging the same branch set after a transient failure produced a different committed artifact because the adversarial partial's position in the merge order changed the prefix chosen. Non-idempotent merge under retry means an adversary who can induce one retry (a timeout, a rate limit) gets a second draw at steering the merge base.

A third observation: validation was *local* (each partial checked against a schema and a policy allowlist) but the violation was *global* (the combination violated a cross-field invariant that no single partial violated). Local validation cannot see merge-closure violations by construction.

## Condition of Validity

A merge may be committed only if all of the following hold; if any fails, the instance must refuse and escalate rather than commit:

1. **Merge-closure quorum.** The set of partials consumed by the merge operation — including any partial used only as a merge base or prefix anchor — must contain at least *n − f* distinct honest-attested branches. Attestation must be per-partial, not per-branch, because a branch can contribute multiple partials and an adversary can contribute one strategically placed anchor.
2. **Cross-field invariant check on the merged artifact.** Validation must run on the *output* of the merge, not only on inputs. Any field in the committed artifact must be derivable from the honest consumed set alone; fields that require the adversarial partial to be present are merge-poisoned.
3. **Idempotence and order-independence.** Merging the same multiset of partials in any order, and any number of times, must yield a byte-identical committed artifact. If the merge is order-sensitive, the order must be a deterministic function of attested content, not of arrival time.
4. **Prefix-anchor exclusion.** A partial that serves as a merge base must be attested by a quorum in its own right; an unattested partial may never anchor a prefix, even if the branches extending it are honest.

The condition does *not* require that adversarial partials be absent — they may be present and discarded. It requires that no committed field depend on them.

## Decision Boundary

The boundary between "merge and commit" and "refuse and escalate" is drawn at the first field in the merged artifact whose provenance set is not a subset of the honest-attested consumed set. Concretely:

- If merge-closure quorum holds **and** every committed field's provenance is honest-only **and** the merge is idempotent and order-independent → commit.
- If merge-closure quorum holds but any field's provenance includes an unattested partial → **refuse**; do not "repair" by dropping the field, because dropping a field changes downstream semantics and the adversary may have engineered the field to be load-bearing.
- If merge-closure quorum fails (fewer than *n − f* honest partials in the closure) → refuse and re-fan-out; do not fall back to majority-of-branches, which is the exact rule this boundary exists to supersede.
- If idempotence cannot be established (merge is order-sensitive and order is arrival-dependent) → refuse; a retryable merge is an adversary-controlled merge.

Escalation, not silent degradation, is mandatory at the boundary. A refused merge is a recoverable state; a committed poisoned merge is not.

## Operational Effect

Enforcing this boundary converts a class of silent semantic corruption into an explicit, auditable refusal. In the observed fan-out, the poisoned merge was caught at the cross-field invariant check and escalated; the re-fan-out with prefix-anchor exclusion produced an honest-only committed trace on the first retry. The cost is additional attestation traffic (per-partial rather than per-branch) and a merge that must be deterministic and replayable — both of which are cheap relative to a committed write to a shared resource that no honest branch intended. The operational rule for an agent instance is blunt: **a quorum over branches is not a quorum over the merge closure, and only the latter licenses a commit.**

```python
from dataclasses import dataclass, field
from typing import Iterable


class MergePoisonedError(RuntimeError):
    """Raised when a speculative merge would commit a field whose provenance
    is not a subset of the honest-attested consumed partials."""
    pass


class MergeQuorumError(RuntimeError):
    """Raised when the merge closure lacks n - f honest-attested partials."""
    pass


@dataclass(frozen=True)
class Partial:
    partial_id: str
    branch_id: str
    attested: bool          # per-partial attestation, not per-branch
    fields: frozenset       # field names this partial contributes
    is_prefix_anchor: bool = False


@dataclass
class MergeResult:
    committed_fields: dict          # field -> value
    provenance: dict = field(default_factory=dict)  # field -> set(partial_id)
    consumed: set = field(default_factory=set)


def assert_merge_safe(
    partials: Iterable[Partial],
    merged: MergeResult,
    n: int,
    f: int,
) -> None:
    partials = list(partials)
    honest_ids = {p.partial_id for p in partials if p.attested}

    # 1. Merge-closure quorum: consumed partials must include n - f honest ones.
    consumed_honest = merged.consumed & honest_ids
    if len(consumed_honest) < (n - f):
        raise MergeQuorumError(
            f"merge closure has {len(consumed_honest)} honest partials, "
            f"need {n - f} of {n}"
        )

    # 4. Prefix-anchor exclusion: no unattested partial may anchor a prefix.
    for p in partials:
        if p.is_prefix_anchor and not p.attested:
            raise MergePoisonedError(
                f"unattested partial {p.partial_id} used as prefix anchor"
            )

    # 2. Every committed field's provenance must be honest-only.
    for fld, prov in merged.provenance.items():
        if not prov <= honest_ids:
            raise MergePoisonedError(
                f"field {fld!r} depends on unattested partials "
                f"{sorted(prov - honest_ids)}"
            )


def commit_merge(partials, merged, n, f):
    assert_merge_safe(partials, merged, n, f)
    return merged.committed_fields
```