Resumo Técnico: Algoritmos de Agendamento Otimizados para Vazão em Inferência de LLM e Agentes de IA

Declaração do Problema

À medida que a demanda por Modelos de Linguagem de Grande Escala (LLMs) e agentes de IA cresce, a otimização dos sistemas de inferência para eficiência torna-se crítica. Embora esforços significativos de engenharia tenham se concentrado em melhorias no nível do sistema, falta um modelo matemático coeso e um quadro teórico de filas para avaliar algoritmos de agendamento. Especificamente, o artigo aborda a questão fundamental: Qual é a taxa máxima de vazão para um sistema de inferência de LLM e quais classes de algoritmos de agendamento podem atingir esse limite?

A inferência de LLM apresenta desafios únicos em comparação com sistemas de filas clássicos:

1. Processamento em Duas Fases: As solicitações passam por uma fase de preenchimento (prefill) limitada por computação (processamento de tokens de entrada para construir o cache KV) seguida por uma fase de decodificação (decode) limitada por E/S de memória (geração autoregressiva de tokens).
2. Restrições de Agrupamento (Batching): Para maximizar a utilização da GPU, as solicitações são agrupadas. No entanto, a mistura de tokens de preenchimento e decodificação cria interferência, e o hardware impõe um orçamento de tokens ($b_{max}$) e, frequentemente, uma restrição de tamanho do lote ($k_{max}$).
3. Cargas de Trabalho de Agentes de IA: Aplicações modernas envolvem redes de servidores LLM processando tarefas complexas de agentes, que podem seguir topologias de Grafos Acíclicos Direcionados (DAG), padrões fork-join ou conter roteamento cíclico.

Sistemas existentes empregam estratégias diversas (por exemplo, FasterTransformer, vLLM, Orca, Sarathi-Serve) com prioridades variadas (prioridade de preenchimento vs. prioridade de decodificação) e capacidades de agrupamento (misturado vs. separado). Os praticantes atualmente dependem de testes de referência (benchmarking) específicos de carga de trabalho e custosos para escolher sistemas, carecendo de uma garantia teórica de estabilidade ou otimalidade de vazão.

Metodologia

Os autores desenvolvem um quadro teórico de filas rigoroso para modelar sistemas de inferência de LLM.

1. Modelagem Estocástica

• Modelo Básico: O sistema é modelado como uma cadeia de Markov em tempo discreto (DTMC) representando uma fila de serviço em lote de duas classes.
  • Classes: As solicitações existem em uma fila de preenchimento ou em uma fila de decodificação.
  • Agrupamento: O servidor processa um lote de tokens de ambas as filas simultaneamente, sujeito a um orçamento de tokens $b_{max}$.
  • Assimetria: Tokens de preenchimento de uma única solicitação podem ser processados em massa, enquanto tokens de decodificação são estritamente sequenciais (um por solicitação por lote).
• Modelo de Tempo de Processamento: Aproveitando rastreamentos empíricos, o tempo de processamento do lote $t_b$ é aproximado por uma função constante por partes dependente da carga de tokens $b$:
  $$t_b = c + a \cdot \lceil b/b_0 \rceil$$
  onde $c$ é o custo base, $a$ é o custo marginal por bloco de $b_0$ tokens. Este modelo captura a dominância dos cálculos de camadas lineares na inferência de LLM.

2. Quadro Analítico

• Técnica de Limite Fluido: Os autores empregam o quadro de limite fluido (Dai 1995, Stolyar 1995) para analisar a estabilidade. Eles provam que, sob condições específicas, o processo estocástico escalonado converge para um modelo fluido determinístico.
• Definição de Estabilidade: Um sistema é estável (recorrente positivo) se o número total de tokens não processados não divergir à medida que o tempo tende ao infinito.
• Classe de Agendamento: A análise foca em algoritmos conservadores de trabalho (aqueles que preenchem o lote até a capacidade $b_{max}$ sempre que possível) e introduz a condição K-FCFS (Primeiro a Chegar, Primeiro a Ser Servido com ultrapassagem limitada) para lidar com as complexidades do agrupamento misto.

3. Extensões

O quadro é estendido para:

• Servidores Paralelos: Sistemas com balanceamento de carga (Aleatório ou Junte-se à Fila Mais Curta).
• Redes Multiclasse: Servidores únicos lidando com múltiplas classes de solicitações (por exemplo, etapas diferentes de agentes).
• Topologias de Rede: Redes de múltiplos servidores com roteamento DAG e sincronização fork-join.
• Roteamento Cíclico: Análise de redes com loops de feedback (tipo Rybko–Stolyar).
• Restrições de Tamanho do Lote: Análise de sistemas restritos tanto pelo orçamento de tokens ($b_{max}$) quanto pelo tamanho máximo do lote ($k_{max}$).

Principais Contribuições e Resultados

1. Otimalidade de Vazão de Agendamento Conservador de Trabalho

O artigo estabelece um princípio fundamental de design: Algoritmos de agendamento conservadores de trabalho atingem a vazão máxima para inferência de LLM em servidor único e redes com topologias DAG ou fork-join.

• Teorema 2: Para um servidor único, se a carga de chegada $\lambda(m_p + m_d)$ for menor que a taxa máxima de processamento $b_{max}/t_{b_{max}}$, qualquer algoritmo K-FCFS conservador de trabalho estabiliza o sistema. Por outro lado, se a carga exceder esse limiar, o sistema é instável sob qualquer algoritmo.
• Implicação: Isso fornece um limite superior teórico ($b_{max}/t_{b_{max}}$) e valida a mudança na indústria em direção a agendadores conservadores de trabalho.

2. Avaliação de Sistemas Existentes

A aplicação do quadro teórico a algoritmos do mundo real produz classificações claras:

• Otimizados para Vazão (Conservadores de Trabalho):
  • Orca: Suporta agrupamento misto (preenchimento + decodificação) com prioridade de preenchimento.
  • Sarathi-Serve: Suporta preenchimento fragmentado (chunked) com prioridade de decodificação e agrupamento misto.
  • vLLM Mais Recente (com preenchimento fragmentado): Conservador de trabalho.
• Subótimos/Instáveis (Não Conservadores de Trabalho):
  • FasterTransformer: Prioriza a decodificação, mas proíbe o agrupamento misto. Deixa a GPU ociosa quando as solicitações de decodificação são insuficientes para preencher um lote, mesmo que solicitações de preenchimento estejam aguardando.
  • vLLM Vanilla: Prioriza o preenchimento, mas proíbe o agrupamento misto. Deixa solicitações de decodificação aguardando enquanto processa lotes apenas de preenchimento.
• Validação Experimental: Rastreamentos do mundo real confirmam que algoritmos não conservadores de trabalho (FasterTransformer, vLLM vanilla) tornam-se instáveis (explosão da fila) sob cargas moderadas onde algoritmos conservadores de trabalho (Sarathi-Serve, Orca) permanecem estáveis.

3. Cargas de Trabalho de Agentes de IA e Topologias de Rede

• DAG e Fork-Join: O artigo prova que o agendamento conservador de trabalho permanece otimizado para vazão em redes de servidores LLM organizados em DAGs ou topologias fork-join, desde que a condição de carga seja atendida em cada servidor.
• Roteamento Cíclico (Contraexemplo de Rybko–Stolyar): Os autores demonstram que o agendamento conservador de trabalho não é suficiente para redes com roteamento cíclico. Eles constroem uma rede de dois servidores onde atribuições de prioridade específicas sob uma política conservadora de trabalho levam à instabilidade, mesmo quando a carga total está abaixo da capacidade. Isso destaca a necessidade de um design cuidadoso de prioridades ou políticas não conservadoras de trabalho (por exemplo, contra-pressão) em topologias cíclicas.

4. Impacto das Restrições de Tamanho do Lote

Quando uma restrição de tamanho máximo de lote ($k_{max}$) é imposta juntamente com o orçamento de tokens ($b_{max}$):

• A região de estabilidade torna-se um envoltório convexo bidimensional no plano $(\lambda_{preenchimento}, \lambda_{decodificação})$, em vez de um limiar escalar simples.
• Descoberta Contra-intuitiva: Em certos regimes (especificamente perto de um vértice da região de estabilidade envolvendo lotes mistos), algoritmos estritamente conservadores de trabalho que sempre preenchem até $b_{max}$ podem falhar em estabilizar o sistema. A estabilidade ótima pode exigir operar com uma carga de tokens mais baixa (por exemplo, $b_0$) para equilibrar as taxas de processamento de tokens de preenchimento e decodificação. Isso sugere que, sob restrições apertadas de tamanho do lote, estratégias de agendamento adaptativas são necessárias.

Significado e Alegações

O artigo afirma fornecer a primeira base teórica de filas rigorosa para o agendamento de inferência de LLM. Seu significado reside em:

1. Princípio de Design: Identifica "conservador de trabalho" como um princípio de design chave para praticantes, oferecendo garantia teórica de que algoritmos como Sarathi-Serve e Orca são otimizados para vazão, enquanto alerta contra abordagens de agrupamento não misto como FasterTransformer e vLLM vanilla.
2. Ponte entre Comunidades: Reduz a barreira para a comunidade de teoria de filas contribuir com sistemas de LLM, fornecendo um modelo formal que captura as características únicas de duas fases e de agrupamento dos LLMs.
3. Orientação para Agentes de IA: Estende a análise de estabilidade para cargas de trabalho de agentes de IA, revelando que, embora topologias DAG sejam robustas, topologias cíclicas exigem agendamento mais sofisticado do que políticas simples conservadoras de trabalho.
4. Restrições Nuanceadas: Revela que restrições práticas, como limites de tamanho de lote, podem alterar fundamentalmente as regiões de estabilidade, desafiando a suposição de que "preencher o lote" é sempre ótimo.

Os autores concluem que, embora seu trabalho estabeleça uma linha de base para a otimalidade de vazão, trabalhos futuros devem abordar a otimização de latência, modelos de tempo de processamento mais ricos (incorporando camadas de atenção) e o design de algoritmos adaptativos para restrições complexas e topologias de rede.