Adaptive Multi-Objective Tiered Storage Configuration for KV Cache in LLM Service

Dit paper introduceert Kareto, een geoptimaliseerde tool voor het dynamisch beheren van gestapelde opslag voor KV-caches in LLM-diensten, die door het vinden van de Pareto-grens tussen kosten, doorvoer en latentie aanzienlijke verbeteringen boekt ten opzichte van statische configuraties.

De kern

Stel je voor dat je een gigantische, slimme robot (een Large Language Model of LLM) hebt die vragen beantwoordt. Om snel te zijn, onthoudt deze robot wat hij net heeft gezegd, zodat hij niet elke zin opnieuw hoeft uit te rekenen. Dit noemen we de KV-cache.

Het probleem is dat deze robot een enorm geheugen nodig heeft om alles bij te houden. Maar het dure, supersnelle geheugen in de robot (de GPU) is klein en duur. Als je te veel vragen tegelijk krijgt, raakt dit geheugen vol.

De oplossing die veel mensen nu gebruiken, is om het "oude" geheugen naar goedkopere, langzamere plekken te verplaatsen, zoals een harde schijf of het werkgeheugen van de computer. Maar hier zit de valkuil: Hoeveel ruimte moet je aan elk type geheugen geven?

• Geef je te veel aan de dure, snelle plek? Dan ben je veel geld kwijt.
• Geef je te veel aan de goedkope, trage plek? Dan wordt de robot traag en wachten mensen lang op hun antwoord.
• En wat als de vraagstelling verandert? Soms zijn er veel korte vragen, soms lange gesprekken. Een vaste instelling werkt dan niet meer.

Dit is precies waar het paper over gaat. De auteurs hebben Kareto bedacht: een slimme, lerende assistent die voor je uitzoekt wat de perfecte balans is.

Hier is hoe Kareto werkt, vertaald naar alledaagse taal:

1. De "Proefkeuken" (De Simulator)

Stel je voor dat je een kok bent die een nieuw recept wil testen. Je kunt niet zomaar 100 keer een hele maaltijd koken; dat kost te veel tijd en ingrediënten. In plaats daarvan bouw je een virtuele keuken (de simulator).
In deze virtuele keuken kun je duizenden scenario's doornemen: "Wat gebeurt er als ik 500 GB aan snel geheugen heb en 1000 GB aan harde schijf?" of "En als ik 200 GB snel geheugen heb?"
De simulator speelt historische data na (vragen die mensen in het verleden stelden) en zegt precies: "Met deze instelling kost het je €100 en duurt het antwoord 2 seconden. Met die instelling kost het €80 maar duurt het 5 seconden."

2. De "Slimme Zoeker" (Adaptive Pareto Search)

Het vinden van de beste instelling is als het zoeken naar de top van een berg in mist. Je kunt niet elke steen op de berg controleren; dat duurt eeuwen.
Kareto gebruikt een slimme truc: de wet van de afnemende meeropbrengst.
Stel je voor dat je een auto hebt. De eerste 100 km/uur kost weinig brandstof. De volgende 50 km/uur kost al veel meer. Als je probeert van 200 naar 201 km/uur te gaan, kost dat enorm veel energie voor een minieme winst.
Kareto weet dit. Het zoekt eerst grof, en zodra het ziet dat het toevoegen van meer geheugen nauwelijks nog snelheid oplevert, stopt het daar met zoeken. Zo bespaart het enorm veel tijd en vindt het toch de beste plekken op de berg.

3. De "Individuele Bewaartijd" (Group TTL)

Vroeger behandelden systemen alle informatie hetzelfde: "Bewaar alles 10 minuten, en gooi het dan weg."
Maar Kareto kijkt scherper. Het ziet dat sommige informatie (zoals een standaard begroeting of een veelgebruikte code) altijd weer terugkomt. Andere informatie (een eenmalige vraag) komt nooit meer terug.
Kareto gebruikt een boodschappenlijstje (een prefix tree) om te zien welke stukjes informatie populair zijn.

• Populaire stukjes: Deze krijgt een lange "bewaar-tijd" (TTL), zodat ze snel beschikbaar zijn.
• Onduidelijke stukjes: Deze krijgen een korte bewaar-tijd of worden snel verwijderd.
  Het is alsof je in je koelkast alleen de melk en het brood (die je elke dag gebruikt) op een handige plek legt, en de rare kruiden (die je maar één keer per jaar gebruikt) in een hoekje of zelfs niet in huis haalt. Dit maakt het geheugen veel efficiënter.

Wat levert dit op?

Door deze slimme aanpak kunnen bedrijven:

• Sneller zijn: De robot reageert tot wel 58% sneller op vragen.
• Meer doen: Ze kunnen meer vragen tegelijk afhandelen (tot 9% meer).
• Besparen: Ze hoeven minder dure hardware te huren, wat 20% kostenbesparing oplevert.

Kortom: Kareto is de slimme manager die voor je uitzoekt hoeveel snel geheugen en hoeveel goedkoop geheugen je precies nodig hebt, op basis van wat je klanten echt doen. Het voorkomt dat je geld weggooit aan dure hardware die niet gebruikt wordt, of dat je klanten laat wachten omdat je te weinig geheugen hebt.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het paper "Adaptive Multi-Objective Tiered Storage Configuration for KV Cache in LLM Service" in het Nederlands.

Titel: Adaptieve Multi-Doelstellingen Geoptimaliseerde Tiered Storage Configuratie voor KV Cache in LLM-diensten

Auteurs: Xianzhe Zheng et al. (Zhejiang University & Alibaba Group)

---

1. Het Probleem

De inferentie van Large Language Models (LLM) maakt gebruik van KV-cache (Key-Value cache) om herhaalde berekeningen te vermijden tijdens de autoregressieve generatie. Dit "memory-for-computation"-paradigma is essentieel voor lage latentie, maar de cachegrootte groeit lineair met het aantal gelijktijdige verzoeken en de sequentielengte. Dit leidt vaak tot een tekort aan GPU High-Bandwidth Memory (HBM).

Om dit op te lossen, worden tiered storage architecturen gebruikt (GPU HBM -> Host DRAM -> Schijf/SSD). Hoewel bestaande systemen (zoals vLLM, SGLang, Mooncake) cache-vervangingsbeleid (bijv. LRU) hebben geïmplementeerd, missen ze een intelligent mechanisme voor dynamische capaciteitsconfiguratie over deze verschillende opslageniveaus.

De huidige uitdagingen zijn:

• Statische Provisioning: Veel systemen gebruiken vaste configuraties (bijv. 1 TB DRAM per 8 GPU's), wat leidt tot over- of onderprovisioning afhankelijk van de werklast.
• Complexiteit van Trade-offs: Het optimaliseren van de balans tussen kosten, throughput en latentie is niet-lineair en afhankelijk van de werklast.
• Gebrek aan Adaptiviteit: Bestaande oplossingen kunnen niet dynamisch reageren op veranderende werklastpatronen (bijv. pieken in verzoeken, variërende promptlengtes).
• Heterogeniteit: Het behandelen van opslag als een homogene resource negeert de verschillende kosten- en bandbreedteprofielen van GPU, DRAM en schijf.

2. Methodologie: Kareto

Het paper introduceert Kareto (KV-cache Adaptive REsource managemenT Optimizer), een raamwerk dat de configuratie van KV-cache automatiseert door gebruik te maken van simulatie-gedreven Pareto-optimalisatie.

A. Probleemformulering

Het optimalisatieprobleem wordt gedefinieerd als een multi-objective optimalisatie waarbij de volgende doelen worden geminimaliseerd/maximaliseerd:

1. Latentie (bijv. Time To First Token - TTFT).
2. Throughput (tokens per seconde).
3. Kosten (OPEX, inclusief GPU-uurtjes en opslagkosten).

De auteurs tonen aan dat er geen gesloten vorm (analytische formule) bestaat voor deze relatie vanwege:

• Niet-lineaire koppeling: Prestaties hangen complex af van werklast, beleid en capaciteit.
• Discontinuïteiten: Cloud-prijzen hebben "cliff edges" (bijv. prijsstijgingen bij bepaalde IOPS-drempels) en opslagcapaciteit vertoont afnemende meeropbrengsten.

B. High-Fidelity Simulator

Om de Pareto-grens (de set van optimale oplossingen waar je niet op één criterium kunt verbeteren zonder een ander te verslechteren) te vinden, bouwen de auteurs een gedetailleerde eind-tot-eind simulator. Deze simuleert:

• Multi-tier opslaghiërarchie (HBM, DRAM, Remote Storage).
• Niet-lineaire pipeline-interacties (hoe cache-hits GPU-gebruik en I/O-wachttijden beïnvloeden).
• Cloud-prijstarieven en bandbreedte-koppelingen.
• Gedeelde prefixen (radix-tree) en hiërarchische prefetching.

C. Kerncomponenten van Kareto

1. Adaptieve Pareto-Zoekstrategie:

   • In plaats van een brute-force grid search (te duur), gebruikt Kareto een diminishing-return guided pruning methode.
   • Het start met een grof rooster en verfijnt alleen gebieden waar de prestaties of kosten sterk variëren (hoge gradiënt).
   • Het stopt met het verkennen van een dimensie zodra de marginale winst onder een drempelwaarde zakt (lange staart van afnemende meeropbrengsten).
   • Dit reduceert de zoekruimte aanzienlijk terwijl de kwaliteit van de Pareto-grens behouden blijft.

2. ROI-bewuste Groeps-TTL (Time-To-Live) Configuratie:

   • In plaats van één vaste TTL voor alle KV-blokken, analyseert Kareto het prefix-tree-patroon.
   • Het groepeert blokken op basis van hun voorvoegsel (prefix) en wijst per groep een specifieke TTL toe.
   • Blokken met hoge hergebruik (hot) krijgen een langere TTL, terwijl koude blokken sneller worden verwijderd.
   • Dit wordt opgelost als een geconstrueerd optimalisatieprobleem (maximaliseren van hits binnen een kostenbudget) met behulp van SLSQP (Sequential Least Squares Programming).

3. Belangrijkste Bijdragen

• Formulering: Het formaliseren van de trade-off tussen latentie, throughput en kosten als een niet-convex Pareto-optimalisatieprobleem zonder gesloten vorm oplossing.
• Simulator: De ontwikkeling van een hoog-trouwheidsimulator die historische traces kan afspelen om configuraties te evalueren zonder fysieke deploy.
• Zoekalgoritme: Een adaptieve zoekstrategie die de configuratieruimte efficiënt navigeert door afnemende meeropbrengsten te detecteren.
• Finetuning: Een groepsgebaseerde TTL-mechanisme dat cache-efficiëntie verbetert door rekening te houden met specifieke hergebruikspatronen van blokken.
• Implementatie: Een volledig werkend systeem (Kareto) dat wordt geëvalueerd met real-world traces.

4. Resultaten

De evaluatie is uitgevoerd op drie real-world traces (Chatbot, API-calls, Agent-applicaties) en twee schaalscenario's (1 GPU-instance en 4 GPU-instances).

• Vergelijking met Statische Baseline:
  • Vergelijken met een vaste configuratie van 1024 GB DRAM.
  • Throughput: Tot 9,3% verbetering (vooral in compute-beperkte scenario's).
  • Latentie: Tot 58,3% reductie in gemiddelde TTFT.
  • Kosten: Tot 20,2% verlaging in totale kosten door juiste dimensionering van DRAM en schijf.
• Zoekefficiëntie: De adaptieve zoekstrategie vereist aanzienlijk minder evaluaties dan een uniforme grid search, terwijl het een vergelijkbare Pareto-grens bereikt.
• Groeps-TTL: Toont significante verbeteringen in hergebruik (reuse ratio) en kosten voor werklasten met gestructureerde hergebruikspatronen (zoals API-calls), vergeleken met een vaste TTL.
• Simulator Nauwkeurigheid: De simulator toont een hoge nauwkeurigheid met maximale afwijkingen van 19,2% voor TTFT, 6,5% voor throughput en 2,0% voor hitrate ten opzichte van een echte GPU-server.

5. Betekenis en Conclusie

Dit paper biedt een fundamentele verschuiving in het beheer van KV-cache voor LLM-diensten: van statische, handmatig ingestelde capaciteit naar autonome, adaptieve provisionering.

• Kostenefficiëntie: Het stelt cloud-aanbieders en gebruikers in staat om de dure GPU- en DRAM-resources te optimaliseren en goedkopere opslag (schijf) slim in te zetten zonder prestaties te verliezen.
• Scalabiliteit: Het raamwerk is schaalbaar en kan zich aanpassen aan veranderende werklastpatronen (bijv. dag-tot-dag variaties) zonder menselijke ingreep.
• Toekomstvisie: Kareto legt de basis voor volledig autonome LLM-inferentie-systemen die continu de balans zoeken tussen kosten en prestaties, wat essentieel is voor de economische haalbaarheid van LLM's op grote schaal.

Kortom, Kareto lost het probleem op van "hoeveel opslag heb ik nodig en waar moet het staan?" door dit te beantwoorden met data-gedreven, adaptieve optimalisatie in plaats van schattingen.