Tree-Structured Exact Expert Router

Integrate this at the MoE router, before dispatching tokens to experts. Use one routing problem per token group or microbatch, with n experts and binary z_i indicating whether expert i may receive traffic. Build a symmetric interaction matrix Q from a calibration set: Q_ij can be an empirical covariance or cosine-similarity penalty between expert outputs, augmented with diagonal dispatch costs. Factor Q approximately as F F^T, or use a low-rank factor F directly. Let d_i be the negative router logit for expert i, c_i be the fixed activation or communication cost, and x_i be a nonnegative routing weight. Add sum_i x_i = 1, 0 <= x_i <= U_i z_i, and at most k active experts. Choose an expert ordering for which supp(Q) is a tree or has small separators. Enumerate partial binary assignments in this order. For every partial assignment v, compute its separator S_1^ell(v) and state H^ell(v) using H^ell(v) = F_[ell:n] - Q_[ell:n],S Q_S,S^(-1) F_S; hash states with identical separators and tolerance-rounded H matrices, and retain only the lowest-cost representative. For every retained state, solve the small local convex quadratic problem over newly activated experts, then propagate its cost. Backtrack the best terminal state to obtain z and x, and dispatch only to experts with z_i = 1. The separator rule and quadratic state update come from the paper; Q estimation, state tolerances, and ordering are empirical. First test on an 8-expert Switch-Transformer-style model using CIFAR-100 or WikiText-2, comparing against top-2 routing at equal active experts. Measure router wall time, expert FLOPs, load imbalance, validation loss, and unique state count. Success requires lower redundancy or communication and equal-or-better accuracy without router overhead dominating dispatch savings.