Resumo Técnico: Arquivos de Cache KV Fratais

Declaração do Problema

Servir modelos de linguagem transformer sobre contextos longos mudou de um desafio limitado por computação para um desafio limitado por memória. O cache de Chave-Valor (KV), necessário para a atenção autorregressiva, cresce linearmente com o comprimento do contexto, muitas vezes superando o peso dos modelos e restringindo os tamanos de lote (batch sizes). Enquanto as soluções existentes focam em compressão com perda (lossy compression) (quantização, expulsão, descarregamento), este artigo aborda uma questão subsequente, frequentemente implícita: Uma vez que um estado KV foi reduzido a um fluxo de símbolos via quantização vetorial, como esse fluxo deve ser armazenado?

Os autores argumentam que a camada de armazenamento não deve ser um bloco inerte, mas um componente ativo capaz de suportar os padrões de acesso específicos de um cache crescente: anexo amortizado O(1) (conforme novos tokens chegam) e acesso aleatório O(1) (para recuperar posições passadas), oferecendo potencialmente funcionalidade adicional, como a recuperação in-place.

Metodologia

1. O Primitivo de Armazenamento: Códigos de Mapa Iterado Contrativos

O artigo propõe o uso de um código de mapa iterado contrativo sem perdas (especificamente, uma generalização da Representação do Jogo do Caos e Mapas de Sequência Universal) como a camada de serialização para índices KV quantizados.

• Mecanismo: Uma sequência de símbolos sobre um alfabeto de tamanho $N$ é mapeada para uma trajetória de pontos em um plano 2D. Um $N$-gono regular é fixado com um vértice por símbolo. Cada símbolo $c_k$ mapeia o ponto atual $p_{k-1}$ para um novo ponto $p_k$ via a contração $p_k = V(c_k) + r(p_{k-1} - V(c_k))$, onde $r$ é uma razão de contração.
• Propriedades:
  • Sem perdas (Lossless): O mapa é invertível, desde que a razão de contração $r$ seja pequena o suficiente para garantir "células" disjuntas para cada símbolo.
  • Eficiência: A codificação é de tempo linear. A decodificação permite o acesso aleatório a qualquer posição reconstruindo apenas o intervalo necessário a partir do ponto âncora armazenado mais próximo.
  • Autossimilaridade: O conjunto de pontos alcançáveis forma um atrator fractal (ex: um triângulo de Sierpinski para $N=3$).
• Implementação: Para mitigar a amplificação do erro de ponto flutuante durante a inversão, o codec armazena um ponto por intervalo de comprimento fixo e reconstrói os intervalos via busca reversa ancorada.

2. Estratégia de Quantização

Os autores conduzem um estudo controlado no GPT-2 (124M) com contextos de 1024 tokens para determinar o esquema de quantização ideal que alimenta este arquivo:

• Janela Exata: Para manter o desempenho, uma pequena janela exata é mantida (4 tokens de "sumidouro de atenção" + 32 recentes). O restante do contexto é arquivado.
• Variantes de Quantização:
  • Agrupado (Pooled) vs. Por Cabeça (Per-Head): Comparando um único código compartilhado entre todas as cabeças de atenção versus códigos individuais por cabeça.
  • Quantização Vetorial Residual (RVQ): Armazenando vetores como uma soma de $s$ índices de livros de códigos (codebooks).
  • Assimetria Chave/Valor: Investigando o impacto diferencial da quantização de Chaves (K) versus Valores (V).

3. Recuperação In-Place

O artigo explora uma propriedade geométrica do código de mapa iterado: pontos que compartilham um sufixo comum de comprimento $s$ são espacialmente próximos (distância $\approx 2r^s$). Isso permite que consultas de substring aproximadas sejam executadas diretamente nos vetores 2D armazenados via busca de vizinho mais próximo, sem descomprimir o texto circundante.

Principais Resultados

1. Desempenho do Codec

O codec fractal atua como um primitivo de armazenamento de alto desempenho independente do modelo:

• Codificação: 0,68 µs/caractere (tempo linear).
• Acesso Aleatório: 311 µs/busca para um documento de 1M de caracteres.
• Anexo (Append): 175 µs/token (amortizado).

2. Achados de Quantização (GPT-2, 1024 tokens)

• Superioridade por Cabeça: Livros de códigos por cabeça superam significativamente os livros de códigos agrupados em igual orçamento de bits. Um RVQ por cabeça (profundidade 2) reduz o aumento da perplexidade para +15,0% em comparação com +29,2% para um RVQ agrupado.
• Assimetria Chave/Valor: Quantizar as Chaves é aproximadamente 4× mais prejudicial à perplexidade do que quantizar os Valores.
  • Apenas Valores (Chaves exatas): +4,0% de perplexidade.
  • Apenas Chaves (Valores exatos): +14,5% de perplexidade.
  • Isso confirma que as Chaves determinam o roteamento da atenção (alta sensibilidade), enquanto os Valores são suavizados (atenuação de erro).
• Esquema Híbrido Ótimo: Alocar mais bits para as Chaves (4 estágios de RVQ) e menos para os Valores (2 estágios) produz o melhor equilíbrio:
  • Compressão: Redução de 36× em relação a um cache fp16.
  • Custo de Perplexidade: +11,2% (especificamente +16,6% na "segunda metade" do contexto, onde o arquivo domina).
  • Armazenamento: 1025 bytes/token.

3. Capacidades de Recuperação

• Recall Exato: O limiar da distância entre pontos armazenados recupera todas as posições com um sufixo correspondente de comprimento $\ell$ com 1,00 de recall.
• Precisão: Controlada pela precisão numérica. Índices de precisão dupla alcançam 0,89–1,00 de precisão; precisão simples serve como um filtro grosseiro.
• Eficiência: Busca de vizinho mais próximo por força bruta sobre 100K posições em espaço 2D leva ~0,9 ms/consulta.
• Decodificação: O contexto correspondente é decodificado para trás a partir do vetor correspondente sem acessar o texto externo.

Significância e Alegações

O artigo afirma três contribuições primárias, distinguindo-se de trabalhos concorrentes (ex: FibQuant, RetroInfer) que focam na geometria do livro de códigos ou motores de armazenamento de vetores:

1. Um Formato de Arquivo Unificado: Ele enquadra o código de mapa iterado de contração como um arquivo KV prático que é simultaneamente um armazenamento sem perdas, um decodificador de acesso aleatório e um índice de busca in-place. Essa unificação de armazenamento e recuperação em uma única representação é apresentada como a contribuição inovadora.
2. Insights de Quantização: Ele quantifica a assimetria Chave/Valor como um orçamento específico de perplexidade, demonstrando que um esquema híbrido assimétrico de bits (4x bits para Chaves, 2x para Valores) é o ponto operacional ideal para compressão de contexto longo.
3. Memória Pesquisável: Demonstra que o arquivo suporta correspondência de sufixo diretamente na representação comprimida, permitindo a decodificação aumentada por recuperação onde o modelo pode localizar contextos passados relevantes sem materializar o cache completo.

Limitações Reconhecidas pelos Autores

• Escala: Os experimentos são limitados ao GPT-2 (124M) e um contexto único de 1024 tokens. Resultados em modelos maiores não foram testados (embora provavelmente sejam mais tolerantes à quantização).
• Treinamento de Livro de Códigos: Os livros de códigos são treinados por corpus, não amortizados através de dados.
• Escopo de Recuperação: A recuperação é estritamente de correspondência de estrutura de sequência (sufixos), não de recuperação semântica sobre embeddings.
• Razão de Compressão: A razão de compressão bruta do codec fractal é comparável a empacotadores de bytes padrão; sua vantagem reside no padrão de acesso (acesso aleatório/busca) e não na redução de tamanho bruto.
• Benchmarking: O artigo não realiza benchmarking contra os designs específicos de livros de códigos de trabalhos concorrentes, reconhecendo que combinar seus quantizadores com este formato de armazenamento é um trabalho futuro.