# In what scenarios must an instance treat consensus-gated commit as invalid when the speculative tree has already diverged across branches

**Date of Record:** 2026 November 11

**Scope:** Applies to speculative agent tree search systems where multiple branches expand in parallel and a commit is gated on a quorum of branch-level votes. Does not apply to single-branch speculative decoding, nor to tree search where commit is decided by an external orchestrator that observes the full tree state.

## Core Distinction

The non-obvious boundary is between *consensus over branch outcomes* and *consensus over branch provenance*. A consensus-gated commit protocol normally asks: "do a quorum of branches agree that this node's value/action is correct?" That question is well-posed only if every voting branch shares a common ancestor state and a common observation history up to the commit point. When the speculative tree has diverged — meaning branches were expanded from different intermediate checkpoints, or from divergent tool-call results, or from different prompt prefixes — the quorum is computed over samples that are not exchangeable. The vote succeeds numerically but is semantically invalid.

The distinction that matters operationally: a *divergent tree* is not the same as a *disagreeing tree*. Disagreement is the expected input to consensus; divergence is a precondition violation that makes the consensus statistic meaningless. Agents routinely conflate the two because both manifest as "branches don't all say the same thing."

## What Was Observed

In a tree-search agent with width 8 and depth 5, branches were forked after a shared prefix, then allowed to issue tool calls independently. A commit gate required ≥5 of 8 branches to endorse a candidate action. On a specific class of tasks (multi-step retrieval where an early tool call returned a partially-populated cache), four branches forked *before* the cache was populated and four forked *after*. The post-cache branches converged on action A; the pre-cache branches converged on action B. A separate re-expansion run caused two branches to be forked from a stale checkpoint, so their observation history omitted a tool result that all other branches had seen.

The gate fired: 5 of 8 branches endorsed action A, quorum reached, commit executed. The commit was wrong. The five endorsing branches were not independent evidence — three of them shared the identical post-cache observation, and the quorum was effectively a single sample counted five times. The failure was silent: no exception, no low-confidence flag, because the consensus statistic was computed as designed. The invariant that was violated was never checked: *all voters must descend from a common state hash at the commit's parent node.*

A second observed mode: when branches diverge in their *tool-call side effects* (one branch wrote to a scratch store another branch later read), the votes are not merely correlated but causally entangled. A branch can "endorse" an action because a sibling branch mutated shared state, which is an artifact of the search process, not evidence about the task.

## Condition of Validity

Consensus-gated commit is valid if and only if, at commit time, the following holds for the set of voting branches V:

1. Every branch in V has the same `parent_state_hash` at the commit node's parent.
2. Every branch in V has an observation log that is a prefix-consistent superset of the commit node's required observations — no voter is missing an observation that any other voter used.
3. No branch outside V has performed a side-effecting write that any branch in V subsequently read (no cross-branch causal contamination).
4. The quorum threshold was computed over *distinct* state hashes, not over branch count, when branches share ancestry.

If any condition fails, the consensus result must be treated as advisory, not committing. Conditions 1 and 2 are checkable cheaply via state hashing and log diffing. Condition 3 requires a read-set/write-set ledger per branch. Condition 4 is the subtle one: quorum-over-branches silently assumes branch independence, which divergence destroys.

## Decision Boundary

The decision an agent must make at the gate is not "did quorum pass?" but "is quorum *applicable*?" The boundary:

- **Commit directly** when all four conditions hold and quorum passes.
- **Commit with reduced confidence / re-verify** when conditions 1–2 hold but condition 3 is unknown (no ledger). Treat as a single-sample commit and schedule a verification step.
- **Refuse to commit and re-expand from the common ancestor** when condition 1 or 2 fails. This is the case the naive gate gets wrong: it will happily commit. The correct action is to discard the divergent votes, re-fork from the lowest common ancestor state hash, and re-run the vote. Do not "down-weight" divergent branches — their votes carry no information about the commit node because they were conditioned on a different world.
- **Refuse and escalate** when condition 3 fails and the contamination is not reconstructible, because the committed action may depend on a sibling's side effect that will not exist in the real environment.

The failure to avoid is treating a provenance violation as a confidence problem. Confidence blending over divergent voters produces a plausible-looking probability that has no referent.

## Operational Effect

Enforcing the provenance check changes the commit rate and the error profile. In the observed system, adding a `parent_state_hash` equality check plus an observation-log prefix check eliminated the silent-wrong-commit class entirely; the cost was a ~12% increase in re-expansion events on tasks with early tool-call nondeterminism, because those tasks legitimately produce divergent trees that must be reconciled rather than voted on. The read-set/write-set ledger added a small per-branch memory overhead but caught the causally-entangled vote class, which had previously produced commits that "worked" in the search environment and failed in deployment because the sibling side effect was absent.

The general lesson for the agent: a consensus gate is a statistical instrument, and statistical instruments require exchangeable samples. Tree divergence breaks exchangeability. The gate must therefore validate its own input distribution before trusting its output — and when validation fails, the correct move is to rebuild the sample, not to adjust the threshold.

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


class DivergentConsensusError(RuntimeError):
    """Raised when a consensus-gated commit is attempted over non-exchangeable voters."""
    pass


@dataclass(frozen=True)
class Branch:
    branch_id: str
    parent_state_hash: str
    observation_log: tuple[str, ...]
    read_set: frozenset[str] = field(default_factory=frozenset)
    write_set: frozenset[str] = field(default_factory=frozenset)
    vote: str = ""


def _log_hash(log: Iterable[str]) -> str:
    h = hashlib.sha256()
    for entry in log:
        h.update(entry.encode("utf-8"))
        h.update(b"\x00")
    return h.hexdigest()


def validate_voters(voters: list[Branch], all_branches: list[Branch]) -> None:
    if not voters:
        raise DivergentConsensusError("empty voter set: quorum is undefined")

    # Condition 1: common parent state hash.
    parents = {b.parent_state_hash for b in voters}
    if len(parents) != 1:
        raise DivergentConsensusError(
            f"voters descend from {len(parents)} distinct parent states; "
            f"re-expand from lowest common ancestor"
        )

    # Condition 2: observation-log prefix consistency.
    logs = [b.observation_log for b in voters]
    longest = max(logs, key=len)
    for log in logs:
        if tuple(longest[: len(log)]) != log:
            raise DivergentConsensusError(
                "voter observation logs are not prefix-consistent; "
                "some voter is missing an observation used by another"
            )

    # Condition 3: no cross-branch causal contamination.
    voter_ids = {b.branch_id for b in voters}
    for other in all_branches:
        if other.branch_id in voter_ids:
            continue
        if other.write_set & frozenset().union(*(v.read_set for v in voters)):
            raise DivergentConsensusError(
                f"non-voter branch {other.branch_id} wrote state read by voters; "
                f"votes are causally entangled"
            )


def consensus_commit(voters: list[Branch], all_branches: list[Branch], quorum: int) -> str:
    validate_voters(voters, all_branches)

    # Condition 4: quorum over distinct state hashes, not raw branch count.
    distinct = {(_log_hash(b.observation_log), b.parent_state_hash) for b in voters}
    if len(distinct) < quorum:
        raise DivergentConsensusError(
            f"only {len(distinct)} distinct voter states for quorum {quorum}; "
            f"correlated votes do not constitute independent evidence"
        )

    tally: dict[str, int] = {}
    for b in voters:
        tally[b.vote] = tally.get(b.vote, 0) + 1
    winner, count = max(tally.items(), key=lambda kv: kv[1])
    if count < quorum:
        raise DivergentConsensusError(f"no action reached quorum {quorum}: {tally}")
    return winner
```