💻 computer science

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

TEMPO introduceert een maaktijd-bewuste expert-parallelle load balancing dispatcher die niet-lineaire expert-executietijden over geheugen- en rekengebonden regimes modelleert om de tokenverdeling dynamisch te optimaliseren, waarbij tot 15,5% doorvoergroei en significante latentiereducties worden bereikt in scenario's met gemengde regimes waar traditionele lineaire telgebaseerde methoden falen.

Oorspronkelijke auteurs: Jie Li, Chenxin Jia, Jinliang Shen, Cunzhuang Liu, Ruiyi Ding, Jianwen Xian, Kang He, Chengru Song

Gepubliceerd 2026-08-14

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Jie Li, Chenxin Jia, Jinliang Shen, Cunzhuang Liu, Ruiyi Ding, Jianwen Xian, Kang He, Chengru Song

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een enorme, razendsnelle pizzabestelservice runt voor een stad die nooit slaapt. Je hebt een vloot identieke bezorgers (de GPU's) en een centrale keuken met honderden verschillende specialiteitschefs (de "experts" in een AI-model). Elke keer als een klant een pizza bestelt, moet het systeem beslissen welke chefs aan de pizza werken en welke chauffeur de afgeronde pizza meeneemt. In de wereld van Kunstmatige Intelligentie, specifits bij een type model dat een "Mixture-of-Experts" (MoE) wordt genoemd, is dit precies wat er gebeurt. Deze AI-modellen zijn als gigantische hersenen die bestaan uit duizenden kleinere, gespecialiseerde sub-hersenen. Wanneer de AI nadenkt, gebruikt hij niet zijn hele brein tegelijk; hij kiest een paar specifieke experts om de taak af te handelen.

De grote uitdaging is om het hele team op dezelfde snelheid te laten bewegen. Als één chauffeur vast komt te zitten met een enorme, ingewikkelde bestelling terwijl de rest niets te doen heeft, wordt de hele levering vertraagd. De tijd die het kost om een batch bestellingen af te handelen, wordt bepaald door de langzaamste persoon in de groep. Jarenlang was de standaardregel voor het balanceren van deze werklast simpel: "Verdeel het aantal bestellingen gewoon gelijkmatig." Als je 100 bestellingen hebt, geef je er 10 aan elk van de 10 chauffeurs. Dit leek logisch, alsof je een stapel appels gelijk verdeelt. Maar wat als sommige appels zware stenen zijn en andere lichte veren? Of wat als de keuken een regel heeft waarbij het ophalen van een nieuwe chef een vaste hoeveelheid tijd kost, ongeacht hoeveel pizza's ze maken? De oude regels gingen ervan uit dat tijd altijd direct verbonden was aan het aantal bestellingen. Deze paper vraagt: wat als die aanname onjuist is?

De onderzoekers achter deze paper, werkend bij KlingAI, ontdekten dat de oude "tel de bestellingen"-regel eigenlijk een valstrik is. Ze ontdekten dat in moderne AI-hardware de tijd die nodig is om een expert te verwerken niet alleen afhangt van hoeveel tokens (woorden of datapakketjes) deze ziet. Het is een tweeledig beest. Soms wordt de tijd gedomineerd door de pure inspanning om het "recept" van de expert (de gewichten) uit het geheugen te laden, wat een vaste hoeveelheid tijd kost, ongeacht hoe klein de bestelling is. Op andere momenten, zodra het recept geladen is, groeit de tijd lineair mee met het aantal bestellingen. De oude methoden, die alleen naar het aantal bestellingen keken, misten de verborgen kosten van het laden van het recept. Ze probeerden een stapel veren en stenen te balanceren door ze te tellen, in plaats van ze te wegen.

Om dit op te lossen, bouwde het team een nieuwe dispatcher genaamd TEMPO (Time-modeled Expert-Parallel Optimization). In plaats van alleen tokens te tellen, fungeert TEMPO als een slimme verkeersregelaar die de fysica van de keuken begrijpt. Het gebruikt een speciale "kostenmodellen" die exact meet hoe lang het duurt om het recept van een chef te laden en hoe lang het duurt om de pizza te bakken. Het realiseert zich dat als je een "koude" expert hebt (één die een tijdje niet is gebruikt), het verdelen van zijn kleine bestelling over twee chauffeurs een ramp is, omdat je de "laadkosten" twee keer moet betalen. Maar als je een "hete" expert hebt met een berg aan bestellingen, is het verdelen ervan prima.

De paper laat zien dat TEMPO niet alleen maar gokt; het berekent de perfecte balans voor elke batch verzoeken in milliseconden. Ze testten dit op echte AI-modellen en vonden dat de oude methoden vaak 15% langzamer waren of significante vertragingen veroorzaakten voor de laatste paar klanten in een rij. TEMPO houdt de lijn echter soepel in beweging. Het is alsof je overstapt van een regel die zegt "iedereen krijgt hetzelfde aantal appels" naar een regel die zegt "iedereen krijgt evenveel werk", rekening houdend met het feit dat sommige appels zwaar zijn en sommige chefs traag wakker worden.

De onderzoekers waren zeer zorgvuldig in het aantonen waar deze nieuwe methode wel en niet werkt. Ze bewezen dat als de "hete" experts zo talrijk zijn dat het systeem simpelweg wordt overweldigd door de enorme hoeveelheid data (het "compute-bound" regime), de oude methode van het tellen van tokens eigenlijk prima is. Maar in de echte wereld, waar sommige experts druk zijn en anderen rusten, en waar de "laadkosten" hoog zijn, blinkt TEMPO uit. Ze brachten zelfs een "fasediagram" in kaart, wat een soort weerkaart is voor AI-verkeer, die precies voorspelt wanneer de nieuwe methode tijd zal besparen en wanneer de oude methode goed genoeg is.

Uiteindelijk gaat deze paper niet alleen over een sneller algoritme; het gaat over het veranderen van hoe we denken over het verdelen van werk in AI. Het leert ons dat je in de complexe, hogesnelheidswereld van moderne AI niet alleen dingen kunt tellen. Je moet de verborgen kosten van het verplaatsen van data en de specifieke vorm van het werk begrijpen. Door de werkelijke tijd te meten die nodig is om de klus te klaren in plaats van alleen de items te tellen, maakt TEMPO AI-modellen sneller, efficiënter en klaar om aan de enorme eisen van de toekomst te voldoen. Het verandert een chaotische keuken in een goed geoliede machine, waardoor geen enkele chauffeur hoeft te wachten terwijl de pizza onder de warmtelamp ligt.

Technische Samenvatting: TEMPO – Makespan-bewuste Expert-Parallel Load Balancing

1. Probleemdefinitie

In Mixture-of-Experts (MoE) serving wordt de latentie van een laag bepaald door de makespan (de maximale tijd besteed aan een enkele GPU) vanwege synchronisatiepunten aan het einde van elke laag. Huidige productiedispatchers (bijv. EPLB, LPLB, UltraEP, METRO) proberen de belasting te balanceren door proxies te optimaliseren: ofwel het aantal tokens per GPU, ofwel het aantal geactiveerde experts per GPU. Deze proxies vertrouwen op impliciete lineariteitsaannames—dat de executietijd van een expert lineair proportioneel is aan het aantal tokens of het aantal experts respectievelijk.

Echter, metingen op datacenter-GPU's (specifiek met behulp van DeepGEMM fp8 grouped GEMM kernels) onthullen dat de executietijd van een expert niet-lineair is en een twee-regime structuur volgt:

Memory-Bound (Flat) Regime: Onder een drempelwaarde van $n^* \approx 156\text{--}168$ tokens per expert, wordt de kosten gedomineerd door het streamen van expert-gewichten uit High Bandwidth Memory (HBM). In dit regime is de tijd constant per geactiveerde expert-replica, ongeacht het aantal tokens.
Compute-Bound (Linear) Regime: Boven $n^*$ wordt de kosten lineair met het aantal tokens. Echter, door de implementatie van grouped GEMM die tokens naar 128-token M-tiles afrondt, introduceert het splitsen van een expert over meerdere replica's "padded compute", wat de kosten niet-lineair maakt op een manier die eenvoudige token-tellingen missen.

Consequent bevatten echte decode-batches vaak een gemengd regime: "hete" experts met veel tokens (lineair regime) en "koude" experts met weinig tokens (plat regime) bestaan naast elkaar. Bestaande proxies falen omdat strategieën voor token-balancering koude experts fragmenteren (waardoor verborgen activatie-vloeren worden betaald), terwijl activatie-balancering strategieën hete replica's overbelasten. Geen enkele vaste proxy is optimaal over alle operationele punten.

2. Methodologie

Kostenmodellering

De auteurs formaliseren de executietijd $t$ per expert als een max-affine functie:
$t = \max(a + bG, c + \beta N)$
Waarbij $G$ het aantal geactiveerde expert-replica's is en $N$ het aantal tokens.

$b$ (Activation Floor): De kosten voor het streamen van gewichten voor een extra replica (memory-bound).
$\beta$ (Token Slope): De kosten per token in het compute-bound regime.
Tile Awareness: Voor prefill of grote batches legt een secundaire parameter het "trapsgewijze" effect van 128-token tiling vast, waardoor het model wordt verfijnd tot $t = \max(a+bG+b_2(T-G), c+\beta N)$ .

Dit model wordt gekalibreerd via een black-box, tien-minuten durende microbenchmark op de uitgerolde kernel, waarbij de wandkloktijden over $(G, N)$ grids worden gemeten.

Probleemformulering

Het dispatch-probleem wordt geformaliseerd als een fixed-charge makespan minimalisatie probleem. De auteurs bewijzen dat dit probleem NP-hard is, zelfs met twee GPU's en volledige replicatie, aangezien het twee concurrerende beperkingen (activatie-aantal versus token-aantal) tegelijkertijd vereist om te balanceren. Het probleem is echter polynomiaal in degeneratieve limieten (pure token-balancering of pure activatie-balancering).

Het TEMPO Algoritme

TEMPO (Time-modeled Expert-Parallel Optimization) is een dispatcher die dit makespan-probleem in milliseconden oplost, werkend buiten het kritieke pad. De solver, tempo fast, hanteert vier stadia:

Cost-Aware Greedy Seeding: Plaatst volledige experts op replica's met de laagste marginale kosten, om de fragmentatie van koude experts te vermijden.
Activation Rebalancing: Gebruikt augmenting chains om het aantal experts te herbalanceren in het platte regime (waar token-verplaatsingen ineffectief zijn).
Bottleneck Local Search: Voert partiële token-migraties uit om de makespan in het lineaire regime te verminderen.
Ensemble met Switching Tolerance: Scoort de huidige oplossing tegenover een Token-LP (Lineair Programmeren) baseline en een Round-Robin heuristiek. Het wisselt alleen als de nieuwe oplossing >1% beter is, wat stabiliteit garandeert en de theoretische garanties van de eenvoudigere algoritmen overneemt.

Systeemintegratie

TEMPO is geïntegreerd in SGLang met een focus op zero overhead op het kritieke pad:

In-Graph: Een enkele gefuseerde CUDA kernel handelt probabilistische dispatch en count collectie af, wat de per-layer collectieven elimineert die vereist zijn voor vorige LP solvers.
Out-of-Process: De solver draait in een apart proces, wat GIL-contention voorkomt en ervoor zorgt dat de dispatch-beslissing de inference graph niet blokkeert.
Topology Awareness: Voor multi-node opstellingen zorgt een twee-fasen split ervoor dat tokens eerst naar replica's op dezelfde node worden gerouteerd, wat inter-node verkeer minimaliseert zonder de kern van de solver te wijzigen.

3. Belangrijkste Resultaten

Theoretisch en Simulatie

Fase-diagram: Een gekalibreerd fase-diagram demonstreert dat de optimale vaste policy wisselt tussen activatie-balancering (memory-bound) en token-balancering (compute-bound) op basis van batchgrootte en expert-skew. TEMPO volgt de optimale policy over deze gehele kaart.
Benaderingsgarantie: Onder volledige replicatie biedt TEMPO een additieve benaderingsgarantie van $OPT + \max(b, \beta n_{max})$ .
Simulatiewinsten: In gesimuleerde omgevingen bereikt TEMPO tot wel 15,5% verbetering ten opzichte van de beste vaste baseline in mixed-regime scenario's (specifiek voor EP32–64 extrapolaties).

Empirische Evaluatie (Testbed A & B)

Microbenchmarks: Op een 8-GPU Testbed A blijft TEMPO binnen 1% van de beste vaste baseline op elk geëvalueerd gridpunt en wint met tot wel 15,5% waar regimes mengen.
End-to-End Serving (Qwen3-235B):
- Bij lang-context en decode-zware verkeer verbetert TEMPO de throughput met 4–6% en vermindert het de p99 inter-token latentie met ~15,6%.
- Op een 2-node EP16 setup met topology-aware splitting bereiken de winsten 4–7%.
- Cruciaal is dat de auteurs opmerken dat een groot deel van het gat tussen TEMPO en de door SGLang geleverde LPLB architecturaal is (het verwijderen van in-graph collectieven); wanneer LPLB naar dezelfde architectuur wordt geport, is de residuele winst van TEMPO voornamelijk stabiliteit bij compute-bound punten.
End-to-End Serving (DeepSeek-V3): Op een model waar communicatie domineert en experts kleiner per GPU zijn (buiten de "win region"), levert TEMPO enkel de mechanisme-kosten op, presterend op gelijke voet met statische plaatsing. Dit bevestigt de claim van het papier dat de voordelen conditioneel zijn.
Staleness en Placement: Het systeem is robuust tegen plaatsing-stalheid (tot 200ms drift). Echter, als de plaatsingslaag significant stale is (hete experts verplaatst naar koude replica's), kan dispatch alleen de throughput niet herstellen; alleen de plaatsingslaag kan het gemiddelde herstellen, terwijl dispatch de latentie-tail repareert.

4. Betekenis en Claims

De primaire claim van het papier is geen universele prestatiewinst, maar een fase-diagram dat voorspelt wanneer time-based dispatch voordelig is.

De "Win Region": Adaptieve dispatch levert significante winsten alleen wanneer:
1. Het model grote experts heeft (hoge activation floor $b$ ).
2. Batches in een gemengd regime zijn (bevatten zowel hete als koude experts).
3. Placement voldoende stale is om disbalans te veroorzaken, maar niet zo stale dat alleen gewichts-migratie het kan oplossen.
4. Expert-compute een significant deel van de stap-tijd vormt (niet gedomineerd door communicatie).
Methodologische Verschuiving: Het papier betoogt dat "tijd balanceren, niet tokens" de principiële aanpak is voor MoE serving. Het demonstreert dat token-count proxies systematisch fout zijn in memory-bound regimes en dat een gekalibreerd kostenmodel noodzakelijk is om de interactie tussen memory en compute bottlenecks te navigeren.
Praktiseerbaarheid: Het werk biedt een inzetbare oplossing (TEMPO) die naadloos integreert in bestaande serving stacks (SGLang) met verwaarloosbare overhead, wat bewijst dat complexe makespan optimalisatie in milliseconden kan worden uitgevoerd zonder de inference te blokkeren.

De auteurs stellen expliciet dat voor kleine expert-vormen of communicatie-gedomineerde modellen, adaptieve dispatch geen voordeel biedt ten opzime van statische plaatsing, en dat het systeem correct degradeert naar gelijkwaardigheid in plaats van een penalty te veroorzaken. De bijdrage is het in kaart brengen van deze condities en het algoritme om deze te navigeren.