Recency/Frequency Adaptive KV Caching for Large Language Model Serving

Résumé Technique : Mise en cache KV adaptative à récence/fréquence pour le service de Grands Modèles de Langage

Énoncé du Problème
Les systèmes de service de Grands Modèles de Langage (LLM) sont confrontés à des défis importants dans la gestion du cache Clé-Valeur (KV) en raison de la taille croissante des modèles et des longueurs de contexte, ce qui sollicite fortement la capacité limitée de la mémoire GPU. Bien que le cache de préfixe et la réutilisation soient essentiels pour réduire les calculs redondants et améliorer le débit, les stratégies de gestion existantes reposent principalement sur des politiques d'éviction de type LRU (Least-Recently-Used / Moins Récemment Utilisé). Les auteurs soutiennent que le LRU est insuffisant pour les modèles d'accès divers et complexes rencontrés dans les charges de travail réelles de LLM. Plus précisément, le LRU ne parvient pas à distinguer les requêtes qui présentent une forte localité temporelle (accès récent) de celles qui agissent comme des « points chauds » (accès fréquents à travers différents utilisateurs ou sessions). Cette limitation conduit des charges de travail non liées à se supprimer mutuellement les caches, dégradant ainsi les taux de succès (hit rates) et augmentant la latence, particulièrement dans des scénarios comme le Questionnement/Réponse (QA) basé sur des documents et les conversations multi-tours.

Méthodologie
Pour remédier à ces limitations, l'article propose d'intégrer l'algorithme Adaptive Replacement Cache (ARC) dans le framework de service vLLM. La méthodologie introduit une stratégie hybride de récence-fréquence qui alloue dynamiquement l'espace de cache entre les blocs KV récemment accédés et ceux fréquemment accédés.

Les composants techniques clés incluent :

1. Structure à double file d'attente : Le cache est logiquement divisé en deux files :
   • L1 (File de récence) : Contient les éléments accédés une seule fois (composée du cache physique $T1$ et du cache fantôme $B1$).
   • L2 (File de fréquence) : Contient les éléments accédés plusieurs fois (composée du cache physique $T2$ et du cache fantôme $B2$).
   • Les éléments de la file de récence sont promus vers la file de fréquence lors d'un second succès d'accès (hit).
2. Mise en cache fantôme (Ghost Caching) : Le système utilise des « caches fantômes » ($B1$ et $B2$) qui stockent uniquement les métadonnées (et non les blocs KV complets) pour les éléments évincés. Ces caches suivent l'historique des évictions.
   • Si une requête échoue dans le cache principal mais réussit dans un cache fantôme, cela sert de signal de rétroaction. Un succès dans $B1$ suggère que la file de récence ($T1$) est trop petite, tandis qu'un succès dans $B2$ suggère que la file de fréquence ($T2$) nécessite une expansion.
3. Partitionnement dynamique : Sur la base des succès dans les caches fantômes, l'algorithme ajuste dynamiquement la taille des caches physiques $T1$ et $T2$ tout en maintenant une taille totale de cache fixe. Cela permet au système de s'adapter aux changements de charge de travail, tels que l'émergence de nouveaux points chauds ou les changements dans les modèles d'activité des utilisateurs.
4. Intégration : La stratégie opère au niveau du bloc KV (par exemple, 16 tokens), s'alignant sur le mécanisme de paged attention utilisé dans les systèmes de service modernes. Elle est conçue pour être sans paramètre et s'intègre directement avec le module d'éviction de vLLM.

Principales Contributions

• Politique d'éviction adaptative : L'article introduit la première application de l'ARC au service de LLM, passant de politiques statiques basées sur la récence à une approche hybride dynamique.
• Adaptabilité de la charge de travail : La méthode démontre la capacité de balancer automatiquement les ressources de cache entre les modèles d'accès récents et fréquents sans réglage manuel.
• Interprétabilité : Contrairement aux approches basées sur l'apprentissage qui nécessitent l'entraînement de prédicteurs, cette méthode offre une interprétabilité claire concernant la manière dont l'espace de cache est alloué en fonction de l'historique des accès.
• Implémentation Open-Source : Les auteurs fournissent une implémentation open-source intégrée à vLLM, disponible pour la communauté et pour la recherche ultérieure.

Résultats Expérimentaux
Les auteurs ont évalué la méthode proposée par rapport à la ligne de base standard vLLM LRU et une variante à deux files statiques (DBL) en utilisant deux principaux types de charges de travail :

1. QA de documents synthétiques : En utilisant les jeux de données QuALITY et WikiQA avec un échantillonnage de requêtes suivant une distribution de Zipf.
   • Taux de succès (Hit Rate) : Amélioration allant jusqu'à 10,8 % (QuALITY) et 7,8 % (WikiQA) par rapport au LRU.
   • Temps pour le premier jeton (TTFT) : Réduction allant jusqu'à 12,6 % (QuALITY) et 7,9 % (WikiQA).
   • Les améliorations étaient plus marquées pour de petites tailles de cache, là où les décisions d'éviction sont plus fréquentes.
2. Conversation réelle : En utilisant une trace du jeu de données anonyme Qwen-Bailian (43 058 requêtes).
   • Taux de succès (Hit Rate) : Amélioration de 1,1 % à 2,1 %.
   • TTFT : Réduction de 1,0 % à 2,0 %.
   • L'étude a noté que le dimensionnement adaptatif devenait de plus en plus bénéfique à mesure que les tailles de cache augmentaient, capturant les changements de charge de travail à grande échelle que les politiques statiques manquaient.
3. Inférence par lots (Batch Inference) : Les expériences faisant varier les tailles de lots sur le jeu de données QuALITY ont montré que l'avantage relatif de l'ARC sur le LRU persistait et augmentait légèrement avec des tailles de lots plus importantes, maintenant une réduction de 5 à 7 % du TTFT.

Signification et Revendications
L'article affirme qu'une gestion adaptative du cache KV est un mécanisme pratique et efficace pour améliorer les performances du service de LLM. En capturant les modèles de réutilisation au-delà de la simple récence, la méthode proposée améliore les taux de succès du cache et réduit la latence à travers diverses charges de travail. Les auteurs soulignent que leur approche se généralise bien à l'inférence par lots et fournit une base pour les futurs systèmes devant gérer des modèles d'accès complexes et changeants sans la surcharge des prédicteurs basés sur l'entraînement. Le travail suggère que le partitionnement dynamique des ressources de cache est une étape critique vers un déploiement plus efficace des LLM dans les environnements de production.