SageSched: Efficient LLM Scheduling Confronting Demand Uncertainty and Hybridity

Dit paper introduceert SageSched, een efficiënte planner voor LLM-inferentie die onzekerheid in vraag en hybride reken- en geheugeneisen aanpakt door outputlengtes te voorspellen en een onzekerheidsbewuste schedulingbeleid te hanteren, wat resulteert in een efficiëntieverbetering van meer dan 28,7%.

De kern

Stel je voor dat je een enorm drukke koffiezaak runt, maar in plaats van koffie, serveer je kunstmatige intelligentie (LLM's). Klanten komen binnen met vragen, en de AI moet antwoorden genereren, woord voor woord.

Het probleem is dat niemand weet hoe lang een antwoord zal duren. Soms is het een kort "Ja", soms een heel verhaal van 500 woorden. Bovendien is het werk zwaar: het kost niet alleen veel rekenkracht (zoals het bakken van koffie), maar ook veel geheugenruimte (zoals het opbergen van de bonnetjes en ingrediënten in de koelkast).

Deze paper introduceert SageSched, een slimme "manager" voor deze AI-koffiezaak die zorgt dat alles soepel verloopt, zelfs als het chaotisch druk is. Hier is hoe het werkt, vertaald naar alledaagse taal:

1. Het Grote Probleem: Onzekerheid en Twee Soorten Werk

In de oude manier van werken (zoals bij vLLM of SGLang), volgden ze een simpele regel: "Wie er eerst komt, krijgt eerst bediend" (First-Come-First-Served).

• Het nadeel: Stel, er komt een klant binnen die een heel kort antwoord wil, maar staat achter een klant die een heel lang verhaal gaat schrijven. De korte klant moet wachten, terwijl de lange klant de hele tijd de machine bezet houdt. Dit heet head-of-line-blocking.
• De complexiteit: Sommige vragen zijn zwaar voor de rekenkracht (denk aan het bakken van de koffie), andere vragen zijn zwaar voor het geheugen (het opbergen van de bonnetjes). Oude systemen keken alleen naar de rekenkracht en vergeten het geheugen.

2. De Oplossing: SageSched

SageSched is als een super-slimme manager die drie nieuwe trucs heeft:

Truc 1: De "Herinnering" in plaats van de "Voorspeller"

Oude systemen probeerden met zware, getrainde modellen te raden hoe lang een antwoord zou zijn. Dat was traag en vaak fout.

• De SageSched-methode: In plaats van te raden, kijkt de manager naar het verleden. "Ah, deze klant vraagt iets over 'recepten voor pannenkoeken'. Vorige week had iemand een vergelijkbare vraag en toen duurde het antwoord precies 3 minuten."
• De analogie: Het is alsof je niet probeert te voorspellen hoe lang het regent, maar gewoon kijkt naar wat de buren deden toen het ook regende. SageSched zoekt naar vergelijkbare vragen in de geschiedenis en kijkt hoe lang die duurden. Zo krijgt hij een verdeling van mogelijke tijden (bijv. "meestal 2-4 minuten, soms 10"), in plaats van één vast getal. Dit is snel en accuraat.

Truc 2: De "Totaalkost" (Rekenkracht + Geheugen)

Oude managers keken alleen naar het aantal woorden dat eruit zou komen.

• De SageSched-methode: SageSched beseft dat een korte vraag met een enorme hoeveelheid context (veel "bonnetjes" in het geheugen) zwaarder kan zijn dan een lange vraag met weinig context.
• De analogie: Het is alsof je twee pakketten moet vervoeren. Pakket A is klein maar weegt 100 kilo (zwaar geheugen). Pakket B is groot maar weegt 1 kilo (veel woorden, weinig geheugen). Een oude manager zou zeggen: "Pakket B is groter, dus die is zwaarder." SageSched zegt: "Nee, Pakket A is zwaarder voor onze vrachtwagen (GPU), dus die moet eerst."

Truc 3: De "Gittins-Index" (De Slimme Wachtlijst)

Nu we weten wat de kosten zijn, hoe ordenen we de wachtlijst?

• Het oude idee: "Wie het kortste antwoord heeft, gaat eerst."
• Het SageSched-probleem: Soms is een antwoord gemiddeld lang, maar heeft het een grote kans om snel klaar te zijn. Als je wacht tot het zeker is, mis je kansen.
• De SageSched-methode: Ze gebruiken een wiskundige formule (de Gittins-index) die werkt als een slotmachine-strategie. Ze kijken niet alleen naar de gemiddelde duur, maar naar de kans dat een klant snel klaar is.
• De analogie: Stel je hebt drie klanten.
  1. Klant A: Zeker 10 minuten.
  2. Klant B: 50% kans op 1 minuut, 50% kans op 100 minuten.
  3. Klant C: Zeker 2 minuten.
     Een simpele manager zou B misschien negeren omdat de gemiddelde tijd hoog is. SageSched zegt: "Klant B heeft een grote kans om nu klaar te zijn. Laten we die eerst doen, want als het mislukt, kunnen we altijd nog naar C gaan." Dit minimaliseert de totale wachttijd voor iedereen.

Het Resultaat

Door deze drie trucs te combineren, kan SageSched de wachtrijen veel efficiënter beheren.

• Resultaat: De paper toont aan dat SageSched de totale wachttijd voor gebruikers met meer dan 28% verkort in vergelijking met de beste huidige systemen.
• Conclusie: Het is alsof je van een chaotische, drukke koffiezaak bent gegaan naar een geoliede machine waar niemand onnodig lang hoeft te wachten, omdat de manager precies weet wie er snel geholpen kan worden en wie de zware lasten draagt.

Kortom: SageSched maakt AI sneller en reagerender, niet door de AI zelf sneller te maken, maar door de planning van de vragen veel slimmer te doen.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het paper "SageSched: Efficient LLM Scheduling Confronting Demand Uncertainty and Hybridity" in het Nederlands.

Probleemstelling

De efficiënte planning (scheduling) van inferentie-aanvragen voor Large Language Models (LLM's) is cruciaal voor de gebruikerservaring, specifiek om de Time-to-Last-Token (TTLT) te minimaliseren. Bestaande schedulers kampen echter met twee fundamentele uitdagingen die hun prestaties beperken:

1. Onzekerheid in vraag (Demand Uncertainty): Vanwege het autoregressieve karakter van LLM's is de lengte van de output (aantal tokens) niet van tevoren bekend. Bestaande systemen vertrouwen vaak op simpele heuristieken of proberen een enkele voorspelde waarde te genereren, wat onnauwkeurig is en de inherente waarschijnlijkheidsverdeling van de output negeert.
2. Hybriditeit van vraag (Demand Hybridity): LLM-inferenties zijn zowel rekenintensief (compute-bound) als geheugintensief (memory-bound) vanwege de zware afhankelijkheid van KVCache. Bestaande schedulers (zoals vLLM en SGLang) focussen vaak alleen op rekentijd of outputlengte, en negeren de geheugenvraag. Dit leidt tot suboptimale beslissingen, vooral als het systeem geheugenbeperkt is.

Bestaande oplossingen lijden onder "head-of-line-blocking" (bij FCFS) of gebruiken zware, getrainde modellen voor voorspelling die geen kansverdeling leveren.

Methodologie: SageSched

SageSched is een nieuwe scheduler ontworpen om deze uitdagingen aan te pakken door drie kerncomponenten te integreren:

1. Semantisch-bewuste, geschiedenisgebaseerde voorspeller

In plaats van een zwaar, getraind model te gebruiken om een enkele outputlengte te voorspellen, gebruikt SageSched een lichtgewicht aanpak:

• Principe: Het maakt gebruik van de correlatie tussen de semantische gelijkenis van een prompt en de gelijkenis in de outputlengte.
• Werking: Voor een nieuwe aanvraag zoekt het systeem in de recente geschiedenis naar eerdere aanvragen met een vergelijkbare prompt (gemeten via cosine-similarity van embeddings).
• Resultaat: In plaats van één getal, levert het de verdeling van de outputlengte op basis van de historische resultaten van die vergelijkbare prompts. Dit vereist geen fine-tuning en is zeer nauwkeurig.

2. Resource-bound gebaseerde kostenmodellering

SageSched modelleert de werkelijke servicekosten van een aanvraag door rekening te houden met zowel rekenkracht als geheugen:

• Analyse: Het systeem analyseert of de backend op dat moment compute-bound of memory-bound is.
• Universeel Model: Het paper toont aan dat in beide scenario's de kostenparadigma vergelijkbaar is. De totale kosten ($C$) worden gemodelleerd als een functie van de inputlengte ($I$) en de outputlengte ($O$):
  $$C = \frac{O^2}{2} + IO$$
  Deze formule vangt de cumulatieve impact van KVCache-gebruik en rekenwerk over de gehele inferentiecyclus, in tegenstelling tot eerdere modellen die alleen op $O$ of een gewogen som van $I$ en $O$ focusten.

3. Onzekerheidsbewuste planningsbeleid (Gittins Index)

Omdat de kosten van een aanvraag nu een verdeling zijn (geen vast getal), gebruikt SageSched een geavanceerde wiskundige benadering voor de wachtrij:

• Gittins Index: Het systeem berekent de Gittins-index voor elke aanvraag op basis van zijn kostenverdeling. Deze index is bekend uit de theorie van multi-armed bandits en garandeert theoretisch de optimale prestatie (minimale gemiddelde latentie) voor taken met onbekende duur maar bekende verdelingen.
• Dynamische Refreshing: De index wordt niet statisch berekend. SageSched ververst de Gittins-index periodiek (bij grenswaarden van "buckets" van de kostenverdeling) om rekening te houden met de voortgang van lopende inferenties, zonder de systeemstabiliteit te verstoren door te vaak te herschikken.

Belangrijkste Bijdragen

1. Identificatie van beperkingen: Het paper kwantificeert de inefficiëntie van bestaande schedulers bij het hanteren van onzekerheid en hybriditeit in LLM-workloads.
2. Ontwerp van SageSched: Een nieuwe architectuur die drie innovaties combineert:
   • Een trainingsvrije, semantisch-bewuste voorspeller voor outputlengte-verdelingen.
   • Een unificatie van reken- en geheugenkosten in één model.
   • Een planningsbeleid gebaseerd op de Gittins-index voor optimale wachtrijorde.
3. Implementatie en Evaluatie: SageSched is geïmplementeerd bovenop het populaire vLLM-framework en uitgebreid getest.

Resultaten

De evaluaties zijn uitgevoerd op diverse hardware-configuraties (A40 en H800 GPU's) met verschillende modellen (Llama3.1-8B, Qwen3-32B) en datasets (SharedGPT, Alpaca, Document-Write).

• Prestatieverbetering: SageSched presteert significant beter dan state-of-the-art schedulers (zoals FCFS, FastServe, SSJF, TRAIL). Het bereikt een verbetering in de gemiddelde TTLT van meer dan 28,7%.
• Robuustheid: De voordelen zijn het grootst bij hoge belasting en bij datasets met lange input-outputs, waar bestaande methoden het meest falen.
• Overhead: De extra overhead voor voorspelling en planningsberekening is verwaarloosbaar (gemiddeld < 100ms per aanvraag, zelfs bij schaalvergroting tot 64 GPU's).
• Componentanalyse: Microscopische analyses bevestigen dat elk onderdeel (voorspeller, kostenmodel, Gittins-beleid) essentieel is voor de totale prestatieverbetering.

Betekenis

SageSched markeert een belangrijke stap in de optimalisatie van LLM-diensten. Door de inherente onzekerheid en de hybride aard van LLM-inferenties niet als een nadeel te zien, maar als een statistisch kenmerk dat kan worden benut, biedt het een theoretisch onderbouwde en praktische oplossing. Het stelt systemen in staat om niet alleen sneller te reageren, maar ook om GPU-bronnen (zowel VRAM als compute) veel efficiënter te benutten, wat essentieel is voor de schaalbaarheid van LLM-toepassingen in de toekomst.