Résumé Technique : Un Cadre Théorique des Files d'Attente pour l'Analyse de Stabilité de l'Inférence des LLM avec Contraintes de Mémoire KV Cache

Énoncé du Problème

L'adoption rapide des grands modèles de langage (LLM) a créé des défis significatifs pour une inférence efficace à grande échelle. Contrairement aux charges de travail traditionnelles, l'inférence des LLM est contrainte par un goulot d'étranglement dual : le débit de calcul et la surcharge mémoire de la mise en cache des clés et valeurs (KV). Bien que la mise en cache KV accélère le décodage en réutilisant les représentations des tokens précédemment générés, elle consomme une mémoire GPU substantielle, devenant souvent la contrainte de capacité principale.

Les modèles de files d'attente existants pour l'inférence des LLM se concentrent généralement sur les limites de calcul ou traitent la mémoire comme une contrainte statique, échouant à capturer l'interaction dynamique entre le calcul et la croissance de la mémoire pendant le processus d'inférence. Plus précisément, à mesure qu'une requête progresse à travers les phases de prompt (préremplissage) et de génération de tokens (décodage), son empreinte mémoire évolue linéairement. Si le taux d'arrivée des requêtes dépasse le taux de service effectif du système — déterminé conjointement par le calcul GPU et la mémoire KV cache disponible — les files d'attente croissent de manière illimitée, entraînant une instabilité du système, une latence inacceptable et une dégradation de l'expérience utilisateur. Il manque des cadres théoriques rigoureux intégrant explicitement ces contraintes mémoire dynamiques pour déterminer les conditions de stabilité et guider le provisionnement des GPU.

Méthodologie

Les auteurs proposent un cadre théorique des files d'attente novateur qui modélise l'inférence des LLM comme un système de file d'attente en temps discret, conservateur de travail, soumis à une contrainte stricte de mémoire KV cache ($M$).

1. Modèle du Système

• Structure de la Requête : Chaque requête $i$ se compose d'un prompt de taille $s_i$ et d'une réponse de longueur $o_i$, échantillonnés à partir d'une distribution conjointe $F_{in-out}$.
• Phases de Traitement :
  • Phase de Prompt : Les prompts sont traités par blocs de taille fixe ($\hat{s}$). L'utilisation de la mémoire pour le $j$-ème bloc d'un prompt croît linéairement ($j \times \hat{s}$).
  • Phase de Décodage : À mesure que les tokens sont générés séquentiellement, l'utilisation de la mémoire augmente d'une valeur de cache KV par token à chaque étape. La mémoire totale pour une requête atteint $s_i + o_i$ à l'achèvement.
• Contrainte de Mémoire : Le système doit satisfaire $\sum_{i \in S(t)} (c_i^{(t)}\hat{s} + d_i^{(t)}) \le M$ à tout instant $t$, où $S(t)$ est l'ensemble des requêtes actives, $c_i^{(t)}$ est l'index du bloc de prompt traité, et $d_i^{(t)}$ est l'index du token de sortie traité.
• Ordonnancement : Le cadre suppose un regroupement continu (continuous batching) et des politiques conservatrices de travail (par exemple, Premier Arrivé Premier Servi), où le serveur traite le prompt de priorité suivant dès que la capacité le permet.

2. Déduction Théorique

Les auteurs définissent l'utilisation cumulative de la mémoire sur la durée de vie $g(s, o)$ pour une seule requête, représentant l'« aire » totale de mémoire consommée sur toute la durée de service de la requête.
$$g(s, o) := \sum_{k=1}^{s/\hat{s}} k\hat{s} + \sum_{j=1}^{o} (s+j)$$
Sur cette base, ils dérivent le taux de service stable maximal $\mu$ :
$$\mu = \frac{M}{\bar{b} \mathbb{E}_{s,o \sim p(s,o)}[g(s, o)]}$$
où $\bar{b}$ est le temps de traitement par lot normalisé.

3. Analyse de Stabilité

En utilisant un argument de dérive de Lyapunov adapté à la dynamique mémoire linéaire par morceaux des LLM, l'article établit deux théorèmes clés :

• Instabilité : Si le taux d'arrivée $\lambda > \mu$, le système est surchargé et le nombre de requêtes croît à l'infini.
• Stabilité : Si $\lambda < \mu(1 - \delta)$, où $\delta = \frac{\text{ess sup}(s+o)}{M} \ll 1$ représente la marge mémoire requise pour accueillir le plus grand travail unique, le système est stable (chaîne de Markov récurrente positive).

Contributions Clés

1. Modélisation Novatrice : L'article introduit le premier modèle de file d'attente pour l'inférence des LLM intégrant explicitement à la fois la demande de calcul et les contraintes dynamiques de mémoire GPU gouvernées par le cache KV. Il généralise les modèles antérieurs en ajoutant une conscience de la mémoire et en affinant les configurations d'ordonnancement avec des phases de préremplissage par blocs.
2. Conditions de Stabilité Rigoureuses : Les auteurs dérivent des conditions de stabilité et d'instabilité sous forme fermée. Ces résultats fournissent une base fondée sur des principes pour déterminer le débit maximal durable d'un système de service LLM sous des charges de travail stochastiques.
3. Validation Empirique : Les prédictions théoriques sont validées par des expériences extensives dans des environnements de production GPU réels (NVIDIA A100), couvrant à la fois des configurations à GPU unique et multi-GPU (parallélisme de données).

Résultats Expérimentaux

Les auteurs ont mené des expériences en utilisant le modèle Meta-Llama-3-8B sur un banc d'essai à 8 GPU avec le moteur d'inférence vLLM.

• Précision : Le taux de service théorique $\mu_{theory}$ correspond étroitement au taux mesuré empiriquement $\mu_{gpu}$. À travers divers ratios prompt/décodage (P/D) (1:1, 2:1, 1:2) et un jeu de données réel (LongBench v2), l'erreur de prédiction (Écart en Pourcentage Absolu) est restée dans les 10 % (spécifiquement variant de 2,25 % à 8,38 %).
• Évolutivité Multi-GPU : Dans une configuration de cluster à 8 GPU, le modèle théorique a évolué linéairement, atteignant un écart de seulement 3,38 % entre les taux prédits et observés.
• Dynamiques de Stabilité : Les expériences ont confirmé que lorsque $\lambda < \mu$, les longueurs de file d'attente restaient bornées (par exemple, $\le 5$ pour un GPU unique), tandis que $\lambda > \mu$ entraînait une croissance linéaire et illimitée de la file d'attente.

Importance et Revendications

L'article revendique fournir un outil puissant pour le déploiement de systèmes et le provisionnement des ressources. En combinant un taux d'arrivée de requêtes estimé avec le taux de service stable dérivé, les opérateurs peuvent calculer la taille de cluster nécessaire pour :

• Éviter un surachat coûteux (GPU inactifs).
• Prévenir un sous-provisionnement violant les performances (files d'attente illimitées et pics de latence).

Les auteurs soulignent que leur cadre offre une « base fondée sur des principes » pour la planification des capacités, permettant aux praticiens d'équilibrer quantitativement la capacité et la demande. Ils notent que, bien que leur travail actuel se concentre sur les déploiements en parallélisme de données, le cadre peut être étendu au parallélisme tensoriel en ajustant les paramètres de mémoire effective et de temps de lot, bien que le parallélisme de pipeline et la désagrégation nécessitent une étude ultérieure. Les résultats confirment que l'intégration de la dynamique mémoire dans les modèles de files d'attente est essentielle pour une analyse de stabilité précise dans les systèmes modernes de service LLM.