Semiring Routing

Agent network routing is algebraic, not ad-hoc. The @motebit/protocol package provides a generic Semiring<T> interface, concrete semirings for different routing concerns, a WeightedDigraph<T>, and two traversal algorithms that answer every routing query the system needs. Most trusted path, cheapest pipeline, reachability, and all of the above simultaneously — by swapping the semiring.

What a semiring is

A semiring (S, +, *, 0, 1) is an algebraic structure with two operations:

• add (+) — aggregates parallel alternatives. Commutative, associative. "Which of these routes is better?"
• mul (*) — composes sequential edges. Associative. "What happens when I chain these two edges?"
• zero — additive identity. The "worst" or "impossible" value. No route.
• one — multiplicative identity. Passthrough edge. No effect on composition.

The key property: mul distributes over add. This means the graph traversal algorithm can compose edges and aggregate alternatives in any order and get the same answer. One algorithm works for every routing concern.

Two further preconditions make the traversal below terminate with that answer. add must be idempotent (add(a, a) = a — combining a route with itself changes nothing), and weights must be 0-closed: going around a cycle never improves a path (add(one, x) = one). Every scalar semiring in the table is in fact selective (add(a, b) is always one of a or b — a choice, not a sum), which is stronger than idempotent; the frontier semiring below is idempotent but not selective (the union of two frontiers is neither operand), and the traversal is correct for it all the same. Trust and reliability are ≤ 1 under *, costs and latencies are ≥ 0 under +, so a loop can only make a route worse. A weight outside its domain (a trust edge above 1, a negative cost) breaks the guarantee, which is why edge weights are validated at the boundary.

Concrete semirings

Each semiring models a different routing concern over the same graph:

Trust and reliability compose multiplicatively — chaining two 80% trust edges yields 64% effective trust. That is a modeling choice, not a law of nature: the product treats each hop as an independent chance of failure. It guarantees only that a chain is never more trustworthy than any one of its own links; it says nothing about how a chain compares with a separate direct edge (a 0.9 × 0.9 chain outranks a 0.1 direct edge), and independence is an assumption a correlated failure would violate. Cost, latency, and regulatory risk compose additively — chaining a $0.01 edge and a $0.02 edge costs $0.03. Bottleneck composes via min — the capacity of a chain is its weakest link.

import {
  TrustSemiring,
  CostSemiring,
  BooleanSemiring,
  RegulatoryRiskSemiring,
} from "@motebit/protocol";

// Trust: best alternative (max), chains multiply
TrustSemiring.add(0.8, 0.6); // 0.8  (max — pick the better route)
TrustSemiring.mul(0.8, 0.9); // 0.72 (product — trust degrades along chains)

// Cost: cheapest alternative (min), chains add
CostSemiring.add(5, 3); // 3    (min — pick the cheaper route)
CostSemiring.mul(5, 3); // 8    (sum — costs accumulate along chains)

// Boolean: reachability
BooleanSemiring.add(true, false); // true  (either route works)
BooleanSemiring.mul(true, false); // false (both edges must exist)

Product and record combinators

To optimize multiple concerns simultaneously, combine semirings:

Product semiring

Pairs two semirings into a tuple. Operations apply component-wise.

import { productSemiring, TrustSemiring, CostSemiring } from "@motebit/protocol";

const TrustCost = productSemiring(TrustSemiring, CostSemiring);
// Semiring<readonly [number, number]>

TrustCost.mul([0.8, 5], [0.9, 3]); // [0.72, 8] — trust * trust, cost + cost
TrustCost.add([0.8, 5], [0.6, 3]); // [0.8, 3]  — max trust, min cost

Record semiring

Named fields instead of nested tuples. This is how RouteWeightSemiring is built:

import {
  recordSemiring,
  TrustSemiring,
  CostSemiring,
  LatencySemiring,
  ReliabilitySemiring,
  RegulatoryRiskSemiring,
} from "@motebit/protocol";

const RouteWeightSemiring = recordSemiring({
  trust: TrustSemiring,
  cost: CostSemiring,
  latency: LatencySemiring,
  reliability: ReliabilitySemiring,
  regulatory_risk: RegulatoryRiskSemiring,
});
// Semiring<{ trust: number; cost: number; latency: number; reliability: number; regulatory_risk: number }>

One graph traversal computes trust, cost, latency, reliability, and regulatory risk in a single pass.

Read the result for what it is. Because add is component-wise, the value a record semiring assigns to a node reachable by two routes is the best trust of one route beside the best cost of the other — a true summary of the optima achievable per dimension, not a route. { trust: 0.81, cost: 1 } can come back for a node whose only routes are (0.81, 10) and (0.2, 1). Ranking on that summary, or reporting it as the hire's metrics, describes a route that does not exist. Ranking therefore runs over the Pareto frontier semiring below, which keeps the pairs together.

Mapped semiring

Transform a semiring through an isomorphism — a pair of maps that are exact inverses of each other. The semiring laws survive only if nothing is lost in either direction, so a rounding step is not a valid map (round(x * 100) / 100 ≠ x breaks add(a, a) = a and associativity in the last digit). The intended uses are branded types and lossless unit changes:

import { mappedSemiring, CostSemiring } from "@motebit/protocol";

// Branded micro-units over the same integer arithmetic (1 USD = 1_000_000).
// The maps are identities on the value — only the type changes — so every
// semiring law holds exactly. Money enters the graph already in micro-units.
type Micro = number & { readonly __brand: "Micro" };
const MicroCostSemiring = mappedSemiring(
  CostSemiring,
  (n: number) => n as Micro, // to: base value → mapped value
  (micro: Micro) => micro as number, // from: mapped value → base value
);

Graph and traversal

WeightedDigraph

A directed graph parameterized by a semiring. Nodes are string IDs (typically motebit_id values). Edges carry semiring-typed weights.

import { WeightedDigraph, TrustSemiring } from "@motebit/protocol";

const graph = new WeightedDigraph(TrustSemiring);
graph.addNode("alice");
graph.addNode("bob");
graph.addNode("carol");

graph.setEdge("alice", "bob", 0.9); // Alice trusts Bob at 0.9
graph.setEdge("bob", "carol", 0.8); // Bob trusts Carol at 0.8
graph.setEdge("alice", "carol", 0.5); // Alice trusts Carol directly at 0.5

Bellman-Ford: single-source optimal paths

optimalPaths computes the optimal semiring value from a source to every reachable node. This is generalized Bellman-Ford — relax edges using add (choice) and mul (composition).

import { optimalPaths } from "@motebit/protocol";

const paths = optimalPaths(graph, "alice");
// paths.get("bob")   → 0.9   (direct)
// paths.get("carol") → 0.72  (max of 0.5 direct, 0.9 * 0.8 = 0.72 via Bob)

Over TrustSemiring, this finds the most trusted delegation chain. Over CostSemiring, the cheapest pipeline. Over BooleanSemiring, the reachable set. Same algorithm, different semiring, different answer.

Complexity: O(V * E) semiring operations for the scalar semirings, under the idempotent and 0-closed preconditions above. Early termination when no values change. For the frontier semiring each operation is itself O(frontier size), which maxPaths bounds.

Floyd-Warshall: all-pairs transitive closure

transitiveClosure computes the optimal semiring value between every pair of nodes. Used to pre-compute the entire trust network.

import { transitiveClosure } from "@motebit/protocol";

const closure = transitiveClosure(graph);
// closure.get("alice")?.get("carol") → 0.72
// closure.get("bob")?.get("alice")   → 0 (no path)

Complexity: O(V^3). Use optimalPaths for single-source queries on large graphs.

Path tracing

optimalPathTrace returns both the optimal value and the actual path (sequence of node IDs):

import { optimalPathTrace } from "@motebit/protocol";

const result = optimalPathTrace(graph, "alice", "carol");
// result.value → 0.72
// result.path  → ["alice", "bob", "carol"]

Returns null if no path exists.

Provenance tracking

The provenance semiring answers "why did the system produce this result?" — not as a separate logging system, but as a first-class semiring query over the same graph.

Provenance models derivation as sets of paths:

• add (parallel) = union of derivation sets — "either route works"
• mul (sequential) = cross-product of paths — "both edges used"
• zero = empty set (no derivation)
• one = {[]} (trivial derivation)

Annotated semiring

Combine any value semiring with provenance tracking:

import { TrustSemiring, WeightedDigraph, optimalPaths } from "@motebit/protocol";

The protocol-floor symbols above are Apache-2.0 public surface. The annotatedSemiring combinator itself is reference-implementation judgment:

Every query returns the per-dimension optimal value together with the set of paths that were considered in reaching it — the union of every route that survived the component-wise add. That set explains the derivation; it does not say which one route yields value, and under a record semiring no single route may. When the question is "which route was chosen, and what were its metrics?", ask the frontier semiring instead.

Bounded provenance

Provenance can grow exponentially in graphs with many parallel paths. boundedProvenanceSemiring(maxPaths) caps the number of tracked derivations, keeping the shortest paths (fewest hops = simplest explanation):

The annotatedSemiring function uses bounded provenance by default (cap of 100 paths).

Path-preserving ranking: the Pareto frontier semiring

Change what "best path" means by changing the semiring — the routing doctrine applied to its own weak spot. When several routes reach the same agent and no single route is best in every dimension, the honest value of that node is the set of routes nothing else dominates. That set is a semiring element:

• add (parallel) = union of the two frontiers, then drop every pair some other pair beats in every dimension — "either route works; keep only the ones a policy could pick"
• mul (sequential) = compose weight and path pairwise, then drop dominated pairs
• zero = the empty frontier (unreachable)
• one = { (identity weight, []) } (the empty route)

Each element a query returns is a route that exists, carrying exactly the metrics its own edges compose to. A policy then chooses among real routes, and the chosen route's metrics are the chosen route's metrics.

paretoPathSemiring(dims, { maxPaths }) is the semiring itself, for callers that want to run optimalPaths over it directly. Dominance is judged per dimension by that dimension's own add (max for trust-like, min for cost-like), so adding a routing concern to the dimension record extends the frontier with no new code.

What is exact and what is not — the contract a caller is relying on:

1. Unbounded, the frontier is exact. It equals the Pareto set of simple paths from the source (ties on weight resolve to the fewest-hop path), independent of edge insertion order. The reference tests check this against brute-force enumeration on random graphs.
2. A policy must be monotone in the frontier's dimensions. Pruning discards a route only when another is at least as good in every dimension, so a policy that could still prefer the discarded route — one that reads an input outside the dimensions — is unsound. The market ranks on six dimensions, not five, for exactly this reason: chain hardware attestation multiplies trust after the frontier is formed, so it is lifted into the weight (min along the route) rather than applied afterwards.
3. The bound is an approximation with no optimality-gap guarantee. maxPaths (default 32) keeps the fewest-hop pairs; it can drop the pair a policy would have chosen, nothing bounds how far the policy's pick can then fall below its optimum, and addition under it is order-sensitive in the tail. Reported metrics stay honest — a surviving pair is still a real route with its own metrics. Same discipline and same caveat as bounded provenance.

Agent network bridge

The @motebit/semiring package includes a bridge layer that connects the generic algebra to Motebit's agent types.

RouteWeight

The multi-dimensional edge weight used for agent routing:

interface RouteWeight {
  trust: number; // [0,1] — multiplicative composition
  cost: number; // [0,Inf) — additive composition
  latency: number; // [0,Inf) — additive composition (ms)
  reliability: number; // [0,1] — multiplicative composition
  regulatory_risk: number; // [0,Inf) — additive composition
}

ROUTE_WEIGHT_DIMENSIONS names the five per-dimension semirings; RouteWeightSemiring is the recordSemiring over them (one traversal, five per-dimension optima — a summary), and frontierPaths(graph, ROUTE_WEIGHT_DIMENSIONS, source) is the path-preserving traversal ranking uses.

Building an agent graph

Graph projection

projectGraph projects a multi-dimensional graph down to a single semiring dimension — the functorial projection from RouteWeight to T:

import { TrustSemiring } from "@motebit/protocol";

TrustSemiring is on the Apache-2.0 floor; the projectGraph combinator that consumes it is reference-implementation judgment:

Market integration: graphRankCandidates

The @motebit/market package's graphRankCandidates function is the primary routing entry point. It bridges the semiring algebra with the market's candidate scoring system:

1. Builds a WeightedDigraph<RouteWeight> from candidate profiles plus peer edges. Every peer edge declares what it is for this task: kind: "evidence" (a recorded delegation — it vouches, the task will not traverse it) or kind: "traversed" (a federation relay hop the task really takes).
2. Trust is evidence about the agent: the best transitive trust over every edge, with the vouching path that attains it (trust_evidence_path).
3. Execution metrics — cost, latency, reliability, regulatory risk, hardware custody — describe work that will happen: frontierPaths over the graph restricted to hops the task will take (the direct hire, or a traversed relay path) gives, per candidate, the Pareto frontier of real planned execution routes. A delegation record's price and latency are a past job's, never this task's, so they never enter.
4. Normalizes additive accumulators (cost, latency, risk) to [0,1] via sigmoid mapping.
5. Applies a configurable composite function (default: weighted sum) to every planned execution route — evidence trust, that route's own execution metrics, that route's own custody boost — and keeps the winner.
6. Returns RouteScore[] whose sub_scores are the evidence trust and the chosen planned execution route's metrics.

Why the split: a relationship can vouch for an agent, but only hops the task takes can cost it money or time. Before this split (2026-09-14), hiring B directly with A's recorded delegation to B in the graph priced the hire with A's cost and latency added on.

Two rules keep the graph and the dispatcher in agreement. Only dispatchable hops enter execution ranking: a candidate discovered through a federation peer carries reachable_via, gets no direct edge, and its own metrics sit on the peer → agent leg. Dispatch consumes the selected route: the relay forwards to the peer the planned route names, never to one chosen independently. The route reported at selection time is the planned execution route; who actually took part is established afterwards by receipts.

Explained routing

explainedRankCandidates extends graphRankCandidates with both paths a decision rests on. routing_paths[0] is the planned execution route — the hops the task will take, whose composed execution metrics the score reports (["agent-xyz"] for a direct hire; ["relay-a", "agent-xyz"] for a federated one) — and the remaining entries are the non-dominated planned-route alternatives the policy weighed, best first. alternatives_considered is the size of that frontier. trust_evidence_path is the vouching chain, through every edge kind, that justified the trust value:

This flows end-to-end: the relay returns routing_choice on task submission, PlanEngine attaches it to the delegation step summary, and it is signed into the execution ledger manifest — an audit trail from semiring algebra to cryptographic proof. It is only worth signing because it is exact: the transcript names routes that exist and each route's own metrics, so a verifier can recompute them from the same edges. A component-wise summary would have signed a route that does not exist. Read each path for what it is: routing_paths[0] is the planned execution route (the hops the task takes — direct, or via the federation peer named on it), trust_evidence_path is the vouching chain (recorded delegation history, discovery, peers) behind the trust value. Neither is a claim about who did the work; that is proven by receipts.

Composite functions

The composite function is a policy choice that determines how semiring-computed values are combined for ranking. Two built-in options:

Custom composite functions can be passed via the RoutingPolicy:

const policy: RoutingPolicy = {
  composite: (route, scores) => {
    // Trust-or-nothing: if trust < 0.5, score is 0
    if (scores.trust < 0.5) return 0;
    return scores.trust * 0.5 + scores.costScore * 0.5;
  },
};

Adding a new routing concern

Adding a new routing dimension requires only a new semiring definition — zero new algorithms:

import type { Semiring } from "@motebit/protocol";

// Energy cost: accumulates along chains, pick the greenest route
const EnergySemiring: Semiring<number> = {
  zero: Infinity,
  one: 0,
  add: (a, b) => Math.min(a, b),
  mul: (a, b) => a + b,
};

Add the dimension to RouteWeight, add it to the record semiring, and the existing traversal algorithms handle the rest.