Llama : ajout de l’échantillonnage basé sur une grammaire

 (github.com/ggerganov)
1 points par GN⁺ 2023-07-23 | 1 commentaires | Partager sur WhatsApp
  • La PR #1773 de llama.cpp propose l’ajout d’une API qui restreint les candidats d’échantillonnage à l’aide d’une grammaire hors contexte, afin d’empêcher que le résultat généré ne s’écarte du format spécifié
  • L’API reçoit une structure de grammaire fondée sur des points de code 32 bits, filtre ensuite les tokens candidats avec llama_sample_grammar, puis répercute le token choisi dans l’état de la grammaire avec llama_grammar_accept_token
  • Des arguments --grammar et --grammar-file ont été ajoutés à main pour fournir une grammaire au format BNF étendu, avec comme exemples Chess, les expressions arithmétiques, JSON et la génération dans des plages de caractères japonais
  • Les tests ont été réalisés sur un M2 Max et un modèle 30B Q4_0 ; avec la grammaire, la sortie est contrainte à la notation d’échecs, aux expressions arithmétiques, au JSON et aux plages de caractères japonais, tandis que sans grammaire le modèle génère du texte généraliste ou du code sans rapport avec le prompt
  • Les discussions se sont concentrées sur des contraintes d’usage réel comme la prise en charge des fichiers de grammaire, le traitement des lignes vides et des commentaires, l’inclusion ou non du parseur dans l’API, le masquage des logits sur GPU, le traitement par lots de tokens fixes et le surcoût en performances

Changements clés de la PR

  • Il s’agit d’une PR qui ajoute un échantillonnage basé sur une grammaire à llama.cpp
  • Elle s’appuie sur des travaux existants, notamment #1397 et le travail CFG de grantslatton
  • La nouvelle API reçoit une grammaire hors contexte sérialisée pour guider et contraindre l’échantillonnage
  • Des exemples de grammaire de type BNF ont été ajoutés à main pour spécifier la grammaire de génération

Structure de l’API Grammar

  • L’API llama reçoit une structure de grammaire hors contexte portant sur des points de code 32 bits
  • Les types d’éléments de grammaire représentent la fin d’une règle, le début d’une alternative, une référence de règle, un caractère, la borne supérieure d’une plage de caractères et l’ajout d’un caractère alternatif
  • La fonction d’initialisation reçoit les informations suivantes
    • un tableau de règles
    • le nombre de règles
    • l’indice de la règle de départ
  • llama_grammar_element possède un type et une value, cette dernière étant utilisée comme point de code Unicode ou comme identifiant de règle

Méthode d’échantillonnage

  • Le code d’échantillonnage grammatical modélise un automate à pile non déterministe
  • Il maintient N piles pour représenter les états de parsing possibles
  • L’échantillonnage des tokens fonctionne en deux étapes
    • llama_sample_grammar ne conserve parmi les candidats que ceux compatibles avec au moins une pile de parsing
    • llama_grammar_accept_token ajoute le token sélectionné à l’état de la grammaire

Saisie de grammaire dans main

  • Des arguments --grammar et --grammar-file ont été ajoutés à main
  • Ces deux arguments acceptent une grammaire simple de type BNF étendu pour contraindre le résultat généré
  • Le parseur de grammaire est implémenté dans examples/grammar-parser.{h,cpp}
  • Les fonctionnalités de grammaire prises en charge incluent les plages de caractères, le groupement et les opérateurs de répétition
  • La règle root identifie le point de départ de la grammaire
  • Des mises à jour ultérieures ont ajouté la prise en charge des fichiers de grammaire, des exemples supplémentaires, les commentaires de style shell, les lignes vides entre les règles et les retours à la ligne dans les groupes entre parenthèses

Exemples de test

  • L’environnement de test mentionné est un modèle M2 Max, 30B
  • Exemple Chess
    • Avec --grammar-file grammars/chess.gbnf, le modèle génère des notations d’échecs comme 1. e4 e5, 2. Nf3 Nc6
    • Sans grammaire, le même prompt produit une phrase générale à propos de Sir Thomas Gresham
  • Exemple d’expression arithmétique
    • Une grammaire inline impose une forme expr "=" ws num "\n"
    • Le résultat est alors limité à des expressions arithmétiques comme 10 *a*1 +b*2 =640
    • Sans grammaire, le modèle génère un fragment de code Go
  • Exemple JSON
    • Avec grammars/json.gbnf, le modèle génère une structure JSON du type { "fullName": ..., "address": ... }
    • Sans grammaire, il produit une prose de type présentation personnelle
  • Exemple japonais
    • grammars/japanese.gbnf autorise l’hiragana, le katakana, la ponctuation et les plages CJK
    • Avec la grammaire, une liste fondée sur des caractères japonais est générée
    • Sans grammaire, le modèle produit une liste à étapes en anglais

Revue et discussions de conception

  • Une proposition a été faite pour fournir la grammaire via un fichier, et la prise en charge des grammar files ainsi que des exemples ont ensuite été ajoutées
  • Parmi les problèmes relevés lors des premiers usages figuraient un conflit avec --prompt-cache et un crash provoqué par des lignes vides dans la grammaire
  • La prise en charge des lignes vides et des commentaires, ainsi que l’autorisation des retours à la ligne dans les groupes entre parenthèses, ont été incluses dans des commits ultérieurs
  • Une discussion a porté sur l’inclusion du parseur dans l’API de llama.cpp
    • Si le parseur reste hors de l’API, les utilisateurs downstream risquent de devoir le copier pour prendre en charge la fonctionnalité
    • L’auteur voulait limiter les modifications de llama.cpp lui-même, tout en reconnaissant qu’intégrer le parseur à l’API serait plus pratique
  • Il a aussi été proposé que llama_grammar conserve une copie binaire de la grammaire, afin que l’utilisateur n’ait pas à garantir la durée de vie de la copie transmise

Discussions sur les performances et l’optimisation

  • Il est compris qu’à l’heure actuelle, même lorsque les N > 1 tokens suivants sont déterminés de manière unique par la grammaire, ils sont échantillonnés un par un
  • Une discussion a eu lieu sur le fait qu’une évaluation par lots de plusieurs tokens fixes pourrait fortement accélérer l’inférence dans ce cas
  • L’auteur a répondu qu’il faut tout de même évaluer les tokens et que le goulot d’étranglement semble se situer de ce côté ; selon lui, une évaluation par lots au niveau des chaînes pourrait constituer une piste d’optimisation
  • L’idée de compiler la grammaire sur GPU sous forme de tenseur de transition d’état, ou d’effectuer un masquage des logits sur GPU pour l’ensemble du vocabulaire, a également été évoquée
  • torch-grammar a été cité comme approche similaire, réalisant sur GPU un masquage des logits imposé par la grammaire sur l’ensemble du vocabulaire

Observations de performance

  • L’auteur précise n’avoir testé que l’inférence CPU et n’avoir pas constaté d’impact majeur sur les performances dans la plage de ses essais
  • Mesures observées sur M2 Max
    • l’échantillonnage non contraint est d’environ 0.5ms/token
    • l’échantillonnage avec grammaire est d’environ 6ms/token
    • l’évaluation des tokens sur un 13B Q4_K est d’environ 70ms/token
  • Un autre utilisateur a signalé un cas où le débit passe d’environ 20T/s à 13T/s sur un 13B
  • L’auteur estime généralement le surcoût de la grammaire à environ 5ms/token, tout en notant que certaines grammaires ont eu un impact plus important et qu’il pourrait exister des cas pathologiques

Discussions liées aux extensions

  • L’idée d’utiliser une entrée JSON Schema convertie en BNF a été mentionnée
  • L’auteur indique disposer d’une branche locale fonctionnant avec l’exemple du README de jsonformer, ainsi que d’un script Python qui génère une BNF JSON conforme à un JSON Schema
  • Par la suite, examples : generate JSON according to schema #1887 a été mentionné en lien avec cette PR
  • Il a été répondu que cette approche est indépendante des variantes de modèle et peut aussi être utilisée avec des modèles fine-tunés
  • Une PR distincte ajoutant l’échantillonnage basé sur une grammaire à whisper.cpp a également été mentionnée

À lire aussi

1 commentaires

 
GN⁺ 2023-07-23
Commentaires sur Hacker News

  • Voici comment je comprends le fonctionnement. Le modèle de langage émet un token à la fois à partir du prompt comme point de départ, et une conversation avec un LLM peut aussi se voir comme une séquence de tokens fournie par l’utilisateur, puis partiellement générée par le modèle, puis prolongée à nouveau par l’utilisateur
    Cette technique de grammaire permet un contrôle beaucoup plus fin des tokens. Par exemple, si on lui donne Give me the address of the White House as JSON: {"street": ", le LLM peut renvoyer 1600 Pennsylvania Ave NW", puis au moment où l’on voit le guillemet fermant, l’utilisateur injecte ", "City": " pour obtenir Washington, DC"
    Mais comme c’est basé sur une grammaire, cela peut faire bien plus que du JSON. J’avais aussi vu auparavant sur Twitter une proposition intéressante : qu’OpenAI accepte une grammaire context-free déterministe comme argument d’API, ou mieux encore, un petit binaire WASM servant directement de sampler, de quelques Ko, exécutable avec quelques Mo de mémoire, ce qui pourrait considérablement étendre les capacités des LLM
    https://twitter.com/grantslatton/status/1637692033115762688

    • En plus, le LLM ne produit pas directement chaque token individuellement, mais plutôt une liste de recommandations pondérée. Le token le plus plausible reçoit le poids le plus élevé, mais il peut aussi y avoir plusieurs alternatives, y compris des symboles JSON comme les guillemets
      Le réglage temperature ajuste la probabilité qu’un token autre que le mieux classé soit choisi, afin de réduire les sorties répétitives. Forcer un LLM à respecter une grammaire consiste généralement à filtrer cette liste avant la sélection du token, tout en conservant malgré tout l’aléa contrôlé par la temperature
      Une fonctionnalité plus avancée consisterait à autoriser un retour en arrière quand l’IA est bloquée et ne peut plus produire une sortie valide
    • En pratique, le fonctionnement consiste à vérifier avec la grammaire la sortie courante ainsi que les tokens suivants candidats à l’échantillonnage, puis à supprimer tous les tokens candidats qui ne conviennent pas. On applique ensuite la stratégie d’échantillonnage habituelle à la liste restante de tokens valides
    • Cette explication ne me semble pas correcte. On pouvait déjà auparavant contrôler la sortie d’un LLM en lisant les tokens un par un puis en s’arrêtant lorsqu’on rencontrait un caractère d’arrêt
      À mon avis, l’essentiel de cette PR sur l’échantillonnage basé sur la grammaire est que llama.cpp utilise la grammaire pour restreindre le prochain token de sortie à un ensemble limité de tokens possibles
    • Il existe aussi une explication plus détaillée de l’implémentation : https://github.com/normal-computing/outlines/pull/131
      Elle a été écrite par l’un des développeurs de la bibliothèque Outlines, qui est aussi une bonne bibliothèque de workflow pour LLM
    • Je ne comprends pas très bien ce qu’il raconte. À partir de “passing up”, on dirait qu’il a inventé sa propre terminologie. La seule entrée qu’on puisse fournir à un LLM est un prompt qui sera tokenisé
      Même si l’on envoie des règles DCFG ou leur version compilée dans la requête, je ne vois pas en quoi cela changerait fondamentalement la façon dont le modèle prédit les tokens. Si le modèle prédit quelque chose qui ne respecte pas la grammaire demandée, cela veut-il dire qu’il faut réinjecter le prompt jusqu’à ce qu’il tombe juste ?

  • Il faut souligner que cela ne fait qu’imposer des contraintes grammaticales sur le texte généré par le modèle, et non assurer un véritable alignement du contenu. C’est utile lorsqu’il faut garantir qu’un serveur renvoie du JSON bien formé, mais cela ne résoudra probablement pas beaucoup des problèmes actuels d’alignement en génération de langage
    Par exemple, aujourd’hui Llama ou GPT se trompent souvent dans les libellés de blocs de code Markdown. On peut les forcer à mettre un libellé avec l’échantillonnage basé sur la grammaire, mais on ne peut pas forcer que ce soit le bon, car cela dépend du contexte. Et il est difficile d’espérer de bonnes sorties après avoir créé un nouveau langage spécifique à un domaine sans aligner ensuite le modèle sur ce langage

    • Il est aussi important de noter que dès qu’une chaîne libre est autorisée, cela devient une invitation ouverte pour que le LLM parte complètement dans une mauvaise direction. C’est pourquoi cette méthode gagne à être combinée avec d’autres heuristiques, comme une pénalité de répétition, afin de biaiser l’échantillonnage lorsqu’on entre dans des zones de texte libre
    • Malgré tout, avec Llama on pourrait entraîner quelques exemples dans une LoRA
      On peut par exemple imaginer un système qui hot-swap à la demande une LoRA pour Markdown et un fichier de grammaire Markdown

  • J’aime vraiment beaucoup ça. J’avais déjà créé Constrained Text Generation Studio (https://github.com/Hellisotherpeople/Constrained-Text-Genera...), et un article associé a même été présenté à COLING 2022 (https://paperswithcode.com/paper/most-language-models-can-be...)
    Malgré tout, j’ai toujours pensé que ce type d’approche, ainsi que les idées connexes listées dans cet article, allaient dans la bonne direction : https://arxiv.org/abs/2306.03081
    Il va maintenant falloir réfléchir à la façon de construire des grammaires capables d’imposer des choses comme le nombre de syllabes ou des règles syntaxiques. Les LLM actuels sont très mauvais pour ce genre de tâche à cause de leur mode de tokenisation

    • C’était inattendu, mais Nous Hermes écrit des haïkus plutôt convaincants

  • Cela a aussi été implémenté pour PyTorch : https://github.com/Shopify/torch-grammar. Il existe aussi une version bricolée de text-generation-inference qui l’utilise, je peux la partager si besoin

    • Je veux bien. J’essayais justement de dumper le vecteur de probabilités des tokens dans l’une des interfaces LLM, donc avoir un autre point de départ pourrait être très utile

  • Pour une énumération de chaînes à choix multiple, en pratique l’équivalent d’une liste déroulante, je me demande s’il ne vaudrait pas mieux, au moment du choix final, considérer la probabilité jointe totale sous les logits donnés plutôt qu’un algorithme glouton
    Quand le token de départ est partagé par plusieurs éléments de la liste, cela pourrait amener à préférer la bonne option plutôt qu’une option contenant simplement le token initial le plus fréquent. Bien sûr, une fois qu’une partie des logits a été mise à zéro, il faut réajuster les probabilités pour que cela ait encore un sens

  • Cette « bibliothèque » de grammaires a été citée comme exemple de formats : https://github.com/antlr/grammars-v4
    On y trouve de tout, de l’assembleur et du C++ à GLSL, des langages de script, l’arithmétique, les jeux, les raccourcis freedesktop, LLVM IR, Verilog, jusqu’à des formats plus atypiques

    • Ce serait pratique de pouvoir indiquer dans l’API d’inférence des raccourcis vers des grammaires standard comme HTML, JSON ou Python. Vu les efforts qu’OpenAI a consacrés au fine-tuning du modèle Code Interpreter, il est franchement étrange qu’ils n’aient pas encore fait ça
    • Ce serait vraiment bien de prendre en charge la syntaxe des grammaires ANTLR4. C’est un excellent outil

  • Quelqu’un peut m’expliquer simplement ? Je connais un peu les LLM, mais je ne vois pas bien ce que Georgi fait ici ni pourquoi certains sont aussi enthousiastes

    • Un LLM ne génère pas directement le « prochain token ». Il produit un vecteur de probabilités où chaque case correspond à un token du texte d’entrée, et chaque valeur peut être vue comme une approximation de la probabilité que ce token soit le suivant
      Un programme comme ChatGPT « interprète » ensuite ce vecteur de probabilités pour choisir, c’est-à-dire échantillonner, un des tokens les plus probables et produire du texte. Mais cette méthode est parfois trop souple : même si on veut une sortie JSON, elle peut choisir un token qui ne respecte pas la grammaire JSON et produire un JSON invalide
      Une façon de « forcer » le LLM à générer quelque chose comme du JSON consiste à modifier le processus d’échantillonnage. Au lieu de choisir parmi n’importe quels tokens probables, on ne garde d’abord que ceux compatibles avec la grammaire JSON, puis on échantillonne parmi ce sous-ensemble
    • Quand on demande à un LLM de générer du JSON ou un autre langage doté d’une grammaire, il produit parfois une syntaxe invalide. Cette PR modifie la procédure d’échantillonnage pour contraindre le LLM à ne produire qu’une syntaxe valide selon une grammaire fournie par l’utilisateur
      Le LLM génère le texte token par token. D’abord, un énorme réseau de neurones attribue une probabilité à tous les tokens possibles, puis la procédure d’échantillonnage utilise ces probabilités pour en choisir un, avant de répéter l’opération
      La procédure d’échantillonnage n’étant pas un réseau de neurones, on peut la modifier de nombreuses façons. On peut faire de l’échantillonnage glouton en choisissant toujours le token le plus probable, mais en général un choix aléatoire pondéré par les probabilités est préférable. Cela apporte de la diversité et réduit le risque de boucler. En revanche, n’importe quel token dont la probabilité n’est pas nulle peut être choisi, ce qui peut produire un JSON invalide. Cette PR met la probabilité de tous les tokens grammaticalement invalides à 0, afin qu’ils ne puissent pas être sélectionnés
      On peut aussi imaginer d’autres modifications intéressantes du processus d’échantillonnage. Si, en échantillonnant token par token, on arrive dans une impasse sans aucun choix possible, on pourrait autoriser un retour en arrière. Mieux encore, on peut considérer plusieurs choix à chaque étape pour construire un arbre des sorties possibles, puis sélectionner à la fin le chemin dont la probabilité totale est la plus élevée. Si on considère tous les choix, on obtient un arbre complet qui se ramifie selon le nombre de tokens possibles et grossit de façon exponentielle ; on peut donc l’élaguer en ne gardant par exemple que les 5 meilleurs chemins à chaque étape. C’est la recherche en faisceau. Comme le coût d’exécution du réseau de neurones qui produit les probabilités est très élevé, multiplier ce coût par 5 est généralement trop lourd pour les LLM, donc on l’utilise rarement, mais c’est possible et cela améliore un peu les résultats. On peut aussi imaginer utiliser une recherche arborescente Monte-Carlo, comme dans les moteurs d’échecs
    • Un LLM génère volontiers des chaînes arbitraires. On voulait peut-être quelque chose comme « Alice: 42 », mais il peut répondre « Bonjour, je suis un modèle utile et selon moi Alice vaut exactement forty two, mais je ne suis qu’un modèle de langage »
      On lui donne donc une grammaire disant que la réponse doit se terminer après une majuscule suivie de lettres minuscules, d’un deux-points, d’une espace et de chiffres. Alors, lors du choix du premier token, seuls les tokens compatibles avec ce motif sont pris en compte, puis seuls ceux compatibles avec le motif suivant sont considérés à leur tour
      Ce type de grammaire permet de faire cela d’une manière souple et utile
    • Voir mon commentaire ici : https://news.ycombinator.com/item?id=36820884

  • Je trouve ça intéressant et je vais essayer de l’intégrer dans ce que je fais. Mais j’ai l’impression que, du point de vue de la Bitter Lesson, ce n’est peut-être pas la meilleure approche au-delà du très court terme : http://www.incompleteideas.net/IncIdeas/BitterLesson.html

    • C’est peut-être un pis-aller, mais un pis-aller important. Il n’est pas certain que les LLM résolvent « naturellement » les problèmes de génération de texte sous contraintes dans les prochaines années
    • Je suis loin d’être un expert, mais il me semble qu’OpenAI utilise ce genre d’approche dans certaines API GPT pour la programmation. J’ai aussi vu l’hypothèse selon laquelle confier le traitement de grammaires simples à un processus simple et adapté permet au LLM d’utiliser plus efficacement ses ressources de calcul pour les tâches complexes. Je ne sais pas si c’est vrai

  • Il existe aussi un projet qui utilise une méthode similaire : https://github.com/automorphic-ai/trex
    Playground : https://automorphic.ai/playground

  • J’aimerais qu’on me recommande des articles ou des synthèses expliquant comment se font le sampling/décodage à l’ère des réseaux neuronaux de bout en bout. Je sais comment le décodage se faisait en traduction automatique et en reconnaissance vocale à l’époque des HMM, par exemple avec des choses comme le https://en.wikipedia.org/wiki/Viterbi_algorithm ou le https://en.wikipedia.org/wiki/Beam_search
    De nos jours, j’ai l’impression que les gens font simplement du mode « greedy », mais je n’en suis pas sûr. S’il y a des ressources à recommander sur ce sujet, je suis preneur

    • C’est à la fois greedy et aléatoire :) Je recommanderais surtout de regarder les algorithmes des implémentations de LLM plutôt que des articles. rwkv.cpp a une implémentation Python relativement propre ici : https://github.com/saharNooby/rwkv.cpp/blob/master/rwkv/samp...
    • En lisant la documentation de GPT-4, ça ne semble pas très différent de ce que vous avez mentionné
      https://platform.openai.com/docs/api-reference/completions/c...
      Bien sûr, on sait maintenant que GPT-4 a une architecture de mélange d’experts, donc les calculs y sont parallélisés en interne. Cela inclut aussi une méthode qui modifie les logits via des termes de pénalité de présence/fréquence.