Technische Samenvatting: FibQuant: Universele Vectorquantisatie voor Willekeurig-toegankelijke KV-Cache-compressie

1. Probleemstelling

Inferentie met lange context in autoregressieve transformers wordt steeds meer beperkt door memory-bandbreedte en -capaciteit, voornamelijk als gevolg van de Key-Value (KV)-cache. De cache-grootte schaalt lineair met contextlengte, batchgrootte, aantal lagen en aantal heads, en moet bij elke decodestap worden opgevraagd.

Bestaande compressiemethoden staan voor een kritieke systeembeperking: willekeurige toegang. Een inzetbare cache-codec moet representaties op vaste adressen opslaan, zodat de sleutel of waarde van elk token onafhankelijk kan worden gedecodeerd via eenvoudige adresberekening. Deze beperking sluit variabele-lengte codering en contextafhankelijke representaties uit, en dwingt het gebruik van vaste-rates quantizers af.

Huidige state-of-the-art codecs voor willekeurige toegang, zoals TURBOQUANT, hanteren een "normaliseren–roteren–quantiseren"-benadering:

1. De vectornorm opslaan.
2. Een gedeelde willekeurige orthogonale (Haar-)rotatie toepassen.
3. Elke geroerde coördinaat onafhankelijk quantiseren met behulp van een scalair Lloyd–Max-tabel.

Hoewel deze interface universeel en willekeurig-toegankelijk is, betoogt het artikel dat deze geometrisch suboptimaal is. Zodra een vector is genormaliseerd en via Haar is gerooteerd, vormt een blok van $k$ opeenvolgende coördinaten geen onafhankelijk product van scalair marginaal. In plaats daarvan vormt het een sferisch-Beta-bron op de eenheidsbol. Scalare codecs behandelen coördinaten als onafhankelijk, waardoor de geometrische structuur (radiale en hoekcorrelaties) die inherent is aan het geroteerde blok, wordt genegeerd. Bovendien hebben scalare methoden moeite om effectief te werken onder één bit per coördinaat, wat een "sub-een-bit-gat" creëert waar huidige universele, kalibratievrije codecs falen.

2. Methodologie: FibQuant

FibQuant stelt een universele vaste-rates vectorquantizer voor die dezelfde "normaliseren–roteren"-interface behoudt als scalare methoden, maar de scalare coördinatentabellen vervangt door een gedeelde radiaal-hoekige vectorcodebook.

2.1 De Canonieke Bron

De auteurs bewijzen dat de normaliseren–roteren-interface een universele bronverdeling induceert, ongeacht de oorspronkelijke KV-data-verdeling.

• Normalisatie: Verwijdert schaal.
• Haar-rotatie: Verwijdert oriëntatie.
• Resultaat: De geroteerde eenheidsvector is Haar-uniform verdeeld op de sfeer $S^{d-1}$. Bijgevolg volgt elk blok van $k$ opeenvolgende coördinaten een specifieke sferisch-Beta-dichtheid $f_{d,k}$ op de eenheidsbol $B^k$.
• Implicatie: Een enkel offline codebook kan alle lagen, heads, prompts en modellen bedienen, aangezien de bronverdeling invariant is ten opzichte van de specifieke invoer.

2.2 Constructie van het Codebook

Het FibQuant-codebook is geconstrueerd om de sferisch-Beta-bron te matchen, en combineert drie componenten:

1. Stralen ($r_n$): Gekoppeld aan de radiale dichtheid van de sferisch-Beta-bron met behulp van Bennett–Gersho-companderingsregels. Voor $k=2$ levert dit een gesloten-vormoplossing op die Beta-kwantielstralen omvat.
2. Richtingen ($u_n$): Benaderd met behulp van quasi-uniforme sferische puntsets om uniforme hoekige pakking te waarborgen:
   • $k=2$: Planaire Fibonacci-spiraal (Golden Quantizer).
   • $k=3$: Fibonacci-bol.
   • $k \ge 4$: Roberts–Kronecker-sequenties met lage discrepantie.
3. Verfijning: Een multi-restart Lloyd–Max-algoritme verfijnt de deterministische initialisatie om de gemiddelde kwadratische fout (MSE) te minimaliseren voor de specifieke eindige codebookgrootte $N$.

2.3 Encoderen en Decoderen

• Encoder: Berekent de norm $\nu = \|x\|_2$, roteert de eenheidsvector $\Pi x / \nu$, splitst deze in $d/k$ blokken van grootte $k$, en voert een zoekopdracht naar de dichtstbijzijnde codewoord uit tegen het gedeelde codebook.
• Decoder: Haalt het codewoord op, reconstrueert het blok, concateneert blokken, past de inverse rotatie toe en schaalt met de norm.
• Snelheid: De bitsnelheid is $b = (\log_2 N) / k$ bits per coördinaat. Door $N$ en $k$ te variëren, bereikt FibQuant een dichte snelheidsas, wat operationele punten met fractionele bits en onder één bit mogelijk maakt zonder variabele-lengte-adressering.

3. Belangrijkste Bijdragen

3.1 Identificatie van de Canonieke Bron

Het artikel bewijst (Stelling 1) dat de interface van eerst normeren en vervolgens Haar-rotatie elke niet-nul invoerverdeling afbeeldt op dezelfde sferisch-Beta-marginaal $f_{d,k}$. Dit vestigt dat een gedeeld offline codebook het theoretisch correcte universele object is voor KV-cache-compressie.

3.2 Vectorvoordeel ten opzichte van Scalare Specialisatie

De auteurs bewijzen (Stelling 2) dat de optimale $k$-vectorcode de scalare productspecialisatie (waarbij $k=1$) strikt domineert bij gelijke snelheden. De winst bij hoge snelheden wordt gefactoreerd in twee componenten:

1. Cel-vormingsfactor ($\gamma_{cell}$): Vectorquantisatiecellen (bijvoorbeeld hexagonaal in 2D) zijn efficiënter dan rechthoekige scalare cellen.
2. Dichtheids-matchingsfactor ($\gamma_{dens}$): Het matchen van de gezamenlijke sferisch-Beta-dichtheid is superieur aan het matchen van alleen de scalare marginaal.

3.3 Dichte Snelheidsas

In tegenstelling tot scalare Lloyd–Max-tabellen die beperkt zijn tot geheeltallige bitsnelheden, realiseert FibQuant een dichte verzameling snelheden $b \in (0, \infty)$. Dit maakt bediening mogelijk in het sub-een-bit-regime (bijvoorbeeld $b \approx 0,19$), een regime waar huidige universele codecs voor willekeurige toegang niet meer functioneren.

4. Experimentele Resultaten

4.1 Prestaties van Broncodering

Op de canonieke sferisch-Beta-bron toont FibQuant strikte dominantie over scalair TURBOQUANT bij alle geheeltallige snelheden. Het vult ook de gaten tussen geheeltallige snelheden, en biedt operationele punten die scalare methoden niet kunnen bereiken.

4.2 KV-Cache-compressie (GPT-2 Small)

Geëvalueerd op GPT-2 kleine KV-caches met cosinussimilariteit van de attentie-uitvoer als maatstaf:

• FibQuant traceert een geheugen-trouw-grens van 5× compressie (bij 0,99 similariteit) tot 34,1× compressie (bij 0,946 similariteit).
• Bij hoge compressieverhoudingen (>10×) is FibQuant de enige universele, kalibratievrije methode die trouw behoudt, en presteert het beter dan projectiemethoden met lage rang die per-laag kalibratie vereisen.
• Het artikel merkt op dat volledige vectorcodes ($k=d$) bij extreme compressie beter presteren dan half-vectorcodes ($k=d/2$), omdat ze alle bits besteden aan hoekige pakking, wat direct correleert met attentie-inproducten.

4.3 End-to-End Prestaties van Taalmodellen (TinyLlama-1.1B)

Geëvalueerd op WikiText-103 perplexiteit en HellaSwag-accuraatheid:

• Bij $b=4$ (4× compressie): FibQuant ligt binnen 0,10 perplexiteit van de fp16-basislijn en presteert beter dan scalair TURBOQUANT.
• Bij $b=2$ (8× compressie): FibQuant bereikt 15,88 perplexiteit, wat aanzienlijk beter is dan scalair TURBOQUANT (56,72) en per-token INT-quantisatie (die instort tot 4450,5).
• Fractionele Snelheden: FibQuant biedt intermediate operationele punten (bijvoorbeeld $b=2,5; 3,5$) die niet beschikbaar zijn voor scalare codecs, waardoor het cache-budget eerst kan worden gekozen en de codec vervolgens kan worden afgestemd om hierin te passen.

5. Betekenis en Claims

Het artikel beweert dat de beperking van willekeurige toegang, vaak gezien als een technische beperking, een diepgaand wiskundig gevolg heeft: het dwingt de data in een specifieke sferisch-Beta-geometrie. Door deze canonieke bron te herkennen, herstelt FibQuant de "winsten in vorming en dichtheidsmatching" die scalare quantisatie onbenut laat.

De betekenis ligt in:

1. Universaliteit: Een enkel codebook werkt voor alle modelconfiguraties zonder kalibratie.
2. Bediening onder één bit: Het maakt hoge-trouw compressie mogelijk in regimes waar scalare methoden falen, waardoor het bruikbare geheugenbudget voor inferentie met lange context effectief wordt uitgebreid.
3. Systeemcompatibiliteit: Het behoudt de vaste-adres, willekeurig-toegankelijke interface die vereist is voor het samenvoegen van decompressie met attentie-kernen, waardoor het direct inzetbaar is in bestaande serveerframeworks.

De auteurs concluderen dat willekeurige toegang goede broncodering niet uitsluit; integendeel, het dicteert precies welke bron moet worden gecodeerd.