Resumo Técnico: CachePrune

Declaração do Problema

Modelos de Linguagem de Grande Escala (LLMs) dependem de cache de Chave-Valor (KV) para acelerar a inferência, e sistemas de serviço modernos frequentemente compartilham caches KV entre diferentes usuários para reduzir computação redundante e uso de memória. No entanto, o compartilhamento irrestrito entre usuários introduz vulnerabilidades significativas de canal lateral. Adversários podem sondar o sistema com sequências de tokens específicas; se o sistema reutilizar entradas KV em cache (detectado via latência reduzida ou prioridade de agendamento), o adversário pode inferir a presença desses tokens no prompt de uma vítima, potencialmente reconstruindo entradas sensíveis.

As defesas atuais geralmente desabilitam completamente o compartilhamento entre usuários para prevenir vazamento. Essa abordagem "tudo ou nada" é excessivamente grosseira. Na prática, os prompts dos usuários contêm conteúdo substancialmente irrelevante para a privacidade (por exemplo, instruções do sistema, modelos públicos ou trechos recuperados em pipelines RAG), onde tokens sensíveis (como PII) frequentemente constituem uma fração minúscula da entrada total (por exemplo, ~2,3% da entrada do usuário). Desabilitar todo o compartilhamento sacrifica ganhos significativos de eficiência. Além disso, mecanismos de compartilhamento de granularidade fina existentes (por exemplo, CacheBlend, CacheCraft) operam em níveis de blocos fixos (por exemplo, 512 tokens). Se um único token sensível cair dentro de um bloco, todo o bloco deve ser descartado, levando a uma perda substancial de conteúdo reutilizável.

Metodologia: CachePrune

Os autores propõem o CachePrune, um mecanismo de compartilhamento de cache KV consciente de privacidade que habilita a reutilização de granularidade fina, ao nível de token de entradas KV não sensíveis. O sistema é projetado para romper o trade-off entre privacidade e eficiência, compartilhando seletivamente apenas segmentos irrelevantes para a privacidade.

Arquitetura do Sistema

O CachePrune integra cinco componentes principais sobre frameworks existentes como o vLLM:

1. Detector de Sensibilidade: Uma interface plugável (suportando regras definidas pelo usuário, expressões regulares ou classificadores como Presidio) que identifica tokens sensíveis em um prompt e gera uma máscara binária de sensibilidade.
2. Anotador KV: Pós-inferência, este módulo analisa a matriz de pontuação de atenção para derivar segmentos reutilizáveis a partir dos tokens não sensíveis. Ele identifica segmentos "auto-contextualizados" onde a atenção intra excede a atenção inter.
3. Recuperador KV: Antes de gerar uma resposta, este módulo pesquisa o Pool KV por segmentos que correspondem aos tokens não sensíveis da solicitação entrante usando um algoritmo baseado em hash rolante.
4. Motor LLM: Completa a inferência computando entradas KV ausentes e recalcando tokens específicos dentro de segmentos reutilizados para manter a qualidade da geração.
5. Pool KV: Armazena e indexa segmentos KV reutilizáveis, gerenciando seu ciclo de vida e evicção.

Soluções Algorítmicas Chave

O sistema aborda dois desafios primários:

1. Derivação Eficiente de Segmentos KV Reutilizáveis (Desafio 1)

• Problema: Determinar a reutilizabilidade ao nível de token requer avaliar dependências de atenção para substrings arbitrários. Uma abordagem ingênua que verifica todos os substrings contra a matriz de atenção resulta em complexidade $O(n^4)$, o que é proibitivo.
• Solução: O CachePrune emprega um algoritmo de tabela de área somada (imagem integral) na matriz de pontuação de atenção. Isso permite que o sistema compute somas de atenção intra e inter para qualquer substring candidata em tempo $O(1)$ após uma etapa de pré-processamento $O(n^2)$. Isso reduz a complexidade geral de encontrar segmentos reutilizáveis ótimos para $O(n^2)$.
• Estratégia de Recálculo: Dentro de um segmento reutilizável, tokens com alta atenção inter (dependência de contexto externo) são marcados para recálculo para preservar a qualidade da saída.

2. Recuperação Eficiente de Segmentos de Comprimento Variável (Desafio 2)

• Problema: Diferente de blocos de tamanho fixo, o compartilhamento ao nível de token produz segmentos de comprimento variável. Buscas diretas por hash falham porque um deslocamento de um único token quebra o alinhamento, tornando a recuperação um problema de contenção de substring com complexidade $O(n \times m)$ para busca ingênua.
• Solução: O sistema usa um algoritmo de recuperação baseado em hash rolante.
  • Filtragem de Prefixo: Pré-computa hashes para os primeiros 128 tokens dos segmentos em cache. Solicitações entrantes são escaneadas com uma janela deslizante para encontrar correspondências potenciais em tempo $O(n)$.
  • Verificação Completa: Candidatos passam por uma verificação rápida de hash de prefixo seguida por uma verificação de hash criptográfico (SHA-256) para garantir correção sem comparação token a token.

Contribuições Chave

1. Primeiro Sistema Prático de Compartilhamento de Granularidade Fina: O CachePrune é o primeiro sistema a habilitar o compartilhamento seletivo de cache KV ao nível de token, rompendo efetivamente o trade-off privacidade-eficiência ao reutilizar entradas não sensíveis enquanto bloqueia as sensíveis.
2. Inovações Algorítmicas: O artigo introduz um algoritmo adaptativo usando tabelas de área somada para derivação eficiente de segmentos e um mecanismo de hash rolante para recuperação de comprimento variável, superando as limitações de abordagens de blocos fixos.
3. Avaliação Abrangente: Os autores implementam o CachePrune no vLLM e o avaliam em três conjuntos de dados (QASPER, NarrativeQA, QMSum) e múltiplos modelos (Mistral-7B, Qwen2.5).

Resultados

A avaliação demonstra que o CachePrune alcança ganhos significativos de eficiência sem comprometer a privacidade ou a qualidade de geração:

• Privacidade:
  • Vazamento Direto: Tokens marcados como sensíveis não podem ser recuperados via canais laterais baseados em reutilização (0% de taxa de recuperação exata).
  • Vazamento Contextual: A inferência de conteúdo sensível a partir de tokens não sensíveis permanece limitada (2,2% de recuperação exata e 6,4% de recuperação semântica sob ataques SOTA).
  • Detecção Imperfeita: O sistema é robusto a erros de detecção; falsos negativos aumentam o vazamento direto, enquanto falsos positivos reduzem conservadoramente o vazamento contextual.
• Eficiência:
  • Redução de TTFT: O CachePrune reduz o Tempo até o Primeiro Token (TTFT) em até 4,5x comparado a baselines sem compartilhamento.
  • Taxas de Acerto: Alcança até 94,57% de reutilização de cache KV.
  • Vantagem de Granularidade Fina: Mesmo sem restrições de privacidade, o compartilhamento ao nível de token do CachePrune melhora as taxas de acerto de cache em 44% comparado a métodos de blocos fixos state-of-the-art (CacheCraft, CacheBlend, EPIC).
• Qualidade: A qualidade de geração (medida por F1-score e ROUGE-L) permanece comparável ao recálculo completo, com desvio negligenciável.

Significado e Alegações

O artigo alega que o CachePrune fornece uma base prática para serviço seguro de LLMs em ambientes multi-tenant. Ao ir além do particionamento em blocos de tamanho fixo, ele maximiza o potencial de reutilização de conteúdo irrelevante para a privacidade (como prompts do sistema e dados públicos) enquanto isola estritamente entradas de usuário sensíveis. Os autores enfatizam que sua abordagem não requer novos mecanismos de detecção de privacidade, mas sim integra-se aos existentes para fornecer uma interface unificada para inferência segura e de alto desempenho. O trabalho destaca que o gerenciamento de KV de granularidade fina não é apenas viável, mas essencial para equilibrar as demandas concorrentes de privacidade e eficiência na infraestrutura moderna de LLMs.