SageSched: Efficient LLM Scheduling Confronting Demand Uncertainty and Hybridity

Each language version is independently generated for its own context, not a direct translation.

🚦 SageSched : Le Chef d'Orchestre Intelligent pour les IA

Imaginez que vous êtes le directeur d'un restaurant très populaire (c'est le serveur d'IA) où des milliers de clients (les demandes d'IA) arrivent chaque minute pour commander des plats complexes.

Le problème ?

On ne sait pas combien de temps ça va prendre : Un client commande une salade simple (une réponse courte), un autre veut un banquet de 50 plats (une réponse très longue). Mais au moment de passer commande, le serveur ne sait pas exactement combien de plats le client va vraiment vouloir. C'est l'incertitude.
Deux types de ressources : Certains plats demandent beaucoup de cuisson (puissance de calcul), d'autres demandent beaucoup d'espace sur les étagères pour stocker les ingrédients avant de servir (mémoire). C'est l'hybridité.

Les anciens systèmes de gestion (les "vieux chefs") faisaient deux erreurs :

Ils servaient les clients dans l'ordre d'arrivée (Premier arrivé, premier servi), ce qui bloquait tout le monde derrière un client qui commandait un banquet interminable.
Ils prédisaient la durée du repas en devinant un seul chiffre (ex: "ça va prendre 10 minutes"), ce qui est souvent faux et ignore la variabilité.

SageSched est le nouveau chef d'orchestre qui résout ces problèmes grâce à trois astuces magiques.

🧠 Astuce 1 : La "Mémoire des Similitudes" (Prédiction)

Au lieu d'essayer de deviner l'avenir avec un modèle mathématique lourd et compliqué, SageSched utilise une approche plus humaine : l'observation.

L'analogie : Imaginez que vous arrivez au restaurant avec une phrase de commande un peu bizarre. Le nouveau chef regarde son carnet de notes et dit : "Tiens, il y a 10 minutes, un client a dit presque la même chose, et il a fini par commander 15 plats. Et il y a 20 minutes, un autre a dit la même chose et en a commandé 5."
Le résultat : Au lieu de donner un chiffre unique, SageSched dit : "Il y a 30% de chances que ce soit court, 50% que ce soit moyen, et 20% que ce soit long."
Pourquoi c'est génial ? C'est rapide, gratuit (pas besoin de réapprendre tout le temps) et beaucoup plus précis que de deviner au hasard.

⚖️ Astuce 2 : Le "Poids Réel" du Client (Modélisation des Coûts)

Les anciens chefs ne regardaient que la longueur de la réponse (le nombre de mots). SageSched regarde le vrai coût pour le restaurant.

L'analogie :
- Un client demande une réponse courte mais avec des ingrédients très encombrants qui prennent toute la place dans le frigo (mémoire).
- Un autre demande une réponse longue mais avec des ingrédients légers qui tiennent dans une petite boîte.
- Si le frigo est plein, le premier client va bloquer tout le monde, même si sa commande est courte.
Le résultat : SageSched calcule le coût en combinant le temps de cuisson ET l'espace de stockage nécessaire. Il ne se trompe pas en pensant qu'une petite commande est toujours facile à gérer.

🎲 Astuce 3 : La "Règle du Jeu de Hasard" (Ordonnancement)

C'est l'astuce la plus intelligente. Au lieu de servir le client qui a la moyenne la plus basse, SageSched utilise une formule mathématique appelée l'indice de Gittins.

L'analogie : Imaginez un jeu de casino avec plusieurs machines à sous. Certaines machines ont un gros jackpot mais sont rares, d'autres donnent de petits gains souvent.
- Un chef classique choisirait la machine avec le plus gros gain moyen.
- SageSched, lui, choisit la machine qui a le plus de chances de vous faire gagner quelque chose maintenant, même si le gain potentiel est plus petit. Il évite de rester coincé sur une machine qui va vous faire attendre 10 minutes pour un petit gain.
Le résultat : Il priorise les demandes qui ont de fortes chances de se terminer rapidement, libérant ainsi les ressources pour les autres. Et il met à jour ce calcul en temps réel : si un client commence à commander trop de plats, le chef change son plan immédiatement pour ne pas bloquer les autres.

🏆 Le Résultat Final

Grâce à ces trois astuces, SageSched a prouvé qu'il pouvait réduire le temps d'attente total des clients de plus de 28,7 % par rapport aux meilleurs systèmes actuels.

En résumé :

Moins d'attente pour les utilisateurs.
Plus de clients servis par le serveur.
Une gestion intelligente qui s'adapte à l'imprévisible (la longueur des réponses) et aux contraintes physiques (la mémoire et la puissance).

C'est comme passer d'une file d'attente de supermarché où tout le monde attend son tour, à un système où le caissier regarde le contenu de vos paniers et vous fait passer en priorité si vous n'avez que deux articles, même si vous êtes arrivé après quelqu'un avec un chariot plein !

Each language version is independently generated for its own context, not a direct translation.

Voici un résumé technique détaillé du papier de recherche "SageSched: Efficient LLM Scheduling Confronting Demand Uncertainty and Hybridity", rédigé en français.

1. Problématique et Contexte

L'inférence des grands modèles de langage (LLM) est devenue critique pour de nombreuses applications, mais son ordonnancement (scheduling) sur les serveurs GPU rencontre deux défis majeurs que les solutions actuelles ne gèrent pas efficacement :

L'incertitude de la demande (Demand Uncertainty) : Contrairement aux charges de travail traditionnelles, la longueur de la sortie d'un LLM est non déterministe avant l'exécution en raison de la nature auto-régressive de la génération. Les méthodes existantes tentent souvent de prédire une valeur unique (moyenne), ce qui est intrinsèquement imprécis et ignore la distribution probabiliste des longueurs possibles.
L'hybridité des ressources (Demand Hybridity) : Les inférences LLM sont à la fois gourmandes en calcul (compute) et en mémoire (mémoire KVCache). Les ordonnanceurs traditionnels se concentrent souvent uniquement sur le coût de calcul ou supposent que la longueur de sortie est le seul facteur de coût. Or, dans des scénarios où la mémoire GPU est saturée, deux requêtes avec la même longueur de sortie peuvent avoir des coûts de service très différents en raison de leur consommation de mémoire.

Les solutions actuelles (comme vLLM avec FCFS, ou des approches basées sur la prédiction de longueur comme SSJF) souffrent de performances sous-optimales, notamment en raison du blocage en tête de file (head-of-line blocking) et de l'incapacité à modéliser correctement le coût réel des requêtes.

2. Méthodologie : L'Approche SageSched

SageSched est un ordonnanceur conçu pour traiter simultanément l'incertitude et l'hybridité via trois techniques clés :

A. Prédicteur basé sur l'histoire et la sémantique (Semantic-aware History-based Predictor)

Au lieu d'utiliser un modèle lourd fine-tuné pour prédire une longueur unique, SageSched propose une méthode légère et précise :

Principe : Il exploite la corrélation entre la similarité sémantique des prompts d'entrée et la similarité des distributions de longueurs de sortie.
Mécanisme : Pour une requête entrante, le système recherche dans l'historique récent des requêtes ayant des prompts sémantiquement similaires (via des embeddings et une recherche de similarité cosinus).
Résultat : Au lieu d'un nombre, il récupère la distribution de probabilité des longueurs de sortie observées pour ces requêtes similaires. Cette méthode évite l'entraînement coûteux de modèles et capture l'incertitude inhérente.

B. Modélisation du coût basée sur les limites de ressources (Resource-bound-based Cost Modeling)

SageSched reconnaît que le coût de service dépend de la ressource goulot d'étranglement (calcul ou mémoire) :

Analyse : L'étude montre que le coût est soit limité par la mémoire (KVCache), soit par le calcul (Attention/FFN).
Formule unifiée : Les auteurs dérivent une formule de coût unifiée qui capture la consommation cumulative de ressources. Le coût $C$ $C$ est modélisé comme $C = \frac{O^2}{2} + IO$ $C = \frac{O ^{2}}{2} + I O$ , où $O$ $O$ est la longueur de sortie et $I$ $I$ la longueur d'entrée.
- En mode mémoire, cela représente le produit "mémoire-temps" cumulatif.
- En mode calcul, cela représente le temps de calcul cumulatif.
Cette approche est supérieure aux modèles simples basés uniquement sur $O$ ou sur une somme pondérée linéaire de $I$ et $O$ .

C. Ordonnancement conscient de l'incertitude (Uncertainty-aware Scheduling)

Pour déterminer l'ordre de traitement des requêtes, SageSched utilise la Politique de Gittins :

Concept : Le problème est formulé comme un "problème de bandit manchot multi-bras" où l'on cherche à minimiser le temps moyen d'achèvement (TTLT - Time-to-Last-Token).
Indice de Gittins : Au lieu d'utiliser la valeur moyenne de la distribution de coût (ce qui est sous-optimal), le système calcule l'indice de Gittins pour chaque requête. Cet indice représente le coût amorti minimum atteignable. Les requêtes avec un indice plus faible sont priorisées.
Mise à jour dynamique : Pour gérer l'évolution de l'inférence, les indices de Gittins sont rafraîchis périodiquement (à des seuils de "buckets" de longueur) plutôt qu'à chaque token, afin de trouver un équilibre entre réactivité et stabilité du système.

3. Contributions Clés

Identification des limites : Mise en évidence par des mesures expérimentales de l'échec des ordonnanceurs actuels face à l'incertitude et l'hybridité des charges LLM.
Conception de SageSched : Un nouveau système intégrant :
- Une prédiction de distribution de longueur basée sur l'histoire sémantique (sans entraînement).
- Une modélisation de coût unifiée tenant compte des contraintes de mémoire et de calcul.
- Une politique d'ordonnancement optimale basée sur l'indice de Gittins.
Évaluation rigoureuse : Validation sur des tests réels (benchmarks) et des simulations à grande échelle.

4. Résultats Expérimentaux

Les expériences ont été menées sur des configurations variées (modèles Llama3.1-8B et Qwen3-32B, GPU A40 et H800) avec des traces de données réelles (SharedGPT, Alpaca, Document-Write).

Amélioration des performances : SageSched surpasse les solutions de l'état de l'art (FCFS, FastServe, SSJF, TRAIL, LTR) avec une réduction du TTLT moyen de plus de 28,7% dans les scénarios les plus intenses.
Robustesse : Le système maintient de bonnes performances même avec des prédictions imparfaites (bruitées), surpassant les méthodes basées sur la moyenne.
Évolutivité : Les simulations sur des clusters jusqu'à 64 nœuds GPU montrent que la surcharge de l'ordonnancement reste négligeable (environ 100 ms par requête à grande échelle), grâce à une complexité linéaire.
Analyse fine : La désactivation de l'une des trois composantes (prédicteur, modélisation de coût, ou politique de Gittins) entraîne une dégradation significative des performances, confirmant la nécessité de l'approche holistique.

5. Signification et Impact

Ce travail est significatif car il propose une solution théoriquement fondée (via la théorie des bandits manchots et l'indice de Gittins) et pratiquement applicable pour résoudre le problème fondamental de l'ordonnancement des LLM.

Changement de paradigme : Il passe d'une approche déterministe (prédire une longueur unique) à une approche probabiliste (gérer une distribution), ce qui est crucial pour les systèmes auto-régressifs.
Optimisation des ressources : En considérant simultanément la mémoire et le calcul, SageSched évite les goulots d'étranglement invisibles pour les ordonnanceurs classiques.
Expérience utilisateur : La réduction du TTLT améliore directement l'expérience utilisateur finale, un facteur critique pour l'adoption massive des assistants IA et des systèmes autonomes.

En résumé, SageSched démontre que la prise en compte explicite de l'incertitude et de l'hybridité des ressources est la clé pour atteindre une efficacité maximale dans les infrastructures d'inférence LLM modernes.