Décodage spéculatif : propositions, vérification et gains réels de vitesse

Pour produire une longue réponse, le modèle cible est généralement exécuté à nouveau après chaque token choisi afin de calculer les probabilités du suivant. Le décodage spéculatif propose d’abord une suite de candidats avec un calcul moins coûteux, puis les fait vérifier en parallèle par le modèle cible. Un tour de vérification peut valider plusieurs tokens et répartir entre eux le coût des étapes séquentielles les plus lourdes. L’article original de Leviathan et ses collègues présente un algorithme qui préserve la distribution d’échantillonnage du modèle cible.

Les préfixes dont dépend la génération autorégressive, ainsi que les limites de mesure du prefill, du decode et du débit dans les performances d’inférence, donnent les bases nécessaires. Il s’agit ici de réduire les appels au modèle cible pendant le decode et de comprendre quand cette réduction fait gagner du temps.

Des candidats connus permettent une vérification parallèle

En génération ordinaire, le choix du deuxième token dépend du premier, et celui du troisième dépend des deux précédents. Le cache KV conserve l’état du préfixe existant ; le modèle cible doit encore traiter chaque nouvelle position.

Soit $h$ le préfixe déjà validé, et $x_1,x_2,x_3$ les tokens proposés. Tous les préfixes candidats sont désormais connus : une passe causale du modèle cible peut calculer :

$$\begin{aligned} p_1&=p(\cdot\mid h),\\ p_2&=p(\cdot\mid h,x_1),\\ p_3&=p(\cdot\mid h,x_1,x_2),\\ p_4&=p(\cdot\mid h,x_1,x_2,x_3). \end{aligned}$$

On vérifie $x_1$ avec $p_1$, $x_2$ avec $p_2$, et ainsi de suite, en respectant le décalage entre logits et positions candidates. Si les trois tokens sont acceptés, on tire un token supplémentaire selon $p_4$. Si le deuxième est rejeté, seul le premier est conservé, puis un token de correction est ajouté à la deuxième position. Le troisième candidat initial et son résultat de vérification sont abandonnés, puisqu’ils dépendent du préfixe rejeté. EOS ou une limite de sortie peuvent terminer le tour plus tôt.

La vérification par la cible est parallèle ; les propositions d’une chaîne linéaire peuvent encore être produites séquentiellement. Vérifier davantage de positions ajoute du calcul. Le bénéfice dépend de la possibilité d’amortir la lecture des poids et de l’état historique.

Préserver la distribution par acceptation et rejet

La règle de la section 2.3 et de l’annexe A.1 de l’article original s’applique à une distribution cible normalisée $p$ et à la distribution réelle de proposition $q$, pour un même préfixe et les mêmes identifiants de tokens. Ici, $p$ intègre la température, le top-k, le top-p ou les autres transformations d’échantillonnage de la cible ; $q$ doit également correspondre à la procédure effectivement utilisée pour proposer les candidats.

Un candidat $x$ tiré selon $q$ est accepté avec la probabilité :

$$a(x)=\min\left(1,\frac{p(x)}{q(x)}\right).$$

Un token proposé a donc $q(x)>0$. Au premier rejet, le remplacement est tiré dans la masse de probabilité restante :

$$r(x)=\frac{\max(0,p(x)-q(x))}{\sum_y\max(0,p(y)-q(y))}.$$

Lorsque $p=q$, tous les candidats sont acceptés : la branche de correction dont le dénominateur serait nul n’est jamais empruntée. L’application correcte de ces règles à chaque préfixe préserve la distribution des séquences de la cible. Rejeter des candidats peu probables, puis refaire simplement un tirage selon $p$, modifie généralement cette distribution.

Retrouver toute la masse de probabilité avec trois tokens

Prenons un vocabulaire construit de trois tokens A, B, C, avec $p=(0.5,0.3,0.2)$ et $q=(0.6,0.1,0.3)$. Leurs probabilités d’acceptation sont $5/6,1,2/3$. En les multipliant par les probabilités de proposition, on obtient une masse acceptée de $(0.5,0.1,0.2)$, soit un taux total de $0.8$. Les $0.2$ restants reviennent entièrement à B : on retrouve $(0.5,0.3,0.2)$.

Ce code Python 3 vérifie les probabilités avec des fractions exactes, puis rejoue un tour de vérification avec des candidats et des tirages fixés. Ici, $p$ et $q$ sont des distributions normalisées sur le même vocabulaire fini ; chaque candidat a une probabilité $q(x)>0$ et les valeurs tirées appartiennent à $[0,1)$. Pour simplifier le calcul, les distributions restent identiques quel que soit le préfixe ; celles d’un vrai modèle évoluent avec lui. Au premier rejet, le remplacement est tiré selon la distribution de correction. Si tous les candidats sont acceptés, un token supplémentaire est tiré selon $p$. Lorsque $p=q$, la distribution de correction n’est pas calculée. Avec les entrées présentées, C est rejeté et remplacé par B avec une probabilité de 1.

from fractions import Fraction as F

tokens = ['A', 'B', 'C']
p = dict(zip(tokens, map(F, ['0.5', '0.3', '0.2'])))
q = dict(zip(tokens, map(F, ['0.6', '0.1', '0.3'])))
accepted = {x: min(p[x], q[x]) for x in tokens}
alpha = sum(accepted.values())
if alpha < 1:
    residual = {x: max(p[x] - q[x], 0) / (1 - alpha) for x in tokens}
    restored = {x: accepted[x] + (1 - alpha) * residual[x] for x in tokens}
else:
    residual = None
    restored = accepted
assert restored == p
print('accepted mass:', [float(accepted[x]) for x in tokens])
print('acceptance:', float(alpha))
print('residual:', None if residual is None else [float(residual[x]) for x in tokens])
print('reconstructed:', [float(restored[x]) for x in tokens])

def sample(distribution, u):
    assert 0 <= u < 1
    cumulative = F(0)
    for x in tokens:
        cumulative += distribution[x]
        if u < cumulative:
            return x
    raise ValueError('distribution must sum to 1')

draft = ['A', 'C', 'B']
draws = list(map(F, ['0.7', '0.9', '0.2']))
final_draw = F('0.2')
assert len(draft) == len(draws)
emitted = []
for i, (x, u) in enumerate(zip(draft, draws)):
    assert q[x] > 0 and 0 <= u < 1
    threshold = min(F(1), p[x] / q[x])
    ok = u < threshold
    print(f'{x}: u={float(u):.1f}, threshold={float(threshold):.3f}, accept={ok}')
    if not ok:
        assert residual is not None
        emitted.append(sample(residual, final_draw))
        print('discard:', draft[i:])
        break
    emitted.append(x)
else:
    bonus = sample(p, final_draw)
    emitted.append(bonus)
    print('bonus:', bonus)
print('emit:', emitted)

accepted mass: [0.5, 0.1, 0.2]
acceptance: 0.8
residual: [0.0, 1.0, 0.0]
reconstructed: [0.5, 0.3, 0.2]
A: u=0.7, threshold=0.833, accept=True
C: u=0.9, threshold=0.667, accept=False
discard: ['C', 'B']
emit: ['A', 'B']

Le tour valide A, B. Même si le dernier B proposé coïncide avec le token de correction, son état initial dépendait du préfixe A, C : il doit être abandonné.

Une distribution identique n’exige pas des réponses identiques mot pour mot avec la même graine : les algorithmes peuvent consommer les nombres aléatoires dans un ordre différent. La documentation de vLLM sur les garanties sans perte conserve aussi les conditions liées à la précision flottante, à la taille des lots et à la stabilité des logprobs. La garantie porte sur le décodage d’une cible donnée ; les changements introduits par sa quantification ou par un cache approximatif demandent une comparaison distincte.

Une bonne proposition doit aussi coûter peu

Pour un préfixe fixé, le taux d’acceptation vaut $\sum_x\min(p(x),q(x))$. Des distributions proches favorisent l’acceptation. La capacité du modèle de proposition à répondre seul à des questions ne remplace pas cette mesure.

Un budget simplifié permet d’estimer si la spéculation mérite un essai. Supposons que chaque tour propose $\gamma$ candidats, que chaque position ait une probabilité conditionnelle d’acceptation $\alpha$, que les événements d’acceptation soient indépendants et identiquement distribués, et qu’aucun arrêt anticipé ne survienne. En comptant le token de correction ou le token supplémentaire, le nombre moyen de tokens validés par tour est :

$$E[N]=1+\alpha+\alpha^2+\cdots+\alpha^\gamma.$$

Ce sont les hypothèses simplificatrices de la section 3.1 de l’article original. Quand l’acceptation varie selon la position et la tâche, il faut mesurer les tokens effectivement validés par tour plutôt qu’insérer un taux moyen global sans vérifier ces conditions.

Les durées suivantes sont toutes hypothétiques : le decode ordinaire de la cible prend 10 ms par token, $\gamma=4$, la vérification d’un tour entier prend 12 ms et la gestion de l’état prend 2 ms. Avec un coût de proposition $d$ ms par token, sans chevauchement de ces étapes, un cycle coûte $4d+12+2$ ms. Sur une génération suffisamment longue, ce budget divisé par $E[N]$ donne le temps moyen par token sur l’ensemble des tours.

gamma = 4
baseline_ms = 10
verify_ms = 12
state_ms = 2
for alpha, draft_ms in [(0.8, 1), (0.9, 3)]:
    expected = sum(alpha ** j for j in range(gamma + 1))
    cycle_ms = gamma * draft_ms + verify_ms + state_ms
    per_token = cycle_ms / expected
    speedup = baseline_ms / per_token
    print(f'alpha={alpha:.1f} tokens={expected:.4f} cycle_ms={cycle_ms} '
          f'ms/token={per_token:.3f} speedup={speedup:.3f}x')

alpha=0.8 tokens=3.3616 cycle_ms=18 ms/token=5.355 speedup=1.868x
alpha=0.9 tokens=4.0951 cycle_ms=26 ms/token=6.349 speedup=1.575x

Le premier modèle de proposition prend 1 ms par token, le second 3 ms. Le second valide davantage de tokens en moyenne, mais reste plus lent : sa vitesse atteint environ 1,575 fois celle de référence, contre 1,868 pour le premier. Le temps réel de vérification peut aussi varier avec le nombre de candidats, la taille des lots, le contexte et la forme de l’arbre. Insérer les coûts mesurés avant de régler la longueur proposée permet de considérer ensemble acceptation, vitesse de proposition, vérification et gestion de l’état.

Chaînes, arbres et auto-spéculation décrivent des choix différents

La prépublication du 21 septembre 2026 sur l’adaptation à DeepSeek-V4 traite des chaînes linéaires et des arbres de candidats. L’article original de LayerSkip fournit un exemple d’auto-spéculation : l’entraînement emploie un dropout par couche et une fonction de perte pour la sortie anticipée ; à l’inférence, les premières couches proposent les tokens, puis les couches restantes les vérifient et les corrigent. On ne peut donc pas supposer qu’un modèle quelconque, sans adaptation, offre de bonnes sorties anticipées.

Choix	Organisation des candidats ou du calcul	Coût à prendre en compte
Chaîne linéaire	Un seul chemin continu de candidats par tour	Un rejet précoce gaspille les candidats suivants
Arbre de candidats	Plusieurs suites partent de préfixes partagés, avec un nombre borné de nœuds à vérifier	Attention causale adaptée à l’arbre, état des branches et validation du chemin
Auto-spéculation	Une partie du même modèle propose ; le calcul complet de la cible vérifie	Capacité de sortie anticipée, réutilisation du calcul et retour à l’état antérieur

Les deux premières lignes décrivent la forme des candidats ; la troisième indique l’origine des propositions. Un arbre ne valide finalement qu’un chemin continu, avec des règles d’acceptation et d’échantillonnage qui doivent préserver la distribution cible. La correction d’un candidat unique sur une chaîne ne s’applique pas telle quelle à un arbre quelconque, et choisir la branche la plus probable n’équivaut pas à échantillonner selon la cible. L’objectif diffère du beam search, qui explore plusieurs préfixes pour optimiser un score de séquence.

L’état KV doit suivre le chemin accepté

La note sur le cache KV explique sa réutilisation et sa compression. La spéculation exige en plus que son contenu corresponde au préfixe validé : dans une chaîne, supprimer le suffixe rejeté ; dans un arbre, ne rendre visibles que le contexte validé et les ancêtres du nœud, jamais ses branches sœurs. Les préfixes partagés peuvent être réutilisés, mais les états temporaires doivent rester isolés après la bifurcation. Si un nouveau token de correction ou un token supplémentaire n’a pas encore traversé le modèle, son état KV doit être calculé ultérieurement, sans reprendre celui d’un candidat rejeté.

Les sections 2–4 de la prépublication DeepSeek-V4 expliquent que CSA (Compressed Sparse Attention) et HCA (Heavily Compressed Attention) compriment aussi l’historique le long de la séquence. Des branches peuvent produire des états comprimés différents : un masque d’attention en arbre ne suffit pas. L’implémentation isole les branches dans un scratch pad temporaire, puis actualise le KV, les états comprimés et les buffers intermédiaires du chemin choisi. Cette compression entre positions diffère de MLA (attention latente multi-têtes), qui réduit la largeur de la représentation en cache de chaque token.

L’article teste DeepSeek-V4-Flash sur huit GPU NVIDIA, avec des budgets de vérification de 5–8, des tailles de lots de 1–64 et les jeux GSM8K, MBPP et ShareGPT. Il rapporte un gain maximal de débit du decode d’environ 18,5 % par rapport à la spéculation linéaire de même budget, sur ShareGPT avec s3_k2_d6 et un lot de 4. La référence utilise donc déjà la spéculation. Lorsque le budget augmente, la longueur acceptée peut continuer à croître alors que le débit plafonne : la gestion des branches et l’actualisation de l’état absorbent les gains.

Comparer à charge et qualité équivalentes

La documentation officielle de vLLM présente les charges à QPS faible ou moyen, limitées par la bande passante mémoire, comme un cas où réduire la latence entre tokens. Vérifier d’abord la compatibilité du modèle, du composant de proposition et du backend à l’aide des runtimes d’inférence locale. Effectuer deux comparaisons : spéculation désactivée puis activée ; ensuite, si la spéculation linéaire est déjà disponible, chaînes et arbres à budget de vérification égal.

Fixer le checkpoint cible, la précision, le tokenizer, le modèle de prompt, les règles d’échantillonnage et d’arrêt, la politique de cache, le matériel et la version du runtime. Utiliser les mêmes prompts et la même distribution de longueurs d’entrée, relever les longueurs réellement produites, puis comparer à concurrence égale ou à taux d’arrivée égal dans des essais distincts. Mesurer séparément la latence à faible charge et le débit à saturation.

À relever	Comment interpréter le gain
Tokens validés par tour, nombre de candidats et définition du taux d’acceptation	Distinguer l’acceptation des propositions de la sortie utile ; le nombre total de nœuds ne donne pas la longueur du chemin accepté
Durée des propositions, de la vérification et de l’actualisation de l’état, mémoire GPU maximale	Vérifier si les tokens supplémentaires compensent le travail ajouté ; inclure les poids du modèle de proposition et l’état temporaire des branches
Médiane et p95 du TTFT, des intervalles entre tokens et de la latence totale	La spéculation peut produire par salves ; la vitesse moyenne masque les pauses entre salves
Tokens de sortie finale par seconde, requêtes terminées par seconde, erreurs et délais dépassés	Les candidats rejetés ne comptent pas dans le débit utile ; conserver les requêtes échouées
Exactitude, validité du format et taux d’achèvement sur les mêmes tâches	Distinguer la préservation de l’échantillonnage cible des changements de qualité dus à la précision, au cache ou aux réglages d’échantillonnage

L’acceptation mesure la proximité des propositions avec la cible ; le temps d’un cycle divisé par les tokens validés relie cette proximité à la vitesse. Employer les limites de mesure de la note sur les performances d’inférence permet de situer le gain : dans le decode, dans la requête entière ou dans le service dans son ensemble.

Mes lectures · Les notes ouvertes sont mémorisées dans ce navigateur.