🤖 machine learning

Fractal KV-Cache Archives: Lossless Symbolic Storage with In-Place Retrieval for Long-Context LLM Inference

Cet article introduit les « Fractal KV-Cache Archives », un format de stockage sans perte et en temps linéaire pour les caches KV quantifiés qui permet un accès aléatoire en O(1) et un ajout amorti tout en fonctionnant simultanément comme un index de recherche pour des requêtes de sous-chaînes approximatives, atteignant jusqu'à 54x de compression avec une dégradation minimale de la perplexité.

Auteurs originaux : Vladimir Gusev

Publié 2026-07-09

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Vladimir Gusev

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous lisez un livre très long, et qu'à chaque fois que vous tournez une page, vous devez vous souvenir de tout ce que vous avez lu jusqu'à présent pour comprendre la phrase suivante. Pour une intelligence artificielle informatique (comme celle de cet article), cette « mémoire » est appelée le KV Cache.

À mesure que l'histoire s'allonge, cette mémoire devient énorme. C'est comme essayer de transporter une bibliothèque dans un sac à dos juste pour lire une page supplémentaire. Finalement, le sac devient si lourd (utilisant toute la mémoire de l'ordinateur) que vous ne pouvez plus lire.

Cet article propose une solution ingénieuse en deux parties pour rendre ce sac à dos plus léger et plus facile à utiliser.

Partie 1 : La « Carte Fractale » (L'astuce de stockage)

Habituellement, lorsque les ordinateurs essaient de gagner de l'espace, ils compressent les données en un gros bloc informe. Pour retrouver une phrase spécifique plus tard, ils doivent décompresser tout le bloc, ce qui est lent.

Les auteurs suggèrent une méthode différente : La Carte Fractale.

Imaginez que vous avez une carte magique et géante d'une ville.

La Règle : Chaque fois que vous ajoutez un nouveau mot à votre mémoire, vous faites un petit pas sur cette carte.
La Magie : La carte est conçue de telle sorte que si vous faites un pas pour le mot « Pomme », vous arrivez dans un minuscule quartier spécifique. Si vous faites ensuite un pas pour « Tarte », vous arrivez dans un endroit précis à l'intérieur du quartier « Pomme ».
Le Résultat : Votre mémoire entière d'une histoire n'est pas une liste de mots ; c'est juste un seul point sur cette carte.
- Si vous voulez connaître le dernier mot, vous regardez le point et voyez dans quel minuscule quartier il se trouve.
- Si vous voulez les deux derniers mots, vous regardez le point, déterminez le deuxième quartier en partant de la fin, et ainsi de suite.

Pourquoi est-ce génial ?

C'est sans perte (Lossless) : Vous pouvez reconstruire les mots originaux exacts à partir de ce seul point, parfaitement.
C'est rapide : Vous pouvez accéder instantanément à n'importe quel point de l'histoire (Accès Aléatoire) sans lire toute la carte au préalable.
C'est interrogeable : Parce que la carte est construite sur la géométrie, si vous cherchez une expression comme « Le chat est assis », vous pouvez la trouver simplement en cherchant des points qui sont proches les uns des autres selon un motif spécifique. Vous n'avez pas besoin de lire le texte pour trouver le motif ; la forme du point est le motif.

Partie 2 : Le « Rétrécissement Intelligent » (L'astuce de compression)

Avant de transformer la mémoire en un point sur la carte, l'IA doit rétrécir les données. L'article a testé comment rétrécir les parties « Key » (Clé) et « Value » (Valeur) de la mémoire de l'IA.

Considérez la mémoire de l'IA comme une conversation entre deux personnes :

Les Clés (Keys) : Ce sont comme des « questions » ou des « étiquettes » qui décident de ce à quoi il faut prêter attention.
Les Valeurs (Values) : Ce sont comme les « réponses » ou le contenu réel.

Les auteurs ont découvert un déséquilibre amusant :

Les Clés sont fragiles : Si vous déformez les « questions » (en les compressant trop), l'IA s'embrouille sur ce qu'elle doit regarder. C'est comme donner à quelqu'un une carte floue ; elle pourrait regarder la mauvaise rue.
Les Valeurs sont robustes : Si vous déformez un peu les « réponses », l'IA peut généralement toujours comprendre l'essentiel. C'est comme entendre une voix légèrement étouffée ; on peut toujours saisir le sens.

La Solution : Les auteurs ont créé un « Sac à dos Hybride ». Ils ont emballé les « Questions » (Clés) très soigneusement (en utilisant plus d'espace) et les « Réponses » (Valeurs) plus lâchement (en utilisant moins d'espace). Cela a permis d'économiser énormément d'espace — 36 fois plus petit que l'original — tout en rendant l'IA légèrement moins précise (environ 11 % de moins pour deviner le mot suivant).

La Vue d'Ensemble

L'article combine ces deux idées :

Rétrécir les données en utilisant la méthode du « Rétrécissement Intelligent » (en traitant différemment les questions et les réponses).
Stocker les données rétrécies sur la « Carte Fractale ».

Le Superpouvoir :
Parce que les données sont stockées sur cette Carte Fractale, l'IA peut faire quelque chose d'incroyable : Elle peut chercher dans son propre passé sans « décompresser » les fichiers.

Si l'IA a besoin de trouver une phrase spécifique qu'elle a lue il y a 500 pages, elle n'a pas besoin de charger tout le livre. Elle regarde simplement la carte, trouve le point correspondant, et sait instantanément où se trouve cette phrase. C'est comme avoir une bibliothèque où l'on peut trouver un livre spécifique juste en regardant la couleur de la poussière sur l'étagère, sans jamais sortir le livre de l'étagère.

Résumé des affirmations

Stockage : Ils ont créé un moyen de stocker la mémoire de l'IA qui est parfaitement précis, très rapide d'accès et facile à enrichir.
Compression : Ils ont découvert que compresser les « questions » (Clés) est beaucoup plus difficile que de compresser les « réponses » (Valeurs), et ils ont utilisé cela pour économiser 36 fois plus d'espace.
Recherche : La méthode de stockage elle-même agit comme un moteur de recherche, permettant à l'IA de trouver des motifs dans sa mémoire passée instantanément.
Portée : Ils ont testé cela sur un modèle d'IA spécifique et petit (GPT-2) avec un contexte de 1 000 mots. Ils n'ont pas encore testé cela sur de très grands modèles ou des tâches du monde réel, mais les mathématiques et le code fonctionnent parfaitement sur un ordinateur portable standard.

Résumé technique : Archives de cache KV fractales

Énoncé du problème

Le service de modèles de langage transformeurs sur de longs contextes est passé d'un défi de calcul à un défi de mémoire. Le cache Clé-Valeur (KV), requis pour l'attention autorégressive, croît linéairement avec la longueur du contexte, dépassant souvent le poids des modèles et limitant les tailles de lots (batch sizes). Alors que les solutions existantes se concentrent sur la compression avec perte (quantification, éviction, déchargement), cet article traite d'une question en aval, souvent implicite : Une fois qu'un état KV a été réduit en un flux de symboles via la quantification vectorielle, comment ce flux doit-il être stocké ?

Les auteurs soutiennent que la couche de stockage ne doit pas être un bloc inerte, mais une composante active capable de supporter les schémas d'accès spécifiques d'un cache en croissance : un ajout (append) amorti en O(1) (à mesure que de nouveaux jetons arrivent) et un accès aléatoire en O(1) (pour récupérer les positions passées), tout en offrant potentiellement des fonctionnalités supplémentaires comme la récupération sur place (in-place retrieval).

Méthodologie

1. Le primitif de stockage : Codes par itération de cartes contractives

L'article propose l'utilisation d'un code de carte itérée contractive sans perte (spécifiquement, une généralisation de la Représentation du Jeu du Chaos et des Cartes de Séquences Universelles) comme couche de sérialisation pour les indices KV quantifiés.

Mécanisme : Une séquence de symboles sur un alphabet de taille $N$ est projetée en une trajectoire de points dans un plan 2D. Un $N$ -gone régulier est fixé avec un sommet par symbole. Chaque symbole $c_k$ projette le point actuel $p_{k-1}$ vers un nouveau point $p_k$ via la contraction $p_k = V(c_k) + r(p_{k-1} - V(c_k))$ , où $r$ est un rapport de contraction.
Propriétés :
- Sans perte : La carte est inversible si le rapport de contraction $r$ est suffisamment petit pour garantir des « cellules » disjointes pour chaque symbole.
- Efficacité : L'encodage est de temps linéaire. Le décodage permet un accès aléatoire à n'importe quelle position en reconstruisant uniquement l'étendue nécessaire à partir du point d'ancrage le plus proche.
- Auto-similarité : L'ensemble des points atteignables forme un attracteur fractal (par exemple, un gasket de Sierpinski pour $N=3$ ).
Implémentation : Pour atténuer l'amplification de l'erreur de virgule flottante lors de l'inversion, le codec stocke un point par étendue de longueur fixe et reconstruit les étendues via une recherche arrière ancrée.

2. Stratégie de quantification

Les auteurs mènent une étude contrôlée sur GPT-2 (124M) avec des contextes de 1024 jetons pour déterminer le schéma de quantification optimal alimentant cette archive :

Fenêtre exacte : Pour maintenir les performances, une petite fenêtre exacte est conservée (4 jetons de « puits d'attention » + 32 jetons récents). Le reste du contexte est archivé.
Variantes de quantification :
- Groupée vs Par-tête (Pooled vs Per-Head) : Comparaison d'un codebook unique partagé par toutes les têtes d'attention versus des codebooks individuels par tête.
- Quantification Vectorielle Résiduelle (RVQ) : Stockage des vecteurs comme une somme de $s$ indices provenant de codebooks.
- Asymétrie Clé/Valeur : Étude de l'impact différentiel de la quantification des Clés (K) par rapport aux Valeurs (V).

3. Récupération sur place (In-Place Retrieval)

L'article exploite une propriété géométrique du code de carte itérée : les points partageant un suffixe commun de longueur $s$ sont spatialement proches (distance $\approx 2r^s$ ). Cela permet d'exécuter des requêtes de sous-chaînes approximatives directement sur les vecteurs 2D stockés via une recherche de plus près voisin, sans décompresser le texte environnant.

Résultats clés

1. Performance du codec

Le codec fractal agit comme un primitif de stockage haute performance indépendant du modèle :

Encodage : 0,68 µs/caractère (temps linéaire).
Accès aléatoire : 311 µs/recherche pour un document de 1M de caractères.
Ajout (Append) : 175 µs/jeton (amorti).

2. Résultats de la quantification (GPT-2, 1024 jetons)

Supériorité du mode Par-Tête : Les codebooks par tête surpassent nettement les codebooks groupés à budget de bits égal. Une RVQ par tête (profondeur 2) réduit l'augmentation de la perplexité à +15,0 % contre +29,2 % pour une RVQ groupée.
Asymétrie Clé/Valeur : La quantification des Clés est environ 4 fois plus dommageable pour la perplexité que la quantification des Valeurs.
- Valeurs seules (Clés exactes) : +4,0 % de perplexité.
- Clés seules (Valeurs exactes) : +14,5 % de perplexité.
- Cela confirme que les Clés déterminent le routage de l'attention (haute sensibilité), tandis que les Valeurs sont moyennées (atténuation de l'erreur).
Schéma hybride optimal : Allouer plus de bits aux Clés (4 étapes RVQ) et moins aux Valeurs (2 étapes) offre le meilleur compromis :
- Compression : Réduction de 36× par rapport à un cache fp16.
- Coût de perplexité : +11,2 % (spécifiquement +16,6 % dans la « seconde moitié » du contexte où l'archive domine).
- Stockage : 1025 octets/jeton.

3. Capacités de récupération

Rappel exact : Le seuillage de la distance entre les points stockés permet de récupérer toutes les positions possédant un suffixe correspondant de longueur $\ell$ avec un rappel de 1,00.
Précision : Contrôlée par la précision numérique. Les indices en double précision atteignent une précision de 0,89–1,00 ; la précision simple sert de filtre grossier.
Efficacité : La recherche de plus proche voisin par force brute sur 100K positions dans l'espace 2D prend ~0,9 ms/requête.
Décodage : Le contexte correspondant est décodé vers l'arrière à partir du vecteur correspondant sans accéder au texte externe.

Signification et revendications

L'article revendique trois contributions principales, se distinguant des travaux concomitants (ex: FibQuant, RetroInfer) qui se concentrent sur la géométrie des codebooks ou les moteurs de stockage vectoriel :

Un format d'archive unifié : Il présente le code de carte itérée contractive comme un archive KV pratique qui est simultanément un stock sans perte, un décodeur à accès aléatoire et un index de recherche sur place. Cette unification du stockage et de la récupération dans une seule représentation est présentée comme la contribution novatrice.
Aperçus sur la quantification : Il quantifie l'asymétrie Clé/Valeur comme un budget de perplexité spécifique, démontant qu'un schéma hybride de bits asymétrique (4x plus de bits pour les Clés, 2x pour les Valeurs) est le point de fonctionnement optimal.
Mémoire Recherchable : Il démontre que l'archive supporte la correspondance de suffixe directement sur la représentation compressée, permettant un décodage augmenté par la récupération où le modèle peut localiser les contextes passés pertinents sans matérialiser l'intégralité du cache.

Limites reconnues par les auteurs

Échelle : Les expériences sont limitées à GPT-2 (124M) et un contexte unique de 1024 jetons. Les résultats sur des modèles plus larges n'ont pas été testés (bien qu'ils soient probablement plus tolérants à la quantification).
Entraînement des Codebooks : Les codebooks sont entraînés par corpus, et non de manière amortie sur les données.
Portée de la récupération : La récupération est strictement une correspondance de structure de séquence (suffixes), et non une recherche sémantique sur les embeddings.
Ratio de compression : Le ratio de compression brut du codec fractal est comparable aux compresseurs d'octets standards ; son avantage réside dans le schéma d'accès (accès aléatoire/recherche) plutôt que dans la réduction de taille pure.
Benchmarking : Le papier ne compare pas ses résultats aux conceptions de codebooks spécifiques de travaux concomitants comme FibQuant, reconnaissant que la combinaison de leurs quantificateurs avec ce format de stockage est un travail futur.