🤖 machine learning

Sparse Prefix Caching for Hybrid and Recurrent LLM Serving

Ce papier introduit la mise en cache de préfixes épars pour le service d'LLM hybrides et récurrents, une méthode qui optimise la latence en stockant stratégiquement des états récurrents exacts à des positions de point de contrôle éparset pour reprendre le calcul à partir de la correspondance la plus profonde, surpassant ainsi les heuristiques de mise en cache denses existantes tout en préservant les sorties exactes et sans nécessiter de modifications de noyau.

Auteurs originaux : Mikhail Shirokikh, Sergey Nikolenko

Publié 2026-05-08

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Mikhail Shirokikh, Sergey Nikolenko

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 êtes un chef préparant un repas complexe à plusieurs services pour une série de convives. Dans le monde des modèles de langage de grande taille (LLM), le « repas » consiste à générer une réponse, et les « ingrédients » sont les mots (tokens) que le modèle a déjà traités.

L'Ancienne Méthode : La Cuisine « Tout ou Rien »

Traditionnellement, lorsqu'un nouveau convive (une nouvelle requête) arrive, le chef vérifie s'il a commandé quelque chose de similaire au dernier convive.

S'ils ont commandé exactement le même apéritif : Le chef réutilise l'assiette entière.
S'ils ont commandé quelque chose de légèrement différent : Le chef jette toute l'assiette d'apéritif et recommence à cuisiner depuis zéro, même si les 90 % premiers des ingrédients étaient identiques.

En termes techniques, cela s'appelle la mise en cache dense. Le système conserve une copie de chaque étape (chaque token) pour la réutiliser plus tard. Cela fonctionne très bien pour les modèles standards, mais pour un nouveau type de modèle appelé Modèle Hybride ou Récurrent, cette approche revient à essayer de transporter une bibliothèque de livres juste pour lire une phrase. C'est trop lourd et cela occupe trop de mémoire.

La Nouvelle Idée : La Stratégie des « Points de Contrôle »

Ce papier propose une manière plus intelligente de gérer ces modèles spécifiques. Imaginez la mémoire du modèle non pas comme une bibliothèque de chaque mot, mais comme un état d'esprit.

Imaginez que vous lisez un roman très long.

L'Ancienne Méthode : Vous placez un post-it sur chaque page afin de pouvoir revenir instantanément en arrière. (Trop de post-its !).
La Nouvelle Méthode (Mise en cache de préfixe clairsemée) : Vous ne placez des post-its que sur la Page 1, la Page 100, la Page 200, etc.

Si un nouveau lecteur souhaite continuer l'histoire à partir de la Page 150 :

Vous ne jetez pas le livre entier.
Vous trouvez le dernier post-it (Page 100).
Vous relisez rapidement l'histoire de la Page 101 à la 149 pour retrouver l'état actuel.
Ensuite, vous continuez à partir de la Page 150.

Parce que le modèle est « récurrent » (il fait évoluer son état étape par étape), il n'a pas besoin de l'histoire entière, seulement de l'état à un point spécifique. Ce papier appelle ces post-its des points de contrôle.

Le Problème : Où Placer les Post-its ?

Voici maintenant la partie délicate. Vous avez un budget limité de post-its (mémoire). Où devriez-vous les placer pour gagner le plus de temps ?

La Stratégie « Équilibrée » : Placer les notes uniformément (toutes les 100 pages). C'est sûr, mais peut-être pas le plus rapide.
La Stratégie « Intelligente » (Ce que fait ce papier) : Observer les habitudes de vos lecteurs.
- Si la plupart des gens arrêtent de lire vers la Page 50, vous placez une note là-bas.
- Si les gens lisent généralement jusqu'à la fin, vous placez des notes vers la fin.
- Si les gens s'arrêtent souvent à la Page 200, vous placez une note là-bas.

Les auteurs ont créé une formule mathématique (un « Programme Dynamique ») qui agit comme un bibliothécaire sur-intelligent. Il analyse les requêtes passées pour prédire où les futurs lecteurs sont susceptibles de s'arrêter. Il place ensuite les post-its exactement là où ils seront les plus utiles, plutôt que de les répartir uniformément.

Les Résultats : Gagner du Temps et de la Mémoire

Le papier a testé cela sur des scénarios réels, tels que :

QuALITY : Un long document où les gens posent différentes questions sur le même texte.
Prompts Système : Un long ensemble d'instructions suivi de nombreuses questions différentes des utilisateurs.

Ce qu'ils ont découvert :

Moins de Mémoire, Même Vitesse : En plaçant les points de contrôle de manière « intelligente » en fonction de l'endroit où les gens s'arrêtent réellement, ils ont pu utiliser moins de post-its (points de contrôle) que la méthode standard « espacée uniformément » tout en économisant la même quantité de temps de cuisson.
Grands Gains pour des Budgets Restreints : Les plus grandes améliorations se sont produites lorsqu'ils avaient très peu de post-its à se permettre. Dans ces situations serrées, le placement « intelligent » était bien meilleur que de simplement deviner ou de les espacer uniformément.
Résultats Exacts : Contrairement à certaines raccourcis qui devinent la réponse, cette méthode garantit que la sortie est 100 % identique à un travail effectué depuis zéro. Elle le fait simplement plus vite en sautant les parties qu'elle connaît déjà.

L'Essentiel

Ce papier introduit une méthode pour rendre les modèles d'IA utilisant une mémoire « récurrente » plus efficaces. Au lieu de sauvegarder chaque étape ou de ne rien sauvegarder du tout, il sauvegarde quelques « instantanés » stratégiques du cerveau du modèle. En utilisant les mathématiques pour déterminer exactement où sauvegarder ces instantanés en fonction de la façon dont les gens utilisent réellement l'IA, le système peut fonctionner plus vite et utiliser moins de mémoire, surtout lorsque de nombreux utilisateurs posent des questions similaires sur le même long document.

C'est comme avoir un GPS qui ne vous montre pas simplement toute la carte, mais qui sait exactement quels virages vous êtes le plus susceptible de prendre, afin de ne sauvegarder les directions que pour ces virages spécifiques.

Résumé Technique : Mise en Cache de Préfixes Épars pour le Service d'LLM Hybrides et Récurrents

1. Énoncé du Problème

Les systèmes existants de service de Modèles de Langage à Grande Échelle (LLM) reposent fortement sur la mise en cache de préfixes denses, où les états Clé/Valeur (KV) pour chaque token d'un préfixe partagé sont stockés pour éviter un calcul de remplissage redondant. Cette approche est standard pour les architectures Transformer. Cependant, les Modèles d'Espace d'État (SSM) et les architectures hybrides (combinant l'attention avec des couches récurrentes) présentent une asymétrie structurelle : une couche récurrente fait évoluer son état selon $h_t = F(h_{t-1}, x_t)$ , ce qui signifie qu'elle peut reprendre le calcul à partir d'un seul état stocké $h_c$ plutôt que d'exiger l'historique complet des états intermédiaires.

La mise en cache dense par token des états récurrents est souvent inutile et prohibitivement coûteuse. Pour des modèles comme Qwen-3.5, l'état récurrent par tête évolue selon $d_{head}^2$ , tandis que le stockage KV de l'attention évolue linéairement. Par conséquent, stocker l'état récurrent de chaque token consomme significativement plus de mémoire que les caches KV d'attention, sans offrir d'avantage supplémentaire par rapport au stockage d'un ensemble épars de points de contrôle.

Le problème central abordé est le suivant : Étant donné un budget mémoire de $M$ emplacements de points de contrôle pour un préfixe de longueur $N$ , où les points de contrôle doivent-ils être placés pour minimiser le coût de recalcul attendu sous une distribution spécifique des profondeurs de chevauchement des futures requêtes ? Cette optimisation se distingue des politiques d'admission/évacuation du cache ; elle se concentre sur quels tokens mettre en point de contrôle au sein d'une seule entrée conservée afin de maximiser l'utilité pour les chevauchements partiels de préfixes.

2. Méthodologie

Formulation Théorique

Les auteurs formalisent le problème comme un problème de médiane k pondérée unilatérale sur une ligne.

Soit $C = \{c_1, \dots, c_M\}$ l'ensemble des positions des points de contrôle.
Pour une requête chevauchant le préfixe jusqu'à la profondeur $t$ , le point de contrôle réutilisable le plus profond est $\ell(t; C) = \max(\{0\} \cup \{c \in C : c \le t\})$ .
Le coût est le nombre de tokens à recalculer : $r(t; C) = t - \ell(t; C)$ .
L'objectif est de minimiser le coût de recalcul attendu $E[r(T; C)]$ étant donné une distribution de profondeur de chevauchement $T$ avec des probabilités $p_t$ .

Approche Algorithmique

Placement Équilibré Optimal (Uniforme/Pire Cas) : Les auteurs prouvent que sous une distribution de chevauchement uniforme ou dans le scénario du pire cas, un espacement équilibré (points de contrôle répartis uniformément) est optimal.
Programmation Dynamique (PD) Sensible à la Distribution : Pour des distributions de chevauchement non uniformes et réelles, les auteurs dérivent un algorithme exact de programmation dynamique $O(NM)$.
- La relation de récurrence est : $dp[m, j] = \min_{1 \le s \le j} (dp[m-1, s-1] + w(s, j))$ , où $w(s, j)$ est le coût d'utilisation de $s$ comme point de contrôle le plus profond pour les profondeurs $s \dots j$ .
- Ceci est résolu efficacement en utilisant l'astuce de la coque convexe monotone, exploitant la monotonie des sommes partielles.
Gestion de la Dérive de Distribution : Puisque la vraie distribution de chevauchement est inconnue et doit être estimée à partir de données historiques, l'article fournit des garanties théoriques (via le Lemme 1 et le Théorème 3) selon lesquelles la fonction de valeur est lipschitzienne par rapport à la distribution de chevauchement. Cela garantit que l'utilisation d'un histogramme empirique (ou d'un histogramme à pondération exponentielle pour les distributions en dérive) produit un planning quasi-optimal avec une sous-optimalité bornée.

Stratégie d'Implémentation

Points de Contrôle : Le système stocke les états récurrents exacts à des positions esparses. En cas de succès de cache, le système reprend à partir du point de contrôle stocké le plus profond et recalcul le suffixe exactement.
Exactitude : Puisque la mise à jour récurrente est déterministe, reprendre à partir d'un point de contrôle et rejouer le suffixe produit des sorties bit-à-bit identiques à un remplissage complet.
Intégration Hybride : Pour les modèles hybrides, la méthode stocke le cache KV d'attention complet (dense) mais applique la mise en point de contrôle épars uniquement aux couches récurrentes.

3. Contributions Clés

Optimalité Théorique : Prouvé que l'espacement équilibré est optimal sous des conditions de chevauchement uniforme et de pire cas (Théorème 1).
Algorithme Exact : Formulation de la mise en cache de préfixes épars comme un problème de médiane k pondérée et fourniture d'une solution exacte de programmation dynamique $O(NM)$ (Théorème 2).
Garanties de Robustesse : Démonstration que le planning optimal est stable sous une mauvaise spécification de la distribution. La sous-optimalité est bornée par la distance de variation totale entre les distributions de chevauchement empirique et vraie (Théorème 3), et étendue aux scénarios avec dérive de distribution en utilisant une pondération exponentielle (Théorème 4).
Validation Empirique : Validation de la méthode sur des jeux de données réels (QuALITY, NarrativeQA, Prompts Système), montrant des améliorations constantes par rapport aux bases de référence à budget fixe.

4. Résultats Expérimentaux

Jeux de Données et Configuration

Jeux de Données :
- QuALITY : Un seul document avec plusieurs questions (chevauchement élevé près de la longueur totale).
- NarrativeQA : Structure similaire avec un large chevauchement multimodal.
- Prompts Système : Vrais prompts système combinés à des requêtes utilisateur (chevauchement concentré sur de courtes longueurs).
Bases de Référence : Comparaison avec « Pas de Cache », « KV Uniquement », « Équilibré » (espacement régulier), « Bloc » (taille de bloc fixe), « Logarithmique » et « Espacé en $\sqrt{L}$ ».
Matériel : Exécutions prototypes sur NVIDIA RTX 2080 Super avec le modèle Qwen-3.5-0.8B.

Constats

Économies de Tokens : Le planning optimal PD domine constamment les bases de référence déterministes (Équilibré, Bloc, Logarithmique) en termes de facteurs de réduction du travail récurrent.
Avantage à Budget Faible : L'écart de performance est le plus grand à faibles budgets de points de contrôle où la distribution de chevauchement est la plus non uniforme. Par exemple, sur les Prompts Système (où les chevauchements sont courts), la méthode PD place les points de contrôle densément près du pic de divergence, atteignant le même temps d'exécution que la mise en cache par bloc avec moins de points de contrôle.
Temps Réel : Sur QuALITY et les Prompts Système, le planning dérivé de la PD génère des accélérations mesurables en temps réel sur des groupes de couches représentatifs. La réduction du temps d'exécution corrèle linéairement avec le nombre de tokens économisés.
Surcharge : La surcharge du chargement des points de contrôle du CPU vers le GPU est faible par rapport aux économies réalisées grâce à la réduction du recalcul, résultant en une amélioration nette du temps d'exécution.

5. Signification et Revendications

L'article revendique que la mise en cache de préfixes épars débloque un nouveau point de conception pour le service d'LLM hybrides et récurrents qui n'était pas précédemment disponible.

Compromis Mémoire/Calcul : Il offre un compromis entre l'utilisation de la mémoire et le recalcul que la mise en cache KV dense ne peut fournir, spécifiquement pour les architectures où l'état peut être extrait et restauré exactement.
Exactitude : Contrairement aux techniques de compression KV approximatives, cette méthode préserve des sorties exactes sans altérer les noyaux de calcul récurrents.
Applicabilité : Elle est la plus bénéfique pour les charges de travail où les requêtes partagent un préfixe substantiel mais non identique (par exemple, RAG avec différentes questions, prompts système variables). Elle n'offre pas d'avantages supplémentaires pour les charges de travail de chat strictement en ajout uniquement (où le dernier état suffit) mais n'entraîne aucune surcharge dans de tels cas.
Travaux Futurs : Les auteurs reconnaissent des défis d'ingénierie, spécifiquement la nécessité d'API efficaces d'extraction/restauration d'état dans les temps d'exécution de production et l'intégration de cette stratégie de placement avec des politiques d'admission/évacuation (par exemple, Marconi et al.). Ils notent également que la théorie actuelle à préfixe unique pourrait être étendue aux arbres de préfixes généraux.