Technische Samenvatting: Doorvoeroptimaliserende Scheduling-algoritmen voor LLM-inferentie en AI-agenten

Probleemstelling

Naarmate de vraag naar Large Language Models (LLM's) en AI-agenten groeit, is het optimaliseren van inferentiesystemen voor efficiëntie cruciaal. Hoewel aanzienlijke engineeringinspanningen zijn gericht op verbeteringen op systeemniveau, ontbreekt er een samenhangend wiskundig model en een wachtrijtheoretisch raamwerk om scheduling-algoritmen te evalueren. Specifiek behandelt het artikel de fundamentele vraag: Wat is de maximale doorvoersnelheid voor een LLM-inferentiesysteem, en welke klassen van scheduling-algoritmen kunnen deze limiet bereiken?

LLM-inferentie stelt unieke uitdagingen in vergelijking met klassieke wachtrijsystemen:

1. Tweefasige Verwerking: Verzoeken ondergaan een rekenkrachtgebonden prefill-fase (verwerken van invoertokens om de KV-cache op te bouwen), gevolgd door een geheugen-I/O-gebonden decode-fase (autoregressieve token-generatie).
2. Batchbeperkingen: Om GPU-gebruik te maximaliseren, worden verzoeken gebatcht. Het mengen van prefill- en decode-tokens creëert echter interferentie, en hardware legt een tokenbudget ($b_{max}$) en vaak een batchgrootte ($k_{max}$) beperking op.
3. AI-agent-werklasten: Moderne toepassingen omvatten netwerken van LLM-servers die complexe agenttaken verwerken, die Directed Acyclic Graph (DAG)-topologieën, fork-join-patronen of cyclische routing kunnen volgen.

Bestaande systemen hanteren diverse strategieën (bijv. FasterTransformer, vLLM, Orca, Sarathi-Serve) met variërende prioriteiten (prefill-first versus decode-first) en batchmogelijkheden (gemengd versus gescheiden). Beoefenaars vertrouwen momenteel op kostbare, werkdruk-specifieke benchmarking om systemen te kiezen, zonder een theoretische garantie voor stabiliteit of doorvoeroptimaliteit.

Methodologie

De auteurs ontwikkelen een rigoureus wachtrijtheoretisch raamwerk om LLM-inferentiesystemen te modelleren.

1. Stochastische Modellering

• Basismodel: Het systeem wordt gemodelleerd als een discrete-tijd Markov-keten (DTMC) die een batchservice-wachtrij met twee klassen voorstelt.
  • Klassen: Verzoeken bestaan in een prefill-wachtrij of een decode-wachtrij.
  • Batching: De server verwerkt gelijktijdig een batch tokens van beide wachtrijen, onderworpen aan een tokenbudget $b_{max}$.
  • Asymmetrie: Prefill-tokens van een enkel verzoek kunnen in bulk worden verwerkt, terwijl decode-tokens strikt sequentieel zijn (één per verzoek per batch).
• Verwerkingstijdmodel: Door gebruik te maken van empirische traces, wordt de batchverwerkingstijd $t_b$ benaderd door een stuksgewijs constante functie die afhankelijk is van de tokenbelasting $b$:
  $$t_b = c + a \cdot \lceil b/b_0 \rceil$$
  waarbij $c$ de basiskost is en $a$ de marginale kost per blok van $b_0$ tokens. Dit model vangt de dominantie van lineaire-laagberekeningen in LLM-inferentie.

2. Analytisch Raamwerk

• Fluid-Limit Techniek: De auteurs maken gebruik van het fluid-limit raamwerk (Dai 1995, Stolyar 1995) om stabiliteit te analyseren. Ze bewijzen dat onder specifieke voorwaarden het geschaalde stochastische proces convergeert naar een deterministisch fluid-model.
• Stabiliteitsdefinitie: Een systeem is stabiel (positief recurrent) als het totale aantal niet-verwerkte tokens niet divergeert naarmate de tijd naar oneindig gaat.
• Scheduling-klasse: De analyse richt zich op werkbehoudende algoritmen (die de batch tot capaciteit $b_{max}$ vullen wanneer mogelijk) en introduceert de K-FCFS-conditie (First-Come-First-Served met beperkt voorbijrijden) om de complexiteiten van gemengde batching te hanteren.

3. Uitbreidingen

Het raamwerk wordt uitgebreid tot:

• Parallelle Servers: Systemen met load balancing (Random of Join-the-Shortest-Queue).
• Multi-class Netwerken: Enkele servers die meerdere verzoekklassen verwerken (bijv. verschillende agentstappen).
• Netwerktopologieën: Multi-server netwerken met DAG-routing en fork-join-synchronisatie.
• Cyclische Routing: Analyse van netwerken met feedbacklussen (Rybko–Stolyar type).
• Batchgrootte-beperkingen: Analyse van systemen die beperkt zijn door zowel tokenbudget ($b_{max}$) als maximale batchgrootte ($k_{max}$).

Belangrijkste Bijdragen en Resultaten

1. Doorvoeroptimaliteit van Werkbehoudende Scheduling

Het artikel vestigt een fundamenteel ontwerpprincipe: Werkbehoudende scheduling-algoritmen bereiken maximale doorvoer voor single-server LLM-inferentie en netwerken met DAG- of fork-join-topologieën.

• Stelling 2: Voor een enkele server, als de aankomstbelasting $\lambda(m_p + m_d)$ kleiner is dan de maximale verwerkingssnelheid $b_{max}/t_{b_{max}}$, stabiliseert elk werkbehoudend K-FCFS-algoritme het systeem. Omgekeerd is het systeem onder elk algoritme instabiel als de belasting deze drempel overschrijdt.
• Implicatie: Dit biedt een theoretische bovengrens ($b_{max}/t_{b_{max}}$) en valideert de verschuiving in de industrie naar werkbehoudende schedulers.

2. Evaluatie van Bestaande Systemen

Toepassing van het theoretische raamwerk op real-world algoritmen levert duidelijke classificaties op:

• Doorvoeroptimaal (Werkbehoudend):
  • Orca: Ondersteunt gemengde batching (prefill + decode) met prefill-prioriteit.
  • Sarathi-Serve: Ondersteunt chunked prefill met decode-prioriteit en gemengde batching.
  • Nieuwste vLLM (met chunked prefill): Werkbehoudend.
• Suboptimaal/Instabiel (Niet-werkbehoudend):
  • FasterTransformer: Prioriteert decode maar verbiedt gemengde batching. Het laat de GPU inactief wanneer decode-verzoeken onvoldoende zijn om een batch te vullen, zelfs als er prefill-verzoeken wachten.
  • Vanilla vLLM: Prioriteert prefill maar verbiedt gemengde batching. Het laat decode-verzoeken wachten terwijl het batches verwerkt die alleen prefill bevatten.
• Experimentele Validatie: Real-world traces bevestigen dat niet-werkbehoudende algoritmen (FasterTransformer, vanilla vLLM) instabiel worden (wachtrij-opblazen) onder gematigde belastingen waar werkbehoudende algoritmen (Sarathi-Serve, Orca) stabiel blijven.

3. AI-agent-werklasten en Netwerktopologieën

• DAG en Fork-Join: Het artikel bewijst dat werkbehoudende scheduling doorvoeroptimaal blijft voor netwerken van LLM-servers die in DAG's of fork-join-topologieën zijn gerangschikt, mits de belastingconditie op elke server geldt.
• Cyclische Routing (Rybko–Stolyar Tegenvoorbeeld): De auteurs demonstreren dat werkbehoudende scheduling niet voldoende is voor netwerken met cyclische routing. Ze construeren een tweeservernetwerk waar specifieke prioriteitstoewijzingen onder een werkbehoudend beleid leiden tot instabiliteit, zelfs wanneer de totale belasting onder de capaciteit ligt. Dit onderstreept de noodzaak van zorgvuldig prioriteitsontwerp of niet-werkbehoudende beleidslijnen (bijv. back-pressure) in cyclische topologieën.

4. Impact van Batchgrootte-beperkingen

Wanneer een maximale batchgrootte-beperking ($k_{max}$) wordt opgelegd naast het tokenbudget ($b_{max}$):

• Wordt het stabiliteitsgebied een tweedimensionale convexe hull in het $(\lambda_{prefill}, \lambda_{decode})$-vlak, in plaats van een eenvoudige scalair drempelwaarde.
• Tegennatuurlijke Bevinding: In bepaalde regimes (specifiek nabij een hoekpunt van het stabiliteitsgebied dat gemengde batches betreft), kunnen strikt werkbehoudende algoritmen die altijd vullen tot $b_{max}$ het systeem niet stabiliseren. Optimale stabiliteit kan vereisen dat wordt gewerkt bij een lagere tokenbelasting (bijv. $b_0$) om de verwerkingssnelheden van prefill- en decode-tokens in evenwicht te brengen. Dit suggereert dat onder strakke batchgrootte-beperkingen adaptieve scheduling-strategieën noodzakelijk zijn.

Betekenis en Claims

Het artikel claimt de eerste rigoureuze wachtrijtheoretische basis te bieden voor LLM-inferentie-scheduling. De betekenis ligt in:

1. Ontwerpprincipe: Het identificeert "werkbehoudend" als een sleutelontwerpprincipe voor beoefenaars, en biedt theoretische zekerheid dat algoritmen zoals Sarathi-Serve en Orca doorvoeroptimaal zijn, terwijl het waarschuwt voor niet-gemengde batching-benaderingen zoals FasterTransformer en vanilla vLLM.
2. Brug tussen Gemeenschappen: Het verlaagt de drempel voor de wachtrijtheorie-gemeenschap om bij te dragen aan LLM-systemen door een formeel model te bieden dat de unieke tweefasige en batchkarakteristieken van LLM's vastlegt.
3. Richting voor AI-agenten: Het breidt stabiliteitsanalyse uit tot AI-agent-werklasten, en onthult dat terwijl DAG-topologieën robuust zijn, cyclische topologieën meer geavanceerde scheduling vereisen dan eenvoudige werkbehoudende beleidslijnen.
4. Nuance in Beperkingen: Het onthult dat praktische beperkingen zoals batchgrootte-limieten stabiliteitsgebieden fundamenteel kunnen veranderen, en uitdagingen biedt aan de aanname dat "het vullen van de batch" altijd optimaal is.

De auteurs concluderen dat hoewel hun werk een basisvestigt voor doorvoeroptimaliteit, toekomstig werk zich moet richten op optimalisatie van latentie, rijker verwerkingstijdmodellen (met inbegrip van attention-lagen), en het ontwerpen van adaptieve algoritmen voor complexe beperkingen en netwerktopologieën.