Recency/Frequency Adaptive KV Caching for Large Language Model Serving

Resumo Técnico: Cache de KV Adaptativo por Recência/Frequência para Servimento de Grandes Modelos de Linguagem

Declaração do Problema
Sistemas de servimento de Grandes Modelos de Linguagem (LLMs) enfrentam desafios significativos na gestão de caches de Chave-Valor (KV) devido ao crescimento do tamanho dos modelos e das extensões de contexto, o que sobrecarrega a capacidade limitada de memória da GPU. Embora o cache de prefixo e o reuso sejam críticos para reduzir a computação redundante e melhorar o throughput, as estratégias de gestão existentes baseiam-se predominantemente em políticas de expulsão Least-Recently-Used (LRU). Os autores argumentam que o LRU é insuficiente para os padrões de acesso diversos e complexos encontrados em cargas de trabalho reais de LLM. Especificamente, o LRU falha em distinguir entre requisições que exibem forte localidade temporal (acesso recente) e aquelas que atuam como "hotspots" (acesso frequente entre diferentes usuários ou sessões). Essa limitação leva a cargas de trabalho não relacionadas a expulsarem os caches umas das outras, degradando as taxas de acerto (hit rates) e aumentando a latência, particularmente em cenários como Questionamento e Resposta (QA) baseado em documentos e conversas de múltiplos turnos.

Metodologia
Para abordar essas limitações, o artigo propõe a integração do algoritmo Adaptive Replacement Cache (ARC) ao framework de servimento vLLM. A metodologia introduz uma estratégia híbrida de recência-frequência que aloca dinamicamente o espaço de cache entre blocos de KV acessados recentemente e acessados frequentemente.

Os componentes técnicos centrais incluem:

1. Estrutura de Duas Filas: O cache é logicamente dividido em duas filas:
   • L1 (Fila de Recência): Contém itens acessados uma única vez (composta pelo cache físico $T1$ e cache fantasma $B1$).
   • L2 (Fila de Frequência): Contém itens acessados múltiplas vezes (composta pelo cache físico $T2$ e cache fantasma $B2$).
   • Itens na fila de recência são promovidos para a fila de frequência após um segundo acerto (hit).
2. Ghost Caching (Cache Fantasma): O sistema utiliza "caches fantasmas" ($B1$ e $B2$) que armazenam apenas metadados (não blocos KV completos) para itens expulsos. Esses caches rastreiam o histórico de expulsões.
   • Se uma requisição falha no cache principal (miss), mas acerta em um cache fantasma, isso serve como um sinal de feedback. Um acerto em $B1$ sugere que a fila de recência ($T1$) é muito pequena, enquanto um acerto em $B2$ sugere que a fila de frequência ($T2$) precisa de expansão.
3. Particionamento Dinâmico: Com base nos acertos nos caches fantasmas, o algoritmo ajusta dinamicamente o tamanho dos caches físicos $T1$ e $T2$, mantendo um tamanho total de cache fixo. Isso permite que o sistema se adapte a mudanças de carga de trabalho, como o surgimento de novos hotspots ou mudanças nos padrões de atividade do usuário.
4. Integração: A estratégia opera ao nível do bloco de KV (ex: 16 tokens), alinhando-se com o mecanismo de paged attention usado em sistemas de servimento modernos. É projetada para ser livre de parâmetros e integra-se diretamente ao módulo de evicção do vLLM.

Principais Contribuições

• Política de Expulsão Adaptativa: O artigo apresenta a primeira aplicação de ARC ao servimento de LLM, indo além de políticas estáticas baseadas em recência para uma abordagem híbrida dinâmica.
• Adaptabilidade de Carga de Trabalho: O método demonstra a capacidade de equilibrar automaticamente os recursos de cache entre padrões de acesso recente e frequente sem ajuste manual.
• Interpretabilidade: Ao contrário de abordagens baseadas em aprendizado que exigem preditores treinados, este método oferece interpretabilidade clara sobre como o espaço de cache é alocado com base no histórico de acesso.
• Implementação de Código Aberto: Os autores fornecem uma implementação de código aberto integrada ao vLLM, disponível para uso da comunidade e pesquisas futuras.

Resultados Experimentais
Os autores avaliaram o método proposto contra o baseline padrão LRU do vLLM e uma variante de duas filas estáticas (DBL) usando dois tipos primários de carga de trabalho:

1. Document QA Sintético: Usando os datasets QuALITY e WikiQA com amostragem de requisição distribuída por Zipf.
   • Taxa de Acerto (Hit Rate): Melhorou em até 10,8% (QuALITY) e 7,8% (WikiQA) em comparação ao LRU.
   • Tempo para o Primeiro Token (TTFT): Reduzido em até 12,6% (QuALITY) e 7,9% (WikiQA).
   • As melhorias foram mais pronunciadas em tamanhos de cache menores, onde as decisões de expulsão são mais frequentes.
2. Conversa do Mundo Real: Usando um traço do Qwen-Bailian Anonymous Dataset (43.058 requisições).
   • Taxa de Acerto (Hit Rate): Melhorou entre 1,1%–2,1%.
   • TTFT: Reduzido entre 1,0%–2,0%.
   • O estudo observou que o dimensionamento adaptativo tornou-se cada vez mais benéfico à medida que os tamanhos de cache cresciam, capturando mudanças de escala de carga de trabalho que as políticas estáticas perderam.
3. Inferência em Batch: Experimentos variando tamanhos de batch no dataset QuALITY mostraram que a vantagem relativa do ARC sobre o LRU persistiu e aumentou ligeiramente com maiores tamanhos de batch, mantendo uma redução de 5–7% no TTFT.

Significância e Alegações
O artigo alega que a gestão adaptativa de cache de KV é um mecanismo prático e eficaz para aumentar o desempenho do servimento de LLM. Ao capturar padrões de reuso além da simples recência, o método proposto melhora as taxas de acerto de cache e reduz a latência em diversas cargas de trabalho. Os autores enfatizam que sua abordagem generaliza bem para inferência em batch e fornece uma base para sistemas futuros lidarem com padrões de acesso complexos e variáveis sem o overhead de preditores baseados em treinamento. O trabalho sugere que o particionamento dinâmico de recursos de cache é um passo crítico para um deploy de LLM mais eficiente em ambientes de produção.