🤖 machine learning

Not All Tokens Are Worth Caching: Learning Semantic-Aware Eviction for LLM Prefix Caches

Ce papier présente SAECache, une politique d'éviction de cache de préfixe adaptative sémantique qui exploite les valeurs de réutilisation variables de différents types de jetons grâce à une architecture multi-files d'attente et à un apprentissage en ligne pour améliorer considérablement l'efficacité du service des LLM tout en éliminant le besoin d'un réglage manuel des paramètres.

Auteurs originaux : Shaoke Fang, Ziang Li, Wenfei Wu, Jiatong Ji, Qingsong Liu, Ruizhi Pu

Publié 2026-05-20

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Shaoke Fang, Ziang Li, Wenfei Wu, Jiatong Ji, Qingsong Liu, Ruizhi Pu

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous gérez un café très fréquenté et haut de gamme (le Grand Modèle de Langage ou LLM) qui sert des millions de clients chaque jour. Pour préparer le café rapidement, vous disposez d'une « étagère de mémoire » spéciale (la Mémoire GPU) où vous conservez les ingrédients préfabriqués et les instructions pour les commandes que vous avez déjà commencées. C'est ce qu'on appelle le Mise en cache des préfixes.

Si un nouveau client commande un latte qui est identique à 90 % à une commande précédente, vous n'avez pas besoin de moudre de nouveaux grains ou de chauffer du nouveau lait ; vous prenez simplement la base préfabriquée sur l'étagère. Cela permet à la première gorgée (le Premier Jeton) d'apparaître presque instantanément.

Cependant, votre étagère est minuscule. Vous ne pouvez pas conserver chaque base préfabriquée indéfiniment. Finalement, vous devez jeter certaines choses pour faire de la place aux nouvelles commandes. C'est la Politique d'éviction.

Le Problème : L'Erreur du « Taille Unique »

Pendant longtemps, les gérants de cafés ont utilisé une règle simple : « Jetez d'abord l'article le plus ancien. » (C'est la politique LRU).

L'article soutient que c'est une mauvaise idée car tous les articles sur l'étagère n'ont pas la même valeur.

L'Invite Système : Imaginez un « Menu Standard » que chaque client voit. Il ne change jamais. Il est incroyablement précieux car tout le monde le commande.
La Chaîne de Pensée : Imaginez le monologue intérieur désordonné d'un client expliquant pourquoi il veut un latte. Cela est unique à cette personne et à ce moment précis. Ce n'est presque jamais utile pour le client suivant.

L'ancienne règle traitait le « Menu Standard » et le « Monologue Désordonné » exactement de la même manière. Si le Monologue était légèrement plus récent que le Menu, l'ancienne règle aurait jeté le Menu pour faire de la place au Monologue. C'est une catastrophe car le client suivant aura besoin du Menu immédiatement, mais le Monologue lui sera inutile.

La Solution : SAECache (Le Gérant Intelligent)

Les auteurs ont créé un nouveau système appelé SAECache. Imaginez-le comme un gérant intelligent qui ne regarde pas seulement quand un article a été touché pour la dernière fois, mais ce que l'article est réellement.

Voici comment cela fonctionne, en utilisant des analogies simples :

1. Les Quatre Bacs Spécialisés (Architecture Multi-File d'Attente)

Au lieu d'une seule grande étagère, SAECache organise l'étagère en quatre bacs distincts, chacun avec ses propres règles :

Le Bac « Poubelle » : Contient les articles qui sont presque jamais réutilisés (comme le monologue désordonné ou les étapes finales d'une boisson). Ceux-ci sont jetés en premier.
Le Bac « Modèle » : Contient les instructions standard et les invites système (comme le menu). Ceux-ci sont conservés avec beaucoup de soin car ils sont réutilisés constamment.
Le Bac « Discussion » : Contient les conversations où les gens parlent tour à tour.
Le Bac « Agent » : Contient les tâches complexes où l'IA effectue un travail (comme coder ou utiliser des outils).

2. Le « Score de Valeur » (Pondération Consciente de la Sémantique)

Le gérant ne devine pas simplement quel bac est important. Il apprend !

Si le gérant jette une « Invite Système » et qu'on lui demande immédiatement à nouveau, le système apprend : « Oups ! J'ai jeté quelque chose de précieux. Je devrais donner un score plus élevé aux Invites Système la prochaine fois. »
S'il jette une « Chaîne de Pensée » et que personne ne le demande, il apprend : « Bon travail ! C'était de la ferraille. Je continuerai à lui donner un score bas. »

Cela se produit automatiquement, comme un gérant ajustant les étagères en fonction de ce que les clients achètent réellement, sans qu'un humain ait besoin de lui dire quoi faire.

3. La « Machine à Remonter le Temps » (Chronométrage Adaptatif)

Le système apprend également quand les gens reviennent.

Les sessions de discussion peuvent avoir de longues pauses (comme un client prenant une pause café).
Les sessions d'agent peuvent être très rapides et frénétiques.
Le système apprend le « rythme cardiaque » spécifique de chaque type de session. Il sait que si une session de discussion n'est pas revenue depuis 10 minutes, elle est probablement partie pour toujours. Mais si une session d'agent n'est pas revenue depuis 10 secondes, elle est peut-être simplement en train de réfléchir. Il ajuste ses règles d'éviction en temps réel pour correspondre au rythme du trafic.

Les Résultats : Café Plus Rapide, Moins de Gaspillage

L'article a testé ce nouveau gérant contre l'ancienne règle du « plus ancien en premier » et d'autres systèmes intelligents mais rigides.

Vitesse : Le nouveau système a fait apparaître la première gorgée de café 1,4 à 2,7 fois plus vite dans des environnements chargés et mixtes.
Adaptabilité : Les anciens systèmes ont échoué lorsque le type de clients a changé (par exemple, si le café a soudainement reçu plus de clients avec des commandes uniques au lieu de discoureurs). Le nouveau système s'est adapté instantanément.
Efficacité : Il a économisé une quantité massive de mémoire « gaspillée » en ne thésaurisant pas de ferraille (comme les monologues désordonnés) et en gardant les éléments précieux (comme le menu) en sécurité.

Résumé

En bref, l'article dit : Ne traitez pas tous les blocs de mémoire de la même manière. Le fait que deux choses aient été touchées en même temps ne signifie pas qu'elles sont également utiles. En enseignant à l'ordinateur à comprendre le sens des données (s'agit-il d'un menu ? d'une blague ? d'un outil ?) et en lui permettant d'apprendre de ses propres erreurs en temps réel, nous pouvons rendre l'IA beaucoup plus rapide et plus efficace.

Résumé Technique : SAECache – Éviction Sensible au Sémantique pour les Caches de Préfixe des LLM

Énoncé du Problème

La mise en cache de préfixes dans les modèles de langage de grande taille (LLM) vise à réduire la latence d'inférence (spécifiquement le temps jusqu'au premier jeton, ou TTFT) en réutilisant les états Clé-Valeur (KV) provenant de requêtes partageant des préfixes d'entrée. Cependant, l'efficacité de la mise en cache de préfixes est sévèrement contrainte par la mémoire GPU limitée, nécessitant une politique d'éviction pour rejeter les blocs moins précieux lorsque la capacité est atteinte.

Les politiques d'éviction existantes, telles que LRU (Least Recently Used) et LFU (Least Frequently Used), reposent principalement sur des statistiques de temps d'accès ou de fréquence. Ces approches agnostiques aux jetons traitent uniformément tous les blocs mis en cache, ignorant deux dimensions critiques des charges de travail des LLM :

Hétérogénéité Sémantique : Différents types de jetons (par exemple, invites système vs raisonnement par chaîne de pensée) présentent des taux de réutilisation intrinsèques radicalement différents.
Variabilité des Charges de Travail : Les motifs de réutilisation diffèrent considérablement entre les requêtes à tour unique basées sur des modèles (réutilisation structurelle) et les conversations à tours multiples (réutilisation temporelle locale à la session), les intervalles inter-tours suivant des distributions distinctes selon les types d'applications (par exemple, chat vs flux de travail d'agents).

Les auteurs observent que traiter un bloc d'invite système à haute valeur et un bloc de raisonnement par chaîne de pensée à faible valeur comme équivalents lorsque leur récence correspond conduit à une allocation mémoire sous-optimale. De plus, les politiques à paramètres fixes échouent lorsque les compositions de charges de travail évoluent, entraînant une dégradation des performances allant jusqu'à 2,7× en cas de mismatch de charge de travail.

Méthodologie : SAECache

Pour pallier ces limitations, les auteurs proposent SAECache (Éviction Adaptative au Sémantique pour les caches de préfixe), une politique qui intègre la structure sémantique des jetons avec l'adaptation en ligne aux charges de travail. Le système fonctionne via trois mécanismes fondamentaux :

1. Architecture Multi-File avec Routage Basé sur des Règles

SAECache achemine les blocs KV vers quatre files distinctes basées sur leurs motifs de réutilisation dominants, plutôt que vers une file globale unique :

File d'Éviction Prioritaire : Stocke les blocs à faible valeur, incluant les jetons de phase de décodage et les blocs de préremplissage non modélisés à faible potentiel de réutilisation. Ceux-ci sont vidés en premier.
File Structurelle : Stocke les blocs KV des sessions à tour unique qui reposent sur des structures d'invite partagées (par exemple, modèles d'utilisation d'outils, instructions de programmation).
File de Chat : Stocke les blocs à tours multiples des sessions conversationnelles, modélisant la réutilisation temporelle locale à la session.
File d'Agent : Stocke les blocs à tours multiples des sessions d'agent/d'utilisation d'outils, qui présentent des distributions de contenu de jeton et d'intervalle de requête différentes par rapport au chat standard.

Un prédicteur de session à tours multiples léger (un MLP à 3 couches réutilisant les états cachés finaux du modèle de service) résout l'ambiguïté pour la première requête d'une session, l'acheminant vers la file à tours multiples appropriée si une continuation est prédite, ou vers les files structurelle/d'éviction prioritaire sinon.

2. Notation de Priorité Locale

Au sein de chaque file, les blocs sont notés pour l'éviction sur la base d'une métrique composite $P(b)$ :
$P(b) = \alpha_q \cdot w_{\tau(b)} \cdot \frac{p_q(b)}{\Delta t_b}$

$\alpha_q$ (Poids de File) : Un poids dynamique reflétant l'efficacité récente des hits de la file spécifique.
$w_{\tau(b)}$ (Poids de Type de Jeton) : Un poids appris spécifique au type de jeton (par exemple, invite système, requête utilisateur, chaîne de pensée) du bloc.
$p_q(b)$ (Probabilité de Survie Locale) :
- Pour les files Chat/Agent : Calculée comme la probabilité de survie $1 - F_{LN}(\Delta t_b; \mu_q, \sigma_q)$ sous une distribution log-normale ajustée aux intervalles inter-tours de ce type de session.
- Pour la file Structurelle : Calculée comme $1 - (o_b / o_{max})^\gamma$ , où $o_b$ est le décalage du bloc et $\gamma$ une puissance de décroissance apprise, privilégiant les blocs plus tôt dans une invite.
$\Delta t_b$ : Le temps écoulé depuis le dernier accès au bloc.

3. Apprentissage En Ligne Fully Adaptatif

SAECache élimine le réglage manuel en mettant à jour tous les paramètres en ligne via une boucle de rétroaction unifiée basée sur les statistiques de hits/misses du cache :

Poids de Type de Jeton : Mis à jour via une Moyenne Mobile Exponentielle (EMA) basée sur les taux de "miss après éviction" et les taux de hits globaux.
Paramètres Log-Normaux ( $\mu, \sigma$ ) : Estimés en ligne par Maximum de Vraisemblance (MLE) sur les intervalles d'accès observés pour les files chat et agent.
Puissance de Décroissance de Position ( $\gamma$ ) : Apprise à partir des corrélations entre la position du bloc et les taux de hits dans la file structurelle.
Poids de File ( $\alpha_q$ ) : Mis à jour en fonction du ratio de jetons hit à la capacité allouée pour chaque file, pondéré par un paramètre de température.

Contributions Clés

Caractérisation Empirique : Une étude systématique révélant que la réutilisation des jetons varie jusqu'à 756× selon les types de jetons (92,3 % pour les invites système contre 2,2 % pour la chaîne de pensée) et que les intervalles inter-tours suivent des distributions log-normales spécifiques à la session plutôt que de simples décroissances exponentielles.
Politique SAECache : Une politique d'éviction multi-file sensible au sémantique qui découple les mécanismes de réutilisation hétérogènes (structurel vs temporel) et assigne des priorités distinctes aux types de jetons.
Adaptation En Ligne : Un cadre d'apprentissage qui ajuste automatiquement les distributions temporelles, la décroissance de position et les paramètres de pondération sans intervention manuelle, s'adaptant aux compositions de charges de travail changeantes.
Évaluation Complète : Expériences étendues sur des jeux de données réels (ShareGPT, LMSys, Chatbot-Arena) démontrant une robustesse à travers des charges de travail hétérogènes.

Résultats Expérimentaux

Évalué sur une implémentation vLLM avec Qwen2.5-1.5B-Instruct sur un GPU NVIDIA A40, SAECache a été comparé à LRU (référence de production) et à la mise en cache de préfixe apprise (LPC).

Amélioration du TTFT : SAECache a réalisé une amélioration du TTFT de 1,4× à 2,7× par rapport aux références de style production à travers des charges de travail hétérogènes.
Taux de Hit du Cache : SAECache a constamment atteint les taux de hits de cache les plus élevés, améliorant de 4,8 à 5,9 points de pourcentage par rapport à la référence la plus forte (LRU ou LPC) sur toutes les configurations testées.
Résilience au Mismatch de Charge de Travail : Les alternatives à paramètres fixes ont subi jusqu'à une dégradation de 2,7× du TTFT lorsque la composition de la charge de travail s'écartait de la trace d'entraînement. SAECache a maintenu des performances stables en adaptant ses paramètres en ligne.
Études d'Ablation :
- La pondération sensible au type de jeton a contribué à une amélioration supplémentaire de 23 %.
- La pondération adaptative des files a contribué au gain le plus important à 39 %.
- Le timing log-normal et l'apprentissage de la décroissance de position ont fourni des gains supplémentaires de 14 % et 12 % respectivement.
Surcharge : Le prédicteur de session à tours multiples est hautement efficace, ne nécessitant que ~1M de paramètres (contre 118M pour le modèle d'encodage de LPC) et atteignant un débit d'inférence 8,8 fois plus élevé.

Importance et Revendications

L'article revendique que l'éviction de cache de préfixe ne doit pas traiter uniformément tous les blocs mis en cache, même lorsqu'ils partagent des statistiques de récence ou de fréquence similaires. Les auteurs affirment que la sémantique des jetons, la structure de l'invite et le type de session sont des moteurs fondamentaux de la réutilisation que les politiques existantes échouent à capturer.

L'importance de SAECache réside dans sa capacité à :

Combler le fossé entre les politiques heuristiques statiques et la réalité dynamique et sémantique du service des LLM.
Éliminer le réglage manuel, rendant le système robuste aux changements de charge de travail (par exemple, d'un trafic riche en chat à un trafic riche en utilisation d'outils) sans réentraînement ni ajustement de paramètres.
Démontrer que l'éviction fine et sensible au sémantique est un choix de conception critique pour un service LLM efficace, en particulier dans des environnements à forte pression de cache et à motifs de requêtes hétérogènes.

Les auteurs notent que si SAECache excelle dans les charges de travail mixtes et à tours multiples, sa surcharge peut légèrement réduire les performances dans les régimes dominés par les tours uniques (par exemple, Chatbot-Arena) où les bénéfices de taux de hits plus élevés ne compensent pas entièrement les coûts de gestion, soulignant la nécessité de stratégies adaptatives pouvant évoluer avec les caractéristiques de la charge de travail.