🤖 AI

Geometry-Aware Online Scheduling for LLM Serving: From Theoretical Bound to System Practice

Cet article propose un cadre d'ordonnancement en ligne sensible à la géométrie, présentant les algorithmes Smallest Volume First (SVF) et 1-bit SVF, qui améliorent théoriquement les ratios de compétitivité et améliorent pratiquement les performances de service des LLM en traitant plus efficacement l'empreinte mémoire 2D dynamique des caches Clé-Valeur que les heuristiques traditionnelles centrées sur le temps.

Auteurs originaux : Li Kong, Qi Qi, Yinyu Ye, Zijie Zhou

Publié 2026-06-23

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Li Kong, Qi Qi, Yinyu Ye, Zijie Zhou

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 gérez un café très fréquenté. Ce n'est pas n'importe quel café : c'est un établissement de haute technologie où chaque boisson que vous préparez nécessite une quantité spécifique d'espace sur le comptoir (mémoire) qui augmente au fur et à mesure que vous la préparez.

Dans le monde des modèles de langage étendus (LLM), ce « espace de comptoir » est appelé le KV Cache. Chaque fois que l'IA génère un mot (token), elle a besoin d'un peu plus de mémoire pour se souvenir de ce qu'elle vient de dire afin de maintenir la fluidité de la conversation. Si vous manquez d'espace sur le comptoir, tout le magasin doit s'arrêter.

Le Problème : L'erreur du « Plus court travail en premier » (Shortest Job First)

Pendant longtemps, les systèmes informatiques ont géré ces requêtes en utilisant une règle appelée Shortest Job First (SJF). La logique est simple : « Si un client commande un expresso rapide, laissez-le passer en premier car c'est rapide. Si quelqu'un commande un latte compliqué de 20 minutes, faites-le attendre. »

L'article soutient que dans le monde de l'IA, cette règle est en fait erronée. Voici pourquoi :

Le Piège : Dans un café normal, une commande courte occupe de l'espace pendant peu de temps. Mais dans un café d'IA, même une requête « courte » peut nécessiter un énorme espace de comptoir si le client demande une longue histoire.
La Réalité 2D : L'article affirme que nous devons regarder deux dimensions : le Temps (combien de temps cela prend) et l'Espace (quelle quantité de mémoire cela consomme à mesure qu'il croît). L'ancienne règle ne regardait que le temps.
Le Résultat : En privilégiant uniquement les tâches « rapides », le système se retrouve souvent encombré par des requêtes qui sont rapides à démarrer mais qui mangent toute la mémoire, bloquant ainsi tout le monde. C'est comme laisser un client commander un minuscule expresso, mais décider ensuite de s'asseoir au comptoir pendant une heure, bloquant ainsi le barista pour toutes les autres préparations.

La Solution : « Le plus petit volume en premier » (Smallest Volume First - SVF)

Les auteurs proposent une nouvelle règle appelée Smallest Volume First (SVF). Au lieu de demander : « À quelle vitesse est-ce ? », ils demandent : « Quel espace de comptoir total cette requête occupera-t-elle durant toute sa vie ? »

Pensez à charger un camion de déménagement :

L'ancienne méthode (SJF) : Vous chargez les plus petites boîtes en premier, en espérant qu'elles rentrent.
La nouvelle méthode (SVF) : Vous calculez le « volume » total de chaque objet (hauteur × largeur × profondeur) et vous chargez les articles qui occupent le moins d'espace total en premier.

En faisant cela, le système évite les embouteillages en évacuant rapidement les requêtes qui ont une empreinte mémoire totale « petite ». Cela libère de l'espace pour que les requêtes plus importantes puissent commencer plus tôt, empêchant ainsi le système entier de se bloquer.

L'astuce du « Un-bit » (1-bit SVF)

Prédire exactement combien de temps une conversation va durer est difficile. C'est comme essayer de deviner exactement combien de mots un client dira avant de s'arrêter de parler. L'article introduit un raccourci ingénieux appelé 1-bit SVF.

Au lieu d'essayer de prédire le nombre exact de mots, le système pose simplement une question simple : « Est-ce une requête courte ou une requête longue ? » (Oui/Non).

Il utilise une infime quantité d'information (juste un « bit ») pour catégoriser la requête.
Étonnamment, l'article montre que cette simple supposition est presque aussi efficace qu'une prédiction complexe. C'est comme si un barista demandait simplement : « Est-ce un café rapide ou une boisson longue ? » et prenait des décisions basées sur cette simple réponse. Cela économise beaucoup de puissance cérébrale (puissance de calcul) tout en maintenant la file d'attente fluide.

Ce que l'article a prouvé

Les auteurs n'ont pas seulement supposé que cela fonctionnerait ; ils ont fait les calculs pour le prouver :

Les Mathématiques : Ils ont montré que dans les scénarios les plus défavorables (comme un coup de rush soudain), leur nouvelle méthode est garantie d'être bien meilleure que l'ancienne méthode « Shortest Job First ». Ils ont resserré la garantie mathématique, passant d'un potentiel 48 fois pire que la perfection à seulement 5 fois pire.
Le Test : Ils ont testé cela sur de vrais modèles d'IA (Llama-3.1) en utilisant un système populaire appelé vLLM.
- Résultat : La nouvelle méthode a rendu l'IA plus rapide pour tout le monde, en particulier pour les requêtes les plus lentes (réduisant la « latence de queue » ou tail latency).
- Efficacité : La version « 1-bit » était incroyablement légère, n'ajoutant presque aucun délai au système tout en étant très performante.

Résumé

En termes simples, cet article dit : Arrêtez de juger les requêtes d'IA uniquement par la rapidité avec laquelle elles se terminent. Jugez-les par l'espace mémoire qu'elles occupent pendant qu'elles sont actives. En passant à une stratégie de « Plus petit volume en premier », et même en utilisant une supposition très simple de type « court vs long », nous pouvons rendre les chatbots d'IA plus rapides, plus fluides et moins susceptibles de planter sous des charges lourdes.

Résumé Technique : Ordonnancement en Ligne Sensible à la Géométrie pour le Service de LLM

Énoncé du Problème

Le déploiement des grands modèles de langage (LLM) dans des scénarios interactifs fait face à un goulot d'étranglement critique : la gestion de l'empreinte mémoire dynamique du cache KV (Key-Value). Contrairement aux problèmes d'ordonnancement traditionnels où la taille des tâches est statique, l'inférence de LLM présente une croissance géométrique spatio-temporelle 2D unique.

Couplage Mémoire-Temps : Dans le décodage autorégressif, le temps d'exécution est linéairement couplé à l'expansion de la mémoire ; chaque jeton généré augmente l'empreinte du cache KV.
Dynamique de Batching Continu : Les moteurs modernes (par exemple, vLLM) utilisent le batching continu, où la taille du lot simultané fluctue dynamiquement après chaque étape de décodage, à mesure que les requêtes se terminent et que de nouvelles entrent.

Les heuristiques d'ordonnancement existantes, principalement le Shortest Job First (SJF - Travail le plus court en premier), sont ancrées dans une modélisation classique centrée sur le temps. Elles ne parviennent pas à capturer la réalité géométrique du service de LLM. Des travaux théoriques récents [10] ont démontré que sous ces contraintes géométriques spécifiques, le SJF produit un ratio de compétitivité (competitive ratio) pire cas non borné, créant un écart fondamental entre la théorie classique de l'ordonnancement et les réalités physiques de l'inférence moderne de LLM.

Méthodologie

Les auteurs proposent un cadre d'Ordonnancement en Ligne Sensible à la Géométrie qui déplace la métrique de priorité de la durée d'exécution 1D vers le volume de mémoire 2D.

Algorithme Central : Smallest Volume First (SVF - Le plus petit volume en premier)

Au lieu d'isoler le temps d'exécution, le SVF évalue l'intégrale de la consommation de mémoire sur l'ensemble du cycle de vie d'une requête. Pour une requête $r_i$ avec une longueur de prompt $s_i$ et une longueur de sortie $o_i$ , le Volume $v_i$ est défini par :
$v_i = s_i \cdot o_i + \frac{o_i^2 + o_i}{2}$
Cette formule quantifie l'aire totale de "mémoire-temps" occupée par la requête. Le SVF agit comme une politique strictement gourmande, triant les requêtes par ordre croissant de $v_i$ . L'implémentation est découpée en deux processus : un prédicteur en arrière-plan qui regroupe les requêtes pour interroger les longueurs de sortie, et un ordonnanceur qui admet les requêtes de priorité la plus haute (plus petit volume) dans le lot en cours jusqu'à ce que la capacité du cache KV soit atteinte.

Variante Légère : 1-bit SVF

Pour minimiser la surcharge de calcul, les auteurs introduisent le 1-bit SVF. Cette variante remplace la prédiction exacte de la longueur par un classificateur binaire qui catégorise les requêtes comme "courtes" ( $m=0$ ) ou "longues" ( $m=1$ ).

Il assigne une longueur proxy globale $O_m$ à chaque classe.
Le volume proxy est calculé comme $\hat{v}_i = s_i \cdot O_m + \frac{O_m^2 + O_m}{2}$ .
Cette conception n'extrait qu'un seul bit d'information tout en préservant les garanties d'ordonnancement spatio-temporelles fondamentales.

Contributions Théoriques

Le papier fournit un fondement mathématique rigoureux, allant au-delà de l'essai empirique pour proposer des garanties formelles :

Bornes de Pire Cas Resserrées (Arrivées par Rafales) :
- Pour le SVF avec des longueurs de sortie connues sous des modèles d'arrivées par rafales, les auteurs prouvent un ratio de compétitivité (CR) de pire cas de CR $\le$ 5. Cela resserre considérablement l'ancien seuil de CR $\le$ 48 trouvé dans la littérature antérieure [10].
- La preuve utilise une nouvelle méthodologie de "certificat macroscopique", montrant que chaque étape bloquée implique une masse de mémoire active $> M/2$ , alignant directement le temps d'attente de l'algorithme sur la borne inférieure de l'ordonnancement hors ligne optimal.
- Pour le 1-bit SVF, le ratio de compétitivité est borné par $O(T)$ , où $T$ est la longueur maximale du modèle, prouvant que même avec un minimum d'informations, le système reste stable sous des charges extrêmes.
Bornes Stochastiques (Arrivées de Poisson) :
- Sous des processus d'arrivée de Poisson, le papier dérive des ratios de compétitivité attendus.
- Le SVF atteint $E[CR] \le 1 + \frac{4}{(1-\mu)(1-\rho)}$ , où $\mu$ est lié à la distribution géométrique des longueurs et $\rho$ est l'utilisation du système.
- La dégradation des performances du 1-bit SVF est montrée comme étant gouvernée par une "pénalité de distorsion volumétrique" $\epsilon$ , qui décroît exponentiellement avec le seuil de classification, assurant une stabilité à long terme.

Résultats Expérimentaux

L'approche a été implémentée comme une couche "plug-and-play" au sein de vLLM et évaluée sur les modèles Llama-3.1-8B et Llama-3.1-70B en utilisant les charges de travail LMSYS-Chat et LongBench.

Réduction de la Latence : Le SVF a systématiquement obtenu les latences moyennes et de queue (P95) les plus basses sur tous les benchmarks, surpassant le FCFS, le SJF et même l'Oracle-SJF (qui possède une connaissance parfaite des longueurs futures) dans les scénarios gourmands en mémoire (LongBench).
Débit (Throughput) : Le SVF a maintenu un débit plus élevé que le SJF. Le 1-bit SVF a obtenu un débit et une latence compétitifs, surpassant souvent le SJF en termes de latence de queue.
Surcharge (Overhead) : La surcharge de prédiction était négligeable. Le prédicteur de longueur complète a consommé au plus 0,06 % de la latence de bout en bout, tandis que le classificateur 1-bit a consommé $\le$ 0,01 %.
Équité (Fairness) : Contrairement aux heuristiques gourmandes classiques qui affament les tâches longues, la gourmandise géométrique du SVF libère rapidement la mémoire du cache KV bornée, brisant le blocage de tête (head-of-line blocking) global et améliorant l'équité pour les requêtes plus importantes.

Signification et Revendications

Le papier affirme établir une approche théoriquement saine et empiriquement prouvée pour résoudre l'ordonnancement contraint par la mémoire dans les déploiements modernes de LLM. Sa principale signification réside dans :

Changement de Paradigme : Il déplace le domaine des héritages d'heuristiques 1D centrées sur le temps vers une priorisation 2D sensible à la géométrie, traitant l'incompatibilité fondamentale entre la théorie classique de l'ordonnancement et la mécanique d'inférence des LLM.
Avancée Théorique : En resserrant le ratio de compétitivité de 48 à 5 et en introduisant une nouvelle méthodologie de preuve, il fournit des garanties structurelles universelles qui tiennent à travers des distributions de charges de travail arbitraires et adverses.
Viabilité Pratique : La nature "plug-and-play" de l'ordonnanceur, combinée à l'extrême efficacité de la variante 1-bit, démontre qu'une optimisation mathématique rigoureuse peut être intégrée de manière transparente dans des moteurs d'inférence haute performance sans surcharge prohibitive.

Les auteurs concluent que cette approche sensible à la géométrie non seulement optimise l'efficacité du système, mais offre également des implications pour le déploiement durable de l'IA en réduisant les ressources computationnelles et l'empreinte carbone nécessaires pour l'inférence à grande échelle.