SageSched: Efficient LLM Scheduling Confronting Demand Uncertainty and Hybridity

Das Paper stellt SageSched vor, einen effizienten LLM-Scheduler, der durch die Vorhersage der Ausgabe-Länge und die Berücksichtigung sowohl von Rechen- als auch von Speicherkosten bei unsicherer Nachfrage die Gesamteffizienz um über 28,7 % steigert.

Das Wesentliche

Stellen Sie sich vor, ein großes Sprachmodell (wie ein sehr kluger Chatbot) ist eine Super-Küche, in der viele Köche gleichzeitig arbeiten. Die Kunden (die Nutzer) bestellen Gerichte (Anfragen), aber es gibt zwei große Probleme, die die Küche oft zum Stillstand bringen:

1. Das "Unbekannte Menü"-Problem (Unsicherheit): Wenn ein Kunde bestellt, weiß er nicht genau, wie viele Gänge sein Essen haben wird. Ein Kunde will vielleicht nur einen kleinen Salat (kurze Antwort), ein anderer bestellt ein riesiges 10-Gänge-Menü (lange Antwort). Die Küche weiß das erst, wenn das Essen fertig ist.
2. Das "Platz-und-Koch-Problem" (Hybridität): Manche Gerichte brauchen viel Herdplatz (Rechenleistung), andere brauchen riesige Kühlschränke, um Zutaten vorzubereiten (Speicherplatz). Wenn die Küche nur auf den Herd achtet, aber der Kühlschrank voll ist, stehen alle Köche still.

Bisherige Systeme (die "Küchenmanager") waren oft dumm. Sie bedienten einfach die Leute in der Reihenfolge, in der sie kamen (wer zuerst kam, bekommt zuerst). Das führte dazu, dass ein Kunde, der ein riesiges 10-Gänge-Menü bestellte, die ganze Küche blockierte, während dahinter viele Leute mit kleinen Snacks warteten. Andere Manager versuchten, die Größe des Menüs vorherzusagen, aber ihre Vorhersagen waren oft schwerfällig und ungenau.

Hier kommt SageSched ins Spiel. Es ist wie ein genialer, erfahrener Küchenchef, der drei neue Tricks anwendet, um die Küche effizienter zu machen:

1. Der "Erinnerungs-Trick" (Vorhersage ohne Magie)

Statt eine komplexe Maschine zu bauen, die versucht, das Essen im Kopf des Kunden zu simulieren (was teuer und fehleranfällig ist), schaut SageSched einfach in sein Gedächtnis.

• Die Analogie: Wenn ein neuer Kunde bestellt, fragt der Chef: "Habe ich jemanden hier, der ähnlich bestellt hat wie dieser?" Wenn ja, schaut er: "Was hat der andere damals bekommen? War es kurz oder lang?"
• Der Vorteil: Er nutzt die Ähnlichkeit der Bestellung, um eine Wahrscheinlichkeitsverteilung zu erstellen. Er sagt nicht "Es wird genau 5 Gänge", sondern "Es ist wahrscheinlich zwischen 3 und 7 Gängen". Das ist leichtgewichtig, schnell und sehr genau, weil es auf echten Erfahrungen basiert.

2. Der "Gesamtkosten-Rechner" (Nicht nur Herd, auch Kühlschrank)

Früher haben Manager nur auf die Kochzeit (Rechenleistung) geachtet. SageSched weiß, dass der Kühlschrank (Speicher) genauso wichtig ist.

• Die Analogie: Ein Gericht, das schnell auf dem Herd fertig ist, aber einen riesigen Kühlschrank braucht, blockiert vielleicht den ganzen Raum. Ein anderes Gericht braucht viel Herdzeit, aber wenig Platz. SageSched berechnet den "wahren Preis" eines Auftrags: Wie viel Herdzeit plus wie viel Kühlschrankplatz wird insgesamt verbraucht?
• Der Vorteil: Er priorisiert nicht einfach die "schnellsten" Gerichte, sondern die, die die Küche insgesamt am wenigsten belasten.

3. Der "Glücksrad-Scheduler" (Umgang mit Unsicherheit)

Das ist der coolste Trick. Da wir nie genau wissen, wie lange ein Gericht dauert, aber eine gute Schätzung haben, nutzt SageSched eine mathematische Formel namens Gittins-Index.

• Die Analogie: Stellen Sie sich vor, Sie haben viele Kunden, und Sie wissen nicht, wer als nächstes fertig wird. Ein einfacher Manager würde denjenigen nehmen, der im Durchschnitt am schnellsten ist. SageSched fragt stattdessen: "Wer hat die höchste Chance, jetzt gerade fertig zu werden?"
• Es ist wie beim Spielen von Glücksrad-Spielen: Man wählt nicht den Spieler mit dem höchsten Durchschnittsgewinn, sondern den, bei dem die Wahrscheinlichkeit für einen schnellen Gewinn gerade am höchsten ist.
• Der Clou: Der Chef aktualisiert diese Entscheidung ständig. Wenn ein Kunde schon lange wartet und sein Gericht sich verzögert, rutscht er in der Schlange nach hinten, damit jemand anderes mit einer besseren Chance dran kommt.

Das Ergebnis

Durch diese drei Tricks schafft SageSched es, die "Küche" (den Server) viel effizienter zu betreiben.

• Die Kunden warten im Durchschnitt 28,7 % weniger Zeit, bis ihr letztes Wort (das fertige Gericht) auf dem Teller liegt.
• Es funktioniert auch dann gut, wenn die Vorhersagen nicht zu 100 % stimmen, weil der Algorithmus flexibel auf Unsicherheiten reagiert.

Zusammenfassend: SageSched ist kein starres System, das nur auf Zeit schaut. Es ist ein intelligenter Manager, der vergisst, was er schon gesehen hat, den Platz im Kühlschrank beachtet und ständig die besten Chancen berechnet, um sicherzustellen, dass niemand unnötig lange warten muss.

Technische Zusammenfassung

Hier ist eine detaillierte technische Zusammenfassung des Papers „SageSched: Efficient LLM Scheduling Confronting Demand Uncertainty and Hybridity" auf Deutsch:

1. Problemstellung

Die effiziente Planung (Scheduling) von Inferenzanfragen für Large Language Models (LLMs) ist entscheidend für die Benutzererfahrung, insbesondere um die Gesamtlatenz bis zum letzten Token (Time-to-Last-Token, TTLT) zu minimieren. Bestehende Scheduler scheitern jedoch an zwei fundamentalen Eigenschaften von LLM-Workloads:

• Unsicherheit (Uncertainty): Aufgrund des auto-regressiven Charakters von LLMs ist die Länge der Ausgabe (Anzahl der Tokens) vor der Inferenz nicht deterministisch. Sie kann erst nach Abschluss der Generierung bekannt sein. Im Gegensatz zu stabilen Workloads in Betriebssystemen oder Big Data zeigt sich hier eine starke Variabilität.
• Hybridität (Hybridity): LLM-Inferenzen sind sowohl rechenintensiv (Compute-bound) als auch speicherintensiv (Memory-bound), da sie massiv auf den GPU-Speicher für den KV-Cache (Key-Value Cache) angewiesen sind. Herkömmliche Scheduler betrachten oft nur die Rechenkosten oder nutzen einfache Heuristiken, was zu suboptimalen Entscheidungen führt.

Bestehende Lösungen wie vLLM (First-Come-First-Served) leiden unter Head-of-Line-Blocking. Neuere, vorhersagebasierte Ansätze (z. B. SSJF, TRAIL) nutzen oft schwerfällige, feinabgestimmte Modelle, um eine einzelne erwartete Ausgabelänge vorherzusagen. Dies ignoriert die Wahrscheinlichkeitsverteilung der Unsicherheit und vernachlässigt die Speicherressourcen, was zu ineffizienten Warteschlangen führt.

2. Methodik: SageSched

SageSched ist ein neuer Scheduler, der drei Schlüsseltechniken kombiniert, um Unsicherheit und Hybridität zu adressieren:

A. Semantik-bewusster, historischer Prädiktor (Semantic-aware History-based Predictor)

Statt ein schweres Modell zu trainieren, um die Ausgabe direkt zu simulieren, nutzt SageSched die Korrelation zwischen Prompt-Similarität und Ausgabelängen-Ähnlichkeit.

• Funktionsweise: Für eine eingehende Anfrage wird im Verlauf der letzten Inferenzen nach Prompts mit ähnlicher semantischer Einbettung (Cosine-Similarity) gesucht.
• Ergebnis: Anstatt einen einzelnen Wert vorherzusagen, wird die Verteilung der Ausgabelängen basierend auf den historischen Ergebnissen ähnlicher Anfragen geschätzt.
• Vorteil: Dies ist rechenleicht (keine Feinabstimmung nötig), schnell (< 0,5 ms pro Anfrage) und liefert eine probabilistische Verteilung statt eines ungenauen Punktwerts.

B. Ressourcen-basiertes Kostenmodell (Resource-bound-based Cost Modeling)

SageSched erkennt, dass die reine Ausgabelänge keine ausreichende Metrik für die Servicekosten ist, da der KV-Cache-Speicherbedarf stark variiert.

• Analyse: Das System unterscheidet zwischen rechen- und speichergebundenen Szenarien. Es wird gezeigt, dass in beiden Fällen die Kosten durch eine einheitliche Formel beschrieben werden können, die sowohl Eingabe- ($I$) als auch Ausgabelängen ($O$) sowie den Speicherbedarf pro Token berücksichtigt.
• Kostenfunktion: Die Gesamtkosten $C$ werden als $C = \frac{O^2}{2} + I \cdot O$ modelliert (angepasst an Einheiten für Rechenzeit oder Speicherkonsum). Dies erfasst den wahren Serviceaufwand genauer als einfache lineare Summen oder reine Ausgabelängen.

C. Unsicherheitsbewusste Planung (Uncertainty-aware Scheduling Policy)

Da die Kosten als Verteilung vorliegen, wird der klassische Erwartungswert (Mean) als Prioritätskriterium als suboptimal verworfen.

• Gittins-Index: SageSched wendet die Gittins-Policy an, ein bekanntes Optimierungsverfahren aus der Theorie der Multi-Armed Bandits. Der Gittins-Index berechnet den minimalen amortisierten Kostenwert basierend auf der gesamten Kostenverteilung.
• Dynamische Aktualisierung: Der Index wird nicht nur bei der Ankunft berechnet, sondern periodisch (an definierten „Bucket"-Grenzen) aktualisiert, um den verbleibenden Serviceaufwand zu berücksichtigen. Dies ermöglicht ein dynamisches Preemption (Unterbrechung), ohne das System durch zu häufige Neuplanung zu destabilisieren.

3. Wichtige Beiträge

1. Identifikation von Limitierungen: Durch Testbed-Messungen wurde nachgewiesen, dass bestehende Scheduler aufgrund der Nichtberücksichtigung von Unsicherheitsverteilungen und Speicherhybridität ineffizient sind.
2. Neues Scheduler-Design: Einführung von SageSched mit drei integrierten Techniken:
   • Semantik-basierte Vorhersage von Ausgabelängen-Verteilungen.
   • Ressourcen-grenzbasierte Kostenmodellierung (Compute + Memory).
   • Unsicherheitsbewusste Warteschlangenplanung mittels Gittins-Index.
3. Implementierung und Evaluation: Die Lösung wurde auf dem populären vLLM-Framework implementiert und umfassend evaluiert.

4. Ergebnisse

Die Evaluation erfolgte auf Testbeds mit verschiedenen Modellen (Llama3.1-8B, Qwen3-32B) und Datensätzen (SharedGPT, Alpaca, Document-Write) sowie in Simulationen bis zu 64 GPUs.

• Leistungssteigerung: SageSched übertrifft den State-of-the-Art-Scheduler (TRAIL) und andere Baselines (FCFS, FastServe, SSJF) in der durchschnittlichen TTLT um über 28,7 %.
• Robustheit: Die Leistung bleibt auch bei ungenauen Vorhersagen stabil, da der Gittins-Index die Verteilungsinformation nutzt.
• Skalierbarkeit: Die Overhead-Zeiten für Vorhersage und Scheduling steigen nur linear mit der Clustergröße. Selbst bei 64 GPUs beträgt der zusätzliche Latenzbeitrag pro Anfrage nur ca. 100 ms, was im Vergleich zu Inferenzzeiten von Sekunden bis Minuten vernachlässigbar ist.
• Vergleich: SageSched ist der einzige Scheduler, der sowohl die TTLT (Gesamtlatenz) als auch die TTFT (Time-to-First-Token) optimiert, da es Head-of-Line-Blocking effektiv verhindert.

5. Bedeutung und Fazit

SageSched adressiert ein kritisches Problem im Bereich des LLM-Servings: Die Diskrepanz zwischen den statischen Annahmen traditioneller Scheduler und der dynamischen, unsicheren Natur von LLM-Inferenzen.

• Paradigmenwechsel: Der Ansatz verschiebt den Fokus von der Vorhersage eines einzelnen Wertes hin zur Nutzung von Verteilungsinformationen und integriert Speicherkosten direkt in die Kostenfunktion.
• Praktische Relevanz: Durch die signifikante Reduktion der End-to-End-Latenz verbessert SageSched direkt die Benutzererfahrung und die Auslastung teurer GPU-Ressourcen.
• Generalisierbarkeit: Da der Prädiktor auf historischen Daten und semantischer Ähnlichkeit basiert, ist die Methode modellagnostisch und kann leicht auf verschiedene LLM-Architekturen angewendet werden, ohne aufwendiges Retraining.

Zusammenfassend stellt SageSched einen wesentlichen Fortschritt in der Effizienz von LLM-Infrastrukturen dar, indem er mathematisch fundierte Optimierungsmethoden (Gittins-Index) mit ressourcenbewusster Modellierung kombiniert.