Résumé Technique : FibQuant, Quantification Vectorielle Universelle pour la Compression de Cache KV à Accès Aléatoire

1. Énoncé du Problème

L'inférence en contexte long dans les transformateurs autorégressifs est de plus en plus contrainte par la bande passante et la capacité mémoire, principalement en raison du cache Key-Value (KV). La taille du cache évolue linéairement avec la longueur du contexte, la taille du lot, le nombre de couches et le nombre de têtes, et il doit être accessible à chaque étape de décodage.

Les méthodes de compression existantes font face à une contrainte système critique : l'accès aléatoire. Un codec de cache déployable doit stocker des représentations à des adresses fixes afin que la clé ou la valeur de n'importe quel jeton puisse être décodée indépendamment via un simple calcul d'adresse. Cette contrainte exclut le codage de longueur variable et les représentations dépendantes du contexte, imposant l'utilisation de quantificateurs à taux fixe.

Les codecs à accès aléatoire les plus avancés actuels, tels que TURBOQUANT, emploient une approche « normaliser–pivoter–quantifier » :

1. Stocker la norme du vecteur.
2. Appliquer une rotation orthogonale aléatoire partagée (Haar).
3. Quantifier chaque coordonnée pivotée indépendamment à l'aide d'une table scalaire de Lloyd–Max.

Bien que cette interface soit universelle et à accès aléatoire, l'article soutient qu'elle est géométriquement sous-optimale. Une fois un vecteur normalisé et pivoté selon Haar, un bloc de $k$ coordonnées consécutives ne forme pas un produit indépendant de marginales scalaires. Il forme plutôt une source sphérique-Beta sur la boule unité. Les codecs scalaires traitent les coordonnées comme indépendantes, jetant la structure géométrique (corrélations radiales et angulaires) inhérente au bloc pivoté. De plus, les méthodes scalaires peinent à fonctionner efficacement en dessous d'un bit par coordonnée, créant un « écart sous-un-bit » où les codecs universels actuels, sans calibration, échouent.

2. Méthodologie : FibQuant

FibQuant propose un quantificateur vectoriel universel à taux fixe qui maintient la même interface « normaliser–pivoter » que les méthodes scalaires, mais remplace les tables de coordonnées scalaires par un codebook vectoriel radial–angulaire partagé.

2.1 La Source Canonique

Les auteurs démontrent que l'interface normaliser–pivoter induit une distribution de source universelle, indépendamment de la distribution des données KV d'origine.

• Normalisation : Supprime l'échelle.
• Rotation Haar : Supprime l'orientation.
• Résultat : Le vecteur unitaire pivoté est uniformément réparti selon Haar sur la sphère $S^{d-1}$. Par conséquent, tout bloc de $k$ coordonnées consécutives suit une densité sphérique-Beta spécifique $f_{d,k}$ sur la boule unité $B^k$.
• Implication : Un seul codebook hors ligne peut servir toutes les couches, têtes, invites et modèles, car la distribution de source est invariante par rapport à l'entrée spécifique.

2.2 Construction du Codebook

Le codebook FibQuant est construit pour correspondre à la source sphérique-Beta, combinant trois composantes :

1. Rayons ($r_n$) : Correspondent à la densité radiale de la source sphérique-Beta en utilisant les règles de compansion de Bennett–Gersho. Pour $k=2$, cela donne une solution sous forme fermée impliquant des rayons de quantile Beta.
2. Directions ($u_n$) : Approchées à l'aide d'ensembles de points sphériques quasi-uniformes pour assurer un emballage angulaire uniforme :
   • $k=2$ : Spirale de Fibonacci plane (Quantificateur d'Or).
   • $k=3$ : Sphère de Fibonacci.
   • $k \ge 4$ : Séquences à faible discrépance de Roberts–Kronecker.
3. Raffinement : Un algorithme Lloyd–Max multi-redémarrage affine l'initialisation déterministe pour minimiser l'erreur quadratique moyenne (MSE) pour la taille de codebook finie spécifique $N$.

2.3 Encodage et Décodage

• Encodeur : Calcule la norme $\nu = \|x\|_2$, pivote le vecteur unitaire $\Pi x / \nu$, le divise en $d/k$ blocs de taille $k$, et effectue une recherche du mot de code le plus proche dans le codebook partagé.
• Décodeur : Récupère le mot de code, reconstruit le bloc, concatène les blocs, applique la rotation inverse et met à l'échelle par la norme.
• Débit : Le débit binaire est $b = (\log_2 N) / k$ bits par coordonnée. En variant $N$ et $k$, FibQuant réalise un axe de débit dense, permettant des points de fonctionnement à bits fractionnaires et inférieurs à un bit sans adressage de longueur variable.

3. Contributions Clés

3.1 Identification de la Source Canonique

L'article démontre (Théorème 1) que l'interface norme puis rotation Haar mappe n'importe quelle distribution d'entrée non nulle vers la même marginales sphérique-Beta $f_{d,k}$. Cela établit qu'un codebook hors ligne partagé est l'objet universel théoriquement correct pour la compression de cache KV.

3.2 Avantage Vectoriel par rapport à la Spécialisation Scalaire

Les auteurs démontrent (Théorème 2) que le code vectoriel optimal de taille $k$ domine strictement la spécialisation produit scalaire (où $k=1$) à débits équivalents. Le gain à haut débit se décompose en deux composantes :

1. Facteur de Façonnage de Cellule ($\gamma_{cell}$) : Les cellules de quantification vectorielle (par exemple, hexagonales en 2D) sont plus efficaces que les cellules scalaires rectangulaires.
2. Facteur d'Adéquation de Densité ($\gamma_{dens}$) : L'adéquation à la densité conjointe sphérique-Beta est supérieure à l'adéquation aux seules marginales scalaires.

3.3 Axe de Débit Dense

Contrairement aux tables de Lloyd–Max scalaires limitées à des débits entiers, FibQuant réalise un ensemble dense de débits $b \in (0, \infty)$. Cela permet une opération dans le régime sous-un-bit (par exemple, $b \approx 0,19$), un régime où les codecs universels à accès aléatoire actuels cessent de fonctionner.

4. Résultats Expérimentaux

4.1 Performance de Codage de Source

Sur la source canonique sphérique-Beta, FibQuant démontre une domination stricte sur le TURBOQUANT scalaire à tous les débits entiers. Il comble également les écarts entre les débits entiers, fournissant des points de fonctionnement inaccessibles aux méthodes scalaires.

4.2 Compression de Cache KV (GPT-2 Small)

Évalué sur les caches KV de GPT-2 small avec la similarité cosinus de la sortie d'attention comme métrique :

• FibQuant trace une frontière mémoire–fidélité allant d'une compression 5× (à une similarité de 0,99) à une compression 34,1× (à une similarité de 0,946).
• À des ratios de compression élevés (>10×), FibQuant est la seule méthode universelle, sans calibration, qui maintient la fidélité, surpassant les méthodes de projection de rang faible qui nécessitent une calibration par couche.
• L'article note que les codes vectoriels complets ($k=d$) fonctionnent mieux à une compression extrême que les codes demi-vectoriels ($k=d/2$) car ils consacrent tous les bits à l'emballage angulaire, ce qui corrèle directement avec les produits scalaires d'attention.

4.3 Performance du Modèle de Langage de Bout en Bout (TinyLlama-1.1B)

Évalué sur la perplexité WikiText-103 et la précision HellaSwag :

• À $b=4$ (compression 4×) : FibQuant est à moins de 0,10 de perplexité de la base fp16 et surpasse le TURBOQUANT scalaire.
• À $b=2$ (compression 8×) : FibQuant atteint une perplexité de 15,88, surpassant significativement le TURBOQUANT scalaire (56,72) et la quantification INT par jeton (qui s'effondre à 4450,5).
• Débits Fractionnaires : FibQuant fournit des points de fonctionnement intermédiaires (par exemple, $b=2,5 ; 3,5$) indisponibles pour les codecs scalaires, permettant de choisir d'abord le budget mémoire puis d'ajuster le codec pour s'y adapter.

5. Signification et Revendications

L'article revendique que la contrainte d'accès aléatoire, souvent considérée comme une limitation technique, a une conséquence mathématique profonde : elle force les données dans une géométrie spécifique sphérique-Beta. En reconnaissant cette source canonique, FibQuant récupère les « gains de façonnage et d'adéquation de densité » que la quantification scalaire laisse de côté.

La signification réside dans :

1. Universalité : Un seul codebook fonctionne sur toutes les configurations de modèles sans calibration.
2. Fonctionnement Sous-Un-Bit : Il permet une compression haute fidélité dans des régimes où les méthodes scalaires échouent, élargissant efficacement le budget mémoire utilisable pour l'inférence en contexte long.
3. Compatibilité Système : Il conserve l'interface à adresse fixe et à accès aléatoire requise pour fusionner la décompression avec les noyaux d'attention, le rendant immédiatement déployable dans les frameworks de service existants.

Les auteurs concluent que l'accès aléatoire n'exclut pas un bon codage de source ; au contraire, il dicte exactement quelle source doit être codée.