Resumo Técnico: Além da Predição: Escalonamento Consciente de Cauda para Inferência de LLM

1. Declaração do Problema

O serviço de Grandes Modelos de Linguagem (LLMs) enfrenta um desafio crítico no gerenciamento da extrema variabilidade nos comprimentos das requisições, particularmente com o surgimento de modelos aumentados por raciocínio que exibem geração de múltiplos passos, autorreflexão e terminação adaptativa. Essa variabilidade torna as políticas de escalonamento baseadas em tamanho (como o Shortest Job First - SJF, ou Shortest Remaining Processing Time - SRPT) frágeis.

Escalonadores de última geração dependem da predição de comprimentos de saída ou de tokens restantes para aproximar o SJF/SRPT. No entanto, o artigo identifica três problemas fundamentais com essa abordagem:

1. Fragilidade da Predição: A predição do comprimento da saída é inerentemente difícil devido à alta variância na geração de tokens (estocasticidade e não determinismo), tornando as políticas instáveis sob mudanças de distribuição e chegadas de carga (bursty arrivals).
2. Descompasso de Métricas: Políticas otimizadas para latência média (ex: média de TTFT/TBT) frequentemente apresentam um comportamento ruim de latência de cauda (P90–P99). No serviço de LLMs, a experiência do usuário é governada pelas latências de cauda (Time-To-Last-Token, TTLT), que são frequentemente a restrição limitante para os Objetivos de Nível de Serviço (SLOs).
3. Dinâmicas Acopladas à Memória: Diferente de filas clássicas, a inferência de LLM é estatal. As requisições acumulam grandes caches de Chave-Valor (KV) durante a decodificação. A preempção ingênua para priorizar trabalhos curtos pode levar à expulsão de cache, recomputação e "thrashing" caros, o que pode aumentar a latência de cauda apesar de reduzir o atraso de fila.

A questão central levantada é se os escalonadores precisam de predições explícitas de comprimento de trabalho para otimizar a latência de cauda. Os autores argumentam que não, propondo uma abordagem livre de predição e consciente da distribuição.

2. Metodologia: UNIBOOST

O artigo introduz o UNIBOOST, um framework de escalonamento livre de predição e consciente da distribuição que substitui a predição explícita de comprimento por um aumento de prioridade "suave" (soft priority boosting) impulsionado por sinais estatísticos leves. O design é uma co-otimização de escalonamento e preempção consciente de cache, estruturado em quatro fases:

Fase 1: Strawman (DISTBOOST)

A abordagem inicial trata as fases de prefill e decode como problemas distintos. Ela utiliza uma função de aumento $\gamma$-Boost (inspirada na teoria de filas) para requisições de prefill, mas prioriza a fila de decode. Embora isso melhore as métricas de cauda para decodificação, sofre de bloqueio de Cabeça de Linha (Head-of-Line - HoL), onde requisições de prefill são negligenciadas por trabalhos de decode de longa duração.

Fase 2: Priorização Unificada (UNIBOOST-BASE)

Para resolver o bloqueio de HoL, os autores unificam as filas de prefill e decode em um único espaço de prioridade.

• Pontuação de Prioridade: As requisições são pontuadas com base em $\phi_i(t) = a_i - b_\gamma(\tilde{w}_i(t))$, onde $a_i$ é o tempo de chegada e $\tilde{w}_i(t)$ é o trabalho efetivo (máximo entre o trabalho alcançado e o comprimento do prefill).
• Função de Aumento: $b_\gamma(w) = \frac{1}{\gamma} \log(\frac{1}{1 - e^{-\gamma w}})$. Esta função fornece um aumento de prioridade "suave" para requisições com menos serviço alcançado, evitando a preempção severa do SRPT clássico.
• Mecanismo: O escalonador seleciona a requisição com a menor pontuação, permitindo a preempção entre fases, mas controlada por um parâmetro de histerese para evitar oscilações.

Fase 3: Estabilidade via MEMGUARD (Histerese Consciente de KV)

Para mitigar o alto custo de expulsão e recomputação do cache KV, os autores introduzem o MEMGUARD.

• Prioridades Quantizadas: Em vez de atualizar as prioridades continuamente, o sistema discretiza a métrica de trabalho alcançado ($\hat{w}_i$) usando quantização geométrica (ex: limiares em $k, 2k, 4k...$).
• Execução Mínima: Uma vez que uma requisição é despachada, ela não pode ser expulsa até que seu trabalho alcançado cruze o próximo limiar de quantização. Isso amortiza os custos de movimentação de KV e limita as oportunidades de preempção a um limite logarítmico em relação ao comprimento do trabalho.

Fase 4: Estimativa de Parâmetros Adaptativos ($\gamma$-Ada)

O parâmetro de aumento $\gamma$ impacta significativamente o comportamento da cauda. Um $\gamma$ estático é subótimo sob cargas variáveis.

• Estimativa Online: O sistema estima uma inclinação de cauda efetiva ($\gamma_{eff}$) ajustando uma inclinação log-linear à cauda superior da distribuição de tempo de resposta observada (entre P95 e P99).
• Adaptação: O escalonador ajusta dinamicamente o $\gamma$ para interpolar entre FCFS (protegendo a cauda) e LAS (otimizando a média), adaptando-se a mudanças de carga sem predição explícita.

3. Principais Contribuições

1. Otimização de Cauda Livre de Predição: Demonstra que não é necessária a predição explícita do comprimento do trabalho para otimizar a latência de cauda. Em vez disso, sinais estatísticos leves e aumentos suaves são suficientes.
2. Co-Design de Escalonamento e Expulsão: Introduz um framework que otimiza conjuntamente as decisões de escalonamento com o gerenciamento de cache KV. Ao acoplar o escalonamento baseado em aumento com o controle de execução consciente de expulsão (MEMGUARD), o sistema evita a degradação de desempenho causada pelo thrashing de cache.
3. Robustez a Mudanças de Distribuição: O método proposto se adapta a diversas cargas de trabalho (cauda pesada vs. cauda leve, raciocínio vs. chat) sem necessidade de retreinamento ou modelos de predição complexos.
4. Fundamentação Teórica: Adapta a política $\gamma$-Boost da teoria de filas para as restrições específicas da inferência de LLM (estatismo, acoplamento de memória).

4. Resultados Experimentais

Avaliado em rastreios de produção e de código aberto (Azure, ShareGPT, S1K) usando modelos como Llama-3-8B, CodeLlama-34B e Qwen-72B em GPUs NVIDIA A100:

• Redução de Latência de Cauda: O UNIBOOST alcança um P99 TTLT até 35–50% menor que o SRPT com predição de comprimento perfeita (TRAIL+). Também reduz o P99 TTFT em 34–47% em várias cargas de trabalho.
• Vazão (Throughput): O método melhora a vazão em 1.01–1.12$\times$ sob cargas de trabalho intensas (bursty) comparado aos baselines.
• Atingimento de SLO: O UNIBOOST permite que sistemas tolerem 2.9–8.7$\times$ mais SLOs rigorosos para TTFT mantendo 99% de atingimento em comparação com abordagens baseadas em SJF.
• Estudos de Ablação:
  • Remover a priorização unificada (Fase 2) leva à fome (starvation) de prefill.
  • Remover o MEMGUARD (Fase 3) causa picos significativos de latência de cauda devido ao thrashing de KV.
  • Remover o $\gamma$ adaptativo (Fase 4) reduz a robustez sob mudanças de carga.
• Comparação: O método supera os baselines de última geração, incluindo o Sarathi da vLLM (prefill em blocos), LTR (aprendizado para ranking SJF) e TRAIL (SRPT baseado em predição), particularmente em cargas de trabalho intensas em raciocínio, onde a qualidade da predição é mais instável.

5. Significância e Alegações

O artigo afirma que o UNIBOOST fornece uma alternativa robusta para políticas de escalonamento dependentes de predição para o serviço online de LLMs. Sua significância reside em:

• Desacoplamento da Predição: Remove a dependência de predições precisas de comprimento, que é um grande gargalo em cargas de trabalho de raciocínio e de comprimento variável.
• Otimização Holística: Aborda simultaneamente o compromisso "média vs. cauda" e o compromisso "escalonamento vs. memória", ofereando uma solução que é eficaz mesmo quando a qualidade da predição degrada.
• Praticidade: O design é simples de integrar em stacks de continuous-batching existentes (como vLLM e SGLang) e depende de estatísticas de tempo de execução leves em vez de modelos de ML complexos.

Os autores concluem que o escalonamento consciente da distribuição e da expulsão é essencial para a próxima geração de serviço de LLM, especialmente à medida que os modelos se tornam mais capazes de raciocínio de comprimento variável.