🤖 machine learning

Requests of a Feather Must Flock Together: Batch Size vs. Prefix Homogeneity in LLM Inference

Cet article présente Feather, un ordonnanceur sensible aux préfixes basé sur l'apprentissage par renforcement qui optimise le compromis entre la taille des lots et l'homogénéité des préfixes en utilisant une Arbre de Hachage par Morceaux léger, permettant d'atteindre un débit d'inférence de LLM 2 à 10 fois supérieur en réduisant la surcharge d'accès au cache KV par rapport aux ordonnanceurs de l'état de l'art existants.

Auteurs originaux : Saksham Rathi, Preeti, Mythili Vutukuru

Publié 2026-05-08

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Saksham Rathi, Preeti, Mythili Vutukuru

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 une bibliothèque très animée et ultra-rapide où un seul bibliothécaire (le GPU) tente de répondre à des milliers de questions de différentes personnes (requêtes) en même temps.

Dans le monde des modèles de langage de grande taille (LLM), le bibliothécaire doit lire un livre massif de « contexte » (le cache clé-valeur) pour chaque mot qu'il génère. L'article soutient que la manière actuelle d'organiser ces questions est inefficace car elle se concentre trop sur combien de questions le bibliothécaire répond en même temps, plutôt que sur à quel point ces questions sont similaires.

Voici l'histoire de leur solution, Feather, décomposée en concepts simples :

1. Le Problème : Le « Bus Bondé » contre le « Groupe Familial »

Actuellement, la plupart des systèmes tentent de faire monter le plus de personnes possible dans un bus (un « lot ») pour rendre le trajet efficace. Ils utilisent une règle du « Premier arrivé, premier servi ».

Le Problème : Si vous mettez 500 étrangers dans un bus, ils veulent tous aller à 500 endroits différents. Le conducteur doit s'arrêter à 500 arrêts différents, changeant constamment de direction. C'est chaotique et lent.
La Découverte : Les auteurs ont constaté que si vous prenez un plus petit groupe de 100 personnes qui habitent toutes dans la même rue (partageant un « préfixe »), le conducteur peut rouler tout droit dans cette rue sans s'arrêter. Même si le bus n'est pas plein, le trajet est beaucoup plus rapide car le conducteur n'a pas à continuer de tourner le volant.

L'Idée Maîtresse : Il vaut mieux avoir un plus petit groupe de personnes allant au même endroit qu'un groupe énorme de personnes allant à des endroits différents. C'est ce qu'on appelle l'Homogénéité des Préfixes.

2. L'Ancienne Méthode : L'« Escalade d'Arbre »

Les systèmes existants (comme SGLang) tentent de trouver ces groupes en examinant un arbre familial géant et complexe (un arbre radix) pour voir qui partage les mêmes ancêtres.

Le Problème : Grimper cet arbre pour trouver des correspondances prend beaucoup de temps et d'énergie au « cerveau » de l'ordinateur (le CPU). En fait, le temps passé à grimper l'arbre était parfois presque aussi long que le temps que le bibliothécaire passait à répondre réellement aux questions ! C'était comme passer 10 minutes à organiser les passagers juste pour conduire pendant 10 minutes.

3. La Solution : « Feather »

Les auteurs ont construit un nouveau planificateur appelé Feather qui résout les deux problèmes.

Partie A : L'« Arbre de Hachage Découpé » (CHT) – La Liste de Contrôle Intelligente

Au lieu de grimper l'arbre familial géant, Feather utilise un raccourci astucieux.

L'Analogie : Imaginez que, au lieu de vérifier chaque lettre du nom d'une personne, vous vérifiez simplement les premiers « blocs » de son adresse.
Fonctionnement : Feather divise le long texte en petits blocs (chunks) et donne à chaque bloc une « empreinte » unique (un hachage). Il maintient une liste simple des empreintes actuellement utilisées.
L'Avantage : Il peut instantanément voir : « Oh, cette nouvelle requête a les mêmes empreintes que le groupe déjà dans le bus ». Il le fait si vite que le « cerveau CPU » peine à peine à transpirer. C'est comme utiliser un scanner de code-barres plutôt que de lire un livre entier pour vérifier un billet.

Partie B : L'« Apprentissage par Renforcement » (RL) – Le Dispatcheur Intelligent

Feather ne se contente pas de trouver des groupes similaires ; il apprend quand arrêter d'ajouter des personnes au bus.

Le Dilemme : Si vous continuez d'ajouter des personnes au bus, vous finirez peut-être par devoir ajouter quelqu'un qui habite dans une rue différente. Si vous les ajoutez, tout le groupe devient désordonné et la vitesse chute.
L'Apprentissage : Feather agit comme un dispatcheur intelligent qui a appris par essais et erreurs : « Si j'ajoute une personne de plus, nous risquons de perdre notre vitesse. Envoyons ce bus maintenant tant qu'il est rapide, et attendons le prochain groupe. »
Le Résultat : Il décide dynamiquement du moment parfait pour lancer le lot, en équilibrant entre avoir un bus plein et garder tout le monde dans la même rue.

4. Les Résultats : Accélérer la Bibliothèque

Lorsque les auteurs ont testé Feather :

Vitesse : Il a rendu le système 2 à 10 fois plus rapide que les meilleures méthodes actuelles lorsque les gens posaient des questions similaires.
Sécurité : Si les questions étaient toutes totalement différentes (pas de rues partagées), Feather ne s'est pas confondu ; il a simplement performé aussi bien que les anciennes méthodes.
Efficacité : Il a réduit les « embouteillages » dans la mémoire de l'ordinateur, ce qui signifie que le bibliothécaire n'avait pas à courir d'avant en arrière autant pour récupérer les pages du livre.

Résumé

Feather est une nouvelle façon d'organiser les requêtes d'IA. Au lieu d'empiler autant de requêtes que possible dans un seul lot, il regroupe les requêtes similaires (comme une famille allant à la même destination) et utilise une méthode ultra-rapide et peu énergivore pour trouver ces groupes. Il apprend exactement quand arrêter d'ajouter des personnes au groupe pour garder le trajet fluide et rapide.

L'article affirme que cette approche accélère considérablement les temps de réponse de l'IA sans avoir besoin de nouveau matériel coûteux, simplement en organisant le « trafic » de manière plus intelligente.

Résumé technique : Les requêtes d'une plume doivent se regrouper

Énoncé du problème

L'inférence des grands modèles de langage (LLM) est fondamentalement limitée par la mémoire lors de la phase de décodage auto-régressif. Chaque token généré nécessite de porter une attention sur le cache Key-Value (KV) de tous les tokens précédents, ce qui impose un balayage complet du cache KV en mémoire GPU à chaque étape. Alors que les travaux antérieurs se sont concentrés sur la maximisation de la taille des lots pour améliorer l'utilisation du GPU, cet article identifie un compromis critique, négligé : l'homogénéité des préfixes.

Dans les charges de travail réelles (par exemple, le few-shot prompting, les prompts système, RAG), les requêtes partagent souvent des préfixes significatifs. Les moteurs d'inférence existants (comme vLLM et SGLang) utilisent des arbres radicaux ou des structures de hachage pour détecter ces préfixes partagés et réutiliser les caches KV, principalement afin de réduire l'empreinte mémoire. Cependant, les planificateurs actuels privilégient la maximisation de la taille des lots ou la minimisation des évictions de mémoire sans tenir compte de l'impact de l'hétérogénéité des préfixes sur les modèles d'accès mémoire.

Les auteurs démontrent que les lots hétérogènes (contenant des requêtes avec des préfixes différents) perturbent la localité spatiale et temporelle dans les accès DRAM du GPU, entraînant une mauvaise utilisation de la bande passante et un débit réduit. À l'inverse, les lots homogènes en préfixes (où toutes les requêtes partagent un préfixe commun) permettent un préchargement matériel efficace et une réutilisation du cache. L'article soutient que les planificateurs existants ne reconnaissent pas qu'un lot homogène modérément petit peut surpasser un lot plus grand mais hétérogène. De plus, les mécanismes utilisés pour détecter le partage de préfixes (par exemple, les traversées d'arbres radicaux) entraînent une surcharge CPU prohibitive, souvent comparable ou supérieure au temps d'exécution du GPU.

Méthodologie

L'article présente Feather, un planificateur conscient des préfixes conçu pour optimiser le compromis entre la taille des lots et l'homogénéité des préfixes. Feather intègre deux composants principaux :

1. Arbre de hachage par blocs (CHT)

Pour remédier à la surcharge CPU élevée des traversées d'arbres radicaux traditionnels, Feather utilise une structure de données légère appelée Arbre de hachage par blocs (Chunked Hash Tree).

Mécanisme : Au lieu de comparaisons token par token, les requêtes sont représentées comme des vecteurs de hachages cumulatifs sur des blocs de tokens de taille fixe.
Efficacité : Le CHT maintient un "ensemble de travail" de hachages pour le lot actif et un tas min (min-heap) des requêtes en attente, ordonné par leur "compteur manquant" (le nombre de blocs encore non couverts par le lot actif).
Complexité : Cela permet au planificateur d'identifier la meilleure requête candidate à ajouter à un lot en temps $O(\log W)$ (où $W$ est le nombre de requêtes en attente), une amélioration significative par rapport à la complexité $O(W \times T)$ ou $O(E)$ des traversées d'arbres radicaux en profondeur.
Opérations : Le CHT prend en charge l'insertion efficace, la recherche de la meilleure requête, l'ajout d'une requête au lot actif et la suppression des requêtes terminées, en utilisant des mises à jour paresseuses du tas et une maintenance incrémentale des extrémités pour minimiser la surcharge.

2. Politique de regroupement par apprentissage par renforcement (RL)

Feather utilise une politique basée sur l'apprentissage par renforcement pour déterminer le point d'arrêt optimal pour la formation des lots.

Le compromis : Ajouter plus de requêtes augmente l'utilisation du GPU (taille de lot plus grande) mais peut diluer l'homogénéité des préfixes (réduisant la localité mémoire).
État et Action : Le planificateur observe la taille actuelle du lot, la perte de profondeur de préfixe partagé ( $\Delta$ ) et le nombre de requêtes en attente partageant la nouvelle profondeur de préfixe ( $w$ ). Il décide d'Ajouter une autre requête ou de S'arrêter et d'expédier le lot.
Politiques : Les auteurs évaluent trois politiques : une heuristique statique, un Bandit contextuel (UCB) et l'apprentissage Q. L'objectif est de maximiser la récompense, définie comme le débit de décodage.
Adaptabilité : La politique RL apprend à former des lots "juste ce qu'il faut" : assez grands pour utiliser le GPU, mais assez homogènes pour maximiser la localité mémoire. Elle s'adapte dynamiquement à l'intensité de la charge de travail et aux modèles de partage de préfixes.

Contributions clés

Identification d'un compromis critique : L'article établit que l'homogénéité des préfixes est un déterminant plus fort du débit de décodage que la taille des lots seule. Il démontre qu'une seule requête divergente dans un lot peut perturber la localité et réduire le débit de près de 2 fois.
Quantification de la surcharge CPU : Les auteurs révèlent que les mécanismes de détection de préfixes les plus avancés (comme les traversées d'arbres radicaux dans SGLang) entraînent des surcharges CPU pouvant atteindre 50 à 90 % de la latence totale, annulant effectivement les bénéfices de la réutilisation des préfixes.
Planificateur Feather : La conception et la mise en œuvre de Feather, qui intègre la structure de données CHT avec une politique de regroupement basée sur l'apprentissage par renforcement. Feather est intégré à la fois dans vLLM et SGLang.
Indépendance matérielle : Contrairement aux noyaux d'attention conscients des préfixes qui nécessitent un réglage matériel spécifique, Feather opère au niveau de la couche de planification, ce qui le rend compatible avec les noyaux d'attention et les configurations matérielles existants.

Résultats

L'évaluation a été menée sur des GPU NVIDIA RTX 6000 Ada et A100 en utilisant des modèles tels que Llama 3 8B, Qwen et LongChat 13B sur diverses charges de travail (L-Eval, LongBench).

Gains de débit : Feather atteint un débit de bout en bout 2 à 10 fois supérieur par rapport aux planificateurs existants (FCFS de vLLM, LPM/DFS-W de SGLang) dans des charges de travail avec des préfixes partagés allant de 1K à 10K tokens.
Sensibilité aux préfixes : Dans des expériences avec 800 requêtes réparties en 8 groupes de préfixes, leur traitement en 8 lots homogènes de 100 requêtes a produit un débit presque 2 fois supérieur à leur traitement dans des lots plus grands et hétérogènes.
Réduction de la surcharge : Le CHT de Feather réduit la surcharge de détection des préfixes jusqu'à 1000 fois par rapport aux approches basées sur DFS pour les séquences longues. La surcharge de planification reste inférieure à 1 % du temps d'exécution du GPU, alors que les approches de base peuvent dépasser le temps d'exécution du GPU.
Robustesse : Feather performe au même niveau que le statu quo (FCFS) lorsque les charges de travail ne comportent pas de partage de préfixes, garantissant aucune dégradation des performances dans les scénarios non partagés.
Comparaison avec les noyaux : Feather surpasse ou égale les noyaux d'attention spécialisés conscients des préfixes (comme PAT) sans modifier le noyau lui-même, prouvant que les optimisations au niveau de la planification peuvent être aussi efficaces que celles au niveau du noyau.

Importance

L'article affirme que la maximisation de la taille des lots ne suffit plus pour un service efficace des LLM. Le goulot d'étranglement principal dans les phases de décodage modernes est la bande passante mémoire, qui est fortement influencée par la localité d'accès. En déplaçant l'accent de la "maximisation de la taille des lots" vers "l'optimisation de l'homogénéité des préfixes", Feather débloque des gains de performance significatifs sans nécessiter de modifications de noyaux spécifiques au matériel.

Ce travail met en évidence que le coût de la recherche de préfixes partagés (surcharge CPU) a été un goulot d'étranglement caché dans les systèmes actuels. Le CHT léger de Feather et sa politique RL adaptative démontrent qu'il est possible d'équilibrer dynamiquement l'utilisation du calcul et la localité mémoire, conduisant à des améliorations substantielles à la fois du débit et de la latence pour les charges de travail d'inférence LLM réelles. Les auteurs prévoient de rendre Feather open source en le contribuant aux dépôts vLLM et SGLang.