Resumen Técnico: Programación Lineal en Línea para el Enrutamiento Multiobjetivo en el Servicio de LLM

1. Planteamiento del Problema

El artículo aborda el desafío del enrutamiento de solicitudes en línea en sistemas de servicio de Modelos de Lenguaje Extensos (LLM). En estos sistemas, las solicitudes entrantes deben ser despachadas a trabajadores de decodificación paralela bajo restricciones estrictas:

• Restricciones Acopladas en el Tiempo: Las solicitudes consumen recursos (ranuras de lote y memoria KV-cache) de forma continua durante toda su duración de decodificación. Una solicitud admitida en el tiempo $t$ ocupa capacidad hasta que finaliza, lo que crea un problema de asignación de recursos complejo y dependiente del tiempo.
• Compromisos Multiobjetivo: Los sistemas deben equilibrar SLOs (Objetivos de Nivel de Servicio) contrapuestos, incluyendo el rendimiento (throughput), la latencia de extremo a extremo (EEL), la latencia del primer token (TTFT) y la latencia de cola (por ejemplo, el percentil 96). Estos objetivos suelen estar en tensión; por ejemplo, maximizar el rendimiento mediante un agrupamiento (batching) agresivo suele degradar la latencia.
• Limitaciones de las Heurísticas Actuales: Los sistemas de producción existentes (por ejemplo, vLLM) y los simuladores (por ejemplo, Vidur) dependen de heurísticas como Round-Robin, Join-Shortest-Queue (LOR) o elecciones de Power-of-$d$. Estos métodos carecen de objetivos de optimización explícitos, ofrecen un control limitado sobre los compromisos de los SLO y no tienen en cuenta la naturaleza heterogénea e incierta de las longitudes de decodificación de los LLM.

2. Metodología

Los autores proponen un marco que formula el enrutamiento de LLM como un problema de Programación Lineal en Línea (OLP), aprovechando técnicas de investigación de operaciones para derivar una política de control computacionalmente eficiente.

A. Formulación Matemática

• Modelo: El sistema se modela sobre un horizonte de tiempo discreto con dispositivos de decodificación paralelos. Las solicitudes llegan secuencialmente con huellas de prefill conocidas y longitudes de decodificación predichas (pero potencialmente inexactas).
• Restricciones: La formulación impone dos restricciones críticas por dispositivo por cada paso de tiempo:
  1. Tamaño de Lote (Batch Size): Un número máximo de solicitudes activas ($B$).
  2. Capacidad de KV-Cache: Un presupuesto máximo de memoria ($M$) para las solicitudes activas.
• Función Objetivo: Los autores definen una función de recompensa lineal para cada decisión de enrutamiento $(j, g, k)$ (asignar la solicitud $j$ al dispositivo $g$ en el tiempo $k$). Esta recompensa es una suma ponderada de:
  • Rendimiento (tokens procesados).
  • Latencia negativa (minimizando EEL y TTFT).
  • Consultas Por Segundo (QPS).
  • Métricas de cola (modeladas mediante recompensas indicadoras para solicitudes que cumplen con límites de latencia específicos).
  • Idea Clave: Las métricas agregadas como la latencia de cola se descomponen en incentivos por solicitud utilizando funciones indicadoras, lo que permite optimizarlas dentro de un marco lineal.

B. Diseño del Algoritmo: Control de Precio de Puja (Bid-Price Control)

Resolver el OLP completo en cada milisegundo es computacionalmente inviable. En su lugar, los autores derivan una política de Control de Precio de Puja basada en la dualidad de la programación lineal (LP):

1. Variables Duales (Precios Sombra): Las variables duales $p_i$ representan el "precio sombra" o el costo de oportunidad de los recursos (ranuras de lote y KV-cache) en momentos y dispositivos específicos. Un precio sombra alto indica una congestión anticipada.
2. Regla de Decisión: Una solicitud se admite si su beneficio ponderado por SLO supera su costo de recurso imputado (calculado como el producto punto del vector de uso de recursos y los precios sombra actuales).
3. Aprendizaje en Línea (SAA): Para manejar la naturaleza estocástica de las llegadas y las predicciones, los precios sombra se aprenden en línea utilizando un enfoque de Aproximación de Promedio de Muestra (SAA). El objetivo dual se minimiza sobre un historial de acciones observadas.
4. Actualizaciones Eficientes: Para cumplir con las latencias de decisión de milisegundos, los autores emplean descenso de gradiente de mini-lotes proyectado y con reinicio caliente (warm-started). En lugar de resolver el problema dual desde cero, el algoritmo actualiza el vector de precios incrementalmente basándose en un pequeño lote de datos históricos. Esto asegura un tiempo de ejecución predecible (1–2 ms por periodo en una CPU).

3. Contribuciones Clave

1. Marco de Optimización Multiobjetivo: El primer marco que formula el enrutamiento de LLM como un OLP con restricciones de lote y KV-cache acopladas en el tiempo. Descompone los SLOs agregados (incluyendo la latencia de cola) en recompensas por solicitud adecuadas para la optimización en línea.
2. Algoritmo de Precio de Puja Eficiente: Una política computacionalmente tratable que rastrea la evolución de los precios sombra duales en línea sin resolver un LP completo en cada paso, cumpliendo con los estrictos requisitos de latencia del servicio de LLM.
3. Control de Compromiso Interpretable: El marco proporciona a los operadores "perillas" (pesos de objetivo) transparentes para desplazar sistemáticamente el rendimiento a lo largo de la frontera de Pareto. Los precios sombra también sirven como herramientas de diagnóstico para identificar si las ranuras de lote o el KV-cache son el cuello de botella actual.

4. Resultados Experimentales

Los autores integraron su enrutador en el simulador Vidur y lo evaluaron contra líneas base estándar (Round-Robin, LOR, Random, Power-of-2) bajo diversas cargas de trabajo (datos reales de LMSYS-Chat-1M y relaciones sintéticas P/D).

• Ganancias de Rendimiento: El método propuesto demostró mejoras sustanciales sobre las líneas base en múltiples regímenes de SLO.
  • En escenarios de predicción ruidosa (error del 20%), el algoritmo logró una reducción del 45.75% en la EEL promedio y una reducción del 42.49% en la P95 EEL en comparación con Round-Robin.
  • Superó significativamente a las heurísticas en métricas de latencia de cola (P99 EEL y TTFT).
• Robustez: La política se mantuvo efectiva incluso con predicciones de longitud de decodificación imperfectas, ya que las actualizaciones de precios en línea se adaptan a los errores de estimación.
• Adaptabilidad: En cargas de trabajo no estacionarias (picos repentinos de carga), el enrutador se adaptó rápidamente utilizando un mecanismo de ventana rodante para las actualizaciones del historial, manteniendo un rendimiento superior.
• Ajuste de Pesos: Los experimentos confirmaron que ajustar los pesos de los objetivos permite a los operadores priorizar métricas específicas (por ejemplo, minimizar la latencia promedio frente a controlar estrictamente la latencia de cola) con resultados predecibles.

5. Significancia y Reclamaciones

El artículo afirma que un enfoque de optimización basado en la ciencia supera al enrutamiento basado en heurísticas en el servicio de LLM.

• Puente entre Comunidades: Establece un puente fundamental entre la comunidad de investigación de operaciones (asignación de recursos en línea, control de precio de puja) y la comunidad de sistemas de LLM.
• Perspectivas de Diseño de Sistemas: El marco revela conocimientos estructurales, como el uso de precios sombra para diagnosticar cuellos de botella de recursos (lote vs. memoria) y permitir el control de admisión sensible a los SLO durante la sobrecarga.
• Aplicabilidad Práctica: Aunque se señala la integración completa en producción como un trabajo futuro, los resultados demuestran que el enrutamiento basado en optimización es factible a escalas de milisegundos y proporciona una base para el diseño sistemático de políticas en lugar de ajustes ad-hoc.

Los autores mantienen la modestia respecto a la implementación inmediata en producción, reconociendo desafíos como la integración con motores de servicio (por ejemplo, vLLM), el manejo de la preempción y la coordinación en entornos distribuidos. Sin embargo, afirman que el marco proporciona una base necesaria para la investigación futura en la intersección de la investigación de operaciones y los sistemas de aprendizaje automático.