Technische Zusammenfassung: Ein Warteschlangentheoretisches Framework für die Stabilitätsanalyse von LLM-Inferenz mit KV-Cache-Speicherbeschränkungen

Problemstellung

Die rasche Verbreitung von Large Language Models (LLMs) hat erhebliche Herausforderungen für eine effiziente Inferenz im großen Maßstab geschaffen. Im Gegensatz zu traditionellen Arbeitslasten ist die LLM-Inferenz durch eine duale Engpasssituation eingeschränkt: die Rechenleistung und der Speicherbedarf durch Key-Value (KV)-Caching. Während KV-Caching die Dekodierung durch Wiederverwendung von Repräsentationen zuvor generierter Tokens beschleunigt, verbraucht es erheblichen GPU-Speicher und wird oft zur primären Kapazitätsbeschränkung.

Bestehende Warteschlangenmodelle für die LLM-Inferenz konzentrieren sich typischerweise auf Rechengrenzen oder behandeln Speicher als statische Beschränkung, wodurch sie das dynamische Zusammenspiel zwischen Berechnung und Speicherwachstum während des Inferenzprozesses nicht erfassen können. Spezifisch entwickelt sich der Speicherbedarf einer Anfrage, während sie durch die Prompt-Phase (Prefill) und die Token-Generierungsphase (Decode) fortschreitet, linear. Wenn die Ankunftsrate der Anfragen die effektive Service-Rate des Systems überschreitet – die gemeinsam durch GPU-Rechenleistung und verfügbaren KV-Cache-Speicher bestimmt wird –, wachsen die Warteschlangen unbegrenzt, was zu Systeminstabilität, inakzeptabler Latenz und einer verschlechterten Benutzererfahrung führt. Es fehlt an rigorosen theoretischen Frameworks, die diese dynamischen Speicherbeschränkungen explizit einbeziehen, um Stabilitätsbedingungen zu bestimmen und die GPU-Bereitstellung zu steuern.

Methodik

Die Autoren schlagen ein neuartiges warteschlangentheoretisches Framework vor, das die LLM-Inferenz als diskretzeitiges, arbeitsbewahrendes Warteschlangensystem modelliert, das einer harten KV-Cache-Speicherbeschränkung ($M$) unterliegt.

1. Systemmodell

• Anfragenstruktur: Jede Anfrage $i$ besteht aus einem Prompt der Größe $s_i$ und einer Antwort der Länge $o_i$, die aus einer gemeinsamen Verteilung $F_{in-out}$ gezogen werden.
• Verarbeitungsphasen:
  • Prompt-Phase: Prompts werden in festen Größenblöcken ($\hat{s}$) verarbeitet. Der Speicherbedarf für den $j$-ten Block eines Prompts wächst linear ($j \times \hat{s}$).
  • Decode-Phase: Während Tokens sequenziell generiert werden, erhöht sich der Speicherbedarf pro Schritt um den KV-Cache eines Tokens. Der gesamte Speicherbedarf einer Anfrage erreicht bei Abschluss $s_i + o_i$.
• Speicherbeschränkung: Das System muss zu jedem Zeitpunkt $t$ die Bedingung $\sum_{i \in S(t)} (c_i^{(t)}\hat{s} + d_i^{(t)}) \le M$ erfüllen, wobei $S(t)$ die Menge der aktiven Anfragen ist, $c_i^{(t)}$ der Index des verarbeiteten Prompt-Blocks und $d_i^{(t)}$ der Index des verarbeiteten Ausgabetokens.
• Planung: Das Framework setzt Continuous Batching und arbeitsbewahrende Strategien (z. B. First-Come-First-Served) voraus, wobei der Server den nächsten priorisierten Prompt verarbeitet, sobald Kapazität verfügbar ist.

2. Theoretische Herleitung

Die Autoren definieren den kumulativen Speicherbedarf über die Lebensdauer $g(s, o)$ für eine einzelne Anfrage, der die gesamte „Fläche" des über die gesamte Servicezeit einer Anfrage verbrauchten Speichers darstellt.
$$g(s, o) := \sum_{k=1}^{s/\hat{s}} k\hat{s} + \sum_{j=1}^{o} (s+j)$$
Basierend darauf leiten sie die maximale stabile Service-Rate $\mu$ her:
$$\mu = \frac{M}{\bar{b} \mathbb{E}_{s,o \sim p(s,o)}[g(s, o)]}$$
wobei $\bar{b}$ die normalisierte Batch-Verarbeitungszeit ist.

3. Stabilitätsanalyse

Unter Verwendung eines Lyapunov-Drift-Arguments, das an die stückweise linearen Speicherdynamiken von LLMs angepasst ist, etabliert die Arbeit zwei zentrale Theoreme:

• Instabilität: Wenn die Ankunftsrate $\lambda > \mu$ ist, ist das System überlastet, und die Anzahl der Anfragen wächst ins Unendliche.
• Stabilität: Wenn $\lambda < \mu(1 - \delta)$, wobei $\delta = \frac{\text{ess sup}(s+o)}{M} \ll 1$ den Speicherpuffer darstellt, der erforderlich ist, um den größten einzelnen Auftrag aufzunehmen, ist das System stabil (positive rekurrente Markov-Kette).

Hauptbeiträge

1. Neuartige Modellierung: Die Arbeit stellt das erste Warteschlangenmodell für die LLM-Inferenz vor, das sowohl die Rechenanforderungen als auch die dynamischen GPU-Speicherbeschränkungen, die durch den KV-Cache gesteuert werden, explizit integriert. Es verallgemeinert vorherige Modelle durch die Einführung von Speicherbewusstsein und die Verfeinerung von Planungssetups mit chunkierten Prefill-Phasen.
2. Rigorose Stabilitätsbedingungen: Die Autoren leiten geschlossene Stabilitäts- und Instabilitätsbedingungen her. Diese Ergebnisse bieten eine prinzipielle Grundlage für die Bestimmung der maximal nachhaltigen Durchsatzrate eines LLM-Dienstsystems unter stochastischen Arbeitslasten.
3. Empirische Validierung: Die theoretischen Vorhersagen wurden durch umfangreiche Experimente in realen GPU-Produktionsumgebungen (NVIDIA A100) validiert, die sowohl Single-GPU- als auch Multi-GPU-Konfigurationen (datenparallel) abdecken.

Experimentelle Ergebnisse

Die Autoren führten Experimente mit dem Meta-Llama-3-8B-Modell auf einem 8-GPU-Teststand mit der vLLM-Inferenz-Engine durch.

• Genauigkeit: Die theoretische Service-Rate $\mu_{theory}$ stimmt eng mit der empirisch gemessenen Rate $\mu_{gpu}$ überein. Über verschiedene Prompt-zu-Decode-Verhältnisse (P/D) (1:1, 2:1, 1:2) und einen realen Datensatz (LongBench v2) hinweg blieb der Vorhersagefehler (Gap Absolute Percentage) innerhalb von 10% (spezifisch im Bereich von 2,25% bis 8,38%).
• Multi-GPU-Skalierbarkeit: In einem 8-GPU-Cluster-Setup skalierte das theoretische Modell linear und erreichte eine Abweichung von nur 3,38% zwischen vorhergesagten und beobachteten Raten.
• Stabilitätsdynamik: Experimente bestätigten, dass bei $\lambda < \mu$ die Warteschlangenlängen begrenzt blieben (z. B. $\le 5$ für eine einzelne GPU), wohingegen $\lambda > \mu$ zu einem linearen, unbegrenzten Wachstum der Warteschlangen führte.

Bedeutung und Behauptungen

Die Arbeit behauptet, ein leistungsstarkes Werkzeug für Systembereitstellung und Ressourcenbereitstellung bereitzustellen. Durch die Kombination einer geschätzten Anfragen-Ankunftsrate mit der abgeleiteten stabilen Service-Rate können Betreiber die erforderliche Clustergröße berechnen, um:

• Kostspielige Überbeschaffung (untätige GPUs) zu vermeiden.
• Leistungsverletzende Unterbereitstellung (unbegrenzte Warteschlangen und Latenzspitzen) zu verhindern.

Die Autoren betonen, dass ihr Framework eine „prinzipielle Grundlage" für die Kapazitätsplanung bietet, die es Praktikern ermöglicht, Kapazität und Nachfrage quantitativ auszubalancieren. Sie stellen fest, dass sich ihr aktueller Fokus zwar auf datenparallele Bereitstellungen richtet, das Framework jedoch durch Anpassung der effektiven Speicher- und Batch-Zeitparameter auf Tensor-Parallelismus erweitert werden kann, wobei Pipeline-Parallelismus und Disaggregation weiterer Untersuchungen bedürfen. Die Ergebnisse bestätigen, dass die Einbeziehung von Speicherdynamiken in Warteschlangenmodelle für eine genaue Stabilitätsanalyse in modernen LLM-Dienstsystemen unerlässlich ist.