Resumo Técnico: SAECache – Evicção Semântica para Caches de Prefixo de LLM

Declaração do Problema

A cache de prefixo em Modelos de Linguagem de Grande Escala (LLMs) visa reduzir a latência de inferência (especificamente o Tempo até o Primeiro Token, ou TTFT) reutilizando estados Chave-Valor (KV) de solicitações que compartilham prefixos de entrada. No entanto, a eficácia da cache de prefixo é severamente limitada pela memória GPU restrita, tornando necessária uma política de evicção para descartar blocos menos valiosos quando a capacidade é atingida.

Políticas de evicção existentes, como Menos Recentemente Usado (LRU) e Menos Frequentemente Usado (LFU), baseiam-se principalmente em estatísticas de tempo de acesso ou frequência. Essas abordagens agnósticas a tokens tratam todos os blocos em cache de forma uniforme, ignorando duas dimensões críticas das cargas de trabalho de LLM:

1. Heterogeneidade Semântica: Diferentes tipos de tokens (por exemplo, prompts de sistema vs. raciocínio de cadeia de pensamento) exibem taxas de reutilização intrínsecas drasticamente diferentes.
2. Variabilidade da Carga de Trabalho: Padrões de reutilização diferem significativamente entre solicitações de turno único com templates (reutilização estrutural) e conversas de múltiplos turnos (reutilização temporal local à sessão), com intervalos entre turnos seguindo distribuições distintas em diferentes tipos de aplicação (por exemplo, chat vs. fluxos de trabalho de agentes).

Os autores observam que tratar um bloco de prompt de sistema de alto valor e um bloco de cadeia de pensamento de baixo valor como equivalentes quando sua recência coincide leva a uma alocação de memória subótima. Além disso, políticas de parâmetros fixos falham quando as composições de carga de trabalho mudam, causando degradação de desempenho de até 2,7× sob incompatibilidade de carga de trabalho.

Metodologia: SAECache

Para abordar essas limitações, os autores propõem o SAECache (Evicção Adaptativa Semântica para caches de prefixo), uma política que integra a estrutura semântica de tokens com adaptação de carga de trabalho online. O sistema opera por meio de três mecanismos principais:

1. Arquitetura de Múltiplas Filas com Roteamento Baseado em Regras

O SAECache roteia blocos KV para quatro filas distintas com base em seus padrões de reutilização dominantes, em vez de uma única fila global:

• Fila de Evicção Prioritária: Armazena blocos de baixo valor, incluindo tokens da fase de decodificação e blocos de pré-preenchimento sem template com baixo potencial de reutilização. Estes são esvaziados primeiro.
• Fila Estrutural: Armazena blocos KV de sessões de turno único que dependem de estruturas de prompt compartilhadas (por exemplo, templates de uso de ferramentas, instruções de programação).
• Fila de Chat: Armazena blocos de múltiplos turnos de sessões conversacionais, modelando a reutilização temporal local à sessão.
• Fila de Agente: Armazena blocos de múltiplos turnos de sessões de agente/usuário de ferramentas, que exibem conteúdo de token e distribuições de intervalo de solicitação diferentes em comparação com o chat padrão.

Um preditor de sessão de múltiplos turnos leve (um MLP de 3 camadas que reutiliza os estados ocultos finais do modelo de serviço) resolve ambiguidades para a primeira solicitação de uma sessão, roteando-a para a fila de múltiplos turnos apropriada se uma continuação for prevista, ou para as filas estrutural/de evicção prioritária caso contrário.

2. Pontuação de Prioridade Local

Dentro de cada fila, os blocos são pontuados para evicção com base em uma métrica composta $P(b)$:
$$P(b) = \alpha_q \cdot w_{\tau(b)} \cdot \frac{p_q(b)}{\Delta t_b}$$

• $\alpha_q$ (Peso da Fila): Um peso dinâmico refletindo a eficiência de acerto recente da fila específica.
• $w_{\tau(b)}$ (Peso do Tipo de Token): Um peso aprendido específico para o tipo de token (por exemplo, prompt de sistema, consulta do usuário, cadeia de pensamento) do bloco.
• $p_q(b)$ (Probabilidade de Sobrevivência Local):
  • Para filas de Chat/Agente: Calculada como a probabilidade de sobrevivência $1 - F_{LN}(\Delta t_b; \mu_q, \sigma_q)$ sob uma distribuição log-normal ajustada aos intervalos entre turnos desse tipo de sessão.
  • Para a fila Estrutural: Calculada como $1 - (o_b / o_{max})^\gamma$, onde $o_b$ é o deslocamento do bloco e $\gamma$ é uma potência de decaimento aprendida, priorizando blocos iniciais em um prompt.
• $\Delta t_b$: O tempo decorrido desde o último acesso ao bloco.

3. Aprendizado Online Totalmente Adaptativo

O SAECache elimina o ajuste manual atualizando todos os parâmetros online por meio de um loop de feedback unificado baseado em estatísticas de acerto/erro de cache:

• Pesos de Tipo de Token: Atualizados via Média Móvel Exponencial (EMA) com base nas taxas de "erro após evicção" e nas taxas gerais de acerto.
• Parâmetros Log-Normais ($\mu, \sigma$): Estimados online usando Estimativa de Máxima Verossimilhança (MLE) em tempos de acesso observados para filas de chat e agente.
• Potência de Decaimento de Posição ($\gamma$): Aprendida a partir de correlações entre a posição do bloco e as taxas de acerto na fila estrutural.
• Pesos de Fila ($\alpha_q$): Atualizados com base na razão de tokens de acerto para capacidade alocada para cada fila, escalonados por um parâmetro de temperatura.

Principais Contribuições

1. Caracterização Empírica: Um estudo sistemático revelando que a reutilização de tokens varia em até 756× entre tipos de tokens (92,3% para prompts de sistema vs. 2,2% para cadeia de pensamento) e que os intervalos entre turnos seguem distribuições log-normais específicas da sessão, em vez de decaimentos exponenciais simples.
2. Política SAECache: Uma política de evicção de múltiplas filas, consciente de semântica, que desacopla mecanismos de reutilização heterogêneos (estrutural vs. temporal) e atribui prioridades distintas a tipos de tokens.
3. Adaptação Online: Um framework de aprendizado que ajusta automaticamente distribuições de tempo, decaimento de posição e parâmetros de ponderação sem intervenção manual, adaptando-se a mudanças nas composições de carga de trabalho.
4. Avaliação Abrangente: Experimentos extensivos em conjuntos de dados do mundo real (ShareGPT, LMSys, Chatbot-Arena) demonstrando robustez em cargas de trabalho heterogêneas.

Resultados Experimentais

Avaliado em uma implementação vLLM com Qwen2.5-1.5B-Instruct em uma GPU NVIDIA A40, o SAECache foi comparado ao LRU (base de produção) e à Cache de Prefixo Aprendida (LPC).

• Melhoria no TTFT: O SAECache alcançou uma melhoria de 1,4× a 2,7× no TTFT em relação às bases de estilo de produção em cargas de trabalho heterogêneas.
• Taxa de Acerto de Cache: O SAECache consistentemente alcançou as maiores taxas de acerto de cache, melhorando em 4,8–5,9 pontos percentuais sobre a base mais forte (LRU ou LPC) em todas as configurações testadas.
• Resiliência a Incompatibilidade de Carga de Trabalho: Alternativas de parâmetros fixos sofreram até 2,7× de degradação no TTFT quando a composição da carga de trabalho desviou do rastro de treinamento. O SAECache manteve desempenho estável ao adaptar seus parâmetros online.
• Estudos de Ablação:
  • A ponderação consciente do tipo de token contribuiu com uma melhoria adicional de 23%.
  • A ponderação adaptativa de fila contribuiu com o maior ganho em 39%.
  • O tempo log-normal e o aprendizado de decaimento de posição forneceram ganhos adicionais de 14% e 12%, respectivamente.
• Sobrecarga: O preditor de sessão de múltiplos turnos é altamente eficiente, exigindo apenas ~1M de parâmetros (vs. 118M para o modelo de incorporação do LPC) e alcançando uma taxa de transferência de inferência 8,8× maior.

Significado e Alegações

O artigo afirma que a evicção de cache de prefixo não deve tratar todos os blocos em cache de forma uniforme, mesmo quando compartilham estatísticas semelhantes de recência ou frequência. Os autores afirmam que semântica de token, estrutura de prompt e tipo de sessão são drivers fundamentais de reutilização que políticas existentes falham em capturar.

O significado do SAECache reside em sua capacidade de:

1. Preencher a lacuna entre políticas heurísticas estáticas e a realidade dinâmica e semântica do serviço de LLM.
2. Eliminar o ajuste manual, tornando o sistema robusto a mudanças de carga de trabalho (por exemplo, de tráfego pesado em chat para tráfego pesado em uso de ferramentas) sem retreinamento ou ajuste de parâmetros.
3. Demonstrar que a evicção granular e consciente de semântica é uma escolha de design crítica para o serviço eficiente de LLM, particularmente em ambientes com alta pressão de cache e padrões de solicitação heterogêneos.

Os autores observam que, embora o SAECache se destaque em cargas de trabalho de múltiplos turnos e mistas, sua sobrecarga pode reduzir ligeiramente o desempenho em regimes dominados por turno único (por exemplo, Chatbot-Arena), onde os benefícios de taxas de acerto mais altas não compensam totalmente os custos de gerenciamento, destacando a necessidade de estratégias adaptativas que possam escalar com as características da carga de trabalho.