Résumé Technique : Au-delà de la Prédiction : Ordonnancement Sensible à la Queue pour l'Inférence des LLM

1. Énoncé du Problème

Le service de modèles de langage de grande taille (LLM) fait face à un défi critique dans la gestion de l'extrême variabilité de la longueur des requêtes, particulièrement avec l'émergence de modèles augmentés par le raisonnement qui présentent une génération multi-étapes, une auto-réflexion et une terminaison adaptative. Cette variabilité rend les politiques d'ordonnancement basées sur la taille (comme le Shortest Job First - SJF, ou le Shortest Remaining Processing Time - SRPT) fragiles.

Les ordonnanceurs de pointe actuels s'appuient sur la prédiction de la longueur de sortie ou des tokens restants pour approximer le SJF/SRPT. Cependant, l'article identifie trois problèmes fondamentaux avec cette approche :

1. Fragilité de la Prédiction : La prédiction de la longueur de sortie est intrinsèquement difficile en raison de la haute variance dans la génération de tokens (stochasticité et non-déterminisme), ce qui rend les politiques fragiles face aux changements de distribution et aux arrivées par rafales.
2. Inadéquation des Métriques : Les politiques optimisées pour la latence moyenne (ex: TTFT/TBT moyen) présentent souvent un comportement médiocre pour la latence de queue (P90–P99). Dans le service de LLM, l'expérience utilisateur est régie par les latences de queue (Time-To-Last-Token, TTLT), qui sont souvent la contrainte déterminante pour les Objectifs de Niveau de Service (SLO).
3. Dynamiques Couplées à la Mémoire : Contrairement aux files d'attente classiques, l'inférence de LLM est un processus avec état. Les requêtes accumulent de larges caches de clés-valeurs (KV) pendant le décodage. Une préemption naïve pour prioriser les tâches courtes peut mener à une éviction de cache, une recomputation et un « battement » (thrashing) coûteux, ce qui peut augmenter la latence de queue malgré la réduction du délai d'attente.

La question centrale posée est de savoir si les ordonnanceurs ont besoin de prédictions explicites de la longueur des tâches pour optimiser la latence de queue. Les auteurs soutiennent que non, proposant à la place une approche sans prédiction et sensible à la distribution.

2. Méthodologie : UNIBOOST

L'article introduit UNIBOOST, un cadre d'ordonnancement sensible à la distribution et sans prédiction, qui remplace la prédiction explicite de la longueur par un renforcement de priorité (« soft » priority boosting) piloté par des signaux statistiques légers. La conception est une co-optimisation de l'ordonnancement et de la préemption sensible au cache, structurée en quatre phases :

Phase 1 : Strawman (DISTBOOST)

L'approche initiale traite les phases de prefill (pré-remplissage) et de decode (décodage) comme des problèmes disjoints. Elle utilise une fonction de priorité $\gamma$-Boost (inspirée de la théorie des files d'attente) pour les requêtes de prefill mais priorise la file de decode. Bien que cela améliore les métriques de queue pour le décodage, cela souffre d'un blocage en tête de ligne (Head-of-Line - HoL) où les requêtes de prefill sont affamées par des tâches de décodage de longue durée.

Phase 2 : Priorisation Unifiée (UNIBOOST-BASE)

Pour remédier au blocage HoL, les auteurs unifient les files de prefill et de decode dans un espace de priorité unique.

• Score de Priorité : Les requêtes sont scorées selon $\phi_i(t) = a_i - b_\gamma(\tilde{w}_i(t))$, où $a_i$ est le temps d'arrivée et $\tilde{w}_i(t)$ est le travail effectif (le maximum entre le travail atteint et la longueur du prefill).
• Fonction de Boost : $b_\gamma(w) = \frac{1}{\gamma} \log(\frac{1}{1 - e^{-\gamma w}})$. Cette fonction fournit un renforcement de priorité « doux » aux requêtes ayant moins de service atteint, évitant la préemption brutale du SRPT classique.
• Mécanisme : L'ordonnanceur sélectionne la requête avec le score minimum, permettant la préemption entre les phases mais contrôlée par un paramètre d'hystérésis pour éviter les oscillations.

Phase 3 : Stabilité via MEMGUARD (Hystérésis sensible au KV)

Pour atténuer le coût élevé de l'éviction et de la recomputation du cache KV, les auteurs introduisent MEMGUARD.

• Priorités Quantifiées : Au lieu de mettre à jour les priorités de manière continue, le système discrétise la métrique du travail atteint ($\hat{w}_i$) en utilisant une quantification géométrique (ex: seuils à $k, 2k, 4k...$).
• Durée Minimale : Une fois qu'une requête est lancée, elle ne peut être évictée tant que son travail atteint n'a pas franchi le seuil de quantification suivant. Cela amortit les coûts de mouvement du cache KV et limite le nombre d'opportunités de préemption à une borne logarithmique par rapport à la longueur de la tâche.

Phase 4 : Estimation de Paramètre Adaptatif ($\gamma$-Ada)

Le paramètre de boost $\gamma$ impacte significativement le comportement de la queue. Un $\gamma$ statique est sous-optimal sous des charges variables.

• Estimation en Ligne : Le système estime une pente de queue effective ($\gamma_{eff}$) en ajustant une pente log-linéaire à la queue supérieure de la distribution des temps de réponse observés (entre P95 et P99).
• Adaptation : L'ordonnanceur ajuste dynamiquement $\gamma$ pour interpoler entre le FCFS (protégeant la queue) et le LAS (optimisant la moyenne), s'adaptant aux changements de charge sans prédiction explicite.

3. Contributions Clés

1. Optimisation de la Queue sans Prédiction : Démontre que la prédiction explicite de la longueur des tâches n'est pas nécessaire pour optimiser la latence de queue. À la place, des signaux statistiques légers et un renforcement doux suffisent.
2. Co-conception de l'Ordonnancement et de l'Éviction : Introduit un cadre qui optimise conjointement les décisions d'ordonnancement avec la gestion du cache KV. En couplant l'ordonnancement par boost avec un contrôle d'exécution sensible à l'éviction (MEMGUARD), le système évite la dégradation des performances causée par le battement (thrashing) du cache.
3. Robustesse aux Changements de Distribution : La méthode proposée s'adapte à diverses charges de travail (à queue lourde ou queue légère, raisonnement ou chat) sans réentraînement ni modèles de prédiction complexes.
4. Fondement Théorique : Adapte la politique $\gamma$-Boost de la théorie des files d'attente aux contraintes spécifiques de l'inférence de LLM (état, couplage mémoire).

4. Résultats Expérimentaux

Évalué sur des traces de production et open-source (Azure, ShareGPT, S1K) avec des modèles tels que Llama-3-8B, CodeLlama-34B et Qwen-72B sur des GPU NVIDIA A100 :

• Réduction de la Latence de Queue : UNIBOOST atteint un P99 TTLT jusqu'à 35–50 % inférieur à celui de SRPT avec une prédiction de longueur parfaite (TRAIL+). Il réduit également le P99 TTFT de 34–47 % sur diverses charges de travail.
• Débit (Throughput) : La méthode améliore le débit de 1,01–1,12$\times$ sous des charges par rafales par rapport aux bases de référence.
• Atteinte des SLO : UNIBOOST permet aux systèmes de tolérer des SLO pour le TTFT 2,9 à 8,7 fois plus stricts tout en maintenant une atteinte de 99 % par rapport aux approches basées sur le SJF.
• Études d'Ablation :
  • Supprimer la priorité unifiée (Phase 2) entraîne une famine du prefill.
  • Supprimer MEMGUARD (Phase 3) provoque des pics importants de latence de queue dus au battement (thrashing) du KV.
  • Supprimer l'adaptation de $\gamma$ (Phase 4) réduit la robustesse lors des changements de charge.
• Comparaison : La méthode surpasse les bases de référence de pointe, incluant le chunked prefill de Sarathi (vLLM), le LTR (learning-to-rank SJF) et TRAIL (SRPT basé sur la prédiction), particulièrement dans les charges de travail lourdes en raisonnement où la prédiction est la plus peu fiable.

5. Signification et Revendications

L'article affirme que UNIBOOST offre une alternative robuste aux politiques d'ordonnancement dépendantes de la prédiction pour le service en ligne de LLM. Sa signification réside dans :

• Découplage de la Prédiction : Il élimine la dépendance à une prédiction précise de la longueur, ce qui est un goulot d'étranglement majeur dans les charges de travail de raisonnement intense et de longueur variable.
• Optimisation Holistique : Il traite simultanément le compromis « moyenne vs queue » et le compromis « ordonnancement vs mémoire », offrant une solution efficace même lorsque la qualité de la prédiction se dégrade.
• Praticité : Sa conception est simple à intégrer dans les piles de continuous-batching existantes (comme vLLM et SGLang) et repose sur des statistiques d'exécution légères plutôt que sur des modèles ML complexes.

Les auteurs concluent qu'un ordonnancement sensible à la distribution et conscient de l'éviction est essentiel pour la prochaine génération de service de LLM, surtout à mesure que les modèles deviennent plus capables de raisonnement à longueur variable.