# Polyhedral Column-Generation MoE Router

- ID: 2971
- Canonical URL: https://synthcore.org/idea/2971/polyhedral-column-generation-moe-router
- API JSON: https://synthcore.org/api/idea/2971.json
- API Markdown: https://synthcore.org/api/idea/2971.md
- Verification status: unverified
- Source: [arXiv:2609.00439](https://arxiv.org/abs/2609.00439)
- Category: architecture
- Solves: speedup, stability, memory
- ML areas: moe-routing, transformer, training, inference-speedup
- Math tags: optimization, convex-analysis, linear-algebra, combinatorics
- Ratings: usefulness 6/10; difficulty 6/10; novelty 7/10

## Idea description

Replace unconstrained token-to-expert routing with a nonnegative mixture of a small set of feasible routing or communication patterns. Enforce resource limits using the paper's one-sided positive-contribution bound, which gives a conservative certificate without enumerating all joint token activation scenarios. Expand the pattern set only when a separation procedure finds a routing pattern that improves the router objective while adding useful capacity information.

## Mathematical statement

Theorem 1 uses exchange-pattern columns p_i and nonnegative coefficients f_i to represent a net-injection vector as nr = sum_i p_i f_i, with f_i >= 0. For each network constraint k, the paper defines a secure per-pattern capacity W_k^i and imposes sum_i W_k^i f_i <= F_k^max. In the power-flow specialization, W_k^(n,z) = max(PTDF_(k,n) - PTDF_(k,z), 0) for the exchange e_n - e_z. The crucial one-sided inequality is sum_z PTDF_(k,z) nrAct_(z,s) <= sum_i W_k^i f_i <= F_k^max, which certifies every activation scenario represented by the same nonnegative pattern coefficients. Adapt this to a router as follows: p_i in R^E is a routing or traffic pattern over E experts, f_i >= 0 is its batch-level usage coefficient, r in R^E is the resulting expert-load vector, a_k in R^E is the measured resource-incidence vector for constraint k, b_k is its capacity, and W_k^i = max(0, a_k^T p_i). The conservative feasible router is r = sum_i p_i f_i with sum_i W_k^i f_i <= b_k. The max prevents unsafe cancellation between individually costly patterns, while the active column pool avoids enumerating all joint routing configurations.

## Key formulas

- $$nr=\sum_{i=1}^{T}p_i f_i,\qquad f_i\geq 0$$
- $$\sum_{i\in T}W_k^i f_i\leq \widetilde{F_k^{max}},\qquad \forall k\in CNE$$
- $$W_k^{n,z}:=\max\left(PTDF_{k,n}-PTDF_{k,z},0\right)$$
- $$r=\sum_{i=1}^{T}p_i f_i,\qquad \sum_{i=1}^{T}\max\left(0,a_k^{\top}p_i\right)f_i\leq b_k\quad\forall k$$

## Implementation notes

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.

## Disclaimer

AI-generated research hypothesis, automatically tested. Not peer-reviewed.