Technische Samenvatting: Een Wachtrij-theoretisch Kader voor Stabiliteitsanalyse van LLM-inferentie met Beperkingen in KV-cachegeheugen

Probleemstelling

De snelle adoptie van Large Language Models (LLM's) heeft aanzienlijke uitdagingen geschapen voor efficiënte inferentie op schaal. In tegenstelling tot traditionele werklasten wordt LLM-inferentie beperkt door een dubbele bottleneck: rekenkundige doorvoer en het geheugennadeel van Key-Value (KV) caching. Hoewel KV-caching de decoding versnelt door hergebruik van representaties van eerder gegenereerde tokens, verbruikt het aanzienlijk GPU-geheugen en wordt dit vaak de primaire capaciteitsbeperking.

Bestaande wachtrijmodellen voor LLM-inferentie richten zich typisch op rekenkundige limieten of behandelen geheugen als een statische beperking, waardoor ze de dynamische wisselwerking tussen berekening en geheugengroei tijdens het inferentieproces niet vastleggen. Specifiek evolueert het geheugengebruik lineair naarmate een verzoek door de promptfase (prefill) en de token-generatiefase (decode) vordert. Als de aankomstfrequentie van verzoeken de effectieve servicefrequentie van het systeem overschrijdt – welke gezamenlijk wordt bepaald door GPU-berekening en beschikbaar KV-cachegeheugen – groeien de wachtrijen onbeperkt, wat leidt tot systeeminstabiliteit, onacceptabele latentie en een verslechterde gebruikerservaring. Er ontbreekt een rigoureus theoretisch kader dat deze dynamische geheugenbeperkingen expliciet integreert om stabiliteitsvoorwaarden te bepalen en GPU-provisioning te sturen.

Methodologie

De auteurs stellen een nieuw wachtrij-theoretisch kader voor dat LLM-inferentie modelleert als een discrete-tijd, werkbehoudend wachtrijsysteem onderworpen aan een harde KV-cachegeheugenbeperking ($M$).

1. Systeemmodel

• Verzoekstructuur: Elk verzoek $i$ bestaat uit een prompt van grootte $s_i$ en een antwoord van lengte $o_i$, getrokken uit een gezamenlijke verdeling $F_{in-out}$.
• Verwerkingsfasen:
  • Promptfase: Prompts worden verwerkt in vaste chunk-groottes ($\hat{s}$). Het geheugengebruik voor de $j$-de chunk van een prompt groeit lineair ($j \times \hat{s}$).
  • Decodefase: Naarmate tokens sequentieel worden gegenereerd, neemt het geheugengebruik toe met de hoeveelheid KV-cache van één token per stap. Het totale geheugen voor een verzoek bereikt $s_i + o_i$ bij voltooiing.
• Geheugenbeperking: Het systeem moet op elk tijdstip $t$ voldoen aan $\sum_{i \in S(t)} (c_i^{(t)}\hat{s} + d_i^{(t)}) \le M$, waarbij $S(t)$ de set actieve verzoeken is, $c_i^{(t)}$ de index van de verwerkte prompt-chunk is, en $d_i^{(t)}$ de index van het verwerkte output-token is.
• Planning: Het kader gaat uit van continue batching en werkbehoudende beleidslijnen (bijvoorbeeld First-Come-First-Served), waarbij de server de volgende prioriteitsprompt verwerkt zodra capaciteit dit toelaat.

2. Theoretische Afleiding

De auteurs definiëren het levenslange cumulatieve geheugengebruik $g(s, o)$ voor een enkel verzoek, wat het totale "oppervlak" van het verbruikte geheugen over de volledige servicetijd van het verzoek voorstelt.
$$g(s, o) := \sum_{k=1}^{s/\hat{s}} k\hat{s} + \sum_{j=1}^{o} (s+j)$$
Op basis hiervan leiden ze de maximale stabiele servicefrequentie $\mu$ af:
$$\mu = \frac{M}{\bar{b} \mathbb{E}_{s,o \sim p(s,o)}[g(s, o)]}$$
waarbij $\bar{b}$ de genormaliseerde batchverwerkingstijd is.

3. Stabiliteitsanalyse

Met behulp van een Lyapunov-driftargument, aangepast voor de stuksgewijs lineaire geheugendynamiek van LLM's, stelt het artikel twee belangrijke stellingen vast:

• Instabiliteit: Als de aankomstfrequentie $\lambda > \mu$, is het systeem overbelast en groeit het aantal verzoeken naar oneindig.
• Stabiliteit: Als $\lambda < \mu(1 - \delta)$, waarbij $\delta = \frac{\text{ess sup}(s+o)}{M} \ll 1$ de geheugenruimte voorstelt die nodig is om de grootste enkele taak te accommoderen, is het systeem stabiel (positief recurrente Markov-keten).

Belangrijkste Bijdragen

1. Nieuw Modellering: Het artikel introduceert het eerste wachtrijmodel voor LLM-inferentie dat zowel de rekenkundige vraag als dynamische GPU-geheugenbeperkingen, gestuurd door de KV-cache, expliciet integreert. Het generaliseert eerdere modellen door geheugenbewustzijn toe te voegen en planningsopstellingen te verfijnen met op chunken gebaseerde prefill-fases.
2. Rigoureuze Stabiliteitsvoorwaarden: De auteurs leiden gesloten-vorm stabiliteits- en instabiliteitsvoorwaarden af. Deze resultaten bieden een principiële basis voor het bepalen van de maximaal duurzame doorvoer van een LLM-servingsysteem onder stochastische werklasten.
3. Empirische Validatie: De theoretische voorspellingen worden gevalideerd door uitgebreide experimenten in echte GPU-productieomgevingen (NVIDIA A100), die zowel single-GPU- als multi-GPU-configuraties (data-parallel) omvatten.

Experimentele Resultaten

De auteurs voerden experimenten uit met het Meta-Llama-3-8B-model op een testomgeving met 8 GPU's, gebruikmakend van de vLLM-inferentie-engine.

• Nauwkeurigheid: De theoretische servicefrequentie $\mu_{theory}$ komt nauw overeen met de empirisch gemeten frequentie $\mu_{gpu}$. Bij verschillende prompt-naar-decode (P/D)-verhoudingen (1:1, 2:1, 1:2) en een real-world dataset (LongBench v2) bleef de voorspellingsfout (Gap Absolute Percentage) binnen 10% (specifiek variërend van 2,25% tot 8,38%).
• Multi-GPU Schaalbaarheid: In een 8-GPU-clusteropstelling schaalde het theoretische model lineair, met een verschil van slechts 3,38% tussen voorspelde en waargenomen frequenties.
• Stabiliteitsdynamiek: Experimenten bevestigden dat wanneer $\lambda < \mu$, de wachtrijlengten begrensd bleven (bijvoorbeeld $\le 5$ voor een enkele GPU), terwijl $\lambda > \mu$ leidde tot lineaire, onbeperkte groei van de wachtrij.

Betekenis en Aanspraken

Het artikel claimt een krachtig hulpmiddel te bieden voor systeemimplementatie en resource-provisioning. Door een geschatte aankomstfrequentie van verzoeken te combineren met de afgeleide stabiele servicefrequentie, kunnen beheerders de benodigde clusteromvang berekenen om:

• Duurzame overaanschaffing (idle GPU's) te vermijden.
• Prestatieschendende onderprovisioning (onbeperkte wachtrijen en latentiepieken) te voorkomen.

De auteurs benadrukken dat hun kader een "principiële basis" biedt voor capaciteitsplanning, waardoor praktici kwantitatief capaciteit en vraag in evenwicht kunnen brengen. Zij merken op dat hoewel hun huidige werk zich richt op data-parallelle implementaties, het kader kan worden uitgebreid tot tensor-parallelisme door effectieve geheugen- en batchtijdparameters aan te passen, hoewel pipeline-parallelisme en disaggregatie verder onderzoek vereisen. De resultaten bevestigen dat het integreren van geheugendynamiek in wachtrijmodellen essentieel is voor een accurate stabiliteitsanalyse in moderne LLM-servingsystemen.