Resumo Técnico: FibQuant: Quantização Vetorial Universal para Compressão de KV-Cache de Acesso Aleatório

1. Declaração do Problema

A inferência de longo contexto em transformadores autoregressivos está cada vez mais limitada pela largura de banda e capacidade de memória, principalmente devido ao cache de Chave-Valor (KV). O tamanho do cache escala linearmente com o comprimento do contexto, tamanho do lote, número de camadas e número de cabeças, e deve ser acessado a cada etapa de decodificação.

Os métodos de compressão existentes enfrentam uma restrição crítica de sistemas: acesso aleatório. Um codec de cache implantável deve armazenar representações em endereços fixos para que a chave ou o valor de qualquer token possa ser decodificado independentemente por meio de aritmética de endereços simples. Essa restrição elimina a codificação de comprimento variável e representações dependentes do contexto, forçando o uso de quantizadores de taxa fixa.

Os codecs de acesso aleatório mais avançados atuais, como o TURBOQUANT, empregam uma abordagem de "normalizar–rotacionar–quantizar":

1. Armazenar a norma do vetor.
2. Aplicar uma rotação ortogonal aleatória compartilhada (Haar).
3. Quantizar cada coordenada rotacionada independentemente usando uma tabela escalar de Lloyd–Max.

Embora essa interface seja universal e de acesso aleatório, o artigo argumenta que ela é geometricamente subótima. Uma vez que um vetor é normalizado e rotacionado por Haar, um bloco de $k$ coordenadas consecutivas não forma um produto independente de marginais escalares. Em vez disso, forma uma fonte esférica-Beta na bola unitária. Codecs escalares tratam as coordenadas como independentes, descartando a estrutura geométrica (correlações radiais e angulares) inerente ao bloco rotacionado. Além disso, métodos escalares lutam para operar efetivamente abaixo de um bit por coordenada, criando uma "lacuna subum-bit" onde os codecs universais e livres de calibração atuais falham.

2. Metodologia: FibQuant

O FibQuant propõe um quantizador vetorial universal de taxa fixa que mantém a mesma interface "normalizar–rotacionar" dos métodos escalares, mas substitui as tabelas de coordenadas escalares por um livro de códigos vetorial radial–angular compartilhado.

2.1 A Fonte Canônica

Os autores provam que a interface de normalização seguida de rotação Haar induz uma distribuição de fonte universal, independentemente da distribuição original dos dados KV.

• Normalização: Remove a escala.
• Rotação Haar: Remove a orientação.
• Resultado: O vetor unitário rotacionado é uniforme de Haar na esfera $S^{d-1}$. Consequentemente, qualquer bloco de $k$ coordenadas consecutivas segue uma densidade esférica-Beta específica $f_{d,k}$ na bola unitária $B^k$.
• Implicação: Um único livro de códigos offline pode servir a todas as camadas, cabeças, prompts e modelos, pois a distribuição da fonte é invariante ao input específico.

2.2 Construção do Livro de Códigos

O livro de códigos FibQuant é construído para corresponder à fonte esférica-Beta, combinando três componentes:

1. Raios ($r_n$): Correspondem à densidade radial da fonte esférica-Beta usando regras de compansão Bennett–Gersho. Para $k=2$, isso produz uma solução de forma fechada envolvendo raios de quantil Beta.
2. Direções ($u_n$): Aproximadas usando conjuntos de pontos esféricos quase uniformes para garantir um empacotamento angular uniforme:
   • $k=2$: Espiral de Fibonacci planar (Quantizador Dourado).
   • $k=3$: Esfera de Fibonacci.
   • $k \ge 4$: Sequências de baixa discrepância de Roberts–Kronecker.
3. Refinamento: Um algoritmo Lloyd–Max com múltiplos reinícios refina a inicialização determinística para minimizar o Erro Quadrático Médio (MSE) para o tamanho específico do livro de códigos finito $N$.

2.3 Codificação e Decodificação

• Codificador: Calcula a norma $\nu = \|x\|_2$, rotaciona o vetor unitário $\Pi x / \nu$, divide-o em $d/k$ blocos de tamanho $k$ e realiza uma busca do código mais próximo contra o livro de códigos compartilhado.
• Decodificador: Recupera o código, reconstrói o bloco, concatena os blocos, aplica a rotação inversa e escala pela norma.
• Taxa: A taxa de bits é $b = (\log_2 N) / k$ bits por coordenada. Variando $N$ e $k$, o FibQuant alcança um eixo de taxa denso, permitindo pontos de operação fracionários e subum-bit sem endereçamento de comprimento variável.

3. Principais Contribuições

3.1 Identificação da Fonte Canônica

O artigo prova (Teorema 1) que a interface de norma seguida de rotação Haar mapeia qualquer distribuição de entrada não nula para a mesma marginal esférica-Beta $f_{d,k}$. Isso estabelece que um livro de códigos offline compartilhado é o objeto universal teoricamente correto para a compressão de KV-cache.

3.2 Vantagem Vetorial sobre Especialização Escalar

Os autores provam (Teorema 2) que o código vetorial ótimo de $k$ vetores domina estritamente a especialização de produto escalar (onde $k=1$) em taxas correspondentes. O ganho de alta taxa é fatorado em dois componentes:

1. Fator de Moldagem de Célula ($\gamma_{cell}$): Células de quantização vetorial (por exemplo, hexagonais em 2D) são mais eficientes do que células escalares retangulares.
2. Fator de Correspondência de Densidade ($\gamma_{dens}$): Correspondência à densidade conjunta esférica-Beta é superior à correspondência apenas das marginais escalares.

3.3 Eixo de Taxa Denso

Diferentemente das tabelas escalares de Lloyd–Max, que são limitadas a taxas de bits inteiras, o FibQuant realiza um conjunto denso de taxas $b \in (0, \infty)$. Isso permite operação no regime subum-bit (por exemplo, $b \approx 0,19$), um regime onde os codecs universais de acesso aleatório atuais deixam de funcionar.

4. Resultados Experimentais

4.1 Desempenho de Codificação de Fonte

Na fonte esférica-Beta canônica, o FibQuant demonstra domínio estrito sobre o TURBOQUANT escalar em todas as taxas inteiras. Ele também preenche as lacunas entre as taxas inteiras, fornecendo pontos de operação que métodos escalares não podem alcançar.

4.2 Compressão de KV-Cache (GPT-2 Small)

Avaliado em caches KV do GPT-2 pequeno com similaridade de cosseno de saída de atenção como métrica:

• O FibQuant traça uma fronteira de memória–fidelidade de 5× compressão (em 0,99 de similaridade) a 34,1× compressão (em 0,946 de similaridade).
• Em altas taxas de compressão (>10×), o FibQuant é o único método universal e livre de calibração que mantém a fidelidade, superando métodos de projeção de baixo rank que exigem calibração por camada.
• O artigo observa que códigos de vetor completo ($k=d$) performam melhor em compressão extrema do que códigos de meio vetor ($k=d/2$), porque gastam todos os bits no empacotamento angular, o que correlaciona diretamente com produtos internos de atenção.

4.3 Desempenho de Modelo de Linguagem End-to-End (TinyLlama-1.1B)

Avaliado em perplexidade do WikiText-103 e precisão do HellaSwag:

• Em $b=4$ (4× compressão): O FibQuant está dentro de 0,10 de perplexidade da linha de base fp16 e supera o TURBOQUANT escalar.
• Em $b=2$ (8× compressão): O FibQuant alcança 15,88 de perplexidade, superando significativamente o TURBOQUANT escalar (56,72) e a quantização INT por token (que colapsa para 4450,5).
• Taxas Fracionárias: O FibQuant fornece pontos de operação intermediários (por exemplo, $b=2,5; 3,5$) indisponíveis para codecs escalares, permitindo que o orçamento de cache seja escolhido primeiro e o codec ajustado para caber.

5. Significado e Alegações

O artigo alega que a restrição de acesso aleatório, frequentemente vista como uma limitação de engenharia, tem uma consequência matemática profunda: ela força os dados para uma geometria esférica-Beta específica. Ao reconhecer essa fonte canônica, o FibQuant recupera os "ganhos de moldagem e correspondência de densidade" que a quantização escalar deixa na mesa.

O significado reside em:

1. Universalidade: Um único livro de códigos funciona em todas as configurações de modelo sem calibração.
2. Operação Subum-Bit: Permite compressão de alta fidelidade em regimes onde métodos escalares falham, expandindo efetivamente o orçamento de memória utilizável para inferência de longo contexto.
3. Compatibilidade de Sistema: Mantém a interface de endereço fixo e acesso aleatório necessária para fundir a descompressão com kernels de atenção, tornando-o imediatamente implantável em frameworks de serviço existentes.

Os autores concluem que o acesso aleatório não impede uma boa codificação de fonte; ao contrário, ele dita exatamente qual fonte deve ser codificada.