🤖 machine learning

Quad Length Codes for Lossless Compression of e4m3

Ce papier présente les Quad Length Codes, une méthode hybride de compression sans perte pour les données e4m3 qui, bien que légèrement moins efficace que le codage de Huffman, offre une décodage plus rapide et une complexité matérielle réduite grâce à l'utilisation d'une table de recherche de 256 entrées.

Auteurs originaux : Aditya Agrawal, Albert Magyar, Hiteshwar Eswaraiah, Patrick Sheridan, Pradeep Janedula, Ravi Krishnan Venkatesan, Krishna Nair, Ravi Iyer

Publié 2026-02-26

📖 4 min de lecture☕ Lecture pause café

CC BY 4.0

Auteurs originaux : Aditya Agrawal, Albert Magyar, Hiteshwar Eswaraiah, Patrick Sheridan, Pradeep Janedula, Ravi Krishnan Venkatesan, Krishna Nair, Ravi Iyer

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

🚀 Le Problème : L'embouteillage sur l'autoroute de l'IA

Imaginez que vous dirigez une immense équipe de chercheurs (les Intelligences Artificielles ou LLM) qui travaillent ensemble sur un projet colossal. Pour aller vite, ils doivent constamment s'échanger des documents (des données) entre eux.

Le problème ? La route (le réseau) est trop étroite. Les documents sont si gros que les chercheurs passent plus de temps à attendre leur tour pour les envoyer qu'à travailler. C'est ce qu'on appelle un goulot d'étranglement.

Pour résoudre ça, on a besoin de compresser les documents : les rendre plus petits pour qu'ils passent plus vite sur la route, sans perdre une seule virgule d'information (compression "sans perte").

🌳 La Solution Classique : L'arbre de Huffman (Le dictionnaire trop complexe)

Jusqu'à présent, on utilisait une méthode appelée Huffman.
Imaginez un dictionnaire où les mots les plus courants (comme "le", "de", "et") sont écrits très court, et les mots rares sont écrits très long. C'est très efficace pour réduire la taille.

Mais il y a un hic : Pour lire ce dictionnaire, il faut grimper dans un arbre très haut et très complexe.

Si le mot est court, vous descendez vite.
Si le mot est long, vous devez grimper des étages et des étages.
Résultat : Le décodeur (celui qui lit le message) est lent et compliqué à construire en matériel électronique. C'est comme essayer de trouver un livre dans une bibliothèque où les rayonnages sont des escaliers en colimaçon infinis.

⚡ La Nouvelle Idée : Les "Codes Quad" (Le système de zones)

Les auteurs de ce papier (chez Google) ont dit : "Et si on simplifiait la bibliothèque ?"

Au lieu d'avoir un arbre infini, ils ont divisé les 256 symboles possibles (tous les petits morceaux de données) en 8 grandes zones (ou quartiers).

Voici comment ça marche, avec une analogie simple :

Les 3 premiers bits sont comme un code postal :
Imaginez que chaque symbole commence par 3 petits drapeaux (000, 001, 010, etc.). Ces 3 drapeaux vous disent immédiatement dans quel "quartier" vous êtes.
- Quartier 1 à 5 : C'est la ville haute. Tout le monde y habite dans des petites maisons. Le message est court (6 bits).
- Quartier 6 : C'est la banlieue. Les maisons sont un peu plus grandes (7 bits).
- Quartier 7 : C'est la zone industrielle. Les maisons sont moyennes (8 bits).
- Quartier 8 : C'est la grande plaine. Il y a beaucoup de gens, donc les maisons sont grandes (11 bits).
La magie de la simplicité :
Au lieu de grimper un arbre, le décodeur regarde juste les 3 premiers drapeaux.
- Il voit "000" ? Il sait immédiatement : "Ah, c'est le quartier 1, je n'ai qu'à lire 3 petits symboles de plus !".
- Il voit "111" ? Il sait : "C'est le quartier 8, je dois lire 8 symboles de plus".

C'est comme si, au lieu de chercher un livre dans un labyrinthe, vous regardiez juste le code postal sur l'enveloppe, et le facteur savait exactement dans quelle boîte mettre le courrier.

📊 Les Résultats : Un petit compromis pour une vitesse énorme

Les chercheurs ont testé ça sur des données d'IA (le format "e4m3").

Le Code Huffman (L'ancien) : Il comprime très bien (réduit la taille de 15,9 %). Mais il est lent et compliqué à fabriquer.
Le Code Quad (Le nouveau) : Il comprime un peu moins bien (réduit la taille de 13,9 %). C'est un tout petit peu moins efficace.
MAIS : Il est beaucoup plus rapide à lire et beaucoup plus simple à construire en matériel électronique.

🎯 En résumé

Imaginez que vous devez envoyer 100 paquets.

Huffman, c'est comme un expert en logistique qui fait des paquets de tailles parfaites, mais qui passe 10 minutes à les emballer un par un.
Quad Length, c'est un système où on met les paquets dans 8 types de boîtes standardisées. On perd un tout petit peu d'espace dans les boîtes (car elles ne sont pas taillées sur mesure), mais on peut les emballer et les lire instantanément.

Pour les supercalculateurs d'IA qui doivent aller à la vitesse de la lumière, gagner du temps de lecture est souvent plus important que de gagner quelques pourcents d'espace. C'est pour cela que cette méthode est une excellente avancée.

1. Contexte et Problématique

L'entraînement et le déploiement des grands modèles de langage (LLM) reposent massivement sur la parallélisation et les opérations collectives (tels que AllReduce, AllGather), qui sont souvent limitées par la bande passante du réseau. La compression sans perte est une solution clé pour réduire le trafic réseau et améliorer les performances.

Cependant, les méthodes de compression existantes présentent des compromis difficiles :

Codes de Huffman : Bien qu'ils soient optimaux en termes d'entropie et exploitent la fréquence des symboles, leur décodage est lent et séquentiel (bit par bit) car il nécessite une traversal profonde d'un arbre binaire. Cela augmente la complexité matérielle et la latence.
Codes Universels (ex: Exponential-Golomb) : Ils sont plus rapides à décoder car la longueur du code est intrinsèque au code lui-même, mais ils n'exploitent pas la distribution spécifique des fréquences des symboles, ce qui les rend sous-optimaux en termes de taux de compression.

Objectif : Développer un schéma de codage qui combine l'efficacité de la compression de Huffman (en exploitant les fréquences) avec la rapidité de décodage des codes universels (non séquentiel), tout en simplifiant l'implémentation matérielle.

2. Méthodologie : Les Codes de Longueur Quad (Quad Length Codes)

Les auteurs proposent une approche hybride appelée Quad Length Codes. Le principe repose sur la division de l'espace des symboles (256 symboles pour le type de données e4m3) en plusieurs zones distinctes, chacune ayant une longueur de code fixe.

Principes de conception

Partitionnement en Zones : Les 256 symboles sont divisés en 8 zones (ou « areas »).
Préfixe de 3 bits : Les 3 premiers bits du code servent d'« area code » pour identifier la zone dans laquelle se trouve le symbole. Cela détermine immédiatement la longueur totale du code.
Longueurs de code variables mais limitées : Contrairement à Huffman qui peut avoir de nombreuses longueurs différentes (ex: 6 à 18 bits), ce schéma utilise un nombre restreint de longueurs de code (4 longueurs distinctes : 6, 7, 8 et 11 bits pour la configuration de base).
- Exemple de la configuration de base (Tableau 1) :
  - Zones 1 à 5 : 8 symboles chacune $\rightarrow$ 3 bits (préfixe) + 3 bits (symbole) = 6 bits.
  - Zone 6 : 16 symboles $\rightarrow$ 3 bits + 4 bits = 7 bits.
  - Zone 7 : 32 symboles $\rightarrow$ 3 bits + 5 bits = 8 bits.
  - Zone 8 : 168 symboles restants $\rightarrow$ 3 bits + 8 bits = 11 bits.

Adaptation aux distributions

Le schéma est adaptable. Pour des distributions où un symbole (comme le zéro) est extrêmement fréquent (cas des activations FFN2), les auteurs proposent une répartition différente (Tableau 2) avec des longueurs de code de 4, 6, 8 et 11 bits, optimisant ainsi la compression pour cette distribution spécifique.

Implémentation Matérielle et Logicielle

Tables de Recherche (LUT) : Au lieu d'un arbre binaire complexe, le système utilise des tables de recherche (Look Up Tables) de 256 entrées.
- Encodeur : Trie les symboles d'entrée par fréquence décroissante, les mappe aux indices 0-255, et utilise la LUT pour trouver le code correspondant.
- Décodeur : Lit les 3 bits de préfixe pour déterminer la longueur du code, lit les bits restants, ajoute un décalage (offset) basé sur la zone, et utilise une LUT pour récupérer le symbole de sortie original.
Avantage : Cette approche élimine la traversée d'arbre, rendant le décodage non séquentiel et beaucoup plus rapide, avec une complexité matérielle réduite.

3. Résultats Expérimentaux

Les expériences ont été menées sur le modèle Gemma 2B lors d'un Supervised Fine Tuning (SFT), en analysant les tenseurs d'activation et de gradient des couches FFN (Feed-Forward Networks) au format de données e4m3 (8 bits).

Comparaison Huffman vs. Quad Length Codes

Cas FFN1 (Activations) :
- Huffman : Compression de 15,9 %. Longueurs de code allant de 6 à 18 bits (arbre très profond).
- Quad Length Codes (Base) : Compression de 13,9 %.
- Gain : Une perte de compression de seulement 2 % par rapport à Huffman, mais avec une simplification drastique de la structure de décodage.
Cas FFN2 (Activations avec pic de fréquence) :
- Huffman : Compression de 23,2 %.
- Quad Length Codes (Adapté) : Compression de 19,0 %.
- Gain : Une amélioration de 2,3 % par rapport à la configuration de base, avec toujours une complexité réduite.

4. Contributions Clés

Nouveau Schéma de Codage : Introduction des « Quad Length Codes », un compromis efficace entre l'optimalité de Huffman et la vitesse des codes universels.
Simplification Matérielle : Remplacement des arbres de Huffman profonds par des tables de recherche (LUT) de taille fixe (256 entrées), facilitant grandement l'implémentation sur le matériel (ASIC/FPGA) et réduisant la latence.
Décodage Non Séquentiel : En fixant la longueur du code via un préfixe court (3 bits), le décodeur peut lire directement la longueur nécessaire sans parcourir l'arbre bit par bit.
Adaptabilité : Démonstration que le schéma peut être ajusté (nombre de zones, répartition des symboles) pour s'adapter à différentes distributions de probabilités rencontrées dans les LLM.

5. Signification et Conclusion

Ce travail propose une solution pragmatique pour les systèmes d'inférence et d'entraînement de LLM où la bande passante et la latence sont critiques. Bien que les Quad Length Codes sacrifient une petite partie de l'efficacité de compression (environ 2 à 4 % de moins que Huffman), ils offrent des avantages majeurs :

Réduction de la latence de décodage grâce à l'absence de traversée d'arbre.
Réduction de la complexité matérielle, ce qui est crucial pour les accélérateurs de calcul où la surface de silicium et la consommation d'énergie sont des contraintes.
Compatibilité avec les formats de données modernes comme e4m3.

Les auteurs concluent que ce compromis est favorable pour les opérations collectives dans les réseaux de neurones, et envisagent de formaliser mathématiquement l'optimisation de ces schémas pour d'autres distributions à l'avenir.