LLM Serving Optimization with Variable Prefill and Decode Lengths

Résumé technique : Optimisation du service LLM avec des longueurs de préremplissage (prefill) et de décodage variables

Formulation du problème
Cet article traite du problème d'ordonnancement hors ligne pour l'inférence de modèles de langage de grande taille (LLM) sur un travailleur de calcul unique doté d'un budget de mémoire de cache clé-valeur (KV) fixe. Le système gère un arriéré de $n$ requêtes arrivant simultanément à $t=0$. Chaque requête $i$ est caractérisée par une longueur de prompt hétérogène (taille de préremplissage, $s_i$) et une longueur de réponse (taille de décodage, $o_i$).

Le défi central découle de la nature dynamique de la consommation de mémoire pendant le décodage autorégressif. Alors que la phase de préremplissage consomme une mémoire proportionnelle à $s_i$, la phase de décodage consomme une mémoire qui croît linéairement à chaque jeton généré ($s_i + j$ pour le $j$-ième jeton). Par conséquent, le nombre de requêtes simultanées qu'un travailleur peut gérer fluctue dynamiquement en fonction de la progression de la génération des requêtes actives. L'objectif est de minimiser la latence totale de bout en bout (Total End-to-End Latency, TEL), définie comme la somme des temps d'achèvement de toutes les requêtes, sous la contrainte que l'utilisation globale de la mémoire de n'importe quel lot à n'importe quel pas de temps ne dépasse pas la capacité $M$.

Les auteurs lèvent l'hypothèse de tailles d'entrée uniformes présente dans les travaux antérieurs (Jaillet et al., 2025), en considérant un scénario réaliste où les charges de travail mélangent des prompts de conversation courts avec des tâches de résumé de documents longs.

Résultats théoriques et défis
L'article établit que le relâchement de l'hypothèse de taille d'entrée uniforme modifie fondamentalement la complexité du problème d'ordonnancement :

1. NP-dureté : Le problème d'ordonnancement généralisé avec des $s_i$ et $o_i$ hétérogènes est prouvé comme étant NP-difficile par réduction du problème de la 3-Partition restreinte.
2. Échec des heuristiques standards : Les politiques standards, incluant le premier arrivé, premier servi (FCFS), le plus court output d'abord (MC-SF), et la priorisation basée sur la taille totale, s'avèrent avoir des ratios d'approximation non bornés dans ce contexte hétérogène. Plus précisément, une requête avec un grand input mais un petit output peut consommer une mémoire importante brièvement, tandis qu'une requête avec un petit input mais un long output peut occuper la mémoire pendant une durée prolongée, créant des compromis que les heuristiques simples ne peuvent résoudre.

Méthodologie : L'algorithme Sorted-F
Pour répondre à ces défis, les auteurs proposent Sorted-F, un algorithme d'ordonnancement conçu pour atteindre une garantie d'approximation à facteur constant. L'algorithme opère en deux phases :

1. Construction des lots (Phase 1) : L'algorithme sélectionne de manière itérative des lots de requêtes réalisables pour former une liste ordonnée. La sélection est guidée par une nouvelle métrique de qualité, $F(X)$, définie pour un ensemble de requêtes $X$ comme :
   $$F(X) = \frac{\sum_{r_i \in X} o_i}{|X|^2}$$
   Cette métrique équilibre la taille du lot ($|X|$) par rapport au coût de décodage global en aval ($\sum o_i$). Minimiser $F(X)$ est équivalent à maximiser la « densité de débit » (requêtes terminées par unité de temps de décodage moyen). Au sein de chaque lot sélectionné, les requêtes sont triées par longueur de sortie non décroissante.
2. Exécution (Phase 2) : Le système exécute l'ordonnancement sur des pas de temps discrets, admettant les requêtes de la liste ordonnée dans le lot actuel tant que les contraintes de faisabilité de la mémoire sont satisfaites, en utilisant le batching continu et le mélange préremplissage/décodage.

Garantie d'approximation
Les auteurs prouvent que Sorted-F atteint un ratio d'approximation constant d'au plus 48 par rapport à l'ordonnancement hors ligne optimal. La preuve implique une série de transformations structurelles (séparation, regroupement et alignement) qui convertissent l'ordonnancement Sorted-F et l'ordonnancement optimal en formes comparables, démontant que l'augmentation de la latence à chaque étape est bornée par un facteur constant.

Implémentations pratiques
Reconnaissant que l'optimisation combinatoire requise dans la Phase 1 est coûteuse en calcul pour de grands $n$, l'article propose trois solveurs pratiques :

• Programmation dynamique exacte : Fournit une solution exacte pour de petites instances ($n \le 100$) avec une complexité de $O(n^2 M)$.
• Recherche par échange local (Local Swap Search) : Une heuristique pour des échelles modérées ($n \le 500$) qui améliore itérativement une solution gourmande initiale via des échanges par paires ($O(n^2)$).
• Sélection gourmande par quantile : Une heuristique en temps linéaire ($O(n)$) pour les systèmes à grande échelle ($n \ge 1000$) qui utilise l'échantillonnage statistique pour filtrer les valeurs aberrantes et remplit la capacité de manière gourmande.

De plus, l'article introduit Sorted-LP, une heuristique exploitant la solution d'une relaxation de programmation linéaire (LP) du problème pour ordonner les requêtes, et Sorted-F+Amin, une variante adaptative qui gère l'incertitude de prédiction des longueurs de sortie en affinant dynamiquement les estimations pendant l'inférence.

Résultats expérimentaux
Des expériences numériques sur des charges de travail mixtes (combinant le jeu de données LMSYS-Chat et des résumés de documents longs d'Arxiv) démontrent :

• Réduction de la latence : Sorted-F (utilisant la recherche par échange local) surpasse systématiquement FCFS, MC-SF et les bases de référence guidées par LP. Dans un mélange 80/20 court/long avec 2000 requêtes, Sorted-F a réduit la latence moyenne de 4,87$\times$ par rapport à FCFS et de 2,09$\times$ par rapport à MC-SF.
• Écart d'optimalité : Sur les instances tractables, l'écart empirique entre Sorted-F et la borne inférieure de la relaxation LP est faible (environ 1,03–1,09), suggérant que l'algorithme est proche de l'optimalité en pratique malgré la borne théorique lâche.
• Sensibilité à la charge de travail : Les bénéfices de Sorted-F sont plus prononcés dans les régimes hétérogènes et surchargés où la mémoire est une contrainte contraignante. Dans les régimes homogènes ou peu chargés, l'avantage diminue.
• Performance en ligne : Une variante à horizon fuyant (receding-horizon) testée sous des arrivées de type Poisson montre des améliorations significatives par rapport à MC-SF et FCFS dans les régimes en ligne surchargés, bien qu'elle offre moins de bénéfices dans les régimes stables à faible latence.

Signification et revendications
L'article affirme que les longueurs de préremplissage variables ne sont pas un simple détail de modélisation, mais un facteur fondamental qui rend inefficaces les heuristiques d'ordonnancement standards et rend le problème NP-difficile. La contribution principale est l'algorithme Sorted-F, qui fournit la première garantie d'approximation à facteur constant pour l'ordonnancement de LLM sous des contraintes d'entrée/sortie hétérogènes. Ce travail comble le fossé entre les limites théoriques d'ordonnancement et le service pratique de LLM, offrant un cadre évolable et conscient de la mémoire qui réduit considérablement la latence dans les scénarios de charges de travail mixtes sans nécessiter une prédiction parfaite des longueurs de sortie. Les auteurs soulignent que si la borne théorique est de 48, les résultats empiriques suggèrent que l'algorithme est beaucoup plus proche de la solution optimale dans des contextes réalistes.