From Exact Hits to Close Enough: Semantic Caching for LLM Embeddings

Dit paper onderzoekt semantische caching voor LLM-embeddings, bewijst dat het vinden van een optimale offline beleid NP-moeilijk is, en stelt polynomiale heuristieken en online beleidsregels voor die de prestaties verbeteren ten opzichte van bestaande methoden.

De kern

Stel je voor dat je een superintelligente assistent hebt (een Large Language Model of LLM) die je vragen beantwoordt. Deze assistent is briljant, maar hij is ook traag, duur en verbruikt veel energie, alsof hij een enorme vrachtwagen is die elke keer opnieuw moet worden opgestart, zelfs als je hem alleen vraagt: "Wat is de hoofdstad van Frankrijk?" en een seconde later: "Hoe heet de hoofdstad van Frankrijk?"

Om dit op te lossen, gebruiken we een cache (een geheugen). Het idee is simpel: als de assistent het antwoord al eens heeft berekend, slaan we het op. De volgende keer dat je iets vraagt, kijken we in ons geheugen. Als het antwoord er al staat, geven we het direct terug. Snel en goedkoop.

Maar hier zit de twist: mensen zijn niet als computers. We zeggen niet altijd precies hetzelfde.

• Vraag 1: "Wat is de hoofdstad van Frankrijk?"
• Vraag 2: "Hoe heet de stad waar de Eiffeltoren staat?"

Voor een computer zijn dit twee totaal verschillende zinnen. Voor een mens (en voor moderne AI) zijn het echter bijna hetzelfde. Dit noemen we semantisch caching: we zoeken niet op exacte tekst, maar op de betekenis.

Het Probleem: De "Niet-Exacte" Puzzel

In het verleden was het makkelijk: als je vraag exact leek op een opgeslagen vraag, was het een "hit". Nu, met AI, is het moeilijker. Als je vraag "niet exact" maar wel "vrijwel hetzelfde" is, is het ook een hit.

Dit breekt de oude regels. Stel je een bibliotheek voor waar je boeken mag terugleggen als ze op elkaar lijken. Als je een boek over "honden" teruglegt, mag je misschien ook een boek over "puppy's" erbij doen, of zelfs een boek over "viervoeters". Maar wat als je bibliotheek vol zit? Welk boek gooi je eruit om ruimte te maken?

• Gooi je het boek met de meeste lezers eruit? (Frequentie)
• Gooi je het boek eruit dat het langst niet is gelezen? (Recency)
• Of probeer je een boek te vinden dat de meeste andere boeken in de buurt dekt?

De auteurs van dit paper ontdekten dat de oude, simpele regels hier niet meer werken. Ze bewezen zelfs dat het vinden van de perfecte oplossing om te beslissen welk boek je eruit gooit, wiskundig gezien onmogelijk is om snel te berekenen (het is "NP-hard"). Het is alsof je probeert de perfecte route te vinden door een doolhof van oneindig veel paden, terwijl je tegelijkertijd moet rennen.

De Oplossingen: Slimme Strategieën

Omdat de perfecte oplossing te moeilijk is, hebben de auteurs een paar slimme strategieën (heuristieken) bedacht:

1. De "Cluster"-methode (CRVB):
   Stel je voor dat je alle boeken over "honden", "katten" en "paarden" in één grote stapel legt. Als je een vraag over "honden" krijgt, kijk je naar die hele stapel. Dit werkt goed, maar in de echte wereld overlappen de categorieën elkaar (een "hond" is ook een "viervoeter"). Deze methode kan hierdoor soms in de war raken.

2. De "Volume"-methode (FGRVB):
   Deze strategie probeert te voorspellen: "Welk boek in mijn kast dekt de meeste toekomstige vragen?" Het is alsof je een boek kiest dat niet alleen populair is, maar ook de meeste andere boeken in de buurt "vertegenwoordigt". Dit werkt heel goed, maar vereist dat je de toekomst kunt zien (wat we niet kunnen).

3. De "SphereLFU" (De Sterke Online Kiezer):
   Dit is de echte winnaar in hun experimenten. Stel je voor dat je een vloeibare substantie (zoals honing) hebt. Als iemand een vraag stelt, valt er een druppel honing op de plek in je geheugen die daar het dichtst bij ligt. Maar in plaats van alleen die ene plek te vullen, verspreidt de honing zich zachtjes naar de buren.

   • Hoe het werkt: Als iemand vraagt naar "honden", krijgen niet alleen de boeken over honden een punt, maar ook de boeken over "puppy's" en "viervoeters" krijgen een klein beetje credit.
   • Het resultaat: Het systeem leert welke gebieden in de "betekenis-ruimte" het drukst bezocht worden. Het houdt de boeken vast die in het midden van die drukke gebieden liggen, in plaats van alleen de boeken die exact op de vraag lijken.

Wat hebben ze ontdekt?

Ze hebben dit getest met duizenden echte vragen uit verschillende bronnen (zoals StackOverflow, Wikipedia en chatgesprekken).

• Frequentie is koning: Net als in een echte bibliotheek, zijn de boeken die het vaakst worden gelezen het belangrijkst om te houden.
• De "SphereLFU" is de beste: De methode die de "honing" verspreidt (soft updates) werkt beter dan de oude methoden. Het zorgt ervoor dat je niet alleen de exacte match hebt, maar ook de beste match. De antwoorden zijn semantisch dichter bij wat de gebruiker bedoelde.
• Er is nog veel ruimte voor verbetering: De auteurs laten zien dat als we de toekomst zouden kunnen voorspellen (de "offline" methoden), we nog veel efficiënter zouden kunnen zijn. Maar voor nu is "SphereLFU" de slimste manier om dit in het echt te doen.

Waarom is dit belangrijk?

Voor de gebruiker betekent dit:

• Snellere antwoorden: Je hoeft niet te wachten tot de AI opnieuw nadenkt.
• Minder kosten: Minder rekenkracht nodig.
• Beter resultaat: De AI geeft een antwoord dat beter past bij wat je bedoelde, zelfs als je het niet perfect verwoordde.

Kortom: Dit paper leert ons hoe we een slimme, snelle en goedkope "herinneringsmachine" kunnen bouwen voor AI, die niet alleen luistert naar wat je zegt, maar ook begrijpt wat je bedoelt.

Technische samenvatting

1. Probleemstelling

De snelle adoptie van Large Language Models (LLM's) heeft geleid tot een enorme vraag naar snellere responsen en lagere kosten. LLM's zijn echter computatierijk en verbruiken veel energie, geheugen en bandbreedte. Caching is een bekende techniek om dit te verminderen, maar traditionele caching werkt op basis van exacte matches (dezelfde string of hash).

Bij LLM's worden queries echter omgezet in embeddings (hoogdimensionale vectoren) die de semantische betekenis vastleggen. Twee queries kunnen semantisch identiek zijn (en dus hetzelfde antwoord vereisen) maar syntactisch verschillend zijn. Dit vereist semantische caching, waarbij een query een "hit" is als deze binnen een bepaalde afstand ($D_{thresh}$) ligt van een reeds opgeslagen vector.

De kernproblemen die dit paper adresseert zijn:

• Breuk met klassieke aannames: Bestaande cache-beheerpolitieken (zoals LRU, LFU) zijn ontworpen voor exacte matches en gaan uit van discrete items. In een semantische ruimte is er geen duidelijke "volgende keer" voor een specifiek item, omdat een vector meerdere toekomstige queries kan dekken.
• Optimalisatiecomplexiteit: Het is onduidelijk welke vervangingsstrategie (eviction policy) optimaal is voor semantische caching. Bestaande oplossingen gebruiken vaak naïeve benaderingen (zoals LRU of LFU) zonder rekening te houden met de overdekkingsredundantie van semantische vectoren.
• Theoretische limieten: Het is niet bekend of de klassieke optimale offline politiek (Belady's OPT) nog wel geldig is in een semantische context.

2. Methodologie

Het paper volgt een systematische aanpak die theoretische analyse combineert met uitgebreide experimentele evaluatie.

Theoretische Analyse

• Complexiteit van VOPT: De auteurs definiëren VOPT (Voorbeeld van een optimale offline politiek voor semantische caching) als een beleid dat de maximale hit-rate bereikt voor een gegeven workload. Ze bewijzen dat het berekenen van VOPT NP-hard is. Dit wordt gedaan door een reductie van het Maximum Coverage Problem (MCP).
  • In tegenstelling tot Belady's OPT (dat perfect is voor exacte matches), faalt OPT in semantische caching omdat het niet rekening houdt met het feit dat één vector meerdere toekomstige queries kan dekken.
• Offline Heuristieken (Clairvoyant): Omdat VOPT onberekenbaar is voor realistische workloads, worden drie polynomiale tijd-heuristieken voorgesteld die gebruikmaken van volledige kennis van de toekomstige workload (clairvoyant):
  1. CRVB (Clustered Relaxed Vector Belady): Groepeert semantisch identieke vectoren in clusters en past OPT toe op cluster-ID's. Dit is een benadering die faalt bij overlappende clusters.
  2. FGRVB (Frequency Greedy Relaxed Vector Belady): Een "greedy" strategie die probeert de totale "volume" van toekomstige hits te maximaliseren. Het verwijdert vectoren die de minste unieke toekomstige queries dekken. Dit benadert het MCP-probleem.
  3. RGRVB (Recency Greedy Relaxed Vector Belady): Richt zich op het maximaliseren van de volgende hit in plaats van het totale volume. Dit is effectiever voor bursty workloads.

Online Politieken

De auteurs evalueren bestaande online politieken (LRU, LFU, ARC, etc.) aangepast voor semantische caching, en introduceren nieuwe varianten:

• SphereLFU: Een nieuwe, opmerkelijke politiek die een online Kernel Density Estimation (KDE) benadert. In plaats van een discrete teller te verhogen voor de exacte hit, wordt "gebruiksmassa" probabilistisch verdeeld over alle naburige vectoren binnen de drempelafstand. Dit creëert een gladde dichtheidskaart van de query-distributie.
• Andere varianten: MissLFU, ClusterLFU, DistanceLFU, Surprisal en SurprisalLFU (die taalstatistieken gebruikt).

Experimenten

• Datasets: Evaluatie op 9 diverse real-world datasets (o.a. MsMarco, WildChat, Natural Questions, StackOverflow, MMLU) met in totaal 100k queries per dataset.
• Embeddings: Gebruik van all-MiniLM-L6-v2 (384 dimensies) met L2-normalisatie.
• Metingen: Hit-rate (aantal hits) en Mean Hit Distance (MHD, een maat voor semantische nauwkeurigheid/kwaliteit van de hit).

3. Belangrijkste Bijdragen

1. Theoretisch Bewijs: Het bewijzen dat het vinden van de optimale offline oplossing voor semantische caching (VOPT) NP-hard is, en dat de klassieke Belady's OPT niet langer optimaal is in deze context.
2. Nieuwe Heuristieken: Introductie van drie offline heuristieken (CRVB, FGRVB, RGRVB) die dienen als een theoretische bovengrens (oracle) voor prestaties.
3. SphereLFU: De ontwikkeling van een nieuwe online politiek die semantische nauwkeurigheid maximaliseert door soft-frequency updates en probabilistische credit-toewijzing, in plaats van harde tellers.
4. Uitgebreide Evaluatie: Een uitgebreide vergelijking van offline heuristieken versus online politieken over negen datasets, wat inzicht geeft in de prestaties onder verschillende werklasten (bijv. frequentie-gedreven vs. recency-gedreven).

4. Resultaten

• Offline vs. Online: De offline heuristieken (vooral FGRVB) presteren significant beter dan alle online politieken. Dit bevestigt dat er nog veel ruimte is voor innovatie in online caching voor LLM's, aangezien toekomstkennis een groot voordeel biedt.
• Frequentie is Koning: Voor de meeste werklasten (die vaak een Zipf-verdeling volgen) presteren frequentie-gebaseerde politieken (LFU-varianten) beter dan recentie-gebaseerde politieken (LRU).
• SphereLFU Superioriteit:
  • Hit-rate: SphereLFU presteert consistent hoog en concurreert met de beste frequentie-gebaseerde baselines.
  • Semantische Nauwkeurigheid (MHD): SphereLFU behaalt de laagste Mean Hit Distance op 7 van de 9 datasets. Dit betekent dat de gevonden hits semantisch dichter bij de oorspronkelijke query liggen dan bij andere methoden.
  • Reden: Door vectoren in het centrum van dichte semantische clusters te behouden (in plaats van aan de randen, zoals sommige offline methoden doen die puur op volume mikken), behoudt SphereLFU de context-integriteit beter.
• Workload-afhankelijkheid:
  • Op "harde" datasets met lange staarten (zoals StackOverflow) blijft SphereLFU de beste online kandidaat.
  • Op datasets met veel tijdslokaliteit (zoals WildChat) kunnen LRU of tijd-afnemende dichtheid concurreren.
  • Op datasets met veel "one-hit wonders" (zoals MMLU) presteren frequentie-gebaseerde methoden minder goed, maar SphereLFU blijft robuust door zijn probabilistische aard.

5. Betekenis en Impact

Dit paper is van groot belang voor de efficiëntie van LLM-systemen:

• Kostenreductie: Door effectiever te cachen, kunnen systemen minder inferenties uitvoeren, wat leidt tot lagere rekenkosten, minder energieverbruik en minder bandbreedtegebruik.
• Verbeterde Gebruikerservaring: Lagere latentie door het vermijden van dure LLM-inferenties voor semantisch vergelijkbare vragen.
• Kwaliteit van Antwoorden: De bevinding dat SphereLFU niet alleen meer hits genereert, maar ook betere hits (kleinere semantische afstand), is cruciaal voor RAG-systemen (Retrieval-Augmented Generation) en KV-caches, waar de kwaliteit van de prompt/context direct de outputkwaliteit van het model beïnvloedt.
• Richting voor Toekomstig Onderzoek: Het paper toont aan dat er een aanzienlijke kloof bestaat tussen de beste online politieken en de theoretische limiet (VOPT), wat een sterke motivatie biedt voor verder onderzoek in adaptieve en leer-gebaseerde caching voor semantische ruimtes.

Kortom, het paper verschuift het paradigma van "exact match caching" naar "semantische caching" en biedt zowel de theoretische onderbouwing als praktische, superieure algoritmen om dit te realiseren.