Show HN : possibilité de doubler la vitesse d’inférence des LLM (Speeding up LLM inference 2x times (possibly))

Qu’est-ce que l’effort ?

• L’effort désigne l’énergie, le temps et les ressources investis pour accomplir une tâche ou atteindre un objectif
• Il désigne le travail et la peine nécessaires pour surmonter des obstacles ou obtenir le résultat souhaité
• L’effort peut être physique ou mental
  • effort physique, comme l’énergie utilisée pour soulever des objets lourds ou courir un marathon
  • effort mental, comme la concentration et la force mentale nécessaires pour résoudre des problèmes complexes ou apprendre une nouvelle compétence
• C’est un élément clé pour réussir dans de nombreux domaines de la vie, comme le développement personnel, le travail ou l’éducation

L’avis de GN⁺

• L’effort n’est pas seulement une question de quantité de temps ou d’énergie investie ; c’est aussi un concept où interagissent de manière complexe la persévérance, la concentration, la motivation et d’autres facteurs. Par conséquent, travailler dur ne garantit pas nécessairement le succès
• En particulier pour les tâches qui demandent un effort mental, il faut veiller à ne pas tomber dans le burn out. Il est important de trouver des moyens de soutenir cet effort grâce à un repos approprié et à des récompenses adaptées
• La manière de fournir un effort peut varier d’une personne à l’autre. Certains peuvent s’y consacrer intensément sur une courte période, d’autres de façon régulière sur le long terme. Il est efficace de trouver la méthode qui vous convient

[GN⁺]

Avis sur Hacker News

• Le cœur de l’algorithme semble consister à élaguer des paramètres à l’exécution et, dans chaque groupe, à déterminer les poids les moins importants selon le rang de leur valeur absolue parmi les poids à élaguer, puis à les mettre à 0 afin de rendre la matrice de poids creuse
  Une recherche sur l’élagage de modèles donne beaucoup de résultats, et https://arxiv.org/abs/2305.11627 traite aussi de l’« élagage fondé sur l’amplitude » comme baseline en citant https://arxiv.org/pdf/2301.00774.pdf
  Je n’aime pas trop quand des articles implémentent leur baseline de façon bâclée pour mieux mettre en avant leur propre méthode, ou l’enrobent d’une montagne de jargon mathématique. Le billet de blog d’origine explique la méthode bien plus clairement, même à quelqu’un qui n’a presque aucune connaissance préalable

  • J’ai passé le dernier mois à rendre la recherche aussi reproductible et fiable que possible. L’implémentation d’origine était très inefficace, et même après l’accélération des multiplications de matrices sur Metal/GPU, j’ai passé beaucoup de temps à aligner le reste de l’implémentation au plus près de Llama.cpp pour faciliter les benchmarks
    Les approches des articles mentionnés semblent statiques, et je n’ai pas l’impression qu’elles proposent un algorithme qui accélère réellement le calcul avec des résultats à 20~50 %. C’était une grande partie de la difficulté. J’aimerais prendre le temps, un jour, de parcourir sérieusement la littérature sur le sujet
    Au final, j’aimerais ajouter une page de références avec les articles que les gens ont postés dans les commentaires. Quelqu’un finira peut-être bientôt par retrouver un texte qui a déjà formalisé cet algorithme
    Pendant le développement, j’ai aussi demandé à gpt-4 et fait des recherches Google, mais ce que j’ai trouvé relevait surtout d’approches statiques ou consistait à supprimer arbitrairement des dimensions/couches entières puis à réentraîner. Je n’ai rien trouvé qui corresponde exactement à cette idée
  • « Enrober sa méthode de jargon mathématique et implémenter la baseline de façon médiocre », ça ressemble au signe d’un mauvais article
    Plus un texte est dense et difficile à comprendre, plus il est probable qu’il cache une science médiocre

• J’ai aimé cette phrase dans la partie sur l’implémentation GPU
  « Un lecteur qui découvre la programmation GPU peut maintenant se demander : comment est-ce que ça marche ?
  Un lecteur qui a de l’expérience en programmation GPU peut se demander : mais comment est-ce que ça marche, au juste ? »

  • Si j’ai bien compris, il a fallu implémenter les lectures mémoire et quelques autres éléments à l’inverse de ce qui est généralement considéré comme la bonne approche
    J’aimerais bien qu’une personne qui connaît vraiment Metal relise ce code. C’était ma première tentative de programmation GPU

• « Inversions la matrice, trions les éléments par ligne, puis regardons la multiplication dans cette direction. Les gens intelligents appellent ça le format compressed sparse row (CSR). Pour multiplier, on prend alors le 1 du vecteur, on le multiplie par 256, puis on l’ajoute à la 3e ligne du vecteur de sortie, et ainsi de suite. Voyons maintenant ce qui se passe si l’on coupe la dernière colonne, où se trouvent les plus petites valeurs. »
  Je me demande comment le CSR s’articule avec la réduction du nombre de multiplications

  • Tu pourrais reformuler la question ? Je ne suis pas sûr de bien l’avoir comprise

• Cette approche ressemble à de la creusité semi-structurée, autrement dit de la creusité 2:4, donc une comparaison explicite vaudrait le coup. À première vue, cette technique est optimisée pour Apple Silicon, offre environ 2x de vitesse à 75 % de creusité, s’applique dynamiquement à l’exécution selon l’entrée, et permet de choisir le degré de creusité
  À l’inverse, la creusité semi-structurée 2:4 est optimisée pour les GPU dotés de sparse tensor cores, donc Nvidia Ampere et suivants, offre environ 2x de vitesse à 50 % de creusité, s’applique statiquement au moment du stockage du modèle, et à 50 % de creusité pourrait donner de moins bons résultats que cette technique
  La comparaison que j’aimerais voir est celle entre les résultats de la creusité semi-structurée à 50 % de creusité avec un gain de vitesse de 2x, et ceux de cette technique à 75 % de creusité avec un gain de vitesse de 2x

  • Merci d’avoir vérifié. J’attends moi aussi avec impatience l’arrivée rapide de plus de tests
    J’ai choisi Apple Silicon parce que c’était plus simple pour le développement. Il est possible que cet algorithme obtienne aussi de bonnes performances sur d’autres architectures

• Pour avoir déjà utilisé le CSR, ça ne me surprend pas. Parmi les formats plus récents, il y en a peut-être qui collent mieux aux caractéristiques matérielles, comme block ELL
  Ces formats évitent les lectures non fusionnées ou les gather, mais le code devient plus compliqué

  • Ravi de tomber enfin sur quelqu’un qui a de l’expérience avec le CSR
    bucketMul n’a presque pas de lectures non fusionnées et utilise une structure de données différente du CSR classique. C’est expliqué ici : https://kolinko.github.io/effort/bucketmul.html
    Chaque ligne de la matrice est découpée en 16 parties, puis on sélectionne celles qu’il faut lire. Les écritures sont entièrement linéaires
    Cela dit, je ne sais pas trop si ce que je raconte a du sens pour l’instant. Il est un peu tard aujourd’hui, et la journée a été longue

• Excellente idée et excellent billet. Je travaille aussi sur la sparsité en inférence de réseaux de neurones, et quelques points utiles me viennent à l’esprit
  Par rapport à une implémentation dense de multiplication matrice-vecteur, cet algorithme ajoute de la complexité algorithmique mais réduit le trafic mémoire. La multiplication matrice-vecteur est généralement limitée par la mémoire, donc réduire les accès mémoire augmente le débit. En revanche, dès que la taille de batch dépasse 1, l’accès mémoire cesse probablement d’être le goulet d’étranglement, et le gain de vitesse risque de disparaître très vite
  J’aimerais voir des comparaisons non seulement avec le même modèle, mais aussi avec d’autres modèles ayant une architecture 2x plus rapide. Par exemple, si on applique cette méthode à un LLM de 13B de paramètres avec 50 % de sparsité, comment se comporte-t-il face à un LLM de 7B, ou face au même LLM quantifié à la moitié de la largeur de bits de référence ? S’il peut produire, dans le même temps, des sorties de fidélité supérieure à celles des frameworks d’inférence existants, cela pourrait faire un article vraiment intéressant
  Comme on omet des multiplications, l’erreur d’approximation risque d’être systématiquement biaisée vers des valeurs absolues plus faibles que le résultat réel. S’il est possible d’ajouter un terme de correction pour compenser cette erreur systématique, les performances pourraient encore un peu s’améliorer

  • La complexité algorithmique n’augmente pas vraiment. Les multiplications sont en O(effrt * inDim * outDim), le calcul de dispatch en O(inDim), et la recherche du point de coupure en O(~inDim * log inDim)
    La notation Big O n’est pas idéale pour le travail sur GPU, mais ici elle reste approximativement juste
    Le principal problème vient des limites architecturales du GPU. Cet algorithme demande plus de registres / groupes de threads / mémoire cache que l’approche traditionnelle, et c’est cela qui devient le principal goulet d’étranglement. De plus, comme toutes les multiplications utilisent des buckets différents, il n’est pas simple de paralléliser le travail comme avec des modèles MoE
    Pour les architectures plus grandes, j’ai en fait beaucoup testé sur Mixtral, qui est en pratique un modèle 13B, et j’ai l’impression qu’il tient bien mieux le coup. La vitesse d’inférence par rapport à l’effort s’y maintient, et la qualité par rapport à l’effort reste lisible jusqu’à 12–16 %, au lieu de 20–25 %. Les tests ont été limités, et j’ai cassé l’implémentation Mixtral en intégrant celle de Mistral, donc je n’ai pas encore de données solides, mais je compte corriger ça bientôt
    Intuitivement, je pense que plus le modèle est gros, plus on peut réduire l’effort
    Au départ, je supposais aussi que l’omission de multiplications introduirait un biais, mais contrairement à cette intuition, ce n’est pas le cas. J’ai quelques graphiques, mais ils ne sont pas encore prêts à être publiés
    Comme les valeurs de la matrice sont réparties de manière équilibrée entre positives et négatives, au-delà d’un certain seuil il n’y a pas de dérive importante dans le résultat

• Ça a l’air excellent. Cela dit, 15 ms de latence est proche des 16,7 ms de la synchronisation verticale à 60 Hz
  Si vous rafraîchissez l’écran à chaque token, cela pourrait être une cause de synchronisation quelque part

  • Ce n’est pas ça. Je mesure séparément les tâches CPU et GPU, et les 15 ms se produisent entre les appels de noyau. Cela arrive même sans afficher le texte
    Merci quand même pour l’idée. Je vais la prendre comme première contribution de la communauté :D

• C’est vraiment chouette, et une contribution très ouverte. Je vais surveiller de près si llama.cpp implémente ça
  Je cherchais justement un moyen d’accélérer l’inférence sur CPU, et j’aime beaucoup l’idée d’effort

  • Développer ça a été un marathon, et je suis ravi que ce soit arrivé en page principale
    Le nom a été proposé par chatgpt. Comme il ne semblait pas reconnaître cette approche, il est possible qu’elle soit vraiment nouvelle
    J’aimerais contacter llama.cpp et d’autres projets, et j’espère que ce sera implémenté. J’ai même pensé à écrire moi-même un patch pour llama, mais le C++ et l’ampleur du projet étaient trop intimidants pour moi
    L’inférence CPU sera accélérée elle aussi. En plus, comme on peut ne charger qu’une partie des poids — par exemple seulement 70 % en sautant les moins importants — on pourra faire tourner le modèle avec moins de VRAM qu’avant. Il faut encore une implémentation Q8, cependant
    Fait amusant, quand j’ai voulu comparer les benchmarks avec llama.cpp, je n’ai pas trouvé de vitesse pour du 7B/FP16 sur un MB Air 16 GB. Avec la méthode classique, ce n’est tout simplement pas exécutable. Avec Effort, ça l’est
    De même, j’ai fait tourner Mixtral tronqué mais en pleine résolution sur un M2 de 96 GB. Normalement il faut 114 GB de RAM, mais en ne chargeant que 75 % des poids, ça tournait de manière fluide. Pour l’instant, j’ai un peu cassé l’implémentation et elle produit des sorties absurdes, donc il faut corriger ça

• Bon billet. Je suis vraiment curieux de voir ce que vaut la performance par VRAM par rapport à une simple quantification
  Je me demande aussi s’il est prévu d’implémenter une version cross-platform

  • La performance par VRAM n’est pas énormément meilleure. La structure utilise toujours tous les poids, simplement pas toujours tous à chaque fois
    Bien sûr, on peut aussi en charger moins, mais au-delà de 20 à 30 % de poids retirés, la qualité semble se dégrader rapidement
    Autrement dit, cet algorithme découple le temps d’inférence de l’usage de VRAM
    Cela dit, je suis moi aussi curieux de voir si un Q8 réduit à 75 % avec effort peut donner de meilleurs résultats qu’un Q6
    Mais il me faudra probablement encore quelques semaines pour suffisamment peaufiner l’implémentation et faire des tests corrects

• Cette approche ne fait pas de réentraînement, mais je me demande si on pourrait combiner ce type d’approche avec la quantification, puis faire un apprentissage supplémentaire ensuite pour récupérer une partie de la qualité perdue
  J’aime voir ce genre de choses, et ça aide à se représenter jusqu’où les performances et les coûts peuvent encore s’améliorer. Merci de développer ça en open source

  • À première vue, cela semble possible. D’après ce que j’ai lu, il existe deux grandes façons de récupérer une partie de la qualité en quantification
    La première est un apprentissage a posteriori, et la seconde est la quantification-aware training, où l’on quantifie pendant l’apprentissage tout en conservant les activations et les gradients en pleine précision