# Tree-Hall Collision-Free Router

- ID: 2073
- Canonical URL: https://synthcore.org/idea/2073/tree-hall-collision-free-router
- API JSON: https://synthcore.org/api/idea/2073.json
- API Markdown: https://synthcore.org/api/idea/2073.md
- Verification status: unverified
- Source: [arXiv:2608.10193](https://arxiv.org/abs/2608.10193)
- Category: architecture
- Solves: scalability, stability, accuracy
- ML areas: moe-routing, attention, graph-nn
- Math tags: combinatorics, graph-theory, optimization
- Ratings: usefulness 6/10; difficulty 7/10; novelty 7/10

## Idea description

Replace independent top-k routing by a tree-structured hypergraph assignment layer. Each candidate route is a singleton or pair of resources, and the router selects exactly q_e routes for every tree edge e while ensuring that no resource is consumed twice. This removes capacity collisions before expert computation instead of repairing them with token dropping or load-balancing penalties.

## Mathematical statement

Let T be a finite tree, U a finite resource set, and Q_x a support subtree of T for every resource x in U. The bag at tree vertex t is P_t = {x in U : t is in V(Q_x)}. For each edge e = tu, the candidate hypergraph A_e contains singleton loops {x} for x in P_t intersection P_u and pair hyperedges {x,y} with x in P_t and y in P_u. A q-SDR chooses q_e = q(e) candidates from each A_e such that selected hyperedges are pairwise vertex-disjoint. The direct engineering formulation uses binary variables x_(e,h), one for each candidate h in A_e, with exactly q_e choices per edge and at most one selected candidate incident to every resource r. The paper's feasibility machinery is based on matroid union and Rado-Perfect rank formulas. For matroids J_1 through J_m on E, the union rank is the minimum over W contained in X of |X minus W| plus the sum of r_Ji(W). For a bipartite graph K with left side L, right side R, and matroid M on R, the matchable-set matroid has rank equal to the minimum over A contained in H of |H minus A| plus r_M(N_K(A)). In the router, resources are tokens, experts, communication slots, or paired-operation operands; the tree-Hall theorem supplies the structural reason that feasibility can be certified and constructed for this restricted candidate family.

## Key formulas

- P_t = { x in U : t belongs to V(Q_x) }.
- E(A(F)) = union over e in F of E(A_e), and q(F) = sum over e in F of q_e.
- r_union(X) = min over W contained in X of (|X minus W| + sum over i of r_Ji(W)).
- sum over h in E(A_e) of x_(e,h) = q_e for every e; sum over e and h containing r of x_(e,h) is at most 1 for every r in U; x_(e,h) is binary.

## Implementation notes

Integrate the method in the MoE router after computing token-to-expert logits and before dispatch. Build a fixed balanced tree T whose leaves are experts or expert groups. For each token x, define a support subtree Q_x containing the groups permitted by its mask, locality rule, or learned candidate generator. For every tree edge e, construct A_e from feasible singleton routes {x} and, optionally, pair routes {x,y} that jointly consume two resources such as a token plus a communication slot. Set q_e to the desired number of assignments on edge e. Convert router logits into candidate costs c(e,h) = minus logit(e,h). Solve the binary optimization problem with objective minimize the sum of c(e,h)x(e,h), subject to exactly q_e choices on each edge and at most one selected candidate incident to each resource. For a first MVP, use a min-cost ILP or branch-and-bound solver on small batches; then replace it with a tree dynamic program or min-cost flow for the singleton-only case. Compute candidate neighborhoods and resource incidence exactly from Q_x; no mathematical constants need estimation. If a batch is infeasible, reduce q_e, enlarge supports, or select the highest-scoring feasible subset instead of arbitrary overflow dropping. Test on a 125M-parameter Transformer with WikiText-103 and a synthetic tree-local routing task, comparing against Switch top-1 and top-2 routing at equal FLOPs. Record dropped-token rate, expert-load variance, routing overhead, throughput, and perplexity. Success means near-zero collision drops, lower load variance, and equal or better perplexity without excessive routing latency.

## Disclaimer

AI-generated research hypothesis, automatically tested. Not peer-reviewed.