Viterbi, beam search y LLM reranking: cómo un algoritmo elige un solo significado entre muchos

En 2026, un autor de Habr traza una cadena que va de los algoritmos clásicos de NLP al LLM reranking a partir de un único principio: no el mejor paso en cada turno, sino el mejor camino a lo largo de toda la secuencia. Lo explica con un ejemplo de interpretación de cartas del Tarot.

Por qué el algoritmo greedy da un resultado erróneo

El algoritmo greedy elige la opción más probable en cada paso, sin tener en cuenta el contexto posterior. En tareas de NLP como el etiquetado de categorías gramaticales (POS tagging) o el reconocimiento de entidades nombradas (NER), esto provoca errores sistemáticos: la mejor etiqueta a nivel local puede romper la coherencia de toda la secuencia.

El algoritmo de Viterbi resuelve el problema mediante programación dinámica: evalúa a la vez todos los caminos a través de los estados ocultos y encuentra el óptimo global. Su complejidad computacional es O(N × T²), frente a O(N × T) del greedy, donde N es la longitud de la secuencia y T, el número de estados. Es más caro, 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: conserva las k mejores hipótesis; es un compromiso entre precisión y velocidad (k típico = 4–10)
• CRF (Conditional Random Fields): parámetros de transición entrenables sobre un decodificador Viterbi
• LLM reranking: un modelo de lenguaje ordena el conjunto final de candidatos

Qué aportan beam search y CRF

El beam search ocupa una posición intermedia: conserva las k mejores hipótesis en lugar de una sola. Con k = 1 coincide con greedy; con k = ∞, con la búsqueda exhaustiva. Los valores de 4 a 10 ofrecían un equilibrio razonable en los sistemas clásicos de traducción automática, incluido Google Translate antes de su paso a los transformers.

Los CRF (campos aleatorios condicionales) añaden parámetros de transición entrenables: en lugar de probabilidades fijas, el modelo aprende de los datos qué secuencias de etiquetas son verosímiles. Según los resultados del benchmark CoNLL-2003, BiLSTM-CRF superaba a BiLSTM sin CRF en 1–2 puntos porcentuales de F1. Esa mejora estable convirtió a los CRF en un componente estándar de los pipelines de NER hasta la llegada de BERT.

«Con 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 dónde empieza la generación de texto», formula la idea central el autor del artículo en Habr.

Dónde encajan los LLM en esta cadena

Los transformers no usan Viterbi de forma directa: el texto se genera de manera autorregresiva, token a token. Los métodos de decodificación estándar son el beam search o el sampling (nucleus, temperature). El LLM reranking cubre la brecha en el siguiente nivel: el modelo genera entre 10 y 20 variantes de respuesta y luego un LLM aparte (o el mismo, con otro prompt) las ordena según criterios de calidad: coherencia, exactitud factual y ajuste a la instrucción.

Como señala el autor, ahí se sitúa la frontera entre la búsqueda de estructura y la generación de texto. Entender esa frontera explica por qué el reranking en los pipelines de LLM en producción sigue aportando una mejora medible en las métricas automáticas.

Qué significa esto

La cadena greedy → Viterbi → beam search → CRF → LLM reranking es la evolución de un mismo principio: buscar el mejor camino global a través del espacio de significados posibles. Entender esta jerarquía ayuda a elegir el método de decodificación adecuado para cada tarea de NLP y explica las decisiones de arquitectura de los modelos de lenguaje actuales.

Preguntas frecuentes

¿En qué se diferencia el algoritmo de

Viterbi del beam search?

Viterbi garantiza encontrar el camino globalmente óptimo a través de todos los estados: es un algoritmo exacto con exploración completa. El beam search conserva solo las k mejores hipótesis en cada paso: es más rápido, pero no garantiza la optimalidad.

¿Se usa Viterbi en los LLM actuales?

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