SageSched: Efficient LLM Scheduling Confronting Demand Uncertainty and Hybridity

O artigo apresenta o SageSched, um agendador eficiente para inferência de LLMs que supera as limitações das abordagens existentes ao lidar com a incerteza da demanda e a natureza híbrida das cargas de trabalho, combinando previsões precisas de comprimento de saída com uma política de agendamento que considera simultaneamente custos computacionais e de memória para alcançar ganhos de eficiência superiores a 28,7%.

O essencial

Imagine que você é o gerente de um restaurante muito famoso e moderno, onde os clientes (os usuários) pedem pratos complexos feitos por um chef robô superinteligente (a Inteligência Artificial ou LLM).

O problema é que esse restaurante tem dois desafios gigantescos que os gerentes antigos não sabiam resolver:

1. A Incerteza do Pedido: Quando um cliente pede um prato, o chef não sabe exatamente quanto tempo vai demorar para cozinhar. Um pedido de "sopa" pode demorar 5 minutos ou 50 minutos, dependendo de como o cliente quer o tempero. Ninguém sabe o tamanho do prato antes de ele estar pronto.
2. A Mistura de Recursos: Cozinhar esses pratos exige duas coisas ao mesmo tempo: muito fogo (processamento do computador) e muitas panelas (memória do computador). Às vezes, o gargalo é o fogo; outras vezes, é a falta de panelas.

O Problema dos Gerentes Antigos (Sistemas Atuais)

Os sistemas atuais de agendamento (como o vLLM ou SGLang) funcionam de duas formas ruins:

• A fila da padaria (FCFS): "Quem chegou primeiro, é atendido primeiro." Se um cliente pedir um banquete gigante (que vai demorar horas), todos os outros clientes ficam esperando na fila, mesmo que seus pedidos sejam rápidos. Isso é chamado de "bloqueio da cabeça da fila".
• O palpite cego (SJF): Alguns sistemas tentam adivinhar o tempo de cozimento usando um modelo complexo (como um chef que estuda o pedido antes). Mas isso é caro, lento e muitas vezes erra, porque a IA é imprevisível. Além disso, eles só olham para o "tempo de fogo" e esquecem das "panelas". Se o restaurante estiver sem panelas, priorizar um prato rápido que usa 100 panelas vai travar a cozinha inteira.

A Solução: SageSched (O Gerente Sábio)

Os autores criaram o SageSched, um novo sistema de gerenciamento que é como um gerente experiente e sábio. Ele usa três truques mágicos:

1. O "Detetive de Pedidos Semelhantes" (Previsão Inteligente)

Em vez de tentar adivinhar o futuro com um modelo complexo, o SageSched olha para o histórico.

• A Analogia: Imagine que um cliente pede "uma receita de bolo de chocolate com frutas". O gerente olha no livro de pedidos de ontem e vê: "Ah, três pessoas pediram algo muito parecido e os bolos ficaram com tamanhos entre 20 e 30 fatias".
• O Truque: Ele não tenta prever um número exato (que seria errado). Ele cria uma distribuição de probabilidade: "Há 30% de chance de ser pequeno, 50% médio e 20% grande". Isso é leve, rápido e muito mais preciso do que tentar simular a receita inteira de novo.

2. A "Medida de Custo Real" (Fogo + Panelas)

O SageSched entende que o custo de um pedido não é apenas o tempo, mas a combinação de tempo de cozimento e quantidade de panelas usadas.

• A Analogia: Se o restaurante está sem panelas, ele não vai priorizar um prato rápido que precisa de 50 panelas, mesmo que seja rápido. Ele vai priorizar um prato que usa apenas 2 panelas, liberando espaço para outros.
• O Truque: Ele calcula um "custo total" que considera tanto o processamento quanto a memória. Se o sistema está cheio de memória, ele age de um jeito; se está cheio de processamento, age de outro.

3. O "Índice de Sorte" (Agendamento com Incerteza)

Aqui está a parte mais genial. Como ninguém sabe o tamanho exato do prato, como decidir quem atender?

• A Analogia: Imagine que você tem várias apostas. Uma aposta pode ganhar $100 amanhã, mas tem 90% de chance de não ganhar nada. Outra pode ganhar $10 com certeza. Qual você escolhe?
• O Truque (Índice de Gittins): O SageSched usa uma fórmula matemática chamada Índice de Gittins. Em vez de olhar para a "média" (o que é comum), ele olha para a probabilidade de terminar logo. Ele prioriza os pedidos que têm a maior chance de serem concluídos agora, mesmo que o tamanho total seja incerto. É como dizer: "Vamos servir primeiro quem tem mais chance de sair da cozinha em 5 minutos, em vez de quem tem o pedido médio mais curto".

O Resultado

Quando os autores testaram o SageSched em laboratórios e simulações:

• O tempo total que os clientes esperavam para receber tudo o que pediram (TTLT) caiu em mais de 28%.
• O sistema funcionou bem tanto em restaurantes pequenos quanto em grandes redes de 64 cozinhas (GPUs).
• Ele foi rápido demais para atrasar o serviço: o tempo extra para o gerente pensar na fila foi de apenas 100 milissegundos (menos que um piscar de olhos).

Resumo em uma Frase

O SageSched é como um gerente de restaurante que não tenta adivinhar o futuro, mas sim olha para o passado recente para entender as probabilidades, considera tanto o tempo quanto o espaço na cozinha, e usa matemática avançada para decidir quem atender primeiro, garantindo que ninguém fique esperando em vão.

Resumo técnico

Título: SageSched: Agendamento Eficiente de LLM Enfrentando Incerteza e Heterogeneidade da Demanda

1. O Problema

O agendamento eficiente de inferências de Grandes Modelos de Linguagem (LLMs) é crítico para a experiência do usuário, especialmente para minimizar a latência total até o último token (Time-to-Last-Token - TTLT). No entanto, os trabalhos existentes falham em lidar com duas características fundamentais das cargas de trabalho de LLMs:

1. Incerteza da Demanda: Diferente de cargas de trabalho tradicionais (como SO ou Big Data), o comprimento de saída de uma inferência de LLM é não determinístico devido à natureza autoregressiva. O número exato de tokens gerados só é conhecido após a conclusão, tornando difícil prever o tempo de execução.
2. Heterogeneidade (Hybridity) da Demanda: As inferências de LLM consomem intensamente tanto recursos de computação (operações matriciais) quanto de memória (KVCache para evitar recomputação). Agendadores tradicionais focam apenas no custo computacional, ignorando que o gargalo pode ser a memória, especialmente em sequências longas.

Limitações das Soluções Atuais:

• Heurísticas Simples: Frameworks como vLLM e SGLang usam "Primeiro a Chegar, Primeiro a Ser Atendido" (FCFS), causando bloqueio de linha (head-of-line blocking).
• Previsão de Comprimento Único: Agendadores recentes tentam prever o comprimento de saída usando modelos finamente ajustados (ex: BERT), mas isso é pesado computacionalmente e impreciso, pois fornece apenas um valor único, ignorando a distribuição probabilística da incerteza.
• Modelagem de Custo Incompleta: A maioria trata o custo apenas como o número de tokens de saída, negligenciando o consumo de memória (KVCache), o que leva a decisões de agendamento subótimas quando a memória é o gargalo.

2. Metodologia: SageSched

O SageSched é um agendador projetado para lidar com incerteza e heterogeneidade através de três técnicas principais:

A. Preditor Baseado em Histórico Consciente Semântico (Semantic-aware History-based Predictor)

• Abordagem: Em vez de treinar um modelo pesado para prever o comprimento de saída, o SageSched utiliza a correlação entre a similaridade semântica do prompt e a similaridade da distribuição de comprimento de saída.
• Mecanismo: Para cada nova solicitação, o sistema busca no histórico de requisições passadas (armazenado em uma janela deslizante) aquelas com prompts semanticamente similares (usando embeddings e busca de similaridade cosseno).
• Resultado: Em vez de prever um número único, ele gera uma distribuição de probabilidade de comprimentos de saída baseada nas execuções históricas de prompts similares. Isso elimina a necessidade de treinamento de modelos e é leve e preciso.

B. Modelagem de Custo Baseada em Limites de Recursos (Resource-bound-based Cost Modeling)

• Análise: O sistema identifica se o backend está limitado por computação ou memória.
• Modelo Unificado: O authors derivaram que tanto o custo de computação quanto o de memória seguem o mesmo paradigma matemático em relação ao comprimento da sequência (input $I$ e output $O$).
• Fórmula: O custo total $C$ é modelado como $C = \frac{O^2}{2} + IO$.
  • Isso difere de modelos anteriores que usavam apenas $O$ ou uma soma ponderada simples de $I$ e $O$.
  • Este modelo captura o custo cumulativo do KVCache e do tempo de computação de atenção, sendo aplicável independentemente de qual recurso seja o gargalo.

C. Agendamento Consciente de Incerteza (Uncertainty-aware Scheduling Policy)

• Problema: Usar o valor médio (esperado) da distribuição de custo para priorizar requisições é subótimo.
• Solução: O SageSched utiliza a Política de Gittins (Gittins Index), originalmente desenvolvida para problemas de "bandit multi-armado".
• Funcionamento:
  • Calcula o Índice de Gittins para cada solicitação baseada na sua distribuição de custo.
  • Prioriza solicitações com índices menores, o que teoricamente minimiza a latência média (TTLT) para tarefas com durações desconhecidas, mas distribuições conhecidas.
  • Atualização Dinâmica: O índice é recalculado periodicamente (em "buckets" de custo) durante a execução da inferência para manter a precisão sem gerar sobrecarga excessiva de reagendamento.

3. Principais Contribuições

1. Identificação de Limitações: Demonstração empírica de que agendadores atuais falham ao lidar com a incerteza intrínseca e a natureza híbrida (memória/computação) das cargas de LLM.
2. Projeto do SageSched: Um novo agendador que integra:
   • Predição de distribuição de comprimento baseada em histórico semântico (leve e sem treinamento).
   • Modelagem de custo unificada que considera ambos os recursos.
   • Política de agendamento baseada no Índice de Gittins para otimização teórica de latência.
3. Validação Abrangente: Implementação sobre o framework vLLM e avaliação extensiva com rastreamentos reais e simulações em larga escala.

4. Resultados Experimentais

Os experimentos foram realizados em servidores com GPUs A40 e H800, utilizando modelos Llama3.1-8B e Qwen3-32B e datasets como SharedGPT, Alpaca e Document-Write.

• Melhoria de Desempenho: O SageSched superou os agendadores mais avançados (como TRAIL, SSJF e FastServe) com uma melhoria de mais de 28,7% no TTLT médio.
• Robustez: O sistema manteve alto desempenho mesmo sob altas taxas de concorrência e em diferentes distribuições de datasets (especialmente no dataset Alpaca, onde o comprimento de entrada é longo e a modelagem de custo é crítica).
• Overhead: A análise de escalabilidade (até 64 nós GPU) mostrou que o overhead de previsão e agendamento é linear e negligenciável (aprox. 100ms adicionais por requisição em escala máxima), dado que as inferências de LLM ocorrem em escala de segundos.
• Análise de Componentes:
  • O preditor baseado em histórico superou preditores baseados em modelos LLM (mais rápidos e precisos).
  • O modelo de custo baseado em recursos superou modelos baseados apenas no comprimento de saída.
  • A política de Gittins superou a priorização baseada em valores médios, especialmente em cenários com alta incerteza.

5. Significado e Impacto

O SageSched representa um avanço significativo na infraestrutura de serviço de LLMs. Ao tratar a incerteza não como um ruído a ser ignorado, mas como uma distribuição probabilística utilizável, e ao considerar a memória como um recurso de primeira classe no agendamento, o sistema oferece uma solução teórica e prática para otimizar a experiência do usuário final.

A abordagem demonstra que é possível alcançar eficiência próxima do ótimo teórico (usando a Política de Gittins) sem a complexidade de modelos de previsão pesados, tornando-a viável para implantação em produção em grandes clusters de GPU. Isso é crucial para a escalabilidade de aplicações de IA generativa, onde a latência e a eficiência de recursos são fatores determinantes para a viabilidade econômica e a satisfação do usuário.