Robust Batch-Level Query Routing for Large Language Models under Cost and Capacity Constraints

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

🚀 Le Problème : Le Chaos du Restaurant de l'IA

Imaginez que vous êtes le chef d'un restaurant très populaire qui utilise des cuisiniers de tous niveaux :

Les apprentis : Rapides, peu chers, mais ils font des erreurs sur les plats complexes.
Les chefs étoilés : Incroyables, mais très lents et très chers.

Dans le monde actuel des "Grands Modèles de Langage" (les IA comme moi), la plupart des systèmes fonctionnent comme un serveur individuel. Dès qu'un client arrive (une question), le serveur regarde le menu et décide : "Est-ce que je donne cette commande à l'apprenti ou au chef ?".

Le problème ?

L'effet de groupe : En réalité, les commandes n'arrivent pas une par une. Elles arrivent par paquets (des "lots" ou batches). Si 50 clients arrivent en même temps et que le serveur envoie tous les plats difficiles au chef étoilé, la cuisine explose ! Le chef est débordé, les plats brûlent, et la facture devient astronomique.
L'incertitude : Parfois, le serveur se trompe sur la difficulté du plat. Il pense que c'est simple et l'envoie à l'apprenti, mais l'apprenti rate le plat.
Le manque de ressources : Vous avez un nombre limité de cuisiniers (des cartes graphiques/GPU). Si vous engagez trop de chefs, vous n'avez plus de place pour les apprentis, et vice-versa.

💡 La Solution : Le "Chef de Cuisine" Intelligent (Routing par Lots)

Les auteurs de ce papier proposent de changer de méthode. Au lieu de décider pour chaque client individuellement, ils proposent de regarder tout le groupe de commandes d'un coup et de faire un plan d'attaque global.

Ils utilisent une sorte de tableau de calcul magique (un programme mathématique appelé "Programmation Linéaire en Nombres Entiers") qui répond à trois questions en même temps pour tout le groupe :

Qui doit cuisiner quoi pour que le résultat soit le meilleur ?
Comment ne pas dépasser notre budget ?
Comment ne pas surcharger nos cuisiniers ?

C'est comme si, au lieu de laisser chaque serveur décider au cas par cas, un maître d'hôtel prenait le groupe entier, regardait le budget total et la capacité de la cuisine, et répartissait les tâches de manière optimale : "Toi, tu fais les salades simples. Toi, tu fais les sauces complexes. Toi, tu aides le chef sur les plats spéciaux."

🛡️ L'Innovation : La "Ceinture de Sécurité" (Approche Robuste)

Le papier introduit une idée géniale : la robustesse.

Imaginez que votre estimation de la difficulté d'un plat n'est pas parfaite. Peut-être que l'apprenti est fatigué aujourd'hui, ou que le chef a un rhume.

La méthode classique : Elle dit "C'est sûr, l'apprenti peut le faire !" et l'envoie. Si l'apprenti échoue, catastrophe.
La méthode robuste de ce papier : Elle dit "Attends, il y a un risque que l'apprenti échoue. Mieux vaut être prudent et lui donner un plat un peu plus simple, ou envoyer un chef plus expérimenté pour être sûr."

En mathématiques, au lieu de viser le "meilleur résultat possible", ils visent le "pire scénario acceptable". Ils s'assurent que même si tout va mal (estimations erronées), le système ne s'effondre pas et reste performant. C'est comme conduire avec une ceinture de sécurité : vous espérez ne jamais avoir d'accident, mais vous êtes prêt au pire.

🏗️ L'Infrastructure : Choisir ses Cuisiniers (Allocation des Ressources)

Avant même d'ouvrir le restaurant, les auteurs se posent une question cruciale : "Combien de cuisiniers de chaque type dois-je embaucher ?"

Si j'engage 100 apprentis, je peux servir beaucoup de monde, mais les plats seront moyens.
Si j'engage 10 chefs, les plats seront parfaits, mais je ne pourrai servir que quelques clients à la fois.

Le papier propose un algorithme pour trouver le juste équilibre avant même que les clients n'arrivent. Il calcule le nombre idéal de "cuisiniers" (serveurs d'IA) à allouer pour chaque type de modèle, en fonction de ce que les clients commandent habituellement.

📊 Les Résultats : Pourquoi c'est génial ?

Les tests montrent que cette nouvelle méthode est bien supérieure :

Moins de gaspillage : On ne dépasse jamais le budget, même quand les commandes arrivent en foule (situation "adverse").
Plus de qualité : En gérant les groupes intelligemment, on obtient des réponses meilleures (jusqu'à 24% de mieux dans les pires cas) que les méthodes actuelles.
Plus de sécurité : L'approche "robuste" évite les catastrophes quand les prédictions sont incertaines.

En Résumé

Ce papier dit : "Arrêtez de décider au fil de l'eau pour chaque question. Prenez un moment, regardez le groupe entier, calculez le meilleur plan possible en tenant compte de l'argent, de la fatigue des machines et des imprévus, et exécutez ce plan."

C'est passer d'une gestion de restaurant chaotique et réactive à une gestion de restaurant de luxe, fluide, prévoyante et parfaitement optimisée.

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

1. Problématique

L'article aborde les défis du routage des requêtes vers des Grands Modèles de Langage (LLM) dans des systèmes de production réels. Bien que le routage par requête (per-query) soit courant, les auteurs identifient plusieurs limitations majeures dans les environnements industriels :

Contrôle insuffisant des coûts par lot : Les méthodes actuelles optimisent chaque requête individuellement (en maximisant $l(q, m_j) - \lambda \cdot c(q, m_j)$ ). Cependant, dans la pratique, l'inférence LLM repose sur le batching (regroupement de requêtes) pour optimiser l'utilisation du matériel (GPU). Le routage individuel ne garantit pas que le coût total d'un lot respecte un budget strict, ce qui peut entraîner des dépassements de coûts ou une sous-utilisation des ressources, surtout lors de "batches adversariaux" (regroupement de requêtes difficiles).
Ignorance des contraintes de capacité : Les systèmes réels combinent des modèles hébergés localement (limités par le nombre de GPU et la capacité de concurrence) et des modèles cloud (limités par le coût monétaire). Le routage individuel ignore souvent ces contraintes de capacité globales.
Incertitude des estimations : Les estimateurs de performance (prédisant la qualité d'une réponse) sont bruités. Une décision basée sur une estimation ponctuelle peut conduire à un échec catastrophique si l'estimation est surestimée.

2. Méthodologie

Les auteurs proposent un cadre de routage au niveau du lot (batch-level) basé sur la Programmation Linéaire en Nombres Entiers (ILP) et l'Optimisation Robuste.

A. Formulation du Routage par Lot (Online)

Au lieu de router requête par requête, le système résout un problème d'optimisation pour un lot de $N$ requêtes et $M$ modèles disponibles.

Objectif : Maximiser la qualité moyenne de routage sur le lot.
Contraintes :
- Coût : Le coût total du lot ne doit pas dépasser un budget global $N \cdot C$ .
- Capacité : Le nombre de requêtes routées vers un modèle $j$ ne doit pas dépasser sa capacité totale ( $l_j \cdot I_j$ , où $I_j$ est le nombre d'instances et $l_j$ la capacité par instance).
- Assignation : Chaque requête doit être assignée à exactement un modèle.

Ce problème est formulé comme un ILP, résolu efficacement par des solveurs modernes (comme SCIP) en quelques millisecondes.

B. Optimisation Robuste

Pour gérer l'incertitude des estimations de performance ( $a_{i,j}$ ), les auteurs introduisent une variante robuste :

Au lieu d'utiliser une estimation ponctuelle, ils définissent un intervalle de prédiction $[ \underline{a}_{i,j}, \overline{a}_{i,j} ]$ .
L'objectif est de maximiser la pire des performances possibles (worst-case) dans cet intervalle.
Concrètement, cela revient à utiliser la borne inférieure ( $\underline{a}_{i,j}$ ) de l'intervalle de confiance (obtenu par bootstrap ou conformal prediction) dans la fonction objectif. Cela évite de surconfiance dans des modèles dont la performance est incertaine.

C. Allocation Offline des Instances (Offline)

Avant le déploiement en ligne, une étape d'optimisation offline détermine le nombre optimal d'instances ( $I_j$ ) à allouer à chaque modèle (notamment pour les modèles open-source hébergés localement).

Cette étape simule le comportement du routeur sur des lots de calibration.
Elle optimise l'allocation des ressources GPU pour maximiser la performance globale tout en respectant les contraintes de coût et de capacité, comblant ainsi le fossé entre la planification des ressources et le routage en ligne.

3. Contributions Clés

Identification des lacunes du routage individuel : Mise en évidence de l'incapacité des méthodes actuelles à contrôler les coûts par lot et à gérer les contraintes de capacité hétérogènes (local vs cloud).
Cadre de routage robuste par lot : Introduction d'un framework ILP qui optimise simultanément la qualité, le coût et la capacité, tout en intégrant l'incertitude via l'optimisation robuste.
Optimisation de l'allocation des ressources : Proposition d'une méthode pour déterminer dynamiquement le nombre d'instances de modèles à déployer avant l'inférence, en fonction de la distribution des données.
Validation empirique extensive : Démonstration que cette approche surpasse les méthodes de l'état de l'art (comme MIRT, kNN, XGBoost non robustes) sur deux benchmarks multi-tâches.

4. Résultats Expérimentaux

Les expériences ont été menées sur deux ensembles de données (Dataset 1 et Dataset 2) couvrant diverses tâches (MMLU, GSM8K, etc.) et plusieurs modèles (GPT-4, Llama, DeepSeek, etc.).

Performance de l'estimation robuste :
- L'utilisation de l'estimateur XGBoost robuste améliore la précision de 1 % à 14 % par rapport aux versions non robustes, selon l'estimateur de base et le jeu de données.
- Le routage robuste favorise systématiquement les modèles avec une incertitude de prédiction plus faible, réduisant ainsi le risque de mauvaise performance.
Routage par lot vs. Routage individuel :
- Sous un batching aléatoire, le routage par lot améliore les performances jusqu'à 4 % (Dataset 1) et 1,7 % (Dataset 2).
- Sous un batching adversarial (regroupement de requêtes difficiles), l'amélioration est spectaculaire, atteignant jusqu'à 24 % sur le Dataset 1 et 15,8 % sur le Dataset 2. Le routage individuel échoue souvent à respecter les budgets dans ces scénarios.
Allocation optimisée des instances :
- L'allocation offline optimisée des instances de modèles (GPU) par rapport à une allocation fixe et uniforme apporte un gain supplémentaire de 2,7 % à 3,2 % de performance.
- Cela permet de mieux équilibrer l'utilisation des petits modèles efficaces et des grands modèles performants selon le budget disponible.
Efficacité des ressources :
- Pour atteindre la même performance que le modèle le plus performant (DeepSeek_Chat), la méthode d'optimisation complète nécessite 177 GPU de moins (et un coût réduit) que l'utilisation exclusive de ce modèle.

5. Signification et Impact

Ce travail marque un changement de paradigme dans le déploiement des LLM :

Passage de l'individuel au collectif : Il démontre que l'optimisation doit se faire au niveau du lot pour respecter les contraintes réelles de l'infrastructure (coûts, GPU, latence).
Robustesse opérationnelle : En intégrant l'incertitude directement dans la fonction de décision, le système devient plus fiable en production, évitant les pannes de qualité lors de pics de charge ou de distributions de requêtes défavorables.
Efficacité économique : La combinaison du routage par lot et de l'allocation dynamique des ressources permet de réduire significativement les coûts d'infrastructure tout en maintenant, voire en améliorant, la qualité de service.

Bien que l'article note certaines limites (hypothèses de batchs fixes, distribution stationnaire, absence d'interactions multi-tours), il fournit une base solide pour des systèmes de routage LLM industriels plus stables, économiques et résilients.