Hybrid Verified Decoding: Learning to Allocate Verification in Speculative Decoding

Résumé Technique : Décodage Vérifié Hybride

Énoncé du Problème
La génération par les Grands Modèles de Langage (LLM) est contrainte par la nature séquentielle du décodage autorégressif, où chaque nouveau jeton nécessite un passage direct complet sur le préfixe actuel et la mémoire cache Clé-Valeur (KV). Le décodage spéculatif répond à cela en proposant des jetons candidats via une source de « brouillon » (draft) et en les vérifiant en une seule étape avec le modèle cible. Cependant, l'efficacité du décodage spéculatif dépend du « taux d'acceptation » — le nombre de jetons proposés que le modèle cible accepte.

Les sources de brouillon sans paramètres (ex: caches de suffixes, recherche) offrent des propositions à faible coût en réutilisant les continuations des invites ou de l'historique de génération, mais elles souffrent d'une limitation critique : une correspondance de cache qui semble prometteuse à une étape de génération donnée peut produire un préfixe accepté très court à l'étape suivante en raison de variations dépendantes de l'état (ex: arguments différents pour un appel d'outil similaire). Vérifier un brouillon de cache à faible rendement entraîne un surcoût sans gain de vitesse significatif. Les méthodes adaptatives existantes ajustent souvent les structures ou les budgets de brouillon, mais ne prédisent pas explicitement le rendement (longueur acceptée) d'un brouillon sans paramètres avant de s'engager dans la vérification.

Méthodologie : Décodage Vérifié Hybride
Les auteurs proposent le Décodage Vérifié Hybride, un cadre qui traite la sélection de brouillon comme un problème d'allocation de vérification guidé par le rendement. Au lieu de vérifier aveuglément chaque brouillon de cache ou de s'appuyer uniquement sur un modeleur de brouillon appris par un modèle, le système prédit la longueur acceptée attendue d'un brouillon de cache avant la vérification.

1. Brouillage à Double Source : Le système maintient deux sources de brouillon :
   • Modeleur de Cache ($D_C$) : Un mécanisme sans paramètres (instancié comme SuffixDecoding) qui propose des continuations en faisant correspondre des suffixes dans l'invite d'entrée et l'historique de génération.
   • Modeleur Basé sur le Modèle ($D_m$) : Un modeleur appris (spécifiquement EAGLE3) utilisé comme solution de repli.
2. Prédiction du Rendement : Avant la vérification, un prédicteur de rendement léger ($g_\theta$), implémenté sous forme de perceptron multicouche (MLP), estime la longueur acceptée ($\hat{y}_t$) du brouillon de cache actuel.
   • Caractéristiques : Le prédicteur prend un vecteur de caractéristiques d'exécution ($\phi_t$) incluant la correspondance de suffixe, la longueur du brouillon, la position de décodage actuelle, l'historique récent et les indicateurs de structure de jetons.
   • Règle de Décision : Si le rendement prédit $\hat{y}_t$ dépasse un seuil $\tau$, le brouillon de cache est envoyé pour vérification. Sinon, le système bascule sur le modeleur basé sur le modèle.
3. Entraînement par Rejeu de Trace : Le prédicteur est entraîné via une procédure de rejeu. Pour chaque position de jeton dans une trace de génération du modèle cible, le système reconstruit l'état, génère un brouillon de cache, et calcule la longueur acceptée « oracle » ($y_t$) en comparant le brouillon avec la continuation réelle du modèle cible. Le modèle est entraîné par régression pour minimiser l'erreur quadratique entre la longueur prédite et la longueur acceptée réelle.

Principales Contributions

• Formulation : L'article formule la sélection de brouillon dépendante de l'état comme un problème d'allocation de vérification guidé par le rendement, définissant la « longueur acceptée » comme la variable de rendement principale.
• Algorithme : Il introduit le Décodage Vérifié Hybride, qui bascule dynamiquement entre le mode de brouillage par cache et le mode de brouillage basé sur le modèle en fonction d'une estimation de rendement pré-vérification.
• Procédure d'Entraînement : Il propose une méthode d'entraînement légère par rejeu qui dérive des signaux de supervision directement des traces de génération sans nécess avoir besoin d'un entraînement de modèle supplémentaire pour le prédicteur.
• Évaluation Complète : La méthode est évaluée sur trois LLM (Qwen3-8B, Qwen3-4B, Llama3.1-8B) et seize jeux de données couvrant les flux de travail agentiques, le codage, la génération structurée et le chat ouvert.
• Intégration Système : Les auteurs fournissent une analyse systématique des opportunités de cache, des rendements de vérification et des coûts d'exécution, incluant un prototype de service vLLM pour la validation du déploiement.

Résultats

• Performance : À travers 48 paires modèle-jeu de données, le Décodage Vérifié Hybride surpasse le Décodage Glouton (Greedy Decoding) dans 47 cas et SuffixDecoding dans 46 cas.
• Accélération : La méthode atteint une accélération moyenne de 2,73x par rapport à EAGLE3 (une base forte basée sur le modèle) sur l'ensemble des configurations.
• Charges de Travail Agentiques : L'approche est particulièrement efficace dans les tâches d'agent et d'édition de flux de travail (ex: Delegate-52, InstructEdit), où elle surpasse systématiquement EAGLE3 et les autres bases. Ces charges de travail bénéficient de motifs structurels récurrents que le cache exploite, tandis que le prédicteur filtre les incohérences dépendantes de l'état.
• Efficacité : L'analyse montre que la méthode réduit considérablement le nombre de cycles de décodage par 1 000 jetons (ex: de 571 pour EAGLE3 à 200 pour le Décodage Vérifié Hybride sur Llama3.1-8B) tout en maintenant des coûts par cycle comparables au brouillage basé sur le modèle.
• Précision du Prédicteur : Le prédicteur de rendement identifie avec succès les brouillons à haut rendement (définis par une longueur acceptée $\ge 6$) avec une précision allant de 78,2 % à 87,6 % et un rappel de 61,4 % à 79,8 % selon les modèles.

Signification et Revendications
L'article soutient que le goulot d'étranglement principal du décodage spéculatif n'est pas seulement la qualité du brouillon, mais le moment de la décision de vérification. En prédisant le rendement d'un brouillon sans paramètres avant la vérification, le Décodage Vérifié Hybride évite le surcoût de la vérification de correspondances de cache de faible valeur.

Les auteurs affirment que cette approche pointe vers la sélection de brouillon au moment de l'exécution (runtime draft selection) comme une direction prometteuse pour le décodage spéculatif. Ils démontrent que la structure des invites crée des opportunités de cache, mais que les brouillons à haut rendement sont concentrés dans un petit sous-ensemble de l'espace de brouillage. Le prédicteur appris isole efficacement ces opportunités de haute valeur, permettant au système d'amortir les coûts de vérification sur des préfixes acceptés plus longs. Les résultats suggèrent que pour les charges de travail structurées et agentiques, une approche hybride guidée par l'estimation du rendement peut nettement surpasser les stratégies purement basées sur le modèle ou purement basées sur le cache.