ProServe: Unified Multi-Priority Request Scheduling for LLM Serving

ProServe ist ein vereinheitlichtes zweistufiges Scheduling-Framework, das den Gesamtnutzen des Service durch die gemeinsame Optimierung der SLO-Einhaltung und klientenspezifischer Prioritäten mittels dynamischer Batch-Bildung, effizienter Blockverwaltung und gewinnorientierter Request-Verteilung maximiert.

Das Wesentliche

Stellen Sie sich eine geschäftige Restaurantküche vor, die von einem Large Language Model (LLM) betrieben wird. In dieser Küche bereiten Köche (die Computerprozessoren) ständig Antworten für Tausende von Kunden gleichzeitig zu.

Das Problem, das die Arbeit adressiert, ist, dass nicht alle Kunden gleich sind. Es gibt VIPs (geschäftskritische Kunden), die extra bezahlen, damit ihr Essen sofort eintrifft. Und es gibt reguläre Kunden. Zudem sind manche Bestellungen einfach (ein schnelles Toastbrot), während andere komplex sind (ein Fünf-Gänge-Menü).

Bestehende Küchenmanager (Scheduling-Systeme) waren schlecht darin, diesen Mix zu handhaben. Sie behandeln entweder alle exakt gleich (was dazu führt, dass VIPs zu lange warten müssen) oder sie schauen nur darauf, wer zuerst bestellt hat (was die Küche ineffizient macht).

ProServe ist ein neuer, superintelligenter Küchenmanager, der genau dies lösen soll. So funktioniert er, unterteilt in einfache Teile:

1. Das Ziel: Maximierung der „Glückspunkte“

Anstatt nur zu versuchen, Bestellungen so schnell wie möglich fertigzustellen, versucht ProServe, den „Service Gain“ zu maximieren.

• Die Analogie: Stellen Sie sich vor, jeder Kunde hat einen „Glücksmesser“.
  • Wenn ein VIP sein Essen rechtzeitig bekommt, schenkt er dem Restaurant 10 Glückspunkte.
  • Wenn ein regulärer Kunde sein Essen rechtzeitig bekommt, schenkt er 5 Punkte.
  • Wenn das Essen eines VIPs zu spät kommt, gibt er 0 Punkte (und hinterlässt vielleicht eine schlechte Bewertung).
• Die Behauptung der Arbeit: Das Ziel des Systems ist nicht nur Schnelligkeit; es geht darum, die Reihenfolge des Kochens so zu arrangieren, dass die höchste Gesamtzahl an Glückspunkten von allen Beteiligten kombiniert wird. Es wertet die Zeit des VIPs mehr als die des Regulären, versucht aber dennoch, die Regulären zufrieden genug zu halten, um im Spiel zu bleiben.

2. Der lokale Manager: „SlideBatching“ (Die smarte Aufstellung)

Innerhalb der Küche befindet sich eine Schlange von Bestellungen, die darauf warten, gekocht zu werden. Ein normaler Manager würde vielleicht einfach sagen: „Wer zuerst kommt, mahlt zuerst.“ ProServices lokaler Manager nutzt eine Sliding Window-Strategie (Gleitendes Fenster).

• Die Analogie: Stellen Sie sich vor, die Warteschlange der Kunden befindet sich auf einem Laufband.
  • Wenn die Küche langsam ist (Niedrige Auslastung): Lässt der Manager alle in der Schlange in einer entspannten Reihenfolge kochen. Jeder bekommt sein Essen.
  • Wenn die Küche überrannt ist (Hohe Auslastung): Schaut der Manager auf das Laufband und sieht, dass einige Kunden kurz davor sind, ihre „Hunger-Deadline“ zu verpassen.
  • Das Gleiten: Der Manager verschiebt eine Grenze. Jeder vor der Linie wird als „dringend“ markiert. Der Manager priorisiert diese dringenden Kunden. Aber hier ist der Trick: Unter den Dringenden wählt er nicht einfach blind die VIPs aus. Er wählt diejenigen, die „dicht“ sind (kurz und schnell zu kochen), um die Schlange schnell abzuarbeiten, während er gleichzeitig sicherstellt, dass die VIPs bedient werden, bevor ihre Zeit abläuft.
• Die Behauptung der Arbeit: Dieses dynamische Verschieben ermöglicht es dem System, plötzliche Verkehrsspitzen zu bewältigen, ohne dass jemand hungern muss oder seine Fristen versäumt, wodurch die gesamte „Glückspunkte“-Summe maximiert wird.

3. Der Speicher-Manager: „Async Offloading“ (Das Förderband)

Manchmal geht in der Küche der Platz auf der Arbeitsplatte aus (GPU-Speicher). Wenn dies passiert, muss die Küche einige Zutaten in ein Lagerhaus (Host-Speicher) auslagern, um Platz für neue Bestellungen zu schaffen.

• Die Analogie: Normalerweise muss man, wenn man Zutaten in das Lagerhaus bewegt, den Kochvorgang stoppen und warten, bis ein Läufer sie zurückbringt. Das stoppt die gesamte Küche.
• Die Lösung von ProServe: Es nutzt ein pipelined Förderband.
  • Während die Köche die aktuelle Schicht eines Gerichts kochen, holt ein Läufer gleichzeitig die Zutaten für die nächste Schicht aus dem Lagerhaus.
  • Es verfügt außerdem über ein „Copy-Budget“. Es bewegt nur so viel, wie es bewältigen kann, ohne die Köche auszubremsen. Wenn die Küche super beschäftigt ist, bewegt es weniger; wenn es ruhig ist, bewegt es mehr.
• Die Behauptung der Arbeit: Dies stellt sicher, dass das Bewegen von Zutaten (Memory Swapping) den Kochprozess niemals unterbricht und die Küche auch bei hoher Auslastung reibungslos weiterläuft.

4. Der globale Manager: „GoRouting“ (Der smarte Gastgeber)

Wenn das Restaurant über mehrere Küchen verfügt (mehrere Server), muss ein Gastgeber entscheiden, welche Küche die neue Bestellung erhält.

• Die Analogie: Ein dummer Gastgeber schickt die Bestellung einfach an die Küche mit den wenigsten Menschen in der Schlange (Least Load).
  • Das Problem: Wenn der Gastgeber eine kleine Bestellung an eine Küche schickt, die gerade frei ist, könnte diese Küche später mit einer riesigen, langen Bestellung feststecken, die sie nicht bewältigen kann, was zu einer Verzögerung führt.
• Die Lösung von ProServe: Der Gastgeber ist kapazitätsbewusst (Capability-Aware).
  • Er schaut sich die Küchen an und fragt: „Wenn ich diese VIP-Bestellung hierher schicke, wird diese Küche dann noch genug Platz und Zeit für eine potenzielle zukünftige große Bestellung haben?“
  • Er schickt eine kleine Bestellung vielleicht an eine Küche, die bereits etwas belebter ist, nur um den „leeren Raum“ in der anderen Küche für eine zukünftige VIP- oder eine lange, komplexe Bestellung aufzusparen.
• Die Behauptung der Arbeit: Dies verhindert, dass das System durch schlechte Entscheidungen „verstopft“ wird, und stellt sicher, dass hochpriorisierte Anfragen immer untergebracht werden können.

Die Ergebnisse

Die Autoren haben ProServe mit realen Daten getestet (einschließlich eines massiven industriellen Datensatzes aus ihrem eigenen Unternehmen). Sie fanden heraus:

• Es steigerte die gesamte „Glückseligkeit“ (Systemgewinn) um bis zu 35 %.
• Es stellte sicher, dass Kunden ihre Fristen (SLO-Einhaltung) bis zu 52 % häufiger einhielten als die besten bestehenden Systeme.

Kurz gesagt: ProServe ist ein Scheduling-System, das verschiedene Kunden basierend auf ihrem Wert unterschiedlich behandelt, smarte Aufstellungs-Tricks nutzt, um Menschenmassen zu bewältigen, Zutaten während des Kochens bewegt, um Zeit zu sparen, und kluge Entscheidungen darüber trifft, welche Küche genutzt wird, um sicherzustellen, dass das gesamte Restaurant effizient arbeitet.

Technische Zusammenfassung

Technisches Resümee: ProServe – Einheitliches Multi-Prioritäts-Request-Scheduling für das LLM-Serving

1. Problemstellung

Die weitverbreitete Bereitstellung von Large Language Models (LLMs) für interaktive Anwendungen erfordert Serving-Systeme, die in der Lage sind, tausende von gleichzeitigen Anfragen mit heterogenen Service Level Objective (SLO)-Anforderungen zu verarbeiten. Eine kritische, oft übersehene Dimension ist der inhärente Prioritätsunterschied zwischen Clients. In realen Unternehmensszenarien erfordern geschäftskritische Funktionen höhere Leistungsgarantien als nicht-kritische Funktionen, und die Erfüllung hochpriorisierter Anfragen liefert einen signifikant höheren Geschäftswert.

Bestehende LLM-Serving-Scheduler versäumen es, sowohl die SLO-Erfüllung als auch die Client-Level-Prioritäten gemeinsam zu optimieren:

• Fokus auf SLO-Heterogenität: Einige Arbeiten priorisieren Anfragen mit engeren Deadlines, ignorieren jedoch die inhärenten Unterschiede in der Client-Priorität.
• Online/Offline Co-Scheduling: Andere behandeln alle Online-Anfragen als einheitlich hochpriorisiert und Offline-Aufgaben als Best-Effort, was jedoch nicht anwendbar ist, wenn sowohl hoch- als auch niedrigpriorisierte Anfragen spezifische Latenzanforderungen haben.
• Prioritätsbewusst, aber SLO-blind: Einige Ansätze berücksichtigen zwar die Client-Priorität, verfügen aber über keine expliziten pro-Request-Latenzgarantien (z. B. statische Speicherreservierung) oder erzwingen eine Token-basierte Fairness, die strikte Latenzziele nicht erfüllen kann.

Die Kernherausforderung besteht darin, ein Framework zu entwerfen, das gleichzeitig pro-Request-SLOs (TTFT und TPOT) respektiert und den Service basierend auf der Client-Priorität differenziert, um den gesamten System-„Service Gain“ zu maximieren.

2. Methodik

Die Autoren schlagen ProServe vor, ein einheitliches zweistufiges Scheduling-Framework, das darauf ausgelegt ist, den Service Gain aus Multi-Prioritäts-Requests zu maximieren. Das System arbeitet sowohl in PD-kohälozierten (Prefill-Decode) als auch in PD-disaggregierten Deployments.

2.1 Formalisierung: Token-level Deadline-aware Gain (TDG)

Um das Ziel zu quantifizieren, formalisieren die Autoren das Problem als Maximierung des Service Gain. Sie führen eine neuartige Gain-Funktion ein, TDG, die die Einschränkungen früherer Ansätze (z. B. den „Discard-or-Postpone“-Trick und die Unempfindlichkeit gegenüber der pro-Token-Latenz) adressiert.

• Mechanismus: TDG interpretiert den Gain als binären Indikator dafür, ob das Timing eines Tokens die Nutzererfahrung beeinträchtigt. Jedes Token hat eine feste Deadline, die sich aus den TTFT- und TPOT-SLOs der Anfrage ableitet.
• Formel: $f_{TDG}(r) = \sum_i w_r(i) \cdot \mathbb{I}[t_{r,i} < \text{deadline}_{r,i}]$, wobei Gewichte die Wichtigkeit des ersten Tokens gegenüber nachfolgenden Tokens unterscheiden, skaliert durch das Gewicht der Client-Priorität.
• Eigenschaften: TDG gewährleistet positive Monotonie (eine frühere Fertigstellung hilft nachfolgenden Tokens) und verhindert den „Infinite-Postpone“-Trick, da verspätete Tokens keinen Gain mehr liefern und die Zeit für nachfolgende Tokens reduzieren.

2.2 Engine-Layer: SlideBatching

Der lokale Batch-Scheduler, SlideBatching, passt seine Policy dynamisch basierend auf der Echtzeitlast an, um ein Gleichgewicht zwischen Latenz und Priorität zu finden.

• Adaptive Urgency Partition: Der Algorithmus unterteilt die Request-Queue in Urgent (gefährdet, Deadlines zu verpassen) und Normal Subsets. Die Grenze zwischen diesen Sets „gleitet“ (slides) bas in Abhängigkeit von der aktuellen Last.
• Scheduling-Strategie:
  • Urgent Requests: Werden in absteigender Reihenfolge der Dichte (Priority-Gewicht pro Einheit der Ausführungszeit) geplant, wobei das Problem als fraktionales Knapsack-Problem behandelt wird, um den unmittelbaren Gain zu maximieren.
  • Normal Requests: Werden in aufsteigender Reihenfolge der verbleibenden Zeit bis zur Deadline (Earliest Deadline First) geplant.
• Dynamisches Budget: Anstatt eines festen Token-Budgets setzt der Scheduler ein Zeit-Level-Latenzbudget ($\eta$) bas thereof der kleinsten verbleibenden Deadline, um sicherzustellen, dass kein Request im aktuellen Batch seine Deadline verpasst, sofern dies möglich ist.
• Verhindern von Starvation: Eine konfigurierbare Regel befördert Requests, die länger als ein Schwellenwert gewartet haben, an die Spitze der Warteschlange.

2.3 Engine-Layer: Effizientes Block-Management

Um den durch häufige Präemption von niedrigpriorisierten Requests verursachten KV-Cache-Druck zu bewältigen, nutzt ProServe:

• Asynchrones Offloading: KV-Blöcke werden asynchron in den Host-Speicher ausgelagert. Prioritätsbewusste Schwellenwerte lösen das Offloading für niedrigpriorisierte Requests häufiger aus.
• Pipelined Reloading: Wenn ein präemptierter Request neu geplant wird, werden die KV-Blöcke Schicht für Schicht parallel zur Berechnung neu geladen, um den Transfer-Overhead zu verbergen.
• Adaptive Copy-Budget Control: Das System bestimmt dynamisch die Anzahl der Blöcke, die pro Batch kopiert werden sollen. Es balanciert den Trade-off zwischen Rechenzeit und Transferzeit, um sicherzustellen, dass der Datentransfer nicht zum kritischen Pfad wird oder SLOs verletzt.

2.4 Service-Layer: GoRouting

Der globale Router, GoRouting, führt ein gain-orientiertes und fähigkeitsbewusstes Dispatching über verteilte Instanzen hinweg durch.

• Statusüberwachung: Er verfolgt Prefill-Queues, Decode-Counter und freie Block-Anzahlen pro Instanz.
• Gain-Orientiertes Dispatching: Anstatt einfachem Load Balancing (Min-Load) schätzt GoRouting den inkrementellen Gain der Aufnahme eines Requests in eine Kandidaten-Instanz.
• Capability-Aware Selection: Es verwendet eine Dual-Threshold-Policy, um Kapazitäten zu reservieren. Wenn eine Instanz gering belastet ist, wird sie ausgewählt, um Unterauslastung zu vermeiden. Wenn alle Kandidaten stark belastet sind, wird die am wenigsten belastete gewählt. Entscheidend ist, dass bei moderater Belastung der Kandidaten eine relativ schwerer belastete Instanz gewählt werden kann, um Kapazität auf leichteren Instanzen für zukünftige lange oder hochpriorisierte Requests zu reservieren, um SLO-Verletzungen bei zukünftigen Ankünften zu verhindern.

3. Kernbeiträge

1. Problemformalisierung: Definition des Multi-Prioritäts-Schedulings als Service-Gain-Maximierungsproblem und Vorschlag der TDG-Funktion zur Quantifizierung des prioritätsbasierten Gains unter Einhaltung der Token-Level-Deadlines.
2. SlideBatching: Einführung eines lokalen Schedulers, der die Anforderungsreihenfolge (Urgent vs. Normal) und die Batch-Kapazität dynamisch an die Echtzeitlast anpasst und so Latenz und Priorität effektiv ausbalanciert.
3. Effizientes Block-Management: Design eines Mechanismus mit asynchronem Offloading, pipelined Reloading und adaptiver Copy-Budget-Kontrolle, um den Host-Device-Transfer-Overhead während der Präemption zu minimieren.
4. GoRouting: Entwicklung eines globalen Routers, der durch gain-orientiertes, fähigkeitsbewusstes Dispatching proaktiv Kapazitäten für zukünftige hochpriorisierte oder lange Requests reserviert.
5. Empirische Validierung: Nachweis durch umfangreiche Experimente, dass ProServe State-of-the-Art-Baselines übertrifft.

4. Experimentelle Ergebnisse

Die Autoren evaluierten ProServe auf vier Open-Source-Datensätzen (ShareGPT, Azure, BurstGPT, QwenTrace) und einem großen industriellen Datensatz unter Verwendung von Qwen2-7B und Qwen3-32B Modellen auf Ascend 910B NPUs.

• System Gain: ProServe verbesserte den System-Gain (gemessen am TDG-Ratio) um bis zu 35 % im Vergleich zu State-of-the-Art-Baselines (einschließlich vLLM-FCFS, Weighted VTC, Sarathi-Priority und FairBatching).
• SLO-Erfüllung: ProServe steigerte die allgemeine SLO-Erfüllung um bis zu 52 %.
• Prioritätsbehandlung: Im Gegensatz zu „Priority-First“-Baselines, die niedrigpriorisierte Requests verhungern lassen (starvation), hält ProServe eine hohe SLO-Erfüllung für hochpriorisierte Requests aufrecht und hält gleichzeitig die Performance für niedrigpriorisierte Requests auf einem akzeptablen Niveau, wodurch ein besserer Trade-off erreicht wird.
• Skalierbarkeit: In groß angelegten Cluster-Experimenten (32 Instanzen) übertraf ProServe konsistent Round-Robin- und Min-Load-Baselines bei realen industriellen Workloads.
• Ablation: Das Entfernen einer Komponente (SlideBatching-Logik, Latenzschätzung oder Block-Management) führte zu einer Leistungsverschlechterung, was die Notwendigkeit des vollständigen Frameworks bestätigt.

5. Bedeutung

Das Paper behauptet, dass ProServe die Lücke zwischen SLO-Diversität und Client-Level-Prioritätsdifferenzierung im LLM-Serving schließt. Durch die Formalisierung des Problems als Maximierung des Service Gain und die Einführung eines einheitlichen zweistufigen Frameworks bietet ProServe einen prinzipienbasierten Ansatz für die Handhabung von Multi-Prioritäts-Workloads. Es zeigt, dass die gemeinsame Optimierung von Latenz und Priorität – anstatt sie als separate oder konkurrierende Ziele zu behandeln – zu einem signifikant höheren Geschäftswert und einer höheren Systemeffizienz führt. Die Arbeit adressiert einen kritischen Bedarf für Enterprise-LLM-Deployments, bei denen verschiedene Clients unterschiedliche Geschäftswerte und Leistungsanforderungen haben.