Accueil › Glossaire › Beam Search

Beam Search : explorer plusieurs chemins pour trouver la meilleure séquence

Le beam search est un algorithme de décodage heuristique qui, à chaque étape de génération d’une séquence, maintient les k meilleures hypothèses en parallèle (k = beam width) au lieu de ne conserver que la plus probable. C’est le compromis standard entre le greedy decoding (rapide mais sous-optimal) et la recherche exhaustive (optimale mais impraticable), utilisé en traduction automatique, transcription vocale et génération de texte.

Le problème : trouver la meilleure séquence

Quand un modèle Seq2Seq ou un LLM génère du texte, il produit à chaque pas de temps une distribution de probabilités sur tout le vocabulaire. La séquence « idéale » est celle qui maximise la probabilité jointe de tous les tokens :

Séquence optimale = argmax P(y₁, y₂, ..., y_T | x)
                  = argmax ∏ P(y_t | y₁, ..., y_{t-1}, x)

Le problème : explorer toutes les combinaisons possibles est impossible. Pour un vocabulaire de 50 000 tokens et une séquence de 20 tokens, il y a 50 000²⁰ séquences candidates, un nombre astronomique. Il faut donc une stratégie de recherche intelligente.

Greedy search vs beam search

Le greedy search : rapide mais myope

Le greedy decoding sélectionne le token le plus probable à chaque étape, sans considérer l’impact sur les étapes futures. C’est rapide (un seul chemin à suivre) mais il peut rater la meilleure séquence globale en faisant des choix localement gourmands.

Exemple avec vocabulaire {A, B, C, <EOS>} :

Étape 1 : P(A)=0.5, P(B)=0.4, P(C)=0.1
Greedy → choisit A (0.5)

Étape 2 | A : P(B)=0.3, P(C)=0.6, P(<EOS>)=0.1
Greedy → choisit C (0.6)

Séquence greedy : A-C, probabilité = 0.5 × 0.6 = 0.30

Mais si on avait choisi B à l'étape 1 :
Étape 2 | B : P(A)=0.9, P(C)=0.05, P(<EOS>)=0.05
Séquence B-A, probabilité = 0.4 × 0.9 = 0.36

→ B-A (0.36) est meilleur que A-C (0.30), mais greedy l'a raté !

Le beam search : explorer k chemins en parallèle

Le beam search résout ce problème en maintenant les k meilleures hypothèses à chaque étape. Pour k=2 dans l’exemple ci-dessus, le beam search conserverait A (0.5) et B (0.4) à l’étape 1, les étendrait toutes les deux à l’étape 2, et trouverait correctement que B-A (0.36) est meilleur que A-C (0.30).

Le processus détaillé :

Étape 1 : on génère les probabilités de tous les tokens du vocabulaire. On conserve les k tokens les plus probables. Ce sont les k « faisceaux » (beams) initiaux.

Étape 2 : pour chacun des k faisceaux, on génère les probabilités du token suivant. On obtient k × |V| hypothèses. On ne conserve que les k meilleures (en score cumulé).

Étapes suivantes : on répète le processus. À chaque étape, on étend les k faisceaux, on évalue les k × |V| extensions, et on ne garde que les k meilleures.

Terminaison : quand un faisceau génère le token <EOS>, il est mis de côté comme séquence « terminée ». La recherche continue pour les faisceaux restants. À la fin, on retourne la meilleure séquence terminée.

Scoring et normalisation par longueur

Le beam search utilise des log-probabilités (au lieu de probabilités brutes) pour éviter les problèmes numériques de sous-dépassement :

Score(y₁, ..., y_T) = Σ log P(y_t | y₁, ..., y_{t-1}, x)

Les log-probabilités sont toujours négatives, donc le score cumulé diminue avec la longueur de la séquence. Conséquence : le beam search a un biais vers les séquences courtes (moins de termes négatifs = score plus élevé).

La solution standard est la normalisation par longueur (length penalty) :

Score normalisé = (1 / T^α) × Σ log P(y_t | ...)

Où :
- T = longueur de la séquence
- α = facteur de pénalité (typiquement 0.6 à 1.0)
- α = 0 → pas de normalisation
- α = 1 → division par la longueur exacte

Google Neural Machine Translation (GNMT) utilise α = 0.6, un bon point de départ empirique. Sans cette normalisation, les traductions sont souvent tronquées.

Choisir la taille du beam

Au-delà de k=10, les gains de qualité sont généralement marginaux tandis que le temps de décodage augmente linéairement. Un phénomène contre-intuitif a été observé : avec des beams très larges (k>100), la qualité peut se dégrader. Cela s’explique par le fait que les séquences à haute probabilité selon le modèle ne sont pas toujours les plus naturelles pour un humain (le modèle est imparfait).

Variantes du beam search

Diverse beam search

Le beam search classique a tendance à produire des hypothèses très similaires entre elles (les k faisceaux convergent vers des variantes proches). Le diverse beam search introduit une pénalité de similarité entre les faisceaux, forçant l’algorithme à explorer des chemins plus variés. Utile quand vous voulez proposer plusieurs traductions alternatives ou générer des réponses diversifiées.

Constrained beam search

Permet d’imposer des contraintes sur la séquence de sortie : certains mots doivent obligatoirement apparaître dans le résultat final. Hugging Face Transformers supporte cette variante via le paramètre force_words_ids dans model.generate(). Cas d’usage : forcer l’utilisation de termes techniques précis en traduction, ou garantir que certaines entités nommées apparaissent dans un résumé.

Early stopping

Quand les k faisceaux les plus probables ont tous généré <EOS>, la recherche s’arrête. Certaines implémentations s’arrêtent dès qu’un seul faisceau est terminé si son score dépasse le meilleur score possible des faisceaux restants.

Beam search vs sampling : quand utiliser quoi ?

Le beam search et le sampling (avec température, top-k, nucleus sampling) servent des objectifs différents :

Implémentation avec Hugging Face

from transformers import AutoModelForSeq2SeqLM, AutoTokenizer

model = AutoModelForSeq2SeqLM.from_pretrained("Helsinki-NLP/opus-mt-fr-en")
tokenizer = AutoTokenizer.from_pretrained("Helsinki-NLP/opus-mt-fr-en")

text = "Le chat noir dort paisiblement sur le tapis rouge."
inputs = tokenizer(text, return_tensors="pt")

# Greedy decoding (k=1)
greedy = model.generate(**inputs, max_length=50)
print("Greedy:", tokenizer.decode(greedy[0], skip_special_tokens=True))

# Beam search (k=5) avec length penalty
beam = model.generate(
    **inputs,
    max_length=50,
    num_beams=5,              # beam width
    length_penalty=0.6,       # normalisation par longueur
    no_repeat_ngram_size=3,   # évite les répétitions de trigrammes
    early_stopping=True       # arrêt quand tous les beams sont terminés
)
print("Beam:", tokenizer.decode(beam[0], skip_special_tokens=True))

# Beam search avec plusieurs sorties
beams_multi = model.generate(
    **inputs,
    max_length=50,
    num_beams=5,
    num_return_sequences=3,   # retourne les 3 meilleures hypothèses
    length_penalty=0.6
)
for i, b in enumerate(beams_multi):
    print(f"Hyp {i+1}:", tokenizer.decode(b, skip_special_tokens=True))

Le paramètre no_repeat_ngram_size est crucial en pratique : sans lui, le beam search a tendance à produire des séquences répétitives (le modèle se « bloque » dans une boucle de tokens à haute probabilité). Fixer cette valeur à 2 ou 3 élimine la plupart des répétitions.

Limites du beam search

Biais vers les séquences courtes : résolu par la normalisation par longueur, mais le paramètre α nécessite un réglage empirique.

Répétitions : le beam search peut générer des boucles répétitives. La pénalité de n-grammes est une correction efficace mais ad hoc.

Pas de diversité : les k faisceaux convergent souvent vers des variantes presque identiques. Le diverse beam search atténue ce problème.

Coût linéaire en k : chaque faisceau nécessite un passage forward séparé dans le decoder. Avec k=10, le décodage est 10× plus lent qu’en greedy.

Texte « ennuyeux » : en maximisant la probabilité, le beam search favorise les formulations les plus courantes et prévisibles. Pour la génération ouverte, c’est un défaut majeur qui explique pourquoi les LLM préfèrent le sampling.

Applications concrètes du beam search

Traduction automatique neuronale : c’est l’application historique et le cas d’usage où le beam search excelle le plus. Google Translate, DeepL, et les modèles NLLB (Meta) utilisent tous le beam search pour le décodage final. Un beam width de 4-5 avec normalisation par longueur est le standard industriel.

Reconnaissance vocale (ASR) : Whisper (OpenAI) utilise le beam search pour décoder les transcriptions à partir des sorties de son encoder audio. Dans ce contexte, le beam search peut être combiné avec un modèle de langue externe (language model fusion) pour améliorer la cohérence linguistique de la transcription.

Résumé de texte : les modèles comme BART et Pegasus utilisent le beam search pour générer des résumés extractifs ou abstractifs. La normalisation par longueur est particulièrement importante ici pour éviter des résumés trop courts.

Génération de légendes d’images : les modèles image-to-text utilisent le beam search pour décoder des descriptions cohérentes à partir des features visuelles extraites par le CNN ou le Vision Transformer.

Complétion de code : certains assistants de code utilisent le beam search pour proposer plusieurs suggestions de complétion, en particulier pour les complétions multi-lignes où la cohérence syntaxique est critique.

Optimisations pratiques

Batching des faisceaux : les k faisceaux peuvent être traités comme un batch sur le GPU, exploitant le parallélisme matériel. Le coût réel est donc inférieur à k× le greedy, car les opérations matricielles s’effectuent en parallèle.

Cache KV : dans les Transformers, chaque faisceau maintient son propre cache clé-valeur. Avec k=5 et une séquence longue, la mémoire GPU requise pour le cache est 5× celle du greedy. C’est souvent le facteur limitant en pratique, bien plus que le temps de calcul.

Pruning adaptatif : au lieu d’un beam width fixe, certaines implémentations utilisent un seuil de score relatif. Les faisceaux dont le score est trop éloigné du meilleur sont éliminés, ce qui peut accélérer le décodage de 40 % sans perte de qualité mesurable.

Reranking : une technique avancée consiste à générer n hypothèses avec le beam search, puis à les réordonner avec un modèle séparé (par exemple un modèle bidirectionnel comme BERT) qui évalue la qualité globale de chaque hypothèse. Cette approche de « generate then rerank » est utilisée dans plusieurs systèmes de traduction de pointe.

Le beam search dans le paysage actuel du décodage

L’arrivée des LLM génératifs a repositionné le beam search dans l’écosystème des stratégies de décodage. Voici comment les principaux modèles et applications abordent le décodage :

Modèles de traduction (NLLB, mBART, opus-mt) : beam search avec k=4-5, normalisation par longueur, pénalité de n-grammes. C’est le standard incontesté.

Transcription vocale (Whisper) : beam search avec k=5 par défaut. Possibilité de combiner avec un language model pour les langues à faibles ressources.

LLM conversationnels (GPT, Claude, LLaMA) : sampling (temperature + top-p) par défaut. Le beam search n’est quasiment jamais utilisé car il produit du texte trop prévisible pour le dialogue.

Génération de code : mélange selon le cas. Les complétions courtes (une ligne) utilisent souvent le greedy. Les générations plus longues (fonctions, classes) peuvent bénéficier d’un beam search léger (k=2-3) pour la cohérence syntaxique, ou d’un sampling avec température basse (0.2-0.4).

Le beam search n’est donc pas un algorithme en déclin : il reste optimal pour les tâches de transduction structurée. Son territoire s’est simplement rétréci face aux stratégies de sampling qui dominent la génération ouverte.