Summary (Overview)

• Core contribution: TEMPO introduces a makespan-aware expert-parallel (EP) load balancer for Mixture-of-Experts (MoE) serving, replacing token-count or activation-count proxies with a calibrated two-regime time model of expert computation.
• Key finding: Real hardware measurements show expert cost is neither linear in tokens nor in expert count—it's flat below ~156-168 tokens per expert (weight streaming dominates) and linear above (compute dominates), with a tile-staircase mechanism underlying both.
• Main result: On real batches, the dispatches produced by existing proxy policies differ by 1.4-1.6× in modeled block time (p95 up to 1.7×), and the best policy flips with the operating regime—no fixed proxy wins everywhere.
• Algorithm: A millisecond-scale solver combining cost-aware seeding, augmenting-chain activation rebalancing, bottleneck local search with partial migrations, and an ensemble with switching tolerance; achieves within 1.02% of a 10-second MILP at ~2 ms.
• Deployment: SGLang integration with zero in-graph kernels and collectives; end-to-end results show 4-6% throughput gains on Qwen3-235B (inside win region), ~15.6% p99 latency reduction, while DeepSeek-V3 (outside win region) shows no gain—a falsifiable phase diagram predicts both outcomes.

Introduction and Theoretical Foundation

The EP Synchronization Problem

In expert-parallel (EP) Mixture-of-Experts serving, each MoE layer ends at a synchronization point: the time a batch spends in the MoE block equals the time of the slowest GPU. Production dispatchers balance proxies—token counts (EPLB, LPLB, UltraEP) or activated-expert counts (METRO)—implicitly assuming expert time is linear in one of these two quantities.

The Measured Cost Model

Measurements on two generations of datacenter GPUs show the cost is two-regime:

$$t_g = \max\left(a + bG_g, c + \beta N_g\right)$$

where:

• $G_g$ = number of activated (expert, replica) pairs on GPU $g$
• $N_g$ = token count on GPU $g$
• $b$ = activation floor (cost of streaming one more replica's weights from HBM): 1.74 µs (Qwen3-30B) to 14.8 µs (DeepSeek-V3)—an 8.5× spread
• $\beta$ = per-token compute cost in the linear regime

Key hardware mechanisms:

1. Weight streaming floor: Below ≈156-168 tokens per expert, cost attaches to activated replicas, not tokens—the expert's weights must be streamed from HBM regardless of token count.
2. M-tile padding: Grouped GEMM rounds tokens to 128-token M-tiles, so splitting an expert across $k$ replicas rounds up $k$ times—fragmenting experts manufactures padded compute.

The tile-aware extension:

$$t = \max\{|a + bG + b_2(T-G), c + \beta N\}, \quad T = \sum_e \lceil n_e/128\rceil$$

Mixed Regimes Are the Common Case

92-100% of real decode batches contain both regimes simultaneously: hot experts sit deep in the linear region carrying ~91% of tokens, while roughly half of activated experts remain in the flat region. This is the pivotal empirical fact that makes proxy-based balancing systematically wrong.

Methodology

Problem Formulation: Fixed-Charge Makespan Dispatch

Given per-expert token counts $n_e$, replica sets $R(e)$, token shares $x_{e,g} \geq 0$ (supported on $R(e)$), and activation indicators $z_{e,g} = \mathbf{1}[x_{e,g} > 0]$:

$$\min \max_g \max\left(a + b\sum_e z_{e,g}, c + \beta\sum_e x_{e,g}\right)$$

Theorem 1 (NP-hardness): Deciding whether a dispatch with makespan ≤ T exists is NP-complete, already with 2 GPUs, full replication, and $a=c=0$. Reduction from Balanced PARTITION.

Degenerate cases are polynomial:

• $b \to 0$: reduces to min-max token LP (LPLB/UltraEP objective)
• $\beta \to 0$: reduces to optimal semi-matching (polynomial via augmenting paths)

Theorem 2 (Additive approximation): Under full replication, a descending-token round-robin placement $A_3$ achieves $M(A_3) \leq \text{OPT} + \max(b, \beta n_{\max})$.

The Phase Diagram

Sweeping synthetic Zipf(s) routing over batch size $B \in [16, 2048]$ per GPU, skew $s \in [0, 1.5]$, replication {1.25, 1.5}×, EP {8..64}:

• Best fixed policy flips across the map: activation balancing wins at small B (memory-bound), token-LP at large B (compute-bound)
• The flip boundary is analytically predictable: $B^* = \min(B^*_{\text{avg}}, B^*_{\text{hot}})$ where $B^*_{\text{avg}} = n^* E_{\text{eff}}/(K n_{\text{gpus}})$ and $B^*_{\text{hot}} = n^* E_{\text{eff}}/(p_1 K n_{\text{gpus}}^2)$

The tempo fast Solver

Four stages, each targeting a failure mode:

1. Cost-aware greedy seeding: Experts placed whole on replica with lowest marginal cost—fragmenting cold experts is the token-LP mistake
2. Activation rebalancing via augmenting chains: 1- and 2-step chains (truncated semi-matching augmenting paths)
3. Bottleneck local search with partial migrations: Ternary-search partial splits in the linear regime
4. Ensemble with switching tolerance: Score token-LP and round-robin certificates under the model; switch only if >1% better

Calibration Method

Black-box calibration on the deployed pipeline: run a (G,N) grid, log per-GPU (G,N,t), fit the two-piece max-affine by alternating assignment. About ten minutes per (kernel, dtype, hardware) combination.

Empirical Validation / Results

Phase Diagram and Scale (Calibrated Simulation)

• TEMPO tracks the per-cell best everywhere (min gain ≥ -0.3%, inside the 1% ensemble band)
• Wins by up to 8.5% (DSv3) / 10.2% (Qwen3) / 11.8% (DSv2, 1.5× replication) in the mixed zone
• At EP 8→64: mean 6-6.5% at s=0 on EP32-64 (max 15.5%), collapsing to 0 exactly where theory predicts

Wall-Clock Microbenchmark (8-GPU Testbed A, EP8)

• At B=32 (memory-bound): TEMPO beats EPLB-even by 11-14% and token-LP by 7%
• At B=2048 (compute-bound): METRO is 7-11% off best; TEMPO ties token-LP at top
• TEMPO within 5% of per-B best fixed policy across all B; every fixed policy has a ≥7% failure region

End-to-End Serving Results (Testbed B)

Qwen3-235B (inside win region):

• GovReport (long-prefill): +5.0% median throughput (non-overlapping ranges)
• Under Poisson load: p99 TPOT −15.6% (191 vs 226 ms), median TTFT −12.5%
• ShareGPT: parity (−0.2% throughput, −8.9% p99)

DeepSeek-V3 (outside win region):

• Every workload lands at −2 to −3%, indistinguishable from noop control
• The pair of models brackets the phase diagram's win region

Multi-Node EP16 (Testbed B)

• With fresh placement: static, TEMPO, and noop tie within noise (zero-tax result)
• Under drift-16: flat table loses −3.5% at 1024 requests; topology-aware split recovers +4.1%
• Qwen3-235B EP16: TEMPO +4.1% decode-heavy, +7.2% with topology-aware split; SGLang dynamic rebalancer negative throughout

Table 1: Modeled Block Time of Proxy Dispatches vs. TEMPO

Table 4: Policy Landscape (Block Makespan Relative to Static)

Table 5: Four-Way Attribution on Qwen3-235B 2-Node EP16

Table 3: $B_{\text{a2a}}^*$ Prediction vs. Measurement

Component Ablation (Table 2)

Theoretical and Practical Implications

Theoretical Contributions

• Formal hardness framework: The fixed-charge makespan problem is PN-complete even at 2 GPUs with full replication, yet polynomial in each degenerate limit—the hardness lives in the regime interaction, mirroring the systems observation that each proxy works at home and fails in the transition zone
• Additive approximation guarantee: Round-robin whole-expert placement achieves OPT + max(b, βn_max) under full replication, with a certificate that the deployed solver inherits
• Analytically predictable phase boundary: The flip between activation-balancing and token-LP winners follows a closed-form prediction matching observed behavior in 12/12 grid columns

Practical Implications

• Deployment-ready: Solver runs out-of-process in milliseconds; zero kernels and zero collectives on the critical path
• Win region is conditional and mapped: Adaptive dispatch pays only within a batch-size band (B=64-256 at EP8) bracketing $B_{\text{a2a}}^* \approx 300$, with placement staleness, tight replica budgets, and sufficient expert compute share
• Architecture matters as much as objective: Like-for-like port of token-LP shows most of the gap between TEMPO and SGLang's shipped dispatcher is due to integration architecture, not the objective
• Complementary to placement: Dispatch repairs the latency tail; only placement repairs the mean—the two layers partition the problem

Conclusion

TEMPO's core claim is "balance time, not tokens." A ten-minute black-box calibration reveals the two-regime structure of expert cost; a phase diagram shows every fixed proxy has a failure region while the regimes coexist inside single batches 92-100% of the time; and a makespan solver over the calibrated model tracks the per-regime best everywhere at millisecond cost.

The win region requires three coordinates: moderate experts-per-GPU, sufficient skew, and expert compute a large enough share of the step. The measured results bracket the predicted region: Qwen3-235B (inside) gains 4-6% throughput and cuts p99 latency by ~15.6%; DeepSeek-V3 (outside) returns only mechanism cost.

The paper carefully disclaims limitations: headline numbers are model-space (L1), testbeds are limited to 8-16 GPUs (L2), the win region is conditional and mapped (L3), calibration is static (L4), the (G,N) model has a floor (L5), and the deployed system is not the theoretical optimum by design (L6). The durable contribution is the map itself—as MoE serving consolidates around fp8 grouped kernels, large-expert flagships, and multi-node expert parallelism, dispatching on measured time rather than counted tokens is both principled and profitable.