Llama: Grammatikbasiertes Sampling hinzugefügt

 (github.com/ggerganov)
1 Punkte von GN⁺ 2023-07-23 | 1 Kommentare | Auf WhatsApp teilen
  • llama.cpp PR #1773 schlägt eine API vor, die Sampling-Kandidaten mithilfe einer kontextfreien Grammatik einschränkt, damit die generierten Ergebnisse nicht vom vorgegebenen Format abweichen
  • Die API nimmt eine Grammatik-Datenstruktur auf Basis von 32-Bit-Codepoints entgegen, filtert Kandidaten-Tokens mit llama_sample_grammar und übernimmt das ausgewählte Token anschließend mit llama_grammar_accept_token in den Grammatikzustand
  • In main wurden die Argumente --grammar und --grammar-file hinzugefügt, über die Grammatiken in erweiterter BNF-Form eingegeben werden können; als Beispiele werden Chess, arithmetische Ausdrücke, JSON und die Generierung japanischer Zeichenbereiche gezeigt
  • Die Tests wurden auf einem M2 Max mit einem 30B-Q4_0-Modell durchgeführt; mit Grammatik werden Ausgaben auf Schachnotation, arithmetische Ausdrücke, JSON bzw. japanische Zeichenbereiche beschränkt, während ohne Grammatik allgemeiner Text oder Code erzeugt wird, der nicht zum Prompt passt
  • In der Diskussion standen Praxis-Einschränkungen wie Unterstützung für Grammatikdateien, Behandlung leerer Zeilen und Kommentare, Aufnahme des Parsers in die API, GPU-basiertes Logit-Masking, Batch-Verarbeitung fester Tokens und Performance-Overhead im Mittelpunkt

Zentrale Änderungen des PR

  • Es handelt sich um einen PR, der grammatikbasiertes Sampling zu llama.cpp hinzufügt
  • Als Vorarbeiten werden #1397 und grantslattons CFG-Arbeit herangezogen
  • Die neue API nimmt eine serialisierte kontextfreie Grammatik entgegen und steuert bzw. beschränkt damit das Sampling
  • In main wurden BNF-ähnliche Grammatikbeispiele zur Angabe der Generierungsgrammatik ergänzt

Struktur der Grammar API

  • Die llama-API nimmt eine Datenstruktur für kontextfreie Grammatiken über 32-Bit-Codepoints entgegen
  • Die Typen der Grammatikelemente stellen Regelende, Beginn einer Alternative, Regelreferenz, Zeichen, Obergrenze eines Zeichenbereichs und Hinzufügen eines alternativen Zeichens dar
  • Die Initialisierungsfunktion erhält folgende Informationen
    • Regel-Array
    • Anzahl der Regeln
    • Index der Startregel
  • llama_grammar_element besitzt type und value; value wird als Unicode-Codepoint oder Regel-ID verwendet

Sampling-Verfahren

  • Der Grammatik-Sampling-Code modelliert einen nichtdeterministischen Pushdown-Automaten
  • Um mögliche Parsing-Zustände abzubilden, werden N Stacks verwaltet
  • Das Token-Sampling arbeitet in zwei Schritten
    • llama_sample_grammar lässt unter den Kandidaten-Tokens nur diejenigen übrig, die zu einem der Parsing-Stacks passen
    • llama_grammar_accept_token fügt das ausgewählte Token dem Grammatikzustand hinzu

Grammatik-Eingabe in main

  • In main wurden die Argumente --grammar und --grammar-file hinzugefügt
  • Beide Argumente nehmen eine einfache Grammatik in erweiterter BNF entgegen und beschränken damit die generierten Ergebnisse
  • Der Grammatikparser ist in examples/grammar-parser.{h,cpp} implementiert
  • Unterstützte Grammatikfunktionen sind Zeichenbereiche, Gruppierung und Wiederholungsoperatoren
  • Die Regel root identifiziert den Startpunkt der Grammatik
  • In späteren Updates kamen Unterstützung für Grammatikdateien, zusätzliche Beispiele, Shell-Style-Kommentare, Leerzeilen zwischen Regeln und Zeilenumbrüche innerhalb von Klammergruppen hinzu

Testbeispiele

  • Als Testumgebung wird ein M2 Max mit einem 30B-Modell angegeben
  • Chess-Beispiel
    • Mit --grammar-file grammars/chess.gbnf wird Schachnotation wie 1. e4 e5 oder 2. Nf3 Nc6 erzeugt
    • Wird derselbe Prompt ohne Grammatik ausgeführt, entstehen allgemeine Sätze über Sir Thomas Gresham
  • Beispiel für arithmetische Ausdrücke
    • Eine Inline-Grammatik erzwingt eine Form wie expr "=" ws num "\n"
    • Das Ergebnis wird auf arithmetische Ausdrucksformen wie 10 *a*1 +b*2 =640 beschränkt
    • Ohne Grammatik wird ein Go-Codefragment erzeugt
  • JSON-Beispiel
    • Mit grammars/json.gbnf wird eine JSON-Struktur der Form { "fullName": ..., "address": ... } erzeugt
    • Ohne Grammatik entsteht prosaischer Text in Form einer Selbstvorstellung
  • Japanisch-Beispiel
    • grammars/japanese.gbnf erlaubt Hiragana, Katakana, Satzzeichen und CJK-Bereiche
    • Mit Grammatik wird eine auf japanischen Zeichen basierende Liste erzeugt
    • Ohne Grammatik wird eine englische Schritt-für-Schritt-Liste erzeugt

Review und Design-Diskussion

  • Es gab den Vorschlag, Grammatiken aus Dateien entgegenzunehmen; später wurden Unterstützung für grammar file und Beispiele ergänzt
  • Als frühe Probleme bei der Nutzung wurden ein Konflikt mit --prompt-cache und ein Crash durch Leerzeilen in der Grammatik gemeldet
  • Unterstützung für Leerzeilen und Kommentare sowie Zeilenumbrüche innerhalb von Klammergruppen wurden in Folge-Commits aufgenommen
  • Es wurde diskutiert, ob der Parser in die llama.cpp-API aufgenommen werden soll
    • Es wurde die Sorge geäußert, dass Downstream-Nutzer den Parser kopieren müssten, um das Feature zu unterstützen, falls der Parser außerhalb der API bleibt
    • Der Autor wollte Änderungen an llama.cpp selbst begrenzen, stimmte aber zu, dass die Aufnahme des Parsers in die API bequemer wäre
  • Es gab den Vorschlag, dass llama_grammar eine Kopie der binären Grammatik vorhält, damit Nutzer die Lebensdauer der von ihnen übergebenen Kopie nicht selbst sicherstellen müssen

Performance- und Optimierungsdiskussion

  • Selbst wenn die nächsten N > 1 Tokens durch die Grammatik eindeutig festgelegt sind, wird dies derzeit offenbar als Sampling Token für Token verstanden
  • Es wurde diskutiert, dass eine Batch-Auswertung mehrerer fester Tokens in solchen Fällen die Inferenzgeschwindigkeit deutlich erhöhen könnte
  • Der Autor antwortete, dass Tokens ausgewertet werden müssten und der Engpass offenbar bei der Auswertung liege; Batch-Auswertung auf String-Ebene könne ein Optimierungspunkt sein
  • Außerdem wurden Ideen genannt, die Grammatik auf der GPU in einen Zustandsübergangstensor zu kompilieren oder GPU-Logit-Masking über den gesamten Token-Satz durchzuführen
  • torch-grammar wurde als ähnlicher Ansatz erwähnt, der grammatik-erzwingendes Logit-Masking auf der GPU über den gesamten Token-Satz ausführt

Beobachtungen zur Performance

  • Der Autor hat nur CPU-Inferenz getestet und erklärte, dass der Performance-Einfluss in seinen Versuchen nicht groß gewesen sei
  • Auf einem M2 Max beobachtete Werte
    • Uneingeschränktes Sampling: etwa 0,5 ms/token
    • Sampling mit Grammatik: etwa 6 ms/token
    • Token-Auswertung mit 13B Q4_K: etwa 70 ms/token
  • Ein anderer Nutzer berichtete bei 13B von einem Rückgang von etwa 20 T/s auf 13 T/s
  • Der Autor sieht den Grammatik-Overhead üblicherweise bei etwa 5 ms/token, merkte aber an, dass bestimmte Grammatiken stärkere Auswirkungen hatten und pathologische Fälle möglich seien

Verwandte Erweiterungsdiskussion

  • Es wurde erwähnt, JSON-Schema-Eingaben in BNF umzuwandeln und so zu verwenden
  • Der Autor erklärte, es gebe einen lokalen Branch, der passend zum Beispiel aus dem jsonformer-README funktioniere, und ein Python-Skript erzeuge JSON-BNF passend zu einem JSON Schema
  • Später wurde examples : generate JSON according to schema #1887 in Verbindung mit diesem PR erwähnt
  • Dieser Ansatz sei unabhängig von Modellvarianten und könne auch zusammen mit Fine-Tune-Modellen genutzt werden
  • Ein separater PR, der grammatikbasiertes Sampling auch zu whisper.cpp hinzufügt, wurde ebenfalls erwähnt

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2023-07-23
Meinungen auf Hacker News

  • So verstehe ich die Funktionsweise: Ein Sprachmodell gibt, ausgehend vom Prompt, Token für Token aus; auch eine Unterhaltung mit einem LLM kann man so sehen, dass der Nutzer eine Token-Sequenz vorgibt, das Modell etwas generiert und der Nutzer dann wieder etwas anhängt.
    Diese Grammatiktechnik erlaubt eine viel feinere Kontrolle über die Token. Wenn man zum Beispiel bis zu Give me the address of the White House as JSON: {"street": " vorgibt, gibt das LLM 1600 Pennsylvania Ave NW" zurück, und sobald man das schließende Anführungszeichen sieht, injiziert der Nutzer ", "City": " und erhält Washington, DC".
    Da das aber grammatikbasiert ist, kann man damit nicht nur JSON, sondern sehr viel mehr machen. Ein Vorschlag, den ich früher auf Twitter gesehen habe, gefiel mir auch: OpenAI könnte eine deterministische kontextfreie Grammatik als API-Argument entgegennehmen oder sogar ein kleines WASM-Binary, das selbst der Sampler ist, ein paar KB groß ist und mit ein paar MB Speicher läuft. Das könnte die Fähigkeiten von LLMs deutlich erweitern.
    https://twitter.com/grantslatton/status/1637692033115762688

    • Nicht nur das: LLMs geben nicht direkt einzelne Token aus, sondern eine gewichtete Empfehlungsliste. Das plausibelste Token hat das höchste Gewicht, aber es kann mehrere Alternativen geben, einschließlich JSON-Symbolen wie Anführungszeichen.
      Die Einstellung temperature steuert, wie wahrscheinlich es ist, dass nicht das höchstplatzierte Token gewählt wird, und reduziert so wiederholte Ausgaben. Ein LLM dazu zu zwingen, einer Grammatik zu folgen, bedeutet im Wesentlichen, die Liste vor der Token-Auswahl zu filtern; die durch temperature gesteuerte Zufälligkeit kann dennoch erhalten bleiben.
      Als fortgeschrittenere Funktion gibt es auch Ansätze, Backtracking zu erlauben, wenn die KI feststeckt und keine gültige Ausgabe erzeugen kann.
    • In der Praxis werden die aktuelle Ausgabe und die nächsten Token, die Sampling-Kandidaten sind, gegen die Grammatik geprüft, und alle nicht passenden Kandidaten-Token werden entfernt. Auf die verbleibende Liste gültiger Token wird dann die normale Sampling-Strategie angewendet.
    • Diese Erklärung scheint mir nicht zu stimmen. Schon früher konnte man die Ausgabe von LLMs steuern, indem man Token einzeln gelesen hat und beim Auftreten eines Stop-Zeichens angehalten hat.
      Der Kern des PRs zu grammatikbasiertem Sampling scheint mir zu sein, dass llama.cpp mithilfe einer Grammatik das nächste Ausgabe-Token auf eine eingeschränkte Menge möglicher Token verengt.
    • Es gibt auch eine ausführlichere Erklärung zur Implementierung: https://github.com/normal-computing/outlines/pull/131
      Sie stammt von einem der Entwickler der Outlines-Bibliothek; Outlines ist ebenfalls eine brauchbare LLM-Workflow-Bibliothek.
    • Ich verstehe nicht recht, worum es geht. Schon bei „passing up“ frage ich mich, ob diese Person gerade eigene Begriffe erfindet. Die einzige Eingabe, die man einem LLM geben kann, ist ein Prompt, der tokenisiert wird.
      Selbst wenn man als Teil der Anfrage DCFG-Regeln oder eine kompilierte Version davon mitschickt, sehe ich nicht, wie das die Art der Token-Vorhersage grundlegend ändern soll. Wenn das Modell etwas vorhersagt, das nicht zur geforderten Grammatik passt, soll man dann den Prompt so lange erneut einspeisen, bis es passt?

  • Man sollte festhalten, dass dies dem vom Modell erzeugten Text nur grammatische Beschränkungen auferlegt, aber keine echte inhaltliche Ausrichtung sicherstellt. Es ist nützlich, wenn ein Server garantiert wohlgeformtes JSON ausgeben soll, wird aber vermutlich viele der heutigen Alignment-Probleme bei Sprachgenerierung nicht lösen.
    Zum Beispiel versehen Llama oder GPT Markdown-Codeblöcke derzeit häufig mit falschen Labels. Mit grammatikbasiertem Sampling kann man erzwingen, dass ein Label gesetzt wird, aber ob es das richtige Label ist, hängt vom Kontext ab und lässt sich nicht erzwingen. Ebenso ist schwer zu erwarten, dass man eine neue domänenspezifische Sprache erstellt und gute Ausgaben bekommt, ohne das Modell auf diese Sprache auszurichten.

    • Wichtig ist auch, dass eine frei formatierte Zeichenkette eine offene Einladung für das LLM ist, völlig vom Kurs abzukommen. Deshalb kombiniert man solche Verfahren am besten mit anderen Heuristiken, die das Sampling in Freitextbereichen verzerren, etwa einer Repetition Penalty.
    • Bei Llama könnte man trotzdem einige Beispiele in eine LoRA eintrainieren.
      Man könnte sich zum Beispiel ein System vorstellen, das je nach Bedarf eine Markdown-LoRA und eine Markdown-Grammatikdatei per Hot-Swap austauscht.

  • Das gefällt mir wirklich. Ich habe früher einmal das Constrained Text Generation Studio gebaut (https://github.com/Hellisotherpeople/Constrained-Text-Genera...) und dazu wurde auch ein Paper auf der COLING 2022 veröffentlicht (https://paperswithcode.com/paper/most-language-models-can-be...).
    Trotzdem dachte ich immer, dass solche Ansätze oder die in diesem Paper aufgeführten verwandten Ideen der richtige Weg sind: https://arxiv.org/abs/2306.03081
    Jetzt muss ich mir überlegen, wie man eine Grammatik bauen könnte, die Dinge wie Silbenzahl oder syntaktische Regeln erzwingt. Aktuelle LLMs sind wegen ihrer Tokenisierung bei dieser Art von Aufgabe sehr schlecht.

    • Überraschenderweise schreibt Nous Hermes ziemlich überzeugende Haikus.

  • Ich habe das auch für PyTorch implementiert: https://github.com/Shopify/torch-grammar. Es gibt auch eine gehackte Version von text-generation-inference, die das nutzt; bei Bedarf kann ich sie teilen.

    • Es wäre schön, wenn du sie teilen könntest. Ich wollte in einer der LLM-UIs einen Token-Wahrscheinlichkeitsvektor dumpen; ein anderer Ausgangspunkt wäre ziemlich hilfreich.

  • Bei Multiple-Choice-String-Enums, also im Grunde Dropdowns, frage ich mich, ob es besser funktionieren würde, bei der endgültigen Auswahl nicht einen Greedy-Algorithmus zu verwenden, sondern die gesamte gemeinsame Wahrscheinlichkeit des gegebenen Logit-Zustands zu berücksichtigen.
    Wenn Anfangstoken von mehreren Einträgen in der Liste geteilt werden, könnte das dazu führen, dass die richtige Option bevorzugt wird und nicht die Option mit dem häufigsten Anfangstoken. Natürlich muss man die Wahrscheinlichkeiten anpassen, nachdem einige Logits auf 0 gesetzt wurden, damit das tatsächlich sinnvoll ist.

  • Diese Grammatik-„Bibliothek“ wurde als Formatbeispiel zitiert: https://github.com/antlr/grammars-v4
    Dort gibt es alles von Assembly und C++ bis hin zu GLSL, Skriptsprachen, Arithmetik, Spielen, freedesktop-Shortcuts, LLVM IR und ungewöhnlichen Formaten wie Verilog.

    • Es wäre praktisch, wenn man in der Inferenz-API Standard-Grammatik-Shortcuts wie HTML, JSON oder Python angeben könnte. Wenn man bedenkt, wie viel Aufwand OpenAI in das Fine-Tuning des Code-Interpreter-Modells gesteckt hat, ist es ehrlich gesagt seltsam, dass sie so etwas noch nicht machen.
    • Unterstützung für die ANTLR4-Grammatiksyntax wäre wirklich großartig. Das ist ein hervorragendes Tool.

  • Kann das jemand einfach erklären? Ich kenne mich mit LLMs einigermaßen aus, aber ich verstehe nicht so recht, was Georgi hier macht und warum einige so begeistert sind.

    • Ein LLM erzeugt nicht direkt das „nächste Token“. Es erstellt aus dem Eingabetext einen Wahrscheinlichkeitsvektor, bei dem jede Position einem Token entspricht, und jeder Wert ungefähr die Wahrscheinlichkeit angibt, dass dieses Token als Nächstes kommt.
      Programme wie ChatGPT „interpretieren“ diesen Wahrscheinlichkeitsvektor und wählen eines der Top-Tokens aus, also sie samplen, um Text zu erzeugen. Dieser Ansatz ist aber manchmal zu flexibel: Selbst wenn man JSON-Ausgabe möchte, kann ein Token gewählt werden, das nicht zur JSON-Grammatik passt, und dadurch ungültiges JSON entstehen.
      Die Methode, ein LLM zur Erzeugung von etwas wie JSON zu „zwingen“, besteht darin, den Sampling-Prozess zu ändern. Man wählt nicht einfach irgendein Top-Token aus, sondern lässt zuerst nur die Tokens übrig, die zur JSON-Grammatik passen, und sampelt dann aus dieser Teilmenge die Top-Tokens.
    • Wenn man ein LLM bittet, JSON oder eine andere Sprache mit Grammatik zu erzeugen, produziert es gelegentlich fehlerhafte Syntax. Dieser PR beschränkt das LLM darauf, gemäß einer vom Nutzer bereitgestellten Grammatik nur gültige Syntax auszugeben, indem das Sampling-Verfahren geändert wird.
      Ein LLM erzeugt Text tokenweise. Zuerst weist ein riesiges neuronales Netz allen möglichen Tokens Wahrscheinlichkeiten zu; anschließend nutzt das Sampling-Verfahren diese Wahrscheinlichkeiten, um ein Token auszuwählen, und wiederholt diesen Vorgang.
      Das Sampling-Verfahren ist kein neuronales Netz und kann daher auf verschiedene Arten verändert werden. Greedy Sampling, bei dem immer das Token mit der höchsten Wahrscheinlichkeit gewählt wird, ist möglich, aber normalerweise ist eine nach Wahrscheinlichkeit gewichtete Zufallsauswahl besser. Dadurch entsteht Vielfalt, und die Wahrscheinlichkeit, in Schleifen zu geraten, sinkt. Allerdings kann jedes Token mit einer Wahrscheinlichkeit ungleich 0 gezogen werden, wodurch ungültiges JSON entstehen kann. Dieser PR setzt die Wahrscheinlichkeit aller Tokens, die grammatikalisch nicht gültig sind, auf 0, sodass sie nicht ausgewählt werden können.
      Am Sampling-Prozess sind auch andere interessante Änderungen möglich. Wenn man Tokens einzeln sampelt, kann man in eine Sackgasse geraten, in der es keine Optionen mehr gibt; man könnte also Backtracking erlauben. Darüber hinaus könnte man in jedem Schritt mehrere Optionen berücksichtigen, einen Baum möglicher Ausgaben aufbauen und am Ende den Pfad mit der höchsten Gesamtwahrscheinlichkeit wählen. Wenn man alle Optionen berücksichtigt, verzweigt der vollständige Baum um die Anzahl möglicher Tokens und wächst daher exponentiell; man kann ihn aber beschneiden, indem man in jedem Schritt nur die obersten, sagen wir, 5 Pfade behält. Das ist Beam Search. Da die Ausführung des neuronalen Netzes, das die Wahrscheinlichkeiten erzeugt, sehr teuer ist, wäre eine Verfünffachung der Kosten belastend; deshalb wird es bei LLMs normalerweise nicht genutzt. Möglich ist es aber, und die Ergebnisse werden bis zu einem gewissen Grad besser. Auch Monte-Carlo Tree Search wie bei Schach-Engines wäre denkbar.
    • Ein LLM erzeugt bereitwillig beliebige Zeichenketten. Man wollte etwas wie „Alice: 42“, bekommt aber vielleicht etwas wie „Hallo, ich bin ein hilfreiches Modell, und meiner Ansicht nach ist Alice genau forty two, aber ich bin nur ein Sprachmodell“.
      Also gibt man eine Grammatik vor, nach der die Antwort mit einem Großbuchstaben beginnt, danach Kleinbuchstaben, ein Doppelpunkt, ein Leerzeichen und Ziffern folgen und dann Schluss ist. Beim Suchen nach dem ersten Token werden dann nur Tokens berücksichtigt, die mit diesem Muster kompatibel sind, und anschließend weiterhin nur Tokens, die mit dem nächsten Muster kompatibel sind.
      Eine solche Grammatik macht genau das auf flexible und nützliche Weise möglich.
    • Siehe meinen Kommentar hier: https://news.ycombinator.com/item?id=36820884

  • Das ist interessant, deshalb will ich es in das einbauen, woran ich arbeite. Allerdings habe ich aus Sicht der Bitter Lesson das Gefühl, dass dies außer sehr kurzfristig vielleicht nicht der beste Ansatz ist: http://www.incompleteideas.net/IncIdeas/BitterLesson.html

    • Es mag ein Workaround sein, aber ein wichtiger. Es ist nicht klar, ob LLMs in den nächsten Jahren Probleme der eingeschränkten Texterzeugung „natürlich“ lösen werden.
    • Ich bin ganz sicher kein Experte, aber soweit ich weiß, nutzt OpenAI bei einigen GPT-APIs fürs Programmieren so einen Ansatz. Ich habe auch die Vermutung gesehen, dass ein LLM seine Rechenressourcen effektiver für komplexe Aufgaben einsetzen kann, wenn man einfache Grammatikverarbeitung an einen dafür passenden einfachen Prozess auslagert. Ob das stimmt, weiß ich nicht.

  • Es gibt auch ein Projekt, das einen ähnlichen Ansatz nutzt: https://github.com/automorphic-ai/trex
    Playground: https://automorphic.ai/playground

  • Ich hätte gern Empfehlungen für Papers oder Übersichten, die erklären, wie Sampling/Decoding im Zeitalter von End-to-End-Neuronalen Netzen funktioniert. Ich weiß, wie Decoding in der maschinellen Übersetzung und Spracherkennung zu HMM-Zeiten gemacht wurde, also etwa Dinge wie https://en.wikipedia.org/wiki/Viterbi_algorithm oder https://en.wikipedia.org/wiki/Beam_search
    Heutzutage habe ich den Eindruck, dass die Leute einfach „greedy“ vorgehen, aber ich bin mir nicht sicher. Empfehlungen zu Material zu diesem Thema wären hilfreich.

    • Greedy und zugleich zufällig :) Statt Papers würde ich empfehlen, sich die Algorithmen in den meisten LLM-Implementierungen anzusehen. rwkv.cpp hat eine relativ saubere Python-Implementierung: https://github.com/saharNooby/rwkv.cpp/blob/master/rwkv/samp...
    • Wenn man die GPT-4-Dokumentation liest, scheint es keine großen Unterschiede zu den genannten Dingen zu geben
      https://platform.openai.com/docs/api-reference/completions/c...
      Natürlich wissen wir inzwischen, dass GPT-4 eine Mixture-of-Experts-Architektur hat, daher wird die Berechnung intern parallelisiert. Außerdem ist enthalten, wie die Logits durch Presence-/Frequency-Penalty-Terme angepasst werden.