Recency/Frequency Adaptive KV Caching for Large Language Model Serving

Technische Samenvatting: Recency/Frequency Adaptieve KV-Caching voor Large Language Model Serving

Probleemstelling
LLM-serving-systemen worden geconfronteerd met aanzienlijke uitdagingen bij het beheren van Key-Value (KV) caches vanwege de groeiende omvang van modellen en contextlengtes, wat de beperkte GPU-geheugencapaciteit onder druk zet. Hoewel prefix-caching en hergebruik cruciaal zijn voor het verminderen van redundante berekeningen en het verbeteren van de doorvoer, vertrouwen bestaande beheerstrategieën voornamelijk op Least-Recently-Used (LRU) verdrijvingsbeleid (eviction policies). De auteurs stellen dat LRU onvoldoende is voor de diverse en complexe toegangspatronen die in real-world LLM-workloads voorkomen. Specifiek faalt LRU in het onderscheiden tussen verzoeken die een sterke temporele lokaliteit vertonen (recente toegang) en verzoeken die fungeren als "hotspots" (frequente toegang over verschillende gebruikers of sessies heen). Deze beperking leidt ertoe dat niet-gerelateerde workloads elkaars caches verdringen, wat resulteert in lagere hit rates en hogere latentie, met name in scenario's zoals document-gebaseerde Question Answering (QA) en multi-turn conversaties.

Methodologie
Om deze beperkingen aan te pakken, stelt het paper voor om het Adaptive Replacement Cache (ARC) algoritme te integreren in het vLLM serving-framework. De methodologie introduceert een hybride recency-frequency strategie die de cacheruimte dynamisch verdeelt tussen recent toegesproken en frequent toegesproken KV-blokken.

De kerncomponenten van de technische methodologie zijn:

1. Dual-Queue Structuur: De cache is logisch gesplitst in twee wachtrijen:
   • L1 (Recency Queue): Bevat items die eenmalig zijn toegesproken (bestaande uit fysieke cache $T1$ en ghost cache $B1$).
   • L2 (Frequency Queue): Bevat items die meerdere keren zijn toegesproken (bestaande uit fysieke cache $T2$ en ghost cache $B2$).
   • Items in de recency-wachtrij worden gepromoveerd naar de frequency-wachtrij bij een tweede hit.
2. Ghost Caching: Het systeem maakt gebruik van "ghost caches" ($B1$ en $B2$) die alleen metadata (geen volledige KV-blokken) opslaan voor verdreven items. Deze caches houden de geschiedenis van verdrijvingen bij.
   • Als een verzoek een miss in de hoofdcache heeft maar een hit in een ghost cache, dient dit als een feedbacksignaal. Een hit in $B1$ suggereert dat de recency-wachtrij ($T1$) te klein is, terwijl een hit in $B2$ suggereert dat de frequency-wachtrij ($T2$) moet worden uitgebreid.
3. Dynamische Partitionering: Op basis van ghost cache hits past het algoritme de grootte van de fysieke caches $T1$ en $T2$ dynamisch aan, terwijl de totale cachegrootte constant blijft. Dit stelt het systeem in staat om zich aan te passen aan verschuivingen in de workload, zoals het ontstaan van nieuwe hotspots of veranderingen in gebruikersactiviteitspatronen.
4. Integratie: De strategie opereert op KV-blokniveau (bijv. 16 tokens), wat aansluit bij het paged attention-mechanisme dat wordt gebruikt in moderne serving-systemen. Het is ontworpen als parameter-vrij en integreert direct met de vLLM evictor-module.

Belangrijkste Bijdragen

• Adaptief Verdrijvingsbeleid: Het paper introduceert de eerste toepassing van ARC op LLM-serving, waarbij de stap wordt gezet van statische recency-gebaseerde beleid naar een dynamische hybride benadering.
• Workload Aanpassingsvermogen: De methode demonstreert het vermogen om automatisch cachebronnen te balanceren tussen recente en frequente toegangs patronen zonder handmatige afstemming.
• Interpreteerbaarheid: In tegen tegenstelling tot learning-based benaderingen die training van voorspellers vereisen, biedt deze methode een duidelijke interpreteerbaarheid met betrekking tot hoe de cacheruimte wordt toegewezen op basis van de toegangsgeschiedenis.
• Open-Source Implementatie: De auteurs bieden een open-source implementatie die geïntegreerd is met vLLM, beschikbaar voor gemeenschapsgebruik en verder onderzoek.

Experimentele Resultaten
De auteurs hebben de voorgestelde methode geëvalueerd tegenover de standaard vLLM LRU-baseline en een statische twee-wachtrij variant (DBL) met behulp van twee primaire workload-typen:

1. Synthetische Document QA: Gebruikmakend van de QuALITY en WikiQA datasets met Zipf-verdeelde request sampling.
   • Hit Rate: Verbeterd met maximaal 10,8% (QuALITY) en 7,8% (WikiQA) vergeleken met LRU.
   • Time to First Token (TTFT): Verminderd met maximaal 12,6% (QuALITY) en 7,9% (WikiQA).
   • De verbeteringen waren het meest uitgesproken bij kleinere cachegroottes waar verdrijkingsbeslissingen frequenter voorkomen.
2. Real-World Conversatie: Gebruikmakend van een trace uit de Qwen-Bailian Anonymous Dataset (43.058 verzoeken).
   • Hit Rate: Verbeterd met 1,1%–2,1%.
   • TTFT: Verminderd met 1,0%–2,0%.
   • De studie merkte op dat adaptieve dimensionering steeds voordeliger werd naarmate de cachegroottes groter werden, waardoor langdurige verschuivingen in de workload werden opgevangen die statische beleid misten.
3. Batch Inference: Experimenten waarbij de batch sizes varieerden op de QuALITY-dataset lieten zien dat het relatieve voordeel van ARC ten opzichte van LRU standhield en licht toenam bij grotere batch sizes, met een behoud van een 5–7% reductie in TTFT.

Betekenis en Claims
Het paper claimt dat adaptief KV-cachebeheer een praktische en effectieve methode is voor het verbeteren van de prestaties van LLM-serving. Door hergebruikpatronen te vangen die verder gaan dan eenvoudige recency, verbetert de voorgestelde methode de cache hit rates en vermindert het de latentie over diverse workloads. De auteurs benadrukken dat hun benadering goed generaliseert naar batch inference en een fundament biedt voor toekomstige systemen om complexe, verschuivende toegangspatronen te hanteren zonder de overhead van training-gebaseerde voorspellers. Het werk suggereert dat de dynamische partitionering van cachebronnen een cruciale stap is naar een efficiëntere LLM-implementatie in productieomgevingen.