Resumo Técnico: Um Framework Teórico de Filas para Análise de Estabilidade de Inferência de LLM com Restrições de Memória de Cache KV

Declaração do Problema

A rápida adoção de Modelos de Linguagem de Grande Escala (LLMs) criou desafios significativos para a inferência eficiente em escala. Diferentemente de cargas de trabalho tradicionais, a inferência de LLMs é limitada por um gargalo duplo: a vazão computacional e a sobrecarga de memória do cache de Chave-Valor (KV). Embora o cache KV acelere a decodificação ao reutilizar representações de tokens gerados anteriormente, ele consome memória GPU substancial, tornando-se frequentemente a principal restrição de capacidade.

Modelos de filas existentes para inferência de LLMs geralmente focam em limites computacionais ou tratam a memória como uma restrição estática, falhando em capturar a interdependência dinâmica entre computação e crescimento de memória durante o processo de inferência. Especificamente, à medida que uma solicitação avança pelas fases de prompt (preenchimento) e geração de tokens (decodificação), sua pegada de memória evolui linearmente. Se a taxa de chegada de solicitações exceder a taxa de serviço efetiva do sistema — determinada conjuntamente pela computação da GPU e pela memória de cache KV disponível — as filas crescem sem limite, levando à instabilidade do sistema, latência inaceitável e degradação da experiência do usuário. Há uma falta de frameworks teóricos rigorosos que incorporem explicitamente essas restrições dinâmicas de memória para determinar condições de estabilidade e orientar o provisionamento de GPUs.

Metodologia

Os autores propõem um novo framework teórico de filas que modela a inferência de LLM como um sistema de filas em tempo discreto, conservador de trabalho, sujeito a uma restrição rígida de memória de cache KV ($M$).

1. Modelo do Sistema

• Estrutura da Solicitação: Cada solicitação $i$ consiste em um prompt de tamanho $s_i$ e uma resposta de comprimento $o_i$, amostrados de uma distribuição conjunta $F_{in-out}$.
• Fases de Processamento:
  • Fase de Prompt: Prompts são processados em blocos de tamanho fixo ($\hat{s}$). O uso de memória para o $j$-ésimo bloco de um prompt cresce linearmente ($j \times \hat{s}$).
  • Fase de Decodificação: À medida que os tokens são gerados sequencialmente, o uso de memória aumenta em uma quantidade equivalente ao cache KV de um token por etapa. A memória total para uma solicitação atinge $s_i + o_i$ ao ser concluída.
• Restrição de Memória: O sistema deve satisfazer $\sum_{i \in S(t)} (c_i^{(t)}\hat{s} + d_i^{(t)}) \le M$ em todos os instantes $t$, onde $S(t)$ é o conjunto de solicitações ativas, $c_i^{(t)}$ é o índice do bloco de prompt processado e $d_i^{(t)}$ é o índice do token de saída processado.
• Agendamento: O framework assume agendamento contínuo (continuous batching) e políticas conservadoras de trabalho (por exemplo, Primeiro a Chegar, Primeiro a Ser Atendido), onde o servidor processa o próximo prompt prioritário sempre que a capacidade permitir.

2. Derivação Teórica

Os autores definem o uso cumulativo de memória ao longo da vida útil $g(s, o)$ para uma única solicitação, representando a "área" total de memória consumida durante todo o tempo de serviço da solicitação.
$$g(s, o) := \sum_{k=1}^{s/\hat{s}} k\hat{s} + \sum_{j=1}^{o} (s+j)$$
Com base nisso, eles derivam a taxa de serviço estável máxima $\mu$:
$$\mu = \frac{M}{\bar{b} \mathbb{E}_{s,o \sim p(s,o)}[g(s, o)]}$$
onde $\bar{b}$ é o tempo de processamento de lote normalizado.

3. Análise de Estabilidade

Utilizando um argumento de deriva de Lyapunov adaptado para a dinâmica de memória linear por partes dos LLMs, o artigo estabelece dois teoremas-chave:

• Instabilidade: Se a taxa de chegada $\lambda > \mu$, o sistema está sobrecarregado e o número de solicitações cresce até o infinito.
• Estabilidade: Se $\lambda < \mu(1 - \delta)$, onde $\delta = \frac{\text{ess sup}(s+o)}{M} \ll 1$ representa a folga de memória necessária para acomodar o maior trabalho único, o sistema é estável (cadeia de Markov recorrente positiva).

Principais Contribuições

1. Modelagem Inovadora: O artigo introduz o primeiro modelo de filas para inferência de LLM que integra explicitamente tanto a demanda computacional quanto as restrições dinâmicas de memória da GPU governadas pelo cache KV. Ele generaliza modelos anteriores ao adicionar consciência de memória e refinar configurações de agendamento com fases de preenchimento em blocos.
2. Condições de Estabilidade Rigorosas: Os autores derivam condições de estabilidade e instabilidade em forma fechada. Esses resultados fornecem uma base fundamentada para determinar a vazão sustentável máxima de um sistema de serviço de LLM sob cargas de trabalho estocásticas.
3. Validação Empírica: As previsões teóricas são validadas por meio de experimentos extensivos em ambientes de produção reais de GPU (NVIDIA A100), cobrindo configurações de GPU única e multi-GPU (paralelismo de dados).

Resultados Experimentais

Os autores conduziram experimentos utilizando o modelo Meta-Llama-3-8B em um banco de testes de 8 GPUs com o motor de inferência vLLM.

• Precisão: A taxa de serviço teórica $\mu_{theory}$ corresponde estreitamente à taxa medida empiricamente $\mu_{gpu}$. Em várias razões de prompt para decodificação (P/D) (1:1, 2:1, 1:2) e em um conjunto de dados do mundo real (LongBench v2), o erro de previsão (Gap Absolute Percentage) permaneceu dentro de 10% (variando especificamente de 2,25% a 8,38%).
• Escalabilidade Multi-GPU: Em uma configuração de cluster de 8 GPUs, o modelo teórico escalou linearmente, alcançando uma diferença de apenas 3,38% entre as taxas previstas e observadas.
• Dinâmica de Estabilidade: Os experimentos confirmaram que, quando $\lambda < \mu$, os comprimentos das filas permaneceram limitados (por exemplo, $\le 5$ para GPU única), enquanto $\lambda > \mu$ resultou em crescimento linear e ilimitado das filas.

Significado e Alegações

O artigo alega fornecer uma ferramenta poderosa para implantação de sistemas e provisionamento de recursos. Ao combinar uma taxa de chegada de solicitações estimada com a taxa de serviço estável derivada, os operadores podem calcular o tamanho necessário do cluster para:

• Evitar compras excessivas custosas (GPUs ociosas).
• Prevenir subprovisionamento que viola o desempenho (filas ilimitadas e picos de latência).

Os autores enfatizam que seu framework oferece uma "base fundamentada" para o planejamento de capacidade, permitindo que os profissionais equilibrem quantitativamente capacidade e demanda. Eles observam que, embora seu trabalho atual se concentre em implantações de paralelismo de dados, o framework pode ser estendido ao paralelismo tensorial ajustando os parâmetros de memória efetiva e tempo de lote, embora o paralelismo de pipeline e a desagregação requeiram estudos adicionais. Os resultados confirmam que incorporar a dinâmica de memória em modelos de filas é essencial para uma análise de estabilidade precisa em modernos sistemas de serviço de LLM.