Beam Search

Bei der Auswahl des ersten Antwortfragments kannst du einen Weg zu früh verwerfen, der sich später als besser erwiesen hätte. Alle möglichen Folgen zu prüfen ist jedoch zu teuer. Du brauchst eine begrenzte Menge an Alternativen.

Beam Search behält mehrere der am besten bewerteten Teilantworten. In jedem Schritt erweitert es sie, vergleicht die neuen Folgen und lässt erneut nur eine festgelegte Anzahl übrig. Die Größe dieser Menge heißt Beam Width.

Bei einer Breite von zwei kann das System die Anfänge A und B behalten, statt sofort A zu wählen. Im nächsten Schritt vergleicht es ihre Fortsetzungen. Die grundlegende Bewertung verbindet die Wahrscheinlichkeiten aufeinanderfolgender Tokens — Textstücke —, wobei Implementierungen den Einfluss der Länge korrigieren können.

Eine größere Menge kostet mehr Speicher und Berechnungen und kann trotzdem den besten Weg verwerfen. Eine hohe Wahrscheinlichkeit der gesamten Folge garantiert außerdem weder Wahrheit noch Vielfalt oder Nützlichkeit der Aussage.

Mechanismus und Details

Bei der autoregressiven Sprachmodellierung ist der grundlegende Sequenzscore die Summe der Logarithmen ihrer Tokenwahrscheinlichkeiten:

$$S(x_{1:t})=\sum_{i=1}^{t}\ln p(x_i\mid x_{<i})$$

Dies ist der Logarithmus des Wahrscheinlichkeitsprodukts. Ein größerer Wert ist besser; die Summe vermeidet die Multiplikation sehr kleiner Zahlen. Die Hugging-Face-Dokumentation, „Beam search“ beschreibt das Behalten mehrerer Sequenzen. Bei Breite 1 reduziert sich diese grundlegende Variante auf Greedy Decoding.

Welches Präfix verwirfst du zu früh?

Das eigene Beispiel beginnt mit A = 0,45, B = 0,35 und C = 0,20. Ein Beam mit Breite 2 verwirft C. Die beste Fortsetzung von A hat später die Chance 0,4; AA erreicht daher 0,18. Das übergangene CA hätte aber $0{,}20\cdot0{,}99=0{,}198$ erreicht. Breite 3 behält C und findet das bessere Ergebnis. Dies ist ein vollständiger kleiner Baum mit zwei Tokens, ohne vorzeitiges Ende und ohne Längennormalisierung.

Beam Search bleibt eine Näherung: Ein verworfenes Präfix wird nicht erneut erweitert. Die Breite bezeichnet nicht die Anzahl der aus einer Verteilung gezogenen Tokens wie bei Top-k-Sampling.

Bei unterschiedlich langen Sequenzen zählen Endtoken, Abbruchbedingung und Bewertungsfunktion. Beispielsweise teilt length_penalty in GenerationConfig den logarithmischen Score durch die mit einem festgelegten Exponenten potenzierte Länge. Dieses Kriterium darf nicht mit reiner Wahrscheinlichkeit verwechselt werden. Ein breiterer Beam garantiert auch keinen besseren Inhalt; das Problem besprechen Holtzman et al., §2.2–3.

Ich verwende KI-generierte Inhalte als Teil meines täglichen Lernprozesses.