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

A Habr author in 2026 builds a chain from classical NLP algorithms to LLM-reranking through a single principle: not the best step at each move, but the best path through the entire sequence — and explains this using the example of Tarot card interpretation.

Why greedy gives the wrong result

The greedy algorithm selects the most probable option at each step in isolation from subsequent context. In NLP tasks — part-of-speech tagging (POS tagging), named entity recognition (NER) — this leads to systematic errors: a locally optimal tag can destroy the coherence of the entire sequence.

The Viterbi algorithm solves the problem using dynamic programming: it considers all paths through hidden states simultaneously and finds the global optimum. Computational complexity is O(N × T²) versus O(N × T) for greedy, where N is the sequence length and T is the number of states; this is more expensive but guarantees optimality.

• Greedy: O(N × T), fast, no guarantee of global optimum
• Viterbi: O(N × T²), exact global optimum according to the model
• Beam search: keeps k best hypotheses — a trade-off between accuracy and speed (typical k = 4–10)
• CRF (Conditional Random Fields): learnable transition parameters on top of the Viterbi decoder
• LLM reranking: a language model ranks the final set of candidates

What beam search and CRF add

Beam search occupies a middle ground: it keeps k best hypotheses instead of one. At k = 1 it matches greedy; at k = ∞ it matches exhaustive search. Values from 4 to 10 provided a reasonable balance in classic MT systems, including Google Translate before the transition to transformers.

CRF (Conditional Random Fields) adds learnable transition parameters: instead of fixed probabilities, the model learns from data which tag sequences are plausible. According to CoNLL-2003 benchmark results, BiLSTM-CRF outperformed BiLSTM without CRF by 1–2 F1 percentage points — a consistent gain that secured CRF's standard role in NER pipelines before the advent of BERT.

"Using a counterexample, I show why the best local choice loses to the global one — and also where the search for structure ends and text generation begins," the

Habr article author formulates the key idea.

Where LLMs fit into this chain

Transformers do not use Viterbi directly: text is generated autoregressively, token by token; the standard decoding method is beam search or sampling (nucleus, temperature). LLM reranking closes the gap at the next level: the model generates 10–20 response candidates, then a separate LLM (or the same one, with a different prompt) ranks them by quality criteria — coherence, factual accuracy, instruction compliance.

As the author notes, this is precisely where the boundary lies between searching for structure and generating text — and understanding this boundary explains why reranking in production LLM pipelines still yields a measurable quality improvement on automatic metrics.

What this means

The chain greedy → Viterbi → beam search → CRF → LLM reranking is the evolution of a single principle: searching for the globally best path through the space of possible meanings. Understanding this hierarchy helps choose the decoding method for a specific NLP task and explains the architectural decisions of modern language models.

Frequently asked questions

How does the Viterbi algorithm differ from beam search?

Viterbi guarantees finding the globally optimal path through all states — it is an exact algorithm with exhaustive search. Beam search keeps only k best hypotheses at each step: it is faster but does not guarantee optimality.

Is Viterbi used in modern LLMs?

Viterbi is not used directly in transformers: autoregressive generation requires beam search or sampling. Viterbi remains relevant in CRF layers on top of encoders — for example, in NER and POS tagging tasks based on BERT-like architectures.