Sequential KV Cache Compression via Probabilistic Language Tries: Beyond the Per-Vector Shannon Limit

Título: Compressão Sequencial de KV Cache via Árvores de Linguagem Probabilísticas: Além do Limite de Shannon por Vetor

Autor: Gregory Magarshak
Data: 10 de abril de 2026 (arXiv:2604.15356v1)

1. O Problema: O Gargalo da Memória KV Cache

Em modelos de linguagem baseados em Transformers, a inferência autogressiva requer o armazenamento de um KV Cache (Cache de Chave e Valor) para cada token processado. Este cache atua como a "memória de trabalho" do modelo.

• Escala do Problema: Para um modelo de 70B parâmetros com contexto de 128k tokens, o cache pode ocupar cerca de 80 GB em precisão FP16, superando o tamanho dos pesos do próprio modelo.
• Estado da Arte Atual: Métodos recentes de quantização, culminando no TurboQuant [13], atingiram o limite de Shannon para a compressão por vetor. O TurboQuant comprime cada componente de vetor de chave/valor para cerca de 3 bits, provando que não é possível fazer significativamente melhor tratando os vetores como amostras independentes.
• A Lacuna: O artigo argumenta que o limite do TurboQuant resolve um problema "mais fraco". O KV Cache não é uma coleção de vetores aleatórios e independentes; é uma sequência gerada por um modelo que aprendeu a estrutura de uma linguagem formal. Ignorar a dependência temporal e a estrutura sequencial desperdiça redundância previsível.

2. Metodologia: Compressão Sequencial de Duas Camadas

O autor propõe uma arquitetura de duas camadas que explora a estrutura sequencial e semântica do cache, superando o limite por vetor.

Camada 1: Deduplicação de Prefixos Probabilísticos (Layer 1)

• Conceito: Em vez de apenas compartilhar prefixos exatos (como fazem vLLM ou SGLang), o método utiliza Árvores de Linguagem Probabilísticas (PLTs) para identificar prefixos semanticamente equivalentes entre diferentes sessões.
• Métrica: Utiliza a métrica de árvore $d_T(s, s') = -\log_2 P_M(s \land s')$, onde $s \land s'$ é o prefixo comum mais longo. Sessões com distância pequena na métrica $d_T$ compartilham uma estrutura de KV muito similar.
• Mecanismo: Agrupa sessões em "clusters" semânticos. Armazena o cache completo apenas para o "centroide" (prefixo mais provável do cluster) e armazena apenas as deltas (diferenças) para as outras sessões a partir desse centroide.
• Vantagem: Elimina redundância entre sessões que começam com frases semanticamente similares, mas lexicalmente diferentes (ex: "Você é um assistente útil" vs "Você é uma IA útil").

Camada 2: Codificação Delta Preditiva (Layer 2)

• Conceito: Dentro de uma única sessão, o modelo já possui uma distribuição de probabilidade sobre o próximo token antes de gerar o vetor KV correspondente.
• Mecanismo:
  1. Calcula o vetor KV previsto ($\hat{KV}_i$) como a expectativa do vetor KV sobre a distribuição de probabilidade do próximo token.
  2. Em vez de armazenar o vetor KV real ($KV_i$), armazena apenas o resíduo ($R_i = KV_i - \hat{KV}_i$).
• Eficiência: Em textos coerentes, o modelo prevê o próximo token com alta precisão (baixa perplexidade). Consequentemente, o resíduo é pequeno e possui baixa entropia.
• Quantização Adaptativa: A quantização do resíduo é adaptada à "surpresa" (surprisal) do token. Tokens previsíveis exigem poucos bits; tokens surpreendentes exigem mais.

Composição com Quantização por Vetor

As duas camadas são ortogonais e podem ser aplicadas antes de métodos existentes como o TurboQuant. O fluxo final é:

1. Deduplicação de Prefixo (reduz o número de vetores únicos).
2. Codificação Delta Preditiva (reduz a magnitude dos vetores restantes).
3. Quantização por Vetor (ex: TurboQuant) aplicada aos resíduos já comprimidos.

3. Contribuições Principais

1. Limite de Entropia Sequencial (Teorema 1):

   • Prova formal de que a entropia condicional do vetor KV no passo $i$, dado o histórico, é limitada pela surpresa por token do modelo:
     $$H(KV_i | KV_{<i}) \leq H(token_i | token_{<i})$$
   • Isso significa que a informação necessária para codificar o KV é limitada pela incerteza do modelo sobre o próximo token, não pelo tamanho do vetor em si.

2. Análise de Taxa-Distorção:

   • Demonstra que, para textos coerentes (perplexidade 10-20), a entropia condicional é de apenas 3.3 a 4.3 bits por posição de token (para todo o estado KV de todas as camadas e cabeças).
   • Em contraste, o TurboQuant armazena ~3 bits por componente do vetor. Com 128 componentes por cabeça, 64 cabeças e 80 camadas, o custo por token no TurboQuant é de ~3.9 milhões de bits.

3. Comportamento Assintótico:

   • Diferente dos métodos por vetor (onde o custo cresce linearmente e fixo com o contexto), a compressão sequencial melhora conforme o contexto aumenta. Quanto mais tokens o modelo vê, mais previsível se torna o próximo, reduzindo o custo marginal por token.

4. Resultados Teóricos e Proporções de Compressão

O artigo apresenta estimativas teóricas de compressão para um modelo de 70B parâmetros:

• Comparação com FP16 (16 bits/componente):
  • Limite teórico: ~4.9 milhões de vezes melhor.
• Comparação com TurboQuant (3 bits/componente):
  • Limite de Shannon Teórico: ~914.000x de melhoria.
  • Cenário Pessimista Prático (1000x acima do limite de entropia): Ainda ~914x de melhoria sobre o TurboQuant.
  • Cenário Prático Realista (10-20x acima do limite): ~45.000x a 91.000x de melhoria.

Esses números indicam que a "parede de memória" (Memory Wall) pode ser drasticamente reduzida não apenas por hardware, mas explorando a redundância linguística.

5. Significado e Implicações

• Revisão do Limite de Shannon: O trabalho mostra que o limite de Shannon provado pelo TurboQuant aplica-se a um problema de vetores independentes. O limite real para o problema de compressão de cache sequencial é estritamente menor, explorando a correlação temporal.
• Solução para a "Parede de Memória": Sugere que a escalabilidade de contextos longos não depende apenas de memória de hardware mais barata, mas de algoritmos que entendem a estrutura da linguagem. O custo marginal de adicionar um token a um contexto longo pode diminuir, em vez de aumentar.
• Sinergia com Outras Técnicas: A abordagem é compatível com Speculative Decoding (o mesmo cálculo de distribuição top-k usado para prever tokens pode ser usado para prever vetores KV) e métodos de descarte de cache (eviction).
• Paradoxo de Jevons: A redução drástica no custo de inferência pode levar ao aumento do uso total de memória, permitindo aplicações antes inviáveis, como análise de documentos de milhões de tokens em tempo real ou memória persistente de agentes.

6. Desafios e Implementação Prática

O artigo reconhece desafios de engenharia para a implementação:

• Cálculo de Predição: Calcular o vetor KV previsto exige somar sobre o vocabulário inteiro. O autor propõe aproximações eficientes usando apenas os top-k tokens (ex: k=20) ou aproximações lineares da camada de embedding.
• Integração no Loop de Inferência: Requer acesso à distribuição softmax durante a inferência, o que é nativo, mas exige modificações no kernel para calcular e armazenar o resíduo em vez do vetor bruto.
• Índice de Árvore: É necessário um sistema eficiente de indexação baseado em árvores (Trie) para gerenciar os clusters de prefixos probabilísticos e realizar buscas de vizinhos mais próximos.

Conclusão

O artigo demonstra que o TurboQuant não é o teto final da compressão de KV Cache. Ao tratar o cache como uma sequência linguística e não como vetores isolados, e ao utilizar a estrutura probabilística do próprio modelo para prever e deduplicar dados, é possível atingir taxas de compressão ordens de magnitude superiores. A chave está em codificar a redundância da linguagem que o modelo já aprendeu, transformando a previsão de tokens em compressão de memória.