Synchronizing Probabilities in Model-Driven Lossless Compression

Dit paper introduceert PMATIC, een model-agnostisch algoritme dat modelgestuurde verliesvrije compressie robuust maakt tegen voorspellingafwijkingen door probabilistische intervalcodering te synchroniseren, wat leidt tot betere compressieprestaties dan bestaande tools.

De kern

Hier is een uitleg van het paper "Synchronizing Probabilities in Model-Driven Lossless Compression" in eenvoudig Nederlands, met behulp van creatieve vergelijkingen.

De Kernprobleem: Twee Kunstenaars die niet precies hetzelfde tekenen

Stel je voor dat je een heel lang verhaal wilt opslaan op een computer, maar dan zo klein mogelijk. Om dit te doen, gebruiken moderne computers (zoals AI) een slimme truc: ze voorspellen het volgende woord in de zin. Als de AI denkt dat er een 90% kans is dat het woord "de" komt, en een 10% kans op "het", dan kan het de tekst heel efficiënt comprimeren. Dit werkt als een geheime code tussen een zender (de encoder) en een ontvanger (de decoder).

Het probleem:
Voor deze code te werken, moeten de zender en de ontvanger exact hetzelfde voorspellen. Maar moderne AI-modellen draaien op krachtige chips (zoals GPU's). Net zoals twee verschillende artiesten die hetzelfde schilderij proberen te kopiëren, kunnen er kleine verschillen ontstaan door:

• Verschillende computermodellen (een MacBook vs. een Windows-pc).
• Verschillende software-versies.
• Zelfs de volgorde waarin de computer berekeningen doet.

Deze kleine verschillen lijken niets, maar in de wereld van data-compressie is dat als een domino-effect. Als de ontvanger één woord verkeerd raadt door een klein rekenfoutje, raakt hij de draad kwijt. Hij denkt dat de volgende woorden ook anders zijn, en binnen enkele seconden is het hele bericht onleesbare rommel. Dit noemen de auteurs "prediction mismatch" (voorspellingsmismatch).

De Oplossing: PMATIC (De "Veilige" Code)

De auteurs, Aviv Adler en Jennifer Tang, hebben een nieuwe methode bedacht genaamd PMATIC. Ze noemen het een "model-agnostisch algoritme", wat betekent dat het werkt met elk slim AI-model, of het nu een taalmodel is of een beeldherkenningsmodel.

Hoe werkt het? Stel je voor dat je twee mensen hebt die een gesprek voeren, maar ze zitten in verschillende kamers met een slechte verbinding. Ze moeten precies hetzelfde zeggen, maar ze maken soms kleine foutjes.

In plaats van te proberen de verbinding perfect te maken (wat onmogelijk is), zeggen ze tegen elkaar: "Laten we het gesprek opdelen in grote blokken."

1. De Blokken (Binnen):
   De AI voorspelt een kans (bijvoorbeeld 0,45). In plaats van dat getal exact te gebruiken, kijken we naar een "netje" of een rooster.

   • Als de voorspelling in het midden van een blokje valt, zeggen ze: "Oké, we gebruiken het midden van dit blokje."
   • Als de voorspelling heel dicht bij de rand van een blokje zit (waar de ene kant overgaat in de andere), dan is het onzeker of de ander ook in datzelfde blokje zit.

2. Het Hulpje (De Helper Bit):
   Hier komt de slimme truc. Voordat ze het daadwerkelijke woord coderen, sturen ze een klein hulpje (een "helper bit").

   • Geen hulpje nodig (0): Als de voorspelling veilig in het midden zit, sturen ze een "0". De ontvanger weet dan: "Ah, jij zit in dit blokje, ik zit ook in dit blokje, laten we het midden gebruiken."
   • Hulpje nodig (1): Als de voorspelling bij de rand zit, sturen ze een "1". De ontvanger denkt: "Oeps, je zit bij de rand. Ik moet ook naar de rand kijken." Ze komen dan overeen om de rand zelf te gebruiken als referentiepunt.

Door dit kleine "hulpje" te sturen, weten beide kanten altijd precies welke "gemeenschappelijke taal" ze moeten spreken, zelfs als hun eigen berekeningen een beetje afwijken.

Waarom is dit slim?

• Het is robuust: Zelfs als de computers op de zender en ontvanger heel verschillend zijn (bijvoorbeeld een oude laptop vs. een nieuwe server), werkt de code nog steeds. De AI's hoeven niet langer exact hetzelfde te zijn, zolang ze maar binnen een bepaalde "marge" blijven.
• Het is efficiënt: De meeste voorspellingen zitten veilig in het midden van de blokken. Het "hulpje" (de 1) is dus zeldzaam. Omdat het zeldzaam is, kost het heel weinig ruimte om het te sturen. Het is alsof je in een briefje schrijft: "Vandaag is het weer normaal" (kost weinig) in plaats van "Vandaag is het regenen, sneeuwen, onweersbui..." (kost veel).
• Beter dan de rest: De auteurs hebben dit getest met krachtige AI-modellen (zoals Llama 3 en Mistral) op teksten zoals Wikipedia en Shakespeare. Zelfs met de extra "hulpjes" voor de veiligheid, comprimeerden ze de tekst veel beter dan de standaard methoden die we vandaag de dag gebruiken (zoals ZIP of GZIP).

De Vergelijking in het Kort

• De oude manier (Arithmetic Coding): Twee mensen proberen een danspas exact na te bootsen. Als de ene persoon een millimeter te veel draait, vallen ze allebei om.
• De nieuwe manier (PMATIC): Twee mensen dansen op een vloer met grote tegels. Als je niet precies in het midden van de tegel staat, roep je even: "Ik ben bij de rand!" De ander roept terug: "Oké, dan doen we de rand." Ze vallen nooit om, en de dans gaat gewoon door.

Conclusie

Dit paper lost een groot praktisch probleem op: hoe maak je slimme, AI-gedreven data-compressie veilig voor gebruik op verschillende computers? Met PMATIC kunnen we de kracht van moderne AI gebruiken om bestanden superklein te maken, zonder bang te hoeven zijn dat een klein rekenfoutje op een andere computer het hele bestand vernietigt. Het is een brug tussen de theorie van perfecte AI en de ruwe realiteit van verschillende computers.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het paper "Synchronizing Probabilities in Model-Driven Lossless Compression" in het Nederlands.

Titel: Synchroniseren van Kansen in Model-Gedreven Verliesvrije Compressie

Auteurs: Aviv Adler en Jennifer Tang
Publicatie: ICLR 2026

---

1. Het Probleem: Voorspellingmismatch door Non-Determinisme

Verliesvrije datacompressie, en specifiek model-gedreven compressie, vertrouwt erop dat zowel de encoder (die comprimeert) als de decoder (die decomprimeert) exact dezelfde probabilistische voorspellingen maken voor het volgende symbool in een sequentie. Moderne methoden gebruiken diepe neurale netwerken (zoals LLM's) om deze kansen te schatten, vaak gekoppeld aan arithmetic coding.

Het fundamentele probleem dat dit paper adresseert is non-determinisme in machine learning-inferentie. Zelfs met identieke modellen en invoer kunnen de encoder en decoder op verschillende hardware (bijv. verschillende GPU's of CPU-architecturen) of door variaties in software-uitvoering, licht verschillende uitkomsten genereren.

• Oorzaak: Floating-point afrondingsfouten, parallelle verwerking en niet-garandeerde determinisme in bibliotheken zoals CUDA/cuDNN.
• Gevolg: Zelfs een klein verschil in de voorspelde kansen leidt bij arithmetic coding tot een cascaderend decodeerfout. Zodra één symbool verkeerd wordt gedecodeerd, verandert de context voor alle volgende symbolen, waardoor de volledige bestandsreconstructie faalt.
• Huidige situatie: Bestaande oplossingen vereisen vaak deterministische backends (wat prestatiekost heeft) of zijn niet robuust tegen deze kleine numerieke afwijkingen.

2. Methodologie: PMATIC (Probability-Matched Interval Coding)

Het paper introduceert PMATIC, een model-agnostisch algoritme dat ontworpen is om begrensde voorspellingmismatch te tolereren zonder dat de encoder en decoder exact dezelfde kansen hoeven te hebben. Het werkt als een "drop-in" vervanging voor de arithmetic encoder.

Kernprincipes van PMATIC:

1. Bit-gebaseerde compressie: In plaats van tokens direct te comprimeren, worden tokens omgezet naar een binaire representatie ("longform") en bit voor bit gecodeerd.
2. Kwantisering van Kansen: Het interval $[0, 1]$ wordt opgedeeld in gelijke "bins" met een straal $r$.
3. Gemeenschappelijke Referentie: De encoder en decoder komen overeen om een specifieke kanswaarde te gebruiken die binnen dezelfde bin valt, in plaats van hun exacte (en mogelijk verschillende) voorspellingen.
4. Helper-bits: Om zekerheid te hebben dat beide kanten dezelfde bin of grens kiezen, wordt er een extra "helper bit" verzonden:
   • Case 1 (Bin-interieur): Als de voorspelling diep genoeg in een bin zit (binnen een $\delta$-marge van de randen), weten beide kanten dat ze in dezelfde bin zitten. Ze kwantiseren naar het centrum van de bin. De helper bit is 0.
   • Case 2 (Bin-rand): Als de voorspelling dicht bij de grens van twee bins ligt, weten ze niet zeker in welke bin de andere zit, maar weten ze wel dat ze dicht bij dezelfde grens zitten. Ze kwantiseren naar de grens tussen de bins. De helper bit is 1.
5. Robuustheid: Zolang het verschil tussen de encoder- en decoder-kansen kleiner is dan een vooraf gedefinieerde drempel $\delta$ (gemeten in conditionele totale variatie-afstand), zullen ze altijd dezelfde gekwantiseerde waarde kiezen en dus correct decoderen.

3. Belangrijkste Bijdragen

• Formalisatie van het probleem: Het paper definieert formeel het probleem van mismatch-tolerantie in model-gedreven compressie en introduceert de maatstaf voor conditionele totale variatie-afstand ($d_{CTV}$).
• Theoretische Correctheid: Bewezen dat PMATIC gegarandeerd correct decodeert zolang de mismatch binnen de grens $\delta$ blijft.
• Theoretische Prestatiegrenzen: Afgeleide theoretische bovengrenzen voor de compressie-overhead (de extra bits die nodig zijn voor de helper-bits en de kwantisatiefout). De overhead wordt geoptimaliseerd door de bin-grootte $r$ in balans te brengen met de tolerantie $\delta$.
• Praktische Validatie: Experimentele bewijzen dat PMATIC werkt met moderne LLM's (LLaMA 3.1, Mistral, Qwen) op tekstdata, zelfs bij echte non-determinisme tussen verschillende hardware-platforms.

4. Resultaten

De auteurs testten PMATIC op diverse datasets (o.a. enwik8, Wikipedia, Shakespeare, Austen, Voltaire, en Chinese literatuur) met verschillende LLM-modellen.

• Compressieverhouding:
  • PMATIC behaalt aanzienlijk betere compressieverhoudingen dan traditionele tools zoals gzip, bzip2, xz en zelfs state-of-the-art tools zoals CMIX en zstd.
  • Zelfs met de hoogste robuustheidsinstellingen (grootste $\delta$), presteert PMATIC beter dan traditionele methoden.
  • De "overhead" (het verlies in compressie door het gebruik van PMATIC t.o.v. niet-robuste arithmetic coding) is klein, maar neemt toe naarmate de tolerantie $\delta$ groter wordt.
• Robuustheid tegen Non-Determinisme:
  • Synthetische test: Bij het toevoegen van willekeurige ruis binnen de theoretische grenzen, slaagden alle bestanden in het decoderen.
  • Real-world test: Bij het coderen op een Apple M2 Pro en decoderen op een Apple M4 Max (twee verschillende chips), faalde standaard arithmetic coding volledig. PMATIC met $\delta = 0.01** slaagde echter in het correct decoderen van alle bestanden.
• Helper-bits: De analyse toont aan dat helper-bits in de praktijk veel minder vaak 1 zijn dan theoretisch verwacht (op basis van uniforme verdeling), omdat voorspellingen vaak zeer zeker zijn (dicht bij 0 of 1). Dit suggereert dat verdere optimalisatie van de helper-bit-compressie mogelijk is.

5. Betekenis en Toekomstperspectief

Dit paper biedt een cruciale oplossing voor een van de grootste praktische obstakels bij het gebruik van LLM's voor verliesvrije compressie: de onmogelijkheid om exacte determinisme te garanderen op heterogene hardware.

• Praktische toepasbaarheid: Het maakt het mogelijk om krachtige, context-gevoelige compressiealgoritmen op te schalen zonder dat men zich zorgen hoeft te maken over hardware-specifieke numerieke fouten.
• Theoretische bijdrage: Het legt een brug tussen informationstheorie en de realiteit van onzekerheid in machine learning-systemen.
• Toekomstig werk: De auteurs wijzen op potentieel voor uitbreiding naar andere domeinen (zoals afbeeldingen), het verbeteren van de schatting van helper-bit-kansen, en het onderzoeken van stochastische (in plaats van strikt begrensde) mismatch-modellen.

Kortom, PMATIC maakt model-gedreven verliesvrije compressie robuust, reproduceerbaar en praktisch toepasbaar in real-world scenario's waar hardware-variabiliteit onvermijdelijk is.