# TEMPO: Makespan-Aware Expert-Parallel Load Balancing Across Memory- and Compute-Bound Regimes

arXiv: https://arxiv.org/abs/2608.13057 · HTML: https://mlsanity.com/paper/2608.13057/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Efficient MoE training and inference systems, one of 12 directions in Mixture-of-experts.
- Builds on 12 of its 22 references that are in the map.
- First posted on arXiv 13 Aug 2026.

## Placed in

- Mixture-of-experts / [Efficient MoE training and inference systems](https://mlsanity.com/moe/efficient-moe-training-and-inference-systems/)

## Builds on (most cited first, 12 of 12)

- [Outrageously Large Neural Networks: The Sparsely-Gated Mixture-of-Experts Layer](https://mlsanity.com/paper/1701.06538/) (2017)
- [Switch Transformers: Scaling to Trillion Parameter Models with Simple and Efficient Sparsity](https://mlsanity.com/paper/2101.03961/) (2021)
- [GShard: Scaling Giant Models with Conditional Computation and Automatic Sharding](https://mlsanity.com/paper/2006.16668/) (2020)
- [FlexMoE: Scaling Large-scale Sparse Pre-trained Model Training via Dynamic Device Placement](https://mlsanity.com/paper/2304.03946/) (2023)
- [Taming Latency-Memory Trade-Off in MoE-Based LLM Serving via Fine-Grained Expert Offloading](https://mlsanity.com/paper/2502.05370/) (2025)
- [Least-Loaded Expert Parallelism: Load Balancing An Imbalanced Mixture-of-Experts](https://mlsanity.com/paper/2601.17111/) (2026)
- [UltraEP: Unleash MoE Training and Inference on Rack-Scale Nodes with Near-Optimal Load Balancing](https://mlsanity.com/paper/2606.04101/) (2026)
- [Efficient MoE Serving in the Memory-Bound Regime: Balance Activated Experts, Not Tokens](https://mlsanity.com/paper/2512.09277/) (2025)
- [Mixture-of-Experts Serving](https://mlsanity.com/paper/2607.17880/) (2026)
- [ViBE: Co-Optimizing Workload Skew and Hardware Variability for MoE Serving](https://mlsanity.com/paper/2606.00735/) (2026)
- [Beyond Uniform Experts: Cost-Aware Expert Execution for Efficient Multi-Device MoE Inference](https://mlsanity.com/paper/2606.29982/) (2026)
- [TAOT: Topology-Aware Optimal Transport for Dynamic Expert Replica Placement in MoE Training](https://mlsanity.com/paper/2608.03676/) (2026)

## Abstract (arXiv)

In expert-parallel (EP) MoE serving, every layer synchronizes at the slowest GPU. Dispatchers balance token counts (EPLB, LPLB, UltraEP) or activated-expert counts (METRO), assuming expert time is linear in one. Measurements on two datacenter GPU generations show it is neither: below n^* ≈ 156--168 tokens, HBM weight streaming dominates---cost attaches to activated replicas, not tokens; above it, grouped GEMM rounds tokens to 128-tile M-tiles, so splitting an expert adds padded compute. A max-affine profile t=max(a+bG,,c+β N) captures both regimes. Realistic decode batches hold hot experts in the linear regime and cold in the flat simultaneously; recorded batches show proxy dispatches differ by 1.4--1.6× in modeled block time (p95 up to 1.7×), and which proxy wins flips with the regime. We formalize per-batch dispatch as a fixed-charge makespan problem---NP-hard on two fully replicated GPUs, polynomial in degenerate limits---and present TEMPO, a makespan-aware dispatcher solving it in milliseconds off the critical path; its SGLang integration runs out-of-process and fuses dispatch with count collection into one in-graph kernel. Anchored by an 8-GPU Testbed A microbenchmark, TEMPO stays within 1% of the best fixed baseline everywhere and wins by up to 15.5% where regimes mix. End-to-end on Testbed B, Qwen3-235B (inside the win region) gains 4--6% throughput and cuts p99 latency by ~ 15.6%; DeepSeek-V3 (outside, communication-dominated) shows only mechanism cost. A phase diagram, not a universal win, is the claim: it predicts both outcomes before deployment.