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

Un autor en Habr construye en 2026 una cadena que va desde los algoritmos clásicos de NLP hasta el LLM-reranking a través de un único principio: no el mejor paso en cada jugada, sino el mejor camino a lo largo de toda la secuencia — y lo explica mediante el ejemplo de la interpretación de cartas del Tarot.

Por qué el greedy da un resultado incorrecto

El algoritmo greedy selecciona la opción más probable en cada paso, aislado del contexto posterior. En tareas de NLP — etiquetado de clases gramaticales (POS tagging), reconocimiento de entidades nombradas (NER) — esto conduce a errores sistemáticos: la mejor etiqueta local puede destruir la coherencia de toda la secuencia.

El algoritmo Viterbi resuelve el problema mediante programación dinámica: considera todos los caminos por los estados ocultos simultáneamente y encuentra el óptimo global. La complejidad computacional es O(N × T²) frente a O(N × T) del greedy, donde N es la longitud de la secuencia y T es el número de estados; esto es más costoso, pero garantiza la optimalidad.

• Greedy: O(N × T), rápido, sin garantía de óptimo global
• Viterbi: O(N × T²), óptimo global exacto según el modelo
• Beam search: mantiene k mejores hipótesis — un compromiso entre precisión y velocidad (k típico = 4–10)
• CRF (Conditional Random Fields): parámetros de transición entrenables sobre el decodificador Viterbi
• LLM reranking: un modelo de lenguaje clasifica el conjunto final de candidatos

Qué añaden beam search y CRF

El beam search ocupa una posición intermedia: mantiene k mejores hipótesis en lugar de una. Con k = 1 coincide con greedy; con k = ∞ equivale a la búsqueda exhaustiva. Valores de 4 a 10 proporcionaban un equilibrio razonable en los sistemas clásicos de MT, incluido Google Translate antes de la transición a los transformers.

El CRF (Campos Aleatorios Condicionales) añade parámetros de transición entrenables: en lugar de probabilidades fijas, el modelo aprende a partir de los datos qué secuencias de etiquetas son plausibles. Según los resultados del benchmark CoNLL-2003, el BiLSTM-CRF superó al BiLSTM sin CRF en 1–2 puntos porcentuales de F1 — una mejora consistente que otorgó al CRF un papel estándar en los pipelines de NER antes de la aparición de BERT.

"Mediante un contraejemplo muestro por qué la mejor elección local

pierde frente a la global — y también dónde termina la búsqueda de estructura y comienza la generación de texto", formula el autor del artículo en Habr la idea central.

Dónde encajan los LLMs en esta cadena

Los transformers no usan Viterbi directamente: el texto se genera de forma autorregresiva, token a token; el método estándar de decodificación es beam search o sampling (nucleus, temperature). El LLM reranking cierra la brecha en el siguiente nivel: el modelo genera 10–20 candidatos de respuesta, y luego un LLM separado (o el mismo, con un prompt diferente) los clasifica según criterios de calidad — coherencia, precisión factual, cumplimiento de la instrucción.

Como señala el autor, es precisamente aquí donde se encuentra la frontera entre la búsqueda de estructura y la generación de texto — y comprender esta frontera explica por qué el reranking en los pipelines de producción de LLM sigue proporcionando una mejora de calidad medible en métricas automáticas.

Qué significa esto

La cadena greedy → Viterbi → beam search → CRF → LLM reranking es la evolución de un único principio: la búsqueda del mejor camino global a través del espacio de significados posibles. Comprender esta jerarquía ayuda a elegir el método de decodificación adecuado para una tarea de NLP específica y explica las decisiones arquitectónicas de los modelos de lenguaje modernos.

Preguntas frecuentes

¿En qué se diferencia el algoritmo Viterbi del beam search?

Viterbi garantiza encontrar el camino globalmente óptimo a través de todos los estados — es un algoritmo exacto con búsqueda exhaustiva. El beam search mantiene solo k mejores hipótesis en cada paso: es más rápido, pero no garantiza la optimalidad.

¿Se usa Viterbi en los LLMs modernos?

Viterbi no se usa directamente en los transformers: la generación autorregresiva requiere beam search o sampling. Viterbi sigue siendo relevante en las capas CRF sobre encoders — por ejemplo, en tareas de NER y POS tagging basadas en arquitecturas de tipo BERT.