Résumé Technique : BlendServe

Problématique

L'inférence par lots (batch inference) hors ligne est apparue comme une solution rentable pour les tâches de modèles de langage de grande taille (LLM) peu sensibles à la latence, telles que l'évaluation de modèles et la curation de données. Contraなる l'inférence en ligne, qui privilégie la faible latence, l'inférence hors ligne vise à maximiser le débit (tokens par seconde) dans une fenêtre de temps plus souple.

Les techniques d'optimisation du débit existantes, telles que le prefill par blocs (Sarathi-Serve) et le chevauchement au niveau des opérateurs (NanoFlow, Orion), se concentrent sur l'équilibre des ressources de calcul et de mémoire au sein d'un même lot. Cependant, ces approches font face à des rendements décroissants à mesure que la diversité des applications augmente. Les charges de travail modernes des LLM présentent des demandes de ressources très différentes :

• Intensives en calcul : Les tâches avec de longues séquences d'entrée mais de courtes sorties (ex: résumé de documents, benchmarks comme MMLU) saturent les unités de calcul GPU tout en laissant la bande passante mémoire sous-utilisée.
• Intensives en mémoire : Les tâches avec de longues séquences de sortie (ex: génération de vidéo, raisonnement) saturent la bande passante mémoire lors de la phase de décodage autorégressif tout en laissant les unités de calcul sous-utilisées.

Lorsqu'un lot est composé principalement d'un seul type de requête, les ressources matérielles restent déséquilibrées, ce qui limite le débit. De plus, le simple réordonnancement des requêtes pour maximiser le chevauchement des ressources entre souvent en conflit avec le partage de préfixe (prefix sharing), une technique qui regroupe les requêtes ayant des préfixes communs pour éviter les calculs redondants. Un ordre de requête qui maximise le partage de préfixe (généralement un parcours en profondeur ou DFS sur un arbre de préfixes) peut aboutir à des lots dominés par un seul type de ressource, tandis qu'un ordre qui maximise le chevauchement des ressources peut détruire la localité des préfixes.

Méthodologie : BlendServe

BlendServe est un système de service conçu pour harmoniser le batching sensible aux ressources et le partage de préfixe afin de maximiser le débit de l'inférence hors ligne. Sa conception centrale repose sur trois composants principaux :

1. Modélisation de la performance et densité de calcul

BlendServe introduit une métrique appelée densité de calcul ($\rho$), définie comme le ratio du temps des opérateurs limités par le calcul par rapport au temps des opérateurs limités par la mémoire pour une requête.

• Au niveau de la requête : $\rho(r) = \frac{\text{Comp}(r)}{\text{Mem}(r)}$. Une $\rho$ élevée indique des charges de travail intensives en calcul ; une $\rho$ faible indique des charges de travail intensives en mémoire.
• Au niveau du lot : Le système modélise le temps d'exécution total $T$ comme une fonction du temps de calcul ($T_{comp}$), du temps de mémoire ($T_{mem}$) et du ratio de partage de préfixe ($s$). L'objectif est de minimiser $T$ en maximisant le chevauchement des opérations de calcul et de mémoire tout en minimisant le calcul redondant.
• Estimation de la sortie : Comme les longueurs de sortie sont inconnues lors de la génération autorégressive, BlendServe emploie une stratégie d'échantillonnage lors d'une phase de chauffe (warm-up). Il infère les distributions de longueur de sortie basées sur la sémantique des prompts et les types de tâches, en utilisant des requêtes échantillonnées pour estimer la densité des requêtes non échantillonnées au sein du même sous-arbre de préfixe.

2. Arbre de préfixe sensible aux ressources

Pour gérer le compromis entre partage de préfixe et chevauchement des ressources, BlendServe construit un arbre de préfixe sensible aux ressources :

• Structure : Basée sur la structure Trie utilisée dans des systèmes comme SGLang, où les nœuds représentent des segments de prompt partagés.
• Amélioration : Chaque nœud est annoté avec la densité de calcul de toutes les requêtes de son sous-arbre.
• Tri et division : Le système trie les nœuds à chaque couche en fonction de leur densité de calcul, plaçant les nœuds intensifs en calcul sur la gauche et les nœuds intensifs en mémoire sur la droite. Pour gérer les valeurs aberrantes qui perturbent cet ordonnancement global, une technique de division conditionnelle de nœud est utilisée. Si la densité d'un nœud dévie de manière significative de celle de ses voisins, il est divisé et repositionné. Cela entraîne un coût contrôlé de recalcul d'un petit segment de préfixe pour obtenir un meilleur équilibre des ressources.

3. Algorithme de balayage double (Dual Scanning)

Pour générer le calendrier final des requêtes, BlendServe emploie un algorithme de balayage double :

• Mécanisme : L'algorithme parcourt les feuilles de l'arbre de préfixe trié simultanément depuis les extrémités gauche (intensive en calcul) et droite (intensive en mémoire).
• Formation des lots : Il calcule dynamiquement la partition de mémoire requise ($M_L$ et $M_R$) pour atteindre une densité de calcul globale cible ($\rho_{target}$) qui correspond à la racine de l'arbre. Les requêtes sont sélectionnées des deux extrémités pour remplir ces partitions, garantissant que chaque lot contient un mélange équilibré de requêtes intensives en calcul et en mémoire.
• Résultat : Cette approche préserve la structure hiérarchique de l'arbre de préfixe (maintenant un partage de préfixe élevé) tout en entrelaçant les requêtes pour maximiser le chevauchement des ressources matérielles.

4. Déploiement distribué

BlendServe supporte le parallélisme de données (DP) et le parallélisme de tenseur (TP).

• En DP, l'arbre de préfixe centralisé est décomposé en sous-arbres assignés à différents rangs, assurant des charges de travail équilibrées.
• En TP, le système s'intègre aux stratégies de pipeline existantes pour chevaucher l'overhead de communication avec le calcul, maintenant la compatibilité avec les déploiements à grande échelle.

Contributions clés

1. Analyse de la diversité des charges de travail : Une caractérisation détaillée de la manière dont les diverses applications de LLM (chat, codage, génération de vidéo) créent des demandes de ressources conflictuelles (calcul vs mémoire) qui limitent les stratégies de batching existantes.
2. Arbre de préfixe sensible aux ressources : Une structure de données novatrice qui encode les demandes de ressources (densité de calcul) tout en préservant les structures de préfixes, permettant au système de raisonner simultanément sur le partage de préfixe et le chevauchement des ressources.
3. Algorithme de balayage double : Un algorithme d'ordonnancement heuristique qui construit des lots en balayant un arbre de préfixe trié depuis les deux extrémités, mélangeant efficacement les types de requêtes pour maximiser le chevauchement des ressources sans sacrifier le partage de préfixe.
4. Prototype et évaluation : Une implémentation complète construite sur NanoFlow et SGLang, évaluée sur plusieurs modèles (Llama-3-8B/70B, Qwen-2.5, DeepSeek) et diverses charges de travail synthétiques.

Résultats expérimentaux

Les auteurs ont évalué BlendServe par rapport aux bases de référence standards de l'industrie (vLLM, SGLang) et aux systèmes orientés vers le débit de pointe (NanoFlow).

• Accélération du débit :
  • Comparé à vLLM et SGLang, BlendServe atteint une accélération du débit allant jusqu'à 1,44×.
  • Comparé à NanoFlow (l'état de l'art actuel pour le débit), BlendServe offre un débit moyen supérieur de 20,84 %.
• Écart d'optimalité : BlendServe atteint en moyenne 86,55 % du débit optimal théorique (jusqu'à 90 % dans certaines configurations), démontant qu'il s'approche efficacement de la limite de ce qui est réalisable avec un chevauchement parfait des ressources et un partage de préfixe.
• Utilisation des ressources : Les visualisations de l'utilisation du calcul et de la mémoire montrent que BlendServe maintient une utilisation des ressources stable et équilibrée à travers les étapes d'inférence, alors que les bases comme NanoFlow-DFS présentent des fluctuations importantes et des périodes de sous-utilisation des ressources.
• Partage de préfixe : Malgré le réordonnancement des requêtes pour l'équilibre des ressources, BlendServe maintient 97 % du ratio de partage de préfixe maximal réalisable par un parcours DFS standard.
• Scalabilité : Le système démontre une mise à l'échelle quasi linéaire avec le parallélisme de données (DP) et reste efficace à travers différentes tailles de modèles (7B à 72B) et configurations matérielles.

Signification et affirmations

L'article affirme que BlendServe est le premier système de service spécifiquement optimisé pour l'inférence par lots hors ligne qui parvient à harmoniser deux objectifs traditionnellement conflictuels : le chevauchement des ressources et le partage de préfixe.

Les auteurs soutiennent qu'à mesure que les applications de LLM se diversifient, l'hypothèse de demandes de ressources uniformes au sein d'un lot n'est plus valide. En exploitant les contraintes de latence plus souples de l'inférence hors ligne pour réordonner les requêtes, BlendServe débloque des gains de débit significatifs que les optimisations intra-lot précédentes ne pouvaient atteindre. Le système démonte qu'il est possible d'approcher le débit optimal (90 %) sans sacrifier les gains d'efficacité du cache de préfixe, fournissant une solution robuste pour une inférence de LLM à haut débit et rentable.