acceptodds
Under review as a conference paper at ICLR 2027

Optimality and Load Balance of Group-Limited Routing in Mixture-of-Experts

Abstract

Mixture-of-experts (MoE) language models activate only a few experts for each token, and large deployments place groups of experts on different devices. Group-limited routing bounds the number of groups per token, but not how much work each group receives. On single-domain batches of real text, the busiest group receives on average nearly twice its fair share; when groups work in parallel, it sets the pace for all of them, and a group with a buffer of fixed size must drop whatever does not fit. We give a novel analysis of group-limited routing that describes each route by how many experts it takes from each group. With this analysis, we determine exactly at which shapes the selection rule released with DeepSeek-V3-style models is score-optimal. We then prove what the existing rules cannot guarantee: with this rule, the routing score on some batches stays well below the best balanced score, whatever the group prices, and on bursty traffic every fixed bias either overloads a group or loses score. Prices set for each batch succeed there. When a linear programme sets one price per group and each token selects exactly its best route at these prices, the programme splits only a few tokens between routes. Rounding them jointly keeps every group within a fixed allowance of its target at any batch size, with a routing score at least that of the best routing that meets the target. On some batches, no routing reaches this score without an allowance. The resulting router, **HYPERSPACE**, needs no retraining and drops nothing. Our empirical results on 159,776 recorded batches of user conversations, including prefill batches of up to 16,384 tokens, show that **HYPERSPACE** meets both guarantees on every batch, whereas the baselines, group prices on the released rule and static replication, miss one of them on some batches. In every one of eight text domains on three MoE models, **HYPERSPACE** has a lower next-token loss than dropping the overflow. On GSM8K and HumanEval, its accuracy stays within four points of the model's own router; dropping loses 5.5 points on GSM8K.

Primary area:
optimization
Keywords:
mixture of experts, group-limited routing, load balancing, linear programming, column generation, large language model inference

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_AYSNOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies load balancing for group-limited MoE routing. It characterizes the optimality of the released DeepSeek's selection rule and develops HYPERSPACE, which is an LP-based router with a batch-size-independent load allowance and a routing-score guarantee. Experiments confirm tight load control without dropping assignments, but show quality losses and substantial routing overhead.

Critical strengths
  1. The theoretical contribution is important and interesting. The paper connects route patterns, group prices and balanced routing through an LP formulation. The optimality characterization, rounding guarantee and impossibility results clarify both the capabilities and limitations of group-limited routing.

  2. The load guarantees are supported empirically. HYPERSPACE stays within four assignments of the target across the evaluated batches, including recorded user-traffic replay. It requires no retraining and achieves lower NLL than group dropping in all tested model-domain pairs.

Critical weaknesses
  1. The practical benefit remains unproven. Tab 5 reports 26.9 ms per layer for a 64-token routing step, vs. 0.16ms for the released router, which is approx. 170× slower. This measurement excludes the placement flow. However, the LP runs on CPU, so the result establishes the cost of the current implementation rather than an inherent limitation of the method. The paper provides neither evidence of that improvement nor end-to-end expert-parallel measurements showing that better balance offsets routing overhead. I do believe that an optimized implementation could substantially improve the paper.

The evaluation also lacks LPLB, which the paper cites. LPLB uses per-batch LP optimization to redistribute assignments among replicas while preserving logical expert choices. Its replication requirements make it a different trade-off, but comparison under a stated memory budget would help establish when changing routes is preferable to redistributing work.

  1. The quality-balance trade-off needs stronger justification. HYPERSPACE improves load balance at a noticeable quality cost relative to the released router, and its advantage over group dropping is not consistent across downstream tasks (Tab 4, 6). Without end-to-end timing, it remains unclear whether these losses buy a worthwhile latency improvement. I believe that quality evaluation on mixed-domain traffic would strengthen the evidence beyond single-domain NLL batches.
Questions for authors
  1. Can an optimized GPU implementation deliver an latency/throughput improvement under expert parallelism, including placement and communication costs?

  2. How does routing time scale from decoding to large prefill batches?

  3. How does HYPERSPACE compare with LPLB at comparable replication-memory budgets?

Reviewer_HvveOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies group-limited routing in MoE language models: the experts are split into N groups and each token selects K experts from at most M groups. This bounds cross-device traffic but not how much work each group receives, and the authors show that on real batches the busiest group gets almost twice its fair share, which sets the pace for the whole layer. They reformulate routing in terms of how many experts a route takes from each group and per-group prices, and use this to prove several negative results about existing rules. They then propose HYPERSPACE, an inference-time router that solves a linear program over patterns per batch, rounds the few fractional tokens, and places experts by a network flow. Experiments on various models are further shown.

Critical strengths
  • The problem is real and clearly motivated: per-token group limits do nothing for per-group load, and the measured imbalance makes the case.
  • The method is training-free and comes with a provable per-batch load bound that holds at any batch size.
  • The theory appears thorough (I did not verify the proofs in detail) and is tied to the design.
Critical weaknesses
  • Computational cost is the main concern. A routing step takes 26.9 ms per layer on 64 tokens versus 0.16 ms for the released router, about 170 times slower. Over 19 layers that is roughly half a second per decoding step. The paper reports this in one table but never measures end-to-end time of the MoE layer or decoding step with and without HYPERSPACE, so there is no evidence that balancing load in assignments actually makes anything faster.
  • Section 4 is dense and hard to follow. Theorem 4.1 in particular is stated with constants (P, H, rho) whose meaning is not conveyed in words. Each result would benefit from a one-sentence plain-language statement of what it says and why it matters for the design, ideally with a small example.
  • Figure 1(b) is not self-explanatory. The coordinate system (number of experts from A, B, C), what the square/star/blue dot represent, and how the price moves the choice are unclear. The caption should walk the reader through it.
  • What routing score measures is never connected to quality. The score is the sum of the chosen experts' gate values, normalized per token, which is a proxy for agreement with the router rather than a likelihood or any downstream quantity. The paper optimizes and guarantees this score, but the results show that even the likelihood looks good, the accuracy drops a lot compared to the released router as shown in Table 4.
Questions for authors
  • Could you add a plain-language summary of each theorem (what it rules out and which design choice it motivates), and expand the Figure 1(b) caption?
  • What is the end-to-end wall-clock time of one MoE layer and one decoding step with HYPERSPACE versus the released router, including the placement flow? At what batch size or imbalance level does it break even?
  • How does the routing score relate to NLL or accuracy empirically?
Reviewer_bV2hOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies optimality and load balance in group-limited MoE routing. The authors show that the routing rule used by DeepSeek-V3-style models can miss a token's best legal route, and that adding group prices to this rule cannot always recover the best balanced score. They also show that limiting the number of groups per token does not prevent individual groups from becoming overloaded.

The proposed method, HYPERSPACE, solves a linear program for each batch and uses its group prices to select routes. A joint rounding step gives an integral routing with a score at least as high as the best exactly balanced routing, while allowing a bounded load deviation. The method requires no retraining and drops no expert assignments. Experiments on recorded traffic show small load deviations across batch sizes. It also gives lower NLL than overflow dropping, although quality decreases relative to the released router.

Critical strengths
  1. The analysis of the deployed routing rule is valuable. It identifies when the rule is optimal and shows why group prices alone cannot always fix it.
  2. The batch-size-independent load bound is useful. HYPERSPACE avoids dropping assignments and gives better NLL than overflow dropping in the tested settings.
Critical weaknesses
  1. I am not convinced that the improved balance gives a practical speed benefit. Table 5 reports 26.9 ms per routing step at 64 tokens, excluding the placement flow, compared with a separately measured 0.16 ms for the released router. There is no end-to-end timing to show whether the saved expert computation offsets this cost. Timing at larger prefill batches would be especially useful.
  2. The practical advantage over tuned group prices is also unclear. With 200 iterates, group prices stay within the allowance on all decoding batches and achieve nearly the same routing score as HYPERSPACE (Table 2). They fail on some prefill batches, so the guarantee matters, but their NLL and runtime are not reported. I therefore cannot tell how much HYPERSPACE improves the quality-cost trade-off over this baseline.
Questions for authors
  1. Can you report end-to-end latency for HYPERSPACE and the released router on decoding and prefill batches? At what batch sizes does the improved balance offset the routing cost?
  2. How does HYPERSPACE compare with 200-iterate group prices in NLL and runtime under the same setup? This would help clarify when the proposed method is preferable in practice.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.