Recency/Frequency Adaptive KV Caching for Large Language Model Serving

Riepilogo Tecnico: Gestione del KV Cache Adattiva per la Recenza/Frequenza nel Servizio di Large Language Model

Problematica
I sistemi di servizio per Large Language Model (LLM) affrontano sfide significative nella gestione della cache Key-Value (KV) a causa della crescita delle dimensioni dei modelli e della lunghezza del contesto, che mettono sotto sforzo la capacità limitata della memoria GPU. Sebbene il caching dei prefissi e il riutilizzo siano critici per ridurre la computazione ridondante e migliorare il throughput, le strategie di gestione esistenti si basano prevalentemente su politiche di espulsione Least-Recently-Used (LRU). Gli autori sostengono che l'LRU sia insufficiente per i diversi e complessi pattern di accesso presenti nei carichi di lavoro reali degli LLM. Nello specifico, l'LRU non riesce a distinguere tra richieste che esibiscono una forte località temporale (accesso recente) e quelle che agiscono come "hotspot" (accesso frequente tra diversi utenti o sessioni). Questa limitazione porta carichi di lavoro non correlati a svuotare le cache l'uno dell'altro, degradando i tassi di hit e aumentando la latenza, in particolare in scenari come il Question Answering (QA) basato su documenti e le conversazioni multi-turno.

Metodologia
Per affrontare queste limitazioni, il paper propone l'integrazione dell'algoritmo Adaptive Replacement Cache (ARC) nel framework di servizio vLLM. La metodologia introduce una strategia ibrida recenza-frequenza che alloca dinamicamente lo spazio della cache tra blocchi KV acceduti recentemente e blocchi acceduti frequentemente.

I componenti tecnici principali includono:

1. Struttura a Doppia Coda: La cache è logicamente divisa in due code:
   • L1 (Coda di Recenza): Contiene elementi acceduti una sola volta (composta dalla cache fisica $T1$ e dalla ghost cache $B1$).
   • L2 (Coda di Frequenza): Contiene elementi acceduti più volte (composta dalla cache fisica $T2$ e dalla ghost cache $B2$).
   • Gli elementi nella coda di recenza vengono promossi alla coda di frequenza al secondo hit.
2. Ghost Caching: Il sistema utilizza "ghost cache" ($B1$ e $B2$) che memorizzano solo i metadati (non i blocchi KV completi) per gli elementi espulsi. Queste cache tracciano la cronologia delle espulsioni.
   • Se una richiesta manca la cache principale ma colpisce una ghost cache, questa funge da segnale di feedback. Un hit in $B1$ suggerisce che la coda di recenza ($T1$) è troppo piccola, mentre un hit in $B2$ suggerisce che la coda di frequenza ($T2$) necessita di un'espansione.
3. Partizionamento Dinamico: In base agli hit nelle ghost cache, l'algoritmo regola dinamicamente la dimensione delle cache fisiche $T1$ e $T2$ mantenendo una dimensione totale della cache fissa. Ciò consente al sistema di adattarsi ai cambiamenti del carico di lavoro, come l'emergere di nuovi hotspot o cambiamenti nei pattern di attività degli utenti.
4. Integrazione: La strategia opera a livello di blocco KV (ad esempio, 16 token), allineandosi con il meccanismo di paged attention utilizzato nei moderni sistemi di servizio. È progettata per essere priva di parametri e si integra direttamente con il modulo di evizione di vLLM.

Contributi Chiave

• Politica di Espulsione Adattiva: Il paper introduce la prima applicazione di ARC al servizio di LLM, andando oltre le politiche statiche basate sulla recenza verso un approccio ibrido dinamico.
• Adattabilità al Carico di Lavoro: Il metodo dimostra la capacità di bilanciare automaticamente le risorse della cache tra pattern di accesso recenti e frequenti senza tuning manuale.
• Interpretabilità: A differenza degli approcci basati sull'apprendimento che richiedono predittori addestrati, questo metodo offre una chiara interpretabilità su come lo spazio della cache venga allocato in base alla cronologia degli accessi.
• Implementazione Open-Source: Gli autori forniscono un'implementazione open-source integrata con vLLM, disponibile per l'uso della comunità e per ulteriori ricerche.

Risultati Sperimentali
Gli autori hanno valutato il metodo proposto rispetto al baseline standard LRU di vLLM e a una variante a due code statica (DBL) utilizzando due tipi primari di carichi di lavoro:

1. Document QA Sintetico: Utilizzando i dataset QuALITY e WikiQA con campionamento delle richieste distribuito secondo la legge di Zipf.
   • Hit Rate: Migliorato fino al 10,8% (QuALITY) e al 7,8% (WikiQA) rispetto a LRU.
   • Time to First Token (TTFT): Ridotto fino al 12,6% (QuALITY) e al 7,9% (WikiQA).
   • I miglioramenti sono stati più pronunciati con dimensioni di cache minori, dove le decisioni di espulsione sono più frequenti.
2. Conversazione Real-World: Utilizzando una traccia dal Qwen-Bailian Anonymous Dataset (43.058 richieste).
   • Hit Rate: Migliorato dell'1,1%–2,1%.
   • TTFT: Ridotto dell'1,0%–2,0%.
   • Lo studio ha notato che la dimensione adattiva è diventata sempre più vantaggiosa man mano che le dimensioni della cache crescevano, catturando i cambiamenti su larga scala dei carichi di lavoro che le politiche statiche avevano mancato.
3. Inferenza Batch: Gli esperimenti variando le dimensioni dei batch sul dataset QuALITY hanno mostrato che il vantaggio relativo di ARC rispetto a LRU persisteva e aumentava leggermente con batch più grandi, mantenendo una riduzione del TTFT del 5–7%.

Significatività e Rivendicazioni
Il paper sostiene che la gestione adattiva della cache KV sia un meccanismo pratico ed efficace per migliorare le prestazioni del servizio LLM. Catturando i pattern di riutilizzo oltre la semplice recenza, il metodo proposto migliora i tassi di hit della cache e riduce la latenza attraverso diversi carichi di lavoro. Gli autori sottolineano che il loro approccio generalizza bene all'inferenza batch e fornisce una base per futuri sistemi per gestire pattern di accesso complessi e variabili senza l'overhead dei predittori basati sull'addestramento. Il lavoro suggerisce che il partizionamento dinamico delle risorse della cache sia un passo critico verso un deployment più efficiente degli LLM in ambienti di produzione.