Accueil › Glossaire › Greedy Decoding

Greedy Decoding : le décodage le plus simple (et ses pièges)

Le greedy decoding (décodage glouton) est la stratégie de décodage la plus simple en génération de texte : à chaque étape, le modèle sélectionne le token ayant la probabilité la plus élevée, sans considérer l’impact de ce choix sur les tokens futurs. C’est rapide, déterministe, et souvent la première approche testée, mais sa myopie le rend inadapté à la plupart des tâches de génération en production.

Comment fonctionne le greedy decoding ?

Le processus est d’une simplicité désarmante. À chaque pas de temps, un LLM ou un modèle Seq2Seq produit un vecteur de logits de taille |V| (la taille du vocabulaire, typiquement 32 000 à 128 000 tokens). Ce vecteur est passé dans une fonction softmax pour obtenir une distribution de probabilités. Le greedy decoding prend simplement l’argmax de cette distribution.

Étape par étape :

1. Le modèle reçoit le contexte : "Le chat est"
2. Il produit les probabilités pour le token suivant :
   P("assis") = 0.25
   P("noir") = 0.20
   P("un") = 0.15
   P("parti") = 0.12
   ... (50 000 autres tokens avec des probabilités plus faibles)

3. Greedy → sélectionne "assis" (0.25, le max)

4. Nouveau contexte : "Le chat est assis"
5. Le modèle produit les probabilités :
   P("sur") = 0.45
   P(".") = 0.20
   P(",") = 0.15
   ...

6. Greedy → sélectionne "sur" (0.45)

7. Continue jusqu'à <EOS> ou longueur max

Le choix est local : à chaque étape, le greedy decoding ne se demande jamais si un token moins probable maintenant pourrait mener à une meilleure séquence globale. C’est exactement le problème classique de l’optimisation gloutonne en algorithmique.

Pourquoi le greedy decoding est sous-optimal

Piégé par les optima locaux

Le greedy decoding maximise la probabilité à chaque étape, mais pas la probabilité de la séquence complète. L’exemple classique :

Vocabulaire : {A, B, C, <EOS>}

Avec le contexte donné :
P(A | contexte) = 0.50     P(B | contexte) = 0.40

Si on choisit A :
  P(C | A) = 0.60 → séquence A-C, prob = 0.50 × 0.60 = 0.30

Si on avait choisi B :
  P(A | B) = 0.90 → séquence B-A, prob = 0.40 × 0.90 = 0.36

Greedy choisit A puis C (prob totale 0.30)
Mais B-A est meilleur (prob totale 0.36)

Le greedy a fait le « meilleur » choix local (A à 0.50 > B à 0.40), mais le résultat global est inférieur. Le beam search résout ce problème en explorant plusieurs chemins simultanément.

Le problème des répétitions

Le défaut le plus visible du greedy decoding en pratique est la génération de texte répétitif. Le modèle se « bloque » dans des boucles :

Entrée : "I enjoy walking with my cute dog"

Greedy output (GPT-2) :
"I enjoy walking with my cute dog, but I'm not sure if I'll
ever be able to walk with my dog. I'm not sure if I'll ever
be able to walk with my dog. I'm not sure if I'll ever..."

Ce phénomène, appelé « neural text degeneration », se produit parce qu’une séquence déjà générée crée un contexte où la même séquence reste la plus probable. Le greedy, sans aucun mécanisme de diversité, reproduit la boucle indéfiniment.

Manque de diversité et de naturel

Le texte généré par greedy decoding est déterministe : la même entrée produit toujours la même sortie. En génération ouverte (conversation, écriture créative), cela donne un texte « plat », prévisible, qui manque de la variabilité naturelle du langage humain. Le greedy favorise systématiquement les formulations les plus communes, éliminant les choix de mots originaux ou les tournures inattendues.

Quand le greedy decoding est-il approprié ?

Malgré ses limites, le greedy decoding n’est pas inutile. Il reste le bon choix dans plusieurs scénarios :

Prototypage rapide : quand vous testez un modèle ou un pipeline, le greedy est le moyen le plus rapide d’obtenir une sortie et de vérifier que tout fonctionne.

Tâches à faible ambiguïté : pour des tâches où la « bonne » réponse est quasi déterministe (extraction d’entités, classification par génération, réponses factuelles courtes), le token le plus probable est souvent le bon.

Streaming temps réel : quand la latence est critique (chatbot en temps réel, sous-titrage en direct), le greedy est le plus rapide car il ne nécessite qu’un seul passage forward par token.

Baseline de comparaison : le greedy sert de référence pour évaluer l’apport des stratégies plus sophistiquées. Si le beam search ou le sampling n’améliorent pas les résultats par rapport au greedy, c’est un signal que le problème est dans le modèle, pas dans le décodage.

Température très basse : en pratique, configurer une température proche de 0 dans un LLM revient à faire du greedy decoding. La distribution de probabilités devient tellement « piquée » autour du maximum que le sampling sélectionne presque toujours le même token que le greedy.

Le greedy dans le spectre des stratégies de décodage

Le greedy decoding se situe à l’extrémité « déterministe et efficace » du spectre, avec les autres stratégies offrant différents compromis :

Implémentation

Le greedy decoding est trivial à implémenter. Voici la version minimale et la version Hugging Face :

import torch

# Version manuelle (pseudo-code PyTorch)
def greedy_decode(model, input_ids, max_length=50):
    generated = input_ids.clone()
    for _ in range(max_length):
        with torch.no_grad():
            logits = model(generated).logits[:, -1, :]  # dernière position
        next_token = logits.argmax(dim=-1, keepdim=True)  # argmax = greedy
        generated = torch.cat([generated, next_token], dim=-1)
        if next_token.item() == eos_token_id:
            break
    return generated

from transformers import AutoModelForCausalLM, AutoTokenizer

model = AutoModelForCausalLM.from_pretrained("gpt2")
tokenizer = AutoTokenizer.from_pretrained("gpt2")

inputs = tokenizer("Le futur de l'IA est", return_tensors="pt")

# Greedy decoding (c'est le comportement par défaut)
output = model.generate(
    **inputs,
    max_new_tokens=50,
    do_sample=False  # False = greedy (pas de sampling)
)
print(tokenizer.decode(output[0], skip_special_tokens=True))

Notez que do_sample=False est le paramètre par défaut dans Hugging Face Transformers. Si vous ne spécifiez rien, le modèle utilise le greedy decoding. Pour activer le beam search, ajoutez num_beams=5. Pour le sampling, ajoutez do_sample=True avec temperature, top_k ou top_p.

Greedy decoding et speculative decoding

Le greedy decoding joue un rôle particulier dans le speculative decoding, une technique d’accélération de l’inférence des LLM. Le principe : un petit modèle « brouillon » (draft model) génère rapidement plusieurs tokens en greedy, puis le grand modèle vérifie ces tokens en un seul passage forward parallèle. Les tokens corrects sont acceptés, les incorrects sont rejetés et regénérés.

Cette technique fonctionne particulièrement bien avec le greedy decoding car la vérification est déterministe : soit le grand modèle aurait choisi le même token (accepté), soit non (rejeté). Avec le sampling, la vérification est plus complexe (il faut comparer des distributions, pas des tokens uniques). Le speculative decoding peut accélérer l’inférence de 2 à 3× sans aucun changement dans la qualité de sortie.

Greedy decoding et Chain-of-Thought

Une découverte intéressante de la recherche récente (Wang et Zhou, 2024) : en examinant les chemins alternatifs du greedy decoding (les tokens qui auraient été choisis à la place du top-1), on peut découvrir des raisonnements de type Chain-of-Thought (CoT) enfouis dans le modèle. Certains chemins alternatifs du greedy produisent des étapes de raisonnement que le chemin principal n’a pas explorées. Ce « CoT decoding » montre que les LLM possèdent des capacités de raisonnement qui ne sont pas toujours révélées par le greedy standard.

Formalisation mathématique

Pour un modèle autoregressif qui génère une séquence y = (y₁, y₂, …, y_T) conditionnellement à une entrée x, la probabilité de la séquence est :

P(y | x) = ∏ P(y_t | y₁, ..., y_{t-1}, x)

En log-probabilité :
log P(y | x) = Σ log P(y_t | y₁, ..., y_{t-1}, x)

Le décodage optimal trouverait :

y* = argmax_y P(y | x)

Le greedy decoding approxime cela par :

y_t^greedy = argmax_{y_t} P(y_t | y₁^greedy, ..., y_{t-1}^greedy, x)

La différence fondamentale : le décodage optimal maximise la probabilité jointe de toute la séquence, tandis que le greedy maximise la probabilité conditionnelle de chaque token individuellement. Ces deux objectifs ne coïncident pas en général. Le greedy ne garantit d’être optimal que si la probabilité du meilleur token à chaque étape est supérieure à la somme de toutes les probabilités des tokens alternatifs combinées avec leurs meilleures suites, ce qui est rarement le cas en pratique.

Le greedy decoding selon les tâches

L’impact du greedy decoding varie considérablement selon la nature de la tâche :

Traduction automatique : le greedy est nettement inférieur au beam search. Perte typique de 1 à 3 points BLEU par rapport à un beam search k=5. Les erreurs d’alignement (un mot traduit trop tôt ou trop tard) sont fréquentes car le greedy ne peut pas anticiper la structure de la phrase cible.

Résumé de texte : le greedy produit des résumés acceptables pour les modèles bien entraînés, mais le beam search améliore la cohérence globale. La perte ROUGE est de 0.5 à 2 points typiquement.

Complétion de code : le greedy fonctionne bien pour les complétions courtes (une ligne) où le contexte est fortement contraint (syntaxe, types). Pour les générations plus longues (fonctions, classes), il produit plus d’erreurs logiques.

Classification par génération : quand un LLM répond « oui » ou « non » à une question, le greedy est parfait. La réponse est quasi-déterministe et le premier token suffit.

Conversation ouverte : le greedy est le pire choix. Texte répétitif, monotone, prévisible. Le sampling avec température 0.7 et top-p 0.9 est massivement supérieur pour la fluidité et le naturel.

Améliorer le greedy sans changer de stratégie

Si vous êtes contraint d’utiliser le greedy (par exemple pour des raisons de latence ou de reproductibilité), plusieurs techniques l’améliorent sans changer fondamentalement l’algorithme :

Repetition penalty : un facteur multiplicatif appliqué aux logits des tokens déjà générés. Une valeur de 1.2 réduit significativement les boucles tout en gardant le décodage déterministe.

No-repeat n-gram : interdire la réapparition d’un trigramme ou quadrigramme déjà produit. Supprime complètement les boucles mais peut occasionnellement forcer des formulations maladroites.

Length penalty : ajuster le score en fonction de la longueur pour éviter que le greedy ne s’arrête trop tôt (biais vers les séquences courtes).

Prompt engineering : un prompt bien structuré contraint suffisamment l’espace de sortie pour que le greedy produise de bons résultats. Les formats structurés (JSON, listes, tableaux) guident le modèle vers des sorties cohérentes même en greedy. C’est d’ailleurs pourquoi les appels d’API structurés (function calling, tool use) fonctionnent très bien avec le greedy : la structure de la sortie est suffisamment contrainte pour que le token le plus probable soit presque toujours le bon.