💻 computer science

Beyond Prediction: Tail-Aware Scheduling for LLM Inference

Dieses Paper stellt ein distributionsbewusstes, prädiktionsfreies Scheduling-Framework vor, das durch Soft Priority Boosting und Cache-bewusste Präemption die Tail-Latenz sowie die Time-to-First-Token bei der LLM-Inferenz signifikant reduziert und dabei traditionelle prädiktionsbasierte Policies selbst unter anspruchsvollen Bedingungen wie burstartigen Ankünften und GPU-Speicherdruck übertrifft.

Ursprüngliche Autoren: Yueying Li, Yuanfan Chen, Jiayang Chen, Esha Choukse, Haoran Qiu, G. Edward Suh, Rodrigo Fonseca, Ziv Scully, Udit Gupta

Veröffentlicht 2026-06-19

📖 4 Min. Lesezeit☕ Kaffeepausen-Lektüre

CC BY 4.0

Ursprüngliche Autoren: Yueying Li, Yuanfan Chen, Jiayang Chen, Esha Choukse, Haoran Qiu, G. Edward Suh, Rodrigo Fonseca, Ziv Scully, Udit Gupta

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 eine geschäftige Restaurantküche vor, in der Köche (die GPUs) Mahlzeiten für Kunden (die KI-Anfragen) zubereiten. Einige Bestellungen sind einfach: „Nur ein Glas Wasser“ (eine kurze Chat-Nachricht). Andere sind komplex: „Entwirf einen 50-seitigen Roman mit einer detaillierten Handlung“ (eine lange Denkaufgabe).

Das Problem ist, dass der Küchenmanager nicht weiß, wie lange eine Bestellung dauern wird, bis sie fast fertig ist. Ein „Glas Wasser“ kann sich in ein „10-Gänge-Menü“ verwandeln, wenn der Kunde immer weiter nachfragt.

Der alte Weg: Die Zukunft erraten

Heutige Küchenmanager versuchen, effizient zu sein, indem sie raten, wie lange eine Bestellung dauern wird. Sie verwenden eine Strategie namens „Shortest Job First“ (SJF).

Die Logik: „Ich denke, diese Bestellung wird schnell gehen, also koche ich sie zuerst, um sie vom Tisch zu bekommen.“
Der Fehler: Wenn der Manager falsch rät (was bei komplexen KI-Aufgaben oft passiert), wird die schnelle Bestellung verzögert, und die lange Bestellung, die eigentlich als „kurz“ geplant war, beansprucht den Herd ewig für sich allein.
Das Ergebnis: Die durchschnittliche Wartezeit sieht akzeptabel aus, aber die Worst-Case-Wartezeiten (die Tail-Latenz) sind schrecklich. Einige Kunden warten Stunden, während andere in Sekunden bedient werden. Das ist schlecht für das Nutzererlebnis.

Der neue Weg: Das „Boost“-System (UNIBOOST)

Die Autoren dieser Arbeit schlagen einen neuen Manager vor, der aufhört zu raten und stattdessen anfängt zu beobachten. Sie nennen ihr System UNIBOOST.

So funktioniert es, unter Verwendung einfacher Analogien:

1. Der „Soft Boost“ (Keine Kristallkugeln nötig)

Anstatt zu versuchen, die Zukunft vorherzusagen, gibt der neue Manager jeder Bestellung einen „Prioritätswert“, der sich im Laufe der Zeit stetig verändert.

Die Analogie: Stellen Sie sich eine Schlange von Menschen vor, die auf eine Fahrt warten. Der neue Manager fragt nicht: „Wie weit fahren Sie?“ Stattdessen sagt er: „Je länger Sie schon warten, desto mehr erhält Ihr Ticket einen kleinen ‚Boost‘ in der Priorität.“
Wie es hilft: Kurze Bestellungen werden schnell bedient, weil sie zuerst ankommen. Aber wenn eine lange Bestellung schon eine Weile wartet, erhält sie einen sanften Schubs nach vorne, damit sie nicht hinter einem endlosen Strom neuer, kurzer Bestellungen stecken bleibt. Dies verhindert, dass die „lange Schlange“ der Kunden ewig warten muss.

2. Der „Memory Guard“ (Verschwenden Sie nicht die Pfanne)

In der KI erfordert das Kochen einer Mahlzeit viel Speicher (den KV-Cache). Wenn man das Kochen einer Mahlzeit mittendrin unterbricht, um zu einer neuen zu wechseln, muss man die gerade vorbereiteten Zutaten wegwerfen und von vorne beginnen. Das ist teuer und langsam.

Die Analogie: Stellen Sie sich vor, ein Koch ist gerade dabei, einen riesigen Kuchen zu backen. Wenn der Manager ruft: „Stopp! Backe stattdessen einen Keks!“, muss der Koch den Kuchenteig aus der Pfanne kratzen, die Pfanne waschen und erst dann mit dem Keks beginnen. Wenn er dann wieder zurückwechselt, muss er die Pfanne erneut waschen.
Die Lösung: Der neue Manager nutzt einen „Memory Guard“. Er sagt: „Soblich du angefangen hast, einen Kuchen zu backen, musst du mindestens ein ‚Stück‘ davon fertigstellen, bevor wir überhaupt über einen Wechsel nachdenken.“ Dies verhindert, dass die Küche ständig die Aufgaben wechselt und dadurch Zeit verschwendet.

3. Der „Adaptive Thermostat“

Die Bedingungen in der Küche ändern sich. Manchmal gibt es einen Ansturm kleiner Bestellungen; manchmal sind es ein paar massive Bestellungen.

Die Analogie: Der Manager hat einen intelligenten Thermostaten, der beobachtet, wie lange die Leute tatsächlich warten. Wenn die Schlange zu lang wird, passt der Manager den „Boost“ automatisch an, um aggressiver dabei zu helfen, die Menschen zu unterstützen, die schon am längsten warten. Er lernt im laufenden Betrieb, ohne eine Kristallkugel zu benötigen.

Die Ergebnisse

Die Arbeit testete dieses neue System gegen die alten „Rate-Systeme“ unter Verwendung realer Daten (wie Programmieraufgaben und Chat-Gespräche).

Die alten Systeme: Wenn die Arbeitslast extrem wurde (bursty), versagten die „Rate-Systeme“. Die Worst-Case-Wartezeiten (P99) wurden riesig.
Das neue System (UNIBOOST): Es verbesserte nicht nur die durchschnittliche Wartezeit, sondern senkte drastisch die schlechtesten Wartezeiten (P99).
- Es reduzierte die Worst-Case-Wartezeit (P99) im Vergleich zu den besten „perfekten Vorhersage“-Systemen um 35 % bis 50 %.
- Es machte das Erscheinen des ersten Tokens (TTFT) 34 % bis 47 % schneller.

Das Fazit

Die Arbeit argumentiert, dass der Versuch, vorherzusagen, wie lange eine KI-Aufgabe dauern wird, fragil ist und oft falsch liegt. Stattdessen schafft ein System, das darauf reagiert, wie lange Aufgaben bereits warten – während es gleichzeitig darauf achtet, den Speicher nicht durch zu häufige Aufgabenwechsel zu verschwenden –, ein viel faireres und schnelleres Erlebnis für alle. Es geht darum, den Fluss der Schlange zu managen, nicht das Ziel zu erraten.

Technisches Resümee: Beyond Prediction: Tail-Aware Scheduling for LLM Inference

1. Problemstellung

Das Serving von Large Language Models (LLMs) steht vor der kritischen Herausforderung, die extreme Variabilität in der Anfragelänge zu bewältigen, insbesondere durch den Aufstieg von reasoning-augmentierten Modellen, die mehrstufige Generierung, Selbstreflexion und adaptive Terminierung aufweisen. Diese Variabilität macht größenbasierte Scheduling-Policies (wie Shortest Job First – SJF oder Shortest Remaining Processing Time – SRPT) fragil.

Aktuelle State-of-the-Art-Scheduler verlassen sich auf die Vorhersage von Ausgabelängen oder verbleibenden Token, um SJF/SRPT zu approximieren. Das Paper identifiziert jedoch drei fundamentale Probleme mit diesem Ansatz:

Vorhersage-Fragilität (Prediction Fragility): Die Vorhersage der Ausgabelänge ist aufgrund der hohen Varianz in der Token-Generierung (Stochastik und Nicht-Determinismus) inhärent schwierig, was Policies unter Verteilungsverschiebungen und stoßartigen Ankünften instabil macht.
Metrik-Mismatch (Metric Mismatch): Policies, die auf mittlere Latenz optimiert sind (z. B. mittlere TTFT/TBT), weisen oft ein schlechtes Tail-Latency-Verhalten (P90–P99) auf. Beim LLM-Serving wird das Nutzererlebnis durch Tail-Latenzen (Time-To-Last-Token, TTLT) bestimmt, die oft die bindende Randbedingung für Service Level Objectives (SLOs) darstellen.
Speichergekoppelte Dynamik (Memory-Coupled Dynamics): Im Gegensatz zu klassischen Warteschlangen ist LLM-Inferenz zustandsbehaftet. Anfragen akkumulieren während des Decodings große Key-Value (KV)-Caches. Naive Präemption zur Priorisierung kurzer Jobs kann zu teurer Cache-Eviction, Recomputation und „Thrashing“ führen, was die Tail-Latenz trotz Reduzierung der Warteschlangenverzögerung potenziell erhöht.

Die zentrale Frage lautet: Benötigen Scheduler explizite Job-Längen-Vorhersagen, um die Tail-Latenz zu optimieren? Die Autoren argumentieren, dass dies nicht der Fall ist, und schlagen stattdessen einen distributionsbewussten, vorhersagefreien Ansatz vor.

2. Methodik: UNIBOOST

Das Paper stellt UNIBOOST vor, ein distributionsbewusstes, vorhersagefreies Scheduling-Framework, das die explizite Längenvorhersage durch „sanftes“ Priority Boosting ersetzt, das auf leichtgewichtigen statistischen Signalen basiert. Das Design ist eine Co-Optimierung von Scheduling und Cache-bewusster Präemption, strukturiert in vier Phasen:

Phase 1: Strawman (DISTBOOST)

Der initiale Ansatz behandelt Prefill- und Decode-Phasen als getrennte Probleme. Er verwendet eine $\gamma$ -Boost Prioritätsfunktion (inspiriert durch Warteschlangentheorie) für Prefill-Anfragen, priorisiert jedoch die Decode-Warteschlange. Dies verbessert zwar die Tail-Metriken für das Decoding, leidet aber unter Head-of-Line (HoL) Blocking, bei dem Prefill-Anfragen durch lang laufende Decode-Jobs ausgehungert werden.

Phase 2: Unified Prioritization (UNIBOOST-BASE)

Um das HoL-Blocking zu adressieren, vereinigt das Team die Prefill- und Decode-Warteschlangen in einem einzigen Prioritätsraum.

Prioritäts-Score: Anfragen werden basierend auf $\phi_i(t) = a_i - b_\gamma(\tilde{w}_i(t))$ bewertet, wobei $a_i$ die Ankunftszeit ist und $\tilde{w}_i(t)$ die effektive Arbeit (das Maximum aus erbrachter Arbeit und Prefill-Länge) darstellt.
Boost-Funktion: $b_\gamma(w) = \frac{1}{\gamma} \log(\frac{1}{1 - e^{-\gamma w}})$ . Diese Funktion bietet einen „sanften“ Prioritäts-Boost für Anfragen mit weniger erbrachter Service, wodurch die harte Präemption eines klassischen SRPT vermieden wird.
Mechanismus: Der Scheduler wählt die Anfrage mit dem minimalen Score aus, was eine Präemption über die Phasen hinweg ermöglicht, jedoch kontrolliert durch einen Hystereseparameter, um Oszillationen zu verhindern.

Phase 3: Stabilität durch MEMGUARD (KV-Aware Hysteresis)

Um die hohen Kosten der KV-Cache-Eviction und Recomputation zu mildern, führen die Autoren MEMGUARD ein.

Quantisierte Prioritäten: Anstatt Prioritäten kontinuierlich zu aktualisieren, diskretisiert das System die Metrik der erbrachten Arbeit ( $\hat{w}_i$ ) mittels geometrischer Quantisierung (z. B. Schwellenwerte bei $k, 2k, 4k...$ ).
Minimum Run: Sobald eine Anfrage disponiert wurde, kann sie nicht mehr evictet werden, bis ihre erbrachte Arbeit den nächsten Quantisierungsschwellenwert überschreitet. Dies amortisiert die Kosten der KV-Bewegung und begrenzt die Anzahl der Präemptionsmöglichkeiten auf eine logarithmische Bindung relativ zur Job-Länge.

Phase 4: Adaptive Parameter Estimation ( $\gamma$ -Ada)

Der Boost-Parameter $\gamma$ beeinflusst das Tail-Verhalten signifikant. Ein statisches $\gamma$ ist unter variierenden Lasten suboptimal.

Online-Schätzung: Das System schätzt eine effektive Tail-Steigung ( $\gamma_{eff}$ ), indem es eine log-lineare Steigung an den oberen Teil der beobachteten Antwortzeitverteilung (zwischen P95 und P99) anpasst.
Adaption: Der Scheduler passt $\gamma$ dynamisch an, um zwischen FCFS (zum Schutz des Tails) und LAS (zur Optimierung des Mittelwerts) zu interpolieren und sich so ohne explizite Vorhersage an Workload-Shifts anzupassen.

3. Zentrale Beiträge

Vorhersagefreie Tail-Optimierung: Es wird gezeigt, dass keine explizite Job-Längen-Vorhersage erforderlich ist, um die Tail-Latenz zu optimieren. Stattdessen genügen leichtgewichtige statistische Signale und sanftes Boosting.
Co-Design von Scheduling und Eviction: Es wird ein Framework eingeführt, das Scheduling-Entscheidungen und KV-Cache-Management gemeinsam optimiert. Durch die Kopplung von Boost-basiertem Scheduling mit Eviction-bewusster Ausführungskontrolle (MEMGUARD) vermeidet das System die Leistungsdegradierung durch Cache-Thrashing.
Robustheit gegenüber Verteilungsverschiebungen: Die vorgeschlagene Methode passt sich an variierende Workloads (Heavy-Tailed vs. Light-Tailed, Reasoning vs. Chat) an, ohne Retraining oder komplexe Vorhersagemodelle.
Theoretische Fundierung: Die Anpassung der $\gamma$ -Boost-Policy aus der Warteschlangentheorie an die spezifischen Constraints der LLM-Inferenz (Zustandshaftigkeit, Speicherkopplung).

4. Experimentelle Ergebnisse

Evaluierung auf Produktions- und Open-Source-Traces (Azure, ShareGPT, S1K) mit Modellen wie Llama-3-8B, CodeLlama-34B und Qwen-72B auf NVIDIA A100 GPUs:

Reduktion der Tail-Latenz: UNIBOOST erreicht eine um 35–50 % niedrigere P99 TTLT im Vergleich zu SRPT mit perfekter Längenvorhersage (TRAIL+). Es reduziert zudem die P99 TTFT über verschiedene Workloads hinweg um 34–47 %.
Durchsatz: Die Methode verbessert den Durchsatz unter stoßartigen Lasten um den Faktor 1,01–1,12 $\times$ im Vergleich zu den Baselines.
SLO-Einhaltung: UNIBOOST ermöglicht es Systemen, 2,9–8,7 $\times$ strengere SLOs für die TTFT zu tolerieren und dabei im Vergleich zu SJF-basierten Ansätzen eine 99%ige Einhaltung beizubehalten.
Ablationsstudien:
- Das Entfernen der vereinheitlichten Priorität (Phase 2) führt zu Prefill-Starvation.
- Das Entfernen von MEMGUARD (Phase 3) verursacht signifikante Tail-Latenz-Spikes durch KV-Thrashing.
- Das Entfernen des adaptiven $\gamma$ (Phase 4) reduziert die Robustheit unter Lastwechseln.
Vergleich: Die Methode übertrifft State-of-the-Art-Baselines wie vLLM's Sarathi (Chunked Prefill), LTR (Learning-to-Rank SJF) und TRAIL (Vorhersage-basiertes SRPT), insbesondere bei reasoning-intensiven Workloads, in denen Vorhersagen am unzuverlässigsten sind.

5. Bedeutung und Ansprüche

Das Paper behauptet, dass UNIBOOST eine robuste Alternative zu vorhersageintensiven Scheduling-Policies für das Online-LLM-Serving bietet. Die Bedeutung liegt in:

Entkopplung von der Vorhersage: Es eliminiert die Abhängigkeit von präziser Längenvorhersage, was einen Hauptengpass in reasoning-starken und variabel-langen Workloads darstellt.
Ganzheitliche Optimierung: Es adressiert gleichzeitig den „Mean vs. Tail“-Trade-off und den „Scheduling vs. Memory“-Trade-off und bietet eine Lösung, die auch dann effektiv ist, wenn die Vorhersagequalität sinkt.
Praktikabilität: Das Design ist einfach in bestehende Continuous-Batching-Stacks (wie vLLM und SGLang) zu integrieren und stützt sich auf leichtgewichtige Runtime-Statistiken statt auf komplexe ML-Modelle.

Die Autoren kommen zu dem Schluss, dass eine distributionsbewusste, eviction-bewusste Scheduling-Strategie essenziell für die nächste Generation des LLM-Servings ist, insbesondere da Modelle zunehmend in der Lage sind, variable Längen im Reasoning-Bereich zu generieren.