SemantiCache: Efficient KV Cache Compression via Semantic Chunking and Clustered Merging

Probleemstelling

Grote Taalmodellen (LLM's) kampen met hoge kosten voor autoregressieve inferentie, vooral in scenario's met lange contexten. De belangrijkste bottleneck is de Key-Value (KV) cache, die de attention-keys en -values van alle voorgaande tokens opslaat. Deze cache groeit lineair met de invoersequentie, wat leidt tot:

1. Een onaanvaardbaar groot geheugengebruik (GPU-ram).
2. Een aanzienlijke toename van de inferentielatentie.

Bestaande compressietechnieken vallen in twee categorieën:

• Eviction-based: Verwijdert tokens die als minder "kritiek" worden beschouwd. Dit leidt vaak tot onherstelbaar verlies van informatie en prestatiedaling.
• Merging-based: Voegt tokens samen in plaats van ze te verwijderen.

De kernprobleem: Zowel eviction- als merging-methoden opereren vaak op discrete tokens of willekeurige, niet-semantische blokken. Dit veroorzaakt semantische fragmentatie: samenhangende taalkundige eenheden (zoals zinnen, clausules of zinsdelen) worden doorbroken. Hierdoor gaat cruciale semantische informatie verloren, wat de prestaties van het model verslechtert.

Methodologie: SemantiCache

SemantiCache is een nieuw compressieframework dat de compressieprocessen afstemt op de semantische hiërarchie van de taal, geïnspireerd door de menselijke cognitieve strategie om lange teksten te onthouden. Het framework bestaat uit drie fasen:

1. Semantische Chunking (Semantic Chunking)

In plaats van vaste blokken te gebruiken, wordt de KV-cache opgesplitst in semantisch samenhangende stukken ("chunks") op basis van natuurlijke taalafbakeningen (delimiters).

• Delimiters: Tokens zoals leestekens (., ,, ?, !, ;, :) en witruimte worden gedefinieerd als grenzen.
• Behoud: De KV-states van deze delimiters worden ongewijzigd bewaard als structurele ankers.
• Resultaat: De cache wordt omgezet in een alternerende reeks van semantische chunks en delimiters, waardoor intacte taaleenheden behouden blijven.

2. Gelijkheidsclustering (Similarity Clustering)

Binnen elke chunk worden semantisch gerelateerde tokens gegroepeerd.

• Metriek: Semantische gelijkenis wordt gemeten aan de hand van de Key-vectoren (die rijke semantische informatie bevatten) via puntproducten (cosine similarity).
• Algoritme (GSC): Er wordt een Greedy Seed-Based Clustering (GSC) algoritme gebruikt. Dit is een efficiënt, één-pass algoritme:
  • Een ontoegewezen token fungeert als "zaad" (seed) voor een nieuw cluster.
  • Dit zaad absorbeert greedy alle volgende ontoegewezen tokens waarvan de Key-vector een gelijkenis boven een drempelwaarde ($\tau$) heeft.
  • Dit proces herhaalt zich totdat alle tokens in de chunk zijn toegewezen aan een cluster.

3. Geclusterd Samenvoegen (Clustered Merging)

De tokens binnen een cluster worden samengevoegd tot één compacte "semantische kern" (semantic core).

• Representatie: Voor elke cluster wordt een representatieve Key- en Value-vector berekend via mean-pooling.
• Proportionele Attention: Omdat het samenvoegen van tokens de attention-bijdrage zou kunnen verdunnen, wordt een Proportional Attention-mechanisme toegepast.
  • De attention-scores worden gewogen met de grootte van het cluster ($s$).
  • Wiskundig wordt $\log(s)$ toegevoegd aan de pre-softmax logits. Dit zorgt ervoor dat de bijdrage van een samengevoegde token evenredig is met het aantal oorspronkelijke tokens, waardoor informatieverlies wordt voorkomen.

Belangrijkste Bijdragen

1. Identificatie van Semantische Fragmentatie: Het paper benadrukt en lost het probleem op dat bestaande methoden coherentie in de taal verbreken.
2. Nieuw Framework: Een compressiestrategie die de menselijke cognitieve aanpak (hiërarchische decompositie) nabootst.
3. Efficiënt Algoritme: Ontwikkeling van het lichtgewicht GSC-algoritme voor snelle semantische aggregatie.
4. Proportionele Attention: Een mechanisme om het verdunnen van informatie bij het samenvoegen van tokens te compenseren.

Resultaten

De methode is getest op diverse benchmarks (LongBench, Needle-in-a-Haystack) met modellen zoals Llama-3-8B en Mistral-7B.

• Prestaties (Accuracy): SemantiCache presteert consistent beter dan state-of-the-art eviction- en merging-methoden (zoals StreamingLLM, H2O, SnapKV, CaM, D2O).
  • Op LongBench behaalde het de hoogste scores bij verschillende cache-budgetten (bijv. 20%, 35%, 50% van de originele grootte).
  • Bij de "Needle-in-a-Haystack" test (retrieval van specifieke zinnen in lange documenten) behaalde het de beste resultaten, zelfs bij hoge compressie.
• Efficiëntie:
  • Snelheid: De decode-fase van de inferentie wordt versneld met tot 2,61x (gemeten via Time Per Output Token - TPOT) ten opzichte van de volledige KV-cache.
  • Geheugen: Het reduceert het geheugengebruik aanzienlijk, wat leidt tot een efficiënter gebruik van GPU-resources.
• Ablatie-studies:
  • Semantische chunking bleek cruciaal; zonder chunking (globale clustering) of met vaste blokken (64 tokens) daalden de prestaties aanzienlijk.
  • De drempelwaarde $\tau$ biedt een afweging tussen compressiegraad en nauwkeurigheid (lagere $\tau$ = hogere compressie, maar lagere nauwkeurigheid).

Significantie

SemantiCache biedt een fundamentele verbetering in de efficiënte inferentie van LLM's voor lange contexten. Door de compressie te koppelen aan de natuurlijke structuur van de taal in plaats van willekeurige tokens, lost het het dilemma op tussen geheugenefficiëntie en modelkwaliteit. Het bewijst dat het behoud van semantische integriteit essentieel is om hoge compressieratio's te bereiken zonder de kwaliteit van de gegenereerde tekst te laten inzakken. Dit maakt het mogelijk om LLM's op beperkte hardware te draaien met lange contextvensters, zonder in te leveren op de nauwkeurigheid.