Balanced KL projection for MoE routing
Implementation & benchmark of arXiv:2608.08642 — Exact Rank-Space KL Projection for Shared-Marginal Low-Rank Factors: Application to Doubly Stochastic Clustering
Source paper: Exact Rank-Space KL Projection for Shared-Marginal Low-Rank Factors: Application to Doubly Stochastic Clustering arXiv:2608.08642 ⓘ · analyzed Sep 1, 2026
AI-generated research hypothesis, automatically tested. Not peer-reviewed.
Idea description
Use the shared-marginal KL projection to turn token-to-expert routing into a low-rank, exactly balanced assignment rather than relying only on an auxiliary load-balancing penalty. Tokens retain normalized routing distributions while the shared latent marginal enforces consistent aggregate usage across two independently learned routing factors.
Formulas
Mathematical statement
Let n tokens be assigned through nonnegative U,V in R^(n x r), with each row summing to one and with a common latent mass g=U^T 1_n=V^T 1_n. The construction W=U Diag(g)^(-1) V^T produces a nonnegative assignment kernel whose row and column sums are one. In a router, U can encode token-to-latent-group probabilities and V can encode expert-to-latent-group probabilities; the induced token-expert interaction need not be materialized. The exact KL projection uses generalized KL divergence, preserving positivity and producing multiplicative primal updates. Its dual Hessian is a sum of categorical covariance matrices C(p)=Diag(p)-p p^T, enabling matrix-free Newton steps in O(nr) time. The all-ones dual direction is redundant, so fixing one coordinate or imposing sum-zero gauge leaves r-1 variables.
Implementation notes
Insert the method into a sparse MoE router immediately after router-logit computation and before top-k dispatch. For a batch of n tokens, produce factor logits A and B with shape n by r, then compute U0=softmax(A) and V0=softmax(B). Interpret U as token-to-latent routing and V as expert-to-latent routing, using a rectangular variant if the number of experts differs from r. Perform a KL projection toward the current factors subject to row-simplex and shared-marginal constraints. Use a damped Newton loop on the first r-1 dual coordinates: initialize dual variables at zero, compute normalized rows p_i and q_j by exponentiating and normalizing, evaluate marginal residuals, compute each Hessian-vector product with C(p)s=p elementwise-multiplied by (s-p dot s), solve the Newton system with 3 to 10 conjugate-gradient iterations, and backtrack until the KL objective decreases and all constraint residuals are below 1e-6. Use the projected factors to derive dispatch probabilities or top-k indices, and use straight-through gradients through the projection initially. The exact mathematics supplies positivity and marginal feasibility; choose capacity clipping, projection tolerance, and gradient treatment empirically. First benchmark an 8-expert Switch-Transformer-style model on a small language-model corpus, comparing standard auxiliary load loss, Sinkhorn balancing, and this projection at equal router FLOPs. Track expert-load coefficient of variation, dropped-token rate, validation perplexity, router gradient variance, and projection overhead. Success means lower dropped-token rate and expert imbalance without an auxiliary balancing loss, stable training, and less than 10 percent router-time overhead.
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.