Viterbi, beam search and LLM reranking: how an algorithm picks one meaning out of many

In 2026, an author on Habr traces a line from classic NLP algorithms to LLM reranking through a single principle: pick not the best step at each move, but the best path through the whole sequence. The explanation runs on an unlikely example, the interpretation of Tarot cards.

Why greedy decoding gives the wrong result

A greedy algorithm picks the most probable option at each step, without regard to the context that follows. In NLP tasks such as part-of-speech tagging (POS tagging) and named entity recognition (NER), this causes systematic errors: a locally best tag can break the consistency of the entire sequence.

The Viterbi algorithm solves the problem with dynamic programming. It considers all paths through the hidden states at once and finds the global optimum. Its 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. That is more expensive, but it guarantees optimality.

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

What beam search and CRF add

Beam search sits in the middle: it keeps the k best hypotheses instead of one. At k = 1 it is identical to greedy; at k = ∞ it becomes exhaustive search. Values from 4 to 10 gave a reasonable balance in classic MT systems, including Google Translate before its move to transformers.

CRFs (Conditional Random Fields) add trainable transition parameters. Instead of fixed probabilities, the model learns from data which tag sequences are plausible. On the CoNLL-2003 benchmark, BiLSTM-CRF outperformed BiLSTM without a CRF by 1–2 percentage points of F1. That consistent gain made CRF a standard component of NER pipelines until BERT arrived.

"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 author says of the article's central idea.

Where LLMs fit into this chain

Transformers do not use Viterbi directly: text is generated autoregressively, token by token, and the standard decoding methods are beam search or sampling (nucleus, temperature). LLM reranking closes the gap at the next level. The model generates 10–20 candidate answers, then a separate LLM (or the same one with a different prompt) ranks them on quality criteria such as coherence, factual accuracy and adherence to the instruction.

As the author notes, this is where the line falls between searching for structure and generating text. Understanding that line also explains why reranking in production LLM pipelines still delivers a measurable quality gain 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 you choose a decoding method for a specific NLP task and explains the architectural decisions behind 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 that covers every path. Beam search keeps only the k best hypotheses at each step. It is faster, but does not guarantee optimality.

Is Viterbi used in modern LLMs?

Transformers do not apply Viterbi directly: autoregressive generation calls for beam search or sampling. Viterbi remains relevant in CRF layers on top of encoders, for example in NER and POS tagging tasks built on BERT-like architectures.