Polyhedral Column-Generation MoE Router

Integrate the method at the router output of a sparse MoE Transformer, before dispatching tokens to experts. Let E be the number of experts and let K index resource constraints such as per-device capacity, all-to-all bandwidth, memory, or latency. Maintain a pattern matrix P = [p_1,...,p_T], where each p_i is a normalized expert-load or signed traffic pattern, and nonnegative coefficients f. For each batch, compute router logits g(x), aggregate the desired load vector r_target, and solve a small constrained projection: minimize ||P f - r_target||_2^2 + tau ||f||_2^2 subject to f >= 0 and sum_i W_ki f_i <= b_k for every k. Here W_ki = max(0, a_k^T p_i). Convert the projected vector r = P f into top-1 or top-2 dispatch probabilities. A simple implementation can use 10 to 30 projected-gradient iterations or a differentiable QP layer. Every 100 to 500 training steps, perform column generation: sample candidate patterns by perturbing overloaded expert assignments, compute each candidate's reduced-cost proxy using the current router residual and capacity slack, and append the best nonduplicate pattern. Estimate a_k from recent token counts, transmitted bytes, or measured communication time; b_k is the hardware budget. The mathematical part is the one-sided W bound; resource estimates and pattern generation are empirical. First test on an 8-expert, 12-layer MoE language model with WikiText-103 or C4, comparing against Switch top-1 and top-2 routing at equal model size and FLOPs. Track perplexity, dropped-token rate, peak memory, communication volume, and per-step latency. Success means at least 50 percent fewer dropped tokens and lower communication variance with no more than 5 percent perplexity degradation, or equal perplexity with lower peak memory and stable constraint satisfaction.