Recency/Frequency Adaptive KV Caching for Large Language Model Serving

Technisches Resümee: Recency/Frequency Adaptive KV-Caching für das Serving von Large Language Models

Problemstellung
Serving-Systeme für Large Language Models (LLMs) stehen vor erheblichen Herausforderungen bei der Verwaltung von Key-Value (KV)-Caches aufgrund der wachsenden Modellgröße und der Kontextlängen, was die begrenzte GPU-Speicherkapazität stark beansprucht. Während Prefix-Caching und Wiederverwendung entscheidend sind, um redundante Berechnungen zu reduzieren und den Durchsatz zu verbessern, verlassen sich bestehende Verwaltungsstrategien überwiegend auf Least-Recently-Used (LRU)-Eviktionsrichtlinien. Die Autoren argumentieren, dass LRU unzureichend ist, um die vielfältigen und komplexen Zugriffsmuster realer LLM-Workloads abzubilden. Speziell versagt LRU dabei, zwischen Anfragen zu unterscheiden, die eine starke zeitliche Lokalität (kürzlicher Zugriff) aufweisen, und solchen, die als „Hotspots“ fungieren (häufiger Zugriff über verschiedene Nutzer oder Sitzungen hinweg). Diese Einschränkung führt dazu, dass nicht verwandte Workloads gegenseitig deren Caches verdrängen, was die Trefferraten senkt und die Latenz erhöht, insbesondere in Szenarien wie dokumentenbasiertem Question Answering (QA) und Multi-Turn-Konversationen.

Methodik
Um diese Einschränkungen zu adressieren, schlägt das Paper die Integration des Adaptive Replacement Cache (ARC) Algorithmus in das vLLM Serving-Framework vor. Die Methodik führt eine hybride Recency-Frequency-Strategie ein, die den Cache-Speicherplatz dynamisch zwischen kürzlich aufgerufenen und häufig aufgerufenen KV-Blöcken aufteilt.

Die zentralen technischen Komponenten umfassen:

1. Dual-Queue-Struktur: Der Cache wird logisch in zwei Warteschlangen unterteilt:
   • L1 (Recency Queue): Enthält Elemente, die einmal aufgerufen wurden (bestehend aus physischem Cache $T1$ und Ghost-Cache $B1$).
   • L2 (Frequency Queue): Enthält Elemente, die mehrfach aufgerufen wurden (bestehend aus physischem Cache $T2$ und Ghost-Cache $B2$).
   • Elemente in der Recency-Queue werden beim zweiten Treffer in die Frequency-Queue befördert.
2. Ghost Caching: Das System nutzt „Ghost-Caches“ ($B1$ und $B2$), die nur Metadaten (keine vollständigen KV-Blöcke) für eviktierte Elemente speichern. Diese Caches verfolgen die Historie der Eviktionen.
   • Wenn eine Anfrage den Hauptcache verfehlt (Miss), aber im Ghost-Cache einen Treffer (Hit) erzielt, dient dies als Feedback-Signal. Ein Treffer in $B1$ deutet darauf hin, dass die Recency-Queue ($T1$) zu klein ist, während ein Treffer in $B2$ darauf hindeutet, dass die Frequency-Queue ($T2$) erweitert werden muss.
3. Dynamische Partitionierung: Basierend auf den Ghost-Cache-Treffern passt der Algorithmus die Größe der physischen Caches $T1$ und $T2$ dynamisch an, während er eine feste Gesamt-Cache-Größe beibehält. Dies ermöglicht es dem System, sich an Verschiebungen in den Workloads anzupassen, wie etwa das Entstehen neuer Hotspots oder Änderungen im Nutzerverhalten.
4. Integration: Die Strategie operiert auf KV-Block-Ebene (z. B. 16 Token) und richtet sich an den Paged-Attention-Mechanismus, der in modernen Serving-Systemen verwendet wird. Sie ist als parameterfrei konzipiert und lässt sich direkt in das vLLM-Evictor-Modul integrieren.

Wesentliche Beiträge

• Adaptive Eviktionsrichtlinie: Das Paper stellt die erste Anwendung von ARC im LLM-Serving vor und bewegt sich damit über statische, auf Recency basierende Richtlinien hin zu einem dynamischen Hybrid-Ansatz.
• Workload-Adaptivität: Die Methode demonstriert die Fähigkeit, Cache-Ressourcen automatisch zwischen aktuellen und häufigen Zugriffsmustern auszubalancieren, ohne manuelles Tuning.
• Interpretierbarkeit: Im Gegensatz zu lernbasierten Ansätzen, die trainierte Prädiktoren erfordern, bietet diese Methode eine klare Interpretierbarkeit hinsichtlich der Frage, wie der Cache-Speicherplatz basierend auf der Zugriffshistorie zugewiesen wird.
• Open-Source-Implementierung: Die Autoren stellen eine Open-Source-Implementierung bereit, die in vLLM integriert und für die Community-Nutzung sowie weitere Forschung verfügbar ist.

Experimentelle Ergebnisse
Die Autoren evaluierten die vorgeschlagene Methode gegenüber der Standard-vLLM-LRU-Baseline und einer statischen Zwei-Warteschlangen-Variante (DBL) unter Verwendung von zwei primären Workload-Typen:

1. Synthetisches Dokument-QA: Verwendung der Datensätze QuALITY und WikiQA mit Zipf-verteilter Request-Sampling-Methode.
   • Trefferrate (Hit Rate): Verbesserte Rate um bis zu 10,8 % (QuALITY) und 7,8 % (WikiQA) im Vergleich zu LRU.
   • Time to First Token (TTFT): Reduktion um bis zu 12,6 % (QuALITY) und 7,9 % (WikiQA).
   • Die Verbesserungen waren am deutlichsten bei kleineren Cache-Größen, bei denen Eviktionsentscheidungen häufiger getroffen werden müssen.
2. Reale Konversationen: Verwendung eines Traces aus dem Qwen-Bailian Anonymous Dataset (43.058 Anfragen).
   • Trefferrate (Hit Rate): Verbesserung um 1,1 % – 2,1 %.
   • TTFT: Reduktion um 1,0 % – 2,0 %.
   • Die Studie stellte fest, dass die adaptive Größenanpassung mit zunehmender Cache-Größe immer vorteilhafter wurde, da sie langfristige Verschiebungen in den Workloads erfasste, die statische Richtlinien übersehen hatten.
3. Batch-Inferenz: Experimente zur Variation der Batch-Größen auf dem QuALITY-Datensatz zeigten, dass der relative Vorteil von ARC gegenüber LRU bestehen blieb und mit größeren Batch-Größen leicht anstieg, wobei eine Reduktion der TTFT um 5–7 % beibehalten wurde.

Bedeutung und Ansprüche
Das Paper behauptet, dass adaptives KV-Cache-Management ein praktischer und effektiver Mechanismus zur Steigerung der Performance beim LLM-Serving ist. Durch die Erfassung von Wiederverwendungsmustern, die über einfache Recency hinausgehen, verbessert die vorgeschlagene Methode die Cache-Trefferraten und reduziert die Latenz über verschiedene Workloads hinweg. Die Autoren betonen, dass ihr Ansatz gut auf Batch-Inferenz generalisiert und eine Grundlage für zukünftige Systeme bildet, um komplexe, sich ändernde Zugriffsmuster ohne den Overhead von trainingsbasierten Prädiktoren zu handhaben. Die Arbeit legt nahe, dass die dynamische Partitionierung von Cache-Ressourcen ein kritischer Schritt zu einem effizienteren LLM-Deployment in Produktionsumgebungen ist.