Beam Search

Einfach erklärt

Beam Search ist ein Decoding-Algorithmus, der mehrere mögliche Fortsetzungen parallel verfolgt. Statt bei jedem Schritt nur das wahrscheinlichste Token zu wählen (Greedy), behält er die k besten Kandidaten.

Warum ist das besser als Greedy?

Greedy: "Der" → "beste" (0.4) → "Weg" (0.3) → ...
        Gesamtwahrscheinlichkeit: 0.4 × 0.3 = 0.12

Beam Search (k=2):
Kandidat 1: "Der" → "beste" (0.4) → "Weg" (0.3) = 0.12
Kandidat 2: "Der" → "schnellste" (0.35) → "Pfad" (0.5) = 0.175 ✓

-> Beam Search findet die bessere Gesamtsequenz

Der Trade-off:

Beam Search ist rechenintensiver (k-mal mehr Berechnungen), findet aber oft bessere Sequenzen.

Technischer Deep Dive

Algorithmus

def beam_search(model, prompt, beam_width=5, max_length=50):
    # Starte mit einem Kandidaten
    beams = [(prompt, 0.0)]  # (Sequenz, Log-Wahrscheinlichkeit)
    
    for _ in range(max_length):
        all_candidates = []
        
        for seq, score in beams:
            # Nächste Token-Wahrscheinlichkeiten
            probs = model.get_next_token_probs(seq)
            
            # Top-k Erweiterungen
            for token, prob in top_k(probs, beam_width):
                new_seq = seq + token
                new_score = score + log(prob)
                all_candidates.append((new_seq, new_score))
        
        # Behalte nur die besten k Kandidaten
        beams = sorted(all_candidates, key=lambda x: x[1], reverse=True)[:beam_width]
    
    return beams[0][0]  # Beste Sequenz

Vergleich Decoding-Strategien

Strategie	Deterministisch	Qualität	Diversität	Geschwindigkeit
Greedy	✅	Niedrig	Keine	Schnell
Beam Search	✅	Hoch	Keine	Mittel
Sampling	❌	Variabel	Hoch	Schnell
Top-p/Top-k	❌	Gut	Mittel	Schnell

Probleme von Beam Search

• Repetition: Neigt zu sich wiederholenden Phrasen
• Generische Ausgaben: “Sichere” aber langweilige Texte
• Length Bias: Bevorzugt kürzere Sequenzen (höhere Gesamtwahrscheinlichkeit)

Lösungen: Length Normalization, Repetition Penalty, Diverse Beam Search