Contexte technique
Le décodage par recherche de prompt (prompt lookup decoding) est une forme de décodage spéculatif qui utilise un modèle n‑gramme très simple pour proposer les prochains tokens. Les moteurs d’inférence populaires – llama.cpp, vllm ou la bibliothèque transformers de Hugging Face – intègrent cette technique afin de réduire la latence de génération. Dans la version b11182 de llama.cpp, trois caches n‑grammes sont exploités : le context cache (n‑grammes 1‑4 pour la séquence courante), le dynamic cache (historique des conversations précédentes) et le static cache (n‑grammes de taille 2 issus d’un corpus pré‑construit).
Mécanisme de prompt lookup dans llama.cpp
Pour chaque suffixe X_n = (x_{t-n+1},…,x_t), le moteur calcule un score
s_n^{f}(y) = f(X_n, y) * w(y)où f représente le compteur du cache (c_ctx ou c_dyn) et le poids w(y) vaut 100 * c_st(X_2, y) si le token apparaît dans le cache statique, sinon 1. Le token y* qui maximise ce score est retenu à condition de satisfaire deux seuils : un nombre minimal d’occurrences a_n et une proportion minimale p_n. Les valeurs codées dans b11182 sont : pour le cache contextuel (a_1,a_2,a_3,a_4)=(2,2,1,1) et (p_1,p_2,p_3,p_4)=(0.66,0.5,0.5,0.5) ; pour le cache dynamique (a_1,a_2,a_3,a_4)=(4,3,2,2) et (p_1,p_2,p_3,p_4)=(0.75,0.66,0.66,0.66). Si aucun candidat ne passe, le moteur se rabat sur le cache statique, qui utilise les mêmes seuils que le cache contextuel pour n=2.
Optimisations et gains de performance
L’auteur a appliqué une série d’optimisations inspirées des travaux de Daniel Lemire et Martin Ankerl, principalement centrées sur la structure de hachage des caches et l’utilisation de SIMD pour les comptages. Ces améliorations réduisent le temps de recherche de token de 42× en moyenne et la consommation mémoire du cache statique de 2,6×. Un pull‑request ultérieur de Lemire ajoute une optimisation supplémentaire de 4,2×, portant le facteur global à environ 140× sur les mêmes charges de travail.
Les tests utilisent le corpus WikiText‑103 (541 Mo) et des sous‑ensembles de 25 Mo, 50 Mo, 100 Mo et 200 Mo. Le benchmark llama-lookup-stats mesure trois indicateurs : latence par token drafté, temps de chargement du cache statique et empreinte mémoire. Les résultats montrent que la réduction de la taille du cache diminue proportionnellement le temps de chargement, tandis que les gains de latence restent stables grâce à la meilleure organisation interne des tables de hachage.
Limites et perspectives
Les optimisations n’affectent pas le taux d’acceptation des tokens, qui dépend uniquement de la qualité du corpus et des seuils a_n/p_n. Ainsi, les améliorations sont purement structurelles : elles ne modifient pas l’algorithme de sélection et ne garantissent pas une meilleure précision de génération. De plus, le gain maximal (≈140×) ne se manifeste que lorsque le cache statique est chargé ; sur des systèmes à très faible mémoire, le cache dynamique seul offre des accélérations plus modestes. Enfin, l’approche reste limitée aux n‑grammes de petite taille (max 4) et ne profite pas d’éventuels modèles de prévision plus sophistiqués.
