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

• URL: http://arxiv.org/abs/2608.13057v2
• Date: Fri, 14 Aug 2026 07:00:29 GMT
• Title: TEMPO: Makespan-Aware Expert-Parallel Load Balancing Across Memory- and Compute-Bound Regimes
• Abstract summary: TEMPO is a makespan-aware dispatcher solving per-batch dispatch in milliseconds off the critical path.<n>Its SG integration runs out-of-process and fuses dispatch with count into one in-graph kernel.<n>End-to-end on Testbed B, Qwen3-235B (inside the win region) gains $4$--$6%$ throughput and cuts p99 latency by $sim 15.6%$; DeepSeek-V3 shows only mechanism cost.
• Score: 6.460910545652521
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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^* \approx 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\times$ in modeled block time (p95 up to $1.7\times$), 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 $\sim 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.

Related papers

• Fast LapSum: Exact Differentiable Top-k at Million Scale [10.106073328854459]
  Fast LapSum is an exact-budget soft top-$k$ primitive whose GPU solver runs in linear time after sorting.<n>We demonstrate Fast LapSum on two demanding applications operating over millions of coordinates inside the training loop.
  arXiv  Detail & Related papers  (2026-08-07T07:44:35Z)
• Concurrent Image Understanding and Generation: Self-Correcting Coupled Markov Jump Processes [70.61868608402723]
  We introduce $textbfSelf-Correcting Coupled Markov Jump Processes (SC-CMJP)<n>In conjunction with SC-CMJP, we introduce $textttCO_texttt2textttJump$, a novel training-free single-pass sampler for joint multimodal geneneration.<n>For training and evaluation purposes, we have created and will release three large-scale joint multimodal generation corpora.
  arXiv  Detail & Related papers  (2026-07-14T18:39:29Z)
• \chisao{}: A GPU-Native Parallel Optimizer for Multimodal Black-Box Functions via Convergence-Anticonvergence Oscillation [0.0]
  chisao runs an entire sample batch simultaneously and exploits a deliberate convergence-anticonvergence cycle.<n>chisao achieves textbf100% mode recovery where all CPU baselines collapse at $d geq 8$ on the hardest multimodal functions.<n>The algorithm is available as a standalone open-source Python package on PyPI.
  arXiv  Detail & Related papers  (2026-06-24T06:33:29Z)
• Scaling Neural Network Verification with Tensor Parallelism and Fully Sharded Data Parallelism [0.0]
  Formal neural network verification is bounded in practice by GPU memory.<n>We adapt two techniques originally developed for large-scale model training to the auto_LiRPA / $,$-CROWN verification framework.<n>Fully Sharded Data Parallelism (FSDP) shards only weight matrices with a per-layer AllGather, producing bounds that are bitwise identical to the single- GPU baseline.
  arXiv  Detail & Related papers  (2026-06-08T11:56:29Z)
• Online Packet Scheduling with Deadlines and Learning [30.323408304797365]
  Network routers that enforce Quality-of-Service (QoS) guarantees must decide, at every clock cycle, which expiring packet of information to transmit.<n>We frame this problem as the Online Packet Scheduling with Deadlines (OPSD) problem under Partial Feedback.<n>We provide algorithms with provable $$-regret guarantees under different spans of slackness.
  arXiv  Detail & Related papers  (2026-05-30T18:20:33Z)
• Deterministic Realization of Classical Dissipation on Quantum Computers [0.0]
  Lattice Boltzmann (LB) on quantum devices must reconcile unitary gate evolution with the dissipative emph collide step.<n>In the multiple-relaxation-time (MRT) class, we work in the common setting of emphmodewise diagonal moment relaxation, $m_r'=_r,m_r$ with $_rin[-1,1]$.<n>The main result is the dissipative MRT block; construction of the equilibrium moment vector$mmathrmeq=Mfmathrm
  arXiv  Detail & Related papers  (2026-04-28T09:36:40Z)
• ELSA: Exact Linear-Scan Attention for Fast and Memory-Light Vision Transformers [11.576817774473398]
  Existing attention accelerators often trade exact softmax semantics, depend on fused Core kernels, or incur sequential depth that limits FP32 throughput on long sequences.<n>We present bfELSA, an algorithmic reformulation of online softmax attention that reserves exact softmax semantics in real arithmetic with a emphprovable $mathcalO(ulog n)$ FP32 relative error bound.<n>Unlike FlashAttention-2/3, which rely on HMMA/GMMA Core instructions and provide no FP32 path, ELSA operates identically on A100s and resource-
  arXiv  Detail & Related papers  (2026-04-26T16:41:30Z)
• Copy-as-Decode: Grammar-Constrained Parallel Prefill for LLM Editing [2.6382975801439836]
  LLMs edit text and code by autoregressively regenerating the full output, even when most tokens appear verbatim in the input.<n>We study Copy-as-Decode, a decoding-layer mechanism that recasts edit generation as structured decoding over a two-primitive grammar.
  arXiv  Detail & Related papers  (2026-04-20T12:29:53Z)
• TwinFormer: A Dual-Level Transformer for Long-Sequence Time-Series Forecasting [0.0]
  TwinFormer is a hierarchical Transformer for long-sequence time-series forecasting.<n>It divides the input into non-overlapping temporal patches and processes them in two stages.<n>A lightweight GRU aggregates the globally contextualized patch tokens for direct multi-horizon prediction.
  arXiv  Detail & Related papers  (2025-12-13T11:50:18Z)
• Learning and Computation of $Φ$-Equilibria at the Frontier of Tractability [85.07238533644636]
  $Phi$-equilibria is a powerful and flexible framework at the heart of online learning and game theory.<n>We show that an efficient online algorithm incurs average $Phi$-regret at most $epsilon$ using $textpoly(d, k)/epsilon2$ rounds.<n>We also show nearly matching lower bounds in the online setting, thereby obtaining for the first time a family of deviations that captures the learnability of $Phi$-regret.
  arXiv  Detail & Related papers  (2025-02-25T19:08:26Z)
• Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDP [58.13930707612128]
  This work considers the sample complexity of obtaining an $varepsilon$-optimal policy in an average reward Markov Decision Process (AMDP) We prove an upper bound of $widetilde O(H varepsilon-3 ln frac1delta)$ samples per state-action pair, where $H := sp(h*)$ is the span of bias of any optimal policy, $varepsilon$ is the accuracy and $delta$ is the failure probability.
  arXiv  Detail & Related papers  (2022-12-01T15:57:58Z)
• Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning [54.806166861456035]
  We study the episodic reinforcement learning (RL) problem modeled by finite-horizon Markov Decision Processes (MDPs) with constraint on the number of batches. We design a computational efficient algorithm to achieve near-optimal regret of $tildeO(sqrtSAH3Kln (1/delta))$tildeO(cdot) hides logarithmic terms of $(S,A,H,K)$ in $K$ episodes. Our technical contribution are two-fold: 1) a near-optimal design scheme to explore
  arXiv  Detail & Related papers  (2022-10-15T09:22:22Z)
• Reward-Mixing MDPs with a Few Latent Contexts are Learnable [75.17357040707347]
  We consider episodic reinforcement learning in reward-mixing Markov decision processes (RMMDPs) Our goal is to learn a near-optimal policy that nearly maximizes the $H$ time-step cumulative rewards in such a model.
  arXiv  Detail & Related papers  (2022-10-05T22:52:00Z)
• Sharper Convergence Guarantees for Asynchronous SGD for Distributed and Federated Learning [77.22019100456595]
  We show a training algorithm for distributed computation workers with varying communication frequency. In this work, we obtain a tighter convergence rate of $mathcalO!!!(sigma2-2_avg!! . We also show that the heterogeneity term in rate is affected by the average delay within each worker.
  arXiv  Detail & Related papers  (2022-06-16T17:10:57Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.