Autor:  (1) Brandon T. Willard, Normal Computing;  (2) R´emi Louf, Normal Computing.  Linktabelle   Zusammenfassung und Einleitung   LLM-Sampling und geführte Generierung   Iterative FSM-Verarbeitung und Indizierung   Erweiterungen zum iterativen Parsing   Diskussion, Referenzen und Danksagungen  3. Iterative FSM-Verarbeitung und Indizierung   Um genau zu sein, betrachten wir reguläre Ausdrücke in 5-Tupel-Endlicher-Automaten-Form [Sipser, 1996, Definition 1.5]:    (Endlicher Automat).  Definition 1 Ein endlicher Automat oder eine endliche Zustandsmaschine ist gegeben durch (Q, Σ, δ, q0, F), wobei Q eine endliche Menge von Zuständen, Σ ein endliches Alphabet, δ : Q × Σ → Q die Übergangsfunktion, q0 ∈ Q der Startzustand und F ⊆ Q die Menge der Akzeptanzzustände ist.  Die Zeichen, aus denen die Zeichenfolgen in V bestehen, werden aus Σ gezogen: d. h. V ⊂ P(Σ). Die FSM-Zustände Q werden der Einfachheit halber durchgängig durch ganzzahlige Werte dargestellt.      Beispiel 1. Wir veranschaulichen den FSM-Sampling-Prozess in Abbildung 1 für den regulären Ausdruck ([0-9]*)?\.?[0-9]*, der zum Generieren von Gleitkommazahlen verwendet werden kann. Der Einfachheit halber bestehen die Wörter V nur aus den Zeichenfolgen: „A“, „.“ „42“, „.2“ und „1“.   Wenn die Generierung beginnt, befindet sich das FSM im Zustand 0, daher maskiert unser Algorithmus die Zeichenfolge „A“, da diese vom FSM nicht akzeptiert würde. In diesem Fall können wir nur „.“ „42“, „.2“ und „1“ abtasten.     Wenn wir „.2“ abtasten, rücken wir das FSM in den Zustand 3 vor. In diesem Fall sind nur „42“ und „1“ gültige Vervollständigungen, daher maskieren wir die anderen Werte vor der Abtastung. Wenn wir stattdessen „1“ abtasten, rücken wir das FSM in den Zustand 1 vor. In diesem Fall sind „.“ „.42“, „.2“ und „1“ gültige Vervollständigungen und die Maske bleibt unverändert.  Das größte Problem ist immer noch, das Vokabular zu durchlaufen, um die gültigen nächsten Token zu bestimmen. Dazu verarbeiten wir das Vokabular vorab mit dem FSM des regulären Ausdrucks und erstellen einen Index. Wichtig ist, dass wir in Betracht ziehen, in jedem möglichen FSM-Zustand zu beginnen, da die Zeichenfolgen im Vokabular mit beliebigen Teilen eines regulären Ausdrucks übereinstimmen könnten und diese Teile implizit die FSM-Zustände sind.  In Algorithmus 3 wird ein Verfahren zum Erzeugen von Übereinstimmungen beschrieben, das an jedem beliebigen Punkt im FSM beginnt. Das Ergebnis ist eine Liste von Teilsequenzen, die die Zustände detailliert beschreiben, die das FSM durchläuft, wenn es die bereitgestellte Zeichenfolge akzeptiert.   Indem wir die Startzustände dieser Teilsequenzen mit dem letzten FSM-Zustand abgleichen, der in einem einzelnen Schritt der Schleife in Algorithmus 2 erreicht wurde, können wir das Vokabular effizient mit einer Abbildung indizieren, σ : Q → P(V), die FSM-Zustände und Mengen von Elementen des Vokabulars verbindet, die vom FSM in diesen Zuständen akzeptiert werden.  Algorithmus 4 beschreibt die Konstruktion von σ.  Die Verwendung einer Hash-Map für σ kann dazu führen, dass der m-te Schritt in Algorithmus 2 im Durchschnitt nur O(1) kostet. Da σ außerdem außerhalb des Token-Sampling-Verfahrens erstellt wird, sind seine Laufzeitkosten praktisch irrelevant, obwohl es theoretisch Speicher benötigt, der der Anzahl der Zustände im FSM entspricht (d. h. |Q|). Glücklicherweise wird bei nicht-pathologischen Kombinationen von regulären Ausdrücken und Vokabularen nicht jede Zeichenfolge im Vokabular vom FSM akzeptiert und nicht jeder FSM-Zustand wird durch eine Zeichenfolge in V dargestellt.   3.1 Beispiele  In diesem Abschnitt verwenden wir GPT2-medium (355M Parameter), um zu veranschaulichen, wie die Generierung mithilfe regulärer Ausdrücke in der Praxis funktioniert. Wir verwenden die Bibliothek Outlines, um sie zu generieren:   Listing 3.1 – Fortsetzung   Listing 3.3 – Fortsetzung   3.2 Vergleich mit aktuellen Methoden  Um die Effizienz des hier beschriebenen und in Outlines implementierten Indexierungsansatzes zu veranschaulichen, führen wir einen einfachen Vergleich mit der Guidance-Bibliothek durch. Zum Zeitpunkt des Schreibens dieses Artikels verwendet die Guidance-Bibliothek partielles Matching mit regulären Ausdrücken – jedes Mal vom Beginn der abgetasteten Sequenz an angewendet – und muss bei jedem Schritt das Vokabular des LLM (N = 50, 257) durchlaufen.  Der für diesen Vergleich verwendete Leitcode und die Eingabeaufforderung lauten wie folgt:   Listing 3.4 – Fortsetzung   Der entsprechende Outlines-Code lautet wie folgt:   Listing 3.5 – Fortsetzung   Der Wert von max_tokens wird variiert und die Zeitangaben werden mit timeit für eine einzelne Schleife und einen einzelnen Wiederholungswert aufgezeichnet (d. h. für jeden Wert von max_tokens wird nur eine Probe erfasst). Die Ergebnisse werden in Abschnitt 3.2 dargestellt.  Sofern keine Konfigurationsfehler vorliegen, die zu großen Laufzeitunterschieden führen könnten, ist die beobachtete Skalierung der maximalen Anzahl abgetasteter Token bemerkenswert und weist auf das wachsende Rechenproblem hin, das dieser Ansatz mit sich bringt.   Dieses Dokument ist   . auf Arxiv unter der CC 4.0-Lizenz verfügbar

Part of HackerNoon's growing list of open-source research papers, promoting free access to academic material.

AI Models on HackerNoon

Dieses Audio ist in der Originalsprache der Geschichte produziert!

Zu lang; Lesen

Make resilience your competitive advantage

Effiziente geführte Generierung für große Sprachmodelle: Iterative FSM-Verarbeitung und Indizierung

About Author

KOMMENTARE

Hängeetiketten

DIESER ARTIKEL WURDE VORGESTELLT IN

Related Stories

HackerNoon Decoded: The Top 10 Countries Where HackerNoon Is the Most Active

HackerNoon Decoded 2024: Celebrating Our AI Community!

HackerNoon Decoded 2024: Wir feiern unsere Remote-Work-Community!

HackerNoon Decoded 2024: Celebrating Our Startups Community!

HackerNoon Decoded: The Top 10 Countries Where HackerNoon Is the Most Active

HackerNoon Decoded 2024: Celebrating Our AI Community!

HackerNoon Decoded 2024: Wir feiern unsere Remote-Work-Community!

HackerNoon Decoded 2024: Celebrating Our Startups Community!

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps