🤖 AI

Geometry-Aware Online Scheduling for LLM Serving: From Theoretical Bound to System Practice

Dieses Paper schlägt ein geometrie-bewusstes Online-Scheduling-Framework vor, das die Algorithmen Smallest Volume First (SVF) und 1-bit SVF umfasst, welche die Wettbewerbsverhältnisse theoretisch verbessern und die LLM-Serving-Performance praktisch steigern, indem sie den dynamischen 2D-Speicherbedarf von Key-Value-Caches effektiver adressieren als traditionelle zeitzentrierte Heuristiken.

Ursprüngliche Autoren: Li Kong, Qi Qi, Yinyu Ye, Zijie Zhou

Veröffentlicht 2026-06-23

📖 4 Min. Lesezeit☕ Kaffeepausen-Lektüre

CC BY 4.0

Ursprüngliche Autoren: Li Kong, Qi Qi, Yinyu Ye, Zijie Zhou

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie führen ein belebtes Café. Dies ist nicht irgendein Café; es ist ein hochmodernes Café, in dem jedes Getränk, das Sie zubereiten, eine bestimmte Menge an Arbeitsfläche (Speicher) beansprucht, die wächst, je länger Sie an der Zubereitung arbeiten.

In der Welt der Large Language Models (LLMs) wird dieser „Arbeitsflächen-Speicher“ als KV-Cache bezeichnet. Jedes Mal, wenn die KI ein Wort (Token) generiert, benötigt sie ein wenig mehr Speicher, um sich zu erinnern, was sie gerade gesagt hat, damit der Gesprächsfluss erhalten bleibt. Wenn Ihnen der Platz auf der Arbeitsfläche ausgeht, muss der gesamte Betrieb im Café stoppen.

Das Problem: Der „Shortest Job First“-Fehler

Lange Zeit verwalteten Computersysteme diese Anfragen nach einer Regel namens Shortest Job First (SJF). Die Logik ist simpel: „Wenn ein Kunde einen schnellen Espresso bestellt, lassen wir ihn zuerst bedienen, weil er schnell geht. Wenn jemand einen komplizierten 20-minütigen Latte bestellt, muss er warten.“

Das Paper argumentiert, dass diese Regel in der Welt der KI eigentlich fehlerhaft ist. Hier ist der Grund:

Die Falle: In einem normalen Café nimmt eine kurze Bestellung nur für kurze Zeit Platz ein. Aber in einem KI-Café kann selbst eine „kurze“ Anfrage riesige Mengen an Arbeitsfläche beanspruchen, wenn der Kunde eine lange Geschichte erzählt.
Die 2D-Realität: Das Paper sagt, dass wir in zwei Dimensionen denken müssen: Zeit (wie lange es dauert) und Raum (wie viel Speicher es während des Wachstums verbraucht). Die alte Regel betrachtete nur die Zeit.
Das Ergebnis: Indem man nur „schnelle“ Jobs priorisiert, verstopft das System oft mit Anfragen, die zwar schnell starten, aber den gesamten Speicher aufbrauchen und dadurch alle anderen blockieren. Es ist, als ließe man einen Kunden einen winzigen Espresso bestellen, doch dann entscheidet er sich, eine Stunde lang am Tresen zu sitzen und blockiert so den Barista daran, etwas anderes zu machen.

Die Lösung: „Smallest Volume First“ (SVF)

Die Autoren schlagen eine neue Regel vor, die Smallest Volume First (SVF) genannt wird. Anstatt zu fragen: „Wie schnell ist das?“, fragen sie: „Wie viel Arbeitsfläche wird diese Anfrage über ihre gesamte Lebensdauer hinweg beanspruchen?“

Denken Sie an das Beladen eines Lieferwagens:

Der alte Weg (SJF): Man lädt zuerst die kleinsten Kartons, in der Hoffnung, dass sie passen.
Der neue Weg (SVF): Man berechnet das gesamte „Volumen“ jedes Gegenstands (Höhe × Breite × Tiefe) und lädt zuerst die Gegenstände, die insgesamt den geringsten Platz beanspruchen.

Durch dieses Vorgehen werden Anfragen, die einen „kleinen“ Gesamtspeicherbedarf haben, schnell abgearbeitet. Dies schafft Platz, damit auch größere Anfragen früher beginnen können, was verhindert, dass das gesamte System stecken bleibt.

Der „1-Bit“-Trick (1-bit SVF)

Genau vorherzusagen, wie lange ein Gespräch dauern wird, ist schwer. Es ist, als versuche man zu erraten, wie viele Wörter ein Kunde sagen wird, bevor er aufhört zu reden. Das Paper führt eine clevere Abkürzung namens 1-bit SVF ein.

Anstatt zu versuchen, die exakte Anzahl der Wörter vorherzusagen, stellt das System nur eine einfache Frage: „Ist dies eine kurze oder eine lange Anfrage?“ (Ja/Nein).

Es verwendet einen winzigen Bruchteil an Information (nur ein „Bit“), um die Anfrage zu kategorisieren.
Überraschenderweise zeigt das Paper, dass diese einfache Vermutung fast so gut ist wie eine komplexe Vorhersage. Es ist, als würde ein Barista nur fragen: „Ist das ein schneller Kaffee oder ein langes Getränk?“ und Entscheidungen basierend auf dieser einfachen Antwort treffen. Das spart viel Gehirnschmalz (Rechenleistung), während der Betrieb dennoch reibungslos läuft.

Was das Paper bewiesen hat

Die Autoren haben nicht nur vermutet, dass dies funktioniert; sie haben die Mathematik dahinter geliefert, um es zu beweisen:

Die Mathematik: Sie zeigten, dass ihr neues Verfahren in den schlimmsten Szenarien (wie bei einem plötzlichen Ansturm von Kunden) garantiert viel besser ist als die alte „Shortest Job First“-Methode. Sie haben die mathematische Garantie von einem Zustand, der potenziell 48-mal schlechter als perfekt war, auf nur noch 5-mal schlechter verbessert.
Der Test: Sie testeten dies an echten KI-Modellen (Llama-3.1) unter Verwendung eines populären Systems namens vLLM.
- Ergebnis: Die neue Methode machte die KI für alle schneller, insbesondere für die langsamsten Anfragen (Reduzierung der „Tail Latency“).
- Effizienz: Die „1-Bit“-Version war unglaublich leichtgewichtig, fügte dem System fast keine Verzögerung hinzu und funktionierte dennoch sehr gut.

Zusammenfassung

Vereinfacht ausgedrückt sagt dieses Paper: Beurteilen Sie KI-Anfragen nicht nur danach, wie schnell sie fertig sind. Beurteilen Sie sie danach, wie viel „Speicherplatz“ sie während ihres Laufs beanspruchen. Durch den Wechsel zu einer „Smallest Volume First“-Strategie, und sogar durch die Nutzung einer super-simplen „kurz vs. lang“-Vermutung, können wir KI-Chatbots schneller, reibungsloser und weniger anfällig für Abstürze unter hoher Last machen.

Technisches Resümee: Geometrie-bewusstes Online-Scheduling für das LLM-Serving

Problemstellung

Die Bereitstellung von Large Language Models (LLMs) in interaktiven Szenarien steht vor einem kritischen Engpass: der Verwaltung des dynamischen Speicher-Footprints des Key-Value (KV)-Caches. Im Gegensatz zu traditionellen Scheduling-Problemen, bei denen die Jobgröße statisch ist, weist die LLM-Inferenz eine einzigartige 2D-spatio-temporale geometrische Wachstumscharakteristik auf:

Kopplung von Speicher und Zeit: In der autoregressiven Dekodierung ist die Ausführungszeit linear mit der Speichererweiterung gekoppelt; jedes generierte Token erhöht den KV-Cache-Footprint.
Dynamik des Continuous Batching: Moderne Engines (z. B. vLLM) nutzen Continuous Batching, wobei die gleichzeitige Batch-Größe nach jedem Dekodierungsschritt dynamisch fluktuiert, wenn Anfragen abgeschlossen werden und neue hinzukommen.

Bestehende Scheduling-Heuristiken, primär Shortest Job First (SJF), sind in der klassischen zeitzentrierten Modellierung verwurzelt. Sie versäumnen es, die geometrische Realität des LLM-Servings zu erfassen. Jüngste theoretische Arbeiten [10] haben gezeigt, dass unter diesen spezifischen geometrischen Bedingungen SJF ein unbeschränktes Worst-Case-Competitive-Ratio liefert, was eine fundamentale Lücke zwischen der klassischen Scheduling-Theorie und der physischen Realität moderner LLM-Inferenz schafft.

Methodik

Die Autoren schlagen ein Geometrie-bewusstes Online-Scheduling-Framework vor, das die Priorisierungsmetrik von der 1D-Ausführungszeit zur 2D-Speichervolumen verschiebt.

Kernalgorithmus: Smallest Volume First (SVF)

Anstatt die Ausführungszeit isoliert zu betrachten, evaluiert SVF das Integral des Speicherverbrauchs über den gesamten Lebenszyklus einer Anfrage. Für eine Anfrage $r_i$ mit Prompt-Länge $s_i$ und Output-Länge $o_i$ ist das Volumen $v_i$ definiert als:
$v_i = s_i \cdot o_i + \frac{o_i^2 + o_i}{2}$
Diese Formel quantifiziert die gesamte „Speicher-Zeit-Fläche“, die von der Anfrage eingenommen wird. SVF fungiert als streng gierige (greedy) Policy, die Anfragen in aufsteigender Reihenfolge ihrer $v_i$ sortiert. Die Implementierung ist in zwei Prozesse entkoppelt: einen Hintergrund-Prädiktor, der Anfragen bündelt, um Output-Längen abzufragen, und einen Scheduler, der die höchstpriorisierten (kleinstvolumigen) Anfragen in den laufenden Batch aufnimmt, bis die KV-Cache-Kapazität erreicht ist.

Leichtgewichtige Variante: 1-Bit SVF

Um den Rechenaufwand zu minimieren, führen die Autoren 1-bit SVF ein. Diese Variante ersetzt die exakte Längenprognose durch einen binären Klassifikator, der Anfragen als „kurz“ ( $m=0$ ) oder „lang“ ( $m=1$ ) kategorisiert.

Es weist jeder Klasse eine globale Proxy-Länge $O_m$ zu.
Das Proxy-Volumen wird berechnet als $\hat{v}_i = s_i \cdot O_m + \frac{O_m^2 + O_m}{2}$ .
Dieses Design extrahiert lediglich ein einzelnes Bit an Information und bewahrt dennoch die Kern-Garantien des spatio-temporalen Schedulings.

Theoretische Beiträge

Die Arbeit liefert eine rigorose mathematische Grundlage, die über empirisches Trial-and-Error hinausgeht und formale Garantien bietet:

Verdichtete Worst-Case-Grenzen (Burst-Arrivals):
- Für SVF mit bekannten Output-Längen unter Burst-Arrival-Modellen beweisen die Autoren ein Worst-Case-Competitive-Ratio (CR) von CR $\le$ 5. Dies verdichtet signifikant die zuvor in der Literatur [10] gefundene Schranke von CR $\le$ 48.
- Der Beweis nutzt eine neuartige „makroskopische Zertifikat“-Methodik, die zeigt, dass jeder blockierte Schritt eine aktive Speichermasse $> M/2$ impliziert, wodurch die Wartezeit des Algorithmus direkt mit der Untergrenze des optimalen Offline-Schedules korreliert.
- Für 1-bit SVF ist das Competitive-Ratio durch $O(T)$ begrenzt, wobei $T$ die maximale Modelllänge ist, was beweist, dass das System selbst unter extremer Last stabil bleibt.
Stochastische Grenzen (Poisson-Arrivals):
- Unter Poisson-Ankunftsprozessen leitet die Arbeit erwartete Competitive-Ratios her.
- SVF erreicht $E[CR] \le 1 + \frac{4}{(1-\mu)(1-\rho)}$ , wobei $\mu$ sich auf die geometrische Verteilung der Längen bezieht und $\rho$ die Systemauslastung beschreibt.
- Die Leistungsdegradierung von 1-bit SVF wird durch eine „volumetrische Verzerrungsstrafe“ $\epsilon$ bestimmt, die exponentiell mit dem Klassifizierungsschwellenwert abnimmt und somit langfristige Stabilität gewährleistet.

Experimentelle Ergebnisse

Der Ansatz wurde als Plug-and-Play-Layer innerhalb von vLLM implementiert und auf Llama-3.1-8B und Llama-3.1-70B Modellen unter Verwendung von LMSYS-Chat und LongBench Workloads evaluiert.

Latenzreduktion: SVF erreichte konsistent die niedrigsten durchschnittlichen und Tail-Latenzen (P95) über alle Benchmarks hinweg und übertraf dabei FCFS, SJF und sogar Oracle-SJF (welches über perfektes zukünftiges Wissen der Längen verfügt) in speicherintensiven Szenarien (LongBench).
Durchsatz: SVF hielt einen höheren Durchsatz als SJF aufrecht. 1-bit SVF erreichte konkurrenzfähige Durchsatz- und Latenzwerte und übertraf oft SJF bei den Tail-Latenz-Metriken.
Overhead: Der Prognose-Overhead war vernachlässigbar. Der Full-Length-Prädiktor verbrauchte höchstens 0,06 % der End-to-End-Latenz, während der 1-bit Klassifikator $\le$ 0,01 % beanspruchte.
Fairness: Im Gegensatz zu klassischen Greedy-Heuristiken, die lange Jobs verhungern lassen (starvation), setzt die geometrie-bewusste Gier von SVF schnell begrenzte KV-Cache-Speicher frei, wodurch globales Head-of-Line-Blocking durchbrochen und die Fairness für größere Anfragen verbessert wird.

Bedeutung und Ansprüche

Die Arbeit beansprucht, einen theoretisch fundierten und empirisch bewiesenen Ansatz zur Lösung des speicherbeschränkten Schedulings in modernen LLM-Deployments etabliert zu haben. Ihre primäre Bedeutung liegt in:

Paradigmenwechsel: Sie verschiebt das Feld von veralteten 1D-zeitzentrierten Heuristiken hin zu 2D-geometrie-bewusster Priorisierung und adressiert damit die fundamentale Diskrepanz zwischen klassischer Scheduling-Theorie und der Mechanik der LLM-Inferenz.
Theoretische Fortentwicklung: Durch die Verdichtung des Competitive-Ratio von 48 auf 5 und die Einführung einer neuartigen Beweismethodik bietet sie universelle strukturelle Garantien, die über beliebige und adversarielle Workload-Verteilungen hinweg Bestand haben.
Praktische Umsetzbarkeit: Die „Plug-and-Play“-Natur des Schedulers, kombiniert mit der extremen Effizienz der 1-Bit-Variante, zeigt, dass rigoröse mathematische Optimierung nahtlos in Hochleistungs-Inferenz-Engines integriert werden kann, ohne prohibitive Kosten zu verursachen.

Die Autoren schließen, dass dieser geometrie-bewusste Ansatz nicht nur die Systemeffizienz optimiert, sondern auch Auswirkungen auf eine nachhaltige KI-Bereitstellung hat, indem er die für groß angelegte Inferenz erforderlichen Rechenressourcen und den CO2-Fußabdruck reduziert.