Viterbi Algorithm (1967) › Connections to Modern Sequence Models

The relationship between the Viterbi algorithm and modern language models reveals how fundamental insights persist across paradigm shifts. Transformer models don't use explicit dynamic programming, but they face the same core challenge: generating or decoding sequences optimally. The attention mechanism that allows transformers to model dependencies across entire sequences can be viewed as a learned alternative to the Markov assumption.instead of assuming dependencies only to the previous state, attention learns which past positions are most relevant.

Beam search in neural language models is a direct conceptual descendant of Viterbi's pruning strategy. Instead of exploring all possible continuations, beam search maintains the $k$ most promising partial sequences, expanding only from those. This is exactly what Viterbi does for each state.maintain the single best path and expand only from that. Beam search generalizes this to maintaining multiple hypotheses, but the core idea of pruning unlikely paths remains identical.

The contrast between HMMs decoded with Viterbi and modern autoregressive models highlights an important trade-off. Viterbi decoding finds the globally optimal sequence according to the model, but requires processing the entire sequence before producing any output. Autoregressive models generate sequences left-to-right, making local decisions at each step. They're more flexible (can generate indefinitely long sequences) but don't guarantee global optimality.each decision is made based on what's been generated so far, without knowledge of future tokens.

Some modern systems attempt to bridge this gap. Non-autoregressive translation models generate all tokens in parallel, then use iterative refinement to improve the sequence.a process that shares some conceptual similarity with Viterbi's global optimization approach. These models trade the efficiency of autoregressive generation for the potential of better global coherence, though in practice they haven't yet surpassed autoregressive models in most applications.

The Viterbi algorithm also influenced how researchers think about training sequence models. The forward-backward algorithm, closely related to Viterbi, is used in the expectation step of Baum-Welch training for HMMs. This pattern.using efficient dynamic programming for inference during training.appears in other contexts, like the forward and backward passes in neural sequence models. The efficient computation of gradients through sequences relies on similar dynamic programming principles.