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

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]:

Definition 1 (Endlicher Automat). 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.