LLM Serving Optimization with Variable Prefill and Decode Lengths

Technische Zusammenfassung: Optimierung des LLM-Servings mit variablen Prefill- und Decode-Längen

Problemformulierung
Diese Arbeit adressiert das Offline-Scheduling-Problem für die Inferenz von Large Language Models (LLMs) auf einem einzelnen Rechenknoten mit einem festen Key-Value (KV)-Cache-Speicherbudget. Das System verarbeitet einen Rückstau von $n$ Anfragen, die gleichzeitig zum Zeitpunkt $t=0$ eintreffen. Jede Anfrage $i$ ist durch eine heterogene Prompt-Länge (Prefill-Größe, $s_i$) und eine Antwort-Länge (Decode-Größe, $o_i$) charakterisiert.

Die zentrale Herausforderung ergibt sich aus der dynamischen Natur des Speicherverbrauchs während des autoregressiven Decodings. Während die Prefill-Phase Speicher verbraucht, der proportional zu $s_i$ ist, wächst der Speicherverbrauch in der Decode-Phase linear mit jedem generierten Token ($s_i + j$ für das $j$-te Token). Folglich fluktuiert die Anzahl der gleichzeitig bearbeitbaren Anfragen eines Workers dynamisch basierend auf dem Fortschritt der Generierung aktiver Anfragen. Das Ziel ist es, die gesamte End-to-End-Latenz (Total End-to-End Latency, TEL) zu minimieren, definiert als die Summe der Abschlusszeiten aller Anfragen, unter der Bedingung, dass der aggregierte Speicherverbrauch eines Batches zu jedem Zeitschritt das Kapazitätslimit $M$ nicht überschreitet.

Die Autoren lockern die Annahme gleichförmiger Eingabegrößen, wie sie in vorangegangener Arbeit (Jaillet et al., 2025) gefunden wurde, und betrachten ein realistisches Szenario, in dem Workloads kurze Konversations-Prompts mit langen Dokumenten-Zusammenfassungen mischen.

Theoretische Erkenntnisse und Herausforderungen
Die Arbeit stellt fest, dass die Lockerung der Annahme gleichförmiger Eingabegrößen die Komplexität des Scheduling-Problems grundlegend verändert:

1. NP-Schwere: Das verallgemeinerte Scheduling-Problem mit heterogenen $s_i$ und $o_i$ wird mittels Reduktion auf das eingeschränkte 3-Partition-Problem als NP-schwer bewiesen.
2. Versagen Standard-Heuristiken: Es wird gezeigt, dass Standard-Policies, einschließlich First-Come-First-Served (FCFS), Shortest-Output-First (MC-SF) und Total-Size-Based Priorisierung, in diesem heterogenen Setting unbeschränkte Approximationsverhältnisse aufweisen. Speziell kann eine Anfrage mit einem großen Input, aber kleinem Output, kurzzeitig signifikanten Speicher beanspruchen, während eine Anfrage mit kleinem Input, aber langem Output, über einen längeren Zeitraum Speicher belegt; dies erzeugt Trade-offs, die einfache Heuristiken nicht auflösen können.

Methodik: Der Sorted-F Algorithmus
Um diese Herausforderungen zu adressieren, schlagen die Autoren Sorted-F vor, einen Scheduling-Algorithmus, der darauf ausgelegt ist, eine konstante Approximationsgarantie zu erreichen. Der Algorithmus operiert in zwei Phasen:

1. Batch-Konstruktion (Phase 1): Der Algorithmus wählt iterativ zulässige Batches von Anfragen aus, um eine geordnete Liste zu erstellen. Die Auswahl wird durch eine neuartige Qualitätsmetrik $F(X)$ geleitet, die für eine Anfrage-Menge $X$ definiert ist als:
   $$F(X) = \frac{\sum_{r_i \in X} o_i}{|X|^2}$$
   Diese Metrik balanciert die Batch-Größe ($|X|$) gegen die aggregierte nachgelagerte Decode-Kosten ($\sum o_i$) ab. Die Minimierung von $F(X)$ ist äquivalent zur Maximierung der „Durchsatzdichte“ (abgeschlossene Anfragen pro Einheit der durchschnittlichen Decode-Zeit). Innerhalb jedes ausgewählten Batches werden die Anfragen nach nicht-abnehmender Ausgabelänge sortiert.
2. Ausführung (Phase 2): Das System führt das Schedule über diskrete Zeitschritte aus, wobei es Anfragen aus der geordneten Liste in den aktuellen Batch aufnimmt, solange die Speicher-Machbarkeitsbedingungen erfüllt sind, unter Nutzung von Continuous Batching und Prefill/Decode-Mixing.

Approximationsgarantie
Die Autoren beweisen, dass Sorted-F eine konstante Approximationsrate von höchstens 48 im Verhältnis zum optimalen Offline-Schedule erreicht. Der Beweis umfasst eine Reihe struktureller Transformationen (Separation, Gruppierung und Ausrichtung), die den Sorted-F-Schedule und den optimalen Schedule in vergleichbare Formen überführen und zeigen, dass der Latenzanstieg bei jedem Schritt durch einen konstanten Faktor begrenzt ist.

Praktische Implementierungen
In Anerkennung der Tatsache, dass die kombinatorische Optimierung erforderlich in Phase 1 für große $n$ rechenintensiv ist, schlägt das Paper drei praktische Solver vor:

• Exakte Dynamische Programmierung: Liefert eine exakte Lösung für kleine Instanzen ($n \le 100$) mit einer Komplexität von $O(n^2 M)$.
• Local Swap Search: Eine Heuristik für mittlere Skalen ($n \le 500$), die eine initiale Greedy-Lösung durch paarweise Vertauschungen iterativ verbessert ($O(n^2)$).
• Quantile Greedy Selection: Eine lineare-Zeit-Heuristik ($O(n)$) für großskalige Systeme ($n \ge 1000$), die statistisches Sampling nutzt, um Ausreißer zu filtern und die Kapazität gierig zu füllen.

Zusätzlich führen die Autoren Sorted-LP ein, eine Heuristik, die die Lösung einer Linearen Programmierung (LP)-Relaxierung des Problems nutzt, um Anfragen zu ordnen, sowie Sorted-F+Amin, eine adaptive Variante, die die Unsicherheit der Vorhersage von Ausgabelängen handhabt, indem sie Schätzungen während der Inferenz dynamisch verfeinert.

Experimentelle Ergebnisse
Numerische Experimente mit gemischten Workloads (Kombination aus dem LMSYS-Chat-Datensatz und Arxiv-Langdokument-Zusammenfassungen) zeigen:

• Latenzreduktion: Sorted-F (unter Verwendung der Local Swap Search) übertrifft konsistent FCFS, MC-SF und LP-gestützte Baselines. In einem 80/20 Kurz/Lang-Gemisch mit 2000 Anfragen reduzierte Sorted-F die durchschnittliche Latenz um den Faktor 4,87 gegenüber FCFS und um den Faktor 2,09 gegenüber MC-SF.
• Optimalitätslücke: Auf handhabbaren Instanzen ist die empirische Lücke zwischen Sorted-F und der LP-Relaxation-Untergrenze gering (etwa 1,03–1,09), was darauf hindeutet, dass der Algorithmus in der Praxis nahezu optimal arbeitet, trotz der lockeren theoretischen Bindung.
• Workload-Sensitivität: Die Vorteile von Sorted-F sind in heterogenen, überlasteten Regimen am ausgeprägtesten, in denen der Speicher eine bindende Nebenbedingung darstellt. In homogenen oder leicht ausgelasteten Regimen nimmt der Vorteil ab.
• Online-Performance: Eine Receding-Horizon-Variante (Sorted-F-Online), die unter Poisson-Ankünften getestet wurde, zeigt signifikante Verbesserungen gegenüber MC-SF und FCFS in überlasteten Online-Regimen, bietet jedoch weniger Nutzen in stabilen, latenzarmen Regimen.

Bedeutung und Ansprüche
Das Paper behauptet, dass variable Prefill-Längen keine geringfügige Modellierungsdetails sind, sondern ein fundamentaler Faktor, der Standard-Scheduling-Heuristiken ineffektiv macht und das Problem NP-schwer macht. Der primäre Beitrag ist der Sorted-F Algorithmus, der die erste konstante Approximationsgarantie für das LLM-Scheduling unter heterogenen Input/Output-Beschränkungen liefert. Die Arbeit schließt die Lücke zwischen theoretischen Scheduling-Limits und praktischem LLM-Serving und bietet ein skalierbares, speicherbewusstes Framework, das die Latenz in gemischten Workload-Szenarien signifikant reduziert, ohne eine perfekte Vorhersage der Ausgabelängen zu erfordern. Die Autoren betonen, dass während die theoretische Schranke bei 48 liegt, die empirischen Ergebnisse darauf hindeuten, dass der Algorithmus in realistischen Settings viel näher an der optimalen Lösung liegt.