Viterbi Decoding

The Viterbi algorithm performs exact MAP inference by finding the single best label sequence that maximizes the conditional probability P(Y|X). Unlike greedy decoding, which selects the highest-probability label at each step independently, Viterbi considers the entire sequence context to avoid invalid transitions, such as an I-ORG tag following an O tag in BIO notation.

The algorithm operates on a trellis diagram where columns represent observation tokens and rows represent possible hidden states. At each time step, it recursively computes the maximum cumulative score for reaching each state by considering:

• The emission score from the CRF for the current token
• The transition score from the previous state
• The previous path probability stored in the dynamic programming table

A critical function of Viterbi decoding is enforcing hard grammatical constraints on label sequences. The transition matrix learned by the CRF assigns near-zero probabilities to illegal transitions. During decoding, Viterbi naturally avoids paths like:

• B-LOC → I-PER (type mismatch)
• I-ORG → B-ORG (missing beginning tag)
• O → I-MISC (inside without beginning) This guarantees a well-formed BIO output without post-processing rules.

To retrieve the optimal path, Viterbi maintains a backpointer matrix that records which previous state led to the maximum score for each current state. After the forward pass reaches the final token, the algorithm traces backward from the highest-scoring final state through these pointers to reconstruct the complete label sequence. This avoids storing all exponential possible paths explicitly.

In practice, Viterbi is implemented in log-probability space to prevent numerical underflow. Multiplying many small transition and emission probabilities quickly approaches zero. By summing log-probabilities instead, the algorithm maintains numerical stability even for very long sequences. The log-sum-exp trick is used when combining path scores.

The time complexity of Viterbi decoding is O(T × S²) where T is the sequence length and S is the number of states. This is dramatically more efficient than the naive O(Sᵀ) brute-force enumeration. For a typical NER task with 9 BIO states and a 50-token sentence, Viterbi evaluates approximately 4,050 transitions instead of 9⁵⁰ possible paths.