Takagi-Regularized Hierarchical Routing
Implementation & benchmark of arXiv:2607.11069 — Sharp Ternary Martingale Isoperimetry and $n$-adic Takagi-Type Lower Bounds
Source paper: Sharp Ternary Martingale Isoperimetry and $n$-adic Takagi-Type Lower Bounds arXiv:2607.11069 ⓘ · analyzed Aug 30, 2026
AI-generated research hypothesis, automatically tested. Not peer-reviewed.
Idea description
Represent MoE experts as leaves of a balanced ternary tree and regularize the hierarchical boundary of each expert's assignment mask. At fixed routing mass x, the ternary martingale isoperimetric theorem supplies the explicit minimum one-variation T_3(x), so the router can be penalized according to an occupancy-dependent profile rather than a uniform parent-child disagreement cost. This should favor coherent, stable routing regions while preventing small expert supports from obtaining artificially cheap fragmented assignments.
Formulas
Mathematical statement
For a measurable set A of measure x in the ternary filtration, the paper identifies the exact minimum V_3(x) of the L1 norm of the martingale one-variation S_1(1_A): V_3(x)=T_3(x). Here x=|A|, {u}=u-floor(u) is the fractional part, and T_3 is defined by T_3(x)=sum_{j=0}^infinity 3^{-j} psi_3({3^j x}). The digit-scale penalty is psi_3(t)=min{(1+2|t-1/2|)/3,(2-4|t-1/2|)/3} for 0<=t<=1. For every n>=2, the general lower bound is ||S_1(1_A)||_1 >= omega_n(|A|*) and omega_n(|A|*) is comparable, up to constants depending only on n, to |A|* log(1/|A|*), where |A|*=min(|A|,1-|A|). In a finite depth-D ternary tree, let m_v(a) be the empirical mean assignment probability for expert a in node v, p(v) its parent, and w_v the fraction of leaves below v. The computable hierarchical variation is B(a)=sum_{v != root} w_v |m_v(a)-m_{p(v)}(a)|. Let x_a be the global routing mass of expert a. Use the truncated profile T_3^(D)(x)=sum_{j=0}^{D-1}3^{-j} psi_3({3^j x}) as the occupancy-dependent reference.
Implementation notes
Integrate the method into the auxiliary loss of a hierarchical ternary MoE router, not into the expert MLPs. (1) Build a balanced depth-D ternary tree whose leaves are experts. For each token t, let q_t(a) be the router's soft assignment to expert a. For every internal node v, aggregate q_t(a) over the leaves below v and compute m_v(a) as the minibatch mean of that quantity; use the root mean x_a as the global occupancy of expert a. (2) Compute B(a)=sum over non-root nodes v of w_v*abs(m_v(a)-m_parent(v)(a)), where w_v is the leaf fraction below v. Evaluate psi3 from the displayed piecewise-minimum formula for j=0,...,D-1 and form T3^(D)(x_a). Add lambda*R to the task loss, with R=sum_a(B(a)-T3^(D)(x_a))^2. For a safer first implementation, use the one-sided penalty R=sum_a max(0,T3^(D)(x_a)-B(a))^2, because the theorem is a lower bound; stop-gradient through x_a during a short warmup, then enable gradients. (3) The exact mathematical computation is psi3 and the truncated profile; minibatch node means are empirical estimates and should be stabilized with exponential moving averages. (4) First test a 3-level, 27-expert Switch-style Transformer on WikiText-103 or a clustered synthetic classification problem. Compare against standard load-balancing and plain parent-child smoothness losses. Log validation perplexity or accuracy, expert-load coefficient of variation, routing changes between adjacent batches, B(a), dropped-token rate, and communication. A positive result is lower routing churn and communication at matched perplexity, or better perplexity at matched load balance and compute. Ablate lambda, depth, squared versus hinge penalty, and EMA versus raw batch statistics.
Verification
This idea has not been verified yet.
Verification happens in two stages: Stage 1 — a mechanism check on a toy system confirms the claimed mathematical phenomenon reproduces; Stage 2 — a benchmark implements the idea on a real (small) neural network task and compares it against a tuned baseline over 8 paired seeds with a permutation test.
Artifacts
Artifacts unavailable.