Viterbi, beam search et reranking par LLM : comment un algorithme choisit un seul sens parmi plusieurs

Sur Habr, un auteur relie en 2026 les algorithmes classiques du NLP au reranking par LLM à partir d'un seul principe : ce qui compte n'est pas le meilleur pas à chaque étape, mais le meilleur chemin à travers toute la séquence. Il l'illustre avec l'interprétation des cartes de tarot.

Pourquoi l'algorithme glouton (greedy) donne un mauvais résultat

L'algorithme greedy retient à chaque étape la variante la plus probable, sans tenir compte du contexte qui suit. Dans les tâches de NLP comme l'étiquetage morphosyntaxique (POS tagging) ou la reconnaissance d'entités nommées (NER), cela produit des erreurs systématiques : une étiquette localement optimale peut briser la cohérence de toute la séquence.

L'algorithme de Viterbi résout le problème par programmation dynamique : il examine simultanément tous les chemins à travers les états cachés et trouve l'optimum global. Sa complexité de calcul est de O(N × T²), contre O(N × T) pour greedy, où N est la longueur de la séquence et T le nombre d'états. C'est plus coûteux, mais l'optimalité est garantie.

• Greedy : O(N × T), rapide, sans garantie d'optimum global
• Viterbi : O(N × T²), optimum global exact selon le modèle
• Beam search : conserve les k meilleures hypothèses, un compromis entre précision et vitesse (k typiques : 4–10)
• CRF (Conditional Random Fields) : paramètres de transition apprenables au-dessus d'un décodeur Viterbi
• Reranking par LLM : un modèle de langage classe l'ensemble final de candidats

Ce qu'apportent le beam search et les CRF

Le beam search occupe une position intermédiaire : il conserve k hypothèses au lieu d'une seule. Avec k = 1, il équivaut à greedy ; avec k = ∞, à l'énumération exhaustive. Des valeurs de 4 à 10 offraient un équilibre raisonnable dans les systèmes de traduction automatique classiques, notamment Google Translate avant son passage aux transformers.

Les CRF (champs aléatoires conditionnels) ajoutent des paramètres de transition apprenables : au lieu de probabilités fixes, le modèle apprend à partir des données quelles séquences d'étiquettes sont plausibles. Sur le benchmark CoNLL-2003, BiLSTM-CRF dépassait BiLSTM sans CRF de 1 à 2 points de pourcentage de F1. Ce gain stable a fait des CRF un composant standard des pipelines NER jusqu'à l'arrivée de BERT.

«

Sur un contre-exemple, je montre pourquoi le meilleur choix local perd face au choix global — et où s'arrête la recherche de structure pour laisser place à la génération de texte », résume l'idée centrale l'auteur de l'article sur Habr.

Où les LLM s'insèrent dans cette chaîne

Les transformers n'utilisent pas Viterbi directement : le texte est généré de façon autorégressive, token par token, et la méthode de décodage standard est le beam search ou l'échantillonnage (nucleus, temperature). Le reranking par LLM comble l'écart au niveau suivant : le modèle génère 10 à 20 variantes de réponse, puis un LLM distinct (ou le même, avec un autre prompt) les classe selon des critères de qualité : cohérence, exactitude factuelle, respect de la consigne.

Comme le souligne l'auteur, c'est là que passe la frontière entre recherche de structure et génération de texte. Comprendre cette frontière explique pourquoi le reranking, dans les pipelines LLM en production, apporte encore un gain de qualité mesurable sur les métriques automatiques.

Ce que cela signifie

La chaîne greedy → Viterbi → beam search → CRF → reranking par LLM décline un même principe : chercher le meilleur chemin global dans l'espace des sens possibles. Comprendre cette hiérarchie aide à choisir la méthode de décodage adaptée à une tâche de NLP donnée et éclaire les choix d'architecture des modèles de langage actuels.

Questions fréquentes

En quoi l'algorithme de

Viterbi diffère-t-il du beam search ?

Viterbi garantit de trouver le chemin globalement optimal à travers tous les états : c'est un algorithme exact, qui prend en compte l'ensemble des chemins. Le beam search ne conserve que les k meilleures hypothèses à chaque étape : il est plus rapide, mais n'offre aucune garantie d'optimalité.

Viterbi est-il utilisé dans les LLM modernes ?

Dans les transformers, Viterbi n'est pas appliqué directement : la génération autorégressive passe par le beam search ou l'échantillonnage. Viterbi reste pertinent dans les couches CRF placées au-dessus d'encodeurs, par exemple pour le NER et le POS tagging avec des architectures de type BERT.