Retour à la bibliothèque
arXiv 2019Langage et TransformersNotes de lecture

MQA

Des clés et valeurs partagées

Article original

Fast Transformer Decoding: One Write-Head is All You Need

Auteurs de l’article

Noam Shazeer

Publication
Lieu de publication non encore vérifié
Premier dépôt sur arXiv
arXiv:1911.02150
Citer cet article · BibTeX

La référence correspond à la version liée et cite les auteurs de l’article original.

@misc{transformersmqa2019,
  title = {{Fast Transformer Decoding: One Write-Head is All You Need}},
  author = {Noam Shazeer},
  year = {2019},
  eprint = {1911.02150},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1911.02150}
}
Sur cette page

L'économie du partage est partout ; apparemment, on peut aussi l'appliquer au mécanisme d'attention.

L'auteur de cet article est Noam Shazeer, membre de l'équipe qui a écrit « Attention Is All You Need ».

Définir le problème

Après avoir proposé le mécanisme d'attention classique, l'auteur constate qu'en décodage autorégressif, il faut relire à chaque étape un cache de clés et de valeurs qui grandit avec la séquence. Les projections passées sont normalement conservées : le coût visé ici est surtout l'accès répété au cache, qui pèse sur la bande passante mémoire.

C'est une opération peu efficace que l'auteur souhaite améliorer.

Retour sur le mécanisme d'attention

Pour comprendre sa solution, repartons du mécanisme d'attention initial.

Attention par produit scalaire

Commençons par une seule requête (query) confrontée à un ensemble de paires clé-valeur.

python
def DotProductAttention(q, K, V):
    """
    Attention par produit scalaire pour une requête.
    Paramètres :
    q: vecteur de forme [k] (requête)
    K: matrice de forme [m, k] (clés)
    V: matrice de forme [m, v] (valeurs)

    Retour :
    y: vecteur de forme [v] (sortie)
    """
    # Produit scalaire de q et K : logits de forme [m]
    logits = tf.einsum("k,mk->m", q, K)

    # Softmax des logits : poids de chaque clé, de forme [m]
    weights = tf.nn.softmax(logits)

    # Somme pondérée des valeurs V : vecteur de sortie y de forme [v]
    y = tf.einsum("m,mv->v", weights, V)

    return y

Voilà l'attention classique par produit scalaire.

Elle calcule la similarité entre la requête et les clés, puis utilise ces similarités pour pondérer les valeurs et produire le vecteur de sortie.

Attention multi-têtes

Passons à l'attention multi-têtes : plusieurs opérations d'attention par produit scalaire sont combinées pour améliorer le modèle.

Dans la fonction ci-dessous, les paramètres désignent :

  • dd : la dimension du vecteur de requête.
  • mm : le nombre de paires clé-valeur.
  • hh : le nombre de têtes d'attention.
  • kk : la dimension de projection linéaire des requêtes et des clés.
  • vv : la dimension de projection linéaire des valeurs.
python
import tensorflow as tf

def MultiheadAttention(x, M, P_q, P_k, P_v, P_o):
    """
    Attention multi-têtes pour une requête.

    Paramètres :
    x: vecteur de forme [d] représentant la requête
    M: matrice de forme [m, d] représentant clés et valeurs
    P_q: tenseur de forme [h, d, k] projetant les requêtes
    P_k: tenseur de forme [h, d, k] projetant les clés
    P_v: tenseur de forme [h, d, v] projetant les valeurs
    P_o: tenseur de forme [h, d, v] projetant la sortie

    Retour :
    y: vecteur de forme [d] représentant la sortie finale
    """

    # Projection de la requête x : forme [h, k]
    q = tf.einsum("d, hdk->hk", x, P_q)

    # Projection des clés et des valeurs de M
    # K a la forme [h, m, k] ; V a la forme [h, m, v]
    K = tf.einsum("md, hdk->hmk", M, P_k)
    V = tf.einsum("md, hdv->hmv", M, P_v)

    # Produit scalaire requête-clé : logits de forme [h, m]
    logits = tf.einsum("hk, hmk->hm", q, K)

    # Softmax des logits : poids d’attention de forme [h, m]
    weights = tf.nn.softmax(logits)

    # Somme pondérée des valeurs : forme [h, v]
    o = tf.einsum("hm, hmv->hv", weights, V)

    # Projection et réunion des têtes : vecteur final de forme [d]
    y = tf.einsum("hv, hdv->d", o, P_o)

    return y

Attention multi-têtes en lot

Élargissons maintenant le calcul.

À l'entraînement, on traite généralement les exemples par lots. Il faut donc adapter la fonction précédente.

python
import tensorflow as tf

def MultiheadAttentionBatched(X, M, mask, P_q, P_k, P_v, P_o):
    """
    Attention multi-têtes pour des entrées traitées par lots.

    Paramètres :
    X: tenseur de forme [b, n, d] des requêtes (lot b, séquence n, dimension d)
    M: tenseur de forme [b, m, d] des clés et valeurs (m paires)
    mask: tenseur de forme [b, h, n, m] masquant les positions invalides
    P_q: tenseur de forme [h, d, k] projetant les requêtes
    P_k: tenseur de forme [h, d, k] projetant les clés
    P_v: tenseur de forme [h, d, v] projetant les valeurs
    P_o: tenseur de forme [h, d, v] projetant la sortie

    Retour :
    Y: tenseur de forme [b, n, d] représentant la sortie finale
    """

    # Projection des requêtes X : forme [b, h, n, k]
    Q = tf.einsum("bnd, hdk->bhnk", X, P_q)

    # Projection de M : clés K [b, h, m, k] et valeurs V [b, h, m, v]
    K = tf.einsum("bmd, hdk->bhmk", M, P_k)
    V = tf.einsum("bmd, hdv->bhmv", M, P_v)

    # Produit scalaire requête-clé : logits de forme [b, h, n, m]
    logits = tf.einsum("bhnk, bhmk->bhnm", Q, K)

    # Masque puis softmax : poids d’attention de forme [b, h, n, m]
    weights = tf.nn.softmax(logits + mask)

    # Somme pondérée des valeurs : forme [b, h, n, v]
    O = tf.einsum("bhnm, bhmv->bhnv", weights, V)

    # Projection et réunion des têtes : sortie de forme [b, n, d]
    Y = tf.einsum("bhnv, hdv->bnd", O, P_o)

    return Y

L'auteur simplifie ici les hypothèses sur les calculs et les accès mémoire :

  1. m=nm = n : le nombre mm de clés et valeurs égale la longueur nn de la séquence de requêtes.
  2. k=v=dhk = v = \frac{d}{h} : comme dans le Transformer d'origine, les dimensions kk et vv sont égales à la dimension des caractéristiques dd divisée par le nombre de têtes hh.
  3. n≤dn ≤ d : la longueur nn de la séquence ne dépasse pas la dimension dd des caractéristiques.

Sous ces hypothèses, le nombre total d'opérations est de Θ(bnd2)Θ(bnd^2), où bb est la taille du lot, nn la longueur de la séquence et dd la dimension des caractéristiques. Chaque opération tf.einsum considérée ici est d'ordre O(bnd2)O(bnd^2).

Quant aux accès mémoire, la taille totale des tenseurs est de l'ordre de O(bnd+bhn2+d2)O(bnd + bhn^2 + d^2) :

  • Le terme bndbnd vient des entrées XX et MM, ainsi que des requêtes QQ, clés KK, valeurs VV, sorties OO et sorties finales YY.
  • Le terme bhn2bhn^2 provient des logits et des poids d'attention.
  • Le terme d2d^2 correspond aux tenseurs de projection PqP_q, PkP_k, PvP_v et PoP_o.

Le rapport des accès mémoire aux calculs est donc :

O(1k+1bn)O\left(\frac{1}{k} + \frac{1}{bn}\right)

Plus ce rapport est faible, mieux les GPU et TPU modernes peuvent exploiter leur puissance de calcul, qui dépasse largement leur bande passante mémoire.

Attention multi-têtes incrémentale

Il existe aussi une version incrémentale de l'attention multi-têtes pour la génération autorégressive.

python
import tensorflow as tf

def MultiheadSelfAttentionIncremental(x, prev_K, prev_V, P_q, P_k, P_v, P_o):
    """
    Auto-attention multi-têtes pour une étape de génération incrémentale.

    Paramètres :
    x: tenseur de forme [b, d] représentant la requête actuelle
    prev_K: tenseur de forme [b, h, m, k] des clés précédentes
    prev_V: tenseur de forme [b, h, m, v] des valeurs précédentes
    P_q: tenseur de forme [h, d, k] projetant la requête
    P_k: tenseur de forme [h, d, k] projetant les clés
    P_v: tenseur de forme [h, d, v] projetant les valeurs
    P_o: tenseur de forme [h, d, v] projetant la sortie

    Retour :
    y: tenseur de forme [b, d] produit à cette étape
    new_K: tenseur de forme [b, h, m+1, k] des clés mises à jour
    new_V: tenseur de forme [b, h, m+1, v] des valeurs mises à jour
    """

    # Projection de la requête x : forme [b, h, k]
    q = tf.einsum("bd, hdk->bhk", x, P_q)

    # Ajout de la nouvelle clé au cache : forme [b, h, m+1, k]
    new_K = tf.concat(
        [prev_K, tf.expand_dims(tf.einsum("bd, hdk->bhk", x, P_k), axis=2)],
        axis=2
    )

    # Ajout de la nouvelle valeur au cache : forme [b, h, m+1, v]
    new_V = tf.concat(
        [prev_V, tf.expand_dims(tf.einsum("bd, hdv->bhv", x, P_v), axis=2)],
        axis=2
    )

    # Produit scalaire requête-clé : logits de forme [b, h, m+1]
    logits = tf.einsum("bhk, bhmk->bhm", q, new_K)

    # Softmax : poids d’attention de forme [b, h, m+1]
    weights = tf.nn.softmax(logits)

    # Somme pondérée des valeurs : forme [b, h, v]
    o = tf.einsum("bhm, bhmv->bhv", weights, new_V)

    # Projection et réunion des têtes : forme [b, d]
    y = tf.einsum("bhv, hdv->bd", o, P_o)

    return y, new_K, new_V

L'auteur conserve les hypothèses simplifiées précédentes et évalue le décodage incrémental.

Sur toute la génération, le nombre d'opérations est de Θ(bnd2)\Theta(bnd^2), où bb désigne la taille du lot, nn la longueur de la séquence et dd la dimension des caractéristiques.

Le nombre total d'accès mémoire est de Θ(bn2d+nd2)\Theta(bn^2d + nd^2) :

  • Le terme bn2dbn^2d vient des clés KK et des valeurs VV qu'il faut relire à chaque étape ; la taille de ces tenseurs croît avec nn.
  • Le terme nd2nd^2 vient des matrices de projection des requêtes, clés et valeurs Pq,Pk,Pv,PoP_q, P_k, P_v, P_o.

Le rapport entre accès mémoire et calculs est :

Θ(nd+1b)\Theta\left(\frac{n}{d} + \frac{1}{b}\right)

Lorsque n≈dn ≈ d ou b≈1b ≈ 1, ce rapport approche 1 : la bande passante mémoire devient alors un obstacle majeur sur le matériel moderne.


Une première optimisation consiste à augmenter la taille du lot : le rapport entre accès mémoire et calculs diminue facilement.

Il est plus difficile de réduire le rapport nd\frac{n}{d}, puisqu'il faut relire les clés et les valeurs à chaque étape. On peut limiter la longueur nn de la séquence ou concentrer l'attention sur une zone locale pour réduire les positions mémoire à traiter.

Résoudre le problème

Pour réduire la taille des tenseurs de Key\text{Key} et de Value\text{Value}, l'auteur propose de retirer leur dimension « têtes » (heads) tout en conservant les différentes têtes des requêtes. Cela allège les accès mémoire et accélère le décodage.

Attention multi-requêtes

L'attention multi-requêtes (Multi-Query Attention) est une variante de l'attention multi-têtes (Multi-Head Attention).

Dans la version multi-têtes classique, chaque tête possède ses propres requêtes, clés et valeurs, ainsi qu'une sortie. L'attention multi-requêtes simplifie ce schéma : les têtes gardent des requêtes distinctes, mais partagent un seul jeu de clés et de valeurs. Le cache est ainsi plus petit et l'inférence plus rapide.

python
def MultiQueryAttentionBatched(X, M, mask, P_q, P_k, P_v, P_o):
    """
    Attention multi-requêtes pour des entrées traitées par lots.

    Paramètres :
    X: tenseur de forme [b, n, d] des requêtes
    M: tenseur de forme [b, m, d] des clés et valeurs
    mask: tenseur de forme [b, h, n, m] masquant les positions invalides
    P_q: tenseur de forme [h, d, k] projetant les requêtes
    P_k: tenseur de forme [d, k] projetant les clés
    P_v: tenseur de forme [d, v] projetant les valeurs
    P_o: tenseur de forme [h, d, v] projetant la sortie

    Retour :
    Y: tenseur de forme [b, n, d] représentant la sortie finale
    """

    # Projection des requêtes X : forme [b, h, n, k]
    Q = tf.einsum("bnd, hdk->bhnk", X, P_q)

    # Projection de M : clés K [b, m, k] et valeurs V [b, m, v]
    K = tf.einsum("bmd, dk->bmk", M, P_k)
    V = tf.einsum("bmd, dv->bmv", M, P_v)

    # Produit scalaire requête-clé : forme [b, h, n, m]
    logits = tf.einsum("bhnk, bmk->bhnm", Q, K)

    # Softmax avec masque : poids d’attention de forme [b, h, n, m]
    weights = tf.nn.softmax(logits + mask)

    # Somme pondérée des valeurs : forme [b, h, n, v]
    O = tf.einsum("bhnm, bmv->bhnv", weights, V)

    # Projection et réunion des têtes : forme [b, n, d]
    Y = tf.einsum("bhnv, hdv->bnd", O, P_o)

    return Y

L'auteur donne aussi le code d'une auto-attention multi-requêtes incrémentale (Incremental Multi-Query Self-Attention) :

python
def MultiQuerySelfAttentionIncremental(x, prev_K, prev_V, P_q, P_k, P_v, P_o):
    """
    Auto-attention multi-requêtes incrémentale pour une étape.

    Paramètres :
    x: tenseur de forme [b, d] représentant la requête actuelle
    prev_K: tenseur de forme [b, m, k] des clés précédentes
    prev_V: tenseur de forme [b, m, v] des valeurs précédentes
    P_q: tenseur de forme [h, d, k] projetant la requête
    P_k: tenseur de forme [d, k] projetant les clés
    P_v: tenseur de forme [d, v] projetant les valeurs
    P_o: tenseur de forme [h, d, v] projetant la sortie

    Retour :
    y: tenseur de forme [b, d] représentant la sortie
    new_K: matrice de clés mise à jour, de forme [b, m+1, k]
    new_V: matrice de valeurs mise à jour, de forme [b, m+1, v]
    """

    # Projection de la requête : forme [b, h, k]
    q = tf.einsum("bd, hdk->bhk", x, P_q)

    # Mise à jour des matrices de clés et de valeurs
    new_K = tf.concat([prev_K, tf.expand_dims(tf.einsum("bd, dk->bk", x, P_k), axis=1)], axis=1)
    new_V = tf.concat([prev_V, tf.expand_dims(tf.einsum("bd, dv->bv", x, P_v), axis=1)], axis=1)

    # Produit scalaire requête-clé : forme [b, h, m+1]
    logits = tf.einsum("bhk, bmk->bhm", q, new_K)

    # Calcul des poids par softmax
    weights = tf.nn.softmax(logits)

    # Somme pondérée des valeurs
    o = tf.einsum("bhm, bmv->bhv", weights, new_V)

    # Projection et réunion des sorties
    y = tf.einsum("bhv, hdv->bd", o, P_o)

    return y, new_K, new_V

Analyse des performances

Comme dans l'attention multi-têtes ordinaire, le calcul de l'attention multi-requêtes incrémentale reste de l'ordre de Θ(bnd2)\Theta(bnd^2). Les accès mémoire sont de l'ordre de Θ(bnd+bn2k+nd2)\Theta(bnd + bn^2k + nd^2).

En retirant la dimension des têtes des clés et des valeurs, on réduit le cache K/V relu sans cesse pendant le décodage. L'ordre asymptotique des calculs reste Θ(bnd2)\Theta(bnd^2) ; l'accélération vient surtout d'une moindre pression sur la bande passante mémoire.

Le rapport entre accès mémoire et calculs devient :

Θ(1d+ndh+1b)\Theta\left(\frac{1}{d} + \frac{n}{dh} + \frac{1}{b}\right)

Le terme nd\frac{n}{d} est divisé par le nombre de têtes hh, d'où une amélioration possible du décodage incrémental.

Imaginons la génération d'un lot de taille b=128b = 128 sur 100 mots (n=100n = 100), avec des vecteurs de dimension d=512d = 512.

Pour l'attention multi-têtes classique, le rapport « accès mémoire / calculs » serait approximativement :

nd+1b=100512+1128≈0.195+0.0078=0.2028\frac{n}{d} + \frac{1}{b} = \frac{100}{512} + \frac{1}{128} \approx 0.195 + 0.0078 = 0.2028

En attention multi-requêtes, avec h=8h = 8, il devient :

1d+ndh+1b\frac{1}{d} + \frac{n}{dh} + \frac{1}{b} =1512+100512×8+1128= \frac{1}{512} + \frac{100}{512 \times 8} + \frac{1}{128} ≈0.00195+0.0244+0.0078=0.03415\approx 0.00195 + 0.0244 + 0.0078 = 0.03415

Ce calcul simple illustre une réduction du rapport dans ces hypothèses. La vitesse réelle demande une mesure distincte.

Stratégie d'entraînement

L'auteur évalue la méthode sur la traduction anglais-allemand de WMT 2014.

Le modèle de départ est un Transformer encodeur-décodeur à six couches, configuré ainsi :

  • dmodel=1024d_{model} = 1024.
  • dff=4096d_{ff} = 4096.
  • h=8h = 8 têtes.
  • dk=dv=128d_k = d_v = 128, avec des embeddings de position appris et des poids partagés entre les embeddings des tokens et la couche de sortie.

L'entraînement dure 100 000 étapes, soit environ 20 époques. Chaque lot compte 128 exemples, avec 256 tokens d'entrée et 256 tokens cibles par exemple. Il se déroule sur un cluster TPUv3 à 32 cœurs et dure environ deux heures par modèle.

Dans la version MQA, toutes les couches d'attention sont remplacées par l'attention multi-requêtes ; la dimension cachée du réseau feed-forward passe de 4 096 à 5 440 pour maintenir un nombre total de paramètres comparable à celui du modèle de référence.

Discussion

Résultats WMT14 anglais-allemand

Le tableau présente les résultats expérimentaux des auteurs.

Sur le développement, MQA obtient un ln(PPL) de 1,439 et un BLEU de 26,5, légèrement moins bons que les 1,424 et 26,7 du modèle de référence, mais meilleurs que les autres variantes du tableau qui réduisent le nombre de têtes ou la dimension des clés et valeurs. Sur le test WMT14 avec un faisceau de largeur quatre, MQA atteint 28,5 BLEU, un peu plus que les 28,4 du modèle de référence. Dire « légèrement moins bon » ne concerne donc que les mesures de développement ci-dessus.

Gain de temps à l'inférence

Le tableau de vitesse utilise un TPUv2 à huit cœurs. Chaque étape d'entraînement traite 32 768 tokens d'entrée et autant de tokens cibles. Les durées divisées par 32 768 sont des temps amortis par paire « token d'entrée et token cible ».

Code
- **Modèle de référence** : **433 ms** par étape d'entraînement.
- **Modèle multi-requêtes** : **425 ms** par étape, un peu plus rapide.

Le temps d'entraînement par paire de tokens d'entrée et de cible est :

  • Modèle de référence :

    43332,768=13.2μs\frac{433}{32,768} = 13.2\mu s
  • Modèle MQA :

    42532,768=13.0μs\frac{425}{32,768} = 13.0\mu s

À l'inférence, les auteurs mesurent le décodage glouton incrémental d'un modèle de traduction : 1 024 séquences, chacune avec 128 tokens d'entrée et 128 tokens cibles, soit en moyenne 128 séquences par cœur TPU.

  • Modèle de référence :

    • L'encodeur prend 222 ms, soit 1,7 µs par token.
    • Chaque étape du décodeur prend 47 ms, soit 46 µs par token décodé.
  • Modèle MQA :

    • L'encodeur prend 195 ms, soit 1,5 µs par token.
    • Chaque étape du décodeur prend 3,9 ms, soit 3,8 µs par token décodé : nettement plus rapide que la référence.

Conclusion

Rapide et efficace !

Avec une précision presque inchangée, l'inférence s'accélère fortement, d'environ dix fois pour le décodage autorégressif !