Understanding Viterbi Decoding in Linear-Chain CRFs

Sequence labelling looks local only until two plausible labels compete. A token-level classifier can assign one score to every label at every position, but it cannot say that I-PER should usually follow B-PER, or that a medical problem span is unlikely to jump directly into a medication span. A linear-chain conditional random field (CRF) adds those dependencies while keeping exact decoding possible.

This article develops Viterbi decoding from the CRF sequence score rather than presenting the recurrence as a formula to memorize. The essential move is to retain the best prefix for each possible final label. Prefixes ending in the same label have identical options in the future, so all but the best one can be discarded.

Motivation#

Let an input sequence be $\mathbf{x}=(x_1,\ldots,x_T)$, and let its label sequence be $\mathbf{y}=(y_1,\ldots,y_T)$, where every $y_t$ belongs to a set of $K$ labels. In named entity recognition, the input could be clinical tokens and the labels could be BIO tags such as B-PROBLEM, I-PROBLEM, and O.

A neural encoder produces an emission score $s_t(j,\mathbf{x})$: how compatible position $t$ is with label $j$. These scores are not probabilities and need not sum to one. The CRF also learns a transition score $A_{ij}$ for moving from label $i$ at position $t-1$ to label $j$ at position $t$.

Independent decoding would choose the highest emission at every position:

That decision ignores the transition matrix. Viterbi instead finds one sequence whose total score is maximal:

The distinction matters whenever a slightly weaker local label enables a much more coherent sequence.

Sequence scoring#

For now, omit explicit start and stop states. The score of a complete label sequence is

The first sum collects one emission at every position. The second collects one transition for every adjacent pair. Our matrix convention is important: row $i$ is the previous label and column $j$ is the current label.

Many implementations add vectors $a^{\text{start}}$ and $a^{\text{stop}}$:

They change initialization and termination, not the core recurrence.

During probabilistic training, the CRF defines

where

The normalizer $Z(\mathbf{x})$ is essential for likelihoods, but it does not affect the most likely sequence for a fixed input. Since the exponential is monotone and the denominator is shared by every candidate, MAP decoding reduces to maximizing the unnormalized score.

Why brute force is intractable#

There are $K^T$ possible label sequences. With nine labels and a sentence of 40 tokens, exhaustive search considers $9^{40}$, roughly $1.5\times10^{38}$, paths. Scoring a path is cheap; enumerating the paths is impossible.

The layered graph below makes the redundancy visible. Every path reaching label $j$ at time $t$ has the same set of outgoing transitions. If two such prefixes have scores 12.4 and 10.1, extending the weaker prefix with any identical suffix keeps it 2.3 points behind. It can never recover.

Dynamic-programming decomposition#

Define the Viterbi state

In words, $\delta_t(j)$ is the score of the best prefix through position $t$ subject to ending with label $j$. This final condition is what makes the state sufficient. A single global best prefix is not enough because different end labels offer different transition scores at the next position.

With start scores, initialization is

There is no previous ordinary label at $t=1$, so no entry from $A$ is used.

Derivation of the recurrence#

Suppose the current label at position $t$ is fixed to $j$. The preceding label must be some $i$. A candidate path is composed of:

1. the best prefix ending in $i$, with score $\delta_{t-1}(i)$;
2. the transition from $i$ to $j$, with score $A_{ij}$;
3. the current emission, with score $s_t(j,\mathbf{x})$.

Maximizing over the only unresolved boundary label gives

Because the emission does not depend on $i$, an equivalent implementation is

The explicit form is often easier to audit against tensor broadcasting.

At the last position, include the stop score:

If start and stop scores are not modelled, use zero vectors.

Backpointers#

The dynamic program above returns the best score, but a decoder needs the labels. At every state, store which predecessor achieved the maximum:

After selecting the final label, move backward:

This is why taking argmax independently from each row of the completed score table is wrong. A high-scoring state at time $t-1$ may not be the predecessor of the selected state at time $t$. The backpointer records the compatible choice.

score[j] ← start[j] + emission[1, j] for every label j
 
for t ← 2 … T:
    candidate[i, j] ← score[i] + transition[i, j]
    backpointer[t, j] ← argmax_i candidate[i, j]
    score[j] ← max_i candidate[i, j] + emission[t, j]
 
last ← argmax_j (score[j] + stop[j])
path[T] ← last
 
for t ← T … 2:
    path[t - 1] ← backpointer[t, path[t]]
 
return path and its score

Complexity analysis#

At each of $T-1$ recurrent steps, every one of $K$ destination labels compares all $K$ source labels. Time complexity is therefore $O(TK^2)$. The full backpointer table stores one integer per position and label, so reconstruction takes $O(TK)$ memory. The score calculation itself needs only the previous and current rows, or $O(K)$ memory.

Time

O(TK²)

Dense transition matrix

Backpointers

O(TK)

Required for path recovery

Rolling scores

O(K)

Two score vectors suffice

This is exact, not a beam-search approximation. Constraints can also make it cheaper in practice: invalid BIO transitions may receive negative infinity, and a sparse transition graph can avoid evaluating forbidden edges.

For batched neural inference, emissions usually have shape [batch, time, labels]. A broadcasted addition forms scores of shape [batch, previous_label, current_label] at each time step. Masks must prevent padded positions from overwriting the last valid state for shorter sequences.

Python implementation#

The NumPy implementation below chooses the transition convention used throughout this article: transitions[i, j] scores a move from previous label i to current label j.

from __future__ import annotations
 
import numpy as np
from numpy.typing import NDArray
 
 
def viterbi_decode(
    emissions: NDArray[np.floating],
    transitions: NDArray[np.floating],
    start: NDArray[np.floating] | None = None,
    stop: NDArray[np.floating] | None = None,
) -> tuple[list[int], float]:
    """Return the highest-scoring label path and its unnormalized score."""
    if emissions.ndim != 2:
        raise ValueError("emissions must have shape [time, labels]")
    time_steps, labels = emissions.shape
    if time_steps == 0 or labels == 0:
        raise ValueError("emissions must describe a non-empty sequence")
    if transitions.shape != (labels, labels):
        raise ValueError("transitions must have shape [labels, labels]")
 
    start_scores = (
        np.zeros(labels, dtype=emissions.dtype) if start is None else np.asarray(start)
    )
    stop_scores = (
        np.zeros(labels, dtype=emissions.dtype) if stop is None else np.asarray(stop)
    )
    if start_scores.shape != (labels,) or stop_scores.shape != (labels,):
        raise ValueError("start and stop must each have shape [labels]")
 
    scores = start_scores + emissions[0]
    backpointers = np.full((time_steps, labels), -1, dtype=np.int64)
 
    for t in range(1, time_steps):
        # candidate[i, j] extends previous label i with current label j.
        candidate = scores[:, None] + transitions
        backpointers[t] = np.argmax(candidate, axis=0)
        scores = np.max(candidate, axis=0) + emissions[t]
 
    terminal_scores = scores + stop_scores
    last = int(np.argmax(terminal_scores))
    best_score = float(terminal_scores[last])
 
    path = [last]
    for t in range(time_steps - 1, 0, -1):
        last = int(backpointers[t, last])
        path.append(last)
    path.reverse()
    return path, best_score

The update is deliberately split into a transition maximum and an emission addition. A fused expression is shorter, but this form exposes the two axes at which most implementation errors occur.

For a differentiable PyTorch CRF, decoding is normally run outside gradient tracking. Training uses the gold path score and the log partition function, not the Viterbi score. Replacing logsumexp with max during negative log-likelihood training changes the objective.

A small worked example#

Consider two tokens, “time flies”, and two labels: noun $N$ and verb $V$. Use zero start and stop scores. Let rows be time positions and columns be labels:

At the first token:

At the second token, the best paths ending in $N$ and $V$ are

Both maxima come from previous label $N$, so $\psi_2(N)=N$ and $\psi_2(V)=N$. The best final label is $V$; following its backpointer gives the path $(N,V)$ with score 3.9.

Notice that the locally strongest second-token emission is already $V$, but the decoder still needs the transition calculation to identify its predecessor and evaluate the sequence consistently.

Common implementation mistakes#

Reversing the transition axes#

Some libraries define transitions[current, previous]; others use transitions[previous, current]. Both are valid. Mixing the convention between training, gold-sequence scoring, and decoding is not. Write the candidate tensor shape beside the broadcasting expression and test it with an asymmetric matrix.

Applying the emission on the wrong axis#

The current emission $s_t(j)$ is added after maximizing over predecessor $i$. In a candidate tensor indexed by [i, j], it broadcasts across rows, not columns. An emission accidentally indexed by $i$ scores the previous state twice and the current state not at all.

Greedy backtracking#

Choosing argmax(delta[t]) at every time step does not recover one connected path. Select the final state once and follow stored predecessors. The result may pass simple tests when emissions dominate, which makes this bug unusually persistent.

Ignoring sequence lengths in a batch#

If padded time steps run the recurrence, their arbitrary emissions and transitions can replace the valid terminal score. Use a mask to retain the old score when a sequence has ended, and begin backtracking at each sequence’s last valid position.

Mishandling impossible transitions#

For constrained BIO decoding, invalid transitions can be assigned -inf. Be careful when every predecessor of a state is impossible: an entire row may remain -inf. In mixed-precision code, a large finite negative sentinel is sometimes more stable, but it must be low enough never to win.

Forgetting start and stop scores#

If the model learned boundary parameters, omitting them at inference changes the model being decoded. Conversely, do not silently add boundaries to a model trained without them.

Relationship between Viterbi and the forward algorithm#

Viterbi and the forward algorithm traverse the same dynamic-programming graph. They differ only in how alternative prefixes are combined.

The log-space forward state is

It aggregates the mass of all paths ending in $j$. At termination, logsumexp over the final states (plus stop scores) yields $\log Z(\mathbf{x})$. Viterbi replaces logsumexp with max, retaining only the highest-scoring path:

This is sometimes described using semirings. The forward algorithm operates in the log semiring, where path alternatives combine with logsumexp; Viterbi operates in the max-plus semiring, where they combine with max. Both use addition to extend a path.

The distinction answers two different questions:

• Forward: what total probability mass do all label sequences contribute?
• Viterbi: which single label sequence has the greatest score?

Posterior decoding asks yet another question—choosing labels from marginal probabilities—and need not return the MAP sequence. In a constrained label space, independent marginal choices can even form an invalid transition.

Practical checklist#

Before trusting a decoder:

1. document whether $A_{ij}$ means $i\to j$ or $j\to i$;
2. compare against exhaustive enumeration on tiny cases;
3. test a length-one sequence, where no ordinary transition is used;
4. test non-zero start and stop scores;
5. test ties and decide whether deterministic first-index behavior is acceptable;
6. test batches with different valid lengths;
7. verify the decoded score by rescoring the returned path directly.

The larger lesson extends beyond CRFs. Dynamic programming becomes possible when many histories share the same future-relevant state. Here that state is simply the last label. Once that equivalence is visible, an exponential search becomes a compact table plus a trail of backpointers.

References#