Resumo Técnico: Escalonamento Online com Consciência Geométrica para Atendimento de LLMs

Declaração do Problema

A implantação de Grandes Modelos de Linguagem (LLMs) em cenários interativos enfrenta um gargalo crítico: o gerenciamento da pegada de memória dinâmica do cache Key-Value (KV). Ao contrário dos problemas de escalonamento tradicionais, onde o tamanho do trabalho é estático, a inferência de LLM exibe um crescimento geométrico espaço-temporal 2D único.

1. Acoplamento Memória-Tempo: Na decodificação autorregressiva, o tempo de execução é linearmente acoplado à expansão de memória; cada token gerado aumenta a pegada do cache KV.
2. Dinâmica de Batching Contínuo: Motores modernos (ex: vLLM) utilizam batching contínuo, onde o tamanho do lote concorrente flutua dinamicamente após cada etapa de decodificação, conforme as requisições são concluídas e novas entram.

Heurísticas de escalonamento existentes, primariamente o Shortest Job First (SJF), estão enraizadas na modelagem clássica centrada no tempo. Elas falham em capturar a realidade geométrica do atendimento de LLM. Trabalhos teóricos recentes [10] demonstraram que, sob essas restrições geométricas específicas, o SJF produz uma razão competitiva de pior caso ilimitada, criando um hiato fundamental entre a teoria de escalonamento clássica e as realidades físicas da inferência de LLM moderna.

Metodologia

Os autores propõem um framework de Escalonamento Online com Consciência Geométrica que desloca a métrica de priorização do tempo de execução 1D para o volume de memória 2D.

Algoritmo Central: Smallest Volume First (SVF)

Em vez de isolar o tempo de execução, o SVF avalia a integral do consumo de memória ao longo de todo o ciclo de vida de uma requisição. Para uma requisição $r_i$ com comprimento de prompt $s_i$ e comprimento de saída $o_i$, o Volume $v_i$ é definido como:
$$v_i = s_i \cdot o_i + \frac{o_i^2 + o_i}{2}$$
Esta fórmula quantifica a área total de "memória-tempo" ocupada pela requisição. O SVF atua como uma política estritamente gananciosa, ordenando as requisições em ordem crescente de $v_i$. A implementação é desacoplada em dois processos: um preditor de segundo plano que agrupa requisições para consultar comprimentos de saída, e um escalonador que admite as requisições de maior prioridade (menor volume) no lote em execução até que a capacidade do cache KV seja atingida.

Variante Leve: 1-bit SVF

Para minimizar o overhead computacional, os autores introduzem o 1-bit SVF. Esta variante substitui a predição exata de comprimento por um classificador binário que categoriza requisições como "curtas" ($m=0$) ou "longas" ($m=1$).

• Ele atribui um comprimento de procuração global $O_m$ para cada classe.
• O volume de procuração é calculado como $\hat{v}_i = s_i \cdot O_m + \frac{O_m^2 + O_m}{2}$.
• Este design extrai apenas um bit de informação enquanto preserva as garantias de escalonamento espaço-temporal centrais.

Contribuições Teóricas

O artigo fornece uma base matemática rigorosa, indo além do teste empírico de tentativa e erro para garantias formais:

1. Limites de Pior Caso Estreitados (Chegadas em Rajadas):

   • Para o SVF com comprimentos de saída conhecidos sob modelos de chegada em rajadas, os autores provam uma razão competitiva (CR) de pior caso de CR $\le$ 5. Isso estreita significativamente o limite anterior de CR $\le$ 48 encontrado na literatura prévia [10].
   • A prova utiliza uma nova metodologia de "certificado macroscópico", mostrando que cada etapa bloqueada implica uma massa de memória ativa $> M/2$, alinhando diretamente o tempo de espera do algoritmo com o limite inferior do escalonamento offline ideal.
   • Para o 1-bit SVF, a razão competitiva é limitada por $O(T)$, onde $T$ é o comprimento máximo do modelo, provando que, mesmo com informações mínimas, o sistema permanece estável sob cargas extremas.

2. Limites Estocásticos (Chegadas de Poisson):

   • Sob processos de chegada de Poisson, o artigo deriva razões competitivas esperadas.
   • O SVF alcança $E[CR] \le 1 + \frac{4}{(1-\mu)(1-\rho)}$, onde $\mu$ relaciona-se com a distribuição geométrica de comprimentos e $\rho$ é a utilização do sistema.
   • A degradação de desempenho do 1-bit SVF é governada por uma "penalidade de distorção volumétrica" $\epsilon$, que decai exponencialmente com o limiar de classificação, garantindo estabilidade a longo prazo.

Resultados Experimentais

A abordagem foi implementada como uma camada plug-and-play dentro do vLLM e avaliada nos modelos Llama-3.1-8B e Llama-3.1-70B usando cargas de trabalho LMSYS-Chat e LongBench.

• Redução de Latência: O SVF consistentemente alcançou as menores latências médias e de cauda (P95) em todos os benchmarks, superando FCFS, SJF e até o Oracle-SJF (que possui conhecimento perfeito do futuro dos comprimentos) em cenários intensivos em memória (LongBench).
• Throughput: O SVF manteve um throughput maior que o SJF. O 1-bit SVF alcançou throughput e latência competitivos, muitas vezes superando o SJF em métricas de latência de cauda.
• Overhead: O overhead de predição foi insignificante. O preditor de comprimento total consumiu no máximo 0,06% da latência de ponta a ponta, enquanto o classificador de 1-bit consumiu $\le$ 0,01%.
• Justiça (Fairness): Contrário às heurísticas gananciosas clássicas que causam inanição (starvation) de trabalhos longos, a ganância com consciência geométrica do SVF libera rapidamente a memória do cache KV limitada, quebrando o bloqueio de cabeça de linha (head-of-line blocking) global e melhorando a justiça para requisições maiores.

Significância e Alegações

O artigo afirma estabelecer uma abordagem teoricamente sólida e empiricamente comprovada para resolver o escalonamento restrito por memória em implantações modernas de LLM. Sua principal significância reside em:

1. Mudança de Paradigma: Ele move o campo das heurísticas legadas de 1D centradas no tempo para a priorização 2D com consciência geométrica, abordando o descompasso fundamental entre a teoria de escalonamento clássica e a mecânica de inferência de LLM.
2. Avanço Teórico: Ao estreitar a razão competitiva de 48 para 5 e introduzir uma nova metodologia de prova, ele fornece garantias estruturais universais que se mantêm através de distribuições de carga de trabalho arbitrárias e adversárias.
3. Viabilidade Prática: A natureza "plug-and-play" do escalonador, combinada com a eficiência extrema da variante de 1-bit, demonstra que a otimização matemática rigorosa pode ser integrada perfeitamente em motores de inferência de alto desempenho sem overhead proibitivo.

Os autores concluem que esta abordagem com consciência geométrica não apenas otimiza a eficiência do sistema, mas também oferece implicações para o deployment sustentável de IA, reduzindo os recursos computacionais e a pegada de carbono necessários para a inferência em larga escala.