Cet article étudie le problème du traitement des requêtes LLM avec des longueurs de pré-remplissage et de décodage hétérogènes. Dans le traitement LLM, la longueur de pré-remplissage correspond à la longueur de l'invite d'entrée et détermine l'utilisation initiale de la mémoire du cache KV. La longueur de décodage représente le nombre de jetons de sortie générés séquentiellement, et chaque jeton supplémentaire augmente l'utilisation de la mémoire du cache KV d'une unité. Étant donné un ensemble de n requêtes, notre objectif est de les planifier et de les traiter afin de minimiser le temps d'exécution total. Cet article montre que ce problème est NP-difficile en raison de l'interaction entre le placement, les contraintes de placement, les relations de précédence et l'augmentation linéaire de l'utilisation de la mémoire. Nous analysons les stratégies d'ordonnancement FCFS et SF couramment utilisées et démontrons que leurs taux de contention augmentent de manière sous-linéaire avec les contraintes de mémoire (un inconvénient majeur dans les environnements réels à forte demande mémoire). Pour résoudre ce problème, nous proposons un nouvel algorithme basé sur une nouvelle métrique de sélection qui forme efficacement des lots au fil du temps, et nous démontrons que cet algorithme atteint un taux de contention constant. Enfin, nous développons et évaluons plusieurs variantes algorithmiques inspirées de cette approche, notamment des variantes de programmation dynamique, des méthodes de recherche locale et des planificateurs basés sur LP, et montrons par des simulations complètes qu'elles surpassent la ligne de base standard tout en maintenant l'efficacité de calcul.
