📊 statistics

Throughput-Optimal Scheduling Algorithms for LLM Inference and AI Agents

Cet article établit les fondements mathématiques de la file d'attente pour l'inférence des LLM, démontrant que les algorithmes de planification qui préservent le travail atteignent le débit maximal pour les charges de travail individuelles et celles des agents IA, tout en évaluant des systèmes réels pour confirmer l'optimalité d'Orca et de Sarathi-Serve et mettant en garde contre l'instabilité de FasterTransformer et de vLLM standard.

Auteurs originaux : J. G. Dai, Tianze Deng, Yueying Li, Tianyi Peng

Publié 2026-05-19

📖 7 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : J. G. Dai, Tianze Deng, Yueying Li, Tianyi Peng

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous dirigez une usine à haute vitesse qui construit des robots personnalisés. Dans cette usine, chaque commande (une « requête ») passe par deux étapes distinctes :

La phase de configuration (Prefill) : Vous lisez les plans et rassemblez toutes les pièces nécessaires. C'est un travail lourd qui demande beaucoup de puissance de calcul, mais qui s'effectue en une seule fois.
La phase d'assemblage (Decode) : Vous commencez à construire le robot, en ajoutant une pièce à la fois, une par une. C'est un travail plus lent, gourmand en mémoire, qui s'effectue étape par étape.

Votre usine dispose d'un bras robotique géant et ultra-rapide (le GPU) capable de travailler sur plusieurs commandes simultanément. Cependant, ce bras a une limite : il ne peut maintenir qu'un certain poids total de pièces dans sa pince à la fois (le budget de jetons).

Le document que vous avez fourni est une étude mathématique sur la manière d'organiser les commandes afin que votre usine ne s'arrête jamais et produise le nombre maximal de robots possible sans se bloquer.

Voici la décomposition de leurs découvertes à l'aide d'analogies simples :

1. La Règle d'Or : « Ne laissez pas le bras inactif »

La découverte la plus importante de ce document est un concept appelé « conservation du travail » (Work-Conserving).

Imaginez que votre bras robotique est prêt à saisir des pièces.

La mauvaise façon : Vous ne permettez au bras de saisir des pièces de « configuration » que s'il n'y a que des commandes de configuration en attente. S'il y a des commandes d'« assemblage » en attente, vous les ignorez, même si le bras a de l'espace vide. Ou alors, vous ne lui permettez de saisir des pièces d'« assemblage » que s'il n'y a que des commandes d'assemblage.
- Résultat : Le bras reste à moitié vide, attendant un type spécifique de commande, tandis qu'un énorme tas de l'autre type de commande s'accumule. L'usine ralentit ou plante.
La bonne façon (conservation du travail) : Si le bras a de la place, vous le remplissez avec tout ce qui est disponible. Vous mélangez des pièces de configuration et des pièces d'assemblage dans le même lot. Vous ne laissez jamais le bras inactif s'il y a du travail à faire.

L'affirmation du document : Les algorithmes qui suivent cette règle de « remplir le seau » (comme Orca et Sarathi-Serve) sont mathématiquement prouvés comme étant les plus efficaces. Ils peuvent gérer la quantité de travail maximale possible sans que le système ne s'effondre.

2. Les « anciens » vs « nouveaux » directeurs d'usine

Les auteurs ont testé quatre « directeurs » populaires (algorithmes d'ordonnancement) pour voir qui suivait la Règle d'Or :

FasterTransformer & Vanilla vLLM (Les directeurs stricts) : Ces directeurs sont trop exigeants.
- FasterTransformer ne saisit que des pièces d'assemblage. S'il n'y a pas de commandes d'assemblage, il ignore les commandes de configuration en attente, même si le bras est vide.
- Vanilla vLLM ne saisit que des pièces de configuration. S'il n'y a pas de commandes de configuration, il ignore les commandes d'assemblage.
- Verdict : Ces solutions ne sont pas optimales. Sous forte charge, elles provoquent l'encombrement et l'instabilité de l'usine.
Orca & Sarathi-Serve (Les directeurs flexibles) : Ces directeurs mélangent les deux types de travail. Ils remplissent le bras avec ce qui convient.
- Verdict : Ces solutions sont optimales. Elles maintiennent l'usine en fonctionnement fluide à vitesse maximale.

3. L'usine des « agents IA » (flux de travail complexes)

Parfois, une commande n'est pas un simple robot ; c'est toute une équipe de robots travaillant ensemble.

Le DAG (Graphe Acyclique Dirigé) : Imaginez un flux de travail où la commande A va à la station 1, puis à la station 2, puis à la station 3, et ne revient jamais en arrière.
- Découverte : Tant que le flux de travail est une ligne droite (sans boucles), la règle « Ne laissez pas le bras inactif » fonctionne toujours parfaitement à travers toutes les stations.
La fourche-réunion (Fork-Join) : Imaginez que la commande A se divise en trois sous-tâches qui vont à trois stations différentes, et qu'elles doivent toutes se terminer avant que l'étape finale puisse avoir lieu.
- Découverte : La règle « Ne laissez pas le bras inactif » fonctionne également ici.
La boucle (Le piège) : Imaginez que la commande A va à la station 1, puis à la station 2, mais que la commande B va de la station 2 vers la station 1. Elles se poursuivent en cercle.
- Découverte : Ici, la règle « Ne laissez pas le bras inactif » peut échouer. Même si les directeurs font de leur mieux, la circulation circulaire peut provoquer un embouteillage qui ne se résout jamais. Le document montre que si votre usine possède ces boucles circulaires, vous avez besoin d'un directeur beaucoup plus intelligent et prudent, pas seulement d'un « remplisseur de seau ».

4. La surprise de la « taille du seau »

Il y a une deuxième limite dans l'usine : la taille du lot (Batch Size). C'est le nombre maximum de commandes que le bras peut contenir, indépendamment de leur poids.

La surprise : Les auteurs ont découvert que parfois, remplir le bras jusqu'à sa limite de poids absolue (le budget de jetons) est en fait une mauvaise idée.
L'analogie : Imaginez que vous avez un seau qui contient 100 livres. Vous avez 100 petits cailloux (Configuration) et 100 lourdes briques (Assemblage).
- Si vous essayez de remplir le seau à 100 livres avec des briques, vous ne pourrez peut-être en mettre que 5. Le temps nécessaire pour soulever cette charge lourde est long.
- Mais si vous vous arrêtez à 50 livres (une charge plus légère), vous pourrez peut-être la soulever beaucoup plus vite, vous permettant de faire plus de trajets par heure.
La découverte : Dans des situations spécifiques, la stratégie la plus efficace consiste à arrêter de remplir le seau avant qu'il ne soit plein pour maintenir une vitesse de traitement élevée. Cela signifie que même les « bons directeurs » (conservation du travail) peuvent échouer si les règles de l'usine (limites de taille de lot) sont trop strictes et que le mélange de commandes est juste ce qu'il faut pour provoquer un embouteillage.

Résumé

Le document nous dit :

Mélangez votre travail : Ne séparez pas les tâches de configuration et d'assemblage. Mélangez-les dans le même lot pour maintenir le GPU occupé.
Orca et Sarathi-Serve sont les gagnants : Ils suivent la règle « mélanger et remplir », ce qui en fait les choix les plus stables et efficaces pour la plupart des situations.
Méfiez-vous des boucles : Si vos agents IA envoient des tâches d'avant en arrière entre les serveurs en cercle, les règles simples de « remplissage du seau » pourraient ne pas fonctionner ; vous avez besoin d'un contrôle de circulation spécial.
Plein n'est pas toujours mieux : Parfois, laisser un peu d'espace vide dans votre lot est plus intelligent que de le remplir à ras bord, selon la taille des tâches individuelles.

Le but de tout ce calcul est d'aider les ingénieurs à construire des systèmes d'IA qui ne plantent pas lorsque des millions de personnes posent des questions en même temps.

Résumé technique : Algorithmes de planification optimaux pour le débit dans l'inférence des LLM et les agents IA

Énoncé du problème

À mesure que la demande pour les modèles de langage de grande taille (LLM) et les agents IA augmente, l'optimisation des systèmes d'inférence pour l'efficacité devient cruciale. Bien que d'importants efforts d'ingénierie se soient concentrés sur des améliorations au niveau du système, il manque un cadre de modélisation mathématique cohérent et fondé sur la théorie des files d'attente pour évaluer les algorithmes de planification. Plus précisément, l'article aborde la question fondamentale : quel est le taux de débit maximal pour un système d'inférence LLM, et quelles classes d'algorithmes de planification peuvent atteindre cette limite ?

L'inférence LLM présente des défis uniques par rapport aux systèmes de files d'attente classiques :

Traitement en deux phases : Les requêtes subissent une phase de préremplissage (prefill) limitée par le calcul (traitement des tokens d'entrée pour construire le cache KV) suivie d'une phase de décodage (decode) limitée par les E/S mémoire (génération autoregressive de tokens).
Contraintes de regroupement (batching) : Pour maximiser l'utilisation du GPU, les requêtes sont regroupées. Cependant, mélanger les tokens de préremplissage et de décodage crée des interférences, et le matériel impose un budget de tokens ( $b_{max}$ ) et souvent une contrainte de taille de lot ( $k_{max}$ ).
Charges de travail des agents IA : Les applications modernes impliquent des réseaux de serveurs LLM traitant des tâches d'agents complexes, qui peuvent suivre des topologies de graphes acycliques orientés (DAG), des motifs fork-join, ou contenir un routage cyclique.

Les systèmes existants emploient des stratégies diverses (par exemple, FasterTransformer, vLLM, Orca, Sarathi-Serve) avec des priorités variables (préremplissage en premier vs décodage en premier) et des capacités de regroupement (mixte vs séparé). Les praticiens s'appuient actuellement sur des tests de référence coûteux et spécifiques à la charge de travail pour choisir des systèmes, sans garantie théorique de stabilité ou d'optimalité du débit.

Méthodologie

Les auteurs développent un cadre théorique des files d'attente rigoureux pour modéliser les systèmes d'inférence LLM.

1. Modélisation stochastique

Modèle de base : Le système est modélisé comme une chaîne de Markov à temps discret (DTMC) représentant une file d'attente à service par lot de deux classes.
- Classes : Les requêtes existent soit dans une file de préremplissage, soit dans une file de décodage.
- Regroupement : Le serveur traite un lot de tokens des deux files simultanément, soumis à un budget de tokens $b_{max}$ .
- Asymétrie : Les tokens de préremplissage d'une seule requête peuvent être traités en bloc, tandis que les tokens de décodage sont strictement séquentiels (un par requête par lot).
Modèle de temps de traitement : En s'appuyant sur des traces empiriques, le temps de traitement par lot $t_b$ est approximé par une fonction constante par morceaux dépendante de la charge en tokens $b$ :
$t_b = c + a \cdot \lceil b/b_0 \rceil$
où $c$ est le coût de base et $a$ le coût marginal par bloc de $b_0$ tokens. Ce modèle capture la dominance des calculs de couches linéaires dans l'inférence LLM.

2. Cadre analytique

Technique de limite fluide : Les auteurs emploient le cadre de la limite fluide (Dai 1995, Stolyar 1995) pour analyser la stabilité. Ils prouvent que, sous des conditions spécifiques, le processus stochastique mis à l'échelle converge vers un modèle fluide déterministe.
Définition de la stabilité : Un système est stable (récurrence positive) si le nombre total de tokens non traités ne diverge pas lorsque le temps tend vers l'infini.
Classe de planification : L'analyse se concentre sur les algorithmes conservateurs de travail (ceux qui remplissent le lot à la capacité $b_{max}$ chaque fois que possible) et introduit la condition K-FCFS (First-Come-First-Served avec dépassement borné) pour gérer les complexités du regroupement mixte.

3. Extensions

Le cadre est étendu à :

Serveurs parallèles : Systèmes avec équilibrage de charge (Aléatoire ou Join-the-Shortest-Queue).
Réseaux multi-classes : Serveurs uniques gérant plusieurs classes de requêtes (par exemple, différentes étapes d'agent).
Topologies de réseau : Réseaux multi-serveurs avec routage DAG et synchronisation fork-join.
Routage cyclique : Analyse des réseaux avec boucles de rétroaction (type Rybko–Stolyar).
Contraintes de taille de lot : Analyse des systèmes contraints à la fois par le budget de tokens ( $b_{max}$ ) et la taille maximale de lot ( $k_{max}$ ).

Contributions et résultats clés

1. Optimalité du débit des algorithmes de planification conservateurs de travail

L'article établit un principe de conception fondamental : les algorithmes de planification conservateurs de travail atteignent le débit maximal pour l'inférence LLM sur un serveur unique et pour les réseaux avec des topologies DAG ou fork-join.

Théorème 2 : Pour un serveur unique, si la charge d'arrivée $\lambda(m_p + m_d)$ est inférieure au taux de traitement maximal $b_{max}/t_{b_{max}}$ , tout algorithme K-FCFS conservateur de travail stabilise le système. Inversement, si la charge dépasse ce seuil, le système est instable sous n'importe quel algorithme.
Implication : Cela fournit une borne supérieure théorique ( $b_{max}/t_{b_{max}}$ ) et valide le virage de l'industrie vers des planificateurs conservateurs de travail.

2. Évaluation des systèmes existants

L'application du cadre théorique aux algorithmes réels produit des classifications claires :

Optimaux pour le débit (Conservateurs de travail) :
- Orca : Prend en charge le regroupement mixte (préremplissage + décodage) avec priorité au préremplissage.
- Sarathi-Serve : Prend en charge le préremplissage par blocs (chunked) avec priorité au décodage et regroupement mixte.
- Dernière version de vLLM (avec préremplissage par blocs) : Conservateur de travail.
Sous-optimaux/Instables (Non conservateurs de travail) :
- FasterTransformer : Priorise le décodage mais interdit le regroupement mixte. Il laisse le GPU inactif lorsque les requêtes de décodage sont insuffisantes pour remplir un lot, même si des requêtes de préremplissage sont en attente.
- vLLM standard (Vanilla) : Priorise le préremplissage mais interdit le regroupement mixte. Il laisse les requêtes de décodage en attente tout en traitant des lots uniquement de préremplissage.
Validation expérimentale : Des traces réelles confirment que les algorithmes non conservateurs de travail (FasterTransformer, vLLM standard) deviennent instables (explosion de la file d'attente) sous des charges modérées où les algorithmes conservateurs de travail (Sarathi-Serve, Orca) restent stables.

3. Charges de travail des agents IA et topologies de réseau

DAG et Fork-Join : L'article prouve que la planification conservatrice de travail reste optimale pour le débit dans les réseaux de serveurs LLM arrangés en DAG ou en topologies fork-join, à condition que la condition de charge soit satisfaite à chaque serveur.
Routage cyclique (Contre-exemple de Rybko–Stolyar) : Les auteurs démontrent que la planification conservatrice de travail n'est pas suffisante pour les réseaux avec routage cyclique. Ils construisent un réseau à deux serveurs où des affectations de priorités spécifiques sous une politique conservatrice de travail conduisent à l'instabilité, même lorsque la charge totale est inférieure à la capacité. Cela souligne la nécessité d'une conception soignée des priorités ou de politiques non conservatrices de travail (par exemple, rétropression) dans les topologies cycliques.

4. Impact des contraintes de taille de lot

Lorsqu'une contrainte de taille de lot maximale ( $k_{max}$ ) est imposée parallèlement au budget de tokens ( $b_{max}$ ) :

La région de stabilité devient un enveloppe convexe bidimensionnelle dans le plan $(\lambda_{prefill}, \lambda_{decode})$ , plutôt qu'un simple seuil scalaire.
Découverte contre-intuitive : Dans certains régimes (spécifiquement près d'un sommet de la région de stabilité impliquant des lots mixtes), les algorithmes strictement conservateurs de travail qui remplissent toujours jusqu'à $b_{max}$ peuvent échouer à stabiliser le système. Une stabilité optimale peut nécessiter de fonctionner à une charge de tokens inférieure (par exemple, $b_0$ ) pour équilibrer les taux de traitement des tokens de préremplissage et de décodage. Cela suggère que sous des contraintes de taille de lot strictes, des stratégies de planification adaptatives sont nécessaires.

Importance et affirmations

L'article prétend fournir la première fondation théorique des files d'attente rigoureuse pour la planification de l'inférence LLM. Son importance réside dans :

Principe de conception : Il identifie le « conservateur de travail » comme un principe de conception clé pour les praticiens, offrant une assurance théorique que des algorithmes comme Sarathi-Serve et Orca sont optimaux pour le débit, tout en mettant en garde contre les approches de regroupement non mixtes comme FasterTransformer et vLLM standard.
Pont entre les communautés : Il réduit la barrière pour la communauté de la théorie des files d'attente afin de contribuer aux systèmes LLM en fournissant un modèle formel qui capture les caractéristiques uniques de double phase et de regroupement des LLM.
Orientation pour les agents IA : Il étend l'analyse de stabilité aux charges de travail des agents IA, révélant que si les topologies DAG sont robustes, les topologies cycliques nécessitent une planification plus sophistiquée que de simples politiques conservatrices de travail.
Contraintes nuancées : Il révèle que des contraintes pratiques comme les limites de taille de lot peuvent fondamentalement altérer les régions de stabilité, remettant en question l'hypothèse selon laquelle « remplir le lot » est toujours optimal.

Les auteurs concluent que, bien que leur travail établisse une base pour l'optimalité du débit, les travaux futurs devront aborder l'optimisation de la latence, des modèles de temps de traitement plus riches (incorporant les couches d'attention) et la conception d'algorithmes adaptatifs pour des contraintes complexes et des topologies de réseau.