Este artículo estudia el problema del procesamiento de solicitudes LLM con longitudes de prerrelleno y decodificación heterogéneas. En el servicio LLM, la longitud de prerrelleno corresponde a la longitud del mensaje de entrada y determina el uso inicial de memoria de la caché KV. La longitud de decodificación representa el número de tokens de salida generados secuencialmente, y cada token adicional incrementa el uso de memoria de la caché KV en una unidad. Dado un conjunto de n solicitudes, nuestro objetivo es programarlas y procesarlas para minimizar el tiempo total de finalización. Este artículo demuestra que este problema es NP-hard debido a la interacción entre la ubicación, las restricciones de ubicación, las relaciones de precedencia y el aumento lineal del uso de memoria. Analizamos las estrategias de programación FCFS y SF comúnmente utilizadas y demostramos que sus tasas de contención aumentan sublinealmente con las restricciones de memoria (una desventaja significativa en entornos reales con altas demandas de memoria). Para abordar este problema, proponemos un nuevo algoritmo basado en una nueva métrica de selección que forma lotes eficientemente a lo largo del tiempo y demostramos que este algoritmo logra una tasa de contención constante. Por último, desarrollamos y evaluamos varias variantes algorítmicas inspiradas en este enfoque, incluidas variantes de programación dinámica, métodos de búsqueda local y programadores basados en LP, y demostramos a través de simulaciones exhaustivas que superan la línea base estándar manteniendo la eficiencia computacional.
