Sequential KV Cache Compression via Probabilistic Language Tries: Beyond the Per-Vector Shannon Limit

Probleemstelling

De huidige staat van de techniek voor het comprimeren van de Key-Value (KV) cache in transformer-modellen (zoals TurboQuant) benadert de Shannon-grens voor per-vector compressie. Dit betekent dat ze de minimale hoeveelheid bits berekenen die nodig is om een geïsoleerd KV-vector te representeren, ongeacht de context.

Het paper identificeert echter een fundamenteel tekortkoming in deze aanpak:

1. Isolatie vs. Sequentie: De KV-cache is geen verzameling van geïsoleerde vectoren, maar een sequentie. Elke vector wordt gegenereerd op basis van een specifieke token in een specifieke context.
2. Voorspelbaarheid: Omdat tokens uit een gestructureerde taalverdeling komen en het model is getraind om deze taal te voorspellen, is de volgende KV-vector sterk voorspelbaar op basis van de eerdere vectoren.
3. De Gaten: De huidige methoden negeren de conditionele entropie (de onzekerheid gegeven de vorige tokens). Voor een goed taalmodel is de "surprisal" (verrassing) van een volgende token laag (typisch 10-20 perplexiteit), wat betekent dat de daadwerkelijke informatie-inhoud van de KV-cache veel lager is dan wat per-vector quantisatie suggereert. TurboQuant zit vast in een "vloer" van ongeveer 3 bits per component, terwijl de sequentiële grens theoretisch veel lager ligt.

Methodologie: Twee-Lagen Architectuur

Het paper introduceert Sequential KV Compression, een architectuur die de structurele redundantie van taal exploiteert via twee orthogonale lagen:

Laag 1: Probabilistische Prefix Deduplicatie (Cross-Session)

In plaats van te zoeken naar exacte overeenkomsten in token-sequenties (zoals bij vLLM of SGLang), gebruikt deze laag de Probabilistic Language Trie (PLT) metric.

• Concept: Twee sessies met semantisch vergelijkbare voorvoegsels (bijv. "Je bent een assistent" vs. "Je bent een AI-assistent") hebben een kleine afstand in de PLT-metriek ($d_T$), zelfs als de tokens niet exact overeenkomen.
• Implementatie: Sessies worden gegroepeerd in "semantische clusters" op basis van hun PLT-afstand. Er wordt een centroïde (de meest waarschijnlijke prefix) geselecteerd.
• Opslag: De volledige KV-cache van de centroïde wordt opgeslagen. Voor andere sessies in de cluster wordt alleen het delta (het verschil) opgeslagen vanaf het punt van divergentie. Omdat de KV-vectoren voor de gedeelde prefix identiek zijn (door determinisme), en het verschil na divergentie klein is, levert dit enorme besparingen op.

Laag 2: Predictieve Delta Coding (Intra-Session)

Binnen één sessie wordt niet de volledige KV-vector opgeslagen, maar alleen het residu (het verschil) tussen de werkelijke vector en de door het model voorspelde vector.

• Voorspelling: Het model berekent de waarschijnlijkheidsverdeling over de volgende token. Hieruit wordt de verwachte KV-vector ($\hat{KV}_i$) afgeleid als de verwachting over alle mogelijke tokens.
• Residu: De op te slaan waarde is $R_i = KV_i - \hat{KV}_i$.
• Entropie: De entropie van dit residu is begrensd door de per-token surprisal van het model. Bij voorspelbare teksten (lage surprisal) is het residu zeer klein (dicht bij nul), wat betekent dat er zeer weinig bits nodig zijn om het te coderen.
• Adaptieve Quantisatie: De quantisatie diepte wordt dynamisch aangepast op basis van de surprisal van de token. Voorspelbare tokens krijgen minder bits, onverwachte tokens meer.

Compositie

Deze twee lagen zijn orthogonaal en kunnen worden gecombineerd met bestaande per-vector quantisatiemethoden (zoals TurboQuant). De volledige stack werkt als volgt:

1. Zoek een clustercentroïde (Laag 1).
2. Bereken het residu ten opzichte van de voorspelling (Laag 2).
3. Quantiseer het residu met een per-vector quantizer (bijv. TurboQuant).

Kernbijdragen

1. De Sequentiële Entropiegrens (Theorema 1): Een formeel bewijs dat de conditionele entropie van een KV-vector, gegeven alle eerdere cache-inhoud, begrensd is door de per-token surprisal van het model ($H(KV_i | KV_{<i}) \leq H(t_i | t_{<i})$).
2. Probabilistische Prefix Deduplicatie: Een methode om semantisch equivalente prefixes over sessies heen te identificeren en te comprimeren, verder gaand dan exacte string-matching.
3. Predictieve Delta Coding: Een techniek om alleen de residuen op te slaan, waarbij de grootte van het residu direct gekoppeld is aan de voorspelbaarheid van de taal.
4. Asymptotisch Gedrag: Het bewijs dat de compressieverhouding verbetert naarmate de contextlengte toeneemt (voor coherente teksten), in tegenstelling tot per-vector methoden waar de kosten lineair en constant blijven per token.

Resultaten en Theoretische Grenzen

Het paper presenteert schokkende theoretische compressieverhoudingen vergeleken met de huidige staat van de techniek (TurboQuant):

• Theoretische Limiet: Voor een model met een perplexiteit van 10-20 (typisch voor vloeiend Engels) is de entropiegrens ongeveer 3,3 tot 4,3 bits per tokenpositie (voor de volledige KV-state van alle lagen en hoofden).
• Vergelijking met TurboQuant: TurboQuant vereist ongeveer 3 bits per component. Voor een groot model (70B parameters, 80 lagen, 64 hoofden, dimensie 128) betekent dit ongeveer $3,93 \times 10^6$ bits per token.
• Compressieverhouding:
  • Theoretisch: Een verhouding van ongeveer 914.000x ten opzichte van TurboQuant.
  • Pessimistisch Praktisch: Zelfs bij een pessimistische schatting van 1000x boven de entropievloer (een zeer conservatieve overhead), blijft de verhouding ongeveer 914x beter dan TurboQuant.
• Contextlengte: Bij lange contexten wordt de compressie efficiënter omdat het model meer context heeft om de volgende token (en dus de KV-vector) nauwkeuriger te voorspellen.

Significantie en Implicaties

1. Doorbreken van de "Memory Wall": De KV-cache is momenteel een van de grootste bottlenecks voor inferentie bij lange contexten. Deze methode suggereert dat de software-oplossing voor dit probleem nog niet uitgeput is door quantisatie alleen; er is een fundamenteel lager niveau van compressie haalbaar door de sequentiële aard van taal te benutten.
2. Jevons Paradox: Door de marginale kosten per token drastisch te verlagen, zouden toepassingen die nu onpraktisch zijn (zoals real-time analyse van documenten met miljoenen tokens, persistente agent-geheugens) economisch haalbaar worden, wat de totale vraag naar geheugen zou kunnen verhogen.
3. Synergie met Speculative Decoding: De paper toont aan dat de voorspellingen die nodig zijn voor deze compressie (de top-k distributie) exact dezelfde zijn als die gebruikt worden bij speculative decoding. Dit betekent dat de berekeningstijd voor de compressie-nabijheid verwaarloosbaar is als het systeem al speculative decoding gebruikt.
4. Nieuwe Richting: Het paper verschuift de focus van "hoe comprimeren we een vector?" naar "hoe comprimeren we een sequentie van vectoren?". Het toont aan dat de Shannon-grens van TurboQuant slechts een ondergrens is voor een subprobleem, en dat de werkelijke grens voor sequentiële compressie aanzienlijk lager ligt.

Kortom, dit paper biedt een theoretisch onderbouwde en architecturale roadmap om de KV-cache-compressie met factoren van honderden tot duizenden te verbeteren door de inherente voorspelbaarheid van taalverdelingen te benutten.