Accueil › Glossaire › Cache Eviction

Cache Eviction

Le cache eviction (éviction du cache) est le processus de sélection et de suppression d’éléments du KV-cache d’un LLM quand la mémoire GPU est pleine, afin de libérer de l’espace pour de nouvelles requêtes tout en conservant les éléments les plus importants pour la qualité de la génération.

Pourquoi l’éviction du KV-cache est nécessaire

Le KV-cache stocke les vecteurs Key et Value calculés par le mécanisme d’attention pour chaque token déjà traité. Ce cache croît linéairement avec la longueur du contexte. Pour un modèle de 70B paramètres avec un contexte de 128K tokens, le KV-cache peut atteindre des dizaines de Go par requête. Multipliez par le nombre de requêtes concurrentes, et la mémoire GPU (VRAM) sature rapidement.

Quand la VRAM est pleine, trois options existent : rejeter les nouvelles requêtes (inacceptable en production), offloader le KV-cache vers la RAM CPU ou le SSD (ajoute de la latence), ou évincer les éléments du cache les moins utiles pour faire place aux nouveaux. L’éviction est la solution la plus directe et la plus rapide, mais elle implique un compromis : supprimer un élément du cache signifie que l’information qu’il portait est perdue pour le modèle.

Le défi est de déterminer quoi évincer. Les politiques d’éviction classiques de l’informatique (LRU, LFU) ne tiennent pas compte des particularités de l’attention dans les transformers. Des algorithmes spécifiques aux LLM ont été développés pour évincer les tokens les moins importants pour la qualité de la génération future.

Deux contextes d’éviction distincts

L’éviction du KV-cache s’applique dans deux contextes différents, chacun avec ses propres contraintes :

Éviction au niveau des blocs (serveur d’inférence)

Dans un serveur d’inférence comme vLLM ou TensorRT-LLM, le prefix caching stocke les blocs de KV-cache entre les requêtes pour accélérer les futures requêtes partageant le même préfixe. Quand la VRAM est pleine, le serveur doit évincer des blocs entiers (pages de KV-cache correspondant à des requêtes passées) pour accueillir de nouvelles requêtes.

Ce type d’éviction porte sur des blocs inter-requêtes. La politique par défaut est LRU : les blocs les moins récemment accédés sont évincés en premier. TensorRT-LLM offre une éviction par priorité configurable, où l’utilisateur peut assigner une priorité et une durée de rétention à certains blocs (par exemple, garder les blocs du system prompt plus longtemps que les blocs de conversations terminées).

Éviction au niveau des tokens (compression du KV-cache)

Au sein d’une même requête, quand le contexte dépasse le budget mémoire alloué, le système doit sélectionner quels tokens du KV-cache conserver et lesquels supprimer. C’est ici que les algorithmes spécifiques aux LLM interviennent (H2O, SnapKV, StreamingLLM). Cette éviction porte sur des tokens intra-requête et affecte directement la qualité de la génération.

La distinction est importante : l’éviction de blocs (inter-requêtes) est un problème de gestion de ressources système. L’éviction de tokens (intra-requête) est un problème d’approximation de l’attention du modèle.

Politiques d’éviction classiques

LRU (Least Recently Used)

La politique la plus simple et la plus utilisée par défaut. Les éléments les moins récemment accédés sont évincés en premier. L’hypothèse : si un bloc de cache n’a pas été utilisé récemment, il est peu probable qu’il soit utilisé bientôt.

Avantages : simple à implémenter, overhead quasi nul, fonctionne bien pour les patterns de trafic uniformes.

Limites pour les LLM : LRU ne comprend pas l’importance sémantique des tokens. Dans un workflow agentique séquentiel (agent A → agent B → agent C → retour à agent A), le cache de l’agent A est évincé pendant l’exécution de B et C, forçant un recalcul coûteux quand A est ré-invoqué. LRU ne distingue pas non plus un system prompt (précieux, réutilisé par toutes les requêtes) d’une conversation terminée (peu de chance de réutilisation).

LFU (Least Frequently Used)

Les éléments les moins fréquemment accédés sont évincés. L’hypothèse : les éléments populaires le resteront. Moins utilisé que LRU en production LLM car les patterns d’accès au KV-cache ne correspondent pas bien au modèle de fréquence (un token peut être critique mais accédé une seule fois).

Éviction par priorité (TensorRT-LLM)

NVIDIA TensorRT-LLM offre une API d’éviction par priorité qui permet d’assigner une priorité de rétention et une durée à des plages de tokens spécifiques. Cela donne un contrôle fin : le system prompt reçoit la priorité maximale (retenu le plus longtemps), les conversations actives une priorité moyenne, et les conversations terminées une priorité basse (évincées en premier).

# TensorRT-LLM : éviction par priorité
# Configurer la priorité de rétention pour des plages de tokens
retention_config = [
    TokenRangeRetentionConfig(
        start=0,
        end=2048,          # System prompt (premiers 2048 tokens)
        priority="high",   # Retenir le plus longtemps possible
        duration=3600      # Garder au moins 1 heure
    ),
    TokenRangeRetentionConfig(
        start=2048,
        end=None,          # Contenu dynamique (conversation)
        priority="low",    # Évincer en premier si nécessaire
        duration=300       # Garder au moins 5 minutes
    )
]

Les benchmarks NVIDIA montrent que l’éviction par priorité améliore le taux de cache hits d’environ 20 % par rapport au LRU standard, car les blocs de haute valeur (system prompts, documents de référence) sont protégés de l’éviction.

Politiques d’éviction spécifiques aux LLM

Ces algorithmes analysent les patterns d’attention du modèle pour identifier les tokens les plus importants et évincer les moins importants. Ils s’appliquent à l’éviction intra-requête (compression du KV-cache d’une seule séquence).

H2O (Heavy-Hitter Oracle)

H2O (NeurIPS 2023) observe que certains tokens reçoivent une quantité disproportionnée d’attention à chaque étape de génération. Ces « heavy hitters » sont les tokens les plus importants pour le modèle. H2O conserve les heavy hitters et un buffer de tokens récents, évincant les tokens à faible score d’attention cumulé.

Fonctionnement : à chaque étape de décodage, H2O cumule les scores d’attention reçus par chaque token. Quand le budget mémoire est atteint, le token avec le score cumulé le plus bas est évincé. Le KV-cache conserve donc en permanence les tokens les plus « regardés » par le modèle.

Résultats : H2O peut réduire le KV-cache de 50 % avec une dégradation de perplexité < 1 % sur les modèles Llama. Le throughput augmente de plus de 40 %.

Limites : H2O évince un seul token à la fois, ce qui peut être lent pour les longues séquences. Le score cumulé peut biaiser contre les tokens récents (qui n’ont pas encore accumulé beaucoup d’attention). Des recherches récentes (DefensiveKV, 2025) montrent que l’hypothèse de « stabilité de l’importance » sur laquelle H2O repose est fragile dans certains cas.

SnapKV

SnapKV aborde l’éviction du KV-cache du côté prefill (compression du prompt avant la génération). Au lieu de garder tout le KV-cache du prompt, SnapKV utilise une « fenêtre d’observation » (les derniers tokens du prompt) pour prédire quels tokens seront importants pendant la génération. Les tokens importants sont conservés, les autres sont évincés.

Fonctionnement : SnapKV calcule l’attention croisée entre les tokens de la fenêtre d’observation (suffixe du prompt) et tous les tokens précédents. Les tokens qui reçoivent le plus d’attention dans cette fenêtre sont conservés. Un mécanisme de pooling agrège les scores pour plus de robustesse.

Résultats : réduction du KV-cache du prompt de 50-80 % avec une dégradation minimale. Particulièrement efficace pour les longs documents où la majorité du contenu n’est pas pertinent pour la question posée.

Limites : la fenêtre d’observation ne voit que le suffixe du prompt, pas les tokens de la réponse future. Des travaux récents (SpecKV, LookaheadKV) utilisent un modèle draft pour générer une réponse approximative et l’utiliser comme fenêtre d’observation plus fiable.

StreamingLLM

StreamingLLM (2023) est conçu pour la génération de longueur théoriquement infinie avec une mémoire fixe. Il exploite un phénomène observé dans les transformers : les tout premiers tokens du contexte (les « attention sinks », typiquement les 4-8 premiers tokens) reçoivent une quantité massive d’attention, indépendamment de leur contenu sémantique. Ce sont des points d’ancrage pour le mécanisme d’attention.

Fonctionnement : StreamingLLM maintient un KV-cache de taille fixe composé de deux parties : les attention sinks (premiers tokens, toujours conservés) et une fenêtre glissante des tokens les plus récents. Tous les tokens intermédiaires sont évincés.

Résultats : mémoire constante quelle que soit la longueur de la génération. Fonctionne bien pour les tâches conversationnelles où le contexte récent est le plus pertinent.

Limites : la perte de contexte intermédiaire dégrade la qualité pour les tâches nécessitant des dépendances à longue portée (résumé de long document, raisonnement sur un contexte complet). StreamingLLM est un compromis explicite : mémoire fixe contre qualité dégradée sur les longues dépendances.

Scissorhands

Similaire à H2O mais avec une approche par lot. Scissorhands définit un taux de compression cible (par exemple, réduire le KV-cache de 30 %) et supprime d’un coup tous les tokens en dessous d’un seuil d’importance, en gardant les tokens à haute attention et les tokens récents. L’hypothèse est la même que H2O (Persistence of Importance Hypothesis) : les tokens importants à un moment donné restent importants aux étapes futures.

Avancées récentes (2025-2026)

Le domaine évolue rapidement. Voici les directions de recherche les plus prometteuses :

Éviction multi-niveaux : GPU → CPU → SSD

L’éviction ne signifie pas nécessairement la suppression définitive du KV-cache. Dans une architecture multi-niveaux, les blocs évincés de la VRAM GPU sont déplacés vers la RAM CPU (plus lente mais beaucoup plus grande), puis vers le SSD si la RAM est aussi pleine. Quand un bloc est à nouveau nécessaire (cache hit sur un préfixe précédemment évincé), il est rechargé depuis la RAM ou le SSD plutôt que recalculé.

EvicPress (2025) propose de combiner la compression adaptative et l’éviction multi-niveaux de manière jointe. Au lieu de traiter tous les contextes de la même manière, EvicPress adapte le niveau de compression à chaque contexte : un contexte qui supporte bien la compression est compressé agressivement et gardé en GPU, un contexte fragile à la compression est évincé vers le CPU avec une compression minimale.

Le framework MTDS (Multi-Tier Dynamic Storage, 2026) formalise cette approche avec un schéma de contrôle d’accès dynamique et une stratégie d’éviction hiérarchique adaptative qui gère automatiquement les transitions GPU → CPU → SSD en fonction de la contention de bande passante et de la capacité restante à chaque niveau.

Cas particulier : modèles de raisonnement

Les modèles de raisonnement (Claude avec extended thinking, o1/o3 d’OpenAI, DeepSeek-R1) génèrent de longues chaînes de pensée (chain-of-thought) pouvant atteindre des dizaines de milliers de tokens. Le KV-cache de ces traces de raisonnement est massif et pose un défi unique à l’éviction.

Pourquoi c’est difficile : dans une chaîne de raisonnement, le modèle peut revenir sur des étapes antérieures pour vérifier ou corriger son travail. Un token de raisonnement qui semble peu important à l’étape 100 peut devenir critique à l’étape 500 quand le modèle y fait référence. Les méthodes d’éviction basées sur l’attention passée (H2O) échouent à prédire ces réutilisations futures.

G-KV (2025-2026) propose une éviction guidée par graphe spécifiquement pour les modèles de raisonnement. ForesightKV apprend à prédire l’importance future des tokens via un entraînement supervisé, offrant de meilleures décisions d’éviction pour les longues traces de raisonnement.

Comparatif des politiques d’éviction

Guide pratique

Choisir sa politique d’éviction

Votre problème est-il l'éviction entre requêtes (prefix caching) ?
├── Oui → LRU (défaut vLLM/SGLang) ou Priorité (TensorRT-LLM)
│   └── Workloads agentiques → KVFlow si disponible
└── Non → Le KV-cache d'une seule requête dépasse le budget ?
    ├── Long document en prefill → SnapKV
    ├── Génération longue (raisonnement, CoT) → H2O + DefensiveKV
    ├── Streaming infini → StreamingLLM
    └── Besoin de compression maximale → SnapKV (prefill) + H2O (decode) + quantification FP8

Configuration dans vLLM

vLLM utilise LRU par défaut pour l’éviction des blocs de prefix caching. Les algorithmes d’éviction intra-requête (H2O, SnapKV) ne sont pas intégrés nativement dans vLLM (ils nécessitent des kernels CUDA custom). PagedEviction, conçu spécifiquement pour PagedAttention, opère au niveau des blocs sans modifier les kernels.

Pour la plupart des déploiements, la combinaison prefix caching (APC) + LRU + quantification FP8 du KV-cache offre le meilleur rapport simplicité/performance. Les algorithmes d’éviction avancés (H2O, SnapKV) se justifient quand le contexte par requête dépasse la VRAM disponible et que l’offloading n’est pas une option (contraintes de latence strictes).

Bonnes pratiques

Commencez par le prefix caching + LRU. C’est la configuration par défaut de vLLM et SGLang. Elle couvre 90 % des cas d’usage sans complexité additionnelle. N’ajoutez des politiques d’éviction avancées que si la VRAM reste un goulot d’étranglement après avoir activé le prefix caching et la quantification du KV-cache.

Utilisez l’éviction par priorité si vos workloads sont hétérogènes. Si votre serveur traite à la fois des conversations courtes et des analyses de longs documents, l’éviction par priorité (TensorRT-LLM) permet de protéger les blocs des documents longs (coûteux à recalculer) tout en évincant rapidement les conversations courtes terminées.

Combinez compression et éviction. L’éviction seule perd de l’information. La compression seule garde tout mais dégrade la qualité quand le ratio est trop agressif. La combinaison (EvicPress) adapte le compromis par contexte : compresser les contextes robustes, évincer les contextes fragiles.

Surveillez le taux d’éviction et le taux de recalcul. Si le taux d’éviction est élevé (> 50 % des blocs sont évincés à chaque cycle), votre VRAM est sous-dimensionnée pour votre charge. Ajoutez des GPU, réduisez le batch size, ou activez l’offloading vers la RAM CPU. Le taux de recalcul (blocs évincés puis recalculés parce qu’une requête les redemande) est la métrique la plus directe du coût de l’éviction.

Attention aux modèles de raisonnement. Les longues traces de chain-of-thought sont particulièrement vulnérables à l’éviction car le modèle peut référencer des tokens anciens de manière imprévisible. Augmentez le budget de cache pour les requêtes de raisonnement, ou utilisez des politiques adaptatives (ForesightKV, G-KV) qui prennent en compte l’importance future des tokens.