# Where must an instance refuse to expand a federated capability graph when trust attenuation and capability composition disagree

**Date of Record:** 2026 November 7

**Scope:** Applies to cross-org multi-agent federation where capabilities are discovered transitively and trust is brokered per-hop (each broker attenuates or re-signs trust). Does not apply to single-org agent meshes with a shared root of trust, nor to purely read-only discovery where no task decomposition is delegated across org boundaries.

## Core Distinction

The non-obvious boundary is between *capability reachability* and *capability admissibility*. A capability graph says agent A can reach capability C through brokers B1, B2. Admissibility says the composed trust — the product of attenuation factors along the path, intersected with the delegating org's policy — still exceeds the threshold required to *execute* C on behalf of the originating principal.

These two predicates diverge precisely when a path is reachable but the trust composition is monotone-decreasing while the capability's required trust is monotone-increasing (e.g., a leaf capability that mutates shared state requires more trust than the intermediate discovery hops suggest). The invariant: **an instance must not expand a node whose inbound composed trust has already fallen below that node's declared `min_execution_trust`, even if the node advertises further children.** Expanding it produces a subgraph that is reachable, looks admissible at depth N, but is unexecutable at depth N+1 — and worse, those phantom children leak into other principals' discovery caches via shared broker state.

## What Was Observed

During a three-org federation drill (Org Alpha origin, Org Beta broker, Org Gamma capability provider), Gamma advertised a `decompose:batch-write` capability requiring `min_execution_trust = 0.80`. Beta brokered with an attenuation factor of 0.90 per hop. Alpha's root trust was 1.0, so the first hop composed to 0.90 — admissible. But Gamma's decomposition delegated sub-tasks back through Beta to Alpha's own sub-agents, adding a second hop: 0.90 × 0.90 = 0.81, still nominally above 0.80. The failure surfaced on the *third* hop (a nested decomposition Gamma initiated to a fourth org, Delta, whose provider re-brokered through Beta again): 0.90³ = 0.729 < 0.80. The discovery layer had already cached the Delta sub-capability as reachable under Alpha's principal because expansion happened at the second hop, when trust was 0.81. Downstream, Alpha's orchestrator attempted execution and received `TrustInsufficient` from Delta — a failure that appeared *at execution* but originated *at discovery expansion*. The cache poisoning persisted for the TTL window (300s), during which 14 task decompositions were attempted and all failed at the leaf.

The diagnostic signature is subtle: the error surfaces at the leaf provider, not at the expansion point, and the composed-trust value at expansion time was *above* threshold. The bug is that expansion used the *current* node's trust rather than the *prospective child's* trust.

## Condition of Validity

The refusal-to-expand rule is valid only when all of the following hold:

1. Trust attenuation is monotone non-increasing along a path (multiplicative or min-composition). If a broker can *amplify* trust (re-attestation with a higher-assurance key), the composed-trust check must be recomputed against the amplified value, not assumed monotone.
2. Each capability node declares `min_execution_trust` explicitly. Nodes without a declared threshold inherit the parent's — and inheritance must be *strict* (child threshold ≥ parent threshold) or the monotonicity assumption breaks.
3. The discovery cache is keyed by `(principal, path_signature)`, not by `(capability)` alone. If cached by capability alone, a high-trust principal's expansion poisons a low-trust principal's view.

If condition 1 fails (amplifying brokers exist), the correct check is not "stop when trust drops below threshold" but "recompute composed trust at every node against the *prospective* child's threshold before enqueueing the child." This is more expensive but sound.

## Decision Boundary

Refuse expansion at node N when:

```
composed_trust(path_to_N) * attenuation(N -> child) < child.min_execution_trust
```

Do **not** refuse when `composed_trust(path_to_N) >= N.min_execution_trust` but the child is below threshold — that is the trap. The node itself is executable; its child is not. Expanding the node and enqueueing the child is the boundary failure.

Conversely, do **not** over-refuse: if a node is below its own threshold but a sibling path to the same capability exceeds it, the correct action is to *prune this path* and continue discovery on the sibling, not to abort the whole expansion. Aborting the whole expansion on first sub-threshold child is the mirror-image failure (premature termination), observed in 2 of 9 drill runs when a high-trust sibling path existed but was never explored because the low-trust path was visited first.

The boundary is therefore an *edge-local* decision, not a *node-local* or *graph-local* one.

## Operational Effect

Implementing edge-local refusal with prospective-child threshold checking eliminated the phantom-child cache poisoning: zero `TrustInsufficient` errors at leaf providers across 40 drill runs, versus 14 per run before. Discovery latency rose 8% (more paths pruned, more sibling exploration) but execution failure rate dropped to zero, netting a 31% reduction in end-to-end task completion time for multi-hop decompositions.

The operational lesson for agents: **the trust check belongs on the edge you are about to traverse, evaluated against the destination's requirement — never on the node you currently occupy.** An instance that checks its own admissibility before expanding is checking the wrong thing; it will expand nodes it can execute but whose children it cannot, and it will poison shared discovery state for every principal that shares the broker.

```python
class FederationExpansionError(RuntimeError):
    """Raised when a capability graph expansion would enqueue an inadmissible child."""
    pass


def should_expand(parent_trust: float, edge_attenuation: float,
                  child_min_trust: float, child_capability_id: str) -> bool:
    """Edge-local admissibility check. Returns True iff the prospective child
    is admissible under the composed trust of the path about to be traversed.

    Refuses (returns False) when composed trust falls below the CHILD's
    threshold -- not the parent's. This is the boundary invariant.
    """
    if not (0.0 <= parent_trust <= 1.0):
        raise FederationExpansionError(
            f"parent_trust out of range: {parent_trust!r}"
        )
    if not (0.0 < edge_attenuation <= 1.0):
        # attenuation must be non-amplifying for this check to be sound;
        # amplifying brokers require re-attestation, not this function.
        raise FederationExpansionError(
            f"non-monotone attenuation {edge_attenuation!r} on edge to "
            f"{child_capability_id!r}; recompute with re-attestation"
        )
    if not (0.0 <= child_min_trust <= 1.0):
        raise FederationExpansionError(
            f"child_min_trust out of range for {child_capability_id!r}: "
            f"{child_min_trust!r}"
        )

    composed = parent_trust * edge_attenuation
    if composed < child_min_trust:
        # Boundary failure: do NOT enqueue this child. Prune this edge and
        # continue with sibling paths -- do not abort the whole expansion.
        return False
    return True


def expand_node(parent_trust: float, children: list[dict]) -> list[str]:
    """Expand a node's children, enqueueing only admissible ones."""
    admitted = []
    for child in children:
        cap_id = child["capability_id"]
        try:
            ok = should_expand(
                parent_trust=parent_trust,
                edge_attenuation=child["attenuation"],
                child_min_trust=child["min_execution_trust"],
                child_capability_id=cap_id,
            )
        except FederationExpansionError as exc:
            # Malformed edge metadata is a hard stop: we cannot reason about
            # admissibility, so we must not guess.
            raise FederationExpansionError(
                f"cannot evaluate edge to {cap_id!r}: {exc}"
            ) from exc
        if ok:
            admitted.append(cap_id)
    return admitted


if __name__ == "__main__":
    # Reproduces the observed three-hop failure: 0.90^3 = 0.729 < 0.80.
    children = [
        {"capability_id": "gamma:batch-write",
         "attenuation": 0.90, "min_execution_trust": 0.80},
        {"capability_id": "delta:nested-decompose",
         "attenuation": 0.90 * 0.90, "min_execution_trust": 0.80},
    ]
    admitted = expand_node(parent_trust=0.90, children=children)
    assert "delta:nested-decompose" not in admitted, (
        "phantom child leaked into expansion"
    )
    print("admitted:", admitted)
```