Aller au contenu principal
Yaniv Leviathan et al.

Un petit modèle propose des tokens, le grand les vérifie en une passe: sortie identique, inférence plus rapide. ICML 2023, gratuit en ligne.

Fast Inference from Transformers via Speculative Decoding

Inférence rapide à partir de Transformers via le décodage spéculatif

Yaniv Leviathan \* 1 Matan Kalman \* 1 Yossi Matias 1

Résumé

L'inférence à partir de grands modèles autorégressifs comme les Transformers est lente — le décodage de KK jetons nécessite KK exécutions sérielles du modèle. Dans ce travail, nous introduisons le décodage spéculatif — un algorithme pour échantillonner à partir de modèles autorégressifs plus rapidement sans aucune modification des sorties, en calculant plusieurs jetons en parallèle. Au cœur de notre approche se trouvent les observations selon lesquelles (1) les tâches difficiles de modélisation du langage incluent souvent des sous-tâches plus faciles qui peuvent être bien approximées par des modèles plus efficaces, et (2) en utilisant l'exécution spéculative et une nouvelle méthode d'échantillonnage, nous pouvons rendre le décodage exact à partir des grands modèles plus rapide, en les exécutant en parallèle sur les sorties des modèles d'approximation, générant potentiellement plusieurs jetons simultanément, et sans modifier la distribution. Notre méthode peut accélérer les modèles existants prêts à l'emploi sans réentraînement ni modification de l'architecture. Nous la démontrons sur T5-XXL et montrons une accélération de 2X à 3X par rapport à l'implémentation standard T5X, avec des sorties identiques.

1. Introduction

Les grands modèles autorégressifs, notamment les grands Transformers (Vaswani et al., [2017]), sont bien plus performants que les modèles plus petits, comme cela a été démontré d'innombrables fois ces dernières années, par exemple dans les domaines du texte ou de l'image, comme GPT-3 (Brown et al., [2020]), LaMDA (Thoppilan et al., [2022]), Parti (Yu et al., [2022]) et PaLM (Chowdhery et al., [2022]). Malheureusement, une seule étape de décodage de ces modèles plus grands est nettement plus lente qu'une étape de leurs homologues plus petits, et pour aggraver les choses, ces étapes sont effectuées en série — le décodage de KK jetons nécessite KK exécutions sérielles du modèle.

Étant donné l'importance des grands modèles autorégressifs et en particulier des grands Transformers, plusieurs approches ont été développées pour rendre l'inférence à partir de ceux-ci plus rapide. Certaines approches visent à réduire le coût d'inférence pour toutes les entrées de manière égale (par exemple Hinton et al., [2015], Jaszczur et al., [2021], Hubara et al., [2016], So et al., [2021], Shazeer [2019]). D'autres approches découlent de l'observation que toutes les étapes d'inférence ne se ressemblent pas — certaines nécessitent un très grand modèle, tandis que d'autres peuvent être bien approximées par des modèles plus efficaces. Ces méthodes de calcul adaptatif (par exemple Han et al., [2021], Sukhbaatar et al., [2019], Schuster et al., [2021], Scardapane et al., [2020], Bapna et al., [2020], Elbayad et al., [2019], Schwartz et al., [2020]) visent à utiliser moins de ressources de calcul pour les étapes d'inférence plus faciles. Bien que nombre de ces solutions se soient révélées extrêmement efficaces en pratique, elles nécessitent généralement de modifier l'architecture du modèle, de modifier la procédure d'entraînement et de réentraîner les modèles, et ne maintiennent pas des sorties identiques.

Contribution égale 1Google Research, Mountain View, CA, USA. Correspondance : Yaniv Leviathan leviathan@google.com.

L'observation clé ci-dessus, selon laquelle certaines étapes d'inférence sont « plus difficiles » et d'autres « plus faciles », est également un motivateur clé de notre travail. Nous observons en outre que l'inférence à partir de grands modèles n'est souvent pas limitée par les opérations arithmétiques, mais plutôt par la bande passante mémoire et la communication, de sorte que des ressources de calcul supplémentaires pourraient être disponibles. Par conséquent, nous suggérons d'augmenter la concurrence comme approche complémentaire à l'utilisation d'une quantité adaptative de calcul. Plus précisément, nous sommes en mesure d'accélérer l'inférence sans modifier les architectures des modèles, sans modifier les procédures d'entraînement ni avoir besoin de réentraîner les modèles, et sans modifier la distribution de sortie du modèle. Cela est accompli via l'exécution spéculative.

L'exécution spéculative (Burton, [1985], Hennessy & Patterson, [2012]) est une technique d'optimisation, courante dans les processeurs, où une tâche est effectuée en parallèle de la vérification de sa nécessité réelle — le gain étant une concurrence accrue. Un exemple bien connu d'exécution spéculative est la prédiction de branchement. Pour que l'exécution spéculative soit efficace, nous avons besoin d'un mécanisme efficace pour suggérer des tâches à exécuter qui sont susceptibles d'être nécessaires. Dans ce travail, nous généralisons l'exécution spéculative au cadre stochastique — où une tâche peut être nécessaire avec une certaine probabilité. En appliquant cela au décodage à partir de modèles autorégressifs comme les Transformers, nous échantillonnons des générations à partir de modèles d'approximation plus efficaces comme préfixes spéculatifs pour les modèles cibles plus lents. Avec une nouvelle méthode d'échantillonnage, l'échantillonnage spéculatif, nous maximisons la probabilité que ces tâches spéculatives

Figure 1. Notre technique illustrée dans le cas de la modélisation de langage inconditionnelle. Chaque ligne représente une itération de l'algorithme. Les tokens en vert sont les suggestions faites par le modèle d'approximation (ici, un décodeur Transformer de type GPT avec 6M de paramètres entraîné sur 1m1b avec 8k tokens) que le modèle cible (ici, un décodeur Transformer de type GPT avec 97M de paramètres dans le même cadre) a acceptées, tandis que les tokens rouges et bleus sont respectivement les suggestions rejetées et leurs corrections. Par exemple, dans la première ligne, le modèle cible n'a été exécuté qu'une seule fois, et 5 tokens ont été générés.
Figure 1. Notre technique illustrée dans le cas de la modélisation de langage inconditionnelle. Chaque ligne représente une itération de l'algorithme. Les tokens en vert sont les suggestions faites par le modèle d'approximation (ici, un décodeur Transformer de type GPT avec 6M de paramètres entraîné sur 1m1b avec 8k tokens) que le modèle cible (ici, un décodeur Transformer de type GPT avec 97M de paramètres dans le même cadre) a acceptées, tandis que les tokens rouges et bleus sont respectivement les suggestions rejetées et leurs corrections. Par exemple, dans la première ligne, le modèle cible n'a été exécuté qu'une seule fois, et 5 tokens ont été générés.

soient acceptées, tout en garantissant que les sorties de notre système ont la même distribution que celles du modèle cible seul. Par exemple, la phrase de la Figure 1 composée de 38 jetons a été générée par notre méthode avec seulement 9 exécutions sérielles d'un modèle cible plus grand (97M de paramètres) grâce à un modèle d'approximation plus petit et plus efficace (6M de paramètres), tandis que la probabilité de la générer est inchangée.

Nous analysons notre méthode sur une variété de tâches et de tailles de modèles : génération non conditionnelle à partir d'un modèle de type GPT de 97M de paramètres entraîné sur 1m1b, traduction de l'anglais vers l'allemand et résumé d'articles de presse avec un modèle T5-XXL de 11B de paramètres, et une tâche de dialogue avec un modèle LaMDA de 137B de paramètres. Nous implémentons notre méthode et comparons les temps réels pour T5-XXL à ceux de l'implémentation robuste T5X (Roberts et al., 2022), montrant une amélioration de la latence prête à l'emploi de 2X à 3X, sans aucune modification des sorties (Section 4).

Notre méthode est facile à employer dans des contextes de production réels, ne nécessite pas d'entraîner de nouveaux modèles et ne modifie pas les sorties. Par conséquent, dans les situations courantes où la bande passante mémoire est le goulot d'étranglement et où des ressources de calcul sont disponibles, elle peut constituer un bon choix par défaut pour accélérer l'échantillonnage à partir de modèles autorégressifs comme les Transformers.

Pour résumer, nos principales contributions sont : (1) Une généralisation de l'exécution spéculative au cadre stochastique, avec une nouvelle méthode d'échantillonnage que nous appelons échantillonnage spéculatif, et (2) Un mécanisme de décodage que nous appelons décodage spéculatif qui peut accélérer le décodage à partir de modèles autorégressifs, sans aucune modification des architectures des modèles, des régimes d'entraînement et des distributions de sortie.

2. Décodage spéculatif

2.1. Vue d'ensemble

Soit MpM_{p} le modèle cible, à partir duquel nous cherchons à accélérer l'inférence, et p(xt∣x<t)p(x_{t}|x_{< t}) la distribution que nous obtenons du modèle pour un préfixe x<tx_{< t}. Soit MqM_{q} un modèle d'approximation plus efficace pour la même tâche, et désignons par q(xt∣x<t)q(x_{t}|x_{< t}) la distribution que nous obtenons du modèle pour un préfixe x<tx_{< t}. L'idée centrale est de (1) utiliser le modèle plus efficace MqM_{q} pour générer γ∈Z+\gamma \in \mathbb{Z}^{+} complétions (voir Section 3.5 pour savoir comment choisir ce paramètre de manière optimale), puis (2) utiliser le modèle cible MpM_{p} pour évaluer toutes les suppositions et leurs probabilités respectives issues de MqM_{q} en parallèle, en acceptant toutes celles qui peuvent conduire à une distribution identique, et (3) échantillonner un jeton supplémentaire à partir d'une distribution ajustée pour corriger le premier qui a été rejeté, ou pour en ajouter un supplémentaire s'ils sont tous acceptés. Ainsi, chaque exécution parallèle du modèle cible MpM_{p} produira au moins un nouveau jeton (de sorte que le nombre d'exécutions sérielles du modèle cible ne pourra jamais, même dans le pire des cas, être supérieur à celui de la méthode autorégressive simple), mais elle peut potentiellement générer de nombreux nouveaux jetons, jusqu'à γ+1\gamma +1, selon la qualité de l'approximation de MpM_{p} par MqM_{q}.

2.2. Échantillonnage standardisé

Premièrement, notons que bien qu'il existe de nombreuses méthodes et paramètres d'échantillonnage, comme argmax, top-k, nucleus, et la fixation d'une température, et que les implémentations populaires les traitent généralement différemment au niveau des logits, elles peuvent toutes facilement être ramenées à un échantillonnage standard à partir d'une distribution de probabilité ajustée. Par exemple, l'échantillonnage argmax équivaut à mettre à zéro les éléments non maximaux de la distribution et à normaliser. Nous pouvons donc ne traiter que de l'échantillonnage standard à partir d'une distribution de probabilité, et ramener tous les autres types d'échantillonnage à ce cadre. Dans la suite, nous supposerons que p(x)p(x) et q(x)q(x) sont les distributions issues respectivement de MpM_{p} et MqM_{q}, ajustées pour la méthode d'échantillonnage.

2.3. Échantillonnage spéculatif

Pour échantillonner x∼p(x)x\sim p(x), nous échantillonnons plutôt x∼q(x)x\sim q(x), en le conservant si q(x)≤p(x)q(x)\leq p(x), et dans le cas où q(x)>p(x)q(x) > p(x), nous rejetons l'échantillon avec probabilité 1−p(x)q(x)1 - \frac{p(x)}{q(x)} et échantillonnons xx à nouveau à partir d'une distribution ajustée p′(x)=norm(max(0,p(x)−q(x)))p^{\prime}(x) = norm(max(0,p(x) - q(x))). Il est facile de montrer (voir Annexe [A.1]) que pour toutes distributions p(x)p(x) et q(x)q(x), et xx échantillonné de cette manière, on a bien x∼p(x)x\sim p(x).

Étant donné la distribution q(x)q(x) obtenue en exécutant MqM_{q} sur un prefixprefix de conditionnement, nous pouvons échantillonner un token x1∼q(x)x_{1}\sim q(x). Nous calculons ensuite la distribution p(x)p(x) en exécutant MpM_{p} sur prefixprefix tout en calculant en parallèle, de manière spéculative, la distribution du token suivant x2x_{2} en exécutant MpM_{p} sur prefix+[x1]prefix + [x_{1}]. Une fois les deux calculs terminés, nous procédons comme ci-dessus : si x1x_{1} est rejeté, nous écartons le calcul de x2x_{2} et ré-échantillonnons x1x_{1} à partir d'une distribution ajustée, et si x1x_{1} est accepté, nous conservons les deux tokens. L'algorithme [I] généralise cette idée pour échantillonner entre 1 et γ+1\gamma +1 tokens à la fois.

Algorithme 1 SpeculativeDecodingStep

3. Analyse

3.1. Nombre de tokens générés

Analysons le facteur de réduction du nombre d'appels séquentiels au modèle cible, ou de manière équivalente, le nombre attendu de tokens produits par une seule exécution de l'algorithme [I]

Définition 3.1. Le taux d'acceptation βx<t\beta_{x< t}, étant donné un préfixe x<tx_{< t}, est la probabilité d'accepter xt∼q(xt∣x<t)x_{t}\sim q(x_{t}|x_{< t}) par échantillonnage spéculatif, conformément à la Section [2.3] :

E(β)E(\beta) est alors une mesure naturelle de la qualité de l'approximation de MpM_{p} par MqM_{q}. Si nous faisons l'hypothèse simplificatrice que les β\beta sont i.i.d., et notons α=E(β)\alpha = E(\beta), alors le nombre de tokens produits par une seule exécution de l'algorithme [I] est une variable géométrique plafonnée, de probabilité de succès 1−α1 - \alpha et de plafond γ+1\gamma +1, et le nombre attendu de tokens générés par l'algorithme [I] satisfait l'équation [I]. Voir la Figure [2]

E(#generated tokens)=1−αγ+11−α(1)E(\# \text{generated tokens}) = \frac{1 - \alpha^{\gamma + 1}}{1 - \alpha} \quad (1)
Figure 2. Nombre attendu de jetons générés par l'algorithme [I] en fonction de \alpha pour diverses valeurs de \gamma.
Figure 2. Nombre attendu de jetons générés par l'algorithme [I] en fonction de α\alpha pour diverses valeurs de γ\gamma.

3.2. Calcul de α\alpha

Nous allons maintenant dériver une formule simple pour calculer α\alpha étant donné un préfixe et les deux modèles MpM_{p} et MqM_{q}. Nous commençons par définir une divergence naturelle DLKD_{LK} :

Définition 3.2. DLK(p,q)=∑x∣p(x)−M(x)∣=∑x∣q(x)−M(x)∣D_{LK}(p,q) = \sum_{x}|p(x) - M(x)| = \sum_{x}|q(x) - M(x)| où M(x)=p(x)+q(x)2M(x) = \frac{p(x) + q(x)}{2}.

Lemme 3.3. DLK(p,q)=1−∑xmin⁡(p(x),q(x))D_{LK}(p,q) = 1 - \sum_{x}\min (p(x),q(x))

Preuve. DLK(p,q)=∑x∣p(x)−M(x)∣=∑x∣p−q∣2=D_{LK}(p,q) = \sum_{x}|p(x) - M(x)| = \sum_{x}\frac{|p - q|}{2} = 1−∑xp+q−∣p−q∣2=1−∑xmin⁡(p(x),q(x))1 - \sum_{x}\frac{p + q - |p - q|}{2} = 1 - \sum_{x}\min (p(x),q(x))

Du lemme [3.3], nous obtenons immédiatement les résultats suivants : Corollaire 3.4. DLK(p,q)D_{LK}(p,q) est une divergence symétrique dans [0,1][0,1] . DLK(p,q)=0  ⟺  p=qD_{LK}(p,q) = 0 \iff p = q . DLK(p,q)=1  ⟺  pD_{LK}(p,q) = 1 \iff p et qq ont des supports disjoints.

Théorème 3.5. β=1−DLK(p,q)\beta = 1 - D_{LK}(p,q)

Preuve.β=Ex∼q(x){1q(x)≤p(x)p(x)q(x)q(x)>p(x)Ex∼q(x)min⁡(1,p(x)q(x))=∑xmin⁡(p(x),q(x))(3)\begin{array}{rcl}{\mathrm{Preuve.}\beta} & = & {E_{x\sim q(x)}\left\{ \begin{array}{ll}1 & q(x)\leq p(x)\\ \frac{p(x)}{q(x)} & q(x) > p(x) \end{array} \right.}\\ {E_{x\sim q(x)}\min (1,\frac{p(x)}{q(x)}) = \sum_{x}\min (p(x),q(x))} \end{array} \quad (3)

Finalement, nous obtenons :

Corollaire 3.6. α=1−E(DLK(p,q))=E(min⁡(p,q))\alpha = 1 - E(D_{LK}(p,q)) = E(\min (p,q))

Voir le tableau 3 pour les valeurs de α\alpha observées empiriquement dans nos expériences.

3.3. Amélioration du temps d'exécution

Nous avons montré que, sous l'hypothèse i.i.d., notre algorithme réduit le nombre d'appels au modèle cible d'un facteur 1−αγ+11−α\frac{1 - \alpha^{\gamma + 1}}{1 - \alpha} . Notons que l'exécution spéculative en général, et notre algorithme en particulier, supposent que nous disposons de suffisamment de ressources de calcul pour soutenir la concurrence accrue (section 3.4). Pour l'analyse du temps d'exécution, nous supposerons que nous pouvons exécuter γ+1\gamma + 1 évaluations concurrentes de MpM_{p} en parallèle sans augmenter le temps d'exécution. Pour obtenir l'amélioration totale du temps d'exécution, nous considérons maintenant le coût d'exécution du modèle d'approximation MqM_{q} .

Définition 3.7. Soit cc , le coefficient de coût, le rapport entre le temps d'une seule exécution de MqM_{q} et le temps d'une seule exécution de MpM_{p} .

Notons que, contrairement à α\alpha qui est une propriété intrinsèque des modèles et de la tâche, la valeur de cc dépend de la configuration matérielle et des détails d'implémentation logicielle. Dans nos expériences, où MqM_{q} est typiquement de quelques ordres de grandeur plus petit que MpM_{p} , cc était toujours inférieur à 0,05 et souvent négligeable, proche de 0.

Théorème 3.8. Le facteur d'amélioration attendu du temps d'exécution total par l'algorithme 1 est 1−αγ+1(1−α)(γc+1)\frac{1 - \alpha^{\gamma + 1}}{(1 - \alpha)(\gamma c + 1)} .

Preuve. Notons TT le coût d'exécution d'une seule étape de MpM_{p} . Maintenant, chaque exécution de l'algorithme 1 coûte Tcγ+TT c\gamma + T (pour l'exécution du modèle d'approximation MqM_{q} fois et l'exécution de MpM_{p} une fois) et, d'après l'équation (1), produit 1−αγ+11−α\frac{1 - \alpha^{\gamma + 1}}{1 - \alpha} tokens en moyenne. Ainsi, le coût attendu global pour produire un token avec l'algorithme 1 est (cγ+1)(1−α)1−αγ+1T\frac{(c\gamma + 1)(1 - \alpha)}{1 - \alpha^{\gamma + 1}} T . Puisque le coût de production d'un seul token avec l'algorithme de décodage standard est TT , nous obtenons le résultat souhaité. □\square

Notons que le théorème 3.8 suppose des générations suffisamment longues (par exemple, puisque nous exécutons MpM_{p} au moins une fois, le facteur d'amélioration est plafonné par le nombre de tokens générés).

Corollaire 3.9. Si α>c\alpha >c , il existe γ\gamma pour lequel nous obtiendrons une amélioration, et le facteur d'amélioration sera d'au moins 1+α1+c\frac{1 + \alpha}{1 + c} .

Preuve. Si nous obtenons une amélioration pour γ\gamma , nous obtiendrons également une amélioration pour tout 0<γ∗<γ0 < \gamma^{*} < \gamma , donc pour que notre méthode produise une amélioration, nous pouvons évaluer le théorème 3.8 pour γ=1\gamma = 1 , ce qui donne 1−α2(1−α)(c+1)=1+α1+c\frac{1 - \alpha^{2}}{(1 - \alpha)(c + 1)} = \frac{1 + \alpha}{1 + c} . □\square

3.4. Nombre d'opérations arithmétiques

L'algorithme 1 effectue γ+1\gamma +1 exécutions de MpM_{p} en parallèle, donc le nombre d'opérations arithmétiques concurrentes augmente d'un facteur γ+1\gamma +1 . Maintenant, puisque l'algorithme 1 produit au plus γ+1\gamma +1 tokens par exécution, le nombre total d'opérations arithmétiques peut être supérieur à celui de l'algorithme de décodage standard. Lorsque nous acceptons l'échantillon de MqM_{q} , la concurrence accrue est « gratuite » et le nombre total d'opérations n'est pas augmenté. En revanche, lorsque nous rejetons une conjecture, le calcul est gaspillé. Analysons maintenant l'effet de notre méthode sur le nombre total d'opérations arithmétiques.

Définition 3.10. Soit c^\hat{c} le rapport entre le nombre d'opérations arithmétiques par token du modèle d'approximation MqM_{q} et celui du modèle cible MpM_{p} .

Théorème 3.11. Le facteur d'augmentation attendu du nombre total d'opérations de l'algorithme 1 est (1−α)(γc+γ+1)1−αγ+1\frac{(1 - \alpha)(\gamma c + \gamma + 1)}{1 - \alpha^{\gamma + 1}} .

Preuve. Notons T^\hat{T} le nombre d'opérations arithmétiques effectuées par une base de décodage standard par token, c'est-à-dire le nombre d'opérations d'une seule exécution de MpM_{p} . Alors une seule itération de l'algorithme 1 coûte T^c^γ+T^(γ+1)\hat{T} \hat{c} \gamma + \hat{T} (\gamma + 1) opérations (pour γ\gamma exécutions de MqM_{q} et γ+1\gamma + 1 exécutions parallèles de MpM_{p} ). En divisant par le nombre attendu de tokens produits par l'algorithme 1, c'est-à-dire l'équation (1), et par T^\hat{T} , nous obtenons le résultat souhaité. □\square

Si α\alpha est faible, l'augmentation du nombre d'opérations arithmétiques est élevée, et vice versa. Notons que, pour les décodeurs Transformer, le nombre total d'opérations arithmétiques effectuées par l'algorithme 1 (sans compter les exécutions de MqM_{q} ) peut être majoré par celui d'une seule exécution d'un encodeur Transformer de même taille.

Contrairement au nombre total d’opérations arithmétiques, le nombre total d’accès mémoire peut diminuer avec notre méthode. Plus précisément, les poids du modèle cible et le cache KV peuvent être lus une seule fois par exécution de l’algorithme 1, de sorte que le nombre d’accès mémoire pour les lire est réduit d’un facteur 1−αγ+11−α\frac{1 - \alpha^{\gamma + 1}}{1 - \alpha}, d’après l’équation (1).

3.5. Choix de γ\gamma

Étant donnés cc et α\alpha, et en supposant des ressources de calcul suffisantes (voir section 3.4), le γ\gamma optimal est celui qui maximise l’équation d’amélioration du temps réel (théorème 3.8) :

Figure 3. Le \gamma optimal en fonction de \alpha pour diverses valeurs de c.
Figure 3. Le γ\gamma optimal en fonction de α\alpha pour diverses valeurs de cc.

1−αγ+1(1−α)(γc+1)\frac{1 - \alpha^{\gamma + 1}}{(1 - \alpha)(\gamma c + 1)}. Comme γ\gamma est un entier, il peut être facilement trouvé numériquement, voir figure 3

Le tableau 1 et la figure 4 illustrent le compromis entre la vitesse d’inférence et le nombre total d’opérations arithmétiques pour diverses valeurs de α\alpha et γ\gamma, en supposant c=c^=0c = \hat{c} = 0. La figure 5 montre un diagramme de trace simplifié.

αγOPÉRATIONSVITESSE
0,621,53X1,96X
0,731,58X2,53X
0,821,23X2,44X
0,851,63X3,69X
0,921,11X2,71X
0,9101,60X6,86X
Tableau 1. Le nombre total d'opérations arithmétiques et la vitesse d'inférence par rapport à la référence, pour différentes valeurs de γ\gamma et α\alpha, en supposant c=c^=0c = \hat{c} = 0

Au lieu de choisir une seule valeur pour γ\gamma en fonction de α\alpha, comme les β\beta ne sont pas constants, nous pourrions obtenir une amélioration supplémentaire en prédisant la valeur de β\beta et en faisant varier en conséquence la valeur de γ\gamma pendant l’exécution de l’algorithme 1. Pour obtenir une borne supérieure du facteur d’amélioration supplémentaire, supposons que nous disposions d’un oracle pour γ\gamma. Nous aurions alors E(#generatedtokens)=11−αE(\# generated tokens) = \frac{1}{1 - \alpha}. Pour des valeurs typiques de cc et α\alpha, et en supposant des ressources de calcul non bornées, le facteur d’amélioration du temps réel renforcé peut être jusqu’à ∼60%\sim 60\% plus élevé que le facteur d’amélioration avec un γ\gamma fixe. Nous laissons l’exploration de ce point à des travaux futurs.

Figure 4. Le facteur d'accélération et l'augmentation du nombre d'opérations arithmétiques en fonction de \alpha pour diverses valeurs de \gamma.
Figure 4. Le facteur d'accélération et l'augmentation du nombre d'opérations arithmétiques en fonction de α\alpha pour diverses valeurs de γ\gamma.

3.6. Modèles d’approximation

L’échantillonnage spéculatif, et donc le décodage spéculatif, garantit une distribution de sortie identique pour tout choix de modèle d’approximation MqM_{q} sans restriction (voir annexe [A.1]). Dans nos expériences, nous avons principalement testé des Transformers plus petits existants prêts à l’emploi comme modèles d’approximation. En outre, nous n’avons testé que des modèles d’approximation de même architecture que les modèles cibles MpM_{p} et utilisant la même standardisation des probabilités. Dans cette configuration, choisir MqM_{q} environ deux ordres de grandeur plus petit que MpM_{p} a généralement donné les meilleurs résultats, en équilibrant α\alpha et cc (théorème 3.8).

Un autre type de modèles d’approximation, les modèles à coût négligeable, sont ceux pour lesquels c≈0c \approx 0, c’est-à-dire des modèles d’approximation dont le coût est négligeable par rapport au modèle cible. Dans ce cas, nous obtenons une amélioration attendue du temps réel de 1−αγ+11−α\frac{1 - \alpha^{\gamma + 1}}{1 - \alpha}, qui est majorée par 11−α\frac{1}{1 - \alpha} (nous approchons l’égalité si γ\gamma est grand). Un type intéressant de modèles d’approximation à coût négligeable est constitué par les modèles de n-grammes, dont l’évaluation se réduit à une consultation de table. Fait intéressant, dans les tests empiriques (section 4.2), nous obtenons des α\alpha non nuls même pour ces modèles de n-grammes triviaux. Par exemple, pour la tâche de traduction anglais-allemand, avec MpM_{p} étant T5-XXL 11B et MqM_{q} étant un modèle bigramme trivial, nous obtenons α≈0.2\alpha \approx 0.2, ce qui conduit à un facteur d’amélioration de la vitesse d’inférence de 1.25X1.25X avec γ=3\gamma = 3.

D’autres heuristiques simples peuvent être utilisées comme modèles d’approximation à coût négligeable. Par exemple, dans les cas où de longues séquences sont susceptibles de se répéter, comme pour les tâches de résumé ou les interfaces de type chat, un modèle d’approximation qui copie simplement

Figure 5. Un diagramme de trace simplifié pour une pile complète de Transformer encodeur-décodeur. La rangée du haut montre le décodage spéculatif avec \gamma = 7, de sorte que chacun des appels à M_{p} (les blocs violets) est précédé de 7 appels à M_{q} (les blocs bleus). Le bloc jaune à gauche est l'appel à l'encodeur pour M_{p} et le bloc orange est l'appel à l'encodeur pour M_{q}. De même, la rangée du milieu montre le décodage spéculatif avec \gamma = 3, et la rangée du bas montre le décodage standard.
Figure 5. Un diagramme de trace simplifié pour une pile complète de Transformer encodeur-décodeur. La rangée du haut montre le décodage spéculatif avec γ=7\gamma = 7, de sorte que chacun des appels à MpM_{p} (les blocs violets) est précédé de 7 appels à MqM_{q} (les blocs bleus). Le bloc jaune à gauche est l'appel à l'encodeur pour MpM_{p} et le bloc orange est l'appel à l'encodeur pour MqM_{q}. De même, la rangée du milieu montre le décodage spéculatif avec γ=3\gamma = 3, et la rangée du bas montre le décodage standard.

des tokens du contexte lorsqu’un préfixe correspondant est trouvé pourrait produire des valeurs élevées de α\alpha. Ces modèles d’approximation sans paramètres ont l’avantage supplémentaire d’être encore plus simples à déployer d’un point de vue de production.

Un autre type de modèles d’approximation pouvant être utilisé par le décodage spéculatif est constitué par les modèles non autorégressifs, comme ceux de Stern et al. [2018]. Dans ce cas, au lieu de la boucle autorégressive de l’algorithme 1, nous appellerions simplement le modèle non autorégressif une fois.

Un dernier exemple, intéressant surtout d’un point de vue théorique, est un modèle d’approximation qui choisit des tokens au hasard, ce qui garantit une certaine amélioration (bien que très faible) pour tous les modèles MpM_{p}.

4. Expériences

4.1. Amélioration empirique du temps réel

Nous implémentons notre algorithme et le comparons à l’implémentation de la base de code T5X pour accélérer T5-XXL.

Configuration Nous testons un modèle standard encodeur-décodeur T5 version 1.1 (Raffel et al., [2020]) sur deux tâches issues de l'article T5 : (1) la traduction de l'anglais vers l'allemand, affinée sur WMT EnDe, et (2) le résumé de texte, affiné sur CCN/DM. Pour les deux tâches, nous utilisons T5-XXL (11B) pour MpM_{p}. Pour le modèle d'approximation MqM_{q}, nous testons plusieurs configurations existantes, à savoir T5-large (800M), T5-base (250M) et T5-small (77M) (Raffel et al., [2020]). Nous utilisons les checkpoints existants pour tous les modèles. Nous mesurons les améliorations de temps d'exécution avec une taille de lot de 1 sur un seul TPU-v4, à la fois pour l'échantillonnage argmax (temp=0) et pour l'échantillonnage standard (temp=1).

Résultats Le tableau 2 présente les résultats empiriques de notre méthode. Nous constatons que T5-small (77M), avec un bon équilibre entre cc et α\alpha, offre la plus forte accélération parmi les modèles d'approximation testés.Comme attendu, nous observons que α\alpha augmente avec la taille du modèle d'approximation. Fait intéressant, α\alpha et l'amélioration du temps d'exécution sont plus élevés pour l'échantillonnage argmax (temp=0). Nous observons des accélérations de 2,6X (temp=1) et 3,4X (temp=0) sur la tâche de traduction, et des accélérations légèrement inférieures de 2,3X (temp=1) et 3,1X (temp=0) pour la tâche de résumé. Ces résultats empiriques concordent bien avec les prédictions théoriques, avec une certaine variance due aux détails d'implémentation (voir annexe A.3).

TâcheMqTEMPγαVITESSE
ENDET5-SMALL ★070,753,4X
ENDET5-BASE070,82,8X
ENDET5-LARGE070,821,7X
ENDET5-SMALL ★170,622,6X
ENDET5-BASE150,682,4X
ENDET5-LARGE130,711,4X
CNNDMT5-SMALL ★050,653,1X
CNNDMT5-BASE050,733,0X
CNNDMT5-LARGE030,742,2X
CNNDMT5-SMALL ★150,532,3X
CNNDMT5-BASE130,552,2X
CNNDMT5-LARGE130,561,7X
Tableau 2. Résultats empiriques pour l'accélération de l'inférence à partir d'un modèle T5-XXL 11B.

4.2. Valeurs empiriques de α\alpha

Bien que nous n'ayons implémenté notre méthode que pour T5, nous avons mesuré les valeurs de α\alpha pour diverses tâches, méthodes d'échantillonnage, modèles cibles MpM_{p} et modèles d'approximation MqM_{q}. Plus précisément, nous avons évalué l'espérance du corollaire 3.6 sur 10K tokens générés par MpM_{p}, pour chacune des configurations ci-dessous.

De type GPT (97M paramètres) Nous testons un modèle Transformer décodeur seul sur la génération de langage inconditionnelle, entraîné sur lm1b (Chelba et al., [2013]). Le modèle ici est un décodeur Transformer de type GPT avec des activations Gelu (Hendrycks & Gimpel, [2016]). Pour MqM_{q}, nous avons expérimenté avec un modèle décodeur Transformer de 6M paramètres : dim 256, dim feed-forward 1024, 2 couches, 4 têtes d'attention, ainsi qu'avec de simples modèles unigramme et bigramme. MpM_{p} compte 97M de paramètres : dim 768, dim feed-forward 3072, 12 couches, 12 têtes d'attention. Nous avons utilisé la tokenisation Bert (Devlin et al., [2019]) avec 8k tokens pour tous les modèles.

LaMDA (137B paramètres) Nous avons testé un modèle LaMDA décodeur seul sur une tâche de dialogue (Thoppilan et al., [2022]). Nous avons utilisé les checkpoints existants de LaMDA 137B comme MpM_{p}, et LaMDA 8B, LaMDA 2B et LaMDA 100M pour MqM_{q}.

Voir la section 4.1 pour la configuration du modèle T5-XXL (11B paramètres).

Le tableau 3 résume les valeurs de α\alpha pour les cas testés. Nous observons que les modèles d'approximation qui sont de quelques ordres de grandeur plus petits que le modèle cible tendent à produire des valeurs de α\alpha entre 0,5 et 0,9. Fait intéressant, nous notons également que, pour tous les modèles, plus la distribution ajustée est nette, plus les valeurs de α\alpha sont élevées. Enfin, nous notons que même des approximations triviales par unigramme et bigramme donnent des valeurs de α\alpha non négligeables. Par exemple, dans le cas de la traduction de l'anglais vers l'allemand, le modèle bigramme a une valeur de α\alpha de 0,2, et comme c=0c = 0 dans ce cas, il produit une amélioration de vitesse de 1,25X, ce qui est étonnamment élevé pour ce modèle d'approximation trivial (mais reste inférieur à l'accélération obtenue en utilisant T5-small comme modèle d'approximation).

5. Travaux connexes

L'efficacité de l'inférence à partir de grands modèles a été étudiée de manière approfondie (Dehghani et al., [2021]). De nombreuses approches visent à accélérer l'inférence à partir de grands modèles en général, et des modèles autorégressifs comme les Transformers en particulier. De nombreuses techniques tentent de rendre l'inférence plus efficace pour tous les tokens, par exemple la distillation (Hinton et al., [2015]), la sparcification (Jaszczur et al., [2021]), la quantification (Hubara et al., [2016]) et la modification d'architecture (So et al., [2021] ; Shazeer [2019]). Plus proches de notre approche sont les méthodes de calcul adaptatif qui adaptent la quantité de calcul à la difficulté du problème (Han et al., [2021]). Citons par exemple l'attention portée à un sous-ensemble des entrées (Sukhbaatar et al., [2019]) et les sorties anticipées (Schuster et al., [2021] ; Scardapane et al., [2020] ; Bapna et al., [2020] ; Elbayad et al., [2019] ; Schwartz et al., [2020]). Notably, Wisdom of Committees (Schwartz et al., [2020]) exploite des modèles plus petits prêts à l'emploi, mais il s'agit d'une approche de calcul adaptatif, et elle utilise donc une heuristique pour déterminer quand s'arrêter, perdant ainsi la garantie d'obtenir des sorties identiques à celles des modèles cibles. En général, les méthodes de calcul adaptatif apprennent, soit au sein du modèle lui-même, soit au moyen d'un modèle auxiliaire, quand un raccourci de calcul peut être emprunté. Habituellement, ces méthodes économisent à la fois le temps d'inférence et les opérations arithmétiques, mais nécessitent un changement d'architecture, un changement de procédure d'entraînement et l'entraînement de modèles personnalisés ou

MpMqSMPLα
DE TYPE GPT (97M)UNIGRAMMET=00,03
DE TYPE GPT (97M)BIGRAMMET=00,05
DE TYPE GPT (97M)DE TYPE GPT (6M)T=00,88
DE TYPE GPT (97M)UNIGRAMMET=10,03
DE TYPE GPT (97M)BIGRAMMET=10,05
DE TYPE GPT (97M)DE TYPE GPT (6M)T=10,89
T5-XXL (ENDE)UNIGRAMMET=00,08
T5-XXL (ENDE)BIGRAMMET=00,20
T5-XXL (ENDE)T5-SMALLT=00,75
T5-XXL (ENDE)T5-BASET=00,80
T5-XXL (ENDE)T5-LARGET=00,82
T5-XXL (ENDE)UNIGRAMMET=10,07
T5-XXL (ENDE)BIGRAMMET=10,19
T5-XXL (ENDE)T5-SMALLT=10,62
T5-XXL (ENDE)T5-BASET=10,68
T5-XXL (ENDE)T5-LARGET=10,71
T5-XXL (CNNDM)UNIGRAMT=00,13
T5-XXL (CNNDM)BIGRAMT=00,23
T5-XXL (CNNDM)T5-SMALLT=00,65
T5-XXL (CNNDM)T5-BASET=00,73
T5-XXL (CNNDM)T5-LARGET=00,74
T5-XXL (CNNDM)UNIGRAMT=10,08
T5-XXL (CNNDM)BIGRAMT=10,16
T5-XXL (CNNDM)T5-SMALLT=10,53
T5-XXL (CNNDM)T5-BASET=10,55
T5-XXL (CNNDM)T5-LARGET=10,56
LAMDA (137B)LAMDA (100M)T=00,61
LAMDA (137B)LAMDA (2B)T=00,71
LAMDA (137B)LAMDA (8B)T=00,75
LAMDA (137B)LAMDA (100M)T=10,57
LAMDA (137B)LAMDA (2B)T=10,71
LAMDA (137B)LAMDA (8B)T=10,74
Tableau 3. Valeurs empiriques de α\alpha pour différents modèles cibles MpM_{p} , modèles d'approximation MqM_{q} et réglages d'échantillonnage. T=0 et T=1 désignent respectivement argmax et l'échantillonnage standard.

le réentraînement de modèles existants. Elles modifient généralement aussi les sorties du modèle. Nous notons que, bien que nombre des méthodes ci-dessus améliorent le rapport entre la mémoire et les opérations arithmétiques, dans les cas où ce rapport reste élevé, ces méthodes et notre méthode de décodage spéculatif pourraient être efficaces en tandem.

Deux méthodes antérieures exploitent l'exécution spéculative pour accélérer le décodage à partir de modèles autorégressifs. Le décodage parallèle par blocs (Blockwise Parallel Decoding, Stern et al., [2018]) décode plusieurs tokens en parallèle, de manière similaire à nos travaux. Cependant, il ne prend en charge que le décodage glouton (température =0= 0) et non le cadre stochastique général ; il nécessite un entraînement supplémentaire d'un modèle personnalisé et se concentre sur la préservation de la qualité des tâches en aval, plutôt que sur la garantie de sorties identiques. Le décodage agressif peu profond (Shallow Aggressive Decoding, SAD) (Sun et al., [2021]) décode également plusieurs tokens en parallèle, de manière similaire à nos travaux. Contrairement à nos travaux, SAD ne prend en charge que la copie de l'entrée vers la sortie, et non les modèles d'approximation généraux, ce qui le rend adapté uniquement aux cas où les entrées et les sorties sont très similaires, comme la correction d'erreurs grammaticales. En outre, comme le décodage parallèle par blocs, SAD ne prend pas en charge le cadre général d'échantillonnage stochastique.

Après notre publication initiale, une implémentation indépendante du décodage spéculatif (Chen et al., [2023]) a montré des améliorations similaires de 2X-2,5X sur Chinchilla 70B.

6. Discussion

Nous avons présenté l'échantillonnage spéculatif, qui permet une exécution spéculative stochastique efficace, c'est-à-dire une exécution spéculative dans le cadre stochastique. Nous avons analysé son impact sur le décodage à partir de modèles autorégressifs comme les Transformers via le décodage spéculatif, et nous avons montré que, avec suffisamment de ressources de calcul, nous obtenons en pratique des accélérations significatives de 2X-3X par rapport à T5X, une implémentation optimisée populaire.

Une limite de l'exécution spéculative en général, et du décodage spéculatif en particulier, est que la latence est améliorée grâce à une concurrence accrue, au prix d'un nombre accru d'opérations arithmétiques. Ainsi, notre méthode n'est pas utile pour les configurations où des ressources de calcul supplémentaires ne sont pas disponibles. Cependant, dans les cas courants où des ressources de calcul supplémentaires sont disponibles (par exemple lorsque la bande passante mémoire est le goulot d'étranglement), notre méthode offre une accélération avec des avantages significatifs : l'architecture du modèle ne change pas, aucun réentraînement n'est nécessaire et, surtout, la distribution des sorties est garantie de rester la même. Notre méthode est facile à implémenter et peut être utilisée pour accélérer l'inférence à l'aide de modèles prêts à l'emploi, sans développer ni évaluer de schémas personnalisés.

Il existe plusieurs pistes de recherche future, et notamment l'étude plus approfondie de la compatibilité du décodage spéculatif avec la recherche par faisceau (voir l'annexe [A.4]). De plus, bien que notre méthode permette d'obtenir des accélérations substantielles avec les modèles d'approximation existants prêts à l'emploi, des améliorations plus importantes pourraient être obtenues grâce à des modèles d'approximation personnalisés (section [3.6]), tels que ceux dotés d'architectures personnalisées (par exemple des tailles personnalisées, des modèles non autorégressifs ou diverses heuristiques) ou de procédures d'entraînement personnalisées (par exemple une distillation standard avec des cibles souples issues de MpM_{p}, ou l'optimisation de MqM_{q} directement pour α\alpha). Il pourrait également être intéressant d'explorer une version hiérarchique de l'algorithme, où le modèle d'approximation est lui-même accéléré par un modèle encore plus rapide, ce qui pourrait permettre d'utiliser des modèles d'approximation plus performants. Dans ce travail, nous avons fixé le modèle d'approximation et le nombre de conjectures γ\gamma tout au long de l'inférence, mais les faire varier pendant l'inférence pourrait apporter des améliorations supplémentaires (section [3.5]). Dans nos expériences, nous avons toujours appliqué aux distributions générées par le modèle d'approximation la même standardisation que celle souhaitée pour le modèle cible (section [2.2]), mais des améliorations supplémentaires pourraient être obtenues en appliquant des transformations différentes. Nous n'avons testé le décodage spéculatif que dans la modalité textuelle, mais il pourrait bien fonctionner dans d'autres domaines (par exemple les images), ce qui serait intéressant à expérimenter.

Enfin, nous notons que l'exécution spéculative stochastique et l'échantillonnage spéculatif peuvent être utiles en dehors du cadre du décodage spéculatif à partir de modèles autorégressifs. Par exemple, étant donné deux fonctions lentes, f(x)f(x) et g(y)g(y), telles que f(x)f(x) génère une distribution à partir de laquelle l'entrée de gg est échantillonnée, nous pourrions utiliser notre méthode pour exécuter ff et gg en parallèle. Cette configuration pourrait se présenter par exemple dans des simulations physiques, ou en apprentissage par renforcement où ff est un grand modèle qui produit une distribution sur les actions et gg est la simulation du monde, ce qui serait intéressant à explorer.

Remerciements

Nous tenons à remercier tout particulièrement YaGuang Li pour son aide sur tout ce qui concerne LaMDA et pour le calcul des figures LaMDA présentées dans l'article, ainsi que Blake Hechtman pour ses précieuses idées et son aide concernant XLA. Nous remercions également les relecteurs pour leurs commentaires pertinents, ainsi qu'Asaf Aharoni, Reiner Pope, Sasha Goldshtein, Nadav Sherman, Eyal Segalis, Eyal Molad, Dani Valevski, Daniel Wasserman, Valerie Nygaard, Danny Vainstein, les équipes LaMDA et Theta Labs de Google, et nos familles.

Références

Bapna, A., Arivazhagan, N., and Firat, O. Controlling computation versus quality for neural sequence models. ArXiv, abs/2002.07106, 2020.

Brown, T. B., Mann, B., Ryder, N., Subbiah, M., Kaplan, J., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., Agarwal, S., Herbert-Voss, A., Krueger, G., Henighan, T., Child, R., Ramesh, A., Ziegler, D. M., Wu, J., Winter, C., Hesse, C., Chen, M., Sigler, E., Litwin, M., Gray, S., Chess, B., Clark, J., Berner, C., McCandlish, S., Radford, A., Sutskever, I., and Amodei, D. Language models are few-shot learners. In Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS'20, Red Hook, NY, USA, 2020. Curran Associates Inc. ISBN 9781713829546.

Burton, F. W. Speculative computation, parallelism, and functional programming. IEEE Transactions on Computers, C-34(12):1190-1193, 1985. doi: 10.1109/TC.1985.6312218.

Chelba, C., Mikolov, T., Schuster, M., Ge, Q., Brants, T., Koehn, P. T., and Robinson, T. One billion word bench mark for measuring progress in statistical language modeling. In Interspeech, 2013.

Chen, C., Borgeaud, S., Irving, G., Lespiau, J.- B., Sifre, L., and Jumper, J. M. Accelerating large language model decoding with speculative sampling. ArXiv, abs/2302.01318, 2023.

Chowdhery, A., Narang, S., Devlin, J., Bosma, M., Mishra, G., Roberts, A., Barham, P., Chung, H. W., Sutton, C., Gehrmann, S., Schuh, P., Shi, K., Tsvyashchenko, S., Maynez, J., Rao, A., Barnes, P., Tay, Y., Shazeer, N. M., Prabhakaran, V., Reif, E., Du, N., Hutchinson, B. C., Pope, R., Bradbury, J., Austin, J., Isard, M., Gur- Ari, G., Yin, P., Duke, T., Levskaya, A., Ghemawat, S., Dev, S., Michalewski, H., Garcia, X., Misra, V., Robinson, K., Fedus, L., Zhou, D., Ippolito, D., Luan, D., Lim, H., Zoph, B., Spiridonov, A., Sepassi, R., Dohan, D., Agrawal, S., Omernick, M., Dai, A. M., Pillai, T. S., Pelat, M., Lewkowycz, A., Moreira, E., Child, R., Polozov, O., Lee, K., Zhou, Z., Wang, X., Saeta, B., Diaz, M., Firat, O., Catasta, M., Wei, J., Meier- Hellstern, K. S., Eck, D., Dean, J., Petrov, S., and Fiedel, N. Palm: Scaling language modeling with pathways. ArXiv, abs/2204.02311, 2022.

Dehghani, M., Arnab, A., Beyer, L., Vaswani, A., and Tay, Y. The efficiency misnomer. ArXiv, abs/2110.12894, 2021.

Devlin, J., Chang, M.- W., Lee, K., and Toutanova, K. Bert: Pre- training of deep bidirectional transformers for language understanding. ArXiv, abs/1810.04805, 2019.

Elbayad, M., Gu, J., Grave, E., and Auli, M. Depth- adaptive transformer. ArXiv, abs/1910.10073, 2019.

Han, Y., Huang, G., Song, S., Yang, L., Wang, H., and Wang, Y. Dynamic neural networks: A survey. IEEE Transactions on Pattern Analysis and Machine Intelligence, 44: 7436- 7456, 2021.

Hendrycks, D. and Gimpel, K. Bridging nonlinearities and stochastic regularizers with gaussian error linear units. ArXiv, abs/1606.08415, 2016.

Hennessy, J. L. and Patterson, D. A. Computer Architecture: A Quantitative Approach. Morgan Kaufmann, Amsterdam, 5 edition, 2012. ISBN 978- 0- 12- 383872- 8.

Hinton, G. E., Vinyals, O., and Dean, J. Distilling the knowledge in a neural network. ArXiv, abs/1503.02531, 2015.

Hubara, I., Courbariaux, M., Soudry, D., El- Yaniv, R., and Bengio, Y. Quantized neural networks: Training neural networks with low precision weights and activations. ArXiv, abs/1609.07061, 2016.

Jaszczur, S., Chowdhery, A., Mohiuddin, A., Kaiser, L., Gajewski, W., Michalewski, H., and Kanerva, J. Sparse is enough in scaling transformers. In Neural Information Processing Systems, 2021.

Raffel, C., Shazeer, N., Roberts, A., Lee, K., Narang, S., Matena, M., Zhou, Y., Li, W., and Liu, P. J. Exploring the limits of transfer learning with a unified text- to- text transformer. The Journal of Machine Learning Research, 21(1):5485- 5551, 2020.

Roberts, A., Chung, H. W., Levskaya, A., Mishra, G., Bradbury, J., Andor, D., Narang, S., Lester, B., Gaffney, C., Mohiuddin, A., Hawthorne, C., Lewkowycz, A., Salcianu, A., van Zee, M., Austin, J., Goodman, S., Soares, L. B., Hu, H., Tsvyashchenko, S., Chowdhery, A., Bastings, J., Bulian, J., Garcia, X., Ni, J., Chen, A., Kenealy, K., Clark, J., Lee, S., Garrette, D. H., Lee- Thorp, J., Raffel, C., Shazeer, N. M., Ritter, M., Bosma, M., Passos, A., Maitin- Shepard, J. B., Fiedel, N., Omernick, M., Saeta, B., Sepassi, R., Spiridonov, A., Newlan, J., and Gesmundo, A. Scaling up models and data with 5x and seqio. ArXiv, abs/2203.17189, 2022.

Scardapane, S., Scarpiniti, M., Baccarelli, E., and Uncini, A. Why should we add early exits to neural networks? Cognitive Computation, 12(5):954- 966, 2020.

Schuster, T., Fisch, A., Jaakkola, T., and Barzilay, R. Consistent accelerated inference via confident adaptive transformers. In Conference on Empirical Methods in Natural Language Processing, 2021.

Schwartz, R., Stanovsky, G., Swayamdipta, S., Dodge, J., and Smith, N. A. The right tool for the job: Matching model and instance complexities. In Annual Meeting of the Association for Computational Linguistics, 2020.

Shazeer, N. M. Fast transformer decoding: One write- head is all you need. ArXiv, abs/1911.02150, 2019.

So, D. R., Ma'ake, W., Liu, H., Dai, Z., Shazeer, N. M., and Le, Q. V. Primer: Searching for efficient transformers for language modeling. ArXiv, abs/2109.08668, 2021.

Stern, M., Shazeer, N., and Uszkoreit, J. Blockwise parallel decoding for deep autoregressive models. Advances in Neural Information Processing Systems, 31, 2018.

Sukhbaatar, S., Grave, E., Bojanowski, P., and Joulin, A. Adaptive attention span in transformers. In Annual Meeting of the Association for Computational Linguistics, 2019.

Sun, X., Ge, T., Wei, F., and Wang, H. Instantaneous grammatical error correction with shallow aggressive decoding. ArXiv, abs/2106.04970, 2021.

Thoppilan, R., Freitas, D. D., Hall, J., Shazeer, N. M., Kulshreshtha, A., Cheng, H.- T., Jin, A., Bos, T., Baker, L., Du, Y., Li, Y., Lee, H., Zheng, H., Ghafouri, A., Menegali, M., Huang, Y., Krikun, M., Lepikhin, D., Qin, J., Chen, D., Xu, Y., Chen, Z., Roberts, A., Bosma, M., Zhou, Y., Chang, C.- C., Krivokon, I. A., Rusch, W. J., Pickett, M., Meier- Hellstern, K. S., Morris, M. R., Doshi, T., Santos, R. D., Duke, T., Soraker, J. H., Zevenbergen, B., Prabhakaran, V., Díaz, M., Hutchinson, B., Olson, K., Molina, A., Hoffman- John, E., Lee, J., Aroyo, L., Rajakumar, R., Butryna, A., Lamm, M., Kuzmina, V. O., Fenton, J., Cohen, A., Bernstein, R., Kurzweil, R., Aguera- Arcas, B., Cui, C., Croak, M., hsin Chi, E. H., and Le, Q. Lamda: Language models for dialog applications. ArXiv, abs/2201.08239, 2022.

Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, L., et Polosukhin, I. Attention is all you need. Advances in neural information processing systems, 30, 2017.

Yu, J., Xu, Y., Koh, J. Y., Luong, T., Baid, G., Wang, Z., Vasudevan, V., Ku, A., Yang, Y., Ayan, B. K., Hutchinson, B. C., Han, W., Parekh, Z., Li, X., Zhang, H., Baldridge, J., et Wu, Y. Scaling autoregressive models for content-rich text- to- image generation. ArXiv, abs/2206.10789, 2022.

A. Annexe

A.1. Exactitude de l'échantillonnage spéculatif

Nous allons maintenant montrer que pour toutes distributions p(x)p(x) et q(x)q(x) , les tokens échantillonnés par échantillonnage spéculatif à partir de p(x)p(x) et q(x)q(x) sont distribués de manière identique à ceux échantillonnés à partir de p(x)p(x) seul. Soit β\beta la probabilité d'acceptation (Définition 3.1).

Notons que comme p′(x)=norm(max(0,p(x)−q(x)))=p(x)−min(q(x),p(x))∑x′(p(x′)−min(q(x′),p(x′)))=p(x)−min(q(x),p(x))1−βp^{\prime}(x) = n o r m(m a x(0,p(x) - q(x))) = \frac{p(x) - m i n(q(x),p(x))}{\sum_{x^{\prime}}(p(x^{\prime}) - m i n(q(x^{\prime}),p(x^{\prime})))} = \frac{p(x) - m i n(q(x),p(x))}{1 - \beta} , la constante de normalisation pour la distribution ajustée p′(x)p^{\prime}(x) est 1−β1 - \beta , où la dernière équation découle immédiatement du Lemme 3.3 et du Théorème 3.5

Maintenant :

P(x=x′)=P(devine accepteˊe,x=x′)+P(devine rejeteˊe,x=x′)P(x = x^{\prime}) = P(\text{devine acceptée}, x = x^{\prime}) + P(\text{devine rejetée}, x = x^{\prime})

Où :

P(devine accepteˊe,x=x′)=q(x′)min⁡(1,p(x′)q(x′))=min⁡(q(x′),p(x′))P(\text{devine acceptée}, x = x^{\prime}) = q(x^{\prime}) \min (1, \frac{p(x^{\prime})}{q(x^{\prime})}) = \min (q(x^{\prime}), p(x^{\prime}))

Et :

P(devine rejeteˊe,x=x′)=(1−β)p′(x′)=p(x′)−min⁡(q(x′),p(x′))P(\text{devine rejetée}, x = x^{\prime}) = (1 - \beta) p^{\prime}(x^{\prime}) = p(x^{\prime}) - \min (q(x^{\prime}), p(x^{\prime}))

Globalement :

P(x=x′)=min⁡(p(x′),q(x′))+p(x′)−min⁡(p(x′),q(x′))=p(x′).P(x = x^{\prime}) = \min (p(x^{\prime}), q(x^{\prime})) + p(x^{\prime}) - \min (p(x^{\prime}), q(x^{\prime})) = p(x^{\prime}).

Comme souhaité.

A.2. Échantillonnage spéculatif vs. échantillonnage par rejet

L'échantillonnage par rejet est la procédure d'échantillonnage itérative suivante qui semble superficiellement similaire à la nôtre :

1. Tirer x∼q(x)x \sim q(x) et r∼U(0,1)r \sim U(0, 1) .

2. Si r<p(x)Mq(x)r < \frac{p(x)}{M q(x)} renvoyer xx .

3. Aller à 1.

Où M=maxxp(x)q(x)M = m a x_{x} \frac{p(x)}{q(x)} . Nous pourrions employer une version non itérative de l'échantillonnage par rejet au lieu de l'échantillonnage spéculatif — plus précisément, parcourir les étapes 1 et 2 ci-dessus, et sinon échantillonner directement à partir d'un p(x)p(x) non modifié. Ce serait cependant bien moins efficace que notre méthode. Plus précisément, la probabilité d'acceptation espérée ici est Ex∼q(x)p(x)Mq(x)=∑xp(x)min⁡x′q(x′)p(x′)≤∑xp(x)min⁡(1,q(x)p(x))=∑xmin⁡(p(x),q(x))=αE_{x \sim q(x)} \frac{p(x)}{M q(x)} = \sum_{x} p(x) \min_{x^{\prime}} \frac{q(x^{\prime})}{p(x^{\prime})} \leq \sum_{x} p(x) \min (1, \frac{q(x)}{p(x)}) = \sum_{x} \min (p(x), q(x)) = \alpha est (potentiellement bien) inférieure à la probabilité d'acceptation espérée dans notre méthode α\alpha .

A.3. Prédictions théoriques vs. temps d'exécution empiriques

Le tableau 4 compare les améliorations de temps d'exécution attendues d'après le théorème 3.8 aux temps d'exécution mesurés empiriquement du tableau 2. Nous avons estimé les valeurs de cc pour les différents modèles à partir de traces de profilage. Nous pouvons constater que les prédictions théoriques correspondent globalement aux temps d'exécution mesurés. Les écarts plus importants sont dus à : (1) des différences d'optimisation entre notre implémentation et la référence, et (2) l'hypothèse simplificatrice selon laquelle les β\beta sont i.i.d. n'étant qu'une approximation (voir section 3.1).

TÂCHEMQTEMPγαcEXPEMP
ENDET5-SMALL070,750,023,23,4
ENDET5-BASE070,80,043,32,8
ENDET5-LARGE070,820,112,51,7
ENDET5-SMALL170,620,022,32,6
ENDET5-BASE150,680,042,42,4
ENDET5-LARGE130,710,112,01,4
CNNDMT5-SMALL050,650,022,43,1
CNNDMT5-BASE050,730,042,63,0
CNNDMT5-LARGE030,740,112,02,2
CNNDMT5-SMALL150,530,021,92,3
CNNDMT5-BASE130,550,041,82,2
CNNDMT5-LARGE130,560,111,61,7

Tableau 4. Facteur d'amélioration attendu (Exp) vs. facteur d'amélioration mesuré empiriquement (EMP).

A.4. Application à la recherche par faisceau

Notre méthode peut être appliquée, avec une certaine pénalité de performance, à l'échantillonnage par recherche par faisceau. Étant donné la largeur de faisceau originale ww , nous pouvons effectuer une recherche par faisceau avec le modèle d'approximation MqM_{q} et une largeur de faisceau u≥wu\geq w pendant γ\gamma étapes. Ensuite, nous pouvons utiliser MpM_{p} pour vérifier tous les candidats en parallèle (ce qui coûte un budget de calcul de (w+uγ)(w + u\gamma) exécutions de MpM_{p} ). Enfin, pour chaque étape, nous pouvons accepter les devinettes de MqM_{q} tant que topw(Mp)⊆topu(Mq)t o p_{w}(M_{p})\subseteq t o p_{u}(M_{q}) pour obtenir des résultats identiques à une recherche par faisceau régulière avec MpM_{p} seul (avec une procédure plus élaborée, nous pourrions aussi accepter les cas où les candidats obtenus ont par hasard des probabilités plus élevées que celles de MpM_{p} seul). L'analyse de notre méthode dans ce cadre est plus complexe et nous la laissons pour des travaux futurs.

A.5. Indulgence

Une propriété forte de l'algorithme \boxed{ \begin{array}{r l} \end{array} } est que la distribution de sortie est garantie de rester inchangée. Cela dit, si nous acceptons de permettre certains changements, avec de belles garanties, nous pouvons obtenir d'autres améliorations de vitesse d'inférence. Pour motiver davantage cela, notons que lorsque nous entraînons deux modèles d'architectures et de tailles identiques sur le même jeu de données, les distributions de probabilité générées ne seront pas identiques, donc une certaine indulgence pourrait avoir du sens. Notons que les résultats de cet article, à l'exception de cette section, utilisent la version la plus stricte de l'algorithme \boxed{ \begin{array}{r l} \end{array} } et n'autorisent aucune forme d'indulgence.

Nous pourrions inclure un paramètre d'indulgence l∈[0,1]l\in [0,1] et multiplier q(x)q(x) par ll avant de le comparer à p(x)p(x) dans l'algorithme \boxed{ \begin{array}{r l} \end{array} } Cela maintient toujours la belle garantie qu'aucun token ne peut être échantillonné avec une probabilité supérieure à p(x)l\frac{p(x)}{l} . Cela signifie par exemple qu'avec l=110l = \frac{1}{10} aucun token ne peut être échantillonné avec plus de 10 fois sa probabilité de vérité terrain, de sorte que nous pouvons garantir que les tokens extrêmement rares resteront extrêmement rares (il n'y a aucune garantie sur la probabilité minimale, donc l'indulgence pourrait nuire à la diversité des échantillons).

Plus précisément, avec un facteur d'indulgence ll nous avons \begin{array}{r l r}{{\alpha}~=}&{{}E_{x\sim q(x)}\left\{\begin{array}{l l}{1}&{l q(x)\leq p(x)}\\ {\frac{p(x)}{l q(x)}}&{l q(x)>p(x)}\end{array}\right.}&{{}=}&{{}E_{x\sim q(x)}\frac{p(x)}{m a x(p(x),l q(x))}}}\end{array} ∑xp(x)q(x)max(p(x),lq(x))=1l∑xmin⁡(p(x),lq(x))=∑xmin⁡(p(x)l,q(x))\begin{array}{r}{\sum_{x}\frac{p(x)q(x)}{m a x(p(x),l q(x))} = \frac{1}{l}\sum_{x}\min (p(x),l q(x)) = \sum_{x}\min (\frac{p(x)}{l},q(x))} \end{array}

Le tableau 5 montre les valeurs de α\alpha pour différentes valeurs de ll lorsque MpM_{p} est T5- XXL (11B) et MqM_{q} est T5- small (77M). Avec c=0.015c = 0.015 en utilisant des valeurs d'indulgence de 1, 0.5, 0.3 et 0.1 (ce qui signifie qu'aucun token ne peut être échantillonné avec une probabilité supérieure à 1X, 2X, 3X et 10X de la vérité terrain) nous obtenons des facteurs d'amélioration de 2.5X, 3.1X, 3.6X et 5X respectivement.

Contexte en lecture seule pour comprendre la source (il ne s'agit pas du texte source à traduire) : Le tableau 5 montre les valeurs de α pour différentes valeurs de l lorsque M_{p} est T5- XXL (11B) et M_{q} est T5- small (77M). Avec c = 0,015 en utilisant des valeurs d'indulgence de 1, 0,5, 0,3 et 0,1 (ce qui signifie qu'aucun token ne peut être échantillonné avec une probabilité supérieure à 1X, 2X, 3X et 10X de la vérité terrain), nous obtenons des facteurs d'amélioration de 2,5X, 3,1X, 3,6X et 5X respectivement. Tableau 5. Valeurs de α pour diverses valeurs de l avec un échantillonnage standard où M_{p} est T5-XXL (11B) sur la tâche de traduction EnDe. Texte à traduire : MQ l = 1 l = 0,5 l = 0,3 l = 0,1 UNIGRAM 0,07 0,1 0,11 0,16 BIGRAM 0,19 0,23 0,25 0,32 T5-SMALL (77M) 0,62 0,71 0,76 0,84 T5-BASE (250M) 0,68 0,8 0,83 0,90

Tableau 5. Valeurs de α\alpha pour diverses valeurs de ll avec un échantillonnage standard où MpM_{p} est T5-XXL (11B) sur la tâche de traduction EnDe.

Notez que lorsqu'on utilise une température =0= 0 (c'est-à-dire un échantillonnage argmax), nous ne pouvons plus utiliser l'indulgence comme ci-dessus. Au lieu de cela, nous pourrions autoriser une certaine indulgence avant de standardiser les distributions. Par exemple, nous pourrions accepter le token xx échantillonné à partir de MqM_{q} dans le cas où p(x)≤l⋅max⁡(p)p(x) \leq l \cdot \max (p) . Dans ce cas, nous mesurons des augmentations empiriques similaires des valeurs de α\alpha à celles obtenues avec une température =1= 1 . Par exemple, en utilisant des valeurs d'indulgence de 1, 0,5, 0,3 et 0,1 pour MpM_{p} T5- XXL MqM_{q} T5- small pour la traduction anglais-allemand, nous obtenons des valeurs de α\alpha de 0,75, 0,75, 0,8, 0,87. En prenant par exemple c=0.015c = 0.015 et γ=8\gamma = 8 nous obtenons des facteurs d'amélioration de la vitesse de 3,3X, 3,3X, 3,9X et 4,9X respectivement.7