Tree-Hall Collision-Free Router

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.