🔢 mathematics

Online Linear Programming for Multi-Objective Routing in LLM Serving

Cet article propose un cadre de programmation linéaire en ligne fondé sur la science, avec un contrôle par prix d'enchère et des mises à jour duales avec amorçage à chaud, afin d'optimiser le routage multi-objectif dans le service de LLM, démontrant une performance de latence et de débit supérieure par rapport aux approches heuristiques traditionnelles.

Auteurs originaux : Zixi Chen, Yinyu Ye, Zijie Zhou

Publié 2026-07-07

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Zixi Chen, 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 dirigez la cuisine d'un restaurant haut de gamme et très fréquenté. Cette cuisine possède plusieurs postes de cuisson parallèles (les GPU), et des clients (les requêtes d'IA) arrivent les uns après les autres.

Dans une cuisine normale, vous enverriez simplement la commande suivante au premier chef disponible. Mais dans ce "restaurant d'IA" spécifique, les choses sont délicates :

Les commandes sont étranges : Certaines commandes sont des amuse-bouches rapides (texte court), tandis que d'autres sont des repas massifs et complexes qui prennent beaucoup de temps à cuisiner (génération de texte long). Vous ne savez pas exactement combien de temps une commande prendra avant qu'elle ne soit déjà en train de cuire.
L'espace est restreint : Chaque chef a un espace de comptoir limité (mémoire) et ne peut tenir qu'un certain nombre d'assiettes sur son réchaud à la fois (taille de lot ou "batch size"). Si vous mettez trop d'assiettes sur un seul réchaud, tout le poste de travail s'effondre.
Les clients sont exigeants : Certains clients veulent leur nourriture immédiatement (faible latence), tandis que d'autres veulent simplement savoir que la cuisine est occupée et efficace (haut débit). Parfois, vous devez choisir : servir un client super rapidement, ou servir dix clients un peu plus lentement ?

Le problème avec les anciennes méthodes
La plupart des cuisines aujourd'hui utilisent des règles simples, comme "envoyer la commande au chef qui a la ligne la plus courte" ou "l'envoyer au chef qui est actuellement libre". Le papier soutient que ces règles sont comme utiliser un marteau pour réparer une montre. Elles ne comprennent pas la valeur de la commande ou le coût de l'espace qu'elle occupe. Elles ne peuvent pas facilement équilibrer le besoin de vitesse par rapport au besoin de faire fonctionner la cuisine de manière fluide.

La nouvelle solution : Le système de l'« Étiquette de Prix Intelligente »
Les auteurs proposent une nouvelle façon de gérer la cuisine en utilisant un concept de Programmation Linéaire en Ligne. Considérez cela comme un système d'« Étiquette de Prix Intelligente » pour chaque pouce de l'espace de comptoir et chaque minute du temps d'un chef.

Voici comment cela fonctionne, étape par étape :

1. Le Prix de l'Ombre (Le « Coût d'Opportunité »)

Imaginez que chaque emplacement sur le réchaud d'un chef possède une "étiquette de prix" cachée attachée à lui. Ce n'est pas de l'argent ; c'est un Prix de l'Ombre (Shadow Price).

Si un réchaud est encombré et manque d'espace, l'étiquette de prix augmente. Cela dit au routeur : "Faites attention ! Utiliser cet espace maintenant pourrait signifier que nous ne pourrons pas cuisiner un énorme repas important plus tard."
Si un réchaud est vide, l'étiquette de prix est basse. Il est bon marché de l'utiliser en ce moment.

2. La Décision (Bénéfice vs Coût)

Lorsqu'une nouvelle commande de client arrive, le routeur ne regarde pas seulement qui est libre. Il effectue un calcul rapide :

Le Bénéfice : À quel point ce client sera-t-il satisfait ? (Recevra-t-il sa nourriture rapidement ? Cela aidera-t-il l'efficacité globale de la cuisine ?)
Le Coût : Quel est la somme des "Prix de l'Ombre" de l'espace dont cette commande a besoin ?

La Règle : Si le Bénéfice est supérieur au Coût, le routeur dit : "Oui, cuisinez ceci !" Si le Coût est trop élevé (le réchaud est trop cher en ce moment), le routeur peut dire : "Attendez dans la file" ou envoyer la commande vers un autre réchaud, moins cher.

3. Apprendre à la volée (Le « Warm Start »)

La cuisine est chaotique. Les "étiquettes de prix" changent chaque seconde à mesure que de nouvelles commandes arrivent et que les anciennes se terminent.

Les anciennes méthodes essaieraient de recalculer le plan parfait à partir de zéro chaque fois qu'une nouvelle commande arrive. Cela prend trop de temps (comme essayer de résoudre un puzzle géant pendant que la nourriture brûle).
Cette nouvelle méthode utilise une Mise à jour Intelligente. Elle se souvient des prix de la seconde précédente et effectue un petit ajustement rapide (un "warm start") basé sur ce qui vient de se passer. C'est comme un chef qui connaît le rythme général de la cuisine et qui ajuste simplement légèrement ses mouvements pour la nouvelle commande, plutôt que de réapprendre à cuisiner à chaque fois.

4. Le Menu Multi-Objectifs

Le meilleur aspect est que le gestionnaire de cuisine peut changer le "menu" des objectifs instantanément sans reconstruire la cuisine.

Besoin de vitesse ? Le gestionnaire augmente le "prix" du temps d'attente. Le routeur donnera la priorité à la sortie rapide de la nourriture, même si la cuisine devient un peu encombrée.
Besoin d'efficacité ? Le gestionnaire augmente le "prix" de l'espace gaspillé. Le routeur emboîtera les commandes de manière serrée pour en faire plus, même si certains clients attendent un peu plus longtemps.
Besoin de corriger les clients les plus lents ? Le gestionnaire peut dire au système de protéger spécifiquement la "queue" (les 1 % de commandes les plus lentes) afin que personne ne soit laissé de côté.

Les Résultats

Les auteurs ont testé ce système d'« Étiquette de Prix Intelligente » dans une simulation d'une cuisine d'IA massive. Ils l'ont comparé aux anciennes règles de "ligne la plus courte".

Le Résultat : Le nouveau système était bien meilleur pour équilibrer les compromis. Il pouvait rendre la cuisine plus rapide ou plus efficace selon ce que le gestionnaire voulait, sans casser le système.
La Vue d'Ensemble : Le papier affirme qu'utiliser cette approche mathématique "scientifique" est supérieur aux heuristiques de "tâtonnement" actuellement utilisées dans la plupart des systèmes d'IA. Cela donne au système un cerveau qui comprend le véritable coût des ressources, plutôt que de simplement suivre une règle simple.

En bref : Au lieu d'envoyer aveuglément les commandes au premier chef disponible, ce système agit comme un gestionnaire intelligent qui sait exactement ce que chaque seconde de temps et chaque pouce d'espace de comptoir valent réellement, garantissant que la cuisine fonctionne parfaitement, peu importe l'intensité de l'affluence.

Résumé Technique : Programmation Linéaire en Ligne pour le Routage Multi-Objectif dans le Service de LLM

1. Énoncé du Problème

L'article traite du défi du routage de requêtes en ligne dans les systèmes de service de modèles de langage de grande taille (LLM). Dans ces systèmes, les requêtes entrantes doivent être réparties vers des travailleurs de décodage parallèles sous des contraintes strictes :

Contraintes Temporelles Liées : Les requêtes consomment des ressources (emplacements de batch et mémoire KV-cache) de manière continue sur toute leur durée de décodage. Une requête admise à l'instant $t$ occupe une capacité jusqu'à sa complétion, créant un problème d'allocation de ressources complexe et dépendant du temps.
Compromis Multi-Objectifs : Les systèmes doivent équilibrer des objectifs de niveau de service (SLO) concurrents, notamment le débit, la latence de bout en bout (EEL), le temps jusqu'au premier jeton (TTFT) et la latence de queue (ex: 99e percentile). Ces objectifs sont souvent en tension ; par exemple, maximiser le débit via un batching agressif dégrade souvent la latence.
Limites des Heuristiques Actuelles : Les systèmes de production existants (ex: vLLM) et les simulateurs (ex: Vidur) reposent sur des heuristiques telles que le Round-Robin, le Join-Shortest-Queue (LOR) ou le Power-of- $d$ choices. Ces méthodes manquent d'objectifs d'optimisation explicites, offrent un contrôle limité sur les compromis SLO et ne tiennent pas compte de la nature hétérogène et incertaine des longueurs de décodage des LLM.

2. Méthodologie

Les auteurs proposent un cadre qui formule le routage de LLM comme un problème de Programmation Linéaire en Ligne (OLP), en exploitant les techniques de recherche opérationnelle pour dériver une politique de contrôle efficace sur le plan computationnel.

A. Formulation Mathématique

Modèle : Le système est modélisé sur un horizon de temps discret avec des dispositifs de décodage parallèles. Les requêtes arrivent séquentiellement avec des empreintes de prefill connues et des longueurs de décodage prédites (mais potentiellement inexactes).
Contraintes : La formulation impose deux contraintes critiques par dispositif et par pas de temps :
1. Taille de Batch : Un nombre maximum de requêtes actives ( $B$ ).
2. Capacité du KV-Cache : Un budget mémoire maximum ( $M$ ) pour les requêtes actives.
Fonction d'Objectif : Les auteurs définissent une fonction de récompense linéaire pour chaque décision de routage $(j, g, k)$ $(j, g, k)$ (assigner la requête $j$ $j$ au dispositif $g$ $g$ à l'instant $k$ $k$ ). Cette récompense est une somme pondérée de :
- Débit (jetons traités).
- Latence négative (minimisation de l'EEL et du TTFT).
- Requêtes par seconde (QPS).
- Métriques de queue (modélisées via des récompenses indicatrices pour les requêtes respectant des limites de latence spécifiques).
- Insight Clé : Les métriques agrégées comme la latence de queue sont décomposées en incitations par requête via des fonctions indicatrices, permettant de les optimiser au sein d'un cadre linéaire.

B. Conception d'Algorithme : Contrôle par Prix d'Enchère (Bid-Price Control)

Résoudre l'OLP complet à chaque milliseconde est informatiquement irréalisable. Au lieu de cela, les auteurs dérivent une politique de Contrôle par Prix d'Enchère basée sur la dualité LP :

Variables Duales (Prix de l'Ombre) : Les variables duales $p_i$ représentent le "prix de l'ombre" ou le coût d'opportunité des ressources (emplacements de batch et KV-cache) à des moments et dispositifs spécifiques. Des prix d'ombre élevés indiquent une congestion anticipée.
Règle de Décision : Une requête est admise si son bénéfice pondéré par le SLO dépasse son coût de ressource imputé (calculé comme le produit scalaire du vecteur d'utilisation des ressources et des prix d'ombre actuels).
Apprentissage en Ligne (SAA) : Pour gérer la nature stochastique des arrivées et des prédictions, les prix d'ombre sont appris en ligne à l'aide d'une approche d'Approximation Moyenne par Échantillonnage (SAA). L'objectif dual est minimisé sur un historique d'actions observées.
Mises à Jour Efficaces : Pour répondre aux latences de décision de l'ordre de la milliseconde, les auteurs emploient une descente de gradient par mini-lots projetée et avec redémarrage (warm-started). Au lieu de résoudre le problème dual à partir de zéro, l'algorithme met à jour le vecteur de prix de manière incrémentielle sur la base d'un petit lot de données historiques. Cela garantit un temps d'exécution prévisible (1–2 ms par période sur un CPU).

3. Contributions Clés

Cadre d'Optimisation Multi-Objectif : Le premier cadre formulant le routage de LLM comme une OLP avec des contraintes de batch et de KV-cache explicitement liées au temps. Il décompose les SLO agrégés (y compris la latence de queue) en récompenses par requête adaptées à l'optimisation en ligne.
Algorithme de Prix d'Enchère Efficace : Une politique calculable qui suit l'évolution des prix d'ombre duaux en ligne sans résoudre un LP complet à chaque étape, répondant aux exigences de latence strictes du service de LLM.
Contrôle de Compromis Interprétable : Le cadre fournit aux opérateurs des "boutons" transparents (poids d'objectifs) pour déplacer systématiquement la performance le long de la frontière de Pareto. Les prix d'ombre servent également d'outils de diagnostic pour identifier si les emplacements de batch ou le KV-cache sont les goulots d'étranglement actuels.

4. Résultats Expérimentaux

Les auteurs ont intégré leur routeur dans le simulateur Vidur et l'ont évalué par rapport à des bases de référence standards (Round-Robin, LOR, Random, Power-of-2) sous diverses charges de travail (données réelles LMSYS-Chat-1M et ratios P/D synthétiques).

Gains de Performance : La méthode proposée a démontré des améliorations substantielles par rapport aux bases de référence dans plusieurs régimes SLO.
- Dans des scénarios de prédiction bruités (erreur de 20 %), l'algorithme a obtenu une réduction de 45,75 % de l'EEL moyenne et une réduction de 42,49 % de l'EEL P95 par rapport au Round-Robin.
- Il a nettement surpassé les heuristiques pour les métriques de latence de queue (EEL P99 et TTFT).
Robustesse : La politique est restée efficace même avec des prédictions de longueur de décodage imparfaites, car les mises à jour de prix en ligne s'adaptent aux erreurs d'estimation.
Adaptabilité : Dans des charges de travail non stationnaires (pics de charge soudains), le routeur s'est adapté rapidement grâce à un mécanisme de fenêtre glissante pour les mises à jour de l'historique, maintenant une performance supérieure.
Réglage des Poids : Les expériences ont confirmé qu'ajuster les poids d'objectifs permet aux opérateurs de prioriser des métriques spécifiques (ex: minimiser la latence moyenne vs contrôler strictement la latence de queue) avec des résultats prévisibles.

5. Signification et Revendications

L'article affirme qu'une approche d'optimisation basée sur la science surpasse le routage basé sur des heuristiques dans le service de LLM.

Pont entre Communautés : Il établit un pont principled entre la communauté de la recherche opérationnelle (allocation de ressources en ligne, contrôle par prix d'enchère) et la communauté des systèmes de LLM.
Aperçus de Conception de Système : Le cadre révèle des informations structurelles, telles que l'utilisation des prix d'ombre pour diagnostiquer les goulots d'étranglement des ressources (batch vs mémoire) et permettre un contrôle d'admission sensible aux SLO lors de la surcharge.
Applicabilité Pratique : Bien qu'une intégration complète en production soit notée comme un travail futur, les résultats démontrent que le routage basé sur l'optimisation est réalisable à l'échelle de la milliseconde et fournit une base pour la conception systématique de politiques plutôt que pour un réglage ad hoc.

Les auteurs restent modestes quant au déploiement immédiat en production, reconnaissant les défis tels que l'intégration avec les moteurs de service (ex: vLLM), la gestion de la préemption et la coordination dans des environnements distribués. Cependant, ils affirment que le cadre fournit une base nécessaire pour la recherche future à l'intersection de la recherche opérationnelle et des systèmes d'apprentissage automatique.