LLM Serving Optimization with Variable Prefill and Decode Lengths

Resumen Técnico: Optimización del Servicio de LLM con Longitudes de Prefill y Decode Variables

Formulación del Problema
Este artículo aborda el problema de programación offline para la inferencia de Modelos de Lenguaje de Gran Tamaño (LLM) en un único trabajador computacional con un presupuesto fijo de memoria para el caché de Clave-Valor (KV). El sistema gestiona una acumulación de $n$ solicitudes que llegan simultáneamente en $t=0$. Cada solicitud $i$ se caracteriza por una longitud de prompt heterogénea (tamaño de prefill, $s_i$) y una longitud de respuesta (tamaño de decode, $o_i$).

El desafío central surge de la naturaleza dinámica del consumo de memoria durante el decodificado autorregresivo. Mientras que la fase de prefill consume memoria proporcional a $s_i$, la fase de decode consume memoria que crece linealmente con cada token generado ($s_i + j$ para el $j$-ésimo token). En consecuencia, el número de solicitudes concurrentes que un trabajador puede manejar fluctúa dinámicamente según el progreso de generación de las solicitudes activas. El objetivo es minimizar la Latencia Total de Extremo a Extremo (TEL, por sus siglas en inglés), definida como la suma de los tiempos de finalización de todas las solicitudes, sujeto a la restricción de que el uso agregado de memoria de cualquier lote en cualquier paso de tiempo no exceda la capacidad $M$.

Los autores relajan la suposición de tamaños de entrada uniformes de trabajos previos (Jaillet et al., 2025), considerando un escenario realista donde las cargas de trabajo mezclan prompts de conversación cortos con tareas de resumen de documentos largos.

Hallazgos Teóricos y Desafíos
El artículo establece que relajar la suposición de tamaño de entrada uniforme altera fundamentalmente la complejidad del problema de programación:

1. NP-Hardness (Complejidad NP-dura): Se demuestra que el problema de programación generalizado con $s_i$ y $o_i$ heterogéneos es NP-duro mediante una reducción del problema 3-Partición restringido.
2. Fracaso de las Heurísticas Estándar: Se demuestra que las políticas estándar, incluyendo First-Come-First-Served (FCFS), Shortest-Output-First (MC-SF) y la priorización basada en el tamaño total, tienen ratios de aproximación no acotados en este entorno heterogéneo. Específicamente, una solicitud con un input grande pero un output pequeño puede consumir mucha memoria brevemente, mientras que una solicitud con un input pequeño pero un output largo puede ocupar memoria durante un periodo prolongado, creando compensaciones que las heurísticas simples no pueden resolver.

Metodología: El Algoritmo Sorted-F
Para abordar estos desafíos, los autores proponen Sorted-F, un algoritmo de programación diseñado para lograr una garantía de aproximación de factor constante. El algoritmo opera en dos fases:

1. Construcción de Lotes (Fase 1): El algoritmo selecciona iterativamente lotes factibles de solicitudes para formar una lista ordenada. La selección se guía por una novedosa métrica de calidad, $F(X)$, definida para un conjunto de solicitudes $X$ como:
   $$F(X) = \frac{\sum_{r_i \in X} o_i}{|X|^2}$$
   Esta métrica equilibra el tamaño del lote ($|X|$) contra el costo agregado de decodificación descendente ($\sum o_i$). Minimizar $F(X)$ es equivalente a maximizar la "densidad de throughput" (solicitudes completadas por unidad de tiempo de decode promedio). Dentro de cada lote seleccionado, las solicitudes se ordenan por longitud de salida no decreciente.
2. Ejecución (Fase 2): El sistema ejecuta la programación sobre pasos de tiempo discretos, admitiendo solicitudes de la lista ordenada en el lote actual siempre que se satisfagan las restricciones de factibilidad de memoria, utilizando batching continuo y mezcla de prefill/decode.

Garantía de Aproximación
Los autores demuestran que Sorted-F logra un ratio de aproximación constante de máximo 48 respecto al esquema offline óptimo. La prueba involucra una serie de transformaciones estructurales (separación, agrupación y alineación) que convierten el esquema de Sorted-F y el esquema óptimo en formas comparables, demostando que el incremento de latencia en cada paso está acotado por un factor constante.

Implementaciones Prácticas
Reconociendo que la optimización combinatoria requerida en la Fase 1 es computacionalmente costosa para $n$ grandes, el artículo propone tres solvers prácticos:

• Programación Dinámica Exacta: Proporciona una solución exacta para instancias pequeñas ($n \le 100$) con complejidad $O(n^2 M)$.
• Búsqueda de Intercambio Local (Local Swap Search): Una heurística para escalas moderadas ($n \le 500$) que mejora iterativamente una solución greedy inicial mediante intercambios por pares ($O(n^2)$).
• Selección Greedy por Cuantiles: Una heurística de tiempo lineal ($O(n)$) para sistemas de gran escala ($n \ge 1000$) que utiliza muestreo estadístico para filtrar valores atípicos y llena la capacidad de forma codiciosa.

Adicionalmente, el artículo introduce Sorted-LP, una heurística que aprovecha la solución de una relajación de Programación Lineal (LP) del problema para ordenar las solicitudes, y Sorted-F+Amin, una variante adaptativa que maneja la incertidumbre de la predicción de las longitudes de salida refinando dinámicamente las estimaciones durante la inferencia.

Resultados Experimentales
Experimentos numéricos en cargas de trabajo mixtas (combinando el dataset LMSYS-Chat y resúmenes de documentos largos de Arxiv) demuestran:

• Reducción de Latencia: Sorted-F (usando Local Swap Search) supera consistentemente a FCFS, MC-SF y las líneas base guiadas por LP. En una mezcla 80/20 de corto/largo con 2000 solicitudes, Sorted-F redujo la latencia promedio en 4.87$\times$ comparado con FCFS y en 2.09$\times$ comparado con MC-SF.
• Brecha de Optimalidad: En instancias tratables, la brecha empírica entre Sorted-F y el límite inferior de la relajación LP es pequeña (aproximadamente 1.03–1.09), lo que sugiere que el algoritmo actúa casi de forma óptima en la práctica a pesar del límite teórico laxo.
• Sensibilidad de la Carga de Trabajo: Los beneficios de Sorted-F son más pronunciados en regímenes heterogéneos y sobrecargados donde la memoria es una restricción vinculante. En regímenes homogéneos o de baja carga, la ventaja disminuye.
• Desempeño Online: Una variante de horizonte de retroceso (Sorted-F-Online) probada bajo llegadas de Poisson muestra mejoras significativas sobre MC-SF y FCFS en regímenes online sobrecargados, aunque ofrece menos beneficio en regímenes estables de baja latencia.

Significancia y Reivindicaciones
El artículo afirma que las longitudes de prefill variables no son un detalle menor de modelado, sino un factor fundamental que vuelve ineficaces las heurísticas de programación estándar y hace que el problema sea NP-duro. La contribución principal es el algoritmo Sorted-F, que proporciona la primera garantía de aproximación de factor constante para la programación de LLM bajo restricciones heterogéneas de input/output. El trabajo cierra la brecha entre los límites teóricos de programación y el servicio práctico de LLM, ofreciendo un marco escalable y consciente de la memoria que reduce significativamente la latencia en escenarios de cargas de trabajo mixtas sin requerir una predicción perfecta de las longitudes de salida. Los autores enfatizan que, si bien el límite teórico es 48, los resultados empíricos sugieren que el algoritmo está mucho más cerca de la solución óptima en configuraciones realistas.