🤖 machine learning

Quad Length Codes for Lossless Compression of e4m3

Dit artikel introduceert Quad Length Codes, een hybride compressiemethode voor e4m3-gegevens die, ondanks een iets lagere compressie dan Huffman-codes, aanzienlijk snellere decodering en eenvoudigere hardware-implementatie biedt door het gebruik van een vooraf bepaalde prefixstructuur en een lookup-tabel.

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

Gepubliceerd 2026-02-26

📖 4 min leestijd☕ Koffiepauze-leesvoer

CC BY 4.0

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

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een enorm boek moet versturen naar een vriend, maar de postbode (het netwerk) kan maar heel weinig per keer dragen. Als je het boek niet verkleint, duurt het eeuwen voordat je vriend het ontvangt. In de wereld van kunstmatige intelligentie (zoals de slimme modellen die Google gebruikt) gebeurt precies dit: er moeten gigantische hoeveelheden gegevens worden verplaatst tussen duizenden computers.

De auteurs van dit paper, een team van Google, hebben een nieuwe manier bedacht om die gegevens in te pakken. Ze noemen het Quad Length Codes. Laten we uitleggen hoe dit werkt, zonder ingewikkelde wiskunde.

Het Probleem: De Twee Uitersten

Om de postbode te helpen, kun je twee dingen doen:

De "Slimme Pakker" (Huffman Codes):
Stel je voor dat je een pakker hebt die heel goed is. Hij kijkt naar elk woord in je boek. Woorden die vaak voorkomen (zoals "de" of "en") krijgt hij een heel kort label, zoals "A". Woorden die zelden voorkomen (zoals "kameleon") krijgt hij een lang label, zoals "X9Z".
- Voordeel: Het boek wordt extreem klein.
- Nadeel: De pakker moet heel lang zoeken in zijn lijstje om te weten welk label bij welk woord hoort. Het is alsof je een enorme boom moet beklimmen om bij het juiste label te komen. Dit kost tijd en is traag.
De "Snelle Pakker" (Universele Codes):
Deze pakker is niet slim, maar wel supersnel. Hij gebruikt een vast patroon, bijvoorbeeld: "Elk woord krijgt een nummer, en ik tel de lengte van het nummer mee."
- Voordeel: Hij is razendsnel.
- Nadeel: Hij pakt niet slim in. Woorden die vaak voorkomen krijgen net zo'n lang label als zeldzame woorden. Het boek wordt niet veel kleiner.

Google wilde een pakker die slim is (zoals de eerste) maar ook snel (zoals de tweede).

De Oplossing: De "Kwartier-Indeling" (Quad Length Codes)

De auteurs bedachten een hybride systeem. In plaats van voor elk van de 256 mogelijke symbolen een unieke, willekeurige lengte te bedenken (zoals bij de slimme pakker), hebben ze de wereld opgedeeld in 8 grote gebieden (kwartieren).

Stel je een hotel voor met 256 kamers:

De Entree (De eerste 3 bits):
Zodra de pakker een bericht binnenkrijgt, kijkt hij eerst naar de eerste 3 cijfers. Dit is als een bordje bij de lift dat zegt: "Ga naar Vloer 1 t/m 8". Dit kost heel weinig tijd.
De Vloeren (De gebieden):
- Vloer 1 t/m 5: Hier zitten de populairste gasten (de meest voorkomende symbolen). Omdat we weten dat ze hier zitten, hoeven we ze maar met een kort nummer te identificeren.
- Vloer 6: Iets minder populair, dus een iets langer nummer.
- Vloer 7: Nog minder populair, nog een langer nummer.
- Vloer 8: Hier zitten de "zeldzame" gasten. Omdat er heel veel van zijn, gebruiken we een lang nummer.

Het magische trucje:
In plaats van 13 verschillende soorten nummers (zoals bij de oude slimme pakker), gebruiken ze nu maar 4 verschillende lengtes (6, 7, 8 of 11 bits).

Waarom is dit zo geweldig?

Stel je voor dat je een computerchip bent die deze gegevens moet decoderen (lezen).

Bij de oude methode (Huffman): Je moet een ingewikkeld labyrint doorlopen. Je loopt een pad, kijkt of je links of rechts moet, loopt nog een stukje, kijkt weer... Dit kost veel tijd en energie.
Bij de nieuwe methode (Quad Length): Je kijkt naar de eerste 3 cijfers.
- "Ah, het begint met 000? Dan weet ik direct: het volgende stukje is 3 cijfers lang."
- "Het begint met 111? Dan weet ik direct: het volgende stukje is 8 cijfers lang."
- Je hoeft niet te zoeken in een labyrint. Je pakt gewoon een lijstje (een tabel) en slaat het antwoord direct op.

De Resultaten in het Kort

Snelheid: De nieuwe methode is veel sneller omdat het geen diepe zoektochten vereist. Het is alsof je van een wandeling door een bos (Huffman) naar het nemen van een snelle lift (Quad Length) gaat.
Grootte: Het pakketje is wel iets groter dan bij de allerbeste methode (ongeveer 2% meer ruimte nodig), maar de snelheidswinst is zo groot dat het de moeite waard is.
Eenvoud: De hardware die dit doet, kan veel simpeler worden gebouwd. Geen ingewikkelde bomen meer, maar een simpele lijst met 256 regels.

Conclusie

Google heeft een manier gevonden om de "postbode" van hun AI-modellen te helpen. Ze hebben een systeem bedacht dat net slim genoeg is om de boodschappen klein te houden, maar simpel genoeg om razendsnel te worden gelezen. Het is de perfecte balans tussen efficiëntie (ruimte besparen) en snelheid (tijd winnen), waardoor onze AI-toepassingen straks sneller en soepeler werken.

Probleemstelling

Het trainen en bedienen van Large Language Models (LLMs) zoals Gemini, Gemma en LLaMA vereist intensieve parallelle verwerking en collectieve operaties (zoals AllReduce en AllGather) over meerdere accelerators. Deze operaties worden vaak beperkt door de netwerkbandbreedte. Hoewel verliesvrije compressie (bijvoorbeeld met Huffman-codes) de netwerkverkeersdrukte kan verminderen, lopen bestaande methoden tegen twee belangrijke beperkingen aan:

Huffman-codes: Hoewel ze optimaal zijn wat betreft entropie en compressie, vereisen ze een binaire boomtraversie voor decoding. Dit leidt tot een bit-sequentiële decoding, wat traag is en complexe hardware vereist vanwege de diepe boomstructuren.
Universele codes (bijv. Exponential-Golomb): Deze zijn sneller te decoderen omdat de code-lengte deel uitmaakt van de code, maar ze exploiteren niet de frequentieverdeling van symbolen, waardoor ze minder efficiënt comprimeren.

Het doel is een coderingsschema te ontwikkelen dat de compressie-efficiëntie van Huffman benadert, maar de decodingssnelheid en hardware-simpliciteit van universele codes behoudt.

Methodologie: Quad Length Codes

De auteurs introduceren Quad Length Codes, een hybride aanpak die de symbolen (in dit geval 8-bit waarden voor het e4m3 data-type) in gebieden indelt op basis van hun frequentie.

Indeling in Gebieden: De 256 mogelijke symbolen worden verdeeld in 8 gebieden (areas) aan de hand van 3 prefix-bits.
Variabele Code-lengtes per Gebied: Elk gebied heeft een vast aantal symbolen en een bijbehorende code-lengte. In plaats van een unieke code-lengte voor elk symbool (zoals bij Huffman), zijn er slechts 4 unieke code-lengtes (vandaar de naam "Quad Length").
- Voorbeeld (Schema voor FFN1 activaties):
  - Gebieden 1-5: 8 symbolen elk $\rightarrow$ 3 prefix-bits + 3 symbool-bits = 6 bits.
  - Gebied 6: 16 symbolen $\rightarrow$ 3 prefix-bits + 4 symbool-bits = 7 bits.
  - Gebied 7: 32 symbolen $\rightarrow$ 3 prefix-bits + 5 symbool-bits = 8 bits.
  - Gebied 8: 168 symbolen $\rightarrow$ 3 prefix-bits + 8 symbool-bits = 11 bits.
Implementatie via Look-Up Tables (LUT):
- Encoder: De invoersymbolen worden gesorteerd op afnemende frequentie en gemapt naar een index (0-255). Een LUT met 256 entries vertaalt het invoersymbool naar de gecomprimeerde code.
- Decoder: De decoder leest eerst de 3 prefix-bits om de code-lengte te bepalen. Vervolgens leest hij de resterende bits en gebruikt een LUT om de oorspronkelijke waarde te herstellen. Dit elimineert de noodzaak voor diepe boomtraversies.
Adaptiviteit: Het schema kan worden aangepast aan verschillende frequentieverdelingen. Voor FFN2-activaties, waar het symbool '0' extreem frequent voorkomt, wordt een aangepast schema gebruikt met code-lengtes van 4, 6, 8 en 11 bits om de compressie te optimaliseren.

Kernresultaten

De methode is getest op het Gemma 2B-model tijdens Supervised Fine Tuning (SFT) op 64 TPUs, met focus op FFN1 en FFN2 activatie- en gewichtsgradiënten in het e4m3 formaat.

Compressie-efficiëntie:
- Huffman: Bereikt 15,9% compressie voor FFN1-activaties.
- Quad Length Codes: Bereikt 13,9% compressie voor FFN1-activaties (een verlies van ongeveer 2,0% ten opzichte van Huffman).
- Voor FFN2-activaties (waar de verdeling extreem scheef is) levert het aangepaste Quad Length-schema 19,0% compressie op, vergeleken met 23,2% voor Huffman.
Decodingssnelheid en Hardware:
- In tegenstelling tot Huffman, waarbij de code-lengtes variëren van 6 tot 18 bits (of zelfs 39 bits bij FFN2), zijn de code-lengtes bij Quad Length Codes beperkt tot slechts 4 waarden.
- Dit vereenvoudigt de hardware-implementatie aanzienlijk omdat er geen diepe binaire bomen nodig zijn.
- De decoding is niet langer volledig bit-sequentiëel, wat leidt tot een significante versnelling van de decoding en lagere latentie.

Bijdragen en Significantie

Balans tussen Efficiëntie en Snelheid: Het paper biedt een praktische oplossing voor het compromis tussen maximale compressie (Huffman) en decodingssnelheid. Voor ML-workloads waar netwerkbandbreedte en doorvoer cruciaal zijn, weegt de winst in snelheid en hardware-simpliciteit vaak op tegen een kleine daling in compressie-ratio.
Hardware-vriendelijk ontwerp: Door het gebruik van een vaste prefix-lengte (3 bits) en een beperkt aantal code-lengtes, wordt de complexiteit van de decoder drastisch verlaagd ten opzichte van traditionele Huffman-decoders.
Toepasbaarheid: De methode is specifiek ontworpen voor het e4m3 data-type (veel gebruikt in ML), maar het concept van het indelen van symbolen in gebieden met vaste code-lengtes is breed toepasbaar op andere distributies.
Empirische Validatie: De auteurs tonen aan dat door het schema aan te passen aan de specifieke frequentieverdeling van verschillende tensor-types (zoals FFN1 vs. FFN2), de compressie-efficiëntie verder kan worden geoptimaliseerd.

Conclusie: Quad Length Codes zijn een effectieve techniek voor verliesvrije compressie in ML-systemen. Ze bieden een aanzienlijke verbetering in decodingssnelheid en hardware-vereisten ten opzichte van Huffman-codes, met slechts een marginaal verlies in compressie-efficiëntie, wat ze ideaal maakt voor high-performance computing omgevingen zoals het trainen van LLMs.