Resumo Técnico: Programação Linear Online para Roteamento Multi-Objetivo em Servimento de LLM

1. Definição do Problema

O artigo aborda o desafio do roteamento de requisições online em sistemas de servimento de Large Language Models (LLM). Nesses sistemas, as requisições recebidas devem ser despachadas para workers de decodificação paralela sob restrições rigorosas:

• Restrições Acopladas no Tempo: As requisições consomem recursos (slots de batch e memória KV-cache) continuamente durante toda a sua duração de decodificação. Uma requisição admitida no tempo $t$ ocupa capacidade até que seja concluída, criando um problema de alocação de recursos complexo e dependente do tempo.
• Compensações Multi-Objetivo (Trade-offs): Os sistemas devem equilibrar Objetivos de Nível de Serviço (SLOs) conflitantes, incluindo throughput, latência de ponta a ponta (EEL), tempo para o primeiro token (TTFT) e latência de cauda (ex: percentil 99). Esses objetivos são frequentemente antagônicos; por exemplo, maximizar o throughput via batching agressivo frequentemente degrada a latência.
• Limitações das Heurísticas Atuais: Sistemas de produção existentes (ex: vLLM) e simuladores (ex: Vidur) dependem de heurísticas como Round-Robin, Join-Shortest-Queue (LOR) ou escolhas Power-of-$d$. Esses métodos carecem de objetivos de otimização explícitos, oferecem controle limitado sobre compensações de SLO e não consideram a natureza heterogênea e incerta dos comprimentos de decodificação de LLMs.

2. Metodologia

Os autores propõem um framework que formula o roteamento de LLM como um problema de Programação Linear Online (OLP), utilizando técnicas de pesquisa operacional para derivar uma política de controle computacionalmente eficiente.

A. Formulação Matemática

• Modelo: O sistema é modelado sobre um horizonte de tempo discreto com dispositivos de decodificação paralelos. As requisições chegam sequencialmente com pegadas de prefill conhecidas e comprimentos de decodificação previstos (mas potencialmente imprecisos).
• Restrições: A formulação impõe duas restrições críticas por dispositivo por passo de tempo:
  1. Tamanho do Batch: Um número máximo de requisições ativas ($B$).
  2. Capacidade de KV-Cache: Um orçamento máximo de memória ($M$) para requisições ativas.
• Função Objetivo: Os autores definem uma função de recompensa linear para cada decisão de roteamento $(j, g, k)$ (atribuindo a requisição $j$ ao dispositivo $g$ no tempo $k$). Esta recompensa é uma soma ponderada de:
  • Throughput (tokens processados).
  • Latência negativa (minimização de EEL e TTFT).
  • Queries Per Second (QPS).
  • Métricas de cauda (modeladas via recompensas de indicador para requisições que atendem a limites específicos de latência).
  • Insight Chave: Métricas agregadas como latência de cauda são decompostas em incentivos por requisição usando funções indicadoras, permitindo que sejam otimizadas dentro de um framework linear.

B. Design do Algoritmo: Controle de Preço de Lance (Bid-Price Control)

Resolver o OLP completo a cada milissegundo é computacionalmente inviável. Em vez disso, os autores derivam uma política de Controle de Preço de Lance baseada na dualidade de LP:

1. Variáveis Duais (Preços de Sombra): As variáveis duais $p_i$ representam o "preço de sombra" ou custo de oportunidade dos recursos (slots de batch e KV-cache) em tempos e dispositivos específicos. Preços de sombra altos indicam congestionamento antecipado.
2. Regra de Decisão: Uma requisição é admitida se seu benefício ponderado pelo SLO exceder seu custo de recurso imputado (calculado como o produto escalar do vetor de uso de recurso e os preços de sombra atuais).
3. Aprendizado Online (SAA): Para lidar com a natureza estocástica de chegadas e previsões, os preços de sombra são aprendidos online usando uma abordagem de Aproximação de Média de Amostra (SAA). O objetivo dual é minimizado sobre um histórico de ações observadas.
4. Atualizações Eficientes: Para atender às latências de decisão de milissegundos, os autores empregam gradiente descendente de mini-lote projetado com warm-start. Em vez de resolver o problema dual do zero, o algoritmo atualiza o vetor de preços incrementalmente com base em um pequeno lote de dados históricos. Isso garante um tempo de execução previsível (1–2ms por período em uma CPU).

3. Principais Contribuições

1. Framework de Otimização Multi-Objetivo: O primeiro framework que formula o roteamento de LLM como um OLP com restrições de batch e KV-cache acopladas no tempo. Ele decompõe SLOs agregados (incluindo latência de cauda) em recompensas por requisição adequadas para otimização online.
2. Algoritmo de Preço de Lance Eficiente: Uma política computacionalmente tratável que rastreia a evolução dos preços de sombra duais online sem resolver um LP completo em cada etapa, atendendo aos rigorosos requisitos de latência do servimento de LLM.
3. Controle de Compensação Interpretável: O framework fornece aos operadores "botões" (pesos de objetivo) transparentes para deslocar sistematicamente o desempenho ao longo da fronteira de Pareto. Os preços de sombra também servem como ferramentas de diagnóstico para identificar se o gargalo atual é o slot de batch ou o KV-cache.

4. Resultados Experimentais

Os autores integraram seu roteador no simulador Vidur e o avaliaram contra baselines padrão (Round-Robin, LOR, Random, Power-of-2) sob várias cargas de trabalho (dados reais LMSYS-Chat-1M e razões P/D sintéticas).

• Ganhos de Desempenho: O método proposto demonstrou melhorias substanciais sobre os baselines em múltiplos regimes de SLO.
  • Em cenários de previsão ruidosa (erro de 20%), o algoritmo alcançou uma redução de 45,75% na EEL média e uma redução de 42,49% na P95 EEL em comparação ao Round-Robin.
  • Superou significativamente as heurísticas em métricas de latência de cauda (P99 EEL e TTFT).
• Robustez: A política permaneceu eficaz mesmo com previsões de comprimento de decodificação imperfeitas, pois as atualizações de preço online se adaptam aos erros de estimativa.
• Adaptabilidade: Em cargas de trabalho não estacionárias (picos súbitos de carga), o roteador se adaptou rapidamente usando um mecanismo de janela deslizante para atualizações de histórico, mantendo o desempenho superior.
• Ajuste de Pesos: Experimentos confirmaram que o ajuste dos pesos de objetivo permite que os operadores priorizem métricas específicas (ex: minimizar a latência média vs. controlar estritamente a latência de cauda) com resultados previsíveis.

5. Significância e Alegações

O artigo alega que uma abordagem de otimização baseada em ciência supera o roteamento baseado em heurísticas no servimento de LLM.

• Unindo Comunidades: Estabelece uma ponte principista entre a comunidade de pesquisa operacional (alocação de recursos online, controle de preço de lance) e a comunidade de sistemas de LLM.
• Insights de Design de Sistema: O framework revela insights estruturais, como o uso de preços de sombra para diagnosticar gargalos de recursos (batch vs. memória) e permitir o controle de admissão consciente de SLO durante sobrecargas.
• Aplicabilidade Prática: Embora a integração total em produção seja notada como trabalho futuro, os resultados demonstram que o roteamento baseado em otimização é viável em escalas de milissegundos e fornece uma base para o design sistemático de políticas em vez de ajustes ad-hoc.

Os autores permanecem modestos quanto à implementação imediata em produção, reconhecendo desafios como a integração com motores de servimento (ex: vLLM), tratamento de preempção e coordenação em ambientes distribuídos. No entanto, eles afirmam que o framework fornece uma base necessária para pesquisas futuras na interseção entre pesquisa operacional e sistemas de aprendizado de máquina.