Viterbi, beam search и LLM-reranking: как алгоритм выбирает один смысл из многих

Un auteur sur Habr construit en 2026 une chaîne allant des algorithmes classiques de NLP au LLM-reranking à travers un principe unique : non pas le meilleur pas à chaque coup, mais le meilleur chemin à travers toute la séquence — et il explique cela à l'aide de l'exemple de l'interprétation des cartes de Tarot.

Pourquoi le greedy donne un résultat incorrect

L'algorithme greedy sélectionne l'option la plus probable à chaque étape, isolément du contexte suivant. Dans les tâches de NLP — étiquetage des parties du discours (POS tagging), reconnaissance des entités nommées (NER) — cela conduit à des erreurs systématiques : la meilleure étiquette locale peut détruire la cohérence de toute la séquence.

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

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

Ce que beam search et CRF apportent

Le beam search occupe une position intermédiaire : il conserve k meilleures hypothèses au lieu d'une seule. Pour k = 1, il coïncide avec le greedy ; pour k = ∞, il équivaut à une recherche exhaustive. Des valeurs de 4 à 10 assuraient un équilibre raisonnable dans les systèmes classiques de MT, y compris Google Translate avant la transition vers les transformers.

Le CRF (Champs Aléatoires Conditionnels) ajoute 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. D'après les résultats du benchmark CoNLL-2003, BiLSTM-CRF surpassait BiLSTM sans CRF de 1 à 2 points de pourcentage F1 — un gain stable qui a assuré au CRF un rôle standard dans les pipelines NER avant l'avènement de BERT.

« À l'aide d'un contre-exemple, je montre pourquoi le meilleur choix

local perd face au global — et aussi où s'arrête la recherche de structure et où commence la génération de texte », formule l'auteur de l'article sur Habr l'idée clé.

Où les LLMs s'intègrent dans cette chaîne

Les transformers n'utilisent pas Viterbi directement : le texte est généré de manière autorégressive, jeton par jeton ; la méthode standard de décodage est le beam search ou l'échantillonnage (nucleus, temperature). Le LLM reranking comble l'écart au niveau suivant : le modèle génère 10 à 20 candidats de réponse, puis un LLM séparé (ou le même, avec un prompt différent) les classe selon des critères de qualité — cohérence, précision factuelle, conformité à l'instruction.

Comme le souligne l'auteur, c'est précisément ici que se situe la frontière entre la recherche de structure et la génération de texte — et comprendre cette frontière explique pourquoi le reranking dans les pipelines LLM de production offre toujours une amélioration de qualité mesurable sur les métriques automatiques.

Ce que cela signifie

La chaîne greedy → Viterbi → beam search → CRF → LLM reranking est l'évolution d'un seul principe : la recherche du meilleur chemin global à travers l'espace des significations possibles. Comprendre cette hiérarchie aide à choisir la méthode de décodage adaptée à une tâche NLP spécifique et explique les décisions architecturales des modèles de langage modernes.

Questions fréquentes

En quoi l'algorithme 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 avec recherche exhaustive. Le beam search ne conserve que k meilleures hypothèses à chaque étape : il est plus rapide, mais ne garantit pas l'optimalité.

Viterbi est-il utilisé dans les LLMs modernes ?

Viterbi n'est pas utilisé directement dans les transformers : la génération autorégressive nécessite beam search ou échantillonnage. Viterbi reste pertinent dans les couches CRF au-dessus des encodeurs — par exemple, dans les tâches de NER et de POS tagging basées sur des architectures de type BERT.